source4/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 3 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];
 108         int l, id;
 109         uint32_t bm;
 110
 111         memset(pa, 0, sizeof(pa));
 112
 113         id = *starting_id;
 114         p = idp->top;
 115         l = idp->layers;
 116         pa[l--] = NULL;
 117         while (1) {
 118                 /*
 119                  * We run around this while until we reach the leaf node...
 120                  */
 121                 n = (id >> (IDR_BITS*l)) & IDR_MASK;
 122                 bm = ~p->bitmap;
 123                 m = find_next_bit(bm, IDR_SIZE, n);
 124                 if (m == IDR_SIZE) {
 125                         /* no space available go back to previous layer. */
 126                         l++;
 127                         id = (id | ((1 << (IDR_BITS*l))-1)) + 1;
 128                         if (!(p = pa[l])) {
 129                                 *starting_id = id;
 130                                 return -2;
 131                         }
 132                         continue;
 133                 }
 134                 if (m != n) {
 135                         sh = IDR_BITS*l;
 136                         id = ((id >> sh) ^ n ^ m) << sh;
 137                 }
 138                 if ((id >= MAX_ID_BIT) || (id < 0))
 139                         return -1;
 140                 if (l == 0)
 141                         break;
 142                 /*
 143                  * Create the layer below if it is missing.
 144                  */
 145                 if (!p->ary[m]) {
 146                         if (!(new = alloc_layer(idp)))
 147                                 return -1;
 148                         p->ary[m] = new;
 149                         p->count++;
 150                 }
 151                 pa[l--] = p;
 152                 p = p->ary[m];
 153         }
 154         /*
 155          * We have reached the leaf node, plant the
 156          * users pointer and return the raw id.
 157          */
 158         p->ary[m] = (struct idr_layer *)ptr;
 159         set_bit(m, p->bitmap);
 160         p->count++;
 161         /*
 162          * If this layer is full mark the bit in the layer above
 163          * to show that this part of the radix tree is full.
 164          * This may complete the layer above and require walking
 165          * up the radix tree.
 166          */
 167         n = id;
 168         while (p->bitmap == IDR_FULL) {
 169                 if (!(p = pa[++l]))
 170                         break;
 171                 n = n >> IDR_BITS;
 172                 set_bit((n & IDR_MASK), p->bitmap);
 173         }
 174         return(id);
 175 }
 176
 177 static int idr_get_new_above_int(struct idr_context *idp, void *ptr, int starting_id)
 178 {
 179         struct idr_layer *p, *new;
 180         int layers, v, id;
 181
 182         idr_pre_get(idp);
 183
 184         id = starting_id;
 185 build_up:
 186         p = idp->top;
 187         layers = idp->layers;
 188         if (!p) {
 189                 if (!(p = alloc_layer(idp)))
 190                         return -1;
 191                 layers = 1;
 192         }
 193         /*
 194          * Add a new layer to the top of the tree if the requested
 195          * id is larger than the currently allocated space.
 196          */
 197         while ((layers < MAX_LEVEL) && (id >= (1 << (layers*IDR_BITS)))) {
 198                 layers++;
 199                 if (!p->count)
 200                         continue;
 201                 if (!(new = alloc_layer(idp))) {
 202                         /*
 203                          * The allocation failed.  If we built part of
 204                          * the structure tear it down.
 205                          */
 206                         for (new = p; p && p != idp->top; new = p) {
 207                                 p = p->ary[0];
 208                                 new->ary[0] = NULL;
 209                                 new->bitmap = new->count = 0;
 210                                 free_layer(idp, new);
 211                         }
 212                         return -1;
 213                 }
 214                 new->ary[0] = p;
 215                 new->count = 1;
 216                 if (p->bitmap == IDR_FULL)
 217                         set_bit(0, new->bitmap);
 218                 p = new;
 219         }
 220         idp->top = p;
 221         idp->layers = layers;
 222         v = sub_alloc(idp, ptr, &id);
 223         if (v == -2)
 224                 goto build_up;
 225         return(v);
 226 }
 227
 228 static int sub_remove(struct idr_context *idp, int shift, int id)
 229 {
 230         struct idr_layer *p = idp->top;
 231         struct idr_layer **pa[MAX_LEVEL];
 232         struct idr_layer ***paa = &pa[0];
 233         int n;
 234
 235         *paa = NULL;
 236         *++paa = &idp->top;
 237
 238         while ((shift > 0) && p) {
 239                 n = (id >> shift) & IDR_MASK;
 240                 clear_bit(n, p->bitmap);
 241                 *++paa = &p->ary[n];
 242                 p = p->ary[n];
 243                 shift -= IDR_BITS;
 244         }
 245         n = id & IDR_MASK;
 246         if (p != NULL && test_bit(n, p->bitmap)) {
 247                 clear_bit(n, p->bitmap);
 248                 p->ary[n] = NULL;
 249                 while(*paa && ! --((**paa)->count)){
 250                         free_layer(idp, **paa);
 251                         **paa-- = NULL;
 252                 }
 253                 if ( ! *paa )
 254                         idp->layers = 0;
 255                 return 0;
 256         }
 257         return -1;
 258 }
 259
 260 static void *_idr_find(struct idr_context *idp, int id)
 261 {
 262         int n;
 263         struct idr_layer *p;
 264
 265         n = idp->layers * IDR_BITS;
 266         p = idp->top;
 267         /*
 268          * This tests to see if bits outside the current tree are
 269          * present.  If so, tain't one of ours!
 270          */
 271         if ((id & ~(~0 << MAX_ID_SHIFT)) >> (n + IDR_BITS))
 272              return NULL;
 273
 274         /* Mask off upper bits we don't use for the search. */
 275         id &= MAX_ID_MASK;
 276
 277         while (n >= IDR_BITS && p) {
 278                 n -= IDR_BITS;
 279                 p = p->ary[(id >> n) & IDR_MASK];
 280         }
 281         return((void *)p);
 282 }
 283
 284 static int _idr_remove(struct idr_context *idp, int id)
 285 {
 286         struct idr_layer *p;
 287
 288         /* Mask off upper bits we don't use for the search. */
 289         id &= MAX_ID_MASK;
 290
 291         if (sub_remove(idp, (idp->layers - 1) * IDR_BITS, id) == -1) {
 292                 return -1;
 293         }
 294
 295         if ( idp->top && idp->top->count == 1 &&
 296              (idp->layers > 1) &&
 297              idp->top->ary[0]) {
 298                 /* We can drop a layer */
 299                 p = idp->top->ary[0];
 300                 idp->top->bitmap = idp->top->count = 0;
 301                 free_layer(idp, idp->top);
 302                 idp->top = p;
 303                 --idp->layers;
 304         }
 305         while (idp->id_free_cnt >= IDR_FREE_MAX) {
 306                 p = alloc_layer(idp);
 307                 talloc_free(p);
 308         }
 309         return 0;
 310 }
 311
 312 /************************************************************************
 313   this is the public interface
 314 **************************************************************************/
 315
 316 /**
 317   initialise a idr tree. The context return value must be passed to
 318   all subsequent idr calls. To destroy the idr tree use talloc_free()
 319   on this context
 320  */
 321 _PUBLIC_ struct idr_context *idr_init(TALLOC_CTX *mem_ctx)
 322 {
 323         return talloc_zero(mem_ctx, struct idr_context);
 324 }
 325
 326 /**
 327   allocate the next available id, and assign 'ptr' into its slot.
 328   you can retrieve later this pointer using idr_find()
 329 */
 330 _PUBLIC_ int idr_get_new(struct idr_context *idp, void *ptr, int limit)
 331 {
 332         int ret = idr_get_new_above_int(idp, ptr, 0);
 333         if (ret > limit) {
 334                 idr_remove(idp, ret);
 335                 return -1;
 336         }
 337         return ret;
 338 }
 339
 340 /**
 341    allocate a new id, giving the first available value greater than or
 342    equal to the given starting id
 343 */
 344 _PUBLIC_ int idr_get_new_above(struct idr_context *idp, void *ptr, int starting_id, int limit)
 345 {
 346         int ret = idr_get_new_above_int(idp, ptr, starting_id);
 347         if (ret > limit) {
 348                 idr_remove(idp, ret);
 349                 return -1;
 350         }
 351         return ret;
 352 }
 353
 354 /**
 355   allocate a new id randomly in the given range
 356 */
 357 _PUBLIC_ int idr_get_new_random(struct idr_context *idp, void *ptr, int limit)
 358 {
 359         int id;
 360
 361         /* first try a random starting point in the whole range, and if that fails,
 362            then start randomly in the bottom half of the range. This can only
 363            fail if the range is over half full */
 364         id = idr_get_new_above(idp, ptr, 1+(generate_random() % limit), limit);
 365         if (id == -1) {
 366                 id = idr_get_new_above(idp, ptr, 1+(generate_random()%(limit/2)), limit);
 367         }
 368
 369         return id;
 370 }
 371
 372 /**
 373   find a pointer value previously set with idr_get_new given an id
 374 */
 375 _PUBLIC_ void *idr_find(struct idr_context *idp, int id)
 376 {
 377         return _idr_find(idp, id);
 378 }
 379
 380 /**
 381   remove an id from the idr tree
 382 */
 383 _PUBLIC_ int idr_remove(struct idr_context *idp, int id)
 384 {
 385         int ret;
 386         ret = _idr_remove((struct idr_context *)idp, id);
 387         if (ret != 0) {
 388                 DEBUG(0,("WARNING: attempt to remove unset id %d in idtree\n", id));
 389         }
 390         return ret;
 391 }