[B.A.T.M.A.N.] [PATCH 0/6] DAT: Distributed ARP Table

[B.A.T.M.A.N.] [PATCH 0/6] DAT: Distributed ARP Table

[Antonio Quartulli]

Hello people,
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/DAT

[B.A.T.M.A.N.] [PATCH 1/6] 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 |   48 ++++++++++++++++++++++++++++++++----------------
 unicast.h |    2 ++
 2 files changed, 34 insertions(+), 16 deletions(-)

diff --git a/unicast.c b/unicast.c
index 07d1c1d..ee7bceb 100644
--- a/unicast.c
+++ b/unicast.c
@@ -283,6 +283,33 @@ out:
 	return ret;
 }
 
+struct sk_buff *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)
+		goto out;
+
+	unicast_packet = (struct unicast_packet *)skb->data;
+
+	unicast_packet->version = COMPAT_VERSION;
+	/* batman packet type: unicast */
+	unicast_packet->packet_type = BAT_UNICAST;
+	/* set unicast ttl */
+	unicast_packet->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 skb;
+out:
+	kfree(skb);
+	return NULL;
+}
+
 int unicast_send_skb(struct sk_buff *skb, struct bat_priv *bat_priv)
 {
 	struct ethhdr *ethhdr = (struct ethhdr *)skb->data;
@@ -296,7 +323,7 @@ int unicast_send_skb(struct sk_buff *skb, struct bat_priv *bat_priv)
 	if (is_multicast_ether_addr(ethhdr->h_dest)) {
 		orig_node = gw_get_selected_orig(bat_priv);
 		if (orig_node)
-			goto find_router;
+			goto prepare_packet;
 	}
 
 	/* check for tt host - increases orig_node refcount.
@@ -304,33 +331,22 @@ int unicast_send_skb(struct sk_buff *skb, struct bat_priv *bat_priv)
 	orig_node = transtable_search(bat_priv, ethhdr->h_source,
 				      ethhdr->h_dest);
 
-find_router:
+prepare_packet:
 	/**
 	 * find_router():
 	 *  - if orig_node is NULL it returns NULL
 	 *  - increases neigh_nodes refcount if found.
 	 */
 	neigh_node = find_router(bat_priv, orig_node, NULL);
-
 	if (!neigh_node)
 		goto out;
 
-	if (my_skb_head_push(skb, sizeof(*unicast_packet)) < 0)
+	skb = prepare_unicast_packet(skb, orig_node);
+	if (!skb)
 		goto out;
 
 	unicast_packet = (struct unicast_packet *)skb->data;
 
-	unicast_packet->version = COMPAT_VERSION;
-	/* batman packet type: unicast */
-	unicast_packet->packet_type = BAT_UNICAST;
-	/* set unicast ttl */
-	unicast_packet->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) {
@@ -350,7 +366,7 @@ out:
 		neigh_node_free_ref(neigh_node);
 	if (orig_node)
 		orig_node_free_ref(orig_node);
-	if (ret == 1)
+	if (ret == 1 && skb)
 		kfree_skb(skb);
 	return ret;
 }
diff --git a/unicast.h b/unicast.h
index 8fd5535..f53a735 100644
--- a/unicast.h
+++ b/unicast.h
@@ -33,6 +33,8 @@ 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[]);
+struct sk_buff *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

[B.A.T.M.A.N.] [PATCH 2/6] 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>
---
 bat_sysfs.c |    2 +-
 main.h      |    3 ++-
 2 files changed, 3 insertions(+), 2 deletions(-)

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 53e5d9f..f3978c0 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.] [PATCH 3/6] 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 +
 arp.c            |  185 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 arp.h            |   46 +++++++++++++
 hard-interface.c |    2 +
 main.h           |    7 ++
 originator.c     |    1 +
 soft-interface.c |    3 +
 types.h          |    7 ++
 8 files changed, 252 insertions(+), 0 deletions(-)
 create mode 100644 arp.c
 create mode 100644 arp.h

