[B.A.T.M.A.N.] [RFC 04/23] batman-adv: ELP - creating neighbor structures

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

From: Linus Luessing <linus.luessing@web.de>

Initially developed by Linus during a 6 months trainee study
period in Ascom (Switzerland) AG.

Signed-off-by: Linus Luessing <linus.luessing@web.de>
Signed-off-by: Marek Lindner <lindner_marek@yahoo.de>
Signed-off-by: Antonio Quartulli <antonio@open-mesh.com>
---
bat_v.c | 18 +++++-
bat_v_elp.c | 204 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
bat_v_elp.h | 6 ++
main.h | 2 +
types.h | 53 ++++++++++++++++
5 files changed, 281 insertions(+), 2 deletions(-)

diff --git a/bat_v.c b/bat_v.c
index 7247d7f..bed5e00 100644
--- a/bat_v.c
+++ b/bat_v.c
@@ -61,5 +61,21 @@ static struct batadv_algo_ops batadv_batman_v __read_mostly = {

int __init batadv_v_init(void)
{
- return batadv_algo_register(&batadv_batman_v);
+ int ret;
+
+ /* batman v echo location protocol packet */
+ ret = batadv_recv_handler_register(BATADV_ELP,
+ batadv_v_elp_packet_recv);
+ if (ret < 0)
+ goto elp_unregister;
+
+ ret = batadv_algo_register(&batadv_batman_v);
+
+ return ret;
+
+elp_unregister:
+ if (ret < 0)
+ batadv_recv_handler_unregister(BATADV_ELP);
+
+ return ret;
}
diff --git a/bat_v_elp.c b/bat_v_elp.c
index 45b082b..ee4207d 100644
--- a/bat_v_elp.c
+++ b/bat_v_elp.c
@@ -23,6 +23,8 @@
#include "send.h"
#include "bat_algo.h"
#include "bat_v_elp.h"
+#include "originator.h"
+#include "routing.h"

/**
* batadv_v_elp_start_timer - restart timer for ELP periodic work
@@ -40,6 +42,111 @@ static void batadv_v_elp_start_timer(struct batadv_hard_iface *hard_iface)
}

/**
+ * batadv_elp_neigh_node_free_ref - release a ELP neighbour node
+ * @neigh: the neighbour object to release
+ */
+void batadv_elp_neigh_node_free_ref(struct batadv_elp_neigh_node *neigh)
+{
+ if (atomic_dec_and_test(&neigh->refcount))
+ kfree_rcu(neigh, rcu);
+}
+
+/**
+ * batadv_v_elp_neigh_new - create a new ELP neighbour node
+ * @hard_iface: the interface the neighbour is connected to
+ * @neigh_addr: the neighbour interface address
+ * @orig_addr: the neighbour originator address
+ * @seqno: the received sequence number to be used to initialize the object
+ *
+ * Returns a new ELP neighbour node or NULL in case of failure.
+ */
+static struct batadv_elp_neigh_node *
+batadv_v_elp_neigh_new(struct batadv_hard_iface *hard_iface,
+ uint8_t *neigh_addr, uint8_t *orig_addr, uint32_t seqno)
+{
+ struct batadv_elp_neigh_node *neigh;
+
+ neigh = kzalloc(sizeof(*neigh), GFP_ATOMIC);
+ if (!neigh)
+ return NULL;
+
+ memcpy(neigh->orig, orig_addr, ETH_ALEN);
+ memcpy(neigh->addr, neigh_addr, ETH_ALEN);
+ neigh->last_recv_seqno = seqno - 1;
+ neigh->last_seen = jiffies;
+ ewma_init(&neigh->metric, 1024, 8);
+ /* recount initialised to 2 to simplify the caller function */
+ atomic_set(&neigh->refcount, 2);
+
+ spin_lock_bh(&hard_iface->bat_v.neigh_list_lock);
+ hlist_add_head_rcu(&neigh->list, &hard_iface->bat_v.neigh_list);
+ spin_unlock_bh(&hard_iface->bat_v.neigh_list_lock);
+ atomic_inc(&hard_iface->bat_v.num_neighbors);
+
+ return neigh;
+}
+
+/**
+ * batadv_v_elp_neigh_get - retrieve an ELP neighbour node
+ * @hard_iface: the interface this neighbour is connected to
+ * @neigh_addr: the interface address of the neighbour to retrieve
+ *
+ * Returns the ELP neighbour node if found or NULL otherwise.
+ */
+struct batadv_elp_neigh_node *
+batadv_v_elp_neigh_get(struct batadv_hard_iface *hard_iface,
+ uint8_t *neigh_addr)
+{
+ struct batadv_elp_neigh_node *neigh = NULL, *neigh_tmp;
+
+ rcu_read_lock();
+ hlist_for_each_entry_rcu(neigh_tmp,
+ &hard_iface->bat_v.neigh_list, list) {
+ if (!batadv_compare_eth(neigh_tmp->addr, neigh_addr))
+ continue;
+
+ if (!atomic_inc_not_zero(&neigh_tmp->refcount))
+ continue;
+
+ neigh = neigh_tmp;
+ break;
+ }
+ rcu_read_unlock();
+
+ return neigh;
+}
+
+/**
+ * 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.
+ */
+static void batadv_v_elp_neigh_purge(struct batadv_hard_iface *hard_iface)
+{
+ unsigned long timeout;
+ struct batadv_elp_neigh_node *neigh;
+ struct hlist_node *node;
+ bool has_timed_out;
+
+ 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;
+ has_timed_out = batadv_has_timed_out(neigh->last_seen, timeout);
+
+ if ((!has_timed_out) &&
+ (hard_iface->if_status == BATADV_IF_ACTIVE))
+ 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);
+}
+
+/**
* batadv_v_elp_send_outstanding - ELP periodic broadcast sending
* @work: work queue item
*
@@ -54,6 +161,7 @@ static void batadv_v_elp_send_outstanding(struct work_struct *work)
struct batadv_elp_packet *elp_packet;
uint32_t elp_interval;
struct sk_buff *skb;
+ uint8_t num_neighs;

bat_v = container_of(work, struct batadv_hard_iface_bat_v, elp_wq.work);
hard_iface = container_of(bat_v, struct batadv_hard_iface, bat_v);
@@ -75,9 +183,15 @@ static void batadv_v_elp_send_outstanding(struct work_struct *work)
if (!skb)
goto out;

+ /* purge outdated entries first */
+ batadv_v_elp_neigh_purge(hard_iface);
+
elp_packet = (struct batadv_elp_packet *)skb->data;
elp_packet->seqno = htonl(atomic_read(&hard_iface->bat_v.elp_seqno));
- elp_packet->num_neighbors = 0;
+
+ num_neighs = atomic_read(&hard_iface->bat_v.num_neighbors);
+ elp_packet->num_neighbors = num_neighs;
+
elp_interval = atomic_read(&hard_iface->bat_v.elp_interval);
elp_packet->elp_interval = htonl(elp_interval);

