idr_get_new_above() limitation?

Hello,
For ehca device driver we're intending to utilize 
idr_get_new_above() and have written a test case, which I'm attaching
at the end. Basically it tries to get an idr token above a lower boundary
by calling idr_get_new_above() and then uses idr_find() to check if 
the returned token can be found. 
Here is our observation with 2.6.22-rc7 on ppc64:

Use lower boundary 0x3ffffffc
[root@xyz idr_bug]# insmod idr_test_mod.ko start=1073741820
insmod: error inserting 'idr_test_mod.ko': -1 Unknown symbol in module
[root@xyz idr_bug]# dmesg -c
i=3ffffffc token=3ffffffc t=000000003ffffffc
i=3ffffffd token=3ffffffd t=000000003ffffffd
i=3ffffffe token=3ffffffe t=000000003ffffffe
i=3fffffff token=3fffffff t=000000003fffffff
i=40000000 token=40000000 t=0000000000000000
Invalid object 0000000000000000. Expected 40000000

That means token 0x40000000 seems to be the "upper boundary" of idr_find().
However the behaviour is not consistent in that it was returned by
idr_get_new_above().

Looking at void *idr_find(struct idr *idp, int id)
{
	int n;
	struct idr_layer *p;

	n = idp->layers * IDR_BITS;
	p = idp->top;

	/* Mask off upper bits we don't use for the search. */
	id &= MAX_ID_MASK;

	if (id >= (1 << n))
		return NULL;

	while (n > 0 && p) {
		n -= IDR_BITS;
		p = p->ary[(id >> n) & IDR_MASK];
	}
	return((void *)p);
}
we found that the if-condition has failed:
  layers = 5
  IDR_BITS = 6
  n = 30
  (id >= (1 << n)) = (0x40000000 >= 0x40000000) = 1

Since MAX_ID_MASK=0x7fffffff, I'm wondering if 0x40000000 is the actual
upper boundary. Any hints or suggestions are appreciated.

Thanks!
Nam



#include <linux/module.h>
#include <linux/idr.h>

MODULE_LICENSE("GPL");

int start_opt = 0x7e000000;

module_param_named(start, start_opt, int, 0);

MODULE_PARM_DESC(start,
		 "Start token for idr_get_new_above(). Default 0x7e000000");

static int __init idr_test_init(void)
{
	DEFINE_IDR(idr);
	int token, ret;
	unsigned long i;

	for (i = start_opt;  i <= MAX_ID_MASK; i++) {
		void * t;
		if (!idr_pre_get(&idr, GFP_KERNEL)) {
			printk(KERN_ERR "ERROR: Out of mem\n");
			return -ENOENT;
		}
		ret = idr_get_new_above(&idr, (void*)i, start_opt, &token);
		switch (ret) {
		case 0:
			t = idr_find(&idr, token);
			printk(KERN_ERR "i=%lx token=%x t=%p\n", i, token, t);
			if (t != (void*)i) {
				printk(KERN_ERR "Invalid object %p. Expected %lx\n",
				       t, i);
				return -ENOENT;
			}
			break;
		case -EAGAIN:
			i--;
			printk("idr_get_new_above() ret=-EAGAIN\n");
			break;
		default:
			printk(KERN_ERR "ERROR: Out of mem\n");
			break;
		}
	}
	/*
	 * return an error in any case since we don't need the module
	 * loaded anyway.
	 */
	return -ENOENT;
}

static void __exit idr_test_exit(void)
{
	printk(KERN_ERR "module exit\n");
}

module_init(idr_test_init);
module_exit(idr_test_exit);

On Mon, 2 Jul 2007 19:19:26 +0200
Hoang-Nam Nguyen [off-list ref] wrote:

For ehca device driver we're intending to utilize 
idr_get_new_above() and have written a test case, which I'm attaching
at the end. Basically it tries to get an idr token above a lower boundary
by calling idr_get_new_above() and then uses idr_find() to check if 
the returned token can be found. 
Here is our observation with 2.6.22-rc7 on ppc64:

Use lower boundary 0x3ffffffc
[root@xyz idr_bug]# insmod idr_test_mod.ko start=1073741820
insmod: error inserting 'idr_test_mod.ko': -1 Unknown symbol in module
[root@xyz idr_bug]# dmesg -c
i=3ffffffc token=3ffffffc t=000000003ffffffc
i=3ffffffd token=3ffffffd t=000000003ffffffd
i=3ffffffe token=3ffffffe t=000000003ffffffe
i=3fffffff token=3fffffff t=000000003fffffff
i=40000000 token=40000000 t=0000000000000000
Invalid object 0000000000000000. Expected 40000000

