Line data    Source code

       1             : // SPDX-License-Identifier: GPL-2.0-only
       2             : /*
       3             :  * Lock-less NULL terminated single linked list
       4             :  *
       5             :  * The basic atomic operation of this list is cmpxchg on long.  On
       6             :  * architectures that don't have NMI-safe cmpxchg implementation, the
       7             :  * list can NOT be used in NMI handlers.  So code that uses the list in
       8             :  * an NMI handler should depend on CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG.
       9             :  *
      10             :  * Copyright 2010,2011 Intel Corp.
      11             :  *   Author: Huang Ying <ying.huang@intel.com>
      12             :  */
      13             : #include <linux/kernel.h>
      14             : #include <linux/export.h>
      15             : #include <linux/llist.h>
      16             : 
      17             : 
      18             : /**
      19             :  * llist_add_batch - add several linked entries in batch
      20             :  * @new_first:  first entry in batch to be added
      21             :  * @new_last:   last entry in batch to be added
      22             :  * @head:       the head for your lock-less list
      23             :  *
      24             :  * Return whether list is empty before adding.
      25             :  */
      26       14908 : bool llist_add_batch(struct llist_node *new_first, struct llist_node *new_last,
      27             :                      struct llist_head *head)
      28             : {
      29       14909 :         struct llist_node *first;
      30             : 
      31       14909 :         do {
      32       14909 :                 new_last->next = first = READ_ONCE(head->first);
      33       14909 :         } while (cmpxchg(&head->first, first, new_first) != first);
      34             : 
      35       14908 :         return !first;
      36             : }
      37             : EXPORT_SYMBOL_GPL(llist_add_batch);
      38             : 
      39             : /**
      40             :  * llist_del_first - delete the first entry of lock-less list
      41             :  * @head:       the head for your lock-less list
      42             :  *
      43             :  * If list is empty, return NULL, otherwise, return the first entry
      44             :  * deleted, this is the newest added one.
      45             :  *
      46             :  * Only one llist_del_first user can be used simultaneously with
      47             :  * multiple llist_add users without lock.  Because otherwise
      48             :  * llist_del_first, llist_add, llist_add (or llist_del_all, llist_add,
      49             :  * llist_add) sequence in another user may change @head->first->next,
      50             :  * but keep @head->first.  If multiple consumers are needed, please
      51             :  * use llist_del_all or use lock between consumers.
      52             :  */
      53         145 : struct llist_node *llist_del_first(struct llist_head *head)
      54             : {
      55         145 :         struct llist_node *entry, *old_entry, *next;
      56             : 
      57         145 :         entry = smp_load_acquire(&head->first);
      58         145 :         for (;;) {
      59         145 :                 if (entry == NULL)
      60             :                         return NULL;
      61         145 :                 old_entry = entry;
      62         145 :                 next = READ_ONCE(entry->next);
      63         145 :                 entry = cmpxchg(&head->first, old_entry, next);
      64         145 :                 if (entry == old_entry)
      65             :                         break;
      66             :         }
      67             : 
      68             :         return entry;
      69             : }
      70             : EXPORT_SYMBOL_GPL(llist_del_first);
      71             : 
      72             : /**
      73             :  * llist_reverse_order - reverse order of a llist chain
      74             :  * @head:       first item of the list to be reversed
      75             :  *
      76             :  * Reverse the order of a chain of llist entries and return the
      77             :  * new first entry.
      78             :  */
      79       14117 : struct llist_node *llist_reverse_order(struct llist_node *head)
      80             : {
      81       14117 :         struct llist_node *new_head = NULL;
      82             : 
      83       28803 :         while (head) {
      84       14686 :                 struct llist_node *tmp = head;
      85       14686 :                 head = head->next;
      86       14686 :                 tmp->next = new_head;
      87       14686 :                 new_head = tmp;
      88             :         }
      89             : 
      90       14117 :         return new_head;
      91             : }
      92             : EXPORT_SYMBOL_GPL(llist_reverse_order);