[PATCH] 1/1: Device-Mapper: Remove 1024 devices limitation

[PATCH] 1/1: Device-Mapper: Remove 1024 devices limitation

[Kevin Corry]

Remove the limitation of 1024 DM devices.

Signed-off-by: Kevin Corry <kevcorry@us.ibm.com>

--- diff/drivers/md/dm.c	2004-06-30 08:45:34.512303600 -0500
+++ source/drivers/md/dm.c	2004-06-30 08:48:42.085788096 -0500
@@ -17,11 +17,13 @@
 #include <linux/slab.h>
 
 static const char *_name = DM_NAME;
-#define MAX_DEVICES 1024
 
 static unsigned int major = 0;
 static unsigned int _major = 0;
 
+static int realloc_minor_bits(unsigned long requested_minor);
+static void free_minor_bits(void);
+
 /*
  * One of these is allocated per bio.
  */
@@ -111,11 +113,19 @@
 		return -ENOMEM;
 	}
 
+	r = realloc_minor_bits(1024);
+	if (r < 0) {
+		kmem_cache_destroy(_tio_cache);
+		kmem_cache_destroy(_io_cache);
+		return r;
+	}
+
 	_major = major;
 	r = register_blkdev(_major, _name);
 	if (r < 0) {
 		kmem_cache_destroy(_tio_cache);
 		kmem_cache_destroy(_io_cache);
+		free_minor_bits();
 		return r;
 	}
 
