[PATCH 0/2] speed up net device allocation using pattern names

[PATCH 0/2] speed up net device allocation using pattern names

[Lucian Adrian Grijincu]

The next two patches:
- add a faster way to add net devices using pattern names like "dummy%d"
- call that routine for dummy

Patches are against net-next, but should apply cleanly to 3.0-rc1 too.

Lucian Adrian Grijincu (2):
  net: add alloc_netdev_mqs_id
  net: dummy: allocate devices with alloc_netdev_id

 drivers/net/dummy.c       |    4 ++-
 include/linux/netdevice.h |    7 +++++
 net/core/dev.c            |   63 +++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 73 insertions(+), 1 deletions(-)

-- 
1.7.5.2.317.g391b14

[PATCH 1/2] net: add alloc_netdev_mqs_id

[Lucian Adrian Grijincu]

The complexity of alloc_netdev_mqs depends on the type of the device name:
- O(nr-net-devices) - for a device name with '%d' in it
- O(1)              - for given device name without any format.

The difference comes from the path chosen in __dev_alloc_name: if '%d'
is found in the name (e.g. 'dummy%d') it will:
- match all the devices in the that network namespace with the device
  name format extracting all used values for '%d' (e.g. 'dummy0',
  'dummy1', dummy3' => {0, 1 ,3} are used)
- create a device with the smallest unused value (e.g. 'dummy2').

Obviously the O(N) part comes the for_each_netdev loop. One could keep
around a precomputed table of values that are in use for each pattern
that is of interest (patterns for with there will be large numbers of
devices created) and make sure to mark slots as unused when
unregistering the device. The table would have no use after
registering a device and would need to be netns-specific.

Things get more complicated when taking into consideration device
renames and registration of devices that do not use patterns in names
(e.g. an explicit registration of a device with the 'dummy3' name).

This patch adds a new method of creating device names that aims to sit
in the middle: accept device names patterns with '%d' and the last
value used for '%d'. If the next slot is not taken, alloc_netdev_mqs_id
will be an O(1) operation. If that name is taken it falls back on
the O(N) algorithm.

Signed-off-by: Lucian Adrian Grijincu <lucian.grijincu@gmail.com>
---
 include/linux/netdevice.h |    7 +++++
 net/core/dev.c            |   63 +++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 70 insertions(+), 0 deletions(-)

diff --git a/include/linux/netdevice.h b/include/linux/netdevice.h
index ca333e7..612c1f3 100644
--- a/include/linux/netdevice.h
+++ b/include/linux/netdevice.h
@@ -2452,9 +2452,16 @@ extern void		ether_setup(struct net_device *dev);
 extern struct net_device *alloc_netdev_mqs(int sizeof_priv, const char *name,
 				       void (*setup)(struct net_device *),
 				       unsigned int txqs, unsigned int rxqs);
+extern struct net_device *alloc_netdev_mqs_id(int sizeof_priv, const char *name,
+		void (*setup)(struct net_device *),
+		unsigned int txqs, unsigned int rxqs, int *p_last_id);
+
 #define alloc_netdev(sizeof_priv, name, setup) \
 	alloc_netdev_mqs(sizeof_priv, name, setup, 1, 1)
 
+#define alloc_netdev_id(sizeof_priv, name, setup, p_last_id)	\
+	alloc_netdev_mqs_id(sizeof_priv, name, setup, 1, 1, p_last_id)
+
 #define alloc_netdev_mq(sizeof_priv, name, setup, count) \
 	alloc_netdev_mqs(sizeof_priv, name, setup, count, count)
 
diff --git a/net/core/dev.c b/net/core/dev.c
index 9393078..0862e81 100644
--- a/net/core/dev.c
+++ b/net/core/dev.c
@@ -5908,6 +5908,69 @@ free_p:
 }
 EXPORT_SYMBOL(alloc_netdev_mqs);
 
