[ovs-dev,v2] tests: add unit tests to rculist

Low test coverage on this area caused some errors to remain unnoticed.
Add basic functional test of rculist.

Signed-off-by: Adrian Moreno <amorenoz@redhat.com>

---
Changes since v1:
- Fix Windows build
---
 tests/automake.mk    |   1 +
 tests/library.at     |   5 +
 tests/test-rculist.c | 214 +++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 220 insertions(+)
 create mode 100644 tests/test-rculist.c

On 1/2/23 09:58, Adrian Moreno wrote:
> Low test coverage on this area caused some errors to remain unnoticed.
> Add basic functional test of rculist.
> 
> Signed-off-by: Adrian Moreno <amorenoz@redhat.com>
> 
> ---
> Changes since v1:
> - Fix Windows build

Hi, Adrian.  Thanks for the update.

I have one big comment about the license inline, others are just
small style nitpicks since the new version is needed anyway.

Best regards, Ilya Maximets.

> ---
>  tests/automake.mk    |   1 +
>  tests/library.at     |   5 +
>  tests/test-rculist.c | 214 +++++++++++++++++++++++++++++++++++++++++++
>  3 files changed, 220 insertions(+)
>  create mode 100644 tests/test-rculist.c
> 
> diff --git a/tests/automake.mk b/tests/automake.mk
> index d509cf935..88f97b8b7 100644
> --- a/tests/automake.mk
> +++ b/tests/automake.mk
> @@ -474,6 +474,7 @@ tests_ovstest_SOURCES = \
>  	tests/test-packets.c \
>  	tests/test-random.c \
>  	tests/test-rcu.c \
> +	tests/test-rculist.c \
>  	tests/test-reconnect.c \
>  	tests/test-rstp.c \
>  	tests/test-sflow.c \
> diff --git a/tests/library.at b/tests/library.at
> index bafb28277..164ae789d 100644
> --- a/tests/library.at
> +++ b/tests/library.at
> @@ -27,6 +27,11 @@ AT_CHECK([ovstest test-hindex], [0], [.....................
>  ])
>  AT_CLEANUP
>  
> +AT_SETUP([test rcu linked lists])
> +AT_CHECK([ovstest test-rculist], [0], [.....
> +])
> +AT_CLEANUP
> +
>  AT_SETUP([cuckoo hash])
>  AT_KEYWORDS([cmap])
>  AT_CHECK([ovstest test-cmap check 1], [0], [...
> diff --git a/tests/test-rculist.c b/tests/test-rculist.c
> new file mode 100644
> index 000000000..1fdac9700
> --- /dev/null
> +++ b/tests/test-rculist.c
> @@ -0,0 +1,214 @@

Please, add a license boilerplate here.

> +#include <config.h>
> +#undef NDEBUG
> +#include <unistd.h>
> +
> +#include "ovstest.h"
> +#include "rculist.h"
> +#include "openvswitch/list.h"
> +#include "ovs-thread.h"
> +#include "random.h"
> +#include "util.h"

Maybe sort these headers.

> +
> +enum { MAX_ELEMS = 10, MAX_CHECKS = 200 };
> +
> +/* Sample list element. */
> +struct element {
> +    int value;
> +    struct rculist node;
> +};
> +
> +static void
> +do_usleep(unsigned int usecs) {

'{' should be on a separate line.

> +#ifdef _WIN32
> +    Sleep(MAX(usecs / 1000, 1));
> +#else
> +    usleep(usecs);
> +#endif
> +}
> +
> +/* Continuously check the integrity of the list until it's empty. */
> +static void *
> +checker_main(void *aux)
> +{
> +    struct element *elem;
> +    struct rculist *list = (struct rculist *) aux;
> +    bool checked = false;

Reverse x-mass tree.

> +
> +    for (int i = 0; i < MAX_CHECKS; i++) {
> +        int value = -1;

An empty line here.

> +        RCULIST_FOR_EACH (elem, node, list) {
> +            ovs_assert(value <= elem->value);
> +            ovs_assert(elem->value < MAX_ELEMS);
> +            value = elem->value;
> +            if (!checked) {
> +                checked = true;
> +            }
> +            do_usleep(10);
> +        }
> +
> +        ovsrcu_quiesce();
> +
> +        if (checked && rculist_is_empty(list)) {
> +            break;
> +        }
> +    }
> +    return NULL;
> +}
> +
> +/* Run test while a thread checks the integrity of the list.
> + * Tests must end up emptying the list. */
> +static void
> +run_test_while_checking(void (*function)(struct rculist *list))
> +{
> +    struct rculist list;
> +    pthread_t checker;
> +
> +    rculist_init(&list);
> +
> +    checker = ovs_thread_create("checker", checker_main, &list);
> +    function(&list);
> +
> +    ovs_assert(rculist_is_empty(&list));
> +    ovsrcu_quiesce();
> +    xpthread_join(checker, NULL);
> +    printf(".");
> +}
> +
> +static void
> +test_rculist_insert_delete__(struct rculist *list, bool long_version)
> +{
> +    struct element *elem;
> +    int value;
> +
> +    for (int i = 1; i < MAX_ELEMS; i++) {
> +        elem = xmalloc(sizeof *elem);
> +        elem->value = i;
> +        rculist_insert(list, &elem->node);
> +        /* Leave some time for checkers to iterate through. */
> +        do_usleep(random_range(1000));
> +    }
> +
> +    ovsrcu_quiesce();
> +
> +    value = MAX_ELEMS;
> +    RCULIST_FOR_EACH_REVERSE_PROTECTED (elem, node, list) {
> +        ovs_assert (elem->value <= value);
> +        value = elem->value;
> +    }
> +
> +    if (long_version) {
> +        struct element *next;
> +        RCULIST_FOR_EACH_SAFE_PROTECTED (elem, next, node, list) {
> +            rculist_remove(&elem->node);
> +            ovsrcu_postpone(free, elem);
> +            /* Leave some time for checkers to iterate through. */
> +            do_usleep(random_range(1000));
> +        }
> +    } else {
> +        RCULIST_FOR_EACH_SAFE_PROTECTED (elem, node, list) {
> +            rculist_remove(&elem->node);
> +            ovsrcu_postpone(free, elem);
> +            /* Leave some time for checkers to iterate through. */
> +            do_usleep(random_range(1000));
> +        }
> +    }
> +}
> +
> +static void
> +test_rculist_insert_delete(struct rculist *list) {

'{' on a separete line.

> +    test_rculist_insert_delete__(list, false);
> +}
> +
> +static void
> +test_rculist_insert_delete_long(struct rculist *list) {

Ditto.

> +    test_rculist_insert_delete__(list, true);
> +}
> +
> +static void
> +test_rculist_push_front_pop_back(struct rculist *list)
> +{
> +    struct element *elem;
> +
> +    for (int i = MAX_ELEMS - 1; i > 0; i--) {
> +        elem = xmalloc(sizeof *elem);
> +        elem->value = i;
> +        rculist_push_front(list, &elem->node);
> +        /* Leave some time for checkers to iterate through. */
> +        do_usleep(random_range(1000));
> +    }
> +
> +    ovsrcu_quiesce();
> +
> +    while (!rculist_is_empty(list)) {
> +        elem = CONTAINER_OF(rculist_pop_back(list), struct element, node);
> +        ovsrcu_postpone(free, elem);
> +        /* Leave some time for checkers to iterate through. */
> +        do_usleep(random_range(1000));
> +    }
> +}
> +
> +static void
> +test_rculist_push_back_pop_front(struct rculist *list)
> +{
> +    struct element *elem;
> +
> +    for (int i = 0 ; i < MAX_ELEMS; i++) {

There is a redundant space before the ';'.

> +        elem = xmalloc(sizeof *elem);
> +        elem->value = i;
> +        rculist_push_back(list, &elem->node);
> +        /* Leave some time for checkers to iterate through. */
> +        do_usleep(random_range(1000));
> +    }
> +
> +    ovsrcu_quiesce();
> +
> +    while (!rculist_is_empty(list)) {
> +        elem = CONTAINER_OF(rculist_pop_front(list), struct element, node);
> +        ovsrcu_postpone(free, elem);
> +        /* Leave some time for checkers to iterate through. */
> +        do_usleep(random_range(1000));
> +    }
> +}
> +
> +static void
> +test_rculist_splice(struct rculist *list)
> +{
> +    struct element *elem;
> +    struct rculist other;
> +    rculist_init(&other);
> +
> +    /* Insert elements in list by splicing an intermediate rculist */

Period at the end of a comment.

> +    for (int i = 0; i < MAX_ELEMS; i++) {
> +        elem = xmalloc(sizeof *elem);
> +        elem->value = i;
> +        rculist_insert(&other, &elem->node);
> +        rculist_splice_hidden(list, rculist_next_protected(&other), &other);
> +        rculist_init(&other);
> +        /* Leave some time for checkers to iterate through. */
> +        do_usleep(random_range(1000));
> +    }
> +
> +    ovsrcu_quiesce();
> +
> +    ovs_assert(rculist_size(list) == MAX_ELEMS);
> +    ovs_assert(rculist_is_empty(&other));
> +    while (!rculist_is_empty(list)) {
> +        elem = CONTAINER_OF(rculist_pop_front(list), struct element, node);
> +        ovsrcu_postpone(free, elem);
> +        /* Leave some time for checkers to iterate through. */
> +        do_usleep(random_range(1000));
> +    }
> +}
> +
> +static void
> +test_rculist_main(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
> +{
> +    run_test_while_checking(test_rculist_insert_delete);
> +    run_test_while_checking(test_rculist_insert_delete_long);
> +    run_test_while_checking(test_rculist_push_back_pop_front);
> +    run_test_while_checking(test_rculist_push_front_pop_back);
> +    run_test_while_checking(test_rculist_splice);
> +    printf("\n");
> +}
> +
> +OVSTEST_REGISTER("test-rculist", test_rculist_main);