spaces.cc 99.7 KB
Newer Older
danno@chromium.org's avatar
danno@chromium.org committed
1
// Copyright 2011 the V8 project authors. All rights reserved.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//     * Redistributions of source code must retain the above copyright
//       notice, this list of conditions and the following disclaimer.
//     * Redistributions in binary form must reproduce the above
//       copyright notice, this list of conditions and the following
//       disclaimer in the documentation and/or other materials provided
//       with the distribution.
//     * Neither the name of Google Inc. nor the names of its
//       contributors may be used to endorse or promote products derived
//       from this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

#include "v8.h"

30
#include "liveobjectlist-inl.h"
31 32 33 34
#include "macro-assembler.h"
#include "mark-compact.h"
#include "platform.h"

35 36
namespace v8 {
namespace internal {
37 38 39 40

// For contiguous spaces, top should be in the space (or at the end) and limit
// should be the end of the space.
#define ASSERT_SEMISPACE_ALLOCATION_INFO(info, space) \
41 42
  ASSERT((space).low() <= (info).top                  \
         && (info).top <= (space).high()              \
43
         && (info).limit == (space).high())
44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69

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

HeapObjectIterator::HeapObjectIterator(PagedSpace* space) {
  Initialize(space->bottom(), space->top(), NULL);
}


HeapObjectIterator::HeapObjectIterator(PagedSpace* space,
                                       HeapObjectCallback size_func) {
  Initialize(space->bottom(), space->top(), size_func);
}


HeapObjectIterator::HeapObjectIterator(PagedSpace* space, Address start) {
  Initialize(start, space->top(), NULL);
}


HeapObjectIterator::HeapObjectIterator(PagedSpace* space, Address start,
                                       HeapObjectCallback size_func) {
  Initialize(start, space->top(), size_func);
}


70 71 72 73 74 75
HeapObjectIterator::HeapObjectIterator(Page* page,
                                       HeapObjectCallback size_func) {
  Initialize(page->ObjectAreaStart(), page->AllocationTop(), size_func);
}


76 77 78 79 80 81 82 83 84 85 86 87 88 89 90
void HeapObjectIterator::Initialize(Address cur, Address end,
                                    HeapObjectCallback size_f) {
  cur_addr_ = cur;
  end_addr_ = end;
  end_page_ = Page::FromAllocationTop(end);
  size_func_ = size_f;
  Page* p = Page::FromAllocationTop(cur_addr_);
  cur_limit_ = (p == end_page_) ? end_addr_ : p->AllocationTop();

#ifdef DEBUG
  Verify();
#endif
}


91 92
HeapObject* HeapObjectIterator::FromNextPage() {
  if (cur_addr_ == end_addr_) return NULL;
93 94 95 96 97 98 99 100

  Page* cur_page = Page::FromAllocationTop(cur_addr_);
  cur_page = cur_page->next_page();
  ASSERT(cur_page->is_valid());

  cur_addr_ = cur_page->ObjectAreaStart();
  cur_limit_ = (cur_page == end_page_) ? end_addr_ : cur_page->AllocationTop();

101
  if (cur_addr_ == end_addr_) return NULL;
102 103 104 105
  ASSERT(cur_addr_ < cur_limit_);
#ifdef DEBUG
  Verify();
#endif
106
  return FromCurrentPage();
107 108 109 110 111 112 113 114 115 116 117 118 119 120 121
}


#ifdef DEBUG
void HeapObjectIterator::Verify() {
  Page* p = Page::FromAllocationTop(cur_addr_);
  ASSERT(p == Page::FromAllocationTop(cur_limit_));
  ASSERT(p->Offset(cur_addr_) <= p->Offset(cur_limit_));
}
#endif


// -----------------------------------------------------------------------------
// PageIterator

122 123
PageIterator::PageIterator(PagedSpace* space, Mode mode) : space_(space) {
  prev_page_ = NULL;
124 125
  switch (mode) {
    case PAGES_IN_USE:
126
      stop_page_ = space->AllocationTopPage();
127 128
      break;
    case PAGES_USED_BY_MC:
129
      stop_page_ = space->MCRelocationTopPage();
130 131
      break;
    case ALL_PAGES:
132 133 134 135 136 137 138 139 140 141
#ifdef DEBUG
      // Verify that the cached last page in the space is actually the
      // last page.
      for (Page* p = space->first_page_; p->is_valid(); p = p->next_page()) {
        if (!p->next_page()->is_valid()) {
          ASSERT(space->last_page_ == p);
        }
      }
#endif
      stop_page_ = space->last_page_;
142 143 144 145 146
      break;
  }
}


147 148 149
// -----------------------------------------------------------------------------
// CodeRange

150 151 152 153 154 155 156 157

CodeRange::CodeRange()
    : code_range_(NULL),
      free_list_(0),
      allocation_list_(0),
      current_allocation_block_index_(0),
      isolate_(NULL) {
}
158 159 160 161 162 163 164 165 166 167 168 169 170 171 172


bool CodeRange::Setup(const size_t requested) {
  ASSERT(code_range_ == NULL);

  code_range_ = new VirtualMemory(requested);
  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.
  ASSERT(code_range_->size() == requested);
173
  LOG(isolate_, NewEvent("CodeRange", code_range_->address(), requested));
174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272
  allocation_list_.Add(FreeBlock(code_range_->address(), code_range_->size()));
  current_allocation_block_index_ = 0;
  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);
}


void CodeRange::GetNextAllocationBlock(size_t requested) {
  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) {
      return;  // Found a large enough allocation block.
    }
  }

  // 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;
      i++;
    }
    if (merged.size > 0) {
      allocation_list_.Add(merged);
    }
  }
  free_list_.Clear();

  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) {
      return;  // Found a large enough allocation block.
    }
  }

  // Code range is full or too fragmented.
  V8::FatalProcessOutOfMemory("CodeRange::GetNextAllocationBlock");
}



void* CodeRange::AllocateRawMemory(const size_t requested, size_t* allocated) {
  ASSERT(current_allocation_block_index_ < allocation_list_.length());
  if (requested > allocation_list_[current_allocation_block_index_].size) {
    // Find an allocation block large enough.  This function call may
    // call V8::FatalProcessOutOfMemory if it cannot find a large enough block.
    GetNextAllocationBlock(requested);
  }
  // Commit the requested memory at the start of the current allocation block.
  *allocated = RoundUp(requested, Page::kPageSize);
  FreeBlock current = allocation_list_[current_allocation_block_index_];
  if (*allocated >= current.size - Page::kPageSize) {
    // Don't leave a small free block, useless for a large object or chunk.
    *allocated = current.size;
  }
  ASSERT(*allocated <= current.size);
  if (!code_range_->Commit(current.start, *allocated, true)) {
    *allocated = 0;
    return NULL;
  }
  allocation_list_[current_allocation_block_index_].start += *allocated;
  allocation_list_[current_allocation_block_index_].size -= *allocated;
  if (*allocated == current.size) {
    GetNextAllocationBlock(0);  // This block is used up, get the next one.
  }
  return current.start;
}


void CodeRange::FreeRawMemory(void* address, size_t length) {
  free_list_.Add(FreeBlock(address, length));
  code_range_->Uncommit(address, length);
}


void CodeRange::TearDown() {
    delete code_range_;  // Frees all memory in the virtual memory range.
    code_range_ = NULL;
    free_list_.Free();
    allocation_list_.Free();
}


273 274 275 276 277 278 279
// -----------------------------------------------------------------------------
// MemoryAllocator
//

// 270 is an estimate based on the static default heap size of a pair of 256K
// semispaces and a 64M old generation.
const int kEstimatedNumberOfChunks = 270;
280 281 282 283 284 285 286 287 288 289 290 291 292 293


MemoryAllocator::MemoryAllocator()
    : capacity_(0),
      capacity_executable_(0),
      size_(0),
      size_executable_(0),
      initial_chunk_(NULL),
      chunks_(kEstimatedNumberOfChunks),
      free_chunk_ids_(kEstimatedNumberOfChunks),
      max_nof_chunks_(0),
      top_(0),
      isolate_(NULL) {
}
294 295 296 297 298 299 300 301 302 303 304 305 306 307 308


void MemoryAllocator::Push(int free_chunk_id) {
  ASSERT(max_nof_chunks_ > 0);
  ASSERT(top_ < max_nof_chunks_);
  free_chunk_ids_[top_++] = free_chunk_id;
}


int MemoryAllocator::Pop() {
  ASSERT(top_ > 0);
  return free_chunk_ids_[--top_];
}


309
bool MemoryAllocator::Setup(intptr_t capacity, intptr_t capacity_executable) {
310
  capacity_ = RoundUp(capacity, Page::kPageSize);
311 312
  capacity_executable_ = RoundUp(capacity_executable, Page::kPageSize);
  ASSERT_GE(capacity_, capacity_executable_);
313 314 315 316 317 318 319 320

  // Over-estimate the size of chunks_ array.  It assumes the expansion of old
  // space is always in the unit of a chunk (kChunkSize) except the last
  // expansion.
  //
  // Due to alignment, allocated space might be one page less than required
  // number (kPagesPerChunk) of pages for old spaces.
  //
321 322
  // Reserve two chunk ids for semispaces, one for map space, one for old
  // space, and one for code space.
323 324
  max_nof_chunks_ =
      static_cast<int>((capacity_ / (kChunkSize - Page::kPageSize))) + 5;
325 326 327
  if (max_nof_chunks_ > kMaxNofChunks) return false;

  size_ = 0;
328
  size_executable_ = 0;
329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346
  ChunkInfo info;  // uninitialized element.
  for (int i = max_nof_chunks_ - 1; i >= 0; i--) {
    chunks_.Add(info);
    free_chunk_ids_.Add(i);
  }
  top_ = max_nof_chunks_;
  return true;
}


void MemoryAllocator::TearDown() {
  for (int i = 0; i < max_nof_chunks_; i++) {
    if (chunks_[i].address() != NULL) DeleteChunk(i);
  }
  chunks_.Clear();
  free_chunk_ids_.Clear();

  if (initial_chunk_ != NULL) {
347
    LOG(isolate_, DeleteEvent("InitialChunk", initial_chunk_->address()));
348 349 350 351 352 353 354
    delete initial_chunk_;
    initial_chunk_ = NULL;
  }

  ASSERT(top_ == max_nof_chunks_);  // all chunks are free
  top_ = 0;
  capacity_ = 0;
355
  capacity_executable_ = 0;
356 357 358 359 360 361
  size_ = 0;
  max_nof_chunks_ = 0;
}


void* MemoryAllocator::AllocateRawMemory(const size_t requested,
362
                                         size_t* allocated,
363
                                         Executability executable) {
ager@chromium.org's avatar
ager@chromium.org committed
364 365 366
  if (size_ + static_cast<size_t>(requested) > static_cast<size_t>(capacity_)) {
    return NULL;
  }
367

368
  void* mem;
369 370 371 372
  if (executable == EXECUTABLE) {
    // Check executable memory limit.
    if (size_executable_ + requested >
        static_cast<size_t>(capacity_executable_)) {
373 374
      LOG(isolate_,
          StringEvent("MemoryAllocator::AllocateRawMemory",
375 376 377 378 379
                      "V8 Executable Allocation capacity exceeded"));
      return NULL;
    }
    // Allocate executable memory either from code range or from the
    // OS.
380 381
    if (isolate_->code_range()->exists()) {
      mem = isolate_->code_range()->AllocateRawMemory(requested, allocated);
382 383 384 385 386
    } else {
      mem = OS::Allocate(requested, allocated, true);
    }
    // Update executable memory size.
    size_executable_ += static_cast<int>(*allocated);
387
  } else {
388
    mem = OS::Allocate(requested, allocated, false);
389
  }
390
  int alloced = static_cast<int>(*allocated);
391
  size_ += alloced;
392

393 394 395
#ifdef DEBUG
  ZapBlock(reinterpret_cast<Address>(mem), alloced);
#endif
396
  isolate_->counters()->memory_allocated()->Increment(alloced);
397 398 399 400
  return mem;
}


401 402 403
void MemoryAllocator::FreeRawMemory(void* mem,
                                    size_t length,
                                    Executability executable) {
404 405 406
#ifdef DEBUG
  ZapBlock(reinterpret_cast<Address>(mem), length);
#endif
407 408
  if (isolate_->code_range()->contains(static_cast<Address>(mem))) {
    isolate_->code_range()->FreeRawMemory(mem, length);
409 410 411
  } else {
    OS::Free(mem, length);
  }
412
  isolate_->counters()->memory_allocated()->Decrement(static_cast<int>(length));
413
  size_ -= static_cast<int>(length);
414
  if (executable == EXECUTABLE) size_executable_ -= static_cast<int>(length);
415

416
  ASSERT(size_ >= 0);
417
  ASSERT(size_executable_ >= 0);
418 419 420
}


421 422
void MemoryAllocator::PerformAllocationCallback(ObjectSpace space,
                                                AllocationAction action,
423
                                                size_t size) {
424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465
  for (int i = 0; i < memory_allocation_callbacks_.length(); ++i) {
    MemoryAllocationCallbackRegistration registration =
      memory_allocation_callbacks_[i];
    if ((registration.space & space) == space &&
        (registration.action & action) == action)
      registration.callback(space, action, static_cast<int>(size));
  }
}


bool MemoryAllocator::MemoryAllocationCallbackRegistered(
    MemoryAllocationCallback callback) {
  for (int i = 0; i < memory_allocation_callbacks_.length(); ++i) {
    if (memory_allocation_callbacks_[i].callback == callback) return true;
  }
  return false;
}


void MemoryAllocator::AddMemoryAllocationCallback(
    MemoryAllocationCallback callback,
    ObjectSpace space,
    AllocationAction action) {
  ASSERT(callback != NULL);
  MemoryAllocationCallbackRegistration registration(callback, space, action);
  ASSERT(!MemoryAllocator::MemoryAllocationCallbackRegistered(callback));
  return memory_allocation_callbacks_.Add(registration);
}


void MemoryAllocator::RemoveMemoryAllocationCallback(
     MemoryAllocationCallback callback) {
  ASSERT(callback != NULL);
  for (int i = 0; i < memory_allocation_callbacks_.length(); ++i) {
    if (memory_allocation_callbacks_[i].callback == callback) {
      memory_allocation_callbacks_.Remove(i);
      return;
    }
  }
  UNREACHABLE();
}

466 467 468 469 470 471 472 473 474 475 476 477 478
void* MemoryAllocator::ReserveInitialChunk(const size_t requested) {
  ASSERT(initial_chunk_ == NULL);

  initial_chunk_ = new VirtualMemory(requested);
  CHECK(initial_chunk_ != NULL);
  if (!initial_chunk_->IsReserved()) {
    delete initial_chunk_;
    initial_chunk_ = NULL;
    return NULL;
  }

  // We are sure that we have mapped a block of requested addresses.
  ASSERT(initial_chunk_->size() == requested);
479 480
  LOG(isolate_,
      NewEvent("InitialChunk", initial_chunk_->address(), requested));
481
  size_ += static_cast<int>(requested);
482 483 484 485 486 487 488 489 490
  return initial_chunk_->address();
}


