From b69ec42b1b194cc88f04b3fbcda8d3f93182d6c3 Mon Sep 17 00:00:00 2001 From: Catalin Marinas Date: Mon, 8 Oct 2012 16:28:11 -0700 Subject: Kconfig: clean up the long arch list for the DEBUG_KMEMLEAK config option Introduce HAVE_DEBUG_KMEMLEAK config option and select it in corresponding architecture Kconfig files. DEBUG_KMEMLEAK now only depends on HAVE_DEBUG_KMEMLEAK. Signed-off-by: Catalin Marinas Cc: Russell King Cc: Michal Simek Cc: Ralf Baechle Cc: Benjamin Herrenschmidt Cc: Paul Mackerras Cc: Martin Schwidefsky Cc: Heiko Carstens Cc: Paul Mundt Cc: "David S. Miller" Cc: Chris Metcalf Cc: Thomas Gleixner Cc: Ingo Molnar Cc: "H. Peter Anvin" Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/Kconfig.debug | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) (limited to 'lib') diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index 7fba3a98967f..736db3990506 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -450,12 +450,12 @@ config SLUB_STATS out which slabs are relevant to a particular load. Try running: slabinfo -DA +config HAVE_DEBUG_KMEMLEAK + bool + config DEBUG_KMEMLEAK bool "Kernel memory leak detector" - depends on DEBUG_KERNEL && EXPERIMENTAL && \ - (X86 || ARM || PPC || MIPS || S390 || SPARC64 || SUPERH || \ - MICROBLAZE || TILE || ARM64) - + depends on DEBUG_KERNEL && EXPERIMENTAL && HAVE_DEBUG_KMEMLEAK select DEBUG_FS select STACKTRACE if STACKTRACE_SUPPORT select KALLSYMS -- cgit v1.2.1 From 9b2a60c484715e2d2f07d8192fd9f18435cbc77c Mon Sep 17 00:00:00 2001 From: Catalin Marinas Date: Mon, 8 Oct 2012 16:28:13 -0700 Subject: Kconfig: clean up the long arch list for the DEBUG_BUGVERBOSE config option Introduce HAVE_DEBUG_BUGVERBOSE config option and select it in corresponding architecture Kconfig files. Architectures that already select GENERIC_BUG don't need to select HAVE_DEBUG_BUGVERBOSE. Signed-off-by: Catalin Marinas Acked-by: Geert Uytterhoeven Cc: David Howells Cc: Hirokazu Takata Cc: Paul Mundt Cc: "David S. Miller" Cc: Chris Metcalf Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/Kconfig.debug | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) (limited to 'lib') diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index 736db3990506..b7281e4d1473 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -751,12 +751,12 @@ config DEBUG_HIGHMEM This options enables addition error checking for high memory systems. Disable for production systems. +config HAVE_DEBUG_BUGVERBOSE + bool + config DEBUG_BUGVERBOSE bool "Verbose BUG() reporting (adds 70K)" if DEBUG_KERNEL && EXPERT - depends on BUG - depends on ARM || AVR32 || M32R || M68K || SPARC32 || SPARC64 || \ - FRV || SUPERH || GENERIC_BUG || BLACKFIN || MN10300 || \ - TILE || ARM64 + depends on BUG && (GENERIC_BUG || HAVE_DEBUG_BUGVERBOSE) default y help Say Y here to make BUG() panics output the file name and line number -- cgit v1.2.1 From 4c199a93a2d36b277a9fd209a0f2793f8460a215 Mon Sep 17 00:00:00 2001 From: Michel Lespinasse Date: Mon, 8 Oct 2012 16:30:32 -0700 Subject: rbtree: empty nodes have no color Empty nodes have no color. We can make use of this property to simplify the code emitted by the RB_EMPTY_NODE and RB_CLEAR_NODE macros. Also, we can get rid of the rb_init_node function which had been introduced by commit 88d19cf37952 ("timers: Add rb_init_node() to allow for stack allocated rb nodes") to avoid some issue with the empty node's color not being initialized. I'm not sure what the RB_EMPTY_NODE checks in rb_prev() / rb_next() are doing there, though. axboe introduced them in commit 10fd48f2376d ("rbtree: fixed reversed RB_EMPTY_NODE and rb_next/prev"). The way I see it, the 'empty node' abstraction is only used by rbtree users to flag nodes that they haven't inserted in any rbtree, so asking the predecessor or successor of such nodes doesn't make any sense. One final rb_init_node() caller was recently added in sysctl code to implement faster sysctl name lookups. This code doesn't make use of RB_EMPTY_NODE at all, and from what I could see it only called rb_init_node() under the mistaken assumption that such initialization was required before node insertion. [sfr@canb.auug.org.au: fix net/ceph/osd_client.c build] Signed-off-by: Michel Lespinasse Cc: Andrea Arcangeli Acked-by: David Woodhouse Cc: Rik van Riel Cc: Peter Zijlstra Cc: Daniel Santos Cc: Jens Axboe Cc: "Eric W. Biederman" Cc: John Stultz Signed-off-by: Stephen Rothwell Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/rbtree.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'lib') diff --git a/lib/rbtree.c b/lib/rbtree.c index d4175565dc2c..fe43c8c5f527 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -387,7 +387,7 @@ struct rb_node *rb_next(const struct rb_node *node) { struct rb_node *parent; - if (rb_parent(node) == node) + if (RB_EMPTY_NODE(node)) return NULL; /* If we have a right-hand child, go down and then left as far @@ -416,7 +416,7 @@ struct rb_node *rb_prev(const struct rb_node *node) { struct rb_node *parent; - if (rb_parent(node) == node) + if (RB_EMPTY_NODE(node)) return NULL; /* If we have a left-hand child, go down and then right as far -- cgit v1.2.1 From bf7ad8eeab995710c766df49c9c69a8592ca0216 Mon Sep 17 00:00:00 2001 From: Michel Lespinasse Date: Mon, 8 Oct 2012 16:30:37 -0700 Subject: rbtree: move some implementation details from rbtree.h to rbtree.c rbtree users must use the documented APIs to manipulate the tree structure. Low-level helpers to manipulate node colors and parenthood are not part of that API, so move them to lib/rbtree.c [dwmw2@infradead.org: fix jffs2 build issue due to renamed __rb_parent_color field] Signed-off-by: Michel Lespinasse Cc: Andrea Arcangeli Acked-by: David Woodhouse Cc: Rik van Riel Cc: Peter Zijlstra Cc: Daniel Santos Cc: Jens Axboe Cc: "Eric W. Biederman" Signed-off-by: David Woodhouse Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/rbtree.c | 20 +++++++++++++++++++- 1 file changed, 19 insertions(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/rbtree.c b/lib/rbtree.c index fe43c8c5f527..ccada9abe6f5 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -23,6 +23,24 @@ #include #include +#define RB_RED 0 +#define RB_BLACK 1 + +#define rb_color(r) ((r)->__rb_parent_color & 1) +#define rb_is_red(r) (!rb_color(r)) +#define rb_is_black(r) rb_color(r) +#define rb_set_red(r) do { (r)->__rb_parent_color &= ~1; } while (0) +#define rb_set_black(r) do { (r)->__rb_parent_color |= 1; } while (0) + +static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p) +{ + rb->__rb_parent_color = rb_color(rb) | (unsigned long)p; +} +static inline void rb_set_color(struct rb_node *rb, int color) +{ + rb->__rb_parent_color = (rb->__rb_parent_color & ~1) | color; +} + static void __rb_rotate_left(struct rb_node *node, struct rb_root *root) { struct rb_node *right = node->rb_right; @@ -255,7 +273,7 @@ void rb_erase(struct rb_node *node, struct rb_root *root) rb_set_parent(old->rb_right, node); } - node->rb_parent_color = old->rb_parent_color; + node->__rb_parent_color = old->__rb_parent_color; node->rb_left = old->rb_left; rb_set_parent(old->rb_left, node); -- cgit v1.2.1 From 910a742d4ba863848c7283d69c21bfa779d3b9a8 Mon Sep 17 00:00:00 2001 From: Michel Lespinasse Date: Mon, 8 Oct 2012 16:30:39 -0700 Subject: rbtree: performance and correctness test This small module helps measure the performance of rbtree insert and erase. Additionally, we run a few correctness tests to check that the rbtrees have all desired properties: - contains the right number of nodes in the order desired, - never two consecutive red nodes on any path, - all paths to leaf nodes have the same number of black nodes, - root node is black [akpm@linux-foundation.org: fix printk warning: sparc64 cycles_t is unsigned long] Signed-off-by: Michel Lespinasse Cc: Andrea Arcangeli Acked-by: David Woodhouse Cc: Rik van Riel Cc: Peter Zijlstra Cc: Daniel Santos Cc: Jens Axboe Cc: "Eric W. Biederman" Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/Kconfig.debug | 7 +++ lib/Makefile | 2 + lib/rbtree_test.c | 135 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 144 insertions(+) create mode 100644 lib/rbtree_test.c (limited to 'lib') diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index b7281e4d1473..a4e5d93b0f41 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -1282,6 +1282,13 @@ config LATENCYTOP source mm/Kconfig.debug source kernel/trace/Kconfig +config RBTREE_TEST + tristate "Red-Black tree test" + depends on m && DEBUG_KERNEL + help + A benchmark measuring the performance of the rbtree library. + Also includes rbtree invariant checks. + config PROVIDE_OHCI1394_DMA_INIT bool "Remote debugging over FireWire early on boot" depends on PCI && X86 diff --git a/lib/Makefile b/lib/Makefile index 42d283edc4d3..f49445d26b65 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -140,6 +140,8 @@ $(foreach file, $(libfdt_files), \ $(eval CFLAGS_$(file) = -I$(src)/../scripts/dtc/libfdt)) lib-$(CONFIG_LIBFDT) += $(libfdt_files) +obj-$(CONFIG_RBTREE_TEST) += rbtree_test.o + hostprogs-y := gen_crc32table clean-files := crc32table.h diff --git a/lib/rbtree_test.c b/lib/rbtree_test.c new file mode 100644 index 000000000000..19dfca9ff7d7 --- /dev/null +++ b/lib/rbtree_test.c @@ -0,0 +1,135 @@ +#include +#include +#include +#include + +#define NODES 100 +#define PERF_LOOPS 100000 +#define CHECK_LOOPS 100 + +struct test_node { + struct rb_node rb; + u32 key; +}; + +static struct rb_root root = RB_ROOT; +static struct test_node nodes[NODES]; + +static struct rnd_state rnd; + +static void insert(struct test_node *node, struct rb_root *root) +{ + struct rb_node **new = &root->rb_node, *parent = NULL; + + while (*new) { + parent = *new; + if (node->key < rb_entry(parent, struct test_node, rb)->key) + new = &parent->rb_left; + else + new = &parent->rb_right; + } + + rb_link_node(&node->rb, parent, new); + rb_insert_color(&node->rb, root); +} + +static inline void erase(struct test_node *node, struct rb_root *root) +{ + rb_erase(&node->rb, root); +} + +static void init(void) +{ + int i; + for (i = 0; i < NODES; i++) + nodes[i].key = prandom32(&rnd); +} + +static bool is_red(struct rb_node *rb) +{ + return !(rb->__rb_parent_color & 1); +} + +static int black_path_count(struct rb_node *rb) +{ + int count; + for (count = 0; rb; rb = rb_parent(rb)) + count += !is_red(rb); + return count; +} + +static void check(int nr_nodes) +{ + struct rb_node *rb; + int count = 0; + int blacks; + u32 prev_key = 0; + + for (rb = rb_first(&root); rb; rb = rb_next(rb)) { + struct test_node *node = rb_entry(rb, struct test_node, rb); + WARN_ON_ONCE(node->key < prev_key); + WARN_ON_ONCE(is_red(rb) && + (!rb_parent(rb) || is_red(rb_parent(rb)))); + if (!count) + blacks = black_path_count(rb); + else + WARN_ON_ONCE((!rb->rb_left || !rb->rb_right) && + blacks != black_path_count(rb)); + prev_key = node->key; + count++; + } + WARN_ON_ONCE(count != nr_nodes); +} + +static int rbtree_test_init(void) +{ + int i, j; + cycles_t time1, time2, time; + + printk(KERN_ALERT "rbtree testing"); + + prandom32_seed(&rnd, 3141592653589793238); + init(); + + time1 = get_cycles(); + + for (i = 0; i < PERF_LOOPS; i++) { + for (j = 0; j < NODES; j++) + insert(nodes + j, &root); + for (j = 0; j < NODES; j++) + erase(nodes + j, &root); + } + + time2 = get_cycles(); + time = time2 - time1; + + time = div_u64(time, PERF_LOOPS); + printk(" -> %llu cycles\n", (unsigned long long)time); + + for (i = 0; i < CHECK_LOOPS; i++) { + init(); + for (j = 0; j < NODES; j++) { + check(j); + insert(nodes + j, &root); + } + for (j = 0; j < NODES; j++) { + check(NODES - j); + erase(nodes + j, &root); + } + check(0); + } + + return -EAGAIN; /* Fail will directly unload the module */ +} + +static void rbtree_test_exit(void) +{ + printk(KERN_ALERT "test exit\n"); +} + +module_init(rbtree_test_init) +module_exit(rbtree_test_exit) + +MODULE_LICENSE("GPL"); +MODULE_AUTHOR("Michel Lespinasse"); +MODULE_DESCRIPTION("Red Black Tree test"); -- cgit v1.2.1 From 1f0528653e41ec230c60f5738820e8a544731399 Mon Sep 17 00:00:00 2001 From: Michel Lespinasse Date: Mon, 8 Oct 2012 16:30:42 -0700 Subject: rbtree: break out of rb_insert_color loop after tree rotation It is a well known property of rbtrees that insertion never requires more than two tree rotations. In our implementation, after one loop iteration identified one or two necessary tree rotations, we would iterate and look for more. However at that point the node's parent would always be black, which would cause us to exit the loop. We can make the code flow more obvious by just adding a break statement after the tree rotations, where we know we are done. Additionally, in the cases where two tree rotations are necessary, we don't have to update the 'node' pointer as it wouldn't be used until the next loop iteration, which we now avoid due to this break statement. Signed-off-by: Michel Lespinasse Cc: Andrea Arcangeli Acked-by: David Woodhouse Cc: Rik van Riel Cc: Peter Zijlstra Cc: Daniel Santos Cc: Jens Axboe Cc: "Eric W. Biederman" Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/rbtree.c | 14 ++++---------- 1 file changed, 4 insertions(+), 10 deletions(-) (limited to 'lib') diff --git a/lib/rbtree.c b/lib/rbtree.c index ccada9abe6f5..12abb8abf442 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -109,18 +109,15 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root) } } - if (parent->rb_right == node) - { - register struct rb_node *tmp; + if (parent->rb_right == node) { __rb_rotate_left(parent, root); - tmp = parent; parent = node; - node = tmp; } rb_set_black(parent); rb_set_red(gparent); __rb_rotate_right(gparent, root); + break; } else { { register struct rb_node *uncle = gparent->rb_left; @@ -134,18 +131,15 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root) } } - if (parent->rb_left == node) - { - register struct rb_node *tmp; + if (parent->rb_left == node) { __rb_rotate_right(parent, root); - tmp = parent; parent = node; - node = tmp; } rb_set_black(parent); rb_set_red(gparent); __rb_rotate_left(gparent, root); + break; } } -- cgit v1.2.1 From 6d58452dc066db61acdff7b84671db1b11a3de1c Mon Sep 17 00:00:00 2001 From: Michel Lespinasse Date: Mon, 8 Oct 2012 16:30:44 -0700 Subject: rbtree: adjust root color in rb_insert_color() only when necessary The root node of an rbtree must always be black. However, rb_insert_color() only needs to maintain this invariant when it has been broken - that is, when it exits the loop due to the current (red) node being the root. In all other cases (exiting after tree rotations, or exiting due to an existing black parent) the invariant is already satisfied, so there is no need to adjust the root node color. Signed-off-by: Michel Lespinasse Cc: Andrea Arcangeli Acked-by: David Woodhouse Cc: Rik van Riel Cc: Peter Zijlstra Cc: Daniel Santos Cc: Jens Axboe Cc: "Eric W. Biederman" Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/rbtree.c | 19 +++++++++++++++---- 1 file changed, 15 insertions(+), 4 deletions(-) (limited to 'lib') diff --git a/lib/rbtree.c b/lib/rbtree.c index 12abb8abf442..d0be5fcaafe8 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -91,8 +91,21 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root) { struct rb_node *parent, *gparent; - while ((parent = rb_parent(node)) && rb_is_red(parent)) - { + while (true) { + /* + * Loop invariant: node is red + * + * If there is a black parent, we are done. + * Otherwise, take some corrective action as we don't + * want a red root or two consecutive red nodes. + */ + parent = rb_parent(node); + if (!parent) { + rb_set_black(node); + break; + } else if (rb_is_black(parent)) + break; + gparent = rb_parent(parent); if (parent == gparent->rb_left) @@ -142,8 +155,6 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root) break; } } - - rb_set_black(root->rb_node); } EXPORT_SYMBOL(rb_insert_color); -- cgit v1.2.1 From 5bc9188aa207dafd47eab57df7c4fe5b3d3f636a Mon Sep 17 00:00:00 2001 From: Michel Lespinasse Date: Mon, 8 Oct 2012 16:30:47 -0700 Subject: rbtree: low level optimizations in rb_insert_color() - Use the newly introduced rb_set_parent_color() function to flip the color of nodes whose parent is already known. - Optimize rb_parent() when the node is known to be red - there is no need to mask out the color in that case. - Flipping gparent's color to red requires us to fetch its rb_parent_color field, so we can reuse it as the parent value for the next loop iteration. - Do not use __rb_rotate_left() and __rb_rotate_right() to handle tree rotations: we already have pointers to all relevant nodes, and know their colors (either because we want to adjust it, or because we've tested it, or we can deduce it as black due to the node proximity to a known red node). So we can generate more efficient code by making use of the node pointers we already have, and setting both the parent and color attributes for nodes all at once. Also in Case 2, some node attributes don't have to be set because we know another tree rotation (Case 3) will always follow and override them. Signed-off-by: Michel Lespinasse Cc: Andrea Arcangeli Acked-by: David Woodhouse Cc: Rik van Riel Cc: Peter Zijlstra Cc: Daniel Santos Cc: Jens Axboe Cc: "Eric W. Biederman" Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/rbtree.c | 166 ++++++++++++++++++++++++++++++++++++++++++++++------------- 1 file changed, 131 insertions(+), 35 deletions(-) (limited to 'lib') diff --git a/lib/rbtree.c b/lib/rbtree.c index d0be5fcaafe8..41cf19b2fe51 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -23,6 +23,25 @@ #include #include +/* + * red-black trees properties: http://en.wikipedia.org/wiki/Rbtree + * + * 1) A node is either red or black + * 2) The root is black + * 3) All leaves (NULL) are black + * 4) Both children of every red node are black + * 5) Every simple path from root to leaves contains the same number + * of black nodes. + * + * 4 and 5 give the O(log n) guarantee, since 4 implies you cannot have two + * consecutive red nodes in a path and every red node is therefore followed by + * a black. So if B is the number of black nodes on every simple path (as per + * 5), then the longest possible path due to 4 is 2B. + * + * We shall indicate color with case, where black nodes are uppercase and red + * nodes will be lowercase. + */ + #define RB_RED 0 #define RB_BLACK 1 @@ -41,6 +60,17 @@ static inline void rb_set_color(struct rb_node *rb, int color) rb->__rb_parent_color = (rb->__rb_parent_color & ~1) | color; } +static inline void rb_set_parent_color(struct rb_node *rb, + struct rb_node *p, int color) +{ + rb->__rb_parent_color = (unsigned long)p | color; +} + +static inline struct rb_node *rb_red_parent(struct rb_node *red) +{ + return (struct rb_node *)red->__rb_parent_color; +} + static void __rb_rotate_left(struct rb_node *node, struct rb_root *root) { struct rb_node *right = node->rb_right; @@ -87,9 +117,30 @@ static void __rb_rotate_right(struct rb_node *node, struct rb_root *root) rb_set_parent(node, left); } +/* + * Helper function for rotations: + * - old's parent and color get assigned to new + * - old gets assigned new as a parent and 'color' as a color. + */ +static inline void +__rb_rotate_set_parents(struct rb_node *old, struct rb_node *new, + struct rb_root *root, int color) +{ + struct rb_node *parent = rb_parent(old); + new->__rb_parent_color = old->__rb_parent_color; + rb_set_parent_color(old, new, color); + if (parent) { + if (parent->rb_left == old) + parent->rb_left = new; + else + parent->rb_right = new; + } else + root->rb_node = new; +} + void rb_insert_color(struct rb_node *node, struct rb_root *root) { - struct rb_node *parent, *gparent; + struct rb_node *parent = rb_red_parent(node), *gparent, *tmp; while (true) { /* @@ -99,59 +150,104 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root) * Otherwise, take some corrective action as we don't * want a red root or two consecutive red nodes. */ - parent = rb_parent(node); if (!parent) { - rb_set_black(node); + rb_set_parent_color(node, NULL, RB_BLACK); break; } else if (rb_is_black(parent)) break; - gparent = rb_parent(parent); - - if (parent == gparent->rb_left) - { - { - register struct rb_node *uncle = gparent->rb_right; - if (uncle && rb_is_red(uncle)) - { - rb_set_black(uncle); - rb_set_black(parent); - rb_set_red(gparent); - node = gparent; - continue; - } + gparent = rb_red_parent(parent); + + if (parent == gparent->rb_left) { + tmp = gparent->rb_right; + if (tmp && rb_is_red(tmp)) { + /* + * Case 1 - color flips + * + * G g + * / \ / \ + * p u --> P U + * / / + * n N + * + * However, since g's parent might be red, and + * 4) does not allow this, we need to recurse + * at g. + */ + rb_set_parent_color(tmp, gparent, RB_BLACK); + rb_set_parent_color(parent, gparent, RB_BLACK); + node = gparent; + parent = rb_parent(node); + rb_set_parent_color(node, parent, RB_RED); + continue; } if (parent->rb_right == node) { - __rb_rotate_left(parent, root); + /* + * Case 2 - left rotate at parent + * + * G G + * / \ / \ + * p U --> n U + * \ / + * n p + * + * This still leaves us in violation of 4), the + * continuation into Case 3 will fix that. + */ + parent->rb_right = tmp = node->rb_left; + node->rb_left = parent; + if (tmp) + rb_set_parent_color(tmp, parent, + RB_BLACK); + rb_set_parent_color(parent, node, RB_RED); parent = node; } - rb_set_black(parent); - rb_set_red(gparent); - __rb_rotate_right(gparent, root); + /* + * Case 3 - right rotate at gparent + * + * G P + * / \ / \ + * p U --> n g + * / \ + * n U + */ + gparent->rb_left = tmp = parent->rb_right; + parent->rb_right = gparent; + if (tmp) + rb_set_parent_color(tmp, gparent, RB_BLACK); + __rb_rotate_set_parents(gparent, parent, root, RB_RED); break; } else { - { - register struct rb_node *uncle = gparent->rb_left; - if (uncle && rb_is_red(uncle)) - { - rb_set_black(uncle); - rb_set_black(parent); - rb_set_red(gparent); - node = gparent; - continue; - } + tmp = gparent->rb_left; + if (tmp && rb_is_red(tmp)) { + /* Case 1 - color flips */ + rb_set_parent_color(tmp, gparent, RB_BLACK); + rb_set_parent_color(parent, gparent, RB_BLACK); + node = gparent; + parent = rb_parent(node); + rb_set_parent_color(node, parent, RB_RED); + continue; } if (parent->rb_left == node) { - __rb_rotate_right(parent, root); + /* Case 2 - right rotate at parent */ + parent->rb_left = tmp = node->rb_right; + node->rb_right = parent; + if (tmp) + rb_set_parent_color(tmp, parent, + RB_BLACK); + rb_set_parent_color(parent, node, RB_RED); parent = node; } - rb_set_black(parent); - rb_set_red(gparent); - __rb_rotate_left(gparent, root); + /* Case 3 - left rotate at gparent */ + gparent->rb_right = tmp = parent->rb_left; + parent->rb_left = gparent; + if (tmp) + rb_set_parent_color(tmp, gparent, RB_BLACK); + __rb_rotate_set_parents(gparent, parent, root, RB_RED); break; } } -- cgit v1.2.1 From d6ff1273928ebf15466a85b7e1810cd00e72998b Mon Sep 17 00:00:00 2001 From: Michel Lespinasse Date: Mon, 8 Oct 2012 16:30:50 -0700 Subject: rbtree: adjust node color in __rb_erase_color() only when necessary In __rb_erase_color(), we were always setting a node to black after exiting the main loop. And in one case, after fixing up the tree to satisfy all rbtree invariants, we were setting the current node to root just to guarantee a loop exit, at which point the root would be set to black. However this is not necessary, as the root of an rbtree is already known to be black. The only case where the color flip is required is when we exit the loop due to the current node being red, and it's easiest to just do the flip at that point instead of doing it after the loop. [adrian.hunter@intel.com: perf tools: fix build for another rbtree.c change] Signed-off-by: Michel Lespinasse Cc: Andrea Arcangeli Acked-by: David Woodhouse Cc: Rik van Riel Cc: Peter Zijlstra Cc: Daniel Santos Cc: Jens Axboe Cc: "Eric W. Biederman" Signed-off-by: Adrian Hunter Cc: Alexander Shishkin Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/rbtree.c | 28 +++++++++++++++++----------- 1 file changed, 17 insertions(+), 11 deletions(-) (limited to 'lib') diff --git a/lib/rbtree.c b/lib/rbtree.c index 41cf19b2fe51..baf7c835c57c 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -259,10 +259,22 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, { struct rb_node *other; - while ((!node || rb_is_black(node)) && node != root->rb_node) - { - if (parent->rb_left == node) - { + while (true) { + /* + * Loop invariant: all leaf paths going through node have a + * black node count that is 1 lower than other leaf paths. + * + * If node is red, we can flip it to black to adjust. + * If node is the root, all leaf paths go through it. + * Otherwise, we need to adjust the tree through color flips + * and tree rotations as per one of the 4 cases below. + */ + if (node && rb_is_red(node)) { + rb_set_black(node); + break; + } else if (!parent) { + break; + } else if (parent->rb_left == node) { other = parent->rb_right; if (rb_is_red(other)) { @@ -291,12 +303,9 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, rb_set_black(parent); rb_set_black(other->rb_right); __rb_rotate_left(parent, root); - node = root->rb_node; break; } - } - else - { + } else { other = parent->rb_left; if (rb_is_red(other)) { @@ -325,13 +334,10 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, rb_set_black(parent); rb_set_black(other->rb_left); __rb_rotate_right(parent, root); - node = root->rb_node; break; } } } - if (node) - rb_set_black(node); } void rb_erase(struct rb_node *node, struct rb_root *root) -- cgit v1.2.1 From e125d1471a4f8f1bf7ea9a83deb8d23cb40bd712 Mon Sep 17 00:00:00 2001 From: Michel Lespinasse Date: Mon, 8 Oct 2012 16:30:54 -0700 Subject: rbtree: optimize case selection logic in __rb_erase_color() In __rb_erase_color(), we have to select one of 3 cases depending on the color on the 'other' node children. If both children are black, we flip a few node colors and iterate. Otherwise, we do either one or two tree rotations, depending on the color of the 'other' child opposite to 'node', and then we are done. The corresponding logic had duplicate checks for the color of the 'other' child opposite to 'node'. It was checking it first to determine if both children are black, and then to determine how many tree rotations are required. Rearrange the logic to avoid that extra check. Signed-off-by: Michel Lespinasse Cc: Andrea Arcangeli Acked-by: David Woodhouse Cc: Rik van Riel Cc: Peter Zijlstra Cc: Daniel Santos Cc: Jens Axboe Cc: "Eric W. Biederman" Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/rbtree.c | 68 +++++++++++++++++++++++++++--------------------------------- 1 file changed, 30 insertions(+), 38 deletions(-) (limited to 'lib') diff --git a/lib/rbtree.c b/lib/rbtree.c index baf7c835c57c..eb823a31099c 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -283,28 +283,24 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, __rb_rotate_left(parent, root); other = parent->rb_right; } - if ((!other->rb_left || rb_is_black(other->rb_left)) && - (!other->rb_right || rb_is_black(other->rb_right))) - { - rb_set_red(other); - node = parent; - parent = rb_parent(node); - } - else - { - if (!other->rb_right || rb_is_black(other->rb_right)) - { - rb_set_black(other->rb_left); + if (!other->rb_right || rb_is_black(other->rb_right)) { + if (!other->rb_left || + rb_is_black(other->rb_left)) { rb_set_red(other); - __rb_rotate_right(other, root); - other = parent->rb_right; + node = parent; + parent = rb_parent(node); + continue; } - rb_set_color(other, rb_color(parent)); - rb_set_black(parent); - rb_set_black(other->rb_right); - __rb_rotate_left(parent, root); - break; + rb_set_black(other->rb_left); + rb_set_red(other); + __rb_rotate_right(other, root); + other = parent->rb_right; } + rb_set_color(other, rb_color(parent)); + rb_set_black(parent); + rb_set_black(other->rb_right); + __rb_rotate_left(parent, root); + break; } else { other = parent->rb_left; if (rb_is_red(other)) @@ -314,28 +310,24 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, __rb_rotate_right(parent, root); other = parent->rb_left; } - if ((!other->rb_left || rb_is_black(other->rb_left)) && - (!other->rb_right || rb_is_black(other->rb_right))) - { - rb_set_red(other); - node = parent; - parent = rb_parent(node); - } - else - { - if (!other->rb_left || rb_is_black(other->rb_left)) - { - rb_set_black(other->rb_right); + if (!other->rb_left || rb_is_black(other->rb_left)) { + if (!other->rb_right || + rb_is_black(other->rb_right)) { rb_set_red(other); - __rb_rotate_left(other, root); - other = parent->rb_left; + node = parent; + parent = rb_parent(node); + continue; } - rb_set_color(other, rb_color(parent)); - rb_set_black(parent); - rb_set_black(other->rb_left); - __rb_rotate_right(parent, root); - break; + rb_set_black(other->rb_right); + rb_set_red(other); + __rb_rotate_left(other, root); + other = parent->rb_left; } + rb_set_color(other, rb_color(parent)); + rb_set_black(parent); + rb_set_black(other->rb_left); + __rb_rotate_right(parent, root); + break; } } } -- cgit v1.2.1 From 6280d2356fd8ad0936a63c10dc1e6accf48d0c61 Mon Sep 17 00:00:00 2001 From: Michel Lespinasse Date: Mon, 8 Oct 2012 16:30:57 -0700 Subject: rbtree: low level optimizations in __rb_erase_color() In __rb_erase_color(), we often already have pointers to the nodes being rotated and/or know what their colors must be, so we can generate more efficient code than the generic __rb_rotate_left() and __rb_rotate_right() functions. Also when the current node is red or when flipping the sibling's color, the parent is already known so we can use the more efficient rb_set_parent_color() function to set the desired color. Signed-off-by: Michel Lespinasse Cc: Andrea Arcangeli Acked-by: David Woodhouse Cc: Rik van Riel Cc: Peter Zijlstra Cc: Daniel Santos Cc: Jens Axboe Cc: "Eric W. Biederman" Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/rbtree.c | 208 +++++++++++++++++++++++++++++++++-------------------------- 1 file changed, 115 insertions(+), 93 deletions(-) (limited to 'lib') diff --git a/lib/rbtree.c b/lib/rbtree.c index eb823a31099c..a38e473d8fe7 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -39,7 +39,8 @@ * 5), then the longest possible path due to 4 is 2B. * * We shall indicate color with case, where black nodes are uppercase and red - * nodes will be lowercase. + * nodes will be lowercase. Unknown color nodes shall be drawn as red within + * parentheses and have some accompanying text comment. */ #define RB_RED 0 @@ -48,17 +49,11 @@ #define rb_color(r) ((r)->__rb_parent_color & 1) #define rb_is_red(r) (!rb_color(r)) #define rb_is_black(r) rb_color(r) -#define rb_set_red(r) do { (r)->__rb_parent_color &= ~1; } while (0) -#define rb_set_black(r) do { (r)->__rb_parent_color |= 1; } while (0) static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p) { rb->__rb_parent_color = rb_color(rb) | (unsigned long)p; } -static inline void rb_set_color(struct rb_node *rb, int color) -{ - rb->__rb_parent_color = (rb->__rb_parent_color & ~1) | color; -} static inline void rb_set_parent_color(struct rb_node *rb, struct rb_node *p, int color) @@ -71,52 +66,6 @@ static inline struct rb_node *rb_red_parent(struct rb_node *red) return (struct rb_node *)red->__rb_parent_color; } -static void __rb_rotate_left(struct rb_node *node, struct rb_root *root) -{ - struct rb_node *right = node->rb_right; - struct rb_node *parent = rb_parent(node); - - if ((node->rb_right = right->rb_left)) - rb_set_parent(right->rb_left, node); - right->rb_left = node; - - rb_set_parent(right, parent); - - if (parent) - { - if (node == parent->rb_left) - parent->rb_left = right; - else - parent->rb_right = right; - } - else - root->rb_node = right; - rb_set_parent(node, right); -} - -static void __rb_rotate_right(struct rb_node *node, struct rb_root *root) -{ - struct rb_node *left = node->rb_left; - struct rb_node *parent = rb_parent(node); - - if ((node->rb_left = left->rb_right)) - rb_set_parent(left->rb_right, node); - left->rb_right = node; - - rb_set_parent(left, parent); - - if (parent) - { - if (node == parent->rb_right) - parent->rb_right = left; - else - parent->rb_left = left; - } - else - root->rb_node = left; - rb_set_parent(node, left); -} - /* * Helper function for rotations: * - old's parent and color get assigned to new @@ -257,7 +206,7 @@ EXPORT_SYMBOL(rb_insert_color); static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, struct rb_root *root) { - struct rb_node *other; + struct rb_node *sibling, *tmp1, *tmp2; while (true) { /* @@ -270,63 +219,136 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, * and tree rotations as per one of the 4 cases below. */ if (node && rb_is_red(node)) { - rb_set_black(node); + rb_set_parent_color(node, parent, RB_BLACK); break; } else if (!parent) { break; } else if (parent->rb_left == node) { - other = parent->rb_right; - if (rb_is_red(other)) - { - rb_set_black(other); - rb_set_red(parent); - __rb_rotate_left(parent, root); - other = parent->rb_right; + sibling = parent->rb_right; + if (rb_is_red(sibling)) { + /* + * Case 1 - left rotate at parent + * + * P S + * / \ / \ + * N s --> p Sr + * / \ / \ + * Sl Sr N Sl + */ + parent->rb_right = tmp1 = sibling->rb_left; + sibling->rb_left = parent; + rb_set_parent_color(tmp1, parent, RB_BLACK); + __rb_rotate_set_parents(parent, sibling, root, + RB_RED); + sibling = tmp1; } - if (!other->rb_right || rb_is_black(other->rb_right)) { - if (!other->rb_left || - rb_is_black(other->rb_left)) { - rb_set_red(other); + tmp1 = sibling->rb_right; + if (!tmp1 || rb_is_black(tmp1)) { + tmp2 = sibling->rb_left; + if (!tmp2 || rb_is_black(tmp2)) { + /* + * Case 2 - sibling color flip + * (p could be either color here) + * + * (p) (p) + * / \ / \ + * N S --> N s + * / \ / \ + * Sl Sr Sl Sr + * + * This leaves us violating 5), so + * recurse at p. If p is red, the + * recursion will just flip it to black + * and exit. If coming from Case 1, + * p is known to be red. + */ + rb_set_parent_color(sibling, parent, + RB_RED); node = parent; parent = rb_parent(node); continue; } - rb_set_black(other->rb_left); - rb_set_red(other); - __rb_rotate_right(other, root); - other = parent->rb_right; + /* + * Case 3 - right rotate at sibling + * (p could be either color here) + * + * (p) (p) + * / \ / \ + * N S --> N Sl + * / \ \ + * sl Sr s + * \ + * Sr + */ + sibling->rb_left = tmp1 = tmp2->rb_right; + tmp2->rb_right = sibling; + parent->rb_right = tmp2; + if (tmp1) + rb_set_parent_color(tmp1, sibling, + RB_BLACK); + tmp1 = sibling; + sibling = tmp2; } - rb_set_color(other, rb_color(parent)); - rb_set_black(parent); - rb_set_black(other->rb_right); - __rb_rotate_left(parent, root); + /* + * Case 4 - left rotate at parent + color flips + * (p and sl could be either color here. + * After rotation, p becomes black, s acquires + * p's color, and sl keeps its color) + * + * (p) (s) + * / \ / \ + * N S --> P Sr + * / \ / \ + * (sl) sr N (sl) + */ + parent->rb_right = tmp2 = sibling->rb_left; + sibling->rb_left = parent; + rb_set_parent_color(tmp1, sibling, RB_BLACK); + if (tmp2) + rb_set_parent(tmp2, parent); + __rb_rotate_set_parents(parent, sibling, root, + RB_BLACK); break; } else { - other = parent->rb_left; - if (rb_is_red(other)) - { - rb_set_black(other); - rb_set_red(parent); - __rb_rotate_right(parent, root); - other = parent->rb_left; + sibling = parent->rb_left; + if (rb_is_red(sibling)) { + /* Case 1 - right rotate at parent */ + parent->rb_left = tmp1 = sibling->rb_right; + sibling->rb_right = parent; + rb_set_parent_color(tmp1, parent, RB_BLACK); + __rb_rotate_set_parents(parent, sibling, root, + RB_RED); + sibling = tmp1; } - if (!other->rb_left || rb_is_black(other->rb_left)) { - if (!other->rb_right || - rb_is_black(other->rb_right)) { - rb_set_red(other); + tmp1 = sibling->rb_left; + if (!tmp1 || rb_is_black(tmp1)) { + tmp2 = sibling->rb_right; + if (!tmp2 || rb_is_black(tmp2)) { + /* Case 2 - sibling color flip */ + rb_set_parent_color(sibling, parent, + RB_RED); node = parent; parent = rb_parent(node); continue; } - rb_set_black(other->rb_right); - rb_set_red(other); - __rb_rotate_left(other, root); - other = parent->rb_left; + /* Case 3 - right rotate at sibling */ + sibling->rb_right = tmp1 = tmp2->rb_left; + tmp2->rb_left = sibling; + parent->rb_left = tmp2; + if (tmp1) + rb_set_parent_color(tmp1, sibling, + RB_BLACK); + tmp1 = sibling; + sibling = tmp2; } - rb_set_color(other, rb_color(parent)); - rb_set_black(parent); - rb_set_black(other->rb_left); - __rb_rotate_right(parent, root); + /* Case 4 - left rotate at parent + color flips */ + parent->rb_left = tmp2 = sibling->rb_right; + sibling->rb_right = parent; + rb_set_parent_color(tmp1, sibling, RB_BLACK); + if (tmp2) + rb_set_parent(tmp2, parent); + __rb_rotate_set_parents(parent, sibling, root, + RB_BLACK); break; } } -- cgit v1.2.1 From 7ce6ff9e5de99e7b72019c7de82fb438fe1dc5a0 Mon Sep 17 00:00:00 2001 From: Michel Lespinasse Date: Mon, 8 Oct 2012 16:31:01 -0700 Subject: rbtree: coding style adjustments Set comment and indentation style to be consistent with linux coding style and the rest of the file, as suggested by Peter Zijlstra Signed-off-by: Michel Lespinasse Cc: Andrea Arcangeli Acked-by: David Woodhouse Cc: Rik van Riel Cc: Peter Zijlstra Cc: Daniel Santos Cc: Jens Axboe Cc: "Eric W. Biederman" Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/rbtree.c | 42 +++++++++++++++++++++++------------------- 1 file changed, 23 insertions(+), 19 deletions(-) (limited to 'lib') diff --git a/lib/rbtree.c b/lib/rbtree.c index a38e473d8fe7..08926709b4f9 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -363,8 +363,7 @@ void rb_erase(struct rb_node *node, struct rb_root *root) child = node->rb_right; else if (!node->rb_right) child = node->rb_left; - else - { + else { struct rb_node *old = node, *left; node = node->rb_right; @@ -406,17 +405,15 @@ void rb_erase(struct rb_node *node, struct rb_root *root) if (child) rb_set_parent(child, parent); - if (parent) - { + if (parent) { if (parent->rb_left == node) parent->rb_left = child; else parent->rb_right = child; - } - else + } else root->rb_node = child; - color: +color: if (color == RB_BLACK) __rb_erase_color(child, parent, root); } @@ -529,8 +526,10 @@ struct rb_node *rb_next(const struct rb_node *node) if (RB_EMPTY_NODE(node)) return NULL; - /* If we have a right-hand child, go down and then left as far - as we can. */ + /* + * If we have a right-hand child, go down and then left as far + * as we can. + */ if (node->rb_right) { node = node->rb_right; while (node->rb_left) @@ -538,12 +537,13 @@ struct rb_node *rb_next(const struct rb_node *node) return (struct rb_node *)node; } - /* No right-hand children. Everything down and left is - smaller than us, so any 'next' node must be in the general - direction of our parent. Go up the tree; any time the - ancestor is a right-hand child of its parent, keep going - up. First time it's a left-hand child of its parent, said - parent is our 'next' node. */ + /* + * No right-hand children. Everything down and left is smaller than us, + * so any 'next' node must be in the general direction of our parent. + * Go up the tree; any time the ancestor is a right-hand child of its + * parent, keep going up. First time it's a left-hand child of its + * parent, said parent is our 'next' node. + */ while ((parent = rb_parent(node)) && node == parent->rb_right) node = parent; @@ -558,8 +558,10 @@ struct rb_node *rb_prev(const struct rb_node *node) if (RB_EMPTY_NODE(node)) return NULL; - /* If we have a left-hand child, go down and then right as far - as we can. */ + /* + * If we have a left-hand child, go down and then right as far + * as we can. + */ if (node->rb_left) { node = node->rb_left; while (node->rb_right) @@ -567,8 +569,10 @@ struct rb_node *rb_prev(const struct rb_node *node) return (struct rb_node *)node; } - /* No left-hand children. Go up till we find an ancestor which - is a right-hand child of its parent */ + /* + * No left-hand children. Go up till we find an ancestor which + * is a right-hand child of its parent. + */ while ((parent = rb_parent(node)) && node == parent->rb_left) node = parent; -- cgit v1.2.1 From 59633abf34e2f44b8e772a2c12a92132aa7c2220 Mon Sep 17 00:00:00 2001 From: Michel Lespinasse Date: Mon, 8 Oct 2012 16:31:02 -0700 Subject: rbtree: optimize fetching of sibling node When looking to fetch a node's sibling, we went through a sequence of: - check if node is the parent's left child - if it is, then fetch the parent's right child This can be replaced with: - fetch the parent's right child as an assumed sibling - check that node is NOT the fetched child This avoids fetching the parent's left child when node is actually that child. Saves a bit on code size, though it doesn't seem to make a large difference in speed. Signed-off-by: Michel Lespinasse Cc: Andrea Arcangeli Cc: David Woodhouse Acked-by: Rik van Riel Cc: Peter Zijlstra Cc: Daniel Santos Cc: Jens Axboe Cc: "Eric W. Biederman" Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/rbtree.c | 21 +++++++++++++-------- 1 file changed, 13 insertions(+), 8 deletions(-) (limited to 'lib') diff --git a/lib/rbtree.c b/lib/rbtree.c index 08926709b4f9..61cdd0e3e538 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -107,8 +107,8 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root) gparent = rb_red_parent(parent); - if (parent == gparent->rb_left) { - tmp = gparent->rb_right; + tmp = gparent->rb_right; + if (parent != tmp) { /* parent == gparent->rb_left */ if (tmp && rb_is_red(tmp)) { /* * Case 1 - color flips @@ -131,7 +131,8 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root) continue; } - if (parent->rb_right == node) { + tmp = parent->rb_right; + if (node == tmp) { /* * Case 2 - left rotate at parent * @@ -151,6 +152,7 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root) RB_BLACK); rb_set_parent_color(parent, node, RB_RED); parent = node; + tmp = node->rb_right; } /* @@ -162,7 +164,7 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root) * / \ * n U */ - gparent->rb_left = tmp = parent->rb_right; + gparent->rb_left = tmp; /* == parent->rb_right */ parent->rb_right = gparent; if (tmp) rb_set_parent_color(tmp, gparent, RB_BLACK); @@ -180,7 +182,8 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root) continue; } - if (parent->rb_left == node) { + tmp = parent->rb_left; + if (node == tmp) { /* Case 2 - right rotate at parent */ parent->rb_left = tmp = node->rb_right; node->rb_right = parent; @@ -189,10 +192,11 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root) RB_BLACK); rb_set_parent_color(parent, node, RB_RED); parent = node; + tmp = node->rb_left; } /* Case 3 - left rotate at gparent */ - gparent->rb_right = tmp = parent->rb_left; + gparent->rb_right = tmp; /* == parent->rb_left */ parent->rb_left = gparent; if (tmp) rb_set_parent_color(tmp, gparent, RB_BLACK); @@ -223,8 +227,9 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, break; } else if (!parent) { break; - } else if (parent->rb_left == node) { - sibling = parent->rb_right; + } + sibling = parent->rb_right; + if (node != sibling) { /* node == parent->rb_left */ if (rb_is_red(sibling)) { /* * Case 1 - left rotate at parent -- cgit v1.2.1 From 28d7530928d01638678f63c3c70113540b0e6abe Mon Sep 17 00:00:00 2001 From: Michel Lespinasse Date: Mon, 8 Oct 2012 16:31:04 -0700 Subject: rbtree test: fix sparse warning about 64-bit constant Just a small fix to make sparse happy. Signed-off-by: Michel Lespinasse Reported-by: Fengguang Wu Acked-by: Rik van Riel Cc: Peter Zijlstra Cc: Andrea Arcangeli Cc: David Woodhouse Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/rbtree_test.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/rbtree_test.c b/lib/rbtree_test.c index 19dfca9ff7d7..fd09465d82ca 100644 --- a/lib/rbtree_test.c +++ b/lib/rbtree_test.c @@ -88,7 +88,7 @@ static int rbtree_test_init(void) printk(KERN_ALERT "rbtree testing"); - prandom32_seed(&rnd, 3141592653589793238); + prandom32_seed(&rnd, 3141592653589793238ULL); init(); time1 = get_cycles(); -- cgit v1.2.1 From 7abc704ae399fcb9c51ca200b0456f8a975a8011 Mon Sep 17 00:00:00 2001 From: Michel Lespinasse Date: Mon, 8 Oct 2012 16:31:07 -0700 Subject: rbtree: add __rb_change_child() helper function Add __rb_change_child() as an inline helper function to replace code that would otherwise be duplicated 4 times in the source. No changes to binary size or speed. Signed-off-by: Michel Lespinasse Reviewed-by: Rik van Riel Cc: Peter Zijlstra Cc: Andrea Arcangeli Cc: David Woodhouse Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/rbtree.c | 46 +++++++++++++++++----------------------------- 1 file changed, 17 insertions(+), 29 deletions(-) (limited to 'lib') diff --git a/lib/rbtree.c b/lib/rbtree.c index 61cdd0e3e538..de89a614b1ba 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -66,6 +66,19 @@ static inline struct rb_node *rb_red_parent(struct rb_node *red) return (struct rb_node *)red->__rb_parent_color; } +static inline void +__rb_change_child(struct rb_node *old, struct rb_node *new, + struct rb_node *parent, struct rb_root *root) +{ + if (parent) { + if (parent->rb_left == old) + parent->rb_left = new; + else + parent->rb_right = new; + } else + root->rb_node = new; +} + /* * Helper function for rotations: * - old's parent and color get assigned to new @@ -78,13 +91,7 @@ __rb_rotate_set_parents(struct rb_node *old, struct rb_node *new, struct rb_node *parent = rb_parent(old); new->__rb_parent_color = old->__rb_parent_color; rb_set_parent_color(old, new, color); - if (parent) { - if (parent->rb_left == old) - parent->rb_left = new; - else - parent->rb_right = new; - } else - root->rb_node = new; + __rb_change_child(old, new, parent, root); } void rb_insert_color(struct rb_node *node, struct rb_root *root) @@ -375,13 +382,7 @@ void rb_erase(struct rb_node *node, struct rb_root *root) while ((left = node->rb_left) != NULL) node = left; - if (rb_parent(old)) { - if (rb_parent(old)->rb_left == old) - rb_parent(old)->rb_left = node; - else - rb_parent(old)->rb_right = node; - } else - root->rb_node = node; + __rb_change_child(old, node, rb_parent(old), root); child = node->rb_right; parent = rb_parent(node); @@ -410,13 +411,7 @@ void rb_erase(struct rb_node *node, struct rb_root *root) if (child) rb_set_parent(child, parent); - if (parent) { - if (parent->rb_left == node) - parent->rb_left = child; - else - parent->rb_right = child; - } else - root->rb_node = child; + __rb_change_child(node, child, parent, root); color: if (color == RB_BLACK) @@ -591,14 +586,7 @@ void rb_replace_node(struct rb_node *victim, struct rb_node *new, struct rb_node *parent = rb_parent(victim); /* Set the surrounding nodes to point to the replacement */ - if (parent) { - if (victim == parent->rb_left) - parent->rb_left = new; - else - parent->rb_right = new; - } else { - root->rb_node = new; - } + __rb_change_child(victim, new, parent, root); if (victim->rb_left) rb_set_parent(victim->rb_left, new); if (victim->rb_right) -- cgit v1.2.1 From 60670b8034d6e2ba860af79c9379b7788d09db73 Mon Sep 17 00:00:00 2001 From: Michel Lespinasse Date: Mon, 8 Oct 2012 16:31:10 -0700 Subject: rbtree: place easiest case first in rb_erase() In rb_erase, move the easy case (node to erase has no more than 1 child) first. I feel the code reads easier that way. Signed-off-by: Michel Lespinasse Reviewed-by: Rik van Riel Cc: Peter Zijlstra Cc: Andrea Arcangeli Cc: David Woodhouse Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/rbtree.c | 35 ++++++++++++++++++----------------- 1 file changed, 18 insertions(+), 17 deletions(-) (limited to 'lib') diff --git a/lib/rbtree.c b/lib/rbtree.c index de89a614b1ba..bde1b5c5fb33 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -368,17 +368,28 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, void rb_erase(struct rb_node *node, struct rb_root *root) { - struct rb_node *child, *parent; + struct rb_node *child = node->rb_right, *tmp = node->rb_left; + struct rb_node *parent; int color; - if (!node->rb_left) - child = node->rb_right; - else if (!node->rb_right) - child = node->rb_left; - else { + if (!tmp) { + case1: + /* Case 1: node to erase has no more than 1 child (easy!) */ + + parent = rb_parent(node); + color = rb_color(node); + + if (child) + rb_set_parent(child, parent); + __rb_change_child(node, child, parent, root); + } else if (!child) { + /* Still case 1, but this time the child is node->rb_left */ + child = tmp; + goto case1; + } else { struct rb_node *old = node, *left; - node = node->rb_right; + node = child; while ((left = node->rb_left) != NULL) node = left; @@ -402,18 +413,8 @@ void rb_erase(struct rb_node *node, struct rb_root *root) node->__rb_parent_color = old->__rb_parent_color; node->rb_left = old->rb_left; rb_set_parent(old->rb_left, node); - - goto color; } - parent = rb_parent(node); - color = rb_color(node); - - if (child) - rb_set_parent(child, parent); - __rb_change_child(node, child, parent, root); - -color: if (color == RB_BLACK) __rb_erase_color(child, parent, root); } -- cgit v1.2.1 From 46b6135a7402ac23c5b25f2bd79b03bab8f98278 Mon Sep 17 00:00:00 2001 From: Michel Lespinasse Date: Mon, 8 Oct 2012 16:31:11 -0700 Subject: rbtree: handle 1-child recoloring in rb_erase() instead of rb_erase_color() An interesting observation for rb_erase() is that when a node has exactly one child, the node must be black and the child must be red. An interesting consequence is that removing such a node can be done by simply replacing it with its child and making the child black, which we can do efficiently in rb_erase(). __rb_erase_color() then only needs to handle the no-childs case and can be modified accordingly. Signed-off-by: Michel Lespinasse Acked-by: Rik van Riel Cc: Peter Zijlstra Cc: Andrea Arcangeli Cc: David Woodhouse Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/rbtree.c | 105 +++++++++++++++++++++++++++++++++++------------------------ 1 file changed, 62 insertions(+), 43 deletions(-) (limited to 'lib') diff --git a/lib/rbtree.c b/lib/rbtree.c index bde1b5c5fb33..80b092538fa9 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -2,7 +2,8 @@ Red Black Trees (C) 1999 Andrea Arcangeli (C) 2002 David Woodhouse - + (C) 2012 Michel Lespinasse + This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or @@ -50,6 +51,11 @@ #define rb_is_red(r) (!rb_color(r)) #define rb_is_black(r) rb_color(r) +static inline void rb_set_black(struct rb_node *rb) +{ + rb->__rb_parent_color |= RB_BLACK; +} + static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p) { rb->__rb_parent_color = rb_color(rb) | (unsigned long)p; @@ -214,27 +220,18 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root) } EXPORT_SYMBOL(rb_insert_color); -static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, - struct rb_root *root) +static void __rb_erase_color(struct rb_node *parent, struct rb_root *root) { - struct rb_node *sibling, *tmp1, *tmp2; + struct rb_node *node = NULL, *sibling, *tmp1, *tmp2; while (true) { /* - * Loop invariant: all leaf paths going through node have a - * black node count that is 1 lower than other leaf paths. - * - * If node is red, we can flip it to black to adjust. - * If node is the root, all leaf paths go through it. - * Otherwise, we need to adjust the tree through color flips - * and tree rotations as per one of the 4 cases below. + * Loop invariants: + * - node is black (or NULL on first iteration) + * - node is not the root (parent is not NULL) + * - All leaf paths going through parent and node have a + * black node count that is 1 lower than other leaf paths. */ - if (node && rb_is_red(node)) { - rb_set_parent_color(node, parent, RB_BLACK); - break; - } else if (!parent) { - break; - } sibling = parent->rb_right; if (node != sibling) { /* node == parent->rb_left */ if (rb_is_red(sibling)) { @@ -268,17 +265,22 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, * / \ / \ * Sl Sr Sl Sr * - * This leaves us violating 5), so - * recurse at p. If p is red, the - * recursion will just flip it to black - * and exit. If coming from Case 1, - * p is known to be red. + * This leaves us violating 5) which + * can be fixed by flipping p to black + * if it was red, or by recursing at p. + * p is red when coming from Case 1. */ rb_set_parent_color(sibling, parent, RB_RED); - node = parent; - parent = rb_parent(node); - continue; + if (rb_is_red(parent)) + rb_set_black(parent); + else { + node = parent; + parent = rb_parent(node); + if (parent) + continue; + } + break; } /* * Case 3 - right rotate at sibling @@ -339,9 +341,15 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, /* Case 2 - sibling color flip */ rb_set_parent_color(sibling, parent, RB_RED); - node = parent; - parent = rb_parent(node); - continue; + if (rb_is_red(parent)) + rb_set_black(parent); + else { + node = parent; + parent = rb_parent(node); + if (parent) + continue; + } + break; } /* Case 3 - right rotate at sibling */ sibling->rb_right = tmp1 = tmp2->rb_left; @@ -369,23 +377,31 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, void rb_erase(struct rb_node *node, struct rb_root *root) { struct rb_node *child = node->rb_right, *tmp = node->rb_left; - struct rb_node *parent; - int color; + struct rb_node *parent, *rebalance; if (!tmp) { - case1: - /* Case 1: node to erase has no more than 1 child (easy!) */ + /* + * Case 1: node to erase has no more than 1 child (easy!) + * + * Note that if there is one child it must be red due to 5) + * and node must be black due to 4). We adjust colors locally + * so as to bypass __rb_erase_color() later on. + */ parent = rb_parent(node); - color = rb_color(node); - - if (child) - rb_set_parent(child, parent); __rb_change_child(node, child, parent, root); + if (child) { + rb_set_parent_color(child, parent, RB_BLACK); + rebalance = NULL; + } else { + rebalance = rb_is_black(node) ? parent : NULL; + } } else if (!child) { /* Still case 1, but this time the child is node->rb_left */ - child = tmp; - goto case1; + parent = rb_parent(node); + __rb_change_child(node, tmp, parent, root); + rb_set_parent_color(tmp, parent, RB_BLACK); + rebalance = NULL; } else { struct rb_node *old = node, *left; @@ -397,26 +413,29 @@ void rb_erase(struct rb_node *node, struct rb_root *root) child = node->rb_right; parent = rb_parent(node); - color = rb_color(node); if (parent == old) { parent = node; } else { - if (child) - rb_set_parent(child, parent); parent->rb_left = child; node->rb_right = old->rb_right; rb_set_parent(old->rb_right, node); } + if (child) { + rb_set_parent_color(child, parent, RB_BLACK); + rebalance = NULL; + } else { + rebalance = rb_is_black(node) ? parent : NULL; + } node->__rb_parent_color = old->__rb_parent_color; node->rb_left = old->rb_left; rb_set_parent(old->rb_left, node); } - if (color == RB_BLACK) - __rb_erase_color(child, parent, root); + if (rebalance) + __rb_erase_color(rebalance, root); } EXPORT_SYMBOL(rb_erase); -- cgit v1.2.1 From 4f035ad67f4633c233cb3642711d49b4efc9c82d Mon Sep 17 00:00:00 2001 From: Michel Lespinasse Date: Mon, 8 Oct 2012 16:31:13 -0700 Subject: rbtree: low level optimizations in rb_erase() Various minor optimizations in rb_erase(): - Avoid multiple loading of node->__rb_parent_color when computing parent and color information (possibly not in close sequence, as there might be further branches in the algorithm) - In the 1-child subcase of case 1, copy the __rb_parent_color field from the erased node to the child instead of recomputing it from the desired parent and color - When searching for the erased node's successor, differentiate between cases 2 and 3 based on whether any left links were followed. This avoids a condition later down. - In case 3, keep a pointer to the erased node's right child so we don't have to refetch it later to adjust its parent. - In the no-childs subcase of cases 2 and 3, place the rebalance assigment last so that the compiler can remove the following if(rebalance) test. Also, added some comments to illustrate cases 2 and 3. Signed-off-by: Michel Lespinasse Acked-by: Rik van Riel Cc: Peter Zijlstra Cc: Andrea Arcangeli Cc: David Woodhouse Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/rbtree.c | 98 +++++++++++++++++++++++++++++++++++++++--------------------- 1 file changed, 64 insertions(+), 34 deletions(-) (limited to 'lib') diff --git a/lib/rbtree.c b/lib/rbtree.c index 80b092538fa9..938061ecbe61 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -47,9 +47,14 @@ #define RB_RED 0 #define RB_BLACK 1 -#define rb_color(r) ((r)->__rb_parent_color & 1) -#define rb_is_red(r) (!rb_color(r)) -#define rb_is_black(r) rb_color(r) +#define __rb_parent(pc) ((struct rb_node *)(pc & ~3)) + +#define __rb_color(pc) ((pc) & 1) +#define __rb_is_black(pc) __rb_color(pc) +#define __rb_is_red(pc) (!__rb_color(pc)) +#define rb_color(rb) __rb_color((rb)->__rb_parent_color) +#define rb_is_red(rb) __rb_is_red((rb)->__rb_parent_color) +#define rb_is_black(rb) __rb_is_black((rb)->__rb_parent_color) static inline void rb_set_black(struct rb_node *rb) { @@ -378,6 +383,7 @@ void rb_erase(struct rb_node *node, struct rb_root *root) { struct rb_node *child = node->rb_right, *tmp = node->rb_left; struct rb_node *parent, *rebalance; + unsigned long pc; if (!tmp) { /* @@ -387,51 +393,75 @@ void rb_erase(struct rb_node *node, struct rb_root *root) * and node must be black due to 4). We adjust colors locally * so as to bypass __rb_erase_color() later on. */ - - parent = rb_parent(node); + pc = node->__rb_parent_color; + parent = __rb_parent(pc); __rb_change_child(node, child, parent, root); if (child) { - rb_set_parent_color(child, parent, RB_BLACK); + child->__rb_parent_color = pc; rebalance = NULL; - } else { - rebalance = rb_is_black(node) ? parent : NULL; - } + } else + rebalance = __rb_is_black(pc) ? parent : NULL; } else if (!child) { /* Still case 1, but this time the child is node->rb_left */ - parent = rb_parent(node); + tmp->__rb_parent_color = pc = node->__rb_parent_color; + parent = __rb_parent(pc); __rb_change_child(node, tmp, parent, root); - rb_set_parent_color(tmp, parent, RB_BLACK); rebalance = NULL; } else { - struct rb_node *old = node, *left; - - node = child; - while ((left = node->rb_left) != NULL) - node = left; - - __rb_change_child(old, node, rb_parent(old), root); - - child = node->rb_right; - parent = rb_parent(node); - - if (parent == old) { - parent = node; + struct rb_node *successor = child, *child2; + tmp = child->rb_left; + if (!tmp) { + /* + * Case 2: node's successor is its right child + * + * (n) (s) + * / \ / \ + * (x) (s) -> (x) (c) + * \ + * (c) + */ + parent = child; + child2 = child->rb_right; } else { - parent->rb_left = child; - - node->rb_right = old->rb_right; - rb_set_parent(old->rb_right, node); + /* + * Case 3: node's successor is leftmost under + * node's right child subtree + * + * (n) (s) + * / \ / \ + * (x) (y) -> (x) (y) + * / / + * (p) (p) + * / / + * (s) (c) + * \ + * (c) + */ + do { + parent = successor; + successor = tmp; + tmp = tmp->rb_left; + } while (tmp); + parent->rb_left = child2 = successor->rb_right; + successor->rb_right = child; + rb_set_parent(child, successor); } - if (child) { - rb_set_parent_color(child, parent, RB_BLACK); + successor->rb_left = tmp = node->rb_left; + rb_set_parent(tmp, successor); + + pc = node->__rb_parent_color; + tmp = __rb_parent(pc); + __rb_change_child(node, successor, tmp, root); + if (child2) { + successor->__rb_parent_color = pc; + rb_set_parent_color(child2, parent, RB_BLACK); rebalance = NULL; } else { - rebalance = rb_is_black(node) ? parent : NULL; + unsigned long pc2 = successor->__rb_parent_color; + successor->__rb_parent_color = pc; + rebalance = __rb_is_black(pc2) ? parent : NULL; } - node->__rb_parent_color = old->__rb_parent_color; - node->rb_left = old->rb_left; - rb_set_parent(old->rb_left, node); } if (rebalance) -- cgit v1.2.1 From dadf93534f125b9eda486b471446a8456a603d27 Mon Sep 17 00:00:00 2001 From: Michel Lespinasse Date: Mon, 8 Oct 2012 16:31:15 -0700 Subject: rbtree: augmented rbtree test Small test to measure the performance of augmented rbtrees. Signed-off-by: Michel Lespinasse Acked-by: Rik van Riel Cc: Peter Zijlstra Cc: Andrea Arcangeli Cc: David Woodhouse Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/rbtree_test.c | 103 ++++++++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 101 insertions(+), 2 deletions(-) (limited to 'lib') diff --git a/lib/rbtree_test.c b/lib/rbtree_test.c index fd09465d82ca..66e41d4bfc39 100644 --- a/lib/rbtree_test.c +++ b/lib/rbtree_test.c @@ -10,6 +10,10 @@ struct test_node { struct rb_node rb; u32 key; + + /* following fields used for testing augmented rbtree functionality */ + u32 val; + u32 augmented; }; static struct rb_root root = RB_ROOT; @@ -20,10 +24,11 @@ static struct rnd_state rnd; static void insert(struct test_node *node, struct rb_root *root) { struct rb_node **new = &root->rb_node, *parent = NULL; + u32 key = node->key; while (*new) { parent = *new; - if (node->key < rb_entry(parent, struct test_node, rb)->key) + if (key < rb_entry(parent, struct test_node, rb)->key) new = &parent->rb_left; else new = &parent->rb_right; @@ -38,11 +43,62 @@ static inline void erase(struct test_node *node, struct rb_root *root) rb_erase(&node->rb, root); } +static inline u32 augment_recompute(struct test_node *node) +{ + u32 max = node->val, child_augmented; + if (node->rb.rb_left) { + child_augmented = rb_entry(node->rb.rb_left, struct test_node, + rb)->augmented; + if (max < child_augmented) + max = child_augmented; + } + if (node->rb.rb_right) { + child_augmented = rb_entry(node->rb.rb_right, struct test_node, + rb)->augmented; + if (max < child_augmented) + max = child_augmented; + } + return max; +} + +static void augment_callback(struct rb_node *rb, void *unused) +{ + struct test_node *node = rb_entry(rb, struct test_node, rb); + node->augmented = augment_recompute(node); +} + +static void insert_augmented(struct test_node *node, struct rb_root *root) +{ + struct rb_node **new = &root->rb_node, *parent = NULL; + u32 key = node->key; + + while (*new) { + parent = *new; + if (key < rb_entry(parent, struct test_node, rb)->key) + new = &parent->rb_left; + else + new = &parent->rb_right; + } + + rb_link_node(&node->rb, parent, new); + rb_insert_color(&node->rb, root); + rb_augment_insert(&node->rb, augment_callback, NULL); +} + +static void erase_augmented(struct test_node *node, struct rb_root *root) +{ + struct rb_node *deepest = rb_augment_erase_begin(&node->rb); + rb_erase(&node->rb, root); + rb_augment_erase_end(deepest, augment_callback, NULL); +} + static void init(void) { int i; - for (i = 0; i < NODES; i++) + for (i = 0; i < NODES; i++) { nodes[i].key = prandom32(&rnd); + nodes[i].val = prandom32(&rnd); + } } static bool is_red(struct rb_node *rb) @@ -81,6 +137,17 @@ static void check(int nr_nodes) WARN_ON_ONCE(count != nr_nodes); } +static void check_augmented(int nr_nodes) +{ + struct rb_node *rb; + + check(nr_nodes); + for (rb = rb_first(&root); rb; rb = rb_next(rb)) { + struct test_node *node = rb_entry(rb, struct test_node, rb); + WARN_ON_ONCE(node->augmented != augment_recompute(node)); + } +} + static int rbtree_test_init(void) { int i, j; @@ -119,6 +186,38 @@ static int rbtree_test_init(void) check(0); } + printk(KERN_ALERT "augmented rbtree testing"); + + init(); + + time1 = get_cycles(); + + for (i = 0; i < PERF_LOOPS; i++) { + for (j = 0; j < NODES; j++) + insert_augmented(nodes + j, &root); + for (j = 0; j < NODES; j++) + erase_augmented(nodes + j, &root); + } + + time2 = get_cycles(); + time = time2 - time1; + + time = div_u64(time, PERF_LOOPS); + printk(" -> %llu cycles\n", (unsigned long long)time); + + for (i = 0; i < CHECK_LOOPS; i++) { + init(); + for (j = 0; j < NODES; j++) { + check_augmented(j); + insert_augmented(nodes + j, &root); + } + for (j = 0; j < NODES; j++) { + check_augmented(NODES - j); + erase_augmented(nodes + j, &root); + } + check_augmented(0); + } + return -EAGAIN; /* Fail will directly unload the module */ } -- cgit v1.2.1 From 14b94af0b251a2c80885b60538166fb7d04a642e Mon Sep 17 00:00:00 2001 From: Michel Lespinasse Date: Mon, 8 Oct 2012 16:31:17 -0700 Subject: rbtree: faster augmented rbtree manipulation Introduce new augmented rbtree APIs that allow minimal recalculation of augmented node information. A new callback is added to the rbtree insertion and erase rebalancing functions, to be called on each tree rotations. Such rotations preserve the subtree's root augmented value, but require recalculation of the one child that was previously located at the subtree root. In the insertion case, the handcoded search phase must be updated to maintain the augmented information on insertion, and then the rbtree coloring/rebalancing algorithms keep it up to date. In the erase case, things are more complicated since it is library code that manipulates the rbtree in order to remove internal nodes. This requires a couple additional callbacks to copy a subtree's augmented value when a new root is stitched in, and to recompute augmented values down the ancestry path when a node is removed from the tree. In order to preserve maximum speed for the non-augmented case, we provide two versions of each tree manipulation function. rb_insert_augmented() is the augmented equivalent of rb_insert_color(), and rb_erase_augmented() is the augmented equivalent of rb_erase(). Signed-off-by: Michel Lespinasse Acked-by: Rik van Riel Cc: Peter Zijlstra Cc: Andrea Arcangeli Cc: David Woodhouse Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/rbtree.c | 83 ++++++++++++++++++++++++++++++++++++++++++++++++++----- lib/rbtree_test.c | 58 ++++++++++++++++++++++++++++---------- 2 files changed, 120 insertions(+), 21 deletions(-) (limited to 'lib') diff --git a/lib/rbtree.c b/lib/rbtree.c index 938061ecbe61..a37ee7954b8f 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -105,7 +105,9 @@ __rb_rotate_set_parents(struct rb_node *old, struct rb_node *new, __rb_change_child(old, new, parent, root); } -void rb_insert_color(struct rb_node *node, struct rb_root *root) +static __always_inline void +__rb_insert(struct rb_node *node, struct rb_root *root, + void (*augment_rotate)(struct rb_node *old, struct rb_node *new)) { struct rb_node *parent = rb_red_parent(node), *gparent, *tmp; @@ -169,6 +171,7 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root) rb_set_parent_color(tmp, parent, RB_BLACK); rb_set_parent_color(parent, node, RB_RED); + augment_rotate(parent, node); parent = node; tmp = node->rb_right; } @@ -187,6 +190,7 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root) if (tmp) rb_set_parent_color(tmp, gparent, RB_BLACK); __rb_rotate_set_parents(gparent, parent, root, RB_RED); + augment_rotate(gparent, parent); break; } else { tmp = gparent->rb_left; @@ -209,6 +213,7 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root) rb_set_parent_color(tmp, parent, RB_BLACK); rb_set_parent_color(parent, node, RB_RED); + augment_rotate(parent, node); parent = node; tmp = node->rb_left; } @@ -219,13 +224,15 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root) if (tmp) rb_set_parent_color(tmp, gparent, RB_BLACK); __rb_rotate_set_parents(gparent, parent, root, RB_RED); + augment_rotate(gparent, parent); break; } } } -EXPORT_SYMBOL(rb_insert_color); -static void __rb_erase_color(struct rb_node *parent, struct rb_root *root) +static __always_inline void +__rb_erase_color(struct rb_node *parent, struct rb_root *root, + const struct rb_augment_callbacks *augment) { struct rb_node *node = NULL, *sibling, *tmp1, *tmp2; @@ -254,6 +261,7 @@ static void __rb_erase_color(struct rb_node *parent, struct rb_root *root) rb_set_parent_color(tmp1, parent, RB_BLACK); __rb_rotate_set_parents(parent, sibling, root, RB_RED); + augment->rotate(parent, sibling); sibling = tmp1; } tmp1 = sibling->rb_right; @@ -305,6 +313,7 @@ static void __rb_erase_color(struct rb_node *parent, struct rb_root *root) if (tmp1) rb_set_parent_color(tmp1, sibling, RB_BLACK); + augment->rotate(sibling, tmp2); tmp1 = sibling; sibling = tmp2; } @@ -327,6 +336,7 @@ static void __rb_erase_color(struct rb_node *parent, struct rb_root *root) rb_set_parent(tmp2, parent); __rb_rotate_set_parents(parent, sibling, root, RB_BLACK); + augment->rotate(parent, sibling); break; } else { sibling = parent->rb_left; @@ -337,6 +347,7 @@ static void __rb_erase_color(struct rb_node *parent, struct rb_root *root) rb_set_parent_color(tmp1, parent, RB_BLACK); __rb_rotate_set_parents(parent, sibling, root, RB_RED); + augment->rotate(parent, sibling); sibling = tmp1; } tmp1 = sibling->rb_left; @@ -363,6 +374,7 @@ static void __rb_erase_color(struct rb_node *parent, struct rb_root *root) if (tmp1) rb_set_parent_color(tmp1, sibling, RB_BLACK); + augment->rotate(sibling, tmp2); tmp1 = sibling; sibling = tmp2; } @@ -374,12 +386,15 @@ static void __rb_erase_color(struct rb_node *parent, struct rb_root *root) rb_set_parent(tmp2, parent); __rb_rotate_set_parents(parent, sibling, root, RB_BLACK); + augment->rotate(parent, sibling); break; } } } -void rb_erase(struct rb_node *node, struct rb_root *root) +static __always_inline void +__rb_erase(struct rb_node *node, struct rb_root *root, + const struct rb_augment_callbacks *augment) { struct rb_node *child = node->rb_right, *tmp = node->rb_left; struct rb_node *parent, *rebalance; @@ -401,12 +416,14 @@ void rb_erase(struct rb_node *node, struct rb_root *root) rebalance = NULL; } else rebalance = __rb_is_black(pc) ? parent : NULL; + tmp = parent; } else if (!child) { /* Still case 1, but this time the child is node->rb_left */ tmp->__rb_parent_color = pc = node->__rb_parent_color; parent = __rb_parent(pc); __rb_change_child(node, tmp, parent, root); rebalance = NULL; + tmp = parent; } else { struct rb_node *successor = child, *child2; tmp = child->rb_left; @@ -420,8 +437,9 @@ void rb_erase(struct rb_node *node, struct rb_root *root) * \ * (c) */ - parent = child; - child2 = child->rb_right; + parent = successor; + child2 = successor->rb_right; + augment->copy(node, successor); } else { /* * Case 3: node's successor is leftmost under @@ -445,6 +463,8 @@ void rb_erase(struct rb_node *node, struct rb_root *root) parent->rb_left = child2 = successor->rb_right; successor->rb_right = child; rb_set_parent(child, successor); + augment->copy(node, successor); + augment->propagate(parent, successor); } successor->rb_left = tmp = node->rb_left; @@ -462,13 +482,62 @@ void rb_erase(struct rb_node *node, struct rb_root *root) successor->__rb_parent_color = pc; rebalance = __rb_is_black(pc2) ? parent : NULL; } + tmp = successor; } + augment->propagate(tmp, NULL); if (rebalance) - __rb_erase_color(rebalance, root); + __rb_erase_color(rebalance, root, augment); +} + +/* + * Non-augmented rbtree manipulation functions. + * + * We use dummy augmented callbacks here, and have the compiler optimize them + * out of the rb_insert_color() and rb_erase() function definitions. + */ + +static inline void dummy_propagate(struct rb_node *node, struct rb_node *stop) {} +static inline void dummy_copy(struct rb_node *old, struct rb_node *new) {} +static inline void dummy_rotate(struct rb_node *old, struct rb_node *new) {} + +static const struct rb_augment_callbacks dummy_callbacks = { + dummy_propagate, dummy_copy, dummy_rotate +}; + +void rb_insert_color(struct rb_node *node, struct rb_root *root) +{ + __rb_insert(node, root, dummy_rotate); +} +EXPORT_SYMBOL(rb_insert_color); + +void rb_erase(struct rb_node *node, struct rb_root *root) +{ + __rb_erase(node, root, &dummy_callbacks); } EXPORT_SYMBOL(rb_erase); +/* + * Augmented rbtree manipulation functions. + * + * This instantiates the same __always_inline functions as in the non-augmented + * case, but this time with user-defined callbacks. + */ + +void __rb_insert_augmented(struct rb_node *node, struct rb_root *root, + void (*augment_rotate)(struct rb_node *old, struct rb_node *new)) +{ + __rb_insert(node, root, augment_rotate); +} +EXPORT_SYMBOL(__rb_insert_augmented); + +void rb_erase_augmented(struct rb_node *node, struct rb_root *root, + const struct rb_augment_callbacks *augment) +{ + __rb_erase(node, root, augment); +} +EXPORT_SYMBOL(rb_erase_augmented); + static void rb_augment_path(struct rb_node *node, rb_augment_f func, void *data) { struct rb_node *parent; diff --git a/lib/rbtree_test.c b/lib/rbtree_test.c index 66e41d4bfc39..e28345df09bf 100644 --- a/lib/rbtree_test.c +++ b/lib/rbtree_test.c @@ -61,35 +61,65 @@ static inline u32 augment_recompute(struct test_node *node) return max; } -static void augment_callback(struct rb_node *rb, void *unused) +static void augment_propagate(struct rb_node *rb, struct rb_node *stop) { - struct test_node *node = rb_entry(rb, struct test_node, rb); - node->augmented = augment_recompute(node); + while (rb != stop) { + struct test_node *node = rb_entry(rb, struct test_node, rb); + u32 augmented = augment_recompute(node); + if (node->augmented == augmented) + break; + node->augmented = augmented; + rb = rb_parent(&node->rb); + } +} + +static void augment_copy(struct rb_node *rb_old, struct rb_node *rb_new) +{ + struct test_node *old = rb_entry(rb_old, struct test_node, rb); + struct test_node *new = rb_entry(rb_new, struct test_node, rb); + new->augmented = old->augmented; } +static void augment_rotate(struct rb_node *rb_old, struct rb_node *rb_new) +{ + struct test_node *old = rb_entry(rb_old, struct test_node, rb); + struct test_node *new = rb_entry(rb_new, struct test_node, rb); + + /* Rotation doesn't change subtree's augmented value */ + new->augmented = old->augmented; + old->augmented = augment_recompute(old); +} + +static const struct rb_augment_callbacks augment_callbacks = { + augment_propagate, augment_copy, augment_rotate +}; + static void insert_augmented(struct test_node *node, struct rb_root *root) { - struct rb_node **new = &root->rb_node, *parent = NULL; + struct rb_node **new = &root->rb_node, *rb_parent = NULL; u32 key = node->key; + u32 val = node->val; + struct test_node *parent; while (*new) { - parent = *new; - if (key < rb_entry(parent, struct test_node, rb)->key) - new = &parent->rb_left; + rb_parent = *new; + parent = rb_entry(rb_parent, struct test_node, rb); + if (parent->augmented < val) + parent->augmented = val; + if (key < parent->key) + new = &parent->rb.rb_left; else - new = &parent->rb_right; + new = &parent->rb.rb_right; } - rb_link_node(&node->rb, parent, new); - rb_insert_color(&node->rb, root); - rb_augment_insert(&node->rb, augment_callback, NULL); + node->augmented = val; + rb_link_node(&node->rb, rb_parent, new); + rb_insert_augmented(&node->rb, root, &augment_callbacks); } static void erase_augmented(struct test_node *node, struct rb_root *root) { - struct rb_node *deepest = rb_augment_erase_begin(&node->rb); - rb_erase(&node->rb, root); - rb_augment_erase_end(deepest, augment_callback, NULL); + rb_erase_augmented(&node->rb, root, &augment_callbacks); } static void init(void) -- cgit v1.2.1 From 9d9e6f9703bbd642f3f2f807e6aaa642a4cbcec9 Mon Sep 17 00:00:00 2001 From: Michel Lespinasse Date: Mon, 8 Oct 2012 16:31:20 -0700 Subject: rbtree: remove prior augmented rbtree implementation convert arch/x86/mm/pat_rbtree.c to the proposed augmented rbtree api and remove the old augmented rbtree implementation. Signed-off-by: Michel Lespinasse Acked-by: Rik van Riel Cc: Peter Zijlstra Cc: Andrea Arcangeli Cc: David Woodhouse Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/rbtree.c | 71 ------------------------------------------------------------ 1 file changed, 71 deletions(-) (limited to 'lib') diff --git a/lib/rbtree.c b/lib/rbtree.c index a37ee7954b8f..c0088ca345f9 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -538,77 +538,6 @@ void rb_erase_augmented(struct rb_node *node, struct rb_root *root, } EXPORT_SYMBOL(rb_erase_augmented); -static void rb_augment_path(struct rb_node *node, rb_augment_f func, void *data) -{ - struct rb_node *parent; - -up: - func(node, data); - parent = rb_parent(node); - if (!parent) - return; - - if (node == parent->rb_left && parent->rb_right) - func(parent->rb_right, data); - else if (parent->rb_left) - func(parent->rb_left, data); - - node = parent; - goto up; -} - -/* - * after inserting @node into the tree, update the tree to account for - * both the new entry and any damage done by rebalance - */ -void rb_augment_insert(struct rb_node *node, rb_augment_f func, void *data) -{ - if (node->rb_left) - node = node->rb_left; - else if (node->rb_right) - node = node->rb_right; - - rb_augment_path(node, func, data); -} -EXPORT_SYMBOL(rb_augment_insert); - -/* - * before removing the node, find the deepest node on the rebalance path - * that will still be there after @node gets removed - */ -struct rb_node *rb_augment_erase_begin(struct rb_node *node) -{ - struct rb_node *deepest; - - if (!node->rb_right && !node->rb_left) - deepest = rb_parent(node); - else if (!node->rb_right) - deepest = node->rb_left; - else if (!node->rb_left) - deepest = node->rb_right; - else { - deepest = rb_next(node); - if (deepest->rb_right) - deepest = deepest->rb_right; - else if (rb_parent(deepest) != node) - deepest = rb_parent(deepest); - } - - return deepest; -} -EXPORT_SYMBOL(rb_augment_erase_begin); - -/* - * after removal, update the tree to account for the removed entry - * and any rebalance damage. - */ -void rb_augment_erase_end(struct rb_node *node, rb_augment_f func, void *data) -{ - if (node) - rb_augment_path(node, func, data); -} -EXPORT_SYMBOL(rb_augment_erase_end); - /* * This function returns the first node (in sort order) of the tree. */ -- cgit v1.2.1 From 3908836aa77e3621aaf2101f2920e01d7c8460d6 Mon Sep 17 00:00:00 2001 From: Michel Lespinasse Date: Mon, 8 Oct 2012 16:31:21 -0700 Subject: rbtree: add RB_DECLARE_CALLBACKS() macro As proposed by Peter Zijlstra, this makes it easier to define the augmented rbtree callbacks. Signed-off-by: Michel Lespinasse Cc: Rik van Riel Cc: Peter Zijlstra Cc: Andrea Arcangeli Cc: David Woodhouse Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/rbtree_test.c | 34 ++-------------------------------- 1 file changed, 2 insertions(+), 32 deletions(-) (limited to 'lib') diff --git a/lib/rbtree_test.c b/lib/rbtree_test.c index e28345df09bf..b20e99969b0f 100644 --- a/lib/rbtree_test.c +++ b/lib/rbtree_test.c @@ -61,38 +61,8 @@ static inline u32 augment_recompute(struct test_node *node) return max; } -static void augment_propagate(struct rb_node *rb, struct rb_node *stop) -{ - while (rb != stop) { - struct test_node *node = rb_entry(rb, struct test_node, rb); - u32 augmented = augment_recompute(node); - if (node->augmented == augmented) - break; - node->augmented = augmented; - rb = rb_parent(&node->rb); - } -} - -static void augment_copy(struct rb_node *rb_old, struct rb_node *rb_new) -{ - struct test_node *old = rb_entry(rb_old, struct test_node, rb); - struct test_node *new = rb_entry(rb_new, struct test_node, rb); - new->augmented = old->augmented; -} - -static void augment_rotate(struct rb_node *rb_old, struct rb_node *rb_new) -{ - struct test_node *old = rb_entry(rb_old, struct test_node, rb); - struct test_node *new = rb_entry(rb_new, struct test_node, rb); - - /* Rotation doesn't change subtree's augmented value */ - new->augmented = old->augmented; - old->augmented = augment_recompute(old); -} - -static const struct rb_augment_callbacks augment_callbacks = { - augment_propagate, augment_copy, augment_rotate -}; +RB_DECLARE_CALLBACKS(static, augment_callbacks, struct test_node, rb, + u32, augmented, augment_recompute) static void insert_augmented(struct test_node *node, struct rb_root *root) { -- cgit v1.2.1 From fff3fd8a1210a165252cd7cd01206da7a90d3a06 Mon Sep 17 00:00:00 2001 From: Michel Lespinasse Date: Mon, 8 Oct 2012 16:31:23 -0700 Subject: rbtree: add prio tree and interval tree tests Patch 1 implements support for interval trees, on top of the augmented rbtree API. It also adds synthetic tests to compare the performance of interval trees vs prio trees. Short answers is that interval trees are slightly faster (~25%) on insert/erase, and much faster (~2.4 - 3x) on search. It is debatable how realistic the synthetic test is, and I have not made such measurements yet, but my impression is that interval trees would still come out faster. Patch 2 uses a preprocessor template to make the interval tree generic, and uses it as a replacement for the vma prio_tree. Patch 3 takes the other prio_tree user, kmemleak, and converts it to use a basic rbtree. We don't actually need the augmented rbtree support here because the intervals are always non-overlapping. Patch 4 removes the now-unused prio tree library. Patch 5 proposes an additional optimization to rb_erase_augmented, now providing it as an inline function so that the augmented callbacks can be inlined in. This provides an additional 5-10% performance improvement for the interval tree insert/erase benchmark. There is a maintainance cost as it exposes augmented rbtree users to some of the rbtree library internals; however I think this cost shouldn't be too high as I expect the augmented rbtree will always have much less users than the base rbtree. I should probably add a quick summary of why I think it makes sense to replace prio trees with augmented rbtree based interval trees now. One of the drivers is that we need augmented rbtrees for Rik's vma gap finding code, and once you have them, it just makes sense to use them for interval trees as well, as this is the simpler and more well known algorithm. prio trees, in comparison, seem *too* clever: they impose an additional 'heap' constraint on the tree, which they use to guarantee a faster worst-case complexity of O(k+log N) for stabbing queries in a well-balanced prio tree, vs O(k*log N) for interval trees (where k=number of matches, N=number of intervals). Now this sounds great, but in practice prio trees don't realize this theorical benefit. First, the additional constraint makes them harder to update, so that the kernel implementation has to simplify things by balancing them like a radix tree, which is not always ideal. Second, the fact that there are both index and heap properties makes both tree manipulation and search more complex, which results in a higher multiplicative time constant. As it turns out, the simple interval tree algorithm ends up running faster than the more clever prio tree. This patch: Add two test modules: - prio_tree_test measures the performance of lib/prio_tree.c, both for insertion/removal and for stabbing searches - interval_tree_test measures the performance of a library of equivalent functionality, built using the augmented rbtree support. In order to support the second test module, lib/interval_tree.c is introduced. It is kept separate from the interval_tree_test main file for two reasons: first we don't want to provide an unfair advantage over prio_tree_test by having everything in a single compilation unit, and second there is the possibility that the interval tree functionality could get some non-test users in kernel over time. Signed-off-by: Michel Lespinasse Cc: Rik van Riel Cc: Hillf Danton Cc: Peter Zijlstra Cc: Catalin Marinas Cc: Andrea Arcangeli Cc: David Woodhouse Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/Kconfig.debug | 12 ++++ lib/Makefile | 4 ++ lib/interval_tree.c | 159 ++++++++++++++++++++++++++++++++++++++++++ lib/interval_tree_test_main.c | 105 ++++++++++++++++++++++++++++ lib/prio_tree.c | 4 ++ lib/prio_tree_test.c | 106 ++++++++++++++++++++++++++++ 6 files changed, 390 insertions(+) create mode 100644 lib/interval_tree.c create mode 100644 lib/interval_tree_test_main.c create mode 100644 lib/prio_tree_test.c (limited to 'lib') diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index a4e5d93b0f41..ee9f030b6951 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -1289,6 +1289,18 @@ config RBTREE_TEST A benchmark measuring the performance of the rbtree library. Also includes rbtree invariant checks. +config PRIO_TREE_TEST + tristate "Prio tree test" + depends on m && DEBUG_KERNEL + help + A benchmark measuring the performance of the prio tree library + +config INTERVAL_TREE_TEST + tristate "Interval tree test" + depends on m && DEBUG_KERNEL + help + A benchmark measuring the performance of the interval tree library + config PROVIDE_OHCI1394_DMA_INIT bool "Remote debugging over FireWire early on boot" depends on PCI && X86 diff --git a/lib/Makefile b/lib/Makefile index f49445d26b65..26f578bf616a 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -141,6 +141,10 @@ $(foreach file, $(libfdt_files), \ lib-$(CONFIG_LIBFDT) += $(libfdt_files) obj-$(CONFIG_RBTREE_TEST) += rbtree_test.o +obj-$(CONFIG_PRIO_TREE_TEST) += prio_tree_test.o +obj-$(CONFIG_INTERVAL_TREE_TEST) += interval_tree_test.o + +interval_tree_test-objs := interval_tree_test_main.o interval_tree.o hostprogs-y := gen_crc32table clean-files := crc32table.h diff --git a/lib/interval_tree.c b/lib/interval_tree.c new file mode 100644 index 000000000000..6fd540b1e499 --- /dev/null +++ b/lib/interval_tree.c @@ -0,0 +1,159 @@ +#include +#include + +/* Callbacks for augmented rbtree insert and remove */ + +static inline unsigned long +compute_subtree_last(struct interval_tree_node *node) +{ + unsigned long max = node->last, subtree_last; + if (node->rb.rb_left) { + subtree_last = rb_entry(node->rb.rb_left, + struct interval_tree_node, rb)->__subtree_last; + if (max < subtree_last) + max = subtree_last; + } + if (node->rb.rb_right) { + subtree_last = rb_entry(node->rb.rb_right, + struct interval_tree_node, rb)->__subtree_last; + if (max < subtree_last) + max = subtree_last; + } + return max; +} + +RB_DECLARE_CALLBACKS(static, augment_callbacks, struct interval_tree_node, rb, + unsigned long, __subtree_last, compute_subtree_last) + +/* Insert / remove interval nodes from the tree */ + +void interval_tree_insert(struct interval_tree_node *node, + struct rb_root *root) +{ + struct rb_node **link = &root->rb_node, *rb_parent = NULL; + unsigned long start = node->start, last = node->last; + struct interval_tree_node *parent; + + while (*link) { + rb_parent = *link; + parent = rb_entry(rb_parent, struct interval_tree_node, rb); + if (parent->__subtree_last < last) + parent->__subtree_last = last; + if (start < parent->start) + link = &parent->rb.rb_left; + else + link = &parent->rb.rb_right; + } + + node->__subtree_last = last; + rb_link_node(&node->rb, rb_parent, link); + rb_insert_augmented(&node->rb, root, &augment_callbacks); +} + +void interval_tree_remove(struct interval_tree_node *node, + struct rb_root *root) +{ + rb_erase_augmented(&node->rb, root, &augment_callbacks); +} + +/* + * Iterate over intervals intersecting [start;last] + * + * Note that a node's interval intersects [start;last] iff: + * Cond1: node->start <= last + * and + * Cond2: start <= node->last + */ + +static struct interval_tree_node * +subtree_search(struct interval_tree_node *node, + unsigned long start, unsigned long last) +{ + while (true) { + /* + * Loop invariant: start <= node->__subtree_last + * (Cond2 is satisfied by one of the subtree nodes) + */ + if (node->rb.rb_left) { + struct interval_tree_node *left = + rb_entry(node->rb.rb_left, + struct interval_tree_node, rb); + if (start <= left->__subtree_last) { + /* + * Some nodes in left subtree satisfy Cond2. + * Iterate to find the leftmost such node N. + * If it also satisfies Cond1, that's the match + * we are looking for. Otherwise, there is no + * matching interval as nodes to the right of N + * can't satisfy Cond1 either. + */ + node = left; + continue; + } + } + if (node->start <= last) { /* Cond1 */ + if (start <= node->last) /* Cond2 */ + return node; /* node is leftmost match */ + if (node->rb.rb_right) { + node = rb_entry(node->rb.rb_right, + struct interval_tree_node, rb); + if (start <= node->__subtree_last) + continue; + } + } + return NULL; /* No match */ + } +} + +struct interval_tree_node * +interval_tree_iter_first(struct rb_root *root, + unsigned long start, unsigned long last) +{ + struct interval_tree_node *node; + + if (!root->rb_node) + return NULL; + node = rb_entry(root->rb_node, struct interval_tree_node, rb); + if (node->__subtree_last < start) + return NULL; + return subtree_search(node, start, last); +} + +struct interval_tree_node * +interval_tree_iter_next(struct interval_tree_node *node, + unsigned long start, unsigned long last) +{ + struct rb_node *rb = node->rb.rb_right, *prev; + + while (true) { + /* + * Loop invariants: + * Cond1: node->start <= last + * rb == node->rb.rb_right + * + * First, search right subtree if suitable + */ + if (rb) { + struct interval_tree_node *right = + rb_entry(rb, struct interval_tree_node, rb); + if (start <= right->__subtree_last) + return subtree_search(right, start, last); + } + + /* Move up the tree until we come from a node's left child */ + do { + rb = rb_parent(&node->rb); + if (!rb) + return NULL; + prev = &node->rb; + node = rb_entry(rb, struct interval_tree_node, rb); + rb = node->rb.rb_right; + } while (prev == rb); + + /* Check if the node intersects [start;last] */ + if (last < node->start) /* !Cond1 */ + return NULL; + else if (start <= node->last) /* Cond2 */ + return node; + } +} diff --git a/lib/interval_tree_test_main.c b/lib/interval_tree_test_main.c new file mode 100644 index 000000000000..b25903987f7a --- /dev/null +++ b/lib/interval_tree_test_main.c @@ -0,0 +1,105 @@ +#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 = prandom32(&rnd), b = prandom32(&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] = prandom32(&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"); + + prandom32_seed(&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/prio_tree.c b/lib/prio_tree.c index 8d443af03b4c..4e0d2edff2b4 100644 --- a/lib/prio_tree.c +++ b/lib/prio_tree.c @@ -14,6 +14,7 @@ #include #include #include +#include /* * A clever mix of heap and radix trees forms a radix priority search tree (PST) @@ -241,6 +242,7 @@ struct prio_tree_node *prio_tree_insert(struct prio_tree_root *root, BUG(); return NULL; } +EXPORT_SYMBOL(prio_tree_insert); /* * Remove a prio_tree_node @node from a radix priority search tree @root. The @@ -290,6 +292,7 @@ void prio_tree_remove(struct prio_tree_root *root, struct prio_tree_node *node) while (cur != node) cur = prio_tree_replace(root, cur->parent, cur); } +EXPORT_SYMBOL(prio_tree_remove); static void iter_walk_down(struct prio_tree_iter *iter) { @@ -464,3 +467,4 @@ repeat: goto repeat; } +EXPORT_SYMBOL(prio_tree_next); diff --git a/lib/prio_tree_test.c b/lib/prio_tree_test.c new file mode 100644 index 000000000000..c26084ddc6a4 --- /dev/null +++ b/lib/prio_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 prio_tree_root root; +static struct prio_tree_node nodes[NODES]; +static u32 queries[SEARCHES]; + +static struct rnd_state rnd; + +static inline unsigned long +search(unsigned long query, struct prio_tree_root *root) +{ + struct prio_tree_iter iter; + unsigned long results = 0; + + prio_tree_iter_init(&iter, root, query, query); + while (prio_tree_next(&iter)) + results++; + return results; +} + +static void init(void) +{ + int i; + for (i = 0; i < NODES; i++) { + u32 a = prandom32(&rnd), b = prandom32(&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] = prandom32(&rnd); +} + +static int prio_tree_test_init(void) +{ + int i, j; + unsigned long results; + cycles_t time1, time2, time; + + printk(KERN_ALERT "prio tree insert/remove"); + + prandom32_seed(&rnd, 3141592653589793238ULL); + INIT_PRIO_TREE_ROOT(&root); + init(); + + time1 = get_cycles(); + + for (i = 0; i < PERF_LOOPS; i++) { + for (j = 0; j < NODES; j++) + prio_tree_insert(&root, nodes + j); + for (j = 0; j < NODES; j++) + prio_tree_remove(&root, nodes + j); + } + + time2 = get_cycles(); + time = time2 - time1; + + time = div_u64(time, PERF_LOOPS); + printk(" -> %llu cycles\n", (unsigned long long)time); + + printk(KERN_ALERT "prio tree search"); + + for (j = 0; j < NODES; j++) + prio_tree_insert(&root, nodes + j); + + 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 prio_tree_test_exit(void) +{ + printk(KERN_ALERT "test exit\n"); +} + +module_init(prio_tree_test_init) +module_exit(prio_tree_test_exit) + +MODULE_LICENSE("GPL"); +MODULE_AUTHOR("Michel Lespinasse"); +MODULE_DESCRIPTION("Prio Tree test"); -- cgit v1.2.1 From 6b2dbba8b6ac4df26f72eda1e5ea7bab9f950e08 Mon Sep 17 00:00:00 2001 From: Michel Lespinasse Date: Mon, 8 Oct 2012 16:31:25 -0700 Subject: mm: replace vma prio_tree with an interval tree Implement an interval tree as a replacement for the VMA prio_tree. The algorithms are similar to lib/interval_tree.c; however that code can't be directly reused as the interval endpoints are not explicitly stored in the VMA. So instead, the common algorithm is moved into a template and the details (node type, how to get interval endpoints from the node, etc) are filled in using the C preprocessor. Once the interval tree functions are available, using them as a replacement to the VMA prio tree is a relatively simple, mechanical job. Signed-off-by: Michel Lespinasse Cc: Rik van Riel Cc: Hillf Danton Cc: Peter Zijlstra Cc: Catalin Marinas Cc: Andrea Arcangeli Cc: David Woodhouse Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/interval_tree.c | 166 ++++------------------------------------------------ lib/prio_tree.c | 19 +----- 2 files changed, 12 insertions(+), 173 deletions(-) (limited to 'lib') diff --git a/lib/interval_tree.c b/lib/interval_tree.c index 6fd540b1e499..77a793e0644b 100644 --- a/lib/interval_tree.c +++ b/lib/interval_tree.c @@ -1,159 +1,13 @@ #include #include -/* Callbacks for augmented rbtree insert and remove */ - -static inline unsigned long -compute_subtree_last(struct interval_tree_node *node) -{ - unsigned long max = node->last, subtree_last; - if (node->rb.rb_left) { - subtree_last = rb_entry(node->rb.rb_left, - struct interval_tree_node, rb)->__subtree_last; - if (max < subtree_last) - max = subtree_last; - } - if (node->rb.rb_right) { - subtree_last = rb_entry(node->rb.rb_right, - struct interval_tree_node, rb)->__subtree_last; - if (max < subtree_last) - max = subtree_last; - } - return max; -} - -RB_DECLARE_CALLBACKS(static, augment_callbacks, struct interval_tree_node, rb, - unsigned long, __subtree_last, compute_subtree_last) - -/* Insert / remove interval nodes from the tree */ - -void interval_tree_insert(struct interval_tree_node *node, - struct rb_root *root) -{ - struct rb_node **link = &root->rb_node, *rb_parent = NULL; - unsigned long start = node->start, last = node->last; - struct interval_tree_node *parent; - - while (*link) { - rb_parent = *link; - parent = rb_entry(rb_parent, struct interval_tree_node, rb); - if (parent->__subtree_last < last) - parent->__subtree_last = last; - if (start < parent->start) - link = &parent->rb.rb_left; - else - link = &parent->rb.rb_right; - } - - node->__subtree_last = last; - rb_link_node(&node->rb, rb_parent, link); - rb_insert_augmented(&node->rb, root, &augment_callbacks); -} - -void interval_tree_remove(struct interval_tree_node *node, - struct rb_root *root) -{ - rb_erase_augmented(&node->rb, root, &augment_callbacks); -} - -/* - * Iterate over intervals intersecting [start;last] - * - * Note that a node's interval intersects [start;last] iff: - * Cond1: node->start <= last - * and - * Cond2: start <= node->last - */ - -static struct interval_tree_node * -subtree_search(struct interval_tree_node *node, - unsigned long start, unsigned long last) -{ - while (true) { - /* - * Loop invariant: start <= node->__subtree_last - * (Cond2 is satisfied by one of the subtree nodes) - */ - if (node->rb.rb_left) { - struct interval_tree_node *left = - rb_entry(node->rb.rb_left, - struct interval_tree_node, rb); - if (start <= left->__subtree_last) { - /* - * Some nodes in left subtree satisfy Cond2. - * Iterate to find the leftmost such node N. - * If it also satisfies Cond1, that's the match - * we are looking for. Otherwise, there is no - * matching interval as nodes to the right of N - * can't satisfy Cond1 either. - */ - node = left; - continue; - } - } - if (node->start <= last) { /* Cond1 */ - if (start <= node->last) /* Cond2 */ - return node; /* node is leftmost match */ - if (node->rb.rb_right) { - node = rb_entry(node->rb.rb_right, - struct interval_tree_node, rb); - if (start <= node->__subtree_last) - continue; - } - } - return NULL; /* No match */ - } -} - -struct interval_tree_node * -interval_tree_iter_first(struct rb_root *root, - unsigned long start, unsigned long last) -{ - struct interval_tree_node *node; - - if (!root->rb_node) - return NULL; - node = rb_entry(root->rb_node, struct interval_tree_node, rb); - if (node->__subtree_last < start) - return NULL; - return subtree_search(node, start, last); -} - -struct interval_tree_node * -interval_tree_iter_next(struct interval_tree_node *node, - unsigned long start, unsigned long last) -{ - struct rb_node *rb = node->rb.rb_right, *prev; - - while (true) { - /* - * Loop invariants: - * Cond1: node->start <= last - * rb == node->rb.rb_right - * - * First, search right subtree if suitable - */ - if (rb) { - struct interval_tree_node *right = - rb_entry(rb, struct interval_tree_node, rb); - if (start <= right->__subtree_last) - return subtree_search(right, start, last); - } - - /* Move up the tree until we come from a node's left child */ - do { - rb = rb_parent(&node->rb); - if (!rb) - return NULL; - prev = &node->rb; - node = rb_entry(rb, struct interval_tree_node, rb); - rb = node->rb.rb_right; - } while (prev == rb); - - /* Check if the node intersects [start;last] */ - if (last < node->start) /* !Cond1 */ - return NULL; - else if (start <= node->last) /* Cond2 */ - return node; - } -} +#define ITSTRUCT struct interval_tree_node +#define ITRB rb +#define ITTYPE unsigned long +#define ITSUBTREE __subtree_last +#define ITSTART(n) ((n)->start) +#define ITLAST(n) ((n)->last) +#define ITSTATIC +#define ITPREFIX interval_tree + +#include diff --git a/lib/prio_tree.c b/lib/prio_tree.c index 4e0d2edff2b4..bba37148c15e 100644 --- a/lib/prio_tree.c +++ b/lib/prio_tree.c @@ -44,27 +44,12 @@ * The following macros are used for implementing prio_tree for i_mmap */ -#define RADIX_INDEX(vma) ((vma)->vm_pgoff) -#define VMA_SIZE(vma) (((vma)->vm_end - (vma)->vm_start) >> PAGE_SHIFT) -/* avoid overflow */ -#define HEAP_INDEX(vma) ((vma)->vm_pgoff + (VMA_SIZE(vma) - 1)) - - static void get_index(const struct prio_tree_root *root, const struct prio_tree_node *node, unsigned long *radix, unsigned long *heap) { - if (root->raw) { - struct vm_area_struct *vma = prio_tree_entry( - node, struct vm_area_struct, shared.prio_tree_node); - - *radix = RADIX_INDEX(vma); - *heap = HEAP_INDEX(vma); - } - else { - *radix = node->start; - *heap = node->last; - } + *radix = node->start; + *heap = node->last; } static unsigned long index_bits_to_maxindex[BITS_PER_LONG]; -- cgit v1.2.1 From 147e615f83c2c36caf89e7a3bf78090ade6f266c Mon Sep 17 00:00:00 2001 From: Michel Lespinasse Date: Mon, 8 Oct 2012 16:31:30 -0700 Subject: prio_tree: remove After both prio_tree users have been converted to use red-black trees, there is no need to keep around the prio tree library anymore. Signed-off-by: Michel Lespinasse Cc: Rik van Riel Cc: Hillf Danton Cc: Peter Zijlstra Cc: Catalin Marinas Cc: Andrea Arcangeli Cc: David Woodhouse Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/Kconfig.debug | 6 - lib/Makefile | 3 +- lib/prio_tree.c | 455 --------------------------------------------------- lib/prio_tree_test.c | 106 ------------ 4 files changed, 1 insertion(+), 569 deletions(-) delete mode 100644 lib/prio_tree.c delete mode 100644 lib/prio_tree_test.c (limited to 'lib') diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index ee9f030b6951..a6e7e7741523 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -1289,12 +1289,6 @@ config RBTREE_TEST A benchmark measuring the performance of the rbtree library. Also includes rbtree invariant checks. -config PRIO_TREE_TEST - tristate "Prio tree test" - depends on m && DEBUG_KERNEL - help - A benchmark measuring the performance of the prio tree library - config INTERVAL_TREE_TEST tristate "Interval tree test" depends on m && DEBUG_KERNEL diff --git a/lib/Makefile b/lib/Makefile index 26f578bf616a..3128e357e286 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -9,7 +9,7 @@ endif lib-y := ctype.o string.o vsprintf.o cmdline.o \ rbtree.o radix-tree.o dump_stack.o timerqueue.o\ - idr.o int_sqrt.o extable.o prio_tree.o \ + idr.o int_sqrt.o extable.o \ sha1.o md5.o irq_regs.o reciprocal_div.o argv_split.o \ proportions.o flex_proportions.o prio_heap.o ratelimit.o show_mem.o \ is_single_threaded.o plist.o decompress.o @@ -141,7 +141,6 @@ $(foreach file, $(libfdt_files), \ lib-$(CONFIG_LIBFDT) += $(libfdt_files) obj-$(CONFIG_RBTREE_TEST) += rbtree_test.o -obj-$(CONFIG_PRIO_TREE_TEST) += prio_tree_test.o obj-$(CONFIG_INTERVAL_TREE_TEST) += interval_tree_test.o interval_tree_test-objs := interval_tree_test_main.o interval_tree.o diff --git a/lib/prio_tree.c b/lib/prio_tree.c deleted file mode 100644 index bba37148c15e..000000000000 --- a/lib/prio_tree.c +++ /dev/null @@ -1,455 +0,0 @@ -/* - * lib/prio_tree.c - priority search tree - * - * Copyright (C) 2004, Rajesh Venkatasubramanian - * - * This file is released under the GPL v2. - * - * Based on the radix priority search tree proposed by Edward M. McCreight - * SIAM Journal of Computing, vol. 14, no.2, pages 257-276, May 1985 - * - * 02Feb2004 Initial version - */ - -#include -#include -#include -#include - -/* - * A clever mix of heap and radix trees forms a radix priority search tree (PST) - * which is useful for storing intervals, e.g, we can consider a vma as a closed - * interval of file pages [offset_begin, offset_end], and store all vmas that - * map a file in a PST. Then, using the PST, we can answer a stabbing query, - * i.e., selecting a set of stored intervals (vmas) that overlap with (map) a - * given input interval X (a set of consecutive file pages), in "O(log n + m)" - * time where 'log n' is the height of the PST, and 'm' is the number of stored - * intervals (vmas) that overlap (map) with the input interval X (the set of - * consecutive file pages). - * - * In our implementation, we store closed intervals of the form [radix_index, - * heap_index]. We assume that always radix_index <= heap_index. McCreight's PST - * is designed for storing intervals with unique radix indices, i.e., each - * interval have different radix_index. However, this limitation can be easily - * overcome by using the size, i.e., heap_index - radix_index, as part of the - * index, so we index the tree using [(radix_index,size), heap_index]. - * - * When the above-mentioned indexing scheme is used, theoretically, in a 32 bit - * machine, the maximum height of a PST can be 64. We can use a balanced version - * of the priority search tree to optimize the tree height, but the balanced - * tree proposed by McCreight is too complex and memory-hungry for our purpose. - */ - -/* - * The following macros are used for implementing prio_tree for i_mmap - */ - -static void get_index(const struct prio_tree_root *root, - const struct prio_tree_node *node, - unsigned long *radix, unsigned long *heap) -{ - *radix = node->start; - *heap = node->last; -} - -static unsigned long index_bits_to_maxindex[BITS_PER_LONG]; - -void __init prio_tree_init(void) -{ - unsigned int i; - - for (i = 0; i < ARRAY_SIZE(index_bits_to_maxindex) - 1; i++) - index_bits_to_maxindex[i] = (1UL << (i + 1)) - 1; - index_bits_to_maxindex[ARRAY_SIZE(index_bits_to_maxindex) - 1] = ~0UL; -} - -/* - * Maximum heap_index that can be stored in a PST with index_bits bits - */ -static inline unsigned long prio_tree_maxindex(unsigned int bits) -{ - return index_bits_to_maxindex[bits - 1]; -} - -static void prio_set_parent(struct prio_tree_node *parent, - struct prio_tree_node *child, bool left) -{ - if (left) - parent->left = child; - else - parent->right = child; - - child->parent = parent; -} - -/* - * Extend a priority search tree so that it can store a node with heap_index - * max_heap_index. In the worst case, this algorithm takes O((log n)^2). - * However, this function is used rarely and the common case performance is - * not bad. - */ -static struct prio_tree_node *prio_tree_expand(struct prio_tree_root *root, - struct prio_tree_node *node, unsigned long max_heap_index) -{ - struct prio_tree_node *prev; - - if (max_heap_index > prio_tree_maxindex(root->index_bits)) - root->index_bits++; - - prev = node; - INIT_PRIO_TREE_NODE(node); - - while (max_heap_index > prio_tree_maxindex(root->index_bits)) { - struct prio_tree_node *tmp = root->prio_tree_node; - - root->index_bits++; - - if (prio_tree_empty(root)) - continue; - - prio_tree_remove(root, root->prio_tree_node); - INIT_PRIO_TREE_NODE(tmp); - - prio_set_parent(prev, tmp, true); - prev = tmp; - } - - if (!prio_tree_empty(root)) - prio_set_parent(prev, root->prio_tree_node, true); - - root->prio_tree_node = node; - return node; -} - -/* - * Replace a prio_tree_node with a new node and return the old node - */ -struct prio_tree_node *prio_tree_replace(struct prio_tree_root *root, - struct prio_tree_node *old, struct prio_tree_node *node) -{ - INIT_PRIO_TREE_NODE(node); - - if (prio_tree_root(old)) { - BUG_ON(root->prio_tree_node != old); - /* - * We can reduce root->index_bits here. However, it is complex - * and does not help much to improve performance (IMO). - */ - root->prio_tree_node = node; - } else - prio_set_parent(old->parent, node, old->parent->left == old); - - if (!prio_tree_left_empty(old)) - prio_set_parent(node, old->left, true); - - if (!prio_tree_right_empty(old)) - prio_set_parent(node, old->right, false); - - return old; -} - -/* - * Insert a prio_tree_node @node into a radix priority search tree @root. The - * algorithm typically takes O(log n) time where 'log n' is the number of bits - * required to represent the maximum heap_index. In the worst case, the algo - * can take O((log n)^2) - check prio_tree_expand. - * - * If a prior node with same radix_index and heap_index is already found in - * the tree, then returns the address of the prior node. Otherwise, inserts - * @node into the tree and returns @node. - */ -struct prio_tree_node *prio_tree_insert(struct prio_tree_root *root, - struct prio_tree_node *node) -{ - struct prio_tree_node *cur, *res = node; - unsigned long radix_index, heap_index; - unsigned long r_index, h_index, index, mask; - int size_flag = 0; - - get_index(root, node, &radix_index, &heap_index); - - if (prio_tree_empty(root) || - heap_index > prio_tree_maxindex(root->index_bits)) - return prio_tree_expand(root, node, heap_index); - - cur = root->prio_tree_node; - mask = 1UL << (root->index_bits - 1); - - while (mask) { - get_index(root, cur, &r_index, &h_index); - - if (r_index == radix_index && h_index == heap_index) - return cur; - - if (h_index < heap_index || - (h_index == heap_index && r_index > radix_index)) { - struct prio_tree_node *tmp = node; - node = prio_tree_replace(root, cur, node); - cur = tmp; - /* swap indices */ - index = r_index; - r_index = radix_index; - radix_index = index; - index = h_index; - h_index = heap_index; - heap_index = index; - } - - if (size_flag) - index = heap_index - radix_index; - else - index = radix_index; - - if (index & mask) { - if (prio_tree_right_empty(cur)) { - INIT_PRIO_TREE_NODE(node); - prio_set_parent(cur, node, false); - return res; - } else - cur = cur->right; - } else { - if (prio_tree_left_empty(cur)) { - INIT_PRIO_TREE_NODE(node); - prio_set_parent(cur, node, true); - return res; - } else - cur = cur->left; - } - - mask >>= 1; - - if (!mask) { - mask = 1UL << (BITS_PER_LONG - 1); - size_flag = 1; - } - } - /* Should not reach here */ - BUG(); - return NULL; -} -EXPORT_SYMBOL(prio_tree_insert); - -/* - * Remove a prio_tree_node @node from a radix priority search tree @root. The - * algorithm takes O(log n) time where 'log n' is the number of bits required - * to represent the maximum heap_index. - */ -void prio_tree_remove(struct prio_tree_root *root, struct prio_tree_node *node) -{ - struct prio_tree_node *cur; - unsigned long r_index, h_index_right, h_index_left; - - cur = node; - - while (!prio_tree_left_empty(cur) || !prio_tree_right_empty(cur)) { - if (!prio_tree_left_empty(cur)) - get_index(root, cur->left, &r_index, &h_index_left); - else { - cur = cur->right; - continue; - } - - if (!prio_tree_right_empty(cur)) - get_index(root, cur->right, &r_index, &h_index_right); - else { - cur = cur->left; - continue; - } - - /* both h_index_left and h_index_right cannot be 0 */ - if (h_index_left >= h_index_right) - cur = cur->left; - else - cur = cur->right; - } - - if (prio_tree_root(cur)) { - BUG_ON(root->prio_tree_node != cur); - __INIT_PRIO_TREE_ROOT(root, root->raw); - return; - } - - if (cur->parent->right == cur) - cur->parent->right = cur->parent; - else - cur->parent->left = cur->parent; - - while (cur != node) - cur = prio_tree_replace(root, cur->parent, cur); -} -EXPORT_SYMBOL(prio_tree_remove); - -static void iter_walk_down(struct prio_tree_iter *iter) -{ - iter->mask >>= 1; - if (iter->mask) { - if (iter->size_level) - iter->size_level++; - return; - } - - if (iter->size_level) { - BUG_ON(!prio_tree_left_empty(iter->cur)); - BUG_ON(!prio_tree_right_empty(iter->cur)); - iter->size_level++; - iter->mask = ULONG_MAX; - } else { - iter->size_level = 1; - iter->mask = 1UL << (BITS_PER_LONG - 1); - } -} - -static void iter_walk_up(struct prio_tree_iter *iter) -{ - if (iter->mask == ULONG_MAX) - iter->mask = 1UL; - else if (iter->size_level == 1) - iter->mask = 1UL; - else - iter->mask <<= 1; - if (iter->size_level) - iter->size_level--; - if (!iter->size_level && (iter->value & iter->mask)) - iter->value ^= iter->mask; -} - -/* - * Following functions help to enumerate all prio_tree_nodes in the tree that - * overlap with the input interval X [radix_index, heap_index]. The enumeration - * takes O(log n + m) time where 'log n' is the height of the tree (which is - * proportional to # of bits required to represent the maximum heap_index) and - * 'm' is the number of prio_tree_nodes that overlap the interval X. - */ - -static struct prio_tree_node *prio_tree_left(struct prio_tree_iter *iter, - unsigned long *r_index, unsigned long *h_index) -{ - if (prio_tree_left_empty(iter->cur)) - return NULL; - - get_index(iter->root, iter->cur->left, r_index, h_index); - - if (iter->r_index <= *h_index) { - iter->cur = iter->cur->left; - iter_walk_down(iter); - return iter->cur; - } - - return NULL; -} - -static struct prio_tree_node *prio_tree_right(struct prio_tree_iter *iter, - unsigned long *r_index, unsigned long *h_index) -{ - unsigned long value; - - if (prio_tree_right_empty(iter->cur)) - return NULL; - - if (iter->size_level) - value = iter->value; - else - value = iter->value | iter->mask; - - if (iter->h_index < value) - return NULL; - - get_index(iter->root, iter->cur->right, r_index, h_index); - - if (iter->r_index <= *h_index) { - iter->cur = iter->cur->right; - iter_walk_down(iter); - return iter->cur; - } - - return NULL; -} - -static struct prio_tree_node *prio_tree_parent(struct prio_tree_iter *iter) -{ - iter->cur = iter->cur->parent; - iter_walk_up(iter); - return iter->cur; -} - -static inline int overlap(struct prio_tree_iter *iter, - unsigned long r_index, unsigned long h_index) -{ - return iter->h_index >= r_index && iter->r_index <= h_index; -} - -/* - * prio_tree_first: - * - * Get the first prio_tree_node that overlaps with the interval [radix_index, - * heap_index]. Note that always radix_index <= heap_index. We do a pre-order - * traversal of the tree. - */ -static struct prio_tree_node *prio_tree_first(struct prio_tree_iter *iter) -{ - struct prio_tree_root *root; - unsigned long r_index, h_index; - - INIT_PRIO_TREE_ITER(iter); - - root = iter->root; - if (prio_tree_empty(root)) - return NULL; - - get_index(root, root->prio_tree_node, &r_index, &h_index); - - if (iter->r_index > h_index) - return NULL; - - iter->mask = 1UL << (root->index_bits - 1); - iter->cur = root->prio_tree_node; - - while (1) { - if (overlap(iter, r_index, h_index)) - return iter->cur; - - if (prio_tree_left(iter, &r_index, &h_index)) - continue; - - if (prio_tree_right(iter, &r_index, &h_index)) - continue; - - break; - } - return NULL; -} - -/* - * prio_tree_next: - * - * Get the next prio_tree_node that overlaps with the input interval in iter - */ -struct prio_tree_node *prio_tree_next(struct prio_tree_iter *iter) -{ - unsigned long r_index, h_index; - - if (iter->cur == NULL) - return prio_tree_first(iter); - -repeat: - while (prio_tree_left(iter, &r_index, &h_index)) - if (overlap(iter, r_index, h_index)) - return iter->cur; - - while (!prio_tree_right(iter, &r_index, &h_index)) { - while (!prio_tree_root(iter->cur) && - iter->cur->parent->right == iter->cur) - prio_tree_parent(iter); - - if (prio_tree_root(iter->cur)) - return NULL; - - prio_tree_parent(iter); - } - - if (overlap(iter, r_index, h_index)) - return iter->cur; - - goto repeat; -} -EXPORT_SYMBOL(prio_tree_next); diff --git a/lib/prio_tree_test.c b/lib/prio_tree_test.c deleted file mode 100644 index c26084ddc6a4..000000000000 --- a/lib/prio_tree_test.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 prio_tree_root root; -static struct prio_tree_node nodes[NODES]; -static u32 queries[SEARCHES]; - -static struct rnd_state rnd; - -static inline unsigned long -search(unsigned long query, struct prio_tree_root *root) -{ - struct prio_tree_iter iter; - unsigned long results = 0; - - prio_tree_iter_init(&iter, root, query, query); - while (prio_tree_next(&iter)) - results++; - return results; -} - -static void init(void) -{ - int i; - for (i = 0; i < NODES; i++) { - u32 a = prandom32(&rnd), b = prandom32(&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] = prandom32(&rnd); -} - -static int prio_tree_test_init(void) -{ - int i, j; - unsigned long results; - cycles_t time1, time2, time; - - printk(KERN_ALERT "prio tree insert/remove"); - - prandom32_seed(&rnd, 3141592653589793238ULL); - INIT_PRIO_TREE_ROOT(&root); - init(); - - time1 = get_cycles(); - - for (i = 0; i < PERF_LOOPS; i++) { - for (j = 0; j < NODES; j++) - prio_tree_insert(&root, nodes + j); - for (j = 0; j < NODES; j++) - prio_tree_remove(&root, nodes + j); - } - - time2 = get_cycles(); - time = time2 - time1; - - time = div_u64(time, PERF_LOOPS); - printk(" -> %llu cycles\n", (unsigned long long)time); - - printk(KERN_ALERT "prio tree search"); - - for (j = 0; j < NODES; j++) - prio_tree_insert(&root, nodes + j); - - 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 prio_tree_test_exit(void) -{ - printk(KERN_ALERT "test exit\n"); -} - -module_init(prio_tree_test_init) -module_exit(prio_tree_test_exit) - -MODULE_LICENSE("GPL"); -MODULE_AUTHOR("Michel Lespinasse"); -MODULE_DESCRIPTION("Prio Tree test"); -- cgit v1.2.1 From 9c079add0d0f45220f4bb37febf0621137ec2d38 Mon Sep 17 00:00:00 2001 From: Michel Lespinasse Date: Mon, 8 Oct 2012 16:31:33 -0700 Subject: rbtree: move augmented rbtree functionality to rbtree_augmented.h Provide rb_insert_augmented() and rb_erase_augmented() through a new rbtree_augmented.h include file. rb_erase_augmented() is defined there as an __always_inline function, in order to allow inlining of augmented rbtree callbacks into it. Since this generates a relatively large function, each augmented rbtree user should make sure to have a single call site. Signed-off-by: Michel Lespinasse Cc: Rik van Riel Cc: Hillf Danton Cc: Peter Zijlstra Cc: Catalin Marinas Cc: Andrea Arcangeli Cc: David Woodhouse Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/rbtree.c | 162 ++++-------------------------------------------------- lib/rbtree_test.c | 2 +- 2 files changed, 12 insertions(+), 152 deletions(-) (limited to 'lib') diff --git a/lib/rbtree.c b/lib/rbtree.c index c0088ca345f9..4f56a11d67fa 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -21,7 +21,7 @@ linux/lib/rbtree.c */ -#include +#include #include /* @@ -44,52 +44,16 @@ * parentheses and have some accompanying text comment. */ -#define RB_RED 0 -#define RB_BLACK 1 - -#define __rb_parent(pc) ((struct rb_node *)(pc & ~3)) - -#define __rb_color(pc) ((pc) & 1) -#define __rb_is_black(pc) __rb_color(pc) -#define __rb_is_red(pc) (!__rb_color(pc)) -#define rb_color(rb) __rb_color((rb)->__rb_parent_color) -#define rb_is_red(rb) __rb_is_red((rb)->__rb_parent_color) -#define rb_is_black(rb) __rb_is_black((rb)->__rb_parent_color) - static inline void rb_set_black(struct rb_node *rb) { rb->__rb_parent_color |= RB_BLACK; } -static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p) -{ - rb->__rb_parent_color = rb_color(rb) | (unsigned long)p; -} - -static inline void rb_set_parent_color(struct rb_node *rb, - struct rb_node *p, int color) -{ - rb->__rb_parent_color = (unsigned long)p | color; -} - static inline struct rb_node *rb_red_parent(struct rb_node *red) { return (struct rb_node *)red->__rb_parent_color; } -static inline void -__rb_change_child(struct rb_node *old, struct rb_node *new, - struct rb_node *parent, struct rb_root *root) -{ - if (parent) { - if (parent->rb_left == old) - parent->rb_left = new; - else - parent->rb_right = new; - } else - root->rb_node = new; -} - /* * Helper function for rotations: * - old's parent and color get assigned to new @@ -230,9 +194,9 @@ __rb_insert(struct rb_node *node, struct rb_root *root, } } -static __always_inline void +__always_inline void __rb_erase_color(struct rb_node *parent, struct rb_root *root, - const struct rb_augment_callbacks *augment) + void (*augment_rotate)(struct rb_node *old, struct rb_node *new)) { struct rb_node *node = NULL, *sibling, *tmp1, *tmp2; @@ -261,7 +225,7 @@ __rb_erase_color(struct rb_node *parent, struct rb_root *root, rb_set_parent_color(tmp1, parent, RB_BLACK); __rb_rotate_set_parents(parent, sibling, root, RB_RED); - augment->rotate(parent, sibling); + augment_rotate(parent, sibling); sibling = tmp1; } tmp1 = sibling->rb_right; @@ -313,7 +277,7 @@ __rb_erase_color(struct rb_node *parent, struct rb_root *root, if (tmp1) rb_set_parent_color(tmp1, sibling, RB_BLACK); - augment->rotate(sibling, tmp2); + augment_rotate(sibling, tmp2); tmp1 = sibling; sibling = tmp2; } @@ -336,7 +300,7 @@ __rb_erase_color(struct rb_node *parent, struct rb_root *root, rb_set_parent(tmp2, parent); __rb_rotate_set_parents(parent, sibling, root, RB_BLACK); - augment->rotate(parent, sibling); + augment_rotate(parent, sibling); break; } else { sibling = parent->rb_left; @@ -347,7 +311,7 @@ __rb_erase_color(struct rb_node *parent, struct rb_root *root, rb_set_parent_color(tmp1, parent, RB_BLACK); __rb_rotate_set_parents(parent, sibling, root, RB_RED); - augment->rotate(parent, sibling); + augment_rotate(parent, sibling); sibling = tmp1; } tmp1 = sibling->rb_left; @@ -374,7 +338,7 @@ __rb_erase_color(struct rb_node *parent, struct rb_root *root, if (tmp1) rb_set_parent_color(tmp1, sibling, RB_BLACK); - augment->rotate(sibling, tmp2); + augment_rotate(sibling, tmp2); tmp1 = sibling; sibling = tmp2; } @@ -386,109 +350,12 @@ __rb_erase_color(struct rb_node *parent, struct rb_root *root, rb_set_parent(tmp2, parent); __rb_rotate_set_parents(parent, sibling, root, RB_BLACK); - augment->rotate(parent, sibling); + augment_rotate(parent, sibling); break; } } } - -static __always_inline void -__rb_erase(struct rb_node *node, struct rb_root *root, - const struct rb_augment_callbacks *augment) -{ - struct rb_node *child = node->rb_right, *tmp = node->rb_left; - struct rb_node *parent, *rebalance; - unsigned long pc; - - if (!tmp) { - /* - * Case 1: node to erase has no more than 1 child (easy!) - * - * Note that if there is one child it must be red due to 5) - * and node must be black due to 4). We adjust colors locally - * so as to bypass __rb_erase_color() later on. - */ - pc = node->__rb_parent_color; - parent = __rb_parent(pc); - __rb_change_child(node, child, parent, root); - if (child) { - child->__rb_parent_color = pc; - rebalance = NULL; - } else - rebalance = __rb_is_black(pc) ? parent : NULL; - tmp = parent; - } else if (!child) { - /* Still case 1, but this time the child is node->rb_left */ - tmp->__rb_parent_color = pc = node->__rb_parent_color; - parent = __rb_parent(pc); - __rb_change_child(node, tmp, parent, root); - rebalance = NULL; - tmp = parent; - } else { - struct rb_node *successor = child, *child2; - tmp = child->rb_left; - if (!tmp) { - /* - * Case 2: node's successor is its right child - * - * (n) (s) - * / \ / \ - * (x) (s) -> (x) (c) - * \ - * (c) - */ - parent = successor; - child2 = successor->rb_right; - augment->copy(node, successor); - } else { - /* - * Case 3: node's successor is leftmost under - * node's right child subtree - * - * (n) (s) - * / \ / \ - * (x) (y) -> (x) (y) - * / / - * (p) (p) - * / / - * (s) (c) - * \ - * (c) - */ - do { - parent = successor; - successor = tmp; - tmp = tmp->rb_left; - } while (tmp); - parent->rb_left = child2 = successor->rb_right; - successor->rb_right = child; - rb_set_parent(child, successor); - augment->copy(node, successor); - augment->propagate(parent, successor); - } - - successor->rb_left = tmp = node->rb_left; - rb_set_parent(tmp, successor); - - pc = node->__rb_parent_color; - tmp = __rb_parent(pc); - __rb_change_child(node, successor, tmp, root); - if (child2) { - successor->__rb_parent_color = pc; - rb_set_parent_color(child2, parent, RB_BLACK); - rebalance = NULL; - } else { - unsigned long pc2 = successor->__rb_parent_color; - successor->__rb_parent_color = pc; - rebalance = __rb_is_black(pc2) ? parent : NULL; - } - tmp = successor; - } - - augment->propagate(tmp, NULL); - if (rebalance) - __rb_erase_color(rebalance, root, augment); -} +EXPORT_SYMBOL(__rb_erase_color); /* * Non-augmented rbtree manipulation functions. @@ -513,7 +380,7 @@ EXPORT_SYMBOL(rb_insert_color); void rb_erase(struct rb_node *node, struct rb_root *root) { - __rb_erase(node, root, &dummy_callbacks); + rb_erase_augmented(node, root, &dummy_callbacks); } EXPORT_SYMBOL(rb_erase); @@ -531,13 +398,6 @@ void __rb_insert_augmented(struct rb_node *node, struct rb_root *root, } EXPORT_SYMBOL(__rb_insert_augmented); -void rb_erase_augmented(struct rb_node *node, struct rb_root *root, - const struct rb_augment_callbacks *augment) -{ - __rb_erase(node, root, augment); -} -EXPORT_SYMBOL(rb_erase_augmented); - /* * This function returns the first node (in sort order) of the tree. */ diff --git a/lib/rbtree_test.c b/lib/rbtree_test.c index b20e99969b0f..268b23951fec 100644 --- a/lib/rbtree_test.c +++ b/lib/rbtree_test.c @@ -1,5 +1,5 @@ #include -#include +#include #include #include -- cgit v1.2.1 From 9826a516ff77c5820e591211e4f3e58ff36f46be Mon Sep 17 00:00:00 2001 From: Michel Lespinasse Date: Mon, 8 Oct 2012 16:31:35 -0700 Subject: mm: interval tree updates Update the generic interval tree code that was introduced in "mm: replace vma prio_tree with an interval tree". Changes: - fixed 'endpoing' typo noticed by Andrew Morton - replaced include/linux/interval_tree_tmpl.h, which was used as a template (including it automatically defined the interval tree functions) with include/linux/interval_tree_generic.h, which only defines a preprocessor macro INTERVAL_TREE_DEFINE(), which itself defines the interval tree functions when invoked. Now that is a very long macro which is unfortunate, but it does make the usage sites (lib/interval_tree.c and mm/interval_tree.c) a bit nicer than previously. - make use of RB_DECLARE_CALLBACKS() in the INTERVAL_TREE_DEFINE() macro, instead of duplicating that code in the interval tree template. - replaced vma_interval_tree_add(), which was actually handling the nonlinear and interval tree cases, with vma_interval_tree_insert_after() which handles only the interval tree case and has an API that is more consistent with the other interval tree handling functions. The nonlinear case is now handled explicitly in kernel/fork.c dup_mmap(). Signed-off-by: Michel Lespinasse Cc: Andrea Arcangeli Cc: Rik van Riel Cc: Peter Zijlstra Cc: Daniel Santos Cc: Hugh Dickins Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/interval_tree.c | 15 ++++++--------- 1 file changed, 6 insertions(+), 9 deletions(-) (limited to 'lib') diff --git a/lib/interval_tree.c b/lib/interval_tree.c index 77a793e0644b..e6eb406f2d65 100644 --- a/lib/interval_tree.c +++ b/lib/interval_tree.c @@ -1,13 +1,10 @@ #include #include +#include -#define ITSTRUCT struct interval_tree_node -#define ITRB rb -#define ITTYPE unsigned long -#define ITSUBTREE __subtree_last -#define ITSTART(n) ((n)->start) -#define ITLAST(n) ((n)->last) -#define ITSTATIC -#define ITPREFIX interval_tree +#define START(node) ((node)->start) +#define LAST(node) ((node)->last) -#include +INTERVAL_TREE_DEFINE(struct interval_tree_node, rb, + unsigned long, __subtree_last, + START, LAST,, interval_tree) -- cgit v1.2.1 From ed8ea8150182f8d715fceb3b175ef0a9ebacd872 Mon Sep 17 00:00:00 2001 From: Michel Lespinasse Date: Mon, 8 Oct 2012 16:31:45 -0700 Subject: mm: add CONFIG_DEBUG_VM_RB build option Add a CONFIG_DEBUG_VM_RB build option for the previously existing DEBUG_MM_RB code. Now that Andi Kleen modified it to avoid using recursive algorithms, we can expose it a bit more. Also extend this code to validate_mm() after stack expansion, and to check that the vma's start and last pgoffs have not changed since the nodes were inserted on the anon vma interval tree (as it is important that the nodes be reindexed after each such update). Signed-off-by: Michel Lespinasse Cc: Andrea Arcangeli Cc: Rik van Riel Cc: Peter Zijlstra Cc: Daniel Santos Cc: Hugh Dickins Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/Kconfig.debug | 9 +++++++++ 1 file changed, 9 insertions(+) (limited to 'lib') diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index a6e7e7741523..28e9d6c98941 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -798,6 +798,15 @@ config DEBUG_VM If unsure, say N. +config DEBUG_VM_RB + bool "Debug VM red-black trees" + depends on DEBUG_VM + help + Enable this to turn on more extended checks in the virtual-memory + system that may impact performance. + + If unsure, say N. + config DEBUG_VIRTUAL bool "Debug VM translations" depends on DEBUG_KERNEL && X86 -- cgit v1.2.1