[PATCH 2/2 v2] chrdev: allocate dynamic chardevs in all unused holes

[PATCH 2/2 v2] chrdev: allocate dynamic chardevs in all unused holes

[Linus Walleij]

This is a duct-tape-and-chewing-gum solution to the problem
with the major numbers running out when allocating major
numbers dynamically.

To avoid collisions in the major space, we supply a bitmap with
"holes" that exist in the lower range of major numbers [0-254]
and pick numbers from there, beginning with the unused char
device 8 and moving up through 26, 40, 60-63, 93-94, 102,
120-127, 159, 213-215, 222-223 and 234-254.

It will also FAIL if we actually fill up all free major
numbers. This seems to me like the reasonable thing to do
since the other numbers are, after all, reserved.

This also adds the macro BITS() to <linux/bitops.h> so we can
define the static bitmap at compiletime in a reasonable way.
If someone prefer that I just put opaque hex numbers in there,
then tell me, that works too, it's just not elegant IMO.

This also deletes the comment /* temporary */ which must be
one of the biggest lies ever.

This also updates the Documentation/devices.txt document to
reflect that all these numbers are used for dynamic assignment.

Reported-by: Ying Huang <ying.huang@linux.intel.com>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
Cc: Alan Cox <alan@linux.intel.com>
Cc: Arnd Bergmann <arnd@arndb.de>
Signed-off-by: Linus Walleij <linus.walleij@linaro.org>
---
ChangeLog v1->v2:
- Follow-up on the previous RFC patch, this uses Torvald's
  suggested bitmap approach to allocate devices instead of
  a list of free numbers.
- As a result of using find_first_zero_bit(), the major
  numbers are assigned from low to high instead from high
  to low. It's a bit scarier but I guess drivers using
  dynamic numbers should be all right with it, I'm more
  worried about userspaces expecting dynamic majors to
  be in the [234,254] range. Input welcome, maybe I'm
  just chicken.
- This still needs to be applied on top of the previous
  fix to start warning about going below major 234. If
  you prefer to just get this patch and get rid of the
  problem then tell me.
---
 Documentation/devices.txt | 22 ++++++++++++++--------
 fs/char_dev.c             | 46 ++++++++++++++++++++++++++++++++++------------
 include/linux/bitops.h    |  1 +
 include/linux/fs.h        |  2 --
 4 files changed, 49 insertions(+), 22 deletions(-)

diff --git a/Documentation/devices.txt b/Documentation/devices.txt
index 4035eca87144..2a4242be2fcd 100644
--- a/Documentation/devices.txt
+++ b/Documentation/devices.txt
@@ -248,6 +248,8 @@ Your cooperation is appreciated.
 		associated with block devices.	The binding to the
 		loop devices is handled by mount(8) or losetup(8).
 
+  8 char	RESERVED FOR DYNAMIC ALLOCATION OF MAJOR NUMBERS
+
   8 block	SCSI disk devices (0-15)
 		  0 = /dev/sda		First SCSI disk whole disk
 		 16 = /dev/sdb		Second SCSI disk whole disk
@@ -620,7 +622,7 @@ Your cooperation is appreciated.
 		  2 = /dev/sbpcd2	Panasonic CD-ROM controller 0 unit 2
 		  3 = /dev/sbpcd3	Panasonic CD-ROM controller 0 unit 3
 
- 26 char
+ 26 char	RESERVED FOR DYNAMIC ALLOCATION OF MAJOR NUMBERS
 
  26 block	Second Matsushita (Panasonic/SoundBlaster) CD-ROM
 		  0 = /dev/sbpcd4	Panasonic CD-ROM controller 1 unit 0
@@ -863,7 +865,7 @@ Your cooperation is appreciated.
 		      ...
  39 block
 
- 40 char
+ 40 char	RESERVED FOR DYNAMIC ALLOCATION OF MAJOR NUMBERS
 
  40 block
 
@@ -1127,7 +1129,7 @@ Your cooperation is appreciated.
 
 		NAMING CONFLICT -- PROPOSED REVISED NAME /dev/rpda0 etc
 
- 60-63 char	LOCAL/EXPERIMENTAL USE
+ 60-63 char	RESERVED FOR DYNAMIC ALLOCATION OF MAJOR NUMBERS
 
  60-63 block	LOCAL/EXPERIMENTAL USE
 		Allocated for local/experimental use.  For devices not
@@ -1641,7 +1643,7 @@ Your cooperation is appreciated.
 		disks (see major number 3) except that the limit on
 		partitions is 15.
 
- 93 char
+ 93 char	RESERVED FOR DYNAMIC ALLOCATION OF MAJOR NUMBERS
 
  93 block	NAND Flash Translation Layer filesystem
 		  0 = /dev/nftla	First NFTL layer
