Oilpan: Implement bitmap marking

Source/platform/heap/Heap.h

 /*
  * Copyright (C) 2013 Google Inc. 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
@@ skipping 48 matching lines @@
 // blinkPagesPerRegion at a given random address. We group pages to
 // not spread out too much over the address space which would blow
 // away the page tables and lead to bad performance.
 const size_t blinkPagesPerRegion = 10;
 
 // Double precision floats are more efficient when 8 byte aligned, so we 8 byte
 // align all allocations even on 32 bit.
 const size_t allocationGranularity = 8;
 const size_t allocationMask = allocationGranularity - 1;
 const size_t objectStartBitMapSize = (blinkPageSize + ((8 * allocationGranularity) - 1)) / (8 * allocationGranularity);
-const size_t reservedForObjectBitMap = ((objectStartBitMapSize + allocationMask) & ~allocationMask);
+const size_t reservedForObjectStartBitMap = ((objectStartBitMapSize + allocationMask) & ~allocationMask);
+const size_t objectMarkBitMapSize = (blinkPageSize + ((8 * allocationGranularity) - 1)) / (8 * allocationGranularity);
+const size_t reservedForObjectMarkBitMap = ((objectStartBitMapSize + allocationMask) & ~allocationMask);
 const size_t maxHeapObjectSizeLog2 = 27;
 const size_t maxHeapObjectSize = 1 << maxHeapObjectSizeLog2;
 
-const size_t markBitMask = 1;
 const size_t freeListMask = 2;
 // The dead bit is used for objects that have gone through a GC marking, but did
 // not get swept before a new GC started. In that case we set the dead bit on
 // objects that were not marked in the previous GC to ensure we are not tracing
 // them via a conservatively found pointer. Tracing dead objects could lead to
 // tracing of already finalized objects in another thread's heap which is a
 // use-after-free situation.
 const size_t deadBitMask = 4;
 // On free-list entries we reuse the dead bit to distinguish a normal free-list
 // entry from one that has been promptly freed.
@@ skipping 88 matching lines @@
 // In order to use the same memory allocation routines for everything
 // allocated in the heap, large objects are considered heap pages
 // containing only one object.
 //
 // The layout of a large heap object is as follows:
 //
 // | BaseHeapPage | next pointer | FinalizedHeapObjectHeader or HeapObjectHeader | payload |
 template<typename Header>
 class LargeHeapObject : public BaseHeapPage {
 public:
-    LargeHeapObject(PageMemory* storage, const GCInfo* gcInfo, ThreadState* state) : BaseHeapPage(storage, gcInfo, state)
+    LargeHeapObject(PageMemory* storage, const GCInfo* gcInfo, ThreadState* state)
+        : BaseHeapPage(storage, gcInfo, state)
+        , m_next(nullptr)
+        , m_marked(false)
     {
         COMPILE_ASSERT(!(sizeof(LargeHeapObject<Header>) & allocationMask), large_heap_object_header_misaligned);
     }
 
     virtual void checkAndMarkPointer(Visitor*, Address) override;
     virtual bool isLargeObject() override { return true; }
 
+    virtual void markObject(Address address) override
+    {
+        ASSERT(!m_marked);
+        m_marked = true;
+    }
+
+    virtual bool objectIsMarked(Address address) override
+    {
+        return m_marked;
+    }
+
+    void clearObjectMarkBitMap()
+    {
+        m_marked = false;
+    }
+
 #if ENABLE(GC_PROFILE_MARKING)
     virtual const GCInfo* findGCInfo(Address address)
     {
         if (!objectContains(address))
             return 0;
         return gcInfo();
     }
 #endif
 
 #if ENABLE(GC_PROFILE_HEAP)
@@ skipping 38 matching lines @@
 
     Address payload() { return heapObjectHeader()->payload(); }
     size_t payloadSize() { return heapObjectHeader()->payloadSize(); }
 
     Header* heapObjectHeader()
     {
         Address headerAddress = address() + sizeof(LargeHeapObject<Header>) + headerPadding<Header>();
         return reinterpret_cast<Header*>(headerAddress);
     }
 
+    void mark(Visitor*);
     bool isMarked();
-    void unmark();
+
     size_t objectPayloadSizeForTesting();
-    void mark(Visitor*);
     void finalize();
     void setDeadMark();
     virtual void markOrphaned()
     {
         // Zap the payload with a recognizable value to detect any incorrect
         // cross thread pointer usage.
         memset(payload(), orphanedZapValue, payloadSize());
         BaseHeapPage::markOrphaned();
     }
 
 private:
     friend class ThreadHeap<Header>;
 
     LargeHeapObject<Header>* m_next;
+    bool m_marked;
 };
 
 // The BasicObjectHeader is the minimal object header. It is used when
 // encountering heap space of size allocationGranularity to mark it as
 // as freelist entry.
 class PLATFORM_EXPORT BasicObjectHeader {
 public:
     NO_SANITIZE_ADDRESS
     explicit BasicObjectHeader(size_t encodedSize)
         : m_size(encodedSize) { }
@@ skipping 57 matching lines @@
 
     NO_SANITIZE_ADDRESS
     HeapObjectHeader(size_t encodedSize, const GCInfo*)
         : BasicObjectHeader(encodedSize)
 #if ENABLE(ASSERT)
         , m_magic(magic)
 #endif
     { }
 
     inline void checkHeader() const;
-    inline bool isMarked() const;
 
     inline void mark();
-    inline void unmark();
+    inline bool isMarked() const;
 
     inline const GCInfo* gcInfo() { return 0; }
 
     inline Address payload();
     inline size_t payloadSize();
     inline Address payloadEnd();
 
     inline void setDeadMark();
     inline void clearDeadMark();
     inline bool hasDeadMark() const;
@@ skipping 133 matching lines @@
 template<typename Header>
 class HeapPage : public BaseHeapPage {
 public:
     HeapPage(PageMemory*, ThreadHeap<Header>*, const GCInfo*);
 
     void link(HeapPage**);
     static void unlink(ThreadHeap<Header>*, HeapPage*, HeapPage**);
 
     bool isEmpty();
 
+    virtual void markObject(Address object) override
+    {
+        size_t offset = (object - payload()) / allocationGranularity;
+        ASSERT(!((object - payload()) & allocationMask));
+        ASSERT(!(m_objectMarkBitMap[offset / 8] & (1 << (offset & 7))));
+        m_objectMarkBitMap[offset / 8] |= (1 << (offset & 7));
+    }
+
+    virtual bool objectIsMarked(Address object) override
+    {
+        size_t offset = (object - payload()) / allocationGranularity;
+        ASSERT(!((object - payload()) & allocationMask));
+        return m_objectMarkBitMap[offset / 8] & (1 << (offset & 7));
+    }
+
+    void clearObjectMarkBitMap();
+
     // Returns true for the whole blinkPageSize page that the page is on, even
     // for the header, and the unmapped guard page at the start. That ensures
     // the result can be used to populate the negative page cache.
     virtual bool contains(Address addr) override
     {
         Address blinkPageStart = roundToBlinkPageStart(address());
         ASSERT(blinkPageStart == address() - WTF::kSystemPageSize); // Page is at aligned address plus guard page size.
         return blinkPageStart <= addr && addr < blinkPageStart + blinkPageSize;
     }
 
     HeapPage* next() { return m_next; }
 
     Address payload()
     {
         return address() + sizeof(*this) + headerPadding<Header>();
     }
 
     static size_t payloadSize()
     {
         return (blinkPagePayloadSize() - sizeof(HeapPage) - headerPadding<Header>()) & ~allocationMask;
     }
 
     Address end() { return payload() + payloadSize(); }
 
     size_t objectPayloadSizeForTesting();
-    void clearLiveAndMarkDead();
+    void makeUnmarkedObjectsDead();
     void sweep(ThreadHeap<Header>*);
     void clearObjectStartBitMap();
     void finalize(Header*);
     virtual void checkAndMarkPointer(Visitor*, Address) override;
 #if ENABLE(GC_PROFILE_MARKING)
     const GCInfo* findGCInfo(Address) override;
 #endif
 #if ENABLE(GC_PROFILE_HEAP)
     virtual void snapshot(TracedValue*, ThreadState::SnapshotInfo*);
 #endif
@@ skipping 23 matching lines @@
     void populateObjectStartBitMap();
     bool isObjectStartBitMapComputed() { return m_objectStartBitMapComputed; }
     TraceCallback traceCallback(Header*);
     bool hasVTable(Header*);
 
     intptr_t padding() const { return m_padding; }
 
     HeapPage<Header>* m_next;
     intptr_t m_padding; // Preserve 8-byte alignment on 32-bit systems.
     bool m_objectStartBitMapComputed;
-    uint8_t m_objectStartBitMap[reservedForObjectBitMap];
+    uint8_t m_objectStartBitMap[reservedForObjectStartBitMap];
+    uint8_t m_objectMarkBitMap[reservedForObjectMarkBitMap];
 
     friend class ThreadHeap<Header>;
 };
 
 // A HeapDoesNotContainCache provides a fast way of taking an arbitrary
 // pointer-sized word, and determining whether it cannot be interpreted
 // as a pointer to an area that is managed by the garbage collected
 // Blink heap. This is a cache of 'pages' that have previously been
 // determined to be wholly outside of the heap. The size of these pages must be
 // smaller than the allocation alignment of the heap pages. We determine
@@ skipping 107 matching lines @@
 #if ENABLE(GC_PROFILE_HEAP)
     virtual void snapshot(TracedValue*, ThreadState::SnapshotInfo*) = 0;
 #endif
 
     // Sweep this part of the Blink heap. This finalizes dead objects
     // and builds freelists for all the unused memory.
     virtual void sweep() = 0;
     virtual void postSweepProcessing() = 0;
 
     virtual void clearFreeLists() = 0;
-    virtual void clearLiveAndMarkDead() = 0;
+    virtual void clearObjectMarkBitMaps() = 0;
+    virtual void makeUnmarkedObjectsDead() = 0;
 
     virtual void makeConsistentForSweeping() = 0;
 #if ENABLE(ASSERT)
     virtual bool isConsistentForSweeping() = 0;
 #endif
     virtual size_t objectPayloadSizeForTesting() = 0;
 
     virtual void updateRemainingAllocationSize() = 0;
 
     virtual void prepareHeapForTermination() = 0;
@@ skipping 46 matching lines @@
     virtual const GCInfo* findGCInfoOfLargeHeapObject(Address) override;
 #endif
 #if ENABLE(GC_PROFILE_HEAP)
     virtual void snapshot(TracedValue*, ThreadState::SnapshotInfo*) override;
 #endif
 
     virtual void sweep() override;
     virtual void postSweepProcessing() override;
 
     virtual void clearFreeLists() override;
-    virtual void clearLiveAndMarkDead() override;
+    virtual void clearObjectMarkBitMaps() override;
+    virtual void makeUnmarkedObjectsDead() override;
 
     virtual void makeConsistentForSweeping() override;
 #if ENABLE(ASSERT)
     virtual bool isConsistentForSweeping() override;
 #endif
     virtual size_t objectPayloadSizeForTesting() override;
 
     virtual void updateRemainingAllocationSize() override;
 
     ThreadState* threadState() { return m_threadState; }
@@ skipping 525 matching lines @@
 size_t HeapObjectHeader::payloadSize()
 {
     return size() - objectHeaderSize;
 }
 
 Address HeapObjectHeader::payloadEnd()
 {
     return reinterpret_cast<Address>(this) + size();
 }
 
-NO_SANITIZE_ADDRESS
 void HeapObjectHeader::mark()
 {
     checkHeader();
-    m_size = m_size | markBitMask;
+    pageHeaderFromObject(this)->markObject(reinterpret_cast<Address>(this));
 }
 
 Address FinalizedHeapObjectHeader::payload()
 {
     return reinterpret_cast<Address>(this) + finalizedHeaderSize;
 }
 
 size_t FinalizedHeapObjectHeader::payloadSize()
 {
     return size() - finalizedHeaderSize;
@@ skipping 1030 matching lines @@
 template<typename T, size_t inlineCapacity>
 struct GCInfoTrait<HeapVector<T, inlineCapacity> > : public GCInfoTrait<Vector<T, inlineCapacity, HeapAllocator> > { };
 template<typename T, size_t inlineCapacity>
 struct GCInfoTrait<HeapDeque<T, inlineCapacity> > : public GCInfoTrait<Deque<T, inlineCapacity, HeapAllocator> > { };
 template<typename T, typename U, typename V>
 struct GCInfoTrait<HeapHashCountedSet<T, U, V> > : public GCInfoTrait<HashCountedSet<T, U, V, HeapAllocator> > { };
 
 } // namespace blink
 
 #endif // Heap_h