[B.A.T.M.A.N.] [PATCH 0/6] Solve consistency issues in TT code

[B.A.T.M.A.N.] [PATCH 0/6] Solve consistency issues in TT code

[Antonio Quartulli]

Hello everybody.

In the current TT implementation there are some cases where transtable
consistency is not kept.

In particular, it is possible to observe this problem in case of a tt_response
issued after a request for full-table: if the responding node is _the real
destination of the request_ then it will send within the response message also
those clients added after the last ttvn increment.
This will cause an inconsistency because now we have different nodes with
the same ttvn value but with different tables for the same originator.

These patches are meant to solve this issue and keep consistency among nodes.

Patches 1) and 2) introduce beautifications only. This change helped in writing
patches 5) and 6) by reducing the code complexity.

I would like to read some feedbacks even about the patch decomposition, which
could probably be improved :-)

Thank you all.

Regards,
	Antonio Quartulli

[B.A.T.M.A.N.] [PATCH 1/6] batman-adv: unify the three starting fields of the tt_local/global_entry structures

[Antonio Quartulli]

Now the three starting fields of the tt_local/global_entry structures are
unified. This allows to write generalised functions that operate on the
flags and refcount field.

Signed-off-by: Antonio Quartulli <ordex@autistici.org>
---
 types.h |    6 +++---
 1 files changed, 3 insertions(+), 3 deletions(-)

diff --git a/types.h b/types.h
index 25bd1db..b32ae5a 100644
--- a/types.h
+++ b/types.h
@@ -223,20 +223,20 @@ struct socket_packet {
 
 struct tt_local_entry {
 	uint8_t addr[ETH_ALEN];
-	unsigned long last_seen;
 	uint16_t flags;
 	atomic_t refcount;
+	unsigned long last_seen;
 	struct rcu_head rcu;
 	struct hlist_node hash_entry;
 };
 
 struct tt_global_entry {
 	uint8_t addr[ETH_ALEN];
+	uint16_t flags; /* only TT_GLOBAL_ROAM is used */
+	atomic_t refcount;
 	struct orig_node *orig_node;
 	uint8_t ttvn;
-	uint16_t flags; /* only TT_GLOBAL_ROAM is used */
 	unsigned long roam_at; /* time at which TT_GLOBAL_ROAM was set */
-	atomic_t refcount;
 	struct rcu_head rcu;
 	struct hlist_node hash_entry; /* entry in the global table */
 };
-- 
1.7.3.4

[B.A.T.M.A.N.] [PATCH 2/6] batman-adv: unify tt_local/global_free_ref functions

[Antonio Quartulli]

Thanks to the unification of the refcount field position inside the
tt_local/global structures, it is now possible to use
tt_local_entry_free_ref() for both the structures

Signed-off-by: Antonio Quartulli <ordex@autistici.org>
---
 translation-table.c |   25 ++++++++++---------------
 1 files changed, 10 insertions(+), 15 deletions(-)

diff --git a/translation-table.c b/translation-table.c
index 06d361d..0f5219e 100644
--- a/translation-table.c
+++ b/translation-table.c
@@ -131,18 +131,13 @@ static bool is_out_of_time(unsigned long starting_time, unsigned long timeout)
 	return time_after(jiffies, deadline);
 }
 
-static void tt_local_entry_free_ref(struct tt_local_entry *tt_local_entry)
+static void tt_local_entry_free_ref(void *data_ptr)
 {
+	struct tt_local_entry *tt_local_entry = data_ptr;
 	if (atomic_dec_and_test(&tt_local_entry->refcount))
 		kfree_rcu(tt_local_entry, rcu);
 }
 
-static void tt_global_entry_free_ref(struct tt_global_entry *tt_global_entry)
-{
-	if (atomic_dec_and_test(&tt_global_entry->refcount))
-		kfree_rcu(tt_global_entry, rcu);
-}
-
 static void tt_local_event(struct bat_priv *bat_priv, const uint8_t *addr,
 			   uint8_t flags)
 {
@@ -236,7 +231,7 @@ out:
 	if (tt_local_entry)
 		tt_local_entry_free_ref(tt_local_entry);
 	if (tt_global_entry)
-		tt_global_entry_free_ref(tt_global_entry);
+		tt_local_entry_free_ref(tt_global_entry);
 }
 
 int tt_changes_fill_buffer(struct bat_priv *bat_priv,
@@ -544,7 +539,7 @@ int tt_global_add(struct bat_priv *bat_priv, struct orig_node *orig_node,
 	ret = 1;
 out:
 	if (tt_global_entry)
-		tt_global_entry_free_ref(tt_global_entry);
+		tt_local_entry_free_ref(tt_global_entry);
 	return ret;
 }
 
@@ -647,7 +642,7 @@ static void _tt_global_del(struct bat_priv *bat_priv,
 		    tt_global_entry->addr);
 out:
 	if (tt_global_entry)
-		tt_global_entry_free_ref(tt_global_entry);
+		tt_local_entry_free_ref(tt_global_entry);
 }
 
 void tt_global_del(struct bat_priv *bat_priv,
@@ -670,7 +665,7 @@ void tt_global_del(struct bat_priv *bat_priv,
 	}
 out:
 	if (tt_global_entry)
-		tt_global_entry_free_ref(tt_global_entry);
+		tt_local_entry_free_ref(tt_global_entry);
 }
 
 void tt_global_del_orig(struct bat_priv *bat_priv,
@@ -697,7 +692,7 @@ void tt_global_del_orig(struct bat_priv *bat_priv,
 					tt_global_entry->addr,
 					tt_global_entry->orig_node->orig);
 				hlist_del_rcu(node);
-				tt_global_entry_free_ref(tt_global_entry);
+				tt_local_entry_free_ref(tt_global_entry);
 			}
 		}
 		spin_unlock_bh(list_lock);
