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(struct xarray *xa)
43 {
44 	XA_STATE(xas, xa, 0);
45 	struct item *item;
46 	int i, j, err;
47 
48 #define NUM_ENTRIES 11
49 	int index[NUM_ENTRIES] = {0, 2, 4, 8, 16, 32, 34, 36, 64, 72, 128};
50 	int order[NUM_ENTRIES] = {1, 1, 2, 3,  4,  1,  0,  1,  3,  0, 7};
51 
52 	printv(1, "Multiorder iteration test\n");
53 
54 	for (i = 0; i < NUM_ENTRIES; i++) {
55 		err = item_insert_order(xa, index[i], order[i]);
56 		assert(!err);
57 	}
58 
59 	for (j = 0; j < 256; j++) {
60 		for (i = 0; i < NUM_ENTRIES; i++)
61 			if (j <= (index[i] | ((1 << order[i]) - 1)))
62 				break;
63 
64 		xas_set(&xas, j);
65 		xas_for_each(&xas, item, ULONG_MAX) {
66 			int height = order[i] / XA_CHUNK_SHIFT;
67 			int shift = height * XA_CHUNK_SHIFT;
68 			unsigned long mask = (1UL << order[i]) - 1;
69 
70 			assert((xas.xa_index | mask) == (index[i] | mask));
71 			assert(xas.xa_node->shift == shift);
72 			assert(!radix_tree_is_internal_node(item));
73 			assert((item->index | mask) == (index[i] | mask));
74 			assert(item->order == order[i]);
75 			i++;
76 		}
77 	}
78 
79 	item_kill_tree(xa);
80 }
81 
82 void multiorder_tagged_iteration(struct xarray *xa)
83 {
84 	XA_STATE(xas, xa, 0);
85 	struct item *item;
86 	int i, j;
87 
88 #define MT_NUM_ENTRIES 9
89 	int index[MT_NUM_ENTRIES] = {0, 2, 4, 16, 32, 40, 64, 72, 128};
90 	int order[MT_NUM_ENTRIES] = {1, 0, 2, 4,  3,  1,  3,  0,   7};
91 
92 #define TAG_ENTRIES 7
93 	int tag_index[TAG_ENTRIES] = {0, 4, 16, 40, 64, 72, 128};
94 
95 	printv(1, "Multiorder tagged iteration test\n");
96 
97 	for (i = 0; i < MT_NUM_ENTRIES; i++)
98 		assert(!item_insert_order(xa, index[i], order[i]));
99 
100 	assert(!xa_marked(xa, XA_MARK_1));
101 
102 	for (i = 0; i < TAG_ENTRIES; i++)
103 		xa_set_mark(xa, tag_index[i], XA_MARK_1);
104 
105 	for (j = 0; j < 256; j++) {
106 		int k;
107 
108 		for (i = 0; i < TAG_ENTRIES; i++) {
109 			for (k = i; index[k] < tag_index[i]; k++)
110 				;
111 			if (j <= (index[k] | ((1 << order[k]) - 1)))
112 				break;
113 		}
114 
115 		xas_set(&xas, j);
116 		xas_for_each_marked(&xas, item, ULONG_MAX, XA_MARK_1) {
117 			unsigned long mask;
118 			for (k = i; index[k] < tag_index[i]; k++)
119 				;
120 			mask = (1UL << order[k]) - 1;
121 
122 			assert((xas.xa_index | mask) == (tag_index[i] | mask));
123 			assert(!xa_is_internal(item));
124 			assert((item->index | mask) == (tag_index[i] | mask));
125 			assert(item->order == order[k]);
126 			i++;
127 		}
128 	}
129 
130 	assert(tag_tagged_items(xa, 0, ULONG_MAX, TAG_ENTRIES, XA_MARK_1,
131 				XA_MARK_2) == TAG_ENTRIES);
132 
133 	for (j = 0; j < 256; j++) {
134 		int mask, k;
135 
136 		for (i = 0; i < TAG_ENTRIES; i++) {
137 			for (k = i; index[k] < tag_index[i]; k++)
138 				;
139 			if (j <= (index[k] | ((1 << order[k]) - 1)))
140 				break;
141 		}
142 
143 		xas_set(&xas, j);
144 		xas_for_each_marked(&xas, item, ULONG_MAX, XA_MARK_2) {
145 			for (k = i; index[k] < tag_index[i]; k++)
146 				;
147 			mask = (1 << order[k]) - 1;
148 
149 			assert((xas.xa_index | mask) == (tag_index[i] | mask));
150 			assert(!xa_is_internal(item));
151 			assert((item->index | mask) == (tag_index[i] | mask));
152 			assert(item->order == order[k]);
153 			i++;
154 		}
155 	}
156 
157 	assert(tag_tagged_items(xa, 1, ULONG_MAX, MT_NUM_ENTRIES * 2, XA_MARK_1,
158 				XA_MARK_0) == TAG_ENTRIES);
159 	i = 0;
160 	xas_set(&xas, 0);
161 	xas_for_each_marked(&xas, item, ULONG_MAX, XA_MARK_0) {
162 		assert(xas.xa_index == tag_index[i]);
163 		i++;
164 	}
165 	assert(i == TAG_ENTRIES);
166 
167 	item_kill_tree(xa);
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 	XA_STATE(xas, ptr, 0);
191 	struct item *item;
192 
193 	while (!stop_iteration) {
194 		rcu_read_lock();
195 		xas_for_each(&xas, item, ULONG_MAX) {
196 			if (xas_retry(&xas, item))
197 				continue;
198 
199 			item_sanity(item, xas.xa_index);
200 		}
201 		rcu_read_unlock();
202 	}
203 	return NULL;
204 }
205 
206 static void multiorder_iteration_race(struct xarray *xa)
207 {
208 	const int num_threads = sysconf(_SC_NPROCESSORS_ONLN);
209 	pthread_t worker_thread[num_threads];
210 	int i;
211 
212 	pthread_create(&worker_thread[0], NULL, &creator_func, xa);
213 	for (i = 1; i < num_threads; i++)
214 		pthread_create(&worker_thread[i], NULL, &iterator_func, xa);
215 
216 	for (i = 0; i < num_threads; i++)
217 		pthread_join(worker_thread[i], NULL);
218 
219 	item_kill_tree(xa);
220 }
221 
222 static DEFINE_XARRAY(array);
223 
224 void multiorder_checks(void)
225 {
226 	multiorder_iteration(&array);
227 	multiorder_tagged_iteration(&array);
228 	multiorder_iteration_race(&array);
229 
230 	radix_tree_cpu_dead(0);
231 }
232 
233 int __weak main(void)
234 {
235 	radix_tree_init();
236 	multiorder_checks();
237 	return 0;
238 }
239