1 // Copyright 2023 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 #ifndef BASE_ALLOCATOR_PARTITION_ALLOCATOR_SRC_PARTITION_ALLOC_POOL_OFFSET_FREELIST_H_ 6 #define BASE_ALLOCATOR_PARTITION_ALLOCATOR_SRC_PARTITION_ALLOC_POOL_OFFSET_FREELIST_H_ 7 8 #include <cstddef> 9 #include <cstdint> 10 11 #include "partition_alloc/partition_address_space.h" 12 #include "partition_alloc/partition_alloc-inl.h" 13 #include "partition_alloc/partition_alloc_base/compiler_specific.h" 14 15 namespace partition_alloc::internal { 16 17 // This implementation of PartitionAlloc's freelist uses pool offsets 18 // rather than naked pointers. This is intended to prevent usage of 19 // freelist pointers to easily jump around to freed slots. 20 class PoolOffsetFreelistEntry { 21 private: PoolOffsetFreelistEntry(std::nullptr_t)22 constexpr explicit PoolOffsetFreelistEntry(std::nullptr_t) {} 23 PoolOffsetFreelistEntry(PoolOffsetFreelistEntry * next)24 explicit PoolOffsetFreelistEntry(PoolOffsetFreelistEntry* next) 25 : next_(PoolOffset(reinterpret_cast<uintptr_t>(next))) {} 26 27 // For testing only. PoolOffsetFreelistEntry(void * next,bool make_shadow_match)28 PoolOffsetFreelistEntry(void* next, bool make_shadow_match) 29 : next_(PoolOffset(reinterpret_cast<uintptr_t>(next))) {} 30 31 public: 32 ~PoolOffsetFreelistEntry() = delete; 33 EmplaceAndInitNull(void * slot_start_tagged)34 PA_ALWAYS_INLINE static PoolOffsetFreelistEntry* EmplaceAndInitNull( 35 void* slot_start_tagged) { 36 auto* entry = new (slot_start_tagged) PoolOffsetFreelistEntry(nullptr); 37 return entry; 38 } 39 EmplaceAndInitNull(uintptr_t slot_start)40 PA_ALWAYS_INLINE static PoolOffsetFreelistEntry* EmplaceAndInitNull( 41 uintptr_t slot_start) { 42 return EmplaceAndInitNull(SlotStartAddr2Ptr(slot_start)); 43 } 44 EmplaceAndInitForThreadCache(uintptr_t slot_start,PoolOffsetFreelistEntry * next)45 PA_ALWAYS_INLINE static PoolOffsetFreelistEntry* EmplaceAndInitForThreadCache( 46 uintptr_t slot_start, 47 PoolOffsetFreelistEntry* next) { 48 auto* entry = 49 new (SlotStartAddr2Ptr(slot_start)) PoolOffsetFreelistEntry(next); 50 return entry; 51 } 52 EmplaceAndInitForTest(uintptr_t slot_start,void * next,bool make_shadow_match)53 PA_ALWAYS_INLINE static void EmplaceAndInitForTest(uintptr_t slot_start, 54 void* next, 55 bool make_shadow_match) { 56 new (SlotStartAddr2Ptr(slot_start)) 57 PoolOffsetFreelistEntry(next, make_shadow_match); 58 } 59 CorruptNextForTesting(uintptr_t v)60 void CorruptNextForTesting(uintptr_t v) { 61 // TODO(crbug.com/1461983): Make this do something useful. 62 next_ += 1ull << 31; 63 } 64 65 template <bool crash_on_corruption> GetNextForThreadCache(size_t slot_size)66 PA_ALWAYS_INLINE PoolOffsetFreelistEntry* GetNextForThreadCache( 67 size_t slot_size) const { 68 return GetNextInternal<crash_on_corruption, /*for_thread_cache=*/true>( 69 slot_size); 70 } 71 GetNext(size_t slot_size)72 PA_ALWAYS_INLINE PoolOffsetFreelistEntry* GetNext(size_t slot_size) const { 73 return GetNextInternal<true, /*for_thread_cache=*/false>(slot_size); 74 } 75 CheckFreeList(size_t slot_size)76 PA_NOINLINE void CheckFreeList(size_t slot_size) const { 77 for (auto* entry = this; entry; entry = entry->GetNext(slot_size)) { 78 // `GetNext()` calls `IsWellFormed()`. 79 } 80 } 81 CheckFreeListForThreadCache(size_t slot_size)82 PA_NOINLINE void CheckFreeListForThreadCache(size_t slot_size) const { 83 for (auto* entry = this; entry; 84 entry = entry->GetNextForThreadCache<true>(slot_size)) { 85 // `GetNextForThreadCache()` calls `IsWellFormed()`. 86 } 87 } 88 SetNext(PoolOffsetFreelistEntry * entry)89 PA_ALWAYS_INLINE void SetNext(PoolOffsetFreelistEntry* entry) { 90 next_ = PoolOffset(reinterpret_cast<uintptr_t>(entry)); 91 } 92 ClearForAllocation()93 PA_ALWAYS_INLINE uintptr_t ClearForAllocation() { 94 next_ = uintptr_t{0}; 95 return SlotStartPtr2Addr(this); 96 } 97 IsEncodedNextPtrZero()98 PA_ALWAYS_INLINE constexpr bool IsEncodedNextPtrZero() const { 99 return !next_; 100 } 101 102 private: 103 // Determines the containing pool of `addr` and returns `addr` 104 // represented as an offset into that pool. PoolOffset(uintptr_t addr)105 PA_ALWAYS_INLINE static uintptr_t PoolOffset(uintptr_t addr) { 106 return addr ? PartitionAddressSpace::GetPoolInfo(addr).offset : addr; 107 } 108 109 template <bool crash_on_corruption, bool for_thread_cache> GetNextInternal(size_t slot_size)110 PA_ALWAYS_INLINE PoolOffsetFreelistEntry* GetNextInternal( 111 size_t slot_size) const { 112 if (IsEncodedNextPtrZero()) { 113 return nullptr; 114 } 115 116 auto* ret = reinterpret_cast<PoolOffsetFreelistEntry*>( 117 GetPoolInfo(reinterpret_cast<uintptr_t>(this)).base + next_); 118 if (PA_UNLIKELY(!IsWellFormed<for_thread_cache>(this, ret))) { 119 if constexpr (crash_on_corruption) { 120 PA_DEBUG_DATA_ON_STACK("first", static_cast<size_t>(next_)); 121 FreelistCorruptionDetected(slot_size); 122 } 123 return nullptr; 124 } 125 PA_PREFETCH(ret); 126 return ret; 127 } 128 129 // TODO(crbug.com/1461983): Add support for freelist shadow entries 130 // (and freeslot bitmaps). 131 template <bool for_thread_cache> IsWellFormed(const PoolOffsetFreelistEntry * here,const PoolOffsetFreelistEntry * next)132 PA_ALWAYS_INLINE static bool IsWellFormed( 133 const PoolOffsetFreelistEntry* here, 134 const PoolOffsetFreelistEntry* next) { 135 const uintptr_t here_address = SlotStartPtr2Addr(here); 136 const uintptr_t next_address = SlotStartPtr2Addr(next); 137 138 const bool not_in_metadata = 139 (next_address & kSuperPageOffsetMask) >= PartitionPageSize(); 140 if constexpr (for_thread_cache) { 141 return not_in_metadata; 142 } 143 const bool same_super_page = (here_address & kSuperPageBaseMask) == 144 (next_address & kSuperPageBaseMask); 145 return same_super_page && not_in_metadata; 146 } 147 148 // Expresses the next entry in the freelist as an offset in the 149 // same pool as `this`, except when 0, which (as an invalid pool 150 // offset) serves as a sentinel value. 151 uintptr_t next_ = uintptr_t{0}; 152 }; 153 154 } // namespace partition_alloc::internal 155 156 #endif // BASE_ALLOCATOR_PARTITION_ALLOCATOR_SRC_PARTITION_ALLOC_POOL_OFFSET_FREELIST_H_ 157