[RFC,07/11] batman-adv: add broadcast duplicate check

diff --git a/bridge_loop_avoidance.c b/bridge_loop_avoidance.c
index a787c96..b1f2abc 100644
--- a/bridge_loop_avoidance.c
+++ b/bridge_loop_avoidance.c
@@ -970,8 +970,16 @@  timer:
 /* initialize all bla structures */
 int bla_init(struct bat_priv *bat_priv)
 {
+	int i;
+
 	bat_dbg(DBG_BLA, bat_priv, "bla hash registering\n");
 
+	/* initialize the duplicate list */
+	for (i = 0; i < DUPLIST_SIZE; i++)
+		bat_priv->bcast_duplist[i].entrytime =
+			jiffies - msecs_to_jiffies(DUPLIST_TIMEOUT);
+	bat_priv->bcast_duplist_curr = 0;
+
 	if (bat_priv->claim_hash)
 		return 1;
 
@@ -989,6 +997,71 @@  int bla_init(struct bat_priv *bat_priv)
 
 /**
  * @bat_priv: the bat priv with all the soft interface information
+ * @bcast_packet: originator mac address
+ * @hdr_size: maximum length of the frame
+ *
+ * check if it is on our broadcast list. Another gateway might
+ * have sent the same packet because it is connected to the same backbone,
+ * so we have to remove this duplicate.
+ *
+ * This is performed by checking the CRC, which will tell us
+ * with a good chance that it is the same packet. If it is furthermore
+ * sent by another host, drop it. We allow equal packets from
+ * the same host however as this might be intended.
+ *
+ **/
+
+int bla_check_bcast_duplist(struct bat_priv *bat_priv,
+		struct bcast_packet *bcast_packet, int hdr_size)
+{
+	int i, length, curr;
+	uint8_t *content;
+	uint16_t crc;
+	struct bcast_duplist_entry *entry;
+
+	length = hdr_size - sizeof(*bcast_packet);
+	content = (uint8_t *) bcast_packet;
+	content += sizeof(*bcast_packet);
+
+	/* calculate the crc ... */
+	crc = crc16(0, content, length);
+
+	for (i = 0 ; i < DUPLIST_SIZE; i++) {
+		curr = (bat_priv->bcast_duplist_curr + i) % DUPLIST_SIZE;
+		entry = &bat_priv->bcast_duplist[curr];
+
+		/* we can stop searching if the entry is too old ;
+		 * later entries will be even older */
+		if (time_after(jiffies, entry->entrytime
+				+ msecs_to_jiffies(DUPLIST_TIMEOUT)))
+			break;
+
+		if (entry->crc != crc)
+			continue;
+
+		if (compare_eth(entry->orig, bcast_packet->orig))
+			continue;
+
+		/* this entry seems to match: same crc, not too old,
+		 * and from another gw. therefore return 1 to forbid it. */
+		return 1;
+	}
+	/* not found, add a new entry (overwrite the oldest entry) */
+	curr = (bat_priv->bcast_duplist_curr + DUPLIST_SIZE - 1) % DUPLIST_SIZE;
+	entry = &bat_priv->bcast_duplist[curr];
+	entry->crc = crc;
+	entry->entrytime = jiffies;
+	memcpy(entry->orig, bcast_packet->orig, ETH_ALEN);
+	bat_priv->bcast_duplist_curr = curr;
+
+	/* allow it, its the first occurence. */
+	return 0;
+}
+
+
+
+/**
+ * @bat_priv: the bat priv with all the soft interface information
  * @orig: originator mac address
  *
  * check if the originator is a gateway for any VLAN ID.
diff --git a/bridge_loop_avoidance.h b/bridge_loop_avoidance.h
index bafcfac..60dcb1b 100644
--- a/bridge_loop_avoidance.h
+++ b/bridge_loop_avoidance.h
@@ -25,6 +25,8 @@  int bla_is_backbone_gw(struct sk_buff *skb,
 		struct orig_node *orig_node, int hdr_size);
 int bla_claim_table_seq_print_text(struct seq_file *seq, void *offset);
 int bla_is_backbone_gw_orig(struct bat_priv *bat_priv, uint8_t *orig);
+int bla_check_bcast_duplist(struct bat_priv *bat_priv,
+		struct bcast_packet *bcast_packet, int hdr_size);
 void bla_update_orig_address(struct bat_priv *bat_priv, uint8_t *newaddr);
 int bla_init(struct bat_priv *bat_priv);
 void bla_free(struct bat_priv *bat_priv);
diff --git a/main.h b/main.h
index 1bd41f1..f96d817 100644
--- a/main.h
+++ b/main.h
@@ -82,6 +82,9 @@ 
 #define BLA_PERIOD_LENGTH	10000	/* 10 seconds */
 #define BLA_BACKBONE_TIMEOUT	(BLA_PERIOD_LENGTH * 3)
 #define BLA_CLAIM_TIMEOUT	(BLA_PERIOD_LENGTH * 10)
+
+#define DUPLIST_SIZE		16
+#define DUPLIST_TIMEOUT		500	/* 500 ms */
 /* don't reset again within 30 seconds */
 #define RESET_PROTECTION_MS 30000
 #define EXPECTED_SEQNO_RANGE	65536
diff --git a/routing.c b/routing.c
index 1554f60..00e5339 100644
--- a/routing.c
+++ b/routing.c
@@ -1078,6 +1078,10 @@  int recv_bcast_packet(struct sk_buff *skb, struct hard_iface *recv_if)
 
 	spin_unlock_bh(&orig_node->bcast_seqno_lock);
 
+	/* check whether this has been sent by another originator before */
+	if (bla_check_bcast_duplist(bat_priv, bcast_packet, hdr_size))
+		goto out;
+
 	/* rebroadcast packet */
 	add_bcast_packet_to_list(bat_priv, skb, 1);
 
diff --git a/types.h b/types.h
index 0ca2d4c..5f02447 100644
--- a/types.h
+++ b/types.h
@@ -139,6 +139,11 @@  struct neigh_node {
 	spinlock_t tq_lock;	/* protects: tq_recv, tq_index */
 };
 
+struct bcast_duplist_entry {
+	uint8_t orig[ETH_ALEN];
+	uint16_t crc;
+	unsigned long entrytime;
+};
 
 struct bat_priv {
 	atomic_t mesh_state;
@@ -185,6 +190,8 @@  struct bat_priv {
 	struct list_head tt_req_list; /* list of pending tt_requests */
 	struct list_head tt_roam_list;
 	struct hashtable_t *vis_hash;
+	struct bcast_duplist_entry bcast_duplist[DUPLIST_SIZE];
+	int bcast_duplist_curr;
 	spinlock_t forw_bat_list_lock; /* protects forw_bat_list */
 	spinlock_t forw_bcast_list_lock; /* protects  */
 	spinlock_t tt_changes_list_lock; /* protects tt_changes */