Commit | Line | Data |
---|---|---|
dd6b880e MD |
1 | // SPDX-License-Identifier: LGPL-2.1 |
2 | #define _GNU_SOURCE | |
3 | #include <assert.h> | |
4 | #include <pthread.h> | |
5 | #include <sched.h> | |
6 | #include <stdint.h> | |
7 | #include <stdio.h> | |
8 | #include <stdlib.h> | |
9 | #include <string.h> | |
10 | #include <stddef.h> | |
11 | ||
12 | #include <rseq/percpu-op.h> | |
13 | ||
14 | #define ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[0])) | |
15 | ||
16 | struct percpu_lock_entry { | |
17 | intptr_t v; | |
18 | } __attribute__((aligned(128))); | |
19 | ||
20 | struct percpu_lock { | |
21 | struct percpu_lock_entry c[CPU_SETSIZE]; | |
22 | }; | |
23 | ||
24 | struct test_data_entry { | |
25 | intptr_t count; | |
26 | } __attribute__((aligned(128))); | |
27 | ||
28 | struct spinlock_test_data { | |
29 | struct percpu_lock lock; | |
30 | struct test_data_entry c[CPU_SETSIZE]; | |
31 | int reps; | |
32 | }; | |
33 | ||
34 | struct percpu_list_node { | |
35 | intptr_t data; | |
36 | struct percpu_list_node *next; | |
37 | }; | |
38 | ||
39 | struct percpu_list_entry { | |
40 | struct percpu_list_node *head; | |
41 | } __attribute__((aligned(128))); | |
42 | ||
43 | struct percpu_list { | |
44 | struct percpu_list_entry c[CPU_SETSIZE]; | |
45 | }; | |
46 | ||
0cfe92f9 MD |
47 | /* A simple percpu spinlock. */ |
48 | void rseq_percpu_lock(struct percpu_lock *lock, int cpu) | |
dd6b880e | 49 | { |
dd6b880e MD |
50 | for (;;) { |
51 | int ret; | |
52 | ||
dd6b880e MD |
53 | ret = percpu_cmpeqv_storev(&lock->c[cpu].v, |
54 | 0, 1, cpu); | |
55 | if (rseq_likely(!ret)) | |
56 | break; | |
57 | if (rseq_unlikely(ret < 0)) { | |
58 | perror("cpu_opv"); | |
59 | abort(); | |
60 | } | |
61 | /* Retry if comparison fails. */ | |
62 | } | |
63 | /* | |
64 | * Acquire semantic when taking lock after control dependency. | |
65 | * Matches rseq_smp_store_release(). | |
66 | */ | |
67 | rseq_smp_acquire__after_ctrl_dep(); | |
dd6b880e MD |
68 | } |
69 | ||
70 | void rseq_percpu_unlock(struct percpu_lock *lock, int cpu) | |
71 | { | |
72 | assert(lock->c[cpu].v == 1); | |
73 | /* | |
74 | * Release lock, with release semantic. Matches | |
75 | * rseq_smp_acquire__after_ctrl_dep(). | |
76 | */ | |
77 | rseq_smp_store_release(&lock->c[cpu].v, 0); | |
78 | } | |
79 | ||
80 | void *test_percpu_spinlock_thread(void *arg) | |
81 | { | |
82 | struct spinlock_test_data *data = arg; | |
0cfe92f9 | 83 | int i; |
dd6b880e MD |
84 | |
85 | if (rseq_register_current_thread()) { | |
86 | fprintf(stderr, "Error: rseq_register_current_thread(...) failed(%d): %s\n", | |
87 | errno, strerror(errno)); | |
88 | abort(); | |
89 | } | |
90 | for (i = 0; i < data->reps; i++) { | |
0cfe92f9 MD |
91 | int cpu = percpu_current_cpu(); |
92 | ||
93 | rseq_percpu_lock(&data->lock, cpu); | |
dd6b880e MD |
94 | data->c[cpu].count++; |
95 | rseq_percpu_unlock(&data->lock, cpu); | |
96 | } | |
97 | if (rseq_unregister_current_thread()) { | |
98 | fprintf(stderr, "Error: rseq_unregister_current_thread(...) failed(%d): %s\n", | |
99 | errno, strerror(errno)); | |
100 | abort(); | |
101 | } | |
102 | ||
103 | return NULL; | |
104 | } | |
105 | ||
106 | /* | |
107 | * A simple test which implements a sharded counter using a per-cpu | |
108 | * lock. Obviously real applications might prefer to simply use a | |
109 | * per-cpu increment; however, this is reasonable for a test and the | |
110 | * lock can be extended to synchronize more complicated operations. | |
111 | */ | |
112 | void test_percpu_spinlock(void) | |
113 | { | |
114 | const int num_threads = 200; | |
115 | int i; | |
116 | uint64_t sum; | |
117 | pthread_t test_threads[num_threads]; | |
118 | struct spinlock_test_data data; | |
119 | ||
120 | memset(&data, 0, sizeof(data)); | |
121 | data.reps = 5000; | |
122 | ||
123 | for (i = 0; i < num_threads; i++) | |
124 | pthread_create(&test_threads[i], NULL, | |
125 | test_percpu_spinlock_thread, &data); | |
126 | ||
127 | for (i = 0; i < num_threads; i++) | |
128 | pthread_join(test_threads[i], NULL); | |
129 | ||
130 | sum = 0; | |
131 | for (i = 0; i < CPU_SETSIZE; i++) | |
132 | sum += data.c[i].count; | |
133 | ||
134 | assert(sum == (uint64_t)data.reps * num_threads); | |
135 | } | |
136 | ||
137 | int percpu_list_push(struct percpu_list *list, struct percpu_list_node *node, | |
138 | int cpu) | |
139 | { | |
140 | for (;;) { | |
141 | intptr_t *targetptr, newval, expect; | |
142 | int ret; | |
143 | ||
144 | /* Load list->c[cpu].head with single-copy atomicity. */ | |
145 | expect = (intptr_t)RSEQ_READ_ONCE(list->c[cpu].head); | |
146 | newval = (intptr_t)node; | |
147 | targetptr = (intptr_t *)&list->c[cpu].head; | |
148 | node->next = (struct percpu_list_node *)expect; | |
149 | ret = percpu_cmpeqv_storev(targetptr, expect, newval, cpu); | |
150 | if (rseq_likely(!ret)) | |
151 | break; | |
152 | if (rseq_unlikely(ret < 0)) { | |
153 | perror("cpu_opv"); | |
154 | abort(); | |
155 | } | |
156 | /* Retry if comparison fails. */ | |
157 | } | |
158 | return cpu; | |
159 | } | |
160 | ||
161 | /* | |
162 | * Unlike a traditional lock-less linked list; the availability of a | |
163 | * rseq primitive allows us to implement pop without concerns over | |
164 | * ABA-type races. | |
165 | */ | |
166 | struct percpu_list_node *percpu_list_pop(struct percpu_list *list, | |
167 | int cpu) | |
168 | { | |
169 | struct percpu_list_node *head; | |
170 | intptr_t *targetptr, expectnot, *load; | |
171 | off_t offset; | |
172 | int ret; | |
173 | ||
174 | targetptr = (intptr_t *)&list->c[cpu].head; | |
175 | expectnot = (intptr_t)NULL; | |
176 | offset = offsetof(struct percpu_list_node, next); | |
177 | load = (intptr_t *)&head; | |
178 | ret = percpu_cmpnev_storeoffp_load(targetptr, expectnot, | |
179 | offset, load, cpu); | |
180 | if (rseq_unlikely(ret < 0)) { | |
181 | perror("cpu_opv"); | |
182 | abort(); | |
183 | } | |
184 | if (ret > 0) | |
185 | return NULL; | |
186 | return head; | |
187 | } | |
188 | ||
189 | void *test_percpu_list_thread(void *arg) | |
190 | { | |
191 | int i; | |
192 | struct percpu_list *list = (struct percpu_list *)arg; | |
193 | ||
194 | if (rseq_register_current_thread()) { | |
195 | fprintf(stderr, "Error: rseq_register_current_thread(...) failed(%d): %s\n", | |
196 | errno, strerror(errno)); | |
197 | abort(); | |
198 | } | |
199 | ||
200 | for (i = 0; i < 100000; i++) { | |
201 | struct percpu_list_node *node; | |
202 | ||
0cfe92f9 | 203 | node = percpu_list_pop(list, percpu_current_cpu()); |
dd6b880e MD |
204 | sched_yield(); /* encourage shuffling */ |
205 | if (node) | |
0cfe92f9 | 206 | percpu_list_push(list, node, percpu_current_cpu()); |
dd6b880e MD |
207 | } |
208 | ||
209 | if (rseq_unregister_current_thread()) { | |
210 | fprintf(stderr, "Error: rseq_unregister_current_thread(...) failed(%d): %s\n", | |
211 | errno, strerror(errno)); | |
212 | abort(); | |
213 | } | |
214 | ||
215 | return NULL; | |
216 | } | |
217 | ||
218 | /* Simultaneous modification to a per-cpu linked list from many threads. */ | |
219 | void test_percpu_list(void) | |
220 | { | |
221 | int i, j; | |
222 | uint64_t sum = 0, expected_sum = 0; | |
223 | struct percpu_list list; | |
224 | pthread_t test_threads[200]; | |
225 | cpu_set_t allowed_cpus; | |
226 | ||
227 | memset(&list, 0, sizeof(list)); | |
228 | ||
229 | /* Generate list entries for every usable cpu. */ | |
230 | sched_getaffinity(0, sizeof(allowed_cpus), &allowed_cpus); | |
231 | for (i = 0; i < CPU_SETSIZE; i++) { | |
232 | if (!CPU_ISSET(i, &allowed_cpus)) | |
233 | continue; | |
234 | for (j = 1; j <= 100; j++) { | |
235 | struct percpu_list_node *node; | |
236 | ||
237 | expected_sum += j; | |
238 | ||
239 | node = malloc(sizeof(*node)); | |
240 | assert(node); | |
241 | node->data = j; | |
242 | node->next = list.c[i].head; | |
243 | list.c[i].head = node; | |
244 | } | |
245 | } | |
246 | ||
247 | for (i = 0; i < 200; i++) | |
248 | pthread_create(&test_threads[i], NULL, | |
249 | test_percpu_list_thread, &list); | |
250 | ||
251 | for (i = 0; i < 200; i++) | |
252 | pthread_join(test_threads[i], NULL); | |
253 | ||
254 | for (i = 0; i < CPU_SETSIZE; i++) { | |
255 | struct percpu_list_node *node; | |
256 | ||
257 | if (!CPU_ISSET(i, &allowed_cpus)) | |
258 | continue; | |
259 | ||
260 | while ((node = percpu_list_pop(&list, i))) { | |
261 | sum += node->data; | |
262 | free(node); | |
263 | } | |
264 | } | |
265 | ||
266 | /* | |
267 | * All entries should now be accounted for (unless some external | |
268 | * actor is interfering with our allowed affinity while this | |
269 | * test is running). | |
270 | */ | |
271 | assert(sum == expected_sum); | |
272 | } | |
273 | ||
274 | int main(int argc, char **argv) | |
275 | { | |
276 | if (rseq_register_current_thread()) { | |
277 | fprintf(stderr, "Error: rseq_register_current_thread(...) failed(%d): %s\n", | |
278 | errno, strerror(errno)); | |
279 | goto error; | |
280 | } | |
281 | printf("spinlock\n"); | |
282 | test_percpu_spinlock(); | |
283 | printf("percpu_list\n"); | |
284 | test_percpu_list(); | |
285 | if (rseq_unregister_current_thread()) { | |
286 | fprintf(stderr, "Error: rseq_unregister_current_thread(...) failed(%d): %s\n", | |
287 | errno, strerror(errno)); | |
288 | goto error; | |
289 | } | |
290 | return 0; | |
291 | ||
292 | error: | |
293 | return -1; | |
294 | } | |
295 |