static int PagesInChunk(Address start, size_t size) {
  // The first page starts on the first page-aligned address from start onward
  // and the last page ends on the last page-aligned address before
  // start+size.  Page::kPageSize is a power of two so we can divide by
  // shifting.
491
  return static_cast<int>((RoundDown(start + size, Page::kPageSize)
492
      - RoundUp(start, Page::kPageSize)) >> kPageSizeBits);
493 494 495
}


496 497
Page* MemoryAllocator::AllocatePages(int requested_pages,
                                     int* allocated_pages,
498 499 500 501
                                     PagedSpace* owner) {
  if (requested_pages <= 0) return Page::FromAddress(NULL);
  size_t chunk_size = requested_pages * Page::kPageSize;

502
  void* chunk = AllocateRawMemory(chunk_size, &chunk_size, owner->executable());
503
  if (chunk == NULL) return Page::FromAddress(NULL);
504
  LOG(isolate_, NewEvent("PagedChunk", chunk, chunk_size));
505 506

  *allocated_pages = PagesInChunk(static_cast<Address>(chunk), chunk_size);
507 508
  // We may 'lose' a page due to alignment.
  ASSERT(*allocated_pages >= kPagesPerChunk - 1);
509
  if (*allocated_pages == 0) {
510
    FreeRawMemory(chunk, chunk_size, owner->executable());
511
    LOG(isolate_, DeleteEvent("PagedChunk", chunk));
512 513 514 515 516 517
    return Page::FromAddress(NULL);
  }

  int chunk_id = Pop();
  chunks_[chunk_id].init(static_cast<Address>(chunk), chunk_size, owner);

518 519
  ObjectSpace space = static_cast<ObjectSpace>(1 << owner->identity());
  PerformAllocationCallback(space, kAllocationActionAllocate, chunk_size);
520 521 522
  Page* new_pages = InitializePagesInChunk(chunk_id, *allocated_pages, owner);

  return new_pages;
523 524 525 526 527 528 529 530 531
}


Page* MemoryAllocator::CommitPages(Address start, size_t size,
                                   PagedSpace* owner, int* num_pages) {
  ASSERT(start != NULL);
  *num_pages = PagesInChunk(start, size);
  ASSERT(*num_pages > 0);
  ASSERT(initial_chunk_ != NULL);
532 533
  ASSERT(InInitialChunk(start));
  ASSERT(InInitialChunk(start + size - 1));
534
  if (!initial_chunk_->Commit(start, size, owner->executable() == EXECUTABLE)) {
535 536
    return Page::FromAddress(NULL);
  }
537 538 539
#ifdef DEBUG
  ZapBlock(start, size);
#endif
540
  isolate_->counters()->memory_allocated()->Increment(static_cast<int>(size));
541 542 543 544 545 546 547 548 549 550

  // So long as we correctly overestimated the number of chunks we should not
  // run out of chunk ids.
  CHECK(!OutOfChunkIds());
  int chunk_id = Pop();
  chunks_[chunk_id].init(start, size, owner);
  return InitializePagesInChunk(chunk_id, *num_pages, owner);
}


551 552
bool MemoryAllocator::CommitBlock(Address start,
                                  size_t size,
553
                                  Executability executable) {
554 555 556
  ASSERT(start != NULL);
  ASSERT(size > 0);
  ASSERT(initial_chunk_ != NULL);
557 558
  ASSERT(InInitialChunk(start));
  ASSERT(InInitialChunk(start + size - 1));
559

560
  if (!initial_chunk_->Commit(start, size, executable)) return false;
561 562 563
#ifdef DEBUG
  ZapBlock(start, size);
#endif
564
  isolate_->counters()->memory_allocated()->Increment(static_cast<int>(size));
565 566 567
  return true;
}

568

569 570 571 572 573 574 575 576
bool MemoryAllocator::UncommitBlock(Address start, size_t size) {
  ASSERT(start != NULL);
  ASSERT(size > 0);
  ASSERT(initial_chunk_ != NULL);
  ASSERT(InInitialChunk(start));
  ASSERT(InInitialChunk(start + size - 1));

  if (!initial_chunk_->Uncommit(start, size)) return false;
577
  isolate_->counters()->memory_allocated()->Decrement(static_cast<int>(size));
578 579
  return true;
}
580

581 582 583 584 585 586 587 588

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


589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607
Page* MemoryAllocator::InitializePagesInChunk(int chunk_id, int pages_in_chunk,
                                              PagedSpace* owner) {
  ASSERT(IsValidChunk(chunk_id));
  ASSERT(pages_in_chunk > 0);

  Address chunk_start = chunks_[chunk_id].address();

  Address low = RoundUp(chunk_start, Page::kPageSize);

#ifdef DEBUG
  size_t chunk_size = chunks_[chunk_id].size();
  Address high = RoundDown(chunk_start + chunk_size, Page::kPageSize);
  ASSERT(pages_in_chunk <=
        ((OffsetFrom(high) - OffsetFrom(low)) / Page::kPageSize));
#endif

  Address page_addr = low;
  for (int i = 0; i < pages_in_chunk; i++) {
    Page* p = Page::FromAddress(page_addr);
608
    p->heap_ = owner->heap();
609
    p->opaque_header = OffsetFrom(page_addr + Page::kPageSize) | chunk_id;
610
    p->InvalidateWatermark(true);
611
    p->SetIsLargeObjectPage(false);
612 613
    p->SetAllocationWatermark(p->ObjectAreaStart());
    p->SetCachedAllocationWatermark(p->ObjectAreaStart());
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 651 652 653 654 655 656
    page_addr += Page::kPageSize;
  }

  // Set the next page of the last page to 0.
  Page* last_page = Page::FromAddress(page_addr - Page::kPageSize);
  last_page->opaque_header = OffsetFrom(0) | chunk_id;

  return Page::FromAddress(low);
}


Page* MemoryAllocator::FreePages(Page* p) {
  if (!p->is_valid()) return p;

  // Find the first page in the same chunk as 'p'
  Page* first_page = FindFirstPageInSameChunk(p);
  Page* page_to_return = Page::FromAddress(NULL);

  if (p != first_page) {
    // Find the last page in the same chunk as 'prev'.
    Page* last_page = FindLastPageInSameChunk(p);
    first_page = GetNextPage(last_page);  // first page in next chunk

    // set the next_page of last_page to NULL
    SetNextPage(last_page, Page::FromAddress(NULL));
    page_to_return = p;  // return 'p' when exiting
  }

  while (first_page->is_valid()) {
    int chunk_id = GetChunkId(first_page);
    ASSERT(IsValidChunk(chunk_id));

    // Find the first page of the next chunk before deleting this chunk.
    first_page = GetNextPage(FindLastPageInSameChunk(first_page));

    // Free the current chunk.
    DeleteChunk(chunk_id);
  }

  return page_to_return;
}


657 658 659 660 661 662 663 664 665
void MemoryAllocator::FreeAllPages(PagedSpace* space) {
  for (int i = 0, length = chunks_.length(); i < length; i++) {
    if (chunks_[i].owner() == space) {
      DeleteChunk(i);
    }
  }
}


666 667 668 669 670 671 672 673
void MemoryAllocator::DeleteChunk(int chunk_id) {
  ASSERT(IsValidChunk(chunk_id));

  ChunkInfo& c = chunks_[chunk_id];

  // We cannot free a chunk contained in the initial chunk because it was not
  // allocated with AllocateRawMemory.  Instead we uncommit the virtual
  // memory.
674
  if (InInitialChunk(c.address())) {
675 676 677
    // TODO(1240712): VirtualMemory::Uncommit has a return value which
    // is ignored here.
    initial_chunk_->Uncommit(c.address(), c.size());
678 679
    Counters* counters = isolate_->counters();
    counters->memory_allocated()->Decrement(static_cast<int>(c.size()));
680
  } else {
681 682
    LOG(isolate_, DeleteEvent("PagedChunk", c.address()));
    ObjectSpace space = static_cast<ObjectSpace>(1 << c.owner_identity());
683 684
    size_t size = c.size();
    FreeRawMemory(c.address(), size, c.executable());
685
    PerformAllocationCallback(space, kAllocationActionFree, size);
686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717
  }
  c.init(NULL, 0, NULL);
  Push(chunk_id);
}


Page* MemoryAllocator::FindFirstPageInSameChunk(Page* p) {
  int chunk_id = GetChunkId(p);
  ASSERT(IsValidChunk(chunk_id));

  Address low = RoundUp(chunks_[chunk_id].address(), Page::kPageSize);
  return Page::FromAddress(low);
}


Page* MemoryAllocator::FindLastPageInSameChunk(Page* p) {
  int chunk_id = GetChunkId(p);
  ASSERT(IsValidChunk(chunk_id));

  Address chunk_start = chunks_[chunk_id].address();
  size_t chunk_size = chunks_[chunk_id].size();

  Address high = RoundDown(chunk_start + chunk_size, Page::kPageSize);
  ASSERT(chunk_start <= p->address() && p->address() < high);

  return Page::FromAddress(high - Page::kPageSize);
}


#ifdef DEBUG
void MemoryAllocator::ReportStatistics() {
  float pct = static_cast<float>(capacity_ - size_) / capacity_;
718 719 720
  PrintF("  capacity: %" V8_PTR_PREFIX "d"
             ", used: %" V8_PTR_PREFIX "d"
             ", available: %%%d\n\n",
721 722 723 724 725
         capacity_, size_, static_cast<int>(pct*100));
}
#endif


726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760
void MemoryAllocator::RelinkPageListInChunkOrder(PagedSpace* space,
                                                 Page** first_page,
                                                 Page** last_page,
                                                 Page** last_page_in_use) {
  Page* first = NULL;
  Page* last = NULL;

  for (int i = 0, length = chunks_.length(); i < length; i++) {
    ChunkInfo& chunk = chunks_[i];

    if (chunk.owner() == space) {
      if (first == NULL) {
        Address low = RoundUp(chunk.address(), Page::kPageSize);
        first = Page::FromAddress(low);
      }
      last = RelinkPagesInChunk(i,
                                chunk.address(),
                                chunk.size(),
                                last,
                                last_page_in_use);
    }
  }

  if (first_page != NULL) {
    *first_page = first;
  }

  if (last_page != NULL) {
    *last_page = last;
  }
}


Page* MemoryAllocator::RelinkPagesInChunk(int chunk_id,
                                          Address chunk_start,
761
                                          size_t chunk_size,
762 763 764 765 766 767 768 769 770 771 772 773 774 775
                                          Page* prev,
                                          Page** last_page_in_use) {
  Address page_addr = RoundUp(chunk_start, Page::kPageSize);
  int pages_in_chunk = PagesInChunk(chunk_start, chunk_size);

  if (prev->is_valid()) {
    SetNextPage(prev, Page::FromAddress(page_addr));
  }

  for (int i = 0; i < pages_in_chunk; i++) {
    Page* p = Page::FromAddress(page_addr);
    p->opaque_header = OffsetFrom(page_addr + Page::kPageSize) | chunk_id;
    page_addr += Page::kPageSize;

776
    p->InvalidateWatermark(true);
777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793
    if (p->WasInUseBeforeMC()) {
      *last_page_in_use = p;
    }
  }

  // Set the next page of the last page to 0.
  Page* last_page = Page::FromAddress(page_addr - Page::kPageSize);
  last_page->opaque_header = OffsetFrom(0) | chunk_id;

  if (last_page->WasInUseBeforeMC()) {
    *last_page_in_use = last_page;
  }

  return last_page;
}


794 795 796
// -----------------------------------------------------------------------------
// PagedSpace implementation

797 798
PagedSpace::PagedSpace(Heap* heap,
                       intptr_t max_capacity,
799 800
                       AllocationSpace id,
                       Executability executable)
801
    : Space(heap, id, executable) {
802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819
  max_capacity_ = (RoundDown(max_capacity, Page::kPageSize) / Page::kPageSize)
                  * Page::kObjectAreaSize;
  accounting_stats_.Clear();

  allocation_info_.top = NULL;
  allocation_info_.limit = NULL;

  mc_forwarding_info_.top = NULL;
  mc_forwarding_info_.limit = NULL;
}


bool PagedSpace::Setup(Address start, size_t size) {
  if (HasBeenSetup()) return false;

  int num_pages = 0;
  // Try to use the virtual memory range passed to us.  If it is too small to
  // contain at least one page, ignore it and allocate instead.
820 821
  int pages_in_chunk = PagesInChunk(start, size);
  if (pages_in_chunk > 0) {
822 823 824 825
    first_page_ = Isolate::Current()->memory_allocator()->CommitPages(
        RoundUp(start, Page::kPageSize),
        Page::kPageSize * pages_in_chunk,
        this, &num_pages);
826
  } else {
827 828 829
    int requested_pages =
        Min(MemoryAllocator::kPagesPerChunk,
            static_cast<int>(max_capacity_ / Page::kObjectAreaSize));
830
    first_page_ =
831 832
        Isolate::Current()->memory_allocator()->AllocatePages(
            requested_pages, &num_pages, this);
833 834 835 836 837 838 839 840 841 842
    if (!first_page_->is_valid()) return false;
  }

  // We are sure that the first page is valid and that we have at least one
  // page.
  ASSERT(first_page_->is_valid());
  ASSERT(num_pages > 0);
  accounting_stats_.ExpandSpace(num_pages * Page::kObjectAreaSize);
  ASSERT(Capacity() <= max_capacity_);

843
  // Sequentially clear region marks in the newly allocated
844
  // pages and cache the current last page in the space.
845
  for (Page* p = first_page_; p->is_valid(); p = p->next_page()) {
846
    p->SetRegionMarks(Page::kAllRegionsCleanMarks);
847
    last_page_ = p;
848 849 850 851 852
  }

  // Use first_page_ for allocation.
  SetAllocationInfo(&allocation_info_, first_page_);

853 854
  page_list_is_chunk_ordered_ = true;

855 856 857 858 859 860 861 862 863 864
  return true;
}


bool PagedSpace::HasBeenSetup() {
  return (Capacity() > 0);
}


void PagedSpace::TearDown() {
865
  Isolate::Current()->memory_allocator()->FreeAllPages(this);
866
  first_page_ = NULL;
867 868 869 870
  accounting_stats_.Clear();
}


871 872 873 874 875
#ifdef ENABLE_HEAP_PROTECTION

void PagedSpace::Protect() {
  Page* page = first_page_;
  while (page->is_valid()) {
876 877 878
    Isolate::Current()->memory_allocator()->ProtectChunkFromPage(page);
    page = Isolate::Current()->memory_allocator()->
        FindLastPageInSameChunk(page)->next_page();
879 880 881 882 883 884 885
  }
}


void PagedSpace::Unprotect() {
  Page* page = first_page_;
  while (page->is_valid()) {
886 887 888
    Isolate::Current()->memory_allocator()->UnprotectChunkFromPage(page);
    page = Isolate::Current()->memory_allocator()->
        FindLastPageInSameChunk(page)->next_page();
889 890 891 892 893 894
  }
}

#endif


