[PATCH] unify x86/x86-64 semaphore code
[linux-2.6.git] / lib / idr.c
1 /*
2  * 2002-10-18  written by Jim Houston jim.houston@ccur.com
3  *      Copyright (C) 2002 by Concurrent Computer Corporation
4  *      Distributed under the GNU GPL license version 2.
5  *
6  * Modified by George Anzinger to reuse immediately and to use
7  * find bit instructions.  Also removed _irq on spinlocks.
8  *
9  * Small id to pointer translation service.  
10  *
11  * It uses a radix tree like structure as a sparse array indexed 
12  * by the id to obtain the pointer.  The bitmap makes allocating
13  * a new id quick.  
14  *
15  * You call it to allocate an id (an int) an associate with that id a
16  * pointer or what ever, we treat it as a (void *).  You can pass this
17  * id to a user for him to pass back at a later time.  You then pass
18  * that id to this code and it returns your pointer.
19
20  * You can release ids at any time. When all ids are released, most of 
21  * the memory is returned (we keep IDR_FREE_MAX) in a local pool so we
22  * don't need to go to the memory "store" during an id allocate, just 
23  * so you don't need to be too concerned about locking and conflicts
24  * with the slab allocator.
25  */
26
27 #ifndef TEST                        // to test in user space...
28 #include <linux/slab.h>
29 #include <linux/init.h>
30 #include <linux/module.h>
31 #endif
32 #include <linux/string.h>
33 #include <linux/idr.h>
34
35 static kmem_cache_t *idr_layer_cache;
36
37 static struct idr_layer *alloc_layer(struct idr *idp)
38 {
39         struct idr_layer *p;
40
41         spin_lock(&idp->lock);
42         if ((p = idp->id_free)) {
43                 idp->id_free = p->ary[0];
44                 idp->id_free_cnt--;
45                 p->ary[0] = NULL;
46         }
47         spin_unlock(&idp->lock);
48         return(p);
49 }
50
51 static void free_layer(struct idr *idp, struct idr_layer *p)
52 {
53         /*
54          * Depends on the return element being zeroed.
55          */
56         spin_lock(&idp->lock);
57         p->ary[0] = idp->id_free;
58         idp->id_free = p;
59         idp->id_free_cnt++;
60         spin_unlock(&idp->lock);
61 }
62
63 /**
64  * idr_pre_get - reserver resources for idr allocation
65  * @idp:        idr handle
66  * @gfp_mask:   memory allocation flags
67  *
68  * This function should be called prior to locking and calling the
69  * following function.  It preallocates enough memory to satisfy
70  * the worst possible allocation.
71  *
72  * If the system is REALLY out of memory this function returns 0,
73  * otherwise 1.
74  */
75 int idr_pre_get(struct idr *idp, unsigned gfp_mask)
76 {
77         while (idp->id_free_cnt < IDR_FREE_MAX) {
78                 struct idr_layer *new;
79                 new = kmem_cache_alloc(idr_layer_cache, gfp_mask);
80                 if(new == NULL)
81                         return (0);
82                 free_layer(idp, new);
83         }
84         return 1;
85 }
86 EXPORT_SYMBOL(idr_pre_get);
87
88 static int sub_alloc(struct idr *idp, void *ptr, int *starting_id)
89 {
90         int n, m, sh;
91         struct idr_layer *p, *new;
92         struct idr_layer *pa[MAX_LEVEL];
93         int l, id;
94         long bm;
95
96         id = *starting_id;
97         p = idp->top;
98         l = idp->layers;
99         pa[l--] = NULL;
100         while (1) {
101                 /*
102                  * We run around this while until we reach the leaf node...
103                  */
104                 n = (id >> (IDR_BITS*l)) & IDR_MASK;
105                 bm = ~p->bitmap;
106                 m = find_next_bit(&bm, IDR_SIZE, n);
107                 if (m == IDR_SIZE) {
108                         /* no space available go back to previous layer. */
109                         l++;
110                         id = (id | ((1 << (IDR_BITS*l))-1)) + 1;
111                         if (!(p = pa[l])) {
112                                 *starting_id = id;
113                                 return -2;
114                         }
115                         continue;
116                 }
117                 if (m != n) {
118                         sh = IDR_BITS*l;
119                         id = ((id >> sh) ^ n ^ m) << sh;
120                 }
121                 if ((id >= MAX_ID_BIT) || (id < 0))
122                         return -3;
123                 if (l == 0)
124                         break;
125                 /*
126                  * Create the layer below if it is missing.
127                  */
128                 if (!p->ary[m]) {
129                         if (!(new = alloc_layer(idp)))
130                                 return -1;
131                         p->ary[m] = new;
132                         p->count++;
133                 }
134                 pa[l--] = p;
135                 p = p->ary[m];
136         }
137         /*
138          * We have reached the leaf node, plant the
139          * users pointer and return the raw id.
140          */
141         p->ary[m] = (struct idr_layer *)ptr;
142         __set_bit(m, &p->bitmap);
143         p->count++;
144         /*
145          * If this layer is full mark the bit in the layer above
146          * to show that this part of the radix tree is full.
147          * This may complete the layer above and require walking
148          * up the radix tree.
149          */
150         n = id;
151         while (p->bitmap == IDR_FULL) {
152                 if (!(p = pa[++l]))
153                         break;
154                 n = n >> IDR_BITS;
155                 __set_bit((n & IDR_MASK), &p->bitmap);
156         }
157         return(id);
158 }
159
160 static int idr_get_new_above_int(struct idr *idp, void *ptr, int starting_id)
161 {
162         struct idr_layer *p, *new;
163         int layers, v, id;
164         
165         id = starting_id;
166 build_up:
167         p = idp->top;
168         layers = idp->layers;
169         if (unlikely(!p)) {
170                 if (!(p = alloc_layer(idp)))
171                         return -1;
172                 layers = 1;
173         }
174         /*
175          * Add a new layer to the top of the tree if the requested
176          * id is larger than the currently allocated space.
177          */
178         while ((layers < (MAX_LEVEL - 1)) && (id >= (1 << (layers*IDR_BITS)))) {
179                 layers++;
180                 if (!p->count)
181                         continue;
182                 if (!(new = alloc_layer(idp))) {
183                         /*
184                          * The allocation failed.  If we built part of
185                          * the structure tear it down.
186                          */
187                         for (new = p; p && p != idp->top; new = p) {
188                                 p = p->ary[0];
189                                 new->ary[0] = NULL;
190                                 new->bitmap = new->count = 0;
191                                 free_layer(idp, new);
192                         }
193                         return -1;
194                 }
195                 new->ary[0] = p;
196                 new->count = 1;
197                 if (p->bitmap == IDR_FULL)
198                         __set_bit(0, &new->bitmap);
199                 p = new;
200         }
201         idp->top = p;
202         idp->layers = layers;
203         v = sub_alloc(idp, ptr, &id);
204         if (v == -2)
205                 goto build_up;
206         return(v);
207 }
208
209 /**
210  * idr_get_new_above - allocate new idr entry above or equal to a start id
211  * @idp: idr handle
212  * @ptr: pointer you want associated with the ide
213  * @start_id: id to start search at
214  * @id: pointer to the allocated handle
215  *
216  * This is the allocate id function.  It should be called with any
217  * required locks.
218  *
219  * If memory is required, it will return -EAGAIN, you should unlock
220  * and go back to the idr_pre_get() call.  If the idr is full, it will
221  * return -ENOSPC.
222  *
223  * @id returns a value in the range 0 ... 0x7fffffff
224  */
225 int idr_get_new_above(struct idr *idp, void *ptr, int starting_id, int *id)
226 {
227         int rv;
228         rv = idr_get_new_above_int(idp, ptr, starting_id);
229         /*
230          * This is a cheap hack until the IDR code can be fixed to
231          * return proper error values.
232          */
233         if (rv < 0) {
234                 if (rv == -1)
235                         return -EAGAIN;
236                 else /* Will be -3 */
237                         return -ENOSPC;
238         }
239         *id = rv;
240         return 0;
241 }
242 EXPORT_SYMBOL(idr_get_new_above);
243
244 /**
245  * idr_get_new - allocate new idr entry
246  * @idp: idr handle
247  * @ptr: pointer you want associated with the ide
248  * @id: pointer to the allocated handle
249  *
250  * This is the allocate id function.  It should be called with any
251  * required locks.
252  *
253  * If memory is required, it will return -EAGAIN, you should unlock
254  * and go back to the idr_pre_get() call.  If the idr is full, it will
255  * return -ENOSPC.
256  *
257  * @id returns a value in the range 0 ... 0x7fffffff
258  */
259 int idr_get_new(struct idr *idp, void *ptr, int *id)
260 {
261         int rv;
262         rv = idr_get_new_above_int(idp, ptr, 0);
263         /*
264          * This is a cheap hack until the IDR code can be fixed to
265          * return proper error values.
266          */
267         if (rv < 0) {
268                 if (rv == -1)
269                         return -EAGAIN;
270                 else /* Will be -3 */
271                         return -ENOSPC;
272         }
273         *id = rv;
274         return 0;
275 }
276 EXPORT_SYMBOL(idr_get_new);
277
278 static void idr_remove_warning(int id)
279 {
280         printk("idr_remove called for id=%d which is not allocated.\n", id);
281         dump_stack();
282 }
283
284 static void sub_remove(struct idr *idp, int shift, int id)
285 {
286         struct idr_layer *p = idp->top;
287         struct idr_layer **pa[MAX_LEVEL];
288         struct idr_layer ***paa = &pa[0];
289         int n;
290
291         *paa = NULL;
292         *++paa = &idp->top;
293
294         while ((shift > 0) && p) {
295                 n = (id >> shift) & IDR_MASK;
296                 __clear_bit(n, &p->bitmap);
297                 *++paa = &p->ary[n];
298                 p = p->ary[n];
299                 shift -= IDR_BITS;
300         }
301         n = id & IDR_MASK;
302         if (likely(p != NULL && test_bit(n, &p->bitmap))){
303                 __clear_bit(n, &p->bitmap);
304                 p->ary[n] = NULL;
305                 while(*paa && ! --((**paa)->count)){
306                         free_layer(idp, **paa);
307                         **paa-- = NULL;
308                 }
309                 if ( ! *paa )
310                         idp->layers = 0;
311         } else {
312                 idr_remove_warning(id);
313         }
314 }
315
316 /**
317  * idr_remove - remove the given id and free it's slot
318  * idp: idr handle
319  * id: uniqueue key
320  */
321 void idr_remove(struct idr *idp, int id)
322 {
323         struct idr_layer *p;
324
325         /* Mask off upper bits we don't use for the search. */
326         id &= MAX_ID_MASK;
327
328         sub_remove(idp, (idp->layers - 1) * IDR_BITS, id);
329         if ( idp->top && idp->top->count == 1 && 
330              (idp->layers > 1) &&
331              idp->top->ary[0]){  // We can drop a layer
332
333                 p = idp->top->ary[0];
334                 idp->top->bitmap = idp->top->count = 0;
335                 free_layer(idp, idp->top);
336                 idp->top = p;
337                 --idp->layers;
338         }
339         while (idp->id_free_cnt >= IDR_FREE_MAX) {
340                 
341                 p = alloc_layer(idp);
342                 kmem_cache_free(idr_layer_cache, p);
343                 return;
344         }
345 }
346 EXPORT_SYMBOL(idr_remove);
347
348 /**
349  * idr_find - return pointer for given id
350  * @idp: idr handle
351  * @id: lookup key
352  *
353  * Return the pointer given the id it has been registered with.  A %NULL
354  * return indicates that @id is not valid or you passed %NULL in
355  * idr_get_new().
356  *
357  * The caller must serialize idr_find() vs idr_get_new() and idr_remove().
358  */
359 void *idr_find(struct idr *idp, int id)
360 {
361         int n;
362         struct idr_layer *p;
363
364         n = idp->layers * IDR_BITS;
365         p = idp->top;
366
367         /* Mask off upper bits we don't use for the search. */
368         id &= MAX_ID_MASK;
369
370         if (id >= (1 << n))
371                 return NULL;
372
373         while (n > 0 && p) {
374                 n -= IDR_BITS;
375                 p = p->ary[(id >> n) & IDR_MASK];
376         }
377         return((void *)p);
378 }
379 EXPORT_SYMBOL(idr_find);
380
381 static void idr_cache_ctor(void * idr_layer, 
382                            kmem_cache_t *idr_layer_cache, unsigned long flags)
383 {
384         memset(idr_layer, 0, sizeof(struct idr_layer));
385 }
386
387 static  int init_id_cache(void)
388 {
389         if (!idr_layer_cache)
390                 idr_layer_cache = kmem_cache_create("idr_layer_cache", 
391                         sizeof(struct idr_layer), 0, 0, idr_cache_ctor, NULL);
392         return 0;
393 }
394
395 /**
396  * idr_init - initialize idr handle
397  * @idp:        idr handle
398  *
399  * This function is use to set up the handle (@idp) that you will pass
400  * to the rest of the functions.
401  */
402 void idr_init(struct idr *idp)
403 {
404         init_id_cache();
405         memset(idp, 0, sizeof(struct idr));
406         spin_lock_init(&idp->lock);
407 }
408 EXPORT_SYMBOL(idr_init);