diff mbox

[v2,1/4] batman-adv: Keep hard interface neighbor list sorted

Message ID 20161006064142.20003-2-linus.luessing@c0d3.blue (mailing list archive)
State Superseded, archived
Delegated to: Sven Eckelmann
Headers

Commit Message

Linus Lüssing Oct. 6, 2016, 6:41 a.m. UTC 
  The upcoming neighborhood hashing will compute a hash over the MAC
address of all neighbors on an interface, from the smallest to the
largest one.

This patch keeps the hard interface neighbor list in order to ease
the hash computation later.

Signed-off-by: Linus Lüssing <linus.luessing@c0d3.blue>

---

Changes in v2:
* Moved sorted storing of hardif neighbors to this separate patch
* fix rcu bug: use hlist_add_{head,behind}_rcu() instead of their
  non-rcu variants (and rebase on top of Sven's maint patch for the
  original hlist_add_head() )
(thanks Sven!)
---
 net/batman-adv/originator.c | 48 +++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 46 insertions(+), 2 deletions(-)

Comments

Sven Eckelmann Dec. 14, 2016, 6:48 p.m. UTC | #1 
On Donnerstag, 6. Oktober 2016 08:41:38 CET Linus Lüssing wrote:
> +               hlist_add_behind_rcu(&hardif_neigh->list, &pre_neigh->list);

Compat code is missing for this function

ecsv/pu: sparse linux-3.16 cfg: BLA=n DAT=n DEBUGFS=y DEBUG=y NC=n MCAST=n BATMAN_V=y
---------------------------------------------------------------------------

    /home/build_test/build_env/tmp.YwQkM10Q6k/build/net/batman-adv/bat_v_elp.c:96:9: warning: Variable length array is used.
    /home/build_test/build_env/tmp.YwQkM10Q6k/build/net/batman-adv/originator.c:594:17: error: undefined identifier 'hlist_add_behind_rcu'
    /home/build_test/build_env/tmp.YwQkM10Q6k/build/net/batman-adv/originator.c: In function 'batadv_hardif_neigh_create':
    /home/build_test/build_env/tmp.YwQkM10Q6k/build/net/batman-adv/originator.c:594:3: error: implicit declaration of function 'hlist_add_behind_rcu' [-Werror=implicit-function-declaration]
       hlist_add_behind_rcu(&hardif_neigh->list, &pre_neigh->list);

Kind regards,
	Sven
Sven Eckelmann Dec. 14, 2016, 7:23 p.m. UTC | #2 
On Mittwoch, 14. Dezember 2016 19:48:19 CET Sven Eckelmann wrote:
> On Donnerstag, 6. Oktober 2016 08:41:38 CET Linus Lüssing wrote:
> > +               hlist_add_behind_rcu(&hardif_neigh->list, &pre_neigh->list);
> 
> Compat code is missing for this function
> 
> ecsv/pu: sparse linux-3.16 cfg: BLA=n DAT=n DEBUGFS=y DEBUG=y NC=n MCAST=n BATMAN_V=y
> ---------------------------------------------------------------------------
> 
>     /home/build_test/build_env/tmp.YwQkM10Q6k/build/net/batman-adv/bat_v_elp.c:96:9: warning: Variable length array is used.
>     /home/build_test/build_env/tmp.YwQkM10Q6k/build/net/batman-adv/originator.c:594:17: error: undefined identifier 'hlist_add_behind_rcu'
>     /home/build_test/build_env/tmp.YwQkM10Q6k/build/net/batman-adv/originator.c: In function 'batadv_hardif_neigh_create':
>     /home/build_test/build_env/tmp.YwQkM10Q6k/build/net/batman-adv/originator.c:594:3: error: implicit declaration of function 'hlist_add_behind_rcu' [-Werror=implicit-function-declaration]
>        hlist_add_behind_rcu(&hardif_neigh->list, &pre_neigh->list);

