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 4488693 : static struct idr_layer *alloc_layer(struct idr_context *idp)
71 : {
72 32299 : struct idr_layer *p;
73 :
74 4488693 : if (!(p = idp->id_free))
75 0 : return NULL;
76 4488693 : idp->id_free = p->ary[0];
77 4488693 : idp->id_free_cnt--;
78 4488693 : p->ary[0] = NULL;
79 4473812 : return p;
80 : }
81 :
82 4818802 : static int find_next_bit(uint32_t bm, int maxid, int n)
83 : {
84 14220092 : while (n<maxid && !test_bit(n, bm)) n++;
85 4818802 : return n;
86 : }
87 :
88 5360275 : static void free_layer(struct idr_context *idp, struct idr_layer *p)
89 : {
90 5360275 : p->ary[0] = idp->id_free;
91 5360275 : idp->id_free = p;
92 5360275 : idp->id_free_cnt++;
93 5346220 : }
94 :
95 1054445 : static int idr_pre_get(struct idr_context *idp)
96 : {
97 3023563 : while (idp->id_free_cnt < IDR_FREE_MAX) {
98 2007146 : struct idr_layer *pn = talloc_zero(idp, struct idr_layer);
99 2007146 : if(pn == NULL)
100 0 : return (0);
101 2047888 : free_layer(idp, pn);
102 : }
103 1013703 : return 1;
104 : }
105 :
106 1054462 : static int sub_alloc(struct idr_context *idp, void *ptr, int *starting_id)
107 : {
108 40742 : int n, m, sh;
109 40742 : struct idr_layer *p, *pn;
110 40742 : struct idr_layer *pa[MAX_LEVEL+1];
111 40742 : unsigned int l, id, oid;
112 40742 : uint32_t bm;
113 :
114 1054462 : memset(pa, 0, sizeof(pa));
115 :
116 1054462 : id = *starting_id;
117 1054499 : restart:
118 1054499 : p = idp->top;
119 1054499 : l = idp->layers;
120 1054499 : pa[l--] = NULL;
121 106142 : while (1) {
122 : /*
123 : * We run around this while until we reach the leaf node...
124 : */
125 4818802 : n = (id >> (IDR_BITS*l)) & IDR_MASK;
126 4818802 : bm = ~p->bitmap;
127 4818802 : m = find_next_bit(bm, IDR_SIZE, n);
128 4818802 : if (m == IDR_SIZE) {
129 : /* no space available go back to previous layer. */
130 183737 : l++;
131 183737 : oid = id;
132 183737 : id = (id | ((1 << (IDR_BITS*l))-1)) + 1;
133 :
134 : /* if already at the top layer, we need to grow */
135 183737 : 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 183720 : sh = IDR_BITS * (l + 1);
144 183720 : if (oid >> sh == id >> sh)
145 183683 : continue;
146 : else
147 37 : goto restart;
148 : }
149 4635065 : if (m != n) {
150 341687 : sh = IDR_BITS*l;
151 341687 : id = ((id >> sh) ^ n ^ m) << sh;
152 : }
153 4635065 : if (id >= MAX_ID_BIT)
154 0 : return -1;
155 4635065 : if (l == 0)
156 1013703 : break;
157 : /*
158 : * Create the layer below if it is missing.
159 : */
160 3580620 : if (!p->ary[m]) {
161 2828897 : if (!(pn = alloc_layer(idp)))
162 0 : return -1;
163 2828897 : p->ary[m] = pn;
164 2828897 : p->count++;
165 : }
166 3580620 : pa[l--] = p;
167 3580620 : 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 1054445 : p->ary[m] = (struct idr_layer *)ptr;
174 1054445 : set_bit(m, p->bitmap);
175 1054445 : 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 1054445 : n = id;
183 1057754 : while (p->bitmap == IDR_FULL) {
184 3309 : if (l >= MAX_LEVEL) {
185 0 : break;
186 : }
187 3309 : p = pa[++l];
188 3309 : if (p == NULL) {
189 0 : break;
190 : }
191 3309 : n = n >> IDR_BITS;
192 3309 : set_bit((n & IDR_MASK), p->bitmap);
193 : }
194 1013703 : return(id);
195 : }
196 :
197 1054445 : static int idr_get_new_above_int(struct idr_context *idp, void *ptr, int starting_id)
198 : {
199 40742 : struct idr_layer *p, *pn;
200 40742 : int layers, v, id;
201 :
202 1054445 : idr_pre_get(idp);
203 :
204 1054445 : id = starting_id;
205 1054462 : build_up:
206 1054462 : p = idp->top;
207 1054462 : layers = idp->layers;
208 1054462 : if (!p) {
209 451567 : if (!(p = alloc_layer(idp)))
210 0 : return -1;
211 447610 : 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 2107014 : while ((layers < MAX_LEVEL) && (id >= (1 << (layers*IDR_BITS)))) {
218 1052552 : layers++;
219 1052552 : if (!p->count)
220 982010 : continue;
221 70542 : 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 70542 : pn->ary[0] = p;
235 70542 : pn->count = 1;
236 70542 : if (p->bitmap == IDR_FULL)
237 0 : set_bit(0, pn->bitmap);
238 70413 : p = pn;
239 : }
240 1054462 : idp->top = p;
241 1054462 : idp->layers = layers;
242 1054462 : v = sub_alloc(idp, ptr, &id);
243 1054462 : if (v == -2)
244 17 : goto build_up;
245 1013703 : return(v);
246 : }
247 :
248 1030643 : static int sub_remove(struct idr_context *idp, int shift, int id)
249 : {
250 1030643 : struct idr_layer *p = idp->top;
251 15736 : struct idr_layer **pa[1+MAX_LEVEL];
252 1030643 : struct idr_layer ***paa = &pa[0];
253 15736 : int n;
254 :
255 1030643 : *paa = NULL;
256 1030643 : *++paa = &idp->top;
257 :
258 4414983 : while ((shift > 0) && p) {
259 3384340 : n = (id >> shift) & IDR_MASK;
260 3384340 : clear_bit(n, p->bitmap);
261 3384340 : *++paa = &p->ary[n];
262 3384340 : p = p->ary[n];
263 3384340 : shift -= IDR_BITS;
264 : }
265 1030643 : n = id & IDR_MASK;
266 1030643 : if (p != NULL && test_bit(n, p->bitmap)) {
267 1030643 : clear_bit(n, p->bitmap);
268 1030643 : p->ary[n] = NULL;
269 4313279 : while(*paa && ! --((**paa)->count)){
270 3282636 : free_layer(idp, **paa);
271 3282636 : **paa-- = NULL;
272 : }
273 1030643 : if ( ! *paa )
274 451756 : idp->layers = 0;
275 1030643 : return 0;
276 : }
277 0 : return -1;
278 : }
279 :
280 3331041 : static void *_idr_find(struct idr_context *idp, int id)
281 : {
282 42807 : int n;
283 42807 : struct idr_layer *p;
284 :
285 3331041 : n = idp->layers * IDR_BITS;
286 3331041 : 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 3331041 : if (n + IDR_BITS < 31 &&
292 2526916 : ((id & ~(~0U << MAX_ID_SHIFT)) >> (n + IDR_BITS))) {
293 5931 : return NULL;
294 : }
295 :
296 : /* Mask off upper bits we don't use for the search. */
297 3325002 : id &= MAX_ID_MASK;
298 :
299 17506420 : while (n >= IDR_BITS && p) {
300 14181418 : n -= IDR_BITS;
301 14181418 : p = p->ary[(id >> n) & IDR_MASK];
302 : }
303 3282303 : return((void *)p);
304 : }
305 :
306 1030643 : static int _idr_remove(struct idr_context *idp, int id)
307 : {
308 15736 : struct idr_layer *p;
309 :
310 : /* Mask off upper bits we don't use for the search. */
311 1030643 : id &= MAX_ID_MASK;
312 :
313 1030643 : if (sub_remove(idp, (idp->layers - 1) * IDR_BITS, id) == -1) {
314 0 : return -1;
315 : }
316 :
317 1030643 : if ( idp->top && idp->top->count == 1 &&
318 283363 : (idp->layers > 1) &&
319 251832 : idp->top->ary[0]) {
320 : /* We can drop a layer */
321 70493 : p = idp->top->ary[0];
322 70493 : idp->top->bitmap = idp->top->count = 0;
323 70493 : free_layer(idp, idp->top);
324 70493 : idp->top = p;
325 70493 : --idp->layers;
326 : }
327 2168330 : while (idp->id_free_cnt >= IDR_FREE_MAX) {
328 1137687 : p = alloc_layer(idp);
329 1137687 : talloc_free(p);
330 : }
331 1014907 : 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 887563 : _PUBLIC_ struct idr_context *idr_init(TALLOC_CTX *mem_ctx)
344 : {
345 887563 : 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 26553 : _PUBLIC_ int idr_get_new(struct idr_context *idp, void *ptr, int limit)
353 : {
354 26553 : int ret = idr_get_new_above_int(idp, ptr, 0);
355 26553 : if (ret > limit) {
356 0 : idr_remove(idp, ret);
357 0 : return -1;
358 : }
359 15955 : 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 1027892 : _PUBLIC_ int idr_get_new_above(struct idr_context *idp, void *ptr, int starting_id, int limit)
367 : {
368 1027892 : int ret = idr_get_new_above_int(idp, ptr, starting_id);
369 1027892 : if (ret > limit) {
370 2 : idr_remove(idp, ret);
371 2 : return -1;
372 : }
373 997748 : return ret;
374 : }
375 :
376 : /**
377 : find a pointer value previously set with idr_get_new given an id
378 : */
379 3331041 : _PUBLIC_ void *idr_find(struct idr_context *idp, int id)
380 : {
381 3331041 : return _idr_find(idp, id);
382 : }
383 :
384 : /**
385 : remove an id from the idr tree
386 : */
387 1030643 : _PUBLIC_ int idr_remove(struct idr_context *idp, int id)
388 : {
389 15736 : int ret;
390 1030643 : ret = _idr_remove((struct idr_context *)idp, id);
391 1030643 : if (ret != 0) {
392 0 : DEBUG(0,("WARNING: attempt to remove unset id %d in idtree\n", id));
393 : }
394 1030643 : return ret;
395 : }
|
