mark-compact.cc.svn-base

Google浏览器V8内核代码

  if (object->IsCode()) LOG(CodeDeleteEvent(object->address()));
}


// Function template that, given a range of addresses (eg, a semispace or a
// paged space page), iterates through the objects in the range to clear
// mark bits and compute and encode forwarding addresses.  As a side effect,
// maximal free chunks are marked so that they can be skipped on subsequent
// sweeps.
//
// The template parameters are an allocation function, a forwarding address
// encoding function, and a function to process non-live objects.
template<MarkCompactCollector::AllocationFunction Alloc,
         MarkCompactCollector::EncodingFunction Encode,
         MarkCompactCollector::ProcessNonLiveFunction ProcessNonLive>
inline void EncodeForwardingAddressesInRange(Address start,
                                             Address end,
                                             int* offset) {
  // The start address of the current free region while sweeping the space.
  // This address is set when a transition from live to non-live objects is
  // encountered.  A value (an encoding of the 'next free region' pointer)
  // is written to memory at this address when a transition from non-live to
  // live objects is encountered.
  Address free_start = NULL;

  // A flag giving the state of the previously swept object.  Initially true
  // to ensure that free_start is initialized to a proper address before
  // trying to write to it.
  bool is_prev_alive = true;

  int object_size;  // Will be set on each iteration of the loop.
  for (Address current = start; current < end; current += object_size) {
    HeapObject* object = HeapObject::FromAddress(current);
    if (object->IsMarked()) {
      object->ClearMark();
      MarkCompactCollector::tracer()->decrement_marked_count();
      object_size = object->Size();

      Object* forwarded = Alloc(object, object_size);
      // Allocation cannot fail, because we are compacting the space.
      ASSERT(!forwarded->IsFailure());
      Encode(object, object_size, forwarded, offset);

#ifdef DEBUG
      if (FLAG_gc_verbose) {
        PrintF("forward %p -> %p.\n", object->address(),
               HeapObject::cast(forwarded)->address());
      }
#endif
      if (!is_prev_alive) {  // Transition from non-live to live.
        EncodeFreeRegion(free_start, current - free_start);
        is_prev_alive = true;
      }
    } else {  // Non-live object.
      object_size = object->Size();
      ProcessNonLive(object);
      if (is_prev_alive) {  // Transition from live to non-live.
        free_start = current;
        is_prev_alive = false;
      }
    }
  }

  // If we ended on a free region, mark it.
  if (!is_prev_alive) EncodeFreeRegion(free_start, end - free_start);
}


// Functions to encode the forwarding pointers in each compactable space.
void MarkCompactCollector::EncodeForwardingAddressesInNewSpace() {
  int ignored;
  EncodeForwardingAddressesInRange<MCAllocateFromNewSpace,
                                   EncodeForwardingAddressInNewSpace,
                                   IgnoreNonLiveObject>(
      Heap::new_space()->bottom(),
      Heap::new_space()->top(),
      &ignored);
}


template<MarkCompactCollector::AllocationFunction Alloc,
         MarkCompactCollector::ProcessNonLiveFunction ProcessNonLive>
void MarkCompactCollector::EncodeForwardingAddressesInPagedSpace(
    PagedSpace* space) {
  PageIterator it(space, PageIterator::PAGES_IN_USE);
  while (it.has_next()) {
    Page* p = it.next();
    // The offset of each live object in the page from the first live object
    // in the page.
    int offset = 0;
    EncodeForwardingAddressesInRange<Alloc,
                                     EncodeForwardingAddressInPagedSpace,
                                     ProcessNonLive>(
        p->ObjectAreaStart(),
        p->AllocationTop(),
        &offset);
  }
}


static void SweepSpace(NewSpace* space) {
  HeapObject* object;
  for (Address current = space->bottom();
       current < space->top();
       current += object->Size()) {
    object = HeapObject::FromAddress(current);
    if (object->IsMarked()) {
      object->ClearMark();
      MarkCompactCollector::tracer()->decrement_marked_count();
    } else {
      // We give non-live objects a map that will correctly give their size,
      // since their existing map might not be live after the collection.
      int size = object->Size();
      if (size >= Array::kHeaderSize) {
        object->set_map(Heap::byte_array_map());
        ByteArray::cast(object)->set_length(ByteArray::LengthFor(size));
      } else {
        ASSERT(size == kPointerSize);
        object->set_map(Heap::one_word_filler_map());
      }
      ASSERT(object->Size() == size);
    }
    // The object is now unmarked for the call to Size() at the top of the
    // loop.
  }
}


