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           0 : bool llist_add_batch(struct llist_node *new_first, struct llist_node *new_last,
      27             :                      struct llist_head *head)
      28             : {
      29           0 :         struct llist_node *first = READ_ONCE(head->first);
      30             : 
      31             :         do {
      32           0 :                 new_last->next = first;
      33           0 :         } while (!try_cmpxchg(&head->first, &first, new_first));
      34             : 
      35           0 :         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           0 : struct llist_node *llist_del_first(struct llist_head *head)
      54             : {
      55             :         struct llist_node *entry, *next;
      56             : 
      57           0 :         entry = smp_load_acquire(&head->first);
      58             :         do {
      59           0 :                 if (entry == NULL)
      60             :                         return NULL;
      61           0 :                 next = READ_ONCE(entry->next);
      62           0 :         } while (!try_cmpxchg(&head->first, &entry, next));
      63             : 
      64             :         return entry;
      65             : }
      66             : EXPORT_SYMBOL_GPL(llist_del_first);
      67             : 
      68             : /**
      69             :  * llist_reverse_order - reverse order of a llist chain
      70             :  * @head:       first item of the list to be reversed
      71             :  *
      72             :  * Reverse the order of a chain of llist entries and return the
      73             :  * new first entry.
      74             :  */
      75           0 : struct llist_node *llist_reverse_order(struct llist_node *head)
      76             : {
      77           0 :         struct llist_node *new_head = NULL;
      78             : 
      79           0 :         while (head) {
      80           0 :                 struct llist_node *tmp = head;
      81           0 :                 head = head->next;
      82           0 :                 tmp->next = new_head;
      83           0 :                 new_head = tmp;
      84             :         }
      85             : 
      86           0 :         return new_head;
      87             : }
      88             : EXPORT_SYMBOL_GPL(llist_reverse_order);