| // Copyright 2021 The Chromium Authors |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #include "base/allocator/partition_allocator/starscan/pcscan_internal.h" |
| |
| #include <algorithm> |
| #include <array> |
| #include <chrono> |
| #include <condition_variable> |
| #include <cstdint> |
| #include <mutex> |
| #include <numeric> |
| #include <set> |
| #include <thread> |
| #include <type_traits> |
| #include <unordered_map> |
| #include <vector> |
| |
| #include "base/allocator/partition_allocator/address_pool_manager.h" |
| #include "base/allocator/partition_allocator/address_pool_manager_bitmap.h" |
| #include "base/allocator/partition_allocator/allocation_guard.h" |
| #include "base/allocator/partition_allocator/page_allocator.h" |
| #include "base/allocator/partition_allocator/page_allocator_constants.h" |
| #include "base/allocator/partition_allocator/partition_address_space.h" |
| #include "base/allocator/partition_allocator/partition_alloc.h" |
| #include "base/allocator/partition_allocator/partition_alloc_base/bits.h" |
| #include "base/allocator/partition_allocator/partition_alloc_base/compiler_specific.h" |
| #include "base/allocator/partition_allocator/partition_alloc_base/cpu.h" |
| #include "base/allocator/partition_allocator/partition_alloc_base/debug/alias.h" |
| #include "base/allocator/partition_allocator/partition_alloc_base/immediate_crash.h" |
| #include "base/allocator/partition_allocator/partition_alloc_base/memory/ref_counted.h" |
| #include "base/allocator/partition_allocator/partition_alloc_base/memory/scoped_refptr.h" |
| #include "base/allocator/partition_allocator/partition_alloc_base/no_destructor.h" |
| #include "base/allocator/partition_allocator/partition_alloc_base/threading/platform_thread.h" |
| #include "base/allocator/partition_allocator/partition_alloc_base/time/time.h" |
| #include "base/allocator/partition_allocator/partition_alloc_check.h" |
| #include "base/allocator/partition_allocator/partition_alloc_config.h" |
| #include "base/allocator/partition_allocator/partition_alloc_constants.h" |
| #include "base/allocator/partition_allocator/partition_page.h" |
| #include "base/allocator/partition_allocator/reservation_offset_table.h" |
| #include "base/allocator/partition_allocator/starscan/metadata_allocator.h" |
| #include "base/allocator/partition_allocator/starscan/pcscan_scheduling.h" |
| #include "base/allocator/partition_allocator/starscan/raceful_worklist.h" |
| #include "base/allocator/partition_allocator/starscan/scan_loop.h" |
| #include "base/allocator/partition_allocator/starscan/snapshot.h" |
| #include "base/allocator/partition_allocator/starscan/stack/stack.h" |
| #include "base/allocator/partition_allocator/starscan/stats_collector.h" |
| #include "base/allocator/partition_allocator/starscan/stats_reporter.h" |
| #include "base/allocator/partition_allocator/tagging.h" |
| #include "base/allocator/partition_allocator/thread_cache.h" |
| #include "build/build_config.h" |
| |
| #if PA_CONFIG(STARSCAN_NOINLINE_SCAN_FUNCTIONS) |
| #define PA_SCAN_INLINE PA_NOINLINE |
| #else |
| #define PA_SCAN_INLINE PA_ALWAYS_INLINE |
| #endif |
| |
| namespace partition_alloc::internal { |
| |
| [[noreturn]] PA_NOINLINE PA_NOT_TAIL_CALLED void DoubleFreeAttempt() { |
| PA_NO_CODE_FOLDING(); |
| PA_IMMEDIATE_CRASH(); |
| } |
| |
| namespace { |
| |
| #if PA_CONFIG(HAS_ALLOCATION_GUARD) |
| // Currently, check reentracy only on Linux. On Android TLS is emulated by the |
| // runtime lib, which can allocate and therefore cause reentrancy. |
| struct ReentrantScannerGuard final { |
| public: |
| ReentrantScannerGuard() { |
| PA_CHECK(!guard_); |
| guard_ = true; |
| } |
| ~ReentrantScannerGuard() { guard_ = false; } |
| |
| private: |
| // Since this variable has hidden visibility (not referenced by other DSOs), |
| // assume that thread_local works on all supported architectures. |
| static thread_local size_t guard_; |
| }; |
| thread_local size_t ReentrantScannerGuard::guard_ = 0; |
| #else |
| struct [[maybe_unused]] ReentrantScannerGuard final {}; |
| #endif // PA_CONFIG(HAS_ALLOCATION_GUARD) |
| |
| // Scope that disables MTE checks. Only used inside scanning to avoid the race: |
| // a slot tag is changed by the mutator, while the scanner sees an old value. |
| struct DisableMTEScope final { |
| DisableMTEScope() { |
| ::partition_alloc::ChangeMemoryTaggingModeForCurrentThread( |
| ::partition_alloc::TagViolationReportingMode::kDisabled); |
| } |
| ~DisableMTEScope() { |
| ::partition_alloc::ChangeMemoryTaggingModeForCurrentThread( |
| parent_tagging_mode); |
| } |
| |
| private: |
| ::partition_alloc::TagViolationReportingMode parent_tagging_mode = |
| ::partition_alloc::internal::GetMemoryTaggingModeForCurrentThread(); |
| }; |
| |
| #if PA_CONFIG(STARSCAN_USE_CARD_TABLE) |
| // Bytemap that represent regions (cards) that contain quarantined slots. |
| // A single PCScan cycle consists of the following steps: |
| // 1) clearing (memset quarantine + marking cards that contain quarantine); |
| // 2) scanning; |
| // 3) sweeping (freeing + unmarking cards that contain freed slots). |
| // Marking cards on step 1) ensures that the card table stays in the consistent |
| // state while scanning. Unmarking on the step 3) ensures that unmarking |
| // actually happens (and we don't hit too many false positives). |
| // |
| // The code here relies on the fact that |address| is in the regular pool and |
| // that the card table (this object) is allocated at the very beginning of that |
| // pool. |
| class QuarantineCardTable final { |
| public: |
| // Avoid the load of the base of the regular pool. |
| PA_ALWAYS_INLINE static QuarantineCardTable& GetFrom(uintptr_t address) { |
| PA_SCAN_DCHECK(IsManagedByPartitionAllocRegularPool(address)); |
| return *reinterpret_cast<QuarantineCardTable*>( |
| address & PartitionAddressSpace::RegularPoolBaseMask()); |
| } |
| |
| PA_ALWAYS_INLINE void Quarantine(uintptr_t begin, size_t size) { |
| return SetImpl(begin, size, true); |
| } |
| |
| PA_ALWAYS_INLINE void Unquarantine(uintptr_t begin, size_t size) { |
| return SetImpl(begin, size, false); |
| } |
| |
| // Returns whether the card to which |address| points to contains quarantined |
| // slots. May return false positives for but should never return false |
| // negatives, as otherwise this breaks security. |
| PA_ALWAYS_INLINE bool IsQuarantined(uintptr_t address) const { |
| const size_t byte = Byte(address); |
| PA_SCAN_DCHECK(byte < bytes_.size()); |
| return bytes_[byte]; |
| } |
| |
| private: |
| static constexpr size_t kCardSize = kPoolMaxSize / kSuperPageSize; |
| static constexpr size_t kBytes = kPoolMaxSize / kCardSize; |
| |
| QuarantineCardTable() = default; |
| |
| PA_ALWAYS_INLINE static size_t Byte(uintptr_t address) { |
| return (address & ~PartitionAddressSpace::RegularPoolBaseMask()) / |
| kCardSize; |
| } |
| |
| PA_ALWAYS_INLINE void SetImpl(uintptr_t begin, size_t size, bool value) { |
| const size_t byte = Byte(begin); |
| const size_t need_bytes = (size + (kCardSize - 1)) / kCardSize; |
| PA_SCAN_DCHECK(bytes_.size() >= byte + need_bytes); |
| PA_SCAN_DCHECK(IsManagedByPartitionAllocRegularPool(begin)); |
| for (size_t i = byte; i < byte + need_bytes; ++i) { |
| bytes_[i] = value; |
| } |
| } |
| |
| std::array<bool, kBytes> bytes_; |
| }; |
| static_assert(kSuperPageSize >= sizeof(QuarantineCardTable), |
| "Card table size must be less than kSuperPageSize, since this is " |
| "what is committed"); |
| #endif // PA_CONFIG(STARSCAN_USE_CARD_TABLE) |
| |
| template <typename T> |
| using MetadataVector = std::vector<T, MetadataAllocator<T>>; |
| template <typename T> |
| using MetadataSet = std::set<T, std::less<>, MetadataAllocator<T>>; |
| template <typename K, typename V> |
| using MetadataHashMap = |
| std::unordered_map<K, |
| V, |
| std::hash<K>, |
| std::equal_to<>, |
| MetadataAllocator<std::pair<const K, V>>>; |
| |
| struct GetSlotStartResult final { |
| PA_ALWAYS_INLINE bool is_found() const { |
| PA_SCAN_DCHECK(!slot_start || slot_size); |
| return slot_start; |
| } |
| |
| uintptr_t slot_start = 0; |
| size_t slot_size = 0; |
| }; |
| |
| // Returns the start of a slot, or 0 if |maybe_inner_address| is not inside of |
| // an existing slot span. The function may return a non-0 address even inside a |
| // decommitted or free slot span, it's the caller responsibility to check if |
| // memory is actually allocated. |
| // |
| // |maybe_inner_address| must be within a normal-bucket super page and can also |
| // point to guard pages or slot-span metadata. |
| PA_SCAN_INLINE GetSlotStartResult |
| GetSlotStartInSuperPage(uintptr_t maybe_inner_address) { |
| PA_SCAN_DCHECK(IsManagedByNormalBuckets(maybe_inner_address)); |
| // Don't use SlotSpanMetadata/PartitionPage::FromAddr() and family, because |
| // they expect an address within a super page payload area, which we don't |
| // know yet if |maybe_inner_address| is. |
| const uintptr_t super_page = maybe_inner_address & kSuperPageBaseMask; |
| |
| const uintptr_t partition_page_index = |
| (maybe_inner_address & kSuperPageOffsetMask) >> PartitionPageShift(); |
| auto* page = PartitionSuperPageToMetadataArea<ThreadSafe>(super_page) + |
| partition_page_index; |
| // Check if page is valid. The check also works for the guard pages and the |
| // metadata page. |
| if (!page->is_valid) { |
| return {}; |
| } |
| |
| page -= page->slot_span_metadata_offset; |
| PA_SCAN_DCHECK(page->is_valid); |
| PA_SCAN_DCHECK(!page->slot_span_metadata_offset); |
| auto* slot_span = &page->slot_span_metadata; |
| // Check if the slot span is actually used and valid. |
| if (!slot_span->bucket) { |
| return {}; |
| } |
| PA_SCAN_DCHECK(PartitionRoot<ThreadSafe>::IsValidSlotSpan(slot_span)); |
| const uintptr_t slot_span_start = |
| SlotSpanMetadata<ThreadSafe>::ToSlotSpanStart(slot_span); |
| const ptrdiff_t ptr_offset = maybe_inner_address - slot_span_start; |
| PA_SCAN_DCHECK(0 <= ptr_offset && |
| ptr_offset < static_cast<ptrdiff_t>( |
| slot_span->bucket->get_pages_per_slot_span() * |
| PartitionPageSize())); |
| // Slot span size in bytes is not necessarily multiple of partition page. |
| // Don't check if the pointer points outside of usable area, since checking |
| // the quarantine bit will anyway return false in this case. |
| const size_t slot_size = slot_span->bucket->slot_size; |
| const size_t slot_number = slot_span->bucket->GetSlotNumber(ptr_offset); |
| const uintptr_t slot_start = slot_span_start + (slot_number * slot_size); |
| PA_SCAN_DCHECK(slot_start <= maybe_inner_address && |
| maybe_inner_address < slot_start + slot_size); |
| return {.slot_start = slot_start, .slot_size = slot_size}; |
| } |
| |
| #if PA_SCAN_DCHECK_IS_ON() |
| bool IsQuarantineEmptyOnSuperPage(uintptr_t super_page) { |
| auto* bitmap = SuperPageStateBitmap(super_page); |
| size_t visited = 0; |
| bitmap->IterateQuarantined([&visited](auto) { ++visited; }); |
| return !visited; |
| } |
| #endif |
| |
| SimdSupport DetectSimdSupport() { |
| #if PA_CONFIG(STARSCAN_NEON_SUPPORTED) |
| return SimdSupport::kNEON; |
| #else |
| const base::CPU& cpu = base::CPU::GetInstanceNoAllocation(); |
| if (cpu.has_avx2()) { |
| return SimdSupport::kAVX2; |
| } |
| if (cpu.has_sse41()) { |
| return SimdSupport::kSSE41; |
| } |
| return SimdSupport::kUnvectorized; |
| #endif // PA_CONFIG(STARSCAN_NEON_SUPPORTED) |
| } |
| |
| void CommitCardTable() { |
| #if PA_CONFIG(STARSCAN_USE_CARD_TABLE) |
| RecommitSystemPages(PartitionAddressSpace::RegularPoolBase(), |
| sizeof(QuarantineCardTable), |
| PageAccessibilityConfiguration( |
| PageAccessibilityConfiguration::kReadWrite), |
| PageAccessibilityDisposition::kRequireUpdate); |
| #endif |
| } |
| |
| template <class Function> |
| void IterateNonEmptySlotSpans(uintptr_t super_page, |
| size_t nonempty_slot_spans, |
| Function function) { |
| PA_SCAN_DCHECK(!(super_page % kSuperPageAlignment)); |
| PA_SCAN_DCHECK(nonempty_slot_spans); |
| |
| size_t slot_spans_to_visit = nonempty_slot_spans; |
| #if PA_SCAN_DCHECK_IS_ON() |
| size_t visited = 0; |
| #endif |
| |
| IterateSlotSpans<ThreadSafe>( |
| super_page, true /*with_quarantine*/, |
| [&function, &slot_spans_to_visit |
| #if PA_SCAN_DCHECK_IS_ON() |
| , |
| &visited |
| #endif |
| ](SlotSpanMetadata<ThreadSafe>* slot_span) { |
| if (slot_span->is_empty() || slot_span->is_decommitted()) { |
| // Skip empty/decommitted slot spans. |
| return false; |
| } |
| function(slot_span); |
| --slot_spans_to_visit; |
| #if PA_SCAN_DCHECK_IS_ON() |
| // In debug builds, scan all the slot spans to check that number of |
| // visited slot spans is equal to the number of nonempty_slot_spans. |
| ++visited; |
| return false; |
| #else |
| return slot_spans_to_visit == 0; |
| #endif |
| }); |
| #if PA_SCAN_DCHECK_IS_ON() |
| // Check that exactly all non-empty slot spans have been visited. |
| PA_DCHECK(nonempty_slot_spans == visited); |
| #endif |
| } |
| |
| // SuperPageSnapshot is used to record all slot spans that contain live slots. |
| // The class avoids dynamic allocations and is designed to be instantiated on |
| // stack. To avoid stack overflow, internal data structures are kept packed. |
| class SuperPageSnapshot final { |
| // The following constants are used to define a conservative estimate for |
| // maximum number of slot spans in a super page. |
| // |
| // For systems with runtime-defined page size, assume partition page size is |
| // at least 16kiB. |
| static constexpr size_t kMinPartitionPageSize = |
| __builtin_constant_p(PartitionPageSize()) ? PartitionPageSize() : 1 << 14; |
| static constexpr size_t kStateBitmapMinReservedSize = |
| __builtin_constant_p(ReservedStateBitmapSize()) |
| ? ReservedStateBitmapSize() |
| : partition_alloc::internal::base::bits::AlignUp( |
| sizeof(AllocationStateMap), |
| kMinPartitionPageSize); |
| // Take into account guard partition page at the end of super-page. |
| static constexpr size_t kGuardPagesSize = 2 * kMinPartitionPageSize; |
| |
| static constexpr size_t kPayloadMaxSize = |
| kSuperPageSize - kStateBitmapMinReservedSize - kGuardPagesSize; |
| static_assert(kPayloadMaxSize % kMinPartitionPageSize == 0, |
| "kPayloadMaxSize must be multiple of kMinPartitionPageSize"); |
| |
| static constexpr size_t kMaxSlotSpansInSuperPage = |
| kPayloadMaxSize / kMinPartitionPageSize; |
| |
| public: |
| struct ScanArea { |
| // Use packed integer types to save stack space. In theory, kAlignment could |
| // be used instead of words, but it doesn't seem to bring savings. |
| uint32_t offset_within_page_in_words; |
| uint32_t size_in_words; |
| uint32_t slot_size_in_words; |
| }; |
| |
| class ScanAreas : private std::array<ScanArea, kMaxSlotSpansInSuperPage> { |
| using Base = std::array<ScanArea, kMaxSlotSpansInSuperPage>; |
| |
| public: |
| using iterator = Base::iterator; |
| using const_iterator = Base::const_iterator; |
| using Base::operator[]; |
| |
| iterator begin() { return Base::begin(); } |
| const_iterator begin() const { return Base::begin(); } |
| |
| iterator end() { return std::next(begin(), size_); } |
| const_iterator end() const { return std::next(begin(), size_); } |
| |
| void set_size(size_t new_size) { size_ = new_size; } |
| |
| private: |
| size_t size_; |
| }; |
| |
| static_assert(std::is_trivially_default_constructible<ScanAreas>::value, |
| "ScanAreas must be trivially default constructible to ensure " |
| "that no memsets are generated by the compiler as a " |
| "result of value-initialization (or zero-initialization)"); |
| |
| void* operator new(size_t) = delete; |
| void operator delete(void*) = delete; |
| |
| // Creates snapshot for a single super page. In theory, we could simply |
| // iterate over slot spans without taking a snapshot. However, we do this to |
| // minimize the mutex locking time. The mutex must be acquired to make sure |
| // that no mutator is concurrently changing any of the slot spans. |
| explicit SuperPageSnapshot(uintptr_t super_page_base); |
| |
| const ScanAreas& scan_areas() const { return scan_areas_; } |
| |
| private: |
| ScanAreas scan_areas_; |
| }; |
| |
| static_assert( |
| sizeof(SuperPageSnapshot) <= 2048, |
| "SuperPageSnapshot must stay relatively small to be allocated on stack"); |
| |
| SuperPageSnapshot::SuperPageSnapshot(uintptr_t super_page) { |
| using SlotSpan = SlotSpanMetadata<ThreadSafe>; |
| |
| auto* extent_entry = PartitionSuperPageToExtent<ThreadSafe>(super_page); |
| |
| ::partition_alloc::internal::ScopedGuard lock(extent_entry->root->lock_); |
| |
| const size_t nonempty_slot_spans = |
| extent_entry->number_of_nonempty_slot_spans; |
| if (!nonempty_slot_spans) { |
| #if PA_SCAN_DCHECK_IS_ON() |
| // Check that quarantine bitmap is empty for super-pages that contain |
| // only empty/decommitted slot-spans. |
| PA_CHECK(IsQuarantineEmptyOnSuperPage(super_page)); |
| #endif |
| scan_areas_.set_size(0); |
| return; |
| } |
| |
| size_t current = 0; |
| |
| IterateNonEmptySlotSpans( |
| super_page, nonempty_slot_spans, [this, ¤t](SlotSpan* slot_span) { |
| const uintptr_t payload_begin = SlotSpan::ToSlotSpanStart(slot_span); |
| // For single-slot slot-spans, scan only utilized slot part. |
| const size_t provisioned_size = |
| PA_UNLIKELY(slot_span->CanStoreRawSize()) |
| ? slot_span->GetRawSize() |
| : slot_span->GetProvisionedSize(); |
| // Free & decommitted slot spans are skipped. |
| PA_SCAN_DCHECK(provisioned_size > 0); |
| const uintptr_t payload_end = payload_begin + provisioned_size; |
| auto& area = scan_areas_[current]; |
| |
| const size_t offset_in_words = |
| (payload_begin & kSuperPageOffsetMask) / sizeof(uintptr_t); |
| const size_t size_in_words = |
| (payload_end - payload_begin) / sizeof(uintptr_t); |
| const size_t slot_size_in_words = |
| slot_span->bucket->slot_size / sizeof(uintptr_t); |
| |
| #if PA_SCAN_DCHECK_IS_ON() |
| PA_DCHECK(offset_in_words <= |
| std::numeric_limits< |
| decltype(area.offset_within_page_in_words)>::max()); |
| PA_DCHECK(size_in_words <= |
| std::numeric_limits<decltype(area.size_in_words)>::max()); |
| PA_DCHECK( |
| slot_size_in_words <= |
| std::numeric_limits<decltype(area.slot_size_in_words)>::max()); |
| #endif |
| |
| area.offset_within_page_in_words = offset_in_words; |
| area.size_in_words = size_in_words; |
| area.slot_size_in_words = slot_size_in_words; |
| |
| ++current; |
| }); |
| |
| PA_SCAN_DCHECK(kMaxSlotSpansInSuperPage >= current); |
| scan_areas_.set_size(current); |
| } |
| |
| } // namespace |
| |
| class PCScanScanLoop; |
| |
| // This class is responsible for performing the entire PCScan task. |
| // TODO(bikineev): Move PCScan algorithm out of PCScanTask. |
| class PCScanTask final : public base::RefCountedThreadSafe<PCScanTask>, |
| public AllocatedOnPCScanMetadataPartition { |
| public: |
| // Creates and initializes a PCScan state. |
| PCScanTask(PCScan& pcscan, size_t quarantine_last_size); |
| |
| PCScanTask(PCScanTask&&) noexcept = delete; |
| PCScanTask& operator=(PCScanTask&&) noexcept = delete; |
| |
| // Execute PCScan from mutator inside safepoint. |
| void RunFromMutator(); |
| |
| // Execute PCScan from the scanner thread. Must be called only once from the |
| // scanner thread. |
| void RunFromScanner(); |
| |
| PCScanScheduler& scheduler() const { return pcscan_.scheduler(); } |
| |
| private: |
| class StackVisitor; |
| friend class PCScanScanLoop; |
| |
| using Root = PCScan::Root; |
| using SlotSpan = SlotSpanMetadata<ThreadSafe>; |
| |
| // This is used: |
| // - to synchronize all scanning threads (mutators and the scanner); |
| // - for the scanner, to transition through the state machine |
| // (kScheduled -> kScanning (ctor) -> kSweepingAndFinishing (dtor). |
| template <Context context> |
| class SyncScope final { |
| public: |
| explicit SyncScope(PCScanTask& task) : task_(task) { |
| task_.number_of_scanning_threads_.fetch_add(1, std::memory_order_relaxed); |
| if (context == Context::kScanner) { |
| task_.pcscan_.state_.store(PCScan::State::kScanning, |
| std::memory_order_relaxed); |
| task_.pcscan_.SetJoinableIfSafepointEnabled(true); |
| } |
| } |
| ~SyncScope() { |
| // First, notify the scanning thread that this thread is done. |
| NotifyThreads(); |
| if (context == Context::kScanner) { |
| // The scanner thread must wait here until all safepoints leave. |
| // Otherwise, sweeping may free a page that can later be accessed by a |
| // descheduled mutator. |
| WaitForOtherThreads(); |
| task_.pcscan_.state_.store(PCScan::State::kSweepingAndFinishing, |
| std::memory_order_relaxed); |
| } |
| } |
| |
| private: |
| void NotifyThreads() { |
| { |
| // The lock is required as otherwise there is a race between |
| // fetch_sub/notify in the mutator and checking |
| // number_of_scanning_threads_/waiting in the scanner. |
| std::lock_guard<std::mutex> lock(task_.mutex_); |
| task_.number_of_scanning_threads_.fetch_sub(1, |
| std::memory_order_relaxed); |
| { |
| // Notify that scan is done and there is no need to enter |
| // the safepoint. This also helps a mutator to avoid repeating |
| // entering. Since the scanner thread waits for all threads to finish, |
| // there is no ABA problem here. |
| task_.pcscan_.SetJoinableIfSafepointEnabled(false); |
| } |
| } |
| task_.condvar_.notify_all(); |
| } |
| |
| void WaitForOtherThreads() { |
| std::unique_lock<std::mutex> lock(task_.mutex_); |
| task_.condvar_.wait(lock, [this] { |
| return !task_.number_of_scanning_threads_.load( |
| std::memory_order_relaxed); |
| }); |
| } |
| |
| PCScanTask& task_; |
| }; |
| |
| friend class base::RefCountedThreadSafe<PCScanTask>; |
| ~PCScanTask() = default; |
| |
| PA_SCAN_INLINE AllocationStateMap* TryFindScannerBitmapForPointer( |
| uintptr_t maybe_ptr) const; |
| |
| // Lookup and marking functions. Return size of the slot if marked, or zero |
| // otherwise. |
| PA_SCAN_INLINE size_t TryMarkSlotInNormalBuckets(uintptr_t maybe_ptr) const; |
| |
| // Scans stack, only called from safepoints. |
| void ScanStack(); |
| |
| // Scan individual areas. |
| void ScanNormalArea(PCScanInternal& pcscan, |
| PCScanScanLoop& scan_loop, |
| uintptr_t begin, |
| uintptr_t end); |
| void ScanLargeArea(PCScanInternal& pcscan, |
| PCScanScanLoop& scan_loop, |
| uintptr_t begin, |
| uintptr_t end, |
| size_t slot_size); |
| |
| // Scans all registered partitions and marks reachable quarantined slots. |
| void ScanPartitions(); |
| |
| // Clear quarantined slots and prepare card table for fast lookup |
| void ClearQuarantinedSlotsAndPrepareCardTable(); |
| |
| // Unprotect all slot spans from all partitions. |
| void UnprotectPartitions(); |
| |
| // Sweeps (frees) unreachable quarantined entries. |
| void SweepQuarantine(); |
| |
| // Finishes the scanner (updates limits, UMA, etc). |
| void FinishScanner(); |
| |
| // Cache the pcscan epoch to avoid the compiler loading the atomic |
| // QuarantineData::epoch_ on each access. |
| const size_t pcscan_epoch_; |
| std::unique_ptr<StarScanSnapshot> snapshot_; |
| StatsCollector stats_; |
| // Mutex and codvar that are used to synchronize scanning threads. |
| std::mutex mutex_; |
| std::condition_variable condvar_; |
| std::atomic<size_t> number_of_scanning_threads_{0u}; |
| // We can unprotect only once to reduce context-switches. |
| std::once_flag unprotect_once_flag_; |
| bool immediatelly_free_slots_{false}; |
| PCScan& pcscan_; |
| }; |
| |
| PA_SCAN_INLINE AllocationStateMap* PCScanTask::TryFindScannerBitmapForPointer( |
| uintptr_t maybe_ptr) const { |
| PA_SCAN_DCHECK(IsManagedByPartitionAllocRegularPool(maybe_ptr)); |
| // First, check if |maybe_ptr| points to a valid super page or a quarantined |
| // card. |
| #if PA_CONFIG(HAS_64_BITS_POINTERS) |
| #if PA_CONFIG(STARSCAN_USE_CARD_TABLE) |
| // Check if |maybe_ptr| points to a quarantined card. |
| if (PA_LIKELY( |
| !QuarantineCardTable::GetFrom(maybe_ptr).IsQuarantined(maybe_ptr))) { |
| return nullptr; |
| } |
| #else |
| // Without the card table, use the reservation offset table to check if |
| // |maybe_ptr| points to a valid super-page. It's not as precise (meaning that |
| // we may have hit the slow path more frequently), but reduces the memory |
| // overhead. Since we are certain here, that |maybe_ptr| refers to the |
| // regular pool, it's okay to use non-checking version of |
| // ReservationOffsetPointer(). |
| const uintptr_t offset = |
| maybe_ptr & ~PartitionAddressSpace::RegularPoolBaseMask(); |
| if (PA_LIKELY(*ReservationOffsetPointer(kRegularPoolHandle, offset) != |
| kOffsetTagNormalBuckets)) { |
| return nullptr; |
| } |
| #endif // PA_CONFIG(STARSCAN_USE_CARD_TABLE) |
| #else // PA_CONFIG(HAS_64_BITS_POINTERS) |
| if (PA_LIKELY(!IsManagedByPartitionAllocRegularPool(maybe_ptr))) { |
| return nullptr; |
| } |
| #endif // PA_CONFIG(HAS_64_BITS_POINTERS) |
| |
| // We are certain here that |maybe_ptr| points to an allocated super-page. |
| return StateBitmapFromAddr(maybe_ptr); |
| } |
| |
| // Looks up and marks a potential dangling pointer. Returns the size of the slot |
| // (which is then accounted as quarantined), or zero if no slot is found. |
| // For normal bucket super pages, PCScan uses two quarantine bitmaps, the |
| // mutator and the scanner one. The former is used by mutators when slots are |
| // freed, while the latter is used concurrently by the PCScan thread. The |
| // bitmaps are swapped as soon as PCScan is triggered. Once a dangling pointer |
| // (which points to a slot in the scanner bitmap) is found, |
| // TryMarkSlotInNormalBuckets() marks it again in the bitmap and clears |
| // from the scanner bitmap. This way, when scanning is done, all uncleared |
| // entries in the scanner bitmap correspond to unreachable slots. |
| PA_SCAN_INLINE size_t |
| PCScanTask::TryMarkSlotInNormalBuckets(uintptr_t maybe_ptr) const { |
| // Check if |maybe_ptr| points somewhere to the heap. |
| // The caller has to make sure that |maybe_ptr| isn't MTE-tagged. |
| auto* state_map = TryFindScannerBitmapForPointer(maybe_ptr); |
| if (!state_map) { |
| return 0; |
| } |
| |
| // Beyond this point, we know that |maybe_ptr| is a pointer within a |
| // normal-bucket super page. |
| PA_SCAN_DCHECK(IsManagedByNormalBuckets(maybe_ptr)); |
| |
| #if !PA_CONFIG(STARSCAN_USE_CARD_TABLE) |
| // Pointer from a normal bucket is always in the first superpage. |
| auto* root = Root::FromAddrInFirstSuperpage(maybe_ptr); |
| // Without the card table, we must make sure that |maybe_ptr| doesn't point to |
| // metadata partition. |
| // TODO(bikineev): To speed things up, consider removing the check and |
| // committing quarantine bitmaps for metadata partition. |
| // TODO(bikineev): Marking an entry in the reservation-table is not a |
| // publishing operation, meaning that the |root| pointer may not be assigned |
| // yet. This can happen as arbitrary pointers may point into a super-page |
| // during its set up. Make sure to check |root| is not null before |
| // dereferencing it. |
| if (PA_UNLIKELY(!root || !root->IsQuarantineEnabled())) { |
| return 0; |
| } |
| #endif // !PA_CONFIG(STARSCAN_USE_CARD_TABLE) |
| |
| // Check if pointer was in the quarantine bitmap. |
| const GetSlotStartResult slot_start_result = |
| GetSlotStartInSuperPage(maybe_ptr); |
| if (!slot_start_result.is_found()) { |
| return 0; |
| } |
| |
| const uintptr_t slot_start = slot_start_result.slot_start; |
| if (PA_LIKELY(!state_map->IsQuarantined(slot_start))) { |
| return 0; |
| } |
| |
| PA_SCAN_DCHECK((maybe_ptr & kSuperPageBaseMask) == |
| (slot_start & kSuperPageBaseMask)); |
| |
| if (PA_UNLIKELY(immediatelly_free_slots_)) { |
| return 0; |
| } |
| |
| // Now we are certain that |maybe_ptr| is a dangling pointer. Mark it again in |
| // the mutator bitmap and clear from the scanner bitmap. Note that since |
| // PCScan has exclusive access to the scanner bitmap, we can avoid atomic rmw |
| // operation for it. |
| if (PA_LIKELY( |
| state_map->MarkQuarantinedAsReachable(slot_start, pcscan_epoch_))) { |
| return slot_start_result.slot_size; |
| } |
| |
| return 0; |
| } |
| |
| void PCScanTask::ClearQuarantinedSlotsAndPrepareCardTable() { |
| const PCScan::ClearType clear_type = pcscan_.clear_type_; |
| |
| #if !PA_CONFIG(STARSCAN_USE_CARD_TABLE) |
| if (clear_type == PCScan::ClearType::kEager) { |
| return; |
| } |
| #endif |
| |
| StarScanSnapshot::ClearingView view(*snapshot_); |
| view.VisitConcurrently([clear_type](uintptr_t super_page) { |
| auto* bitmap = StateBitmapFromAddr(super_page); |
| auto* root = Root::FromFirstSuperPage(super_page); |
| bitmap->IterateQuarantined([root, clear_type](uintptr_t slot_start) { |
| auto* slot_span = SlotSpan::FromSlotStart(slot_start); |
| // Use zero as a zapping value to speed up the fast bailout check in |
| // ScanPartitions. |
| const size_t size = slot_span->GetUsableSize(root); |
| if (clear_type == PCScan::ClearType::kLazy) { |
| void* object = root->SlotStartToObject(slot_start); |
| memset(object, 0, size); |
| } |
| #if PA_CONFIG(STARSCAN_USE_CARD_TABLE) |
| // Set card(s) for this quarantined slot. |
| QuarantineCardTable::GetFrom(slot_start).Quarantine(slot_start, size); |
| #endif |
| }); |
| }); |
| } |
| |
| void PCScanTask::UnprotectPartitions() { |
| auto& pcscan = PCScanInternal::Instance(); |
| if (!pcscan.WriteProtectionEnabled()) { |
| return; |
| } |
| |
| StarScanSnapshot::UnprotectingView unprotect_view(*snapshot_); |
| unprotect_view.VisitConcurrently([&pcscan](uintptr_t super_page) { |
| SuperPageSnapshot super_page_snapshot(super_page); |
| |
| for (const auto& scan_area : super_page_snapshot.scan_areas()) { |
| const uintptr_t begin = |
| super_page | |
| (scan_area.offset_within_page_in_words * sizeof(uintptr_t)); |
| const uintptr_t end = |
| begin + (scan_area.size_in_words * sizeof(uintptr_t)); |
| |
| pcscan.UnprotectPages(begin, end - begin); |
| } |
| }); |
| } |
| |
| class PCScanScanLoop final : public ScanLoop<PCScanScanLoop> { |
| friend class ScanLoop<PCScanScanLoop>; |
| |
| public: |
| explicit PCScanScanLoop(const PCScanTask& task) |
| : ScanLoop(PCScanInternal::Instance().simd_support()), task_(task) {} |
| |
| size_t quarantine_size() const { return quarantine_size_; } |
| |
| private: |
| #if PA_CONFIG(HAS_64_BITS_POINTERS) |
| PA_ALWAYS_INLINE static uintptr_t RegularPoolBase() { |
| return PartitionAddressSpace::RegularPoolBase(); |
| } |
| PA_ALWAYS_INLINE static uintptr_t RegularPoolMask() { |
| return PartitionAddressSpace::RegularPoolBaseMask(); |
| } |
| #endif // PA_CONFIG(HAS_64_BITS_POINTERS) |
| |
| PA_SCAN_INLINE void CheckPointer(uintptr_t maybe_ptr_maybe_tagged) { |
| // |maybe_ptr| may have an MTE tag, so remove it first. |
| quarantine_size_ += |
| task_.TryMarkSlotInNormalBuckets(UntagAddr(maybe_ptr_maybe_tagged)); |
| } |
| |
| const PCScanTask& task_; |
| DisableMTEScope disable_mte_; |
| size_t quarantine_size_ = 0; |
| }; |
| |
| class PCScanTask::StackVisitor final : public internal::StackVisitor { |
| public: |
| explicit StackVisitor(const PCScanTask& task) : task_(task) {} |
| |
| void VisitStack(uintptr_t* stack_ptr, uintptr_t* stack_top) override { |
| static constexpr size_t kMinimalAlignment = 32; |
| uintptr_t begin = |
| reinterpret_cast<uintptr_t>(stack_ptr) & ~(kMinimalAlignment - 1); |
| uintptr_t end = |
| (reinterpret_cast<uintptr_t>(stack_top) + kMinimalAlignment - 1) & |
| ~(kMinimalAlignment - 1); |
| PA_CHECK(begin < end); |
| PCScanScanLoop loop(task_); |
| loop.Run(begin, end); |
| quarantine_size_ += loop.quarantine_size(); |
| } |
| |
| // Returns size of quarantined slots that are reachable from the current |
| // stack. |
| size_t quarantine_size() const { return quarantine_size_; } |
| |
| private: |
| const PCScanTask& task_; |
| size_t quarantine_size_ = 0; |
| }; |
| |
| PCScanTask::PCScanTask(PCScan& pcscan, size_t quarantine_last_size) |
| : pcscan_epoch_(pcscan.epoch() - 1), |
| snapshot_(StarScanSnapshot::Create(PCScanInternal::Instance())), |
| stats_(PCScanInternal::Instance().process_name(), quarantine_last_size), |
| immediatelly_free_slots_( |
| PCScanInternal::Instance().IsImmediateFreeingEnabled()), |
| pcscan_(pcscan) {} |
| |
| void PCScanTask::ScanStack() { |
| const auto& pcscan = PCScanInternal::Instance(); |
| if (!pcscan.IsStackScanningEnabled()) { |
| return; |
| } |
| // Check if the stack top was registered. It may happen that it's not if the |
| // current allocation happens from pthread trampolines. |
| void* stack_top = pcscan.GetCurrentThreadStackTop(); |
| if (PA_UNLIKELY(!stack_top)) { |
| return; |
| } |
| |
| Stack stack_scanner(stack_top); |
| StackVisitor visitor(*this); |
| stack_scanner.IteratePointers(&visitor); |
| stats_.IncreaseSurvivedQuarantineSize(visitor.quarantine_size()); |
| } |
| |
| void PCScanTask::ScanNormalArea(PCScanInternal& pcscan, |
| PCScanScanLoop& scan_loop, |
| uintptr_t begin, |
| uintptr_t end) { |
| // Protect slot span before scanning it. |
| pcscan.ProtectPages(begin, end - begin); |
| scan_loop.Run(begin, end); |
| } |
| |
| void PCScanTask::ScanLargeArea(PCScanInternal& pcscan, |
| PCScanScanLoop& scan_loop, |
| uintptr_t begin, |
| uintptr_t end, |
| size_t slot_size) { |
| // For scanning large areas, it's worthwhile checking whether the range that |
| // is scanned contains allocated slots. It also helps to skip discarded |
| // freed slots. |
| // Protect slot span before scanning it. |
| pcscan.ProtectPages(begin, end - begin); |
| |
| auto* bitmap = StateBitmapFromAddr(begin); |
| |
| for (uintptr_t current_slot = begin; current_slot < end; |
| current_slot += slot_size) { |
| // It is okay to skip slots as the object they hold has been zapped at this |
| // point, which means that the pointers no longer retain other slots. |
| if (!bitmap->IsAllocated(current_slot)) { |
| continue; |
| } |
| uintptr_t current_slot_end = current_slot + slot_size; |
| // |slot_size| may be larger than |raw_size| for single-slot slot spans. |
| scan_loop.Run(current_slot, std::min(current_slot_end, end)); |
| } |
| } |
| |
| void PCScanTask::ScanPartitions() { |
| // Threshold for which bucket size it is worthwhile in checking whether the |
| // slot is allocated and needs to be scanned. PartitionPurgeSlotSpan() |
| // purges only slots >= page-size, this helps us to avoid faulting in |
| // discarded pages. We actually lower it further to 1024, to take advantage of |
| // skipping unallocated slots, but don't want to go any lower, as this comes |
| // at a cost of expensive bitmap checking. |
| static constexpr size_t kLargeScanAreaThresholdInWords = |
| 1024 / sizeof(uintptr_t); |
| |
| PCScanScanLoop scan_loop(*this); |
| auto& pcscan = PCScanInternal::Instance(); |
| |
| StarScanSnapshot::ScanningView snapshot_view(*snapshot_); |
| snapshot_view.VisitConcurrently([this, &pcscan, |
| &scan_loop](uintptr_t super_page) { |
| SuperPageSnapshot super_page_snapshot(super_page); |
| |
| for (const auto& scan_area : super_page_snapshot.scan_areas()) { |
| const uintptr_t begin = |
| super_page | |
| (scan_area.offset_within_page_in_words * sizeof(uintptr_t)); |
| PA_SCAN_DCHECK(begin == |
| super_page + (scan_area.offset_within_page_in_words * |
| sizeof(uintptr_t))); |
| const uintptr_t end = begin + scan_area.size_in_words * sizeof(uintptr_t); |
| |
| if (PA_UNLIKELY(scan_area.slot_size_in_words >= |
| kLargeScanAreaThresholdInWords)) { |
| ScanLargeArea(pcscan, scan_loop, begin, end, |
| scan_area.slot_size_in_words * sizeof(uintptr_t)); |
| } else { |
| ScanNormalArea(pcscan, scan_loop, begin, end); |
| } |
| } |
| }); |
| |
| stats_.IncreaseSurvivedQuarantineSize(scan_loop.quarantine_size()); |
| } |
| |
| namespace { |
| |
| struct SweepStat { |
| // Bytes that were really swept (by calling free()). |
| size_t swept_bytes = 0; |
| // Bytes of marked quarantine memory that were discarded (by calling |
| // madvice(DONT_NEED)). |
| size_t discarded_bytes = 0; |
| }; |
| |
| void UnmarkInCardTable(uintptr_t slot_start, |
| SlotSpanMetadata<ThreadSafe>* slot_span) { |
| #if PA_CONFIG(STARSCAN_USE_CARD_TABLE) |
| // Reset card(s) for this quarantined slot. Please note that the cards may |
| // still contain quarantined slots (which were promoted in this scan cycle), |
| // but ClearQuarantinedSlotsAndPrepareCardTable() will set them again in the |
| // next PCScan cycle. |
| QuarantineCardTable::GetFrom(slot_start) |
| .Unquarantine(slot_start, slot_span->GetUtilizedSlotSize()); |
| #endif // PA_CONFIG(STARSCAN_USE_CARD_TABLE) |
| } |
| |
| [[maybe_unused]] size_t FreeAndUnmarkInCardTable( |
| PartitionRoot<ThreadSafe>* root, |
| SlotSpanMetadata<ThreadSafe>* slot_span, |
| uintptr_t slot_start) { |
| void* object = root->SlotStartToObject(slot_start); |
| root->FreeNoHooksImmediate(object, slot_span, slot_start); |
| UnmarkInCardTable(slot_start, slot_span); |
| return slot_span->bucket->slot_size; |
| } |
| |
| [[maybe_unused]] void SweepSuperPage(ThreadSafePartitionRoot* root, |
| uintptr_t super_page, |
| size_t epoch, |
| SweepStat& stat) { |
| auto* bitmap = StateBitmapFromAddr(super_page); |
| ThreadSafePartitionRoot::FromFirstSuperPage(super_page); |
| bitmap->IterateUnmarkedQuarantined(epoch, [root, |
| &stat](uintptr_t slot_start) { |
| auto* slot_span = SlotSpanMetadata<ThreadSafe>::FromSlotStart(slot_start); |
| stat.swept_bytes += FreeAndUnmarkInCardTable(root, slot_span, slot_start); |
| }); |
| } |
| |
| [[maybe_unused]] void SweepSuperPageAndDiscardMarkedQuarantine( |
| ThreadSafePartitionRoot* root, |
| uintptr_t super_page, |
| size_t epoch, |
| SweepStat& stat) { |
| auto* bitmap = StateBitmapFromAddr(super_page); |
| bitmap->IterateQuarantined(epoch, [root, &stat](uintptr_t slot_start, |
| bool is_marked) { |
| auto* slot_span = SlotSpanMetadata<ThreadSafe>::FromSlotStart(slot_start); |
| if (PA_LIKELY(!is_marked)) { |
| stat.swept_bytes += FreeAndUnmarkInCardTable(root, slot_span, slot_start); |
| return; |
| } |
| // Otherwise, try to discard pages for marked quarantine. Since no data is |
| // stored in quarantined slots (e.g. the |next| pointer), this can be |
| // freely done. |
| const size_t slot_size = slot_span->bucket->slot_size; |
| if (slot_size >= SystemPageSize()) { |
| const uintptr_t discard_end = |
| base::bits::AlignDown(slot_start + slot_size, SystemPageSize()); |
| const uintptr_t discard_begin = |
| base::bits::AlignUp(slot_start, SystemPageSize()); |
| const intptr_t discard_size = discard_end - discard_begin; |
| if (discard_size > 0) { |
| DiscardSystemPages(discard_begin, discard_size); |
| stat.discarded_bytes += discard_size; |
| } |
| } |
| }); |
| } |
| |
| [[maybe_unused]] void SweepSuperPageWithBatchedFree( |
| ThreadSafePartitionRoot* root, |
| uintptr_t super_page, |
| size_t epoch, |
| SweepStat& stat) { |
| using SlotSpan = SlotSpanMetadata<ThreadSafe>; |
| |
| auto* bitmap = StateBitmapFromAddr(super_page); |
| SlotSpan* previous_slot_span = nullptr; |
| internal::PartitionFreelistEntry* freelist_tail = nullptr; |
| internal::PartitionFreelistEntry* freelist_head = nullptr; |
| size_t freelist_entries = 0; |
| |
| const auto bitmap_iterator = [&](uintptr_t slot_start) { |
| SlotSpan* current_slot_span = SlotSpan::FromSlotStart(slot_start); |
| auto* entry = PartitionFreelistEntry::EmplaceAndInitNull(slot_start); |
| |
| if (current_slot_span != previous_slot_span) { |
| // We started scanning a new slot span. Flush the accumulated freelist to |
| // the slot-span's freelist. This is a single lock acquired per slot span. |
| if (previous_slot_span && freelist_entries) { |
| root->RawFreeBatch(freelist_head, freelist_tail, freelist_entries, |
| previous_slot_span); |
| } |
| freelist_head = entry; |
| freelist_tail = nullptr; |
| freelist_entries = 0; |
| previous_slot_span = current_slot_span; |
| } |
| |
| if (freelist_tail) { |
| freelist_tail->SetNext(entry); |
| } |
| freelist_tail = entry; |
| ++freelist_entries; |
| |
| UnmarkInCardTable(slot_start, current_slot_span); |
| |
| stat.swept_bytes += current_slot_span->bucket->slot_size; |
| }; |
| |
| bitmap->IterateUnmarkedQuarantinedAndFree(epoch, bitmap_iterator); |
| |
| if (previous_slot_span && freelist_entries) { |
| root->RawFreeBatch(freelist_head, freelist_tail, freelist_entries, |
| previous_slot_span); |
| } |
| } |
| |
| } // namespace |
| |
| void PCScanTask::SweepQuarantine() { |
| // Check that scan is unjoinable by this time. |
| PA_DCHECK(!pcscan_.IsJoinable()); |
| // Discard marked quarantine memory on every Nth scan. |
| // TODO(bikineev): Find a better signal (e.g. memory pressure, high |
| // survival rate, etc). |
| static constexpr size_t kDiscardMarkedQuarantineFrequency = 16; |
| const bool should_discard = |
| (pcscan_epoch_ % kDiscardMarkedQuarantineFrequency == 0) && |
| (pcscan_.clear_type_ == PCScan::ClearType::kEager); |
| |
| SweepStat stat; |
| StarScanSnapshot::SweepingView sweeping_view(*snapshot_); |
| sweeping_view.VisitNonConcurrently( |
| [this, &stat, should_discard](uintptr_t super_page) { |
| auto* root = ThreadSafePartitionRoot::FromFirstSuperPage(super_page); |
| |
| #if PA_STARSCAN_BATCHED_FREE |
| SweepSuperPageWithBatchedFree(root, super_page, pcscan_epoch_, stat); |
| (void)should_discard; |
| #else |
| if (PA_UNLIKELY(should_discard && !root->flags.allow_cookie)) |
| SweepSuperPageAndDiscardMarkedQuarantine(root, super_page, |
| pcscan_epoch_, stat); |
| else |
| SweepSuperPage(root, super_page, pcscan_epoch_, stat); |
| #endif |
| }); |
| |
| stats_.IncreaseSweptSize(stat.swept_bytes); |
| stats_.IncreaseDiscardedQuarantineSize(stat.discarded_bytes); |
| |
| #if PA_CONFIG(THREAD_CACHE_SUPPORTED) |
| // Sweeping potentially frees into the current thread's thread cache. Purge |
| // releases the cache back to the global allocator. |
| auto* current_thread_tcache = ThreadCache::Get(); |
| if (ThreadCache::IsValid(current_thread_tcache)) { |
| current_thread_tcache->Purge(); |
| } |
| #endif // PA_CONFIG(THREAD_CACHE_SUPPORTED) |
| } |
| |
| void PCScanTask::FinishScanner() { |
| stats_.ReportTracesAndHists(PCScanInternal::Instance().GetReporter()); |
| |
| pcscan_.scheduler_.scheduling_backend().UpdateScheduleAfterScan( |
| stats_.survived_quarantine_size(), stats_.GetOverallTime(), |
| PCScanInternal::Instance().CalculateTotalHeapSize()); |
| |
| PCScanInternal::Instance().ResetCurrentPCScanTask(); |
| // Change the state and check that concurrent task can't be scheduled twice. |
| PA_CHECK(pcscan_.state_.exchange(PCScan::State::kNotRunning, |
| std::memory_order_acq_rel) == |
| PCScan::State::kSweepingAndFinishing); |
| } |
| |
| void PCScanTask::RunFromMutator() { |
| ReentrantScannerGuard reentrancy_guard; |
| StatsCollector::MutatorScope overall_scope( |
| stats_, StatsCollector::MutatorId::kOverall); |
| { |
| SyncScope<Context::kMutator> sync_scope(*this); |
| // Mutator might start entering the safepoint while scanning was already |
| // finished. |
| if (!pcscan_.IsJoinable()) { |
| return; |
| } |
| { |
| // Clear all quarantined slots and prepare card table. |
| StatsCollector::MutatorScope clear_scope( |
| stats_, StatsCollector::MutatorId::kClear); |
| ClearQuarantinedSlotsAndPrepareCardTable(); |
| } |
| { |
| // Scan the thread's stack to find dangling references. |
| StatsCollector::MutatorScope scan_scope( |
| stats_, StatsCollector::MutatorId::kScanStack); |
| ScanStack(); |
| } |
| { |
| // Unprotect all scanned pages, if needed. |
| UnprotectPartitions(); |
| } |
| { |
| // Scan heap for dangling references. |
| StatsCollector::MutatorScope scan_scope(stats_, |
| StatsCollector::MutatorId::kScan); |
| ScanPartitions(); |
| } |
| } |
| } |
| |
| void PCScanTask::RunFromScanner() { |
| ReentrantScannerGuard reentrancy_guard; |
| { |
| StatsCollector::ScannerScope overall_scope( |
| stats_, StatsCollector::ScannerId::kOverall); |
| { |
| SyncScope<Context::kScanner> sync_scope(*this); |
| { |
| // Clear all quarantined slots and prepare the card table. |
| StatsCollector::ScannerScope clear_scope( |
| stats_, StatsCollector::ScannerId::kClear); |
| ClearQuarantinedSlotsAndPrepareCardTable(); |
| } |
| { |
| // Scan heap for dangling references. |
| StatsCollector::ScannerScope scan_scope( |
| stats_, StatsCollector::ScannerId::kScan); |
| ScanPartitions(); |
| } |
| { |
| // Unprotect all scanned pages, if needed. |
| UnprotectPartitions(); |
| } |
| } |
| { |
| // Sweep unreachable quarantined slots. |
| StatsCollector::ScannerScope sweep_scope( |
| stats_, StatsCollector::ScannerId::kSweep); |
| SweepQuarantine(); |
| } |
| } |
| FinishScanner(); |
| } |
| |
| class PCScan::PCScanThread final { |
| public: |
| using TaskHandle = PCScanInternal::TaskHandle; |
| |
| static PCScanThread& Instance() { |
| // Lazily instantiate the scanning thread. |
| static internal::base::NoDestructor<PCScanThread> instance; |
| return *instance; |
| } |
| |
| void PostTask(TaskHandle task) { |
| { |
| std::lock_guard<std::mutex> lock(mutex_); |
| PA_DCHECK(!posted_task_.get()); |
| posted_task_ = std::move(task); |
| wanted_delay_ = base::TimeDelta(); |
| } |
| condvar_.notify_one(); |
| } |
| |
| void PostDelayedTask(base::TimeDelta delay) { |
| { |
| std::lock_guard<std::mutex> lock(mutex_); |
| if (posted_task_.get()) { |
| return; |
| } |
| wanted_delay_ = delay; |
| } |
| condvar_.notify_one(); |
| } |
| |
| private: |
| friend class internal::base::NoDestructor<PCScanThread>; |
| |
| PCScanThread() { |
| ScopedAllowAllocations allow_allocations_within_std_thread; |
| std::thread{[](PCScanThread* instance) { |
| static constexpr const char* kThreadName = "PCScan"; |
| // Ideally we should avoid mixing base:: and std:: API for |
| // threading, but this is useful for visualizing the pcscan |
| // thread in chrome://tracing. |
| internal::base::PlatformThread::SetName(kThreadName); |
| instance->TaskLoop(); |
| }, |
| this} |
| .detach(); |
| } |
| |
| // Waits and returns whether the delay should be recomputed. |
| bool Wait(std::unique_lock<std::mutex>& lock) { |
| PA_DCHECK(lock.owns_lock()); |
| if (wanted_delay_.is_zero()) { |
| condvar_.wait(lock, [this] { |
| // Re-evaluate if either delay changed, or a task was |
| // enqueued. |
| return !wanted_delay_.is_zero() || posted_task_.get(); |
| }); |
| // The delay has already been set up and should not be queried again. |
| return false; |
| } |
| condvar_.wait_for( |
| lock, std::chrono::microseconds(wanted_delay_.InMicroseconds())); |
| // If no task has been posted, the delay should be recomputed at this point. |
| return !posted_task_.get(); |
| } |
| |
| void TaskLoop() { |
| while (true) { |
| TaskHandle current_task; |
| { |
| std::unique_lock<std::mutex> lock(mutex_); |
| // Scheduling. |
| while (!posted_task_.get()) { |
| if (Wait(lock)) { |
| wanted_delay_ = |
| scheduler().scheduling_backend().UpdateDelayedSchedule(); |
| if (wanted_delay_.is_zero()) { |
| break; |
| } |
| } |
| } |
| // Differentiate between a posted task and a delayed task schedule. |
| if (posted_task_.get()) { |
| std::swap(current_task, posted_task_); |
| wanted_delay_ = base::TimeDelta(); |
| } else { |
| PA_DCHECK(wanted_delay_.is_zero()); |
| } |
| } |
| // Differentiate between a posted task and a delayed task schedule. |
| if (current_task.get()) { |
| current_task->RunFromScanner(); |
| } else { |
| PCScan::Instance().PerformScan(PCScan::InvocationMode::kNonBlocking); |
| } |
| } |
| } |
| |
| PCScanScheduler& scheduler() const { return PCScan::Instance().scheduler(); } |
| |
| std::mutex mutex_; |
| std::condition_variable condvar_; |
| TaskHandle posted_task_; |
| base::TimeDelta wanted_delay_; |
| }; |
| |
| PCScanInternal::PCScanInternal() : simd_support_(DetectSimdSupport()) {} |
| |
| PCScanInternal::~PCScanInternal() = default; |
| |
| void PCScanInternal::Initialize(PCScan::InitConfig config) { |
| PA_DCHECK(!is_initialized_); |
| #if PA_CONFIG(HAS_64_BITS_POINTERS) |
| // Make sure that pools are initialized. |
| PartitionAddressSpace::Init(); |
| #endif |
| CommitCardTable(); |
| #if PA_CONFIG(STARSCAN_UFFD_WRITE_PROTECTOR_SUPPORTED) |
| if (config.write_protection == |
| PCScan::InitConfig::WantedWriteProtectionMode::kEnabled) { |
| write_protector_ = std::make_unique<UserFaultFDWriteProtector>(); |
| } else { |
| write_protector_ = std::make_unique<NoWriteProtector>(); |
| } |
| #else |
| write_protector_ = std::make_unique<NoWriteProtector>(); |
| #endif // PA_CONFIG(STARSCAN_UFFD_WRITE_PROTECTOR_SUPPORTED) |
| PCScan::SetClearType(write_protector_->SupportedClearType()); |
| |
| if (config.safepoint == PCScan::InitConfig::SafepointMode::kEnabled) { |
| PCScan::Instance().EnableSafepoints(); |
| } |
| scannable_roots_ = RootsMap(); |
| nonscannable_roots_ = RootsMap(); |
| |
| static partition_alloc::StatsReporter s_no_op_reporter; |
| PCScan::Instance().RegisterStatsReporter(&s_no_op_reporter); |
| |
| // Don't initialize PCScanThread::Instance() as otherwise sandbox complains |
| // about multiple threads running on sandbox initialization. |
| is_initialized_ = true; |
| } |
| |
| void PCScanInternal::PerformScan(PCScan::InvocationMode invocation_mode) { |
| #if PA_SCAN_DCHECK_IS_ON() |
| PA_DCHECK(is_initialized()); |
| PA_DCHECK(scannable_roots().size() > 0); |
| PA_DCHECK(std::all_of( |
| scannable_roots().begin(), scannable_roots().end(), |
| [](const auto& pair) { return pair.first->IsScanEnabled(); })); |
| PA_DCHECK(std::all_of( |
| nonscannable_roots().begin(), nonscannable_roots().end(), |
| [](const auto& pair) { return pair.first->IsQuarantineEnabled(); })); |
| #endif |
| |
| PCScan& frontend = PCScan::Instance(); |
| { |
| // If scanning is already in progress, bail out. |
| PCScan::State expected = PCScan::State::kNotRunning; |
| if (!frontend.state_.compare_exchange_strong( |
| expected, PCScan::State::kScheduled, std::memory_order_acq_rel, |
| std::memory_order_relaxed)) { |
| return; |
| } |
| } |
| |
| const size_t last_quarantine_size = |
| frontend.scheduler_.scheduling_backend().ScanStarted(); |
| |
| // Create PCScan task and set it as current. |
| auto task = base::MakeRefCounted<PCScanTask>(frontend, last_quarantine_size); |
| PCScanInternal::Instance().SetCurrentPCScanTask(task); |
| |
| if (PA_UNLIKELY(invocation_mode == |
| PCScan::InvocationMode::kScheduleOnlyForTesting)) { |
| // Immediately change the state to enable safepoint testing. |
| frontend.state_.store(PCScan::State::kScanning, std::memory_order_release); |
| frontend.SetJoinableIfSafepointEnabled(true); |
| return; |
| } |
| |
| // Post PCScan task. |
| if (PA_LIKELY(invocation_mode == PCScan::InvocationMode::kNonBlocking)) { |
| PCScan::PCScanThread::Instance().PostTask(std::move(task)); |
| } else { |
| PA_SCAN_DCHECK(PCScan::InvocationMode::kBlocking == invocation_mode || |
| PCScan::InvocationMode::kForcedBlocking == invocation_mode); |
| std::move(*task).RunFromScanner(); |
| } |
| } |
| |
| void PCScanInternal::PerformScanIfNeeded( |
| PCScan::InvocationMode invocation_mode) { |
| if (!scannable_roots().size()) { |
| return; |
| } |
| PCScan& frontend = PCScan::Instance(); |
| if (invocation_mode == PCScan::InvocationMode::kForcedBlocking || |
| frontend.scheduler_.scheduling_backend() |
| .GetQuarantineData() |
| .MinimumScanningThresholdReached()) { |
| PerformScan(invocation_mode); |
| } |
| } |
| |
| void PCScanInternal::PerformDelayedScan(base::TimeDelta delay) { |
| PCScan::PCScanThread::Instance().PostDelayedTask(delay); |
| } |
| |
| void PCScanInternal::JoinScan() { |
| // Current task can be destroyed by the scanner. Check that it's valid. |
| if (auto current_task = CurrentPCScanTask()) { |
| current_task->RunFromMutator(); |
| } |
| } |
| |
| PCScanInternal::TaskHandle PCScanInternal::CurrentPCScanTask() const { |
| std::lock_guard<std::mutex> lock(current_task_mutex_); |
| return current_task_; |
| } |
| |
| void PCScanInternal::SetCurrentPCScanTask(TaskHandle task) { |
| std::lock_guard<std::mutex> lock(current_task_mutex_); |
| current_task_ = std::move(task); |
| } |
| |
| void PCScanInternal::ResetCurrentPCScanTask() { |
| std::lock_guard<std::mutex> lock(current_task_mutex_); |
| current_task_.reset(); |
| } |
| |
| namespace { |
| PCScanInternal::SuperPages GetSuperPagesAndCommitStateBitmaps( |
| PCScan::Root& root) { |
| const size_t state_bitmap_size_to_commit = CommittedStateBitmapSize(); |
| PCScanInternal::SuperPages super_pages; |
| for (auto* super_page_extent = root.first_extent; super_page_extent; |
| super_page_extent = super_page_extent->next) { |
| for (uintptr_t super_page = SuperPagesBeginFromExtent(super_page_extent), |
| super_page_end = SuperPagesEndFromExtent(super_page_extent); |
| super_page != super_page_end; super_page += kSuperPageSize) { |
| // Make sure the metadata is committed. |
| // TODO(bikineev): Remove once this is known to work. |
| const volatile char* metadata = reinterpret_cast<char*>( |
| PartitionSuperPageToMetadataArea<ThreadSafe>(super_page)); |
| *metadata; |
| RecommitSystemPages(SuperPageStateBitmapAddr(super_page), |
| state_bitmap_size_to_commit, |
| PageAccessibilityConfiguration( |
| PageAccessibilityConfiguration::kReadWrite), |
| PageAccessibilityDisposition::kRequireUpdate); |
| super_pages.push_back(super_page); |
| } |
| } |
| return super_pages; |
| } |
| } // namespace |
| |
| void PCScanInternal::RegisterScannableRoot(Root* root) { |
| PA_DCHECK(is_initialized()); |
| PA_DCHECK(root); |
| // Avoid nesting locks and store super_pages in a temporary vector. |
| SuperPages super_pages; |
| { |
| ::partition_alloc::internal::ScopedGuard guard(root->lock_); |
| PA_CHECK(root->IsQuarantineAllowed()); |
| if (root->IsScanEnabled()) { |
| return; |
| } |
| PA_CHECK(!root->IsQuarantineEnabled()); |
| super_pages = GetSuperPagesAndCommitStateBitmaps(*root); |
| root->flags.scan_mode = Root::ScanMode::kEnabled; |
| root->flags.quarantine_mode = Root::QuarantineMode::kEnabled; |
| } |
| std::lock_guard<std::mutex> lock(roots_mutex_); |
| PA_DCHECK(!scannable_roots_.count(root)); |
| auto& root_super_pages = scannable_roots_[root]; |
| root_super_pages.insert(root_super_pages.end(), super_pages.begin(), |
| super_pages.end()); |
| } |
| |
| void PCScanInternal::RegisterNonScannableRoot(Root* root) { |
| PA_DCHECK(is_initialized()); |
| PA_DCHECK(root); |
| // Avoid nesting locks and store super_pages in a temporary vector. |
| SuperPages super_pages; |
| { |
| ::partition_alloc::internal::ScopedGuard guard(root->lock_); |
| PA_CHECK(root->IsQuarantineAllowed()); |
| PA_CHECK(!root->IsScanEnabled()); |
| if (root->IsQuarantineEnabled()) { |
| return; |
| } |
| super_pages = GetSuperPagesAndCommitStateBitmaps(*root); |
| root->flags.quarantine_mode = Root::QuarantineMode::kEnabled; |
| } |
| std::lock_guard<std::mutex> lock(roots_mutex_); |
| PA_DCHECK(!nonscannable_roots_.count(root)); |
| auto& root_super_pages = nonscannable_roots_[root]; |
| root_super_pages.insert(root_super_pages.end(), super_pages.begin(), |
| super_pages.end()); |
| } |
| |
| void PCScanInternal::RegisterNewSuperPage(Root* root, |
| uintptr_t super_page_base) { |
| PA_DCHECK(is_initialized()); |
| PA_DCHECK(root); |
| PA_CHECK(root->IsQuarantineAllowed()); |
| PA_DCHECK(!(super_page_base % kSuperPageAlignment)); |
| // Make sure the metadata is committed. |
| // TODO(bikineev): Remove once this is known to work. |
| const volatile char* metadata = reinterpret_cast<char*>( |
| PartitionSuperPageToMetadataArea<ThreadSafe>(super_page_base)); |
| *metadata; |
| |
| std::lock_guard<std::mutex> lock(roots_mutex_); |
| |
| // Dispatch based on whether root is scannable or not. |
| if (root->IsScanEnabled()) { |
| PA_DCHECK(scannable_roots_.count(root)); |
| auto& super_pages = scannable_roots_[root]; |
| PA_DCHECK(std::find(super_pages.begin(), super_pages.end(), |
| super_page_base) == super_pages.end()); |
| super_pages.push_back(super_page_base); |
| } else { |
| PA_DCHECK(root->IsQuarantineEnabled()); |
| PA_DCHECK(nonscannable_roots_.count(root)); |
| auto& super_pages = nonscannable_roots_[root]; |
| PA_DCHECK(std::find(super_pages.begin(), super_pages.end(), |
| super_page_base) == super_pages.end()); |
| super_pages.push_back(super_page_base); |
| } |
| } |
| |
| void PCScanInternal::SetProcessName(const char* process_name) { |
| PA_DCHECK(is_initialized()); |
| PA_DCHECK(process_name); |
| PA_DCHECK(!process_name_); |
| process_name_ = process_name; |
| } |
| |
| size_t PCScanInternal::CalculateTotalHeapSize() const { |
| PA_DCHECK(is_initialized()); |
| std::lock_guard<std::mutex> lock(roots_mutex_); |
| const auto acc = [](size_t size, const auto& pair) { |
| return size + pair.first->get_total_size_of_committed_pages(); |
| }; |
| return std::accumulate(scannable_roots_.begin(), scannable_roots_.end(), 0u, |
| acc) + |
| std::accumulate(nonscannable_roots_.begin(), nonscannable_roots_.end(), |
| 0u, acc); |
| } |
| |
| void PCScanInternal::EnableStackScanning() { |
| PA_DCHECK(!stack_scanning_enabled_); |
| stack_scanning_enabled_ = true; |
| } |
| void PCScanInternal::DisableStackScanning() { |
| PA_DCHECK(stack_scanning_enabled_); |
| stack_scanning_enabled_ = false; |
| } |
| bool PCScanInternal::IsStackScanningEnabled() const { |
| return stack_scanning_enabled_; |
| } |
| |
| void PCScanInternal::NotifyThreadCreated(void* stack_top) { |
| const auto tid = base::PlatformThread::CurrentId(); |
| std::lock_guard<std::mutex> lock(stack_tops_mutex_); |
| const auto res = stack_tops_.insert({tid, stack_top}); |
| PA_DCHECK(res.second); |
| } |
| |
| void PCScanInternal::NotifyThreadDestroyed() { |
| const auto tid = base::PlatformThread::CurrentId(); |
| std::lock_guard<std::mutex> lock(stack_tops_mutex_); |
| PA_DCHECK(1 == stack_tops_.count(tid)); |
| stack_tops_.erase(tid); |
| } |
| |
| void* PCScanInternal::GetCurrentThreadStackTop() const { |
| const auto tid = base::PlatformThread::CurrentId(); |
| std::lock_guard<std::mutex> lock(stack_tops_mutex_); |
| auto it = stack_tops_.find(tid); |
| return it != stack_tops_.end() ? it->second : nullptr; |
| } |
| |
| bool PCScanInternal::WriteProtectionEnabled() const { |
| return write_protector_->IsEnabled(); |
| } |
| |
| void PCScanInternal::ProtectPages(uintptr_t begin, size_t size) { |
| // Slot-span sizes are multiple of system page size. However, the ranges that |
| // are recorded are not, since in the snapshot we only record the used |
| // payload. Therefore we align up the incoming range by 4k. The unused part of |
| // slot-spans doesn't need to be protected (the allocator will enter the |
| // safepoint before trying to allocate from it). |
| PA_SCAN_DCHECK(write_protector_.get()); |
| write_protector_->ProtectPages( |
| begin, |
| partition_alloc::internal::base::bits::AlignUp(size, SystemPageSize())); |
| } |
| |
| void PCScanInternal::UnprotectPages(uintptr_t begin, size_t size) { |
| PA_SCAN_DCHECK(write_protector_.get()); |
| write_protector_->UnprotectPages( |
| begin, |
| partition_alloc::internal::base::bits::AlignUp(size, SystemPageSize())); |
| } |
| |
| void PCScanInternal::ClearRootsForTesting() { |
| std::lock_guard<std::mutex> lock(roots_mutex_); |
| // Set all roots as non-scannable and non-quarantinable. |
| for (auto& pair : scannable_roots_) { |
| Root* root = pair.first; |
| root->flags.scan_mode = Root::ScanMode::kDisabled; |
| root->flags.quarantine_mode = Root::QuarantineMode::kDisabledByDefault; |
| } |
| for (auto& pair : nonscannable_roots_) { |
| Root* root = pair.first; |
| root->flags.quarantine_mode = Root::QuarantineMode::kDisabledByDefault; |
| } |
| // Make sure to destroy maps so that on the following ReinitForTesting() call |
| // the maps don't attempt to destroy the backing. |
| scannable_roots_.clear(); |
| scannable_roots_.~RootsMap(); |
| nonscannable_roots_.clear(); |
| nonscannable_roots_.~RootsMap(); |
| // Destroy write protector object, so that there is no double free on the next |
| // call to ReinitForTesting(); |
| write_protector_.reset(); |
| } |
| |
| void PCScanInternal::ReinitForTesting(PCScan::InitConfig config) { |
| is_initialized_ = false; |
| auto* new_this = new (this) PCScanInternal; |
| new_this->Initialize(config); |
| } |
| |
| void PCScanInternal::FinishScanForTesting() { |
| auto current_task = CurrentPCScanTask(); |
| PA_CHECK(current_task.get()); |
| current_task->RunFromScanner(); |
| } |
| |
| void PCScanInternal::RegisterStatsReporter( |
| partition_alloc::StatsReporter* reporter) { |
| PA_DCHECK(reporter); |
| stats_reporter_ = reporter; |
| } |
| |
| partition_alloc::StatsReporter& PCScanInternal::GetReporter() { |
| PA_DCHECK(stats_reporter_); |
| return *stats_reporter_; |
| } |
| |
| } // namespace partition_alloc::internal |