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 54struct idr_layer { 55 uint32_t bitmap; 56 struct idr_layer *ary[IDR_SIZE]; 57 int count; 58}; 59 60struct idr_context { 61 struct idr_layer *top; 62 struct idr_layer *id_free; 63 int layers; 64 int id_free_cnt; 65}; 66 67static 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 79static 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 85static 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 92static int idr_pre_get(struct idr_context *idp) 93{ 94 while (idp->id_free_cnt < IDR_FREE_MAX) { 95 struct idr_layer *pn = talloc_zero(idp, struct idr_layer); 96 if(pn == NULL) 97 return (0); 98 free_layer(idp, pn); 99 } 100 return 1; 101} 102 103static int sub_alloc(struct idr_context *idp, void *ptr, int *starting_id) 104{ 105 int n, m, sh; 106 struct idr_layer *p, *pn; 107 struct idr_layer *pa[MAX_LEVEL]; 108 int l, id, oid; 109 uint32_t bm; 110 111 memset(pa, 0, sizeof(pa)); 112 113 id = *starting_id; 114restart: 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 (!(pn = alloc_layer(idp))) 159 return -1; 160 p->ary[m] = pn; 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 189static int idr_get_new_above_int(struct idr_context *idp, void *ptr, int starting_id) 190{ 191 struct idr_layer *p, *pn; 192 int layers, v, id; 193 194 idr_pre_get(idp); 195 196 id = starting_id; 197build_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 (!(pn = alloc_layer(idp))) { 214 /* 215 * The allocation failed. If we built part of 216 * the structure tear it down. 217 */ 218 for (pn = p; p && p != idp->top; pn = p) { 219 p = p->ary[0]; 220 pn->ary[0] = NULL; 221 pn->bitmap = pn->count = 0; 222 free_layer(idp, pn); 223 } 224 return -1; 225 } 226 pn->ary[0] = p; 227 pn->count = 1; 228 if (p->bitmap == IDR_FULL) 229 set_bit(0, pn->bitmap); 230 p = pn; 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 240static int sub_remove(struct idr_context *idp, int shift, int id) 241{ 242 struct idr_layer *p = idp->top; 243 struct idr_layer **pa[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 272static 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 ((id & ~(~0 << MAX_ID_SHIFT)) >> (n + IDR_BITS)) 284 return NULL; 285 286 /* Mask off upper bits we don't use for the search. */ 287 id &= MAX_ID_MASK; 288 289 while (n >= IDR_BITS && p) { 290 n -= IDR_BITS; 291 p = p->ary[(id >> n) & IDR_MASK]; 292 } 293 return((void *)p); 294} 295 296static int _idr_remove(struct idr_context *idp, int id) 297{ 298 struct idr_layer *p; 299 300 /* Mask off upper bits we don't use for the search. */ 301 id &= MAX_ID_MASK; 302 303 if (sub_remove(idp, (idp->layers - 1) * IDR_BITS, id) == -1) { 304 return -1; 305 } 306 307 if ( idp->top && idp->top->count == 1 && 308 (idp->layers > 1) && 309 idp->top->ary[0]) { 310 /* We can drop a layer */ 311 p = idp->top->ary[0]; 312 idp->top->bitmap = idp->top->count = 0; 313 free_layer(idp, idp->top); 314 idp->top = p; 315 --idp->layers; 316 } 317 while (idp->id_free_cnt >= IDR_FREE_MAX) { 318 p = alloc_layer(idp); 319 talloc_free(p); 320 } 321 return 0; 322} 323 324/************************************************************************ 325 this is the public interface 326**************************************************************************/ 327 328/** 329 initialise a idr tree. The context return value must be passed to 330 all subsequent idr calls. To destroy the idr tree use talloc_free() 331 on this context 332 */ 333_PUBLIC_ struct idr_context *idr_init(TALLOC_CTX *mem_ctx) 334{ 335 return talloc_zero(mem_ctx, struct idr_context); 336} 337 338/** 339 allocate the next available id, and assign 'ptr' into its slot. 340 you can retrieve later this pointer using idr_find() 341*/ 342_PUBLIC_ int idr_get_new(struct idr_context *idp, void *ptr, int limit) 343{ 344 int ret = idr_get_new_above_int(idp, ptr, 0); 345 if (ret > limit) { 346 idr_remove(idp, ret); 347 return -1; 348 } 349 return ret; 350} 351 352/** 353 allocate a new id, giving the first available value greater than or 354 equal to the given starting id 355*/ 356_PUBLIC_ int idr_get_new_above(struct idr_context *idp, void *ptr, int starting_id, int limit) 357{ 358 int ret = idr_get_new_above_int(idp, ptr, starting_id); 359 if (ret > limit) { 360 idr_remove(idp, ret); 361 return -1; 362 } 363 return ret; 364} 365 366/** 367 allocate a new id randomly in the given range 368*/ 369_PUBLIC_ int idr_get_new_random(struct idr_context *idp, void *ptr, int limit) 370{ 371 int id; 372 373 /* first try a random starting point in the whole range, and if that fails, 374 then start randomly in the bottom half of the range. This can only 375 fail if the range is over half full, and finally fallback to any 376 free id */ 377 id = idr_get_new_above(idp, ptr, 1+(generate_random() % limit), limit); 378 if (id == -1) { 379 id = idr_get_new_above(idp, ptr, 1+(generate_random()%(limit/2)), limit); 380 } 381 if (id == -1) { 382 id = idr_get_new_above(idp, ptr, 1, limit); 383 } 384 385 return id; 386} 387 388/** 389 find a pointer value previously set with idr_get_new given an id 390*/ 391_PUBLIC_ void *idr_find(struct idr_context *idp, int id) 392{ 393 return _idr_find(idp, id); 394} 395 396/** 397 remove an id from the idr tree 398*/ 399_PUBLIC_ int idr_remove(struct idr_context *idp, int id) 400{ 401 int ret; 402 ret = _idr_remove((struct idr_context *)idp, id); 403 if (ret != 0) { 404 DEBUG(0,("WARNING: attempt to remove unset id %d in idtree\n", id)); 405 } 406 return ret; 407} 408