[scudo] Add Android support

[cryptoad]

Summary

This change adds Android support to the allocator (but doesn't yet enable it in
the cmake config), and should be the last fragment of the rewritten change
D31947.

Android has more memory constraints than other platforms, so the idea of a
unique context per thread would not have worked. The alternative chosen is to
allocate a set of contexts based on the number of cores on the machine, and
share those contexts within the threads. Contexts can be dynamically reassigned
to threads to prevent contention, based on a scheme suggested by @dvyuokv in
the initial review.

Additionally, given that Android doesn't support ELF TLS (only emutls for now),
we use the TSan TLS slot to make things faster: Scudo is mutually exclusive
with other sanitizers so this shouldn't cause any problem.

An additional change made here, is replacing thread_local by THREADLOCAL
and using the initial-exec thread model in the non-Android version to prevent
extraneous weak definition and checks on the relevant variables.

[dvyukov]

lib/scudo/scudo_tls.h

36

This one liner is used only once, just inline it there. Additional levels of indirection do not help understanding code.

lib/scudo/scudo_tls_android.h

47

This is duplicated from tsan, right? Please move this bulky chunk of tricky assembly into sanitizer_common (along with TLS_SLOT_TSAN). No reason to have 2 copies of a complex code, and we can potentially use it in asan and later in msan. Something like:

uptr *get_android_tls_ptr();

85

By sanitizer convention functions ending with Locked mean that function call normally needs to be protected with a mutex, but this is version for the case when caller already holds the mutex. For such case we generally use AndLock suffix (e.g. GetIfExistsAndLock).
Please rename this to getThreadContextAndLock. It will also make relation between Lock and Unlock much clearer in the following code:

ScudoThreadContext *ThreadContext = getThreadContextAndLock();
if (LIKELY(ThreadContext)) {
  ...
  ThreadContext->unlock();
}

92

I would move everything starting from this line to getThreadContextLockedSlow. I think this is where slow path starts.
Then we also don't need ThreadContexts and NumberOfContexts in header.

[cryptoad]

Thanks Dmitry. Additional question in the comment before making the code modifications.

lib/scudo/scudo_tls.h

36

Will do.
Additionally, UnusedSince and Mutex are only used for Android. Is worth adding an #if to not have them in the non-Android version, or is the clutter not worth it?

lib/scudo/scudo_tls_android.h

47

Correct. TSan uses only the AArch64 & x64 versions, and I needed them all (mips being bordeline but still included).
I will move it to sanitizer_common.

85

Will do.

92

Will do.

[dvyukov]

lib/scudo/scudo_tls.h

36

I am fine either way.
I've noticed the android-specific data and methods, but couldn't think of an elegant, non-overdesigned solution...

[cryptoad]

Addressing Dmitry's comments, except for the the __get_tls() part which is
being worked on in a separate patch. Once it's done, I will update this patch
again.

[cryptoad]

Modified to leverage the new get_android_tls_ptr() function introduced in
sanitizer_common with D32705.

[cryptoad]

Removing debug Printf line that mistakenly made its way in the patch.

[cryptoad]

Getting rid of some extra spaces.

[alekseyshl]

lib/scudo/scudo_tls_android.h

29

Can we rename UnusedSince to something else? It's a bit confusing to read the code, it is set when the context is, in fact, in use (by some other thread). How about InSlowLockQueueSince or SlowLockOrder or SlowLockPrecedence? Two latter ones abstract the fact that we use timespamp, which, to me, is a good thing,

lib/scudo/scudo_tls_linux.h

35–38

Is the explicit model necessary?

[cryptoad]

lib/scudo/scudo_tls_android.h

29

Good idea. Will do.

lib/scudo/scudo_tls_linux.h

35–38

I talked to Dmitry offline about this.
When looking at the assembly, the portion of codes using ScudoThreadState looked like (on all archs):

                mov     r15, cs:_ZTHN7__scudo16ScudoThreadStateE_ptr
                test    r15, r15
                jz      short loc_7FD57
                call    __ZTHN7__scudo16ScudoThreadStateE
loc_7FD57:                              ; CODE XREF: __scudo::scudoMalloc(ulong,__scudo::AllocType)+20 j
                mov     r13, 0FFFFFFFFFFFFFFC0h
                cmp     byte ptr fs:[r13+0], 0
                jz      loc_80020
loc_7FD6A:                              ; CODE XREF: __scudo::scudoMalloc(ulong,__scudo::AllocType)+2F5 j

The compiler creates a weak symbol for the extern thread_local variables, looks them up, and if they exist, calls them, then proceeds with the regular flow of code.
The overhead has no use (those weak symbols are never defined), and goes away by explicitly specifying the model: it just read it from the TLS.

