3 #ifndef INCLUDE_NN_NLIB_LOCKFREE_H_
4 #define INCLUDE_NN_NLIB_LOCKFREE_H_
14 template<
class T1,
class T2 =
void>
15 struct LockFreePlaceHolder {
19 LockFreePlaceHolder<T1, T2>* raw_ptr;
29 struct LockFreePlaceHolder<T1, void> {
33 LockFreePlaceHolder<T1, void>* raw_ptr;
40 template<
class T1,
class T2 =
void>
41 class LockFreePlaceHolderPool {
44 LockFreePlaceHolderPool()
NLIB_NOEXCEPT : invariant_(0), mask_(0), mem_(NULL) {}
47 NLIB_ALWAYS_INLINE LockFreePlaceHolder<T1, T2>* CalcPtr(uintptr_t aba)
const NLIB_NOEXCEPT {
48 return reinterpret_cast<LockFreePlaceHolder<T1, T2>*
>((aba & mask_) | invariant_);
54 LockFreePlaceHolder<T1, T2>* ptr;
55 uintptr_t expected = Load(&freelist_);
58 ptr = this->CalcPtr(expected);
59 uintptr_t desired = Load(&ptr->next.aba_ptr);
60 if (
NLIB_LIKELY(Cas(&freelist_, &expected, &desired, 1)))
63 uintptr_t mask = mask_;
64 ptr->next.aba_ptr = (ptr->next.aba_ptr & ~mask) + (mask + 2);
68 uintptr_t mask = mask_;
69 uintptr_t desired =
reinterpret_cast<uintptr_t
>(p);
70 uintptr_t expected = Load(&freelist_);
71 uintptr_t base = (p->next.aba_ptr & ~mask) + (mask + 1);
73 Store(&p->next.aba_ptr, base | (expected & mask));
80 uintptr_t expected = freelist_;
82 LockFreePlaceHolder<T1, T2>* ptr = this->CalcPtr(expected);
83 freelist_ = ptr->next.aba_ptr;
84 ptr->next.aba_ptr = 1;
88 p->next.aba_ptr = freelist_;
89 freelist_ =
reinterpret_cast<uintptr_t
>(p);
93 return reinterpret_cast<uintptr_t
>(val);
97 return reinterpret_cast<uintptr_t
>(val);
101 reinterpret_cast<void*>(value),
106 reinterpret_cast<void*>(value),
109 NLIB_ALWAYS_INLINE int Cas(uintptr_t* ptr, uintptr_t* expected, uintptr_t* desired,
int weak,
111 uintptr_t mask = mask_;
112 *desired = ((*desired & mask) | (mask + 1)) + (*expected & ~mask);
114 reinterpret_cast<void**>(expected),
115 reinterpret_cast<void*>(*desired),
116 weak, success_memorder, failure_memorder);
119 NLIB_ALWAYS_INLINE int Cas(uintptr_t* ptr, uintptr_t* expected, uintptr_t* desired,
int weak,
127 void SwapUnsafe(LockFreePlaceHolderPool& rhs)
NLIB_NOEXCEPT {
128 uintptr_t freelist = rhs.freelist_;
129 uintptr_t invariant = rhs.invariant_;
130 uintptr_t mask = rhs.mask_;
131 LockFreePlaceHolder<T1, T2>* mem = rhs.mem_;
132 rhs.freelist_ = freelist_;
133 rhs.invariant_ = invariant_;
136 freelist_ = freelist;
137 invariant_ = invariant;
147 errno_t PushUnsafe(uintptr_t* stack,
const T1& elem) NLIB_NOEXCEPT {
148 typedef LockFreePlaceHolder<T1, T2> item_type;
149 item_type* item_ptr = AllocUnsafe();
153 item_ptr->data = elem;
154 item_ptr->next.aba_ptr = *stack;
155 *stack =
reinterpret_cast<uintptr_t
>(item_ptr);
158 errno_t PopUnsafe(uintptr_t* stack, T1* elem) NLIB_NOEXCEPT {
160 LockFreePlaceHolder<T1, T2>* ptr = CalcPtr(*stack);
162 *stack = ptr->next.aba_ptr;
166 errno_t EnqueueUnsafe(uintptr_t* tail,
const T1& elem) NLIB_NOEXCEPT {
167 LockFreePlaceHolder<T1, T2>* item_ptr = AllocUnsafe();
171 item_ptr->data = elem;
172 CalcPtr(*tail)->next.aba_ptr = reinterpret_cast<uintptr_t>(item_ptr);
173 *tail =
reinterpret_cast<uintptr_t
>(item_ptr);
176 errno_t DequeueUnsafe(uintptr_t* head, uintptr_t* tail, T1* elem) NLIB_NOEXCEPT {
177 typedef LockFreePlaceHolder<T1, T2> item_type;
178 item_type* first_ptr = CalcPtr(*head);
179 item_type* last_ptr = CalcPtr(*tail);
180 if (first_ptr == last_ptr)
return EAGAIN;
182 uintptr_t first_next = first_ptr->next.aba_ptr;
183 item_type* first_next_ptr = CalcPtr(first_next);
184 *elem = first_next_ptr->data;
186 FreeUnsafe(first_ptr);
192 uintptr_t invariant_;
194 LockFreePlaceHolder<T1, T2>* mem_;
198 template<
class T1,
class T2>
199 errno_t LockFreePlaceHolderPool<T1, T2>::Init(
size_t count) NLIB_NOEXCEPT {
201 LockFreePlaceHolder<T1, T2>* mem =
new (std::nothrow) LockFreePlaceHolder<T1, T2>[count];
203 uintptr_t freelist = 1;
205 for (
size_t j = 0; j < 4; ++j) {
206 for (
size_t i = j; i < count; i += 4) {
207 mem[i].next.aba_ptr = freelist;
209 freelist =
reinterpret_cast<uintptr_t
>(&mem[i]);
213 for (
size_t j = 0; j < 8; ++j) {
214 for (
size_t i = j; i < count; i += 8) {
215 mem[i].next.aba_ptr = freelist;
217 freelist =
reinterpret_cast<uintptr_t
>(&mem[i]);
221 uintptr_t first =
reinterpret_cast<uintptr_t
>(mem);
222 uintptr_t last =
reinterpret_cast<uintptr_t
>(mem + count);
228 freelist_ = freelist;
229 mask_ = (
static_cast<uintptr_t
>(0) - 1) >> sft;
230 invariant_ = first & ~mask_;
235 template<
class T1,
class T2>
237 const T1& elem) NLIB_NOEXCEPT {
238 typedef LockFreePlaceHolder<T1, T2> item_type;
239 item_type* item_ptr = Alloc();
243 item_ptr->data = elem;
244 uintptr_t mask = mask_;
245 uintptr_t desired =
reinterpret_cast<uintptr_t
>(item_ptr);
246 uintptr_t expected = Load(&freelist_);
247 uintptr_t base = (item_ptr->next.aba_ptr & ~mask) + (mask + 1);
249 Store(&item_ptr->next.aba_ptr, base | (expected & mask));
257 template<
class T1,
class T2>
259 T1* elem) NLIB_NOEXCEPT {
260 LockFreePlaceHolder<T1, T2>* ptr;
261 uintptr_t expected = Load(stack);
264 ptr = this->CalcPtr(expected);
265 uintptr_t desired = Load(&ptr->next.aba_ptr);
266 if (
NLIB_LIKELY(Cas(stack, &expected, &desired, 1)))
274 template<
class T1,
class T2>
276 const T1& elem) NLIB_NOEXCEPT {
277 LockFreePlaceHolder<T1, T2>* item_ptr = Alloc();
281 item_ptr->Init(elem);
282 #if !defined(_M_IX86) && !defined(_M_AMD64) && !defined(__i386__) && !defined(__x86_64__)
285 uintptr_t last = Load(tail);
287 uintptr_t* last_next_ptr = &CalcPtr(last)->next.aba_ptr;
288 uintptr_t last_next = Load(last_next_ptr,
290 uintptr_t last_new = Load(tail);
294 reinterpret_cast<uintptr_t*>(&item_ptr),
297 Cas(tail, &last, reinterpret_cast<uintptr_t*>(&item_ptr), 0);
302 if (
NLIB_LIKELY(Cas(tail, &last, &last_next, 0))) {
312 template<
class T1,
class T2>
315 T1* elem) NLIB_NOEXCEPT {
316 typedef LockFreePlaceHolder<T1, T2> item_type;
319 uintptr_t last = Load(tail);
321 item_type* first_ptr = CalcPtr(first);
322 item_type* last_ptr = CalcPtr(last);
323 uintptr_t first_next = Load(&first_ptr->next.aba_ptr,
325 uintptr_t first_new = Load(head);
331 if (
NLIB_LIKELY(Cas(tail, &last, &first_next, 0))) {
335 item_type* first_next_ptr = CalcPtr(first_next);
336 *elem = first_next_ptr->data;
337 if (
NLIB_LIKELY(Cas(head, &first, &first_next, 0))) {
338 Free(CalcPtr(first));
367 uint32_t rofs_actual = rofs & (N - 1);
369 size_t ntail = N - rofs_actual;
370 if (ntail >= nbytes) {
374 reinterpret_cast<const void*>(&buffer_[rofs_actual]),
379 reinterpret_cast<const void*>(&buffer_[rofs_actual]),
381 nlib_memcpy(reinterpret_cast<void*>(reinterpret_cast<uint8_t*>(dest) + ntail),
383 reinterpret_cast<void*>(&buffer_[0]),
386 rofs +=
static_cast<uint32_t
>(nbytes);
397 if (
NLIB_UNLIKELY(nbytes > N - (wofs - rofs)))
return EAGAIN;
398 uint32_t wofs_actual = wofs & (N - 1);
400 size_t ntail = N - wofs_actual;
401 if (ntail >= nbytes) {
402 nlib_memcpy(reinterpret_cast<void*>(&buffer_[wofs_actual]),
407 nlib_memcpy(reinterpret_cast<void*>(&buffer_[wofs_actual]),
413 reinterpret_cast<const void*>(
414 reinterpret_cast<const uint8_t*>(src) + ntail),
417 wofs +=
static_cast<uint32_t
>(nbytes);
427 reinterpret_cast<int32_t*>(p), memorder));
429 NLIB_ALWAYS_INLINE void Store(uint32_t* p, uint32_t value,
int memorder) NLIB_NOEXCEPT {
431 static_cast<int32_t>(value), memorder);
443 T* operator()() NLIB_NOEXCEPT {
return new (std::nothrow) T(); }
449 void operator()(T* ptr) NLIB_NOEXCEPT {
delete ptr; }
467 errno_t Push(
const T& x) NLIB_NOEXCEPT {
return pool_.Push(&top_, x); }
468 errno_t Pop(PopType x) NLIB_NOEXCEPT {
return pool_.Pop(&top_, x); }
476 LockFreePlaceHolderPool<T> pool_;
480 class LockFreeStack<T*> {
482 typedef UniquePtr<T, DestructorForLockFree<T> > PopType;
483 LockFreeStack() NLIB_NOEXCEPT : top_(0), pool_() {}
484 ~LockFreeStack() NLIB_NOEXCEPT {
487 while (0 == pool_.PopUnsafe(&top_, &elem)) {
488 DestructorForLockFree<T>()(elem);
493 errno_t Init(
size_t count) NLIB_NOEXCEPT {
499 errno_t Push(T* obj) NLIB_NOEXCEPT {
return pool_.Push(&top_, obj); }
500 errno_t Pop(PopType& obj) NLIB_NOEXCEPT {
502 errno_t e = pool_.Pop(&top_, &x);
503 if (e != 0)
return e;
508 errno_t PushUnsafe(T* obj) NLIB_NOEXCEPT {
return pool_.PushUnsafe(&top_, obj); }
510 errno_t PopUnsafe(PopType& obj) NLIB_NOEXCEPT {
512 errno_t e = pool_.PopUnsafe(&top_, &x);
513 if (e != 0)
return e;
520 LockFreePlaceHolderPool<T*> pool_;
533 errno_t e = pool_.Init(count + 1);
535 head_ = tail_ =
reinterpret_cast<uintptr_t
>(pool_.AllocUnsafe());
539 errno_t Dequeue(DequeueType x) NLIB_NOEXCEPT {
return pool_.Dequeue(&head_, &tail_, x); }
544 return pool_.DequeueUnsafe(&head_, &tail_, x);
550 LockFreePlaceHolderPool<T> pool_;
554 class LockFreeQueue<T*> {
556 typedef UniquePtr<T, DestructorForLockFree<T> > DequeueType;
557 LockFreeQueue() NLIB_NOEXCEPT : head_(0), tail_(0), pool_() {}
558 ~LockFreeQueue() NLIB_NOEXCEPT {
561 while (0 == pool_.DequeueUnsafe(&head_, &tail_, &elem)) {
562 DestructorForLockFree<T>()(elem);
567 errno_t Init(
size_t count) NLIB_NOEXCEPT {
568 errno_t e = pool_.Init(count + 1);
570 head_ = tail_ =
reinterpret_cast<uintptr_t
>(pool_.AllocUnsafe());
573 errno_t Enqueue(T* obj) NLIB_NOEXCEPT {
return pool_.Enqueue(&tail_, obj); }
574 errno_t Dequeue(DequeueType& obj) NLIB_NOEXCEPT {
576 errno_t e = pool_.Dequeue(&head_, &tail_, &x);
577 if (e != 0)
return e;
582 errno_t EnqueueUnsafe(T* x) NLIB_NOEXCEPT {
return pool_.EnqueueUnsafe(&tail_, x); }
584 errno_t DequeueUnsafe(DequeueType& obj) NLIB_NOEXCEPT {
586 errno_t e = pool_.DequeueUnsafe(&head_, &tail_, &x);
587 if (e != 0)
return e;
595 LockFreePlaceHolderPool<T*> pool_;
603 NLIB_EINVAL_IFNULL(ptr);
609 return pold ? 0 : EAGAIN;
612 &pold, reinterpret_cast<void*>(obj), 0,
634 if (mq_.raw_handle != 0)
return EALREADY;
635 if (max_size > INT32_MAX)
return EINVAL;
637 attr.
flag = NLIB_MQ_LOCKFREE;
638 attr.
max_msg =
static_cast<int32_t
>(max_size);
639 attr.
destructor = LockFreePriorityQueue::dtor;
657 if (e != 0)
return e;
664 T* obj =
reinterpret_cast<T*
>(msg);
673 class LockFreeBroadcastQueueImpl {
674 typedef LockFreePlaceHolder<const void*, int32_t> item_type;
677 LockFreeBroadcastQueueImpl() NLIB_NOEXCEPT
678 : head_(1), tail_(1), listener_count_(0), pool_(), listeners_() {}
679 ~LockFreeBroadcastQueueImpl() NLIB_NOEXCEPT {}
681 errno_t Enqueue(
const void* msg) NLIB_NOEXCEPT {
683 return pool_.Enqueue(&tail_, msg);
685 errno_t Dequeue(int32_t listener_id,
const void** msg) NLIB_NOEXCEPT {
688 NLIB_UNLIKELY(listener_id >= listener_count_))
return ERANGE;
689 uintptr_t& pos = listeners_[listener_id];
690 item_type* item = pool_.CalcPtr(pos);
691 uintptr_t next = item->next.aba_ptr;
692 if (pool_.IsNull(next))
return ENOENT;
693 *msg = pool_.CalcPtr(next)->data;
699 errno_t DeleteUnsafe(const
void** msg) NLIB_NOEXCEPT {
700 if (pool_.IsNull(head_))
return ENOENT;
701 item_type* item = pool_.CalcPtr(head_);
702 const void* p = item->data;
703 head_ = item->next.aba_ptr;
707 size_t GetListenerCount() const NLIB_NOEXCEPT {
return listener_count_; }
718 int32_t listener_count_;
719 LockFreePlaceHolderPool<const void*, int32_t> pool_;
720 UniquePtr<uintptr_t[]> listeners_;
729 void operator()(
const T*) {}
735 while (impl_.DeleteUnsafe(&p) == 0) {
742 return impl_.Init(max_size, listeners);
746 return impl_.Enqueue(obj);
751 errno_t e = impl_.Dequeue(listener_id, &x);
752 if (e != 0)
return e;
753 obj.reset(reinterpret_cast<const T*>(x));
754 const T* p =
reinterpret_cast<const T*
>(impl_.CheckAndRemove());
762 return impl_.GetListenerCount();
766 detail::LockFreeBroadcastQueueImpl impl_;
773 void* Get() NLIB_NOEXCEPT {
return ptr_; }
788 return reinterpret_cast<MemHolder*
>(pool_.Alloc());
792 pool_.Free(
reinterpret_cast<LockFreePlaceHolder<void*>*
>(p));
799 return reinterpret_cast<MemHolder*
>(pool_.AllocUnsafe());
803 pool_.FreeUnsafe(
reinterpret_cast<LockFreePlaceHolder<void*>*
>(p));
808 LockFreePlaceHolderPool<void*> pool_;
814 #endif // INCLUDE_NN_NLIB_LOCKFREE_H_
#define NLIB_NOEXCEPT
Defines noexcept geared to the environment, or the equivalent.
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() and DequeueUnsafe().
#define NLIB_FINAL
Defines final if it is available for use. If not, holds an empty string.
#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.
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.
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() and DequeueUnsafe().
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.
Class template for destructing an object. This should be specialized before use.
MemHolder * Alloc() noexcept
Allocates memory. The allocated region can be obtained by executing Get() on the returned pointer to ...
Structure to store the settings and current status of a message queue.
size_t GetListenerCount() const noexcept
Returns the number of listeners specified in Init(). This is thread-safe.
This class implements a lock-free queue.
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.
~LockFreeUnitHeap() noexcept
Destructor.
When a single sender thread sends data and a single receiver thread receives that data...
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.