That means token 0x40000000 seems to be the "upper boundary" of idr_find().
However the behaviour is not consistent in that it was returned by
idr_get_new_above().

Looking at void *idr_find(struct idr *idp, int id)
{
	int n;
	struct idr_layer *p;

	n = idp->layers * IDR_BITS;
	p = idp->top;

	/* Mask off upper bits we don't use for the search. */
	id &= MAX_ID_MASK;

	if (id >= (1 << n))
		return NULL;

	while (n > 0 && p) {
		n -= IDR_BITS;
		p = p->ary[(id >> n) & IDR_MASK];
	}
	return((void *)p);
}
we found that the if-condition has failed:
  layers = 5
  IDR_BITS = 6
  n = 30
  (id >= (1 << n)) = (0x40000000 >= 0x40000000) = 1

Since MAX_ID_MASK=0x7fffffff, I'm wondering if 0x40000000 is the actual
upper boundary. Any hints or suggestions are appreciated.

Looks like a bug to me.  Really an IDR tree on 32-bit should go all
the way up to 0xffffffff.  Certainly up to 0x7fffffff.  And the fact
that idr_find() disagrees with idr_get_new_above() is a big hint
that the code is getting it wrong.

On Mon, 2007-07-02 at 19:19 +0200, Hoang-Nam Nguyen wrote:

i=3fffffff token=3fffffff t=000000003fffffff
i=40000000 token=40000000 t=0000000000000000
Invalid object 0000000000000000. Expected 40000000

That means token 0x40000000 seems to be the "upper boundary" of idr_find().
However the behaviour is not consistent in that it was returned by
idr_get_new_above().

Hi Nam,

Yes this is a bug.  Thanks for the great test module.

The problem is in idr_get_new_above_int() in the loop which
adds new layers to the top of the radix tree.  It is failing
the "layers < (MAX_LEVEL - 1)" test.  It doesn't allocate the
new layer but still calls sub_alloc() which relies on having
the new layer properly constructed.  I believe that it is
allocating the slot which corresponds to id = 0.

I believe this is an off by one error in calculating the
MAX_LEVEL value.  I will do a more careful review and post 
a fix in the next day or so.  I have been in Ottawa for OLS.
I'm flying home tomorrow.

Jim Houston - Concurrent Computer Corp.

On Tuesday 03 July 2007 02:31, Jim Houston wrote:

The problem is in idr_get_new_above_int() in the loop which
adds new layers to the top of the radix tree.  It is failing
the "layers < (MAX_LEVEL - 1)" test.  It doesn't allocate the
new layer but still calls sub_alloc() which relies on having
the new layer properly constructed.  I believe that it is
allocating the slot which corresponds to id = 0.

Hi Jim,
Thanks for your quick reply.
Yes, I realized that while condition too and have tried with a tiny
change like (layers < MAX_LEVEL), but without success with idr_find(), 
even though 6 layers were created and the object was added at proper
location. After several debug cycles I think to find the root cause 
in the if-condition in idr_find():
void *idr_find(struct idr *idp, int id)
{
	int n;
	struct idr_layer *p;

	n = idp->layers * IDR_BITS;
	p = idp->top;

	/* Mask off upper bits we don't use for the search. */
	id &= MAX_ID_MASK;

	if (id >= (1 << n))
		return NULL;
...
}
Since idp->layers is now 6, n is equal 36, ie out of 32-bit-range,
and therefore
	(1 << n) = (1 << 36) = 0
causing that if-cond to be true ie idr_find() fails.
Replacing that if-line by
	if ((long)id >= (1L << n))
makes idr_find() working properly until MAX_ID_MASK.
Since there are other places to be changed like above as well eg.
idr_replace() and because you're creating a patch too, I'm waiting
first for your comment. Let me know if you prefer me to send a
patch.
Regards
Nam

Hi Everyone,

Hoang-Nam Nguyen reported a bug in idr_get_new_above() 
which occurred with a starting id value like 0x3ffffffc.
His test module easily reproduced the problem.  Thanks.

The test revealed the following bugs:

1. Relying on shift operations which have undefined results
   e.g.: 1 << n where n > word size.  On i386 an integer shift
   only uses the low 5 bits of the shift count.

2. An off by one error which prevented the top most layer
   of the radix tree from being allocated.  This meant that
   sub_alloc() would allocate an entry in the existing portion
   of the radix tree which aliased the requested address.  When
   it tried to allocate id 0x40000000, it might use the slot 
   belonging to id 0.

