diff options
author | arkady-e1ppa <arkady-e1ppa@yandex-team.com> | 2024-04-28 02:09:44 +0300 |
---|---|---|
committer | arkady-e1ppa <arkady-e1ppa@yandex-team.com> | 2024-04-28 02:18:13 +0300 |
commit | 2c75f008ecfca5cfe830f799d7fa3f48a9760ce1 (patch) | |
tree | d4ecd256b46a250a94bd14ed23bda546de110107 | |
parent | e476b37cb796475328cc77d0a217d688e072d27c (diff) | |
download | ydb-2c75f008ecfca5cfe830f799d7fa3f48a9760ce1.tar.gz |
YT-21402: Adjust util's IntrusiveList to support more convenient use in lockfree algorithms (and farewell SimpleIntrusiveList)
Should be done
8a7cafa1f535df785680b70b488a2e4fbb46b1b0
-rw-r--r-- | util/generic/intrlist.h | 33 | ||||
-rw-r--r-- | yt/yt/core/concurrency/fiber.cpp | 26 | ||||
-rw-r--r-- | yt/yt/core/concurrency/fiber.h | 10 | ||||
-rw-r--r-- | yt/yt/core/misc/intrusive_list-inl.h | 152 | ||||
-rw-r--r-- | yt/yt/core/misc/intrusive_list.h | 87 | ||||
-rw-r--r-- | yt/yt/core/misc/intrusive_mpsc_stack-inl.h | 18 | ||||
-rw-r--r-- | yt/yt/core/misc/intrusive_mpsc_stack.h | 8 | ||||
-rw-r--r-- | yt/yt/library/backtrace_introspector/introspect.cpp | 4 |
8 files changed, 65 insertions, 273 deletions
diff --git a/util/generic/intrlist.h b/util/generic/intrlist.h index b5d3f2051b..2982e3a281 100644 --- a/util/generic/intrlist.h +++ b/util/generic/intrlist.h @@ -39,7 +39,7 @@ public: Prev_->SetNext(Next_); Next_->SetPrev(Prev_); - SetEnd(); + ResetItem(); } inline void LinkBefore(TListItem* before) noexcept { @@ -87,11 +87,6 @@ public: } public: - inline void SetEnd() noexcept { - Prev_ = this; - Next_ = Prev_; - } - inline void SetNext(TListItem* item) noexcept { Next_ = item; } @@ -109,6 +104,28 @@ public: return static_cast<const T*>(this); } +public: + // NB(arkady-e1ppa): These methods are used to implement + // intrusive lock-free algorithms which want to natively + // interact with TIntrusiveList. + // Assume that if you've used MutableNext/MutablePrev + // methods, you are not safe to use anything but + // MutableNext/MutablePrev/ResetItem methods until + // you call a ResetItem method. + + inline TListItem*& MutableNext() noexcept { + return Next_; + } + + inline TListItem*& MutablePrev() noexcept { + return Prev_; + } + + inline void ResetItem() noexcept { + Next_ = this; + Prev_ = Next_; + } + private: inline TIntrusiveListItem(const TIntrusiveListItem&) = delete; inline TIntrusiveListItem& operator=(const TIntrusiveListItem&) = delete; @@ -508,6 +525,10 @@ public: Cut(list.Begin(), list.End(), End()); } + inline void Append(TIntrusiveList&& list) noexcept { + Append(list); + } + inline static void Cut(TIterator begin, TIterator end, TIterator pasteBefore) noexcept { if (begin == end) { return; diff --git a/yt/yt/core/concurrency/fiber.cpp b/yt/yt/core/concurrency/fiber.cpp index 9bdb6fb35c..b0ea1b173d 100644 --- a/yt/yt/core/concurrency/fiber.cpp +++ b/yt/yt/core/concurrency/fiber.cpp @@ -172,8 +172,12 @@ private: auto toUnregister = UnregisterQueue_.PopAll(); - while (auto fiber = toUnregister.PopBack()) { - fiber->UnregisterAndDelete(); + // NB: util intrusive list does not return + // nullptr in case of empty! + // We have to check ourselves that + // PopBack return is a valid one. + while (!toUnregister.Empty()) { + toUnregister.PopBack()->UnregisterAndDelete(); } // NB: Around this line guard is released. We do not properly double check @@ -187,18 +191,20 @@ private: { Cerr << "Debug print begin\n"; Cerr << "---------------------------------------------------------------" << '\n'; - for (auto* iter = Fibers_.Begin(); iter != Fibers_.End(); iter = iter->Next) { - auto* fiber = static_cast<TFiber*>(iter); - auto* regNode = static_cast<TIntrusiveNode<TFiber, NDetail::TFiberRegisterTag>*>(fiber); - auto* delNode = static_cast<TIntrusiveNode<TFiber, NDetail::TFiberUnregisterTag>*>(fiber); + for (auto& iter : Fibers_) { + auto* ptr = &iter; + auto* fiber = static_cast<TFiber*>(ptr); + auto* regNode = static_cast<TIntrusiveListItem<TFiber, NDetail::TFiberRegisterTag>*>(fiber); + auto* delNode = static_cast<TIntrusiveListItem<TFiber, NDetail::TFiberUnregisterTag>*>(fiber); - Cerr << Format("Fiber node at %v. Next is %v, Prev is %v", iter, iter->Next, iter->Prev) << '\n'; + Cerr << Format("Fiber node at %v", iter) << '\n'; Cerr << Format("Fiber address after cast is %v", fiber) << '\n'; - Cerr << Format("Fiber registration queue status: Next: %v, Prev: %v", regNode->Next, regNode->Prev) << '\n'; + Cerr << Format("Fiber registration queue status: Next: %v, Prev: %v", regNode->Next(), regNode->Prev()) << '\n'; // NB: Reading deletion queue is data race. Don't do this under tsan. - Cerr << Format("Fiber deletion queue status: Next: %v, Prev: %v", delNode->Next, delNode->Prev) << '\n'; + Cerr << Format("Fiber deletion queue status: Next: %v, Prev: %v", delNode->Next(), delNode->Prev()) << '\n'; Cerr << "---------------------------------------------------------------" << '\n'; } + Cerr << "Debug print end\n"; } }; @@ -349,7 +355,7 @@ void TFiber::ReadFibers(TFunctionView<void(TFiberList&)> callback) void TFiber::UnregisterAndDelete() noexcept { - YT_VERIFY(!static_cast<TUnregisterBase*>(this)->IsLinked()); + YT_VERIFY(static_cast<TUnregisterBase*>(this)->Empty()); static_cast<TRegisterBase*>(this)->Unlink(); delete this; diff --git a/yt/yt/core/concurrency/fiber.h b/yt/yt/core/concurrency/fiber.h index e08d72601c..d8aade79e1 100644 --- a/yt/yt/core/concurrency/fiber.h +++ b/yt/yt/core/concurrency/fiber.h @@ -39,15 +39,15 @@ struct TFiberUnregisterTag // Do not change inheritence order or layout. // Some offsets are hardcoded at devtools/gdb/yt_fibers_printer.py. class TFiber - : public TIntrusiveNode<TFiber, NDetail::TFiberRegisterTag> - , public TIntrusiveNode<TFiber, NDetail::TFiberUnregisterTag> + : public TIntrusiveListItem<TFiber, NDetail::TFiberRegisterTag> + , public TIntrusiveListItem<TFiber, NDetail::TFiberUnregisterTag> , public ITrampoLine { - using TRegisterBase = TIntrusiveNode<TFiber, NDetail::TFiberRegisterTag>; - using TUnregisterBase = TIntrusiveNode<TFiber, NDetail::TFiberUnregisterTag>; + using TRegisterBase = TIntrusiveListItem<TFiber, NDetail::TFiberRegisterTag>; + using TUnregisterBase = TIntrusiveListItem<TFiber, NDetail::TFiberUnregisterTag>; public: - using TFiberList = TSimpleIntrusiveList<TFiber, NDetail::TFiberRegisterTag>; + using TFiberList = TIntrusiveList<TFiber, NDetail::TFiberRegisterTag>; static TFiber* CreateFiber(EExecutionStackKind stackKind = EExecutionStackKind::Small); diff --git a/yt/yt/core/misc/intrusive_list-inl.h b/yt/yt/core/misc/intrusive_list-inl.h deleted file mode 100644 index 9bf00d4eb1..0000000000 --- a/yt/yt/core/misc/intrusive_list-inl.h +++ /dev/null @@ -1,152 +0,0 @@ -#ifndef INTRUSIVE_LIST_INL_H_ -#error "Direct inclusion of this file is not allowed, include intrusive_list.h" -// For the sake of sane code completion. -#include "intrusive_list.h" -#endif - -#include <concepts> - -namespace NYT { - -//////////////////////////////////////////////////////////////////////////////// - -template <class T, class Tag> -void TIntrusiveNode<T, Tag>::Unlink() noexcept -{ - if (Next) { - Next->Prev = Prev; - } - - if (Prev) { - Prev->Next = Next; - } - - Prev = Next = nullptr; -} - -template <class T, class Tag> -void TIntrusiveNode<T, Tag>::LinkBefore(TIntrusiveNode* next) noexcept -{ - YT_VERIFY(!IsLinked()); - - Prev = next->Prev; - Prev->Next = this; - Next = next; - next->Prev = this; -} - -template <class T, class Tag> -bool TIntrusiveNode<T, Tag>::IsLinked() const noexcept -{ - return (Next != nullptr) || (Prev != nullptr); -} - -template <class T, class Tag> -T* TIntrusiveNode<T, Tag>::AsItem() noexcept -{ - return static_cast<T*>(this); -} - -//////////////////////////////////////////////////////////////////////////////// - -template <class T, class Tag> -TSimpleIntrusiveList<T, Tag>::TSimpleIntrusiveList() noexcept -{ - InitializeEmpty(); -} - -template <class T, class Tag> -TSimpleIntrusiveList<T, Tag>::TSimpleIntrusiveList(TList&& other) noexcept -{ - InitializeEmpty(); - Append(std::move(other)); -} - -template <class T, class Tag> -void TSimpleIntrusiveList<T, Tag>::PushBack(TNode* node) noexcept -{ - node->LinkBefore(&Head_); -} - -template <class T, class Tag> -void TSimpleIntrusiveList<T, Tag>::PushFront(TNode* node) noexcept -{ - node->LinkBefore(Head_.Next); -} - -template <class T, class Tag> -T*TSimpleIntrusiveList<T, Tag>::PopBack() noexcept -{ - if (IsEmpty()) { - return nullptr; - } - - TNode* back = Head_.Prev; - back->Unlink(); - return back->AsItem(); -} - -template <class T, class Tag> -T* TSimpleIntrusiveList<T, Tag>::PopFront() noexcept -{ - if (IsEmpty()) { - return nullptr; - } - - TNode* front = Head_.Next; - front->Unlink(); - return front->AsItem(); -} - -template <class T, class Tag> -void TSimpleIntrusiveList<T, Tag>::Append(TList&& other) noexcept -{ - if (other.IsEmpty()) { - return; - } - - auto* other_front = other.Head_.Next; - auto* current_back = Head_.Prev; - current_back->Next = other_front; - other_front->Prev = current_back; - - auto* other_back = other.Head_.Prev; - other_back->Next = &Head_; - Head_.Prev = other_back; - - other.InitializeEmpty(); -} - -template <class T, class Tag> -bool TSimpleIntrusiveList<T, Tag>::IsEmpty() const noexcept -{ - return Head_.Next == &Head_; -} - -template <class T, class Tag> -TIntrusiveNode<T, Tag>* TSimpleIntrusiveList<T, Tag>::Begin() -{ - return Head_.Next; -} - -template <class T, class Tag> -TIntrusiveNode<T, Tag>* TSimpleIntrusiveList<T, Tag>::End() -{ - return &Head_; -} - -template <class T, class Tag> -TSimpleIntrusiveList<T, Tag>::~TSimpleIntrusiveList() -{ - YT_VERIFY(IsEmpty()); -} - -template <class T, class Tag> -void TSimpleIntrusiveList<T, Tag>::InitializeEmpty() -{ - Head_.Next = Head_.Prev = &Head_; -} - -//////////////////////////////////////////////////////////////////////////////// - -} // namespace NYT diff --git a/yt/yt/core/misc/intrusive_list.h b/yt/yt/core/misc/intrusive_list.h deleted file mode 100644 index 208e5fea18..0000000000 --- a/yt/yt/core/misc/intrusive_list.h +++ /dev/null @@ -1,87 +0,0 @@ -#pragma once - -#include <cstdlib> - -namespace NYT { - -//////////////////////////////////////////////////////////////////////////////// - -struct TIntrusiveNodeDefaultTag -{ }; - -//////////////////////////////////////////////////////////////////////////////// - -// NB1: util/intrlist.h inits pointers differently -// and also doesn't provide a way to directly modify -// Next/Prev making it unusable in lockfree. -// NB2: yt/containers/intrusive_linked_list.h doesn't provide tag -// and gives quite a bit of overhead in the list (ItemToNode field, extra pointer -// and size field). It would be a bit more annoying to hardcode in introspection. -// TODO(arkady-e1ppa): Change util/intrlist.h to support lf algos and use it one day? -template <class T, class Tag = TIntrusiveNodeDefaultTag> -class TIntrusiveNode -{ -public: - TIntrusiveNode* Next = nullptr; - TIntrusiveNode* Prev = nullptr; - - TIntrusiveNode() = default; - - TIntrusiveNode(const TIntrusiveNode& other) = delete; - TIntrusiveNode& operator=(const TIntrusiveNode& other) = delete; - - void Unlink() noexcept; - - void LinkBefore(TIntrusiveNode* next) noexcept; - - bool IsLinked() const noexcept; - - T* AsItem() noexcept; -}; - -//////////////////////////////////////////////////////////////////////////////// - -template <class T, class Tag = TIntrusiveNodeDefaultTag> -class TSimpleIntrusiveList -{ - using TNode = TIntrusiveNode<T, Tag>; - using TList = TSimpleIntrusiveList<T, Tag>; - -public: - TSimpleIntrusiveList() noexcept; - TSimpleIntrusiveList(TSimpleIntrusiveList&& other) noexcept; - - TSimpleIntrusiveList(const TSimpleIntrusiveList& other) = delete; - TSimpleIntrusiveList& operator=(const TSimpleIntrusiveList& other) = delete; - TSimpleIntrusiveList& operator=(TSimpleIntrusiveList&& other) = delete; - - ~TSimpleIntrusiveList(); - - void PushBack(TNode* node) noexcept; - void PushFront(TNode* node) noexcept; - - T* PopBack() noexcept; - T* PopFront() noexcept; - - void Append(TList&& other) noexcept; - - bool IsEmpty() const noexcept; - - TNode* Begin(); - - TNode* End(); - -private: - // Sentinel node. - TNode Head_; - - void InitializeEmpty(); -}; - -//////////////////////////////////////////////////////////////////////////////// - -} // namespace NYT - -#define INTRUSIVE_LIST_INL_H_ -#include "intrusive_list-inl.h" -#undef INTRUSIVE_LIST_INL_H_ diff --git a/yt/yt/core/misc/intrusive_mpsc_stack-inl.h b/yt/yt/core/misc/intrusive_mpsc_stack-inl.h index dcd5682784..f294557942 100644 --- a/yt/yt/core/misc/intrusive_mpsc_stack-inl.h +++ b/yt/yt/core/misc/intrusive_mpsc_stack-inl.h @@ -13,17 +13,19 @@ namespace NYT { template <class T, class Tag> TIntrusiveMPSCStack<T, Tag>::TIntrusiveMPSCStack() noexcept { - static_assert(std::derived_from<T, TIntrusiveNode<T, Tag>>, "Class must inherit from CRTP-base TIntrusiveNode"); + static_assert(std::derived_from<T, TIntrusiveListItem<T, Tag>>, "Class must inherit from CRTP-base TIntrusiveListItem"); } template <class T, class Tag> void TIntrusiveMPSCStack<T, Tag>::Push(TNode* item) noexcept { + // Past this line item is not a valid instance of TInstrusiveListItem. + // NB: This saves up extra CAS in case of non-empty stack. - item->Next = Head_.load(std::memory_order::relaxed); + item->MutableNext() = Head_.load(std::memory_order::relaxed); while (!Head_.compare_exchange_weak( - item->Next, + item->MutableNext(), item, std::memory_order::release, std::memory_order::relaxed)) @@ -31,16 +33,18 @@ void TIntrusiveMPSCStack<T, Tag>::Push(TNode* item) noexcept } template <class T, class Tag> -TSimpleIntrusiveList<T, Tag> TIntrusiveMPSCStack<T, Tag>::PopAll() noexcept +TIntrusiveList<T, Tag> TIntrusiveMPSCStack<T, Tag>::PopAll() noexcept { TNode* head = Head_.exchange(nullptr, std::memory_order::acquire); - TSimpleIntrusiveList<T, Tag> list; + TIntrusiveList<T, Tag> list; while (head) { auto tmp = head; - head = head->Next; - tmp->Next = nullptr; + head = head->Next(); + + // From this line tmp is a valid instance of TIntrusiveListItem. + tmp->ResetItem(); list.PushFront(tmp); } diff --git a/yt/yt/core/misc/intrusive_mpsc_stack.h b/yt/yt/core/misc/intrusive_mpsc_stack.h index 80d460553e..0b54e13262 100644 --- a/yt/yt/core/misc/intrusive_mpsc_stack.h +++ b/yt/yt/core/misc/intrusive_mpsc_stack.h @@ -1,6 +1,6 @@ #pragma once -#include "intrusive_list.h" +#include <util/generic/intrlist.h> #include <atomic> @@ -8,17 +8,17 @@ namespace NYT { //////////////////////////////////////////////////////////////////////////////// -template <class T, class Tag = TIntrusiveNodeDefaultTag> +template <class T, class Tag = TIntrusiveListDefaultTag> class TIntrusiveMPSCStack { - using TNode = TIntrusiveNode<T, Tag>; + using TNode = TIntrusiveListItem<T, Tag>; public: TIntrusiveMPSCStack() noexcept; void Push(TNode* item) noexcept; - TSimpleIntrusiveList<T, Tag> PopAll() noexcept; + TIntrusiveList<T, Tag> PopAll() noexcept; private: std::atomic<TNode*> Head_ = nullptr; diff --git a/yt/yt/library/backtrace_introspector/introspect.cpp b/yt/yt/library/backtrace_introspector/introspect.cpp index 38e146ab08..6b5e008106 100644 --- a/yt/yt/library/backtrace_introspector/introspect.cpp +++ b/yt/yt/library/backtrace_introspector/introspect.cpp @@ -47,8 +47,8 @@ std::vector<TFiberIntrospectionInfo> IntrospectFibers() THashMap<TFiberId, EFiberState> fiberStates; auto introspectionAction = [&] (NYT::NConcurrency::TFiber::TFiberList& fibers) { - for (auto* iter = fibers.Begin(); iter != fibers.End(); iter = iter->Next) { - auto* fiber = iter->AsItem(); + for (auto& fiberRef : fibers) { + auto* fiber = &fiberRef; auto fiberId = fiber->GetFiberId(); if (fiberId == InvalidFiberId) { |