[PATCH net-next v3 0/2] Improve neigh_flush_dev performance

[PATCH net-next v3 0/2] Improve neigh_flush_dev performance

[Gilad Naaman]

From: Gilad Naaman <gilad@naaman.io>

This patchsets improves the performance of neigh_flush_dev.

Currently, the only way to implement it requires traversing
all neighbours known to the kernel, across all network-namespaces.

This means that some flows are slowed down as a function of neighbour-scale,
even if the specific link they're handling has little to no neighbours.

In order to solve this, this patchset adds a netdev->neighbours list,
as well as making the original linked-list doubly-, so that it is
possible to unlink neighbours without traversing the hash-bucket to
obtain the previous neighbour.

The original use-case we encountered was mass-deletion of links (12K
VLANs) while there are 50K ARPs and 50K NDPs in the system; though the
slowdowns would also appear when the links are set down.

Changes in v3:

 - Fix rcu_torture failures (misusage of _protected)
 - Convert first/next access to for-each macros where appropriate

Gilad Naaman (2):
  Convert neighbour-table to use hlist
  Create netdev->neighbour association

 .../networking/net_cachelines/net_device.rst  |   1 +
 include/linux/netdevice.h                     |   6 +
 include/net/neighbour.h                       |  18 +-
 include/net/neighbour_tables.h                |  13 +
 net/core/neighbour.c                          | 272 ++++++++++--------
 5 files changed, 176 insertions(+), 134 deletions(-)
 create mode 100644 include/net/neighbour_tables.h

-- 
2.46.0

[PATCH net-next v3 1/2] Convert neighbour-table to use hlist

[Gilad Naaman]

Use doubly-linked instead of singly-linked list when linking neighbours,
so that it is possible to remove neighbours without traversing the
entire table.

Signed-off-by: Gilad Naaman <gnaaman@drivenets.com>
---
 include/net/neighbour.h |   8 +-
 net/core/neighbour.c    | 162 ++++++++++++++++------------------------
 2 files changed, 68 insertions(+), 102 deletions(-)

