#include <linux/module.h>
#include <linux/interval_tree.h>
#include <linux/random.h>
#include <asm/timex.h>

#define NODES        100
#define PERF_LOOPS   100000
#define SEARCHES     100
#define SEARCH_LOOPS 10000

static struct rb_root root = RB_ROOT;
static struct interval_tree_node nodes[NODES];
static u32 queries[SEARCHES];

static struct rnd_state rnd;

static inline unsigned long
search(unsigned long query, struct rb_root *root)
{
	struct interval_tree_node *node;
	unsigned long results = 0;

	for (node = interval_tree_iter_first(root, query, query); node;
	     node = interval_tree_iter_next(node, query, query))
		results++;
	return results;
}

static void init(void)
{
	int i;
	for (i = 0; i < NODES; i++) {
		u32 a = prandom_u32_state(&rnd);
		u32 b = prandom_u32_state(&rnd);
		if (a <= b) {
			nodes[i].start = a;
			nodes[i].last = b;
		} else {
			nodes[i].start = b;
			nodes[i].last = a;
		}
	}
	for (i = 0; i < SEARCHES; i++)
		queries[i] = prandom_u32_state(&rnd);
}

static int interval_tree_test_init(void)
{
	int i, j;
	unsigned long results;
	cycles_t time1, time2, time;

	printk(KERN_ALERT "interval tree insert/remove");

	prandom_seed_state(&rnd, 3141592653589793238ULL);
	init();

	time1 = get_cycles();

	for (i = 0; i < PERF_LOOPS; i++) {
		for (j = 0; j < NODES; j++)
			interval_tree_insert(nodes + j, &root);
		for (j = 0; j < NODES; j++)
			interval_tree_remove(nodes + j, &root);
	}

	time2 = get_cycles();
	time = time2 - time1;

	time = div_u64(time, PERF_LOOPS);
	printk(" -> %llu cycles\n", (unsigned long long)time);

	printk(KERN_ALERT "interval tree search");

	for (j = 0; j < NODES; j++)
		interval_tree_insert(nodes + j, &root);

	time1 = get_cycles();

	results = 0;
	for (i = 0; i < SEARCH_LOOPS; i++)
		for (j = 0; j < SEARCHES; j++)
			results += search(queries[j], &root);

	time2 = get_cycles();
	time = time2 - time1;

	time = div_u64(time, SEARCH_LOOPS);
	results = div_u64(results, SEARCH_LOOPS);
	printk(" -> %llu cycles (%lu results)\n",
	       (unsigned long long)time, results);

	return -EAGAIN; /* Fail will directly unload the module */
}

static void interval_tree_test_exit(void)
{
	printk(KERN_ALERT "test exit\n");
}

module_init(interval_tree_test_init)
module_exit(interval_tree_test_exit)

MODULE_LICENSE("GPL");
MODULE_AUTHOR("Michel Lespinasse");
MODULE_DESCRIPTION("Interval Tree test");
lue='author'>author</option>
<option value='committer'>committer</option>
<option value='range'>range</option>
</select>
<input class='txt' type='search' size='10' name='q' value=''/>
<input type='submit' value='search'/>
</form>
</td></tr></table>
<div class='path'>path: <a href='/cgit.cgi/linux/net-next.git/log/?id=b876b9aaadce9c6bb47508c4b31efc474b70f179&amp;showmsg=1'>root</a>/<a href='/cgit.cgi/linux/net-next.git/log/net?id=b876b9aaadce9c6bb47508c4b31efc474b70f179&amp;showmsg=1'>net</a>/<a href='/cgit.cgi/linux/net-next.git/log/net/sched?id=b876b9aaadce9c6bb47508c4b31efc474b70f179&amp;showmsg=1'>sched</a></div><div class='content'><table class='list nowrap'><tr class='nohover'><th class='left'>Age</th><th class='left'>Commit message (<a href='/cgit.cgi/linux/net-next.git/log/net/sched?id=b876b9aaadce9c6bb47508c4b31efc474b70f179'>Collapse</a>)</th><th class='left'>Author</th><th class='left'>Files</th><th class='left'>Lines</th></tr>
<tr class='logheader'><td><span title='2017-02-03 15:16:46 -0500'>2017-02-03</span></td><td class='logsubject'><a href='/cgit.cgi/linux/net-next.git/commit/net/sched?id=295a6e06d21e1f469c9f38b00125a13b60ad4e7c'>net/sched: act_ife: Change to use ife module</a></td><td>Yotam Gigi</td><td>2</td><td><span class='deletions'>-78</span>/<span class='insertions'>+33</span></td></tr>
<tr class='nohover-highlight'><td/><td colspan='5' class='logmsg'>
Use the encode/decode functionality from the ife module instead of using
implementation inside the act_ife.

Reviewed-by: Jiri Pirko &lt;jiri@mellanox.com&gt;
Signed-off-by: Yotam Gigi &lt;yotamg@mellanox.com&gt;
Signed-off-by: Jamal Hadi Salim &lt;jhs@mojatatu.com&gt;
Signed-off-by: Roman Mashak &lt;mrv@mojatatu.com&gt;
Signed-off-by: David S. Miller &lt;davem@davemloft.net&gt;


