[PATCH 0/2] net: Replace custom page based bitmap with IDA

[PATCH 0/2] net: Replace custom page based bitmap with IDA

[Tobin C. Harding]

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(-)

-- 
2.7.4

[PATCH 1/2] include: Fix checkpatch whitespace error and warning

[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 <me@tobin.cc>
---
 include/linux/idr.h | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/include/linux/idr.h b/include/linux/idr.h
index 3c01b89..4a8de2f 100644
--- a/include/linux/idr.h
+++ b/include/linux/idr.h
@@ -1,6 +1,6 @@
 /*
  * include/linux/idr.h
- * 
+ *
  * 2002-10-18  written by Jim Houston jim.houston@ccur.com
  *	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

Re: [PATCH 1/2] include: Fix checkpatch whitespace error and warning

[Sergei Shtylyov]

Hello!

On 2/12/2017 5:57 AM, Tobin C. Harding wrote:

> 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 <me@tobin.cc>
> ---
>  include/linux/idr.h | 4 ++--
>  1 file changed, 2 insertions(+), 2 deletions(-)
>
> diff --git a/include/linux/idr.h b/include/linux/idr.h
> index 3c01b89..4a8de2f 100644
> --- a/include/linux/idr.h
> +++ b/include/linux/idr.h
> @@ -1,6 +1,6 @@
>  /*
>   * include/linux/idr.h
> - *
> + *
>   * 2002-10-18  written by Jim Houston jim.houston@ccur.com
>   *	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)

    Why replace tab with spaces?!

[...]

MBR, Sergei

RE: [PATCH 1/2] include: Fix checkpatch whitespace error and warning

[Matthew Wilcox]

Don't worry about this file; I have a complete rewrite already queued.

> -----Original Message-----
> From: Tobin C. Harding [mailto:me@tobin.cc]
> Sent: Saturday, February 11, 2017 9:58 PM
> To: David S . Miller <davem@davemloft.net>
> Cc: Matthew Wilcox <mawilcox@microsoft.com>; netdev@vger.kernel.org;
> linux-kernel@vger.kernel.org; Tobin C. Harding <me@tobin.cc>
> Subject: [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.
> 
> Signed-off-by: Tobin C. Harding <me@tobin.cc>
> ---
>  include/linux/idr.h | 4 ++--
>  1 file changed, 2 insertions(+), 2 deletions(-)
> 
> diff --git a/include/linux/idr.h b/include/linux/idr.h
> index 3c01b89..4a8de2f 100644
> --- a/include/linux/idr.h
> +++ b/include/linux/idr.h
> @@ -1,6 +1,6 @@
>  /*
>   * include/linux/idr.h
> - *
> + *
>   * 2002-10-18  written by Jim Houston jim.houston@ccur.com
>   *	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

[Tobin C. Harding]

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 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.

Signed-off-by: Tobin C. Harding <me@tobin.cc>
---
 net/core/dev.c | 20 ++++++--------------
 1 file changed, 6 insertions(+), 14 deletions(-)

diff --git a/net/core/dev.c b/net/core/dev.c
index 29101c9..b16ea84 100644
--- a/net/core/dev.c
+++ b/net/core/dev.c
@@ -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)
-- 
2.7.4