@@ -129,6 +139,7 @@
 {
 	kmem_cache_destroy(_tio_cache);
 	kmem_cache_destroy(_io_cache);
+	free_minor_bits();
 
 	if (unregister_blkdev(_major, _name) < 0)
 		DMERR("devfs_unregister_blkdev failed");
@@ -615,14 +626,58 @@
 /*-----------------------------------------------------------------
  * A bitset is used to keep track of allocated minor numbers.
  *---------------------------------------------------------------*/
-static spinlock_t _minor_lock = SPIN_LOCK_UNLOCKED;
-static unsigned long _minor_bits[MAX_DEVICES / BITS_PER_LONG];
+static DECLARE_MUTEX(_minor_lock);
+static unsigned long *_minor_bits = NULL;
+static unsigned long _max_minors = 0;
+
+#define MINORS_SIZE(minors) ((minors / BITS_PER_LONG) * sizeof(unsigned long))
+
+static int realloc_minor_bits(unsigned long requested_minor)
+{
+	unsigned long max_minors;
+	unsigned long *minor_bits, *tmp;
+
+	if (requested_minor < _max_minors)
+		return -EINVAL;
+
+	/* Round up the requested minor to the next power-of-2. */
+	max_minors = 1 << fls(requested_minor - 1);
+	if (max_minors > (1 << MINORBITS))
+		return -EINVAL;
+
+	minor_bits = kmalloc(MINORS_SIZE(max_minors), GFP_KERNEL);
+	if (!minor_bits)
+		return -ENOMEM;
+	memset(minor_bits, 0, MINORS_SIZE(max_minors));
+
+	/* Copy the existing bit-set to the new one. */
+	if (_minor_bits)
+		memcpy(minor_bits, _minor_bits, MINORS_SIZE(_max_minors));
+
+	tmp = _minor_bits;
+	_minor_bits = minor_bits;
+	_max_minors = max_minors;
+	if (tmp)
+		kfree(tmp);
+
+	return 0;
+}
+
+static void free_minor_bits(void)
+{
+	down(&_minor_lock);
+	kfree(_minor_bits);
+	_minor_bits = NULL;
+	_max_minors = 0;
+	up(&_minor_lock);
+}
 
 static void free_minor(unsigned int minor)
 {
-	spin_lock(&_minor_lock);
-	clear_bit(minor, _minor_bits);
-	spin_unlock(&_minor_lock);
+	down(&_minor_lock);
+	if (minor < _max_minors)
+		clear_bit(minor, _minor_bits);
+	up(&_minor_lock);
 }
 
 /*
@@ -630,37 +685,48 @@
  */
 static int specific_minor(unsigned int minor)
 {
-	int r = -EBUSY;
+	int r = 0;
 
-	if (minor >= MAX_DEVICES) {
-		DMWARN("request for a mapped_device beyond MAX_DEVICES (%d)",
-		       MAX_DEVICES);
+	if (minor > (1 << MINORBITS))
 		return -EINVAL;
+
+	down(&_minor_lock);
+	if (minor >= _max_minors) {
+		r = realloc_minor_bits(minor);
+		if (r) {
+			up(&_minor_lock);
+			return r;
+		}
 	}
 
-	spin_lock(&_minor_lock);
-	if (!test_and_set_bit(minor, _minor_bits))
-		r = 0;
-	spin_unlock(&_minor_lock);
+	if (test_and_set_bit(minor, _minor_bits))
+		r = -EBUSY;
+	up(&_minor_lock);
 
 	return r;
 }
 
 static int next_free_minor(unsigned int *minor)
 {
-	int r = -EBUSY;
+	int r;
 	unsigned int m;
 
-	spin_lock(&_minor_lock);
-	m = find_first_zero_bit(_minor_bits, MAX_DEVICES);
-	if (m != MAX_DEVICES) {
-		set_bit(m, _minor_bits);
-		*minor = m;
-		r = 0;
+	down(&_minor_lock);
+	m = find_first_zero_bit(_minor_bits, _max_minors);
+	if (m >= _max_minors) {
+		r = realloc_minor_bits(_max_minors * 2);
+		if (r) {
+			up(&_minor_lock);
+			return r;
+		}
+		m = find_first_zero_bit(_minor_bits, _max_minors);
 	}
-	spin_unlock(&_minor_lock);
 
-	return r;
+	set_bit(m, _minor_bits);
+	*minor = m;
+	up(&_minor_lock);
+
+	return 0;
 }
 
 static struct block_device_operations dm_blk_dops;

Re: [PATCH] 1/1: Device-Mapper: Remove 1024 devices limitation

[Andrew Morton]

Kevin Corry <kevcorry@us.ibm.com> wrote:
>
> Remove the limitation of 1024 DM devices.

That seems to be an awful lot of fuss just to maintain a bitmap.

What is a realistic useful upper bound on the minors?  Would it not be sufficient
to increase the size of the statically allocated bitmap?

Did you consider going to a different data structure altogether?  lib/radix-tree.c and
lib/idr.c provide appropriate ones.

Re: [PATCH] 1/1: Device-Mapper: Remove 1024 devices limitation

[Kevin Corry]

On Thursday 01 July 2004 16:38, Andrew Morton wrote:
> Kevin Corry <kevcorry@us.ibm.com> wrote:
> > Remove the limitation of 1024 DM devices.
>
> That seems to be an awful lot of fuss just to maintain a bitmap.

Mmm...perhaps.

> What is a realistic useful upper bound on the minors?  Would it not be
> sufficient to increase the size of the statically allocated bitmap?

I guess that depends on who you ask. Obviously, for most people the previous 
limit of 1024 devices is more than enough. But there's always going to be 
folks pushing the limits. So I figured I'd go ahead and rewrite it to 
theoretically allow for the maximum range of minor numbers, while trying not 
to waste memory for the common case.

> Did you consider going to a different data structure altogether? 
> lib/radix-tree.c and lib/idr.c provide appropriate ones.

The idr stuff looks promising at first glance. I'll take a better look at it 
tomorrow and see if we can switch from a bit-set to one of these data 
structures.

-- 
Kevin Corry
kevcorry@us.ibm.com
http://evms.sourceforge.net

Re: [PATCH] 1/1: Device-Mapper: Remove 1024 devices limitation

[Andrew Morton]

Kevin Corry <kevcorry@us.ibm.com> wrote:
>
> > Did you consider going to a different data structure altogether? 
>  > lib/radix-tree.c and lib/idr.c provide appropriate ones.
> 
>  The idr stuff looks promising at first glance. I'll take a better look at it 
>  tomorrow and see if we can switch from a bit-set to one of these data 
>  structures.

Yes, idr is the one to use.  That linear search you have in there becomes
logarithmic.  Will speed up the registration of 100,000 minors no end ;)

Re: [PATCH] 1/1: Device-Mapper: Remove 1024 devices limitation

[Kevin Corry]

On Thursday 01 July 2004 10:30 pm, Andrew Morton wrote:
> Kevin Corry <kevcorry@us.ibm.com> wrote:
> > > Did you consider going to a different data structure altogether?
> > >
> >  > lib/radix-tree.c and lib/idr.c provide appropriate ones.
> >
> >  The idr stuff looks promising at first glance. I'll take a better look
> > at it tomorrow and see if we can switch from a bit-set to one of these
> > data structures.
>
> Yes, idr is the one to use.  That linear search you have in there becomes
> logarithmic.  Will speed up the registration of 100,000 minors no end ;)

I've got a patch that switches from a bit-set to an IDR structure. The only
thing I'm slightly uncertain about is the case where we're trying to create
a device with a specific minor number (when creating a DM device, you have
the choice to specify a minor number or have DM find the first available
one). To do this, I call idr_find() with the desired minor. If that returns
NULL (meaning it's not already in use), then I call idr_get_new_above() with
that same desired minor. In the cases I've tested, this always chooses the
desired minor, but can we depend on that behavior? For now I've got a check
to make sure the idr_get_new_above() call returned the correct value, but if
we can't be certain that this value will be correct in at least the vast
majority of the cases, we might want to find an alternate approach.

Here's the proposed patch. This is in addition to yesterday's, since Linus
has already picked that one up in his tree. It completely removes the
realloc_minor_bits() and free_minor_bits() routines, and modifies
free_minor(), specific_minor() and next_free_minor() to use the IDR
instead of the bit-set.

-- 
Kevin Corry
kevcorry@us.ibm.com
http://evms.sourceforge.net/


Keep track of allocated minor numbers with an IDR instead of a bit-set.

Signed-off-by: Kevin Corry <kevcorry@us.ibm.com>

--- diff/drivers/md/dm.c	2004-07-02 11:48:26.402266784 -0500
+++ source/drivers/md/dm.c	2004-07-02 12:14:12.000000000 -0500
@@ -15,15 +15,13 @@
 #include <linux/buffer_head.h>
 #include <linux/mempool.h>
 #include <linux/slab.h>
+#include <linux/idr.h>
 
 static const char *_name = DM_NAME;
 
 static unsigned int major = 0;
 static unsigned int _major = 0;
 
-static int realloc_minor_bits(unsigned long requested_minor);
-static void free_minor_bits(void);
-
 /*
  * One of these is allocated per bio.
  */
@@ -113,19 +111,11 @@
 		return -ENOMEM;
 	}
 
-	r = realloc_minor_bits(1024);
-	if (r < 0) {
-		kmem_cache_destroy(_tio_cache);
-		kmem_cache_destroy(_io_cache);
-		return r;
-	}
-
 	_major = major;
 	r = register_blkdev(_major, _name);
 	if (r < 0) {
 		kmem_cache_destroy(_tio_cache);
 		kmem_cache_destroy(_io_cache);
-		free_minor_bits();
 		return r;
 	}
 
@@ -139,7 +129,6 @@
 {
 	kmem_cache_destroy(_tio_cache);
 	kmem_cache_destroy(_io_cache);
-	free_minor_bits();
 
 	if (unregister_blkdev(_major, _name) < 0)
 		DMERR("devfs_unregister_blkdev failed");
@@ -624,59 +613,15 @@
 }
 
 /*-----------------------------------------------------------------
- * A bitset is used to keep track of allocated minor numbers.
+ * An IDR is used to keep track of allocated minor numbers.
  *---------------------------------------------------------------*/
 static DECLARE_MUTEX(_minor_lock);
-static unsigned long *_minor_bits = NULL;
-static unsigned long _max_minors = 0;
-
-#define MINORS_SIZE(minors) ((minors / BITS_PER_LONG) * sizeof(unsigned long))
-
-static int realloc_minor_bits(unsigned long requested_minor)
-{
-	unsigned long max_minors;
-	unsigned long *minor_bits, *tmp;
-
-	if (requested_minor < _max_minors)
-		return -EINVAL;
-
-	/* Round up the requested minor to the next power-of-2. */
-	max_minors = 1 << fls(requested_minor - 1);
-	if (max_minors > (1 << MINORBITS))
-		return -EINVAL;
-
-	minor_bits = kmalloc(MINORS_SIZE(max_minors), GFP_KERNEL);
-	if (!minor_bits)
-		return -ENOMEM;
-	memset(minor_bits, 0, MINORS_SIZE(max_minors));
-
-	/* Copy the existing bit-set to the new one. */
-	if (_minor_bits)
-		memcpy(minor_bits, _minor_bits, MINORS_SIZE(_max_minors));
-
-	tmp = _minor_bits;
-	_minor_bits = minor_bits;
-	_max_minors = max_minors;
-	if (tmp)
-		kfree(tmp);
-
-	return 0;
-}
-
-static void free_minor_bits(void)
-{
-	down(&_minor_lock);
-	kfree(_minor_bits);
-	_minor_bits = NULL;
-	_max_minors = 0;
-	up(&_minor_lock);
-}
+static DEFINE_IDR(_minor_idr);
 
 static void free_minor(unsigned int minor)
 {
 	down(&_minor_lock);
-	if (minor < _max_minors)
-		clear_bit(minor, _minor_bits);
+	idr_remove(&_minor_idr, minor);
 	up(&_minor_lock);
 }
 
@@ -685,24 +630,37 @@
  */
 static int specific_minor(unsigned int minor)
 {
-	int r = 0;
+	int r, m;
 
 	if (minor > (1 << MINORBITS))
 		return -EINVAL;
 
 	down(&_minor_lock);
-	if (minor >= _max_minors) {
-		r = realloc_minor_bits(minor);
-		if (r) {
-			up(&_minor_lock);
-			return r;
-		}
+
+	if (idr_find(&_minor_idr, minor)) {
+		r = -EBUSY;
+		goto out;
 	}
 
-	if (test_and_set_bit(minor, _minor_bits))
+	r = idr_pre_get(&_minor_idr, GFP_KERNEL);
+	if (!r) {
+		r = -ENOMEM;
+		goto out;
+	}
+
+	r = idr_get_new_above(&_minor_idr, specific_minor, minor, &m);
+	if (r) {
+		goto out;
+	}
+
+	if (m != minor) {
+		idr_remove(&_minor_idr, m);
 		r = -EBUSY;
-	up(&_minor_lock);
+		goto out;
+	}
 
+out:
+	up(&_minor_lock);
 	return r;
 }
 
@@ -712,21 +670,29 @@
 	unsigned int m;
 
 	down(&_minor_lock);
-	m = find_first_zero_bit(_minor_bits, _max_minors);
-	if (m >= _max_minors) {
-		r = realloc_minor_bits(_max_minors * 2);
-		if (r) {
-			up(&_minor_lock);
-			return r;
-		}
-		m = find_first_zero_bit(_minor_bits, _max_minors);
+
+	r = idr_pre_get(&_minor_idr, GFP_KERNEL);
+	if (!r) {
+		r = -ENOMEM;
+		goto out;
+	}
+
+	r = idr_get_new(&_minor_idr, next_free_minor, &m);
+	if (r) {
+		goto out;
+	}
+
+	if (m > (1 << MINORBITS)) {
+		idr_remove(&_minor_idr, m);
+		r = -ENOSPC;
+		goto out;
 	}
 
-	set_bit(m, _minor_bits);
 	*minor = m;
-	up(&_minor_lock);
 
-	return 0;
+out:
+	up(&_minor_lock);
+	return r;
 }
 
 static struct block_device_operations dm_blk_dops;

Re: [PATCH] 1/1: Device-Mapper: Remove 1024 devices limitation

[Andrew Morton]

Kevin Corry <kevcorry@us.ibm.com> wrote:
>
> > Yes, idr is the one to use.  That linear search you have in there becomes
>  > logarithmic.  Will speed up the registration of 100,000 minors no end ;)
> 
>  I've got a patch that switches from a bit-set to an IDR structure. The only
>  thing I'm slightly uncertain about is the case where we're trying to create
>  a device with a specific minor number (when creating a DM device, you have
>  the choice to specify a minor number or have DM find the first available
>  one). To do this, I call idr_find() with the desired minor. If that returns
>  NULL (meaning it's not already in use), then I call idr_get_new_above() with
>  that same desired minor. In the cases I've tested, this always chooses the
>  desired minor, but can we depend on that behavior?

Yes, that has to work - you're holding the lock throughout.

It would be sensible to make that a part of the idr API though.  

Re: [PATCH] 1/1: Device-Mapper: Remove 1024 devices limitation

[Kevin Corry]

On Friday 02 July 2004 2:42 pm, Andrew Morton wrote:
> Kevin Corry <kevcorry@us.ibm.com> wrote:
> > > Yes, idr is the one to use.  That linear search you have in there
> > > becomes
> > >
> >  > logarithmic.  Will speed up the registration of 100,000 minors no end
> >  > ;)
> >
> >  I've got a patch that switches from a bit-set to an IDR structure. The
> > only thing I'm slightly uncertain about is the case where we're trying to
> > create a device with a specific minor number (when creating a DM device,
> > you have the choice to specify a minor number or have DM find the first
> > available one). To do this, I call idr_find() with the desired minor. If
> > that returns NULL (meaning it's not already in use), then I call
> > idr_get_new_above() with that same desired minor. In the cases I've
> > tested, this always chooses the desired minor, but can we depend on that
> > behavior?
>
> Yes, that has to work - you're holding the lock throughout.
>
> It would be sensible to make that a part of the idr API though.

After talking with Alasdair a bit, there might be one bug in the "dm-use-idr"
patch I submitted before. It seems (based on some comments in lib/idr.c) that
the idr_find() routine might not return NULL if the desired ID value is not
in the tree. However, my previous patch assumed it would. So, if that is in
fact the behavior of idr_find(), we'll need to replace my previous
"dm-use-idr" patch (now in -mm6) with this one. It now allocates a integer
before calling idr_get_new() or idr_get_new_above() so it can pass a unique
pointer to associate with each ID. After the idr_get_ call it stores the ID
into that allocated integer so it can verify that the correct pointer is
returned from calls to idr_find().

(If you'd rather have an incremental patch from the previous version, just
let me know.)

-- 
Kevin Corry
kevcorry@us.ibm.com
http://evms.sourceforge.net/



Keep track of allocated minor numbers with an IDR instead of a bit-set.

Signed-off-by: Kevin Corry <kevcorry@us.ibm.com>

--- diff/drivers/md/dm.c	2004-07-02 11:40:41.000000000 -0500
+++ source/drivers/md/dm.c	2004-07-06 11:59:34.738796728 -0500
@@ -15,15 +15,13 @@
 #include <linux/buffer_head.h>
 #include <linux/mempool.h>
 #include <linux/slab.h>
+#include <linux/idr.h>
 
 static const char *_name = DM_NAME;
 
 static unsigned int major = 0;
 static unsigned int _major = 0;
 
-static int realloc_minor_bits(unsigned long requested_minor);
-static void free_minor_bits(void);
-
 /*
  * One of these is allocated per bio.
  */
@@ -113,19 +111,11 @@
 		return -ENOMEM;
 	}
 
-	r = realloc_minor_bits(1024);
-	if (r < 0) {
-		kmem_cache_destroy(_tio_cache);
-		kmem_cache_destroy(_io_cache);
-		return r;
-	}
-
 	_major = major;
 	r = register_blkdev(_major, _name);
 	if (r < 0) {
 		kmem_cache_destroy(_tio_cache);
 		kmem_cache_destroy(_io_cache);
-		free_minor_bits();
 		return r;
 	}
 
@@ -139,7 +129,6 @@
 {
 	kmem_cache_destroy(_tio_cache);
 	kmem_cache_destroy(_io_cache);
-	free_minor_bits();
 
 	if (unregister_blkdev(_major, _name) < 0)
 		DMERR("devfs_unregister_blkdev failed");
@@ -624,59 +613,23 @@
 }
 
 /*-----------------------------------------------------------------
- * A bitset is used to keep track of allocated minor numbers.
+ * An IDR is used to keep track of allocated minor numbers.
  *---------------------------------------------------------------*/
 static DECLARE_MUTEX(_minor_lock);
-static unsigned long *_minor_bits = NULL;
-static unsigned long _max_minors = 0;
+static DEFINE_IDR(_minor_idr);
 
-#define MINORS_SIZE(minors) ((minors / BITS_PER_LONG) * sizeof(unsigned long))
-
-static int realloc_minor_bits(unsigned long requested_minor)
+static void free_minor(unsigned int minor)
 {
-	unsigned long max_minors;
-	unsigned long *minor_bits, *tmp;
-
-	if (requested_minor < _max_minors)
-		return -EINVAL;
-
-	/* Round up the requested minor to the next power-of-2. */
-	max_minors = 1 << fls(requested_minor - 1);
-	if (max_minors > (1 << MINORBITS))
-		return -EINVAL;
-
-	minor_bits = kmalloc(MINORS_SIZE(max_minors), GFP_KERNEL);
-	if (!minor_bits)
-		return -ENOMEM;
-	memset(minor_bits, 0, MINORS_SIZE(max_minors));
-
-	/* Copy the existing bit-set to the new one. */
-	if (_minor_bits)
-		memcpy(minor_bits, _minor_bits, MINORS_SIZE(_max_minors));
-
-	tmp = _minor_bits;
-	_minor_bits = minor_bits;
-	_max_minors = max_minors;
-	if (tmp)
-		kfree(tmp);
+	unsigned int *m;
 
-	return 0;
-}
-
-static void free_minor_bits(void)
-{
 	down(&_minor_lock);
-	kfree(_minor_bits);
-	_minor_bits = NULL;
-	_max_minors = 0;
-	up(&_minor_lock);
-}
 
-static void free_minor(unsigned int minor)
-{
-	down(&_minor_lock);
-	if (minor < _max_minors)
-		clear_bit(minor, _minor_bits);
+	m = idr_find(&_minor_idr, minor);
+	if (m && *m == minor) {
+		idr_remove(&_minor_idr, minor);
+		kfree(m);
+	}
+
 	up(&_minor_lock);
 }
 
@@ -685,48 +638,95 @@
  */
 static int specific_minor(unsigned int minor)
 {
-	int r = 0;
+	unsigned int m, *p;
+	int r;
 
-	if (minor > (1 << MINORBITS))
+	if (minor >= (1 << MINORBITS))
 		return -EINVAL;
 
 	down(&_minor_lock);
-	if (minor >= _max_minors) {
-		r = realloc_minor_bits(minor);
-		if (r) {
-			up(&_minor_lock);
-			return r;
-		}
+
+	/* Make sure this minor isn't already in use. */
+	p = idr_find(&_minor_idr, minor);
+	if (p && *p == minor) {
+		r = -EBUSY;
+		goto out;
+	}
+
+	r = idr_pre_get(&_minor_idr, GFP_KERNEL);
+	if (!r) {
+		r = -ENOMEM;
+		goto out;
+	}
+
+	/* Allocate an int to store the minor number in. */
+	p = kmalloc(sizeof(*p), GFP_KERNEL);
+	if (!p) {
+		r = - ENOMEM;
+		goto out;
+	}
+
+	/* Since the desired minor isn't in the IDR, this should get that
+	 * specific minor. But, check the returned ID just to be safe.
+	 */
+	r = idr_get_new_above(&_minor_idr, p, minor, &m);
+	if (r) {
+		kfree(p);
+		goto out;
 	}
 
-	if (test_and_set_bit(minor, _minor_bits))
+	if (m != minor) {
+		idr_remove(&_minor_idr, m);
+		kfree(p);
 		r = -EBUSY;
-	up(&_minor_lock);
+		goto out;
+	}
+
+	*p = minor;
 
+out:
+	up(&_minor_lock);
 	return r;
 }
 
 static int next_free_minor(unsigned int *minor)
 {
 	int r;
-	unsigned int m;
+	unsigned int m, *p;
 
 	down(&_minor_lock);
-	m = find_first_zero_bit(_minor_bits, _max_minors);
-	if (m >= _max_minors) {
-		r = realloc_minor_bits(_max_minors * 2);
-		if (r) {
-			up(&_minor_lock);
-			return r;
-		}
-		m = find_first_zero_bit(_minor_bits, _max_minors);
+
+	r = idr_pre_get(&_minor_idr, GFP_KERNEL);
+	if (!r) {
+		r = -ENOMEM;
+		goto out;
 	}
 
-	set_bit(m, _minor_bits);
-	*minor = m;
-	up(&_minor_lock);
+	/* Allocate an int to store the minor number in. */
+	p = kmalloc(sizeof(*p), GFP_KERNEL);
+	if (!p) {
+		r = - ENOMEM;
+		goto out;
+	}
 
-	return 0;
+	r = idr_get_new(&_minor_idr, p, &m);
+	if (r) {
+		kfree(p);
+		goto out;
+	}
+
+	if (m >= (1 << MINORBITS)) {
+		idr_remove(&_minor_idr, m);
+		kfree(p);
+		r = -ENOSPC;
+		goto out;
+	}
+
+	*minor = *p = m;
+
+out:
+	up(&_minor_lock);
+	return r;
 }
 
 static struct block_device_operations dm_blk_dops;

Re: [PATCH] 1/1: Device-Mapper: Remove 1024 devices limitation

[Andrew Morton]

Kevin Corry <kevcorry@us.ibm.com> wrote:
>
> After talking with Alasdair a bit, there might be one bug in the "dm-use-idr"
> patch I submitted before. It seems (based on some comments in lib/idr.c) that
> the idr_find() routine might not return NULL if the desired ID value is not
> in the tree.


Confused.  idr_find() returns the thing it found, or NULL.  To which
comments do you refer?

Re: [PATCH] 1/1: Device-Mapper: Remove 1024 devices limitation

[Alasdair G Kergon]

On Tue, Jul 06, 2004 at 02:23:35PM -0700, Andrew Morton wrote:
> Kevin Corry <kevcorry@us.ibm.com> wrote:

> > It seems (based on some comments in lib/idr.c) that
 
> Confused.  idr_find() returns the thing it found, or NULL.  

Yes, but the comments imply that the thing it found might in some
circumstances not be the thing you asked it to look for (if there've 
been deletions) and it's the caller's responsibility to verify
what's returned.

> To which comments do you refer?

lib/idr.c:30

 * What you need to do is, since we don't keep the counter as part of
 * id / ptr pair, to keep a copy of it in the pointed to structure
 * (or else where) so that when you ask for a ptr you can varify that
 * the returned ptr is correct by comparing the id it contains with the one
 * you asked for.  In other words, we only did half the reuse protection.
 * Since the code depends on your code doing this check, we ignore high
 * order bits in the id, not just the count, but bits that would, if used,
 * index outside of the allocated ids.  In other words, if the largest id
 * currently allocated is 32 a look up will only look at the low 5 bits of
 * the id.  Since you will want to keep this id in the structure anyway
 * (if for no other reason than to be able to eliminate the id when the
 * structure is found in some other way) this seems reasonable.  If you
 * really think otherwise, the code to check these bits here, it is just
 * disabled with a #if 0.

Alasdair
-- 
agk@redhat.com

Re: [PATCH] 1/1: Device-Mapper: Remove 1024 devices limitation

[Alasdair G Kergon]

On Tue, Jul 06, 2004 at 10:35:52PM +0100, Alasdair G Kergon wrote:
> Yes, but the comments imply that the thing it found might in some
> circumstances not be the thing you asked it to look for 

To clarify, we make two sorts of requests for ids [minor numbers]:
  (a) What is the lowest unused id number?
  (b) Is id number N used or not?

If I interpret things correctly, in case (b) if N is larger than the
the highest id number currently stored it might still return non-NULL 
(if lower order bits match lower order bits of a different stored id).

[Would it be sufficient for the caller to keep track of the highest 
allocated ID and check before calling, or is the masking sometimes
stronger than that?]

Alasdair
-- 
agk@redhat.com

Re: [PATCH] 1/1: Device-Mapper: Remove 1024 devices limitation

[Jim Houston]

[-- Attachment #1: Type: text/plain, Size: 1073 bytes --]

On Tue, 2004-07-06 at 17:23, Andrew Morton wrote:
> Kevin Corry <kevcorry@us.ibm.com> wrote:
> >
> > After talking with Alasdair a bit, there might be one bug in the "dm-use-idr"
> > patch I submitted before. It seems (based on some comments in lib/idr.c) that
> > the idr_find() routine might not return NULL if the desired ID value is not
> > in the tree.
> 
> 
> Confused.  idr_find() returns the thing it found, or NULL.  To which
> comments do you refer?

Hi Andrew, Kevin,

Kevin is correct.  It's more of the nonsense related to having a counter
in the upper bits of the id.  If you call idr_find with an id that is
beyond the currently allocated space it ignores the upper bits and
returns one of the entries that is in the allocated space.  This
aliasing is most annoying.

I'm attaching an untested patch which removes the counter in the upper
bits of the id and makes idr_find return NULL if the requested id is
beyond the allocated space.  I suspect that there are problems with
id values which are less than zero.

Jim Houston - Concurrent Computer Corp.






[-- Attachment #2: idr_remove_counter.patch --]
[-- Type: text/plain, Size: 3824 bytes --]

--- lib/idr.c.orig	2004-07-06 15:19:34.301383300 -0400
+++ lib/idr.c	2004-07-06 17:41:55.749885756 -0400
@@ -28,29 +28,7 @@
  * with the slab allocator.
 
  * A word on reuse.  We reuse empty id slots as soon as we can, always
- * using the lowest one available.  But we also merge a counter in the
- * high bits of the id.  The counter is RESERVED_ID_BITS (8 at this time)
- * long.  This means that if you allocate and release the same id in a 
- * loop we will reuse an id after about 256 times around the loop.  The
- * word about is used here as we will NOT return a valid id of -1 so if
- * you loop on the largest possible id (and that is 24 bits, wow!) we
- * will kick the counter to avoid -1.  (Paranoid?  You bet!)
- *
- * What you need to do is, since we don't keep the counter as part of
- * id / ptr pair, to keep a copy of it in the pointed to structure
- * (or else where) so that when you ask for a ptr you can varify that
- * the returned ptr is correct by comparing the id it contains with the one
- * you asked for.  In other words, we only did half the reuse protection.
- * Since the code depends on your code doing this check, we ignore high
- * order bits in the id, not just the count, but bits that would, if used,
- * index outside of the allocated ids.  In other words, if the largest id
- * currently allocated is 32 a look up will only look at the low 5 bits of
- * the id.  Since you will want to keep this id in the structure anyway
- * (if for no other reason than to be able to eliminate the id when the
- * structure is found in some other way) this seems reasonable.  If you
- * really think otherwise, the code to check these bits here, it is just
- * disabled with a #if 0.
-
+ * using the lowest one available.
 
  * So here are the complete details:
 
@@ -79,6 +57,12 @@
  *   unlock and go back to the idr_pre_get() call.  ptr is the pointer
  *   you want associated with the id.  In other words:
 
+ * int idr_get_new_above(struct idr *idp, void *ptr, int starting_id)
+
+ *   The same as above but you can specify a prefered id value.  If the
+ *   starting_id value is available it will be allocated.  If it is
+ *   already the next id greater than starting_id will be allocated.
+
  * void *idr_find(struct idr *idp, int id);
  
  *   returns the "ptr", given the id.  A NULL return indicates that the
@@ -181,8 +165,6 @@
 			sh = IDR_BITS*l;
 			id = ((id >> sh) ^ n ^ m) << sh;
 		}
-		if (id >= MAX_ID_BIT)
-			return -1;
 		if (l == 0)
 			break;
 		/*
@@ -266,12 +248,6 @@
 	v = sub_alloc(idp, ptr, &id);
 	if (v == -2)
 		goto build_up;
-	if ( likely(v >= 0 )) {
-		idp->count++;
-		v += (idp->count << MAX_ID_SHIFT);
-		if ( unlikely( v == -1 ))
-		     v += (1L << MAX_ID_SHIFT);
-	}
 	return(v);
 }
 EXPORT_SYMBOL(idr_get_new_above);
@@ -342,14 +318,8 @@
 
 	n = idp->layers * IDR_BITS;
 	p = idp->top;
-#if 0
-	/*
-	 * This tests to see if bits outside the current tree are
-	 * present.  If so, tain't one of ours!
-	 */
-	if ( unlikely( (id & ~(~0 << MAX_ID_SHIFT)) >> (n + IDR_BITS)))
-	     return NULL;
-#endif
+	if (id >= (1 << n))
+		return NULL;
 	while (n > 0 && p) {
 		n -= IDR_BITS;
 		p = p->ary[(id >> n) & IDR_MASK];
--- include/linux/idr.h.orig	2004-07-06 18:04:07.388445924 -0400
+++ include/linux/idr.h	2004-07-06 18:01:24.355230740 -0400
@@ -29,12 +29,8 @@
 /* Define the size of the id's */
 #define BITS_PER_INT (sizeof(int)*8)
 
-#define MAX_ID_SHIFT (BITS_PER_INT - RESERVED_ID_BITS)
-#define MAX_ID_BIT (1 << MAX_ID_SHIFT)
-#define MAX_ID_MASK (MAX_ID_BIT - 1)
-
 /* Leave the possibility of an incomplete final layer */
-#define MAX_LEVEL (MAX_ID_SHIFT + IDR_BITS - 1) / IDR_BITS
+#define MAX_LEVEL (BITS_PER_INT + IDR_BITS - 1) / IDR_BITS
 
 /* Number of id_layer structs to leave in free list */
 #define IDR_FREE_MAX MAX_LEVEL + MAX_LEVEL

Re: [PATCH] 1/1: Device-Mapper: Remove 1024 devices limitation

[Andrew Morton]

Alasdair G Kergon <agk@redhat.com> wrote:
>
> > Confused.  idr_find() returns the thing it found, or NULL.  
> 
> Yes, but the comments imply that the thing it found might in some
> circumstances not be the thing you asked it to look for (if there've 
> been deletions) and it's the caller's responsibility to verify
> what's returned.

ah, OK.  The original idr.c code had a (weird) feature in which each time
you add a new element, idr_add_new() returns a generation counter in the
top bits of the returned index.  So when doing a lookup the idr code would
mask the counter bits off the index before using it.

This was so that if someone did a quick add/remove/add, the second `add'
would return the same index, with a different counter in te top eight bits.

When you do another lookup you can compare the counter which you imbedded
in the object with the counter in the index which you used for the lookup. 
If they're different, you know that someone has deleted the object you were
looking for.

It was, IMO, sorry, a complete crock and was all thrown away a month or so
ago.

> > To which comments do you refer?
> 
> lib/idr.c:30
> 
>  * What you need to do is, since we don't keep the counter as part of
>  * id / ptr pair, to keep a copy of it in the pointed to structure
>  * (or else where) so that when you ask for a ptr you can varify that
>  * the returned ptr is correct by comparing the id it contains with the one
>  * you asked for.  In other words, we only did half the reuse protection.
>  * Since the code depends on your code doing this check, we ignore high
>  * order bits in the id, not just the count, but bits that would, if used,
>  * index outside of the allocated ids.  In other words, if the largest id
>  * currently allocated is 32 a look up will only look at the low 5 bits of
>  * the id.  Since you will want to keep this id in the structure anyway
>  * (if for no other reason than to be able to eliminate the id when the
>  * structure is found in some other way) this seems reasonable.  If you
>  * really think otherwise, the code to check these bits here, it is just
>  * disabled with a #if 0.

The comment is stale - I'll remove it.

Re: [PATCH] 1/1: Device-Mapper: Remove 1024 devices limitation

[Andrew Morton]

Jim Houston <jim.houston@comcast.net> wrote:
>
> On Tue, 2004-07-06 at 17:23, Andrew Morton wrote:
> > Kevin Corry <kevcorry@us.ibm.com> wrote:
> > >
> > > After talking with Alasdair a bit, there might be one bug in the "dm-use-idr"
> > > patch I submitted before. It seems (based on some comments in lib/idr.c) that
> > > the idr_find() routine might not return NULL if the desired ID value is not
> > > in the tree.
> > 
> > 
> > Confused.  idr_find() returns the thing it found, or NULL.  To which
> > comments do you refer?
> 
> Hi Andrew, Kevin,
> 
> Kevin is correct.  It's more of the nonsense related to having a counter
> in the upper bits of the id.  If you call idr_find with an id that is
> beyond the currently allocated space it ignores the upper bits and
> returns one of the entries that is in the allocated space.  This
> aliasing is most annoying.

erk, OK, we have vestigial bits still.  Note that MAX_ID_SHIFT is now 31 on
32-bit, so we're still waggling the top bit.

> I'm attaching an untested patch which removes the counter in the upper
> bits of the id and makes idr_find return NULL if the requested id is
> beyond the allocated space.

Would you have time to get it tested please?

>  I suspect that there are problems with
> id values which are less than zero.

Me too.  I'd only be confident in the 0..2G range.


> -#endif
> +	if (id >= (1 << n))
> +		return NULL;
>  	while (n > 0 && p) {
>  		n -= IDR_BITS;
>  		p = p->ary[(id >> n) & IDR_MASK];
> 

I think the above test is unneeded?

Re: [PATCH] 1/1: Device-Mapper: Remove 1024 devices limitation

[Jim Houston]

On Tue, 2004-07-06 at 18:28, Andrew Morton wrote:
> Jim Houston <jim.houston@comcast.net> wrote:
> >
> > On Tue, 2004-07-06 at 17:23, Andrew Morton wrote:
> > > Kevin Corry <kevcorry@us.ibm.com> wrote:
> > > >
> > > > After talking with Alasdair a bit, there might be one bug in the "dm-use-idr"
> > > > patch I submitted before. It seems (based on some comments in lib/idr.c) that
> > > > the idr_find() routine might not return NULL if the desired ID value is not
> > > > in the tree.
> > > 
> > > 
> > > Confused.  idr_find() returns the thing it found, or NULL.  To which
> > > comments do you refer?
> > 
> > Hi Andrew, Kevin,
> > 
> > Kevin is correct.  It's more of the nonsense related to having a counter
> > in the upper bits of the id.  If you call idr_find with an id that is
> > beyond the currently allocated space it ignores the upper bits and
> > returns one of the entries that is in the allocated space.  This
> > aliasing is most annoying.
> 
> erk, OK, we have vestigial bits still.  Note that MAX_ID_SHIFT is now 31 on
> 32-bit, so we're still waggling the top bit.
> 
> > I'm attaching an untested patch which removes the counter in the upper
> > bits of the id and makes idr_find return NULL if the requested id is
> > beyond the allocated space.
> 
> Would you have time to get it tested please?
> 
> >  I suspect that there are problems with
> > id values which are less than zero.
> 
> Me too.  I'd only be confident in the 0..2G range.
> 
> 
> > -#endif
> > +	if (id >= (1 << n))
> > +		return NULL;
> >  	while (n > 0 && p) {
> >  		n -= IDR_BITS;
> >  		p = p->ary[(id >> n) & IDR_MASK];
> > 
> 
> I think the above test is unneeded?

Hi Everyone,

With out the test above an id beyond the allocated space will alias
to one that exists.  Perhaps the highest id currently allocated is 
100, there will be two layers in the radix tree and the while loop
above will only look at the 10 least significant bits.  If you call
idr_find with 1025 it will return the pointer associated with id 1.

The patch I sent was against linux-2.6.7, so I missed the change to
MAX_ID_SHIFT.

Jim Houston - Concurrent Computer Corp.

Re: [PATCH] 1/1: Device-Mapper: Remove 1024 devices limitation

[Andrew Morton]

Jim Houston <jim.houston@comcast.net> wrote:
>
> With out the test above an id beyond the allocated space will alias
> to one that exists.  Perhaps the highest id currently allocated is 
> 100, there will be two layers in the radix tree and the while loop
> above will only look at the 10 least significant bits.  If you call
> idr_find with 1025 it will return the pointer associated with id 1.

OK.

> The patch I sent was against linux-2.6.7, so I missed the change to
> MAX_ID_SHIFT.

How about this?

diff -puN lib/idr.c~idr-stale-comment lib/idr.c
--- 25/lib/idr.c~idr-stale-comment	Tue Jul  6 16:12:45 2004
+++ 25-akpm/lib/idr.c	Tue Jul  6 16:15:41 2004
@@ -27,22 +27,6 @@
  * so you don't need to be too concerned about locking and conflicts
  * with the slab allocator.
 
- * What you need to do is, since we don't keep the counter as part of
- * id / ptr pair, to keep a copy of it in the pointed to structure
- * (or else where) so that when you ask for a ptr you can varify that
- * the returned ptr is correct by comparing the id it contains with the one
- * you asked for.  In other words, we only did half the reuse protection.
- * Since the code depends on your code doing this check, we ignore high
- * order bits in the id, not just the count, but bits that would, if used,
- * index outside of the allocated ids.  In other words, if the largest id
- * currently allocated is 32 a look up will only look at the low 5 bits of
- * the id.  Since you will want to keep this id in the structure anyway
- * (if for no other reason than to be able to eliminate the id when the
- * structure is found in some other way) this seems reasonable.  If you
- * really think otherwise, the code to check these bits here, it is just
- * disabled with a #if 0.
-
-
  * So here are the complete details:
 
  *  include <linux/idr.h>
@@ -371,15 +355,11 @@ void *idr_find(struct idr *idp, int id)
 	struct idr_layer *p;
 
 	n = idp->layers * IDR_BITS;
+	if (id >= (1 << n))
+		return NULL;
+
 	p = idp->top;
-#if 0
-	/*
-	 * This tests to see if bits outside the current tree are
-	 * present.  If so, tain't one of ours!
-	 */
-	if ( unlikely( (id & ~(~0 << MAX_ID_SHIFT)) >> (n + IDR_BITS)))
-	     return NULL;
-#endif
+
 	/* Mask off upper bits we don't use for the search. */
 	id &= MAX_ID_MASK;
 
_

Re: [PATCH] 1/1: Device-Mapper: Remove 1024 devices limitation

[Jim Houston]

On Tue, 2004-07-06 at 19:16, Andrew Morton wrote:
Jim Houston <jim.houston@comcast.net> wrote:
> >
> > With out the test above an id beyond the allocated space will alias
> > to one that exists.  Perhaps the highest id currently allocated is 
> > 100, there will be two layers in the radix tree and the while loop
> > above will only look at the 10 least significant bits.  If you call
> > idr_find with 1025 it will return the pointer associated with id 1.
> 
> OK.
> 
> > The patch I sent was against linux-2.6.7, so I missed the change to
> > MAX_ID_SHIFT.
> 
> How about this?
>  
>  	n = idp->layers * IDR_BITS;
> +	if (id >= (1 << n))
> +		return NULL;
> +
>  	p = idp->top;
> +
>  	/* Mask off upper bits we don't use for the search. */
>  	id &= MAX_ID_MASK;
>  

Hi Andrew,

It's not quite right.  If you want to keep a count in the upper bits
you have to mask off that count before checking if the id is beyond the
end of the allocated space.

Jim Houston - Concurrent Computer Corp.

Re: [PATCH] 1/1: Device-Mapper: Remove 1024 devices limitation

[Andrew Morton]

Jim Houston <jim.houston@comcast.net> wrote:
>
> On Tue, 2004-07-06 at 19:16, Andrew Morton wrote:
> Jim Houston <jim.houston@comcast.net> wrote:
> > >
> > > With out the test above an id beyond the allocated space will alias
> > > to one that exists.  Perhaps the highest id currently allocated is 
> > > 100, there will be two layers in the radix tree and the while loop
> > > above will only look at the 10 least significant bits.  If you call
> > > idr_find with 1025 it will return the pointer associated with id 1.
> > 
> > OK.
> > 
> > > The patch I sent was against linux-2.6.7, so I missed the change to
> > > MAX_ID_SHIFT.
> > 
> > How about this?
> >  
> >  	n = idp->layers * IDR_BITS;
> > +	if (id >= (1 << n))
> > +		return NULL;
> > +
> >  	p = idp->top;
> > +
> >  	/* Mask off upper bits we don't use for the search. */
> >  	id &= MAX_ID_MASK;
> >  
> 
> Hi Andrew,
> 
> It's not quite right.  If you want to keep a count in the upper bits
> you have to mask off that count before checking if the id is beyond the
> end of the allocated space.

OK, I'll fix that up.

But I don't want to keep a count in the upper bits!  I want rid of that
stuff altogether, completely, all of it.  It just keeps on hanging around :(

We should remove MAX_ID_* from the kernel altogether.

Re: [PATCH] 1/1: Device-Mapper: Remove 1024 devices limitation

[Kevin Corry]

On Wednesday 07 July 2004 6:10 am, Andrew Morton wrote:
> Jim Houston <jim.houston@comcast.net> wrote:
> >
> > Hi Andrew,
> >
> > It's not quite right.  If you want to keep a count in the upper bits
> > you have to mask off that count before checking if the id is beyond the
> > end of the allocated space.
>
> OK, I'll fix that up.
>
> But I don't want to keep a count in the upper bits!  I want rid of that
> stuff altogether, completely, all of it.  It just keeps on hanging around
> :(
>
> We should remove MAX_ID_* from the kernel altogether.

Just following up on the proposed IDR changes. Based on the patches in the 
latest -mm tree, I'm assuming there is or will be a fix for IDR so it will 
always return NULL when asked to find an id that's not currently allocated. 
Is this correct? If so, I can drop the second "dm-use-idr" patch (from July 
6, 2004) and keep the one that's currently in -mm.

Thanks!

-- 
Kevin Corry
kevcorry@us.ibm.com
http://evms.sourceforge.net/

Re: [PATCH] 1/1: Device-Mapper: Remove 1024 devices limitation

[Andrew Morton]

Kevin Corry <kevcorry@us.ibm.com> wrote:
>
> On Wednesday 07 July 2004 6:10 am, Andrew Morton wrote:
> > Jim Houston <jim.houston@comcast.net> wrote:
> > >
> > > Hi Andrew,
> > >
> > > It's not quite right.  If you want to keep a count in the upper bits
> > > you have to mask off that count before checking if the id is beyond the
> > > end of the allocated space.
> >
> > OK, I'll fix that up.
> >
> > But I don't want to keep a count in the upper bits!  I want rid of that
> > stuff altogether, completely, all of it.  It just keeps on hanging around
> > :(
> >
> > We should remove MAX_ID_* from the kernel altogether.
> 
> Just following up on the proposed IDR changes. Based on the patches in the 
> latest -mm tree, I'm assuming there is or will be a fix for IDR so it will 
> always return NULL when asked to find an id that's not currently allocated. 
> Is this correct? If so, I can drop the second "dm-use-idr" patch (from July 
> 6, 2004) and keep the one that's currently in -mm.
> 

Yes, I'm assuming that the code in Linus's tree at present is acceptable,
and I'll take another look at the idr code post-2.6.8.