1// Copyright 2014 The Chromium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "base/threading/thread_local_storage.h"
6
7#include "base/atomicops.h"
8#include "base/logging.h"
9#include "base/synchronization/lock.h"
10#include "build/build_config.h"
11
12using base::internal::PlatformThreadLocalStorage;
13
14// Chrome Thread Local Storage (TLS)
15//
16// This TLS system allows Chrome to use a single OS level TLS slot process-wide,
17// and allows us to control the slot limits instead of being at the mercy of the
18// platform. To do this, Chrome TLS replicates an array commonly found in the OS
19// thread metadata.
20//
21// Overview:
22//
23// OS TLS Slots       Per-Thread                 Per-Process Global
24//     ...
25//     []             Chrome TLS Array           Chrome TLS Metadata
26//     [] ----------> [][][][][ ][][][][]        [][][][][ ][][][][]
27//     []                      |                          |
28//     ...                     V                          V
29//                      Metadata Version           Slot Information
30//                         Your Data!
31//
32// Using a single OS TLS slot, Chrome TLS allocates an array on demand for the
33// lifetime of each thread that requests Chrome TLS data. Each per-thread TLS
34// array matches the length of the per-process global metadata array.
35//
36// A per-process global TLS metadata array tracks information about each item in
37// the per-thread array:
38//   * Status: Tracks if the slot is allocated or free to assign.
39//   * Destructor: An optional destructor to call on thread destruction for that
40//                 specific slot.
41//   * Version: Tracks the current version of the TLS slot. Each TLS slot
42//              allocation is associated with a unique version number.
43//
44//              Most OS TLS APIs guarantee that a newly allocated TLS slot is
45//              initialized to 0 for all threads. The Chrome TLS system provides
46//              this guarantee by tracking the version for each TLS slot here
47//              on each per-thread Chrome TLS array entry. Threads that access
48//              a slot with a mismatched version will receive 0 as their value.
49//              The metadata version is incremented when the client frees a
50//              slot. The per-thread metadata version is updated when a client
51//              writes to the slot. This scheme allows for constant time
52//              invalidation and avoids the need to iterate through each Chrome
53//              TLS array to mark the slot as zero.
54//
55// Just like an OS TLS API, clients of the Chrome TLS are responsible for
56// managing any necessary lifetime of the data in their slots. The only
57// convenience provided is automatic destruction when a thread ends. If a client
58// frees a slot, that client is responsible for destroying the data in the slot.
59
60namespace {
61// In order to make TLS destructors work, we need to keep around a function
62// pointer to the destructor for each slot. We keep this array of pointers in a
63// global (static) array.
64// We use the single OS-level TLS slot (giving us one pointer per thread) to
65// hold a pointer to a per-thread array (table) of slots that we allocate to
66// Chromium consumers.
67
68// g_native_tls_key is the one native TLS that we use. It stores our table.
69base::subtle::Atomic32 g_native_tls_key =
70    PlatformThreadLocalStorage::TLS_KEY_OUT_OF_INDEXES;
71
72// The maximum number of slots in our thread local storage stack.
73constexpr int kThreadLocalStorageSize = 256;
74constexpr int kInvalidSlotValue = -1;
75
76enum TlsStatus {
77  FREE,
78  IN_USE,
79};
80
81struct TlsMetadata {
82  TlsStatus status;
83  base::ThreadLocalStorage::TLSDestructorFunc destructor;
84  uint32_t version;
85};
86
87struct TlsVectorEntry {
88  void* data;
89  uint32_t version;
90};
91
92// This lock isn't needed until after we've constructed the per-thread TLS
93// vector, so it's safe to use.
94base::Lock* GetTLSMetadataLock() {
95  static auto* lock = new base::Lock();
96  return lock;
97}
98TlsMetadata g_tls_metadata[kThreadLocalStorageSize];
99size_t g_last_assigned_slot = 0;
100
101// The maximum number of times to try to clear slots by calling destructors.
102// Use pthread naming convention for clarity.
103constexpr int kMaxDestructorIterations = kThreadLocalStorageSize;
104
105// This function is called to initialize our entire Chromium TLS system.
106// It may be called very early, and we need to complete most all of the setup
107// (initialization) before calling *any* memory allocator functions, which may
108// recursively depend on this initialization.
109// As a result, we use Atomics, and avoid anything (like a singleton) that might
110// require memory allocations.
111TlsVectorEntry* ConstructTlsVector() {
112  PlatformThreadLocalStorage::TLSKey key =
113      base::subtle::NoBarrier_Load(&g_native_tls_key);
114  if (key == PlatformThreadLocalStorage::TLS_KEY_OUT_OF_INDEXES) {
115    CHECK(PlatformThreadLocalStorage::AllocTLS(&key));
116
117    // The TLS_KEY_OUT_OF_INDEXES is used to find out whether the key is set or
118    // not in NoBarrier_CompareAndSwap, but Posix doesn't have invalid key, we
119    // define an almost impossible value be it.
120    // If we really get TLS_KEY_OUT_OF_INDEXES as value of key, just alloc
121    // another TLS slot.
122    if (key == PlatformThreadLocalStorage::TLS_KEY_OUT_OF_INDEXES) {
123      PlatformThreadLocalStorage::TLSKey tmp = key;
124      CHECK(PlatformThreadLocalStorage::AllocTLS(&key) &&
125            key != PlatformThreadLocalStorage::TLS_KEY_OUT_OF_INDEXES);
126      PlatformThreadLocalStorage::FreeTLS(tmp);
127    }
128    // Atomically test-and-set the tls_key. If the key is
129    // TLS_KEY_OUT_OF_INDEXES, go ahead and set it. Otherwise, do nothing, as
130    // another thread already did our dirty work.
131    if (PlatformThreadLocalStorage::TLS_KEY_OUT_OF_INDEXES !=
132        static_cast<PlatformThreadLocalStorage::TLSKey>(
133            base::subtle::NoBarrier_CompareAndSwap(
134                &g_native_tls_key,
135                PlatformThreadLocalStorage::TLS_KEY_OUT_OF_INDEXES, key))) {
136      // We've been shortcut. Another thread replaced g_native_tls_key first so
137      // we need to destroy our index and use the one the other thread got
138      // first.
139      PlatformThreadLocalStorage::FreeTLS(key);
140      key = base::subtle::NoBarrier_Load(&g_native_tls_key);
141    }
142  }
143  CHECK(!PlatformThreadLocalStorage::GetTLSValue(key));
144
145  // Some allocators, such as TCMalloc, make use of thread local storage. As a
146  // result, any attempt to call new (or malloc) will lazily cause such a system
147  // to initialize, which will include registering for a TLS key. If we are not
148  // careful here, then that request to create a key will call new back, and
149  // we'll have an infinite loop. We avoid that as follows: Use a stack
150  // allocated vector, so that we don't have dependence on our allocator until
151  // our service is in place. (i.e., don't even call new until after we're
152  // setup)
153  TlsVectorEntry stack_allocated_tls_data[kThreadLocalStorageSize];
154  memset(stack_allocated_tls_data, 0, sizeof(stack_allocated_tls_data));
155  // Ensure that any rentrant calls change the temp version.
156  PlatformThreadLocalStorage::SetTLSValue(key, stack_allocated_tls_data);
157
158  // Allocate an array to store our data.
159  TlsVectorEntry* tls_data = new TlsVectorEntry[kThreadLocalStorageSize];
160  memcpy(tls_data, stack_allocated_tls_data, sizeof(stack_allocated_tls_data));
161  PlatformThreadLocalStorage::SetTLSValue(key, tls_data);
162  return tls_data;
163}
164
165void OnThreadExitInternal(TlsVectorEntry* tls_data) {
166  DCHECK(tls_data);
167  // Some allocators, such as TCMalloc, use TLS. As a result, when a thread
168  // terminates, one of the destructor calls we make may be to shut down an
169  // allocator. We have to be careful that after we've shutdown all of the known
170  // destructors (perchance including an allocator), that we don't call the
171  // allocator and cause it to resurrect itself (with no possibly destructor
172  // call to follow). We handle this problem as follows: Switch to using a stack
173  // allocated vector, so that we don't have dependence on our allocator after
174  // we have called all g_tls_metadata destructors. (i.e., don't even call
175  // delete[] after we're done with destructors.)
176  TlsVectorEntry stack_allocated_tls_data[kThreadLocalStorageSize];
177  memcpy(stack_allocated_tls_data, tls_data, sizeof(stack_allocated_tls_data));
178  // Ensure that any re-entrant calls change the temp version.
179  PlatformThreadLocalStorage::TLSKey key =
180      base::subtle::NoBarrier_Load(&g_native_tls_key);
181  PlatformThreadLocalStorage::SetTLSValue(key, stack_allocated_tls_data);
182  delete[] tls_data;  // Our last dependence on an allocator.
183
184  // Snapshot the TLS Metadata so we don't have to lock on every access.
185  TlsMetadata tls_metadata[kThreadLocalStorageSize];
186  {
187    base::AutoLock auto_lock(*GetTLSMetadataLock());
188    memcpy(tls_metadata, g_tls_metadata, sizeof(g_tls_metadata));
189  }
190
191  int remaining_attempts = kMaxDestructorIterations;
192  bool need_to_scan_destructors = true;
193  while (need_to_scan_destructors) {
194    need_to_scan_destructors = false;
195    // Try to destroy the first-created-slot (which is slot 1) in our last
196    // destructor call. That user was able to function, and define a slot with
197    // no other services running, so perhaps it is a basic service (like an
198    // allocator) and should also be destroyed last. If we get the order wrong,
199    // then we'll iterate several more times, so it is really not that critical
200    // (but it might help).
201    for (int slot = 0; slot < kThreadLocalStorageSize ; ++slot) {
202      void* tls_value = stack_allocated_tls_data[slot].data;
203      if (!tls_value || tls_metadata[slot].status == TlsStatus::FREE ||
204          stack_allocated_tls_data[slot].version != tls_metadata[slot].version)
205        continue;
206
207      base::ThreadLocalStorage::TLSDestructorFunc destructor =
208          tls_metadata[slot].destructor;
209      if (!destructor)
210        continue;
211      stack_allocated_tls_data[slot].data = nullptr;  // pre-clear the slot.
212      destructor(tls_value);
213      // Any destructor might have called a different service, which then set a
214      // different slot to a non-null value. Hence we need to check the whole
215      // vector again. This is a pthread standard.
216      need_to_scan_destructors = true;
217    }
218    if (--remaining_attempts <= 0) {
219      NOTREACHED();  // Destructors might not have been called.
220      break;
221    }
222  }
223
224  // Remove our stack allocated vector.
225  PlatformThreadLocalStorage::SetTLSValue(key, nullptr);
226}
227
228}  // namespace
229
230namespace base {
231
232namespace internal {
233
234#if defined(OS_WIN)
235void PlatformThreadLocalStorage::OnThreadExit() {
236  PlatformThreadLocalStorage::TLSKey key =
237      base::subtle::NoBarrier_Load(&g_native_tls_key);
238  if (key == PlatformThreadLocalStorage::TLS_KEY_OUT_OF_INDEXES)
239    return;
240  void *tls_data = GetTLSValue(key);
241  // Maybe we have never initialized TLS for this thread.
242  if (!tls_data)
243    return;
244  OnThreadExitInternal(static_cast<TlsVectorEntry*>(tls_data));
245}
246#elif defined(OS_POSIX)
247void PlatformThreadLocalStorage::OnThreadExit(void* value) {
248  OnThreadExitInternal(static_cast<TlsVectorEntry*>(value));
249}
250#endif  // defined(OS_WIN)
251
252}  // namespace internal
253
254void ThreadLocalStorage::StaticSlot::Initialize(TLSDestructorFunc destructor) {
255  PlatformThreadLocalStorage::TLSKey key =
256      base::subtle::NoBarrier_Load(&g_native_tls_key);
257  if (key == PlatformThreadLocalStorage::TLS_KEY_OUT_OF_INDEXES ||
258      !PlatformThreadLocalStorage::GetTLSValue(key)) {
259    ConstructTlsVector();
260  }
261
262  // Grab a new slot.
263  slot_ = kInvalidSlotValue;
264  version_ = 0;
265  {
266    base::AutoLock auto_lock(*GetTLSMetadataLock());
267    for (int i = 0; i < kThreadLocalStorageSize; ++i) {
268      // Tracking the last assigned slot is an attempt to find the next
269      // available slot within one iteration. Under normal usage, slots remain
270      // in use for the lifetime of the process (otherwise before we reclaimed
271      // slots, we would have run out of slots). This makes it highly likely the
272      // next slot is going to be a free slot.
273      size_t slot_candidate =
274          (g_last_assigned_slot + 1 + i) % kThreadLocalStorageSize;
275      if (g_tls_metadata[slot_candidate].status == TlsStatus::FREE) {
276        g_tls_metadata[slot_candidate].status = TlsStatus::IN_USE;
277        g_tls_metadata[slot_candidate].destructor = destructor;
278        g_last_assigned_slot = slot_candidate;
279        slot_ = slot_candidate;
280        version_ = g_tls_metadata[slot_candidate].version;
281        break;
282      }
283    }
284  }
285  CHECK_NE(slot_, kInvalidSlotValue);
286  CHECK_LT(slot_, kThreadLocalStorageSize);
287
288  // Setup our destructor.
289  base::subtle::Release_Store(&initialized_, 1);
290}
291
292void ThreadLocalStorage::StaticSlot::Free() {
293  DCHECK_NE(slot_, kInvalidSlotValue);
294  DCHECK_LT(slot_, kThreadLocalStorageSize);
295  {
296    base::AutoLock auto_lock(*GetTLSMetadataLock());
297    g_tls_metadata[slot_].status = TlsStatus::FREE;
298    g_tls_metadata[slot_].destructor = nullptr;
299    ++(g_tls_metadata[slot_].version);
300  }
301  slot_ = kInvalidSlotValue;
302  base::subtle::Release_Store(&initialized_, 0);
303}
304
305void* ThreadLocalStorage::StaticSlot::Get() const {
306  TlsVectorEntry* tls_data = static_cast<TlsVectorEntry*>(
307      PlatformThreadLocalStorage::GetTLSValue(
308          base::subtle::NoBarrier_Load(&g_native_tls_key)));
309  if (!tls_data)
310    tls_data = ConstructTlsVector();
311  DCHECK_NE(slot_, kInvalidSlotValue);
312  DCHECK_LT(slot_, kThreadLocalStorageSize);
313  // Version mismatches means this slot was previously freed.
314  if (tls_data[slot_].version != version_)
315    return nullptr;
316  return tls_data[slot_].data;
317}
318
319void ThreadLocalStorage::StaticSlot::Set(void* value) {
320  TlsVectorEntry* tls_data = static_cast<TlsVectorEntry*>(
321      PlatformThreadLocalStorage::GetTLSValue(
322          base::subtle::NoBarrier_Load(&g_native_tls_key)));
323  if (!tls_data)
324    tls_data = ConstructTlsVector();
325  DCHECK_NE(slot_, kInvalidSlotValue);
326  DCHECK_LT(slot_, kThreadLocalStorageSize);
327  tls_data[slot_].data = value;
328  tls_data[slot_].version = version_;
329}
330
331ThreadLocalStorage::Slot::Slot(TLSDestructorFunc destructor) {
332  tls_slot_.Initialize(destructor);
333}
334
335ThreadLocalStorage::Slot::~Slot() {
336  tls_slot_.Free();
337}
338
339void* ThreadLocalStorage::Slot::Get() const {
340  return tls_slot_.Get();
341}
342
343void ThreadLocalStorage::Slot::Set(void* value) {
344  tls_slot_.Set(value);
345}
346
347}  // namespace base
348