1 /*
2 * Copyright (c) 2016-2018 David Lamparter, for NetDEF, Inc.
3 *
4 * Permission to use, copy, modify, and distribute this software for any
5 * purpose with or without fee is hereby granted, provided that the above
6 * copyright notice and this permission notice appear in all copies.
7 *
8 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
9 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
10 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
11 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
12 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
13 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
14 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
15 */
16
17 #ifdef HAVE_CONFIG_H
18 #include "config.h"
19 #endif
20
21 #include <stdio.h>
22 #include <stdint.h>
23 #include <inttypes.h>
24 #include <string.h>
25 #include <unistd.h>
26 #include <assert.h>
27 #include <pthread.h>
28
29 #include "atomlist.h"
30 #include "seqlock.h"
31 #include "monotime.h"
32 #include "printfrr.h"
33
34 /*
35 * maybe test:
36 * - alist_del_hint
37 * - alist_next_safe
38 * - asort_del_hint
39 * - asort_next_safe
40 */
41
42 static struct seqlock sqlo;
43
44 PREDECL_ATOMLIST(alist)
45 PREDECL_ATOMSORT_UNIQ(asort)
46 struct item {
47 uint64_t val1;
48 struct alist_item chain;
49 struct asort_item sortc;
50 uint64_t val2;
51 };
52 DECLARE_ATOMLIST(alist, struct item, chain)
53
54 static int icmp(const struct item *a, const struct item *b);
DECLARE_ATOMSORT_UNIQ(asort,struct item,sortc,icmp)55 DECLARE_ATOMSORT_UNIQ(asort, struct item, sortc, icmp)
56
57 static int icmp(const struct item *a, const struct item *b)
58 {
59 if (a->val1 > b->val1)
60 return 1;
61 if (a->val1 < b->val1)
62 return -1;
63 return 0;
64 }
65
66 #define NITEM 10000
67 struct item itm[NITEM];
68
69 static struct alist_head ahead;
70 static struct asort_head shead;
71
72 #define NTHREADS 4
73 static struct testthread {
74 pthread_t pt;
75 struct seqlock sqlo;
76 size_t counter, nullops;
77 } thr[NTHREADS];
78
79 struct testrun {
80 struct testrun *next;
81 int lineno;
82 const char *desc;
83 ssize_t prefill;
84 bool sorted;
85 void (*func)(unsigned int offset);
86 };
87 struct testrun *runs = NULL;
88
89 #define NOCLEAR -1
90
91 #define deftestrun(name, _desc, _prefill, _sorted) \
92 static void trfunc_##name(unsigned int offset); \
93 struct testrun tr_##name = { \
94 .desc = _desc, \
95 .lineno = __LINE__, \
96 .prefill = _prefill, \
97 .func = &trfunc_##name, \
98 .sorted = _sorted }; \
99 static void __attribute__((constructor)) trsetup_##name(void) \
100 { \
101 struct testrun **inspos = &runs; \
102 while (*inspos && (*inspos)->lineno < tr_##name.lineno) \
103 inspos = &(*inspos)->next; \
104 tr_##name.next = *inspos; \
105 *inspos = &tr_##name; \
106 } \
107 static void trfunc_##name(unsigned int offset) \
108 { \
109 size_t i = 0, n = 0;
110
111 #define endtestrun \
112 thr[offset].counter = i; \
113 thr[offset].nullops = n; \
114 }
115
116 deftestrun(add, "add vs. add", 0, false)
117 for (; i < NITEM / NTHREADS; i++)
118 alist_add_head(&ahead, &itm[i * NTHREADS + offset]);
119 endtestrun
120
121 deftestrun(del, "del vs. del", NOCLEAR, false)
122 for (; i < NITEM / NTHREADS / 10; i++)
123 alist_del(&ahead, &itm[i * NTHREADS + offset]);
124 endtestrun
125
126 deftestrun(addtail, "add_tail vs. add_tail", 0, false)
127 for (; i < NITEM / NTHREADS; i++)
128 alist_add_tail(&ahead, &itm[i * NTHREADS + offset]);
129 endtestrun
130
131 deftestrun(pop, "pop vs. pop", NOCLEAR, false)
132 for (; i < NITEM / NTHREADS; )
133 if (alist_pop(&ahead))
134 i++;
135 else
136 n++;
137 endtestrun
138
139 deftestrun(headN_vs_pop1, "add_head(N) vs. pop(1)", 1, false);
140 if (offset == 0) {
141 struct item *dr = NULL;
142
143 for (i = n = 0; i < NITEM; ) {
144 dr = alist_pop(&ahead);
145 if (dr)
146 i++;
147 else
148 n++;
149 }
150 } else {
151 for (i = offset; i < NITEM; i += NTHREADS)
152 alist_add_head(&ahead, &itm[i]);
153 i = 0;
154 }
155 endtestrun
156
157 deftestrun(head1_vs_popN, "add_head(1) vs. pop(N)", 0, false);
158 if (offset < NTHREADS - 1) {
159 struct item *dr = NULL;
160
161 for (i = n = 0; i < NITEM / NTHREADS; ) {
162 dr = alist_pop(&ahead);
163 if (dr)
164 i++;
165 else
166 n++;
167 }
168 } else {
169 for (i = 0; i < NITEM; i++)
170 alist_add_head(&ahead, &itm[i]);
171 i = 0;
172 }
173 endtestrun
174
175 deftestrun(headN_vs_popN, "add_head(N) vs. pop(N)", NTHREADS / 2, false)
176 if (offset < NTHREADS / 2) {
177 struct item *dr = NULL;
178
179 for (i = n = 0; i < NITEM * 2 / NTHREADS; ) {
180 dr = alist_pop(&ahead);
181 if (dr)
182 i++;
183 else
184 n++;
185 }
186 } else {
187 for (i = offset; i < NITEM; i += NTHREADS)
188 alist_add_head(&ahead, &itm[i]);
189 i = 0;
190 }
191 endtestrun
192
193 deftestrun(tailN_vs_pop1, "add_tail(N) vs. pop(1)", 1, false)
194 if (offset == 0) {
195 struct item *dr = NULL;
196
197 for (i = n = 0; i < NITEM - (NITEM / NTHREADS); ) {
198 dr = alist_pop(&ahead);
199 if (dr)
200 i++;
201 else
202 n++;
203 }
204 } else {
205 for (i = offset; i < NITEM; i += NTHREADS)
206 alist_add_tail(&ahead, &itm[i]);
207 i = 0;
208 }
209 endtestrun
210
211 deftestrun(tail1_vs_popN, "add_tail(1) vs. pop(N)", 0, false)
212 if (offset < NTHREADS - 1) {
213 struct item *dr = NULL;
214
215 for (i = n = 0; i < NITEM / NTHREADS; ) {
216 dr = alist_pop(&ahead);
217 if (dr)
218 i++;
219 else
220 n++;
221 }
222 } else {
223 for (i = 0; i < NITEM; i++)
224 alist_add_tail(&ahead, &itm[i]);
225 i = 0;
226 }
227 endtestrun
228
229 deftestrun(sort_add, "add_sort vs. add_sort", 0, true)
230 for (; i < NITEM / NTHREADS / 10; i++)
231 asort_add(&shead, &itm[i * NTHREADS + offset]);
232 endtestrun
233
234 deftestrun(sort_del, "del_sort vs. del_sort", NOCLEAR, true)
235 for (; i < NITEM / NTHREADS / 10; i++)
236 asort_del(&shead, &itm[i * NTHREADS + offset]);
237 endtestrun
238
239 deftestrun(sort_add_del, "add_sort vs. del_sort", NTHREADS / 2, true)
240 if (offset < NTHREADS / 2) {
241 for (; i < NITEM / NTHREADS / 10; i++)
242 asort_del(&shead, &itm[i * NTHREADS + offset]);
243 } else {
244 for (; i < NITEM / NTHREADS / 10; i++)
245 asort_add(&shead, &itm[i * NTHREADS + offset]);
246 }
247 endtestrun
248
thr1func(void * arg)249 static void *thr1func(void *arg)
250 {
251 struct testthread *p = arg;
252 unsigned int offset = (unsigned int)(p - &thr[0]);
253 seqlock_val_t sv;
254 struct testrun *tr;
255
256 for (tr = runs; tr; tr = tr->next) {
257 sv = seqlock_bump(&p->sqlo) - SEQLOCK_INCR;
258 seqlock_wait(&sqlo, sv);
259
260 tr->func(offset);
261 }
262 seqlock_bump(&p->sqlo);
263
264 return NULL;
265 }
266
clear_list(size_t prefill)267 static void clear_list(size_t prefill)
268 {
269 size_t i;
270
271 memset(&ahead, 0, sizeof(ahead));
272 memset(&shead, 0, sizeof(shead));
273 memset(itm, 0, sizeof(itm));
274 for (i = 0; i < NITEM; i++) {
275 itm[i].val1 = itm[i].val2 = i;
276 if ((i % NTHREADS) < prefill) {
277 alist_add_tail(&ahead, &itm[i]);
278 asort_add(&shead, &itm[i]);
279 }
280 }
281 }
282
run_tr(struct testrun * tr)283 static void run_tr(struct testrun *tr)
284 {
285 const char *desc = tr->desc;
286 struct timeval tv;
287 int64_t delta;
288 seqlock_val_t sv;
289 size_t c = 0, s = 0, n = 0;
290 struct item *item, *prev, dummy;
291
292 printfrr("[%02u] %35s %s\n", seqlock_cur(&sqlo) >> 2, "", desc);
293 fflush(stdout);
294
295 if (tr->prefill != NOCLEAR)
296 clear_list(tr->prefill);
297
298 monotime(&tv);
299 sv = seqlock_bump(&sqlo) - SEQLOCK_INCR;
300 for (size_t i = 0; i < NTHREADS; i++) {
301 seqlock_wait(&thr[i].sqlo, seqlock_cur(&sqlo));
302 s += thr[i].counter;
303 n += thr[i].nullops;
304 thr[i].counter = 0;
305 thr[i].nullops = 0;
306 }
307
308 delta = monotime_since(&tv, NULL);
309 if (tr->sorted) {
310 uint64_t prevval = 0;
311
312 frr_each(asort, &shead, item) {
313 assert(item->val1 >= prevval);
314 prevval = item->val1;
315 c++;
316 }
317 assert(c == asort_count(&shead));
318 } else {
319 prev = &dummy;
320 frr_each(alist, &ahead, item) {
321 assert(item != prev);
322 prev = item;
323 c++;
324 assert(c <= NITEM);
325 }
326 assert(c == alist_count(&ahead));
327 }
328 printfrr("\033[1A[%02u] %9"PRId64"us c=%5zu s=%5zu n=%5zu %s\n",
329 sv >> 2, delta, c, s, n, desc);
330 }
331
332 #ifdef BASIC_TESTS
dump(const char * lbl)333 static void dump(const char *lbl)
334 {
335 struct item *item, *safe;
336 size_t ctr = 0;
337
338 printfrr("dumping %s:\n", lbl);
339 frr_each_safe(alist, &ahead, item) {
340 printfrr("%s %3zu %p %3"PRIu64" %3"PRIu64"\n", lbl, ctr++,
341 (void *)item, item->val1, item->val2);
342 }
343 }
344
basic_tests(void)345 static void basic_tests(void)
346 {
347 size_t i;
348
349 memset(&ahead, 0, sizeof(ahead));
350 memset(itm, 0, sizeof(itm));
351 for (i = 0; i < NITEM; i++)
352 itm[i].val1 = itm[i].val2 = i;
353
354 assert(alist_first(&ahead) == NULL);
355 dump("");
356 alist_add_head(&ahead, &itm[0]);
357 dump("");
358 alist_add_head(&ahead, &itm[1]);
359 dump("");
360 alist_add_tail(&ahead, &itm[2]);
361 dump("");
362 alist_add_tail(&ahead, &itm[3]);
363 dump("");
364 alist_del(&ahead, &itm[1]);
365 dump("");
366 printfrr("POP: %p\n", alist_pop(&ahead));
367 dump("");
368 printfrr("POP: %p\n", alist_pop(&ahead));
369 printfrr("POP: %p\n", alist_pop(&ahead));
370 printfrr("POP: %p\n", alist_pop(&ahead));
371 printfrr("POP: %p\n", alist_pop(&ahead));
372 dump("");
373 }
374 #else
375 #define basic_tests() do { } while (0)
376 #endif
377
main(int argc,char ** argv)378 int main(int argc, char **argv)
379 {
380 size_t i;
381
382 basic_tests();
383
384 seqlock_init(&sqlo);
385 seqlock_acquire_val(&sqlo, SEQLOCK_STARTVAL);
386
387 for (i = 0; i < NTHREADS; i++) {
388 seqlock_init(&thr[i].sqlo);
389 seqlock_acquire(&thr[i].sqlo, &sqlo);
390 thr[i].counter = 0;
391 thr[i].nullops = 0;
392
393 pthread_create(&thr[i].pt, NULL, thr1func, &thr[i]);
394 }
395
396 struct testrun *tr;
397
398 for (tr = runs; tr; tr = tr->next)
399 run_tr(tr);
400
401 for (i = 0; i < NTHREADS; i++)
402 pthread_join(thr[i].pt, NULL);
403
404 return 0;
405 }
406