1 // Copyright 2019 The Chromium Authors
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/android/reached_addresses_bitset.h"
6
7 #include "base/android/library_loader/anchor_functions.h"
8 #include "base/android/library_loader/anchor_functions_buildflags.h"
9 #include "base/check_op.h"
10 #include "base/numerics/safe_conversions.h"
11
12 namespace base {
13 namespace android {
14
15 namespace {
16 constexpr size_t kBitsPerElement = sizeof(uint32_t) * 8;
17
18 // Below an array of uint32_t in BSS is introduced and then casted to an array
19 // of std::atomic<uint32_t>. In C++20 constructing an std::atomic is not
20 // 'trivial'. See https://github.com/microsoft/STL/issues/661 for reasons of
21 // this change in the standard.
22 //
23 // Assert that both types have the same size. The sizes do not have to match
24 // according to a note in [atomics.types.generic] in C++17. With this assertion
25 // in place it is unlikely that the constructor produces the value other than
26 // (uint32_t)0.
27 static_assert(sizeof(uint32_t) == sizeof(std::atomic<uint32_t>), "");
28
29 // Keep the array in BSS only for non-official builds to avoid potential harm to
30 // data locality and unspecified behavior from the reinterpret_cast below.
31 // In order to start new experiments with base::Feature(ReachedCodeProfiler) on
32 // Canary/Dev this array will need to be reintroduced to official builds. When
33 // doing so, don't forget to update `kConfigurationSupported` in
34 // `reached_code_profiler.cc`
35 #if BUILDFLAG(SUPPORTS_CODE_ORDERING) && !defined(OFFICIAL_BUILD)
36 // Enough for 1 << 29 bytes of code, 512MB.
37 constexpr size_t kTextBitfieldSize = 1 << 20;
38 uint32_t g_text_bitfield[kTextBitfieldSize];
39 #endif
40 } // namespace
41
42 // static
GetTextBitset()43 ReachedAddressesBitset* ReachedAddressesBitset::GetTextBitset() {
44 #if BUILDFLAG(SUPPORTS_CODE_ORDERING) && !defined(OFFICIAL_BUILD)
45 static ReachedAddressesBitset text_bitset(
46 kStartOfText, kEndOfText,
47 reinterpret_cast<std::atomic<uint32_t>*>(g_text_bitfield),
48 kTextBitfieldSize);
49 return &text_bitset;
50 #else
51 return nullptr;
52 #endif
53 }
54
RecordAddress(uintptr_t address)55 void ReachedAddressesBitset::RecordAddress(uintptr_t address) {
56 // |address| is outside of the range.
57 if (address < start_address_ || address >= end_address_)
58 return;
59
60 size_t offset = static_cast<size_t>(address - start_address_);
61 uint32_t offset_index = checked_cast<uint32_t>(offset / kBytesGranularity);
62
63 // Atomically set the corresponding bit in the array.
64 std::atomic<uint32_t>* element = reached_ + (offset_index / kBitsPerElement);
65
66 // First, a racy check. This saves a CAS if the bit is already set, and
67 // allows the cache line to remain shared across CPUs in this case.
68 uint32_t value = element->load(std::memory_order_relaxed);
69 uint32_t mask = 1 << (offset_index % kBitsPerElement);
70 if (value & mask)
71 return;
72 element->fetch_or(mask, std::memory_order_relaxed);
73 }
74
GetReachedOffsets() const75 std::vector<uint32_t> ReachedAddressesBitset::GetReachedOffsets() const {
76 std::vector<uint32_t> offsets;
77 const size_t elements = NumberOfReachableElements();
78
79 for (size_t i = 0; i < elements; ++i) {
80 uint32_t element = reached_[i].load(std::memory_order_relaxed);
81 // No reached addresses at this element.
82 if (element == 0)
83 continue;
84
85 for (size_t j = 0; j < 32; ++j) {
86 if (!((element >> j) & 1))
87 continue;
88
89 size_t offset_index = i * 32 + j;
90 size_t offset = offset_index * kBytesGranularity;
91 offsets.push_back(checked_cast<uint32_t>(offset));
92 }
93 }
94
95 return offsets;
96 }
97
ReachedAddressesBitset(uintptr_t start_address,uintptr_t end_address,std::atomic<uint32_t> * storage_ptr,size_t storage_size)98 ReachedAddressesBitset::ReachedAddressesBitset(
99 uintptr_t start_address,
100 uintptr_t end_address,
101 std::atomic<uint32_t>* storage_ptr,
102 size_t storage_size)
103 : start_address_(start_address),
104 end_address_(end_address),
105 reached_(storage_ptr) {
106 DCHECK_LE(start_address_, end_address_);
107 DCHECK_LE(NumberOfReachableElements(), storage_size * kBitsPerElement);
108 }
109
NumberOfReachableElements() const110 size_t ReachedAddressesBitset::NumberOfReachableElements() const {
111 size_t reachable_bits =
112 (end_address_ + kBytesGranularity - 1) / kBytesGranularity -
113 start_address_ / kBytesGranularity;
114 return (reachable_bits + kBitsPerElement - 1) / kBitsPerElement;
115 }
116
117 } // namespace android
118 } // namespace base
119