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