1 /*
2  * multiorder.c: Multi-order radix tree entry testing
3  * Copyright (c) 2016 Intel Corporation
4  * Author: Ross Zwisler <ross.zwisler@linux.intel.com>
5  * Author: Matthew Wilcox <matthew.r.wilcox@intel.com>
6  *
7  * This program is free software; you can redistribute it and/or modify it
8  * under the terms and conditions of the GNU General Public License,
9  * version 2, as published by the Free Software Foundation.
10  *
11  * This program is distributed in the hope it will be useful, but WITHOUT
12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
14  * more details.
15  */
16 #include <linux/radix-tree.h>
17 #include <linux/slab.h>
18 #include <linux/errno.h>
19 #include <pthread.h>
20 
21 #include "test.h"
22 
23 static int item_insert_order(struct xarray *xa, unsigned long index,
24 			unsigned order)
25 {
26 	XA_STATE_ORDER(xas, xa, index, order);
27 	struct item *item = item_create(index, order);
28 
29 	do {
30 		xas_lock(&xas);
31 		xas_store(&xas, item);
32 		xas_unlock(&xas);
33 	} while (xas_nomem(&xas, GFP_KERNEL));
34 
35 	if (!xas_error(&xas))
36 		return 0;
37 
38 	free(item);
39 	return xas_error(&xas);
40 }
41 
42 void multiorder_iteration(void)
43 {
44 	RADIX_TREE(tree, GFP_KERNEL);
45 	struct radix_tree_iter iter;
46 	void **slot;
47 	int i, j, err;
48 
49 	printv(1, "Multiorder iteration test\n");
50 
51 #define NUM_ENTRIES 11
52 	int index[NUM_ENTRIES] = {0, 2, 4, 8, 16, 32, 34, 36, 64, 72, 128};
53 	int order[NUM_ENTRIES] = {1, 1, 2, 3,  4,  1,  0,  1,  3,  0, 7};
54 
55 	for (i = 0; i < NUM_ENTRIES; i++) {
56 		err = item_insert_order(&tree, index[i], order[i]);
57 		assert(!err);
58 	}
59 
60 	for (j = 0; j < 256; j++) {
61 		for (i = 0; i < NUM_ENTRIES; i++)
62 			if (j <= (index[i] | ((1 << order[i]) - 1)))
63 				break;
64 
65 		radix_tree_for_each_slot(slot, &tree, &iter, j) {
66 			int height = order[i] / RADIX_TREE_MAP_SHIFT;
67 			int shift = height * RADIX_TREE_MAP_SHIFT;
68 			unsigned long mask = (1UL << order[i]) - 1;
69 			struct item *item = *slot;
70 
71 			assert((iter.index | mask) == (index[i] | mask));
72 			assert(iter.shift == shift);
73 			assert(!radix_tree_is_internal_node(item));
74 			assert((item->index | mask) == (index[i] | mask));
75 			assert(item->order == order[i]);
76 			i++;
77 		}
78 	}
79 
80 	item_kill_tree(&tree);
81 }
82 
83 void multiorder_tagged_iteration(void)
84 {
85 	RADIX_TREE(tree, GFP_KERNEL);
86 	struct radix_tree_iter iter;
87 	void **slot;
88 	int i, j;
89 
90 	printv(1, "Multiorder tagged iteration test\n");
91 
92 #define MT_NUM_ENTRIES 9
93 	int index[MT_NUM_ENTRIES] = {0, 2, 4, 16, 32, 40, 64, 72, 128};
94 	int order[MT_NUM_ENTRIES] = {1, 0, 2, 4,  3,  1,  3,  0,   7};
95 
96 #define TAG_ENTRIES 7
97 	int tag_index[TAG_ENTRIES] = {0, 4, 16, 40, 64, 72, 128};
98 
99 	for (i = 0; i < MT_NUM_ENTRIES; i++)
100 		assert(!item_insert_order(&tree, index[i], order[i]));
101 
102 	assert(!radix_tree_tagged(&tree, 1));
103 
104 	for (i = 0; i < TAG_ENTRIES; i++)
105 		assert(radix_tree_tag_set(&tree, tag_index[i], 1));
106 
107 	for (j = 0; j < 256; j++) {
108 		int k;
109 
110 		for (i = 0; i < TAG_ENTRIES; i++) {
111 			for (k = i; index[k] < tag_index[i]; k++)
112 				;
113 			if (j <= (index[k] | ((1 << order[k]) - 1)))
114 				break;
115 		}
116 
117 		radix_tree_for_each_tagged(slot, &tree, &iter, j, 1) {
118 			unsigned long mask;
119 			struct item *item = *slot;
120 			for (k = i; index[k] < tag_index[i]; k++)
121 				;
122 			mask = (1UL << order[k]) - 1;
123 
124 			assert((iter.index | mask) == (tag_index[i] | mask));
125 			assert(!radix_tree_is_internal_node(item));
126 			assert((item->index | mask) == (tag_index[i] | mask));
127 			assert(item->order == order[k]);
128 			i++;
129 		}
130 	}
131 
132 	assert(tag_tagged_items(&tree, 0, ~0UL, TAG_ENTRIES, XA_MARK_1,
133 				XA_MARK_2) == TAG_ENTRIES);
134 
135 	for (j = 0; j < 256; j++) {
136 		int mask, k;
137 
138 		for (i = 0; i < TAG_ENTRIES; i++) {
139 			for (k = i; index[k] < tag_index[i]; k++)
140 				;
141 			if (j <= (index[k] | ((1 << order[k]) - 1)))
142 				break;
143 		}
144 
145 		radix_tree_for_each_tagged(slot, &tree, &iter, j, 2) {
146 			struct item *item = *slot;
147 			for (k = i; index[k] < tag_index[i]; k++)
148 				;
149 			mask = (1 << order[k]) - 1;
150 
151 			assert((iter.index | mask) == (tag_index[i] | mask));
152 			assert(!radix_tree_is_internal_node(item));
153 			assert((item->index | mask) == (tag_index[i] | mask));
154 			assert(item->order == order[k]);
155 			i++;
156 		}
157 	}
158 
159 	assert(tag_tagged_items(&tree, 1, ~0UL, MT_NUM_ENTRIES * 2, XA_MARK_1,
160 				XA_MARK_0) == TAG_ENTRIES);
161 	i = 0;
162 	radix_tree_for_each_tagged(slot, &tree, &iter, 0, 0) {
163 		assert(iter.index == tag_index[i]);
164 		i++;
165 	}
166 
167 	item_kill_tree(&tree);
168 }
169 
170 bool stop_iteration = false;
171 
172 static void *creator_func(void *ptr)
173 {
174 	/* 'order' is set up to ensure we have sibling entries */
175 	unsigned int order = RADIX_TREE_MAP_SHIFT - 1;
176 	struct radix_tree_root *tree = ptr;
177 	int i;
178 
179 	for (i = 0; i < 10000; i++) {
180 		item_insert_order(tree, 0, order);
181 		item_delete_rcu(tree, 0);
182 	}
183 
184 	stop_iteration = true;
185 	return NULL;
186 }
187 
188 static void *iterator_func(void *ptr)
189 {
190 	struct radix_tree_root *tree = ptr;
191 	struct radix_tree_iter iter;
192 	struct item *item;
193 	void **slot;
194 
195 	while (!stop_iteration) {
196 		rcu_read_lock();
197 		radix_tree_for_each_slot(slot, tree, &iter, 0) {
198 			item = radix_tree_deref_slot(slot);
199 
200 			if (!item)
201 				continue;
202 			if (radix_tree_deref_retry(item)) {
203 				slot = radix_tree_iter_retry(&iter);
204 				continue;
205 			}
206 
207 			item_sanity(item, iter.index);
208 		}
209 		rcu_read_unlock();
210 	}
211 	return NULL;
212 }
213 
214 static void multiorder_iteration_race(void)
215 {
216 	const int num_threads = sysconf(_SC_NPROCESSORS_ONLN);
217 	pthread_t worker_thread[num_threads];
218 	RADIX_TREE(tree, GFP_KERNEL);
219 	int i;
220 
221 	pthread_create(&worker_thread[0], NULL, &creator_func, &tree);
222 	for (i = 1; i < num_threads; i++)
223 		pthread_create(&worker_thread[i], NULL, &iterator_func, &tree);
224 
225 	for (i = 0; i < num_threads; i++)
226 		pthread_join(worker_thread[i], NULL);
227 
228 	item_kill_tree(&tree);
229 }
230 
231 void multiorder_checks(void)
232 {
233 	multiorder_iteration();
234 	multiorder_tagged_iteration();
235 	multiorder_iteration_race();
236 
237 	radix_tree_cpu_dead(0);
238 }
239 
240 int __weak main(void)
241 {
242 	radix_tree_init();
243 	multiorder_checks();
244 	return 0;
245 }
246