From 0a835c4f090af2c76fc2932c539c3b32fd21fbbb Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Tue, 20 Dec 2016 10:27:56 -0500 Subject: Reimplement IDR and IDA using the radix tree The IDR is very similar to the radix tree. It has some functionality that the radix tree did not have (alloc next free, cyclic allocation, a callback-based for_each, destroy tree), which is readily implementable on top of the radix tree. A few small changes were needed in order to use a tag to represent nodes with free space below them. More extensive changes were needed to support storing NULL as a valid entry in an IDR. Plain radix trees still interpret NULL as a not-present entry. The IDA is reimplemented as a client of the newly enhanced radix tree. As in the current implementation, it uses a bitmap at the last level of the tree. Signed-off-by: Matthew Wilcox Signed-off-by: Matthew Wilcox Tested-by: Kirill A. Shutemov Cc: Konstantin Khlebnikov Cc: Ross Zwisler Cc: Tejun Heo Signed-off-by: Andrew Morton --- tools/testing/radix-tree/idr-test.c | 342 ++++++++++++++++++++++++++++++++++++ 1 file changed, 342 insertions(+) create mode 100644 tools/testing/radix-tree/idr-test.c (limited to 'tools/testing/radix-tree/idr-test.c') diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr-test.c new file mode 100644 index 000000000000..4dffad9284e0 --- /dev/null +++ b/tools/testing/radix-tree/idr-test.c @@ -0,0 +1,342 @@ +/* + * idr-test.c: Test the IDR API + * Copyright (c) 2016 Matthew Wilcox + * + * 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 +#include +#include +#include + +#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(&ida, &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 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_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(); + + radix_tree_cpu_dead(1); +} -- cgit v1.2.3 From d37cacc5adace7f3e0824e1f559192ad7299d029 Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Sat, 17 Dec 2016 08:18:17 -0500 Subject: ida: Use exceptional entries for small IDAs We can use the root entry as a bitmap and save allocating a 128 byte bitmap for an IDA that contains only a few entries (30 on a 32-bit machine, 62 on a 64-bit machine). This costs about 300 bytes of kernel text on x86-64, so as long as 3 IDAs fall into this category, this is a net win for memory consumption. Thanks to Rasmus Villemoes for his work documenting the problem and collecting statistics on IDAs. Signed-off-by: Matthew Wilcox --- lib/idr.c | 87 +++++++++++++++++++++++++++++++--- lib/radix-tree.c | 8 ++++ tools/testing/radix-tree/idr-test.c | 93 ++++++++++++++++++++++++++++++++++++- 3 files changed, 181 insertions(+), 7 deletions(-) (limited to 'tools/testing/radix-tree/idr-test.c') diff --git a/lib/idr.c b/lib/idr.c index 2abd7769c430..7d25e240bc5a 100644 --- a/lib/idr.c +++ b/lib/idr.c @@ -194,6 +194,39 @@ EXPORT_SYMBOL(idr_replace); * limitation, it should be quite straightforward to raise the maximum. */ +/* + * Developer's notes: + * + * The IDA uses the functionality provided by the IDR & radix tree to store + * bitmaps in each entry. The IDR_FREE tag means there is at least one bit + * free, unlike the IDR where it means at least one entry is free. + * + * I considered telling the radix tree that each slot is an order-10 node + * and storing the bit numbers in the radix tree, but the radix tree can't + * allow a single multiorder entry at index 0, which would significantly + * increase memory consumption for the IDA. So instead we divide the index + * by the number of bits in the leaf bitmap before doing a radix tree lookup. + * + * As an optimisation, if there are only a few low bits set in any given + * leaf, instead of allocating a 128-byte bitmap, we use the 'exceptional + * entry' functionality of the radix tree to store BITS_PER_LONG - 2 bits + * directly in the entry. By being really tricksy, we could store + * BITS_PER_LONG - 1 bits, but there're diminishing returns after optimising + * for 0-3 allocated IDs. + * + * We allow the radix tree 'exceptional' count to get out of date. Nothing + * in the IDA nor the radix tree code checks it. If it becomes important + * to maintain an accurate exceptional count, switch the rcu_assign_pointer() + * calls to radix_tree_iter_replace() which will correct the exceptional + * count. + * + * The IDA always requires a lock to alloc/free. If we add a 'test_bit' + * equivalent, it will still need locking. Going to RCU lookup would require + * using RCU to free bitmaps, and that's not trivial without embedding an + * RCU head in the bitmap, which adds a 2-pointer overhead to each 128-byte + * bitmap, which is excessive. + */ + #define IDA_MAX (0x80000000U / IDA_BITMAP_BITS) /** @@ -221,11 +254,12 @@ int ida_get_new_above(struct ida *ida, int start, int *id) struct radix_tree_iter iter; struct ida_bitmap *bitmap; unsigned long index; - unsigned bit; + unsigned bit, ebit; int new; index = start / IDA_BITMAP_BITS; bit = start % IDA_BITMAP_BITS; + ebit = bit + RADIX_TREE_EXCEPTIONAL_SHIFT; slot = radix_tree_iter_init(&iter, index); for (;;) { @@ -240,10 +274,29 @@ int ida_get_new_above(struct ida *ida, int start, int *id) return PTR_ERR(slot); } } - if (iter.index > index) + if (iter.index > index) { bit = 0; + ebit = RADIX_TREE_EXCEPTIONAL_SHIFT; + } new = iter.index * IDA_BITMAP_BITS; bitmap = rcu_dereference_raw(*slot); + if (radix_tree_exception(bitmap)) { + unsigned long tmp = (unsigned long)bitmap; + ebit = find_next_zero_bit(&tmp, BITS_PER_LONG, ebit); + if (ebit < BITS_PER_LONG) { + tmp |= 1UL << ebit; + rcu_assign_pointer(*slot, (void *)tmp); + *id = new + ebit - RADIX_TREE_EXCEPTIONAL_SHIFT; + return 0; + } + bitmap = this_cpu_xchg(ida_bitmap, NULL); + if (!bitmap) + return -EAGAIN; + memset(bitmap, 0, sizeof(*bitmap)); + bitmap->bitmap[0] = tmp >> RADIX_TREE_EXCEPTIONAL_SHIFT; + rcu_assign_pointer(*slot, bitmap); + } + if (bitmap) { bit = find_next_zero_bit(bitmap->bitmap, IDA_BITMAP_BITS, bit); @@ -261,6 +314,14 @@ int ida_get_new_above(struct ida *ida, int start, int *id) new += bit; if (new < 0) return -ENOSPC; + if (ebit < BITS_PER_LONG) { + bitmap = (void *)((1UL << ebit) | + RADIX_TREE_EXCEPTIONAL_ENTRY); + radix_tree_iter_replace(root, &iter, slot, + bitmap); + *id = new; + return 0; + } bitmap = this_cpu_xchg(ida_bitmap, NULL); if (!bitmap) return -EAGAIN; @@ -287,6 +348,7 @@ void ida_remove(struct ida *ida, int id) unsigned long index = id / IDA_BITMAP_BITS; unsigned offset = id % IDA_BITMAP_BITS; struct ida_bitmap *bitmap; + unsigned long *btmp; struct radix_tree_iter iter; void **slot; @@ -295,12 +357,24 @@ void ida_remove(struct ida *ida, int id) goto err; bitmap = rcu_dereference_raw(*slot); - if (!test_bit(offset, bitmap->bitmap)) + if (radix_tree_exception(bitmap)) { + btmp = (unsigned long *)slot; + offset += RADIX_TREE_EXCEPTIONAL_SHIFT; + if (offset >= BITS_PER_LONG) + goto err; + } else { + btmp = bitmap->bitmap; + } + if (!test_bit(offset, btmp)) goto err; - __clear_bit(offset, bitmap->bitmap); + __clear_bit(offset, btmp); radix_tree_iter_tag_set(&ida->ida_rt, &iter, IDR_FREE); - if (bitmap_empty(bitmap->bitmap, IDA_BITMAP_BITS)) { + if (radix_tree_exception(bitmap)) { + if (rcu_dereference_raw(*slot) == + (void *)RADIX_TREE_EXCEPTIONAL_ENTRY) + radix_tree_iter_delete(&ida->ida_rt, &iter, slot); + } else if (bitmap_empty(btmp, IDA_BITMAP_BITS)) { kfree(bitmap); radix_tree_iter_delete(&ida->ida_rt, &iter, slot); } @@ -326,7 +400,8 @@ void ida_destroy(struct ida *ida) radix_tree_for_each_slot(slot, &ida->ida_rt, &iter, 0) { struct ida_bitmap *bitmap = rcu_dereference_raw(*slot); - kfree(bitmap); + if (!radix_tree_exception(bitmap)) + kfree(bitmap); radix_tree_iter_delete(&ida->ida_rt, &iter, slot); } } diff --git a/lib/radix-tree.c b/lib/radix-tree.c index 7b9f8515033e..14130ab197c0 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c @@ -338,6 +338,14 @@ static void dump_ida_node(void *entry, unsigned long index) for (i = 0; i < RADIX_TREE_MAP_SIZE; i++) dump_ida_node(node->slots[i], index | (i << node->shift)); + } else if (radix_tree_exceptional_entry(entry)) { + pr_debug("ida excp: %p offset %d indices %lu-%lu data %lx\n", + entry, (int)(index & RADIX_TREE_MAP_MASK), + index * IDA_BITMAP_BITS, + index * IDA_BITMAP_BITS + BITS_PER_LONG - + RADIX_TREE_EXCEPTIONAL_SHIFT, + (unsigned long)entry >> + RADIX_TREE_EXCEPTIONAL_SHIFT); } else { struct ida_bitmap *bitmap = entry; diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr-test.c index 4dffad9284e0..59081122c63d 100644 --- a/tools/testing/radix-tree/idr-test.c +++ b/tools/testing/radix-tree/idr-test.c @@ -11,6 +11,7 @@ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for * more details. */ +#include #include #include #include @@ -214,7 +215,7 @@ void ida_check_nomem(void) DEFINE_IDA(ida); int id, err; - err = ida_get_new(&ida, &id); + err = ida_get_new_above(&ida, 256, &id); assert(err == -EAGAIN); err = ida_get_new_above(&ida, 1UL << 30, &id); assert(err == -EAGAIN); @@ -246,6 +247,66 @@ void ida_check_leaf(void) 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 @@ -273,6 +334,34 @@ void ida_check_max(void) } } +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); @@ -337,6 +426,8 @@ void ida_checks(void) ida_check_leaf(); ida_check_max(); + ida_check_conv(); + ida_check_random(); radix_tree_cpu_dead(1); } -- cgit v1.2.3 From 8ac04868315c6ffcb2c5a5ad9cd5cec61cad3576 Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Sun, 18 Dec 2016 22:56:05 -0500 Subject: radix tree test suite: Build separate binaries for some tests To allow developers to run a subset of tests, build separate multiorder and idr-test binaries which will run just the tests in those files. Signed-off-by: Matthew Wilcox Reviewed-by: Rehas Sachdeva --- tools/testing/radix-tree/.gitignore | 4 +++- tools/testing/radix-tree/Makefile | 18 ++++++++++++------ tools/testing/radix-tree/idr-test.c | 11 +++++++++++ tools/testing/radix-tree/multiorder.c | 7 +++++++ 4 files changed, 33 insertions(+), 7 deletions(-) (limited to 'tools/testing/radix-tree/idr-test.c') diff --git a/tools/testing/radix-tree/.gitignore b/tools/testing/radix-tree/.gitignore index 3b5534b643f0..26dedaf57aab 100644 --- a/tools/testing/radix-tree/.gitignore +++ b/tools/testing/radix-tree/.gitignore @@ -1,3 +1,5 @@ +idr.c +idr-test main +multiorder radix-tree.c -idr.c diff --git a/tools/testing/radix-tree/Makefile b/tools/testing/radix-tree/Makefile index 3597a3a9f269..4aba7b75e43a 100644 --- a/tools/testing/radix-tree/Makefile +++ b/tools/testing/radix-tree/Makefile @@ -1,10 +1,10 @@ CFLAGS += -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE LDFLAGS += -lpthread -lurcu -TARGETS = main -OFILES = main.o radix-tree.o idr.o linux.o test.o tag_check.o find_bit.o \ - regression1.o regression2.o regression3.o multiorder.o idr-test.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 @@ -13,10 +13,16 @@ endif targets: $(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 vpath %.c ../../lib diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr-test.c index 59081122c63d..a26098c6123d 100644 --- a/tools/testing/radix-tree/idr-test.c +++ b/tools/testing/radix-tree/idr-test.c @@ -431,3 +431,14 @@ void ida_checks(void) 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/multiorder.c b/tools/testing/radix-tree/multiorder.c index f79812a5e070..e465a3811b97 100644 --- a/tools/testing/radix-tree/multiorder.c +++ b/tools/testing/radix-tree/multiorder.c @@ -633,3 +633,10 @@ void multiorder_checks(void) radix_tree_cpu_dead(0); } + +int __weak main(void) +{ + radix_tree_init(); + multiorder_checks(); + return 0; +} -- cgit v1.2.3