diff --git a/Makefile.kbuild b/Makefile.kbuild
index bd7e93c..c8d6543 100644
--- a/Makefile.kbuild
+++ b/Makefile.kbuild
@@ -32,6 +32,7 @@ ccflags-y += -DSOURCE_VERSION=\"$(REVISION)\"
 endif
 
 obj-m += batman-adv.o
+batman-adv-y += arp.o
 batman-adv-y += bat_debugfs.o
 batman-adv-y += bat_iv_ogm.o
 batman-adv-y += bat_sysfs.o
diff --git a/arp.c b/arp.c
new file mode 100644
index 0000000..39043b8
--- /dev/null
+++ b/arp.c
@@ -0,0 +1,185 @@
+/*
+ * 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 "arp.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;
+	uint16_t last_max = USHRT_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 = hash_ipv4(&ip_dst, USHRT_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 = USHRT_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 = USHRT_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;
+
+				if (!atomic_inc_not_zero(&orig_node->refcount))
+					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);
+		tmp_skb = prepare_unicast_packet(tmp_skb, cand[i].orig_node);
+		if (tmp_skb)
+			send_skb_packet(tmp_skb, neigh_node->if_incoming,
+					neigh_node->addr);
+		/* 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/arp.h b/arp.h
new file mode 100644
index 0000000..ee1a8b3
--- /dev/null
+++ b/arp.h
@@ -0,0 +1,46 @@
+/*
+ * 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_
+
+/* 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 7704df4..3508934 100644
--- a/hard-interface.c
+++ b/hard-interface.c
@@ -117,6 +117,8 @@ static void primary_if_update_addr(struct bat_priv *bat_priv)
 	if (!primary_if)
 		goto out;
 
+	bat_priv->dht_hash = choose_orig(bat_priv, USHRT_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 f3978c0..2ca7b08 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 0bc2045..9673b44 100644
--- a/originator.c
+++ b/originator.c
@@ -222,6 +222,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 = choose_orig(addr, USHRT_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 45297c8..ca15aa7 100644
--- a/soft-interface.c
+++ b/soft-interface.c
@@ -20,6 +20,7 @@
  */
 
 #include "main.h"
+#include "arp.h"
 #include "soft-interface.h"
 #include "hard-interface.h"
 #include "routing.h"
@@ -855,6 +856,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 ab8d0fe..837bc42 100644
--- a/types.h
+++ b/types.h
@@ -67,6 +67,7 @@ struct hard_iface {
 struct orig_node {
 	uint8_t orig[ETH_ALEN];
 	uint8_t primary_addr[ETH_ALEN];
+	uint16_t dht_hash;
 	struct neigh_node __rcu *router; /* rcu protected pointer */
 	unsigned long *bcast_own;
 	uint8_t *bcast_own_sum;
@@ -204,6 +205,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 */
+	uint16_t dht_hash;
 	struct vis_info *my_vis_info;
 };
 
@@ -343,4 +345,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.] [PATCH 4/6] 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>
---
 arp.c |   43 +++++++++++++++++++++++++++++++++++++++++++
 arp.h |    7 +++++++
 2 files changed, 50 insertions(+), 0 deletions(-)

diff --git a/arp.c b/arp.c
index 39043b8..ea7cc1e 100644
--- a/arp.c
+++ b/arp.c
@@ -183,3 +183,46 @@ out:
 	kfree(cand);
 	return ret;
 }
+
+/* Returns arphdr->ar_op if the skb contains a valid ARP packet, otherwise
+ * returns 0 */
+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) + 8 + 12)))
+		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(DBG_ARP, bat_priv, "ARP message of type %d recognised "
+		"[%pM-%pI4 %pM-%pI4]\n", type, ARP_HW_SRC(skb),
+		&ARP_IP_SRC(skb), ARP_HW_DST(skb), &ARP_IP_DST(skb));
+out:
+	return type;
+}
diff --git a/arp.h b/arp.h
index ee1a8b3..56b0a0a 100644
--- a/arp.h
+++ b/arp.h
@@ -22,6 +22,13 @@
 #ifndef _NET_BATMAN_ADV_ARP_H_
 #define _NET_BATMAN_ADV_ARP_H_
 
