include/linux/llist.h

   1 /* SPDX-License-Identifier: GPL-2.0-only */
   2 #ifndef LLIST_H
   3 #define LLIST_H
   4 /*
   5  * Lock-less NULL terminated single linked list
   6  *
   7  * Cases where locking is not needed:
   8  * If there are multiple producers and multiple consumers, llist_add can be
   9  * used in producers and llist_del_all can be used in consumers simultaneously
  10  * without locking. Also a single consumer can use llist_del_first while
  11  * multiple producers simultaneously use llist_add, without any locking.
  12  *
  13  * Cases where locking is needed:
  14  * If we have multiple consumers with llist_del_first used in one consumer, and
  15  * llist_del_first or llist_del_all used in other consumers, then a lock is
  16  * needed.  This is because llist_del_first depends on list->first->next not
  17  * changing, but without lock protection, there's no way to be sure about that
  18  * if a preemption happens in the middle of the delete operation and on being
  19  * preempted back, the list->first is the same as before causing the cmpxchg in
  20  * llist_del_first to succeed. For example, while a llist_del_first operation
  21  * is in progress in one consumer, then a llist_del_first, llist_add,
  22  * llist_add (or llist_del_all, llist_add, llist_add) sequence in another
  23  * consumer may cause violations.
  24  *
  25  * This can be summarized as follows:
  26  *
  27  *           |   add    | del_first |  del_all
  28  * add       |    -     |     -     |     -
  29  * del_first |          |     L     |     L
  30  * del_all   |          |           |     -
  31  *
  32  * Where, a particular row's operation can happen concurrently with a column's
  33  * operation, with "-" being no lock needed, while "L" being lock is needed.
  34  *
  35  * The list entries deleted via llist_del_all can be traversed with
  36  * traversing function such as llist_for_each etc.  But the list
  37  * entries can not be traversed safely before deleted from the list.
  38  * The order of deleted entries is from the newest to the oldest added
  39  * one.  If you want to traverse from the oldest to the newest, you
  40  * must reverse the order by yourself before traversing.
  41  *
  42  * The basic atomic operation of this list is cmpxchg on long.  On
  43  * architectures that don't have NMI-safe cmpxchg implementation, the
  44  * list can NOT be used in NMI handlers.  So code that uses the list in
  45  * an NMI handler should depend on CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG.
  46  *
  47  * Copyright 2010,2011 Intel Corp.
  48  *   Author: Huang Ying <ying.huang@intel.com>
  49  */
  50
  51 #include <linux/atomic.h>
  52 #include <linux/kernel.h>
  53
  54 struct llist_head {
  55         struct llist_node *first;
  56 };
  57
  58 struct llist_node {
  59         struct llist_node *next;
  60 };
  61
  62 #define LLIST_HEAD_INIT(name)   { NULL }
  63 #define LLIST_HEAD(name)        struct llist_head name = LLIST_HEAD_INIT(name)
  64
  65 /**
  66  * init_llist_head - initialize lock-less list head
  67  * @head:       the head for your lock-less list
  68  */
  69 static inline void init_llist_head(struct llist_head *list)
  70 {
  71         list->first = NULL;
  72 }
  73
  74 /**
  75  * llist_entry - get the struct of this entry
  76  * @ptr:        the &struct llist_node pointer.
  77  * @type:       the type of the struct this is embedded in.
  78  * @member:     the name of the llist_node within the struct.
  79  */
  80 #define llist_entry(ptr, type, member)          \
  81         container_of(ptr, type, member)
  82
  83 /**
  84  * member_address_is_nonnull - check whether the member address is not NULL
  85  * @ptr:        the object pointer (struct type * that contains the llist_node)
  86  * @member:     the name of the llist_node within the struct.
  87  *
  88  * This macro is conceptually the same as
  89  *      &ptr->member != NULL
  90  * but it works around the fact that compilers can decide that taking a member
  91  * address is never a NULL pointer.
  92  *
  93  * Real objects that start at a high address and have a member at NULL are
  94  * unlikely to exist, but such pointers may be returned e.g. by the
  95  * container_of() macro.
  96  */
  97 #define member_address_is_nonnull(ptr, member)  \
  98         ((uintptr_t)(ptr) + offsetof(typeof(*(ptr)), member) != 0)
  99
 100 /**
 101  * llist_for_each - iterate over some deleted entries of a lock-less list
 102  * @pos:        the &struct llist_node to use as a loop cursor
 103  * @node:       the first entry of deleted list entries
 104  *
 105  * In general, some entries of the lock-less list can be traversed
 106  * safely only after being deleted from list, so start with an entry
 107  * instead of list head.
 108  *
 109  * If being used on entries deleted from lock-less list directly, the
 110  * traverse order is from the newest to the oldest added entry.  If
 111  * you want to traverse from the oldest to the newest, you must
 112  * reverse the order by yourself before traversing.
 113  */
 114 #define llist_for_each(pos, node)                       \
 115         for ((pos) = (node); pos; (pos) = (pos)->next)
 116
 117 /**
 118  * llist_for_each_safe - iterate over some deleted entries of a lock-less list
 119  *                       safe against removal of list entry
 120  * @pos:        the &struct llist_node to use as a loop cursor
 121  * @n:          another &struct llist_node to use as temporary storage
 122  * @node:       the first entry of deleted list entries
 123  *
 124  * In general, some entries of the lock-less list can be traversed
 125  * safely only after being deleted from list, so start with an entry
 126  * instead of list head.
 127  *
 128  * If being used on entries deleted from lock-less list directly, the
 129  * traverse order is from the newest to the oldest added entry.  If
 130  * you want to traverse from the oldest to the newest, you must
 131  * reverse the order by yourself before traversing.
 132  */
 133 #define llist_for_each_safe(pos, n, node)                       \
 134         for ((pos) = (node); (pos) && ((n) = (pos)->next, true); (pos) = (n))
 135
 136 /**
 137  * llist_for_each_entry - iterate over some deleted entries of lock-less list of given type
 138  * @pos:        the type * to use as a loop cursor.
 139  * @node:       the fist entry of deleted list entries.
 140  * @member:     the name of the llist_node with the struct.
 141  *
 142  * In general, some entries of the lock-less list can be traversed
 143  * safely only after being removed from list, so start with an entry
 144  * instead of list head.
 145  *
 146  * If being used on entries deleted from lock-less list directly, the
 147  * traverse order is from the newest to the oldest added entry.  If
 148  * you want to traverse from the oldest to the newest, you must
 149  * reverse the order by yourself before traversing.
 150  */
 151 #define llist_for_each_entry(pos, node, member)                         \
 152         for ((pos) = llist_entry((node), typeof(*(pos)), member);       \
 153              member_address_is_nonnull(pos, member);                    \
 154              (pos) = llist_entry((pos)->member.next, typeof(*(pos)), member))
 155
 156 /**
 157  * llist_for_each_entry_safe - iterate over some deleted entries of lock-less list of given type
 158  *                             safe against removal of list entry
 159  * @pos:        the type * to use as a loop cursor.
 160  * @n:          another type * to use as temporary storage
 161  * @node:       the first entry of deleted list entries.
 162  * @member:     the name of the llist_node with the struct.
 163  *
 164  * In general, some entries of the lock-less list can be traversed
 165  * safely only after being removed from list, so start with an entry
 166  * instead of list head.
 167  *
 168  * If being used on entries deleted from lock-less list directly, the
 169  * traverse order is from the newest to the oldest added entry.  If
 170  * you want to traverse from the oldest to the newest, you must
 171  * reverse the order by yourself before traversing.
 172  */
 173 #define llist_for_each_entry_safe(pos, n, node, member)                        \
 174         for (pos = llist_entry((node), typeof(*pos), member);                  \
 175              member_address_is_nonnull(pos, member) &&                         \
 176                 (n = llist_entry(pos->member.next, typeof(*n), member), true); \
 177              pos = n)
 178
 179 /**
 180  * llist_empty - tests whether a lock-less list is empty
 181  * @head:       the list to test
 182  *
 183  * Not guaranteed to be accurate or up to date.  Just a quick way to
 184  * test whether the list is empty without deleting something from the
 185  * list.
 186  */
 187 static inline bool llist_empty(const struct llist_head *head)
 188 {
 189         return READ_ONCE(head->first) == NULL;
 190 }
 191
 192 static inline struct llist_node *llist_next(struct llist_node *node)
 193 {
 194         return node->next;
 195 }
 196
 197 extern bool llist_add_batch(struct llist_node *new_first,
 198                             struct llist_node *new_last,
 199                             struct llist_head *head);
 200
 201 static inline bool __llist_add_batch(struct llist_node *new_first,
 202                                      struct llist_node *new_last,
 203                                      struct llist_head *head)
 204 {
 205         new_last->next = head->first;
 206         head->first = new_first;
 207         return new_last->next == NULL;
 208 }
 209
 210 /**
 211  * llist_add - add a new entry
 212  * @new:        new entry to be added
 213  * @head:       the head for your lock-less list
 214  *
 215  * Returns true if the list was empty prior to adding this entry.
 216  */
 217 static inline bool llist_add(struct llist_node *new, struct llist_head *head)
 218 {
 219         return llist_add_batch(new, new, head);
 220 }
 221
 222 static inline bool __llist_add(struct llist_node *new, struct llist_head *head)
 223 {
 224         return __llist_add_batch(new, new, head);
 225 }
 226
 227 /**
 228  * llist_del_all - delete all entries from lock-less list
 229  * @head:       the head of lock-less list to delete all entries
 230  *
 231  * If list is empty, return NULL, otherwise, delete all entries and
 232  * return the pointer to the first entry.  The order of entries
 233  * deleted is from the newest to the oldest added one.
 234  */
 235 static inline struct llist_node *llist_del_all(struct llist_head *head)
 236 {
 237         return xchg(&head->first, NULL);
 238 }
 239
 240 static inline struct llist_node *__llist_del_all(struct llist_head *head)
 241 {
 242         struct llist_node *first = head->first;
 243
 244         head->first = NULL;
 245         return first;
 246 }
 247
 248 extern struct llist_node *llist_del_first(struct llist_head *head);
 249
 250 struct llist_node *llist_reverse_order(struct llist_node *head);
 251
 252 #endif /* LLIST_H */