Skip to contentSkip to conversation

net: store netdevs in an xarray

PATCH Applied Jakub Kicinski 4 participants 11 messages Jul 26, 2023 – Jul 29, 2023

Subsystems (3)
lore
Share & tools
lore

Jakub Kicinski

author maintainer
#0 lore raw

v2 cover net: store netdevs in an xarray

One of more annoying developer experience gaps we have in netlink is iterating over netdevs. It's painful. Add an xarray to make it trivial.

v2:
- fix the potential mishandling of wrapping (Leon)
v1: https://lore.kernel.org/all/[email protected]/

Jakub Kicinski (2):
net: store netdevs in an xarray
net: convert some netlink netdev iterators to depend on the xarray

 include/linux/netdevice.h   |  3 ++
 include/net/net_namespace.h |  4 +-
 net/core/dev.c              | 82 ++++++++++++++++++++++++-------------
 net/core/netdev-genl.c      | 37 ++++-------------
 net/ethtool/netlink.c       | 59 +++++++-------------------
 net/ethtool/tunnels.c       | 73 ++++++++++++---------------------
 6 files changed, 109 insertions(+), 149 deletions(-)
Signature · 1 line
2.41.0
author maintainer
#1 lore raw

PATCH v2 1/2 net: store netdevs in an xarray

Iterating over the netdev hash table for netlink dumps is hard. Dumps are done in "chunks" so we need to save the position after each chunk, so we know where to restart from. Because netdevs are stored in a hash table we remember which bucket we were in and how many devices we dumped.

Since we don't hold any locks across the "chunks" - devices may come and go while we're dumping. If that happens we may miss a device (if device is deleted from the bucket we were in). We indicate to user space that this may have happened by setting NLM_F_DUMP_INTR. User space is supposed to dump again (I think) if it sees that. Somehow I doubt most user space gets this right..

To illustrate let's look at an example:

System state:
start: # [A, B, C]
del: B # [A, C]

with the hash table we may dump [A, B], missing C completely even tho it existed both before and after the "del B".

Add an xarray and use it to allocate ifindexes. This way we can iterate ifindexes in order, without the worry that we'll skip one. We may still generate a dump of a state which "never existed", for example for a set of values and sequence of ops:

System state:

  start:       # [A, B]
  add:  C      # [A, C, B]
  del:  B      # [A, C]

