diff options
Diffstat (limited to 'tools')
41 files changed, 689 insertions, 709 deletions
diff --git a/tools/include/asm-generic/bitops/atomic.h b/tools/include/asm-generic/bitops/atomic.h index 18663f59d72f..68b8c1516c5a 100644 --- a/tools/include/asm-generic/bitops/atomic.h +++ b/tools/include/asm-generic/bitops/atomic.h @@ -20,4 +20,7 @@ static __always_inline int test_bit(unsigned int nr, const unsigned long *addr) (((unsigned long *)addr)[nr / __BITS_PER_LONG])) != 0; } +#define __set_bit(nr, addr) set_bit(nr, addr) +#define __clear_bit(nr, addr) clear_bit(nr, addr) + #endif /* _TOOLS_LINUX_ASM_GENERIC_BITOPS_ATOMIC_H_ */ diff --git a/tools/include/asm/bug.h b/tools/include/asm/bug.h index beda1a884b50..4790f047a89c 100644 --- a/tools/include/asm/bug.h +++ b/tools/include/asm/bug.h @@ -12,6 +12,14 @@ unlikely(__ret_warn_on); \ }) +#define WARN_ON(condition) ({ \ + int __ret_warn_on = !!(condition); \ + if (unlikely(__ret_warn_on)) \ + __WARN_printf("assertion failed at %s:%d\n", \ + __FILE__, __LINE__); \ + unlikely(__ret_warn_on); \ +}) + #define WARN_ON_ONCE(condition) ({ \ static int __warned; \ int __ret_warn_once = !!(condition); \ diff --git a/tools/include/linux/bitmap.h b/tools/include/linux/bitmap.h index eef41d500e9e..e8b9f518e36b 100644 --- a/tools/include/linux/bitmap.h +++ b/tools/include/linux/bitmap.h @@ -4,6 +4,7 @@ #include <string.h> #include <linux/bitops.h> #include <stdlib.h> +#include <linux/kernel.h> #define DECLARE_BITMAP(name,bits) \ unsigned long name[BITS_TO_LONGS(bits)] diff --git a/tools/include/linux/bitops.h b/tools/include/linux/bitops.h index fc446343ff41..1aecad369af5 100644 --- a/tools/include/linux/bitops.h +++ b/tools/include/linux/bitops.h @@ -2,7 +2,6 @@ #define _TOOLS_LINUX_BITOPS_H_ #include <asm/types.h> -#include <linux/kernel.h> #include <linux/compiler.h> #ifndef __WORDSIZE diff --git a/tools/include/linux/compiler.h b/tools/include/linux/compiler.h index 6326ede9aece..8de163b17c0d 100644 --- a/tools/include/linux/compiler.h +++ b/tools/include/linux/compiler.h @@ -25,6 +25,8 @@ #endif #define __user +#define __rcu +#define __read_mostly #ifndef __attribute_const__ # define __attribute_const__ @@ -54,6 +56,8 @@ # define unlikely(x) __builtin_expect(!!(x), 0) #endif +#define uninitialized_var(x) x = *(&(x)) + #define ACCESS_ONCE(x) (*(volatile typeof(x) *)&(x)) #include <linux/types.h> diff --git a/tools/include/linux/spinlock.h b/tools/include/linux/spinlock.h new file mode 100644 index 000000000000..58397dcb19d6 --- /dev/null +++ b/tools/include/linux/spinlock.h @@ -0,0 +1,5 @@ +#define spinlock_t pthread_mutex_t +#define DEFINE_SPINLOCK(x) pthread_mutex_t x = PTHREAD_MUTEX_INITIALIZER; + +#define spin_lock_irqsave(x, f) (void)f, pthread_mutex_lock(x) +#define spin_unlock_irqrestore(x, f) (void)f, pthread_mutex_unlock(x) diff --git a/tools/testing/radix-tree/.gitignore b/tools/testing/radix-tree/.gitignore index 11d888ca6a92..d4706c0ffceb 100644 --- a/tools/testing/radix-tree/.gitignore +++ b/tools/testing/radix-tree/.gitignore @@ -1,2 +1,6 @@ +generated/map-shift.h +idr.c +idr-test main +multiorder radix-tree.c diff --git a/tools/testing/radix-tree/Makefile b/tools/testing/radix-tree/Makefile index 3635e4d3eca7..f11315bedefc 100644 --- a/tools/testing/radix-tree/Makefile +++ b/tools/testing/radix-tree/Makefile @@ -1,29 +1,47 @@ -CFLAGS += -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE +CFLAGS += -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address 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 \ - iteration_check.o benchmark.o +TARGETS = main idr-test multiorder +CORE_OFILES := radix-tree.o idr.o linux.o test.o find_bit.o +OFILES = main.o $(CORE_OFILES) regression1.o regression2.o regression3.o \ + tag_check.o multiorder.o idr-test.o iteration_check.o benchmark.o -ifdef BENCHMARK - CFLAGS += -DBENCHMARK=1 +ifndef SHIFT + SHIFT=3 endif -targets: $(TARGETS) +targets: mapshift $(TARGETS) main: $(OFILES) - $(CC) $(CFLAGS) $(LDFLAGS) $(OFILES) -o main + $(CC) $(CFLAGS) $(LDFLAGS) $^ -o main + +idr-test: idr-test.o $(CORE_OFILES) + $(CC) $(CFLAGS) $(LDFLAGS) $^ -o idr-test + +multiorder: multiorder.o $(CORE_OFILES) + $(CC) $(CFLAGS) $(LDFLAGS) $^ -o multiorder clean: - $(RM) -f $(TARGETS) *.o radix-tree.c + $(RM) $(TARGETS) *.o radix-tree.c idr.c generated/map-shift.h -find_next_bit.o: ../../lib/find_bit.c - $(CC) $(CFLAGS) -c -o $@ $< +vpath %.c ../../lib -$(OFILES): *.h */*.h \ +$(OFILES): *.h */*.h generated/map-shift.h \ ../../include/linux/*.h \ - ../../../include/linux/radix-tree.h + ../../include/asm/*.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 //' < $< > $@ + +.PHONY: mapshift + +mapshift: + @if ! grep -qw $(SHIFT) generated/map-shift.h; then \ + echo "#define RADIX_TREE_MAP_SHIFT $(SHIFT)" > \ + generated/map-shift.h; \ + fi diff --git a/tools/testing/radix-tree/benchmark.c b/tools/testing/radix-tree/benchmark.c index 215ca86c7605..9b09ddfe462f 100644 --- a/tools/testing/radix-tree/benchmark.c +++ b/tools/testing/radix-tree/benchmark.c @@ -71,7 +71,7 @@ static void benchmark_size(unsigned long size, unsigned long step, int order) tagged = benchmark_iter(&tree, true); normal = benchmark_iter(&tree, false); - printf("Size %ld, step %6ld, order %d tagged %10lld ns, normal %10lld ns\n", + printv(2, "Size %ld, step %6ld, order %d tagged %10lld ns, normal %10lld ns\n", size, step, order, tagged, normal); item_kill_tree(&tree); @@ -85,8 +85,8 @@ void benchmark(void) 128, 256, 512, 12345, 0}; int c, s; - printf("starting benchmarks\n"); - printf("RADIX_TREE_MAP_SHIFT = %d\n", RADIX_TREE_MAP_SHIFT); + printv(1, "starting benchmarks\n"); + printv(1, "RADIX_TREE_MAP_SHIFT = %d\n", RADIX_TREE_MAP_SHIFT); for (c = 0; size[c]; c++) for (s = 0; step[s]; s++) diff --git a/tools/testing/radix-tree/generated/autoconf.h b/tools/testing/radix-tree/generated/autoconf.h index ad18cf5a2a3a..cf88dc5b8832 100644 --- a/tools/testing/radix-tree/generated/autoconf.h +++ b/tools/testing/radix-tree/generated/autoconf.h @@ -1,3 +1 @@ #define CONFIG_RADIX_TREE_MULTIORDER 1 -#define CONFIG_SHMEM 1 -#define CONFIG_SWAP 1 diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr-test.c new file mode 100644 index 000000000000..a26098c6123d --- /dev/null +++ b/tools/testing/radix-tree/idr-test.c @@ -0,0 +1,444 @@ +/* + * idr-test.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/bitmap.h> +#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); + 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); + idr_destroy(&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); + + assert(idr_is_empty(&idr)); + + assert(idr_alloc(&idr, NULL, 0, 0, GFP_KERNEL) == 0); + assert(!idr_is_empty(&idr)); + idr_remove(&idr, 0); + assert(idr_is_empty(&idr)); + + assert(idr_alloc(&idr, NULL, 0, 0, GFP_KERNEL) == 0); + assert(!idr_is_empty(&idr)); + idr_destroy(&idr); + assert(idr_is_empty(&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 < 9; i++) { + idr_remove(&idr, i); + assert(!idr_is_empty(&idr)); + } + idr_remove(&idr, 8); + assert(!idr_is_empty(&idr)); + idr_remove(&idr, 9); + 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); + assert(idr_is_empty(&idr)); +} + +void idr_nowait_test(void) +{ + unsigned int i; + DEFINE_IDR(idr); + + idr_preload(GFP_KERNEL); + + for (i = 0; i < 3; i++) { + struct item *item = item_create(i, 0); + assert(idr_alloc(&idr, item, i, i + 1, GFP_NOWAIT) == i); + } + + idr_preload_end(); + + idr_for_each(&idr, item_idr_free, &idr); + 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_remove(&idr, 3); + + idr_for_each(&idr, item_idr_free, &idr); + idr_destroy(&idr); + + assert(idr_is_empty(&idr)); + + idr_remove(&idr, 3); + idr_remove(&idr, 0); + + 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_for_each(&idr, item_idr_free, &idr); + 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_for_each(&idr, item_idr_free, &idr); + idr_destroy(&idr); + + idr_replace_test(); + idr_alloc_test(); + idr_null_test(); + idr_nowait_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_above(&ida, 256, &id); + assert(err == -EAGAIN); + err = ida_get_new_above(&ida, 1UL << 30, &id); + assert(err == -EAGAIN); +} + +/* + * 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. + */ +void ida_check_conv(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); + } else { + assert((i % IDA_BITMAP_BITS) != (BITS_PER_LONG - 2)); + } + assert(!err); + assert(id == i); + } + 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); + DECLARE_BITMAP(bitmap, 2048); + int id; + unsigned int i; + time_t s = time(NULL); + + repeat: + memset(bitmap, 0, sizeof(bitmap)); + for (i = 0; i < 100000; i++) { + int i = rand(); + int bit = i & 2047; + if (test_bit(bit, bitmap)) { + __clear_bit(bit, bitmap); + ida_remove(&ida, bit); + } else { + __set_bit(bit, bitmap); + ida_pre_get(&ida, GFP_KERNEL); + assert(!ida_get_new_above(&ida, bit, &id)); + assert(id == bit); + } + } + ida_destroy(&ida); + if (time(NULL) < s + 10) + goto repeat; +} + +void 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_leaf(); + ida_check_max(); + ida_check_conv(); + ida_check_random(); + + radix_tree_cpu_dead(1); +} + +int __weak main(void) +{ + radix_tree_init(); + idr_checks(); + ida_checks(); + rcu_barrier(); + if (nr_allocated) + printf("nr_allocated = %d\n", nr_allocated); + return 0; +} diff --git a/tools/testing/radix-tree/iteration_check.c b/tools/testing/radix-tree/iteration_check.c index 7572b7ed930e..a92bab513701 100644 --- a/tools/testing/radix-tree/iteration_check.c +++ b/tools/testing/radix-tree/iteration_check.c @@ -177,7 +177,7 @@ void iteration_test(unsigned order, unsigned test_duration) { int i; - printf("Running %siteration tests for %d seconds\n", + printv(1, "Running %siteration tests for %d seconds\n", order > 0 ? "multiorder " : "", test_duration); max_order = order; diff --git a/tools/testing/radix-tree/linux.c b/tools/testing/radix-tree/linux.c index d31ea7c9abec..cf48c8473f48 100644 --- a/tools/testing/radix-tree/linux.c +++ b/tools/testing/radix-tree/linux.c @@ -5,7 +5,7 @@ #include <unistd.h> #include <assert.h> -#include <linux/mempool.h> +#include <linux/gfp.h> #include <linux/poison.h> #include <linux/slab.h> #include <linux/radix-tree.h> @@ -13,6 +13,8 @@ int nr_allocated; int preempt_count; +int kmalloc_verbose; +int test_verbose; struct kmem_cache { pthread_mutex_t lock; @@ -22,27 +24,6 @@ struct kmem_cache { void (*ctor)(void *); }; -void *mempool_alloc(mempool_t *pool, int gfp_mask) -{ - return pool->alloc(gfp_mask, pool->data); -} - -void mempool_free(void *element, mempool_t *pool) -{ - pool->free(element, pool->data); -} - -mempool_t *mempool_create(int min_nr, mempool_alloc_t *alloc_fn, - mempool_free_t *free_fn, void *pool_data) -{ - mempool_t *ret = malloc(sizeof(*ret)); - - ret->alloc = alloc_fn; - ret->free = free_fn; - ret->data = pool_data; - return ret; -} - void *kmem_cache_alloc(struct kmem_cache *cachep, int flags) { struct radix_tree_node *node; @@ -54,9 +35,9 @@ void *kmem_cache_alloc(struct kmem_cache *cachep, int flags) if (cachep->nr_objs) { cachep->nr_objs--; node = cachep->objs; - cachep->objs = node->private_data; + cachep->objs = node->parent; pthread_mutex_unlock(&cachep->lock); - node->private_data = NULL; + node->parent = NULL; } else { pthread_mutex_unlock(&cachep->lock); node = malloc(cachep->size); @@ -65,6 +46,8 @@ void *kmem_cache_alloc(struct kmem_cache *cachep, int flags) } uatomic_inc(&nr_allocated); + if (kmalloc_verbose) + printf("Allocating %p from slab\n", node); return node; } @@ -72,6 +55,8 @@ void kmem_cache_free(struct kmem_cache *cachep, void *objp) { assert(objp); uatomic_dec(&nr_allocated); + if (kmalloc_verbose) + printf("Freeing %p to slab\n", objp); pthread_mutex_lock(&cachep->lock); if (cachep->nr_objs > 10) { memset(objp, POISON_FREE, cachep->size); @@ -79,7 +64,7 @@ void kmem_cache_free(struct kmem_cache *cachep, void *objp) } else { struct radix_tree_node *node = objp; cachep->nr_objs++; - node->private_data = cachep->objs; + node->parent = cachep->objs; cachep->objs = node; } pthread_mutex_unlock(&cachep->lock); @@ -89,6 +74,8 @@ void *kmalloc(size_t size, gfp_t gfp) { void *ret = malloc(size); uatomic_inc(&nr_allocated); + if (kmalloc_verbose) + printf("Allocating %p from malloc\n", ret); return ret; } @@ -97,6 +84,8 @@ void kfree(void *p) if (!p) return; uatomic_dec(&nr_allocated); + if (kmalloc_verbose) + printf("Freeing %p to malloc\n", p); free(p); } diff --git a/tools/testing/radix-tree/linux/bitops.h b/tools/testing/radix-tree/linux/bitops.h deleted file mode 100644 index a13e9bc76eec..000000000000 --- a/tools/testing/radix-tree/linux/bitops.h +++ /dev/null @@ -1,160 +0,0 @@ -#ifndef _ASM_GENERIC_BITOPS_NON_ATOMIC_H_ -#define _ASM_GENERIC_BITOPS_NON_ATOMIC_H_ - -#include <linux/types.h> -#include <linux/bitops/find.h> -#include <linux/bitops/hweight.h> -#include <linux/kernel.h> - -#define BIT_MASK(nr) (1UL << ((nr) % BITS_PER_LONG)) -#define BIT_WORD(nr) ((nr) / BITS_PER_LONG) -#define BITS_PER_BYTE 8 -#define BITS_TO_LONGS(nr) DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(long)) - -/** - * __set_bit - Set a bit in memory - * @nr: the bit to set - * @addr: the address to start counting from - * - * Unlike set_bit(), this function is non-atomic and may be reordered. - * If it's called on the same region of memory simultaneously, the effect - * may be that only one operation succeeds. - */ -static inline void __set_bit(int nr, volatile unsigned long *addr) -{ - unsigned long mask = BIT_MASK(nr); - unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr); - - *p |= mask; -} - -static inline void __clear_bit(int nr, volatile unsigned long *addr) -{ - unsigned long mask = BIT_MASK(nr); - unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr); - - *p &= ~mask; -} - -/** - * __change_bit - Toggle a bit in memory - * @nr: the bit to change - * @addr: the address to start counting from - * - * Unlike change_bit(), this function is non-atomic and may be reordered. - * If it's called on the same region of memory simultaneously, the effect - * may be that only one operation succeeds. - */ -static inline void __change_bit(int nr, volatile unsigned long *addr) -{ - unsigned long mask = BIT_MASK(nr); - unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr); - - *p ^= mask; -} - -/** - * __test_and_set_bit - Set a bit and return its old value - * @nr: Bit to set - * @addr: Address to count from - * - * This operation is non-atomic and can be reordered. - * If two examples of this operation race, one can appear to succeed - * but actually fail. You must protect multiple accesses with a lock. - */ -static inline int __test_and_set_bit(int nr, volatile unsigned long *addr) -{ - unsigned long mask = BIT_MASK(nr); - unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr); - unsigned long old = *p; - - *p = old | mask; - return (old & mask) != 0; -} - -/** - * __test_and_clear_bit - Clear a bit and return its old value - * @nr: Bit to clear - * @addr: Address to count from - * - * This operation is non-atomic and can be reordered. - * If two examples of this operation race, one can appear to succeed - * but actually fail. You must protect multiple accesses with a lock. - */ -static inline int __test_and_clear_bit(int nr, volatile unsigned long *addr) -{ - unsigned long mask = BIT_MASK(nr); - unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr); - unsigned long old = *p; - - *p = old & ~mask; - return (old & mask) != 0; -} - -/* WARNING: non atomic and it can be reordered! */ -static inline int __test_and_change_bit(int nr, - volatile unsigned long *addr) -{ - unsigned long mask = BIT_MASK(nr); - unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr); - unsigned long old = *p; - - *p = old ^ mask; - return (old & mask) != 0; -} - -/** - * test_bit - Determine whether a bit is set - * @nr: bit number to test - * @addr: Address to start counting from - */ -static inline int test_bit(int nr, const volatile unsigned long *addr) -{ - return 1UL & (addr[BIT_WORD(nr)] >> (nr & (BITS_PER_LONG-1))); -} - -/** - * __ffs - find first bit in word. - * @word: The word to search - * - * Undefined if no bit exists, so code should check against 0 first. - */ -static inline unsigned long __ffs(unsigned long word) -{ - int num = 0; - - if ((word & 0xffffffff) == 0) { - num += 32; - word >>= 32; - } - if ((word & 0xffff) == 0) { - num += 16; - word >>= 16; - } - if ((word & 0xff) == 0) { - num += 8; - word >>= 8; - } - if ((word & 0xf) == 0) { - num += 4; - word >>= 4; - } - if ((word & 0x3) == 0) { - num += 2; - word >>= 2; - } - if ((word & 0x1) == 0) - num += 1; - return num; -} - -unsigned long find_next_bit(const unsigned long *addr, - unsigned long size, - unsigned long offset); - -static inline unsigned long hweight_long(unsigned long w) -{ - return sizeof(w) == 4 ? hweight32(w) : hweight64(w); -} - -#endif /* _ASM_GENERIC_BITOPS_NON_ATOMIC_H_ */ diff --git a/tools/testing/radix-tree/linux/bitops/__ffs.h b/tools/testing/radix-tree/linux/bitops/__ffs.h deleted file mode 100644 index 9a3274aecf83..000000000000 --- a/tools/testing/radix-tree/linux/bitops/__ffs.h +++ /dev/null @@ -1,43 +0,0 @@ -#ifndef _ASM_GENERIC_BITOPS___FFS_H_ -#define _ASM_GENERIC_BITOPS___FFS_H_ - -#include <asm/types.h> - -/** - * __ffs - find first bit in word. - * @word: The word to search - * - * Undefined if no bit exists, so code should check against 0 first. - */ -static inline unsigned long __ffs(unsigned long word) -{ - int num = 0; - -#if BITS_PER_LONG == 64 - if ((word & 0xffffffff) == 0) { - num += 32; - word >>= 32; - } -#endif - if ((word & 0xffff) == 0) { - num += 16; - word >>= 16; - } - if ((word & 0xff) == 0) { - num += 8; - word >>= 8; - } - if ((word & 0xf) == 0) { - num += 4; - word >>= 4; - } - if ((word & 0x3) == 0) { - num += 2; - word >>= 2; - } - if ((word & 0x1) == 0) - num += 1; - return num; -} - -#endif /* _ASM_GENERIC_BITOPS___FFS_H_ */ diff --git a/tools/testing/radix-tree/linux/bitops/ffs.h b/tools/testing/radix-tree/linux/bitops/ffs.h deleted file mode 100644 index fbbb43af7dc0..000000000000 --- a/tools/testing/radix-tree/linux/bitops/ffs.h +++ /dev/null @@ -1,41 +0,0 @@ -#ifndef _ASM_GENERIC_BITOPS_FFS_H_ -#define _ASM_GENERIC_BITOPS_FFS_H_ - -/** - * ffs - find first bit set - * @x: the word to search - * - * This is defined the same way as - * the libc and compiler builtin ffs routines, therefore - * differs in spirit from the above ffz (man ffs). - */ -static inline int ffs(int x) -{ - int r = 1; - - if (!x) - return 0; - if (!(x & 0xffff)) { - x >>= 16; - r += 16; - } - if (!(x & 0xff)) { - x >>= 8; - r += 8; - } - if (!(x & 0xf)) { - x >>= 4; - r += 4; - } - if (!(x & 3)) { - x >>= 2; - r += 2; - } - if (!(x & 1)) { - x >>= 1; - r += 1; - } - return r; -} - -#endif /* _ASM_GENERIC_BITOPS_FFS_H_ */ diff --git a/tools/testing/radix-tree/linux/bitops/ffz.h b/tools/testing/radix-tree/linux/bitops/ffz.h deleted file mode 100644 index 6744bd4cdf46..000000000000 --- a/tools/testing/radix-tree/linux/bitops/ffz.h +++ /dev/null @@ -1,12 +0,0 @@ -#ifndef _ASM_GENERIC_BITOPS_FFZ_H_ -#define _ASM_GENERIC_BITOPS_FFZ_H_ - -/* - * ffz - find first zero in word. - * @word: The word to search - * - * Undefined if no zero exists, so code should check against ~0UL first. - */ -#define ffz(x) __ffs(~(x)) - -#endif /* _ASM_GENERIC_BITOPS_FFZ_H_ */ diff --git a/tools/testing/radix-tree/linux/bitops/find.h b/tools/testing/radix-tree/linux/bitops/find.h deleted file mode 100644 index 72a51e5a12ef..000000000000 --- a/tools/testing/radix-tree/linux/bitops/find.h +++ /dev/null @@ -1,13 +0,0 @@ -#ifndef _ASM_GENERIC_BITOPS_FIND_H_ -#define _ASM_GENERIC_BITOPS_FIND_H_ - -extern unsigned long find_next_bit(const unsigned long *addr, unsigned long - size, unsigned long offset); - -extern unsigned long find_next_zero_bit(const unsigned long *addr, unsigned - long size, unsigned long offset); - -#define find_first_bit(addr, size) find_next_bit((addr), (size), 0) -#define find_first_zero_bit(addr, size) find_next_zero_bit((addr), (size), 0) - -#endif /*_ASM_GENERIC_BITOPS_FIND_H_ */ diff --git a/tools/testing/radix-tree/linux/bitops/fls.h b/tools/testing/radix-tree/linux/bitops/fls.h deleted file mode 100644 index 850859bc5069..000000000000 --- a/tools/testing/radix-tree/linux/bitops/fls.h +++ /dev/null @@ -1,41 +0,0 @@ -#ifndef _ASM_GENERIC_BITOPS_FLS_H_ -#define _ASM_GENERIC_BITOPS_FLS_H_ - -/** - * fls - find last (most-significant) bit set - * @x: the word to search - * - * This is defined the same way as ffs. - * Note fls(0) = 0, fls(1) = 1, fls(0x80000000) = 32. - */ - -static inline int fls(int x) -{ - int r = 32; - - if (!x) - return 0; - if (!(x & 0xffff0000u)) { - x <<= 16; - r -= 16; - } - if (!(x & 0xff000000u)) { - x <<= 8; - r -= 8; - } - if (!(x & 0xf0000000u)) { - x <<= 4; - r -= 4; - } - if (!(x & 0xc0000000u)) { - x <<= 2; - r -= 2; - } - if (!(x & 0x80000000u)) { - x <<= 1; - r -= 1; - } - return r; -} - -#endif /* _ASM_GENERIC_BITOPS_FLS_H_ */ diff --git a/tools/testing/radix-tree/linux/bitops/fls64.h b/tools/testing/radix-tree/linux/bitops/fls64.h deleted file mode 100644 index 1b6b17ce2428..000000000000 --- a/tools/testing/radix-tree/linux/bitops/fls64.h +++ /dev/null @@ -1,14 +0,0 @@ -#ifndef _ASM_GENERIC_BITOPS_FLS64_H_ -#define _ASM_GENERIC_BITOPS_FLS64_H_ - -#include <asm/types.h> - -static inline int fls64(__u64 x) -{ - __u32 h = x >> 32; - if (h) - return fls(h) + 32; - return fls(x); -} - -#endif /* _ASM_GENERIC_BITOPS_FLS64_H_ */ diff --git a/tools/testing/radix-tree/linux/bitops/hweight.h b/tools/testing/radix-tree/linux/bitops/hweight.h deleted file mode 100644 index fbbc383771da..000000000000 --- a/tools/testing/radix-tree/linux/bitops/hweight.h +++ /dev/null @@ -1,11 +0,0 @@ -#ifndef _ASM_GENERIC_BITOPS_HWEIGHT_H_ -#define _ASM_GENERIC_BITOPS_HWEIGHT_H_ - -#include <asm/types.h> - -extern unsigned int hweight32(unsigned int w); -extern unsigned int hweight16(unsigned int w); -extern unsigned int hweight8(unsigned int w); -extern unsigned long hweight64(__u64 w); - -#endif /* _ASM_GENERIC_BITOPS_HWEIGHT_H_ */ diff --git a/tools/testing/radix-tree/linux/bitops/le.h b/tools/testing/radix-tree/linux/bitops/le.h deleted file mode 100644 index b9c7e5d2d2ad..000000000000 --- a/tools/testing/radix-tree/linux/bitops/le.h +++ /dev/null @@ -1,53 +0,0 @@ -#ifndef _ASM_GENERIC_BITOPS_LE_H_ -#define _ASM_GENERIC_BITOPS_LE_H_ - -#include <asm/types.h> -#include <asm/byteorder.h> - -#define BITOP_WORD(nr) ((nr) / BITS_PER_LONG) -#define BITOP_LE_SWIZZLE ((BITS_PER_LONG-1) & ~0x7) - -#if defined(__LITTLE_ENDIAN) - -#define generic_test_le_bit(nr, addr) test_bit(nr, addr) -#define generic___set_le_bit(nr, addr) __set_bit(nr, addr) -#define generic___clear_le_bit(nr, addr) __clear_bit(nr, addr) - -#define generic_test_and_set_le_bit(nr, addr) test_and_set_bit(nr, addr) -#define generic_test_and_clear_le_bit(nr, addr) test_and_clear_bit(nr, addr) - -#define generic___test_and_set_le_bit(nr, addr) __test_and_set_bit(nr, addr) -#define generic___test_and_clear_le_bit(nr, addr) __test_and_clear_bit(nr, addr) - -#define generic_find_next_zero_le_bit(addr, size, offset) find_next_zero_bit(addr, size, offset) - -#elif defined(__BIG_ENDIAN) - -#define generic_test_le_bit(nr, addr) \ - test_bit((nr) ^ BITOP_LE_SWIZZLE, (addr)) -#define generic___set_le_bit(nr, addr) \ - __set_bit((nr) ^ BITOP_LE_SWIZZLE, (addr)) -#define generic___clear_le_bit(nr, addr) \ - __clear_bit((nr) ^ BITOP_LE_SWIZZLE, (addr)) - -#define generic_test_and_set_le_bit(nr, addr) \ - test_and_set_bit((nr) ^ BITOP_LE_SWIZZLE, (addr)) -#define generic_test_and_clear_le_bit(nr, addr) \ - test_and_clear_bit((nr) ^ BITOP_LE_SWIZZLE, (addr)) - -#define generic___test_and_set_le_bit(nr, addr) \ - __test_and_set_bit((nr) ^ BITOP_LE_SWIZZLE, (addr)) -#define generic___test_and_clear_le_bit(nr, addr) \ - __test_and_clear_bit((nr) ^ BITOP_LE_SWIZZLE, (addr)) - -extern unsigned long generic_find_next_zero_le_bit(const unsigned long *addr, - unsigned long size, unsigned long offset); - -#else -#error "Please fix <asm/byteorder.h>" -#endif - -#define generic_find_first_zero_le_bit(addr, size) \ - generic_find_next_zero_le_bit((addr), (size), 0) - -#endif /* _ASM_GENERIC_BITOPS_LE_H_ */ diff --git a/tools/testing/radix-tree/linux/bitops/non-atomic.h b/tools/testing/radix-tree/linux/bitops/non-atomic.h deleted file mode 100644 index 6a1bcb9d2c4a..000000000000 --- a/tools/testing/radix-tree/linux/bitops/non-atomic.h +++ /dev/null @@ -1,110 +0,0 @@ -#ifndef _ASM_GENERIC_BITOPS_NON_ATOMIC_H_ -#define _ASM_GENERIC_BITOPS_NON_ATOMIC_H_ - -#include <asm/types.h> - -#define BITOP_WORD(nr) ((nr) / BITS_PER_LONG) - -/** - * __set_bit - Set a bit in memory - * @nr: the bit to set - * @addr: the address to start counting from - * - * Unlike set_bit(), this function is non-atomic and may be reordered. - * If it's called on the same region of memory simultaneously, the effect - * may be that only one operation succeeds. - */ -static inline void __set_bit(int nr, volatile unsigned long *addr) -{ - unsigned long mask = BIT_MASK(nr); - unsigned long *p = ((unsigned long *)addr) + BITOP_WORD(nr); - - *p |= mask; -} - -static inline void __clear_bit(int nr, volatile unsigned long *addr) -{ - unsigned long mask = BIT_MASK(nr); - unsigned long *p = ((unsigned long *)addr) + BITOP_WORD(nr); - - *p &= ~mask; -} - -/** - * __change_bit - Toggle a bit in memory - * @nr: the bit to change - * @addr: the address to start counting from - * - * Unlike change_bit(), this function is non-atomic and may be reordered. - * If it's called on the same region of memory simultaneously, the effect - * may be that only one operation succeeds. - */ -static inline void __change_bit(int nr, volatile unsigned long *addr) -{ - unsigned long mask = BIT_MASK(nr); - unsigned long *p = ((unsigned long *)addr) + BITOP_WORD(nr); - - *p ^= mask; -} - -/** - * __test_and_set_bit - Set a bit and return its old value - * @nr: Bit to set - * @addr: Address to count from - * - * This operation is non-atomic and can be reordered. - * If two examples of this operation race, one can appear to succeed - * but actually fail. You must protect multiple accesses with a lock. - */ -static inline int __test_and_set_bit(int nr, volatile unsigned long *addr) -{ - unsigned long mask = BIT_MASK(nr); - unsigned long *p = ((unsigned long *)addr) + BITOP_WORD(nr); - unsigned long old = *p; - - *p = old | mask; - return (old & mask) != 0; -} - -/** - * __test_and_clear_bit - Clear a bit and return its old value - * @nr: Bit to clear - * @addr: Address to count from - * - * This operation is non-atomic and can be reordered. - * If two examples of this operation race, one can appear to succeed - * but actually fail. You must protect multiple accesses with a lock. - */ -static inline int __test_and_clear_bit(int nr, volatile unsigned long *addr) -{ - unsigned long mask = BIT_MASK(nr); - unsigned long *p = ((unsigned long *)addr) + BITOP_WORD(nr); - unsigned long old = *p; - - *p = old & ~mask; - return (old & mask) != 0; -} - -/* WARNING: non atomic and it can be reordered! */ -static inline int __test_and_change_bit(int nr, - volatile unsigned long *addr) -{ - unsigned long mask = BIT_MASK(nr); - unsigned long *p = ((unsigned long *)addr) + BITOP_WORD(nr); - unsigned long old = *p; - - *p = old ^ mask; - return (old & mask) != 0; -} - -/** - * test_bit - Determine whether a bit is set - * @nr: bit number to test - * @addr: Address to start counting from - */ -static inline int test_bit(int nr, const volatile unsigned long *addr) -{ - return 1UL & (addr[BITOP_WORD(nr)] >> (nr & (BITS_PER_LONG-1))); -} - -#endif /* _ASM_GENERIC_BITOPS_NON_ATOMIC_H_ */ diff --git a/tools/testing/radix-tree/linux/export.h b/tools/testing/radix-tree/linux/export.h deleted file mode 100644 index b6afd131998d..000000000000 --- a/tools/testing/radix-tree/linux/export.h +++ /dev/null @@ -1,2 +0,0 @@ - -#define EXPORT_SYMBOL(sym) diff --git a/tools/testing/radix-tree/linux/gfp.h b/tools/testing/radix-tree/linux/gfp.h index 5b09b2ce6c33..39a0dcb9475a 100644 --- a/tools/testing/radix-tree/linux/gfp.h +++ b/tools/testing/radix-tree/linux/gfp.h @@ -1,6 +1,8 @@ #ifndef _GFP_H #define _GFP_H +#include <linux/types.h> + #define __GFP_BITS_SHIFT 26 #define __GFP_BITS_MASK ((gfp_t)((1 << __GFP_BITS_SHIFT) - 1)) @@ -13,10 +15,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/init.h b/tools/testing/radix-tree/linux/init.h index 360cabb3c4e7..1bb0afc21309 100644 --- a/tools/testing/radix-tree/linux/init.h +++ b/tools/testing/radix-tree/linux/init.h @@ -1 +1 @@ -/* An empty file stub that allows radix-tree.c to compile. */ +#define __init diff --git a/tools/testing/radix-tree/linux/kernel.h b/tools/testing/radix-tree/linux/kernel.h index 9b43b4975d83..b21a77fddcf7 100644 --- a/tools/testing/radix-tree/linux/kernel.h +++ b/tools/testing/radix-tree/linux/kernel.h @@ -1,64 +1,21 @@ #ifndef _KERNEL_H #define _KERNEL_H -#include <assert.h> +#include "../../include/linux/kernel.h" #include <string.h> #include <stdio.h> -#include <stddef.h> #include <limits.h> -#include "../../include/linux/compiler.h" -#include "../../include/linux/err.h" +#include <linux/compiler.h> +#include <linux/err.h> +#include <linux/bitops.h> +#include <linux/log2.h> #include "../../../include/linux/kconfig.h" -#ifdef BENCHMARK -#define RADIX_TREE_MAP_SHIFT 6 -#else -#define RADIX_TREE_MAP_SHIFT 3 -#endif - -#ifndef NULL -#define NULL 0 -#endif - -#define BUG_ON(expr) assert(!(expr)) -#define WARN_ON(expr) assert(!(expr)) -#define __init -#define __must_check -#define panic(expr) #define printk printf -#define __force -#define DIV_ROUND_UP(n,d) (((n) + (d) - 1) / (d)) #define pr_debug printk - -#define smp_rmb() barrier() -#define smp_wmb() barrier() -#define cpu_relax() barrier() +#define pr_cont printk #define ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[0])) -#define container_of(ptr, type, member) ({ \ - const typeof( ((type *)0)->member ) *__mptr = (ptr); \ - (type *)( (char *)__mptr - offsetof(type, member) );}) -#define min(a, b) ((a) < (b) ? (a) : (b)) - -#define cond_resched() sched_yield() - -static inline int in_interrupt(void) -{ - return 0; -} - -/* - * This looks more complex than it should be. But we need to - * get the type for the ~ right in round_down (it needs to be - * as wide as the result!), and we want to evaluate the macro - * arguments just once each. - */ -#define __round_mask(x, y) ((__typeof__(x))((y)-1)) -#define round_up(x, y) ((((x)-1) | __round_mask(x, y))+1) -#define round_down(x, y) ((x) & ~__round_mask(x, y)) - -#define xchg(ptr, x) uatomic_xchg(ptr, x) - #endif /* _KERNEL_H */ diff --git a/tools/testing/radix-tree/linux/mempool.h b/tools/testing/radix-tree/linux/mempool.h deleted file mode 100644 index 6a2dc55b41d6..000000000000 --- a/tools/testing/radix-tree/linux/mempool.h +++ /dev/null @@ -1,16 +0,0 @@ - -#include <linux/slab.h> - -typedef void *(mempool_alloc_t)(int gfp_mask, void *pool_data); -typedef void (mempool_free_t)(void *element, void *pool_data); - -typedef struct { - mempool_alloc_t *alloc; - mempool_free_t *free; - void *data; -} mempool_t; - -void *mempool_alloc(mempool_t *pool, int gfp_mask); -void mempool_free(void *element, mempool_t *pool); -mempool_t *mempool_create(int min_nr, mempool_alloc_t *alloc_fn, - mempool_free_t *free_fn, void *pool_data); diff --git a/tools/testing/radix-tree/linux/percpu.h b/tools/testing/radix-tree/linux/percpu.h index 5837f1d56f17..3ea01a1a88c2 100644 --- a/tools/testing/radix-tree/linux/percpu.h +++ b/tools/testing/radix-tree/linux/percpu.h @@ -1,7 +1,10 @@ - +#define DECLARE_PER_CPU(type, val) extern type val #define DEFINE_PER_CPU(type, val) type val #define __get_cpu_var(var) var #define this_cpu_ptr(var) var +#define this_cpu_read(var) var +#define this_cpu_xchg(var, val) uatomic_xchg(&var, val) +#define this_cpu_cmpxchg(var, old, new) uatomic_cmpxchg(&var, old, new) #define per_cpu_ptr(ptr, cpu) ({ (void)(cpu); (ptr); }) #define per_cpu(var, cpu) (*per_cpu_ptr(&(var), cpu)) diff --git a/tools/testing/radix-tree/linux/preempt.h b/tools/testing/radix-tree/linux/preempt.h index 65c04c226965..35c5ac81529f 100644 --- a/tools/testing/radix-tree/linux/preempt.h +++ b/tools/testing/radix-tree/linux/preempt.h @@ -1,4 +1,14 @@ +#ifndef __LINUX_PREEMPT_H +#define __LINUX_PREEMPT_H + extern int preempt_count; #define preempt_disable() uatomic_inc(&preempt_count) #define preempt_enable() uatomic_dec(&preempt_count) + +static inline int in_interrupt(void) +{ + return 0; +} + +#endif /* __LINUX_PREEMPT_H */ diff --git a/tools/testing/radix-tree/linux/radix-tree.h b/tools/testing/radix-tree/linux/radix-tree.h index ce694ddd4aea..bf1bb231f9b5 100644 --- a/tools/testing/radix-tree/linux/radix-tree.h +++ b/tools/testing/radix-tree/linux/radix-tree.h @@ -1 +1,26 @@ +#ifndef _TEST_RADIX_TREE_H +#define _TEST_RADIX_TREE_H + +#include "generated/map-shift.h" #include "../../../../include/linux/radix-tree.h" + +extern int kmalloc_verbose; +extern int test_verbose; + +static inline void trace_call_rcu(struct rcu_head *head, + void (*func)(struct rcu_head *head)) +{ + if (kmalloc_verbose) + printf("Delaying free of %p to slab\n", (char *)head - + offsetof(struct radix_tree_node, rcu_head)); + call_rcu(head, func); +} + +#define printv(verbosity_level, fmt, ...) \ + if(test_verbose >= verbosity_level) \ + printf(fmt, ##__VA_ARGS__) + +#undef call_rcu +#define call_rcu(x, y) trace_call_rcu(x, y) + +#endif /* _TEST_RADIX_TREE_H */ diff --git a/tools/testing/radix-tree/linux/types.h b/tools/testing/radix-tree/linux/types.h deleted file mode 100644 index 8491d89873bb..000000000000 --- a/tools/testing/radix-tree/linux/types.h +++ /dev/null @@ -1,23 +0,0 @@ -#ifndef _TYPES_H -#define _TYPES_H - -#include "../../include/linux/types.h" - -#define __rcu -#define __read_mostly - -static inline void INIT_LIST_HEAD(struct list_head *list) -{ - list->next = list; - list->prev = list; -} - -typedef struct { - unsigned int x; -} spinlock_t; - -#define uninitialized_var(x) x = x - -#include <linux/gfp.h> - -#endif diff --git a/tools/testing/radix-tree/main.c b/tools/testing/radix-tree/main.c index f7e9801a6754..b829127d5670 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> @@ -67,7 +68,7 @@ void big_gang_check(bool long_run) for (i = 0; i < (long_run ? 1000 : 3); i++) { __big_gang_check(); - printf("%d ", i); + printv(2, "%d ", i); fflush(stdout); } } @@ -128,14 +129,19 @@ void check_copied_tags(struct radix_tree_root *tree, unsigned long start, unsign putchar('.'); */ if (idx[i] < start || idx[i] > end) { if (item_tag_get(tree, idx[i], totag)) { - printf("%lu-%lu: %lu, tags %d-%d\n", start, end, idx[i], item_tag_get(tree, idx[i], fromtag), item_tag_get(tree, idx[i], totag)); + printv(2, "%lu-%lu: %lu, tags %d-%d\n", start, + end, idx[i], item_tag_get(tree, idx[i], + fromtag), + item_tag_get(tree, idx[i], totag)); } assert(!item_tag_get(tree, idx[i], totag)); continue; } if (item_tag_get(tree, idx[i], fromtag) ^ item_tag_get(tree, idx[i], totag)) { - printf("%lu-%lu: %lu, tags %d-%d\n", start, end, idx[i], item_tag_get(tree, idx[i], fromtag), item_tag_get(tree, idx[i], totag)); + printv(2, "%lu-%lu: %lu, tags %d-%d\n", start, end, + idx[i], item_tag_get(tree, idx[i], fromtag), + item_tag_get(tree, idx[i], totag)); } assert(!(item_tag_get(tree, idx[i], fromtag) ^ item_tag_get(tree, idx[i], totag))); @@ -237,7 +243,7 @@ static void __locate_check(struct radix_tree_root *tree, unsigned long index, item = item_lookup(tree, index); index2 = find_item(tree, item); if (index != index2) { - printf("index %ld order %d inserted; found %ld\n", + printv(2, "index %ld order %d inserted; found %ld\n", index, order, index2); abort(); } @@ -288,43 +294,48 @@ static void single_thread_tests(bool long_run) { int i; - printf("starting single_thread_tests: %d allocated, preempt %d\n", + printv(1, "starting single_thread_tests: %d allocated, preempt %d\n", nr_allocated, preempt_count); multiorder_checks(); rcu_barrier(); - printf("after multiorder_check: %d allocated, preempt %d\n", + printv(2, "after multiorder_check: %d allocated, preempt %d\n", nr_allocated, preempt_count); locate_check(); rcu_barrier(); - printf("after locate_check: %d allocated, preempt %d\n", + printv(2, "after locate_check: %d allocated, preempt %d\n", nr_allocated, preempt_count); tag_check(); rcu_barrier(); - printf("after tag_check: %d allocated, preempt %d\n", + printv(2, "after tag_check: %d allocated, preempt %d\n", nr_allocated, preempt_count); gang_check(); rcu_barrier(); - printf("after gang_check: %d allocated, preempt %d\n", + printv(2, "after gang_check: %d allocated, preempt %d\n", nr_allocated, preempt_count); add_and_check(); rcu_barrier(); - printf("after add_and_check: %d allocated, preempt %d\n", + printv(2, "after add_and_check: %d allocated, preempt %d\n", nr_allocated, preempt_count); dynamic_height_check(); rcu_barrier(); - printf("after dynamic_height_check: %d allocated, preempt %d\n", + printv(2, "after dynamic_height_check: %d allocated, preempt %d\n", + nr_allocated, preempt_count); + idr_checks(); + ida_checks(); + rcu_barrier(); + printv(2, "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", + printv(2, "after big_gang_check: %d allocated, preempt %d\n", nr_allocated, preempt_count); for (i = 0; i < (long_run ? 2000 : 3); i++) { copy_tag_check(); - printf("%d ", i); + printv(2, "%d ", i); fflush(stdout); } rcu_barrier(); - printf("after copy_tag_check: %d allocated, preempt %d\n", + printv(2, "after copy_tag_check: %d allocated, preempt %d\n", nr_allocated, preempt_count); } @@ -334,24 +345,28 @@ int main(int argc, char **argv) int opt; unsigned int seed = time(NULL); - while ((opt = getopt(argc, argv, "ls:")) != -1) { + while ((opt = getopt(argc, argv, "ls:v")) != -1) { if (opt == 'l') long_run = true; else if (opt == 's') seed = strtoul(optarg, NULL, 0); + else if (opt == 'v') + test_verbose++; } printf("random seed %u\n", seed); srand(seed); + printf("running tests\n"); + rcu_register_thread(); radix_tree_init(); regression1_test(); regression2_test(); regression3_test(); - iteration_test(0, 10); - iteration_test(7, 20); + iteration_test(0, 10 + 90 * long_run); + iteration_test(7, 10 + 90 * long_run); single_thread_tests(long_run); /* Free any remaining preallocated nodes */ @@ -360,9 +375,11 @@ int main(int argc, char **argv) benchmark(); rcu_barrier(); - printf("after rcu_barrier: %d allocated, preempt %d\n", + printv(2, "after rcu_barrier: %d allocated, preempt %d\n", nr_allocated, preempt_count); rcu_unregister_thread(); + printf("tests completed\n"); + exit(0); } diff --git a/tools/testing/radix-tree/multiorder.c b/tools/testing/radix-tree/multiorder.c index f79812a5e070..06c71178d07d 100644 --- a/tools/testing/radix-tree/multiorder.c +++ b/tools/testing/radix-tree/multiorder.c @@ -30,7 +30,7 @@ static void __multiorder_tag_test(int index, int order) /* our canonical entry */ base = index & ~((1 << order) - 1); - printf("Multiorder tag test with index %d, canonical entry %d\n", + printv(2, "Multiorder tag test with index %d, canonical entry %d\n", index, base); err = item_insert_order(&tree, index, order); @@ -150,7 +150,7 @@ static void multiorder_check(unsigned long index, int order) struct item *item2 = item_create(min, order); RADIX_TREE(tree, GFP_KERNEL); - printf("Multiorder index %ld, order %d\n", index, order); + printv(2, "Multiorder index %ld, order %d\n", index, order); assert(item_insert_order(&tree, index, order) == 0); @@ -188,7 +188,7 @@ static void multiorder_shrink(unsigned long index, int order) RADIX_TREE(tree, GFP_KERNEL); struct radix_tree_node *node; - printf("Multiorder shrink index %ld, order %d\n", index, order); + printv(2, "Multiorder shrink index %ld, order %d\n", index, order); assert(item_insert_order(&tree, 0, order) == 0); @@ -209,7 +209,8 @@ static void multiorder_shrink(unsigned long index, int order) item_check_absent(&tree, i); if (!item_delete(&tree, 0)) { - printf("failed to delete index %ld (order %d)\n", index, order); abort(); + printv(2, "failed to delete index %ld (order %d)\n", index, order); + abort(); } for (i = 0; i < 2*max; i++) @@ -234,7 +235,7 @@ void multiorder_iteration(void) void **slot; int i, j, err; - printf("Multiorder iteration test\n"); + printv(1, "Multiorder iteration test\n"); #define NUM_ENTRIES 11 int index[NUM_ENTRIES] = {0, 2, 4, 8, 16, 32, 34, 36, 64, 72, 128}; @@ -275,7 +276,7 @@ void multiorder_tagged_iteration(void) void **slot; int i, j; - printf("Multiorder tagged iteration test\n"); + printv(1, "Multiorder tagged iteration test\n"); #define MT_NUM_ENTRIES 9 int index[MT_NUM_ENTRIES] = {0, 2, 4, 16, 32, 40, 64, 72, 128}; @@ -355,6 +356,10 @@ void multiorder_tagged_iteration(void) item_kill_tree(&tree); } +/* + * Basic join checks: make sure we can't find an entry in the tree after + * a larger entry has replaced it + */ static void multiorder_join1(unsigned long index, unsigned order1, unsigned order2) { @@ -373,6 +378,10 @@ static void multiorder_join1(unsigned long index, item_kill_tree(&tree); } +/* + * Check that the accounting of exceptional entries is handled correctly + * by joining an exceptional entry to a normal pointer. + */ static void multiorder_join2(unsigned order1, unsigned order2) { RADIX_TREE(tree, GFP_KERNEL); @@ -386,6 +395,9 @@ static void multiorder_join2(unsigned order1, unsigned order2) assert(item2 == (void *)0x12UL); assert(node->exceptional == 1); + item2 = radix_tree_lookup(&tree, 0); + free(item2); + radix_tree_join(&tree, 0, order1, item1); item2 = __radix_tree_lookup(&tree, 1 << order2, &node, NULL); assert(item2 == item1); @@ -453,7 +465,7 @@ static void check_mem(unsigned old_order, unsigned new_order, unsigned alloc) { struct radix_tree_preload *rtp = &radix_tree_preloads; if (rtp->nr != 0) - printf("split(%u %u) remaining %u\n", old_order, new_order, + printv(2, "split(%u %u) remaining %u\n", old_order, new_order, rtp->nr); /* * Can't check for equality here as some nodes may have been @@ -461,7 +473,7 @@ static void check_mem(unsigned old_order, unsigned new_order, unsigned alloc) * nodes allocated since they should have all been preloaded. */ if (nr_allocated > alloc) - printf("split(%u %u) allocated %u %u\n", old_order, new_order, + printv(2, "split(%u %u) allocated %u %u\n", old_order, new_order, alloc, nr_allocated); } @@ -471,6 +483,7 @@ static void __multiorder_split(int old_order, int new_order) void **slot; struct radix_tree_iter iter; unsigned alloc; + struct item *item; radix_tree_preload(GFP_KERNEL); assert(item_insert_order(&tree, 0, old_order) == 0); @@ -479,7 +492,7 @@ static void __multiorder_split(int old_order, int new_order) /* Wipe out the preloaded cache or it'll confuse check_mem() */ radix_tree_cpu_dead(0); - radix_tree_tag_set(&tree, 0, 2); + item = radix_tree_tag_set(&tree, 0, 2); radix_tree_split_preload(old_order, new_order, GFP_KERNEL); alloc = nr_allocated; @@ -492,6 +505,7 @@ static void __multiorder_split(int old_order, int new_order) radix_tree_preload_end(); item_kill_tree(&tree); + free(item); } static void __multiorder_split2(int old_order, int new_order) @@ -633,3 +647,10 @@ void multiorder_checks(void) radix_tree_cpu_dead(0); } + +int __weak main(void) +{ + radix_tree_init(); + multiorder_checks(); + return 0; +} diff --git a/tools/testing/radix-tree/regression1.c b/tools/testing/radix-tree/regression1.c index 0d6813a61b37..bf97742fc18c 100644 --- a/tools/testing/radix-tree/regression1.c +++ b/tools/testing/radix-tree/regression1.c @@ -193,7 +193,7 @@ void regression1_test(void) long arg; /* Regression #1 */ - printf("running regression test 1, should finish in under a minute\n"); + printv(1, "running regression test 1, should finish in under a minute\n"); nr_threads = 2; pthread_barrier_init(&worker_barrier, NULL, nr_threads); @@ -216,5 +216,5 @@ void regression1_test(void) free(threads); - printf("regression test 1, done\n"); + printv(1, "regression test 1, done\n"); } diff --git a/tools/testing/radix-tree/regression2.c b/tools/testing/radix-tree/regression2.c index a41325d7a170..42dd2a33ed24 100644 --- a/tools/testing/radix-tree/regression2.c +++ b/tools/testing/radix-tree/regression2.c @@ -80,7 +80,7 @@ void regression2_test(void) unsigned long int start, end; struct page *pages[1]; - printf("running regression test 2 (should take milliseconds)\n"); + printv(1, "running regression test 2 (should take milliseconds)\n"); /* 0. */ for (i = 0; i <= max_slots - 1; i++) { p = page_alloc(); @@ -103,7 +103,7 @@ void regression2_test(void) /* 4. */ for (i = max_slots - 1; i >= 0; i--) - radix_tree_delete(&mt_tree, i); + free(radix_tree_delete(&mt_tree, i)); /* 5. */ // NOTE: start should not be 0 because radix_tree_gang_lookup_tag_slot @@ -114,7 +114,9 @@ void regression2_test(void) PAGECACHE_TAG_TOWRITE); /* We remove all the remained nodes */ - radix_tree_delete(&mt_tree, max_slots); + free(radix_tree_delete(&mt_tree, max_slots)); - printf("regression test 2, done\n"); + BUG_ON(!radix_tree_empty(&mt_tree)); + + printv(1, "regression test 2, done\n"); } diff --git a/tools/testing/radix-tree/regression3.c b/tools/testing/radix-tree/regression3.c index b594841fae85..670c3d2ae7b1 100644 --- a/tools/testing/radix-tree/regression3.c +++ b/tools/testing/radix-tree/regression3.c @@ -34,21 +34,21 @@ void regression3_test(void) void **slot; bool first; - printf("running regression test 3 (should take milliseconds)\n"); + printv(1, "running regression test 3 (should take milliseconds)\n"); radix_tree_insert(&root, 0, ptr0); radix_tree_tag_set(&root, 0, 0); first = true; radix_tree_for_each_tagged(slot, &root, &iter, 0, 0) { - printf("tagged %ld %p\n", iter.index, *slot); + printv(2, "tagged %ld %p\n", iter.index, *slot); if (first) { radix_tree_insert(&root, 1, ptr); radix_tree_tag_set(&root, 1, 0); first = false; } if (radix_tree_deref_retry(*slot)) { - printf("retry at %ld\n", iter.index); + printv(2, "retry at %ld\n", iter.index); slot = radix_tree_iter_retry(&iter); continue; } @@ -57,13 +57,13 @@ void regression3_test(void) first = true; radix_tree_for_each_slot(slot, &root, &iter, 0) { - printf("slot %ld %p\n", iter.index, *slot); + printv(2, "slot %ld %p\n", iter.index, *slot); if (first) { radix_tree_insert(&root, 1, ptr); first = false; } if (radix_tree_deref_retry(*slot)) { - printk("retry at %ld\n", iter.index); + printv(2, "retry at %ld\n", iter.index); slot = radix_tree_iter_retry(&iter); continue; } @@ -72,30 +72,30 @@ void regression3_test(void) first = true; radix_tree_for_each_contig(slot, &root, &iter, 0) { - printk("contig %ld %p\n", iter.index, *slot); + printv(2, "contig %ld %p\n", iter.index, *slot); if (first) { radix_tree_insert(&root, 1, ptr); first = false; } if (radix_tree_deref_retry(*slot)) { - printk("retry at %ld\n", iter.index); + printv(2, "retry at %ld\n", iter.index); slot = radix_tree_iter_retry(&iter); continue; } } radix_tree_for_each_slot(slot, &root, &iter, 0) { - printf("slot %ld %p\n", iter.index, *slot); + printv(2, "slot %ld %p\n", iter.index, *slot); if (!iter.index) { - printf("next at %ld\n", iter.index); + printv(2, "next at %ld\n", iter.index); slot = radix_tree_iter_resume(slot, &iter); } } radix_tree_for_each_contig(slot, &root, &iter, 0) { - printf("contig %ld %p\n", iter.index, *slot); + printv(2, "contig %ld %p\n", iter.index, *slot); if (!iter.index) { - printf("next at %ld\n", iter.index); + printv(2, "next at %ld\n", iter.index); slot = radix_tree_iter_resume(slot, &iter); } } @@ -103,9 +103,9 @@ void regression3_test(void) radix_tree_tag_set(&root, 0, 0); radix_tree_tag_set(&root, 1, 0); radix_tree_for_each_tagged(slot, &root, &iter, 0, 0) { - printf("tagged %ld %p\n", iter.index, *slot); + printv(2, "tagged %ld %p\n", iter.index, *slot); if (!iter.index) { - printf("next at %ld\n", iter.index); + printv(2, "next at %ld\n", iter.index); slot = radix_tree_iter_resume(slot, &iter); } } @@ -113,5 +113,5 @@ void regression3_test(void) radix_tree_delete(&root, 0); radix_tree_delete(&root, 1); - printf("regression test 3 passed\n"); + printv(1, "regression test 3 passed\n"); } diff --git a/tools/testing/radix-tree/tag_check.c b/tools/testing/radix-tree/tag_check.c index fd98c132207a..d4ff00989245 100644 --- a/tools/testing/radix-tree/tag_check.c +++ b/tools/testing/radix-tree/tag_check.c @@ -49,10 +49,10 @@ void simple_checks(void) } verify_tag_consistency(&tree, 0); verify_tag_consistency(&tree, 1); - printf("before item_kill_tree: %d allocated\n", nr_allocated); + printv(2, "before item_kill_tree: %d allocated\n", nr_allocated); item_kill_tree(&tree); rcu_barrier(); - printf("after item_kill_tree: %d allocated\n", nr_allocated); + printv(2, "after item_kill_tree: %d allocated\n", nr_allocated); } /* @@ -257,7 +257,7 @@ static void do_thrash(struct radix_tree_root *tree, char *thrash_state, int tag) gang_check(tree, thrash_state, tag); - printf("%d(%d) %d(%d) %d(%d) %d(%d) / " + printv(2, "%d(%d) %d(%d) %d(%d) %d(%d) / " "%d(%d) present, %d(%d) tagged\n", insert_chunk, nr_inserted, delete_chunk, nr_deleted, @@ -296,13 +296,13 @@ static void __leak_check(void) { RADIX_TREE(tree, GFP_KERNEL); - printf("%d: nr_allocated=%d\n", __LINE__, nr_allocated); + printv(2, "%d: nr_allocated=%d\n", __LINE__, nr_allocated); item_insert(&tree, 1000000); - printf("%d: nr_allocated=%d\n", __LINE__, nr_allocated); + printv(2, "%d: nr_allocated=%d\n", __LINE__, nr_allocated); item_delete(&tree, 1000000); - printf("%d: nr_allocated=%d\n", __LINE__, nr_allocated); + printv(2, "%d: nr_allocated=%d\n", __LINE__, nr_allocated); item_kill_tree(&tree); - printf("%d: nr_allocated=%d\n", __LINE__, nr_allocated); + printv(2, "%d: nr_allocated=%d\n", __LINE__, nr_allocated); } static void single_check(void) @@ -336,15 +336,15 @@ void tag_check(void) extend_checks(); contract_checks(); rcu_barrier(); - printf("after extend_checks: %d allocated\n", nr_allocated); + printv(2, "after extend_checks: %d allocated\n", nr_allocated); __leak_check(); leak_check(); rcu_barrier(); - printf("after leak_check: %d allocated\n", nr_allocated); + printv(2, "after leak_check: %d allocated\n", nr_allocated); simple_checks(); rcu_barrier(); - printf("after simple_checks: %d allocated\n", nr_allocated); + printv(2, "after simple_checks: %d allocated\n", nr_allocated); thrash_tags(); rcu_barrier(); - printf("after thrash_tags: %d allocated\n", nr_allocated); + printv(2, "after thrash_tags: %d allocated\n", nr_allocated); } diff --git a/tools/testing/radix-tree/test.c b/tools/testing/radix-tree/test.c index e5726e373646..1a257d738a1e 100644 --- a/tools/testing/radix-tree/test.c +++ b/tools/testing/radix-tree/test.c @@ -29,15 +29,28 @@ int __item_insert(struct radix_tree_root *root, struct item *item) return __radix_tree_insert(root, item->index, item->order, item); } -int item_insert(struct radix_tree_root *root, unsigned long index) +struct item *item_create(unsigned long index, unsigned int order) { - return __item_insert(root, item_create(index, 0)); + struct item *ret = malloc(sizeof(*ret)); + + ret->index = index; + ret->order = order; + return ret; } int item_insert_order(struct radix_tree_root *root, unsigned long index, unsigned order) { - return __item_insert(root, item_create(index, order)); + struct item *item = item_create(index, order); + int err = __item_insert(root, item); + if (err) + free(item); + return err; +} + +int item_insert(struct radix_tree_root *root, unsigned long index) +{ + return item_insert_order(root, index, 0); } void item_sanity(struct item *item, unsigned long index) @@ -61,15 +74,6 @@ int item_delete(struct radix_tree_root *root, unsigned long index) return 0; } -struct item *item_create(unsigned long index, unsigned int order) -{ - struct item *ret = malloc(sizeof(*ret)); - - ret->index = index; - ret->order = order; - return ret; -} - void item_check_present(struct radix_tree_root *root, unsigned long index) { struct item *item; 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); |