10a835c4fSMatthew Wilcox #include <linux/bitmap.h> 2460488c5SMatthew Wilcox #include <linux/bug.h> 38bc3bcc9SPaul Gortmaker #include <linux/export.h> 41da177e4SLinus Torvalds #include <linux/idr.h> 50a835c4fSMatthew Wilcox #include <linux/slab.h> 688eca020SRusty Russell #include <linux/spinlock.h> 7b94078e6SMatthew Wilcox #include <linux/xarray.h> 81da177e4SLinus Torvalds 97ad3d4d8SMatthew Wilcox DEFINE_PER_CPU(struct ida_bitmap *, ida_bitmap); 101da177e4SLinus Torvalds 11e096f6a7SMatthew Wilcox /** 12e096f6a7SMatthew Wilcox * idr_alloc_u32() - Allocate an ID. 13e096f6a7SMatthew Wilcox * @idr: IDR handle. 14e096f6a7SMatthew Wilcox * @ptr: Pointer to be associated with the new ID. 15e096f6a7SMatthew Wilcox * @nextid: Pointer to an ID. 16e096f6a7SMatthew Wilcox * @max: The maximum ID to allocate (inclusive). 17e096f6a7SMatthew Wilcox * @gfp: Memory allocation flags. 18e096f6a7SMatthew Wilcox * 19e096f6a7SMatthew Wilcox * Allocates an unused ID in the range specified by @nextid and @max. 20e096f6a7SMatthew Wilcox * Note that @max is inclusive whereas the @end parameter to idr_alloc() 21460488c5SMatthew Wilcox * is exclusive. The new ID is assigned to @nextid before the pointer 22460488c5SMatthew Wilcox * is inserted into the IDR, so if @nextid points into the object pointed 23460488c5SMatthew Wilcox * to by @ptr, a concurrent lookup will not find an uninitialised ID. 24e096f6a7SMatthew Wilcox * 25e096f6a7SMatthew Wilcox * The caller should provide their own locking to ensure that two 26e096f6a7SMatthew Wilcox * concurrent modifications to the IDR are not possible. Read-only 27e096f6a7SMatthew Wilcox * accesses to the IDR may be done under the RCU read lock or may 28e096f6a7SMatthew Wilcox * exclude simultaneous writers. 29e096f6a7SMatthew Wilcox * 30e096f6a7SMatthew Wilcox * Return: 0 if an ID was allocated, -ENOMEM if memory allocation failed, 31e096f6a7SMatthew Wilcox * or -ENOSPC if no free IDs could be found. If an error occurred, 32e096f6a7SMatthew Wilcox * @nextid is unchanged. 33e096f6a7SMatthew Wilcox */ 34e096f6a7SMatthew Wilcox int idr_alloc_u32(struct idr *idr, void *ptr, u32 *nextid, 35e096f6a7SMatthew Wilcox unsigned long max, gfp_t gfp) 36e096f6a7SMatthew Wilcox { 370a835c4fSMatthew Wilcox struct radix_tree_iter iter; 38388f79fdSChris Mi void __rcu **slot; 394b0ad076SMatthew Wilcox unsigned int base = idr->idr_base; 404b0ad076SMatthew Wilcox unsigned int id = *nextid; 41d5c7409fSTejun Heo 42460488c5SMatthew Wilcox if (WARN_ON_ONCE(!(idr->idr_rt.gfp_mask & ROOT_IS_IDR))) 43460488c5SMatthew Wilcox idr->idr_rt.gfp_mask |= IDR_RT_MARKER; 44d5c7409fSTejun Heo 456ce711f2SMatthew Wilcox id = (id < base) ? 0 : id - base; 466ce711f2SMatthew Wilcox radix_tree_iter_init(&iter, id); 476ce711f2SMatthew Wilcox slot = idr_get_free(&idr->idr_rt, &iter, gfp, max - base); 480a835c4fSMatthew Wilcox if (IS_ERR(slot)) 490a835c4fSMatthew Wilcox return PTR_ERR(slot); 50d5c7409fSTejun Heo 516ce711f2SMatthew Wilcox *nextid = iter.index + base; 52460488c5SMatthew Wilcox /* there is a memory barrier inside radix_tree_iter_replace() */ 530a835c4fSMatthew Wilcox radix_tree_iter_replace(&idr->idr_rt, &iter, slot, ptr); 540a835c4fSMatthew Wilcox radix_tree_iter_tag_clear(&idr->idr_rt, &iter, IDR_FREE); 55388f79fdSChris Mi 56388f79fdSChris Mi return 0; 57d5c7409fSTejun Heo } 58460488c5SMatthew Wilcox EXPORT_SYMBOL_GPL(idr_alloc_u32); 59d5c7409fSTejun Heo 603e6628c4SJeff Layton /** 61460488c5SMatthew Wilcox * idr_alloc() - Allocate an ID. 62460488c5SMatthew Wilcox * @idr: IDR handle. 63460488c5SMatthew Wilcox * @ptr: Pointer to be associated with the new ID. 64460488c5SMatthew Wilcox * @start: The minimum ID (inclusive). 65460488c5SMatthew Wilcox * @end: The maximum ID (exclusive). 66460488c5SMatthew Wilcox * @gfp: Memory allocation flags. 673e6628c4SJeff Layton * 68460488c5SMatthew Wilcox * Allocates an unused ID in the range specified by @start and @end. If 69460488c5SMatthew Wilcox * @end is <= 0, it is treated as one larger than %INT_MAX. This allows 70460488c5SMatthew Wilcox * callers to use @start + N as @end as long as N is within integer range. 71460488c5SMatthew Wilcox * 72460488c5SMatthew Wilcox * The caller should provide their own locking to ensure that two 73460488c5SMatthew Wilcox * concurrent modifications to the IDR are not possible. Read-only 74460488c5SMatthew Wilcox * accesses to the IDR may be done under the RCU read lock or may 75460488c5SMatthew Wilcox * exclude simultaneous writers. 76460488c5SMatthew Wilcox * 77460488c5SMatthew Wilcox * Return: The newly allocated ID, -ENOMEM if memory allocation failed, 78460488c5SMatthew Wilcox * or -ENOSPC if no free IDs could be found. 79460488c5SMatthew Wilcox */ 80460488c5SMatthew Wilcox int idr_alloc(struct idr *idr, void *ptr, int start, int end, gfp_t gfp) 81460488c5SMatthew Wilcox { 82460488c5SMatthew Wilcox u32 id = start; 83460488c5SMatthew Wilcox int ret; 84460488c5SMatthew Wilcox 85460488c5SMatthew Wilcox if (WARN_ON_ONCE(start < 0)) 86460488c5SMatthew Wilcox return -EINVAL; 87460488c5SMatthew Wilcox 88460488c5SMatthew Wilcox ret = idr_alloc_u32(idr, ptr, &id, end > 0 ? end - 1 : INT_MAX, gfp); 89460488c5SMatthew Wilcox if (ret) 90460488c5SMatthew Wilcox return ret; 91460488c5SMatthew Wilcox 92460488c5SMatthew Wilcox return id; 93460488c5SMatthew Wilcox } 94460488c5SMatthew Wilcox EXPORT_SYMBOL_GPL(idr_alloc); 95460488c5SMatthew Wilcox 96460488c5SMatthew Wilcox /** 97460488c5SMatthew Wilcox * idr_alloc_cyclic() - Allocate an ID cyclically. 98460488c5SMatthew Wilcox * @idr: IDR handle. 99460488c5SMatthew Wilcox * @ptr: Pointer to be associated with the new ID. 100460488c5SMatthew Wilcox * @start: The minimum ID (inclusive). 101460488c5SMatthew Wilcox * @end: The maximum ID (exclusive). 102460488c5SMatthew Wilcox * @gfp: Memory allocation flags. 103460488c5SMatthew Wilcox * 104460488c5SMatthew Wilcox * Allocates an unused ID in the range specified by @nextid and @end. If 105460488c5SMatthew Wilcox * @end is <= 0, it is treated as one larger than %INT_MAX. This allows 106460488c5SMatthew Wilcox * callers to use @start + N as @end as long as N is within integer range. 107460488c5SMatthew Wilcox * The search for an unused ID will start at the last ID allocated and will 108460488c5SMatthew Wilcox * wrap around to @start if no free IDs are found before reaching @end. 109460488c5SMatthew Wilcox * 110460488c5SMatthew Wilcox * The caller should provide their own locking to ensure that two 111460488c5SMatthew Wilcox * concurrent modifications to the IDR are not possible. Read-only 112460488c5SMatthew Wilcox * accesses to the IDR may be done under the RCU read lock or may 113460488c5SMatthew Wilcox * exclude simultaneous writers. 114460488c5SMatthew Wilcox * 115460488c5SMatthew Wilcox * Return: The newly allocated ID, -ENOMEM if memory allocation failed, 116460488c5SMatthew Wilcox * or -ENOSPC if no free IDs could be found. 1173e6628c4SJeff Layton */ 1180a835c4fSMatthew Wilcox int idr_alloc_cyclic(struct idr *idr, void *ptr, int start, int end, gfp_t gfp) 1193e6628c4SJeff Layton { 120460488c5SMatthew Wilcox u32 id = idr->idr_next; 121460488c5SMatthew Wilcox int err, max = end > 0 ? end - 1 : INT_MAX; 1223e6628c4SJeff Layton 123460488c5SMatthew Wilcox if ((int)id < start) 124460488c5SMatthew Wilcox id = start; 1253e6628c4SJeff Layton 126460488c5SMatthew Wilcox err = idr_alloc_u32(idr, ptr, &id, max, gfp); 127460488c5SMatthew Wilcox if ((err == -ENOSPC) && (id > start)) { 128460488c5SMatthew Wilcox id = start; 129460488c5SMatthew Wilcox err = idr_alloc_u32(idr, ptr, &id, max, gfp); 130460488c5SMatthew Wilcox } 131460488c5SMatthew Wilcox if (err) 132460488c5SMatthew Wilcox return err; 1330a835c4fSMatthew Wilcox 134460488c5SMatthew Wilcox idr->idr_next = id + 1; 1353e6628c4SJeff Layton return id; 1363e6628c4SJeff Layton } 1373e6628c4SJeff Layton EXPORT_SYMBOL(idr_alloc_cyclic); 1383e6628c4SJeff Layton 1395806f07cSJeff Mahoney /** 1406ce711f2SMatthew Wilcox * idr_remove() - Remove an ID from the IDR. 1416ce711f2SMatthew Wilcox * @idr: IDR handle. 1426ce711f2SMatthew Wilcox * @id: Pointer ID. 1436ce711f2SMatthew Wilcox * 1446ce711f2SMatthew Wilcox * Removes this ID from the IDR. If the ID was not previously in the IDR, 1456ce711f2SMatthew Wilcox * this function returns %NULL. 1466ce711f2SMatthew Wilcox * 1476ce711f2SMatthew Wilcox * Since this function modifies the IDR, the caller should provide their 1486ce711f2SMatthew Wilcox * own locking to ensure that concurrent modification of the same IDR is 1496ce711f2SMatthew Wilcox * not possible. 1506ce711f2SMatthew Wilcox * 1516ce711f2SMatthew Wilcox * Return: The pointer formerly associated with this ID. 1526ce711f2SMatthew Wilcox */ 1536ce711f2SMatthew Wilcox void *idr_remove(struct idr *idr, unsigned long id) 1546ce711f2SMatthew Wilcox { 1556ce711f2SMatthew Wilcox return radix_tree_delete_item(&idr->idr_rt, id - idr->idr_base, NULL); 1566ce711f2SMatthew Wilcox } 1576ce711f2SMatthew Wilcox EXPORT_SYMBOL_GPL(idr_remove); 1586ce711f2SMatthew Wilcox 1596ce711f2SMatthew Wilcox /** 1606ce711f2SMatthew Wilcox * idr_find() - Return pointer for given ID. 1616ce711f2SMatthew Wilcox * @idr: IDR handle. 1626ce711f2SMatthew Wilcox * @id: Pointer ID. 1636ce711f2SMatthew Wilcox * 1646ce711f2SMatthew Wilcox * Looks up the pointer associated with this ID. A %NULL pointer may 1656ce711f2SMatthew Wilcox * indicate that @id is not allocated or that the %NULL pointer was 1666ce711f2SMatthew Wilcox * associated with this ID. 1676ce711f2SMatthew Wilcox * 1686ce711f2SMatthew Wilcox * This function can be called under rcu_read_lock(), given that the leaf 1696ce711f2SMatthew Wilcox * pointers lifetimes are correctly managed. 1706ce711f2SMatthew Wilcox * 1716ce711f2SMatthew Wilcox * Return: The pointer associated with this ID. 1726ce711f2SMatthew Wilcox */ 1736ce711f2SMatthew Wilcox void *idr_find(const struct idr *idr, unsigned long id) 1746ce711f2SMatthew Wilcox { 1756ce711f2SMatthew Wilcox return radix_tree_lookup(&idr->idr_rt, id - idr->idr_base); 1766ce711f2SMatthew Wilcox } 1776ce711f2SMatthew Wilcox EXPORT_SYMBOL_GPL(idr_find); 1786ce711f2SMatthew Wilcox 1796ce711f2SMatthew Wilcox /** 1807a457577SMatthew Wilcox * idr_for_each() - Iterate through all stored pointers. 1817a457577SMatthew Wilcox * @idr: IDR handle. 1827a457577SMatthew Wilcox * @fn: Function to be called for each pointer. 1837a457577SMatthew Wilcox * @data: Data passed to callback function. 18496d7fa42SKristian Hoegsberg * 1850a835c4fSMatthew Wilcox * The callback function will be called for each entry in @idr, passing 1867a457577SMatthew Wilcox * the ID, the entry and @data. 18796d7fa42SKristian Hoegsberg * 1880a835c4fSMatthew Wilcox * If @fn returns anything other than %0, the iteration stops and that 1890a835c4fSMatthew Wilcox * value is returned from this function. 19096d7fa42SKristian Hoegsberg * 1910a835c4fSMatthew Wilcox * idr_for_each() can be called concurrently with idr_alloc() and 1920a835c4fSMatthew Wilcox * idr_remove() if protected by RCU. Newly added entries may not be 1930a835c4fSMatthew Wilcox * seen and deleted entries may be seen, but adding and removing entries 1940a835c4fSMatthew Wilcox * will not cause other entries to be skipped, nor spurious ones to be seen. 19596d7fa42SKristian Hoegsberg */ 1960a835c4fSMatthew Wilcox int idr_for_each(const struct idr *idr, 19796d7fa42SKristian Hoegsberg int (*fn)(int id, void *p, void *data), void *data) 19896d7fa42SKristian Hoegsberg { 1990a835c4fSMatthew Wilcox struct radix_tree_iter iter; 2007e73eb0bSMatthew Wilcox void __rcu **slot; 2016ce711f2SMatthew Wilcox int base = idr->idr_base; 20296d7fa42SKristian Hoegsberg 2030a835c4fSMatthew Wilcox radix_tree_for_each_slot(slot, &idr->idr_rt, &iter, 0) { 20472fd6c7bSMatthew Wilcox int ret; 2054b0ad076SMatthew Wilcox unsigned long id = iter.index + base; 20672fd6c7bSMatthew Wilcox 2074b0ad076SMatthew Wilcox if (WARN_ON_ONCE(id > INT_MAX)) 20872fd6c7bSMatthew Wilcox break; 2094b0ad076SMatthew Wilcox ret = fn(id, rcu_dereference_raw(*slot), data); 2100a835c4fSMatthew Wilcox if (ret) 2110a835c4fSMatthew Wilcox return ret; 21296d7fa42SKristian Hoegsberg } 21396d7fa42SKristian Hoegsberg 2140a835c4fSMatthew Wilcox return 0; 21596d7fa42SKristian Hoegsberg } 21696d7fa42SKristian Hoegsberg EXPORT_SYMBOL(idr_for_each); 21796d7fa42SKristian Hoegsberg 21896d7fa42SKristian Hoegsberg /** 2197a457577SMatthew Wilcox * idr_get_next() - Find next populated entry. 2207a457577SMatthew Wilcox * @idr: IDR handle. 2217a457577SMatthew Wilcox * @nextid: Pointer to an ID. 22238460b48SKAMEZAWA Hiroyuki * 2230a835c4fSMatthew Wilcox * Returns the next populated entry in the tree with an ID greater than 2240a835c4fSMatthew Wilcox * or equal to the value pointed to by @nextid. On exit, @nextid is updated 2250a835c4fSMatthew Wilcox * to the ID of the found value. To use in a loop, the value pointed to by 2260a835c4fSMatthew Wilcox * nextid must be incremented by the user. 22738460b48SKAMEZAWA Hiroyuki */ 2280a835c4fSMatthew Wilcox void *idr_get_next(struct idr *idr, int *nextid) 22938460b48SKAMEZAWA Hiroyuki { 2300a835c4fSMatthew Wilcox struct radix_tree_iter iter; 2317e73eb0bSMatthew Wilcox void __rcu **slot; 2324b0ad076SMatthew Wilcox unsigned long base = idr->idr_base; 2334b0ad076SMatthew Wilcox unsigned long id = *nextid; 23438460b48SKAMEZAWA Hiroyuki 2356ce711f2SMatthew Wilcox id = (id < base) ? 0 : id - base; 2366ce711f2SMatthew Wilcox slot = radix_tree_iter_find(&idr->idr_rt, &iter, id); 2370a835c4fSMatthew Wilcox if (!slot) 23838460b48SKAMEZAWA Hiroyuki return NULL; 2396ce711f2SMatthew Wilcox id = iter.index + base; 24038460b48SKAMEZAWA Hiroyuki 2416ce711f2SMatthew Wilcox if (WARN_ON_ONCE(id > INT_MAX)) 24272fd6c7bSMatthew Wilcox return NULL; 24372fd6c7bSMatthew Wilcox 2446ce711f2SMatthew Wilcox *nextid = id; 2450a835c4fSMatthew Wilcox return rcu_dereference_raw(*slot); 24638460b48SKAMEZAWA Hiroyuki } 2474d1ee80fSBen Hutchings EXPORT_SYMBOL(idr_get_next); 24838460b48SKAMEZAWA Hiroyuki 2497a457577SMatthew Wilcox /** 2507a457577SMatthew Wilcox * idr_get_next_ul() - Find next populated entry. 2517a457577SMatthew Wilcox * @idr: IDR handle. 2527a457577SMatthew Wilcox * @nextid: Pointer to an ID. 2537a457577SMatthew Wilcox * 2547a457577SMatthew Wilcox * Returns the next populated entry in the tree with an ID greater than 2557a457577SMatthew Wilcox * or equal to the value pointed to by @nextid. On exit, @nextid is updated 2567a457577SMatthew Wilcox * to the ID of the found value. To use in a loop, the value pointed to by 2577a457577SMatthew Wilcox * nextid must be incremented by the user. 2587a457577SMatthew Wilcox */ 2597a457577SMatthew Wilcox void *idr_get_next_ul(struct idr *idr, unsigned long *nextid) 260388f79fdSChris Mi { 261388f79fdSChris Mi struct radix_tree_iter iter; 262388f79fdSChris Mi void __rcu **slot; 2636ce711f2SMatthew Wilcox unsigned long base = idr->idr_base; 2646ce711f2SMatthew Wilcox unsigned long id = *nextid; 265388f79fdSChris Mi 2666ce711f2SMatthew Wilcox id = (id < base) ? 0 : id - base; 2676ce711f2SMatthew Wilcox slot = radix_tree_iter_find(&idr->idr_rt, &iter, id); 268388f79fdSChris Mi if (!slot) 269388f79fdSChris Mi return NULL; 270388f79fdSChris Mi 2716ce711f2SMatthew Wilcox *nextid = iter.index + base; 272388f79fdSChris Mi return rcu_dereference_raw(*slot); 273388f79fdSChris Mi } 2747a457577SMatthew Wilcox EXPORT_SYMBOL(idr_get_next_ul); 275388f79fdSChris Mi 27638460b48SKAMEZAWA Hiroyuki /** 277460488c5SMatthew Wilcox * idr_replace() - replace pointer for given ID. 278460488c5SMatthew Wilcox * @idr: IDR handle. 279460488c5SMatthew Wilcox * @ptr: New pointer to associate with the ID. 280460488c5SMatthew Wilcox * @id: ID to change. 2815806f07cSJeff Mahoney * 2820a835c4fSMatthew Wilcox * Replace the pointer registered with an ID and return the old value. 2830a835c4fSMatthew Wilcox * This function can be called under the RCU read lock concurrently with 2840a835c4fSMatthew Wilcox * idr_alloc() and idr_remove() (as long as the ID being removed is not 2850a835c4fSMatthew Wilcox * the one being replaced!). 2865806f07cSJeff Mahoney * 287a70e43a5SEric Biggers * Returns: the old value on success. %-ENOENT indicates that @id was not 288234a4624SMatthew Wilcox * found. %-EINVAL indicates that @ptr was not valid. 2895806f07cSJeff Mahoney */ 290234a4624SMatthew Wilcox void *idr_replace(struct idr *idr, void *ptr, unsigned long id) 291388f79fdSChris Mi { 2920a835c4fSMatthew Wilcox struct radix_tree_node *node; 2937e73eb0bSMatthew Wilcox void __rcu **slot = NULL; 2940a835c4fSMatthew Wilcox void *entry; 2955806f07cSJeff Mahoney 2966ce711f2SMatthew Wilcox id -= idr->idr_base; 297e8c8d1bcSTejun Heo 2980a835c4fSMatthew Wilcox entry = __radix_tree_lookup(&idr->idr_rt, id, &node, &slot); 2990a835c4fSMatthew Wilcox if (!slot || radix_tree_tag_get(&idr->idr_rt, id, IDR_FREE)) 300b93804b2SLai Jiangshan return ERR_PTR(-ENOENT); 3016ff2d39bSManfred Spraul 302c7df8ad2SMel Gorman __radix_tree_replace(&idr->idr_rt, node, slot, ptr, NULL); 3035806f07cSJeff Mahoney 3040a835c4fSMatthew Wilcox return entry; 3055806f07cSJeff Mahoney } 306234a4624SMatthew Wilcox EXPORT_SYMBOL(idr_replace); 3075806f07cSJeff Mahoney 30856083ab1SRandy Dunlap /** 30956083ab1SRandy Dunlap * DOC: IDA description 31072dba584STejun Heo * 3110a835c4fSMatthew Wilcox * The IDA is an ID allocator which does not provide the ability to 3120a835c4fSMatthew Wilcox * associate an ID with a pointer. As such, it only needs to store one 3130a835c4fSMatthew Wilcox * bit per ID, and so is more space efficient than an IDR. To use an IDA, 3140a835c4fSMatthew Wilcox * define it using DEFINE_IDA() (or embed a &struct ida in a data structure, 3150a835c4fSMatthew Wilcox * then initialise it using ida_init()). To allocate a new ID, call 3165ade60ddSMatthew Wilcox * ida_alloc(), ida_alloc_min(), ida_alloc_max() or ida_alloc_range(). 3175ade60ddSMatthew Wilcox * To free an ID, call ida_free(). 31872dba584STejun Heo * 319b03f8e43SMatthew Wilcox * ida_destroy() can be used to dispose of an IDA without needing to 320b03f8e43SMatthew Wilcox * free the individual IDs in it. You can use ida_is_empty() to find 321b03f8e43SMatthew Wilcox * out whether the IDA has any IDs currently allocated. 3220a835c4fSMatthew Wilcox * 3230a835c4fSMatthew Wilcox * IDs are currently limited to the range [0-INT_MAX]. If this is an awkward 3240a835c4fSMatthew Wilcox * limitation, it should be quite straightforward to raise the maximum. 32572dba584STejun Heo */ 32672dba584STejun Heo 327d37cacc5SMatthew Wilcox /* 328d37cacc5SMatthew Wilcox * Developer's notes: 329d37cacc5SMatthew Wilcox * 330d37cacc5SMatthew Wilcox * The IDA uses the functionality provided by the IDR & radix tree to store 331d37cacc5SMatthew Wilcox * bitmaps in each entry. The IDR_FREE tag means there is at least one bit 332d37cacc5SMatthew Wilcox * free, unlike the IDR where it means at least one entry is free. 333d37cacc5SMatthew Wilcox * 334d37cacc5SMatthew Wilcox * I considered telling the radix tree that each slot is an order-10 node 335d37cacc5SMatthew Wilcox * and storing the bit numbers in the radix tree, but the radix tree can't 336d37cacc5SMatthew Wilcox * allow a single multiorder entry at index 0, which would significantly 337d37cacc5SMatthew Wilcox * increase memory consumption for the IDA. So instead we divide the index 338d37cacc5SMatthew Wilcox * by the number of bits in the leaf bitmap before doing a radix tree lookup. 339d37cacc5SMatthew Wilcox * 340d37cacc5SMatthew Wilcox * As an optimisation, if there are only a few low bits set in any given 3413159f943SMatthew Wilcox * leaf, instead of allocating a 128-byte bitmap, we store the bits 3423159f943SMatthew Wilcox * directly in the entry. 343d37cacc5SMatthew Wilcox * 344d37cacc5SMatthew Wilcox * We allow the radix tree 'exceptional' count to get out of date. Nothing 345d37cacc5SMatthew Wilcox * in the IDA nor the radix tree code checks it. If it becomes important 346d37cacc5SMatthew Wilcox * to maintain an accurate exceptional count, switch the rcu_assign_pointer() 347d37cacc5SMatthew Wilcox * calls to radix_tree_iter_replace() which will correct the exceptional 348d37cacc5SMatthew Wilcox * count. 349d37cacc5SMatthew Wilcox * 350d37cacc5SMatthew Wilcox * The IDA always requires a lock to alloc/free. If we add a 'test_bit' 351d37cacc5SMatthew Wilcox * equivalent, it will still need locking. Going to RCU lookup would require 352d37cacc5SMatthew Wilcox * using RCU to free bitmaps, and that's not trivial without embedding an 353d37cacc5SMatthew Wilcox * RCU head in the bitmap, which adds a 2-pointer overhead to each 128-byte 354d37cacc5SMatthew Wilcox * bitmap, which is excessive. 355d37cacc5SMatthew Wilcox */ 356d37cacc5SMatthew Wilcox 357460488c5SMatthew Wilcox #define IDA_MAX (0x80000000U / IDA_BITMAP_BITS - 1) 3580a835c4fSMatthew Wilcox 3591df89519SMatthew Wilcox static int ida_get_new_above(struct ida *ida, int start) 36072dba584STejun Heo { 3610a835c4fSMatthew Wilcox struct radix_tree_root *root = &ida->ida_rt; 3627e73eb0bSMatthew Wilcox void __rcu **slot; 3630a835c4fSMatthew Wilcox struct radix_tree_iter iter; 36472dba584STejun Heo struct ida_bitmap *bitmap; 3650a835c4fSMatthew Wilcox unsigned long index; 3663159f943SMatthew Wilcox unsigned bit; 3670a835c4fSMatthew Wilcox int new; 36872dba584STejun Heo 3690a835c4fSMatthew Wilcox index = start / IDA_BITMAP_BITS; 3700a835c4fSMatthew Wilcox bit = start % IDA_BITMAP_BITS; 37172dba584STejun Heo 3720a835c4fSMatthew Wilcox slot = radix_tree_iter_init(&iter, index); 3730a835c4fSMatthew Wilcox for (;;) { 3740a835c4fSMatthew Wilcox if (slot) 3750a835c4fSMatthew Wilcox slot = radix_tree_next_slot(slot, &iter, 3760a835c4fSMatthew Wilcox RADIX_TREE_ITER_TAGGED); 3770a835c4fSMatthew Wilcox if (!slot) { 3780a835c4fSMatthew Wilcox slot = idr_get_free(root, &iter, GFP_NOWAIT, IDA_MAX); 3790a835c4fSMatthew Wilcox if (IS_ERR(slot)) { 3800a835c4fSMatthew Wilcox if (slot == ERR_PTR(-ENOMEM)) 3810a835c4fSMatthew Wilcox return -EAGAIN; 3820a835c4fSMatthew Wilcox return PTR_ERR(slot); 3830a835c4fSMatthew Wilcox } 3840a835c4fSMatthew Wilcox } 3853159f943SMatthew Wilcox if (iter.index > index) 3860a835c4fSMatthew Wilcox bit = 0; 3870a835c4fSMatthew Wilcox new = iter.index * IDA_BITMAP_BITS; 3880a835c4fSMatthew Wilcox bitmap = rcu_dereference_raw(*slot); 3893159f943SMatthew Wilcox if (xa_is_value(bitmap)) { 3903159f943SMatthew Wilcox unsigned long tmp = xa_to_value(bitmap); 3913159f943SMatthew Wilcox int vbit = find_next_zero_bit(&tmp, BITS_PER_XA_VALUE, 3923159f943SMatthew Wilcox bit); 3933159f943SMatthew Wilcox if (vbit < BITS_PER_XA_VALUE) { 3943159f943SMatthew Wilcox tmp |= 1UL << vbit; 3953159f943SMatthew Wilcox rcu_assign_pointer(*slot, xa_mk_value(tmp)); 3963159f943SMatthew Wilcox return new + vbit; 397d37cacc5SMatthew Wilcox } 398d37cacc5SMatthew Wilcox bitmap = this_cpu_xchg(ida_bitmap, NULL); 399d37cacc5SMatthew Wilcox if (!bitmap) 400d37cacc5SMatthew Wilcox return -EAGAIN; 4013159f943SMatthew Wilcox bitmap->bitmap[0] = tmp; 402d37cacc5SMatthew Wilcox rcu_assign_pointer(*slot, bitmap); 403d37cacc5SMatthew Wilcox } 404d37cacc5SMatthew Wilcox 4050a835c4fSMatthew Wilcox if (bitmap) { 4060a835c4fSMatthew Wilcox bit = find_next_zero_bit(bitmap->bitmap, 4070a835c4fSMatthew Wilcox IDA_BITMAP_BITS, bit); 4080a835c4fSMatthew Wilcox new += bit; 4090a835c4fSMatthew Wilcox if (new < 0) 41072dba584STejun Heo return -ENOSPC; 4110a835c4fSMatthew Wilcox if (bit == IDA_BITMAP_BITS) 4120a835c4fSMatthew Wilcox continue; 41372dba584STejun Heo 4140a835c4fSMatthew Wilcox __set_bit(bit, bitmap->bitmap); 4150a835c4fSMatthew Wilcox if (bitmap_full(bitmap->bitmap, IDA_BITMAP_BITS)) 4160a835c4fSMatthew Wilcox radix_tree_iter_tag_clear(root, &iter, 4170a835c4fSMatthew Wilcox IDR_FREE); 4180a835c4fSMatthew Wilcox } else { 4190a835c4fSMatthew Wilcox new += bit; 4200a835c4fSMatthew Wilcox if (new < 0) 4210a835c4fSMatthew Wilcox return -ENOSPC; 4223159f943SMatthew Wilcox if (bit < BITS_PER_XA_VALUE) { 4233159f943SMatthew Wilcox bitmap = xa_mk_value(1UL << bit); 4243159f943SMatthew Wilcox } else { 4257ad3d4d8SMatthew Wilcox bitmap = this_cpu_xchg(ida_bitmap, NULL); 42672dba584STejun Heo if (!bitmap) 42772dba584STejun Heo return -EAGAIN; 4280a835c4fSMatthew Wilcox __set_bit(bit, bitmap->bitmap); 4293159f943SMatthew Wilcox } 4300a835c4fSMatthew Wilcox radix_tree_iter_replace(root, &iter, slot, bitmap); 43172dba584STejun Heo } 43272dba584STejun Heo 4331df89519SMatthew Wilcox return new; 43472dba584STejun Heo } 4350a835c4fSMatthew Wilcox } 43672dba584STejun Heo 437b03f8e43SMatthew Wilcox static void ida_remove(struct ida *ida, int id) 43872dba584STejun Heo { 4390a835c4fSMatthew Wilcox unsigned long index = id / IDA_BITMAP_BITS; 4400a835c4fSMatthew Wilcox unsigned offset = id % IDA_BITMAP_BITS; 44172dba584STejun Heo struct ida_bitmap *bitmap; 442d37cacc5SMatthew Wilcox unsigned long *btmp; 4430a835c4fSMatthew Wilcox struct radix_tree_iter iter; 4447e73eb0bSMatthew Wilcox void __rcu **slot; 44572dba584STejun Heo 4460a835c4fSMatthew Wilcox slot = radix_tree_iter_lookup(&ida->ida_rt, &iter, index); 4470a835c4fSMatthew Wilcox if (!slot) 4488f9f665aSLai Jiangshan goto err; 4498f9f665aSLai Jiangshan 4500a835c4fSMatthew Wilcox bitmap = rcu_dereference_raw(*slot); 4513159f943SMatthew Wilcox if (xa_is_value(bitmap)) { 452d37cacc5SMatthew Wilcox btmp = (unsigned long *)slot; 4533159f943SMatthew Wilcox offset += 1; /* Intimate knowledge of the value encoding */ 454d37cacc5SMatthew Wilcox if (offset >= BITS_PER_LONG) 455d37cacc5SMatthew Wilcox goto err; 456d37cacc5SMatthew Wilcox } else { 457d37cacc5SMatthew Wilcox btmp = bitmap->bitmap; 458d37cacc5SMatthew Wilcox } 459d37cacc5SMatthew Wilcox if (!test_bit(offset, btmp)) 46072dba584STejun Heo goto err; 46172dba584STejun Heo 462d37cacc5SMatthew Wilcox __clear_bit(offset, btmp); 4630a835c4fSMatthew Wilcox radix_tree_iter_tag_set(&ida->ida_rt, &iter, IDR_FREE); 4643159f943SMatthew Wilcox if (xa_is_value(bitmap)) { 4653159f943SMatthew Wilcox if (xa_to_value(rcu_dereference_raw(*slot)) == 0) 466d37cacc5SMatthew Wilcox radix_tree_iter_delete(&ida->ida_rt, &iter, slot); 467d37cacc5SMatthew Wilcox } else if (bitmap_empty(btmp, IDA_BITMAP_BITS)) { 4680a835c4fSMatthew Wilcox kfree(bitmap); 4690a835c4fSMatthew Wilcox radix_tree_iter_delete(&ida->ida_rt, &iter, slot); 47072dba584STejun Heo } 47172dba584STejun Heo return; 47272dba584STejun Heo err: 473b03f8e43SMatthew Wilcox WARN(1, "ida_free called for id=%d which is not allocated.\n", id); 47472dba584STejun Heo } 47572dba584STejun Heo 47672dba584STejun Heo /** 47750d97d50SMatthew Wilcox * ida_destroy() - Free all IDs. 47850d97d50SMatthew Wilcox * @ida: IDA handle. 4790a835c4fSMatthew Wilcox * 48050d97d50SMatthew Wilcox * Calling this function frees all IDs and releases all resources used 48150d97d50SMatthew Wilcox * by an IDA. When this call returns, the IDA is empty and can be reused 48250d97d50SMatthew Wilcox * or freed. If the IDA is already empty, there is no need to call this 48350d97d50SMatthew Wilcox * function. 48450d97d50SMatthew Wilcox * 48550d97d50SMatthew Wilcox * Context: Any context. 48672dba584STejun Heo */ 48772dba584STejun Heo void ida_destroy(struct ida *ida) 48872dba584STejun Heo { 48950d97d50SMatthew Wilcox unsigned long flags; 4900a835c4fSMatthew Wilcox struct radix_tree_iter iter; 4917e73eb0bSMatthew Wilcox void __rcu **slot; 4920a835c4fSMatthew Wilcox 49350d97d50SMatthew Wilcox xa_lock_irqsave(&ida->ida_rt, flags); 4940a835c4fSMatthew Wilcox radix_tree_for_each_slot(slot, &ida->ida_rt, &iter, 0) { 4950a835c4fSMatthew Wilcox struct ida_bitmap *bitmap = rcu_dereference_raw(*slot); 4963159f943SMatthew Wilcox if (!xa_is_value(bitmap)) 4970a835c4fSMatthew Wilcox kfree(bitmap); 4980a835c4fSMatthew Wilcox radix_tree_iter_delete(&ida->ida_rt, &iter, slot); 4990a835c4fSMatthew Wilcox } 50050d97d50SMatthew Wilcox xa_unlock_irqrestore(&ida->ida_rt, flags); 50172dba584STejun Heo } 50272dba584STejun Heo EXPORT_SYMBOL(ida_destroy); 50372dba584STejun Heo 50472dba584STejun Heo /** 5055ade60ddSMatthew Wilcox * ida_alloc_range() - Allocate an unused ID. 5065ade60ddSMatthew Wilcox * @ida: IDA handle. 5075ade60ddSMatthew Wilcox * @min: Lowest ID to allocate. 5085ade60ddSMatthew Wilcox * @max: Highest ID to allocate. 5095ade60ddSMatthew Wilcox * @gfp: Memory allocation flags. 51088eca020SRusty Russell * 5115ade60ddSMatthew Wilcox * Allocate an ID between @min and @max, inclusive. The allocated ID will 5125ade60ddSMatthew Wilcox * not exceed %INT_MAX, even if @max is larger. 51388eca020SRusty Russell * 5145ade60ddSMatthew Wilcox * Context: Any context. 5155ade60ddSMatthew Wilcox * Return: The allocated ID, or %-ENOMEM if memory could not be allocated, 5165ade60ddSMatthew Wilcox * or %-ENOSPC if there are no free IDs. 51788eca020SRusty Russell */ 5185ade60ddSMatthew Wilcox int ida_alloc_range(struct ida *ida, unsigned int min, unsigned int max, 5195ade60ddSMatthew Wilcox gfp_t gfp) 52088eca020SRusty Russell { 5211df89519SMatthew Wilcox int id = 0; 52246cbc1d3STejun Heo unsigned long flags; 52388eca020SRusty Russell 5245ade60ddSMatthew Wilcox if ((int)min < 0) 5255ade60ddSMatthew Wilcox return -ENOSPC; 52688eca020SRusty Russell 5275ade60ddSMatthew Wilcox if ((int)max < 0) 5285ade60ddSMatthew Wilcox max = INT_MAX; 52988eca020SRusty Russell 53088eca020SRusty Russell again: 531b94078e6SMatthew Wilcox xa_lock_irqsave(&ida->ida_rt, flags); 5321df89519SMatthew Wilcox id = ida_get_new_above(ida, min); 5331df89519SMatthew Wilcox if (id > (int)max) { 53488eca020SRusty Russell ida_remove(ida, id); 5351df89519SMatthew Wilcox id = -ENOSPC; 53688eca020SRusty Russell } 537b94078e6SMatthew Wilcox xa_unlock_irqrestore(&ida->ida_rt, flags); 53888eca020SRusty Russell 5391df89519SMatthew Wilcox if (unlikely(id == -EAGAIN)) { 5405ade60ddSMatthew Wilcox if (!ida_pre_get(ida, gfp)) 5415ade60ddSMatthew Wilcox return -ENOMEM; 54288eca020SRusty Russell goto again; 5435ade60ddSMatthew Wilcox } 54488eca020SRusty Russell 5451df89519SMatthew Wilcox return id; 54688eca020SRusty Russell } 5475ade60ddSMatthew Wilcox EXPORT_SYMBOL(ida_alloc_range); 54888eca020SRusty Russell 54988eca020SRusty Russell /** 5505ade60ddSMatthew Wilcox * ida_free() - Release an allocated ID. 5515ade60ddSMatthew Wilcox * @ida: IDA handle. 5525ade60ddSMatthew Wilcox * @id: Previously allocated ID. 553a2ef9471SDaniel Vetter * 5545ade60ddSMatthew Wilcox * Context: Any context. 55588eca020SRusty Russell */ 5565ade60ddSMatthew Wilcox void ida_free(struct ida *ida, unsigned int id) 55788eca020SRusty Russell { 55846cbc1d3STejun Heo unsigned long flags; 55946cbc1d3STejun Heo 56088eca020SRusty Russell BUG_ON((int)id < 0); 561b94078e6SMatthew Wilcox xa_lock_irqsave(&ida->ida_rt, flags); 56288eca020SRusty Russell ida_remove(ida, id); 563b94078e6SMatthew Wilcox xa_unlock_irqrestore(&ida->ida_rt, flags); 56488eca020SRusty Russell } 5655ade60ddSMatthew Wilcox EXPORT_SYMBOL(ida_free); 566