cachepc-linux

Fork of AMDESE/linux with modifications for CachePC side-channel attack
git clone https://git.sinitax.com/sinitax/cachepc-linux
Log | Files | Refs | README | LICENSE | sfeed.txt

interval_tree_test.c (3505B)

      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");