static void SweepSpace(PagedSpace* space, DeallocateFunction dealloc) {
  PageIterator it(space, PageIterator::PAGES_IN_USE);
  while (it.has_next()) {
    Page* p = it.next();

    bool is_previous_alive = true;
    Address free_start = NULL;
    HeapObject* object;

    for (Address current = p->ObjectAreaStart();
         current < p->AllocationTop();
         current += object->Size()) {
      object = HeapObject::FromAddress(current);
      if (object->IsMarked()) {
        object->ClearMark();
        MarkCompactCollector::tracer()->decrement_marked_count();
        if (MarkCompactCollector::IsCompacting() && object->IsCode()) {
          // If this is compacting collection marked code objects have had
          // their IC targets converted to objects.
          // They need to be converted back to addresses.
          Code::cast(object)->ConvertICTargetsFromObjectToAddress();
        }
        if (!is_previous_alive) {  // Transition from free to live.
          dealloc(free_start, current - free_start);
          is_previous_alive = true;
        }
      } else {
        if (object->IsCode()) {
          LOG(CodeDeleteEvent(Code::cast(object)->address()));
        }
        if (is_previous_alive) {  // Transition from live to free.
          free_start = current;
          is_previous_alive = false;
        }
      }
      // The object is now unmarked for the call to Size() at the top of the
      // loop.
    }

    // If the last region was not live we need to from free_start to the
    // allocation top in the page.
    if (!is_previous_alive) {
      int free_size = p->AllocationTop() - free_start;
      if (free_size > 0) {
        dealloc(free_start, free_size);
      }
    }
  }
}


void MarkCompactCollector::DeallocateOldPointerBlock(Address start,
                                                     int size_in_bytes) {
  Heap::ClearRSetRange(start, size_in_bytes);
  Heap::old_pointer_space()->Free(start, size_in_bytes);
}


void MarkCompactCollector::DeallocateOldDataBlock(Address start,
                                                  int size_in_bytes) {
  Heap::old_data_space()->Free(start, size_in_bytes);
}


void MarkCompactCollector::DeallocateCodeBlock(Address start,
                                               int size_in_bytes) {
  Heap::code_space()->Free(start, size_in_bytes);
}


void MarkCompactCollector::DeallocateMapBlock(Address start,
                                              int size_in_bytes) {
  // Objects in map space are frequently assumed to have size Map::kSize and a
  // valid map in their first word.  Thus, we break the free block up into
  // chunks and free them separately.
  ASSERT(size_in_bytes % Map::kSize == 0);
  Heap::ClearRSetRange(start, size_in_bytes);
  Address end = start + size_in_bytes;
  for (Address a = start; a < end; a += Map::kSize) {
    Heap::map_space()->Free(a);
  }
}


void MarkCompactCollector::EncodeForwardingAddresses() {
  ASSERT(state_ == ENCODE_FORWARDING_ADDRESSES);
  // Objects in the active semispace of the young generation may be
  // relocated to the inactive semispace (if not promoted).  Set the
  // relocation info to the beginning of the inactive semispace.
  Heap::new_space()->MCResetRelocationInfo();

  // Compute the forwarding pointers in each space.
  EncodeForwardingAddressesInPagedSpace<MCAllocateFromOldPointerSpace,
                                        IgnoreNonLiveObject>(
      Heap::old_pointer_space());

  EncodeForwardingAddressesInPagedSpace<MCAllocateFromOldDataSpace,
                                        IgnoreNonLiveObject>(
      Heap::old_data_space());

  EncodeForwardingAddressesInPagedSpace<MCAllocateFromCodeSpace,
                                        LogNonLiveCodeObject>(
      Heap::code_space());

  // Compute new space next to last after the old and code spaces have been
  // compacted.  Objects in new space can be promoted to old or code space.
  EncodeForwardingAddressesInNewSpace();

  // Compute map space last because computing forwarding addresses
  // overwrites non-live objects.  Objects in the other spaces rely on
  // non-live map pointers to get the sizes of non-live objects.
  EncodeForwardingAddressesInPagedSpace<MCAllocateFromMapSpace,
                                        IgnoreNonLiveObject>(
      Heap::map_space());

  // Write relocation info to the top page, so we can use it later.  This is
  // done after promoting objects from the new space so we get the correct
  // allocation top.
  Heap::old_pointer_space()->MCWriteRelocationInfoToPage();
  Heap::old_data_space()->MCWriteRelocationInfoToPage();
  Heap::code_space()->MCWriteRelocationInfoToPage();
  Heap::map_space()->MCWriteRelocationInfoToPage();
}


