summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorTejun Heo <htejun@gmail.com>2007-06-14 03:45:12 +0900
committerGreg Kroah-Hartman <gregkh@suse.de>2007-07-11 16:09:02 -0700
commit7aae6dd80e265aa9402ed507caaff4a5dba55069 (patch)
treeb6b2e4d4942fd199768f6df6b0694a886e8c4375
parentdc0afa8388972a9ed7c2203cc46d8df1a4713f65 (diff)
idr: fix obscure bug in allocation path
In sub_alloc(), when bitmap search fails, it goes up one level to continue search. This is done by updating the id cursor and searching the upper level again. If the cursor was at the end of the upper level, we need to go further than that. This wasn't implemented and when that happens the part of the cursor which indexes into the upper level wraps and sub_alloc() ends up searching the wrong bitmap. It allocates id which doesn't match the actual slot. This patch fixes this by restarting from the top if the search needs to go higher than one level. Signed-off-by: Tejun Heo <htejun@gmail.com> Signed-off-by: Greg Kroah-Hartman <gregkh@suse.de>
-rw-r--r--lib/idr.c16
1 files changed, 14 insertions, 2 deletions
diff --git a/lib/idr.c b/lib/idr.c
index 305117ca2d41..7b5a59caa989 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -100,10 +100,11 @@ static int sub_alloc(struct idr *idp, void *ptr, int *starting_id)
int n, m, sh;
struct idr_layer *p, *new;
struct idr_layer *pa[MAX_LEVEL];
- int l, id;
+ int l, id, oid;
long bm;
id = *starting_id;
+ restart:
p = idp->top;
l = idp->layers;
pa[l--] = NULL;
@@ -117,12 +118,23 @@ static int sub_alloc(struct idr *idp, void *ptr, int *starting_id)
if (m == IDR_SIZE) {
/* no space available go back to previous layer. */
l++;
+ oid = id;
id = (id | ((1 << (IDR_BITS * l)) - 1)) + 1;
+
+ /* if already at the top layer, we need to grow */
if (!(p = pa[l])) {
*starting_id = id;
return -2;
}
- continue;
+
+ /* If we need to go up one layer, continue the
+ * loop; otherwise, restart from the top.
+ */
+ sh = IDR_BITS * (l + 1);
+ if (oid >> sh == id >> sh)
+ continue;
+ else
+ goto restart;
}
if (m != n) {
sh = IDR_BITS*l;