lib/util/idtree.c

   1 /*
   2    Unix SMB/CIFS implementation.
   3
   4    very efficient functions to manage mapping a id (such as a fnum) to
   5    a pointer. This is used for fnum and search id allocation.
   6
   7    Copyright (C) Andrew Tridgell 2004
   8
   9    This code is derived from lib/idr.c in the 2.6 Linux kernel, which was
  10    written by Jim Houston jim.houston@ccur.com, and is
  11    Copyright (C) 2002 by Concurrent Computer Corporation
  12
  13    This program is free software; you can redistribute it and/or modify
  14    it under the terms of the GNU General Public License as published by
  15    the Free Software Foundation; either version 2 of the License, or
  16    (at your option) any later version.
  17
  18    This program is distributed in the hope that it will be useful,
  19    but WITHOUT ANY WARRANTY; without even the implied warranty of
  20    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  21    GNU General Public License for more details.
  22
  23    You should have received a copy of the GNU General Public License
  24    along with this program.  If not, see <http://www.gnu.org/licenses/>.
  25 */
  26
  27 /*
  28   see the section marked "public interface" below for documentation
  29 */
  30
  31 /**
  32  * @file
  33  */
  34
  35 #include "includes.h"
  36
  37 #define IDR_BITS 5
  38 #define IDR_FULL 0xfffffffful
  39 #if 0 /* unused */
  40 #define TOP_LEVEL_FULL (IDR_FULL >> 30)
  41 #endif
  42 #define IDR_SIZE (1 << IDR_BITS)
  43 #define IDR_MASK ((1 << IDR_BITS)-1)
  44 #define MAX_ID_SHIFT (sizeof(int)*8 - 1)
  45 #define MAX_ID_BIT (1U << MAX_ID_SHIFT)
  46 #define MAX_ID_MASK (MAX_ID_BIT - 1)
  47 #define MAX_LEVEL (MAX_ID_SHIFT + IDR_BITS - 1) / IDR_BITS
  48 #define IDR_FREE_MAX MAX_LEVEL + MAX_LEVEL
  49
  50 #define set_bit(bit, v) (v) |= (1<<(bit))
  51 #define clear_bit(bit, v) (v) &= ~(1<<(bit))
  52 #define test_bit(bit, v) ((v) & (1<<(bit)))
  53
  54 struct idr_layer {
  55         uint32_t                 bitmap;
  56         struct idr_layer        *ary[IDR_SIZE];
  57         int                      count;
  58 };
  59
  60 struct idr_context {
  61         struct idr_layer *top;
  62         struct idr_layer *id_free;
  63         int               layers;
  64         int               id_free_cnt;
  65 };
  66
  67 static struct idr_layer *alloc_layer(struct idr_context *idp)
  68 {
  69         struct idr_layer *p;
  70
  71         if (!(p = idp->id_free))
  72                 return NULL;
  73         idp->id_free = p->ary[0];
  74         idp->id_free_cnt--;
  75         p->ary[0] = NULL;
  76         return p;
  77 }
  78
  79 static int find_next_bit(uint32_t bm, int maxid, int n)
  80 {
  81         while (n<maxid && !test_bit(n, bm)) n++;
  82         return n;
  83 }
  84
  85 static void free_layer(struct idr_context *idp, struct idr_layer *p)
  86 {
  87         p->ary[0] = idp->id_free;
  88         idp->id_free = p;
  89         idp->id_free_cnt++;
  90 }
  91
  92 static int idr_pre_get(struct idr_context *idp)
  93 {
  94         while (idp->id_free_cnt < IDR_FREE_MAX) {
  95                 struct idr_layer *pn = talloc_zero(idp, struct idr_layer);
  96                 if(pn == NULL)
  97                         return (0);
  98                 free_layer(idp, pn);
  99         }
 100         return 1;
 101 }
 102
 103 static int sub_alloc(struct idr_context *idp, void *ptr, int *starting_id)
 104 {
 105         int n, m, sh;
 106         struct idr_layer *p, *pn;
 107         struct idr_layer *pa[MAX_LEVEL];
 108         int l, id, oid;
 109         uint32_t bm;
 110
 111         memset(pa, 0, sizeof(pa));
 112
 113         id = *starting_id;
 114 restart:
 115         p = idp->top;
 116         l = idp->layers;
 117         pa[l--] = NULL;
 118         while (1) {
 119                 /*
 120                  * We run around this while until we reach the leaf node...
 121                  */
 122                 n = (id >> (IDR_BITS*l)) & IDR_MASK;
 123                 bm = ~p->bitmap;
 124                 m = find_next_bit(bm, IDR_SIZE, n);
 125                 if (m == IDR_SIZE) {
 126                         /* no space available go back to previous layer. */
 127                         l++;
 128                         oid = id;
 129                         id = (id | ((1 << (IDR_BITS*l))-1)) + 1;
 130
 131                         /* if already at the top layer, we need to grow */
 132                         if (!(p = pa[l])) {
 133                                 *starting_id = id;
 134                                 return -2;
 135                         }
 136
 137                         /* If we need to go up one layer, continue the
 138                          * loop; otherwise, restart from the top.
 139                          */
 140                         sh = IDR_BITS * (l + 1);
 141                         if (oid >> sh == id >> sh)
 142                         continue;
 143                         else
 144                                 goto restart;
 145                 }
 146                 if (m != n) {
 147                         sh = IDR_BITS*l;
 148                         id = ((id >> sh) ^ n ^ m) << sh;
 149                 }
 150                 if ((id >= MAX_ID_BIT) || (id < 0))
 151                         return -1;
 152                 if (l == 0)
 153                         break;
 154                 /*
 155                  * Create the layer below if it is missing.
 156                  */
 157                 if (!p->ary[m]) {
 158                         if (!(pn = alloc_layer(idp)))
 159                                 return -1;
 160                         p->ary[m] = pn;
 161                         p->count++;
 162                 }
 163                 pa[l--] = p;
 164                 p = p->ary[m];
 165         }
 166         /*
 167          * We have reached the leaf node, plant the
 168          * users pointer and return the raw id.
 169          */
 170         p->ary[m] = (struct idr_layer *)ptr;
 171         set_bit(m, p->bitmap);
 172         p->count++;
 173         /*
 174          * If this layer is full mark the bit in the layer above
 175          * to show that this part of the radix tree is full.
 176          * This may complete the layer above and require walking
 177          * up the radix tree.
 178          */
 179         n = id;
 180         while (p->bitmap == IDR_FULL) {
 181                 if (!(p = pa[++l]))
 182                         break;
 183                 n = n >> IDR_BITS;
 184                 set_bit((n & IDR_MASK), p->bitmap);
 185         }
 186         return(id);
 187 }
 188
 189 static int idr_get_new_above_int(struct idr_context *idp, void *ptr, int starting_id)
 190 {
 191         struct idr_layer *p, *pn;
 192         int layers, v, id;
 193
 194         idr_pre_get(idp);
 195
 196         id = starting_id;
 197 build_up:
 198         p = idp->top;
 199         layers = idp->layers;
 200         if (!p) {
 201                 if (!(p = alloc_layer(idp)))
 202                         return -1;
 203                 layers = 1;
 204         }
 205         /*
 206          * Add a new layer to the top of the tree if the requested
 207          * id is larger than the currently allocated space.
 208          */
 209         while ((layers < MAX_LEVEL) && (id >= (1 << (layers*IDR_BITS)))) {
 210                 layers++;
 211                 if (!p->count)
 212                         continue;
 213                 if (!(pn = alloc_layer(idp))) {
 214                         /*
 215                          * The allocation failed.  If we built part of
 216                          * the structure tear it down.
 217                          */
 218                         for (pn = p; p && p != idp->top; pn = p) {
 219                                 p = p->ary[0];
 220                                 pn->ary[0] = NULL;
 221                                 pn->bitmap = pn->count = 0;
 222                                 free_layer(idp, pn);
 223                         }
 224                         return -1;
 225                 }
 226                 pn->ary[0] = p;
 227                 pn->count = 1;
 228                 if (p->bitmap == IDR_FULL)
 229                         set_bit(0, pn->bitmap);
 230                 p = pn;
 231         }
 232         idp->top = p;
 233         idp->layers = layers;
 234         v = sub_alloc(idp, ptr, &id);
 235         if (v == -2)
 236                 goto build_up;
 237         return(v);
 238 }
 239
 240 static int sub_remove(struct idr_context *idp, int shift, int id)
 241 {
 242         struct idr_layer *p = idp->top;
 243         struct idr_layer **pa[1+MAX_LEVEL];
 244         struct idr_layer ***paa = &pa[0];
 245         int n;
 246
 247         *paa = NULL;
 248         *++paa = &idp->top;
 249
 250         while ((shift > 0) && p) {
 251                 n = (id >> shift) & IDR_MASK;
 252                 clear_bit(n, p->bitmap);
 253                 *++paa = &p->ary[n];
 254                 p = p->ary[n];
 255                 shift -= IDR_BITS;
 256         }
 257         n = id & IDR_MASK;
 258         if (p != NULL && test_bit(n, p->bitmap)) {
 259                 clear_bit(n, p->bitmap);
 260                 p->ary[n] = NULL;
 261                 while(*paa && ! --((**paa)->count)){
 262                         free_layer(idp, **paa);
 263                         **paa-- = NULL;
 264                 }
 265                 if ( ! *paa )
 266                         idp->layers = 0;
 267                 return 0;
 268         }
 269         return -1;
 270 }
 271
 272 static void *_idr_find(struct idr_context *idp, int id)
 273 {
 274         int n;
 275         struct idr_layer *p;
 276
 277         n = idp->layers * IDR_BITS;
 278         p = idp->top;
 279         /*
 280          * This tests to see if bits outside the current tree are
 281          * present.  If so, tain't one of ours!
 282          */
 283         if (n + IDR_BITS < 31 &&
 284             ((id & ~(~0 << MAX_ID_SHIFT)) >> (n + IDR_BITS))) {
 285                 return NULL;
 286         }
 287
 288         /* Mask off upper bits we don't use for the search. */
 289         id &= MAX_ID_MASK;
 290
 291         while (n >= IDR_BITS && p) {
 292                 n -= IDR_BITS;
 293                 p = p->ary[(id >> n) & IDR_MASK];
 294         }
 295         return((void *)p);
 296 }
 297
 298 static int _idr_remove(struct idr_context *idp, int id)
 299 {
 300         struct idr_layer *p;
 301
 302         /* Mask off upper bits we don't use for the search. */
 303         id &= MAX_ID_MASK;
 304
 305         if (sub_remove(idp, (idp->layers - 1) * IDR_BITS, id) == -1) {
 306                 return -1;
 307         }
 308
 309         if ( idp->top && idp->top->count == 1 &&
 310              (idp->layers > 1) &&
 311              idp->top->ary[0]) {
 312                 /* We can drop a layer */
 313                 p = idp->top->ary[0];
 314                 idp->top->bitmap = idp->top->count = 0;
 315                 free_layer(idp, idp->top);
 316                 idp->top = p;
 317                 --idp->layers;
 318         }
 319         while (idp->id_free_cnt >= IDR_FREE_MAX) {
 320                 p = alloc_layer(idp);
 321                 talloc_free(p);
 322         }
 323         return 0;
 324 }
 325
 326 /************************************************************************
 327   this is the public interface
 328 **************************************************************************/
 329
 330 /**
 331   initialise a idr tree. The context return value must be passed to
 332   all subsequent idr calls. To destroy the idr tree use talloc_free()
 333   on this context
 334  */
 335 _PUBLIC_ struct idr_context *idr_init(TALLOC_CTX *mem_ctx)
 336 {
 337         return talloc_zero(mem_ctx, struct idr_context);
 338 }
 339
 340 /**
 341   allocate the next available id, and assign 'ptr' into its slot.
 342   you can retrieve later this pointer using idr_find()
 343 */
 344 _PUBLIC_ int idr_get_new(struct idr_context *idp, void *ptr, int limit)
 345 {
 346         int ret = idr_get_new_above_int(idp, ptr, 0);
 347         if (ret > limit) {
 348                 idr_remove(idp, ret);
 349                 return -1;
 350         }
 351         return ret;
 352 }
 353
 354 /**
 355    allocate a new id, giving the first available value greater than or
 356    equal to the given starting id
 357 */
 358 _PUBLIC_ int idr_get_new_above(struct idr_context *idp, void *ptr, int starting_id, int limit)
 359 {
 360         int ret = idr_get_new_above_int(idp, ptr, starting_id);
 361         if (ret > limit) {
 362                 idr_remove(idp, ret);
 363                 return -1;
 364         }
 365         return ret;
 366 }
 367
 368 /**
 369   allocate a new id randomly in the given range
 370 */
 371 _PUBLIC_ int idr_get_new_random(struct idr_context *idp, void *ptr, int limit)
 372 {
 373         int id;
 374
 375         /* first try a random starting point in the whole range, and if that fails,
 376            then start randomly in the bottom half of the range. This can only
 377            fail if the range is over half full, and finally fallback to any
 378            free id */
 379         id = idr_get_new_above(idp, ptr, 1+(generate_random() % limit), limit);
 380         if (id == -1) {
 381                 id = idr_get_new_above(idp, ptr, 1+(generate_random()%(limit/2)), limit);
 382         }
 383         if (id == -1) {
 384                 id = idr_get_new_above(idp, ptr, 1, limit);
 385         }
 386
 387         return id;
 388 }
 389
 390 /**
 391   find a pointer value previously set with idr_get_new given an id
 392 */
 393 _PUBLIC_ void *idr_find(struct idr_context *idp, int id)
 394 {
 395         return _idr_find(idp, id);
 396 }
 397
 398 /**
 399   remove an id from the idr tree
 400 */
 401 _PUBLIC_ int idr_remove(struct idr_context *idp, int id)
 402 {
 403         int ret;
 404         ret = _idr_remove((struct idr_context *)idp, id);
 405         if (ret != 0) {
 406                 DEBUG(0,("WARNING: attempt to remove unset id %d in idtree\n", id));
 407         }
 408         return ret;
 409 }