[B.A.T.M.A.N.] [PATCHv4 0/7] DAT: Distributed ARP Table

[B.A.T.M.A.N.] [PATCHv4 0/7] DAT: Distributed ARP Table

[Antonio Quartulli]

Hello people,

****
This is the fourth version of this patchset. The whole code has been reviewed
after some discussions on irc. Several bugs have been spotted and fixed.
Thanks Marek, Sven and Simon.
This should be a final version, unless some other mistakes/problems are find.

This patchset assume that patch
[PATCH] batman-adv: add biggest_unsigned_int(x) macro
has already been applied
****


as most of you may already know, last summer I've been working on the
B.A.T.M.A.N.-Adv GSoC project named "DAT: Distributed ARP Table". For who wants
to get deeper into the details of the project there are two links:
- The GSoC proposal [1]
- The DAT wikipage on open-mesh.org [2], with status and ideas description

Just to recap: DAT is a distributes hash table meant to store ARP entries for
fast lookup. In a normal scenario, whenever a node wants to communicate with
another one, it first needs to issue a broadcast ARP request in order to
retrieve its PHY/MAC address. In a sparse network a broadcast message could be
lost several times before reaching the real destination so creating high
latencies. With DAT, every ARP entries (a pair [IP addr, MAC addr]) is stored on
a "computed" set of nodes, therefore in case of ARP request theses nodes can
directly be contacted (in unicast) and the needed information can be quickly
fetched.


Cheers,
Antonio

[1] http://www.google-melange.com/gsoc/project/google/gsoc2011/ordex/4001
[2] http://www.open-mesh.org/wiki/batman-adv/GSOC2011_DAT

[B.A.T.M.A.N.] [PATCHv4 1/7] batman-adv: implement an helper function to forge unicast packets

[Antonio Quartulli]

A new function named prepare_unicast_packet() has been implemented so that it can
do all the needed operations to set up a skb for unicast sending. It is general
enough to be used in every context. Helpful for later developments

Signed-off-by: Antonio Quartulli <ordex@autistici.org>
---
 unicast.c |   36 ++++++++++++++++++++++++------------
 unicast.h |    1 +
 2 files changed, 25 insertions(+), 12 deletions(-)

diff --git a/unicast.c b/unicast.c
index 6f3c659..d49f2cc 100644
--- a/unicast.c
+++ b/unicast.c
@@ -283,6 +283,29 @@ out:
 	return ret;
 }
 
