From 051803c0d01f4d8a197ecc08bfeffdff00d86c62 Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Fri, 3 Nov 2017 23:06:32 -0400 Subject: radix tree test suite: Remove ARRAY_SIZE This is now defined in tools/include/linux/kernel.h, so our definition generates a warning. Signed-off-by: Matthew Wilcox --- tools/testing/radix-tree/linux/kernel.h | 2 -- 1 file changed, 2 deletions(-) (limited to 'tools') diff --git a/tools/testing/radix-tree/linux/kernel.h b/tools/testing/radix-tree/linux/kernel.h index c3bc3f364f68..426f32f28547 100644 --- a/tools/testing/radix-tree/linux/kernel.h +++ b/tools/testing/radix-tree/linux/kernel.h @@ -17,6 +17,4 @@ #define pr_debug printk #define pr_cont printk -#define ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[0])) - #endif /* _KERNEL_H */ -- cgit v1.2.3-70-g09d2 From 490645d027c5925b30c88b9c7a663850a641d15d Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Thu, 9 Nov 2017 20:15:14 -0500 Subject: idr test suite: Fix ida_test_random() The test was checking the wrong errno; ida_get_new_above() returns EAGAIN, not ENOMEM on memory allocation failure. Double the number of threads to increase the chance that we actually exercise this path during the test suite (it was a bit sporadic before). Signed-off-by: Matthew Wilcox --- tools/testing/radix-tree/idr-test.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'tools') diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr-test.c index 30cd0b296f1a..193450b29bf0 100644 --- a/tools/testing/radix-tree/idr-test.c +++ b/tools/testing/radix-tree/idr-test.c @@ -380,7 +380,7 @@ void ida_check_random(void) do { ida_pre_get(&ida, GFP_KERNEL); err = ida_get_new_above(&ida, bit, &id); - } while (err == -ENOMEM); + } while (err == -EAGAIN); assert(!err); assert(id == bit); } @@ -489,7 +489,7 @@ static void *ida_random_fn(void *arg) void ida_thread_tests(void) { - pthread_t threads[10]; + pthread_t threads[20]; int i; for (i = 0; i < ARRAY_SIZE(threads); i++) -- cgit v1.2.3-70-g09d2 From 6e6d301490936789ff57daaaaf63f44d928a4028 Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Tue, 28 Nov 2017 14:27:14 -0500 Subject: IDR test suite: Check handling negative end correctly One of the charming quirks of the idr_alloc() interface is that you can pass a negative end and it will be interpreted as "maximum". Ensure we don't break that. Signed-off-by: Matthew Wilcox --- tools/testing/radix-tree/idr-test.c | 1 + 1 file changed, 1 insertion(+) (limited to 'tools') diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr-test.c index 193450b29bf0..892ef8855b02 100644 --- a/tools/testing/radix-tree/idr-test.c +++ b/tools/testing/radix-tree/idr-test.c @@ -207,6 +207,7 @@ void idr_checks(void) assert(idr_alloc(&idr, item, i, i + 10, GFP_KERNEL) == i); } assert(idr_alloc(&idr, DUMMY_PTR, i - 2, i, GFP_KERNEL) == -ENOSPC); + assert(idr_alloc(&idr, DUMMY_PTR, i - 2, i + 10, GFP_KERNEL) == -ENOSPC); idr_for_each(&idr, item_idr_free, &idr); idr_destroy(&idr); -- cgit v1.2.3-70-g09d2 From 460488c58ca8b9167463ac22ec9a2e33db351962 Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Tue, 28 Nov 2017 15:16:24 -0500 Subject: idr: Remove idr_alloc_ext It has no more users, so remove it. Move idr_alloc() back into idr.c, move the guts of idr_alloc_cmn() into idr_alloc_u32(), remove the wrappers around idr_get_free_cmn() and rename it to idr_get_free(). While there is now no interface to allocate IDs larger than a u32, the IDR internals remain ready to handle a larger ID should a need arise. These changes make it possible to provide the guarantee that, if the nextid pointer points into the object, the object's ID will be initialised before a concurrent lookup can find the object. Signed-off-by: Matthew Wilcox --- include/linux/idr.h | 51 +------------- include/linux/radix-tree.h | 17 +---- lib/idr.c | 128 +++++++++++++++++++++++------------- lib/radix-tree.c | 3 +- tools/testing/radix-tree/idr-test.c | 17 +++++ 5 files changed, 105 insertions(+), 111 deletions(-) (limited to 'tools') diff --git a/include/linux/idr.h b/include/linux/idr.h index 561a4cbabca6..fa2a04b984df 100644 --- a/include/linux/idr.h +++ b/include/linux/idr.h @@ -15,7 +15,6 @@ #include #include #include -#include struct idr { struct radix_tree_root idr_rt; @@ -82,55 +81,7 @@ static inline void idr_set_cursor(struct idr *idr, unsigned int val) void idr_preload(gfp_t gfp_mask); -int idr_alloc_cmn(struct idr *idr, void *ptr, unsigned long *index, - unsigned long start, unsigned long end, gfp_t gfp, - bool ext); - -/** - * 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 [start, end). Returns -ENOSPC - * if there are no unused IDs in that range. - * - * 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. - * - * Simultaneous modifications to the @idr are not allowed and should be - * prevented by the user, usually with a lock. idr_alloc() may be called - * concurrently with read-only accesses to the @idr, such as idr_find() and - * idr_for_each_entry(). - */ -static inline int idr_alloc(struct idr *idr, void *ptr, - int start, int end, gfp_t gfp) -{ - unsigned long id; - int ret; - - if (WARN_ON_ONCE(start < 0)) - return -EINVAL; - - ret = idr_alloc_cmn(idr, ptr, &id, start, end, gfp, false); - - if (ret) - return ret; - - return id; -} - -static inline int idr_alloc_ext(struct idr *idr, void *ptr, - unsigned long *index, - unsigned long start, - unsigned long end, - gfp_t gfp) -{ - return idr_alloc_cmn(idr, ptr, index, start, end, gfp, true); -} - +int idr_alloc(struct idr *, void *, int start, int end, gfp_t); int __must_check idr_alloc_u32(struct idr *, void *ptr, u32 *nextid, unsigned long max, gfp_t); int idr_alloc_cyclic(struct idr *, void *entry, int start, int end, gfp_t); diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h index 23a9c89c7ad9..fc55ff31eca7 100644 --- a/include/linux/radix-tree.h +++ b/include/linux/radix-tree.h @@ -356,24 +356,9 @@ int radix_tree_split(struct radix_tree_root *, unsigned long index, int radix_tree_join(struct radix_tree_root *, unsigned long index, unsigned new_order, void *); -void __rcu **idr_get_free_cmn(struct radix_tree_root *root, +void __rcu **idr_get_free(struct radix_tree_root *root, struct radix_tree_iter *iter, gfp_t gfp, unsigned long max); -static inline void __rcu **idr_get_free(struct radix_tree_root *root, - struct radix_tree_iter *iter, - gfp_t gfp, - int end) -{ - return idr_get_free_cmn(root, iter, gfp, end > 0 ? end - 1 : INT_MAX); -} - -static inline void __rcu **idr_get_free_ext(struct radix_tree_root *root, - struct radix_tree_iter *iter, - gfp_t gfp, - unsigned long end) -{ - return idr_get_free_cmn(root, iter, gfp, end - 1); -} enum { RADIX_TREE_ITER_TAG_MASK = 0x0f, /* tag index in lower nybble */ diff --git a/lib/idr.c b/lib/idr.c index 6d4ec2c2982b..c3f16307b908 100644 --- a/lib/idr.c +++ b/lib/idr.c @@ -1,4 +1,5 @@ #include +#include #include #include #include @@ -17,7 +18,9 @@ static DEFINE_SPINLOCK(simple_ida_lock); * * 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. + * 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 @@ -30,67 +33,104 @@ static DEFINE_SPINLOCK(simple_ida_lock); */ int idr_alloc_u32(struct idr *idr, void *ptr, u32 *nextid, unsigned long max, gfp_t gfp) -{ - unsigned long tmp = *nextid; - int ret = idr_alloc_ext(idr, ptr, &tmp, tmp, max + 1, gfp); - *nextid = tmp; - return ret; -} -EXPORT_SYMBOL_GPL(idr_alloc_u32); - -int idr_alloc_cmn(struct idr *idr, void *ptr, unsigned long *index, - unsigned long start, unsigned long end, gfp_t gfp, - bool ext) { struct radix_tree_iter iter; void __rcu **slot; 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, start); - if (ext) - slot = idr_get_free_ext(&idr->idr_rt, &iter, gfp, end); - else - slot = idr_get_free(&idr->idr_rt, &iter, gfp, end); + radix_tree_iter_init(&iter, *nextid); + slot = idr_get_free(&idr->idr_rt, &iter, gfp, max); if (IS_ERR(slot)) return PTR_ERR(slot); + *nextid = iter.index; + /* 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); - if (index) - *index = iter.index; return 0; } -EXPORT_SYMBOL_GPL(idr_alloc_cmn); +EXPORT_SYMBOL_GPL(idr_alloc_u32); /** - * idr_alloc_cyclic - allocate new idr entry in a cyclical fashion - * @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 ID larger than the last ID allocated if one is available. - * If not, it will attempt to allocate the smallest ID that is larger or - * equal to @start. + * 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. */ -int idr_alloc_cyclic(struct idr *idr, void *ptr, int start, int end, gfp_t gfp) +int idr_alloc(struct idr *idr, void *ptr, int start, int end, gfp_t gfp) { - int id, curr = idr->idr_next; + u32 id = start; + int ret; + + if (WARN_ON_ONCE(start < 0)) + return -EINVAL; - if (curr < start) - curr = start; + ret = idr_alloc_u32(idr, ptr, &id, end > 0 ? end - 1 : INT_MAX, gfp); + if (ret) + return ret; - id = idr_alloc(idr, ptr, curr, end, gfp); - if ((id == -ENOSPC) && (curr > start)) - id = idr_alloc(idr, ptr, start, curr, gfp); + return id; +} +EXPORT_SYMBOL_GPL(idr_alloc); - if (id >= 0) - idr->idr_next = id + 1U; +/** + * 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 @nextid 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. + */ +int idr_alloc_cyclic(struct idr *idr, void *ptr, int start, int end, gfp_t gfp) +{ + u32 id = idr->idr_next; + int err, max = end > 0 ? end - 1 : INT_MAX; + if ((int)id < start) + id = start; + + 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->idr_next = id + 1; return id; } EXPORT_SYMBOL(idr_alloc_cyclic); @@ -167,10 +207,10 @@ void *idr_get_next_ext(struct idr *idr, unsigned long *nextid) EXPORT_SYMBOL(idr_get_next_ext); /** - * idr_replace - replace pointer for given id - * @idr: idr handle - * @ptr: New pointer to associate with the ID - * @id: Lookup key + * 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 @@ -257,7 +297,7 @@ EXPORT_SYMBOL(idr_replace); * bitmap, which is excessive. */ -#define IDA_MAX (0x80000000U / IDA_BITMAP_BITS) +#define IDA_MAX (0x80000000U / IDA_BITMAP_BITS - 1) /** * ida_get_new_above - allocate new ID above or equal to a start id diff --git a/lib/radix-tree.c b/lib/radix-tree.c index c8d55565fafa..0a7ae3288a24 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c @@ -24,6 +24,7 @@ #include #include +#include #include #include #include @@ -2135,7 +2136,7 @@ int ida_pre_get(struct ida *ida, gfp_t gfp) } EXPORT_SYMBOL(ida_pre_get); -void __rcu **idr_get_free_cmn(struct radix_tree_root *root, +void __rcu **idr_get_free(struct radix_tree_root *root, struct radix_tree_iter *iter, gfp_t gfp, unsigned long max) { diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr-test.c index 892ef8855b02..36437ade429c 100644 --- a/tools/testing/radix-tree/idr-test.c +++ b/tools/testing/radix-tree/idr-test.c @@ -215,6 +215,23 @@ void idr_checks(void) assert(idr_is_empty(&idr)); + idr_set_cursor(&idr, INT_MAX - 3UL); + for (i = INT_MAX - 3UL; i < INT_MAX + 3UL; i++) { + struct item *item; + unsigned int id; + if (i <= INT_MAX) + item = item_create(i, 0); + else + item = item_create(i - INT_MAX - 1, 0); + + id = idr_alloc_cyclic(&idr, item, 0, 0, GFP_KERNEL); + assert(id == item->index); + } + + idr_for_each(&idr, item_idr_free, &idr); + idr_destroy(&idr); + assert(idr_is_empty(&idr)); + for (i = 1; i < 10000; i++) { struct item *item = item_create(i, 0); assert(idr_alloc(&idr, item, 1, 20000, GFP_KERNEL) == i); -- cgit v1.2.3-70-g09d2 From 6ce711f2750031d12cec91384ac5cfa0a485b60a Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Thu, 30 Nov 2017 13:45:11 -0500 Subject: idr: Make 1-based IDRs more efficient About 20% of the IDR users in the kernel want the allocated IDs to start at 1. The implementation currently searches all the way down the left hand side of the tree, finds no free ID other than ID 0, walks all the way back up, and then all the way down again. This patch 'rebases' the ID so we fill the entire radix tree, rather than leave a gap at 0. Chris Wilson says: "I did the quick hack of allocating index 0 of the idr and that eradicated idr_get_free() from being at the top of the profiles for the many-object stress tests. This improvement will be much appreciated." Signed-off-by: Matthew Wilcox --- include/linux/idr.h | 66 +++++++++++++++++++--------------- lib/idr.c | 70 ++++++++++++++++++++++++++++++++----- tools/testing/radix-tree/idr-test.c | 7 ++-- 3 files changed, 103 insertions(+), 40 deletions(-) (limited to 'tools') 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,12 +31,20 @@ 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) @@ -120,25 +147,6 @@ static inline void idr_preload_end(void) preempt_enable(); } -/** - * 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. 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); @@ -135,6 +138,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. @@ -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); } /* -- cgit v1.2.3-70-g09d2