Commit | Line | Data |
---|---|---|
50126a76 MD |
1 | #ifndef _CDS_RCUDQ_H |
2 | #define _CDS_RCUDQ_H | |
3 | ||
4 | /* | |
5 | * Copyright (C) 2002 Free Software Foundation, Inc. | |
6 | * (originally part of the GNU C Library) | |
7 | * Contributed by Ulrich Drepper <drepper@redhat.com>, 2002. | |
8 | * | |
9 | * Copyright (C) 2009 Pierre-Marc Fournier | |
10 | * Copyright (C) 2010-2013 Mathieu Desnoyers <mathieu.desnoyers@efficios.com> | |
11 | * | |
12 | * This library is free software; you can redistribute it and/or | |
13 | * modify it under the terms of the GNU Lesser General Public | |
14 | * License as published by the Free Software Foundation; either | |
15 | * version 2.1 of the License, or (at your option) any later version. | |
16 | * | |
17 | * This library is distributed in the hope that it will be useful, | |
18 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
19 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
20 | * Lesser General Public License for more details. | |
21 | * | |
22 | * You should have received a copy of the GNU Lesser General Public | |
23 | * License along with this library; if not, write to the Free Software | |
24 | * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA | |
25 | */ | |
26 | ||
27 | #include <urcu/arch.h> | |
28 | #include <urcu/compiler.h> | |
29 | #include <urcu-pointer.h> | |
30 | #include <assert.h> | |
31 | ||
32 | #ifdef __cplusplus | |
33 | extern "C" { | |
34 | #endif | |
35 | ||
36 | /* | |
37 | * RCU double-ended queue (DQ). | |
38 | * | |
39 | * Allow consistent forward and backward traversal of the DQ. For | |
40 | * instance, given traversals occurring concurrently with a | |
41 | * cds_rcudq_add() operation, if a node is seen by a forward RCU | |
42 | * traversal, it will be seen by a following backward RCU traversal. The | |
43 | * reverse is also true: if seen by backward RCU traversal, it will be | |
44 | * seen by a following forward traversal. | |
45 | * | |
46 | * For node deletion, if forward and backward traversals execute | |
47 | * concurrently with cds_rcudq_del(), if the node is not seen by a | |
48 | * forward traversal, any following backward traversal is guaranteed not | |
49 | * to see it. Likewise for backward traversal followed by forward | |
50 | * traversal. | |
51 | * | |
52 | * Updates are RCU-aware. RCU-protected traversals end with _rcu | |
53 | * suffix. | |
54 | */ | |
55 | ||
56 | #define CDS_RCUDQ_FLAG_SKIP (1U << 0) /* Traversal should skip node */ | |
57 | ||
58 | /* Basic type for the DQ. */ | |
59 | struct cds_rcudq_head { | |
60 | struct cds_rcudq_head *next, *prev; | |
61 | unsigned int flags; | |
62 | }; | |
63 | ||
64 | #define CDS_RCUDQ_HEAD_INIT(name) \ | |
65 | { .prev = &(name), .next = &(name), .flags = 0 } | |
66 | ||
67 | /* Define a variable with the head and tail of the DQ. */ | |
68 | #define CDS_RCUDQ_HEAD(name) \ | |
69 | struct cds_rcudq_head name = CDS_RCUDQ_HEAD_INIT(name) | |
70 | ||
71 | /* Initialize a new DQ head. */ | |
72 | #define CDS_INIT_RCUDQ_HEAD(ptr) \ | |
73 | do { \ | |
74 | (ptr)->next = (ptr)->prev = (ptr); \ | |
75 | (ptr)->flags = 0; \ | |
76 | } while (0) | |
77 | ||
78 | /* Add new element at the head of the DQ. */ | |
79 | static inline | |
80 | void cds_rcudq_add(struct cds_rcudq_head *newp, struct cds_rcudq_head *head) | |
81 | { | |
82 | newp->next = head->next; | |
83 | newp->prev = head; | |
84 | newp->flags = CDS_RCUDQ_FLAG_SKIP; | |
85 | cmm_smp_wmb(); /* Initialize newp before adding to dq */ | |
86 | _CMM_STORE_SHARED(head->next->prev, newp); | |
87 | _CMM_STORE_SHARED(head->next, newp); | |
88 | cmm_smp_wmb(); /* Order adding to dq before showing node */ | |
89 | CMM_STORE_SHARED(newp->flags, 0); /* Show node */ | |
90 | } | |
91 | ||
92 | /* Add new element at the tail of the DQ. */ | |
93 | static inline | |
94 | void cds_rcudq_add_tail(struct cds_rcudq_head *newp, | |
95 | struct cds_rcudq_head *head) | |
96 | { | |
97 | newp->next = head; | |
98 | newp->prev = head->prev; | |
99 | newp->flags = CDS_RCUDQ_FLAG_SKIP; | |
100 | cmm_smp_wmb(); /* Initialize newp before adding to dq */ | |
101 | _CMM_STORE_SHARED(head->prev->next, newp); | |
102 | _CMM_STORE_SHARED(head->prev, newp); | |
103 | cmm_smp_wmb(); /* Order adding to dq before showing node */ | |
104 | CMM_STORE_SHARED(newp->flags, 0); /* Show node */ | |
105 | } | |
106 | ||
107 | /* Remove element from list. */ | |
108 | static inline | |
109 | void cds_rcudq_del(struct cds_rcudq_head *elem) | |
110 | { | |
111 | _CMM_STORE_SHARED(elem->flags, CDS_RCUDQ_FLAG_SKIP); /* Hide node */ | |
112 | cmm_smp_wmb(); /* Order hiding node before removing from dq */ | |
113 | _CMM_STORE_SHARED(elem->next->prev, elem->prev); | |
114 | CMM_STORE_SHARED(elem->prev->next, elem->next); | |
115 | } | |
116 | ||
117 | static inline | |
118 | int cds_rcudq_empty(struct cds_rcudq_head *head) | |
119 | { | |
120 | return head == CMM_LOAD_SHARED(head->next); | |
121 | } | |
122 | ||
123 | /* Get typed element from list at a given position. */ | |
124 | #define cds_rcudq_entry(ptr, type, member) \ | |
125 | caa_container_of(ptr, type, member) | |
126 | ||
127 | /* | |
128 | * Traversals NOT RCU-protected. Need mutual exclusion against updates. | |
129 | */ | |
130 | ||
131 | /* Get first entry from a list. */ | |
132 | #define cds_rcudq_first_entry(ptr, type, member) \ | |
133 | cds_rcudq_entry((ptr)->next, type, member) | |
134 | ||
135 | /* Iterate forward over the elements of the list. */ | |
136 | #define cds_rcudq_for_each(pos, head) \ | |
137 | for (pos = (head)->next; pos != (head); pos = pos->next) | |
138 | ||
139 | /* | |
140 | * Iterate forward over the elements list. The list elements can be | |
141 | * removed from the list while doing this. | |
142 | */ | |
143 | #define cds_rcudq_for_each_safe(pos, p, head) \ | |
144 | for (pos = (head)->next, p = pos->next; \ | |
145 | pos != (head); \ | |
146 | pos = p, p = pos->next) | |
147 | ||
148 | #define cds_rcudq_for_each_entry(pos, head, member) \ | |
149 | for (pos = cds_rcudq_entry((head)->next, __typeof__(*pos), member); \ | |
150 | &pos->member != (head); \ | |
151 | pos = cds_rcudq_entry(pos->member.next, __typeof__(*pos), member)) | |
152 | ||
153 | #define cds_rcudq_for_each_entry_safe(pos, p, head, member) \ | |
154 | for (pos = cds_rcudq_entry((head)->next, __typeof__(*pos), member), \ | |
155 | p = cds_rcudq_entry(pos->member.next, __typeof__(*pos), member); \ | |
156 | &pos->member != (head); \ | |
157 | pos = p, p = cds_rcudq_entry(pos->member.next, __typeof__(*pos), member)) | |
158 | ||
159 | /* Iterate backward over the elements of the list. */ | |
160 | #define cds_rcudq_for_each_reverse(pos, head) \ | |
161 | for (pos = (head)->prev; pos != (head); pos = pos->prev) | |
162 | ||
163 | /* | |
164 | * Iterate backward over the elements list. The list elements can be | |
165 | * removed from the list while doing this. | |
166 | */ | |
167 | #define cds_rcudq_for_each_reverse_safe(pos, p, head) \ | |
168 | for (pos = (head)->prev, p = pos->prev; \ | |
169 | pos != (head); \ | |
170 | pos = p, p = pos->prev) | |
171 | ||
172 | #define cds_rcudq_for_each_entry_reverse(pos, head, member) \ | |
173 | for (pos = cds_rcudq_entry((head)->prev, __typeof__(*pos), member); \ | |
174 | &pos->member != (head); \ | |
175 | pos = cds_rcudq_entry(pos->member.prev, __typeof__(*pos), member)) | |
176 | ||
177 | #define cds_rcudq_for_each_entry_reverse_safe(pos, p, head, member) \ | |
178 | for (pos = cds_rcudq_entry((head)->prev, __typeof__(*pos), member), \ | |
179 | p = cds_rcudq_entry(pos->member.prev, __typeof__(*pos), member); \ | |
180 | &pos->member != (head); \ | |
181 | pos = p, p = cds_rcudq_entry(pos->member.prev, __typeof__(*pos), member)) | |
182 | ||
183 | ||
184 | /* | |
185 | * RCU-protected traversals. | |
186 | * | |
187 | * Iteration through all elements of the list must be done while rcu_read_lock() | |
188 | * is held. cds_rcudq_get_next/cds_rcudq_get_prev are helpers to get the | |
189 | * next and previous DQ nodes in RCU traversal. | |
190 | */ | |
191 | ||
192 | static inline struct cds_rcudq_head *cds_rcudq_get_next(struct cds_rcudq_head *pos, | |
193 | struct cds_rcudq_head *head) | |
194 | { | |
195 | unsigned int flags; | |
196 | ||
197 | do { | |
198 | pos = rcu_dereference(pos->next); | |
199 | /* Implicit read barrier ordering load of next pointer before flags */ | |
200 | flags = CMM_LOAD_SHARED(pos->flags); | |
201 | assert(!(flags & CDS_RCUDQ_FLAG_SKIP && pos == head)); | |
202 | } while (flags & CDS_RCUDQ_FLAG_SKIP); | |
203 | return pos; | |
204 | } | |
205 | ||
206 | static inline struct cds_rcudq_head *cds_rcudq_get_prev(struct cds_rcudq_head *pos, | |
207 | struct cds_rcudq_head *head) | |
208 | { | |
209 | unsigned int flags; | |
210 | ||
211 | do { | |
212 | pos = rcu_dereference(pos->prev); | |
213 | /* Implicit read barrier ordering load of prev pointer before flags */ | |
214 | flags = CMM_LOAD_SHARED(pos->flags); | |
215 | assert(!(flags & CDS_RCUDQ_FLAG_SKIP && pos == head)); | |
216 | } while (flags & CDS_RCUDQ_FLAG_SKIP); | |
217 | return pos; | |
218 | } | |
219 | ||
220 | /* Iterate forward over the elements of the list. RCU-protected. */ | |
221 | #define cds_rcudq_for_each_rcu(pos, head) \ | |
222 | for (pos = cds_rcudq_get_next(head, head); pos != (head); \ | |
223 | pos = cds_rcudq_get_next(pos, head)) | |
224 | ||
225 | /* Iterate forward through elements of the list. RCU-protected. */ | |
226 | #define cds_rcudq_for_each_entry_rcu(pos, head, member) \ | |
227 | for (pos = cds_rcudq_entry(cds_rcudq_get_next(head, head), __typeof__(*pos), member); \ | |
228 | &pos->member != (head); \ | |
229 | pos = cds_rcudq_entry(cds_rcudq_get_next(&pos->member, head), __typeof__(*pos), member)) | |
230 | ||
231 | /* Iterate backward over the elements of the list. RCU-protected. */ | |
232 | #define cds_rcudq_for_each_reverse_rcu(pos, head) \ | |
233 | for (pos = cds_rcudq_get_prev(head, head); pos != (head); \ | |
234 | pos = cds_rcudq_get_prev(pos, head)) | |
235 | ||
236 | /* Iterate forward through elements of the list. RCU-protected. */ | |
237 | #define cds_rcudq_for_each_entry_reverse_rcu(pos, head, member) \ | |
238 | for (pos = cds_rcudq_entry(cds_rcudq_get_prev(head, head), __typeof__(*pos), member); \ | |
239 | &pos->member != (head); \ | |
240 | pos = cds_rcudq_entry(cds_rcudq_get_prev(&pos->member, head), __typeof__(*pos), member)) | |
241 | ||
242 | #ifdef __cplusplus | |
243 | } | |
244 | #endif | |
245 | ||
246 | #endif /* _CDS_RCUDQ_H */ |