+bool prepare_unicast_packet(struct sk_buff *skb, struct orig_node *orig_node)
+{
+	struct unicast_packet *unicast_packet;
+
+	if (my_skb_head_push(skb, sizeof(*unicast_packet)) < 0)
+		return false;
+
+	unicast_packet = (struct unicast_packet *)skb->data;
+
+	unicast_packet->header.version = COMPAT_VERSION;
+	/* batman packet type: unicast */
+	unicast_packet->header.packet_type = BAT_UNICAST;
+	/* set unicast ttl */
+	unicast_packet->header.ttl = TTL;
+	/* copy the destination for faster routing */
+	memcpy(unicast_packet->dest, orig_node->orig, ETH_ALEN);
+	/* set the destination tt version number */
+	unicast_packet->ttvn =
+		(uint8_t)atomic_read(&orig_node->last_ttvn);
+
+	return true;
+}
+
 int unicast_send_skb(struct sk_buff *skb, struct bat_priv *bat_priv)
 {
 	struct ethhdr *ethhdr = (struct ethhdr *)skb->data;
@@ -315,22 +338,11 @@ find_router:
 	if (!neigh_node)
 		goto out;
 
-	if (my_skb_head_push(skb, sizeof(*unicast_packet)) < 0)
+	if (!prepare_unicast_packet(skb, orig_node))
 		goto out;
 
 	unicast_packet = (struct unicast_packet *)skb->data;
 
-	unicast_packet->header.version = COMPAT_VERSION;
-	/* batman packet type: unicast */
-	unicast_packet->header.packet_type = BAT_UNICAST;
-	/* set unicast ttl */
-	unicast_packet->header.ttl = TTL;
-	/* copy the destination for faster routing */
-	memcpy(unicast_packet->dest, orig_node->orig, ETH_ALEN);
-	/* set the destination tt version number */
-	unicast_packet->ttvn =
-		(uint8_t)atomic_read(&orig_node->last_ttvn);
-
 	if (atomic_read(&bat_priv->fragmentation) &&
 	    data_len + sizeof(*unicast_packet) >
 				neigh_node->if_incoming->net_dev->mtu) {
diff --git a/unicast.h b/unicast.h
index 8fd5535..63d0305 100644
--- a/unicast.h
+++ b/unicast.h
@@ -33,6 +33,7 @@ void frag_list_free(struct list_head *head);
 int unicast_send_skb(struct sk_buff *skb, struct bat_priv *bat_priv);
 int frag_send_skb(struct sk_buff *skb, struct bat_priv *bat_priv,
 		  struct hard_iface *hard_iface, const uint8_t dstaddr[]);
+bool prepare_unicast_packet(struct sk_buff *skb, struct orig_node *orig_node);
 
 static inline int frag_can_reassemble(const struct sk_buff *skb, int mtu)
 {
-- 
1.7.3.4

Re: [B.A.T.M.A.N.] [PATCHv4 1/7] batman-adv: implement an helper function to forge unicast packets

[Andrew Lunn]

On Thu, Nov 24, 2011 at 11:21:13PM +0100, Antonio Quartulli wrote:
> A new function named prepare_unicast_packet() has been implemented so that it can
> do all the needed operations to set up a skb for unicast sending. It is general
> enough to be used in every context. Helpful for later developments
> 
> Signed-off-by: Antonio Quartulli <ordex@autistici.org>
> ---
>  unicast.c |   36 ++++++++++++++++++++++++------------
>  unicast.h |    1 +
>  2 files changed, 25 insertions(+), 12 deletions(-)
> 
> diff --git a/unicast.c b/unicast.c
> index 6f3c659..d49f2cc 100644
> --- a/unicast.c
> +++ b/unicast.c
> @@ -283,6 +283,29 @@ out:
>  	return ret;
>  }
>  
> +bool prepare_unicast_packet(struct sk_buff *skb, struct orig_node *orig_node)
> +{
> +	struct unicast_packet *unicast_packet;
> +
> +	if (my_skb_head_push(skb, sizeof(*unicast_packet)) < 0)
> +		return false;
> +
> +	unicast_packet = (struct unicast_packet *)skb->data;
> +
> +	unicast_packet->header.version = COMPAT_VERSION;
> +	/* batman packet type: unicast */
> +	unicast_packet->header.packet_type = BAT_UNICAST;
> +	/* set unicast ttl */
> +	unicast_packet->header.ttl = TTL;

When Sven added this header structure, did he also add a function to
fill it in?

     Andrew

Re: [B.A.T.M.A.N.] [PATCHv4 1/7] batman-adv: implement an helper function to forge unicast packets

[Sven Eckelmann]

[-- Attachment #1: Type: text/plain, Size: 702 bytes --]

On Friday 25 November 2011 09:18:20 Andrew Lunn wrote:
[...]
> > +	unicast_packet = (struct unicast_packet *)skb->data;
> > +
> > +	unicast_packet->header.version = COMPAT_VERSION;
> > +	/* batman packet type: unicast */
> > +	unicast_packet->header.packet_type = BAT_UNICAST;
> > +	/* set unicast ttl */
> > +	unicast_packet->header.ttl = TTL;
> 
> When Sven added this header structure, did he also add a function to
> fill it in?

No, I didn't. The header structure part was just the "keep it safe" thing. The 
fancy stuff can come later. And I am not sure whether such a function would be 
useful. More interesting would be the TTL cleanup that Linus proposed a long 
time ago.

Kind regards,
	Sven

[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

[B.A.T.M.A.N.] [PATCHv4 2/7] batman-adv: add a new log level for DAT-ARP debugging

[Antonio Quartulli]

A new log level has been added to concentrate messages regarding DAT: ARP
snooping, requests, response and DHT related messages.
The new log level is named DBG_ARP

Signed-off-by: Antonio Quartulli <ordex@autistici.org>
---
 README      |    3 ++-
 bat_sysfs.c |    2 +-
 main.h      |    3 ++-
 3 files changed, 5 insertions(+), 3 deletions(-)

diff --git a/README b/README
index 7404c0a..856ca7e 100644
--- a/README
+++ b/README
@@ -224,7 +224,8 @@ abled  during run time. Following log_levels are defined:
 1 - Enable messages related to routing / flooding / broadcasting
 2 - Enable messages related to route added / changed / deleted
 4 - Enable messages related to translation table operations
-7 - Enable all messages
+8 - Enable messaged related to DAT, ARP snooping and parsing
+15 - Enable all messages
 
 The debug output can be changed at runtime  using  the  file
 /sys/class/net/bat0/mesh/log_level. e.g.
diff --git a/bat_sysfs.c b/bat_sysfs.c
index c25492f..ec2e437 100644
--- a/bat_sysfs.c
+++ b/bat_sysfs.c
@@ -390,7 +390,7 @@ BAT_ATTR_UINT(gw_sel_class, S_IRUGO | S_IWUSR, 1, TQ_MAX_VALUE,
 static BAT_ATTR(gw_bandwidth, S_IRUGO | S_IWUSR, show_gw_bwidth,
 		store_gw_bwidth);
 #ifdef CONFIG_BATMAN_ADV_DEBUG
-BAT_ATTR_UINT(log_level, S_IRUGO | S_IWUSR, 0, 7, NULL);
+BAT_ATTR_UINT(log_level, S_IRUGO | S_IWUSR, 0, 15, NULL);
 #endif
 
 static struct bat_attribute *mesh_attrs[] = {
diff --git a/main.h b/main.h
index 3c58235..5561bf7 100644
--- a/main.h
+++ b/main.h
@@ -120,7 +120,8 @@ enum dbg_level {
 	DBG_BATMAN = 1 << 0,
 	DBG_ROUTES = 1 << 1, /* route added / changed / deleted */
 	DBG_TT	   = 1 << 2, /* translation table operations */
-	DBG_ALL    = 7
+	DBG_ARP    = 1 << 3, /* snooped arp messages / dht operations */
+	DBG_ALL    = 15
 };
 
 
-- 
1.7.3.4

[B.A.T.M.A.N.] [PATCHv4 3/7] batman-adv: Distributed ARP Table - create the DHT helper functions

[Antonio Quartulli]

Add all the relevant functions in order to manage a Distributed Hash Table over
the B.A.T.M.A.N.-adv network. It will later be used to store several ARP entries
and implement DAT (Distributed ARP Table)

Signed-off-by: Antonio Quartulli <ordex@autistici.org>
---
 Makefile.kbuild         |    1 +
 distributed-arp-table.c |  182 +++++++++++++++++++++++++++++++++++++++++++++++
 distributed-arp-table.h |   55 ++++++++++++++
 hard-interface.c        |    5 ++
 main.h                  |    7 ++
 originator.c            |    2 +
 soft-interface.c        |    2 +
 types.h                 |    8 ++
 8 files changed, 262 insertions(+), 0 deletions(-)
 create mode 100644 distributed-arp-table.c
 create mode 100644 distributed-arp-table.h

diff --git a/Makefile.kbuild b/Makefile.kbuild
index bd7e93c..e8861cb 100644
--- a/Makefile.kbuild
+++ b/Makefile.kbuild
@@ -36,6 +36,7 @@ batman-adv-y += bat_debugfs.o
 batman-adv-y += bat_iv_ogm.o
 batman-adv-y += bat_sysfs.o
 batman-adv-y += bitarray.o
+batman-adv-y += distributed-arp-table.o
 batman-adv-y += gateway_client.o
 batman-adv-y += gateway_common.o
 batman-adv-y += hard-interface.o
diff --git a/distributed-arp-table.c b/distributed-arp-table.c
new file mode 100644
index 0000000..4c4e064
--- /dev/null
+++ b/distributed-arp-table.c
@@ -0,0 +1,182 @@
+/*
+ * Copyright (C) 2011 B.A.T.M.A.N. contributors:
+ *
+ * Antonio Quartulli
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of version 2 of the GNU General Public
+ * License as published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+ * 02110-1301, USA
+ *
+ */
+
+#include <linux/if_ether.h>
+#include <linux/if_arp.h>
+
+#include "main.h"
+#include "distributed-arp-table.h"
+#include "hard-interface.h"
+#include "originator.h"
+#include "send.h"
+#include "types.h"
+#include "unicast.h"
+
+/* Given a key, selects the candidates which the DHT message has to be sent to.
+ * An originator O is selected if and only if its DHT_ID value is one of three
+ * closest values (but not greater) then the hash value of the key.
+ * ip_dst is the key.
+ *
+ * return an array of size DHT_CANDIDATES_NUM */
+static struct dht_candidate *dht_select_candidates(struct bat_priv *bat_priv,
+						   uint32_t ip_dst)
+{
+	struct hashtable_t *hash = bat_priv->orig_hash;
+	struct hlist_node *node;
+	struct hlist_head *head;
+	struct orig_node *orig_node, *max_orig_node = NULL;
+	int select, i, j;
+	dat_addr_t last_max = DAT_ADDR_MAX, max, tmp_max, ip_key;
+	struct dht_candidate *res;
+	bool chosen_me = false;
+
+	if (!hash)
+		return NULL;
+
+	res = kmalloc(DHT_CANDIDATES_NUM * sizeof(*res), GFP_ATOMIC);
+	if (!res)
+		return NULL;
+
+	ip_key = (dat_addr_t)hash_ipv4(&ip_dst, DAT_ADDR_MAX);
+
+	bat_dbg(DBG_ARP, bat_priv, "DHT_SEL_CAND key: %pI4 %u\n", &ip_dst,
+		ip_key);
+
+	for (select = 0; select < DHT_CANDIDATES_NUM; select++) {
+		max = 0;
+		max_orig_node = NULL;
+		if (!chosen_me) {
+			/* if true, wrap around the key space */
+			if (bat_priv->dht_hash > ip_key)
+				max = DAT_ADDR_MAX - bat_priv->dht_hash +
+					ip_key;
+			else
+				max = ip_key - bat_priv->dht_hash;
+			max = bat_priv->dht_hash;
+			res[select].type = DHT_CANDIDATE_ME;
+		} else
+			res[select].type = DHT_CANDIDATE_NULL;
+		/* for all origins... */
+		for (i = 0; i < hash->size; i++) {
+			head = &hash->table[i];
+
+			rcu_read_lock();
+			hlist_for_each_entry_rcu(orig_node, node, head,
+						 hash_entry) {
+				if (orig_node->dht_hash > ip_key)
+					tmp_max = DAT_ADDR_MAX -
+						orig_node->dht_hash + ip_key;
+				else
+					tmp_max = ip_key - orig_node->dht_hash;
+
+				/* this is closest! */
+				if (tmp_max <= max)
+					continue;
+
+				/* this has already been selected */
+				if (tmp_max > last_max)
+					continue;
+
+				/* In case of hash collision we can select two
+				 * nodes with the same hash, but we have ensure
+				 * they are different */
+				if (tmp_max == last_max) {
+					for (j = 0; j < select; j++)
+						if (res[j].orig_node ==
+						    orig_node)
+							break;
+					if (j < select)
+						continue;
+				}
+
+				if (!atomic_inc_not_zero(&orig_node->refcount))
+					continue;
+
+				max = tmp_max;
+				if (max_orig_node)
+					orig_node_free_ref(max_orig_node);
+				max_orig_node = orig_node;
+			}
+			rcu_read_unlock();
+		}
+		last_max = max;
+		if (max_orig_node) {
+			res[select].type = DHT_CANDIDATE_ORIG;
+			res[select].orig_node = max_orig_node;
+			bat_dbg(DBG_ARP, bat_priv, "DHT_SEL_CAND %d: %pM %u\n",
+				select, max_orig_node->orig, max);
+		}
+		if (res[select].type == DHT_CANDIDATE_ME) {
+			chosen_me = true;
+			bat_dbg(DBG_ARP, bat_priv, "DHT_SEL_CAND %d: ME %u\n",
+				select, bat_priv->dht_hash);
+		}
+
+		max_orig_node = NULL;
+	}
+
+	return res;
+}
+
+/*
+ * Sends the skb payload passed as argument to the candidates selected for
+ * 'ip'. The skb is copied by means of pskb_copy() and is sent as unicast packet
+ * to each of the selected candidate. */
+static bool dht_send_data(struct bat_priv *bat_priv, struct sk_buff *skb,
+			  uint32_t ip)
+{
+	int i;
+	bool ret = false;
+	struct neigh_node *neigh_node = NULL;
+	struct sk_buff *tmp_skb;
+	struct dht_candidate *cand = dht_select_candidates(bat_priv, ip);
+
+	if (!cand)
+		goto out;
+
+	bat_dbg(DBG_ARP, bat_priv, "DHT_SEND for %pI4\n", &ip);
+
+	for (i = 0; i < DHT_CANDIDATES_NUM; i++) {
+		if (cand[i].type == DHT_CANDIDATE_ME ||
+		    cand[i].type == DHT_CANDIDATE_NULL)
+			continue;
+
+		neigh_node = orig_node_get_router(cand[i].orig_node);
+		if (!neigh_node)
+			goto free_orig;
+
+		tmp_skb = pskb_copy(skb, GFP_ATOMIC);
+		if (prepare_unicast_packet(tmp_skb, cand[i].orig_node))
+			send_skb_packet(tmp_skb, neigh_node->if_incoming,
+					neigh_node->addr);
+		else
+			kfree_skb(tmp_skb);
+		/* set ret to true only if we send at least one request */
+		ret = true;
+		neigh_node_free_ref(neigh_node);
+free_orig:
+		orig_node_free_ref(cand[i].orig_node);
+	}
+
+out:
+	kfree(cand);
+	return ret;
+}
diff --git a/distributed-arp-table.h b/distributed-arp-table.h
new file mode 100644
index 0000000..cca5c6a
--- /dev/null
+++ b/distributed-arp-table.h
@@ -0,0 +1,55 @@
+/*
+ * Copyright (C) 2011 B.A.T.M.A.N. contributors:
+ *
+ * Antonio Quartulli
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of version 2 of the GNU General Public
+ * License as published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+ * 02110-1301, USA
+ *
+ */
+
+#ifndef _NET_BATMAN_ADV_ARP_H_
+#define _NET_BATMAN_ADV_ARP_H_
+
+/*
+ * dat_addr_t is the type used for all DHT indexes. If it is changed,
+ * DAT_ADDR_MAX is changed as well.
+ *
+ * *Please be careful: dat_addr_t must be UNSIGNED*
+ */
+#define dat_addr_t uint16_t
+#define DAT_ADDR_MAX biggest_unsigned_int(dat_addr_t)
+
+/* hash function to choose an entry in a hash table of given size */
+/* hash algorithm from http://en.wikipedia.org/wiki/Hash_table */
+static inline uint32_t hash_ipv4(const void *data, uint32_t size)
+{
+	const unsigned char *key = data;
+	uint32_t hash = 0;
+	size_t i;
+
+	for (i = 0; i < 4; i++) {
+		hash += key[i];
+		hash += (hash << 10);
+		hash ^= (hash >> 6);
+	}
+
+	hash += (hash << 3);
+	hash ^= (hash >> 11);
+	hash += (hash << 15);
+
+	return hash % size;
+}
+
+#endif /* _NET_BATMAN_ADV_ARP_H_ */
diff --git a/hard-interface.c b/hard-interface.c
index d3e0e32..4a6948c 100644
--- a/hard-interface.c
+++ b/hard-interface.c
@@ -20,6 +20,7 @@
  */
 
 #include "main.h"
+#include "distributed-arp-table.h"
 #include "hard-interface.h"
 #include "soft-interface.h"
 #include "send.h"
@@ -117,6 +118,10 @@ static void primary_if_update_addr(struct bat_priv *bat_priv)
 	if (!primary_if)
 		goto out;
 
+	bat_priv->dht_hash = (dat_addr_t)
+				choose_orig(primary_if->net_dev->dev_addr,
+					    DAT_ADDR_MAX);
+
 	vis_packet = (struct vis_packet *)
 				bat_priv->my_vis_info->skb_packet->data;
 	memcpy(vis_packet->vis_orig, primary_if->net_dev->dev_addr, ETH_ALEN);
diff --git a/main.h b/main.h
index 5561bf7..e129b01 100644
--- a/main.h
+++ b/main.h
@@ -64,6 +64,9 @@
 
 #define NULL_IFINDEX 0 /* dummy ifindex used to avoid iface checks */
 
+/* numbers of originator to contact for any STORE/GET DHT operation */
+#define DHT_CANDIDATES_NUM 3
+
 #define NUM_WORDS (TQ_LOCAL_WINDOW_SIZE / WORD_BIT_SIZE)
 
 #define LOG_BUF_LEN 8192	  /* has to be a power of 2 */
@@ -106,6 +109,10 @@ enum uev_type {
 
 #define GW_THRESHOLD	50
 
+#define DHT_CANDIDATE_NULL 0
+#define DHT_CANDIDATE_ME   1
+#define DHT_CANDIDATE_ORIG 2
+
 /*
  * Debug Messages
  */
diff --git a/originator.c b/originator.c
index 847ff7e..14fb6d8 100644
--- a/originator.c
+++ b/originator.c
@@ -20,6 +20,7 @@
  */
 
 #include "main.h"
+#include "distributed-arp-table.h"
 #include "originator.h"
 #include "hash.h"
 #include "translation-table.h"
@@ -223,6 +224,7 @@ struct orig_node *get_orig_node(struct bat_priv *bat_priv, const uint8_t *addr)
 	orig_node->tt_poss_change = false;
 	orig_node->bat_priv = bat_priv;
 	memcpy(orig_node->orig, addr, ETH_ALEN);
+	orig_node->dht_hash = (dat_addr_t)choose_orig(addr, DAT_ADDR_MAX);
 	orig_node->router = NULL;
 	orig_node->tt_crc = 0;
 	atomic_set(&orig_node->last_ttvn, 0);
diff --git a/soft-interface.c b/soft-interface.c
index bd8c7cf..962ee8d 100644
--- a/soft-interface.c
+++ b/soft-interface.c
@@ -855,6 +855,8 @@ struct net_device *softif_create(const char *name)
 	bat_priv->primary_if = NULL;
 	bat_priv->num_ifaces = 0;
 
+	bat_priv->dht_hash = 0;
+
 	ret = sysfs_add_meshif(soft_iface);
 	if (ret < 0)
 		goto unreg_soft_iface;
diff --git a/types.h b/types.h
index 35085f4..afd166b 100644
--- a/types.h
+++ b/types.h
@@ -24,6 +24,7 @@
 #ifndef _NET_BATMAN_ADV_TYPES_H_
 #define _NET_BATMAN_ADV_TYPES_H_
 
+#include "distributed-arp-table.h"
 #include "packet.h"
 #include "bitarray.h"
 
@@ -67,6 +68,7 @@ struct hard_iface {
 struct orig_node {
 	uint8_t orig[ETH_ALEN];
 	uint8_t primary_addr[ETH_ALEN];
+	dat_addr_t dht_hash;
 	struct neigh_node __rcu *router; /* rcu protected pointer */
 	unsigned long *bcast_own;
 	uint8_t *bcast_own_sum;
@@ -205,6 +207,7 @@ struct bat_priv {
 	struct gw_node __rcu *curr_gw;  /* rcu protected pointer */
 	atomic_t gw_reselect;
 	struct hard_iface __rcu *primary_if;  /* rcu protected pointer */
+	dat_addr_t dht_hash;
 	struct vis_info *my_vis_info;
 };
 
@@ -344,4 +347,9 @@ struct softif_neigh {
 	struct rcu_head rcu;
 };
 
+struct dht_candidate {
+	int type;
+	struct orig_node *orig_node;
+};
+
 #endif /* _NET_BATMAN_ADV_TYPES_H_ */
-- 
1.7.3.4

[B.A.T.M.A.N.] [PATCHv4 4/7] batman-adv: Distributed ARP Table - add ARP parsing functions

[Antonio Quartulli]

ARP messages are now parsed to make it possible to trigger special actions
depending on their types (snooping).

Signed-off-by: Antonio Quartulli <ordex@autistici.org>
---
 distributed-arp-table.c |   59 +++++++++++++++++++++++++++++++++++++++++++++++
 distributed-arp-table.h |   12 +++++++++
 2 files changed, 71 insertions(+), 0 deletions(-)

diff --git a/distributed-arp-table.c b/distributed-arp-table.c
index 4c4e064..6cb60b0 100644
--- a/distributed-arp-table.c
+++ b/distributed-arp-table.c
@@ -30,6 +30,22 @@
 #include "types.h"
 #include "unicast.h"
 
+static inline void bat_dbg_arp(struct bat_priv *bat_priv,
+			       struct sk_buff *skb, uint16_t type) {
+	char buf[30];
+	const char *type_str[] = { "REQUEST", "REPLY", "RREQUEST", "RREPLY",
+				      "InREQUEST", "InREPLY", "NAK" };
+
+	if (type >= 1 && type <= ARRAY_SIZE(type_str))
+		scnprintf(buf, sizeof(buf), "%s", type_str[type - 1]);
+	else
+		scnprintf(buf, sizeof(buf), "UNKNOWN (%hu)", type);
+
+	bat_dbg(DBG_ARP, bat_priv, "ARP message of type %s recognised "
+		"[%pM-%pI4 %pM-%pI4]\n", buf, ARP_HW_SRC(skb), &ARP_IP_SRC(skb),
+		ARP_HW_DST(skb), &ARP_IP_DST(skb));
+}
+
 /* Given a key, selects the candidates which the DHT message has to be sent to.
  * An originator O is selected if and only if its DHT_ID value is one of three
  * closest values (but not greater) then the hash value of the key.
@@ -180,3 +196,46 @@ out:
 	kfree(cand);
 	return ret;
 }
+
+/* Returns arphdr->ar_op if the skb contains a valid ARP packet, otherwise
+ * returns 0 */
+static uint16_t arp_get_type(struct bat_priv *bat_priv, struct sk_buff *skb)
+{
+	struct arphdr *arphdr;
+	struct ethhdr *ethhdr;
+	uint16_t type = 0;
+
+	if (unlikely(!pskb_may_pull(skb, ETH_HLEN)))
+		goto out;
+
+	ethhdr = (struct ethhdr *)skb_mac_header(skb);
+
+	if (ethhdr->h_proto != htons(ETH_P_ARP))
+		goto out;
+
+	if (unlikely(!pskb_may_pull(skb, ETH_HLEN + arp_hdr_len(skb->dev))))
+		goto out;
+
+	arphdr = (struct arphdr *)(skb->data + sizeof(struct ethhdr));
+
+	/* Check whether the ARP packet carries a valid
+	 * IP information */
+	if (arphdr->ar_hrd != htons(ARPHRD_ETHER))
+		goto out;
+
+	if (arphdr->ar_pro != htons(ETH_P_IP))
+		goto out;
+
+	if (arphdr->ar_hln != ETH_ALEN)
+		goto out;
+
+	if (arphdr->ar_pln != 4)
+		goto out;
+
+	type = ntohs(arphdr->ar_op);
+
+	bat_dbg_arp(bat_priv, skb, type);
+
+out:
+	return type;
+}
diff --git a/distributed-arp-table.h b/distributed-arp-table.h
index cca5c6a..3e0f5c6 100644
--- a/distributed-arp-table.h
+++ b/distributed-arp-table.h
@@ -22,6 +22,12 @@
 #ifndef _NET_BATMAN_ADV_ARP_H_
 #define _NET_BATMAN_ADV_ARP_H_
 
+#include "main.h"
+
+#include <linux/if_arp.h>
+
+struct bat_priv;
+
 /*
  * dat_addr_t is the type used for all DHT indexes. If it is changed,
  * DAT_ADDR_MAX is changed as well.
@@ -31,6 +37,12 @@
 #define dat_addr_t uint16_t
 #define DAT_ADDR_MAX biggest_unsigned_int(dat_addr_t)
 
+#define ARP_HW_SRC(skb) ((uint8_t *)(skb->data) + sizeof(struct ethhdr) + \
+			sizeof(struct arphdr))
+#define ARP_IP_SRC(skb) (*(uint32_t *)(ARP_HW_SRC(skb) + ETH_ALEN))
+#define ARP_HW_DST(skb) (ARP_HW_SRC(skb) + ETH_ALEN + 4)
+#define ARP_IP_DST(skb) (*(uint32_t *)(ARP_HW_SRC(skb) + ETH_ALEN * 2 + 4))
+
 /* hash function to choose an entry in a hash table of given size */
 /* hash algorithm from http://en.wikipedia.org/wiki/Hash_table */
 static inline uint32_t hash_ipv4(const void *data, uint32_t size)
-- 
1.7.3.4

Re: [B.A.T.M.A.N.] [PATCHv4 4/7] batman-adv: Distributed ARP Table - add ARP parsing functions

[Andrew Lunn]

> +/* Returns arphdr->ar_op if the skb contains a valid ARP packet, otherwise
> + * returns 0 */
> +static uint16_t arp_get_type(struct bat_priv *bat_priv, struct sk_buff *skb)
> +{
> +	struct arphdr *arphdr;
> +	struct ethhdr *ethhdr;
> +	uint16_t type = 0;
> +
> +	if (unlikely(!pskb_may_pull(skb, ETH_HLEN)))
> +		goto out;
> +
> +	ethhdr = (struct ethhdr *)skb_mac_header(skb);
> +
> +	if (ethhdr->h_proto != htons(ETH_P_ARP))
> +		goto out;

Do we have any idea how many people run vlans over B.A.T.M.A.N? It
would not be too hard to skip over the VLAN tag if there is one to see
if it is an ARP message inside.

   Andrew

Re: [B.A.T.M.A.N.] [PATCHv4 4/7] batman-adv: Distributed ARP Table - add ARP parsing functions

[Antonio Quartulli]

On Fri, Nov 25, 2011 at 09:31:25AM +0100, Andrew Lunn wrote:
> Do we have any idea how many people run vlans over B.A.T.M.A.N? It
> would not be too hard to skip over the VLAN tag if there is one to see
> if it is an ARP message inside.

Actually I don't have any idea about that, but I think there is plenty
of those out there.

However: Yes you are right. I discussed this with Simon several times, but since
I have never dealt with the VLAN before, I postponed this "feature" (ok, it's
a very small one) to a later patch..

Cheers,

-- 
Antonio Quartulli

..each of us alone is worth nothing..
Ernesto "Che" Guevara ☭

[B.A.T.M.A.N.] [PATCHv4 5/7] batman-adv: Distributed ARP Table - add snooping functions for ARP messages

[Antonio Quartulli]

In case of an ARP message going in or out the soft_iface, it is intercepted and
a special action is performed. In particular the DHT helper functions previously
implemented are used to store all the ARP entries belonging to the network in
order to provide a fast and unicast lookup instead of the classic broadcast flooding
mechanism.
Each node stores the entries it is responsible for (following the DHT rules) in
its soft_iface ARP table. This makes it possible to reuse the kernel data
structures and functions for ARP management.

Signed-off-by: Antonio Quartulli <ordex@autistici.org>
---
 distributed-arp-table.c |  226 +++++++++++++++++++++++++++++++++++++++++++++++
 distributed-arp-table.h |   10 ++
 main.h                  |    2 +
 send.c                  |    6 ++
 soft-interface.c        |   16 +++-
 5 files changed, 259 insertions(+), 1 deletions(-)

diff --git a/distributed-arp-table.c b/distributed-arp-table.c
index 6cb60b0..a1deb79 100644
--- a/distributed-arp-table.c
+++ b/distributed-arp-table.c
@@ -21,6 +21,8 @@
 
 #include <linux/if_ether.h>
 #include <linux/if_arp.h>
+/* needed to use arp_tbl */
+#include <net/arp.h>
 
 #include "main.h"
 #include "distributed-arp-table.h"
@@ -197,6 +199,31 @@ out:
 	return ret;
 }
 
+/* Update the neighbour entry corresponding to the IP passed as parameter with
+ * the hw address hw. If the neighbour entry doesn't exists, then it will be
+ * created */
+static void arp_neigh_update(struct bat_priv *bat_priv, uint32_t ip,
+			     uint8_t *hw)
+{
+	struct neighbour *n = NULL;
+	struct hard_iface *primary_if = primary_if_get_selected(bat_priv);
+	if (!primary_if)
+		goto out;
+
+	n = __neigh_lookup(&arp_tbl, &ip, primary_if->soft_iface, 1);
+	if (!n)
+		goto out;
+
+	bat_dbg(DBG_ARP, bat_priv, "Updating neighbour: %pI4 - %pM\n", &ip, hw);
+
+	neigh_update(n, hw, NUD_CONNECTED, NEIGH_UPDATE_F_OVERRIDE);
+out:
+	if (n && !IS_ERR(n))
+		neigh_release(n);
+	if (primary_if)
+		hardif_free_ref(primary_if);
+}
+
 /* Returns arphdr->ar_op if the skb contains a valid ARP packet, otherwise
  * returns 0 */
 static uint16_t arp_get_type(struct bat_priv *bat_priv, struct sk_buff *skb)
@@ -239,3 +266,202 @@ static uint16_t arp_get_type(struct bat_priv *bat_priv, struct sk_buff *skb)
 out:
 	return type;
 }
+
+/* return true if the message has been sent to the dht candidates, false
+ * otherwise. In case of true the message has to be enqueued to permit the
+ * fallback */
+bool arp_snoop_outgoing_request(struct bat_priv *bat_priv, struct sk_buff *skb)
+{
+	uint16_t type = 0;
+	uint32_t ip_dst, ip_src;
+	uint8_t *hw_src;
+	bool ret = false;
+	struct neighbour *n = NULL;
+	struct hard_iface *primary_if = NULL;
+	struct sk_buff *skb_new;
+
+	type = arp_get_type(bat_priv, skb);
+	/* If we get an ARP_REQUEST we have to send the unicast message to the
+	 * selected DHT candidates */
+	if (type != ARPOP_REQUEST)
+		goto out;
+
+	bat_dbg(DBG_ARP, bat_priv, "Snooped outgoing ARP request\n");
+
+	ip_src = ARP_IP_SRC(skb);
+	hw_src = ARP_HW_SRC(skb);
+	ip_dst = ARP_IP_DST(skb);
+
+	primary_if = primary_if_get_selected(bat_priv);
+	if (!primary_if)
+		goto out;
+
+	arp_neigh_update(bat_priv, ip_src, hw_src);
+
+	n = neigh_lookup(&arp_tbl, &ip_dst, primary_if->soft_iface);
+	/* check if it is a valid neigh entry */
+	if (n && (n->nud_state & NUD_CONNECTED)) {
+		skb_new = arp_create(ARPOP_REPLY, ETH_P_ARP, ip_src,
+				     primary_if->soft_iface, ip_dst, hw_src,
+				     n->ha, hw_src);
+		if (!skb_new)
+			goto out;
+
+		skb_reset_mac_header(skb_new);
+		skb_new->protocol = eth_type_trans(skb_new,
+						   primary_if->soft_iface);
+		bat_priv->stats.rx_packets++;
+		bat_priv->stats.rx_bytes += skb->len + sizeof(struct ethhdr);
+		primary_if->soft_iface->last_rx = jiffies;
+
+		netif_rx(skb_new);
+		bat_dbg(DBG_ARP, bat_priv, "ARP request replied locally\n");
+	} else
+		/* Send the request on the DHT */
+		ret = dht_send_data(bat_priv, skb, ip_dst);
+out:
+	if (n)
+		neigh_release(n);
+	if (primary_if)
+		hardif_free_ref(primary_if);
+	return ret;
+}
+
+/* This function is meant to be invoked for an ARP request which is coming into
+ * the bat0 interfaces from the mesh network. It will check for the needed data
+ * into the local table. If found, an ARP reply is sent immediately, otherwise
+ * the caller has to deliver the ARP request to the upper layer */
+bool arp_snoop_incoming_request(struct bat_priv *bat_priv, struct sk_buff *skb)
+{
+	uint16_t type;
+	uint32_t ip_src, ip_dst;
+	uint8_t *hw_src;
+	struct hard_iface *primary_if = NULL;
+	struct sk_buff *skb_new;
+	struct neighbour *n = NULL;
+	bool ret = false;
+
+	type = arp_get_type(bat_priv, skb);
+	if (type != ARPOP_REQUEST)
+		goto out;
+
+	hw_src = ARP_HW_SRC(skb);
+	ip_src = ARP_IP_SRC(skb);
+	ip_dst = ARP_IP_DST(skb);
+
+	bat_dbg(DBG_ARP, bat_priv, "Snooped incoming ARP request\n");
+
+	primary_if = primary_if_get_selected(bat_priv);
+	if (!primary_if)
+		goto out;
+
+	arp_neigh_update(bat_priv, ip_src, hw_src);
+
+	n = neigh_lookup(&arp_tbl, &ip_dst, primary_if->soft_iface);
+	/* check if it is a valid neigh entry */
+	if (!n || !(n->nud_state & NUD_CONNECTED))
+		goto out;
+
+	skb_new = arp_create(ARPOP_REPLY, ETH_P_ARP, ip_src,
+			     primary_if->soft_iface, ip_dst, hw_src, n->ha,
+			     hw_src);
+
+	if (!skb_new)
+		goto out;
+
+	unicast_send_skb(skb_new, bat_priv);
+
+	ret = true;
+out:
+	if (n)
+		neigh_release(n);
+	if (primary_if)
+		hardif_free_ref(primary_if);
+	if (ret)
+		kfree_skb(skb);
+	return ret;
+}
+
+/* This function is meant to be invoked on an ARP reply packet going into the
+ * soft interface. The related neighbour entry has to be updated and the DHT has
+ * to be populated as well */
+bool arp_snoop_outgoing_reply(struct bat_priv *bat_priv, struct sk_buff *skb)
+{
+	uint16_t type;
+	uint32_t ip_src, ip_dst;
+	uint8_t *hw_src, *hw_dst;
+	bool ret = false;
+
+	type = arp_get_type(bat_priv, skb);
+	if (type != ARPOP_REPLY)
+		goto out;
+
+	bat_dbg(DBG_ARP, bat_priv, "Snooped outgoing ARP reply\n");
+
+	hw_src = ARP_HW_SRC(skb);
+	ip_src = ARP_IP_SRC(skb);
+	hw_dst = ARP_HW_DST(skb);
+	ip_dst = ARP_IP_DST(skb);
+
+	arp_neigh_update(bat_priv, ip_src, hw_src);
+	arp_neigh_update(bat_priv, ip_dst, hw_dst);
+
+	/* Send the ARP reply to the candidates for both the IP addresses we
+	 * fetched from the ARP reply */
+	dht_send_data(bat_priv, skb, ip_src);
+	dht_send_data(bat_priv, skb, ip_dst);
+	ret = true;
+out:
+	return ret;
+}
+
+/* This function has to be invoked on an ARP reply coming into the soft
+ * interface from the mesh network. The local table has to be updated */
+bool arp_snoop_incoming_reply(struct bat_priv *bat_priv, struct sk_buff *skb)
+{
+	uint16_t type;
+	uint32_t ip_src, ip_dst;
+	uint8_t *hw_src, *hw_dst;
+	bool ret = false;
+
+	type = arp_get_type(bat_priv, skb);
+	if (type != ARPOP_REPLY)
+		goto out;
+
+	bat_dbg(DBG_ARP, bat_priv, "Snooped incoming ARP reply\n");
+
+	hw_src = ARP_HW_SRC(skb);
+	ip_src = ARP_IP_SRC(skb);
+	hw_dst = ARP_HW_DST(skb);
+	ip_dst = ARP_IP_DST(skb);
+
+	/* Update our internal cache with both the IP addresses we fetched from
+	 * the ARP reply */
+	arp_neigh_update(bat_priv, ip_src, hw_src);
+	arp_neigh_update(bat_priv, ip_dst, hw_dst);
+
+	ret = true;
+out:
+	return ret;
+}
+
+bool arp_drop_broadcast_packet(struct bat_priv *bat_priv,
+			       struct forw_packet *forw_packet)
+{
+	struct neighbour *n;
+
+	/* If this packet is an ARP_REQUEST and we already have the information
+	 * that it is going to ask, we can drop the packet */
+	if (!forw_packet->num_packets &&
+			(arp_get_type(bat_priv, forw_packet->skb) ==
+							ARPOP_REQUEST)) {
+		n = neigh_lookup(&arp_tbl, &ARP_IP_DST(forw_packet->skb),
+				 forw_packet->if_incoming->soft_iface);
+		/* check if we already know this neigh */
+		if (n && (n->nud_state & NUD_CONNECTED))
+			return true;
+
+		bat_dbg(DBG_ARP, bat_priv, "ARP request: fallback\n");
+	}
+	return false;
+}
diff --git a/distributed-arp-table.h b/distributed-arp-table.h
index 3e0f5c6..3747aad 100644
--- a/distributed-arp-table.h
+++ b/distributed-arp-table.h
@@ -27,6 +27,7 @@
 #include <linux/if_arp.h>
 
 struct bat_priv;
+struct forw_packet;
 
 /*
  * dat_addr_t is the type used for all DHT indexes. If it is changed,
@@ -43,6 +44,15 @@ struct bat_priv;
 #define ARP_HW_DST(skb) (ARP_HW_SRC(skb) + ETH_ALEN + 4)
 #define ARP_IP_DST(skb) (*(uint32_t *)(ARP_HW_SRC(skb) + ETH_ALEN * 2 + 4))
 
+bool arp_snoop_outgoing_request(struct bat_priv *bat_priv,
+				struct sk_buff *skb);
+bool arp_snoop_incoming_request(struct bat_priv *bat_priv,
+				struct sk_buff *skb);
+bool arp_snoop_outgoing_reply(struct bat_priv *bat_priv, struct sk_buff *skb);
+bool arp_snoop_incoming_reply(struct bat_priv *bat_priv, struct sk_buff *skb);
+bool arp_drop_broadcast_packet(struct bat_priv *bat_priv,
+			       struct forw_packet *forw_packet);
+
 /* hash function to choose an entry in a hash table of given size */
 /* hash algorithm from http://en.wikipedia.org/wiki/Hash_table */
 static inline uint32_t hash_ipv4(const void *data, uint32_t size)
diff --git a/main.h b/main.h
index e129b01..a915db6 100644
--- a/main.h
+++ b/main.h
@@ -64,6 +64,8 @@
 
 #define NULL_IFINDEX 0 /* dummy ifindex used to avoid iface checks */
 
+/* msecs after which an ARP_REQUEST is sent in broadcast as fallback */
+#define ARP_REQ_DELAY 250
 /* numbers of originator to contact for any STORE/GET DHT operation */
 #define DHT_CANDIDATES_NUM 3
 
diff --git a/send.c b/send.c
index b00a0f5..d625998 100644
--- a/send.c
+++ b/send.c
@@ -20,6 +20,7 @@
  */
 
 #include "main.h"
+#include "distributed-arp-table.h"
 #include "send.h"
 #include "routing.h"
 #include "translation-table.h"
@@ -30,6 +31,8 @@
 #include "originator.h"
 #include "bat_ogm.h"
 
+#include <net/arp.h>
+
 static void send_outstanding_bcast_packet(struct work_struct *work);
 
 /* send out an already prepared packet to the given address via the
@@ -275,6 +278,9 @@ static void send_outstanding_bcast_packet(struct work_struct *work)
 	if (atomic_read(&bat_priv->mesh_state) == MESH_DEACTIVATING)
 		goto out;
 
+	if (arp_drop_broadcast_packet(bat_priv, forw_packet))
+		goto out;
+
 	/* rebroadcast packet */
 	rcu_read_lock();
 	list_for_each_entry_rcu(hard_iface, &hardif_list, list) {
diff --git a/soft-interface.c b/soft-interface.c
index 962ee8d..21991e1 100644
--- a/soft-interface.c
+++ b/soft-interface.c
@@ -22,6 +22,7 @@
 #include "main.h"
 #include "soft-interface.h"
 #include "hard-interface.h"
+#include "distributed-arp-table.h"
 #include "routing.h"
 #include "send.h"
 #include "bat_debugfs.h"
@@ -567,6 +568,7 @@ static int interface_tx(struct sk_buff *skb, struct net_device *soft_iface)
 	int data_len = skb->len, ret;
 	short vid = -1;
 	bool do_bcast = false;
+	unsigned long brd_delay = 1;
 
 	if (atomic_read(&bat_priv->mesh_state) != MESH_ACTIVE)
 		goto dropped;
@@ -587,6 +589,8 @@ static int interface_tx(struct sk_buff *skb, struct net_device *soft_iface)
 		goto end;
 	}
 
+	skb_reset_mac_header(skb);
+
 	/**
 	 * if we have a another chosen mesh exit node in range
 	 * it will transport the packets to the mesh
@@ -628,6 +632,9 @@ static int interface_tx(struct sk_buff *skb, struct net_device *soft_iface)
 		if (!primary_if)
 			goto dropped;
 
+		if (arp_snoop_outgoing_request(bat_priv, skb))
+			brd_delay = msecs_to_jiffies(ARP_REQ_DELAY);
+
 		if (my_skb_head_push(skb, sizeof(*bcast_packet)) < 0)
 			goto dropped;
 
@@ -647,7 +654,7 @@ static int interface_tx(struct sk_buff *skb, struct net_device *soft_iface)
 		bcast_packet->seqno =
 			htonl(atomic_inc_return(&bat_priv->bcast_seqno));
 
-		add_bcast_packet_to_list(bat_priv, skb, 1);
+		add_bcast_packet_to_list(bat_priv, skb, brd_delay);
 
 		/* a copy is stored in the bcast list, therefore removing
 		 * the original skb. */
@@ -661,6 +668,8 @@ static int interface_tx(struct sk_buff *skb, struct net_device *soft_iface)
 				goto dropped;
 		}
 
+		arp_snoop_outgoing_reply(bat_priv, skb);
+
 		ret = unicast_send_skb(skb, bat_priv);
 		if (ret != 0)
 			goto dropped_freed;
@@ -716,6 +725,11 @@ void interface_rx(struct net_device *soft_iface,
 		goto dropped;
 	}
 
+	if (arp_snoop_incoming_request(bat_priv, skb))
+		goto out;
+
+	arp_snoop_incoming_reply(bat_priv, skb);
+
 	/**
 	 * if we have a another chosen mesh exit node in range
 	 * it will transport the packets to the non-mesh network
-- 
1.7.3.4

Re: [B.A.T.M.A.N.] [PATCHv4 5/7] batman-adv: Distributed ARP Table - add snooping functions for ARP messages

[Marek Lindner]

On Friday, November 25, 2011 06:21:17 Antonio Quartulli wrote:
> @@ -30,6 +31,8 @@
>  #include "originator.h"
>  #include "bat_ogm.h"
>  
> +#include <net/arp.h>
> +
>  static void send_outstanding_bcast_packet(struct work_struct *work);

What is this include doing here ? If I am not mistaken you removed it from 
your patchset already. Is this really the latest version ? 

Regards,
Marek

Re: [B.A.T.M.A.N.] [PATCHv4 5/7] batman-adv: Distributed ARP Table - add snooping functions for ARP messages

[Andrew Lunn]

Hi Antonio

General question. In the Linux ARP decode code is:

/*
 *      Check for bad requests for 127.x.x.x and requests for multicast
 *      addresses.  If this is one such, delete it.
 */
        if (ipv4_is_loopback(tip) || ipv4_is_multicast(tip))
                goto out;

I don't see the same filtering here. What would happen if you did
receiver and cached such a bad request?

In a similar direction, how does duplicate address detection work?
i.e. i ARP my own address to see if somebody else is using it? 

Or do i just need to RTFM your GSOC documentation :-)

   Andrew

Re: [B.A.T.M.A.N.] [PATCHv4 5/7] batman-adv: Distributed ARP Table - add snooping functions for ARP messages

[Antonio Quartulli]

On Fri, Nov 25, 2011 at 09:45:56AM +0100, Andrew Lunn wrote:
> Hi Antonio
> 
> General question. In the Linux ARP decode code is:
> 
> /*
>  *      Check for bad requests for 127.x.x.x and requests for multicast
>  *      addresses.  If this is one such, delete it.
>  */
>         if (ipv4_is_loopback(tip) || ipv4_is_multicast(tip))
>                 goto out;
> 
> I don't see the same filtering here. What would happen if you did
> receiver and cached such a bad request?

atually there isnot such control over the arp message content. In case
of, let's say, a malicious ARP message of this type, it is stored like
any other one.

> 
> In a similar direction, how does duplicate address detection work?
> i.e. i ARP my own address to see if somebody else is using it? 
> 
> Or do i just need to RTFM your GSOC documentation :-)
> 

Don't think so. Actually I/we didn't think too much about this kind of
cases. Well, a duplicate entry is simply overwritten: I mean, if we
already have the entry [IPa,MACa] in the table, any other ARP reply containing
[IPa,MACb] will update the older one and MACa will be lost.

Do you expect a different behaviour? Can I do it better?

Cheers,

-- 
Antonio Quartulli

..each of us alone is worth nothing..
Ernesto "Che" Guevara ☭

Re: [B.A.T.M.A.N.] [PATCHv4 5/7] batman-adv: Distributed ARP Table - add snooping functions for ARP messages

[Andrew Lunn]

On Fri, Nov 25, 2011 at 12:17:08PM +0100, Antonio Quartulli wrote:
> On Fri, Nov 25, 2011 at 09:45:56AM +0100, Andrew Lunn wrote:
> > Hi Antonio
> > 
> > General question. In the Linux ARP decode code is:
> > 
> > /*
> >  *      Check for bad requests for 127.x.x.x and requests for multicast
> >  *      addresses.  If this is one such, delete it.
> >  */
> >         if (ipv4_is_loopback(tip) || ipv4_is_multicast(tip))
> >                 goto out;
> > 
> > I don't see the same filtering here. What would happen if you did
> > receiver and cached such a bad request?
> 
> atually there isnot such control over the arp message content. In case
> of, let's say, a malicious ARP message of this type, it is stored like
> any other one.

It might make sense to drop such messages, since they are
invalid. However, nothing obvious comes to mind which would go wrong
if you did cache them, other than somebody could DOS you by sending
lots of ARP entries for multicast addresses.

> > In a similar direction, how does duplicate address detection work?
> > i.e. i ARP my own address to see if somebody else is using it? 
 
> Don't think so. Actually I/we didn't think too much about this kind of
> cases. Well, a duplicate entry is simply overwritten: I mean, if we
> already have the entry [IPa,MACa] in the table, any other ARP reply containing
> [IPa,MACb] will update the older one and MACa will be lost.

The basic idea with duplicate address detection is to send out an ARP
request for your own address. If you get an answer, you know somebody
is using the address. I think Windoz then shuts the interface down, or
at least gives a warning. So in the case of duplicate address
detection, you want to fallback to broadcasting the ARP request and
see if anybody answers. You can detect if a node is performing
aduplicate detection, if the ARP requests source MAC address is the
same as the answer in the cache. If so, fall back to broadcasting
rather than answering from the cache.

Looking at RFC 3927 might also be interesting, since it uses ARP
messages in a different way.

Also, i know some dhcp servers try to ping an IP address before giving
it out, just to be sure it is not in use. Answering the ARP request
from what could be an out of date cache entry doesn't i think causes a
problem, so long as the ping that follows it does not get
answered. But maybe some DHCP servers just perform an ARP request?

Some things to think about...

	  Andrew	  

Re: [B.A.T.M.A.N.] [PATCHv4 5/7] batman-adv: Distributed ARP Table - add snooping functions for ARP messages

[Antonio Quartulli]

On Fri, Nov 25, 2011 at 10:09:11 +0100, Andrew Lunn wrote:
> It might make sense to drop such messages, since they are
> invalid. However, nothing obvious comes to mind which would go wrong
> if you did cache them, other than somebody could DOS you by sending
> lots of ARP entries for multicast addresses.

Yes, I was thinking the same. A DOS is the major threat we could face without
this validity check. However, since we use the kernel function to add such
entries into the table it might be that the kernel already does this checks for
us. I'll look towards it

> 
> > > In a similar direction, how does duplicate address detection work?
> > > i.e. i ARP my own address to see if somebody else is using it? 
>  
> > Don't think so. Actually I/we didn't think too much about this kind of
> > cases. Well, a duplicate entry is simply overwritten: I mean, if we
> > already have the entry [IPa,MACa] in the table, any other ARP reply containing
> > [IPa,MACb] will update the older one and MACa will be lost.
> 
> The basic idea with duplicate address detection is to send out an ARP
> request for your own address. If you get an answer, you know somebody
> is using the address. I think Windoz then shuts the interface down, or
> at least gives a warning. So in the case of duplicate address
> detection, you want to fallback to broadcasting the ARP request and
> see if anybody answers. You can detect if a node is performing
> aduplicate detection, if the ARP requests source MAC address is the
> same as the answer in the cache. If so, fall back to broadcasting
> rather than answering from the cache.
> 
> Looking at RFC 3927 might also be interesting, since it uses ARP
> messages in a different way.
> 
> Also, i know some dhcp servers try to ping an IP address before giving
> it out, just to be sure it is not in use. Answering the ARP request
> from what could be an out of date cache entry doesn't i think causes a
> problem, so long as the ping that follows it does not get
> answered. But maybe some DHCP servers just perform an ARP request?
> 

Mh...but I think this behaviour is somehow left untouched. The mechanisms you
are describing are higher-level matters. Since we only limit to fill tables and
get answer, all the other mechanisms/procedures which use the tables should
still continue to work as they are. If a windows client will issue an ARP req to
see is someone else is using the same IP, DAT will simply answer as a normal
table would do. Therefore I think that this kind of worries are not matter of
DAT.

I hope I clearly explained my thought.

Then we could always add more feature in order to "facilitate" such mechanisms,
but up to now I think that DAT simply provides the same behaviour a normal table
would do.

Thank you for your comments!
Cheers,

-- 
Antonio Quartulli

..each of us alone is worth nothing..
Ernesto "Che" Guevara

[B.A.T.M.A.N.] [PATCHv4 6/7] batman-adv: Distributed ARP Table - increase default soft_iface ARP table timeout

[Antonio Quartulli]

The default timeout value for ARP entries belonging to any soft_iface
ARP table has been incremented by a factor 4. This is necessary because the DHT
will store several network entries in the soft_iface ARP table.

Signed-off-by: Antonio Quartulli <ordex@autistici.org>
---
 main.h           |    4 ++++
 soft-interface.c |   17 +++++++++++++++++
 2 files changed, 21 insertions(+), 0 deletions(-)

diff --git a/main.h b/main.h
index a915db6..8672b04 100644
--- a/main.h
+++ b/main.h
@@ -69,6 +69,10 @@
 /* numbers of originator to contact for any STORE/GET DHT operation */
 #define DHT_CANDIDATES_NUM 3
 
+/* Factor which default ARP timeout values of the soft_iface table are
+ * multiplied by */
+#define ARP_TIMEOUT_FACTOR 4
+
 #define NUM_WORDS (TQ_LOCAL_WINDOW_SIZE / WORD_BIT_SIZE)
 
 #define LOG_BUF_LEN 8192	  /* has to be a power of 2 */
diff --git a/soft-interface.c b/soft-interface.c
index 21991e1..1194cf7 100644
--- a/soft-interface.c
+++ b/soft-interface.c
@@ -36,6 +36,7 @@
 #include <linux/ethtool.h>
 #include <linux/etherdevice.h>
 #include <linux/if_vlan.h>
+#include <linux/inetdevice.h>
 #include "unicast.h"
 
 
@@ -825,6 +826,7 @@ static void interface_setup(struct net_device *dev)
 struct net_device *softif_create(const char *name)
 {
 	struct net_device *soft_iface;
+	struct in_device *in_dev;
 	struct bat_priv *bat_priv;
 	int ret;
 
@@ -840,6 +842,21 @@ struct net_device *softif_create(const char *name)
 		goto free_soft_iface;
 	}
 
+	in_dev = in_dev_get(soft_iface);
+	if (!in_dev) {
+		pr_err("Unable to set ARP parameters for the batman interface "
+		       "'%s'\n", name);
+		goto free_soft_iface;
+	}
+
+	/* Introduce a delay in the ARP state-machine transactions. Entries
+	 * will be kept in the ARP table for the default time multiplied by 4 */
+	in_dev->arp_parms->base_reachable_time *= ARP_TIMEOUT_FACTOR;
+	in_dev->arp_parms->gc_staletime *= ARP_TIMEOUT_FACTOR;
+	in_dev->arp_parms->reachable_time *= ARP_TIMEOUT_FACTOR;
+
+	in_dev_put(in_dev);
+
 	bat_priv = netdev_priv(soft_iface);
 
 	atomic_set(&bat_priv->aggregated_ogms, 1);
-- 
1.7.3.4

[B.A.T.M.A.N.] [PATCHv4 7/7] batman-adv: add Distributed ARP Table compile option

[Antonio Quartulli]

This patch makes it possible possible to decide whether to compile DAT or not.

Signed-off-by: Antonio Quartulli <ordex@autistici.org>
---
 Makefile.kbuild         |    7 ++++++-
 README                  |    4 ++++
 distributed-arp-table.c |   28 ++++++++++++++++++++++++++++
 distributed-arp-table.h |   34 +++++++++++++++++++++++++---------
 hard-interface.c        |    2 ++
 originator.c            |    2 ++
 send.c                  |    2 --
 soft-interface.c        |   19 +++----------------
 types.h                 |    4 ++++
 9 files changed, 74 insertions(+), 28 deletions(-)

diff --git a/Makefile.kbuild b/Makefile.kbuild
index e8861cb..7e3b9e5 100644
--- a/Makefile.kbuild
+++ b/Makefile.kbuild
@@ -18,6 +18,9 @@
 # 02110-1301, USA
 #
 
+# uncomment the following line to enable the related feature
+# Distributed ARP Table:
+# CONFIG_BATMAN_ADV_DAT=y
 
 
 # openwrt integration
@@ -27,6 +30,8 @@ endif
 
 # ccflags-y += -DCONFIG_BATMAN_ADV_DEBUG
 
+ccflags-$(CONFIG_BATMAN_ADV_DAT) += -DCONFIG_BATMAN_ADV_DAT
+
 ifneq ($(REVISION),)
 ccflags-y += -DSOURCE_VERSION=\"$(REVISION)\"
 endif
@@ -36,7 +41,7 @@ batman-adv-y += bat_debugfs.o
 batman-adv-y += bat_iv_ogm.o
 batman-adv-y += bat_sysfs.o
 batman-adv-y += bitarray.o
-batman-adv-y += distributed-arp-table.o
+batman-adv-$(CONFIG_BATMAN_ADV_DAT) += distributed-arp-table.o
 batman-adv-y += gateway_client.o
 batman-adv-y += gateway_common.o
 batman-adv-y += hard-interface.o
diff --git a/README b/README
index 856ca7e..06f1469 100644
--- a/README
+++ b/README
@@ -26,6 +26,10 @@ it.  If you work on a backport, feel free to contact us.  :-)
 COMPILE
 -------
 
+Before compiling you want to have a look at the Makefile.kbuild
+file to enable/disable wanted features. Actually there are:
+- CONFIG_BATMAN_ADV_DAT enables the Distributed ARP Table
+
 To compile against your currently installed  kernel, just type:
 
 # make
diff --git a/distributed-arp-table.c b/distributed-arp-table.c
index a1deb79..8876ec5 100644
--- a/distributed-arp-table.c
+++ b/distributed-arp-table.c
@@ -23,15 +23,19 @@
 #include <linux/if_arp.h>
 /* needed to use arp_tbl */
 #include <net/arp.h>
+#include <linux/inetdevice.h>
 
 #include "main.h"
 #include "distributed-arp-table.h"
 #include "hard-interface.h"
 #include "originator.h"
 #include "send.h"
+#include "soft-interface.h"
 #include "types.h"
 #include "unicast.h"
 
+#ifdef CONFIG_BATMAN_ADV_DEBUG
+
 static inline void bat_dbg_arp(struct bat_priv *bat_priv,
 			       struct sk_buff *skb, uint16_t type) {
 	char buf[30];
@@ -48,6 +52,12 @@ static inline void bat_dbg_arp(struct bat_priv *bat_priv,
 		ARP_HW_DST(skb), &ARP_IP_DST(skb));
 }
 
+#else
+
+#define bat_dbg_arp(...)
+
+#endif /* CONFIG_BATMAN_ADV_DEBUG */
+
 /* Given a key, selects the candidates which the DHT message has to be sent to.
  * An originator O is selected if and only if its DHT_ID value is one of three
  * closest values (but not greater) then the hash value of the key.
@@ -465,3 +475,21 @@ bool arp_drop_broadcast_packet(struct bat_priv *bat_priv,
 	}
 	return false;
 }
+
+void arp_change_timeout(struct net_device *soft_iface, const char *name)
+{
+	struct in_device *in_dev = in_dev_get(soft_iface);
+	if (!in_dev) {
+		pr_err("Unable to set ARP parameters for the batman interface "
+		       "'%s'\n", name);
+		return;
+	}
+
+	/* Introduce a delay in the ARP state-machine transactions. Entries
+	 * will be kept in the ARP table for the default time multiplied by 4 */
+	in_dev->arp_parms->base_reachable_time *= ARP_TIMEOUT_FACTOR;
+	in_dev->arp_parms->gc_staletime *= ARP_TIMEOUT_FACTOR;
+	in_dev->arp_parms->reachable_time *= ARP_TIMEOUT_FACTOR;
+
+	in_dev_put(in_dev);
+}
diff --git a/distributed-arp-table.h b/distributed-arp-table.h
index 3747aad..71eaeaf 100644
--- a/distributed-arp-table.h
+++ b/distributed-arp-table.h
@@ -22,36 +22,52 @@
 #ifndef _NET_BATMAN_ADV_ARP_H_
 #define _NET_BATMAN_ADV_ARP_H_
 
+#ifdef CONFIG_BATMAN_ADV_DAT
+
 #include "main.h"
 
 #include <linux/if_arp.h>
+#include <linux/netdevice.h>
 
 struct bat_priv;
 struct forw_packet;
 
 /*
- * dat_addr_t is the type used for all DHT indexes. If it is changed,
- * DAT_ADDR_MAX is changed as well.
- *
- * *Please be careful: dat_addr_t must be UNSIGNED*
- */
+* dat_addr_t is the type used for all DHT indexes. If it is changed,
+* DAT_ADDR_MAX is changed as well.
+*
+* *Please be careful: dat_addr_t must be UNSIGNED*
+*/
 #define dat_addr_t uint16_t
 #define DAT_ADDR_MAX biggest_unsigned_int(dat_addr_t)
 
 #define ARP_HW_SRC(skb) ((uint8_t *)(skb->data) + sizeof(struct ethhdr) + \
-			sizeof(struct arphdr))
+		sizeof(struct arphdr))
 #define ARP_IP_SRC(skb) (*(uint32_t *)(ARP_HW_SRC(skb) + ETH_ALEN))
 #define ARP_HW_DST(skb) (ARP_HW_SRC(skb) + ETH_ALEN + 4)
 #define ARP_IP_DST(skb) (*(uint32_t *)(ARP_HW_SRC(skb) + ETH_ALEN * 2 + 4))
 
+
 bool arp_snoop_outgoing_request(struct bat_priv *bat_priv,
-				struct sk_buff *skb);
+			struct sk_buff *skb);
 bool arp_snoop_incoming_request(struct bat_priv *bat_priv,
-				struct sk_buff *skb);
+			struct sk_buff *skb);
 bool arp_snoop_outgoing_reply(struct bat_priv *bat_priv, struct sk_buff *skb);
 bool arp_snoop_incoming_reply(struct bat_priv *bat_priv, struct sk_buff *skb);
 bool arp_drop_broadcast_packet(struct bat_priv *bat_priv,
-			       struct forw_packet *forw_packet);
+		       struct forw_packet *forw_packet);
+void arp_change_timeout(struct net_device *soft_iface, const char *name);
+
+#else
+
+#define arp_snoop_outgoing_request(...) (0)
+#define arp_snoop_incoming_request(...) (0)
+#define arp_snoop_outgoing_reply(...)
+#define arp_snoop_incoming_reply(...)
+#define arp_drop_broadcast_packet(...) (0)
+#define arp_change_timeout(...)
+
+#endif /* CONFIG_BATMAN_ADV_DAT */
 
 /* hash function to choose an entry in a hash table of given size */
 /* hash algorithm from http://en.wikipedia.org/wiki/Hash_table */
