10a835c4fSMatthew Wilcox #include <linux/bitmap.h> 28bc3bcc9SPaul Gortmaker #include <linux/export.h> 31da177e4SLinus Torvalds #include <linux/idr.h> 40a835c4fSMatthew Wilcox #include <linux/slab.h> 588eca020SRusty Russell #include <linux/spinlock.h> 61da177e4SLinus Torvalds 77ad3d4d8SMatthew Wilcox DEFINE_PER_CPU(struct ida_bitmap *, ida_bitmap); 888eca020SRusty Russell static DEFINE_SPINLOCK(simple_ida_lock); 91da177e4SLinus Torvalds 10388f79fdSChris Mi int idr_alloc_cmn(struct idr *idr, void *ptr, unsigned long *index, 11388f79fdSChris Mi unsigned long start, unsigned long end, gfp_t gfp, 12388f79fdSChris Mi bool ext) 13d5c7409fSTejun Heo { 140a835c4fSMatthew Wilcox struct radix_tree_iter iter; 15388f79fdSChris Mi void __rcu **slot; 16d5c7409fSTejun Heo 170a835c4fSMatthew Wilcox if (WARN_ON_ONCE(radix_tree_is_internal_node(ptr))) 180a835c4fSMatthew Wilcox return -EINVAL; 19d5c7409fSTejun Heo 200a835c4fSMatthew Wilcox radix_tree_iter_init(&iter, start); 21388f79fdSChris Mi if (ext) 22388f79fdSChris Mi slot = idr_get_free_ext(&idr->idr_rt, &iter, gfp, end); 23388f79fdSChris Mi else 240a835c4fSMatthew Wilcox slot = idr_get_free(&idr->idr_rt, &iter, gfp, end); 250a835c4fSMatthew Wilcox if (IS_ERR(slot)) 260a835c4fSMatthew Wilcox return PTR_ERR(slot); 27d5c7409fSTejun Heo 280a835c4fSMatthew Wilcox radix_tree_iter_replace(&idr->idr_rt, &iter, slot, ptr); 290a835c4fSMatthew Wilcox radix_tree_iter_tag_clear(&idr->idr_rt, &iter, IDR_FREE); 30388f79fdSChris Mi 31388f79fdSChris Mi if (index) 32388f79fdSChris Mi *index = iter.index; 33388f79fdSChris Mi return 0; 34d5c7409fSTejun Heo } 35388f79fdSChris Mi EXPORT_SYMBOL_GPL(idr_alloc_cmn); 36d5c7409fSTejun Heo 373e6628c4SJeff Layton /** 383e6628c4SJeff Layton * idr_alloc_cyclic - allocate new idr entry in a cyclical fashion 390a835c4fSMatthew Wilcox * @idr: idr handle 403e6628c4SJeff Layton * @ptr: pointer to be associated with the new id 413e6628c4SJeff Layton * @start: the minimum id (inclusive) 420a835c4fSMatthew Wilcox * @end: the maximum id (exclusive) 430a835c4fSMatthew Wilcox * @gfp: memory allocation flags 443e6628c4SJeff Layton * 450a835c4fSMatthew Wilcox * Allocates an ID larger than the last ID allocated if one is available. 460a835c4fSMatthew Wilcox * If not, it will attempt to allocate the smallest ID that is larger or 470a835c4fSMatthew Wilcox * equal to @start. 483e6628c4SJeff Layton */ 490a835c4fSMatthew Wilcox int idr_alloc_cyclic(struct idr *idr, void *ptr, int start, int end, gfp_t gfp) 503e6628c4SJeff Layton { 510a835c4fSMatthew Wilcox int id, curr = idr->idr_next; 523e6628c4SJeff Layton 530a835c4fSMatthew Wilcox if (curr < start) 540a835c4fSMatthew Wilcox curr = start; 553e6628c4SJeff Layton 560a835c4fSMatthew Wilcox id = idr_alloc(idr, ptr, curr, end, gfp); 570a835c4fSMatthew Wilcox if ((id == -ENOSPC) && (curr > start)) 580a835c4fSMatthew Wilcox id = idr_alloc(idr, ptr, start, curr, gfp); 590a835c4fSMatthew Wilcox 600a835c4fSMatthew Wilcox if (id >= 0) 610a835c4fSMatthew Wilcox idr->idr_next = id + 1U; 620a835c4fSMatthew Wilcox 633e6628c4SJeff Layton return id; 643e6628c4SJeff Layton } 653e6628c4SJeff Layton EXPORT_SYMBOL(idr_alloc_cyclic); 663e6628c4SJeff Layton 675806f07cSJeff Mahoney /** 6896d7fa42SKristian Hoegsberg * idr_for_each - iterate through all stored pointers 690a835c4fSMatthew Wilcox * @idr: idr handle 7096d7fa42SKristian Hoegsberg * @fn: function to be called for each pointer 710a835c4fSMatthew Wilcox * @data: data passed to callback function 7296d7fa42SKristian Hoegsberg * 730a835c4fSMatthew Wilcox * The callback function will be called for each entry in @idr, passing 740a835c4fSMatthew Wilcox * the id, the pointer and the data pointer passed to this function. 7596d7fa42SKristian Hoegsberg * 760a835c4fSMatthew Wilcox * If @fn returns anything other than %0, the iteration stops and that 770a835c4fSMatthew Wilcox * value is returned from this function. 7896d7fa42SKristian Hoegsberg * 790a835c4fSMatthew Wilcox * idr_for_each() can be called concurrently with idr_alloc() and 800a835c4fSMatthew Wilcox * idr_remove() if protected by RCU. Newly added entries may not be 810a835c4fSMatthew Wilcox * seen and deleted entries may be seen, but adding and removing entries 820a835c4fSMatthew Wilcox * will not cause other entries to be skipped, nor spurious ones to be seen. 8396d7fa42SKristian Hoegsberg */ 840a835c4fSMatthew Wilcox int idr_for_each(const struct idr *idr, 8596d7fa42SKristian Hoegsberg int (*fn)(int id, void *p, void *data), void *data) 8696d7fa42SKristian Hoegsberg { 870a835c4fSMatthew Wilcox struct radix_tree_iter iter; 887e73eb0bSMatthew Wilcox void __rcu **slot; 8996d7fa42SKristian Hoegsberg 900a835c4fSMatthew Wilcox radix_tree_for_each_slot(slot, &idr->idr_rt, &iter, 0) { 910a835c4fSMatthew Wilcox int ret = fn(iter.index, rcu_dereference_raw(*slot), data); 920a835c4fSMatthew Wilcox if (ret) 930a835c4fSMatthew Wilcox return ret; 9496d7fa42SKristian Hoegsberg } 9596d7fa42SKristian Hoegsberg 960a835c4fSMatthew Wilcox return 0; 9796d7fa42SKristian Hoegsberg } 9896d7fa42SKristian Hoegsberg EXPORT_SYMBOL(idr_for_each); 9996d7fa42SKristian Hoegsberg 10096d7fa42SKristian Hoegsberg /** 1010a835c4fSMatthew Wilcox * idr_get_next - Find next populated entry 1020a835c4fSMatthew Wilcox * @idr: idr handle 1030a835c4fSMatthew Wilcox * @nextid: Pointer to lowest possible ID to return 10438460b48SKAMEZAWA Hiroyuki * 1050a835c4fSMatthew Wilcox * Returns the next populated entry in the tree with an ID greater than 1060a835c4fSMatthew Wilcox * or equal to the value pointed to by @nextid. On exit, @nextid is updated 1070a835c4fSMatthew Wilcox * to the ID of the found value. To use in a loop, the value pointed to by 1080a835c4fSMatthew Wilcox * nextid must be incremented by the user. 10938460b48SKAMEZAWA Hiroyuki */ 1100a835c4fSMatthew Wilcox void *idr_get_next(struct idr *idr, int *nextid) 11138460b48SKAMEZAWA Hiroyuki { 1120a835c4fSMatthew Wilcox struct radix_tree_iter iter; 1137e73eb0bSMatthew Wilcox void __rcu **slot; 11438460b48SKAMEZAWA Hiroyuki 1150a835c4fSMatthew Wilcox slot = radix_tree_iter_find(&idr->idr_rt, &iter, *nextid); 1160a835c4fSMatthew Wilcox if (!slot) 11738460b48SKAMEZAWA Hiroyuki return NULL; 11838460b48SKAMEZAWA Hiroyuki 1190a835c4fSMatthew Wilcox *nextid = iter.index; 1200a835c4fSMatthew Wilcox return rcu_dereference_raw(*slot); 12138460b48SKAMEZAWA Hiroyuki } 1224d1ee80fSBen Hutchings EXPORT_SYMBOL(idr_get_next); 12338460b48SKAMEZAWA Hiroyuki 124388f79fdSChris Mi void *idr_get_next_ext(struct idr *idr, unsigned long *nextid) 125388f79fdSChris Mi { 126388f79fdSChris Mi struct radix_tree_iter iter; 127388f79fdSChris Mi void __rcu **slot; 128388f79fdSChris Mi 129388f79fdSChris Mi slot = radix_tree_iter_find(&idr->idr_rt, &iter, *nextid); 130388f79fdSChris Mi if (!slot) 131388f79fdSChris Mi return NULL; 132388f79fdSChris Mi 133388f79fdSChris Mi *nextid = iter.index; 134388f79fdSChris Mi return rcu_dereference_raw(*slot); 135388f79fdSChris Mi } 136388f79fdSChris Mi EXPORT_SYMBOL(idr_get_next_ext); 137388f79fdSChris Mi 13838460b48SKAMEZAWA Hiroyuki /** 1395806f07cSJeff Mahoney * idr_replace - replace pointer for given id 1400a835c4fSMatthew Wilcox * @idr: idr handle 1410a835c4fSMatthew Wilcox * @ptr: New pointer to associate with the ID 1420a835c4fSMatthew Wilcox * @id: Lookup key 1435806f07cSJeff Mahoney * 1440a835c4fSMatthew Wilcox * Replace the pointer registered with an ID and return the old value. 1450a835c4fSMatthew Wilcox * This function can be called under the RCU read lock concurrently with 1460a835c4fSMatthew Wilcox * idr_alloc() and idr_remove() (as long as the ID being removed is not 1470a835c4fSMatthew Wilcox * the one being replaced!). 1485806f07cSJeff Mahoney * 149a70e43a5SEric Biggers * Returns: the old value on success. %-ENOENT indicates that @id was not 150a70e43a5SEric Biggers * found. %-EINVAL indicates that @id or @ptr were not valid. 1515806f07cSJeff Mahoney */ 1520a835c4fSMatthew Wilcox void *idr_replace(struct idr *idr, void *ptr, int id) 1535806f07cSJeff Mahoney { 154a47f68d6SEric Biggers if (id < 0) 155388f79fdSChris Mi return ERR_PTR(-EINVAL); 156388f79fdSChris Mi 157388f79fdSChris Mi return idr_replace_ext(idr, ptr, id); 158388f79fdSChris Mi } 159388f79fdSChris Mi EXPORT_SYMBOL(idr_replace); 160388f79fdSChris Mi 161388f79fdSChris Mi void *idr_replace_ext(struct idr *idr, void *ptr, unsigned long id) 162388f79fdSChris Mi { 1630a835c4fSMatthew Wilcox struct radix_tree_node *node; 1647e73eb0bSMatthew Wilcox void __rcu **slot = NULL; 1650a835c4fSMatthew Wilcox void *entry; 1665806f07cSJeff Mahoney 1670a835c4fSMatthew Wilcox if (WARN_ON_ONCE(radix_tree_is_internal_node(ptr))) 168e8c8d1bcSTejun Heo return ERR_PTR(-EINVAL); 169e8c8d1bcSTejun Heo 1700a835c4fSMatthew Wilcox entry = __radix_tree_lookup(&idr->idr_rt, id, &node, &slot); 1710a835c4fSMatthew Wilcox if (!slot || radix_tree_tag_get(&idr->idr_rt, id, IDR_FREE)) 172b93804b2SLai Jiangshan return ERR_PTR(-ENOENT); 1736ff2d39bSManfred Spraul 1740a835c4fSMatthew Wilcox __radix_tree_replace(&idr->idr_rt, node, slot, ptr, NULL, NULL); 1755806f07cSJeff Mahoney 1760a835c4fSMatthew Wilcox return entry; 1775806f07cSJeff Mahoney } 178388f79fdSChris Mi EXPORT_SYMBOL(idr_replace_ext); 1795806f07cSJeff Mahoney 18056083ab1SRandy Dunlap /** 18156083ab1SRandy Dunlap * DOC: IDA description 18272dba584STejun Heo * 1830a835c4fSMatthew Wilcox * The IDA is an ID allocator which does not provide the ability to 1840a835c4fSMatthew Wilcox * associate an ID with a pointer. As such, it only needs to store one 1850a835c4fSMatthew Wilcox * bit per ID, and so is more space efficient than an IDR. To use an IDA, 1860a835c4fSMatthew Wilcox * define it using DEFINE_IDA() (or embed a &struct ida in a data structure, 1870a835c4fSMatthew Wilcox * then initialise it using ida_init()). To allocate a new ID, call 1880a835c4fSMatthew Wilcox * ida_simple_get(). To free an ID, call ida_simple_remove(). 18972dba584STejun Heo * 1900a835c4fSMatthew Wilcox * If you have more complex locking requirements, use a loop around 1910a835c4fSMatthew Wilcox * ida_pre_get() and ida_get_new() to allocate a new ID. Then use 1920a835c4fSMatthew Wilcox * ida_remove() to free an ID. You must make sure that ida_get_new() and 1930a835c4fSMatthew Wilcox * ida_remove() cannot be called at the same time as each other for the 1940a835c4fSMatthew Wilcox * same IDA. 1950a835c4fSMatthew Wilcox * 1960a835c4fSMatthew Wilcox * You can also use ida_get_new_above() if you need an ID to be allocated 1970a835c4fSMatthew Wilcox * above a particular number. ida_destroy() can be used to dispose of an 1980a835c4fSMatthew Wilcox * IDA without needing to free the individual IDs in it. You can use 1990a835c4fSMatthew Wilcox * ida_is_empty() to find out whether the IDA has any IDs currently allocated. 2000a835c4fSMatthew Wilcox * 2010a835c4fSMatthew Wilcox * IDs are currently limited to the range [0-INT_MAX]. If this is an awkward 2020a835c4fSMatthew Wilcox * limitation, it should be quite straightforward to raise the maximum. 20372dba584STejun Heo */ 20472dba584STejun Heo 205d37cacc5SMatthew Wilcox /* 206d37cacc5SMatthew Wilcox * Developer's notes: 207d37cacc5SMatthew Wilcox * 208d37cacc5SMatthew Wilcox * The IDA uses the functionality provided by the IDR & radix tree to store 209d37cacc5SMatthew Wilcox * bitmaps in each entry. The IDR_FREE tag means there is at least one bit 210d37cacc5SMatthew Wilcox * free, unlike the IDR where it means at least one entry is free. 211d37cacc5SMatthew Wilcox * 212d37cacc5SMatthew Wilcox * I considered telling the radix tree that each slot is an order-10 node 213d37cacc5SMatthew Wilcox * and storing the bit numbers in the radix tree, but the radix tree can't 214d37cacc5SMatthew Wilcox * allow a single multiorder entry at index 0, which would significantly 215d37cacc5SMatthew Wilcox * increase memory consumption for the IDA. So instead we divide the index 216d37cacc5SMatthew Wilcox * by the number of bits in the leaf bitmap before doing a radix tree lookup. 217d37cacc5SMatthew Wilcox * 218d37cacc5SMatthew Wilcox * As an optimisation, if there are only a few low bits set in any given 219d37cacc5SMatthew Wilcox * leaf, instead of allocating a 128-byte bitmap, we use the 'exceptional 220d37cacc5SMatthew Wilcox * entry' functionality of the radix tree to store BITS_PER_LONG - 2 bits 221d37cacc5SMatthew Wilcox * directly in the entry. By being really tricksy, we could store 222d37cacc5SMatthew Wilcox * BITS_PER_LONG - 1 bits, but there're diminishing returns after optimising 223d37cacc5SMatthew Wilcox * for 0-3 allocated IDs. 224d37cacc5SMatthew Wilcox * 225d37cacc5SMatthew Wilcox * We allow the radix tree 'exceptional' count to get out of date. Nothing 226d37cacc5SMatthew Wilcox * in the IDA nor the radix tree code checks it. If it becomes important 227d37cacc5SMatthew Wilcox * to maintain an accurate exceptional count, switch the rcu_assign_pointer() 228d37cacc5SMatthew Wilcox * calls to radix_tree_iter_replace() which will correct the exceptional 229d37cacc5SMatthew Wilcox * count. 230d37cacc5SMatthew Wilcox * 231d37cacc5SMatthew Wilcox * The IDA always requires a lock to alloc/free. If we add a 'test_bit' 232d37cacc5SMatthew Wilcox * equivalent, it will still need locking. Going to RCU lookup would require 233d37cacc5SMatthew Wilcox * using RCU to free bitmaps, and that's not trivial without embedding an 234d37cacc5SMatthew Wilcox * RCU head in the bitmap, which adds a 2-pointer overhead to each 128-byte 235d37cacc5SMatthew Wilcox * bitmap, which is excessive. 236d37cacc5SMatthew Wilcox */ 237d37cacc5SMatthew Wilcox 2380a835c4fSMatthew Wilcox #define IDA_MAX (0x80000000U / IDA_BITMAP_BITS) 2390a835c4fSMatthew Wilcox 24072dba584STejun Heo /** 24172dba584STejun Heo * ida_get_new_above - allocate new ID above or equal to a start id 24272dba584STejun Heo * @ida: ida handle 2430a835c4fSMatthew Wilcox * @start: id to start search at 2440a835c4fSMatthew Wilcox * @id: pointer to the allocated handle 24572dba584STejun Heo * 2460a835c4fSMatthew Wilcox * Allocate new ID above or equal to @start. It should be called 2470a835c4fSMatthew Wilcox * with any required locks to ensure that concurrent calls to 2480a835c4fSMatthew Wilcox * ida_get_new_above() / ida_get_new() / ida_remove() are not allowed. 2490a835c4fSMatthew Wilcox * Consider using ida_simple_get() if you do not have complex locking 2500a835c4fSMatthew Wilcox * requirements. 25172dba584STejun Heo * 25256083ab1SRandy Dunlap * If memory is required, it will return %-EAGAIN, you should unlock 25372dba584STejun Heo * and go back to the ida_pre_get() call. If the ida is full, it will 2540a835c4fSMatthew Wilcox * return %-ENOSPC. On success, it will return 0. 25572dba584STejun Heo * 2560a835c4fSMatthew Wilcox * @id returns a value in the range @start ... %0x7fffffff. 25772dba584STejun Heo */ 2580a835c4fSMatthew Wilcox int ida_get_new_above(struct ida *ida, int start, int *id) 25972dba584STejun Heo { 2600a835c4fSMatthew Wilcox struct radix_tree_root *root = &ida->ida_rt; 2617e73eb0bSMatthew Wilcox void __rcu **slot; 2620a835c4fSMatthew Wilcox struct radix_tree_iter iter; 26372dba584STejun Heo struct ida_bitmap *bitmap; 2640a835c4fSMatthew Wilcox unsigned long index; 265d37cacc5SMatthew Wilcox unsigned bit, ebit; 2660a835c4fSMatthew Wilcox int new; 26772dba584STejun Heo 2680a835c4fSMatthew Wilcox index = start / IDA_BITMAP_BITS; 2690a835c4fSMatthew Wilcox bit = start % IDA_BITMAP_BITS; 270d37cacc5SMatthew Wilcox ebit = bit + RADIX_TREE_EXCEPTIONAL_SHIFT; 27172dba584STejun Heo 2720a835c4fSMatthew Wilcox slot = radix_tree_iter_init(&iter, index); 2730a835c4fSMatthew Wilcox for (;;) { 2740a835c4fSMatthew Wilcox if (slot) 2750a835c4fSMatthew Wilcox slot = radix_tree_next_slot(slot, &iter, 2760a835c4fSMatthew Wilcox RADIX_TREE_ITER_TAGGED); 2770a835c4fSMatthew Wilcox if (!slot) { 2780a835c4fSMatthew Wilcox slot = idr_get_free(root, &iter, GFP_NOWAIT, IDA_MAX); 2790a835c4fSMatthew Wilcox if (IS_ERR(slot)) { 2800a835c4fSMatthew Wilcox if (slot == ERR_PTR(-ENOMEM)) 2810a835c4fSMatthew Wilcox return -EAGAIN; 2820a835c4fSMatthew Wilcox return PTR_ERR(slot); 2830a835c4fSMatthew Wilcox } 2840a835c4fSMatthew Wilcox } 285d37cacc5SMatthew Wilcox if (iter.index > index) { 2860a835c4fSMatthew Wilcox bit = 0; 287d37cacc5SMatthew Wilcox ebit = RADIX_TREE_EXCEPTIONAL_SHIFT; 288d37cacc5SMatthew Wilcox } 2890a835c4fSMatthew Wilcox new = iter.index * IDA_BITMAP_BITS; 2900a835c4fSMatthew Wilcox bitmap = rcu_dereference_raw(*slot); 291d37cacc5SMatthew Wilcox if (radix_tree_exception(bitmap)) { 292d37cacc5SMatthew Wilcox unsigned long tmp = (unsigned long)bitmap; 293d37cacc5SMatthew Wilcox ebit = find_next_zero_bit(&tmp, BITS_PER_LONG, ebit); 294d37cacc5SMatthew Wilcox if (ebit < BITS_PER_LONG) { 295d37cacc5SMatthew Wilcox tmp |= 1UL << ebit; 296d37cacc5SMatthew Wilcox rcu_assign_pointer(*slot, (void *)tmp); 297d37cacc5SMatthew Wilcox *id = new + ebit - RADIX_TREE_EXCEPTIONAL_SHIFT; 298d37cacc5SMatthew Wilcox return 0; 299d37cacc5SMatthew Wilcox } 300d37cacc5SMatthew Wilcox bitmap = this_cpu_xchg(ida_bitmap, NULL); 301d37cacc5SMatthew Wilcox if (!bitmap) 302d37cacc5SMatthew Wilcox return -EAGAIN; 303d37cacc5SMatthew Wilcox memset(bitmap, 0, sizeof(*bitmap)); 304d37cacc5SMatthew Wilcox bitmap->bitmap[0] = tmp >> RADIX_TREE_EXCEPTIONAL_SHIFT; 305d37cacc5SMatthew Wilcox rcu_assign_pointer(*slot, bitmap); 306d37cacc5SMatthew Wilcox } 307d37cacc5SMatthew Wilcox 3080a835c4fSMatthew Wilcox if (bitmap) { 3090a835c4fSMatthew Wilcox bit = find_next_zero_bit(bitmap->bitmap, 3100a835c4fSMatthew Wilcox IDA_BITMAP_BITS, bit); 3110a835c4fSMatthew Wilcox new += bit; 3120a835c4fSMatthew Wilcox if (new < 0) 31372dba584STejun Heo return -ENOSPC; 3140a835c4fSMatthew Wilcox if (bit == IDA_BITMAP_BITS) 3150a835c4fSMatthew Wilcox continue; 31672dba584STejun Heo 3170a835c4fSMatthew Wilcox __set_bit(bit, bitmap->bitmap); 3180a835c4fSMatthew Wilcox if (bitmap_full(bitmap->bitmap, IDA_BITMAP_BITS)) 3190a835c4fSMatthew Wilcox radix_tree_iter_tag_clear(root, &iter, 3200a835c4fSMatthew Wilcox IDR_FREE); 3210a835c4fSMatthew Wilcox } else { 3220a835c4fSMatthew Wilcox new += bit; 3230a835c4fSMatthew Wilcox if (new < 0) 3240a835c4fSMatthew Wilcox return -ENOSPC; 325d37cacc5SMatthew Wilcox if (ebit < BITS_PER_LONG) { 326d37cacc5SMatthew Wilcox bitmap = (void *)((1UL << ebit) | 327d37cacc5SMatthew Wilcox RADIX_TREE_EXCEPTIONAL_ENTRY); 328d37cacc5SMatthew Wilcox radix_tree_iter_replace(root, &iter, slot, 329d37cacc5SMatthew Wilcox bitmap); 330d37cacc5SMatthew Wilcox *id = new; 331d37cacc5SMatthew Wilcox return 0; 332d37cacc5SMatthew Wilcox } 3337ad3d4d8SMatthew Wilcox bitmap = this_cpu_xchg(ida_bitmap, NULL); 33472dba584STejun Heo if (!bitmap) 33572dba584STejun Heo return -EAGAIN; 3360a835c4fSMatthew Wilcox memset(bitmap, 0, sizeof(*bitmap)); 3370a835c4fSMatthew Wilcox __set_bit(bit, bitmap->bitmap); 3380a835c4fSMatthew Wilcox radix_tree_iter_replace(root, &iter, slot, bitmap); 33972dba584STejun Heo } 34072dba584STejun Heo 3410a835c4fSMatthew Wilcox *id = new; 34272dba584STejun Heo return 0; 34372dba584STejun Heo } 3440a835c4fSMatthew Wilcox } 34572dba584STejun Heo EXPORT_SYMBOL(ida_get_new_above); 34672dba584STejun Heo 34772dba584STejun Heo /** 3480a835c4fSMatthew Wilcox * ida_remove - Free the given ID 34972dba584STejun Heo * @ida: ida handle 35072dba584STejun Heo * @id: ID to free 3510a835c4fSMatthew Wilcox * 3520a835c4fSMatthew Wilcox * This function should not be called at the same time as ida_get_new_above(). 35372dba584STejun Heo */ 35472dba584STejun Heo void ida_remove(struct ida *ida, int id) 35572dba584STejun Heo { 3560a835c4fSMatthew Wilcox unsigned long index = id / IDA_BITMAP_BITS; 3570a835c4fSMatthew Wilcox unsigned offset = id % IDA_BITMAP_BITS; 35872dba584STejun Heo struct ida_bitmap *bitmap; 359d37cacc5SMatthew Wilcox unsigned long *btmp; 3600a835c4fSMatthew Wilcox struct radix_tree_iter iter; 3617e73eb0bSMatthew Wilcox void __rcu **slot; 36272dba584STejun Heo 3630a835c4fSMatthew Wilcox slot = radix_tree_iter_lookup(&ida->ida_rt, &iter, index); 3640a835c4fSMatthew Wilcox if (!slot) 3658f9f665aSLai Jiangshan goto err; 3668f9f665aSLai Jiangshan 3670a835c4fSMatthew Wilcox bitmap = rcu_dereference_raw(*slot); 368d37cacc5SMatthew Wilcox if (radix_tree_exception(bitmap)) { 369d37cacc5SMatthew Wilcox btmp = (unsigned long *)slot; 370d37cacc5SMatthew Wilcox offset += RADIX_TREE_EXCEPTIONAL_SHIFT; 371d37cacc5SMatthew Wilcox if (offset >= BITS_PER_LONG) 372d37cacc5SMatthew Wilcox goto err; 373d37cacc5SMatthew Wilcox } else { 374d37cacc5SMatthew Wilcox btmp = bitmap->bitmap; 375d37cacc5SMatthew Wilcox } 376d37cacc5SMatthew Wilcox if (!test_bit(offset, btmp)) 37772dba584STejun Heo goto err; 37872dba584STejun Heo 379d37cacc5SMatthew Wilcox __clear_bit(offset, btmp); 3800a835c4fSMatthew Wilcox radix_tree_iter_tag_set(&ida->ida_rt, &iter, IDR_FREE); 381d37cacc5SMatthew Wilcox if (radix_tree_exception(bitmap)) { 382d37cacc5SMatthew Wilcox if (rcu_dereference_raw(*slot) == 383d37cacc5SMatthew Wilcox (void *)RADIX_TREE_EXCEPTIONAL_ENTRY) 384d37cacc5SMatthew Wilcox radix_tree_iter_delete(&ida->ida_rt, &iter, slot); 385d37cacc5SMatthew Wilcox } else if (bitmap_empty(btmp, IDA_BITMAP_BITS)) { 3860a835c4fSMatthew Wilcox kfree(bitmap); 3870a835c4fSMatthew Wilcox radix_tree_iter_delete(&ida->ida_rt, &iter, slot); 38872dba584STejun Heo } 38972dba584STejun Heo return; 39072dba584STejun Heo err: 391dd04b452SJean Delvare WARN(1, "ida_remove called for id=%d which is not allocated.\n", id); 39272dba584STejun Heo } 39372dba584STejun Heo EXPORT_SYMBOL(ida_remove); 39472dba584STejun Heo 39572dba584STejun Heo /** 3960a835c4fSMatthew Wilcox * ida_destroy - Free the contents of an ida 397ea24ea85SNaohiro Aota * @ida: ida handle 3980a835c4fSMatthew Wilcox * 3990a835c4fSMatthew Wilcox * Calling this function releases all resources associated with an IDA. When 4000a835c4fSMatthew Wilcox * this call returns, the IDA is empty and can be reused or freed. The caller 4010a835c4fSMatthew Wilcox * should not allow ida_remove() or ida_get_new_above() to be called at the 4020a835c4fSMatthew Wilcox * same time. 40372dba584STejun Heo */ 40472dba584STejun Heo void ida_destroy(struct ida *ida) 40572dba584STejun Heo { 4060a835c4fSMatthew Wilcox struct radix_tree_iter iter; 4077e73eb0bSMatthew Wilcox void __rcu **slot; 4080a835c4fSMatthew Wilcox 4090a835c4fSMatthew Wilcox radix_tree_for_each_slot(slot, &ida->ida_rt, &iter, 0) { 4100a835c4fSMatthew Wilcox struct ida_bitmap *bitmap = rcu_dereference_raw(*slot); 411d37cacc5SMatthew Wilcox if (!radix_tree_exception(bitmap)) 4120a835c4fSMatthew Wilcox kfree(bitmap); 4130a835c4fSMatthew Wilcox radix_tree_iter_delete(&ida->ida_rt, &iter, slot); 4140a835c4fSMatthew Wilcox } 41572dba584STejun Heo } 41672dba584STejun Heo EXPORT_SYMBOL(ida_destroy); 41772dba584STejun Heo 41872dba584STejun Heo /** 41988eca020SRusty Russell * ida_simple_get - get a new id. 42088eca020SRusty Russell * @ida: the (initialized) ida. 42188eca020SRusty Russell * @start: the minimum id (inclusive, < 0x8000000) 42288eca020SRusty Russell * @end: the maximum id (exclusive, < 0x8000000 or 0) 42388eca020SRusty Russell * @gfp_mask: memory allocation flags 42488eca020SRusty Russell * 42588eca020SRusty Russell * Allocates an id in the range start <= id < end, or returns -ENOSPC. 42688eca020SRusty Russell * On memory allocation failure, returns -ENOMEM. 42788eca020SRusty Russell * 428a2ef9471SDaniel Vetter * Compared to ida_get_new_above() this function does its own locking, and 429a2ef9471SDaniel Vetter * should be used unless there are special requirements. 430a2ef9471SDaniel Vetter * 43188eca020SRusty Russell * Use ida_simple_remove() to get rid of an id. 43288eca020SRusty Russell */ 43388eca020SRusty Russell int ida_simple_get(struct ida *ida, unsigned int start, unsigned int end, 43488eca020SRusty Russell gfp_t gfp_mask) 43588eca020SRusty Russell { 43688eca020SRusty Russell int ret, id; 43788eca020SRusty Russell unsigned int max; 43846cbc1d3STejun Heo unsigned long flags; 43988eca020SRusty Russell 44088eca020SRusty Russell BUG_ON((int)start < 0); 44188eca020SRusty Russell BUG_ON((int)end < 0); 44288eca020SRusty Russell 44388eca020SRusty Russell if (end == 0) 44488eca020SRusty Russell max = 0x80000000; 44588eca020SRusty Russell else { 44688eca020SRusty Russell BUG_ON(end < start); 44788eca020SRusty Russell max = end - 1; 44888eca020SRusty Russell } 44988eca020SRusty Russell 45088eca020SRusty Russell again: 45188eca020SRusty Russell if (!ida_pre_get(ida, gfp_mask)) 45288eca020SRusty Russell return -ENOMEM; 45388eca020SRusty Russell 45446cbc1d3STejun Heo spin_lock_irqsave(&simple_ida_lock, flags); 45588eca020SRusty Russell ret = ida_get_new_above(ida, start, &id); 45688eca020SRusty Russell if (!ret) { 45788eca020SRusty Russell if (id > max) { 45888eca020SRusty Russell ida_remove(ida, id); 45988eca020SRusty Russell ret = -ENOSPC; 46088eca020SRusty Russell } else { 46188eca020SRusty Russell ret = id; 46288eca020SRusty Russell } 46388eca020SRusty Russell } 46446cbc1d3STejun Heo spin_unlock_irqrestore(&simple_ida_lock, flags); 46588eca020SRusty Russell 46688eca020SRusty Russell if (unlikely(ret == -EAGAIN)) 46788eca020SRusty Russell goto again; 46888eca020SRusty Russell 46988eca020SRusty Russell return ret; 47088eca020SRusty Russell } 47188eca020SRusty Russell EXPORT_SYMBOL(ida_simple_get); 47288eca020SRusty Russell 47388eca020SRusty Russell /** 47488eca020SRusty Russell * ida_simple_remove - remove an allocated id. 47588eca020SRusty Russell * @ida: the (initialized) ida. 47688eca020SRusty Russell * @id: the id returned by ida_simple_get. 477a2ef9471SDaniel Vetter * 478a2ef9471SDaniel Vetter * Use to release an id allocated with ida_simple_get(). 479a2ef9471SDaniel Vetter * 480a2ef9471SDaniel Vetter * Compared to ida_remove() this function does its own locking, and should be 481a2ef9471SDaniel Vetter * used unless there are special requirements. 48288eca020SRusty Russell */ 48388eca020SRusty Russell void ida_simple_remove(struct ida *ida, unsigned int id) 48488eca020SRusty Russell { 48546cbc1d3STejun Heo unsigned long flags; 48646cbc1d3STejun Heo 48788eca020SRusty Russell BUG_ON((int)id < 0); 48846cbc1d3STejun Heo spin_lock_irqsave(&simple_ida_lock, flags); 48988eca020SRusty Russell ida_remove(ida, id); 49046cbc1d3STejun Heo spin_unlock_irqrestore(&simple_ida_lock, flags); 49188eca020SRusty Russell } 49288eca020SRusty Russell EXPORT_SYMBOL(ida_simple_remove); 493