1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
|
#ifndef LLIST_H
#define LLIST_H
/*
* Lock-less NULL terminated single linked list
*
* If there are multiple producers and multiple consumers, llist_add
* can be used in producers and llist_del_all can be used in
* consumers. They can work simultaneously without lock. But
* llist_del_first can not be used here. Because llist_del_first
* depends on list->first->next does not changed if list->first is not
* changed during its operation, but llist_del_first, llist_add,
* llist_add (or llist_del_all, llist_add, llist_add) sequence in
* another consumer may violate that.
*
* If there are multiple producers and one consumer, llist_add can be
* used in producers and llist_del_all or llist_del_first can be used
* in the consumer.
*
* This can be summarized as follow:
*
* | add | del_first | del_all
* add | - | - | -
* del_first | | L | L
* del_all | | | -
*
* Where "-" stands for no lock is needed, while "L" stands for lock
* is needed.
*
* The list entries deleted via llist_del_all can be traversed with
* traversing function such as llist_for_each etc. But the list
* entries can not be traversed safely before deleted from the list.
* The order of deleted entries is from the newest to the oldest added
* one. If you want to traverse from the oldest to the newest, you
* must reverse the order by yourself before traversing.
*
* The basic atomic operation of this list is cmpxchg on long. On
* architectures that don't have NMI-safe cmpxchg implementation, the
* 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.
*
* Copyright 2010,2011 Intel Corp.
* Author: Huang Ying <ying.huang@intel.com>
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License version
* 2 as published by the Free Software Foundation;
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*/
#include <linux/kernel.h>
#include <asm/cmpxchg.h>
struct llist_head {
struct llist_node *first;
};
struct llist_node {
struct llist_node *next;
};
#define LLIST_HEAD_INIT(name) { NULL }
#define LLIST_HEAD(name) struct llist_head name = LLIST_HEAD_INIT(name)
static inline void init_llist_head(struct llist_head *list)
{
list->first = NULL;
}
#define llist_entry(ptr, type, member) \
container_of(ptr, type, member)
#define llist_for_each(pos, node) \
for ((pos) = (node); pos; (pos) = (pos)->next)
#define llist_for_each_entry(pos, node, member) \
for ((pos) = llist_entry((node), typeof(*(pos)), member); \
&(pos)->member != NULL; \
(pos) = llist_entry((pos)->member.next, typeof(*(pos)), member))
static inline bool llist_empty(const struct llist_head *head)
{
return ACCESS_ONCE(head->first) == NULL;
}
static inline struct llist_node *llist_next(struct llist_node *node)
{
return node->next;
}
static inline bool llist_add(struct llist_node *new, struct llist_head *head)
{
struct llist_node *entry, *old_entry;
entry = head->first;
for (;;) {
old_entry = entry;
new->next = entry;
entry = cmpxchg(&head->first, old_entry, new);
if (entry == old_entry)
break;
}
return old_entry == NULL;
}
static inline struct llist_node *llist_del_all(struct llist_head *head)
{
return xchg(&head->first, NULL);
}
extern bool llist_add_batch(struct llist_node *new_first,
struct llist_node *new_last,
struct llist_head *head);
extern struct llist_node *llist_del_first(struct llist_head *head);
#endif
|
