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