Commit | Line | Data |
---|---|---|
c3f74cb2 MD |
1 | #ifndef _URCU_RCULFQUEUE_H |
2 | #define _URCU_RCULFQUEUE_H | |
3 | ||
453629a9 MD |
4 | /* |
5 | * rculfqueue.h | |
6 | * | |
7 | * Userspace RCU library - Lock-Free RCU Queue | |
8 | * | |
9 | * Copyright 2010 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com> | |
10 | * | |
11 | * This library is free software; you can redistribute it and/or | |
12 | * modify it under the terms of the GNU Lesser General Public | |
13 | * License as published by the Free Software Foundation; either | |
14 | * version 2.1 of the License, or (at your option) any later version. | |
15 | * | |
16 | * This library is distributed in the hope that it will be useful, | |
17 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
18 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
19 | * Lesser General Public License for more details. | |
20 | * | |
21 | * You should have received a copy of the GNU Lesser General Public | |
22 | * License along with this library; if not, write to the Free Software | |
23 | * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA | |
24 | */ | |
25 | ||
f9bf6d54 | 26 | #include <urcu/ref.h> |
453629a9 MD |
27 | #include <assert.h> |
28 | ||
0e2e9380 MD |
29 | #ifdef __cplusplus |
30 | extern "C" { | |
31 | #endif | |
32 | ||
453629a9 MD |
33 | /* |
34 | * Lock-free RCU queue using reference counting. Enqueue and dequeue operations | |
35 | * hold a RCU read lock to deal with cmpxchg ABA problem. This implementation | |
36 | * keeps a dummy head node to ensure we can always update the queue locklessly. | |
37 | * Given that this is a queue, the dummy head node must always advance as we | |
38 | * dequeue entries. Therefore, we keep a reference count on each entry we are | |
39 | * dequeueing, so they can be kept as dummy head node until the next dequeue, at | |
40 | * which point their reference count will be decremented. | |
41 | */ | |
42 | ||
d9b52143 MD |
43 | struct cds_lfq_queue_rcu; |
44 | ||
16aa9ee8 DG |
45 | struct cds_lfq_node_rcu { |
46 | struct cds_lfq_node_rcu *next; | |
453629a9 | 47 | struct urcu_ref ref; |
d9b52143 MD |
48 | struct cds_lfq_queue_rcu *queue; |
49 | struct rcu_head rcu_head; | |
453629a9 MD |
50 | }; |
51 | ||
16aa9ee8 DG |
52 | struct cds_lfq_queue_rcu { |
53 | struct cds_lfq_node_rcu *head, *tail; | |
54 | struct cds_lfq_node_rcu init; /* Dummy initialization node */ | |
d9b52143 | 55 | void (*release)(struct urcu_ref *ref); |
453629a9 MD |
56 | }; |
57 | ||
3d02c34d | 58 | #ifdef _LGPL_SOURCE |
453629a9 | 59 | |
af7c2dbe | 60 | #include <urcu/static/rculfqueue.h> |
453629a9 | 61 | |
a34df756 | 62 | #define cds_lfq_node_init_rcu _cds_lfq_node_init_rcu |
16aa9ee8 DG |
63 | #define cds_lfq_init_rcu _cds_lfq_init_rcu |
64 | #define cds_lfq_enqueue_rcu _cds_lfq_enqueue_rcu | |
65 | #define cds_lfq_dequeue_rcu _cds_lfq_dequeue_rcu | |
453629a9 | 66 | |
3d02c34d | 67 | #else /* !_LGPL_SOURCE */ |
453629a9 | 68 | |
16aa9ee8 | 69 | extern void cds_lfq_node_init_rcu(struct cds_lfq_node_rcu *node); |
d9b52143 MD |
70 | extern void cds_lfq_init_rcu(struct cds_lfq_queue_rcu *q, |
71 | void (*release)(struct urcu_ref *ref)); | |
72 | ||
73 | /* | |
74 | * Should be called under rcu read lock critical section. | |
75 | */ | |
76 | extern void cds_lfq_enqueue_rcu(struct cds_lfq_queue_rcu *q, | |
77 | struct cds_lfq_node_rcu *node); | |
453629a9 MD |
78 | |
79 | /* | |
d9b52143 MD |
80 | * Should be called under rcu read lock critical section. |
81 | * | |
82 | * The entry returned by dequeue must be taken care of by doing a | |
a34df756 | 83 | * sequence of urcu_ref_put which release handler should do a call_rcu. |
d9b52143 | 84 | * |
c97740a3 MD |
85 | * In other words, the entry lfq node returned by dequeue must not be |
86 | * modified/re-used/freed until the reference count reaches zero and a grace | |
87 | * period has elapsed (after the refcount reached 0). | |
453629a9 | 88 | */ |
a34df756 MD |
89 | extern |
90 | struct cds_lfq_node_rcu *cds_lfq_dequeue_rcu(struct cds_lfq_queue_rcu *q); | |
453629a9 | 91 | |
3d02c34d | 92 | #endif /* !_LGPL_SOURCE */ |
c3f74cb2 | 93 | |
0e2e9380 MD |
94 | #ifdef __cplusplus |
95 | } | |
96 | #endif | |
97 | ||
c3f74cb2 | 98 | #endif /* _URCU_RCULFQUEUE_H */ |