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 4496076 : static struct idr_layer *alloc_layer(struct idr_context *idp)
71 : {
72 38366 : struct idr_layer *p;
73 :
74 4496076 : if (!(p = idp->id_free))
75 0 : return NULL;
76 4496076 : idp->id_free = p->ary[0];
77 4496076 : idp->id_free_cnt--;
78 4496076 : p->ary[0] = NULL;
79 4481085 : return p;
80 : }
81 :
82 4879148 : static int find_next_bit(uint32_t bm, int maxid, int n)
83 : {
84 14331617 : while (n<maxid && !test_bit(n, bm)) n++;
85 4879148 : return n;
86 : }
87 :
88 5381765 : static void free_layer(struct idr_context *idp, struct idr_layer *p)
89 : {
90 5381765 : p->ary[0] = idp->id_free;
91 5381765 : idp->id_free = p;
92 5381765 : idp->id_free_cnt++;
93 5367601 : }
94 :
95 1066164 : static int idr_pre_get(struct idr_context *idp)
96 : {
97 3055789 : while (idp->id_free_cnt < IDR_FREE_MAX) {
98 2033611 : struct idr_layer *pn = talloc_zero(idp, struct idr_layer);
99 2033611 : if(pn == NULL)
100 0 : return (0);
101 2080323 : free_layer(idp, pn);
102 : }
103 1019452 : return 1;
104 : }
105 :
106 1066181 : static int sub_alloc(struct idr_context *idp, void *ptr, int *starting_id)
107 : {
108 46712 : int n, m, sh;
109 46712 : struct idr_layer *p, *pn;
110 46712 : struct idr_layer *pa[MAX_LEVEL+1];
111 46712 : unsigned int l, id, oid;
112 46712 : uint32_t bm;
113 :
114 1066181 : memset(pa, 0, sizeof(pa));
115 :
116 1066181 : id = *starting_id;
117 1066235 : restart:
118 1066235 : p = idp->top;
119 1066235 : l = idp->layers;
120 1066235 : pa[l--] = NULL;
121 111765 : while (1) {
122 : /*
123 : * We run around this while until we reach the leaf node...
124 : */
125 4879148 : n = (id >> (IDR_BITS*l)) & IDR_MASK;
126 4879148 : bm = ~p->bitmap;
127 4879148 : m = find_next_bit(bm, IDR_SIZE, n);
128 4879148 : if (m == IDR_SIZE) {
129 : /* no space available go back to previous layer. */
130 183520 : l++;
131 183520 : oid = id;
132 183520 : id = (id | ((1 << (IDR_BITS*l))-1)) + 1;
133 :
134 : /* if already at the top layer, we need to grow */
135 183520 : 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 183503 : sh = IDR_BITS * (l + 1);
144 183503 : if (oid >> sh == id >> sh)
145 183449 : continue;
146 : else
147 54 : goto restart;
148 : }
149 4695628 : if (m != n) {
150 347728 : sh = IDR_BITS*l;
151 347728 : id = ((id >> sh) ^ n ^ m) << sh;
152 : }
153 4695628 : if (id >= MAX_ID_BIT)
154 0 : return -1;
155 4695628 : if (l == 0)
156 1019452 : break;
157 : /*
158 : * Create the layer below if it is missing.
159 : */
160 3629464 : if (!p->ary[m]) {
161 2852765 : if (!(pn = alloc_layer(idp)))
162 0 : return -1;
163 2852765 : p->ary[m] = pn;
164 2852765 : p->count++;
165 : }
166 3629464 : pa[l--] = p;
167 3629464 : 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 1066164 : p->ary[m] = (struct idr_layer *)ptr;
174 1066164 : set_bit(m, p->bitmap);
175 1066164 : 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 1066164 : n = id;
183 1069471 : while (p->bitmap == IDR_FULL) {
184 3307 : if (l >= MAX_LEVEL) {
185 0 : break;
186 : }
187 3307 : p = pa[++l];
188 3307 : if (p == NULL) {
189 0 : break;
190 : }
191 3307 : n = n >> IDR_BITS;
192 3307 : set_bit((n & IDR_MASK), p->bitmap);
193 : }
194 1019452 : return(id);
195 : }
196 :
197 1066164 : static int idr_get_new_above_int(struct idr_context *idp, void *ptr, int starting_id)
198 : {
199 46712 : struct idr_layer *p, *pn;
200 46712 : int layers, v, id;
201 :
202 1066164 : idr_pre_get(idp);
203 :
204 1066164 : id = starting_id;
205 1066181 : build_up:
206 1066181 : p = idp->top;
207 1066181 : layers = idp->layers;
208 1066181 : if (!p) {
209 455721 : if (!(p = alloc_layer(idp)))
210 0 : return -1;
211 451753 : 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 2097308 : while ((layers < MAX_LEVEL) && (id >= (1 << (layers*IDR_BITS)))) {
218 1031127 : layers++;
219 1031127 : if (!p->count)
220 993915 : continue;
221 37212 : 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 37212 : pn->ary[0] = p;
235 37212 : pn->count = 1;
236 37212 : if (p->bitmap == IDR_FULL)
237 0 : set_bit(0, pn->bitmap);
238 37072 : p = pn;
239 : }
240 1066181 : idp->top = p;
241 1066181 : idp->layers = layers;
242 1066181 : v = sub_alloc(idp, ptr, &id);
243 1066181 : if (v == -2)
244 17 : goto build_up;
245 1019452 : return(v);
246 : }
247 :
248 1042485 : static int sub_remove(struct idr_context *idp, int shift, int id)
249 : {
250 1042485 : struct idr_layer *p = idp->top;
251 21706 : struct idr_layer **pa[1+MAX_LEVEL];
252 1042485 : struct idr_layer ***paa = &pa[0];
253 21706 : int n;
254 :
255 1042485 : *paa = NULL;
256 1042485 : *++paa = &idp->top;
257 :
258 4476043 : while ((shift > 0) && p) {
259 3433558 : n = (id >> shift) & IDR_MASK;
260 3433558 : clear_bit(n, p->bitmap);
261 3433558 : *++paa = &p->ary[n];
262 3433558 : p = p->ary[n];
263 3433558 : shift -= IDR_BITS;
264 : }
265 1042485 : n = id & IDR_MASK;
266 1042485 : if (p != NULL && test_bit(n, p->bitmap)) {
267 1042485 : clear_bit(n, p->bitmap);
268 1042485 : p->ary[n] = NULL;
269 4353350 : while(*paa && ! --((**paa)->count)){
270 3310865 : free_layer(idp, **paa);
271 3310865 : **paa-- = NULL;
272 : }
273 1042485 : if ( ! *paa )
274 455981 : idp->layers = 0;
275 1042485 : return 0;
276 : }
277 0 : return -1;
278 : }
279 :
280 3362204 : static void *_idr_find(struct idr_context *idp, int id)
281 : {
282 58202 : int n;
283 58202 : struct idr_layer *p;
284 :
285 3362204 : n = idp->layers * IDR_BITS;
286 3362204 : 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 3362204 : if (n + IDR_BITS < 31 &&
292 2548883 : ((id & ~(~0U << MAX_ID_SHIFT)) >> (n + IDR_BITS))) {
293 6052 : return NULL;
294 : }
295 :
296 : /* Mask off upper bits we don't use for the search. */
297 3356044 : id &= MAX_ID_MASK;
298 :
299 17366434 : while (n >= IDR_BITS && p) {
300 14010390 : n -= IDR_BITS;
301 14010390 : p = p->ary[(id >> n) & IDR_MASK];
302 : }
303 3297950 : return((void *)p);
304 : }
305 :
306 1042485 : static int _idr_remove(struct idr_context *idp, int id)
307 : {
308 21706 : struct idr_layer *p;
309 :
310 : /* Mask off upper bits we don't use for the search. */
311 1042485 : id &= MAX_ID_MASK;
312 :
313 1042485 : if (sub_remove(idp, (idp->layers - 1) * IDR_BITS, id) == -1) {
314 0 : return -1;
315 : }
316 :
317 1042485 : if ( idp->top && idp->top->count == 1 &&
318 316105 : (idp->layers > 1) &&
319 283998 : idp->top->ary[0]) {
320 : /* We can drop a layer */
321 37289 : p = idp->top->ary[0];
322 37289 : idp->top->bitmap = idp->top->count = 0;
323 37289 : free_layer(idp, idp->top);
324 37289 : idp->top = p;
325 37289 : --idp->layers;
326 : }
327 2192863 : while (idp->id_free_cnt >= IDR_FREE_MAX) {
328 1150378 : p = alloc_layer(idp);
329 1150378 : talloc_free(p);
330 : }
331 1020779 : 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 903100 : _PUBLIC_ struct idr_context *idr_init(TALLOC_CTX *mem_ctx)
344 : {
345 903100 : 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 32600 : _PUBLIC_ int idr_get_new(struct idr_context *idp, void *ptr, int limit)
353 : {
354 32600 : int ret = idr_get_new_above_int(idp, ptr, 0);
355 32600 : if (ret > limit) {
356 0 : idr_remove(idp, ret);
357 0 : return -1;
358 : }
359 16038 : 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 1033564 : _PUBLIC_ int idr_get_new_above(struct idr_context *idp, void *ptr, int starting_id, int limit)
367 : {
368 1033564 : int ret = idr_get_new_above_int(idp, ptr, starting_id);
369 1033564 : if (ret > limit) {
370 2 : idr_remove(idp, ret);
371 2 : return -1;
372 : }
373 1003414 : return ret;
374 : }
375 :
376 : /**
377 : find a pointer value previously set with idr_get_new given an id
378 : */
379 3362204 : _PUBLIC_ void *idr_find(struct idr_context *idp, int id)
380 : {
381 3362204 : return _idr_find(idp, id);
382 : }
383 :
384 : /**
385 : remove an id from the idr tree
386 : */
387 1042485 : _PUBLIC_ int idr_remove(struct idr_context *idp, int id)
388 : {
389 21706 : int ret;
390 1042485 : ret = _idr_remove((struct idr_context *)idp, id);
391 1042485 : if (ret != 0) {
392 0 : DEBUG(0,("WARNING: attempt to remove unset id %d in idtree\n", id));
393 : }
394 1042485 : return ret;
395 : }
|
