Back to home page

LXR

 
 

    


0001 /*
0002  * Lock-less NULL terminated single linked list
0003  *
0004  * The basic atomic operation of this list is cmpxchg on long.  On
0005  * architectures that don't have NMI-safe cmpxchg implementation, the
0006  * list can NOT be used in NMI handlers.  So code that uses the list in
0007  * an NMI handler should depend on CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG.
0008  *
0009  * Copyright 2010,2011 Intel Corp.
0010  *   Author: Huang Ying <ying.huang@intel.com>
0011  *
0012  * This program is free software; you can redistribute it and/or
0013  * modify it under the terms of the GNU General Public License version
0014  * 2 as published by the Free Software Foundation;
0015  *
0016  * This program is distributed in the hope that it will be useful,
0017  * but WITHOUT ANY WARRANTY; without even the implied warranty of
0018  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
0019  * GNU General Public License for more details.
0020  *
0021  * You should have received a copy of the GNU General Public License
0022  * along with this program; if not, write to the Free Software
0023  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
0024  */
0025 #include <linux/kernel.h>
0026 #include <linux/export.h>
0027 #include <linux/llist.h>
0028 
0029 
0030 /**
0031  * llist_add_batch - add several linked entries in batch
0032  * @new_first:  first entry in batch to be added
0033  * @new_last:   last entry in batch to be added
0034  * @head:   the head for your lock-less list
0035  *
0036  * Return whether list is empty before adding.
0037  */
0038 bool llist_add_batch(struct llist_node *new_first, struct llist_node *new_last,
0039              struct llist_head *head)
0040 {
0041     struct llist_node *first;
0042 
0043     do {
0044         new_last->next = first = ACCESS_ONCE(head->first);
0045     } while (cmpxchg(&head->first, first, new_first) != first);
0046 
0047     return !first;
0048 }
0049 EXPORT_SYMBOL_GPL(llist_add_batch);
0050 
0051 /**
0052  * llist_del_first - delete the first entry of lock-less list
0053  * @head:   the head for your lock-less list
0054  *
0055  * If list is empty, return NULL, otherwise, return the first entry
0056  * deleted, this is the newest added one.
0057  *
0058  * Only one llist_del_first user can be used simultaneously with
0059  * multiple llist_add users without lock.  Because otherwise
0060  * llist_del_first, llist_add, llist_add (or llist_del_all, llist_add,
0061  * llist_add) sequence in another user may change @head->first->next,
0062  * but keep @head->first.  If multiple consumers are needed, please
0063  * use llist_del_all or use lock between consumers.
0064  */
0065 struct llist_node *llist_del_first(struct llist_head *head)
0066 {
0067     struct llist_node *entry, *old_entry, *next;
0068 
0069     entry = smp_load_acquire(&head->first);
0070     for (;;) {
0071         if (entry == NULL)
0072             return NULL;
0073         old_entry = entry;
0074         next = READ_ONCE(entry->next);
0075         entry = cmpxchg(&head->first, old_entry, next);
0076         if (entry == old_entry)
0077             break;
0078     }
0079 
0080     return entry;
0081 }
0082 EXPORT_SYMBOL_GPL(llist_del_first);
0083 
0084 /**
0085  * llist_reverse_order - reverse order of a llist chain
0086  * @head:   first item of the list to be reversed
0087  *
0088  * Reverse the order of a chain of llist entries and return the
0089  * new first entry.
0090  */
0091 struct llist_node *llist_reverse_order(struct llist_node *head)
0092 {
0093     struct llist_node *new_head = NULL;
0094 
0095     while (head) {
0096         struct llist_node *tmp = head;
0097         head = head->next;
0098         tmp->next = new_head;
0099         new_head = tmp;
0100     }
0101 
0102     return new_head;
0103 }
0104 EXPORT_SYMBOL_GPL(llist_reverse_order);