| 1 | // SPDX-License-Identifier: MIT |
| 2 | // SPDX-FileCopyrightText: 2018-2022 Mathieu Desnoyers <mathieu.desnoyers@efficios.com> |
| 3 | #ifndef _GNU_SOURCE |
| 4 | #define _GNU_SOURCE |
| 5 | #endif |
| 6 | #include <assert.h> |
| 7 | #include <pthread.h> |
| 8 | #include <sched.h> |
| 9 | #include <stdint.h> |
| 10 | #include <inttypes.h> |
| 11 | #include <stdio.h> |
| 12 | #include <stdlib.h> |
| 13 | #include <string.h> |
| 14 | #include <stddef.h> |
| 15 | |
| 16 | #include <rseq/rseq.h> |
| 17 | |
| 18 | #include "tap.h" |
| 19 | |
| 20 | #define NR_TESTS 4 |
| 21 | |
| 22 | #define ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[0])) |
| 23 | |
| 24 | #ifdef BUILDOPT_RSEQ_PERCPU_MM_CID |
| 25 | # define RSEQ_PERCPU RSEQ_PERCPU_MM_CID |
| 26 | static |
| 27 | int get_current_cpu_id(void) |
| 28 | { |
| 29 | return rseq_current_mm_cid(); |
| 30 | } |
| 31 | static |
| 32 | bool rseq_validate_cpu_id(void) |
| 33 | { |
| 34 | return rseq_mm_cid_available(); |
| 35 | } |
| 36 | static |
| 37 | bool rseq_use_cpu_index(void) |
| 38 | { |
| 39 | return false; /* Use mm_cid */ |
| 40 | } |
| 41 | #else |
| 42 | # define RSEQ_PERCPU RSEQ_PERCPU_CPU_ID |
| 43 | static |
| 44 | int get_current_cpu_id(void) |
| 45 | { |
| 46 | return rseq_cpu_start(); |
| 47 | } |
| 48 | static |
| 49 | bool rseq_validate_cpu_id(void) |
| 50 | { |
| 51 | return rseq_current_cpu_raw() >= 0; |
| 52 | } |
| 53 | static |
| 54 | bool rseq_use_cpu_index(void) |
| 55 | { |
| 56 | return true; /* Use cpu_id as index. */ |
| 57 | } |
| 58 | #endif |
| 59 | |
| 60 | struct percpu_lock_entry { |
| 61 | intptr_t v; |
| 62 | } __attribute__((aligned(128))); |
| 63 | |
| 64 | struct percpu_lock { |
| 65 | struct percpu_lock_entry c[CPU_SETSIZE]; |
| 66 | }; |
| 67 | |
| 68 | struct test_data_entry { |
| 69 | intptr_t count; |
| 70 | } __attribute__((aligned(128))); |
| 71 | |
| 72 | struct spinlock_test_data { |
| 73 | struct percpu_lock lock; |
| 74 | struct test_data_entry c[CPU_SETSIZE]; |
| 75 | int reps; |
| 76 | }; |
| 77 | |
| 78 | struct percpu_list_node { |
| 79 | intptr_t data; |
| 80 | struct percpu_list_node *next; |
| 81 | }; |
| 82 | |
| 83 | struct percpu_list_entry { |
| 84 | struct percpu_list_node *head; |
| 85 | } __attribute__((aligned(128))); |
| 86 | |
| 87 | struct percpu_list { |
| 88 | struct percpu_list_entry c[CPU_SETSIZE]; |
| 89 | }; |
| 90 | |
| 91 | /* A simple percpu spinlock. Returns the cpu lock was acquired on. */ |
| 92 | static int rseq_this_cpu_lock(struct percpu_lock *lock) |
| 93 | { |
| 94 | int cpu; |
| 95 | |
| 96 | for (;;) { |
| 97 | int ret; |
| 98 | |
| 99 | cpu = get_current_cpu_id(); |
| 100 | ret = rseq_load_cbne_store__ptr(RSEQ_MO_RELAXED, RSEQ_PERCPU, |
| 101 | &lock->c[cpu].v, 0, 1, cpu); |
| 102 | if (rseq_likely(!ret)) |
| 103 | break; |
| 104 | /* Retry if comparison fails or rseq aborts. */ |
| 105 | } |
| 106 | /* |
| 107 | * Acquire semantic when taking lock after control dependency. |
| 108 | * Matches rseq_smp_store_release(). |
| 109 | */ |
| 110 | rseq_smp_acquire__after_ctrl_dep(); |
| 111 | return cpu; |
| 112 | } |
| 113 | |
| 114 | static void rseq_percpu_unlock(struct percpu_lock *lock, int cpu) |
| 115 | { |
| 116 | assert(lock->c[cpu].v == 1); |
| 117 | /* |
| 118 | * Release lock, with release semantic. Matches |
| 119 | * rseq_smp_acquire__after_ctrl_dep(). |
| 120 | */ |
| 121 | rseq_smp_store_release(&lock->c[cpu].v, 0); |
| 122 | } |
| 123 | |
| 124 | static void *test_percpu_spinlock_thread(void *arg) |
| 125 | { |
| 126 | struct spinlock_test_data *data = (struct spinlock_test_data *) arg; |
| 127 | int i, cpu; |
| 128 | |
| 129 | if (rseq_register_current_thread()) { |
| 130 | fprintf(stderr, "Error: rseq_register_current_thread(...) failed(%d): %s\n", |
| 131 | errno, strerror(errno)); |
| 132 | abort(); |
| 133 | } |
| 134 | for (i = 0; i < data->reps; i++) { |
| 135 | cpu = rseq_this_cpu_lock(&data->lock); |
| 136 | data->c[cpu].count++; |
| 137 | rseq_percpu_unlock(&data->lock, cpu); |
| 138 | } |
| 139 | if (rseq_unregister_current_thread()) { |
| 140 | fprintf(stderr, "Error: rseq_unregister_current_thread(...) failed(%d): %s\n", |
| 141 | errno, strerror(errno)); |
| 142 | abort(); |
| 143 | } |
| 144 | |
| 145 | return NULL; |
| 146 | } |
| 147 | |
| 148 | /* |
| 149 | * A simple test which implements a sharded counter using a per-cpu |
| 150 | * lock. Obviously real applications might prefer to simply use a |
| 151 | * per-cpu increment; however, this is reasonable for a test and the |
| 152 | * lock can be extended to synchronize more complicated operations. |
| 153 | */ |
| 154 | static void test_percpu_spinlock(void) |
| 155 | { |
| 156 | const int num_threads = 200; |
| 157 | int i; |
| 158 | uint64_t sum, expected_sum; |
| 159 | pthread_t test_threads[num_threads]; |
| 160 | struct spinlock_test_data data; |
| 161 | |
| 162 | diag("spinlock"); |
| 163 | |
| 164 | memset(&data, 0, sizeof(data)); |
| 165 | data.reps = 5000; |
| 166 | |
| 167 | for (i = 0; i < num_threads; i++) |
| 168 | pthread_create(&test_threads[i], NULL, |
| 169 | test_percpu_spinlock_thread, &data); |
| 170 | |
| 171 | for (i = 0; i < num_threads; i++) |
| 172 | pthread_join(test_threads[i], NULL); |
| 173 | |
| 174 | sum = 0; |
| 175 | for (i = 0; i < CPU_SETSIZE; i++) |
| 176 | sum += data.c[i].count; |
| 177 | |
| 178 | expected_sum = (uint64_t)data.reps * num_threads; |
| 179 | |
| 180 | ok(sum == expected_sum, "spinlock - sum (%" PRIu64 " == %" PRIu64 ")", sum, expected_sum); |
| 181 | } |
| 182 | |
| 183 | static void this_cpu_list_push(struct percpu_list *list, |
| 184 | struct percpu_list_node *node, |
| 185 | int *_cpu) |
| 186 | { |
| 187 | int cpu; |
| 188 | |
| 189 | for (;;) { |
| 190 | intptr_t *targetptr, newval, expect; |
| 191 | int ret; |
| 192 | |
| 193 | cpu = get_current_cpu_id(); |
| 194 | /* Load list->c[cpu].head with single-copy atomicity. */ |
| 195 | expect = (intptr_t)RSEQ_READ_ONCE(list->c[cpu].head); |
| 196 | newval = (intptr_t)node; |
| 197 | targetptr = (intptr_t *)&list->c[cpu].head; |
| 198 | node->next = (struct percpu_list_node *)expect; |
| 199 | ret = rseq_load_cbne_store__ptr(RSEQ_MO_RELAXED, RSEQ_PERCPU, |
| 200 | targetptr, expect, newval, cpu); |
| 201 | if (rseq_likely(!ret)) |
| 202 | break; |
| 203 | /* Retry if comparison fails or rseq aborts. */ |
| 204 | } |
| 205 | if (_cpu) |
| 206 | *_cpu = cpu; |
| 207 | } |
| 208 | |
| 209 | /* |
| 210 | * Unlike a traditional lock-less linked list; the availability of a |
| 211 | * rseq primitive allows us to implement pop without concerns over |
| 212 | * ABA-type races. |
| 213 | */ |
| 214 | static struct percpu_list_node *this_cpu_list_pop(struct percpu_list *list, |
| 215 | int *_cpu) |
| 216 | { |
| 217 | for (;;) { |
| 218 | struct percpu_list_node *head; |
| 219 | intptr_t *targetptr, expectnot, *load; |
| 220 | long offset; |
| 221 | int ret, cpu; |
| 222 | |
| 223 | cpu = get_current_cpu_id(); |
| 224 | targetptr = (intptr_t *)&list->c[cpu].head; |
| 225 | expectnot = (intptr_t)NULL; |
| 226 | offset = offsetof(struct percpu_list_node, next); |
| 227 | load = (intptr_t *)&head; |
| 228 | ret = rseq_load_cbeq_store_add_load_store__ptr(RSEQ_MO_RELAXED, RSEQ_PERCPU, |
| 229 | targetptr, expectnot, |
| 230 | offset, load, cpu); |
| 231 | if (rseq_likely(!ret)) { |
| 232 | if (_cpu) |
| 233 | *_cpu = cpu; |
| 234 | return head; |
| 235 | } |
| 236 | if (ret > 0) |
| 237 | return NULL; |
| 238 | /* Retry if rseq aborts. */ |
| 239 | } |
| 240 | } |
| 241 | |
| 242 | /* |
| 243 | * __percpu_list_pop is not safe against concurrent accesses. Should |
| 244 | * only be used on lists that are not concurrently modified. |
| 245 | */ |
| 246 | static struct percpu_list_node *__percpu_list_pop(struct percpu_list *list, int cpu) |
| 247 | { |
| 248 | struct percpu_list_node *node; |
| 249 | |
| 250 | node = list->c[cpu].head; |
| 251 | if (!node) |
| 252 | return NULL; |
| 253 | list->c[cpu].head = node->next; |
| 254 | return node; |
| 255 | } |
| 256 | |
| 257 | static void *test_percpu_list_thread(void *arg) |
| 258 | { |
| 259 | int i; |
| 260 | struct percpu_list *list = (struct percpu_list *)arg; |
| 261 | |
| 262 | if (rseq_register_current_thread()) { |
| 263 | fprintf(stderr, "Error: rseq_register_current_thread(...) failed(%d): %s\n", |
| 264 | errno, strerror(errno)); |
| 265 | abort(); |
| 266 | } |
| 267 | |
| 268 | for (i = 0; i < 100000; i++) { |
| 269 | struct percpu_list_node *node; |
| 270 | |
| 271 | node = this_cpu_list_pop(list, NULL); |
| 272 | sched_yield(); /* encourage shuffling */ |
| 273 | if (node) |
| 274 | this_cpu_list_push(list, node, NULL); |
| 275 | } |
| 276 | |
| 277 | if (rseq_unregister_current_thread()) { |
| 278 | fprintf(stderr, "Error: rseq_unregister_current_thread(...) failed(%d): %s\n", |
| 279 | errno, strerror(errno)); |
| 280 | abort(); |
| 281 | } |
| 282 | |
| 283 | return NULL; |
| 284 | } |
| 285 | |
| 286 | /* Simultaneous modification to a per-cpu linked list from many threads. */ |
| 287 | static void test_percpu_list(void) |
| 288 | { |
| 289 | int i, j; |
| 290 | uint64_t sum = 0, expected_sum = 0; |
| 291 | struct percpu_list list; |
| 292 | pthread_t test_threads[200]; |
| 293 | cpu_set_t allowed_cpus; |
| 294 | |
| 295 | diag("percpu_list"); |
| 296 | |
| 297 | memset(&list, 0, sizeof(list)); |
| 298 | |
| 299 | /* Generate list entries for every usable cpu. */ |
| 300 | sched_getaffinity(0, sizeof(allowed_cpus), &allowed_cpus); |
| 301 | for (i = 0; i < CPU_SETSIZE; i++) { |
| 302 | if (rseq_use_cpu_index() && !CPU_ISSET(i, &allowed_cpus)) |
| 303 | continue; |
| 304 | for (j = 1; j <= 100; j++) { |
| 305 | struct percpu_list_node *node; |
| 306 | |
| 307 | expected_sum += j; |
| 308 | |
| 309 | node = (struct percpu_list_node *) malloc(sizeof(*node)); |
| 310 | assert(node); |
| 311 | node->data = j; |
| 312 | node->next = list.c[i].head; |
| 313 | list.c[i].head = node; |
| 314 | } |
| 315 | } |
| 316 | |
| 317 | for (i = 0; i < 200; i++) |
| 318 | pthread_create(&test_threads[i], NULL, |
| 319 | test_percpu_list_thread, &list); |
| 320 | |
| 321 | for (i = 0; i < 200; i++) |
| 322 | pthread_join(test_threads[i], NULL); |
| 323 | |
| 324 | for (i = 0; i < CPU_SETSIZE; i++) { |
| 325 | struct percpu_list_node *node; |
| 326 | |
| 327 | if (rseq_use_cpu_index() && !CPU_ISSET(i, &allowed_cpus)) |
| 328 | continue; |
| 329 | |
| 330 | while ((node = __percpu_list_pop(&list, i))) { |
| 331 | sum += node->data; |
| 332 | free(node); |
| 333 | } |
| 334 | } |
| 335 | |
| 336 | /* |
| 337 | * All entries should now be accounted for (unless some external |
| 338 | * actor is interfering with our allowed affinity while this |
| 339 | * test is running). |
| 340 | */ |
| 341 | ok(sum == expected_sum, "percpu_list - sum (%" PRIu64 " == %" PRIu64 ")", sum, expected_sum); |
| 342 | } |
| 343 | |
| 344 | int main(void) |
| 345 | { |
| 346 | plan_tests(NR_TESTS); |
| 347 | |
| 348 | if (!rseq_available(RSEQ_AVAILABLE_QUERY_KERNEL)) { |
| 349 | skip(NR_TESTS, "The rseq syscall is unavailable"); |
| 350 | goto end; |
| 351 | } |
| 352 | |
| 353 | if (rseq_register_current_thread()) { |
| 354 | fail("rseq_register_current_thread(...) failed(%d): %s\n", |
| 355 | errno, strerror(errno)); |
| 356 | goto end; |
| 357 | } else { |
| 358 | pass("Registered current thread with rseq"); |
| 359 | } |
| 360 | if (!rseq_validate_cpu_id()) { |
| 361 | skip(NR_TESTS - 1, "Error: cpu id getter unavailable"); |
| 362 | goto end; |
| 363 | } |
| 364 | test_percpu_spinlock(); |
| 365 | test_percpu_list(); |
| 366 | |
| 367 | if (rseq_unregister_current_thread()) { |
| 368 | fail("rseq_unregister_current_thread(...) failed(%d): %s\n", |
| 369 | errno, strerror(errno)); |
| 370 | goto end; |
| 371 | } else { |
| 372 | pass("Unregistered current thread with rseq"); |
| 373 | } |
| 374 | end: |
| 375 | exit(exit_status()); |
| 376 | } |