11da177e4SLinus Torvalds /* 21da177e4SLinus Torvalds * 2002-10-18 written by Jim Houston jim.houston@ccur.com 31da177e4SLinus Torvalds * Copyright (C) 2002 by Concurrent Computer Corporation 41da177e4SLinus Torvalds * Distributed under the GNU GPL license version 2. 51da177e4SLinus Torvalds * 61da177e4SLinus Torvalds * Modified by George Anzinger to reuse immediately and to use 71da177e4SLinus Torvalds * find bit instructions. Also removed _irq on spinlocks. 81da177e4SLinus Torvalds * 91da177e4SLinus Torvalds * Small id to pointer translation service. 101da177e4SLinus Torvalds * 111da177e4SLinus Torvalds * It uses a radix tree like structure as a sparse array indexed 121da177e4SLinus Torvalds * by the id to obtain the pointer. The bitmap makes allocating 131da177e4SLinus Torvalds * a new id quick. 141da177e4SLinus Torvalds * 151da177e4SLinus Torvalds * You call it to allocate an id (an int) an associate with that id a 161da177e4SLinus Torvalds * pointer or what ever, we treat it as a (void *). You can pass this 171da177e4SLinus Torvalds * id to a user for him to pass back at a later time. You then pass 181da177e4SLinus Torvalds * that id to this code and it returns your pointer. 191da177e4SLinus Torvalds 201da177e4SLinus Torvalds * You can release ids at any time. When all ids are released, most of 211da177e4SLinus Torvalds * the memory is returned (we keep IDR_FREE_MAX) in a local pool so we 221da177e4SLinus Torvalds * don't need to go to the memory "store" during an id allocate, just 231da177e4SLinus Torvalds * so you don't need to be too concerned about locking and conflicts 241da177e4SLinus Torvalds * with the slab allocator. 251da177e4SLinus Torvalds */ 261da177e4SLinus Torvalds 271da177e4SLinus Torvalds #ifndef TEST // to test in user space... 281da177e4SLinus Torvalds #include <linux/slab.h> 291da177e4SLinus Torvalds #include <linux/init.h> 301da177e4SLinus Torvalds #include <linux/module.h> 311da177e4SLinus Torvalds #endif 321da177e4SLinus Torvalds #include <linux/string.h> 331da177e4SLinus Torvalds #include <linux/idr.h> 341da177e4SLinus Torvalds 351da177e4SLinus Torvalds static kmem_cache_t *idr_layer_cache; 361da177e4SLinus Torvalds 371da177e4SLinus Torvalds static struct idr_layer *alloc_layer(struct idr *idp) 381da177e4SLinus Torvalds { 391da177e4SLinus Torvalds struct idr_layer *p; 401da177e4SLinus Torvalds 411da177e4SLinus Torvalds spin_lock(&idp->lock); 421da177e4SLinus Torvalds if ((p = idp->id_free)) { 431da177e4SLinus Torvalds idp->id_free = p->ary[0]; 441da177e4SLinus Torvalds idp->id_free_cnt--; 451da177e4SLinus Torvalds p->ary[0] = NULL; 461da177e4SLinus Torvalds } 471da177e4SLinus Torvalds spin_unlock(&idp->lock); 481da177e4SLinus Torvalds return(p); 491da177e4SLinus Torvalds } 501da177e4SLinus Torvalds 511eec0056SSonny Rao /* only called when idp->lock is held */ 521eec0056SSonny Rao static void __free_layer(struct idr *idp, struct idr_layer *p) 531eec0056SSonny Rao { 541eec0056SSonny Rao p->ary[0] = idp->id_free; 551eec0056SSonny Rao idp->id_free = p; 561eec0056SSonny Rao idp->id_free_cnt++; 571eec0056SSonny Rao } 581eec0056SSonny Rao 591da177e4SLinus Torvalds static void free_layer(struct idr *idp, struct idr_layer *p) 601da177e4SLinus Torvalds { 611da177e4SLinus Torvalds /* 621da177e4SLinus Torvalds * Depends on the return element being zeroed. 631da177e4SLinus Torvalds */ 641da177e4SLinus Torvalds spin_lock(&idp->lock); 651eec0056SSonny Rao __free_layer(idp, p); 661da177e4SLinus Torvalds spin_unlock(&idp->lock); 671da177e4SLinus Torvalds } 681da177e4SLinus Torvalds 691da177e4SLinus Torvalds /** 701da177e4SLinus Torvalds * idr_pre_get - reserver resources for idr allocation 711da177e4SLinus Torvalds * @idp: idr handle 721da177e4SLinus Torvalds * @gfp_mask: memory allocation flags 731da177e4SLinus Torvalds * 741da177e4SLinus Torvalds * This function should be called prior to locking and calling the 751da177e4SLinus Torvalds * following function. It preallocates enough memory to satisfy 761da177e4SLinus Torvalds * the worst possible allocation. 771da177e4SLinus Torvalds * 781da177e4SLinus Torvalds * If the system is REALLY out of memory this function returns 0, 791da177e4SLinus Torvalds * otherwise 1. 801da177e4SLinus Torvalds */ 81fd4f2df2SAl Viro int idr_pre_get(struct idr *idp, gfp_t gfp_mask) 821da177e4SLinus Torvalds { 831da177e4SLinus Torvalds while (idp->id_free_cnt < IDR_FREE_MAX) { 841da177e4SLinus Torvalds struct idr_layer *new; 851da177e4SLinus Torvalds new = kmem_cache_alloc(idr_layer_cache, gfp_mask); 861da177e4SLinus Torvalds if (new == NULL) 871da177e4SLinus Torvalds return (0); 881da177e4SLinus Torvalds free_layer(idp, new); 891da177e4SLinus Torvalds } 901da177e4SLinus Torvalds return 1; 911da177e4SLinus Torvalds } 921da177e4SLinus Torvalds EXPORT_SYMBOL(idr_pre_get); 931da177e4SLinus Torvalds 941da177e4SLinus Torvalds static int sub_alloc(struct idr *idp, void *ptr, int *starting_id) 951da177e4SLinus Torvalds { 961da177e4SLinus Torvalds int n, m, sh; 971da177e4SLinus Torvalds struct idr_layer *p, *new; 981da177e4SLinus Torvalds struct idr_layer *pa[MAX_LEVEL]; 991da177e4SLinus Torvalds int l, id; 1001da177e4SLinus Torvalds long bm; 1011da177e4SLinus Torvalds 1021da177e4SLinus Torvalds id = *starting_id; 1031da177e4SLinus Torvalds p = idp->top; 1041da177e4SLinus Torvalds l = idp->layers; 1051da177e4SLinus Torvalds pa[l--] = NULL; 1061da177e4SLinus Torvalds while (1) { 1071da177e4SLinus Torvalds /* 1081da177e4SLinus Torvalds * We run around this while until we reach the leaf node... 1091da177e4SLinus Torvalds */ 1101da177e4SLinus Torvalds n = (id >> (IDR_BITS*l)) & IDR_MASK; 1111da177e4SLinus Torvalds bm = ~p->bitmap; 1121da177e4SLinus Torvalds m = find_next_bit(&bm, IDR_SIZE, n); 1131da177e4SLinus Torvalds if (m == IDR_SIZE) { 1141da177e4SLinus Torvalds /* no space available go back to previous layer. */ 1151da177e4SLinus Torvalds l++; 1161da177e4SLinus Torvalds id = (id | ((1 << (IDR_BITS * l)) - 1)) + 1; 1171da177e4SLinus Torvalds if (!(p = pa[l])) { 1181da177e4SLinus Torvalds *starting_id = id; 1191da177e4SLinus Torvalds return -2; 1201da177e4SLinus Torvalds } 1211da177e4SLinus Torvalds continue; 1221da177e4SLinus Torvalds } 1231da177e4SLinus Torvalds if (m != n) { 1241da177e4SLinus Torvalds sh = IDR_BITS*l; 1251da177e4SLinus Torvalds id = ((id >> sh) ^ n ^ m) << sh; 1261da177e4SLinus Torvalds } 1271da177e4SLinus Torvalds if ((id >= MAX_ID_BIT) || (id < 0)) 1281da177e4SLinus Torvalds return -3; 1291da177e4SLinus Torvalds if (l == 0) 1301da177e4SLinus Torvalds break; 1311da177e4SLinus Torvalds /* 1321da177e4SLinus Torvalds * Create the layer below if it is missing. 1331da177e4SLinus Torvalds */ 1341da177e4SLinus Torvalds if (!p->ary[m]) { 1351da177e4SLinus Torvalds if (!(new = alloc_layer(idp))) 1361da177e4SLinus Torvalds return -1; 1371da177e4SLinus Torvalds p->ary[m] = new; 1381da177e4SLinus Torvalds p->count++; 1391da177e4SLinus Torvalds } 1401da177e4SLinus Torvalds pa[l--] = p; 1411da177e4SLinus Torvalds p = p->ary[m]; 1421da177e4SLinus Torvalds } 1431da177e4SLinus Torvalds /* 1441da177e4SLinus Torvalds * We have reached the leaf node, plant the 1451da177e4SLinus Torvalds * users pointer and return the raw id. 1461da177e4SLinus Torvalds */ 1471da177e4SLinus Torvalds p->ary[m] = (struct idr_layer *)ptr; 1481da177e4SLinus Torvalds __set_bit(m, &p->bitmap); 1491da177e4SLinus Torvalds p->count++; 1501da177e4SLinus Torvalds /* 1511da177e4SLinus Torvalds * If this layer is full mark the bit in the layer above 1521da177e4SLinus Torvalds * to show that this part of the radix tree is full. 1531da177e4SLinus Torvalds * This may complete the layer above and require walking 1541da177e4SLinus Torvalds * up the radix tree. 1551da177e4SLinus Torvalds */ 1561da177e4SLinus Torvalds n = id; 1571da177e4SLinus Torvalds while (p->bitmap == IDR_FULL) { 1581da177e4SLinus Torvalds if (!(p = pa[++l])) 1591da177e4SLinus Torvalds break; 1601da177e4SLinus Torvalds n = n >> IDR_BITS; 1611da177e4SLinus Torvalds __set_bit((n & IDR_MASK), &p->bitmap); 1621da177e4SLinus Torvalds } 1631da177e4SLinus Torvalds return(id); 1641da177e4SLinus Torvalds } 1651da177e4SLinus Torvalds 1661da177e4SLinus Torvalds static int idr_get_new_above_int(struct idr *idp, void *ptr, int starting_id) 1671da177e4SLinus Torvalds { 1681da177e4SLinus Torvalds struct idr_layer *p, *new; 1691da177e4SLinus Torvalds int layers, v, id; 1701da177e4SLinus Torvalds 1711da177e4SLinus Torvalds id = starting_id; 1721da177e4SLinus Torvalds build_up: 1731da177e4SLinus Torvalds p = idp->top; 1741da177e4SLinus Torvalds layers = idp->layers; 1751da177e4SLinus Torvalds if (unlikely(!p)) { 1761da177e4SLinus Torvalds if (!(p = alloc_layer(idp))) 1771da177e4SLinus Torvalds return -1; 1781da177e4SLinus Torvalds layers = 1; 1791da177e4SLinus Torvalds } 1801da177e4SLinus Torvalds /* 1811da177e4SLinus Torvalds * Add a new layer to the top of the tree if the requested 1821da177e4SLinus Torvalds * id is larger than the currently allocated space. 1831da177e4SLinus Torvalds */ 184589777eaSZaur Kambarov while ((layers < (MAX_LEVEL - 1)) && (id >= (1 << (layers*IDR_BITS)))) { 1851da177e4SLinus Torvalds layers++; 1861da177e4SLinus Torvalds if (!p->count) 1871da177e4SLinus Torvalds continue; 1881da177e4SLinus Torvalds if (!(new = alloc_layer(idp))) { 1891da177e4SLinus Torvalds /* 1901da177e4SLinus Torvalds * The allocation failed. If we built part of 1911da177e4SLinus Torvalds * the structure tear it down. 1921da177e4SLinus Torvalds */ 1931eec0056SSonny Rao spin_lock(&idp->lock); 1941da177e4SLinus Torvalds for (new = p; p && p != idp->top; new = p) { 1951da177e4SLinus Torvalds p = p->ary[0]; 1961da177e4SLinus Torvalds new->ary[0] = NULL; 1971da177e4SLinus Torvalds new->bitmap = new->count = 0; 1981eec0056SSonny Rao __free_layer(idp, new); 1991da177e4SLinus Torvalds } 2001eec0056SSonny Rao spin_unlock(&idp->lock); 2011da177e4SLinus Torvalds return -1; 2021da177e4SLinus Torvalds } 2031da177e4SLinus Torvalds new->ary[0] = p; 2041da177e4SLinus Torvalds new->count = 1; 2051da177e4SLinus Torvalds if (p->bitmap == IDR_FULL) 2061da177e4SLinus Torvalds __set_bit(0, &new->bitmap); 2071da177e4SLinus Torvalds p = new; 2081da177e4SLinus Torvalds } 2091da177e4SLinus Torvalds idp->top = p; 2101da177e4SLinus Torvalds idp->layers = layers; 2111da177e4SLinus Torvalds v = sub_alloc(idp, ptr, &id); 2121da177e4SLinus Torvalds if (v == -2) 2131da177e4SLinus Torvalds goto build_up; 2141da177e4SLinus Torvalds return(v); 2151da177e4SLinus Torvalds } 2161da177e4SLinus Torvalds 2171da177e4SLinus Torvalds /** 2187c657f2fSJohn McCutchan * idr_get_new_above - allocate new idr entry above or equal to a start id 2191da177e4SLinus Torvalds * @idp: idr handle 2201da177e4SLinus Torvalds * @ptr: pointer you want associated with the ide 2211da177e4SLinus Torvalds * @start_id: id to start search at 2221da177e4SLinus Torvalds * @id: pointer to the allocated handle 2231da177e4SLinus Torvalds * 2241da177e4SLinus Torvalds * This is the allocate id function. It should be called with any 2251da177e4SLinus Torvalds * required locks. 2261da177e4SLinus Torvalds * 2271da177e4SLinus Torvalds * If memory is required, it will return -EAGAIN, you should unlock 2281da177e4SLinus Torvalds * and go back to the idr_pre_get() call. If the idr is full, it will 2291da177e4SLinus Torvalds * return -ENOSPC. 2301da177e4SLinus Torvalds * 2311da177e4SLinus Torvalds * @id returns a value in the range 0 ... 0x7fffffff 2321da177e4SLinus Torvalds */ 2331da177e4SLinus Torvalds int idr_get_new_above(struct idr *idp, void *ptr, int starting_id, int *id) 2341da177e4SLinus Torvalds { 2351da177e4SLinus Torvalds int rv; 236e15ae2ddSJesper Juhl 2371da177e4SLinus Torvalds rv = idr_get_new_above_int(idp, ptr, starting_id); 2381da177e4SLinus Torvalds /* 2391da177e4SLinus Torvalds * This is a cheap hack until the IDR code can be fixed to 2401da177e4SLinus Torvalds * return proper error values. 2411da177e4SLinus Torvalds */ 2421da177e4SLinus Torvalds if (rv < 0) { 2431da177e4SLinus Torvalds if (rv == -1) 2441da177e4SLinus Torvalds return -EAGAIN; 2451da177e4SLinus Torvalds else /* Will be -3 */ 2461da177e4SLinus Torvalds return -ENOSPC; 2471da177e4SLinus Torvalds } 2481da177e4SLinus Torvalds *id = rv; 2491da177e4SLinus Torvalds return 0; 2501da177e4SLinus Torvalds } 2511da177e4SLinus Torvalds EXPORT_SYMBOL(idr_get_new_above); 2521da177e4SLinus Torvalds 2531da177e4SLinus Torvalds /** 2541da177e4SLinus Torvalds * idr_get_new - allocate new idr entry 2551da177e4SLinus Torvalds * @idp: idr handle 2561da177e4SLinus Torvalds * @ptr: pointer you want associated with the ide 2571da177e4SLinus Torvalds * @id: pointer to the allocated handle 2581da177e4SLinus Torvalds * 2591da177e4SLinus Torvalds * This is the allocate id function. It should be called with any 2601da177e4SLinus Torvalds * required locks. 2611da177e4SLinus Torvalds * 2621da177e4SLinus Torvalds * If memory is required, it will return -EAGAIN, you should unlock 2631da177e4SLinus Torvalds * and go back to the idr_pre_get() call. If the idr is full, it will 2641da177e4SLinus Torvalds * return -ENOSPC. 2651da177e4SLinus Torvalds * 2661da177e4SLinus Torvalds * @id returns a value in the range 0 ... 0x7fffffff 2671da177e4SLinus Torvalds */ 2681da177e4SLinus Torvalds int idr_get_new(struct idr *idp, void *ptr, int *id) 2691da177e4SLinus Torvalds { 2701da177e4SLinus Torvalds int rv; 271e15ae2ddSJesper Juhl 2721da177e4SLinus Torvalds rv = idr_get_new_above_int(idp, ptr, 0); 2731da177e4SLinus Torvalds /* 2741da177e4SLinus Torvalds * This is a cheap hack until the IDR code can be fixed to 2751da177e4SLinus Torvalds * return proper error values. 2761da177e4SLinus Torvalds */ 2771da177e4SLinus Torvalds if (rv < 0) { 2781da177e4SLinus Torvalds if (rv == -1) 2791da177e4SLinus Torvalds return -EAGAIN; 2801da177e4SLinus Torvalds else /* Will be -3 */ 2811da177e4SLinus Torvalds return -ENOSPC; 2821da177e4SLinus Torvalds } 2831da177e4SLinus Torvalds *id = rv; 2841da177e4SLinus Torvalds return 0; 2851da177e4SLinus Torvalds } 2861da177e4SLinus Torvalds EXPORT_SYMBOL(idr_get_new); 2871da177e4SLinus Torvalds 2881da177e4SLinus Torvalds static void idr_remove_warning(int id) 2891da177e4SLinus Torvalds { 2901da177e4SLinus Torvalds printk("idr_remove called for id=%d which is not allocated.\n", id); 2911da177e4SLinus Torvalds dump_stack(); 2921da177e4SLinus Torvalds } 2931da177e4SLinus Torvalds 2941da177e4SLinus Torvalds static void sub_remove(struct idr *idp, int shift, int id) 2951da177e4SLinus Torvalds { 2961da177e4SLinus Torvalds struct idr_layer *p = idp->top; 2971da177e4SLinus Torvalds struct idr_layer **pa[MAX_LEVEL]; 2981da177e4SLinus Torvalds struct idr_layer ***paa = &pa[0]; 2991da177e4SLinus Torvalds int n; 3001da177e4SLinus Torvalds 3011da177e4SLinus Torvalds *paa = NULL; 3021da177e4SLinus Torvalds *++paa = &idp->top; 3031da177e4SLinus Torvalds 3041da177e4SLinus Torvalds while ((shift > 0) && p) { 3051da177e4SLinus Torvalds n = (id >> shift) & IDR_MASK; 3061da177e4SLinus Torvalds __clear_bit(n, &p->bitmap); 3071da177e4SLinus Torvalds *++paa = &p->ary[n]; 3081da177e4SLinus Torvalds p = p->ary[n]; 3091da177e4SLinus Torvalds shift -= IDR_BITS; 3101da177e4SLinus Torvalds } 3111da177e4SLinus Torvalds n = id & IDR_MASK; 3121da177e4SLinus Torvalds if (likely(p != NULL && test_bit(n, &p->bitmap))){ 3131da177e4SLinus Torvalds __clear_bit(n, &p->bitmap); 3141da177e4SLinus Torvalds p->ary[n] = NULL; 3151da177e4SLinus Torvalds while(*paa && ! --((**paa)->count)){ 3161da177e4SLinus Torvalds free_layer(idp, **paa); 3171da177e4SLinus Torvalds **paa-- = NULL; 3181da177e4SLinus Torvalds } 3191da177e4SLinus Torvalds if (!*paa) 3201da177e4SLinus Torvalds idp->layers = 0; 321e15ae2ddSJesper Juhl } else 3221da177e4SLinus Torvalds idr_remove_warning(id); 3231da177e4SLinus Torvalds } 3241da177e4SLinus Torvalds 3251da177e4SLinus Torvalds /** 3261da177e4SLinus Torvalds * idr_remove - remove the given id and free it's slot 3271da177e4SLinus Torvalds * idp: idr handle 3281da177e4SLinus Torvalds * id: uniqueue key 3291da177e4SLinus Torvalds */ 3301da177e4SLinus Torvalds void idr_remove(struct idr *idp, int id) 3311da177e4SLinus Torvalds { 3321da177e4SLinus Torvalds struct idr_layer *p; 3331da177e4SLinus Torvalds 3341da177e4SLinus Torvalds /* Mask off upper bits we don't use for the search. */ 3351da177e4SLinus Torvalds id &= MAX_ID_MASK; 3361da177e4SLinus Torvalds 3371da177e4SLinus Torvalds sub_remove(idp, (idp->layers - 1) * IDR_BITS, id); 338e15ae2ddSJesper Juhl if (idp->top && idp->top->count == 1 && (idp->layers > 1) && 3391da177e4SLinus Torvalds idp->top->ary[0]) { // We can drop a layer 3401da177e4SLinus Torvalds 3411da177e4SLinus Torvalds p = idp->top->ary[0]; 3421da177e4SLinus Torvalds idp->top->bitmap = idp->top->count = 0; 3431da177e4SLinus Torvalds free_layer(idp, idp->top); 3441da177e4SLinus Torvalds idp->top = p; 3451da177e4SLinus Torvalds --idp->layers; 3461da177e4SLinus Torvalds } 3471da177e4SLinus Torvalds while (idp->id_free_cnt >= IDR_FREE_MAX) { 3481da177e4SLinus Torvalds p = alloc_layer(idp); 3491da177e4SLinus Torvalds kmem_cache_free(idr_layer_cache, p); 3501da177e4SLinus Torvalds return; 3511da177e4SLinus Torvalds } 3521da177e4SLinus Torvalds } 3531da177e4SLinus Torvalds EXPORT_SYMBOL(idr_remove); 3541da177e4SLinus Torvalds 3551da177e4SLinus Torvalds /** 3568d3b3591SAndrew Morton * idr_destroy - release all cached layers within an idr tree 3578d3b3591SAndrew Morton * idp: idr handle 3588d3b3591SAndrew Morton */ 3598d3b3591SAndrew Morton void idr_destroy(struct idr *idp) 3608d3b3591SAndrew Morton { 3618d3b3591SAndrew Morton while (idp->id_free_cnt) { 3628d3b3591SAndrew Morton struct idr_layer *p = alloc_layer(idp); 3638d3b3591SAndrew Morton kmem_cache_free(idr_layer_cache, p); 3648d3b3591SAndrew Morton } 3658d3b3591SAndrew Morton } 3668d3b3591SAndrew Morton EXPORT_SYMBOL(idr_destroy); 3678d3b3591SAndrew Morton 3688d3b3591SAndrew Morton /** 3691da177e4SLinus Torvalds * idr_find - return pointer for given id 3701da177e4SLinus Torvalds * @idp: idr handle 3711da177e4SLinus Torvalds * @id: lookup key 3721da177e4SLinus Torvalds * 3731da177e4SLinus Torvalds * Return the pointer given the id it has been registered with. A %NULL 3741da177e4SLinus Torvalds * return indicates that @id is not valid or you passed %NULL in 3751da177e4SLinus Torvalds * idr_get_new(). 3761da177e4SLinus Torvalds * 3771da177e4SLinus Torvalds * The caller must serialize idr_find() vs idr_get_new() and idr_remove(). 3781da177e4SLinus Torvalds */ 3791da177e4SLinus Torvalds void *idr_find(struct idr *idp, int id) 3801da177e4SLinus Torvalds { 3811da177e4SLinus Torvalds int n; 3821da177e4SLinus Torvalds struct idr_layer *p; 3831da177e4SLinus Torvalds 3841da177e4SLinus Torvalds n = idp->layers * IDR_BITS; 3851da177e4SLinus Torvalds p = idp->top; 3861da177e4SLinus Torvalds 3871da177e4SLinus Torvalds /* Mask off upper bits we don't use for the search. */ 3881da177e4SLinus Torvalds id &= MAX_ID_MASK; 3891da177e4SLinus Torvalds 3901da177e4SLinus Torvalds if (id >= (1 << n)) 3911da177e4SLinus Torvalds return NULL; 3921da177e4SLinus Torvalds 3931da177e4SLinus Torvalds while (n > 0 && p) { 3941da177e4SLinus Torvalds n -= IDR_BITS; 3951da177e4SLinus Torvalds p = p->ary[(id >> n) & IDR_MASK]; 3961da177e4SLinus Torvalds } 3971da177e4SLinus Torvalds return((void *)p); 3981da177e4SLinus Torvalds } 3991da177e4SLinus Torvalds EXPORT_SYMBOL(idr_find); 4001da177e4SLinus Torvalds 401e15ae2ddSJesper Juhl static void idr_cache_ctor(void * idr_layer, kmem_cache_t *idr_layer_cache, 402e15ae2ddSJesper Juhl unsigned long flags) 4031da177e4SLinus Torvalds { 4041da177e4SLinus Torvalds memset(idr_layer, 0, sizeof(struct idr_layer)); 4051da177e4SLinus Torvalds } 4061da177e4SLinus Torvalds 4071da177e4SLinus Torvalds static int init_id_cache(void) 4081da177e4SLinus Torvalds { 4091da177e4SLinus Torvalds if (!idr_layer_cache) 4101da177e4SLinus Torvalds idr_layer_cache = kmem_cache_create("idr_layer_cache", 4111da177e4SLinus Torvalds sizeof(struct idr_layer), 0, 0, idr_cache_ctor, NULL); 4121da177e4SLinus Torvalds return 0; 4131da177e4SLinus Torvalds } 4141da177e4SLinus Torvalds 4151da177e4SLinus Torvalds /** 4161da177e4SLinus Torvalds * idr_init - initialize idr handle 4171da177e4SLinus Torvalds * @idp: idr handle 4181da177e4SLinus Torvalds * 4191da177e4SLinus Torvalds * This function is use to set up the handle (@idp) that you will pass 4201da177e4SLinus Torvalds * to the rest of the functions. 4211da177e4SLinus Torvalds */ 4221da177e4SLinus Torvalds void idr_init(struct idr *idp) 4231da177e4SLinus Torvalds { 4241da177e4SLinus Torvalds init_id_cache(); 4251da177e4SLinus Torvalds memset(idp, 0, sizeof(struct idr)); 4261da177e4SLinus Torvalds spin_lock_init(&idp->lock); 4271da177e4SLinus Torvalds } 4281da177e4SLinus Torvalds EXPORT_SYMBOL(idr_init); 429