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/string.h>
  33 #include <linux/idr.h>
  34
  35 static kmem_cache_t *idr_layer_cache;
  36
  37 static struct idr_layer *alloc_layer(struct idr *idp)
  38 {
  39         struct idr_layer *p;
  40         unsigned long flags;
  41
  42         spin_lock_irqsave(&idp->lock, flags);
  43         if ((p = idp->id_free)) {
  44                 idp->id_free = p->ary[0];
  45                 idp->id_free_cnt--;
  46                 p->ary[0] = NULL;
  47         }
  48         spin_unlock_irqrestore(&idp->lock, flags);
  49         return(p);
  50 }
  51
  52 /* only called when idp->lock is held */
  53 static void __free_layer(struct idr *idp, struct idr_layer *p)
  54 {
  55         p->ary[0] = idp->id_free;
  56         idp->id_free = p;
  57         idp->id_free_cnt++;
  58 }
  59
  60 static void free_layer(struct idr *idp, struct idr_layer *p)
  61 {
  62         unsigned long flags;
  63
  64         /*
  65          * Depends on the return element being zeroed.
  66          */
  67         spin_lock_irqsave(&idp->lock, flags);
  68         __free_layer(idp, p);
  69         spin_unlock_irqrestore(&idp->lock, flags);
  70 }
  71
  72 /**
  73  * idr_pre_get - reserver resources for idr allocation
  74  * @idp:        idr handle
  75  * @gfp_mask:   memory allocation flags
  76  *
  77  * This function should be called prior to locking and calling the
  78  * following function.  It preallocates enough memory to satisfy
  79  * the worst possible allocation.
  80  *
  81  * If the system is REALLY out of memory this function returns 0,
  82  * otherwise 1.
  83  */
  84 int idr_pre_get(struct idr *idp, gfp_t gfp_mask)
  85 {
  86         while (idp->id_free_cnt < IDR_FREE_MAX) {
  87                 struct idr_layer *new;
  88                 new = kmem_cache_alloc(idr_layer_cache, gfp_mask);
  89                 if (new == NULL)
  90                         return (0);
  91                 free_layer(idp, new);
  92         }
  93         return 1;
  94 }
  95 EXPORT_SYMBOL(idr_pre_get);
  96
  97 static int sub_alloc(struct idr *idp, void *ptr, int *starting_id)
  98 {
  99         int n, m, sh;
 100         struct idr_layer *p, *new;
 101         struct idr_layer *pa[MAX_LEVEL];
 102         int l, id;
 103         long bm;
 104
 105         id = *starting_id;
 106         p = idp->top;
 107         l = idp->layers;
 108         pa[l--] = NULL;
 109         while (1) {
 110                 /*
 111                  * We run around this while until we reach the leaf node...
 112                  */
 113                 n = (id >> (IDR_BITS*l)) & IDR_MASK;
 114                 bm = ~p->bitmap;
 115                 m = find_next_bit(&bm, IDR_SIZE, n);
 116                 if (m == IDR_SIZE) {
 117                         /* no space available go back to previous layer. */
 118                         l++;
 119                         id = (id | ((1 << (IDR_BITS * l)) - 1)) + 1;
 120                         if (!(p = pa[l])) {
 121                                 *starting_id = id;
 122                                 return -2;
 123                         }
 124                         continue;
 125                 }
 126                 if (m != n) {
 127                         sh = IDR_BITS*l;
 128                         id = ((id >> sh) ^ n ^ m) << sh;
 129                 }
 130                 if ((id >= MAX_ID_BIT) || (id < 0))
 131                         return -3;
 132                 if (l == 0)
 133                         break;
 134                 /*
 135                  * Create the layer below if it is missing.
 136                  */
 137                 if (!p->ary[m]) {
 138                         if (!(new = alloc_layer(idp)))
 139                                 return -1;
 140                         p->ary[m] = new;
 141                         p->count++;
 142                 }
 143                 pa[l--] = p;
 144                 p = p->ary[m];
 145         }
 146         /*
 147          * We have reached the leaf node, plant the
 148          * users pointer and return the raw id.
 149          */
 150         p->ary[m] = (struct idr_layer *)ptr;
 151         __set_bit(m, &p->bitmap);
 152         p->count++;
 153         /*
 154          * If this layer is full mark the bit in the layer above
 155          * to show that this part of the radix tree is full.
 156          * This may complete the layer above and require walking
 157          * up the radix tree.
 158          */
 159         n = id;
 160         while (p->bitmap == IDR_FULL) {
 161                 if (!(p = pa[++l]))
 162                         break;
 163                 n = n >> IDR_BITS;
 164                 __set_bit((n & IDR_MASK), &p->bitmap);
 165         }
 166         return(id);
 167 }
 168
 169 static int idr_get_new_above_int(struct idr *idp, void *ptr, int starting_id)
 170 {
 171         struct idr_layer *p, *new;
 172         int layers, v, id;
 173         unsigned long flags;
 174
 175         id = starting_id;
 176 build_up:
 177         p = idp->top;
 178         layers = idp->layers;
 179         if (unlikely(!p)) {
 180                 if (!(p = alloc_layer(idp)))
 181                         return -1;
 182                 layers = 1;
 183         }
 184         /*
 185          * Add a new layer to the top of the tree if the requested
 186          * id is larger than the currently allocated space.
 187          */
 188         while ((layers < (MAX_LEVEL - 1)) && (id >= (1 << (layers*IDR_BITS)))) {
 189                 layers++;
 190                 if (!p->count)
 191                         continue;
 192                 if (!(new = alloc_layer(idp))) {
 193                         /*
 194                          * The allocation failed.  If we built part of
 195                          * the structure tear it down.
 196                          */
 197                         spin_lock_irqsave(&idp->lock, flags);
 198                         for (new = p; p && p != idp->top; new = p) {
 199                                 p = p->ary[0];
 200                                 new->ary[0] = NULL;
 201                                 new->bitmap = new->count = 0;
 202                                 __free_layer(idp, new);
 203                         }
 204                         spin_unlock_irqrestore(&idp->lock, flags);
 205                         return -1;
 206                 }
 207                 new->ary[0] = p;
 208                 new->count = 1;
 209                 if (p->bitmap == IDR_FULL)
 210                         __set_bit(0, &new->bitmap);
 211                 p = new;
 212         }
 213         idp->top = p;
 214         idp->layers = layers;
 215         v = sub_alloc(idp, ptr, &id);
 216         if (v == -2)
 217                 goto build_up;
 218         return(v);
 219 }
 220
 221 /**
 222  * idr_get_new_above - allocate new idr entry above or equal to a start id
 223  * @idp: idr handle
 224  * @ptr: pointer you want associated with the ide
 225  * @start_id: id to start search at
 226  * @id: pointer to the allocated handle
 227  *
 228  * This is the allocate id function.  It should be called with any
 229  * required locks.
 230  *
 231  * If memory is required, it will return -EAGAIN, you should unlock
 232  * and go back to the idr_pre_get() call.  If the idr is full, it will
 233  * return -ENOSPC.
 234  *
 235  * @id returns a value in the range 0 ... 0x7fffffff
 236  */
 237 int idr_get_new_above(struct idr *idp, void *ptr, int starting_id, int *id)
 238 {
 239         int rv;
 240
 241         rv = idr_get_new_above_int(idp, ptr, starting_id);
 242         /*
 243          * This is a cheap hack until the IDR code can be fixed to
 244          * return proper error values.
 245          */
 246         if (rv < 0) {
 247                 if (rv == -1)
 248                         return -EAGAIN;
 249                 else /* Will be -3 */
 250                         return -ENOSPC;
 251         }
 252         *id = rv;
 253         return 0;
 254 }
 255 EXPORT_SYMBOL(idr_get_new_above);
 256
 257 /**
 258  * idr_get_new - allocate new idr entry
 259  * @idp: idr handle
 260  * @ptr: pointer you want associated with the ide
 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(struct idr *idp, void *ptr, int *id)
 273 {
 274         int rv;
 275
 276         rv = idr_get_new_above_int(idp, ptr, 0);
 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);
 291
 292 static void idr_remove_warning(int id)
 293 {
 294         printk("idr_remove called for id=%d which is not allocated.\n", id);
 295         dump_stack();
 296 }
 297
 298 static void sub_remove(struct idr *idp, int shift, int id)
 299 {
 300         struct idr_layer *p = idp->top;
 301         struct idr_layer **pa[MAX_LEVEL];
 302         struct idr_layer ***paa = &pa[0];
 303         int n;
 304
 305         *paa = NULL;
 306         *++paa = &idp->top;
 307
 308         while ((shift > 0) && p) {
 309                 n = (id >> shift) & IDR_MASK;
 310                 __clear_bit(n, &p->bitmap);
 311                 *++paa = &p->ary[n];
 312                 p = p->ary[n];
 313                 shift -= IDR_BITS;
 314         }
 315         n = id & IDR_MASK;
 316         if (likely(p != NULL && test_bit(n, &p->bitmap))){
 317                 __clear_bit(n, &p->bitmap);
 318                 p->ary[n] = NULL;
 319                 while(*paa && ! --((**paa)->count)){
 320                         free_layer(idp, **paa);
 321                         **paa-- = NULL;
 322                 }
 323                 if (!*paa)
 324                         idp->layers = 0;
 325         } else
 326                 idr_remove_warning(id);
 327 }
 328
 329 /**
 330  * idr_remove - remove the given id and free it's slot
 331  * idp: idr handle
 332  * id: uniqueue key
 333  */
 334 void idr_remove(struct idr *idp, int id)
 335 {
 336         struct idr_layer *p;
 337
 338         /* Mask off upper bits we don't use for the search. */
 339         id &= MAX_ID_MASK;
 340
 341         sub_remove(idp, (idp->layers - 1) * IDR_BITS, id);
 342         if (idp->top && idp->top->count == 1 && (idp->layers > 1) &&
 343             idp->top->ary[0]) {  // We can drop a layer
 344
 345                 p = idp->top->ary[0];
 346                 idp->top->bitmap = idp->top->count = 0;
 347                 free_layer(idp, idp->top);
 348                 idp->top = p;
 349                 --idp->layers;
 350         }
 351         while (idp->id_free_cnt >= IDR_FREE_MAX) {
 352                 p = alloc_layer(idp);
 353                 kmem_cache_free(idr_layer_cache, p);
 354                 return;
 355         }
 356 }
 357 EXPORT_SYMBOL(idr_remove);
 358
 359 /**
 360  * idr_destroy - release all cached layers within an idr tree
 361  * idp: idr handle
 362  */
 363 void idr_destroy(struct idr *idp)
 364 {
 365         while (idp->id_free_cnt) {
 366                 struct idr_layer *p = alloc_layer(idp);
 367                 kmem_cache_free(idr_layer_cache, p);
 368         }
 369 }
 370 EXPORT_SYMBOL(idr_destroy);
 371
 372 /**
 373  * idr_find - return pointer for given id
 374  * @idp: idr handle
 375  * @id: lookup key
 376  *
 377  * Return the pointer given the id it has been registered with.  A %NULL
 378  * return indicates that @id is not valid or you passed %NULL in
 379  * idr_get_new().
 380  *
 381  * The caller must serialize idr_find() vs idr_get_new() and idr_remove().
 382  */
 383 void *idr_find(struct idr *idp, int id)
 384 {
 385         int n;
 386         struct idr_layer *p;
 387
 388         n = idp->layers * IDR_BITS;
 389         p = idp->top;
 390
 391         /* Mask off upper bits we don't use for the search. */
 392         id &= MAX_ID_MASK;
 393
 394         if (id >= (1 << n))
 395                 return NULL;
 396
 397         while (n > 0 && p) {
 398                 n -= IDR_BITS;
 399                 p = p->ary[(id >> n) & IDR_MASK];
 400         }
 401         return((void *)p);
 402 }
 403 EXPORT_SYMBOL(idr_find);
 404
 405 static void idr_cache_ctor(void * idr_layer, kmem_cache_t *idr_layer_cache,
 406                 unsigned long flags)
 407 {
 408         memset(idr_layer, 0, sizeof(struct idr_layer));
 409 }
 410
 411 static  int init_id_cache(void)
 412 {
 413         if (!idr_layer_cache)
 414                 idr_layer_cache = kmem_cache_create("idr_layer_cache",
 415                         sizeof(struct idr_layer), 0, 0, idr_cache_ctor, NULL);
 416         return 0;
 417 }
 418
 419 /**
 420  * idr_init - initialize idr handle
 421  * @idp:        idr handle
 422  *
 423  * This function is use to set up the handle (@idp) that you will pass
 424  * to the rest of the functions.
 425  */
 426 void idr_init(struct idr *idp)
 427 {
 428         init_id_cache();
 429         memset(idp, 0, sizeof(struct idr));
 430         spin_lock_init(&idp->lock);
 431 }
 432 EXPORT_SYMBOL(idr_init);