diff options
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/Kconfig.debug | 38 | ||||
| -rw-r--r-- | lib/Makefile | 7 | ||||
| -rw-r--r-- | lib/interval_tree.c | 10 | ||||
| -rw-r--r-- | lib/interval_tree_test_main.c | 105 | ||||
| -rw-r--r-- | lib/prio_tree.c | 466 | ||||
| -rw-r--r-- | lib/rbtree.c | 656 | ||||
| -rw-r--r-- | lib/rbtree_test.c | 234 |
7 files changed, 735 insertions, 781 deletions
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index 7fba3a98967f..28e9d6c98941 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 @@ -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 @@ -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 @@ -1282,6 +1291,19 @@ 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 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 42d283edc4d3..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 @@ -140,6 +140,11 @@ $(foreach file, $(libfdt_files), \ $(eval CFLAGS_$(file) = -I$(src)/../scripts/dtc/libfdt)) lib-$(CONFIG_LIBFDT) += $(libfdt_files) +obj-$(CONFIG_RBTREE_TEST) += rbtree_test.o +obj-$(CONFIG_INTERVAL_TREE_TEST) += interval_tree_test.o + +interval_tree_test-objs := interval_tree_test_main.o interval_tree.o + 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..e6eb406f2d65 --- /dev/null +++ b/lib/interval_tree.c @@ -0,0 +1,10 @@ +#include <linux/init.h> +#include <linux/interval_tree.h> +#include <linux/interval_tree_generic.h> + +#define START(node) ((node)->start) +#define LAST(node) ((node)->last) + +INTERVAL_TREE_DEFINE(struct interval_tree_node, rb, + unsigned long, __subtree_last, + START, LAST,, interval_tree) 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 <linux/module.h> +#include <linux/interval_tree.h> +#include <linux/random.h> +#include <asm/timex.h> + +#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 deleted file mode 100644 index 8d443af03b4c..000000000000 --- a/lib/prio_tree.c +++ /dev/null @@ -1,466 +0,0 @@ -/* - * lib/prio_tree.c - priority search tree - * - * Copyright (C) 2004, Rajesh Venkatasubramanian <vrajesh@umich.edu> - * - * 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 <linux/init.h> -#include <linux/mm.h> -#include <linux/prio_tree.h> - -/* - * 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 - */ - -#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; - } -} - -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; -} - -/* - * 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); -} - -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; -} diff --git a/lib/rbtree.c b/lib/rbtree.c index d4175565dc2c..4f56a11d67fa 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -2,7 +2,8 @@ Red Black Trees (C) 1999 Andrea Arcangeli <andrea@suse.de> (C) 2002 David Woodhouse <dwmw2@infradead.org> - + (C) 2012 Michel Lespinasse <walken@google.com> + 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 @@ -20,339 +21,382 @@ linux/lib/rbtree.c */ -#include <linux/rbtree.h> +#include <linux/rbtree_augmented.h> #include <linux/export.h> -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); +/* + * 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. Unknown color nodes shall be drawn as red within + * parentheses and have some accompanying text comment. + */ - 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 inline void rb_set_black(struct rb_node *rb) +{ + rb->__rb_parent_color |= RB_BLACK; } -static void __rb_rotate_right(struct rb_node *node, struct rb_root *root) +static inline struct rb_node *rb_red_parent(struct rb_node *red) { - 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); + return (struct rb_node *)red->__rb_parent_color; +} - 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 + * - 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); + __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, *gparent; - - while ((parent = rb_parent(node)) && rb_is_red(parent)) - { - 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; - } + struct rb_node *parent = rb_red_parent(node), *gparent, *tmp; + + 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. + */ + if (!parent) { + rb_set_parent_color(node, NULL, RB_BLACK); + break; + } else if (rb_is_black(parent)) + break; + + gparent = rb_red_parent(parent); + + tmp = gparent->rb_right; + if (parent != tmp) { /* parent == gparent->rb_left */ + 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) - { - register struct rb_node *tmp; - __rb_rotate_left(parent, root); - tmp = parent; + tmp = parent->rb_right; + if (node == tmp) { + /* + * 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); + augment_rotate(parent, node); parent = node; - node = tmp; + tmp = node->rb_right; } - 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); + augment_rotate(gparent, parent); + 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) - { - register struct rb_node *tmp; - __rb_rotate_right(parent, root); - tmp = parent; + tmp = parent->rb_left; + if (node == tmp) { + /* 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); + augment_rotate(parent, node); parent = node; - node = tmp; + tmp = node->rb_left; } - 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); + augment_rotate(gparent, parent); + break; } } - - rb_set_black(root->rb_node); } -EXPORT_SYMBOL(rb_insert_color); -static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, - struct rb_root *root) +__always_inline void +__rb_erase_color(struct rb_node *parent, struct rb_root *root, + void (*augment_rotate)(struct rb_node *old, struct rb_node *new)) { - struct rb_node *other; - - while ((!node || rb_is_black(node)) && node != root->rb_node) - { - 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; + struct rb_node *node = NULL, *sibling, *tmp1, *tmp2; + + while (true) { + /* + * 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. + */ + sibling = parent->rb_right; + if (node != sibling) { /* node == parent->rb_left */ + 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); + augment_rotate(parent, sibling); + sibling = tmp1; } - 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); - rb_set_red(other); - __rb_rotate_right(other, root); - other = parent->rb_right; + 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) 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); + if (rb_is_red(parent)) + rb_set_black(parent); + else { + node = parent; + parent = rb_parent(node); + if (parent) + continue; + } + break; } - rb_set_color(other, rb_color(parent)); - rb_set_black(parent); - rb_set_black(other->rb_right); - __rb_rotate_left(parent, root); - node = root->rb_node; - 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; + /* + * 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); + augment_rotate(sibling, tmp2); + tmp1 = sibling; + sibling = tmp2; } - 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); + /* + * 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); + augment_rotate(parent, sibling); + break; + } else { + 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); + augment_rotate(parent, sibling); + sibling = tmp1; } - else - { - if (!other->rb_left || rb_is_black(other->rb_left)) - { - rb_set_black(other->rb_right); - rb_set_red(other); - __rb_rotate_left(other, root); - other = parent->rb_left; + 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); + if (rb_is_red(parent)) + rb_set_black(parent); + else { + node = parent; + parent = rb_parent(node); + if (parent) + continue; + } + break; } - rb_set_color(other, rb_color(parent)); - rb_set_black(parent); - rb_set_black(other->rb_left); - __rb_rotate_right(parent, root); - node = root->rb_node; - break; + /* 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); + augment_rotate(sibling, tmp2); + tmp1 = sibling; + sibling = tmp2; } + /* 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); + augment_rotate(parent, sibling); + break; } } - if (node) - rb_set_black(node); } +EXPORT_SYMBOL(__rb_erase_color); -void rb_erase(struct rb_node *node, struct rb_root *root) -{ - struct rb_node *child, *parent; - int color; - - if (!node->rb_left) - child = node->rb_right; - else if (!node->rb_right) - child = node->rb_left; - else - { - struct rb_node *old = node, *left; - - node = node->rb_right; - 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; - - 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); - } - - node->rb_parent_color = old->rb_parent_color; - node->rb_left = old->rb_left; - rb_set_parent(old->rb_left, node); +/* + * 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. + */ - goto color; - } +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) {} - parent = rb_parent(node); - color = rb_color(node); - - 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; +static const struct rb_augment_callbacks dummy_callbacks = { + dummy_propagate, dummy_copy, dummy_rotate +}; - color: - if (color == RB_BLACK) - __rb_erase_color(child, parent, root); -} -EXPORT_SYMBOL(rb_erase); - -static void rb_augment_path(struct rb_node *node, rb_augment_f func, void *data) +void rb_insert_color(struct rb_node *node, struct rb_root *root) { - 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; + __rb_insert(node, root, dummy_rotate); } +EXPORT_SYMBOL(rb_insert_color); -/* - * 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) +void rb_erase(struct rb_node *node, struct rb_root *root) { - if (node->rb_left) - node = node->rb_left; - else if (node->rb_right) - node = node->rb_right; - - rb_augment_path(node, func, data); + rb_erase_augmented(node, root, &dummy_callbacks); } -EXPORT_SYMBOL(rb_augment_insert); +EXPORT_SYMBOL(rb_erase); /* - * before removing the node, find the deepest node on the rebalance path - * that will still be there after @node gets removed + * Augmented rbtree manipulation functions. + * + * This instantiates the same __always_inline functions as in the non-augmented + * case, but this time with user-defined callbacks. */ -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) +void __rb_insert_augmented(struct rb_node *node, struct rb_root *root, + void (*augment_rotate)(struct rb_node *old, struct rb_node *new)) { - if (node) - rb_augment_path(node, func, data); + __rb_insert(node, root, augment_rotate); } -EXPORT_SYMBOL(rb_augment_erase_end); +EXPORT_SYMBOL(__rb_insert_augmented); /* * This function returns the first node (in sort order) of the tree. @@ -387,11 +431,13 @@ 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 - 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) @@ -399,12 +445,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; @@ -416,11 +463,13 @@ 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 - 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) @@ -428,8 +477,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; @@ -443,14 +494,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) diff --git a/lib/rbtree_test.c b/lib/rbtree_test.c new file mode 100644 index 000000000000..268b23951fec --- /dev/null +++ b/lib/rbtree_test.c @@ -0,0 +1,234 @@ +#include <linux/module.h> +#include <linux/rbtree_augmented.h> +#include <linux/random.h> +#include <asm/timex.h> + +#define NODES 100 +#define PERF_LOOPS 100000 +#define CHECK_LOOPS 100 + +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; +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; + 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); +} + +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; +} + +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) +{ + struct rb_node **new = &root->rb_node, *rb_parent = NULL; + u32 key = node->key; + u32 val = node->val; + struct test_node *parent; + + while (*new) { + 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.rb_right; + } + + 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) +{ + rb_erase_augmented(&node->rb, root, &augment_callbacks); +} + +static void init(void) +{ + int 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) +{ + 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 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; + cycles_t time1, time2, time; + + printk(KERN_ALERT "rbtree testing"); + + prandom32_seed(&rnd, 3141592653589793238ULL); + 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); + } + + 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 */ +} + +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"); |