nlib
LockFree.h
Go to the documentation of this file.
1 
2 #pragma once
3 #ifndef INCLUDE_NN_NLIB_LOCKFREE_H_
4 #define INCLUDE_NN_NLIB_LOCKFREE_H_
5 
6 #include <new>
7 #include "nn/nlib/Config.h"
8 #include "nn/nlib/TypeTraits.h"
9 #include "nn/nlib/UniquePtr.h"
11 
12 NLIB_NAMESPACE_BEGIN
13 
14 template<class T1, class T2 = void>
15 struct LockFreePlaceHolder {
16  T1 data; // T1 must be POD
17  union next_type {
18  uintptr_t aba_ptr;
19  LockFreePlaceHolder<T1, T2>* raw_ptr;
20  } next;
21  T2 aux;
22  void Init(const T1& elem) NLIB_NOEXCEPT {
23  data = elem;
24  aux = T2();
25  }
26 };
27 
28 template<class T1>
29 struct LockFreePlaceHolder<T1, void> {
30  T1 data; // T1 must be POD
31  union next_type {
32  uintptr_t aba_ptr;
33  LockFreePlaceHolder<T1, void>* raw_ptr;
34  } next;
35  void Init(const T1& elem) NLIB_NOEXCEPT {
36  data = elem;
37  }
38 };
39 
40 template<class T1, class T2 = void>
41 class LockFreePlaceHolderPool {
42  public:
43  NLIB_STATIC_ASSERT(IsPod<T1>::value);
44  LockFreePlaceHolderPool() NLIB_NOEXCEPT : invariant_(0), mask_(0), mem_(NULL) {}
45  ~LockFreePlaceHolderPool() NLIB_NOEXCEPT { delete[] mem_; }
46  errno_t Init(size_t count) NLIB_NOEXCEPT;
47  NLIB_ALWAYS_INLINE LockFreePlaceHolder<T1, T2>* CalcPtr(uintptr_t aba) const NLIB_NOEXCEPT {
48  return reinterpret_cast<LockFreePlaceHolder<T1, T2>*>((aba & mask_) | invariant_);
49  }
50  NLIB_ALWAYS_INLINE bool IsNull(uintptr_t aba) const NLIB_NOEXCEPT {
51  return aba & 1;
52  }
53  NLIB_ALWAYS_INLINE LockFreePlaceHolder<T1, T2>* Alloc() NLIB_NOEXCEPT {
54  LockFreePlaceHolder<T1, T2>* ptr;
55  uintptr_t expected = Load(&freelist_);
56  for (;;) {
57  if (NLIB_UNLIKELY(IsNull(expected))) return NULL;
58  ptr = this->CalcPtr(expected);
59  uintptr_t desired = Load(&ptr->next.aba_ptr);
60  if (NLIB_LIKELY(Cas(&freelist_, &expected, &desired, 1)))
61  break;
62  }
63  uintptr_t mask = mask_;
64  ptr->next.aba_ptr = (ptr->next.aba_ptr & ~mask) + (mask + 2);
65  return ptr;
66  }
67  NLIB_ALWAYS_INLINE void Free(LockFreePlaceHolder<T1, T2>* p) NLIB_NOEXCEPT {
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);
72  for (;;) {
73  Store(&p->next.aba_ptr, base | (expected & mask));
74  // must comfirm p->next written
75  if (NLIB_LIKELY(Cas(&freelist_, &expected, &desired, 1, NLIB_ATOMIC_RELEASE)))
76  break;
77  }
78  }
79  NLIB_ALWAYS_INLINE LockFreePlaceHolder<T1, T2>* AllocUnsafe() NLIB_NOEXCEPT {
80  uintptr_t expected = freelist_;
81  if (NLIB_UNLIKELY(IsNull(expected))) return NULL;
82  LockFreePlaceHolder<T1, T2>* ptr = this->CalcPtr(expected);
83  freelist_ = ptr->next.aba_ptr;
84  ptr->next.aba_ptr = 1;
85  return ptr;
86  }
87  NLIB_ALWAYS_INLINE void FreeUnsafe(LockFreePlaceHolder<T1, T2>* p) NLIB_NOEXCEPT {
88  p->next.aba_ptr = freelist_;
89  freelist_ = reinterpret_cast<uintptr_t>(p);
90  }
91  NLIB_ALWAYS_INLINE uintptr_t Load(uintptr_t* ptr) NLIB_NOEXCEPT {
92  void* val = nlib_atomic_loadptr(reinterpret_cast<void**>(ptr), NLIB_ATOMIC_RELAXED);
93  return reinterpret_cast<uintptr_t>(val);
94  }
95  NLIB_ALWAYS_INLINE uintptr_t Load(uintptr_t* ptr, int memorder) NLIB_NOEXCEPT {
96  void* val = nlib_atomic_loadptr(reinterpret_cast<void**>(ptr), memorder);
97  return reinterpret_cast<uintptr_t>(val);
98  }
99  NLIB_ALWAYS_INLINE void Store(uintptr_t* ptr, uintptr_t value) NLIB_NOEXCEPT {
100  nlib_atomic_storeptr(reinterpret_cast<void**>(ptr),
101  reinterpret_cast<void*>(value),
103  }
104  NLIB_ALWAYS_INLINE void Store(uintptr_t* ptr, uintptr_t value, int memorder) NLIB_NOEXCEPT {
105  nlib_atomic_storeptr(reinterpret_cast<void**>(ptr),
106  reinterpret_cast<void*>(value),
107  memorder);
108  }
109  NLIB_ALWAYS_INLINE int Cas(uintptr_t* ptr, uintptr_t* expected, uintptr_t* desired, int weak,
110  int success_memorder, int failure_memorder) NLIB_NOEXCEPT {
111  uintptr_t mask = mask_;
112  *desired = ((*desired & mask) | (mask + 1)) + (*expected & ~mask);
113  int rval = nlib_atomic_compare_exchangeptr(reinterpret_cast<void**>(ptr),
114  reinterpret_cast<void**>(expected),
115  reinterpret_cast<void*>(*desired),
116  weak, success_memorder, failure_memorder);
117  return rval;
118  }
119  NLIB_ALWAYS_INLINE int Cas(uintptr_t* ptr, uintptr_t* expected, uintptr_t* desired, int weak,
120  int success_memorder) NLIB_NOEXCEPT {
121  return Cas(ptr, expected, desired, weak, success_memorder, NLIB_ATOMIC_RELAXED);
122  }
123  NLIB_ALWAYS_INLINE int Cas(uintptr_t* ptr, uintptr_t* expected, uintptr_t* desired,
124  int weak) NLIB_NOEXCEPT {
125  return Cas(ptr, expected, desired, weak, NLIB_ATOMIC_RELAXED, NLIB_ATOMIC_RELAXED);
126  }
127  void SwapUnsafe(LockFreePlaceHolderPool& rhs) NLIB_NOEXCEPT { // NOLINT
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_;
134  rhs.mask_ = mask_;
135  rhs.mem_ = mem_;
136  freelist_ = freelist;
137  invariant_ = invariant;
138  mask_ = mask;
139  mem_ = mem;
140  }
141 
142  public:
143  errno_t Push(uintptr_t* stack, const T1& elem) NLIB_NOEXCEPT;
144  errno_t Pop(uintptr_t* stack, T1* elem) NLIB_NOEXCEPT;
145  errno_t Enqueue(uintptr_t* tail, const T1& elem) NLIB_NOEXCEPT;
146  errno_t Dequeue(uintptr_t* head, uintptr_t* tail, T1* elem) NLIB_NOEXCEPT;
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();
150  if (NLIB_UNLIKELY(!item_ptr)) return EAGAIN;
151 
152  // point of no failure
153  item_ptr->data = elem;
154  item_ptr->next.aba_ptr = *stack;
155  *stack = reinterpret_cast<uintptr_t>(item_ptr);
156  return 0;
157  }
158  errno_t PopUnsafe(uintptr_t* stack, T1* elem) NLIB_NOEXCEPT {
159  if (NLIB_UNLIKELY(IsNull(*stack))) return EAGAIN;
160  LockFreePlaceHolder<T1, T2>* ptr = CalcPtr(*stack);
161  *elem = ptr->data;
162  *stack = ptr->next.aba_ptr;
163  FreeUnsafe(ptr);
164  return 0;
165  }
166  errno_t EnqueueUnsafe(uintptr_t* tail, const T1& elem) NLIB_NOEXCEPT {
167  LockFreePlaceHolder<T1, T2>* item_ptr = AllocUnsafe();
168  if (NLIB_UNLIKELY(!item_ptr)) return EAGAIN;
169 
170  // point of no failure
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);
174  return 0;
175  }
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;
181 
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;
185  *head = first_next;
186  FreeUnsafe(first_ptr);
187  return 0;
188  }
189 
190  private:
191  uintptr_t freelist_;
192  uintptr_t invariant_;
193  uintptr_t mask_;
194  LockFreePlaceHolder<T1, T2>* mem_;
195  NLIB_DISALLOW_COPY_AND_ASSIGN(LockFreePlaceHolderPool);
196 };
197 
198 template<class T1, class T2>
199 errno_t LockFreePlaceHolderPool<T1, T2>::Init(size_t count) NLIB_NOEXCEPT {
200  if (NLIB_UNLIKELY(mem_)) return EALREADY;
201  LockFreePlaceHolder<T1, T2>* mem = new (std::nothrow) LockFreePlaceHolder<T1, T2>[count];
202  if (NLIB_UNLIKELY(!mem)) return ENOMEM;
203  uintptr_t freelist = 1;
204 #ifdef NLIB_64BIT
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;
208  mem[i].data = T1();
209  freelist = reinterpret_cast<uintptr_t>(&mem[i]);
210  }
211  }
212 #else
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;
216  mem[i].data = T1();
217  freelist = reinterpret_cast<uintptr_t>(&mem[i]);
218  }
219  }
220 #endif
221  uintptr_t first = reinterpret_cast<uintptr_t>(mem);
222  uintptr_t last = reinterpret_cast<uintptr_t>(mem + count);
223 #ifdef NLIB_64BIT
224  int sft = nlib_clz64(first ^ last);
225 #else
226  int sft = nlib_clz(first ^ last);
227 #endif
228  freelist_ = freelist;
229  mask_ = (static_cast<uintptr_t>(0) - 1) >> sft;
230  invariant_ = first & ~mask_;
231  mem_ = mem;
232  return 0;
233 }
234 
235 template<class T1, class T2>
236 NLIB_ALWAYS_INLINE errno_t LockFreePlaceHolderPool<T1, T2>::Push(uintptr_t* stack,
237  const T1& elem) NLIB_NOEXCEPT {
238  typedef LockFreePlaceHolder<T1, T2> item_type;
239  item_type* item_ptr = Alloc();
240  if (NLIB_UNLIKELY(!item_ptr)) return EAGAIN;
241 
242  // point of no failure
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);
248  for (;;) {
249  Store(&item_ptr->next.aba_ptr, base | (expected & mask));
250  // must comfirm p->next written
251  if (NLIB_LIKELY(Cas(stack, &expected, &desired, 1, NLIB_ATOMIC_RELEASE)))
252  break;
253  }
254  return 0;
255 }
256 
257 template<class T1, class T2>
258 NLIB_ALWAYS_INLINE errno_t LockFreePlaceHolderPool<T1, T2>::Pop(uintptr_t* stack,
259  T1* elem) NLIB_NOEXCEPT {
260  LockFreePlaceHolder<T1, T2>* ptr;
261  uintptr_t expected = Load(stack);
262  for (;;) {
263  if (NLIB_UNLIKELY(IsNull(expected))) return EAGAIN;
264  ptr = this->CalcPtr(expected);
265  uintptr_t desired = Load(&ptr->next.aba_ptr);
266  if (NLIB_LIKELY(Cas(stack, &expected, &desired, 1)))
267  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,
276  const T1& elem) NLIB_NOEXCEPT {
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),
295  1, NLIB_ATOMIC_ACQUIRE))) {
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(uintptr_t* head,
314  uintptr_t* tail,
315  T1* elem) NLIB_NOEXCEPT {
316  typedef LockFreePlaceHolder<T1, T2> item_type;
317  // Load(head), then Load(tail)
318  uintptr_t first = Load(head, NLIB_ATOMIC_ACQUIRE);
319  uintptr_t last = Load(tail);
320  for (;;) {
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,
324  NLIB_ATOMIC_ACQUIRE); // before first_new is loaded
325  uintptr_t first_new = Load(head);
326  if (NLIB_LIKELY(first == first_new)) {
327  if (NLIB_UNLIKELY(first_ptr == last_ptr)) {
328  if (NLIB_UNLIKELY(IsNull(first_next))) return EAGAIN;
329  // Update tail and retry
330  first = Load(head, NLIB_ATOMIC_ACQUIRE);
331  if (NLIB_LIKELY(Cas(tail, &last, &first_next, 0))) {
332  last = first_next;
333  }
334  } else {
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));
339  return 0;
340  }
341  first = Load(head, NLIB_ATOMIC_ACQUIRE);
342  last = Load(tail);
343  }
344  } else {
345  first = first_new;
346  last = Load(tail);
347  }
348  }
349 }
350 
351 template<size_t N>
353  public:
354  LockFreePipe() NLIB_NOEXCEPT : ofs_read_(0), ofs_write_(0) {}
355  size_t GetBufferSize() NLIB_NOEXCEPT {
356  NLIB_STATIC_ASSERT(N > 0);
357  NLIB_STATIC_ASSERT((N & (N - 1)) == 0);
358  NLIB_STATIC_ASSERT(N < INT32_MAX);
359  return N;
360  }
361  NLIB_ALWAYS_INLINE errno_t Read(void* dest, size_t nbytes) NLIB_NOEXCEPT {
362  uint32_t rofs = this->Load(&ofs_read_, NLIB_ATOMIC_RELAXED);
363  uint32_t wofs = this->Load(&ofs_write_, NLIB_ATOMIC_ACQUIRE);
364  // read ofs_write_, then read buffer_[rofs_actual]
365 
366  if (NLIB_UNLIKELY(nbytes > wofs - rofs)) return EAGAIN;
367  uint32_t rofs_actual = rofs & (N - 1);
368 
369  size_t ntail = N - rofs_actual;
370  if (ntail >= nbytes) {
371  // ARMCC needs this cast.
372  nlib_memcpy(dest,
373  nbytes,
374  reinterpret_cast<const void*>(&buffer_[rofs_actual]),
375  nbytes);
376  } else {
377  nlib_memcpy(dest,
378  nbytes,
379  reinterpret_cast<const void*>(&buffer_[rofs_actual]),
380  ntail);
381  nlib_memcpy(reinterpret_cast<void*>(reinterpret_cast<uint8_t*>(dest) + ntail),
382  nbytes - ntail,
383  reinterpret_cast<void*>(&buffer_[0]),
384  nbytes - ntail);
385  }
386  rofs += static_cast<uint32_t>(nbytes);
387 
388  // must not be reordered
389  this->Store(&ofs_read_, rofs, NLIB_ATOMIC_RELEASE);
390  return 0;
391  }
392  NLIB_ALWAYS_INLINE errno_t Write(const void* src, size_t nbytes) NLIB_NOEXCEPT {
393  uint32_t wofs = this->Load(&ofs_write_, NLIB_ATOMIC_RELAXED);
394  uint32_t rofs = this->Load(&ofs_read_, NLIB_ATOMIC_ACQUIRE);
395  // read ofs_read_, then write buffer_[wofs_actual]
396 
397  if (NLIB_UNLIKELY(nbytes > N - (wofs - rofs))) return EAGAIN;
398  uint32_t wofs_actual = wofs & (N - 1);
399 
400  size_t ntail = N - wofs_actual;
401  if (ntail >= nbytes) {
402  nlib_memcpy(reinterpret_cast<void*>(&buffer_[wofs_actual]),
403  nbytes,
404  src,
405  nbytes);
406  } else {
407  nlib_memcpy(reinterpret_cast<void*>(&buffer_[wofs_actual]),
408  ntail,
409  src,
410  ntail);
411  nlib_memcpy(reinterpret_cast<void*>(&buffer_[0]),
412  nbytes - ntail,
413  reinterpret_cast<const void*>(
414  reinterpret_cast<const uint8_t*>(src) + ntail),
415  nbytes - ntail);
416  }
417  wofs += static_cast<uint32_t>(nbytes);
418 
419  // must not be reordered
420  this->Store(&ofs_write_, wofs, NLIB_ATOMIC_RELEASE);
421  return 0;
422  }
423 
424  private:
425  NLIB_ALWAYS_INLINE uint32_t Load(uint32_t* p, int memorder) NLIB_NOEXCEPT {
426  return static_cast<uint32_t>(nlib_atomic_load32(
427  reinterpret_cast<int32_t*>(p), memorder));
428  }
429  NLIB_ALWAYS_INLINE void Store(uint32_t* p, uint32_t value, int memorder) NLIB_NOEXCEPT {
430  nlib_atomic_store32(reinterpret_cast<int32_t*>(p),
431  static_cast<int32_t>(value), memorder);
432  }
433 
434  uint32_t ofs_read_;
435  uint32_t ofs_write_;
436  uint8_t buffer_[N];
437  NLIB_DISALLOW_COPY_AND_ASSIGN(LockFreePipe);
438 };
439 
440 template<class T>
442  public:
443  T* operator()() NLIB_NOEXCEPT { return new (std::nothrow) T(); }
444 };
445 
446 template<class T>
448  public:
449  void operator()(T* ptr) NLIB_NOEXCEPT { delete ptr; }
450 };
451 
452 template<class T>
454  public:
455  typedef T* PopType;
456  LockFreeStack() NLIB_NOEXCEPT : top_(0), pool_() {}
457  ~LockFreeStack() NLIB_NOEXCEPT {
458  // T is POD, and not pointer
459  }
460  // NOT thread safe
461  errno_t Init(size_t count) NLIB_NOEXCEPT {
462  errno_t e = pool_.Init(count);
463  if (NLIB_UNLIKELY(e != 0)) return e;
464  top_ = 1;
465  return 0;
466  }
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); }
469  // NOT thread safe
470  errno_t PushUnsafe(const T& x) NLIB_NOEXCEPT { return pool_.PushUnsafe(&top_, x); }
471  // NOT thread safe
472  errno_t PopUnsafe(PopType x) NLIB_NOEXCEPT { return pool_.PopUnsafe(&top_, x); }
473 
474  private:
475  uintptr_t top_;
476  LockFreePlaceHolderPool<T> pool_;
477 };
478 
479 template<class T>
480 class LockFreeStack<T*> {
481  public:
482  typedef UniquePtr<T, DestructorForLockFree<T> > PopType;
483  LockFreeStack() NLIB_NOEXCEPT : top_(0), pool_() {}
484  ~LockFreeStack() NLIB_NOEXCEPT {
485  if (top_ != 0) {
486  T* elem;
487  while (0 == pool_.PopUnsafe(&top_, &elem)) {
488  DestructorForLockFree<T>()(elem);
489  }
490  }
491  }
492  // NOT thread safe
493  errno_t Init(size_t count) NLIB_NOEXCEPT {
494  errno_t e = pool_.Init(count);
495  if (NLIB_UNLIKELY(e != 0)) return e;
496  top_ = 1;
497  return 0;
498  }
499  errno_t Push(T* obj) NLIB_NOEXCEPT { return pool_.Push(&top_, obj); }
500  errno_t Pop(PopType& obj) NLIB_NOEXCEPT { // NOLINT
501  T* x;
502  errno_t e = pool_.Pop(&top_, &x);
503  if (e != 0) return e;
504  obj.reset(x);
505  return 0;
506  }
507  // NOT thread safe
508  errno_t PushUnsafe(T* obj) NLIB_NOEXCEPT { return pool_.PushUnsafe(&top_, obj); }
509  // NOT thread safe
510  errno_t PopUnsafe(PopType& obj) NLIB_NOEXCEPT { // NOLINT
511  T* x;
512  errno_t e = pool_.PopUnsafe(&top_, &x);
513  if (e != 0) return e;
514  obj.reset(x);
515  return 0;
516  }
517 
518  private:
519  uintptr_t top_;
520  LockFreePlaceHolderPool<T*> pool_;
521 };
522 
523 template<class T>
525  public:
526  typedef T* DequeueType;
527  LockFreeQueue() NLIB_NOEXCEPT : head_(0), tail_(0), pool_() {}
528  ~LockFreeQueue() NLIB_NOEXCEPT {
529  // T is POD, and not pointer
530  }
531  // NOT thread safe
532  errno_t Init(size_t count) NLIB_NOEXCEPT {
533  errno_t e = pool_.Init(count + 1);
534  if (NLIB_UNLIKELY(e != 0)) return e;
535  head_ = tail_ = reinterpret_cast<uintptr_t>(pool_.AllocUnsafe());
536  return 0;
537  }
538  errno_t Enqueue(const T& x) NLIB_NOEXCEPT { return pool_.Enqueue(&tail_, x); }
539  errno_t Dequeue(DequeueType x) NLIB_NOEXCEPT { return pool_.Dequeue(&head_, &tail_, x); }
540  // NOT thread safe
541  errno_t EnqueueUnsafe(const T& x) NLIB_NOEXCEPT { return pool_.EnqueueUnsafe(&tail_, x); }
542  // NOT thread safe
543  errno_t DequeueUnsafe(DequeueType x) NLIB_NOEXCEPT {
544  return pool_.DequeueUnsafe(&head_, &tail_, x);
545  }
546 
547  private:
548  uintptr_t head_;
549  uintptr_t tail_;
550  LockFreePlaceHolderPool<T> pool_;
551 };
552 
553 template<class T>
554 class LockFreeQueue<T*> {
555  public:
556  typedef UniquePtr<T, DestructorForLockFree<T> > DequeueType;
557  LockFreeQueue() NLIB_NOEXCEPT : head_(0), tail_(0), pool_() {}
558  ~LockFreeQueue() NLIB_NOEXCEPT {
559  if (head_ != 0) {
560  T* elem;
561  while (0 == pool_.DequeueUnsafe(&head_, &tail_, &elem)) {
562  DestructorForLockFree<T>()(elem);
563  }
564  }
565  }
566  // NOT thread safe
567  errno_t Init(size_t count) NLIB_NOEXCEPT {
568  errno_t e = pool_.Init(count + 1);
569  if (NLIB_UNLIKELY(e != 0)) return e;
570  head_ = tail_ = reinterpret_cast<uintptr_t>(pool_.AllocUnsafe());
571  return 0;
572  }
573  errno_t Enqueue(T* obj) NLIB_NOEXCEPT { return pool_.Enqueue(&tail_, obj); }
574  errno_t Dequeue(DequeueType& obj) NLIB_NOEXCEPT { // NOLINT
575  T* x;
576  errno_t e = pool_.Dequeue(&head_, &tail_, &x);
577  if (e != 0) return e;
578  obj.reset(x);
579  return 0;
580  }
581  // NOT thread safe
582  errno_t EnqueueUnsafe(T* x) NLIB_NOEXCEPT { return pool_.EnqueueUnsafe(&tail_, x); }
583  // NOT thread safe
584  errno_t DequeueUnsafe(DequeueType& obj) NLIB_NOEXCEPT { // NOLINT
585  T* x;
586  errno_t e = pool_.DequeueUnsafe(&head_, &tail_, &x);
587  if (e != 0) return e;
588  obj.reset(x);
589  return 0;
590  }
591 
592  private:
593  uintptr_t head_;
594  uintptr_t tail_;
595  LockFreePlaceHolderPool<T*> pool_;
596 };
597 
598 template<class T>
599 errno_t LockFreeInit(T** ptr) NLIB_NOEXCEPT NLIB_NONNULL;
600 
601 template<class T>
602 inline errno_t LockFreeInit(T** ptr) NLIB_NOEXCEPT {
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),
612  &pold, reinterpret_cast<void*>(obj), 0,
614  return 0;
615  } else {
617  return 0;
618  }
619 }
620 
621 template<class T>
623  public:
625  LockFreePriorityQueue() NLIB_NOEXCEPT : mq_() {
626  mq_.raw_handle = 0;
627  }
628  ~LockFreePriorityQueue() NLIB_NOEXCEPT {
629  if (mq_.raw_handle != 0) (void)nlib_mq_close(mq_);
630  }
631  // NOT thread safe
632  errno_t Init(size_t max_size) NLIB_NOEXCEPT {
633  // not thread safe
634  if (mq_.raw_handle != 0) return EALREADY;
635  if (max_size > INT32_MAX) return EINVAL;
636  nlib_mq_attr attr;
637  attr.flag = NLIB_MQ_LOCKFREE;
638  attr.max_msg = static_cast<int32_t>(max_size);
639  attr.destructor = LockFreePriorityQueue::dtor;
640  return nlib_mq_open(&mq_, &attr);
641  }
642  // NOT thread safe
643  errno_t Close() NLIB_NOEXCEPT {
644  // not thread safe
645  nlib_mq mq = mq_;
646  mq_.raw_handle = 0;
647  return nlib_mq_close(mq);
648  }
649  errno_t Enqueue(T* obj, int prio) NLIB_NOEXCEPT {
650  // thread safe
651  return nlib_mq_send(mq_, obj, prio);
652  }
653  errno_t Dequeue(DequeueType& obj, int* prio) NLIB_NOEXCEPT { // NOLINT
654  // thread safe
655  T* x;
656  errno_t e = nlib_mq_receive(mq_, reinterpret_cast<nlib_mq_msg*>(&x), prio);
657  if (e != 0) return e;
658  obj.reset(x);
659  return 0;
660  }
661 
662  private:
663  static void dtor(nlib_mq_msg msg) {
664  T* obj = reinterpret_cast<T*>(msg);
666  }
667 
668  nlib_mq mq_;
669 };
670 
671 namespace detail {
672 
673 class LockFreeBroadcastQueueImpl {
674  typedef LockFreePlaceHolder<const void*, int32_t> item_type;
675 
676  public:
677  LockFreeBroadcastQueueImpl() NLIB_NOEXCEPT
678  : head_(1), tail_(1), listener_count_(0), pool_(), listeners_() {}
679  ~LockFreeBroadcastQueueImpl() NLIB_NOEXCEPT {}
680  NLIB_VIS_PUBLIC errno_t Init(size_t max_size, size_t listeners) NLIB_NOEXCEPT;
681  errno_t Enqueue(const void* msg) NLIB_NOEXCEPT {
682  // thread safe
683  return pool_.Enqueue(&tail_, msg);
684  }
685  errno_t Dequeue(int32_t listener_id, const void** msg) NLIB_NOEXCEPT {
686  // thread safe if listener_id is different
687  if (NLIB_UNLIKELY(listener_id < 0) ||
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;
694  pos = next;
696  return 0;
697  }
698  NLIB_VIS_PUBLIC const void* CheckAndRemove() NLIB_NOEXCEPT;
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;
704  *msg = p;
705  return 0;
706  }
707  size_t GetListenerCount() const NLIB_NOEXCEPT { return listener_count_; }
708 
709  private:
710  uintptr_t Load(uintptr_t* p, int memorder = NLIB_ATOMIC_RELAXED) NLIB_NOEXCEPT {
711  return reinterpret_cast<uintptr_t>(nlib_atomic_loadptr(reinterpret_cast<void**>(p),
712  memorder));
713  }
714 
715  private:
716  uintptr_t head_;
717  uintptr_t tail_;
718  int32_t listener_count_;
719  LockFreePlaceHolderPool<const void*, int32_t> pool_;
720  UniquePtr<uintptr_t[]> listeners_;
721 };
722 
723 } // namespace detail
724 
725 template<class T>
727  public:
728  struct empty_func {
729  void operator()(const T*) {}
730  };
732  LockFreeBroadcastQueue() NLIB_NOEXCEPT : impl_() {}
733  ~LockFreeBroadcastQueue() NLIB_NOEXCEPT {
734  const void* p;
735  while (impl_.DeleteUnsafe(&p) == 0) {
736  DestructorForLockFree<const T>()(reinterpret_cast<const T*>(p));
737  }
738  }
739  // NOT thread safe
740  errno_t Init(size_t max_size, size_t listeners) NLIB_NOEXCEPT {
741  // not thread safe
742  return impl_.Init(max_size, listeners);
743  }
744  errno_t Enqueue(const T* obj) NLIB_NOEXCEPT {
745  // thread safe
746  return impl_.Enqueue(obj);
747  }
748  errno_t Dequeue(int32_t listener_id, DequeueType& obj) NLIB_NOEXCEPT { // NOLINT
749  // thread safe if listener_id is different
750  const void* x;
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());
755  if (p) {
757  }
758  return 0;
759  }
760  size_t GetListenerCount() const NLIB_NOEXCEPT {
761  // thread safe
762  return impl_.GetListenerCount();
763  }
764 
765  private:
766  detail::LockFreeBroadcastQueueImpl impl_;
767 };
768 
770  public:
771  class MemHolder {
772  public:
773  void* Get() NLIB_NOEXCEPT { return ptr_; }
774 
775  private:
776  void* const ptr_;
778  };
779  LockFreeUnitHeap() NLIB_NOEXCEPT : mem_(), pool_() {}
780  // NOT thread safe
781  NLIB_VIS_PUBLIC errno_t Init(size_t unit_size, size_t align,
782  size_t count) NLIB_NOEXCEPT;
783  ~LockFreeUnitHeap() NLIB_NOEXCEPT {}
784 
785  // MemHolder* x = heap.Alloc();
786  // void* ptr = x->Get(); // 'ptr' is what you want.
787  NLIB_ALWAYS_INLINE MemHolder* Alloc() NLIB_NOEXCEPT {
788  return reinterpret_cast<MemHolder*>(pool_.Alloc());
789  }
790 
791  NLIB_ALWAYS_INLINE void Free(MemHolder* p) NLIB_NOEXCEPT {
792  pool_.Free(reinterpret_cast<LockFreePlaceHolder<void*>*>(p));
793  }
794 
795  // NOT thread safe
796  // MemHolder* x = heap.Alloc();
797  // void* ptr = x->Get(); // 'ptr' is what you want.
798  NLIB_ALWAYS_INLINE MemHolder* AllocUnsafe() NLIB_NOEXCEPT {
799  return reinterpret_cast<MemHolder*>(pool_.AllocUnsafe());
800  }
801  // NOT thread safe
802  NLIB_ALWAYS_INLINE void FreeUnsafe(MemHolder* p) NLIB_NOEXCEPT {
803  pool_.FreeUnsafe(reinterpret_cast<LockFreePlaceHolder<void*>*>(p));
804  }
805 
806  private:
808  LockFreePlaceHolderPool<void*> pool_;
810 };
811 
812 NLIB_NAMESPACE_END
813 
814 #endif // INCLUDE_NN_NLIB_LOCKFREE_H_
#define NLIB_NOEXCEPT
Defines noexcept geared to the environment, or the equivalent.
Definition: Platform.h:2151
void FreeUnsafe(MemHolder *p) noexcept
This function is similar to Free(), but not thread-safe.
Definition: LockFree.h:802
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:472
LockFreePipe() noexcept
Instantiates the object with default parameters (default constructor).
Definition: LockFree.h:354
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_UNLIKELY(x)
Indicates to the compiler that condition x is likely to be false.
Definition: Platform_unix.h:62
LockFreeQueue() noexcept
Instantiates the object with default parameters (default constructor).
Definition: LockFree.h:527
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().
Definition: LockFree.h:731
nlib_mq_msg_destructor destructor
A destructor function for a message taken from a message queue can be set or obtained.
Definition: Platform.h:801
errno_t nlib_mq_close(nlib_mq mq)
Closes the message queue indicated with a handle.
#define NLIB_FINAL
Defines final if it is available for use. If not, holds an empty string.
#define NLIB_NONNULL
Indicates that you cannot specify NULL for all arguments.
Definition: Platform_unix.h:66
#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:126
NLIB_CHECK_RESULT errno_t nlib_mq_receive(nlib_mq mq, nlib_mq_msg *msg, int *prio)
Receives a message from a queue. It is the user'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:461
T * PopType
The type for the argument of Pop() and PopUnsafe().
Definition: LockFree.h:455
LockFreeStack() noexcept
Instantiates the object with default parameters (default constructor).
Definition: LockFree.h:456
#define NLIB_ATOMIC_RELEASE
Similar to __ATOMIC_RELEASE of gcc or std::memory_order_release of C++11.
~LockFreeQueue() noexcept
Destructor.
Definition: LockFree.h:528
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:543
size_t GetBufferSize() noexcept
Returns the buffer size. This is thread-safe.
Definition: LockFree.h:355
UniquePtr owns the pointer, and when it goes out of scope, the pointer is released by the destructor ...
Definition: UniquePtr.h:96
errno_t PushUnsafe(const T &x) noexcept
Places the element x in the stack. This is not thread-safe.
Definition: LockFree.h:470
Defines that class that is corresponding to std::unique_ptr.
NLIB_CHECK_RESULT 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:468
errno_t LockFreeInit(T **ptr) noexcept
Constructs an object in a thread safe manner.
Definition: LockFree.h:602
errno_t EnqueueUnsafe(const T &x) noexcept
Adds the element x to the queue. This is not thread-safe.
Definition: LockFree.h:541
#define NLIB_LIKELY(x)
Indicates to the compiler that condition x is likely to be true.
Definition: Platform_unix.h:61
A pool allocator that can allocate or free a fixed size of memory region in a lock free manner...
Definition: LockFree.h:769
int32_t max_msg
When creating a message queue, you can set the maximum number of messages.
Definition: Platform.h:799
The specified number of listeners can obtain elements from the queue. After all the listeners have ob...
Definition: LockFree.h:726
int nlib_clz(uint32_t x)
Returns the number of consecutive zero bits, with respect to the most significant bit (MSB)...
MemHolder * AllocUnsafe() noexcept
This function is similar to Alloc(), but not thread-safe.
Definition: LockFree.h:798
errno_t Read(void *dest, size_t nbytes) noexcept
Reads data from a pipe. This is thread-safe.
Definition: LockFree.h:361
int32_t nlib_mq
Handle associated with a message queue. If the handle is cleared to zero (usubg memset()), it will always be an invalid handle.
Definition: Platform.h:783
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...
errno_t Enqueue(T *obj, int prio) noexcept
Adds an element to the queue. This is thread-safe.
Definition: LockFree.h:649
errno_t Enqueue(const T &x) noexcept
Adds the element x to the queue. This is thread-safe.
Definition: LockFree.h:538
UniquePtr< T, DestructorForLockFree< T > > DequeueType
The type for the argument of Dequeue() and DequeueUnsafe().
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:392
T * DequeueType
The type for the argument of Dequeue() and DequeueUnsafe().
Definition: LockFree.h:526
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:453
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...
Class template for destructing an object. This should be specialized before use.
Definition: LockFree.h:447
void nlib_atomic_thread_fence(int memorder)
Places the specified memory barrier.
MemHolder * Alloc() noexcept
Allocates memory. The allocated region can be obtained by executing Get() on the returned pointer to ...
Definition: LockFree.h:787
Structure to store the settings and current status of a message queue.
Definition: Platform.h:797
size_t GetListenerCount() const noexcept
Returns the number of listeners specified in Init(). This is thread-safe.
Definition: LockFree.h:760
This class implements a lock-free queue.
Definition: LockFree.h:524
errno_t Dequeue(DequeueType &obj, int *prio) noexcept
Picks up an element from the queue. This is thread-safe.
Definition: LockFree.h:653
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:643
errno_t Init(size_t count) noexcept
Initializes the queue. This is not thread-safe.
Definition: LockFree.h:532
#define NLIB_ATOMIC_ACQUIRE
Similar to __ATOMIC_ACQUIRE of gcc or std::memory_order_acquire of C++11.
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:539
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:467
NLIB_CHECK_RESULT errno_t nlib_mq_send(nlib_mq mq, nlib_mq_msg msg, int prio)
Sends a message to a queue.
LockFreeUnitHeap() noexcept
Instantiates the object with default parameters (default constructor).
Definition: LockFree.h:779
errno_t Init(size_t max_size, size_t listeners) noexcept
Initializes the queue. This is not thread-safe.
Definition: LockFree.h:740
#define NLIB_ATOMIC_RELAXED
Similar to __ATOMIC_RELAXED of gcc or std::memory_order_relaxed of C++11.
#define NLIB_ALWAYS_INLINE
Indicates that the compiler is forced to perform inline expansion of functions.
Definition: Platform_unix.h:59
#define NLIB_VIS_PUBLIC
Symbols for functions and classes are made available outside of the library.
Definition: Platform_unix.h:51
~LockFreeUnitHeap() noexcept
Destructor.
Definition: LockFree.h:783
When a single sender thread sends data and a single receiver thread receives that data...
Definition: LockFree.h:352
errno_t Init(size_t max_size) noexcept
Initializes the queue. This is not thread-safe.
Definition: LockFree.h:632
#define NLIB_STATIC_ASSERT(exp)
Defines a static assertion. Uses static_assert if it is available for use.
Definition: Config.h:117
LockFreeBroadcastQueue() noexcept
Instantiates the object with default parameters (default constructor).
Definition: LockFree.h:732
Class template for initializing an object. This should be specialized before use. ...
Definition: LockFree.h:441
~LockFreeStack() noexcept
Destructor.
Definition: LockFree.h:457
~LockFreeBroadcastQueue() noexcept
Destructor.
Definition: LockFree.h:733
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:748
void Free(MemHolder *p) noexcept
Frees memory. This is thread-safe.
Definition: LockFree.h:791
LockFreePriorityQueue() noexcept
Instantiates the object with default parameters (default constructor).
Definition: LockFree.h:625
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. Value Description NLIB_MQ_BLOCK When reading an e...
Definition: Platform.h:798
int nlib_clz64(uint64_t x)
Returns the number of consecutive zero bits, with respect to the most significant bit (MSB)...
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:628
errno_t nlib_memcpy(void *s1, size_t s1max, const void *s2, size_t n)
An implementation corresponding to N1078 memcpy_s.
Definition: Platform.h:2095
void * nlib_mq_msg
Type of messages stored in a message queue.
Definition: Platform.h:789
errno_t Enqueue(const T *obj) noexcept
Adds an element to the queue. This is thread-safe.
Definition: LockFree.h:744
int errno_t
Indicates with an int-type typedef that a POSIX error value is returned as the return value...
Definition: NMalloc.h:24