]>
Commit | Line | Data |
---|---|---|
bcea0c0f DL |
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" | |
fb84c629 | 32 | #include "printfrr.h" |
bcea0c0f DL |
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 | ||
960b9a53 DL |
44 | PREDECL_ATOMLIST(alist); |
45 | PREDECL_ATOMSORT_UNIQ(asort); | |
bcea0c0f DL |
46 | struct item { |
47 | uint64_t val1; | |
48 | struct alist_item chain; | |
49 | struct asort_item sortc; | |
50 | uint64_t val2; | |
51 | }; | |
960b9a53 | 52 | DECLARE_ATOMLIST(alist, struct item, chain); |
bcea0c0f DL |
53 | |
54 | static int icmp(const struct item *a, const struct item *b); | |
960b9a53 | 55 | DECLARE_ATOMSORT_UNIQ(asort, struct item, sortc, icmp); |
bcea0c0f DL |
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 | ||
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) { | |
6046b690 | 257 | sv = seqlock_bump(&p->sqlo) - SEQLOCK_INCR; |
bcea0c0f DL |
258 | seqlock_wait(&sqlo, sv); |
259 | ||
260 | tr->func(offset); | |
261 | } | |
262 | seqlock_bump(&p->sqlo); | |
263 | ||
264 | return NULL; | |
265 | } | |
266 | ||
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 | ||
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 | ||
fb84c629 | 292 | printfrr("[%02u] %35s %s\n", seqlock_cur(&sqlo) >> 2, "", desc); |
bcea0c0f DL |
293 | fflush(stdout); |
294 | ||
295 | if (tr->prefill != NOCLEAR) | |
296 | clear_list(tr->prefill); | |
297 | ||
298 | monotime(&tv); | |
6046b690 | 299 | sv = seqlock_bump(&sqlo) - SEQLOCK_INCR; |
bcea0c0f DL |
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 | ||
81fddbe7 | 312 | frr_each(asort, &shead, item) { |
bcea0c0f DL |
313 | assert(item->val1 >= prevval); |
314 | prevval = item->val1; | |
315 | c++; | |
316 | } | |
317 | assert(c == asort_count(&shead)); | |
318 | } else { | |
319 | prev = &dummy; | |
81fddbe7 | 320 | frr_each(alist, &ahead, item) { |
bcea0c0f DL |
321 | assert(item != prev); |
322 | prev = item; | |
323 | c++; | |
324 | assert(c <= NITEM); | |
325 | } | |
326 | assert(c == alist_count(&ahead)); | |
327 | } | |
fb84c629 | 328 | printfrr("\033[1A[%02u] %9"PRId64"us c=%5zu s=%5zu n=%5zu %s\n", |
6046b690 | 329 | sv >> 2, delta, c, s, n, desc); |
bcea0c0f DL |
330 | } |
331 | ||
332 | #ifdef BASIC_TESTS | |
333 | static void dump(const char *lbl) | |
334 | { | |
335 | struct item *item, *safe; | |
336 | size_t ctr = 0; | |
337 | ||
fb84c629 | 338 | printfrr("dumping %s:\n", lbl); |
81fddbe7 | 339 | frr_each_safe(alist, &ahead, item) { |
fb84c629 | 340 | printfrr("%s %3zu %p %3"PRIu64" %3"PRIu64"\n", lbl, ctr++, |
bcea0c0f DL |
341 | (void *)item, item->val1, item->val2); |
342 | } | |
343 | } | |
344 | ||
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(""); | |
fb84c629 | 366 | printfrr("POP: %p\n", alist_pop(&ahead)); |
bcea0c0f | 367 | dump(""); |
fb84c629 DL |
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)); | |
bcea0c0f DL |
372 | dump(""); |
373 | } | |
374 | #else | |
375 | #define basic_tests() do { } while (0) | |
376 | #endif | |
377 | ||
378 | int main(int argc, char **argv) | |
379 | { | |
380 | size_t i; | |
381 | ||
382 | basic_tests(); | |
383 | ||
384 | seqlock_init(&sqlo); | |
6046b690 | 385 | seqlock_acquire_val(&sqlo, SEQLOCK_STARTVAL); |
bcea0c0f DL |
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 | } |