895
void PagedSpace::MarkAllPagesClean() {
896 897
  PageIterator it(this, PageIterator::ALL_PAGES);
  while (it.has_next()) {
898
    it.next()->SetRegionMarks(Page::kAllRegionsCleanMarks);
899 900 901 902
  }
}


903
MaybeObject* PagedSpace::FindObject(Address addr) {
904 905
  // Note: this function can only be called before or after mark-compact GC
  // because it accesses map pointers.
906
  ASSERT(!heap()->mark_compact_collector()->in_use());
907 908 909 910

  if (!Contains(addr)) return Failure::Exception();

  Page* p = Page::FromAddress(addr);
911
  ASSERT(IsUsed(p));
912 913 914 915 916 917 918 919 920
  Address cur = p->ObjectAreaStart();
  Address end = p->AllocationTop();
  while (cur < end) {
    HeapObject* obj = HeapObject::FromAddress(cur);
    Address next = cur + obj->Size();
    if ((cur <= addr) && (addr < next)) return obj;
    cur = next;
  }

921
  UNREACHABLE();
922 923 924 925
  return Failure::Exception();
}


926 927 928 929 930 931 932 933 934
bool PagedSpace::IsUsed(Page* page) {
  PageIterator it(this, PageIterator::PAGES_IN_USE);
  while (it.has_next()) {
    if (page == it.next()) return true;
  }
  return false;
}


935 936 937
void PagedSpace::SetAllocationInfo(AllocationInfo* alloc_info, Page* p) {
  alloc_info->top = p->ObjectAreaStart();
  alloc_info->limit = p->ObjectAreaEnd();
938
  ASSERT(alloc_info->VerifyPagedAllocation());
939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979
}


void PagedSpace::MCResetRelocationInfo() {
  // Set page indexes.
  int i = 0;
  PageIterator it(this, PageIterator::ALL_PAGES);
  while (it.has_next()) {
    Page* p = it.next();
    p->mc_page_index = i++;
  }

  // Set mc_forwarding_info_ to the first page in the space.
  SetAllocationInfo(&mc_forwarding_info_, first_page_);
  // All the bytes in the space are 'available'.  We will rediscover
  // allocated and wasted bytes during GC.
  accounting_stats_.Reset();
}


int PagedSpace::MCSpaceOffsetForAddress(Address addr) {
#ifdef DEBUG
  // The Contains function considers the address at the beginning of a
  // page in the page, MCSpaceOffsetForAddress considers it is in the
  // previous page.
  if (Page::IsAlignedToPageSize(addr)) {
    ASSERT(Contains(addr - kPointerSize));
  } else {
    ASSERT(Contains(addr));
  }
#endif

  // If addr is at the end of a page, it belongs to previous page
  Page* p = Page::IsAlignedToPageSize(addr)
            ? Page::FromAllocationTop(addr)
            : Page::FromAddress(addr);
  int index = p->mc_page_index;
  return (index * Page::kPageSize) + p->Offset(addr);
}


980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000
// Slow case for reallocating and promoting objects during a compacting
// collection.  This function is not space-specific.
HeapObject* PagedSpace::SlowMCAllocateRaw(int size_in_bytes) {
  Page* current_page = TopPageOf(mc_forwarding_info_);
  if (!current_page->next_page()->is_valid()) {
    if (!Expand(current_page)) {
      return NULL;
    }
  }

  // There are surely more pages in the space now.
  ASSERT(current_page->next_page()->is_valid());
  // We do not add the top of page block for current page to the space's
  // free list---the block may contain live objects so we cannot write
  // bookkeeping information to it.  Instead, we will recover top of page
  // blocks when we move objects to their new locations.
  //
  // We do however write the allocation pointer to the page.  The encoding
  // of forwarding addresses is as an offset in terms of live bytes, so we
  // need quick access to the allocation top of each page to decode
  // forwarding addresses.
1001 1002
  current_page->SetAllocationWatermark(mc_forwarding_info_.top);
  current_page->next_page()->InvalidateWatermark(true);
1003 1004 1005 1006 1007
  SetAllocationInfo(&mc_forwarding_info_, current_page->next_page());
  return AllocateLinearly(&mc_forwarding_info_, size_in_bytes);
}


1008 1009 1010 1011 1012 1013 1014 1015 1016 1017
bool PagedSpace::Expand(Page* last_page) {
  ASSERT(max_capacity_ % Page::kObjectAreaSize == 0);
  ASSERT(Capacity() % Page::kObjectAreaSize == 0);

  if (Capacity() == max_capacity_) return false;

  ASSERT(Capacity() < max_capacity_);
  // Last page must be valid and its next page is invalid.
  ASSERT(last_page->is_valid() && !last_page->next_page()->is_valid());

1018 1019
  int available_pages =
      static_cast<int>((max_capacity_ - Capacity()) / Page::kObjectAreaSize);
1020 1021 1022 1023
  // We don't want to have to handle small chunks near the end so if there are
  // not kPagesPerChunk pages available without exceeding the max capacity then
  // act as if memory has run out.
  if (available_pages < MemoryAllocator::kPagesPerChunk) return false;
1024 1025

  int desired_pages = Min(available_pages, MemoryAllocator::kPagesPerChunk);
1026 1027
  Page* p = heap()->isolate()->memory_allocator()->AllocatePages(
      desired_pages, &desired_pages, this);
1028 1029 1030 1031 1032
  if (!p->is_valid()) return false;

  accounting_stats_.ExpandSpace(desired_pages * Page::kObjectAreaSize);
  ASSERT(Capacity() <= max_capacity_);

1033
  heap()->isolate()->memory_allocator()->SetNextPage(last_page, p);
1034

1035
  // Sequentially clear region marks of new pages and and cache the
1036
  // new last page in the space.
1037
  while (p->is_valid()) {
1038
    p->SetRegionMarks(Page::kAllRegionsCleanMarks);
1039
    last_page_ = p;
1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058
    p = p->next_page();
  }

  return true;
}


#ifdef DEBUG
int PagedSpace::CountTotalPages() {
  int count = 0;
  for (Page* p = first_page_; p->is_valid(); p = p->next_page()) {
    count++;
  }
  return count;
}
#endif


void PagedSpace::Shrink() {
1059 1060 1061 1062 1063 1064
  if (!page_list_is_chunk_ordered_) {
    // We can't shrink space if pages is not chunk-ordered
    // (see comment for class MemoryAllocator for definition).
    return;
  }

1065 1066 1067 1068
  // Release half of free pages.
  Page* top_page = AllocationTopPage();
  ASSERT(top_page->is_valid());

1069 1070 1071 1072
  // Count the number of pages we would like to free.
  int pages_to_free = 0;
  for (Page* p = top_page->next_page(); p->is_valid(); p = p->next_page()) {
    pages_to_free++;
1073 1074
  }

1075
  // Free pages after top_page.
1076 1077 1078
  Page* p = heap()->isolate()->memory_allocator()->
      FreePages(top_page->next_page());
  heap()->isolate()->memory_allocator()->SetNextPage(top_page, p);
1079

1080 1081 1082 1083 1084
  // Find out how many pages we failed to free and update last_page_.
  // Please note pages can only be freed in whole chunks.
  last_page_ = top_page;
  for (Page* p = top_page->next_page(); p->is_valid(); p = p->next_page()) {
    pages_to_free--;
1085
    last_page_ = p;
1086 1087
  }

1088
  accounting_stats_.ShrinkSpace(pages_to_free * Page::kObjectAreaSize);
1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099
  ASSERT(Capacity() == CountTotalPages() * Page::kObjectAreaSize);
}


bool PagedSpace::EnsureCapacity(int capacity) {
  if (Capacity() >= capacity) return true;

  // Start from the allocation top and loop to the last page in the space.
  Page* last_page = AllocationTopPage();
  Page* next_page = last_page->next_page();
  while (next_page->is_valid()) {
1100 1101
    last_page = heap()->isolate()->memory_allocator()->
        FindLastPageInSameChunk(next_page);
1102 1103 1104 1105 1106 1107 1108 1109
    next_page = last_page->next_page();
  }

  // Expand the space until it has the required capacity or expansion fails.
  do {
    if (!Expand(last_page)) return false;
    ASSERT(last_page->next_page()->is_valid());
    last_page =
1110 1111
        heap()->isolate()->memory_allocator()->FindLastPageInSameChunk(
            last_page->next_page());
1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122
  } while (Capacity() < capacity);

  return true;
}


#ifdef DEBUG
void PagedSpace::Print() { }
#endif


1123 1124 1125 1126 1127 1128 1129 1130
#ifdef DEBUG
// We do not assume that the PageIterator works, because it depends on the
// invariants we are checking during verification.
void PagedSpace::Verify(ObjectVisitor* visitor) {
  // The allocation pointer should be valid, and it should be in a page in the
  // space.
  ASSERT(allocation_info_.VerifyPagedAllocation());
  Page* top_page = Page::FromAllocationTop(allocation_info_.top);
1131
  ASSERT(heap()->isolate()->memory_allocator()->IsPageInSpace(top_page, this));
1132 1133 1134 1135 1136 1137 1138 1139 1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155

  // Loop over all the pages.
  bool above_allocation_top = false;
  Page* current_page = first_page_;
  while (current_page->is_valid()) {
    if (above_allocation_top) {
      // We don't care what's above the allocation top.
    } else {
      Address top = current_page->AllocationTop();
      if (current_page == top_page) {
        ASSERT(top == allocation_info_.top);
        // The next page will be above the allocation top.
        above_allocation_top = true;
      }

      // It should be packed with objects from the bottom to the top.
      Address current = current_page->ObjectAreaStart();
      while (current < top) {
        HeapObject* object = HeapObject::FromAddress(current);

        // The first word should be a map, and we expect all map pointers to
        // be in map space.
        Map* map = object->map();
        ASSERT(map->IsMap());
1156
        ASSERT(heap()->map_space()->Contains(map));
1157 1158 1159 1160 1161 1162 1163 1164

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

        // The object itself should look OK.
        object->Verify();

        // All the interior pointers should be contained in the heap and
1165 1166
        // have page regions covering intergenerational references should be
        // marked dirty.
1167
        int size = object->Size();
1168
        object->IterateBody(map->instance_type(), size, visitor);
1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182

        current += size;
      }

      // The allocation pointer should not be in the middle of an object.
      ASSERT(current == top);
    }

    current_page = current_page->next_page();
  }
}
#endif


1183 1184 1185
// -----------------------------------------------------------------------------
// NewSpace implementation

1186 1187 1188 1189 1190 1191

bool NewSpace::Setup(Address start, int size) {
  // Setup new space based on the preallocated memory block defined by
  // start and size. The provided space is divided into two semi-spaces.
  // To support fast containment testing in the new space, the size of
  // this chunk must be a power of two and it must be aligned to its size.
1192 1193
  int initial_semispace_capacity = heap()->InitialSemiSpaceSize();
  int maximum_semispace_capacity = heap()->MaxSemiSpaceSize();
1194

1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208
  ASSERT(initial_semispace_capacity <= maximum_semispace_capacity);
  ASSERT(IsPowerOf2(maximum_semispace_capacity));

  // Allocate and setup the histogram arrays if necessary.
#if defined(DEBUG) || defined(ENABLE_LOGGING_AND_PROFILING)
  allocated_histogram_ = NewArray<HistogramInfo>(LAST_TYPE + 1);
  promoted_histogram_ = NewArray<HistogramInfo>(LAST_TYPE + 1);

#define SET_NAME(name) allocated_histogram_[name].set_name(#name); \
                       promoted_histogram_[name].set_name(#name);
  INSTANCE_TYPE_LIST(SET_NAME)
#undef SET_NAME
#endif

1209
  ASSERT(size == 2 * heap()->ReservedSemiSpaceSize());
1210 1211
  ASSERT(IsAddressAligned(start, size, 0));

1212 1213 1214
  if (!to_space_.Setup(start,
                       initial_semispace_capacity,
                       maximum_semispace_capacity)) {
1215 1216
    return false;
  }
1217 1218 1219
  if (!from_space_.Setup(start + maximum_semispace_capacity,
                         initial_semispace_capacity,
                         maximum_semispace_capacity)) {
1220 1221 1222 1223 1224
    return false;
  }

  start_ = start;
  address_mask_ = ~(size - 1);
1225
  object_mask_ = address_mask_ | kHeapObjectTagMask;
1226
  object_expected_ = reinterpret_cast<uintptr_t>(start) | kHeapObjectTag;
1227

1228 1229
  allocation_info_.top = to_space_.low();
  allocation_info_.limit = to_space_.high();
1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255
  mc_forwarding_info_.top = NULL;
  mc_forwarding_info_.limit = NULL;

  ASSERT_SEMISPACE_ALLOCATION_INFO(allocation_info_, to_space_);
  return true;
}


void NewSpace::TearDown() {
#if defined(DEBUG) || defined(ENABLE_LOGGING_AND_PROFILING)
  if (allocated_histogram_) {
    DeleteArray(allocated_histogram_);
    allocated_histogram_ = NULL;
  }
  if (promoted_histogram_) {
    DeleteArray(promoted_histogram_);
    promoted_histogram_ = NULL;
  }
#endif

  start_ = NULL;
  allocation_info_.top = NULL;
  allocation_info_.limit = NULL;
  mc_forwarding_info_.top = NULL;
  mc_forwarding_info_.limit = NULL;

1256 1257
  to_space_.TearDown();
  from_space_.TearDown();
1258 1259 1260
}


1261 1262 1263
#ifdef ENABLE_HEAP_PROTECTION

void NewSpace::Protect() {
1264 1265
  heap()->isolate()->memory_allocator()->Protect(ToSpaceLow(), Capacity());
  heap()->isolate()->memory_allocator()->Protect(FromSpaceLow(), Capacity());
1266 1267 1268 1269
}


void NewSpace::Unprotect() {
1270 1271 1272 1273
  heap()->isolate()->memory_allocator()->Unprotect(ToSpaceLow(), Capacity(),
                                                   to_space_.executable());
  heap()->isolate()->memory_allocator()->Unprotect(FromSpaceLow(), Capacity(),
                                                   from_space_.executable());
1274 1275 1276 1277 1278
}

#endif


1279
void NewSpace::Flip() {
1280
  SemiSpace tmp = from_space_;
1281 1282 1283 1284 1285
  from_space_ = to_space_;
  to_space_ = tmp;
}


1286
void NewSpace::Grow() {
1287
  ASSERT(Capacity() < MaximumCapacity());
1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305
  if (to_space_.Grow()) {
    // Only grow from space if we managed to grow to space.
    if (!from_space_.Grow()) {
      // If we managed to grow to space but couldn't grow from space,
      // attempt to shrink to space.
      if (!to_space_.ShrinkTo(from_space_.Capacity())) {
        // We are in an inconsistent state because we could not
        // commit/uncommit memory from new space.
        V8::FatalProcessOutOfMemory("Failed to grow new space.");
      }
    }
  }
  allocation_info_.limit = to_space_.high();
  ASSERT_SEMISPACE_ALLOCATION_INFO(allocation_info_, to_space_);
}


void NewSpace::Shrink() {
1306
  int new_capacity = Max(InitialCapacity(), 2 * SizeAsInt());
1307 1308
  int rounded_new_capacity =
      RoundUp(new_capacity, static_cast<int>(OS::AllocateAlignment()));
1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321
  if (rounded_new_capacity < Capacity() &&
      to_space_.ShrinkTo(rounded_new_capacity))  {
    // Only shrink from space if we managed to shrink to space.
    if (!from_space_.ShrinkTo(rounded_new_capacity)) {
      // If we managed to shrink to space but couldn't shrink from
      // space, attempt to grow to space again.
      if (!to_space_.GrowTo(from_space_.Capacity())) {
        // We are in an inconsistent state because we could not
        // commit/uncommit memory from new space.
        V8::FatalProcessOutOfMemory("Failed to shrink new space.");
      }
    }
  }
1322
  allocation_info_.limit = to_space_.high();
1323 1324 1325 1326 1327
  ASSERT_SEMISPACE_ALLOCATION_INFO(allocation_info_, to_space_);
}


void NewSpace::ResetAllocationInfo() {
1328 1329
  allocation_info_.top = to_space_.low();
  allocation_info_.limit = to_space_.high();
1330 1331 1332 1333 1334
  ASSERT_SEMISPACE_ALLOCATION_INFO(allocation_info_, to_space_);
}


void NewSpace::MCResetRelocationInfo() {
1335 1336
  mc_forwarding_info_.top = from_space_.low();
  mc_forwarding_info_.limit = from_space_.high();
1337 1338 1339 1340 1341 1342 1343 1344
  ASSERT_SEMISPACE_ALLOCATION_INFO(mc_forwarding_info_, from_space_);
}


void NewSpace::MCCommitRelocationInfo() {
  // Assumes that the spaces have been flipped so that mc_forwarding_info_ is
  // valid allocation info for the to space.
  allocation_info_.top = mc_forwarding_info_.top;
1345
  allocation_info_.limit = to_space_.high();
1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358
  ASSERT_SEMISPACE_ALLOCATION_INFO(allocation_info_, to_space_);
}


#ifdef DEBUG
// We do not use the SemispaceIterator because verification doesn't assume
// 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.
  ASSERT_SEMISPACE_ALLOCATION_INFO(allocation_info_, to_space_);

  // There should be objects packed in from the low address up to the
  // allocation pointer.
1359
  Address current = to_space_.low();
1360 1361 1362 1363 1364 1365 1366
  while (current < top()) {
    HeapObject* object = HeapObject::FromAddress(current);

    // The first word should be a map, and we expect all map pointers to
    // be in map space.
    Map* map = object->map();
    ASSERT(map->IsMap());
1367
    ASSERT(heap()->map_space()->Contains(map));
1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 1387 1388 1389

    // The object should not be code or a map.
    ASSERT(!object->IsMap());
    ASSERT(!object->IsCode());

    // The object itself should look OK.
    object->Verify();

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

    current += size;
  }

  // The allocation pointer should not be in the middle of an object.
  ASSERT(current == top());
}
#endif