</td></tr>
<tr class='logheader'><td><span title='2017-02-03 15:16:45 -0500'>2017-02-03</span></td><td class='logsubject'><a href='/cgit.cgi/linux/net-next.git/commit/net/sched?id=1d5e7c859e81a66674d194c346119d154d31e9dc'>net/sched: act_ife: Unexport ife_tlv_meta_encode</a></td><td>Yotam Gigi</td><td>1</td><td><span class='deletions'>-2</span>/<span class='insertions'>+2</span></td></tr>
<tr class='nohover-highlight'><td/><td colspan='5' class='logmsg'>
As the function ife_tlv_meta_encode is not used by any other module,
unexport it and make it static for the act_ife module.

Signed-off-by: Yotam Gigi &lt;yotamg@mellanox.com&gt;
Signed-off-by: Jamal Hadi Salim &lt;jhs@mojatatu.com&gt;
Signed-off-by: Roman Mashak &lt;mrv@mojatatu.com&gt;
Signed-off-by: David S. Miller &lt;davem@davemloft.net&gt;


</td></tr>
<tr class='logheader'><td><span title='2017-02-02 16:54:00 -0500'>2017-02-02</span></td><td class='logsubject'><a href='/cgit.cgi/linux/net-next.git/commit/net/sched?id=e2160156bf2a7d5018e99a9993fbcdda0abac09b'>Merge git://git.kernel.org/pub/scm/linux/kernel/git/davem/net</a></td><td>David S. Miller</td><td>2</td><td><span class='deletions'>-85</span>/<span class='insertions'>+48</span></td></tr>
<tr class='nohover-highlight'><td/><td colspan='5' class='logmsg'>
All merge conflicts were simple overlapping changes.

Signed-off-by: David S. Miller &lt;davem@davemloft.net&gt;


</td></tr>
<tr class='logheader'><td><span title='2017-02-01 14:10:03 -0500'>2017-02-01</span></td><td class='logsubject'><a href='/cgit.cgi/linux/net-next.git/commit/net/sched?id=f3b20313aef93f9cfda76fec2c05625f88510f18'>net/sched: act_psample: Remove unnecessary ASSERT_RTNL</a></td><td>Yotam Gigi</td><td>1</td><td><span class='deletions'>-1</span>/<span class='insertions'>+0</span></td></tr>
<tr class='nohover-highlight'><td/><td colspan='5' class='logmsg'>
The ASSERT_RTNL is not necessary in the init function, as it does not
touch any rtnl protected structures, as opposed to the mirred action which
does have to hold a net device.

Reported-by: Cong Wang &lt;xiyou.wangcong@gmail.com&gt;
Reviewed-by: Jiri Pirko &lt;jiri@mellanox.com&gt;
Signed-off-by: Yotam Gigi &lt;yotamg@mellanox.com&gt;
Signed-off-by: David S. Miller &lt;davem@davemloft.net&gt;


</td></tr>
<tr class='logheader'><td><span title='2017-02-01 14:10:03 -0500'>2017-02-01</span></td><td class='logsubject'><a href='/cgit.cgi/linux/net-next.git/commit/net/sched?id=cadb9c9fdbc6a624d57b5ecdfd412b5800848703'>net/sched: act_sample: Fix error path in init</a></td><td>Yotam Gigi</td><td>1</td><td><span class='deletions'>-1</span>/<span class='insertions'>+4</span></td></tr>
<tr class='nohover-highlight'><td/><td colspan='5' class='logmsg'>
Fix error path of in sample init, by releasing the tc hash in case of
failure in psample_group creation.

Fixes: 5c5670fae430 ("net/sched: Introduce sample tc action")
Reported-by: Cong Wang &lt;xiyou.wangcong@gmail.com&gt;
Reviewed-by: Jiri Pirko &lt;jiri@mellanox.com&gt;
Signed-off-by: Yotam Gigi &lt;yotamg@mellanox.com&gt;
Signed-off-by: David S. Miller &lt;davem@davemloft.net&gt;


</td></tr>
<tr class='logheader'><td><span title='2017-02-01 11:57:33 -0500'>2017-02-01</span></td><td class='logsubject'><a href='/cgit.cgi/linux/net-next.git/commit/net/sched?id=fd62d9f5c575f0792f150109f1fd24a0d4b3f854'>net/sched: matchall: Fix configuration race</a></td><td>Yotam Gigi</td><td>1</td><td><span class='deletions'>-82</span>/<span class='insertions'>+45</span></td></tr>
<tr class='nohover-highlight'><td/><td colspan='5' class='logmsg'>
In the current version, the matchall internal state is split into two
structs: cls_matchall_head and cls_matchall_filter. This makes little
sense, as matchall instance supports only one filter, and there is no
situation where one exists and the other does not. In addition, that led
to some races when filter was deleted while packet was processed.

Unify that two structs into one, thus simplifying the process of matchall
creation and deletion. As a result, the new, delete and get callbacks have
a dummy implementation where all the work is done in destroy and change
callbacks, as was done in cls_cgroup.

Fixes: bf3994d2ed31 ("net/sched: introduce Match-all classifier")
Reported-by: Daniel Borkmann &lt;daniel@iogearbox.net&gt;
Signed-off-by: Yotam Gigi &lt;yotamg@mellanox.com&gt;
Acked-by: Jiri Pirko &lt;jiri@mellanox.com&gt;
Signed-off-by: David S. Miller &lt;davem@davemloft.net&gt;


</td></tr>