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 <[email protected]>
--
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;
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
[Index of Archives]
[Kernel Newbies]
[Netfilter]
[Bugtraq]
[Photo]
[Stuff]
[Gimp]
[Yosemite News]
[MIPS Linux]
[ARM Linux]
[Linux Security]
[Linux RAID]
[Video 4 Linux]
[Linux for the blind]
[Linux Resources]