diff --git a/hard-interface.c b/hard-interface.c
index 4a6948c..af17c9c 100644
--- a/hard-interface.c
+++ b/hard-interface.c
@@ -118,9 +118,11 @@ static void primary_if_update_addr(struct bat_priv *bat_priv)
 	if (!primary_if)
 		goto out;
 
+#ifdef CONFIG_BATMAN_ADV_DAT
 	bat_priv->dht_hash = (dat_addr_t)
 				choose_orig(primary_if->net_dev->dev_addr,
 					    DAT_ADDR_MAX);
+#endif
 
 	vis_packet = (struct vis_packet *)
 				bat_priv->my_vis_info->skb_packet->data;
diff --git a/originator.c b/originator.c
index 14fb6d8..270c1c3 100644
--- a/originator.c
+++ b/originator.c
@@ -224,7 +224,9 @@ struct orig_node *get_orig_node(struct bat_priv *bat_priv, const uint8_t *addr)
 	orig_node->tt_poss_change = false;
 	orig_node->bat_priv = bat_priv;
 	memcpy(orig_node->orig, addr, ETH_ALEN);
+#ifdef CONFIG_BATMAN_ADV_DAT
 	orig_node->dht_hash = (dat_addr_t)choose_orig(addr, DAT_ADDR_MAX);
