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