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