LCOV - code coverage report
Current view: top level - include/linux - llist.h (source / functions) Hit Total Coverage
Test: coverage.info Lines: 2 4 50.0 %
Date: 2023-08-24 13:40:31 Functions: 0 0 -

          Line data    Source code
       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          23 :         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          10 :         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           0 :         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           0 :         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 */

Generated by: LCOV version 1.14