+
+/**
+ * alloc_netdev_mqs_id - allocate a network device
+ *
+ * @name      - format of the device name. E.g. 'dummy%d'
+ * @p_last_id - IN: last known value that was given to '%d'
+ *              OUT: the value used for '%d' for the newly created device
+ *
+ *	@sizeof_priv:	size of private data to allocate space for
+ *	@setup:		callback to initialize device
+ *	@txqs:		the number of TX subqueues to allocate
+ *	@rxqs:		the number of RX subqueues to allocate
+ *
+ * alloc_netdev_mqs' complexity depends on the device name:
+ *  - O(nr-net-devices) - for a device name with '%d' in it
+ *  - O(1)              - for given device name without any format.
+ *
+ * alloc_netdev_mqs_id takes an extra argument: the last value that was
+ * used to fill '%d' in the name pattern. It uses this to create name
+ * that is likely to not be used (last_id+1) and tries to register a
+ * device with that name - O(1). If that fails it drops to the O(N)
+ * algorithm by sending the device name format.
+ *
+ * alloc_netdev_mqs will always make sure to find the smallest unused
+ * value for the '%d' in the name. alloc_netdev_mqs_id does not.
+ *
+ * E.g.:
+ * - you create 8 devices by calling alloc_netdev_mqs_id ('eth0' .. 'eth7')
+ *   and you know the next free slot is 'eth8'.
+ * - someone renames 'eth2' to 'some-other-name'
+ * - the next device created by alloc_netdev_mqs_id will be 'eth8'
+ *   even though 'eth2' could have been used.
+ */
+struct net_device *alloc_netdev_mqs_id(int sizeof_priv, const char *name,
+		void (*setup)(struct net_device *),
+		unsigned int txqs, unsigned int rxqs, int *p_last_id)
+{
+	struct net_device *dev;
+	char buf[IFNAMSIZ];
+
+	int new_id = (*p_last_id) + 1;
+
+	/* first try with explicit name - O(1) */
+	snprintf(buf, IFNAMSIZ, name, new_id);
+	dev = alloc_netdev_mqs(sizeof_priv, buf, setup, txqs, rxqs);
+	if (dev)
+		goto out;
+
+	/* fallback: create a name automatically - O(N) */
+	dev = alloc_netdev_mqs(sizeof_priv, name, setup, txqs, rxqs);
+	if (!dev)
+		goto fail;
+
+	sscanf(dev->name, name, &new_id);
+
+out:
+	*p_last_id = new_id;
+fail:
+	return dev;
+}
+EXPORT_SYMBOL(alloc_netdev_mqs_id);
+
+
 /**
  *	free_netdev - free network device
  *	@dev: device
-- 
1.7.5.2.317.g391b14

[PATCH 2/2] net: dummy: allocate devices with alloc_netdev_id

[Lucian Adrian Grijincu]

The most like case is that no one else is registering devices with a
name like "dummy%d".

We can bring the complexity down by replacing:
- alloc_netdev_id which is O(N) with
- alloc_netdev_id which, on the average case, is O(1).

$ time modprobe dummy numdummies=5000
- with alloc_netdev   : 9.50s
- with alloc_netdev_id: 3.50s

NOTE: Stats generated on a heavily patched 3.0-rc1 which replaces the
      current O(N^2) sysctl algorithm with a better one.

Signed-off-by: Lucian Adrian Grijincu <lucian.grijincu@gmail.com>
---
 drivers/net/dummy.c |    4 +++-
 1 files changed, 3 insertions(+), 1 deletions(-)

diff --git a/drivers/net/dummy.c b/drivers/net/dummy.c
index 39cf9b9..24d4ee5 100644
--- a/drivers/net/dummy.c
+++ b/drivers/net/dummy.c
@@ -159,12 +159,14 @@ static struct rtnl_link_ops dummy_link_ops __read_mostly = {
 module_param(numdummies, int, 0);
 MODULE_PARM_DESC(numdummies, "Number of dummy pseudo devices");
 
+
+static int last_device_id = -1;
 static int __init dummy_init_one(void)
 {
 	struct net_device *dev_dummy;
 	int err;
 
-	dev_dummy = alloc_netdev(0, "dummy%d", dummy_setup);
+	dev_dummy = alloc_netdev_id(0, "dummy%d", dummy_setup, &last_device_id);
 	if (!dev_dummy)
 		return -ENOMEM;
 
-- 
1.7.5.2.317.g391b14

Re: [PATCH 2/2] net: dummy: allocate devices with alloc_netdev_id

[Eric Dumazet]

Le mardi 07 juin 2011 à 04:39 +0300, Lucian Adrian Grijincu a écrit :
> The most like case is that no one else is registering devices with a
> name like "dummy%d".
> 
> We can bring the complexity down by replacing:
> - alloc_netdev_id which is O(N) with
> - alloc_netdev_id which, on the average case, is O(1).
> 
> $ time modprobe dummy numdummies=5000
> - with alloc_netdev   : 9.50s
> - with alloc_netdev_id: 3.50s
> 
> NOTE: Stats generated on a heavily patched 3.0-rc1 which replaces the
>       current O(N^2) sysctl algorithm with a better one.

Yes, and disabled hotplug I guess.

Dont try this on a random computer ;)

# time modprobe dummy numdummies=5000

real	4m45.646s
user	0m0.000s
sys	0m12.440s
# uptime
 05:13:46 up 13:30,  3 users,  load average: 11221.41, 6918.70, 3101.12
# uptime
 05:18:45 up 13:35,  3 users,  load average: 12159.82, 10277.39, 5623.19

Re: [PATCH 2/2] net: dummy: allocate devices with alloc_netdev_id

[David Miller]

From: Eric Dumazet <eric.dumazet@gmail.com>
Date: Tue, 07 Jun 2011 05:19:25 +0200

> Le mardi 07 juin 2011 à 04:39 +0300, Lucian Adrian Grijincu a écrit :
>> The most like case is that no one else is registering devices with a
>> name like "dummy%d".
>> 
>> We can bring the complexity down by replacing:
>> - alloc_netdev_id which is O(N) with
>> - alloc_netdev_id which, on the average case, is O(1).
>> 
>> $ time modprobe dummy numdummies=5000
>> - with alloc_netdev   : 9.50s
>> - with alloc_netdev_id: 3.50s
>> 
>> NOTE: Stats generated on a heavily patched 3.0-rc1 which replaces the
>>       current O(N^2) sysctl algorithm with a better one.
> 
> Yes, and disabled hotplug I guess.
> 
> Dont try this on a random computer ;)
> 
> # time modprobe dummy numdummies=5000
> 
> real	4m45.646s
> user	0m0.000s
> sys	0m12.440s
> # uptime
>  05:13:46 up 13:30,  3 users,  load average: 11221.41, 6918.70, 3101.12

ROFL

Re: [PATCH 2/2] net: dummy: allocate devices with alloc_netdev_id

[Lucian Adrian Grijincu]

On Tue, Jun 7, 2011 at 6:19 AM, Eric Dumazet <eric.dumazet@gmail.com> wrote:
> Le mardi 07 juin 2011 à 04:39 +0300, Lucian Adrian Grijincu a écrit :
>> The most like case is that no one else is registering devices with a
>> name like "dummy%d".
>>
>> We can bring the complexity down by replacing:
>> - alloc_netdev_id which is O(N) with
>> - alloc_netdev_id which, on the average case, is O(1).
>>
>> $ time modprobe dummy numdummies=5000
>> - with alloc_netdev   : 9.50s
>> - with alloc_netdev_id: 3.50s
>>
>> NOTE: Stats generated on a heavily patched 3.0-rc1 which replaces the
>>       current O(N^2) sysctl algorithm with a better one.
>
> Yes, and disabled hotplug I guess.


$ cat .config | grep HOTPLUG
CONFIG_HOTPLUG=y
# CONFIG_MEMORY_HOTPLUG is not set
CONFIG_HOTPLUG_CPU=y
CONFIG_ARCH_ENABLE_MEMORY_HOTPLUG=y
CONFIG_ACPI_HOTPLUG_CPU=y
# CONFIG_HOTPLUG_PCI is not set

I would guess you're going for CONFIG_HOTPLUG_PCI or
CONFIG_HOTPLUG_CPU, but I don't understand the implications.


> Dont try this on a random computer ;)

Could you briefly explain what's at stake here? What can go wrong if
we do this? I wasn't advocating replacing all alloc_netdev calls with
the new call.


> # time modprobe dummy numdummies=5000
>
> real    4m45.646s
> user    0m0.000s
> sys     0m12.440s
> # uptime
>  05:13:46 up 13:30,  3 users,  load average: 11221.41, 6918.70, 3101.12
> # uptime
>  05:18:45 up 13:35,  3 users,  load average: 12159.82, 10277.39, 5623.19


I don't get where you're going with these stats.

I don't care much about these patches, and even less if they're
fundamentally borked, but I'd like to know how/why they're not ok.

Please spare a second and illuminate me; I feel left out on a big joke.


-- 
 .
..: Lucian

Re: [PATCH 2/2] net: dummy: allocate devices with alloc_netdev_id

[Eric Dumazet]

Le mardi 07 juin 2011 à 10:49 +0300, Lucian Adrian Grijincu a écrit :
> On Tue, Jun 7, 2011 at 6:19 AM, Eric Dumazet <eric.dumazet@gmail.com> wrote:
> > Le mardi 07 juin 2011 à 04:39 +0300, Lucian Adrian Grijincu a écrit :
> >> The most like case is that no one else is registering devices with a
> >> name like "dummy%d".
> >>
> >> We can bring the complexity down by replacing:
> >> - alloc_netdev_id which is O(N) with
> >> - alloc_netdev_id which, on the average case, is O(1).
> >>
> >> $ time modprobe dummy numdummies=5000
> >> - with alloc_netdev   : 9.50s
> >> - with alloc_netdev_id: 3.50s
> >>
> >> NOTE: Stats generated on a heavily patched 3.0-rc1 which replaces the
> >>       current O(N^2) sysctl algorithm with a better one.
> >
> > Yes, and disabled hotplug I guess.
> 
> 

Some distros have :

$ cat /proc/sys/kernel/hotplug
/sbin/hotplug

http://linux.die.net/man/8/hotplug

Basically this starts a lot of process when a new device is created.

modprobe dummy numdummies=5000

This previous line ask 5000 asynchronous hotplug start, so it launches
thousands of processes, all fighting to get RTNL because they access
network configuration data.


Please note I was not commenting your patch (it seems fine at a first
glance), only warning people not doing "modprobe dummy numdummies=5000"
without thinking a bit if their machine wont crash or freeze :)

Re: [PATCH 2/2] net: dummy: allocate devices with alloc_netdev_id

[Lucian Adrian Grijincu]

On Tue, Jun 7, 2011 at 10:59 AM, Eric Dumazet <eric.dumazet@gmail.com> wrote:
> Please note I was not commenting your patch (it seems fine at a first
> glance), only warning people not doing "modprobe dummy numdummies=5000"
> without thinking a bit if their machine wont crash or freeze :)


Sorry for fooling you into killing your machine. :))

Later today I'll post a scheduler patch that speeds up the fork bomb too :)

Thank you for the explanation.


@David: I see [1][2] that you marked the patches as Rejected. If it's
not a script that sends all my patches to /dev/null because of the
100+ patch set I sent a while back, could you tell me why you rejected
the patches?

Something fundamentally wrong with them, optimisations that "normal
people" don't care about, etc.?



[1] http://patchwork.ozlabs.org/patch/99065/
[2] http://patchwork.ozlabs.org/patch/99066/
-- 
 .
..: Lucian

Re: [PATCH 2/2] net: dummy: allocate devices with alloc_netdev_id

[David Miller]

From: Lucian Adrian Grijincu <lucian.grijincu@gmail.com>
Date: Tue, 7 Jun 2011 11:30:38 +0300

> @David: I see [1][2] that you marked the patches as Rejected. If it's
> not a script that sends all my patches to /dev/null because of the
> 100+ patch set I sent a while back, could you tell me why you rejected
> the patches?

I misfired while changing patch states earlier today, I put them back
into "Under Review"

Re: [PATCH 2/2] net: dummy: allocate devices with alloc_netdev_id

[David Miller]

From: David Miller <davem@davemloft.net>
Date: Tue, 07 Jun 2011 02:29:26 -0700 (PDT)

> From: Lucian Adrian Grijincu <lucian.grijincu@gmail.com>
> Date: Tue, 7 Jun 2011 11:30:38 +0300
> 
>> @David: I see [1][2] that you marked the patches as Rejected. If it's
>> not a script that sends all my patches to /dev/null because of the
>> 100+ patch set I sent a while back, could you tell me why you rejected
>> the patches?
> 
> I misfired while changing patch states earlier today, I put them back
> into "Under Review"

So I took a look again, you're patches introduce problems.

We don't do the instance allocation and (more importantly) conflict
validation of the netdev name in alloc_netdev_mqs(), we do it when the
netdev is registered.

So with your patch some other entity could rename a random netdev
to "dummy62" in between the alloc_netdev_id() call and the register
and the register will fail erroneously.

I really don't like this optimization, sorry.  Make dev_alloc_name()
less stupid instead.