aboutsummaryrefslogtreecommitdiffstats
path: root/lib/idr.c
diff options
context:
space:
mode:
authorTejun Heo <htejun@gmail.com>2007-06-13 14:45:12 -0400
committerGreg Kroah-Hartman <gregkh@suse.de>2007-07-11 19:09:02 -0400
commit7aae6dd80e265aa9402ed507caaff4a5dba55069 (patch)
treeb6b2e4d4942fd199768f6df6b0694a886e8c4375 /lib/idr.c
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>
Diffstat (limited to 'lib/idr.c')
-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)
100 int n, m, sh; 100 int n, m, sh;
101 struct idr_layer *p, *new; 101 struct idr_layer *p, *new;
102 struct idr_layer *pa[MAX_LEVEL]; 102 struct idr_layer *pa[MAX_LEVEL];
103 int l, id; 103 int l, id, oid;
104 long bm; 104 long bm;
105 105
106 id = *starting_id; 106 id = *starting_id;
107 restart:
107 p = idp->top; 108 p = idp->top;
108 l = idp->layers; 109 l = idp->layers;
109 pa[l--] = NULL; 110 pa[l--] = NULL;
@@ -117,12 +118,23 @@ static int sub_alloc(struct idr *idp, void *ptr, int *starting_id)
117 if (m == IDR_SIZE) { 118 if (m == IDR_SIZE) {
118 /* no space available go back to previous layer. */ 119 /* no space available go back to previous layer. */
119 l++; 120 l++;
121 oid = id;
120 id = (id | ((1 << (IDR_BITS * l)) - 1)) + 1; 122 id = (id | ((1 << (IDR_BITS * l)) - 1)) + 1;
123
124 /* if already at the top layer, we need to grow */
121 if (!(p = pa[l])) { 125 if (!(p = pa[l])) {
122 *starting_id = id; 126 *starting_id = id;
123 return -2; 127 return -2;
124 } 128 }
125 continue; 129
130 /* If we need to go up one layer, continue the
131 * loop; otherwise, restart from the top.
132 */
133 sh = IDR_BITS * (l + 1);
134 if (oid >> sh == id >> sh)
135 continue;
136 else
137 goto restart;
126 } 138 }
127 if (m != n) { 139 if (m != n) {
128 sh = IDR_BITS*l; 140 sh = IDR_BITS*l;