1#include <xrpl/basics/IntrusivePointer.h>
2#include <xrpl/basics/IntrusivePointer.ipp>
3#include <xrpl/basics/IntrusiveRefCounts.h>
5#include <gtest/gtest.h>
74 cv.wait(lock, [&] {
return generation != currentGeneration; });
83 PartiallyDeletedStarted,
89class TIBase :
public IntrusiveRefCounts
96 [[nodiscard]]
static TrackedState
99 if (
id >= state.
size())
102 return state[id].load(std::memory_order_acquire);
106 resetStates(
bool resetCallback)
108 for (std::size_t i = 0; i < kMaxStates; ++i)
109 state[i].store(TrackedState::Uninitialized, std::memory_order_release);
110 nextId.store(0, std::memory_order_release);
112 TIBase::tracingCallback = [](TrackedState, std::optional<TrackedState>) {};
115 struct ResetStatesGuard
117 bool resetCallback{
false};
119 ResetStatesGuard(
bool resetCallback) : resetCallback{resetCallback}
121 TIBase::resetStates(resetCallback);
126 TIBase::resetStates(resetCallback);
130 TIBase() : id{checkoutID()}
132 state[id].store(TrackedState::Alive, std::memory_order_relaxed);
137 using enum TrackedState;
139 tracingCallback(state[
id].load(std::memory_order_relaxed), DeletedStarted);
144 state[id].store(DeletedStarted, std::memory_order_relaxed);
146 tracingCallback(DeletedStarted, Deleted);
148 state[id].store(TrackedState::Deleted, std::memory_order_relaxed);
150 tracingCallback(TrackedState::Deleted, std::nullopt);
154 partialDestructor()
const
156 using enum TrackedState;
158 tracingCallback(state[
id].load(std::memory_order_relaxed), PartiallyDeletedStarted);
160 state[id].store(PartiallyDeletedStarted, std::memory_order_relaxed);
162 tracingCallback(PartiallyDeletedStarted, PartiallyDeleted);
164 state[id].store(PartiallyDeleted, std::memory_order_relaxed);
166 tracingCallback(PartiallyDeleted, std::nullopt);
169 static std::function<void(TrackedState, std::optional<TrackedState>)> tracingCallback;
171 std::size_t
const id;
174 [[nodiscard]]
static std::size_t
177 auto const id = nextId.fetch_add(1, std::memory_order_acq_rel);
178 if (
id >= state.size())
179 throw std::out_of_range(
"TIBase state capacity exceeded");
185std::array<std::atomic<TrackedState>, TIBase::kMaxStates> TIBase::state;
186std::atomic<std::size_t> TIBase::nextId{0};
188std::function<void(TrackedState, std::optional<TrackedState>)> TIBase::tracingCallback =
189 [](TrackedState, std::optional<TrackedState>) {};
193TEST(IntrusiveSharedTest, ref_counts_on_a_bare_object)
195 TIBase::ResetStatesGuard
const rsg{
true};
198 EXPECT_EQ(b.useCount(), 1);
200 EXPECT_EQ(b.useCount(), 1);
201 auto const s = b.releaseStrongRef();
203 EXPECT_EQ(b.useCount(), 0);
204 TIBase
const* pb = &b;
207 auto const w = b.releaseWeakRef();
211TEST(IntrusiveSharedTest, strong_and_weak_containers_track_liveness)
215 TIBase::ResetStatesGuard
const rsg{
true};
217 using enum TrackedState;
220 EXPECT_EQ(TIBase::getState(
id), Alive);
221 EXPECT_EQ(b->useCount(), 1);
223 for (
auto i = 0uz; i < 10; ++i)
229 EXPECT_EQ(TIBase::getState(
id), Alive);
231 EXPECT_EQ(TIBase::getState(
id), Alive);
233 EXPECT_EQ(TIBase::getState(
id), Deleted);
237 EXPECT_EQ(TIBase::getState(
id), Alive);
238 EXPECT_EQ(b->useCount(), 1);
239 for (
auto i = 0uz; i < 10; ++i)
242 EXPECT_EQ(b->useCount(), 1);
244 EXPECT_EQ(TIBase::getState(
id), Alive);
246 EXPECT_EQ(TIBase::getState(
id), Alive);
248 EXPECT_EQ(TIBase::getState(
id), PartiallyDeleted);
249 while (!weak.
empty())
253 EXPECT_EQ(TIBase::getState(
id), PartiallyDeleted);
256 EXPECT_EQ(TIBase::getState(
id), Deleted);
259TEST(IntrusiveSharedTest, a_weak_pointer_cannot_revive_a_partially_deleted_object)
261 TIBase::ResetStatesGuard
const rsg{
true};
263 using enum TrackedState;
265 auto const id = b->id;
266 EXPECT_EQ(TIBase::getState(
id), Alive);
268 EXPECT_EQ(TIBase::getState(
id), Alive);
270 EXPECT_TRUE(s && s->useCount() == 2);
272 EXPECT_TRUE(TIBase::getState(
id) == Alive);
273 EXPECT_TRUE(s && s->useCount() == 1);
275 EXPECT_EQ(TIBase::getState(
id), PartiallyDeleted);
282 EXPECT_EQ(TIBase::getState(
id), Deleted);
285TEST(IntrusiveSharedTest, shared_weak_union_converts_between_strong_and_weak)
287 TIBase::ResetStatesGuard
const rsg{
true};
289 using enum TrackedState;
292 EXPECT_TRUE(b.isStrong() && b.useCount() == 1);
293 auto const id = b.get()->id;
294 EXPECT_EQ(TIBase::getState(
id), Alive);
296 EXPECT_TRUE(TIBase::getState(
id) == Alive);
297 EXPECT_TRUE(w.isStrong() && b.useCount() == 2);
299 EXPECT_TRUE(w.isWeak() && b.useCount() == 1);
301 EXPECT_TRUE(s.isWeak() && b.useCount() == 1);
303 EXPECT_TRUE(s.isStrong() && b.useCount() == 2);
305 EXPECT_EQ(TIBase::getState(
id), Alive);
306 EXPECT_EQ(s.useCount(), 1);
307 EXPECT_FALSE(w.expired());
309 EXPECT_EQ(TIBase::getState(
id), PartiallyDeleted);
310 EXPECT_TRUE(w.expired());
314 EXPECT_TRUE(w.isWeak());
316 EXPECT_EQ(TIBase::getState(
id), Deleted);
319TEST(IntrusiveSharedTest, shared_weak_union_assignment)
323 TIBase::ResetStatesGuard
const rsg{
true};
328 auto const id1 = strong1->id;
329 auto const id2 = strong2->id;
338 EXPECT_EQ(union1.
get(), strong1.get());
339 EXPECT_EQ(union2.
get(), strong2.get());
345 EXPECT_EQ(union1.
get(), union2.
get());
346 EXPECT_EQ(TIBase::getState(id1), TrackedState::Alive);
347 EXPECT_EQ(TIBase::getState(id2), TrackedState::Alive);
351 EXPECT_EQ(TIBase::getState(id2), TrackedState::Alive);
352 int const initialRefCount = strong2->useCount();
353#pragma clang diagnostic push
354#pragma clang diagnostic ignored "-Wself-assign-overloaded"
356#pragma clang diagnostic pop
358 EXPECT_EQ(union1.
get(), strong2.get());
359 EXPECT_EQ(TIBase::getState(id2), TrackedState::Alive);
360 EXPECT_EQ(strong2->useCount(), initialRefCount);
364 EXPECT_EQ(union1.
get(),
nullptr);
370 EXPECT_EQ(union1.
get(),
nullptr);
371 EXPECT_EQ(TIBase::getState(id2), TrackedState::Deleted);
374TEST(IntrusiveSharedTest, partial_delete)
383 using enum TrackedState;
385 TIBase::ResetStatesGuard
const rsg{
true};
394 using enum TrackedState;
406 EXPECT_EQ(cur, PartiallyDeleted);
409 case PartiallyDeletedStarted: {
411 using namespace std::chrono_literals;
419 case PartiallyDeleted:
420 EXPECT_FALSE(partialDeleteRan.
exchange(
true) || destructorRan.
load());
424 EXPECT_FALSE(destructorRan.
exchange(
true));
446 EXPECT_TRUE(destructorRan.
load() && partialDeleteRan.
load());
449TEST(IntrusiveSharedTest, convert_last_strong_to_weak)
451 using enum TrackedState;
453 TIBase::ResetStatesGuard
const rsg{
true};
456 auto const id = p.
get()->id;
457 EXPECT_EQ(TIBase::getState(
id), Alive);
462 EXPECT_EQ(TIBase::getState(
id), PartiallyDeleted);
465 EXPECT_EQ(TIBase::getState(
id), Deleted);
468TEST(IntrusiveSharedTest, multithreaded_convert_to_weak_partial_delete)
470 using enum TrackedState;
472 TIBase::ResetStatesGuard
const rsg{
true};
478 auto const id = converted.
get()->id;
492 EXPECT_EQ(cur, PartiallyDeleted);
495 case PartiallyDeletedStarted:
498 otherReleasedSyncPoint.
wait();
501 case PartiallyDeleted:
502 EXPECT_FALSE(partialDeleteRan.
exchange(
true) || destructorRan.
load());
506 EXPECT_FALSE(destructorRan.
exchange(
true));
516 partialDeleteStartedSyncPoint.
wait();
528 EXPECT_TRUE(partialDeleteRan.
load());
529 EXPECT_FALSE(destructorRan.
load());
530 EXPECT_TRUE(converted.
isWeak());
531 EXPECT_EQ(TIBase::getState(
id), PartiallyDeleted);
534 EXPECT_TRUE(destructorRan.
load());
535 EXPECT_EQ(TIBase::getState(
id), Deleted);
538TEST(IntrusiveSharedTest, destructor)
548 using enum TrackedState;
550 TIBase::ResetStatesGuard
const rsg{
true};
558 using enum TrackedState;
564 case PartiallyDeleted:
565 EXPECT_FALSE(partialDeleteRan.
exchange(
true) || destructorRan.
load());
569 EXPECT_FALSE(destructorRan.
exchange(
true));
574 case PartiallyDeletedStarted:
590 EXPECT_TRUE(destructorRan.
load() && !partialDeleteRan.
load());
593TEST(IntrusiveSharedTest, multithreaded_clear_mixed_variant)
600 using enum TrackedState;
601 TIBase::ResetStatesGuard
const rsg{
true};
606 int const s = destructionState.
load(std::memory_order_relaxed);
607 return {(s & 1) != 0, (s & 2) != 0};
609 auto setDestructorRan = [&] ->
void {
610 destructionState.
fetch_or(1, std::memory_order_acq_rel);
612 auto setPartialDeleteRan = [&] ->
void {
613 destructionState.
fetch_or(2, std::memory_order_acq_rel);
616 using enum TrackedState;
617 auto [destructorRan, partialDeleteRan] = getDestructorState();
623 case PartiallyDeleted:
624 EXPECT_FALSE(partialDeleteRan || destructorRan);
625 setPartialDeleteRan();
629 EXPECT_FALSE(destructorRan);
635 case PartiallyDeletedStarted:
645 auto const numToCreate = toCreateDist(eng);
647 for (
auto i = 0uz; i < numToCreate; ++i)
649 if (isStrongDist(eng))
660 constexpr auto kLoopIters = 2uz * 1024;
661 constexpr auto kNumThreads = 16uz;
663 Barrier loopStartSyncPoint{kNumThreads};
664 Barrier postCreateToCloneSyncPoint{kNumThreads};
665 Barrier postCreateVecOfPointersSyncPoint{kNumThreads};
670 for (
auto i = 0uz; i < kNumThreads; ++i)
678 auto const cloneAndDestroy = [&](
std::size_t threadId) {
679 for (
auto i = 0uz; i < kLoopIters; ++i)
694 auto [destructorRan, partialDeleteRan] = getDestructorState();
695 EXPECT_TRUE(i == 0 || destructorRan);
696 destructionState.
store(0, std::memory_order_release);
699 toClone.
resize(kNumThreads);
701 strong->tracingCallback = tracingCallback;
708 auto v = createVecOfPointers(toClone[threadId], engines[threadId]);
709 toClone[threadId].reset();
719 for (
auto i = 0uz; i < kNumThreads; ++i)
723 for (
auto i = 0uz; i < kNumThreads; ++i)
729TEST(IntrusiveSharedTest, multithreaded_clear_mixed_union)
741 using enum TrackedState;
743 TIBase::ResetStatesGuard
const rsg{
true};
748 int const s = destructionState.
load(std::memory_order_relaxed);
749 return {(s & 1) != 0, (s & 2) != 0};
751 auto setDestructorRan = [&] ->
void {
752 destructionState.
fetch_or(1, std::memory_order_acq_rel);
754 auto setPartialDeleteRan = [&] ->
void {
755 destructionState.
fetch_or(2, std::memory_order_acq_rel);
758 using enum TrackedState;
759 auto [destructorRan, partialDeleteRan] = getDestructorState();
765 case PartiallyDeleted:
766 EXPECT_FALSE(partialDeleteRan || destructorRan);
767 setPartialDeleteRan();
771 EXPECT_FALSE(destructorRan);
777 case PartiallyDeletedStarted:
782 auto createVecOfPointers =
783 [&](
auto const& toClone,
787 auto const numToCreate = toCreateDist(eng);
789 for (
auto i = 0uz; i < numToCreate; ++i)
793 constexpr auto kLoopIters = 2uz * 1024;
794 constexpr auto kFlipPointersLoopIters = 256uz;
795 constexpr auto kNumThreads = 16uz;
797 Barrier loopStartSyncPoint{kNumThreads};
798 Barrier postCreateToCloneSyncPoint{kNumThreads};
799 Barrier postCreateVecOfPointersSyncPoint{kNumThreads};
800 Barrier postFlipPointersLoopSyncPoint{kNumThreads};
805 for (
auto i = 0uz; i < kNumThreads; ++i)
814 auto const cloneAndDestroy = [&](
std::size_t threadId) {
815 for (
auto i = 0uz; i < kLoopIters; ++i)
829 auto [destructorRan, partialDeleteRan] = getDestructorState();
830 EXPECT_TRUE(i == 0 || destructorRan);
831 destructionState.
store(0, std::memory_order_release);
834 toClone.
resize(kNumThreads);
836 strong->tracingCallback = tracingCallback;
843 auto v = createVecOfPointers(toClone[threadId], engines[threadId]);
844 toClone[threadId].reset();
850 for (
auto f = 0uz; f < kFlipPointersLoopIters; ++f)
854 if (isStrongDist(engines[threadId]))
873 for (
auto i = 0uz; i < kNumThreads; ++i)
877 for (
auto i = 0uz; i < kNumThreads; ++i)
883TEST(IntrusiveSharedTest, multithreaded_locking_weak)
890 using enum TrackedState;
892 TIBase::ResetStatesGuard
const rsg{
true};
897 int const s = destructionState.
load(std::memory_order_relaxed);
898 return {(s & 1) != 0, (s & 2) != 0};
900 auto setDestructorRan = [&] ->
void {
901 destructionState.
fetch_or(1, std::memory_order_acq_rel);
903 auto setPartialDeleteRan = [&] ->
void {
904 destructionState.
fetch_or(2, std::memory_order_acq_rel);
907 using enum TrackedState;
908 auto [destructorRan, partialDeleteRan] = getDestructorState();
914 case PartiallyDeleted:
915 EXPECT_FALSE(partialDeleteRan || destructorRan);
916 setPartialDeleteRan();
920 EXPECT_FALSE(destructorRan);
926 case PartiallyDeletedStarted:
932 constexpr auto kLoopIters = 2uz * 1024;
933 constexpr auto kLockWeakLoopIters = 256uz;
934 constexpr auto kNumThreads = 16uz;
936 Barrier loopStartSyncPoint{kNumThreads};
937 Barrier postCreateToLockSyncPoint{kNumThreads};
938 Barrier postLockWeakLoopSyncPoint{kNumThreads};
943 auto const lockAndDestroy = [&](
std::size_t threadId) {
944 for (
auto i = 0uz; i < kLoopIters; ++i)
958 auto [destructorRan, partialDeleteRan] = getDestructorState();
959 EXPECT_TRUE(i == 0 || destructorRan);
960 destructionState.
store(0, std::memory_order_release);
963 toLock.
resize(kNumThreads);
965 strong->tracingCallback = tracingCallback;
975 for (
auto wi = 0uz; wi < kLockWeakLoopIters; ++wi)
978 auto const strong = weak.
lock();
985 toLock[threadId].reset();
990 for (
auto i = 0uz; i < kNumThreads; ++i)
994 for (
auto i = 0uz; i < kNumThreads; ++i)
T arrive_and_wait(T... args)
A shared intrusive pointer class that supports weak pointers.
A combination of a strong and a weak intrusive pointer stored in the space of a single pointer.
bool expired() const
Return true if there is a non-zero strong count.
void reset()
Set the pointer to null, decrement the appropriate ref count, and run the appropriate release action.
T * get() const
If this is a strong pointer, return the raw pointer.
bool convertToWeak()
If this is a strong pointer, attempt to convert it to a weak pointer.
bool isStrong() const
Return true is this represents a strong pointer.
std::size_t useCount() const
If this is a strong pointer, return the strong count.
bool isWeak() const
Return true is this represents a weak pointer.
A weak intrusive pointer class for the SharedIntrusive pointer class.
SharedIntrusive< T > lock() const
Get a strong pointer from the weak pointer, if possible.
bool expired() const
Return true if the strong count is zero.
void reset()
Set the pointer to null and decrement the weak count.
T emplace_back(T... args)
TEST(IntrusiveSharedTest, ref_counts_on_a_bare_object)
void partialDestructorFinished(T **o)
SharedIntrusive< TT > makeSharedIntrusive(Args &&... args)
Create a shared intrusive pointer.
std::condition_variable cv
std::size_t const initial