diff options
Diffstat (limited to 'lib/idr.c')
| -rw-r--r-- | lib/idr.c | 1537 |
1 files changed, 521 insertions, 1016 deletions
diff --git a/lib/idr.c b/lib/idr.c index bfe4db4e165f..e2adc457abb4 100644 --- a/lib/idr.c +++ b/lib/idr.c @@ -1,1161 +1,666 @@ -/* - * 2002-10-18 written by Jim Houston jim.houston@ccur.com - * Copyright (C) 2002 by Concurrent Computer Corporation - * Distributed under the GNU GPL license version 2. - * - * Modified by George Anzinger to reuse immediately and to use - * find bit instructions. Also removed _irq on spinlocks. - * - * Modified by Nadia Derbey to make it RCU safe. - * - * Small id to pointer translation service. - * - * It uses a radix tree like structure as a sparse array indexed - * by the id to obtain the pointer. The bitmap makes allocating - * a new id quick. - * - * You call it to allocate an id (an int) an associate with that id a - * pointer or what ever, we treat it as a (void *). You can pass this - * id to a user for him to pass back at a later time. You then pass - * that id to this code and it returns your pointer. - - * You can release ids at any time. When all ids are released, most of - * the memory is returned (we keep MAX_IDR_FREE) in a local pool so we - * don't need to go to the memory "store" during an id allocate, just - * so you don't need to be too concerned about locking and conflicts - * with the slab allocator. - */ - -#ifndef TEST // to test in user space... -#include <linux/slab.h> -#include <linux/init.h> +// SPDX-License-Identifier: GPL-2.0-only +#include <linux/bitmap.h> +#include <linux/bug.h> #include <linux/export.h> -#endif -#include <linux/err.h> -#include <linux/string.h> #include <linux/idr.h> +#include <linux/slab.h> #include <linux/spinlock.h> -#include <linux/percpu.h> -#include <linux/hardirq.h> - -#define MAX_IDR_SHIFT (sizeof(int) * 8 - 1) -#define MAX_IDR_BIT (1U << MAX_IDR_SHIFT) - -/* Leave the possibility of an incomplete final layer */ -#define MAX_IDR_LEVEL ((MAX_IDR_SHIFT + IDR_BITS - 1) / IDR_BITS) - -/* Number of id_layer structs to leave in free list */ -#define MAX_IDR_FREE (MAX_IDR_LEVEL * 2) - -static struct kmem_cache *idr_layer_cache; -static DEFINE_PER_CPU(struct idr_layer *, idr_preload_head); -static DEFINE_PER_CPU(int, idr_preload_cnt); -static DEFINE_SPINLOCK(simple_ida_lock); - -/* the maximum ID which can be allocated given idr->layers */ -static int idr_max(int layers) -{ - int bits = min_t(int, layers * IDR_BITS, MAX_IDR_SHIFT); - - return (1 << bits) - 1; -} - -/* - * Prefix mask for an idr_layer at @layer. For layer 0, the prefix mask is - * all bits except for the lower IDR_BITS. For layer 1, 2 * IDR_BITS, and - * so on. - */ -static int idr_layer_prefix_mask(int layer) -{ - return ~idr_max(layer + 1); -} - -static struct idr_layer *get_from_free_list(struct idr *idp) -{ - struct idr_layer *p; - unsigned long flags; - - spin_lock_irqsave(&idp->lock, flags); - if ((p = idp->id_free)) { - idp->id_free = p->ary[0]; - idp->id_free_cnt--; - p->ary[0] = NULL; - } - spin_unlock_irqrestore(&idp->lock, flags); - return(p); -} +#include <linux/xarray.h> /** - * idr_layer_alloc - allocate a new idr_layer - * @gfp_mask: allocation mask - * @layer_idr: optional idr to allocate from - * - * If @layer_idr is %NULL, directly allocate one using @gfp_mask or fetch - * one from the per-cpu preload buffer. If @layer_idr is not %NULL, fetch - * an idr_layer from @idr->id_free. - * - * @layer_idr is to maintain backward compatibility with the old alloc - * interface - idr_pre_get() and idr_get_new*() - and will be removed - * together with per-pool preload buffer. + * idr_alloc_u32() - Allocate an ID. + * @idr: IDR handle. + * @ptr: Pointer to be associated with the new ID. + * @nextid: Pointer to an ID. + * @max: The maximum ID to allocate (inclusive). + * @gfp: Memory allocation flags. + * + * Allocates an unused ID in the range specified by @nextid and @max. + * Note that @max is inclusive whereas the @end parameter to idr_alloc() + * is exclusive. The new ID is assigned to @nextid before the pointer + * is inserted into the IDR, so if @nextid points into the object pointed + * to by @ptr, a concurrent lookup will not find an uninitialised ID. + * + * The caller should provide their own locking to ensure that two + * concurrent modifications to the IDR are not possible. Read-only + * accesses to the IDR may be done under the RCU read lock or may + * exclude simultaneous writers. + * + * Return: 0 if an ID was allocated, -ENOMEM if memory allocation failed, + * or -ENOSPC if no free IDs could be found. If an error occurred, + * @nextid is unchanged. */ -static struct idr_layer *idr_layer_alloc(gfp_t gfp_mask, struct idr *layer_idr) -{ - struct idr_layer *new; - - /* this is the old path, bypass to get_from_free_list() */ - if (layer_idr) - return get_from_free_list(layer_idr); - - /* - * Try to allocate directly from kmem_cache. We want to try this - * before preload buffer; otherwise, non-preloading idr_alloc() - * users will end up taking advantage of preloading ones. As the - * following is allowed to fail for preloaded cases, suppress - * warning this time. - */ - new = kmem_cache_zalloc(idr_layer_cache, gfp_mask | __GFP_NOWARN); - if (new) - return new; - - /* - * Try to fetch one from the per-cpu preload buffer if in process - * context. See idr_preload() for details. - */ - if (!in_interrupt()) { - preempt_disable(); - new = __this_cpu_read(idr_preload_head); - if (new) { - __this_cpu_write(idr_preload_head, new->ary[0]); - __this_cpu_dec(idr_preload_cnt); - new->ary[0] = NULL; - } - preempt_enable(); - if (new) - return new; - } - - /* - * Both failed. Try kmem_cache again w/o adding __GFP_NOWARN so - * that memory allocation failure warning is printed as intended. - */ - return kmem_cache_zalloc(idr_layer_cache, gfp_mask); -} - -static void idr_layer_rcu_free(struct rcu_head *head) +int idr_alloc_u32(struct idr *idr, void *ptr, u32 *nextid, + unsigned long max, gfp_t gfp) { - struct idr_layer *layer; + struct radix_tree_iter iter; + void __rcu **slot; + unsigned int base = idr->idr_base; + unsigned int id = *nextid; - layer = container_of(head, struct idr_layer, rcu_head); - kmem_cache_free(idr_layer_cache, layer); -} + if (WARN_ON_ONCE(!(idr->idr_rt.xa_flags & ROOT_IS_IDR))) + idr->idr_rt.xa_flags |= IDR_RT_MARKER; -static inline void free_layer(struct idr *idr, struct idr_layer *p) -{ - if (idr->hint && idr->hint == p) - RCU_INIT_POINTER(idr->hint, NULL); - call_rcu(&p->rcu_head, idr_layer_rcu_free); -} + id = (id < base) ? 0 : id - base; + radix_tree_iter_init(&iter, id); + slot = idr_get_free(&idr->idr_rt, &iter, gfp, max - base); + if (IS_ERR(slot)) + return PTR_ERR(slot); -/* only called when idp->lock is held */ -static void __move_to_free_list(struct idr *idp, struct idr_layer *p) -{ - p->ary[0] = idp->id_free; - idp->id_free = p; - idp->id_free_cnt++; -} + *nextid = iter.index + base; + /* there is a memory barrier inside radix_tree_iter_replace() */ + radix_tree_iter_replace(&idr->idr_rt, &iter, slot, ptr); + radix_tree_iter_tag_clear(&idr->idr_rt, &iter, IDR_FREE); -static void move_to_free_list(struct idr *idp, struct idr_layer *p) -{ - unsigned long flags; - - /* - * Depends on the return element being zeroed. - */ - spin_lock_irqsave(&idp->lock, flags); - __move_to_free_list(idp, p); - spin_unlock_irqrestore(&idp->lock, flags); -} - -static void idr_mark_full(struct idr_layer **pa, int id) -{ - struct idr_layer *p = pa[0]; - int l = 0; - - __set_bit(id & IDR_MASK, p->bitmap); - /* - * If this layer is full mark the bit in the layer above to - * show that this part of the radix tree is full. This may - * complete the layer above and require walking up the radix - * tree. - */ - while (bitmap_full(p->bitmap, IDR_SIZE)) { - if (!(p = pa[++l])) - break; - id = id >> IDR_BITS; - __set_bit((id & IDR_MASK), p->bitmap); - } -} - -int __idr_pre_get(struct idr *idp, gfp_t gfp_mask) -{ - while (idp->id_free_cnt < MAX_IDR_FREE) { - struct idr_layer *new; - new = kmem_cache_zalloc(idr_layer_cache, gfp_mask); - if (new == NULL) - return (0); - move_to_free_list(idp, new); - } - return 1; + return 0; } -EXPORT_SYMBOL(__idr_pre_get); +EXPORT_SYMBOL_GPL(idr_alloc_u32); /** - * sub_alloc - try to allocate an id without growing the tree depth - * @idp: idr handle - * @starting_id: id to start search at - * @pa: idr_layer[MAX_IDR_LEVEL] used as backtrack buffer - * @gfp_mask: allocation mask for idr_layer_alloc() - * @layer_idr: optional idr passed to idr_layer_alloc() - * - * Allocate an id in range [@starting_id, INT_MAX] from @idp without - * growing its depth. Returns - * - * the allocated id >= 0 if successful, - * -EAGAIN if the tree needs to grow for allocation to succeed, - * -ENOSPC if the id space is exhausted, - * -ENOMEM if more idr_layers need to be allocated. + * idr_alloc() - Allocate an ID. + * @idr: IDR handle. + * @ptr: Pointer to be associated with the new ID. + * @start: The minimum ID (inclusive). + * @end: The maximum ID (exclusive). + * @gfp: Memory allocation flags. + * + * Allocates an unused ID in the range specified by @start and @end. If + * @end is <= 0, it is treated as one larger than %INT_MAX. This allows + * callers to use @start + N as @end as long as N is within integer range. + * + * The caller should provide their own locking to ensure that two + * concurrent modifications to the IDR are not possible. Read-only + * accesses to the IDR may be done under the RCU read lock or may + * exclude simultaneous writers. + * + * Return: The newly allocated ID, -ENOMEM if memory allocation failed, + * or -ENOSPC if no free IDs could be found. */ -static int sub_alloc(struct idr *idp, int *starting_id, struct idr_layer **pa, - gfp_t gfp_mask, struct idr *layer_idr) +int idr_alloc(struct idr *idr, void *ptr, int start, int end, gfp_t gfp) { - int n, m, sh; - struct idr_layer *p, *new; - int l, id, oid; + u32 id = start; + int ret; - id = *starting_id; - restart: - p = idp->top; - l = idp->layers; - pa[l--] = NULL; - while (1) { - /* - * We run around this while until we reach the leaf node... - */ - n = (id >> (IDR_BITS*l)) & IDR_MASK; - m = find_next_zero_bit(p->bitmap, IDR_SIZE, n); - if (m == IDR_SIZE) { - /* no space available go back to previous layer. */ - l++; - oid = id; - id = (id | ((1 << (IDR_BITS * l)) - 1)) + 1; - - /* if already at the top layer, we need to grow */ - if (id >= 1 << (idp->layers * IDR_BITS)) { - *starting_id = id; - return -EAGAIN; - } - p = pa[l]; - BUG_ON(!p); + if (WARN_ON_ONCE(start < 0)) + return -EINVAL; - /* If we need to go up one layer, continue the - * loop; otherwise, restart from the top. - */ - sh = IDR_BITS * (l + 1); - if (oid >> sh == id >> sh) - continue; - else - goto restart; - } - if (m != n) { - sh = IDR_BITS*l; - id = ((id >> sh) ^ n ^ m) << sh; - } - if ((id >= MAX_IDR_BIT) || (id < 0)) - return -ENOSPC; - if (l == 0) - break; - /* - * Create the layer below if it is missing. - */ - if (!p->ary[m]) { - new = idr_layer_alloc(gfp_mask, layer_idr); - if (!new) - return -ENOMEM; - new->layer = l-1; - new->prefix = id & idr_layer_prefix_mask(new->layer); - rcu_assign_pointer(p->ary[m], new); - p->count++; - } - pa[l--] = p; - p = p->ary[m]; - } + ret = idr_alloc_u32(idr, ptr, &id, end > 0 ? end - 1 : INT_MAX, gfp); + if (ret) + return ret; - pa[l] = p; return id; } +EXPORT_SYMBOL_GPL(idr_alloc); -static int idr_get_empty_slot(struct idr *idp, int starting_id, - struct idr_layer **pa, gfp_t gfp_mask, - struct idr *layer_idr) -{ - struct idr_layer *p, *new; - int layers, v, id; - unsigned long flags; - - id = starting_id; -build_up: - p = idp->top; - layers = idp->layers; - if (unlikely(!p)) { - if (!(p = idr_layer_alloc(gfp_mask, layer_idr))) - return -ENOMEM; - p->layer = 0; - layers = 1; - } - /* - * Add a new layer to the top of the tree if the requested - * id is larger than the currently allocated space. - */ - while (id > idr_max(layers)) { - layers++; - if (!p->count) { - /* special case: if the tree is currently empty, - * then we grow the tree by moving the top node - * upwards. - */ - p->layer++; - WARN_ON_ONCE(p->prefix); - continue; - } - if (!(new = idr_layer_alloc(gfp_mask, layer_idr))) { - /* - * The allocation failed. If we built part of - * the structure tear it down. - */ - spin_lock_irqsave(&idp->lock, flags); - for (new = p; p && p != idp->top; new = p) { - p = p->ary[0]; - new->ary[0] = NULL; - new->count = 0; - bitmap_clear(new->bitmap, 0, IDR_SIZE); - __move_to_free_list(idp, new); - } - spin_unlock_irqrestore(&idp->lock, flags); - return -ENOMEM; - } - new->ary[0] = p; - new->count = 1; - new->layer = layers-1; - new->prefix = id & idr_layer_prefix_mask(new->layer); - if (bitmap_full(p->bitmap, IDR_SIZE)) - __set_bit(0, new->bitmap); - p = new; - } - rcu_assign_pointer(idp->top, p); - idp->layers = layers; - v = sub_alloc(idp, &id, pa, gfp_mask, layer_idr); - if (v == -EAGAIN) - goto build_up; - return(v); -} - -/* - * @id and @pa are from a successful allocation from idr_get_empty_slot(). - * Install the user pointer @ptr and mark the slot full. +/** + * idr_alloc_cyclic() - Allocate an ID cyclically. + * @idr: IDR handle. + * @ptr: Pointer to be associated with the new ID. + * @start: The minimum ID (inclusive). + * @end: The maximum ID (exclusive). + * @gfp: Memory allocation flags. + * + * Allocates an unused ID in the range specified by @start and @end. If + * @end is <= 0, it is treated as one larger than %INT_MAX. This allows + * callers to use @start + N as @end as long as N is within integer range. + * The search for an unused ID will start at the last ID allocated and will + * wrap around to @start if no free IDs are found before reaching @end. + * + * The caller should provide their own locking to ensure that two + * concurrent modifications to the IDR are not possible. Read-only + * accesses to the IDR may be done under the RCU read lock or may + * exclude simultaneous writers. + * + * Return: The newly allocated ID, -ENOMEM if memory allocation failed, + * or -ENOSPC if no free IDs could be found. */ -static void idr_fill_slot(struct idr *idr, void *ptr, int id, - struct idr_layer **pa) +int idr_alloc_cyclic(struct idr *idr, void *ptr, int start, int end, gfp_t gfp) { - /* update hint used for lookup, cleared from free_layer() */ - rcu_assign_pointer(idr->hint, pa[0]); + u32 id = idr->idr_next; + int err, max = end > 0 ? end - 1 : INT_MAX; - rcu_assign_pointer(pa[0]->ary[id & IDR_MASK], (struct idr_layer *)ptr); - pa[0]->count++; - idr_mark_full(pa, id); -} - -int __idr_get_new_above(struct idr *idp, void *ptr, int starting_id, int *id) -{ - struct idr_layer *pa[MAX_IDR_LEVEL + 1]; - int rv; + if ((int)id < start) + id = start; - rv = idr_get_empty_slot(idp, starting_id, pa, 0, idp); - if (rv < 0) - return rv == -ENOMEM ? -EAGAIN : rv; + err = idr_alloc_u32(idr, ptr, &id, max, gfp); + if ((err == -ENOSPC) && (id > start)) { + id = start; + err = idr_alloc_u32(idr, ptr, &id, max, gfp); + } + if (err) + return err; - idr_fill_slot(idp, ptr, rv, pa); - *id = rv; - return 0; + idr->idr_next = id + 1; + return id; } -EXPORT_SYMBOL(__idr_get_new_above); +EXPORT_SYMBOL(idr_alloc_cyclic); /** - * idr_preload - preload for idr_alloc() - * @gfp_mask: allocation mask to use for preloading + * idr_remove() - Remove an ID from the IDR. + * @idr: IDR handle. + * @id: Pointer ID. * - * Preload per-cpu layer buffer for idr_alloc(). Can only be used from - * process context and each idr_preload() invocation should be matched with - * idr_preload_end(). Note that preemption is disabled while preloaded. + * Removes this ID from the IDR. If the ID was not previously in the IDR, + * this function returns %NULL. * - * The first idr_alloc() in the preloaded section can be treated as if it - * were invoked with @gfp_mask used for preloading. This allows using more - * permissive allocation masks for idrs protected by spinlocks. + * Since this function modifies the IDR, the caller should provide their + * own locking to ensure that concurrent modification of the same IDR is + * not possible. * - * For example, if idr_alloc() below fails, the failure can be treated as - * if idr_alloc() were called with GFP_KERNEL rather than GFP_NOWAIT. - * - * idr_preload(GFP_KERNEL); - * spin_lock(lock); - * - * id = idr_alloc(idr, ptr, start, end, GFP_NOWAIT); - * - * spin_unlock(lock); - * idr_preload_end(); - * if (id < 0) - * error; + * Return: The pointer formerly associated with this ID. */ -void idr_preload(gfp_t gfp_mask) +void *idr_remove(struct idr *idr, unsigned long id) { - /* - * Consuming preload buffer from non-process context breaks preload - * allocation guarantee. Disallow usage from those contexts. - */ - WARN_ON_ONCE(in_interrupt()); - might_sleep_if(gfp_mask & __GFP_WAIT); - - preempt_disable(); - - /* - * idr_alloc() is likely to succeed w/o full idr_layer buffer and - * return value from idr_alloc() needs to be checked for failure - * anyway. Silently give up if allocation fails. The caller can - * treat failures from idr_alloc() as if idr_alloc() were called - * with @gfp_mask which should be enough. - */ - while (__this_cpu_read(idr_preload_cnt) < MAX_IDR_FREE) { - struct idr_layer *new; - - preempt_enable(); - new = kmem_cache_zalloc(idr_layer_cache, gfp_mask); - preempt_disable(); - if (!new) - break; - - /* link the new one to per-cpu preload list */ - new->ary[0] = __this_cpu_read(idr_preload_head); - __this_cpu_write(idr_preload_head, new); - __this_cpu_inc(idr_preload_cnt); - } + return radix_tree_delete_item(&idr->idr_rt, id - idr->idr_base, NULL); } -EXPORT_SYMBOL(idr_preload); +EXPORT_SYMBOL_GPL(idr_remove); /** - * idr_alloc - allocate new idr entry - * @idr: the (initialized) idr - * @ptr: pointer to be associated with the new id - * @start: the minimum id (inclusive) - * @end: the maximum id (exclusive, <= 0 for max) - * @gfp_mask: memory allocation flags + * idr_find() - Return pointer for given ID. + * @idr: IDR handle. + * @id: Pointer ID. * - * Allocate an id in [start, end) and associate it with @ptr. If no ID is - * available in the specified range, returns -ENOSPC. On memory allocation - * failure, returns -ENOMEM. + * Looks up the pointer associated with this ID. A %NULL pointer may + * indicate that @id is not allocated or that the %NULL pointer was + * associated with this ID. * - * Note that @end is treated as max when <= 0. This is to always allow - * using @start + N as @end as long as N is inside integer range. + * This function can be called under rcu_read_lock(), given that the leaf + * pointers lifetimes are correctly managed. * - * The user is responsible for exclusively synchronizing all operations - * which may modify @idr. However, read-only accesses such as idr_find() - * or iteration can be performed under RCU read lock provided the user - * destroys @ptr in RCU-safe way after removal from idr. + * Return: The pointer associated with this ID. */ -int idr_alloc(struct idr *idr, void *ptr, int start, int end, gfp_t gfp_mask) +void *idr_find(const struct idr *idr, unsigned long id) { - int max = end > 0 ? end - 1 : INT_MAX; /* inclusive upper limit */ - struct idr_layer *pa[MAX_IDR_LEVEL + 1]; - int id; - - might_sleep_if(gfp_mask & __GFP_WAIT); - - /* sanity checks */ - if (WARN_ON_ONCE(start < 0)) - return -EINVAL; - if (unlikely(max < start)) - return -ENOSPC; - - /* allocate id */ - id = idr_get_empty_slot(idr, start, pa, gfp_mask, NULL); - if (unlikely(id < 0)) - return id; - if (unlikely(id > max)) - return -ENOSPC; - - idr_fill_slot(idr, ptr, id, pa); - return id; + return radix_tree_lookup(&idr->idr_rt, id - idr->idr_base); } -EXPORT_SYMBOL_GPL(idr_alloc); +EXPORT_SYMBOL_GPL(idr_find); /** - * idr_alloc_cyclic - allocate new idr entry in a cyclical fashion - * @idr: the (initialized) idr - * @ptr: pointer to be associated with the new id - * @start: the minimum id (inclusive) - * @end: the maximum id (exclusive, <= 0 for max) - * @gfp_mask: memory allocation flags + * idr_for_each() - Iterate through all stored pointers. + * @idr: IDR handle. + * @fn: Function to be called for each pointer. + * @data: Data passed to callback function. * - * Essentially the same as idr_alloc, but prefers to allocate progressively - * higher ids if it can. If the "cur" counter wraps, then it will start again - * at the "start" end of the range and allocate one that has already been used. - */ -int idr_alloc_cyclic(struct idr *idr, void *ptr, int start, int end, - gfp_t gfp_mask) -{ - int id; - - id = idr_alloc(idr, ptr, max(start, idr->cur), end, gfp_mask); - if (id == -ENOSPC) - id = idr_alloc(idr, ptr, start, end, gfp_mask); - - if (likely(id >= 0)) - idr->cur = id + 1; - return id; -} -EXPORT_SYMBOL(idr_alloc_cyclic); - -static void idr_remove_warning(int id) -{ - WARN(1, "idr_remove called for id=%d which is not allocated.\n", id); -} - -static void sub_remove(struct idr *idp, int shift, int id) -{ - struct idr_layer *p = idp->top; - struct idr_layer **pa[MAX_IDR_LEVEL + 1]; - struct idr_layer ***paa = &pa[0]; - struct idr_layer *to_free; - int n; - - *paa = NULL; - *++paa = &idp->top; - - while ((shift > 0) && p) { - n = (id >> shift) & IDR_MASK; - __clear_bit(n, p->bitmap); - *++paa = &p->ary[n]; - p = p->ary[n]; - shift -= IDR_BITS; - } - n = id & IDR_MASK; - if (likely(p != NULL && test_bit(n, p->bitmap))) { - __clear_bit(n, p->bitmap); - rcu_assign_pointer(p->ary[n], NULL); - to_free = NULL; - while(*paa && ! --((**paa)->count)){ - if (to_free) - free_layer(idp, to_free); - to_free = **paa; - **paa-- = NULL; - } - if (!*paa) - idp->layers = 0; - if (to_free) - free_layer(idp, to_free); - } else - idr_remove_warning(id); -} - -/** - * idr_remove - remove the given id and free its slot - * @idp: idr handle - * @id: unique key - */ -void idr_remove(struct idr *idp, int id) -{ - struct idr_layer *p; - struct idr_layer *to_free; - - if (id < 0) - return; - - sub_remove(idp, (idp->layers - 1) * IDR_BITS, id); - if (idp->top && idp->top->count == 1 && (idp->layers > 1) && - idp->top->ary[0]) { - /* - * Single child at leftmost slot: we can shrink the tree. - * This level is not needed anymore since when layers are - * inserted, they are inserted at the top of the existing - * tree. - */ - to_free = idp->top; - p = idp->top->ary[0]; - rcu_assign_pointer(idp->top, p); - --idp->layers; - to_free->count = 0; - bitmap_clear(to_free->bitmap, 0, IDR_SIZE); - free_layer(idp, to_free); - } - while (idp->id_free_cnt >= MAX_IDR_FREE) { - p = get_from_free_list(idp); - /* - * Note: we don't call the rcu callback here, since the only - * layers that fall into the freelist are those that have been - * preallocated. - */ - kmem_cache_free(idr_layer_cache, p); - } - return; -} -EXPORT_SYMBOL(idr_remove); - -void __idr_remove_all(struct idr *idp) -{ - int n, id, max; - int bt_mask; - struct idr_layer *p; - struct idr_layer *pa[MAX_IDR_LEVEL + 1]; - struct idr_layer **paa = &pa[0]; - - n = idp->layers * IDR_BITS; - p = idp->top; - rcu_assign_pointer(idp->top, NULL); - max = idr_max(idp->layers); - - id = 0; - while (id >= 0 && id <= max) { - while (n > IDR_BITS && p) { - n -= IDR_BITS; - *paa++ = p; - p = p->ary[(id >> n) & IDR_MASK]; - } - - bt_mask = id; - id += 1 << n; - /* Get the highest bit that the above add changed from 0->1. */ - while (n < fls(id ^ bt_mask)) { - if (p) - free_layer(idp, p); - n += IDR_BITS; - p = *--paa; - } - } - idp->layers = 0; -} -EXPORT_SYMBOL(__idr_remove_all); - -/** - * idr_destroy - release all cached layers within an idr tree - * @idp: idr handle + * The callback function will be called for each entry in @idr, passing + * the ID, the entry and @data. * - * Free all id mappings and all idp_layers. After this function, @idp is - * completely unused and can be freed / recycled. The caller is - * responsible for ensuring that no one else accesses @idp during or after - * idr_destroy(). + * If @fn returns anything other than %0, the iteration stops and that + * value is returned from this function. * - * A typical clean-up sequence for objects stored in an idr tree will use - * idr_for_each() to free all objects, if necessay, then idr_destroy() to - * free up the id mappings and cached idr_layers. + * idr_for_each() can be called concurrently with idr_alloc() and + * idr_remove() if protected by RCU. Newly added entries may not be + * seen and deleted entries may be seen, but adding and removing entries + * will not cause other entries to be skipped, nor spurious ones to be seen. */ -void idr_destroy(struct idr *idp) +int idr_for_each(const struct idr *idr, + int (*fn)(int id, void *p, void *data), void *data) { - __idr_remove_all(idp); + struct radix_tree_iter iter; + void __rcu **slot; + int base = idr->idr_base; - while (idp->id_free_cnt) { - struct idr_layer *p = get_from_free_list(idp); - kmem_cache_free(idr_layer_cache, p); - } -} -EXPORT_SYMBOL(idr_destroy); - -void *idr_find_slowpath(struct idr *idp, int id) -{ - int n; - struct idr_layer *p; + radix_tree_for_each_slot(slot, &idr->idr_rt, &iter, 0) { + int ret; + unsigned long id = iter.index + base; - if (id < 0) - return NULL; - - p = rcu_dereference_raw(idp->top); - if (!p) - return NULL; - n = (p->layer+1) * IDR_BITS; - - if (id > idr_max(p->layer + 1)) - return NULL; - BUG_ON(n == 0); - - while (n > 0 && p) { - n -= IDR_BITS; - BUG_ON(n != p->layer*IDR_BITS); - p = rcu_dereference_raw(p->ary[(id >> n) & IDR_MASK]); + if (WARN_ON_ONCE(id > INT_MAX)) + break; + ret = fn(id, rcu_dereference_raw(*slot), data); + if (ret) + return ret; } - return((void *)p); + + return 0; } -EXPORT_SYMBOL(idr_find_slowpath); +EXPORT_SYMBOL(idr_for_each); /** - * idr_for_each - iterate through all stored pointers - * @idp: idr handle - * @fn: function to be called for each pointer - * @data: data passed back to callback function - * - * Iterate over the pointers registered with the given idr. The - * callback function will be called for each pointer currently - * registered, passing the id, the pointer and the data pointer passed - * to this function. It is not safe to modify the idr tree while in - * the callback, so functions such as idr_get_new and idr_remove are - * not allowed. - * - * We check the return of @fn each time. If it returns anything other - * than %0, we break out and return that value. - * - * The caller must serialize idr_for_each() vs idr_get_new() and idr_remove(). + * idr_get_next_ul() - Find next populated entry. + * @idr: IDR handle. + * @nextid: Pointer to an ID. + * + * Returns the next populated entry in the tree with an ID greater than + * or equal to the value pointed to by @nextid. On exit, @nextid is updated + * to the ID of the found value. To use in a loop, the value pointed to by + * nextid must be incremented by the user. */ -int idr_for_each(struct idr *idp, - int (*fn)(int id, void *p, void *data), void *data) -{ - int n, id, max, error = 0; - struct idr_layer *p; - struct idr_layer *pa[MAX_IDR_LEVEL + 1]; - struct idr_layer **paa = &pa[0]; - - n = idp->layers * IDR_BITS; - p = rcu_dereference_raw(idp->top); - max = idr_max(idp->layers); - - id = 0; - while (id >= 0 && id <= max) { - while (n > 0 && p) { - n -= IDR_BITS; - *paa++ = p; - p = rcu_dereference_raw(p->ary[(id >> n) & IDR_MASK]); - } - - if (p) { - error = fn(id, (void *)p, data); - if (error) - break; - } - - id += 1 << n; - while (n < fls(id)) { - n += IDR_BITS; - p = *--paa; - } +void *idr_get_next_ul(struct idr *idr, unsigned long *nextid) +{ + struct radix_tree_iter iter; + void __rcu **slot; + void *entry = NULL; + unsigned long base = idr->idr_base; + unsigned long id = *nextid; + + id = (id < base) ? 0 : id - base; + radix_tree_for_each_slot(slot, &idr->idr_rt, &iter, id) { + entry = rcu_dereference_raw(*slot); + if (!entry) + continue; + if (!xa_is_internal(entry)) + break; + if (slot != &idr->idr_rt.xa_head && !xa_is_retry(entry)) + break; + slot = radix_tree_iter_retry(&iter); } + if (!slot) + return NULL; - return error; + *nextid = iter.index + base; + return entry; } -EXPORT_SYMBOL(idr_for_each); +EXPORT_SYMBOL(idr_get_next_ul); /** - * idr_get_next - lookup next object of id to given id. - * @idp: idr handle - * @nextidp: pointer to lookup key - * - * Returns pointer to registered object with id, which is next number to - * given id. After being looked up, *@nextidp will be updated for the next - * iteration. - * - * This function can be called under rcu_read_lock(), given that the leaf - * pointers lifetimes are correctly managed. + * idr_get_next() - Find next populated entry. + * @idr: IDR handle. + * @nextid: Pointer to an ID. + * + * Returns the next populated entry in the tree with an ID greater than + * or equal to the value pointed to by @nextid. On exit, @nextid is updated + * to the ID of the found value. To use in a loop, the value pointed to by + * nextid must be incremented by the user. */ -void *idr_get_next(struct idr *idp, int *nextidp) +void *idr_get_next(struct idr *idr, int *nextid) { - struct idr_layer *p, *pa[MAX_IDR_LEVEL + 1]; - struct idr_layer **paa = &pa[0]; - int id = *nextidp; - int n, max; + unsigned long id = *nextid; + void *entry = idr_get_next_ul(idr, &id); - /* find first ent */ - p = rcu_dereference_raw(idp->top); - if (!p) + if (WARN_ON_ONCE(id > INT_MAX)) return NULL; - n = (p->layer + 1) * IDR_BITS; - max = idr_max(p->layer + 1); - - while (id >= 0 && id <= max) { - while (n > 0 && p) { - n -= IDR_BITS; - *paa++ = p; - p = rcu_dereference_raw(p->ary[(id >> n) & IDR_MASK]); - } - - if (p) { - *nextidp = id; - return p; - } - - /* - * Proceed to the next layer at the current level. Unlike - * idr_for_each(), @id isn't guaranteed to be aligned to - * layer boundary at this point and adding 1 << n may - * incorrectly skip IDs. Make sure we jump to the - * beginning of the next layer using round_up(). - */ - id = round_up(id + 1, 1 << n); - while (n < fls(id)) { - n += IDR_BITS; - p = *--paa; - } - } - return NULL; + *nextid = id; + return entry; } EXPORT_SYMBOL(idr_get_next); - /** - * idr_replace - replace pointer for given id - * @idp: idr handle - * @ptr: pointer you want associated with the id - * @id: lookup key - * - * Replace the pointer registered with an id and return the old value. - * A %-ENOENT return indicates that @id was not found. - * A %-EINVAL return indicates that @id was not within valid constraints. - * - * The caller must serialize with writers. + * idr_replace() - replace pointer for given ID. + * @idr: IDR handle. + * @ptr: New pointer to associate with the ID. + * @id: ID to change. + * + * Replace the pointer registered with an ID and return the old value. + * This function can be called under the RCU read lock concurrently with + * idr_alloc() and idr_remove() (as long as the ID being removed is not + * the one being replaced!). + * + * Returns: the old value on success. %-ENOENT indicates that @id was not + * found. %-EINVAL indicates that @ptr was not valid. */ -void *idr_replace(struct idr *idp, void *ptr, int id) +void *idr_replace(struct idr *idr, void *ptr, unsigned long id) { - int n; - struct idr_layer *p, *old_p; - - if (id < 0) - return ERR_PTR(-EINVAL); - - p = idp->top; - if (!p) - return ERR_PTR(-EINVAL); + struct radix_tree_node *node; + void __rcu **slot = NULL; + void *entry; - n = (p->layer+1) * IDR_BITS; + id -= idr->idr_base; - if (id >= (1 << n)) - return ERR_PTR(-EINVAL); - - n -= IDR_BITS; - while ((n > 0) && p) { - p = p->ary[(id >> n) & IDR_MASK]; - n -= IDR_BITS; - } - - n = id & IDR_MASK; - if (unlikely(p == NULL || !test_bit(n, p->bitmap))) + entry = __radix_tree_lookup(&idr->idr_rt, id, &node, &slot); + if (!slot || radix_tree_tag_get(&idr->idr_rt, id, IDR_FREE)) return ERR_PTR(-ENOENT); - old_p = p->ary[n]; - rcu_assign_pointer(p->ary[n], ptr); + __radix_tree_replace(&idr->idr_rt, node, slot, ptr); - return old_p; + return entry; } EXPORT_SYMBOL(idr_replace); -void __init idr_init_cache(void) -{ - idr_layer_cache = kmem_cache_create("idr_layer_cache", - sizeof(struct idr_layer), 0, SLAB_PANIC, NULL); -} - -/** - * idr_init - initialize idr handle - * @idp: idr handle - * - * This function is use to set up the handle (@idp) that you will pass - * to the rest of the functions. - */ -void idr_init(struct idr *idp) -{ - memset(idp, 0, sizeof(struct idr)); - spin_lock_init(&idp->lock); -} -EXPORT_SYMBOL(idr_init); - - /** * DOC: IDA description - * IDA - IDR based ID allocator * - * This is id allocator without id -> pointer translation. Memory - * usage is much lower than full blown idr because each id only - * occupies a bit. ida uses a custom leaf node which contains - * IDA_BITMAP_BITS slots. + * The IDA is an ID allocator which does not provide the ability to + * associate an ID with a pointer. As such, it only needs to store one + * bit per ID, and so is more space efficient than an IDR. To use an IDA, + * define it using DEFINE_IDA() (or embed a &struct ida in a data structure, + * then initialise it using ida_init()). To allocate a new ID, call + * ida_alloc(), ida_alloc_min(), ida_alloc_max() or ida_alloc_range(). + * To free an ID, call ida_free(). * - * 2007-04-25 written by Tejun Heo <htejun@gmail.com> + * ida_destroy() can be used to dispose of an IDA without needing to + * free the individual IDs in it. You can use ida_is_empty() to find + * out whether the IDA has any IDs currently allocated. + * + * The IDA handles its own locking. It is safe to call any of the IDA + * functions without synchronisation in your code. + * + * IDs are currently limited to the range [0-INT_MAX]. If this is an awkward + * limitation, it should be quite straightforward to raise the maximum. */ -static void free_bitmap(struct ida *ida, struct ida_bitmap *bitmap) -{ - unsigned long flags; - - if (!ida->free_bitmap) { - spin_lock_irqsave(&ida->idr.lock, flags); - if (!ida->free_bitmap) { - ida->free_bitmap = bitmap; - bitmap = NULL; - } - spin_unlock_irqrestore(&ida->idr.lock, flags); - } - - kfree(bitmap); -} +/* + * Developer's notes: + * + * The IDA uses the functionality provided by the XArray to store bitmaps in + * each entry. The XA_FREE_MARK is only cleared when all bits in the bitmap + * have been set. + * + * I considered telling the XArray that each slot is an order-10 node + * and indexing by bit number, but the XArray can't allow a single multi-index + * entry in the head, which would significantly increase memory consumption + * for the IDA. So instead we divide the index by the number of bits in the + * leaf bitmap before doing a radix tree lookup. + * + * As an optimisation, if there are only a few low bits set in any given + * leaf, instead of allocating a 128-byte bitmap, we store the bits + * as a value entry. Value entries never have the XA_FREE_MARK cleared + * because we can always convert them into a bitmap entry. + * + * It would be possible to optimise further; once we've run out of a + * single 128-byte bitmap, we currently switch to a 576-byte node, put + * the 128-byte bitmap in the first entry and then start allocating extra + * 128-byte entries. We could instead use the 512 bytes of the node's + * data as a bitmap before moving to that scheme. I do not believe this + * is a worthwhile optimisation; Rasmus Villemoes surveyed the current + * users of the IDA and almost none of them use more than 1024 entries. + * Those that do use more than the 8192 IDs that the 512 bytes would + * provide. + * + * The IDA always uses a lock to alloc/free. If we add a 'test_bit' + * equivalent, it will still need locking. Going to RCU lookup would require + * using RCU to free bitmaps, and that's not trivial without embedding an + * RCU head in the bitmap, which adds a 2-pointer overhead to each 128-byte + * bitmap, which is excessive. + */ /** - * ida_pre_get - reserve resources for ida allocation - * @ida: ida handle - * @gfp_mask: memory allocation flag - * - * This function should be called prior to locking and calling the - * following function. It preallocates enough memory to satisfy the - * worst possible allocation. - * - * If the system is REALLY out of memory this function returns %0, - * otherwise %1. + * ida_alloc_range() - Allocate an unused ID. + * @ida: IDA handle. + * @min: Lowest ID to allocate. + * @max: Highest ID to allocate. + * @gfp: Memory allocation flags. + * + * Allocate an ID between @min and @max, inclusive. The allocated ID will + * not exceed %INT_MAX, even if @max is larger. + * + * Context: Any context. It is safe to call this function without + * locking in your code. + * Return: The allocated ID, or %-ENOMEM if memory could not be allocated, + * or %-ENOSPC if there are no free IDs. */ -int ida_pre_get(struct ida *ida, gfp_t gfp_mask) +int ida_alloc_range(struct ida *ida, unsigned int min, unsigned int max, + gfp_t gfp) { - /* allocate idr_layers */ - if (!__idr_pre_get(&ida->idr, gfp_mask)) - return 0; + XA_STATE(xas, &ida->xa, min / IDA_BITMAP_BITS); + unsigned bit = min % IDA_BITMAP_BITS; + unsigned long flags; + struct ida_bitmap *bitmap, *alloc = NULL; - /* allocate free_bitmap */ - if (!ida->free_bitmap) { - struct ida_bitmap *bitmap; + if ((int)min < 0) + return -ENOSPC; - bitmap = kmalloc(sizeof(struct ida_bitmap), gfp_mask); + if ((int)max < 0) + max = INT_MAX; + +retry: + xas_lock_irqsave(&xas, flags); +next: + bitmap = xas_find_marked(&xas, max / IDA_BITMAP_BITS, XA_FREE_MARK); + if (xas.xa_index > min / IDA_BITMAP_BITS) + bit = 0; + if (xas.xa_index * IDA_BITMAP_BITS + bit > max) + goto nospc; + + if (xa_is_value(bitmap)) { + unsigned long tmp = xa_to_value(bitmap); + + if (bit < BITS_PER_XA_VALUE) { + bit = find_next_zero_bit(&tmp, BITS_PER_XA_VALUE, bit); + if (xas.xa_index * IDA_BITMAP_BITS + bit > max) + goto nospc; + if (bit < BITS_PER_XA_VALUE) { + tmp |= 1UL << bit; + xas_store(&xas, xa_mk_value(tmp)); + goto out; + } + } + bitmap = alloc; if (!bitmap) - return 0; - - free_bitmap(ida, bitmap); + bitmap = kzalloc(sizeof(*bitmap), GFP_NOWAIT); + if (!bitmap) + goto alloc; + bitmap->bitmap[0] = tmp; + xas_store(&xas, bitmap); + if (xas_error(&xas)) { + bitmap->bitmap[0] = 0; + goto out; + } } - return 1; + if (bitmap) { + bit = find_next_zero_bit(bitmap->bitmap, IDA_BITMAP_BITS, bit); + if (xas.xa_index * IDA_BITMAP_BITS + bit > max) + goto nospc; + if (bit == IDA_BITMAP_BITS) + goto next; + + __set_bit(bit, bitmap->bitmap); + if (bitmap_full(bitmap->bitmap, IDA_BITMAP_BITS)) + xas_clear_mark(&xas, XA_FREE_MARK); + } else { + if (bit < BITS_PER_XA_VALUE) { + bitmap = xa_mk_value(1UL << bit); + } else { + bitmap = alloc; + if (!bitmap) + bitmap = kzalloc(sizeof(*bitmap), GFP_NOWAIT); + if (!bitmap) + goto alloc; + __set_bit(bit, bitmap->bitmap); + } + xas_store(&xas, bitmap); + } +out: + xas_unlock_irqrestore(&xas, flags); + if (xas_nomem(&xas, gfp)) { + xas.xa_index = min / IDA_BITMAP_BITS; + bit = min % IDA_BITMAP_BITS; + goto retry; + } + if (bitmap != alloc) + kfree(alloc); + if (xas_error(&xas)) + return xas_error(&xas); + return xas.xa_index * IDA_BITMAP_BITS + bit; +alloc: + xas_unlock_irqrestore(&xas, flags); + alloc = kzalloc(sizeof(*bitmap), gfp); + if (!alloc) + return -ENOMEM; + xas_set(&xas, min / IDA_BITMAP_BITS); + bit = min % IDA_BITMAP_BITS; + goto retry; +nospc: + xas_unlock_irqrestore(&xas, flags); + kfree(alloc); + return -ENOSPC; } -EXPORT_SYMBOL(ida_pre_get); +EXPORT_SYMBOL(ida_alloc_range); /** - * ida_get_new_above - allocate new ID above or equal to a start id - * @ida: ida handle - * @starting_id: id to start search at - * @p_id: pointer to the allocated handle - * - * Allocate new ID above or equal to @starting_id. It should be called - * with any required locks. + * ida_find_first_range - Get the lowest used ID. + * @ida: IDA handle. + * @min: Lowest ID to get. + * @max: Highest ID to get. * - * If memory is required, it will return %-EAGAIN, you should unlock - * and go back to the ida_pre_get() call. If the ida is full, it will - * return %-ENOSPC. + * Get the lowest used ID between @min and @max, inclusive. The returned + * ID will not exceed %INT_MAX, even if @max is larger. * - * @p_id returns a value in the range @starting_id ... %0x7fffffff. + * Context: Any context. Takes and releases the xa_lock. + * Return: The lowest used ID, or errno if no used ID is found. */ -int ida_get_new_above(struct ida *ida, int starting_id, int *p_id) +int ida_find_first_range(struct ida *ida, unsigned int min, unsigned int max) { - struct idr_layer *pa[MAX_IDR_LEVEL + 1]; - struct ida_bitmap *bitmap; + unsigned long index = min / IDA_BITMAP_BITS; + unsigned int offset = min % IDA_BITMAP_BITS; + unsigned long *addr, size, bit; + unsigned long tmp = 0; unsigned long flags; - int idr_id = starting_id / IDA_BITMAP_BITS; - int offset = starting_id % IDA_BITMAP_BITS; - int t, id; - - restart: - /* get vacant slot */ - t = idr_get_empty_slot(&ida->idr, idr_id, pa, 0, &ida->idr); - if (t < 0) - return t == -ENOMEM ? -EAGAIN : t; + void *entry; + int ret; - if (t * IDA_BITMAP_BITS >= MAX_IDR_BIT) - return -ENOSPC; - - if (t != idr_id) - offset = 0; - idr_id = t; + if ((int)min < 0) + return -EINVAL; + if ((int)max < 0) + max = INT_MAX; - /* if bitmap isn't there, create a new one */ - bitmap = (void *)pa[0]->ary[idr_id & IDR_MASK]; - if (!bitmap) { - spin_lock_irqsave(&ida->idr.lock, flags); - bitmap = ida->free_bitmap; - ida->free_bitmap = NULL; - spin_unlock_irqrestore(&ida->idr.lock, flags); + xa_lock_irqsave(&ida->xa, flags); - if (!bitmap) - return -EAGAIN; - - memset(bitmap, 0, sizeof(struct ida_bitmap)); - rcu_assign_pointer(pa[0]->ary[idr_id & IDR_MASK], - (void *)bitmap); - pa[0]->count++; + entry = xa_find(&ida->xa, &index, max / IDA_BITMAP_BITS, XA_PRESENT); + if (!entry) { + ret = -ENOENT; + goto err_unlock; } - /* lookup for empty slot */ - t = find_next_zero_bit(bitmap->bitmap, IDA_BITMAP_BITS, offset); - if (t == IDA_BITMAP_BITS) { - /* no empty slot after offset, continue to the next chunk */ - idr_id++; + if (index > min / IDA_BITMAP_BITS) offset = 0; - goto restart; + if (index * IDA_BITMAP_BITS + offset > max) { + ret = -ENOENT; + goto err_unlock; } - id = idr_id * IDA_BITMAP_BITS + t; - if (id >= MAX_IDR_BIT) - return -ENOSPC; + if (xa_is_value(entry)) { + tmp = xa_to_value(entry); + addr = &tmp; + size = BITS_PER_XA_VALUE; + } else { + addr = ((struct ida_bitmap *)entry)->bitmap; + size = IDA_BITMAP_BITS; + } - __set_bit(t, bitmap->bitmap); - if (++bitmap->nr_busy == IDA_BITMAP_BITS) - idr_mark_full(pa, idr_id); + bit = find_next_bit(addr, size, offset); - *p_id = id; + xa_unlock_irqrestore(&ida->xa, flags); - /* Each leaf node can handle nearly a thousand slots and the - * whole idea of ida is to have small memory foot print. - * Throw away extra resources one by one after each successful - * allocation. - */ - if (ida->idr.id_free_cnt || ida->free_bitmap) { - struct idr_layer *p = get_from_free_list(&ida->idr); - if (p) - kmem_cache_free(idr_layer_cache, p); - } + if (bit == size || + index * IDA_BITMAP_BITS + bit > max) + return -ENOENT; - return 0; + return index * IDA_BITMAP_BITS + bit; + +err_unlock: + xa_unlock_irqrestore(&ida->xa, flags); + return ret; } -EXPORT_SYMBOL(ida_get_new_above); +EXPORT_SYMBOL(ida_find_first_range); /** - * ida_remove - remove the given ID - * @ida: ida handle - * @id: ID to free + * ida_free() - Release an allocated ID. + * @ida: IDA handle. + * @id: Previously allocated ID. + * + * Context: Any context. It is safe to call this function without + * locking in your code. */ -void ida_remove(struct ida *ida, int id) +void ida_free(struct ida *ida, unsigned int id) { - struct idr_layer *p = ida->idr.top; - int shift = (ida->idr.layers - 1) * IDR_BITS; - int idr_id = id / IDA_BITMAP_BITS; - int offset = id % IDA_BITMAP_BITS; - int n; + XA_STATE(xas, &ida->xa, id / IDA_BITMAP_BITS); + unsigned bit = id % IDA_BITMAP_BITS; struct ida_bitmap *bitmap; + unsigned long flags; - /* clear full bits while looking up the leaf idr_layer */ - while ((shift > 0) && p) { - n = (idr_id >> shift) & IDR_MASK; - __clear_bit(n, p->bitmap); - p = p->ary[n]; - shift -= IDR_BITS; - } - - if (p == NULL) - goto err; - - n = idr_id & IDR_MASK; - __clear_bit(n, p->bitmap); - - bitmap = (void *)p->ary[n]; - if (!test_bit(offset, bitmap->bitmap)) - goto err; + if ((int)id < 0) + return; - /* update bitmap and remove it if empty */ - __clear_bit(offset, bitmap->bitmap); - if (--bitmap->nr_busy == 0) { - __set_bit(n, p->bitmap); /* to please idr_remove() */ - idr_remove(&ida->idr, idr_id); - free_bitmap(ida, bitmap); + xas_lock_irqsave(&xas, flags); + bitmap = xas_load(&xas); + + if (xa_is_value(bitmap)) { + unsigned long v = xa_to_value(bitmap); + if (bit >= BITS_PER_XA_VALUE) + goto err; + if (!(v & (1UL << bit))) + goto err; + v &= ~(1UL << bit); + if (!v) + goto delete; + xas_store(&xas, xa_mk_value(v)); + } else { + if (!bitmap || !test_bit(bit, bitmap->bitmap)) + goto err; + __clear_bit(bit, bitmap->bitmap); + xas_set_mark(&xas, XA_FREE_MARK); + if (bitmap_empty(bitmap->bitmap, IDA_BITMAP_BITS)) { + kfree(bitmap); +delete: + xas_store(&xas, NULL); + } } - + xas_unlock_irqrestore(&xas, flags); return; - err: - WARN(1, "ida_remove called for id=%d which is not allocated.\n", id); -} -EXPORT_SYMBOL(ida_remove); - -/** - * ida_destroy - release all cached layers within an ida tree - * @ida: ida handle - */ -void ida_destroy(struct ida *ida) -{ - idr_destroy(&ida->idr); - kfree(ida->free_bitmap); + xas_unlock_irqrestore(&xas, flags); + WARN(1, "ida_free called for id=%d which is not allocated.\n", id); } -EXPORT_SYMBOL(ida_destroy); +EXPORT_SYMBOL(ida_free); /** - * ida_simple_get - get a new id. - * @ida: the (initialized) ida. - * @start: the minimum id (inclusive, < 0x8000000) - * @end: the maximum id (exclusive, < 0x8000000 or 0) - * @gfp_mask: memory allocation flags + * ida_destroy() - Free all IDs. + * @ida: IDA handle. * - * Allocates an id in the range start <= id < end, or returns -ENOSPC. - * On memory allocation failure, returns -ENOMEM. + * Calling this function frees all IDs and releases all resources used + * by an IDA. When this call returns, the IDA is empty and can be reused + * or freed. If the IDA is already empty, there is no need to call this + * function. * - * Use ida_simple_remove() to get rid of an id. + * Context: Any context. It is safe to call this function without + * locking in your code. */ -int ida_simple_get(struct ida *ida, unsigned int start, unsigned int end, - gfp_t gfp_mask) +void ida_destroy(struct ida *ida) { - int ret, id; - unsigned int max; + XA_STATE(xas, &ida->xa, 0); + struct ida_bitmap *bitmap; unsigned long flags; - BUG_ON((int)start < 0); - BUG_ON((int)end < 0); - - if (end == 0) - max = 0x80000000; - else { - BUG_ON(end < start); - max = end - 1; - } - -again: - if (!ida_pre_get(ida, gfp_mask)) - return -ENOMEM; - - spin_lock_irqsave(&simple_ida_lock, flags); - ret = ida_get_new_above(ida, start, &id); - if (!ret) { - if (id > max) { - ida_remove(ida, id); - ret = -ENOSPC; - } else { - ret = id; - } + xas_lock_irqsave(&xas, flags); + xas_for_each(&xas, bitmap, ULONG_MAX) { + if (!xa_is_value(bitmap)) + kfree(bitmap); + xas_store(&xas, NULL); } - spin_unlock_irqrestore(&simple_ida_lock, flags); - - if (unlikely(ret == -EAGAIN)) - goto again; - - return ret; + xas_unlock_irqrestore(&xas, flags); } -EXPORT_SYMBOL(ida_simple_get); +EXPORT_SYMBOL(ida_destroy); -/** - * ida_simple_remove - remove an allocated id. - * @ida: the (initialized) ida. - * @id: the id returned by ida_simple_get. - */ -void ida_simple_remove(struct ida *ida, unsigned int id) +#ifndef __KERNEL__ +extern void xa_dump_index(unsigned long index, unsigned int shift); +#define IDA_CHUNK_SHIFT ilog2(IDA_BITMAP_BITS) + +static void ida_dump_entry(void *entry, unsigned long index) { - unsigned long flags; + unsigned long i; + + if (!entry) + return; - BUG_ON((int)id < 0); - spin_lock_irqsave(&simple_ida_lock, flags); - ida_remove(ida, id); - spin_unlock_irqrestore(&simple_ida_lock, flags); + if (xa_is_node(entry)) { + struct xa_node *node = xa_to_node(entry); + unsigned int shift = node->shift + IDA_CHUNK_SHIFT + + XA_CHUNK_SHIFT; + + xa_dump_index(index * IDA_BITMAP_BITS, shift); + xa_dump_node(node); + for (i = 0; i < XA_CHUNK_SIZE; i++) + ida_dump_entry(node->slots[i], + index | (i << node->shift)); + } else if (xa_is_value(entry)) { + xa_dump_index(index * IDA_BITMAP_BITS, ilog2(BITS_PER_LONG)); + pr_cont("value: data %lx [%px]\n", xa_to_value(entry), entry); + } else { + struct ida_bitmap *bitmap = entry; + + xa_dump_index(index * IDA_BITMAP_BITS, IDA_CHUNK_SHIFT); + pr_cont("bitmap: %p data", bitmap); + for (i = 0; i < IDA_BITMAP_LONGS; i++) + pr_cont(" %lx", bitmap->bitmap[i]); + pr_cont("\n"); + } } -EXPORT_SYMBOL(ida_simple_remove); -/** - * ida_init - initialize ida handle - * @ida: ida handle - * - * This function is use to set up the handle (@ida) that you will pass - * to the rest of the functions. - */ -void ida_init(struct ida *ida) +static void ida_dump(struct ida *ida) { - memset(ida, 0, sizeof(struct ida)); - idr_init(&ida->idr); - + struct xarray *xa = &ida->xa; + pr_debug("ida: %p node %p free %d\n", ida, xa->xa_head, + xa->xa_flags >> ROOT_TAG_SHIFT); + ida_dump_entry(xa->xa_head, 0); } -EXPORT_SYMBOL(ida_init); +#endif |