1 //===-- tsd_shared.h --------------------------------------------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #ifndef SCUDO_TSD_SHARED_H_ 10 #define SCUDO_TSD_SHARED_H_ 11 12 #include "linux.h" // for getAndroidTlsPtr() 13 #include "tsd.h" 14 15 #include <pthread.h> 16 17 namespace scudo { 18 19 template <class Allocator, u32 MaxTSDCount> struct TSDRegistrySharedT { 20 void initLinkerInitialized(Allocator *Instance) { 21 Instance->initLinkerInitialized(); 22 CHECK_EQ(pthread_key_create(&PThreadKey, nullptr), 0); // For non-TLS 23 NumberOfTSDs = Min(Max(1U, getNumberOfCPUs()), MaxTSDCount); 24 TSDs = reinterpret_cast<TSD<Allocator> *>( 25 map(nullptr, sizeof(TSD<Allocator>) * NumberOfTSDs, "scudo:tsd")); 26 for (u32 I = 0; I < NumberOfTSDs; I++) 27 TSDs[I].initLinkerInitialized(Instance); 28 // Compute all the coprimes of NumberOfTSDs. This will be used to walk the 29 // array of TSDs in a random order. For details, see: 30 // https://lemire.me/blog/2017/09/18/visiting-all-values-in-an-array-exactly-once-in-random-order/ 31 for (u32 I = 0; I < NumberOfTSDs; I++) { 32 u32 A = I + 1; 33 u32 B = NumberOfTSDs; 34 // Find the GCD between I + 1 and NumberOfTSDs. If 1, they are coprimes. 35 while (B != 0) { 36 const u32 T = A; 37 A = B; 38 B = T % B; 39 } 40 if (A == 1) 41 CoPrimes[NumberOfCoPrimes++] = I + 1; 42 } 43 Initialized = true; 44 } 45 void init(Allocator *Instance) { 46 memset(this, 0, sizeof(*this)); 47 initLinkerInitialized(Instance); 48 } 49 50 void unmapTestOnly() { 51 unmap(reinterpret_cast<void *>(TSDs), 52 sizeof(TSD<Allocator>) * NumberOfTSDs); 53 } 54 55 ALWAYS_INLINE void initThreadMaybe(Allocator *Instance, 56 UNUSED bool MinimalInit) { 57 if (LIKELY(getCurrentTSD())) 58 return; 59 initThread(Instance); 60 } 61 62 ALWAYS_INLINE TSD<Allocator> *getTSDAndLock(bool *UnlockRequired) { 63 TSD<Allocator> *TSD = getCurrentTSD(); 64 DCHECK(TSD); 65 *UnlockRequired = true; 66 // Try to lock the currently associated context. 67 if (TSD->tryLock()) 68 return TSD; 69 // If that fails, go down the slow path. 70 return getTSDAndLockSlow(TSD); 71 } 72 73 private: 74 ALWAYS_INLINE void setCurrentTSD(TSD<Allocator> *CurrentTSD) { 75 #if SCUDO_ANDROID 76 *getAndroidTlsPtr() = reinterpret_cast<uptr>(CurrentTSD); 77 #elif SCUDO_LINUX 78 ThreadTSD = CurrentTSD; 79 #else 80 CHECK_EQ( 81 pthread_setspecific(PThreadKey, reinterpret_cast<void *>(CurrentTSD)), 82 0); 83 #endif 84 } 85 86 ALWAYS_INLINE TSD<Allocator> *getCurrentTSD() { 87 #if SCUDO_ANDROID 88 return reinterpret_cast<TSD<Allocator> *>(*getAndroidTlsPtr()); 89 #elif SCUDO_LINUX 90 return ThreadTSD; 91 #else 92 return reinterpret_cast<TSD<Allocator> *>(pthread_getspecific(PThreadKey)); 93 #endif 94 } 95 96 void initOnceMaybe(Allocator *Instance) { 97 ScopedLock L(Mutex); 98 if (Initialized) 99 return; 100 initLinkerInitialized(Instance); // Sets Initialized. 101 } 102 103 NOINLINE void initThread(Allocator *Instance) { 104 initOnceMaybe(Instance); 105 // Initial context assignment is done in a plain round-robin fashion. 106 const u32 Index = atomic_fetch_add(&CurrentIndex, 1U, memory_order_relaxed); 107 setCurrentTSD(&TSDs[Index % NumberOfTSDs]); 108 } 109 110 NOINLINE TSD<Allocator> *getTSDAndLockSlow(TSD<Allocator> *CurrentTSD) { 111 if (MaxTSDCount > 1U && NumberOfTSDs > 1U) { 112 // Use the Precedence of the current TSD as our random seed. Since we are 113 // in the slow path, it means that tryLock failed, and as a result it's 114 // very likely that said Precedence is non-zero. 115 u32 RandState = static_cast<u32>(CurrentTSD->getPrecedence()); 116 const u32 R = getRandomU32(&RandState); 117 const u32 Inc = CoPrimes[R % NumberOfCoPrimes]; 118 u32 Index = R % NumberOfTSDs; 119 uptr LowestPrecedence = UINTPTR_MAX; 120 TSD<Allocator> *CandidateTSD = nullptr; 121 // Go randomly through at most 4 contexts and find a candidate. 122 for (u32 I = 0; I < Min(4U, NumberOfTSDs); I++) { 123 if (TSDs[Index].tryLock()) { 124 setCurrentTSD(&TSDs[Index]); 125 return &TSDs[Index]; 126 } 127 const uptr Precedence = TSDs[Index].getPrecedence(); 128 // A 0 precedence here means another thread just locked this TSD. 129 if (Precedence && Precedence < LowestPrecedence) { 130 CandidateTSD = &TSDs[Index]; 131 LowestPrecedence = Precedence; 132 } 133 Index += Inc; 134 if (Index >= NumberOfTSDs) 135 Index -= NumberOfTSDs; 136 } 137 if (CandidateTSD) { 138 CandidateTSD->lock(); 139 setCurrentTSD(CandidateTSD); 140 return CandidateTSD; 141 } 142 } 143 // Last resort, stick with the current one. 144 CurrentTSD->lock(); 145 return CurrentTSD; 146 } 147 148 pthread_key_t PThreadKey; 149 atomic_u32 CurrentIndex; 150 u32 NumberOfTSDs; 151 TSD<Allocator> *TSDs; 152 u32 NumberOfCoPrimes; 153 u32 CoPrimes[MaxTSDCount]; 154 bool Initialized; 155 HybridMutex Mutex; 156 #if SCUDO_LINUX && !SCUDO_ANDROID 157 static THREADLOCAL TSD<Allocator> *ThreadTSD; 158 #endif 159 }; 160 161 #if SCUDO_LINUX && !SCUDO_ANDROID 162 template <class Allocator, u32 MaxTSDCount> 163 THREADLOCAL TSD<Allocator> 164 *TSDRegistrySharedT<Allocator, MaxTSDCount>::ThreadTSD; 165 #endif 166 167 } // namespace scudo 168 169 #endif // SCUDO_TSD_SHARED_H_ 170