diff options
author | Linus Torvalds <torvalds@linux-foundation.org> | 2017-02-28 20:29:41 -0800 |
---|---|---|
committer | Linus Torvalds <torvalds@linux-foundation.org> | 2017-02-28 20:29:41 -0800 |
commit | cf393195c3ba5d4c0a8e237eb00f7ef104876ee5 (patch) | |
tree | 8aa515ca0e0c00bffbc8dccb9d36ea319f251a12 /tools/testing | |
parent | 5ecc5ac215bc4d88243a2f4909e70ccc1bda710f (diff) | |
parent | c6ce3e2fe3dacda5e8afb0036c814ae9c3fee9b9 (diff) |
Merge branch 'idr-4.11' of git://git.infradead.org/users/willy/linux-dax
Pull IDR rewrite from Matthew Wilcox:
"The most significant part of the following is the patch to rewrite the
IDR & IDA to be clients of the radix tree. But there's much more,
including an enhancement of the IDA to be significantly more space
efficient, an IDR & IDA test suite, some improvements to the IDR API
(and driver changes to take advantage of those improvements), several
improvements to the radix tree test suite and RCU annotations.
The IDR & IDA rewrite had a good spin in linux-next and Andrew's tree
for most of the last cycle. Coupled with the IDR test suite, I feel
pretty confident that any remaining bugs are quite hard to hit. 0-day
did a great job of watching my git tree and pointing out problems; as
it hit them, I added new test-cases to be sure not to be caught the
same way twice"
Willy goes on to expand a bit on the IDR rewrite rationale:
"The radix tree and the IDR use very similar data structures.
Merging the two codebases lets us share the memory allocation pools,
and results in a net deletion of 500 lines of code. It also opens up
the possibility of exposing more of the features of the radix tree to
users of the IDR (and I have some interesting patches along those
lines waiting for 4.12)
It also shrinks the size of the 'struct idr' from 40 bytes to 24 which
will shrink a fair few data structures that embed an IDR"
* 'idr-4.11' of git://git.infradead.org/users/willy/linux-dax: (32 commits)
radix tree test suite: Add config option for map shift
idr: Add missing __rcu annotations
radix-tree: Fix __rcu annotations
radix-tree: Add rcu_dereference and rcu_assign_pointer calls
radix tree test suite: Run iteration tests for longer
radix tree test suite: Fix split/join memory leaks
radix tree test suite: Fix leaks in regression2.c
radix tree test suite: Fix leaky tests
radix tree test suite: Enable address sanitizer
radix_tree_iter_resume: Fix out of bounds error
radix-tree: Store a pointer to the root in each node
radix-tree: Chain preallocated nodes through ->parent
radix tree test suite: Dial down verbosity with -v
radix tree test suite: Introduce kmalloc_verbose
idr: Return the deleted entry from idr_remove
radix tree test suite: Build separate binaries for some tests
ida: Use exceptional entries for small IDAs
ida: Move ida_bitmap to a percpu variable
Reimplement IDR and IDA using the radix tree
radix-tree: Add radix_tree_iter_delete
...
Diffstat (limited to 'tools/testing')
35 files changed, 668 insertions, 708 deletions
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; |