Commit | Line | Data |
---|---|---|
3d02c34d MD |
1 | #ifndef _URCU_RCULFQUEUE_STATIC_H |
2 | #define _URCU_RCULFQUEUE_STATIC_H | |
3 | ||
4 | /* | |
5 | * rculfqueue-static.h | |
6 | * | |
7 | * Userspace RCU library - Lock-Free RCU Queue | |
8 | * | |
9 | * Copyright 2010 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com> | |
10 | * | |
11 | * TO BE INCLUDED ONLY IN LGPL-COMPATIBLE CODE. See rculfqueue.h for linking | |
12 | * dynamically with the userspace rcu library. | |
13 | * | |
14 | * This library is free software; you can redistribute it and/or | |
15 | * modify it under the terms of the GNU Lesser General Public | |
16 | * License as published by the Free Software Foundation; either | |
17 | * version 2.1 of the License, or (at your option) any later version. | |
18 | * | |
19 | * This library is distributed in the hope that it will be useful, | |
20 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
21 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
22 | * Lesser General Public License for more details. | |
23 | * | |
24 | * You should have received a copy of the GNU Lesser General Public | |
25 | * License along with this library; if not, write to the Free Software | |
26 | * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA | |
27 | */ | |
28 | ||
f9bf6d54 | 29 | #include <urcu/ref.h> |
a2e7bf9c | 30 | #include <urcu/uatomic.h> |
3d02c34d MD |
31 | #include <assert.h> |
32 | /* A urcu implementation header should be already included. */ | |
33 | ||
34 | #ifdef __cplusplus | |
35 | extern "C" { | |
36 | #endif | |
37 | ||
38 | /* | |
39 | * Lock-free RCU queue using reference counting. Enqueue and dequeue operations | |
40 | * hold a RCU read lock to deal with cmpxchg ABA problem. This implementation | |
41 | * keeps a dummy head node to ensure we can always update the queue locklessly. | |
42 | * Given that this is a queue, the dummy head node must always advance as we | |
43 | * dequeue entries. Therefore, we keep a reference count on each entry we are | |
44 | * dequeueing, so they can be kept as dummy head node until the next dequeue, at | |
45 | * which point their reference count will be decremented. | |
46 | */ | |
47 | ||
48 | #define URCU_LFQ_PERMANENT_REF 128 | |
49 | ||
16aa9ee8 | 50 | void _cds_lfq_node_init_rcu(struct cds_lfq_node_rcu *node) |
3d02c34d MD |
51 | { |
52 | node->next = NULL; | |
53 | urcu_ref_init(&node->ref); | |
54 | } | |
55 | ||
d9b52143 MD |
56 | void _cds_lfq_init_rcu(struct cds_lfq_queue_rcu *q, |
57 | void (*release)(struct urcu_ref *ref)) | |
3d02c34d | 58 | { |
16aa9ee8 | 59 | _cds_lfq_node_init_rcu(&q->init); |
3d02c34d MD |
60 | /* Make sure the initial node is never freed. */ |
61 | urcu_ref_set(&q->init.ref, URCU_LFQ_PERMANENT_REF); | |
62 | q->head = q->tail = &q->init; | |
d9b52143 | 63 | q->release = release; |
3d02c34d MD |
64 | } |
65 | ||
d9b52143 MD |
66 | /* |
67 | * Should be called under rcu read lock critical section. | |
68 | */ | |
69 | void _cds_lfq_enqueue_rcu(struct cds_lfq_queue_rcu *q, | |
70 | struct cds_lfq_node_rcu *node) | |
3d02c34d MD |
71 | { |
72 | urcu_ref_get(&node->ref); | |
d9b52143 | 73 | node->queue = q; |
3d02c34d MD |
74 | |
75 | /* | |
76 | * uatomic_cmpxchg() implicit memory barrier orders earlier stores to | |
77 | * node before publication. | |
78 | */ | |
79 | ||
80 | for (;;) { | |
16aa9ee8 | 81 | struct cds_lfq_node_rcu *tail, *next; |
3d02c34d | 82 | |
3d02c34d MD |
83 | tail = rcu_dereference(q->tail); |
84 | /* | |
85 | * Typically expect tail->next to be NULL. | |
86 | */ | |
87 | next = uatomic_cmpxchg(&tail->next, NULL, node); | |
88 | if (next == NULL) { | |
89 | /* | |
90 | * Tail was at the end of queue, we successfully | |
91 | * appended to it. | |
92 | * Now move tail (another enqueue might beat | |
93 | * us to it, that's fine). | |
94 | */ | |
85b57703 | 95 | (void) uatomic_cmpxchg(&q->tail, tail, node); |
3d02c34d MD |
96 | return; |
97 | } else { | |
98 | /* | |
99 | * Failure to append to current tail. Help moving tail | |
100 | * further and retry. | |
101 | */ | |
85b57703 | 102 | (void) uatomic_cmpxchg(&q->tail, tail, next); |
3d02c34d MD |
103 | continue; |
104 | } | |
105 | } | |
106 | } | |
107 | ||
108 | /* | |
d9b52143 MD |
109 | * Should be called under rcu read lock critical section. |
110 | * | |
111 | * The entry returned by dequeue must be taken care of by doing a | |
a34df756 | 112 | * sequence of urcu_ref_put which release handler should do a call_rcu. |
d9b52143 | 113 | * |
3d02c34d MD |
114 | * In other words, the entry lfq node returned by dequeue must not be |
115 | * modified/re-used/freed until the reference count reaches zero and a grace | |
d9b52143 | 116 | * period has elapsed. |
3d02c34d | 117 | */ |
a34df756 | 118 | struct cds_lfq_node_rcu *_cds_lfq_dequeue_rcu(struct cds_lfq_queue_rcu *q) |
3d02c34d MD |
119 | { |
120 | for (;;) { | |
16aa9ee8 | 121 | struct cds_lfq_node_rcu *head, *next; |
3d02c34d | 122 | |
3d02c34d MD |
123 | head = rcu_dereference(q->head); |
124 | next = rcu_dereference(head->next); | |
125 | if (next) { | |
126 | if (uatomic_cmpxchg(&q->head, head, next) == head) { | |
d9b52143 | 127 | urcu_ref_put(&head->ref, q->release); |
3d02c34d MD |
128 | return next; |
129 | } else { | |
130 | /* Concurrently pushed, retry */ | |
3d02c34d MD |
131 | continue; |
132 | } | |
133 | } else { | |
134 | /* Empty */ | |
3d02c34d MD |
135 | return NULL; |
136 | } | |
137 | } | |
138 | } | |
139 | ||
140 | #ifdef __cplusplus | |
141 | } | |
142 | #endif | |
143 | ||
144 | #endif /* _URCU_RCULFQUEUE_STATIC_H */ |