nlib
LockFree.h
Go to the documentation of this file.
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
This function is similar to Free(), but not thread-safe.
Definition: LockFree.h:815
errno_t PopUnsafe(PopType x) noexcept
Picks up an element from the stack and stores it in x. This is not thread-safe.
Definition: LockFree.h:454
LockFreePipe() noexcept
Instantiates the object with default parameters (default constructor).
Definition: LockFree.h:353
int nlib_atomic_compare_exchangeptr(void **ptr, void **expected, void *desired, int weak, int success_memorder, int failure_memorder)
Compares and swaps atomic values. Its behavior is similar to the one for __atomic_compare_exchange_n(...
int32_t nlib_atomic_load32(const int32_t *ptr, int memorder)
Loads a value in an atomic operation. Its behavior is similar to the one for __atomic_load_n() of gcc...
#define NLIB_ALWAYS_INLINE
Indicates that the compiler is forced to perform inline expansion of functions.
Definition: Platform_unix.h:95
LockFreeQueue() noexcept
Instantiates the object with default parameters (default constructor).
Definition: LockFree.h:517
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().
Definition: LockFree.h:744
nlib_mq_msg_destructor destructor
A destructor function for a message taken from a message queue can be set or obtained.
Definition: Platform.h:1175
errno_t nlib_mq_close(nlib_mq mq)
Closes the message queue indicated with a handle.
#define NLIB_DISALLOW_COPY_AND_ASSIGN(TypeName)
Prohibits use of the copy constructor and assignment operator for the class specified by TypeName...
Definition: Config.h:183
errno_t nlib_mq_receive(nlib_mq mq, nlib_mq_msg *msg, int *prio)
Receives a message from a queue. It is the user&#39;s responsibility to delete the received messages usin...
errno_t Init(size_t count) noexcept
Initializes the stack. This is not thread-safe.
Definition: LockFree.h:443
T * PopType
The type for the argument of Pop() and PopUnsafe().
Definition: LockFree.h:437
#define NLIB_ATOMIC_RELEASE
Similar to __ATOMIC_RELEASE of gcc or std::memory_order_release of C++11.
LockFreeStack() noexcept
Instantiates the object with default parameters (default constructor).
Definition: LockFree.h:438
~LockFreeQueue() noexcept
Destructor.
Definition: LockFree.h:518
#define NLIB_UNLIKELY(x)
Indicates to the compiler that condition x is likely to be false.
Definition: Platform_unix.h:98
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.
Definition: LockFree.h:533
size_t GetBufferSize() noexcept
Returns the buffer size. This is thread-safe.
Definition: LockFree.h:354
In the C++11 environment (which supports alias templates), std::unique_ptr is made an alias template...
Definition: UniquePtr.h:108
errno_t PushUnsafe(const T &x) noexcept
Places the element x in the stack. This is not thread-safe.
Definition: LockFree.h:452
Defines that class that is corresponding to std::unique_ptr.
errno_t nlib_mq_open(nlib_mq *mq, const nlib_mq_attr *attr)
Creates a message queue to be used to exchange messages across threads.
errno_t Pop(PopType x) noexcept
Picks up an element from the stack and stores it in x. This is thread-safe.
Definition: LockFree.h:450
errno_t LockFreeInit(T **ptr) noexcept
Constructs an object in a thread safe manner.
Definition: LockFree.h:602
static int nlib_clz32(uint32_t x)
Returns the number of consecutive zero bits, with respect to the most significant bit (MSB)...
Definition: Platform.h:2690
void SwapUnsafe(LockFreePriorityQueue &rhs) noexcept
Swaps an object. This is not thread-safe.
Definition: LockFree.h:659
errno_t EnqueueUnsafe(const T &x) noexcept
Adds the element x to the queue. This is not thread-safe.
Definition: LockFree.h:531
#define NLIB_VIS_PUBLIC
Symbols for functions and classes are made available outside of the library.
Definition: Platform_unix.h:87
A pool allocator that can allocate or free a fixed size of memory region in a lock free manner...
Definition: LockFree.h:783
int32_t max_msg
When creating a message queue, you can set the maximum number of messages.
Definition: Platform.h:1173
The specified number of listeners can obtain elements from the queue. After all the listeners have ob...
Definition: LockFree.h:739
#define NLIB_ATOMIC_ACQUIRE
Similar to __ATOMIC_ACQUIRE of gcc or std::memory_order_acquire of C++11.
MemHolder * AllocUnsafe() noexcept
This function is similar to Alloc(), but not thread-safe.
Definition: LockFree.h:811
errno_t Read(void *dest, size_t nbytes) noexcept
Reads data from a pipe. This is thread-safe.
Definition: LockFree.h:360
int32_t nlib_mq
Handle associated with a message queue. If the handle is cleared to zero (using memset()), it will always be an invalid handle.
Definition: Platform.h:1157
void * nlib_atomic_loadptr(void *const *ptr, int memorder)
Loads a value in an atomic operation. Its behavior is similar to the one for __atomic_load_n() of gcc...
void SwapUnsafe(LockFreeStack &rhs) noexcept
Swaps an object. This is not thread-safe.
Definition: LockFree.h:455
errno_t Enqueue(T *obj, int prio) noexcept
Adds an element to the queue. This is thread-safe.
Definition: LockFree.h:647
errno_t Enqueue(const T &x) noexcept
Adds the element x to the queue. This is thread-safe.
Definition: LockFree.h:528
UniquePtr< T, DestructorForLockFree< T > > DequeueType
The type for the argument of Dequeue().
Definition: LockFree.h:624
errno_t Write(const void *src, size_t nbytes) noexcept
Writes data to a pipe. This is thread-safe.
Definition: LockFree.h:383
#define NLIB_LIKELY(x)
Indicates to the compiler that condition x is likely to be true.
Definition: Platform_unix.h:97
T * DequeueType
The type for the argument of Dequeue() and DequeueUnsafe().
Definition: LockFree.h:516
int32_t nlib_atomic_add_fetch32(int32_t *ptr, int32_t val, int memorder)
Adds atomic values. Its behavior is similar to the one for __atomic_add_fetch() of gcc...
This class implements a lock-free stack.
Definition: LockFree.h:435
void nlib_atomic_storeptr(void **ptr, void *val, int memorder)
Stores a value in an atomic operation. Its behavior is similar to the one for __atomic_store_n() of g...
size_t GetListenerCount() const noexcept
Returns the number of listeners specified in Init(). This is thread-safe.
Definition: LockFree.h:773
Class template for destructing an object. This should be specialized before use.
Definition: LockFree.h:429
void SwapUnsafe(LockFreeQueue &rhs) noexcept
Swaps an object. This is not thread-safe.
Definition: LockFree.h:536
void nlib_atomic_thread_fence(int memorder)
Places the specified memory barrier.
void SwapUnsafe(LockFreeUnitHeap &rhs) noexcept
Swaps an object. This is not thread-safe.
Definition: LockFree.h:818
Structure to store the settings and current status of a message queue.
Definition: Platform.h:1171
This class implements a lock-free queue.
Definition: LockFree.h:514
#define NLIB_NOEXCEPT
Defines noexcept geared to the environment, or the equivalent.
Definition: Config.h:109
void SwapUnsafe(LockFreeBroadcastQueue &rhs) noexcept
Swaps an object. This is not thread-safe.
Definition: LockFree.h:777
errno_t Dequeue(DequeueType &obj, int *prio) noexcept
Picks up an element from the queue. This is thread-safe.
Definition: LockFree.h:651
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...
Definition: LockFree.h:641
errno_t Init(size_t count) noexcept
Initializes the queue. This is not thread-safe.
Definition: LockFree.h:522
errno_t Dequeue(DequeueType x) noexcept
Picks up an element from the queue and stores it in x. This is thread-safe.
Definition: LockFree.h:529
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.
Definition: LockFree.h:449
errno_t nlib_mq_send(nlib_mq mq, nlib_mq_msg msg, int prio)
Sends a message to a queue.
#define NLIB_ATOMIC_RELAXED
Similar to __ATOMIC_RELAXED of gcc or std::memory_order_relaxed of C++11.
LockFreeUnitHeap() noexcept
Instantiates the object with default parameters (default constructor).
Definition: LockFree.h:793
errno_t Init(size_t max_size, size_t listeners) noexcept
Initializes the queue. This is not thread-safe.
Definition: LockFree.h:753
When a single sender thread sends data and a single receiver thread receives that data...
Definition: LockFree.h:351
#define NLIB_FINAL
Defines final if it is available for use. If not, holds an empty string.
Definition: Config.h:250
errno_t Init(size_t max_size) noexcept
Initializes the queue. This is not thread-safe.
Definition: LockFree.h:630
#define NLIB_STATIC_ASSERT(exp)
Defines a static assertion. Uses static_assert if it is available for use.
Definition: Config.h:174
LockFreeBroadcastQueue() noexcept
Instantiates the object with default parameters (default constructor).
Definition: LockFree.h:745
Class template for initializing an object. This should be specialized before use. ...
Definition: LockFree.h:423
~LockFreeStack() noexcept
Destructor.
Definition: LockFree.h:439
~LockFreeBroadcastQueue() noexcept
Destructor.
Definition: LockFree.h:746
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...
Definition: LockFree.h:761
void Free(MemHolder *p) noexcept
Frees memory. This is thread-safe.
Definition: LockFree.h:804
LockFreePriorityQueue() noexcept
Instantiates the object with default parameters (default constructor).
Definition: LockFree.h:625
#define NLIB_NONNULL
Indicates that you cannot specify NULL for all arguments.
void nlib_atomic_store32(int32_t *ptr, int32_t val, int memorder)
Stores a value in an atomic operation. Its behavior is similar to the one for __atomic_store_n() of g...
int32_t flag
Settings to be used when creating a message queue.
Definition: Platform.h:1172
Wraps nlib_mq with a class implementing a lock-free queue with a priority set.
Definition: LockFree.h:622
~LockFreePriorityQueue() noexcept
Destructor.
Definition: LockFree.h:626
void * nlib_mq_msg
Type of messages stored in a message queue.
Definition: Platform.h:1163
static int nlib_clz64(uint64_t x)
Returns the number of consecutive zero bits, with respect to the most significant bit (MSB)...
Definition: Platform.h:2692
errno_t Enqueue(const T *obj) noexcept
Adds an element to the queue. This is thread-safe.
Definition: LockFree.h:757
int errno_t
Indicates with an int-type typedef that a POSIX error value is returned as the return value...
Definition: NMalloc.h:37