Green shading in the line number column means the source is part of the translation unit, red means it is conditionally excluded. Highlighted line numbers link to the translation unit page. Highlighted macros link to the macro page.
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 handlers. So code that uses the list in 39: * an NMI handler should depend on CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG. 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 56: */ 57: 58: #include <linux/kernel.h> 59: #include <asm/cmpxchg.h> 60: 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: /** 91: * llist_for_each - iterate over some deleted entries of a lock-less list 92: * @pos: the &struct llist_node to use as a loop cursor 93: * @node: the first entry of deleted list entries 94: * 95: * In general, some entries of the lock-less list can be traversed 96: * safely only after being deleted from list, so start with an entry 97: * instead of list head. 98: * 99: * If being used on entries deleted from lock-less list directly, the 100: * traverse order is from the newest to the oldest added entry. If 101: * you want to traverse from the oldest to the newest, you must 102: * reverse the order by yourself before traversing. 103: */ 104: #define llist_for_each(pos, node) \ 105: for ((pos) = (node); pos; (pos) = (pos)->next) 106: 107: /** 108: * llist_for_each_entry - iterate over some deleted entries of lock-less list of given type 109: * @pos: the type * to use as a loop cursor. 110: * @node: the fist entry of deleted list entries. 111: * @member: the name of the llist_node with the struct. 112: * 113: * In general, some entries of the lock-less list can be traversed 114: * safely only after being removed from list, so start with an entry 115: * instead of list head. 116: * 117: * If being used on entries deleted from lock-less list directly, the 118: * traverse order is from the newest to the oldest added entry. If 119: * you want to traverse from the oldest to the newest, you must 120: * reverse the order by yourself before traversing. 121: */ 122: #define llist_for_each_entry(pos, node, member) \ 123: for ((pos) = llist_entry((node), typeof(*(pos)), member); \ 124: &(pos)->member != NULL; \ 125: (pos) = llist_entry((pos)->member.next, typeof(*(pos)), member)) 126: 127: /** 128: * llist_for_each_entry_safe - iterate over some deleted entries of lock-less list of given type 129: * safe against removal of list entry 130: * @pos: the type * to use as a loop cursor. 131: * @n: another type * to use as temporary storage 132: * @node: the first entry of deleted list entries. 133: * @member: the name of the llist_node with the struct. 134: * 135: * In general, some entries of the lock-less list can be traversed 136: * safely only after being removed from list, so start with an entry 137: * instead of list head. 138: * 139: * If being used on entries deleted from lock-less list directly, the 140: * traverse order is from the newest to the oldest added entry. If 141: * you want to traverse from the oldest to the newest, you must 142: * reverse the order by yourself before traversing. 143: */ 144: #define llist_for_each_entry_safe(pos, n, node, member) \ 145: for (pos = llist_entry((node), typeof(*pos), member); \ 146: &pos->member != NULL && \ 147: (n = llist_entry(pos->member.next, typeof(*n), member), true); \ 148: pos = n) 149: 150: /** 151: * llist_empty - tests whether a lock-less list is empty 152: * @head: the list to test 153: * 154: * Not guaranteed to be accurate or up to date. Just a quick way to 155: * test whether the list is empty without deleting something from the 156: * list. 157: */ 158: static inline bool llist_empty(const struct llist_head *head) 159: { 160: return ACCESS_ONCE(head->first) == NULL; 161: } 162: 163: static inline struct llist_node *llist_next(struct llist_node *node) 164: { 165: return node->next; 166: } 167: 168: extern bool llist_add_batch(struct llist_node *new_first, 169: struct llist_node *new_last, 170: struct llist_head *head); 171: /** 172: * llist_add - add a new entry 173: * @new: new entry to be added 174: * @head: the head for your lock-less list 175: * 176: * Returns true if the list was empty prior to adding this entry. 177: */ 178: static inline bool llist_add(struct llist_node *new, struct llist_head *head) 179: { 180: return llist_add_batch(new, new, head); 181: } 182: 183: /** 184: * llist_del_all - delete all entries from lock-less list 185: * @head: the head of lock-less list to delete all entries 186: * 187: * If list is empty, return NULL, otherwise, delete all entries and 188: * return the pointer to the first entry. The order of entries 189: * deleted is from the newest to the oldest added one. 190: */ 191: static inline struct llist_node *llist_del_all(struct llist_head *head) 192: { 193: return xchg(&head->first, NULL); 194: } 195: 196: extern struct llist_node *llist_del_first(struct llist_head *head); 197: 198: struct llist_node *llist_reverse_order(struct llist_node *head); 199: 200: #endif /* LLIST_H */ 201: