Separate markbits from heap object map words into bitmaps.

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 95 matching lines @@
 
 #define ASSERT_MAP_PAGE_INDEX(index)                                           \
   ASSERT((0 <= index) && (index <= MapSpace::kMaxMapPageIndex))
 
 
 class PagedSpace;
 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
 // any heap object.
 class MemoryChunk {
  public:
   static MemoryChunk* FromAddress(Address a) {
     return reinterpret_cast<MemoryChunk*>(OffsetFrom(a) & ~kAlignmentMask);
   }
 
@@ skipping 28 matching lines @@
     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;
 
+  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_; }
 
   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);
+  }
+
+  // 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_;
   intptr_t flags_;
   Space* owner_;
 
  private:
   static MemoryChunk* Initialize(Address base,
                                  size_t size,
                                  Executability executable,
                                  Space* owner) {
     MemoryChunk* chunk = FromAddress(base);
 
     ASSERT(base == chunk->address());
 
     chunk->next_chunk_ = NULL;
     chunk->size_ = size;
     chunk->flags_ = 0;
     chunk->owner_ = owner;
+    chunk->markbits()->Clear();
 
     if (executable == EXECUTABLE) chunk->SetFlag(IS_EXECUTABLE);
 
     return chunk;
   }
 
   friend class MemoryAllocator;
 };
 
 STATIC_CHECK(sizeof(MemoryChunk) <= MemoryChunk::kHeaderSize);
@@ skipping 1205 matching lines @@
   // Get the age mark of the inactive semispace.
   Address age_mark() { return from_space_.age_mark(); }
   // Set the age mark in the active semispace.
   void set_age_mark(Address mark) { to_space_.set_age_mark(mark); }
 
   // The start address of the space and a bit mask. Anding an address in the
   // new space with the mask will result in the start address.
   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; }
 
   MUST_USE_RESULT MaybeObject* AllocateRaw(int size_in_bytes) {
     return AllocateRawInternal(size_in_bytes, &allocation_info_);
   }
 
   // Reset the allocation pointer to the beginning of the active semispace.
   void ResetAllocationInfo();
@@ skipping 666 matching lines @@
 
  private:
   LargePage* current_;
   HeapObjectCallback size_func_;
 };
 
 
 } }  // namespace v8::internal
 
 #endif  // V8_SPACES_H_