Commit | Line | Data |
---|---|---|
f49f23ab HY |
1 | /* |
2 | * Lock-less NULL terminated single linked list | |
3 | * | |
4 | * The basic atomic operation of this list is cmpxchg on long. On | |
5 | * architectures that don't have NMI-safe cmpxchg implementation, the | |
6 | * list can NOT be used in NMI handler. So code uses the list in NMI | |
7 | * handler should depend on CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG. | |
8 | * | |
9 | * Copyright 2010,2011 Intel Corp. | |
10 | * Author: Huang Ying <ying.huang@intel.com> | |
11 | * | |
12 | * This program is free software; you can redistribute it and/or | |
13 | * modify it under the terms of the GNU General Public License version | |
14 | * 2 as published by the Free Software Foundation; | |
15 | * | |
16 | * This program is distributed in the hope that it will be useful, | |
17 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
18 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
19 | * GNU General Public License for more details. | |
20 | * | |
21 | * You should have received a copy of the GNU General Public License | |
22 | * along with this program; if not, write to the Free Software | |
23 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA | |
24 | */ | |
25 | #include <linux/kernel.h> | |
26 | #include <linux/module.h> | |
27 | #include <linux/interrupt.h> | |
28 | #include <linux/llist.h> | |
29 | ||
30 | #include <asm/system.h> | |
31 | ||
f49f23ab HY |
32 | /** |
33 | * llist_add_batch - add several linked entries in batch | |
34 | * @new_first: first entry in batch to be added | |
35 | * @new_last: last entry in batch to be added | |
36 | * @head: the head for your lock-less list | |
37 | */ | |
38 | void llist_add_batch(struct llist_node *new_first, struct llist_node *new_last, | |
39 | struct llist_head *head) | |
40 | { | |
41 | struct llist_node *entry, *old_entry; | |
42 | ||
43 | #ifndef CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG | |
44 | BUG_ON(in_nmi()); | |
45 | #endif | |
46 | ||
47 | entry = head->first; | |
48 | do { | |
49 | old_entry = entry; | |
50 | new_last->next = entry; | |
51 | cpu_relax(); | |
52 | } while ((entry = cmpxchg(&head->first, old_entry, new_first)) != old_entry); | |
53 | } | |
54 | EXPORT_SYMBOL_GPL(llist_add_batch); | |
55 | ||
56 | /** | |
57 | * llist_del_first - delete the first entry of lock-less list | |
58 | * @head: the head for your lock-less list | |
59 | * | |
60 | * If list is empty, return NULL, otherwise, return the first entry | |
61 | * deleted, this is the newest added one. | |
62 | * | |
63 | * Only one llist_del_first user can be used simultaneously with | |
64 | * multiple llist_add users without lock. Because otherwise | |
65 | * llist_del_first, llist_add, llist_add (or llist_del_all, llist_add, | |
66 | * llist_add) sequence in another user may change @head->first->next, | |
67 | * but keep @head->first. If multiple consumers are needed, please | |
68 | * use llist_del_all or use lock between consumers. | |
69 | */ | |
70 | struct llist_node *llist_del_first(struct llist_head *head) | |
71 | { | |
72 | struct llist_node *entry, *old_entry, *next; | |
73 | ||
74 | #ifndef CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG | |
75 | BUG_ON(in_nmi()); | |
76 | #endif | |
77 | ||
78 | entry = head->first; | |
79 | do { | |
80 | if (entry == NULL) | |
81 | return NULL; | |
82 | old_entry = entry; | |
83 | next = entry->next; | |
84 | cpu_relax(); | |
85 | } while ((entry = cmpxchg(&head->first, old_entry, next)) != old_entry); | |
86 | ||
87 | return entry; | |
88 | } | |
89 | EXPORT_SYMBOL_GPL(llist_del_first); |