| 32 | } |
| 33 | |
| 34 | inline N* try_get() |
| 35 | { |
| 36 | auto head = freeListHead.load(std::memory_order_acquire); |
| 37 | while (head != nullptr) { |
| 38 | auto prevHead = head; |
| 39 | auto refs = head->freeListRefs.load(std::memory_order_relaxed); |
| 40 | if ((refs & REFS_MASK) == 0 || !head->freeListRefs.compare_exchange_strong(refs, refs + 1, |
| 41 | std::memory_order_acquire, std::memory_order_relaxed)) { |
| 42 | head = freeListHead.load(std::memory_order_acquire); |
| 43 | continue; |
| 44 | } |
| 45 | |
| 46 | // Good, reference count has been incremented (it wasn't at zero), which means |
| 47 | // we can read the next and not worry about it changing between now and the time |
| 48 | // we do the CAS |
| 49 | auto next = head->freeListNext.load(std::memory_order_relaxed); |
| 50 | if (freeListHead.compare_exchange_strong(head, next, |
| 51 | std::memory_order_acquire, std::memory_order_relaxed)) { |
| 52 | // Yay, got the node. This means it was on the list, which means |
| 53 | // shouldBeOnFreeList must be false no matter the refcount (because |
| 54 | // nobody else knows it's been taken off yet, it can't have been put back on). |
| 55 | RL_ASSERT((head->freeListRefs.load(std::memory_order_relaxed) & SHOULD_BE_ON_FREELIST) == 0); |
| 56 | |
| 57 | // Decrease refcount twice, once for our ref, and once for the list's ref |
| 58 | head->freeListRefs.fetch_add(-2, std::memory_order_release); |
| 59 | |
| 60 | return head; |
| 61 | } |
| 62 | |
| 63 | // OK, the head must have changed on us, but we still need to decrease the refcount we |
| 64 | // increased. |
| 65 | // Note that we don't need to release any memory effects, but we do need to ensure that the reference |
| 66 | // count decrement happens-after the CAS on the head. |
| 67 | refs = prevHead->freeListRefs.fetch_add(-1, std::memory_order_acq_rel); |
| 68 | if (refs == SHOULD_BE_ON_FREELIST + 1) { |
| 69 | add_knowing_refcount_is_zero(prevHead); |
| 70 | } |
| 71 | } |
| 72 | |
| 73 | return nullptr; |
| 74 | } |
| 75 | |
| 76 | // Useful for traversing the list when there's no contention (e.g. to destroy remaining nodes) |
| 77 | N* head_unsafe() const { return freeListHead.load(std::memory_order_relaxed); } |