3 #ifndef INCLUDE_NN_NLIB_LOCKFREE_H_ 4 #define INCLUDE_NN_NLIB_LOCKFREE_H_ 11 #include "nn/nlib/Swap.h" 15 template<
class T1,
class T2 =
void>
16 struct LockFreePlaceHolder {
20 LockFreePlaceHolder<T1, T2>* raw_ptr;
30 struct LockFreePlaceHolder<T1, void> {
34 LockFreePlaceHolder<T1, void>* raw_ptr;
41 template<
class T1,
class T2 =
void>
42 class LockFreePlaceHolderPool {
44 #if !defined(CAFE) && !defined(NN_PLATFORM_CTR) 48 LockFreePlaceHolderPool()
NLIB_NOEXCEPT : invariant_(0), mask_(0), mem_(NULL) {}
51 NLIB_ALWAYS_INLINE LockFreePlaceHolder<T1, T2>* CalcPtr(uintptr_t aba)
const NLIB_NOEXCEPT {
52 return reinterpret_cast<LockFreePlaceHolder<T1, T2>*
>((aba & mask_) | invariant_);
58 LockFreePlaceHolder<T1, T2>* ptr;
59 uintptr_t expected = Load(&freelist_);
62 ptr = this->CalcPtr(expected);
63 uintptr_t desired = Load(&ptr->next.aba_ptr);
64 if (
NLIB_LIKELY(Cas(&freelist_, &expected, &desired, 1)))
67 uintptr_t mask = mask_;
68 ptr->next.aba_ptr = (ptr->next.aba_ptr & ~mask) + (mask + 2);
72 uintptr_t mask = mask_;
73 uintptr_t desired =
reinterpret_cast<uintptr_t
>(p);
74 uintptr_t expected = Load(&freelist_);
75 uintptr_t base = (p->next.aba_ptr & ~mask) + (mask + 1);
77 Store(&p->next.aba_ptr, base | (expected & mask));
84 uintptr_t expected = freelist_;
86 LockFreePlaceHolder<T1, T2>* ptr = this->CalcPtr(expected);
87 freelist_ = ptr->next.aba_ptr;
88 ptr->next.aba_ptr = 1;
92 p->next.aba_ptr = freelist_;
93 freelist_ =
reinterpret_cast<uintptr_t
>(p);
97 return reinterpret_cast<uintptr_t
>(val);
101 return reinterpret_cast<uintptr_t
>(val);
105 reinterpret_cast<void*>(value),
111 reinterpret_cast<void*>(value),
114 NLIB_ALWAYS_INLINE int Cas(uintptr_t* ptr, uintptr_t* expected, uintptr_t* desired,
int weak,
115 int success_memorder,
int failure_memorder)
117 uintptr_t mask = mask_;
118 *desired = ((*desired & mask) | (mask + 1)) + (*expected & ~mask);
120 reinterpret_cast<void**>(expected),
121 reinterpret_cast<void*>(*desired),
122 weak, success_memorder, failure_memorder);
125 NLIB_ALWAYS_INLINE int Cas(uintptr_t* ptr, uintptr_t* expected, uintptr_t* desired,
int weak,
133 void SwapUnsafe(LockFreePlaceHolderPool& rhs)
NLIB_NOEXCEPT {
134 std::swap(freelist_, rhs.freelist_);
135 std::swap(invariant_, rhs.invariant_);
136 std::swap(mask_, rhs.mask_);
137 std::swap(mem_, rhs.mem_);
145 errno_t PushUnsafe(uintptr_t* stack,
const T1& elem) NLIB_NOEXCEPT {
146 typedef LockFreePlaceHolder<T1, T2> item_type;
147 item_type* item_ptr = AllocUnsafe();
151 item_ptr->data = elem;
152 item_ptr->next.aba_ptr = *stack;
153 *stack =
reinterpret_cast<uintptr_t
>(item_ptr);
156 errno_t PopUnsafe(uintptr_t* stack, T1* elem) NLIB_NOEXCEPT {
158 LockFreePlaceHolder<T1, T2>* ptr = CalcPtr(*stack);
160 *stack = ptr->next.aba_ptr;
164 errno_t EnqueueUnsafe(uintptr_t* tail,
const T1& elem) NLIB_NOEXCEPT {
165 LockFreePlaceHolder<T1, T2>* item_ptr = AllocUnsafe();
169 item_ptr->data = elem;
170 CalcPtr(*tail)->next.aba_ptr = reinterpret_cast<uintptr_t>(item_ptr);
171 *tail =
reinterpret_cast<uintptr_t
>(item_ptr);
174 errno_t DequeueUnsafe(uintptr_t* head, uintptr_t* tail, T1* elem) NLIB_NOEXCEPT {
175 typedef LockFreePlaceHolder<T1, T2> item_type;
176 item_type* first_ptr = CalcPtr(*head);
177 item_type* last_ptr = CalcPtr(*tail);
178 if (first_ptr == last_ptr)
return EAGAIN;
180 uintptr_t first_next = first_ptr->next.aba_ptr;
181 item_type* first_next_ptr = CalcPtr(first_next);
182 *elem = first_next_ptr->data;
184 FreeUnsafe(first_ptr);
190 uintptr_t invariant_;
192 LockFreePlaceHolder<T1, T2>* mem_;
196 template<
class T1,
class T2>
197 errno_t LockFreePlaceHolderPool<T1, T2>::Init(
size_t count) NLIB_NOEXCEPT {
199 LockFreePlaceHolder<T1, T2>* mem =
new (std::nothrow) LockFreePlaceHolder<T1, T2>[count];
201 uintptr_t freelist = 1;
203 for (
size_t j = 0; j < 4; ++j) {
204 for (
size_t i = j; i < count; i += 4) {
205 mem[i].next.aba_ptr = freelist;
207 freelist =
reinterpret_cast<uintptr_t
>(&mem[i]);
211 for (
size_t j = 0; j < 8; ++j) {
212 for (
size_t i = j; i < count; i += 8) {
213 mem[i].next.aba_ptr = freelist;
215 freelist =
reinterpret_cast<uintptr_t
>(&mem[i]);
219 uintptr_t first =
reinterpret_cast<uintptr_t
>(mem);
220 uintptr_t last =
reinterpret_cast<uintptr_t
>(mem + count);
224 int sft = nlib_clz(first ^ last);
226 freelist_ = freelist;
227 mask_ = (
static_cast<uintptr_t
>(0) - 1) >> sft;
228 invariant_ = first & ~mask_;
233 template<
class T1,
class T2>
235 uintptr_t* stack,
const T1& elem) NLIB_NOEXCEPT NLIB_NO_TSAN {
236 typedef LockFreePlaceHolder<T1, T2> item_type;
237 item_type* item_ptr = Alloc();
241 item_ptr->data = elem;
242 uintptr_t mask = mask_;
243 uintptr_t desired =
reinterpret_cast<uintptr_t
>(item_ptr);
244 uintptr_t expected = Load(&freelist_);
245 uintptr_t base = (item_ptr->next.aba_ptr & ~mask) + (mask + 1);
247 Store(&item_ptr->next.aba_ptr, base | (expected & mask));
255 template<
class T1,
class T2>
257 uintptr_t* stack, T1* elem) NLIB_NOEXCEPT NLIB_NO_TSAN {
258 LockFreePlaceHolder<T1, T2>* ptr;
259 uintptr_t expected = Load(stack);
262 ptr = this->CalcPtr(expected);
263 uintptr_t desired = Load(&ptr->next.aba_ptr);
264 if (
NLIB_LIKELY(Cas(stack, &expected, &desired, 1)))
272 template<
class T1,
class T2>
274 uintptr_t* tail,
const T1& elem) NLIB_NOEXCEPT NLIB_NO_TSAN {
275 LockFreePlaceHolder<T1, T2>* item_ptr = Alloc();
279 item_ptr->Init(elem);
280 #if !defined(_M_IX86) && !defined(_M_AMD64) && !defined(__i386__) && !defined(__x86_64__) 283 uintptr_t last = Load(tail);
285 uintptr_t* last_next_ptr = &CalcPtr(last)->next.aba_ptr;
286 uintptr_t last_next = Load(last_next_ptr,
288 uintptr_t last_new = Load(tail);
292 reinterpret_cast<uintptr_t*>(&item_ptr),
295 Cas(tail, &last, reinterpret_cast<uintptr_t*>(&item_ptr), 0);
300 if (
NLIB_LIKELY(Cas(tail, &last, &last_next, 0))) {
310 template<
class T1,
class T2>
312 uintptr_t* head, uintptr_t* tail, T1* elem) NLIB_NOEXCEPT NLIB_NO_TSAN {
313 typedef LockFreePlaceHolder<T1, T2> item_type;
316 uintptr_t last = Load(tail);
318 item_type* first_ptr = CalcPtr(first);
319 item_type* last_ptr = CalcPtr(last);
320 uintptr_t first_next = Load(&first_ptr->next.aba_ptr,
322 uintptr_t first_new = Load(head);
328 if (
NLIB_LIKELY(Cas(tail, &last, &first_next, 0))) {
332 item_type* first_next_ptr = CalcPtr(first_next);
333 *elem = first_next_ptr->data;
334 if (
NLIB_LIKELY(Cas(head, &first, &first_next, 0))) {
335 Free(CalcPtr(first));
364 uint32_t rofs_actual = rofs & (N - 1);
366 size_t ntail = N - rofs_actual;
367 if (ntail >= nbytes) {
371 reinterpret_cast<const void*>(&buffer_[rofs_actual]),
376 reinterpret_cast<const void*>(&buffer_[rofs_actual]),
378 nlib_memcpy(reinterpret_cast<void*>(reinterpret_cast<uint8_t*>(dest) + ntail),
380 reinterpret_cast<void*>(&buffer_[0]),
383 rofs +=
static_cast<uint32_t
>(nbytes);
394 if (
NLIB_UNLIKELY(nbytes > N - (wofs - rofs)))
return EAGAIN;
395 uint32_t wofs_actual = wofs & (N - 1);
397 size_t ntail = N - wofs_actual;
398 if (ntail >= nbytes) {
399 nlib_memcpy(reinterpret_cast<void*>(&buffer_[wofs_actual]),
404 nlib_memcpy(reinterpret_cast<void*>(&buffer_[wofs_actual]),
410 reinterpret_cast<const void*>(
411 reinterpret_cast<const uint8_t*>(src) + ntail),
414 wofs +=
static_cast<uint32_t
>(nbytes);
424 reinterpret_cast<int32_t*>(p), memorder));
426 NLIB_ALWAYS_INLINE void Store(uint32_t* p, uint32_t value,
int memorder) NLIB_NOEXCEPT {
428 static_cast<int32_t>(value), memorder);
440 T* operator()() NLIB_NOEXCEPT {
return new (std::nothrow) T(); }
446 void operator()(T* ptr) NLIB_NOEXCEPT {
delete ptr; }
464 errno_t Push(
const T& x) NLIB_NOEXCEPT {
return pool_.Push(&top_, x); }
465 errno_t Pop(PopType x) NLIB_NOEXCEPT {
return pool_.Pop(&top_, x); }
471 std::swap(top_, rhs.top_);
472 pool_.SwapUnsafe(rhs.pool_);
477 LockFreePlaceHolderPool<T> pool_;
488 while (0 == pool_.PopUnsafe(&top_, &elem)) {
494 errno_t Init(
size_t count) NLIB_NOEXCEPT {
500 errno_t Push(T* obj) NLIB_NOEXCEPT {
return pool_.Push(&top_, obj); }
501 errno_t Pop(PopType& obj) NLIB_NOEXCEPT {
504 if (e != 0)
return e;
509 errno_t PushUnsafe(T* obj) NLIB_NOEXCEPT {
return pool_.PushUnsafe(&top_, obj); }
511 errno_t PopUnsafe(PopType& obj) NLIB_NOEXCEPT {
514 if (e != 0)
return e;
519 std::swap(top_, rhs.top_);
520 pool_.SwapUnsafe(rhs.pool_);
525 LockFreePlaceHolderPool<T*> pool_;
538 errno_t e = pool_.Init(count + 1);
540 head_ = tail_ =
reinterpret_cast<uintptr_t
>(pool_.AllocUnsafe());
544 errno_t Dequeue(DequeueType x) NLIB_NOEXCEPT {
return pool_.Dequeue(&head_, &tail_, x); }
549 return pool_.DequeueUnsafe(&head_, &tail_, x);
552 std::swap(head_, rhs.head_);
553 std::swap(tail_, rhs.tail_);
554 pool_.SwapUnsafe(rhs.pool_);
560 LockFreePlaceHolderPool<T> pool_;
567 LockFreeQueue() NLIB_NOEXCEPT : head_(0), tail_(0), pool_() {}
571 while (0 == pool_.DequeueUnsafe(&head_, &tail_, &elem)) {
577 errno_t Init(
size_t count) NLIB_NOEXCEPT {
578 errno_t e = pool_.Init(count + 1);
580 head_ = tail_ =
reinterpret_cast<uintptr_t
>(pool_.AllocUnsafe());
583 errno_t Enqueue(T* obj) NLIB_NOEXCEPT {
return pool_.Enqueue(&tail_, obj); }
584 errno_t Dequeue(DequeueType& obj) NLIB_NOEXCEPT {
587 if (e != 0)
return e;
592 errno_t EnqueueUnsafe(T* x) NLIB_NOEXCEPT {
return pool_.EnqueueUnsafe(&tail_, x); }
594 errno_t DequeueUnsafe(DequeueType& obj) NLIB_NOEXCEPT {
597 if (e != 0)
return e;
602 std::swap(head_, rhs.head_);
603 std::swap(tail_, rhs.tail_);
604 pool_.SwapUnsafe(rhs.pool_);
610 LockFreePlaceHolderPool<T*> pool_;
618 NLIB_EINVAL_IFNULL(ptr);
624 return pold ? 0 : EAGAIN;
627 &pold, reinterpret_cast<void*>(obj), 0,
649 if (mq_.raw_handle != 0)
return EALREADY;
650 if (max_size > INT32_MAX)
return EINVAL;
652 attr.
flag = NLIB_MQ_LOCKFREE;
653 attr.
max_msg =
static_cast<int32_t
>(max_size);
654 attr.
destructor = LockFreePriorityQueue::dtor;
672 if (e != 0)
return e;
684 T* obj =
reinterpret_cast<T*
>(msg);
693 class LockFreeBroadcastQueueImpl {
694 typedef LockFreePlaceHolder<const void*, int32_t> item_type;
697 LockFreeBroadcastQueueImpl() NLIB_NOEXCEPT
698 : head_(1), tail_(1), listener_count_(0), pool_(), listeners_() {}
701 errno_t Enqueue(
const void* msg) NLIB_NOEXCEPT {
703 return pool_.Enqueue(&tail_, msg);
705 errno_t Dequeue(int32_t listener_id,
const void** msg) NLIB_NOEXCEPT {
708 NLIB_UNLIKELY(listener_id >= listener_count_))
return ERANGE;
709 uintptr_t& pos = listeners_[listener_id];
710 item_type* item = pool_.CalcPtr(pos);
711 uintptr_t next = item->next.aba_ptr;
712 if (pool_.IsNull(next))
return ENOENT;
713 *msg = pool_.CalcPtr(next)->data;
719 errno_t DeleteUnsafe(
const void** msg) NLIB_NOEXCEPT {
720 if (pool_.IsNull(head_))
return ENOENT;
721 item_type* item = pool_.CalcPtr(head_);
722 const void* p = item->data;
723 head_ = item->next.aba_ptr;
727 size_t GetListenerCount()
const NLIB_NOEXCEPT {
return listener_count_; }
728 void SwapUnsafe(LockFreeBroadcastQueueImpl& rhs) NLIB_NOEXCEPT {
729 std::swap(head_, rhs.head_);
730 std::swap(tail_, rhs.tail_);
731 std::swap(listener_count_, rhs.listener_count_);
732 pool_.SwapUnsafe(rhs.pool_);
733 listeners_.swap(rhs.listeners_);
745 int32_t listener_count_;
746 LockFreePlaceHolderPool<const void*, int32_t> pool_;
756 void operator()(
const T*) {}
762 while (impl_.DeleteUnsafe(&p) == 0) {
769 return impl_.Init(max_size, listeners);
773 return impl_.Enqueue(obj);
778 errno_t e = impl_.Dequeue(listener_id, &x);
779 if (e != 0)
return e;
780 obj.reset(reinterpret_cast<const T*>(x));
781 const T* p =
reinterpret_cast<const T*
>(impl_.CheckAndRemove());
789 return impl_.GetListenerCount();
792 impl_.SwapUnsafe(rhs);
796 detail::LockFreeBroadcastQueueImpl impl_;
803 void* Get() NLIB_NOEXCEPT {
return ptr_; }
818 return reinterpret_cast<MemHolder*
>(pool_.Alloc());
822 pool_.Free(
reinterpret_cast<LockFreePlaceHolder<void*>*
>(p));
829 return reinterpret_cast<MemHolder*
>(pool_.AllocUnsafe());
833 pool_.FreeUnsafe(
reinterpret_cast<LockFreePlaceHolder<void*>*
>(p));
837 pool_.SwapUnsafe(rhs.pool_);
842 LockFreePlaceHolderPool<void*> pool_;
848 #endif // INCLUDE_NN_NLIB_LOCKFREE_H_ void FreeUnsafe(MemHolder *p) noexcept
This function is similar to Free(), but not thread-safe.
errno_t PopUnsafe(PopType x) noexcept
Picks up an element from the stack and stores it in x. This is not thread-safe.
LockFreePipe() noexcept
Instantiates the object with default parameters (default constructor).
LockFreeQueue() noexcept
Instantiates the object with default parameters (default constructor).
Substitute definitions for the C++11 standard header type_traits. These substitute definitions are us...
UniquePtr< const T, empty_func > DequeueType
The type for the argument of Dequeue().
#define NLIB_DISALLOW_COPY_AND_ASSIGN(TypeName)
Prohibits use of the copy constructor and assignment operator for the class specified by TypeName...
errno_t Init(size_t count) noexcept
Initializes the stack. This is not thread-safe.
T * PopType
The type for the argument of Pop() and PopUnsafe().
LockFreeStack() noexcept
Instantiates the object with default parameters (default constructor).
~LockFreeQueue() noexcept
Destructor.
A class for obtaining aligned memory.
errno_t DequeueUnsafe(DequeueType x) noexcept
Picks up an element from the queue and stores it in x. This is not thread-safe.
size_t GetBufferSize() noexcept
Returns the buffer size. This is thread-safe.
UniquePtr owns the pointer, and when it goes out of scope, the pointer is released by the destructor ...
errno_t PushUnsafe(const T &x) noexcept
Places the element x in the stack. This is not thread-safe.
Defines that class that is corresponding to std::unique_ptr.
errno_t Pop(PopType x) noexcept
Picks up an element from the stack and stores it in x. This is thread-safe.
errno_t LockFreeInit(T **ptr) noexcept
Constructs an object in a thread safe manner.
void SwapUnsafe(LockFreePriorityQueue &rhs) noexcept
Swaps an object. This is not thread-safe.
errno_t EnqueueUnsafe(const T &x) noexcept
Adds the element x to the queue. This is not thread-safe.
A pool allocator that can allocate or free a fixed size of memory region in a lock free manner...
The specified number of listeners can obtain elements from the queue. After all the listeners have ob...
MemHolder * AllocUnsafe() noexcept
This function is similar to Alloc(), but not thread-safe.
errno_t Read(void *dest, size_t nbytes) noexcept
Reads data from a pipe. This is thread-safe.
void SwapUnsafe(LockFreeStack &rhs) noexcept
Swaps an object. This is not thread-safe.
errno_t Enqueue(T *obj, int prio) noexcept
Adds an element to the queue. This is thread-safe.
errno_t Enqueue(const T &x) noexcept
Adds the element x to the queue. This is thread-safe.
UniquePtr< T, DestructorForLockFree< T > > DequeueType
The type for the argument of Dequeue().
errno_t Write(const void *src, size_t nbytes) noexcept
Writes data to a pipe. This is thread-safe.
T * DequeueType
The type for the argument of Dequeue() and DequeueUnsafe().
This class implements a lock-free stack.
size_t GetListenerCount() const noexcept
Returns the number of listeners specified in Init(). This is thread-safe.
Class template for destructing an object. This should be specialized before use.
void SwapUnsafe(LockFreeQueue &rhs) noexcept
Swaps an object. This is not thread-safe.
MemHolder * Alloc() noexcept
Allocates memory. This is thread-safe.
void SwapUnsafe(LockFreeUnitHeap &rhs) noexcept
Swaps an object. This is not thread-safe.
Structure to store the settings and current status of a message queue.
This class implements a lock-free queue.
#define NLIB_NOEXCEPT
Defines noexcept geared to the environment, or the equivalent.
void SwapUnsafe(LockFreeBroadcastQueue &rhs) noexcept
Swaps an object. This is not thread-safe.
errno_t Dequeue(DequeueType &obj, int *prio) noexcept
Picks up an element from the queue. This is thread-safe.
A file that contains the configuration information for each development environment.
errno_t Close() noexcept
Closes the queue and restores it to the state before its initialization. This is not thread-safe...
errno_t Init(size_t count) noexcept
Initializes the queue. This is not thread-safe.
errno_t Dequeue(DequeueType x) noexcept
Picks up an element from the queue and stores it in x. This is thread-safe.
Used when aligned memory needs to be obtained.
errno_t Push(const T &x) noexcept
Places the element x in the stack. This is thread-safe.
LockFreeUnitHeap() noexcept
Instantiates the object with default parameters (default constructor).
errno_t Init(size_t max_size, size_t listeners) noexcept
Initializes the queue. This is not thread-safe.
When a single sender thread sends data and a single receiver thread receives that data...
#define NLIB_FINAL
Defines final if it is available for use. If not, holds an empty string.
errno_t Init(size_t max_size) noexcept
Initializes the queue. This is not thread-safe.
#define NLIB_STATIC_ASSERT(exp)
Defines a static assertion. Uses static_assert if it is available for use.
LockFreeBroadcastQueue() noexcept
Instantiates the object with default parameters (default constructor).
Class template for initializing an object. This should be specialized before use. ...
~LockFreeStack() noexcept
Destructor.
~LockFreeBroadcastQueue() noexcept
Destructor.
errno_t Dequeue(int32_t listener_id, DequeueType &obj) noexcept
Specifies the listener and then reads an element from the queue. This is thread-safe when using a dif...
void Free(MemHolder *p) noexcept
Frees memory. This is thread-safe.
LockFreePriorityQueue() noexcept
Instantiates the object with default parameters (default constructor).
Wraps nlib_mq with a class implementing a lock-free queue with a priority set.
~LockFreePriorityQueue() noexcept
Destructor.
errno_t Enqueue(const T *obj) noexcept
Adds an element to the queue. This is thread-safe.