[scudo] Fine tune busy-waiting in HybridMutex

[Chia-hungDuan]

Summary

Instead of using hardware specific instruction, using simple loop over
volatile variable gives similar and more predicatable waiting time. Also
fine tune the waiting time to fit with the average time in malloc/free
operations.

[cferris]

Mostly comment nits.

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

38

It's probably better to name this something like delay or delayLoop since it's not really doing a yield any more.

57–58

that are guarded by the mutex.

Although, I'm not sure exactly what you mean by minimum time spent among operations. Do you mean the average time spent during operations while the mutex is held?

69

times

[Chia-hungDuan]

Address review comment

[Chia-hungDuan]

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

57–58

It's the shortest time while doing alloc/free. Use it as query interval (or tryLock interval) to avoid waiting too long for the completion of an operation.

Rephrased a little bit

[cferris]

LGTM.

[Chia-hungDuan]

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

60

There was some measurement bias here. Will update a new default value

[melver]

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

117

What's the real objective of this change?

What's the performance improvement?

gives similar and more predicatable waiting time

The CPU pause/yield instructions are not just about the waiting time itself, but about making sure the CPU doesn't waste energy and is potentially hostile to neighbouring cores/HW-threads (such as hyperthreads). One problem here is that if the locking thread starts to spin too aggressively, it may take resources from the thread that it wants to release the mutex to make forward progress in the first place. This is a real problem when the waiting thread and the thread that needs to release the mutex are on the same core on sibling hyperthreads.

"Improves the performance of spin-wait loops. When executing a “spin-wait loop,” processors will suffer a severe performance penalty when exiting the loop because it detects a possible memory order violation. The PAUSE instruction provides a hint to the processor that the code sequence is a spin-wait loop. [...] An additional function of the PAUSE instruction is to reduce the power consumed by a processor while executing a spin loop."

https://www.felixcloutier.com/x86/pause.html

[Chia-hungDuan]

Update the length of busy-waiting loop

[Chia-hungDuan]

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

117

I take several busy-waiting implementations from allocators (like jemalloc, tcmalloc), jvm (Android ART), libraries (libc++, abseil), .etc as references. Most of them use volatile as well. In Linux kernel, it uses pause or nop depends on versions.

The main argument behind this is that this is not a general used mutex. It's specific to Scudo's operations and most operations are expected to be pretty quick. Besides, a program is unlikely to heavily stress the user space memory allocator and therefore causes heavy contention on the Scudo's region mutex.' Those instructions may suggest context-switch which may take longer time than finishing most operations. For example, on pixel 7 pro (arm64), it shows 7~8% performance difference.

As a result, using those inline assembly seems not showing the benefit as always in our case but increase the complexity of maintaining these kind of inline assembly across different platforms (and architectures). In addition, given that the short and expected length of waiting time, volatile is more preferred in Scudo.

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

template <typename T> inline void shuffle(T *A, u32 N, u32 *RandState) {
   if (N <= 1)
     return;
   u32 State = *RandState;
   for (u32 I = N - 1; I > 0; I--)
     Swap(A[I], A[getRandomModN(&State, I + 1)]);
   *RandState = State;
 }
 
-// Hardware specific inlinable functions.
-
-inline void yieldProcessor(UNUSED u8 Count) {
-#if defined(__i386__) || defined(__x86_64__)
-  __asm__ __volatile__("" ::: "memory");
-  for (u8 I = 0; I < Count; I++)
-    __asm__ __volatile__("pause");
-#elif defined(__aarch64__) || defined(__arm__)
-  __asm__ __volatile__("" ::: "memory");
-  for (u8 I = 0; I < Count; I++)
-    __asm__ __volatile__("yield");
-#endif
-  __asm__ __volatile__("" ::: "memory");
-}
-
 // Platform specific functions.
 
 extern uptr PageSizeCached;
 uptr getPageSizeSlow();
 inline uptr getPageSizeCached() {
 #if SCUDO_ANDROID && defined(PAGE_SIZE)
   // Most Android builds have a build-time constant page size.
   return PAGE_SIZE;

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

if (LIKELY(tryLock()))
       // The compiler may try to fully unroll the loop, ending up in a
       // NumberOfTries*NumberOfYields block of pauses mixed with tryLocks. This
       // is large, ugly and unneeded, a compact loop is better for our purpose
       // here. Use a pragma to tell the compiler not to unroll the loop.
 #ifdef __clang__
 #pragma nounroll
 #endif
     for (u8 I = 0U; I < NumberOfTries; I++) {
-      yieldProcessor(NumberOfYields);
+      delayLoop();
       if (tryLock())
         return;
     }
     lockSlow();
   }
   void unlock() RELEASE();
 
   // TODO(chiahungduan): In general, we may want to assert the owner of lock as
   // well. Given the current uses of HybridMutex, it's acceptable without
   // asserting the owner. Re-evaluate this when we have certain scenarios which
   // requires a more fine-grained lock granularity.
   ALWAYS_INLINE void assertHeld() ASSERT_CAPABILITY(this) {
     if (SCUDO_DEBUG)
       assertHeldImpl();
   }
 
 private:
+  void delayLoop() {
+    // The value comes from the average time spent in accessing caches (which
+    // are the fastest operations) so that we are unlikely to wait too long for
+    // fast operations.
+    constexpr u32 SpinTimes = 16;
+    volatile u32 V = 0;
+    for (u32 I = 0; I < SpinTimes; ++I)
+      ++V;
+  }
+
   void assertHeldImpl();
 
-  static constexpr u8 NumberOfTries = 8U;
-  static constexpr u8 NumberOfYields = 8U;
+  // TODO(chiahungduan): Adapt this value based on scenarios. E.g., primary and
+  // secondary allocator have different allocation times.
+  static constexpr u8 NumberOfTries = 32U;
 
 #if SCUDO_LINUX
   atomic_u32 M = {};
 #elif SCUDO_FUCHSIA
   sync_mutex_t M = {};
 #endif
 
   void lockSlow() ACQUIRE();