linux/lib/idr.c
<<
>>
Prefs
   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
lxr.linux.no kindly hosted by Redpill Linpro AS, provider of Linux consulting and operations services since 1995.