^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1) // SPDX-License-Identifier: GPL-2.0-only
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 2) #include <linux/module.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 3) #include <linux/moduleparam.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 4) #include <linux/rbtree_augmented.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 5) #include <linux/random.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 6) #include <linux/slab.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 7) #include <asm/timex.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 8)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 9) #define __param(type, name, init, msg) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 10) static type name = init; \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 11) module_param(name, type, 0444); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 12) MODULE_PARM_DESC(name, msg);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 13)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 14) __param(int, nnodes, 100, "Number of nodes in the rb-tree");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 15) __param(int, perf_loops, 1000, "Number of iterations modifying the rb-tree");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 16) __param(int, check_loops, 100, "Number of iterations modifying and verifying the rb-tree");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 17)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 18) struct test_node {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 19) u32 key;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 20) struct rb_node rb;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 21)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 22) /* following fields used for testing augmented rbtree functionality */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 23) u32 val;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 24) u32 augmented;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 25) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 26)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 27) static struct rb_root_cached root = RB_ROOT_CACHED;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 28) static struct test_node *nodes = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 29)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 30) static struct rnd_state rnd;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 31)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 32) static void insert(struct test_node *node, struct rb_root_cached *root)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 33) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 34) struct rb_node **new = &root->rb_root.rb_node, *parent = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 35) u32 key = node->key;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 36)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 37) while (*new) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 38) parent = *new;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 39) if (key < rb_entry(parent, struct test_node, rb)->key)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 40) new = &parent->rb_left;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 41) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 42) new = &parent->rb_right;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 43) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 44)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 45) rb_link_node(&node->rb, parent, new);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 46) rb_insert_color(&node->rb, &root->rb_root);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 47) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 48)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 49) static void insert_cached(struct test_node *node, struct rb_root_cached *root)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 50) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 51) struct rb_node **new = &root->rb_root.rb_node, *parent = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 52) u32 key = node->key;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 53) bool leftmost = true;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 54)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 55) while (*new) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 56) parent = *new;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 57) if (key < rb_entry(parent, struct test_node, rb)->key)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 58) new = &parent->rb_left;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 59) else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 60) new = &parent->rb_right;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 61) leftmost = false;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 62) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 63) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 64)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 65) rb_link_node(&node->rb, parent, new);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 66) rb_insert_color_cached(&node->rb, root, leftmost);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 67) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 68)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 69) static inline void erase(struct test_node *node, struct rb_root_cached *root)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 70) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 71) rb_erase(&node->rb, &root->rb_root);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 72) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 73)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 74) static inline void erase_cached(struct test_node *node, struct rb_root_cached *root)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 75) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 76) rb_erase_cached(&node->rb, root);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 77) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 78)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 79)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 80) #define NODE_VAL(node) ((node)->val)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 81)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 82) RB_DECLARE_CALLBACKS_MAX(static, augment_callbacks,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 83) struct test_node, rb, u32, augmented, NODE_VAL)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 84)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 85) static void insert_augmented(struct test_node *node,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 86) struct rb_root_cached *root)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 87) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 88) struct rb_node **new = &root->rb_root.rb_node, *rb_parent = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 89) u32 key = node->key;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 90) u32 val = node->val;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 91) struct test_node *parent;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 92)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 93) while (*new) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 94) rb_parent = *new;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 95) parent = rb_entry(rb_parent, struct test_node, rb);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 96) if (parent->augmented < val)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 97) parent->augmented = val;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 98) if (key < parent->key)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 99) new = &parent->rb.rb_left;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 100) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 101) new = &parent->rb.rb_right;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 102) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 103)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 104) node->augmented = val;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 105) rb_link_node(&node->rb, rb_parent, new);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 106) rb_insert_augmented(&node->rb, &root->rb_root, &augment_callbacks);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 107) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 108)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 109) static void insert_augmented_cached(struct test_node *node,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 110) struct rb_root_cached *root)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 111) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 112) struct rb_node **new = &root->rb_root.rb_node, *rb_parent = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 113) u32 key = node->key;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 114) u32 val = node->val;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 115) struct test_node *parent;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 116) bool leftmost = true;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 117)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 118) while (*new) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 119) rb_parent = *new;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 120) parent = rb_entry(rb_parent, struct test_node, rb);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 121) if (parent->augmented < val)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 122) parent->augmented = val;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 123) if (key < parent->key)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 124) new = &parent->rb.rb_left;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 125) else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 126) new = &parent->rb.rb_right;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 127) leftmost = false;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 128) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 129) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 130)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 131) node->augmented = val;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 132) rb_link_node(&node->rb, rb_parent, new);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 133) rb_insert_augmented_cached(&node->rb, root,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 134) leftmost, &augment_callbacks);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 135) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 136)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 137)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 138) static void erase_augmented(struct test_node *node, struct rb_root_cached *root)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 139) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 140) rb_erase_augmented(&node->rb, &root->rb_root, &augment_callbacks);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 141) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 142)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 143) static void erase_augmented_cached(struct test_node *node,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 144) struct rb_root_cached *root)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 145) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 146) rb_erase_augmented_cached(&node->rb, root, &augment_callbacks);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 147) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 148)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 149) static void init(void)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 150) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 151) int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 152) for (i = 0; i < nnodes; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 153) nodes[i].key = prandom_u32_state(&rnd);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 154) nodes[i].val = prandom_u32_state(&rnd);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 155) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 156) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 157)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 158) static bool is_red(struct rb_node *rb)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 159) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 160) return !(rb->__rb_parent_color & 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 161) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 162)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 163) static int black_path_count(struct rb_node *rb)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 164) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 165) int count;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 166) for (count = 0; rb; rb = rb_parent(rb))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 167) count += !is_red(rb);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 168) return count;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 169) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 170)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 171) static void check_postorder_foreach(int nr_nodes)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 172) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 173) struct test_node *cur, *n;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 174) int count = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 175) rbtree_postorder_for_each_entry_safe(cur, n, &root.rb_root, rb)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 176) count++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 177)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 178) WARN_ON_ONCE(count != nr_nodes);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 179) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 180)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 181) static void check_postorder(int nr_nodes)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 182) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 183) struct rb_node *rb;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 184) int count = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 185) for (rb = rb_first_postorder(&root.rb_root); rb; rb = rb_next_postorder(rb))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 186) count++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 187)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 188) WARN_ON_ONCE(count != nr_nodes);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 189) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 190)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 191) static void check(int nr_nodes)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 192) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 193) struct rb_node *rb;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 194) int count = 0, blacks = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 195) u32 prev_key = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 196)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 197) for (rb = rb_first(&root.rb_root); rb; rb = rb_next(rb)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 198) struct test_node *node = rb_entry(rb, struct test_node, rb);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 199) WARN_ON_ONCE(node->key < prev_key);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 200) WARN_ON_ONCE(is_red(rb) &&
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 201) (!rb_parent(rb) || is_red(rb_parent(rb))));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 202) if (!count)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 203) blacks = black_path_count(rb);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 204) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 205) WARN_ON_ONCE((!rb->rb_left || !rb->rb_right) &&
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 206) blacks != black_path_count(rb));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 207) prev_key = node->key;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 208) count++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 209) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 210)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 211) WARN_ON_ONCE(count != nr_nodes);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 212) WARN_ON_ONCE(count < (1 << black_path_count(rb_last(&root.rb_root))) - 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 213)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 214) check_postorder(nr_nodes);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 215) check_postorder_foreach(nr_nodes);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 216) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 217)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 218) static void check_augmented(int nr_nodes)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 219) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 220) struct rb_node *rb;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 221)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 222) check(nr_nodes);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 223) for (rb = rb_first(&root.rb_root); rb; rb = rb_next(rb)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 224) struct test_node *node = rb_entry(rb, struct test_node, rb);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 225) u32 subtree, max = node->val;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 226) if (node->rb.rb_left) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 227) subtree = rb_entry(node->rb.rb_left, struct test_node,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 228) rb)->augmented;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 229) if (max < subtree)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 230) max = subtree;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 231) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 232) if (node->rb.rb_right) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 233) subtree = rb_entry(node->rb.rb_right, struct test_node,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 234) rb)->augmented;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 235) if (max < subtree)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 236) max = subtree;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 237) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 238) WARN_ON_ONCE(node->augmented != max);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 239) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 240) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 241)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 242) static int __init rbtree_test_init(void)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 243) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 244) int i, j;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 245) cycles_t time1, time2, time;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 246) struct rb_node *node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 247)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 248) nodes = kmalloc_array(nnodes, sizeof(*nodes), GFP_KERNEL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 249) if (!nodes)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 250) return -ENOMEM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 251)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 252) printk(KERN_ALERT "rbtree testing");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 253)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 254) prandom_seed_state(&rnd, 3141592653589793238ULL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 255) init();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 256)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 257) time1 = get_cycles();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 258)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 259) for (i = 0; i < perf_loops; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 260) for (j = 0; j < nnodes; j++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 261) insert(nodes + j, &root);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 262) for (j = 0; j < nnodes; j++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 263) erase(nodes + j, &root);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 264) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 265)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 266) time2 = get_cycles();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 267) time = time2 - time1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 268)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 269) time = div_u64(time, perf_loops);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 270) printk(" -> test 1 (latency of nnodes insert+delete): %llu cycles\n",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 271) (unsigned long long)time);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 272)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 273) time1 = get_cycles();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 274)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 275) for (i = 0; i < perf_loops; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 276) for (j = 0; j < nnodes; j++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 277) insert_cached(nodes + j, &root);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 278) for (j = 0; j < nnodes; j++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 279) erase_cached(nodes + j, &root);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 280) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 281)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 282) time2 = get_cycles();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 283) time = time2 - time1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 284)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 285) time = div_u64(time, perf_loops);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 286) printk(" -> test 2 (latency of nnodes cached insert+delete): %llu cycles\n",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 287) (unsigned long long)time);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 288)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 289) for (i = 0; i < nnodes; i++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 290) insert(nodes + i, &root);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 291)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 292) time1 = get_cycles();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 293)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 294) for (i = 0; i < perf_loops; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 295) for (node = rb_first(&root.rb_root); node; node = rb_next(node))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 296) ;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 297) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 298)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 299) time2 = get_cycles();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 300) time = time2 - time1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 301)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 302) time = div_u64(time, perf_loops);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 303) printk(" -> test 3 (latency of inorder traversal): %llu cycles\n",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 304) (unsigned long long)time);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 305)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 306) time1 = get_cycles();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 307)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 308) for (i = 0; i < perf_loops; i++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 309) node = rb_first(&root.rb_root);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 310)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 311) time2 = get_cycles();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 312) time = time2 - time1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 313)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 314) time = div_u64(time, perf_loops);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 315) printk(" -> test 4 (latency to fetch first node)\n");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 316) printk(" non-cached: %llu cycles\n", (unsigned long long)time);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 317)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 318) time1 = get_cycles();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 319)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 320) for (i = 0; i < perf_loops; i++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 321) node = rb_first_cached(&root);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 322)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 323) time2 = get_cycles();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 324) time = time2 - time1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 325)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 326) time = div_u64(time, perf_loops);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 327) printk(" cached: %llu cycles\n", (unsigned long long)time);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 328)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 329) for (i = 0; i < nnodes; i++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 330) erase(nodes + i, &root);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 331)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 332) /* run checks */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 333) for (i = 0; i < check_loops; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 334) init();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 335) for (j = 0; j < nnodes; j++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 336) check(j);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 337) insert(nodes + j, &root);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 338) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 339) for (j = 0; j < nnodes; j++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 340) check(nnodes - j);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 341) erase(nodes + j, &root);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 342) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 343) check(0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 344) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 345)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 346) printk(KERN_ALERT "augmented rbtree testing");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 347)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 348) init();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 349)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 350) time1 = get_cycles();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 351)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 352) for (i = 0; i < perf_loops; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 353) for (j = 0; j < nnodes; j++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 354) insert_augmented(nodes + j, &root);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 355) for (j = 0; j < nnodes; j++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 356) erase_augmented(nodes + j, &root);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 357) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 358)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 359) time2 = get_cycles();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 360) time = time2 - time1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 361)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 362) time = div_u64(time, perf_loops);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 363) printk(" -> test 1 (latency of nnodes insert+delete): %llu cycles\n", (unsigned long long)time);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 364)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 365) time1 = get_cycles();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 366)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 367) for (i = 0; i < perf_loops; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 368) for (j = 0; j < nnodes; j++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 369) insert_augmented_cached(nodes + j, &root);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 370) for (j = 0; j < nnodes; j++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 371) erase_augmented_cached(nodes + j, &root);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 372) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 373)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 374) time2 = get_cycles();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 375) time = time2 - time1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 376)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 377) time = div_u64(time, perf_loops);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 378) printk(" -> test 2 (latency of nnodes cached insert+delete): %llu cycles\n", (unsigned long long)time);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 379)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 380) for (i = 0; i < check_loops; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 381) init();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 382) for (j = 0; j < nnodes; j++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 383) check_augmented(j);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 384) insert_augmented(nodes + j, &root);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 385) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 386) for (j = 0; j < nnodes; j++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 387) check_augmented(nnodes - j);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 388) erase_augmented(nodes + j, &root);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 389) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 390) check_augmented(0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 391) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 392)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 393) kfree(nodes);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 394)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 395) return -EAGAIN; /* Fail will directly unload the module */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 396) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 397)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 398) static void __exit rbtree_test_exit(void)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 399) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 400) printk(KERN_ALERT "test exit\n");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 401) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 402)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 403) module_init(rbtree_test_init)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 404) module_exit(rbtree_test_exit)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 405)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 406) MODULE_LICENSE("GPL");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 407) MODULE_AUTHOR("Michel Lespinasse");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 408) MODULE_DESCRIPTION("Red Black Tree test");
Orange Pi5 kernel
Deprecated Linux kernel 5.10.110 for OrangePi 5/5B/5+ boards
3 Commits
0 Branches
0 Tags