[scudo] Add ConditionVariable in SizeClassAllocator64

[Chia-hungDuan]

Summary

This may improve the waiting of Region->MMLock while trying to refill
the freelist. Instead of always waiting on the completion of
populateFreeListAndPopBatch() or releaseToOSMaybe(), pushBlocks()
also refills the freelist. This increases the chance of earlier return
from popBatches().

The support of condition variable hasn't been done for all platforms.
Therefore, add another popBatchWithCV() and it can be configured in
the allocator configuration by setting Primary::UseConditionVariable
and the desired ConditionVariableT.

[Chia-hungDuan]

Minor build fix

[Chia-hungDuan]

1. Fix potential ABA problem
2. Switch to detect the condition variable config so that the exisiting custom config doesn't need to add new parameters
3. Add condition variable test

[cferris]

Just a few comment nits.

compiler-rt/lib/scudo/standalone/primary64.h

158

from the wrong

258

to call

902

populating the freelist.

[cferris]

Looks good to me, but it's good to wait for Hans to take one last look.

[hboehm]

compiler-rt/lib/scudo/standalone/condition_variable.h

34–35

Is it possible to do something more like sched_yield here? Or there isn't a portable call along these lines. This clearly breaks completely if the waiting thread can't be preempted, e.g. because it has a higher real-time priority that the thread for which it's waiting, and there is a single hardware thread. I don't know if that matters here.

compiler-rt/lib/scudo/standalone/condition_variable_linux.cpp

26

It appears to me that all updates to Counter are lock-protected. So a non-atomic add with separate loads and stores should be fine. Since the only concurrent access is the futex read, I would expect this to have a release or relaxed store, and a relaxed load.

31

It seems to me that this makes the second notification in a row, without intervening waits cheap. But the third one will again perform a system call, even without an intervening wait. Intended? Do you want separate counters for notifications and waits?

[Chia-hungDuan]

Address review comments

compiler-rt/lib/scudo/standalone/condition_variable.h

34–35

So far we don't have a portable version here.

This implementation is supposed to be only used in the tests only. The busy-wait here is supposed to be something like sleep or yield hint. The reason we have the busy-wait is to simulate the same idea of waiting in usual condition variable implementation. It only waits for a short time and then wait on the mutex again.

Or do you think we can remove the busy-wait instead?

compiler-rt/lib/scudo/standalone/condition_variable_linux.cpp

31

Sorry I may miss something here. I think the notify and wait are put in a total order. LastNotifyAll will always record the last notify. We only call the system call to wake up waiters when the difference between the Counter and LastNotifyAll greater than 1, i.e., there are waiters.

Could you share more details about in what case we may have redundant notify calls?

