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 | bool llist_add_batch(struct llist_node *new_first, struct llist_node *new_last, |
27 | struct llist_head *head) |
28 | { |
29 | struct llist_node *first = READ_ONCE(head->first); |
30 | |
31 | do { |
32 | new_last->next = first; |
33 | } while (!try_cmpxchg(&head->first, &first, new_first)); |
34 | |
35 | 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 | struct llist_node *llist_del_first(struct llist_head *head) |
54 | { |
55 | struct llist_node *entry, *next; |
56 | |
57 | entry = smp_load_acquire(&head->first); |
58 | do { |
59 | if (entry == NULL) |
60 | return NULL; |
61 | next = READ_ONCE(entry->next); |
62 | } while (!try_cmpxchg(&head->first, &entry, next)); |
63 | |
64 | return entry; |
65 | } |
66 | EXPORT_SYMBOL_GPL(llist_del_first); |
67 | |
68 | /** |
69 | * llist_del_first_this - delete given entry of lock-less list if it is first |
70 | * @head: the head for your lock-less list |
71 | * @this: a list entry. |
72 | * |
73 | * If head of the list is given entry, delete and return %true else |
74 | * return %false. |
75 | * |
76 | * Multiple callers can safely call this concurrently with multiple |
77 | * llist_add() callers, providing all the callers offer a different @this. |
78 | */ |
79 | bool llist_del_first_this(struct llist_head *head, |
80 | struct llist_node *this) |
81 | { |
82 | struct llist_node *entry, *next; |
83 | |
84 | /* acquire ensures orderig wrt try_cmpxchg() is llist_del_first() */ |
85 | entry = smp_load_acquire(&head->first); |
86 | do { |
87 | if (entry != this) |
88 | return false; |
89 | next = READ_ONCE(entry->next); |
90 | } while (!try_cmpxchg(&head->first, &entry, next)); |
91 | |
92 | return true; |
93 | } |
94 | EXPORT_SYMBOL_GPL(llist_del_first_this); |
95 | |
96 | /** |
97 | * llist_reverse_order - reverse order of a llist chain |
98 | * @head: first item of the list to be reversed |
99 | * |
100 | * Reverse the order of a chain of llist entries and return the |
101 | * new first entry. |
102 | */ |
103 | struct llist_node *llist_reverse_order(struct llist_node *head) |
104 | { |
105 | struct llist_node *new_head = NULL; |
106 | |
107 | while (head) { |
108 | struct llist_node *tmp = head; |
109 | head = head->next; |
110 | tmp->next = new_head; |
111 | new_head = tmp; |
112 | } |
113 | |
114 | return new_head; |
115 | } |
116 | EXPORT_SYMBOL_GPL(llist_reverse_order); |
117 | |