Introduce conservative sweeping.

src/mark-compact.h

 // 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
@@ skipping 88 matching lines @@
     if (Heap::InNewSpace(addr)) {
       uint32_t index = Heap::new_space()->Address2MarkbitIndex(addr);
       new_space_bitmap_->ClearRange(index, size >> kPointerSizeLog2);
     } else {
       Page *p = Page::FromAddress(addr);
       p->markbits()->ClearRange(p->FastAddress2Markbit(addr),
                                 size >> kPointerSizeLog2);
     }
   }
 
+  INLINE(static Address FirstMarkedObject(Page* p,
+                                          uint32_t cell_index,
+                                          uint32_t cell)) {
+    ASSERT(cell != 0);
+    uint32_t bit = __builtin_ctz(cell);

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

We will need to make this work on non-gcc at some point.

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

I create separate class for compiler intrinsics.

+    return p->Markbit2Address(
+        Page::MarkbitsBitmap::Cell2Index(cell_index) + bit);
+  }
+
+  INLINE(static Address FirstLiveObject(Address start,
+                                        Address limit)) {
+    ASSERT(!Heap::InNewSpace(start));
+    if (start >= limit) return start;
+
+    Page* p = Page::FromAddress(start);

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

can we call this variable page and the b variable bitmap?

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

Done.

+
+    // Space above linearity boundary is continious.

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

continious -> continuous

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

Done.

+    if (start >= p->linearity_boundary()) return start;

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

how do we know an object starts here?  This should be mentioned in the
documentation of the function.

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

Done.

+
+    Page::MarkbitsBitmap* b = p->markbits();
+    uint32_t markbit = p->Address2Markbit(start);

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

I'd prefer int instead of uint32_t.  Firstly unsigned variables cause trouble,
secondly the explicit specification of the size leads the reader to think it
matters.

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

I prefer uint32_t. Having uint32_t there and int here will require some
typecasting here or there.

+
+    // If the start address is marked return it.
+    if (b->Get(markbit)) return start;
+
+    uint32_t* cells = b->cells();
+    uint32_t cell = Page::MarkbitsBitmap::Index2Cell(markbit);
+
+    uint32_t last_cell =
+        Page::MarkbitsBitmap::Index2Cell(
+            Page::MarkbitsBitmap::CellAlignIndex(
+                p->Address2Markbit(limit)));

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

'To' is ! much longer than '2' and more clear2read&grok!

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

Done.

+
+    ASSERT(cell < last_cell);

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

Comm /* comment */ ent?

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

Done.

+
+    while (cell < last_cell && cells[cell] == 0) cell++;
+
+    if (cell == last_cell) return limit;
+
+    return FirstMarkedObject(p, cell, cells[cell]);
+  }
+
+  INLINE(static Address NextLiveObject(HeapObject* obj,
+                                       int size,
+                                       Address end)) {
+    ASSERT(!Heap::InNewSpace(obj));
+    Page* p = Page::FromAddress(obj->address());
+    Address watermark = p->linearity_boundary();
+    Address next_addr = obj->address() + size;
+
+    if (next_addr >= watermark) return next_addr;
+
+    Page::MarkbitsBitmap* b = p->markbits();
+    uint32_t markbit = p->Address2Markbit(next_addr);
+
+    if (b->Get(markbit)) return next_addr;
+
+    uint32_t* cells = b->cells();
+    uint32_t cell = Page::MarkbitsBitmap::Index2Cell(markbit);

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

Again, it's an int.  Can we call it cell_index to indicate it's not the actual
cell?

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

Done.

+
+    ASSERT(IsMarked(obj));
+
+    uint32_t bit  = Page::MarkbitsBitmap::Index2Bit(markbit);
+    uint32_t mask = (~1) << bit;
+    if ((cells[cell] & mask) != 0) {
+      // There are more marked objects in this cell.
+      return FirstMarkedObject(p, cell, cells[cell] & mask);
+    }
+
+    Address limit = Min(watermark, end);
+
+    uint32_t last_cell =

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

This is actually one past the last cell?

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

Yes. This is frontier cell.

+      Page::MarkbitsBitmap::Index2Cell(
+          Page::MarkbitsBitmap::CellAlignIndex(
+              p->Address2Markbit(limit)));
+
+    ASSERT(cell < last_cell);
+
+    do {
+      cell++;
+    } while (cell < last_cell && cells[cell] == 0);
+
+    if (cell == last_cell) return limit;
+
+    return FirstMarkedObject(p, cell, cells[cell]);
+  }
+
+  static inline void TransferMark(Address old_start,
+                                  Address new_start) {
+    if (Heap::InNewSpace(old_start) ||
+        Page::FromAddress(old_start)->IsFlagSet(Page::IS_CONTINIOUS) ||

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

IS_CONTINIOUS -> IS_CONTINUOUS

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

Done everywhere.

+        !IsMarked(old_start)) {
+      return;
+    }
+
+    SetMark(new_start);
+  }
+
   static bool Setup();
 
   static void TearDown();
 
  private:
   class BitmapStorageDescriptor {
    public:
     INLINE(static int CellsCount(Address addr)) {
       return HeaderOf(addr)->cells_count_;
     }
@@ skipping 272 matching lines @@
   // number of live objects.
   static int IterateLiveObjectsInRange(Address start, Address end,
                                        HeapObjectCallback size_func);
 
   // If we are not compacting the heap, we simply sweep the spaces except
   // for the large object space, clearing mark bits and adding unmarked
   // regions to each space's free list.
   static void SweepSpaces();
 
   static void SweepNewSpace(NewSpace* space);
-  static void SweepSpace(PagedSpace* space);
+
+  enum SweeperType { CONSERVATIVE, PRECISE };

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

The style guide allows kConservative and kPrecise.  I prefer them, you don't?

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

I prefer kX for non trivial constants.

XXX is for trivial constants.

+
+  static void SweepSpace(PagedSpace* space, SweeperType sweeper);
 
 #ifdef DEBUG
   // -----------------------------------------------------------------------
   // Debugging variables, functions and classes
   // Counters used for debugging the marking phase of mark-compact or
   // mark-sweep collection.
 
   // Size of live objects in Heap::to_space_.
   static int live_young_objects_size_;
 
@@ skipping 23 matching lines @@
 
   friend class UnmarkObjectVisitor;
   static void UnmarkObject(HeapObject* obj);
 #endif
 };
 
 
 } }  // namespace v8::internal
 
 #endif  // V8_MARK_COMPACT_H_