[cryptoad]

Renaming UnusedSince to SlowLockPrecedence.

Also, since I am not 100% sure that the case where all the contexts would have
a 0 SlowLockPrecedence cannot happen, change the CHECK_NE to a fallback to
the context currently assigned to the thread.

[alekseyshl]

lib/scudo/scudo_tls.h

28–30

You don't need public here.

47

How about structuring it this way:

namespace __scudo {

#include "scudo_tls_context_android.inc"
#include "scudo_tls_context_linux.inc"

struct ALIGNED(64) ScudoThreadContext : public ScudoThreadContextPlatform {
  AllocatorCache Cache;
  Xorshift128Plus Prng;
  uptr QuarantineCachePlaceHolder[4];
};

void initThread();

// Fastpath functions are defined in the following platform specific headers.
#include "scudo_tls_android.inc"
#include "scudo_tls_linux.inc"

}  // namespace __scudo

You can define lock/unlock/etc functions inline on the struct and Linux version might not need them defined at all (hard to tell for me off the bat).

lib/scudo/scudo_tls_linux.h

35–38

Good to know. My understanding was that compiler is supposed to select the most restricted model which works for the code being compiled. Apparently, it's not always the case.

[cryptoad]

Splitting the thread context definition based on the underlying platform.

[cryptoad]

Reshuffling public & private, to leverage the default public-ness of structs.

[cryptoad]

Forgot one last public.

[alekseyshl]

LGTM

lib/scudo/scudo_tls_android.cpp

74

I'd call it just 'Precedence', to match ThreadContext. 'LowestPrecedence' usually means 'the last to pick' and here it's the other way.

[cryptoad]

Addressing Aleksey's comment (s/LowestPrecedence/Precedence).

lib/scudo/CMakeLists.txt

 add_compiler_rt_component(scudo)
 
 include_directories(..)
 
 set(SCUDO_CFLAGS ${SANITIZER_COMMON_CFLAGS})
 # SANITIZER_COMMON_CFLAGS include -fno-builtin, but we actually want builtins!
 list(APPEND SCUDO_CFLAGS -fbuiltin)
 append_rtti_flag(OFF SCUDO_CFLAGS)
 
 set(SCUDO_SOURCES
   scudo_allocator.cpp
   scudo_flags.cpp
   scudo_crc32.cpp
   scudo_interceptors.cpp
   scudo_new_delete.cpp
   scudo_termination.cpp
+  scudo_tls_android.cpp
   scudo_tls_linux.cpp
   scudo_utils.cpp)
 
 # Enable the SSE 4.2 instruction set for scudo_crc32.cpp, if available.
 if (COMPILER_RT_HAS_MSSE4_2_FLAG)
   set_source_files_properties(scudo_crc32.cpp PROPERTIES COMPILE_FLAGS -msse4.2)
 endif()
 

lib/scudo/scudo_allocator.h

 const uptr MaxAlignment = 1 << MaxAlignmentLog;
 
 const uptr ChunkHeaderSize = sizeof(PackedHeader);
 const uptr AlignedChunkHeaderSize =
     (ChunkHeaderSize + MinAlignment - 1) & ~(MinAlignment - 1);
 
 #if SANITIZER_CAN_USE_ALLOCATOR64
 const uptr AllocatorSpace = ~0ULL;
