[PATCH] IDR fixups

There were definately some problems in there.  I've made some changes and
tested with a lot of bounds.  I don't have a machine with enough memory to
fill it up (it would take ~16GB on a 64-bit machine), but I use the "above"
code to simulate a lot of situations.

The problems were:

    * IDR_FULL was not the right value
    * idr_get_new_above() was not defined in the headers or documented.
    * idr_alloc() bug-ed if there was a race and not enough memory was
      allocated.  It should have returned NULL.
    * id will overflow when you go past the end.
    * There was a "(id >= (1 << (layers*IDR_BITS)))" comparison, but at
      the top layer it would overflow the id and be zero.
    * The allocation should return ENOSPC for an "above" value with
      nothing above it, but it returned EAGAIN.

I have not tested on 64-bits (as I don't have a 64-bit machine).

I've included the files, a diff from the previous version, and my test
programs.

For the test programs, idr_test <size> will just attempt to allocate 
<size> elements, check them, free them, and check them again.

idr_test2 <size> <incr> will allocate <size> element with <incr> between
them.

idr_test3 just tests some bounds and tries all values with just a few in
the idr.

Signed-off-by: Andrew Morton <akpm@osdl.org>
Signed-off-by: Linus Torvalds <torvalds@osdl.org>

1 files changed, 31 insertions, 14 deletions

diff --git a/lib/idr.c b/lib/idr.c
index a4c042d7445923..cd4d1389fde072 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -72,6 +72,11 @@
  *   with the id.  The value is returned in the "id" field.  idr_get_new()
  *   returns a value in the range 0 ... 0x7fffffff
 
+ * int idr_get_new_above(struct idr *idp, void *ptr, int start_id, int *id);
+
+ *   Like idr_get_new(), but the returned id is guaranteed to be at or
+ *   above start_id.
+
  * void *idr_find(struct idr *idp, int id);
  
  *   returns the "ptr", given the id.  A NULL return indicates that the
@@ -112,7 +117,7 @@ static struct idr_layer *alloc_layer(struct idr *idp)
 
 	spin_lock(&idp->lock);
 	if (!(p = idp->id_free))
-		BUG();
+		return NULL;
 	idp->id_free = p->ary[0];
 	idp->id_free_cnt--;
 	p->ary[0] = 0;
@@ -178,8 +183,8 @@ static int sub_alloc(struct idr *idp, void *ptr, int *starting_id)
 			sh = IDR_BITS*l;
 			id = ((id >> sh) ^ n ^ m) << sh;
 		}
-		if (id >= MAX_ID_BIT)
-			return -1;
+		if ((id >= MAX_ID_BIT) || (id < 0))
+			return -3;
 		if (l == 0)
 			break;
 		/*
@@ -217,7 +222,7 @@ static int sub_alloc(struct idr *idp, void *ptr, int *starting_id)
 	return(id);
 }
 
-int idr_get_new_above(struct idr *idp, void *ptr, int starting_id)
+static int idr_get_new_above_int(struct idr *idp, void *ptr, int starting_id)
 {
 	struct idr_layer *p, *new;
 	int layers, v, id;
@@ -235,7 +240,7 @@ build_up:
 	 * Add a new layer to the top of the tree if the requested
 	 * id is larger than the currently allocated space.
 	 */
-	while (id >= (1 << (layers*IDR_BITS))) {
+	while ((layers < MAX_LEVEL) && (id >= (1 << (layers*IDR_BITS)))) {
 		layers++;
 		if (!p->count)
 			continue;
@@ -265,27 +270,39 @@ build_up:
 		goto build_up;
 	return(v);
 }
-EXPORT_SYMBOL(idr_get_new_above);
 
-static int idr_full(struct idr *idp)
+int idr_get_new_above(struct idr *idp, void *ptr, int starting_id, int *id)
 {
-	return ((idp->layers >= MAX_LEVEL)
-		&& (idp->top->bitmap == TOP_LEVEL_FULL));
+	int rv;
+	rv = idr_get_new_above_int(idp, ptr, starting_id);
+	/*
+	 * This is a cheap hack until the IDR code can be fixed to
+	 * return proper error values.
+	 */
+	if (rv < 0) {
+		if (rv == -1)
+			return -EAGAIN;
+		else /* Will be -3 */
+			return -ENOSPC;
+	}
+	*id = rv;
+	return 0;
 }
+EXPORT_SYMBOL(idr_get_new_above);
 
 int idr_get_new(struct idr *idp, void *ptr, int *id)
 {
 	int rv;
-	rv = idr_get_new_above(idp, ptr, 0);
+	rv = idr_get_new_above_int(idp, ptr, 0);
 	/*
 	 * This is a cheap hack until the IDR code can be fixed to
 	 * return proper error values.
 	 */
-	if (rv == -1) {
-		if (idr_full(idp))
-			return -ENOSPC;
-		else
+	if (rv < 0) {
+		if (rv == -1)
 			return -EAGAIN;
+		else /* Will be -3 */
+			return -ENOSPC;
 	}
 	*id = rv;
 	return 0;