SAFE public projects git trees. - safe/jmp/linux-2.6/blob - lib/idr.c

   1 /*
   2  * 2002-10-18  written by Jim Houston jim.houston@ccur.com
   3  *      Copyright (C) 2002 by Concurrent Computer Corporation
   4  *      Distributed under the GNU GPL license version 2.
   5  *
   6  * Modified by George Anzinger to reuse immediately and to use
   7  * find bit instructions.  Also removed _irq on spinlocks.
   8  *
   9  * Small id to pointer translation service.
  10  *
  11  * It uses a radix tree like structure as a sparse array indexed
  12  * by the id to obtain the pointer.  The bitmap makes allocating
  13  * a new id quick.
  14  *
  15  * You call it to allocate an id (an int) an associate with that id a
  16  * pointer or what ever, we treat it as a (void *).  You can pass this
  17  * id to a user for him to pass back at a later time.  You then pass
  18  * that id to this code and it returns your pointer.
  19
  20  * You can release ids at any time. When all ids are released, most of
  21  * the memory is returned (we keep IDR_FREE_MAX) in a local pool so we
  22  * don't need to go to the memory "store" during an id allocate, just
  23  * so you don't need to be too concerned about locking and conflicts
  24  * with the slab allocator.
  25  */
  26
  27 #ifndef TEST                        // to test in user space...
  28 #include <linux/slab.h>
  29 #include <linux/init.h>
  30 #include <linux/module.h>
  31 #endif
  32 #include <linux/err.h>
  33 #include <linux/string.h>
  34 #include <linux/idr.h>
  35
  36 static struct kmem_cache *idr_layer_cache;
  37
  38 static struct idr_layer *get_from_free_list(struct idr *idp)
  39 {
  40         struct idr_layer *p;
  41         unsigned long flags;
  42
  43         spin_lock_irqsave(&idp->lock, flags);
  44         if ((p = idp->id_free)) {
  45                 idp->id_free = p->ary[0];
  46                 idp->id_free_cnt--;
  47                 p->ary[0] = NULL;
  48         }
  49         spin_unlock_irqrestore(&idp->lock, flags);
  50         return(p);
  51 }
  52
  53 /* only called when idp->lock is held */
  54 static void __move_to_free_list(struct idr *idp, struct idr_layer *p)
  55 {
  56         p->ary[0] = idp->id_free;
  57         idp->id_free = p;
  58         idp->id_free_cnt++;
  59 }
  60
  61 static void move_to_free_list(struct idr *idp, struct idr_layer *p)
  62 {
  63         unsigned long flags;
  64
  65         /*
  66          * Depends on the return element being zeroed.
  67          */
  68         spin_lock_irqsave(&idp->lock, flags);
  69         __move_to_free_list(idp, p);
  70         spin_unlock_irqrestore(&idp->lock, flags);
  71 }
  72
  73 static void idr_mark_full(struct idr_layer **pa, int id)
  74 {
  75         struct idr_layer *p = pa[0];
  76         int l = 0;
  77
  78         __set_bit(id & IDR_MASK, &p->bitmap);
  79         /*
  80          * If this layer is full mark the bit in the layer above to
  81          * show that this part of the radix tree is full.  This may
  82          * complete the layer above and require walking up the radix
  83          * tree.
  84          */
  85         while (p->bitmap == IDR_FULL) {
  86                 if (!(p = pa[++l]))
  87                         break;
  88                 id = id >> IDR_BITS;
  89                 __set_bit((id & IDR_MASK), &p->bitmap);
  90         }
  91 }
  92
  93 /**
  94  * idr_pre_get - reserver resources for idr allocation
  95  * @idp:        idr handle
  96  * @gfp_mask:   memory allocation flags
  97  *
  98  * This function should be called prior to locking and calling the
  99  * following function.  It preallocates enough memory to satisfy
 100  * the worst possible allocation.
 101  *
 102  * If the system is REALLY out of memory this function returns 0,
 103  * otherwise 1.
 104  */
 105 int idr_pre_get(struct idr *idp, gfp_t gfp_mask)
 106 {
 107         while (idp->id_free_cnt < IDR_FREE_MAX) {
 108                 struct idr_layer *new;
 109                 new = kmem_cache_alloc(idr_layer_cache, gfp_mask);
 110                 if (new == NULL)
 111                         return (0);
 112                 move_to_free_list(idp, new);
 113         }
 114         return 1;
 115 }
 116 EXPORT_SYMBOL(idr_pre_get);
 117
 118 static int sub_alloc(struct idr *idp, int *starting_id, struct idr_layer **pa)
 119 {
 120         int n, m, sh;
 121         struct idr_layer *p, *new;
 122         int l, id, oid;
 123         unsigned long bm;
 124
 125         id = *starting_id;
 126  restart:
 127         p = idp->top;
 128         l = idp->layers;
 129         pa[l--] = NULL;
 130         while (1) {
 131                 /*
 132                  * We run around this while until we reach the leaf node...
 133                  */
 134                 n = (id >> (IDR_BITS*l)) & IDR_MASK;
 135                 bm = ~p->bitmap;
 136                 m = find_next_bit(&bm, IDR_SIZE, n);
 137                 if (m == IDR_SIZE) {
 138                         /* no space available go back to previous layer. */
 139                         l++;
 140                         oid = id;
 141                         id = (id | ((1 << (IDR_BITS * l)) - 1)) + 1;
 142
 143                         /* if already at the top layer, we need to grow */
 144                         if (!(p = pa[l])) {
 145                                 *starting_id = id;
 146                                 return -2;
 147                         }
 148
 149                         /* If we need to go up one layer, continue the
 150                          * loop; otherwise, restart from the top.
 151                          */
 152                         sh = IDR_BITS * (l + 1);
 153                         if (oid >> sh == id >> sh)
 154                                 continue;
 155                         else
 156                                 goto restart;
 157                 }
 158                 if (m != n) {
 159                         sh = IDR_BITS*l;
 160                         id = ((id >> sh) ^ n ^ m) << sh;
 161                 }
 162                 if ((id >= MAX_ID_BIT) || (id < 0))
 163                         return -3;
 164                 if (l == 0)
 165                         break;
 166                 /*
 167                  * Create the layer below if it is missing.
 168                  */
 169                 if (!p->ary[m]) {
 170                         new = get_from_free_list(idp);
 171                         if (!new)
 172                                 return -1;
 173                         p->ary[m] = new;
 174                         p->count++;
 175                 }
 176                 pa[l--] = p;
 177                 p = p->ary[m];
 178         }
 179
 180         pa[l] = p;
 181         return id;
 182 }
 183
 184 static int idr_get_empty_slot(struct idr *idp, int starting_id,
 185                               struct idr_layer **pa)
 186 {
 187         struct idr_layer *p, *new;
 188         int layers, v, id;
 189         unsigned long flags;
 190
 191         id = starting_id;
 192 build_up:
 193         p = idp->top;
 194         layers = idp->layers;
 195         if (unlikely(!p)) {
 196                 if (!(p = get_from_free_list(idp)))
 197                         return -1;
 198                 layers = 1;
 199         }
 200         /*
 201          * Add a new layer to the top of the tree if the requested
 202          * id is larger than the currently allocated space.
 203          */
 204         while ((layers < (MAX_LEVEL - 1)) && (id >= (1 << (layers*IDR_BITS)))) {
 205                 layers++;
 206                 if (!p->count)
 207                         continue;
 208                 if (!(new = get_from_free_list(idp))) {
 209                         /*
 210                          * The allocation failed.  If we built part of
 211                          * the structure tear it down.
 212                          */
 213                         spin_lock_irqsave(&idp->lock, flags);
 214                         for (new = p; p && p != idp->top; new = p) {
 215                                 p = p->ary[0];
 216                                 new->ary[0] = NULL;
 217                                 new->bitmap = new->count = 0;
 218                                 __move_to_free_list(idp, new);
 219                         }
 220                         spin_unlock_irqrestore(&idp->lock, flags);
 221                         return -1;
 222                 }
 223                 new->ary[0] = p;
 224                 new->count = 1;
 225                 if (p->bitmap == IDR_FULL)
 226                         __set_bit(0, &new->bitmap);
 227                 p = new;
 228         }
 229         idp->top = p;
 230         idp->layers = layers;
 231         v = sub_alloc(idp, &id, pa);
 232         if (v == -2)
 233                 goto build_up;
 234         return(v);
 235 }
 236
 237 static int idr_get_new_above_int(struct idr *idp, void *ptr, int starting_id)
 238 {
 239         struct idr_layer *pa[MAX_LEVEL];
 240         int id;
 241
 242         id = idr_get_empty_slot(idp, starting_id, pa);
 243         if (id >= 0) {
 244                 /*
 245                  * Successfully found an empty slot.  Install the user
 246                  * pointer and mark the slot full.
 247                  */
 248                 pa[0]->ary[id & IDR_MASK] = (struct idr_layer *)ptr;
 249                 pa[0]->count++;
 250                 idr_mark_full(pa, id);
 251         }
 252
 253         return id;
 254 }
 255
 256 /**
 257  * idr_get_new_above - allocate new idr entry above or equal to a start id
 258  * @idp: idr handle
 259  * @ptr: pointer you want associated with the ide
 260  * @start_id: id to start search at
 261  * @id: pointer to the allocated handle
 262  *
 263  * This is the allocate id function.  It should be called with any
 264  * required locks.
 265  *
 266  * If memory is required, it will return -EAGAIN, you should unlock
 267  * and go back to the idr_pre_get() call.  If the idr is full, it will
 268  * return -ENOSPC.
 269  *
 270  * @id returns a value in the range 0 ... 0x7fffffff
 271  */
 272 int idr_get_new_above(struct idr *idp, void *ptr, int starting_id, int *id)
 273 {
 274         int rv;
 275
 276         rv = idr_get_new_above_int(idp, ptr, starting_id);
 277         /*
 278          * This is a cheap hack until the IDR code can be fixed to
 279          * return proper error values.
 280          */
 281         if (rv < 0) {
 282                 if (rv == -1)
 283                         return -EAGAIN;
 284                 else /* Will be -3 */
 285                         return -ENOSPC;
 286         }
 287         *id = rv;
 288         return 0;
 289 }
 290 EXPORT_SYMBOL(idr_get_new_above);
 291
 292 /**
 293  * idr_get_new - allocate new idr entry
 294  * @idp: idr handle
 295  * @ptr: pointer you want associated with the ide
 296  * @id: pointer to the allocated handle
 297  *
 298  * This is the allocate id function.  It should be called with any
 299  * required locks.
 300  *
 301  * If memory is required, it will return -EAGAIN, you should unlock
 302  * and go back to the idr_pre_get() call.  If the idr is full, it will
 303  * return -ENOSPC.
 304  *
 305  * @id returns a value in the range 0 ... 0x7fffffff
 306  */
 307 int idr_get_new(struct idr *idp, void *ptr, int *id)
 308 {
 309         int rv;
 310
 311         rv = idr_get_new_above_int(idp, ptr, 0);
 312         /*
 313          * This is a cheap hack until the IDR code can be fixed to
 314          * return proper error values.
 315          */
 316         if (rv < 0) {
 317                 if (rv == -1)
 318                         return -EAGAIN;
 319                 else /* Will be -3 */
 320                         return -ENOSPC;
 321         }
 322         *id = rv;
 323         return 0;
 324 }
 325 EXPORT_SYMBOL(idr_get_new);
 326
 327 static void idr_remove_warning(int id)
 328 {
 329         printk("idr_remove called for id=%d which is not allocated.\n", id);
 330         dump_stack();
 331 }
 332
 333 static void sub_remove(struct idr *idp, int shift, int id)
 334 {
 335         struct idr_layer *p = idp->top;
 336         struct idr_layer **pa[MAX_LEVEL];
 337         struct idr_layer ***paa = &pa[0];
 338         int n;
 339
 340         *paa = NULL;
 341         *++paa = &idp->top;
 342
 343         while ((shift > 0) && p) {
 344                 n = (id >> shift) & IDR_MASK;
 345                 __clear_bit(n, &p->bitmap);
 346                 *++paa = &p->ary[n];
 347                 p = p->ary[n];
 348                 shift -= IDR_BITS;
 349         }
 350         n = id & IDR_MASK;
 351         if (likely(p != NULL && test_bit(n, &p->bitmap))){
 352                 __clear_bit(n, &p->bitmap);
 353                 p->ary[n] = NULL;
 354                 while(*paa && ! --((**paa)->count)){
 355                         move_to_free_list(idp, **paa);
 356                         **paa-- = NULL;
 357                 }
 358                 if (!*paa)
 359                         idp->layers = 0;
 360         } else
 361                 idr_remove_warning(id);
 362 }
 363
 364 /**
 365  * idr_remove - remove the given id and free it's slot
 366  * @idp: idr handle
 367  * @id: unique key
 368  */
 369 void idr_remove(struct idr *idp, int id)
 370 {
 371         struct idr_layer *p;
 372
 373         /* Mask off upper bits we don't use for the search. */
 374         id &= MAX_ID_MASK;
 375
 376         sub_remove(idp, (idp->layers - 1) * IDR_BITS, id);
 377         if (idp->top && idp->top->count == 1 && (idp->layers > 1) &&
 378             idp->top->ary[0]) {  // We can drop a layer
 379
 380                 p = idp->top->ary[0];
 381                 idp->top->bitmap = idp->top->count = 0;
 382                 move_to_free_list(idp, idp->top);
 383                 idp->top = p;
 384                 --idp->layers;
 385         }
 386         while (idp->id_free_cnt >= IDR_FREE_MAX) {
 387                 p = get_from_free_list(idp);
 388                 kmem_cache_free(idr_layer_cache, p);
 389         }
 390         return;
 391 }
 392 EXPORT_SYMBOL(idr_remove);
 393
 394 /**
 395  * idr_remove_all - remove all ids from the given idr tree
 396  * @idp: idr handle
 397  *
 398  * idr_destroy() only frees up unused, cached idp_layers, but this
 399  * function will remove all id mappings and leave all idp_layers
 400  * unused.
 401  *
 402  * A typical clean-up sequence for objects stored in an idr tree, will
 403  * use idr_for_each() to free all objects, if necessay, then
 404  * idr_remove_all() to remove all ids, and idr_destroy() to free
 405  * up the cached idr_layers.
 406  */
 407 void idr_remove_all(struct idr *idp)
 408 {
 409         int n, id, max;
 410         struct idr_layer *p;
 411         struct idr_layer *pa[MAX_LEVEL];
 412         struct idr_layer **paa = &pa[0];
 413
 414         n = idp->layers * IDR_BITS;
 415         p = idp->top;
 416         max = 1 << n;
 417
 418         id = 0;
 419         while (id < max) {
 420                 while (n > IDR_BITS && p) {
 421                         n -= IDR_BITS;
 422                         *paa++ = p;
 423                         p = p->ary[(id >> n) & IDR_MASK];
 424                 }
 425
 426                 id += 1 << n;
 427                 while (n < fls(id)) {
 428                         if (p) {
 429                                 memset(p, 0, sizeof *p);
 430                                 move_to_free_list(idp, p);
 431                         }
 432                         n += IDR_BITS;
 433                         p = *--paa;
 434                 }
 435         }
 436         idp->top = NULL;
 437         idp->layers = 0;
 438 }
 439 EXPORT_SYMBOL(idr_remove_all);
 440
 441 /**
 442  * idr_destroy - release all cached layers within an idr tree
 443  * idp: idr handle
 444  */
 445 void idr_destroy(struct idr *idp)
 446 {
 447         while (idp->id_free_cnt) {
 448                 struct idr_layer *p = get_from_free_list(idp);
 449                 kmem_cache_free(idr_layer_cache, p);
 450         }
 451 }
 452 EXPORT_SYMBOL(idr_destroy);
 453
 454 /**
 455  * idr_find - return pointer for given id
 456  * @idp: idr handle
 457  * @id: lookup key
 458  *
 459  * Return the pointer given the id it has been registered with.  A %NULL
 460  * return indicates that @id is not valid or you passed %NULL in
 461  * idr_get_new().
 462  *
 463  * The caller must serialize idr_find() vs idr_get_new() and idr_remove().
 464  */
 465 void *idr_find(struct idr *idp, int id)
 466 {
 467         int n;
 468         struct idr_layer *p;
 469
 470         n = idp->layers * IDR_BITS;
 471         p = idp->top;
 472
 473         /* Mask off upper bits we don't use for the search. */
 474         id &= MAX_ID_MASK;
 475
 476         if (id >= (1 << n))
 477                 return NULL;
 478
 479         while (n > 0 && p) {
 480                 n -= IDR_BITS;
 481                 p = p->ary[(id >> n) & IDR_MASK];
 482         }
 483         return((void *)p);
 484 }
 485 EXPORT_SYMBOL(idr_find);
 486
 487 /**
 488  * idr_for_each - iterate through all stored pointers
 489  * @idp: idr handle
 490  * @fn: function to be called for each pointer
 491  * @data: data passed back to callback function
 492  *
 493  * Iterate over the pointers registered with the given idr.  The
 494  * callback function will be called for each pointer currently
 495  * registered, passing the id, the pointer and the data pointer passed
 496  * to this function.  It is not safe to modify the idr tree while in
 497  * the callback, so functions such as idr_get_new and idr_remove are
 498  * not allowed.
 499  *
 500  * We check the return of @fn each time. If it returns anything other
 501  * than 0, we break out and return that value.
 502  *
 503  * The caller must serialize idr_for_each() vs idr_get_new() and idr_remove().
 504  */
 505 int idr_for_each(struct idr *idp,
 506                  int (*fn)(int id, void *p, void *data), void *data)
 507 {
 508         int n, id, max, error = 0;
 509         struct idr_layer *p;
 510         struct idr_layer *pa[MAX_LEVEL];
 511         struct idr_layer **paa = &pa[0];
 512
 513         n = idp->layers * IDR_BITS;
 514         p = idp->top;
 515         max = 1 << n;
 516
 517         id = 0;
 518         while (id < max) {
 519                 while (n > 0 && p) {
 520                         n -= IDR_BITS;
 521                         *paa++ = p;
 522                         p = p->ary[(id >> n) & IDR_MASK];
 523                 }
 524
 525                 if (p) {
 526                         error = fn(id, (void *)p, data);
 527                         if (error)
 528                                 break;
 529                 }
 530
 531                 id += 1 << n;
 532                 while (n < fls(id)) {
 533                         n += IDR_BITS;
 534                         p = *--paa;
 535                 }
 536         }
 537
 538         return error;
 539 }
 540 EXPORT_SYMBOL(idr_for_each);
 541
 542 /**
 543  * idr_replace - replace pointer for given id
 544  * @idp: idr handle
 545  * @ptr: pointer you want associated with the id
 546  * @id: lookup key
 547  *
 548  * Replace the pointer registered with an id and return the old value.
 549  * A -ENOENT return indicates that @id was not found.
 550  * A -EINVAL return indicates that @id was not within valid constraints.
 551  *
 552  * The caller must serialize vs idr_find(), idr_get_new(), and idr_remove().
 553  */
 554 void *idr_replace(struct idr *idp, void *ptr, int id)
 555 {
 556         int n;
 557         struct idr_layer *p, *old_p;
 558
 559         n = idp->layers * IDR_BITS;
 560         p = idp->top;
 561
 562         id &= MAX_ID_MASK;
 563
 564         if (id >= (1 << n))
 565                 return ERR_PTR(-EINVAL);
 566
 567         n -= IDR_BITS;
 568         while ((n > 0) && p) {
 569                 p = p->ary[(id >> n) & IDR_MASK];
 570                 n -= IDR_BITS;
 571         }
 572
 573         n = id & IDR_MASK;
 574         if (unlikely(p == NULL || !test_bit(n, &p->bitmap)))
 575                 return ERR_PTR(-ENOENT);
 576
 577         old_p = p->ary[n];
 578         p->ary[n] = ptr;
 579
 580         return old_p;
 581 }
 582 EXPORT_SYMBOL(idr_replace);
 583
 584 static void idr_cache_ctor(struct kmem_cache *idr_layer_cache, void *idr_layer)
 585 {
 586         memset(idr_layer, 0, sizeof(struct idr_layer));
 587 }
 588
 589 void __init idr_init_cache(void)
 590 {
 591         idr_layer_cache = kmem_cache_create("idr_layer_cache",
 592                                 sizeof(struct idr_layer), 0, SLAB_PANIC,
 593                                 idr_cache_ctor);
 594 }
 595
 596 /**
 597  * idr_init - initialize idr handle
 598  * @idp:        idr handle
 599  *
 600  * This function is use to set up the handle (@idp) that you will pass
 601  * to the rest of the functions.
 602  */
 603 void idr_init(struct idr *idp)
 604 {
 605         memset(idp, 0, sizeof(struct idr));
 606         spin_lock_init(&idp->lock);
 607 }
 608 EXPORT_SYMBOL(idr_init);
 609
 610
 611 /*
 612  * IDA - IDR based ID allocator
 613  *
 614  * this is id allocator without id -> pointer translation.  Memory
 615  * usage is much lower than full blown idr because each id only
 616  * occupies a bit.  ida uses a custom leaf node which contains
 617  * IDA_BITMAP_BITS slots.
 618  *
 619  * 2007-04-25  written by Tejun Heo <htejun@gmail.com>
 620  */
 621
 622 static void free_bitmap(struct ida *ida, struct ida_bitmap *bitmap)
 623 {
 624         unsigned long flags;
 625
 626         if (!ida->free_bitmap) {
 627                 spin_lock_irqsave(&ida->idr.lock, flags);
 628                 if (!ida->free_bitmap) {
 629                         ida->free_bitmap = bitmap;
 630                         bitmap = NULL;
 631                 }
 632                 spin_unlock_irqrestore(&ida->idr.lock, flags);
 633         }
 634
 635         kfree(bitmap);
 636 }
 637
 638 /**
 639  * ida_pre_get - reserve resources for ida allocation
 640  * @ida:        ida handle
 641  * @gfp_mask:   memory allocation flag
 642  *
 643  * This function should be called prior to locking and calling the
 644  * following function.  It preallocates enough memory to satisfy the
 645  * worst possible allocation.
 646  *
 647  * If the system is REALLY out of memory this function returns 0,
 648  * otherwise 1.
 649  */
 650 int ida_pre_get(struct ida *ida, gfp_t gfp_mask)
 651 {
 652         /* allocate idr_layers */
 653         if (!idr_pre_get(&ida->idr, gfp_mask))
 654                 return 0;
 655
 656         /* allocate free_bitmap */
 657         if (!ida->free_bitmap) {
 658                 struct ida_bitmap *bitmap;
 659
 660                 bitmap = kmalloc(sizeof(struct ida_bitmap), gfp_mask);
 661                 if (!bitmap)
 662                         return 0;
 663
 664                 free_bitmap(ida, bitmap);
 665         }
 666
 667         return 1;
 668 }
 669 EXPORT_SYMBOL(ida_pre_get);
 670
 671 /**
 672  * ida_get_new_above - allocate new ID above or equal to a start id
 673  * @ida:        ida handle
 674  * @staring_id: id to start search at
 675  * @p_id:       pointer to the allocated handle
 676  *
 677  * Allocate new ID above or equal to @ida.  It should be called with
 678  * any required locks.
 679  *
 680  * If memory is required, it will return -EAGAIN, you should unlock
 681  * and go back to the ida_pre_get() call.  If the ida is full, it will
 682  * return -ENOSPC.
 683  *
 684  * @p_id returns a value in the range 0 ... 0x7fffffff.
 685  */
 686 int ida_get_new_above(struct ida *ida, int starting_id, int *p_id)
 687 {
 688         struct idr_layer *pa[MAX_LEVEL];
 689         struct ida_bitmap *bitmap;
 690         unsigned long flags;
 691         int idr_id = starting_id / IDA_BITMAP_BITS;
 692         int offset = starting_id % IDA_BITMAP_BITS;
 693         int t, id;
 694
 695  restart:
 696         /* get vacant slot */
 697         t = idr_get_empty_slot(&ida->idr, idr_id, pa);
 698         if (t < 0) {
 699                 if (t == -1)
 700                         return -EAGAIN;
 701                 else /* will be -3 */
 702                         return -ENOSPC;
 703         }
 704
 705         if (t * IDA_BITMAP_BITS >= MAX_ID_BIT)
 706                 return -ENOSPC;
 707
 708         if (t != idr_id)
 709                 offset = 0;
 710         idr_id = t;
 711
 712         /* if bitmap isn't there, create a new one */
 713         bitmap = (void *)pa[0]->ary[idr_id & IDR_MASK];
 714         if (!bitmap) {
 715                 spin_lock_irqsave(&ida->idr.lock, flags);
 716                 bitmap = ida->free_bitmap;
 717                 ida->free_bitmap = NULL;
 718                 spin_unlock_irqrestore(&ida->idr.lock, flags);
 719
 720                 if (!bitmap)
 721                         return -EAGAIN;
 722
 723                 memset(bitmap, 0, sizeof(struct ida_bitmap));
 724                 pa[0]->ary[idr_id & IDR_MASK] = (void *)bitmap;
 725                 pa[0]->count++;
 726         }
 727
 728         /* lookup for empty slot */
 729         t = find_next_zero_bit(bitmap->bitmap, IDA_BITMAP_BITS, offset);
 730         if (t == IDA_BITMAP_BITS) {
 731                 /* no empty slot after offset, continue to the next chunk */
 732                 idr_id++;
 733                 offset = 0;
 734                 goto restart;
 735         }
 736
 737         id = idr_id * IDA_BITMAP_BITS + t;
 738         if (id >= MAX_ID_BIT)
 739                 return -ENOSPC;
 740
 741         __set_bit(t, bitmap->bitmap);
 742         if (++bitmap->nr_busy == IDA_BITMAP_BITS)
 743                 idr_mark_full(pa, idr_id);
 744
 745         *p_id = id;
 746
 747         /* Each leaf node can handle nearly a thousand slots and the
 748          * whole idea of ida is to have small memory foot print.
 749          * Throw away extra resources one by one after each successful
 750          * allocation.
 751          */
 752         if (ida->idr.id_free_cnt || ida->free_bitmap) {
 753                 struct idr_layer *p = get_from_free_list(&ida->idr);
 754                 if (p)
 755                         kmem_cache_free(idr_layer_cache, p);
 756         }
 757
 758         return 0;
 759 }
 760 EXPORT_SYMBOL(ida_get_new_above);
 761
 762 /**
 763  * ida_get_new - allocate new ID
 764  * @ida:        idr handle
 765  * @p_id:       pointer to the allocated handle
 766  *
 767  * Allocate new ID.  It should be called with any required locks.
 768  *
 769  * If memory is required, it will return -EAGAIN, you should unlock
 770  * and go back to the idr_pre_get() call.  If the idr is full, it will
 771  * return -ENOSPC.
 772  *
 773  * @id returns a value in the range 0 ... 0x7fffffff.
 774  */
 775 int ida_get_new(struct ida *ida, int *p_id)
 776 {
 777         return ida_get_new_above(ida, 0, p_id);
 778 }
 779 EXPORT_SYMBOL(ida_get_new);
 780
 781 /**
 782  * ida_remove - remove the given ID
 783  * @ida:        ida handle
 784  * @id:         ID to free
 785  */
 786 void ida_remove(struct ida *ida, int id)
 787 {
 788         struct idr_layer *p = ida->idr.top;
 789         int shift = (ida->idr.layers - 1) * IDR_BITS;
 790         int idr_id = id / IDA_BITMAP_BITS;
 791         int offset = id % IDA_BITMAP_BITS;
 792         int n;
 793         struct ida_bitmap *bitmap;
 794
 795         /* clear full bits while looking up the leaf idr_layer */
 796         while ((shift > 0) && p) {
 797                 n = (idr_id >> shift) & IDR_MASK;
 798                 __clear_bit(n, &p->bitmap);
 799                 p = p->ary[n];
 800                 shift -= IDR_BITS;
 801         }
 802
 803         if (p == NULL)
 804                 goto err;
 805
 806         n = idr_id & IDR_MASK;
 807         __clear_bit(n, &p->bitmap);
 808
 809         bitmap = (void *)p->ary[n];
 810         if (!test_bit(offset, bitmap->bitmap))
 811                 goto err;
 812
 813         /* update bitmap and remove it if empty */
 814         __clear_bit(offset, bitmap->bitmap);
 815         if (--bitmap->nr_busy == 0) {
 816                 __set_bit(n, &p->bitmap);       /* to please idr_remove() */
 817                 idr_remove(&ida->idr, idr_id);
 818                 free_bitmap(ida, bitmap);
 819         }
 820
 821         return;
 822
 823  err:
 824         printk(KERN_WARNING
 825                "ida_remove called for id=%d which is not allocated.\n", id);
 826 }
 827 EXPORT_SYMBOL(ida_remove);
 828
 829 /**
 830  * ida_destroy - release all cached layers within an ida tree
 831  * ida:         ida handle
 832  */
 833 void ida_destroy(struct ida *ida)
 834 {
 835         idr_destroy(&ida->idr);
 836         kfree(ida->free_bitmap);
 837 }
 838 EXPORT_SYMBOL(ida_destroy);
 839
 840 /**
 841  * ida_init - initialize ida handle
 842  * @ida:        ida handle
 843  *
 844  * This function is use to set up the handle (@ida) that you will pass
 845  * to the rest of the functions.
 846  */
 847 void ida_init(struct ida *ida)
 848 {
 849         memset(ida, 0, sizeof(struct ida));
 850         idr_init(&ida->idr);
 851
 852 }
 853 EXPORT_SYMBOL(ida_init);