Blame view
include/linux/llist.h
6.27 KB
f49f23abf lib, Add lock-les... |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
#ifndef LLIST_H #define LLIST_H /* * Lock-less NULL terminated single linked list * * If there are multiple producers and multiple consumers, llist_add * can be used in producers and llist_del_all can be used in * consumers. They can work simultaneously without lock. But * llist_del_first can not be used here. Because llist_del_first * depends on list->first->next does not changed if list->first is not * changed during its operation, but llist_del_first, llist_add, * llist_add (or llist_del_all, llist_add, llist_add) sequence in * another consumer may violate that. * * If there are multiple producers and one consumer, llist_add can be * used in producers and llist_del_all or llist_del_first can be used * in the consumer. * * This can be summarized as follow: * * | add | del_first | del_all * add | - | - | - * del_first | | L | L * del_all | | | - * * Where "-" stands for no lock is needed, while "L" stands for lock * is needed. * * The list entries deleted via llist_del_all can be traversed with * traversing function such as llist_for_each etc. But the list * entries can not be traversed safely before deleted from the list. * The order of deleted entries is from the newest to the oldest added * one. If you want to traverse from the oldest to the newest, you * must reverse the order by yourself before traversing. * * The basic atomic operation of this list is cmpxchg on long. On * architectures that don't have NMI-safe cmpxchg implementation, the |
2c30245c6 llist: Remove the... |
38 39 |
* list can NOT be used in NMI handlers. So code that uses the list in * an NMI handler should depend on CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG. |
1230db8e1 llist: Make some ... |
40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
* * Copyright 2010,2011 Intel Corp. * Author: Huang Ying <ying.huang@intel.com> * * This program is free software; you can redistribute it and/or * modify it under the terms of the GNU General Public License version * 2 as published by the Free Software Foundation; * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA |
f49f23abf lib, Add lock-les... |
56 |
*/ |
1230db8e1 llist: Make some ... |
57 58 59 |
#include <linux/kernel.h> #include <asm/system.h> #include <asm/processor.h> |
f49f23abf lib, Add lock-les... |
60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 |
struct llist_head { struct llist_node *first; }; struct llist_node { struct llist_node *next; }; #define LLIST_HEAD_INIT(name) { NULL } #define LLIST_HEAD(name) struct llist_head name = LLIST_HEAD_INIT(name) /** * init_llist_head - initialize lock-less list head * @head: the head for your lock-less list */ static inline void init_llist_head(struct llist_head *list) { list->first = NULL; } /** * llist_entry - get the struct of this entry * @ptr: the &struct llist_node pointer. * @type: the type of the struct this is embedded in. * @member: the name of the llist_node within the struct. */ #define llist_entry(ptr, type, member) \ container_of(ptr, type, member) /** * llist_for_each - iterate over some deleted entries of a lock-less list * @pos: the &struct llist_node to use as a loop cursor * @node: the first entry of deleted list entries * * In general, some entries of the lock-less list can be traversed * safely only after being deleted from list, so start with an entry * instead of list head. * * If being used on entries deleted from lock-less list directly, the * traverse order is from the newest to the oldest added entry. If * you want to traverse from the oldest to the newest, you must * reverse the order by yourself before traversing. */ #define llist_for_each(pos, node) \ for ((pos) = (node); pos; (pos) = (pos)->next) /** * llist_for_each_entry - iterate over some deleted entries of lock-less list of given type * @pos: the type * to use as a loop cursor. * @node: the fist entry of deleted list entries. * @member: the name of the llist_node with the struct. * * In general, some entries of the lock-less list can be traversed * safely only after being removed from list, so start with an entry * instead of list head. * * If being used on entries deleted from lock-less list directly, the * traverse order is from the newest to the oldest added entry. If * you want to traverse from the oldest to the newest, you must * reverse the order by yourself before traversing. */ #define llist_for_each_entry(pos, node, member) \ for ((pos) = llist_entry((node), typeof(*(pos)), member); \ &(pos)->member != NULL; \ (pos) = llist_entry((pos)->member.next, typeof(*(pos)), member)) /** * llist_empty - tests whether a lock-less list is empty * @head: the list to test * * Not guaranteed to be accurate or up to date. Just a quick way to * test whether the list is empty without deleting something from the * list. */ |
1230db8e1 llist: Make some ... |
134 |
static inline bool llist_empty(const struct llist_head *head) |
f49f23abf lib, Add lock-les... |
135 136 137 |
{ return ACCESS_ONCE(head->first) == NULL; } |
924f8f5af llist: Add llist_... |
138 139 140 141 |
static inline struct llist_node *llist_next(struct llist_node *node) { return node->next; } |
1230db8e1 llist: Make some ... |
142 143 144 145 |
/** * llist_add - add a new entry * @new: new entry to be added * @head: the head for your lock-less list |
781f7fd91 llist: Return whe... |
146 |
* |
fc23af34b llist-return-whet... |
147 |
* Returns true if the list was empty prior to adding this entry. |
1230db8e1 llist: Make some ... |
148 |
*/ |
781f7fd91 llist: Return whe... |
149 |
static inline bool llist_add(struct llist_node *new, struct llist_head *head) |
1230db8e1 llist: Make some ... |
150 151 |
{ struct llist_node *entry, *old_entry; |
1230db8e1 llist: Make some ... |
152 |
entry = head->first; |
a3127336b llist: Move cpu_r... |
153 |
for (;;) { |
1230db8e1 llist: Make some ... |
154 155 |
old_entry = entry; new->next = entry; |
a3127336b llist: Move cpu_r... |
156 157 158 |
entry = cmpxchg(&head->first, old_entry, new); if (entry == old_entry) break; |
a3127336b llist: Move cpu_r... |
159 |
} |
781f7fd91 llist: Return whe... |
160 161 |
return old_entry == NULL; |
1230db8e1 llist: Make some ... |
162 163 164 165 166 167 168 169 170 171 172 173 |
} /** * llist_del_all - delete all entries from lock-less list * @head: the head of lock-less list to delete all entries * * If list is empty, return NULL, otherwise, delete all entries and * return the pointer to the first entry. The order of entries * deleted is from the newest to the oldest added one. */ static inline struct llist_node *llist_del_all(struct llist_head *head) { |
1230db8e1 llist: Make some ... |
174 175 |
return xchg(&head->first, NULL); } |
540f41edc llist: Add back l... |
176 177 178 179 180 |
extern bool llist_add_batch(struct llist_node *new_first, struct llist_node *new_last, struct llist_head *head); extern struct llist_node *llist_del_first(struct llist_head *head); |
f49f23abf lib, Add lock-les... |
181 |
#endif /* LLIST_H */ |