mark-compact.cc.svn-base

Google浏览器V8内核代码

// Copyright 2006-2008 the V8 project authors. All rights reserved.
// 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"

#include "execution.h"
#include "global-handles.h"
#include "ic-inl.h"
#include "mark-compact.h"
#include "stub-cache.h"

namespace v8 { namespace internal {

#ifdef DEBUG
// The verification code used between phases of the m-c collector does not
// currently work.
//
// TODO(1240833): Fix the heap verification code and turn this into a real
// flag.
static const bool FLAG_verify_global_gc = false;
#endif  // DEBUG

// ----------------------------------------------------------------------------
// MarkCompactCollector

bool MarkCompactCollector::compacting_collection_ = false;

int MarkCompactCollector::previous_marked_count_ = 0;
GCTracer* MarkCompactCollector::tracer_ = NULL;


#ifdef DEBUG
MarkCompactCollector::CollectorState MarkCompactCollector::state_ = IDLE;

// Counters used for debugging the marking phase of mark-compact or mark-sweep
// collection.
int MarkCompactCollector::live_bytes_ = 0;
int MarkCompactCollector::live_young_objects_ = 0;
int MarkCompactCollector::live_old_data_objects_ = 0;
int MarkCompactCollector::live_old_pointer_objects_ = 0;
int MarkCompactCollector::live_code_objects_ = 0;
int MarkCompactCollector::live_map_objects_ = 0;
int MarkCompactCollector::live_lo_objects_ = 0;
#endif

void MarkCompactCollector::CollectGarbage(GCTracer* tracer) {
  // Rather than passing the tracer around we stash it in a static member
  // variable.
  tracer_ = tracer;
  Prepare();
  // Prepare has selected whether to compact the old generation or not.
  // Tell the tracer.
  if (IsCompacting()) tracer_->set_is_compacting();

  MarkLiveObjects();

  SweepLargeObjectSpace();

  if (compacting_collection_) {
    EncodeForwardingAddresses();

    UpdatePointers();

    RelocateObjects();

    RebuildRSets();

  } else {
    SweepSpaces();
  }

  Finish();

  // Save the count of marked objects remaining after the collection and
  // null out the GC tracer.
  previous_marked_count_ = tracer_->marked_count();
  ASSERT(previous_marked_count_ == 0);
  tracer_ = NULL;
}


void MarkCompactCollector::Prepare() {
  static const int kFragmentationLimit = 50;  // Percent.
#ifdef DEBUG
  ASSERT(state_ == IDLE);
  state_ = PREPARE_GC;
#endif
  ASSERT(!FLAG_always_compact || !FLAG_never_compact);

  compacting_collection_ = FLAG_always_compact;

  // We compact the old generation if it gets too fragmented (ie, we could
  // recover an expected amount of space by reclaiming the waste and free
  // list blocks).  We always compact when the flag --gc-global is true
  // because objects do not get promoted out of new space on non-compacting
  // GCs.
  if (!compacting_collection_) {
    int old_gen_recoverable = 0;
    int old_gen_used = 0;

    OldSpaces spaces;
    while (OldSpace* space = spaces.next()) {
      old_gen_recoverable += space->Waste() + space->AvailableFree();
      old_gen_used += space->Size();
    }
    int old_gen_fragmentation =
      static_cast<int>((old_gen_recoverable * 100.0) / old_gen_used);
    if (old_gen_fragmentation > kFragmentationLimit) {
      compacting_collection_ = true;
    }
  }

  if (FLAG_never_compact) compacting_collection_ = false;

#ifdef DEBUG
  if (compacting_collection_) {
    // We will write bookkeeping information to the remembered set area
    // starting now.
    Page::set_rset_state(Page::NOT_IN_USE);
  }
#endif

  PagedSpaces spaces;
  while (PagedSpace* space = spaces.next()) {
    space->PrepareForMarkCompact(compacting_collection_);
  }

  Counters::global_objects.Set(0);

#ifdef DEBUG
  live_bytes_ = 0;
  live_young_objects_ = 0;
  live_old_pointer_objects_ = 0;
  live_old_data_objects_ = 0;
  live_code_objects_ = 0;
  live_map_objects_ = 0;
  live_lo_objects_ = 0;
#endif
}


void MarkCompactCollector::Finish() {
#ifdef DEBUG
  ASSERT(state_ == SWEEP_SPACES || state_ == REBUILD_RSETS);
  state_ = IDLE;
#endif
  // The stub cache is not traversed during GC; clear the cache to
  // force lazy re-initialization of it. This must be done after the
  // GC, because it relies on the new address of certain old space
  // objects (empty string, illegal builtin).
  StubCache::Clear();
}


// ----------------------------------------------------------------------------
// Phase 1: tracing and marking live objects.
//   before: all objects are in normal state.
//   after: a live object's map pointer is marked as '00'.

// Marking all live objects in the heap as part of mark-sweep or mark-compact
// collection.  Before marking, all objects are in their normal state.  After
// marking, live objects' map pointers are marked indicating that the object
// has been found reachable.
//
// The marking algorithm is a (mostly) depth-first (because of possible stack
// overflow) traversal of the graph of objects reachable from the roots.  It
// uses an explicit stack of pointers rather than recursion.  The young
// generation's inactive ('from') space is used as a marking stack.  The
// objects in the marking stack are the ones that have been reached and marked
// but their children have not yet been visited.
//
// The marking stack can overflow during traversal.  In that case, we set an
// overflow flag.  When the overflow flag is set, we continue marking objects
// reachable from the objects on the marking stack, but no longer push them on
// the marking stack.  Instead, we mark them as both marked and overflowed.
// When the stack is in the overflowed state, objects marked as overflowed
// have been reached and marked but their children have not been visited yet.
// After emptying the marking stack, we clear the overflow flag and traverse
// the heap looking for objects marked as overflowed, push them on the stack,
// and continue with marking.  This process repeats until all reachable
// objects have been marked.

static MarkingStack marking_stack;


inline HeapObject* ShortCircuitConsString(Object** p) {
  // Optimization: If the heap object pointed to by p is a non-symbol
  // cons string whose right substring is Heap::empty_string, update
  // it in place to its left substring.  Return the updated value.
  //
  // Here we assume that if we change *p, we replace it with a heap object
  // (ie, the left substring of a cons string is always a heap object).
  //
  // The check performed is:
  //   object->IsConsString() && !object->IsSymbol() &&
  //   (ConsString::cast(object)->second() == Heap::empty_string())
  // except the maps for the object and its possible substrings might be
  // marked.
  HeapObject* object = HeapObject::cast(*p);
  MapWord map_word = object->map_word();
  map_word.ClearMark();
  InstanceType type = map_word.ToMap()->instance_type();
  if (type >= FIRST_NONSTRING_TYPE || (type & kIsSymbolMask) != 0) {
    return object;
  }

  StringRepresentationTag rep =
      static_cast<StringRepresentationTag>(type & kStringRepresentationMask);
  if (rep != kConsStringTag) return object;

  Object* second = reinterpret_cast<ConsString*>(object)->second();
  if (reinterpret_cast<String*>(second) != Heap::empty_string()) return object;

  // Since we don't have the object's start, it is impossible to update the
  // remembered set.  Therefore, we only replace the string with its left
  // substring when the remembered set does not change.
  Object* first = reinterpret_cast<ConsString*>(object)->first();
  if (!Heap::InNewSpace(object) && Heap::InNewSpace(first)) return object;

  *p = first;
  return HeapObject::cast(first);
}


// Helper class for marking pointers in HeapObjects.
class MarkingVisitor : public ObjectVisitor {
 public:

