Skip to contentSkip to conversation

net: Replace custom page based bitmap with IDA

PATCH In review Tobin C. Harding 3 participants 5 messages Feb 12, 2017

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

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
#1 lore raw

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
index 3c01b89..4a8de2f 100644
@@ -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
#2 lore raw

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.

---
 include/linux/idr.h | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)
include/linux/idr.h +1 -1
index 3c01b89..4a8de2f 100644
@@ -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

#3 lore raw

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

In reply to Tobin C. Harding

Don'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 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 -3
index 3c01b89..4a8de2f 100644
@@ -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

#4 lore raw

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

In reply to 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.

---
 net/core/dev.c | 20 ++++++--------------
 1 file changed, 6 insertions(+), 14 deletions(-)
net/core/dev.c +6 -14
index 29101c9..b16ea84 100644
@@ -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