1390 1391
bool SemiSpace::Commit() {
  ASSERT(!is_committed());
1392 1393
  if (!heap()->isolate()->memory_allocator()->CommitBlock(
      start_, capacity_, executable())) {
1394 1395 1396 1397 1398 1399 1400 1401 1402
    return false;
  }
  committed_ = true;
  return true;
}


bool SemiSpace::Uncommit() {
  ASSERT(is_committed());
1403 1404
  if (!heap()->isolate()->memory_allocator()->UncommitBlock(
      start_, capacity_)) {
1405 1406 1407 1408 1409 1410 1411
    return false;
  }
  committed_ = false;
  return true;
}


1412 1413 1414
// -----------------------------------------------------------------------------
// SemiSpace implementation

1415 1416 1417 1418 1419 1420 1421 1422 1423
bool SemiSpace::Setup(Address start,
                      int initial_capacity,
                      int maximum_capacity) {
  // Creates a space in the young generation. The constructor does not
  // allocate memory from the OS.  A SemiSpace is given a contiguous chunk of
  // memory of size 'capacity' when set up, and does not grow or shrink
  // otherwise.  In the mark-compact collector, the memory region of the from
  // space is used as the marking stack. It requires contiguous memory
  // addresses.
1424
  initial_capacity_ = initial_capacity;
1425 1426
  capacity_ = initial_capacity;
  maximum_capacity_ = maximum_capacity;
1427
  committed_ = false;
1428 1429

  start_ = start;
1430
  address_mask_ = ~(maximum_capacity - 1);
1431
  object_mask_ = address_mask_ | kHeapObjectTagMask;
1432
  object_expected_ = reinterpret_cast<uintptr_t>(start) | kHeapObjectTag;
1433
  age_mark_ = start_;
1434 1435

  return Commit();
1436 1437 1438 1439 1440 1441 1442 1443 1444
}


void SemiSpace::TearDown() {
  start_ = NULL;
  capacity_ = 0;
}


1445
bool SemiSpace::Grow() {
1446
  // Double the semispace size but only up to maximum capacity.
1447
  int maximum_extra = maximum_capacity_ - capacity_;
1448
  int extra = Min(RoundUp(capacity_, static_cast<int>(OS::AllocateAlignment())),
1449
                  maximum_extra);
1450 1451
  if (!heap()->isolate()->memory_allocator()->CommitBlock(
      high(), extra, executable())) {
1452 1453
    return false;
  }
1454
  capacity_ += extra;
1455 1456 1457 1458
  return true;
}


1459 1460 1461 1462 1463
bool SemiSpace::GrowTo(int new_capacity) {
  ASSERT(new_capacity <= maximum_capacity_);
  ASSERT(new_capacity > capacity_);
  size_t delta = new_capacity - capacity_;
  ASSERT(IsAligned(delta, OS::AllocateAlignment()));
1464 1465
  if (!heap()->isolate()->memory_allocator()->CommitBlock(
      high(), delta, executable())) {
1466 1467 1468 1469 1470 1471 1472 1473 1474 1475 1476 1477
    return false;
  }
  capacity_ = new_capacity;
  return true;
}


bool SemiSpace::ShrinkTo(int new_capacity) {
  ASSERT(new_capacity >= initial_capacity_);
  ASSERT(new_capacity < capacity_);
  size_t delta = capacity_ - new_capacity;
  ASSERT(IsAligned(delta, OS::AllocateAlignment()));
1478 1479
  if (!heap()->isolate()->memory_allocator()->UncommitBlock(
      high() - delta, delta)) {
1480 1481 1482 1483 1484 1485 1486
    return false;
  }
  capacity_ = new_capacity;
  return true;
}


1487 1488
#ifdef DEBUG
void SemiSpace::Print() { }
1489 1490 1491


void SemiSpace::Verify() { }
1492 1493 1494 1495 1496 1497 1498 1499 1500 1501 1502 1503 1504 1505 1506 1507 1508 1509 1510 1511 1512 1513 1514 1515 1516 1517 1518
#endif


// -----------------------------------------------------------------------------
// SemiSpaceIterator implementation.
SemiSpaceIterator::SemiSpaceIterator(NewSpace* space) {
  Initialize(space, space->bottom(), space->top(), NULL);
}


SemiSpaceIterator::SemiSpaceIterator(NewSpace* space,
                                     HeapObjectCallback size_func) {
  Initialize(space, space->bottom(), space->top(), size_func);
}


SemiSpaceIterator::SemiSpaceIterator(NewSpace* space, Address start) {
  Initialize(space, start, space->top(), NULL);
}


void SemiSpaceIterator::Initialize(NewSpace* space, Address start,
                                   Address end,
                                   HeapObjectCallback size_func) {
  ASSERT(space->ToSpaceContains(start));
  ASSERT(space->ToSpaceLow() <= end
         && end <= space->ToSpaceHigh());
1519
  space_ = &space->to_space_;
1520 1521 1522 1523 1524 1525 1526 1527 1528
  current_ = start;
  limit_ = end;
  size_func_ = size_func;
}


#ifdef DEBUG
// heap_histograms is shared, always clear it before using it.
static void ClearHistograms() {
1529
  Isolate* isolate = Isolate::Current();
1530
  // We reset the name each time, though it hasn't changed.
1531
#define DEF_TYPE_NAME(name) isolate->heap_histograms()[name].set_name(#name);
1532 1533 1534
  INSTANCE_TYPE_LIST(DEF_TYPE_NAME)
#undef DEF_TYPE_NAME

1535
#define CLEAR_HISTOGRAM(name) isolate->heap_histograms()[name].clear();
1536 1537 1538
  INSTANCE_TYPE_LIST(CLEAR_HISTOGRAM)
#undef CLEAR_HISTOGRAM

1539
  isolate->js_spill_information()->Clear();
1540 1541 1542 1543
}


static void ClearCodeKindStatistics() {
1544
  Isolate* isolate = Isolate::Current();
1545
  for (int i = 0; i < Code::NUMBER_OF_KINDS; i++) {
1546
    isolate->code_kind_statistics()[i] = 0;
1547 1548 1549 1550 1551
  }
}


static void ReportCodeKindStatistics() {
1552
  Isolate* isolate = Isolate::Current();
1553
  const char* table[Code::NUMBER_OF_KINDS] = { NULL };
1554 1555 1556 1557 1558 1559 1560 1561

#define CASE(name)                            \
  case Code::name: table[Code::name] = #name; \
  break

  for (int i = 0; i < Code::NUMBER_OF_KINDS; i++) {
    switch (static_cast<Code::Kind>(i)) {
      CASE(FUNCTION);
1562
      CASE(OPTIMIZED_FUNCTION);
1563 1564 1565 1566 1567 1568 1569
      CASE(STUB);
      CASE(BUILTIN);
      CASE(LOAD_IC);
      CASE(KEYED_LOAD_IC);
      CASE(STORE_IC);
      CASE(KEYED_STORE_IC);
      CASE(CALL_IC);
1570
      CASE(KEYED_CALL_IC);
1571
      CASE(TYPE_RECORDING_UNARY_OP_IC);
1572 1573
      CASE(TYPE_RECORDING_BINARY_OP_IC);
      CASE(COMPARE_IC);
1574 1575 1576 1577 1578 1579 1580
    }
  }

#undef CASE

  PrintF("\n   Code kind histograms: \n");
  for (int i = 0; i < Code::NUMBER_OF_KINDS; i++) {
1581 1582 1583
    if (isolate->code_kind_statistics()[i] > 0) {
      PrintF("     %-20s: %10d bytes\n", table[i],
          isolate->code_kind_statistics()[i]);
1584 1585 1586 1587 1588 1589 1590
    }
  }
  PrintF("\n");
}


static int CollectHistogramInfo(HeapObject* obj) {
1591
  Isolate* isolate = Isolate::Current();
1592 1593
  InstanceType type = obj->map()->instance_type();
  ASSERT(0 <= type && type <= LAST_TYPE);
1594 1595 1596
  ASSERT(isolate->heap_histograms()[type].name() != NULL);
  isolate->heap_histograms()[type].increment_number(1);
  isolate->heap_histograms()[type].increment_bytes(obj->Size());
1597 1598

  if (FLAG_collect_heap_spill_statistics && obj->IsJSObject()) {
1599 1600
    JSObject::cast(obj)->IncrementSpillStatistics(
        isolate->js_spill_information());
1601 1602 1603 1604 1605 1606 1607
  }

  return obj->Size();
}


static void ReportHistogram(bool print_spill) {
1608
  Isolate* isolate = Isolate::Current();
1609 1610
  PrintF("\n  Object Histogram:\n");
  for (int i = 0; i <= LAST_TYPE; i++) {
1611
    if (isolate->heap_histograms()[i].number() > 0) {
1612
      PrintF("    %-34s%10d (%10d bytes)\n",
1613 1614 1615
             isolate->heap_histograms()[i].name(),
             isolate->heap_histograms()[i].number(),
             isolate->heap_histograms()[i].bytes());
1616 1617 1618 1619 1620 1621 1622
    }
  }
  PrintF("\n");

  // Summarize string types.
  int string_number = 0;
  int string_bytes = 0;
1623
#define INCREMENT(type, size, name, camel_name)      \
1624 1625
    string_number += isolate->heap_histograms()[type].number(); \
    string_bytes += isolate->heap_histograms()[type].bytes();
1626 1627 1628
  STRING_TYPE_LIST(INCREMENT)
#undef INCREMENT
  if (string_number > 0) {
1629
    PrintF("    %-34s%10d (%10d bytes)\n\n", "STRING_TYPE", string_number,
1630 1631 1632 1633
           string_bytes);
  }

  if (FLAG_collect_heap_spill_statistics && print_spill) {
1634
    isolate->js_spill_information()->Print();
1635 1636 1637 1638 1639 1640 1641 1642 1643 1644 1645 1646 1647 1648 1649 1650 1651 1652 1653 1654 1655 1656
  }
}
#endif  // DEBUG


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

// Because the copying collector does not touch garbage objects, we iterate
// the new space before a collection to get a histogram of allocated objects.
// This only happens (1) when compiled with DEBUG and the --heap-stats flag is
// set, or when compiled with ENABLE_LOGGING_AND_PROFILING and the --log-gc
// flag is set.
void NewSpace::CollectStatistics() {
  ClearHistograms();
  SemiSpaceIterator it(this);
1657 1658
  for (HeapObject* obj = it.next(); obj != NULL; obj = it.next())
    RecordAllocation(obj);
1659 1660 1661 1662
}


#ifdef ENABLE_LOGGING_AND_PROFILING
1663 1664 1665
static void DoReportStatistics(Isolate* isolate,
                               HistogramInfo* info, const char* description) {
  LOG(isolate, HeapSampleBeginEvent("NewSpace", description));
1666 1667 1668
  // Lump all the string types together.
  int string_number = 0;
  int string_bytes = 0;
1669 1670
#define INCREMENT(type, size, name, camel_name)       \
    string_number += info[type].number();             \
1671 1672 1673 1674
    string_bytes += info[type].bytes();
  STRING_TYPE_LIST(INCREMENT)
#undef INCREMENT
  if (string_number > 0) {
1675 1676
    LOG(isolate,
        HeapSampleItemEvent("STRING_TYPE", string_number, string_bytes));
1677 1678 1679 1680 1681
  }

  // Then do the other types.
  for (int i = FIRST_NONSTRING_TYPE; i <= LAST_TYPE; ++i) {
    if (info[i].number() > 0) {
1682 1683
      LOG(isolate,
          HeapSampleItemEvent(info[i].name(), info[i].number(),
1684 1685 1686
                              info[i].bytes()));
    }
  }
1687
  LOG(isolate, HeapSampleEndEvent("NewSpace", description));
1688 1689 1690 1691 1692 1693 1694 1695
}
#endif  // ENABLE_LOGGING_AND_PROFILING