@@ -1649,7 +1651,7 @@ Your cooperation is appreciated.
 		    ...
 		240 = /dev/nftlp	16th NTFL layer
 
- 94 char
+ 94 char	RESERVED FOR DYNAMIC ALLOCATION OF MAJOR NUMBERS
 
  94 block	IBM S/390 DASD block storage
     		  0 = /dev/dasda First DASD device, major
@@ -1742,7 +1744,7 @@ Your cooperation is appreciated.
 		    ...
 		 15 = /dev/amiraid/ar?p15 15th partition
 
-102 char
+102 char	RESERVED FOR DYNAMIC ALLOCATION OF MAJOR NUMBERS
 
 102 block	Compressed block device
 		  0 = /dev/cbd/a	First compressed block device, whole device
@@ -2027,7 +2029,7 @@ Your cooperation is appreciated.
 		  1 = /dev/vnet1	2nd virtual network
 		    ...
 
-120-127 char	LOCAL/EXPERIMENTAL USE
+120-127 char	RESERVED FOR DYNAMIC ALLOCATION OF MAJOR NUMBERS
 
 120-127 block	LOCAL/EXPERIMENTAL USE
 		Allocated for local/experimental use.  For devices not
@@ -2341,7 +2343,7 @@ Your cooperation is appreciated.
 		  1 = /dev/gfax1	GammaLink channel 1
 		    ...
 
-159 char	RESERVED
+159 char	RESERVED FOR DYNAMIC ALLOCATION OF MAJOR NUMBERS
 
 159 block	RESERVED
 
@@ -2929,6 +2931,8 @@ Your cooperation is appreciated.
 		    ...
 		196 = /dev/dvb/adapter3/video0    first video decoder of fourth card
 
+213-215 char	RESERVED FOR DYNAMIC ALLOCATION OF MAJOR NUMBERS
+
 216 char	Bluetooth RFCOMM TTY devices
 		  0 = /dev/rfcomm0		First Bluetooth RFCOMM TTY device
 		  1 = /dev/rfcomm1		Second Bluetooth RFCOMM TTY device
@@ -2971,6 +2975,8 @@ Your cooperation is appreciated.
 		same interface.  For interface documentation see
 		http://www.vmelinux.org/.
 
+222-223 char	RESERVED FOR DYNAMIC ALLOCATION OF MAJOR NUMBERS
+
 224 char	A2232 serial card
 		  0 = /dev/ttyY0		First A2232 port
 		  1 = /dev/ttyY1		Second A2232 port
diff --git a/fs/char_dev.c b/fs/char_dev.c
index 687471dc04a0..d37319bca072 100644
--- a/fs/char_dev.c
+++ b/fs/char_dev.c
@@ -21,6 +21,8 @@
 #include <linux/mutex.h>
 #include <linux/backing-dev.h>
 #include <linux/tty.h>
+#include <linux/bitmap.h>
+#include <linux/bitops.h>
 
 #include "internal.h"
 
@@ -37,6 +39,31 @@ static struct char_device_struct {
 	struct cdev *cdev;		/* will die */
 } *chrdevs[CHRDEV_MAJOR_HASH_SIZE];
 
