aboutsummaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
authorTejun Heo <tj@kernel.org>2013-02-27 20:05:05 -0500
committerLinus Torvalds <torvalds@linux-foundation.org>2013-02-27 22:10:20 -0500
commit1d9b2e1e663719d406e3a770979a19ba4233bba0 (patch)
tree359bf3e2dce77fda66d42296992e705f0b305ea1 /lib
parente8c8d1bc063bc88cfa1356266027b5075d3a82d7 (diff)
idr: remove length restriction from idr_layer->bitmap
Currently, idr->bitmap is declared as an unsigned long which restricts the number of bits an idr_layer can contain. All bitops can handle arbitrary positive integer bit number and there's no reason for this restriction. Declare idr_layer->bitmap using DECLARE_BITMAP() instead of a single unsigned long. * idr_layer->bitmap is now an array. '&' dropped from params to bitops. * Replaced "== IDR_FULL" tests with bitmap_full() and removed IDR_FULL. * Replaced find_next_bit() on ~bitmap with find_next_zero_bit(). * Replaced "bitmap = 0" with bitmap_clear(). This patch doesn't (or at least shouldn't) introduce any behavior changes. [akpm@linux-foundation.org: checkpatch fixes] Signed-off-by: Tejun Heo <tj@kernel.org> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Diffstat (limited to 'lib')
-rw-r--r--lib/idr.c34
1 files changed, 17 insertions, 17 deletions
diff --git a/lib/idr.c b/lib/idr.c
index e2b799989ab0..d66e75bfc1a0 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -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 }