diff options
Diffstat (limited to 'lib')
-rw-r--r-- | lib/idr.c | 34 |
1 files changed, 17 insertions, 17 deletions
@@ -157,18 +157,18 @@ static void idr_mark_full(struct idr_layer **pa, int id) | |||
157 | struct idr_layer *p = pa[0]; | 157 | struct idr_layer *p = pa[0]; |
158 | int l = 0; | 158 | int l = 0; |
159 | 159 | ||
160 | __set_bit(id & IDR_MASK, &p->bitmap); | 160 | __set_bit(id & IDR_MASK, p->bitmap); |
161 | /* | 161 | /* |
162 | * If this layer is full mark the bit in the layer above to | 162 | * If this layer is full mark the bit in the layer above to |
163 | * show that this part of the radix tree is full. This may | 163 | * show that this part of the radix tree is full. This may |
164 | * complete the layer above and require walking up the radix | 164 | * complete the layer above and require walking up the radix |
165 | * tree. | 165 | * tree. |
166 | */ | 166 | */ |
167 | while (p->bitmap == IDR_FULL) { | 167 | while (bitmap_full(p->bitmap, IDR_SIZE)) { |
168 | if (!(p = pa[++l])) | 168 | if (!(p = pa[++l])) |
169 | break; | 169 | break; |
170 | id = id >> IDR_BITS; | 170 | id = id >> IDR_BITS; |
171 | __set_bit((id & IDR_MASK), &p->bitmap); | 171 | __set_bit((id & IDR_MASK), p->bitmap); |
172 | } | 172 | } |
173 | } | 173 | } |
174 | 174 | ||
@@ -221,7 +221,6 @@ static int sub_alloc(struct idr *idp, int *starting_id, struct idr_layer **pa, | |||
221 | int n, m, sh; | 221 | int n, m, sh; |
222 | struct idr_layer *p, *new; | 222 | struct idr_layer *p, *new; |
223 | int l, id, oid; | 223 | int l, id, oid; |
224 | unsigned long bm; | ||
225 | 224 | ||
226 | id = *starting_id; | 225 | id = *starting_id; |
227 | restart: | 226 | restart: |
@@ -233,8 +232,7 @@ static int sub_alloc(struct idr *idp, int *starting_id, struct idr_layer **pa, | |||
233 | * We run around this while until we reach the leaf node... | 232 | * We run around this while until we reach the leaf node... |
234 | */ | 233 | */ |
235 | n = (id >> (IDR_BITS*l)) & IDR_MASK; | 234 | n = (id >> (IDR_BITS*l)) & IDR_MASK; |
236 | bm = ~p->bitmap; | 235 | m = find_next_zero_bit(p->bitmap, IDR_SIZE, n); |
237 | m = find_next_bit(&bm, IDR_SIZE, n); | ||
238 | if (m == IDR_SIZE) { | 236 | if (m == IDR_SIZE) { |
239 | /* no space available go back to previous layer. */ | 237 | /* no space available go back to previous layer. */ |
240 | l++; | 238 | l++; |
@@ -326,7 +324,8 @@ build_up: | |||
326 | for (new = p; p && p != idp->top; new = p) { | 324 | for (new = p; p && p != idp->top; new = p) { |
327 | p = p->ary[0]; | 325 | p = p->ary[0]; |
328 | new->ary[0] = NULL; | 326 | new->ary[0] = NULL; |
329 | new->bitmap = new->count = 0; | 327 | new->count = 0; |
328 | bitmap_clear(new->bitmap, 0, IDR_SIZE); | ||
330 | __move_to_free_list(idp, new); | 329 | __move_to_free_list(idp, new); |
331 | } | 330 | } |
332 | spin_unlock_irqrestore(&idp->lock, flags); | 331 | spin_unlock_irqrestore(&idp->lock, flags); |
@@ -335,8 +334,8 @@ build_up: | |||
335 | new->ary[0] = p; | 334 | new->ary[0] = p; |
336 | new->count = 1; | 335 | new->count = 1; |
337 | new->layer = layers-1; | 336 | new->layer = layers-1; |
338 | if (p->bitmap == IDR_FULL) | 337 | if (bitmap_full(p->bitmap, IDR_SIZE)) |
339 | __set_bit(0, &new->bitmap); | 338 | __set_bit(0, new->bitmap); |
340 | p = new; | 339 | p = new; |
341 | } | 340 | } |
342 | rcu_assign_pointer(idp->top, p); | 341 | rcu_assign_pointer(idp->top, p); |
@@ -517,14 +516,14 @@ static void sub_remove(struct idr *idp, int shift, int id) | |||
517 | 516 | ||
518 | while ((shift > 0) && p) { | 517 | while ((shift > 0) && p) { |
519 | n = (id >> shift) & IDR_MASK; | 518 | n = (id >> shift) & IDR_MASK; |
520 | __clear_bit(n, &p->bitmap); | 519 | __clear_bit(n, p->bitmap); |
521 | *++paa = &p->ary[n]; | 520 | *++paa = &p->ary[n]; |
522 | p = p->ary[n]; | 521 | p = p->ary[n]; |
523 | shift -= IDR_BITS; | 522 | shift -= IDR_BITS; |
524 | } | 523 | } |
525 | n = id & IDR_MASK; | 524 | n = id & IDR_MASK; |
526 | if (likely(p != NULL && test_bit(n, &p->bitmap))){ | 525 | if (likely(p != NULL && test_bit(n, p->bitmap))) { |
527 | __clear_bit(n, &p->bitmap); | 526 | __clear_bit(n, p->bitmap); |
528 | rcu_assign_pointer(p->ary[n], NULL); | 527 | rcu_assign_pointer(p->ary[n], NULL); |
529 | to_free = NULL; | 528 | to_free = NULL; |
530 | while(*paa && ! --((**paa)->count)){ | 529 | while(*paa && ! --((**paa)->count)){ |
@@ -567,7 +566,8 @@ void idr_remove(struct idr *idp, int id) | |||
567 | p = idp->top->ary[0]; | 566 | p = idp->top->ary[0]; |
568 | rcu_assign_pointer(idp->top, p); | 567 | rcu_assign_pointer(idp->top, p); |
569 | --idp->layers; | 568 | --idp->layers; |
570 | to_free->bitmap = to_free->count = 0; | 569 | to_free->count = 0; |
570 | bitmap_clear(to_free->bitmap, 0, IDR_SIZE); | ||
571 | free_layer(to_free); | 571 | free_layer(to_free); |
572 | } | 572 | } |
573 | while (idp->id_free_cnt >= MAX_IDR_FREE) { | 573 | while (idp->id_free_cnt >= MAX_IDR_FREE) { |
@@ -827,7 +827,7 @@ void *idr_replace(struct idr *idp, void *ptr, int id) | |||
827 | } | 827 | } |
828 | 828 | ||
829 | n = id & IDR_MASK; | 829 | n = id & IDR_MASK; |
830 | if (unlikely(p == NULL || !test_bit(n, &p->bitmap))) | 830 | if (unlikely(p == NULL || !test_bit(n, p->bitmap))) |
831 | return ERR_PTR(-ENOENT); | 831 | return ERR_PTR(-ENOENT); |
832 | 832 | ||
833 | old_p = p->ary[n]; | 833 | old_p = p->ary[n]; |
@@ -1024,7 +1024,7 @@ void ida_remove(struct ida *ida, int id) | |||
1024 | /* clear full bits while looking up the leaf idr_layer */ | 1024 | /* clear full bits while looking up the leaf idr_layer */ |
1025 | while ((shift > 0) && p) { | 1025 | while ((shift > 0) && p) { |
1026 | n = (idr_id >> shift) & IDR_MASK; | 1026 | n = (idr_id >> shift) & IDR_MASK; |
1027 | __clear_bit(n, &p->bitmap); | 1027 | __clear_bit(n, p->bitmap); |
1028 | p = p->ary[n]; | 1028 | p = p->ary[n]; |
1029 | shift -= IDR_BITS; | 1029 | shift -= IDR_BITS; |
1030 | } | 1030 | } |
@@ -1033,7 +1033,7 @@ void ida_remove(struct ida *ida, int id) | |||
1033 | goto err; | 1033 | goto err; |
1034 | 1034 | ||
1035 | n = idr_id & IDR_MASK; | 1035 | n = idr_id & IDR_MASK; |
1036 | __clear_bit(n, &p->bitmap); | 1036 | __clear_bit(n, p->bitmap); |
1037 | 1037 | ||
1038 | bitmap = (void *)p->ary[n]; | 1038 | bitmap = (void *)p->ary[n]; |
1039 | if (!test_bit(offset, bitmap->bitmap)) | 1039 | if (!test_bit(offset, bitmap->bitmap)) |
@@ -1042,7 +1042,7 @@ void ida_remove(struct ida *ida, int id) | |||
1042 | /* update bitmap and remove it if empty */ | 1042 | /* update bitmap and remove it if empty */ |
1043 | __clear_bit(offset, bitmap->bitmap); | 1043 | __clear_bit(offset, bitmap->bitmap); |
1044 | if (--bitmap->nr_busy == 0) { | 1044 | if (--bitmap->nr_busy == 0) { |
1045 | __set_bit(n, &p->bitmap); /* to please idr_remove() */ | 1045 | __set_bit(n, p->bitmap); /* to please idr_remove() */ |
1046 | idr_remove(&ida->idr, idr_id); | 1046 | idr_remove(&ida->idr, idr_id); |
1047 | free_bitmap(ida, bitmap); | 1047 | free_bitmap(ida, bitmap); |
1048 | } | 1048 | } |