Separate markbits from heap object map words into bitmaps.

src/spaces.h

Index: src/spaces.h
diff --git a/src/spaces.h b/src/spaces.h
index 7ba89951f956f62dcf09ad21135029bb45816485..b2f3fa45ac1737effc0a95b82b045ac791c1931f 100644
--- a/src/spaces.h
+++ b/src/spaces.h
@@ -113,6 +113,122 @@ class MemoryAllocator;
 class AllocationInfo;
 class Space;
 
+
+// Bitmap is a sequence of cells each containing fixed number of bits.

[Erik Corry, 2011/01/07 12:13:21]

Perhaps add a comment with the word 'endian' since this stuff looks
endian-dependent.  Or do we only ever access in words, never in bytes?

+template<typename StorageDescriptor>
+class Bitmap {
+ public:
+  typedef uint32_t CellType;
+  static const uint32_t kBitsPerCell = 32;
+  static const uint32_t kBitsPerCellLog2 = 5;
+
+  static int CellsForLength(int length) {
+    return (length + kBitsPerCell - 1) >> kBitsPerCellLog2;
+  }
+
+  int CellsCount() {
+    return StorageDescriptor::CellsCount(this->address());
+  }
+
+  static int SizeFor(int cells_count) {
+    return sizeof(CellType)*cells_count;
+  }
+
+  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);
+  }
+
+  INLINE(static Bitmap* FromAddress(uint32_t* addr)) {
+    return reinterpret_cast<Bitmap*>(addr);
+  }
+
+  INLINE(bool TestAndSet(const uint32_t index)) {
+    const uint32_t mask = 1 << index;
+    if (cells()[index >> kBitsPerCellLog2] & mask) {
+      return true;
+    } else {
+      cells()[index >> kBitsPerCellLog2] |= mask;
+      return false;
+    }
+  }
+
+  INLINE(bool Get(uint32_t index)) {
+    uint32_t mask = 1 << index;
+    return (this->cells()[index >> kBitsPerCellLog2] & mask) != 0;
+  }
+
+  INLINE(void Set(uint32_t index, bool value)) {

[Erik Corry, 2011/01/07 12:13:21]

I think it's nicer to have Set and Clear methods instead of relying on the
inliner to do that for you.

+    uint32_t mask = 1 << index;
+    if (value) {
+      this->cells()[index >> kBitsPerCellLog2] |= mask;
+    } else {
+      this->cells()[index >> kBitsPerCellLog2] &= ~mask;
+    }
+  }
+
+  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;

[Erik Corry, 2011/01/07 12:13:21]

I think you are assuming here that the rhs of the shift operand will be masked
down, but it would be clearer and less fragile if you did the mask explicitly.

+    const uint32_t end_mask   = (1 << end) - 1;
+
+    if (start_cell == end_cell) {
+      cells()[start_cell] &= ~(start_mask & end_mask);
+    } else {
+      cells()[start_cell] &= ~start_mask;
+      cells()[end_cell] &= ~end_mask;

[Erik Corry, 2011/01/07 12:13:21]

I think this reads and writes (but doesn't change) the word after the end if
start+size hits a word boundary.

+
+      for(uint32_t cell = start_cell + 1, last_cell = end_cell - 1;
+          cell <= last_cell;
+          cell++) {
+        cells()[cell] = 0;
+      }
+    }
+  }
+
+

[Erik Corry, 2011/01/07 12:13:21]

Why two blank lines?

+  INLINE(void Clear()) {
+    for (int i = 0; i < CellsCount(); i++) {
+      cells()[i] = 0;
+    }
+  }
+
+
+  static void PrintWord(const uint32_t& word, const char* sep = " ") {
+    for (uint32_t mask = 1; mask != 0; mask <<= 1) {
+      PrintF((mask & word) ? "1" : "0");
+    }
+    PrintF("%s", sep);
+  }
+
+
+  void Print() {
+    for (int i = 0; i < CellsCount(); i++) {
+      PrintWord(cells()[i]);
+    }
+    PrintF("\n");
+  }
+
+
+  bool IsClean() {
+    for (int i = 0; i < CellsCount(); i++) {
+      if (cells()[i] != 0) return false;
+    }
+    return true;
+  }
+};
+
+
 // MemoryChunk represents a memory region owned by a specific space.
 // It is divided into the header and the body. Chunk start is always
 // 1MB aligned. Start of the body is aligned so it can accomodate
@@ -161,8 +277,16 @@ class MemoryChunk {
   static const size_t kHeaderSize = kPointerSize + kPointerSize + kPointerSize +
     kPointerSize + kPointerSize;
 
+  static const size_t kBitsPerByteLog2 = 3;

[Erik Corry, 2011/01/07 12:13:21]

This constant already exists in globals.h

+
+  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));
+    CODE_POINTER_ALIGN(MAP_POINTER_ALIGN(kHeaderSize + kMarksBitmapSize));
 
   size_t size() const { return size_; }
 
@@ -170,6 +294,38 @@ class MemoryChunk {
     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);
+  }
+
+  // TODO [EVE] when do we need this crap?

[Erik Corry, 2011/01/07 12:13:21]

Does this lint or pass the FCC?

+  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;
+  }
+
+  inline Address Markbit2Address(uint32_t index) {
+    return this->address() + (index << kPointerSizeLog2);
+  }
+
  protected:
   MemoryChunk* next_chunk_;
   size_t size_;
@@ -189,6 +345,7 @@ class MemoryChunk {
     chunk->size_ = size;
     chunk->flags_ = 0;
     chunk->owner_ = owner;
+    chunk->markbits()->Clear();
 
     if (executable == EXECUTABLE) chunk->SetFlag(IS_EXECUTABLE);
 
@@ -1414,6 +1571,16 @@ class NewSpace : public Space {
   Address start() { return start_; }
   uintptr_t mask() { return address_mask_; }
 
+  INLINE(uint32_t Address2MarkbitIndex(Address addr)) {
+    ASSERT(Contains(addr));
+    ASSERT(IsAligned(OffsetFrom(addr), kPointerSize));
+    return static_cast<uint32_t>(addr - start_) >> kPointerSizeLog2;
+  }
+
+  INLINE(Address MarkbitIndex2Address(uint32_t index)) {
+    return reinterpret_cast<Address>(index << kPointerSizeLog2);
+  }
+
   // The allocation top and limit addresses.
   Address* allocation_top_address() { return &allocation_info_.top; }
   Address* allocation_limit_address() { return &allocation_info_.limit; }