From ebbc636e167941e372bfeac6117c823a52f885a2 Mon Sep 17 00:00:00 2001 From: "Matthew Wilcox (Oracle)" Date: Wed, 9 Jun 2021 15:48:06 -0400 Subject: [PATCH] Add wait lists None of the existing lists do exactly what I want; a single pointer for the head and O(1) access to both the head and the tail of the list. So introduce yet another variant of doubly linked lists. Also add a test-suite. Signed-off-by: Matthew Wilcox (Oracle) --- include/linux/list.h | 161 ++++++++++++++++++++ include/linux/types.h | 8 + tools/include/linux/types.h | 8 + tools/testing/lists/.gitignore | 1 + tools/testing/lists/Makefile | 5 + tools/testing/lists/wlist.c | 270 +++++++++++++++++++++++++++++++++ 6 files changed, 453 insertions(+) create mode 100644 tools/testing/lists/.gitignore create mode 100644 tools/testing/lists/Makefile create mode 100644 tools/testing/lists/wlist.c diff --git a/include/linux/list.h b/include/linux/list.h index f2af4b4aa4e9..74c02af292a7 100644 --- a/include/linux/list.h +++ b/include/linux/list.h @@ -3,6 +3,7 @@ #define _LINUX_LIST_H #include +#include #include #include #include @@ -1025,4 +1026,164 @@ static inline void hlist_move_list(struct hlist_head *old, pos && ({ n = pos->member.next; 1; }); \ pos = hlist_entry_safe(n, typeof(*pos), member)) +/* + * Lists optimised for wait queues, where we should normally add to the tail + * and remove from the head. The head pointer points to the first element in + * the list. The first element in the list has a 'prev' pointer which points + * to the last element in the list. The last element in the list has a 'next' + * pointer which is NULL. This reduces memory consumption in the head while + * giving us O(1) access to the head and tail of the list, and allowing + * deletions from the middle in O(1). + */ + +#define WLIST_HEAD_INIT { .first = NULL } +#define WLIST_HEAD(name) struct wlist_head name = { .first = NULL } +#define INIT_WLIST_HEAD(ptr) ((ptr)->first = NULL) +static inline void INIT_WLIST_NODE(struct wlist_node *w) +{ + w->next = NULL; + w->prev = NULL; +} + +static inline bool wlist_empty(const struct wlist_head *h) +{ + return !READ_ONCE(h->first); +} + +static inline bool wlist_is_singular(const struct wlist_head *head) +{ + const struct wlist_node *first = READ_ONCE(head->first); + + return first && first->prev == first; +} + +static inline bool wlist_deleted(const struct wlist_node *node) +{ + return !READ_ONCE(node->prev); +} + +/** + * wlist_add - Adds a waiter to the tail of the wait list. + * @head: Wait list head. + * @node: New entry to add. + * + * Return: true if the queue was empty. + */ +static inline bool wlist_add(struct wlist_head *head, struct wlist_node *node) +{ + struct wlist_node *first = head->first; + + node->next = NULL; + if (first) { + struct wlist_node *last = first->prev; + node->prev = last; + first->prev = node; + last->next = node; + return false; + } else { + node->prev = node; + head->first = node; + return true; + } +} + +/* Returns true if the queue was empty */ +static inline bool wlist_add_head(struct wlist_head *head, + struct wlist_node *node) +{ + struct wlist_node *first = head->first; + + WRITE_ONCE(node->next, first); + WRITE_ONCE(head->first, node); + if (first) { + node->prev = first->prev; + first->prev = node; + return false; + } else { + node->prev = node; + return true; + } +} + +static inline struct wlist_node *__wlist_del_first(struct wlist_head *head, + struct wlist_node *node) +{ + struct wlist_node *next = node->next; + + if (next) + next->prev = node->prev; + node->prev = NULL; + WRITE_ONCE(head->first, next); + return node; +} + +static inline struct wlist_node *wlist_del_first(struct wlist_head *head) +{ + return __wlist_del_first(head, head->first); +} + +#define wlist_del_first_entry(head, type, member) \ + hlist_entry(wlist_del_first(head), type, member) + +/* Returns true if the queue is now empty */ +static inline bool wlist_del(struct wlist_head *head, struct wlist_node *node) +{ + struct wlist_node *next = node->next; + struct wlist_node *prev; + struct wlist_node *first = head->first; + + if (first == node) { + __wlist_del_first(head, first); + return (next == NULL); + } + + prev = node->prev; + if (next) + next->prev = prev; + node->prev = NULL; + WRITE_ONCE(prev->next, next); + if (!next) + first->prev = prev; + else + next->prev = prev; + return false; +} + +static inline void wlist_move(struct wlist_head *oldh, + struct wlist_node *node, struct wlist_head *newh) +{ + wlist_del(oldh, node); + wlist_add(newh, node); +} + +#define wlist_first_entry(head, type, member) \ + hlist_entry_safe((head)->first, type, member) + +/** + * wlist_for_each_entry - iterate over list of given type + * @pos: the type * to use as a loop cursor. + * @head: the head for your list. + * @member: the name of the wlist_node within the struct. + */ +#define wlist_for_each_entry hlist_for_each_entry + +/** + * wlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry + * @pos: the type * to use as a loop cursor. + * @n: a &struct wlist_node to use as temporary storage + * @head: the head for your list. + * @member: the name of the wlist_node within the struct. + */ +#define wlist_for_each_entry_safe hlist_for_each_entry_safe + +/** + * wlist_for_each_entry_from_safe - iterate over a wlist safe from removal of list entries continuing from current point + * @pos: the type * to use as a loop cursor. + * @member: the name of the wlist_node within the struct. + */ +#define wlist_for_each_entry_from_safe(pos, n, member) \ + for (; \ + pos && ({ n = pos->member.next; 1; }); \ + pos = hlist_entry_safe(n, typeof(*pos), member)) + #endif diff --git a/include/linux/types.h b/include/linux/types.h index ac825ad90e44..65ee9a65f2ff 100644 --- a/include/linux/types.h +++ b/include/linux/types.h @@ -187,6 +187,14 @@ struct hlist_node { struct hlist_node *next, **pprev; }; +struct wlist_head { + struct wlist_node *first; +}; + +struct wlist_node { + struct wlist_node *next, *prev; +}; + struct ustat { __kernel_daddr_t f_tfree; #ifdef CONFIG_ARCH_32BIT_USTAT_F_TINODE diff --git a/tools/include/linux/types.h b/tools/include/linux/types.h index 6e14a533ab4e..68711a9dc016 100644 --- a/tools/include/linux/types.h +++ b/tools/include/linux/types.h @@ -84,4 +84,12 @@ struct hlist_node { struct hlist_node *next, **pprev; }; +struct wlist_head { + struct wlist_node *first; +}; + +struct wlist_node { + struct wlist_node *next, *prev; +}; + #endif /* _TOOLS_LINUX_TYPES_H_ */ diff --git a/tools/testing/lists/.gitignore b/tools/testing/lists/.gitignore new file mode 100644 index 000000000000..c9465dec53b6 --- /dev/null +++ b/tools/testing/lists/.gitignore @@ -0,0 +1 @@ +wlist diff --git a/tools/testing/lists/Makefile b/tools/testing/lists/Makefile new file mode 100644 index 000000000000..868cb59b2583 --- /dev/null +++ b/tools/testing/lists/Makefile @@ -0,0 +1,5 @@ +CFLAGS=-W -Wall -Wno-unused-parameter -O2 -g -I../../include + +wlist: wlist.o + gcc -o wlist $< +wlist.o: ../../../include/linux/list.h diff --git a/tools/testing/lists/wlist.c b/tools/testing/lists/wlist.c new file mode 100644 index 000000000000..af2c2ae0e6e1 --- /dev/null +++ b/tools/testing/lists/wlist.c @@ -0,0 +1,270 @@ +#include +#include +#include "../../../include/linux/list.h" + +#include +#include +#include + +int verbose = 0; + +#define printv(level, fmt, ...) \ + if (verbose >= level) \ + printf(fmt, ##__VA_ARGS__) + +struct item { + int i; + struct wlist_node list; +}; + +struct item *item_create(int i) +{ + struct item *item = malloc(sizeof(*item)); + item->i = i; + INIT_WLIST_NODE(&item->list); + printv(2, "item %d allocated at %p\n", i, item); + return item; +} + +/* Check that an empty list behaves the way we want it to */ +void wlist_test0(struct wlist_head *wlist) +{ + struct item *item; + struct wlist_node *next; + + assert(wlist_empty(wlist)); + assert(wlist_first_entry(wlist, struct item, list) == NULL); + wlist_for_each_entry(item, wlist, list) + assert(0); + wlist_for_each_entry_safe(item, next, wlist, list) + assert(0); + printv(1, "test0 passed\n"); +} + +void verify_singleton(struct wlist_head *wlist) +{ + assert(wlist->first != NULL); + assert(wlist->first->next == NULL); + assert(wlist->first->prev == wlist->first); +} + +void verify_doubleton(struct wlist_head *wlist) +{ + assert(wlist->first != NULL); + assert(wlist->first->next == wlist->first->prev); + assert(wlist->first->prev->next == NULL); + assert(wlist->first->prev->prev == wlist->first); +} + +void wlist_test1(struct wlist_head *wlist) +{ + int i; + struct item *item; + struct wlist_node *next; + struct item *item0 = item_create(0); + + assert(wlist_empty(wlist)); + + assert(wlist_add(wlist, &item0->list)); + assert(!wlist_empty(wlist)); + verify_singleton(wlist); + assert(wlist_first_entry(wlist, struct item, list) == item0); + i = 0; + wlist_for_each_entry(item, wlist, list) + assert(item->i == i++); + assert(i == 1); + + wlist_for_each_entry_safe(item, next, wlist, list) + wlist_del(wlist, &item->list); + + assert(wlist_deleted(&item0->list)); + assert(wlist_empty(wlist)); + + assert(wlist_add_head(wlist, &item0->list)); + verify_singleton(wlist); + item = item0; + i = 0; + wlist_for_each_entry_from_safe(item, next, list) + assert(item->i == i++); + assert(i == 1); + wlist_for_each_entry_from_safe(item, next, list) + assert(0); + + item = item0; + wlist_for_each_entry_from_safe(item, next, list) + wlist_del(wlist, &item->list); + assert(wlist_empty(wlist)); + + free(item0); + printv(1, "test1 passed\n"); +} + +void wlist_test2(struct wlist_head *wlist) +{ + int i; + struct item *item; + struct wlist_node *next; + struct item *item0 = item_create(0); + struct item *item1 = item_create(1); + + assert(wlist_empty(wlist)); + + assert(wlist_add(wlist, &item0->list)); + assert(wlist_first_entry(wlist, struct item, list) == item0); + assert(!wlist_add(wlist, &item1->list)); + assert(!wlist_empty(wlist)); + verify_doubleton(wlist); + assert(wlist_first_entry(wlist, struct item, list) == item0); + i = 0; + wlist_for_each_entry(item, wlist, list) + assert(item->i == i++); + assert(i == 2); + + assert(!wlist_del(wlist, &item0->list)); + verify_singleton(wlist); + assert(wlist_first_entry(wlist, struct item, list) == item1); + i = 1; + wlist_for_each_entry(item, wlist, list) + assert(item->i == i++); + assert(i == 2); + + assert(wlist_del(wlist, &item1->list)); + assert(wlist_empty(wlist)); + + assert(wlist_add_head(wlist, &item1->list)); + assert(!wlist_add_head(wlist, &item0->list)); + verify_doubleton(wlist); + i = 0; + wlist_for_each_entry(item, wlist, list) + assert(item->i == i++); + assert(i == 2); + + assert(!wlist_del(wlist, &item1->list)); + verify_singleton(wlist); + i = 0; + wlist_for_each_entry(item, wlist, list) + assert(item->i == i++); + assert(i == 1); + assert(wlist_del(wlist, &item0->list)); + + assert(wlist_add(wlist, &item0->list)); + assert(!wlist_add(wlist, &item1->list)); + wlist_for_each_entry_safe(item, next, wlist, list) + wlist_del(wlist, &item->list); + assert(wlist_empty(wlist)); + + free(item0); + free(item1); + printv(1, "test2 passed\n"); +} + +void wlist_test3(struct wlist_head *wlist) +{ + int i; + struct item *item; + struct wlist_node *next; + struct item *item0 = item_create(0); + struct item *item1 = item_create(1); + struct item *item2 = item_create(2); + + assert(wlist_empty(wlist)); + + assert(wlist_add(wlist, &item0->list)); + assert(!wlist_add(wlist, &item1->list)); + assert(!wlist_add(wlist, &item2->list)); + assert(!wlist_empty(wlist)); + assert(wlist_first_entry(wlist, struct item, list) == item0); + i = 0; + wlist_for_each_entry(item, wlist, list) + assert(item->i == i++); + assert(i == 3); + + assert(!wlist_del(wlist, &item0->list)); + verify_doubleton(wlist); + assert(wlist_first_entry(wlist, struct item, list) == item1); + i = 1; + wlist_for_each_entry(item, wlist, list) + assert(item->i == i++); + assert(i == 3); + + assert(!wlist_del(wlist, &item1->list)); + verify_singleton(wlist); + assert(wlist_first_entry(wlist, struct item, list) == item2); + assert(wlist_del(wlist, &item2->list)); + assert(wlist_empty(wlist)); + + assert(wlist_add(wlist, &item0->list)); + assert(!wlist_add(wlist, &item1->list)); + assert(!wlist_add(wlist, &item2->list)); + assert(!wlist_del(wlist, &item1->list)); + verify_doubleton(wlist); + assert(wlist_first_entry(wlist, struct item, list) == item0); + i = 0; + wlist_for_each_entry(item, wlist, list) { + assert(item->i == i); + i += 2; + } + assert(i == 4); + assert(!wlist_del(wlist, &item0->list)); + assert(wlist_del(wlist, &item2->list)); + assert(wlist_empty(wlist)); + + assert(wlist_add(wlist, &item0->list)); + assert(!wlist_add(wlist, &item1->list)); + assert(!wlist_add(wlist, &item2->list)); + assert(!wlist_del(wlist, &item2->list)); + verify_doubleton(wlist); + assert(wlist_first_entry(wlist, struct item, list) == item0); + i = 0; + wlist_for_each_entry(item, wlist, list) + assert(item->i == i++); + assert(i == 2); + assert(!wlist_del(wlist, &item0->list)); + assert(wlist_del(wlist, &item1->list)); + assert(wlist_empty(wlist)); + + assert(wlist_add(wlist, &item0->list)); + assert(!wlist_add(wlist, &item1->list)); + assert(!wlist_add(wlist, &item2->list)); + item = item0; + wlist_for_each_entry_from_safe(item, next, list) + wlist_del(wlist, &item->list); + assert(wlist_empty(wlist)); + + assert(wlist_add(wlist, &item0->list)); + assert(!wlist_add(wlist, &item1->list)); + assert(!wlist_add(wlist, &item2->list)); + wlist_for_each_entry_safe(item, next, wlist, list) + wlist_del(wlist, &item->list); + assert(wlist_empty(wlist)); + + assert(wlist_add(wlist, &item0->list)); + assert(!wlist_add(wlist, &item1->list)); + assert(!wlist_add(wlist, &item2->list)); + assert(wlist_del_first(wlist) == &item0->list); + assert(wlist_del_first(wlist) == &item1->list); + assert(wlist_del_first(wlist) == &item2->list); + assert(wlist_empty(wlist)); + + free(item0); + free(item1); + free(item2); + printv(1, "test3 passed\n"); +} + +int main(int argc, char **argv) +{ + int opt; + WLIST_HEAD(wlist); + + while ((opt = getopt(argc, argv, "v")) != -1) { + if (opt == 'v') + verbose++; + } + + wlist_test0(&wlist); + wlist_test1(&wlist); + wlist_test2(&wlist); + wlist_test3(&wlist); + return 0; +} -- 2.49.0