compiler-rt/lib/scudo/standalone/CMakeLists.txt

 
 set(SCUDO_HEADERS
   allocator_common.h
   allocator_config.h
   atomic_helpers.h
   bytemap.h
   checksum.h
   chunk.h
+  condition_variable.h
+  condition_variable_base.h
+  condition_variable_linux.h
   combined.h
   common.h
   flags_parser.h
   flags.h
   fuchsia.h
   internal_defs.h
   linux.h
   list.h
set(SCUDO_HEADERS
   wrappers_c.h
 
   include/scudo/interface.h
   )
 
 set(SCUDO_SOURCES
   checksum.cpp
   common.cpp
+  condition_variable_linux.cpp
   crc32_hw.cpp
   flags_parser.cpp
   flags.cpp
   fuchsia.cpp
   linux.cpp
   mem_map.cpp
   mem_map_fuchsia.cpp
   mem_map_linux.cpp

compiler-rt/lib/scudo/standalone/allocator_config.h

 //===-- allocator_config.h --------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef SCUDO_ALLOCATOR_CONFIG_H_
 #define SCUDO_ALLOCATOR_CONFIG_H_
 
 #include "combined.h"
 #include "common.h"
+#include "condition_variable.h"
 #include "flags.h"
 #include "primary32.h"
 #include "primary64.h"
 #include "secondary.h"
 #include "size_class_map.h"
 #include "tsd_exclusive.h"
 #include "tsd_shared.h"
 

 //
 //     // Call map for user memory with at least this size. Only used with
 //     // primary64.
 //     static const uptr MapSizeIncrement = 1UL << 18;
 //
 //     // Defines the minimal & maximal release interval that can be set.
 //     static const s32 MinReleaseToOsIntervalMs = INT32_MIN;
 //     static const s32 MaxReleaseToOsIntervalMs = INT32_MAX;
+//
+//     // Use condition variable to shorten the waiting time of refillment of
+//     // freelist. Note that this depends on the implementation of condition
+//     // variable on each platform and the performance may vary so that it
+//     // doesn't guarantee a performance benefit.
+//     // Note that both variables have to be defined to enable it.
+//     static const bool UseConditionVariable = true;
+//     using ConditionVariableT = ConditionVariableLinux;
 //   };
 //   // Defines the type of Primary allocator to use.
 //   template <typename Config> using PrimaryT = SizeClassAllocator64<Config>;
 //
 //   // Defines the type of cache used by the Secondary. Some additional
 //   // configuration entries can be necessary depending on the Cache.
 //   struct Secondary {
 //     struct Cache {

compiler-rt/lib/scudo/standalone/condition_variable.h

+//===-- condition_variable.h ------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef SCUDO_CONDITION_VARIABLE_H_
+#define SCUDO_CONDITION_VARIABLE_H_
+
+#include "condition_variable_base.h"
+
+#include "common.h"
+#include "platform.h"
+
+#include "condition_variable_linux.h"
+
+namespace scudo {
+
+// A default implementation of default condition variable. It doesn't do a real
+// `wait`, instead it spins a short amount of time only.
+class ConditionVariableDummy
+    : public ConditionVariableBase<ConditionVariableDummy> {
+public:
+  void notifyAllImpl(UNUSED HybridMutex &M) REQUIRES(M) {}
+
+  void waitImpl(UNUSED HybridMutex &M) REQUIRES(M) {
+    M.unlock();
+
+    constexpr u32 SpinTimes = 64;
+    volatile u32 V = 0;
+    for (u32 I = 0; I < SpinTimes; ++I) {
+      u32 Tmp = V + 1;
+      V = Tmp;
+    }
+
+    M.lock();
+  }
+};
+
+template <typename Config, typename = const bool>
+struct ConditionVariableState {
+  static constexpr bool enabled() { return false; }
+  // This is only used for compilation purpose so that we won't end up having
+  // many conditional compilations. If you want to use `ConditionVariableDummy`,
+  // define `ConditionVariableT` in your allocator configuration. See
+  // allocator_config.h for more details.
+  using ConditionVariableT = ConditionVariableDummy;
+};
+
+template <typename Config>
+struct ConditionVariableState<Config, decltype(Config::UseConditionVariable)> {
+  static constexpr bool enabled() { return true; }
+  using ConditionVariableT = typename Config::ConditionVariableT;
+};
+
+} // namespace scudo
+
+#endif // SCUDO_CONDITION_VARIABLE_H_

compiler-rt/lib/scudo/standalone/condition_variable_base.h

+//===-- condition_variable_base.h -------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef SCUDO_CONDITION_VARIABLE_BASE_H_
+#define SCUDO_CONDITION_VARIABLE_BASE_H_
+
+#include "mutex.h"
+#include "thread_annotations.h"
+
+namespace scudo {
+
+template <typename Derived> class ConditionVariableBase {
+public:
+  constexpr ConditionVariableBase() = default;
+
+  void bindTestOnly(HybridMutex &Mutex) {
+#if SCUDO_DEBUG
+    boundMutex = &Mutex;
+#else
+    (void)Mutex;
+#endif
+  }
+
+  void notifyAll(HybridMutex &M) REQUIRES(M) {
+#if SCUDO_DEBUG
+    CHECK_EQ(&M, boundMutex);
+#endif
+    getDerived()->notifyAllImpl(M);
+  }
+
+  void wait(HybridMutex &M) REQUIRES(M) {
+#if SCUDO_DEBUG
+    CHECK_EQ(&M, boundMutex);
+#endif
+    getDerived()->waitImpl(M);
+  }
+
+protected:
+  Derived *getDerived() { return static_cast<Derived *>(this); }
+
+#if SCUDO_DEBUG
+  // Because thread-safety analysis doesn't support pointer aliasing, we are not
+  // able to mark the proper annotations without false positive. Instead, we
+  // pass the lock and do the same-lock check separately.
+  HybridMutex *boundMutex = nullptr;
+#endif
+};
+
+} // namespace scudo
+
+#endif // SCUDO_CONDITION_VARIABLE_BASE_H_

compiler-rt/lib/scudo/standalone/condition_variable_linux.h

+//===-- condition_variable_linux.h ------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef SCUDO_CONDITION_VARIABLE_LINUX_H_
+#define SCUDO_CONDITION_VARIABLE_LINUX_H_
+
+#include "platform.h"
+
+#if SCUDO_LINUX
+
+#include "atomic_helpers.h"
+#include "condition_variable_base.h"
+#include "thread_annotations.h"
+
+namespace scudo {
+
+class ConditionVariableLinux
+    : public ConditionVariableBase<ConditionVariableLinux> {
+public:
+  void notifyAllImpl(HybridMutex &M) REQUIRES(M);
+
+  void waitImpl(HybridMutex &M) REQUIRES(M);
+
+private:
+  u32 LastNotifyAll = 0;
+  atomic_u32 Counter = {};
+};
+
+} // namespace scudo
+
+#endif // SCUDO_LINUX
+
+#endif // SCUDO_CONDITION_VARIABLE_LINUX_H_

compiler-rt/lib/scudo/standalone/condition_variable_linux.cpp

+//===-- condition_variable_linux.cpp ----------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "platform.h"
+
+#if SCUDO_LINUX
+
+#include "condition_variable_linux.h"
+
+#include "atomic_helpers.h"
+
+#include <limits.h>
+#include <linux/futex.h>
+#include <sys/syscall.h>
+#include <unistd.h>
+
+namespace scudo {
+
+void ConditionVariableLinux::notifyAllImpl(UNUSED HybridMutex &M) {
+  const u32 V = atomic_load_relaxed(&Counter);
+  atomic_store_relaxed(&Counter, V + 1);
+
+  // TODO(chiahungduan): Move the waiters from the futex waiting queue
+  // `Counter` to futex waiting queue `M` so that the awoken threads won't be
+  // blocked again due to locked `M` by current thread.
+  if (LastNotifyAll != V) {
+    syscall(SYS_futex, reinterpret_cast<uptr>(&Counter), FUTEX_WAKE_PRIVATE,
+            INT_MAX, nullptr, nullptr, 0);
+  }
+
+  LastNotifyAll = V + 1;
+}
+
+void ConditionVariableLinux::waitImpl(HybridMutex &M) {
+  const u32 V = atomic_load_relaxed(&Counter) + 1;
+  atomic_store_relaxed(&Counter, V);
+
+  // TODO: Use ScopedUnlock when it's supported.
+  M.unlock();
+  syscall(SYS_futex, reinterpret_cast<uptr>(&Counter), FUTEX_WAIT_PRIVATE, V,
+          nullptr, nullptr, 0);
+  M.lock();
+}
+
+} // namespace scudo
+
+#endif // SCUDO_LINUX

compiler-rt/lib/scudo/standalone/primary64.h

 #include "mem_map.h"
 #include "memtag.h"
 #include "options.h"
 #include "release.h"
 #include "stats.h"
 #include "string_utils.h"
 #include "thread_annotations.h"
 
+#include "condition_variable.h"
+
 namespace scudo {
 
 // SizeClassAllocator64 is an allocator tuned for 64-bit address space.
 //
 // It starts by reserving NumClasses * 2^RegionSizeLog bytes, equally divided in
 // Regions, specific to each size class. Note that the base of that mapping is
 // random (based to the platform specific map() capabilities). If
 // PrimaryEnableRandomOffset is set, each Region actually starts at a random

 //
 // The memory used by this allocator is never unmapped, but can be partially
 // released if the platform allows for it.
 
 template <typename Config> class SizeClassAllocator64 {
 public:
   typedef typename Config::Primary::CompactPtrT CompactPtrT;
   typedef typename Config::Primary::SizeClassMap SizeClassMap;
+  typedef typename ConditionVariableState<
+      typename Config::Primary>::ConditionVariableT ConditionVariableT;
   static const uptr CompactPtrScale = Config::Primary::CompactPtrScale;
   static const uptr RegionSizeLog = Config::Primary::RegionSizeLog;
   static const uptr GroupSizeLog = Config::Primary::GroupSizeLog;
   static_assert(RegionSizeLog >= GroupSizeLog,
                 "Group size shouldn't be greater than the region size");
   static const uptr GroupScale = GroupSizeLog - CompactPtrScale;
   typedef SizeClassAllocator64<Config> ThisT;
   typedef SizeClassAllocatorLocalCache<ThisT> CacheT;
   typedef TransferBatch<ThisT> TransferBatchT;
   typedef BatchGroup<ThisT> BatchGroupT;
 
   static_assert(sizeof(BatchGroupT) <= sizeof(TransferBatchT),
                 "BatchGroupT uses the same class size as TransferBatchT");
 
   static uptr getSizeByClassId(uptr ClassId) {
     return (ClassId == SizeClassMap::BatchClassId)
                ? roundUp(sizeof(TransferBatchT), 1U << CompactPtrScale)
                : SizeClassMap::getSizeByClassId(ClassId);
   }
 
   static bool canAllocate(uptr Size) { return Size <= SizeClassMap::MaxSize; }
 
+  static bool conditionVariableEnabled() {
+    return ConditionVariableState<typename Config::Primary>::enabled();
+  }
+
   void init(s32 ReleaseToOsInterval) NO_THREAD_SAFETY_ANALYSIS {
     DCHECK(isAligned(reinterpret_cast<uptr>(this), alignof(ThisT)));
 
     const uptr PageSize = getPageSizeCached();
     const uptr GroupSize = (1UL << GroupSizeLog);
     const uptr PagesInGroup = GroupSize / PageSize;
     const uptr MinSizeClass = getSizeByClassId(1);
     // When trying to release pages back to memory, visiting smaller size
void init(s32 ReleaseToOsInterval) NO_THREAD_SAFETY_ANALYSIS {
 
     u32 Seed;
     const u64 Time = getMonotonicTimeFast();
     if (!getRandom(reinterpret_cast<void *>(&Seed), sizeof(Seed)))
       Seed = static_cast<u32>(Time ^ (PrimaryBase >> 12));
 
     for (uptr I = 0; I < NumClasses; I++) {
       RegionInfo *Region = getRegionInfo(I);
+
       // The actual start of a region is offset by a random number of pages
       // when PrimaryEnableRandomOffset is set.
       Region->RegionBeg = (PrimaryBase + (I << RegionSizeLog)) +
                           (Config::Primary::EnableRandomOffset
                                ? ((getRandomModN(&Seed, 16) + 1) * PageSize)
                                : 0);
       Region->RandState = getRandomU32(&Seed);
       // Releasing small blocks is expensive, set a higher threshold to avoid
       // frequent page releases.
       if (isSmallBlock(getSizeByClassId(I)))
         Region->TryReleaseThreshold = PageSize * SmallerBlockReleasePageDelta;
       else
         Region->TryReleaseThreshold = PageSize;
       Region->ReleaseInfo.LastReleaseAtNs = Time;
 
       Region->MemMapInfo.MemMap = ReservedMemory.dispatch(
           PrimaryBase + (I << RegionSizeLog), RegionSize);
       CHECK(Region->MemMapInfo.MemMap.isAllocated());
     }
     shuffle(RegionInfoArray, NumClasses, &Seed);
 
+    // The binding should be done after region shuffling so that it won't bind
+    // the FLLock from the wrong region.
+    for (uptr I = 0; I < NumClasses; I++)
+      getRegionInfo(I)->FLLockCV.bindTestOnly(getRegionInfo(I)->FLLock);
+
     setOption(Option::ReleaseInterval, static_cast<sptr>(ReleaseToOsInterval));
   }
 
   void unmapTestOnly() NO_THREAD_SAFETY_ANALYSIS {
     for (uptr I = 0; I < NumClasses; I++) {
       RegionInfo *Region = getRegionInfo(I);
       *Region = {};
     }
RegionInfo *Region = getRegionInfo(ClassId);
       TransferBatchT *B = popBatchImpl(C, ClassId, Region);
       if (LIKELY(B))
         return B;
     }
 
     bool ReportRegionExhausted = false;
     TransferBatchT *B = nullptr;
 
+    if (conditionVariableEnabled()) {
+      B = popBatchWithCV(C, ClassId, Region, ReportRegionExhausted);
+    } else {
       while (true) {
-      // When two threads compete for `Region->MMLock`, we only want one of them
-      // does the populateFreeListAndPopBatch(). To avoid both of them doing
-      // that, always check the freelist before mapping new pages.
-      //
-      // TODO(chiahungduan): Use a condition variable so that we don't need to
-      // hold `Region->MMLock` here.
+        // When two threads compete for `Region->MMLock`, we only want one of
+        // them to call populateFreeListAndPopBatch(). To avoid both of them
+        // doing that, always check the freelist before mapping new pages.
         ScopedLock ML(Region->MMLock);
         {
           ScopedLock FL(Region->FLLock);
-        B = popBatchImpl(C, ClassId, Region);
-        if (LIKELY(B))
-          return B;
+          if ((B = popBatchImpl(C, ClassId, Region)))
+            break;
         }
 
         const bool RegionIsExhausted = Region->Exhausted;
         if (!RegionIsExhausted)
           B = populateFreeListAndPopBatch(C, ClassId, Region);
         ReportRegionExhausted = !RegionIsExhausted && Region->Exhausted;
         break;
       }
+    }
 
     if (UNLIKELY(ReportRegionExhausted)) {
       Printf("Can't populate more pages for size class %zu.\n",
              getSizeByClassId(ClassId));
 
       // Theoretically, BatchClass shouldn't be used up. Abort immediately  when
       // it happens.
       if (ClassId == SizeClassMap::BatchClassId)
         reportOutOfBatchClass();
     }
 
     return B;
   }
 
   // Push the array of free blocks to the designated batch group.
   void pushBlocks(CacheT *C, uptr ClassId, CompactPtrT *Array, u32 Size) {
     DCHECK_LT(ClassId, NumClasses);
     DCHECK_GT(Size, 0);
 
     RegionInfo *Region = getRegionInfo(ClassId);
     if (ClassId == SizeClassMap::BatchClassId) {
       ScopedLock L(Region->FLLock);
       pushBatchClassBlocks(Region, Array, Size);
+      if (conditionVariableEnabled())
+        Region->FLLockCV.notifyAll(Region->FLLock);
       return;
     }
 
     // TODO(chiahungduan): Consider not doing grouping if the group size is not
     // greater than the block size with a certain scale.
 
     bool SameGroup = true;
     if (GroupSizeLog < RegionSizeLog) {
if (GroupSizeLog < RegionSizeLog) {
         }
         Array[J] = Cur;
       }
     }
 
     {
       ScopedLock L(Region->FLLock);
       pushBlocksImpl(C, ClassId, Region, Array, Size, SameGroup);
+      if (conditionVariableEnabled())
+        Region->FLLockCV.notifyAll(Region->FLLock);
     }
   }
 
   void disable() NO_THREAD_SAFETY_ANALYSIS {
     // The BatchClassId must be locked last since other classes can use it.
     for (sptr I = static_cast<sptr>(NumClasses) - 1; I >= 0; I--) {
       if (static_cast<uptr>(I) == SizeClassMap::BatchClassId)
         continue;
struct PagesInfo {
     uptr MappedUser = 0;
     // Bytes allocated for user memory.
     uptr AllocatedUser = 0;
   };
 
   struct UnpaddedRegionInfo {
     // Mutex for operations on freelist
     HybridMutex FLLock;
+    ConditionVariableT FLLockCV GUARDED_BY(FLLock);
     // Mutex for memmap operations
     HybridMutex MMLock ACQUIRED_BEFORE(FLLock);
     // `RegionBeg` is initialized before thread creation and won't be changed.
     uptr RegionBeg = 0;
     u32 RandState GUARDED_BY(MMLock) = 0;
     BlocksInfo FreeListInfo GUARDED_BY(FLLock);
     PagesInfo MemMapInfo GUARDED_BY(MMLock);
     // The minimum size of pushed blocks to trigger page release.
     uptr TryReleaseThreshold GUARDED_BY(MMLock) = 0;
     ReleaseToOsInfo ReleaseInfo GUARDED_BY(MMLock) = {};
     bool Exhausted GUARDED_BY(MMLock) = false;
+    bool isPopulatingFreeList GUARDED_BY(FLLock) = false;
   };
   struct RegionInfo : UnpaddedRegionInfo {
     char Padding[SCUDO_CACHE_LINE_SIZE -
                  (sizeof(UnpaddedRegionInfo) % SCUDO_CACHE_LINE_SIZE)] = {};
   };
   static_assert(sizeof(RegionInfo) % SCUDO_CACHE_LINE_SIZE == 0, "");
 
   RegionInfo *getRegionInfo(uptr ClassId) {
for (u32 I = 1; I < Size; ++I) {
       } else {
         ++Count;
       }
     }
 
     InsertBlocks(Cur, Array + Size - Count, Count);
   }
 
+  TransferBatchT *popBatchWithCV(CacheT *C, uptr ClassId, RegionInfo *Region,
+                                 bool &ReportRegionExhausted) {
+    TransferBatchT *B = nullptr;
+
+    while (true) {
+      // We only expect one thread doing the freelist refillment and other
+      // threads will be waiting for either the completion of the
+      // `populateFreeListAndPopBatch()` or `pushBlocks()` called by other
+      // threads.
+      bool PopulateFreeList = false;
+      {
+        ScopedLock FL(Region->FLLock);
+        if (!Region->isPopulatingFreeList) {
+          Region->isPopulatingFreeList = true;
+          PopulateFreeList = true;
+        }
+      }
+
+      if (PopulateFreeList) {
+        ScopedLock ML(Region->MMLock);
+
+        const bool RegionIsExhausted = Region->Exhausted;
+        if (!RegionIsExhausted)
+          B = populateFreeListAndPopBatch(C, ClassId, Region);
+        ReportRegionExhausted = !RegionIsExhausted && Region->Exhausted;
+
+        {
+          // Before reacquiring the `FLLock`, the freelist may be used up again
+          // and some threads are waiting for the freelist refillment by the
+          // current thread. It's important to set
+          // `Region->isPopulatingFreeList` to false so the threads about to
+          // sleep will notice the status change.
+          ScopedLock FL(Region->FLLock);
+          Region->isPopulatingFreeList = false;
+          Region->FLLockCV.notifyAll(Region->FLLock);
+        }
+
+        break;
+      }
+
+      // At here, there are two preconditions to be met before waiting,
+      //   1. The freelist is empty.
+      //   2. Region->isPopulatingFreeList == true, i.e, someone is still doing
+      //   `populateFreeListAndPopBatch()`.
+      //
+      // Note that it has the chance that freelist is empty but
+      // Region->isPopulatingFreeList == false because all the new populated
+      // blocks were used up right after the refillment. Therefore, we have to
+      // check if someone is still populating the freelist.
+      ScopedLock FL(Region->FLLock);
+      if (LIKELY(B = popBatchImpl(C, ClassId, Region)))
+        break;
+
+      if (!Region->isPopulatingFreeList)
+        continue;
+
+      // Now the freelist is empty and someone's doing the refillment. We will
+      // wait until anyone refills the freelist or someone finishes doing
+      // `populateFreeListAndPopBatch()`. The refillment can be done by
+      // `populateFreeListAndPopBatch()`, `pushBlocks()`,
+      // `pushBatchClassBlocks()` and `mergeGroupsToReleaseBack()`.
+      Region->FLLockCV.wait(Region->FLLock);
+
+      if (LIKELY(B = popBatchImpl(C, ClassId, Region)))
+        break;
+    }
+
+    return B;
+  }
+
   // Pop one TransferBatch from a BatchGroup. The BatchGroup with the smallest
   // group id will be considered first.
   //
   // The region mutex needs to be held while calling this method.
   TransferBatchT *popBatchImpl(CacheT *C, uptr ClassId, RegionInfo *Region)
       REQUIRES(Region->FLLock) {
     if (Region->FreeListInfo.BlockList.empty())
       return nullptr;
for (BatchGroupT *BG = Region->FreeListInfo.BlockList.front(),
               BG->Batches.push_front(NonFullBatch);
           }
         }
 
         const u32 NeededSlots = UnusedTransferBatch == nullptr ? 1U : 2U;
         if (UNLIKELY(Idx + NeededSlots > MaxUnusedSize)) {
           ScopedLock L(BatchClassRegion->FLLock);
           pushBatchClassBlocks(BatchClassRegion, Blocks, Idx);
+          if (conditionVariableEnabled())
+            BatchClassRegion->FLLockCV.notifyAll(BatchClassRegion->FLLock);
           Idx = 0;
         }
         Blocks[Idx++] =
             compactPtr(SizeClassMap::BatchClassId, reinterpret_cast<uptr>(Cur));
         if (UnusedTransferBatch) {
           Blocks[Idx++] =
               compactPtr(SizeClassMap::BatchClassId,
                          reinterpret_cast<uptr>(UnusedTransferBatch));
for (BatchGroupT *BG = Region->FreeListInfo.BlockList.front(),
         Region->FreeListInfo.BlockList.insert(Prev, Cur);
       DCHECK_EQ(Cur->Next, BG);
       Prev = Cur;
     }
 
     if (Idx != 0) {
       ScopedLock L(BatchClassRegion->FLLock);
       pushBatchClassBlocks(BatchClassRegion, Blocks, Idx);
+      if (conditionVariableEnabled())
+        BatchClassRegion->FLLockCV.notifyAll(BatchClassRegion->FLLock);
     }
 
     if (SCUDO_DEBUG) {
       BatchGroupT *Prev = Region->FreeListInfo.BlockList.front();
       for (BatchGroupT *Cur = Prev->Next; Cur != nullptr;
            Prev = Cur, Cur = Cur->Next) {
         CHECK_LT(Prev->CompactPtrGroupBase, Cur->CompactPtrGroupBase);
       }
     }
+
+    if (conditionVariableEnabled())
+      Region->FLLockCV.notifyAll(Region->FLLock);
   }
 
   // TODO: `PrimaryBase` can be obtained from ReservedMemory. This needs to be
   // deprecated.
   uptr PrimaryBase = 0;
   ReservedMemoryT ReservedMemory = {};
   // The minimum size of pushed blocks that we will try to release the pages in
   // that size class.
   uptr SmallerBlockReleasePageDelta = 0;
   atomic_s32 ReleaseToOsIntervalMs = {};
   alignas(SCUDO_CACHE_LINE_SIZE) RegionInfo RegionInfoArray[NumClasses];
 };
 
 } // namespace scudo
 
 #endif // SCUDO_PRIMARY64_H_

compiler-rt/lib/scudo/standalone/tests/CMakeLists.txt

 
 set(SCUDO_UNIT_TEST_SOURCES
   atomic_test.cpp
   bytemap_test.cpp
   checksum_test.cpp
   chunk_test.cpp
   combined_test.cpp
   common_test.cpp
+  condition_variable_test.cpp
   flags_test.cpp
   list_test.cpp
   map_test.cpp
   memtag_test.cpp
   mutex_test.cpp
   primary_test.cpp
   quarantine_test.cpp
   release_test.cpp

compiler-rt/lib/scudo/standalone/tests/combined_test.cpp

 //===-- combined_test.cpp ---------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "memtag.h"
 #include "tests/scudo_unit_test.h"
 
 #include "allocator_config.h"
 #include "chunk.h"
 #include "combined.h"
+#include "condition_variable.h"
 #include "mem_map.h"
+#include "size_class_map.h"
 
 #include <algorithm>
 #include <condition_variable>
 #include <memory>
 #include <mutex>
 #include <set>
 #include <stdlib.h>
 #include <thread>
template <class TypeParam> struct ScudoCombinedTest : public Test {
   void BasicTest(scudo::uptr SizeLog);
 
   using AllocatorT = TestAllocator<TypeParam>;
   std::unique_ptr<AllocatorT> Allocator;
 };
 
 template <typename T> using ScudoCombinedDeathTest = ScudoCombinedTest<T>;
 
+namespace scudo {
+struct TestConditionVariableConfig {
+  static const bool MaySupportMemoryTagging = true;
+  template <class A>
+  using TSDRegistryT =
+      scudo::TSDRegistrySharedT<A, 8U, 4U>; // Shared, max 8 TSDs.
+
+  struct Primary {
+    using SizeClassMap = scudo::AndroidSizeClassMap;
+#if SCUDO_CAN_USE_PRIMARY64
+    static const scudo::uptr RegionSizeLog = 28U;
+    typedef scudo::u32 CompactPtrT;
+    static const scudo::uptr CompactPtrScale = SCUDO_MIN_ALIGNMENT_LOG;
+    static const scudo::uptr GroupSizeLog = 20U;
+    static const bool EnableRandomOffset = true;
+    static const scudo::uptr MapSizeIncrement = 1UL << 18;
+#else
+    static const scudo::uptr RegionSizeLog = 18U;
+    static const scudo::uptr GroupSizeLog = 18U;
+    typedef scudo::uptr CompactPtrT;
+#endif
+    static const scudo::s32 MinReleaseToOsIntervalMs = 1000;
+    static const scudo::s32 MaxReleaseToOsIntervalMs = 1000;
+    static const bool UseConditionVariable = true;
+#if SCUDO_LINUX
+    using ConditionVariableT = scudo::ConditionVariableLinux;
+#else
+    using ConditionVariableT = scudo::ConditionVariableDummy;
+#endif
+  };
+#if SCUDO_CAN_USE_PRIMARY64
+  template <typename Config>
+  using PrimaryT = scudo::SizeClassAllocator64<Config>;
+#else
+  template <typename Config>
+  using PrimaryT = scudo::SizeClassAllocator32<Config>;
+#endif
+
+  struct Secondary {
+    template <typename Config>
+    using CacheT = scudo::MapAllocatorNoCache<Config>;
+  };
+  template <typename Config> using SecondaryT = scudo::MapAllocator<Config>;
+};
+} // namespace scudo
+
 #if SCUDO_FUCHSIA
 #define SCUDO_TYPED_TEST_ALL_TYPES(FIXTURE, NAME)                              \
   SCUDO_TYPED_TEST_TYPE(FIXTURE, NAME, FuchsiaConfig)
 #else
 #define SCUDO_TYPED_TEST_ALL_TYPES(FIXTURE, NAME)                              \
   SCUDO_TYPED_TEST_TYPE(FIXTURE, NAME, DefaultConfig)                          \
-  SCUDO_TYPED_TEST_TYPE(FIXTURE, NAME, AndroidConfig)
+  SCUDO_TYPED_TEST_TYPE(FIXTURE, NAME, AndroidConfig)                          \
+  SCUDO_TYPED_TEST_TYPE(FIXTURE, NAME, TestConditionVariableConfig)
 #endif
 
 #define SCUDO_TYPED_TEST_TYPE(FIXTURE, NAME, TYPE)                             \
   using FIXTURE##NAME##_##TYPE = FIXTURE##NAME<scudo::TYPE>;                   \
   TEST_F(FIXTURE##NAME##_##TYPE, NAME) { FIXTURE##NAME<scudo::TYPE>::Run(); }
 
 #define SCUDO_TYPED_TEST(FIXTURE, NAME)                                        \
   template <class TypeParam>                                                   \

compiler-rt/lib/scudo/standalone/tests/condition_variable_test.cpp

+//===-- condition_variable_test.cpp -----------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "tests/scudo_unit_test.h"
+
+#include "common.h"
+#include "condition_variable.h"
+#include "mutex.h"
+
+#include <thread>
+
+template <typename ConditionVariableT> void simpleWaitAndNotifyAll() {
+  constexpr scudo::u32 NumThreads = 2;
+  constexpr scudo::u32 CounterMax = 1024;
+  std::thread Threads[NumThreads];
+
+  scudo::HybridMutex M;
+  ConditionVariableT CV;
+  CV.bindTestOnly(M);
+  scudo::u32 Counter = 0;
+
+  for (scudo::u32 I = 0; I < NumThreads; ++I) {
+    Threads[I] = std::thread(
+        [&](scudo::u32 Id) {
+          do {
+            scudo::ScopedLock L(M);
+            if (Counter % NumThreads != Id && Counter < CounterMax)
+              CV.wait(M);
+            if (Counter >= CounterMax) {
+              break;
+            } else {
+              ++Counter;
+              CV.notifyAll(M);
+            }
+          } while (true);
+        },
+        I);
+  }
+
+  for (std::thread &T : Threads)
+    T.join();
+
+  EXPECT_EQ(Counter, CounterMax);
+}
+
+TEST(ScudoConditionVariableTest, DummyCVWaitAndNotifyAll) {
+  simpleWaitAndNotifyAll<scudo::ConditionVariableDummy>();
+}
+
+#ifdef SCUDO_LINUX
+TEST(ScudoConditionVariableTest, LinuxCVWaitAndNotifyAll) {
+  simpleWaitAndNotifyAll<scudo::ConditionVariableLinux>();
+}
+#endif

compiler-rt/lib/scudo/standalone/tests/primary_test.cpp

 //===-- primary_test.cpp ----------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "tests/scudo_unit_test.h"
 
 #include "allocator_config.h"
+#include "condition_variable.h"
 #include "primary32.h"
 #include "primary64.h"
 #include "size_class_map.h"
 
 #include <algorithm>
 #include <chrono>
 #include <condition_variable>
 #include <mutex>
#endif
     static const scudo::uptr CompactPtrScale = 3U;
     static const scudo::uptr GroupSizeLog = 20U;
     typedef scudo::u32 CompactPtrT;
     static const bool EnableRandomOffset = true;
     static const scudo::uptr MapSizeIncrement = 1UL << 18;
   };
 };
 
+// This is the only test config that enables the condition variable.
+template <typename SizeClassMapT> struct TestConfig5 {
+  static const bool MaySupportMemoryTagging = true;
+
+  struct Primary {
+    using SizeClassMap = SizeClassMapT;
+#if defined(__mips__)
+    // Unable to allocate greater size on QEMU-user.
+    static const scudo::uptr RegionSizeLog = 23U;
+#else
+    static const scudo::uptr RegionSizeLog = 24U;
+#endif
+    static const scudo::s32 MinReleaseToOsIntervalMs = INT32_MIN;
+    static const scudo::s32 MaxReleaseToOsIntervalMs = INT32_MAX;
+    static const scudo::uptr CompactPtrScale = SCUDO_MIN_ALIGNMENT_LOG;
+    static const scudo::uptr GroupSizeLog = 18U;
+    typedef scudo::u32 CompactPtrT;
+    static const bool EnableRandomOffset = true;
+    static const scudo::uptr MapSizeIncrement = 1UL << 18;
+    static const bool UseConditionVariable = true;
+#if SCUDO_LINUX
+    using ConditionVariableT = scudo::ConditionVariableLinux;
+#else
+    using ConditionVariableT = scudo::ConditionVariableDummy;
+#endif
+  };
+};
+
 template <template <typename> class BaseConfig, typename SizeClassMapT>
 struct Config : public BaseConfig<SizeClassMapT> {};
 
 template <template <typename> class BaseConfig, typename SizeClassMapT>
 struct SizeClassAllocator
     : public scudo::SizeClassAllocator64<Config<BaseConfig, SizeClassMapT>> {};
 template <typename SizeClassMapT>
 struct SizeClassAllocator<TestConfig1, SizeClassMapT>

 #define SCUDO_TYPED_TEST_ALL_TYPES(FIXTURE, NAME)                              \
   SCUDO_TYPED_TEST_TYPE(FIXTURE, NAME, TestConfig2)                            \
   SCUDO_TYPED_TEST_TYPE(FIXTURE, NAME, TestConfig3)
 #else
 #define SCUDO_TYPED_TEST_ALL_TYPES(FIXTURE, NAME)                              \
   SCUDO_TYPED_TEST_TYPE(FIXTURE, NAME, TestConfig1)                            \
   SCUDO_TYPED_TEST_TYPE(FIXTURE, NAME, TestConfig2)                            \
   SCUDO_TYPED_TEST_TYPE(FIXTURE, NAME, TestConfig3)                            \
-  SCUDO_TYPED_TEST_TYPE(FIXTURE, NAME, TestConfig4)
+  SCUDO_TYPED_TEST_TYPE(FIXTURE, NAME, TestConfig4)                            \
+  SCUDO_TYPED_TEST_TYPE(FIXTURE, NAME, TestConfig5)
 #endif
 
 #define SCUDO_TYPED_TEST_TYPE(FIXTURE, NAME, TYPE)                             \
   using FIXTURE##NAME##_##TYPE = FIXTURE##NAME<TYPE>;                          \
   TEST_F(FIXTURE##NAME##_##TYPE, NAME) { FIXTURE##NAME<TYPE>::Run(); }
 
 #define SCUDO_TYPED_TEST(FIXTURE, NAME)                                        \
   template <template <typename> class TypeParam>                               \