net: Replace custom page based bitmap with IDA
Subsystems (3)
cover net: Replace custom page based bitmap with IDA
Current implementation of __dev_alloc_name uses a custom bitmap of a single page to iterate network device id's and allocate an unused id. This is seemingly the same task that the IDA does. Also the current implementation leads to a upper limit of 8 * PAGE_SIZE on the number of network id's (for each name format i.e eth0).
This patch uses the kernel's IDA as a replacement to the page based bitmap. This has the effect of simplifying the code and removing the upper limit.
Testing was carried out using a simple network device module, the core of which is;
#define NDEVICES 32768 /* current implementation hard limit */
/* test driver */
static int tm_init_module(void)
{
int result;
int i;
unsigned long before, after, diff, msec;
pr_debug("tm: init module");
before = jiffies;
for (i = 0; i < NDEVICES; i++) {
devs[i] = alloc_netdev(0, "sn%d",
NET_NAME_UNKNOWN, tm_init);
if (!devs[i])
return -ENOMEM;
result = register_netdev(devs[i]);
if (result) {
pr_err("tm: error %i registering device \"%s\"\n",
result, devs[i]->name);
tm_cleanup();
return -ENODEV;
}
}
after = jiffies;
diff = (long)after - (long)before;
msec = diff * 1000 / HZ;
pr_debug("tm: Total milliseconds: %ld\n", msec);
return 0;
}module_init(tm_init_module);
The main objective of this patch is to simplify the code of __dev_alloc_name. As a side effect the hard limit is also removed. Results from running the, admittedly convoluted, test module show that the patched version is slightly slower.
Benchmarks
==========
System: core i5 Linux 4.10.0-rc7+ #18 SMP
$ qemu-system-x86_64 -kernel arch/x86_64/boot/bzImage -drive file=/home/tobin/build/imgs/qemu-image.img,index=0,media=disk,format=raw -append "root=/dev/sda console=ttyS0" --enable-kvm --nographic -m 12G
Current implementation
#define NDEVICES 30000
[ 134.376741] tm: Total milliseconds: 127152
Patched version
#define NDEVICES 30000
[ 226.960212] tm: Total milliseconds: 220756
#define NDEVICES 35000
[ 276.590994] tm: Total milliseconds: 270620
Tobin C. Harding (2):
include: Fix checkpatch whitespace error and warning
net: Replace custom page based bitmap with IDA
include/linux/idr.h | 4 ++-- net/core/dev.c | 20 ++++++-------------- 2 files changed, 8 insertions(+), 16 deletions(-)
Signature · 1 line
2.7.4
PATCH 1/2 include: Fix checkpatch whitespace error and warning
This patch fixes two trivial whitespace messages (ERROR/WARNING). Fixes trailing whitespace ERROR and fixes space before tabs WARNING.
--- include/linux/idr.h | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)
include/linux/idr.h +2 -2
@@ -1,6 +1,6 @@/* * include/linux/idr.h -* +* * 2002-10-18 written by Jim Houston [email protected] * Copyright (C) 2002 by Concurrent Computer Corporation * Distributed under the GNU GPL license version 2.
@@ -183,7 +183,7 @@ static inline void *idr_find(struct idr *idr, int id)*/ #define IDA_CHUNK_SIZE 128/* 128 bytes per chunk */ #define IDA_BITMAP_LONGS (IDA_CHUNK_SIZE / sizeof(long) - 1) -#define IDA_BITMAP_BITS (IDA_BITMAP_LONGS * sizeof(long) * 8) +#define IDA_BITMAP_BITS (IDA_BITMAP_LONGS * sizeof(long) * 8)struct ida_bitmap {long nr_busy;
Signature · 1 line
2.7.4
Re: [PATCH 1/2] include: Fix checkpatch whitespace error and warning
Hello!
Quoted 21 lines · Tobin C. Harding
This patch fixes two trivial whitespace messages (ERROR/WARNING). Fixes trailing whitespace ERROR and fixes space before tabs WARNING.
Signed-off-by Tobin C. Harding <[email protected]>--- include/linux/idr.h | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)include/linux/idr.h +1
-1@@ -1,6 +1,6 @@/* * include/linux/idr.h -* +* * 2002-10-18 written by Jim Houston [email protected] * Copyright (C) 2002 by Concurrent Computer Corporation * Distributed under the GNU GPL license version 2.
include/linux/idr.h static inline void *idr_find(struct idr *idr, int id) · line 186
Quoted 5 lines
include/linux/idr.h +1
-1@@ -183,7 +183,7 @@ static inline void *idr_find(struct idr *idr, int id)*/ #define IDA_CHUNK_SIZE 128/* 128 bytes per chunk */ #define IDA_BITMAP_LONGS (IDA_CHUNK_SIZE / sizeof(long) - 1) -#define IDA_BITMAP_BITS (IDA_BITMAP_LONGS * sizeof(long) * 8) +#define IDA_BITMAP_BITS (IDA_BITMAP_LONGS * sizeof(long) * 8)
Why replace tab with spaces?!
[...]
MBR, Sergei
RE: [PATCH 1/2] include: Fix checkpatch whitespace error and warning
In reply to Tobin C. HardingDon't worry about this file; I have a complete rewrite already queued.
Quoted 39 lines
-----Original Message-----
From: Tobin C. Harding [mailto:[email protected]]
Sent: Saturday, February 11, 2017 9:58 PM
To: David S . Miller <[email protected]>
Cc: Matthew Wilcox <[email protected]>; [email protected]; [email protected]; Tobin C. Harding <[email protected]>
Subject: [PATCH 1/2] include: Fix checkpatch whitespace error and warningThis patch fixes two trivial whitespace messages (ERROR/WARNING). Fixes trailing whitespace ERROR and fixes space before tabs WARNING.
Signed-off-by Tobin C. Harding <[email protected]>--- include/linux/idr.h | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)include/linux/idr.h +2
-3@@ -1,6 +1,6 @@/* * include/linux/idr.h -* +* * 2002-10-18 written by Jim Houston [email protected] * Copyright (C) 2002 by Concurrent Computer Corporation * Distributed under the GNU GPL license version 2. @@ -183,7 +183,7 @@ static inline void *idr_find(struct idr *idr, int id)*/ #define IDA_CHUNK_SIZE 128/* 128 bytes per chunk */ #define IDA_BITMAP_LONGS (IDA_CHUNK_SIZE / sizeof(long) - 1) -#define IDA_BITMAP_BITS (IDA_BITMAP_LONGS * sizeof(long) * 8) +#define IDA_BITMAP_BITS (IDA_BITMAP_LONGS * sizeof(long) * 8)struct ida_bitmap {long nr_busy; --2.7.4
PATCH 2/2 net: Replace custom page based bitmap with IDA
In reply to Tobin C. HardingCurrent implementation of __dev_alloc_name uses a custom bitmap of a single page to iterate network device id's and allocate an unused id. This leads to a upper limit of 8 * PAGE_SIZE network device id's (for each name format i.e eth0).
This patch uses the kernel's IDA as a replacement to the page based bitmap. This has the effect of simplifying the code and removing the upper limit.
--- net/core/dev.c | 20 ++++++-------------- 1 file changed, 6 insertions(+), 14 deletions(-)
net/core/dev.c +6 -14
@@ -1025,39 +1025,31 @@ static int __dev_alloc_name(struct net *net, const char *name, char *buf) {int i =0 ;const char *p; -const int max_netdevices =8 *PAGE_SIZE ; -unsigned long *inuse;struct net_device *d; +DEFINE_IDA (ida); +const int end =0 ; p =strnchr (name,IFNAMSIZ -1 ,'%' );if (p) { -/* -* Verify the string as this thing may have come from +/* Verify the string as this thing may have come from * the user. There must be either one "%d" and no other "%" * characters. */ if (p[1 ] !='d' ||strchr (p +2 ,'%' ))return -EINVAL ; -/* Use one page as a bit array of possible slots */ - inuse = (unsigned long *)get_zeroed_page (GFP_ATOMIC ); -if (!inuse) -return -ENOMEM ; -for_each_netdev (net, d) {if (!sscanf (d->name, name, &i))continue ; -if (i <0 || i >= max_netdevices) +if (i <0 )continue ;/* avoid cases where sscanf is not exact inverse of printf */ snprintf (buf,IFNAMSIZ , name, i);if (!strncmp (buf, d->name,IFNAMSIZ )) -set_bit (i, inuse); +ida_simple_get (&ida, i, end,GFP_KERNEL ); } - - i =find_first_zero_bit (inuse, max_netdevices); -free_page ((unsigned long ) inuse); + i =ida_simple_get (&ida,0 , end,GFP_KERNEL ); }if (buf != name)
Signature · 1 line
2.7.4