+/*
+ * A bitmap for the 255 lower device numbers. A "1" means the
+ * major number is taken, a "0" means it is available. We first
+ * need to define all the assigned devices as taken so that
+ * dynamic device allocation will not go in and steal them.
+ */
+static u32 majors_map[] = {
+	/* 8 and 26 are free */
+	BITS(0, 7) | BITS(9, 25) | BITS(27, 31),
+	/* 40 and 60-63 are free */
+	BITS(0, 7) | BITS(9, 27),
+	/* 93 and 94 are free */
+	BITS(0, 28) | BIT(31),
+	/* 102 and 120-127 are free */
+	BITS(0, 5) | BITS(7, 23),
+	/* 159 is free */
+	BITS(0, 30),
+	/* No free numbers */
+	~0x0U,
+	/* 213-215 and 222-223 are free */
+	BITS(0, 20) | BITS(24, 29),
+	/* 234-254 are free */
+	BITS(0, 9) | BIT(31)
+};
+
 /* index in the above */
 static inline int major_to_index(unsigned major)
 {
@@ -84,22 +111,17 @@ __register_chrdev_region(unsigned int major, unsigned int baseminor,
 
 	mutex_lock(&chrdevs_lock);
 
-	/* temporary */
 	if (major == 0) {
-		for (i = ARRAY_SIZE(chrdevs)-1; i > 0; i--) {
-			if (chrdevs[i] == NULL)
-				break;
-		}
-
-		if (i < CHRDEV_MAJOR_DYN_END)
-			pr_warn("CHRDEV \"%s\" major number %d goes below the dynamic allocation range",
-				name, i);
-
-		if (i == 0) {
+		major = find_first_zero_bit(majors_map, CHRDEV_MAJOR_HASH_SIZE);
+		if (major == CHRDEV_MAJOR_HASH_SIZE) {
+			pr_warn("CHRDEV: \"%s\" out of major numbers",
+				name);
 			ret = -EBUSY;
 			goto out;
 		}
-		major = i;
+		set_bit(major, (unsigned long *)majors_map);
+		pr_dbg("CHRDEV: \"%s\" using major %d\n",
+		       name, major);
 	}
 
 	cd->major = major;
diff --git a/include/linux/bitops.h b/include/linux/bitops.h
index defeaac0745f..73301256b474 100644
--- a/include/linux/bitops.h
+++ b/include/linux/bitops.h
@@ -4,6 +4,7 @@
 
 #ifdef	__KERNEL__
 #define BIT(nr)			(1UL << (nr))
+#define BITS(_start, _end)	((BIT(_end) - BIT(_start)) + BIT(_end))
 #define BIT_ULL(nr)		(1ULL << (nr))
 #define BIT_MASK(nr)		(1UL << ((nr) % BITS_PER_LONG))
 #define BIT_WORD(nr)		((nr) / BITS_PER_LONG)
diff --git a/include/linux/fs.h b/include/linux/fs.h
index 6301ac091e54..1a2046275cdf 100644
--- a/include/linux/fs.h
+++ b/include/linux/fs.h
@@ -2384,8 +2384,6 @@ static inline void bd_unlink_disk_holder(struct block_device *bdev,
 
 /* fs/char_dev.c */
 #define CHRDEV_MAJOR_HASH_SIZE	255
-/* Marks the bottom of the first segment of free char majors */
-#define CHRDEV_MAJOR_DYN_END 234
 extern int alloc_chrdev_region(dev_t *, unsigned, unsigned, const char *);
 extern int register_chrdev_region(dev_t, unsigned, const char *);
 extern int __register_chrdev(unsigned int major, unsigned int baseminor,
-- 
2.4.3

Re: [PATCH 2/2 v2] chrdev: allocate dynamic chardevs in all unused holes

[Linus Torvalds]

On Mon, Feb 22, 2016 at 4:20 AM, Linus Walleij <linus.walleij@linaro.org> wrote:
> This is a duct-tape-and-chewing-gum solution to the problem
> with the major numbers running out when allocating major
> numbers dynamically.

Ok, much less hacky, but now the initialization is fairly unreadable,
even if the comment kind of saves it:

> +/*
> + * A bitmap for the 255 lower device numbers. A "1" means the
> + * major number is taken, a "0" means it is available. We first
> + * need to define all the assigned devices as taken so that
> + * dynamic device allocation will not go in and steal them.
> + */

But then the numbers are really hard to grok, and verify that they
actually match the comments:

> +static u32 majors_map[] = {
> +       /* 8 and 26 are free */
> +       BITS(0, 7) | BITS(9, 25) | BITS(27, 31),

That first one looks "obviously correct", but then:

> +       /* 40 and 60-63 are free */
> +       BITS(0, 7) | BITS(9, 27),
> +       /* 93 and 94 are free */
> +       BITS(0, 28) | BIT(31),

Yeah, it's not exactly obvious that 93/94 modulo 32 is 29/30 etc.

Now, we could fix it two ways:

 - make a BITS32() macro that just masks things by 32 bits, so that
you could write this as

      /* 8 and 26 are free */
      BITS32(0, 7) | BITS32(9, 25) | BITS32(27, 31),
      /* 40 and 60-63 are free */
      BITS32(32, 39) | BITS32(41, 59),
      /* 93 and 94 are free */
      BITS32(64, 92) | BIT32(95),
      ...

which would at least take away *some* of the costs.

Or, quite frankly, just waste memory, and make the array be an array
of buytes, and make it a whole lot more readable. That *could* have
advantages in that it would allow you to differentiate "used
dynamically" from "statically allocated" in the array too, in that you
now have more values than 0/1 to play with. You could also make it
show both the block and char assignments, for example, and use the
same map for both (even if perhaps only used for character devices
initially). Then the initializer could just look like

      #define CHR 1
      #define BLK 2
      #define DYNCHR 0x10  // set when allocated for dynamic char device
     #define DYNBLK 0x20 // set when allocated for dynamic block device

      static unsigned char major_map[] = {
            [0] = CHR|BLK,   // unnamed block devices, no character device
            [1] = CHR|BLK,   // memory devices, ramdisk
            ...

and that would make the source code much bigger, but it would perhaps
be worth it for the legibility and documentation reasons.

I dunno. Maybe I'm worrying about something that isn't worth worrying about.

                    Linus