+#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))
+
+uint16_t arp_get_type(struct bat_priv *bat_priv, struct sk_buff *skb);
+
 /* 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

[B.A.T.M.A.N.] [PATCH 5/6] 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>
---
 Makefile.kbuild  |    2 +-
 arp.c            |  195 +++++++++++++++++++++++++++++++++++++++++++++++++++++-
 arp.h            |    6 ++
 main.h           |    2 +
 routing.c        |    2 +
 send.c           |   18 +++++
 soft-interface.c |   22 ++++++-
 7 files changed, 244 insertions(+), 3 deletions(-)

diff --git a/Makefile.kbuild b/Makefile.kbuild
index c8d6543..3076c22 100644
--- a/Makefile.kbuild
+++ b/Makefile.kbuild
@@ -25,7 +25,7 @@ ifeq ($(MAKING_MODULES),1)
 -include $(TOPDIR)/Rules.make
 endif
 
-# ccflags-y += -DCONFIG_BATMAN_ADV_DEBUG
+ccflags-y += -DCONFIG_BATMAN_ADV_DEBUG
 
 ifneq ($(REVISION),)
 ccflags-y += -DSOURCE_VERSION=\"$(REVISION)\"
diff --git a/arp.c b/arp.c
index ea7cc1e..e3e0c8c 100644
--- a/arp.c
+++ b/arp.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 "arp.h"
@@ -184,6 +186,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 */
 uint16_t arp_get_type(struct bat_priv *bat_priv, struct sk_buff *skb)
@@ -200,7 +227,7 @@ uint16_t arp_get_type(struct bat_priv *bat_priv, struct sk_buff *skb)
 	if (ethhdr->h_proto != htons(ETH_P_ARP))
 		goto out;
 
-	if (unlikely(!pskb_may_pull(skb, ETH_HLEN + arp_hdr_len(skb->dev) + 8 + 12)))
+	if (unlikely(!pskb_may_pull(skb, ETH_HLEN + arp_hdr_len(skb->dev))))
 		goto out;
 
 	arphdr = (struct arphdr *)(skb->data + sizeof(struct ethhdr));
@@ -226,3 +253,169 @@ 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);
+		unicast_send_skb(skb_new, bat_priv);
+		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);
+	if (n)
+		neigh_release(n);
+out:
+	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 immediatly, 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);
+
+	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;
+}
diff --git a/arp.h b/arp.h
index 56b0a0a..f1d3e39 100644
--- a/arp.h
+++ b/arp.h
@@ -28,6 +28,12 @@
 #define ARP_IP_DST(skb) (*(uint32_t *)(ARP_HW_SRC(skb) + ETH_ALEN * 2 + 4))
 
 uint16_t arp_get_type(struct bat_priv *bat_priv, struct sk_buff *skb);
+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);
 
 /* 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/main.h b/main.h
index 2ca7b08..13f63d8 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/routing.c b/routing.c
index ef24a72..4f2b417 100644
--- a/routing.c
+++ b/routing.c
@@ -20,6 +20,7 @@
  */
 
 #include "main.h"
+#include "arp.h"
 #include "routing.h"
 #include "send.h"
 #include "soft-interface.h"
@@ -965,6 +966,7 @@ int recv_unicast_packet(struct sk_buff *skb, struct hard_iface *recv_if)
 	/* packet for me */
 	if (is_my_mac(unicast_packet->dest)) {
 		interface_rx(recv_if->soft_iface, skb, recv_if, hdr_size);
+
 		return NET_RX_SUCCESS;
 	}
 
diff --git a/send.c b/send.c
index 8a684eb..8a12e1b 100644
--- a/send.c
+++ b/send.c
@@ -20,6 +20,7 @@
  */
 
 #include "main.h"