  void VisitPointer(Object** p) {
    MarkObjectByPointer(p);
  }

  void VisitPointers(Object** start, Object** end) {
    // Mark all objects pointed to in [start, end).
    const int kMinRangeForMarkingRecursion = 64;
    if (end - start >= kMinRangeForMarkingRecursion) {
      if (VisitUnmarkedObjects(start, end)) return;
      // We are close to a stack overflow, so just mark the objects.
    }
    for (Object** p = start; p < end; p++) MarkObjectByPointer(p);
  }

  void BeginCodeIteration(Code* code) {
    // When iterating over a code object during marking
    // ic targets are derived pointers.
    ASSERT(code->ic_flag() == Code::IC_TARGET_IS_ADDRESS);
  }

  void EndCodeIteration(Code* code) {
    // If this is a compacting collection, set ic targets
    // are pointing to object headers.
    if (IsCompacting()) code->set_ic_flag(Code::IC_TARGET_IS_OBJECT);
  }

  void VisitCodeTarget(RelocInfo* rinfo) {
    ASSERT(RelocInfo::IsCodeTarget(rinfo->rmode()));
    Code* code = CodeFromDerivedPointer(rinfo->target_address());
    if (FLAG_cleanup_ics_at_gc && code->is_inline_cache_stub()) {
      IC::Clear(rinfo->pc());
      // Please note targets for cleared inline cached do not have to be
      // marked since they are contained in Heap::non_monomorphic_cache().
    } else {
      MarkCompactCollector::MarkObject(code);
    }
    if (IsCompacting()) {
      // When compacting we convert the target to a real object pointer.
      code = CodeFromDerivedPointer(rinfo->target_address());
      rinfo->set_target_object(code);
    }
  }

  void VisitDebugTarget(RelocInfo* rinfo) {
    ASSERT(RelocInfo::IsJSReturn(rinfo->rmode()) &&
           rinfo->is_call_instruction());
    HeapObject* code = CodeFromDerivedPointer(rinfo->call_address());
    MarkCompactCollector::MarkObject(code);
    // When compacting we convert the call to a real object pointer.
    if (IsCompacting()) rinfo->set_call_object(code);
  }

