rculfqueue: LGPL-ize
[urcu.git] / urcu / rculfqueue-static.h
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
29 #include <urcu/urcu_ref.h>
30 #include <urcu/uatomic_arch.h>
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
50 void _rcu_lfq_node_init(struct rcu_lfq_node *node)
51 {
52 node->next = NULL;
53 urcu_ref_init(&node->ref);
54 }
55
56 void _rcu_lfq_init(struct rcu_lfq_queue *q)
57 {
58 _rcu_lfq_node_init(&q->init);
59 /* Make sure the initial node is never freed. */
60 urcu_ref_set(&q->init.ref, URCU_LFQ_PERMANENT_REF);
61 q->head = q->tail = &q->init;
62 }
63
64 void _rcu_lfq_enqueue(struct rcu_lfq_queue *q, struct rcu_lfq_node *node)
65 {
66 urcu_ref_get(&node->ref);
67
68 /*
69 * uatomic_cmpxchg() implicit memory barrier orders earlier stores to
70 * node before publication.
71 */
72
73 for (;;) {
74 struct rcu_lfq_node *tail, *next;
75
76 rcu_read_lock();
77 tail = rcu_dereference(q->tail);
78 /*
79 * Typically expect tail->next to be NULL.
80 */
81 next = uatomic_cmpxchg(&tail->next, NULL, node);
82 if (next == NULL) {
83 /*
84 * Tail was at the end of queue, we successfully
85 * appended to it.
86 * Now move tail (another enqueue might beat
87 * us to it, that's fine).
88 */
89 uatomic_cmpxchg(&q->tail, tail, node);
90 rcu_read_unlock();
91 return;
92 } else {
93 /*
94 * Failure to append to current tail. Help moving tail
95 * further and retry.
96 */
97 uatomic_cmpxchg(&q->tail, tail, next);
98 rcu_read_unlock();
99 continue;
100 }
101 }
102 }
103
104 /*
105 * The entry returned by dequeue must be taken care of by doing a urcu_ref_put,
106 * which calls the release primitive when the reference count drops to zero. A
107 * grace period must be waited after execution of the release callback before
108 * performing the actual memory reclamation or modifying the rcu_lfq_node
109 * structure.
110 * In other words, the entry lfq node returned by dequeue must not be
111 * modified/re-used/freed until the reference count reaches zero and a grace
112 * period has elapsed (after the refcount reached 0).
113 */
114 struct rcu_lfq_node *
115 _rcu_lfq_dequeue(struct rcu_lfq_queue *q, void (*release)(struct urcu_ref *))
116 {
117 for (;;) {
118 struct rcu_lfq_node *head, *next;
119
120 rcu_read_lock();
121 head = rcu_dereference(q->head);
122 next = rcu_dereference(head->next);
123 if (next) {
124 if (uatomic_cmpxchg(&q->head, head, next) == head) {
125 rcu_read_unlock();
126 urcu_ref_put(&head->ref, release);
127 return next;
128 } else {
129 /* Concurrently pushed, retry */
130 rcu_read_unlock();
131 continue;
132 }
133 } else {
134 /* Empty */
135 rcu_read_unlock();
136 return NULL;
137 }
138 }
139 }
140
141 #ifdef __cplusplus
142 }
143 #endif
144
145 #endif /* _URCU_RCULFQUEUE_STATIC_H */
This page took 0.047075 seconds and 4 git commands to generate.