lib/interval_tree: add some test cases and cleanup
Subsystems (4)
v2 cover lib/interval_tree: add some test cases and cleanup
Originally, I sent an interval tree cleanup[1], but lack of reasonable test.
As Matthew suggested, this patch set includes proper test to exercise the change in interval tree.
Since rbtree/augmented tree/interval tree share similar data structure, besides new cases for interval tree, this patch set also does cleanup for others.
Patch 1: There are test cases as kernel module, this patch enable them in
userland. This would help for testing and debugging.
Patch 2: Split cases for better reading. And prepare for new cases adding. Patch 3: Add random seed to cover different situations
Patch 4: Add case for interval_tree_iter_xxx() helper
Patch 5: Add case for span iteration
Patch 6: is the original cleanup
Patch 7: fix the comment of interval_tree_span_iter_next_gap()
v2:
* move definition of container_of() into container_of.h
* fix compile warning by defining seed with ullong
[1]: https://lkml.kernel.org/r/[email protected]
Wei Yang (7):
lib/rbtree: enable userland test suite for rbtree related data
structure
lib/rbtree: split tests
lib/rbtree: add random seed
lib/interval_tree: add test case for interval_tree_iter_xxx() helpers lib/interval_tree: add test case for span iteration lib/interval_tree: skip the check before go to the right subtree lib/interval_tree: fix the comment of
interval_tree_span_iter_next_gap()
include/linux/interval_tree_generic.h | 8 +- include/linux/types.h | 1 + lib/interval_tree.c | 12 +- lib/interval_tree_test.c | 237 ++++++++++++++++-- lib/rbtree_test.c | 30 ++- tools/include/asm/timex.h | 13 + tools/include/linux/bitmap.h | 21 ++ tools/include/linux/container_of.h | 18 ++ tools/include/linux/kernel.h | 14 +- tools/include/linux/math64.h | 5 + tools/include/linux/moduleparam.h | 7 + tools/include/linux/prandom.h | 51 ++++ tools/include/linux/slab.h | 1 + tools/include/linux/types.h | 2 + tools/lib/bitmap.c | 20 ++ tools/lib/slab.c | 16 ++ tools/testing/rbtree/Makefile | 33 +++ tools/testing/rbtree/interval_tree_test.c | 58 +++++ tools/testing/rbtree/rbtree_test.c | 48 ++++ tools/testing/rbtree/test.h | 4 + tools/testing/shared/interval_tree-shim.c | 5 + tools/testing/shared/linux/interval_tree.h | 7 + .../shared/linux/interval_tree_generic.h | 2 + tools/testing/shared/linux/rbtree.h | 8 + tools/testing/shared/linux/rbtree_augmented.h | 7 + tools/testing/shared/linux/rbtree_types.h | 8 + tools/testing/shared/rbtree-shim.c | 6 + 27 files changed, 600 insertions(+), 42 deletions(-) create mode 100644 tools/include/asm/timex.h create mode 100644 tools/include/linux/container_of.h create mode 100644 tools/include/linux/moduleparam.h create mode 100644 tools/include/linux/prandom.h create mode 100644 tools/testing/rbtree/Makefile create mode 100644 tools/testing/rbtree/interval_tree_test.c create mode 100644 tools/testing/rbtree/rbtree_test.c create mode 100644 tools/testing/rbtree/test.h create mode 100644 tools/testing/shared/interval_tree-shim.c create mode 100644 tools/testing/shared/linux/interval_tree.h create mode 100644 tools/testing/shared/linux/interval_tree_generic.h create mode 100644 tools/testing/shared/linux/rbtree.h create mode 100644 tools/testing/shared/linux/rbtree_augmented.h create mode 100644 tools/testing/shared/linux/rbtree_types.h create mode 100644 tools/testing/shared/rbtree-shim.c
Signature · 1 line
2.34.1
PATCH v2 1/7 lib/rbtree: enable userland test suite for rbtree related data structure
Currently we have some tests for rbtree related data structure, e.g. rbtree, augmented rbtree, interval tree, in lib/ as kernel module.
To facilitate the test and debug for those fundamental data structure, this patch enable those tests in userland.
---
v2: move container_of into container_of.h
--- tools/include/asm/timex.h | 13 +++++ tools/include/linux/container_of.h | 18 +++++++ tools/include/linux/kernel.h | 14 +---- tools/include/linux/math64.h | 5 ++ tools/include/linux/moduleparam.h | 7 +++ tools/include/linux/prandom.h | 51 ++++++++++++++++++ tools/include/linux/slab.h | 1 + tools/lib/slab.c | 16 ++++++ tools/testing/rbtree/Makefile | 31 +++++++++++ tools/testing/rbtree/interval_tree_test.c | 53 +++++++++++++++++++ tools/testing/rbtree/rbtree_test.c | 45 ++++++++++++++++ tools/testing/rbtree/test.h | 4 ++ tools/testing/shared/interval_tree-shim.c | 5 ++ tools/testing/shared/linux/interval_tree.h | 7 +++ .../shared/linux/interval_tree_generic.h | 2 + tools/testing/shared/linux/rbtree.h | 8 +++ tools/testing/shared/linux/rbtree_augmented.h | 7 +++ tools/testing/shared/linux/rbtree_types.h | 8 +++ tools/testing/shared/rbtree-shim.c | 6 +++ 19 files changed, 288 insertions(+), 13 deletions(-) create mode 100644 tools/include/asm/timex.h create mode 100644 tools/include/linux/container_of.h create mode 100644 tools/include/linux/moduleparam.h create mode 100644 tools/include/linux/prandom.h create mode 100644 tools/testing/rbtree/Makefile create mode 100644 tools/testing/rbtree/interval_tree_test.c create mode 100644 tools/testing/rbtree/rbtree_test.c create mode 100644 tools/testing/rbtree/test.h create mode 100644 tools/testing/shared/interval_tree-shim.c create mode 100644 tools/testing/shared/linux/interval_tree.h create mode 100644 tools/testing/shared/linux/interval_tree_generic.h create mode 100644 tools/testing/shared/linux/rbtree.h create mode 100644 tools/testing/shared/linux/rbtree_augmented.h create mode 100644 tools/testing/shared/linux/rbtree_types.h create mode 100644 tools/testing/shared/rbtree-shim.c
tools/include/asm/timex.h new file +13 -0
@@ -0,0 +1,13 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef __TOOLS_LINUX_ASM_TIMEX_H +#define __TOOLS_LINUX_ASM_TIMEX_H + +#include <time.h> + +#define cycles_t clock_t + +static inline cycles_t get_cycles (void ) +{ +return clock (); +} +#endif // __TOOLS_LINUX_ASM_TIMEX_H
tools/include/linux/container_of.h new file +18 -0
@@ -0,0 +1,18 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef _TOOLS_LINUX_CONTAINER_OF_H +#define _TOOLS_LINUX_CONTAINER_OF_H + +#ifndef container_of +/** +* container_of - cast a member of a structure out to the containing structure +* @ptr: the pointer to the member. +* @type: the type of the container struct this is embedded in. +* @member: the name of the member within the struct. +* +*/ +#define container_of (ptr, type, member) ({ \ + const typeof(((type *)0)->member) * __mptr = (ptr); \ + (type *)((char *)__mptr - offsetof(type, member)); }) +#endif + +#endif /* _TOOLS_LINUX_CONTAINER_OF_H */
tools/include/linux/kernel.h +1 -13
@@ -11,6 +11,7 @@#include <linux/panic.h> #include <endian.h> #include <byteswap.h> +#include <linux/container_of.h> #ifndef UINT_MAX #define UINT_MAX (~0U)
@@ -25,19 +26,6 @@#define offsetof (TYPE ,MEMBER ) ((size_t) &((TYPE *)0)->MEMBER)#endif -#ifndef container_of -/** -* container_of - cast a member of a structure out to the containing structure -* @ptr: the pointer to the member. -* @type: the type of the container struct this is embedded in. -* @member: the name of the member within the struct. -* -*/ -#define container_of (ptr, type, member) ({ \ - const typeof(((type *)0)->member) * __mptr = (ptr); \ - (type *)((char *)__mptr - offsetof(type, member)); }) -#endif -#ifndef max#define max (x, y) ({ \ typeof(x) _max1 = (x); \
tools/include/linux/math64.h +5 -0
@@ -72,4 +72,9 @@ static inline u64 mul_u64_u64_div64(u64 a, u64 b, u64 c) }#endif +static inline u64 div_u64 (u64 dividend,u32 divisor) +{ +return dividend / divisor; +} +#endif /* _LINUX_MATH64_H */
tools/include/linux/moduleparam.h new file +7 -0
@@ -0,0 +1,7 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef _TOOLS_LINUX_MODULE_PARAMS_H +#define _TOOLS_LINUX_MODULE_PARAMS_H + +#define MODULE_PARM_DESC (parm, desc) + +#endif // _TOOLS_LINUX_MODULE_PARAMS_H
tools/include/linux/prandom.h new file +51 -0
51 lines not on this page · raw message
tools/include/linux/slab.h +1 -0
@@ -12,6 +12,7 @@void *kmalloc (size_t size,gfp_t gfp);void kfree (void *p); +void *kmalloc_array (size_t n,size_t size,gfp_t gfp);bool slab_is_available (void );
tools/lib/slab.c +16 -0
@@ -36,3 +36,19 @@ void kfree(void *p)printf ("Freeing %p to malloc\n" , p);free (p); } + +void *kmalloc_array (size_t n,size_t size,gfp_t gfp) +{ +void *ret; + +if (!(gfp & __GFP_DIRECT_RECLAIM)) +return NULL ; + + ret =calloc (n, size); +uatomic_inc (&kmalloc_nr_allocated); +if (kmalloc_verbose) +printf ("Allocating %p from calloc\n" , ret); +if (gfp & __GFP_ZERO) +memset (ret,0 , n * size); +return ret; +}
tools/testing/rbtree/Makefile new file +31 -0
@@ -0,0 +1,31 @@ +# SPDX-License-Identifier: GPL-2.0 + +.PHONY: clean + +TARGETS = rbtree_test interval_tree_test +OFILES = $(LIBS) rbtree-shim.o interval_tree-shim.o +DEPS = ../../../include/linux/rbtree.h \ + ../../../include/linux/rbtree_types.h \ + ../../../include/linux/rbtree_augmented.h \ + ../../../include/linux/interval_tree.h \ + ../../../include/linux/interval_tree_generic.h \ + ../../../lib/rbtree.c \ + ../../../lib/interval_tree.c + +targets: $(TARGETS) + +include ../shared/shared.mk + +ifeq ($(DEBUG), 1) + CFLAGS += -g +endif + +$(TARGETS): $(OFILES) + +rbtree-shim.o: $(DEPS) +rbtree_test.o: ../../../lib/rbtree_test.c +interval_tree-shim.o: $(DEPS) +interval_tree_test.o: ../../../lib/interval_tree_test.c + +clean: + $(RM) $(TARGETS) *.o generated/*
tools/testing/rbtree/interval_tree_test.c new file +53 -0
53 lines not on this page · raw message
tools/testing/rbtree/rbtree_test.c new file +45 -0
45 lines not on this page · raw message
tools/testing/rbtree/test.h new file +4 -0
@@ -0,0 +1,4 @@ +/* SPDX-License-Identifier: GPL-2.0 */ + +void rbtree_tests (void ); +void interval_tree_tests (void );
tools/testing/shared/interval_tree-shim.c new file +5 -0
@@ -0,0 +1,5 @@ +// SPDX-License-Identifier: GPL-2.0 + +/* Very simple shim around the interval tree. */ + +#include "../../../lib/interval_tree.c"
tools/testing/shared/linux/interval_tree.h new file +7 -0
@@ -0,0 +1,7 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef _TEST_INTERVAL_TREE_H +#define _TEST_INTERVAL_TREE_H + +#include "../../../../include/linux/interval_tree.h" + +#endif /* _TEST_INTERVAL_TREE_H */
tools/testing/shared/linux/interval_tree_generic.h new file +2 -0
@@ -0,0 +1,2 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#include "../../../../include/linux/interval_tree_generic.h"
tools/testing/shared/linux/rbtree.h new file +8 -0
@@ -0,0 +1,8 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef _TEST_RBTREE_H +#define _TEST_RBTREE_H + +#include <linux/kernel.h> +#include "../../../../include/linux/rbtree.h" + +#endif /* _TEST_RBTREE_H */
tools/testing/shared/linux/rbtree_augmented.h new file +7 -0
@@ -0,0 +1,7 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef _TEST_RBTREE_AUGMENTED_H +#define _TEST_RBTREE_AUGMENTED_H + +#include "../../../../include/linux/rbtree_augmented.h" + +#endif /* _TEST_RBTREE_AUGMENTED_H */
tools/testing/shared/linux/rbtree_types.h new file +8 -0
@@ -0,0 +1,8 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef _TEST_RBTREE_TYPES_H +#define _TEST_RBTREE_TYPES_H + +#include "../../../../include/linux/rbtree_types.h" + +#endif /* _TEST_RBTREE_TYPES_H */ +
tools/testing/shared/rbtree-shim.c new file +6 -0
@@ -0,0 +1,6 @@ +// SPDX-License-Identifier: GPL-2.0 + +/* Very simple shim around the rbtree. */ + +#include "../../../lib/rbtree.c" +
Signature · 1 line
2.34.1
PATCH v2 2/7 lib/rbtree: split tests
In reply to Wei YangCurrent tests are gathered in one big function.
Split tests into its own function for better understanding and also it is a preparation for introducing new test cases.
--- lib/interval_tree_test.c | 50 +++++++++++++++++++++++++++++----------- lib/rbtree_test.c | 29 ++++++++++++++++++----- 2 files changed, 59 insertions(+), 20 deletions(-)
lib/interval_tree_test.c +36 -14
@@ -59,26 +59,13 @@ static void init(void) queries[i] = (prandom_u32_state (&rnd) >>4 ) % max_endpoint; } -static int interval_tree_test_init (void ) +static int basic_check (void ) {int i, j; -unsigned long results;cycles_t time1, time2, time; - nodes =kmalloc_array (nnodes,sizeof (struct interval_tree_node ), -GFP_KERNEL ); -if (!nodes) -return -ENOMEM ; - - queries =kmalloc_array (nsearches,sizeof (int ),GFP_KERNEL ); -if (!queries) { -kfree (nodes); -return -ENOMEM ; - } -printk (KERN_ALERT "interval tree insert/remove" ); -prandom_seed_state (&rnd,3141592653589793238ULL );init (); time1 =get_cycles ();
@@ -96,8 +83,19 @@ static int interval_tree_test_init(void) time =div_u64 (time, perf_loops);printk (" -> %llu cycles\n" , (unsigned long long )time); +return 0 ; +} + +static int search_check (void ) +{ +int i, j; +unsigned long results; +cycles_t time1, time2, time; +printk (KERN_ALERT "interval tree search" ); +init (); +for (j =0 ; j < nnodes; j++)interval_tree_insert (nodes + j, &root);
@@ -120,6 +118,30 @@ static int interval_tree_test_init(void)printk (" -> %llu cycles (%lu results)\n" , (unsigned long long )time, results); +for (j =0 ; j < nnodes; j++) +interval_tree_remove (nodes + j, &root); + +return 0 ; +} + +static int interval_tree_test_init (void ) +{ + nodes =kmalloc_array (nnodes,sizeof (struct interval_tree_node ), +GFP_KERNEL ); +if (!nodes) +return -ENOMEM ; + + queries =kmalloc_array (nsearches,sizeof (int ),GFP_KERNEL ); +if (!queries) { +kfree (nodes); +return -ENOMEM ; + } + +prandom_seed_state (&rnd,3141592653589793238ULL ); + +basic_check (); +search_check (); +kfree (queries);kfree (nodes);
lib/rbtree_test.c +23 -6
@@ -239,19 +239,14 @@ static void check_augmented(int nr_nodes) } } -static int __init rbtree_test_init (void ) +static int basic_check (void ) {int i, j;cycles_t time1, time2, time;struct rb_node *node; - nodes =kmalloc_array (nnodes,sizeof (*nodes),GFP_KERNEL ); -if (!nodes) -return -ENOMEM ; -printk (KERN_ALERT "rbtree testing" ); -prandom_seed_state (&rnd,3141592653589793238ULL );init (); time1 =get_cycles ();
@@ -343,6 +338,14 @@ static int __init rbtree_test_init(void)check (0 ); } +return 0 ; +} + +static int augmented_check (void ) +{ +int i, j; +cycles_t time1, time2, time; +printk (KERN_ALERT "augmented rbtree testing" );init ();
@@ -390,6 +393,20 @@ static int __init rbtree_test_init(void)check_augmented (0 ); } +return 0 ; +} + +static int __init rbtree_test_init (void ) +{ + nodes =kmalloc_array (nnodes,sizeof (*nodes),GFP_KERNEL ); +if (!nodes) +return -ENOMEM ; + +prandom_seed_state (&rnd,3141592653589793238ULL ); + +basic_check (); +augmented_check (); +kfree (nodes);return -EAGAIN ;/* Fail will directly unload the module */
Signature · 1 line
2.34.1
PATCH v2 3/7 lib/rbtree: add random seed
In reply to Wei YangCurrent test use pseudo rand function with fixed seed, which means the test data is the same pattern each time.
Add random seed parameter to randomize the test.
---
v2:
* define seed with ullong
--- include/linux/types.h | 1 + lib/interval_tree_test.c | 3 ++- lib/rbtree_test.c | 3 ++- tools/include/linux/types.h | 2 ++ tools/testing/rbtree/interval_tree_test.c | 5 ++++- tools/testing/rbtree/rbtree_test.c | 5 ++++- 6 files changed, 15 insertions(+), 4 deletions(-)
include/linux/types.h +1 -0
@@ -92,6 +92,7 @@ typedef unsigned char unchar;typedef unsigned short ushort ;typedef unsigned int uint ;typedef unsigned long ulong ; +typedef unsigned long long ullong ;#ifndef __BIT_TYPES_DEFINED__#define __BIT_TYPES_DEFINED__
lib/interval_tree_test.c +2 -1
@@ -19,6 +19,7 @@ __param(int, search_loops, 1000, "Number of iterations searching the tree");__param (bool, search_all, false,"Searches will iterate all nodes in the tree" );__param (uint, max_endpoint, ~0 ,"Largest value for the interval's endpoint" ); +__param (ullong, seed,3141592653589793238ULL ,"Random seed" );static struct rb_root_cached root =RB_ROOT_CACHED ;static struct interval_tree_node *nodes =NULL ;
@@ -137,7 +138,7 @@ static int interval_tree_test_init(void)return -ENOMEM ; } -prandom_seed_state (&rnd,3141592653589793238ULL ); +prandom_seed_state (&rnd, seed);basic_check ();search_check ();
lib/rbtree_test.c +2 -1
@@ -14,6 +14,7 @@__param (int, nnodes,100 ,"Number of nodes in the rb-tree" );__param (int, perf_loops,1000 ,"Number of iterations modifying the rb-tree" );__param (int, check_loops,100 ,"Number of iterations modifying and verifying the rb-tree" ); +__param (ullong, seed,3141592653589793238ULL ,"Random seed" );struct test_node {u32 key;
@@ -402,7 +403,7 @@ static int __init rbtree_test_init(void)if (!nodes)return -ENOMEM ; -prandom_seed_state (&rnd,3141592653589793238ULL ); +prandom_seed_state (&rnd, seed);basic_check ();augmented_check ();
tools/include/linux/types.h +2 -0
@@ -42,6 +42,8 @@ typedef __s16 s16;typedef __u8 u8 ;typedef __s8 s8 ; +typedef unsigned long long ullong ; +#ifdef __CHECKER__#define __bitwise __attribute__((bitwise))#else
tools/testing/rbtree/interval_tree_test.c +4 -1
@@ -18,6 +18,7 @@ int usage(void)fprintf (stderr," -s: Number of iterations searching the tree\n" );fprintf (stderr," -a: Searches will iterate all nodes in the tree\n" );fprintf (stderr," -m: Largest value for the interval's endpoint\n" ); +fprintf (stderr," -r: Random seed\n" );exit (-1 ); }
@@ -31,7 +32,7 @@ int main(int argc, char **argv) {int opt; -while ((opt =getopt (argc, argv,"n:p:q:s:am:" )) !=-1 ) { +while ((opt =getopt (argc, argv,"n:p:q:s:am:r:" )) !=-1 ) {if (opt =='n' ) nnodes =strtoul (optarg,NULL ,0 );else if (opt =='p' )
@@ -44,6 +45,8 @@ int main(int argc, char **argv) search_all = true; else if (opt == 'm') max_endpoint =strtoul (optarg,NULL ,0 ); + else if (opt == 'r') + seed =strtoul (optarg,NULL ,0 ); elseusage (); }
tools/testing/rbtree/rbtree_test.c +4 -1
@@ -16,6 +16,7 @@ int usage(void)fprintf (stderr," -n: Number of nodes in the rb-tree\n" );fprintf (stderr," -p: Number of iterations modifying the rb-tree\n" );fprintf (stderr," -c: Number of iterations modifying and verifying the rb-tree\n" ); +fprintf (stderr," -r: Random seed\n" );exit (-1 ); }
@@ -29,13 +30,15 @@ int main(int argc, char **argv) {int opt; -while ((opt =getopt (argc, argv,"n:p:c:" )) !=-1 ) { +while ((opt =getopt (argc, argv,"n:p:c:r:" )) !=-1 ) {if (opt =='n' ) nnodes =strtoul (optarg,NULL ,0 );else if (opt =='p' ) perf_loops =strtoul (optarg,NULL ,0 );else if (opt =='c' ) check_loops =strtoul (optarg,NULL ,0 ); +else if (opt =='r' ) + seed =strtoul (optarg,NULL ,0 );else usage (); }
Signature · 1 line
2.34.1
PATCH v2 4/7 lib/interval_tree: add test case for interval_tree_iter_xxx() helpers
In reply to Wei YangVerify interval_tree_iter_xxx() helpers could find intersection ranges as expected.
--- lib/interval_tree_test.c | 69 ++++++++++++++++++++++++++++++++++++ tools/include/linux/bitmap.h | 21 +++++++++++ tools/lib/bitmap.c | 20 +++++++++++ 3 files changed, 110 insertions(+)
lib/interval_tree_test.c +69 -0
@@ -5,6 +5,7 @@#include <linux/prandom.h> #include <linux/slab.h> #include <asm/timex.h> +#include <linux/bitmap.h> #define __param (type, name, init, msg) \ static type name = init; \
@@ -125,6 +126,73 @@ static int search_check(void)return 0 ; } +static int intersection_range_check (void ) +{ +int i, j, k; +unsigned long start, last; +struct interval_tree_node *node; +unsigned long *intxn1; +unsigned long *intxn2; + +printk (KERN_ALERT "interval tree iteration\n" ); + + intxn1 =bitmap_alloc (nnodes,GFP_KERNEL ); +if (!intxn1) { +WARN_ON_ONCE ("Failed to allocate intxn1\n" ); +return -ENOMEM ; + } + + intxn2 =bitmap_alloc (nnodes,GFP_KERNEL ); +if (!intxn2) { +WARN_ON_ONCE ("Failed to allocate intxn2\n" ); +bitmap_free (intxn1); +return -ENOMEM ; + } + +for (i =0 ; i < search_loops; i++) { +/* Initialize interval tree for each round */ +init (); +for (j =0 ; j < nnodes; j++) +interval_tree_insert (nodes + j, &root); + +/* Let's try nsearches different ranges */ +for (k =0 ; k < nsearches; k++) { +/* Try whole range once */ +if (!k) { + start =0UL ; + last =ULONG_MAX ; + }else { + last = (prandom_u32_state (&rnd) >>4 ) % max_endpoint; + start = (prandom_u32_state (&rnd) >>4 ) % last; + } + +/* Walk nodes to mark intersection nodes */ +bitmap_zero (intxn1, nnodes); +for (j =0 ; j < nnodes; j++) { + node = nodes + j; + +if (start <= node->last && last >= node->start) +bitmap_set (intxn1, j,1 ); + } + +/* Iterate tree to clear intersection nodes */ +bitmap_zero (intxn2, nnodes); +for (node =interval_tree_iter_first (&root, start, last); node; + node =interval_tree_iter_next (node, start, last)) +bitmap_set (intxn2, node - nodes,1 ); + +WARN_ON_ONCE (!bitmap_equal (intxn1, intxn2, nnodes)); + } + +for (j =0 ; j < nnodes; j++) +interval_tree_remove (nodes + j, &root); + } + +bitmap_free (intxn1); +bitmap_free (intxn2); +return 0 ; +} +static int interval_tree_test_init (void ) { nodes = kmalloc_array(nnodes, sizeof(struct interval_tree_node),
@@ -142,6 +210,7 @@ static int interval_tree_test_init(void)basic_check ();search_check (); +intersection_range_check ();kfree (queries);kfree (nodes);
tools/include/linux/bitmap.h +21 -0
@@ -19,6 +19,7 @@ bool __bitmap_and(unsigned long *dst, const unsigned long *bitmap1, const unsigned long *bitmap2, unsigned int bits);bool __bitmap_equal (const unsigned long *bitmap1,const unsigned long *bitmap2,unsigned int bits); +void __bitmap_set (unsigned long *map,unsigned int start,int len);void __bitmap_clear (unsigned long *map,unsigned int start,int len);bool __bitmap_intersects (const unsigned long *bitmap1,const unsigned long *bitmap2,unsigned int bits);
@@ -79,6 +80,11 @@ static inline void bitmap_or(unsigned long *dst, const unsigned long *src1,__bitmap_or (dst, src1, src2, nbits); } +static inline unsigned long *bitmap_alloc (unsigned int nbits,gfp_t flags) +{ +return malloc (bitmap_size (nbits)); +} +/** * bitmap_zalloc - Allocate bitmap * @nbits: Number of bits
@@ -150,6 +156,21 @@ static inline bool bitmap_intersects(const unsigned long *src1,return __bitmap_intersects (src1, src2, nbits); } +static inline void bitmap_set (unsigned long *map,unsigned int start,unsigned int nbits) +{ +if (__builtin_constant_p (nbits) && nbits ==1 ) +__set_bit (start, map); +else if (small_const_nbits (start + nbits)) + *map |=GENMASK (start + nbits -1 , start); +else if (__builtin_constant_p (start &BITMAP_MEM_MASK ) && +IS_ALIGNED (start,BITMAP_MEM_ALIGNMENT ) && +__builtin_constant_p (nbits &BITMAP_MEM_MASK ) && +IS_ALIGNED (nbits,BITMAP_MEM_ALIGNMENT )) +memset ((char *)map + start /8 ,0xff , nbits /8 ); +else +__bitmap_set (map, start, nbits); +} +static inline void bitmap_clear (unsigned long *map,unsigned int start,unsigned int nbits) {
tools/lib/bitmap.c +20 -0
@@ -101,6 +101,26 @@ bool __bitmap_intersects(const unsigned long *bitmap1,return false; } +void __bitmap_set (unsigned long *map,unsigned int start,int len) +{ +unsigned long *p = map +BIT_WORD (start); +const unsigned int size = start + len; +int bits_to_set =BITS_PER_LONG - (start %BITS_PER_LONG ); +unsigned long mask_to_set =BITMAP_FIRST_WORD_MASK (start); + +while (len - bits_to_set >=0 ) { + *p |= mask_to_set; + len -= bits_to_set; + bits_to_set =BITS_PER_LONG ; + mask_to_set = ~0UL ; + p++; + } +if (len) { + mask_to_set &=BITMAP_LAST_WORD_MASK (size); + *p |= mask_to_set; + } +} +void __bitmap_clear (unsigned long *map,unsigned int start,int len) {unsigned long *p = map +BIT_WORD (start);
Signature · 1 line
2.34.1
PATCH v2 5/7 lib/interval_tree: add test case for span iteration
In reply to Wei YangVerify interval_tree_span_iter_xxx() helpers works as expected.
--- lib/interval_tree_test.c | 117 ++++++++++++++++++++++ tools/testing/rbtree/Makefile | 6 +- tools/testing/rbtree/interval_tree_test.c | 2 + 3 files changed, 123 insertions(+), 2 deletions(-)
lib/interval_tree_test.c +117 -0
@@ -6,6 +6,7 @@#include <linux/slab.h> #include <asm/timex.h> #include <linux/bitmap.h> +#include <linux/maple_tree.h> #define __param (type, name, init, msg) \ static type name = init; \
@@ -193,6 +194,121 @@ static int intersection_range_check(void)return 0 ; } +#ifdef CONFIG_INTERVAL_TREE_SPAN_ITER +/* +* Helper function to get span of current position from maple tree point of +* view. +*/ +static void mas_cur_span (struct ma_state *mas,struct interval_tree_span_iter *state) +{ +unsigned long cur_start; +unsigned long cur_last; +int is_hole; + +if (mas->status == ma_overflow) +return ; + +/* walk to current position */ + state->is_hole =mas_walk (mas) ?0 :1 ; + + cur_start = mas->index < state->first_index ? + state->first_index : mas->index; + +/* whether we have followers */ +do { + + cur_last = mas->last > state->last_index ? + state->last_index : mas->last; + + is_hole =mas_next_range (mas, state->last_index) ?0 :1 ; + + }while (mas->status != ma_overflow && is_hole == state->is_hole); + +if (state->is_hole) { + state->start_hole = cur_start; + state->last_hole = cur_last; + }else { + state->start_used = cur_start; + state->last_used = cur_last; + } + +/* advance position for next round */ +if (mas->status != ma_overflow) +mas_set (mas, cur_last +1 ); +} + +static int span_iteration_check (void ) +{ +int i, j, k; +unsigned long start, last; +struct interval_tree_span_iter span, mas_span; + +DEFINE_MTREE (tree); + +MA_STATE (mas, &tree,0 ,0 ); + +printk (KERN_ALERT "interval tree span iteration\n" ); + +for (i =0 ; i < search_loops; i++) { +/* Initialize interval tree for each round */ +init (); +for (j =0 ; j < nnodes; j++) +interval_tree_insert (nodes + j, &root); + +/* Put all the range into maple tree */ +mt_init_flags (&tree,MT_FLAGS_ALLOC_RANGE ); +mt_set_in_rcu (&tree); + +for (j =0 ; j < nnodes; j++) +WARN_ON_ONCE (mtree_store_range (&tree, nodes[j].start, + nodes[j].last, nodes + j,GFP_KERNEL )); + +/* Let's try nsearches different ranges */ +for (k =0 ; k < nsearches; k++) { +/* Try whole range once */ +if (!k) { + start =0UL ; + last =ULONG_MAX ; + }else { + last = (prandom_u32_state (&rnd) >>4 ) % max_endpoint; + start = (prandom_u32_state (&rnd) >>4 ) % last; + } + + mas_span.first_index = start; + mas_span.last_index = last; + mas_span.is_hole =-1 ; +mas_set (&mas, start); + +interval_tree_for_each_span (&span, &root, start, last) { +mas_cur_span (&mas, &mas_span); + +WARN_ON_ONCE (span.is_hole != mas_span.is_hole); + +if (span.is_hole) { +WARN_ON_ONCE (span.start_hole != mas_span.start_hole); +WARN_ON_ONCE (span.last_hole != mas_span.last_hole); + }else { +WARN_ON_ONCE (span.start_used != mas_span.start_used); +WARN_ON_ONCE (span.last_used != mas_span.last_used); + } + } + + } + +WARN_ON_ONCE (mas.status != ma_overflow); + +/* Cleanup maple tree for each round */ +mtree_destroy (&tree); +/* Cleanup interval tree for each round */ +for (j =0 ; j < nnodes; j++) +interval_tree_remove (nodes + j, &root); + } +return 0 ; +} +#else +static inline int span_iteration_check (void ) {return 0 ; } +#endif +static int interval_tree_test_init (void ) { nodes = kmalloc_array(nnodes, sizeof(struct interval_tree_node),
@@ -211,6 +327,7 @@ static int interval_tree_test_init(void)basic_check ();search_check ();intersection_range_check (); +span_iteration_check ();kfree (queries);kfree (nodes);
tools/testing/rbtree/Makefile +4 -2
@@ -3,7 +3,7 @@ .PHONY: clean TARGETS = rbtree_test interval_tree_test -OFILES = $(LIBS) rbtree-shim.o interval_tree-shim.o +OFILES = $(SHARED_OFILES) rbtree-shim.o interval_tree-shim.o maple-shim.o DEPS = ../../../include/linux/rbtree.h \ ../../../include/linux/rbtree_types.h \ ../../../include/linux/rbtree_augmented.h \
@@ -25,7 +25,9 @@ $(TARGETS): $(OFILES) rbtree-shim.o: $(DEPS) rbtree_test.o: ../../../lib/rbtree_test.c interval_tree-shim.o: $(DEPS) +interval_tree-shim.o: CFLAGS += -DCONFIG_INTERVAL_TREE_SPAN_ITER interval_tree_test.o: ../../../lib/interval_tree_test.c +interval_tree_test.o: CFLAGS += -DCONFIG_INTERVAL_TREE_SPAN_ITER clean: - $(RM) $(TARGETS) *.o generated/* + $(RM) $(TARGETS) *.o radix-tree.c idr.c generated/*
tools/testing/rbtree/interval_tree_test.c +2 -0
@@ -6,6 +6,7 @@#include <linux/math64.h> #include <linux/kern_levels.h> #include "shared.h" +#include "maple-shared.h" #include "../../../lib/interval_tree_test.c"
@@ -51,6 +52,7 @@ int main(int argc, char **argv)usage (); } +maple_tree_init ();interval_tree_tests ();return 0 ; }
Signature · 1 line
2.34.1
PATCH v2 6/7 lib/interval_tree: skip the check before go to the right subtree
In reply to Wei YangThe interval_tree_subtree_search() holds the loop invariant:
start <= node->ITSUBTREE
Let's say we have a following tree:
node
/ \
left rightSo we know node->ITSUBTREE is contributed by one of the following:
* left->ITSUBTREE
* ITLAST(node)
* right->ITSUBTREE
When we come to the right node, we are sure the first two don't contribute to node->ITSUBTREE and it must be the right node does the job.
So skip the check before go to the right subtree.
--- include/linux/interval_tree_generic.h | 8 ++------ 1 file changed, 2 insertions(+), 6 deletions(-)
include/linux/interval_tree_generic.h +2 -6
@@ -104,12 +104,8 @@ ITPREFIX ## _subtree_search(ITSTRUCT *node, ITTYPE start, ITTYPE last) \if (ITSTART (node) <= last) {/* Cond1 */ \if (start <=ITLAST (node))/* Cond2 */ \return node;/* node is leftmost match */ \ -if (node->ITRB.rb_right) { \ - node =rb_entry (node->ITRB.rb_right, \ -ITSTRUCT ,ITRB ); \ -if (start <= node->ITSUBTREE) \ -continue ; \ - } \ + node =rb_entry (node->ITRB.rb_right,ITSTRUCT ,ITRB ); \ +continue ; \ } \return NULL ;/* No match */ \ } \
Signature · 1 line
2.34.1
PATCH v2 7/7 lib/interval_tree: fix the comment of interval_tree_span_iter_next_gap()
In reply to Wei YangThe comment of interval_tree_span_iter_next_gap() is not exact, nodes[1] is not always !NULL.
There are threes cases here. If there is an interior hole, the statement is correct. If there is a tailing hole or the contiguous used range span to the end, nodes[1] is NULL.
---
v2: add the missing "of" in comment
--- lib/interval_tree.c | 12 +++++++++--- 1 file changed, 9 insertions(+), 3 deletions(-)
lib/interval_tree.c +9 -3
@@ -20,9 +20,15 @@ EXPORT_SYMBOL_GPL(interval_tree_iter_next);/* * Roll nodes[1] into nodes[0] by advancing nodes[1] to the end of a contiguous * span of nodes. This makes nodes[0]->last the end of that contiguous used span -* indexes that started at the original nodes[1]->start. nodes[1] is now the -* first node starting the next used span. A hole span is between nodes[0]->last -* and nodes[1]->start. nodes[1] must be !NULL. +* of indexes that started at the original nodes[1]->start. +* +* If there is an interior hole, nodes[1] is now the first node starting the +* next used span. A hole span is between nodes[0]->last and nodes[1]->start. +* +* If there is a tailing hole, nodes[1] is now NULL. A hole span is between +* nodes[0]->last and last_index. +* +* If the contiguous used range span to last_index, nodes[1] is set to NULL. */ static void interval_tree_span_iter_next_gap (struct interval_tree_span_iter *state)
Signature · 1 line
2.34.1