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 36e18b890bSChristoph Lameter static struct kmem_cache *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 73e33ac8bdSTejun Heo static void idr_mark_full(struct idr_layer **pa, int id) 74e33ac8bdSTejun Heo { 75e33ac8bdSTejun Heo struct idr_layer *p = pa[0]; 76e33ac8bdSTejun Heo int l = 0; 77e33ac8bdSTejun Heo 78e33ac8bdSTejun Heo __set_bit(id & IDR_MASK, &p->bitmap); 79e33ac8bdSTejun Heo /* 80e33ac8bdSTejun Heo * If this layer is full mark the bit in the layer above to 81e33ac8bdSTejun Heo * show that this part of the radix tree is full. This may 82e33ac8bdSTejun Heo * complete the layer above and require walking up the radix 83e33ac8bdSTejun Heo * tree. 84e33ac8bdSTejun Heo */ 85e33ac8bdSTejun Heo while (p->bitmap == IDR_FULL) { 86e33ac8bdSTejun Heo if (!(p = pa[++l])) 87e33ac8bdSTejun Heo break; 88e33ac8bdSTejun Heo id = id >> IDR_BITS; 89e33ac8bdSTejun Heo __set_bit((id & IDR_MASK), &p->bitmap); 90e33ac8bdSTejun Heo } 91e33ac8bdSTejun Heo } 92e33ac8bdSTejun Heo 931da177e4SLinus Torvalds /** 941da177e4SLinus Torvalds * idr_pre_get - reserver resources for idr allocation 951da177e4SLinus Torvalds * @idp: idr handle 961da177e4SLinus Torvalds * @gfp_mask: memory allocation flags 971da177e4SLinus Torvalds * 981da177e4SLinus Torvalds * This function should be called prior to locking and calling the 991da177e4SLinus Torvalds * following function. It preallocates enough memory to satisfy 1001da177e4SLinus Torvalds * the worst possible allocation. 1011da177e4SLinus Torvalds * 1021da177e4SLinus Torvalds * If the system is REALLY out of memory this function returns 0, 1031da177e4SLinus Torvalds * otherwise 1. 1041da177e4SLinus Torvalds */ 105fd4f2df2SAl Viro int idr_pre_get(struct idr *idp, gfp_t gfp_mask) 1061da177e4SLinus Torvalds { 1071da177e4SLinus Torvalds while (idp->id_free_cnt < IDR_FREE_MAX) { 1081da177e4SLinus Torvalds struct idr_layer *new; 1091da177e4SLinus Torvalds new = kmem_cache_alloc(idr_layer_cache, gfp_mask); 1101da177e4SLinus Torvalds if (new == NULL) 1111da177e4SLinus Torvalds return (0); 1121da177e4SLinus Torvalds free_layer(idp, new); 1131da177e4SLinus Torvalds } 1141da177e4SLinus Torvalds return 1; 1151da177e4SLinus Torvalds } 1161da177e4SLinus Torvalds EXPORT_SYMBOL(idr_pre_get); 1171da177e4SLinus Torvalds 118e33ac8bdSTejun Heo static int sub_alloc(struct idr *idp, int *starting_id, struct idr_layer **pa) 1191da177e4SLinus Torvalds { 1201da177e4SLinus Torvalds int n, m, sh; 1211da177e4SLinus Torvalds struct idr_layer *p, *new; 1227aae6dd8STejun Heo int l, id, oid; 1231da177e4SLinus Torvalds long bm; 1241da177e4SLinus Torvalds 1251da177e4SLinus Torvalds id = *starting_id; 1267aae6dd8STejun Heo restart: 1271da177e4SLinus Torvalds p = idp->top; 1281da177e4SLinus Torvalds l = idp->layers; 1291da177e4SLinus Torvalds pa[l--] = NULL; 1301da177e4SLinus Torvalds while (1) { 1311da177e4SLinus Torvalds /* 1321da177e4SLinus Torvalds * We run around this while until we reach the leaf node... 1331da177e4SLinus Torvalds */ 1341da177e4SLinus Torvalds n = (id >> (IDR_BITS*l)) & IDR_MASK; 1351da177e4SLinus Torvalds bm = ~p->bitmap; 1361da177e4SLinus Torvalds m = find_next_bit(&bm, IDR_SIZE, n); 1371da177e4SLinus Torvalds if (m == IDR_SIZE) { 1381da177e4SLinus Torvalds /* no space available go back to previous layer. */ 1391da177e4SLinus Torvalds l++; 1407aae6dd8STejun Heo oid = id; 1411da177e4SLinus Torvalds id = (id | ((1 << (IDR_BITS * l)) - 1)) + 1; 1427aae6dd8STejun Heo 1437aae6dd8STejun Heo /* if already at the top layer, we need to grow */ 1441da177e4SLinus Torvalds if (!(p = pa[l])) { 1451da177e4SLinus Torvalds *starting_id = id; 1461da177e4SLinus Torvalds return -2; 1471da177e4SLinus Torvalds } 1487aae6dd8STejun Heo 1497aae6dd8STejun Heo /* If we need to go up one layer, continue the 1507aae6dd8STejun Heo * loop; otherwise, restart from the top. 1517aae6dd8STejun Heo */ 1527aae6dd8STejun Heo sh = IDR_BITS * (l + 1); 1537aae6dd8STejun Heo if (oid >> sh == id >> sh) 1541da177e4SLinus Torvalds continue; 1557aae6dd8STejun Heo else 1567aae6dd8STejun Heo goto restart; 1571da177e4SLinus Torvalds } 1581da177e4SLinus Torvalds if (m != n) { 1591da177e4SLinus Torvalds sh = IDR_BITS*l; 1601da177e4SLinus Torvalds id = ((id >> sh) ^ n ^ m) << sh; 1611da177e4SLinus Torvalds } 1621da177e4SLinus Torvalds if ((id >= MAX_ID_BIT) || (id < 0)) 1631da177e4SLinus Torvalds return -3; 1641da177e4SLinus Torvalds if (l == 0) 1651da177e4SLinus Torvalds break; 1661da177e4SLinus Torvalds /* 1671da177e4SLinus Torvalds * Create the layer below if it is missing. 1681da177e4SLinus Torvalds */ 1691da177e4SLinus Torvalds if (!p->ary[m]) { 1701da177e4SLinus Torvalds if (!(new = alloc_layer(idp))) 1711da177e4SLinus Torvalds return -1; 1721da177e4SLinus Torvalds p->ary[m] = new; 1731da177e4SLinus Torvalds p->count++; 1741da177e4SLinus Torvalds } 1751da177e4SLinus Torvalds pa[l--] = p; 1761da177e4SLinus Torvalds p = p->ary[m]; 1771da177e4SLinus Torvalds } 178e33ac8bdSTejun Heo 179e33ac8bdSTejun Heo pa[l] = p; 180e33ac8bdSTejun Heo return id; 1811da177e4SLinus Torvalds } 1821da177e4SLinus Torvalds 183e33ac8bdSTejun Heo static int idr_get_empty_slot(struct idr *idp, int starting_id, 184e33ac8bdSTejun Heo struct idr_layer **pa) 1851da177e4SLinus Torvalds { 1861da177e4SLinus Torvalds struct idr_layer *p, *new; 1871da177e4SLinus Torvalds int layers, v, id; 188c259cc28SRoland Dreier unsigned long flags; 1891da177e4SLinus Torvalds 1901da177e4SLinus Torvalds id = starting_id; 1911da177e4SLinus Torvalds build_up: 1921da177e4SLinus Torvalds p = idp->top; 1931da177e4SLinus Torvalds layers = idp->layers; 1941da177e4SLinus Torvalds if (unlikely(!p)) { 1951da177e4SLinus Torvalds if (!(p = alloc_layer(idp))) 1961da177e4SLinus Torvalds return -1; 1971da177e4SLinus Torvalds layers = 1; 1981da177e4SLinus Torvalds } 1991da177e4SLinus Torvalds /* 2001da177e4SLinus Torvalds * Add a new layer to the top of the tree if the requested 2011da177e4SLinus Torvalds * id is larger than the currently allocated space. 2021da177e4SLinus Torvalds */ 203589777eaSZaur Kambarov while ((layers < (MAX_LEVEL - 1)) && (id >= (1 << (layers*IDR_BITS)))) { 2041da177e4SLinus Torvalds layers++; 2051da177e4SLinus Torvalds if (!p->count) 2061da177e4SLinus Torvalds continue; 2071da177e4SLinus Torvalds if (!(new = alloc_layer(idp))) { 2081da177e4SLinus Torvalds /* 2091da177e4SLinus Torvalds * The allocation failed. If we built part of 2101da177e4SLinus Torvalds * the structure tear it down. 2111da177e4SLinus Torvalds */ 212c259cc28SRoland Dreier spin_lock_irqsave(&idp->lock, flags); 2131da177e4SLinus Torvalds for (new = p; p && p != idp->top; new = p) { 2141da177e4SLinus Torvalds p = p->ary[0]; 2151da177e4SLinus Torvalds new->ary[0] = NULL; 2161da177e4SLinus Torvalds new->bitmap = new->count = 0; 2171eec0056SSonny Rao __free_layer(idp, new); 2181da177e4SLinus Torvalds } 219c259cc28SRoland Dreier spin_unlock_irqrestore(&idp->lock, flags); 2201da177e4SLinus Torvalds return -1; 2211da177e4SLinus Torvalds } 2221da177e4SLinus Torvalds new->ary[0] = p; 2231da177e4SLinus Torvalds new->count = 1; 2241da177e4SLinus Torvalds if (p->bitmap == IDR_FULL) 2251da177e4SLinus Torvalds __set_bit(0, &new->bitmap); 2261da177e4SLinus Torvalds p = new; 2271da177e4SLinus Torvalds } 2281da177e4SLinus Torvalds idp->top = p; 2291da177e4SLinus Torvalds idp->layers = layers; 230e33ac8bdSTejun Heo v = sub_alloc(idp, &id, pa); 2311da177e4SLinus Torvalds if (v == -2) 2321da177e4SLinus Torvalds goto build_up; 2331da177e4SLinus Torvalds return(v); 2341da177e4SLinus Torvalds } 2351da177e4SLinus Torvalds 236e33ac8bdSTejun Heo static int idr_get_new_above_int(struct idr *idp, void *ptr, int starting_id) 237e33ac8bdSTejun Heo { 238e33ac8bdSTejun Heo struct idr_layer *pa[MAX_LEVEL]; 239e33ac8bdSTejun Heo int id; 240e33ac8bdSTejun Heo 241e33ac8bdSTejun Heo id = idr_get_empty_slot(idp, starting_id, pa); 242e33ac8bdSTejun Heo if (id >= 0) { 243e33ac8bdSTejun Heo /* 244e33ac8bdSTejun Heo * Successfully found an empty slot. Install the user 245e33ac8bdSTejun Heo * pointer and mark the slot full. 246e33ac8bdSTejun Heo */ 247e33ac8bdSTejun Heo pa[0]->ary[id & IDR_MASK] = (struct idr_layer *)ptr; 248e33ac8bdSTejun Heo pa[0]->count++; 249e33ac8bdSTejun Heo idr_mark_full(pa, id); 250e33ac8bdSTejun Heo } 251e33ac8bdSTejun Heo 252e33ac8bdSTejun Heo return id; 253e33ac8bdSTejun Heo } 254e33ac8bdSTejun Heo 2551da177e4SLinus Torvalds /** 2567c657f2fSJohn McCutchan * idr_get_new_above - allocate new idr entry above or equal to a start id 2571da177e4SLinus Torvalds * @idp: idr handle 2581da177e4SLinus Torvalds * @ptr: pointer you want associated with the ide 2591da177e4SLinus Torvalds * @start_id: id to start search at 2601da177e4SLinus Torvalds * @id: pointer to the allocated handle 2611da177e4SLinus Torvalds * 2621da177e4SLinus Torvalds * This is the allocate id function. It should be called with any 2631da177e4SLinus Torvalds * required locks. 2641da177e4SLinus Torvalds * 2651da177e4SLinus Torvalds * If memory is required, it will return -EAGAIN, you should unlock 2661da177e4SLinus Torvalds * and go back to the idr_pre_get() call. If the idr is full, it will 2671da177e4SLinus Torvalds * return -ENOSPC. 2681da177e4SLinus Torvalds * 2691da177e4SLinus Torvalds * @id returns a value in the range 0 ... 0x7fffffff 2701da177e4SLinus Torvalds */ 2711da177e4SLinus Torvalds int idr_get_new_above(struct idr *idp, void *ptr, int starting_id, int *id) 2721da177e4SLinus Torvalds { 2731da177e4SLinus Torvalds int rv; 274e15ae2ddSJesper Juhl 2751da177e4SLinus Torvalds rv = idr_get_new_above_int(idp, ptr, starting_id); 2761da177e4SLinus Torvalds /* 2771da177e4SLinus Torvalds * This is a cheap hack until the IDR code can be fixed to 2781da177e4SLinus Torvalds * return proper error values. 2791da177e4SLinus Torvalds */ 2801da177e4SLinus Torvalds if (rv < 0) { 2811da177e4SLinus Torvalds if (rv == -1) 2821da177e4SLinus Torvalds return -EAGAIN; 2831da177e4SLinus Torvalds else /* Will be -3 */ 2841da177e4SLinus Torvalds return -ENOSPC; 2851da177e4SLinus Torvalds } 2861da177e4SLinus Torvalds *id = rv; 2871da177e4SLinus Torvalds return 0; 2881da177e4SLinus Torvalds } 2891da177e4SLinus Torvalds EXPORT_SYMBOL(idr_get_new_above); 2901da177e4SLinus Torvalds 2911da177e4SLinus Torvalds /** 2921da177e4SLinus Torvalds * idr_get_new - allocate new idr entry 2931da177e4SLinus Torvalds * @idp: idr handle 2941da177e4SLinus Torvalds * @ptr: pointer you want associated with the ide 2951da177e4SLinus Torvalds * @id: pointer to the allocated handle 2961da177e4SLinus Torvalds * 2971da177e4SLinus Torvalds * This is the allocate id function. It should be called with any 2981da177e4SLinus Torvalds * required locks. 2991da177e4SLinus Torvalds * 3001da177e4SLinus Torvalds * If memory is required, it will return -EAGAIN, you should unlock 3011da177e4SLinus Torvalds * and go back to the idr_pre_get() call. If the idr is full, it will 3021da177e4SLinus Torvalds * return -ENOSPC. 3031da177e4SLinus Torvalds * 3041da177e4SLinus Torvalds * @id returns a value in the range 0 ... 0x7fffffff 3051da177e4SLinus Torvalds */ 3061da177e4SLinus Torvalds int idr_get_new(struct idr *idp, void *ptr, int *id) 3071da177e4SLinus Torvalds { 3081da177e4SLinus Torvalds int rv; 309e15ae2ddSJesper Juhl 3101da177e4SLinus Torvalds rv = idr_get_new_above_int(idp, ptr, 0); 3111da177e4SLinus Torvalds /* 3121da177e4SLinus Torvalds * This is a cheap hack until the IDR code can be fixed to 3131da177e4SLinus Torvalds * return proper error values. 3141da177e4SLinus Torvalds */ 3151da177e4SLinus Torvalds if (rv < 0) { 3161da177e4SLinus Torvalds if (rv == -1) 3171da177e4SLinus Torvalds return -EAGAIN; 3181da177e4SLinus Torvalds else /* Will be -3 */ 3191da177e4SLinus Torvalds return -ENOSPC; 3201da177e4SLinus Torvalds } 3211da177e4SLinus Torvalds *id = rv; 3221da177e4SLinus Torvalds return 0; 3231da177e4SLinus Torvalds } 3241da177e4SLinus Torvalds EXPORT_SYMBOL(idr_get_new); 3251da177e4SLinus Torvalds 3261da177e4SLinus Torvalds static void idr_remove_warning(int id) 3271da177e4SLinus Torvalds { 3281da177e4SLinus Torvalds printk("idr_remove called for id=%d which is not allocated.\n", id); 3291da177e4SLinus Torvalds dump_stack(); 3301da177e4SLinus Torvalds } 3311da177e4SLinus Torvalds 3321da177e4SLinus Torvalds static void sub_remove(struct idr *idp, int shift, int id) 3331da177e4SLinus Torvalds { 3341da177e4SLinus Torvalds struct idr_layer *p = idp->top; 3351da177e4SLinus Torvalds struct idr_layer **pa[MAX_LEVEL]; 3361da177e4SLinus Torvalds struct idr_layer ***paa = &pa[0]; 3371da177e4SLinus Torvalds int n; 3381da177e4SLinus Torvalds 3391da177e4SLinus Torvalds *paa = NULL; 3401da177e4SLinus Torvalds *++paa = &idp->top; 3411da177e4SLinus Torvalds 3421da177e4SLinus Torvalds while ((shift > 0) && p) { 3431da177e4SLinus Torvalds n = (id >> shift) & IDR_MASK; 3441da177e4SLinus Torvalds __clear_bit(n, &p->bitmap); 3451da177e4SLinus Torvalds *++paa = &p->ary[n]; 3461da177e4SLinus Torvalds p = p->ary[n]; 3471da177e4SLinus Torvalds shift -= IDR_BITS; 3481da177e4SLinus Torvalds } 3491da177e4SLinus Torvalds n = id & IDR_MASK; 3501da177e4SLinus Torvalds if (likely(p != NULL && test_bit(n, &p->bitmap))){ 3511da177e4SLinus Torvalds __clear_bit(n, &p->bitmap); 3521da177e4SLinus Torvalds p->ary[n] = NULL; 3531da177e4SLinus Torvalds while(*paa && ! --((**paa)->count)){ 3541da177e4SLinus Torvalds free_layer(idp, **paa); 3551da177e4SLinus Torvalds **paa-- = NULL; 3561da177e4SLinus Torvalds } 3571da177e4SLinus Torvalds if (!*paa) 3581da177e4SLinus Torvalds idp->layers = 0; 359e15ae2ddSJesper Juhl } else 3601da177e4SLinus Torvalds idr_remove_warning(id); 3611da177e4SLinus Torvalds } 3621da177e4SLinus Torvalds 3631da177e4SLinus Torvalds /** 3641da177e4SLinus Torvalds * idr_remove - remove the given id and free it's slot 36572fd4a35SRobert P. J. Day * @idp: idr handle 36672fd4a35SRobert P. J. Day * @id: unique key 3671da177e4SLinus Torvalds */ 3681da177e4SLinus Torvalds void idr_remove(struct idr *idp, int id) 3691da177e4SLinus Torvalds { 3701da177e4SLinus Torvalds struct idr_layer *p; 3711da177e4SLinus Torvalds 3721da177e4SLinus Torvalds /* Mask off upper bits we don't use for the search. */ 3731da177e4SLinus Torvalds id &= MAX_ID_MASK; 3741da177e4SLinus Torvalds 3751da177e4SLinus Torvalds sub_remove(idp, (idp->layers - 1) * IDR_BITS, id); 376e15ae2ddSJesper Juhl if (idp->top && idp->top->count == 1 && (idp->layers > 1) && 3771da177e4SLinus Torvalds idp->top->ary[0]) { // We can drop a layer 3781da177e4SLinus Torvalds 3791da177e4SLinus Torvalds p = idp->top->ary[0]; 3801da177e4SLinus Torvalds idp->top->bitmap = idp->top->count = 0; 3811da177e4SLinus Torvalds free_layer(idp, idp->top); 3821da177e4SLinus Torvalds idp->top = p; 3831da177e4SLinus Torvalds --idp->layers; 3841da177e4SLinus Torvalds } 3851da177e4SLinus Torvalds while (idp->id_free_cnt >= IDR_FREE_MAX) { 3861da177e4SLinus Torvalds p = alloc_layer(idp); 3871da177e4SLinus Torvalds kmem_cache_free(idr_layer_cache, p); 3881da177e4SLinus Torvalds return; 3891da177e4SLinus Torvalds } 3901da177e4SLinus Torvalds } 3911da177e4SLinus Torvalds EXPORT_SYMBOL(idr_remove); 3921da177e4SLinus Torvalds 3931da177e4SLinus Torvalds /** 3948d3b3591SAndrew Morton * idr_destroy - release all cached layers within an idr tree 3958d3b3591SAndrew Morton * idp: idr handle 3968d3b3591SAndrew Morton */ 3978d3b3591SAndrew Morton void idr_destroy(struct idr *idp) 3988d3b3591SAndrew Morton { 3998d3b3591SAndrew Morton while (idp->id_free_cnt) { 4008d3b3591SAndrew Morton struct idr_layer *p = alloc_layer(idp); 4018d3b3591SAndrew Morton kmem_cache_free(idr_layer_cache, p); 4028d3b3591SAndrew Morton } 4038d3b3591SAndrew Morton } 4048d3b3591SAndrew Morton EXPORT_SYMBOL(idr_destroy); 4058d3b3591SAndrew Morton 4068d3b3591SAndrew Morton /** 4071da177e4SLinus Torvalds * idr_find - return pointer for given id 4081da177e4SLinus Torvalds * @idp: idr handle 4091da177e4SLinus Torvalds * @id: lookup key 4101da177e4SLinus Torvalds * 4111da177e4SLinus Torvalds * Return the pointer given the id it has been registered with. A %NULL 4121da177e4SLinus Torvalds * return indicates that @id is not valid or you passed %NULL in 4131da177e4SLinus Torvalds * idr_get_new(). 4141da177e4SLinus Torvalds * 4151da177e4SLinus Torvalds * The caller must serialize idr_find() vs idr_get_new() and idr_remove(). 4161da177e4SLinus Torvalds */ 4171da177e4SLinus Torvalds void *idr_find(struct idr *idp, int id) 4181da177e4SLinus Torvalds { 4191da177e4SLinus Torvalds int n; 4201da177e4SLinus Torvalds struct idr_layer *p; 4211da177e4SLinus Torvalds 4221da177e4SLinus Torvalds n = idp->layers * IDR_BITS; 4231da177e4SLinus Torvalds p = idp->top; 4241da177e4SLinus Torvalds 4251da177e4SLinus Torvalds /* Mask off upper bits we don't use for the search. */ 4261da177e4SLinus Torvalds id &= MAX_ID_MASK; 4271da177e4SLinus Torvalds 4281da177e4SLinus Torvalds if (id >= (1 << n)) 4291da177e4SLinus Torvalds return NULL; 4301da177e4SLinus Torvalds 4311da177e4SLinus Torvalds while (n > 0 && p) { 4321da177e4SLinus Torvalds n -= IDR_BITS; 4331da177e4SLinus Torvalds p = p->ary[(id >> n) & IDR_MASK]; 4341da177e4SLinus Torvalds } 4351da177e4SLinus Torvalds return((void *)p); 4361da177e4SLinus Torvalds } 4371da177e4SLinus Torvalds EXPORT_SYMBOL(idr_find); 4381da177e4SLinus Torvalds 4395806f07cSJeff Mahoney /** 4405806f07cSJeff Mahoney * idr_replace - replace pointer for given id 4415806f07cSJeff Mahoney * @idp: idr handle 4425806f07cSJeff Mahoney * @ptr: pointer you want associated with the id 4435806f07cSJeff Mahoney * @id: lookup key 4445806f07cSJeff Mahoney * 4455806f07cSJeff Mahoney * Replace the pointer registered with an id and return the old value. 4465806f07cSJeff Mahoney * A -ENOENT return indicates that @id was not found. 4475806f07cSJeff Mahoney * A -EINVAL return indicates that @id was not within valid constraints. 4485806f07cSJeff Mahoney * 4495806f07cSJeff Mahoney * The caller must serialize vs idr_find(), idr_get_new(), and idr_remove(). 4505806f07cSJeff Mahoney */ 4515806f07cSJeff Mahoney void *idr_replace(struct idr *idp, void *ptr, int id) 4525806f07cSJeff Mahoney { 4535806f07cSJeff Mahoney int n; 4545806f07cSJeff Mahoney struct idr_layer *p, *old_p; 4555806f07cSJeff Mahoney 4565806f07cSJeff Mahoney n = idp->layers * IDR_BITS; 4575806f07cSJeff Mahoney p = idp->top; 4585806f07cSJeff Mahoney 4595806f07cSJeff Mahoney id &= MAX_ID_MASK; 4605806f07cSJeff Mahoney 4615806f07cSJeff Mahoney if (id >= (1 << n)) 4625806f07cSJeff Mahoney return ERR_PTR(-EINVAL); 4635806f07cSJeff Mahoney 4645806f07cSJeff Mahoney n -= IDR_BITS; 4655806f07cSJeff Mahoney while ((n > 0) && p) { 4665806f07cSJeff Mahoney p = p->ary[(id >> n) & IDR_MASK]; 4675806f07cSJeff Mahoney n -= IDR_BITS; 4685806f07cSJeff Mahoney } 4695806f07cSJeff Mahoney 4705806f07cSJeff Mahoney n = id & IDR_MASK; 4715806f07cSJeff Mahoney if (unlikely(p == NULL || !test_bit(n, &p->bitmap))) 4725806f07cSJeff Mahoney return ERR_PTR(-ENOENT); 4735806f07cSJeff Mahoney 4745806f07cSJeff Mahoney old_p = p->ary[n]; 4755806f07cSJeff Mahoney p->ary[n] = ptr; 4765806f07cSJeff Mahoney 4775806f07cSJeff Mahoney return old_p; 4785806f07cSJeff Mahoney } 4795806f07cSJeff Mahoney EXPORT_SYMBOL(idr_replace); 4805806f07cSJeff Mahoney 481e18b890bSChristoph Lameter static void idr_cache_ctor(void * idr_layer, struct kmem_cache *idr_layer_cache, 482e15ae2ddSJesper Juhl unsigned long flags) 4831da177e4SLinus Torvalds { 4841da177e4SLinus Torvalds memset(idr_layer, 0, sizeof(struct idr_layer)); 4851da177e4SLinus Torvalds } 4861da177e4SLinus Torvalds 4871da177e4SLinus Torvalds static int init_id_cache(void) 4881da177e4SLinus Torvalds { 4891da177e4SLinus Torvalds if (!idr_layer_cache) 4901da177e4SLinus Torvalds idr_layer_cache = kmem_cache_create("idr_layer_cache", 4911da177e4SLinus Torvalds sizeof(struct idr_layer), 0, 0, idr_cache_ctor, NULL); 4921da177e4SLinus Torvalds return 0; 4931da177e4SLinus Torvalds } 4941da177e4SLinus Torvalds 4951da177e4SLinus Torvalds /** 4961da177e4SLinus Torvalds * idr_init - initialize idr handle 4971da177e4SLinus Torvalds * @idp: idr handle 4981da177e4SLinus Torvalds * 4991da177e4SLinus Torvalds * This function is use to set up the handle (@idp) that you will pass 5001da177e4SLinus Torvalds * to the rest of the functions. 5011da177e4SLinus Torvalds */ 5021da177e4SLinus Torvalds void idr_init(struct idr *idp) 5031da177e4SLinus Torvalds { 5041da177e4SLinus Torvalds init_id_cache(); 5051da177e4SLinus Torvalds memset(idp, 0, sizeof(struct idr)); 5061da177e4SLinus Torvalds spin_lock_init(&idp->lock); 5071da177e4SLinus Torvalds } 5081da177e4SLinus Torvalds EXPORT_SYMBOL(idr_init); 509