-const uptr AllocatorSize = 0x40000000000ULL;  // 4TB.
+# if defined(__aarch64__) && SANITIZER_ANDROID
+const uptr AllocatorSize = 0x4000000000ULL;  // 256G.
+# elif defined(__aarch64__)
+const uptr AllocatorSize = 0x10000000000ULL;  // 1T.
+# else
+const uptr AllocatorSize = 0x40000000000ULL;  // 4T.
+# endif
 typedef DefaultSizeClassMap SizeClassMap;
 struct AP {
   static const uptr kSpaceBeg = AllocatorSpace;
   static const uptr kSpaceSize = AllocatorSize;
   static const uptr kMetadataSize = 0;
   typedef __scudo::SizeClassMap SizeClassMap;
   typedef NoOpMapUnmapCallback MapUnmapCallback;
   static const uptr kFlags =

lib/scudo/scudo_allocator.cpp

void *allocate(uptr Size, uptr Alignment, AllocType Type,
     // allocations here, but the Secondary will take care of its own alignment
     // needs, which means we also have to work around some limitations of the
     // combined allocator to accommodate the situation.
     bool FromPrimary = PrimaryAllocator::CanAllocate(NeededSize, MinAlignment);
 
     void *Ptr;
     uptr Salt;
     uptr AllocationAlignment = FromPrimary ? MinAlignment : Alignment;
-    ScudoThreadContext *ThreadContext = getThreadContext();
+    ScudoThreadContext *ThreadContext = getThreadContextAndLock();
     if (LIKELY(ThreadContext)) {
       Salt = getPrng(ThreadContext)->getNext();
       Ptr = BackendAllocator.Allocate(getAllocatorCache(ThreadContext),
                                       NeededSize, AllocationAlignment);
+      ThreadContext->unlock();
     } else {
       SpinMutexLock l(&FallbackMutex);
       Salt = FallbackPrng.getNext();
       Ptr = BackendAllocator.Allocate(&FallbackAllocatorCache, NeededSize,
                                       AllocationAlignment);
     }
     if (!Ptr)
       return BackendAllocator.ReturnNullOrDieOnOOM();
struct ScudoAllocator {
   // chunk being loaded (and checked) twice, and stored (and checksummed) once,
   // with no additional security value.
   void quarantineOrDeallocateChunk(ScudoChunk *Chunk, UnpackedHeader *Header,
                                    uptr Size) {
     bool BypassQuarantine = (AllocatorQuarantine.GetCacheSize() == 0);
     if (BypassQuarantine) {
       Chunk->eraseHeader();
       void *Ptr = Chunk->getAllocBeg(Header);
-      ScudoThreadContext *ThreadContext = getThreadContext();
+      ScudoThreadContext *ThreadContext = getThreadContextAndLock();
       if (LIKELY(ThreadContext)) {
         getBackendAllocator().Deallocate(getAllocatorCache(ThreadContext), Ptr);
+        ThreadContext->unlock();
       } else {
         SpinMutexLock Lock(&FallbackMutex);
         getBackendAllocator().Deallocate(&FallbackAllocatorCache, Ptr);
       }
     } else {
       UnpackedHeader NewHeader = *Header;
       NewHeader.State = ChunkQuarantine;
       Chunk->compareExchangeHeader(&NewHeader, Header);
-      ScudoThreadContext *ThreadContext = getThreadContext();
+      ScudoThreadContext *ThreadContext = getThreadContextAndLock();
       if (LIKELY(ThreadContext)) {
         AllocatorQuarantine.Put(getQuarantineCache(ThreadContext),
                                 QuarantineCallback(
                                     getAllocatorCache(ThreadContext)),
                                 Chunk, Size);
+        ThreadContext->unlock();
       } else {
         SpinMutexLock l(&FallbackMutex);
         AllocatorQuarantine.Put(&FallbackQuarantineCache,
                                 QuarantineCallback(&FallbackAllocatorCache),
                                 Chunk, Size);
       }
     }
   }

lib/scudo/scudo_tls.h

 //===----------------------------------------------------------------------===//
 
 #ifndef SCUDO_TLS_H_
 #define SCUDO_TLS_H_
 
 #include "scudo_allocator.h"
 #include "scudo_utils.h"
 
+#include "sanitizer_common/sanitizer_linux.h"
+#include "sanitizer_common/sanitizer_platform.h"
+
 namespace __scudo {
 
 struct ALIGNED(64) ScudoThreadContext {
  public:
+  StaticSpinMutex Mutex;
+  atomic_uint64_t SlowLockPrecedence;
   AllocatorCache Cache;
   Xorshift128Plus Prng;
   uptr QuarantineCachePlaceHolder[4];
   void init();
   void commitBack();
+  bool tryLock();
+  void lock();
+  void unlock();
 };
 
 void initThread();
 
 // Fastpath functions are defined in the following platform specific headers.
+#include "scudo_tls_android.h"
 #include "scudo_tls_linux.h"
 
 }  // namespace __scudo
 
 #endif  // SCUDO_TLS_H_

lib/scudo/scudo_tls_android.h

+//===-- scudo_tls_android.h -------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+///
+/// Scudo thread local structure fastpath functions implementation for Android.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef SCUDO_TLS_ANDROID_H_
+#define SCUDO_TLS_ANDROID_H_
+
+#ifndef SCUDO_TLS_H_
+# error "This file must be included inside scudo_tls.h."
+#endif  // SCUDO_TLS_H_
+
+#if SANITIZER_LINUX && SANITIZER_ANDROID
+
+INLINE bool ScudoThreadContext::tryLock() {
+  if (Mutex.TryLock()) {
+    atomic_store_relaxed(&SlowLockPrecedence, 0);
+    return true;
+  }
+  if (atomic_load_relaxed(&SlowLockPrecedence) == 0)
+    atomic_store_relaxed(&SlowLockPrecedence, NanoTime());
+  return false;
+}
+
+INLINE void ScudoThreadContext::lock() {
+  Mutex.Lock();
+  atomic_store_relaxed(&SlowLockPrecedence, 0);
+}
+
+INLINE void ScudoThreadContext::unlock() {
+  Mutex.Unlock();
+}
+
+ALWAYS_INLINE void initThreadMaybe() {
+  if (LIKELY(*get_android_tls_ptr()))
+    return;
+  initThread();
+}
+
+ScudoThreadContext *getThreadContextAndLockSlow();
+
+ALWAYS_INLINE ScudoThreadContext *getThreadContextAndLock() {
+  ScudoThreadContext *ThreadContext =
+      reinterpret_cast<ScudoThreadContext *>(*get_android_tls_ptr());
+  CHECK(ThreadContext);
+  // Try to lock the currently associated context.
+  if (ThreadContext->tryLock())
+    return ThreadContext;
+  // If it failed, go the slow path.
+  return getThreadContextAndLockSlow();
+}
+
+#endif  // SANITIZER_LINUX && SANITIZER_ANDROID
+
+#endif  // SCUDO_TLS_ANDROID_H_

lib/scudo/scudo_tls_android.cpp

+//===-- scudo_tls_android.cpp -----------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+///
+/// Scudo thread local structure implementation for Android.
+///
+//===----------------------------------------------------------------------===//
+
+#include "sanitizer_common/sanitizer_platform.h"
+
+#if SANITIZER_LINUX && SANITIZER_ANDROID
+
+#include "scudo_tls.h"
+
+#include <pthread.h>
+
+namespace __scudo {
+
+static pthread_once_t GlobalInitialized = PTHREAD_ONCE_INIT;
+static pthread_key_t PThreadKey;
+
+static atomic_uint32_t ThreadContextCurrentIndex;
+static ScudoThreadContext *ThreadContexts;
+static uptr NumberOfContexts;
+
+// sysconf(_SC_NPROCESSORS_{CONF,ONLN}) cannot be used as they allocate memory.
+static uptr getNumberOfCPUs() {
+  cpu_set_t CPUs;
+  CHECK_EQ(sched_getaffinity(0, sizeof(cpu_set_t), &CPUs), 0);
+  return CPU_COUNT(&CPUs);
+}
+
+static void initOnce() {
+  // Hack: TLS_SLOT_TSAN was introduced in N. To be able to use it on M for
+  // testing, we create an unused key. Since the key_data array follows the tls
+  // array, it basically gives us the extra entry we need.
+  // TODO(kostyak): remove and restrict to N and above.
+  CHECK_EQ(pthread_key_create(&PThreadKey, NULL), 0);
+  initScudo();
+  NumberOfContexts = getNumberOfCPUs();
+  ThreadContexts = reinterpret_cast<ScudoThreadContext *>(
+      MmapOrDie(sizeof(ScudoThreadContext) * NumberOfContexts, __func__));
+  for (int i = 0; i < NumberOfContexts; i++)
+    ThreadContexts[i].init();
+}
+
+void initThread() {
+  pthread_once(&GlobalInitialized, initOnce);
+  // Initial context assignment is done in a plain round-robin fashion.
+  u32 Index = atomic_fetch_add(&ThreadContextCurrentIndex, 1,
+                               memory_order_relaxed);
+  ScudoThreadContext *ThreadContext =
+      &ThreadContexts[Index % NumberOfContexts];
+  *get_android_tls_ptr() = reinterpret_cast<uptr>(ThreadContext);
+}
+
+ScudoThreadContext *getThreadContextAndLockSlow() {
+  ScudoThreadContext *ThreadContext;
+  // Go through all the contexts and find the first unlocked one. 
+  for (u32 i = 0; i < NumberOfContexts; i++) {
+    ThreadContext = &ThreadContexts[i];
+    if (ThreadContext->tryLock()) {
+      *get_android_tls_ptr() = reinterpret_cast<uptr>(ThreadContext);
+      return ThreadContext;
+    }
+  }
+  // No luck, find the one with the lowest precedence, and slow lock it.
+  u64 LowestPrecedence = UINT64_MAX;
+  for (u32 i = 0; i < NumberOfContexts; i++) {
+    u64 SlowLockPrecedence =
+        atomic_load_relaxed(&ThreadContexts[i].SlowLockPrecedence);
+    if (SlowLockPrecedence && SlowLockPrecedence < LowestPrecedence) {
+      ThreadContext = &ThreadContexts[i];
+      LowestPrecedence = SlowLockPrecedence;
+    }
+  }
+  if (LIKELY(LowestPrecedence != UINT64_MAX)) {
+    ThreadContext->lock();
+    *get_android_tls_ptr() = reinterpret_cast<uptr>(ThreadContext);
+    return ThreadContext;
+  }
+  // Last resort (can this happen?), stick with the current one.
+  ThreadContext =
+      reinterpret_cast<ScudoThreadContext *>(*get_android_tls_ptr());
+  ThreadContext->lock();
+  return ThreadContext;
+}
+
+}  // namespace __scudo
+
+#endif  // SANITIZER_LINUX && SANITIZER_ANDROID

lib/scudo/scudo_tls_linux.h

 
 #ifndef SCUDO_TLS_LINUX_H_
 #define SCUDO_TLS_LINUX_H_
 
 #ifndef SCUDO_TLS_H_
 # error "This file must be included inside scudo_tls.h."
 #endif  // SCUDO_TLS_H_
 
-#include "sanitizer_common/sanitizer_platform.h"
+#if SANITIZER_LINUX && !SANITIZER_ANDROID
 
-#if SANITIZER_LINUX
+// For thread_local contexts, there is no locking. unlock() is the only function
+// used within scudo_allocator.cpp, and should be optimized out by the compiler.
+UNUSED INLINE bool ScudoThreadContext::tryLock() { return true; }
+UNUSED INLINE void ScudoThreadContext::lock() {}
+ALWAYS_INLINE void ScudoThreadContext::unlock() {}
 
 enum ThreadState : u8 {
   ThreadNotInitialized = 0,
   ThreadInitialized,
   ThreadTornDown,
 };
-extern thread_local ThreadState ScudoThreadState;
-extern thread_local ScudoThreadContext ThreadLocalContext;
+__attribute__((tls_model("initial-exec")))
+extern THREADLOCAL ThreadState ScudoThreadState;
+__attribute__((tls_model("initial-exec")))
+extern THREADLOCAL ScudoThreadContext ThreadLocalContext;
 
 ALWAYS_INLINE void initThreadMaybe() {
   if (LIKELY(ScudoThreadState != ThreadNotInitialized))
     return;
   initThread();
 }
 
-ALWAYS_INLINE ScudoThreadContext *getThreadContext() {
+ALWAYS_INLINE ScudoThreadContext *getThreadContextAndLock() {
   if (UNLIKELY(ScudoThreadState == ThreadTornDown))
     return nullptr;
   return &ThreadLocalContext;
 }
 
-#endif  // SANITIZER_LINUX
+#endif  // SANITIZER_LINUX && !SANITIZER_ANDROID
 
 #endif  // SCUDO_TLS_LINUX_H_

lib/scudo/scudo_tls_linux.cpp

 //===-- scudo_tls_linux.cpp -------------------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// Scudo thread local structure implementation for platforms supporting
 /// thread_local.
 ///
 //===----------------------------------------------------------------------===//
 
 #include "sanitizer_common/sanitizer_platform.h"
 
-#if SANITIZER_LINUX
+#if SANITIZER_LINUX && !SANITIZER_ANDROID
 
 #include "scudo_tls.h"
 
 #include <limits.h>
 #include <pthread.h>
 
 namespace __scudo {
 
 static pthread_once_t GlobalInitialized = PTHREAD_ONCE_INIT;
 static pthread_key_t PThreadKey;
 
-thread_local ThreadState ScudoThreadState = ThreadNotInitialized;
-thread_local ScudoThreadContext ThreadLocalContext;
+__attribute__((tls_model("initial-exec")))
+THREADLOCAL ThreadState ScudoThreadState = ThreadNotInitialized;
+__attribute__((tls_model("initial-exec")))
+THREADLOCAL ScudoThreadContext ThreadLocalContext;
 
 static void teardownThread(void *Ptr) {
   uptr Iteration = reinterpret_cast<uptr>(Ptr);
   // The glibc POSIX thread-local-storage deallocation routine calls user
   // provided destructors in a loop of PTHREAD_DESTRUCTOR_ITERATIONS.
   // We want to be called last since other destructors might call free and the
   // like, so we wait until PTHREAD_DESTRUCTOR_ITERATIONS before draining the
   // quarantine and swallowing the cache.
void initThread() {
   pthread_once(&GlobalInitialized, initOnce);
   pthread_setspecific(PThreadKey, reinterpret_cast<void *>(1));
   ThreadLocalContext.init();
   ScudoThreadState = ThreadInitialized;
 }
 
 }  // namespace __scudo
 
-#endif  // SANITIZER_LINUX
+#endif  // SANITIZER_LINUX && !SANITIZER_ANDROID