summaryrefslogtreecommitdiff
path: root/tools
diff options
context:
space:
mode:
Diffstat (limited to 'tools')
-rw-r--r--tools/include/asm-generic/bitops/atomic.h3
-rw-r--r--tools/include/asm/bug.h8
-rw-r--r--tools/include/linux/bitmap.h1
-rw-r--r--tools/include/linux/bitops.h1
-rw-r--r--tools/include/linux/compiler.h4
-rw-r--r--tools/include/linux/spinlock.h5
-rw-r--r--tools/testing/radix-tree/.gitignore4
-rw-r--r--tools/testing/radix-tree/Makefile46
-rw-r--r--tools/testing/radix-tree/benchmark.c6
-rw-r--r--tools/testing/radix-tree/generated/autoconf.h2
-rw-r--r--tools/testing/radix-tree/idr-test.c444
-rw-r--r--tools/testing/radix-tree/iteration_check.c2
-rw-r--r--tools/testing/radix-tree/linux.c39
-rw-r--r--tools/testing/radix-tree/linux/bitops.h160
-rw-r--r--tools/testing/radix-tree/linux/bitops/__ffs.h43
-rw-r--r--tools/testing/radix-tree/linux/bitops/ffs.h41
-rw-r--r--tools/testing/radix-tree/linux/bitops/ffz.h12
-rw-r--r--tools/testing/radix-tree/linux/bitops/find.h13
-rw-r--r--tools/testing/radix-tree/linux/bitops/fls.h41
-rw-r--r--tools/testing/radix-tree/linux/bitops/fls64.h14
-rw-r--r--tools/testing/radix-tree/linux/bitops/hweight.h11
-rw-r--r--tools/testing/radix-tree/linux/bitops/le.h53
-rw-r--r--tools/testing/radix-tree/linux/bitops/non-atomic.h110
-rw-r--r--tools/testing/radix-tree/linux/export.h2
-rw-r--r--tools/testing/radix-tree/linux/gfp.h10
-rw-r--r--tools/testing/radix-tree/linux/idr.h1
-rw-r--r--tools/testing/radix-tree/linux/init.h2
-rw-r--r--tools/testing/radix-tree/linux/kernel.h55
-rw-r--r--tools/testing/radix-tree/linux/mempool.h16
-rw-r--r--tools/testing/radix-tree/linux/percpu.h5
-rw-r--r--tools/testing/radix-tree/linux/preempt.h10
-rw-r--r--tools/testing/radix-tree/linux/radix-tree.h25
-rw-r--r--tools/testing/radix-tree/linux/types.h23
-rw-r--r--tools/testing/radix-tree/main.c53
-rw-r--r--tools/testing/radix-tree/multiorder.c39
-rw-r--r--tools/testing/radix-tree/regression1.c4
-rw-r--r--tools/testing/radix-tree/regression2.c10
-rw-r--r--tools/testing/radix-tree/regression3.c28
-rw-r--r--tools/testing/radix-tree/tag_check.c22
-rw-r--r--tools/testing/radix-tree/test.c28
-rw-r--r--tools/testing/radix-tree/test.h2
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);