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 511da177e4SLinus Torvalds static void free_layer(struct idr *idp, struct idr_layer *p) 521da177e4SLinus Torvalds { 531da177e4SLinus Torvalds /* 541da177e4SLinus Torvalds * Depends on the return element being zeroed. 551da177e4SLinus Torvalds */ 561da177e4SLinus Torvalds spin_lock(&idp->lock); 571da177e4SLinus Torvalds p->ary[0] = idp->id_free; 581da177e4SLinus Torvalds idp->id_free = p; 591da177e4SLinus Torvalds idp->id_free_cnt++; 601da177e4SLinus Torvalds spin_unlock(&idp->lock); 611da177e4SLinus Torvalds } 621da177e4SLinus Torvalds 631da177e4SLinus Torvalds /** 641da177e4SLinus Torvalds * idr_pre_get - reserver resources for idr allocation 651da177e4SLinus Torvalds * @idp: idr handle 661da177e4SLinus Torvalds * @gfp_mask: memory allocation flags 671da177e4SLinus Torvalds * 681da177e4SLinus Torvalds * This function should be called prior to locking and calling the 691da177e4SLinus Torvalds * following function. It preallocates enough memory to satisfy 701da177e4SLinus Torvalds * the worst possible allocation. 711da177e4SLinus Torvalds * 721da177e4SLinus Torvalds * If the system is REALLY out of memory this function returns 0, 731da177e4SLinus Torvalds * otherwise 1. 741da177e4SLinus Torvalds */ 751da177e4SLinus Torvalds int idr_pre_get(struct idr *idp, unsigned gfp_mask) 761da177e4SLinus Torvalds { 771da177e4SLinus Torvalds while (idp->id_free_cnt < IDR_FREE_MAX) { 781da177e4SLinus Torvalds struct idr_layer *new; 791da177e4SLinus Torvalds new = kmem_cache_alloc(idr_layer_cache, gfp_mask); 801da177e4SLinus Torvalds if(new == NULL) 811da177e4SLinus Torvalds return (0); 821da177e4SLinus Torvalds free_layer(idp, new); 831da177e4SLinus Torvalds } 841da177e4SLinus Torvalds return 1; 851da177e4SLinus Torvalds } 861da177e4SLinus Torvalds EXPORT_SYMBOL(idr_pre_get); 871da177e4SLinus Torvalds 881da177e4SLinus Torvalds static int sub_alloc(struct idr *idp, void *ptr, int *starting_id) 891da177e4SLinus Torvalds { 901da177e4SLinus Torvalds int n, m, sh; 911da177e4SLinus Torvalds struct idr_layer *p, *new; 921da177e4SLinus Torvalds struct idr_layer *pa[MAX_LEVEL]; 931da177e4SLinus Torvalds int l, id; 941da177e4SLinus Torvalds long bm; 951da177e4SLinus Torvalds 961da177e4SLinus Torvalds id = *starting_id; 971da177e4SLinus Torvalds p = idp->top; 981da177e4SLinus Torvalds l = idp->layers; 991da177e4SLinus Torvalds pa[l--] = NULL; 1001da177e4SLinus Torvalds while (1) { 1011da177e4SLinus Torvalds /* 1021da177e4SLinus Torvalds * We run around this while until we reach the leaf node... 1031da177e4SLinus Torvalds */ 1041da177e4SLinus Torvalds n = (id >> (IDR_BITS*l)) & IDR_MASK; 1051da177e4SLinus Torvalds bm = ~p->bitmap; 1061da177e4SLinus Torvalds m = find_next_bit(&bm, IDR_SIZE, n); 1071da177e4SLinus Torvalds if (m == IDR_SIZE) { 1081da177e4SLinus Torvalds /* no space available go back to previous layer. */ 1091da177e4SLinus Torvalds l++; 1101da177e4SLinus Torvalds id = (id | ((1 << (IDR_BITS*l))-1)) + 1; 1111da177e4SLinus Torvalds if (!(p = pa[l])) { 1121da177e4SLinus Torvalds *starting_id = id; 1131da177e4SLinus Torvalds return -2; 1141da177e4SLinus Torvalds } 1151da177e4SLinus Torvalds continue; 1161da177e4SLinus Torvalds } 1171da177e4SLinus Torvalds if (m != n) { 1181da177e4SLinus Torvalds sh = IDR_BITS*l; 1191da177e4SLinus Torvalds id = ((id >> sh) ^ n ^ m) << sh; 1201da177e4SLinus Torvalds } 1211da177e4SLinus Torvalds if ((id >= MAX_ID_BIT) || (id < 0)) 1221da177e4SLinus Torvalds return -3; 1231da177e4SLinus Torvalds if (l == 0) 1241da177e4SLinus Torvalds break; 1251da177e4SLinus Torvalds /* 1261da177e4SLinus Torvalds * Create the layer below if it is missing. 1271da177e4SLinus Torvalds */ 1281da177e4SLinus Torvalds if (!p->ary[m]) { 1291da177e4SLinus Torvalds if (!(new = alloc_layer(idp))) 1301da177e4SLinus Torvalds return -1; 1311da177e4SLinus Torvalds p->ary[m] = new; 1321da177e4SLinus Torvalds p->count++; 1331da177e4SLinus Torvalds } 1341da177e4SLinus Torvalds pa[l--] = p; 1351da177e4SLinus Torvalds p = p->ary[m]; 1361da177e4SLinus Torvalds } 1371da177e4SLinus Torvalds /* 1381da177e4SLinus Torvalds * We have reached the leaf node, plant the 1391da177e4SLinus Torvalds * users pointer and return the raw id. 1401da177e4SLinus Torvalds */ 1411da177e4SLinus Torvalds p->ary[m] = (struct idr_layer *)ptr; 1421da177e4SLinus Torvalds __set_bit(m, &p->bitmap); 1431da177e4SLinus Torvalds p->count++; 1441da177e4SLinus Torvalds /* 1451da177e4SLinus Torvalds * If this layer is full mark the bit in the layer above 1461da177e4SLinus Torvalds * to show that this part of the radix tree is full. 1471da177e4SLinus Torvalds * This may complete the layer above and require walking 1481da177e4SLinus Torvalds * up the radix tree. 1491da177e4SLinus Torvalds */ 1501da177e4SLinus Torvalds n = id; 1511da177e4SLinus Torvalds while (p->bitmap == IDR_FULL) { 1521da177e4SLinus Torvalds if (!(p = pa[++l])) 1531da177e4SLinus Torvalds break; 1541da177e4SLinus Torvalds n = n >> IDR_BITS; 1551da177e4SLinus Torvalds __set_bit((n & IDR_MASK), &p->bitmap); 1561da177e4SLinus Torvalds } 1571da177e4SLinus Torvalds return(id); 1581da177e4SLinus Torvalds } 1591da177e4SLinus Torvalds 1601da177e4SLinus Torvalds static int idr_get_new_above_int(struct idr *idp, void *ptr, int starting_id) 1611da177e4SLinus Torvalds { 1621da177e4SLinus Torvalds struct idr_layer *p, *new; 1631da177e4SLinus Torvalds int layers, v, id; 1641da177e4SLinus Torvalds 1651da177e4SLinus Torvalds id = starting_id; 1661da177e4SLinus Torvalds build_up: 1671da177e4SLinus Torvalds p = idp->top; 1681da177e4SLinus Torvalds layers = idp->layers; 1691da177e4SLinus Torvalds if (unlikely(!p)) { 1701da177e4SLinus Torvalds if (!(p = alloc_layer(idp))) 1711da177e4SLinus Torvalds return -1; 1721da177e4SLinus Torvalds layers = 1; 1731da177e4SLinus Torvalds } 1741da177e4SLinus Torvalds /* 1751da177e4SLinus Torvalds * Add a new layer to the top of the tree if the requested 1761da177e4SLinus Torvalds * id is larger than the currently allocated space. 1771da177e4SLinus Torvalds */ 178589777eaSZaur Kambarov while ((layers < (MAX_LEVEL - 1)) && (id >= (1 << (layers*IDR_BITS)))) { 1791da177e4SLinus Torvalds layers++; 1801da177e4SLinus Torvalds if (!p->count) 1811da177e4SLinus Torvalds continue; 1821da177e4SLinus Torvalds if (!(new = alloc_layer(idp))) { 1831da177e4SLinus Torvalds /* 1841da177e4SLinus Torvalds * The allocation failed. If we built part of 1851da177e4SLinus Torvalds * the structure tear it down. 1861da177e4SLinus Torvalds */ 1871da177e4SLinus Torvalds for (new = p; p && p != idp->top; new = p) { 1881da177e4SLinus Torvalds p = p->ary[0]; 1891da177e4SLinus Torvalds new->ary[0] = NULL; 1901da177e4SLinus Torvalds new->bitmap = new->count = 0; 1911da177e4SLinus Torvalds free_layer(idp, new); 1921da177e4SLinus Torvalds } 1931da177e4SLinus Torvalds return -1; 1941da177e4SLinus Torvalds } 1951da177e4SLinus Torvalds new->ary[0] = p; 1961da177e4SLinus Torvalds new->count = 1; 1971da177e4SLinus Torvalds if (p->bitmap == IDR_FULL) 1981da177e4SLinus Torvalds __set_bit(0, &new->bitmap); 1991da177e4SLinus Torvalds p = new; 2001da177e4SLinus Torvalds } 2011da177e4SLinus Torvalds idp->top = p; 2021da177e4SLinus Torvalds idp->layers = layers; 2031da177e4SLinus Torvalds v = sub_alloc(idp, ptr, &id); 2041da177e4SLinus Torvalds if (v == -2) 2051da177e4SLinus Torvalds goto build_up; 2061da177e4SLinus Torvalds return(v); 2071da177e4SLinus Torvalds } 2081da177e4SLinus Torvalds 2091da177e4SLinus Torvalds /** 2107c657f2fSJohn McCutchan * idr_get_new_above - allocate new idr entry above or equal to a start id 2111da177e4SLinus Torvalds * @idp: idr handle 2121da177e4SLinus Torvalds * @ptr: pointer you want associated with the ide 2131da177e4SLinus Torvalds * @start_id: id to start search at 2141da177e4SLinus Torvalds * @id: pointer to the allocated handle 2151da177e4SLinus Torvalds * 2161da177e4SLinus Torvalds * This is the allocate id function. It should be called with any 2171da177e4SLinus Torvalds * required locks. 2181da177e4SLinus Torvalds * 2191da177e4SLinus Torvalds * If memory is required, it will return -EAGAIN, you should unlock 2201da177e4SLinus Torvalds * and go back to the idr_pre_get() call. If the idr is full, it will 2211da177e4SLinus Torvalds * return -ENOSPC. 2221da177e4SLinus Torvalds * 2231da177e4SLinus Torvalds * @id returns a value in the range 0 ... 0x7fffffff 2241da177e4SLinus Torvalds */ 2251da177e4SLinus Torvalds int idr_get_new_above(struct idr *idp, void *ptr, int starting_id, int *id) 2261da177e4SLinus Torvalds { 2271da177e4SLinus Torvalds int rv; 2281da177e4SLinus Torvalds rv = idr_get_new_above_int(idp, ptr, starting_id); 2291da177e4SLinus Torvalds /* 2301da177e4SLinus Torvalds * This is a cheap hack until the IDR code can be fixed to 2311da177e4SLinus Torvalds * return proper error values. 2321da177e4SLinus Torvalds */ 2331da177e4SLinus Torvalds if (rv < 0) { 2341da177e4SLinus Torvalds if (rv == -1) 2351da177e4SLinus Torvalds return -EAGAIN; 2361da177e4SLinus Torvalds else /* Will be -3 */ 2371da177e4SLinus Torvalds return -ENOSPC; 2381da177e4SLinus Torvalds } 2391da177e4SLinus Torvalds *id = rv; 2401da177e4SLinus Torvalds return 0; 2411da177e4SLinus Torvalds } 2421da177e4SLinus Torvalds EXPORT_SYMBOL(idr_get_new_above); 2431da177e4SLinus Torvalds 2441da177e4SLinus Torvalds /** 2451da177e4SLinus Torvalds * idr_get_new - allocate new idr entry 2461da177e4SLinus Torvalds * @idp: idr handle 2471da177e4SLinus Torvalds * @ptr: pointer you want associated with the ide 2481da177e4SLinus Torvalds * @id: pointer to the allocated handle 2491da177e4SLinus Torvalds * 2501da177e4SLinus Torvalds * This is the allocate id function. It should be called with any 2511da177e4SLinus Torvalds * required locks. 2521da177e4SLinus Torvalds * 2531da177e4SLinus Torvalds * If memory is required, it will return -EAGAIN, you should unlock 2541da177e4SLinus Torvalds * and go back to the idr_pre_get() call. If the idr is full, it will 2551da177e4SLinus Torvalds * return -ENOSPC. 2561da177e4SLinus Torvalds * 2571da177e4SLinus Torvalds * @id returns a value in the range 0 ... 0x7fffffff 2581da177e4SLinus Torvalds */ 2591da177e4SLinus Torvalds int idr_get_new(struct idr *idp, void *ptr, int *id) 2601da177e4SLinus Torvalds { 2611da177e4SLinus Torvalds int rv; 2621da177e4SLinus Torvalds rv = idr_get_new_above_int(idp, ptr, 0); 2631da177e4SLinus Torvalds /* 2641da177e4SLinus Torvalds * This is a cheap hack until the IDR code can be fixed to 2651da177e4SLinus Torvalds * return proper error values. 2661da177e4SLinus Torvalds */ 2671da177e4SLinus Torvalds if (rv < 0) { 2681da177e4SLinus Torvalds if (rv == -1) 2691da177e4SLinus Torvalds return -EAGAIN; 2701da177e4SLinus Torvalds else /* Will be -3 */ 2711da177e4SLinus Torvalds return -ENOSPC; 2721da177e4SLinus Torvalds } 2731da177e4SLinus Torvalds *id = rv; 2741da177e4SLinus Torvalds return 0; 2751da177e4SLinus Torvalds } 2761da177e4SLinus Torvalds EXPORT_SYMBOL(idr_get_new); 2771da177e4SLinus Torvalds 2781da177e4SLinus Torvalds static void idr_remove_warning(int id) 2791da177e4SLinus Torvalds { 2801da177e4SLinus Torvalds printk("idr_remove called for id=%d which is not allocated.\n", id); 2811da177e4SLinus Torvalds dump_stack(); 2821da177e4SLinus Torvalds } 2831da177e4SLinus Torvalds 2841da177e4SLinus Torvalds static void sub_remove(struct idr *idp, int shift, int id) 2851da177e4SLinus Torvalds { 2861da177e4SLinus Torvalds struct idr_layer *p = idp->top; 2871da177e4SLinus Torvalds struct idr_layer **pa[MAX_LEVEL]; 2881da177e4SLinus Torvalds struct idr_layer ***paa = &pa[0]; 2891da177e4SLinus Torvalds int n; 2901da177e4SLinus Torvalds 2911da177e4SLinus Torvalds *paa = NULL; 2921da177e4SLinus Torvalds *++paa = &idp->top; 2931da177e4SLinus Torvalds 2941da177e4SLinus Torvalds while ((shift > 0) && p) { 2951da177e4SLinus Torvalds n = (id >> shift) & IDR_MASK; 2961da177e4SLinus Torvalds __clear_bit(n, &p->bitmap); 2971da177e4SLinus Torvalds *++paa = &p->ary[n]; 2981da177e4SLinus Torvalds p = p->ary[n]; 2991da177e4SLinus Torvalds shift -= IDR_BITS; 3001da177e4SLinus Torvalds } 3011da177e4SLinus Torvalds n = id & IDR_MASK; 3021da177e4SLinus Torvalds if (likely(p != NULL && test_bit(n, &p->bitmap))){ 3031da177e4SLinus Torvalds __clear_bit(n, &p->bitmap); 3041da177e4SLinus Torvalds p->ary[n] = NULL; 3051da177e4SLinus Torvalds while(*paa && ! --((**paa)->count)){ 3061da177e4SLinus Torvalds free_layer(idp, **paa); 3071da177e4SLinus Torvalds **paa-- = NULL; 3081da177e4SLinus Torvalds } 3091da177e4SLinus Torvalds if ( ! *paa ) 3101da177e4SLinus Torvalds idp->layers = 0; 3111da177e4SLinus Torvalds } else { 3121da177e4SLinus Torvalds idr_remove_warning(id); 3131da177e4SLinus Torvalds } 3141da177e4SLinus Torvalds } 3151da177e4SLinus Torvalds 3161da177e4SLinus Torvalds /** 3171da177e4SLinus Torvalds * idr_remove - remove the given id and free it's slot 3181da177e4SLinus Torvalds * idp: idr handle 3191da177e4SLinus Torvalds * id: uniqueue key 3201da177e4SLinus Torvalds */ 3211da177e4SLinus Torvalds void idr_remove(struct idr *idp, int id) 3221da177e4SLinus Torvalds { 3231da177e4SLinus Torvalds struct idr_layer *p; 3241da177e4SLinus Torvalds 3251da177e4SLinus Torvalds /* Mask off upper bits we don't use for the search. */ 3261da177e4SLinus Torvalds id &= MAX_ID_MASK; 3271da177e4SLinus Torvalds 3281da177e4SLinus Torvalds sub_remove(idp, (idp->layers - 1) * IDR_BITS, id); 3291da177e4SLinus Torvalds if ( idp->top && idp->top->count == 1 && 3301da177e4SLinus Torvalds (idp->layers > 1) && 3311da177e4SLinus Torvalds idp->top->ary[0]){ // We can drop a layer 3321da177e4SLinus Torvalds 3331da177e4SLinus Torvalds p = idp->top->ary[0]; 3341da177e4SLinus Torvalds idp->top->bitmap = idp->top->count = 0; 3351da177e4SLinus Torvalds free_layer(idp, idp->top); 3361da177e4SLinus Torvalds idp->top = p; 3371da177e4SLinus Torvalds --idp->layers; 3381da177e4SLinus Torvalds } 3391da177e4SLinus Torvalds while (idp->id_free_cnt >= IDR_FREE_MAX) { 3401da177e4SLinus Torvalds 3411da177e4SLinus Torvalds p = alloc_layer(idp); 3421da177e4SLinus Torvalds kmem_cache_free(idr_layer_cache, p); 3431da177e4SLinus Torvalds return; 3441da177e4SLinus Torvalds } 3451da177e4SLinus Torvalds } 3461da177e4SLinus Torvalds EXPORT_SYMBOL(idr_remove); 3471da177e4SLinus Torvalds 3481da177e4SLinus Torvalds /** 3498d3b3591SAndrew Morton * idr_destroy - release all cached layers within an idr tree 3508d3b3591SAndrew Morton * idp: idr handle 3518d3b3591SAndrew Morton */ 3528d3b3591SAndrew Morton void idr_destroy(struct idr *idp) 3538d3b3591SAndrew Morton { 3548d3b3591SAndrew Morton while (idp->id_free_cnt) { 3558d3b3591SAndrew Morton struct idr_layer *p = alloc_layer(idp); 3568d3b3591SAndrew Morton kmem_cache_free(idr_layer_cache, p); 3578d3b3591SAndrew Morton } 3588d3b3591SAndrew Morton } 3598d3b3591SAndrew Morton EXPORT_SYMBOL(idr_destroy); 3608d3b3591SAndrew Morton 3618d3b3591SAndrew Morton /** 3621da177e4SLinus Torvalds * idr_find - return pointer for given id 3631da177e4SLinus Torvalds * @idp: idr handle 3641da177e4SLinus Torvalds * @id: lookup key 3651da177e4SLinus Torvalds * 3661da177e4SLinus Torvalds * Return the pointer given the id it has been registered with. A %NULL 3671da177e4SLinus Torvalds * return indicates that @id is not valid or you passed %NULL in 3681da177e4SLinus Torvalds * idr_get_new(). 3691da177e4SLinus Torvalds * 3701da177e4SLinus Torvalds * The caller must serialize idr_find() vs idr_get_new() and idr_remove(). 3711da177e4SLinus Torvalds */ 3721da177e4SLinus Torvalds void *idr_find(struct idr *idp, int id) 3731da177e4SLinus Torvalds { 3741da177e4SLinus Torvalds int n; 3751da177e4SLinus Torvalds struct idr_layer *p; 3761da177e4SLinus Torvalds 3771da177e4SLinus Torvalds n = idp->layers * IDR_BITS; 3781da177e4SLinus Torvalds p = idp->top; 3791da177e4SLinus Torvalds 3801da177e4SLinus Torvalds /* Mask off upper bits we don't use for the search. */ 3811da177e4SLinus Torvalds id &= MAX_ID_MASK; 3821da177e4SLinus Torvalds 3831da177e4SLinus Torvalds if (id >= (1 << n)) 3841da177e4SLinus Torvalds return NULL; 3851da177e4SLinus Torvalds 3861da177e4SLinus Torvalds while (n > 0 && p) { 3871da177e4SLinus Torvalds n -= IDR_BITS; 3881da177e4SLinus Torvalds p = p->ary[(id >> n) & IDR_MASK]; 3891da177e4SLinus Torvalds } 3901da177e4SLinus Torvalds return((void *)p); 3911da177e4SLinus Torvalds } 3921da177e4SLinus Torvalds EXPORT_SYMBOL(idr_find); 3931da177e4SLinus Torvalds 3941da177e4SLinus Torvalds static void idr_cache_ctor(void * idr_layer, 3951da177e4SLinus Torvalds kmem_cache_t *idr_layer_cache, unsigned long flags) 3961da177e4SLinus Torvalds { 3971da177e4SLinus Torvalds memset(idr_layer, 0, sizeof(struct idr_layer)); 3981da177e4SLinus Torvalds } 3991da177e4SLinus Torvalds 4001da177e4SLinus Torvalds static int init_id_cache(void) 4011da177e4SLinus Torvalds { 4021da177e4SLinus Torvalds if (!idr_layer_cache) 4031da177e4SLinus Torvalds idr_layer_cache = kmem_cache_create("idr_layer_cache", 4041da177e4SLinus Torvalds sizeof(struct idr_layer), 0, 0, idr_cache_ctor, NULL); 4051da177e4SLinus Torvalds return 0; 4061da177e4SLinus Torvalds } 4071da177e4SLinus Torvalds 4081da177e4SLinus Torvalds /** 4091da177e4SLinus Torvalds * idr_init - initialize idr handle 4101da177e4SLinus Torvalds * @idp: idr handle 4111da177e4SLinus Torvalds * 4121da177e4SLinus Torvalds * This function is use to set up the handle (@idp) that you will pass 4131da177e4SLinus Torvalds * to the rest of the functions. 4141da177e4SLinus Torvalds */ 4151da177e4SLinus Torvalds void idr_init(struct idr *idp) 4161da177e4SLinus Torvalds { 4171da177e4SLinus Torvalds init_id_cache(); 4181da177e4SLinus Torvalds memset(idp, 0, sizeof(struct idr)); 4191da177e4SLinus Torvalds spin_lock_init(&idp->lock); 4201da177e4SLinus Torvalds } 4211da177e4SLinus Torvalds EXPORT_SYMBOL(idr_init); 422