Introduce conservative sweeping.

src/mark-compact.h

Index: src/mark-compact.h
diff --git a/src/mark-compact.h b/src/mark-compact.h
index 56be21fdd9d308c9c0e3f36c7cba336435b354fb..dee9bd0bb13dfbd61005c3d7474239581ce4137b 100644
--- a/src/mark-compact.h
+++ b/src/mark-compact.h
@@ -106,6 +106,104 @@ class Marking {
     }
   }
 
+  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();
@@ -398,7 +496,10 @@ class MarkCompactCollector: public AllStatic {
   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
   // -----------------------------------------------------------------------