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 4515078 : static struct idr_layer *alloc_layer(struct idr_context *idp)
71 : {
72 36152 : struct idr_layer *p;
73 :
74 4515078 : if (!(p = idp->id_free))
75 0 : return NULL;
76 4515078 : idp->id_free = p->ary[0];
77 4515078 : idp->id_free_cnt--;
78 4515078 : p->ary[0] = NULL;
79 4500043 : return p;
80 : }
81 :
82 4841855 : static int find_next_bit(uint32_t bm, int maxid, int n)
83 : {
84 14276375 : while (n<maxid && !test_bit(n, bm)) n++;
85 4841855 : return n;
86 : }
87 :
88 5390344 : static void free_layer(struct idr_context *idp, struct idr_layer *p)
89 : {
90 5390344 : p->ary[0] = idp->id_free;
91 5390344 : idp->id_free = p;
92 5390344 : idp->id_free_cnt++;
93 5376134 : }
94 :
95 1062445 : static int idr_pre_get(struct idr_context *idp)
96 : {
97 3040155 : while (idp->id_free_cnt < IDR_FREE_MAX) {
98 2019436 : struct idr_layer *pn = talloc_zero(idp, struct idr_layer);
99 2019436 : if(pn == NULL)
100 0 : return (0);
101 2063910 : free_layer(idp, pn);
102 : }
103 1017971 : return 1;
104 : }
105 :
106 1062462 : static int sub_alloc(struct idr_context *idp, void *ptr, int *starting_id)
107 : {
108 44474 : int n, m, sh;
109 44474 : struct idr_layer *p, *pn;
110 44474 : struct idr_layer *pa[MAX_LEVEL+1];
111 44474 : unsigned int l, id, oid;
112 44474 : uint32_t bm;
113 :
114 1062462 : memset(pa, 0, sizeof(pa));
115 :
116 1062462 : id = *starting_id;
117 1062505 : restart:
118 1062505 : p = idp->top;
119 1062505 : l = idp->layers;
120 1062505 : pa[l--] = NULL;
121 109670 : while (1) {
122 : /*
123 : * We run around this while until we reach the leaf node...
124 : */
125 4841855 : n = (id >> (IDR_BITS*l)) & IDR_MASK;
126 4841855 : bm = ~p->bitmap;
127 4841855 : m = find_next_bit(bm, IDR_SIZE, n);
128 4841855 : if (m == IDR_SIZE) {
129 : /* no space available go back to previous layer. */
130 183598 : l++;
131 183598 : oid = id;
132 183598 : id = (id | ((1 << (IDR_BITS*l))-1)) + 1;
133 :
134 : /* if already at the top layer, we need to grow */
135 183598 : 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 183581 : sh = IDR_BITS * (l + 1);
144 183581 : if (oid >> sh == id >> sh)
145 183538 : continue;
146 : else
147 43 : goto restart;
148 : }
149 4658257 : if (m != n) {
150 345666 : sh = IDR_BITS*l;
151 345666 : id = ((id >> sh) ^ n ^ m) << sh;
152 : }
153 4658257 : if (id >= MAX_ID_BIT)
154 0 : return -1;
155 4658257 : if (l == 0)
156 1017971 : break;
157 : /*
158 : * Create the layer below if it is missing.
159 : */
160 3595812 : if (!p->ary[m]) {
161 2845170 : if (!(pn = alloc_layer(idp)))
162 0 : return -1;
163 2845170 : p->ary[m] = pn;
164 2845170 : p->count++;
165 : }
166 3595812 : pa[l--] = p;
167 3595812 : 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 1062445 : p->ary[m] = (struct idr_layer *)ptr;
174 1062445 : set_bit(m, p->bitmap);
175 1062445 : 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 1062445 : n = id;
183 1065762 : while (p->bitmap == IDR_FULL) {
184 3317 : if (l >= MAX_LEVEL) {
185 0 : break;
186 : }
187 3317 : p = pa[++l];
188 3317 : if (p == NULL) {
189 0 : break;
190 : }
191 3317 : n = n >> IDR_BITS;
192 3317 : set_bit((n & IDR_MASK), p->bitmap);
193 : }
194 1017971 : return(id);
195 : }
196 :
197 1062445 : static int idr_get_new_above_int(struct idr_context *idp, void *ptr, int starting_id)
198 : {
199 44474 : struct idr_layer *p, *pn;
200 44474 : int layers, v, id;
201 :
202 1062445 : idr_pre_get(idp);
203 :
204 1062445 : id = starting_id;
205 1062462 : build_up:
206 1062462 : p = idp->top;
207 1062462 : layers = idp->layers;
208 1062462 : if (!p) {
209 454704 : if (!(p = alloc_layer(idp)))
210 0 : return -1;
211 450738 : 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 2122330 : while ((layers < MAX_LEVEL) && (id >= (1 << (layers*IDR_BITS)))) {
218 1059868 : layers++;
219 1059868 : if (!p->count)
220 991326 : continue;
221 68542 : 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 68542 : pn->ary[0] = p;
235 68542 : pn->count = 1;
236 68542 : if (p->bitmap == IDR_FULL)
237 0 : set_bit(0, pn->bitmap);
238 68385 : p = pn;
239 : }
240 1062462 : idp->top = p;
241 1062462 : idp->layers = layers;
242 1062462 : v = sub_alloc(idp, ptr, &id);
243 1062462 : if (v == -2)
244 17 : goto build_up;
245 1017971 : return(v);
246 : }
247 :
248 1038766 : static int sub_remove(struct idr_context *idp, int shift, int id)
249 : {
250 1038766 : struct idr_layer *p = idp->top;
251 19468 : struct idr_layer **pa[1+MAX_LEVEL];
252 1038766 : struct idr_layer ***paa = &pa[0];
253 19468 : int n;
254 :
255 1038766 : *paa = NULL;
256 1038766 : *++paa = &idp->top;
257 :
258 4438759 : while ((shift > 0) && p) {
259 3399993 : n = (id >> shift) & IDR_MASK;
260 3399993 : clear_bit(n, p->bitmap);
261 3399993 : *++paa = &p->ary[n];
262 3399993 : p = p->ary[n];
263 3399993 : shift -= IDR_BITS;
264 : }
265 1038766 : n = id & IDR_MASK;
266 1038766 : if (p != NULL && test_bit(n, p->bitmap)) {
267 1038766 : clear_bit(n, p->bitmap);
268 1038766 : p->ary[n] = NULL;
269 4341138 : while(*paa && ! --((**paa)->count)){
270 3302372 : free_layer(idp, **paa);
271 3302372 : **paa-- = NULL;
272 : }
273 1038766 : if ( ! *paa )
274 454964 : idp->layers = 0;
275 1038766 : return 0;
276 : }
277 0 : return -1;
278 : }
279 :
280 3354407 : static void *_idr_find(struct idr_context *idp, int id)
281 : {
282 55040 : int n;
283 55040 : struct idr_layer *p;
284 :
285 3354407 : n = idp->layers * IDR_BITS;
286 3354407 : 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 3354407 : if (n + IDR_BITS < 31 &&
292 2536081 : ((id & ~(~0U << MAX_ID_SHIFT)) >> (n + IDR_BITS))) {
293 5942 : return NULL;
294 : }
295 :
296 : /* Mask off upper bits we don't use for the search. */
297 3348358 : id &= MAX_ID_MASK;
298 :
299 17610050 : while (n >= IDR_BITS && p) {
300 14261692 : n -= IDR_BITS;
301 14261692 : p = p->ary[(id >> n) & IDR_MASK];
302 : }
303 3293425 : return((void *)p);
304 : }
305 :
306 1038766 : static int _idr_remove(struct idr_context *idp, int id)
307 : {
308 19468 : struct idr_layer *p;
309 :
310 : /* Mask off upper bits we don't use for the search. */
311 1038766 : id &= MAX_ID_MASK;
312 :
313 1038766 : if (sub_remove(idp, (idp->layers - 1) * IDR_BITS, id) == -1) {
314 0 : return -1;
315 : }
316 :
317 1038766 : if ( idp->top && idp->top->count == 1 &&
318 290914 : (idp->layers > 1) &&
319 258893 : idp->top->ary[0]) {
320 : /* We can drop a layer */
321 68536 : p = idp->top->ary[0];
322 68536 : idp->top->bitmap = idp->top->count = 0;
323 68536 : free_layer(idp, idp->top);
324 68536 : idp->top = p;
325 68536 : --idp->layers;
326 : }
327 2185428 : while (idp->id_free_cnt >= IDR_FREE_MAX) {
328 1146662 : p = alloc_layer(idp);
329 1146662 : talloc_free(p);
330 : }
331 1019298 : 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 887564 : _PUBLIC_ struct idr_context *idr_init(TALLOC_CTX *mem_ctx)
344 : {
345 887564 : 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 30179 : _PUBLIC_ int idr_get_new(struct idr_context *idp, void *ptr, int limit)
353 : {
354 30179 : int ret = idr_get_new_above_int(idp, ptr, 0);
355 30179 : if (ret > limit) {
356 0 : idr_remove(idp, ret);
357 0 : return -1;
358 : }
359 15845 : 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 1032266 : _PUBLIC_ int idr_get_new_above(struct idr_context *idp, void *ptr, int starting_id, int limit)
367 : {
368 1032266 : int ret = idr_get_new_above_int(idp, ptr, starting_id);
369 1032266 : if (ret > limit) {
370 2 : idr_remove(idp, ret);
371 2 : return -1;
372 : }
373 1002126 : return ret;
374 : }
375 :
376 : /**
377 : find a pointer value previously set with idr_get_new given an id
378 : */
379 3354407 : _PUBLIC_ void *idr_find(struct idr_context *idp, int id)
380 : {
381 3354407 : return _idr_find(idp, id);
382 : }
383 :
384 : /**
385 : remove an id from the idr tree
386 : */
387 1038766 : _PUBLIC_ int idr_remove(struct idr_context *idp, int id)
388 : {
389 19468 : int ret;
390 1038766 : ret = _idr_remove((struct idr_context *)idp, id);
391 1038766 : if (ret != 0) {
392 0 : DEBUG(0,("WARNING: attempt to remove unset id %d in idtree\n", id));
393 : }
394 1038766 : return ret;
395 : }
|