void MarkCompactCollector::SweepSpaces() {
  ASSERT(state_ == SWEEP_SPACES);
  ASSERT(!IsCompacting());
  // Noncompacting collections simply sweep the spaces to clear the mark
  // bits and free the nonlive blocks (for old and map spaces).  We sweep
  // the map space last because freeing non-live maps overwrites them and
  // the other spaces rely on possibly non-live maps to get the sizes for
  // non-live objects.
  SweepSpace(Heap::old_pointer_space(), &DeallocateOldPointerBlock);
  SweepSpace(Heap::old_data_space(), &DeallocateOldDataBlock);
  SweepSpace(Heap::code_space(), &DeallocateCodeBlock);
  SweepSpace(Heap::new_space());
  SweepSpace(Heap::map_space(), &DeallocateMapBlock);
}


// Iterate the live objects in a range of addresses (eg, a page or a
// semispace).  The live regions of the range have been linked into a list.
// The first live region is [first_live_start, first_live_end), and the last
// address in the range is top.  The callback function is used to get the
// size of each live object.
int MarkCompactCollector::IterateLiveObjectsInRange(
    Address start,
    Address end,
    HeapObjectCallback size_func) {
  int live_objects = 0;
  Address current = start;
  while (current < end) {
    uint32_t encoded_map = Memory::uint32_at(current);
    if (encoded_map == kSingleFreeEncoding) {
      current += kPointerSize;
    } else if (encoded_map == kMultiFreeEncoding) {
      current += Memory::int_at(current + kIntSize);
    } else {
      live_objects++;
      current += size_func(HeapObject::FromAddress(current));
    }
  }
  return live_objects;
}


int MarkCompactCollector::IterateLiveObjects(NewSpace* space,
                                             HeapObjectCallback size_f) {
  ASSERT(MARK_LIVE_OBJECTS < state_ && state_ <= RELOCATE_OBJECTS);
  return IterateLiveObjectsInRange(space->bottom(), space->top(), size_f);
}


int MarkCompactCollector::IterateLiveObjects(PagedSpace* space,
                                             HeapObjectCallback size_f) {
  ASSERT(MARK_LIVE_OBJECTS < state_ && state_ <= RELOCATE_OBJECTS);
  int total = 0;
  PageIterator it(space, PageIterator::PAGES_IN_USE);
  while (it.has_next()) {
    Page* p = it.next();
    total += IterateLiveObjectsInRange(p->ObjectAreaStart(),
                                       p->AllocationTop(),
                                       size_f);
  }
  return total;
}


#ifdef DEBUG
static int VerifyMapObject(HeapObject* obj) {
  InstanceType type = reinterpret_cast<Map*>(obj)->instance_type();
  ASSERT(FIRST_TYPE <= type && type <= LAST_TYPE);
  return Map::kSize;
}


void MarkCompactCollector::VerifyHeapAfterEncodingForwardingAddresses() {
  AllSpaces spaces;
  while (Space* space = spaces.next()) space->Verify();

  ASSERT(state_ == ENCODE_FORWARDING_ADDRESSES);
  int live_maps = IterateLiveObjects(Heap::map_space(), &VerifyMapObject);
  ASSERT(live_maps == live_map_objects_);

  // Verify page headers in paged spaces.
  PagedSpaces paged_spaces;
  while (PagedSpace* space = paged_spaces.next()) VerifyPageHeaders(space);
}


