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/container_of.h>
  53 #include <linux/stddef.h>
  54 #include <linux/types.h>
  55
  56 struct llist_head {
  57         struct llist_node *first;
  58 };
  59
  60 struct llist_node {
  61         struct llist_node *next;
  62 };
  63
  64 #define LLIST_HEAD_INIT(name)   { NULL }
  65 #define LLIST_HEAD(name)        struct llist_head name = LLIST_HEAD_INIT(name)
  66
  67 /**
  68  * init_llist_head - initialize lock-less list head
  69  * @head:       the head for your lock-less list
  70  */
  71 static inline void init_llist_head(struct llist_head *list)
  72 {
  73         list->first = NULL;
  74 }
  75
  76 /**
  77  * llist_entry - get the struct of this entry
  78  * @ptr:        the &struct llist_node pointer.
  79  * @type:       the type of the struct this is embedded in.
  80  * @member:     the name of the llist_node within the struct.
  81  */
  82 #define llist_entry(ptr, type, member)          \
  83         container_of(ptr, type, member)
  84
  85 /**
  86  * member_address_is_nonnull - check whether the member address is not NULL
  87  * @ptr:        the object pointer (struct type * that contains the llist_node)
  88  * @member:     the name of the llist_node within the struct.
  89  *
  90  * This macro is conceptually the same as
  91  *      &ptr->member != NULL
  92  * but it works around the fact that compilers can decide that taking a member
  93  * address is never a NULL pointer.
  94  *
  95  * Real objects that start at a high address and have a member at NULL are
  96  * unlikely to exist, but such pointers may be returned e.g. by the
  97  * container_of() macro.
  98  */
  99 #define member_address_is_nonnull(ptr, member)  \
 100         ((uintptr_t)(ptr) + offsetof(typeof(*(ptr)), member) != 0)
 101
 102 /**
 103  * llist_for_each - iterate over some deleted entries of a lock-less list
 104  * @pos:        the &struct llist_node to use as a loop cursor
 105  * @node:       the first entry of deleted list entries
 106  *
 107  * In general, some entries of the lock-less list can be traversed
 108  * safely only after being deleted from list, so start with an entry
 109  * instead of list head.
 110  *
 111  * If being used on entries deleted from lock-less list directly, the
 112  * traverse order is from the newest to the oldest added entry.  If
 113  * you want to traverse from the oldest to the newest, you must
 114  * reverse the order by yourself before traversing.
 115  */
 116 #define llist_for_each(pos, node)                       \
 117         for ((pos) = (node); pos; (pos) = (pos)->next)
 118
 119 /**
 120  * llist_for_each_safe - iterate over some deleted entries of a lock-less list
 121  *                       safe against removal of list entry
 122  * @pos:        the &struct llist_node to use as a loop cursor
 123  * @n:          another &struct llist_node to use as temporary storage
 124  * @node:       the first entry of deleted list entries
 125  *
 126  * In general, some entries of the lock-less list can be traversed
 127  * safely only after being deleted from list, so start with an entry
 128  * instead of list head.
 129  *
 130  * If being used on entries deleted from lock-less list directly, the
 131  * traverse order is from the newest to the oldest added entry.  If
 132  * you want to traverse from the oldest to the newest, you must
 133  * reverse the order by yourself before traversing.
 134  */
 135 #define llist_for_each_safe(pos, n, node)                       \
 136         for ((pos) = (node); (pos) && ((n) = (pos)->next, true); (pos) = (n))
 137
 138 /**
 139  * llist_for_each_entry - iterate over some deleted entries of lock-less list of given type
 140  * @pos:        the type * to use as a loop cursor.
 141  * @node:       the fist entry of deleted list entries.
 142  * @member:     the name of the llist_node with the struct.
 143  *
 144  * In general, some entries of the lock-less list can be traversed
 145  * safely only after being removed from list, so start with an entry
 146  * instead of list head.
 147  *
 148  * If being used on entries deleted from lock-less list directly, the
 149  * traverse order is from the newest to the oldest added entry.  If
 150  * you want to traverse from the oldest to the newest, you must
 151  * reverse the order by yourself before traversing.
 152  */
 153 #define llist_for_each_entry(pos, node, member)                         \
 154         for ((pos) = llist_entry((node), typeof(*(pos)), member);       \
 155              member_address_is_nonnull(pos, member);                    \
 156              (pos) = llist_entry((pos)->member.next, typeof(*(pos)), member))
 157
 158 /**
 159  * llist_for_each_entry_safe - iterate over some deleted entries of lock-less list of given type
 160  *                             safe against removal of list entry
 161  * @pos:        the type * to use as a loop cursor.
 162  * @n:          another type * to use as temporary storage
 163  * @node:       the first entry of deleted list entries.
 164  * @member:     the name of the llist_node with the struct.
 165  *
 166  * In general, some entries of the lock-less list can be traversed
 167  * safely only after being removed from list, so start with an entry
 168  * instead of list head.
 169  *
 170  * If being used on entries deleted from lock-less list directly, the
 171  * traverse order is from the newest to the oldest added entry.  If
 172  * you want to traverse from the oldest to the newest, you must
 173  * reverse the order by yourself before traversing.
 174  */
 175 #define llist_for_each_entry_safe(pos, n, node, member)                        \
 176         for (pos = llist_entry((node), typeof(*pos), member);                  \
 177              member_address_is_nonnull(pos, member) &&                         \
 178                 (n = llist_entry(pos->member.next, typeof(*n), member), true); \
 179              pos = n)
 180
 181 /**
 182  * llist_empty - tests whether a lock-less list is empty
 183  * @head:       the list to test
 184  *
 185  * Not guaranteed to be accurate or up to date.  Just a quick way to
 186  * test whether the list is empty without deleting something from the
 187  * list.
 188  */
 189 static inline bool llist_empty(const struct llist_head *head)
 190 {
 191         return READ_ONCE(head->first) == NULL;
 192 }
 193
 194 static inline struct llist_node *llist_next(struct llist_node *node)
 195 {
 196         return node->next;
 197 }
 198
 199 extern bool llist_add_batch(struct llist_node *new_first,
 200                             struct llist_node *new_last,
 201                             struct llist_head *head);
 202
 203 static inline bool __llist_add_batch(struct llist_node *new_first,
 204                                      struct llist_node *new_last,
 205                                      struct llist_head *head)
 206 {
 207         new_last->next = head->first;
 208         head->first = new_first;
 209         return new_last->next == NULL;
 210 }
 211
 212 /**
 213  * llist_add - add a new entry
 214  * @new:        new entry to be added
 215  * @head:       the head for your lock-less list
 216  *
 217  * Returns true if the list was empty prior to adding this entry.
 218  */
 219 static inline bool llist_add(struct llist_node *new, struct llist_head *head)
 220 {
 221         return llist_add_batch(new, new, head);
 222 }
 223
 224 static inline bool __llist_add(struct llist_node *new, struct llist_head *head)
 225 {
 226         return __llist_add_batch(new, new, head);
 227 }
 228
 229 /**
 230  * llist_del_all - delete all entries from lock-less list
 231  * @head:       the head of lock-less list to delete all entries
 232  *
 233  * If list is empty, return NULL, otherwise, delete all entries and
 234  * return the pointer to the first entry.  The order of entries
 235  * deleted is from the newest to the oldest added one.
 236  */
 237 static inline struct llist_node *llist_del_all(struct llist_head *head)
 238 {
 239         return xchg(&head->first, NULL);
 240 }
 241
 242 static inline struct llist_node *__llist_del_all(struct llist_head *head)
 243 {
 244         struct llist_node *first = head->first;
 245
 246         head->first = NULL;
 247         return first;
 248 }
 249
 250 extern struct llist_node *llist_del_first(struct llist_head *head);
 251
 252 struct llist_node *llist_reverse_order(struct llist_node *head);
 253
 254 #endif /* LLIST_H */