 private:
  // Mark object pointed to by p.
  void MarkObjectByPointer(Object** p) {
    if (!(*p)->IsHeapObject()) return;
    HeapObject* object = ShortCircuitConsString(p);
    MarkCompactCollector::MarkObject(object);
  }

  // Tells whether the mark sweep collection will perform compaction.
  bool IsCompacting() { return MarkCompactCollector::IsCompacting(); }

  // Retrieves the Code pointer from derived code entry.
  Code* CodeFromDerivedPointer(Address addr) {
    ASSERT(addr != NULL);
    return reinterpret_cast<Code*>(
        HeapObject::FromAddress(addr - Code::kHeaderSize));
  }

  // Visit an unmarked object.
  void VisitUnmarkedObject(HeapObject* obj) {
    ASSERT(Heap::Contains(obj));
#ifdef DEBUG
    MarkCompactCollector::UpdateLiveObjectCount(obj);
#endif
    Map* map = obj->map();
    obj->SetMark();
    MarkCompactCollector::tracer()->increment_marked_count();
    // Mark the map pointer and the body.
    MarkCompactCollector::MarkObject(map);
    obj->IterateBody(map->instance_type(), obj->SizeFromMap(map), this);
  }

  // Visit all unmarked objects pointed to by [start, end).
  // Returns false if the operation fails (lack of stack space).
  inline bool VisitUnmarkedObjects(Object** start, Object** end) {
    // Return false is we are close to the stack limit.
    StackLimitCheck check;
    if (check.HasOverflowed()) return false;

    // Visit the unmarked objects.
    for (Object** p = start; p < end; p++) {
      if (!(*p)->IsHeapObject()) continue;
      HeapObject* obj = HeapObject::cast(*p);
      if (obj->IsMarked()) continue;
      VisitUnmarkedObject(obj);
    }
    return true;
  }
};


// Visitor class for marking heap roots.
class RootMarkingVisitor : public ObjectVisitor {
 public:
  void VisitPointer(Object** p) {
    MarkObjectByPointer(p);
  }

  void VisitPointers(Object** start, Object** end) {
    for (Object** p = start; p < end; p++) MarkObjectByPointer(p);
  }

  MarkingVisitor* stack_visitor() { return &stack_visitor_; }

 private:
  MarkingVisitor stack_visitor_;

  void MarkObjectByPointer(Object** p) {
    if (!(*p)->IsHeapObject()) return;

    // Replace flat cons strings in place.
    HeapObject* object = ShortCircuitConsString(p);
    if (object->IsMarked()) return;

#ifdef DEBUG
    MarkCompactCollector::UpdateLiveObjectCount(object);
#endif
    Map* map = object->map();
    // Mark the object.
    object->SetMark();
    MarkCompactCollector::tracer()->increment_marked_count();
    // Mark the map pointer and body, and push them on the marking stack.
    MarkCompactCollector::MarkObject(map);
    object->IterateBody(map->instance_type(), object->SizeFromMap(map),
                        &stack_visitor_);

    // Mark all the objects reachable from the map and body.  May leave
    // overflowed objects in the heap.
    MarkCompactCollector::EmptyMarkingStack(&stack_visitor_);
  }
};


// Helper class for pruning the symbol table.
class SymbolTableCleaner : public ObjectVisitor {
 public:
  SymbolTableCleaner() : pointers_removed_(0) { }
  void VisitPointers(Object** start, Object** end) {
    // Visit all HeapObject pointers in [start, end).
    for (Object** p = start; p < end; p++) {
      if ((*p)->IsHeapObject() && !HeapObject::cast(*p)->IsMarked()) {
        // Set the entry to null_value (as deleted).
        *p = Heap::null_value();
        pointers_removed_++;
      }
    }
  }

  int PointersRemoved() {
    return pointers_removed_;
  }
 private:
  int pointers_removed_;
};


void MarkCompactCollector::MarkUnmarkedObject(HeapObject* object) {
#ifdef DEBUG
  UpdateLiveObjectCount(object);
#endif
  ASSERT(!object->IsMarked());
  if (object->IsJSGlobalObject()) Counters::global_objects.Increment();

  if (FLAG_cleanup_caches_in_maps_at_gc && object->IsMap()) {
    Map::cast(object)->ClearCodeCache();
  }

  object->SetMark();
  tracer_->increment_marked_count();
  ASSERT(Heap::Contains(object));
  marking_stack.Push(object);
}


static int OverflowObjectSize(HeapObject* obj) {
  // Recover the normal map pointer, it might be marked as live and
  // overflowed.
  MapWord map_word = obj->map_word();
  map_word.ClearMark();
  map_word.ClearOverflow();
  return obj->SizeFromMap(map_word.ToMap());