From 76f070b4135563165c523ab560056b7a9353e2f2 Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Sat, 18 Aug 2018 07:05:50 -0400 Subject: radix-tree: Fix UBSAN warning get_slot_offset() can be called with a NULL 'parent' argument. In this case, the calculated value will not be used, but calculating it is undefined. Rather than fixing the caller (__radix_tree_delete) to not call get_slot_offset(), make get_slot_offset() robust against being called with a NULL parent. Signed-off-by: Matthew Wilcox --- lib/radix-tree.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/radix-tree.c b/lib/radix-tree.c index a9e41aed6de4..cc6096b97afb 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c @@ -120,7 +120,7 @@ bool is_sibling_entry(const struct radix_tree_node *parent, void *node) static inline unsigned long get_slot_offset(const struct radix_tree_node *parent, void __rcu **slot) { - return slot - parent->slots; + return parent ? slot - parent->slots : 0; } static unsigned int radix_tree_descend(const struct radix_tree_node *parent, -- cgit v1.2.3 From 50d97d50715a8664f6bddc18211279cd74b8c3bf Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Thu, 21 Jun 2018 15:36:45 -0400 Subject: ida: Lock the IDA in ida_destroy The user has no need to handle locking between ida_simple_get() and ida_simple_remove(). They shouldn't be forced to think about whether ida_destroy() might be called at the same time as any of their other IDA manipulation calls. Improve the documnetation while I'm in here. Signed-off-by: Matthew Wilcox --- lib/idr.c | 17 +++++++++++------ 1 file changed, 11 insertions(+), 6 deletions(-) (limited to 'lib') diff --git a/lib/idr.c b/lib/idr.c index ed9c169c12bd..352c6160e2e0 100644 --- a/lib/idr.c +++ b/lib/idr.c @@ -523,25 +523,30 @@ void ida_remove(struct ida *ida, int id) EXPORT_SYMBOL(ida_remove); /** - * ida_destroy - Free the contents of an ida - * @ida: ida handle + * ida_destroy() - Free all IDs. + * @ida: IDA handle. + * + * 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. * - * Calling this function releases all resources associated with an IDA. When - * this call returns, the IDA is empty and can be reused or freed. The caller - * should not allow ida_remove() or ida_get_new_above() to be called at the - * same time. + * Context: Any context. */ void ida_destroy(struct ida *ida) { + unsigned long flags; struct radix_tree_iter iter; void __rcu **slot; + xa_lock_irqsave(&ida->ida_rt, flags); radix_tree_for_each_slot(slot, &ida->ida_rt, &iter, 0) { struct ida_bitmap *bitmap = rcu_dereference_raw(*slot); if (!radix_tree_exception(bitmap)) kfree(bitmap); radix_tree_iter_delete(&ida->ida_rt, &iter, slot); } + xa_unlock_irqrestore(&ida->ida_rt, flags); } EXPORT_SYMBOL(ida_destroy); -- cgit v1.2.3 From 5ade60dda43c8906d4554374226c2eb11cc2ffba Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Tue, 20 Mar 2018 17:07:11 -0400 Subject: ida: Add new API Add ida_alloc(), ida_alloc_min(), ida_alloc_max(), ida_alloc_range() and ida_free(). The ida_alloc_max() and ida_alloc_range() functions differ from ida_simple_get() in that they take an inclusive 'max' parameter instead of an exclusive 'end' parameter. Callers are about evenly split whether they'd like inclusive or exclusive parameters and 'max' is easier to document than 'end'. Change the IDA allocation to first attempt to allocate a bit using existing memory, and only allocate memory afterwards. Also change the behaviour of 'min' > INT_MAX from being a BUG() to returning -ENOSPC. Leave compatibility wrappers in place for ida_simple_get() and ida_simple_remove() to avoid changing all callers. Signed-off-by: Matthew Wilcox --- include/linux/idr.h | 59 +++++++++++++++++++++++++++++++++++++++++--- lib/idr.c | 70 ++++++++++++++++++++++++----------------------------- 2 files changed, 87 insertions(+), 42 deletions(-) (limited to 'lib') diff --git a/include/linux/idr.h b/include/linux/idr.h index e856f4e0ab35..cd339da0b1aa 100644 --- a/include/linux/idr.h +++ b/include/linux/idr.h @@ -230,15 +230,68 @@ int ida_get_new_above(struct ida *ida, int starting_id, int *p_id); void ida_remove(struct ida *ida, int id); void ida_destroy(struct ida *ida); -int ida_simple_get(struct ida *ida, unsigned int start, unsigned int end, - gfp_t gfp_mask); -void ida_simple_remove(struct ida *ida, unsigned int id); +int ida_alloc_range(struct ida *, unsigned int min, unsigned int max, gfp_t); +void ida_free(struct ida *, unsigned int id); + +/** + * ida_alloc() - Allocate an unused ID. + * @ida: IDA handle. + * @gfp: Memory allocation flags. + * + * Allocate an ID between 0 and %INT_MAX, inclusive. + * + * Context: Any context. + * Return: The allocated ID, or %-ENOMEM if memory could not be allocated, + * or %-ENOSPC if there are no free IDs. + */ +static inline int ida_alloc(struct ida *ida, gfp_t gfp) +{ + return ida_alloc_range(ida, 0, ~0, gfp); +} + +/** + * ida_alloc_min() - Allocate an unused ID. + * @ida: IDA handle. + * @min: Lowest ID to allocate. + * @gfp: Memory allocation flags. + * + * Allocate an ID between @min and %INT_MAX, inclusive. + * + * Context: Any context. + * Return: The allocated ID, or %-ENOMEM if memory could not be allocated, + * or %-ENOSPC if there are no free IDs. + */ +static inline int ida_alloc_min(struct ida *ida, unsigned int min, gfp_t gfp) +{ + return ida_alloc_range(ida, min, ~0, gfp); +} + +/** + * ida_alloc_max() - Allocate an unused ID. + * @ida: IDA handle. + * @max: Highest ID to allocate. + * @gfp: Memory allocation flags. + * + * Allocate an ID between 0 and @max, inclusive. + * + * Context: Any context. + * Return: The allocated ID, or %-ENOMEM if memory could not be allocated, + * or %-ENOSPC if there are no free IDs. + */ +static inline int ida_alloc_max(struct ida *ida, unsigned int max, gfp_t gfp) +{ + return ida_alloc_range(ida, 0, max, gfp); +} static inline void ida_init(struct ida *ida) { INIT_RADIX_TREE(&ida->ida_rt, IDR_RT_MARKER | GFP_NOWAIT); } +#define ida_simple_get(ida, start, end, gfp) \ + ida_alloc_range(ida, start, (end) - 1, gfp) +#define ida_simple_remove(ida, id) ida_free(ida, id) + /** * ida_get_new - allocate new ID * @ida: idr handle diff --git a/lib/idr.c b/lib/idr.c index 352c6160e2e0..760fce92f1fb 100644 --- a/lib/idr.c +++ b/lib/idr.c @@ -317,7 +317,8 @@ EXPORT_SYMBOL(idr_replace); * 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_simple_get(). To free an ID, call ida_simple_remove(). + * ida_alloc(), ida_alloc_min(), ida_alloc_max() or ida_alloc_range(). + * To free an ID, call ida_free(). * * If you have more complex locking requirements, use a loop around * ida_pre_get() and ida_get_new() to allocate a new ID. Then use @@ -378,7 +379,7 @@ EXPORT_SYMBOL(idr_replace); * Allocate new ID above or equal to @start. It should be called * with any required locks to ensure that concurrent calls to * ida_get_new_above() / ida_get_new() / ida_remove() are not allowed. - * Consider using ida_simple_get() if you do not have complex locking + * Consider using ida_alloc_range() if you do not have complex locking * requirements. * * If memory is required, it will return %-EAGAIN, you should unlock @@ -551,43 +552,34 @@ void ida_destroy(struct ida *ida) EXPORT_SYMBOL(ida_destroy); /** - * 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 - * - * Allocates an id in the range start <= id < end, or returns -ENOSPC. - * On memory allocation failure, returns -ENOMEM. + * ida_alloc_range() - Allocate an unused ID. + * @ida: IDA handle. + * @min: Lowest ID to allocate. + * @max: Highest ID to allocate. + * @gfp: Memory allocation flags. * - * Compared to ida_get_new_above() this function does its own locking, and - * should be used unless there are special requirements. + * Allocate an ID between @min and @max, inclusive. The allocated ID will + * not exceed %INT_MAX, even if @max is larger. * - * Use ida_simple_remove() to get rid of an id. + * Context: Any context. + * Return: The allocated ID, or %-ENOMEM if memory could not be allocated, + * or %-ENOSPC if there are no free IDs. */ -int ida_simple_get(struct ida *ida, unsigned int start, unsigned int end, - gfp_t gfp_mask) +int ida_alloc_range(struct ida *ida, unsigned int min, unsigned int max, + gfp_t gfp) { int ret, id; - unsigned int max; unsigned long flags; - BUG_ON((int)start < 0); - BUG_ON((int)end < 0); + if ((int)min < 0) + return -ENOSPC; - if (end == 0) - max = 0x80000000; - else { - BUG_ON(end < start); - max = end - 1; - } + if ((int)max < 0) + max = INT_MAX; again: - if (!ida_pre_get(ida, gfp_mask)) - return -ENOMEM; - xa_lock_irqsave(&ida->ida_rt, flags); - ret = ida_get_new_above(ida, start, &id); + ret = ida_get_new_above(ida, min, &id); if (!ret) { if (id > max) { ida_remove(ida, id); @@ -598,24 +590,24 @@ again: } xa_unlock_irqrestore(&ida->ida_rt, flags); - if (unlikely(ret == -EAGAIN)) + if (unlikely(ret == -EAGAIN)) { + if (!ida_pre_get(ida, gfp)) + return -ENOMEM; goto again; + } return ret; } -EXPORT_SYMBOL(ida_simple_get); +EXPORT_SYMBOL(ida_alloc_range); /** - * ida_simple_remove - remove an allocated id. - * @ida: the (initialized) ida. - * @id: the id returned by ida_simple_get. - * - * Use to release an id allocated with ida_simple_get(). + * ida_free() - Release an allocated ID. + * @ida: IDA handle. + * @id: Previously allocated ID. * - * Compared to ida_remove() this function does its own locking, and should be - * used unless there are special requirements. + * Context: Any context. */ -void ida_simple_remove(struct ida *ida, unsigned int id) +void ida_free(struct ida *ida, unsigned int id) { unsigned long flags; @@ -624,4 +616,4 @@ void ida_simple_remove(struct ida *ida, unsigned int id) ida_remove(ida, id); xa_unlock_irqrestore(&ida->ida_rt, flags); } -EXPORT_SYMBOL(ida_simple_remove); +EXPORT_SYMBOL(ida_free); -- cgit v1.2.3 From 8ab8ba38d48867aac01812e18f48fc9173ccd400 Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Mon, 18 Jun 2018 16:59:29 -0400 Subject: ida: Start new test_ida module Start transitioning the IDA tests into kernel space. Framework heavily cribbed from test_xarray.c. Signed-off-by: Matthew Wilcox --- lib/Kconfig.debug | 3 +++ lib/Makefile | 1 + lib/test_ida.c | 45 +++++++++++++++++++++++++++++++++++++ tools/testing/radix-tree/Makefile | 1 + tools/testing/radix-tree/idr-test.c | 22 +++++++++++++++--- tools/testing/radix-tree/main.c | 3 +-- tools/testing/radix-tree/test.h | 3 +-- 7 files changed, 71 insertions(+), 7 deletions(-) create mode 100644 lib/test_ida.c (limited to 'lib') diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index 8838d1158d19..2fff661d9070 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -1827,6 +1827,9 @@ config TEST_HASH This is intended to help people writing architecture-specific optimized versions. If unsure, say N. +config TEST_IDA + tristate "Perform selftest on IDA functions" + config TEST_PARMAN tristate "Perform selftest on priority array manager" default n diff --git a/lib/Makefile b/lib/Makefile index 90dc5520b784..18d87ca4c949 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -50,6 +50,7 @@ obj-$(CONFIG_TEST_BPF) += test_bpf.o obj-$(CONFIG_TEST_FIRMWARE) += test_firmware.o obj-$(CONFIG_TEST_SYSCTL) += test_sysctl.o obj-$(CONFIG_TEST_HASH) += test_hash.o test_siphash.o +obj-$(CONFIG_TEST_IDA) += test_ida.o obj-$(CONFIG_TEST_KASAN) += test_kasan.o CFLAGS_test_kasan.o += -fno-builtin obj-$(CONFIG_TEST_UBSAN) += test_ubsan.o diff --git a/lib/test_ida.c b/lib/test_ida.c new file mode 100644 index 000000000000..8c9a0672696b --- /dev/null +++ b/lib/test_ida.c @@ -0,0 +1,45 @@ +// SPDX-License-Identifier: GPL-2.0+ +/* + * test_ida.c: Test the IDA API + * Copyright (c) 2016-2018 Microsoft Corporation + * Copyright (c) 2018 Oracle Corporation + * Author: Matthew Wilcox + */ + +#include +#include + +static unsigned int tests_run; +static unsigned int tests_passed; + +#ifdef __KERNEL__ +void ida_dump(struct ida *ida) { } +#endif +#define IDA_BUG_ON(ida, x) do { \ + tests_run++; \ + if (x) { \ + ida_dump(ida); \ + dump_stack(); \ + } else { \ + tests_passed++; \ + } \ +} while (0) + +static int ida_checks(void) +{ + DEFINE_IDA(ida); + + IDA_BUG_ON(&ida, !ida_is_empty(&ida)); + + printk("IDA: %u of %u tests passed\n", tests_passed, tests_run); + return (tests_run != tests_passed) ? 0 : -EINVAL; +} + +static void ida_exit(void) +{ +} + +module_init(ida_checks); +module_exit(ida_exit); +MODULE_AUTHOR("Matthew Wilcox "); +MODULE_LICENSE("GPL"); diff --git a/tools/testing/radix-tree/Makefile b/tools/testing/radix-tree/Makefile index da030a65d6d6..37baecc3766f 100644 --- a/tools/testing/radix-tree/Makefile +++ b/tools/testing/radix-tree/Makefile @@ -22,6 +22,7 @@ targets: generated/map-shift.h $(TARGETS) main: $(OFILES) +idr-test.o: ../../../lib/test_ida.c idr-test: idr-test.o $(CORE_OFILES) multiorder: multiorder.o $(CORE_OFILES) diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr-test.c index ee820fcc29b0..604b51dc9b38 100644 --- a/tools/testing/radix-tree/idr-test.c +++ b/tools/testing/radix-tree/idr-test.c @@ -309,6 +309,15 @@ void idr_checks(void) idr_u32_test(0); } +#define module_init(x) +#define module_exit(x) +#define MODULE_AUTHOR(x) +#define MODULE_LICENSE(x) +#define dump_stack() assert(0) +void ida_dump(struct ida *); + +#include "../../../lib/test_ida.c" + /* * Check that we get the correct error when we run out of memory doing * allocations. To ensure we run out of memory, just "forget" to preload. @@ -488,7 +497,7 @@ void ida_simple_get_remove_test(void) ida_destroy(&ida); } -void ida_checks(void) +void user_ida_checks(void) { DEFINE_IDA(ida); int id; @@ -582,12 +591,19 @@ void ida_thread_tests(void) pthread_join(threads[i], NULL); } +void ida_tests(void) +{ + user_ida_checks(); + ida_checks(); + ida_exit(); + ida_thread_tests(); +} + int __weak main(void) { radix_tree_init(); idr_checks(); - ida_checks(); - ida_thread_tests(); + ida_tests(); radix_tree_cpu_dead(1); rcu_barrier(); if (nr_allocated) diff --git a/tools/testing/radix-tree/main.c b/tools/testing/radix-tree/main.c index 584a8732f5ce..b741686e53d6 100644 --- a/tools/testing/radix-tree/main.c +++ b/tools/testing/radix-tree/main.c @@ -324,7 +324,7 @@ static void single_thread_tests(bool long_run) printv(2, "after dynamic_height_check: %d allocated, preempt %d\n", nr_allocated, preempt_count); idr_checks(); - ida_checks(); + ida_tests(); rcu_barrier(); printv(2, "after idr_checks: %d allocated, preempt %d\n", nr_allocated, preempt_count); @@ -371,7 +371,6 @@ int main(int argc, char **argv) iteration_test(0, 10 + 90 * long_run); iteration_test(7, 10 + 90 * long_run); single_thread_tests(long_run); - ida_thread_tests(); /* Free any remaining preallocated nodes */ radix_tree_cpu_dead(0); diff --git a/tools/testing/radix-tree/test.h b/tools/testing/radix-tree/test.h index 31f1d9b6f506..92d901eacf49 100644 --- a/tools/testing/radix-tree/test.h +++ b/tools/testing/radix-tree/test.h @@ -39,8 +39,7 @@ void multiorder_checks(void); void iteration_test(unsigned order, unsigned duration); void benchmark(void); void idr_checks(void); -void ida_checks(void); -void ida_thread_tests(void); +void ida_tests(void); struct item * item_tag_set(struct radix_tree_root *root, unsigned long index, int tag); -- cgit v1.2.3 From 0a3856392cff1542170b5bc37211c9a21fd0c3f6 Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Mon, 18 Jun 2018 17:23:37 -0400 Subject: test_ida: Move ida_check_leaf Convert to new API and move to kernel space. Take the opportunity to test the situation a little more thoroughly (ie at different offsets). Signed-off-by: Matthew Wilcox --- lib/test_ida.c | 25 +++++++++++++++++++++++++ tools/testing/radix-tree/idr-test.c | 27 --------------------------- 2 files changed, 25 insertions(+), 27 deletions(-) (limited to 'lib') diff --git a/lib/test_ida.c b/lib/test_ida.c index 8c9a0672696b..1988f91a20c8 100644 --- a/lib/test_ida.c +++ b/lib/test_ida.c @@ -25,11 +25,36 @@ void ida_dump(struct ida *ida) { } } \ } while (0) +/* + * Check what happens when we fill a leaf and then delete it. This may + * discover mishandling of IDR_FREE. + */ +static void ida_check_leaf(struct ida *ida, unsigned int base) +{ + unsigned long i; + + for (i = 0; i < IDA_BITMAP_BITS; i++) { + IDA_BUG_ON(ida, ida_alloc_min(ida, base, GFP_KERNEL) != + base + i); + } + + ida_destroy(ida); + IDA_BUG_ON(ida, !ida_is_empty(ida)); + + IDA_BUG_ON(ida, ida_alloc(ida, GFP_KERNEL) != 0); + IDA_BUG_ON(ida, ida_is_empty(ida)); + ida_free(ida, 0); + IDA_BUG_ON(ida, !ida_is_empty(ida)); +} + static int ida_checks(void) { DEFINE_IDA(ida); IDA_BUG_ON(&ida, !ida_is_empty(&ida)); + ida_check_leaf(&ida, 0); + ida_check_leaf(&ida, 1024); + ida_check_leaf(&ida, 1024 * 64); printk("IDA: %u of %u tests passed\n", tests_passed, tests_run); return (tests_run != tests_passed) ? 0 : -EINVAL; diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr-test.c index 0f557784327d..fef1f45b927b 100644 --- a/tools/testing/radix-tree/idr-test.c +++ b/tools/testing/radix-tree/idr-test.c @@ -336,32 +336,6 @@ void ida_check_nomem(void) IDA_BUG_ON(&ida, !ida_is_empty(&ida)); } -/* - * Check what happens when we fill a leaf and then delete it. This may - * discover mishandling of IDR_FREE. - */ -void ida_check_leaf(void) -{ - DEFINE_IDA(ida); - int id; - unsigned long i; - - for (i = 0; i < IDA_BITMAP_BITS; i++) { - assert(ida_pre_get(&ida, GFP_KERNEL)); - assert(!ida_get_new(&ida, &id)); - assert(id == i); - } - - ida_destroy(&ida); - assert(ida_is_empty(&ida)); - - assert(ida_pre_get(&ida, GFP_KERNEL)); - assert(!ida_get_new(&ida, &id)); - assert(id == 0); - ida_destroy(&ida); - assert(ida_is_empty(&ida)); -} - /* * Check handling of conversions between exceptional entries and full bitmaps. */ @@ -560,7 +534,6 @@ void user_ida_checks(void) ida_destroy(&ida); assert(ida_is_empty(&ida)); - ida_check_leaf(); ida_check_max(); ida_check_conv(); ida_check_random(); -- cgit v1.2.3 From 161b47e31f9912947a3a72dcb161c79978a1fe04 Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Mon, 18 Jun 2018 17:25:20 -0400 Subject: test_ida: Move ida_check_max Convert to new API and move to kernel space. Signed-off-by: Matthew Wilcox --- lib/test_ida.c | 23 +++++++++++++++++++++++ tools/testing/radix-tree/idr-test.c | 28 ---------------------------- 2 files changed, 23 insertions(+), 28 deletions(-) (limited to 'lib') diff --git a/lib/test_ida.c b/lib/test_ida.c index 1988f91a20c8..44174ec9f5bf 100644 --- a/lib/test_ida.c +++ b/lib/test_ida.c @@ -47,6 +47,28 @@ static void ida_check_leaf(struct ida *ida, unsigned int base) IDA_BUG_ON(ida, !ida_is_empty(ida)); } +/* + * Check allocations up to and slightly above the maximum allowed (2^31-1) ID. + * Allocating up to 2^31-1 should succeed, and then allocating the next one + * should fail. + */ +static void ida_check_max(struct ida *ida) +{ + unsigned long i, j; + + for (j = 1; j < 65537; j *= 2) { + unsigned long base = (1UL << 31) - j; + for (i = 0; i < j; i++) { + IDA_BUG_ON(ida, ida_alloc_min(ida, base, GFP_KERNEL) != + base + i); + } + IDA_BUG_ON(ida, ida_alloc_min(ida, base, GFP_KERNEL) != + -ENOSPC); + ida_destroy(ida); + IDA_BUG_ON(ida, !ida_is_empty(ida)); + } +} + static int ida_checks(void) { DEFINE_IDA(ida); @@ -55,6 +77,7 @@ static int ida_checks(void) ida_check_leaf(&ida, 0); ida_check_leaf(&ida, 1024); ida_check_leaf(&ida, 1024 * 64); + ida_check_max(&ida); printk("IDA: %u of %u tests passed\n", tests_passed, tests_run); return (tests_run != tests_passed) ? 0 : -EINVAL; diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr-test.c index fef1f45b927b..bd9699327f95 100644 --- a/tools/testing/radix-tree/idr-test.c +++ b/tools/testing/radix-tree/idr-test.c @@ -396,33 +396,6 @@ void ida_check_conv(void) ida_destroy(&ida); } -/* - * Check allocations up to and slightly above the maximum allowed (2^31-1) ID. - * Allocating up to 2^31-1 should succeed, and then allocating the next one - * should fail. - */ -void ida_check_max(void) -{ - DEFINE_IDA(ida); - int id, err; - unsigned long i, j; - - for (j = 1; j < 65537; j *= 2) { - unsigned long base = (1UL << 31) - j; - for (i = 0; i < j; i++) { - assert(ida_pre_get(&ida, GFP_KERNEL)); - assert(!ida_get_new_above(&ida, base, &id)); - assert(id == base + i); - } - assert(ida_pre_get(&ida, GFP_KERNEL)); - err = ida_get_new_above(&ida, base, &id); - assert(err == -ENOSPC); - ida_destroy(&ida); - assert(ida_is_empty(&ida)); - rcu_barrier(); - } -} - void ida_check_random(void) { DEFINE_IDA(ida); @@ -534,7 +507,6 @@ void user_ida_checks(void) ida_destroy(&ida); assert(ida_is_empty(&ida)); - ida_check_max(); ida_check_conv(); ida_check_random(); ida_simple_get_remove_test(); -- cgit v1.2.3 From 5c78b0b1ebe16fbae39a1cada79ab067965828f5 Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Mon, 18 Jun 2018 18:10:32 -0400 Subject: test_ida: Convert check_ida_conv to new API Move as much as possible to kernel space; leave the parts in user space that rely on checking memory allocation failures to detect the transition between an exceptional entry and a bitmap. Signed-off-by: Matthew Wilcox --- lib/test_ida.c | 30 ++++++++++++++++++++ tools/testing/radix-tree/idr-test.c | 56 +++++++------------------------------ 2 files changed, 40 insertions(+), 46 deletions(-) (limited to 'lib') diff --git a/lib/test_ida.c b/lib/test_ida.c index 44174ec9f5bf..eaee9a28f325 100644 --- a/lib/test_ida.c +++ b/lib/test_ida.c @@ -69,6 +69,35 @@ static void ida_check_max(struct ida *ida) } } +/* + * Check handling of conversions between exceptional entries and full bitmaps. + */ +static void ida_check_conv(struct ida *ida) +{ + unsigned long i; + + for (i = 0; i < IDA_BITMAP_BITS * 2; i += IDA_BITMAP_BITS) { + IDA_BUG_ON(ida, ida_alloc_min(ida, i + 1, GFP_KERNEL) != i + 1); + IDA_BUG_ON(ida, ida_alloc_min(ida, i + BITS_PER_LONG, + GFP_KERNEL) != i + BITS_PER_LONG); + ida_free(ida, i + 1); + ida_free(ida, i + BITS_PER_LONG); + IDA_BUG_ON(ida, !ida_is_empty(ida)); + } + + for (i = 0; i < IDA_BITMAP_BITS * 2; i++) + IDA_BUG_ON(ida, ida_alloc(ida, GFP_KERNEL) != i); + for (i = IDA_BITMAP_BITS * 2; i > 0; i--) + ida_free(ida, i - 1); + IDA_BUG_ON(ida, !ida_is_empty(ida)); + + for (i = 0; i < IDA_BITMAP_BITS + BITS_PER_LONG - 4; i++) + IDA_BUG_ON(ida, ida_alloc(ida, GFP_KERNEL) != i); + for (i = IDA_BITMAP_BITS + BITS_PER_LONG - 4; i > 0; i--) + ida_free(ida, i - 1); + IDA_BUG_ON(ida, !ida_is_empty(ida)); +} + static int ida_checks(void) { DEFINE_IDA(ida); @@ -78,6 +107,7 @@ static int ida_checks(void) ida_check_leaf(&ida, 1024); ida_check_leaf(&ida, 1024 * 64); ida_check_max(&ida); + ida_check_conv(&ida); printk("IDA: %u of %u tests passed\n", tests_passed, tests_run); return (tests_run != tests_passed) ? 0 : -EINVAL; diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr-test.c index bd9699327f95..c6026cfe3145 100644 --- a/tools/testing/radix-tree/idr-test.c +++ b/tools/testing/radix-tree/idr-test.c @@ -339,59 +339,23 @@ void ida_check_nomem(void) /* * Check handling of conversions between exceptional entries and full bitmaps. */ -void ida_check_conv(void) +void ida_check_conv_user(void) { DEFINE_IDA(ida); - int id; unsigned long i; - for (i = 0; i < IDA_BITMAP_BITS * 2; i += IDA_BITMAP_BITS) { - assert(ida_pre_get(&ida, GFP_KERNEL)); - assert(!ida_get_new_above(&ida, i + 1, &id)); - assert(id == i + 1); - assert(!ida_get_new_above(&ida, i + BITS_PER_LONG, &id)); - assert(id == i + BITS_PER_LONG); - ida_remove(&ida, i + 1); - ida_remove(&ida, i + BITS_PER_LONG); - assert(ida_is_empty(&ida)); - } - - assert(ida_pre_get(&ida, GFP_KERNEL)); - - for (i = 0; i < IDA_BITMAP_BITS * 2; i++) { - assert(ida_pre_get(&ida, GFP_KERNEL)); - assert(!ida_get_new(&ida, &id)); - assert(id == i); - } - - for (i = IDA_BITMAP_BITS * 2; i > 0; i--) { - ida_remove(&ida, i - 1); - } - assert(ida_is_empty(&ida)); - - for (i = 0; i < IDA_BITMAP_BITS + BITS_PER_LONG - 4; i++) { - assert(ida_pre_get(&ida, GFP_KERNEL)); - assert(!ida_get_new(&ida, &id)); - assert(id == i); - } - - for (i = IDA_BITMAP_BITS + BITS_PER_LONG - 4; i > 0; i--) { - ida_remove(&ida, i - 1); - } - assert(ida_is_empty(&ida)); - radix_tree_cpu_dead(1); for (i = 0; i < 1000000; i++) { - int err = ida_get_new(&ida, &id); - if (err == -EAGAIN) { - assert((i % IDA_BITMAP_BITS) == (BITS_PER_LONG - 2)); - assert(ida_pre_get(&ida, GFP_KERNEL)); - err = ida_get_new(&ida, &id); + int id = ida_alloc(&ida, GFP_NOWAIT); + if (id == -ENOMEM) { + IDA_BUG_ON(&ida, (i % IDA_BITMAP_BITS) != + BITS_PER_LONG - 2); + id = ida_alloc(&ida, GFP_KERNEL); } else { - assert((i % IDA_BITMAP_BITS) != (BITS_PER_LONG - 2)); + IDA_BUG_ON(&ida, (i % IDA_BITMAP_BITS) == + BITS_PER_LONG - 2); } - assert(!err); - assert(id == i); + IDA_BUG_ON(&ida, id != i); } ida_destroy(&ida); } @@ -507,7 +471,7 @@ void user_ida_checks(void) ida_destroy(&ida); assert(ida_is_empty(&ida)); - ida_check_conv(); + ida_check_conv_user(); ida_check_random(); ida_simple_get_remove_test(); -- cgit v1.2.3 From f272668deb9108b6118a85ffd73886b9a92c1002 Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Mon, 18 Jun 2018 18:39:28 -0400 Subject: test_ida: check_ida_destroy and check_ida_alloc Move these tests from the userspace test-suite to the kernel test-suite. Also convert check_ida_random to the new API. Signed-off-by: Matthew Wilcox --- lib/test_ida.c | 54 ++++++++++++++++++++++++++++ tools/testing/radix-tree/idr-test.c | 70 +++---------------------------------- 2 files changed, 58 insertions(+), 66 deletions(-) (limited to 'lib') diff --git a/lib/test_ida.c b/lib/test_ida.c index eaee9a28f325..2d1637d8136b 100644 --- a/lib/test_ida.c +++ b/lib/test_ida.c @@ -25,6 +25,58 @@ void ida_dump(struct ida *ida) { } } \ } while (0) +/* + * Straightforward checks that allocating and freeing IDs work. + */ +static void ida_check_alloc(struct ida *ida) +{ + int i, id; + + for (i = 0; i < 10000; i++) + IDA_BUG_ON(ida, ida_alloc(ida, GFP_KERNEL) != i); + + ida_free(ida, 20); + ida_free(ida, 21); + for (i = 0; i < 3; i++) { + id = ida_alloc(ida, GFP_KERNEL); + IDA_BUG_ON(ida, id < 0); + if (i == 2) + IDA_BUG_ON(ida, id != 10000); + } + + for (i = 0; i < 5000; i++) + ida_free(ida, i); + + IDA_BUG_ON(ida, ida_alloc_min(ida, 5000, GFP_KERNEL) != 10001); + ida_destroy(ida); + + IDA_BUG_ON(ida, !ida_is_empty(ida)); +} + +/* Destroy an IDA with a single entry at @base */ +static void ida_check_destroy_1(struct ida *ida, unsigned int base) +{ + IDA_BUG_ON(ida, ida_alloc_min(ida, base, GFP_KERNEL) != base); + IDA_BUG_ON(ida, ida_is_empty(ida)); + ida_destroy(ida); + IDA_BUG_ON(ida, !ida_is_empty(ida)); +} + +/* Check that ida_destroy and ida_is_empty work */ +static void ida_check_destroy(struct ida *ida) +{ + /* Destroy an already-empty IDA */ + IDA_BUG_ON(ida, !ida_is_empty(ida)); + ida_destroy(ida); + IDA_BUG_ON(ida, !ida_is_empty(ida)); + + ida_check_destroy_1(ida, 0); + ida_check_destroy_1(ida, 1); + ida_check_destroy_1(ida, 1023); + ida_check_destroy_1(ida, 1024); + ida_check_destroy_1(ida, 12345678); +} + /* * Check what happens when we fill a leaf and then delete it. This may * discover mishandling of IDR_FREE. @@ -103,6 +155,8 @@ static int ida_checks(void) DEFINE_IDA(ida); IDA_BUG_ON(&ida, !ida_is_empty(&ida)); + ida_check_alloc(&ida); + ida_check_destroy(&ida); ida_check_leaf(&ida, 0); ida_check_leaf(&ida, 1024); ida_check_leaf(&ida, 1024 * 64); diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr-test.c index c6026cfe3145..321ba92c70d2 100644 --- a/tools/testing/radix-tree/idr-test.c +++ b/tools/testing/radix-tree/idr-test.c @@ -364,7 +364,6 @@ void ida_check_random(void) { DEFINE_IDA(ida); DECLARE_BITMAP(bitmap, 2048); - int id, err; unsigned int i; time_t s = time(NULL); @@ -375,15 +374,11 @@ void ida_check_random(void) int bit = i & 2047; if (test_bit(bit, bitmap)) { __clear_bit(bit, bitmap); - ida_remove(&ida, bit); + ida_free(&ida, bit); } else { __set_bit(bit, bitmap); - do { - ida_pre_get(&ida, GFP_KERNEL); - err = ida_get_new_above(&ida, bit, &id); - } while (err == -EAGAIN); - assert(!err); - assert(id == bit); + IDA_BUG_ON(&ida, ida_alloc_min(&ida, bit, GFP_KERNEL) + != bit); } } ida_destroy(&ida); @@ -411,66 +406,9 @@ void ida_simple_get_remove_test(void) void user_ida_checks(void) { - DEFINE_IDA(ida); - int id; - unsigned long i; - radix_tree_cpu_dead(1); - ida_check_nomem(); - - for (i = 0; i < 10000; i++) { - assert(ida_pre_get(&ida, GFP_KERNEL)); - assert(!ida_get_new(&ida, &id)); - assert(id == i); - } - - ida_remove(&ida, 20); - ida_remove(&ida, 21); - for (i = 0; i < 3; i++) { - assert(ida_pre_get(&ida, GFP_KERNEL)); - assert(!ida_get_new(&ida, &id)); - if (i == 2) - assert(id == 10000); - } - - for (i = 0; i < 5000; i++) - ida_remove(&ida, i); - - assert(ida_pre_get(&ida, GFP_KERNEL)); - assert(!ida_get_new_above(&ida, 5000, &id)); - assert(id == 10001); - - ida_destroy(&ida); - - assert(ida_is_empty(&ida)); - - assert(ida_pre_get(&ida, GFP_KERNEL)); - assert(!ida_get_new_above(&ida, 1, &id)); - assert(id == 1); - - ida_remove(&ida, id); - assert(ida_is_empty(&ida)); - ida_destroy(&ida); - assert(ida_is_empty(&ida)); - - assert(ida_pre_get(&ida, GFP_KERNEL)); - assert(!ida_get_new_above(&ida, 1, &id)); - ida_destroy(&ida); - assert(ida_is_empty(&ida)); - - assert(ida_pre_get(&ida, GFP_KERNEL)); - assert(!ida_get_new_above(&ida, 1, &id)); - assert(id == 1); - assert(ida_pre_get(&ida, GFP_KERNEL)); - assert(!ida_get_new_above(&ida, 1025, &id)); - assert(id == 1025); - assert(ida_pre_get(&ida, GFP_KERNEL)); - assert(!ida_get_new_above(&ida, 10000, &id)); - assert(id == 10000); - ida_remove(&ida, 1025); - ida_destroy(&ida); - assert(ida_is_empty(&ida)); + ida_check_nomem(); ida_check_conv_user(); ida_check_random(); ida_simple_get_remove_test(); -- cgit v1.2.3 From b03f8e43c9261878bf29d8cc1c3ba458cc98287e Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Mon, 18 Jun 2018 19:02:48 -0400 Subject: ida: Remove old API Delete ida_pre_get(), ida_get_new(), ida_get_new_above() and ida_remove() from the public API. Some of these functions still exist as internal helpers, but they should not be called by consumers. Signed-off-by: Matthew Wilcox --- include/linux/idr.h | 21 ++++----------------- lib/idr.c | 48 +++++++----------------------------------------- lib/radix-tree.c | 9 --------- 3 files changed, 11 insertions(+), 67 deletions(-) (limited to 'lib') diff --git a/include/linux/idr.h b/include/linux/idr.h index cd339da0b1aa..2e1db0e36486 100644 --- a/include/linux/idr.h +++ b/include/linux/idr.h @@ -225,13 +225,9 @@ struct ida { } #define DEFINE_IDA(name) struct ida name = IDA_INIT(name) -int ida_pre_get(struct ida *ida, gfp_t gfp_mask); -int ida_get_new_above(struct ida *ida, int starting_id, int *p_id); -void ida_remove(struct ida *ida, int id); -void ida_destroy(struct ida *ida); - int ida_alloc_range(struct ida *, unsigned int min, unsigned int max, gfp_t); void ida_free(struct ida *, unsigned int id); +void ida_destroy(struct ida *ida); /** * ida_alloc() - Allocate an unused ID. @@ -292,20 +288,11 @@ static inline void ida_init(struct ida *ida) ida_alloc_range(ida, start, (end) - 1, gfp) #define ida_simple_remove(ida, id) ida_free(ida, id) -/** - * ida_get_new - allocate new ID - * @ida: idr handle - * @p_id: pointer to the allocated handle - * - * Simple wrapper around ida_get_new_above() w/ @starting_id of zero. - */ -static inline int ida_get_new(struct ida *ida, int *p_id) -{ - return ida_get_new_above(ida, 0, p_id); -} - static inline bool ida_is_empty(const struct ida *ida) { return radix_tree_empty(&ida->ida_rt); } + +/* in lib/radix-tree.c */ +int ida_pre_get(struct ida *ida, gfp_t gfp_mask); #endif /* __IDR_H__ */ diff --git a/lib/idr.c b/lib/idr.c index 760fce92f1fb..1dc52191acb6 100644 --- a/lib/idr.c +++ b/lib/idr.c @@ -320,16 +320,9 @@ EXPORT_SYMBOL(idr_replace); * ida_alloc(), ida_alloc_min(), ida_alloc_max() or ida_alloc_range(). * To free an ID, call ida_free(). * - * If you have more complex locking requirements, use a loop around - * ida_pre_get() and ida_get_new() to allocate a new ID. Then use - * ida_remove() to free an ID. You must make sure that ida_get_new() and - * ida_remove() cannot be called at the same time as each other for the - * same IDA. - * - * You can also use ida_get_new_above() if you need an ID to be allocated - * above a particular number. 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. + * 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. * * 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. @@ -370,25 +363,7 @@ EXPORT_SYMBOL(idr_replace); #define IDA_MAX (0x80000000U / IDA_BITMAP_BITS - 1) -/** - * ida_get_new_above - allocate new ID above or equal to a start id - * @ida: ida handle - * @start: id to start search at - * @id: pointer to the allocated handle - * - * Allocate new ID above or equal to @start. It should be called - * with any required locks to ensure that concurrent calls to - * ida_get_new_above() / ida_get_new() / ida_remove() are not allowed. - * Consider using ida_alloc_range() if you do not have complex locking - * requirements. - * - * 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. On success, it will return 0. - * - * @id returns a value in the range @start ... %0x7fffffff. - */ -int ida_get_new_above(struct ida *ida, int start, int *id) +static int ida_get_new_above(struct ida *ida, int start, int *id) { struct radix_tree_root *root = &ida->ida_rt; void __rcu **slot; @@ -473,16 +448,8 @@ int ida_get_new_above(struct ida *ida, int start, int *id) return 0; } } -EXPORT_SYMBOL(ida_get_new_above); -/** - * ida_remove - Free the given ID - * @ida: ida handle - * @id: ID to free - * - * This function should not be called at the same time as ida_get_new_above(). - */ -void ida_remove(struct ida *ida, int id) +static void ida_remove(struct ida *ida, int id) { unsigned long index = id / IDA_BITMAP_BITS; unsigned offset = id % IDA_BITMAP_BITS; @@ -519,9 +486,8 @@ void ida_remove(struct ida *ida, int id) } return; err: - WARN(1, "ida_remove called for id=%d which is not allocated.\n", id); + WARN(1, "ida_free called for id=%d which is not allocated.\n", id); } -EXPORT_SYMBOL(ida_remove); /** * ida_destroy() - Free all IDs. @@ -568,7 +534,7 @@ EXPORT_SYMBOL(ida_destroy); int ida_alloc_range(struct ida *ida, unsigned int min, unsigned int max, gfp_t gfp) { - int ret, id; + int ret, id = 0; unsigned long flags; if ((int)min < 0) diff --git a/lib/radix-tree.c b/lib/radix-tree.c index cc6096b97afb..bc03ecc4dfd2 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c @@ -2106,14 +2106,6 @@ void idr_preload(gfp_t gfp_mask) } EXPORT_SYMBOL(idr_preload); -/** - * ida_pre_get - reserve resources for ida allocation - * @ida: ida handle - * @gfp: memory allocation flags - * - * This function should be called before calling ida_get_new_above(). If it - * is unable to allocate memory, it will return %0. On success, it returns %1. - */ int ida_pre_get(struct ida *ida, gfp_t gfp) { /* @@ -2134,7 +2126,6 @@ int ida_pre_get(struct ida *ida, gfp_t gfp) return 1; } -EXPORT_SYMBOL(ida_pre_get); void __rcu **idr_get_free(struct radix_tree_root *root, struct radix_tree_iter *iter, gfp_t gfp, -- cgit v1.2.3 From 1df895190233fcc30d46beca4550bcafb7b959a6 Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Mon, 18 Jun 2018 19:11:56 -0400 Subject: ida: Change ida_get_new_above to return the id This calling convention makes more sense for the implementation as well as the callers. It even shaves 32 bytes off the compiled code size. Signed-off-by: Matthew Wilcox --- lib/idr.c | 30 ++++++++++++------------------ 1 file changed, 12 insertions(+), 18 deletions(-) (limited to 'lib') diff --git a/lib/idr.c b/lib/idr.c index 1dc52191acb6..fab2fd5bc326 100644 --- a/lib/idr.c +++ b/lib/idr.c @@ -363,7 +363,7 @@ EXPORT_SYMBOL(idr_replace); #define IDA_MAX (0x80000000U / IDA_BITMAP_BITS - 1) -static int ida_get_new_above(struct ida *ida, int start, int *id) +static int ida_get_new_above(struct ida *ida, int start) { struct radix_tree_root *root = &ida->ida_rt; void __rcu **slot; @@ -402,8 +402,8 @@ static int ida_get_new_above(struct ida *ida, int start, int *id) if (ebit < BITS_PER_LONG) { tmp |= 1UL << ebit; rcu_assign_pointer(*slot, (void *)tmp); - *id = new + ebit - RADIX_TREE_EXCEPTIONAL_SHIFT; - return 0; + return new + ebit - + RADIX_TREE_EXCEPTIONAL_SHIFT; } bitmap = this_cpu_xchg(ida_bitmap, NULL); if (!bitmap) @@ -434,8 +434,7 @@ static int ida_get_new_above(struct ida *ida, int start, int *id) RADIX_TREE_EXCEPTIONAL_ENTRY); radix_tree_iter_replace(root, &iter, slot, bitmap); - *id = new; - return 0; + return new; } bitmap = this_cpu_xchg(ida_bitmap, NULL); if (!bitmap) @@ -444,8 +443,7 @@ static int ida_get_new_above(struct ida *ida, int start, int *id) radix_tree_iter_replace(root, &iter, slot, bitmap); } - *id = new; - return 0; + return new; } } @@ -534,7 +532,7 @@ EXPORT_SYMBOL(ida_destroy); int ida_alloc_range(struct ida *ida, unsigned int min, unsigned int max, gfp_t gfp) { - int ret, id = 0; + int id = 0; unsigned long flags; if ((int)min < 0) @@ -545,24 +543,20 @@ int ida_alloc_range(struct ida *ida, unsigned int min, unsigned int max, again: xa_lock_irqsave(&ida->ida_rt, flags); - ret = ida_get_new_above(ida, min, &id); - if (!ret) { - if (id > max) { - ida_remove(ida, id); - ret = -ENOSPC; - } else { - ret = id; - } + id = ida_get_new_above(ida, min); + if (id > (int)max) { + ida_remove(ida, id); + id = -ENOSPC; } xa_unlock_irqrestore(&ida->ida_rt, flags); - if (unlikely(ret == -EAGAIN)) { + if (unlikely(id == -EAGAIN)) { if (!ida_pre_get(ida, gfp)) return -ENOMEM; goto again; } - return ret; + return id; } EXPORT_SYMBOL(ida_alloc_range); -- cgit v1.2.3