void NewSpace::ReportStatistics() {
#ifdef DEBUG
  if (FLAG_heap_stats) {
    float pct = static_cast<float>(Available()) / Capacity();
1696 1697
    PrintF("  capacity: %" V8_PTR_PREFIX "d"
               ", available: %" V8_PTR_PREFIX "d, %%%d\n",
1698 1699 1700 1701
           Capacity(), Available(), static_cast<int>(pct*100));
    PrintF("\n  Object Histogram:\n");
    for (int i = 0; i <= LAST_TYPE; i++) {
      if (allocated_histogram_[i].number() > 0) {
1702
        PrintF("    %-34s%10d (%10d bytes)\n",
1703 1704 1705 1706 1707 1708 1709 1710 1711 1712 1713
               allocated_histogram_[i].name(),
               allocated_histogram_[i].number(),
               allocated_histogram_[i].bytes());
      }
    }
    PrintF("\n");
  }
#endif  // DEBUG

#ifdef ENABLE_LOGGING_AND_PROFILING
  if (FLAG_log_gc) {
1714 1715 1716
    Isolate* isolate = ISOLATE;
    DoReportStatistics(isolate, allocated_histogram_, "allocated");
    DoReportStatistics(isolate, promoted_histogram_, "promoted");
1717 1718 1719 1720 1721 1722 1723 1724 1725 1726 1727 1728 1729 1730 1731 1732 1733 1734 1735 1736 1737 1738 1739 1740 1741
  }
#endif  // ENABLE_LOGGING_AND_PROFILING
}


void NewSpace::RecordAllocation(HeapObject* obj) {
  InstanceType type = obj->map()->instance_type();
  ASSERT(0 <= type && type <= LAST_TYPE);
  allocated_histogram_[type].increment_number(1);
  allocated_histogram_[type].increment_bytes(obj->Size());
}


void NewSpace::RecordPromotion(HeapObject* obj) {
  InstanceType type = obj->map()->instance_type();
  ASSERT(0 <= type && type <= LAST_TYPE);
  promoted_histogram_[type].increment_number(1);
  promoted_histogram_[type].increment_bytes(obj->Size());
}
#endif  // defined(DEBUG) || defined(ENABLE_LOGGING_AND_PROFILING)


// -----------------------------------------------------------------------------
// Free lists for old object spaces implementation

1742
void FreeListNode::set_size(Heap* heap, int size_in_bytes) {
1743 1744 1745 1746 1747 1748 1749 1750 1751 1752
  ASSERT(size_in_bytes > 0);
  ASSERT(IsAligned(size_in_bytes, kPointerSize));

  // We write a map and possibly size information to the block.  If the block
  // is big enough to be a ByteArray with at least one extra word (the next
  // pointer), we set its map to be the byte array map and its size to an
  // appropriate array length for the desired size from HeapObject::Size().
  // If the block is too small (eg, one or two words), to hold both a size
  // field and a next pointer, we give it a filler map that gives it the
  // correct size.
1753
  if (size_in_bytes > ByteArray::kHeaderSize) {
1754
    set_map(heap->raw_unchecked_byte_array_map());
1755 1756 1757
    // Can't use ByteArray::cast because it fails during deserialization.
    ByteArray* this_as_byte_array = reinterpret_cast<ByteArray*>(this);
    this_as_byte_array->set_length(ByteArray::LengthFor(size_in_bytes));
1758
  } else if (size_in_bytes == kPointerSize) {
1759
    set_map(heap->raw_unchecked_one_pointer_filler_map());
1760
  } else if (size_in_bytes == 2 * kPointerSize) {
1761
    set_map(heap->raw_unchecked_two_pointer_filler_map());
1762 1763 1764
  } else {
    UNREACHABLE();
  }
1765 1766
  // We would like to ASSERT(Size() == size_in_bytes) but this would fail during
  // deserialization because the byte array map is not done yet.
1767 1768 1769
}


1770
Address FreeListNode::next(Heap* heap) {
1771
  ASSERT(IsFreeListNode(this));
1772
  if (map() == heap->raw_unchecked_byte_array_map()) {
1773 1774 1775 1776 1777
    ASSERT(Size() >= kNextOffset + kPointerSize);
    return Memory::Address_at(address() + kNextOffset);
  } else {
    return Memory::Address_at(address() + kPointerSize);
  }
1778 1779 1780
}


1781
void FreeListNode::set_next(Heap* heap, Address next) {
1782
  ASSERT(IsFreeListNode(this));
1783
  if (map() == heap->raw_unchecked_byte_array_map()) {
1784 1785 1786 1787 1788
    ASSERT(Size() >= kNextOffset + kPointerSize);
    Memory::Address_at(address() + kNextOffset) = next;
  } else {
    Memory::Address_at(address() + kPointerSize) = next;
  }
1789 1790 1791
}


1792 1793 1794
OldSpaceFreeList::OldSpaceFreeList(Heap* heap, AllocationSpace owner)
  : heap_(heap),
    owner_(owner) {
1795 1796 1797 1798 1799 1800 1801 1802 1803 1804 1805 1806 1807 1808 1809 1810 1811 1812 1813 1814 1815 1816 1817 1818 1819 1820 1821 1822 1823 1824 1825
  Reset();
}


void OldSpaceFreeList::Reset() {
  available_ = 0;
  for (int i = 0; i < kFreeListsLength; i++) {
    free_[i].head_node_ = NULL;
  }
  needs_rebuild_ = false;
  finger_ = kHead;
  free_[kHead].next_size_ = kEnd;
}


void OldSpaceFreeList::RebuildSizeList() {
  ASSERT(needs_rebuild_);
  int cur = kHead;
  for (int i = cur + 1; i < kFreeListsLength; i++) {
    if (free_[i].head_node_ != NULL) {
      free_[cur].next_size_ = i;
      cur = i;
    }
  }
  free_[cur].next_size_ = kEnd;
  needs_rebuild_ = false;
}


int OldSpaceFreeList::Free(Address start, int size_in_bytes) {
#ifdef DEBUG
1826
  Isolate::Current()->memory_allocator()->ZapBlock(start, size_in_bytes);
1827 1828
#endif
  FreeListNode* node = FreeListNode::FromAddress(start);
1829
  node->set_size(heap_, size_in_bytes);
1830

1831 1832 1833 1834 1835 1836 1837
  // We don't use the freelists in compacting mode.  This makes it more like a
  // GC that only has mark-sweep-compact and doesn't have a mark-sweep
  // collector.
  if (FLAG_always_compact) {
    return size_in_bytes;
  }

1838 1839 1840 1841 1842 1843 1844 1845 1846
  // Early return to drop too-small blocks on the floor (one or two word
  // blocks cannot hold a map pointer, a size field, and a pointer to the
  // next block in the free list).
  if (size_in_bytes < kMinBlockSize) {
    return size_in_bytes;
  }

  // Insert other blocks at the head of an exact free list.
  int index = size_in_bytes >> kPointerSizeLog2;
1847
  node->set_next(heap_, free_[index].head_node_);
1848 1849 1850 1851 1852 1853 1854
  free_[index].head_node_ = node->address();
  available_ += size_in_bytes;
  needs_rebuild_ = true;
  return 0;
}


1855
MaybeObject* OldSpaceFreeList::Allocate(int size_in_bytes, int* wasted_bytes) {
1856 1857 1858 1859 1860 1861 1862 1863 1864 1865
  ASSERT(0 < size_in_bytes);
  ASSERT(size_in_bytes <= kMaxBlockSize);
  ASSERT(IsAligned(size_in_bytes, kPointerSize));

  if (needs_rebuild_) RebuildSizeList();
  int index = size_in_bytes >> kPointerSizeLog2;
  // Check for a perfect fit.
  if (free_[index].head_node_ != NULL) {
    FreeListNode* node = FreeListNode::FromAddress(free_[index].head_node_);
    // If this was the last block of its size, remove the size.
1866 1867
    if ((free_[index].head_node_ = node->next(heap_)) == NULL)
      RemoveSize(index);
1868 1869
    available_ -= size_in_bytes;
    *wasted_bytes = 0;
1870
    ASSERT(!FLAG_always_compact);  // We only use the freelists with mark-sweep.
1871 1872 1873 1874 1875 1876 1877 1878 1879
    return node;
  }
  // Search the size list for the best fit.
  int prev = finger_ < index ? finger_ : kHead;
  int cur = FindSize(index, &prev);
  ASSERT(index < cur);
  if (cur == kEnd) {
    // No large enough size in list.
    *wasted_bytes = 0;
1880
    return Failure::RetryAfterGC(owner_);
1881
  }
1882
  ASSERT(!FLAG_always_compact);  // We only use the freelists with mark-sweep.
1883 1884 1885
  int rem = cur - index;
  int rem_bytes = rem << kPointerSizeLog2;
  FreeListNode* cur_node = FreeListNode::FromAddress(free_[cur].head_node_);
1886
  ASSERT(cur_node->Size() == (cur << kPointerSizeLog2));
1887 1888 1889 1890 1891 1892 1893 1894 1895
  FreeListNode* rem_node = FreeListNode::FromAddress(free_[cur].head_node_ +
                                                     size_in_bytes);
  // Distinguish the cases prev < rem < cur and rem <= prev < cur
  // to avoid many redundant tests and calls to Insert/RemoveSize.
  if (prev < rem) {
    // Simple case: insert rem between prev and cur.
    finger_ = prev;
    free_[prev].next_size_ = rem;
    // If this was the last block of size cur, remove the size.
1896
    if ((free_[cur].head_node_ = cur_node->next(heap_)) == NULL) {
1897 1898 1899 1900 1901
      free_[rem].next_size_ = free_[cur].next_size_;
    } else {
      free_[rem].next_size_ = cur;
    }
    // Add the remainder block.
1902 1903
    rem_node->set_size(heap_, rem_bytes);
    rem_node->set_next(heap_, free_[rem].head_node_);
1904 1905 1906
    free_[rem].head_node_ = rem_node->address();
  } else {
    // If this was the last block of size cur, remove the size.
1907
    if ((free_[cur].head_node_ = cur_node->next(heap_)) == NULL) {
1908 1909 1910 1911 1912
      finger_ = prev;
      free_[prev].next_size_ = free_[cur].next_size_;
    }
    if (rem_bytes < kMinBlockSize) {
      // Too-small remainder is wasted.
1913
      rem_node->set_size(heap_, rem_bytes);
1914 1915 1916 1917 1918
      available_ -= size_in_bytes + rem_bytes;
      *wasted_bytes = rem_bytes;
      return cur_node;
    }
    // Add the remainder block and, if needed, insert its size.
1919 1920
    rem_node->set_size(heap_, rem_bytes);
    rem_node->set_next(heap_, free_[rem].head_node_);
1921
    free_[rem].head_node_ = rem_node->address();
1922
    if (rem_node->next(heap_) == NULL) InsertSize(rem);
1923 1924 1925 1926 1927 1928 1929
  }
  available_ -= size_in_bytes;
  *wasted_bytes = 0;
  return cur_node;
}


1930 1931 1932 1933 1934
void OldSpaceFreeList::MarkNodes() {
  for (int i = 0; i < kFreeListsLength; i++) {
    Address cur_addr = free_[i].head_node_;
    while (cur_addr != NULL) {
      FreeListNode* cur_node = FreeListNode::FromAddress(cur_addr);
1935
      cur_addr = cur_node->next(heap_);
1936 1937 1938 1939 1940 1941
      cur_node->SetMark();
    }
  }
}


1942 1943 1944 1945 1946 1947 1948
#ifdef DEBUG
bool OldSpaceFreeList::Contains(FreeListNode* node) {
  for (int i = 0; i < kFreeListsLength; i++) {
    Address cur_addr = free_[i].head_node_;
    while (cur_addr != NULL) {
      FreeListNode* cur_node = FreeListNode::FromAddress(cur_addr);
      if (cur_node == node) return true;
1949
      cur_addr = cur_node->next(heap_);
1950 1951 1952 1953 1954 1955 1956
    }
  }
  return false;
}
#endif


1957 1958 1959 1960
FixedSizeFreeList::FixedSizeFreeList(Heap* heap,
                                     AllocationSpace owner,
                                     int object_size)
    : heap_(heap), owner_(owner), object_size_(object_size) {
1961 1962 1963 1964
  Reset();
}


1965
void FixedSizeFreeList::Reset() {
1966
  available_ = 0;
1967
  head_ = tail_ = NULL;
1968 1969 1970
}


1971
void FixedSizeFreeList::Free(Address start) {
1972
#ifdef DEBUG
1973
  Isolate::Current()->memory_allocator()->ZapBlock(start, object_size_);
1974
#endif
1975
  // We only use the freelists with mark-sweep.
1976
  ASSERT(!HEAP->mark_compact_collector()->IsCompacting());
1977
  FreeListNode* node = FreeListNode::FromAddress(start);
1978 1979
  node->set_size(heap_, object_size_);
  node->set_next(heap_, NULL);
1980 1981 1982
  if (head_ == NULL) {
    tail_ = head_ = node->address();
  } else {
1983
    FreeListNode::FromAddress(tail_)->set_next(heap_, node->address());
1984 1985
    tail_ = node->address();
  }
1986
  available_ += object_size_;
1987 1988 1989
}


1990
MaybeObject* FixedSizeFreeList::Allocate() {
1991
  if (head_ == NULL) {
1992
    return Failure::RetryAfterGC(owner_);
1993 1994
  }

1995
  ASSERT(!FLAG_always_compact);  // We only use the freelists with mark-sweep.
1996
  FreeListNode* node = FreeListNode::FromAddress(head_);
1997
  head_ = node->next(heap_);
1998
  available_ -= object_size_;
1999 2000 2001 2002
  return node;
}


2003 2004 2005 2006
void FixedSizeFreeList::MarkNodes() {
  Address cur_addr = head_;
  while (cur_addr != NULL && cur_addr != tail_) {
    FreeListNode* cur_node = FreeListNode::FromAddress(cur_addr);
2007
    cur_addr = cur_node->next(heap_);
2008 2009 2010 2011 2012
    cur_node->SetMark();
  }
}


2013 2014 2015 2016
// -----------------------------------------------------------------------------
// OldSpace implementation

void OldSpace::PrepareForMarkCompact(bool will_compact) {
2017 2018 2019
  // Call prepare of the super class.
  PagedSpace::PrepareForMarkCompact(will_compact);

2020 2021 2022 2023 2024 2025 2026 2027 2028 2029 2030 2031 2032 2033 2034
  if (will_compact) {
    // Reset relocation info.  During a compacting collection, everything in
    // the space is considered 'available' and we will rediscover live data
    // and waste during the collection.
    MCResetRelocationInfo();
    ASSERT(Available() == Capacity());
  } else {
    // During a non-compacting collection, everything below the linear
    // allocation pointer is considered allocated (everything above is
    // available) and we will rediscover available and wasted bytes during
    // the collection.
    accounting_stats_.AllocateBytes(free_list_.available());
    accounting_stats_.FillWastedBytes(Waste());
  }

2035
  // Clear the free list before a full GC---it will be rebuilt afterward.
2036 2037 2038 2039 2040 2041 2042 2043
  free_list_.Reset();
}


