09c434b8a0047 lib/interval_tree_test.c (Thomas Gleixner 2019-05-19 13:08:20 +0100 1) // SPDX-License-Identifier: GPL-2.0-only
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 2) #include <linux/module.h>
a54dae0338b7f lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:46 -0700 3) #include <linux/moduleparam.h>
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 4) #include <linux/interval_tree.h>
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 5) #include <linux/random.h>
a54dae0338b7f lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:46 -0700 6) #include <linux/slab.h>
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 7) #include <asm/timex.h>
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 8)
a54dae0338b7f lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:46 -0700 9) #define __param(type, name, init, msg) \
a54dae0338b7f lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:46 -0700 10) static type name = init; \
a54dae0338b7f lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:46 -0700 11) module_param(name, type, 0444); \
a54dae0338b7f lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:46 -0700 12) MODULE_PARM_DESC(name, msg);
a54dae0338b7f lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:46 -0700 13)
a54dae0338b7f lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:46 -0700 14) __param(int, nnodes, 100, "Number of nodes in the interval tree");
0b548e33e6cb2 lib/interval_tree_test.c (Davidlohr Bueso 2017-11-17 15:28:27 -0800 15) __param(int, perf_loops, 1000, "Number of iterations modifying the tree");
a54dae0338b7f lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:46 -0700 16)
a54dae0338b7f lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:46 -0700 17) __param(int, nsearches, 100, "Number of searches to the interval tree");
0b548e33e6cb2 lib/interval_tree_test.c (Davidlohr Bueso 2017-11-17 15:28:27 -0800 18) __param(int, search_loops, 1000, "Number of iterations searching the tree");
c46ecce431ebe lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:52 -0700 19) __param(bool, search_all, false, "Searches will iterate all nodes in the tree");
a54dae0338b7f lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:46 -0700 20)
a8ec14d4f6aa8 lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:49 -0700 21) __param(uint, max_endpoint, ~0, "Largest value for the interval's endpoint");
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 22)
f808c13fd3738 lib/interval_tree_test.c (Davidlohr Bueso 2017-09-08 16:15:08 -0700 23) static struct rb_root_cached root = RB_ROOT_CACHED;
a54dae0338b7f lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:46 -0700 24) static struct interval_tree_node *nodes = NULL;
a54dae0338b7f lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:46 -0700 25) static u32 *queries = NULL;
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 26)
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 27) static struct rnd_state rnd;
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 28)
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 29) static inline unsigned long
f808c13fd3738 lib/interval_tree_test.c (Davidlohr Bueso 2017-09-08 16:15:08 -0700 30) search(struct rb_root_cached *root, unsigned long start, unsigned long last)
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 31) {
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 32) struct interval_tree_node *node;
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 33) unsigned long results = 0;
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 34)
c46ecce431ebe lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:52 -0700 35) for (node = interval_tree_iter_first(root, start, last); node;
c46ecce431ebe lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:52 -0700 36) node = interval_tree_iter_next(node, start, last))
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 37) results++;
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 38) return results;
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 39) }
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 40)
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 41) static void init(void)
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 42) {
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 43) int i;
a54dae0338b7f lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:46 -0700 44)
a54dae0338b7f lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:46 -0700 45) for (i = 0; i < nnodes; i++) {
a8ec14d4f6aa8 lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:49 -0700 46) u32 b = (prandom_u32_state(&rnd) >> 4) % max_endpoint;
a8ec14d4f6aa8 lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:49 -0700 47) u32 a = (prandom_u32_state(&rnd) >> 4) % b;
a8ec14d4f6aa8 lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:49 -0700 48)
a8ec14d4f6aa8 lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:49 -0700 49) nodes[i].start = a;
a8ec14d4f6aa8 lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:49 -0700 50) nodes[i].last = b;
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 51) }
a8ec14d4f6aa8 lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:49 -0700 52)
a8ec14d4f6aa8 lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:49 -0700 53) /*
a8ec14d4f6aa8 lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:49 -0700 54) * Limit the search scope to what the user defined.
a8ec14d4f6aa8 lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:49 -0700 55) * Otherwise we are merely measuring empty walks,
a8ec14d4f6aa8 lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:49 -0700 56) * which is pointless.
a8ec14d4f6aa8 lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:49 -0700 57) */
a54dae0338b7f lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:46 -0700 58) for (i = 0; i < nsearches; i++)
a8ec14d4f6aa8 lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:49 -0700 59) queries[i] = (prandom_u32_state(&rnd) >> 4) % max_endpoint;
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 60) }
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 61)
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 62) static int interval_tree_test_init(void)
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 63) {
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 64) int i, j;
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 65) unsigned long results;
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 66) cycles_t time1, time2, time;
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 67)
6da2ec56059c3 lib/interval_tree_test.c (Kees Cook 2018-06-12 13:55:00 -0700 68) nodes = kmalloc_array(nnodes, sizeof(struct interval_tree_node),
6da2ec56059c3 lib/interval_tree_test.c (Kees Cook 2018-06-12 13:55:00 -0700 69) GFP_KERNEL);
a54dae0338b7f lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:46 -0700 70) if (!nodes)
a54dae0338b7f lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:46 -0700 71) return -ENOMEM;
a54dae0338b7f lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:46 -0700 72)
6da2ec56059c3 lib/interval_tree_test.c (Kees Cook 2018-06-12 13:55:00 -0700 73) queries = kmalloc_array(nsearches, sizeof(int), GFP_KERNEL);
a54dae0338b7f lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:46 -0700 74) if (!queries) {
a54dae0338b7f lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:46 -0700 75) kfree(nodes);
a54dae0338b7f lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:46 -0700 76) return -ENOMEM;
a54dae0338b7f lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:46 -0700 77) }
a54dae0338b7f lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:46 -0700 78)
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 79) printk(KERN_ALERT "interval tree insert/remove");
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 80)
496f2f93b1cc2 lib/interval_tree_test_main.c (Akinobu Mita 2012-12-17 16:04:23 -0800 81) prandom_seed_state(&rnd, 3141592653589793238ULL);
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 82) init();
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 83)
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 84) time1 = get_cycles();
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 85)
a54dae0338b7f lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:46 -0700 86) for (i = 0; i < perf_loops; i++) {
a54dae0338b7f lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:46 -0700 87) for (j = 0; j < nnodes; j++)
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 88) interval_tree_insert(nodes + j, &root);
a54dae0338b7f lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:46 -0700 89) for (j = 0; j < nnodes; j++)
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 90) interval_tree_remove(nodes + j, &root);
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 91) }
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 92)
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 93) time2 = get_cycles();
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 94) time = time2 - time1;
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 95)
a54dae0338b7f lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:46 -0700 96) time = div_u64(time, perf_loops);
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 97) printk(" -> %llu cycles\n", (unsigned long long)time);
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 98)
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 99) printk(KERN_ALERT "interval tree search");
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 100)
a54dae0338b7f lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:46 -0700 101) for (j = 0; j < nnodes; j++)
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 102) interval_tree_insert(nodes + j, &root);
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 103)
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 104) time1 = get_cycles();
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 105)
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 106) results = 0;
a54dae0338b7f lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:46 -0700 107) for (i = 0; i < search_loops; i++)
c46ecce431ebe lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:52 -0700 108) for (j = 0; j < nsearches; j++) {
c46ecce431ebe lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:52 -0700 109) unsigned long start = search_all ? 0 : queries[j];
c46ecce431ebe lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:52 -0700 110) unsigned long last = search_all ? max_endpoint : queries[j];
c46ecce431ebe lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:52 -0700 111)
c46ecce431ebe lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:52 -0700 112) results += search(&root, start, last);
c46ecce431ebe lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:52 -0700 113) }
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 114)
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 115) time2 = get_cycles();
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 116) time = time2 - time1;
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 117)
a54dae0338b7f lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:46 -0700 118) time = div_u64(time, search_loops);
a54dae0338b7f lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:46 -0700 119) results = div_u64(results, search_loops);
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 120) printk(" -> %llu cycles (%lu results)\n",
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 121) (unsigned long long)time, results);
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 122)
a54dae0338b7f lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:46 -0700 123) kfree(queries);
a54dae0338b7f lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:46 -0700 124) kfree(nodes);
a54dae0338b7f lib/interval_tree_test.c (Davidlohr Bueso 2017-07-10 15:51:46 -0700 125)
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 126) return -EAGAIN; /* Fail will directly unload the module */
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 127) }
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 128)
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 129) static void interval_tree_test_exit(void)
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 130) {
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 131) printk(KERN_ALERT "test exit\n");
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 132) }
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 133)
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 134) module_init(interval_tree_test_init)
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 135) module_exit(interval_tree_test_exit)
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 136)
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 137) MODULE_LICENSE("GPL");
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 138) MODULE_AUTHOR("Michel Lespinasse");
fff3fd8a1210a lib/interval_tree_test_main.c (Michel Lespinasse 2012-10-08 16:31:23 -0700 139) MODULE_DESCRIPTION("Interval Tree test");
VisionFive2 Linux kernel
StarFive Tech Linux Kernel for VisionFive (JH7110) boards (mirror)
More than 9999 Commits
32 Branches
54 Tags