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.
9 * Copyright (C) 2009 Pierre-Marc Fournier
10 * Copyright (C) 2010-2013 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
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.
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.
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
27 #include <urcu/arch.h>
28 #include <urcu/compiler.h>
29 #include <urcu-pointer.h>
37 * RCU double-ended queue (DQ).
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.
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
52 * Updates are RCU-aware. RCU-protected traversals end with _rcu
56 #define CDS_RCUDQ_FLAG_SKIP (1U << 0) /* Traversal should skip node */
58 /* Basic type for the DQ. */
59 struct cds_rcudq_head
{
60 struct cds_rcudq_head
*next
, *prev
;
64 #define CDS_RCUDQ_HEAD_INIT(name) \
65 { .prev = &(name), .next = &(name), .flags = 0 }
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)
71 /* Initialize a new DQ head. */
72 #define CDS_INIT_RCUDQ_HEAD(ptr) \
74 (ptr)->next = (ptr)->prev = (ptr); \
78 /* Add new element at the head of the DQ. */
80 void cds_rcudq_add(struct cds_rcudq_head
*newp
, struct cds_rcudq_head
*head
)
82 newp
->next
= head
->next
;
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 */
92 /* Add new element at the tail of the DQ. */
94 void cds_rcudq_add_tail(struct cds_rcudq_head
*newp
,
95 struct cds_rcudq_head
*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 */
107 /* Remove element from list. */
109 void cds_rcudq_del(struct cds_rcudq_head
*elem
)
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
);
118 int cds_rcudq_empty(struct cds_rcudq_head
*head
)
120 return head
== CMM_LOAD_SHARED(head
->next
);
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)
128 * Traversals NOT RCU-protected. Need mutual exclusion against updates.
131 /* Get first entry from a list. */
132 #define cds_rcudq_first_entry(ptr, type, member) \
133 cds_rcudq_entry((ptr)->next, type, member)
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)
140 * Iterate forward over the elements list. The list elements can be
141 * removed from the list while doing this.
143 #define cds_rcudq_for_each_safe(pos, p, head) \
144 for (pos = (head)->next, p = pos->next; \
146 pos = p, p = pos->next)
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))
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))
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)
164 * Iterate backward over the elements list. The list elements can be
165 * removed from the list while doing this.
167 #define cds_rcudq_for_each_reverse_safe(pos, p, head) \
168 for (pos = (head)->prev, p = pos->prev; \
170 pos = p, p = pos->prev)
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))
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))
185 * RCU-protected traversals.
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.
192 static inline struct cds_rcudq_head
*cds_rcudq_get_next(struct cds_rcudq_head
*pos
,
193 struct cds_rcudq_head
*head
)
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
);
206 static inline struct cds_rcudq_head
*cds_rcudq_get_prev(struct cds_rcudq_head
*pos
,
207 struct cds_rcudq_head
*head
)
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
);
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))
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))
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))
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))
246 #endif /* _CDS_RCUDQ_H */
This page took 0.049753 seconds and 4 git commands to generate.