Fix TFreeList and its unittests for 32 bit platform

commit_hash:6d5cf8bea86a35efd558df2aaec98702dc514f1c

3 files changed, 85 insertions, 35 deletions

diff --git a/library/cpp/yt/memory/free_list-inl.h b/library/cpp/yt/memory/free_list-inl.h
index eb52a35c873..135eb5421b6 100644
--- a/library/cpp/yt/memory/free_list-inl.h
+++ b/library/cpp/yt/memory/free_list-inl.h
@@ -8,13 +8,16 @@ namespace NYT {
 
 ////////////////////////////////////////////////////////////////////////////////
 
-// DCAS is supported in Clang with option -mcx16, is not supported in GCC. See following links.
+namespace NDetail {
+
+#if defined(_64_)
+
+// DCAS is natively supported in Clang with -mcx16 and is not supported in GCC.
 // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=84522
 // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=80878
-
 template <class T1, class T2>
-Y_FORCE_INLINE bool CompareAndSet(
-    TAtomicUint128* atomic,
+Y_FORCE_INLINE bool CasFreeListPackedPair(
+    TFreeListPackedPair* atomic,
     T1& expected1,
     T2& expected2,
     T1 new1,
@@ -88,7 +91,6 @@ Y_FORCE_INLINE bool CompareAndSet(
             , [dst] "r" (atomic)
             : "memory"
         );
-
     } while (Y_UNLIKELY(fail));
     return true;
 #else
@@ -96,6 +98,36 @@ Y_FORCE_INLINE bool CompareAndSet(
 #endif
 }
 
+#elif defined(_32_)
+
+template <class T1, class T2>
+Y_FORCE_INLINE bool CasFreeListPackedPair(
+    TFreeListPackedPair* atomic,
+    T1& expected1,
+    T2& expected2,
+    T1 new1,
+    T2 new2)
+{
+    auto packedExpected =
+        static_cast<ui64>(reinterpret_cast<ui32>(expected1)) |
+        (static_cast<ui64>(reinterpret_cast<ui32>(expected2)) << 32);
+    auto packedNew =
+        static_cast<ui64>(reinterpret_cast<ui32>(new1)) |
+        (static_cast<ui64>(reinterpret_cast<ui32>(new2)) << 32);
+    if (atomic->compare_exchange_weak(packedExpected, packedNew)) {
+        return true;
+    }
+    expected1 = reinterpret_cast<T1>(static_cast<ui32>(packedExpected));
+    expected2 = reinterpret_cast<T2>(static_cast<ui32>(packedExpected >> 32));
+    return false;
+}
+
+#else
+    #error Unsupported platform
+#endif
+
+} // namespace NDetail
+
 ////////////////////////////////////////////////////////////////////////////////
 
 template <class TItem>
@@ -129,7 +161,7 @@ bool TFreeList<TItem>::PutIf(TItem* head, TItem* tail, TPredicate predicate)
 
     while (predicate(current)) {
         tail->Next.store(current, std::memory_order::release);
-        if (CompareAndSet(&AtomicHead_, current, epoch, head, epoch + 1)) {
+        if (NDetail::CasFreeListPackedPair(&PackedHead_, current, epoch, head, epoch + 1)) {
             return true;
         }
     }
@@ -139,7 +171,6 @@ bool TFreeList<TItem>::PutIf(TItem* head, TItem* tail, TPredicate predicate)
     return false;
 }
 
-
 template <class TItem>
 Y_NO_SANITIZE("thread")
 void TFreeList<TItem>::Put(TItem* head, TItem* tail)
@@ -149,7 +180,7 @@ void TFreeList<TItem>::Put(TItem* head, TItem* tail)
 
     do {
         tail->Next.store(current, std::memory_order::release);
-    } while (!CompareAndSet(&AtomicHead_, current, epoch, head, epoch + 1));
+    } while (!NDetail::CasFreeListPackedPair(&PackedHead_, current, epoch, head, epoch + 1));
 }
 
 template <class TItem>
@@ -170,7 +201,7 @@ TItem* TFreeList<TItem>::Extract()
         // 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 (CompareAndSet(&AtomicHead_, current, epoch, next, epoch + 1)) {
+        if (NDetail::CasFreeListPackedPair(&PackedHead_, current, epoch, next, epoch + 1)) {
             current->Next.store(nullptr, std::memory_order::release);
             return current;
         }
