YT-21402: Adjust util's IntrusiveList to support more convenient use in lockfree algorithms (and farewell SimpleIntrusiveList)

Should be done
8a7cafa1f535df785680b70b488a2e4fbb46b1b0

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) {