diff --git a/include/net/neighbour.h b/include/net/neighbour.h
index a44f262a7384..93903f9854f9 100644
--- a/include/net/neighbour.h
+++ b/include/net/neighbour.h
@@ -135,7 +135,7 @@ struct neigh_statistics {
 #define NEIGH_CACHE_STAT_INC(tbl, field) this_cpu_inc((tbl)->stats->field)
 
 struct neighbour {
-	struct neighbour __rcu	*next;
+	struct hlist_node	list;
 	struct neigh_table	*tbl;
 	struct neigh_parms	*parms;
 	unsigned long		confirmed;
@@ -190,7 +190,7 @@ struct pneigh_entry {
 #define NEIGH_NUM_HASH_RND	4
 
 struct neigh_hash_table {
-	struct neighbour __rcu	**hash_buckets;
+	struct hlist_head	*hash_buckets;
 	unsigned int		hash_shift;
 	__u32			hash_rnd[NEIGH_NUM_HASH_RND];
 	struct rcu_head		rcu;
@@ -304,9 +304,7 @@ static inline struct neighbour *___neigh_lookup_noref(
 	u32 hash_val;
 
 	hash_val = hash(pkey, dev, nht->hash_rnd) >> (32 - nht->hash_shift);
-	for (n = rcu_dereference(nht->hash_buckets[hash_val]);
-	     n != NULL;
-	     n = rcu_dereference(n->next)) {
+	hlist_for_each_entry_rcu(n, &nht->hash_buckets[hash_val], list) {
 		if (n->dev == dev && key_eq(n, pkey))
 			return n;
 	}
diff --git a/net/core/neighbour.c b/net/core/neighbour.c
index 77b819cd995b..bf7f69b585d6 100644
--- a/net/core/neighbour.c
+++ b/net/core/neighbour.c
@@ -37,6 +37,7 @@
 #include <linux/string.h>
 #include <linux/log2.h>
 #include <linux/inetdevice.h>
+#include <linux/rculist.h>
 #include <net/addrconf.h>
 
 #include <trace/events/neigh.h>
@@ -57,6 +58,26 @@ static void neigh_update_notify(struct neighbour *neigh, u32 nlmsg_pid);
 static int pneigh_ifdown_and_unlock(struct neigh_table *tbl,
 				    struct net_device *dev);
 
+#define neigh_hlist_entry(n) hlist_entry_safe(n, struct neighbour, list)
+
+#define neigh_for_each_rcu(pos, head, cond...) \
+	hlist_for_each_entry_rcu(pos, head, list, ##cond)
+
+#define neigh_for_each_safe_rcu_protected(pos, n, head, c)		\
+	for (pos = neigh_first_rcu_protected(head, c);			\
+	     pos && ({ n = neigh_next_rcu_protected(pos, c); 1; });	\
+	     pos = n)
+
+#define neigh_first_rcu(bucket) \
+	neigh_hlist_entry(rcu_dereference(hlist_first_rcu(bucket)))
+#define neigh_next_rcu(n) \
+	neigh_hlist_entry(rcu_dereference(hlist_next_rcu(&(n)->list)))
+
+#define neigh_first_rcu_protected(head, c) \
+	neigh_hlist_entry(rcu_dereference_protected(hlist_first_rcu(head), c))
+#define neigh_next_rcu_protected(n, c) \
+	neigh_hlist_entry(rcu_dereference_protected(hlist_next_rcu(&(n)->list), c))
+
 #ifdef CONFIG_PROC_FS
 static const struct seq_operations neigh_stat_seq_ops;
 #endif
@@ -205,18 +226,13 @@ static void neigh_update_flags(struct neighbour *neigh, u32 flags, int *notify,
 	}
 }
 
-static bool neigh_del(struct neighbour *n, struct neighbour __rcu **np,
-		      struct neigh_table *tbl)
+static bool neigh_del(struct neighbour *n, struct neigh_table *tbl)
 {
 	bool retval = false;
 
 	write_lock(&n->lock);
 	if (refcount_read(&n->refcnt) == 1) {
-		struct neighbour *neigh;
-
-		neigh = rcu_dereference_protected(n->next,
-						  lockdep_is_held(&tbl->lock));
-		rcu_assign_pointer(*np, neigh);
+		hlist_del_rcu(&n->list);
 		neigh_mark_dead(n);
 		retval = true;
 	}
@@ -228,25 +244,7 @@ static bool neigh_del(struct neighbour *n, struct neighbour __rcu **np,
 
 bool neigh_remove_one(struct neighbour *ndel, struct neigh_table *tbl)
 {
-	struct neigh_hash_table *nht;
-	void *pkey = ndel->primary_key;
-	u32 hash_val;
-	struct neighbour *n;
-	struct neighbour __rcu **np;
-
-	nht = rcu_dereference_protected(tbl->nht,
-					lockdep_is_held(&tbl->lock));
-	hash_val = tbl->hash(pkey, ndel->dev, nht->hash_rnd);
-	hash_val = hash_val >> (32 - nht->hash_shift);
-
-	np = &nht->hash_buckets[hash_val];
-	while ((n = rcu_dereference_protected(*np,
-					      lockdep_is_held(&tbl->lock)))) {
-		if (n == ndel)
-			return neigh_del(n, np, tbl);
-		np = &n->next;
-	}
-	return false;
+	return neigh_del(ndel, tbl);
 }
 
 static int neigh_forced_gc(struct neigh_table *tbl)
@@ -387,22 +385,18 @@ static void neigh_flush_dev(struct neigh_table *tbl, struct net_device *dev,
 					lockdep_is_held(&tbl->lock));
 
 	for (i = 0; i < (1 << nht->hash_shift); i++) {
-		struct neighbour *n;
-		struct neighbour __rcu **np = &nht->hash_buckets[i];
+		struct neighbour *n, *next;
 
-		while ((n = rcu_dereference_protected(*np,
-					lockdep_is_held(&tbl->lock))) != NULL) {
+		neigh_for_each_safe_rcu_protected(n, next,
+						  &nht->hash_buckets[i],
+						  lockdep_is_held(&tbl->lock)) {
 			if (dev && n->dev != dev) {
-				np = &n->next;
 				continue;
 			}
 			if (skip_perm && n->nud_state & NUD_PERMANENT) {
-				np = &n->next;
 				continue;
 			}
-			rcu_assign_pointer(*np,
-				   rcu_dereference_protected(n->next,
-						lockdep_is_held(&tbl->lock)));
+			hlist_del_rcu(&n->list);
 			write_lock(&n->lock);
 			neigh_del_timer(n);
 			neigh_mark_dead(n);
@@ -530,9 +524,9 @@ static void neigh_get_hash_rnd(u32 *x)
 
 static struct neigh_hash_table *neigh_hash_alloc(unsigned int shift)
 {
-	size_t size = (1 << shift) * sizeof(struct neighbour *);
+	size_t size = (1 << shift) * sizeof(struct hlist_head);
 	struct neigh_hash_table *ret;
-	struct neighbour __rcu **buckets;
+	struct hlist_head *buckets;
 	int i;
 
 	ret = kmalloc(sizeof(*ret), GFP_ATOMIC);
@@ -541,7 +535,7 @@ static struct neigh_hash_table *neigh_hash_alloc(unsigned int shift)
 	if (size <= PAGE_SIZE) {
 		buckets = kzalloc(size, GFP_ATOMIC);
 	} else {
-		buckets = (struct neighbour __rcu **)
+		buckets = (struct hlist_head *)
 			  __get_free_pages(GFP_ATOMIC | __GFP_ZERO,
 					   get_order(size));
 		kmemleak_alloc(buckets, size, 1, GFP_ATOMIC);
@@ -562,8 +556,8 @@ static void neigh_hash_free_rcu(struct rcu_head *head)
 	struct neigh_hash_table *nht = container_of(head,
 						    struct neigh_hash_table,
 						    rcu);
-	size_t size = (1 << nht->hash_shift) * sizeof(struct neighbour *);
-	struct neighbour __rcu **buckets = nht->hash_buckets;
+	size_t size = (1 << nht->hash_shift) * sizeof(struct hlist_head);
+	struct hlist_head *buckets = nht->hash_buckets;
 
 	if (size <= PAGE_SIZE) {
 		kfree(buckets);
@@ -591,7 +585,7 @@ static struct neigh_hash_table *neigh_hash_grow(struct neigh_table *tbl,
 	for (i = 0; i < (1 << old_nht->hash_shift); i++) {
 		struct neighbour *n, *next;
 
-		for (n = rcu_dereference_protected(old_nht->hash_buckets[i],
+		for (n = neigh_first_rcu_protected(&old_nht->hash_buckets[i],
 						   lockdep_is_held(&tbl->lock));
 		     n != NULL;
 		     n = next) {
@@ -599,14 +593,9 @@ static struct neigh_hash_table *neigh_hash_grow(struct neigh_table *tbl,
 					 new_nht->hash_rnd);
 
 			hash >>= (32 - new_nht->hash_shift);
-			next = rcu_dereference_protected(n->next,
-						lockdep_is_held(&tbl->lock));
-
-			rcu_assign_pointer(n->next,
-					   rcu_dereference_protected(
-						new_nht->hash_buckets[hash],
-						lockdep_is_held(&tbl->lock)));
-			rcu_assign_pointer(new_nht->hash_buckets[hash], n);
+			next = neigh_next_rcu_protected(n, lockdep_is_held(&tbl->lock));
+			hlist_del_rcu(&n->list);
+			hlist_add_head_rcu(&n->list, &new_nht->hash_buckets[hash]);
 		}
 	}
 
@@ -693,11 +682,9 @@ ___neigh_create(struct neigh_table *tbl, const void *pkey,
 		goto out_tbl_unlock;
 	}
 
-	for (n1 = rcu_dereference_protected(nht->hash_buckets[hash_val],
-					    lockdep_is_held(&tbl->lock));
-	     n1 != NULL;
-	     n1 = rcu_dereference_protected(n1->next,
-			lockdep_is_held(&tbl->lock))) {
+	neigh_for_each_rcu(n1,
+			   &nht->hash_buckets[hash_val],
+			   lockdep_is_held(&tbl->lock)) {
 		if (dev == n1->dev && !memcmp(n1->primary_key, n->primary_key, key_len)) {
 			if (want_ref)
 				neigh_hold(n1);
@@ -713,10 +700,7 @@ ___neigh_create(struct neigh_table *tbl, const void *pkey,
 		list_add_tail(&n->managed_list, &n->tbl->managed_list);
 	if (want_ref)
 		neigh_hold(n);
-	rcu_assign_pointer(n->next,
-			   rcu_dereference_protected(nht->hash_buckets[hash_val],
-						     lockdep_is_held(&tbl->lock)));
-	rcu_assign_pointer(nht->hash_buckets[hash_val], n);
+	hlist_add_head_rcu(&n->list, &nht->hash_buckets[hash_val]);
 	write_unlock_bh(&tbl->lock);
 	neigh_dbg(2, "neigh %p is created\n", n);
 	rc = n;
@@ -948,8 +932,7 @@ static void neigh_connect(struct neighbour *neigh)
 static void neigh_periodic_work(struct work_struct *work)
 {
 	struct neigh_table *tbl = container_of(work, struct neigh_table, gc_work.work);
-	struct neighbour *n;
-	struct neighbour __rcu **np;
+	struct neighbour *n, *next;
 	unsigned int i;
 	struct neigh_hash_table *nht;
 
@@ -976,10 +959,9 @@ static void neigh_periodic_work(struct work_struct *work)
 		goto out;
 
 	for (i = 0 ; i < (1 << nht->hash_shift); i++) {
-		np = &nht->hash_buckets[i];
-
-		while ((n = rcu_dereference_protected(*np,
-				lockdep_is_held(&tbl->lock))) != NULL) {
+		neigh_for_each_safe_rcu_protected(n, next,
+						  &nht->hash_buckets[i],
+						  lockdep_is_held(&tbl->lock)) {
 			unsigned int state;
 
 			write_lock(&n->lock);
@@ -988,7 +970,7 @@ static void neigh_periodic_work(struct work_struct *work)
 			if ((state & (NUD_PERMANENT | NUD_IN_TIMER)) ||
 			    (n->flags & NTF_EXT_LEARNED)) {
 				write_unlock(&n->lock);
-				goto next_elt;
+				continue;
 			}
 
 			if (time_before(n->used, n->confirmed) &&
@@ -999,18 +981,13 @@ static void neigh_periodic_work(struct work_struct *work)
 			    (state == NUD_FAILED ||
 			     !time_in_range_open(jiffies, n->used,
 						 n->used + NEIGH_VAR(n->parms, GC_STALETIME)))) {
-				rcu_assign_pointer(*np,
-					rcu_dereference_protected(n->next,
-						lockdep_is_held(&tbl->lock)));
+				hlist_del_rcu(&n->list);
 				neigh_mark_dead(n);
 				write_unlock(&n->lock);
 				neigh_cleanup_and_release(n);
 				continue;
 			}
 			write_unlock(&n->lock);
-
-next_elt:
-			np = &n->next;
 		}
 		/*
 		 * It's fine to release lock here, even if hash table
@@ -2728,9 +2705,8 @@ static int neigh_dump_table(struct neigh_table *tbl, struct sk_buff *skb,
 	for (h = s_h; h < (1 << nht->hash_shift); h++) {
 		if (h > s_h)
 			s_idx = 0;
-		for (n = rcu_dereference(nht->hash_buckets[h]), idx = 0;
-		     n != NULL;
-		     n = rcu_dereference(n->next)) {
+		idx = 0;
+		neigh_for_each_rcu(n, &nht->hash_buckets[h]) {
 			if (idx < s_idx || !net_eq(dev_net(n->dev), net))
 				goto next;
 			if (neigh_ifindex_filtered(n->dev, filter->dev_idx) ||
@@ -3097,9 +3073,7 @@ void neigh_for_each(struct neigh_table *tbl, void (*cb)(struct neighbour *, void
 	for (chain = 0; chain < (1 << nht->hash_shift); chain++) {
 		struct neighbour *n;
 
-		for (n = rcu_dereference(nht->hash_buckets[chain]);
-		     n != NULL;
-		     n = rcu_dereference(n->next))
+		neigh_for_each_rcu(n, &nht->hash_buckets[chain])
 			cb(n, cookie);
 	}
 	read_unlock_bh(&tbl->lock);
@@ -3117,23 +3091,19 @@ void __neigh_for_each_release(struct neigh_table *tbl,
 	nht = rcu_dereference_protected(tbl->nht,
 					lockdep_is_held(&tbl->lock));
 	for (chain = 0; chain < (1 << nht->hash_shift); chain++) {
-		struct neighbour *n;
-		struct neighbour __rcu **np;
+		struct neighbour *n, *next;
 
-		np = &nht->hash_buckets[chain];
-		while ((n = rcu_dereference_protected(*np,
-					lockdep_is_held(&tbl->lock))) != NULL) {
+		neigh_for_each_safe_rcu_protected(n, next,
+						  &nht->hash_buckets[chain],
+						  lockdep_is_held(&tbl->lock)) {
 			int release;
 
 			write_lock(&n->lock);
 			release = cb(n);
 			if (release) {
-				rcu_assign_pointer(*np,
-					rcu_dereference_protected(n->next,
-						lockdep_is_held(&tbl->lock)));
+				hlist_del_rcu(&n->list);
 				neigh_mark_dead(n);
-			} else
-				np = &n->next;
+			}
 			write_unlock(&n->lock);
 			if (release)
 				neigh_cleanup_and_release(n);
@@ -3200,25 +3170,21 @@ static struct neighbour *neigh_get_first(struct seq_file *seq)
 
 	state->flags &= ~NEIGH_SEQ_IS_PNEIGH;
 	for (bucket = 0; bucket < (1 << nht->hash_shift); bucket++) {
-		n = rcu_dereference(nht->hash_buckets[bucket]);
-
-		while (n) {
+		neigh_for_each_rcu(n, &nht->hash_buckets[bucket]) {
 			if (!net_eq(dev_net(n->dev), net))
-				goto next;
+				continue;
 			if (state->neigh_sub_iter) {
 				loff_t fakep = 0;
 				void *v;
 
 				v = state->neigh_sub_iter(state, n, &fakep);
 				if (!v)
-					goto next;
+					continue;
 			}
 			if (!(state->flags & NEIGH_SEQ_SKIP_NOARP))
 				break;
 			if (READ_ONCE(n->nud_state) & ~NUD_NOARP)
 				break;
-next:
-			n = rcu_dereference(n->next);
 		}
 
 		if (n)
@@ -3242,7 +3208,8 @@ static struct neighbour *neigh_get_next(struct seq_file *seq,
 		if (v)
 			return n;
 	}
-	n = rcu_dereference(n->next);
+
+	n = neigh_next_rcu(n);
 
 	while (1) {
 		while (n) {
@@ -3260,7 +3227,8 @@ static struct neighbour *neigh_get_next(struct seq_file *seq,
 			if (READ_ONCE(n->nud_state) & ~NUD_NOARP)
 				break;
 next:
-			n = rcu_dereference(n->next);
+
+			n = neigh_next_rcu(n);
 		}
 
 		if (n)
@@ -3269,7 +3237,7 @@ static struct neighbour *neigh_get_next(struct seq_file *seq,
 		if (++state->bucket >= (1 << nht->hash_shift))
 			break;
 
-		n = rcu_dereference(nht->hash_buckets[state->bucket]);
+		n = neigh_first_rcu(&nht->hash_buckets[state->bucket]);
 	}
 
 	if (n && pos)
-- 
2.46.0

[PATCH net-next v3 2/2] Create netdev->neighbour association

[Gilad Naaman]

Create a mapping between a netdev and its neighoburs,
allowing for much cheaper flushes.

Signed-off-by: Gilad Naaman <gnaaman@drivenets.com>
---
 .../networking/net_cachelines/net_device.rst  |   1 +
 include/linux/netdevice.h                     |   6 +
 include/net/neighbour.h                       |  10 +-
 include/net/neighbour_tables.h                |  13 ++
 net/core/neighbour.c                          | 112 ++++++++++++++----
 5 files changed, 109 insertions(+), 33 deletions(-)
 create mode 100644 include/net/neighbour_tables.h

diff --git a/Documentation/networking/net_cachelines/net_device.rst b/Documentation/networking/net_cachelines/net_device.rst
index 1b018ac35e9a..889501a16da2 100644
--- a/Documentation/networking/net_cachelines/net_device.rst
+++ b/Documentation/networking/net_cachelines/net_device.rst
@@ -186,4 +186,5 @@ struct dpll_pin*                    dpll_pin
 struct hlist_head                   page_pools
 struct dim_irq_moder*               irq_moder
 u64                                 max_pacing_offload_horizon
+struct hlist_head                   neighbours[3]
 =================================== =========================== =================== =================== ===================================================================================
diff --git a/include/linux/netdevice.h b/include/linux/netdevice.h
index 3baf8e539b6f..900977881007 100644
--- a/include/linux/netdevice.h
+++ b/include/linux/netdevice.h
@@ -52,6 +52,7 @@
 #include <net/net_trackers.h>
 #include <net/net_debug.h>
 #include <net/dropreason-core.h>
+#include <net/neighbour_tables.h>
 
 struct netpoll_info;
 struct device;
@@ -2011,6 +2012,9 @@ enum netdev_reg_state {
  *
  *	@max_pacing_offload_horizon: max EDT offload horizon in nsec.
  *
+ *	@neighbours:	List heads pointing to this device's neighbours'
+ *			dev_list, one per address-family.
+ *
  *	FIXME: cleanup struct net_device such that network protocol info
  *	moves out.
  */
@@ -2406,6 +2410,8 @@ struct net_device {
 
 	u64			max_pacing_offload_horizon;
 
+	struct hlist_head neighbours[NEIGH_NR_TABLES];
+
 	u8			priv[] ____cacheline_aligned
 				       __counted_by(priv_len);
 } ____cacheline_aligned;
diff --git a/include/net/neighbour.h b/include/net/neighbour.h
index 93903f9854f9..f86f552e1860 100644
--- a/include/net/neighbour.h
+++ b/include/net/neighbour.h
@@ -29,6 +29,7 @@
 #include <linux/sysctl.h>
 #include <linux/workqueue.h>
 #include <net/rtnetlink.h>
+#include <net/neighbour_tables.h>
 
 /*
  * NUD stands for "neighbor unreachability detection"
@@ -136,6 +137,7 @@ struct neigh_statistics {
 
 struct neighbour {
 	struct hlist_node	list;
+	struct hlist_node	dev_list;
 	struct neigh_table	*tbl;
 	struct neigh_parms	*parms;
 	unsigned long		confirmed;
@@ -236,14 +238,6 @@ struct neigh_table {
 	struct pneigh_entry	**phash_buckets;
 };
 
-enum {
-	NEIGH_ARP_TABLE = 0,
-	NEIGH_ND_TABLE = 1,
-	NEIGH_DN_TABLE = 2,
-	NEIGH_NR_TABLES,
-	NEIGH_LINK_TABLE = NEIGH_NR_TABLES /* Pseudo table for neigh_xmit */
-};
-
 static inline int neigh_parms_family(struct neigh_parms *p)
 {
 	return p->tbl->family;
diff --git a/include/net/neighbour_tables.h b/include/net/neighbour_tables.h
new file mode 100644
index 000000000000..ad98b49d58db
--- /dev/null
+++ b/include/net/neighbour_tables.h
@@ -0,0 +1,13 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+#ifndef _NET_NEIGHBOUR_TABLES_H
+#define _NET_NEIGHBOUR_TABLES_H
+
+enum {
+	NEIGH_ARP_TABLE = 0,
+	NEIGH_ND_TABLE = 1,
+	NEIGH_DN_TABLE = 2,
+	NEIGH_NR_TABLES,
+	NEIGH_LINK_TABLE = NEIGH_NR_TABLES /* Pseudo table for neigh_xmit */
+};
+
+#endif
diff --git a/net/core/neighbour.c b/net/core/neighbour.c
index bf7f69b585d6..5f467040c32c 100644
--- a/net/core/neighbour.c
+++ b/net/core/neighbour.c
@@ -78,10 +78,36 @@ static int pneigh_ifdown_and_unlock(struct neigh_table *tbl,
 #define neigh_next_rcu_protected(n, c) \
 	neigh_hlist_entry(rcu_dereference_protected(hlist_next_rcu(&(n)->list), c))
 
+#define neigh_hlist_dev_entry(n) hlist_entry_safe(n, struct neighbour, dev_list)
+
+#define neigh_dev_first_rcu_protected(head, c) \
+	neigh_hlist_dev_entry(rcu_dereference_protected(hlist_first_rcu(head), c))
+#define neigh_dev_next_rcu_protected(n, c) \
+	neigh_hlist_dev_entry(rcu_dereference_protected(hlist_next_rcu(&(n)->dev_list), c))
+
+#define neigh_dev_for_each_safe_rcu_protected(pos, n, head, c)		\
+	for (pos = neigh_dev_first_rcu_protected(head, c);		\
+	     pos && ({ n = neigh_dev_next_rcu_protected(pos, c); 1; });	\
+	     pos = n)
+
 #ifdef CONFIG_PROC_FS
 static const struct seq_operations neigh_stat_seq_ops;
 #endif
 
+static int family_to_neightbl_index(int family)
+{
+	switch (family) {
+	case AF_INET:
+		return NEIGH_ARP_TABLE;
+	case AF_INET6:
+		return NEIGH_ND_TABLE;
+	case AF_DECnet:
+		return NEIGH_DN_TABLE;
+	default:
+		return -1;
+	}
+}
+
 /*
    Neighbour hash table buckets are protected with rwlock tbl->lock.
 
@@ -233,6 +259,7 @@ static bool neigh_del(struct neighbour *n, struct neigh_table *tbl)
 	write_lock(&n->lock);
 	if (refcount_read(&n->refcnt) == 1) {
 		hlist_del_rcu(&n->list);
+		hlist_del_rcu(&n->dev_list);
 		neigh_mark_dead(n);
 		retval = true;
 	}
@@ -375,12 +402,63 @@ static void pneigh_queue_purge(struct sk_buff_head *list, struct net *net,
 	}
 }
 
+static void _neigh_flush_free_neigh(struct neighbour *n)
+{
+	hlist_del_rcu(&n->list);
+	hlist_del_rcu(&n->dev_list);
+	write_lock(&n->lock);
+	neigh_del_timer(n);
+	neigh_mark_dead(n);
+	if (refcount_read(&n->refcnt) != 1) {
+		/* The most unpleasant situation.
+		 * We must destroy neighbour entry,
+		 * but someone still uses it.
+		 *
+		 * The destroy will be delayed until
+		 * the last user releases us, but
+		 * we must kill timers etc. and move
+		 * it to safe state.
+		 */
+		__skb_queue_purge(&n->arp_queue);
+		n->arp_queue_len_bytes = 0;
+		WRITE_ONCE(n->output, neigh_blackhole);
+		if (n->nud_state & NUD_VALID)
+			n->nud_state = NUD_NOARP;
+		else
+			n->nud_state = NUD_NONE;
+		neigh_dbg(2, "neigh %p is stray\n", n);
+	}
+	write_unlock(&n->lock);
+	neigh_cleanup_and_release(n);
+}
+
+static void neigh_flush_dev_fast(struct neigh_table *tbl,
+				 struct hlist_head *head,
+				 bool skip_perm)
+{
+	struct neighbour *n, *next;
+
+	neigh_dev_for_each_safe_rcu_protected(n, next, head,
+					      lockdep_is_held(&tbl->lock)) {
+		if (skip_perm && n->nud_state & NUD_PERMANENT)
+			continue;
+
+		_neigh_flush_free_neigh(n);
+	}
+}
+
 static void neigh_flush_dev(struct neigh_table *tbl, struct net_device *dev,
 			    bool skip_perm)
 {
 	int i;
 	struct neigh_hash_table *nht;
 
+	i = family_to_neightbl_index(tbl->family);
+	if (i != -1) {
+		neigh_flush_dev_fast(tbl, &dev->neighbours[i], skip_perm);
+		return;
+	}
+
 	nht = rcu_dereference_protected(tbl->nht,
 					lockdep_is_held(&tbl->lock));
 
@@ -396,31 +474,8 @@ static void neigh_flush_dev(struct neigh_table *tbl, struct net_device *dev,
 			if (skip_perm && n->nud_state & NUD_PERMANENT) {
 				continue;
 			}
-			hlist_del_rcu(&n->list);
-			write_lock(&n->lock);
-			neigh_del_timer(n);
-			neigh_mark_dead(n);
-			if (refcount_read(&n->refcnt) != 1) {
-				/* The most unpleasant situation.
-				   We must destroy neighbour entry,
-				   but someone still uses it.
-
-				   The destroy will be delayed until
-				   the last user releases us, but
-				   we must kill timers etc. and move
-				   it to safe state.
-				 */
-				__skb_queue_purge(&n->arp_queue);
-				n->arp_queue_len_bytes = 0;
-				WRITE_ONCE(n->output, neigh_blackhole);
-				if (n->nud_state & NUD_VALID)
-					n->nud_state = NUD_NOARP;
-				else
-					n->nud_state = NUD_NONE;
-				neigh_dbg(2, "neigh %p is stray\n", n);
-			}
-			write_unlock(&n->lock);
-			neigh_cleanup_and_release(n);
+
+			_neigh_flush_free_neigh(n);
 		}
 	}
 }
@@ -701,6 +756,11 @@ ___neigh_create(struct neigh_table *tbl, const void *pkey,
 	if (want_ref)
 		neigh_hold(n);
 	hlist_add_head_rcu(&n->list, &nht->hash_buckets[hash_val]);
+
+	error = family_to_neightbl_index(tbl->family);
+	if (error != -1)
+		hlist_add_head_rcu(&n->dev_list, &dev->neighbours[error]);
+
 	write_unlock_bh(&tbl->lock);
 	neigh_dbg(2, "neigh %p is created\n", n);
 	rc = n;
@@ -982,6 +1042,7 @@ static void neigh_periodic_work(struct work_struct *work)
 			     !time_in_range_open(jiffies, n->used,
 						 n->used + NEIGH_VAR(n->parms, GC_STALETIME)))) {
 				hlist_del_rcu(&n->list);
+				hlist_del_rcu(&n->dev_list);
 				neigh_mark_dead(n);
 				write_unlock(&n->lock);
 				neigh_cleanup_and_release(n);
@@ -3102,6 +3163,7 @@ void __neigh_for_each_release(struct neigh_table *tbl,
 			release = cb(n);
 			if (release) {
 				hlist_del_rcu(&n->list);
+				hlist_del_rcu(&n->dev_list);
 				neigh_mark_dead(n);
 			}
 			write_unlock(&n->lock);
-- 
2.46.0

Re: [PATCH net-next v3 1/2] Convert neighbour-table to use hlist

[Kuniyuki Iwashima]

From: Gilad Naaman <gnaaman@drivenets.com>
Date: Thu, 10 Oct 2024 12:01:24 +0000
> @@ -304,9 +304,7 @@ static inline struct neighbour *___neigh_lookup_noref(
>  	u32 hash_val;
>  
>  	hash_val = hash(pkey, dev, nht->hash_rnd) >> (32 - nht->hash_shift);
> -	for (n = rcu_dereference(nht->hash_buckets[hash_val]);
> -	     n != NULL;
> -	     n = rcu_dereference(n->next)) {
> +	hlist_for_each_entry_rcu(n, &nht->hash_buckets[hash_val], list) {

Let's move macros in .h and use it here.


>  		if (n->dev == dev && key_eq(n, pkey))
>  			return n;
>  	}
> diff --git a/net/core/neighbour.c b/net/core/neighbour.c
> index 77b819cd995b..bf7f69b585d6 100644
> --- a/net/core/neighbour.c
> +++ b/net/core/neighbour.c
> @@ -37,6 +37,7 @@
>  #include <linux/string.h>
>  #include <linux/log2.h>
>  #include <linux/inetdevice.h>
> +#include <linux/rculist.h>
>  #include <net/addrconf.h>
>  
>  #include <trace/events/neigh.h>
> @@ -57,6 +58,26 @@ static void neigh_update_notify(struct neighbour *neigh, u32 nlmsg_pid);
>  static int pneigh_ifdown_and_unlock(struct neigh_table *tbl,
>  				    struct net_device *dev);
>  
> +#define neigh_hlist_entry(n) hlist_entry_safe(n, struct neighbour, list)
> +
> +#define neigh_for_each_rcu(pos, head, cond...) \

No cond here, and use this only under RCU.

For places under neigh table lock, let's define neigh_for_each()
with hlist_for_each_entry().

The current neigh_for_each() is only used in spectrum_router.c
and can be moved to mlxsw_sp_neigh_rif_made_sync_each() with
the new macro used.

Let's split this patch for ease of review.

  1. Add hlist_node and link/unlink by hlist_add() / hlist_del()
  2. Define neigh_for_each() macro and move the current
     neigh_for_each() to mlxsw_sp_neigh_rif_made_sync_each()
  3. Rewrite the seq_file part with macro
  4. Convert the rest of while()/for() with macro
  5. Remove ->next


> +	hlist_for_each_entry_rcu(pos, head, list, ##cond)
> +
> +#define neigh_for_each_safe_rcu_protected(pos, n, head, c)		\
> +	for (pos = neigh_first_rcu_protected(head, c);			\
> +	     pos && ({ n = neigh_next_rcu_protected(pos, c); 1; });	\
> +	     pos = n)

This should be hlist_for_each_entry_safe().

There is a reason why rculist.h does not have this version.
_safe means you are on the write side, which does not need RCU.


> +
> +#define neigh_first_rcu(bucket) \
> +	neigh_hlist_entry(rcu_dereference(hlist_first_rcu(bucket)))
> +#define neigh_next_rcu(n) \
> +	neigh_hlist_entry(rcu_dereference(hlist_next_rcu(&(n)->list)))
> +
> +#define neigh_first_rcu_protected(head, c) \
> +	neigh_hlist_entry(rcu_dereference_protected(hlist_first_rcu(head), c))
> +#define neigh_next_rcu_protected(n, c) \
> +	neigh_hlist_entry(rcu_dereference_protected(hlist_next_rcu(&(n)->list), c))
> +
>  #ifdef CONFIG_PROC_FS
>  static const struct seq_operations neigh_stat_seq_ops;
>  #endif
> @@ -205,18 +226,13 @@ static void neigh_update_flags(struct neighbour *neigh, u32 flags, int *notify,
>  	}
>  }
>  
> -static bool neigh_del(struct neighbour *n, struct neighbour __rcu **np,
> -		      struct neigh_table *tbl)
> +static bool neigh_del(struct neighbour *n, struct neigh_table *tbl)

Now this can be renamed to neigh_remove_one() without static.


>  {
>  	bool retval = false;
>  
>  	write_lock(&n->lock);
>  	if (refcount_read(&n->refcnt) == 1) {
> -		struct neighbour *neigh;
> -
> -		neigh = rcu_dereference_protected(n->next,
> -						  lockdep_is_held(&tbl->lock));
> -		rcu_assign_pointer(*np, neigh);
> +		hlist_del_rcu(&n->list);
>  		neigh_mark_dead(n);
>  		retval = true;
>  	}
> @@ -228,25 +244,7 @@ static bool neigh_del(struct neighbour *n, struct neighbour __rcu **np,
>  
>  bool neigh_remove_one(struct neighbour *ndel, struct neigh_table *tbl)
>  {
> -	struct neigh_hash_table *nht;
> -	void *pkey = ndel->primary_key;
> -	u32 hash_val;
> -	struct neighbour *n;
> -	struct neighbour __rcu **np;
> -
> -	nht = rcu_dereference_protected(tbl->nht,
> -					lockdep_is_held(&tbl->lock));
> -	hash_val = tbl->hash(pkey, ndel->dev, nht->hash_rnd);
> -	hash_val = hash_val >> (32 - nht->hash_shift);
> -
> -	np = &nht->hash_buckets[hash_val];
> -	while ((n = rcu_dereference_protected(*np,
> -					      lockdep_is_held(&tbl->lock)))) {
> -		if (n == ndel)
> -			return neigh_del(n, np, tbl);
> -		np = &n->next;
> -	}
> -	return false;
> +	return neigh_del(ndel, tbl);
>  }
>  
>  static int neigh_forced_gc(struct neigh_table *tbl)
> @@ -387,22 +385,18 @@ static void neigh_flush_dev(struct neigh_table *tbl, struct net_device *dev,
>  					lockdep_is_held(&tbl->lock));
>  
>  	for (i = 0; i < (1 << nht->hash_shift); i++) {
> -		struct neighbour *n;
> -		struct neighbour __rcu **np = &nht->hash_buckets[i];
> +		struct neighbour *n, *next;
>  
> -		while ((n = rcu_dereference_protected(*np,
> -					lockdep_is_held(&tbl->lock))) != NULL) {
> +		neigh_for_each_safe_rcu_protected(n, next,
> +						  &nht->hash_buckets[i],
> +						  lockdep_is_held(&tbl->lock)) {

tbl->nht is already fetched with lockdep_is_held(),
soneigh_for_each_safe() is enough.


>  			if (dev && n->dev != dev) {
> -				np = &n->next;
>  				continue;
>  			}

{} is no longer needed.


>  			if (skip_perm && n->nud_state & NUD_PERMANENT) {
> -				np = &n->next;
>  				continue;
>  			}

Same here.


[...]
> @@ -591,7 +585,7 @@ static struct neigh_hash_table *neigh_hash_grow(struct neigh_table *tbl,
>  	for (i = 0; i < (1 << old_nht->hash_shift); i++) {
>  		struct neighbour *n, *next;
>  
> -		for (n = rcu_dereference_protected(old_nht->hash_buckets[i],
> +		for (n = neigh_first_rcu_protected(&old_nht->hash_buckets[i],
>  						   lockdep_is_held(&tbl->lock));

_safe version can be used,


>  		     n != NULL;
>  		     n = next) {
> @@ -599,14 +593,9 @@ static struct neigh_hash_table *neigh_hash_grow(struct neigh_table *tbl,
>  					 new_nht->hash_rnd);
>  
>  			hash >>= (32 - new_nht->hash_shift);
> -			next = rcu_dereference_protected(n->next,
> -						lockdep_is_held(&tbl->lock));
> -
> -			rcu_assign_pointer(n->next,
> -					   rcu_dereference_protected(
> -						new_nht->hash_buckets[hash],
> -						lockdep_is_held(&tbl->lock)));
> -			rcu_assign_pointer(new_nht->hash_buckets[hash], n);
> +			next = neigh_next_rcu_protected(n, lockdep_is_held(&tbl->lock));

then, this will be unnecessary.


> +			hlist_del_rcu(&n->list);
> +			hlist_add_head_rcu(&n->list, &new_nht->hash_buckets[hash]);
>  		}
>  	}
>  
> @@ -693,11 +682,9 @@ ___neigh_create(struct neigh_table *tbl, const void *pkey,
>  		goto out_tbl_unlock;
>  	}
>  
> -	for (n1 = rcu_dereference_protected(nht->hash_buckets[hash_val],
> -					    lockdep_is_held(&tbl->lock));
> -	     n1 != NULL;
> -	     n1 = rcu_dereference_protected(n1->next,
> -			lockdep_is_held(&tbl->lock))) {
> +	neigh_for_each_rcu(n1,
> +			   &nht->hash_buckets[hash_val],
> +			   lockdep_is_held(&tbl->lock)) {

lockdep_is_held() is used above.

Let's use neigh_for_each().


[...]
> @@ -3242,7 +3208,8 @@ static struct neighbour *neigh_get_next(struct seq_file *seq,
>  		if (v)
>  			return n;
>  	}
> -	n = rcu_dereference(n->next);
> +
> +	n = neigh_next_rcu(n);

I guess neigh_get_next() can be simplified with
hlist_for_each_entry_continue_rcu() ?

Then, neigh_first_rcu() and neigh_next_rcu() would be unnecessary ?

>  
>  	while (1) {
>  		while (n) {
> @@ -3260,7 +3227,8 @@ static struct neighbour *neigh_get_next(struct seq_file *seq,
>  			if (READ_ONCE(n->nud_state) & ~NUD_NOARP)
>  				break;
>  next:
> -			n = rcu_dereference(n->next);
> +
> +			n = neigh_next_rcu(n);
>  		}
>  
>  		if (n)
> @@ -3269,7 +3237,7 @@ static struct neighbour *neigh_get_next(struct seq_file *seq,
>  		if (++state->bucket >= (1 << nht->hash_shift))
>  			break;
>  
> -		n = rcu_dereference(nht->hash_buckets[state->bucket]);
> +		n = neigh_first_rcu(&nht->hash_buckets[state->bucket]);
>  	}
>  
>  	if (n && pos)
> -- 
> 2.46.0
> 

Re: [PATCH net-next v3 1/2] Convert neighbour-table to use hlist

[Gilad Naaman]

> The current neigh_for_each() is only used in spectrum_router.c
> and can be moved to mlxsw_sp_neigh_rif_made_sync_each() with
> the new macro used.

Oh, I completely missed that it exists, sorry.

> Let's split this patch for ease of review.
> 
>   1. Add hlist_node and link/unlink by hlist_add() / hlist_del()
>   2. Define neigh_for_each() macro and move the current
>      neigh_for_each() to mlxsw_sp_neigh_rif_made_sync_each()
>   3. Rewrite the seq_file part with macro
>   4. Convert the rest of while()/for() with macro
>   5. Remove ->next

Just making sure, you mean that in (1.) I should add hlist_node *alongside*
the current `struct neighbour __rcu *next`, and only remove this duplication in
(5.)?

Re: [PATCH net-next v3 1/2] Convert neighbour-table to use hlist

[Kuniyuki Iwashima]

From: Gilad Naaman <gnaaman@drivenets.com>
Date: Sun, 13 Oct 2024 10:45:21 +0000
> > The current neigh_for_each() is only used in spectrum_router.c
> > and can be moved to mlxsw_sp_neigh_rif_made_sync_each() with
> > the new macro used.
> 
> Oh, I completely missed that it exists, sorry.
> 
> > Let's split this patch for ease of review.
> > 
> >   1. Add hlist_node and link/unlink by hlist_add() / hlist_del()
> >   2. Define neigh_for_each() macro and move the current
> >      neigh_for_each() to mlxsw_sp_neigh_rif_made_sync_each()
> >   3. Rewrite the seq_file part with macro
> >   4. Convert the rest of while()/for() with macro
> >   5. Remove ->next
> 
> Just making sure, you mean that in (1.) I should add hlist_node *alongside*
> the current `struct neighbour __rcu *next`, and only remove this duplication in
> (5.)?

Right, it will allow part-by-part changes that are easier to review.

Re: [PATCH net-next v3 2/2] Create netdev->neighbour association

[Kuniyuki Iwashima]

From: Gilad Naaman <gnaaman@drivenets.com>
Date: Thu, 10 Oct 2024 12:01:25 +0000
> diff --git a/Documentation/networking/net_cachelines/net_device.rst b/Documentation/networking/net_cachelines/net_device.rst
> index 1b018ac35e9a..889501a16da2 100644
> --- a/Documentation/networking/net_cachelines/net_device.rst
> +++ b/Documentation/networking/net_cachelines/net_device.rst
> @@ -186,4 +186,5 @@ struct dpll_pin*                    dpll_pin
>  struct hlist_head                   page_pools
>  struct dim_irq_moder*               irq_moder
>  u64                                 max_pacing_offload_horizon
> +struct hlist_head                   neighbours[3]

I think 2 should be enough as DECnet was removed two years ago.
https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=1202cdd66531

MPLS also does not support DECnet via RTA_VIA, see nla_get_via().


[...]
> +static int family_to_neightbl_index(int family)
> +{
> +	switch (family) {
> +	case AF_INET:
> +		return NEIGH_ARP_TABLE;
> +	case AF_INET6:
> +		return NEIGH_ND_TABLE;
> +	case AF_DECnet:
> +		return NEIGH_DN_TABLE;
> +	default:
> +		return -1;

AF_DECnet should be unnecessary here and let default warn about it.

	case default:
		DEBUG_NET_WARN_ON_ONCE(1);
		return 0; /* to avoid panic by null-ptr-deref */


[...]
> +static void neigh_flush_dev_fast(struct neigh_table *tbl,
> +				 struct hlist_head *head,
> +				 bool skip_perm)
> +{
> +	struct neighbour *n, *next;
> +
> +	neigh_dev_for_each_safe_rcu_protected(n, next, head,
> +					      lockdep_is_held(&tbl->lock)) {
> +		if (skip_perm && n->nud_state & NUD_PERMANENT)
> +			continue;
> +
> +		_neigh_flush_free_neigh(n);
> +	}
> +}
> +
>  static void neigh_flush_dev(struct neigh_table *tbl, struct net_device *dev,
>  			    bool skip_perm)
>  {
>  	int i;
>  	struct neigh_hash_table *nht;
>  
> +	i = family_to_neightbl_index(tbl->family);
> +	if (i != -1) {

No need to handle error, and replace the following for-loop with
the dev-base iteration.


> +		neigh_flush_dev_fast(tbl, &dev->neighbours[i], skip_perm);
> +		return;
> +	}
> +
>  	nht = rcu_dereference_protected(tbl->nht,
>  					lockdep_is_held(&tbl->lock));
>  
[...]
> @@ -701,6 +756,11 @@ ___neigh_create(struct neigh_table *tbl, const void *pkey,
>  	if (want_ref)
>  		neigh_hold(n);
>  	hlist_add_head_rcu(&n->list, &nht->hash_buckets[hash_val]);
> +
> +	error = family_to_neightbl_index(tbl->family);
> +	if (error != -1)

Same here.

Re: [PATCH net-next v3 2/2] Create netdev->neighbour association

[Kuniyuki Iwashima]

From: Kuniyuki Iwashima <kuniyu@amazon.com>
Date: Mon, 14 Oct 2024 16:19:17 -0700
> From: Gilad Naaman <gnaaman@drivenets.com>
> Date: Thu, 10 Oct 2024 12:01:25 +0000
> > diff --git a/Documentation/networking/net_cachelines/net_device.rst b/Documentation/networking/net_cachelines/net_device.rst
> > index 1b018ac35e9a..889501a16da2 100644
> > --- a/Documentation/networking/net_cachelines/net_device.rst
> > +++ b/Documentation/networking/net_cachelines/net_device.rst
> > @@ -186,4 +186,5 @@ struct dpll_pin*                    dpll_pin
> >  struct hlist_head                   page_pools
> >  struct dim_irq_moder*               irq_moder
> >  u64                                 max_pacing_offload_horizon
> > +struct hlist_head                   neighbours[3]
> 
> I think 2 should be enough as DECnet was removed two years ago.
> https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=1202cdd66531
> 
> MPLS also does not support DECnet via RTA_VIA, see nla_get_via().

FYI, I posted a patch to remove NEIGH_DN_TABLE.
https://lore.kernel.org/netdev/20241014235216.10785-1-kuniyu@amazon.com/T/#u