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 *new = talloc_zero(idp, struct idr_layer);
  96                 if(new == NULL)
  97                         return (0);
  98                 free_layer(idp, new);
  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, *new;
 107         struct idr_layer *pa[MAX_LEVEL+1];
 108         unsigned 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 (!(new = alloc_layer(idp)))
 159                                 return -1;
 160                         p->ary[m] = new;
 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, *new;
 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 (!(new = alloc_layer(idp))) {
 214                         /*
 215                          * The allocation failed.  If we built part of
 216                          * the structure tear it down.
 217                          */
 218                         for (new = p; p && p != idp->top; new = p) {
 219                                 p = p->ary[0];
 220                                 new->ary[0] = NULL;
 221                                 new->bitmap = new->count = 0;
 222                                 free_layer(idp, new);
 223                         }
 224                         return -1;
 225                 }
 226                 new->ary[0] = p;
 227                 new->count = 1;
 228                 if (p->bitmap == IDR_FULL)
 229                         set_bit(0, new->bitmap);
 230                 p = new;
 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   find a pointer value previously set with idr_get_new given an id
 370 */
 371 _PUBLIC_ void *idr_find(struct idr_context *idp, int id)
 372 {
 373         return _idr_find(idp, id);
 374 }
 375
 376 /**
 377   remove an id from the idr tree
 378 */
 379 _PUBLIC_ int idr_remove(struct idr_context *idp, int id)
 380 {
 381         int ret;
 382         ret = _idr_remove((struct idr_context *)idp, id);
 383         if (ret != 0) {
 384                 DEBUG(0,("WARNING: attempt to remove unset id %d in idtree\n", id));
 385         }
 386         return ret;
 387 }