unified device list allocator
Subsystems (2)
PATCH 1/1 unified device list allocator
(This patch is against -mm1, which has different locking than mainline)
This patch introduces a simple allocator for tracking reservations of block and character device ranges. After poking around, I came to the conclusion that we can't avoid having a separate data structure for reservations vs currently available devices so I tidied up the current scheme. Note that everything below is about allocation/reservation of namespace as opposed to lookup/open of existing devices and thus is only invoked at init/exit and reading /proc/devices.
The new allocator is a simple linked list of dev_t range start and end points. This lets us allocate regions of multiple majors (as is done by SCSI) or just a portion of a major (as is done by several types of character device). Dynamic allocation is handled by passing in a start and end base address.
This unifies a lot of the code for registering block and character. It also does away with the hash tables, which were complicating the code and made allocating more devices than available hash table entries difficult. As these tables are now only used at driver load, unload, and for /proc/devices, and the number of entries is relatively limited, the hash tables are no longer necessary.
If this is acceptable, the next steps are to add the helper functions SCSI needs to allocate its spread of majors in > major chunks, add fallback to the 1023-256 range for dynamic allocation of majors, add change the proc bits to use seq_file. This will let us have dynamic allocation of the entire address space of arbitrary numbers of devices.
Tested on a laptop with a typical mix of static and dynamic block and char devices, with identical allocations to the stock kernel. Save about 3k in code and hash tables.
drivers/block/genhd.c +18 -85
@@ -14,100 +14,46 @@#include <linux/slab.h> #include <linux/kmod.h> #include <linux/kobj_map.h> - -#define MAX_PROBE_HASH 255/* random */ +#include <linux/list.h> +#include <linux/devlist.h> static struct subsystem block_subsys; -static DECLARE_MUTEX (block_subsys_sem); - -/* -* Can be deleted altogether. Later. -* -*/ -static struct blk_major_name { -struct blk_major_name *next; -int major; -char name[16 ]; -} *major_names[MAX_PROBE_HASH ]; - -/* index in the above - for now: assume no multimajor ranges */ -static inline int major_to_index (int major) -{ -return major %MAX_PROBE_HASH ; -} +static LIST_HEAD (blkdev_names);#ifdef CONFIG_PROC_FS -/* get block device names in somewhat random order */ int get_blkdev_list (char *p) { -struct blk_major_name *n; -int i, len; +int len; len =sprintf (p,"\nBlock devices:\n" );down (&block_subsys_sem); -for (i =0 ; i <ARRAY_SIZE (major_names); i++) { -for (n = major_names[i]; n; n = n->next) - len +=sprintf (p+len,"%3d %s\n" , - n->major, n->name); - } + len +=get_dev_list (p, &blkdev_names);up (&block_subsys_sem); -return len; }#endif int register_blkdev (unsigned int major,const char *name) { -struct blk_major_name **n, *p; -int index, ret =0 ; +dev_t r; +int ret;down (&block_subsys_sem); -/* temporary */ -if (major ==0 ) { -for (index =ARRAY_SIZE (major_names)-1 ; index >0 ; index--) { -if (major_names[index] ==NULL ) -break ; - } - -if (index ==0 ) { -printk ("register_blkdev: failed to get major for %s\n" , - name); - ret = -EBUSY ; - goto out; - } - major = index; - ret = major; - } - - p =kmalloc (sizeof (struct blk_major_name ),GFP_KERNEL ); -if (p ==NULL ) { - ret = -ENOMEM ; - goto out; - } - - p->major = major; -strlcpy (p->name, name,sizeof (p->name)); - p->next =NULL ; - index =major_to_index (major); - -for (n = &major_names[index]; *n; n = &(*n)->next) { -if ((*n)->major == major) -break ; - } -if (!*n) - *n = p; -else - ret = -EBUSY ; +if (!major) { + ret =register_dev (MKDEV (1 ,0 ),MKDEV (254 ,0 ), +MKDEV (1 ,0 ), name, &blkdev_names, &r); + ret = ret ? ret :MAJOR (r); + }else + ret =register_dev (MKDEV (major,0 ),MKDEV (major,0 ), +MKDEV (1 ,0 ), name, &blkdev_names,NULL ); -if (ret <0 ) { +if (ret == -EBUSY )printk ("register_blkdev: cannot get major %d for %s\n" , major, name); -kfree (p); - } -out: +up (&block_subsys_sem);return ret; }
@@ -117,24 +63,11 @@ EXPORT_SYMBOL(register_blkdev);/* todo: make void - error printk here */ int unregister_blkdev (unsigned int major,const char *name) { -struct blk_major_name **n; -struct blk_major_name *p =NULL ; -int index =major_to_index (major); -int ret =0 ; +int ret;down (&block_subsys_sem); -for (n = &major_names[index]; *n; n = &(*n)->next) -if ((*n)->major == major) -break ; -if (!*n ||strcmp ((*n)->name, name)) - ret = -EINVAL ; -else { - p = *n; - *n = p->next; - } + ret =unregister_dev (MKDEV (major,0 ), &blkdev_names);up (&block_subsys_sem); -kfree (p); -return ret; }
fs/devlist.c new file +115 -0
115 lines not on this page · raw message
include/linux/devlist.h new file +11 -0
@@ -0,0 +1,11 @@ +#ifndef _LINUX_DEVLIST_H +#define _LINUX_DEVLIST_H + +int register_dev (dev_t a,dev_t b,int size,const char * name, +struct list_head *list,dev_t *r); + +int unregister_dev (dev_t begin,struct list_head *l); + +int get_dev_list (char *p,struct list_head *l); + +#endif
fs/Makefile +1 -0
@@ -10,6 +10,7 @@ obj-y := open.o read_write.o file_table. ioctl.o readdir.o select.o fifo.o locks.o dcache.o inode.o \ attr.o bad_inode.o file.o filesystems.o namespace.o aio.o \ seq_file.o xattr.o libfs.o fs-writeback.o mpage.o direct-io.o \ + devlist.o obj-$(CONFIG_EPOLL) += eventpoll.o obj-$(CONFIG_COMPAT) += compat.o
fs/char_dev.c +52 -171
285 lines not on this page · raw message
Signature · 1 line
Mathematics is the supreme nostalgia of our time.
Review
Quoted 3 lines · Matt Mackall
(quoted diff) +1
-0+ /* search for insertion point in reverse for dynamic allocation */ + list_for_each_prev(l, list) {
hrmph. Any time we do anything in O(n) time, some smarty comes along with a workload which blows us out of the water. Although it's hard to think of any register_blkdev()-intensive workloads.
It's not possible to do this with prio-trees?
Quoted 10 lines · Andrew Morton
Review
Quoted 3 lines · Matt Mackall
(quoted diff) +1
-0+ /* search for insertion point in reverse for dynamic allocation */ + list_for_each_prev(l, list) {hrmph. Any time we do anything in O(n) time, some smarty comes along with a workload which blows us out of the water. Although it's hard to think of any register_blkdev()-intensive workloads.
It's not possible to do this with prio-trees?
Andrew, I think in this particular case you suffer of a sporadic severe condition of overengineeritis.
register_blkdev only happens at module_init time (and in fact should go away completely, so I'm not happy wit hthe surgey to keep it barely alive at all)
Quoted 11 lines · Christoph Hellwig
Quoted 9 lines · Andrew Morton
Review
Quoted 3 lines · Matt Mackall
(quoted diff) +1
-0+ /* search for insertion point in reverse for dynamic allocation */ + list_for_each_prev(l, list) {hrmph. Any time we do anything in O(n) time, some smarty comes along with a workload which blows us out of the water. Although it's hard to think of any register_blkdev()-intensive workloads.
Quoted 4 lines
Quoted 1 line
It's not possible to do this with prio-trees?
Andrew, I think in this particular case you suffer of a sporadic severe condition of overengineeritis.
heh. I like to see our fancy data structures getting used.
Quoted 3 lines
register_blkdevonly happens atmodule_inittime (and in fact should go away completely, so I'm not happy wit hthe surgey to keep it barely alive at all)
Is anyone working on that?
Quoted 5 lines · Andrew Morton
Quoted 3 lines
register_blkdevonly happens atmodule_inittime (and in fact should go away completely, so I'm not happy wit hthe surgey to keep it barely alive at all)Is anyone working on that?
I had a patch from a long time ago that just killed it, but that one isn't useable for current users anymore.
There's two things it's doing currently:
- when called with the major argument as 0 it returns an unused major number from the top of the old 255 entries major list. This should be replaced by a real dynamic dev_t allocator, similar to alloc_chrdev_region.
- /proc/devices. This interface has traditionally been used by things like installer but these day's it's totally bogus as the one major, one driver limitation got lifeted. We'll probably have to deprecate it and kill it in half a year or a similar timespan.
Quoted 7 lines · Christoph Hellwig
Quoted 5 lines · Andrew Morton
Quoted 3 lines
register_blkdevonly happens atmodule_inittime (and in fact should go away completely, so I'm not happy wit hthe surgey to keep it barely alive at all)Is anyone working on that?
Quoted 8 lines
I had a patch from a long time ago that just killed it, but that one isn't useable for current users anymore.
There's two things it's doing currently:
- when called with the major argument as 0 it returns an unused major number from the top of the old 255 entries major list. This should be replaced by a real dynamic
dev_tallocator, similar toalloc_chrdev_region.
Umm, this replaces alloc_chrdev_region too. If instead you mean "let's migrate all the users to a sensible interface", I agree. And that means killing alloc_chrdev_region too. (baseminor makes no sense for dynamic allocation - you either know your prefered major and minor or you know neither.)
Quoted 4 lines
-
/proc/devices. This interface has traditionally been used by things like installer but these day's it's totally bogus as the one major, one driver limitation got lifeted. We'll probably have to deprecate it and kill it in half a year or a similar timespan.
I think killing /proc/devices has to wait until after devfs removal, when everyone is more or less comfortable with its alternatives.
Signature · 1 line
Mathematics is the supreme nostalgia of our time.
Quoted 9 lines · Matt Mackall
Quoted 3 lines
- when called with the major argument as 0 it returns an unused major number from the top of the old 255 entries major list. This should be replaced by a real dynamic
dev_tallocator, similar toalloc_chrdev_region.Umm, this replaces
alloc_chrdev_regiontoo. If instead you mean "let's migrate all the users to a sensible interface", I agree. And that means killingalloc_chrdev_regiontoo. (baseminor makes no sense for dynamic allocation - you either know your prefered major and minor or you know neither.)
The thing is this blkdev_register useage should be replace by an API like alloc_chrdev_region. I don't particularly care about the actual implementation.
Quoted 11 lines · Christoph Hellwig
Quoted 9 lines · Matt Mackall
Quoted 3 lines
- when called with the major argument as 0 it returns an unused major number from the top of the old 255 entries major list. This should be replaced by a real dynamic
dev_tallocator, similar toalloc_chrdev_region.Umm, this replaces
alloc_chrdev_regiontoo. If instead you mean "let's migrate all the users to a sensible interface", I agree. And that means killingalloc_chrdev_regiontoo. (baseminor makes no sense for dynamic allocation - you either know your prefered major and minor or you know neither.)
Quoted 3 lines
The thing is this
blkdev_registeruseage should be replace by an API likealloc_chrdev_region. I don't particularly care about the actual implementation.
Ok, I can work on a follow-up that does that.
Signature · 1 line
Mathematics is the supreme nostalgia of our time.
Quoted 10 lines · Andrew Morton
Review
Quoted 3 lines · Matt Mackall
(quoted diff) +1
-0+ /* search for insertion point in reverse for dynamic allocation */ + list_for_each_prev(l, list) {hrmph. Any time we do anything in O(n) time, some smarty comes along with a workload which blows us out of the water. Although it's hard to think of any register_blkdev()-intensive workloads.
It's not possible to do this with prio-trees?
I thought about using rbtrees. But I decided it was overkill. Beyond the 4k limit of the current proc code, currently that's limited to ~256 entries per block/char and will be limited to about ~1024 each for the foreseeable future. It's only walked on driver init/exit and when catting said proc file (where O(n) is unavoidable). In other words, worst case we're talking less than a millisecond at boot/shutdown.
Signature · 1 line
Mathematics is the supreme nostalgia of our time.