mpsc_node_stack.h
8.8 KB
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
#pragma once
#include "../C/Baselib_Memory.h"
#include "../C/Baselib_Atomic_LLSC.h"
#include "mpsc_node.h"
namespace baselib
{
BASELIB_CPP_INTERFACE
{
// In computer science, a stack is an abstract data type that serves as a collection of elements, with two principal operations:
// * push, which adds an element to the collection, and
// * pop, which removes the most recently added element that was not yet removed.
// The order in which elements come off a stack gives rise to its alternative name, LIFO (last in, first out).
// Additionally, a peek operation may give access to the top without modifying the stack.
// The name "stack" for this type of structure comes from the analogy to a set of physical items stacked on top of each other,
// which makes it easy to take an item off the top of the stack, while getting to an item deeper in the stack may require taking off multiple other items first.
// Considered as a linear data structure, or more abstractly a sequential collection, the push and pop operations occur only at one end of the structure,
// referred to as the top of the stack. This makes it possible to implement a stack as a singly linked list and a pointer to the top element.
// A stack may be implemented to have a bounded capacity. If the stack is full and does not contain enough space to accept an entity to be pushed,
// the stack is then considered to be in an overflow state. The pop operation removes an item from the top of the stack.
//
// "Stack (abstract data type)", Wikipedia: The Free Encyclopedia
// https://en.wikipedia.org/wiki/Stack_(abstract_data_type)
//
// This implementation is a lockless node stack capable of handling multiple producers and a single consumer (exclusive access)
//
// Node types are required to inherit the mpsc_node class. No data from the inherited class is modified/copied, so no restrictions apply.
// The node memory is allocated and destroyed by the user (user owned).
// Popped nodes may be deleted, overwritten/discarded and/or reused.
//
// Notes consumer threads:
// Only one consumer thread will exclusively access the top node. Other consumer threads will always progress, either by failing to pop or
// successfully pop the next node once the current thread thread opens access i.e. if the consumer thread with current exclusive access falls asleep
// when popping, no other threads will successfully pop until the thread wakes up.
// Producer threads always progress independently.
//
template<typename T>
class alignas(sizeof(intptr_t) * 2)mpsc_node_stack
{
public:
// Create a new stack instance.
mpsc_node_stack()
{
m_Top.obj.ptr = 0;
m_Top.obj.idx = 0;
m_ConsumerLock.obj = false;
atomic_thread_fence(memory_order_seq_cst);
}
// Returns true if stack is empty.
bool empty() const
{
return m_Top.load(memory_order_relaxed).ptr == 0;
}
// Push a node to the top of the stack.
void push_back(T* node)
{
SequencedTopPtr newtop;
newtop.ptr = node;
if (PLATFORM_LLSC_NATIVE_SUPPORT)
{
Baselib_atomic_llsc_ptr_acquire_release_v(&m_Top, &node->next.obj, &newtop, );
}
else
{
SequencedTopPtr top = m_Top.load(memory_order_relaxed);
do
{
node->next.store(top.ptr, memory_order_relaxed);
newtop.idx = top.idx + 1;
}
while (!m_Top.compare_exchange_strong(top, newtop, memory_order_release, memory_order_relaxed));
}
}
// Push a linked list of nodes to the top of the stack.
void push_back(T* first_node, T* last_node)
{
SequencedTopPtr newtop;
newtop.ptr = first_node;
if (PLATFORM_LLSC_NATIVE_SUPPORT)
{
Baselib_atomic_llsc_ptr_acquire_release_v(&m_Top, &last_node->next.obj, &newtop, );
}
else
{
SequencedTopPtr top = m_Top.load(memory_order_relaxed);
do
{
last_node->next.store(top.ptr, memory_order_relaxed);
newtop.idx = top.idx + 1;
}
while (!m_Top.compare_exchange_strong(top, newtop, memory_order_release, memory_order_relaxed));
}
}
// Try to pop node from the top of the stack.
//
// Note that if null can be returned if another consumer thread has exclusive read access.
// Use the "empty" function to check if a stack is empty.
//
// \returns top node of the stack or null.
T* try_pop_back()
{
if (m_ConsumerLock.exchange(true, memory_order_acquire))
return 0;
T* node;
SequencedTopPtr newtop;
if (PLATFORM_LLSC_NATIVE_SUPPORT)
{
Baselib_atomic_llsc_ptr_acquire_release_v(&m_Top, &node, &newtop,
{
if (!node)
{
Baselib_atomic_llsc_break();
break;
}
newtop.ptr = static_cast<T*>(node->next.obj);
});
}
else
{
SequencedTopPtr top = m_Top.load(memory_order_relaxed);
do
{
node = top.ptr;
if (!node)
break;
newtop.ptr = static_cast<T*>(node->next.load(memory_order_relaxed));
newtop.idx = top.idx + 1;
}
while (!m_Top.compare_exchange_strong(top, newtop, memory_order_relaxed, memory_order_relaxed));
}
m_ConsumerLock.store(false, memory_order_release);
return node;
}
// Try to pop all nodes from the stack.
//
// Note that if null can be returned if another consumer thread has exclusive read access.
// Use the "empty" function to check if a stack is empty.
//
// \returns linked list of nodes or null.
T* try_pop_all()
{
if (m_ConsumerLock.exchange(true, memory_order_acquire))
return 0;
T* node;
SequencedTopPtr newtop;
newtop.ptr = 0;
if (PLATFORM_LLSC_NATIVE_SUPPORT)
{
Baselib_atomic_llsc_ptr_acquire_release_v(&m_Top, &node, &newtop,
{
if (!node)
{
Baselib_atomic_llsc_break();
break;
}
});
}
else
{
SequencedTopPtr top = m_Top.load(memory_order_relaxed);
do
{
node = top.ptr;
if (!node)
break;
newtop.idx = top.idx + 1;
}
while (!m_Top.compare_exchange_strong(top, newtop, memory_order_relaxed, memory_order_relaxed));
}
m_ConsumerLock.store(false, memory_order_release);
return node;
}
private:
typedef struct
{
T* ptr;
intptr_t idx;
} SequencedTopPtr;
// Space out atomic members to individual cache lines. Required for native LLSC operations on some architectures, others to avoid false sharing
char _cachelineSpacer0[PLATFORM_CACHE_LINE_SIZE];
atomic<SequencedTopPtr> m_Top;
char _cachelineSpacer1[PLATFORM_CACHE_LINE_SIZE - sizeof(SequencedTopPtr)];
atomic<bool> m_ConsumerLock;
char _cachelineSpacer2[PLATFORM_CACHE_LINE_SIZE - sizeof(bool)];
// Verify mpsc_node is base of T
static_assert(std::is_base_of<baselib::mpsc_node, T>::value, "Node class/struct used with baselib::mpsc_node_stack must derive from baselib::mpsc_node.");
};
}
}