diff options
Diffstat (limited to 'tools/testing')
-rw-r--r-- | tools/testing/radix-tree/.gitignore | 1 | ||||
-rw-r--r-- | tools/testing/radix-tree/Makefile | 10 | ||||
-rw-r--r-- | tools/testing/radix-tree/idr-test.c | 242 | ||||
-rw-r--r-- | tools/testing/radix-tree/linux/export.h | 1 | ||||
-rw-r--r-- | tools/testing/radix-tree/linux/gfp.h | 8 | ||||
-rw-r--r-- | tools/testing/radix-tree/linux/idr.h | 1 | ||||
-rw-r--r-- | tools/testing/radix-tree/linux/kernel.h | 2 | ||||
-rw-r--r-- | tools/testing/radix-tree/main.c | 6 | ||||
-rw-r--r-- | tools/testing/radix-tree/test.h | 2 |
9 files changed, 267 insertions, 6 deletions
diff --git a/tools/testing/radix-tree/.gitignore b/tools/testing/radix-tree/.gitignore index 11d888ca6a92..3b5534b643f0 100644 --- a/tools/testing/radix-tree/.gitignore +++ b/tools/testing/radix-tree/.gitignore @@ -1,2 +1,3 @@ main radix-tree.c +idr.c diff --git a/tools/testing/radix-tree/Makefile b/tools/testing/radix-tree/Makefile index 3635e4d3eca7..c1308613a1f7 100644 --- a/tools/testing/radix-tree/Makefile +++ b/tools/testing/radix-tree/Makefile @@ -2,8 +2,8 @@ CFLAGS += -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE LDFLAGS += -lpthread -lurcu TARGETS = main -OFILES = main.o radix-tree.o linux.o test.o tag_check.o find_next_bit.o \ - regression1.o regression2.o regression3.o multiorder.o \ +OFILES = main.o radix-tree.o idr.o linux.o test.o tag_check.o find_next_bit.o \ + regression1.o regression2.o regression3.o multiorder.o idr-test.o \ iteration_check.o benchmark.o ifdef BENCHMARK @@ -23,7 +23,11 @@ find_next_bit.o: ../../lib/find_bit.c $(OFILES): *.h */*.h \ ../../include/linux/*.h \ - ../../../include/linux/radix-tree.h + ../../../include/linux/radix-tree.h \ + ../../../include/linux/idr.h radix-tree.c: ../../../lib/radix-tree.c sed -e 's/^static //' -e 's/__always_inline //' -e 's/inline //' < $< > $@ + +idr.c: ../../../lib/idr.c + sed -e 's/^static //' -e 's/__always_inline //' -e 's/inline //' < $< > $@ diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr-test.c new file mode 100644 index 000000000000..010127d392af --- /dev/null +++ b/tools/testing/radix-tree/idr-test.c @@ -0,0 +1,242 @@ +/* + * idr.c: Test the IDR API + * Copyright (c) 2016 Matthew Wilcox <willy@infradead.org> + * + * This program is free software; you can redistribute it and/or modify it + * under the terms and conditions of the GNU General Public License, + * version 2, as published by the Free Software Foundation. + * + * This program is distributed in the hope it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for + * more details. + */ +#include <linux/idr.h> +#include <linux/slab.h> +#include <linux/kernel.h> +#include <linux/errno.h> + +#include "test.h" + +#define DUMMY_PTR ((void *)0x12) + +int item_idr_free(int id, void *p, void *data) +{ + struct item *item = p; + assert(item->index == id); + idr_remove(data, id); + free(p); + + return 0; +} + +void item_idr_remove(struct idr *idr, int id) +{ + struct item *item = idr_find(idr, id); + assert(item->index == id); + idr_remove(idr, id); + free(item); +} + +void idr_alloc_test(void) +{ + unsigned long i; + DEFINE_IDR(idr); + + assert(idr_alloc_cyclic(&idr, DUMMY_PTR, 0, 0x4000, GFP_KERNEL) == 0); + assert(idr_alloc_cyclic(&idr, DUMMY_PTR, 0x3ffd, 0x4000, GFP_KERNEL) == 0x3ffd); + idr_remove(&idr, 0x3ffd); + idr_remove(&idr, 0); + + for (i = 0x3ffe; i < 0x4003; i++) { + int id; + struct item *item; + + if (i < 0x4000) + item = item_create(i, 0); + else + item = item_create(i - 0x3fff, 0); + + id = idr_alloc_cyclic(&idr, item, 1, 0x4000, GFP_KERNEL); + assert(id == item->index); + } + + idr_for_each(&idr, item_idr_free, &idr); +} + +void idr_replace_test(void) +{ + DEFINE_IDR(idr); + + idr_alloc(&idr, (void *)-1, 10, 11, GFP_KERNEL); + idr_replace(&idr, &idr, 10); + + idr_destroy(&idr); +} + +/* + * Unlike the radix tree, you can put a NULL pointer -- with care -- into + * the IDR. Some interfaces, like idr_find() do not distinguish between + * "present, value is NULL" and "not present", but that's exactly what some + * users want. + */ +void idr_null_test(void) +{ + int i; + DEFINE_IDR(idr); + + for (i = 0; i < 10; i++) + assert(idr_alloc(&idr, NULL, 0, 0, GFP_KERNEL) == i); + + assert(idr_replace(&idr, DUMMY_PTR, 3) == NULL); + assert(idr_replace(&idr, DUMMY_PTR, 4) == NULL); + assert(idr_replace(&idr, NULL, 4) == DUMMY_PTR); + assert(idr_replace(&idr, DUMMY_PTR, 11) == ERR_PTR(-ENOENT)); + idr_remove(&idr, 5); + assert(idr_alloc(&idr, NULL, 0, 0, GFP_KERNEL) == 5); + idr_remove(&idr, 5); + + for (i = 0; i < 10; i++) + idr_remove(&idr, i); + assert(idr_is_empty(&idr)); + + assert(idr_alloc(&idr, NULL, 0, 0, GFP_KERNEL) == 0); + assert(idr_replace(&idr, DUMMY_PTR, 3) == ERR_PTR(-ENOENT)); + assert(idr_replace(&idr, DUMMY_PTR, 0) == NULL); + assert(idr_replace(&idr, NULL, 0) == DUMMY_PTR); + + idr_destroy(&idr); + assert(idr_is_empty(&idr)); + + for (i = 1; i < 10; i++) + assert(idr_alloc(&idr, NULL, 1, 0, GFP_KERNEL) == i); + + idr_destroy(&idr); +} + +void idr_checks(void) +{ + unsigned long i; + DEFINE_IDR(idr); + + for (i = 0; i < 10000; i++) { + struct item *item = item_create(i, 0); + assert(idr_alloc(&idr, item, 0, 20000, GFP_KERNEL) == i); + } + + assert(idr_alloc(&idr, DUMMY_PTR, 5, 30, GFP_KERNEL) < 0); + + for (i = 0; i < 5000; i++) + item_idr_remove(&idr, i); + + idr_for_each(&idr, item_idr_free, &idr); + + assert(idr_is_empty(&idr)); + + for (i = INT_MAX - 3UL; i < INT_MAX + 1UL; i++) { + struct item *item = item_create(i, 0); + assert(idr_alloc(&idr, item, i, i + 10, GFP_KERNEL) == i); + } + assert(idr_alloc(&idr, DUMMY_PTR, i - 2, i, GFP_KERNEL) == -ENOSPC); + + idr_destroy(&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); + } + + idr_destroy(&idr); + + idr_replace_test(); + idr_alloc_test(); + idr_null_test(); +} + +/* + * 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. + * The first test is for not having a bitmap available, and the second test + * is for not being able to allocate a level of the radix tree. + */ +void ida_check_nomem(void) +{ + DEFINE_IDA(ida); + int id, err; + + err = ida_get_new(&ida, &id); + assert(err == -EAGAIN); + err = ida_get_new_above(&ida, 1UL << 30, &id); + assert(err == -EAGAIN); +} + +void ida_checks(void) +{ + DEFINE_IDA(ida); + + unsigned long i, j; + int id; + int err; + + ida_check_nomem(); + + for (i = 0; i < 10000; i++) { + ida_pre_get(&ida, GFP_KERNEL); + ida_get_new(&ida, &id); + assert(id == i); + } + + ida_remove(&ida, 20); + ida_remove(&ida, 21); + for (i = 0; i < 3; i++) { + ida_pre_get(&ida, GFP_KERNEL); + ida_get_new(&ida, &id); + if (i == 2) + assert(id == 10000); + } + + for (i = 0; i < 5000; i++) + ida_remove(&ida, i); + + ida_pre_get(&ida, GFP_KERNEL); + ida_get_new_above(&ida, 5000, &id); + assert(id == 10001); + + ida_destroy(&ida); + + assert(ida_is_empty(&ida)); + + ida_pre_get(&ida, GFP_KERNEL); + 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)); + + ida_pre_get(&ida, GFP_KERNEL); + ida_get_new_above(&ida, 1, &id); + ida_destroy(&ida); + assert(ida_is_empty(&ida)); + + for (j = 1; j < 65537; j *= 2) { + for (i = 0; i < j; i++) { + ida_pre_get(&ida, GFP_KERNEL); + err = ida_get_new_above(&ida, (1UL << 31) - j, &id); + assert(err == 0); + assert(id == (1UL << 31) - j + i); + } + ida_pre_get(&ida, GFP_KERNEL); + err = ida_get_new_above(&ida, 0x7fffffff, &id); + assert(err == -ENOSPC); + ida_destroy(&ida); + assert(ida_is_empty(&ida)); + rcu_barrier(); + } + + radix_tree_cpu_dead(1); +} diff --git a/tools/testing/radix-tree/linux/export.h b/tools/testing/radix-tree/linux/export.h index b6afd131998d..52690e595134 100644 --- a/tools/testing/radix-tree/linux/export.h +++ b/tools/testing/radix-tree/linux/export.h @@ -1,2 +1,3 @@ #define EXPORT_SYMBOL(sym) +#define EXPORT_SYMBOL_GPL(sym) diff --git a/tools/testing/radix-tree/linux/gfp.h b/tools/testing/radix-tree/linux/gfp.h index 5b09b2ce6c33..c08db2cf7f07 100644 --- a/tools/testing/radix-tree/linux/gfp.h +++ b/tools/testing/radix-tree/linux/gfp.h @@ -13,10 +13,12 @@ #define __GFP_DIRECT_RECLAIM 0x400000u #define __GFP_KSWAPD_RECLAIM 0x2000000u -#define __GFP_RECLAIM (__GFP_DIRECT_RECLAIM|__GFP_KSWAPD_RECLAIM) +#define __GFP_RECLAIM (__GFP_DIRECT_RECLAIM|__GFP_KSWAPD_RECLAIM) + +#define GFP_ATOMIC (__GFP_HIGH|__GFP_ATOMIC|__GFP_KSWAPD_RECLAIM) +#define GFP_KERNEL (__GFP_RECLAIM | __GFP_IO | __GFP_FS) +#define GFP_NOWAIT (__GFP_KSWAPD_RECLAIM) -#define GFP_ATOMIC (__GFP_HIGH|__GFP_ATOMIC|__GFP_KSWAPD_RECLAIM) -#define GFP_KERNEL (__GFP_RECLAIM | __GFP_IO | __GFP_FS) static inline bool gfpflags_allow_blocking(const gfp_t gfp_flags) { diff --git a/tools/testing/radix-tree/linux/idr.h b/tools/testing/radix-tree/linux/idr.h new file mode 100644 index 000000000000..4e342f2e37cf --- /dev/null +++ b/tools/testing/radix-tree/linux/idr.h @@ -0,0 +1 @@ +#include "../../../../include/linux/idr.h" diff --git a/tools/testing/radix-tree/linux/kernel.h b/tools/testing/radix-tree/linux/kernel.h index 9b43b4975d83..7d214e9ce021 100644 --- a/tools/testing/radix-tree/linux/kernel.h +++ b/tools/testing/radix-tree/linux/kernel.h @@ -30,6 +30,7 @@ #define __force #define DIV_ROUND_UP(n,d) (((n) + (d) - 1) / (d)) #define pr_debug printk +#define pr_cont printk #define smp_rmb() barrier() #define smp_wmb() barrier() @@ -41,6 +42,7 @@ const typeof( ((type *)0)->member ) *__mptr = (ptr); \ (type *)( (char *)__mptr - offsetof(type, member) );}) #define min(a, b) ((a) < (b) ? (a) : (b)) +#define max(a, b) ((a) < (b) ? (b) : (a)) #define cond_resched() sched_yield() diff --git a/tools/testing/radix-tree/main.c b/tools/testing/radix-tree/main.c index f7e9801a6754..ddd90a11db3f 100644 --- a/tools/testing/radix-tree/main.c +++ b/tools/testing/radix-tree/main.c @@ -3,6 +3,7 @@ #include <unistd.h> #include <time.h> #include <assert.h> +#include <limits.h> #include <linux/slab.h> #include <linux/radix-tree.h> @@ -314,6 +315,11 @@ static void single_thread_tests(bool long_run) rcu_barrier(); printf("after dynamic_height_check: %d allocated, preempt %d\n", nr_allocated, preempt_count); + idr_checks(); + ida_checks(); + rcu_barrier(); + printf("after idr_checks: %d allocated, preempt %d\n", + nr_allocated, preempt_count); big_gang_check(long_run); rcu_barrier(); printf("after big_gang_check: %d allocated, preempt %d\n", diff --git a/tools/testing/radix-tree/test.h b/tools/testing/radix-tree/test.h index 056a23b56467..b30e11d9d271 100644 --- a/tools/testing/radix-tree/test.h +++ b/tools/testing/radix-tree/test.h @@ -34,6 +34,8 @@ void tag_check(void); void multiorder_checks(void); void iteration_test(unsigned order, unsigned duration); void benchmark(void); +void idr_checks(void); +void ida_checks(void); struct item * item_tag_set(struct radix_tree_root *root, unsigned long index, int tag); |