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