lingxi-li / lock_free Goto Github PK

Make the following allocator-aware:

• shared_ptr
• atomic_shared_ptr
• queue

It may not always be convenient to supply capacity at construction time. For example, when the allocator is a static data member. Allocator should be DefaultConstructible and be able to be reset with a sensible capacity at a later post-construction time.

With current memory order specification, no happens-before requirement is imposed between head and tail update. Consider try_pop(). hold_ptr() ensures that the latest value of head is read, yet any value in the modification order of tail can be read. Therefore, head != tail doesn't necessarily mean a non-empty queue.

Let's try to establish order between head and tail.

1. Initially, head == tail.
2. The first thread that successfully pops is OK. It sees a tail which is not so outdated that breaks any invariant. The pop should issue a release on head.
3. Any later popping thread needs to hold head before doing anything else. Let hold_ptr() issue an acquire on head. Since it reads the latest value of head, it's therefore guaranteed to acquire the release issued in 2, and sees a tail which is not so outdated that breaks any invariant.

allocator is used to support efficient implementation of fixed-capacity/capacitated data structures. Create a sub-namespace cap (capacitated) for these data structures and move allocator to it.

See this.

C++17 has some killing features that I cannot simply ignore. std::is_aggregate is one of them.

This concerns uniform initialization. By that, you may think I'm talking about the {} syntax. But I don't. What do you expect std::make_unique<std::vector<int>>(2, 1) to make, [1, 1] or [2, 1]? Think about it and you see the issue. It may be problematic if we simply stick to {} as a kind of uniform initialization. We cannot stick to () either, for it doesn't work for aggregate types (unless it's empty). In my humble opinion, genuine uniform initialization should do the following:

1. For non-aggregate type, use () syntax.
2. For aggregate type, use {} syntax.

With std::is_aggregate introduced in C++17, implementing this genuine uniform initialization becomes straightforward.

Now, you may wonder why use aggregate types in the first place? Well, I don't bother writing boilerplate member-wise constructors, and want to leverage aggregate initialization. For example, instead of

struct stru {
  stru(int a = 0, int b = 0, int c = 0) noexcept:
    a(a), b(b), c(c) {
  }

  int a, b, c;
};
stru s0, s1(1), s2(1, 2);

why not simply

struct stru {
  int a, b, c;
};
stru s0{}, s1{1}, s2{1, 2};

For example, allocator::allocate() is currently implemented as

  T* allocate(std::size_t = 1) {
    auto oldhead = head.load(acq);
    do {
      if (!oldhead) throw std::bad_alloc{};
    }
    while (!head.compare_exchange_weak(oldhead, oldhead->next, rlx, acq));
    return std::addressof(oldhead->data);
  }

When head compares equal to oldhead, oldhead->next may already be outdated and invalid.

allocate()
head.trefcnt counts the number of successful pops. It follows that when head == oldhead, nothing has happened in the meantime: 1) No pop happened, otherwise head.trefcnt would have changed; 2) no push happened, otherwise head.p would have changed. Since compare_exchange() compares the latest value, if successful, oldhead is the latest value. oldhead is read with acquire, and thus acquires the results of the latest push. oldhead.p->next.load(rlx) is therefore latest. A successful compare_exchange() thus correctly delinks the current head. Successful compare_exchange() can be a relaxed operation, it only delinks head, and doesn't modify anything to the node.