@@ -110,6 +224,9 @@ int batadv_v_elp_iface_enable(struct batadv_hard_iface *hard_iface)
size_t size;
int res = -ENOMEM;

+ INIT_HLIST_HEAD(&hard_iface->bat_v.neigh_list);
+ spin_lock_init(&hard_iface->bat_v.neigh_list_lock);
+
size = ETH_HLEN + NET_IP_ALIGN + BATADV_ELP_HLEN;
hard_iface->bat_v.elp_skb = dev_alloc_skb(size);
if (!hard_iface->bat_v.elp_skb)
@@ -148,6 +265,8 @@ void batadv_v_elp_iface_disable(struct batadv_hard_iface *hard_iface)

dev_kfree_skb(hard_iface->bat_v.elp_skb);
hard_iface->bat_v.elp_skb = NULL;
+
+ batadv_v_elp_neigh_purge(hard_iface);
}

/**
@@ -177,3 +296,86 @@ void batadv_v_elp_primary_iface_set(struct batadv_hard_iface *hard_iface)
}
rcu_read_unlock();
}
+
+/**
+ * batadv_v_elp_neigh_update - update an ELP neighbour node
+ * @bat_priv: the bat priv with all the soft interface information
+ * @neigh_addr: the neighbour interface address
+ * @if_incoming: the interface the packet was received through
+ * @elp_packet: the received ELP packet
+ *
+ * Updates the ELP neighbour node state with the data received within the new
+ * ELP packet.
+ */
+static void batadv_v_elp_neigh_update(struct batadv_priv *bat_priv,
+ uint8_t *neigh_addr,
+ struct batadv_hard_iface *if_incoming,
+ struct batadv_elp_packet *elp_packet)
+{
+ struct batadv_elp_neigh_node *neigh;
+
+ neigh = batadv_v_elp_neigh_get(if_incoming, neigh_addr);
+ if (!neigh) {
+ neigh = batadv_v_elp_neigh_new(if_incoming, neigh_addr,
+ elp_packet->orig,
+ ntohl(elp_packet->seqno));
+ if (!neigh)
+ goto out;
+ }
+
+ neigh->last_seen = jiffies;
+
+out:
+ if (neigh)
+ batadv_elp_neigh_node_free_ref(neigh);
+}
+
+/**
+ * batadv_v_elp_packet_recv - main ELP packet handler
+ * @skb: the received packet
+ * @if_incoming: the interface this packet was received through
+ *
+ * Returns NET_RX_SUCCESS and consumes the skb if the packet was peoperly
+ * processed or NET_RX_DROP in case of failure.
+ */
+int batadv_v_elp_packet_recv(struct sk_buff *skb,
+ struct batadv_hard_iface *if_incoming)
+{
+ struct batadv_priv *bat_priv = netdev_priv(if_incoming->soft_iface);
+ struct batadv_elp_packet *elp_packet;
+ struct batadv_hard_iface *primary_if;
+ struct ethhdr *ethhdr = (struct ethhdr *)skb_mac_header(skb);
+ bool ret;
+
+ ret = batadv_check_management_packet(skb, if_incoming, BATADV_ELP_HLEN);
+ if (!ret)
+ return NET_RX_DROP;
+
+ if (batadv_is_my_mac(bat_priv, ethhdr->h_source))
+ return NET_RX_DROP;
+
+ /* did we receive a B.A.T.M.A.N. V ELP packet on an interface
+ * that does not have B.A.T.M.A.N. V ELP enabled ? */
+ if (strcmp(bat_priv->bat_algo_ops->name, "BATMAN_V") != 0)
+ return NET_RX_DROP;
+
+ elp_packet = (struct batadv_elp_packet *)skb->data;
+
+ batadv_dbg(BATADV_DBG_BATMAN, bat_priv,
+ "Received ELP packet from %pM seqno %u ORIG: %pM\n",
+ ethhdr->h_source, ntohl(elp_packet->seqno),
+ elp_packet->orig);
+
+ primary_if = batadv_primary_if_get_selected(bat_priv);
+ if (!primary_if)
+ goto out;
+
+ batadv_v_elp_neigh_update(bat_priv, ethhdr->h_source, if_incoming,
+ elp_packet);
+
+out:
+ if (primary_if)
+ batadv_hardif_free_ref(primary_if);
+ consume_skb(skb);
+ return NET_RX_SUCCESS;
+}
diff --git a/bat_v_elp.h b/bat_v_elp.h
index 06d2cb1..186ff4b 100644
--- a/bat_v_elp.h
+++ b/bat_v_elp.h
@@ -23,8 +23,14 @@
#ifndef _NET_BATMAN_ADV_BAT_V_ELP_H_
#define _NET_BATMAN_ADV_BAT_V_ELP_H_

