tests/basic_percpu_ops_test.c

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