void OldSpace::MCCommitRelocationInfo() {
  // Update fast allocation info.
  allocation_info_.top = mc_forwarding_info_.top;
  allocation_info_.limit = mc_forwarding_info_.limit;
2044
  ASSERT(allocation_info_.VerifyPagedAllocation());
2045 2046 2047 2048 2049 2050 2051 2052 2053 2054 2055 2056

  // The space is compacted and we haven't yet built free lists or
  // wasted any space.
  ASSERT(Waste() == 0);
  ASSERT(AvailableFree() == 0);

  // Build the free list for the space.
  int computed_size = 0;
  PageIterator it(this, PageIterator::PAGES_USED_BY_MC);
  while (it.has_next()) {
    Page* p = it.next();
    // Space below the relocation pointer is allocated.
2057
    computed_size +=
2058
        static_cast<int>(p->AllocationWatermark() - p->ObjectAreaStart());
2059
    if (it.has_next()) {
2060
      // Free the space at the top of the page.
2061
      int extra_size =
2062
          static_cast<int>(p->ObjectAreaEnd() - p->AllocationWatermark());
2063
      if (extra_size > 0) {
2064 2065
        int wasted_bytes = free_list_.Free(p->AllocationWatermark(),
                                           extra_size);
2066 2067 2068 2069 2070 2071 2072 2073 2074 2075 2076 2077 2078
        // The bytes we have just "freed" to add to the free list were
        // already accounted as available.
        accounting_stats_.WasteBytes(wasted_bytes);
      }
    }
  }

  // Make sure the computed size - based on the used portion of the pages in
  // use - matches the size obtained while computing forwarding addresses.
  ASSERT(computed_size == Size());
}


2079 2080 2081 2082 2083 2084 2085 2086 2087 2088
bool NewSpace::ReserveSpace(int bytes) {
  // We can't reliably unpack a partial snapshot that needs more new space
  // space than the minimum NewSpace size.
  ASSERT(bytes <= InitialCapacity());
  Address limit = allocation_info_.limit;
  Address top = allocation_info_.top;
  return limit - top >= bytes;
}


2089 2090 2091 2092 2093 2094 2095 2096 2097 2098 2099 2100 2101 2102
void PagedSpace::FreePages(Page* prev, Page* last) {
  if (last == AllocationTopPage()) {
    // Pages are already at the end of used pages.
    return;
  }

  Page* first = NULL;

  // Remove pages from the list.
  if (prev == NULL) {
    first = first_page_;
    first_page_ = last->next_page();
  } else {
    first = prev->next_page();
2103 2104
    heap()->isolate()->memory_allocator()->SetNextPage(
        prev, last->next_page());
2105 2106 2107
  }

  // Attach it after the last page.
2108
  heap()->isolate()->memory_allocator()->SetNextPage(last_page_, first);
2109
  last_page_ = last;
2110
  heap()->isolate()->memory_allocator()->SetNextPage(last, NULL);
2111 2112 2113

  // Clean them up.
  do {
2114 2115 2116 2117
    first->InvalidateWatermark(true);
    first->SetAllocationWatermark(first->ObjectAreaStart());
    first->SetCachedAllocationWatermark(first->ObjectAreaStart());
    first->SetRegionMarks(Page::kAllRegionsCleanMarks);
2118 2119 2120 2121 2122 2123 2124 2125 2126
    first = first->next_page();
  } while (first != NULL);

  // Order of pages in this space might no longer be consistent with
  // order of pages in chunks.
  page_list_is_chunk_ordered_ = false;
}


2127 2128 2129 2130 2131 2132 2133 2134 2135 2136 2137 2138 2139 2140 2141 2142
void PagedSpace::RelinkPageListInChunkOrder(bool deallocate_blocks) {
  const bool add_to_freelist = true;

  // Mark used and unused pages to properly fill unused pages
  // after reordering.
  PageIterator all_pages_iterator(this, PageIterator::ALL_PAGES);
  Page* last_in_use = AllocationTopPage();
  bool in_use = true;

  while (all_pages_iterator.has_next()) {
    Page* p = all_pages_iterator.next();
    p->SetWasInUseBeforeMC(in_use);
    if (p == last_in_use) {
      // We passed a page containing allocation top. All consequent
      // pages are not used.
      in_use = false;
2143
    }
2144
  }
2145

2146 2147 2148
  if (page_list_is_chunk_ordered_) return;

  Page* new_last_in_use = Page::FromAddress(NULL);
2149 2150
  heap()->isolate()->memory_allocator()->RelinkPageListInChunkOrder(
      this, &first_page_, &last_page_, &new_last_in_use);
2151 2152 2153 2154 2155 2156 2157 2158 2159 2160 2161 2162 2163 2164 2165 2166
  ASSERT(new_last_in_use->is_valid());

  if (new_last_in_use != last_in_use) {
    // Current allocation top points to a page which is now in the middle
    // of page list. We should move allocation top forward to the new last
    // used page so various object iterators will continue to work properly.
    int size_in_bytes = static_cast<int>(PageAllocationLimit(last_in_use) -
                                         last_in_use->AllocationTop());

    last_in_use->SetAllocationWatermark(last_in_use->AllocationTop());
    if (size_in_bytes > 0) {
      Address start = last_in_use->AllocationTop();
      if (deallocate_blocks) {
        accounting_stats_.AllocateBytes(size_in_bytes);
        DeallocateBlock(start, size_in_bytes, add_to_freelist);
      } else {
2167
        heap()->CreateFillerObjectAt(start, size_in_bytes);
2168
      }
2169
    }
2170

2171 2172 2173 2174 2175 2176 2177 2178 2179 2180 2181 2182 2183 2184 2185 2186 2187 2188 2189 2190 2191 2192 2193
    // New last in use page was in the middle of the list before
    // sorting so it full.
    SetTop(new_last_in_use->AllocationTop());

    ASSERT(AllocationTopPage() == new_last_in_use);
    ASSERT(AllocationTopPage()->WasInUseBeforeMC());
  }

  PageIterator pages_in_use_iterator(this, PageIterator::PAGES_IN_USE);
  while (pages_in_use_iterator.has_next()) {
    Page* p = pages_in_use_iterator.next();
    if (!p->WasInUseBeforeMC()) {
      // Empty page is in the middle of a sequence of used pages.
      // Allocate it as a whole and deallocate immediately.
      int size_in_bytes = static_cast<int>(PageAllocationLimit(p) -
                                           p->ObjectAreaStart());

      p->SetAllocationWatermark(p->ObjectAreaStart());
      Address start = p->ObjectAreaStart();
      if (deallocate_blocks) {
        accounting_stats_.AllocateBytes(size_in_bytes);
        DeallocateBlock(start, size_in_bytes, add_to_freelist);
      } else {
2194
        heap()->CreateFillerObjectAt(start, size_in_bytes);
2195 2196 2197
      }
    }
  }
2198 2199 2200 2201 2202 2203 2204 2205 2206

  page_list_is_chunk_ordered_ = true;
}


void PagedSpace::PrepareForMarkCompact(bool will_compact) {
  if (will_compact) {
    RelinkPageListInChunkOrder(false);
  }
2207 2208 2209
}


2210 2211 2212 2213 2214 2215 2216 2217 2218 2219 2220 2221 2222
bool PagedSpace::ReserveSpace(int bytes) {
  Address limit = allocation_info_.limit;
  Address top = allocation_info_.top;
  if (limit - top >= bytes) return true;

  // There wasn't enough space in the current page.  Lets put the rest
  // of the page on the free list and start a fresh page.
  PutRestOfCurrentPageOnFreeList(TopPageOf(allocation_info_));

  Page* reserved_page = TopPageOf(allocation_info_);
  int bytes_left_to_reserve = bytes;
  while (bytes_left_to_reserve > 0) {
    if (!reserved_page->next_page()->is_valid()) {
2223
      if (heap()->OldGenerationAllocationLimitReached()) return false;
2224 2225 2226 2227 2228 2229 2230
      Expand(reserved_page);
    }
    bytes_left_to_reserve -= Page::kPageSize;
    reserved_page = reserved_page->next_page();
    if (!reserved_page->is_valid()) return false;
  }
  ASSERT(TopPageOf(allocation_info_)->next_page()->is_valid());
2231
  TopPageOf(allocation_info_)->next_page()->InvalidateWatermark(true);
2232 2233 2234 2235 2236 2237 2238 2239 2240
  SetAllocationInfo(&allocation_info_,
                    TopPageOf(allocation_info_)->next_page());
  return true;
}


// You have to call this last, since the implementation from PagedSpace
// doesn't know that memory was 'promised' to large object space.
bool LargeObjectSpace::ReserveSpace(int bytes) {
2241
  return heap()->OldGenerationSpaceAvailable() >= bytes;
2242 2243 2244
}


2245 2246 2247 2248 2249 2250 2251 2252 2253 2254 2255 2256
// Slow case for normal allocation.  Try in order: (1) allocate in the next
// page in the space, (2) allocate off the space's free list, (3) expand the
// space, (4) fail.
HeapObject* OldSpace::SlowAllocateRaw(int size_in_bytes) {
  // Linear allocation in this space has failed.  If there is another page
  // in the space, move to that page and allocate there.  This allocation
  // should succeed (size_in_bytes should not be greater than a page's
  // object area size).
  Page* current_page = TopPageOf(allocation_info_);
  if (current_page->next_page()->is_valid()) {
    return AllocateInNextPage(current_page, size_in_bytes);
  }
2257

2258 2259
  // There is no next page in this space.  Try free list allocation unless that
  // is currently forbidden.
2260
  if (!heap()->linear_allocation()) {
2261
    int wasted_bytes;
2262 2263
    Object* result;
    MaybeObject* maybe = free_list_.Allocate(size_in_bytes, &wasted_bytes);
2264
    accounting_stats_.WasteBytes(wasted_bytes);
2265
    if (maybe->ToObject(&result)) {
2266
      accounting_stats_.AllocateBytes(size_in_bytes);
2267 2268 2269 2270 2271 2272 2273 2274 2275 2276 2277 2278 2279 2280

      HeapObject* obj = HeapObject::cast(result);
      Page* p = Page::FromAddress(obj->address());

      if (obj->address() >= p->AllocationWatermark()) {
        // There should be no hole between the allocation watermark
        // and allocated object address.
        // Memory above the allocation watermark was not swept and
        // might contain garbage pointers to new space.
        ASSERT(obj->address() == p->AllocationWatermark());
        p->SetAllocationWatermark(obj->address() + size_in_bytes);
      }

      return obj;
2281
    }
2282
  }
2283

2284 2285 2286
  // Free list allocation failed and there is no next page.  Fail if we have
  // hit the old generation size limit that should cause a garbage
  // collection.
2287 2288
  if (!heap()->always_allocate() &&
      heap()->OldGenerationAllocationLimitReached()) {
2289 2290 2291 2292
    return NULL;
  }

  // Try to expand the space and allocate in the new next page.
2293 2294 2295
  ASSERT(!current_page->next_page()->is_valid());
  if (Expand(current_page)) {
    return AllocateInNextPage(current_page, size_in_bytes);
2296 2297
  }

2298 2299 2300
  // Finally, fail.
  return NULL;
}
2301 2302


2303
void OldSpace::PutRestOfCurrentPageOnFreeList(Page* current_page) {
2304
  current_page->SetAllocationWatermark(allocation_info_.top);
2305 2306
  int free_size =
      static_cast<int>(current_page->ObjectAreaEnd() - allocation_info_.top);
2307 2308 2309
  if (free_size > 0) {
    int wasted_bytes = free_list_.Free(allocation_info_.top, free_size);
    accounting_stats_.WasteBytes(wasted_bytes);
2310
  }
2311 2312 2313 2314
}


void FixedSpace::PutRestOfCurrentPageOnFreeList(Page* current_page) {
2315
  current_page->SetAllocationWatermark(allocation_info_.top);
2316 2317 2318 2319 2320 2321 2322 2323 2324 2325 2326 2327 2328 2329 2330 2331 2332 2333 2334
  int free_size =
      static_cast<int>(current_page->ObjectAreaEnd() - allocation_info_.top);
  // In the fixed space free list all the free list items have the right size.
  // We use up the rest of the page while preserving this invariant.
  while (free_size >= object_size_in_bytes_) {
    free_list_.Free(allocation_info_.top);
    allocation_info_.top += object_size_in_bytes_;
    free_size -= object_size_in_bytes_;
    accounting_stats_.WasteBytes(object_size_in_bytes_);
  }
}


// Add the block at the top of the page to the space's free list, set the
// allocation info to the next page (assumed to be one), and allocate
// linearly there.
HeapObject* OldSpace::AllocateInNextPage(Page* current_page,
                                         int size_in_bytes) {
  ASSERT(current_page->next_page()->is_valid());
2335 2336
  Page* next_page = current_page->next_page();
  next_page->ClearGCFields();
2337
  PutRestOfCurrentPageOnFreeList(current_page);
2338
  SetAllocationInfo(&allocation_info_, next_page);
2339
  return AllocateLinearly(&allocation_info_, size_in_bytes);
2340 2341 2342
}


2343 2344 2345 2346 2347 2348 2349
void OldSpace::DeallocateBlock(Address start,
                                 int size_in_bytes,
                                 bool add_to_freelist) {
  Free(start, size_in_bytes, add_to_freelist);
}


2350 2351
#ifdef DEBUG
void PagedSpace::ReportCodeStatistics() {
2352 2353 2354
  Isolate* isolate = Isolate::Current();
  CommentStatistic* comments_statistics =
      isolate->paged_space_comments_statistics();
2355 2356 2357
  ReportCodeKindStatistics();
  PrintF("Code comment statistics (\"   [ comment-txt   :    size/   "
         "count  (average)\"):\n");
2358
  for (int i = 0; i <= CommentStatistic::kMaxComments; i++) {
2359 2360 2361 2362 2363 2364 2365 2366 2367 2368 2369
    const CommentStatistic& cs = comments_statistics[i];
    if (cs.size > 0) {
      PrintF("   %-30s: %10d/%6d     (%d)\n", cs.comment, cs.size, cs.count,
             cs.size/cs.count);
    }
  }
  PrintF("\n");
}


void PagedSpace::ResetCodeStatistics() {
2370 2371 2372
  Isolate* isolate = Isolate::Current();
  CommentStatistic* comments_statistics =
      isolate->paged_space_comments_statistics();
2373
  ClearCodeKindStatistics();
2374 2375 2376 2377 2378 2379
  for (int i = 0; i < CommentStatistic::kMaxComments; i++) {
    comments_statistics[i].Clear();
  }
  comments_statistics[CommentStatistic::kMaxComments].comment = "Unknown";
  comments_statistics[CommentStatistic::kMaxComments].size = 0;
  comments_statistics[CommentStatistic::kMaxComments].count = 0;
2380 2381 2382
}


2383
// Adds comment to 'comment_statistics' table. Performance OK as long as
2384
// 'kMaxComments' is small
2385 2386 2387
static void EnterComment(Isolate* isolate, const char* comment, int delta) {
  CommentStatistic* comments_statistics =
      isolate->paged_space_comments_statistics();
2388 2389
  // Do not count empty comments
  if (delta <= 0) return;
2390
  CommentStatistic* cs = &comments_statistics[CommentStatistic::kMaxComments];
2391 2392
  // Search for a free or matching entry in 'comments_statistics': 'cs'
  // points to result.
2393
  for (int i = 0; i < CommentStatistic::kMaxComments; i++) {
2394 2395 2396 2397 2398 2399 2400 2401 2402 2403 2404 2405 2406 2407 2408 2409 2410
    if (comments_statistics[i].comment == NULL) {
      cs = &comments_statistics[i];
      cs->comment = comment;
      break;
    } else if (strcmp(comments_statistics[i].comment, comment) == 0) {
      cs = &comments_statistics[i];
      break;
    }
  }
  // Update entry for 'comment'
  cs->size += delta;
  cs->count += 1;
}


