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