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