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 4483112 : static struct idr_layer *alloc_layer(struct idr_context *idp)
71 : {
72 34792 : struct idr_layer *p;
73 :
74 4483112 : if (!(p = idp->id_free))
75 0 : return NULL;
76 4483112 : idp->id_free = p->ary[0];
77 4483112 : idp->id_free_cnt--;
78 4483112 : p->ary[0] = NULL;
79 4468148 : return p;
80 : }
81 :
82 4818921 : static int find_next_bit(uint32_t bm, int maxid, int n)
83 : {
84 14241393 : while (n<maxid && !test_bit(n, bm)) n++;
85 4818921 : return n;
86 : }
87 :
88 5371457 : static void free_layer(struct idr_context *idp, struct idr_layer *p)
89 : {
90 5371457 : p->ary[0] = idp->id_free;
91 5371457 : idp->id_free = p;
92 5371457 : idp->id_free_cnt++;
93 5357318 : }
94 :
95 1054395 : static int idr_pre_get(struct idr_context *idp)
96 : {
97 3038644 : while (idp->id_free_cnt < IDR_FREE_MAX) {
98 2024946 : struct idr_layer *pn = talloc_zero(idp, struct idr_layer);
99 2024946 : if(pn == NULL)
100 0 : return (0);
101 2068123 : free_layer(idp, pn);
102 : }
103 1011218 : return 1;
104 : }
105 :
106 1054412 : static int sub_alloc(struct idr_context *idp, void *ptr, int *starting_id)
107 : {
108 43177 : int n, m, sh;
109 43177 : struct idr_layer *p, *pn;
110 43177 : struct idr_layer *pa[MAX_LEVEL+1];
111 43177 : unsigned int l, id, oid;
112 43177 : uint32_t bm;
113 :
114 1054412 : memset(pa, 0, sizeof(pa));
115 :
116 1054412 : id = *starting_id;
117 1054452 : restart:
118 1054452 : p = idp->top;
119 1054452 : l = idp->layers;
120 1054452 : pa[l--] = NULL;
121 108251 : while (1) {
122 : /*
123 : * We run around this while until we reach the leaf node...
124 : */
125 4818921 : n = (id >> (IDR_BITS*l)) & IDR_MASK;
126 4818921 : bm = ~p->bitmap;
127 4818921 : m = find_next_bit(bm, IDR_SIZE, n);
128 4818921 : if (m == IDR_SIZE) {
129 : /* no space available go back to previous layer. */
130 183584 : l++;
131 183584 : oid = id;
132 183584 : id = (id | ((1 << (IDR_BITS*l))-1)) + 1;
133 :
134 : /* if already at the top layer, we need to grow */
135 183584 : 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 183567 : sh = IDR_BITS * (l + 1);
144 183567 : if (oid >> sh == id >> sh)
145 183527 : continue;
146 : else
147 40 : goto restart;
148 : }
149 4635337 : if (m != n) {
150 344646 : sh = IDR_BITS*l;
151 344646 : id = ((id >> sh) ^ n ^ m) << sh;
152 : }
153 4635337 : if (id >= MAX_ID_BIT)
154 0 : return -1;
155 4635337 : if (l == 0)
156 1011218 : break;
157 : /*
158 : * Create the layer below if it is missing.
159 : */
160 3580942 : if (!p->ary[m]) {
161 2831461 : if (!(pn = alloc_layer(idp)))
162 0 : return -1;
163 2831461 : p->ary[m] = pn;
164 2831461 : p->count++;
165 : }
166 3580942 : pa[l--] = p;
167 3580942 : 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 1054395 : p->ary[m] = (struct idr_layer *)ptr;
174 1054395 : set_bit(m, p->bitmap);
175 1054395 : 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 1054395 : n = id;
183 1057719 : while (p->bitmap == IDR_FULL) {
184 3324 : if (l >= MAX_LEVEL) {
185 0 : break;
186 : }
187 3324 : p = pa[++l];
188 3324 : if (p == NULL) {
189 0 : break;
190 : }
191 3324 : n = n >> IDR_BITS;
192 3324 : set_bit((n & IDR_MASK), p->bitmap);
193 : }
194 1011218 : return(id);
195 : }
196 :
197 1054395 : static int idr_get_new_above_int(struct idr_context *idp, void *ptr, int starting_id)
198 : {
199 43177 : struct idr_layer *p, *pn;
200 43177 : int layers, v, id;
201 :
202 1054395 : idr_pre_get(idp);
203 :
204 1054395 : id = starting_id;
205 1054412 : build_up:
206 1054412 : p = idp->top;
207 1054412 : layers = idp->layers;
208 1054412 : if (!p) {
209 447269 : if (!(p = alloc_layer(idp)))
210 0 : return -1;
211 443257 : 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 2091440 : while ((layers < MAX_LEVEL) && (id >= (1 << (layers*IDR_BITS)))) {
218 1037028 : layers++;
219 1037028 : if (!p->count)
220 971671 : continue;
221 65357 : 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 65357 : pn->ary[0] = p;
235 65357 : pn->count = 1;
236 65357 : if (p->bitmap == IDR_FULL)
237 0 : set_bit(0, pn->bitmap);
238 65207 : p = pn;
239 : }
240 1054412 : idp->top = p;
241 1054412 : idp->layers = layers;
242 1054412 : v = sub_alloc(idp, ptr, &id);
243 1054412 : if (v == -2)
244 17 : goto build_up;
245 1011218 : return(v);
246 : }
247 :
248 1030706 : static int sub_remove(struct idr_context *idp, int shift, int id)
249 : {
250 1030706 : struct idr_layer *p = idp->top;
251 18171 : struct idr_layer **pa[1+MAX_LEVEL];
252 1030706 : struct idr_layer ***paa = &pa[0];
253 18171 : int n;
254 :
255 1030706 : *paa = NULL;
256 1030706 : *++paa = &idp->top;
257 :
258 4415742 : while ((shift > 0) && p) {
259 3385036 : n = (id >> shift) & IDR_MASK;
260 3385036 : clear_bit(n, p->bitmap);
261 3385036 : *++paa = &p->ary[n];
262 3385036 : p = p->ary[n];
263 3385036 : shift -= IDR_BITS;
264 : }
265 1030706 : n = id & IDR_MASK;
266 1030706 : if (p != NULL && test_bit(n, p->bitmap)) {
267 1030706 : clear_bit(n, p->bitmap);
268 1030706 : p->ary[n] = NULL;
269 4311818 : while(*paa && ! --((**paa)->count)){
270 3281112 : free_layer(idp, **paa);
271 3281112 : **paa-- = NULL;
272 : }
273 1030706 : if ( ! *paa )
274 447521 : idp->layers = 0;
275 1030706 : return 0;
276 : }
277 0 : return -1;
278 : }
279 :
280 3355890 : static void *_idr_find(struct idr_context *idp, int id)
281 : {
282 52550 : int n;
283 52550 : struct idr_layer *p;
284 :
285 3355890 : n = idp->layers * IDR_BITS;
286 3355890 : 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 3355890 : if (n + IDR_BITS < 31 &&
292 2531722 : ((id & ~(~0U << MAX_ID_SHIFT)) >> (n + IDR_BITS))) {
293 6080 : return NULL;
294 : }
295 :
296 : /* Mask off upper bits we don't use for the search. */
297 3349701 : id &= MAX_ID_MASK;
298 :
299 17531896 : while (n >= IDR_BITS && p) {
300 14182195 : n -= IDR_BITS;
301 14182195 : p = p->ary[(id >> n) & IDR_MASK];
302 : }
303 3297260 : return((void *)p);
304 : }
305 :
306 1030706 : static int _idr_remove(struct idr_context *idp, int id)
307 : {
308 18171 : struct idr_layer *p;
309 :
310 : /* Mask off upper bits we don't use for the search. */
311 1030706 : id &= MAX_ID_MASK;
312 :
313 1030706 : if (sub_remove(idp, (idp->layers - 1) * IDR_BITS, id) == -1) {
314 0 : return -1;
315 : }
316 :
317 1030706 : if ( idp->top && idp->top->count == 1 &&
318 304756 : (idp->layers > 1) &&
319 272676 : idp->top->ary[0]) {
320 : /* We can drop a layer */
321 65399 : p = idp->top->ary[0];
322 65399 : idp->top->bitmap = idp->top->count = 0;
323 65399 : free_layer(idp, idp->top);
324 65399 : idp->top = p;
325 65399 : --idp->layers;
326 : }
327 2169731 : while (idp->id_free_cnt >= IDR_FREE_MAX) {
328 1139025 : p = alloc_layer(idp);
329 1139025 : talloc_free(p);
330 : }
331 1012535 : 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 902821 : _PUBLIC_ struct idr_context *idr_init(TALLOC_CTX *mem_ctx)
344 : {
345 902821 : 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 29211 : _PUBLIC_ int idr_get_new(struct idr_context *idp, void *ptr, int limit)
353 : {
354 29211 : int ret = idr_get_new_above_int(idp, ptr, 0);
355 29211 : if (ret > limit) {
356 0 : idr_remove(idp, ret);
357 0 : return -1;
358 : }
359 16221 : 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 1025184 : _PUBLIC_ int idr_get_new_above(struct idr_context *idp, void *ptr, int starting_id, int limit)
367 : {
368 1025184 : int ret = idr_get_new_above_int(idp, ptr, starting_id);
369 1025184 : if (ret > limit) {
370 2 : idr_remove(idp, ret);
371 2 : return -1;
372 : }
373 994997 : return ret;
374 : }
375 :
376 : /**
377 : find a pointer value previously set with idr_get_new given an id
378 : */
379 3355890 : _PUBLIC_ void *idr_find(struct idr_context *idp, int id)
380 : {
381 3355890 : return _idr_find(idp, id);
382 : }
383 :
384 : /**
385 : remove an id from the idr tree
386 : */
387 1030706 : _PUBLIC_ int idr_remove(struct idr_context *idp, int id)
388 : {
389 18171 : int ret;
390 1030706 : ret = _idr_remove((struct idr_context *)idp, id);
391 1030706 : if (ret != 0) {
392 0 : DEBUG(0,("WARNING: attempt to remove unset id %d in idtree\n", id));
393 : }
394 1030706 : return ret;
395 : }
|
