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 325806f07cSJeff Mahoney #include <linux/err.h> 331da177e4SLinus Torvalds #include <linux/string.h> 341da177e4SLinus Torvalds #include <linux/idr.h> 351da177e4SLinus Torvalds 361da177e4SLinus Torvalds static kmem_cache_t *idr_layer_cache; 371da177e4SLinus Torvalds 381da177e4SLinus Torvalds static struct idr_layer *alloc_layer(struct idr *idp) 391da177e4SLinus Torvalds { 401da177e4SLinus Torvalds struct idr_layer *p; 41c259cc28SRoland Dreier unsigned long flags; 421da177e4SLinus Torvalds 43c259cc28SRoland Dreier spin_lock_irqsave(&idp->lock, flags); 441da177e4SLinus Torvalds if ((p = idp->id_free)) { 451da177e4SLinus Torvalds idp->id_free = p->ary[0]; 461da177e4SLinus Torvalds idp->id_free_cnt--; 471da177e4SLinus Torvalds p->ary[0] = NULL; 481da177e4SLinus Torvalds } 49c259cc28SRoland Dreier spin_unlock_irqrestore(&idp->lock, flags); 501da177e4SLinus Torvalds return(p); 511da177e4SLinus Torvalds } 521da177e4SLinus Torvalds 531eec0056SSonny Rao /* only called when idp->lock is held */ 541eec0056SSonny Rao static void __free_layer(struct idr *idp, struct idr_layer *p) 551eec0056SSonny Rao { 561eec0056SSonny Rao p->ary[0] = idp->id_free; 571eec0056SSonny Rao idp->id_free = p; 581eec0056SSonny Rao idp->id_free_cnt++; 591eec0056SSonny Rao } 601eec0056SSonny Rao 611da177e4SLinus Torvalds static void free_layer(struct idr *idp, struct idr_layer *p) 621da177e4SLinus Torvalds { 63c259cc28SRoland Dreier unsigned long flags; 64c259cc28SRoland Dreier 651da177e4SLinus Torvalds /* 661da177e4SLinus Torvalds * Depends on the return element being zeroed. 671da177e4SLinus Torvalds */ 68c259cc28SRoland Dreier spin_lock_irqsave(&idp->lock, flags); 691eec0056SSonny Rao __free_layer(idp, p); 70c259cc28SRoland Dreier spin_unlock_irqrestore(&idp->lock, flags); 711da177e4SLinus Torvalds } 721da177e4SLinus Torvalds 731da177e4SLinus Torvalds /** 741da177e4SLinus Torvalds * idr_pre_get - reserver resources for idr allocation 751da177e4SLinus Torvalds * @idp: idr handle 761da177e4SLinus Torvalds * @gfp_mask: memory allocation flags 771da177e4SLinus Torvalds * 781da177e4SLinus Torvalds * This function should be called prior to locking and calling the 791da177e4SLinus Torvalds * following function. It preallocates enough memory to satisfy 801da177e4SLinus Torvalds * the worst possible allocation. 811da177e4SLinus Torvalds * 821da177e4SLinus Torvalds * If the system is REALLY out of memory this function returns 0, 831da177e4SLinus Torvalds * otherwise 1. 841da177e4SLinus Torvalds */ 85fd4f2df2SAl Viro int idr_pre_get(struct idr *idp, gfp_t gfp_mask) 861da177e4SLinus Torvalds { 871da177e4SLinus Torvalds while (idp->id_free_cnt < IDR_FREE_MAX) { 881da177e4SLinus Torvalds struct idr_layer *new; 891da177e4SLinus Torvalds new = kmem_cache_alloc(idr_layer_cache, gfp_mask); 901da177e4SLinus Torvalds if (new == NULL) 911da177e4SLinus Torvalds return (0); 921da177e4SLinus Torvalds free_layer(idp, new); 931da177e4SLinus Torvalds } 941da177e4SLinus Torvalds return 1; 951da177e4SLinus Torvalds } 961da177e4SLinus Torvalds EXPORT_SYMBOL(idr_pre_get); 971da177e4SLinus Torvalds 981da177e4SLinus Torvalds static int sub_alloc(struct idr *idp, void *ptr, int *starting_id) 991da177e4SLinus Torvalds { 1001da177e4SLinus Torvalds int n, m, sh; 1011da177e4SLinus Torvalds struct idr_layer *p, *new; 1021da177e4SLinus Torvalds struct idr_layer *pa[MAX_LEVEL]; 1031da177e4SLinus Torvalds int l, id; 1041da177e4SLinus Torvalds long bm; 1051da177e4SLinus Torvalds 1061da177e4SLinus Torvalds id = *starting_id; 1071da177e4SLinus Torvalds p = idp->top; 1081da177e4SLinus Torvalds l = idp->layers; 1091da177e4SLinus Torvalds pa[l--] = NULL; 1101da177e4SLinus Torvalds while (1) { 1111da177e4SLinus Torvalds /* 1121da177e4SLinus Torvalds * We run around this while until we reach the leaf node... 1131da177e4SLinus Torvalds */ 1141da177e4SLinus Torvalds n = (id >> (IDR_BITS*l)) & IDR_MASK; 1151da177e4SLinus Torvalds bm = ~p->bitmap; 1161da177e4SLinus Torvalds m = find_next_bit(&bm, IDR_SIZE, n); 1171da177e4SLinus Torvalds if (m == IDR_SIZE) { 1181da177e4SLinus Torvalds /* no space available go back to previous layer. */ 1191da177e4SLinus Torvalds l++; 1201da177e4SLinus Torvalds id = (id | ((1 << (IDR_BITS * l)) - 1)) + 1; 1211da177e4SLinus Torvalds if (!(p = pa[l])) { 1221da177e4SLinus Torvalds *starting_id = id; 1231da177e4SLinus Torvalds return -2; 1241da177e4SLinus Torvalds } 1251da177e4SLinus Torvalds continue; 1261da177e4SLinus Torvalds } 1271da177e4SLinus Torvalds if (m != n) { 1281da177e4SLinus Torvalds sh = IDR_BITS*l; 1291da177e4SLinus Torvalds id = ((id >> sh) ^ n ^ m) << sh; 1301da177e4SLinus Torvalds } 1311da177e4SLinus Torvalds if ((id >= MAX_ID_BIT) || (id < 0)) 1321da177e4SLinus Torvalds return -3; 1331da177e4SLinus Torvalds if (l == 0) 1341da177e4SLinus Torvalds break; 1351da177e4SLinus Torvalds /* 1361da177e4SLinus Torvalds * Create the layer below if it is missing. 1371da177e4SLinus Torvalds */ 1381da177e4SLinus Torvalds if (!p->ary[m]) { 1391da177e4SLinus Torvalds if (!(new = alloc_layer(idp))) 1401da177e4SLinus Torvalds return -1; 1411da177e4SLinus Torvalds p->ary[m] = new; 1421da177e4SLinus Torvalds p->count++; 1431da177e4SLinus Torvalds } 1441da177e4SLinus Torvalds pa[l--] = p; 1451da177e4SLinus Torvalds p = p->ary[m]; 1461da177e4SLinus Torvalds } 1471da177e4SLinus Torvalds /* 1481da177e4SLinus Torvalds * We have reached the leaf node, plant the 1491da177e4SLinus Torvalds * users pointer and return the raw id. 1501da177e4SLinus Torvalds */ 1511da177e4SLinus Torvalds p->ary[m] = (struct idr_layer *)ptr; 1521da177e4SLinus Torvalds __set_bit(m, &p->bitmap); 1531da177e4SLinus Torvalds p->count++; 1541da177e4SLinus Torvalds /* 1551da177e4SLinus Torvalds * If this layer is full mark the bit in the layer above 1561da177e4SLinus Torvalds * to show that this part of the radix tree is full. 1571da177e4SLinus Torvalds * This may complete the layer above and require walking 1581da177e4SLinus Torvalds * up the radix tree. 1591da177e4SLinus Torvalds */ 1601da177e4SLinus Torvalds n = id; 1611da177e4SLinus Torvalds while (p->bitmap == IDR_FULL) { 1621da177e4SLinus Torvalds if (!(p = pa[++l])) 1631da177e4SLinus Torvalds break; 1641da177e4SLinus Torvalds n = n >> IDR_BITS; 1651da177e4SLinus Torvalds __set_bit((n & IDR_MASK), &p->bitmap); 1661da177e4SLinus Torvalds } 1671da177e4SLinus Torvalds return(id); 1681da177e4SLinus Torvalds } 1691da177e4SLinus Torvalds 1701da177e4SLinus Torvalds static int idr_get_new_above_int(struct idr *idp, void *ptr, int starting_id) 1711da177e4SLinus Torvalds { 1721da177e4SLinus Torvalds struct idr_layer *p, *new; 1731da177e4SLinus Torvalds int layers, v, id; 174c259cc28SRoland Dreier unsigned long flags; 1751da177e4SLinus Torvalds 1761da177e4SLinus Torvalds id = starting_id; 1771da177e4SLinus Torvalds build_up: 1781da177e4SLinus Torvalds p = idp->top; 1791da177e4SLinus Torvalds layers = idp->layers; 1801da177e4SLinus Torvalds if (unlikely(!p)) { 1811da177e4SLinus Torvalds if (!(p = alloc_layer(idp))) 1821da177e4SLinus Torvalds return -1; 1831da177e4SLinus Torvalds layers = 1; 1841da177e4SLinus Torvalds } 1851da177e4SLinus Torvalds /* 1861da177e4SLinus Torvalds * Add a new layer to the top of the tree if the requested 1871da177e4SLinus Torvalds * id is larger than the currently allocated space. 1881da177e4SLinus Torvalds */ 189589777eaSZaur Kambarov while ((layers < (MAX_LEVEL - 1)) && (id >= (1 << (layers*IDR_BITS)))) { 1901da177e4SLinus Torvalds layers++; 1911da177e4SLinus Torvalds if (!p->count) 1921da177e4SLinus Torvalds continue; 1931da177e4SLinus Torvalds if (!(new = alloc_layer(idp))) { 1941da177e4SLinus Torvalds /* 1951da177e4SLinus Torvalds * The allocation failed. If we built part of 1961da177e4SLinus Torvalds * the structure tear it down. 1971da177e4SLinus Torvalds */ 198c259cc28SRoland Dreier spin_lock_irqsave(&idp->lock, flags); 1991da177e4SLinus Torvalds for (new = p; p && p != idp->top; new = p) { 2001da177e4SLinus Torvalds p = p->ary[0]; 2011da177e4SLinus Torvalds new->ary[0] = NULL; 2021da177e4SLinus Torvalds new->bitmap = new->count = 0; 2031eec0056SSonny Rao __free_layer(idp, new); 2041da177e4SLinus Torvalds } 205c259cc28SRoland Dreier spin_unlock_irqrestore(&idp->lock, flags); 2061da177e4SLinus Torvalds return -1; 2071da177e4SLinus Torvalds } 2081da177e4SLinus Torvalds new->ary[0] = p; 2091da177e4SLinus Torvalds new->count = 1; 2101da177e4SLinus Torvalds if (p->bitmap == IDR_FULL) 2111da177e4SLinus Torvalds __set_bit(0, &new->bitmap); 2121da177e4SLinus Torvalds p = new; 2131da177e4SLinus Torvalds } 2141da177e4SLinus Torvalds idp->top = p; 2151da177e4SLinus Torvalds idp->layers = layers; 2161da177e4SLinus Torvalds v = sub_alloc(idp, ptr, &id); 2171da177e4SLinus Torvalds if (v == -2) 2181da177e4SLinus Torvalds goto build_up; 2191da177e4SLinus Torvalds return(v); 2201da177e4SLinus Torvalds } 2211da177e4SLinus Torvalds 2221da177e4SLinus Torvalds /** 2237c657f2fSJohn McCutchan * idr_get_new_above - allocate new idr entry above or equal to a start id 2241da177e4SLinus Torvalds * @idp: idr handle 2251da177e4SLinus Torvalds * @ptr: pointer you want associated with the ide 2261da177e4SLinus Torvalds * @start_id: id to start search at 2271da177e4SLinus Torvalds * @id: pointer to the allocated handle 2281da177e4SLinus Torvalds * 2291da177e4SLinus Torvalds * This is the allocate id function. It should be called with any 2301da177e4SLinus Torvalds * required locks. 2311da177e4SLinus Torvalds * 2321da177e4SLinus Torvalds * If memory is required, it will return -EAGAIN, you should unlock 2331da177e4SLinus Torvalds * and go back to the idr_pre_get() call. If the idr is full, it will 2341da177e4SLinus Torvalds * return -ENOSPC. 2351da177e4SLinus Torvalds * 2361da177e4SLinus Torvalds * @id returns a value in the range 0 ... 0x7fffffff 2371da177e4SLinus Torvalds */ 2381da177e4SLinus Torvalds int idr_get_new_above(struct idr *idp, void *ptr, int starting_id, int *id) 2391da177e4SLinus Torvalds { 2401da177e4SLinus Torvalds int rv; 241e15ae2ddSJesper Juhl 2421da177e4SLinus Torvalds rv = idr_get_new_above_int(idp, ptr, starting_id); 2431da177e4SLinus Torvalds /* 2441da177e4SLinus Torvalds * This is a cheap hack until the IDR code can be fixed to 2451da177e4SLinus Torvalds * return proper error values. 2461da177e4SLinus Torvalds */ 2471da177e4SLinus Torvalds if (rv < 0) { 2481da177e4SLinus Torvalds if (rv == -1) 2491da177e4SLinus Torvalds return -EAGAIN; 2501da177e4SLinus Torvalds else /* Will be -3 */ 2511da177e4SLinus Torvalds return -ENOSPC; 2521da177e4SLinus Torvalds } 2531da177e4SLinus Torvalds *id = rv; 2541da177e4SLinus Torvalds return 0; 2551da177e4SLinus Torvalds } 2561da177e4SLinus Torvalds EXPORT_SYMBOL(idr_get_new_above); 2571da177e4SLinus Torvalds 2581da177e4SLinus Torvalds /** 2591da177e4SLinus Torvalds * idr_get_new - allocate new idr entry 2601da177e4SLinus Torvalds * @idp: idr handle 2611da177e4SLinus Torvalds * @ptr: pointer you want associated with the ide 2621da177e4SLinus Torvalds * @id: pointer to the allocated handle 2631da177e4SLinus Torvalds * 2641da177e4SLinus Torvalds * This is the allocate id function. It should be called with any 2651da177e4SLinus Torvalds * required locks. 2661da177e4SLinus Torvalds * 2671da177e4SLinus Torvalds * If memory is required, it will return -EAGAIN, you should unlock 2681da177e4SLinus Torvalds * and go back to the idr_pre_get() call. If the idr is full, it will 2691da177e4SLinus Torvalds * return -ENOSPC. 2701da177e4SLinus Torvalds * 2711da177e4SLinus Torvalds * @id returns a value in the range 0 ... 0x7fffffff 2721da177e4SLinus Torvalds */ 2731da177e4SLinus Torvalds int idr_get_new(struct idr *idp, void *ptr, int *id) 2741da177e4SLinus Torvalds { 2751da177e4SLinus Torvalds int rv; 276e15ae2ddSJesper Juhl 2771da177e4SLinus Torvalds rv = idr_get_new_above_int(idp, ptr, 0); 2781da177e4SLinus Torvalds /* 2791da177e4SLinus Torvalds * This is a cheap hack until the IDR code can be fixed to 2801da177e4SLinus Torvalds * return proper error values. 2811da177e4SLinus Torvalds */ 2821da177e4SLinus Torvalds if (rv < 0) { 2831da177e4SLinus Torvalds if (rv == -1) 2841da177e4SLinus Torvalds return -EAGAIN; 2851da177e4SLinus Torvalds else /* Will be -3 */ 2861da177e4SLinus Torvalds return -ENOSPC; 2871da177e4SLinus Torvalds } 2881da177e4SLinus Torvalds *id = rv; 2891da177e4SLinus Torvalds return 0; 2901da177e4SLinus Torvalds } 2911da177e4SLinus Torvalds EXPORT_SYMBOL(idr_get_new); 2921da177e4SLinus Torvalds 2931da177e4SLinus Torvalds static void idr_remove_warning(int id) 2941da177e4SLinus Torvalds { 2951da177e4SLinus Torvalds printk("idr_remove called for id=%d which is not allocated.\n", id); 2961da177e4SLinus Torvalds dump_stack(); 2971da177e4SLinus Torvalds } 2981da177e4SLinus Torvalds 2991da177e4SLinus Torvalds static void sub_remove(struct idr *idp, int shift, int id) 3001da177e4SLinus Torvalds { 3011da177e4SLinus Torvalds struct idr_layer *p = idp->top; 3021da177e4SLinus Torvalds struct idr_layer **pa[MAX_LEVEL]; 3031da177e4SLinus Torvalds struct idr_layer ***paa = &pa[0]; 3041da177e4SLinus Torvalds int n; 3051da177e4SLinus Torvalds 3061da177e4SLinus Torvalds *paa = NULL; 3071da177e4SLinus Torvalds *++paa = &idp->top; 3081da177e4SLinus Torvalds 3091da177e4SLinus Torvalds while ((shift > 0) && p) { 3101da177e4SLinus Torvalds n = (id >> shift) & IDR_MASK; 3111da177e4SLinus Torvalds __clear_bit(n, &p->bitmap); 3121da177e4SLinus Torvalds *++paa = &p->ary[n]; 3131da177e4SLinus Torvalds p = p->ary[n]; 3141da177e4SLinus Torvalds shift -= IDR_BITS; 3151da177e4SLinus Torvalds } 3161da177e4SLinus Torvalds n = id & IDR_MASK; 3171da177e4SLinus Torvalds if (likely(p != NULL && test_bit(n, &p->bitmap))){ 3181da177e4SLinus Torvalds __clear_bit(n, &p->bitmap); 3191da177e4SLinus Torvalds p->ary[n] = NULL; 3201da177e4SLinus Torvalds while(*paa && ! --((**paa)->count)){ 3211da177e4SLinus Torvalds free_layer(idp, **paa); 3221da177e4SLinus Torvalds **paa-- = NULL; 3231da177e4SLinus Torvalds } 3241da177e4SLinus Torvalds if (!*paa) 3251da177e4SLinus Torvalds idp->layers = 0; 326e15ae2ddSJesper Juhl } else 3271da177e4SLinus Torvalds idr_remove_warning(id); 3281da177e4SLinus Torvalds } 3291da177e4SLinus Torvalds 3301da177e4SLinus Torvalds /** 3311da177e4SLinus Torvalds * idr_remove - remove the given id and free it's slot 3321da177e4SLinus Torvalds * idp: idr handle 3331da177e4SLinus Torvalds * id: uniqueue key 3341da177e4SLinus Torvalds */ 3351da177e4SLinus Torvalds void idr_remove(struct idr *idp, int id) 3361da177e4SLinus Torvalds { 3371da177e4SLinus Torvalds struct idr_layer *p; 3381da177e4SLinus Torvalds 3391da177e4SLinus Torvalds /* Mask off upper bits we don't use for the search. */ 3401da177e4SLinus Torvalds id &= MAX_ID_MASK; 3411da177e4SLinus Torvalds 3421da177e4SLinus Torvalds sub_remove(idp, (idp->layers - 1) * IDR_BITS, id); 343e15ae2ddSJesper Juhl if (idp->top && idp->top->count == 1 && (idp->layers > 1) && 3441da177e4SLinus Torvalds idp->top->ary[0]) { // We can drop a layer 3451da177e4SLinus Torvalds 3461da177e4SLinus Torvalds p = idp->top->ary[0]; 3471da177e4SLinus Torvalds idp->top->bitmap = idp->top->count = 0; 3481da177e4SLinus Torvalds free_layer(idp, idp->top); 3491da177e4SLinus Torvalds idp->top = p; 3501da177e4SLinus Torvalds --idp->layers; 3511da177e4SLinus Torvalds } 3521da177e4SLinus Torvalds while (idp->id_free_cnt >= IDR_FREE_MAX) { 3531da177e4SLinus Torvalds p = alloc_layer(idp); 3541da177e4SLinus Torvalds kmem_cache_free(idr_layer_cache, p); 3551da177e4SLinus Torvalds return; 3561da177e4SLinus Torvalds } 3571da177e4SLinus Torvalds } 3581da177e4SLinus Torvalds EXPORT_SYMBOL(idr_remove); 3591da177e4SLinus Torvalds 3601da177e4SLinus Torvalds /** 3618d3b3591SAndrew Morton * idr_destroy - release all cached layers within an idr tree 3628d3b3591SAndrew Morton * idp: idr handle 3638d3b3591SAndrew Morton */ 3648d3b3591SAndrew Morton void idr_destroy(struct idr *idp) 3658d3b3591SAndrew Morton { 3668d3b3591SAndrew Morton while (idp->id_free_cnt) { 3678d3b3591SAndrew Morton struct idr_layer *p = alloc_layer(idp); 3688d3b3591SAndrew Morton kmem_cache_free(idr_layer_cache, p); 3698d3b3591SAndrew Morton } 3708d3b3591SAndrew Morton } 3718d3b3591SAndrew Morton EXPORT_SYMBOL(idr_destroy); 3728d3b3591SAndrew Morton 3738d3b3591SAndrew Morton /** 3741da177e4SLinus Torvalds * idr_find - return pointer for given id 3751da177e4SLinus Torvalds * @idp: idr handle 3761da177e4SLinus Torvalds * @id: lookup key 3771da177e4SLinus Torvalds * 3781da177e4SLinus Torvalds * Return the pointer given the id it has been registered with. A %NULL 3791da177e4SLinus Torvalds * return indicates that @id is not valid or you passed %NULL in 3801da177e4SLinus Torvalds * idr_get_new(). 3811da177e4SLinus Torvalds * 3821da177e4SLinus Torvalds * The caller must serialize idr_find() vs idr_get_new() and idr_remove(). 3831da177e4SLinus Torvalds */ 3841da177e4SLinus Torvalds void *idr_find(struct idr *idp, int id) 3851da177e4SLinus Torvalds { 3861da177e4SLinus Torvalds int n; 3871da177e4SLinus Torvalds struct idr_layer *p; 3881da177e4SLinus Torvalds 3891da177e4SLinus Torvalds n = idp->layers * IDR_BITS; 3901da177e4SLinus Torvalds p = idp->top; 3911da177e4SLinus Torvalds 3921da177e4SLinus Torvalds /* Mask off upper bits we don't use for the search. */ 3931da177e4SLinus Torvalds id &= MAX_ID_MASK; 3941da177e4SLinus Torvalds 3951da177e4SLinus Torvalds if (id >= (1 << n)) 3961da177e4SLinus Torvalds return NULL; 3971da177e4SLinus Torvalds 3981da177e4SLinus Torvalds while (n > 0 && p) { 3991da177e4SLinus Torvalds n -= IDR_BITS; 4001da177e4SLinus Torvalds p = p->ary[(id >> n) & IDR_MASK]; 4011da177e4SLinus Torvalds } 4021da177e4SLinus Torvalds return((void *)p); 4031da177e4SLinus Torvalds } 4041da177e4SLinus Torvalds EXPORT_SYMBOL(idr_find); 4051da177e4SLinus Torvalds 4065806f07cSJeff Mahoney /** 4075806f07cSJeff Mahoney * idr_replace - replace pointer for given id 4085806f07cSJeff Mahoney * @idp: idr handle 4095806f07cSJeff Mahoney * @ptr: pointer you want associated with the id 4105806f07cSJeff Mahoney * @id: lookup key 4115806f07cSJeff Mahoney * 4125806f07cSJeff Mahoney * Replace the pointer registered with an id and return the old value. 4135806f07cSJeff Mahoney * A -ENOENT return indicates that @id was not found. 4145806f07cSJeff Mahoney * A -EINVAL return indicates that @id was not within valid constraints. 4155806f07cSJeff Mahoney * 4165806f07cSJeff Mahoney * The caller must serialize vs idr_find(), idr_get_new(), and idr_remove(). 4175806f07cSJeff Mahoney */ 4185806f07cSJeff Mahoney void *idr_replace(struct idr *idp, void *ptr, int id) 4195806f07cSJeff Mahoney { 4205806f07cSJeff Mahoney int n; 4215806f07cSJeff Mahoney struct idr_layer *p, *old_p; 4225806f07cSJeff Mahoney 4235806f07cSJeff Mahoney n = idp->layers * IDR_BITS; 4245806f07cSJeff Mahoney p = idp->top; 4255806f07cSJeff Mahoney 4265806f07cSJeff Mahoney id &= MAX_ID_MASK; 4275806f07cSJeff Mahoney 4285806f07cSJeff Mahoney if (id >= (1 << n)) 4295806f07cSJeff Mahoney return ERR_PTR(-EINVAL); 4305806f07cSJeff Mahoney 4315806f07cSJeff Mahoney n -= IDR_BITS; 4325806f07cSJeff Mahoney while ((n > 0) && p) { 4335806f07cSJeff Mahoney p = p->ary[(id >> n) & IDR_MASK]; 4345806f07cSJeff Mahoney n -= IDR_BITS; 4355806f07cSJeff Mahoney } 4365806f07cSJeff Mahoney 4375806f07cSJeff Mahoney n = id & IDR_MASK; 4385806f07cSJeff Mahoney if (unlikely(p == NULL || !test_bit(n, &p->bitmap))) 4395806f07cSJeff Mahoney return ERR_PTR(-ENOENT); 4405806f07cSJeff Mahoney 4415806f07cSJeff Mahoney old_p = p->ary[n]; 4425806f07cSJeff Mahoney p->ary[n] = ptr; 4435806f07cSJeff Mahoney 4445806f07cSJeff Mahoney return old_p; 4455806f07cSJeff Mahoney } 4465806f07cSJeff Mahoney EXPORT_SYMBOL(idr_replace); 4475806f07cSJeff Mahoney 448e15ae2ddSJesper Juhl static void idr_cache_ctor(void * idr_layer, kmem_cache_t *idr_layer_cache, 449e15ae2ddSJesper Juhl unsigned long flags) 4501da177e4SLinus Torvalds { 4511da177e4SLinus Torvalds memset(idr_layer, 0, sizeof(struct idr_layer)); 4521da177e4SLinus Torvalds } 4531da177e4SLinus Torvalds 4541da177e4SLinus Torvalds static int init_id_cache(void) 4551da177e4SLinus Torvalds { 4561da177e4SLinus Torvalds if (!idr_layer_cache) 4571da177e4SLinus Torvalds idr_layer_cache = kmem_cache_create("idr_layer_cache", 4581da177e4SLinus Torvalds sizeof(struct idr_layer), 0, 0, idr_cache_ctor, NULL); 4591da177e4SLinus Torvalds return 0; 4601da177e4SLinus Torvalds } 4611da177e4SLinus Torvalds 4621da177e4SLinus Torvalds /** 4631da177e4SLinus Torvalds * idr_init - initialize idr handle 4641da177e4SLinus Torvalds * @idp: idr handle 4651da177e4SLinus Torvalds * 4661da177e4SLinus Torvalds * This function is use to set up the handle (@idp) that you will pass 4671da177e4SLinus Torvalds * to the rest of the functions. 4681da177e4SLinus Torvalds */ 4691da177e4SLinus Torvalds void idr_init(struct idr *idp) 4701da177e4SLinus Torvalds { 4711da177e4SLinus Torvalds init_id_cache(); 4721da177e4SLinus Torvalds memset(idp, 0, sizeof(struct idr)); 4731da177e4SLinus Torvalds spin_lock_init(&idp->lock); 4741da177e4SLinus Torvalds } 4751da177e4SLinus Torvalds EXPORT_SYMBOL(idr_init); 476