Michel Lespinasse | fff3fd8 | 2012-10-08 16:31:23 -0700 | [diff] [blame] | 1 | #include <linux/module.h> |
Davidlohr Bueso | c114bdd | 2017-07-10 15:51:46 -0700 | [diff] [blame^] | 2 | #include <linux/moduleparam.h> |
Michel Lespinasse | fff3fd8 | 2012-10-08 16:31:23 -0700 | [diff] [blame] | 3 | #include <linux/interval_tree.h> |
| 4 | #include <linux/random.h> |
Davidlohr Bueso | c114bdd | 2017-07-10 15:51:46 -0700 | [diff] [blame^] | 5 | #include <linux/slab.h> |
Michel Lespinasse | fff3fd8 | 2012-10-08 16:31:23 -0700 | [diff] [blame] | 6 | #include <asm/timex.h> |
| 7 | |
Davidlohr Bueso | c114bdd | 2017-07-10 15:51:46 -0700 | [diff] [blame^] | 8 | #define __param(type, name, init, msg) \ |
| 9 | static type name = init; \ |
| 10 | module_param(name, type, 0444); \ |
| 11 | MODULE_PARM_DESC(name, msg); |
| 12 | |
| 13 | __param(int, nnodes, 100, "Number of nodes in the interval tree"); |
| 14 | __param(int, perf_loops, 100000, "Number of iterations modifying the tree"); |
| 15 | |
| 16 | __param(int, nsearches, 100, "Number of searches to the interval tree"); |
| 17 | __param(int, search_loops, 10000, "Number of iterations searching the tree"); |
| 18 | |
Michel Lespinasse | fff3fd8 | 2012-10-08 16:31:23 -0700 | [diff] [blame] | 19 | |
| 20 | static struct rb_root root = RB_ROOT; |
Davidlohr Bueso | c114bdd | 2017-07-10 15:51:46 -0700 | [diff] [blame^] | 21 | static struct interval_tree_node *nodes = NULL; |
| 22 | static u32 *queries = NULL; |
Michel Lespinasse | fff3fd8 | 2012-10-08 16:31:23 -0700 | [diff] [blame] | 23 | |
| 24 | static struct rnd_state rnd; |
| 25 | |
| 26 | static inline unsigned long |
| 27 | search(unsigned long query, struct rb_root *root) |
| 28 | { |
| 29 | struct interval_tree_node *node; |
| 30 | unsigned long results = 0; |
| 31 | |
| 32 | for (node = interval_tree_iter_first(root, query, query); node; |
| 33 | node = interval_tree_iter_next(node, query, query)) |
| 34 | results++; |
| 35 | return results; |
| 36 | } |
| 37 | |
| 38 | static void init(void) |
| 39 | { |
| 40 | int i; |
Davidlohr Bueso | c114bdd | 2017-07-10 15:51:46 -0700 | [diff] [blame^] | 41 | |
| 42 | for (i = 0; i < nnodes; i++) { |
Akinobu Mita | 496f2f9 | 2012-12-17 16:04:23 -0800 | [diff] [blame] | 43 | u32 a = prandom_u32_state(&rnd); |
| 44 | u32 b = prandom_u32_state(&rnd); |
Michel Lespinasse | fff3fd8 | 2012-10-08 16:31:23 -0700 | [diff] [blame] | 45 | if (a <= b) { |
| 46 | nodes[i].start = a; |
| 47 | nodes[i].last = b; |
| 48 | } else { |
| 49 | nodes[i].start = b; |
| 50 | nodes[i].last = a; |
| 51 | } |
| 52 | } |
Davidlohr Bueso | c114bdd | 2017-07-10 15:51:46 -0700 | [diff] [blame^] | 53 | for (i = 0; i < nsearches; i++) |
Akinobu Mita | 496f2f9 | 2012-12-17 16:04:23 -0800 | [diff] [blame] | 54 | queries[i] = prandom_u32_state(&rnd); |
Michel Lespinasse | fff3fd8 | 2012-10-08 16:31:23 -0700 | [diff] [blame] | 55 | } |
| 56 | |
| 57 | static int interval_tree_test_init(void) |
| 58 | { |
| 59 | int i, j; |
| 60 | unsigned long results; |
| 61 | cycles_t time1, time2, time; |
| 62 | |
Davidlohr Bueso | c114bdd | 2017-07-10 15:51:46 -0700 | [diff] [blame^] | 63 | nodes = kmalloc(nnodes * sizeof(struct interval_tree_node), GFP_KERNEL); |
| 64 | if (!nodes) |
| 65 | return -ENOMEM; |
| 66 | |
| 67 | queries = kmalloc(nsearches * sizeof(int), GFP_KERNEL); |
| 68 | if (!queries) { |
| 69 | kfree(nodes); |
| 70 | return -ENOMEM; |
| 71 | } |
| 72 | |
Michel Lespinasse | fff3fd8 | 2012-10-08 16:31:23 -0700 | [diff] [blame] | 73 | printk(KERN_ALERT "interval tree insert/remove"); |
| 74 | |
Akinobu Mita | 496f2f9 | 2012-12-17 16:04:23 -0800 | [diff] [blame] | 75 | prandom_seed_state(&rnd, 3141592653589793238ULL); |
Michel Lespinasse | fff3fd8 | 2012-10-08 16:31:23 -0700 | [diff] [blame] | 76 | init(); |
| 77 | |
| 78 | time1 = get_cycles(); |
| 79 | |
Davidlohr Bueso | c114bdd | 2017-07-10 15:51:46 -0700 | [diff] [blame^] | 80 | for (i = 0; i < perf_loops; i++) { |
| 81 | for (j = 0; j < nnodes; j++) |
Michel Lespinasse | fff3fd8 | 2012-10-08 16:31:23 -0700 | [diff] [blame] | 82 | interval_tree_insert(nodes + j, &root); |
Davidlohr Bueso | c114bdd | 2017-07-10 15:51:46 -0700 | [diff] [blame^] | 83 | for (j = 0; j < nnodes; j++) |
Michel Lespinasse | fff3fd8 | 2012-10-08 16:31:23 -0700 | [diff] [blame] | 84 | interval_tree_remove(nodes + j, &root); |
| 85 | } |
| 86 | |
| 87 | time2 = get_cycles(); |
| 88 | time = time2 - time1; |
| 89 | |
Davidlohr Bueso | c114bdd | 2017-07-10 15:51:46 -0700 | [diff] [blame^] | 90 | time = div_u64(time, perf_loops); |
Michel Lespinasse | fff3fd8 | 2012-10-08 16:31:23 -0700 | [diff] [blame] | 91 | printk(" -> %llu cycles\n", (unsigned long long)time); |
| 92 | |
| 93 | printk(KERN_ALERT "interval tree search"); |
| 94 | |
Davidlohr Bueso | c114bdd | 2017-07-10 15:51:46 -0700 | [diff] [blame^] | 95 | for (j = 0; j < nnodes; j++) |
Michel Lespinasse | fff3fd8 | 2012-10-08 16:31:23 -0700 | [diff] [blame] | 96 | interval_tree_insert(nodes + j, &root); |
| 97 | |
| 98 | time1 = get_cycles(); |
| 99 | |
| 100 | results = 0; |
Davidlohr Bueso | c114bdd | 2017-07-10 15:51:46 -0700 | [diff] [blame^] | 101 | for (i = 0; i < search_loops; i++) |
| 102 | for (j = 0; j < nsearches; j++) |
Michel Lespinasse | fff3fd8 | 2012-10-08 16:31:23 -0700 | [diff] [blame] | 103 | results += search(queries[j], &root); |
| 104 | |
| 105 | time2 = get_cycles(); |
| 106 | time = time2 - time1; |
| 107 | |
Davidlohr Bueso | c114bdd | 2017-07-10 15:51:46 -0700 | [diff] [blame^] | 108 | time = div_u64(time, search_loops); |
| 109 | results = div_u64(results, search_loops); |
Michel Lespinasse | fff3fd8 | 2012-10-08 16:31:23 -0700 | [diff] [blame] | 110 | printk(" -> %llu cycles (%lu results)\n", |
| 111 | (unsigned long long)time, results); |
| 112 | |
Davidlohr Bueso | c114bdd | 2017-07-10 15:51:46 -0700 | [diff] [blame^] | 113 | kfree(queries); |
| 114 | kfree(nodes); |
| 115 | |
Michel Lespinasse | fff3fd8 | 2012-10-08 16:31:23 -0700 | [diff] [blame] | 116 | return -EAGAIN; /* Fail will directly unload the module */ |
| 117 | } |
| 118 | |
| 119 | static void interval_tree_test_exit(void) |
| 120 | { |
| 121 | printk(KERN_ALERT "test exit\n"); |
| 122 | } |
| 123 | |
| 124 | module_init(interval_tree_test_init) |
| 125 | module_exit(interval_tree_test_exit) |
| 126 | |
| 127 | MODULE_LICENSE("GPL"); |
| 128 | MODULE_AUTHOR("Michel Lespinasse"); |
| 129 | MODULE_DESCRIPTION("Interval Tree test"); |