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;
49 void Init(
const T1& elem)
NLIB_NOEXCEPT NLIB_NO_TSAN { data = elem; }
52 template<
class T1,
class T2 =
void>
55 #if !defined(CAFE) && !defined(NN_PLATFORM_CTR) 59 LockFreePlaceHolderPool()
NLIB_NOEXCEPT : invariant_(0), mask_(0), mem_(
nullptr) {}
63 return reinterpret_cast<LockFreePlaceHolder<T1, T2>*
>((aba & mask_) | invariant_);
67 LockFreePlaceHolder<T1, T2>* ptr;
68 uintptr_t expected = Load(&freelist_);
71 ptr = this->CalcPtr(expected);
72 uintptr_t desired = Load(&ptr->next.aba_ptr);
73 if (
NLIB_LIKELY(Cas(&freelist_, &expected, &desired, 1)))
break;
75 uintptr_t mask = mask_;
76 ptr->next.aba_ptr = (ptr->next.aba_ptr & ~mask) + (mask + 2);
80 uintptr_t mask = mask_;
81 uintptr_t desired =
reinterpret_cast<uintptr_t
>(p);
82 uintptr_t expected = Load(&freelist_);
83 uintptr_t base = (p->next.aba_ptr & ~mask) + (mask + 1);
85 Store(&p->next.aba_ptr, base | (expected & mask));
91 uintptr_t expected = freelist_;
93 LockFreePlaceHolder<T1, T2>* ptr = this->CalcPtr(expected);
94 freelist_ = ptr->next.aba_ptr;
95 ptr->next.aba_ptr = 1;
99 p->next.aba_ptr = freelist_;
100 freelist_ =
reinterpret_cast<uintptr_t
>(p);
104 return reinterpret_cast<uintptr_t
>(val);
108 return reinterpret_cast<uintptr_t
>(val);
115 Store(uintptr_t* ptr, uintptr_t value,
int memorder)
NLIB_NOEXCEPT NLIB_NO_TSAN {
120 Cas(uintptr_t* ptr, uintptr_t* expected, uintptr_t* desired,
int weak,
int success_memorder,
122 uintptr_t mask = mask_;
123 *desired = ((*desired & mask) | (mask + 1)) + (*expected & ~mask);
125 reinterpret_cast<void**>(ptr), reinterpret_cast<void**>(expected),
126 reinterpret_cast<void*>(*desired), weak, success_memorder, failure_memorder);
129 NLIB_ALWAYS_INLINE int Cas(uintptr_t* ptr, uintptr_t* expected, uintptr_t* desired,
int weak,
134 Cas(uintptr_t* ptr, uintptr_t* expected, uintptr_t* desired,
int weak)
NLIB_NOEXCEPT {
137 void SwapUnsafe(LockFreePlaceHolderPool& rhs)
NLIB_NOEXCEPT {
138 std::swap(freelist_, rhs.freelist_);
139 std::swap(invariant_, rhs.invariant_);
140 std::swap(mask_, rhs.mask_);
141 std::swap(mem_, rhs.mem_);
150 typedef LockFreePlaceHolder<T1, T2> item_type;
151 item_type* item_ptr = AllocUnsafe();
155 item_ptr->data = elem;
156 item_ptr->next.aba_ptr = *stack;
157 *stack =
reinterpret_cast<uintptr_t
>(item_ptr);
162 LockFreePlaceHolder<T1, T2>* ptr = CalcPtr(*stack);
164 *stack = ptr->next.aba_ptr;
169 LockFreePlaceHolder<T1, T2>* item_ptr = AllocUnsafe();
173 item_ptr->data = elem;
174 CalcPtr(*tail)->next.aba_ptr = reinterpret_cast<uintptr_t>(item_ptr);
175 *tail =
reinterpret_cast<uintptr_t
>(item_ptr);
179 typedef LockFreePlaceHolder<T1, T2> item_type;
180 item_type* first_ptr = CalcPtr(*head);
181 item_type* last_ptr = CalcPtr(*tail);
182 if (first_ptr == last_ptr)
return EAGAIN;
184 uintptr_t first_next = first_ptr->next.aba_ptr;
185 item_type* first_next_ptr = CalcPtr(first_next);
186 *elem = first_next_ptr->data;
188 FreeUnsafe(first_ptr);
194 uintptr_t invariant_;
196 LockFreePlaceHolder<T1, T2>* mem_;
200 template<
class T1,
class T2>
203 LockFreePlaceHolder<T1, T2>* mem =
new (std::nothrow) LockFreePlaceHolder<T1, T2>[count];
205 uintptr_t freelist = 1;
207 for (
size_t j = 0; j < 4; ++j) {
208 for (
size_t i = j; i < count; i += 4) {
209 mem[i].next.aba_ptr = freelist;
211 freelist =
reinterpret_cast<uintptr_t
>(&mem[i]);
215 for (
size_t j = 0; j < 8; ++j) {
216 for (
size_t i = j; i < count; i += 8) {
217 mem[i].next.aba_ptr = freelist;
219 freelist =
reinterpret_cast<uintptr_t
>(&mem[i]);
223 uintptr_t first =
reinterpret_cast<uintptr_t
>(mem);
224 uintptr_t last =
reinterpret_cast<uintptr_t
>(mem + count);
230 freelist_ = freelist;
231 mask_ = (
static_cast<uintptr_t
>(0) - 1) >> sft;
232 invariant_ = first & ~mask_;
237 template<
class T1,
class T2>
240 typedef LockFreePlaceHolder<T1, T2> item_type;
241 item_type* item_ptr = Alloc();
245 item_ptr->data = elem;
246 uintptr_t mask = mask_;
247 uintptr_t desired =
reinterpret_cast<uintptr_t
>(item_ptr);
248 uintptr_t expected = Load(&freelist_);
249 uintptr_t base = (item_ptr->next.aba_ptr & ~mask) + (mask + 1);
251 Store(&item_ptr->next.aba_ptr, base | (expected & mask));
258 template<
class T1,
class T2>
261 LockFreePlaceHolder<T1, T2>* ptr;
262 uintptr_t expected = Load(stack);
265 ptr = this->CalcPtr(expected);
266 uintptr_t desired = Load(&ptr->next.aba_ptr);
267 if (
NLIB_LIKELY(Cas(stack, &expected, &desired, 1)))
break;
274 template<
class T1,
class T2>
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), 1,
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>
314 uintptr_t* head, uintptr_t* tail, T1* elem)
NLIB_NOEXCEPT NLIB_NO_TSAN {
315 typedef LockFreePlaceHolder<T1, T2> item_type;
318 uintptr_t last = Load(tail);
320 item_type* first_ptr = CalcPtr(first);
321 item_type* last_ptr = CalcPtr(last);
322 uintptr_t first_next = Load(&first_ptr->next.aba_ptr,
324 uintptr_t first_new = Load(head);
330 if (
NLIB_LIKELY(Cas(tail, &last, &first_next, 0))) {
334 item_type* first_next_ptr = CalcPtr(first_next);
335 *elem = first_next_ptr->data;
336 if (
NLIB_LIKELY(Cas(head, &first, &first_next, 0))) {
337 Free(CalcPtr(first));
366 uint32_t rofs_actual = rofs & (N - 1);
368 size_t ntail = N - rofs_actual;
369 if (ntail >= nbytes) {
371 nlib_memcpy(dest, nbytes, reinterpret_cast<const void*>(&buffer_[rofs_actual]), nbytes);
373 nlib_memcpy(dest, nbytes, reinterpret_cast<const void*>(&buffer_[rofs_actual]), ntail);
374 nlib_memcpy(reinterpret_cast<void*>(reinterpret_cast<uint8_t*>(dest) + ntail),
375 nbytes - ntail, reinterpret_cast<void*>(&buffer_[0]), nbytes - ntail);
377 rofs +=
static_cast<uint32_t
>(nbytes);
388 if (
NLIB_UNLIKELY(nbytes > N - (wofs - rofs)))
return EAGAIN;
389 uint32_t wofs_actual = wofs & (N - 1);
391 size_t ntail = N - wofs_actual;
392 if (ntail >= nbytes) {
393 nlib_memcpy(reinterpret_cast<void*>(&buffer_[wofs_actual]), nbytes, src, nbytes);
395 nlib_memcpy(reinterpret_cast<void*>(&buffer_[wofs_actual]), ntail, src, ntail);
397 reinterpret_cast<void*>(&buffer_[0]), nbytes - ntail,
398 reinterpret_cast<const void*>(reinterpret_cast<const uint8_t*>(src) + ntail),
401 wofs +=
static_cast<uint32_t
>(nbytes);
410 return static_cast<uint32_t
>(
nlib_atomic_load32(reinterpret_cast<int32_t*>(p), memorder));
425 T* operator()()
NLIB_NOEXCEPT {
return new (std::nothrow) T(); }
456 std::swap(top_, rhs.top_);
457 pool_.SwapUnsafe(rhs.pool_);
462 LockFreePlaceHolderPool<T> pool_;
468 typedef UniquePtr<T, DestructorForLockFree<T> > PopType;
473 while (0 == pool_.PopUnsafe(&top_, &elem)) {
474 DestructorForLockFree<T>()(elem);
488 errno_t e = pool_.Pop(&top_, &x);
489 if (e != 0)
return e;
498 errno_t e = pool_.PopUnsafe(&top_, &x);
499 if (e != 0)
return e;
504 std::swap(top_, rhs.top_);
505 pool_.SwapUnsafe(rhs.pool_);
510 LockFreePlaceHolderPool<T*> pool_;
523 errno_t e = pool_.Init(count + 1);
525 head_ = tail_ =
reinterpret_cast<uintptr_t
>(pool_.AllocUnsafe());
534 return pool_.DequeueUnsafe(&head_, &tail_, x);
537 std::swap(head_, rhs.head_);
538 std::swap(tail_, rhs.tail_);
539 pool_.SwapUnsafe(rhs.pool_);
545 LockFreePlaceHolderPool<T> pool_;
551 typedef UniquePtr<T, DestructorForLockFree<T> > DequeueType;
552 LockFreeQueue()
NLIB_NOEXCEPT : head_(0), tail_(0), pool_() {}
556 while (0 == pool_.DequeueUnsafe(&head_, &tail_, &elem)) {
557 DestructorForLockFree<T>()(elem);
563 errno_t e = pool_.Init(count + 1);
565 head_ = tail_ =
reinterpret_cast<uintptr_t
>(pool_.AllocUnsafe());
571 errno_t e = pool_.Dequeue(&head_, &tail_, &x);
572 if (e != 0)
return e;
581 errno_t e = pool_.DequeueUnsafe(&head_, &tail_, &x);
582 if (e != 0)
return e;
587 std::swap(head_, rhs.head_);
588 std::swap(tail_, rhs.tail_);
589 pool_.SwapUnsafe(rhs.pool_);
595 LockFreePlaceHolderPool<T*> pool_;
603 NLIB_EINVAL_IFNULL(ptr);
609 return pold ? 0 : EAGAIN;
632 if (mq_.raw_handle != 0)
return EALREADY;
633 if (max_size > INT32_MAX)
return EINVAL;
635 attr.
flag = NLIB_MQ_LOCKFREE;
636 attr.
max_msg =
static_cast<int32_t
>(max_size);
637 attr.
destructor = LockFreePriorityQueue::dtor;
655 if (e != 0)
return e;
667 T* obj =
reinterpret_cast<T*
>(msg);
676 class LockFreeBroadcastQueueImpl {
677 typedef LockFreePlaceHolder<const void*, int32_t> item_type;
689 return pool_.Enqueue(&tail_, msg);
695 uintptr_t& pos = listeners_[listener_id];
696 item_type* item = pool_.CalcPtr(pos);
697 uintptr_t next = item->next.aba_ptr;
698 if (pool_.IsNull(next))
return ENOENT;
699 *msg = pool_.CalcPtr(next)->data;
706 if (pool_.IsNull(head_))
return ENOENT;
707 item_type* item = pool_.CalcPtr(head_);
708 const void* p = item->data;
709 head_ = item->next.aba_ptr;
713 size_t GetListenerCount() const
NLIB_NOEXCEPT {
return listener_count_; }
714 void SwapUnsafe(LockFreeBroadcastQueueImpl& rhs)
NLIB_NOEXCEPT {
715 std::swap(head_, rhs.head_);
716 std::swap(tail_, rhs.tail_);
717 std::swap(listener_count_, rhs.listener_count_);
718 pool_.SwapUnsafe(rhs.pool_);
719 listeners_.swap(rhs.listeners_);
724 return reinterpret_cast<uintptr_t
>(
731 int32_t listener_count_;
732 LockFreePlaceHolderPool<const void*, int32_t> pool_;
733 UniquePtr<uintptr_t[]> listeners_;
742 void operator()(
const T*) {}
748 while (impl_.DeleteUnsafe(&p) == 0) {
755 return impl_.Init(max_size, listeners);
759 return impl_.Enqueue(obj);
764 errno_t e = impl_.Dequeue(listener_id, &x);
765 if (e != 0)
return e;
766 obj.reset(reinterpret_cast<const T*>(x));
767 const T* p =
reinterpret_cast<const T*
>(impl_.CheckAndRemove());
775 return impl_.GetListenerCount();
780 detail::LockFreeBroadcastQueueImpl impl_;
801 return reinterpret_cast<MemHolder*
>(pool_.Alloc());
805 pool_.Free(
reinterpret_cast<LockFreePlaceHolder<void*>*
>(p));
812 return reinterpret_cast<MemHolder*
>(pool_.AllocUnsafe());
816 pool_.FreeUnsafe(
reinterpret_cast<LockFreePlaceHolder<void*>*
>(p));
820 swap(mem_, rhs.mem_);
821 pool_.SwapUnsafe(rhs.pool_);
826 LockFreePlaceHolderPool<void*> pool_;
832 #endif // INCLUDE_NN_NLIB_LOCKFREE_H_ void FreeUnsafe(MemHolder *p) noexcept
Free()と同様ですが、スレッドセーフではありません。
errno_t PopUnsafe(PopType x) noexcept
スタックから要素を取り出してxに格納します。スレッドセーフではありません。
LockFreePipe() noexcept
デフォルトコンストラクタです。
LockFreeQueue() noexcept
デフォルトコンストラクタです。
C++11の標準ヘッダとなるtype_traitsの代用定義です。 コンパイラや標準ライブラリによってサポートされてい...
UniquePtr< const T, empty_func > DequeueType
Dequeue()の引数となる型です
#define NLIB_DISALLOW_COPY_AND_ASSIGN(TypeName)
TypeName で指定されたクラスのコピーコンストラクタと代入演算子を禁止します。
errno_t Init(size_t count) noexcept
スタックを初期化します。スレッドセーフではありません。
T * PopType
Pop(), PopUnsafe()の引数となる型です
LockFreeStack() noexcept
デフォルトコンストラクタです。
~LockFreeQueue() noexcept
デストラクタです。
errno_t DequeueUnsafe(DequeueType x) noexcept
キューから要素を取り出してxに格納します。スレッドセーフではありません。
size_t GetBufferSize() noexcept
バッファ・サイズを返します。スレッドセーフです。
C++11環境(エイリアステンプレートが可能な環境)においてはstd::unique_ptrにエイリアステンプレートされま...
errno_t PushUnsafe(const T &x) noexcept
スタックに要素xを積みます。スレッドセーフではありません。
std::unique_ptrに相当するクラスが定義されています。
errno_t Pop(PopType x) noexcept
スタックから要素を取り出してxに格納します。スレッドセーフです。
errno_t LockFreeInit(T **ptr) noexcept
スレッドセーフにオブジェクトの構築を行います。
void SwapUnsafe(LockFreePriorityQueue &rhs) noexcept
オブジェクトをスワップします。スレッドセーフではありません。
errno_t EnqueueUnsafe(const T &x) noexcept
キューに要素xを追加します。スレッドセーフではありません。
固定メモリサイズの領域を確保・解放をロックフリーで行うことのできるプールアロケータです。 ...
指定された数のリスナーがキューから要素を取得できます。全てのリスナーが取得後、要素はキューから削除さ...
MemHolder * AllocUnsafe() noexcept
Alloc()と同様ですが、スレッドセーフではありません。
errno_t Read(void *dest, size_t nbytes) noexcept
データをパイプから読み込みます。スレッドセーフです。
void SwapUnsafe(LockFreeStack &rhs) noexcept
オブジェクトをスワップします。スレッドセーフではありません。
errno_t Enqueue(T *obj, int prio) noexcept
キューに要素を追加します。スレッドセーフです。
errno_t Enqueue(const T &x) noexcept
キューに要素xを追加します。スレッドセーフです。
UniquePtr< T, DestructorForLockFree< T > > DequeueType
Dequeue()の引数となる型です
errno_t Write(const void *src, size_t nbytes) noexcept
データをパイプに書き込みます。スレッドセーフです。
T * DequeueType
Dequeue(), DequeueUnsafe()の引数となる型です
size_t GetListenerCount() const noexcept
Init()で指定したリスナーの数を返します。スレッドセーフです。
オブジェクトをデストラクトするためのクラステンプレートです。特殊化して利用します。 ...
void SwapUnsafe(LockFreeQueue &rhs) noexcept
オブジェクトをスワップします。スレッドセーフではありません。
void SwapUnsafe(LockFreeUnitHeap &rhs) noexcept
オブジェクトをスワップします。スレッドセーフではありません。
メッセージキューの設定や現在の状態を格納する構造体です。
#define NLIB_NOEXCEPT
環境に合わせてnoexcept 又は同等の定義がされます。
void SwapUnsafe(LockFreeBroadcastQueue &rhs) noexcept
オブジェクトをスワップします。スレッドセーフではありません。
errno_t Dequeue(DequeueType &obj, int *prio) noexcept
キューから要素を取り出します。スレッドセーフです。
errno_t Close() noexcept
キューをクローズし初期化前の状態にします。スレッドセーフではありません。
errno_t Init(size_t count) noexcept
キューを初期化します。スレッドセーフではありません。
errno_t Dequeue(DequeueType x) noexcept
キューから要素を取り出してxに格納します。スレッドセーフです。
errno_t Push(const T &x) noexcept
スタックに要素xを積みます。スレッドセーフです。
LockFreeUnitHeap() noexcept
デフォルトコンストラクタです。
errno_t Init(size_t max_size, size_t listeners) noexcept
キューを初期化します。スレッドセーフではありません。
データの送り手側のスレッドと受け手側のスレッドがそれぞれ1つずつの場合、このクラスを用いてロックフリー...
#define NLIB_FINAL
利用可能であればfinalが定義されます。そうでない場合は空文字列です。
errno_t Init(size_t max_size) noexcept
キューを初期化します。スレッドセーフではありません。
#define NLIB_STATIC_ASSERT(exp)
静的アサートが定義されます。利用可能であればstatic_assertを利用します。
LockFreeBroadcastQueue() noexcept
デフォルトコンストラクタです。
オブジェクトを初期化するためのクラステンプレートです。特殊化して利用します。
~LockFreeStack() noexcept
デストラクタです。
~LockFreeBroadcastQueue() noexcept
デストラクタです。
errno_t Dequeue(int32_t listener_id, DequeueType &obj) noexcept
リスナーを指定してキューから要素を読み込みます。異なるlistener_idを利用している場合はスレッドセーフで...
void Free(MemHolder *p) noexcept
メモリを解放します。スレッドセーフです。
LockFreePriorityQueue() noexcept
デフォルトコンストラクタです。
ロックフリーな優先度つきキューを実装したクラスで、nlib_mqをラップしています。
~LockFreePriorityQueue() noexcept
デストラクタです。
errno_t Enqueue(const T *obj) noexcept
キューに要素を追加します。スレッドセーフです。