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