/
MpscLinkedAtomicQueue.java
226 lines (213 loc) · 9.18 KB
/
MpscLinkedAtomicQueue.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
/*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package org.jctools.queues.atomic;
import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
import java.util.concurrent.atomic.AtomicLongFieldUpdater;
import org.jctools.queues.MessagePassingQueue;
import org.jctools.queues.MessagePassingQueue.Supplier;
import org.jctools.queues.MessagePassingQueueUtil;
import org.jctools.queues.QueueProgressIndicators;
import org.jctools.queues.IndexedQueueSizeUtil;
import static org.jctools.queues.atomic.LinkedAtomicArrayQueueUtil.*;
import java.util.concurrent.atomic.AtomicReferenceArray;
import org.jctools.queues.MpmcArrayQueue;
/**
* NOTE: This class was automatically generated by org.jctools.queues.atomic.JavaParsingAtomicLinkedQueueGenerator
* which can found in the jctools-build module. The original source file is MpscLinkedQueue.java.
* This is a direct Java port of the MPSC algorithm as presented
* <a href="http://www.1024cores.net/home/lock-free-algorithms/queues/non-intrusive-mpsc-node-based-queue"> on
* 1024 Cores</a> by D. Vyukov. The original has been adapted to Java and it's quirks with regards to memory
* model and layout:
* <ol>
* <li>Use inheritance to ensure no false sharing occurs between producer/consumer node reference fields.
* <li>Use XCHG functionality to the best of the JDK ability (see differences in JDK7/8 impls).
* </ol>
* The queue is initialized with a stub node which is set to both the producer and consumer node references.
* From this point follow the notes on offer/poll.
*
* @param <E> the type of elements in this queue
* @author nitsanw
*/
public class MpscLinkedAtomicQueue<E> extends BaseLinkedAtomicQueue<E> {
public MpscLinkedAtomicQueue() {
LinkedQueueAtomicNode<E> node = newNode();
spConsumerNode(node);
xchgProducerNode(node);
}
/**
* {@inheritDoc} <br>
* <p>
* IMPLEMENTATION NOTES:<br>
* Offer is allowed from multiple threads.<br>
* Offer allocates a new node and:
* <ol>
* <li>Swaps it atomically with current producer node (only one producer 'wins')
* <li>Sets the new node as the node following from the swapped producer node
* </ol>
* This works because each producer is guaranteed to 'plant' a new node and link the old node. No 2
* producers can get the same producer node as part of XCHG guarantee.
*
* @see MessagePassingQueue#offer(Object)
* @see java.util.Queue#offer(java.lang.Object)
*/
@Override
public final boolean offer(final E e) {
if (null == e) {
throw new NullPointerException();
}
final LinkedQueueAtomicNode<E> nextNode = newNode(e);
final LinkedQueueAtomicNode<E> prevProducerNode = xchgProducerNode(nextNode);
// Should a producer thread get interrupted here the chain WILL be broken until that thread is resumed
// and completes the store in prev.next.
// StoreStore
prevProducerNode.soNext(nextNode);
return true;
}
/**
* {@inheritDoc} <br>
* <p>
* IMPLEMENTATION NOTES:<br>
* Poll is allowed from a SINGLE thread.<br>
* Poll reads the next node from the consumerNode and:
* <ol>
* <li>If it is null, the queue is assumed empty (though it might not be).
* <li>If it is not null set it as the consumer node and return it's now evacuated value.
* </ol>
* This means the consumerNode.value is always null, which is also the starting point for the queue.
* Because null values are not allowed to be offered this is the only node with it's value set to null at
* any one time.
*
* @see MessagePassingQueue#poll()
* @see java.util.Queue#poll()
*/
@Override
public final E poll() {
// don't load twice, it's alright
LinkedQueueAtomicNode<E> currConsumerNode = lpConsumerNode();
LinkedQueueAtomicNode<E> nextNode = currConsumerNode.lvNext();
if (nextNode != null) {
return getSingleConsumerNodeValue(currConsumerNode, nextNode);
} else if (currConsumerNode != lvProducerNode()) {
nextNode = spinWaitForNextNode(currConsumerNode);
// got the next node...
return getSingleConsumerNodeValue(currConsumerNode, nextNode);
}
return null;
}
@Override
public final E peek() {
// don't load twice, it's alright
LinkedQueueAtomicNode<E> currConsumerNode = lpConsumerNode();
LinkedQueueAtomicNode<E> nextNode = currConsumerNode.lvNext();
if (nextNode != null) {
return nextNode.lpValue();
} else if (currConsumerNode != lvProducerNode()) {
nextNode = spinWaitForNextNode(currConsumerNode);
// got the next node...
return nextNode.lpValue();
}
return null;
}
/**
* {@inheritDoc}
* <p>
* This method is only safe to call from the (single) consumer thread, and is subject to best effort when racing
* with producers.
*/
@Override
public final boolean remove(Object o) {
if (null == o) {
// Null elements are not permitted, so null will never be removed.
return false;
}
final LinkedQueueAtomicNode<E> originalConsumerNode = lpConsumerNode();
LinkedQueueAtomicNode<E> prevConsumerNode = originalConsumerNode;
LinkedQueueAtomicNode<E> currConsumerNode = getNextConsumerNode(originalConsumerNode);
while (currConsumerNode != null) {
if (o.equals(currConsumerNode.lpValue())) {
LinkedQueueAtomicNode<E> nextNode = getNextConsumerNode(currConsumerNode);
// e.g.: consumerNode -> node0 -> node1(o==v) -> node2 ... => consumerNode -> node0 -> node2
if (nextNode != null) {
// We are removing an interior node.
prevConsumerNode.soNext(nextNode);
} else // This case reflects: prevConsumerNode != originalConsumerNode && nextNode == null
// At rest, this would be the producerNode, but we must contend with racing. Changes to subclassed
// queues need to consider remove() when implementing offer().
{
// producerNode is currConsumerNode, try to atomically update the reference to move it to the
// previous node.
prevConsumerNode.soNext(null);
if (!casProducerNode(currConsumerNode, prevConsumerNode)) {
// If the producer(s) have offered more items we need to remove the currConsumerNode link.
nextNode = spinWaitForNextNode(currConsumerNode);
prevConsumerNode.soNext(nextNode);
}
}
// Avoid GC nepotism because we are discarding the current node.
currConsumerNode.soNext(null);
currConsumerNode.spValue(null);
return true;
}
prevConsumerNode = currConsumerNode;
currConsumerNode = getNextConsumerNode(currConsumerNode);
}
return false;
}
@Override
public int fill(Supplier<E> s) {
// result is a long because we want to have a safepoint check at regular intervals
long result = 0;
do {
fill(s, 4096);
result += 4096;
} while (result <= Integer.MAX_VALUE - 4096);
return (int) result;
}
@Override
public int fill(Supplier<E> s, int limit) {
if (limit == 0) {
return 0;
}
LinkedQueueAtomicNode<E> tail = newNode(s.get());
final LinkedQueueAtomicNode<E> head = tail;
for (int i = 1; i < limit; i++) {
final LinkedQueueAtomicNode<E> temp = newNode(s.get());
tail.soNext(temp);
tail = temp;
}
final LinkedQueueAtomicNode<E> oldPNode = xchgProducerNode(tail);
oldPNode.soNext(head);
return limit;
}
@Override
public void fill(Supplier<E> s, WaitStrategy wait, ExitCondition exit) {
while (exit.keepRunning()) {
fill(s, 4096);
}
}
private LinkedQueueAtomicNode<E> getNextConsumerNode(LinkedQueueAtomicNode<E> currConsumerNode) {
LinkedQueueAtomicNode<E> nextNode = currConsumerNode.lvNext();
if (nextNode == null && currConsumerNode != lvProducerNode()) {
nextNode = spinWaitForNextNode(currConsumerNode);
}
return nextNode;
}
private LinkedQueueAtomicNode<E> spinWaitForNextNode(LinkedQueueAtomicNode<E> currNode) {
LinkedQueueAtomicNode<E> nextNode;
while ((nextNode = currNode.lvNext()) == null) {
// spin, we are no longer wait free
}
return nextNode;
}
}