I have now added the compat code together with some include fixes to ecsv/pu

    diff --git a/compat-include/linux/rculist.h b/compat-include/linux/rculist.h
    index d432bc65..3c7ae76b 100644
    --- a/compat-include/linux/rculist.h
    +++ b/compat-include/linux/rculist.h
    @@ -36,4 +36,10 @@
     
     #endif
     
    +#if LINUX_VERSION_CODE < KERNEL_VERSION(3, 17, 0)
    +
    +#define hlist_add_behind_rcu(n, prev) hlist_add_after_rcu(prev, n)
    +
    +#endif /* < KERNEL_VERSION(3, 17, 0) */
    +
     #endif	/* _NET_BATMAN_ADV_COMPAT_LINUX_RCULIST_H_ */
    diff --git a/net/batman-adv/bat_v_elp.c b/net/batman-adv/bat_v_elp.c
    index 712bd428..a69614f5 100644
    --- a/net/batman-adv/bat_v_elp.c
    +++ b/net/batman-adv/bat_v_elp.c
    @@ -19,10 +19,10 @@
     #include "main.h"
     
     #include <crypto/hash.h>
    -#include <crypto/sha.h>
     #include <linux/atomic.h>
    +#include <linux/bug.h>
     #include <linux/byteorder/generic.h>
    -#include <linux/err.h>
    +#include <linux/device.h>
     #include <linux/errno.h>
     #include <linux/etherdevice.h>
     #include <linux/ethtool.h>

Kind regards,
	Sven
Linus Lüssing Jan. 28, 2017, 3:13 a.m. UTC | #3 
On Wed, Dec 14, 2016 at 08:23:19PM +0100, Sven Eckelmann wrote:
>     diff --git a/net/batman-adv/bat_v_elp.c b/net/batman-adv/bat_v_elp.c
>     index 712bd428..a69614f5 100644
>     --- a/net/batman-adv/bat_v_elp.c
>     +++ b/net/batman-adv/bat_v_elp.c
>     @@ -19,10 +19,10 @@
>      #include "main.h"
>      
>      #include <crypto/hash.h>
>     -#include <crypto/sha.h>
>      #include <linux/atomic.h>
>     +#include <linux/bug.h>
>      #include <linux/byteorder/generic.h>
>     -#include <linux/err.h>
>     +#include <linux/device.h>
>      #include <linux/errno.h>
>      #include <linux/etherdevice.h>
>      #include <linux/ethtool.h>

Hm, do you remember what you were adding bug.h and device.h for?
Also, err.h seems to be needed for IS_ERR() and PTR_ERR().

Regards, Linus
Linus Lüssing Jan. 28, 2017, 3:40 a.m. UTC | #4 
On Sat, Jan 28, 2017 at 04:13:11AM +0100, Linus Lüssing wrote:
> On Wed, Dec 14, 2016 at 08:23:19PM +0100, Sven Eckelmann wrote:
> >     diff --git a/net/batman-adv/bat_v_elp.c b/net/batman-adv/bat_v_elp.c
> >     index 712bd428..a69614f5 100644
> >     --- a/net/batman-adv/bat_v_elp.c
> >     +++ b/net/batman-adv/bat_v_elp.c
> >     @@ -19,10 +19,10 @@
> >      #include "main.h"
> >      
> >      #include <crypto/hash.h>
> >     -#include <crypto/sha.h>
> >      #include <linux/atomic.h>
> >     +#include <linux/bug.h>
> >      #include <linux/byteorder/generic.h>
> >     -#include <linux/err.h>
> >     +#include <linux/device.h>
> >      #include <linux/errno.h>
> >      #include <linux/etherdevice.h>
> >      #include <linux/ethtool.h>
> 
> Hm, do you remember what you were adding bug.h and device.h for?
> Also, err.h seems to be needed for IS_ERR() and PTR_ERR().

Ok, found bug.h is needed for WARN_ON() in the third patch. The
device.h addition and err.h removal still leave me clueless
though.
Sven Eckelmann Jan. 28, 2017, 9:07 a.m. UTC | #5 
On Samstag, 28. Januar 2017 04:40:50 CET Linus Lüssing wrote:
[...]
> Ok, found bug.h is needed for WARN_ON() in the third patch. The
> device.h addition and err.h removal still leave me clueless
> though.

