selftests/rseq/basic_percpu_ops_test.c

0001 // SPDX-License-Identifier: LGPL-2.1
0002 #define _GNU_SOURCE
0003 #include <assert.h>
0004 #include <pthread.h>
0005 #include <sched.h>
0006 #include <stdint.h>
0007 #include <stdio.h>
0008 #include <stdlib.h>
0009 #include <string.h>
0010 #include <stddef.h>
0011
0012 #include "../kselftest.h"
0013 #include "rseq.h"
0014
0015 struct percpu_lock_entry {
0016     intptr_t v;
0017 } __attribute__((aligned(128)));
0018
0019 struct percpu_lock {
0020     struct percpu_lock_entry c[CPU_SETSIZE];
0021 };
0022
0023 struct test_data_entry {
0024     intptr_t count;
0025 } __attribute__((aligned(128)));
0026
0027 struct spinlock_test_data {
0028     struct percpu_lock lock;
0029     struct test_data_entry c[CPU_SETSIZE];
0030     int reps;
0031 };
0032
0033 struct percpu_list_node {
0034     intptr_t data;
0035     struct percpu_list_node *next;
0036 };
0037
0038 struct percpu_list_entry {
0039     struct percpu_list_node *head;
0040 } __attribute__((aligned(128)));
0041
0042 struct percpu_list {
0043     struct percpu_list_entry c[CPU_SETSIZE];
0044 };
0045
0046 /* A simple percpu spinlock.  Returns the cpu lock was acquired on. */
0047 int rseq_this_cpu_lock(struct percpu_lock *lock)
0048 {
0049     int cpu;
0050
0051     for (;;) {
0052         int ret;
0053
0054         cpu = rseq_cpu_start();
0055         ret = rseq_cmpeqv_storev(&lock->c[cpu].v,
0056                      0, 1, cpu);
0057         if (rseq_likely(!ret))
0058             break;
0059         /* Retry if comparison fails or rseq aborts. */
0060     }
0061     /*
0062      * Acquire semantic when taking lock after control dependency.
0063      * Matches rseq_smp_store_release().
0064      */
0065     rseq_smp_acquire__after_ctrl_dep();
0066     return cpu;
0067 }
0068
0069 void rseq_percpu_unlock(struct percpu_lock *lock, int cpu)
0070 {
0071     assert(lock->c[cpu].v == 1);
0072     /*
0073      * Release lock, with release semantic. Matches
0074      * rseq_smp_acquire__after_ctrl_dep().
0075      */
0076     rseq_smp_store_release(&lock->c[cpu].v, 0);
0077 }
0078
0079 void *test_percpu_spinlock_thread(void *arg)
0080 {
0081     struct spinlock_test_data *data = arg;
0082     int i, cpu;
0083
0084     if (rseq_register_current_thread()) {
0085         fprintf(stderr, "Error: rseq_register_current_thread(...) failed(%d): %s\n",
0086             errno, strerror(errno));
0087         abort();
0088     }
0089     for (i = 0; i < data->reps; i++) {
0090         cpu = rseq_this_cpu_lock(&data->lock);
0091         data->c[cpu].count++;
0092         rseq_percpu_unlock(&data->lock, cpu);
0093     }
0094     if (rseq_unregister_current_thread()) {
0095         fprintf(stderr, "Error: rseq_unregister_current_thread(...) failed(%d): %s\n",
0096             errno, strerror(errno));
0097         abort();
0098     }
0099
0100     return NULL;
0101 }
0102
0103 /*
0104  * A simple test which implements a sharded counter using a per-cpu
0105  * lock.  Obviously real applications might prefer to simply use a
0106  * per-cpu increment; however, this is reasonable for a test and the
0107  * lock can be extended to synchronize more complicated operations.
0108  */
0109 void test_percpu_spinlock(void)
0110 {
0111     const int num_threads = 200;
0112     int i;
0113     uint64_t sum;
0114     pthread_t test_threads[num_threads];
0115     struct spinlock_test_data data;
0116
0117     memset(&data, 0, sizeof(data));
0118     data.reps = 5000;
0119
0120     for (i = 0; i < num_threads; i++)
0121         pthread_create(&test_threads[i], NULL,
0122                    test_percpu_spinlock_thread, &data);
0123
0124     for (i = 0; i < num_threads; i++)
0125         pthread_join(test_threads[i], NULL);
0126
0127     sum = 0;
0128     for (i = 0; i < CPU_SETSIZE; i++)
0129         sum += data.c[i].count;
0130
0131     assert(sum == (uint64_t)data.reps * num_threads);
0132 }
0133
0134 void this_cpu_list_push(struct percpu_list *list,
0135             struct percpu_list_node *node,
0136             int *_cpu)
0137 {
0138     int cpu;
0139
0140     for (;;) {
0141         intptr_t *targetptr, newval, expect;
0142         int ret;
0143
0144         cpu = rseq_cpu_start();
0145         /* Load list->c[cpu].head with single-copy atomicity. */
0146         expect = (intptr_t)RSEQ_READ_ONCE(list->c[cpu].head);
0147         newval = (intptr_t)node;
0148         targetptr = (intptr_t *)&list->c[cpu].head;
0149         node->next = (struct percpu_list_node *)expect;
0150         ret = rseq_cmpeqv_storev(targetptr, expect, newval, cpu);
0151         if (rseq_likely(!ret))
0152             break;
0153         /* Retry if comparison fails or rseq aborts. */
0154     }
0155     if (_cpu)
0156         *_cpu = cpu;
0157 }
0158
0159 /*
0160  * Unlike a traditional lock-less linked list; the availability of a
0161  * rseq primitive allows us to implement pop without concerns over
0162  * ABA-type races.
0163  */
0164 struct percpu_list_node *this_cpu_list_pop(struct percpu_list *list,
0165                        int *_cpu)
0166 {
0167     for (;;) {
0168         struct percpu_list_node *head;
0169         intptr_t *targetptr, expectnot, *load;
0170         long offset;
0171         int ret, cpu;
0172
0173         cpu = rseq_cpu_start();
0174         targetptr = (intptr_t *)&list->c[cpu].head;
0175         expectnot = (intptr_t)NULL;
0176         offset = offsetof(struct percpu_list_node, next);
0177         load = (intptr_t *)&head;
0178         ret = rseq_cmpnev_storeoffp_load(targetptr, expectnot,
0179                          offset, load, cpu);
0180         if (rseq_likely(!ret)) {
0181             if (_cpu)
0182                 *_cpu = cpu;
0183             return head;
0184         }
0185         if (ret > 0)
0186             return NULL;
0187         /* Retry if rseq aborts. */
0188     }
0189 }
0190
0191 /*
0192  * __percpu_list_pop is not safe against concurrent accesses. Should
0193  * only be used on lists that are not concurrently modified.
0194  */
0195 struct percpu_list_node *__percpu_list_pop(struct percpu_list *list, int cpu)
0196 {
0197     struct percpu_list_node *node;
0198
0199     node = list->c[cpu].head;
0200     if (!node)
0201         return NULL;
0202     list->c[cpu].head = node->next;
0203     return node;
0204 }
0205
0206 void *test_percpu_list_thread(void *arg)
0207 {
0208     int i;
0209     struct percpu_list *list = (struct percpu_list *)arg;
0210
0211     if (rseq_register_current_thread()) {
0212         fprintf(stderr, "Error: rseq_register_current_thread(...) failed(%d): %s\n",
0213             errno, strerror(errno));
0214         abort();
0215     }
0216
0217     for (i = 0; i < 100000; i++) {
0218         struct percpu_list_node *node;
0219
0220         node = this_cpu_list_pop(list, NULL);
0221         sched_yield();  /* encourage shuffling */
0222         if (node)
0223             this_cpu_list_push(list, node, NULL);
0224     }
0225
0226     if (rseq_unregister_current_thread()) {
0227         fprintf(stderr, "Error: rseq_unregister_current_thread(...) failed(%d): %s\n",
0228             errno, strerror(errno));
0229         abort();
0230     }
0231
0232     return NULL;
0233 }
0234
0235 /* Simultaneous modification to a per-cpu linked list from many threads.  */
0236 void test_percpu_list(void)
0237 {
0238     int i, j;
0239     uint64_t sum = 0, expected_sum = 0;
0240     struct percpu_list list;
0241     pthread_t test_threads[200];
0242     cpu_set_t allowed_cpus;
0243
0244     memset(&list, 0, sizeof(list));
0245
0246     /* Generate list entries for every usable cpu. */
0247     sched_getaffinity(0, sizeof(allowed_cpus), &allowed_cpus);
0248     for (i = 0; i < CPU_SETSIZE; i++) {
0249         if (!CPU_ISSET(i, &allowed_cpus))
0250             continue;
0251         for (j = 1; j <= 100; j++) {
0252             struct percpu_list_node *node;
0253
0254             expected_sum += j;
0255
0256             node = malloc(sizeof(*node));
0257             assert(node);
0258             node->data = j;
0259             node->next = list.c[i].head;
0260             list.c[i].head = node;
0261         }
0262     }
0263
0264     for (i = 0; i < 200; i++)
0265         pthread_create(&test_threads[i], NULL,
0266                test_percpu_list_thread, &list);
0267
0268     for (i = 0; i < 200; i++)
0269         pthread_join(test_threads[i], NULL);
0270
0271     for (i = 0; i < CPU_SETSIZE; i++) {
0272         struct percpu_list_node *node;
0273
0274         if (!CPU_ISSET(i, &allowed_cpus))
0275             continue;
0276
0277         while ((node = __percpu_list_pop(&list, i))) {
0278             sum += node->data;
0279             free(node);
0280         }
0281     }
0282
0283     /*
0284      * All entries should now be accounted for (unless some external
0285      * actor is interfering with our allowed affinity while this
0286      * test is running).
0287      */
0288     assert(sum == expected_sum);
0289 }
0290
0291 int main(int argc, char **argv)
0292 {
0293     if (rseq_register_current_thread()) {
0294         fprintf(stderr, "Error: rseq_register_current_thread(...) failed(%d): %s\n",
0295             errno, strerror(errno));
0296         goto error;
0297     }
0298     printf("spinlock\n");
0299     test_percpu_spinlock();
0300     printf("percpu_list\n");
0301     test_percpu_list();
0302     if (rseq_unregister_current_thread()) {
0303         fprintf(stderr, "Error: rseq_unregister_current_thread(...) failed(%d): %s\n",
0304             errno, strerror(errno));
0305         goto error;
0306     }
0307     return 0;
0308
0309 error:
0310     return -1;
0311 }