nlib
LockFree.h
[詳解]
1 
2 /*--------------------------------------------------------------------------------*
3  Project: CrossRoad
4  Copyright (C)Nintendo All rights reserved.
5 
6  These coded instructions, statements, and computer programs contain proprietary
7  information of Nintendo and/or its licensed developers and are protected by
8  national and international copyright laws. They may not be disclosed to third
9  parties or copied or duplicated in any form, in whole or in part, without the
10  prior written consent of Nintendo.
11 
12  The content herein is highly confidential and should be handled accordingly.
13  *--------------------------------------------------------------------------------*/
14 
15 #pragma once
16 #ifndef INCLUDE_NN_NLIB_LOCKFREE_H_
17 #define INCLUDE_NN_NLIB_LOCKFREE_H_
18 
19 #include <new>
20 #include "nn/nlib/Config.h"
21 #include "nn/nlib/TypeTraits.h"
22 #include "nn/nlib/UniquePtr.h"
24 #include "nn/nlib/Swap.h"
25 
26 NLIB_NAMESPACE_BEGIN
27 
28 template<class T1, class T2 = void>
29 struct LockFreePlaceHolder {
30  T1 data; // T1 must be POD
31  union next_type {
32  uintptr_t aba_ptr;
33  LockFreePlaceHolder<T1, T2>* raw_ptr;
34  } next;
35  T2 aux;
36  void Init(const T1& elem) NLIB_NOEXCEPT NLIB_NO_TSAN {
37  data = elem;
38  aux = T2();
39  }
40 };
41 
42 template<class T1>
43 struct LockFreePlaceHolder<T1, void> {
44  T1 data; // T1 must be POD
45  union next_type {
46  uintptr_t aba_ptr;
47  LockFreePlaceHolder<T1, void>* raw_ptr;
48  } next;
49  void Init(const T1& elem) NLIB_NOEXCEPT NLIB_NO_TSAN { data = elem; }
50 };
51 
52 template<class T1, class T2 = void>
53 class LockFreePlaceHolderPool NLIB_FINAL {
54  public:
55 #if !defined(CAFE) && !defined(NN_PLATFORM_CTR)
56  // some old compilers may complain that T1 is incomplete type even if it is not.
57  NLIB_STATIC_ASSERT(IsPod<T1>::value);
58 #endif
59  LockFreePlaceHolderPool() NLIB_NOEXCEPT : invariant_(0), mask_(0), mem_(nullptr) {}
60  ~LockFreePlaceHolderPool() NLIB_NOEXCEPT { delete[] mem_; }
61  errno_t Init(size_t count) NLIB_NOEXCEPT;
62  NLIB_ALWAYS_INLINE LockFreePlaceHolder<T1, T2>* CalcPtr(uintptr_t aba) const NLIB_NOEXCEPT {
63  return reinterpret_cast<LockFreePlaceHolder<T1, T2>*>((aba & mask_) | invariant_);
64  }
65  NLIB_ALWAYS_INLINE bool IsNull(uintptr_t aba) const NLIB_NOEXCEPT { return aba & 1; }
66  NLIB_ALWAYS_INLINE LockFreePlaceHolder<T1, T2>* Alloc() NLIB_NOEXCEPT NLIB_NO_TSAN {
67  LockFreePlaceHolder<T1, T2>* ptr;
68  uintptr_t expected = Load(&freelist_);
69  for (;;) {
70  if (NLIB_UNLIKELY(IsNull(expected))) return nullptr;
71  ptr = this->CalcPtr(expected);
72  uintptr_t desired = Load(&ptr->next.aba_ptr);
73  if (NLIB_LIKELY(Cas(&freelist_, &expected, &desired, 1))) break;
74  }
75  uintptr_t mask = mask_;
76  ptr->next.aba_ptr = (ptr->next.aba_ptr & ~mask) + (mask + 2);
77  return ptr;
78  }
79  NLIB_ALWAYS_INLINE void Free(LockFreePlaceHolder<T1, T2>* p) NLIB_NOEXCEPT NLIB_NO_TSAN {
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);
84  for (;;) {
85  Store(&p->next.aba_ptr, base | (expected & mask));
86  // must comfirm p->next written
87  if (NLIB_LIKELY(Cas(&freelist_, &expected, &desired, 1, NLIB_ATOMIC_RELEASE))) break;
88  }
89  }
90  NLIB_ALWAYS_INLINE LockFreePlaceHolder<T1, T2>* AllocUnsafe() NLIB_NOEXCEPT {
91  uintptr_t expected = freelist_;
92  if (NLIB_UNLIKELY(IsNull(expected))) return nullptr;
93  LockFreePlaceHolder<T1, T2>* ptr = this->CalcPtr(expected);
94  freelist_ = ptr->next.aba_ptr;
95  ptr->next.aba_ptr = 1;
96  return ptr;
97  }
98  NLIB_ALWAYS_INLINE void FreeUnsafe(LockFreePlaceHolder<T1, T2>* p) NLIB_NOEXCEPT {
99  p->next.aba_ptr = freelist_;
100  freelist_ = reinterpret_cast<uintptr_t>(p);
101  }
102  NLIB_ALWAYS_INLINE uintptr_t Load(uintptr_t* ptr) NLIB_NOEXCEPT NLIB_NO_TSAN {
103  void* val = nlib_atomic_loadptr(reinterpret_cast<void**>(ptr), NLIB_ATOMIC_RELAXED);
104  return reinterpret_cast<uintptr_t>(val);
105  }
106  NLIB_ALWAYS_INLINE uintptr_t Load(uintptr_t* ptr, int memorder) NLIB_NOEXCEPT NLIB_NO_TSAN {
107  void* val = nlib_atomic_loadptr(reinterpret_cast<void**>(ptr), memorder);
108  return reinterpret_cast<uintptr_t>(val);
109  }
110  NLIB_ALWAYS_INLINE void Store(uintptr_t* ptr, uintptr_t value) NLIB_NOEXCEPT NLIB_NO_TSAN {
111  nlib_atomic_storeptr(reinterpret_cast<void**>(ptr), reinterpret_cast<void*>(value),
113  }
114  NLIB_ALWAYS_INLINE void
115  Store(uintptr_t* ptr, uintptr_t value, int memorder) NLIB_NOEXCEPT NLIB_NO_TSAN {
116  nlib_atomic_storeptr(reinterpret_cast<void**>(ptr), reinterpret_cast<void*>(value),
117  memorder);
118  }
120  Cas(uintptr_t* ptr, uintptr_t* expected, uintptr_t* desired, int weak, int success_memorder,
121  int failure_memorder) NLIB_NOEXCEPT NLIB_NO_TSAN {
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);
127  return rval;
128  }
129  NLIB_ALWAYS_INLINE int Cas(uintptr_t* ptr, uintptr_t* expected, uintptr_t* desired, int weak,
130  int success_memorder) NLIB_NOEXCEPT {
131  return Cas(ptr, expected, desired, weak, success_memorder, NLIB_ATOMIC_RELAXED);
132  }
134  Cas(uintptr_t* ptr, uintptr_t* expected, uintptr_t* desired, int weak) NLIB_NOEXCEPT {
135  return Cas(ptr, expected, desired, weak, NLIB_ATOMIC_RELAXED, NLIB_ATOMIC_RELAXED);
136  }
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_);
142  }
143 
144  public:
145  errno_t Push(uintptr_t* stack, const T1& elem) NLIB_NOEXCEPT;
146  errno_t Pop(uintptr_t* stack, T1* elem) NLIB_NOEXCEPT;
147  errno_t Enqueue(uintptr_t* tail, const T1& elem) NLIB_NOEXCEPT;
148  errno_t Dequeue(uintptr_t* head, uintptr_t* tail, T1* elem) NLIB_NOEXCEPT;
149  errno_t PushUnsafe(uintptr_t* stack, const T1& elem) NLIB_NOEXCEPT {
150  typedef LockFreePlaceHolder<T1, T2> item_type;
151  item_type* item_ptr = AllocUnsafe();
152  if (NLIB_UNLIKELY(!item_ptr)) return EAGAIN;
153 
154  // point of no failure
155  item_ptr->data = elem;
156  item_ptr->next.aba_ptr = *stack;
157  *stack = reinterpret_cast<uintptr_t>(item_ptr);
158  return 0;
159  }
160  errno_t PopUnsafe(uintptr_t* stack, T1* elem) NLIB_NOEXCEPT {
161  if (NLIB_UNLIKELY(IsNull(*stack))) return EAGAIN;
162  LockFreePlaceHolder<T1, T2>* ptr = CalcPtr(*stack);
163  *elem = ptr->data;
164  *stack = ptr->next.aba_ptr;
165  FreeUnsafe(ptr);
166  return 0;
167  }
168  errno_t EnqueueUnsafe(uintptr_t* tail, const T1& elem) NLIB_NOEXCEPT {
169  LockFreePlaceHolder<T1, T2>* item_ptr = AllocUnsafe();
170  if (NLIB_UNLIKELY(!item_ptr)) return EAGAIN;
171 
172  // point of no failure
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);
176  return 0;
177  }
178  errno_t DequeueUnsafe(uintptr_t* head, uintptr_t* tail, T1* elem) NLIB_NOEXCEPT {
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;
183 
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;
187  *head = first_next;
188  FreeUnsafe(first_ptr);
189  return 0;
190  }
191 
192  private:
193  uintptr_t freelist_;
194  uintptr_t invariant_;
195  uintptr_t mask_;
196  LockFreePlaceHolder<T1, T2>* mem_;
197  NLIB_DISALLOW_COPY_AND_ASSIGN(LockFreePlaceHolderPool);
198 };
199 
200 template<class T1, class T2>
201 errno_t LockFreePlaceHolderPool<T1, T2>::Init(size_t count) NLIB_NOEXCEPT {
202  if (NLIB_UNLIKELY(mem_)) return EALREADY;
203  LockFreePlaceHolder<T1, T2>* mem = new (std::nothrow) LockFreePlaceHolder<T1, T2>[count];
204  if (NLIB_UNLIKELY(!mem)) return ENOMEM;
205  uintptr_t freelist = 1;
206 #ifdef NLIB_64BIT
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;
210  mem[i].data = T1();
211  freelist = reinterpret_cast<uintptr_t>(&mem[i]);
212  }
213  }
214 #else
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;
218  mem[i].data = T1();
219  freelist = reinterpret_cast<uintptr_t>(&mem[i]);
220  }
221  }
222 #endif
223  uintptr_t first = reinterpret_cast<uintptr_t>(mem);
224  uintptr_t last = reinterpret_cast<uintptr_t>(mem + count);
225 #ifdef NLIB_64BIT
226  int sft = nlib_clz64(first ^ last);
227 #else
228  int sft = nlib_clz32(first ^ last);
229 #endif
230  freelist_ = freelist;
231  mask_ = (static_cast<uintptr_t>(0) - 1) >> sft;
232  invariant_ = first & ~mask_;
233  mem_ = mem;
234  return 0;
235 }
236 
237 template<class T1, class T2>
238 NLIB_ALWAYS_INLINE errno_t LockFreePlaceHolderPool<T1, T2>::Push(uintptr_t* stack, const T1& elem)
239  NLIB_NOEXCEPT NLIB_NO_TSAN {
240  typedef LockFreePlaceHolder<T1, T2> item_type;
241  item_type* item_ptr = Alloc();
242  if (NLIB_UNLIKELY(!item_ptr)) return EAGAIN;
243 
244  // point of no failure
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);
250  for (;;) {
251  Store(&item_ptr->next.aba_ptr, base | (expected & mask));
252  // must comfirm p->next written
253  if (NLIB_LIKELY(Cas(stack, &expected, &desired, 1, NLIB_ATOMIC_RELEASE))) break;
254  }
255  return 0;
256 }
257 
258 template<class T1, class T2>
259 NLIB_ALWAYS_INLINE errno_t LockFreePlaceHolderPool<T1, T2>::Pop(uintptr_t* stack, T1* elem)
260  NLIB_NOEXCEPT NLIB_NO_TSAN {
261  LockFreePlaceHolder<T1, T2>* ptr;
262  uintptr_t expected = Load(stack);
263  for (;;) {
264  if (NLIB_UNLIKELY(IsNull(expected))) return EAGAIN;
265  ptr = this->CalcPtr(expected);
266  uintptr_t desired = Load(&ptr->next.aba_ptr);
267  if (NLIB_LIKELY(Cas(stack, &expected, &desired, 1))) break;
268  }
269  *elem = ptr->data;
270  Free(ptr);
271  return 0;
272 }
273 
274 template<class T1, class T2>
275 NLIB_ALWAYS_INLINE errno_t LockFreePlaceHolderPool<T1, T2>::Enqueue(uintptr_t* tail, const T1& elem)
276  NLIB_NOEXCEPT NLIB_NO_TSAN {
277  LockFreePlaceHolder<T1, T2>* item_ptr = Alloc();
278  if (NLIB_UNLIKELY(!item_ptr)) return EAGAIN;
279 
280  // point of no failure
281  item_ptr->Init(elem);
282 #if !defined(_M_IX86) && !defined(_M_AMD64) && !defined(__i386__) && !defined(__x86_64__)
284 #endif
285  uintptr_t last = Load(tail);
286  for (;;) {
287  uintptr_t* last_next_ptr = &CalcPtr(last)->next.aba_ptr;
288  uintptr_t last_next = Load(last_next_ptr,
289  NLIB_ATOMIC_ACQUIRE); // before last_new is loaded
290  uintptr_t last_new = Load(tail);
291  if (NLIB_LIKELY(last == last_new)) {
292  if (NLIB_LIKELY(IsNull(last_next))) {
293  if (NLIB_LIKELY(Cas(last_next_ptr, &last_next,
294  reinterpret_cast<uintptr_t*>(&item_ptr), 1,
296  // Update tail
297  Cas(tail, &last, reinterpret_cast<uintptr_t*>(&item_ptr), 0);
298  return 0;
299  }
300  } else {
301  // Update tail and retry
302  if (NLIB_LIKELY(Cas(tail, &last, &last_next, 0))) {
303  last = last_next;
304  }
305  }
306  } else {
307  last = last_new;
308  }
309  }
310 }
311 
312 template<class T1, class T2>
313 NLIB_ALWAYS_INLINE errno_t LockFreePlaceHolderPool<T1, T2>::Dequeue(
314  uintptr_t* head, uintptr_t* tail, T1* elem) NLIB_NOEXCEPT NLIB_NO_TSAN {
315  typedef LockFreePlaceHolder<T1, T2> item_type;
316  // Load(head), then Load(tail)
317  uintptr_t first = Load(head, NLIB_ATOMIC_ACQUIRE);
318  uintptr_t last = Load(tail);
319  for (;;) {
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,
323  NLIB_ATOMIC_ACQUIRE); // before first_new is loaded
324  uintptr_t first_new = Load(head);
325  if (NLIB_LIKELY(first == first_new)) {
326  if (NLIB_UNLIKELY(first_ptr == last_ptr)) {
327  if (NLIB_UNLIKELY(IsNull(first_next))) return EAGAIN;
328  // Update tail and retry
329  first = Load(head, NLIB_ATOMIC_ACQUIRE);
330  if (NLIB_LIKELY(Cas(tail, &last, &first_next, 0))) {
331  last = first_next;
332  }
333  } else {
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));
338  return 0;
339  }
340  first = Load(head, NLIB_ATOMIC_ACQUIRE);
341  last = Load(tail);
342  }
343  } else {
344  first = first_new;
345  last = Load(tail);
346  }
347  }
348 }
349 
350 template<size_t N>
352  public:
353  LockFreePipe() NLIB_NOEXCEPT : ofs_read_(0), ofs_write_(0) {}
355  NLIB_STATIC_ASSERT(N > 0);
356  NLIB_STATIC_ASSERT((N & (N - 1)) == 0);
357  NLIB_STATIC_ASSERT(N < INT32_MAX);
358  return N;
359  }
360  NLIB_ALWAYS_INLINE errno_t Read(void* dest, size_t nbytes) NLIB_NOEXCEPT {
361  uint32_t rofs = this->Load(&ofs_read_, NLIB_ATOMIC_RELAXED);
362  uint32_t wofs = this->Load(&ofs_write_, NLIB_ATOMIC_ACQUIRE);
363  // read ofs_write_, then read buffer_[rofs_actual]
364 
365  if (NLIB_UNLIKELY(nbytes > wofs - rofs)) return EAGAIN;
366  uint32_t rofs_actual = rofs & (N - 1);
367 
368  size_t ntail = N - rofs_actual;
369  if (ntail >= nbytes) {
370  // ARMCC needs this cast.
371  nlib_memcpy(dest, nbytes, reinterpret_cast<const void*>(&buffer_[rofs_actual]), nbytes);
372  } else {
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);
376  }
377  rofs += static_cast<uint32_t>(nbytes);
378 
379  // must not be reordered
380  this->Store(&ofs_read_, rofs, NLIB_ATOMIC_RELEASE);
381  return 0;
382  }
383  NLIB_ALWAYS_INLINE errno_t Write(const void* src, size_t nbytes) NLIB_NOEXCEPT {
384  uint32_t wofs = this->Load(&ofs_write_, NLIB_ATOMIC_RELAXED);
385  uint32_t rofs = this->Load(&ofs_read_, NLIB_ATOMIC_ACQUIRE);
386  // read ofs_read_, then write buffer_[wofs_actual]
387 
388  if (NLIB_UNLIKELY(nbytes > N - (wofs - rofs))) return EAGAIN;
389  uint32_t wofs_actual = wofs & (N - 1);
390 
391  size_t ntail = N - wofs_actual;
392  if (ntail >= nbytes) {
393  nlib_memcpy(reinterpret_cast<void*>(&buffer_[wofs_actual]), nbytes, src, nbytes);
394  } else {
395  nlib_memcpy(reinterpret_cast<void*>(&buffer_[wofs_actual]), ntail, src, ntail);
396  nlib_memcpy(
397  reinterpret_cast<void*>(&buffer_[0]), nbytes - ntail,
398  reinterpret_cast<const void*>(reinterpret_cast<const uint8_t*>(src) + ntail),
399  nbytes - ntail);
400  }
401  wofs += static_cast<uint32_t>(nbytes);
402 
403  // must not be reordered
404  this->Store(&ofs_write_, wofs, NLIB_ATOMIC_RELEASE);
405  return 0;
406  }
407 
408  private:
409  NLIB_ALWAYS_INLINE uint32_t Load(uint32_t* p, int memorder) NLIB_NOEXCEPT {
410  return static_cast<uint32_t>(nlib_atomic_load32(reinterpret_cast<int32_t*>(p), memorder));
411  }
412  NLIB_ALWAYS_INLINE void Store(uint32_t* p, uint32_t value, int memorder) NLIB_NOEXCEPT {
413  nlib_atomic_store32(reinterpret_cast<int32_t*>(p), static_cast<int32_t>(value), memorder);
414  }
415 
416  uint32_t ofs_read_;
417  uint32_t ofs_write_;
418  uint8_t buffer_[N];
419  NLIB_DISALLOW_COPY_AND_ASSIGN(LockFreePipe);
420 };
421 
422 template<class T>
424  public:
425  T* operator()() NLIB_NOEXCEPT { return new (std::nothrow) T(); }
426 };
427 
428 template<class T>
430  public:
431  void operator()(T* ptr) NLIB_NOEXCEPT { delete ptr; }
432 };
433 
434 template<class T>
436  public:
437  typedef T* PopType;
438  LockFreeStack() NLIB_NOEXCEPT : top_(0), pool_() {}
440  // T is POD, and not pointer
441  }
442  // NOT thread safe
443  errno_t Init(size_t count) NLIB_NOEXCEPT {
444  errno_t e = pool_.Init(count);
445  if (NLIB_UNLIKELY(e != 0)) return e;
446  top_ = 1;
447  return 0;
448  }
449  errno_t Push(const T& x) NLIB_NOEXCEPT { return pool_.Push(&top_, x); }
450  errno_t Pop(PopType x) NLIB_NOEXCEPT { return pool_.Pop(&top_, x); }
451  // NOT thread safe
452  errno_t PushUnsafe(const T& x) NLIB_NOEXCEPT { return pool_.PushUnsafe(&top_, x); }
453  // NOT thread safe
454  errno_t PopUnsafe(PopType x) NLIB_NOEXCEPT { return pool_.PopUnsafe(&top_, x); }
456  std::swap(top_, rhs.top_);
457  pool_.SwapUnsafe(rhs.pool_);
458  }
459 
460  private:
461  uintptr_t top_;
462  LockFreePlaceHolderPool<T> pool_;
463 };
464 
465 template<class T>
466 class LockFreeStack<T*> NLIB_FINAL {
467  public:
468  typedef UniquePtr<T, DestructorForLockFree<T> > PopType;
469  LockFreeStack() NLIB_NOEXCEPT : top_(0), pool_() {}
470  ~LockFreeStack() NLIB_NOEXCEPT {
471  if (top_ != 0) {
472  T* elem;
473  while (0 == pool_.PopUnsafe(&top_, &elem)) {
474  DestructorForLockFree<T>()(elem);
475  }
476  }
477  }
478  // NOT thread safe
479  errno_t Init(size_t count) NLIB_NOEXCEPT {
480  errno_t e = pool_.Init(count);
481  if (NLIB_UNLIKELY(e != 0)) return e;
482  top_ = 1;
483  return 0;
484  }
485  errno_t Push(T* obj) NLIB_NOEXCEPT { return pool_.Push(&top_, obj); }
486  errno_t Pop(PopType& obj) NLIB_NOEXCEPT {
487  T* x;
488  errno_t e = pool_.Pop(&top_, &x);
489  if (e != 0) return e;
490  obj.reset(x);
491  return 0;
492  }
493  // NOT thread safe
494  errno_t PushUnsafe(T* obj) NLIB_NOEXCEPT { return pool_.PushUnsafe(&top_, obj); }
495  // NOT thread safe
496  errno_t PopUnsafe(PopType& obj) NLIB_NOEXCEPT {
497  T* x;
498  errno_t e = pool_.PopUnsafe(&top_, &x);
499  if (e != 0) return e;
500  obj.reset(x);
501  return 0;
502  }
503  void SwapUnsafe(LockFreeStack& rhs) NLIB_NOEXCEPT {
504  std::swap(top_, rhs.top_);
505  pool_.SwapUnsafe(rhs.pool_);
506  }
507 
508  private:
509  uintptr_t top_;
510  LockFreePlaceHolderPool<T*> pool_;
511 };
512 
513 template<class T>
515  public:
516  typedef T* DequeueType;
517  LockFreeQueue() NLIB_NOEXCEPT : head_(0), tail_(0), pool_() {}
519  // T is POD, and not pointer
520  }
521  // NOT thread safe
522  errno_t Init(size_t count) NLIB_NOEXCEPT {
523  errno_t e = pool_.Init(count + 1);
524  if (NLIB_UNLIKELY(e != 0)) return e;
525  head_ = tail_ = reinterpret_cast<uintptr_t>(pool_.AllocUnsafe());
526  return 0;
527  }
528  errno_t Enqueue(const T& x) NLIB_NOEXCEPT { return pool_.Enqueue(&tail_, x); }
529  errno_t Dequeue(DequeueType x) NLIB_NOEXCEPT { return pool_.Dequeue(&head_, &tail_, x); }
530  // NOT thread safe
531  errno_t EnqueueUnsafe(const T& x) NLIB_NOEXCEPT { return pool_.EnqueueUnsafe(&tail_, x); }
532  // NOT thread safe
534  return pool_.DequeueUnsafe(&head_, &tail_, x);
535  }
537  std::swap(head_, rhs.head_);
538  std::swap(tail_, rhs.tail_);
539  pool_.SwapUnsafe(rhs.pool_);
540  }
541 
542  private:
543  uintptr_t head_;
544  uintptr_t tail_;
545  LockFreePlaceHolderPool<T> pool_;
546 };
547 
548 template<class T>
549 class LockFreeQueue<T*> NLIB_FINAL {
550  public:
551  typedef UniquePtr<T, DestructorForLockFree<T> > DequeueType;
552  LockFreeQueue() NLIB_NOEXCEPT : head_(0), tail_(0), pool_() {}
553  ~LockFreeQueue() NLIB_NOEXCEPT {
554  if (head_ != 0) {
555  T* elem;
556  while (0 == pool_.DequeueUnsafe(&head_, &tail_, &elem)) {
557  DestructorForLockFree<T>()(elem);
558  }
559  }
560  }
561  // NOT thread safe
562  errno_t Init(size_t count) NLIB_NOEXCEPT {
563  errno_t e = pool_.Init(count + 1);
564  if (NLIB_UNLIKELY(e != 0)) return e;
565  head_ = tail_ = reinterpret_cast<uintptr_t>(pool_.AllocUnsafe());
566  return 0;
567  }
568  errno_t Enqueue(T* obj) NLIB_NOEXCEPT { return pool_.Enqueue(&tail_, obj); }
569  errno_t Dequeue(DequeueType& obj) NLIB_NOEXCEPT {
570  T* x;
571  errno_t e = pool_.Dequeue(&head_, &tail_, &x);
572  if (e != 0) return e;
573  obj.reset(x);
574  return 0;
575  }
576  // NOT thread safe
577  errno_t EnqueueUnsafe(T* x) NLIB_NOEXCEPT { return pool_.EnqueueUnsafe(&tail_, x); }
578  // NOT thread safe
579  errno_t DequeueUnsafe(DequeueType& obj) NLIB_NOEXCEPT {
580  T* x;
581  errno_t e = pool_.DequeueUnsafe(&head_, &tail_, &x);
582  if (e != 0) return e;
583  obj.reset(x);
584  return 0;
585  }
586  void SwapUnsafe(LockFreeQueue& rhs) NLIB_NOEXCEPT {
587  std::swap(head_, rhs.head_);
588  std::swap(tail_, rhs.tail_);
589  pool_.SwapUnsafe(rhs.pool_);
590  }
591 
592  private:
593  uintptr_t head_;
594  uintptr_t tail_;
595  LockFreePlaceHolderPool<T*> pool_;
596 };
597 
598 template<class T>
600 
601 template<class T>
603  NLIB_EINVAL_IFNULL(ptr);
604  void* pold = nlib_atomic_loadptr(reinterpret_cast<void**>(ptr), NLIB_ATOMIC_RELAXED);
605  if (pold) return 0;
606  T* obj = ConstructorForLockFree<T>()();
607  if (!obj) {
608  pold = nlib_atomic_loadptr(reinterpret_cast<void**>(ptr), NLIB_ATOMIC_RELAXED);
609  return pold ? 0 : EAGAIN;
610  }
611  if (nlib_atomic_compare_exchangeptr(reinterpret_cast<void**>(ptr), &pold,
612  reinterpret_cast<void*>(obj), 0, NLIB_ATOMIC_RELEASE,
614  return 0;
615  } else {
617  return 0;
618  }
619 }
620 
621 template<class T>
623  public:
625  LockFreePriorityQueue() NLIB_NOEXCEPT : mq_() { mq_.raw_handle = 0; }
627  if (mq_.raw_handle != 0) (void)nlib_mq_close(mq_);
628  }
629  // NOT thread safe
630  errno_t Init(size_t max_size) NLIB_NOEXCEPT {
631  // not thread safe
632  if (mq_.raw_handle != 0) return EALREADY;
633  if (max_size > INT32_MAX) return EINVAL;
634  nlib_mq_attr attr;
635  attr.flag = NLIB_MQ_LOCKFREE;
636  attr.max_msg = static_cast<int32_t>(max_size);
637  attr.destructor = LockFreePriorityQueue::dtor;
638  return nlib_mq_open(&mq_, &attr);
639  }
640  // NOT thread safe
642  // not thread safe
643  nlib_mq mq = mq_;
644  mq_.raw_handle = 0;
645  return nlib_mq_close(mq);
646  }
647  errno_t Enqueue(T* obj, int prio) NLIB_NOEXCEPT {
648  // thread safe
649  return nlib_mq_send(mq_, obj, prio);
650  }
652  // thread safe
653  T* x;
654  errno_t e = nlib_mq_receive(mq_, reinterpret_cast<nlib_mq_msg*>(&x), prio);
655  if (e != 0) return e;
656  obj.reset(x);
657  return 0;
658  }
660  nlib_mq mq = rhs.mq_;
661  rhs.mq_ = mq_;
662  mq_ = mq;
663  }
664 
665  private:
666  static void dtor(nlib_mq_msg msg) {
667  T* obj = reinterpret_cast<T*>(msg);
669  }
670 
671  nlib_mq mq_;
672 };
673 
674 namespace detail {
675 
676 class LockFreeBroadcastQueueImpl {
677  typedef LockFreePlaceHolder<const void*, int32_t> item_type;
678 
679  public:
680  LockFreeBroadcastQueueImpl() NLIB_NOEXCEPT : head_(1),
681  tail_(1),
682  listener_count_(0),
683  pool_(),
684  listeners_() {}
685  NLIB_VIS_PUBLIC ~LockFreeBroadcastQueueImpl() NLIB_NOEXCEPT;
686  NLIB_VIS_PUBLIC errno_t Init(size_t max_size, size_t listeners) NLIB_NOEXCEPT;
687  errno_t Enqueue(const void* msg) NLIB_NOEXCEPT {
688  // thread safe
689  return pool_.Enqueue(&tail_, msg);
690  }
691  errno_t Dequeue(int32_t listener_id, const void** msg) NLIB_NOEXCEPT {
692  // thread safe if listener_id is different
693  if (NLIB_UNLIKELY(listener_id < 0) || NLIB_UNLIKELY(listener_id >= listener_count_))
694  return ERANGE;
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;
700  pos = next;
702  return 0;
703  }
704  NLIB_VIS_PUBLIC const void* CheckAndRemove() NLIB_NOEXCEPT;
705  errno_t DeleteUnsafe(const void** msg) NLIB_NOEXCEPT {
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;
710  *msg = p;
711  return 0;
712  }
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_);
720  }
721 
722  private:
723  uintptr_t Load(uintptr_t* p, int memorder = NLIB_ATOMIC_RELAXED) NLIB_NOEXCEPT {
724  return reinterpret_cast<uintptr_t>(
725  nlib_atomic_loadptr(reinterpret_cast<void**>(p), memorder));
726  }
727 
728  private:
729  uintptr_t head_;
730  uintptr_t tail_;
731  int32_t listener_count_;
732  LockFreePlaceHolderPool<const void*, int32_t> pool_;
733  UniquePtr<uintptr_t[]> listeners_;
734 };
735 
736 } // namespace detail
737 
738 template<class T>
740  public:
741  struct empty_func {
742  void operator()(const T*) {}
743  };
747  const void* p;
748  while (impl_.DeleteUnsafe(&p) == 0) {
749  DestructorForLockFree<const T>()(reinterpret_cast<const T*>(p));
750  }
751  }
752  // NOT thread safe
753  errno_t Init(size_t max_size, size_t listeners) NLIB_NOEXCEPT {
754  // not thread safe
755  return impl_.Init(max_size, listeners);
756  }
757  errno_t Enqueue(const T* obj) NLIB_NOEXCEPT {
758  // thread safe
759  return impl_.Enqueue(obj);
760  }
761  errno_t Dequeue(int32_t listener_id, DequeueType& obj) NLIB_NOEXCEPT {
762  // thread safe if listener_id is different
763  const void* x;
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());
768  if (p) {
770  }
771  return 0;
772  }
774  // thread safe
775  return impl_.GetListenerCount();
776  }
777  void SwapUnsafe(LockFreeBroadcastQueue& rhs) NLIB_NOEXCEPT { impl_.SwapUnsafe(rhs); }
778 
779  private:
780  detail::LockFreeBroadcastQueueImpl impl_;
781 };
782 
784  public:
785  class MemHolder {
786  public:
787  void* Get() NLIB_NOEXCEPT { return ptr_; }
788 
789  private:
790  void* const ptr_;
792  };
793  LockFreeUnitHeap() NLIB_NOEXCEPT : mem_(), pool_() {}
794  // NOT thread safe
795  NLIB_VIS_PUBLIC errno_t Init(size_t unit_size, size_t align, size_t count) NLIB_NOEXCEPT;
797 
798  // MemHolder* x = heap.Alloc();
799  // void* ptr = x->Get(); // 'ptr' is what you want.
800  NLIB_ALWAYS_INLINE MemHolder* Alloc() NLIB_NOEXCEPT {
801  return reinterpret_cast<MemHolder*>(pool_.Alloc());
802  }
803 
804  NLIB_ALWAYS_INLINE void Free(MemHolder* p) NLIB_NOEXCEPT {
805  pool_.Free(reinterpret_cast<LockFreePlaceHolder<void*>*>(p));
806  }
807 
808  // NOT thread safe
809  // MemHolder* x = heap.Alloc();
810  // void* ptr = x->Get(); // 'ptr' is what you want.
812  return reinterpret_cast<MemHolder*>(pool_.AllocUnsafe());
813  }
814  // NOT thread safe
816  pool_.FreeUnsafe(reinterpret_cast<LockFreePlaceHolder<void*>*>(p));
817  }
819  using std::swap;
820  swap(mem_, rhs.mem_);
821  pool_.SwapUnsafe(rhs.pool_);
822  }
823 
824  private:
826  LockFreePlaceHolderPool<void*> pool_;
828 };
829 
830 NLIB_NAMESPACE_END
831 
832 #endif // INCLUDE_NN_NLIB_LOCKFREE_H_
void FreeUnsafe(MemHolder *p) noexcept
Free()と同様ですが、スレッドセーフではありません。
Definition: LockFree.h:815
errno_t PopUnsafe(PopType x) noexcept
スタックから要素を取り出してxに格納します。スレッドセーフではありません。
Definition: LockFree.h:454
LockFreePipe() noexcept
デフォルトコンストラクタです。
Definition: LockFree.h:353
int nlib_atomic_compare_exchangeptr(void **ptr, void **expected, void *desired, int weak, int success_memorder, int failure_memorder)
アトミックな値の比較と入れ替えを行います。動作はgccの__atomic_compare_exchange_n()に準じます。 ...
int32_t nlib_atomic_load32(const int32_t *ptr, int memorder)
アトミックに値をロードします。動作はgccの__atomic_load_n()に準じます。
#define NLIB_ALWAYS_INLINE
コンパイラに関数をインライン展開するように強く示します。
Definition: Platform_unix.h:95
LockFreeQueue() noexcept
デフォルトコンストラクタです。
Definition: LockFree.h:517
C++11の標準ヘッダとなるtype_traitsの代用定義です。 コンパイラや標準ライブラリによってサポートされてい...
UniquePtr< const T, empty_func > DequeueType
Dequeue()の引数となる型です
Definition: LockFree.h:744
nlib_mq_msg_destructor destructor
メッセージキューから取り出したメッセージのデストラクタ関数を設定、取得できます。
Definition: Platform.h:1175
errno_t nlib_mq_close(nlib_mq mq)
ハンドルで示されるメッセージキューをクローズします。
#define NLIB_DISALLOW_COPY_AND_ASSIGN(TypeName)
TypeName で指定されたクラスのコピーコンストラクタと代入演算子を禁止します。
Definition: Config.h:183
errno_t nlib_mq_receive(nlib_mq mq, nlib_mq_msg *msg, int *prio)
メッセージをキューから受信します。受信したメッセージはユーザーがデストラクタ関数で削除する必要があり...
errno_t Init(size_t count) noexcept
スタックを初期化します。スレッドセーフではありません。
Definition: LockFree.h:443
T * PopType
Pop(), PopUnsafe()の引数となる型です
Definition: LockFree.h:437
#define NLIB_ATOMIC_RELEASE
gccの__ATOMIC_RELEASEやC++11のstd::memory_order_releaseに準じます。
LockFreeStack() noexcept
デフォルトコンストラクタです。
Definition: LockFree.h:438
~LockFreeQueue() noexcept
デストラクタです。
Definition: LockFree.h:518
#define NLIB_UNLIKELY(x)
条件xが偽になる傾向が高いことをコンパイラに示します。
Definition: Platform_unix.h:98
アラインされたメモリを得るためのクラスです。
errno_t DequeueUnsafe(DequeueType x) noexcept
キューから要素を取り出してxに格納します。スレッドセーフではありません。
Definition: LockFree.h:533
size_t GetBufferSize() noexcept
バッファ・サイズを返します。スレッドセーフです。
Definition: LockFree.h:354
C++11環境(エイリアステンプレートが可能な環境)においてはstd::unique_ptrにエイリアステンプレートされま...
Definition: UniquePtr.h:108
errno_t PushUnsafe(const T &x) noexcept
スタックに要素xを積みます。スレッドセーフではありません。
Definition: LockFree.h:452
std::unique_ptrに相当するクラスが定義されています。
errno_t nlib_mq_open(nlib_mq *mq, const nlib_mq_attr *attr)
スレッド間でメッセージをやりとりするためのメッセージキューを作成します。
errno_t Pop(PopType x) noexcept
スタックから要素を取り出してxに格納します。スレッドセーフです。
Definition: LockFree.h:450
errno_t LockFreeInit(T **ptr) noexcept
スレッドセーフにオブジェクトの構築を行います。
Definition: LockFree.h:602
static int nlib_clz32(uint32_t x)
MSB(most significant bit)から見て連続する0ビットの数を返します。
Definition: Platform.h:2690
void SwapUnsafe(LockFreePriorityQueue &rhs) noexcept
オブジェクトをスワップします。スレッドセーフではありません。
Definition: LockFree.h:659
errno_t EnqueueUnsafe(const T &x) noexcept
キューに要素xを追加します。スレッドセーフではありません。
Definition: LockFree.h:531
#define NLIB_VIS_PUBLIC
関数やクラス等のシンボルをライブラリの外部に公開します。
Definition: Platform_unix.h:87
固定メモリサイズの領域を確保・解放をロックフリーで行うことのできるプールアロケータです。 ...
Definition: LockFree.h:783
int32_t max_msg
メッセージキューの作成の際に最大メッセージ数を設定することができます。
Definition: Platform.h:1173
指定された数のリスナーがキューから要素を取得できます。全てのリスナーが取得後、要素はキューから削除さ...
Definition: LockFree.h:739
#define NLIB_ATOMIC_ACQUIRE
gccの__ATOMIC_ACQUIREやC++11のstd::memory_order_acquireに準じます。
MemHolder * AllocUnsafe() noexcept
Alloc()と同様ですが、スレッドセーフではありません。
Definition: LockFree.h:811
errno_t Read(void *dest, size_t nbytes) noexcept
データをパイプから読み込みます。スレッドセーフです。
Definition: LockFree.h:360
int32_t nlib_mq
メッセージキューに関連付けられるハンドルです。ハンドルがゼロクリア(memset()を利用してください)された...
Definition: Platform.h:1157
void * nlib_atomic_loadptr(void *const *ptr, int memorder)
アトミックに値をロードします。動作はgccの__atomic_load_n()に準じます。
void SwapUnsafe(LockFreeStack &rhs) noexcept
オブジェクトをスワップします。スレッドセーフではありません。
Definition: LockFree.h:455
errno_t Enqueue(T *obj, int prio) noexcept
キューに要素を追加します。スレッドセーフです。
Definition: LockFree.h:647
errno_t Enqueue(const T &x) noexcept
キューに要素xを追加します。スレッドセーフです。
Definition: LockFree.h:528
UniquePtr< T, DestructorForLockFree< T > > DequeueType
Dequeue()の引数となる型です
Definition: LockFree.h:624
errno_t Write(const void *src, size_t nbytes) noexcept
データをパイプに書き込みます。スレッドセーフです。
Definition: LockFree.h:383
#define NLIB_LIKELY(x)
条件xが真になる傾向が高いことをコンパイラに示します。
Definition: Platform_unix.h:97
T * DequeueType
Dequeue(), DequeueUnsafe()の引数となる型です
Definition: LockFree.h:516
int32_t nlib_atomic_add_fetch32(int32_t *ptr, int32_t val, int memorder)
アトミックな値の加算を行います。動作はgccの__atomic_add_fetch()に準じます。
ロックフリーなスタックを実装しているクラスです。
Definition: LockFree.h:435
void nlib_atomic_storeptr(void **ptr, void *val, int memorder)
アトミックに値をストアします。動作はgccの__atomic_store_n()に準じます。
size_t GetListenerCount() const noexcept
Init()で指定したリスナーの数を返します。スレッドセーフです。
Definition: LockFree.h:773
オブジェクトをデストラクトするためのクラステンプレートです。特殊化して利用します。 ...
Definition: LockFree.h:429
void SwapUnsafe(LockFreeQueue &rhs) noexcept
オブジェクトをスワップします。スレッドセーフではありません。
Definition: LockFree.h:536
void nlib_atomic_thread_fence(int memorder)
指定されたメモリバリアを配置します。
void SwapUnsafe(LockFreeUnitHeap &rhs) noexcept
オブジェクトをスワップします。スレッドセーフではありません。
Definition: LockFree.h:818
メッセージキューの設定や現在の状態を格納する構造体です。
Definition: Platform.h:1171
ロックフリーなキューを実装しているクラスです。
Definition: LockFree.h:514
#define NLIB_NOEXCEPT
環境に合わせてnoexcept 又は同等の定義がされます。
Definition: Config.h:109
void SwapUnsafe(LockFreeBroadcastQueue &rhs) noexcept
オブジェクトをスワップします。スレッドセーフではありません。
Definition: LockFree.h:777
errno_t Dequeue(DequeueType &obj, int *prio) noexcept
キューから要素を取り出します。スレッドセーフです。
Definition: LockFree.h:651
開発環境別の設定が書かれるファイルです。
errno_t Close() noexcept
キューをクローズし初期化前の状態にします。スレッドセーフではありません。
Definition: LockFree.h:641
errno_t Init(size_t count) noexcept
キューを初期化します。スレッドセーフではありません。
Definition: LockFree.h:522
errno_t Dequeue(DequeueType x) noexcept
キューから要素を取り出してxに格納します。スレッドセーフです。
Definition: LockFree.h:529
アラインされたメモリを得たい場合に利用します。
errno_t Push(const T &x) noexcept
スタックに要素xを積みます。スレッドセーフです。
Definition: LockFree.h:449
errno_t nlib_mq_send(nlib_mq mq, nlib_mq_msg msg, int prio)
メッセージをキューに送信します。
#define NLIB_ATOMIC_RELAXED
gccの__ATOMIC_RELAXEDやC++11のstd::memory_order_relaxedに準じます。
LockFreeUnitHeap() noexcept
デフォルトコンストラクタです。
Definition: LockFree.h:793
errno_t Init(size_t max_size, size_t listeners) noexcept
キューを初期化します。スレッドセーフではありません。
Definition: LockFree.h:753
データの送り手側のスレッドと受け手側のスレッドがそれぞれ1つずつの場合、このクラスを用いてロックフリー...
Definition: LockFree.h:351
#define NLIB_FINAL
利用可能であればfinalが定義されます。そうでない場合は空文字列です。
Definition: Config.h:250
errno_t Init(size_t max_size) noexcept
キューを初期化します。スレッドセーフではありません。
Definition: LockFree.h:630
#define NLIB_STATIC_ASSERT(exp)
静的アサートが定義されます。利用可能であればstatic_assertを利用します。
Definition: Config.h:174
LockFreeBroadcastQueue() noexcept
デフォルトコンストラクタです。
Definition: LockFree.h:745
オブジェクトを初期化するためのクラステンプレートです。特殊化して利用します。
Definition: LockFree.h:423
~LockFreeStack() noexcept
デストラクタです。
Definition: LockFree.h:439
~LockFreeBroadcastQueue() noexcept
デストラクタです。
Definition: LockFree.h:746
errno_t Dequeue(int32_t listener_id, DequeueType &obj) noexcept
リスナーを指定してキューから要素を読み込みます。異なるlistener_idを利用している場合はスレッドセーフで...
Definition: LockFree.h:761
void Free(MemHolder *p) noexcept
メモリを解放します。スレッドセーフです。
Definition: LockFree.h:804
LockFreePriorityQueue() noexcept
デフォルトコンストラクタです。
Definition: LockFree.h:625
#define NLIB_NONNULL
全ての引数にNULLを指定することができないことを示します。
void nlib_atomic_store32(int32_t *ptr, int32_t val, int memorder)
アトミックに値をストアします。動作はgccの__atomic_store_n()に準じます。
int32_t flag
メッセージキューを作成する際の設定です。
Definition: Platform.h:1172
ロックフリーな優先度つきキューを実装したクラスで、nlib_mqをラップしています。
Definition: LockFree.h:622
~LockFreePriorityQueue() noexcept
デストラクタです。
Definition: LockFree.h:626
void * nlib_mq_msg
メッセージキューに格納されるメッセージの型です。
Definition: Platform.h:1163
static int nlib_clz64(uint64_t x)
MSB(most significant bit)から見て連続する0ビットの数を返します。
Definition: Platform.h:2692
errno_t Enqueue(const T *obj) noexcept
キューに要素を追加します。スレッドセーフです。
Definition: LockFree.h:757
int errno_t
intのtypedefで、戻り値としてPOSIXのエラー値を返すことを示します。
Definition: NMalloc.h:37