Skip to contentSkip to conversation

NDP patches v4

B.A.T.M.A.N. In review Linus Lüssing 4 participants 15 messages Dec 31, 2010 – Jan 12, 2011 Kbuild

lore
Share & tools
lore
#0 lore raw

Hi everyone,

thanks for all the feedback and reviewing again. The following updated patches address Marek's comments and suggestions:
* Introducing a commit for renaming only
* batman_packet_ogm -> ogm_packet, batman_packet_ndp -> ndp_packet
* BAT_UNICAST followed by BAT_UNICAST_FRAG
* structs introduced in the patches where they're used, not earlier (ndp_packet, neigh_entry)
* moved own_ndp_send_time to ndp.c
* checkpatch cleaning
* avoid losing ndp-interval setting on interface down/up
* fixed a potential memory leak in error cases
* skb_copy instead of skb_clone
* rebased to trunk
* removal of unnecessary include
* hlist instead of doubly linked list
* added a break in one list traversal
* secure neigh_list with rcu-locking + ref-counting
* rename rq_real_bits to ndp_rq_window
* use msecs_to_jiffies instead of manual HZ multiplication
* fix get_batman_if_by_netdev usage / refcounting
* adding licenses

Furthermore I've changed the following:
* use dev_kfree_skb instead of kfree_skb in case of successful
ndp packet reception and processing (so no simple NET_RX_DROP return value)
* adding include guards for ndp.h
* use "= seqno - 1" in ndp_create_neighbor(), otherwise ndp_update_neighbor_lq() does not update tq/rq/last_valid on first ndp packet

Would be great if someone could check the usage of rcu-locking + refcounting. I was also a little confused because in "Documentation/RCU/listRCU.txt" list_del_rcu() and list_add_rcu() are not protected with a spinlock for the list here, but in the batman-adv code we are usually having those extra locks. Do I have to leave those spinlocks or can I remove them for adding/deleting entries in the neigh_list?

Cheers, Linus

#1 lore raw

PATCH 1/10 batman-adv: Rename packet type / structure / functions for OGMs

We are going to introduce two separate packet types, namely originator messages (OGM) and NDP (neighbor discovery protocol). This commit renames the structures, the packet type name and scheduling functions for OGMs to clearly indicate their purpose.

---
 aggregation.c       |   43 +++++++++----------
 aggregation.h       |    3 +-
 hard-interface.c    |   45 ++++++++++----------
 packet.h            |    7 ++-
 routing.c           |  103 +++++++++++++++++++++++-----------------------
 routing.h           |    2 +-
 send.c              |  114 +++++++++++++++++++++++++-------------------------
 send.h              |    4 +-
 soft-interface.c    |   16 ++++----
 translation-table.c |    2 +-
 10 files changed, 171 insertions(+), 168 deletions(-)
aggregation.c +21 -22
index 3850a3e..208a1ab 100644
@@ -25,21 +25,21 @@
 #include "routing.h"
 
 /* calculate the size of the hna information for a given packet */
-static int hna_len(struct batman_packet *batman_packet)
+static int hna_len(struct ogm_packet *ogm_packet)
 {
-	return batman_packet->num_hna * ETH_ALEN;
+	return ogm_packet->num_hna * ETH_ALEN;
 }
 
 /* return true if new_packet can be aggregated with forw_packet */
