^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/interval_tree.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 interval tree");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 15) __param(int, perf_loops, 1000, "Number of iterations modifying the tree");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 16)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 17) __param(int, nsearches, 100, "Number of searches to the interval tree");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 18) __param(int, search_loops, 1000, "Number of iterations searching the tree");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 19) __param(bool, search_all, false, "Searches will iterate all nodes in the tree");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 20)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 21) __param(uint, max_endpoint, ~0, "Largest value for the interval's endpoint");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 22)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 23) static struct rb_root_cached root = RB_ROOT_CACHED;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 24) static struct interval_tree_node *nodes = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 25) static u32 *queries = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 26)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 27) static struct rnd_state rnd;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 28)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 29) static inline unsigned long
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 30) search(struct rb_root_cached *root, unsigned long start, unsigned long last)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 31) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 32) struct interval_tree_node *node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 33) unsigned long results = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 34)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 35) for (node = interval_tree_iter_first(root, start, last); node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 36) node = interval_tree_iter_next(node, start, last))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 37) results++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 38) return results;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 39) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 40)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 41) static void init(void)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 42) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 43) int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 44)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 45) for (i = 0; i < nnodes; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 46) u32 b = (prandom_u32_state(&rnd) >> 4) % max_endpoint;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 47) u32 a = (prandom_u32_state(&rnd) >> 4) % b;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 48)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 49) nodes[i].start = a;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 50) nodes[i].last = b;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 51) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 52)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 53) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 54) * Limit the search scope to what the user defined.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 55) * Otherwise we are merely measuring empty walks,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 56) * which is pointless.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 57) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 58) for (i = 0; i < nsearches; i++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 59) queries[i] = (prandom_u32_state(&rnd) >> 4) % max_endpoint;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 60) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 61)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 62) static int interval_tree_test_init(void)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 63) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 64) int i, j;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 65) unsigned long results;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 66) cycles_t time1, time2, time;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 67)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 68) nodes = kmalloc_array(nnodes, sizeof(struct interval_tree_node),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 69) GFP_KERNEL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 70) if (!nodes)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 71) return -ENOMEM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 72)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 73) queries = kmalloc_array(nsearches, sizeof(int), GFP_KERNEL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 74) if (!queries) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 75) kfree(nodes);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 76) return -ENOMEM;
^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) printk(KERN_ALERT "interval tree insert/remove");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 80)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 81) prandom_seed_state(&rnd, 3141592653589793238ULL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 82) init();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 83)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 84) time1 = get_cycles();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 85)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 86) for (i = 0; i < perf_loops; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 87) for (j = 0; j < nnodes; j++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 88) interval_tree_insert(nodes + j, &root);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 89) for (j = 0; j < nnodes; j++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 90) interval_tree_remove(nodes + j, &root);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 91) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 92)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 93) time2 = get_cycles();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 94) time = time2 - time1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 95)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 96) time = div_u64(time, perf_loops);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 97) printk(" -> %llu cycles\n", (unsigned long long)time);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 98)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 99) printk(KERN_ALERT "interval tree search");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 100)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 101) for (j = 0; j < nnodes; j++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 102) interval_tree_insert(nodes + j, &root);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 103)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 104) time1 = get_cycles();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 105)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 106) results = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 107) for (i = 0; i < search_loops; i++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 108) for (j = 0; j < nsearches; j++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 109) unsigned long start = search_all ? 0 : queries[j];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 110) unsigned long last = search_all ? max_endpoint : queries[j];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 111)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 112) results += search(&root, start, last);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 113) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 114)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 115) time2 = get_cycles();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 116) time = time2 - time1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 117)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 118) time = div_u64(time, search_loops);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 119) results = div_u64(results, search_loops);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 120) printk(" -> %llu cycles (%lu results)\n",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 121) (unsigned long long)time, results);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 122)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 123) kfree(queries);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 124) kfree(nodes);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 125)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 126) return -EAGAIN; /* Fail will directly unload the module */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 127) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 128)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 129) static void interval_tree_test_exit(void)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 130) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 131) printk(KERN_ALERT "test exit\n");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 132) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 133)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 134) module_init(interval_tree_test_init)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 135) module_exit(interval_tree_test_exit)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 136)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 137) MODULE_LICENSE("GPL");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 138) MODULE_AUTHOR("Michel Lespinasse");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 139) MODULE_DESCRIPTION("Interval Tree test");
Orange Pi5 kernel
Deprecated Linux kernel 5.10.110 for OrangePi 5/5B/5+ boards
3 Commits
0 Branches
0 Tags