Huang Ying | f49f23a | 2011-07-13 13:14:23 +0800 | [diff] [blame] | 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 |
Ingo Molnar | 2c30245 | 2011-10-04 12:43:11 +0200 | [diff] [blame] | 38 | * list can NOT be used in NMI handlers. So code that uses the list in |
| 39 | * an NMI handler should depend on CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG. |
Huang Ying | 1230db8 | 2011-09-08 14:00:42 +0800 | [diff] [blame] | 40 | * |
| 41 | * Copyright 2010,2011 Intel Corp. |
| 42 | * Author: Huang Ying <ying.huang@intel.com> |
| 43 | * |
| 44 | * This program is free software; you can redistribute it and/or |
| 45 | * modify it under the terms of the GNU General Public License version |
| 46 | * 2 as published by the Free Software Foundation; |
| 47 | * |
| 48 | * This program is distributed in the hope that it will be useful, |
| 49 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 50 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| 51 | * GNU General Public License for more details. |
| 52 | * |
| 53 | * You should have received a copy of the GNU General Public License |
| 54 | * along with this program; if not, write to the Free Software |
| 55 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA |
Huang Ying | f49f23a | 2011-07-13 13:14:23 +0800 | [diff] [blame] | 56 | */ |
| 57 | |
Will Deacon | cd074ae | 2015-08-06 17:54:43 +0100 | [diff] [blame] | 58 | #include <linux/atomic.h> |
Huang Ying | 1230db8 | 2011-09-08 14:00:42 +0800 | [diff] [blame] | 59 | #include <linux/kernel.h> |
Huang Ying | 1230db8 | 2011-09-08 14:00:42 +0800 | [diff] [blame] | 60 | |
Huang Ying | f49f23a | 2011-07-13 13:14:23 +0800 | [diff] [blame] | 61 | struct llist_head { |
| 62 | struct llist_node *first; |
| 63 | }; |
| 64 | |
| 65 | struct llist_node { |
| 66 | struct llist_node *next; |
| 67 | }; |
| 68 | |
| 69 | #define LLIST_HEAD_INIT(name) { NULL } |
| 70 | #define LLIST_HEAD(name) struct llist_head name = LLIST_HEAD_INIT(name) |
| 71 | |
| 72 | /** |
| 73 | * init_llist_head - initialize lock-less list head |
| 74 | * @head: the head for your lock-less list |
| 75 | */ |
| 76 | static inline void init_llist_head(struct llist_head *list) |
| 77 | { |
| 78 | list->first = NULL; |
| 79 | } |
| 80 | |
| 81 | /** |
| 82 | * llist_entry - get the struct of this entry |
| 83 | * @ptr: the &struct llist_node pointer. |
| 84 | * @type: the type of the struct this is embedded in. |
| 85 | * @member: the name of the llist_node within the struct. |
| 86 | */ |
| 87 | #define llist_entry(ptr, type, member) \ |
| 88 | container_of(ptr, type, member) |
| 89 | |
| 90 | /** |
Alexander Potapenko | ff0a112 | 2017-07-19 20:27:30 +0200 | [diff] [blame] | 91 | * member_address_is_nonnull - check whether the member address is not NULL |
| 92 | * @ptr: the object pointer (struct type * that contains the llist_node) |
| 93 | * @member: the name of the llist_node within the struct. |
| 94 | * |
| 95 | * This macro is conceptually the same as |
| 96 | * &ptr->member != NULL |
| 97 | * but it works around the fact that compilers can decide that taking a member |
| 98 | * address is never a NULL pointer. |
| 99 | * |
| 100 | * Real objects that start at a high address and have a member at NULL are |
| 101 | * unlikely to exist, but such pointers may be returned e.g. by the |
| 102 | * container_of() macro. |
| 103 | */ |
| 104 | #define member_address_is_nonnull(ptr, member) \ |
| 105 | ((uintptr_t)(ptr) + offsetof(typeof(*(ptr)), member) != 0) |
| 106 | |
| 107 | /** |
Huang Ying | f49f23a | 2011-07-13 13:14:23 +0800 | [diff] [blame] | 108 | * llist_for_each - iterate over some deleted entries of a lock-less list |
| 109 | * @pos: the &struct llist_node to use as a loop cursor |
| 110 | * @node: the first entry of deleted list entries |
| 111 | * |
| 112 | * In general, some entries of the lock-less list can be traversed |
| 113 | * safely only after being deleted from list, so start with an entry |
| 114 | * instead of list head. |
| 115 | * |
| 116 | * If being used on entries deleted from lock-less list directly, the |
| 117 | * traverse order is from the newest to the oldest added entry. If |
| 118 | * you want to traverse from the oldest to the newest, you must |
| 119 | * reverse the order by yourself before traversing. |
| 120 | */ |
| 121 | #define llist_for_each(pos, node) \ |
| 122 | for ((pos) = (node); pos; (pos) = (pos)->next) |
| 123 | |
| 124 | /** |
| 125 | * llist_for_each_entry - iterate over some deleted entries of lock-less list of given type |
| 126 | * @pos: the type * to use as a loop cursor. |
| 127 | * @node: the fist entry of deleted list entries. |
| 128 | * @member: the name of the llist_node with the struct. |
| 129 | * |
| 130 | * In general, some entries of the lock-less list can be traversed |
| 131 | * safely only after being removed from list, so start with an entry |
| 132 | * instead of list head. |
| 133 | * |
| 134 | * If being used on entries deleted from lock-less list directly, the |
| 135 | * traverse order is from the newest to the oldest added entry. If |
| 136 | * you want to traverse from the oldest to the newest, you must |
| 137 | * reverse the order by yourself before traversing. |
| 138 | */ |
| 139 | #define llist_for_each_entry(pos, node, member) \ |
| 140 | for ((pos) = llist_entry((node), typeof(*(pos)), member); \ |
Alexander Potapenko | ff0a112 | 2017-07-19 20:27:30 +0200 | [diff] [blame] | 141 | member_address_is_nonnull(pos, member); \ |
Huang Ying | f49f23a | 2011-07-13 13:14:23 +0800 | [diff] [blame] | 142 | (pos) = llist_entry((pos)->member.next, typeof(*(pos)), member)) |
| 143 | |
| 144 | /** |
Peter Hurley | 809850b | 2013-06-15 09:36:06 -0400 | [diff] [blame] | 145 | * llist_for_each_entry_safe - iterate over some deleted entries of lock-less list of given type |
| 146 | * safe against removal of list entry |
| 147 | * @pos: the type * to use as a loop cursor. |
| 148 | * @n: another type * to use as temporary storage |
| 149 | * @node: the first entry of deleted list entries. |
| 150 | * @member: the name of the llist_node with the struct. |
| 151 | * |
| 152 | * In general, some entries of the lock-less list can be traversed |
| 153 | * safely only after being removed from list, so start with an entry |
| 154 | * instead of list head. |
| 155 | * |
| 156 | * If being used on entries deleted from lock-less list directly, the |
| 157 | * traverse order is from the newest to the oldest added entry. If |
| 158 | * you want to traverse from the oldest to the newest, you must |
| 159 | * reverse the order by yourself before traversing. |
| 160 | */ |
| 161 | #define llist_for_each_entry_safe(pos, n, node, member) \ |
| 162 | for (pos = llist_entry((node), typeof(*pos), member); \ |
Alexander Potapenko | ff0a112 | 2017-07-19 20:27:30 +0200 | [diff] [blame] | 163 | member_address_is_nonnull(pos, member) && \ |
Peter Hurley | 809850b | 2013-06-15 09:36:06 -0400 | [diff] [blame] | 164 | (n = llist_entry(pos->member.next, typeof(*n), member), true); \ |
| 165 | pos = n) |
| 166 | |
| 167 | /** |
Huang Ying | f49f23a | 2011-07-13 13:14:23 +0800 | [diff] [blame] | 168 | * llist_empty - tests whether a lock-less list is empty |
| 169 | * @head: the list to test |
| 170 | * |
| 171 | * Not guaranteed to be accurate or up to date. Just a quick way to |
| 172 | * test whether the list is empty without deleting something from the |
| 173 | * list. |
| 174 | */ |
Huang Ying | 1230db8 | 2011-09-08 14:00:42 +0800 | [diff] [blame] | 175 | static inline bool llist_empty(const struct llist_head *head) |
Huang Ying | f49f23a | 2011-07-13 13:14:23 +0800 | [diff] [blame] | 176 | { |
| 177 | return ACCESS_ONCE(head->first) == NULL; |
| 178 | } |
| 179 | |
Peter Zijlstra | 924f8f5 | 2011-09-12 13:12:28 +0200 | [diff] [blame] | 180 | static inline struct llist_node *llist_next(struct llist_node *node) |
| 181 | { |
| 182 | return node->next; |
| 183 | } |
| 184 | |
Oleg Nesterov | e9a17bd | 2013-07-08 14:24:19 -0700 | [diff] [blame] | 185 | extern bool llist_add_batch(struct llist_node *new_first, |
| 186 | struct llist_node *new_last, |
| 187 | struct llist_head *head); |
Huang Ying | 1230db8 | 2011-09-08 14:00:42 +0800 | [diff] [blame] | 188 | /** |
| 189 | * llist_add - add a new entry |
| 190 | * @new: new entry to be added |
| 191 | * @head: the head for your lock-less list |
Huang Ying | 781f7fd | 2011-09-08 14:00:45 +0800 | [diff] [blame] | 192 | * |
Andrew Morton | fc23af3 | 2011-10-31 17:13:08 -0700 | [diff] [blame] | 193 | * Returns true if the list was empty prior to adding this entry. |
Huang Ying | 1230db8 | 2011-09-08 14:00:42 +0800 | [diff] [blame] | 194 | */ |
Huang Ying | 781f7fd | 2011-09-08 14:00:45 +0800 | [diff] [blame] | 195 | static inline bool llist_add(struct llist_node *new, struct llist_head *head) |
Huang Ying | 1230db8 | 2011-09-08 14:00:42 +0800 | [diff] [blame] | 196 | { |
Oleg Nesterov | e9a17bd | 2013-07-08 14:24:19 -0700 | [diff] [blame] | 197 | return llist_add_batch(new, new, head); |
Huang Ying | 1230db8 | 2011-09-08 14:00:42 +0800 | [diff] [blame] | 198 | } |
| 199 | |
| 200 | /** |
| 201 | * llist_del_all - delete all entries from lock-less list |
| 202 | * @head: the head of lock-less list to delete all entries |
| 203 | * |
| 204 | * If list is empty, return NULL, otherwise, delete all entries and |
| 205 | * return the pointer to the first entry. The order of entries |
| 206 | * deleted is from the newest to the oldest added one. |
| 207 | */ |
| 208 | static inline struct llist_node *llist_del_all(struct llist_head *head) |
| 209 | { |
Huang Ying | 1230db8 | 2011-09-08 14:00:42 +0800 | [diff] [blame] | 210 | return xchg(&head->first, NULL); |
| 211 | } |
Stephen Rothwell | 540f41e | 2011-10-05 17:25:28 +1100 | [diff] [blame] | 212 | |
Stephen Rothwell | 540f41e | 2011-10-05 17:25:28 +1100 | [diff] [blame] | 213 | extern struct llist_node *llist_del_first(struct llist_head *head); |
| 214 | |
Christoph Hellwig | b89241e | 2013-11-14 14:32:11 -0800 | [diff] [blame] | 215 | struct llist_node *llist_reverse_order(struct llist_node *head); |
| 216 | |
Huang Ying | f49f23a | 2011-07-13 13:14:23 +0800 | [diff] [blame] | 217 | #endif /* LLIST_H */ |