base/android/reached_addresses_bitset.cc

   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
  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
  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
  75 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
  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
 110 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