1 // SPDX-License-Identifier: GPL-2.0-only
14 __param(int, nnodes, 100, "Number of nodes in the rb-tree");
15 __param(int, perf_loops, 1000, "Number of iterations modifying the rb-tree");
16 __param(int, check_loops, 100, "Number of iterations modifying and verifying the rb-tree");
28 static struct rb_root_cached root = RB_ROOT_CACHED;  variable
33 static void insert(struct test_node *node, struct rb_root_cached *root)  in insert()  argument
35 	struct rb_node **new = &root->rb_root.rb_node, *parent = NULL;  in insert()
36 	u32 key = node->key;  in insert()
40 		if (key < rb_entry(parent, struct test_node, rb)->key)  in insert()
41 			new = &parent->rb_left;  in insert()
43 			new = &parent->rb_right;  in insert()
46 	rb_link_node(&node->rb, parent, new);  in insert()
47 	rb_insert_color(&node->rb, &root->rb_root);  in insert()
50 static void insert_cached(struct test_node *node, struct rb_root_cached *root)  in insert_cached()  argument
52 	struct rb_node **new = &root->rb_root.rb_node, *parent = NULL;  in insert_cached()
53 	u32 key = node->key;  in insert_cached()
58 		if (key < rb_entry(parent, struct test_node, rb)->key)  in insert_cached()
59 			new = &parent->rb_left;  in insert_cached()
61 			new = &parent->rb_right;  in insert_cached()
66 	rb_link_node(&node->rb, parent, new);  in insert_cached()
67 	rb_insert_color_cached(&node->rb, root, leftmost);  in insert_cached()
70 static inline void erase(struct test_node *node, struct rb_root_cached *root)  in erase()  argument
72 	rb_erase(&node->rb, &root->rb_root);  in erase()
75 static inline void erase_cached(struct test_node *node, struct rb_root_cached *root)  in erase_cached()  argument
77 	rb_erase_cached(&node->rb, root);  in erase_cached()
81 #define NODE_VAL(node) ((node)->val)  argument
86 static void insert_augmented(struct test_node *node,  in RB_DECLARE_CALLBACKS_MAX()
87 			     struct rb_root_cached *root)  in RB_DECLARE_CALLBACKS_MAX()
89 	struct rb_node **new = &root->rb_root.rb_node, *rb_parent = NULL;  in RB_DECLARE_CALLBACKS_MAX()
90 	u32 key = node->key;  in RB_DECLARE_CALLBACKS_MAX()
91 	u32 val = node->val;  in RB_DECLARE_CALLBACKS_MAX()
97 		if (parent->augmented < val)  in RB_DECLARE_CALLBACKS_MAX()
98 			parent->augmented = val;  in RB_DECLARE_CALLBACKS_MAX()
99 		if (key < parent->key)  in RB_DECLARE_CALLBACKS_MAX()
100 			new = &parent->rb.rb_left;  in RB_DECLARE_CALLBACKS_MAX()
102 			new = &parent->rb.rb_right;  in RB_DECLARE_CALLBACKS_MAX()
105 	node->augmented = val;  in RB_DECLARE_CALLBACKS_MAX()
106 	rb_link_node(&node->rb, rb_parent, new);  in RB_DECLARE_CALLBACKS_MAX()
107 	rb_insert_augmented(&node->rb, &root->rb_root, &augment_callbacks);  in RB_DECLARE_CALLBACKS_MAX()
110 static void insert_augmented_cached(struct test_node *node,  in insert_augmented_cached()  argument
111 				    struct rb_root_cached *root)  in insert_augmented_cached()  argument
113 	struct rb_node **new = &root->rb_root.rb_node, *rb_parent = NULL;  in insert_augmented_cached()
114 	u32 key = node->key;  in insert_augmented_cached()
115 	u32 val = node->val;  in insert_augmented_cached()
122 		if (parent->augmented < val)  in insert_augmented_cached()
123 			parent->augmented = val;  in insert_augmented_cached()
124 		if (key < parent->key)  in insert_augmented_cached()
125 			new = &parent->rb.rb_left;  in insert_augmented_cached()
127 			new = &parent->rb.rb_right;  in insert_augmented_cached()
132 	node->augmented = val;  in insert_augmented_cached()
133 	rb_link_node(&node->rb, rb_parent, new);  in insert_augmented_cached()
134 	rb_insert_augmented_cached(&node->rb, root,  in insert_augmented_cached()
139 static void erase_augmented(struct test_node *node, struct rb_root_cached *root)  in erase_augmented()  argument
141 	rb_erase_augmented(&node->rb, &root->rb_root, &augment_callbacks);  in erase_augmented()
144 static void erase_augmented_cached(struct test_node *node,  in erase_augmented_cached()  argument
145 				   struct rb_root_cached *root)  in erase_augmented_cached()  argument
147 	rb_erase_augmented_cached(&node->rb, root, &augment_callbacks);  in erase_augmented_cached()
161 	return !(rb->__rb_parent_color & 1);  in is_red()
176 	rbtree_postorder_for_each_entry_safe(cur, n, &root.rb_root, rb)  in check_postorder_foreach()
186 	for (rb = rb_first_postorder(&root.rb_root); rb; rb = rb_next_postorder(rb))  in check_postorder()
198 	for (rb = rb_first(&root.rb_root); rb; rb = rb_next(rb)) {  in check()
199 		struct test_node *node = rb_entry(rb, struct test_node, rb);  in check()  local
200 		WARN_ON_ONCE(node->key < prev_key);  in check()
206 			WARN_ON_ONCE((!rb->rb_left || !rb->rb_right) &&  in check()
208 		prev_key = node->key;  in check()
213 	WARN_ON_ONCE(count < (1 << black_path_count(rb_last(&root.rb_root))) - 1);  in check()
224 	for (rb = rb_first(&root.rb_root); rb; rb = rb_next(rb)) {  in check_augmented()
225 		struct test_node *node = rb_entry(rb, struct test_node, rb);  in check_augmented()  local
226 		u32 subtree, max = node->val;  in check_augmented()
227 		if (node->rb.rb_left) {  in check_augmented()
228 			subtree = rb_entry(node->rb.rb_left, struct test_node,  in check_augmented()
229 					   rb)->augmented;  in check_augmented()
233 		if (node->rb.rb_right) {  in check_augmented()
234 			subtree = rb_entry(node->rb.rb_right, struct test_node,  in check_augmented()
235 					   rb)->augmented;  in check_augmented()
239 		WARN_ON_ONCE(node->augmented != max);  in check_augmented()
247 	struct rb_node *node;  in basic_check()  local
257 			insert(nodes + j, &root);  in basic_check()
259 			erase(nodes + j, &root);  in basic_check()
263 	time = time2 - time1;  in basic_check()
266 	printk(" -> test 1 (latency of nnodes insert+delete): %llu cycles\n",  in basic_check()
273 			insert_cached(nodes + j, &root);  in basic_check()
275 			erase_cached(nodes + j, &root);  in basic_check()
279 	time = time2 - time1;  in basic_check()
282 	printk(" -> test 2 (latency of nnodes cached insert+delete): %llu cycles\n",  in basic_check()
286 		insert(nodes + i, &root);  in basic_check()
291 		for (node = rb_first(&root.rb_root); node; node = rb_next(node))  in basic_check()
296 	time = time2 - time1;  in basic_check()
299 	printk(" -> test 3 (latency of inorder traversal): %llu cycles\n",  in basic_check()
305 		node = rb_first(&root.rb_root);  in basic_check()
308 	time = time2 - time1;  in basic_check()
311 	printk(" -> test 4 (latency to fetch first node)\n");  in basic_check()
312 	printk("        non-cached: %llu cycles\n", (unsigned long long)time);  in basic_check()
317 		node = rb_first_cached(&root);  in basic_check()
320 	time = time2 - time1;  in basic_check()
326 		erase(nodes + i, &root);  in basic_check()
333 			insert(nodes + j, &root);  in basic_check()
336 			check(nnodes - j);  in basic_check()
337 			erase(nodes + j, &root);  in basic_check()
358 			insert_augmented(nodes + j, &root);  in augmented_check()
360 			erase_augmented(nodes + j, &root);  in augmented_check()
364 	time = time2 - time1;  in augmented_check()
367 	printk(" -> test 1 (latency of nnodes insert+delete): %llu cycles\n", (unsigned long long)time);  in augmented_check()
373 			insert_augmented_cached(nodes + j, &root);  in augmented_check()
375 			erase_augmented_cached(nodes + j, &root);  in augmented_check()
379 	time = time2 - time1;  in augmented_check()
382 …printk(" -> test 2 (latency of nnodes cached insert+delete): %llu cycles\n", (unsigned long long)t…  in augmented_check()
388 			insert_augmented(nodes + j, &root);  in augmented_check()
391 			check_augmented(nnodes - j);  in augmented_check()
392 			erase_augmented(nodes + j, &root);  in augmented_check()
404 		return -ENOMEM;  in rbtree_test_init()
413 	return -EAGAIN; /* Fail will directly unload the module */  in rbtree_test_init()