1//===-- scudo_tsd_shared.cpp ------------------------------------*- 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/// Scudo shared TSD implementation.
10///
11//===----------------------------------------------------------------------===//
12
13#include "scudo_tsd.h"
14
15#if !SCUDO_TSD_EXCLUSIVE
16
17namespace __scudo {
18
19static pthread_once_t GlobalInitialized = PTHREAD_ONCE_INIT;
20pthread_key_t PThreadKey;
21
22static atomic_uint32_t CurrentIndex;
23static ScudoTSD *TSDs;
24static u32 NumberOfTSDs;
25static u32 CoPrimes[SCUDO_SHARED_TSD_POOL_SIZE];
26static u32 NumberOfCoPrimes = 0;
27
28#if SANITIZER_LINUX && !SANITIZER_ANDROID
29__attribute__((tls_model("initial-exec")))
30THREADLOCAL ScudoTSD *CurrentTSD;
31#endif
32
33static void initOnce() {
34  CHECK_EQ(pthread_key_create(&PThreadKey, NULL), 0);
35  initScudo();
36  NumberOfTSDs = Min(Max(1U, GetNumberOfCPUsCached()),
37                     static_cast<u32>(SCUDO_SHARED_TSD_POOL_SIZE));
38  TSDs = reinterpret_cast<ScudoTSD *>(
39      MmapOrDie(sizeof(ScudoTSD) * NumberOfTSDs, "ScudoTSDs"));
40  for (u32 I = 0; I < NumberOfTSDs; I++) {
41    TSDs[I].init();
42    u32 A = I + 1;
43    u32 B = NumberOfTSDs;
44    while (B != 0) { const u32 T = A; A = B; B = T % B; }
45    if (A == 1)
46      CoPrimes[NumberOfCoPrimes++] = I + 1;
47  }
48}
49
50ALWAYS_INLINE void setCurrentTSD(ScudoTSD *TSD) {
51#if SANITIZER_ANDROID
52  *get_android_tls_ptr() = reinterpret_cast<uptr>(TSD);
53#elif SANITIZER_LINUX
54  CurrentTSD = TSD;
55#else
56  CHECK_EQ(pthread_setspecific(PThreadKey, reinterpret_cast<void *>(TSD)), 0);
57#endif  // SANITIZER_ANDROID
58}
59
60void initThread(bool MinimalInit) {
61  pthread_once(&GlobalInitialized, initOnce);
62  // Initial context assignment is done in a plain round-robin fashion.
63  u32 Index = atomic_fetch_add(&CurrentIndex, 1, memory_order_relaxed);
64  setCurrentTSD(&TSDs[Index % NumberOfTSDs]);
65}
66
67ScudoTSD *getTSDAndLockSlow(ScudoTSD *TSD) {
68  if (NumberOfTSDs > 1) {
69    // Use the Precedence of the current TSD as our random seed. Since we are in
70    // the slow path, it means that tryLock failed, and as a result it's very
71    // likely that said Precedence is non-zero.
72    u32 RandState = static_cast<u32>(TSD->getPrecedence());
73    const u32 R = Rand(&RandState);
74    const u32 Inc = CoPrimes[R % NumberOfCoPrimes];
75    u32 Index = R % NumberOfTSDs;
76    uptr LowestPrecedence = UINTPTR_MAX;
77    ScudoTSD *CandidateTSD = nullptr;
78    // Go randomly through at most 4 contexts and find a candidate.
79    for (u32 I = 0; I < Min(4U, NumberOfTSDs); I++) {
80      if (TSDs[Index].tryLock()) {
81        setCurrentTSD(&TSDs[Index]);
82        return &TSDs[Index];
83      }
84      const uptr Precedence = TSDs[Index].getPrecedence();
85      // A 0 precedence here means another thread just locked this TSD.
86      if (Precedence && Precedence < LowestPrecedence) {
87        CandidateTSD = &TSDs[Index];
88        LowestPrecedence = Precedence;
89      }
90      Index += Inc;
91      if (Index >= NumberOfTSDs)
92        Index -= NumberOfTSDs;
93    }
94    if (CandidateTSD) {
95      CandidateTSD->lock();
96      setCurrentTSD(CandidateTSD);
97      return CandidateTSD;
98    }
99  }
100  // Last resort, stick with the current one.
101  TSD->lock();
102  return TSD;
103}
104
105}  // namespace __scudo
106
107#endif  // !SCUDO_TSD_EXCLUSIVE
108