+struct batadv_elp_neigh_node *
+batadv_v_elp_neigh_get(struct batadv_hard_iface *hard_iface,
+ uint8_t *neigh_addr);
+void batadv_elp_neigh_node_free_ref(struct batadv_elp_neigh_node *neigh);
int batadv_v_elp_iface_enable(struct batadv_hard_iface *hard_iface);
void batadv_v_elp_iface_disable(struct batadv_hard_iface *hard_iface);
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);

#endif /* _NET_BATMAN_ADV_BAT_V_ELP_H_ */
diff --git a/main.h b/main.h
index 34e85a2..4ab3216 100644
--- a/main.h
+++ b/main.h
@@ -45,6 +45,7 @@
#define BATADV_TT_WORK_PERIOD 5000 /* 5 seconds */
#define BATADV_ORIG_WORK_PERIOD 1000 /* 1 second */
#define BATADV_DAT_ENTRY_TIMEOUT (5*60000) /* 5 mins in milliseconds */
+#define BATADV_ELP_OUTDATED_MAX 4
/* sliding packet range of received originator messages in sequence numbers
* (should be a multiple of our word size)
*/
@@ -180,6 +181,7 @@ enum batadv_uev_type {
#include <linux/jiffies.h>
#include <linux/seq_file.h>
#include <linux/if_vlan.h>
+#include <linux/average.h> /* ewma */
#include "compat.h"

#include "types.h"
diff --git a/types.h b/types.h
index 518fa81..be230b6 100644
--- a/types.h
+++ b/types.h
@@ -73,12 +73,18 @@ struct batadv_hard_iface_bat_iv {
* struct batadv_hard_iface_bat_v - per hard interface B.A.T.M.A.N. V data
* @elp_interval: time interval between two ELP transmissions
* @elp_seqno: current ELP sequence number
+ * @neigh_list: list of ELP neighbour objects
+ * @neigh_list_lock: protects neigh_list
+ * @num_neighbours: number of neighbours in the neigh_list
* @elp_skb: base skb containing the ELP message to send
* @elp_wq: workqueue used to schedule ELP transmissions
*/
struct batadv_hard_iface_bat_v {
atomic_t elp_interval;
atomic_t elp_seqno;
+ struct hlist_head neigh_list;
+ spinlock_t neigh_list_lock;
+ atomic_t num_neighbors;
struct sk_buff *elp_skb;
struct delayed_work elp_wq;
};
@@ -327,6 +333,37 @@ struct batadv_gw_node {
};

/**
+ * struct batadv_elp_neigh - hard_iface ralated neighbor information
+ * @list: list node for batadv_hard_iface::neigh_list
+ * @orig: the MAC address of the corresponding orig_node
+ * @addr: the MAC address of the neighboring interface
+ * @metric: ewma link metric towards this neighbor
+ * @last_recv_seqno: last ELP received sequence number
+ * @lest_seen: last time this neigh has been seen
+ * @refcount: number of contexts the object is used
+ * @rcu: struct used for freeing in an RCU-safe manner
+ */
+struct batadv_elp_neigh_node {
+ struct hlist_node list;
+ uint8_t orig[ETH_ALEN];
+ uint8_t addr[ETH_ALEN];
+ struct ewma metric;
+ uint32_t last_recv_seqno;
+ unsigned long last_seen;
+ uint32_t elp_interval;
+ atomic_t refcount;
+ struct rcu_head rcu;
+};
+
+/**
+ * batadv_neigh_node_bat_v - B.A.T.M.A.N. V private neighbor information
+ * @elp_neigh: ELP private neighbour data
+ */
+struct batadv_neigh_node_bat_v {
+ struct batadv_elp_neigh_node *elp_neigh;
+};
+
+/**
* struct batadv_neigh_node - structure for single hops neighbors
* @list: list node for batadv_orig_node::neigh_list
* @orig_node: pointer to corresponding orig_node
@@ -336,6 +373,7 @@ struct batadv_gw_node {
* @if_incoming: pointer to incoming hard interface
* @last_seen: when last packet via this neighbor was received
* @last_ttl: last received ttl from this neigh node
+ * @elp_neigh: ELP private neighbour data
* @rcu: struct used for freeing in an RCU-safe manner
* @bat_iv: B.A.T.M.A.N. IV private structure
*/
@@ -347,6 +385,9 @@ struct batadv_neigh_node {
spinlock_t ifinfo_lock; /* protects ifinfo_list and its members */
struct batadv_hard_iface *if_incoming;
unsigned long last_seen;
+#ifdef CONFIG_BATMAN_ADV_BATMAN_V
+ struct batadv_neigh_node_bat_v bat_v;
+#endif
atomic_t refcount;
struct rcu_head rcu;
};
@@ -370,6 +411,15 @@ struct batadv_neigh_ifinfo_bat_iv {
};

/**
+ * struct batadv_neigh_ifinfo_bat_v - neighbor information per outgoing
+ * interface for BATMAN V
+ * @metric: last metric received from an originator via this neigh
+ */
+struct batadv_neigh_ifinfo_bat_v {
+ uint32_t metric;
+};
+
+/**
* struct batadv_neigh_ifinfo - neighbor information per outgoing interface
* @list: list node for batadv_neigh_node::ifinfo_list
* @if_outgoing: pointer to outgoing hard interface
@@ -382,6 +432,9 @@ struct batadv_neigh_ifinfo {
struct hlist_node list;
struct batadv_hard_iface *if_outgoing;
struct batadv_neigh_ifinfo_bat_iv bat_iv;
+#ifdef CONFIG_BATMAN_ADV_BATMAN_V
+ struct batadv_neigh_ifinfo_bat_v bat_v;
+#endif
uint8_t last_ttl;
atomic_t refcount;
struct rcu_head rcu;
--
1.8.5.3