@@ -732,7 +727,7 @@ static void tt_global_roam_purge(struct bat_priv *bat_priv)
 				tt_global_entry->addr);
 			atomic_dec(&tt_global_entry->orig_node->tt_size);
 			hlist_del_rcu(node);
-			tt_global_entry_free_ref(tt_global_entry);
+			tt_local_entry_free_ref(tt_global_entry);
 		}
 		spin_unlock_bh(list_lock);
 	}
@@ -761,7 +756,7 @@ static void tt_global_table_free(struct bat_priv *bat_priv)
 		hlist_for_each_entry_safe(tt_global_entry, node, node_tmp,
 					  head, hash_entry) {
 			hlist_del_rcu(node);
-			tt_global_entry_free_ref(tt_global_entry);
+			tt_local_entry_free_ref(tt_global_entry);
 		}
 		spin_unlock_bh(list_lock);
 	}
@@ -788,7 +783,7 @@ struct orig_node *transtable_search(struct bat_priv *bat_priv,
 	orig_node = tt_global_entry->orig_node;
 
 free_tt:
-	tt_global_entry_free_ref(tt_global_entry);
+	tt_local_entry_free_ref(tt_global_entry);
 out:
 	return orig_node;
 }
-- 
1.7.3.4

[B.A.T.M.A.N.] [PATCH 3/6] batman-adv: full table response must not contain not yet announced clients

[Antonio Quartulli]

To keep transtable consistency among all the nodes, an originator must
not send not yet announced clients within a full table tt_response.

Signed-off-by: Antonio Quartulli <ordex@autistici.org>
---
 translation-table.c |   18 +++++++++++++++++-
 1 files changed, 17 insertions(+), 1 deletions(-)

diff --git a/translation-table.c b/translation-table.c
index 0f5219e..5570e58 100644
--- a/translation-table.c
+++ b/translation-table.c
@@ -210,6 +210,11 @@ void tt_local_add(struct net_device *soft_iface, const uint8_t *addr)
 
 	tt_local_event(bat_priv, addr, tt_local_entry->flags);
 
+	/* The local entry has to be marked as ROAMING to avoid to send it in
+	 * a full table response going out before the next ttvn increment
+	 * (consistency check) */
+	tt_local_entry->flags |= TT_CLIENT_ROAM;
+
 	hash_add(bat_priv->tt_local_hash, compare_ltt, choose_orig,
 		 tt_local_entry, &tt_local_entry->hash_entry);
 
@@ -930,6 +935,16 @@ unlock:
 	return tt_req_node;
 }
 
