]>
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.
42 static struct seqlock sqlo
;
44 PREDECL_ATOMLIST(alist
)
45 PREDECL_ATOMSORT_UNIQ(asort
)
48 struct alist_item chain
;
49 struct asort_item sortc
;
52 DECLARE_ATOMLIST(alist
, struct item
, chain
)
54 static int icmp(const struct item
*a
, const struct item
*b
);
55 DECLARE_ATOMSORT_UNIQ(asort
, struct item
, sortc
, icmp
)
57 static int icmp(const struct item
*a
, const struct item
*b
)
59 if (a
->val1
> b
->val1
)
61 if (a
->val1
< b
->val1
)
67 struct item itm
[NITEM
];
69 static struct alist_head ahead
;
70 static struct asort_head shead
;
73 static struct testthread
{
76 size_t counter
, nullops
;
85 void (*func
)(unsigned int offset
);
87 struct testrun
*runs
= NULL
;
91 #define deftestrun(name, _desc, _prefill, _sorted) \
92 static void trfunc_##name(unsigned int offset); \
93 struct testrun tr_##name = { \
96 .prefill = _prefill, \
97 .func = &trfunc_##name, \
98 .sorted = _sorted }; \
99 static void __attribute__((constructor)) trsetup_##name(void) \
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; \
107 static void trfunc_##name(unsigned int offset) \
112 thr[offset].counter = i; \
113 thr[offset].nullops = n; \
116 deftestrun(add
, "add vs. add", 0, false)
117 for (; i
< NITEM
/ NTHREADS
; i
++)
118 alist_add_head(&ahead
, &itm
[i
* NTHREADS
+ offset
]);
121 deftestrun(del
, "del vs. del", NOCLEAR
, false)
122 for (; i
< NITEM
/ NTHREADS
/ 10; i
++)
123 alist_del(&ahead
, &itm
[i
* NTHREADS
+ offset
]);
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
]);
131 deftestrun(pop
, "pop vs. pop", NOCLEAR
, false)
132 for (; i
< NITEM
/ NTHREADS
; )
133 if (alist_pop(&ahead
))
139 deftestrun(headN_vs_pop1
, "add_head(N) vs. pop(1)", 1, false);
141 struct item
*dr
= NULL
;
143 for (i
= n
= 0; i
< NITEM
; ) {
144 dr
= alist_pop(&ahead
);
151 for (i
= offset
; i
< NITEM
; i
+= NTHREADS
)
152 alist_add_head(&ahead
, &itm
[i
]);
157 deftestrun(head1_vs_popN
, "add_head(1) vs. pop(N)", 0, false);
158 if (offset
< NTHREADS
- 1) {
159 struct item
*dr
= NULL
;
161 for (i
= n
= 0; i
< NITEM
/ NTHREADS
; ) {
162 dr
= alist_pop(&ahead
);
169 for (i
= 0; i
< NITEM
; i
++)
170 alist_add_head(&ahead
, &itm
[i
]);
175 deftestrun(headN_vs_popN
, "add_head(N) vs. pop(N)", NTHREADS
/ 2, false)
176 if (offset
< NTHREADS
/ 2) {
177 struct item
*dr
= NULL
;
179 for (i
= n
= 0; i
< NITEM
* 2 / NTHREADS
; ) {
180 dr
= alist_pop(&ahead
);
187 for (i
= offset
; i
< NITEM
; i
+= NTHREADS
)
188 alist_add_head(&ahead
, &itm
[i
]);
193 deftestrun(tailN_vs_pop1
, "add_tail(N) vs. pop(1)", 1, false)
195 struct item
*dr
= NULL
;
197 for (i
= n
= 0; i
< NITEM
- (NITEM
/ NTHREADS
); ) {
198 dr
= alist_pop(&ahead
);
205 for (i
= offset
; i
< NITEM
; i
+= NTHREADS
)
206 alist_add_tail(&ahead
, &itm
[i
]);
211 deftestrun(tail1_vs_popN
, "add_tail(1) vs. pop(N)", 0, false)
212 if (offset
< NTHREADS
- 1) {
213 struct item
*dr
= NULL
;
215 for (i
= n
= 0; i
< NITEM
/ NTHREADS
; ) {
216 dr
= alist_pop(&ahead
);
223 for (i
= 0; i
< NITEM
; i
++)
224 alist_add_tail(&ahead
, &itm
[i
]);
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
]);
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
]);
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
]);
244 for (; i
< NITEM
/ NTHREADS
/ 10; i
++)
245 asort_add(&shead
, &itm
[i
* NTHREADS
+ offset
]);
249 static void *thr1func(void *arg
)
251 struct testthread
*p
= arg
;
252 unsigned int offset
= (unsigned int)(p
- &thr
[0]);
256 for (tr
= runs
; tr
; tr
= tr
->next
) {
257 sv
= seqlock_bump(&p
->sqlo
) - SEQLOCK_INCR
;
258 seqlock_wait(&sqlo
, sv
);
262 seqlock_bump(&p
->sqlo
);
267 static void clear_list(size_t prefill
)
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
]);
283 static void run_tr(struct testrun
*tr
)
285 const char *desc
= tr
->desc
;
289 size_t c
= 0, s
= 0, n
= 0;
290 struct item
*item
, *prev
, dummy
;
292 printfrr("[%02u] %35s %s\n", seqlock_cur(&sqlo
) >> 2, "", desc
);
295 if (tr
->prefill
!= NOCLEAR
)
296 clear_list(tr
->prefill
);
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
));
308 delta
= monotime_since(&tv
, NULL
);
310 uint64_t prevval
= 0;
312 frr_each(asort
, &shead
, item
) {
313 assert(item
->val1
>= prevval
);
314 prevval
= item
->val1
;
317 assert(c
== asort_count(&shead
));
320 frr_each(alist
, &ahead
, item
) {
321 assert(item
!= prev
);
326 assert(c
== alist_count(&ahead
));
328 printfrr("\033[1A[%02u] %9"PRId64
"us c=%5zu s=%5zu n=%5zu %s\n",
329 sv
>> 2, delta
, c
, s
, n
, desc
);
333 static void dump(const char *lbl
)
335 struct item
*item
, *safe
;
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
);
345 static void basic_tests(void)
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
;
354 assert(alist_first(&ahead
) == NULL
);
356 alist_add_head(&ahead
, &itm
[0]);
358 alist_add_head(&ahead
, &itm
[1]);
360 alist_add_tail(&ahead
, &itm
[2]);
362 alist_add_tail(&ahead
, &itm
[3]);
364 alist_del(&ahead
, &itm
[1]);
366 printfrr("POP: %p\n", alist_pop(&ahead
));
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
));
375 #define basic_tests() do { } while (0)
378 int main(int argc
, char **argv
)
385 seqlock_acquire_val(&sqlo
, SEQLOCK_STARTVAL
);
387 for (i
= 0; i
< NTHREADS
; i
++) {
388 seqlock_init(&thr
[i
].sqlo
);
389 seqlock_acquire(&thr
[i
].sqlo
, &sqlo
);
393 pthread_create(&thr
[i
].pt
, NULL
, thr1func
, &thr
[i
]);
398 for (tr
= runs
; tr
; tr
= tr
->next
)
401 for (i
= 0; i
< NTHREADS
; i
++)
402 pthread_join(thr
[i
].pt
, NULL
);