Profile FreeList

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 63 matching lines @@
 // 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.
 const size_t promptlyFreedMask = freeListMask | deadBitMask;
-#if ENABLE(GC_PROFILE_HEAP)
+//#if ENABLE(GC_PROFILE_HEAP)
 const size_t heapObjectGenerations = 8;
 const size_t maxHeapObjectAge = heapObjectGenerations - 1;
 const size_t heapObjectAgeMask = ~(maxHeapObjectSize - 1);
 const size_t sizeMask = ~heapObjectAgeMask & ~static_cast<size_t>(7);
-#else
-const size_t sizeMask = ~static_cast<size_t>(7);
-#endif
+//#else
+//const size_t sizeMask = ~static_cast<size_t>(7);
+//#endif
 const uint8_t freelistZapValue = 42;
 const uint8_t finalizedZapValue = 24;
 // The orphaned zap value must be zero in the lowest bits to allow for using
 // the mark bit when tracing.
 const uint8_t orphanedZapValue = 240;
 const int numberOfPagesToConsiderForCoalescing = 100;
 
 #if ENABLE(ASSERT) || defined(LEAK_SANITIZER) || defined(ADDRESS_SANITIZER)
 #define FILL_ZERO_IF_PRODUCTION(address, size) do { } while (false)
 #define FILL_ZERO_IF_NOT_PRODUCTION(address, size) memset((address), 0, (size))
 #else
 #define FILL_ZERO_IF_PRODUCTION(address, size) memset((address), 0, (size))
 #define FILL_ZERO_IF_NOT_PRODUCTION(address, size) do { } while (false)
 #endif
 
 class CallbackStack;
 class PageMemory;
 template<ThreadAffinity affinity> class ThreadLocalPersistents;
 template<typename T, typename RootsAccessor = ThreadLocalPersistents<ThreadingTrait<T>::Affinity>> class Persistent;
 
-#if ENABLE(GC_PROFILE_HEAP)
+#if ENABLE(GC_PROFILE_HEAP) || ENABLE(GC_PROFILE_FREE_LIST)
 class TracedValue;
 #endif
 
 // Blink heap pages are set up with a guard page before and after the payload.
 inline size_t blinkPagePayloadSize()
 {
     return blinkPageSize - 2 * WTF::kSystemPageSize;
 }
 
 // Blink heap pages are aligned to the Blink heap page size.
@@ skipping 215 matching lines @@
 
     static void finalize(const GCInfo*, Address, size_t);
     static HeapObjectHeader* fromPayload(const void*);
 
     static const uint32_t magic = 0xc0de247;
     static const uint32_t zappedMagic = 0xC0DEdead;
     // The zap value for vtables should be < 4K to ensure it cannot be
     // used for dispatch.
     static const intptr_t zappedVTable = 0xd0d;
 
-#if ENABLE(GC_PROFILE_HEAP)
+    //#if ENABLE(GC_PROFILE_HEAP)
     NO_SANITIZE_ADDRESS
     size_t encodedSize() const { return m_size; }
 
     NO_SANITIZE_ADDRESS
     size_t age() const { return m_size >> maxHeapObjectSizeLog2; }
 
     NO_SANITIZE_ADDRESS
     void incAge()
     {
         size_t current = age();
         if (current < maxHeapObjectAge)
             m_size = ((current + 1) << maxHeapObjectSizeLog2) | (m_size & ~heapObjectAgeMask);
     }