3. There was also a failure in the code which walked back up
   the tree if an allocation failed.  The normal case is to
   descend the tree checking the starting id value against the
   bitmap at each level.  If the bit is set, we know that the
   entire sub-tree is full and we can short cut the search.
   We may still descend to the lowest level and find that the
   portion of the id space we want is full.  In this case we
   need to walk back up the tree and continue the search.
   The existing code just returned to the previous level and
   continued.  This resulted in an attempt to allocate an id
   above 0x3ffffffc using the slot for id 0x3ffffc00 instead of
   0x40000000 which it then claimed to have allocated.  The same
   problem occurs with 0x3ff as the requested id value if it
   is already in use.

With this patch, idr.c should work as advertised allocating id
values in the range 0...0x7fffffff.  Andrew had speculated that
it should allow the full range 0...0xffffffff to be used.  I was
tempted to make changes to allow this, but it would require changes
to API, e.g. making the starting id value and the return value
unsigned.

Signed-off-by: Jim Houston <redacted>

--

Index: linux-2.6.22-rc7/include/linux/idr.h
===================================================================

--- linux-2.6.22-rc7.orig/include/linux/idr.h	2007-04-25 23:08:32.000000000 -0400
+++ linux-2.6.22-rc7/include/linux/idr.h	2007-07-06 16:46:31.000000000 -0400

@@ -18,17 +18,9 @@
 #if BITS_PER_LONG == 32
 # define IDR_BITS 5
 # define IDR_FULL 0xfffffffful
-/* We can only use two of the bits in the top level because there is
-   only one possible bit in the top level (5 bits * 7 levels = 35
-   bits, but you only use 31 bits in the id). */
-# define TOP_LEVEL_FULL (IDR_FULL >> 30)
 #elif BITS_PER_LONG == 64
 # define IDR_BITS 6
 # define IDR_FULL 0xfffffffffffffffful
-/* We can only use two of the bits in the top level because there is
-   only one possible bit in the top level (6 bits * 6 levels = 36
-   bits, but you only use 31 bits in the id). */
-# define TOP_LEVEL_FULL (IDR_FULL >> 62)
 #else
 # error "BITS_PER_LONG is not 32 or 64"
 #endif

Index: linux-2.6.22-rc7/lib/idr.c
===================================================================

--- linux-2.6.22-rc7.orig/lib/idr.c	2007-04-25 23:08:32.000000000 -0400
+++ linux-2.6.22-rc7/lib/idr.c	2007-07-10 11:05:19.000000000 -0400

@@ -105,8 +105,8 @@
 
 	id = *starting_id;
 	p = idp->top;
