]>
Commit | Line | Data |
---|---|---|
2025cf9e | 1 | // SPDX-License-Identifier: GPL-2.0-only |
4f3755d1 MW |
2 | /* |
3 | * multiorder.c: Multi-order radix tree entry testing | |
4 | * Copyright (c) 2016 Intel Corporation | |
5 | * Author: Ross Zwisler <ross.zwisler@linux.intel.com> | |
6 | * Author: Matthew Wilcox <matthew.r.wilcox@intel.com> | |
4f3755d1 MW |
7 | */ |
8 | #include <linux/radix-tree.h> | |
9 | #include <linux/slab.h> | |
10 | #include <linux/errno.h> | |
fd8f58c4 | 11 | #include <pthread.h> |
4f3755d1 MW |
12 | |
13 | #include "test.h" | |
14 | ||
4bb53bdd MW |
15 | static int item_insert_order(struct xarray *xa, unsigned long index, |
16 | unsigned order) | |
17 | { | |
18 | XA_STATE_ORDER(xas, xa, index, order); | |
19 | struct item *item = item_create(index, order); | |
20 | ||
21 | do { | |
22 | xas_lock(&xas); | |
23 | xas_store(&xas, item); | |
24 | xas_unlock(&xas); | |
25 | } while (xas_nomem(&xas, GFP_KERNEL)); | |
26 | ||
27 | if (!xas_error(&xas)) | |
28 | return 0; | |
29 | ||
30 | free(item); | |
31 | return xas_error(&xas); | |
32 | } | |
33 | ||
542980aa | 34 | void multiorder_iteration(struct xarray *xa) |
643b57d0 | 35 | { |
542980aa MW |
36 | XA_STATE(xas, xa, 0); |
37 | struct item *item; | |
8c1244de | 38 | int i, j, err; |
643b57d0 | 39 | |
643b57d0 RZ |
40 | #define NUM_ENTRIES 11 |
41 | int index[NUM_ENTRIES] = {0, 2, 4, 8, 16, 32, 34, 36, 64, 72, 128}; | |
42 | int order[NUM_ENTRIES] = {1, 1, 2, 3, 4, 1, 0, 1, 3, 0, 7}; | |
43 | ||
542980aa MW |
44 | printv(1, "Multiorder iteration test\n"); |
45 | ||
643b57d0 | 46 | for (i = 0; i < NUM_ENTRIES; i++) { |
542980aa | 47 | err = item_insert_order(xa, index[i], order[i]); |
643b57d0 RZ |
48 | assert(!err); |
49 | } | |
50 | ||
8c1244de MW |
51 | for (j = 0; j < 256; j++) { |
52 | for (i = 0; i < NUM_ENTRIES; i++) | |
53 | if (j <= (index[i] | ((1 << order[i]) - 1))) | |
54 | break; | |
55 | ||
542980aa MW |
56 | xas_set(&xas, j); |
57 | xas_for_each(&xas, item, ULONG_MAX) { | |
58 | int height = order[i] / XA_CHUNK_SHIFT; | |
59 | int shift = height * XA_CHUNK_SHIFT; | |
148deab2 | 60 | unsigned long mask = (1UL << order[i]) - 1; |
8c1244de | 61 | |
542980aa MW |
62 | assert((xas.xa_index | mask) == (index[i] | mask)); |
63 | assert(xas.xa_node->shift == shift); | |
148deab2 MW |
64 | assert(!radix_tree_is_internal_node(item)); |
65 | assert((item->index | mask) == (index[i] | mask)); | |
66 | assert(item->order == order[i]); | |
8c1244de MW |
67 | i++; |
68 | } | |
643b57d0 RZ |
69 | } |
70 | ||
542980aa | 71 | item_kill_tree(xa); |
643b57d0 RZ |
72 | } |
73 | ||
542980aa | 74 | void multiorder_tagged_iteration(struct xarray *xa) |
643b57d0 | 75 | { |
542980aa MW |
76 | XA_STATE(xas, xa, 0); |
77 | struct item *item; | |
8c1244de | 78 | int i, j; |
643b57d0 | 79 | |
643b57d0 RZ |
80 | #define MT_NUM_ENTRIES 9 |
81 | int index[MT_NUM_ENTRIES] = {0, 2, 4, 16, 32, 40, 64, 72, 128}; | |
82 | int order[MT_NUM_ENTRIES] = {1, 0, 2, 4, 3, 1, 3, 0, 7}; | |
83 | ||
84 | #define TAG_ENTRIES 7 | |
85 | int tag_index[TAG_ENTRIES] = {0, 4, 16, 40, 64, 72, 128}; | |
86 | ||
542980aa MW |
87 | printv(1, "Multiorder tagged iteration test\n"); |
88 | ||
643b57d0 | 89 | for (i = 0; i < MT_NUM_ENTRIES; i++) |
542980aa | 90 | assert(!item_insert_order(xa, index[i], order[i])); |
643b57d0 | 91 | |
542980aa | 92 | assert(!xa_marked(xa, XA_MARK_1)); |
643b57d0 RZ |
93 | |
94 | for (i = 0; i < TAG_ENTRIES; i++) | |
542980aa | 95 | xa_set_mark(xa, tag_index[i], XA_MARK_1); |
643b57d0 | 96 | |
8c1244de | 97 | for (j = 0; j < 256; j++) { |
148deab2 | 98 | int k; |
8c1244de MW |
99 | |
100 | for (i = 0; i < TAG_ENTRIES; i++) { | |
101 | for (k = i; index[k] < tag_index[i]; k++) | |
102 | ; | |
103 | if (j <= (index[k] | ((1 << order[k]) - 1))) | |
104 | break; | |
105 | } | |
106 | ||
542980aa MW |
107 | xas_set(&xas, j); |
108 | xas_for_each_marked(&xas, item, ULONG_MAX, XA_MARK_1) { | |
148deab2 | 109 | unsigned long mask; |
8c1244de MW |
110 | for (k = i; index[k] < tag_index[i]; k++) |
111 | ; | |
148deab2 | 112 | mask = (1UL << order[k]) - 1; |
8c1244de | 113 | |
542980aa MW |
114 | assert((xas.xa_index | mask) == (tag_index[i] | mask)); |
115 | assert(!xa_is_internal(item)); | |
148deab2 MW |
116 | assert((item->index | mask) == (tag_index[i] | mask)); |
117 | assert(item->order == order[k]); | |
8c1244de MW |
118 | i++; |
119 | } | |
643b57d0 RZ |
120 | } |
121 | ||
542980aa | 122 | assert(tag_tagged_items(xa, 0, ULONG_MAX, TAG_ENTRIES, XA_MARK_1, |
372266ba | 123 | XA_MARK_2) == TAG_ENTRIES); |
070c5ac2 | 124 | |
8c1244de MW |
125 | for (j = 0; j < 256; j++) { |
126 | int mask, k; | |
127 | ||
128 | for (i = 0; i < TAG_ENTRIES; i++) { | |
129 | for (k = i; index[k] < tag_index[i]; k++) | |
130 | ; | |
131 | if (j <= (index[k] | ((1 << order[k]) - 1))) | |
132 | break; | |
133 | } | |
134 | ||
542980aa MW |
135 | xas_set(&xas, j); |
136 | xas_for_each_marked(&xas, item, ULONG_MAX, XA_MARK_2) { | |
8c1244de MW |
137 | for (k = i; index[k] < tag_index[i]; k++) |
138 | ; | |
139 | mask = (1 << order[k]) - 1; | |
140 | ||
542980aa MW |
141 | assert((xas.xa_index | mask) == (tag_index[i] | mask)); |
142 | assert(!xa_is_internal(item)); | |
148deab2 MW |
143 | assert((item->index | mask) == (tag_index[i] | mask)); |
144 | assert(item->order == order[k]); | |
8c1244de MW |
145 | i++; |
146 | } | |
070c5ac2 MW |
147 | } |
148 | ||
542980aa | 149 | assert(tag_tagged_items(xa, 1, ULONG_MAX, MT_NUM_ENTRIES * 2, XA_MARK_1, |
372266ba | 150 | XA_MARK_0) == TAG_ENTRIES); |
070c5ac2 | 151 | i = 0; |
542980aa MW |
152 | xas_set(&xas, 0); |
153 | xas_for_each_marked(&xas, item, ULONG_MAX, XA_MARK_0) { | |
154 | assert(xas.xa_index == tag_index[i]); | |
070c5ac2 MW |
155 | i++; |
156 | } | |
542980aa | 157 | assert(i == TAG_ENTRIES); |
070c5ac2 | 158 | |
542980aa | 159 | item_kill_tree(xa); |
643b57d0 RZ |
160 | } |
161 | ||
fd8f58c4 RZ |
162 | bool stop_iteration = false; |
163 | ||
164 | static void *creator_func(void *ptr) | |
165 | { | |
166 | /* 'order' is set up to ensure we have sibling entries */ | |
167 | unsigned int order = RADIX_TREE_MAP_SHIFT - 1; | |
168 | struct radix_tree_root *tree = ptr; | |
169 | int i; | |
170 | ||
171 | for (i = 0; i < 10000; i++) { | |
172 | item_insert_order(tree, 0, order); | |
173 | item_delete_rcu(tree, 0); | |
174 | } | |
175 | ||
176 | stop_iteration = true; | |
177 | return NULL; | |
178 | } | |
179 | ||
180 | static void *iterator_func(void *ptr) | |
181 | { | |
542980aa | 182 | XA_STATE(xas, ptr, 0); |
fd8f58c4 | 183 | struct item *item; |
fd8f58c4 RZ |
184 | |
185 | while (!stop_iteration) { | |
186 | rcu_read_lock(); | |
542980aa MW |
187 | xas_for_each(&xas, item, ULONG_MAX) { |
188 | if (xas_retry(&xas, item)) | |
fd8f58c4 | 189 | continue; |
fd8f58c4 | 190 | |
542980aa | 191 | item_sanity(item, xas.xa_index); |
fd8f58c4 RZ |
192 | } |
193 | rcu_read_unlock(); | |
194 | } | |
195 | return NULL; | |
196 | } | |
197 | ||
542980aa | 198 | static void multiorder_iteration_race(struct xarray *xa) |
fd8f58c4 RZ |
199 | { |
200 | const int num_threads = sysconf(_SC_NPROCESSORS_ONLN); | |
201 | pthread_t worker_thread[num_threads]; | |
fd8f58c4 RZ |
202 | int i; |
203 | ||
542980aa | 204 | pthread_create(&worker_thread[0], NULL, &creator_func, xa); |
fd8f58c4 | 205 | for (i = 1; i < num_threads; i++) |
542980aa | 206 | pthread_create(&worker_thread[i], NULL, &iterator_func, xa); |
fd8f58c4 RZ |
207 | |
208 | for (i = 0; i < num_threads; i++) | |
209 | pthread_join(worker_thread[i], NULL); | |
210 | ||
542980aa | 211 | item_kill_tree(xa); |
fd8f58c4 RZ |
212 | } |
213 | ||
542980aa MW |
214 | static DEFINE_XARRAY(array); |
215 | ||
4f3755d1 MW |
216 | void multiorder_checks(void) |
217 | { | |
542980aa MW |
218 | multiorder_iteration(&array); |
219 | multiorder_tagged_iteration(&array); | |
220 | multiorder_iteration_race(&array); | |
2791653a MW |
221 | |
222 | radix_tree_cpu_dead(0); | |
4f3755d1 | 223 | } |
8ac04868 MW |
224 | |
225 | int __weak main(void) | |
226 | { | |
227 | radix_tree_init(); | |
228 | multiorder_checks(); | |
229 | return 0; | |
230 | } |