Linux kernel mirror (for testing)
git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git
tjh.dev
kernel
os
linux
1#ifndef LLIST_H
2#define LLIST_H
3/*
4 * Lock-less NULL terminated single linked list
5 *
6 * If there are multiple producers and multiple consumers, llist_add
7 * can be used in producers and llist_del_all can be used in
8 * consumers. They can work simultaneously without lock. But
9 * llist_del_first can not be used here. Because llist_del_first
10 * depends on list->first->next does not changed if list->first is not
11 * changed during its operation, but llist_del_first, llist_add,
12 * llist_add (or llist_del_all, llist_add, llist_add) sequence in
13 * another consumer may violate that.
14 *
15 * If there are multiple producers and one consumer, llist_add can be
16 * used in producers and llist_del_all or llist_del_first can be used
17 * in the consumer.
18 *
19 * This can be summarized as follow:
20 *
21 * | add | del_first | del_all
22 * add | - | - | -
23 * del_first | | L | L
24 * del_all | | | -
25 *
26 * Where "-" stands for no lock is needed, while "L" stands for lock
27 * is needed.
28 *
29 * The list entries deleted via llist_del_all can be traversed with
30 * traversing function such as llist_for_each etc. But the list
31 * entries can not be traversed safely before deleted from the list.
32 * The order of deleted entries is from the newest to the oldest added
33 * one. If you want to traverse from the oldest to the newest, you
34 * must reverse the order by yourself before traversing.
35 *
36 * The basic atomic operation of this list is cmpxchg on long. On
37 * architectures that don't have NMI-safe cmpxchg implementation, the
38 * list can NOT be used in NMI handler. So code uses the list in NMI
39 * handler should depend on CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG.
40 */
41
42struct llist_head {
43 struct llist_node *first;
44};
45
46struct llist_node {
47 struct llist_node *next;
48};
49
50#define LLIST_HEAD_INIT(name) { NULL }
51#define LLIST_HEAD(name) struct llist_head name = LLIST_HEAD_INIT(name)
52
53/**
54 * init_llist_head - initialize lock-less list head
55 * @head: the head for your lock-less list
56 */
57static inline void init_llist_head(struct llist_head *list)
58{
59 list->first = NULL;
60}
61
62/**
63 * llist_entry - get the struct of this entry
64 * @ptr: the &struct llist_node pointer.
65 * @type: the type of the struct this is embedded in.
66 * @member: the name of the llist_node within the struct.
67 */
68#define llist_entry(ptr, type, member) \
69 container_of(ptr, type, member)
70
71/**
72 * llist_for_each - iterate over some deleted entries of a lock-less list
73 * @pos: the &struct llist_node to use as a loop cursor
74 * @node: the first entry of deleted list entries
75 *
76 * In general, some entries of the lock-less list can be traversed
77 * safely only after being deleted from list, so start with an entry
78 * instead of list head.
79 *
80 * If being used on entries deleted from lock-less list directly, the
81 * traverse order is from the newest to the oldest added entry. If
82 * you want to traverse from the oldest to the newest, you must
83 * reverse the order by yourself before traversing.
84 */
85#define llist_for_each(pos, node) \
86 for ((pos) = (node); pos; (pos) = (pos)->next)
87
88/**
89 * llist_for_each_entry - iterate over some deleted entries of lock-less list of given type
90 * @pos: the type * to use as a loop cursor.
91 * @node: the fist entry of deleted list entries.
92 * @member: the name of the llist_node with the struct.
93 *
94 * In general, some entries of the lock-less list can be traversed
95 * safely only after being removed from list, so start with an entry
96 * instead of list head.
97 *
98 * If being used on entries deleted from lock-less list directly, the
99 * traverse order is from the newest to the oldest added entry. If
100 * you want to traverse from the oldest to the newest, you must
101 * reverse the order by yourself before traversing.
102 */
103#define llist_for_each_entry(pos, node, member) \
104 for ((pos) = llist_entry((node), typeof(*(pos)), member); \
105 &(pos)->member != NULL; \
106 (pos) = llist_entry((pos)->member.next, typeof(*(pos)), member))
107
108/**
109 * llist_empty - tests whether a lock-less list is empty
110 * @head: the list to test
111 *
112 * Not guaranteed to be accurate or up to date. Just a quick way to
113 * test whether the list is empty without deleting something from the
114 * list.
115 */
116static inline int llist_empty(const struct llist_head *head)
117{
118 return ACCESS_ONCE(head->first) == NULL;
119}
120
121void llist_add(struct llist_node *new, struct llist_head *head);
122void llist_add_batch(struct llist_node *new_first, struct llist_node *new_last,
123 struct llist_head *head);
124struct llist_node *llist_del_first(struct llist_head *head);
125struct llist_node *llist_del_all(struct llist_head *head);
126#endif /* LLIST_H */