we may generate a dump of [A], if C got an index between A and B. System has never been in such state. But I'm 90% sure that's perfectly fine, important part is that we can't _miss_ devices which exist before and after. User space which wants to mirror kernel's state subscribes to notifications and does periodic dumps so it will know that C exists from the notification about its creation or from the next dump (next dump is _guaranteed_ to include C, if it doesn't get removed).

To avoid any perf regressions keep the hash table for now. Most net namespaces have very few devices and microbenchmarking 1M lookups on Skylake I get the following results (not counting loopback to number of devs):

 #devs | hash |  xa  | delta
    2  | 18.3 | 20.1 | + 9.8%
   16  | 18.3 | 20.1 | + 9.5%
   64  | 18.3 | 26.3 | +43.8%
  128  | 20.4 | 26.3 | +28.6%
  256  | 20.0 | 26.4 | +32.1%
 1024  | 26.6 | 26.7 | + 0.2%
 8192  |541.3 | 33.5 | -93.8%

No surprises since the hash table has 256 entries.
The microbenchmark scans indexes in order, if the pattern is more random xa starts to win at 512 devices already. But that's a lot of devices, in practice.

---
v2:
- fix error checking on xa_alloc_cyclic() (Leon)

---
 include/net/net_namespace.h |  4 +-
 net/core/dev.c              | 82 ++++++++++++++++++++++++-------------
 2 files changed, 57 insertions(+), 29 deletions(-)
include/net/net_namespace.h +3 -1
index 78beaa765c73..9f6add96de2d 100644
@@ -42,6 +42,7 @@
 #include <linux/idr.h>
 #include <linux/skbuff.h>
 #include <linux/notifier.h>
+#include <linux/xarray.h>
 
 struct user_namespace;
 struct proc_dir_entry;
@@ -69,7 +70,7 @@ struct net {
 	atomic_t		dev_unreg_count;
 
 	unsigned int		dev_base_seq;	/* protected by rtnl_mutex */
-	int			ifindex;
+	u32			ifindex;
 
 	spinlock_t		nsid_lock;
 	atomic_t		fnhe_genid;
@@ -110,6 +111,7 @@ struct net {
 
 	struct hlist_head 	*dev_name_head;
 	struct hlist_head	*dev_index_head;
+	struct xarray		dev_by_index;
 	struct raw_notifier_head	netdev_chain;
 
 	/* Note that @hash_mix can be read millions times per second,
net/core/dev.c +54 -28

149 lines not on this page · raw message

Signature · 1 line
2.41.0
Reviewed-by on v2 1/2
#2 lore raw
Quoted 67 lines · Jakub Kicinski

Iterating over the netdev hash table for netlink dumps is hard. Dumps are done in "chunks" so we need to save the position after each chunk, so we know where to restart from. Because netdevs are stored in a hash table we remember which bucket we were in and how many devices we dumped.

Since we don't hold any locks across the "chunks" - devices may come and go while we're dumping. If that happens we may miss a device (if device is deleted from the bucket we were in). We indicate to user space that this may have happened by setting NLM_F_DUMP_INTR. User space is supposed to dump again (I think) if it sees that. Somehow I doubt most user space gets this right..

To illustrate let's look at an example:

System state:
start: # [A, B, C]
del: B # [A, C]

with the hash table we may dump [A, B], missing C completely even tho it existed both before and after the "del B".

Add an xarray and use it to allocate ifindexes. This way we can iterate ifindexes in order, without the worry that we'll skip one. We may still generate a dump of a state which "never existed", for example for a set of values and sequence of ops:

System state:

  start:       # [A, B]
  add:  C      # [A, C, B]
  del:  B      # [A, C]

we may generate a dump of [A], if C got an index between A and B. System has never been in such state. But I'm 90% sure that's perfectly fine, important part is that we can't _miss_ devices which exist before and after. User space which wants to mirror kernel's state subscribes to notifications and does periodic dumps so it will know that C exists from the notification about its creation or from the next dump (next dump is _guaranteed_ to include C, if it doesn't get removed).

To avoid any perf regressions keep the hash table for now. Most net namespaces have very few devices and microbenchmarking 1M lookups on Skylake I get the following results (not counting loopback to number of devs):

 #devs | hash |  xa  | delta
    2  | 18.3 | 20.1 | + 9.8%
   16  | 18.3 | 20.1 | + 9.5%
   64  | 18.3 | 26.3 | +43.8%
  128  | 20.4 | 26.3 | +28.6%
  256  | 20.0 | 26.4 | +32.1%
 1024  | 26.6 | 26.7 | + 0.2%
 8192  |541.3 | 33.5 | -93.8%

No surprises since the hash table has 256 entries.
The microbenchmark scans indexes in order, if the pattern is more random xa starts to win at 512 devices already. But that's a lot of devices, in practice.

---
v2:
- fix error checking on xa_alloc_cyclic() (Leon)

---
 include/net/net_namespace.h |  4 +-
 net/core/dev.c              | 82 ++++++++++++++++++++++++-------------
 2 files changed, 57 insertions(+), 29 deletions(-)

<...>

Quoted 3 lines
include/net/net_namespace.h +1 -1
 	unsigned int		dev_base_seq;	/* protected by rtnl_mutex */
-	int			ifindex;
+	u32			ifindex;

<...>

Quoted 4 lines
net/core/dev.c +2 -1
+static int dev_index_reserve(struct net *net, u32 ifindex)
 {
-	int ifindex = net->ifindex;
+	int err;

<...>

net/core/dev.c int dev_change_xdp_fd(struct net_device *dev, struct netlink_ext_ack *extack, · line 9596

Quoted 9 lines
net/core/dev.c +9 -0
+	if (!ifindex)
+		err = xa_alloc_cyclic(&net->dev_by_index, &ifindex, NULL,
+				      xa_limit_31b, &net->ifindex, GFP_KERNEL);
+	else
+		err = xa_insert(&net->dev_by_index, ifindex, NULL, GFP_KERNEL);
+	if (err < 0)
+		return err;
+
+	return ifindex;

ifindex is now u32, but you return it as int. In potential, you can return valid ifindex which will be treated as error.

You should ensure that ifindex doesn't have signed bit on.

Everything else, LGTM

author maintainer
#3 lore raw
Quoted 13 lines · On Thu, 27 Jul 2023 16:08:24 +0300 Leon Romanovsky wrote:

net/core/dev.c int dev_change_xdp_fd(struct net_device *dev, struct netlink_ext_ack *extack, · line 9596

Quoted 9 lines
net/core/dev.c +9 -0
+	if (!ifindex)
+		err = xa_alloc_cyclic(&net->dev_by_index, &ifindex, NULL,
+				      xa_limit_31b, &net->ifindex, GFP_KERNEL);
+	else
+		err = xa_insert(&net->dev_by_index, ifindex, NULL, GFP_KERNEL);
+	if (err < 0)
+		return err;
+
+	return ifindex;  

ifindex is now u32, but you return it as int. In potential, you can return valid ifindex which will be treated as error.

Quoted 1 line

You should ensure that ifindex doesn't have signed bit on.

I'm feeding xa_alloc_cyclic() xa_limit_31b, which should take care of that, no?

#4 lore raw
Quoted 14 lines · Jakub Kicinski
Quoted 13 lines · On Thu, 27 Jul 2023 16:08:24 +0300 Leon Romanovsky wrote:

net/core/dev.c int dev_change_xdp_fd(struct net_device *dev, struct netlink_ext_ack *extack, · line 9596

Quoted 9 lines
net/core/dev.c +9 -0
+	if (!ifindex)
+		err = xa_alloc_cyclic(&net->dev_by_index, &ifindex, NULL,
+				      xa_limit_31b, &net->ifindex, GFP_KERNEL);
+	else
+		err = xa_insert(&net->dev_by_index, ifindex, NULL, GFP_KERNEL);
+	if (err < 0)
+		return err;
+
+	return ifindex;  

ifindex is now u32, but you return it as int. In potential, you can return valid ifindex which will be treated as error.

Quoted 4 lines
Quoted 1 line

You should ensure that ifindex doesn't have signed bit on.

I'm feeding xa_alloc_cyclic() xa_limit_31b, which should take care of that, no?

And what about xa_insert() call? Is it safe?

author maintainer
#5 lore raw
Quoted 4 lines · On Fri, 28 Jul 2023 07:53:04 +0300 Leon Romanovsky wrote:
Quoted 2 lines

I'm feeding xa_alloc_cyclic() xa_limit_31b, which should take care of that, no?

And what about xa_insert() call? Is it safe?

I think so, as in - the previous code doesn't have any checks either, so it'd insert the negative ifindex into the hash table. Hopefully nobody assigns negative values to dev->ifindex, that'd be a bug in itself, I reckon.

#6 lore raw
Quoted 11 lines · On Fri, 28 Jul 2023 08:27:45 -0700 Jakub Kicinski <[email protected]> wrote:
Quoted 4 lines · On Fri, 28 Jul 2023 07:53:04 +0300 Leon Romanovsky wrote:
Quoted 2 lines

I'm feeding xa_alloc_cyclic() xa_limit_31b, which should take care of that, no?

And what about xa_insert() call? Is it safe?

I think so, as in - the previous code doesn't have any checks either, so it'd insert the negative ifindex into the hash table. Hopefully nobody assigns negative values to dev->ifindex, that'd be a bug in itself, I reckon.

Even inserting with ifindex = 0 would be a bug

author maintainer
#7 lore raw
Quoted 6 lines · On Fri, 28 Jul 2023 16:23:50 -0700 Stephen Hemminger wrote:
Quoted 4 lines

I think so, as in - the previous code doesn't have any checks either, so it'd insert the negative ifindex into the hash table. Hopefully nobody assigns negative values to dev->ifindex, that'd be a bug in itself, I reckon.

Even inserting with ifindex = 0 would be a bug

... and that could actually happen if we allocate and the indexes have wrapped :S We need better limit. I'll send a fix.

author maintainer
#8 lore raw

PATCH v2 2/2 net: convert some netlink netdev iterators to depend on the xarray

In reply to Jakub Kicinski

Reap the benefits of easier iteration thanks to the xarray. Convert just the genetlink ones, those are easier to test.

---
 include/linux/netdevice.h |  3 ++
 net/core/netdev-genl.c    | 37 +++++---------------
 net/ethtool/netlink.c     | 59 ++++++++-----------------------
 net/ethtool/tunnels.c     | 73 +++++++++++++++------------------------
 4 files changed, 52 insertions(+), 120 deletions(-)
include/linux/netdevice.h +3 -0
index 11652e464f5d..c35126180541 100644
@@ -3016,6 +3016,9 @@ extern rwlock_t				dev_base_lock;		/* Device list lock */
 			if (netdev_master_upper_dev_get_rcu(slave) == (bond))
 #define net_device_entry(lh)	list_entry(lh, struct net_device, dev_list)
 
+#define for_each_netdev_dump(net, d, ifindex)				\
+	xa_for_each_start(&(net)->dev_by_index, (ifindex), (d), (ifindex))
+
 static inline struct net_device *next_net_device(struct net_device *dev)
 {
 	struct list_head *lh;
net/core/netdev-genl.c +8 -29
index 65ef4867fc49..797c813c7c77 100644
@@ -101,43 +101,22 @@ int netdev_nl_dev_get_dumpit(struct sk_buff *skb, struct netlink_callback *cb)
 {
 	struct net *net = sock_net(skb->sk);
 	struct net_device *netdev;
-	int idx = 0, s_idx;
-	int h, s_h;
-	int err;
-
-	s_h = cb->args[0];
-	s_idx = cb->args[1];
+	int err = 0;
 
 	rtnl_lock();
-
-	for (h = s_h; h < NETDEV_HASHENTRIES; h++, s_idx = 0) {
-		struct hlist_head *head;
-
-		idx = 0;
-		head = &net->dev_index_head[h];
-		hlist_for_each_entry(netdev, head, index_hlist) {
-			if (idx < s_idx)
-				goto cont;
-			err = netdev_nl_dev_fill(netdev, skb,
-						 NETLINK_CB(cb->skb).portid,
-						 cb->nlh->nlmsg_seq, 0,
-						 NETDEV_CMD_DEV_GET);
-			if (err < 0)
-				break;
-cont:
-			idx++;
-		}
+	for_each_netdev_dump(net, netdev, cb->args[0]) {
+		err = netdev_nl_dev_fill(netdev, skb,
+					 NETLINK_CB(cb->skb).portid,
+					 cb->nlh->nlmsg_seq, 0,
+					 NETDEV_CMD_DEV_GET);
+		if (err < 0)
+			break;
 	}
-
 	rtnl_unlock();
 
 	if (err != -EMSGSIZE)
 		return err;
 
-	cb->args[1] = idx;
-	cb->args[0] = h;
-	cb->seq = net->dev_base_seq;
-
 	return skb->len;
 }
 
net/ethtool/netlink.c +14 -45

93 lines not on this page · raw message

net/ethtool/tunnels.c +27 -46

91 lines not on this page · raw message

Signature · 1 line
2.41.0
Reviewed-by on v2 2/2
#9 lore raw

Re: [PATCH net-next v2 2/2] net: convert some netlink netdev iterators to depend on the xarray

Quoted 11 lines · Jakub Kicinski

Reap the benefits of easier iteration thanks to the xarray. Convert just the genetlink ones, those are easier to test.

---
 include/linux/netdevice.h |  3 ++
 net/core/netdev-genl.c    | 37 +++++---------------
 net/ethtool/netlink.c     | 59 ++++++++-----------------------
 net/ethtool/tunnels.c     | 73 +++++++++++++++------------------------
 4 files changed, 52 insertions(+), 120 deletions(-)

Thanks,

#10 lore raw
In reply to Jakub Kicinski
This series was applied to netdev/net-next.git (main) by Jakub Kicinski <[email protected]>:

Hello:

This series was applied to netdev/net-next.git (main) by Jakub Kicinski <[email protected]>:

Quoted 9 lines · On Wed, 26 Jul 2023 11:55:28 -0700 you wrote:

One of more annoying developer experience gaps we have in netlink is iterating over netdevs. It's painful. Add an xarray to make it trivial.

v2:
- fix the potential mishandling of wrapping (Leon)
v1: https://lore.kernel.org/all/[email protected]/

[...]

Here is the summary with links:
- [net-next,v2,1/2] net: store netdevs in an xarray

    https://git.kernel.org/netdev/net-next/c/759ab1edb56c
  - [net-next,v2,2/2] net: convert some netlink netdev iterators to depend on the xarray
    https://git.kernel.org/netdev/net-next/c/84e00d9bd4e4

You are awesome, thank you!

Signature · 2 lines
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html