Introduce conservative sweeping.

src/spaces.h

 // Copyright 2006-2010 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
@@ skipping 117 matching lines @@
   }
 
   int CellsCount() {
     return StorageDescriptor::CellsCount(this->address());
   }
 
   static int SizeFor(int cells_count) {
     return sizeof(CellType)*cells_count;
   }
 
+  INLINE(static uint32_t Index2Cell(uint32_t index)) {
+    return index >> kBitsPerCellLog2;
+  }
+
+  INLINE(static uint32_t Index2Bit(uint32_t index)) {
+    return index & kBitIndexMask;
+  }
+
+  INLINE(static uint32_t Cell2Index(uint32_t index)) {
+    return index << kBitsPerCellLog2;
+  }
+
+  INLINE(static uint32_t CellAlignIndex(uint32_t index)) {
+    return (index + kBitIndexMask) & ~kBitIndexMask;
+  }
+
   INLINE(CellType* cells()) {
     return reinterpret_cast<CellType*>(this);
   }
 
   INLINE(Address address()) {
     return reinterpret_cast<Address>(this);
   }
 
   INLINE(static Bitmap* FromAddress(Address addr)) {
     return reinterpret_cast<Bitmap*>(addr);
@@ skipping 30 matching lines @@
 
   INLINE(void ClearRange(uint32_t start, uint32_t size)) {
     const uint32_t end = start + size;
     const uint32_t start_cell = start >> kBitsPerCellLog2;
     const uint32_t end_cell = end >> kBitsPerCellLog2;
 
     const uint32_t start_mask = (-1) << (start & kBitIndexMask);
     const uint32_t end_mask   = (1 << (end & kBitIndexMask)) - 1;
 
     ASSERT(static_cast<int>(start_cell) < CellsCount());
-    ASSERT(static_cast<int>(end_cell) < CellsCount());
+    ASSERT(static_cast<int>(end_cell) < CellsCount() ||
+           (end_mask == 0 && static_cast<int>(end_cell) == CellsCount()));
 
     if (start_cell == end_cell) {
       cells()[start_cell] &= ~(start_mask & end_mask);
     } else {
       cells()[start_cell] &= ~start_mask;
       if (end_mask != 0) cells()[end_cell] &= ~end_mask;
 
       for (uint32_t cell = start_cell + 1, last_cell = end_cell - 1;
            cell <= last_cell;
            cell++) {
         cells()[cell] = 0;
       }
     }
   }
 
   INLINE(void Clear()) {
     for (int i = 0; i < CellsCount(); i++) cells()[i] = 0;
   }
 
-  static void PrintWord(const uint32_t& word, const char* sep = " ") {
+  static void PrintWord(uint32_t word, uint32_t himask = 0) {
     for (uint32_t mask = 1; mask != 0; mask <<= 1) {
+      if ((mask & himask) != 0) PrintF("[");
       PrintF((mask & word) ? "1" : "0");
+      if ((mask & himask) != 0) PrintF("]");
     }
-    PrintF("%s", sep);
   }
 
+  class CellPrinter {
+   public:
+    CellPrinter() : seq_start(0), seq_type(0), seq_length(0) { }
+
+    void Print(uint32_t pos, uint32_t cell) {
+      if (cell == seq_type) {
+        seq_length++;
+        return;
+      }
+
+      Flush();
+
+      if (IsSeq(cell)) {
+        seq_start = pos;
+        seq_length = 0;
+        seq_type = cell;
+        return;
+      }
+
+      PrintF("%d: ", pos);
+      PrintWord(cell);
+      PrintF("\n");
+    }
+
+    void Flush() {
+      if (seq_length > 0) {
+        PrintF("%d: %dx%d\n",
+               seq_start,
+               seq_type == 0 ? 0 : 1,
+               seq_length * kBitsPerCell);
+        seq_length = 0;
+      }
+    }
+
+    static bool IsSeq(uint32_t cell) { return cell == 0 || cell == 0xFFFFFFFF; }
+   private:
+    uint32_t seq_start;
+    uint32_t seq_type;
+    uint32_t seq_length;
+  };
+
   void Print() {
+    CellPrinter printer;
     for (int i = 0; i < CellsCount(); i++) {
-      PrintWord(cells()[i]);
+      printer.Print(i, cells()[i]);
     }
+    printer.Flush();
     PrintF("\n");
   }
 
   bool IsClean() {
     for (int i = 0; i < CellsCount(); i++) {
       if (cells()[i] != 0) return false;
     }
     return true;
   }
 };
@@ skipping 21 matching lines @@
 
   Address body() { return address() + kBodyOffset; }
 
   int body_size() { return size() - kBodyOffset; }
 
   enum MemoryChunkFlags {
     IS_EXECUTABLE,
     NUM_MEMORY_CHUNK_FLAGS
   };
 
-  void SetFlag(MemoryChunkFlags flag) {
+  void SetFlag(int flag) {
     flags_ |= 1 << flag;
   }
 
-  void ClearFlag(MemoryChunkFlags flag) {
+  void ClearFlag(int flag) {
     flags_ &= ~(1 << flag);
   }
 
-  bool IsFlagSet(MemoryChunkFlags flag) {
+  bool IsFlagSet(int flag) {
     return (flags_ & (1 << flag)) != 0;
   }
 
   static const intptr_t kAlignment = (1 << kPageSizeBits);
 
   static const intptr_t kAlignmentMask = kAlignment - 1;
 
   static const size_t kHeaderSize = kPointerSize + kPointerSize + kPointerSize +
-    kPointerSize + kPointerSize;
+    kPointerSize + kPointerSize + kPointerSize;
 
   static const size_t kMarksBitmapLength =
     (1 << kPageSizeBits) >> (kPointerSizeLog2);
 
   static const size_t kMarksBitmapSize =
     (1 << kPageSizeBits) >> (kPointerSizeLog2 + kBitsPerByteLog2);
 
   static const int kBodyOffset =
     CODE_POINTER_ALIGN(MAP_POINTER_ALIGN(kHeaderSize + kMarksBitmapSize));
 
   size_t size() const { return size_; }
 
   Executability executable() {
     return IsFlagSet(IS_EXECUTABLE) ? EXECUTABLE : NOT_EXECUTABLE;
   }
 
   // ---------------------------------------------------------------------
   // Markbits support
+
   class BitmapStorageDescriptor {
    public:
     INLINE(static int CellsCount(Address addr)) {
       return Bitmap<BitmapStorageDescriptor>::CellsForLength(
           kMarksBitmapLength);
     }
   };
 
   typedef Bitmap<BitmapStorageDescriptor> MarkbitsBitmap;
 
   inline MarkbitsBitmap* markbits() {
     return MarkbitsBitmap::FromAddress(address() + kHeaderSize);
   }
 
+  void PrintMarkbits() { markbits()->Print(); }
+
   inline uint32_t Address2Markbit(Address addr) {
     return static_cast<uint32_t>(addr - this->address()) >> kPointerSizeLog2;
   }
 
   inline static uint32_t FastAddress2Markbit(Address addr) {
     const intptr_t offset =
         reinterpret_cast<intptr_t>(addr) & kAlignmentMask;
 
     return static_cast<uint32_t>(offset) >> kPointerSizeLog2;
   }
@@ skipping 142 matching lines @@
   // The start offset of the object area in a page. Aligned to both maps and
   // code alignment to be suitable for both.
   static const int kObjectStartOffset = kBodyOffset;
 
   // Object area size in bytes.
   static const int kObjectAreaSize = kPageSize - kObjectStartOffset;
 
   // Maximum object size that fits in a page.
   static const int kMaxHeapObjectSize = kObjectAreaSize;
 
+  static const int kFirstUsedCell =
+    (kBodyOffset/kPointerSize) >> MarkbitsBitmap::kBitsPerCellLog2;
+
+  static const int kLastUsedCell =
+    ((kPageSize - kPointerSize)/kPointerSize) >>
+      MarkbitsBitmap::kBitsPerCellLog2;
+
+
 #ifdef ENABLE_CARDMARKING_WRITE_BARRIER
   static const int kDirtyFlagOffset = 2 * kPointerSize;
   static const int kRegionSizeLog2 = 8;
   static const int kRegionSize = 1 << kRegionSizeLog2;
   static const intptr_t kRegionAlignmentMask = (kRegionSize - 1);
 
   STATIC_CHECK(kRegionSize == kPageSize / kBitsPerInt);
 #endif
 
   enum PageFlag {
     // Page allocation watermark was bumped by preallocation during scavenge.
     // Correct watermark can be retrieved by CachedAllocationWatermark() method
     WATERMARK_INVALIDATED = NUM_MEMORY_CHUNK_FLAGS,
+    IS_CONTINIOUS,
     NUM_PAGE_FLAGS  // Must be last
   };
 
-  static const int kPageFlagMask = (1 << NUM_PAGE_FLAGS) - 1;
-
   // To avoid an additional WATERMARK_INVALIDATED flag clearing pass during
   // scavenge we just invalidate the watermark on each old space page after
   // processing it. And then we flip the meaning of the WATERMARK_INVALIDATED
   // flag at the beginning of the next scavenge and each page becomes marked as
   // having a valid watermark.
   //
   // The following invariant must hold for pages in old pointer and map spaces:
   //     If page is in use then page is marked as having invalid watermark at
   //     the beginning and at the end of any GC.
   //
   // This invariant guarantees that after flipping flag meaning at the
   // beginning of scavenge all pages in use will be marked as having valid
   // watermark.
   static inline void FlipMeaningOfInvalidatedWatermarkFlag();
 
   // Returns true if the page allocation watermark was not altered during
   // scavenge.
   inline bool IsWatermarkValid();
 
   inline void InvalidateWatermark(bool value);
 
   inline void ClearGCFields();
 
-  static const int kAllocationWatermarkOffsetShift = WATERMARK_INVALIDATED + 1;
+  static const int kAllocationWatermarkOffsetShift = NUM_PAGE_FLAGS;
   static const int kAllocationWatermarkOffsetBits  = kPageSizeBits + 1;
   static const uint32_t kAllocationWatermarkOffsetMask =
       ((1 << kAllocationWatermarkOffsetBits) - 1) <<
       kAllocationWatermarkOffsetShift;
 
   static const uint32_t kFlagsMask =
     ((1 << kAllocationWatermarkOffsetShift) - 1);
 
   STATIC_CHECK(kBitsPerInt - kAllocationWatermarkOffsetShift >=
                kAllocationWatermarkOffsetBits);
 
   // This field contains the meaning of the WATERMARK_INVALIDATED flag.
   // Instead of clearing this flag from all pages we just flip
   // its meaning at the beginning of a scavenge.
   static intptr_t watermark_invalidated_mark_;
 
+  Address linearity_boundary() { return linearity_boundary_; }
+  void set_linearity_boundary(Address linearity_boundary) {
+    linearity_boundary_ = linearity_boundary;
+  }
+
  private:
   static Page* Initialize(MemoryChunk* chunk) {
     Page* page = static_cast<Page*>(chunk);
     page->allocation_watermark_ = page->body();
     page->InvalidateWatermark(true);
+    page->SetFlag(IS_CONTINIOUS);
     return page;
   }
 
   Address allocation_watermark_;
+  Address linearity_boundary_;

[Erik Corry, 2011/01/19 13:46:48]

Comment?

 
   friend class MemoryAllocator;
 };
 
 STATIC_CHECK(sizeof(Page) <= MemoryChunk::kHeaderSize);
 
 class LargePage : public MemoryChunk {
  public:
   HeapObject* GetObject() {
     return HeapObject::FromAddress(body());
@@ skipping 289 matching lines @@
  public:
   virtual ~ObjectIterator() { }
 
   virtual HeapObject* next_object() = 0;
 };
 
 
 // -----------------------------------------------------------------------------
 // Heap object iterator in new/old/map spaces.
 //
-// A HeapObjectIterator iterates objects from a given address to the
-// top of a space. The given address must be below the current
-// allocation pointer (space top). There are some caveats.
+// A HeapObjectIterator iterates objects from the bottom of the given space of

[Erik Corry, 2011/01/19 13:46:48]

I can't quite parse this.

[Vyacheslav Egorov (Chromium), 2011/01/20 16:40:21]

Done.

+// page given address to the top of a space. The given address must be below the
+// current allocation pointer (space top). There are some caveats.
 //
 // (1) If the space top changes upward during iteration (because of
 //     allocating new objects), the iterator does not iterate objects
 //     above the original space top. The caller must create a new
 //     iterator starting from the old top in order to visit these new
 //     objects.
 //
 // (2) If new objects are allocated below the original allocation top
 //     (e.g., free-list allocation in paged spaces), the new objects
 //     may or may not be iterated depending on their position with
 //     respect to the current point of iteration.
 //
 // (3) The space top should not change downward during iteration,
 //     otherwise the iterator will return not-necessarily-valid
 //     objects.
 
 class HeapObjectIterator: public ObjectIterator {
  public:
-  // Creates a new object iterator in a given space. If a start
-  // address is not given, the iterator starts from the space bottom.
+  // Creates a new object iterator in a given space.
   // If the size function is not given, the iterator calls the default
   // Object::Size().
   explicit HeapObjectIterator(PagedSpace* space);
   HeapObjectIterator(PagedSpace* space, HeapObjectCallback size_func);
-  HeapObjectIterator(PagedSpace* space, Address start);
-  HeapObjectIterator(PagedSpace* space,
-                     Address start,
-                     HeapObjectCallback size_func);
   HeapObjectIterator(Page* page, HeapObjectCallback size_func);
 
   inline HeapObject* next() {
     return (cur_addr_ < cur_limit_) ? FromCurrentPage() : FromNextPage();
   }
 
   // implementation of ObjectIterator.
   virtual HeapObject* next_object() { return next(); }
 
  private:
   Address cur_addr_;  // current iteration point
   Address end_addr_;  // end iteration point
   Address cur_limit_;  // current page limit
   HeapObjectCallback size_func_;  // size function
   Page* end_page_;  // caches the page of the end address
 
   HeapObject* FromCurrentPage() {
     ASSERT(cur_addr_ < cur_limit_);
+    HeapObject* obj = HeapObject::FromAddress(cur_addr_);
 
-    HeapObject* obj = HeapObject::FromAddress(cur_addr_);
-    int obj_size = (size_func_ == NULL) ? obj->Size() : size_func_(obj);
-    ASSERT_OBJECT_SIZE(obj_size);
+    Page* p = Page::FromAddress(cur_addr_);
+    if (p->IsFlagSet(Page::IS_CONTINIOUS)) {
+      int obj_size = (size_func_ == NULL) ? obj->Size() : size_func_(obj);
+      ASSERT_OBJECT_SIZE(obj_size);
 
-    cur_addr_ += obj_size;
-    ASSERT(cur_addr_ <= cur_limit_);
+      cur_addr_ += obj_size;
+      ASSERT(cur_addr_ <= cur_limit_);
+    } else {
+      AdvanceUsingMarkbits();
+    }
 
     return obj;
   }
 
+  void AdvanceUsingMarkbits();
+
   // Slow path of next, goes into the next page.
   HeapObject* FromNextPage();
 
   // Initializes fields.
   void Initialize(Address start, Address end, HeapObjectCallback size_func);
 
 #ifdef DEBUG
   // Verifies whether fields have valid values.
   void Verify();
 #endif
@@ skipping 1338 matching lines @@
 
  private:
   LargePage* current_;
   HeapObjectCallback size_func_;
 };
 
 
 } }  // namespace v8::internal
 
 #endif  // V8_SPACES_H_