Re: [Intel-gfx] [PATCH 1/3] lib: Export interval_tree
On Tue, Mar 18, 2014 at 09:56:12AM +, Chris Wilson wrote: On Mon, Mar 17, 2014 at 06:08:57AM -0700, Michel Lespinasse wrote: On Mon, Mar 17, 2014 at 5:31 AM, David Woodhouse dw...@infradead.org wrote: On Mon, 2014-03-17 at 12:21 +, Chris Wilson wrote: +EXPORT_SYMBOL(interval_tree_insert); +EXPORT_SYMBOL(interval_tree_remove); +EXPORT_SYMBOL(interval_tree_iter_first); +EXPORT_SYMBOL(interval_tree_iter_next); I'd prefer to see EXPORT_SYMBOL_GPL for this. I'm fine with it either way. I think it would help if you stated the reason for your preference though ? Nobody objects? How about v3: Prefer EXPORT_SYMBOL_GPL for new library routines as the reason in the changelog for amending the patch? Frobbed _GPL onto the exports while applying and pulled into my drm-intel-next queue for 3.16. Thanks for the patch and reviews. -Daniel -- Daniel Vetter Software Engineer, Intel Corporation +41 (0) 79 365 57 48 - http://blog.ffwll.ch ___ Intel-gfx mailing list Intel-gfx@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/intel-gfx
Re: [Intel-gfx] [PATCH 1/3] lib: Export interval_tree
On Mon, Mar 17, 2014 at 06:08:57AM -0700, Michel Lespinasse wrote: On Mon, Mar 17, 2014 at 5:31 AM, David Woodhouse dw...@infradead.org wrote: On Mon, 2014-03-17 at 12:21 +, Chris Wilson wrote: +EXPORT_SYMBOL(interval_tree_insert); +EXPORT_SYMBOL(interval_tree_remove); +EXPORT_SYMBOL(interval_tree_iter_first); +EXPORT_SYMBOL(interval_tree_iter_next); I'd prefer to see EXPORT_SYMBOL_GPL for this. I'm fine with it either way. I think it would help if you stated the reason for your preference though ? Nobody objects? How about v3: Prefer EXPORT_SYMBOL_GPL for new library routines as the reason in the changelog for amending the patch? -Chris -- Chris Wilson, Intel Open Source Technology Centre ___ Intel-gfx mailing list Intel-gfx@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/intel-gfx
[Intel-gfx] [PATCH 1/3] 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 ch...@chris-wilson.co.uk Cc: Michel Lespinasse wal...@google.com Cc: Rik van Riel r...@redhat.com Cc: Peter Zijlstra a.p.zijls...@chello.nl Cc: Andrea Arcangeli aarca...@redhat.com Cc: David Woodhouse dw...@infradead.org Cc: Andrew Morton a...@linux-foundation.org Reviewed-by: Michel Lespinasse wal...@google.com [Acked for inclusion via drm/i915 by Andrew Morton.] --- 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 diff --git a/lib/Kconfig b/lib/Kconfig index 991c98bc4a3f..04270aae4b60 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -322,6 +322,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 a48abeac753f..135a6a0588c9 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -1487,6 +1487,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 48140e3ba73f..0969494f20d1 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 @@ -155,8 +156,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..e4109f624e51 100644 --- a/lib/interval_tree.c +++ b/lib/interval_tree.c @@ -1,6 +1,7 @@ #include linux/init.h #include linux/interval_tree.h #include linux/interval_tree_generic.h +#include linux/module.h #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(interval_tree_insert); +EXPORT_SYMBOL(interval_tree_remove); +EXPORT_SYMBOL(interval_tree_iter_first); +EXPORT_SYMBOL(interval_tree_iter_next); diff --git a/lib/interval_tree_test.c b/lib/interval_tree_test.c new file mode 100644 index ..245900b98c8e --- /dev/null +++ b/lib/interval_tree_test.c @@ -0,0 +1,106 @@ +#include linux/module.h +#include linux/interval_tree.h +#include linux/random.h +#include asm/timex.h + +#define NODES100 +#define PERF_LOOPS 10 +#define SEARCHES 100 +#define SEARCH_LOOPS 1 + +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 =
Re: [Intel-gfx] [PATCH 1/3] lib: Export interval_tree
On Mon, 2014-03-17 at 12:21 +, Chris Wilson wrote: +EXPORT_SYMBOL(interval_tree_insert); +EXPORT_SYMBOL(interval_tree_remove); +EXPORT_SYMBOL(interval_tree_iter_first); +EXPORT_SYMBOL(interval_tree_iter_next); I'd prefer to see EXPORT_SYMBOL_GPL for this. -- dwmw2 smime.p7s Description: S/MIME cryptographic signature ___ Intel-gfx mailing list Intel-gfx@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/intel-gfx
[Intel-gfx] [PATCH 1/3] 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 ch...@chris-wilson.co.uk Cc: Michel Lespinasse wal...@google.com Cc: Rik van Riel r...@redhat.com Cc: Peter Zijlstra a.p.zijls...@chello.nl Cc: Andrea Arcangeli aarca...@redhat.com Cc: David Woodhouse dw...@infradead.org Cc: Andrew Morton a...@linux-foundation.org Reviewed-by: Michel Lespinasse wal...@google.com [Acked for inclusion via drm/i915 by Andrew Morton.] --- 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 diff --git a/lib/Kconfig b/lib/Kconfig index 991c98bc4a3f..04270aae4b60 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -322,6 +322,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 db25707aa41b..a29e9b84f102 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -1478,6 +1478,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 a459c31e8c6b..fc04948548ad 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -47,6 +47,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 @@ -152,8 +153,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..e4109f624e51 100644 --- a/lib/interval_tree.c +++ b/lib/interval_tree.c @@ -1,6 +1,7 @@ #include linux/init.h #include linux/interval_tree.h #include linux/interval_tree_generic.h +#include linux/module.h #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(interval_tree_insert); +EXPORT_SYMBOL(interval_tree_remove); +EXPORT_SYMBOL(interval_tree_iter_first); +EXPORT_SYMBOL(interval_tree_iter_next); diff --git a/lib/interval_tree_test.c b/lib/interval_tree_test.c new file mode 100644 index ..245900b98c8e --- /dev/null +++ b/lib/interval_tree_test.c @@ -0,0 +1,106 @@ +#include linux/module.h +#include linux/interval_tree.h +#include linux/random.h +#include asm/timex.h + +#define NODES100 +#define PERF_LOOPS 10 +#define SEARCHES 100 +#define SEARCH_LOOPS 1 + +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 =
[Intel-gfx] [PATCH 1/3] 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 ch...@chris-wilson.co.uk Cc: Michel Lespinasse wal...@google.com Cc: Rik van Riel r...@redhat.com Cc: Peter Zijlstra a.p.zijls...@chello.nl Cc: Andrea Arcangeli aarca...@redhat.com Cc: David Woodhouse dw...@infradead.org Cc: Andrew Morton a...@linux-foundation.org Reviewed-by: Michel Lespinasse wal...@google.com [Acked for inclusion via drm/i915 by Andrew Morton.] --- 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 diff --git a/lib/Kconfig b/lib/Kconfig index 991c98bc4a3f..04270aae4b60 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -322,6 +322,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 db25707aa41b..a29e9b84f102 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -1478,6 +1478,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 a459c31e8c6b..fc04948548ad 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -47,6 +47,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 @@ -152,8 +153,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..e4109f624e51 100644 --- a/lib/interval_tree.c +++ b/lib/interval_tree.c @@ -1,6 +1,7 @@ #include linux/init.h #include linux/interval_tree.h #include linux/interval_tree_generic.h +#include linux/module.h #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(interval_tree_insert); +EXPORT_SYMBOL(interval_tree_remove); +EXPORT_SYMBOL(interval_tree_iter_first); +EXPORT_SYMBOL(interval_tree_iter_next); diff --git a/lib/interval_tree_test.c b/lib/interval_tree_test.c new file mode 100644 index ..245900b98c8e --- /dev/null +++ b/lib/interval_tree_test.c @@ -0,0 +1,106 @@ +#include linux/module.h +#include linux/interval_tree.h +#include linux/random.h +#include asm/timex.h + +#define NODES100 +#define PERF_LOOPS 10 +#define SEARCHES 100 +#define SEARCH_LOOPS 1 + +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 =