← Back to branch summary

~zulcss/samba/server-dailies-3.4

« back to all changes in this revision

Viewing changes to lib/util/idtree.c

  • Committer: Chuck Short
  • Date: 2010-09-28 20:38:39 UTC
  • Revision ID: zulcss@ubuntu.com-20100928203839-pgjulytsi9ue63x1
Initial version

Show diffs side-by-side

added added

removed removed

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