+#include "arp.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
@@ -267,6 +270,7 @@ static void send_outstanding_bcast_packet(struct work_struct *work)
 	struct sk_buff *skb1;
 	struct net_device *soft_iface = forw_packet->if_incoming->soft_iface;
 	struct bat_priv *bat_priv = netdev_priv(soft_iface);
+	struct neighbour *n;
 
 	spin_lock_bh(&bat_priv->forw_bcast_list_lock);
 	hlist_del(&forw_packet->list);
@@ -275,6 +279,20 @@ static void send_outstanding_bcast_packet(struct work_struct *work)
 	if (atomic_read(&bat_priv->mesh_state) == MESH_DEACTIVATING)
 		goto out;
 
+	/* 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),
+				 soft_iface);
+		/* check if we already know this neigh */
+		if (n && (n->nud_state & NUD_CONNECTED))
+			goto out;
+
+		bat_dbg(DBG_ARP, bat_priv, "ARP request: fallback\n");
+	}
+
 	/* 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 ca15aa7..db8c6b1 100644
--- a/soft-interface.c
+++ b/soft-interface.c
@@ -565,9 +565,12 @@ static int interface_tx(struct sk_buff *skb, struct net_device *soft_iface)
 	struct vlan_ethhdr *vhdr;
 	struct softif_neigh *curr_softif_neigh = NULL;
 	unsigned int header_len = 0;
+	struct orig_node *orig_node = NULL;
+	struct sk_buff *arp_skb = NULL;
 	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;
@@ -629,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;
 
@@ -648,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. */
@@ -662,7 +668,12 @@ static int interface_tx(struct sk_buff *skb, struct net_device *soft_iface)
 				goto dropped;
 		}
 
+		/* Increase the refcount to avoid to make the kernel consume
+		 * the skb */
+		arp_skb = skb_clone(skb, GFP_ATOMIC);
 		ret = unicast_send_skb(skb, bat_priv);
+
+		arp_snoop_outgoing_reply(bat_priv, arp_skb);
 		if (ret != 0)
 			goto dropped_freed;
 	}
@@ -680,6 +691,10 @@ end:
 		softif_neigh_free_ref(curr_softif_neigh);
 	if (primary_if)
 		hardif_free_ref(primary_if);
+	if (orig_node)
+		orig_node_free_ref(orig_node);
+	if (arp_skb)
+		kfree_skb(arp_skb);
 	return NETDEV_TX_OK;
 }
 
@@ -717,6 +732,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

[B.A.T.M.A.N.] [PATCH 6/6] 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 13f63d8..8c534b4 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 db8c6b1..577d0ff 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"
 
 
@@ -832,6 +833,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;
 
@@ -847,6 +849,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

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

[Sven Eckelmann]

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

On Sunday 30 October 2011 09:56:01 Antonio Quartulli wrote:
> 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>
[...]
> diff --git a/Makefile.kbuild b/Makefile.kbuild
> index c8d6543..3076c22 100644
> --- a/Makefile.kbuild
> +++ b/Makefile.kbuild
> @@ -25,7 +25,7 @@ ifeq ($(MAKING_MODULES),1)
>  -include $(TOPDIR)/Rules.make
>  endif
> 
> -# ccflags-y += -DCONFIG_BATMAN_ADV_DEBUG
> +ccflags-y += -DCONFIG_BATMAN_ADV_DEBUG
> 
>  ifneq ($(REVISION),)
>  ccflags-y += -DSOURCE_VERSION=\"$(REVISION)\"

Please remove that change.

Thanks,
	Sven

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

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

[Antonio Quartulli]

On Sun, Oct 30, 2011 at 10:18:42AM +0100, Sven Eckelmann wrote:
> > Signed-off-by: Antonio Quartulli <ordex@autistici.org>
> [...]
> > diff --git a/Makefile.kbuild b/Makefile.kbuild
> > index c8d6543..3076c22 100644
> > --- a/Makefile.kbuild
> > +++ b/Makefile.kbuild
> > @@ -25,7 +25,7 @@ ifeq ($(MAKING_MODULES),1)
> >  -include $(TOPDIR)/Rules.make
> >  endif
> > 
> > -# ccflags-y += -DCONFIG_BATMAN_ADV_DEBUG
> > +ccflags-y += -DCONFIG_BATMAN_ADV_DEBUG
> > 
> >  ifneq ($(REVISION),)
> >  ccflags-y += -DSOURCE_VERSION=\"$(REVISION)\"
> 
> Please remove that change.

