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[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 ((id & ~(~0 << MAX_ID_SHIFT)) >> (n + IDR_BITS))
 284              return NULL;
 285
 286         /* Mask off upper bits we don't use for the search. */
 287         id &= MAX_ID_MASK;
 288
 289         while (n >= IDR_BITS && p) {
 290                 n -= IDR_BITS;
 291                 p = p->ary[(id >> n) & IDR_MASK];
 292         }
 293         return((void *)p);
 294 }
 295
 296 static int _idr_remove(struct idr_context *idp, int id)
 297 {
 298         struct idr_layer *p;
 299
 300         /* Mask off upper bits we don't use for the search. */
 301         id &= MAX_ID_MASK;
 302
 303         if (sub_remove(idp, (idp->layers - 1) * IDR_BITS, id) == -1) {
 304                 return -1;
 305         }
 306
 307         if ( idp->top && idp->top->count == 1 &&
 308              (idp->layers > 1) &&
 309              idp->top->ary[0]) {
 310                 /* We can drop a layer */
 311                 p = idp->top->ary[0];
 312                 idp->top->bitmap = idp->top->count = 0;
 313                 free_layer(idp, idp->top);
 314                 idp->top = p;
 315                 --idp->layers;
 316         }
 317         while (idp->id_free_cnt >= IDR_FREE_MAX) {
 318                 p = alloc_layer(idp);
 319                 talloc_free(p);
 320         }
 321         return 0;
 322 }
 323
 324 /************************************************************************
 325   this is the public interface
 326 **************************************************************************/
 327
 328 /**
 329   initialise a idr tree. The context return value must be passed to
 330   all subsequent idr calls. To destroy the idr tree use talloc_free()
 331   on this context
 332  */
 333 _PUBLIC_ struct idr_context *idr_init(TALLOC_CTX *mem_ctx)
 334 {
 335         return talloc_zero(mem_ctx, struct idr_context);
 336 }
 337
 338 /**
 339   allocate the next available id, and assign 'ptr' into its slot.
 340   you can retrieve later this pointer using idr_find()
 341 */
 342 _PUBLIC_ int idr_get_new(struct idr_context *idp, void *ptr, int limit)
 343 {
 344         int ret = idr_get_new_above_int(idp, ptr, 0);
 345         if (ret > limit) {
 346                 idr_remove(idp, ret);
 347                 return -1;
 348         }
 349         return ret;
 350 }
 351
 352 /**
 353    allocate a new id, giving the first available value greater than or
 354    equal to the given starting id
 355 */
 356 _PUBLIC_ int idr_get_new_above(struct idr_context *idp, void *ptr, int starting_id, int limit)
 357 {
 358         int ret = idr_get_new_above_int(idp, ptr, starting_id);
 359         if (ret > limit) {
 360                 idr_remove(idp, ret);
 361                 return -1;
 362         }
 363         return ret;
 364 }
 365
 366 /**
 367   allocate a new id randomly in the given range
 368 */
 369 _PUBLIC_ int idr_get_new_random(struct idr_context *idp, void *ptr, int limit)
 370 {
 371         int id;
 372
 373         /* first try a random starting point in the whole range, and if that fails,
 374            then start randomly in the bottom half of the range. This can only
 375            fail if the range is over half full, and finally fallback to any
 376            free id */
 377         id = idr_get_new_above(idp, ptr, 1+(generate_random() % limit), limit);
 378         if (id == -1) {
 379                 id = idr_get_new_above(idp, ptr, 1+(generate_random()%(limit/2)), limit);
 380         }
 381         if (id == -1) {
 382                 id = idr_get_new_above(idp, ptr, 1, limit);
 383         }
 384
 385         return id;
 386 }
 387
 388 /**
 389   find a pointer value previously set with idr_get_new given an id
 390 */
 391 _PUBLIC_ void *idr_find(struct idr_context *idp, int id)
 392 {
 393         return _idr_find(idp, id);
 394 }
 395
 396 /**
 397   remove an id from the idr tree
 398 */
 399 _PUBLIC_ int idr_remove(struct idr_context *idp, int id)
 400 {
 401         int ret;
 402         ret = _idr_remove((struct idr_context *)idp, id);
 403         if (ret != 0) {
 404                 DEBUG(0,("WARNING: attempt to remove unset id %d in idtree\n", id));
 405         }
 406         return ret;
 407 }