spaces.cc 116 KB
Newer Older
danno@chromium.org's avatar
danno@chromium.org committed
1
// Copyright 2011 the V8 project authors. All rights reserved.
2 3
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
4

5
#include "src/heap/spaces.h"
6

7 8
#include <utility>

9
#include "src/base/bits.h"
10
#include "src/base/platform/platform.h"
11
#include "src/base/platform/semaphore.h"
12
#include "src/counters.h"
13
#include "src/full-codegen/full-codegen.h"
14
#include "src/heap/array-buffer-tracker.h"
15 16
#include "src/heap/incremental-marking.h"
#include "src/heap/mark-compact.h"
ulan's avatar
ulan committed
17
#include "src/heap/slot-set.h"
18 19
#include "src/macro-assembler.h"
#include "src/msan.h"
20
#include "src/objects-inl.h"
21
#include "src/snapshot/snapshot.h"
22
#include "src/v8.h"
23
#include "src/vm-state-inl.h"
24

25 26
namespace v8 {
namespace internal {
27 28 29 30 31


// ----------------------------------------------------------------------------
// HeapObjectIterator

32 33 34 35 36
HeapObjectIterator::HeapObjectIterator(PagedSpace* space)
    : cur_addr_(nullptr),
      cur_end_(nullptr),
      space_(space),
      page_range_(space->anchor()->next_page(), space->anchor()),
37
      current_page_(page_range_.begin()) {}
38 39 40 41

HeapObjectIterator::HeapObjectIterator(Page* page)
    : cur_addr_(nullptr),
      cur_end_(nullptr),
42
      space_(reinterpret_cast<PagedSpace*>(page->owner())),
43
      page_range_(page),
44
      current_page_(page_range_.begin()) {
45
#ifdef DEBUG
46
  Space* owner = page->owner();
47 48 49
  DCHECK(owner == page->heap()->old_space() ||
         owner == page->heap()->map_space() ||
         owner == page->heap()->code_space());
50
#endif  // DEBUG
51 52
}

53 54 55
// We have hit the end of the page and should advance to the next block of
// objects.  This happens at the end of the page.
bool HeapObjectIterator::AdvanceToNextPage() {
56
  DCHECK_EQ(cur_addr_, cur_end_);
57 58
  if (current_page_ == page_range_.end()) return false;
  Page* cur_page = *(current_page_++);
59 60 61 62 63 64 65 66
  Heap* heap = space_->heap();

  heap->mark_compact_collector()->sweeper().SweepOrWaitUntilSweepingCompleted(
      cur_page);
  if (cur_page->IsFlagSet(Page::SWEEP_TO_ITERATE))
    heap->minor_mark_compact_collector()->MakeIterable(
        cur_page, MarkingTreatmentMode::CLEAR,
        FreeSpaceTreatmentMode::IGNORE_FREE_SPACE);
67 68
  cur_addr_ = cur_page->area_start();
  cur_end_ = cur_page->area_end();
69
  DCHECK(cur_page->SweepingDone());
70
  return true;
71 72
}

73 74 75 76 77 78 79 80 81 82 83 84 85 86
PauseAllocationObserversScope::PauseAllocationObserversScope(Heap* heap)
    : heap_(heap) {
  AllSpaces spaces(heap_);
  for (Space* space = spaces.next(); space != NULL; space = spaces.next()) {
    space->PauseAllocationObservers();
  }
}

PauseAllocationObserversScope::~PauseAllocationObserversScope() {
  AllSpaces spaces(heap_);
  for (Space* space = spaces.next(); space != NULL; space = spaces.next()) {
    space->ResumeAllocationObservers();
  }
}
87

88 89 90
// -----------------------------------------------------------------------------
// CodeRange

91

92 93 94
CodeRange::CodeRange(Isolate* isolate)
    : isolate_(isolate),
      code_range_(NULL),
95 96
      free_list_(0),
      allocation_list_(0),
97
      current_allocation_block_index_(0) {}
98 99


100
bool CodeRange::SetUp(size_t requested) {
101
  DCHECK(code_range_ == NULL);
102

103
  if (requested == 0) {
104 105 106 107 108
    // When a target requires the code range feature, we put all code objects
    // in a kMaximalCodeRangeSize range of virtual address space, so that
    // they can call each other with near calls.
    if (kRequiresCodeRange) {
      requested = kMaximalCodeRangeSize;
109 110 111 112 113
    } else {
      return true;
    }
  }

114
  if (requested <= kMinimumCodeRangeSize) {
115 116 117
    requested = kMinimumCodeRangeSize;
  }

118
  const size_t reserved_area =
119
      kReservedCodeRangePages * MemoryAllocator::GetCommitPageSize();
120 121 122
  if (requested < (kMaximalCodeRangeSize - reserved_area))
    requested += reserved_area;

123
  DCHECK(!kRequiresCodeRange || requested <= kMaximalCodeRangeSize);
124 125 126 127

  code_range_ = new base::VirtualMemory(
      requested, Max(kCodeRangeAreaAlignment,
                     static_cast<size_t>(base::OS::AllocateAlignment())));
128 129 130 131 132 133 134 135
  CHECK(code_range_ != NULL);
  if (!code_range_->IsReserved()) {
    delete code_range_;
    code_range_ = NULL;
    return false;
  }

  // We are sure that we have mapped a block of requested addresses.
136
  DCHECK(code_range_->size() == requested);
137
  Address base = reinterpret_cast<Address>(code_range_->address());
138 139 140

  // On some platforms, specifically Win64, we need to reserve some pages at
  // the beginning of an executable space.
141 142
  if (reserved_area > 0) {
    if (!code_range_->Commit(base, reserved_area, true)) {
143 144 145 146
      delete code_range_;
      code_range_ = NULL;
      return false;
    }
147
    base += reserved_area;
148 149
  }
  Address aligned_base = RoundUp(base, MemoryChunk::kAlignment);
150
  size_t size = code_range_->size() - (aligned_base - base) - reserved_area;
151
  allocation_list_.Add(FreeBlock(aligned_base, size));
152
  current_allocation_block_index_ = 0;
153 154

  LOG(isolate_, NewEvent("CodeRange", code_range_->address(), requested));
155 156 157 158 159 160 161 162 163 164 165 166 167
  return true;
}


int CodeRange::CompareFreeBlockAddress(const FreeBlock* left,
                                       const FreeBlock* right) {
  // The entire point of CodeRange is that the difference between two
  // addresses in the range can be represented as a signed 32-bit int,
  // so the cast is semantically correct.
  return static_cast<int>(left->start - right->start);
}


168
bool CodeRange::GetNextAllocationBlock(size_t requested) {
169 170 171 172
  for (current_allocation_block_index_++;
       current_allocation_block_index_ < allocation_list_.length();
       current_allocation_block_index_++) {
    if (requested <= allocation_list_[current_allocation_block_index_].size) {
173
      return true;  // Found a large enough allocation block.
174 175 176
    }
  }

177 178 179 180 181 182 183 184 185 186 187
  // Sort and merge the free blocks on the free list and the allocation list.
  free_list_.AddAll(allocation_list_);
  allocation_list_.Clear();
  free_list_.Sort(&CompareFreeBlockAddress);
  for (int i = 0; i < free_list_.length();) {
    FreeBlock merged = free_list_[i];
    i++;
    // Add adjacent free blocks to the current merged block.
    while (i < free_list_.length() &&
           free_list_[i].start == merged.start + merged.size) {
      merged.size += free_list_[i].size;
188 189
      i++;
    }
190 191 192
    if (merged.size > 0) {
      allocation_list_.Add(merged);
    }
193
  }
194
  free_list_.Clear();
195 196 197 198 199

  for (current_allocation_block_index_ = 0;
       current_allocation_block_index_ < allocation_list_.length();
       current_allocation_block_index_++) {
    if (requested <= allocation_list_[current_allocation_block_index_].size) {
200
      return true;  // Found a large enough allocation block.
201 202
    }
  }
203
  current_allocation_block_index_ = 0;
204
  // Code range is full or too fragmented.
205
  return false;
206 207 208
}


209 210
Address CodeRange::AllocateRawMemory(const size_t requested_size,
                                     const size_t commit_size,
211
                                     size_t* allocated) {
212 213 214 215
  // request_size includes guards while committed_size does not. Make sure
  // callers know about the invariant.
  CHECK_LE(commit_size,
           requested_size - 2 * MemoryAllocator::CodePageGuardSize());
216 217 218 219
  FreeBlock current;
  if (!ReserveBlock(requested_size, &current)) {
    *allocated = 0;
    return NULL;
220
  }
221
  *allocated = current.size;
222 223
  DCHECK(*allocated <= current.size);
  DCHECK(IsAddressAligned(current.start, MemoryChunk::kAlignment));
224
  if (!isolate_->heap()->memory_allocator()->CommitExecutableMemory(
225
          code_range_, current.start, commit_size, *allocated)) {
226
    *allocated = 0;
227
    ReleaseBlock(&current);
228 229 230 231 232 233
    return NULL;
  }
  return current.start;
}


234
bool CodeRange::CommitRawMemory(Address start, size_t length) {
235 236
  return isolate_->heap()->memory_allocator()->CommitMemory(start, length,
                                                            EXECUTABLE);
237 238 239 240 241 242 243 244
}


bool CodeRange::UncommitRawMemory(Address start, size_t length) {
  return code_range_->Uncommit(start, length);
}


245
void CodeRange::FreeRawMemory(Address address, size_t length) {
246
  DCHECK(IsAddressAligned(address, MemoryChunk::kAlignment));
247
  base::LockGuard<base::Mutex> guard(&code_range_mutex_);
248
  free_list_.Add(FreeBlock(address, length));
249
  code_range_->Uncommit(address, length);
250 251 252 253
}


void CodeRange::TearDown() {
254 255
  delete code_range_;  // Frees all memory in the virtual memory range.
  code_range_ = NULL;
256
  base::LockGuard<base::Mutex> guard(&code_range_mutex_);
257 258
  free_list_.Free();
  allocation_list_.Free();
259 260 261
}


262
bool CodeRange::ReserveBlock(const size_t requested_size, FreeBlock* block) {
263
  base::LockGuard<base::Mutex> guard(&code_range_mutex_);
264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284
  DCHECK(allocation_list_.length() == 0 ||
         current_allocation_block_index_ < allocation_list_.length());
  if (allocation_list_.length() == 0 ||
      requested_size > allocation_list_[current_allocation_block_index_].size) {
    // Find an allocation block large enough.
    if (!GetNextAllocationBlock(requested_size)) return false;
  }
  // Commit the requested memory at the start of the current allocation block.
  size_t aligned_requested = RoundUp(requested_size, MemoryChunk::kAlignment);
  *block = allocation_list_[current_allocation_block_index_];
  // Don't leave a small free block, useless for a large object or chunk.
  if (aligned_requested < (block->size - Page::kPageSize)) {
    block->size = aligned_requested;
  }
  DCHECK(IsAddressAligned(block->start, MemoryChunk::kAlignment));
  allocation_list_[current_allocation_block_index_].start += block->size;
  allocation_list_[current_allocation_block_index_].size -= block->size;
  return true;
}


285
void CodeRange::ReleaseBlock(const FreeBlock* block) {
286
  base::LockGuard<base::Mutex> guard(&code_range_mutex_);
287 288
  free_list_.Add(*block);
}
289 290


291 292 293 294
// -----------------------------------------------------------------------------
// MemoryAllocator
//

295 296
MemoryAllocator::MemoryAllocator(Isolate* isolate)
    : isolate_(isolate),
297
      code_range_(nullptr),
298
      capacity_(0),
299
      size_(0),
300 301
      size_executable_(0),
      lowest_ever_allocated_(reinterpret_cast<void*>(-1)),
302 303
      highest_ever_allocated_(reinterpret_cast<void*>(0)),
      unmapper_(this) {}
304

305
bool MemoryAllocator::SetUp(size_t capacity, size_t code_range_size) {
306 307
  capacity_ = RoundUp(capacity, Page::kPageSize);

308
  size_ = 0;
309
  size_executable_ = 0;
310

311
  code_range_ = new CodeRange(isolate_);
312
  if (!code_range_->SetUp(code_range_size)) return false;
313

314 315 316 317 318
  return true;
}


void MemoryAllocator::TearDown() {
319
  unmapper()->TearDown();
320

321
  // Check that spaces were torn down before MemoryAllocator.
322
  DCHECK_EQ(size_.Value(), 0u);
323
  // TODO(gc) this will be true again when we fix FreeMemory.
324
  // DCHECK(size_executable_ == 0);
325
  capacity_ = 0;
326

327 328 329 330
  if (last_chunk_.IsReserved()) {
    last_chunk_.Release();
  }

331 332
  delete code_range_;
  code_range_ = nullptr;
333 334
}

335 336 337 338 339 340 341
class MemoryAllocator::Unmapper::UnmapFreeMemoryTask : public v8::Task {
 public:
  explicit UnmapFreeMemoryTask(Unmapper* unmapper) : unmapper_(unmapper) {}

 private:
  // v8::Task overrides.
  void Run() override {
342
    unmapper_->PerformFreeMemoryOnQueuedChunks<FreeMode::kUncommitPooled>();
343
    unmapper_->pending_unmapping_tasks_semaphore_.Signal();
344 345 346 347 348 349 350
  }