Done. Thanks for highlighting it.




-- 
Antonio Quartulli

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

Re: [B.A.T.M.A.N.] [PATCH 0/6] DAT: Distributed ARP Table

[Simon Wunderlich]

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

Hello Antonio,

thanks for the patchset! I've tested it again in my kvm setup, it worked very
well.

There are some issues remaining, I'll comment the individual patches for this.
About the general stuff:

 * maybe we should rename arp.{c|h} to dat.{c|h} to avoid confusion with
   other code in the linux kernel?
 * please do a checkpatch.pl --strict check on the patches, there were some
   warnings about too long lines and bad spaces

Cheers,
	Simon

On Sun, Oct 30, 2011 at 09:55:56AM +0100, Antonio Quartulli wrote:
> Hello people,
> 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/DAT
> 
> 

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

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

[Simon Wunderlich]

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

On Sun, Oct 30, 2011 at 09:55:57AM +0100, Antonio Quartulli wrote:
> @@ -304,33 +331,22 @@ int unicast_send_skb(struct sk_buff *skb, struct bat_priv *bat_priv)
>  	orig_node = transtable_search(bat_priv, ethhdr->h_source,
>  				      ethhdr->h_dest);
>  
> -find_router:
> +prepare_packet:
>  	/**
>  	 * find_router():

I guess the comment should be changed as well when the label is renamed.

>  	 *  - if orig_node is NULL it returns NULL
>  	 *  - increases neigh_nodes refcount if found.
>  	 */
>  	neigh_node = find_router(bat_priv, orig_node, NULL);
> -

Do we really need to remove this newline?


>  	if (!neigh_node)
>  		goto out;
>  
> -	if (my_skb_head_push(skb, sizeof(*unicast_packet)) < 0)
> +	skb = prepare_unicast_packet(skb, orig_node);
> +	if (!skb)
>  		goto out;
>  
>  	unicast_packet = (struct unicast_packet *)skb->data;
>  
> -	unicast_packet->version = COMPAT_VERSION;
> -	/* batman packet type: unicast */
> -	unicast_packet->packet_type = BAT_UNICAST;
> -	/* set unicast ttl */
> -	unicast_packet->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) {
> @@ -350,7 +366,7 @@ out:
>  		neigh_node_free_ref(neigh_node);
>  	if (orig_node)
>  		orig_node_free_ref(orig_node);
> -	if (ret == 1)
> +	if (ret == 1 && skb)
>  		kfree_skb(skb);
>  	return ret;
>  }

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

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

[Simon Wunderlich]

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

On Sun, Oct 30, 2011 at 09:55:59AM +0100, Antonio Quartulli wrote:
> [...]
> +		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 = USHRT_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;
> +
> +				if (!atomic_inc_not_zero(&orig_node->refcount))
> +					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;

Why do you increase the refcount two times? If it is really required, please
add a comment.

> +
> +				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;
> +		}

no braces are required here.

> +
> +		neigh_node = orig_node_get_router(cand[i].orig_node);
> +		if (!neigh_node)
> +			goto free_orig;
> +
> +		tmp_skb = pskb_copy(skb, GFP_ATOMIC);
> +		tmp_skb = prepare_unicast_packet(tmp_skb, cand[i].orig_node);
> +		if (tmp_skb)
> +			send_skb_packet(tmp_skb, neigh_node->if_incoming,
> +					neigh_node->addr);
> +		/* 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;
> +}

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

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

[Simon Wunderlich]

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

This patch is not checkpatch.pl --strict clean

On Sun, Oct 30, 2011 at 09:56:00AM +0100, Antonio Quartulli wrote:
> 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>
> ---
>  arp.c |   43 +++++++++++++++++++++++++++++++++++++++++++
>  arp.h |    7 +++++++
>  2 files changed, 50 insertions(+), 0 deletions(-)
> 
> diff --git a/arp.c b/arp.c
> index 39043b8..ea7cc1e 100644
> --- a/arp.c
> +++ b/arp.c
> @@ -183,3 +183,46 @@ out:
>  	kfree(cand);
>  	return ret;
>  }
> +
> +/* Returns arphdr->ar_op if the skb contains a valid ARP packet, otherwise
> + * returns 0 */
> +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) + 8 + 12)))
> +		goto out;

