From a88cc108f6f39e56577793f66ac69eb0e18ae099 Mon Sep 17 00:00:00 2001 From: Chris Wilson Date: Mon, 17 Mar 2014 12:21:54 +0000 Subject: lib: Export interval_tree lib/interval_tree.c provides a simple interface for an interval-tree (an augmented red-black tree) but is only built when testing the generic macros for building interval-trees. For drivers with modest needs, export the simple interval-tree library as is. v2: Lots of help from Michel Lespinasse to only compile the code as required: - make INTERVAL_TREE a config option - make INTERVAL_TREE_TEST select the library functions and sanitize the filenames & Makefile - prepare interval_tree for being built as a module if required Signed-off-by: Chris Wilson Cc: Michel Lespinasse Cc: Rik van Riel Cc: Peter Zijlstra Cc: Andrea Arcangeli Cc: David Woodhouse Cc: Andrew Morton Reviewed-by: Michel Lespinasse [Acked for inclusion via drm/i915 by Andrew Morton.] [danvet: switch to _GPL as per the mailing list discussion.] Signed-off-by: Daniel Vetter --- lib/Kconfig | 14 ++++++ lib/Kconfig.debug | 1 + lib/Makefile | 3 +- lib/interval_tree.c | 6 +++ lib/interval_tree_test.c | 106 ++++++++++++++++++++++++++++++++++++++++++ lib/interval_tree_test_main.c | 106 ------------------------------------------ 6 files changed, 128 insertions(+), 108 deletions(-) create mode 100644 lib/interval_tree_test.c delete mode 100644 lib/interval_tree_test_main.c (limited to 'lib') diff --git a/lib/Kconfig b/lib/Kconfig index 4771fb3f4da4..334f7722a999 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -331,6 +331,20 @@ config TEXTSEARCH_FSM config BTREE boolean +config INTERVAL_TREE + boolean + help + Simple, embeddable, interval-tree. Can find the start of an + overlapping range in log(n) time and then iterate over all + overlapping nodes. The algorithm is implemented as an + augmented rbtree. + + See: + + Documentation/rbtree.txt + + for more information. + config ASSOCIATIVE_ARRAY bool help diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index 819ac51202c0..4bff173fef0a 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -1496,6 +1496,7 @@ config RBTREE_TEST config INTERVAL_TREE_TEST tristate "Interval tree test" depends on m && DEBUG_KERNEL + select INTERVAL_TREE help A benchmark measuring the performance of the interval tree library diff --git a/lib/Makefile b/lib/Makefile index 0cd7b68e1382..2c6c1a42e1d2 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -50,6 +50,7 @@ CFLAGS_hweight.o = $(subst $(quote),,$(CONFIG_ARCH_HWEIGHT_CFLAGS)) obj-$(CONFIG_GENERIC_HWEIGHT) += hweight.o obj-$(CONFIG_BTREE) += btree.o +obj-$(CONFIG_INTERVAL_TREE) += interval_tree.o obj-$(CONFIG_ASSOCIATIVE_ARRAY) += assoc_array.o obj-$(CONFIG_DEBUG_PREEMPT) += smp_processor_id.o obj-$(CONFIG_DEBUG_LIST) += list_debug.o @@ -156,8 +157,6 @@ lib-$(CONFIG_LIBFDT) += $(libfdt_files) obj-$(CONFIG_RBTREE_TEST) += rbtree_test.o obj-$(CONFIG_INTERVAL_TREE_TEST) += interval_tree_test.o -interval_tree_test-objs := interval_tree_test_main.o interval_tree.o - obj-$(CONFIG_PERCPU_TEST) += percpu_test.o obj-$(CONFIG_ASN1) += asn1_decoder.o diff --git a/lib/interval_tree.c b/lib/interval_tree.c index e6eb406f2d65..f367f9ad544c 100644 --- a/lib/interval_tree.c +++ b/lib/interval_tree.c @@ -1,6 +1,7 @@ #include #include #include +#include #define START(node) ((node)->start) #define LAST(node) ((node)->last) @@ -8,3 +9,8 @@ INTERVAL_TREE_DEFINE(struct interval_tree_node, rb, unsigned long, __subtree_last, START, LAST,, interval_tree) + +EXPORT_SYMBOL_GPL(interval_tree_insert); +EXPORT_SYMBOL_GPL(interval_tree_remove); +EXPORT_SYMBOL_GPL(interval_tree_iter_first); +EXPORT_SYMBOL_GPL(interval_tree_iter_next); diff --git a/lib/interval_tree_test.c b/lib/interval_tree_test.c new file mode 100644 index 000000000000..245900b98c8e --- /dev/null +++ b/lib/interval_tree_test.c @@ -0,0 +1,106 @@ +#include +#include +#include +#include + +#define NODES 100 +#define PERF_LOOPS 100000 +#define SEARCHES 100 +#define SEARCH_LOOPS 10000 + +static struct rb_root root = RB_ROOT; +static struct interval_tree_node nodes[NODES]; +static u32 queries[SEARCHES]; + +static struct rnd_state rnd; + +static inline unsigned long +search(unsigned long query, struct rb_root *root) +{ + struct interval_tree_node *node; + unsigned long results = 0; + + for (node = interval_tree_iter_first(root, query, query); node; + node = interval_tree_iter_next(node, query, query)) + results++; + return results; +} + +static void init(void) +{ + int i; + for (i = 0; i < NODES; i++) { + u32 a = prandom_u32_state(&rnd); + u32 b = prandom_u32_state(&rnd); + if (a <= b) { + nodes[i].start = a; + nodes[i].last = b; + } else { + nodes[i].start = b; + nodes[i].last = a; + } + } + for (i = 0; i < SEARCHES; i++) + queries[i] = prandom_u32_state(&rnd); +} + +static int interval_tree_test_init(void) +{ + int i, j; + unsigned long results; + cycles_t time1, time2, time; + + printk(KERN_ALERT "interval tree insert/remove"); + + prandom_seed_state(&rnd, 3141592653589793238ULL); + init(); + + time1 = get_cycles(); + + for (i = 0; i < PERF_LOOPS; i++) { + for (j = 0; j < NODES; j++) + interval_tree_insert(nodes + j, &root); + for (j = 0; j < NODES; j++) + interval_tree_remove(nodes + j, &root); + } + + time2 = get_cycles(); + time = time2 - time1; + + time = div_u64(time, PERF_LOOPS); + printk(" -> %llu cycles\n", (unsigned long long)time); + + printk(KERN_ALERT "interval tree search"); + + for (j = 0; j < NODES; j++) + interval_tree_insert(nodes + j, &root); + + time1 = get_cycles(); + + results = 0; + for (i = 0; i < SEARCH_LOOPS; i++) + for (j = 0; j < SEARCHES; j++) + results += search(queries[j], &root); + + time2 = get_cycles(); + time = time2 - time1; + + time = div_u64(time, SEARCH_LOOPS); + results = div_u64(results, SEARCH_LOOPS); + printk(" -> %llu cycles (%lu results)\n", + (unsigned long long)time, results); + + return -EAGAIN; /* Fail will directly unload the module */ +} + +static void interval_tree_test_exit(void) +{ + printk(KERN_ALERT "test exit\n"); +} + +module_init(interval_tree_test_init) +module_exit(interval_tree_test_exit) + +MODULE_LICENSE("GPL"); +MODULE_AUTHOR("Michel Lespinasse"); +MODULE_DESCRIPTION("Interval Tree test"); diff --git a/lib/interval_tree_test_main.c b/lib/interval_tree_test_main.c deleted file mode 100644 index 245900b98c8e..000000000000 --- a/lib/interval_tree_test_main.c +++ /dev/null @@ -1,106 +0,0 @@ -#include -#include -#include -#include - -#define NODES 100 -#define PERF_LOOPS 100000 -#define SEARCHES 100 -#define SEARCH_LOOPS 10000 - -static struct rb_root root = RB_ROOT; -static struct interval_tree_node nodes[NODES]; -static u32 queries[SEARCHES]; - -static struct rnd_state rnd; - -static inline unsigned long -search(unsigned long query, struct rb_root *root) -{ - struct interval_tree_node *node; - unsigned long results = 0; - - for (node = interval_tree_iter_first(root, query, query); node; - node = interval_tree_iter_next(node, query, query)) - results++; - return results; -} - -static void init(void) -{ - int i; - for (i = 0; i < NODES; i++) { - u32 a = prandom_u32_state(&rnd); - u32 b = prandom_u32_state(&rnd); - if (a <= b) { - nodes[i].start = a; - nodes[i].last = b; - } else { - nodes[i].start = b; - nodes[i].last = a; - } - } - for (i = 0; i < SEARCHES; i++) - queries[i] = prandom_u32_state(&rnd); -} - -static int interval_tree_test_init(void) -{ - int i, j; - unsigned long results; - cycles_t time1, time2, time; - - printk(KERN_ALERT "interval tree insert/remove"); - - prandom_seed_state(&rnd, 3141592653589793238ULL); - init(); - - time1 = get_cycles(); - - for (i = 0; i < PERF_LOOPS; i++) { - for (j = 0; j < NODES; j++) - interval_tree_insert(nodes + j, &root); - for (j = 0; j < NODES; j++) - interval_tree_remove(nodes + j, &root); - } - - time2 = get_cycles(); - time = time2 - time1; - - time = div_u64(time, PERF_LOOPS); - printk(" -> %llu cycles\n", (unsigned long long)time); - - printk(KERN_ALERT "interval tree search"); - - for (j = 0; j < NODES; j++) - interval_tree_insert(nodes + j, &root); - - time1 = get_cycles(); - - results = 0; - for (i = 0; i < SEARCH_LOOPS; i++) - for (j = 0; j < SEARCHES; j++) - results += search(queries[j], &root); - - time2 = get_cycles(); - time = time2 - time1; - - time = div_u64(time, SEARCH_LOOPS); - results = div_u64(results, SEARCH_LOOPS); - printk(" -> %llu cycles (%lu results)\n", - (unsigned long long)time, results); - - return -EAGAIN; /* Fail will directly unload the module */ -} - -static void interval_tree_test_exit(void) -{ - printk(KERN_ALERT "test exit\n"); -} - -module_init(interval_tree_test_init) -module_exit(interval_tree_test_exit) - -MODULE_LICENSE("GPL"); -MODULE_AUTHOR("Michel Lespinasse"); -MODULE_DESCRIPTION("Interval Tree test"); -- cgit v1.2.3