]>
git.proxmox.com Git - mirror_frr.git/blob - tests/lib/test_atomlist.c
1 // SPDX-License-Identifier: ISC
3 * Copyright (c) 2016-2018 David Lamparter, for NetDEF, Inc.
31 static struct seqlock sqlo
;
33 PREDECL_ATOMLIST(alist
);
34 PREDECL_ATOMSORT_UNIQ(asort
);
37 struct alist_item chain
;
38 struct asort_item sortc
;
41 DECLARE_ATOMLIST(alist
, struct item
, chain
);
43 static int icmp(const struct item
*a
, const struct item
*b
);
44 DECLARE_ATOMSORT_UNIQ(asort
, struct item
, sortc
, icmp
);
46 static int icmp(const struct item
*a
, const struct item
*b
)
48 if (a
->val1
> b
->val1
)
50 if (a
->val1
< b
->val1
)
56 struct item itm
[NITEM
];
58 static struct alist_head ahead
;
59 static struct asort_head shead
;
62 static struct testthread
{
65 size_t counter
, nullops
;
74 void (*func
)(unsigned int offset
);
76 struct testrun
*runs
= NULL
;
80 #define deftestrun(name, _desc, _prefill, _sorted) \
81 static void trfunc_##name(unsigned int offset); \
82 struct testrun tr_##name = { \
85 .prefill = _prefill, \
86 .func = &trfunc_##name, \
87 .sorted = _sorted }; \
88 static void __attribute__((constructor)) trsetup_##name(void) \
90 struct testrun **inspos = &runs; \
91 while (*inspos && (*inspos)->lineno < tr_##name.lineno) \
92 inspos = &(*inspos)->next; \
93 tr_##name.next = *inspos; \
94 *inspos = &tr_##name; \
96 static void trfunc_##name(unsigned int offset) \
101 thr[offset].counter = i; \
102 thr[offset].nullops = n; \
105 deftestrun(add
, "add vs. add", 0, false)
106 for (; i
< NITEM
/ NTHREADS
; i
++)
107 alist_add_head(&ahead
, &itm
[i
* NTHREADS
+ offset
]);
110 deftestrun(del
, "del vs. del", NOCLEAR
, false)
111 for (; i
< NITEM
/ NTHREADS
/ 10; i
++)
112 alist_del(&ahead
, &itm
[i
* NTHREADS
+ offset
]);
115 deftestrun(addtail
, "add_tail vs. add_tail", 0, false)
116 for (; i
< NITEM
/ NTHREADS
; i
++)
117 alist_add_tail(&ahead
, &itm
[i
* NTHREADS
+ offset
]);
120 deftestrun(pop
, "pop vs. pop", NOCLEAR
, false)
121 for (; i
< NITEM
/ NTHREADS
; )
122 if (alist_pop(&ahead
))
128 deftestrun(headN_vs_pop1
, "add_head(N) vs. pop(1)", 1, false);
130 struct item
*dr
= NULL
;
132 for (i
= n
= 0; i
< NITEM
; ) {
133 dr
= alist_pop(&ahead
);
140 for (i
= offset
; i
< NITEM
; i
+= NTHREADS
)
141 alist_add_head(&ahead
, &itm
[i
]);
146 deftestrun(head1_vs_popN
, "add_head(1) vs. pop(N)", 0, false);
147 if (offset
< NTHREADS
- 1) {
148 struct item
*dr
= NULL
;
150 for (i
= n
= 0; i
< NITEM
/ NTHREADS
; ) {
151 dr
= alist_pop(&ahead
);
158 for (i
= 0; i
< NITEM
; i
++)
159 alist_add_head(&ahead
, &itm
[i
]);
164 deftestrun(headN_vs_popN
, "add_head(N) vs. pop(N)", NTHREADS
/ 2, false)
165 if (offset
< NTHREADS
/ 2) {
166 struct item
*dr
= NULL
;
168 for (i
= n
= 0; i
< NITEM
* 2 / NTHREADS
; ) {
169 dr
= alist_pop(&ahead
);
176 for (i
= offset
; i
< NITEM
; i
+= NTHREADS
)
177 alist_add_head(&ahead
, &itm
[i
]);
182 deftestrun(tailN_vs_pop1
, "add_tail(N) vs. pop(1)", 1, false)
184 struct item
*dr
= NULL
;
186 for (i
= n
= 0; i
< NITEM
- (NITEM
/ NTHREADS
); ) {
187 dr
= alist_pop(&ahead
);
194 for (i
= offset
; i
< NITEM
; i
+= NTHREADS
)
195 alist_add_tail(&ahead
, &itm
[i
]);
200 deftestrun(tail1_vs_popN
, "add_tail(1) vs. pop(N)", 0, false)
201 if (offset
< NTHREADS
- 1) {
202 struct item
*dr
= NULL
;
204 for (i
= n
= 0; i
< NITEM
/ NTHREADS
; ) {
205 dr
= alist_pop(&ahead
);
212 for (i
= 0; i
< NITEM
; i
++)
213 alist_add_tail(&ahead
, &itm
[i
]);
218 deftestrun(sort_add
, "add_sort vs. add_sort", 0, true)
219 for (; i
< NITEM
/ NTHREADS
/ 10; i
++)
220 asort_add(&shead
, &itm
[i
* NTHREADS
+ offset
]);
223 deftestrun(sort_del
, "del_sort vs. del_sort", NOCLEAR
, true)
224 for (; i
< NITEM
/ NTHREADS
/ 10; i
++)
225 asort_del(&shead
, &itm
[i
* NTHREADS
+ offset
]);
228 deftestrun(sort_add_del
, "add_sort vs. del_sort", NTHREADS
/ 2, true)
229 if (offset
< NTHREADS
/ 2) {
230 for (; i
< NITEM
/ NTHREADS
/ 10; i
++)
231 asort_del(&shead
, &itm
[i
* NTHREADS
+ offset
]);
233 for (; i
< NITEM
/ NTHREADS
/ 10; i
++)
234 asort_add(&shead
, &itm
[i
* NTHREADS
+ offset
]);
238 static void *thr1func(void *arg
)
240 struct testthread
*p
= arg
;
241 unsigned int offset
= (unsigned int)(p
- &thr
[0]);
245 for (tr
= runs
; tr
; tr
= tr
->next
) {
246 sv
= seqlock_bump(&p
->sqlo
) - SEQLOCK_INCR
;
247 seqlock_wait(&sqlo
, sv
);
251 seqlock_bump(&p
->sqlo
);
256 static void clear_list(size_t prefill
)
260 memset(&ahead
, 0, sizeof(ahead
));
261 memset(&shead
, 0, sizeof(shead
));
262 memset(itm
, 0, sizeof(itm
));
263 for (i
= 0; i
< NITEM
; i
++) {
264 itm
[i
].val1
= itm
[i
].val2
= i
;
265 if ((i
% NTHREADS
) < prefill
) {
266 alist_add_tail(&ahead
, &itm
[i
]);
267 asort_add(&shead
, &itm
[i
]);
272 static void run_tr(struct testrun
*tr
)
274 const char *desc
= tr
->desc
;
278 size_t c
= 0, s
= 0, n
= 0;
279 struct item
*item
, *prev
, dummy
;
281 printfrr("[%02u] %35s %s\n", seqlock_cur(&sqlo
) >> 2, "", desc
);
284 if (tr
->prefill
!= NOCLEAR
)
285 clear_list(tr
->prefill
);
288 sv
= seqlock_bump(&sqlo
) - SEQLOCK_INCR
;
289 for (size_t i
= 0; i
< NTHREADS
; i
++) {
290 seqlock_wait(&thr
[i
].sqlo
, seqlock_cur(&sqlo
));
297 delta
= monotime_since(&tv
, NULL
);
299 uint64_t prevval
= 0;
301 frr_each(asort
, &shead
, item
) {
302 assert(item
->val1
>= prevval
);
303 prevval
= item
->val1
;
306 assert(c
== asort_count(&shead
));
309 frr_each(alist
, &ahead
, item
) {
310 assert(item
!= prev
);
315 assert(c
== alist_count(&ahead
));
317 printfrr("\033[1A[%02u] %9"PRId64
"us c=%5zu s=%5zu n=%5zu %s\n",
318 sv
>> 2, delta
, c
, s
, n
, desc
);
322 static void dump(const char *lbl
)
324 struct item
*item
, *safe
;
327 printfrr("dumping %s:\n", lbl
);
328 frr_each_safe(alist
, &ahead
, item
) {
329 printfrr("%s %3zu %p %3"PRIu64
" %3"PRIu64
"\n", lbl
, ctr
++,
330 (void *)item
, item
->val1
, item
->val2
);
334 static void basic_tests(void)
338 memset(&ahead
, 0, sizeof(ahead
));
339 memset(itm
, 0, sizeof(itm
));
340 for (i
= 0; i
< NITEM
; i
++)
341 itm
[i
].val1
= itm
[i
].val2
= i
;
343 assert(alist_first(&ahead
) == NULL
);
345 alist_add_head(&ahead
, &itm
[0]);
347 alist_add_head(&ahead
, &itm
[1]);
349 alist_add_tail(&ahead
, &itm
[2]);
351 alist_add_tail(&ahead
, &itm
[3]);
353 alist_del(&ahead
, &itm
[1]);
355 printfrr("POP: %p\n", alist_pop(&ahead
));
357 printfrr("POP: %p\n", alist_pop(&ahead
));
358 printfrr("POP: %p\n", alist_pop(&ahead
));
359 printfrr("POP: %p\n", alist_pop(&ahead
));
360 printfrr("POP: %p\n", alist_pop(&ahead
));
364 #define basic_tests() do { } while (0)
367 int main(int argc
, char **argv
)
374 seqlock_acquire_val(&sqlo
, SEQLOCK_STARTVAL
);
376 for (i
= 0; i
< NTHREADS
; i
++) {
377 seqlock_init(&thr
[i
].sqlo
);
378 seqlock_acquire(&thr
[i
].sqlo
, &sqlo
);
382 pthread_create(&thr
[i
].pt
, NULL
, thr1func
, &thr
[i
]);
387 for (tr
= runs
; tr
; tr
= tr
->next
)
390 for (i
= 0; i
< NTHREADS
; i
++)
391 pthread_join(thr
[i
].pt
, NULL
);