From c68a2aab3300df4106f368568bd7361d6f465993 Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Fri, 16 Dec 2016 11:52:43 -0500 Subject: radix tree test suite: Remove duplicate bitops code By adding __set_bit and __clear_bit to the tools include directory, we can share the bitops code. This reveals an include loop between kernel.h, log2.h, bitmap.h and bitops.h. Break it the same way as the kernel does; by moving the kernel.h include from bitops.h to bitmap.h. Signed-off-by: Matthew Wilcox --- tools/testing/radix-tree/linux/kernel.h | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-) (limited to 'tools/testing/radix-tree/linux/kernel.h') diff --git a/tools/testing/radix-tree/linux/kernel.h b/tools/testing/radix-tree/linux/kernel.h index 9b43b4975d83..1cd72a84a089 100644 --- a/tools/testing/radix-tree/linux/kernel.h +++ b/tools/testing/radix-tree/linux/kernel.h @@ -7,8 +7,10 @@ #include #include -#include "../../include/linux/compiler.h" -#include "../../include/linux/err.h" +#include +#include +#include +#include #include "../../../include/linux/kconfig.h" #ifdef BENCHMARK -- cgit v1.2.1 From b246a9d2671f4f6cfab3f98199568e0b3028f6e5 Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Mon, 19 Dec 2016 11:07:17 -0500 Subject: tools: Provide a definition of WARN_ON The definition of WARN_ON being used by the radix tree test suite was deficient in two ways: it did not provide a return value, and it stopped execution instead of continuing. This version of WARN_ON tells you which file & line the assertion was triggered in. Signed-off-by: Matthew Wilcox --- tools/testing/radix-tree/linux/kernel.h | 1 - 1 file changed, 1 deletion(-) (limited to 'tools/testing/radix-tree/linux/kernel.h') diff --git a/tools/testing/radix-tree/linux/kernel.h b/tools/testing/radix-tree/linux/kernel.h index 1cd72a84a089..9681463c91e2 100644 --- a/tools/testing/radix-tree/linux/kernel.h +++ b/tools/testing/radix-tree/linux/kernel.h @@ -24,7 +24,6 @@ #endif #define BUG_ON(expr) assert(!(expr)) -#define WARN_ON(expr) assert(!(expr)) #define __init #define __must_check #define panic(expr) -- cgit v1.2.1 From ab3a1ffd11d90583c71bd606bf0fd5bfef30bce9 Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Fri, 16 Dec 2016 15:11:05 -0500 Subject: radix tree test suite: Reduce kernel.h Many of the definitions in the radix-tree kernel.h are redundant with others in tools/include, or are no longer used, such as panic(). Move the definition of __init to init.h and in_interrupt() to preempt.h Signed-off-by: Matthew Wilcox --- tools/testing/radix-tree/linux/kernel.h | 39 +-------------------------------- 1 file changed, 1 insertion(+), 38 deletions(-) (limited to 'tools/testing/radix-tree/linux/kernel.h') diff --git a/tools/testing/radix-tree/linux/kernel.h b/tools/testing/radix-tree/linux/kernel.h index 9681463c91e2..dd1d9aefb14f 100644 --- a/tools/testing/radix-tree/linux/kernel.h +++ b/tools/testing/radix-tree/linux/kernel.h @@ -1,10 +1,9 @@ #ifndef _KERNEL_H #define _KERNEL_H -#include +#include "../../include/linux/kernel.h" #include #include -#include #include #include @@ -19,47 +18,11 @@ #define RADIX_TREE_MAP_SHIFT 3 #endif -#ifndef NULL -#define NULL 0 -#endif - -#define BUG_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 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 */ -- cgit v1.2.1 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/linux/kernel.h | 1 + 1 file changed, 1 insertion(+) (limited to 'tools/testing/radix-tree/linux/kernel.h') diff --git a/tools/testing/radix-tree/linux/kernel.h b/tools/testing/radix-tree/linux/kernel.h index dd1d9aefb14f..63fce553781a 100644 --- a/tools/testing/radix-tree/linux/kernel.h +++ b/tools/testing/radix-tree/linux/kernel.h @@ -20,6 +20,7 @@ #define printk printf #define pr_debug printk +#define pr_cont printk #define ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[0])) -- cgit v1.2.1 From 7ad3d4d85c7af9632055a6ac0aa15b6b6a321c6b Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Fri, 16 Dec 2016 11:55:56 -0500 Subject: ida: Move ida_bitmap to a percpu variable When we preload the IDA, we allocate an IDA bitmap. Instead of storing that preallocated bitmap in the IDA, we store it in a percpu variable. Generally there are more IDAs in the system than CPUs, so this cuts down on the number of preallocated bitmaps that are unused, and about half of the IDA users did not call ida_destroy() so they were leaking IDA bitmaps. Signed-off-by: Matthew Wilcox --- tools/testing/radix-tree/linux/kernel.h | 2 -- 1 file changed, 2 deletions(-) (limited to 'tools/testing/radix-tree/linux/kernel.h') diff --git a/tools/testing/radix-tree/linux/kernel.h b/tools/testing/radix-tree/linux/kernel.h index 63fce553781a..677b8c0f60f9 100644 --- a/tools/testing/radix-tree/linux/kernel.h +++ b/tools/testing/radix-tree/linux/kernel.h @@ -24,6 +24,4 @@ #define ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[0])) -#define xchg(ptr, x) uatomic_xchg(ptr, x) - #endif /* _KERNEL_H */ -- cgit v1.2.1 From c6ce3e2fe3dacda5e8afb0036c814ae9c3fee9b9 Mon Sep 17 00:00:00 2001 From: Rehas Sachdeva Date: Mon, 13 Feb 2017 16:16:03 -0500 Subject: radix tree test suite: Add config option for map shift Add config option "SHIFT=" to Makefile for building test suite with any value of RADIX_TREE_MAP_SHIFT between 3 and 7 inclusive. Signed-off-by: Rehas Sachdeva [mawilcox@microsoft.com: .gitignore, quieten grep, remove on clean] Signed-off-by: Matthew Wilcox --- tools/testing/radix-tree/linux/kernel.h | 6 ------ 1 file changed, 6 deletions(-) (limited to 'tools/testing/radix-tree/linux/kernel.h') diff --git a/tools/testing/radix-tree/linux/kernel.h b/tools/testing/radix-tree/linux/kernel.h index 677b8c0f60f9..b21a77fddcf7 100644 --- a/tools/testing/radix-tree/linux/kernel.h +++ b/tools/testing/radix-tree/linux/kernel.h @@ -12,12 +12,6 @@ #include #include "../../../include/linux/kconfig.h" -#ifdef BENCHMARK -#define RADIX_TREE_MAP_SHIFT 6 -#else -#define RADIX_TREE_MAP_SHIFT 3 -#endif - #define printk printf #define pr_debug printk #define pr_cont printk -- cgit v1.2.1