1 // Copyright 2011 the V8 project 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
5 #ifndef V8_HEAP_SPACES_INL_H_
6 #define V8_HEAP_SPACES_INL_H_
7
8 #include "src/base/v8-fallthrough.h"
9 #include "src/heap/incremental-marking.h"
10 #include "src/heap/spaces.h"
11 #include "src/msan.h"
12 #include "src/objects/code-inl.h"
13
14 namespace v8 {
15 namespace internal {
16
17 template <class PAGE_TYPE>
18 PageIteratorImpl<PAGE_TYPE>& PageIteratorImpl<PAGE_TYPE>::operator++() {
19 p_ = p_->next_page();
20 return *this;
21 }
22
23 template <class PAGE_TYPE>
24 PageIteratorImpl<PAGE_TYPE> PageIteratorImpl<PAGE_TYPE>::operator++(int) {
25 PageIteratorImpl<PAGE_TYPE> tmp(*this);
26 operator++();
27 return tmp;
28 }
29
PageRange(Address start,Address limit)30 PageRange::PageRange(Address start, Address limit)
31 : begin_(Page::FromAddress(start)),
32 end_(Page::FromAllocationAreaAddress(limit)->next_page()) {
33 #ifdef DEBUG
34 if (begin_->InNewSpace()) {
35 SemiSpace::AssertValidRange(start, limit);
36 }
37 #endif // DEBUG
38 }
39
40 // -----------------------------------------------------------------------------
41 // SemiSpaceIterator
42
Next()43 HeapObject* SemiSpaceIterator::Next() {
44 while (current_ != limit_) {
45 if (Page::IsAlignedToPageSize(current_)) {
46 Page* page = Page::FromAllocationAreaAddress(current_);
47 page = page->next_page();
48 DCHECK(page);
49 current_ = page->area_start();
50 if (current_ == limit_) return nullptr;
51 }
52 HeapObject* object = HeapObject::FromAddress(current_);
53 current_ += object->Size();
54 if (!object->IsFiller()) {
55 return object;
56 }
57 }
58 return nullptr;
59 }
60
61 // -----------------------------------------------------------------------------
62 // HeapObjectIterator
63
Next()64 HeapObject* HeapObjectIterator::Next() {
65 do {
66 HeapObject* next_obj = FromCurrentPage();
67 if (next_obj != nullptr) return next_obj;
68 } while (AdvanceToNextPage());
69 return nullptr;
70 }
71
FromCurrentPage()72 HeapObject* HeapObjectIterator::FromCurrentPage() {
73 while (cur_addr_ != cur_end_) {
74 if (cur_addr_ == space_->top() && cur_addr_ != space_->limit()) {
75 cur_addr_ = space_->limit();
76 continue;
77 }
78 HeapObject* obj = HeapObject::FromAddress(cur_addr_);
79 const int obj_size = obj->Size();
80 cur_addr_ += obj_size;
81 DCHECK_LE(cur_addr_, cur_end_);
82 if (!obj->IsFiller()) {
83 if (obj->IsCode()) {
84 DCHECK_EQ(space_, space_->heap()->code_space());
85 DCHECK_CODEOBJECT_SIZE(obj_size, space_);
86 } else {
87 DCHECK_OBJECT_SIZE(obj_size);
88 }
89 return obj;
90 }
91 }
92 return nullptr;
93 }
94
95 // -----------------------------------------------------------------------------
96 // SemiSpace
97
Contains(HeapObject * o)98 bool SemiSpace::Contains(HeapObject* o) {
99 return id_ == kToSpace
100 ? MemoryChunk::FromAddress(o->address())->InToSpace()
101 : MemoryChunk::FromAddress(o->address())->InFromSpace();
102 }
103
Contains(Object * o)104 bool SemiSpace::Contains(Object* o) {
105 return o->IsHeapObject() && Contains(HeapObject::cast(o));
106 }
107
ContainsSlow(Address a)108 bool SemiSpace::ContainsSlow(Address a) {
109 for (Page* p : *this) {
110 if (p == MemoryChunk::FromAddress(a)) return true;
111 }
112 return false;
113 }
114
115 // --------------------------------------------------------------------------
116 // NewSpace
117
Contains(HeapObject * o)118 bool NewSpace::Contains(HeapObject* o) {
119 return MemoryChunk::FromAddress(o->address())->InNewSpace();
120 }
121
Contains(Object * o)122 bool NewSpace::Contains(Object* o) {
123 return o->IsHeapObject() && Contains(HeapObject::cast(o));
124 }
125
ContainsSlow(Address a)126 bool NewSpace::ContainsSlow(Address a) {
127 return from_space_.ContainsSlow(a) || to_space_.ContainsSlow(a);
128 }
129
ToSpaceContainsSlow(Address a)130 bool NewSpace::ToSpaceContainsSlow(Address a) {
131 return to_space_.ContainsSlow(a);
132 }
133
FromSpaceContainsSlow(Address a)134 bool NewSpace::FromSpaceContainsSlow(Address a) {
135 return from_space_.ContainsSlow(a);
136 }
137
ToSpaceContains(Object * o)138 bool NewSpace::ToSpaceContains(Object* o) { return to_space_.Contains(o); }
FromSpaceContains(Object * o)139 bool NewSpace::FromSpaceContains(Object* o) { return from_space_.Contains(o); }
140
Contains(Address addr)141 bool PagedSpace::Contains(Address addr) {
142 if (heap()->lo_space()->FindPage(addr)) return false;
143 return MemoryChunk::FromAnyPointerAddress(heap(), addr)->owner() == this;
144 }
145
Contains(Object * o)146 bool PagedSpace::Contains(Object* o) {
147 if (!o->IsHeapObject()) return false;
148 return Page::FromAddress(HeapObject::cast(o)->address())->owner() == this;
149 }
150
UnlinkFreeListCategories(Page * page)151 void PagedSpace::UnlinkFreeListCategories(Page* page) {
152 DCHECK_EQ(this, page->owner());
153 page->ForAllFreeListCategories([this](FreeListCategory* category) {
154 DCHECK_EQ(free_list(), category->owner());
155 category->set_free_list(nullptr);
156 free_list()->RemoveCategory(category);
157 });
158 }
159
RelinkFreeListCategories(Page * page)160 size_t PagedSpace::RelinkFreeListCategories(Page* page) {
161 DCHECK_EQ(this, page->owner());
162 size_t added = 0;
163 page->ForAllFreeListCategories([this, &added](FreeListCategory* category) {
164 category->set_free_list(&free_list_);
165 added += category->available();
166 category->Relink();
167 });
168 DCHECK_EQ(page->AvailableInFreeList(),
169 page->AvailableInFreeListFromAllocatedBytes());
170 return added;
171 }
172
TryFreeLast(HeapObject * object,int object_size)173 bool PagedSpace::TryFreeLast(HeapObject* object, int object_size) {
174 if (allocation_info_.top() != kNullAddress) {
175 const Address object_address = object->address();
176 if ((allocation_info_.top() - object_size) == object_address) {
177 allocation_info_.set_top(object_address);
178 return true;
179 }
180 }
181 return false;
182 }
183
FromAnyPointerAddress(Heap * heap,Address addr)184 MemoryChunk* MemoryChunk::FromAnyPointerAddress(Heap* heap, Address addr) {
185 MemoryChunk* chunk = heap->lo_space()->FindPage(addr);
186 if (chunk == nullptr) {
187 chunk = MemoryChunk::FromAddress(addr);
188 }
189 return chunk;
190 }
191
MarkNeverAllocateForTesting()192 void Page::MarkNeverAllocateForTesting() {
193 DCHECK(this->owner()->identity() != NEW_SPACE);
194 DCHECK(!IsFlagSet(NEVER_ALLOCATE_ON_PAGE));
195 SetFlag(NEVER_ALLOCATE_ON_PAGE);
196 SetFlag(NEVER_EVACUATE);
197 reinterpret_cast<PagedSpace*>(owner())->free_list()->EvictFreeListItems(this);
198 }
199
MarkEvacuationCandidate()200 void Page::MarkEvacuationCandidate() {
201 DCHECK(!IsFlagSet(NEVER_EVACUATE));
202 DCHECK_NULL(slot_set<OLD_TO_OLD>());
203 DCHECK_NULL(typed_slot_set<OLD_TO_OLD>());
204 SetFlag(EVACUATION_CANDIDATE);
205 reinterpret_cast<PagedSpace*>(owner())->free_list()->EvictFreeListItems(this);
206 }
207
ClearEvacuationCandidate()208 void Page::ClearEvacuationCandidate() {
209 if (!IsFlagSet(COMPACTION_WAS_ABORTED)) {
210 DCHECK_NULL(slot_set<OLD_TO_OLD>());
211 DCHECK_NULL(typed_slot_set<OLD_TO_OLD>());
212 }
213 ClearFlag(EVACUATION_CANDIDATE);
214 InitializeFreeListCategories();
215 }
216
MemoryChunkIterator(Heap * heap)217 MemoryChunkIterator::MemoryChunkIterator(Heap* heap)
218 : heap_(heap),
219 state_(kOldSpaceState),
220 old_iterator_(heap->old_space()->begin()),
221 code_iterator_(heap->code_space()->begin()),
222 map_iterator_(heap->map_space()->begin()),
223 lo_iterator_(heap->lo_space()->begin()) {}
224
next()225 MemoryChunk* MemoryChunkIterator::next() {
226 switch (state_) {
227 case kOldSpaceState: {
228 if (old_iterator_ != heap_->old_space()->end()) return *(old_iterator_++);
229 state_ = kMapState;
230 V8_FALLTHROUGH;
231 }
232 case kMapState: {
233 if (map_iterator_ != heap_->map_space()->end()) return *(map_iterator_++);
234 state_ = kCodeState;
235 V8_FALLTHROUGH;
236 }
237 case kCodeState: {
238 if (code_iterator_ != heap_->code_space()->end())
239 return *(code_iterator_++);
240 state_ = kLargeObjectState;
241 V8_FALLTHROUGH;
242 }
243 case kLargeObjectState: {
244 if (lo_iterator_ != heap_->lo_space()->end()) return *(lo_iterator_++);
245 state_ = kFinishedState;
246 V8_FALLTHROUGH;
247 }
248 case kFinishedState:
249 return nullptr;
250 default:
251 break;
252 }
253 UNREACHABLE();
254 }
255
GetPageForCategoryType(FreeListCategoryType type)256 Page* FreeList::GetPageForCategoryType(FreeListCategoryType type) {
257 return top(type) ? top(type)->page() : nullptr;
258 }
259
owner()260 FreeList* FreeListCategory::owner() { return free_list_; }
261
is_linked()262 bool FreeListCategory::is_linked() {
263 return prev_ != nullptr || next_ != nullptr;
264 }
265
AllocateRawAligned(int size_in_bytes,AllocationAlignment alignment)266 AllocationResult LocalAllocationBuffer::AllocateRawAligned(
267 int size_in_bytes, AllocationAlignment alignment) {
268 Address current_top = allocation_info_.top();
269 int filler_size = Heap::GetFillToAlign(current_top, alignment);
270
271 Address new_top = current_top + filler_size + size_in_bytes;
272 if (new_top > allocation_info_.limit()) return AllocationResult::Retry();
273
274 allocation_info_.set_top(new_top);
275 if (filler_size > 0) {
276 return heap_->PrecedeWithFiller(HeapObject::FromAddress(current_top),
277 filler_size);
278 }
279
280 return AllocationResult(HeapObject::FromAddress(current_top));
281 }
282
EnsureLinearAllocationArea(int size_in_bytes)283 bool PagedSpace::EnsureLinearAllocationArea(int size_in_bytes) {
284 if (allocation_info_.top() + size_in_bytes <= allocation_info_.limit()) {
285 return true;
286 }
287 return SlowRefillLinearAllocationArea(size_in_bytes);
288 }
289
AllocateLinearly(int size_in_bytes)290 HeapObject* PagedSpace::AllocateLinearly(int size_in_bytes) {
291 Address current_top = allocation_info_.top();
292 Address new_top = current_top + size_in_bytes;
293 DCHECK_LE(new_top, allocation_info_.limit());
294 allocation_info_.set_top(new_top);
295 return HeapObject::FromAddress(current_top);
296 }
297
TryAllocateLinearlyAligned(int * size_in_bytes,AllocationAlignment alignment)298 HeapObject* PagedSpace::TryAllocateLinearlyAligned(
299 int* size_in_bytes, AllocationAlignment alignment) {
300 Address current_top = allocation_info_.top();
301 int filler_size = Heap::GetFillToAlign(current_top, alignment);
302
303 Address new_top = current_top + filler_size + *size_in_bytes;
304 if (new_top > allocation_info_.limit()) return nullptr;
305
306 allocation_info_.set_top(new_top);
307 if (filler_size > 0) {
308 *size_in_bytes += filler_size;
309 return heap()->PrecedeWithFiller(HeapObject::FromAddress(current_top),
310 filler_size);
311 }
312
313 return HeapObject::FromAddress(current_top);
314 }
315
AllocateRawUnaligned(int size_in_bytes,UpdateSkipList update_skip_list)316 AllocationResult PagedSpace::AllocateRawUnaligned(
317 int size_in_bytes, UpdateSkipList update_skip_list) {
318 DCHECK_IMPLIES(identity() == RO_SPACE, heap()->CanAllocateInReadOnlySpace());
319 if (!EnsureLinearAllocationArea(size_in_bytes)) {
320 return AllocationResult::Retry(identity());
321 }
322 HeapObject* object = AllocateLinearly(size_in_bytes);
323 DCHECK_NOT_NULL(object);
324 if (update_skip_list == UPDATE_SKIP_LIST && identity() == CODE_SPACE) {
325 SkipList::Update(object->address(), size_in_bytes);
326 }
327 MSAN_ALLOCATED_UNINITIALIZED_MEMORY(object->address(), size_in_bytes);
328 return object;
329 }
330
331
AllocateRawAligned(int size_in_bytes,AllocationAlignment alignment)332 AllocationResult PagedSpace::AllocateRawAligned(int size_in_bytes,
333 AllocationAlignment alignment) {
334 DCHECK(identity() == OLD_SPACE || identity() == RO_SPACE);
335 DCHECK_IMPLIES(identity() == RO_SPACE, heap()->CanAllocateInReadOnlySpace());
336 int allocation_size = size_in_bytes;
337 HeapObject* object = TryAllocateLinearlyAligned(&allocation_size, alignment);
338 if (object == nullptr) {
339 // We don't know exactly how much filler we need to align until space is
340 // allocated, so assume the worst case.
341 int filler_size = Heap::GetMaximumFillToAlign(alignment);
342 allocation_size += filler_size;
343 if (!EnsureLinearAllocationArea(allocation_size)) {
344 return AllocationResult::Retry(identity());
345 }
346 allocation_size = size_in_bytes;
347 object = TryAllocateLinearlyAligned(&allocation_size, alignment);
348 DCHECK_NOT_NULL(object);
349 }
350 MSAN_ALLOCATED_UNINITIALIZED_MEMORY(object->address(), size_in_bytes);
351 return object;
352 }
353
354
AllocateRaw(int size_in_bytes,AllocationAlignment alignment)355 AllocationResult PagedSpace::AllocateRaw(int size_in_bytes,
356 AllocationAlignment alignment) {
357 if (top_on_previous_step_ && top() < top_on_previous_step_ &&
358 SupportsInlineAllocation()) {
359 // Generated code decreased the top() pointer to do folded allocations.
360 // The top_on_previous_step_ can be one byte beyond the current page.
361 DCHECK_NE(top(), kNullAddress);
362 DCHECK_EQ(Page::FromAllocationAreaAddress(top()),
363 Page::FromAllocationAreaAddress(top_on_previous_step_ - 1));
364 top_on_previous_step_ = top();
365 }
366 size_t bytes_since_last =
367 top_on_previous_step_ ? top() - top_on_previous_step_ : 0;
368
369 DCHECK_IMPLIES(!SupportsInlineAllocation(), bytes_since_last == 0);
370 #ifdef V8_HOST_ARCH_32_BIT
371 AllocationResult result =
372 alignment == kDoubleAligned
373 ? AllocateRawAligned(size_in_bytes, kDoubleAligned)
374 : AllocateRawUnaligned(size_in_bytes);
375 #else
376 AllocationResult result = AllocateRawUnaligned(size_in_bytes);
377 #endif
378 HeapObject* heap_obj = nullptr;
379 if (!result.IsRetry() && result.To(&heap_obj) && !is_local()) {
380 DCHECK_IMPLIES(
381 heap()->incremental_marking()->black_allocation(),
382 heap()->incremental_marking()->marking_state()->IsBlack(heap_obj));
383 AllocationStep(static_cast<int>(size_in_bytes + bytes_since_last),
384 heap_obj->address(), size_in_bytes);
385 StartNextInlineAllocationStep();
386 }
387 return result;
388 }
389
390
391 // -----------------------------------------------------------------------------
392 // NewSpace
393
394
AllocateRawAligned(int size_in_bytes,AllocationAlignment alignment)395 AllocationResult NewSpace::AllocateRawAligned(int size_in_bytes,
396 AllocationAlignment alignment) {
397 Address top = allocation_info_.top();
398 int filler_size = Heap::GetFillToAlign(top, alignment);
399 int aligned_size_in_bytes = size_in_bytes + filler_size;
400
401 if (allocation_info_.limit() - top <
402 static_cast<uintptr_t>(aligned_size_in_bytes)) {
403 // See if we can create room.
404 if (!EnsureAllocation(size_in_bytes, alignment)) {
405 return AllocationResult::Retry();
406 }
407
408 top = allocation_info_.top();
409 filler_size = Heap::GetFillToAlign(top, alignment);
410 aligned_size_in_bytes = size_in_bytes + filler_size;
411 }
412
413 HeapObject* obj = HeapObject::FromAddress(top);
414 allocation_info_.set_top(top + aligned_size_in_bytes);
415 DCHECK_SEMISPACE_ALLOCATION_INFO(allocation_info_, to_space_);
416
417 if (filler_size > 0) {
418 obj = heap()->PrecedeWithFiller(obj, filler_size);
419 }
420
421 MSAN_ALLOCATED_UNINITIALIZED_MEMORY(obj->address(), size_in_bytes);
422
423 return obj;
424 }
425
426
AllocateRawUnaligned(int size_in_bytes)427 AllocationResult NewSpace::AllocateRawUnaligned(int size_in_bytes) {
428 Address top = allocation_info_.top();
429 if (allocation_info_.limit() < top + size_in_bytes) {
430 // See if we can create room.
431 if (!EnsureAllocation(size_in_bytes, kWordAligned)) {
432 return AllocationResult::Retry();
433 }
434
435 top = allocation_info_.top();
436 }
437
438 HeapObject* obj = HeapObject::FromAddress(top);
439 allocation_info_.set_top(top + size_in_bytes);
440 DCHECK_SEMISPACE_ALLOCATION_INFO(allocation_info_, to_space_);
441
442 MSAN_ALLOCATED_UNINITIALIZED_MEMORY(obj->address(), size_in_bytes);
443
444 return obj;
445 }
446
447
AllocateRaw(int size_in_bytes,AllocationAlignment alignment)448 AllocationResult NewSpace::AllocateRaw(int size_in_bytes,
449 AllocationAlignment alignment) {
450 if (top() < top_on_previous_step_) {
451 // Generated code decreased the top() pointer to do folded allocations
452 DCHECK_EQ(Page::FromAllocationAreaAddress(top()),
453 Page::FromAllocationAreaAddress(top_on_previous_step_));
454 top_on_previous_step_ = top();
455 }
456 #ifdef V8_HOST_ARCH_32_BIT
457 return alignment == kDoubleAligned
458 ? AllocateRawAligned(size_in_bytes, kDoubleAligned)
459 : AllocateRawUnaligned(size_in_bytes);
460 #else
461 return AllocateRawUnaligned(size_in_bytes);
462 #endif
463 }
464
AllocateRawSynchronized(int size_in_bytes,AllocationAlignment alignment)465 V8_WARN_UNUSED_RESULT inline AllocationResult NewSpace::AllocateRawSynchronized(
466 int size_in_bytes, AllocationAlignment alignment) {
467 base::LockGuard<base::Mutex> guard(&mutex_);
468 return AllocateRaw(size_in_bytes, alignment);
469 }
470
FromResult(Heap * heap,AllocationResult result,intptr_t size)471 LocalAllocationBuffer LocalAllocationBuffer::FromResult(Heap* heap,
472 AllocationResult result,
473 intptr_t size) {
474 if (result.IsRetry()) return InvalidBuffer();
475 HeapObject* obj = nullptr;
476 bool ok = result.To(&obj);
477 USE(ok);
478 DCHECK(ok);
479 Address top = HeapObject::cast(obj)->address();
480 return LocalAllocationBuffer(heap, LinearAllocationArea(top, top + size));
481 }
482
483
TryMerge(LocalAllocationBuffer * other)484 bool LocalAllocationBuffer::TryMerge(LocalAllocationBuffer* other) {
485 if (allocation_info_.top() == other->allocation_info_.limit()) {
486 allocation_info_.set_top(other->allocation_info_.top());
487 other->allocation_info_.Reset(kNullAddress, kNullAddress);
488 return true;
489 }
490 return false;
491 }
492
TryFreeLast(HeapObject * object,int object_size)493 bool LocalAllocationBuffer::TryFreeLast(HeapObject* object, int object_size) {
494 if (IsValid()) {
495 const Address object_address = object->address();
496 if ((allocation_info_.top() - object_size) == object_address) {
497 allocation_info_.set_top(object_address);
498 return true;
499 }
500 }
501 return false;
502 }
503
504 } // namespace internal
505 } // namespace v8
506
507 #endif // V8_HEAP_SPACES_INL_H_
508