Looks like an copy + paste error in testhelpers/kernel_mappings.iwyu [1].
Your version was therefore correct and my change was incorrect.

Thanks for checking the headers and reporting the problem.

Kind regards,
	Sven

[1] https://git.open-mesh.org/build_test.git/commit/cc571792fca7a4d15def67d3359863828313e173
diff mbox

Patch

diff --git a/net/batman-adv/originator.c b/net/batman-adv/originator.c
index 8e1ea27..9aaebaf 100644
--- a/net/batman-adv/originator.c
+++ b/net/batman-adv/originator.c
@@ -509,6 +509,43 @@  batadv_neigh_node_get(const struct batadv_orig_node *orig_node,
 }
 
 /**
+ * batadv_hardif_neigh_get_pre - get the predecessor of a neighbor node
+ * @hard_iface: the interface this neighbour is connected to
+ * @neigh_addr: address of the neighbour to retrieve the predecessor for
+ *
+ * Tries to find the neighbor node which has an address closest to but
+ * smaller than the neigh_addr provided. In other words, tries to
+ * find a potential predecessor of a given MAC address.
+ *
+ * Return: The alphabetical predecessor of a neighbor node. Returns NULL
+ * if no such predecessor exists.
+ */
+static struct batadv_hardif_neigh_node *
+batadv_hardif_neigh_get_pre(struct batadv_hard_iface *hard_iface,
+			    const u8 *neigh_addr)
+{
+	struct batadv_hardif_neigh_node *tmp_hardif_neigh, *hardif_neigh = NULL;
+
+	rcu_read_lock();
+	hlist_for_each_entry_rcu(tmp_hardif_neigh, &hard_iface->neigh_list,
+				 list) {
+		if (memcmp(tmp_hardif_neigh->addr, neigh_addr, ETH_ALEN) >= 0)
+			break;
+
+		if (!kref_get_unless_zero(&tmp_hardif_neigh->refcount))
+			continue;
+
+		if (hardif_neigh)
+			batadv_hardif_neigh_put(hardif_neigh);
+
+		hardif_neigh = tmp_hardif_neigh;
+	}
+	rcu_read_unlock();
+
+	return hardif_neigh;
+}
+
+/**
  * batadv_hardif_neigh_create - create a hardif neighbour node
  * @hard_iface: the interface this neighbour is connected to
  * @neigh_addr: the interface address of the neighbour to retrieve
@@ -522,7 +559,7 @@  batadv_hardif_neigh_create(struct batadv_hard_iface *hard_iface,
 			   struct batadv_orig_node *orig_node)
 {
 	struct batadv_priv *bat_priv = netdev_priv(hard_iface->soft_iface);
-	struct batadv_hardif_neigh_node *hardif_neigh = NULL;
+	struct batadv_hardif_neigh_node *hardif_neigh = NULL, *pre_neigh;
 
 	spin_lock_bh(&hard_iface->neigh_list_lock);
 
@@ -547,7 +584,14 @@  batadv_hardif_neigh_create(struct batadv_hard_iface *hard_iface,
 	if (bat_priv->algo_ops->neigh.hardif_init)
 		bat_priv->algo_ops->neigh.hardif_init(hardif_neigh);
 
-	hlist_add_head_rcu(&hardif_neigh->list, &hard_iface->neigh_list);
+	pre_neigh = batadv_hardif_neigh_get_pre(hard_iface, neigh_addr);
+	if (!pre_neigh) {
+		hlist_add_head_rcu(&hardif_neigh->list,
+				   &hard_iface->neigh_list);
+	} else {
+		hlist_add_behind_rcu(&hardif_neigh->list, &pre_neigh->list);
+		batadv_hardif_neigh_put(pre_neigh);
+	}
 
 out:
 	spin_unlock_bh(&hard_iface->neigh_list_lock);