-#endif
+    //#endif
 
 private:
     volatile uint32_t m_size;
 #if ENABLE(ASSERT)
     uint32_t m_magic;
 #endif
 };
 
 inline HeapObjectHeader* HeapObjectHeader::fromPayload(const void* payload)
 {
@@ skipping 168 matching lines @@
     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
 
+    void countUnmarkedObjects();
+
 #if defined(ADDRESS_SANITIZER)
     void poisonUnmarkedObjects();
 #endif
 
     virtual void markOrphaned() override
     {
         // Zap the payload with a recognizable value to detect any incorrect
         // cross thread pointer usage.
 #if defined(ADDRESS_SANITIZER)
         // This needs to zap poisoned memory as well.
@@ skipping 127 matching lines @@
 
     // Find the page in this thread heap containing the given
     // address.  Returns 0 if the address is not contained in any
     // page in this thread heap.
     virtual BaseHeapPage* pageFromAddress(Address) = 0;
 
 #if ENABLE(GC_PROFILE_MARKING)
     virtual const GCInfo* findGCInfoOfLargeObject(Address) = 0;
 #endif
 
+#if ENABLE(GC_PROFILE_FREE_LIST)
+    virtual void snapshotFreeList(TracedValue*) = 0;
+#endif
+
 #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 markUnmarkedObjectsDead() = 0;
 
     virtual void makeConsistentForSweeping() = 0;
 #if ENABLE(ASSERT)
     virtual bool isConsistentForSweeping() = 0;
 #endif
     virtual size_t objectPayloadSizeForTesting() = 0;
 
     virtual void prepareHeapForTermination() = 0;
 };
 
 template<typename Header>
 class FreeList {
 public:
     FreeList();
 
     void addToFreeList(Address, size_t);
     void clear();
+    FreeListEntry* takeEntry(size_t allocationSize);
+
+#if ENABLE(GC_PROFILE_FREE_LIST)
+    void countBucketSizes(size_t[], size_t[], size_t* freeSize) const;
+#endif
 
     // Returns a bucket number for inserting a FreeListEntry of a given size.
     // All FreeListEntries in the given bucket, n, have size >= 2^n.
     static int bucketIndexForSize(size_t);
 
 private:
     int m_biggestFreeListIndex;
 
     // All FreeListEntries in the nth list have size >= 2^n.
     FreeListEntry* m_freeLists[blinkPageSizeLog2];
 
+#if ENABLE(ASSERT)
     friend class ThreadHeap<Header>;
+#endif
 };
 
 // Thread heaps represent a part of the per-thread Blink heap.
 //
 // Each Blink thread has a number of thread heaps: one general heap
 // that contains any type of object and a number of heaps specialized
 // for specific object types (such as Node).
 //
 // Each thread heap contains the functionality to allocate new objects
 // (potentially adding new pages to the heap), to find and mark
 // objects during conservative stack scanning and to sweep the set of
 // pages after a GC.
 template<typename Header>
 class ThreadHeap : public BaseHeap {
 public:
     ThreadHeap(ThreadState*, int);
     virtual ~ThreadHeap();
     virtual void cleanupPages() override;
 
     virtual BaseHeapPage* pageFromAddress(Address) override;
 #if ENABLE(GC_PROFILE_MARKING)
     virtual const GCInfo* findGCInfoOfLargeObject(Address) override;
 #endif
+#if ENABLE(GC_PROFILE_FREE_LIST)
+    virtual void snapshotFreeList(TracedValue*) 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 markUnmarkedObjectsDead() override;
 
     virtual void makeConsistentForSweeping() override;
 #if ENABLE(ASSERT)
     virtual bool isConsistentForSweeping() override;
 #endif
     virtual size_t objectPayloadSizeForTesting() override;
 
     ThreadState* threadState() { return m_threadState; }
 
     void addToFreeList(Address address, size_t size)
     {
         ASSERT(pageFromAddress(address));
         ASSERT(pageFromAddress(address + size - 1));
         m_freeList.addToFreeList(address, size);
     }
 
-    inline Address allocate(size_t payloadSize, const GCInfo*);
+    inline Address allocate(size_t, const GCInfo*);
     inline static size_t roundedAllocationSize(size_t size)
     {
         return allocationSizeFromSize(size) - sizeof(Header);
     }
 
     virtual void prepareHeapForTermination() override;
 
     void removePageFromHeap(HeapPage<Header>*);
 
     PLATFORM_EXPORT void promptlyFreeObject(Header*);
     PLATFORM_EXPORT bool expandObject(Header*, size_t);
     void shrinkObject(Header*, size_t);
 
 private:
     void addPageToHeap(const GCInfo*);
-    PLATFORM_EXPORT Address outOfLineAllocate(size_t allocationSize, const GCInfo*);
+    PLATFORM_EXPORT Address outOfLineAllocate(size_t payloadSize, size_t allocationSize, const GCInfo*);
     static size_t allocationSizeFromSize(size_t);
     PLATFORM_EXPORT Address allocateLargeObject(size_t, const GCInfo*);
     Address currentAllocationPoint() const { return m_currentAllocationPoint; }
     size_t remainingAllocationSize() const { return m_remainingAllocationSize; }
     bool hasCurrentAllocationArea() const { return currentAllocationPoint() && remainingAllocationSize(); }
     void setAllocationPoint(Address point, size_t size)
     {
+#if ENABLE(GC_PROFILE_FREE_LIST)
+        m_allocationPointSizeSum += size;
+        ++m_setAllocationPointCount;
+#endif
         ASSERT(!point || pageFromAddress(point));
         ASSERT(size <= HeapPage<Header>::payloadSize());
         if (hasCurrentAllocationArea())
             addToFreeList(currentAllocationPoint(), remainingAllocationSize());
         updateRemainingAllocationSize();
         m_currentAllocationPoint = point;
         m_lastRemainingAllocationSize = m_remainingAllocationSize = size;
     }
     void updateRemainingAllocationSize();
-    Address allocateFromFreeList(size_t, const GCInfo*);
+    bool allocateFromFreeList(size_t);
 
     void freeLargeObject(LargeObject<Header>*, LargeObject<Header>**);
     void allocatePage(const GCInfo*);
 
-    inline Address allocateSize(size_t allocationSize, const GCInfo*);
-    inline Address allocateAtAddress(Address, size_t allocationSize, const GCInfo*);
-
 #if ENABLE(ASSERT)
     bool pagesToBeSweptContains(Address);
     bool pagesAllocatedDuringSweepingContains(Address);
 #endif
 
     void sweepNormalPages();
     void sweepLargePages();
     bool coalesce(size_t);
 
     Address m_currentAllocationPoint;
     size_t m_remainingAllocationSize;
     size_t m_lastRemainingAllocationSize;
 
+    double m_totalAllocationSize;
+    size_t m_allocationCount;
+    size_t m_inlineAllocationCount;
+
     HeapPage<Header>* m_firstPage;
     LargeObject<Header>* m_firstLargeObject;
 
     HeapPage<Header>* m_firstPageAllocatedDuringSweeping;
     HeapPage<Header>* m_lastPageAllocatedDuringSweeping;
 
     LargeObject<Header>* m_firstLargeObjectAllocatedDuringSweeping;
     LargeObject<Header>* m_lastLargeObjectAllocatedDuringSweeping;
 
     ThreadState* m_threadState;
 
     FreeList<Header> m_freeList;
 
     // Index into the page pools.  This is used to ensure that the pages of the
     // same type go into the correct page pool and thus avoid type confusion.
     int m_index;
 
     // The promptly freed count contains the number of promptly freed objects
     // since the last sweep or since it was manually reset to delay coalescing.
     size_t m_promptlyFreedCount;
+
+#if ENABLE(GC_PROFILE_FREE_LIST)
+    size_t m_allocationPointSizeSum = 0;

[keishi, 2015/01/27 08:59:01]

Used to report average allocation point size between snapshots. Wasn't very
helpful so I think we don't need this metric.

+    size_t m_setAllocationPointCount = 0;
+#endif
 };
 
 class PLATFORM_EXPORT Heap {
 public:
     static void init();
     static void shutdown();
     static void doShutdown();
 
     static BaseHeapPage* contains(Address);
     static BaseHeapPage* contains(void* pointer) { return contains(reinterpret_cast<Address>(pointer)); }
@@ skipping 56 matching lines @@
     static void collectAllGarbage();
 
     static void processMarkingStack(Visitor*);
     static void postMarkingProcessing(Visitor*);
     static void globalWeakProcessing(Visitor*);
     static void setForcePreciseGCForTesting();
 
     static void preGC();
     static void postGC();
 
+    static void reportSweepingStats();
+
     // Conservatively checks whether an address is a pointer in any of the
     // thread heaps.  If so marks the object pointed to as live.
     static Address checkAndMarkPointer(Visitor*, Address);
 
 #if ENABLE(GC_PROFILE_MARKING)
     // Dump the path to specified object on the next GC.  This method is to be
     // invoked from GDB.
     static void dumpPathToObjectOnNextGC(void* p);
 
     // Forcibly find GCInfo of the object at Address.  This is slow and should
@@ skipping 329 matching lines @@
     // therefore has to happen before any calculation on the size.
     RELEASE_ASSERT(size < maxHeapObjectSize);
 
     // Add space for header.
     size_t allocationSize = size + sizeof(Header);
     // Align size with allocation granularity.
     allocationSize = (allocationSize + allocationMask) & ~allocationMask;
     return allocationSize;
 }
 
-
-template<typename Header>
-inline Address ThreadHeap<Header>::allocateAtAddress(Address headerAddress, size_t allocationSize, const GCInfo* gcInfo)
-{
-    new (NotNull, headerAddress) Header(allocationSize, gcInfo);
-    Address result = headerAddress + sizeof(Header);
-    ASSERT(!(reinterpret_cast<uintptr_t>(result) & allocationMask));
-
-    // Unpoison the memory used for the object (payload).
-    ASAN_UNPOISON_MEMORY_REGION(result, allocationSize - sizeof(Header));
-    FILL_ZERO_IF_NOT_PRODUCTION(result, allocationSize - sizeof(Header));
-    ASSERT(pageFromAddress(headerAddress + allocationSize - 1));
-    return result;
-}
-
-template<typename Header>
-Address ThreadHeap<Header>::allocateSize(size_t allocationSize, const GCInfo* gcInfo)
-{
-    if (LIKELY(allocationSize <= m_remainingAllocationSize)) {
-        Address headerAddress = m_currentAllocationPoint;
-        m_currentAllocationPoint += allocationSize;
-        m_remainingAllocationSize -= allocationSize;
-        return allocateAtAddress(headerAddress, allocationSize, gcInfo);
-    }
-    return outOfLineAllocate(allocationSize, gcInfo);
-}
-
 template<typename Header>
 Address ThreadHeap<Header>::allocate(size_t size, const GCInfo* gcInfo)
 {
-    return allocateSize(allocationSizeFromSize(size), gcInfo);
+    size_t allocationSize = allocationSizeFromSize(size);
+    m_totalAllocationSize += allocationSize;
+    m_allocationCount++;
+    if (LIKELY(allocationSize <= m_remainingAllocationSize)) {
+        m_inlineAllocationCount++;
+        Address headerAddress = m_currentAllocationPoint;
+        m_currentAllocationPoint += allocationSize;
+        m_remainingAllocationSize -= allocationSize;
+        new (NotNull, headerAddress) Header(allocationSize, gcInfo);
+        Address result = headerAddress + sizeof(Header);
+        ASSERT(!(reinterpret_cast<uintptr_t>(result) & allocationMask));
+
+        // Unpoison the memory used for the object (payload).
+        ASAN_UNPOISON_MEMORY_REGION(result, allocationSize - sizeof(Header));
+        FILL_ZERO_IF_NOT_PRODUCTION(result, allocationSize - sizeof(Header));
+        ASSERT(pageFromAddress(headerAddress + allocationSize - 1));
+        return result;
+    }
+    return outOfLineAllocate(size, allocationSize, gcInfo);
 }
 
 template<typename T, typename HeapTraits>
 Address Heap::allocate(size_t size)
 {
     ThreadState* state = ThreadStateFor<ThreadingTrait<T>::Affinity>::state();
     ASSERT(state->isAllocationAllowed());
     const GCInfo* gcInfo = GCInfoTrait<T>::get();
     int heapIndex = HeapTraits::index(gcInfo->hasFinalizer(), size);
     BaseHeap* heap = state->heap(heapIndex);
@@ skipping 1022 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