Blame view
lib/llist.c
2.54 KB
450515395
|
1 |
// SPDX-License-Identifier: GPL-2.0-only |
f49f23abf
|
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
|
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
|
9 10 11 |
* * Copyright 2010,2011 Intel Corp. * Author: Huang Ying <ying.huang@intel.com> |
f49f23abf
|
12 13 |
*/ #include <linux/kernel.h> |
8bc3bcc93
|
14 |
#include <linux/export.h> |
f49f23abf
|
15 |
#include <linux/llist.h> |
f49f23abf
|
16 17 |
/** |
f49f23abf
|
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
|
22 23 |
* * Return whether list is empty before adding. |
f49f23abf
|
24 |
*/ |
781f7fd91
|
25 |
bool llist_add_batch(struct llist_node *new_first, struct llist_node *new_last, |
f49f23abf
|
26 27 |
struct llist_head *head) { |
fb4214db5
|
28 |
struct llist_node *first; |
f49f23abf
|
29 |
|
fb4214db5
|
30 |
do { |
6aa7de059
|
31 |
new_last->next = first = READ_ONCE(head->first); |
fb4214db5
|
32 |
} while (cmpxchg(&head->first, first, new_first) != first); |
781f7fd91
|
33 |
|
fb4214db5
|
34 |
return !first; |
f49f23abf
|
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
|
55 |
entry = smp_load_acquire(&head->first); |
a3127336b
|
56 |
for (;;) { |
f49f23abf
|
57 58 59 |
if (entry == NULL) return NULL; old_entry = entry; |
2cf12f821
|
60 |
next = READ_ONCE(entry->next); |
a3127336b
|
61 62 63 |
entry = cmpxchg(&head->first, old_entry, next); if (entry == old_entry) break; |
a3127336b
|
64 |
} |
f49f23abf
|
65 66 67 68 |
return entry; } EXPORT_SYMBOL_GPL(llist_del_first); |
b89241e8c
|
69 70 71 72 73 |
/** * llist_reverse_order - reverse order of a llist chain * @head: first item of the list to be reversed * |
0791a6057
|
74 |
* Reverse the order of a chain of llist entries and return the |
b89241e8c
|
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); |