Something went wrong. Try again.
(I'm so sorry!) Linux kernel mirror (for testing) git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git
kernel os linux
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385// SPDX-License-Identifier: GPL-2.0-only#include <linux/module.h>#include <linux/moduleparam.h>#include <linux/rbtree_augmented.h>#include <linux/prandom.h>#include <linux/slab.h>#include <asm/timex.h>
#define __param(type, name, init, msg) \ static type name = init; \ module_param(name, type, 0444); \ MODULE_PARM_DESC(name, msg);
__param(int, nnodes, 100, "Number of nodes in the rb-tree");__param(int, perf_loops, 1000, "Number of iterations modifying the rb-tree");__param(int, check_loops, 100, "Number of iterations modifying and verifying the rb-tree");__param(ullong, seed, 3141592653589793238ULL, "Random seed");
struct test_node { u32 key; struct rb_node rb;
/* following fields used for testing augmented rbtree functionality */ u32 val; u32 augmented;};
static struct rb_root_cached root = RB_ROOT_CACHED;static struct test_node *nodes = NULL;
static struct rnd_state rnd;
static inline bool less(struct rb_node *a, const struct rb_node *b){ return rb_entry(a, struct test_node, rb)->key < rb_entry(b, struct test_node, rb)->key;}
static void insert(struct test_node *node, struct rb_root_cached *root){ rb_add(&node->rb, &root->rb_root, less);}
static void insert_cached(struct test_node *node, struct rb_root_cached *root){ rb_add_cached(&node->rb, root, less);}
static inline void erase(struct test_node *node, struct rb_root_cached *root){ rb_erase(&node->rb, &root->rb_root);}
static inline void erase_cached(struct test_node *node, struct rb_root_cached *root){ rb_erase_cached(&node->rb, root);}
#define NODE_VAL(node) ((node)->val)
RB_DECLARE_CALLBACKS_MAX(static, augment_callbacks, struct test_node, rb, u32, augmented, NODE_VAL)
static void insert_augmented(struct test_node *node, struct rb_root_cached *root){ struct rb_node **new = &root->rb_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->rb_root, &augment_callbacks);}
static void insert_augmented_cached(struct test_node *node, struct rb_root_cached *root){ node->augmented = node->val; rb_add_augmented_cached(&node->rb, root, less, &augment_callbacks);}
static void erase_augmented(struct test_node *node, struct rb_root_cached *root){ rb_erase_augmented(&node->rb, &root->rb_root, &augment_callbacks);}
static void erase_augmented_cached(struct test_node *node, struct rb_root_cached *root){ rb_erase_augmented_cached(&node->rb, root, &augment_callbacks);}
static void init(void){ int i; for (i = 0; i < nnodes; i++) { nodes[i].key = prandom_u32_state(&rnd); nodes[i].val = prandom_u32_state(&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_postorder_foreach(int nr_nodes){ struct test_node *cur, *n; int count = 0; rbtree_postorder_for_each_entry_safe(cur, n, &root.rb_root, rb) count++;
WARN_ON_ONCE(count != nr_nodes);}
static void check_postorder(int nr_nodes){ struct rb_node *rb; int count = 0; for (rb = rb_first_postorder(&root.rb_root); rb; rb = rb_next_postorder(rb)) count++;
WARN_ON_ONCE(count != nr_nodes);}
static void check(int nr_nodes){ struct rb_node *rb; int count = 0, blacks = 0; u32 prev_key = 0;
for (rb = rb_first(&root.rb_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); WARN_ON_ONCE(count < (1 << black_path_count(rb_last(&root.rb_root))) - 1);
check_postorder(nr_nodes); check_postorder_foreach(nr_nodes);}
static void check_augmented(int nr_nodes){ struct rb_node *rb;
check(nr_nodes); for (rb = rb_first(&root.rb_root); rb; rb = rb_next(rb)) { struct test_node *node = rb_entry(rb, struct test_node, rb); u32 subtree, max = node->val; if (node->rb.rb_left) { subtree = rb_entry(node->rb.rb_left, struct test_node, rb)->augmented; if (max < subtree) max = subtree; } if (node->rb.rb_right) { subtree = rb_entry(node->rb.rb_right, struct test_node, rb)->augmented; if (max < subtree) max = subtree; } WARN_ON_ONCE(node->augmented != max); }}
static int basic_check(void){ int i, j; cycles_t time1, time2, time; struct rb_node *node;
printk(KERN_ALERT "rbtree testing");
init();
time1 = get_cycles();
for (i = 0; i < perf_loops; i++) { for (j = 0; j < nnodes; j++) insert(nodes + j, &root); for (j = 0; j < nnodes; j++) erase(nodes + j, &root); }
time2 = get_cycles(); time = time2 - time1;
time = div_u64(time, perf_loops); printk(" -> test 1 (latency of nnodes insert+delete): %llu cycles\n", (unsigned long long)time);
time1 = get_cycles();
for (i = 0; i < perf_loops; i++) { for (j = 0; j < nnodes; j++) insert_cached(nodes + j, &root); for (j = 0; j < nnodes; j++) erase_cached(nodes + j, &root); }
time2 = get_cycles(); time = time2 - time1;
time = div_u64(time, perf_loops); printk(" -> test 2 (latency of nnodes cached insert+delete): %llu cycles\n", (unsigned long long)time);
for (i = 0; i < nnodes; i++) insert(nodes + i, &root);
time1 = get_cycles();
for (i = 0; i < perf_loops; i++) { for (node = rb_first(&root.rb_root); node; node = rb_next(node)) ; }
time2 = get_cycles(); time = time2 - time1;
time = div_u64(time, perf_loops); printk(" -> test 3 (latency of inorder traversal): %llu cycles\n", (unsigned long long)time);
time1 = get_cycles();
for (i = 0; i < perf_loops; i++) node = rb_first(&root.rb_root);
time2 = get_cycles(); time = time2 - time1;
time = div_u64(time, perf_loops); printk(" -> test 4 (latency to fetch first node)\n"); printk(" non-cached: %llu cycles\n", (unsigned long long)time);
time1 = get_cycles();
for (i = 0; i < perf_loops; i++) node = rb_first_cached(&root);
time2 = get_cycles(); time = time2 - time1;
time = div_u64(time, perf_loops); printk(" cached: %llu cycles\n", (unsigned long long)time);
for (i = 0; i < nnodes; i++) erase(nodes + i, &root);
/* run checks */ for (i = 0; i < check_loops; i++) { init(); for (j = 0; j < nnodes; j++) { check(j); insert(nodes + j, &root); } for (j = 0; j < nnodes; j++) { check(nnodes - j); erase(nodes + j, &root); } check(0); }
return 0;}
static int augmented_check(void){ int i, j; cycles_t time1, time2, time;
printk(KERN_ALERT "augmented rbtree testing");
init();
time1 = get_cycles();
for (i = 0; i < perf_loops; i++) { for (j = 0; j < nnodes; j++) insert_augmented(nodes + j, &root); for (j = 0; j < nnodes; j++) erase_augmented(nodes + j, &root); }
time2 = get_cycles(); time = time2 - time1;
time = div_u64(time, perf_loops); printk(" -> test 1 (latency of nnodes insert+delete): %llu cycles\n", (unsigned long long)time);
time1 = get_cycles();
for (i = 0; i < perf_loops; i++) { for (j = 0; j < nnodes; j++) insert_augmented_cached(nodes + j, &root); for (j = 0; j < nnodes; j++) erase_augmented_cached(nodes + j, &root); }
time2 = get_cycles(); time = time2 - time1;
time = div_u64(time, perf_loops); printk(" -> test 2 (latency of nnodes cached insert+delete): %llu cycles\n", (unsigned long long)time);
for (i = 0; i < check_loops; i++) { init(); for (j = 0; j < nnodes; j++) { check_augmented(j); insert_augmented(nodes + j, &root); } for (j = 0; j < nnodes; j++) { check_augmented(nnodes - j); erase_augmented(nodes + j, &root); } check_augmented(0); }
return 0;}
static int __init rbtree_test_init(void){ nodes = kmalloc_objs(*nodes, nnodes); if (!nodes) return -ENOMEM;
prandom_seed_state(&rnd, seed);
basic_check(); augmented_check();
kfree(nodes);
return -EAGAIN; /* Fail will directly unload the module */}
static void __exit 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");