+/* data_ptr is useless here, but has to be kept to respect the prototype */
+static int tt_local_valid_entry(const void *entry_ptr, const void *data_ptr)
+{
+	const struct tt_local_entry *tt_local_entry = entry_ptr;
+
+	if (tt_local_entry->flags & TT_CLIENT_ROAM)
+		return 0;
+	return 1;
+}
+
 static int tt_global_valid_entry(const void *entry_ptr, const void *data_ptr)
 {
 	const struct tt_global_entry *tt_global_entry = entry_ptr;
@@ -1270,7 +1285,8 @@ static bool send_my_tt_response(struct bat_priv *bat_priv,
 
 		skb = tt_response_fill_table(tt_len, ttvn,
 					     bat_priv->tt_local_hash,
-					     primary_if, NULL, NULL);
+					     primary_if, tt_local_valid_entry,
+					     NULL);
 		if (!skb)
 			goto out;
 
-- 
1.7.3.4

[B.A.T.M.A.N.] [PATCH 4/6] batman-adv: mark local entry as PENDING in case of deletion

[Antonio Quartulli]

In case of deletion of a local entry, it has to be merked as "pending to
be removed" but has to be kept in the table in order to send it within a
full table response issued before the next ttvn increment.

Signed-off-by: Antonio Quartulli <ordex@autistici.org>
---
 packet.h            |    3 ++-
 translation-table.c |   13 +++++++++----
 2 files changed, 11 insertions(+), 5 deletions(-)

diff --git a/packet.h b/packet.h
index 590e4a6..87b371d 100644
--- a/packet.h
+++ b/packet.h
@@ -84,7 +84,8 @@ enum tt_query_flags {
 enum tt_client_flags {
 	TT_CLIENT_DEL     = 1 << 0,
 	TT_CLIENT_ROAM    = 1 << 1,
-	TT_CLIENT_NOPURGE = 1 << 8
+	TT_CLIENT_NOPURGE = 1 << 8,
+	TT_CLIENT_PENDING = 1 << 9
 };
 
 struct batman_packet {
diff --git a/translation-table.c b/translation-table.c
index 5570e58..cf26ee3 100644
--- a/translation-table.c
+++ b/translation-table.c
@@ -386,10 +386,11 @@ void tt_local_remove(struct bat_priv *bat_priv, const uint8_t *addr,
 	tt_local_event(bat_priv, tt_local_entry->addr,
 		       tt_local_entry->flags | TT_CLIENT_DEL |
 		       (roaming ? TT_CLIENT_ROAM : NO_FLAGS));
-	tt_local_del(bat_priv, tt_local_entry, message);
-out:
-	if (tt_local_entry)
-		tt_local_entry_free_ref(tt_local_entry);
+
+	/* The local client has to be merked as "pending to be removed" but has
+	 * to be kept in the table in order to send it in an full tables
+	 * response issued before the net ttvn increment (consistency check) */
+	tt_local_entry->flags |= TT_CLIENT_PENDING;
 }
 
 static void tt_local_purge(struct bat_priv *bat_priv)
@@ -1411,6 +1412,10 @@ bool is_my_client(struct bat_priv *bat_priv, const uint8_t *addr)
 	tt_local_entry = tt_local_hash_find(bat_priv, addr);
 	if (!tt_local_entry)
 		goto out;
+	/* Check if the client has been logically deleted (but is kept for
+	 * consistency purpose) */
+	if (tt_local_entry->flags & TT_CLIENT_PENDING)
+		goto out;
 	ret = true;
 out:
 	if (tt_local_entry)
-- 
1.7.3.4

[B.A.T.M.A.N.] [PATCH 5/6] batman-adv: commit changes and clean the transtable on ttvn increment

[Antonio Quartulli]

On ttvn increment all the collected changes have to be commited:
- local clients marked with TT_CLIENT_ROAM have to be unmarked.
- local clients marked with TT_CLIENT_PENDING have to be deleted.

Signed-off-by: Antonio Quartulli <ordex@autistici.org>
---
 send.c              |    4 +--
 translation-table.c |   80 ++++++++++++++++++++++++++++++++++++++++----------
 translation-table.h |    1 +
 3 files changed, 66 insertions(+), 19 deletions(-)

diff --git a/send.c b/send.c
index 4b8e11b..6071599 100644
--- a/send.c
+++ b/send.c
@@ -310,9 +310,7 @@ void schedule_own_packet(struct hard_iface *hard_iface)
 		/* if at least one change happened */
 		if (atomic_read(&bat_priv->tt_local_changes) > 0) {
 			prepare_packet_buffer(bat_priv, hard_iface);
-			/* Increment the TTVN only once per OGM interval */
-			atomic_inc(&bat_priv->ttvn);
-			bat_priv->tt_poss_change = false;
+			tt_commit_changes(bat_priv);
 		}
 
 		/* if the changes have been sent enough times */
diff --git a/translation-table.c b/translation-table.c
index cf26ee3..fb48f04 100644
--- a/translation-table.c
+++ b/translation-table.c
@@ -358,21 +358,6 @@ out:
 	return ret;
 }
 
-static void tt_local_del(struct bat_priv *bat_priv,
-			 struct tt_local_entry *tt_local_entry,
-			 const char *message)
-{
-	bat_dbg(DBG_TT, bat_priv, "Deleting local tt entry (%pM): %s\n",
-		tt_local_entry->addr, message);
-
-	atomic_dec(&bat_priv->num_local_tt);
-
-	hash_remove(bat_priv->tt_local_hash, compare_ltt, choose_orig,
-		    tt_local_entry->addr);
-
-	tt_local_entry_free_ref(tt_local_entry);
-}
-
 void tt_local_remove(struct bat_priv *bat_priv, const uint8_t *addr,
 		     const char *message, bool roaming)
 {
@@ -381,7 +366,7 @@ void tt_local_remove(struct bat_priv *bat_priv, const uint8_t *addr,
 	tt_local_entry = tt_local_hash_find(bat_priv, addr);
 
 	if (!tt_local_entry)
-		goto out;
+		return;
 
 	tt_local_event(bat_priv, tt_local_entry->addr,
 		       tt_local_entry->flags | TT_CLIENT_DEL |
@@ -1636,3 +1621,66 @@ void tt_free(struct bat_priv *bat_priv)
 
 	kfree(bat_priv->tt_buff);
 }
+
+/* This function will purge out the specified flags from all the entries in
+ * the given hash table */
+static void tt_purge_flags(struct hashtable_t *hash, uint16_t flags)
+{
+	int i;
+	struct hlist_head *head;
+	struct hlist_node *node;
+	struct tt_local_entry *tt_local_entry;
+
+	for (i = 0; i < hash->size; i++) {
+		head = &hash->table[i];
+
+		rcu_read_lock();
+		hlist_for_each_entry_rcu(tt_local_entry, node,
+					 head, hash_entry) {
+			tt_local_entry->flags &= ~flags;
+		}
+		rcu_read_unlock();
+	}
+
+}
+
+static void tt_purge_local_pending_clients(struct bat_priv *bat_priv)
+{
+	struct hashtable_t *hash = bat_priv->tt_local_hash;
+	struct tt_local_entry *tt_local_entry;
+	struct hlist_node *node, *node_tmp;
+	struct hlist_head *head;
+	spinlock_t *list_lock; /* protects write access to the hash lists */
+	int i;
+
+	for (i = 0; i < hash->size; i++) {
+		head = &hash->table[i];
+		list_lock = &hash->list_locks[i];
+
+		spin_lock_bh(list_lock);
+		hlist_for_each_entry_safe(tt_local_entry, node, node_tmp,
+					  head, hash_entry) {
+			if (!(tt_local_entry->flags & TT_CLIENT_PENDING))
+				continue;
+
+			bat_dbg(DBG_TT, bat_priv, "Deleting local tt entry "
+				"(%pM): pending\n", tt_local_entry->addr);
+
+			atomic_dec(&bat_priv->num_local_tt);
+			hlist_del_rcu(node);
+			tt_local_entry_free_ref(tt_local_entry);
+		}
+		spin_unlock_bh(list_lock);
+	}
+
+}
+
+void tt_commit_changes(struct bat_priv *bat_priv)
+{
+	tt_purge_flags(bat_priv->tt_local_hash, TT_CLIENT_ROAM);
+	tt_purge_local_pending_clients(bat_priv);
+
+	/* Increment the TTVN only once per OGM interval */
+	atomic_inc(&bat_priv->ttvn);
+	bat_priv->tt_poss_change = false;
+}
diff --git a/translation-table.h b/translation-table.h
index 460e583..d4122cb 100644
--- a/translation-table.h
+++ b/translation-table.h
@@ -61,5 +61,6 @@ void handle_tt_response(struct bat_priv *bat_priv,
 			struct tt_query_packet *tt_response);
 void send_roam_adv(struct bat_priv *bat_priv, uint8_t *client,
 		   struct orig_node *orig_node);
+void tt_commit_changes(struct bat_priv *bat_priv);
 
 #endif /* _NET_BATMAN_ADV_TRANSLATION_TABLE_H_ */
-- 
1.7.3.4

[B.A.T.M.A.N.] [PATCH 6/6] batman-adv: global entries are marked as PENDING in case of roaming

[Antonio Quartulli]

To keep consistency of other originator tables, new clients detected as
roamed, are kept in the global table but are marked as TT_CLIENT_PENDING
as well. They are purged as well once the new ttvn is received by the
corresponding originator. Moreover they need to be considered as removed
in case of global transtable lookup.

Signed-off-by: Antonio Quartulli <ordex@autistici.org>
---
 translation-table.c |   23 ++++++++++++++++-------
 1 files changed, 16 insertions(+), 7 deletions(-)

diff --git a/translation-table.c b/translation-table.c
index fb48f04..6efa72c 100644
--- a/translation-table.c
+++ b/translation-table.c
@@ -227,8 +227,9 @@ void tt_local_add(struct net_device *soft_iface, const uint8_t *addr)
 	if (tt_global_entry) {
 		/* This node is probably going to update its tt table */
 		tt_global_entry->orig_node->tt_poss_change = true;
-		_tt_global_del(bat_priv, tt_global_entry,
-			       "local tt received");
+		/* The global entry has to be marked as PENDING and has to be
+		 * kept for consistency purpose */
+		tt_global_entry->flags |= TT_CLIENT_PENDING;
 		send_roam_adv(bat_priv, tt_global_entry->addr,
 			      tt_global_entry->orig_node);
 	}
@@ -771,6 +772,11 @@ struct orig_node *transtable_search(struct bat_priv *bat_priv,
 	if (!atomic_inc_not_zero(&tt_global_entry->orig_node->refcount))
 		goto free_tt;
 
+	/* A global client marked as PENDING has already moved from that
+	 * originator */
+	if (tt_global_entry->flags & TT_CLIENT_PENDING)
+		goto free_tt;
+
 	orig_node = tt_global_entry->orig_node;
 
 free_tt:
@@ -1644,9 +1650,10 @@ static void tt_purge_flags(struct hashtable_t *hash, uint16_t flags)
 
 }
 
-static void tt_purge_local_pending_clients(struct bat_priv *bat_priv)
+static void tt_purge_pending_clients(struct bat_priv *bat_priv,
+				     struct hashtable_t *hash,
+				     const char *table_name)
 {
-	struct hashtable_t *hash = bat_priv->tt_local_hash;
 	struct tt_local_entry *tt_local_entry;
 	struct hlist_node *node, *node_tmp;
 	struct hlist_head *head;
@@ -1663,8 +1670,9 @@ static void tt_purge_local_pending_clients(struct bat_priv *bat_priv)
 			if (!(tt_local_entry->flags & TT_CLIENT_PENDING))
 				continue;
 
-			bat_dbg(DBG_TT, bat_priv, "Deleting local tt entry "
-				"(%pM): pending\n", tt_local_entry->addr);
+			bat_dbg(DBG_TT, bat_priv, "Deleting %s tt entry "
+				"(%pM): pending\n", tt_local_entry->addr,
+				table_name);
 
 			atomic_dec(&bat_priv->num_local_tt);
 			hlist_del_rcu(node);
@@ -1678,7 +1686,8 @@ static void tt_purge_local_pending_clients(struct bat_priv *bat_priv)
 void tt_commit_changes(struct bat_priv *bat_priv)
 {
 	tt_purge_flags(bat_priv->tt_local_hash, TT_CLIENT_ROAM);
-	tt_purge_local_pending_clients(bat_priv);
+	tt_purge_pending_clients(bat_priv, bat_priv->tt_local_hash, "local");
+	tt_purge_pending_clients(bat_priv, bat_priv->tt_global_hash, "global");
 
 	/* Increment the TTVN only once per OGM interval */
 	atomic_inc(&bat_priv->ttvn);
-- 
1.7.3.4

Re: [B.A.T.M.A.N.] [PATCH 1/6] batman-adv: unify the three starting fields of the tt_local/global_entry structures

[Sven Eckelmann]

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

On Tuesday 05 July 2011 17:23:00 Antonio Quartulli wrote:
> Now the three starting fields of the tt_local/global_entry structures are
> unified. This allows to write generalised functions that operate on the
> flags and refcount field.
> 
> Signed-off-by: Antonio Quartulli <ordex@autistici.org>
> ---


Ehrm, this is wrong (or at least undefined behaviour). Please read C99 6.5.2.3 
point 5

Kind regards,
	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 1/6] batman-adv: unify the three starting fields of the tt_local/global_entry structures

[Sven Eckelmann]

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

On Wednesday 06 July 2011 09:31:11 Sven Eckelmann wrote:
> On Tuesday 05 July 2011 17:23:00 Antonio Quartulli wrote:
> > Now the three starting fields of the tt_local/global_entry structures
> > are
> > unified. This allows to write generalised functions that operate on the
> > flags and refcount field.
> > 
> > Signed-off-by: Antonio Quartulli <ordex@autistici.org>
> > ---
> 
> Ehrm, this is wrong (or at least undefined behaviour). Please read C99
> 6.5.2.3 point 5

Found an extreme nice example [1] for you. Please read it together with the 
C99 paragraph mentioned above.

Kind regards,
	Sven

[1] 
http://coding.derkeiler.com/Archive/C_CPP/comp.lang.c/2007-05/msg03192.html

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

[B.A.T.M.A.N.] [PATCHv2 0/3] Solve consistency issues in TT code

[Antonio Quartulli]

Hello all,

this is the second version of the TT consistency fix patchset.

The beautification patches have been removed as they were probably introducing
a few new problems (thanks Sven for pointing me to the C99 documentation) while
the remaining 4 patches have been merged in a more logical way.

Here is a little overview:
- 1/3 solves a 'little' bug found today.
- 2/3 fixes the way local tables are handled
- 3/3 fixes the roaming phase in order to keep consistency

For more details, please read the commit messages.
Thanks you!

Regards,
	Antonio Quartulli

[B.A.T.M.A.N.] [PATCH 1/3] batman-adv: initialise last_ttvn and tt_crc for the orig_node structure

[Antonio Quartulli]

The last_ttvn and tt_crc fields of the orig_node structure were not
initialised causing an immediate TT_REQ/RES dialogue even if not needed.

Signed-off-by: Antonio Quartulli <ordex@autistici.org>
---
 originator.c |    2 ++
 1 files changed, 2 insertions(+), 0 deletions(-)

diff --git a/originator.c b/originator.c
index 338b3c5..4aa115f 100644
--- a/originator.c
+++ b/originator.c
@@ -223,6 +223,8 @@ struct orig_node *get_orig_node(struct bat_priv *bat_priv, const uint8_t *addr)
 	orig_node->bat_priv = bat_priv;
 	memcpy(orig_node->orig, addr, ETH_ALEN);
 	orig_node->router = NULL;
+	orig_node->tt_crc = 0;
+	atomic_set(&orig_node->last_ttvn, 0);
 	orig_node->tt_buff = NULL;
 	orig_node->tt_buff_len = 0;
 	atomic_set(&orig_node->tt_size, 0);
-- 
1.7.3.4

[B.A.T.M.A.N.] [PATCH 2/3] batman-adv: keep local table consistency for further TT_RESPONSE

[Antonio Quartulli]

To keep transtable consistency among all the nodes, an originator must
not send not yet announced clients within a full table TT_RESPONSE.
Instead, deleted client have to be kept in the table in order to be sent
within an immediate TT_RESPONSE. In this way all the nodes in the
network will always provide the same response for the same request.

All the modification are committed at the next ttvn increment event.

Signed-off-by: Antonio Quartulli <ordex@autistici.org>
---
 packet.h            |    4 +-
 send.c              |    4 +-
 translation-table.c |  145 ++++++++++++++++++++++++++++++++++++++++----------
 translation-table.h |    1 +
 4 files changed, 121 insertions(+), 33 deletions(-)

diff --git a/packet.h b/packet.h
index 590e4a6..b76b4be 100644
--- a/packet.h
+++ b/packet.h
@@ -84,7 +84,9 @@ enum tt_query_flags {
 enum tt_client_flags {
 	TT_CLIENT_DEL     = 1 << 0,
 	TT_CLIENT_ROAM    = 1 << 1,
-	TT_CLIENT_NOPURGE = 1 << 8
+	TT_CLIENT_NOPURGE = 1 << 8,
+	TT_CLIENT_NEW     = 1 << 9,
+	TT_CLIENT_PENDING = 1 << 10
 };
 
 struct batman_packet {
diff --git a/send.c b/send.c
index 4b8e11b..58d1447 100644
--- a/send.c
+++ b/send.c
@@ -309,10 +309,8 @@ void schedule_own_packet(struct hard_iface *hard_iface)
 	if (hard_iface == primary_if) {
 		/* if at least one change happened */
 		if (atomic_read(&bat_priv->tt_local_changes) > 0) {
+			tt_commit_changes(bat_priv);
 			prepare_packet_buffer(bat_priv, hard_iface);
-			/* Increment the TTVN only once per OGM interval */
-			atomic_inc(&bat_priv->ttvn);
-			bat_priv->tt_poss_change = false;
 		}
 
 		/* if the changes have been sent enough times */
diff --git a/translation-table.c b/translation-table.c
index 06d361d..3267ca2 100644
--- a/translation-table.c
+++ b/translation-table.c
@@ -215,11 +215,14 @@ void tt_local_add(struct net_device *soft_iface, const uint8_t *addr)
 
 	tt_local_event(bat_priv, addr, tt_local_entry->flags);
 
+	/* The local entry has to be marked as ROAMING to avoid to send it in
+	 * a full table response going out before the next ttvn increment
+	 * (consistency check) */
+	tt_local_entry->flags |= TT_CLIENT_NEW;
+
 	hash_add(bat_priv->tt_local_hash, compare_ltt, choose_orig,
 		 tt_local_entry, &tt_local_entry->hash_entry);
 
-	atomic_inc(&bat_priv->num_local_tt);
-
 	/* remove address from global hash if present */
 	tt_global_entry = tt_global_hash_find(bat_priv, addr);
 
@@ -358,19 +361,17 @@ out:
 	return ret;
 }
 
-static void tt_local_del(struct bat_priv *bat_priv,
-			 struct tt_local_entry *tt_local_entry,
-			 const char *message)
+void tt_local_set_pending(struct bat_priv *bat_priv,
+			  struct tt_local_entry *tt_local_entry,
+			  uint16_t flags)
 {
-	bat_dbg(DBG_TT, bat_priv, "Deleting local tt entry (%pM): %s\n",
-		tt_local_entry->addr, message);
-
-	atomic_dec(&bat_priv->num_local_tt);
-
-	hash_remove(bat_priv->tt_local_hash, compare_ltt, choose_orig,
-		    tt_local_entry->addr);
+	tt_local_event(bat_priv, tt_local_entry->addr,
+		       tt_local_entry->flags | flags);
 
-	tt_local_entry_free_ref(tt_local_entry);
+	/* The local client has to be merked as "pending to be removed" but has
+	 * to be kept in the table in order to send it in an full tables
+	 * response issued before the net ttvn increment (consistency check) */
+	tt_local_entry->flags |= TT_CLIENT_PENDING;
 }
 
 void tt_local_remove(struct bat_priv *bat_priv, const uint8_t *addr,
@@ -381,15 +382,12 @@ void tt_local_remove(struct bat_priv *bat_priv, const uint8_t *addr,
 	tt_local_entry = tt_local_hash_find(bat_priv, addr);
 
 	if (!tt_local_entry)
-		goto out;
+		return;
+	tt_local_set_pending(bat_priv, tt_local_entry, TT_CLIENT_DEL |
+			     (roaming ? TT_CLIENT_ROAM : NO_FLAGS));
 
-	tt_local_event(bat_priv, tt_local_entry->addr,
-		       tt_local_entry->flags | TT_CLIENT_DEL |
-		       (roaming ? TT_CLIENT_ROAM : NO_FLAGS));
-	tt_local_del(bat_priv, tt_local_entry, message);
-out:
-	if (tt_local_entry)
-		tt_local_entry_free_ref(tt_local_entry);
+	bat_dbg(DBG_TT, bat_priv, "Local tt entry (%pM) pending to be removed: "
+		"%s\n", tt_local_entry->addr, message);
 }
 
 static void tt_local_purge(struct bat_priv *bat_priv)
@@ -415,14 +413,11 @@ static void tt_local_purge(struct bat_priv *bat_priv)
 					    TT_LOCAL_TIMEOUT * 1000))
 				continue;
 
-			tt_local_event(bat_priv, tt_local_entry->addr,
-				       tt_local_entry->flags | TT_CLIENT_DEL);
-			atomic_dec(&bat_priv->num_local_tt);
-			bat_dbg(DBG_TT, bat_priv, "Deleting local "
-				"tt entry (%pM): timed out\n",
+			tt_local_set_pending(bat_priv, tt_local_entry,
+					     TT_CLIENT_DEL);
+			bat_dbg(DBG_TT, bat_priv, "Local tt entry (%pM) "
+				"pending to be removed: timed out\n",
 				tt_local_entry->addr);
-			hlist_del_rcu(node);
-			tt_local_entry_free_ref(tt_local_entry);
 		}
 		spin_unlock_bh(list_lock);
 	}
@@ -846,6 +841,10 @@ uint16_t tt_local_crc(struct bat_priv *bat_priv)
 		rcu_read_lock();
 		hlist_for_each_entry_rcu(tt_local_entry, node,
 					 head, hash_entry) {
+			/* not yet committed clients have not to be taken into
+			 * account while computing the CRC */
+			if (tt_local_entry->flags & TT_CLIENT_NEW)
+				continue;
 			total_one = 0;
 			for (j = 0; j < ETH_ALEN; j++)
 				total_one = crc16_byte(total_one,
@@ -935,6 +934,16 @@ unlock:
 	return tt_req_node;
 }
 
+/* data_ptr is useless here, but has to be kept to respect the prototype */
+static int tt_local_valid_entry(const void *entry_ptr, const void *data_ptr)
+{
+	const struct tt_local_entry *tt_local_entry = entry_ptr;
+
+	if (tt_local_entry->flags & TT_CLIENT_NEW)
+		return 0;
+	return 1;
+}
+
 static int tt_global_valid_entry(const void *entry_ptr, const void *data_ptr)
 {
 	const struct tt_global_entry *tt_global_entry = entry_ptr;
@@ -1275,7 +1284,8 @@ static bool send_my_tt_response(struct bat_priv *bat_priv,
 
 		skb = tt_response_fill_table(tt_len, ttvn,
 					     bat_priv->tt_local_hash,
-					     primary_if, NULL, NULL);
+					     primary_if, tt_local_valid_entry,
+					     NULL);
 		if (!skb)
 			goto out;
 
@@ -1400,6 +1410,10 @@ bool is_my_client(struct bat_priv *bat_priv, const uint8_t *addr)
 	tt_local_entry = tt_local_hash_find(bat_priv, addr);
 	if (!tt_local_entry)
 		goto out;
+	/* Check if the client has been logically deleted (but is kept for
+	 * consistency purpose) */
+	if (tt_local_entry->flags & TT_CLIENT_PENDING)
+		goto out;
 	ret = true;
 out:
 	if (tt_local_entry)
@@ -1620,3 +1634,76 @@ void tt_free(struct bat_priv *bat_priv)
 
 	kfree(bat_priv->tt_buff);
 }
+
+/* This function will reset the specified flags from all the entries in
+ * the given hash table and will increment num_local_tt for each involved
+ * entry */
+static void tt_local_reset_flags(struct bat_priv *bat_priv, uint16_t flags)
+{
+	int i;
+	struct hashtable_t *hash = bat_priv->tt_local_hash;
+	struct hlist_head *head;
+	struct hlist_node *node;
+	struct tt_local_entry *tt_local_entry;
+
+	if (!hash)
+		return;
+
+	for (i = 0; i < hash->size; i++) {
+		head = &hash->table[i];
+
+		rcu_read_lock();
+		hlist_for_each_entry_rcu(tt_local_entry, node,
+					 head, hash_entry) {
+			tt_local_entry->flags &= ~flags;
+			atomic_inc(&bat_priv->num_local_tt);
+		}
+		rcu_read_unlock();
+	}
+
+}
+
+/* Purge out all the tt local entries marked with TT_CLIENT_PENDING */
+static void tt_local_purge_pending_clients(struct bat_priv *bat_priv)
+{
+	struct hashtable_t *hash = bat_priv->tt_local_hash;
+	struct tt_local_entry *tt_local_entry;
+	struct hlist_node *node, *node_tmp;
+	struct hlist_head *head;
+	spinlock_t *list_lock; /* protects write access to the hash lists */
+	int i;
+
+	if (!hash)
+		return;
+
+	for (i = 0; i < hash->size; i++) {
+		head = &hash->table[i];
+		list_lock = &hash->list_locks[i];
+
+		spin_lock_bh(list_lock);
+		hlist_for_each_entry_safe(tt_local_entry, node, node_tmp,
+					  head, hash_entry) {
+			if (!(tt_local_entry->flags & TT_CLIENT_PENDING))
+				continue;
+
+			bat_dbg(DBG_TT, bat_priv, "Deleting local tt entry "
+				"(%pM): pending\n", tt_local_entry->addr);
+
+			atomic_dec(&bat_priv->num_local_tt);
+			hlist_del_rcu(node);
+			tt_local_entry_free_ref(tt_local_entry);
+		}
+		spin_unlock_bh(list_lock);
+	}
+
+}
+
+void tt_commit_changes(struct bat_priv *bat_priv)
+{
+	tt_local_reset_flags(bat_priv, TT_CLIENT_NEW);
+	tt_local_purge_pending_clients(bat_priv);
+
+	/* Increment the TTVN only once per OGM interval */
+	atomic_inc(&bat_priv->ttvn);
+	bat_priv->tt_poss_change = false;
+}
diff --git a/translation-table.h b/translation-table.h
index 460e583..d4122cb 100644
--- a/translation-table.h
+++ b/translation-table.h
@@ -61,5 +61,6 @@ void handle_tt_response(struct bat_priv *bat_priv,
 			struct tt_query_packet *tt_response);
 void send_roam_adv(struct bat_priv *bat_priv, uint8_t *client,
 		   struct orig_node *orig_node);
+void tt_commit_changes(struct bat_priv *bat_priv);
 
 #endif /* _NET_BATMAN_ADV_TRANSLATION_TABLE_H_ */
-- 
1.7.3.4

[B.A.T.M.A.N.] [PATCH 3/3] batman-adv: keep global table consistency in case of roaming

[Antonio Quartulli]

To keep consistency of other originator tables, new clients detected as
roamed, are kept in the global table but are marked as TT_CLIENT_PENDING
They are purged only when the new ttvn is received by the corresponding
originator. Moreover they need to be considered as removed in case of global
transtable lookup.

Signed-off-by: Antonio Quartulli <ordex@autistici.org>
---
 translation-table.c |   10 ++++++++--
 1 files changed, 8 insertions(+), 2 deletions(-)

diff --git a/translation-table.c b/translation-table.c
index 3267ca2..dfab867 100644
--- a/translation-table.c
+++ b/translation-table.c
@@ -230,8 +230,9 @@ void tt_local_add(struct net_device *soft_iface, const uint8_t *addr)
 	if (tt_global_entry) {
 		/* This node is probably going to update its tt table */
 		tt_global_entry->orig_node->tt_poss_change = true;
-		_tt_global_del(bat_priv, tt_global_entry,
-			       "local tt received");
+		/* The global entry has to be marked as PENDING and has to be
+		 * kept for consistency purpose */
+		tt_global_entry->flags |= TT_CLIENT_PENDING;
 		send_roam_adv(bat_priv, tt_global_entry->addr,
 			      tt_global_entry->orig_node);
 	}
@@ -780,6 +781,11 @@ struct orig_node *transtable_search(struct bat_priv *bat_priv,
 	if (!atomic_inc_not_zero(&tt_global_entry->orig_node->refcount))
 		goto free_tt;
 
+	/* A global client marked as PENDING has already moved from that
+	 * originator */
+	if (tt_global_entry->flags & TT_CLIENT_PENDING)
+		goto free_tt;
+
 	orig_node = tt_global_entry->orig_node;
 
 free_tt:
-- 
1.7.3.4