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