Re: [igt-dev] [PATCH i-g-t] lib/igt_list: Update, clean-up and document igt_list

Petri Latvala
2019-10-25T11:22:46Z

On Thu, Oct 24, 2019 at 03:31:14PM +0300, Arkadiusz Hiler wrote:
> Our list was something between Wayland and Linux Kernel list
> implementations, right in the uncanny valley.
>
> On top of that it falsely claimed that it's a straight copy from the
> Wayland project.
>
> Let's make our impl more akin to the kernel one to ease the cognitive
> dissonance for the developers working on all those projects.
>
> This patch:
> * mimics the current kernel list interface
> * separates IGT helpers in the source files
> * adds brief explanation and code example for igt-doc
> * introduces igt_list.c as static inlines are not visible in the docs
>
> v2: mimic the kernel instead of wayland (Chris)
> - _head suffix for the sentinel/link struct
> - _entry_ in iterator names that go over the elements
>
> Cc: Petri Latvala <petri.latvala@intel.com>
> Cc: Chris Wilson <chris@chris-wilson.co.uk>
> Signed-off-by: Arkadiusz Hiler <arkadiusz.hiler@intel.com>
> ---
> benchmarks/gem_wsim.c | 6 +-
> .../igt-gpu-tools/igt-gpu-tools-docs.xml | 1 +
> lib/Makefile.sources | 2 +
> lib/igt_chamelium.c | 8 +-
> lib/igt_core.c | 8 +-
> lib/igt_dummyload.c | 10 +-
> lib/igt_dummyload.h | 2 +-
> lib/igt_kmod.c | 10 +-
> lib/igt_kmod.h | 4 +-
> lib/igt_list.c | 66 +++++++
> lib/igt_list.h | 164 +++++++++---------
> lib/meson.build | 1 +
> tests/vc4_purgeable_bo.c | 28 +--
> 13 files changed, 189 insertions(+), 121 deletions(-)
> create mode 100644 lib/igt_list.c
>
> diff --git a/benchmarks/gem_wsim.c b/benchmarks/gem_wsim.c
> index 87f873b0..d3c88615 100644
> --- a/benchmarks/gem_wsim.c
> +++ b/benchmarks/gem_wsim.c
> @@ -142,7 +142,7 @@ struct w_step
>
> /* Implementation details */
> unsigned int idx;
> - struct igt_list rq_link;
> + struct igt_list_head rq_link;
> unsigned int request;
> unsigned int preempt_us;
>
> @@ -213,7 +213,7 @@ struct workload
> unsigned long qd_sum[NUM_ENGINES];
> unsigned long nr_bb[NUM_ENGINES];
>
> - struct igt_list requests[NUM_ENGINES];
> + struct igt_list_head requests[NUM_ENGINES];
> unsigned int nrequest[NUM_ENGINES];
>
> struct workload *global_wrk;
> @@ -1061,7 +1061,7 @@ clone_workload(struct workload *_wrk)
> }
>
> for (i = 0; i < NUM_ENGINES; i++)
> - igt_list_init(&wrk->requests[i]);
> + IGT_INIT_LIST_HEAD(&wrk->requests[i]);
>
> return wrk;
> }
> diff --git a/docs/reference/igt-gpu-tools/igt-gpu-tools-docs.xml b/docs/reference/igt-gpu-tools/igt-gpu-tools-docs.xml
> index ac83272f..3f14d7be 100644
> --- a/docs/reference/igt-gpu-tools/igt-gpu-tools-docs.xml
> +++ b/docs/reference/igt-gpu-tools/igt-gpu-tools-docs.xml
> @@ -31,6 +31,7 @@
> <xi:include href="xml/igt_gvt.xml"/>
> <xi:include href="xml/igt_kmod.xml"/>
> <xi:include href="xml/igt_kms.xml"/>
> + <xi:include href="xml/igt_list.xml"/>
> <xi:include href="xml/igt_pm.xml"/>
> <xi:include href="xml/igt_primes.xml"/>
> <xi:include href="xml/igt_rand.xml"/>
> diff --git a/lib/Makefile.sources b/lib/Makefile.sources
> index 34e0c012..1b58b6d0 100644
> --- a/lib/Makefile.sources
> +++ b/lib/Makefile.sources
> @@ -41,6 +41,8 @@ lib_source_list = \
> igt_halffloat.h \
> igt_infoframe.c \
> igt_infoframe.h \
> + igt_list.c \
> + igt_list.h \
> igt_matrix.c \
> igt_matrix.h \
> igt_primes.c \
> diff --git a/lib/igt_chamelium.c b/lib/igt_chamelium.c
> index 1b03a103..9971f51d 100644
> --- a/lib/igt_chamelium.c
> +++ b/lib/igt_chamelium.c
> @@ -87,7 +87,7 @@ struct chamelium_edid {
> struct edid *base;
> struct edid *raw[CHAMELIUM_MAX_PORTS];
> int ids[CHAMELIUM_MAX_PORTS];
> - struct igt_list link;
> + struct igt_list_head link;
> };
>
> struct chamelium_port {
> @@ -122,7 +122,7 @@ struct chamelium {
>
> int drm_fd;
>
> - struct igt_list edids;
> + struct igt_list_head edids;
> struct chamelium_port ports[CHAMELIUM_MAX_PORTS];
> int port_count;
> };
> @@ -2336,7 +2336,7 @@ struct chamelium *chamelium_init(int drm_fd)
>
> memset(chamelium, 0, sizeof(*chamelium));
> chamelium->drm_fd = drm_fd;
> - igt_list_init(&chamelium->edids);
> + IGT_INIT_LIST_HEAD(&chamelium->edids);
>
> /* Setup the libxmlrpc context */
> xmlrpc_env_init(&chamelium->env);
> @@ -2388,7 +2388,7 @@ void chamelium_deinit(struct chamelium *chamelium)
> chamelium_plug(chamelium, &chamelium->ports[i]);
>
> /* Destroy any EDIDs we created to make sure we don't leak them */
> - igt_list_for_each_safe(pos, tmp, &chamelium->edids, link) {
> + igt_list_for_each_entry_safe(pos, tmp, &chamelium->edids, link) {
> for (i = 0; i < CHAMELIUM_MAX_PORTS; i++) {
> if (pos->ids[i])
> chamelium_destroy_edid(chamelium, pos->ids[i]);
> diff --git a/lib/igt_core.c b/lib/igt_core.c
> index 7bd5afa5..86ce8af9 100644
> --- a/lib/igt_core.c
> +++ b/lib/igt_core.c
> @@ -278,10 +278,10 @@ static char __current_description[512];
>
> struct description_node {
> char desc[sizeof(__current_description)];
> - struct igt_list link;
> + struct igt_list_head link;
> };
>
> -static struct igt_list subgroup_descriptions;
> +static struct igt_list_head subgroup_descriptions;
>
>
> bool __igt_plain_output = false;
> @@ -797,7 +797,7 @@ static int common_init(int *argc, char **argv,
> int ret = 0;
>
> common_init_env();
> - igt_list_init(&subgroup_descriptions);
> + IGT_INIT_LIST_HEAD(&subgroup_descriptions);
>
> command_str = argv[0];
> if (strrchr(command_str, '/'))
> @@ -1068,7 +1068,7 @@ static void __igt_print_description(const char *subtest_name, const char *file,
>
> printf("SUB %s %s:%d:\n", subtest_name, file, line);
>
> - igt_list_for_each(desc, &subgroup_descriptions, link) {
> + igt_list_for_each_entry(desc, &subgroup_descriptions, link) {
> print_line_wrapping(indent, desc->desc);
> printf("\n");
> has_doc = true;
> diff --git a/lib/igt_dummyload.c b/lib/igt_dummyload.c
> index 6060878d..b9e239db 100644
> --- a/lib/igt_dummyload.c
> +++ b/lib/igt_dummyload.c
> @@ -65,7 +65,7 @@
> static const int BATCH_SIZE = 4096;
> static const int LOOP_START_OFFSET = 64;
>
> -static IGT_LIST(spin_list);
> +static IGT_LIST_HEAD(spin_list);
> static pthread_mutex_t list_lock = PTHREAD_MUTEX_INITIALIZER;
>
> static int
> @@ -464,7 +464,7 @@ void igt_terminate_spins(void)
> struct igt_spin *iter;
>
> pthread_mutex_lock(&list_lock);
> - igt_list_for_each(iter, &spin_list, link)
> + igt_list_for_each_entry(iter, &spin_list, link)
> igt_spin_end(iter);
> pthread_mutex_unlock(&list_lock);
> }
> @@ -474,9 +474,9 @@ void igt_unshare_spins(void)
> struct igt_spin *it, *n;
>
> /* Disable the automatic termination on inherited spinners */
> - igt_list_for_each_safe(it, n, &spin_list, link)
> - igt_list_init(&it->link);
> - igt_list_init(&spin_list);
> + igt_list_for_each_entry_safe(it, n, &spin_list, link)
> + IGT_INIT_LIST_HEAD(&it->link);
> + IGT_INIT_LIST_HEAD(&spin_list);
> }
>
> static uint32_t plug_vgem_handle(struct igt_cork *cork, int fd)
> diff --git a/lib/igt_dummyload.h b/lib/igt_dummyload.h
> index 66837057..421ca183 100644
> --- a/lib/igt_dummyload.h
> +++ b/lib/igt_dummyload.h
> @@ -35,7 +35,7 @@
> typedef struct igt_spin {
> unsigned int handle;
> timer_t timer;
> - struct igt_list link;
> + struct igt_list_head link;
>
> uint32_t *condition;
> uint32_t cmd_precondition;
> diff --git a/lib/igt_kmod.c b/lib/igt_kmod.c
> index c3da4667..f756f80e 100644
> --- a/lib/igt_kmod.c
> +++ b/lib/igt_kmod.c
> @@ -412,11 +412,11 @@ static void kmsg_dump(int fd)
> }
> }
>
> -static void tests_add(struct igt_kselftest_list *tl, struct igt_list *list)
> +static void tests_add(struct igt_kselftest_list *tl, struct igt_list_head *list)
> {
> struct igt_kselftest_list *pos;
>
> - igt_list_for_each(pos, list, link)
> + igt_list_for_each_entry(pos, list, link)
> if (pos->number > tl->number)
> break;
>
> @@ -425,7 +425,7 @@ static void tests_add(struct igt_kselftest_list *tl, struct igt_list *list)
>
> void igt_kselftest_get_tests(struct kmod_module *kmod,
> const char *filter,
> - struct igt_list *tests)
> + struct igt_list_head *tests)
> {
> const char *param_prefix = "igt__";
> const int prefix_len = strlen(param_prefix);
> @@ -568,7 +568,7 @@ void igt_kselftests(const char *module_name,
> const char *filter)
> {
> struct igt_kselftest tst;
> - IGT_LIST(tests);
> + IGT_LIST_HEAD(tests);
> struct igt_kselftest_list *tl, *tn;
>
> if (igt_kselftest_init(&tst, module_name) != 0)
> @@ -578,7 +578,7 @@ void igt_kselftests(const char *module_name,
> igt_require(igt_kselftest_begin(&tst) == 0);
>
> igt_kselftest_get_tests(tst.kmod, filter, &tests);
> - igt_list_for_each_safe(tl, tn, &tests, link) {
> + igt_list_for_each_entry_safe(tl, tn, &tests, link) {
> igt_subtest_f("%s", tl->name)
> igt_kselftest_execute(&tst, tl, options, result);
> free(tl);
> diff --git a/lib/igt_kmod.h b/lib/igt_kmod.h
> index 87d36d40..b15cde46 100644
> --- a/lib/igt_kmod.h
> +++ b/lib/igt_kmod.h
> @@ -49,7 +49,7 @@ struct igt_kselftest {
> };
>
> struct igt_kselftest_list {
> - struct igt_list link;
> + struct igt_list_head link;
> unsigned int number;
> char *name;
> char param[];
> @@ -61,7 +61,7 @@ int igt_kselftest_begin(struct igt_kselftest *tst);
>
> void igt_kselftest_get_tests(struct kmod_module *kmod,
> const char *filter,
> - struct igt_list *tests);
> + struct igt_list_head *tests);
> int igt_kselftest_execute(struct igt_kselftest *tst,
> struct igt_kselftest_list *tl,
> const char *module_options,
> diff --git a/lib/igt_list.c b/lib/igt_list.c
> new file mode 100644
> index 00000000..5e45161b
> --- /dev/null
> +++ b/lib/igt_list.c
> @@ -0,0 +1,66 @@
> +/*
> + * Copyright © 2019 Intel Corporation
> + *
> + * Permission is hereby granted, free of charge, to any person obtaining a
> + * copy of this software and associated documentation files (the "Software"),
> + * to deal in the Software without restriction, including without limitation
> + * the rights to use, copy, modify, merge, publish, distribute, sublicense,
> + * and/or sell copies of the Software, and to permit persons to whom the
> + * Software is furnished to do so, subject to the following conditions:
> + *
> + * The above copyright notice and this permission notice (including the next
> + * paragraph) shall be included in all copies or substantial portions of the
> + * Software.
> + *
> + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
> + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
> + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
> + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
> + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
> + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
> + * IN THE SOFTWARE.
> + *
> + */
> +
> +#include "igt_list.h"
> +
> +void IGT_INIT_LIST_HEAD(struct igt_list_head *list)
> +{
> + list->prev = list;
> + list->next = list;
> +}
> +
> +void igt_list_add(struct igt_list_head *elem, struct igt_list_head *head)
> +{
> + elem->prev = head;
> + elem->next = head->next;
> + head->next = elem;
> + elem->next->prev = elem;
> +}
> +
> +
> +void igt_list_del(struct igt_list_head *elem)
> +{
> + elem->prev->next = elem->next;
> + elem->next->prev = elem->prev;
> + elem->next = NULL;
> + elem->prev = NULL;
> +}
> +
> +int igt_list_length(const struct igt_list_head *head)
> +{
> + struct igt_list_head *e = head->next;
> + int count = 0;
> +
> + while (e != head) {
> + e = e->next;
> + count++;
> + }
> +
> + return count;
> +}
> +
> +bool igt_list_empty(const struct igt_list_head *head)
> +{
> + return head->next == head;
> +}
> diff --git a/lib/igt_list.h b/lib/igt_list.h
> index cadf9dd3..3e139b8a 100644
> --- a/lib/igt_list.h
> +++ b/lib/igt_list.h
> @@ -28,102 +28,100 @@
> #include <stdbool.h>
> #include <stddef.h>
>
> -/*
> - * This list data structure is a verbatim copy from wayland-util.h from the
> - * Wayland project; except that wl_ prefix has been removed.
> +/**
> + * SECTION:igt_list
> + * @short_description: a list implementation inspired by the kernel
> + * @title: IGT List
> + * @include: igt_list.h
> + *
> + * This list data structure mimics the one we can find in the kernel. A few
> + * bonus helpers are provided.
> + *
> + * igt_list is a doubly-linked list where an instance of igt_list_head is a
> + * head sentinel and has to be initialized.
> + *
> + * Example usage:
> + *
> + * |[
> + * struct igt_list_head foo_head;
> + *
> + * struct element {
> + * int foo;
> + * struct igt_list_head link;
> + * };
> + *
> + * struct element e1, e2, e3;
> + *
> + * IGT_INIT_LIST_HEAD(&foo_head);
> + * igt_list_add(&e1.link, &foo_head); // e1 is the first element
> + * igt_list_add(&e2.link, &foo_head); // e2 is now the first element
> + * igt_list_add(&e3.link, &e2.link); // insert e3 after e2
> + *
> + * printf("list length: %d\n", igt_list_length(&foo_head));
> + *
> + * struct element *iter;
> + * igt_list_for_each_entry(iter, &foo_head, link) {
> + * printf(" %d\n", iter->foo);
> + * }
> + * ]|
> */
>
> -struct igt_list {
> - struct igt_list *prev;
> - struct igt_list *next;
> +struct igt_list_head {
> + struct igt_list_head *prev;
> + struct igt_list_head *next;
> };
>
> -#define __IGT_INIT_LIST(name) { &(name), &(name) }
> -#define IGT_LIST(name) struct igt_list name = __IGT_INIT_LIST(name)
>
> -static inline void igt_list_init(struct igt_list *list)
> -{
> - list->prev = list;
> - list->next = list;
> -}
> +void IGT_INIT_LIST_HEAD(struct igt_list_head *head);
> +void igt_list_add(struct igt_list_head *elem, struct igt_list_head *head);
> +void igt_list_del(struct igt_list_head *elem);
> +int igt_list_length(const struct igt_list_head *head);
> +bool igt_list_empty(const struct igt_list_head *head);
>
> -static inline void __igt_list_add(struct igt_list *list,
> - struct igt_list *prev,
> - struct igt_list *next)
> -{
> - next->prev = list;
> - list->next = next;
> - list->prev = prev;
> - prev->next = list;
> -}
> +#define igt_container_of(ptr, sample, member) \
> + (__typeof__(sample))((char *)(ptr) - \
> + offsetof(__typeof__(*sample), member))
>
> -static inline void igt_list_add(struct igt_list *elm, struct igt_list *list)
> -{
> - __igt_list_add(elm, list, list->next);
> -}
> -
> -static inline void igt_list_add_tail(struct igt_list *elm,
> - struct igt_list *list)
> -{
> - __igt_list_add(elm, list->prev, list);
> -}
> -
> -static inline void __igt_list_del(struct igt_list *prev, struct igt_list *next)
> -{
> - next->prev = prev;
> - prev->next = next;
> -}
> -
> -static inline void igt_list_del(struct igt_list *elm)
> -{
> - __igt_list_del(elm->prev, elm->next);
> -}
> -
> -static inline void igt_list_move(struct igt_list *elm, struct igt_list *list)
> -{
> - igt_list_del(elm);
> - igt_list_add(elm, list);
> -}
> -
> -static inline void igt_list_move_tail(struct igt_list *elm,
> - struct igt_list *list)
> -{
> - igt_list_del(elm);
> - igt_list_add_tail(elm, list);
> -}
> +#define igt_list_for_each_entry(pos, head, member) \
> + for (pos = igt_container_of((head)->next, pos, member); \
> + &pos->member != (head); \
> + pos = igt_container_of((pos)->member.next, pos, member))
> +
> +/**
> + * igt_list_for_each_safe
> + *
> + * Safe against removel of the *current* list element. To achive this it

removal
^

> + * requires an extra helper variable `tmp` with the same type as `pos`.
> + */
> +#define igt_list_for_each_entry_safe(pos, tmp, head, member) \
> + for (pos = igt_container_of((head)->next, pos, member), \

That one \ is trying to escape.

Otherwise LGTM. Straightforward code changes, and I don't have strong
feelings as to which list implementation to chase, but definitely we
should choose and not lie what it is.

Reviewed-by: Petri Latvala <petri.latvala@intel.com>