-	l = idp->layers;
-	pa[l--] = NULL;
+	l = idp->layers - 1;
+	pa[l] = NULL;
 	while (1) {
 		/*
 		 * We run around this while until we reach the leaf node...

@@ -117,8 +117,14 @@
 		if (m == IDR_SIZE) {
 			/* no space available go back to previous layer. */
 			l++;
-			id = (id | ((1 << (IDR_BITS * l)) - 1)) + 1;
-			if (!(p = pa[l])) {
+			id = (id | ((1 << (IDR_BITS * l)) - 1));
+			while (((id >> (IDR_BITS * l)) & IDR_MASK) == IDR_MASK)
+				l++;
+			id++;
+			p = pa[l-1];
+			if ((id >= MAX_ID_BIT) || (id < 0))
+				return -3;
+			if (!p) {
 				*starting_id = id;
 				return -2;
 			}

@@ -141,7 +147,7 @@
 			p->ary[m] = new;
 			p->count++;
 		}
-		pa[l--] = p;
+		pa[--l] = p;
 		p = p->ary[m];
 	}
 	/*

@@ -159,7 +165,7 @@
 	 */
 	n = id;
 	while (p->bitmap == IDR_FULL) {
-		if (!(p = pa[++l]))
+		if (!(p = pa[l++]))
 			break;
 		n = n >> IDR_BITS;
 		__set_bit((n & IDR_MASK), &p->bitmap);

@@ -186,7 +192,7 @@
 	 * Add a new layer to the top of the tree if the requested
 	 * id is larger than the currently allocated space.
 	 */
-	while ((layers < (MAX_LEVEL - 1)) && (id >= (1 << (layers*IDR_BITS)))) {
+	while ((layers < MAX_LEVEL) && (id & ((~0) << (layers*IDR_BITS)))) {
 		layers++;
 		if (!p->count)
 			continue;

@@ -299,7 +305,7 @@
 static void sub_remove(struct idr *idp, int shift, int id)
 {
 	struct idr_layer *p = idp->top;
-	struct idr_layer **pa[MAX_LEVEL];
+	struct idr_layer **pa[MAX_LEVEL+1];
 	struct idr_layer ***paa = &pa[0];
 	int n;
 

@@ -392,7 +398,7 @@
 	/* Mask off upper bits we don't use for the search. */
 	id &= MAX_ID_MASK;
 
-	if (id >= (1 << n))
+	if ((n <= MAX_ID_SHIFT) && (id & ((~0) << n)))
 		return NULL;
 
 	while (n > 0 && p) {

@@ -425,7 +431,7 @@
 
 	id &= MAX_ID_MASK;
 
-	if (id >= (1 << n))
+	if ((n <= MAX_ID_SHIFT) && (id & ((~0) << n)))
 		return ERR_PTR(-EINVAL);
 
 	n -= IDR_BITS;

With this patch, idr.c should work as advertised allocating id
values in the range 0...0x7fffffff.  Andrew had speculated that
it should allow the full range 0...0xffffffff to be used.  I was
tempted to make changes to allow this, but it would require changes
to API, e.g. making the starting id value and the return value
unsigned.

Hi Jim, thanks much for this patch. It should work fine as far
as I can read. Will give it a try in next couple of days.
Nam

On Tue, 10 Jul 2007 16:05:31 -0400
Jim Houston [off-list ref] wrote:

Hoang-Nam Nguyen reported a bug in idr_get_new_above() 
which occurred with a starting id value like 0x3ffffffc.
His test module easily reproduced the problem.  Thanks.

The test revealed the following bugs:

1. Relying on shift operations which have undefined results
   e.g.: 1 << n where n > word size.  On i386 an integer shift
   only uses the low 5 bits of the shift count.

2. An off by one error which prevented the top most layer
   of the radix tree from being allocated.  This meant that
   sub_alloc() would allocate an entry in the existing portion
   of the radix tree which aliased the requested address.  When
   it tried to allocate id 0x40000000, it might use the slot 
   belonging to id 0.

3. There was also a failure in the code which walked back up
   the tree if an allocation failed.  The normal case is to
   descend the tree checking the starting id value against the
   bitmap at each level.  If the bit is set, we know that the
   entire sub-tree is full and we can short cut the search.
   We may still descend to the lowest level and find that the
   portion of the id space we want is full.  In this case we
   need to walk back up the tree and continue the search.
   The existing code just returned to the previous level and
   continued.  This resulted in an attempt to allocate an id
   above 0x3ffffffc using the slot for id 0x3ffffc00 instead of
   0x40000000 which it then claimed to have allocated.  The same
   problem occurs with 0x3ff as the requested id value if it
   is already in use.

With this patch, idr.c should work as advertised allocating id
values in the range 0...0x7fffffff.  Andrew had speculated that
it should allow the full range 0...0xffffffff to be used.  I was
tempted to make changes to allow this, but it would require changes
to API, e.g. making the starting id value and the return value
unsigned.

Problem.  There are a large number of IDR changes pending and this
patch breaks in way which I am not at all confident in fixing.

Originarily I'd just dump the earlier patches because bugfixes come
first.  But this time there's a very large dependency trail on the
earlier patches (especially Tejun's extensive sysfs rework in Greg's
driver tree) so the wreckage would be extensive.

Also, it's possible that Tejun's changes already fixed some of the things
which you fixed.  Or added new bugs ;)

Bottom line: a reworked patch against 2.6.22-rc6-mm1 would be muchly
appreciated if poss, please.

While you're there, it would be helpful if you could review all these
pending IDR changes:

ftp://ftp.kernel.org/pub/linux/kernel/people/akpm/patches/2.6/2.6.22-rc6/2.6.22-rc6-mm1/broken-out/gregkh-driver-ida-implement-idr-based-id-allocator.patch
ftp://ftp.kernel.org/pub/linux/kernel/people/akpm/patches/2.6/2.6.22-rc6/2.6.22-rc6-mm1/broken-out/gregkh-driver-idr-fix-obscure-bug-in-allocation-path.patch
ftp://ftp.kernel.org/pub/linux/kernel/people/akpm/patches/2.6/2.6.22-rc6/2.6.22-rc6-mm1/broken-out/gregkh-driver-idr-separate-out-idr_mark_full.patch
ftp://ftp.kernel.org/pub/linux/kernel/people/akpm/patches/2.6/2.6.22-rc6/2.6.22-rc6-mm1/broken-out/lib-add-idr_for_each.patch
ftp://ftp.kernel.org/pub/linux/kernel/people/akpm/patches/2.6/2.6.22-rc6/2.6.22-rc6-mm1/broken-out/lib-add-idr_for_each-fix.patch
ftp://ftp.kernel.org/pub/linux/kernel/people/akpm/patches/2.6/2.6.22-rc6/2.6.22-rc6-mm1/broken-out/lib-add-idr_remove_all.patch

Thanks.

On 07/12/2007 05:35 PM, Andrew Morton wrote:

quoted

With this patch, idr.c should work as advertised allocating id
values in the range 0...0x7fffffff.  Andrew had speculated that
it should allow the full range 0...0xffffffff to be used.  I was
tempted to make changes to allow this, but it would require changes
to API, e.g. making the starting id value and the return value
unsigned.

Problem.  There are a large number of IDR changes pending and this
patch breaks in way which I am not at all confident in fixing.

Originarily I'd just dump the earlier patches because bugfixes come
first.  But this time there's a very large dependency trail on the
earlier patches (especially Tejun's extensive sysfs rework in Greg's
driver tree) so the wreckage would be extensive.

Also, it's possible that Tejun's changes already fixed some of the things
which you fixed.  Or added new bugs ;)

Bottom line: a reworked patch against 2.6.22-rc6-mm1 would be muchly
appreciated if poss, please.

While you're there, it would be helpful if you could review all these
pending IDR changes:

ftp://ftp.kernel.org/pub/linux/kernel/people/akpm/patches/2.6/2.6.22-rc6/2.6.22-rc6-mm1/broken-out/gregkh-driver-ida-implement-idr-based-id-allocator.patch
ftp://ftp.kernel.org/pub/linux/kernel/people/akpm/patches/2.6/2.6.22-rc6/2.6.22-rc6-mm1/broken-out/gregkh-driver-idr-fix-obscure-bug-in-allocation-path.patch
ftp://ftp.kernel.org/pub/linux/kernel/people/akpm/patches/2.6/2.6.22-rc6/2.6.22-rc6-mm1/broken-out/gregkh-driver-idr-separate-out-idr_mark_full.patch
ftp://ftp.kernel.org/pub/linux/kernel/people/akpm/patches/2.6/2.6.22-rc6/2.6.22-rc6-mm1/broken-out/lib-add-idr_for_each.patch
ftp://ftp.kernel.org/pub/linux/kernel/people/akpm/patches/2.6/2.6.22-rc6/2.6.22-rc6-mm1/broken-out/lib-add-idr_for_each-fix.patch
ftp://ftp.kernel.org/pub/linux/kernel/people/akpm/patches/2.6/2.6.22-rc6/2.6.22-rc6-mm1/broken-out/lib-add-idr_remove_all.patch

The first three just got merged into mainline...

Hello,

Andrew Morton wrote:

quoted

Hoang-Nam Nguyen reported a bug in idr_get_new_above() 
which occurred with a starting id value like 0x3ffffffc.
His test module easily reproduced the problem.  Thanks.

The test revealed the following bugs:

1. Relying on shift operations which have undefined results
   e.g.: 1 << n where n > word size.  On i386 an integer shift
   only uses the low 5 bits of the shift count.

2. An off by one error which prevented the top most layer
   of the radix tree from being allocated.  This meant that
   sub_alloc() would allocate an entry in the existing portion
   of the radix tree which aliased the requested address.  When
   it tried to allocate id 0x40000000, it might use the slot 
   belonging to id 0.

3. There was also a failure in the code which walked back up
   the tree if an allocation failed.  The normal case is to
   descend the tree checking the starting id value against the
   bitmap at each level.  If the bit is set, we know that the
   entire sub-tree is full and we can short cut the search.
   We may still descend to the lowest level and find that the
   portion of the id space we want is full.  In this case we
   need to walk back up the tree and continue the search.
   The existing code just returned to the previous level and
   continued.  This resulted in an attempt to allocate an id
   above 0x3ffffffc using the slot for id 0x3ffffc00 instead of
   0x40000000 which it then claimed to have allocated.  The same
   problem occurs with 0x3ff as the requested id value if it
   is already in use.

The third one sounds like the bug I fixed.  With it fixed, I verified
idr works correctly at least in the lower range of allocation by running
it parallelly with simple bitmap allocator but haven't tested higher
range like 0x3ffffffc.

-- 
tejun