  Unmapper* unmapper_;
  DISALLOW_COPY_AND_ASSIGN(UnmapFreeMemoryTask);
};

void MemoryAllocator::Unmapper::FreeQueuedChunks() {
351
  ReconsiderDelayedChunks();
352 353 354 355 356
  if (FLAG_concurrent_sweeping) {
    V8::GetCurrentPlatform()->CallOnBackgroundThread(
        new UnmapFreeMemoryTask(this), v8::Platform::kShortRunningTask);
    concurrent_unmapping_tasks_active_++;
  } else {
357
    PerformFreeMemoryOnQueuedChunks<FreeMode::kUncommitPooled>();
358 359 360 361 362 363 364 365 366 367 368 369 370
  }
}

bool MemoryAllocator::Unmapper::WaitUntilCompleted() {
  bool waited = false;
  while (concurrent_unmapping_tasks_active_ > 0) {
    pending_unmapping_tasks_semaphore_.Wait();
    concurrent_unmapping_tasks_active_--;
    waited = true;
  }
  return waited;
}

371
template <MemoryAllocator::Unmapper::FreeMode mode>
372 373 374 375 376 377 378 379
void MemoryAllocator::Unmapper::PerformFreeMemoryOnQueuedChunks() {
  MemoryChunk* chunk = nullptr;
  // Regular chunks.
  while ((chunk = GetMemoryChunkSafe<kRegular>()) != nullptr) {
    bool pooled = chunk->IsFlagSet(MemoryChunk::POOLED);
    allocator_->PerformFreeMemory(chunk);
    if (pooled) AddMemoryChunkSafe<kPooled>(chunk);
  }
380 381 382 383 384 385 386 387
  if (mode == MemoryAllocator::Unmapper::FreeMode::kReleasePooled) {
    // The previous loop uncommitted any pages marked as pooled and added them
    // to the pooled list. In case of kReleasePooled we need to free them
    // though.
    while ((chunk = GetMemoryChunkSafe<kPooled>()) != nullptr) {
      allocator_->Free<MemoryAllocator::kAlreadyPooled>(chunk);
    }
  }
388 389 390 391 392 393
  // Non-regular chunks.
  while ((chunk = GetMemoryChunkSafe<kNonRegular>()) != nullptr) {
    allocator_->PerformFreeMemory(chunk);
  }
}

394 395 396 397
void MemoryAllocator::Unmapper::TearDown() {
  WaitUntilCompleted();
  ReconsiderDelayedChunks();
  CHECK(delayed_regular_chunks_.empty());
398 399 400 401
  PerformFreeMemoryOnQueuedChunks<FreeMode::kReleasePooled>();
  for (int i = 0; i < kNumberOfChunkQueues; i++) {
    DCHECK(chunks_[i].empty());
  }
402 403
}

404 405 406 407 408 409 410 411 412 413
void MemoryAllocator::Unmapper::ReconsiderDelayedChunks() {
  std::list<MemoryChunk*> delayed_chunks(std::move(delayed_regular_chunks_));
  // Move constructed, so the permanent list should be empty.
  DCHECK(delayed_regular_chunks_.empty());
  for (auto it = delayed_chunks.begin(); it != delayed_chunks.end(); ++it) {
    AddMemoryChunkSafe<kRegular>(*it);
  }
}

bool MemoryAllocator::CanFreeMemoryChunk(MemoryChunk* chunk) {
414
  MarkCompactCollector* mc = isolate_->heap()->mark_compact_collector();
415 416 417 418
  // We cannot free a memory chunk in new space while the sweeper is running
  // because the memory chunk can be in the queue of a sweeper task.
  // Chunks in old generation are unmapped if they are empty.
  DCHECK(chunk->InNewSpace() || chunk->SweepingDone());
419
  return !chunk->InNewSpace() || mc == nullptr ||
420
         !mc->sweeper().sweeping_in_progress();
421 422
}

423
bool MemoryAllocator::CommitMemory(Address base, size_t size,
424
                                   Executability executable) {
425 426
  if (!base::VirtualMemory::CommitRegion(base, size,
                                         executable == EXECUTABLE)) {
427 428 429 430 431 432 433
    return false;
  }
  UpdateAllocatedSpaceLimits(base, base + size);
  return true;
}


434 435 436
void MemoryAllocator::FreeMemory(base::VirtualMemory* reservation,
                                 Executability executable) {
  // TODO(gc) make code_range part of memory allocator?
437
  // Code which is part of the code-range does not have its own VirtualMemory.
438 439
  DCHECK(code_range() == NULL ||
         !code_range()->contains(static_cast<Address>(reservation->address())));
440 441
  DCHECK(executable == NOT_EXECUTABLE || !code_range()->valid() ||
         reservation->size() <= Page::kPageSize);
442

443
  reservation->Release();
444 445 446
}


447
void MemoryAllocator::FreeMemory(Address base, size_t size,
448
                                 Executability executable) {
449
  // TODO(gc) make code_range part of memory allocator?
450 451
  if (code_range() != NULL &&
      code_range()->contains(static_cast<Address>(base))) {
452
    DCHECK(executable == EXECUTABLE);
453
    code_range()->FreeRawMemory(base, size);
454
  } else {
455
    DCHECK(executable == NOT_EXECUTABLE || !code_range()->valid());
456
    bool result = base::VirtualMemory::ReleaseRegion(base, size);
457
    USE(result);
458
    DCHECK(result);
459
  }
460 461
}

462
Address MemoryAllocator::ReserveAlignedMemory(size_t size, size_t alignment,
463 464
                                              base::VirtualMemory* controller) {
  base::VirtualMemory reservation(size, alignment);
465

466 467
  if (!reservation.IsReserved()) return nullptr;
  const Address base =
468
      RoundUp(static_cast<Address>(reservation.address()), alignment);
469 470 471 472 473
  if (base + size != reservation.end()) {
    const Address unused_start = RoundUp(base + size, GetCommitPageSize());
    reservation.ReleasePartial(unused_start);
  }
  size_.Increment(reservation.size());
474 475
  controller->TakeControl(&reservation);
  return base;
476 477
}

478 479 480
Address MemoryAllocator::AllocateAlignedMemory(
    size_t reserve_size, size_t commit_size, size_t alignment,
    Executability executable, base::VirtualMemory* controller) {
481
  DCHECK(commit_size <= reserve_size);
482
  base::VirtualMemory reservation;
483
  Address base = ReserveAlignedMemory(reserve_size, alignment, &reservation);
484
  if (base == NULL) return NULL;
485

486
  if (executable == EXECUTABLE) {
487
    if (!CommitExecutableMemory(&reservation, base, commit_size,
488
                                reserve_size)) {
489 490
      base = NULL;
    }
491
  } else {
492
    if (reservation.Commit(base, commit_size, false)) {
493 494
      UpdateAllocatedSpaceLimits(base, base + commit_size);
    } else {
495
      base = NULL;
496
    }
497
  }
498

499 500 501 502
  if (base == NULL) {
    // Failed to commit the body. Release the mapping and any partially
    // commited regions inside it.
    reservation.Release();
503
    size_.Decrement(reserve_size);
504 505 506
    return NULL;
  }

507 508
  controller->TakeControl(&reservation);
  return base;
509 510
}

511 512
void Page::InitializeAsAnchor(Space* space) {
  set_owner(space);
513 514
  set_next_chunk(this);
  set_prev_chunk(this);
515
  SetFlags(0, static_cast<uintptr_t>(~0));
516
  SetFlag(ANCHOR);
517 518
}

519 520 521 522 523
Heap* MemoryChunk::synchronized_heap() {
  return reinterpret_cast<Heap*>(
      base::Acquire_Load(reinterpret_cast<base::AtomicWord*>(&heap_)));
}

524 525
MemoryChunk* MemoryChunk::Initialize(Heap* heap, Address base, size_t size,
                                     Address area_start, Address area_end,
526 527
                                     Executability executable, Space* owner,
                                     base::VirtualMemory* reservation) {
528
  MemoryChunk* chunk = FromAddress(base);
529

530
  DCHECK(base == chunk->address());
531

532 533
  chunk->heap_ = heap;
  chunk->size_ = size;
534 535
  chunk->area_start_ = area_start;
  chunk->area_end_ = area_end;
mlippautz's avatar
mlippautz committed
536
  chunk->flags_ = Flags(NO_FLAGS);
537 538
  chunk->set_owner(owner);
  chunk->InitializeReservedMemory();
539 540 541 542 543 544
  base::AsAtomicWord::Release_Store(&chunk->slot_set_[OLD_TO_NEW], nullptr);
  base::AsAtomicWord::Release_Store(&chunk->slot_set_[OLD_TO_OLD], nullptr);
  base::AsAtomicWord::Release_Store(&chunk->typed_slot_set_[OLD_TO_NEW],
                                    nullptr);
  base::AsAtomicWord::Release_Store(&chunk->typed_slot_set_[OLD_TO_OLD],
                                    nullptr);
ulan's avatar
ulan committed
545
  chunk->skip_list_ = nullptr;
546
  chunk->progress_bar_ = 0;
547
  chunk->high_water_mark_.SetValue(static_cast<intptr_t>(area_start - base));
548
  chunk->concurrent_sweeping_state().SetValue(kSweepingDone);
549
  chunk->mutex_ = new base::RecursiveMutex();
550 551
  chunk->available_in_free_list_ = 0;
  chunk->wasted_memory_ = 0;
552
  chunk->young_generation_bitmap_ = nullptr;
553 554
  chunk->set_next_chunk(nullptr);
  chunk->set_prev_chunk(nullptr);
555
  chunk->local_tracker_ = nullptr;
556

557 558
  MarkingState::Internal(chunk).ClearLiveness();

559
  DCHECK(OFFSET_OF(MemoryChunk, flags_) == kFlagsOffset);
560

561
  if (executable == EXECUTABLE) {
562 563
    chunk->SetFlag(IS_EXECUTABLE);
  }
564

565 566 567
  if (reservation != nullptr) {
    chunk->reservation_.TakeControl(reservation);
  }
568 569 570 571 572 573 574 575

#ifdef THREAD_SANITIZER
  // The mark-bit clearing function above emits a memory fence. Since TSAN
  // does not process memory fences, we use the following annotation to tell
  // TSAN that there is no data race in mark-bit clearing.
  base::Release_Store(reinterpret_cast<base::AtomicWord*>(&chunk->heap_),
                      reinterpret_cast<base::AtomicWord>(heap));
#endif
576
  return chunk;
577 578
}

579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650
template <Page::InitializationMode mode>
Page* Page::Initialize(Heap* heap, MemoryChunk* chunk, Executability executable,
                       PagedSpace* owner) {
  Page* page = reinterpret_cast<Page*>(chunk);
  DCHECK(page->area_size() <= kAllocatableMemory);
  DCHECK(chunk->owner() == owner);

  owner->IncreaseCapacity(page->area_size());
  heap->incremental_marking()->SetOldSpacePageFlags(chunk);

  // Make sure that categories are initialized before freeing the area.
  page->InitializeFreeListCategories();
  // In the case we do not free the memory, we effectively account for the whole
  // page as allocated memory that cannot be used for further allocations.
  if (mode == kFreeMemory) {
    owner->Free(page->area_start(), page->area_size());
  }

  return page;
}

Page* Page::Initialize(Heap* heap, MemoryChunk* chunk, Executability executable,
                       SemiSpace* owner) {
  DCHECK_EQ(executable, Executability::NOT_EXECUTABLE);
  bool in_to_space = (owner->id() != kFromSpace);
  chunk->SetFlag(in_to_space ? MemoryChunk::IN_TO_SPACE
                             : MemoryChunk::IN_FROM_SPACE);
  DCHECK(!chunk->IsFlagSet(in_to_space ? MemoryChunk::IN_FROM_SPACE
                                       : MemoryChunk::IN_TO_SPACE));
  Page* page = static_cast<Page*>(chunk);
  heap->incremental_marking()->SetNewSpacePageFlags(page);
  page->AllocateLocalTracker();
  if (FLAG_minor_mc) {
    page->AllocateYoungGenerationBitmap();
    MarkingState::External(page).ClearLiveness();
  }
  return page;
}

LargePage* LargePage::Initialize(Heap* heap, MemoryChunk* chunk,
                                 Executability executable, Space* owner) {
  if (executable && chunk->size() > LargePage::kMaxCodePageSize) {
    STATIC_ASSERT(LargePage::kMaxCodePageSize <= TypedSlotSet::kMaxOffset);
    FATAL("Code page is too large.");
  }
  heap->incremental_marking()->SetOldSpacePageFlags(chunk);

  MSAN_ALLOCATED_UNINITIALIZED_MEMORY(chunk->area_start(), chunk->area_size());

  // Initialize the owner field for each contained page (except the first, which
  // is initialized by MemoryChunk::Initialize).
  for (Address addr = chunk->address() + Page::kPageSize + Page::kOwnerOffset;
       addr < chunk->area_end(); addr += Page::kPageSize) {
    // Clear out kPageHeaderTag.
    Memory::Address_at(addr) = 0;
  }

  return static_cast<LargePage*>(chunk);
}

Page* Page::ConvertNewToOld(Page* old_page) {
  DCHECK(!old_page->is_anchor());
  DCHECK(old_page->InNewSpace());
  OldSpace* old_space = old_page->heap()->old_space();
  old_page->set_owner(old_space);
  old_page->SetFlags(0, static_cast<uintptr_t>(~0));
  old_space->AccountCommitted(old_page->size());
  Page* new_page = Page::Initialize<kDoNotFreeMemory>(
      old_page->heap(), old_page, NOT_EXECUTABLE, old_space);
  new_page->InsertAfter(old_space->anchor()->prev_page());
  return new_page;
}
651

652 653
// Commit MemoryChunk area to the requested size.
bool MemoryChunk::CommitArea(size_t requested) {
654 655
  size_t guard_size =
      IsFlagSet(IS_EXECUTABLE) ? MemoryAllocator::CodePageGuardSize() : 0;
656
  size_t header_size = area_start() - address() - guard_size;
657
  size_t commit_size =
658
      RoundUp(header_size + requested, MemoryAllocator::GetCommitPageSize());
659
  size_t committed_size = RoundUp(header_size + (area_end() - area_start()),
660
                                  MemoryAllocator::GetCommitPageSize());
661 662 663

  if (commit_size > committed_size) {
    // Commit size should be less or equal than the reserved size.
664
    DCHECK(commit_size <= size() - 2 * guard_size);
665 666 667 668
    // Append the committed area.
    Address start = address() + committed_size + guard_size;
    size_t length = commit_size - committed_size;
    if (reservation_.IsReserved()) {
669 670
      Executability executable =
          IsFlagSet(IS_EXECUTABLE) ? EXECUTABLE : NOT_EXECUTABLE;
671 672
      if (!heap()->memory_allocator()->CommitMemory(start, length,
                                                    executable)) {
673 674 675
        return false;
      }
    } else {
676
      CodeRange* code_range = heap_->memory_allocator()->code_range();
677
      DCHECK(code_range->valid() && IsFlagSet(IS_EXECUTABLE));
678 679 680 681
      if (!code_range->CommitRawMemory(start, length)) return false;
    }

    if (Heap::ShouldZapGarbage()) {
682
      heap_->memory_allocator()->ZapBlock(start, length);
683 684
    }
  } else if (commit_size < committed_size) {
685
    DCHECK(commit_size > 0);
686 687 688 689 690 691
    // Shrink the committed area.
    size_t length = committed_size - commit_size;
    Address start = address() + committed_size + guard_size - length;
    if (reservation_.IsReserved()) {
      if (!reservation_.Uncommit(start, length)) return false;
    } else {
692
      CodeRange* code_range = heap_->memory_allocator()->code_range();
693
      DCHECK(code_range->valid() && IsFlagSet(IS_EXECUTABLE));
694 695 696 697 698 699 700 701
      if (!code_range->UncommitRawMemory(start, length)) return false;
    }
  }

  area_end_ = area_start_ + requested;
  return true;
}

702 703 704 705 706
size_t MemoryChunk::CommittedPhysicalMemory() {
  if (!base::VirtualMemory::HasLazyCommits() || owner()->identity() == LO_SPACE)
    return size();
  return high_water_mark_.Value();
}
707

708
void MemoryChunk::InsertAfter(MemoryChunk* other) {
709 710 711 712 713 714
  MemoryChunk* other_next = other->next_chunk();

  set_next_chunk(other_next);
  set_prev_chunk(other);
  other_next->set_prev_chunk(this);
  other->set_next_chunk(this);
715
}
716 717


718
void MemoryChunk::Unlink() {
719 720 721 722 723 724
  MemoryChunk* next_element = next_chunk();
  MemoryChunk* prev_element = prev_chunk();
  next_element->set_prev_chunk(prev_element);
  prev_element->set_next_chunk(next_element);
  set_prev_chunk(NULL);
  set_next_chunk(NULL);
725
}
726

727 728
MemoryChunk* MemoryAllocator::AllocateChunk(size_t reserve_area_size,
                                            size_t commit_area_size,
729 730
                                            Executability executable,
                                            Space* owner) {
731
  DCHECK_LE(commit_area_size, reserve_area_size);
732

733
  size_t chunk_size;
734
  Heap* heap = isolate_->heap();
735
  Address base = nullptr;
736
  base::VirtualMemory reservation;
737 738
  Address area_start = nullptr;
  Address area_end = nullptr;
739

740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769
  //
  // MemoryChunk layout:
  //
  //             Executable
  // +----------------------------+<- base aligned with MemoryChunk::kAlignment
  // |           Header           |
  // +----------------------------+<- base + CodePageGuardStartOffset
  // |           Guard            |
  // +----------------------------+<- area_start_
  // |           Area             |
  // +----------------------------+<- area_end_ (area_start + commit_area_size)
  // |   Committed but not used   |
  // +----------------------------+<- aligned at OS page boundary
  // | Reserved but not committed |
  // +----------------------------+<- aligned at OS page boundary
  // |           Guard            |
  // +----------------------------+<- base + chunk_size
  //
  //           Non-executable
  // +----------------------------+<- base aligned with MemoryChunk::kAlignment
  // |          Header            |
  // +----------------------------+<- area_start_ (base + kObjectStartOffset)
  // |           Area             |
  // +----------------------------+<- area_end_ (area_start + commit_area_size)
  // |  Committed but not used    |
  // +----------------------------+<- aligned at OS page boundary
  // | Reserved but not committed |
  // +----------------------------+<- base + chunk_size
  //

770
  if (executable == EXECUTABLE) {
771
    chunk_size = RoundUp(CodePageAreaStartOffset() + reserve_area_size,
772
                         GetCommitPageSize()) +
773
                 CodePageGuardSize();
774

775 776
    // Size of header (not executable) plus area (executable).
    size_t commit_size = RoundUp(CodePageGuardStartOffset() + commit_area_size,
777
                                 GetCommitPageSize());
778 779
    // Allocate executable memory either from code range or from the
    // OS.
780 781 782
#ifdef V8_TARGET_ARCH_MIPS64
    // Use code range only for large object space on mips64 to keep address
    // range within 256-MB memory region.
783
    if (code_range()->valid() && reserve_area_size > CodePageAreaSize()) {
784
#else
785
    if (code_range()->valid()) {
786
#endif
787 788
      base =
          code_range()->AllocateRawMemory(chunk_size, commit_size, &chunk_size);
789 790
      DCHECK(
          IsAligned(reinterpret_cast<intptr_t>(base), MemoryChunk::kAlignment));
791
      if (base == NULL) return NULL;
792
      size_.Increment(chunk_size);
793
      // Update executable memory size.
794
      size_executable_.Increment(chunk_size);
795
    } else {
796 797
      base = AllocateAlignedMemory(chunk_size, commit_size,
                                   MemoryChunk::kAlignment, executable,
798 799
                                   &reservation);
      if (base == NULL) return NULL;
800
      // Update executable memory size.
801
      size_executable_.Increment(reservation.size());
802
    }
803

804 805
    if (Heap::ShouldZapGarbage()) {
      ZapBlock(base, CodePageGuardStartOffset());
806
      ZapBlock(base + CodePageAreaStartOffset(), commit_area_size);
807 808
    }

809
    area_start = base + CodePageAreaStartOffset();
810
    area_end = area_start + commit_area_size;
811
  } else {
812
    chunk_size = RoundUp(MemoryChunk::kObjectStartOffset + reserve_area_size,
813
                         GetCommitPageSize());
814 815
    size_t commit_size =
        RoundUp(MemoryChunk::kObjectStartOffset + commit_area_size,
816
                GetCommitPageSize());
817 818 819
    base =
        AllocateAlignedMemory(chunk_size, commit_size, MemoryChunk::kAlignment,
                              executable, &reservation);
820

821
    if (base == NULL) return NULL;
822

823
    if (Heap::ShouldZapGarbage()) {
824
      ZapBlock(base, Page::kObjectStartOffset + commit_area_size);
825
    }
826 827

    area_start = base + Page::kObjectStartOffset;
828
    area_end = area_start + commit_area_size;
829 830
  }

831 832
  // Use chunk_size for statistics and callbacks because we assume that they
  // treat reserved but not-yet committed memory regions of chunks as allocated.
833 834
  isolate_->counters()->memory_allocated()->Increment(
      static_cast<int>(chunk_size));
835

836 837
  LOG(isolate_, NewEvent("MemoryChunk", base, chunk_size));

838 839 840 841 842 843 844 845
  // We cannot use the last chunk in the address space because we would
  // overflow when comparing top and limit if this chunk is used for a
  // linear allocation area.
  if ((reinterpret_cast<uintptr_t>(base) + chunk_size) == 0u) {
    CHECK(!last_chunk_.IsReserved());
    last_chunk_.TakeControl(&reservation);
    UncommitBlock(reinterpret_cast<Address>(last_chunk_.address()),
                  last_chunk_.size());
846
    size_.Decrement(chunk_size);
847
    if (executable == EXECUTABLE) {
848
      size_executable_.Decrement(chunk_size);
849 850 851 852 853 854
    }
    CHECK(last_chunk_.IsReserved());
    return AllocateChunk(reserve_area_size, commit_area_size, executable,
                         owner);
  }

855 856
  return MemoryChunk::Initialize(heap, base, chunk_size, area_start, area_end,
                                 executable, owner, &reservation);
857 858 859
}


860
void Page::ResetFreeListStatistics() {
861 862
  wasted_memory_ = 0;
  available_in_free_list_ = 0;
863 864
}

865 866
size_t Page::AvailableInFreeList() {
  size_t sum = 0;
krasin's avatar
krasin committed
867
  ForAllFreeListCategories([&sum](FreeListCategory* category) {
868 869 870 871 872
    sum += category->available();
  });
  return sum;
}

873
size_t Page::ShrinkToHighWaterMark() {
874 875 876 877 878
  // Shrinking only makes sense outside of the CodeRange, where we don't care
  // about address space fragmentation.
  base::VirtualMemory* reservation = reserved_memory();
  if (!reservation->IsReserved()) return 0;

879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894
  // Shrink pages to high water mark. The water mark points either to a filler
  // or the area_end.
  HeapObject* filler = HeapObject::FromAddress(HighWaterMark());
  if (filler->address() == area_end()) return 0;
  CHECK(filler->IsFiller());
  if (!filler->IsFreeSpace()) return 0;

#ifdef DEBUG
  // Check the the filler is indeed the last filler on the page.
  HeapObjectIterator it(this);
  HeapObject* filler2 = nullptr;
  for (HeapObject* obj = it.Next(); obj != nullptr; obj = it.Next()) {
    filler2 = HeapObject::FromAddress(obj->address() + obj->Size());
  }
  if (filler2 == nullptr || filler2->address() == area_end()) return 0;
  DCHECK(filler2->IsFiller());
895 896 897 898 899 900
  // The deserializer might leave behind fillers. In this case we need to
  // iterate even further.
  while ((filler2->address() + filler2->Size()) != area_end()) {
    filler2 = HeapObject::FromAddress(filler2->address() + filler2->Size());
    DCHECK(filler2->IsFiller());
  }
901 902 903 904 905
  DCHECK_EQ(filler->address(), filler2->address());
#endif  // DEBUG

  size_t unused = RoundDown(
      static_cast<size_t>(area_end() - filler->address() - FreeSpace::kSize),
906
      MemoryAllocator::GetCommitPageSize());
907
  if (unused > 0) {
908
    DCHECK_EQ(0u, unused % MemoryAllocator::GetCommitPageSize());
909 910 911 912 913 914 915 916 917 918
    if (FLAG_trace_gc_verbose) {
      PrintIsolate(heap()->isolate(), "Shrinking page %p: end %p -> %p\n",
                   reinterpret_cast<void*>(this),
                   reinterpret_cast<void*>(area_end()),
                   reinterpret_cast<void*>(area_end() - unused));
    }
    heap()->CreateFillerObjectAt(
        filler->address(),
        static_cast<int>(area_end() - filler->address() - unused),
        ClearRecordedSlots::kNo);
919
    heap()->memory_allocator()->PartialFreeMemory(
920
        this, address() + size() - unused, unused, area_end() - unused);
921 922 923 924 925 926
    CHECK(filler->IsFiller());
    CHECK_EQ(filler->address() + filler->Size(), area_end());
  }
  return unused;
}

927 928 929 930 931
void Page::CreateBlackArea(Address start, Address end) {
  DCHECK(heap()->incremental_marking()->black_allocation());
  DCHECK_EQ(Page::FromAddress(start), this);
  DCHECK_NE(start, end);
  DCHECK_EQ(Page::FromAddress(end - 1), this);
932 933
  MarkingState::Internal(this).bitmap()->SetRange(AddressToMarkbitIndex(start),
                                                  AddressToMarkbitIndex(end));
934 935 936
  MarkingState::Internal(this)
      .IncrementLiveBytes<IncrementalMarking::kAtomicity>(
          static_cast<int>(end - start));
937 938
}

939 940 941 942 943
void Page::DestroyBlackArea(Address start, Address end) {
  DCHECK(heap()->incremental_marking()->black_allocation());
  DCHECK_EQ(Page::FromAddress(start), this);
  DCHECK_NE(start, end);
  DCHECK_EQ(Page::FromAddress(end - 1), this);
944 945
  MarkingState::Internal(this).bitmap()->ClearRange(
      AddressToMarkbitIndex(start), AddressToMarkbitIndex(end));
946 947 948
  MarkingState::Internal(this)
      .IncrementLiveBytes<IncrementalMarking::kAtomicity>(
          -static_cast<int>(end - start));
949 950
}

951
void MemoryAllocator::PartialFreeMemory(MemoryChunk* chunk, Address start_free,
952 953
                                        size_t bytes_to_free,
                                        Address new_area_end) {
954 955
  base::VirtualMemory* reservation = chunk->reserved_memory();
  DCHECK(reservation->IsReserved());
956
  chunk->size_ -= bytes_to_free;
957
  chunk->area_end_ = new_area_end;
958 959 960 961 962
  if (chunk->IsFlagSet(MemoryChunk::IS_EXECUTABLE)) {
    DCHECK_EQ(0, reinterpret_cast<uintptr_t>(chunk->area_end_) %
                     static_cast<uintptr_t>(GetCommitPageSize()));
    DCHECK_EQ(chunk->address() + chunk->size(),
              chunk->area_end() + CodePageGuardSize());
963 964 965 966 967 968 969 970 971 972
    reservation->Guard(chunk->area_end_);
  }
  // On e.g. Windows, a reservation may be larger than a page and releasing
  // partially starting at |start_free| will also release the potentially
  // unused part behind the current page.
  const size_t released_bytes = reservation->ReleasePartial(start_free);
  DCHECK_GE(size_.Value(), released_bytes);
  size_.Decrement(released_bytes);
  isolate_->counters()->memory_allocated()->Decrement(
      static_cast<int>(released_bytes));
973 974
}

975 976
void MemoryAllocator::PreFreeMemory(MemoryChunk* chunk) {
  DCHECK(!chunk->IsFlagSet(MemoryChunk::PRE_FREED));
977
  LOG(isolate_, DeleteEvent("MemoryChunk", chunk));
978

979 980
  isolate_->heap()->RememberUnmappedPage(reinterpret_cast<Address>(chunk),
                                         chunk->IsEvacuationCandidate());
981

982
  base::VirtualMemory* reservation = chunk->reserved_memory();
983 984 985 986
  const size_t size =
      reservation->IsReserved() ? reservation->size() : chunk->size();
  DCHECK_GE(size_.Value(), static_cast<size_t>(size));
  size_.Decrement(size);
987 988
  isolate_->counters()->memory_allocated()->Decrement(static_cast<int>(size));
  if (chunk->executable() == EXECUTABLE) {
989 990
    DCHECK_GE(size_executable_.Value(), size);
    size_executable_.Decrement(size);
991 992 993 994 995 996 997 998 999
  }

  chunk->SetFlag(MemoryChunk::PRE_FREED);
}


void MemoryAllocator::PerformFreeMemory(MemoryChunk* chunk) {
  DCHECK(chunk->IsFlagSet(MemoryChunk::PRE_FREED));
  chunk->ReleaseAllocatedMemory();
1000

1001
  base::VirtualMemory* reservation = chunk->reserved_memory();
1002 1003
  if (chunk->IsFlagSet(MemoryChunk::POOLED)) {
    UncommitBlock(reinterpret_cast<Address>(chunk), MemoryChunk::kPageSize);
1004
  } else {
1005 1006 1007 1008 1009
    if (reservation->IsReserved()) {
      FreeMemory(reservation, chunk->executable());
    } else {
      FreeMemory(chunk->address(), chunk->size(), chunk->executable());
    }
1010
  }
1011 1012
}

1013
template <MemoryAllocator::FreeMode mode>
1014
void MemoryAllocator::Free(MemoryChunk* chunk) {
1015 1016 1017 1018 1019
  switch (mode) {
    case kFull:
      PreFreeMemory(chunk);
      PerformFreeMemory(chunk);
      break;
1020 1021 1022 1023 1024
    case kAlreadyPooled:
      // Pooled pages cannot be touched anymore as their memory is uncommitted.
      FreeMemory(chunk->address(), static_cast<size_t>(MemoryChunk::kPageSize),
                 Executability::NOT_EXECUTABLE);
      break;
1025 1026 1027 1028 1029 1030 1031 1032 1033 1034
    case kPooledAndQueue:
      DCHECK_EQ(chunk->size(), static_cast<size_t>(MemoryChunk::kPageSize));
      DCHECK_EQ(chunk->executable(), NOT_EXECUTABLE);
      chunk->SetFlag(MemoryChunk::POOLED);
    // Fall through to kPreFreeAndQueue.
    case kPreFreeAndQueue:
      PreFreeMemory(chunk);
      // The chunks added to this queue will be freed by a concurrent thread.
      unmapper()->AddMemoryChunkSafe(chunk);
      break;
1035 1036 1037
  }
}

1038 1039
template void MemoryAllocator::Free<MemoryAllocator::kFull>(MemoryChunk* chunk);

1040 1041 1042
template void MemoryAllocator::Free<MemoryAllocator::kAlreadyPooled>(
    MemoryChunk* chunk);

1043
template void MemoryAllocator::Free<MemoryAllocator::kPreFreeAndQueue>(
1044 1045
    MemoryChunk* chunk);

1046
template void MemoryAllocator::Free<MemoryAllocator::kPooledAndQueue>(
1047 1048
    MemoryChunk* chunk);

1049
template <MemoryAllocator::AllocationMode alloc_mode, typename SpaceType>
1050
Page* MemoryAllocator::AllocatePage(size_t size, SpaceType* owner,
1051
                                    Executability executable) {
1052
  MemoryChunk* chunk = nullptr;
1053
  if (alloc_mode == kPooled) {
1054
    DCHECK_EQ(size, static_cast<size_t>(MemoryChunk::kAllocatableMemory));
1055 1056 1057 1058 1059 1060 1061
    DCHECK_EQ(executable, NOT_EXECUTABLE);
    chunk = AllocatePagePooled(owner);
  }
  if (chunk == nullptr) {
    chunk = AllocateChunk(size, size, executable, owner);
  }
  if (chunk == nullptr) return nullptr;
1062 1063 1064 1065 1066
  return Page::Initialize(isolate_->heap(), chunk, executable, owner);
}

template Page*
MemoryAllocator::AllocatePage<MemoryAllocator::kRegular, PagedSpace>(
1067
    size_t size, PagedSpace* owner, Executability executable);
1068 1069
template Page*
MemoryAllocator::AllocatePage<MemoryAllocator::kRegular, SemiSpace>(
1070
    size_t size, SemiSpace* owner, Executability executable);
1071 1072
template Page*
MemoryAllocator::AllocatePage<MemoryAllocator::kPooled, SemiSpace>(
1073
    size_t size, SemiSpace* owner, Executability executable);
1074

1075
LargePage* MemoryAllocator::AllocateLargePage(size_t size,
1076 1077 1078 1079 1080
                                              LargeObjectSpace* owner,
                                              Executability executable) {
  MemoryChunk* chunk = AllocateChunk(size, size, executable, owner);
  if (chunk == nullptr) return nullptr;
  return LargePage::Initialize(isolate_->heap(), chunk, executable, owner);
1081 1082 1083 1084
}

template <typename SpaceType>
MemoryChunk* MemoryAllocator::AllocatePagePooled(SpaceType* owner) {
1085 1086
  MemoryChunk* chunk = unmapper()->TryGetPooledMemoryChunkSafe();
  if (chunk == nullptr) return nullptr;
1087 1088 1089 1090
  const int size = MemoryChunk::kPageSize;
  const Address start = reinterpret_cast<Address>(chunk);
  const Address area_start = start + MemoryChunk::kObjectStartOffset;
  const Address area_end = start + size;
1091 1092 1093
  if (!CommitBlock(reinterpret_cast<Address>(chunk), size, NOT_EXECUTABLE)) {
    return nullptr;
  }
1094 1095 1096 1097 1098
  base::VirtualMemory reservation(start, size);
  MemoryChunk::Initialize(isolate_->heap(), start, size, area_start, area_end,
                          NOT_EXECUTABLE, owner, &reservation);
  size_.Increment(size);
  return chunk;
1099 1100
}

1101
bool MemoryAllocator::CommitBlock(Address start, size_t size,
1102 1103
                                  Executability executable) {
  if (!CommitMemory(start, size, executable)) return false;
1104 1105 1106 1107 1108

  if (Heap::ShouldZapGarbage()) {
    ZapBlock(start, size);
  }

1109
  isolate_->counters()->memory_allocated()->Increment(static_cast<int>(size));
1110 1111 1112
  return true;
}

1113

1114
bool MemoryAllocator::UncommitBlock(Address start, size_t size) {
1115
  if (!base::VirtualMemory::UncommitRegion(start, size)) return false;
1116
  isolate_->counters()->memory_allocated()->Decrement(static_cast<int>(size));
1117 1118
  return true;
}
1119

1120 1121 1122 1123 1124 1125 1126

void MemoryAllocator::ZapBlock(Address start, size_t size) {
  for (size_t s = 0; s + kPointerSize <= size; s += kPointerSize) {
    Memory::Address_at(start + s) = kZapValue;
  }
}

1127 1128
#ifdef DEBUG
void MemoryAllocator::ReportStatistics() {
1129
  size_t size = Size();
1130
  float pct = static_cast<float>(capacity_ - size) / capacity_;
1131
  PrintF("  capacity: %zu , used: %" PRIuS ", available: %%%d\n\n",
1132
         capacity_, size, static_cast<int>(pct * 100));
1133 1134 1135
}
#endif

1136
size_t MemoryAllocator::CodePageGuardStartOffset() {
1137 1138
  // We are guarding code pages: the first OS page after the header
  // will be protected as non-writable.
1139
  return RoundUp(Page::kObjectStartOffset, GetCommitPageSize());
1140 1141
}

1142
size_t MemoryAllocator::CodePageGuardSize() {
1143
  return static_cast<int>(GetCommitPageSize());
1144 1145
}

1146
size_t MemoryAllocator::CodePageAreaStartOffset() {
1147 1148 1149 1150 1151
  // We are guarding code pages: the first OS page after the header
  // will be protected as non-writable.
  return CodePageGuardStartOffset() + CodePageGuardSize();
}

1152
size_t MemoryAllocator::CodePageAreaEndOffset() {
1153 1154
  // We are guarding code pages: the last OS page will be protected as
  // non-writable.
1155 1156 1157 1158 1159 1160 1161 1162 1163 1164
  return Page::kPageSize - static_cast<int>(GetCommitPageSize());
}

intptr_t MemoryAllocator::GetCommitPageSize() {
  if (FLAG_v8_os_page_size != 0) {
    DCHECK(base::bits::IsPowerOfTwo32(FLAG_v8_os_page_size));
    return FLAG_v8_os_page_size * KB;
  } else {
    return base::OS::CommitPageSize();
  }
1165 1166 1167
}


1168
bool MemoryAllocator::CommitExecutableMemory(base::VirtualMemory* vm,
1169
                                             Address start, size_t commit_size,
1170
                                             size_t reserved_size) {
1171
  // Commit page header (not executable).
1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187 1188 1189 1190 1191
  Address header = start;
  size_t header_size = CodePageGuardStartOffset();
  if (vm->Commit(header, header_size, false)) {
    // Create guard page after the header.
    if (vm->Guard(start + CodePageGuardStartOffset())) {
      // Commit page body (executable).
      Address body = start + CodePageAreaStartOffset();
      size_t body_size = commit_size - CodePageGuardStartOffset();
      if (vm->Commit(body, body_size, true)) {
        // Create guard page before the end.
        if (vm->Guard(start + reserved_size - CodePageGuardSize())) {
          UpdateAllocatedSpaceLimits(start, start + CodePageAreaStartOffset() +
                                                commit_size -
                                                CodePageGuardStartOffset());
          return true;
        }
        vm->Uncommit(body, body_size);
      }
    }
    vm->Uncommit(header, header_size);
1192
  }
1193
  return false;
1194 1195 1196
}


1197 1198 1199
// -----------------------------------------------------------------------------
// MemoryChunk implementation

1200 1201 1202 1203
bool MemoryChunk::contains_array_buffers() {
  return local_tracker() != nullptr && !local_tracker()->IsEmpty();
}

1204
void MemoryChunk::ReleaseAllocatedMemory() {
1205 1206 1207 1208 1209 1210 1211 1212
  if (skip_list_ != nullptr) {
    delete skip_list_;
    skip_list_ = nullptr;
  }
  if (mutex_ != nullptr) {
    delete mutex_;
    mutex_ = nullptr;
  }
1213 1214 1215 1216
  ReleaseSlotSet<OLD_TO_NEW>();
  ReleaseSlotSet<OLD_TO_OLD>();
  ReleaseTypedSlotSet<OLD_TO_NEW>();
  ReleaseTypedSlotSet<OLD_TO_OLD>();
1217
  if (local_tracker_ != nullptr) ReleaseLocalTracker();
1218
  if (young_generation_bitmap_ != nullptr) ReleaseYoungGenerationBitmap();
ulan's avatar
ulan committed
1219 1220
}

1221
static SlotSet* AllocateAndInitializeSlotSet(size_t size, Address page_start) {
1222
  size_t pages = (size + Page::kPageSize - 1) / Page::kPageSize;
ulan's avatar
ulan committed
1223
  DCHECK(pages > 0);
1224
  SlotSet* slot_set = new SlotSet[pages];
ulan's avatar
ulan committed
1225
  for (size_t i = 0; i < pages; i++) {
1226
    slot_set[i].SetPageStart(page_start + i * Page::kPageSize);
ulan's avatar
ulan committed
1227
  }
1228 1229 1230
  return slot_set;
}

1231 1232
template SlotSet* MemoryChunk::AllocateSlotSet<OLD_TO_NEW>();
template SlotSet* MemoryChunk::AllocateSlotSet<OLD_TO_OLD>();
ulan's avatar
ulan committed
1233

1234 1235 1236
template <RememberedSetType type>
SlotSet* MemoryChunk::AllocateSlotSet() {
  SlotSet* slot_set = AllocateAndInitializeSlotSet(size_, address());
1237 1238 1239
  SlotSet* old_slot_set = base::AsAtomicWord::Release_CompareAndSwap(
      &slot_set_[type], nullptr, slot_set);
  if (old_slot_set != nullptr) {
1240
    delete[] slot_set;
1241
    slot_set = old_slot_set;
1242
  }
1243
  DCHECK(slot_set);
1244
  return slot_set;
1245 1246
}

1247 1248
template void MemoryChunk::ReleaseSlotSet<OLD_TO_NEW>();
template void MemoryChunk::ReleaseSlotSet<OLD_TO_OLD>();
1249

1250 1251
template <RememberedSetType type>
void MemoryChunk::ReleaseSlotSet() {
1252
  SlotSet* slot_set = slot_set_[type];
1253
  if (slot_set) {
1254
    slot_set_[type] = nullptr;
1255 1256
    delete[] slot_set;
  }
1257
}
1258

1259 1260
template TypedSlotSet* MemoryChunk::AllocateTypedSlotSet<OLD_TO_NEW>();
template TypedSlotSet* MemoryChunk::AllocateTypedSlotSet<OLD_TO_OLD>();
1261

1262 1263
template <RememberedSetType type>
TypedSlotSet* MemoryChunk::AllocateTypedSlotSet() {
1264 1265 1266 1267 1268 1269
  TypedSlotSet* typed_slot_set = new TypedSlotSet(address());
  TypedSlotSet* old_value = base::AsAtomicWord::Release_CompareAndSwap(
      &typed_slot_set_[type], nullptr, typed_slot_set);
  if (old_value != nullptr) {
    delete typed_slot_set;
    typed_slot_set = old_value;
1270
  }
1271 1272
  DCHECK(typed_slot_set);
  return typed_slot_set;
1273 1274
}

1275 1276
template void MemoryChunk::ReleaseTypedSlotSet<OLD_TO_NEW>();
template void MemoryChunk::ReleaseTypedSlotSet<OLD_TO_OLD>();
1277

1278 1279
template <RememberedSetType type>
void MemoryChunk::ReleaseTypedSlotSet() {
1280
  TypedSlotSet* typed_slot_set = typed_slot_set_[type];
1281
  if (typed_slot_set) {
1282
    typed_slot_set_[type] = nullptr;
1283 1284
    delete typed_slot_set;
  }
1285
}
1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297

void MemoryChunk::AllocateLocalTracker() {
  DCHECK_NULL(local_tracker_);
  local_tracker_ = new LocalArrayBufferTracker(heap());
}

void MemoryChunk::ReleaseLocalTracker() {
  DCHECK_NOT_NULL(local_tracker_);
  delete local_tracker_;
  local_tracker_ = nullptr;
}

1298
void MemoryChunk::AllocateYoungGenerationBitmap() {
1299 1300 1301 1302
  DCHECK_NULL(young_generation_bitmap_);
  young_generation_bitmap_ = static_cast<Bitmap*>(calloc(1, Bitmap::kSize));
}

1303
void MemoryChunk::ReleaseYoungGenerationBitmap() {
1304 1305 1306 1307 1308
  DCHECK_NOT_NULL(young_generation_bitmap_);
  free(young_generation_bitmap_);
  young_generation_bitmap_ = nullptr;
}

1309 1310 1311
// -----------------------------------------------------------------------------
// PagedSpace implementation

1312 1313
STATIC_ASSERT(static_cast<ObjectSpace>(1 << AllocationSpace::NEW_SPACE) ==
              ObjectSpace::kObjectSpaceNewSpace);
1314 1315
STATIC_ASSERT(static_cast<ObjectSpace>(1 << AllocationSpace::OLD_SPACE) ==
              ObjectSpace::kObjectSpaceOldSpace);
1316 1317 1318 1319 1320
STATIC_ASSERT(static_cast<ObjectSpace>(1 << AllocationSpace::CODE_SPACE) ==
              ObjectSpace::kObjectSpaceCodeSpace);
STATIC_ASSERT(static_cast<ObjectSpace>(1 << AllocationSpace::MAP_SPACE) ==
              ObjectSpace::kObjectSpaceMapSpace);

1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335 1336
void Space::AddAllocationObserver(AllocationObserver* observer) {
  allocation_observers_->Add(observer);
}

void Space::RemoveAllocationObserver(AllocationObserver* observer) {
  bool removed = allocation_observers_->RemoveElement(observer);
  USE(removed);
  DCHECK(removed);
}

void Space::PauseAllocationObservers() { allocation_observers_paused_ = true; }

void Space::ResumeAllocationObservers() {
  allocation_observers_paused_ = false;
}

1337 1338 1339 1340 1341 1342 1343 1344
void Space::AllocationStep(Address soon_object, int size) {
  if (!allocation_observers_paused_) {
    for (int i = 0; i < allocation_observers_->length(); ++i) {
      AllocationObserver* o = (*allocation_observers_)[i];
      o->AllocationStep(size, soon_object, size);
    }
  }
}
1345

1346
PagedSpace::PagedSpace(Heap* heap, AllocationSpace space,
1347
                       Executability executable)
1348
    : Space(heap, space, executable), anchor_(this), free_list_(this) {
1349
  area_size_ = MemoryAllocator::PageAreaSize(space);
1350 1351
  accounting_stats_.Clear();

1352
  allocation_info_.Reset(nullptr, nullptr);
1353 1354 1355
}


1356
bool PagedSpace::SetUp() { return true; }
1357 1358


1359
bool PagedSpace::HasBeenSetUp() { return true; }
1360 1361 1362


void PagedSpace::TearDown() {
1363 1364
  for (auto it = begin(); it != end();) {
    Page* page = *(it++);  // Will be erased.
1365
    ArrayBufferTracker::FreeAll(page);
1366
    heap()->memory_allocator()->Free<MemoryAllocator::kFull>(page);
1367
  }
1368 1369 1370
  anchor_.set_next_page(&anchor_);
  anchor_.set_prev_page(&anchor_);
  accounting_stats_.Clear();
1371 1372
}

1373
void PagedSpace::RefillFreeList() {
1374 1375 1376 1377
  // Any PagedSpace might invoke RefillFreeList. We filter all but our old
  // generation spaces out.
  if (identity() != OLD_SPACE && identity() != CODE_SPACE &&
      identity() != MAP_SPACE) {
1378 1379 1380
    return;
  }
  MarkCompactCollector* collector = heap()->mark_compact_collector();
1381 1382
  intptr_t added = 0;
  {
mlippautz's avatar
mlippautz committed
1383 1384
    Page* p = nullptr;
    while ((p = collector->sweeper().GetSweptPageSafe(this)) != nullptr) {
1385 1386 1387 1388 1389 1390 1391 1392 1393 1394 1395 1396
      // Only during compaction pages can actually change ownership. This is
      // safe because there exists no other competing action on the page links
      // during compaction.
      if (is_local() && (p->owner() != this)) {
        base::LockGuard<base::Mutex> guard(
            reinterpret_cast<PagedSpace*>(p->owner())->mutex());
        p->Unlink();
        p->set_owner(this);
        p->InsertAfter(anchor_.prev_page());
      }
      added += RelinkFreeListCategories(p);
      added += p->wasted_memory();
mlippautz's avatar
mlippautz committed
1397
      if (is_local() && (added > kCompactionMemoryWanted)) break;
1398
    }
1399
  }
1400
  accounting_stats_.IncreaseCapacity(added);
1401 1402
}

1403
void PagedSpace::MergeCompactionSpace(CompactionSpace* other) {
1404
  DCHECK(identity() == other->identity());
1405 1406 1407 1408
  // Unmerged fields:
  //   area_size_
  //   anchor_

1409
  other->EmptyAllocationInfo();
1410 1411 1412

  // Update and clear accounting statistics.
  accounting_stats_.Merge(other->accounting_stats_);
1413 1414 1415 1416 1417 1418
  other->accounting_stats_.Clear();

  // The linear allocation area of {other} should be destroyed now.
  DCHECK(other->top() == nullptr);
  DCHECK(other->limit() == nullptr);

1419 1420
  AccountCommitted(other->CommittedMemory());

1421
  // Move over pages.
1422 1423
  for (auto it = other->begin(); it != other->end();) {
    Page* p = *(it++);
1424 1425 1426 1427

    // Relinking requires the category to be unlinked.
    other->UnlinkFreeListCategories(p);

1428 1429 1430
    p->Unlink();
    p->set_owner(this);
    p->InsertAfter(anchor_.prev_page());
1431
    RelinkFreeListCategories(p);
1432
    DCHECK_EQ(p->AvailableInFreeList(), p->available_in_free_list());
1433 1434 1435 1436
  }
}


1437
size_t PagedSpace::CommittedPhysicalMemory() {
1438
  if (!base::VirtualMemory::HasLazyCommits()) return CommittedMemory();
1439
  MemoryChunk::UpdateHighWaterMark(allocation_info_.top());
1440
  size_t size = 0;
1441 1442
  for (Page* page : *this) {
    size += page->CommittedPhysicalMemory();
1443 1444 1445 1446
  }
  return size;
}

1447
bool PagedSpace::ContainsSlow(Address addr) {
1448
  Page* p = Page::FromAddress(addr);
1449 1450
  for (Page* page : *this) {
    if (page == p) return true;
1451 1452 1453 1454
  }
  return false;
}

1455 1456 1457 1458 1459 1460 1461 1462 1463 1464 1465 1466 1467 1468 1469 1470 1471 1472 1473 1474 1475 1476 1477 1478 1479 1480 1481 1482 1483 1484 1485 1486 1487
Page* PagedSpace::RemovePageSafe(int size_in_bytes) {
  base::LockGuard<base::Mutex> guard(mutex());

  // Check for pages that still contain free list entries. Bail out for smaller
  // categories.
  const int minimum_category =
      static_cast<int>(FreeList::SelectFreeListCategoryType(size_in_bytes));
  Page* page = free_list()->GetPageForCategoryType(kHuge);
  if (!page && static_cast<int>(kLarge) >= minimum_category)
    page = free_list()->GetPageForCategoryType(kLarge);
  if (!page && static_cast<int>(kMedium) >= minimum_category)
    page = free_list()->GetPageForCategoryType(kMedium);
  if (!page && static_cast<int>(kSmall) >= minimum_category)
    page = free_list()->GetPageForCategoryType(kSmall);
  if (!page) return nullptr;

  AccountUncommitted(page->size());
  accounting_stats_.DeallocateBytes(page->LiveBytesFromFreeList());
  accounting_stats_.DecreaseCapacity(page->area_size());
  page->Unlink();
  UnlinkFreeListCategories(page);
  return page;
}

void PagedSpace::AddPage(Page* page) {
  AccountCommitted(page->size());
  accounting_stats_.IncreaseCapacity(page->area_size());
  accounting_stats_.AllocateBytes(page->LiveBytesFromFreeList());
  page->set_owner(this);
  RelinkFreeListCategories(page);
  page->InsertAfter(anchor()->prev_page());
}

1488 1489 1490 1491 1492 1493 1494 1495 1496 1497
void PagedSpace::ShrinkImmortalImmovablePages() {
  DCHECK(!heap()->deserialization_complete());
  MemoryChunk::UpdateHighWaterMark(allocation_info_.top());
  EmptyAllocationInfo();
  ResetFreeList();

  for (Page* page : *this) {
    DCHECK(page->IsFlagSet(Page::NEVER_EVACUATE));
    size_t unused = page->ShrinkToHighWaterMark();
    accounting_stats_.DecreaseCapacity(static_cast<intptr_t>(unused));
1498
    AccountUncommitted(unused);
1499
  }
1500 1501 1502
}

bool PagedSpace::Expand() {
1503 1504 1505 1506
  // Always lock against the main space as we can only adjust capacity and
  // pages concurrently for the main paged space.
  base::LockGuard<base::Mutex> guard(heap()->paged_space(identity())->mutex());

1507
  const int size = AreaSize();
1508

1509
  if (!heap()->CanExpandOldGeneration(size)) return false;
1510

1511
  Page* p = heap()->memory_allocator()->AllocatePage(size, this, executable());
1512
  if (p == nullptr) return false;
1513

1514
  AccountCommitted(p->size());
1515

1516 1517 1518
  // Pages created during bootstrapping may contain immortal immovable objects.
  if (!heap()->deserialization_complete()) p->MarkNeverEvacuate();

1519
  DCHECK(Capacity() <= heap()->MaxOldGenerationSize());
1520

1521
  p->InsertAfter(anchor_.prev_page());
1522 1523 1524 1525 1526 1527 1528

  return true;
}


int PagedSpace::CountTotalPages() {
  int count = 0;
1529
  for (Page* page : *this) {
1530
    count++;
1531
    USE(page);
1532 1533 1534 1535 1536
  }
  return count;
}


1537
void PagedSpace::ResetFreeListStatistics() {
1538
  for (Page* page : *this) {
1539 1540 1541 1542
    page->ResetFreeListStatistics();
  }
}

1543 1544 1545 1546
void PagedSpace::SetAllocationInfo(Address top, Address limit) {
  SetTopAndLimit(top, limit);
  if (top != nullptr && top != limit &&
      heap()->incremental_marking()->black_allocation()) {
1547
    Page::FromAllocationAreaAddress(top)->CreateBlackArea(top, limit);
1548 1549 1550 1551 1552 1553 1554 1555
  }
}

void PagedSpace::MarkAllocationInfoBlack() {
  DCHECK(heap()->incremental_marking()->black_allocation());
  Address current_top = top();
  Address current_limit = limit();
  if (current_top != nullptr && current_top != current_limit) {
1556 1557
    Page::FromAllocationAreaAddress(current_top)
        ->CreateBlackArea(current_top, current_limit);
1558 1559 1560
  }
}

1561 1562 1563 1564 1565 1566 1567 1568 1569
void PagedSpace::UnmarkAllocationInfo() {
  Address current_top = top();
  Address current_limit = limit();
  if (current_top != nullptr && current_top != current_limit) {
    Page::FromAllocationAreaAddress(current_top)
        ->DestroyBlackArea(current_top, current_limit);
  }
}

1570 1571 1572 1573 1574 1575 1576 1577 1578 1579
// Empty space allocation info, returning unused area to free list.
void PagedSpace::EmptyAllocationInfo() {
  // Mark the old linear allocation area with a free space map so it can be
  // skipped when scanning the heap.
  Address current_top = top();
  Address current_limit = limit();
  if (current_top == nullptr) {
    DCHECK(current_limit == nullptr);
    return;
  }
1580 1581

  if (heap()->incremental_marking()->black_allocation()) {
1582
    Page* page = Page::FromAllocationAreaAddress(current_top);
1583 1584 1585

    // Clear the bits in the unused black area.
    if (current_top != current_limit) {
1586 1587 1588
      MarkingState::Internal(page).bitmap()->ClearRange(
          page->AddressToMarkbitIndex(current_top),
          page->AddressToMarkbitIndex(current_limit));
1589 1590 1591
      MarkingState::Internal(page)
          .IncrementLiveBytes<IncrementalMarking::kAtomicity>(
              -static_cast<int>(current_limit - current_top));
1592
    }
1593
  }
1594 1595

  SetTopAndLimit(NULL, NULL);
1596 1597
  DCHECK_GE(current_limit, current_top);
  Free(current_top, current_limit - current_top);
1598
}
1599

1600 1601
void PagedSpace::IncreaseCapacity(size_t bytes) {
  accounting_stats_.ExpandSpace(bytes);
1602 1603
}

1604
void PagedSpace::ReleasePage(Page* page) {
1605
  DCHECK_EQ(0, MarkingState::Internal(page).live_bytes());
1606
  DCHECK_EQ(page->owner(), this);
1607

1608
  free_list_.EvictFreeListItems(page);
1609
  DCHECK(!free_list_.ContainsPageFreeListItems(page));
1610

1611
  if (Page::FromAllocationAreaAddress(allocation_info_.top()) == page) {
1612
    allocation_info_.Reset(nullptr, nullptr);
1613 1614
  }

1615 1616 1617 1618 1619 1620
  // If page is still in a list, unlink it from that list.
  if (page->next_chunk() != NULL) {
    DCHECK(page->prev_chunk() != NULL);
    page->Unlink();
  }

1621
  AccountUncommitted(page->size());
1622
  accounting_stats_.ShrinkSpace(page->area_size());
1623
  heap()->memory_allocator()->Free<MemoryAllocator::kPreFreeAndQueue>(page);
1624 1625
}

1626 1627 1628 1629
std::unique_ptr<ObjectIterator> PagedSpace::GetObjectIterator() {
  return std::unique_ptr<ObjectIterator>(new HeapObjectIterator(this));
}

1630
#ifdef DEBUG
1631
void PagedSpace::Print() {}
1632 1633
#endif

1634
#ifdef VERIFY_HEAP
1635
void PagedSpace::Verify(ObjectVisitor* visitor) {
1636
  bool allocation_pointer_found_in_space =
1637
      (allocation_info_.top() == allocation_info_.limit());
1638
  for (Page* page : *this) {
1639
    CHECK(page->owner() == this);
1640
    if (page == Page::FromAllocationAreaAddress(allocation_info_.top())) {
1641 1642
      allocation_pointer_found_in_space = true;
    }
1643
    CHECK(page->SweepingDone());
1644
    HeapObjectIterator it(page);
1645 1646
    Address end_of_previous_object = page->area_start();
    Address top = page->area_end();
1647 1648
    int black_size = 0;
    for (HeapObject* object = it.Next(); object != NULL; object = it.Next()) {
1649
      CHECK(end_of_previous_object <= object->address());
1650 1651 1652 1653

      // The first word should be a map, and we expect all map pointers to
      // be in map space.
      Map* map = object->map();
1654 1655
      CHECK(map->IsMap());
      CHECK(heap()->map_space()->Contains(map));
1656 1657 1658 1659 1660

      // Perform space-specific object verification.
      VerifyObject(object);

      // The object itself should look OK.
1661
      object->ObjectVerify();
1662

1663 1664 1665
      if (!FLAG_verify_heap_skip_remembered_set) {
        heap()->VerifyRememberedSetFor(object);
      }
1666

1667 1668 1669
      // All the interior pointers should be contained in the heap.
      int size = object->Size();
      object->IterateBody(map->instance_type(), size, visitor);
1670 1671
      if (ObjectMarking::IsBlack<IncrementalMarking::kAtomicity>(
              object, MarkingState::Internal(object))) {
1672
        black_size += size;
1673 1674
      }

1675
      CHECK(object->address() + size <= top);
1676
      end_of_previous_object = object->address() + size;
1677
    }
1678
    CHECK_LE(black_size,
1679
             MarkingState::Internal(page).live_bytes<AccessMode::ATOMIC>());
1680
  }
1681
  CHECK(allocation_pointer_found_in_space);
1682
}
1683
#endif  // VERIFY_HEAP
1684

1685 1686 1687
// -----------------------------------------------------------------------------
// NewSpace implementation

1688 1689
bool NewSpace::SetUp(size_t initial_semispace_capacity,
                     size_t maximum_semispace_capacity) {
1690
  DCHECK(initial_semispace_capacity <= maximum_semispace_capacity);
1691 1692
  DCHECK(base::bits::IsPowerOfTwo32(
      static_cast<uint32_t>(maximum_semispace_capacity)));
1693

1694 1695 1696 1697 1698 1699 1700 1701
  to_space_.SetUp(initial_semispace_capacity, maximum_semispace_capacity);
  from_space_.SetUp(initial_semispace_capacity, maximum_semispace_capacity);
  if (!to_space_.Commit()) {
    return false;
  }
  DCHECK(!from_space_.is_committed());  // No need to use memory yet.
  ResetAllocationInfo();

1702
  // Allocate and set up the histogram arrays if necessary.
1703 1704
  allocated_histogram_ = NewArray<HistogramInfo>(LAST_TYPE + 1);
  promoted_histogram_ = NewArray<HistogramInfo>(LAST_TYPE + 1);
1705 1706 1707
#define SET_NAME(name)                        \
  allocated_histogram_[name].set_name(#name); \
  promoted_histogram_[name].set_name(#name);
1708 1709 1710 1711 1712 1713 1714 1715 1716 1717 1718 1719 1720 1721 1722 1723 1724
  INSTANCE_TYPE_LIST(SET_NAME)
#undef SET_NAME

  return true;
}


void NewSpace::TearDown() {
  if (allocated_histogram_) {
    DeleteArray(allocated_histogram_);
    allocated_histogram_ = NULL;
  }
  if (promoted_histogram_) {
    DeleteArray(promoted_histogram_);
    promoted_histogram_ = NULL;
  }

1725 1726
  allocation_info_.Reset(nullptr, nullptr);

1727 1728
  to_space_.TearDown();
  from_space_.TearDown();
1729 1730
}

1731
void NewSpace::Flip() { SemiSpace::Swap(&from_space_, &to_space_); }
1732 1733


1734
void NewSpace::Grow() {
1735
  // Double the semispace size but only up to maximum capacity.
1736
  DCHECK(TotalCapacity() < MaximumCapacity());
1737
  size_t new_capacity =
1738
      Min(MaximumCapacity(),
1739
          static_cast<size_t>(FLAG_semi_space_growth_factor) * TotalCapacity());
1740
  if (to_space_.GrowTo(new_capacity)) {
1741
    // Only grow from space if we managed to grow to-space.
1742
    if (!from_space_.GrowTo(new_capacity)) {
1743 1744
      // If we managed to grow to-space but couldn't grow from-space,
      // attempt to shrink to-space.
mlippautz's avatar
mlippautz committed
1745
      if (!to_space_.ShrinkTo(from_space_.current_capacity())) {
1746 1747
        // We are in an inconsistent state because we could not
        // commit/uncommit memory from new space.
1748
        CHECK(false);
1749 1750 1751
      }
    }
  }
1752
  DCHECK_SEMISPACE_ALLOCATION_INFO(allocation_info_, to_space_);
1753 1754 1755 1756
}


void NewSpace::Shrink() {
1757 1758
  size_t new_capacity = Max(InitialTotalCapacity(), 2 * Size());
  size_t rounded_new_capacity = RoundUp(new_capacity, Page::kPageSize);
1759
  if (rounded_new_capacity < TotalCapacity() &&
1760
      to_space_.ShrinkTo(rounded_new_capacity)) {
1761 1762
    // Only shrink from-space if we managed to shrink to-space.
    from_space_.Reset();
1763
    if (!from_space_.ShrinkTo(rounded_new_capacity)) {
1764 1765
      // If we managed to shrink to-space but couldn't shrink from
      // space, attempt to grow to-space again.
mlippautz's avatar
mlippautz committed
1766
      if (!to_space_.GrowTo(from_space_.current_capacity())) {
1767 1768
        // We are in an inconsistent state because we could not
        // commit/uncommit memory from new space.
1769
        CHECK(false);
1770 1771 1772
      }
    }
  }
1773
  DCHECK_SEMISPACE_ALLOCATION_INFO(allocation_info_, to_space_);
1774 1775
}

1776 1777 1778 1779 1780 1781 1782 1783 1784
bool NewSpace::Rebalance() {
  CHECK(heap()->promotion_queue()->is_empty());
  // Order here is important to make use of the page pool.
  return to_space_.EnsureCurrentCapacity() &&
         from_space_.EnsureCurrentCapacity();
}

bool SemiSpace::EnsureCurrentCapacity() {
  if (is_committed()) {
1785 1786
    const int expected_pages =
        static_cast<int>(current_capacity_ / Page::kPageSize);
1787 1788 1789 1790 1791 1792 1793
    int actual_pages = 0;
    Page* current_page = anchor()->next_page();
    while (current_page != anchor()) {
      actual_pages++;
      current_page = current_page->next_page();
      if (actual_pages > expected_pages) {
        Page* to_remove = current_page->prev_page();
1794 1795
        // Make sure we don't overtake the actual top pointer.
        CHECK_NE(to_remove, current_page_);
1796
        to_remove->Unlink();
1797 1798 1799
        // Clear new space flags to avoid this page being treated as a new
        // space page that is potentially being swept.
        to_remove->SetFlags(0, Page::kIsInNewSpaceMask);
1800 1801 1802 1803 1804 1805 1806 1807 1808 1809 1810 1811
        heap()->memory_allocator()->Free<MemoryAllocator::kPooledAndQueue>(
            to_remove);
      }
    }
    while (actual_pages < expected_pages) {
      actual_pages++;
      current_page =
          heap()->memory_allocator()->AllocatePage<MemoryAllocator::kPooled>(
              Page::kAllocatableMemory, this, executable());
      if (current_page == nullptr) return false;
      DCHECK_NOT_NULL(current_page);
      current_page->InsertAfter(anchor());
1812
      MarkingState::Internal(current_page).ClearLiveness();
1813
      current_page->SetFlags(anchor()->prev_page()->GetFlags(),
1814
                             static_cast<uintptr_t>(Page::kCopyAllFlags));
1815
      heap()->CreateFillerObjectAt(current_page->area_start(),
1816
                                   static_cast<int>(current_page->area_size()),
1817 1818 1819 1820 1821
                                   ClearRecordedSlots::kNo);
    }
  }
  return true;
}
1822

1823
AllocationInfo LocalAllocationBuffer::Close() {
1824 1825 1826
  if (IsValid()) {
    heap_->CreateFillerObjectAt(
        allocation_info_.top(),
1827 1828
        static_cast<int>(allocation_info_.limit() - allocation_info_.top()),
        ClearRecordedSlots::kNo);
1829 1830 1831
    const AllocationInfo old_info = allocation_info_;
    allocation_info_ = AllocationInfo(nullptr, nullptr);
    return old_info;
1832
  }
1833
  return AllocationInfo(nullptr, nullptr);
1834 1835 1836 1837 1838 1839 1840 1841 1842
}


LocalAllocationBuffer::LocalAllocationBuffer(Heap* heap,
                                             AllocationInfo allocation_info)
    : heap_(heap), allocation_info_(allocation_info) {
  if (IsValid()) {
    heap_->CreateFillerObjectAt(
        allocation_info_.top(),
1843 1844
        static_cast<int>(allocation_info_.limit() - allocation_info_.top()),
        ClearRecordedSlots::kNo);
1845 1846 1847 1848 1849 1850 1851 1852 1853 1854 1855 1856 1857 1858 1859 1860 1861 1862 1863 1864 1865 1866 1867 1868 1869
  }
}


LocalAllocationBuffer::LocalAllocationBuffer(
    const LocalAllocationBuffer& other) {
  *this = other;
}


LocalAllocationBuffer& LocalAllocationBuffer::operator=(
    const LocalAllocationBuffer& other) {
  Close();
  heap_ = other.heap_;
  allocation_info_ = other.allocation_info_;

  // This is needed since we (a) cannot yet use move-semantics, and (b) want
  // to make the use of the class easy by it as value and (c) implicitly call
  // {Close} upon copy.
  const_cast<LocalAllocationBuffer&>(other)
      .allocation_info_.Reset(nullptr, nullptr);
  return *this;
}


1870
void NewSpace::UpdateAllocationInfo() {
1871
  MemoryChunk::UpdateHighWaterMark(allocation_info_.top());
1872
  allocation_info_.Reset(to_space_.page_low(), to_space_.page_high());
1873 1874
  original_top_.SetValue(top());
  original_limit_.SetValue(limit());
1875
  UpdateInlineAllocationLimit(0);
1876
  DCHECK_SEMISPACE_ALLOCATION_INFO(allocation_info_, to_space_);
1877 1878 1879
}


1880
void NewSpace::ResetAllocationInfo() {
1881
  Address old_top = allocation_info_.top();
1882 1883 1884
  to_space_.Reset();
  UpdateAllocationInfo();
  // Clear all mark-bits in the to-space.
1885
  for (Page* p : to_space_) {
1886
    MarkingState::Internal(p).ClearLiveness();
1887
  }
1888
  InlineAllocationStep(old_top, allocation_info_.top(), nullptr, 0);
1889 1890 1891
}


1892 1893 1894 1895 1896 1897
void NewSpace::UpdateInlineAllocationLimit(int size_in_bytes) {
  if (heap()->inline_allocation_disabled()) {
    // Lowest limit when linear allocation was disabled.
    Address high = to_space_.page_high();
    Address new_top = allocation_info_.top() + size_in_bytes;
    allocation_info_.set_limit(Min(new_top, high));
1898
  } else if (allocation_observers_paused_ || top_on_previous_step_ == 0) {
1899 1900 1901 1902 1903 1904
    // Normal limit is the end of the current page.
    allocation_info_.set_limit(to_space_.page_high());
  } else {
    // Lower limit during incremental marking.
    Address high = to_space_.page_high();
    Address new_top = allocation_info_.top() + size_in_bytes;
1905
    Address new_limit = new_top + GetNextInlineAllocationStepSize() - 1;
1906 1907
    allocation_info_.set_limit(Min(new_limit, high));
  }
1908
  DCHECK_SEMISPACE_ALLOCATION_INFO(allocation_info_, to_space_);
1909 1910 1911
}


1912
bool NewSpace::AddFreshPage() {
1913
  Address top = allocation_info_.top();
1914
  DCHECK(!Page::IsAtObjectStart(top));
1915
  if (!to_space_.AdvancePage()) {
mlippautz's avatar
mlippautz committed
1916 1917
    // No more pages left to advance.
    return false;
1918
  }
1919

1920
  // Clear remainder of current page.
1921
  Address limit = Page::FromAllocationAreaAddress(top)->area_end();
1922 1923 1924 1925 1926
  if (heap()->gc_state() == Heap::SCAVENGE) {
    heap()->promotion_queue()->SetNewLimit(limit);
  }

  int remaining_in_page = static_cast<int>(limit - top);
1927
  heap()->CreateFillerObjectAt(top, remaining_in_page, ClearRecordedSlots::kNo);
1928
  UpdateAllocationInfo();
1929

1930
  return true;
1931 1932 1933
}


1934 1935 1936 1937 1938 1939
bool NewSpace::AddFreshPageSynchronized() {
  base::LockGuard<base::Mutex> guard(&mutex_);
  return AddFreshPage();
}


1940 1941
bool NewSpace::EnsureAllocation(int size_in_bytes,
                                AllocationAlignment alignment) {
1942
  Address old_top = allocation_info_.top();
1943
  Address high = to_space_.page_high();
1944 1945
  int filler_size = Heap::GetFillToAlign(old_top, alignment);
  int aligned_size_in_bytes = size_in_bytes + filler_size;
1946

1947
  if (old_top + aligned_size_in_bytes > high) {
1948 1949 1950 1951 1952
    // Not enough room in the page, try to allocate a new one.
    if (!AddFreshPage()) {
      return false;
    }

1953
    InlineAllocationStep(old_top, allocation_info_.top(), nullptr, 0);
1954

1955
    old_top = allocation_info_.top();
1956 1957 1958 1959
    high = to_space_.page_high();
    filler_size = Heap::GetFillToAlign(old_top, alignment);
  }

1960
  DCHECK(old_top + aligned_size_in_bytes <= high);
1961 1962

  if (allocation_info_.limit() < high) {
1963
    // Either the limit has been lowered because linear allocation was disabled
ulan's avatar
ulan committed
1964 1965 1966
    // or because incremental marking wants to get a chance to do a step,
    // or because idle scavenge job wants to get a chance to post a task.
    // Set the new limit accordingly.
1967
    Address new_top = old_top + aligned_size_in_bytes;
1968 1969
    Address soon_object = old_top + filler_size;
    InlineAllocationStep(new_top, new_top, soon_object, size_in_bytes);
1970
    UpdateInlineAllocationLimit(aligned_size_in_bytes);
1971
  }
1972
  return true;
1973 1974 1975
}


1976
void NewSpace::StartNextInlineAllocationStep() {
1977
  if (!allocation_observers_paused_) {
1978
    top_on_previous_step_ =
1979
        allocation_observers_->length() ? allocation_info_.top() : 0;
1980 1981
    UpdateInlineAllocationLimit(0);
  }
1982 1983 1984 1985 1986
}


intptr_t NewSpace::GetNextInlineAllocationStepSize() {
  intptr_t next_step = 0;
1987 1988
  for (int i = 0; i < allocation_observers_->length(); ++i) {
    AllocationObserver* o = (*allocation_observers_)[i];
1989 1990
    next_step = next_step ? Min(next_step, o->bytes_to_next_step())
                          : o->bytes_to_next_step();
1991
  }
1992
  DCHECK(allocation_observers_->length() == 0 || next_step != 0);
1993
  return next_step;
1994 1995
}

1996 1997
void NewSpace::AddAllocationObserver(AllocationObserver* observer) {
  Space::AddAllocationObserver(observer);
1998
  StartNextInlineAllocationStep();
1999 2000
}

2001 2002
void NewSpace::RemoveAllocationObserver(AllocationObserver* observer) {
  Space::RemoveAllocationObserver(observer);
2003
  StartNextInlineAllocationStep();
2004 2005
}

2006
void NewSpace::PauseAllocationObservers() {
2007
  // Do a step to account for memory allocated so far.
2008
  InlineAllocationStep(top(), top(), nullptr, 0);
2009
  Space::PauseAllocationObservers();
2010 2011 2012 2013
  top_on_previous_step_ = 0;
  UpdateInlineAllocationLimit(0);
}

2014
void NewSpace::ResumeAllocationObservers() {
2015
  DCHECK(top_on_previous_step_ == 0);
2016
  Space::ResumeAllocationObservers();
2017 2018 2019 2020
  StartNextInlineAllocationStep();
}


2021 2022
void NewSpace::InlineAllocationStep(Address top, Address new_top,
                                    Address soon_object, size_t size) {
2023 2024
  if (top_on_previous_step_) {
    int bytes_allocated = static_cast<int>(top - top_on_previous_step_);
2025 2026 2027
    for (int i = 0; i < allocation_observers_->length(); ++i) {
      (*allocation_observers_)[i]->AllocationStep(bytes_allocated, soon_object,
                                                  size);
2028
    }
2029 2030 2031 2032
    top_on_previous_step_ = new_top;
  }
}

2033 2034 2035 2036
std::unique_ptr<ObjectIterator> NewSpace::GetObjectIterator() {
  return std::unique_ptr<ObjectIterator>(new SemiSpaceIterator(this));
}

2037
#ifdef VERIFY_HEAP
2038
// We do not use the SemiSpaceIterator because verification doesn't assume
2039 2040 2041
// that it works (it depends on the invariants we are checking).
void NewSpace::Verify() {
  // The allocation pointer should be in the space or at the very end.
2042
  DCHECK_SEMISPACE_ALLOCATION_INFO(allocation_info_, to_space_);
2043 2044 2045

  // There should be objects packed in from the low address up to the
  // allocation pointer.
2046
  Address current = to_space_.first_page()->area_start();
2047
  CHECK_EQ(current, to_space_.space_start());
2048

2049
  while (current != top()) {
2050
    if (!Page::IsAlignedToPageSize(current)) {
2051
      // The allocation pointer should not be in the middle of an object.
2052
      CHECK(!Page::FromAllocationAreaAddress(current)->ContainsLimit(top()) ||
2053
            current < top());
2054

2055
      HeapObject* object = HeapObject::FromAddress(current);
2056

2057 2058 2059 2060 2061
      // The first word should be a map, and we expect all map pointers to
      // be in map space.
      Map* map = object->map();
      CHECK(map->IsMap());
      CHECK(heap()->map_space()->Contains(map));
2062

2063 2064
      // The object should not be code or a map.
      CHECK(!object->IsMap());
2065
      CHECK(!object->IsAbstractCode());
2066

2067
      // The object itself should look OK.
2068
      object->ObjectVerify();
2069

2070 2071 2072 2073
      // All the interior pointers should be contained in the heap.
      VerifyPointersVisitor visitor;
      int size = object->Size();
      object->IterateBody(map->instance_type(), size, &visitor);
2074

2075 2076 2077
      current += size;
    } else {
      // At end of page, switch to next page.
2078
      Page* page = Page::FromAllocationAreaAddress(current)->next_page();
2079 2080
      // Next page should be valid.
      CHECK(!page->is_anchor());
2081
      current = page->area_start();
2082
    }
2083 2084
  }

2085
  // Check semi-spaces.
2086 2087
  CHECK_EQ(from_space_.id(), kFromSpace);
  CHECK_EQ(to_space_.id(), kToSpace);
2088 2089
  from_space_.Verify();
  to_space_.Verify();
2090
}
2091
#endif
2092

2093 2094 2095
// -----------------------------------------------------------------------------
// SemiSpace implementation

2096 2097
void SemiSpace::SetUp(size_t initial_capacity, size_t maximum_capacity) {
  DCHECK_GE(maximum_capacity, static_cast<size_t>(Page::kPageSize));
mlippautz's avatar
mlippautz committed
2098 2099 2100
  minimum_capacity_ = RoundDown(initial_capacity, Page::kPageSize);
  current_capacity_ = minimum_capacity_;
  maximum_capacity_ = RoundDown(maximum_capacity, Page::kPageSize);
2101
  committed_ = false;
2102 2103 2104 2105
}


void SemiSpace::TearDown() {
2106
  // Properly uncommit memory to keep the allocator counters in sync.
2107
  if (is_committed()) {
2108
    for (Page* p : *this) {
2109
      ArrayBufferTracker::FreeAll(p);
2110 2111 2112
    }
    Uncommit();
  }
2113
  current_capacity_ = maximum_capacity_ = 0;
2114 2115 2116
}


2117
bool SemiSpace::Commit() {
2118
  DCHECK(!is_committed());
2119
  Page* current = anchor();
2120
  const int num_pages = static_cast<int>(current_capacity_ / Page::kPageSize);
2121
  for (int pages_added = 0; pages_added < num_pages; pages_added++) {
2122 2123 2124
    Page* new_page =
        heap()->memory_allocator()->AllocatePage<MemoryAllocator::kPooled>(
            Page::kAllocatableMemory, this, executable());
2125 2126 2127 2128
    if (new_page == nullptr) {
      RewindPages(current, pages_added);
      return false;
    }
2129 2130
    new_page->InsertAfter(current);
    current = new_page;
2131
  }
mlippautz's avatar
mlippautz committed
2132
  Reset();
2133
  AccountCommitted(current_capacity_);
2134 2135 2136
  if (age_mark_ == nullptr) {
    age_mark_ = first_page()->area_start();
  }
2137
  committed_ = true;
2138 2139 2140 2141
  return true;
}


2142
bool SemiSpace::Uncommit() {
2143
  DCHECK(is_committed());
2144 2145 2146
  for (auto it = begin(); it != end();) {
    Page* p = *(it++);
    heap()->memory_allocator()->Free<MemoryAllocator::kPooledAndQueue>(p);
2147 2148 2149
  }
  anchor()->set_next_page(anchor());
  anchor()->set_prev_page(anchor());
2150
  AccountUncommitted(current_capacity_);
2151
  committed_ = false;
2152
  heap()->memory_allocator()->unmapper()->FreeQueuedChunks();
2153 2154 2155 2156
  return true;
}


2157 2158 2159
size_t SemiSpace::CommittedPhysicalMemory() {
  if (!is_committed()) return 0;
  size_t size = 0;
2160 2161
  for (Page* p : *this) {
    size += p->CommittedPhysicalMemory();
2162 2163 2164 2165
  }
  return size;
}

2166
bool SemiSpace::GrowTo(size_t new_capacity) {
2167 2168 2169
  if (!is_committed()) {
    if (!Commit()) return false;
  }
2170
  DCHECK_EQ(new_capacity & Page::kPageAlignmentMask, 0u);
mlippautz's avatar
mlippautz committed
2171 2172
  DCHECK_LE(new_capacity, maximum_capacity_);
  DCHECK_GT(new_capacity, current_capacity_);
2173
  const size_t delta = new_capacity - current_capacity_;
2174
  DCHECK(IsAligned(delta, base::OS::AllocateAlignment()));
2175
  const int delta_pages = static_cast<int>(delta / Page::kPageSize);
2176
  Page* last_page = anchor()->prev_page();
mlippautz's avatar
mlippautz committed
2177
  DCHECK_NE(last_page, anchor());
2178
  for (int pages_added = 0; pages_added < delta_pages; pages_added++) {
2179 2180 2181
    Page* new_page =
        heap()->memory_allocator()->AllocatePage<MemoryAllocator::kPooled>(
            Page::kAllocatableMemory, this, executable());
2182 2183 2184 2185
    if (new_page == nullptr) {
      RewindPages(last_page, pages_added);
      return false;
    }
2186
    new_page->InsertAfter(last_page);
2187
    MarkingState::Internal(new_page).ClearLiveness();
2188
    // Duplicate the flags that was set on the old page.
2189
    new_page->SetFlags(last_page->GetFlags(), Page::kCopyOnFlipFlagsMask);
2190 2191
    last_page = new_page;
  }
2192
  AccountCommitted(delta);
2193
  current_capacity_ = new_capacity;
2194 2195 2196
  return true;
}

2197 2198 2199
void SemiSpace::RewindPages(Page* start, int num_pages) {
  Page* new_last_page = nullptr;
  Page* last_page = start;
2200 2201 2202 2203 2204 2205 2206 2207 2208
  while (num_pages > 0) {
    DCHECK_NE(last_page, anchor());
    new_last_page = last_page->prev_page();
    last_page->prev_page()->set_next_page(last_page->next_page());
    last_page->next_page()->set_prev_page(last_page->prev_page());
    last_page = new_last_page;
    num_pages--;
  }
}
2209

2210 2211
bool SemiSpace::ShrinkTo(size_t new_capacity) {
  DCHECK_EQ(new_capacity & Page::kPageAlignmentMask, 0u);
mlippautz's avatar
mlippautz committed
2212 2213
  DCHECK_GE(new_capacity, minimum_capacity_);
  DCHECK_LT(new_capacity, current_capacity_);
2214
  if (is_committed()) {
2215
    const size_t delta = current_capacity_ - new_capacity;
2216
    DCHECK(IsAligned(delta, base::OS::AllocateAlignment()));
2217
    int delta_pages = static_cast<int>(delta / Page::kPageSize);
2218 2219
    Page* new_last_page;
    Page* last_page;
2220 2221 2222 2223 2224
    while (delta_pages > 0) {
      last_page = anchor()->prev_page();
      new_last_page = last_page->prev_page();
      new_last_page->set_next_page(anchor());
      anchor()->set_prev_page(new_last_page);
2225 2226
      heap()->memory_allocator()->Free<MemoryAllocator::kPooledAndQueue>(
          last_page);
2227
      delta_pages--;
2228
    }
2229
    AccountUncommitted(delta);
2230
    heap()->memory_allocator()->unmapper()->FreeQueuedChunks();
2231
  }
2232
  current_capacity_ = new_capacity;
2233 2234 2235
  return true;
}

2236
void SemiSpace::FixPagesFlags(intptr_t flags, intptr_t mask) {
2237 2238 2239 2240
  anchor_.set_owner(this);
  anchor_.prev_page()->set_next_page(&anchor_);
  anchor_.next_page()->set_prev_page(&anchor_);

2241
  for (Page* page : *this) {
2242 2243
    page->set_owner(this);
    page->SetFlags(flags, mask);
2244
    if (id_ == kToSpace) {
2245 2246
      page->ClearFlag(MemoryChunk::IN_FROM_SPACE);
      page->SetFlag(MemoryChunk::IN_TO_SPACE);
2247
      page->ClearFlag(MemoryChunk::NEW_SPACE_BELOW_AGE_MARK);
2248
      MarkingState::Internal(page).SetLiveBytes(0);
2249 2250 2251 2252
    } else {
      page->SetFlag(MemoryChunk::IN_FROM_SPACE);
      page->ClearFlag(MemoryChunk::IN_TO_SPACE);
    }
2253
    DCHECK(page->IsFlagSet(MemoryChunk::IN_TO_SPACE) ||
2254 2255 2256 2257 2258 2259
           page->IsFlagSet(MemoryChunk::IN_FROM_SPACE));
  }
}


void SemiSpace::Reset() {
mlippautz's avatar
mlippautz committed
2260
  DCHECK_NE(anchor_.next_page(), &anchor_);
2261
  current_page_ = anchor_.next_page();
2262
  pages_used_ = 0;
2263 2264
}

2265 2266 2267 2268 2269 2270 2271 2272
void SemiSpace::RemovePage(Page* page) {
  if (current_page_ == page) {
    current_page_ = page->prev_page();
  }
  page->Unlink();
}

void SemiSpace::PrependPage(Page* page) {
2273 2274
  page->SetFlags(current_page()->GetFlags(),
                 static_cast<uintptr_t>(Page::kCopyAllFlags));
2275 2276 2277
  page->set_owner(this);
  page->InsertAfter(anchor());
  pages_used_++;
2278
}
2279 2280 2281

void SemiSpace::Swap(SemiSpace* from, SemiSpace* to) {
  // We won't be swapping semispaces without data in them.
mlippautz's avatar
mlippautz committed
2282 2283
  DCHECK_NE(from->anchor_.next_page(), &from->anchor_);
  DCHECK_NE(to->anchor_.next_page(), &to->anchor_);
2284

2285
  intptr_t saved_to_space_flags = to->current_page()->GetFlags();
2286

2287 2288 2289 2290
  // We swap all properties but id_.
  std::swap(from->current_capacity_, to->current_capacity_);
  std::swap(from->maximum_capacity_, to->maximum_capacity_);
  std::swap(from->minimum_capacity_, to->minimum_capacity_);
2291
  std::swap(from->age_mark_, to->age_mark_);
2292 2293 2294
  std::swap(from->committed_, to->committed_);
  std::swap(from->anchor_, to->anchor_);
  std::swap(from->current_page_, to->current_page_);
2295

2296
  to->FixPagesFlags(saved_to_space_flags, Page::kCopyOnFlipFlagsMask);
2297
  from->FixPagesFlags(0, 0);
2298 2299
}

2300 2301 2302 2303
void SemiSpace::set_age_mark(Address mark) {
  DCHECK_EQ(Page::FromAllocationAreaAddress(mark)->owner(), this);
  age_mark_ = mark;
  // Mark all pages up to the one containing mark.
2304
  for (Page* p : PageRange(space_start(), mark)) {
2305
    p->SetFlag(MemoryChunk::NEW_SPACE_BELOW_AGE_MARK);
mlippautz's avatar
mlippautz committed
2306 2307
  }
}
2308

2309 2310 2311 2312 2313
std::unique_ptr<ObjectIterator> SemiSpace::GetObjectIterator() {
  // Use the NewSpace::NewObjectIterator to iterate the ToSpace.
  UNREACHABLE();
}

2314
#ifdef DEBUG
2315
void SemiSpace::Print() {}
2316
#endif
2317

2318
#ifdef VERIFY_HEAP
2319 2320
void SemiSpace::Verify() {
  bool is_from_space = (id_ == kFromSpace);
2321 2322
  Page* page = anchor_.next_page();
  CHECK(anchor_.owner() == this);
2323
  while (page != &anchor_) {
2324
    CHECK_EQ(page->owner(), this);
2325 2326 2327 2328 2329 2330 2331 2332 2333 2334 2335 2336
    CHECK(page->InNewSpace());
    CHECK(page->IsFlagSet(is_from_space ? MemoryChunk::IN_FROM_SPACE
                                        : MemoryChunk::IN_TO_SPACE));
    CHECK(!page->IsFlagSet(is_from_space ? MemoryChunk::IN_TO_SPACE
                                         : MemoryChunk::IN_FROM_SPACE));
    CHECK(page->IsFlagSet(MemoryChunk::POINTERS_TO_HERE_ARE_INTERESTING));
    if (!is_from_space) {
      // The pointers-from-here-are-interesting flag isn't updated dynamically
      // on from-space pages, so it might be out of sync with the marking state.
      if (page->heap()->incremental_marking()->IsMarking()) {
        CHECK(page->IsFlagSet(MemoryChunk::POINTERS_FROM_HERE_ARE_INTERESTING));
      } else {
2337 2338
        CHECK(
            !page->IsFlagSet(MemoryChunk::POINTERS_FROM_HERE_ARE_INTERESTING));
2339 2340 2341 2342
      }
      // TODO(gc): Check that the live_bytes_count_ field matches the
      // black marking on the page (if we make it match in new-space).
    }
mlippautz's avatar
mlippautz committed
2343
    CHECK_EQ(page->prev_page()->next_page(), page);
2344 2345 2346
    page = page->next_page();
  }
}
2347
#endif
2348

2349
#ifdef DEBUG
2350 2351
void SemiSpace::AssertValidRange(Address start, Address end) {
  // Addresses belong to same semi-space
2352 2353 2354 2355
  Page* page = Page::FromAllocationAreaAddress(start);
  Page* end_page = Page::FromAllocationAreaAddress(end);
  SemiSpace* space = reinterpret_cast<SemiSpace*>(page->owner());
  CHECK_EQ(space, end_page->owner());
2356 2357 2358 2359
  // Start address is before end address, either on same page,
  // or end address is on a later page in the linked list of
  // semi-space pages.
  if (page == end_page) {
mlippautz's avatar
mlippautz committed
2360
    CHECK_LE(start, end);
2361 2362 2363 2364 2365 2366 2367
  } else {
    while (page != end_page) {
      page = page->next_page();
      CHECK_NE(page, space->anchor());
    }
  }
}
2368 2369 2370 2371 2372
#endif


// -----------------------------------------------------------------------------
// SemiSpaceIterator implementation.
2373

2374
SemiSpaceIterator::SemiSpaceIterator(NewSpace* space) {
2375
  Initialize(space->bottom(), space->top());
2376 2377 2378
}


2379
void SemiSpaceIterator::Initialize(Address start, Address end) {
2380
  SemiSpace::AssertValidRange(start, end);
2381 2382 2383 2384 2385 2386
  current_ = start;
  limit_ = end;
}

#ifdef DEBUG
// heap_histograms is shared, always clear it before using it.
2387
static void ClearHistograms(Isolate* isolate) {
2388
// We reset the name each time, though it hasn't changed.
2389
#define DEF_TYPE_NAME(name) isolate->heap_histograms()[name].set_name(#name);
2390 2391 2392
  INSTANCE_TYPE_LIST(DEF_TYPE_NAME)
#undef DEF_TYPE_NAME

2393
#define CLEAR_HISTOGRAM(name) isolate->heap_histograms()[name].clear();
2394 2395 2396
  INSTANCE_TYPE_LIST(CLEAR_HISTOGRAM)
#undef CLEAR_HISTOGRAM

2397
  isolate->js_spill_information()->Clear();
2398 2399 2400
}

static int CollectHistogramInfo(HeapObject* obj) {
2401
  Isolate* isolate = obj->GetIsolate();
2402
  InstanceType type = obj->map()->instance_type();
2403 2404
  DCHECK(0 <= type && type <= LAST_TYPE);
  DCHECK(isolate->heap_histograms()[type].name() != NULL);
2405 2406
  isolate->heap_histograms()[type].increment_number(1);
  isolate->heap_histograms()[type].increment_bytes(obj->Size());
2407 2408

  if (FLAG_collect_heap_spill_statistics && obj->IsJSObject()) {
2409 2410
    JSObject::cast(obj)
        ->IncrementSpillStatistics(isolate->js_spill_information());
2411 2412 2413 2414 2415 2416
  }

  return obj->Size();
}


2417
static void ReportHistogram(Isolate* isolate, bool print_spill) {
2418 2419
  PrintF("\n  Object Histogram:\n");
  for (int i = 0; i <= LAST_TYPE; i++) {
2420
    if (isolate->heap_histograms()[i].number() > 0) {
2421
      PrintF("    %-34s%10d (%10d bytes)\n",
2422 2423 2424
             isolate->heap_histograms()[i].name(),
             isolate->heap_histograms()[i].number(),
             isolate->heap_histograms()[i].bytes());
2425 2426 2427 2428 2429 2430 2431
    }
  }
  PrintF("\n");

  // Summarize string types.
  int string_number = 0;
  int string_bytes = 0;
2432 2433 2434
#define INCREMENT(type, size, name, camel_name)               \
  string_number += isolate->heap_histograms()[type].number(); \
  string_bytes += isolate->heap_histograms()[type].bytes();
2435 2436 2437
  STRING_TYPE_LIST(INCREMENT)
#undef INCREMENT
  if (string_number > 0) {
2438
    PrintF("    %-34s%10d (%10d bytes)\n\n", "STRING_TYPE", string_number,
2439 2440 2441 2442
           string_bytes);
  }

  if (FLAG_collect_heap_spill_statistics && print_spill) {
2443
    isolate->js_spill_information()->Print();
2444 2445 2446 2447 2448 2449 2450 2451 2452 2453 2454 2455 2456
  }
}
#endif  // DEBUG


// Support for statistics gathering for --heap-stats and --log-gc.
void NewSpace::ClearHistograms() {
  for (int i = 0; i <= LAST_TYPE; i++) {
    allocated_histogram_[i].clear();
    promoted_histogram_[i].clear();
  }
}

2457

2458 2459
// Because the copying collector does not touch garbage objects, we iterate
// the new space before a collection to get a histogram of allocated objects.
2460
// This only happens when --log-gc flag is set.
2461 2462 2463
void NewSpace::CollectStatistics() {
  ClearHistograms();
  SemiSpaceIterator it(this);
2464
  for (HeapObject* obj = it.Next(); obj != NULL; obj = it.Next())
2465
    RecordAllocation(obj);
2466 2467 2468
}


2469 2470
static void DoReportStatistics(Isolate* isolate, HistogramInfo* info,
                               const char* description) {
2471
  LOG(isolate, HeapSampleBeginEvent("NewSpace", description));
2472 2473 2474
  // Lump all the string types together.
  int string_number = 0;
  int string_bytes = 0;
2475 2476 2477
#define INCREMENT(type, size, name, camel_name) \
  string_number += info[type].number();         \
  string_bytes += info[type].bytes();
2478 2479 2480
  STRING_TYPE_LIST(INCREMENT)
#undef INCREMENT
  if (string_number > 0) {
2481 2482
    LOG(isolate,
        HeapSampleItemEvent("STRING_TYPE", string_number, string_bytes));
2483 2484 2485 2486 2487
  }

  // Then do the other types.
  for (int i = FIRST_NONSTRING_TYPE; i <= LAST_TYPE; ++i) {
    if (info[i].number() > 0) {
2488 2489
      LOG(isolate, HeapSampleItemEvent(info[i].name(), info[i].number(),
                                       info[i].bytes()));
2490 2491
    }
  }
2492
  LOG(isolate, HeapSampleEndEvent("NewSpace", description));
2493 2494 2495 2496 2497 2498
}


void NewSpace::ReportStatistics() {
#ifdef DEBUG
  if (FLAG_heap_stats) {
2499
    float pct = static_cast<float>(Available()) / TotalCapacity();
2500
    PrintF("  capacity: %" PRIuS ", available: %" PRIuS ", %%%d\n",
2501
           TotalCapacity(), Available(), static_cast<int>(pct * 100));
2502 2503 2504
    PrintF("\n  Object Histogram:\n");
    for (int i = 0; i <= LAST_TYPE; i++) {
      if (allocated_histogram_[i].number() > 0) {
2505
        PrintF("    %-34s%10d (%10d bytes)\n", allocated_histogram_[i].name(),
2506 2507 2508 2509 2510 2511 2512 2513 2514
               allocated_histogram_[i].number(),
               allocated_histogram_[i].bytes());
      }
    }
    PrintF("\n");
  }
#endif  // DEBUG

  if (FLAG_log_gc) {
dcarney@chromium.org's avatar
dcarney@chromium.org committed
2515
    Isolate* isolate = heap()->isolate();
2516 2517
    DoReportStatistics(isolate, allocated_histogram_, "allocated");
    DoReportStatistics(isolate, promoted_histogram_, "promoted");
2518 2519 2520 2521 2522 2523
  }
}


void NewSpace::RecordAllocation(HeapObject* obj) {
  InstanceType type = obj->map()->instance_type();
2524
  DCHECK(0 <= type && type <= LAST_TYPE);
2525 2526 2527 2528 2529 2530 2531
  allocated_histogram_[type].increment_number(1);
  allocated_histogram_[type].increment_bytes(obj->Size());
}


void NewSpace::RecordPromotion(HeapObject* obj) {
  InstanceType type = obj->map()->instance_type();
2532
  DCHECK(0 <= type && type <= LAST_TYPE);
2533 2534 2535 2536
  promoted_histogram_[type].increment_number(1);
  promoted_histogram_[type].increment_bytes(obj->Size());
}

2537 2538

size_t NewSpace::CommittedPhysicalMemory() {
2539
  if (!base::VirtualMemory::HasLazyCommits()) return CommittedMemory();
2540
  MemoryChunk::UpdateHighWaterMark(allocation_info_.top());
2541 2542 2543 2544 2545 2546 2547
  size_t size = to_space_.CommittedPhysicalMemory();
  if (from_space_.is_committed()) {
    size += from_space_.CommittedPhysicalMemory();
  }
  return size;
}

2548

2549 2550 2551
// -----------------------------------------------------------------------------
// Free lists for old object spaces implementation

2552

2553
void FreeListCategory::Reset() {
2554
  set_top(nullptr);
2555 2556
  set_prev(nullptr);
  set_next(nullptr);
2557
  available_ = 0;
2558 2559
}

2560
FreeSpace* FreeListCategory::PickNodeFromList(size_t* node_size) {
2561 2562
  DCHECK(page()->CanAllocate());

2563
  FreeSpace* node = top();
2564
  if (node == nullptr) return nullptr;
2565 2566 2567
  set_top(node->next());
  *node_size = node->Size();
  available_ -= *node_size;
2568 2569 2570
  return node;
}

2571 2572
FreeSpace* FreeListCategory::TryPickNodeFromList(size_t minimum_size,
                                                 size_t* node_size) {
2573
  DCHECK(page()->CanAllocate());
2574

2575
  FreeSpace* node = PickNodeFromList(node_size);
2576 2577
  if ((node != nullptr) && (*node_size < minimum_size)) {
    Free(node, *node_size, kLinkCategory);
2578
    *node_size = 0;
2579
    return nullptr;
2580 2581 2582 2583
  }
  return node;
}

2584 2585
FreeSpace* FreeListCategory::SearchForNodeInList(size_t minimum_size,
                                                 size_t* node_size) {
2586 2587
  DCHECK(page()->CanAllocate());

2588 2589 2590
  FreeSpace* prev_non_evac_node = nullptr;
  for (FreeSpace* cur_node = top(); cur_node != nullptr;
       cur_node = cur_node->next()) {
2591
    size_t size = cur_node->size();
2592
    if (size >= minimum_size) {
2593
      DCHECK_GE(available_, size);
2594
      available_ -= size;
2595 2596 2597 2598 2599 2600
      if (cur_node == top()) {
        set_top(cur_node->next());
      }
      if (prev_non_evac_node != nullptr) {
        prev_non_evac_node->set_next(cur_node->next());
      }
2601
      *node_size = size;
2602
      return cur_node;
2603 2604
    }

2605
    prev_non_evac_node = cur_node;
2606
  }
2607
  return nullptr;
2608 2609
}

2610
bool FreeListCategory::Free(FreeSpace* free_space, size_t size_in_bytes,
2611 2612
                            FreeMode mode) {
  if (!page()->CanAllocate()) return false;
2613

2614 2615
  free_space->set_next(top());
  set_top(free_space);
2616
  available_ += size_in_bytes;
2617 2618 2619 2620
  if ((mode == kLinkCategory) && (prev() == nullptr) && (next() == nullptr)) {
    owner()->AddCategory(this);
  }
  return true;
2621 2622 2623 2624
}


void FreeListCategory::RepairFreeList(Heap* heap) {
2625
  FreeSpace* n = top();
2626 2627 2628 2629 2630
  while (n != NULL) {
    Map** map_location = reinterpret_cast<Map**>(n->address());
    if (*map_location == NULL) {
      *map_location = heap->free_space_map();
    } else {
2631
      DCHECK(*map_location == heap->free_space_map());
2632 2633 2634 2635 2636
    }
    n = n->next();
  }
}

2637 2638 2639
void FreeListCategory::Relink() {
  DCHECK(!is_linked());
  owner()->AddCategory(this);
2640 2641
}

2642
void FreeListCategory::Invalidate() {
2643
  page()->remove_available_in_free_list(available());
2644 2645 2646
  Reset();
  type_ = kInvalidCategory;
}
2647

2648
FreeList::FreeList(PagedSpace* owner) : owner_(owner), wasted_bytes_(0) {
2649
  for (int i = kFirstCategory; i < kNumberOfCategories; i++) {
2650
    categories_[i] = nullptr;
2651
  }
2652
  Reset();
2653 2654 2655
}


2656
void FreeList::Reset() {
2657 2658
  ForAllFreeListCategories(
      [](FreeListCategory* category) { category->Reset(); });
2659
  for (int i = kFirstCategory; i < kNumberOfCategories; i++) {
2660
    categories_[i] = nullptr;
2661
  }
2662
  ResetStats();
2663 2664
}

2665
size_t FreeList::Free(Address start, size_t size_in_bytes, FreeMode mode) {
2666
  if (size_in_bytes == 0) return 0;
2667

2668
  owner()->heap()->CreateFillerObjectAt(start, static_cast<int>(size_in_bytes),
2669
                                        ClearRecordedSlots::kNo);
2670

2671
  Page* page = Page::FromAddress(start);
2672

2673 2674
  // Blocks have to be a minimum size to hold free list items.
  if (size_in_bytes < kMinBlockSize) {
2675
    page->add_wasted_memory(size_in_bytes);
2676
    wasted_bytes_.Increment(size_in_bytes);
2677 2678
    return size_in_bytes;
  }
2679

2680
  FreeSpace* free_space = FreeSpace::cast(HeapObject::FromAddress(start));
2681 2682
  // Insert other blocks at the head of a free list of the appropriate
  // magnitude.
2683
  FreeListCategoryType type = SelectFreeListCategoryType(size_in_bytes);
2684 2685 2686
  if (page->free_list_category(type)->Free(free_space, size_in_bytes, mode)) {
    page->add_available_in_free_list(size_in_bytes);
  }
2687
  DCHECK_EQ(page->AvailableInFreeList(), page->available_in_free_list());
2688
  return 0;
2689 2690
}

2691
FreeSpace* FreeList::FindNodeIn(FreeListCategoryType type, size_t* node_size) {
2692 2693 2694 2695 2696 2697 2698
  FreeListCategoryIterator it(this, type);
  FreeSpace* node = nullptr;
  while (it.HasNext()) {
    FreeListCategory* current = it.Next();
    node = current->PickNodeFromList(node_size);
    if (node != nullptr) {
      Page::FromAddress(node->address())
2699
          ->remove_available_in_free_list(*node_size);
2700 2701 2702 2703 2704 2705 2706
      DCHECK(IsVeryLong() || Available() == SumFreeLists());
      return node;
    }
    RemoveCategory(current);
  }
  return node;
}
2707

2708 2709
FreeSpace* FreeList::TryFindNodeIn(FreeListCategoryType type, size_t* node_size,
                                   size_t minimum_size) {
2710 2711 2712
  if (categories_[type] == nullptr) return nullptr;
  FreeSpace* node =
      categories_[type]->TryPickNodeFromList(minimum_size, node_size);
2713 2714
  if (node != nullptr) {
    Page::FromAddress(node->address())
2715
        ->remove_available_in_free_list(*node_size);
2716
    DCHECK(IsVeryLong() || Available() == SumFreeLists());
2717 2718 2719 2720
  }
  return node;
}

2721
FreeSpace* FreeList::SearchForNodeInList(FreeListCategoryType type,
2722 2723
                                         size_t* node_size,
                                         size_t minimum_size) {
2724 2725 2726 2727 2728 2729 2730
  FreeListCategoryIterator it(this, type);
  FreeSpace* node = nullptr;
  while (it.HasNext()) {
    FreeListCategory* current = it.Next();
    node = current->SearchForNodeInList(minimum_size, node_size);
    if (node != nullptr) {
      Page::FromAddress(node->address())
2731
          ->remove_available_in_free_list(*node_size);
2732 2733 2734
      DCHECK(IsVeryLong() || Available() == SumFreeLists());
      return node;
    }
2735 2736 2737
    if (current->is_empty()) {
      RemoveCategory(current);
    }
2738 2739 2740
  }
  return node;
}
2741

2742
FreeSpace* FreeList::FindNodeFor(size_t size_in_bytes, size_t* node_size) {
2743
  FreeSpace* node = nullptr;
2744

2745 2746 2747 2748 2749 2750
  // First try the allocation fast path: try to allocate the minimum element
  // size of a free list category. This operation is constant time.
  FreeListCategoryType type =
      SelectFastAllocationFreeListCategoryType(size_in_bytes);
  for (int i = type; i < kHuge; i++) {
    node = FindNodeIn(static_cast<FreeListCategoryType>(i), node_size);
2751
    if (node != nullptr) return node;
2752
  }
2753

2754 2755
  // Next search the huge list for free list nodes. This takes linear time in
  // the number of huge elements.
2756
  node = SearchForNodeInList(kHuge, node_size, size_in_bytes);
2757
  if (node != nullptr) {
2758
    DCHECK(IsVeryLong() || Available() == SumFreeLists());
2759 2760 2761
    return node;
  }

2762 2763 2764 2765 2766
  // We need a huge block of memory, but we didn't find anything in the huge
  // list.
  if (type == kHuge) return nullptr;

  // Now search the best fitting free list for a node that has at least the
2767
  // requested size.
2768
  type = SelectFreeListCategoryType(size_in_bytes);
2769
  node = TryFindNodeIn(type, node_size, size_in_bytes);
2770

2771
  DCHECK(IsVeryLong() || Available() == SumFreeLists());
2772
  return node;
2773 2774
}

2775 2776 2777 2778
// Allocation on the old space free list.  If it succeeds then a new linear
// allocation space has been set up with the top and limit of the space.  If
// the allocation fails then NULL is returned, and the caller can perform a GC
// or allocate a new page before retrying.
2779
HeapObject* FreeList::Allocate(size_t size_in_bytes) {
2780 2781
  DCHECK(size_in_bytes <= kMaxBlockSize);
  DCHECK(IsAligned(size_in_bytes, kPointerSize));
2782 2783 2784 2785 2786 2787 2788
  DCHECK_LE(owner_->top(), owner_->limit());
#ifdef DEBUG
  if (owner_->top() != owner_->limit()) {
    DCHECK_EQ(Page::FromAddress(owner_->top()),
              Page::FromAddress(owner_->limit() - 1));
  }
#endif
2789
  // Don't free list allocate if there is linear space available.
2790 2791
  DCHECK_LT(static_cast<size_t>(owner_->limit() - owner_->top()),
            size_in_bytes);
2792 2793 2794 2795

  // Mark the old linear allocation area with a free space map so it can be
  // skipped when scanning the heap.  This also puts it back in the free list
  // if it is big enough.
2796
  owner_->EmptyAllocationInfo();
2797

2798
  owner_->heap()->StartIncrementalMarkingIfAllocationLimitIsReached(
2799
      Heap::kNoGCFlags, kGCCallbackScheduleIdleGarbageCollection);
2800

2801
  size_t new_node_size = 0;
2802
  FreeSpace* new_node = FindNodeFor(size_in_bytes, &new_node_size);
2803
  if (new_node == nullptr) return nullptr;
2804

2805 2806
  DCHECK_GE(new_node_size, size_in_bytes);
  size_t bytes_left = new_node_size - size_in_bytes;
2807

2808
#ifdef DEBUG
2809
  for (size_t i = 0; i < size_in_bytes / kPointerSize; i++) {
2810 2811
    reinterpret_cast<Object**>(new_node->address())[i] =
        Smi::FromInt(kCodeZapValue);
2812 2813 2814
  }
#endif

2815 2816 2817
  // The old-space-step might have finished sweeping and restarted marking.
  // Verify that it did not turn the page of the new node into an evacuation
  // candidate.
2818
  DCHECK(!MarkCompactCollector::IsOnEvacuationCandidate(new_node));
2819

2820
  const size_t kThreshold = IncrementalMarking::kAllocatedThreshold;
2821 2822 2823

  // Memory in the linear allocation area is counted as allocated.  We may free
  // a little of this again immediately - see below.
2824
  owner_->AccountAllocatedBytes(new_node_size);
2825

2826 2827 2828 2829
  if (owner_->heap()->inline_allocation_disabled()) {
    // Keep the linear allocation area empty if requested to do so, just
    // return area back to the free list instead.
    owner_->Free(new_node->address() + size_in_bytes, bytes_left);
2830 2831
    owner_->SetAllocationInfo(new_node->address() + size_in_bytes,
                              new_node->address() + size_in_bytes);
2832
  } else if (bytes_left > kThreshold &&
2833
             owner_->heap()->incremental_marking()->IsMarkingIncomplete() &&
2834
             FLAG_incremental_marking) {
2835
    size_t linear_size = owner_->RoundSizeDownToObjectAlignment(kThreshold);
2836 2837 2838
    // We don't want to give too large linear areas to the allocator while
    // incremental marking is going on, because we won't check again whether
    // we want to do another increment until the linear area is used up.
2839
    DCHECK_GE(new_node_size, size_in_bytes + linear_size);
2840 2841
    owner_->Free(new_node->address() + size_in_bytes + linear_size,
                 new_node_size - size_in_bytes - linear_size);
2842 2843 2844
    owner_->SetAllocationInfo(
        new_node->address() + size_in_bytes,
        new_node->address() + size_in_bytes + linear_size);
2845
  } else {
2846 2847
    // Normally we give the rest of the node to the allocator as its new
    // linear allocation area.
2848 2849
    owner_->SetAllocationInfo(new_node->address() + size_in_bytes,
                              new_node->address() + new_node_size);
2850
  }
2851 2852

  return new_node;
2853 2854
}

2855 2856
size_t FreeList::EvictFreeListItems(Page* page) {
  size_t sum = 0;
2857
  page->ForAllFreeListCategories(
krasin's avatar
krasin committed
2858
      [this, &sum](FreeListCategory* category) {
2859 2860 2861 2862 2863
        DCHECK_EQ(this, category->owner());
        sum += category->available();
        RemoveCategory(category);
        category->Invalidate();
      });
2864 2865 2866
  return sum;
}

2867 2868 2869 2870 2871 2872 2873 2874 2875 2876
bool FreeList::ContainsPageFreeListItems(Page* page) {
  bool contained = false;
  page->ForAllFreeListCategories(
      [this, &contained](FreeListCategory* category) {
        if (category->owner() == this && category->is_linked()) {
          contained = true;
        }
      });
  return contained;
}
2877

2878 2879 2880 2881 2882 2883 2884 2885 2886 2887 2888 2889 2890 2891 2892
void FreeList::RepairLists(Heap* heap) {
  ForAllFreeListCategories(
      [heap](FreeListCategory* category) { category->RepairFreeList(heap); });
}

bool FreeList::AddCategory(FreeListCategory* category) {
  FreeListCategoryType type = category->type_;
  FreeListCategory* top = categories_[type];

  if (category->is_empty()) return false;
  if (top == category) return false;

  // Common double-linked list insertion.
  if (top != nullptr) {
    top->set_prev(category);
2893
  }
2894 2895 2896
  category->set_next(top);
  categories_[type] = category;
  return true;
2897 2898
}

2899 2900 2901
void FreeList::RemoveCategory(FreeListCategory* category) {
  FreeListCategoryType type = category->type_;
  FreeListCategory* top = categories_[type];
2902

2903 2904 2905 2906 2907 2908 2909 2910 2911 2912 2913 2914 2915 2916 2917 2918
  // Common double-linked list removal.
  if (top == category) {
    categories_[type] = category->next();
  }
  if (category->prev() != nullptr) {
    category->prev()->set_next(category->next());
  }
  if (category->next() != nullptr) {
    category->next()->set_prev(category->prev());
  }
  category->set_next(nullptr);
  category->set_prev(nullptr);
}

void FreeList::PrintCategories(FreeListCategoryType type) {
  FreeListCategoryIterator it(this, type);
2919 2920
  PrintF("FreeList[%p, top=%p, %d] ", static_cast<void*>(this),
         static_cast<void*>(categories_[type]), type);
2921 2922
  while (it.HasNext()) {
    FreeListCategory* current = it.Next();
2923
    PrintF("%p -> ", static_cast<void*>(current));
2924
  }
2925
  PrintF("null\n");
2926 2927 2928
}


2929
#ifdef DEBUG
2930 2931
size_t FreeListCategory::SumFreeList() {
  size_t sum = 0;
2932
  FreeSpace* cur = top();
2933
  while (cur != NULL) {
2934
    DCHECK(cur->map() == cur->GetHeap()->root(Heap::kFreeSpaceMapRootIndex));
2935
    sum += cur->relaxed_read_size();
2936
    cur = cur->next();
2937
  }
2938
  return sum;
2939 2940
}

2941
int FreeListCategory::FreeListLength() {
2942
  int length = 0;
2943
  FreeSpace* cur = top();
2944 2945 2946 2947 2948 2949
  while (cur != NULL) {
    length++;
    cur = cur->next();
    if (length == kVeryLongFreeList) return length;
  }
  return length;
2950 2951
}

2952
bool FreeList::IsVeryLong() {
2953
  int len = 0;
2954
  for (int i = kFirstCategory; i < kNumberOfCategories; i++) {
2955 2956 2957 2958
    FreeListCategoryIterator it(this, static_cast<FreeListCategoryType>(i));
    while (it.HasNext()) {
      len += it.Next()->FreeListLength();
      if (len >= FreeListCategory::kVeryLongFreeList) return true;
2959 2960 2961
    }
  }
  return false;
2962
}
2963 2964


2965 2966 2967
// This can take a very long time because it is linear in the number of entries
// on the free list, so it should not be called if FreeListLength returns
// kVeryLongFreeList.
2968 2969
size_t FreeList::SumFreeLists() {
  size_t sum = 0;
2970 2971
  ForAllFreeListCategories(
      [&sum](FreeListCategory* category) { sum += category->SumFreeList(); });
2972
  return sum;
2973
}
2974
#endif
2975 2976


2977 2978 2979 2980 2981 2982
// -----------------------------------------------------------------------------
// OldSpace implementation

void PagedSpace::PrepareForMarkCompact() {
  // We don't have a linear allocation area while sweeping.  It will be restored
  // on the first allocation after the sweep.
2983
  EmptyAllocationInfo();
2984 2985 2986 2987

  // Clear the free list before a full GC---it will be rebuilt afterward.
  free_list_.Reset();
}
2988

2989
size_t PagedSpace::SizeOfObjects() {
2990
  CHECK_GE(limit(), top());
2991 2992
  DCHECK_GE(Size(), static_cast<size_t>(limit() - top()));
  return Size() - (limit() - top());
2993 2994 2995
}


2996 2997 2998 2999
// After we have booted, we have created a map which represents free space
// on the heap.  If there was already a free list then the elements on it
// were created with the wrong FreeSpaceMap (normally NULL), so we need to
// fix them.
3000 3001 3002
void PagedSpace::RepairFreeListsAfterDeserialization() {
  free_list_.RepairLists(heap());
  // Each page may have a small free space that is not tracked by a free list.
3003 3004
  // Those free spaces still contain null as their map pointer.
  // Overwrite them with new fillers.
3005
  for (Page* page : *this) {
3006 3007 3008 3009 3010 3011 3012 3013 3014
    int size = static_cast<int>(page->wasted_memory());
    if (size == 0) {
      // If there is no wasted memory then all free space is in the free list.
      continue;
    }
    Address start = page->HighWaterMark();
    Address end = page->area_end();
    CHECK_EQ(size, static_cast<int>(end - start));
    heap()->CreateFillerObjectAt(start, size, ClearRecordedSlots::kNo);
3015 3016
  }
}
3017

3018
HeapObject* PagedSpace::SweepAndRetryAllocation(int size_in_bytes) {
3019
  MarkCompactCollector* collector = heap()->mark_compact_collector();
3020
  if (collector->sweeping_in_progress()) {
3021
    // Wait for the sweeper threads here and complete the sweeping phase.
3022
    collector->EnsureSweepingCompleted();
3023 3024 3025 3026 3027

    // After waiting for the sweeper threads, there may be new free-list
    // entries.
    return free_list_.Allocate(size_in_bytes);
  }
3028 3029 3030 3031 3032 3033 3034 3035 3036 3037
  return nullptr;
}

HeapObject* CompactionSpace::SweepAndRetryAllocation(int size_in_bytes) {
  MarkCompactCollector* collector = heap()->mark_compact_collector();
  if (collector->sweeping_in_progress()) {
    collector->SweepAndRefill(this);
    return free_list_.Allocate(size_in_bytes);
  }
  return nullptr;
3038 3039
}

3040
HeapObject* PagedSpace::SlowAllocateRaw(int size_in_bytes) {
3041
  VMState<GC> state(heap()->isolate());
3042 3043
  RuntimeCallTimerScope runtime_timer(heap()->isolate(),
                                      &RuntimeCallStats::GC_SlowAllocateRaw);
3044 3045
  return RawSlowAllocateRaw(size_in_bytes);
}
3046

3047 3048 3049 3050 3051
HeapObject* CompactionSpace::SlowAllocateRaw(int size_in_bytes) {
  return RawSlowAllocateRaw(size_in_bytes);
}

HeapObject* PagedSpace::RawSlowAllocateRaw(int size_in_bytes) {
3052
  // Allocation in this space has failed.
3053 3054
  DCHECK_GE(size_in_bytes, 0);
  const int kMaxPagesToSweep = 1;
3055

3056
  MarkCompactCollector* collector = heap()->mark_compact_collector();
3057 3058
  // Sweeping is still in progress.
  if (collector->sweeping_in_progress()) {
3059 3060 3061 3062 3063
    if (FLAG_concurrent_sweeping && !is_local() &&
        !collector->sweeper().AreSweeperTasksRunning()) {
      collector->EnsureSweepingCompleted();
    }

3064 3065
    // First try to refill the free-list, concurrent sweeper threads
    // may have freed some objects in the meantime.
3066
    RefillFreeList();
3067

3068
    // Retry the free list allocation.
3069 3070
    HeapObject* object =
        free_list_.Allocate(static_cast<size_t>(size_in_bytes));
3071
    if (object != NULL) return object;
3072 3073

    // If sweeping is still in progress try to sweep pages on the main thread.
mlippautz's avatar
mlippautz committed
3074 3075
    int max_freed = collector->sweeper().ParallelSweepSpace(
        identity(), size_in_bytes, kMaxPagesToSweep);
3076
    RefillFreeList();
3077
    if (max_freed >= size_in_bytes) {
3078
      object = free_list_.Allocate(static_cast<size_t>(size_in_bytes));
3079 3080
      if (object != nullptr) return object;
    }
3081 3082 3083 3084 3085 3086 3087 3088 3089 3090 3091
  } else if (is_local()) {
    // Sweeping not in progress and we are on a {CompactionSpace}. This can
    // only happen when we are evacuating for the young generation.
    PagedSpace* main_space = heap()->paged_space(identity());
    Page* page = main_space->RemovePageSafe(size_in_bytes);
    if (page != nullptr) {
      AddPage(page);
      HeapObject* object =
          free_list_.Allocate(static_cast<size_t>(size_in_bytes));
      if (object != nullptr) return object;
    }
3092
  }
3093

3094
  if (heap()->ShouldExpandOldGenerationOnSlowAllocation() && Expand()) {
3095
    DCHECK((CountTotalPages() > 1) ||
3096
           (static_cast<size_t>(size_in_bytes) <= free_list_.Available()));
3097
    return free_list_.Allocate(static_cast<size_t>(size_in_bytes));
3098
  }
3099

3100 3101 3102
  // If sweeper threads are active, wait for them at that point and steal
  // elements form their free-lists. Allocation may still fail their which
  // would indicate that there is not enough memory for the given allocation.
3103
  return SweepAndRetryAllocation(size_in_bytes);
3104 3105
}

3106
#ifdef DEBUG
3107
void PagedSpace::ReportStatistics() {
3108
  int pct = static_cast<int>(Available() * 100 / Capacity());
3109 3110
  PrintF("  capacity: %" PRIuS ", waste: %" PRIuS
         ", available: %" PRIuS ", %%%d\n",
3111 3112
         Capacity(), Waste(), Available(), pct);

3113
  heap()->mark_compact_collector()->EnsureSweepingCompleted();
3114
  ClearHistograms(heap()->isolate());
3115
  HeapObjectIterator obj_it(this);
3116
  for (HeapObject* obj = obj_it.Next(); obj != NULL; obj = obj_it.Next())
3117
    CollectHistogramInfo(obj);
3118
  ReportHistogram(heap()->isolate(), true);
3119 3120 3121 3122
}
#endif


3123 3124 3125
// -----------------------------------------------------------------------------
// MapSpace implementation

3126
#ifdef VERIFY_HEAP
3127
void MapSpace::VerifyObject(HeapObject* object) { CHECK(object->IsMap()); }
3128
#endif
3129

3130 3131 3132 3133 3134 3135
Address LargePage::GetAddressToShrink() {
  HeapObject* object = GetObject();
  if (executable() == EXECUTABLE) {
    return 0;
  }
  size_t used_size = RoundUp((object->address() - address()) + object->Size(),
3136
                             MemoryAllocator::GetCommitPageSize());
3137 3138 3139 3140 3141 3142 3143
  if (used_size < CommittedPhysicalMemory()) {
    return address() + used_size;
  }
  return 0;
}

void LargePage::ClearOutOfLiveRangeSlots(Address free_start) {
3144 3145 3146 3147
  RememberedSet<OLD_TO_NEW>::RemoveRange(this, free_start, area_end(),
                                         SlotSet::FREE_EMPTY_BUCKETS);
  RememberedSet<OLD_TO_OLD>::RemoveRange(this, free_start, area_end(),
                                         SlotSet::FREE_EMPTY_BUCKETS);
3148 3149
  RememberedSet<OLD_TO_NEW>::RemoveRangeTyped(this, free_start, area_end());
  RememberedSet<OLD_TO_OLD>::RemoveRangeTyped(this, free_start, area_end());
3150
}
3151

3152 3153 3154 3155
// -----------------------------------------------------------------------------
// LargeObjectIterator

LargeObjectIterator::LargeObjectIterator(LargeObjectSpace* space) {
3156
  current_ = space->first_page_;
3157 3158 3159
}


3160
HeapObject* LargeObjectIterator::Next() {
3161 3162
  if (current_ == NULL) return NULL;

3163
  HeapObject* object = current_->GetObject();
3164
  current_ = current_->next_page();
3165 3166 3167 3168 3169 3170
  return object;
}


// -----------------------------------------------------------------------------
// LargeObjectSpace
3171

3172
LargeObjectSpace::LargeObjectSpace(Heap* heap, AllocationSpace id)
3173
    : Space(heap, id, NOT_EXECUTABLE),  // Managed on a per-allocation basis
3174
      first_page_(NULL),
3175
      size_(0),
3176
      page_count_(0),
3177
      objects_size_(0),
3178
      chunk_map_(1024) {}
3179

3180 3181 3182
LargeObjectSpace::~LargeObjectSpace() {}


3183
bool LargeObjectSpace::SetUp() {
3184
  first_page_ = NULL;
3185 3186
  size_ = 0;
  page_count_ = 0;
3187
  objects_size_ = 0;
3188
  chunk_map_.Clear();
3189 3190 3191 3192 3193
  return true;
}


void LargeObjectSpace::TearDown() {
3194 3195 3196 3197
  while (first_page_ != NULL) {
    LargePage* page = first_page_;
    first_page_ = first_page_->next_page();
    LOG(heap()->isolate(), DeleteEvent("LargeObjectChunk", page->address()));
3198
    heap()->memory_allocator()->Free<MemoryAllocator::kFull>(page);
3199
  }
3200
  SetUp();
3201 3202 3203
}


3204 3205
AllocationResult LargeObjectSpace::AllocateRaw(int object_size,
                                               Executability executable) {
3206 3207
  // Check if we want to force a GC before growing the old space further.
  // If so, fail the allocation.
3208 3209
  if (!heap()->CanExpandOldGeneration(object_size) ||
      !heap()->ShouldExpandOldGenerationOnSlowAllocation()) {
3210
    return AllocationResult::Retry(identity());
3211 3212
  }

3213
  LargePage* page = heap()->memory_allocator()->AllocateLargePage(
3214
      object_size, this, executable);
3215
  if (page == NULL) return AllocationResult::Retry(identity());
3216
  DCHECK_GE(page->area_size(), static_cast<size_t>(object_size));
3217

3218
  size_ += static_cast<int>(page->size());
3219
  AccountCommitted(page->size());
3220
  objects_size_ += object_size;
3221
  page_count_++;
3222 3223
  page->set_next_page(first_page_);
  first_page_ = page;
3224

3225
  InsertChunkMapEntries(page);
3226

3227
  HeapObject* object = page->GetObject();
3228

3229 3230 3231 3232 3233
  if (Heap::ShouldZapGarbage()) {
    // Make the object consistent so the heap can be verified in OldSpaceStep.
    // We only need to do this in debug builds or if verify_heap is on.
    reinterpret_cast<Object**>(object->address())[0] =
        heap()->fixed_array_map();
3234
    reinterpret_cast<Object**>(object->address())[1] = Smi::kZero;
3235
  }
3236

3237 3238
  heap()->StartIncrementalMarkingIfAllocationLimitIsReached(
      Heap::kNoGCFlags, kGCCallbackScheduleIdleGarbageCollection);
3239
  AllocationStep(object->address(), object_size);
3240

3241 3242 3243
  heap()->CreateFillerObjectAt(object->address(), object_size,
                               ClearRecordedSlots::kNo);

3244
  if (heap()->incremental_marking()->black_allocation()) {
3245 3246
    ObjectMarking::WhiteToBlack<IncrementalMarking::kAtomicity>(
        object, MarkingState::Internal(object));
3247
  }
3248
  return object;
3249 3250 3251
}


3252
size_t LargeObjectSpace::CommittedPhysicalMemory() {
3253 3254 3255 3256
  // On a platform that provides lazy committing of memory, we over-account
  // the actually committed memory. There is no easy way right now to support
  // precise accounting of committed memory in large object space.
  return CommittedMemory();
3257 3258 3259
}


3260
// GC support
3261
Object* LargeObjectSpace::FindObject(Address a) {
3262 3263 3264
  LargePage* page = FindPage(a);
  if (page != NULL) {
    return page->GetObject();
3265
  }
3266
  return Smi::kZero;  // Signaling not found.
3267 3268
}

3269 3270 3271 3272
LargePage* LargeObjectSpace::FindPageThreadSafe(Address a) {
  base::LockGuard<base::Mutex> guard(&chunk_map_mutex_);
  return FindPage(a);
}
3273

3274 3275
LargePage* LargeObjectSpace::FindPage(Address a) {
  uintptr_t key = reinterpret_cast<uintptr_t>(a) / MemoryChunk::kAlignment;
lpy's avatar
lpy committed
3276 3277
  base::HashMap::Entry* e = chunk_map_.Lookup(reinterpret_cast<void*>(key),
                                              static_cast<uint32_t>(key));
3278
  if (e != NULL) {
3279
    DCHECK(e->value != NULL);
3280
    LargePage* page = reinterpret_cast<LargePage*>(e->value);
3281
    DCHECK(LargePage::IsValid(page));
3282 3283
    if (page->Contains(a)) {
      return page;
3284 3285 3286 3287 3288 3289
    }
  }
  return NULL;
}


3290
void LargeObjectSpace::ClearMarkingStateOfLiveObjects() {
3291 3292
  LargeObjectIterator it(this);
  for (HeapObject* obj = it.Next(); obj != NULL; obj = it.Next()) {
3293 3294 3295
    if (ObjectMarking::IsBlackOrGrey(obj, MarkingState::Internal(obj))) {
      Marking::MarkWhite(
          ObjectMarking::MarkBitFrom(obj, MarkingState::Internal(obj)));
3296 3297
      MemoryChunk* chunk = MemoryChunk::FromAddress(obj->address());
      chunk->ResetProgressBar();
3298
      MarkingState::Internal(chunk).SetLiveBytes(0);
3299
    }
3300
    DCHECK(ObjectMarking::IsWhite(obj, MarkingState::Internal(obj)));
3301 3302 3303
  }
}

3304 3305 3306 3307 3308 3309
void LargeObjectSpace::InsertChunkMapEntries(LargePage* page) {
  // Register all MemoryChunk::kAlignment-aligned chunks covered by
  // this large page in the chunk map.
  uintptr_t start = reinterpret_cast<uintptr_t>(page) / MemoryChunk::kAlignment;
  uintptr_t limit = (reinterpret_cast<uintptr_t>(page) + (page->size() - 1)) /
                    MemoryChunk::kAlignment;
3310 3311 3312
  // There may be concurrent access on the chunk map. We have to take the lock
  // here.
  base::LockGuard<base::Mutex> guard(&chunk_map_mutex_);
3313 3314 3315 3316 3317 3318 3319 3320 3321 3322 3323 3324 3325 3326 3327 3328 3329 3330 3331 3332 3333 3334 3335
  for (uintptr_t key = start; key <= limit; key++) {
    base::HashMap::Entry* entry = chunk_map_.InsertNew(
        reinterpret_cast<void*>(key), static_cast<uint32_t>(key));
    DCHECK(entry != NULL);
    entry->value = page;
  }
}

void LargeObjectSpace::RemoveChunkMapEntries(LargePage* page) {
  RemoveChunkMapEntries(page, page->address());
}

void LargeObjectSpace::RemoveChunkMapEntries(LargePage* page,
                                             Address free_start) {
  uintptr_t start = RoundUp(reinterpret_cast<uintptr_t>(free_start),
                            MemoryChunk::kAlignment) /
                    MemoryChunk::kAlignment;
  uintptr_t limit = (reinterpret_cast<uintptr_t>(page) + (page->size() - 1)) /
                    MemoryChunk::kAlignment;
  for (uintptr_t key = start; key <= limit; key++) {
    chunk_map_.Remove(reinterpret_cast<void*>(key), static_cast<uint32_t>(key));
  }
}
3336

3337
void LargeObjectSpace::FreeUnmarkedObjects() {
3338
  LargePage* previous = nullptr;
3339
  LargePage* current = first_page_;
3340
  while (current != nullptr) {
3341
    HeapObject* object = current->GetObject();
3342 3343
    DCHECK(!ObjectMarking::IsGrey(object, MarkingState::Internal(object)));
    if (ObjectMarking::IsBlack(object, MarkingState::Internal(object))) {
3344 3345
      Address free_start;
      if ((free_start = current->GetAddressToShrink()) != 0) {
3346
        DCHECK(!current->IsFlagSet(Page::IS_EXECUTABLE));
3347 3348
        current->ClearOutOfLiveRangeSlots(free_start);
        RemoveChunkMapEntries(current, free_start);
3349 3350
        const size_t bytes_to_free =
            current->size() - (free_start - current->address());
3351 3352 3353
        heap()->memory_allocator()->PartialFreeMemory(
            current, free_start, bytes_to_free,
            current->area_start() + object->Size());
3354 3355
        size_ -= bytes_to_free;
        AccountUncommitted(bytes_to_free);
3356
      }
3357
      previous = current;
3358
      current = current->next_page();
3359
    } else {
3360
      LargePage* page = current;
3361
      // Cut the chunk out from the chunk list.
3362
      current = current->next_page();
3363
      if (previous == nullptr) {
3364
        first_page_ = current;
3365
      } else {
3366
        previous->set_next_page(current);
3367 3368 3369
      }

      // Free the chunk.
3370
      size_ -= static_cast<int>(page->size());
3371
      AccountUncommitted(page->size());
3372
      objects_size_ -= object->Size();
3373
      page_count_--;
3374

3375
      RemoveChunkMapEntries(page);
3376
      heap()->memory_allocator()->Free<MemoryAllocator::kPreFreeAndQueue>(page);
3377 3378 3379 3380 3381 3382 3383
    }
  }
}


bool LargeObjectSpace::Contains(HeapObject* object) {
  Address address = object->address();
3384
  MemoryChunk* chunk = MemoryChunk::FromAddress(address);
3385

3386
  bool owned = (chunk->owner() == this);
3387

3388
  SLOW_DCHECK(!owned || FindObject(address)->IsHeapObject());
3389 3390

  return owned;
3391 3392
}

3393 3394 3395
std::unique_ptr<ObjectIterator> LargeObjectSpace::GetObjectIterator() {
  return std::unique_ptr<ObjectIterator>(new LargeObjectIterator(this));
}
3396

3397
#ifdef VERIFY_HEAP
3398 3399 3400
// We do not assume that the large object iterator works, because it depends
// on the invariants we are checking during verification.
void LargeObjectSpace::Verify() {
3401
  for (LargePage* chunk = first_page_; chunk != NULL;
3402
       chunk = chunk->next_page()) {
3403 3404 3405 3406
    // Each chunk contains an object that starts at the large object page's
    // object area start.
    HeapObject* object = chunk->GetObject();
    Page* page = Page::FromAddress(object->address());
3407
    CHECK(object->address() == page->area_start());
3408 3409 3410 3411

    // The first word should be a map, and we expect all map pointers to be
    // in map space.
    Map* map = object->map();
3412 3413
    CHECK(map->IsMap());
    CHECK(heap()->map_space()->Contains(map));
3414

3415 3416
    // We have only code, sequential strings, external strings
    // (sequential strings that have been morphed into external
3417
    // strings), thin strings (sequential strings that have been
3418 3419 3420
    // morphed into thin strings), fixed arrays, fixed double arrays,
    // byte arrays, and free space (right after allocation) in the
    // large object space.
3421
    CHECK(object->IsAbstractCode() || object->IsSeqString() ||
3422 3423
          object->IsExternalString() || object->IsThinString() ||
          object->IsFixedArray() || object->IsFixedDoubleArray() ||
3424
          object->IsByteArray() || object->IsFreeSpace());
3425 3426

    // The object itself should look OK.
3427
    object->ObjectVerify();
3428

3429 3430 3431
    if (!FLAG_verify_heap_skip_remembered_set) {
      heap()->VerifyRememberedSetFor(object);
    }
3432

3433
    // Byte arrays and strings don't have interior pointers.
3434
    if (object->IsAbstractCode()) {
3435
      VerifyPointersVisitor code_visitor;
3436
      object->IterateBody(map->instance_type(), object->Size(), &code_visitor);
3437 3438 3439 3440 3441 3442
    } else if (object->IsFixedArray()) {
      FixedArray* array = FixedArray::cast(object);
      for (int j = 0; j < array->length(); j++) {
        Object* element = array->get(j);
        if (element->IsHeapObject()) {
          HeapObject* element_object = HeapObject::cast(element);
3443 3444
          CHECK(heap()->Contains(element_object));
          CHECK(element_object->map()->IsMap());
3445 3446 3447 3448 3449
        }
      }
    }
  }
}
3450
#endif
3451

3452
#ifdef DEBUG
3453
void LargeObjectSpace::Print() {
3454
  OFStream os(stdout);
3455
  LargeObjectIterator it(this);
3456
  for (HeapObject* obj = it.Next(); obj != NULL; obj = it.Next()) {
3457
    obj->Print(os);
3458 3459 3460 3461 3462
  }
}


void LargeObjectSpace::ReportStatistics() {
3463
  PrintF("  size: %" PRIuS "\n", size_);
3464
  int num_objects = 0;
3465
  ClearHistograms(heap()->isolate());
3466
  LargeObjectIterator it(this);
3467
  for (HeapObject* obj = it.Next(); obj != NULL; obj = it.Next()) {
3468
    num_objects++;
3469
    CollectHistogramInfo(obj);
3470 3471
  }

3472 3473
  PrintF(
      "  number of objects %d, "
3474
      "size of objects %" PRIuS "\n",
3475
      num_objects, objects_size_);
3476
  if (num_objects > 0) ReportHistogram(heap()->isolate(), false);
3477 3478 3479
}


3480 3481
void Page::Print() {
  // Make a best-effort to print the objects in the page.
3482
  PrintF("Page@%p in %s\n", static_cast<void*>(this->address()),
3483 3484
         AllocationSpaceName(this->owner()->identity()));
  printf(" --------------------------------------\n");
3485
  HeapObjectIterator objects(this);
3486
  unsigned mark_size = 0;
3487
  for (HeapObject* object = objects.Next(); object != NULL;
3488
       object = objects.Next()) {
3489 3490
    bool is_marked =
        ObjectMarking::IsBlackOrGrey(object, MarkingState::Internal(object));
3491 3492
    PrintF(" %c ", (is_marked ? '!' : ' '));  // Indent a little.
    if (is_marked) {
3493
      mark_size += object->Size();
3494 3495 3496 3497 3498
    }
    object->ShortPrint();
    PrintF("\n");
  }
  printf(" --------------------------------------\n");
3499 3500
  printf(" Marked: %x, LiveCount: %" V8PRIdPTR "\n", mark_size,
         MarkingState::Internal(this).live_bytes());
3501 3502
}

3503
#endif  // DEBUG
3504 3505
}  // namespace internal
}  // namespace v8