tests/basic_percpu_ops_test.c

   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
  47 /* A simple percpu spinlock. */
  48 void rseq_percpu_lock(struct percpu_lock *lock, int cpu)
  49 {
  50         for (;;) {
  51                 int ret;
  52
  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();
  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;
  83         int i;
  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++) {
  91                 int cpu = percpu_current_cpu();
  92
  93                 rseq_percpu_lock(&data->lock, cpu);
  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
 203                 node = percpu_list_pop(list, percpu_current_cpu());
 204                 sched_yield();  /* encourage shuffling */
 205                 if (node)
 206                         percpu_list_push(list, node, percpu_current_cpu());
 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