[scudo] Correct a behavior on the shared TSD registry

[cryptoad]

Summary

There is an error in the shared TSD registry logic when looking for a
TSD in the slow path. There is an unlikely event when a TSD's precedence
was 0 after attempting a tryLock which indicated that it was grabbed
by another thread in between. We dealt with that case by continuing to
the next iteration, but that meant that the Index was not increased
and we ended up trying to lock the same TSD.
This would manifest in heavy contention, and in the end we would still
lock a TSD, but that was a wasted iteration.
So, do not continue, just skip the TSD as a potential candidate.

This is in both the standalone & non-standalone versions.

[cryptoad]

Remove unchanged files from CL.

[morehouse]

LGTM

lib/scudo/scudo_tsd_shared.cpp

if (NumberOfTSDs > 1) {
     // Go randomly through at most 4 contexts and find a candidate.
     for (u32 I = 0; I < Min(4U, NumberOfTSDs); I++) {
       if (TSDs[Index].tryLock()) {
         setCurrentTSD(&TSDs[Index]);
         return &TSDs[Index];
       }
       const uptr Precedence = TSDs[Index].getPrecedence();
       // A 0 precedence here means another thread just locked this TSD.
-      if (UNLIKELY(Precedence == 0))
-        continue;
-      if (Precedence < LowestPrecedence) {
+      if (Precedence && Precedence < LowestPrecedence) {
         CandidateTSD = &TSDs[Index];
         LowestPrecedence = Precedence;
       }
       Index += Inc;
       if (Index >= NumberOfTSDs)
         Index -= NumberOfTSDs;
     }
     if (CandidateTSD) {

lib/scudo/standalone/tsd_shared.h

if (MaxTSDCount > 1U && NumberOfTSDs > 1U) {
       // Go randomly through at most 4 contexts and find a candidate.
       for (u32 I = 0; I < Min(4U, NumberOfTSDs); I++) {
         if (TSDs[Index].tryLock()) {
           setCurrentTSD(&TSDs[Index]);
           return &TSDs[Index];
         }
         const uptr Precedence = TSDs[Index].getPrecedence();
         // A 0 precedence here means another thread just locked this TSD.
-        if (UNLIKELY(Precedence == 0))
-          continue;
-        if (Precedence < LowestPrecedence) {
+        if (Precedence && Precedence < LowestPrecedence) {
           CandidateTSD = &TSDs[Index];
           LowestPrecedence = Precedence;
         }
         Index += Inc;
         if (Index >= NumberOfTSDs)
           Index -= NumberOfTSDs;
       }
       if (CandidateTSD) {

lib/scudo/standalone/wrappers_c.h

 //===-- wrappers_c.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_WRAPPERS_C_H_
 #define SCUDO_WRAPPERS_C_H_
 
 #include "platform.h"
 #include "stats.h"
 
 // Bionic's struct mallinfo consists of size_t (mallinfo(3) uses int).
 #if SCUDO_ANDROID
 typedef size_t __scudo_mallinfo_data_t;
 #else
 typedef int __scudo_mallinfo_data_t;
 #endif
 
 struct __scudo_mallinfo {
   __scudo_mallinfo_data_t arena;
   __scudo_mallinfo_data_t ordblks;
   __scudo_mallinfo_data_t smblks;
   __scudo_mallinfo_data_t hblks;
   __scudo_mallinfo_data_t hblkhd;
   __scudo_mallinfo_data_t usmblks;
   __scudo_mallinfo_data_t fsmblks;
   __scudo_mallinfo_data_t uordblks;
   __scudo_mallinfo_data_t fordblks;
   __scudo_mallinfo_data_t keepcost;
 };
 
 // Android sometimes includes malloc.h no matter what, which yields to
 // conflicting return types for mallinfo() if we use our own structure. So if
 // struct mallinfo is declared (#define courtesy of malloc.h), use it directly.
 #if STRUCT_MALLINFO_DECLARED
 #define SCUDO_MALLINFO mallinfo
 #else
 #define SCUDO_MALLINFO __scudo_mallinfo
 #endif
 
 #ifndef M_DECAY_TIME
 #define M_DECAY_TIME -100
 #endif
 
 #ifndef M_PURGE
 #define M_PURGE -101
 #endif
 
 #endif // SCUDO_WRAPPERS_C_H_
 

lib/scudo/standalone/wrappers_c.cc

 //===-- wrappers_c.cc -------------------------------------------*- 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"
 
 // Skip this compilation unit if compiled as part of Bionic.
 #if !SCUDO_ANDROID || !_BIONIC
 
 #include "allocator_config.h"
 #include "wrappers_c.h"
 #include "wrappers_c_checks.h"
 
 #include <stdint.h>
 #include <stdio.h>
 
 static scudo::Allocator<scudo::Config> Allocator;
 // Pointer to the static allocator so that the C++ wrappers can access it.
 // Technically we could have a completely separated heap for C & C++ but in
 // reality the amount of cross pollination between the two is staggering.
 scudo::Allocator<scudo::Config> *AllocatorPtr = &Allocator;
 
 extern "C" {
 
 #define SCUDO_PREFIX(name) name
 #define SCUDO_ALLOCATOR Allocator
 #include "wrappers_c.inc"
 #undef SCUDO_ALLOCATOR
 #undef SCUDO_PREFIX
 
 INTERFACE void __scudo_print_stats(void) { Allocator.printStats(); }
 
 } // extern "C"
 
 #endif // !SCUDO_ANDROID || !_BIONIC
 

lib/scudo/standalone/wrappers_c.inc

 //===-- wrappers_c.inc ------------------------------------------*- 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_PREFIX
 #error "Define SCUDO_PREFIX prior to including this file!"
 #endif
 
 // malloc-type functions have to be aligned to std::max_align_t. This is
 // distinct from (1U << SCUDO_MIN_ALIGNMENT_LOG), since C++ new-type functions
 // do not have to abide by the same requirement.
 #ifndef SCUDO_MALLOC_ALIGNMENT
 #define SCUDO_MALLOC_ALIGNMENT FIRST_32_SECOND_64(8U, 16U)
 #endif
 
 INTERFACE WEAK void *SCUDO_PREFIX(calloc)(size_t nmemb, size_t size) {
   scudo::uptr Product;
   if (UNLIKELY(scudo::checkForCallocOverflow(size, nmemb, &Product))) {
     if (SCUDO_ALLOCATOR.canReturnNull()) {
       errno = ENOMEM;
       return nullptr;
     }
     scudo::reportCallocOverflow(nmemb, size);
   }
   return scudo::setErrnoOnNull(SCUDO_ALLOCATOR.allocate(
       Product, scudo::Chunk::Origin::Malloc, SCUDO_MALLOC_ALIGNMENT, true));
 }
 
 INTERFACE WEAK void SCUDO_PREFIX(free)(void *ptr) {
   SCUDO_ALLOCATOR.deallocate(ptr, scudo::Chunk::Origin::Malloc);
 }
 
 INTERFACE WEAK struct SCUDO_MALLINFO SCUDO_PREFIX(mallinfo)(void) {
   struct SCUDO_MALLINFO Info = {};
   scudo::StatCounters Stats;
   SCUDO_ALLOCATOR.getStats(Stats);
   Info.uordblks =
       static_cast<__scudo_mallinfo_data_t>(Stats[scudo::StatAllocated]);
   return Info;
 }
 
 INTERFACE WEAK void *SCUDO_PREFIX(malloc)(size_t size) {
   return scudo::setErrnoOnNull(SCUDO_ALLOCATOR.allocate(
       size, scudo::Chunk::Origin::Malloc, SCUDO_MALLOC_ALIGNMENT));
 }
 
 #if SCUDO_ANDROID
 INTERFACE WEAK size_t SCUDO_PREFIX(malloc_usable_size)(const void *ptr) {
 #else
 INTERFACE WEAK size_t SCUDO_PREFIX(malloc_usable_size)(void *ptr) {
 #endif
   return SCUDO_ALLOCATOR.getUsableSize(ptr);
 }
 
 INTERFACE WEAK void *SCUDO_PREFIX(memalign)(size_t alignment, size_t size) {
   // Android rounds up the alignment to a power of two if it isn't one.
   if (SCUDO_ANDROID) {
     if (UNLIKELY(!alignment)) {
       alignment = 1U;
     } else {
       if (UNLIKELY(!scudo::isPowerOfTwo(alignment)))
         alignment = scudo::roundUpToPowerOfTwo(alignment);
     }
   } else {
     if (UNLIKELY(!scudo::isPowerOfTwo(alignment))) {
       if (SCUDO_ALLOCATOR.canReturnNull()) {
         errno = EINVAL;
         return nullptr;
       }
       scudo::reportAlignmentNotPowerOfTwo(alignment);
     }
   }
   return SCUDO_ALLOCATOR.allocate(size, scudo::Chunk::Origin::Memalign,
                                   alignment);
 }
 
 INTERFACE WEAK int SCUDO_PREFIX(posix_memalign)(void **memptr, size_t alignment,
                                                 size_t size) {
   if (UNLIKELY(scudo::checkPosixMemalignAlignment(alignment))) {
     if (!SCUDO_ALLOCATOR.canReturnNull())
       scudo::reportInvalidPosixMemalignAlignment(alignment);
     return EINVAL;
   }
   void *Ptr =
       SCUDO_ALLOCATOR.allocate(size, scudo::Chunk::Origin::Memalign, alignment);
   if (UNLIKELY(!Ptr))
     return ENOMEM;
   *memptr = Ptr;
   return 0;
 }
 
 INTERFACE WEAK void *SCUDO_PREFIX(pvalloc)(size_t size) {
   const scudo::uptr PageSize = scudo::getPageSizeCached();
   if (UNLIKELY(scudo::checkForPvallocOverflow(size, PageSize))) {
     if (SCUDO_ALLOCATOR.canReturnNull()) {
       errno = ENOMEM;
       return nullptr;
     }
     scudo::reportPvallocOverflow(size);
   }
   // pvalloc(0) should allocate one page.
   return scudo::setErrnoOnNull(SCUDO_ALLOCATOR.allocate(
       size ? scudo::roundUpTo(size, PageSize) : PageSize,
       scudo::Chunk::Origin::Memalign, PageSize));
 }
 
 INTERFACE WEAK void *SCUDO_PREFIX(realloc)(void *ptr, size_t size) {
   if (!ptr)
     return scudo::setErrnoOnNull(SCUDO_ALLOCATOR.allocate(
         size, scudo::Chunk::Origin::Malloc, SCUDO_MALLOC_ALIGNMENT));
   if (size == 0) {
     SCUDO_ALLOCATOR.deallocate(ptr, scudo::Chunk::Origin::Malloc);
     return nullptr;
   }
   return scudo::setErrnoOnNull(
       SCUDO_ALLOCATOR.reallocate(ptr, size, SCUDO_MALLOC_ALIGNMENT));
 }
 
 INTERFACE WEAK void *SCUDO_PREFIX(valloc)(size_t size) {
   return scudo::setErrnoOnNull(SCUDO_ALLOCATOR.allocate(
       size, scudo::Chunk::Origin::Memalign, scudo::getPageSizeCached()));
 }
 
 // Bionic wants a function named PREFIX_iterate and not PREFIX_malloc_iterate
 // which is somewhat inconsistent with the rest, workaround that.
 #if SCUDO_ANDROID && _BIONIC
 #define SCUDO_ITERATE iterate
 #else
 #define SCUDO_ITERATE malloc_iterate
 #endif
 
 INTERFACE WEAK int SCUDO_PREFIX(SCUDO_ITERATE)(
     uintptr_t base, size_t size,
     void (*callback)(uintptr_t base, size_t size, void *arg), void *arg) {
   SCUDO_ALLOCATOR.iterateOverChunks(base, size, callback, arg);
   return 0;
 }
 
 INTERFACE WEAK void SCUDO_PREFIX(malloc_disable)() {
   SCUDO_ALLOCATOR.disable();
 }
 
 INTERFACE WEAK void SCUDO_PREFIX(malloc_enable)() { SCUDO_ALLOCATOR.enable(); }
 
 INTERFACE WEAK int SCUDO_PREFIX(mallopt)(int param, UNUSED int value) {
   if (param == M_DECAY_TIME) {
     // TODO(kostyak): set release_to_os_interval_ms accordingly.
     return 1;
   } else if (param == M_PURGE) {
     SCUDO_ALLOCATOR.releaseToOS();
     return 1;
   }
   return 0;
 }
 
 INTERFACE WEAK void *SCUDO_PREFIX(aligned_alloc)(size_t alignment,
                                                  size_t size) {
   if (UNLIKELY(scudo::checkAlignedAllocAlignmentAndSize(alignment, size))) {
     if (SCUDO_ALLOCATOR.canReturnNull()) {
       errno = EINVAL;
       return nullptr;
     }
     scudo::reportInvalidAlignedAllocAlignment(alignment, size);
   }
   return scudo::setErrnoOnNull(
       SCUDO_ALLOCATOR.allocate(size, scudo::Chunk::Origin::Malloc, alignment));
 }
 
 INTERFACE WEAK int SCUDO_PREFIX(malloc_info)(int, FILE *) {
   errno = ENOTSUP;
   return -1;
 }
 

lib/scudo/standalone/wrappers_c_bionic.cc

 //===-- wrappers_c_bionic.cc ------------------------------------*- 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"
 
 // This is only used when compiled as part of Bionic.
 #if SCUDO_ANDROID && _BIONIC
 
 #include "allocator_config.h"
 #include "wrappers_c.h"
 #include "wrappers_c_checks.h"
 
 #include <stdint.h>
 #include <stdio.h>
 
 static scudo::Allocator<scudo::AndroidConfig> Allocator;
 static scudo::Allocator<scudo::AndroidSvelteConfig> SvelteAllocator;
 
 extern "C" {
 
 // Regular MallocDispatch definitions.
 #define SCUDO_PREFIX(name) CONCATENATE(scudo_, name)
 #define SCUDO_ALLOCATOR Allocator
 #include "wrappers_c.inc"
 #undef SCUDO_ALLOCATOR
 #undef SCUDO_PREFIX
 
 // Svelte MallocDispatch definitions.
 #define SCUDO_PREFIX(name) CONCATENATE(scudo_svelte_, name)
 #define SCUDO_ALLOCATOR SvelteAllocator
 #include "wrappers_c.inc"
 #undef SCUDO_ALLOCATOR
 #undef SCUDO_PREFIX
 
 // The following is the only function that will end up initializing both
 // allocators, which will result in a slight increase in memory footprint.
 INTERFACE void __scudo_print_stats(void) {
   Allocator.printStats();
   SvelteAllocator.printStats();
 }
 
 } // extern "C"
 
 #endif // SCUDO_ANDROID && _BIONIC
 

lib/scudo/standalone/wrappers_c_checks.h

 //===-- wrappers_c_checks.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_CHECKS_H_
 #define SCUDO_CHECKS_H_
 
 #include "common.h"
 
 #include <errno.h>
 
 namespace scudo {
 
 // A common errno setting logic shared by almost all Scudo C wrappers.
 INLINE void *setErrnoOnNull(void *Ptr) {
   if (UNLIKELY(!Ptr))
     errno = ENOMEM;
   return Ptr;
 }
 
 // Checks return true on failure.
 
 // Checks aligned_alloc() parameters, verifies that the alignment is a power of
 // two and that the size is a multiple of alignment.
 INLINE bool checkAlignedAllocAlignmentAndSize(uptr Alignment, uptr Size) {
   return Alignment == 0 || !isPowerOfTwo(Alignment) ||
          !isAligned(Size, Alignment);
 }
 
 // Checks posix_memalign() parameters, verifies that alignment is a power of two
 // and a multiple of sizeof(void *).
 INLINE bool checkPosixMemalignAlignment(uptr Alignment) {
   return Alignment == 0 || !isPowerOfTwo(Alignment) ||
          !isAligned(Alignment, sizeof(void *));
 }
 
 // Returns true if calloc(Size, N) overflows on Size*N calculation. The typical
 // way would be to check for (UINTPTR_MAX / Size) < N, but the division ends up
 // being very costly, so use a builtin supported by recent clang & GCC.
 INLINE bool checkForCallocOverflow(uptr Size, uptr N, uptr *Product) {
   return __builtin_umull_overflow(Size, N, Product);
 }
 
 // Returns true if the size passed to pvalloc overflows when rounded to the next
 // multiple of PageSize.
 INLINE bool checkForPvallocOverflow(uptr Size, uptr PageSize) {
   return roundUpTo(Size, PageSize) < Size;
 }
 
 } // namespace scudo
 
 #endif // SCUDO_CHECKS_H_
 

lib/scudo/standalone/wrappers_cpp.cc

 //===-- wrappers_cpp.cc -----------------------------------------*- 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"
 
 // Skip this compilation unit if compiled as part of Bionic.
 #if !SCUDO_ANDROID || !_BIONIC
 
 #include "allocator_config.h"
 
 #include <stdint.h>
 
 extern scudo::Allocator<scudo::Config> *AllocatorPtr;
 
 namespace std {
 struct nothrow_t {};
 enum class align_val_t : size_t {};
 } // namespace std
 
 INTERFACE WEAK void *operator new(size_t size) {
   return AllocatorPtr->allocate(size, scudo::Chunk::Origin::New);
 }
 INTERFACE WEAK void *operator new[](size_t size) {
   return AllocatorPtr->allocate(size, scudo::Chunk::Origin::NewArray);
 }
 INTERFACE WEAK void *operator new(size_t size,
                                   std::nothrow_t const &) NOEXCEPT {
   return AllocatorPtr->allocate(size, scudo::Chunk::Origin::New);
 }
 INTERFACE WEAK void *operator new[](size_t size,
                                     std::nothrow_t const &) NOEXCEPT {
   return AllocatorPtr->allocate(size, scudo::Chunk::Origin::NewArray);
 }
 INTERFACE WEAK void *operator new(size_t size, std::align_val_t align) {
   return AllocatorPtr->allocate(size, scudo::Chunk::Origin::New,
                                 static_cast<scudo::uptr>(align));
 }
 INTERFACE WEAK void *operator new[](size_t size, std::align_val_t align) {
   return AllocatorPtr->allocate(size, scudo::Chunk::Origin::NewArray,
                                 static_cast<scudo::uptr>(align));
 }
 INTERFACE WEAK void *operator new(size_t size, std::align_val_t align,
                                   std::nothrow_t const &) NOEXCEPT {
   return AllocatorPtr->allocate(size, scudo::Chunk::Origin::New,
                                 static_cast<scudo::uptr>(align));
 }
 INTERFACE WEAK void *operator new[](size_t size, std::align_val_t align,
                                     std::nothrow_t const &) NOEXCEPT {
   return AllocatorPtr->allocate(size, scudo::Chunk::Origin::NewArray,
                                 static_cast<scudo::uptr>(align));
 }
 
 INTERFACE WEAK void operator delete(void *ptr)NOEXCEPT {
   AllocatorPtr->deallocate(ptr, scudo::Chunk::Origin::New);
 }
 INTERFACE WEAK void operator delete[](void *ptr) NOEXCEPT {
   AllocatorPtr->deallocate(ptr, scudo::Chunk::Origin::NewArray);
 }
 INTERFACE WEAK void operator delete(void *ptr, std::nothrow_t const &)NOEXCEPT {
   AllocatorPtr->deallocate(ptr, scudo::Chunk::Origin::New);
 }
 INTERFACE WEAK void operator delete[](void *ptr,
                                       std::nothrow_t const &) NOEXCEPT {
   AllocatorPtr->deallocate(ptr, scudo::Chunk::Origin::NewArray);
 }
 INTERFACE WEAK void operator delete(void *ptr, size_t size)NOEXCEPT {
   AllocatorPtr->deallocate(ptr, scudo::Chunk::Origin::New, size);
 }
 INTERFACE WEAK void operator delete[](void *ptr, size_t size) NOEXCEPT {
   AllocatorPtr->deallocate(ptr, scudo::Chunk::Origin::NewArray, size);
 }
 INTERFACE WEAK void operator delete(void *ptr, std::align_val_t align)NOEXCEPT {
   AllocatorPtr->deallocate(ptr, scudo::Chunk::Origin::New, 0,
                            static_cast<scudo::uptr>(align));
 }
 INTERFACE WEAK void operator delete[](void *ptr,
                                       std::align_val_t align) NOEXCEPT {
   AllocatorPtr->deallocate(ptr, scudo::Chunk::Origin::NewArray, 0,
                            static_cast<scudo::uptr>(align));
 }
 INTERFACE WEAK void operator delete(void *ptr, std::align_val_t align,
                                     std::nothrow_t const &)NOEXCEPT {
   AllocatorPtr->deallocate(ptr, scudo::Chunk::Origin::New, 0,
                            static_cast<scudo::uptr>(align));
 }
 INTERFACE WEAK void operator delete[](void *ptr, std::align_val_t align,
                                       std::nothrow_t const &) NOEXCEPT {
   AllocatorPtr->deallocate(ptr, scudo::Chunk::Origin::NewArray, 0,
                            static_cast<scudo::uptr>(align));
 }
 INTERFACE WEAK void operator delete(void *ptr, size_t size,
                                     std::align_val_t align)NOEXCEPT {
   AllocatorPtr->deallocate(ptr, scudo::Chunk::Origin::New, size,
                            static_cast<scudo::uptr>(align));
 }
 INTERFACE WEAK void operator delete[](void *ptr, size_t size,
                                       std::align_val_t align) NOEXCEPT {
   AllocatorPtr->deallocate(ptr, scudo::Chunk::Origin::NewArray, size,
                            static_cast<scudo::uptr>(align));
 }
 
 #endif // !SCUDO_ANDROID || !_BIONIC