-static bool can_aggregate_with(struct batman_packet *new_batman_packet,
+static bool can_aggregate_with(struct ogm_packet *new_ogm_packet,
 			       int packet_len,
 			       unsigned long send_time,
 			       bool directlink,
 			       struct batman_if *if_incoming,
 			       struct forw_packet *forw_packet)
 {
-	struct batman_packet *batman_packet =
-		(struct batman_packet *)forw_packet->skb->data;
+	struct ogm_packet *ogm_packet =
+		(struct ogm_packet *)forw_packet->skb->data;
 	int aggregated_bytes = forw_packet->packet_len + packet_len;
 
 	/**
@@ -68,8 +68,8 @@ static bool can_aggregate_with(struct batman_packet *new_batman_packet,
 		/* packets without direct link flag and high TTL
 		 * are flooded through the net  */
 		if ((!directlink) &&
-		    (!(batman_packet->flags & DIRECTLINK)) &&
-		    (batman_packet->ttl != 1) &&
+		    (!(ogm_packet->flags & DIRECTLINK)) &&
+		    (ogm_packet->ttl != 1) &&
 
 		    /* own packets originating non-primary
 		     * interfaces leave only that interface */
@@ -80,13 +80,13 @@ static bool can_aggregate_with(struct batman_packet *new_batman_packet,
 		/* if the incoming packet is sent via this one
 		 * interface only - we still can aggregate */
 		if ((directlink) &&
-		    (new_batman_packet->ttl == 1) &&
+		    (new_ogm_packet->ttl == 1) &&
 		    (forw_packet->if_incoming == if_incoming) &&
 
 		    /* packets from direct neighbors or
 		     * own secondary interface packets
 		     * (= secondary interface packets in general) */
-		    (batman_packet->flags & DIRECTLINK ||
+		    (ogm_packet->flags & DIRECTLINK ||
 		     (forw_packet->own &&
 		      forw_packet->if_incoming->if_num != 0)))
 			return true;
@@ -197,9 +197,8 @@ void add_bat_packet_to_list(struct bat_priv *bat_priv,
 	 */
 	struct forw_packet *forw_packet_aggr = NULL, *forw_packet_pos = NULL;
 	struct hlist_node *tmp_node;
-	struct batman_packet *batman_packet =
-		(struct batman_packet *)packet_buff;
-	bool direct_link = batman_packet->flags & DIRECTLINK ? 1 : 0;
+	struct ogm_packet *ogm_packet = (struct ogm_packet *)packet_buff;
+	bool direct_link = ogm_packet->flags & DIRECTLINK ? 1 : 0;
 
 	/* find position for the packet in the forward queue */
 	spin_lock_bh(&bat_priv->forw_bat_list_lock);
@@ -207,7 +206,7 @@ void add_bat_packet_to_list(struct bat_priv *bat_priv,
 	if ((atomic_read(&bat_priv->aggregated_ogms)) && (!own_packet)) {
 		hlist_for_each_entry(forw_packet_pos, tmp_node,
 				     &bat_priv->forw_bat_list, list) {
-			if (can_aggregate_with(batman_packet,
+			if (can_aggregate_with(ogm_packet,
 					       packet_len,
 					       send_time,
 					       direct_link,
@@ -249,25 +248,25 @@ void add_bat_packet_to_list(struct bat_priv *bat_priv,
 void receive_aggr_bat_packet(struct ethhdr *ethhdr, unsigned char *packet_buff,
 			     int packet_len, struct batman_if *if_incoming)
 {
-	struct batman_packet *batman_packet;
+	struct ogm_packet *ogm_packet;
 	int buff_pos = 0;
 	unsigned char *hna_buff;
 
-	batman_packet = (struct batman_packet *)packet_buff;
+	ogm_packet = (struct ogm_packet *)packet_buff;
 
 	do {
 		/* network to host order for our 32bit seqno, and the
 		   orig_interval. */
-		batman_packet->seqno = ntohl(batman_packet->seqno);
+		ogm_packet->seqno = ntohl(ogm_packet->seqno);
 
-		hna_buff = packet_buff + buff_pos + BAT_PACKET_LEN;
-		receive_bat_packet(ethhdr, batman_packet,
-				   hna_buff, hna_len(batman_packet),
+		hna_buff = packet_buff + buff_pos + BAT_PACKET_OGM_LEN;
+		receive_bat_packet(ethhdr, ogm_packet,
+				   hna_buff, hna_len(ogm_packet),
 				   if_incoming);
 
-		buff_pos += BAT_PACKET_LEN + hna_len(batman_packet);
-		batman_packet = (struct batman_packet *)
+		buff_pos += BAT_PACKET_OGM_LEN + hna_len(ogm_packet);
+		ogm_packet = (struct ogm_packet *)
 			(packet_buff + buff_pos);
 	} while (aggregated_packet(buff_pos, packet_len,
-				   batman_packet->num_hna));
+				   ogm_packet->num_hna));
 }
aggregation.h +2 -1
index 71a91b3..667ef2d 100644
@@ -27,7 +27,8 @@
 /* is there another aggregated packet here? */
 static inline int aggregated_packet(int buff_pos, int packet_len, int num_hna)
 {
-	int next_buff_pos = buff_pos + BAT_PACKET_LEN + (num_hna * ETH_ALEN);
+	int next_buff_pos = buff_pos + BAT_PACKET_OGM_LEN +
+			    (num_hna * ETH_ALEN);
 
 	return (next_buff_pos <= packet_len) &&
 		(next_buff_pos <= MAX_AGGREGATION_BYTES);
hard-interface.c +23 -22

110 lines not on this page · raw message

packet.h +4 -3
index b49fdf7..681052d 100644
@@ -24,7 +24,7 @@
 
 #define ETH_P_BATMAN  0x4305	/* unofficial/not registered Ethertype */
 
-#define BAT_PACKET       0x01
+#define BAT_PACKET_OGM   0x01
 #define BAT_ICMP         0x02
 #define BAT_UNICAST      0x03
 #define BAT_BCAST        0x04
@@ -51,7 +51,8 @@
 /* fragmentation defines */
 #define UNI_FRAG_HEAD 0x01
 
-struct batman_packet {
+/* Originator message packet */
+struct ogm_packet {
 	uint8_t  packet_type;
 	uint8_t  version;  /* batman version field */
 	uint8_t  flags;    /* 0x40: DIRECTLINK flag, 0x20 VIS_SERVER flag... */
@@ -65,7 +66,7 @@ struct batman_packet {
 	uint8_t  align;
 } __attribute__((packed));
 
-#define BAT_PACKET_LEN sizeof(struct batman_packet)
+#define BAT_PACKET_OGM_LEN sizeof(struct ogm_packet)
 
 struct icmp_packet {
 	uint8_t  packet_type;
routing.c +52 -51

289 lines not on this page · raw message

routing.h +1 -1
index 725cc38..0c62015 100644
@@ -26,7 +26,7 @@
 
 void slide_own_bcast_window(struct batman_if *batman_if);
 void receive_bat_packet(struct ethhdr *ethhdr,
-				struct batman_packet *batman_packet,
+				struct ogm_packet *ogm_packet,
 				unsigned char *hna_buff, int hna_buff_len,
 				struct batman_if *if_incoming);
 void update_routes(struct bat_priv *bat_priv, struct orig_node *orig_node,
send.c +57 -57

270 lines not on this page · raw message

send.h +2 -2
index c4cefa8..2ac1b98 100644
@@ -27,10 +27,10 @@
 int send_skb_packet(struct sk_buff *skb,
 				struct batman_if *batman_if,
 				uint8_t *dst_addr);
-void schedule_own_packet(struct batman_if *batman_if);
+void schedule_own_ogm_packet(struct batman_if *batman_if);
 void schedule_forward_packet(struct orig_node *orig_node,
 			     struct ethhdr *ethhdr,
-			     struct batman_packet *batman_packet,
+			     struct ogm_packet *ogm_packet,
 			     uint8_t directlink, int hna_buff_len,
 			     struct batman_if *if_outgoing);
 int add_bcast_packet_to_list(struct bat_priv *bat_priv, struct sk_buff *skb);
soft-interface.c +8 -8
index e89ede1..f9f98fb 100644
@@ -221,28 +221,28 @@ static void softif_batman_recv(struct sk_buff *skb, struct net_device *dev,
 {
 	struct bat_priv *bat_priv = netdev_priv(dev);
 	struct ethhdr *ethhdr = (struct ethhdr *)skb->data;
-	struct batman_packet *batman_packet;
+	struct ogm_packet *ogm_packet;
 	struct softif_neigh *softif_neigh, *softif_neigh_tmp;
 
 	if (ntohs(ethhdr->h_proto) == ETH_P_8021Q)
-		batman_packet = (struct batman_packet *)
+		ogm_packet = (struct ogm_packet *)
 					(skb->data + ETH_HLEN + VLAN_HLEN);
 	else
-		batman_packet = (struct batman_packet *)(skb->data + ETH_HLEN);
+		ogm_packet = (struct ogm_packet *) (skb->data + ETH_HLEN);
 
-	if (batman_packet->version != COMPAT_VERSION)
+	if (ogm_packet->version != COMPAT_VERSION)
 		goto err;
 
-	if (batman_packet->packet_type != BAT_PACKET)
+	if (ogm_packet->packet_type != BAT_PACKET_OGM)
 		goto err;
 
-	if (!(batman_packet->flags & PRIMARIES_FIRST_HOP))
+	if (!(ogm_packet->flags & PRIMARIES_FIRST_HOP))
 		goto err;
 
-	if (is_my_mac(batman_packet->orig))
+	if (is_my_mac(ogm_packet->orig))
 		goto err;
 
-	softif_neigh = softif_neigh_get(bat_priv, batman_packet->orig, vid);
+	softif_neigh = softif_neigh_get(bat_priv, ogm_packet->orig, vid);
 
 	if (!softif_neigh)
 		goto err;
translation-table.c +1 -1
index a633b5a..a758c7c 100644
@@ -76,7 +76,7 @@ void hna_local_add(struct net_device *soft_iface, uint8_t *addr)
 	   space in batman_packet->num_hna That also should give a limit to
 	   MAC-flooding. */
 	required_bytes = (bat_priv->num_local_hna + 1) * ETH_ALEN;
-	required_bytes += BAT_PACKET_LEN;
+	required_bytes += BAT_PACKET_OGM_LEN;
 
 	if ((required_bytes > ETH_DATA_LEN) ||
 	    (atomic_read(&bat_priv->aggregated_ogms) &&
Signature · 1 line
1.7.1
#2 lore raw

PATCH 2/10 batman-adv: Adding workqueue for new ndp packets

In reply to Linus Lüssing

The new neighbor discovery packets will later need their own interval per interface. For instance on a wifi interface which has regularly changing link qualities the ndp interval should be faster than on a static cable link where we would need some probes from time to time only.

This patch adds a workqueue per interface used by batman-adv. When an interface is active, a ndp_send() with the according batman_if structure will be called every second now.

---
 Makefile.kbuild  |    1 +
 hard-interface.c |    9 +++++++
 ndp.c            |   71 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 ndp.h            |   31 +++++++++++++++++++++++
 types.h          |    3 ++
 5 files changed, 115 insertions(+), 0 deletions(-)
 create mode 100644 ndp.c
 create mode 100644 ndp.h
Makefile.kbuild +1 -0
index e99c198..094eb31 100644
@@ -42,6 +42,7 @@ batman-adv-y += hard-interface.o
 batman-adv-y += hash.o
 batman-adv-y += icmp_socket.o
 batman-adv-y += main.o
+batman-adv-y += ndp.o
 batman-adv-y += originator.o
 batman-adv-y += ring_buffer.o
 batman-adv-y += routing.o
hard-interface.c +9 -0
index a992113..aba895f 100644
@@ -26,6 +26,7 @@
 #include "translation-table.h"
 #include "routing.h"
 #include "bat_sysfs.h"
+#include "ndp.h"
 #include "originator.h"
 #include "hash.h"
 
@@ -260,6 +261,7 @@ static void hardif_activate_interface(struct batman_if *batman_if)
 		 batman_if->net_dev->name);
 
 	update_min_mtu(batman_if->soft_iface);
+	ndp_start_timer(batman_if);
 	return;
 }
 
@@ -274,6 +276,7 @@ static void hardif_deactivate_interface(struct batman_if *batman_if)
 	bat_info(batman_if->soft_iface, "Interface deactivated: %s\n",
 		 batman_if->net_dev->name);
 
+	ndp_stop_timer(batman_if);
 	update_min_mtu(batman_if->soft_iface);
 }
 
@@ -328,6 +331,8 @@ int hardif_enable_interface(struct batman_if *batman_if, char *iface_name)
 
 	atomic_set(&batman_if->seqno, 1);
 	atomic_set(&batman_if->frag_seqno, 1);
+	ndp_init(batman_if);
+
 	bat_info(batman_if->soft_iface, "Adding interface: %s\n",
 		 batman_if->net_dev->name);
 
@@ -381,6 +386,7 @@ void hardif_disable_interface(struct batman_if *batman_if)
 
 	bat_info(batman_if->soft_iface, "Removing interface: %s\n",
 		 batman_if->net_dev->name);
+	ndp_free(batman_if);
 	dev_remove_pack(&batman_if->batman_adv_ptype);
 	kref_put(&batman_if->refcount, hardif_free_ref);
 
@@ -435,6 +441,9 @@ static struct batman_if *hardif_add_interface(struct net_device *net_dev)
 	if (ret)
 		goto free_if;
 
+	atomic_set(&batman_if->ndp_interval, 500);
+	atomic_set(&batman_if->ndp_seqno, 0);
+
 	batman_if->if_num = -1;
 	batman_if->net_dev = net_dev;
 	batman_if->soft_iface = NULL;
ndp.c new file +71 -0

71 lines not on this page · raw message

ndp.h new file +31 -0
new file mode 100644
index 0000000..1405e6b
@@ -0,0 +1,31 @@
+/*
+ * Copyright (C) 2010 B.A.T.M.A.N. contributors:
+ *
+ * Linus Lüssing
+ *
+ * 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_NDP_H_
+#define _NET_BATMAN_ADV_NDP_H_
+
+void ndp_start_timer(struct batman_if *batman_if);
+void ndp_stop_timer(struct batman_if *batman_if);
+
+int ndp_init(struct batman_if *batman_if);
+void ndp_free(struct batman_if *batman_if);
+
+#endif /* _NET_BATMAN_ADV_NDP_H_ */
types.h +3 -0
index 09d18d8..3ef48a6 100644
@@ -47,6 +47,9 @@ struct batman_if {
 	struct packet_type batman_adv_ptype;
 	struct net_device *soft_iface;
 	struct rcu_head rcu;
+	atomic_t ndp_interval;
+	atomic_t ndp_seqno;
+	struct delayed_work ndp_wq;
 };
 
 /**
Signature · 1 line
1.7.1
#3 lore raw

PATCH 3/10 batman-adv: Send neighbor discovery packets

In reply to Linus Lüssing

This patch makes use of the previously introduced periodic tasks per interface and actually sends neighbor discovery packets on these now.
Note: The TQ values of each neighbor are not being added yet to these NDPs and also no evaluation of these packets is being done.

Also most of the packet type numbers got changed due to their reordering.

---
 hard-interface.c |   12 +++++++++++-
 ndp.c            |   35 ++++++++++++++++++++++++++++++++++-
 packet.h         |   23 +++++++++++++++++------
 types.h          |    1 +
 4 files changed, 63 insertions(+), 8 deletions(-)
hard-interface.c +11 -1
index aba895f..3dc24f1 100644
@@ -284,6 +284,7 @@ int hardif_enable_interface(struct batman_if *batman_if, char *iface_name)
 {
 	struct bat_priv *bat_priv;
 	struct ogm_packet *ogm_packet;
+	int ret;
 
 	if (batman_if->if_status != IF_NOT_IN_USE)
 		goto out;
@@ -331,7 +332,9 @@ int hardif_enable_interface(struct batman_if *batman_if, char *iface_name)
 
 	atomic_set(&batman_if->seqno, 1);
 	atomic_set(&batman_if->frag_seqno, 1);
-	ndp_init(batman_if);
+	ret = ndp_init(batman_if);
+	if (ret)
+		goto free;
 
 	bat_info(batman_if->soft_iface, "Adding interface: %s\n",
 		 batman_if->net_dev->name);
@@ -369,7 +372,14 @@ int hardif_enable_interface(struct batman_if *batman_if, char *iface_name)
 
 out:
 	return 0;
+free:
+	dev_remove_pack(&batman_if->batman_adv_ptype);
+	kref_put(&batman_if->refcount, hardif_free_ref);
 
+	bat_priv->num_ifaces--;
+	orig_hash_del_if(batman_if, bat_priv->num_ifaces);
+
+	kfree(batman_if->packet_buff);
 err:
 	return -ENOMEM;
 }
ndp.c +34 -1
index 60631b0..3269d67 100644
@@ -49,10 +49,21 @@ static void ndp_send(struct work_struct *work)
 	struct batman_if *batman_if = container_of(work, struct batman_if,
 							ndp_wq.work);
 	struct bat_priv *bat_priv = netdev_priv(batman_if->soft_iface);
+	struct batman_packet_ndp *ndp_packet;
+	struct sk_buff *skb;
+
+	skb = skb_copy(batman_if->ndp_skb, GFP_ATOMIC);
+	ndp_packet = (struct batman_packet_ndp *)skb->data;
+	ndp_packet->seqno = htonl(atomic_read(&batman_if->ndp_seqno));
+	ndp_packet->num_neighbors = 0;
+	memcpy(ndp_packet->orig, bat_priv->primary_if->net_dev->dev_addr,
+	       ETH_ALEN);
 
 	bat_dbg(DBG_BATMAN, bat_priv,
 		"batman-adv:Sending ndp packet on interface %s, seqno %d\n",
-		batman_if->net_dev, atomic_read(&batman_if->ndp_seqno));
+		batman_if->net_dev, ntohl(ndp_packet->seqno));
+
+	send_skb_packet(skb, batman_if, broadcast_addr);
 
 	atomic_inc(&batman_if->ndp_seqno);
 	ndp_start_timer(batman_if);
@@ -60,12 +71,34 @@ static void ndp_send(struct work_struct *work)
 
 int ndp_init(struct batman_if *batman_if)
 {
+	struct batman_packet_ndp *ndp_packet;
+
+	batman_if->ndp_skb =
+		dev_alloc_skb(ETH_DATA_LEN + sizeof(struct ethhdr));
+	if (!batman_if->ndp_skb) {
+		printk(KERN_ERR "batman-adv: Can't add "
+			"local interface packet (%s): out of memory\n",
+			batman_if->net_dev->name);
+		goto err;
+	}
+	skb_reserve(batman_if->ndp_skb, sizeof(struct ethhdr) +
+					sizeof(struct batman_packet_ndp));
+	ndp_packet = (struct batman_packet_ndp *)
+		skb_push(batman_if->ndp_skb, sizeof(struct batman_packet_ndp));
+	memset(ndp_packet, 0, sizeof(struct batman_packet_ndp));
+
+	ndp_packet->packet_type = BAT_PACKET_NDP;
+	ndp_packet->version = COMPAT_VERSION;
+
 	INIT_DELAYED_WORK(&batman_if->ndp_wq, ndp_send);
 
 	return 0;
+err:
+	return 1;
 }
 
 void ndp_free(struct batman_if *batman_if)
 {
 	ndp_stop_timer(batman_if);
+	dev_kfree_skb(batman_if->ndp_skb);
 }
packet.h +17 -6
index 681052d..0b0c453 100644
@@ -24,12 +24,13 @@
 
 #define ETH_P_BATMAN  0x4305	/* unofficial/not registered Ethertype */
 
-#define BAT_PACKET_OGM   0x01
-#define BAT_ICMP         0x02
-#define BAT_UNICAST      0x03
-#define BAT_BCAST        0x04
-#define BAT_VIS          0x05
-#define BAT_UNICAST_FRAG 0x06
+#define BAT_PACKET_NDP   0x01
+#define BAT_PACKET_OGM   0x02
+#define BAT_ICMP         0x03
+#define BAT_UNICAST      0x04
+#define BAT_UNICAST_FRAG 0x05
+#define BAT_BCAST        0x06
+#define BAT_VIS          0x07
 
 /* this file is included by batctl which needs these defines */
 #define COMPAT_VERSION 12
@@ -51,6 +52,16 @@
 /* fragmentation defines */
 #define UNI_FRAG_HEAD 0x01
 
+/* Neighbor discovery packet */
+struct batman_packet_ndp {
+	uint8_t  packet_type;
+	uint8_t  version;  /* batman version field */
+	uint8_t  orig[6];
+	uint32_t seqno;
+	uint8_t  num_neighbors;
+	uint8_t  align[3];
+} __attribute__((packed));
+
 /* Originator message packet */
 struct ogm_packet {
 	uint8_t  packet_type;
types.h +1 -0
index 3ef48a6..f81d0ba 100644
@@ -49,6 +49,7 @@ struct batman_if {
 	struct rcu_head rcu;
 	atomic_t ndp_interval;
 	atomic_t ndp_seqno;
+	struct sk_buff *ndp_skb;
 	struct delayed_work ndp_wq;
 };
 
Signature · 1 line
1.7.1
#4 lore raw

PATCH 4/10 batman-adv: Creating neighbor structures, updating LQs

In reply to Linus Lüssing

It will now be checked if a neighbor discovery packet from a new neighbor on a certain interface has been received. If so, structures in memory will be allocated for further seqno-tracking and RQ calculations, and TQ reception, which will be updated frequently from this commit on.

---
 hard-interface.c |    5 ++
 ndp.c            |  145 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 ndp.h            |    4 ++
 routing.c        |   42 +++++++++++++++-
 routing.h        |    1 +
 types.h          |    9 +++
 6 files changed, 205 insertions(+), 1 deletions(-)
hard-interface.c +5 -0
index 3dc24f1..f4bbb1a 100644
@@ -618,6 +618,11 @@ int batman_skb_recv(struct sk_buff *skb, struct net_device *dev,
 	 * the supplied skb. if not, we have to free the skb. */
 
 	switch (ogm_packet->packet_type) {
+		/* batman neighbor discovery protocol packet */
+	case BAT_PACKET_NDP:
+		ret = recv_ndp_packet(skb, batman_if);
+		break;
+
 		/* batman originator packet */
 	case BAT_PACKET_OGM:
 		ret = recv_bat_packet(skb, batman_if);
ndp.c +145 -0

172 lines not on this page · raw message

ndp.h +4 -0
index 1405e6b..2496c3f 100644
@@ -27,5 +27,9 @@ void ndp_stop_timer(struct batman_if *batman_if);
 
 int ndp_init(struct batman_if *batman_if);
 void ndp_free(struct batman_if *batman_if);
+uint8_t ndp_fetch_tq(struct batman_packet_ndp *packet,
+		 uint8_t *my_if_addr);
+int ndp_update_neighbor(uint8_t my_tq, uint32_t seqno,
+			struct batman_if *batman_if, uint8_t *neigh_addr);
 
 #endif /* _NET_BATMAN_ADV_NDP_H_ */
routing.c +41 -1

54 lines not on this page · raw message

routing.h +1 -0
index 0c62015..24567f9 100644
@@ -39,6 +39,7 @@ int recv_unicast_packet(struct sk_buff *skb, struct batman_if *recv_if);
 int recv_ucast_frag_packet(struct sk_buff *skb, struct batman_if *recv_if);
 int recv_bcast_packet(struct sk_buff *skb, struct batman_if *recv_if);
 int recv_vis_packet(struct sk_buff *skb, struct batman_if *recv_if);
+int recv_ndp_packet(struct sk_buff *skb, struct batman_if *recv_if);
 int recv_bat_packet(struct sk_buff *skb, struct batman_if *recv_if);
 struct neigh_node *find_router(struct bat_priv *bat_priv,
 		struct orig_node *orig_node, struct batman_if *recv_if);
types.h +9 -0
index f81d0ba..43721cf 100644
@@ -51,6 +51,8 @@ struct batman_if {
 	atomic_t ndp_seqno;
 	struct sk_buff *ndp_skb;
 	struct delayed_work ndp_wq;
+	struct hlist_head neigh_list;
+	spinlock_t neigh_list_lock;
 };
 
 /**
@@ -113,6 +115,9 @@ struct neigh_node {
 	struct hlist_node list;
 	uint8_t addr[ETH_ALEN];
 	uint8_t real_packet_count;
+	uint8_t rq;
+	uint32_t last_rq_seqno;
+	unsigned long ndp_rq_window[NUM_WORDS];
 	uint8_t tq_recv[TQ_GLOBAL_WINDOW_SIZE];
 	uint8_t tq_index;
 	uint8_t tq_avg;
@@ -126,6 +131,10 @@ struct neigh_node {
 	struct batman_if *if_incoming;
 };
 
+struct neigh_entry {
+	uint8_t addr[ETH_ALEN];
+	uint8_t rq;
+};
 
 struct bat_priv {
 	atomic_t mesh_state;
Signature · 1 line
1.7.1
#5 lore raw

PATCH 5/10 batman-adv: Purge outdated ndp neighbours

In reply to Linus Lüssing

If no new packet has been received from a neighbour for a while, then delete it from memory.

---
 ndp.c        |   28 ++++++++++++++++++++++++++++
 ndp.h        |    1 +
 originator.c |    2 ++
 3 files changed, 31 insertions(+), 0 deletions(-)
ndp.c +28 -0
index 23e3bcd..dbb0e9e 100644
@@ -22,6 +22,7 @@
 #include "main.h"
 #include "send.h"
 #include "ndp.h"
+#include "hard-interface.h"
 #include "originator.h"
 
 /* when do we schedule our own neighbor discovery packet to be sent */
@@ -210,6 +211,33 @@ static struct neigh_node *ndp_create_neighbor(uint8_t my_tq, uint32_t seqno,
 	return neigh_node;
 }
 
+void ndp_purge_neighbors(void)
+{
+	struct neigh_node *neigh_node;
+	struct hlist_node *node, *node_tmp;
+	struct batman_if *batman_if;
+
+	rcu_read_lock();
+	list_for_each_entry_rcu(batman_if, &if_list, list) {
+		if (batman_if->if_status != IF_ACTIVE)
+			continue;
+
+		spin_lock_bh(&batman_if->neigh_list_lock);
+		hlist_for_each_entry_safe(neigh_node, node, node_tmp,
+					  &batman_if->neigh_list, list) {
+			if (time_before(jiffies, neigh_node->last_valid +
+					msecs_to_jiffies(PURGE_TIMEOUT *
+							 1000)))
+				continue;
+
+			hlist_del(&neigh_node->list);
+			kfree(neigh_node);
+		}
+		spin_unlock_bh(&batman_if->neigh_list_lock);
+	}
+	rcu_read_unlock();
+}
+
 int ndp_update_neighbor(uint8_t my_tq, uint32_t seqno,
 			struct batman_if *batman_if, uint8_t *neigh_addr)
 {
ndp.h +1 -0
index 2496c3f..a828362 100644
@@ -29,6 +29,7 @@ int ndp_init(struct batman_if *batman_if);
 void ndp_free(struct batman_if *batman_if);
 uint8_t ndp_fetch_tq(struct batman_packet_ndp *packet,
 		 uint8_t *my_if_addr);
+void ndp_purge_neighbors(void);
 int ndp_update_neighbor(uint8_t my_tq, uint32_t seqno,
 			struct batman_if *batman_if, uint8_t *neigh_addr);
 
originator.c +2 -0
index c043bf8..e98add5 100644
@@ -22,6 +22,7 @@
 /* increase the reference counter for this originator */
 
 #include "main.h"
+#include "ndp.h"
 #include "originator.h"
 #include "hash.h"
 #include "translation-table.h"
@@ -334,6 +335,7 @@ static void purge_orig(struct work_struct *work)
 		container_of(delayed_work, struct bat_priv, orig_work);
 
 	_purge_orig(bat_priv);
+	ndp_purge_neighbors();
 	start_purge_timer(bat_priv);
 }
 
Signature · 1 line
1.7.1
#6 lore raw

PATCH 6/10 batman-adv: Adding ndp debugfs output

In reply to Linus Lüssing

Lists all neighbours and their tq/rq values detected and measured by the Neighbor Discovery Protocol (NDP).

---
 bat_debugfs.c |    9 ++++++++
 ndp.c         |   60 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 ndp.h         |    1 +
 3 files changed, 70 insertions(+), 0 deletions(-)
bat_debugfs.c +9 -0
index 0ae81d0..602aa15 100644
@@ -25,6 +25,7 @@
 
 #include "bat_debugfs.h"
 #include "translation-table.h"
+#include "ndp.h"
 #include "originator.h"
 #include "hard-interface.h"
 #include "gateway_common.h"
@@ -222,6 +223,12 @@ static void debug_log_cleanup(struct bat_priv *bat_priv)
 }
 #endif
 
+static int neighbors_open(struct inode *inode, struct file *file)
+{
+	struct net_device *net_dev = (struct net_device *)inode->i_private;
+	return single_open(file, ndp_seq_print_text, net_dev);
+}
+
 static int originators_open(struct inode *inode, struct file *file)
 {
 	struct net_device *net_dev = (struct net_device *)inode->i_private;
@@ -275,6 +282,7 @@ struct bat_debuginfo bat_debuginfo_##_name = {	\
 		}				\
 };
 
+static BAT_DEBUGINFO(neighbors, S_IRUGO, neighbors_open);
 static BAT_DEBUGINFO(originators, S_IRUGO, originators_open);
 static BAT_DEBUGINFO(gateways, S_IRUGO, gateways_open);
 static BAT_DEBUGINFO(softif_neigh, S_IRUGO, softif_neigh_open);
@@ -283,6 +291,7 @@ static BAT_DEBUGINFO(transtable_local, S_IRUGO, transtable_local_open);
 static BAT_DEBUGINFO(vis_data, S_IRUGO, vis_data_open);
 
 static struct bat_debuginfo *mesh_debuginfos[] = {
+	&bat_debuginfo_neighbors,
 	&bat_debuginfo_originators,
 	&bat_debuginfo_gateways,
 	&bat_debuginfo_softif_neigh,
ndp.c +60 -0

63 lines not on this page · raw message

ndp.h +1 -0
index a828362..f528bcf 100644
@@ -32,5 +32,6 @@ uint8_t ndp_fetch_tq(struct batman_packet_ndp *packet,
 void ndp_purge_neighbors(void);
 int ndp_update_neighbor(uint8_t my_tq, uint32_t seqno,
 			struct batman_if *batman_if, uint8_t *neigh_addr);
+int ndp_seq_print_text(struct seq_file *seq, void *offset);
 
 #endif /* _NET_BATMAN_ADV_NDP_H_ */
Signature · 1 line
1.7.1
#7 lore raw

PATCH 7/10 batman-adv: Adding batman_if specific sysfs wrapper macros for UINT

In reply to Linus Lüssing

This allows us to easily add a sysfs parameter for an unsigned int later, which is not for a batman mesh interface (e.g. bat0), but for a common interface instead. It allows reading and writing an atomic_t in batman_if (instead of bat_priv compared to the mesh variant).

---
 bat_sysfs.c |   43 +++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 43 insertions(+), 0 deletions(-)
bat_sysfs.c +43 -0
index cd7bb51..5954389 100644
@@ -94,6 +94,49 @@ ssize_t show_##_name(struct kobject *kobj, struct attribute *attr,	\
 	static BAT_ATTR(_name, _mode, show_##_name, store_##_name)
 
 
+#define BAT_ATTR_IF_STORE_UINT(_name, _min, _max, _post_func)		\
+ssize_t store_##_name(struct kobject *kobj, struct attribute *attr,	\
+			     char *buff, size_t count)			\
+{									\
+	struct net_device *net_dev = kobj_to_netdev(kobj);		\
+	struct batman_if *batman_if = get_batman_if_by_netdev(net_dev);	\
+	ssize_t length;							\
+									\
+	if (!batman_if)							\
+		return 0;						\
+									\
+	length = __store_uint_attr(buff, count, _min, _max, _post_func,	\
+				 attr, &batman_if->_name, net_dev);	\
+									\
+	kref_put(&batman_if->refcount, hardif_free_ref);		\
+	return length;							\
+}
+
+#define BAT_ATTR_IF_SHOW_UINT(_name)					\
+ssize_t show_##_name(struct kobject *kobj, struct attribute *attr,	\
+			    char *buff)					\
+{									\
+	struct net_device *net_dev = kobj_to_netdev(kobj);		\
+	struct batman_if *batman_if = get_batman_if_by_netdev(net_dev);	\
+	ssize_t length;							\
+									\
+	if (!batman_if)							\
+		return 0;						\
+									\
+	length = sprintf(buff, "%i\n", atomic_read(&batman_if->_name));	\
+									\
+	kref_put(&batman_if->refcount, hardif_free_ref);		\
+	return length;							\
+}
+
+/* Use this, if you are going to set [name] in batman_if to unsigned integer
+ * values only */
+#define BAT_ATTR_IF_UINT(_name, _mode, _min, _max, _post_func)		\
+	static BAT_ATTR_IF_STORE_UINT(_name, _min, _max, _post_func)	\
+	static BAT_ATTR_IF_SHOW_UINT(_name)				\
+	static BAT_ATTR(_name, _mode, show_##_name, store_##_name)
+
+
 static int store_bool_attr(char *buff, size_t count,
 			   struct net_device *net_dev,
 			   char *attr_name, atomic_t *attr)
Signature · 1 line
1.7.1
#8 lore raw

PATCH 8/10 batman-adv: Adding sysfs parameter for ndp interval

In reply to Linus Lüssing

This parameter can be set individually on each interface and allows the configuration of the ndp interval for the link quality measurements during runtime. Usually it is desirable to set it to a higher (= slower) value on interfaces which have a more static characteristic (e.g. wired interfaces) or very dense neighbourhoods to reduce overhead.

---
 bat_sysfs.c |    2 ++
 1 files changed, 2 insertions(+), 0 deletions(-)
bat_sysfs.c +2 -0
index 5954389..ae15a94 100644
@@ -588,10 +588,12 @@ static ssize_t show_iface_status(struct kobject *kobj, struct attribute *attr,
 static BAT_ATTR(mesh_iface, S_IRUGO | S_IWUSR,
 		show_mesh_iface, store_mesh_iface);
 static BAT_ATTR(iface_status, S_IRUGO, show_iface_status, NULL);
+BAT_ATTR_IF_UINT(ndp_interval, S_IRUGO | S_IWUSR, 2 * JITTER, INT_MAX, NULL);
 
 static struct bat_attribute *batman_attrs[] = {
 	&bat_attr_mesh_iface,
 	&bat_attr_iface_status,
+	&bat_attr_ndp_interval,
 	NULL,
 };
 
Signature · 1 line
1.7.1
#9 lore raw

PATCH 9/10 batman-adv: Use local tq values determined by NDP on OGMs

In reply to Linus Lüssing

With this commit not the local transmit quality values determined by the OGMs themselves are applied on received OGMs, but the local transmit quality detemined by NDP instead. Usually the link quality measurements of NDP are more up-to-date than the one of the OGMs, as NDP is using a more frequent interval because NDP's packets are not being flooded through the whole mesh.

---
 routing.c |   64 ++++++++++++++++++++++++++++--------------------------------
 1 files changed, 30 insertions(+), 34 deletions(-)
routing.c +30 -34
index 947592f..8a3acfa 100644
@@ -152,7 +152,7 @@ static int is_bidirectional_neigh(struct orig_node *orig_node,
 	struct bat_priv *bat_priv = netdev_priv(if_incoming->soft_iface);
 	struct neigh_node *neigh_node = NULL, *tmp_neigh_node = NULL;
 	struct hlist_node *node;
-	unsigned char total_count;
+	uint8_t local_tq = 0, local_rq = 0;
 
 	if (orig_node == orig_neigh_node) {
 		rcu_read_lock();
@@ -199,25 +199,23 @@ static int is_bidirectional_neigh(struct orig_node *orig_node,
 			return 0;
 	}
 
-	orig_node->last_valid = jiffies;
+	/* note, bottom halves are already deactivated outside in
+	 * recv_bat_packet() */
+	spin_lock(&if_incoming->neigh_list_lock);
+	hlist_for_each_entry(neigh_node, node, &if_incoming->neigh_list,
+								list) {
+		if (!compare_orig(neigh_node->addr, orig_neigh_node->orig))
+			continue;
 
-	/* pay attention to not get a value bigger than 100 % */
-	total_count = (orig_neigh_node->bcast_own_sum[if_incoming->if_num] >
-		       neigh_node->real_packet_count ?
-		       neigh_node->real_packet_count :
-		       orig_neigh_node->bcast_own_sum[if_incoming->if_num]);
+		orig_node->last_valid = jiffies;
+		local_tq = neigh_node->tq_avg;
+		local_rq = neigh_node->rq;
+		break;
+	}
+	spin_unlock(&if_incoming->neigh_list_lock);
 
-	/* if we have too few packets (too less data) we set tq_own to zero */
-	/* if we receive too few packets it is not considered bidirectional */
-	if ((total_count < TQ_LOCAL_BIDRECT_SEND_MINIMUM) ||
-	    (neigh_node->real_packet_count < TQ_LOCAL_BIDRECT_RECV_MINIMUM))
-		orig_neigh_node->tq_own = 0;
-	else
-		/* neigh_node->real_packet_count is never zero as we
-		 * only purge old information when getting new
-		 * information */
-		orig_neigh_node->tq_own = (TQ_MAX_VALUE * total_count) /
-			neigh_node->real_packet_count;
+	if (local_tq == 0)
+		return 0;
 
 	/*
 	 * 1 - ((1-x) ** 3), normalized to TQ_MAX_VALUE this does
@@ -228,25 +226,22 @@ static int is_bidirectional_neigh(struct orig_node *orig_node,
 	orig_neigh_node->tq_asym_penalty =
 		TQ_MAX_VALUE -
 		(TQ_MAX_VALUE *
-		 (TQ_LOCAL_WINDOW_SIZE - neigh_node->real_packet_count) *
-		 (TQ_LOCAL_WINDOW_SIZE - neigh_node->real_packet_count) *
-		 (TQ_LOCAL_WINDOW_SIZE - neigh_node->real_packet_count)) /
-		(TQ_LOCAL_WINDOW_SIZE *
-		 TQ_LOCAL_WINDOW_SIZE *
-		 TQ_LOCAL_WINDOW_SIZE);
-
-	ogm_packet->tq = ((ogm_packet->tq *
-			      orig_neigh_node->tq_own *
-			      orig_neigh_node->tq_asym_penalty) /
-			     (TQ_MAX_VALUE * TQ_MAX_VALUE));
+		 (TQ_MAX_VALUE - local_rq) *
+		 (TQ_MAX_VALUE - local_rq) *
+		 (TQ_MAX_VALUE - local_rq)) /
+		(TQ_MAX_VALUE *
+		 TQ_MAX_VALUE *
+		 TQ_MAX_VALUE);
+
+	ogm_packet->tq = ((ogm_packet->tq * local_tq *
+			   orig_neigh_node->tq_asym_penalty) /
+			   (TQ_MAX_VALUE * TQ_MAX_VALUE));
 
 	bat_dbg(DBG_BATMAN, bat_priv,
 		"bidirectional: "
-		"orig = %-15pM neigh = %-15pM => own_bcast = %2i, "
-		"real recv = %2i, local tq: %3i, asym_penalty: %3i, "
-		"total tq: %3i\n",
-		orig_node->orig, orig_neigh_node->orig, total_count,
-		neigh_node->real_packet_count, orig_neigh_node->tq_own,
+		"orig = %-15pM neigh = %-15pM => local tq = %3i, "
+		"local rq: %3i, asym_penalty: %3i, total tq: %3i\n",
+		orig_node->orig, orig_neigh_node->orig, local_tq, local_rq,
 		orig_neigh_node->tq_asym_penalty, ogm_packet->tq);
 
 	/* if link has the minimum required transmission quality
@@ -859,6 +854,7 @@ int recv_bat_packet(struct sk_buff *skb,
 
 	ethhdr = (struct ethhdr *)skb_mac_header(skb);
 
+	/* note, is_bidirectional_neigh() relies on deactivated bottom halves */
 	spin_lock_bh(&bat_priv->orig_hash_lock);
 	receive_aggr_bat_packet(ethhdr,
 				skb->data,
Signature · 1 line
1.7.1
#10 lore raw

PATCH 10/10 batman-adv: Use rcu locking + ref-counting for neigh_list

In reply to Linus Lüssing

With this commit only spinlocking for reading/writing variables inside a neigh_node for NDP is used. The neigh_list traversal and entry deleting/adding is done with rcu-locking and reference counting instead to greatly reduce the time of (concurrent) spinlocking.

---
 ndp.c        |   54 ++++++++++++++++++++++++++++++++++++++----------------
 originator.c |    2 +-
 originator.h |    1 +
 routing.c    |   14 +++++++++-----
 types.h      |    2 ++
 5 files changed, 51 insertions(+), 22 deletions(-)
ndp.c +38 -16
index 9f498f9..0793564 100644
@@ -66,19 +66,23 @@ static void ndp_send(struct work_struct *work)
 	       ETH_ALEN);
 
 	neigh_entry = (struct neigh_entry *)(ndp_packet + 1);
-	spin_lock_bh(&batman_if->neigh_list_lock);
-	hlist_for_each_entry(neigh_node, node, &batman_if->neigh_list, list) {
+	rcu_read_lock();
+	hlist_for_each_entry_rcu(neigh_node, node, &batman_if->neigh_list,
+				 list) {
 		if (entries_len + sizeof(struct neigh_entry) >
 		    skb_tailroom(skb))
 			break;
 
+		spin_lock_bh(&neigh_node->update_lock);
 		memcpy(neigh_entry->addr, neigh_node->addr, ETH_ALEN);
 		neigh_entry->rq = neigh_node->rq;
+		spin_unlock_bh(&neigh_node->update_lock);
+
 		ndp_packet->num_neighbors++;
 		neigh_entry++;
 		entries_len += sizeof(struct neigh_entry);
 	}
-	spin_unlock_bh(&batman_if->neigh_list_lock);
+	rcu_read_unlock();
 	skb_put(skb, entries_len);
 
 	bat_dbg(DBG_BATMAN, bat_priv,
@@ -205,6 +209,9 @@ static struct neigh_node *ndp_create_neighbor(uint8_t my_tq, uint32_t seqno,
 		return NULL;
 
 	INIT_HLIST_NODE(&neigh_node->list);
+	spin_lock_init(&neigh_node->update_lock);
+	kref_init(&neigh_node->refcount);
+
 	memcpy(neigh_node->addr, neigh_addr, ETH_ALEN);
 	neigh_node->last_rq_seqno = seqno - 1;
 
@@ -216,6 +223,7 @@ void ndp_purge_neighbors(void)
 	struct neigh_node *neigh_node;
 	struct hlist_node *node, *node_tmp;
 	struct batman_if *batman_if;
+	unsigned long last_valid;
 
 	rcu_read_lock();
 	list_for_each_entry_rcu(batman_if, &if_list, list) {
@@ -225,13 +233,17 @@ void ndp_purge_neighbors(void)
 		spin_lock_bh(&batman_if->neigh_list_lock);
 		hlist_for_each_entry_safe(neigh_node, node, node_tmp,
 					  &batman_if->neigh_list, list) {
-			if (time_before(jiffies, neigh_node->last_valid +
+			spin_lock(&neigh_node->update_lock);
+			last_valid = neigh_node->last_valid;
+			spin_unlock(&neigh_node->update_lock);
+
+			if (time_before(jiffies, last_valid +
 					msecs_to_jiffies(PURGE_TIMEOUT *
 							 1000)))
 				continue;
 
-			hlist_del(&neigh_node->list);
-			kfree(neigh_node);
+			hlist_del_rcu(&neigh_node->list);
+			call_rcu(&neigh_node->rcu, neigh_node_free_rcu);
 		}
 		spin_unlock_bh(&batman_if->neigh_list_lock);
 	}
@@ -246,16 +258,17 @@ int ndp_update_neighbor(uint8_t my_tq, uint32_t seqno,
 	struct hlist_node *node;
 	int ret = 1;
 
-	spin_lock_bh(&batman_if->neigh_list_lock);
-	/* old neighbor? */
-	hlist_for_each_entry(tmp_neigh_node, node, &batman_if->neigh_list,
+	rcu_read_lock();
+	hlist_for_each_entry_rcu(tmp_neigh_node, node, &batman_if->neigh_list,
 			     list) {
 		if (!compare_orig(tmp_neigh_node->addr, neigh_addr))
 			continue;
 
 		neigh_node = tmp_neigh_node;
+		kref_get(&neigh_node->refcount);
 		break;
 	}
+	rcu_read_unlock();
 
 	/* new neighbor? */
 	if (!neigh_node) {
@@ -264,15 +277,24 @@ int ndp_update_neighbor(uint8_t my_tq, uint32_t seqno,
 		if (!neigh_node)
 			goto ret;
 
-		hlist_add_head(&neigh_node->list, &batman_if->neigh_list);
+		ndp_update_neighbor_lq(my_tq, seqno, neigh_node, bat_priv);
+
+		spin_lock_bh(&batman_if->neigh_list_lock);
+		hlist_add_head_rcu(&neigh_node->list, &batman_if->neigh_list);
+		spin_unlock_bh(&batman_if->neigh_list_lock);
 	}
+	/* old neighbor? */
+	else {
+		spin_lock_bh(&neigh_node->update_lock);
+		ndp_update_neighbor_lq(my_tq, seqno, neigh_node, bat_priv);
+		spin_unlock_bh(&neigh_node->update_lock);
 
-	ndp_update_neighbor_lq(my_tq, seqno, neigh_node, bat_priv);
+		kref_put(&neigh_node->refcount, neigh_node_free_ref);
+	}
 
 	ret = 0;
 
 ret:
-	spin_unlock_bh(&batman_if->neigh_list_lock);
 	return ret;
 }
 
@@ -311,9 +333,9 @@ int ndp_seq_print_text(struct seq_file *seq, void *offset)
 		if (batman_if->if_status != IF_ACTIVE)
 			continue;
 
-		spin_lock_bh(&batman_if->neigh_list_lock);
-		hlist_for_each_entry(neigh_node, node, &batman_if->neigh_list,
-				    list) {
+		hlist_for_each_entry_rcu(neigh_node, node,
+					 &batman_if->neigh_list, list) {
+			spin_lock_bh(&neigh_node->update_lock);
 			last_seen_secs = jiffies_to_msecs(jiffies -
 						neigh_node->last_valid) / 1000;
 			last_seen_msecs = jiffies_to_msecs(jiffies -
@@ -324,9 +346,9 @@ int ndp_seq_print_text(struct seq_file *seq, void *offset)
 				   last_seen_msecs, neigh_node->tq_avg,
 				   neigh_node->rq, batman_if->net_dev->name);
 
+			spin_unlock_bh(&neigh_node->update_lock);
 			batman_count++;
 		}
-		spin_unlock_bh(&batman_if->neigh_list_lock);
 	}
 	rcu_read_unlock();
 
originator.c +1 -1
index e98add5..699dbfc 100644
@@ -68,7 +68,7 @@ void neigh_node_free_ref(struct kref *refcount)
 	kfree(neigh_node);
 }
 
-static void neigh_node_free_rcu(struct rcu_head *rcu)
+void neigh_node_free_rcu(struct rcu_head *rcu)
 {
 	struct neigh_node *neigh_node;
 
originator.h +1 -0
index f3676fa..2a7d68b 100644
@@ -31,6 +31,7 @@ struct neigh_node *create_neighbor(struct orig_node *orig_node,
 				   uint8_t *neigh,
 				   struct batman_if *if_incoming);
 void neigh_node_free_ref(struct kref *refcount);
+void neigh_node_free_rcu(struct rcu_head *rcu);
 int orig_seq_print_text(struct seq_file *seq, void *offset);
 int orig_hash_add_if(struct batman_if *batman_if, int max_if_num);
 int orig_hash_del_if(struct batman_if *batman_if, int max_if_num);
routing.c +9 -5
index 8a3acfa..785ddc2 100644
@@ -199,20 +199,24 @@ static int is_bidirectional_neigh(struct orig_node *orig_node,
 			return 0;
 	}
 
-	/* note, bottom halves are already deactivated outside in
-	 * recv_bat_packet() */
-	spin_lock(&if_incoming->neigh_list_lock);
-	hlist_for_each_entry(neigh_node, node, &if_incoming->neigh_list,
+	rcu_read_lock();
+	hlist_for_each_entry_rcu(neigh_node, node, &if_incoming->neigh_list,
 								list) {
 		if (!compare_orig(neigh_node->addr, orig_neigh_node->orig))
 			continue;
 
 		orig_node->last_valid = jiffies;
+
+		/* note, bottom halves are already deactivated outside in
+		 * recv_bat_packet() */
+		spin_lock(&neigh_node->update_lock);
 		local_tq = neigh_node->tq_avg;
 		local_rq = neigh_node->rq;
+		spin_unlock(&neigh_node->update_lock);
+
 		break;
 	}
-	spin_unlock(&if_incoming->neigh_list_lock);
+	rcu_read_unlock();
 
 	if (local_tq == 0)
 		return 0;
types.h +2 -0
index 43721cf..37c2c58 100644
@@ -129,6 +129,8 @@ struct neigh_node {
 	struct rcu_head rcu;
 	struct orig_node *orig_node;
 	struct batman_if *if_incoming;
+	spinlock_t update_lock;	/* protects last_rq_seqno, ndp_rq_window, rq,
+				   last_valid, tq_avg for NDP */
 };
 
 struct neigh_entry {
Signature · 1 line
1.7.1
#11 lore raw

Re: [B.A.T.M.A.N.] [PATCH 10/10] batman-adv: Use rcu locking + ref-counting for neigh_list

Hey,

and please let me know if you'd like me to merge this commit into the previous ones or if it might be better to leave it like that for easier debugging of potential rcu-locking/refcounting bugs as the simple spinlocking before should be less bug prone, and leaving patch 10/10 as a separate performance improvement patch.

Cheers, Linus

Quoted 232 lines · Linus Lüssing

With this commit only spinlocking for reading/writing variables inside a neigh_node for NDP is used. The neigh_list traversal and entry deleting/adding is done with rcu-locking and reference counting instead to greatly reduce the time of (concurrent) spinlocking.

---
 ndp.c        |   54 ++++++++++++++++++++++++++++++++++++++----------------
 originator.c |    2 +-
 originator.h |    1 +
 routing.c    |   14 +++++++++-----
 types.h      |    2 ++
 5 files changed, 51 insertions(+), 22 deletions(-)
ndp.c +38 -16
index 9f498f9..0793564 100644
@@ -66,19 +66,23 @@ static void ndp_send(struct work_struct *work)
 	       ETH_ALEN);
 
 	neigh_entry = (struct neigh_entry *)(ndp_packet + 1);
-	spin_lock_bh(&batman_if->neigh_list_lock);
-	hlist_for_each_entry(neigh_node, node, &batman_if->neigh_list, list) {
+	rcu_read_lock();
+	hlist_for_each_entry_rcu(neigh_node, node, &batman_if->neigh_list,
+				 list) {
 		if (entries_len + sizeof(struct neigh_entry) >
 		    skb_tailroom(skb))
 			break;
 
+		spin_lock_bh(&neigh_node->update_lock);
 		memcpy(neigh_entry->addr, neigh_node->addr, ETH_ALEN);
 		neigh_entry->rq = neigh_node->rq;
+		spin_unlock_bh(&neigh_node->update_lock);
+
 		ndp_packet->num_neighbors++;
 		neigh_entry++;
 		entries_len += sizeof(struct neigh_entry);
 	}
-	spin_unlock_bh(&batman_if->neigh_list_lock);
+	rcu_read_unlock();
 	skb_put(skb, entries_len);
 
 	bat_dbg(DBG_BATMAN, bat_priv,
@@ -205,6 +209,9 @@ static struct neigh_node *ndp_create_neighbor(uint8_t my_tq, uint32_t seqno,
 		return NULL;
 
 	INIT_HLIST_NODE(&neigh_node->list);
+	spin_lock_init(&neigh_node->update_lock);
+	kref_init(&neigh_node->refcount);
+
 	memcpy(neigh_node->addr, neigh_addr, ETH_ALEN);
 	neigh_node->last_rq_seqno = seqno - 1;
 
@@ -216,6 +223,7 @@ void ndp_purge_neighbors(void)
 	struct neigh_node *neigh_node;
 	struct hlist_node *node, *node_tmp;
 	struct batman_if *batman_if;
+	unsigned long last_valid;
 
 	rcu_read_lock();
 	list_for_each_entry_rcu(batman_if, &if_list, list) {
@@ -225,13 +233,17 @@ void ndp_purge_neighbors(void)
 		spin_lock_bh(&batman_if->neigh_list_lock);
 		hlist_for_each_entry_safe(neigh_node, node, node_tmp,
 					  &batman_if->neigh_list, list) {
-			if (time_before(jiffies, neigh_node->last_valid +
+			spin_lock(&neigh_node->update_lock);
+			last_valid = neigh_node->last_valid;
+			spin_unlock(&neigh_node->update_lock);
+
+			if (time_before(jiffies, last_valid +
 					msecs_to_jiffies(PURGE_TIMEOUT *
 							 1000)))
 				continue;
 
-			hlist_del(&neigh_node->list);
-			kfree(neigh_node);
+			hlist_del_rcu(&neigh_node->list);
+			call_rcu(&neigh_node->rcu, neigh_node_free_rcu);
 		}
 		spin_unlock_bh(&batman_if->neigh_list_lock);
 	}
@@ -246,16 +258,17 @@ int ndp_update_neighbor(uint8_t my_tq, uint32_t seqno,
 	struct hlist_node *node;
 	int ret = 1;
 
-	spin_lock_bh(&batman_if->neigh_list_lock);
-	/* old neighbor? */
-	hlist_for_each_entry(tmp_neigh_node, node, &batman_if->neigh_list,
+	rcu_read_lock();
+	hlist_for_each_entry_rcu(tmp_neigh_node, node, &batman_if->neigh_list,
 			     list) {
 		if (!compare_orig(tmp_neigh_node->addr, neigh_addr))
 			continue;
 
 		neigh_node = tmp_neigh_node;
+		kref_get(&neigh_node->refcount);
 		break;
 	}
+	rcu_read_unlock();
 
 	/* new neighbor? */
 	if (!neigh_node) {
@@ -264,15 +277,24 @@ int ndp_update_neighbor(uint8_t my_tq, uint32_t seqno,
 		if (!neigh_node)
 			goto ret;
 
-		hlist_add_head(&neigh_node->list, &batman_if->neigh_list);
+		ndp_update_neighbor_lq(my_tq, seqno, neigh_node, bat_priv);
+
+		spin_lock_bh(&batman_if->neigh_list_lock);
+		hlist_add_head_rcu(&neigh_node->list, &batman_if->neigh_list);
+		spin_unlock_bh(&batman_if->neigh_list_lock);
 	}
+	/* old neighbor? */
+	else {
+		spin_lock_bh(&neigh_node->update_lock);
+		ndp_update_neighbor_lq(my_tq, seqno, neigh_node, bat_priv);
+		spin_unlock_bh(&neigh_node->update_lock);
 
-	ndp_update_neighbor_lq(my_tq, seqno, neigh_node, bat_priv);
+		kref_put(&neigh_node->refcount, neigh_node_free_ref);
+	}
 
 	ret = 0;
 
 ret:
-	spin_unlock_bh(&batman_if->neigh_list_lock);
 	return ret;
 }
 
@@ -311,9 +333,9 @@ int ndp_seq_print_text(struct seq_file *seq, void *offset)
 		if (batman_if->if_status != IF_ACTIVE)
 			continue;
 
-		spin_lock_bh(&batman_if->neigh_list_lock);
-		hlist_for_each_entry(neigh_node, node, &batman_if->neigh_list,
-				    list) {
+		hlist_for_each_entry_rcu(neigh_node, node,
+					 &batman_if->neigh_list, list) {
+			spin_lock_bh(&neigh_node->update_lock);
 			last_seen_secs = jiffies_to_msecs(jiffies -
 						neigh_node->last_valid) / 1000;
 			last_seen_msecs = jiffies_to_msecs(jiffies -
@@ -324,9 +346,9 @@ int ndp_seq_print_text(struct seq_file *seq, void *offset)
 				   last_seen_msecs, neigh_node->tq_avg,
 				   neigh_node->rq, batman_if->net_dev->name);
 
+			spin_unlock_bh(&neigh_node->update_lock);
 			batman_count++;
 		}
-		spin_unlock_bh(&batman_if->neigh_list_lock);
 	}
 	rcu_read_unlock();
 
originator.c +1 -1
index e98add5..699dbfc 100644
@@ -68,7 +68,7 @@ void neigh_node_free_ref(struct kref *refcount)
 	kfree(neigh_node);
 }
 
-static void neigh_node_free_rcu(struct rcu_head *rcu)
+void neigh_node_free_rcu(struct rcu_head *rcu)
 {
 	struct neigh_node *neigh_node;
 
originator.h +1 -0
index f3676fa..2a7d68b 100644
@@ -31,6 +31,7 @@ struct neigh_node *create_neighbor(struct orig_node *orig_node,
 				   uint8_t *neigh,
 				   struct batman_if *if_incoming);
 void neigh_node_free_ref(struct kref *refcount);
+void neigh_node_free_rcu(struct rcu_head *rcu);
 int orig_seq_print_text(struct seq_file *seq, void *offset);
 int orig_hash_add_if(struct batman_if *batman_if, int max_if_num);
 int orig_hash_del_if(struct batman_if *batman_if, int max_if_num);
routing.c +9 -5
index 8a3acfa..785ddc2 100644
@@ -199,20 +199,24 @@ static int is_bidirectional_neigh(struct orig_node *orig_node,
 			return 0;
 	}
 
-	/* note, bottom halves are already deactivated outside in
-	 * recv_bat_packet() */
-	spin_lock(&if_incoming->neigh_list_lock);
-	hlist_for_each_entry(neigh_node, node, &if_incoming->neigh_list,
+	rcu_read_lock();
+	hlist_for_each_entry_rcu(neigh_node, node, &if_incoming->neigh_list,
 								list) {
 		if (!compare_orig(neigh_node->addr, orig_neigh_node->orig))
 			continue;
 
 		orig_node->last_valid = jiffies;
+
+		/* note, bottom halves are already deactivated outside in
+		 * recv_bat_packet() */
+		spin_lock(&neigh_node->update_lock);
 		local_tq = neigh_node->tq_avg;
 		local_rq = neigh_node->rq;
+		spin_unlock(&neigh_node->update_lock);
+
 		break;
 	}
-	spin_unlock(&if_incoming->neigh_list_lock);
+	rcu_read_unlock();
 
 	if (local_tq == 0)
 		return 0;
types.h +2 -0
index 43721cf..37c2c58 100644
@@ -129,6 +129,8 @@ struct neigh_node {
 	struct rcu_head rcu;
 	struct orig_node *orig_node;
 	struct batman_if *if_incoming;
+	spinlock_t update_lock;	/* protects last_rq_seqno, ndp_rq_window, rq,
+				   last_valid, tq_avg for NDP */
 };
 
 struct neigh_entry {
Signature · 1 line
1.7.1
#12 lore raw
In reply to Linus Lüssing

Hi Linus,

great that you embraced the feedback that quickly. As discussed in Berlin I'll go through your patches once I have a little bit more room to manoeuvre (next week is rather packed).

Quoted 6 lines

Would be great if someone could check the usage of rcu-locking + refcounting. I was also a little confused because in "Documentation/RCU/listRCU.txt" list_del_rcu() and list_add_rcu() are not protected with a spinlock for the list here, but in the batman-adv code we are usually having those extra locks. Do I have to leave those spinlocks or can I remove them for adding/deleting entries in the neigh_list?

I don't understand why you think there are no locks. Did you read the text around the examples (Documentation/RCU/listRCU.txt) ? I mean, below the first example (which indeed does not contain spinlocks) it is written:

Normally, the write_lock() and write_unlock() would be replaced by a spin_lock() and a spin_unlock(), but in this case, all callers hold audit_netlink_sem, so no additional locking is required. The auditsc_lock can therefore be eliminated, since use of RCU eliminates the need for writers to exclude readers. Normally, the write_lock() calls would be converted into spin_lock() calls.

If you check the following example you'll find spinlocks or search for list_del_rcu() in the kernel sources to find more usage scenarios.

Regards,
Marek

#13 lore raw
Quoted 25 lines · Marek Lindner

Hi Linus,

great that you embraced the feedback that quickly. As discussed in Berlin I'll go through your patches once I have a little bit more room to manoeuvre (next week is rather packed).

Quoted 6 lines

Would be great if someone could check the usage of rcu-locking + refcounting. I was also a little confused because in "Documentation/RCU/listRCU.txt" list_del_rcu() and list_add_rcu() are not protected with a spinlock for the list here, but in the batman-adv code we are usually having those extra locks. Do I have to leave those spinlocks or can I remove them for adding/deleting entries in the neigh_list?

I don't understand why you think there are no locks. Did you read the text around the examples (Documentation/RCU/listRCU.txt) ? I mean, below the first example (which indeed does not contain spinlocks) it is written:

Normally, the write_lock() and write_unlock() would be replaced by a spin_lock() and a spin_unlock(), but in this case, all callers hold audit_netlink_sem, so no additional locking is required. The auditsc_lock can therefore be eliminated, since use of RCU eliminates the need for writers to exclude readers. Normally, the write_lock() calls would be converted into spin_lock() calls.

Quoted 6 lines

If you check the following example you'll find spinlocks or search for list_del_rcu() in the kernel sources to find more usage scenarios.

Regards,
Marek

Oki doki, thanks. I was a little confused by the example at that section and couldn't find any other references to "audit_netlink_sem" (though it is/was probably just a common semaphore, I guess). Ok,
quick searching of list_del_rcu() in the kernel code (via http://lxr.linux.no/linux)
cleared things up.

Cheers, Linus

#14 lore raw

Re: [B.A.T.M.A.N.] NDP patches v4y

Quoted 5 lines

Oki doki, thanks. I was a little confused by the example at that section and couldn't find any other references to "audit_netlink_sem" (though it is/was probably just a common semaphore, I guess). Ok,
quick searching of list_del_rcu() in the kernel code (via http://lxr.linux.no/linux)
cleared things up.

You might also find this useful:

http://lwn.net/Articles/421425/

Andrew