use ETH_ALEN * 2 + 4 * 2 instead to show where theses numbers come from.


> +
> +	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(DBG_ARP, bat_priv, "ARP message of type %d recognised "
> +		"[%pM-%pI4 %pM-%pI4]\n", type, ARP_HW_SRC(skb),
> +		&ARP_IP_SRC(skb), ARP_HW_DST(skb), &ARP_IP_DST(skb));

Would you mind printing the type as string? something like REQUEST or REPLY instead of 1 and 2 ...


> +out:
> +	return type;
> +}

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

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

[Simon Wunderlich]

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

This patch fails checkpatch.pl --strict.

On Sun, Oct 30, 2011 at 09:56:01AM +0100, Antonio Quartulli wrote:
> +bool arp_snoop_outgoing_request(struct bat_priv *bat_priv, struct sk_buff *skb)
> [...]
> +	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);
> +		unicast_send_skb(skb_new, bat_priv);
> +		bat_dbg(DBG_ARP, bat_priv, "ARP request replied locally\n");

This function is hooked up in the tx patch, why do we send the unicast reply to
the mesh? Shouldn't it be sent on the soft interface instead? I don't really understand this one ...

> +	} else
> +		/* Send the request on the DHT */
> +		ret = dht_send_data(bat_priv, skb, ip_dst);
> +	if (n)
> +		neigh_release(n);
> +out:
> +	if (primary_if)
> +		hardif_free_ref(primary_if);
> +	return ret;
> +}
> +
> diff --git a/routing.c b/routing.c
> index ef24a72..4f2b417 100644
> --- a/routing.c
> +++ b/routing.c
> @@ -965,6 +966,7 @@ int recv_unicast_packet(struct sk_buff *skb, struct hard_iface *recv_if)
>  	/* packet for me */
>  	if (is_my_mac(unicast_packet->dest)) {
>  		interface_rx(recv_if->soft_iface, skb, recv_if, hdr_size);
> +
>  		return NET_RX_SUCCESS;
>  	}
>  

This added newline is useless.

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

Re: [B.A.T.M.A.N.] [PATCH 0/6] DAT: Distributed ARP Table

[Martin Hundebøll]

On 2011-10-31 01:03, Simon Wunderlich wrote:
> Hello Antonio,
>
> thanks for the patchset! I've tested it again in my kvm setup, it worked very
> well.
>
> There are some issues remaining, I'll comment the individual patches for this.
> About the general stuff:
>
>   * maybe we should rename arp.{c|h} to dat.{c|h} to avoid confusion with
>     other code in the linux kernel?

I propose "distributet-arp-tables.{c|h}" to avoid too many acronyms in our file names.

-- 
Kind regards
Martin Hundebøll

+45 61 65 54 61
martin@hundeboll.net

Nordborggade 57, 2. tv
8000 Aarhus C
Denmark

Re: [B.A.T.M.A.N.] [PATCH 0/6] DAT: Distributed ARP Table

[Marek Lindner]

On Monday, October 31, 2011 10:26:39 Martin Hundebøll wrote:
> On 2011-10-31 01:03, Simon Wunderlich wrote:
> > Hello Antonio,
> > 
> > thanks for the patchset! I've tested it again in my kvm setup, it worked
> > very well.
> > 
> > There are some issues remaining, I'll comment the individual patches for
> > this.
> > 
> > About the general stuff:
> >   * maybe we should rename arp.{c|h} to dat.{c|h} to avoid confusion with
> >   
> >     other code in the linux kernel?
> 
> I propose "distributet-arp-tables.{c|h}" to avoid too many acronyms in our
> file names.

