16 #ifndef INCLUDE_NN_NLIB_LOCKFREE_H_ 17 #define INCLUDE_NN_NLIB_LOCKFREE_H_ 24 #include "nn/nlib/Swap.h" 28 template<
class T1,
class T2 =
void>
29 struct LockFreePlaceHolder {
33 LockFreePlaceHolder<T1, T2>* raw_ptr;
43 struct LockFreePlaceHolder<T1, void> {
47 LockFreePlaceHolder<T1, void>* raw_ptr;
54 template<
class T1,
class T2 =
void>
55 class LockFreePlaceHolderPool {
57 #if !defined(CAFE) && !defined(NN_PLATFORM_CTR) 61 LockFreePlaceHolderPool()
NLIB_NOEXCEPT : invariant_(0), mask_(0), mem_(NULL) {}
64 NLIB_ALWAYS_INLINE LockFreePlaceHolder<T1, T2>* CalcPtr(uintptr_t aba)
const NLIB_NOEXCEPT {
65 return reinterpret_cast<LockFreePlaceHolder<T1, T2>*
>((aba & mask_) | invariant_);
71 LockFreePlaceHolder<T1, T2>* ptr;
72 uintptr_t expected = Load(&freelist_);
75 ptr = this->CalcPtr(expected);
76 uintptr_t desired = Load(&ptr->next.aba_ptr);
77 if (
NLIB_LIKELY(Cas(&freelist_, &expected, &desired, 1)))
80 uintptr_t mask = mask_;
81 ptr->next.aba_ptr = (ptr->next.aba_ptr & ~mask) + (mask + 2);
85 uintptr_t mask = mask_;
86 uintptr_t desired =
reinterpret_cast<uintptr_t
>(p);
87 uintptr_t expected = Load(&freelist_);
88 uintptr_t base = (p->next.aba_ptr & ~mask) + (mask + 1);
90 Store(&p->next.aba_ptr, base | (expected & mask));
97 uintptr_t expected = freelist_;
99 LockFreePlaceHolder<T1, T2>* ptr = this->CalcPtr(expected);
100 freelist_ = ptr->next.aba_ptr;
101 ptr->next.aba_ptr = 1;
105 p->next.aba_ptr = freelist_;
106 freelist_ =
reinterpret_cast<uintptr_t
>(p);
110 return reinterpret_cast<uintptr_t
>(val);
114 return reinterpret_cast<uintptr_t
>(val);
118 reinterpret_cast<void*>(value),
124 reinterpret_cast<void*>(value),
127 NLIB_ALWAYS_INLINE int Cas(uintptr_t* ptr, uintptr_t* expected, uintptr_t* desired,
int weak,
128 int success_memorder,
int failure_memorder)
130 uintptr_t mask = mask_;
131 *desired = ((*desired & mask) | (mask + 1)) + (*expected & ~mask);
133 reinterpret_cast<void**>(expected),
134 reinterpret_cast<void*>(*desired),
135 weak, success_memorder, failure_memorder);
138 NLIB_ALWAYS_INLINE int Cas(uintptr_t* ptr, uintptr_t* expected, uintptr_t* desired,
int weak,
146 void SwapUnsafe(LockFreePlaceHolderPool& rhs)
NLIB_NOEXCEPT {
147 std::swap(freelist_, rhs.freelist_);
148 std::swap(invariant_, rhs.invariant_);
149 std::swap(mask_, rhs.mask_);
150 std::swap(mem_, rhs.mem_);
158 errno_t PushUnsafe(uintptr_t* stack,
const T1& elem) NLIB_NOEXCEPT {
159 typedef LockFreePlaceHolder<T1, T2> item_type;
160 item_type* item_ptr = AllocUnsafe();
164 item_ptr->data = elem;
165 item_ptr->next.aba_ptr = *stack;
166 *stack =
reinterpret_cast<uintptr_t
>(item_ptr);
169 errno_t PopUnsafe(uintptr_t* stack, T1* elem) NLIB_NOEXCEPT {
171 LockFreePlaceHolder<T1, T2>* ptr = CalcPtr(*stack);
173 *stack = ptr->next.aba_ptr;
177 errno_t EnqueueUnsafe(uintptr_t* tail,
const T1& elem) NLIB_NOEXCEPT {
178 LockFreePlaceHolder<T1, T2>* item_ptr = AllocUnsafe();
182 item_ptr->data = elem;
183 CalcPtr(*tail)->next.aba_ptr = reinterpret_cast<uintptr_t>(item_ptr);
184 *tail =
reinterpret_cast<uintptr_t
>(item_ptr);
187 errno_t DequeueUnsafe(uintptr_t* head, uintptr_t* tail, T1* elem) NLIB_NOEXCEPT {
188 typedef LockFreePlaceHolder<T1, T2> item_type;
189 item_type* first_ptr = CalcPtr(*head);
190 item_type* last_ptr = CalcPtr(*tail);
191 if (first_ptr == last_ptr)
return EAGAIN;
193 uintptr_t first_next = first_ptr->next.aba_ptr;
194 item_type* first_next_ptr = CalcPtr(first_next);
195 *elem = first_next_ptr->data;
197 FreeUnsafe(first_ptr);
203 uintptr_t invariant_;
205 LockFreePlaceHolder<T1, T2>* mem_;
209 template<
class T1,
class T2>
210 errno_t LockFreePlaceHolderPool<T1, T2>::Init(
size_t count) NLIB_NOEXCEPT {
212 LockFreePlaceHolder<T1, T2>* mem =
new (std::nothrow) LockFreePlaceHolder<T1, T2>[count];
214 uintptr_t freelist = 1;
216 for (
size_t j = 0; j < 4; ++j) {
217 for (
size_t i = j; i < count; i += 4) {
218 mem[i].next.aba_ptr = freelist;
220 freelist =
reinterpret_cast<uintptr_t
>(&mem[i]);
224 for (
size_t j = 0; j < 8; ++j) {
225 for (
size_t i = j; i < count; i += 8) {
226 mem[i].next.aba_ptr = freelist;
228 freelist =
reinterpret_cast<uintptr_t
>(&mem[i]);
232 uintptr_t first =
reinterpret_cast<uintptr_t
>(mem);
233 uintptr_t last =
reinterpret_cast<uintptr_t
>(mem + count);
239 freelist_ = freelist;
240 mask_ = (
static_cast<uintptr_t
>(0) - 1) >> sft;
241 invariant_ = first & ~mask_;
246 template<
class T1,
class T2>
248 uintptr_t* stack,
const T1& elem) NLIB_NOEXCEPT NLIB_NO_TSAN {
249 typedef LockFreePlaceHolder<T1, T2> item_type;
250 item_type* item_ptr = Alloc();
254 item_ptr->data = elem;
255 uintptr_t mask = mask_;
256 uintptr_t desired =
reinterpret_cast<uintptr_t
>(item_ptr);
257 uintptr_t expected = Load(&freelist_);
258 uintptr_t base = (item_ptr->next.aba_ptr & ~mask) + (mask + 1);
260 Store(&item_ptr->next.aba_ptr, base | (expected & mask));
268 template<
class T1,
class T2>
270 uintptr_t* stack, T1* elem) NLIB_NOEXCEPT NLIB_NO_TSAN {
271 LockFreePlaceHolder<T1, T2>* ptr;
272 uintptr_t expected = Load(stack);
275 ptr = this->CalcPtr(expected);
276 uintptr_t desired = Load(&ptr->next.aba_ptr);
277 if (
NLIB_LIKELY(Cas(stack, &expected, &desired, 1)))
285 template<
class T1,
class T2>
287 uintptr_t* tail,
const T1& elem) NLIB_NOEXCEPT NLIB_NO_TSAN {
288 LockFreePlaceHolder<T1, T2>* item_ptr = Alloc();
292 item_ptr->Init(elem);
293 #if !defined(_M_IX86) && !defined(_M_AMD64) && !defined(__i386__) && !defined(__x86_64__) 296 uintptr_t last = Load(tail);
298 uintptr_t* last_next_ptr = &CalcPtr(last)->next.aba_ptr;
299 uintptr_t last_next = Load(last_next_ptr,
301 uintptr_t last_new = Load(tail);
305 reinterpret_cast<uintptr_t*>(&item_ptr),
308 Cas(tail, &last, reinterpret_cast<uintptr_t*>(&item_ptr), 0);
313 if (
NLIB_LIKELY(Cas(tail, &last, &last_next, 0))) {
323 template<
class T1,
class T2>
325 uintptr_t* head, uintptr_t* tail, T1* elem) NLIB_NOEXCEPT NLIB_NO_TSAN {
326 typedef LockFreePlaceHolder<T1, T2> item_type;
329 uintptr_t last = Load(tail);
331 item_type* first_ptr = CalcPtr(first);
332 item_type* last_ptr = CalcPtr(last);
333 uintptr_t first_next = Load(&first_ptr->next.aba_ptr,
335 uintptr_t first_new = Load(head);
341 if (
NLIB_LIKELY(Cas(tail, &last, &first_next, 0))) {
345 item_type* first_next_ptr = CalcPtr(first_next);
346 *elem = first_next_ptr->data;
347 if (
NLIB_LIKELY(Cas(head, &first, &first_next, 0))) {
348 Free(CalcPtr(first));
377 uint32_t rofs_actual = rofs & (N - 1);
379 size_t ntail = N - rofs_actual;
380 if (ntail >= nbytes) {
384 reinterpret_cast<const void*>(&buffer_[rofs_actual]),
389 reinterpret_cast<const void*>(&buffer_[rofs_actual]),
391 nlib_memcpy(reinterpret_cast<void*>(reinterpret_cast<uint8_t*>(dest) + ntail),
393 reinterpret_cast<void*>(&buffer_[0]),
396 rofs +=
static_cast<uint32_t
>(nbytes);
407 if (
NLIB_UNLIKELY(nbytes > N - (wofs - rofs)))
return EAGAIN;
408 uint32_t wofs_actual = wofs & (N - 1);
410 size_t ntail = N - wofs_actual;
411 if (ntail >= nbytes) {
412 nlib_memcpy(reinterpret_cast<void*>(&buffer_[wofs_actual]),
417 nlib_memcpy(reinterpret_cast<void*>(&buffer_[wofs_actual]),
423 reinterpret_cast<const void*>(
424 reinterpret_cast<const uint8_t*>(src) + ntail),
427 wofs +=
static_cast<uint32_t
>(nbytes);
437 reinterpret_cast<int32_t*>(p), memorder));
439 NLIB_ALWAYS_INLINE void Store(uint32_t* p, uint32_t value,
int memorder) NLIB_NOEXCEPT {
441 static_cast<int32_t>(value), memorder);
453 T* operator()() NLIB_NOEXCEPT {
return new (std::nothrow) T(); }
459 void operator()(T* ptr) NLIB_NOEXCEPT {
delete ptr; }
477 errno_t Push(
const T& x) NLIB_NOEXCEPT {
return pool_.Push(&top_, x); }
478 errno_t Pop(PopType x) NLIB_NOEXCEPT {
return pool_.Pop(&top_, x); }
484 std::swap(top_, rhs.top_);
485 pool_.SwapUnsafe(rhs.pool_);
490 LockFreePlaceHolderPool<T> pool_;
501 while (0 == pool_.PopUnsafe(&top_, &elem)) {
507 errno_t Init(
size_t count) NLIB_NOEXCEPT {
513 errno_t Push(T* obj) NLIB_NOEXCEPT {
return pool_.Push(&top_, obj); }
514 errno_t Pop(PopType& obj) NLIB_NOEXCEPT {
517 if (e != 0)
return e;
522 errno_t PushUnsafe(T* obj) NLIB_NOEXCEPT {
return pool_.PushUnsafe(&top_, obj); }
524 errno_t PopUnsafe(PopType& obj) NLIB_NOEXCEPT {
527 if (e != 0)
return e;
532 std::swap(top_, rhs.top_);
533 pool_.SwapUnsafe(rhs.pool_);
538 LockFreePlaceHolderPool<T*> pool_;
551 errno_t e = pool_.Init(count + 1);
553 head_ = tail_ =
reinterpret_cast<uintptr_t
>(pool_.AllocUnsafe());
557 errno_t Dequeue(DequeueType x) NLIB_NOEXCEPT {
return pool_.Dequeue(&head_, &tail_, x); }
562 return pool_.DequeueUnsafe(&head_, &tail_, x);
565 std::swap(head_, rhs.head_);
566 std::swap(tail_, rhs.tail_);
567 pool_.SwapUnsafe(rhs.pool_);
573 LockFreePlaceHolderPool<T> pool_;
584 while (0 == pool_.DequeueUnsafe(&head_, &tail_, &elem)) {
590 errno_t Init(
size_t count) NLIB_NOEXCEPT {
591 errno_t e = pool_.Init(count + 1);
593 head_ = tail_ =
reinterpret_cast<uintptr_t
>(pool_.AllocUnsafe());
596 errno_t Enqueue(T* obj) NLIB_NOEXCEPT {
return pool_.Enqueue(&tail_, obj); }
597 errno_t Dequeue(DequeueType& obj) NLIB_NOEXCEPT {
600 if (e != 0)
return e;
605 errno_t EnqueueUnsafe(T* x) NLIB_NOEXCEPT {
return pool_.EnqueueUnsafe(&tail_, x); }
607 errno_t DequeueUnsafe(DequeueType& obj) NLIB_NOEXCEPT {
610 if (e != 0)
return e;
615 std::swap(head_, rhs.head_);
616 std::swap(tail_, rhs.tail_);
617 pool_.SwapUnsafe(rhs.pool_);
623 LockFreePlaceHolderPool<T*> pool_;
631 NLIB_EINVAL_IFNULL(ptr);
637 return pold ? 0 : EAGAIN;
640 &pold, reinterpret_cast<void*>(obj), 0,
662 if (mq_.raw_handle != 0)
return EALREADY;
663 if (max_size > INT32_MAX)
return EINVAL;
665 attr.
flag = NLIB_MQ_LOCKFREE;
666 attr.
max_msg =
static_cast<int32_t
>(max_size);
667 attr.
destructor = LockFreePriorityQueue::dtor;
685 if (e != 0)
return e;
697 T* obj =
reinterpret_cast<T*
>(msg);
706 class LockFreeBroadcastQueueImpl {
707 typedef LockFreePlaceHolder<const void*, int32_t> item_type;
711 : head_(1), tail_(1), listener_count_(0), pool_(), listeners_() {}
714 errno_t Enqueue(
const void* msg) NLIB_NOEXCEPT {
716 return pool_.Enqueue(&tail_, msg);
718 errno_t Dequeue(int32_t listener_id,
const void** msg) NLIB_NOEXCEPT {
721 NLIB_UNLIKELY(listener_id >= listener_count_))
return ERANGE;
722 uintptr_t& pos = listeners_[listener_id];
723 item_type* item = pool_.CalcPtr(pos);
724 uintptr_t next = item->next.aba_ptr;
725 if (pool_.IsNull(next))
return ENOENT;
726 *msg = pool_.CalcPtr(next)->data;
732 errno_t DeleteUnsafe(
const void** msg) NLIB_NOEXCEPT {
733 if (pool_.IsNull(head_))
return ENOENT;
734 item_type* item = pool_.CalcPtr(head_);
735 const void* p = item->data;
736 head_ = item->next.aba_ptr;
740 size_t GetListenerCount()
const NLIB_NOEXCEPT {
return listener_count_; }
741 void SwapUnsafe(LockFreeBroadcastQueueImpl& rhs) NLIB_NOEXCEPT {
742 std::swap(head_, rhs.head_);
743 std::swap(tail_, rhs.tail_);
744 std::swap(listener_count_, rhs.listener_count_);
745 pool_.SwapUnsafe(rhs.pool_);
746 listeners_.swap(rhs.listeners_);
758 int32_t listener_count_;
759 LockFreePlaceHolderPool<const void*, int32_t> pool_;
769 void operator()(
const T*) {}
775 while (impl_.DeleteUnsafe(&p) == 0) {
782 return impl_.Init(max_size, listeners);
786 return impl_.Enqueue(obj);
791 errno_t e = impl_.Dequeue(listener_id, &x);
792 if (e != 0)
return e;
793 obj.reset(reinterpret_cast<const T*>(x));
794 const T* p =
reinterpret_cast<const T*
>(impl_.CheckAndRemove());
802 return impl_.GetListenerCount();
805 impl_.SwapUnsafe(rhs);
809 detail::LockFreeBroadcastQueueImpl impl_;
816 void* Get() NLIB_NOEXCEPT {
return ptr_; }
831 return reinterpret_cast<MemHolder*
>(pool_.Alloc());
835 pool_.Free(
reinterpret_cast<LockFreePlaceHolder<void*>*
>(p));
842 return reinterpret_cast<MemHolder*
>(pool_.AllocUnsafe());
846 pool_.FreeUnsafe(
reinterpret_cast<LockFreePlaceHolder<void*>*
>(p));
850 pool_.SwapUnsafe(rhs.pool_);
855 LockFreePlaceHolderPool<void*> pool_;
861 #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.