diff options
| -rw-r--r-- | include/linux/idr.h | 66 | ||||
| -rw-r--r-- | lib/idr.c | 70 | ||||
| -rw-r--r-- | tools/testing/radix-tree/idr-test.c | 7 |
3 files changed, 103 insertions, 40 deletions
diff --git a/include/linux/idr.h b/include/linux/idr.h index 95a82cf2ed02..86b38df6e121 100644 --- a/include/linux/idr.h +++ b/include/linux/idr.h @@ -18,6 +18,7 @@ struct idr { struct radix_tree_root idr_rt; + unsigned int idr_base; unsigned int idr_next; }; @@ -30,13 +31,21 @@ struct idr { /* Set the IDR flag and the IDR_FREE tag */ #define IDR_RT_MARKER ((__force gfp_t)(3 << __GFP_BITS_SHIFT)) -#define IDR_INIT \ -{ \ - .idr_rt = RADIX_TREE_INIT(IDR_RT_MARKER) \ +#define IDR_INIT_BASE(base) { \ + .idr_rt = RADIX_TREE_INIT(IDR_RT_MARKER), \ + .idr_base = (base), \ + .idr_next = 0, \ } #define DEFINE_IDR(name) struct idr name = IDR_INIT /** + * IDR_INIT() - Initialise an IDR. + * + * A freshly-initialised IDR contains no IDs. + */ +#define IDR_INIT IDR_INIT_BASE(0) + +/** * idr_get_cursor - Return the current position of the cyclic allocator * @idr: idr handle * @@ -81,10 +90,12 @@ static inline void idr_set_cursor(struct idr *idr, unsigned int val) void idr_preload(gfp_t gfp_mask); -int idr_alloc(struct idr *, void *, int start, int end, gfp_t); -int __must_check idr_alloc_u32(struct idr *, void *ptr, u32 *nextid, +int idr_alloc(struct idr *, void *ptr, int start, int end, gfp_t); +int __must_check idr_alloc_u32(struct idr *, void *ptr, u32 *id, unsigned long max, gfp_t); -int idr_alloc_cyclic(struct idr *, void *entry, int start, int end, gfp_t); +int idr_alloc_cyclic(struct idr *, void *ptr, int start, int end, gfp_t); +void *idr_remove(struct idr *, unsigned long id); +void *idr_find(const struct idr *, unsigned long id); int idr_for_each(const struct idr *, int (*fn)(int id, void *p, void *data), void *data); void *idr_get_next(struct idr *, int *nextid); @@ -92,15 +103,31 @@ void *idr_get_next_ul(struct idr *, unsigned long *nextid); void *idr_replace(struct idr *, void *, unsigned long id); void idr_destroy(struct idr *); -static inline void *idr_remove(struct idr *idr, unsigned long id) +/** + * idr_init_base() - Initialise an IDR. + * @idr: IDR handle. + * @base: The base value for the IDR. + * + * This variation of idr_init() creates an IDR which will allocate IDs + * starting at %base. + */ +static inline void idr_init_base(struct idr *idr, int base) { - return radix_tree_delete_item(&idr->idr_rt, id, NULL); + INIT_RADIX_TREE(&idr->idr_rt, IDR_RT_MARKER); + idr->idr_base = base; + idr->idr_next = 0; } +/** + * idr_init() - Initialise an IDR. + * @idr: IDR handle. + * + * Initialise a dynamically allocated IDR. To initialise a + * statically allocated IDR, use DEFINE_IDR(). + */ static inline void idr_init(struct idr *idr) { - INIT_RADIX_TREE(&idr->idr_rt, IDR_RT_MARKER); - idr->idr_next = 0; + idr_init_base(idr, 0); } static inline bool idr_is_empty(const struct idr *idr) @@ -121,25 +148,6 @@ static inline void idr_preload_end(void) } /** - * idr_find() - Return pointer for given ID. - * @idr: IDR handle. - * @id: Pointer ID. - * - * 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. - * - * This function can be called under rcu_read_lock(), given that the leaf - * pointers lifetimes are correctly managed. - * - * Return: The pointer associated with this ID. - */ -static inline void *idr_find(const struct idr *idr, unsigned long id) -{ - return radix_tree_lookup(&idr->idr_rt, id); -} - -/** * idr_for_each_entry() - Iterate over an IDR's elements of a given type. * @idr: IDR handle. * @entry: The type * to use as cursor diff --git a/lib/idr.c b/lib/idr.c index b47055efceb0..c98d77fcf393 100644 --- a/lib/idr.c +++ b/lib/idr.c @@ -36,18 +36,21 @@ int idr_alloc_u32(struct idr *idr, void *ptr, u32 *nextid, { struct radix_tree_iter iter; void __rcu **slot; + int base = idr->idr_base; + int id = *nextid; if (WARN_ON_ONCE(radix_tree_is_internal_node(ptr))) return -EINVAL; if (WARN_ON_ONCE(!(idr->idr_rt.gfp_mask & ROOT_IS_IDR))) idr->idr_rt.gfp_mask |= IDR_RT_MARKER; - radix_tree_iter_init(&iter, *nextid); - slot = idr_get_free(&idr->idr_rt, &iter, gfp, max); + 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); - *nextid = iter.index; + *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); @@ -136,6 +139,46 @@ int idr_alloc_cyclic(struct idr *idr, void *ptr, int start, int end, gfp_t gfp) EXPORT_SYMBOL(idr_alloc_cyclic); /** + * idr_remove() - Remove an ID from the IDR. + * @idr: IDR handle. + * @id: Pointer ID. + * + * Removes this ID from the IDR. If the ID was not previously in the IDR, + * this function returns %NULL. + * + * 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. + * + * Return: The pointer formerly associated with this ID. + */ +void *idr_remove(struct idr *idr, unsigned long id) +{ + return radix_tree_delete_item(&idr->idr_rt, id - idr->idr_base, NULL); +} +EXPORT_SYMBOL_GPL(idr_remove); + +/** + * idr_find() - Return pointer for given ID. + * @idr: IDR handle. + * @id: Pointer ID. + * + * 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. + * + * This function can be called under rcu_read_lock(), given that the leaf + * pointers lifetimes are correctly managed. + * + * Return: The pointer associated with this ID. + */ +void *idr_find(const struct idr *idr, unsigned long id) +{ + return radix_tree_lookup(&idr->idr_rt, id - idr->idr_base); +} +EXPORT_SYMBOL_GPL(idr_find); + +/** * idr_for_each() - Iterate through all stored pointers. * @idr: IDR handle. * @fn: Function to be called for each pointer. @@ -157,13 +200,14 @@ int idr_for_each(const struct idr *idr, { struct radix_tree_iter iter; void __rcu **slot; + int base = idr->idr_base; radix_tree_for_each_slot(slot, &idr->idr_rt, &iter, 0) { int ret; if (WARN_ON_ONCE(iter.index > INT_MAX)) break; - ret = fn(iter.index, rcu_dereference_raw(*slot), data); + ret = fn(iter.index + base, rcu_dereference_raw(*slot), data); if (ret) return ret; } @@ -186,15 +230,19 @@ void *idr_get_next(struct idr *idr, int *nextid) { struct radix_tree_iter iter; void __rcu **slot; + int base = idr->idr_base; + int id = *nextid; - slot = radix_tree_iter_find(&idr->idr_rt, &iter, *nextid); + id = (id < base) ? 0 : id - base; + slot = radix_tree_iter_find(&idr->idr_rt, &iter, id); if (!slot) return NULL; + id = iter.index + base; - if (WARN_ON_ONCE(iter.index > INT_MAX)) + if (WARN_ON_ONCE(id > INT_MAX)) return NULL; - *nextid = iter.index; + *nextid = id; return rcu_dereference_raw(*slot); } EXPORT_SYMBOL(idr_get_next); @@ -213,12 +261,15 @@ void *idr_get_next_ul(struct idr *idr, unsigned long *nextid) { struct radix_tree_iter iter; void __rcu **slot; + unsigned long base = idr->idr_base; + unsigned long id = *nextid; - slot = radix_tree_iter_find(&idr->idr_rt, &iter, *nextid); + id = (id < base) ? 0 : id - base; + slot = radix_tree_iter_find(&idr->idr_rt, &iter, id); if (!slot) return NULL; - *nextid = iter.index; + *nextid = iter.index + base; return rcu_dereference_raw(*slot); } EXPORT_SYMBOL(idr_get_next_ul); @@ -245,6 +296,7 @@ void *idr_replace(struct idr *idr, void *ptr, unsigned long id) if (WARN_ON_ONCE(radix_tree_is_internal_node(ptr))) return ERR_PTR(-EINVAL); + id -= idr->idr_base; entry = __radix_tree_lookup(&idr->idr_rt, id, &node, &slot); if (!slot || radix_tree_tag_get(&idr->idr_rt, id, IDR_FREE)) diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr-test.c index 36437ade429c..44ef9eba5a7a 100644 --- a/tools/testing/radix-tree/idr-test.c +++ b/tools/testing/radix-tree/idr-test.c @@ -153,11 +153,12 @@ void idr_nowait_test(void) idr_destroy(&idr); } -void idr_get_next_test(void) +void idr_get_next_test(int base) { unsigned long i; int nextid; DEFINE_IDR(idr); + idr_init_base(&idr, base); int indices[] = {4, 7, 9, 15, 65, 128, 1000, 99999, 0}; @@ -244,7 +245,9 @@ void idr_checks(void) idr_alloc_test(); idr_null_test(); idr_nowait_test(); - idr_get_next_test(); + idr_get_next_test(0); + idr_get_next_test(1); + idr_get_next_test(4); } /* |