LXR linux/lib/interval_tree

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