// Call for each nested comment start (start marked with '[ xxx', end marked
// with ']'.  RelocIterator 'it' must point to a comment reloc info.
2411
static void CollectCommentStatistics(Isolate* isolate, RelocIterator* it) {
2412
  ASSERT(!it->done());
2413
  ASSERT(it->rinfo()->rmode() == RelocInfo::COMMENT);
2414 2415 2416 2417 2418 2419 2420 2421 2422 2423 2424 2425 2426 2427 2428 2429
  const char* tmp = reinterpret_cast<const char*>(it->rinfo()->data());
  if (tmp[0] != '[') {
    // Not a nested comment; skip
    return;
  }

  // Search for end of nested comment or a new nested comment
  const char* const comment_txt =
      reinterpret_cast<const char*>(it->rinfo()->data());
  const byte* prev_pc = it->rinfo()->pc();
  int flat_delta = 0;
  it->next();
  while (true) {
    // All nested comments must be terminated properly, and therefore exit
    // from loop.
    ASSERT(!it->done());
2430
    if (it->rinfo()->rmode() == RelocInfo::COMMENT) {
2431 2432
      const char* const txt =
          reinterpret_cast<const char*>(it->rinfo()->data());
2433
      flat_delta += static_cast<int>(it->rinfo()->pc() - prev_pc);
2434 2435
      if (txt[0] == ']') break;  // End of nested  comment
      // A new comment
2436
      CollectCommentStatistics(isolate, it);
2437 2438 2439 2440 2441
      // Skip code that was covered with previous comment
      prev_pc = it->rinfo()->pc();
    }
    it->next();
  }
2442
  EnterComment(isolate, comment_txt, flat_delta);
2443 2444 2445 2446 2447 2448 2449
}


// Collects code size statistics:
// - by code kind
// - by code comment
void PagedSpace::CollectCodeStatistics() {
2450
  Isolate* isolate = heap()->isolate();
2451
  HeapObjectIterator obj_it(this);
2452
  for (HeapObject* obj = obj_it.next(); obj != NULL; obj = obj_it.next()) {
2453 2454
    if (obj->IsCode()) {
      Code* code = Code::cast(obj);
2455
      isolate->code_kind_statistics()[code->kind()] += code->Size();
2456 2457 2458 2459
      RelocIterator it(code);
      int delta = 0;
      const byte* prev_pc = code->instruction_start();
      while (!it.done()) {
2460
        if (it.rinfo()->rmode() == RelocInfo::COMMENT) {
2461
          delta += static_cast<int>(it.rinfo()->pc() - prev_pc);
2462
          CollectCommentStatistics(isolate, &it);
2463 2464 2465 2466 2467 2468
          prev_pc = it.rinfo()->pc();
        }
        it.next();
      }

      ASSERT(code->instruction_start() <= prev_pc &&
2469 2470
             prev_pc <= code->instruction_end());
      delta += static_cast<int>(code->instruction_end() - prev_pc);
2471
      EnterComment(isolate, "NoComment", delta);
2472 2473 2474 2475 2476 2477
    }
  }
}


void OldSpace::ReportStatistics() {
2478 2479 2480 2481
  int pct = static_cast<int>(Available() * 100 / Capacity());
  PrintF("  capacity: %" V8_PTR_PREFIX "d"
             ", waste: %" V8_PTR_PREFIX "d"
             ", available: %" V8_PTR_PREFIX "d, %%%d\n",
2482 2483 2484 2485
         Capacity(), Waste(), Available(), pct);

  ClearHistograms();
  HeapObjectIterator obj_it(this);
2486 2487
  for (HeapObject* obj = obj_it.next(); obj != NULL; obj = obj_it.next())
    CollectHistogramInfo(obj);
2488 2489 2490 2491 2492
  ReportHistogram(true);
}
#endif

// -----------------------------------------------------------------------------
2493
// FixedSpace implementation
2494

2495
void FixedSpace::PrepareForMarkCompact(bool will_compact) {
2496 2497 2498
  // Call prepare of the super class.
  PagedSpace::PrepareForMarkCompact(will_compact);

2499 2500 2501 2502 2503 2504 2505 2506 2507 2508 2509 2510 2511 2512 2513 2514
  if (will_compact) {
    // Reset relocation info.
    MCResetRelocationInfo();

    // During a compacting collection, everything in the space is considered
    // 'available' (set by the call to MCResetRelocationInfo) and we will
    // rediscover live and wasted bytes during the collection.
    ASSERT(Available() == Capacity());
  } else {
    // During a non-compacting collection, everything below the linear
    // allocation pointer except wasted top-of-page blocks is considered
    // allocated and we will rediscover available bytes during the
    // collection.
    accounting_stats_.AllocateBytes(free_list_.available());
  }

2515
  // Clear the free list before a full GC---it will be rebuilt afterward.
2516 2517 2518 2519
  free_list_.Reset();
}


2520
void FixedSpace::MCCommitRelocationInfo() {
2521 2522 2523
  // Update fast allocation info.
  allocation_info_.top = mc_forwarding_info_.top;
  allocation_info_.limit = mc_forwarding_info_.limit;
2524
  ASSERT(allocation_info_.VerifyPagedAllocation());
2525 2526 2527 2528 2529 2530 2531 2532 2533 2534

  // The space is compacted and we haven't yet wasted any space.
  ASSERT(Waste() == 0);

  // Update allocation_top of each page in use and compute waste.
  int computed_size = 0;
  PageIterator it(this, PageIterator::PAGES_USED_BY_MC);
  while (it.has_next()) {
    Page* page = it.next();
    Address page_top = page->AllocationTop();
2535
    computed_size += static_cast<int>(page_top - page->ObjectAreaStart());
2536
    if (it.has_next()) {
2537 2538
      accounting_stats_.WasteBytes(
          static_cast<int>(page->ObjectAreaEnd() - page_top));
2539
      page->SetAllocationWatermark(page_top);
2540 2541 2542 2543 2544 2545 2546 2547 2548
    }
  }

  // Make sure the computed size - based on the used portion of the
  // pages in use - matches the size we adjust during allocation.
  ASSERT(computed_size == Size());
}


2549 2550 2551
// Slow case for normal allocation. Try in order: (1) allocate in the next
// page in the space, (2) allocate off the space's free list, (3) expand the
// space, (4) fail.
2552 2553
HeapObject* FixedSpace::SlowAllocateRaw(int size_in_bytes) {
  ASSERT_EQ(object_size_in_bytes_, size_in_bytes);
2554 2555 2556 2557 2558 2559 2560
  // Linear allocation in this space has failed.  If there is another page
  // in the space, move to that page and allocate there.  This allocation
  // should succeed.
  Page* current_page = TopPageOf(allocation_info_);
  if (current_page->next_page()->is_valid()) {
    return AllocateInNextPage(current_page, size_in_bytes);
  }
2561

2562 2563 2564
  // There is no next page in this space.  Try free list allocation unless
  // that is currently forbidden.  The fixed space free list implicitly assumes
  // that all free blocks are of the fixed size.
2565
  if (!heap()->linear_allocation()) {
2566 2567 2568
    Object* result;
    MaybeObject* maybe = free_list_.Allocate();
    if (maybe->ToObject(&result)) {
2569
      accounting_stats_.AllocateBytes(size_in_bytes);
2570 2571 2572 2573 2574 2575 2576 2577 2578 2579 2580 2581 2582
      HeapObject* obj = HeapObject::cast(result);
      Page* p = Page::FromAddress(obj->address());

      if (obj->address() >= p->AllocationWatermark()) {
        // There should be no hole between the allocation watermark
        // and allocated object address.
        // Memory above the allocation watermark was not swept and
        // might contain garbage pointers to new space.
        ASSERT(obj->address() == p->AllocationWatermark());
        p->SetAllocationWatermark(obj->address() + size_in_bytes);
      }

      return obj;
2583 2584 2585
    }
  }

2586 2587 2588
  // Free list allocation failed and there is no next page.  Fail if we have
  // hit the old generation size limit that should cause a garbage
  // collection.
2589 2590
  if (!heap()->always_allocate() &&
      heap()->OldGenerationAllocationLimitReached()) {
2591 2592 2593 2594
    return NULL;
  }

  // Try to expand the space and allocate in the new next page.
2595 2596 2597
  ASSERT(!current_page->next_page()->is_valid());
  if (Expand(current_page)) {
    return AllocateInNextPage(current_page, size_in_bytes);
2598 2599
  }

2600 2601 2602 2603 2604 2605 2606 2607
  // Finally, fail.
  return NULL;
}


// Move to the next page (there is assumed to be one) and allocate there.
// The top of page block is always wasted, because it is too small to hold a
// map.
2608 2609
HeapObject* FixedSpace::AllocateInNextPage(Page* current_page,
                                           int size_in_bytes) {
2610
  ASSERT(current_page->next_page()->is_valid());
2611
  ASSERT(allocation_info_.top == PageAllocationLimit(current_page));
2612
  ASSERT_EQ(object_size_in_bytes_, size_in_bytes);
2613 2614 2615
  Page* next_page = current_page->next_page();
  next_page->ClearGCFields();
  current_page->SetAllocationWatermark(allocation_info_.top);
2616
  accounting_stats_.WasteBytes(page_extra_);
2617
  SetAllocationInfo(&allocation_info_, next_page);
2618
  return AllocateLinearly(&allocation_info_, size_in_bytes);
2619 2620 2621
}


2622 2623 2624 2625 2626 2627 2628 2629 2630 2631 2632 2633 2634 2635 2636
void FixedSpace::DeallocateBlock(Address start,
                                 int size_in_bytes,
                                 bool add_to_freelist) {
  // Free-list elements in fixed space are assumed to have a fixed size.
  // We break the free block into chunks and add them to the free list
  // individually.
  int size = object_size_in_bytes();
  ASSERT(size_in_bytes % size == 0);
  Address end = start + size_in_bytes;
  for (Address a = start; a < end; a += size) {
    Free(a, add_to_freelist);
  }
}


2637
#ifdef DEBUG
2638
void FixedSpace::ReportStatistics() {
2639 2640 2641 2642
  int pct = static_cast<int>(Available() * 100 / Capacity());
  PrintF("  capacity: %" V8_PTR_PREFIX "d"
             ", waste: %" V8_PTR_PREFIX "d"
             ", available: %" V8_PTR_PREFIX "d, %%%d\n",
2643 2644 2645 2646
         Capacity(), Waste(), Available(), pct);

  ClearHistograms();
  HeapObjectIterator obj_it(this);
2647 2648
  for (HeapObject* obj = obj_it.next(); obj != NULL; obj = obj_it.next())
    CollectHistogramInfo(obj);
2649 2650
  ReportHistogram(false);
}
2651 2652 2653 2654 2655 2656 2657 2658 2659 2660 2661 2662 2663 2664 2665 2666 2667 2668 2669 2670 2671 2672 2673 2674 2675 2676 2677 2678 2679 2680 2681 2682 2683 2684 2685 2686 2687 2688 2689 2690 2691
#endif


// -----------------------------------------------------------------------------
// MapSpace implementation

void MapSpace::PrepareForMarkCompact(bool will_compact) {
  // Call prepare of the super class.
  FixedSpace::PrepareForMarkCompact(will_compact);

  if (will_compact) {
    // Initialize map index entry.
    int page_count = 0;
    PageIterator it(this, PageIterator::ALL_PAGES);
    while (it.has_next()) {
      ASSERT_MAP_PAGE_INDEX(page_count);

      Page* p = it.next();
      ASSERT(p->mc_page_index == page_count);

      page_addresses_[page_count++] = p->address();
    }
  }
}


#ifdef DEBUG
void MapSpace::VerifyObject(HeapObject* object) {
  // The object should be a map or a free-list node.
  ASSERT(object->IsMap() || object->IsByteArray());
}
#endif


// -----------------------------------------------------------------------------
// GlobalPropertyCellSpace implementation

#ifdef DEBUG
void CellSpace::VerifyObject(HeapObject* object) {
  // The object should be a global object property cell or a free-list node.
  ASSERT(object->IsJSGlobalPropertyCell() ||
2692
         object->map() == heap()->two_pointer_filler_map());
2693
}
2694 2695 2696 2697 2698 2699 2700 2701 2702 2703 2704 2705 2706 2707 2708 2709 2710 2711 2712 2713
#endif


// -----------------------------------------------------------------------------
// LargeObjectIterator

LargeObjectIterator::LargeObjectIterator(LargeObjectSpace* space) {
  current_ = space->first_chunk_;
  size_func_ = NULL;
}


LargeObjectIterator::LargeObjectIterator(LargeObjectSpace* space,
                                         HeapObjectCallback size_func) {
  current_ = space->first_chunk_;
  size_func_ = size_func;
}


HeapObject* LargeObjectIterator::next() {
2714 2715
  if (current_ == NULL) return NULL;

2716 2717 2718 2719 2720 2721 2722 2723 2724 2725
  HeapObject* object = current_->GetObject();
  current_ = current_->next();
  return object;
}


// -----------------------------------------------------------------------------
// LargeObjectChunk

LargeObjectChunk* LargeObjectChunk::New(int size_in_bytes,
2726
                                        Executability executable) {
2727
  size_t requested = ChunkSizeFor(size_in_bytes);
2728
  size_t size;
2729 2730 2731
  Isolate* isolate = Isolate::Current();
  void* mem = isolate->memory_allocator()->AllocateRawMemory(
      requested, &size, executable);
2732
  if (mem == NULL) return NULL;
2733 2734 2735 2736 2737

  // The start of the chunk may be overlayed with a page so we have to
  // make sure that the page flags fit in the size field.
  ASSERT((size & Page::kPageFlagMask) == 0);

2738
  LOG(isolate, NewEvent("LargeObjectChunk", mem, size));
2739
  if (size < requested) {
2740 2741 2742
    isolate->memory_allocator()->FreeRawMemory(
        mem, size, executable);
    LOG(isolate, DeleteEvent("LargeObjectChunk", mem));
2743 2744
    return NULL;
  }
2745 2746 2747 2748

  ObjectSpace space = (executable == EXECUTABLE)
      ? kObjectSpaceCodeSpace
      : kObjectSpaceLoSpace;
2749
  isolate->memory_allocator()->PerformAllocationCallback(
2750 2751 2752 2753
      space, kAllocationActionAllocate, size);

  LargeObjectChunk* chunk = reinterpret_cast<LargeObjectChunk*>(mem);
  chunk->size_ = size;
2754
  Page* page = Page::FromAddress(RoundUp(chunk->address(), Page::kPageSize));
2755
  page->heap_ = isolate->heap();
2756
  return chunk;
2757 2758 2759 2760
}


