Under large scale, some routers are required to support tens of thousands
of devices at once, both physical and virtual (e.g. loopbacks, tunnels,
vrfs, etc).
At times such routers are required to delete massive amounts of devices
at once, such as when a factory reset is performed on the router (causing
a deletion of all devices), or when a configuration is restored after an
upgrade, or as a request from an operator.
Currently there are 2 means of deleting devices using Netlink:
1. Deleting a single device (either by ifindex using ifinfomsg::ifi_index,
or by name using IFLA_IFNAME)
2. Delete all device that belong to a group (using IFLA_GROUP)
Deletion of devices one-by-one has poor performance on large scale of
devices compared to "group deletion":
After all device are handled, netdev_run_todo() is called which
calls rcu_barrier() to finish any outstanding RCU callbacks that were
registered during the deletion of the device, then wait until the
refcount of all the devices is 0, then perform final cleanups.
However, calling rcu_barrier() is a very costly operation, each call
taking in the order of 10s of milliseconds.
When deleting a large number of device one-by-one, rcu_barrier()
will be called for each device being deleted.
As an example, following benchmark deletes 10K loopback devices,
all of which are UP and with only IPv6 LLA being configured:
1. Deleting one-by-one using 1 thread : 243 seconds
2. Deleting one-by-one using 10 thread: 70 seconds
3. Deleting one-by-one using 50 thread: 54 seconds
4. Deleting all using "group deletion": 30 seconds
Note that even though the deletion logic takes place under the rtnl
lock, since the call to rcu_barrier() is outside the lock we gain
some improvements.
But, while "group deletion" is the fastest, it is not suited for
deleting large number of arbitrary devices which are unknown a head of
time. Furthermore, moving large number of devices to a group is also a
costly operation.
This patch adds support for passing an arbitrary list of ifindex of
devices to delete with a new IFLA_IFINDEX attribute. A single message
may contain multiple instances of this attribute).
This gives a more fine-grained control over which devices to delete,
while still resulting in rcu_barrier() being called only once.
Indeed, the timings of using this new API to delete 10K devices is
the same as using the existing "group" deletion.
Signed-off-by: Lahav Schlesinger <redacted>
---
v4 -> v5
- Call ->dellink() only once for duplicated devices.
v3 -> v4
- Change single IFLA_INDEX_LIST into multiple IFLA_IFINDEX
- Fail if passing both IFLA_GROUP and at least one IFLA_IFNEX
v2 -> v3
- Rename 'ifindex_list' to 'ifindices', and pass it as int*
- Clamp 'ops' variable in second loop.
v1 -> v2
- Unset 'len' of IFLA_IFINDEX_LIST in policy.
- Use __dev_get_by_index() instead of n^2 loop.
- Return -ENODEV if any ifindex is not present.
- Saved devices in an array.
- Fix formatting.
include/uapi/linux/if_link.h | 1 +
net/core/rtnetlink.c | 82 ++++++++++++++++++++++++++++++++++++
2 files changed, 83 insertions(+)
@@ -3050,6 +3052,78 @@ static int rtnl_group_dellink(const struct net *net, int group)return0;}+staticintdev_ifindex_cmp(constvoid*a,constvoid*b)+{+structnet_device*const*dev1=a,*const*dev2=b;++return(*dev1)->ifindex-(*dev2)->ifindex;+}++staticintrtnl_ifindex_dellink(structnet*net,structnlattr*head,intlen,+structnetlink_ext_ack*extack)+{+inti=0,num_devices=0,rem;+structnet_device**dev_list;+conststructnlattr*nla;+LIST_HEAD(list_kill);+intret;++nla_for_each_attr(nla,head,len,rem){+if(nla_type(nla)==IFLA_IFINDEX)+num_devices++;+}++dev_list=kmalloc_array(num_devices,sizeof(*dev_list),GFP_KERNEL);+if(!dev_list)+return-ENOMEM;++nla_for_each_attr(nla,head,len,rem){+conststructrtnl_link_ops*ops;+structnet_device*dev;+intifindex;++if(nla_type(nla)!=IFLA_IFINDEX)+continue;++ifindex=nla_get_s32(nla);+ret=-ENODEV;+dev=__dev_get_by_index(net,ifindex);+if(!dev){+NL_SET_ERR_MSG_ATTR(extack,nla,"Unknown ifindex");+gotoout_free;+}++ret=-EOPNOTSUPP;+ops=dev->rtnl_link_ops;+if(!ops||!ops->dellink){+NL_SET_ERR_MSG_ATTR(extack,nla,"Device cannot be deleted");+gotoout_free;+}++dev_list[i++]=dev;+}++/* Sort devices, so we could skip duplicates */+sort(dev_list,num_devices,sizeof(*dev_list),dev_ifindex_cmp,NULL);++for(i=0;i<num_devices;i++){+structnet_device*dev=dev_list[i];++if(i!=0&&dev_list[i-1]->ifindex==dev->ifindex)+continue;++dev->rtnl_link_ops->dellink(dev,&list_kill);+}++unregister_netdevice_many(&list_kill);++ret=0;++out_free:+kfree(dev_list);+returnret;+}+intrtnl_delete_link(structnet_device*dev){conststructrtnl_link_ops*ops;
@@ -3093,6 +3167,11 @@ static int rtnl_dellink(struct sk_buff *skb, struct nlmsghdr *nlh,returnPTR_ERR(tgt_net);}+if(tb[IFLA_GROUP]&&tb[IFLA_IFINDEX]){+NL_SET_ERR_MSG(extack,"Can't pass both IFLA_GROUP and IFLA_IFINDEX");+return-EOPNOTSUPP;+}+err=-EINVAL;ifm=nlmsg_data(nlh);if(ifm->ifi_index>0)
From: Nikolay Aleksandrov <hidden> Date: 2021-12-05 10:31:54
On 05/12/2021 11:36, Lahav Schlesinger wrote:
[snip]
But, while "group deletion" is the fastest, it is not suited for
deleting large number of arbitrary devices which are unknown a head of
time. Furthermore, moving large number of devices to a group is also a
costly operation.
This patch adds support for passing an arbitrary list of ifindex of
devices to delete with a new IFLA_IFINDEX attribute. A single message
may contain multiple instances of this attribute).
This gives a more fine-grained control over which devices to delete,
while still resulting in rcu_barrier() being called only once.
Indeed, the timings of using this new API to delete 10K devices is
the same as using the existing "group" deletion.
Signed-off-by: Lahav Schlesinger <redacted>
---
From: Nicolas Dichtel <hidden> Date: 2021-12-06 08:25:20
Le 05/12/2021 à 10:36, Lahav Schlesinger a écrit :
Some comments below, but please, keep the people who replied to previous
versions of this patch in cc.
[snip]
On Mon, Dec 06, 2021 at 09:25:17AM +0100, Nicolas Dichtel wrote:
CAUTION: External E-Mail - Use caution with links and attachments
Le 05/12/2021 à 10:36, Lahav Schlesinger a écrit :
Some comments below, but please, keep the people who replied to previous
versions of this patch in cc.
[snip]
nit: maybe the previous blank line sit better after this new attribute (and
before __IFLA_MAX)?
Due to the comment above the previous 2 attributes, I think that by
removing this empty line it can be accidentally thought as if the new
attribute is part of this "block".
As for adding a new line before __IFLA_MAX, I wanted to preserve the
appearance we had before the IFLA_PARENT_DEV_xxx attributes where added,
where there was no empty line before __IFLA_MAX.
I don't mind either way though, whatever looks better to you.
From: Jakub Kicinski <kuba@kernel.org> Date: 2021-12-07 15:37:42
On Mon, 6 Dec 2021 21:12:33 -0700 David Ahern wrote:
The need to walk the list twice (3 really with the sort) to means the
array solution is better.
Technically the linear walk will be dwarfed by the sort for non-trivial
inputs (have I been conducting too many coding interviews?)
Especially with retpolines :(
I liked the array variant better. Jakub?
I always default to attr-per-member unless there is a strong constraint
on message size. Trying to extend old school netlink (TC etc) left me
scarred. But we can do array, no big deal.
From: Nicolas Dichtel <hidden> Date: 2021-12-08 07:44:11
Le 07/12/2021 à 13:48, Lahav Schlesinger a écrit :
On Mon, Dec 06, 2021 at 09:25:17AM +0100, Nicolas Dichtel wrote:
quoted
CAUTION: External E-Mail - Use caution with links and attachments
Le 05/12/2021 à 10:36, Lahav Schlesinger a écrit :
Some comments below, but please, keep the people who replied to previous
versions of this patch in cc.
[snip]
nit: maybe the previous blank line sit better after this new attribute (and
before __IFLA_MAX)?
Due to the comment above the previous 2 attributes, I think that by
removing this empty line it can be accidentally thought as if the new
attribute is part of this "block".
As for adding a new line before __IFLA_MAX, I wanted to preserve the
appearance we had before the IFLA_PARENT_DEV_xxx attributes where added,
where there was no empty line before __IFLA_MAX.
Good point.
I don't mind either way though, whatever looks better to you.
@@ -3050,6 +3052,78 @@ static int rtnl_group_dellink(const struct net *net, int group) return 0; }+static int dev_ifindex_cmp(const void *a, const void *b)+{+ struct net_device * const *dev1 = a, * const *dev2 = b;
const struct net_device *dev1 = 1, *dev2 = b;
The array stores 'struct net_device *', and 'a' and 'b' are pointers to
elements in this array (so 'struct net_device **', ignoring constness)
quoted
++ return (*dev1)->ifindex - (*dev2)->ifindex;+}++static int rtnl_ifindex_dellink(struct net *net, struct nlattr *head, int len,+ struct netlink_ext_ack *extack)+{+ int i = 0, num_devices = 0, rem;+ struct net_device **dev_list;+ const struct nlattr *nla;+ LIST_HEAD(list_kill);+ int ret;++ nla_for_each_attr(nla, head, len, rem) {+ if (nla_type(nla) == IFLA_IFINDEX)+ num_devices++;+ }
The need to walk the list twice (3 really with the sort) to means the
array solution is better.
quoted
++ dev_list = kmalloc_array(num_devices, sizeof(*dev_list), GFP_KERNEL);+ if (!dev_list)+ return -ENOMEM;++ nla_for_each_attr(nla, head, len, rem) {+ const struct rtnl_link_ops *ops;+ struct net_device *dev;+ int ifindex;++ if (nla_type(nla) != IFLA_IFINDEX)+ continue;
and this business too. We have arrays in other places
(net/ipv4/nexthop.c), so this is not the first.
quoted
++ ifindex = nla_get_s32(nla);+ ret = -ENODEV;+ dev = __dev_get_by_index(net, ifindex);+ if (!dev) {+ NL_SET_ERR_MSG_ATTR(extack, nla, "Unknown ifindex");+ goto out_free;+ }++ ret = -EOPNOTSUPP;+ ops = dev->rtnl_link_ops;+ if (!ops || !ops->dellink) {+ NL_SET_ERR_MSG_ATTR(extack, nla, "Device cannot be deleted");+ goto out_free;+ }++ dev_list[i++] = dev;+ }++ /* Sort devices, so we could skip duplicates */+ sort(dev_list, num_devices, sizeof(*dev_list), dev_ifindex_cmp, NULL);
how did this sort change the results? 10k compares and re-order has to
add some overhead.
No visible changes from what I saw, this API is as fast as group
deletion. Maybe a few tens of milliseconds slower, but it's lost in the
noise.
I'll run more thorough benchmarks to get to a more conclusive conclusion.
Also just pointing out that the sort will be needed even if we pass an
array (IFLA_IFINDEX_LIST) instead.
Feels like CS 101, but do you have a better approach for detecting
duplicates in an array? I imagine a hash table will be slower as it will
need to allocate a node object for each device (assuming we don't want
to add a new hlist_node to 'struct net_device' just for this)
quoted
++ for (i = 0; i < num_devices; i++) {+ struct net_device *dev = dev_list[i];++ if (i != 0 && dev_list[i - 1]->ifindex == dev->ifindex)
if (i && ...)
I liked the array variant better. Jakub?
On Tue, Dec 07, 2021 at 07:37:15AM -0800, Jakub Kicinski wrote:
CAUTION: External E-Mail - Use caution with links and attachments
On Mon, 6 Dec 2021 21:12:33 -0700 David Ahern wrote:
quoted
The need to walk the list twice (3 really with the sort) to means the
array solution is better.
Technically the linear walk will be dwarfed by the sort for non-trivial
inputs (have I been conducting too many coding interviews?)
Especially with retpolines :(
quoted
I liked the array variant better. Jakub?
I always default to attr-per-member unless there is a strong constraint
on message size. Trying to extend old school netlink (TC etc) left me
scarred. But we can do array, no big deal.
Thanks, I'll send a new patch with array API and all previous comments
From: David Ahern <hidden> Date: 2021-12-08 23:43:34
On 12/8/21 2:47 PM, Lahav Schlesinger wrote:
No visible changes from what I saw, this API is as fast as group
deletion. Maybe a few tens of milliseconds slower, but it's lost in the
noise.
I'll run more thorough benchmarks to get to a more conclusive conclusion.
Also just pointing out that the sort will be needed even if we pass an
array (IFLA_IFINDEX_LIST) instead.
Feels like CS 101, but do you have a better approach for detecting
duplicates in an array? I imagine a hash table will be slower as it will
need to allocate a node object for each device (assuming we don't want
to add a new hlist_node to 'struct net_device' just for this)
I think marking the dev's and then using a delete loop is going to be
the better approach - avoid the sort and duplicate problem. I use that
approach for nexthop deletes:
https://git.kernel.org/pub/scm/linux/kernel/git/netdev/net-next.git/tree/net/ipv4/nexthop.c#n1849
Find a hole in net_device struct in an area used only for control path
and add 'bool grp_delete' (or a 1-bit hole). Mark the devices on pass
and delete them on another.
From: Jakub Kicinski <kuba@kernel.org> Date: 2021-12-09 00:04:15
On Wed, 8 Dec 2021 16:43:28 -0700 David Ahern wrote:
On 12/8/21 2:47 PM, Lahav Schlesinger wrote:
quoted
No visible changes from what I saw, this API is as fast as group
deletion. Maybe a few tens of milliseconds slower, but it's lost in the
noise.
I'll run more thorough benchmarks to get to a more conclusive conclusion.
Also just pointing out that the sort will be needed even if we pass an
array (IFLA_IFINDEX_LIST) instead.
Feels like CS 101, but do you have a better approach for detecting
duplicates in an array? I imagine a hash table will be slower as it will
need to allocate a node object for each device (assuming we don't want
to add a new hlist_node to 'struct net_device' just for this)
I think marking the dev's and then using a delete loop is going to be
the better approach - avoid the sort and duplicate problem. I use that
approach for nexthop deletes:
https://git.kernel.org/pub/scm/linux/kernel/git/netdev/net-next.git/tree/net/ipv4/nexthop.c#n1849
Find a hole in net_device struct in an area used only for control path
and add 'bool grp_delete' (or a 1-bit hole). Mark the devices on pass
and delete them on another.
If we want to keep state in the netdev itself we can probably piggy
back on dev->unreg_list. It should be initialized to empty and not
touched unless device goes thru unregister.
From: David Ahern <hidden> Date: 2021-12-09 00:18:57
On 12/8/21 5:04 PM, Jakub Kicinski wrote:
On Wed, 8 Dec 2021 16:43:28 -0700 David Ahern wrote:
quoted
On 12/8/21 2:47 PM, Lahav Schlesinger wrote:
quoted
No visible changes from what I saw, this API is as fast as group
deletion. Maybe a few tens of milliseconds slower, but it's lost in the
noise.
I'll run more thorough benchmarks to get to a more conclusive conclusion.
Also just pointing out that the sort will be needed even if we pass an
array (IFLA_IFINDEX_LIST) instead.
Feels like CS 101, but do you have a better approach for detecting
duplicates in an array? I imagine a hash table will be slower as it will
need to allocate a node object for each device (assuming we don't want
to add a new hlist_node to 'struct net_device' just for this)
I think marking the dev's and then using a delete loop is going to be
the better approach - avoid the sort and duplicate problem. I use that
approach for nexthop deletes:
https://git.kernel.org/pub/scm/linux/kernel/git/netdev/net-next.git/tree/net/ipv4/nexthop.c#n1849
Find a hole in net_device struct in an area used only for control path
and add 'bool grp_delete' (or a 1-bit hole). Mark the devices on pass
and delete them on another.
If we want to keep state in the netdev itself we can probably piggy
back on dev->unreg_list. It should be initialized to empty and not
touched unless device goes thru unregister.
isn't that used when the delink function calls unregister_netdevice_queue?
From: Jakub Kicinski <kuba@kernel.org> Date: 2021-12-09 00:45:51
On Wed, 8 Dec 2021 17:18:48 -0700 David Ahern wrote:
On 12/8/21 5:04 PM, Jakub Kicinski wrote:
quoted
quoted
I think marking the dev's and then using a delete loop is going to be
the better approach - avoid the sort and duplicate problem. I use that
approach for nexthop deletes:
https://git.kernel.org/pub/scm/linux/kernel/git/netdev/net-next.git/tree/net/ipv4/nexthop.c#n1849
Find a hole in net_device struct in an area used only for control path
and add 'bool grp_delete' (or a 1-bit hole). Mark the devices on pass
and delete them on another.
If we want to keep state in the netdev itself we can probably piggy
back on dev->unreg_list. It should be initialized to empty and not
touched unless device goes thru unregister.
isn't that used when the delink function calls unregister_netdevice_queue?
Sure but all the validation is before we start calling delink, so
doesn't matter?
list to_kill, queued;
for_each_attr(nest) {
...
dev = get_by_index(nla_get_s32(..));
if (!dev)
goto cleanup;
if (!list_empty(&dev->unreg_list))
goto cleanup;
...
list_add(&to_kill, &dev->unreg_list);
}
for_each_entry_safe(to_kill) {
list_del_init(&dev->unreg_list);
->dellink(dev, queued);
}
unreg_many(queued);
return
cleanup:
for_each_entry_safe(to_kill) {
list_del_init(&dev->unreg_list);
}
No?
From: David Ahern <hidden> Date: 2021-12-09 00:47:10
On 12/8/21 5:45 PM, Jakub Kicinski wrote:
On Wed, 8 Dec 2021 17:18:48 -0700 David Ahern wrote:
quoted
On 12/8/21 5:04 PM, Jakub Kicinski wrote:
quoted
quoted
I think marking the dev's and then using a delete loop is going to be
the better approach - avoid the sort and duplicate problem. I use that
approach for nexthop deletes:
https://git.kernel.org/pub/scm/linux/kernel/git/netdev/net-next.git/tree/net/ipv4/nexthop.c#n1849
Find a hole in net_device struct in an area used only for control path
and add 'bool grp_delete' (or a 1-bit hole). Mark the devices on pass
and delete them on another.
If we want to keep state in the netdev itself we can probably piggy
back on dev->unreg_list. It should be initialized to empty and not
touched unless device goes thru unregister.
isn't that used when the delink function calls unregister_netdevice_queue?
Sure but all the validation is before we start calling delink, so
doesn't matter?
list to_kill, queued;
for_each_attr(nest) {
...
dev = get_by_index(nla_get_s32(..));
if (!dev)
goto cleanup;
if (!list_empty(&dev->unreg_list))
goto cleanup;
...
list_add(&to_kill, &dev->unreg_list);
}
for_each_entry_safe(to_kill) {
list_del_init(&dev->unreg_list);
sure my mental model was walking the list and not doing that part. :-)
If we want to keep state in the netdev itself we can probably piggy
back on dev->unreg_list. It should be initialized to empty and not
touched unless device goes thru unregister.
isn't that used when the delink function calls unregister_netdevice_queue?
Sure but all the validation is before we start calling delink, so
doesn't matter?
list to_kill, queued;
for_each_attr(nest) {
...
dev = get_by_index(nla_get_s32(..));
if (!dev)
goto cleanup;
if (!list_empty(&dev->unreg_list))
goto cleanup;
...
list_add(&to_kill, &dev->unreg_list);
}
for_each_entry_safe(to_kill) {
list_del_init(&dev->unreg_list);
->dellink(dev, queued);
}
unreg_many(queued);
return
cleanup:
for_each_entry_safe(to_kill) {
list_del_init(&dev->unreg_list);
}
No?
Hi Jakub, I just sent a V6 for this patch. Just wanted to note that I
tried this approach of using unreg_list, but it caused issues with e.g.
veth deletion - the dellink() of a veth peer automatically adds the
other peer to the queued list. So if the list of ifindices contains
both peers then when 'to_kill' is iterated, both the current device
and the next pointer will have their 'unreg_list' moved to the other
list, which later raised a page fault when 'to_kill' was further
iterated upon.
Therefore instead I added a big flag in a "hole" inside struct
net_device, as David suggested.
From: Jakub Kicinski <kuba@kernel.org> Date: 2022-01-04 14:55:55
On Tue, 4 Jan 2022 10:21:21 +0200 Lahav Schlesinger wrote:
Hi Jakub, I just sent a V6 for this patch. Just wanted to note that I
tried this approach of using unreg_list, but it caused issues with e.g.
veth deletion - the dellink() of a veth peer automatically adds the
other peer to the queued list. So if the list of ifindices contains
both peers then when 'to_kill' is iterated, both the current device
and the next pointer will have their 'unreg_list' moved to the other
list, which later raised a page fault when 'to_kill' was further
iterated upon.
Therefore instead I added a big flag in a "hole" inside struct
net_device, as David suggested.