reservation_offset_table.h 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256
  1. // Copyright (c) 2021 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. #ifndef BASE_ALLOCATOR_PARTITION_ALLOCATOR_RESERVATION_OFFSET_TABLE_H_
  5. #define BASE_ALLOCATOR_PARTITION_ALLOCATOR_RESERVATION_OFFSET_TABLE_H_
  6. #include <cstddef>
  7. #include <cstdint>
  8. #include <limits>
  9. #include <tuple>
  10. #include "base/allocator/partition_allocator/address_pool_manager.h"
  11. #include "base/allocator/partition_allocator/partition_address_space.h"
  12. #include "base/allocator/partition_allocator/partition_alloc_base/compiler_specific.h"
  13. #include "base/allocator/partition_allocator/partition_alloc_base/component_export.h"
  14. #include "base/allocator/partition_allocator/partition_alloc_base/debug/debugging_buildflags.h"
  15. #include "base/allocator/partition_allocator/partition_alloc_buildflags.h"
  16. #include "base/allocator/partition_allocator/partition_alloc_check.h"
  17. #include "base/allocator/partition_allocator/partition_alloc_constants.h"
  18. #include "base/allocator/partition_allocator/tagging.h"
  19. #include "build/build_config.h"
  20. namespace partition_alloc::internal {
  21. static constexpr uint16_t kOffsetTagNotAllocated =
  22. std::numeric_limits<uint16_t>::max();
  23. static constexpr uint16_t kOffsetTagNormalBuckets =
  24. std::numeric_limits<uint16_t>::max() - 1;
  25. // The main purpose of the reservation offset table is to easily locate the
  26. // direct map reservation start address for any given address. There is one
  27. // entry in the table for each super page.
  28. //
  29. // When PartitionAlloc reserves an address region it is always aligned to
  30. // super page boundary. However, in 32-bit mode, the size may not be aligned
  31. // super-page-aligned, so it may look like this:
  32. // |<--------- actual reservation size --------->|
  33. // +----------+----------+-----+-----------+-----+ - - - +
  34. // |SuperPage0|SuperPage1| ... |SuperPage K|SuperPage K+1|
  35. // +----------+----------+-----+-----------+-----+ - - -.+
  36. // |<-X->|<-Y*)->|
  37. //
  38. // The table entries for reserved super pages say how many pages away from the
  39. // reservation the super page is:
  40. // +----------+----------+-----+-----------+-------------+
  41. // |Entry for |Entry for | ... |Entry for |Entry for |
  42. // |SuperPage0|SuperPage1| |SuperPage K|SuperPage K+1|
  43. // +----------+----------+-----+-----------+-------------+
  44. // | 0 | 1 | ... | K | K + 1 |
  45. // +----------+----------+-----+-----------+-------------+
  46. //
  47. // For an address Z, the reservation start can be found using this formula:
  48. // ((Z >> kSuperPageShift) - (the entry for Z)) << kSuperPageShift
  49. //
  50. // kOffsetTagNotAllocated is a special tag denoting that the super page isn't
  51. // allocated by PartitionAlloc and kOffsetTagNormalBuckets denotes that it is
  52. // used for a normal-bucket allocation, not for a direct-map allocation.
  53. //
  54. // *) In 32-bit mode, Y is not used by PartitionAlloc, and cannot be used
  55. // until X is unreserved, because PartitionAlloc always uses kSuperPageSize
  56. // alignment when reserving address spaces. One can use "GigaCage" to
  57. // further determine which part of the supe page is used by PartitionAlloc.
  58. // This isn't a problem in 64-bit mode, where allocation granularity is
  59. // kSuperPageSize.
  60. class PA_COMPONENT_EXPORT(PARTITION_ALLOC) ReservationOffsetTable {
  61. public:
  62. #if defined(PA_HAS_64_BITS_POINTERS)
  63. // There is one reservation offset table per Pool in 64-bit mode.
  64. static constexpr size_t kReservationOffsetTableCoverage = kPoolMaxSize;
  65. static constexpr size_t kReservationOffsetTableLength =
  66. kReservationOffsetTableCoverage >> kSuperPageShift;
  67. #else
  68. // The size of the reservation offset table should cover the entire 32-bit
  69. // address space, one element per super page.
  70. static constexpr uint64_t kGiB = 1024 * 1024 * 1024ull;
  71. static constexpr size_t kReservationOffsetTableLength =
  72. 4 * kGiB / kSuperPageSize;
  73. #endif
  74. static_assert(kReservationOffsetTableLength < kOffsetTagNormalBuckets,
  75. "Offsets should be smaller than kOffsetTagNormalBuckets.");
  76. static struct _ReservationOffsetTable {
  77. // The number of table elements is less than MAX_UINT16, so the element type
  78. // can be uint16_t.
  79. static_assert(
  80. kReservationOffsetTableLength <= std::numeric_limits<uint16_t>::max(),
  81. "Length of the reservation offset table must be less than MAX_UINT16");
  82. uint16_t offsets[kReservationOffsetTableLength] = {};
  83. constexpr _ReservationOffsetTable() {
  84. for (uint16_t& offset : offsets)
  85. offset = kOffsetTagNotAllocated;
  86. }
  87. #if defined(PA_HAS_64_BITS_POINTERS)
  88. // One table per Pool.
  89. } reservation_offset_tables_[kNumPools];
  90. #else
  91. // A single table for the entire 32-bit address space.
  92. } reservation_offset_table_;
  93. #endif
  94. };
  95. #if defined(PA_HAS_64_BITS_POINTERS)
  96. PA_ALWAYS_INLINE uint16_t* GetReservationOffsetTable(pool_handle handle) {
  97. PA_DCHECK(0 < handle && handle <= kNumPools);
  98. return ReservationOffsetTable::reservation_offset_tables_[handle - 1].offsets;
  99. }
  100. PA_ALWAYS_INLINE const uint16_t* GetReservationOffsetTableEnd(
  101. pool_handle handle) {
  102. return GetReservationOffsetTable(handle) +
  103. ReservationOffsetTable::kReservationOffsetTableLength;
  104. }
  105. PA_ALWAYS_INLINE uint16_t* GetReservationOffsetTable(uintptr_t address) {
  106. pool_handle handle = GetPool(address);
  107. return GetReservationOffsetTable(handle);
  108. }
  109. PA_ALWAYS_INLINE const uint16_t* GetReservationOffsetTableEnd(
  110. uintptr_t address) {
  111. pool_handle handle = GetPool(address);
  112. return GetReservationOffsetTableEnd(handle);
  113. }
  114. PA_ALWAYS_INLINE uint16_t* ReservationOffsetPointer(pool_handle pool,
  115. uintptr_t offset_in_pool) {
  116. size_t table_index = offset_in_pool >> kSuperPageShift;
  117. PA_DCHECK(table_index <
  118. ReservationOffsetTable::kReservationOffsetTableLength);
  119. return GetReservationOffsetTable(pool) + table_index;
  120. }
  121. #else
  122. PA_ALWAYS_INLINE uint16_t* GetReservationOffsetTable(uintptr_t address) {
  123. return ReservationOffsetTable::reservation_offset_table_.offsets;
  124. }
  125. PA_ALWAYS_INLINE const uint16_t* GetReservationOffsetTableEnd(
  126. uintptr_t address) {
  127. return ReservationOffsetTable::reservation_offset_table_.offsets +
  128. ReservationOffsetTable::kReservationOffsetTableLength;
  129. }
  130. #endif
  131. PA_ALWAYS_INLINE uint16_t* ReservationOffsetPointer(uintptr_t address) {
  132. #if defined(PA_HAS_64_BITS_POINTERS)
  133. // In 64-bit mode, find the owning Pool and compute the offset from its base.
  134. auto [pool, offset] = GetPoolAndOffset(address);
  135. return ReservationOffsetPointer(pool, offset);
  136. #else
  137. size_t table_index = address >> kSuperPageShift;
  138. PA_DCHECK(table_index <
  139. ReservationOffsetTable::kReservationOffsetTableLength);
  140. return GetReservationOffsetTable(address) + table_index;
  141. #endif
  142. }
  143. PA_ALWAYS_INLINE uintptr_t ComputeReservationStart(uintptr_t address,
  144. uint16_t* offset_ptr) {
  145. return (address & kSuperPageBaseMask) -
  146. (static_cast<size_t>(*offset_ptr) << kSuperPageShift);
  147. }
  148. // If the given address doesn't point to direct-map allocated memory,
  149. // returns 0.
  150. PA_ALWAYS_INLINE uintptr_t GetDirectMapReservationStart(uintptr_t address) {
  151. #if BUILDFLAG(PA_DCHECK_IS_ON)
  152. bool is_in_brp_pool = IsManagedByPartitionAllocBRPPool(address);
  153. bool is_in_regular_pool = IsManagedByPartitionAllocRegularPool(address);
  154. // When USE_BACKUP_REF_PTR is off, BRP pool isn't used.
  155. #if !BUILDFLAG(USE_BACKUP_REF_PTR)
  156. PA_DCHECK(!is_in_brp_pool);
  157. #endif
  158. #endif // BUILDFLAG(PA_DCHECK_IS_ON)
  159. uint16_t* offset_ptr = ReservationOffsetPointer(address);
  160. PA_DCHECK(*offset_ptr != kOffsetTagNotAllocated);
  161. if (*offset_ptr == kOffsetTagNormalBuckets)
  162. return 0;
  163. uintptr_t reservation_start = ComputeReservationStart(address, offset_ptr);
  164. #if BUILDFLAG(PA_DCHECK_IS_ON)
  165. // Make sure the reservation start is in the same pool as |address|.
  166. // In the 32-bit mode, the beginning of a reservation may be excluded from the
  167. // BRP pool, so shift the pointer. The other pools don't have this logic.
  168. PA_DCHECK(is_in_brp_pool ==
  169. IsManagedByPartitionAllocBRPPool(
  170. reservation_start
  171. #if !defined(PA_HAS_64_BITS_POINTERS)
  172. + AddressPoolManagerBitmap::kBytesPer1BitOfBRPPoolBitmap *
  173. AddressPoolManagerBitmap::kGuardOffsetOfBRPPoolBitmap
  174. #endif // !defined(PA_HAS_64_BITS_POINTERS)
  175. ));
  176. PA_DCHECK(is_in_regular_pool ==
  177. IsManagedByPartitionAllocRegularPool(reservation_start));
  178. PA_DCHECK(*ReservationOffsetPointer(reservation_start) == 0);
  179. #endif // BUILDFLAG(PA_DCHECK_IS_ON)
  180. return reservation_start;
  181. }
  182. #if defined(PA_HAS_64_BITS_POINTERS)
  183. // If the given address doesn't point to direct-map allocated memory,
  184. // returns 0.
  185. // This variant has better performance than the regular one on 64-bit builds if
  186. // the Pool that an allocation belongs to is known.
  187. PA_ALWAYS_INLINE uintptr_t
  188. GetDirectMapReservationStart(uintptr_t address,
  189. pool_handle pool,
  190. uintptr_t offset_in_pool) {
  191. PA_DCHECK(AddressPoolManager::GetInstance().GetPoolBaseAddress(pool) +
  192. offset_in_pool ==
  193. address);
  194. uint16_t* offset_ptr = ReservationOffsetPointer(pool, offset_in_pool);
  195. PA_DCHECK(*offset_ptr != kOffsetTagNotAllocated);
  196. if (*offset_ptr == kOffsetTagNormalBuckets)
  197. return 0;
  198. uintptr_t reservation_start = ComputeReservationStart(address, offset_ptr);
  199. PA_DCHECK(*ReservationOffsetPointer(reservation_start) == 0);
  200. return reservation_start;
  201. }
  202. #endif // defined(PA_HAS_64_BITS_POINTERS)
  203. // Returns true if |address| is the beginning of the first super page of a
  204. // reservation, i.e. either a normal bucket super page, or the first super page
  205. // of direct map.
  206. // |address| must belong to an allocated super page.
  207. PA_ALWAYS_INLINE bool IsReservationStart(uintptr_t address) {
  208. uint16_t* offset_ptr = ReservationOffsetPointer(address);
  209. PA_DCHECK(*offset_ptr != kOffsetTagNotAllocated);
  210. return ((*offset_ptr == kOffsetTagNormalBuckets) || (*offset_ptr == 0)) &&
  211. (address % kSuperPageSize == 0);
  212. }
  213. // Returns true if |address| belongs to a normal bucket super page.
  214. PA_ALWAYS_INLINE bool IsManagedByNormalBuckets(uintptr_t address) {
  215. uint16_t* offset_ptr = ReservationOffsetPointer(address);
  216. return *offset_ptr == kOffsetTagNormalBuckets;
  217. }
  218. // Returns true if |address| belongs to a direct map region.
  219. PA_ALWAYS_INLINE bool IsManagedByDirectMap(uintptr_t address) {
  220. uint16_t* offset_ptr = ReservationOffsetPointer(address);
  221. return *offset_ptr != kOffsetTagNormalBuckets &&
  222. *offset_ptr != kOffsetTagNotAllocated;
  223. }
  224. // Returns true if |address| belongs to a normal bucket super page or a direct
  225. // map region, i.e. belongs to an allocated super page.
  226. PA_ALWAYS_INLINE bool IsManagedByNormalBucketsOrDirectMap(uintptr_t address) {
  227. uint16_t* offset_ptr = ReservationOffsetPointer(address);
  228. return *offset_ptr != kOffsetTagNotAllocated;
  229. }
  230. } // namespace partition_alloc::internal
  231. #endif // BASE_ALLOCATOR_PARTITION_ALLOCATOR_RESERVATION_OFFSET_TABLE_H_