[B.A.T.M.A.N.] [RFC 17/23] batman-adv: ELP - implement dead neigh node detection

Antonio Quartulli
2014-02-11T12:48:17Z

From: Antonio Quartulli <antonio@open-mesh.com>

Improve the neighbour purging routine to timely detect when
a neighbour is not sending data anymore without waiting for
a real timeout. This detection system can be used by the
B.A.T.M.A.N. V routing algorithm to trigger an on-demand
route reconstruction.

Signed-off-by: Antonio Quartulli <antonio@open-mesh.com>
---
bat_v.c | 7 +++++
bat_v_elp.c | 91 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++---
bat_v_elp.h | 2 ++
types.h | 2 ++
4 files changed, 98 insertions(+), 4 deletions(-)

diff --git a/bat_v.c b/bat_v.c
index 3aa42ec..5681d19 100644
--- a/bat_v.c
+++ b/bat_v.c
@@ -75,14 +75,21 @@ static struct batadv_algo_ops batadv_batman_v __read_mostly = {

int batadv_v_mesh_init(struct batadv_priv *bat_priv)
{
+ int r;
+
atomic_set(&bat_priv->bat_v.base_throughput,
BATADV_DEFAULT_BASE_THROUGHPUT);

+ r = batadv_v_elp_init(bat_priv);
+ if (r)
+ return r;
+
return batadv_v_ogm_init(bat_priv);
}

void batadv_v_mesh_free(struct batadv_priv *bat_priv)
{
+ batadv_v_elp_free(bat_priv);
batadv_v_ogm_free(bat_priv);
}

diff --git a/bat_v_elp.c b/bat_v_elp.c
index 31190af..763113e 100644
--- a/bat_v_elp.c
+++ b/bat_v_elp.c
@@ -25,6 +25,7 @@
#include "send.h"
#include "bat_algo.h"
#include "bat_v_elp.h"
+#include "bat_v_ogm.h"
#include "originator.h"
#include "routing.h"
#include "soft-interface.h"
@@ -186,30 +187,55 @@ batadv_v_elp_neigh_get(struct batadv_hard_iface *hard_iface,
* batadv_v_elp_neigh_purge - purge obsolete neighbour nodes
*
* Deletes the ELP neighbour nodes that did not send any ELP message for a
- * pre-defined amount of time.
+ * pre-defined amount of time and returns the minimum ELP interval among all the
+ * remaining neighbours.
*/
-static void batadv_v_elp_neigh_purge(struct batadv_hard_iface *hard_iface)
+static uint32_t batadv_v_elp_neigh_purge(struct batadv_hard_iface *hard_iface)
{
+ struct batadv_priv *bat_priv = netdev_priv(hard_iface->soft_iface);
unsigned long timeout;
struct batadv_elp_neigh_node *neigh;
struct hlist_node *node;
bool has_timed_out;
+ uint32_t tmp_interval, min_interval = UINT_MAX;

spin_lock_bh(&hard_iface->bat_v.neigh_list_lock);
hlist_for_each_entry_safe(neigh, node, &hard_iface->bat_v.neigh_list,
list) {
- timeout = neigh->elp_interval * BATADV_ELP_OUTDATED_MAX;
+ tmp_interval = neigh->elp_interval;
+
+ timeout = tmp_interval * BATADV_ELP_OUTDATED_MAX;
has_timed_out = batadv_has_timed_out(neigh->last_seen, timeout);
+ if (has_timed_out) {
+ /* this neigh is dead! the node could react somehow.
+ * TODO: implement dead node reaction mechanism
+ */
+ batadv_dbg(BATADV_DBG_BATMAN, bat_priv,
+ "Node %pM is dead.\n", neigh->addr);

+ /* this node is not sending ELP packets anymore. Don't
+ * consider it in the minimum ELP interval research
+ */
+ tmp_interval = UINT_MAX;
+ }
+
+ has_timed_out = batadv_has_timed_out(neigh->last_seen,
+ BATADV_PURGE_TIMEOUT);
if ((!has_timed_out) &&
- (hard_iface->if_status == BATADV_IF_ACTIVE))
+ (hard_iface->if_status == BATADV_IF_ACTIVE)) {
+ if (tmp_interval < min_interval)
+ min_interval = tmp_interval;
continue;
+ }

hlist_del_rcu(&neigh->list);
atomic_dec(&hard_iface->bat_v.num_neighbors);
batadv_elp_neigh_node_free_ref(neigh);
+
}
spin_unlock_bh(&hard_iface->bat_v.neigh_list_lock);
+
+ return min_interval;
}

/**
@@ -479,6 +505,7 @@ static void batadv_v_elp_neigh_update(struct batadv_priv *bat_priv,

{
struct batadv_elp_neigh_node *neigh;
+ uint32_t interval;

neigh = batadv_v_elp_neigh_get(if_incoming, neigh_addr);
if (!neigh) {
@@ -490,6 +517,16 @@ static void batadv_v_elp_neigh_update(struct batadv_priv *bat_priv,

neigh->last_seen = jiffies;
neigh->last_recv_seqno = ntohl(elp_packet->seqno);
+ neigh->elp_interval = ntohl(elp_packet->elp_interval);
+
+ interval = atomic_read(&bat_priv->bat_v.neigh_interval);
+ if (neigh->elp_interval >= interval)
+ goto out;
+
+ /* got a shorter elp interval: reschedule the neigh check */
+ atomic_set(&bat_priv->bat_v.neigh_interval, neigh->elp_interval);
+ queue_delayed_work(batadv_event_workqueue, &bat_priv->bat_v.neigh_wq,
+ msecs_to_jiffies(neigh->elp_interval));

out:
if (neigh)
@@ -625,3 +662,49 @@ out:
batadv_hardif_free_ref(primary_if);
return 0;
}
+
+static void batadv_v_elp_check_neigh(struct work_struct *work)
+{
+ struct batadv_priv_bat_v *bat_v;
+ struct batadv_priv *bat_priv;
+ struct batadv_hard_iface *hard_iface;
+ uint32_t tmp_interval, min_interval = UINT_MAX;
+
+ bat_v = container_of(work, struct batadv_priv_bat_v, neigh_wq.work);
+ bat_priv = container_of(bat_v, struct batadv_priv, bat_v);
+
+ list_for_each_entry(hard_iface, &batadv_hardif_list, list) {
+ if (hard_iface->soft_iface != bat_priv->soft_iface)
+ continue;
+
+ tmp_interval = batadv_v_elp_neigh_purge(hard_iface);
+ /* while iterating over all the ELP neighbors, find the smallest
+ * ELP interval to use to schedule the next check
+ */
+ if (tmp_interval < min_interval)
+ min_interval = tmp_interval;
+ }
+
+ /* if there are no more ELP neighbors the work does not need to be
+ * rescheduled
+ */
+ if (min_interval == UINT_MAX)
+ return;
+
+ atomic_set(&bat_priv->bat_v.neigh_interval, min_interval);
+ queue_delayed_work(batadv_event_workqueue, &bat_priv->bat_v.neigh_wq,
+ msecs_to_jiffies(min_interval));
+}
+
+int batadv_v_elp_init(struct batadv_priv *bat_priv)
+{
+ INIT_DELAYED_WORK(&bat_priv->bat_v.neigh_wq, batadv_v_elp_check_neigh);
+ atomic_set(&bat_priv->bat_v.neigh_interval, UINT_MAX);
+
+ return 0;
+}
+
+void batadv_v_elp_free(struct batadv_priv *bat_priv)
+{
+ cancel_delayed_work_sync(&bat_priv->bat_v.neigh_wq);
+}
diff --git a/bat_v_elp.h b/bat_v_elp.h
index 4f34ecb..5dd0568 100644
--- a/bat_v_elp.h
+++ b/bat_v_elp.h
@@ -33,5 +33,7 @@ void batadv_v_elp_primary_iface_set(struct batadv_hard_iface *hard_iface);
int batadv_v_elp_packet_recv(struct sk_buff *skb,
struct batadv_hard_iface *if_incoming);
int batadv_v_elp_seq_print_text(struct seq_file *seq, void *offset);
+int batadv_v_elp_init(struct batadv_priv *bat_priv);
+void batadv_v_elp_free(struct batadv_priv *bat_priv);

#endif /* _NET_BATMAN_ADV_BAT_V_ELP_H_ */
diff --git a/types.h b/types.h
index 6f05d99..2ba27ab 100644
--- a/types.h
+++ b/types.h
@@ -748,6 +748,8 @@ struct batadv_priv_bat_v {
struct delayed_work ogm_wq;
atomic_t ogm_seqno;
atomic_t base_throughput;
+ atomic_t neigh_interval;
+ struct delayed_work neigh_wq;
};

/**
--
1.8.5.3