1 // Copyright 2018 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 "partition_alloc/partition_page.h"
6
7 #include <algorithm>
8 #include <cstdint>
9
10 #include "partition_alloc/address_pool_manager.h"
11 #include "partition_alloc/freeslot_bitmap.h"
12 #include "partition_alloc/page_allocator.h"
13 #include "partition_alloc/page_allocator_constants.h"
14 #include "partition_alloc/partition_address_space.h"
15 #include "partition_alloc/partition_alloc_base/bits.h"
16 #include "partition_alloc/partition_alloc_base/compiler_specific.h"
17 #include "partition_alloc/partition_alloc_base/debug/debugging_buildflags.h"
18 #include "partition_alloc/partition_alloc_buildflags.h"
19 #include "partition_alloc/partition_alloc_check.h"
20 #include "partition_alloc/partition_alloc_constants.h"
21 #include "partition_alloc/partition_alloc_forward.h"
22 #include "partition_alloc/partition_direct_map_extent.h"
23 #include "partition_alloc/partition_freelist_entry.h"
24 #include "partition_alloc/partition_root.h"
25 #include "partition_alloc/reservation_offset_table.h"
26 #include "partition_alloc/tagging.h"
27
28 namespace partition_alloc::internal {
29
30 namespace {
31
32 void UnmapNow(uintptr_t reservation_start,
33 size_t reservation_size,
34 pool_handle pool);
35
PartitionDirectUnmap(SlotSpanMetadata * slot_span)36 PA_ALWAYS_INLINE void PartitionDirectUnmap(SlotSpanMetadata* slot_span) {
37 auto* root = PartitionRoot::FromSlotSpanMetadata(slot_span);
38 PartitionRootLock(root).AssertAcquired();
39 auto* extent = PartitionDirectMapExtent::FromSlotSpanMetadata(slot_span);
40
41 // Maintain the doubly-linked list of all direct mappings.
42 if (extent->prev_extent) {
43 PA_DCHECK(extent->prev_extent->next_extent == extent);
44 extent->prev_extent->next_extent = extent->next_extent;
45 } else {
46 root->direct_map_list = extent->next_extent;
47 }
48 if (extent->next_extent) {
49 PA_DCHECK(extent->next_extent->prev_extent == extent);
50 extent->next_extent->prev_extent = extent->prev_extent;
51 }
52
53 // The actual decommit is deferred below after releasing the lock.
54 root->DecreaseCommittedPages(slot_span->bucket->slot_size);
55
56 size_t reservation_size = extent->reservation_size;
57 PA_DCHECK(!(reservation_size & DirectMapAllocationGranularityOffsetMask()));
58 PA_DCHECK(root->total_size_of_direct_mapped_pages >= reservation_size);
59 root->total_size_of_direct_mapped_pages -= reservation_size;
60
61 uintptr_t reservation_start = SlotSpanMetadata::ToSlotSpanStart(slot_span);
62 // The mapping may start at an unspecified location within a super page, but
63 // we always reserve memory aligned to super page size.
64 reservation_start = base::bits::AlignDown(reservation_start, kSuperPageSize);
65
66 // All the metadata have been updated above, in particular the mapping has
67 // been unlinked. We can safely release the memory outside the lock, which is
68 // important as decommitting memory can be expensive.
69 //
70 // This can create a fake "address space exhaustion" OOM, in the case where
71 // e.g. a large allocation is freed on a thread, and another large one is made
72 // from another *before* UnmapNow() has finished running. In this case the
73 // second one may not find enough space in the pool, and fail. This is
74 // expected to be very rare though, and likely preferable to holding the lock
75 // while releasing the address space.
76 ScopedUnlockGuard unlock{PartitionRootLock(root)};
77 ScopedSyscallTimer timer{root};
78 UnmapNow(reservation_start, reservation_size, root->ChoosePool());
79 }
80
81 } // namespace
82
RegisterEmpty()83 PA_ALWAYS_INLINE void SlotSpanMetadata::RegisterEmpty() {
84 PA_DCHECK(is_empty());
85 auto* root = PartitionRoot::FromSlotSpanMetadata(this);
86 PartitionRootLock(root).AssertAcquired();
87
88 root->empty_slot_spans_dirty_bytes +=
89 base::bits::AlignUp(GetProvisionedSize(), SystemPageSize());
90
91 ToSuperPageExtent()->DecrementNumberOfNonemptySlotSpans();
92
93 // If the slot span is already registered as empty, don't do anything. This
94 // prevents continually reusing a slot span from decommitting a bunch of other
95 // slot spans.
96 if (in_empty_cache_) {
97 return;
98 }
99
100 PA_DCHECK(root->global_empty_slot_span_ring_index <
101 root->global_empty_slot_span_ring_size);
102 int16_t current_index = root->global_empty_slot_span_ring_index;
103 SlotSpanMetadata* slot_span_to_decommit =
104 root->global_empty_slot_span_ring[current_index];
105 // The slot span might well have been re-activated, filled up, etc. before we
106 // get around to looking at it here.
107 if (slot_span_to_decommit) {
108 slot_span_to_decommit->DecommitIfPossible(root);
109 }
110
111 // There should not be a slot span in the buffer at the position this is
112 // going into.
113 PA_DCHECK(!root->global_empty_slot_span_ring[current_index]);
114
115 // We put the empty slot span on our global list of "slot spans that were once
116 // empty", thus providing it a bit of breathing room to get re-used before we
117 // really free it. This reduces the number of system calls. Otherwise any
118 // free() from a single-slot slot span would lead to a syscall, for instance.
119 root->global_empty_slot_span_ring[current_index] = this;
120 empty_cache_index_ = current_index;
121 in_empty_cache_ = 1;
122 ++current_index;
123 if (current_index == root->global_empty_slot_span_ring_size) {
124 current_index = 0;
125 }
126 root->global_empty_slot_span_ring_index = current_index;
127
128 // Avoid wasting too much memory on empty slot spans. Note that we only divide
129 // by powers of two, since division can be very slow, and this path is taken
130 // for every single-slot slot span deallocation.
131 //
132 // Empty slot spans are also all decommitted with MemoryReclaimer, but it may
133 // never run, be delayed arbitrarily, and/or miss large memory spikes.
134 size_t max_empty_dirty_bytes =
135 root->total_size_of_committed_pages.load(std::memory_order_relaxed) >>
136 root->max_empty_slot_spans_dirty_bytes_shift;
137 if (root->empty_slot_spans_dirty_bytes > max_empty_dirty_bytes) {
138 root->ShrinkEmptySlotSpansRing(std::min(
139 root->empty_slot_spans_dirty_bytes / 2, max_empty_dirty_bytes));
140 }
141 }
142 // static
143 const SlotSpanMetadata SlotSpanMetadata::sentinel_slot_span_;
144
145 // static
get_sentinel_slot_span()146 const SlotSpanMetadata* SlotSpanMetadata::get_sentinel_slot_span() {
147 return &sentinel_slot_span_;
148 }
149
150 // static
get_sentinel_slot_span_non_const()151 SlotSpanMetadata* SlotSpanMetadata::get_sentinel_slot_span_non_const() {
152 return const_cast<SlotSpanMetadata*>(&sentinel_slot_span_);
153 }
154
SlotSpanMetadata(PartitionBucket * bucket)155 SlotSpanMetadata::SlotSpanMetadata(PartitionBucket* bucket)
156 : bucket(bucket), can_store_raw_size_(bucket->CanStoreRawSize()) {}
157
FreeSlowPath(size_t number_of_freed)158 void SlotSpanMetadata::FreeSlowPath(size_t number_of_freed) {
159 DCheckRootLockIsAcquired(PartitionRoot::FromSlotSpanMetadata(this));
160 PA_DCHECK(this != get_sentinel_slot_span());
161
162 // The caller has already modified |num_allocated_slots|. It is a
163 // responsibility of this function to react to it, and update the state. We
164 // can get here only if the slot span is marked full and/or is now empty. Both
165 // are possible at the same time, which can happen when the caller lowered
166 // |num_allocated_slots| from "all" to 0 (common for single-slot spans). First
167 // execute the "is marked full" path, as it sets up |active_slot_spans_head|
168 // in a way later needed for the "is empty" path.
169 if (marked_full) {
170 // Direct map slot spans aren't added to any lists, hence never marked full.
171 PA_DCHECK(!bucket->is_direct_mapped());
172 // Double check that the slot span was full.
173 PA_DCHECK(num_allocated_slots ==
174 bucket->get_slots_per_span() - number_of_freed);
175 marked_full = 0;
176 // Fully used slot span became partially used. It must be put back on the
177 // non-full list. Also make it the current slot span to increase the
178 // chances of it being filled up again. The old current slot span will be
179 // the next slot span.
180 PA_DCHECK(!next_slot_span);
181 if (PA_LIKELY(bucket->active_slot_spans_head != get_sentinel_slot_span())) {
182 next_slot_span = bucket->active_slot_spans_head;
183 }
184 bucket->active_slot_spans_head = this;
185 PA_CHECK(bucket->num_full_slot_spans); // Underflow.
186 --bucket->num_full_slot_spans;
187 }
188
189 if (PA_LIKELY(num_allocated_slots == 0)) {
190 // Slot span became fully unused.
191 if (PA_UNLIKELY(bucket->is_direct_mapped())) {
192 PartitionDirectUnmap(this);
193 return;
194 }
195
196 #if BUILDFLAG(PA_DCHECK_IS_ON)
197 const PartitionFreelistDispatcher* freelist_dispatcher =
198 PartitionRoot::FromSlotSpanMetadata(this)->get_freelist_dispatcher();
199 freelist_dispatcher->CheckFreeList(freelist_head, bucket->slot_size);
200 #endif // BUILDFLAG(PA_DCHECK_IS_ON)
201
202 // If it's the current active slot span, change it. We bounce the slot span
203 // to the empty list as a force towards defragmentation.
204 if (PA_LIKELY(this == bucket->active_slot_spans_head)) {
205 bucket->SetNewActiveSlotSpan();
206 }
207 PA_DCHECK(bucket->active_slot_spans_head != this);
208
209 if (CanStoreRawSize()) {
210 SetRawSize(0);
211 }
212
213 RegisterEmpty();
214 }
215 }
216
Decommit(PartitionRoot * root)217 void SlotSpanMetadata::Decommit(PartitionRoot* root) {
218 PartitionRootLock(root).AssertAcquired();
219 PA_DCHECK(is_empty());
220 PA_DCHECK(!bucket->is_direct_mapped());
221 uintptr_t slot_span_start = SlotSpanMetadata::ToSlotSpanStart(this);
222 // If lazy commit is enabled, only provisioned slots are committed.
223 size_t dirty_size =
224 base::bits::AlignUp(GetProvisionedSize(), SystemPageSize());
225 size_t size_to_decommit =
226 kUseLazyCommit ? dirty_size : bucket->get_bytes_per_span();
227
228 PA_DCHECK(root->empty_slot_spans_dirty_bytes >= dirty_size);
229 root->empty_slot_spans_dirty_bytes -= dirty_size;
230
231 // Not decommitted slot span must've had at least 1 allocation.
232 PA_DCHECK(size_to_decommit > 0);
233 root->DecommitSystemPagesForData(
234 slot_span_start, size_to_decommit,
235 PageAccessibilityDisposition::kAllowKeepForPerf);
236
237 #if BUILDFLAG(USE_FREESLOT_BITMAP)
238 FreeSlotBitmapReset(slot_span_start, slot_span_start + size_to_decommit,
239 bucket->slot_size);
240 #endif
241
242 // We actually leave the decommitted slot span in the active list. We'll sweep
243 // it on to the decommitted list when we next walk the active list.
244 // Pulling this trick enables us to use a singly-linked list for all
245 // cases, which is critical in keeping the slot span metadata structure down
246 // to 32 bytes in size.
247 SetFreelistHead(nullptr);
248 num_unprovisioned_slots = 0;
249 PA_DCHECK(is_decommitted());
250 PA_DCHECK(bucket);
251 }
252
DecommitIfPossible(PartitionRoot * root)253 void SlotSpanMetadata::DecommitIfPossible(PartitionRoot* root) {
254 PartitionRootLock(root).AssertAcquired();
255 PA_DCHECK(in_empty_cache_);
256 PA_DCHECK(empty_cache_index_ < kMaxFreeableSpans);
257 PA_DCHECK(this == root->global_empty_slot_span_ring[empty_cache_index_]);
258 in_empty_cache_ = 0;
259 if (is_empty()) {
260 Decommit(root);
261 }
262 root->global_empty_slot_span_ring[empty_cache_index_] = nullptr;
263 }
264
SortFreelist()265 void SlotSpanMetadata::SortFreelist() {
266 std::bitset<kMaxSlotsPerSlotSpan> free_slots;
267 uintptr_t slot_span_start = ToSlotSpanStart(this);
268
269 size_t num_provisioned_slots =
270 bucket->get_slots_per_span() - num_unprovisioned_slots;
271 PA_CHECK(num_provisioned_slots <= kMaxSlotsPerSlotSpan);
272
273 size_t num_free_slots = 0;
274 size_t slot_size = bucket->slot_size;
275
276 const PartitionFreelistDispatcher* freelist_dispatcher =
277 PartitionRoot::FromSlotSpanMetadata(this)->get_freelist_dispatcher();
278
279 for (PartitionFreelistEntry* head = freelist_head; head;
280 head = freelist_dispatcher->GetNext(head, slot_size)) {
281 ++num_free_slots;
282 size_t offset_in_slot_span = SlotStartPtr2Addr(head) - slot_span_start;
283 size_t slot_number = bucket->GetSlotNumber(offset_in_slot_span);
284 PA_DCHECK(slot_number < num_provisioned_slots);
285 free_slots[slot_number] = true;
286 }
287 PA_DCHECK(num_free_slots == GetFreelistLength());
288
289 // Empty or single-element list is always sorted.
290 if (num_free_slots > 1) {
291 PartitionFreelistEntry* back = nullptr;
292 PartitionFreelistEntry* head = nullptr;
293
294 for (size_t slot_number = 0; slot_number < num_provisioned_slots;
295 slot_number++) {
296 if (free_slots[slot_number]) {
297 uintptr_t slot_start = slot_span_start + (slot_size * slot_number);
298 auto* entry = freelist_dispatcher->EmplaceAndInitNull(slot_start);
299 if (!head) {
300 head = entry;
301 } else {
302 freelist_dispatcher->SetNext(back, entry);
303 }
304
305 back = entry;
306 }
307 }
308 SetFreelistHead(head);
309 }
310
311 freelist_is_sorted_ = true;
312 }
313
314 namespace {
315
UnmapNow(uintptr_t reservation_start,size_t reservation_size,pool_handle pool)316 void UnmapNow(uintptr_t reservation_start,
317 size_t reservation_size,
318 pool_handle pool) {
319 PA_DCHECK(reservation_start && reservation_size > 0);
320 #if BUILDFLAG(PA_DCHECK_IS_ON)
321 // When ENABLE_BACKUP_REF_PTR_SUPPORT is off, BRP pool isn't used.
322 #if BUILDFLAG(ENABLE_BACKUP_REF_PTR_SUPPORT)
323 if (pool == kBRPPoolHandle) {
324 // In 32-bit mode, the beginning of a reservation may be excluded from the
325 // BRP pool, so shift the pointer. Other pools don't have this logic.
326 #if BUILDFLAG(HAS_64_BIT_POINTERS)
327 PA_DCHECK(IsManagedByPartitionAllocBRPPool(reservation_start));
328 #else
329 PA_DCHECK(IsManagedByPartitionAllocBRPPool(
330 reservation_start +
331 AddressPoolManagerBitmap::kBytesPer1BitOfBRPPoolBitmap *
332 AddressPoolManagerBitmap::kGuardOffsetOfBRPPoolBitmap));
333 #endif // BUILDFLAG(HAS_64_BIT_POINTERS)
334
335 } else
336 #endif // BUILDFLAG(ENABLE_BACKUP_REF_PTR_SUPPORT)
337 {
338 const bool received_expected_pool_handle =
339 pool == kRegularPoolHandle
340 #if BUILDFLAG(ENABLE_THREAD_ISOLATION)
341 || pool == kThreadIsolatedPoolHandle
342 #endif
343 #if BUILDFLAG(HAS_64_BIT_POINTERS)
344 || (pool == kConfigurablePoolHandle && IsConfigurablePoolAvailable())
345 #endif
346 ;
347 PA_DCHECK(received_expected_pool_handle);
348
349 // Non-BRP pools don't need adjustment that BRP needs in 32-bit mode.
350 #if BUILDFLAG(ENABLE_THREAD_ISOLATION)
351 PA_DCHECK(IsManagedByPartitionAllocThreadIsolatedPool(reservation_start) ||
352 IsManagedByPartitionAllocRegularPool(reservation_start) ||
353 IsManagedByPartitionAllocConfigurablePool(reservation_start));
354 #else
355 PA_DCHECK(IsManagedByPartitionAllocRegularPool(reservation_start) ||
356 IsManagedByPartitionAllocConfigurablePool(reservation_start));
357 #endif
358 }
359 #endif // BUILDFLAG(PA_DCHECK_IS_ON)
360
361 PA_DCHECK((reservation_start & kSuperPageOffsetMask) == 0);
362 uintptr_t reservation_end = reservation_start + reservation_size;
363 auto* offset_ptr = ReservationOffsetPointer(reservation_start);
364 // Reset the offset table entries for the given memory before unreserving
365 // it. Since the memory is not unreserved and not available for other
366 // threads, the table entries for the memory are not modified by other
367 // threads either. So we can update the table entries without race
368 // condition.
369 uint16_t i = 0;
370 for (uintptr_t address = reservation_start; address < reservation_end;
371 address += kSuperPageSize) {
372 PA_DCHECK(offset_ptr < GetReservationOffsetTableEnd(address));
373 PA_DCHECK(*offset_ptr == i++);
374 *offset_ptr++ = kOffsetTagNotAllocated;
375 }
376
377 #if !BUILDFLAG(HAS_64_BIT_POINTERS)
378 AddressPoolManager::GetInstance().MarkUnused(pool, reservation_start,
379 reservation_size);
380 #endif
381
382 // After resetting the table entries, unreserve and decommit the memory.
383 AddressPoolManager::GetInstance().UnreserveAndDecommit(
384 pool, reservation_start, reservation_size);
385 }
386
387 } // namespace
388
389 } // namespace partition_alloc::internal
390