Revert "YT-17689: Move TFreeList to library/cpp/yt/memory"

This reverts commit 617a1d07971366c19cdf278579ee9b1cbfa53db8, reversing
changes made to 27e0312d3842c4e5e3ea6b09611c8f6ff6938dd6.

4 files changed, 0 insertions, 329 deletions

diff --git a/library/cpp/yt/memory/free_list-inl.h b/library/cpp/yt/memory/free_list-inl.h
deleted file mode 100644
index d64fad8896..0000000000
--- a/library/cpp/yt/memory/free_list-inl.h
+++ /dev/null
@@ -1,222 +0,0 @@
-#ifndef FREE_LIST_INL_H_
-#error "Direct inclusion of this file is not allowed, include free_list.h"
-// For the sake of sane code completion.
-#include "free_list.h"
-#endif
-
-namespace NYT {
-
-////////////////////////////////////////////////////////////////////////////////
-
-namespace NDetail {
-
-template <class T1, class T2>
-Y_FORCE_INLINE bool CompareAndSet(
-    TAtomicUint128* atomic,
-    T1& expected1,
-    T2& expected2,
-    T1 new1,
-    T2 new2)
-{
-#if defined(__x86_64__)
-    bool success;
-    __asm__ __volatile__
-    (
-        "lock cmpxchg16b %1\n"
-        "setz %0"
-        : "=q"(success)
-        , "+m"(*atomic)
-        , "+a"(expected1)
-        , "+d"(expected2)
-        : "b"(new1)
-        , "c"(new2)
-        : "cc"
-    );
-    return success;
-#elif defined(__arm64__) || (defined(__aarch64__) && defined(RTE_ARM_FEATURE_ATOMICS))
-    register ui64 x0 __asm("x0") = (ui64)expected1;
-    register ui64 x1 __asm("x1") = (ui64)expected2;
-    register ui64 x2 __asm("x2") = (ui64)new1;
-    register ui64 x3 __asm("x3") = (ui64)new2;
-    ui64 old1 = (ui64)expected1;
-    ui64 old2 = (ui64)expected2;
-    asm volatile
-    (
-#if defined(RTE_CC_CLANG)
-        ".arch armv8-a+lse\n"
-#endif
-        "caspal %[old0], %[old1], %[upd0], %[upd1], [%[dst]]"
-        : [old0] "+r" (x0)
-        , [old1] "+r" (x1)
-        : [upd0] "r" (x2)
-        , [upd1] "r" (x3)
-        , [dst] "r" (atomic)
-        : "memory"
-    );
-    expected1 = (T1)x0;
-    expected2 = (T2)x1;
-    return x0 == old1 && x1 == old2;
-#elif defined(__aarch64__)
-    ui64 exp1 = reinterpret_cast<ui64>(expected1);
-    ui64 exp2 = reinterpret_cast<ui64>(expected2);
-    ui32 fail = 0;
-
-    do {
-        ui64 current1 = 0;
-        ui64 current2 = 0;
-        asm volatile (
-            "ldaxp %[cur1], %[cur2], [%[src]]"
-            : [cur1] "=r" (current1)
-            , [cur2] "=r" (current2)
-            : [src] "r" (atomic)
-            : "memory"
-        );
-
-        if (current1 != exp1 || current2 != exp2) {
-            expected1 = reinterpret_cast<T1>(current1);
-            expected2 = reinterpret_cast<T2>(current2);
-            return false;
-        }
-
-        asm volatile (
-            "stlxp %w[fail], %[new1], %[new2], [%[dst]]"
-            : [fail] "=&r" (fail)
-            : [new1] "r" (new1)
-            , [new2] "r" (new2)
-            , [dst] "r" (atomic)
-            : "memory"
-        );
-
-    } while (Y_UNLIKELY(fail));
-    return true;
-#else
-#    error Unsupported platform
-#endif
-}
-
-} // namespace NDetail
-
-////////////////////////////////////////////////////////////////////////////////
-
-template <class TItem>
-TFreeList<TItem>::THead::THead(TItem* pointer)
-    : Pointer(pointer)
-{ }
-
-template <class TItem>
-TFreeList<TItem>::TFreeList()
-    : Head_()
-{ }
-
-template <class TItem>
-TFreeList<TItem>::TFreeList(TFreeList<TItem>&& other)
-    : Head_(other.ExtractAll())
-{ }
-
-template <class TItem>
-TFreeList<TItem>::~TFreeList()
-{
-    YT_VERIFY(IsEmpty());
-}
-
-template <class TItem>
-template <class TPredicate>
-Y_NO_SANITIZE("thread")
-bool TFreeList<TItem>::PutIf(TItem* head, TItem* tail, TPredicate predicate)
-{
-    auto* current = Head_.Pointer.load(std::memory_order::relaxed);
-    auto popCount = Head_.PopCount.load(std::memory_order::relaxed);
-
-    while (predicate(current)) {
-        tail->Next.store(current);
-        if (NYT::NDetail::CompareAndSet(&AtomicHead_, current, popCount, head, popCount)) {
-            return true;
-        }
-    }
-
-    tail->Next.store(nullptr);
-
-    return false;
-}
-
-
-template <class TItem>
-Y_NO_SANITIZE("thread")
-void TFreeList<TItem>::Put(TItem* head, TItem* tail)
-{
-    auto* current = Head_.Pointer.load(std::memory_order::relaxed);
-    auto popCount = Head_.PopCount.load(std::memory_order::relaxed);
-
-    do {
-        tail->Next.store(current);
-    } while (!NYT::NDetail::CompareAndSet(&AtomicHead_, current, popCount, head, popCount));
-}
-
-template <class TItem>
-void TFreeList<TItem>::Put(TItem* item)
-{
-    Put(item, item);
-}
-
-template <class TItem>
-Y_NO_SANITIZE("thread")
-TItem* TFreeList<TItem>::Extract()
-{
-    auto* current = Head_.Pointer.load(std::memory_order::relaxed);
-    auto popCount = Head_.PopCount.load(std::memory_order::relaxed);
-
-    while (current) {
-        // If current node is already extracted by other thread
-        // there can be any writes at address &current->Next.
-        // The only guaranteed thing is that address is valid (memory is not freed).
-        auto next = current->Next.load(std::memory_order::acquire);
-        if (NYT::NDetail::CompareAndSet(&AtomicHead_, current, popCount, next, popCount + 1)) {
-            current->Next.store(nullptr, std::memory_order::release);
-            return current;
-        }
-    }
-
-    return nullptr;
-}
-
-template <class TItem>
-TItem* TFreeList<TItem>::ExtractAll()
-{
-    auto* current = Head_.Pointer.load(std::memory_order::relaxed);
-    auto popCount = Head_.PopCount.load(std::memory_order::relaxed);
-
-    while (current) {
-        if (NYT::NDetail::CompareAndSet<TItem*, size_t>(&AtomicHead_, current, popCount, nullptr, popCount + 1)) {
-            return current;
-        }
-    }
-
-    return nullptr;
-}
-
-template <class TItem>
-bool TFreeList<TItem>::IsEmpty() const
-{
-    return Head_.Pointer.load() == nullptr;
-}
-
-template <class TItem>
-void TFreeList<TItem>::Append(TFreeList<TItem>& other)
-{
-    auto* head = other.ExtractAll();
-
-    if (!head) {
-        return;
-    }
-
-    auto* tail = head;
-    while (tail->Next) {
-        tail = tail->Next;
-    }
-
-    Put(head, tail);
-}
-
-////////////////////////////////////////////////////////////////////////////////
-
-} // namespace NYT
diff --git a/library/cpp/yt/memory/free_list.h b/library/cpp/yt/memory/free_list.h
deleted file mode 100644
index 670b7d2cc4..0000000000
--- a/library/cpp/yt/memory/free_list.h
+++ /dev/null
@@ -1,78 +0,0 @@
-#pragma once
-
-#include "public.h"
-
-#include <util/system/compiler.h>
-
-#include <atomic>
-
-namespace NYT {
-
-////////////////////////////////////////////////////////////////////////////////
-
-template <class T>
-struct TFreeListItemBase
-{
-    std::atomic<T*> Next = nullptr;
-};
-
-// DCAS is supported in Clang with option -mcx16, is not supported in GCC. See following links.
-// https://gcc.gnu.org/bugzilla/show_bug.cgi?id=84522
-// https://gcc.gnu.org/bugzilla/show_bug.cgi?id=80878
-
-using TAtomicUint128 = volatile unsigned __int128  __attribute__((aligned(16)));
-
-template <class TItem>
-class TFreeList
-{
-private:
-    struct THead
-    {
-        std::atomic<TItem*> Pointer = {nullptr};
-        std::atomic<size_t> PopCount = 0;
-
-        THead() = default;
-
-        explicit THead(TItem* pointer);
-
-    };
-
-    union
-    {
-        THead Head_;
-        TAtomicUint128 AtomicHead_;
-    };
-
-    // Avoid false sharing.
-    char Padding[CacheLineSize - sizeof(TAtomicUint128)];
-
-public:
-    TFreeList();
-
-    TFreeList(TFreeList&& other);
-
-    ~TFreeList();
-
-    template <class TPredicate>
-    bool PutIf(TItem* head, TItem* tail, TPredicate predicate);
-
-    void Put(TItem* head, TItem* tail);
-
-    void Put(TItem* item);
-
-    TItem* Extract();
-
-    TItem* ExtractAll();
-
-    bool IsEmpty() const;
-
-    void Append(TFreeList& other);
-};
-
-////////////////////////////////////////////////////////////////////////////////
-
-} // namespace NYT
-
-#define FREE_LIST_INL_H_
-#include "free_list-inl.h"
-#undef FREE_LIST_INL_H_
diff --git a/library/cpp/yt/memory/public.h b/library/cpp/yt/memory/public.h
index f05a6b4569..fb1546dd59 100644
--- a/library/cpp/yt/memory/public.h
+++ b/library/cpp/yt/memory/public.h
@@ -6,9 +6,6 @@ namespace NYT {
 
 ////////////////////////////////////////////////////////////////////////////////
 
-// TODO(babenko): consider increasing to 128 due to cache line pairing in L2 prefetcher.
-constexpr size_t CacheLineSize = 64;
-
 class TChunkedMemoryPool;
 
 DECLARE_REFCOUNTED_STRUCT(IMemoryChunkProvider)
diff --git a/library/cpp/yt/memory/unittests/free_list_ut.cpp b/library/cpp/yt/memory/unittests/free_list_ut.cpp
deleted file mode 100644
index 307a5abb7c..0000000000
--- a/library/cpp/yt/memory/unittests/free_list_ut.cpp
+++ /dev/null
@@ -1,26 +0,0 @@
-#include <library/cpp/testing/gtest/gtest.h>
-
-#include <library/cpp/yt/memory/free_list.h>
-
-namespace NYT {
-namespace {
-
-////////////////////////////////////////////////////////////////////////////////
-
-TEST(TFreeListTest, CompareAndSet)
-{
-    TAtomicUint128 v = 0;
-    ui64 p1 = 0;
-    ui64 p2 = 0;
-    EXPECT_TRUE(NYT::NDetail::CompareAndSet(&v, p1, p2, ui64{13}, ui64{9}));
-    EXPECT_FALSE(NYT::NDetail::CompareAndSet(&v, p1, p2, ui64{100}, ui64{500}));
-    EXPECT_EQ(13u, p1);
-    EXPECT_EQ(9u, p2);
-    EXPECT_TRUE(NYT::NDetail::CompareAndSet(&v, p1, p2, ui64{100}, ui64{500}));
-    EXPECT_EQ(TAtomicUint128{500} << 64 | 100, v);
-}
-
-////////////////////////////////////////////////////////////////////////////////
-
-} // namespace
-} // namespace NYT