I second that but I suggest:
distributed-arp-tables.{c|h}

Regards,
Marek

Re: [B.A.T.M.A.N.] [PATCH 0/6] DAT: Distributed ARP Table

[Simon Wunderlich]

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

+1

:)

On Mon, Oct 31, 2011 at 10:42:33AM +0100, Marek Lindner wrote:
> On Monday, October 31, 2011 10:26:39 Martin Hundebøll wrote:
> > On 2011-10-31 01:03, Simon Wunderlich wrote:
> > > Hello Antonio,
> > > 
> > > thanks for the patchset! I've tested it again in my kvm setup, it worked
> > > very well.
> > > 
> > > There are some issues remaining, I'll comment the individual patches for
> > > this.
> > > 
> > > About the general stuff:
> > >   * maybe we should rename arp.{c|h} to dat.{c|h} to avoid confusion with
> > >   
> > >     other code in the linux kernel?
> > 
> > I propose "distributet-arp-tables.{c|h}" to avoid too many acronyms in our
> > file names.
> 
> I second that but I suggest:
> distributed-arp-tables.{c|h}
> 
> Regards,
> Marek
> 
> 

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

Re: [B.A.T.M.A.N.] [PATCH 0/6] DAT: Distributed ARP Table

[Gus Wirth]

On 10/30/2011 01:55 AM, Antonio Quartulli wrote:
> Hello people,
> 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/DAT

The link to the Wiki page doesn't work.

The actual link:

http://www.open-mesh.org/wiki/batman-adv/DistributedArpTable

