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