void MarkCompactCollector::VerifyPageHeaders(PagedSpace* space) {
  PageIterator mc_it(space, PageIterator::PAGES_USED_BY_MC);
  while (mc_it.has_next()) {
    Page* p = mc_it.next();
    Address mc_alloc_top = p->mc_relocation_top;
    ASSERT(p->ObjectAreaStart() <= mc_alloc_top &&
           mc_alloc_top <= p->ObjectAreaEnd());
  }

  int page_count = 0;
  PageIterator it(space, PageIterator::PAGES_IN_USE);
  while (it.has_next()) {
    Page* p = it.next();
    ASSERT(p->mc_page_index == page_count);
    page_count++;

    // first_forwarded could be 'deadbeed' if no live objects in this page
    Address first_forwarded = p->mc_first_forwarded;
    ASSERT(first_forwarded == kZapValue ||
           space->Contains(first_forwarded));
  }
}
#endif


// ----------------------------------------------------------------------------
// Phase 3: Update pointers

// Helper class for updating pointers in HeapObjects.
class UpdatingVisitor: public ObjectVisitor {
 public:
  void VisitPointer(Object** p) {
    UpdatePointer(p);
  }

  void VisitPointers(Object** start, Object** end) {
    // Mark all HeapObject pointers in [start, end)
    for (Object** p = start; p < end; p++) UpdatePointer(p);
  }

 private:
  void UpdatePointer(Object** p) {
    if (!(*p)->IsHeapObject()) return;

    HeapObject* obj = HeapObject::cast(*p);
    Address old_addr = obj->address();
    Address new_addr;
    ASSERT(!Heap::InFromSpace(obj));

    if (Heap::new_space()->Contains(obj)) {
      Address f_addr = Heap::new_space()->FromSpaceLow() +
                       Heap::new_space()->ToSpaceOffsetForAddress(old_addr);
      new_addr = Memory::Address_at(f_addr);

#ifdef DEBUG
      ASSERT(Heap::old_pointer_space()->Contains(new_addr) ||
             Heap::old_data_space()->Contains(new_addr) ||
             Heap::code_space()->Contains(new_addr) ||
             Heap::new_space()->FromSpaceContains(new_addr));

      if (Heap::new_space()->FromSpaceContains(new_addr)) {
        ASSERT(Heap::new_space()->FromSpaceOffsetForAddress(new_addr) <=
               Heap::new_space()->ToSpaceOffsetForAddress(old_addr));
      }
#endif

    } else if (Heap::lo_space()->Contains(obj)) {
      // Don't move objects in the large object space.
      return;

    } else {
      ASSERT(Heap::old_pointer_space()->Contains(obj) ||
             Heap::old_data_space()->Contains(obj) ||
             Heap::code_space()->Contains(obj) ||
             Heap::map_space()->Contains(obj));

      new_addr = MarkCompactCollector::GetForwardingAddressInOldSpace(obj);
      ASSERT(Heap::old_pointer_space()->Contains(new_addr) ||
             Heap::old_data_space()->Contains(new_addr) ||
             Heap::code_space()->Contains(new_addr) ||
             Heap::map_space()->Contains(new_addr));

#ifdef DEBUG
      if (Heap::old_pointer_space()->Contains(obj)) {
        ASSERT(Heap::old_pointer_space()->MCSpaceOffsetForAddress(new_addr) <=
               Heap::old_pointer_space()->MCSpaceOffsetForAddress(old_addr));
      } else if (Heap::old_data_space()->Contains(obj)) {
        ASSERT(Heap::old_data_space()->MCSpaceOffsetForAddress(new_addr) <=
               Heap::old_data_space()->MCSpaceOffsetForAddress(old_addr));
      } else if (Heap::code_space()->Contains(obj)) {
        ASSERT(Heap::code_space()->MCSpaceOffsetForAddress(new_addr) <=
               Heap::code_space()->MCSpaceOffsetForAddress(old_addr));
      } else {
        ASSERT(Heap::map_space()->MCSpaceOffsetForAddress(new_addr) <=
               Heap::map_space()->MCSpaceOffsetForAddress(old_addr));
      }
#endif
    }

    *p = HeapObject::FromAddress(new_addr);

#ifdef DEBUG
    if (FLAG_gc_verbose) {
      PrintF("update %p : %p -> %p\n",
             reinterpret_cast<Address>(p), old_addr, new_addr);
    }