]>
git.proxmox.com Git - mirror_frr.git/blob - tests/lib/test_atomlist.c
2 * Copyright (c) 2016-2018 David Lamparter, for NetDEF, Inc.
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.
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.
41 static struct seqlock sqlo
;
43 PREDECL_ATOMLIST(alist
)
44 PREDECL_ATOMSORT_UNIQ(asort
)
47 struct alist_item chain
;
48 struct asort_item sortc
;
51 DECLARE_ATOMLIST(alist
, struct item
, chain
)
53 static int icmp(const struct item
*a
, const struct item
*b
);
54 DECLARE_ATOMSORT_UNIQ(asort
, struct item
, sortc
, icmp
)
56 static int icmp(const struct item
*a
, const struct item
*b
)
58 if (a
->val1
> b
->val1
)
60 if (a
->val1
< b
->val1
)
66 struct item itm
[NITEM
];
68 static struct alist_head ahead
;
69 static struct asort_head shead
;
72 static struct testthread
{
75 size_t counter
, nullops
;
84 void (*func
)(unsigned int offset
);
86 struct testrun
*runs
= NULL
;
90 #define deftestrun(name, _desc, _prefill, _sorted) \
91 static void trfunc_##name(unsigned int offset); \
92 struct testrun tr_##name = { \
95 .prefill = _prefill, \
96 .func = &trfunc_##name, \
97 .sorted = _sorted }; \
98 static void __attribute__((constructor)) trsetup_##name(void) \
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; \
106 static void trfunc_##name(unsigned int offset) \
111 thr[offset].counter = i; \
112 thr[offset].nullops = n; \
115 deftestrun(add
, "add vs. add", 0, false)
116 for (; i
< NITEM
/ NTHREADS
; i
++)
117 alist_add_head(&ahead
, &itm
[i
* NTHREADS
+ offset
]);
120 deftestrun(del
, "del vs. del", NOCLEAR
, false)
121 for (; i
< NITEM
/ NTHREADS
/ 10; i
++)
122 alist_del(&ahead
, &itm
[i
* NTHREADS
+ offset
]);
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
]);
130 deftestrun(pop
, "pop vs. pop", NOCLEAR
, false)
131 for (; i
< NITEM
/ NTHREADS
; )
132 if (alist_pop(&ahead
))
138 deftestrun(headN_vs_pop1
, "add_head(N) vs. pop(1)", 1, false);
140 struct item
*dr
= NULL
;
142 for (i
= n
= 0; i
< NITEM
; ) {
143 dr
= alist_pop(&ahead
);
150 for (i
= offset
; i
< NITEM
; i
+= NTHREADS
)
151 alist_add_head(&ahead
, &itm
[i
]);
156 deftestrun(head1_vs_popN
, "add_head(1) vs. pop(N)", 0, false);
157 if (offset
< NTHREADS
- 1) {
158 struct item
*dr
= NULL
;
160 for (i
= n
= 0; i
< NITEM
/ NTHREADS
; ) {
161 dr
= alist_pop(&ahead
);
168 for (i
= 0; i
< NITEM
; i
++)
169 alist_add_head(&ahead
, &itm
[i
]);
174 deftestrun(headN_vs_popN
, "add_head(N) vs. pop(N)", NTHREADS
/ 2, false)
175 if (offset
< NTHREADS
/ 2) {
176 struct item
*dr
= NULL
;
178 for (i
= n
= 0; i
< NITEM
* 2 / NTHREADS
; ) {
179 dr
= alist_pop(&ahead
);
186 for (i
= offset
; i
< NITEM
; i
+= NTHREADS
)
187 alist_add_head(&ahead
, &itm
[i
]);
192 deftestrun(tailN_vs_pop1
, "add_tail(N) vs. pop(1)", 1, false)
194 struct item
*dr
= NULL
;
196 for (i
= n
= 0; i
< NITEM
- (NITEM
/ NTHREADS
); ) {
197 dr
= alist_pop(&ahead
);
204 for (i
= offset
; i
< NITEM
; i
+= NTHREADS
)
205 alist_add_tail(&ahead
, &itm
[i
]);
210 deftestrun(tail1_vs_popN
, "add_tail(1) vs. pop(N)", 0, false)
211 if (offset
< NTHREADS
- 1) {
212 struct item
*dr
= NULL
;
214 for (i
= n
= 0; i
< NITEM
/ NTHREADS
; ) {
215 dr
= alist_pop(&ahead
);
222 for (i
= 0; i
< NITEM
; i
++)
223 alist_add_tail(&ahead
, &itm
[i
]);
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
]);
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
]);
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
]);
243 for (; i
< NITEM
/ NTHREADS
/ 10; i
++)
244 asort_add(&shead
, &itm
[i
* NTHREADS
+ offset
]);
248 static void *thr1func(void *arg
)
250 struct testthread
*p
= arg
;
251 unsigned int offset
= (unsigned int)(p
- &thr
[0]);
255 for (tr
= runs
; tr
; tr
= tr
->next
) {
256 sv
= seqlock_bump(&p
->sqlo
) - SEQLOCK_INCR
;
257 seqlock_wait(&sqlo
, sv
);
261 seqlock_bump(&p
->sqlo
);
266 static void clear_list(size_t prefill
)
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
]);
282 static void run_tr(struct testrun
*tr
)
284 const char *desc
= tr
->desc
;
288 size_t c
= 0, s
= 0, n
= 0;
289 struct item
*item
, *prev
, dummy
;
291 printf("[%02u] %35s %s\n", seqlock_cur(&sqlo
) >> 2, "", desc
);
294 if (tr
->prefill
!= NOCLEAR
)
295 clear_list(tr
->prefill
);
298 sv
= seqlock_bump(&sqlo
) - SEQLOCK_INCR
;
299 for (size_t i
= 0; i
< NTHREADS
; i
++) {
300 seqlock_wait(&thr
[i
].sqlo
, seqlock_cur(&sqlo
));
307 delta
= monotime_since(&tv
, NULL
);
309 uint64_t prevval
= 0;
311 frr_each(asort
, &shead
, item
) {
312 assert(item
->val1
>= prevval
);
313 prevval
= item
->val1
;
316 assert(c
== asort_count(&shead
));
319 frr_each(alist
, &ahead
, item
) {
320 assert(item
!= prev
);
325 assert(c
== alist_count(&ahead
));
327 printf("\033[1A[%02u] %9"PRId64
"us c=%5zu s=%5zu n=%5zu %s\n",
328 sv
>> 2, delta
, c
, s
, n
, desc
);
332 static void dump(const char *lbl
)
334 struct item
*item
, *safe
;
337 printf("dumping %s:\n", lbl
);
338 frr_each_safe(alist
, &ahead
, item
) {
339 printf("%s %3zu %p %3"PRIu64
" %3"PRIu64
"\n", lbl
, ctr
++,
340 (void *)item
, item
->val1
, item
->val2
);
344 static void basic_tests(void)
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
;
353 assert(alist_first(&ahead
) == NULL
);
355 alist_add_head(&ahead
, &itm
[0]);
357 alist_add_head(&ahead
, &itm
[1]);
359 alist_add_tail(&ahead
, &itm
[2]);
361 alist_add_tail(&ahead
, &itm
[3]);
363 alist_del(&ahead
, &itm
[1]);
365 printf("POP: %p\n", alist_pop(&ahead
));
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
));
374 #define basic_tests() do { } while (0)
377 int main(int argc
, char **argv
)
384 seqlock_acquire_val(&sqlo
, SEQLOCK_STARTVAL
);
386 for (i
= 0; i
< NTHREADS
; i
++) {
387 seqlock_init(&thr
[i
].sqlo
);
388 seqlock_acquire(&thr
[i
].sqlo
, &sqlo
);
392 pthread_create(&thr
[i
].pt
, NULL
, thr1func
, &thr
[i
]);
397 for (tr
= runs
; tr
; tr
= tr
->next
)
400 for (i
= 0; i
< NTHREADS
; i
++)
401 pthread_join(thr
[i
].pt
, NULL
);