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 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]; 1037aae6dd8STejun Heo int l, id, oid; 1041da177e4SLinus Torvalds long bm; 1051da177e4SLinus Torvalds 1061da177e4SLinus Torvalds id = *starting_id; 1077aae6dd8STejun Heo restart: 1081da177e4SLinus Torvalds p = idp->top; 1091da177e4SLinus Torvalds l = idp->layers; 1101da177e4SLinus Torvalds pa[l--] = NULL; 1111da177e4SLinus Torvalds while (1) { 1121da177e4SLinus Torvalds /* 1131da177e4SLinus Torvalds * We run around this while until we reach the leaf node... 1141da177e4SLinus Torvalds */ 1151da177e4SLinus Torvalds n = (id >> (IDR_BITS*l)) & IDR_MASK; 1161da177e4SLinus Torvalds bm = ~p->bitmap; 1171da177e4SLinus Torvalds m = find_next_bit(&bm, IDR_SIZE, n); 1181da177e4SLinus Torvalds if (m == IDR_SIZE) { 1191da177e4SLinus Torvalds /* no space available go back to previous layer. */ 1201da177e4SLinus Torvalds l++; 1217aae6dd8STejun Heo oid = id; 1221da177e4SLinus Torvalds id = (id | ((1 << (IDR_BITS * l)) - 1)) + 1; 1237aae6dd8STejun Heo 1247aae6dd8STejun Heo /* if already at the top layer, we need to grow */ 1251da177e4SLinus Torvalds if (!(p = pa[l])) { 1261da177e4SLinus Torvalds *starting_id = id; 1271da177e4SLinus Torvalds return -2; 1281da177e4SLinus Torvalds } 1297aae6dd8STejun Heo 1307aae6dd8STejun Heo /* If we need to go up one layer, continue the 1317aae6dd8STejun Heo * loop; otherwise, restart from the top. 1327aae6dd8STejun Heo */ 1337aae6dd8STejun Heo sh = IDR_BITS * (l + 1); 1347aae6dd8STejun Heo if (oid >> sh == id >> sh) 1351da177e4SLinus Torvalds continue; 1367aae6dd8STejun Heo else 1377aae6dd8STejun Heo goto restart; 1381da177e4SLinus Torvalds } 1391da177e4SLinus Torvalds if (m != n) { 1401da177e4SLinus Torvalds sh = IDR_BITS*l; 1411da177e4SLinus Torvalds id = ((id >> sh) ^ n ^ m) << sh; 1421da177e4SLinus Torvalds } 1431da177e4SLinus Torvalds if ((id >= MAX_ID_BIT) || (id < 0)) 1441da177e4SLinus Torvalds return -3; 1451da177e4SLinus Torvalds if (l == 0) 1461da177e4SLinus Torvalds break; 1471da177e4SLinus Torvalds /* 1481da177e4SLinus Torvalds * Create the layer below if it is missing. 1491da177e4SLinus Torvalds */ 1501da177e4SLinus Torvalds if (!p->ary[m]) { 1511da177e4SLinus Torvalds if (!(new = alloc_layer(idp))) 1521da177e4SLinus Torvalds return -1; 1531da177e4SLinus Torvalds p->ary[m] = new; 1541da177e4SLinus Torvalds p->count++; 1551da177e4SLinus Torvalds } 1561da177e4SLinus Torvalds pa[l--] = p; 1571da177e4SLinus Torvalds p = p->ary[m]; 1581da177e4SLinus Torvalds } 1591da177e4SLinus Torvalds /* 1601da177e4SLinus Torvalds * We have reached the leaf node, plant the 1611da177e4SLinus Torvalds * users pointer and return the raw id. 1621da177e4SLinus Torvalds */ 1631da177e4SLinus Torvalds p->ary[m] = (struct idr_layer *)ptr; 1641da177e4SLinus Torvalds __set_bit(m, &p->bitmap); 1651da177e4SLinus Torvalds p->count++; 1661da177e4SLinus Torvalds /* 1671da177e4SLinus Torvalds * If this layer is full mark the bit in the layer above 1681da177e4SLinus Torvalds * to show that this part of the radix tree is full. 1691da177e4SLinus Torvalds * This may complete the layer above and require walking 1701da177e4SLinus Torvalds * up the radix tree. 1711da177e4SLinus Torvalds */ 1721da177e4SLinus Torvalds n = id; 1731da177e4SLinus Torvalds while (p->bitmap == IDR_FULL) { 1741da177e4SLinus Torvalds if (!(p = pa[++l])) 1751da177e4SLinus Torvalds break; 1761da177e4SLinus Torvalds n = n >> IDR_BITS; 1771da177e4SLinus Torvalds __set_bit((n & IDR_MASK), &p->bitmap); 1781da177e4SLinus Torvalds } 1791da177e4SLinus Torvalds return(id); 1801da177e4SLinus Torvalds } 1811da177e4SLinus Torvalds 1821da177e4SLinus Torvalds static int idr_get_new_above_int(struct idr *idp, void *ptr, int starting_id) 1831da177e4SLinus Torvalds { 1841da177e4SLinus Torvalds struct idr_layer *p, *new; 1851da177e4SLinus Torvalds int layers, v, id; 186c259cc28SRoland Dreier unsigned long flags; 1871da177e4SLinus Torvalds 1881da177e4SLinus Torvalds id = starting_id; 1891da177e4SLinus Torvalds build_up: 1901da177e4SLinus Torvalds p = idp->top; 1911da177e4SLinus Torvalds layers = idp->layers; 1921da177e4SLinus Torvalds if (unlikely(!p)) { 1931da177e4SLinus Torvalds if (!(p = alloc_layer(idp))) 1941da177e4SLinus Torvalds return -1; 1951da177e4SLinus Torvalds layers = 1; 1961da177e4SLinus Torvalds } 1971da177e4SLinus Torvalds /* 1981da177e4SLinus Torvalds * Add a new layer to the top of the tree if the requested 1991da177e4SLinus Torvalds * id is larger than the currently allocated space. 2001da177e4SLinus Torvalds */ 201589777eaSZaur Kambarov while ((layers < (MAX_LEVEL - 1)) && (id >= (1 << (layers*IDR_BITS)))) { 2021da177e4SLinus Torvalds layers++; 2031da177e4SLinus Torvalds if (!p->count) 2041da177e4SLinus Torvalds continue; 2051da177e4SLinus Torvalds if (!(new = alloc_layer(idp))) { 2061da177e4SLinus Torvalds /* 2071da177e4SLinus Torvalds * The allocation failed. If we built part of 2081da177e4SLinus Torvalds * the structure tear it down. 2091da177e4SLinus Torvalds */ 210c259cc28SRoland Dreier spin_lock_irqsave(&idp->lock, flags); 2111da177e4SLinus Torvalds for (new = p; p && p != idp->top; new = p) { 2121da177e4SLinus Torvalds p = p->ary[0]; 2131da177e4SLinus Torvalds new->ary[0] = NULL; 2141da177e4SLinus Torvalds new->bitmap = new->count = 0; 2151eec0056SSonny Rao __free_layer(idp, new); 2161da177e4SLinus Torvalds } 217c259cc28SRoland Dreier spin_unlock_irqrestore(&idp->lock, flags); 2181da177e4SLinus Torvalds return -1; 2191da177e4SLinus Torvalds } 2201da177e4SLinus Torvalds new->ary[0] = p; 2211da177e4SLinus Torvalds new->count = 1; 2221da177e4SLinus Torvalds if (p->bitmap == IDR_FULL) 2231da177e4SLinus Torvalds __set_bit(0, &new->bitmap); 2241da177e4SLinus Torvalds p = new; 2251da177e4SLinus Torvalds } 2261da177e4SLinus Torvalds idp->top = p; 2271da177e4SLinus Torvalds idp->layers = layers; 2281da177e4SLinus Torvalds v = sub_alloc(idp, ptr, &id); 2291da177e4SLinus Torvalds if (v == -2) 2301da177e4SLinus Torvalds goto build_up; 2311da177e4SLinus Torvalds return(v); 2321da177e4SLinus Torvalds } 2331da177e4SLinus Torvalds 2341da177e4SLinus Torvalds /** 2357c657f2fSJohn McCutchan * idr_get_new_above - allocate new idr entry above or equal to a start id 2361da177e4SLinus Torvalds * @idp: idr handle 2371da177e4SLinus Torvalds * @ptr: pointer you want associated with the ide 2381da177e4SLinus Torvalds * @start_id: id to start search at 2391da177e4SLinus Torvalds * @id: pointer to the allocated handle 2401da177e4SLinus Torvalds * 2411da177e4SLinus Torvalds * This is the allocate id function. It should be called with any 2421da177e4SLinus Torvalds * required locks. 2431da177e4SLinus Torvalds * 2441da177e4SLinus Torvalds * If memory is required, it will return -EAGAIN, you should unlock 2451da177e4SLinus Torvalds * and go back to the idr_pre_get() call. If the idr is full, it will 2461da177e4SLinus Torvalds * return -ENOSPC. 2471da177e4SLinus Torvalds * 2481da177e4SLinus Torvalds * @id returns a value in the range 0 ... 0x7fffffff 2491da177e4SLinus Torvalds */ 2501da177e4SLinus Torvalds int idr_get_new_above(struct idr *idp, void *ptr, int starting_id, int *id) 2511da177e4SLinus Torvalds { 2521da177e4SLinus Torvalds int rv; 253e15ae2ddSJesper Juhl 2541da177e4SLinus Torvalds rv = idr_get_new_above_int(idp, ptr, starting_id); 2551da177e4SLinus Torvalds /* 2561da177e4SLinus Torvalds * This is a cheap hack until the IDR code can be fixed to 2571da177e4SLinus Torvalds * return proper error values. 2581da177e4SLinus Torvalds */ 2591da177e4SLinus Torvalds if (rv < 0) { 2601da177e4SLinus Torvalds if (rv == -1) 2611da177e4SLinus Torvalds return -EAGAIN; 2621da177e4SLinus Torvalds else /* Will be -3 */ 2631da177e4SLinus Torvalds return -ENOSPC; 2641da177e4SLinus Torvalds } 2651da177e4SLinus Torvalds *id = rv; 2661da177e4SLinus Torvalds return 0; 2671da177e4SLinus Torvalds } 2681da177e4SLinus Torvalds EXPORT_SYMBOL(idr_get_new_above); 2691da177e4SLinus Torvalds 2701da177e4SLinus Torvalds /** 2711da177e4SLinus Torvalds * idr_get_new - allocate new idr entry 2721da177e4SLinus Torvalds * @idp: idr handle 2731da177e4SLinus Torvalds * @ptr: pointer you want associated with the ide 2741da177e4SLinus Torvalds * @id: pointer to the allocated handle 2751da177e4SLinus Torvalds * 2761da177e4SLinus Torvalds * This is the allocate id function. It should be called with any 2771da177e4SLinus Torvalds * required locks. 2781da177e4SLinus Torvalds * 2791da177e4SLinus Torvalds * If memory is required, it will return -EAGAIN, you should unlock 2801da177e4SLinus Torvalds * and go back to the idr_pre_get() call. If the idr is full, it will 2811da177e4SLinus Torvalds * return -ENOSPC. 2821da177e4SLinus Torvalds * 2831da177e4SLinus Torvalds * @id returns a value in the range 0 ... 0x7fffffff 2841da177e4SLinus Torvalds */ 2851da177e4SLinus Torvalds int idr_get_new(struct idr *idp, void *ptr, int *id) 2861da177e4SLinus Torvalds { 2871da177e4SLinus Torvalds int rv; 288e15ae2ddSJesper Juhl 2891da177e4SLinus Torvalds rv = idr_get_new_above_int(idp, ptr, 0); 2901da177e4SLinus Torvalds /* 2911da177e4SLinus Torvalds * This is a cheap hack until the IDR code can be fixed to 2921da177e4SLinus Torvalds * return proper error values. 2931da177e4SLinus Torvalds */ 2941da177e4SLinus Torvalds if (rv < 0) { 2951da177e4SLinus Torvalds if (rv == -1) 2961da177e4SLinus Torvalds return -EAGAIN; 2971da177e4SLinus Torvalds else /* Will be -3 */ 2981da177e4SLinus Torvalds return -ENOSPC; 2991da177e4SLinus Torvalds } 3001da177e4SLinus Torvalds *id = rv; 3011da177e4SLinus Torvalds return 0; 3021da177e4SLinus Torvalds } 3031da177e4SLinus Torvalds EXPORT_SYMBOL(idr_get_new); 3041da177e4SLinus Torvalds 3051da177e4SLinus Torvalds static void idr_remove_warning(int id) 3061da177e4SLinus Torvalds { 3071da177e4SLinus Torvalds printk("idr_remove called for id=%d which is not allocated.\n", id); 3081da177e4SLinus Torvalds dump_stack(); 3091da177e4SLinus Torvalds } 3101da177e4SLinus Torvalds 3111da177e4SLinus Torvalds static void sub_remove(struct idr *idp, int shift, int id) 3121da177e4SLinus Torvalds { 3131da177e4SLinus Torvalds struct idr_layer *p = idp->top; 3141da177e4SLinus Torvalds struct idr_layer **pa[MAX_LEVEL]; 3151da177e4SLinus Torvalds struct idr_layer ***paa = &pa[0]; 3161da177e4SLinus Torvalds int n; 3171da177e4SLinus Torvalds 3181da177e4SLinus Torvalds *paa = NULL; 3191da177e4SLinus Torvalds *++paa = &idp->top; 3201da177e4SLinus Torvalds 3211da177e4SLinus Torvalds while ((shift > 0) && p) { 3221da177e4SLinus Torvalds n = (id >> shift) & IDR_MASK; 3231da177e4SLinus Torvalds __clear_bit(n, &p->bitmap); 3241da177e4SLinus Torvalds *++paa = &p->ary[n]; 3251da177e4SLinus Torvalds p = p->ary[n]; 3261da177e4SLinus Torvalds shift -= IDR_BITS; 3271da177e4SLinus Torvalds } 3281da177e4SLinus Torvalds n = id & IDR_MASK; 3291da177e4SLinus Torvalds if (likely(p != NULL && test_bit(n, &p->bitmap))){ 3301da177e4SLinus Torvalds __clear_bit(n, &p->bitmap); 3311da177e4SLinus Torvalds p->ary[n] = NULL; 3321da177e4SLinus Torvalds while(*paa && ! --((**paa)->count)){ 3331da177e4SLinus Torvalds free_layer(idp, **paa); 3341da177e4SLinus Torvalds **paa-- = NULL; 3351da177e4SLinus Torvalds } 3361da177e4SLinus Torvalds if (!*paa) 3371da177e4SLinus Torvalds idp->layers = 0; 338e15ae2ddSJesper Juhl } else 3391da177e4SLinus Torvalds idr_remove_warning(id); 3401da177e4SLinus Torvalds } 3411da177e4SLinus Torvalds 3421da177e4SLinus Torvalds /** 3431da177e4SLinus Torvalds * idr_remove - remove the given id and free it's slot 34472fd4a35SRobert P. J. Day * @idp: idr handle 34572fd4a35SRobert P. J. Day * @id: unique key 3461da177e4SLinus Torvalds */ 3471da177e4SLinus Torvalds void idr_remove(struct idr *idp, int id) 3481da177e4SLinus Torvalds { 3491da177e4SLinus Torvalds struct idr_layer *p; 3501da177e4SLinus Torvalds 3511da177e4SLinus Torvalds /* Mask off upper bits we don't use for the search. */ 3521da177e4SLinus Torvalds id &= MAX_ID_MASK; 3531da177e4SLinus Torvalds 3541da177e4SLinus Torvalds sub_remove(idp, (idp->layers - 1) * IDR_BITS, id); 355e15ae2ddSJesper Juhl if (idp->top && idp->top->count == 1 && (idp->layers > 1) && 3561da177e4SLinus Torvalds idp->top->ary[0]) { // We can drop a layer 3571da177e4SLinus Torvalds 3581da177e4SLinus Torvalds p = idp->top->ary[0]; 3591da177e4SLinus Torvalds idp->top->bitmap = idp->top->count = 0; 3601da177e4SLinus Torvalds free_layer(idp, idp->top); 3611da177e4SLinus Torvalds idp->top = p; 3621da177e4SLinus Torvalds --idp->layers; 3631da177e4SLinus Torvalds } 3641da177e4SLinus Torvalds while (idp->id_free_cnt >= IDR_FREE_MAX) { 3651da177e4SLinus Torvalds p = alloc_layer(idp); 3661da177e4SLinus Torvalds kmem_cache_free(idr_layer_cache, p); 3671da177e4SLinus Torvalds return; 3681da177e4SLinus Torvalds } 3691da177e4SLinus Torvalds } 3701da177e4SLinus Torvalds EXPORT_SYMBOL(idr_remove); 3711da177e4SLinus Torvalds 3721da177e4SLinus Torvalds /** 3738d3b3591SAndrew Morton * idr_destroy - release all cached layers within an idr tree 3748d3b3591SAndrew Morton * idp: idr handle 3758d3b3591SAndrew Morton */ 3768d3b3591SAndrew Morton void idr_destroy(struct idr *idp) 3778d3b3591SAndrew Morton { 3788d3b3591SAndrew Morton while (idp->id_free_cnt) { 3798d3b3591SAndrew Morton struct idr_layer *p = alloc_layer(idp); 3808d3b3591SAndrew Morton kmem_cache_free(idr_layer_cache, p); 3818d3b3591SAndrew Morton } 3828d3b3591SAndrew Morton } 3838d3b3591SAndrew Morton EXPORT_SYMBOL(idr_destroy); 3848d3b3591SAndrew Morton 3858d3b3591SAndrew Morton /** 3861da177e4SLinus Torvalds * idr_find - return pointer for given id 3871da177e4SLinus Torvalds * @idp: idr handle 3881da177e4SLinus Torvalds * @id: lookup key 3891da177e4SLinus Torvalds * 3901da177e4SLinus Torvalds * Return the pointer given the id it has been registered with. A %NULL 3911da177e4SLinus Torvalds * return indicates that @id is not valid or you passed %NULL in 3921da177e4SLinus Torvalds * idr_get_new(). 3931da177e4SLinus Torvalds * 3941da177e4SLinus Torvalds * The caller must serialize idr_find() vs idr_get_new() and idr_remove(). 3951da177e4SLinus Torvalds */ 3961da177e4SLinus Torvalds void *idr_find(struct idr *idp, int id) 3971da177e4SLinus Torvalds { 3981da177e4SLinus Torvalds int n; 3991da177e4SLinus Torvalds struct idr_layer *p; 4001da177e4SLinus Torvalds 4011da177e4SLinus Torvalds n = idp->layers * IDR_BITS; 4021da177e4SLinus Torvalds p = idp->top; 4031da177e4SLinus Torvalds 4041da177e4SLinus Torvalds /* Mask off upper bits we don't use for the search. */ 4051da177e4SLinus Torvalds id &= MAX_ID_MASK; 4061da177e4SLinus Torvalds 4071da177e4SLinus Torvalds if (id >= (1 << n)) 4081da177e4SLinus Torvalds return NULL; 4091da177e4SLinus Torvalds 4101da177e4SLinus Torvalds while (n > 0 && p) { 4111da177e4SLinus Torvalds n -= IDR_BITS; 4121da177e4SLinus Torvalds p = p->ary[(id >> n) & IDR_MASK]; 4131da177e4SLinus Torvalds } 4141da177e4SLinus Torvalds return((void *)p); 4151da177e4SLinus Torvalds } 4161da177e4SLinus Torvalds EXPORT_SYMBOL(idr_find); 4171da177e4SLinus Torvalds 4185806f07cSJeff Mahoney /** 4195806f07cSJeff Mahoney * idr_replace - replace pointer for given id 4205806f07cSJeff Mahoney * @idp: idr handle 4215806f07cSJeff Mahoney * @ptr: pointer you want associated with the id 4225806f07cSJeff Mahoney * @id: lookup key 4235806f07cSJeff Mahoney * 4245806f07cSJeff Mahoney * Replace the pointer registered with an id and return the old value. 4255806f07cSJeff Mahoney * A -ENOENT return indicates that @id was not found. 4265806f07cSJeff Mahoney * A -EINVAL return indicates that @id was not within valid constraints. 4275806f07cSJeff Mahoney * 4285806f07cSJeff Mahoney * The caller must serialize vs idr_find(), idr_get_new(), and idr_remove(). 4295806f07cSJeff Mahoney */ 4305806f07cSJeff Mahoney void *idr_replace(struct idr *idp, void *ptr, int id) 4315806f07cSJeff Mahoney { 4325806f07cSJeff Mahoney int n; 4335806f07cSJeff Mahoney struct idr_layer *p, *old_p; 4345806f07cSJeff Mahoney 4355806f07cSJeff Mahoney n = idp->layers * IDR_BITS; 4365806f07cSJeff Mahoney p = idp->top; 4375806f07cSJeff Mahoney 4385806f07cSJeff Mahoney id &= MAX_ID_MASK; 4395806f07cSJeff Mahoney 4405806f07cSJeff Mahoney if (id >= (1 << n)) 4415806f07cSJeff Mahoney return ERR_PTR(-EINVAL); 4425806f07cSJeff Mahoney 4435806f07cSJeff Mahoney n -= IDR_BITS; 4445806f07cSJeff Mahoney while ((n > 0) && p) { 4455806f07cSJeff Mahoney p = p->ary[(id >> n) & IDR_MASK]; 4465806f07cSJeff Mahoney n -= IDR_BITS; 4475806f07cSJeff Mahoney } 4485806f07cSJeff Mahoney 4495806f07cSJeff Mahoney n = id & IDR_MASK; 4505806f07cSJeff Mahoney if (unlikely(p == NULL || !test_bit(n, &p->bitmap))) 4515806f07cSJeff Mahoney return ERR_PTR(-ENOENT); 4525806f07cSJeff Mahoney 4535806f07cSJeff Mahoney old_p = p->ary[n]; 4545806f07cSJeff Mahoney p->ary[n] = ptr; 4555806f07cSJeff Mahoney 4565806f07cSJeff Mahoney return old_p; 4575806f07cSJeff Mahoney } 4585806f07cSJeff Mahoney EXPORT_SYMBOL(idr_replace); 4595806f07cSJeff Mahoney 460e18b890bSChristoph Lameter static void idr_cache_ctor(void * idr_layer, struct kmem_cache *idr_layer_cache, 461e15ae2ddSJesper Juhl unsigned long flags) 4621da177e4SLinus Torvalds { 4631da177e4SLinus Torvalds memset(idr_layer, 0, sizeof(struct idr_layer)); 4641da177e4SLinus Torvalds } 4651da177e4SLinus Torvalds 4661da177e4SLinus Torvalds static int init_id_cache(void) 4671da177e4SLinus Torvalds { 4681da177e4SLinus Torvalds if (!idr_layer_cache) 4691da177e4SLinus Torvalds idr_layer_cache = kmem_cache_create("idr_layer_cache", 4701da177e4SLinus Torvalds sizeof(struct idr_layer), 0, 0, idr_cache_ctor, NULL); 4711da177e4SLinus Torvalds return 0; 4721da177e4SLinus Torvalds } 4731da177e4SLinus Torvalds 4741da177e4SLinus Torvalds /** 4751da177e4SLinus Torvalds * idr_init - initialize idr handle 4761da177e4SLinus Torvalds * @idp: idr handle 4771da177e4SLinus Torvalds * 4781da177e4SLinus Torvalds * This function is use to set up the handle (@idp) that you will pass 4791da177e4SLinus Torvalds * to the rest of the functions. 4801da177e4SLinus Torvalds */ 4811da177e4SLinus Torvalds void idr_init(struct idr *idp) 4821da177e4SLinus Torvalds { 4831da177e4SLinus Torvalds init_id_cache(); 4841da177e4SLinus Torvalds memset(idp, 0, sizeof(struct idr)); 4851da177e4SLinus Torvalds spin_lock_init(&idp->lock); 4861da177e4SLinus Torvalds } 4871da177e4SLinus Torvalds EXPORT_SYMBOL(idr_init); 488