+#endif
 	orig_node->router = NULL;
 	orig_node->tt_crc = 0;
 	atomic_set(&orig_node->last_ttvn, 0);
diff --git a/send.c b/send.c
index d625998..2b7ddc9 100644
--- a/send.c
+++ b/send.c
@@ -31,8 +31,6 @@
 #include "originator.h"
 #include "bat_ogm.h"
 
-#include <net/arp.h>
-
 static void send_outstanding_bcast_packet(struct work_struct *work);
 
 /* send out an already prepared packet to the given address via the
diff --git a/soft-interface.c b/soft-interface.c
index 1194cf7..96ebd38 100644
--- a/soft-interface.c
+++ b/soft-interface.c
@@ -36,7 +36,6 @@
 #include <linux/ethtool.h>
 #include <linux/etherdevice.h>
 #include <linux/if_vlan.h>
-#include <linux/inetdevice.h>
 #include "unicast.h"
 
 
@@ -826,7 +825,6 @@ static void interface_setup(struct net_device *dev)
 struct net_device *softif_create(const char *name)
 {
 	struct net_device *soft_iface;
-	struct in_device *in_dev;
 	struct bat_priv *bat_priv;
 	int ret;
 
@@ -842,20 +840,7 @@ struct net_device *softif_create(const char *name)
 		goto free_soft_iface;
 	}
 
-	in_dev = in_dev_get(soft_iface);
-	if (!in_dev) {
-		pr_err("Unable to set ARP parameters for the batman interface "
-		       "'%s'\n", name);
-		goto free_soft_iface;
-	}
-
-	/* Introduce a delay in the ARP state-machine transactions. Entries
-	 * will be kept in the ARP table for the default time multiplied by 4 */
-	in_dev->arp_parms->base_reachable_time *= ARP_TIMEOUT_FACTOR;
-	in_dev->arp_parms->gc_staletime *= ARP_TIMEOUT_FACTOR;
-	in_dev->arp_parms->reachable_time *= ARP_TIMEOUT_FACTOR;
-
-	in_dev_put(in_dev);
+	arp_change_timeout(soft_iface, name);
 
 	bat_priv = netdev_priv(soft_iface);
 
