From b59abc699f5426cda5954a7bea8eed0d40852864 Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Fri, 28 Oct 2022 09:39:19 -0400 Subject: [PATCH] Circular linked-list implementation Signed-off-by: Mathieu Desnoyers --- include/side/macros.h | 14 ++++++++++ src/Makefile | 2 +- src/list.h | 62 +++++++++++++++++++++++++++++++++++++++++++ src/side.c | 3 +++ 4 files changed, 80 insertions(+), 1 deletion(-) create mode 100644 src/list.h diff --git a/include/side/macros.h b/include/side/macros.h index 7b97698..af6ba11 100644 --- a/include/side/macros.h +++ b/include/side/macros.h @@ -27,4 +27,18 @@ #define SIDE_PARAM(...) __VA_ARGS__ +/* + * side_container_of - Get the address of an object containing a field. + * + * @ptr: pointer to the field. + * @type: type of the object. + * @member: name of the field within the object. + */ +#define side_container_of(ptr, type, member) \ + __extension__ \ + ({ \ + const __typeof__(((type *) NULL)->member) * __ptr = (ptr); \ + (type *)((char *)__ptr - offsetof(type, member)); \ + }) + #endif /* _SIDE_MACROS_H */ diff --git a/src/Makefile b/src/Makefile index acc2f90..a4b38aa 100644 --- a/src/Makefile +++ b/src/Makefile @@ -1,6 +1,6 @@ all: test -HEADERS = ../include/side/trace.h ../include/side/macros.h rcu.h smp.h +HEADERS = ../include/side/trace.h ../include/side/macros.h rcu.h smp.h list.h CFLAGS = -g -O2 -Wall CPPFLAGS = -I../include/ -D_GNU_SOURCE diff --git a/src/list.h b/src/list.h new file mode 100644 index 0000000..8717bef --- /dev/null +++ b/src/list.h @@ -0,0 +1,62 @@ +// SPDX-License-Identifier: MIT +/* + * Copyright 2022 Mathieu Desnoyers + */ + +#ifndef _SIDE_LIST_H +#define _SIDE_LIST_H + +struct side_list_node { + struct side_list_node *next; + struct side_list_node *prev; +}; + +struct side_list_head { + struct side_list_node node; +}; + +#define DEFINE_SIDE_LIST_HEAD(_identifier) \ + struct side_list_head _identifier = { \ + .node = { \ + .next = &(_identifier).node, \ + .prev = &(_identifier).node, \ + }, \ + } + +static inline +void side_list_insert_node_tail(struct side_list_head *head, struct side_list_node *node) +{ + node->next = &head->node; + node->prev = head->node.prev; + node->prev->next = node; + head->node.prev = node; +} + +static inline +void side_list_insert_node_head(struct side_list_head *head, struct side_list_node *node) +{ + node->next = head->node.next; + node->prev = &head->node; + node->next->prev = node; + head->node.next = node; +} + +static inline +void side_list_remove_node(struct side_list_node *node) +{ + node->next->prev = node->prev; + node->prev->next = node->next; +} + +#define side_list_for_each_entry(_entry, _head, _member) \ + for ((_entry) = side_container_of((_head)->node.next, __typeof__(*(_entry)), _member); \ + &(_entry)->member != &head->node; \ + (_entry) = side_container_of((_entry)->member.next, __typeof__(*(_entry)), _member)) + +/* List iteration, safe against node reclaim while iterating. */ +#define side_list_for_each_entry_safe(_entry, _next_entry, _head, _member) \ + for ((_entry) = side_container_of((_head)->node.next, __typeof__(*(_entry)), _member), (_next_entry) = (_entry)->next; \ + &(_entry)->member != &head->node; \ + (_entry) = (_next_entry)->next, (_next_entry) = (_entry)->next) + +#endif /* _SIDE_LIST_H */ diff --git a/src/side.c b/src/side.c index acc8db3..0460860 100644 --- a/src/side.c +++ b/src/side.c @@ -8,6 +8,7 @@ #include "tracer.h" #include "rcu.h" +#include "list.h" /* Top 8 bits reserved for kernel tracer use. */ #define SIDE_EVENT_ENABLED_KERNEL_MASK 0xFF000000 @@ -25,6 +26,8 @@ static bool initialized; static pthread_mutex_t side_lock = PTHREAD_MUTEX_INITIALIZER; +static DEFINE_SIDE_LIST_HEAD(side_list); + static void side_init(void) __attribute__((constructor)); -- 2.34.1