diff options
author | Michel Lespinasse <walken@google.com> | 2012-10-08 19:30:39 -0400 |
---|---|---|
committer | Linus Torvalds <torvalds@linux-foundation.org> | 2012-10-09 03:22:33 -0400 |
commit | 910a742d4ba863848c7283d69c21bfa779d3b9a8 (patch) | |
tree | 324d473754194d806fdd254f5a4e58dfc8b4a221 /lib | |
parent | bf7ad8eeab995710c766df49c9c69a8592ca0216 (diff) |
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 <walken@google.com>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Acked-by: David Woodhouse <David.Woodhouse@intel.com>
Cc: Rik van Riel <riel@redhat.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Daniel Santos <daniel.santos@pobox.com>
Cc: Jens Axboe <axboe@kernel.dk>
Cc: "Eric W. Biederman" <ebiederm@xmission.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Diffstat (limited to 'lib')
-rw-r--r-- | lib/Kconfig.debug | 7 | ||||
-rw-r--r-- | lib/Makefile | 2 | ||||
-rw-r--r-- | lib/rbtree_test.c | 135 |
3 files changed, 144 insertions, 0 deletions
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 | |||
1282 | source mm/Kconfig.debug | 1282 | source mm/Kconfig.debug |
1283 | source kernel/trace/Kconfig | 1283 | source kernel/trace/Kconfig |
1284 | 1284 | ||
1285 | config RBTREE_TEST | ||
1286 | tristate "Red-Black tree test" | ||
1287 | depends on m && DEBUG_KERNEL | ||
1288 | help | ||
1289 | A benchmark measuring the performance of the rbtree library. | ||
1290 | Also includes rbtree invariant checks. | ||
1291 | |||
1285 | config PROVIDE_OHCI1394_DMA_INIT | 1292 | config PROVIDE_OHCI1394_DMA_INIT |
1286 | bool "Remote debugging over FireWire early on boot" | 1293 | bool "Remote debugging over FireWire early on boot" |
1287 | depends on PCI && X86 | 1294 | 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), \ | |||
140 | $(eval CFLAGS_$(file) = -I$(src)/../scripts/dtc/libfdt)) | 140 | $(eval CFLAGS_$(file) = -I$(src)/../scripts/dtc/libfdt)) |
141 | lib-$(CONFIG_LIBFDT) += $(libfdt_files) | 141 | lib-$(CONFIG_LIBFDT) += $(libfdt_files) |
142 | 142 | ||
143 | obj-$(CONFIG_RBTREE_TEST) += rbtree_test.o | ||
144 | |||
143 | hostprogs-y := gen_crc32table | 145 | hostprogs-y := gen_crc32table |
144 | clean-files := crc32table.h | 146 | clean-files := crc32table.h |
145 | 147 | ||
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 @@ | |||
1 | #include <linux/module.h> | ||
2 | #include <linux/rbtree.h> | ||
3 | #include <linux/random.h> | ||
4 | #include <asm/timex.h> | ||
5 | |||
6 | #define NODES 100 | ||
7 | #define PERF_LOOPS 100000 | ||
8 | #define CHECK_LOOPS 100 | ||
9 | |||
10 | struct test_node { | ||
11 | struct rb_node rb; | ||
12 | u32 key; | ||
13 | }; | ||
14 | |||
15 | static struct rb_root root = RB_ROOT; | ||
16 | static struct test_node nodes[NODES]; | ||
17 | |||
18 | static struct rnd_state rnd; | ||
19 | |||
20 | static void insert(struct test_node *node, struct rb_root *root) | ||
21 | { | ||
22 | struct rb_node **new = &root->rb_node, *parent = NULL; | ||
23 | |||
24 | while (*new) { | ||
25 | parent = *new; | ||
26 | if (node->key < rb_entry(parent, struct test_node, rb)->key) | ||
27 | new = &parent->rb_left; | ||
28 | else | ||
29 | new = &parent->rb_right; | ||
30 | } | ||
31 | |||
32 | rb_link_node(&node->rb, parent, new); | ||
33 | rb_insert_color(&node->rb, root); | ||
34 | } | ||
35 | |||
36 | static inline void erase(struct test_node *node, struct rb_root *root) | ||
37 | { | ||
38 | rb_erase(&node->rb, root); | ||
39 | } | ||
40 | |||
41 | static void init(void) | ||
42 | { | ||
43 | int i; | ||
44 | for (i = 0; i < NODES; i++) | ||
45 | nodes[i].key = prandom32(&rnd); | ||
46 | } | ||
47 | |||
48 | static bool is_red(struct rb_node *rb) | ||
49 | { | ||
50 | return !(rb->__rb_parent_color & 1); | ||
51 | } | ||
52 | |||
53 | static int black_path_count(struct rb_node *rb) | ||
54 | { | ||
55 | int count; | ||
56 | for (count = 0; rb; rb = rb_parent(rb)) | ||
57 | count += !is_red(rb); | ||
58 | return count; | ||
59 | } | ||
60 | |||
61 | static void check(int nr_nodes) | ||
62 | { | ||
63 | struct rb_node *rb; | ||
64 | int count = 0; | ||
65 | int blacks; | ||
66 | u32 prev_key = 0; | ||
67 | |||
68 | for (rb = rb_first(&root); rb; rb = rb_next(rb)) { | ||
69 | struct test_node *node = rb_entry(rb, struct test_node, rb); | ||
70 | WARN_ON_ONCE(node->key < prev_key); | ||
71 | WARN_ON_ONCE(is_red(rb) && | ||
72 | (!rb_parent(rb) || is_red(rb_parent(rb)))); | ||
73 | if (!count) | ||
74 | blacks = black_path_count(rb); | ||
75 | else | ||
76 | WARN_ON_ONCE((!rb->rb_left || !rb->rb_right) && | ||
77 | blacks != black_path_count(rb)); | ||
78 | prev_key = node->key; | ||
79 | count++; | ||
80 | } | ||
81 | WARN_ON_ONCE(count != nr_nodes); | ||
82 | } | ||
83 | |||
84 | static int rbtree_test_init(void) | ||
85 | { | ||
86 | int i, j; | ||
87 | cycles_t time1, time2, time; | ||
88 | |||
89 | printk(KERN_ALERT "rbtree testing"); | ||
90 | |||
91 | prandom32_seed(&rnd, 3141592653589793238); | ||
92 | init(); | ||
93 | |||
94 | time1 = get_cycles(); | ||
95 | |||
96 | for (i = 0; i < PERF_LOOPS; i++) { | ||
97 | for (j = 0; j < NODES; j++) | ||
98 | insert(nodes + j, &root); | ||
99 | for (j = 0; j < NODES; j++) | ||
100 | erase(nodes + j, &root); | ||
101 | } | ||
102 | |||
103 | time2 = get_cycles(); | ||
104 | time = time2 - time1; | ||
105 | |||
106 | time = div_u64(time, PERF_LOOPS); | ||
107 | printk(" -> %llu cycles\n", (unsigned long long)time); | ||
108 | |||
109 | for (i = 0; i < CHECK_LOOPS; i++) { | ||
110 | init(); | ||
111 | for (j = 0; j < NODES; j++) { | ||
112 | check(j); | ||
113 | insert(nodes + j, &root); | ||
114 | } | ||
115 | for (j = 0; j < NODES; j++) { | ||
116 | check(NODES - j); | ||
117 | erase(nodes + j, &root); | ||
118 | } | ||
119 | check(0); | ||
120 | } | ||
121 | |||
122 | return -EAGAIN; /* Fail will directly unload the module */ | ||
123 | } | ||
124 | |||
125 | static void rbtree_test_exit(void) | ||
126 | { | ||
127 | printk(KERN_ALERT "test exit\n"); | ||
128 | } | ||
129 | |||
130 | module_init(rbtree_test_init) | ||
131 | module_exit(rbtree_test_exit) | ||
132 | |||
133 | MODULE_LICENSE("GPL"); | ||
134 | MODULE_AUTHOR("Michel Lespinasse"); | ||
135 | MODULE_DESCRIPTION("Red Black Tree test"); | ||