@@ -886,7 +871,9 @@ struct net_device *softif_create(const char *name)
 	bat_priv->primary_if = NULL;
 	bat_priv->num_ifaces = 0;
 
+#ifdef CONFIG_BATMAN_ADV_DAT
 	bat_priv->dht_hash = 0;
+#endif
 
 	ret = sysfs_add_meshif(soft_iface);
 	if (ret < 0)
diff --git a/types.h b/types.h
index afd166b..27751f2 100644
--- a/types.h
+++ b/types.h
@@ -68,7 +68,9 @@ struct hard_iface {
 struct orig_node {
 	uint8_t orig[ETH_ALEN];
 	uint8_t primary_addr[ETH_ALEN];
+#ifdef CONFIG_BATMAN_ADV_DAT
 	dat_addr_t dht_hash;
+#endif
 	struct neigh_node __rcu *router; /* rcu protected pointer */
 	unsigned long *bcast_own;
 	uint8_t *bcast_own_sum;
@@ -207,7 +209,9 @@ struct bat_priv {
 	struct gw_node __rcu *curr_gw;  /* rcu protected pointer */
 	atomic_t gw_reselect;
 	struct hard_iface __rcu *primary_if;  /* rcu protected pointer */
+#ifdef CONFIG_BATMAN_ADV_DAT
 	dat_addr_t dht_hash;
+#endif
 	struct vis_info *my_vis_info;
 };
 
-- 
1.7.3.4

Re: [B.A.T.M.A.N.] [PATCHv4 7/7] batman-adv: add Distributed ARP Table compile option

[Marek Lindner]

On Friday, November 25, 2011 06:21:19 Antonio Quartulli wrote:
>  /*
> - * dat_addr_t is the type used for all DHT indexes. If it is changed,
> - * DAT_ADDR_MAX is changed as well.
> - *
> - * *Please be careful: dat_addr_t must be UNSIGNED*
> - */
> +* dat_addr_t is the type used for all DHT indexes. If it is changed,
> +* DAT_ADDR_MAX is changed as well.
> +*
> +* *Please be careful: dat_addr_t must be UNSIGNED*
> +*/
>  #define dat_addr_t uint16_t
>  #define DAT_ADDR_MAX biggest_unsigned_int(dat_addr_t)
>  
>  #define ARP_HW_SRC(skb) ((uint8_t *)(skb->data) + sizeof(struct ethhdr) +
> \ -                       sizeof(struct arphdr))
> +               sizeof(struct arphdr))
>  #define ARP_IP_SRC(skb) (*(uint32_t *)(ARP_HW_SRC(skb) + ETH_ALEN))
>  #define ARP_HW_DST(skb) (ARP_HW_SRC(skb) + ETH_ALEN + 4)
>  #define ARP_IP_DST(skb) (*(uint32_t *)(ARP_HW_SRC(skb) + ETH_ALEN * 2 +
> 4)) 
> +
>  bool arp_snoop_outgoing_request(struct bat_priv *bat_priv,
> -                               struct sk_buff *skb);
> +                       struct sk_buff *skb);
>  bool arp_snoop_incoming_request(struct bat_priv *bat_priv,
> -                               struct sk_buff *skb);
> +                       struct sk_buff *skb);
>  bool arp_snoop_outgoing_reply(struct bat_priv *bat_priv, struct sk_buff
> *skb); bool arp_snoop_incoming_reply(struct bat_priv *bat_priv, struct
> sk_buff *skb); bool arp_drop_broadcast_packet(struct bat_priv *bat_priv,
> -                              struct forw_packet *forw_packet);
> +                      struct forw_packet *forw_packet);

This looks like a couple of spacing fixes that do not belong here ...

Regards,
Marek