@@ -186,7 +217,7 @@ TItem* TFreeList<TItem>::ExtractAll()
     auto epoch = Head_.Epoch.load(std::memory_order::relaxed);
 
     while (current) {
-        if (CompareAndSet<TItem*, size_t>(&AtomicHead_, current, epoch, nullptr, epoch + 1)) {
+        if (NDetail::CasFreeListPackedPair<TItem*, TEpoch>(&PackedHead_, current, epoch, nullptr, epoch + 1)) {
             return current;
         }
     }
diff --git a/library/cpp/yt/memory/free_list.h b/library/cpp/yt/memory/free_list.h
index d11629f08d5..daf8bddfe29 100644
--- a/library/cpp/yt/memory/free_list.h
+++ b/library/cpp/yt/memory/free_list.h
@@ -1,6 +1,7 @@
 #pragma once
 
 #include "public.h"
+#include "tagged_ptr.h"
 
 #include <atomic>
 
@@ -8,59 +9,76 @@ namespace NYT {
 
 ////////////////////////////////////////////////////////////////////////////////
 
+namespace NDetail {
+
+#if defined(_64_)
+
+using TFreeListPackedPairComponent = ui64;
+using TFreeListPackedPair = volatile unsigned __int128  __attribute__((aligned(16)));
+
+#elif defined(_32_)
+
+using TFreeListPackedPairComponent = ui32;
+using TFreeListPackedPair = std::atomic<ui64>;
+
+#else
+    #error Unsupported platform
+#endif
+
+} // namespace NDetail
+
+////////////////////////////////////////////////////////////////////////////////
+
 template <class T>
 struct TFreeListItemBase
 {
     std::atomic<T*> Next = nullptr;
 };
 
-using TAtomicUint128 = volatile unsigned __int128  __attribute__((aligned(16)));
-
 template <class TItem>
 class TFreeList
 {
 private:
+    using TEpoch = NDetail::TFreeListPackedPairComponent;
+
     struct THead
     {
         std::atomic<TItem*> Pointer = nullptr;
-        std::atomic<size_t> Epoch = 0;
+        std::atomic<TEpoch> Epoch = 0;
 
         THead() = default;
 
         explicit THead(TItem* pointer);
-
     };
 
+    static_assert(sizeof(THead) == sizeof(NDetail::TFreeListPackedPair));
+
     union
     {
         THead Head_;
-        TAtomicUint128 AtomicHead_;
+        NDetail::TFreeListPackedPair PackedHead_;
     };
 
     // Avoid false sharing.
-    char Padding[CacheLineSize - sizeof(TAtomicUint128)];
+    [[maybe_unused]] char Padding_[CacheLineSize - sizeof(THead)];
 
 public:
     TFreeList();
-
     TFreeList(TFreeList&& other) noexcept;
 
     ~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);
+
+    bool IsEmpty() const;
 };
 
 ////////////////////////////////////////////////////////////////////////////////
diff --git a/library/cpp/yt/memory/unittests/free_list_ut.cpp b/library/cpp/yt/memory/unittests/free_list_ut.cpp
index 3d2ecf103ef..81f60b694fe 100644
--- a/library/cpp/yt/memory/unittests/free_list_ut.cpp
+++ b/library/cpp/yt/memory/unittests/free_list_ut.cpp
@@ -15,17 +15,19 @@ using namespace std::chrono_literals;
 
 ////////////////////////////////////////////////////////////////////////////////
 
-TEST(TFreeListTest, CompareAndSet)
+TEST(TFreeListDetailsTest, CasFreeListPackedPair)
 {
-    TAtomicUint128 v = 0;
-    ui64 p1 = 0;
-    ui64 p2 = 0;
-    EXPECT_TRUE(CompareAndSet(&v, p1, p2, ui64{13}, ui64{9}));
-    EXPECT_FALSE(CompareAndSet(&v, p1, p2, ui64{100}, ui64{500}));
-    EXPECT_EQ(13u, p1);
-    EXPECT_EQ(9u, p2);
-    EXPECT_TRUE(CompareAndSet(&v, p1, p2, ui64{100}, ui64{500}));
-    EXPECT_EQ(TAtomicUint128{500} << 64 | 100, v);
+    using P = NDetail::TFreeListPackedPair;
+    using C = NDetail::TFreeListPackedPairComponent;
+    P v = 0;
+    C p1 = 0;
+    C p2 = 0;
+    EXPECT_TRUE(NDetail::CasFreeListPackedPair(&v, p1, p2, C(13), C(9)));
+    EXPECT_FALSE(NDetail::CasFreeListPackedPair(&v, p1, p2, C(100), C(500)));
+    EXPECT_EQ(C(13), p1);
+    EXPECT_EQ(C(9), p2);
+    EXPECT_TRUE(NDetail::CasFreeListPackedPair(&v, p1, p2, C(100), C(500)));
+    EXPECT_EQ((P(500) << (sizeof(C) * 8)) | 100, v);
 }
 
 ////////////////////////////////////////////////////////////////////////////////
@@ -90,8 +92,7 @@ private:
     std::stack<size_t> AcquiredItemIndices_;
 };
 
-
-TEST_P(TFreeListStressTest, Stress)
+TEST_P(TFreeListStressTest, Do)
 {
     TTestItemSet::Reset();
     SetRandomSeed(0x424242);
@@ -145,7 +146,7 @@ TEST_P(TFreeListStressTest, Stress)
 }
 
 INSTANTIATE_TEST_SUITE_P(
-    TFreeListTest,
+    TFreeListStressTest,
     TFreeListStressTest,
     testing::Values(
         TTestConfig{4, 1, 15s},