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 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, write to the Free Software
  25    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  26 */
  27
  28 /*
  29   see the section marked "public interface" below for documentation
  30 */
  31
  32 /**
  33  * @file
  34  */
  35
  36 #include "includes.h"
  37
  38 #define IDR_BITS 5
  39 #define IDR_FULL 0xfffffffful
  40 #if 0 /* unused */
  41 #define TOP_LEVEL_FULL (IDR_FULL >> 30)
  42 #endif
  43 #define IDR_SIZE (1 << IDR_BITS)
  44 #define IDR_MASK ((1 << IDR_BITS)-1)
  45 #define MAX_ID_SHIFT (sizeof(int)*8 - 1)
  46 #define MAX_ID_BIT (1U << MAX_ID_SHIFT)
  47 #define MAX_ID_MASK (MAX_ID_BIT - 1)
  48 #define MAX_LEVEL (MAX_ID_SHIFT + IDR_BITS - 1) / IDR_BITS
  49 #define IDR_FREE_MAX MAX_LEVEL + MAX_LEVEL
  50
  51 #define set_bit(bit, v) (v) |= (1<<(bit))
  52 #define clear_bit(bit, v) (v) &= ~(1<<(bit))
  53 #define test_bit(bit, v) ((v) & (1<<(bit)))
  54
  55 struct idr_layer {
  56         uint32_t                 bitmap;
  57         struct idr_layer        *ary[IDR_SIZE];
  58         int                      count;
  59 };
  60
  61 struct idr_context {
  62         struct idr_layer *top;
  63         struct idr_layer *id_free;
  64         int               layers;
  65         int               id_free_cnt;
  66 };
  67
  68 static struct idr_layer *alloc_layer(struct idr_context *idp)
  69 {
  70         struct idr_layer *p;
  71
  72         if (!(p = idp->id_free))
  73                 return NULL;
  74         idp->id_free = p->ary[0];
  75         idp->id_free_cnt--;
  76         p->ary[0] = NULL;
  77         return p;
  78 }
  79
  80 static int find_next_bit(uint32_t bm, int maxid, int n)
  81 {
  82         while (n<maxid && !test_bit(n, bm)) n++;
  83         return n;
  84 }
  85
  86 static void free_layer(struct idr_context *idp, struct idr_layer *p)
  87 {
  88         p->ary[0] = idp->id_free;
  89         idp->id_free = p;
  90         idp->id_free_cnt++;
  91 }
  92
  93 static int idr_pre_get(struct idr_context *idp)
  94 {
  95         while (idp->id_free_cnt < IDR_FREE_MAX) {
  96                 struct idr_layer *new = talloc_zero(idp, struct idr_layer);
  97                 if(new == NULL)
  98                         return (0);
  99                 free_layer(idp, new);
 100         }
 101         return 1;
 102 }
 103
 104 static int sub_alloc(struct idr_context *idp, void *ptr, int *starting_id)
 105 {
 106         int n, m, sh;
 107         struct idr_layer *p, *new;
 108         struct idr_layer *pa[MAX_LEVEL];
 109         int l, id;
 110         uint32_t bm;
 111
 112         memset(pa, 0, sizeof(pa));
 113
 114         id = *starting_id;
 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                         id = (id | ((1 << (IDR_BITS*l))-1)) + 1;
 129                         if (!(p = pa[l])) {
 130                                 *starting_id = id;
 131                                 return -2;
 132                         }
 133                         continue;
 134                 }
 135                 if (m != n) {
 136                         sh = IDR_BITS*l;
 137                         id = ((id >> sh) ^ n ^ m) << sh;
 138                 }
 139                 if ((id >= MAX_ID_BIT) || (id < 0))
 140                         return -1;
 141                 if (l == 0)
 142                         break;
 143                 /*
 144                  * Create the layer below if it is missing.
 145                  */
 146                 if (!p->ary[m]) {
 147                         if (!(new = alloc_layer(idp)))
 148                                 return -1;
 149                         p->ary[m] = new;
 150                         p->count++;
 151                 }
 152                 pa[l--] = p;
 153                 p = p->ary[m];
 154         }
 155         /*
 156          * We have reached the leaf node, plant the
 157          * users pointer and return the raw id.
 158          */
 159         p->ary[m] = (struct idr_layer *)ptr;
 160         set_bit(m, p->bitmap);
 161         p->count++;
 162         /*
 163          * If this layer is full mark the bit in the layer above
 164          * to show that this part of the radix tree is full.
 165          * This may complete the layer above and require walking
 166          * up the radix tree.
 167          */
 168         n = id;
 169         while (p->bitmap == IDR_FULL) {
 170                 if (!(p = pa[++l]))
 171                         break;
 172                 n = n >> IDR_BITS;
 173                 set_bit((n & IDR_MASK), p->bitmap);
 174         }
 175         return(id);
 176 }
 177
 178 static int idr_get_new_above_int(struct idr_context *idp, void *ptr, int starting_id)
 179 {
 180         struct idr_layer *p, *new;
 181         int layers, v, id;
 182
 183         idr_pre_get(idp);
 184
 185         id = starting_id;
 186 build_up:
 187         p = idp->top;
 188         layers = idp->layers;
 189         if (!p) {
 190                 if (!(p = alloc_layer(idp)))
 191                         return -1;
 192                 layers = 1;
 193         }
 194         /*
 195          * Add a new layer to the top of the tree if the requested
 196          * id is larger than the currently allocated space.
 197          */
 198         while ((layers < MAX_LEVEL) && (id >= (1 << (layers*IDR_BITS)))) {
 199                 layers++;
 200                 if (!p->count)
 201                         continue;
 202                 if (!(new = alloc_layer(idp))) {
 203                         /*
 204                          * The allocation failed.  If we built part of
 205                          * the structure tear it down.
 206                          */
 207                         for (new = p; p && p != idp->top; new = p) {
 208                                 p = p->ary[0];
 209                                 new->ary[0] = NULL;
 210                                 new->bitmap = new->count = 0;
 211                                 free_layer(idp, new);
 212                         }
 213                         return -1;
 214                 }
 215                 new->ary[0] = p;
 216                 new->count = 1;
 217                 if (p->bitmap == IDR_FULL)
 218                         set_bit(0, new->bitmap);
 219                 p = new;
 220         }
 221         idp->top = p;
 222         idp->layers = layers;
 223         v = sub_alloc(idp, ptr, &id);
 224         if (v == -2)
 225                 goto build_up;
 226         return(v);
 227 }
 228
 229 static int sub_remove(struct idr_context *idp, int shift, int id)
 230 {
 231         struct idr_layer *p = idp->top;
 232         struct idr_layer **pa[MAX_LEVEL];
 233         struct idr_layer ***paa = &pa[0];
 234         int n;
 235
 236         *paa = NULL;
 237         *++paa = &idp->top;
 238
 239         while ((shift > 0) && p) {
 240                 n = (id >> shift) & IDR_MASK;
 241                 clear_bit(n, p->bitmap);
 242                 *++paa = &p->ary[n];
 243                 p = p->ary[n];
 244                 shift -= IDR_BITS;
 245         }
 246         n = id & IDR_MASK;
 247         if (p != NULL && test_bit(n, p->bitmap)) {
 248                 clear_bit(n, p->bitmap);
 249                 p->ary[n] = NULL;
 250                 while(*paa && ! --((**paa)->count)){
 251                         free_layer(idp, **paa);
 252                         **paa-- = NULL;
 253                 }
 254                 if ( ! *paa )
 255                         idp->layers = 0;
 256                 return 0;
 257         }
 258         return -1;
 259 }
 260
 261 static void *_idr_find(struct idr_context *idp, int id)
 262 {
 263         int n;
 264         struct idr_layer *p;
 265
 266         n = idp->layers * IDR_BITS;
 267         p = idp->top;
 268         /*
 269          * This tests to see if bits outside the current tree are
 270          * present.  If so, tain't one of ours!
 271          */
 272         if ((id & ~(~0 << MAX_ID_SHIFT)) >> (n + IDR_BITS))
 273              return NULL;
 274
 275         /* Mask off upper bits we don't use for the search. */
 276         id &= MAX_ID_MASK;
 277
 278         while (n >= IDR_BITS && p) {
 279                 n -= IDR_BITS;
 280                 p = p->ary[(id >> n) & IDR_MASK];
 281         }
 282         return((void *)p);
 283 }
 284
 285 static int _idr_remove(struct idr_context *idp, int id)
 286 {
 287         struct idr_layer *p;
 288
 289         /* Mask off upper bits we don't use for the search. */
 290         id &= MAX_ID_MASK;
 291
 292         if (sub_remove(idp, (idp->layers - 1) * IDR_BITS, id) == -1) {
 293                 return -1;
 294         }
 295
 296         if ( idp->top && idp->top->count == 1 &&
 297              (idp->layers > 1) &&
 298              idp->top->ary[0]) {
 299                 /* We can drop a layer */
 300                 p = idp->top->ary[0];
 301                 idp->top->bitmap = idp->top->count = 0;
 302                 free_layer(idp, idp->top);
 303                 idp->top = p;
 304                 --idp->layers;
 305         }
 306         while (idp->id_free_cnt >= IDR_FREE_MAX) {
 307                 p = alloc_layer(idp);
 308                 talloc_free(p);
 309         }
 310         return 0;
 311 }
 312
 313 /************************************************************************
 314   this is the public interface
 315 **************************************************************************/
 316
 317 /**
 318   initialise a idr tree. The context return value must be passed to
 319   all subsequent idr calls. To destroy the idr tree use talloc_free()
 320   on this context
 321  */
 322 _PUBLIC_ struct idr_context *idr_init(TALLOC_CTX *mem_ctx)
 323 {
 324         return talloc_zero(mem_ctx, struct idr_context);
 325 }
 326
 327 /**
 328   allocate the next available id, and assign 'ptr' into its slot.
 329   you can retrieve later this pointer using idr_find()
 330 */
 331 _PUBLIC_ int idr_get_new(struct idr_context *idp, void *ptr, int limit)
 332 {
 333         int ret = idr_get_new_above_int(idp, ptr, 0);
 334         if (ret > limit) {
 335                 idr_remove(idp, ret);
 336                 return -1;
 337         }
 338         return ret;
 339 }
 340
 341 /**
 342    allocate a new id, giving the first available value greater than or
 343    equal to the given starting id
 344 */
 345 _PUBLIC_ int idr_get_new_above(struct idr_context *idp, void *ptr, int starting_id, int limit)
 346 {
 347         int ret = idr_get_new_above_int(idp, ptr, starting_id);
 348         if (ret > limit) {
 349                 idr_remove(idp, ret);
 350                 return -1;
 351         }
 352         return ret;
 353 }
 354
 355 /**
 356   allocate a new id randomly in the given range
 357 */
 358 _PUBLIC_ int idr_get_new_random(struct idr_context *idp, void *ptr, int limit)
 359 {
 360         int id;
 361
 362         /* first try a random starting point in the whole range, and if that fails,
 363            then start randomly in the bottom half of the range. This can only
 364            fail if the range is over half full */
 365         id = idr_get_new_above(idp, ptr, 1+(generate_random() % limit), limit);
 366         if (id == -1) {
 367                 id = idr_get_new_above(idp, ptr, 1+(generate_random()%(limit/2)), limit);
 368         }
 369
 370         return id;
 371 }
 372
 373 /**
 374   find a pointer value previously set with idr_get_new given an id
 375 */
 376 _PUBLIC_ void *idr_find(struct idr_context *idp, int id)
 377 {
 378         return _idr_find(idp, id);
 379 }
 380
 381 /**
 382   remove an id from the idr tree
 383 */
 384 _PUBLIC_ int idr_remove(struct idr_context *idp, int id)
 385 {
 386         int ret;
 387         ret = _idr_remove((struct idr_context *)idp, id);
 388         if (ret != 0) {
 389                 DEBUG(0,("WARNING: attempt to remove unset id %d in idtree\n", id));
 390         }
 391         return ret;
 392 }