Except there is no information there :(

Gus

Re: [B.A.T.M.A.N.] [PATCH 0/6] DAT: Distributed ARP Table

[Simon Wunderlich]

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

Hey,

seems the Wiki was edited just recently, have a look here:

http://www.open-mesh.org/wiki/batman-adv/GSOC2011_DAT

Cheers,
	Simon

On Mon, Oct 31, 2011 at 11:53:10AM -0700, Gus Wirth wrote:
> 
> The link to the Wiki page doesn't work.
> 
> The actual link:
> 
> http://www.open-mesh.org/wiki/batman-adv/DistributedArpTable
> 
> Except there is no information there :(
> 
> Gus
> 

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

Re: [B.A.T.M.A.N.] [PATCH 0/6] DAT: Distributed ARP Table

[Antonio Quartulli]

On Mon, Oct 31, 2011 at 11:53:10 -0700, Gus Wirth wrote:
> On 10/30/2011 01:55 AM, Antonio Quartulli wrote:
> > Hello people,
> > 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/DAT
> 
> The link to the Wiki page doesn't work.
> 
> The actual link:
> 
> http://www.open-mesh.org/wiki/batman-adv/DistributedArpTable
> 
> Except there is no information there :(
> 


Sorry for this, yesterday evening I was restructuring the documentation and I
moved [1] to [2] (I had in mind to write an email about this, but it was late..)

Later, [3] will become the official documenting page of DAT (W.I.P. now).

[1] http://www.open-mesh.org/wiki/batman-adv/DAT
[2] http://www.open-mesh.org/wiki/batman-adv/GSOC2011_DAT
[3] http://www.open-mesh.org/wiki/batman-adv/DistributedArpTable

Cheers,

-- 
Antonio Quartulli

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

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

[Antonio Quartulli]

On Mon, Oct 31, 2011 at 01:05:46AM +0100, Simon Wunderlich wrote:
> On Sun, Oct 30, 2011 at 09:55:57AM +0100, Antonio Quartulli wrote:
> > -find_router:
> > +prepare_packet:
> >  	/**
> >  	 * find_router():
> 
> I guess the comment should be changed as well when the label is renamed.

Actually this comment refers to the function below, not to the label.

> 
> >  	 *  - if orig_node is NULL it returns NULL
> >  	 *  - increases neigh_nodes refcount if found.
> >  	 */
> >  	neigh_node = find_router(bat_priv, orig_node, NULL);
> > -
> 
> Do we really need to remove this newline?
>

Don't think so ;)

Thanks,

-- 
Antonio Quartulli

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

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

[Antonio Quartulli]

On Mon, Oct 31, 2011 at 01:10:04AM +0100, Simon Wunderlich wrote:
> This patch is not checkpatch.pl --strict clean
> 
> On Sun, Oct 30, 2011 at 09:56:00AM +0100, Antonio Quartulli wrote:
> > +	if (unlikely(!pskb_may_pull(skb, ETH_HLEN + arp_hdr_len(skb->dev) + 8 + 12)))
> > +		goto out;
> 
> use ETH_ALEN * 2 + 4 * 2 instead to show where theses numbers come from.

Actually this is a mistake, because I have recently seen that arp_hdr_len()
already includes those supplementary bytes.

> > +	bat_dbg(DBG_ARP, bat_priv, "ARP message of type %d recognised "
> > +		"[%pM-%pI4 %pM-%pI4]\n", type, ARP_HW_SRC(skb),
> > +		&ARP_IP_SRC(skb), ARP_HW_DST(skb), &ARP_IP_DST(skb));
> 
> Would you mind printing the type as string? something like REQUEST or REPLY instead of 1 and 2 ...

Oky


Thanks, 

-- 
Antonio Quartulli

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

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

[Antonio Quartulli]

On Mon, Oct 31, 2011 at 01:12:21AM +0100, Simon Wunderlich wrote:
> This patch fails checkpatch.pl --strict.
> 
> On Sun, Oct 30, 2011 at 09:56:01AM +0100, Antonio Quartulli wrote:
> > +bool arp_snoop_outgoing_request(struct bat_priv *bat_priv, struct sk_buff *skb)
> > [...]
> > +	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);
> > +		unicast_send_skb(skb_new, bat_priv);
> > +		bat_dbg(DBG_ARP, bat_priv, "ARP request replied locally\n");
> 
> This function is hooked up in the tx patch, why do we send the unicast reply to
> the mesh? Shouldn't it be sent on the soft interface instead? I don't really understand this one ...

You are right. As we have already discussed on IRC, I should use netif_rx()
directly here (to deliver the packet to the soft_iface).

> >  	if (is_my_mac(unicast_packet->dest)) {
> >  		interface_rx(recv_if->soft_iface, skb, recv_if, hdr_size);
> > +
> >  		return NET_RX_SUCCESS;
> >  	}
> >  
> 
> This added newline is useless.

Yeah :D

Thanks,

-- 
Antonio Quartulli

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

Re: [B.A.T.M.A.N.] [PATCH 0/6] DAT: Distributed ARP Table

[Antonio Quartulli]

On Mon, Oct 31, 2011 at 10:48:12AM +0100, Simon Wunderlich wrote:
> +1
> 
> :)
> 
> On Mon, Oct 31, 2011 at 10:42:33AM +0100, Marek Lindner wrote:
> > On Monday, October 31, 2011 10:26:39 Martin Hundebøll wrote:
> > > On 2011-10-31 01:03, Simon Wunderlich wrote:
> > > > Hello Antonio,
> > > > 
> > > > thanks for the patchset! I've tested it again in my kvm setup, it worked
> > > > very well.
> > > > 
> > > > There are some issues remaining, I'll comment the individual patches for
> > > > this.
> > > > 
> > > > About the general stuff:
> > > >   * maybe we should rename arp.{c|h} to dat.{c|h} to avoid confusion with
> > > >   
> > > >     other code in the linux kernel?
> > > 
> > > I propose "distributet-arp-tables.{c|h}" to avoid too many acronyms in our
> > > file names.
> > 
> > I second that but I suggest:
> > distributed-arp-tables.{c|h}



ok :)


Thanks,

-- 
Antonio Quartulli

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