int LargeObjectChunk::ChunkSizeFor(int size_in_bytes) {
2761
  int os_alignment = static_cast<int>(OS::AllocateAlignment());
2762
  if (os_alignment < Page::kPageSize) {
2763
    size_in_bytes += (Page::kPageSize - os_alignment);
2764
  }
2765 2766 2767 2768 2769 2770
  return size_in_bytes + Page::kObjectStartOffset;
}

// -----------------------------------------------------------------------------
// LargeObjectSpace

2771 2772
LargeObjectSpace::LargeObjectSpace(Heap* heap, AllocationSpace id)
    : Space(heap, id, NOT_EXECUTABLE),  // Managed on a per-allocation basis
2773
      first_chunk_(NULL),
2774
      size_(0),
2775 2776
      page_count_(0),
      objects_size_(0) {}
2777 2778 2779 2780 2781 2782


bool LargeObjectSpace::Setup() {
  first_chunk_ = NULL;
  size_ = 0;
  page_count_ = 0;
2783
  objects_size_ = 0;
2784 2785 2786 2787 2788 2789 2790 2791
  return true;
}


void LargeObjectSpace::TearDown() {
  while (first_chunk_ != NULL) {
    LargeObjectChunk* chunk = first_chunk_;
    first_chunk_ = first_chunk_->next();
2792
    LOG(heap()->isolate(), DeleteEvent("LargeObjectChunk", chunk->address()));
2793 2794 2795
    Page* page = Page::FromAddress(RoundUp(chunk->address(), Page::kPageSize));
    Executability executable =
        page->IsPageExecutable() ? EXECUTABLE : NOT_EXECUTABLE;
2796 2797
    ObjectSpace space = kObjectSpaceLoSpace;
    if (executable == EXECUTABLE) space = kObjectSpaceCodeSpace;
2798
    size_t size = chunk->size();
2799 2800 2801 2802
    heap()->isolate()->memory_allocator()->FreeRawMemory(chunk->address(),
                                                         size,
                                                         executable);
    heap()->isolate()->memory_allocator()->PerformAllocationCallback(
2803
        space, kAllocationActionFree, size);
2804 2805 2806 2807
  }

  size_ = 0;
  page_count_ = 0;
2808
  objects_size_ = 0;
2809 2810 2811
}


2812 2813 2814 2815 2816
#ifdef ENABLE_HEAP_PROTECTION

void LargeObjectSpace::Protect() {
  LargeObjectChunk* chunk = first_chunk_;
  while (chunk != NULL) {
2817 2818
    heap()->isolate()->memory_allocator()->Protect(chunk->address(),
                                                   chunk->size());
2819 2820 2821 2822 2823 2824 2825 2826 2827
    chunk = chunk->next();
  }
}


void LargeObjectSpace::Unprotect() {
  LargeObjectChunk* chunk = first_chunk_;
  while (chunk != NULL) {
    bool is_code = chunk->GetObject()->IsCode();
2828 2829
    heap()->isolate()->memory_allocator()->Unprotect(chunk->address(),
        chunk->size(), is_code ? EXECUTABLE : NOT_EXECUTABLE);
2830 2831 2832 2833 2834 2835 2836
    chunk = chunk->next();
  }
}

#endif


2837 2838 2839
MaybeObject* LargeObjectSpace::AllocateRawInternal(int requested_size,
                                                   int object_size,
                                                   Executability executable) {
2840
  ASSERT(0 < object_size && object_size <= requested_size);
2841 2842 2843

  // Check if we want to force a GC before growing the old space further.
  // If so, fail the allocation.
2844 2845
  if (!heap()->always_allocate() &&
      heap()->OldGenerationAllocationLimitReached()) {
2846
    return Failure::RetryAfterGC(identity());
2847 2848
  }

2849
  LargeObjectChunk* chunk = LargeObjectChunk::New(requested_size, executable);
2850
  if (chunk == NULL) {
2851
    return Failure::RetryAfterGC(identity());
2852 2853
  }

2854
  size_ += static_cast<int>(chunk->size());
2855
  objects_size_ += requested_size;
2856 2857 2858 2859
  page_count_++;
  chunk->set_next(first_chunk_);
  first_chunk_ = chunk;

2860
  // Initialize page header.
2861 2862
  Page* page = Page::FromAddress(RoundUp(chunk->address(), Page::kPageSize));
  Address object_address = page->ObjectAreaStart();
2863

2864 2865 2866
  // Clear the low order bit of the second word in the page to flag it as a
  // large object page.  If the chunk_size happened to be written there, its
  // low order bit should already be clear.
2867
  page->SetIsLargeObjectPage(true);
2868
  page->SetIsPageExecutable(executable);
2869
  page->SetRegionMarks(Page::kAllRegionsCleanMarks);
2870 2871 2872 2873
  return HeapObject::FromAddress(object_address);
}


2874
MaybeObject* LargeObjectSpace::AllocateRawCode(int size_in_bytes) {
2875
  ASSERT(0 < size_in_bytes);
2876 2877 2878
  return AllocateRawInternal(size_in_bytes,
                             size_in_bytes,
                             EXECUTABLE);
2879 2880 2881
}


2882
MaybeObject* LargeObjectSpace::AllocateRawFixedArray(int size_in_bytes) {
2883
  ASSERT(0 < size_in_bytes);
2884
  return AllocateRawInternal(size_in_bytes,
2885 2886 2887 2888 2889
                             size_in_bytes,
                             NOT_EXECUTABLE);
}


2890
MaybeObject* LargeObjectSpace::AllocateRaw(int size_in_bytes) {
2891 2892 2893 2894
  ASSERT(0 < size_in_bytes);
  return AllocateRawInternal(size_in_bytes,
                             size_in_bytes,
                             NOT_EXECUTABLE);
2895 2896 2897 2898
}


// GC support
2899
MaybeObject* LargeObjectSpace::FindObject(Address a) {
2900 2901 2902 2903 2904 2905 2906 2907 2908 2909 2910
  for (LargeObjectChunk* chunk = first_chunk_;
       chunk != NULL;
       chunk = chunk->next()) {
    Address chunk_address = chunk->address();
    if (chunk_address <= a && a < chunk_address + chunk->size()) {
      return chunk->GetObject();
    }
  }
  return Failure::Exception();
}

2911 2912 2913 2914 2915 2916 2917 2918 2919 2920 2921 2922 2923 2924 2925 2926

LargeObjectChunk* LargeObjectSpace::FindChunkContainingPc(Address pc) {
  // TODO(853): Change this implementation to only find executable
  // chunks and use some kind of hash-based approach to speed it up.
  for (LargeObjectChunk* chunk = first_chunk_;
       chunk != NULL;
       chunk = chunk->next()) {
    Address chunk_address = chunk->address();
    if (chunk_address <= pc && pc < chunk_address + chunk->size()) {
      return chunk;
    }
  }
  return NULL;
}


2927
void LargeObjectSpace::IterateDirtyRegions(ObjectSlotCallback copy_object) {
vegorov@chromium.org's avatar
vegorov@chromium.org committed
2928 2929 2930 2931 2932 2933 2934
  LargeObjectIterator it(this);
  for (HeapObject* object = it.next(); object != NULL; object = it.next()) {
    // We only have code, sequential strings, or fixed arrays in large
    // object space, and only fixed arrays can possibly contain pointers to
    // the young generation.
    if (object->IsFixedArray()) {
      Page* page = Page::FromAddress(object->address());
2935 2936 2937 2938 2939 2940 2941 2942 2943 2944 2945 2946 2947 2948 2949
      uint32_t marks = page->GetRegionMarks();
      uint32_t newmarks = Page::kAllRegionsCleanMarks;

      if (marks != Page::kAllRegionsCleanMarks) {
        // For a large page a single dirty mark corresponds to several
        // regions (modulo 32). So we treat a large page as a sequence of
        // normal pages of size Page::kPageSize having same dirty marks
        // and subsequently iterate dirty regions on each of these pages.
        Address start = object->address();
        Address end = page->ObjectAreaEnd();
        Address object_end = start + object->Size();

        // Iterate regions of the first normal page covering object.
        uint32_t first_region_number = page->GetRegionNumberForAddress(start);
        newmarks |=
2950 2951 2952 2953 2954
            heap()->IterateDirtyRegions(marks >> first_region_number,
                                        start,
                                        end,
                                        &Heap::IteratePointersInDirtyRegion,
                                        copy_object) << first_region_number;
2955 2956 2957 2958 2959 2960

        start = end;
        end = start + Page::kPageSize;
        while (end <= object_end) {
          // Iterate next 32 regions.
          newmarks |=
2961 2962 2963 2964 2965
              heap()->IterateDirtyRegions(marks,
                                          start,
                                          end,
                                          &Heap::IteratePointersInDirtyRegion,
                                          copy_object);
2966 2967 2968 2969 2970 2971 2972 2973
          start = end;
          end = start + Page::kPageSize;
        }

        if (start != object_end) {
          // Iterate the last piece of an object which is less than
          // Page::kPageSize.
          newmarks |=
2974 2975 2976 2977 2978
              heap()->IterateDirtyRegions(marks,
                                          start,
                                          object_end,
                                          &Heap::IteratePointersInDirtyRegion,
                                          copy_object);
2979 2980 2981
        }

        page->SetRegionMarks(newmarks);
2982 2983 2984 2985 2986 2987 2988 2989 2990 2991 2992
      }
    }
  }
}


void LargeObjectSpace::FreeUnmarkedObjects() {
  LargeObjectChunk* previous = NULL;
  LargeObjectChunk* current = first_chunk_;
  while (current != NULL) {
    HeapObject* object = current->GetObject();
2993 2994
    if (object->IsMarked()) {
      object->ClearMark();
2995
      heap()->mark_compact_collector()->tracer()->decrement_marked_count();
2996 2997 2998
      previous = current;
      current = current->next();
    } else {
2999 3000 3001 3002
      Page* page = Page::FromAddress(RoundUp(current->address(),
                                     Page::kPageSize));
      Executability executable =
          page->IsPageExecutable() ? EXECUTABLE : NOT_EXECUTABLE;
3003 3004 3005 3006 3007 3008 3009 3010 3011 3012 3013 3014
      Address chunk_address = current->address();
      size_t chunk_size = current->size();

      // Cut the chunk out from the chunk list.
      current = current->next();
      if (previous == NULL) {
        first_chunk_ = current;
      } else {
        previous->set_next(current);
      }

      // Free the chunk.
3015 3016
      heap()->mark_compact_collector()->ReportDeleteIfNeeded(
          object, heap()->isolate());
3017 3018
      LiveObjectList::ProcessNonLive(object);

3019
      size_ -= static_cast<int>(chunk_size);
3020
      objects_size_ -= object->Size();
3021
      page_count_--;
3022 3023
      ObjectSpace space = kObjectSpaceLoSpace;
      if (executable == EXECUTABLE) space = kObjectSpaceCodeSpace;
3024 3025 3026 3027 3028 3029
      heap()->isolate()->memory_allocator()->FreeRawMemory(chunk_address,
                                                           chunk_size,
                                                           executable);
      heap()->isolate()->memory_allocator()->PerformAllocationCallback(
          space, kAllocationActionFree, size_);
      LOG(heap()->isolate(), DeleteEvent("LargeObjectChunk", chunk_address));
3030 3031 3032 3033 3034 3035 3036
    }
  }
}


bool LargeObjectSpace::Contains(HeapObject* object) {
  Address address = object->address();
3037
  if (heap()->new_space()->Contains(address)) {
3038 3039
    return false;
  }
3040 3041 3042 3043 3044 3045 3046 3047 3048 3049 3050 3051 3052 3053 3054 3055 3056 3057 3058 3059 3060 3061 3062 3063 3064 3065
  Page* page = Page::FromAddress(address);

  SLOW_ASSERT(!page->IsLargeObjectPage()
              || !FindObject(address)->IsFailure());

  return page->IsLargeObjectPage();
}


#ifdef DEBUG
// We do not assume that the large object iterator works, because it depends
// on the invariants we are checking during verification.
void LargeObjectSpace::Verify() {
  for (LargeObjectChunk* chunk = first_chunk_;
       chunk != NULL;
       chunk = chunk->next()) {
    // 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());
    ASSERT(object->address() == page->ObjectAreaStart());

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

3068 3069 3070 3071 3072 3073
    // We have only code, sequential strings, external strings
    // (sequential strings that have been morphed into external
    // strings), fixed arrays, and byte arrays in large object space.
    ASSERT(object->IsCode() || object->IsSeqString() ||
           object->IsExternalString() || object->IsFixedArray() ||
           object->IsByteArray());
3074 3075

    // The object itself should look OK.
3076
    object->Verify();
3077 3078 3079 3080 3081 3082 3083 3084 3085 3086

    // Byte arrays and strings don't have interior pointers.
    if (object->IsCode()) {
      VerifyPointersVisitor code_visitor;
      object->IterateBody(map->instance_type(),
                          object->Size(),
                          &code_visitor);
    } else if (object->IsFixedArray()) {
      // We loop over fixed arrays ourselves, rather then using the visitor,
      // because the visitor doesn't support the start/offset iteration
3087
      // needed for IsRegionDirty.
3088 3089 3090 3091 3092
      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);
3093
          ASSERT(heap()->Contains(element_object));
3094
          ASSERT(element_object->map()->IsMap());
3095
          if (heap()->InNewSpace(element_object)) {
3096 3097 3098 3099 3100
            Address array_addr = object->address();
            Address element_addr = array_addr + FixedArray::kHeaderSize +
                j * kPointerSize;

            ASSERT(Page::FromAddress(array_addr)->IsRegionDirty(element_addr));
3101 3102 3103 3104 3105 3106 3107 3108 3109 3110
          }
        }
      }
    }
  }
}


void LargeObjectSpace::Print() {
  LargeObjectIterator it(this);
3111 3112
  for (HeapObject* obj = it.next(); obj != NULL; obj = it.next()) {
    obj->Print();
3113 3114 3115 3116 3117
  }
}


void LargeObjectSpace::ReportStatistics() {
3118
  PrintF("  size: %" V8_PTR_PREFIX "d\n", size_);
3119 3120 3121
  int num_objects = 0;
  ClearHistograms();
  LargeObjectIterator it(this);
3122
  for (HeapObject* obj = it.next(); obj != NULL; obj = it.next()) {
3123
    num_objects++;
3124
    CollectHistogramInfo(obj);
3125 3126
  }

3127 3128
  PrintF("  number of objects %d, "
         "size of objects %" V8_PTR_PREFIX "d\n", num_objects, objects_size_);
3129 3130 3131 3132 3133
  if (num_objects > 0) ReportHistogram(false);
}


void LargeObjectSpace::CollectCodeStatistics() {
3134
  Isolate* isolate = heap()->isolate();
3135
  LargeObjectIterator obj_it(this);
3136
  for (HeapObject* obj = obj_it.next(); obj != NULL; obj = obj_it.next()) {
3137 3138
    if (obj->IsCode()) {
      Code* code = Code::cast(obj);
3139
      isolate->code_kind_statistics()[code->kind()] += code->Size();
3140 3141 3142 3143 3144 3145
    }
  }
}
#endif  // DEBUG

} }  // namespace v8::internal