Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(1626)

Unified Diff: src/spaces.h

Issue 2101002: Cardmarking writebarrier. (Closed)
Patch Set: fixed review comments Created 10 years, 7 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « src/runtime.cc ('k') | src/spaces.cc » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: src/spaces.h
diff --git a/src/spaces.h b/src/spaces.h
index df42d515d4467fa9b4ed8a2cf05120b327d87a65..2870a3ccf9dab4906c1f5063d935f4d30528f3a0 100644
--- a/src/spaces.h
+++ b/src/spaces.h
@@ -45,23 +45,46 @@ namespace internal {
// The old generation is collected by a mark-sweep-compact collector.
//
// The semispaces of the young generation are contiguous. The old and map
-// spaces consists of a list of pages. A page has a page header, a remembered
-// set area, and an object area. A page size is deliberately chosen as 8K
-// bytes. The first word of a page is an opaque page header that has the
+// spaces consists of a list of pages. A page has a page header and an object
+// area. A page size is deliberately chosen as 8K bytes.
+// The first word of a page is an opaque page header that has the
// address of the next page and its ownership information. The second word may
-// have the allocation top address of this page. The next 248 bytes are
-// remembered sets. Heap objects are aligned to the pointer size (4 bytes). A
-// remembered set bit corresponds to a pointer in the object area.
+// have the allocation top address of this page. Heap objects are aligned to the
+// pointer size.
//
// There is a separate large object space for objects larger than
// Page::kMaxHeapObjectSize, so that they do not have to move during
-// collection. The large object space is paged and uses the same remembered
-// set implementation. Pages in large object space may be larger than 8K.
+// collection. The large object space is paged. Pages in large object space
+// may be larger than 8K.
+//
+// A card marking write barrier is used to keep track of intergenerational
+// references. Old space pages are divided into regions of Page::kRegionSize
+// size. Each region has a corresponding dirty bit in the page header which is
+// set if the region might contain pointers to new space. For details about
+// dirty bits encoding see comments in the Page::GetRegionNumberForAddress()
+// method body.
+//
+// During scavenges and mark-sweep collections we iterate intergenerational
+// pointers without decoding heap object maps so if the page belongs to old
+// pointer space or large object space it is essential to guarantee that
+// the page does not contain any garbage pointers to new space: every pointer
+// aligned word which satisfies the Heap::InNewSpace() predicate must be a
+// pointer to a live heap object in new space. Thus objects in old pointer
+// and large object spaces should have a special layout (e.g. no bare integer
+// fields). This requirement does not apply to map space which is iterated in
+// a special fashion. However we still require pointer fields of dead maps to
+// be cleaned.
+//
+// To enable lazy cleaning of old space pages we use a notion of allocation
+// watermark. Every pointer under watermark is considered to be well formed.
+// Page allocation watermark is not necessarily equal to page allocation top but
+// all alive objects on page should reside under allocation watermark.
+// During scavenge allocation watermark might be bumped and invalid pointers
+// might appear below it. To avoid following them we store a valid watermark
+// into special field in the page header and set a page WATERMARK_INVALIDATED
+// flag. For details see comments in the Page::SetAllocationWatermark() method
+// body.
//
-// NOTE: The mark-compact collector rebuilds the remembered set after a
-// collection. It reuses first a few words of the remembered set for
-// bookkeeping relocation information.
-
// Some assertion macros used in the debugging mode.
@@ -91,25 +114,13 @@ class AllocationInfo;
// -----------------------------------------------------------------------------
// A page normally has 8K bytes. Large object pages may be larger. A page
-// address is always aligned to the 8K page size. A page is divided into
-// three areas: the first two words are used for bookkeeping, the next 248
-// bytes are used as remembered set, and the rest of the page is the object
-// area.
-//
-// Pointers are aligned to the pointer size (4), only 1 bit is needed
-// for a pointer in the remembered set. Given an address, its remembered set
-// bit position (offset from the start of the page) is calculated by dividing
-// its page offset by 32. Therefore, the object area in a page starts at the
-// 256th byte (8K/32). Bytes 0 to 255 do not need the remembered set, so that
-// the first two words (64 bits) in a page can be used for other purposes.
+// address is always aligned to the 8K page size.
//
-// On the 64-bit platform, we add an offset to the start of the remembered set,
-// and pointers are aligned to 8-byte pointer size. This means that we need
-// only 128 bytes for the RSet, and only get two bytes free in the RSet's RSet.
-// For this reason we add an offset to get room for the Page data at the start.
+// Each page starts with a header of Page::kPageHeaderSize size which contains
+// bookkeeping data.
//
// The mark-compact collector transforms a map pointer into a page index and a
-// page offset. The excact encoding is described in the comments for
+// page offset. The exact encoding is described in the comments for
// class MapWord in objects.h.
//
// The only way to get a page pointer is by calling factory methods:
@@ -150,18 +161,25 @@ class Page {
// Return the end of allocation in this page. Undefined for unused pages.
inline Address AllocationTop();
+ // Return the allocation watermark for the page.
+ // For old space pages it is guaranteed that the area under the watermark
+ // does not contain any garbage pointers to new space.
+ inline Address AllocationWatermark();
+
+ // Return the allocation watermark offset from the beginning of the page.
+ inline uint32_t AllocationWatermarkOffset();
+
+ inline void SetAllocationWatermark(Address allocation_watermark);
+
+ inline void SetCachedAllocationWatermark(Address allocation_watermark);
+ inline Address CachedAllocationWatermark();
+
// Returns the start address of the object area in this page.
Address ObjectAreaStart() { return address() + kObjectStartOffset; }
// Returns the end address (exclusive) of the object area in this page.
Address ObjectAreaEnd() { return address() + Page::kPageSize; }
- // Returns the start address of the remembered set area.
- Address RSetStart() { return address() + kRSetStartOffset; }
-
- // Returns the end address of the remembered set area (exclusive).
- Address RSetEnd() { return address() + kRSetEndOffset; }
-
// Checks whether an address is page aligned.
static bool IsAlignedToPageSize(Address a) {
return 0 == (OffsetFrom(a) & kPageAlignmentMask);
@@ -193,33 +211,22 @@ class Page {
}
// ---------------------------------------------------------------------
- // Remembered set support
+ // Card marking support
- // Clears remembered set in this page.
- inline void ClearRSet();
+ static const uint32_t kAllRegionsCleanMarks = 0x0;
- // Return the address of the remembered set word corresponding to an
- // object address/offset pair, and the bit encoded as a single-bit
- // mask in the output parameter 'bitmask'.
- INLINE(static Address ComputeRSetBitPosition(Address address, int offset,
- uint32_t* bitmask));
+ inline uint32_t GetRegionMarks();
+ inline void SetRegionMarks(uint32_t dirty);
- // Sets the corresponding remembered set bit for a given address.
- INLINE(static void SetRSet(Address address, int offset));
+ inline uint32_t GetRegionMaskForAddress(Address addr);
+ inline int GetRegionNumberForAddress(Address addr);
- // Clears the corresponding remembered set bit for a given address.
- static inline void UnsetRSet(Address address, int offset);
+ inline void MarkRegionDirty(Address addr);
+ inline bool IsRegionDirty(Address addr);
- // Checks whether the remembered set bit for a given address is set.
- static inline bool IsRSetSet(Address address, int offset);
-
-#ifdef DEBUG
- // Use a state to mark whether remembered set space can be used for other
- // purposes.
- enum RSetState { IN_USE, NOT_IN_USE };
- static bool is_rset_in_use() { return rset_state_ == IN_USE; }
- static void set_rset_state(RSetState state) { rset_state_ = state; }
-#endif
+ inline void ClearRegionMarks(Address start,
+ Address end,
+ bool reaches_limit);
// Page size in bytes. This must be a multiple of the OS page size.
static const int kPageSize = 1 << kPageSizeBits;
@@ -227,25 +234,11 @@ class Page {
// Page size mask.
static const intptr_t kPageAlignmentMask = (1 << kPageSizeBits) - 1;
- // The offset of the remembered set in a page, in addition to the empty bytes
- // formed as the remembered bits of the remembered set itself.
-#ifdef V8_TARGET_ARCH_X64
- static const int kRSetOffset = 4 * kPointerSize; // Room for four pointers.
-#else
- static const int kRSetOffset = 0;
-#endif
- // The end offset of the remembered set in a page
- // (heaps are aligned to pointer size).
- static const int kRSetEndOffset = kRSetOffset + kPageSize / kBitsPerPointer;
+ static const int kPageHeaderSize = kPointerSize + kPointerSize + kIntSize +
+ kIntSize + kPointerSize;
// The start offset of the object area in a page.
- // This needs to be at least (bits per uint32_t) * kBitsPerPointer,
- // to align start of rset to a uint32_t address.
- static const int kObjectStartOffset = 256;
-
- // The start offset of the used part of the remembered set in a page.
- static const int kRSetStartOffset = kRSetOffset +
- kObjectStartOffset / kBitsPerPointer;
+ static const int kObjectStartOffset = MAP_POINTER_ALIGN(kPageHeaderSize);
// Object area size in bytes.
static const int kObjectAreaSize = kPageSize - kObjectStartOffset;
@@ -253,13 +246,63 @@ class Page {
// Maximum object size that fits in a page.
static const int kMaxHeapObjectSize = kObjectAreaSize;
+ 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);
+
enum PageFlag {
IS_NORMAL_PAGE = 1 << 0,
- WAS_IN_USE_BEFORE_MC = 1 << 1
+ WAS_IN_USE_BEFORE_MC = 1 << 1,
+
+ // Page allocation watermark was bumped by preallocation during scavenge.
+ // Correct watermark can be retrieved by CachedAllocationWatermark() method
+ WATERMARK_INVALIDATED = 1 << 2
};
+ // 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 bool GetPageFlag(PageFlag flag);
inline void SetPageFlag(PageFlag flag, bool value);
+ inline void ClearPageFlags();
+
+ static const int kAllocationWatermarkOffsetShift = 3;
+ 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_;
//---------------------------------------------------------------------------
// Page header description.
@@ -279,26 +322,24 @@ class Page {
// second word *may* (if the page start and large object chunk start are
// the same) contain the large object chunk size. In either case, the
// low-order bit for large object pages will be cleared.
- // For normal pages this word is used to store various page flags.
- int flags;
+ // For normal pages this word is used to store page flags and
+ // offset of allocation top.
+ intptr_t flags_;
- // The following fields may overlap with remembered set, they can only
- // be used in the mark-compact collector when remembered set is not
- // used.
+ // This field contains dirty marks for regions covering the page. Only dirty
+ // regions might contain intergenerational references.
+ // Only 32 dirty marks are supported so for large object pages several regions
+ // might be mapped to a single dirty mark.
+ uint32_t dirty_regions_;
// The index of the page in its owner space.
int mc_page_index;
- // The allocation pointer after relocating objects to this page.
- Address mc_relocation_top;
-
- // The forwarding address of the first live object in this page.
+ // During mark-compact collections this field contains the forwarding address
+ // of the first live object in this page.
+ // During scavenge collection this field is used to store allocation watermark
+ // if it is altered during scavenge.
Address mc_first_forwarded;
-
-#ifdef DEBUG
- private:
- static RSetState rset_state_; // state of the remembered set
-#endif
};
@@ -921,8 +962,7 @@ class PagedSpace : public Space {
// Checks whether page is currently in use by this space.
bool IsUsed(Page* page);
- // Clears remembered sets of pages in this space.
- void ClearRSet();
+ void MarkAllPagesClean();
// Prepares for a mark-compact GC.
virtual void PrepareForMarkCompact(bool will_compact);
@@ -936,6 +976,11 @@ class PagedSpace : public Space {
// The limit of allocation for a page in this space.
virtual Address PageAllocationLimit(Page* page) = 0;
+ void FlushTopPageWatermark() {
+ AllocationTopPage()->SetCachedAllocationWatermark(top());
+ AllocationTopPage()->InvalidateWatermark(true);
+ }
+
// Current capacity without growing (Size() + Available() + Waste()).
int Capacity() { return accounting_stats_.Capacity(); }
@@ -990,7 +1035,8 @@ class PagedSpace : public Space {
// Writes relocation info to the top page.
void MCWriteRelocationInfoToPage() {
- TopPageOf(mc_forwarding_info_)->mc_relocation_top = mc_forwarding_info_.top;
+ TopPageOf(mc_forwarding_info_)->
+ SetAllocationWatermark(mc_forwarding_info_.top);
}
// Computes the offset of a given address in this space to the beginning
@@ -1108,8 +1154,6 @@ class PagedSpace : public Space {
#ifdef DEBUG
// Returns the number of total pages in this space.
int CountTotalPages();
-
- void DoPrintRSet(const char* space_name);
#endif
private:
@@ -1746,6 +1790,10 @@ class OldSpace : public PagedSpace {
if (add_to_freelist) {
int wasted_bytes = free_list_.Free(start, size_in_bytes);
accounting_stats_.WasteBytes(wasted_bytes);
+ } else {
+#ifdef DEBUG
+ MemoryAllocator::ZapBlock(start, size_in_bytes);
+#endif
}
}
@@ -1762,8 +1810,6 @@ class OldSpace : public PagedSpace {
#ifdef DEBUG
// Reports statistics for the space
void ReportStatistics();
- // Dump the remembered sets in the space to stdout.
- void PrintRSet();
#endif
protected:
@@ -1812,6 +1858,10 @@ class FixedSpace : public PagedSpace {
void Free(Address start, bool add_to_freelist) {
if (add_to_freelist) {
free_list_.Free(start);
+ } else {
+#ifdef DEBUG
+ MemoryAllocator::ZapBlock(start, object_size_in_bytes_);
+#endif
}
accounting_stats_.DeallocateBytes(object_size_in_bytes_);
}
@@ -1828,9 +1878,6 @@ class FixedSpace : public PagedSpace {
#ifdef DEBUG
// Reports statistic info of the space
void ReportStatistics();
-
- // Dump the remembered sets in the space to stdout.
- void PrintRSet();
#endif
protected:
@@ -1899,11 +1946,11 @@ class MapSpace : public FixedSpace {
PageIterator it(this, PageIterator::ALL_PAGES);
while (pages_left-- > 0) {
ASSERT(it.has_next());
- it.next()->ClearRSet();
+ it.next()->SetRegionMarks(Page::kAllRegionsCleanMarks);
}
ASSERT(it.has_next());
Page* top_page = it.next();
- top_page->ClearRSet();
+ top_page->SetRegionMarks(Page::kAllRegionsCleanMarks);
ASSERT(top_page->is_valid());
int offset = live_maps % kMapsPerPage * Map::kSize;
@@ -1994,9 +2041,8 @@ class LargeObjectChunk {
public:
// Allocates a new LargeObjectChunk that contains a large object page
// (Page::kPageSize aligned) that has at least size_in_bytes (for a large
- // object and possibly extra remembered set words) bytes after the object
- // area start of that page. The allocated chunk size is set in the output
- // parameter chunk_size.
+ // object) bytes after the object area start of that page.
+ // The allocated chunk size is set in the output parameter chunk_size.
static LargeObjectChunk* New(int size_in_bytes,
size_t* chunk_size,
Executability executable);
@@ -2019,16 +2065,12 @@ class LargeObjectChunk {
// Returns the object in this chunk.
inline HeapObject* GetObject();
- // Given a requested size (including any extra remembered set words),
- // returns the physical size of a chunk to be allocated.
+ // Given a requested size returns the physical size of a chunk to be
+ // allocated.
static int ChunkSizeFor(int size_in_bytes);
- // Given a chunk size, returns the object size it can accommodate (not
- // including any extra remembered set words). Used by
- // LargeObjectSpace::Available. Note that this can overestimate the size
- // of object that will fit in a chunk---if the object requires extra
- // remembered set words (eg, for large fixed arrays), the actual object
- // size for the chunk will be smaller than reported by this function.
+ // Given a chunk size, returns the object size it can accommodate. Used by
+ // LargeObjectSpace::Available.
static int ObjectSizeFor(int chunk_size) {
if (chunk_size <= (Page::kPageSize + Page::kObjectStartOffset)) return 0;
return chunk_size - Page::kPageSize - Page::kObjectStartOffset;
@@ -2064,8 +2106,7 @@ class LargeObjectSpace : public Space {
// Allocates a large FixedArray.
Object* AllocateRawFixedArray(int size_in_bytes);
- // Available bytes for objects in this space, not including any extra
- // remembered set words.
+ // Available bytes for objects in this space.
int Available() {
return LargeObjectChunk::ObjectSizeFor(MemoryAllocator::Available());
}
@@ -2083,11 +2124,8 @@ class LargeObjectSpace : public Space {
// space, may be slow.
Object* FindObject(Address a);
- // Clears remembered sets.
- void ClearRSet();
-
- // Iterates objects whose remembered set bits are set.
- void IterateRSet(ObjectSlotCallback func);
+ // Iterates objects covered by dirty regions.
+ void IterateDirtyRegions(ObjectSlotCallback func);
// Frees unmarked objects.
void FreeUnmarkedObjects();
@@ -2114,8 +2152,6 @@ class LargeObjectSpace : public Space {
virtual void Print();
void ReportStatistics();
void CollectCodeStatistics();
- // Dump the remembered sets in the space to stdout.
- void PrintRSet();
#endif
// Checks whether an address is in the object area in this space. It
// iterates all objects in the space. May be slow.
@@ -2134,10 +2170,6 @@ class LargeObjectSpace : public Space {
int object_size,
Executability executable);
- // Returns the number of extra bytes (rounded up to the nearest full word)
- // required for extra_object_bytes of extra pointers (in bytes).
- static inline int ExtraRSetBytesFor(int extra_object_bytes);
-
friend class LargeObjectIterator;
public:
« no previous file with comments | « src/runtime.cc ('k') | src/spaces.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698