lib/idr.c

   1 /*
   2  * linux/kernel/id.c
   3  *
   4  * 2002-10-18  written by Jim Houston jim.houston@ccur.com
   5  *      Copyright (C) 2002 by Concurrent Computer Corporation
   6  *      Distributed under the GNU GPL license version 2.
   7  *
   8  * Small id to pointer translation service.
   9  *
  10  * It uses a radix tree like structure as a sparse array indexed
  11  * by the id to obtain the pointer.  The bitmap makes allocating
  12  * a new id quick.
  13
  14  * Modified by George Anzinger to reuse immediately and to use
  15  * find bit instructions.  Also removed _irq on spinlocks.
  16
  17  * So here is what this bit of code does:
  18
  19  * You call it to allocate an id (an int) an associate with that id a
  20  * pointer or what ever, we treat it as a (void *).  You can pass this
  21  * id to a user for him to pass back at a later time.  You then pass
  22  * that id to this code and it returns your pointer.
  23
  24  * You can release ids at any time. When all ids are released, most of
  25  * the memory is returned (we keep IDR_FREE_MAX) in a local pool so we
  26  * don't need to go to the memory "store" during an id allocate, just
  27  * so you don't need to be too concerned about locking and conflicts
  28  * with the slab allocator.
  29
  30  * What you need to do is, since we don't keep the counter as part of
  31  * id / ptr pair, to keep a copy of it in the pointed to structure
  32  * (or else where) so that when you ask for a ptr you can varify that
  33  * the returned ptr is correct by comparing the id it contains with the one
  34  * you asked for.  In other words, we only did half the reuse protection.
  35  * Since the code depends on your code doing this check, we ignore high
  36  * order bits in the id, not just the count, but bits that would, if used,
  37  * index outside of the allocated ids.  In other words, if the largest id
  38  * currently allocated is 32 a look up will only look at the low 5 bits of
  39  * the id.  Since you will want to keep this id in the structure anyway
  40  * (if for no other reason than to be able to eliminate the id when the
  41  * structure is found in some other way) this seems reasonable.  If you
  42  * really think otherwise, the code to check these bits here, it is just
  43  * disabled with a #if 0.
  44
  45
  46  * So here are the complete details:
  47
  48  *  include <linux/idr.h>
  49
  50  * void idr_init(struct idr *idp)
  51
  52  *   This function is use to set up the handle (idp) that you will pass
  53  *   to the rest of the functions.  The structure is defined in the
  54  *   header.
  55
  56  * int idr_pre_get(struct idr *idp, unsigned gfp_mask)
  57
  58  *   This function should be called prior to locking and calling the
  59  *   following function.  It pre allocates enough memory to satisfy the
  60  *   worst possible allocation.  Unless gfp_mask is GFP_ATOMIC, it can
  61  *   sleep, so must not be called with any spinlocks held.  If the system is
  62  *   REALLY out of memory this function returns 0, other wise 1.
  63
  64  * int idr_get_new(struct idr *idp, void *ptr, int *id);
  65
  66  *   This is the allocate id function.  It should be called with any
  67  *   required locks.  In fact, in the SMP case, you MUST lock prior to
  68  *   calling this function to avoid possible out of memory problems.
  69  *   If memory is required, it will return -EAGAIN, you should unlock
  70  *   and go back to the idr_pre_get() call.  If the idr is full, it
  71  *   will return a -ENOSPC.  ptr is the pointer you want associated
  72  *   with the id.  The value is returned in the "id" field.  idr_get_new()
  73  *   returns a value in the range 0 ... 0x7fffffff
  74
  75  * int idr_get_new_above(struct idr *idp, void *ptr, int start_id, int *id);
  76
  77  *   Like idr_get_new(), but the returned id is guaranteed to be at or
  78  *   above start_id.
  79
  80  * void *idr_find(struct idr *idp, int id);
  81
  82  *   returns the "ptr", given the id.  A NULL return indicates that the
  83  *   id is not valid (or you passed NULL in the idr_get_new(), shame on
  84  *   you).  This function must be called with a spinlock that prevents
  85  *   calling either idr_get_new() or idr_remove() or idr_find() while it
  86  *   is working.
  87
  88  * void idr_remove(struct idr *idp, int id);
  89
  90  *   removes the given id, freeing that slot and any memory that may
  91  *   now be unused.  See idr_find() for locking restrictions.
  92
  93  * int idr_full(struct idr *idp);
  94
  95  *   Returns true if the idr is full and false if not.
  96
  97  */
  98
  99
 100
 101 #ifndef TEST                        // to test in user space...
 102 #include <linux/slab.h>
 103 #include <linux/init.h>
 104 #include <linux/module.h>
 105 #endif
 106 #include <linux/string.h>
 107 #include <linux/idr.h>
 108
 109
 110 static kmem_cache_t *idr_layer_cache;
 111
 112
 113
 114 static struct idr_layer *alloc_layer(struct idr *idp)
 115 {
 116         struct idr_layer *p;
 117
 118         spin_lock(&idp->lock);
 119         if (!(p = idp->id_free))
 120                 return NULL;
 121         idp->id_free = p->ary[0];
 122         idp->id_free_cnt--;
 123         p->ary[0] = NULL;
 124         spin_unlock(&idp->lock);
 125         return(p);
 126 }
 127
 128 static void free_layer(struct idr *idp, struct idr_layer *p)
 129 {
 130         /*
 131          * Depends on the return element being zeroed.
 132          */
 133         spin_lock(&idp->lock);
 134         p->ary[0] = idp->id_free;
 135         idp->id_free = p;
 136         idp->id_free_cnt++;
 137         spin_unlock(&idp->lock);
 138 }
 139
 140 int idr_pre_get(struct idr *idp, unsigned gfp_mask)
 141 {
 142         while (idp->id_free_cnt < IDR_FREE_MAX) {
 143                 struct idr_layer *new;
 144                 new = kmem_cache_alloc(idr_layer_cache, gfp_mask);
 145                 if(new == NULL)
 146                         return (0);
 147                 free_layer(idp, new);
 148         }
 149         return 1;
 150 }
 151 EXPORT_SYMBOL(idr_pre_get);
 152
 153 static int sub_alloc(struct idr *idp, void *ptr, int *starting_id)
 154 {
 155         int n, m, sh;
 156         struct idr_layer *p, *new;
 157         struct idr_layer *pa[MAX_LEVEL];
 158         int l, id;
 159         long bm;
 160
 161         id = *starting_id;
 162         p = idp->top;
 163         l = idp->layers;
 164         pa[l--] = NULL;
 165         while (1) {
 166                 /*
 167                  * We run around this while until we reach the leaf node...
 168                  */
 169                 n = (id >> (IDR_BITS*l)) & IDR_MASK;
 170                 bm = ~p->bitmap;
 171                 m = find_next_bit(&bm, IDR_SIZE, n);
 172                 if (m == IDR_SIZE) {
 173                         /* no space available go back to previous layer. */
 174                         l++;
 175                         id = (id | ((1 << (IDR_BITS*l))-1)) + 1;
 176                         if (!(p = pa[l])) {
 177                                 *starting_id = id;
 178                                 return -2;
 179                         }
 180                         continue;
 181                 }
 182                 if (m != n) {
 183                         sh = IDR_BITS*l;
 184                         id = ((id >> sh) ^ n ^ m) << sh;
 185                 }
 186                 if ((id >= MAX_ID_BIT) || (id < 0))
 187                         return -3;
 188                 if (l == 0)
 189                         break;
 190                 /*
 191                  * Create the layer below if it is missing.
 192                  */
 193                 if (!p->ary[m]) {
 194                         if (!(new = alloc_layer(idp)))
 195                                 return -1;
 196                         p->ary[m] = new;
 197                         p->count++;
 198                 }
 199                 pa[l--] = p;
 200                 p = p->ary[m];
 201         }
 202         /*
 203          * We have reached the leaf node, plant the
 204          * users pointer and return the raw id.
 205          */
 206         p->ary[m] = (struct idr_layer *)ptr;
 207         __set_bit(m, &p->bitmap);
 208         p->count++;
 209         /*
 210          * If this layer is full mark the bit in the layer above
 211          * to show that this part of the radix tree is full.
 212          * This may complete the layer above and require walking
 213          * up the radix tree.
 214          */
 215         n = id;
 216         while (p->bitmap == IDR_FULL) {
 217                 if (!(p = pa[++l]))
 218                         break;
 219                 n = n >> IDR_BITS;
 220                 __set_bit((n & IDR_MASK), &p->bitmap);
 221         }
 222         return(id);
 223 }
 224
 225 static int idr_get_new_above_int(struct idr *idp, void *ptr, int starting_id)
 226 {
 227         struct idr_layer *p, *new;
 228         int layers, v, id;
 229
 230         id = starting_id;
 231 build_up:
 232         p = idp->top;
 233         layers = idp->layers;
 234         if (unlikely(!p)) {
 235                 if (!(p = alloc_layer(idp)))
 236                         return -1;
 237                 layers = 1;
 238         }
 239         /*
 240          * Add a new layer to the top of the tree if the requested
 241          * id is larger than the currently allocated space.
 242          */
 243         while ((layers < MAX_LEVEL) && (id >= (1 << (layers*IDR_BITS)))) {
 244                 layers++;
 245                 if (!p->count)
 246                         continue;
 247                 if (!(new = alloc_layer(idp))) {
 248                         /*
 249                          * The allocation failed.  If we built part of
 250                          * the structure tear it down.
 251                          */
 252                         for (new = p; p && p != idp->top; new = p) {
 253                                 p = p->ary[0];
 254                                 new->ary[0] = NULL;
 255                                 new->bitmap = new->count = 0;
 256                                 free_layer(idp, new);
 257                         }
 258                         return -1;
 259                 }
 260                 new->ary[0] = p;
 261                 new->count = 1;
 262                 if (p->bitmap == IDR_FULL)
 263                         __set_bit(0, &new->bitmap);
 264                 p = new;
 265         }
 266         idp->top = p;
 267         idp->layers = layers;
 268         v = sub_alloc(idp, ptr, &id);
 269         if (v == -2)
 270                 goto build_up;
 271         return(v);
 272 }
 273
 274 int idr_get_new_above(struct idr *idp, void *ptr, int starting_id, int *id)
 275 {
 276         int rv;
 277         rv = idr_get_new_above_int(idp, ptr, starting_id);
 278         /*
 279          * This is a cheap hack until the IDR code can be fixed to
 280          * return proper error values.
 281          */
 282         if (rv < 0) {
 283                 if (rv == -1)
 284                         return -EAGAIN;
 285                 else /* Will be -3 */
 286                         return -ENOSPC;
 287         }
 288         *id = rv;
 289         return 0;
 290 }
 291 EXPORT_SYMBOL(idr_get_new_above);
 292
 293 int idr_get_new(struct idr *idp, void *ptr, int *id)
 294 {
 295         int rv;
 296         rv = idr_get_new_above_int(idp, ptr, 0);
 297         /*
 298          * This is a cheap hack until the IDR code can be fixed to
 299          * return proper error values.
 300          */
 301         if (rv < 0) {
 302                 if (rv == -1)
 303                         return -EAGAIN;
 304                 else /* Will be -3 */
 305                         return -ENOSPC;
 306         }
 307         *id = rv;
 308         return 0;
 309 }
 310 EXPORT_SYMBOL(idr_get_new);
 311
 312 static void sub_remove(struct idr *idp, int shift, int id)
 313 {
 314         struct idr_layer *p = idp->top;
 315         struct idr_layer **pa[MAX_LEVEL];
 316         struct idr_layer ***paa = &pa[0];
 317
 318         *paa = NULL;
 319         *++paa = &idp->top;
 320
 321         while ((shift > 0) && p) {
 322                 int n = (id >> shift) & IDR_MASK;
 323                 __clear_bit(n, &p->bitmap);
 324                 *++paa = &p->ary[n];
 325                 p = p->ary[n];
 326                 shift -= IDR_BITS;
 327         }
 328         if (likely(p != NULL)){
 329                 int n = id & IDR_MASK;
 330                 __clear_bit(n, &p->bitmap);
 331                 p->ary[n] = NULL;
 332                 while(*paa && ! --((**paa)->count)){
 333                         free_layer(idp, **paa);
 334                         **paa-- = NULL;
 335                 }
 336                 if ( ! *paa )
 337                         idp->layers = 0;
 338         }
 339 }
 340
 341 void idr_remove(struct idr *idp, int id)
 342 {
 343         struct idr_layer *p;
 344
 345         /* Mask off upper bits we don't use for the search. */
 346         id &= MAX_ID_MASK;
 347
 348         sub_remove(idp, (idp->layers - 1) * IDR_BITS, id);
 349         if ( idp->top && idp->top->count == 1 &&
 350              (idp->layers > 1) &&
 351              idp->top->ary[0]){  // We can drop a layer
 352
 353                 p = idp->top->ary[0];
 354                 idp->top->bitmap = idp->top->count = 0;
 355                 free_layer(idp, idp->top);
 356                 idp->top = p;
 357                 --idp->layers;
 358         }
 359         while (idp->id_free_cnt >= IDR_FREE_MAX) {
 360
 361                 p = alloc_layer(idp);
 362                 kmem_cache_free(idr_layer_cache, p);
 363                 return;
 364         }
 365 }
 366 EXPORT_SYMBOL(idr_remove);
 367
 368 void *idr_find(struct idr *idp, int id)
 369 {
 370         int n;
 371         struct idr_layer *p;
 372
 373         n = idp->layers * IDR_BITS;
 374         p = idp->top;
 375 #if 0
 376         /*
 377          * This tests to see if bits outside the current tree are
 378          * present.  If so, tain't one of ours!
 379          */
 380         if ( unlikely( (id & ~(~0 << MAX_ID_SHIFT)) >> (n + IDR_BITS)))
 381              return NULL;
 382 #endif
 383         /* Mask off upper bits we don't use for the search. */
 384         id &= MAX_ID_MASK;
 385
 386         while (n > 0 && p) {
 387                 n -= IDR_BITS;
 388                 p = p->ary[(id >> n) & IDR_MASK];
 389         }
 390         return((void *)p);
 391 }
 392 EXPORT_SYMBOL(idr_find);
 393
 394 static void idr_cache_ctor(void * idr_layer,
 395                            kmem_cache_t *idr_layer_cache, unsigned long flags)
 396 {
 397         memset(idr_layer, 0, sizeof(struct idr_layer));
 398 }
 399
 400 static  int init_id_cache(void)
 401 {
 402         if (!idr_layer_cache)
 403                 idr_layer_cache = kmem_cache_create("idr_layer_cache",
 404                         sizeof(struct idr_layer), 0, 0, idr_cache_ctor, NULL);
 405         return 0;
 406 }
 407
 408 void idr_init(struct idr *idp)
 409 {
 410         init_id_cache();
 411         memset(idp, 0, sizeof(struct idr));
 412         spin_lock_init(&idp->lock);
 413 }
 414 EXPORT_SYMBOL(idr_init);
 415