Profile FreeList

Source/platform/heap/Heap.cpp

 /*
  * 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 31 matching lines @@
 #include "wtf/LeakAnnotations.h"
 #include "wtf/PassOwnPtr.h"
 #if ENABLE(GC_PROFILE_MARKING)
 #include "wtf/HashMap.h"
 #include "wtf/HashSet.h"
 #include "wtf/text/StringBuilder.h"
 #include "wtf/text/StringHash.h"
 #include <stdio.h>
 #include <utility>
 #endif
-#if ENABLE(GC_PROFILE_HEAP)
+#if ENABLE(GC_PROFILE_HEAP) || ENABLE(GC_PROFILE_FREE_LIST) || ENABLE(GC_PROFILE_MARKING)
 #include "platform/TracedValue.h"
 #endif
 
 #if OS(POSIX)
 #include <sys/mman.h>
 #include <unistd.h>
 #elif OS(WIN)
 #include <windows.h>
 #endif
 
 namespace blink {
 
+struct AgeHistogram {
+    int data[8];
+};
+
+typedef HashMap<String, AgeHistogram> ObjectAgeMap;
+
+static ObjectAgeMap& uom()
+{
+    static ObjectAgeMap uomap;
+    return uomap;
+}
+
+static Mutex& uomMutex()
+{
+    AtomicallyInitializedStatic(Mutex&, mutex = *new Mutex);
+    return mutex;
+}
+
+static ObjectAgeMap& mom()
+{
+    static ObjectAgeMap momap;
+    return momap;
+}
+
+static Mutex& momMutex()
+{
+    AtomicallyInitializedStatic(Mutex&, mutex = *new Mutex);
+    return mutex;
+}
+
 #if ENABLE(GC_PROFILE_MARKING)
 static String classOf(const void* object)
 {
     const GCInfo* gcInfo = Heap::findGCInfo(reinterpret_cast<Address>(const_cast<void*>(object)));
     if (gcInfo)
         return gcInfo->m_className;
 
     return "unknown";
 }
 #endif
@@ skipping 559 matching lines @@
     FinalizedHeapObjectHeader* header =
         reinterpret_cast<FinalizedHeapObjectHeader*>(addr - finalizedHeaderSize);
     return header;
 }
 
 template<typename Header>
 ThreadHeap<Header>::ThreadHeap(ThreadState* state, int index)
     : m_currentAllocationPoint(0)
     , m_remainingAllocationSize(0)
     , m_lastRemainingAllocationSize(0)
+#if ENABLE(GC_PROFILE_FREE_LIST)
+    , m_totalAllocationSize(0.0)
+    , m_allocationCount(0)
+    , m_inlineAllocationCount(0)
+#endif
     , m_firstPage(0)
     , m_firstLargeObject(0)
     , m_firstPageAllocatedDuringSweeping(0)
     , m_lastPageAllocatedDuringSweeping(0)
     , m_firstLargeObjectAllocatedDuringSweeping(0)
     , m_lastLargeObjectAllocatedDuringSweeping(0)
     , m_threadState(state)
     , m_index(index)
     , m_numberOfNormalPages(0)
     , m_promptlyFreedCount(0)
@@ skipping 39 matching lines @@
     if (m_lastRemainingAllocationSize > remainingAllocationSize()) {
         Heap::increaseAllocatedObjectSize(m_lastRemainingAllocationSize - remainingAllocationSize());
         m_lastRemainingAllocationSize = remainingAllocationSize();
     }
     ASSERT(m_lastRemainingAllocationSize == remainingAllocationSize());
 }
 
 template<typename Header>
 Address ThreadHeap<Header>::outOfLineAllocate(size_t payloadSize, size_t allocationSize, const GCInfo* gcInfo)
 {
+#if ENABLE(GC_PROFILE_FREE_LIST)
+    m_threadState->snapshotFreeListIfNecessary();
+#endif
     ASSERT(allocationSize > remainingAllocationSize());
     if (allocationSize > blinkPageSize / 2)
         return allocateLargeObject(allocationSize, gcInfo);
 
     updateRemainingAllocationSize();
     if (threadState()->shouldGC()) {
         if (threadState()->shouldForceConservativeGC())
             Heap::collectGarbage(ThreadState::HeapPointersOnStack);
         else
             threadState()->setGCRequested();
@@ skipping 79 matching lines @@
 const GCInfo* ThreadHeap<Header>::findGCInfoOfLargeObject(Address address)
 {
     for (LargeObject<Header>* largeObject = m_firstLargeObject; largeObject; largeObject = largeObject->next()) {
         if (largeObject->contains(address))
             return largeObject->gcInfo();
     }
     return 0;
 }
 #endif
 
+#if ENABLE(GC_PROFILE_FREE_LIST)
+template<typename Header>
+void ThreadHeap<Header>::snapshotFreeList(TracedValue* json)
+{
+    json->setDouble("totalAllocationSize", m_totalAllocationSize);
+    json->setDouble("inlineAllocationRate", static_cast<double>(m_inlineAllocationCount) / m_allocationCount);
+    json->setInteger("inlineAllocationCount", m_inlineAllocationCount);
+    json->setInteger("allocationCount", m_allocationCount);
+    if (m_setAllocationPointCount > 0) {
+      json->setDouble("averageAllocationPointSize", static_cast<double>(m_allocationPointSizeSum) / m_setAllocationPointCount);
+    }
+    m_allocationPointSizeSum = 0;
+    m_setAllocationPointCount = 0;
+    size_t pageCount = 0;
+    size_t totalPageSize = 0;
+    for (HeapPage<Header>* page = m_firstPage; page; page = page->next()) {
+        ++pageCount;
+        totalPageSize += page->payloadSize();
+    }
+    json->setInteger("pageCount", pageCount);
+    json->setInteger("totalPageSize", totalPageSize);
+    size_t bucketSizes[blinkPageSizeLog2];
+    size_t bucketTotalSizes[blinkPageSizeLog2];
+    size_t freeSize = 0;
+    m_freeList.countBucketSizes(bucketSizes, bucketTotalSizes, &freeSize);
+    json->setInteger("freeSize", freeSize);
+    json->beginArray("bucketSizes");
+    for (size_t i = 0; i < blinkPageSizeLog2; ++i) {
+        json->pushInteger(bucketSizes[i]);
+    }
+    json->endArray();
+    json->beginArray("bucketTotalSizes");
+    for (size_t i = 0; i < blinkPageSizeLog2; ++i) {
+        json->pushInteger(bucketTotalSizes[i]);
+    }
+    json->endArray();
+}
+#endif
+
 #if ENABLE(GC_PROFILE_HEAP)
 #define GC_PROFILE_HEAP_PAGE_SNAPSHOT_THRESHOLD 0
 template<typename Header>
 void ThreadHeap<Header>::snapshot(TracedValue* json, ThreadState::SnapshotInfo* info)
 {
     size_t previousPageCount = info->pageCount;
 
     json->beginArray("pages");
     for (HeapPage<Header>* page = m_firstPage; page; page = page->next(), ++info->pageCount) {
         // FIXME: To limit the size of the snapshot we only output "threshold" many page snapshots.
@@ skipping 47 matching lines @@
         return;
 #endif
     int index = bucketIndexForSize(size);
     entry->link(&m_freeLists[index]);
     if (!m_lastFreeListEntries[index])
         m_lastFreeListEntries[index] = entry;
     if (index > m_biggestFreeListIndex)
         m_biggestFreeListIndex = index;
 }
 
+#if ENABLE(GC_PROFILE_FREE_LIST)
+template<typename Header>
+void FreeList<Header>::countBucketSizes(size_t sizes[], size_t totalSizes[], size_t* freeSize) const
+{
+    *freeSize = 0;
+    for (size_t i = 0; i < blinkPageSizeLog2; i++) {
+        sizes[i] = 0;
+        totalSizes[i] = 0;
+        FreeListEntry* entry = m_freeLists[i];
+        while (entry) {
+            ++sizes[i];
+            *freeSize += entry->size();
+            totalSizes[i] += entry->size();
+            entry = entry->next();
+        }
+    }
+}
+#endif
+
 template<typename Header>
 bool ThreadHeap<Header>::expandObject(Header* header, size_t newSize)
 {
     ASSERT(header->payloadSize() < newSize);
     size_t allocationSize = allocationSizeFromSize(newSize);
     ASSERT(allocationSize > header->size());
     size_t expandSize = allocationSize - header->size();
     if (header->payloadEnd() == m_currentAllocationPoint && expandSize <= m_remainingAllocationSize) {
         m_currentAllocationPoint += expandSize;
         m_remainingAllocationSize -= expandSize;
@@ skipping 558 matching lines @@
 // STRICT_ASAN_FINALIZATION_CHECKING turns on poisoning of all objects during
 // sweeping to catch cases where dead objects touch each other. This is not
 // turned on by default because it also triggers for cases that are safe.
 // Examples of such safe cases are context life cycle observers and timers
 // embedded in garbage collected objects.
 #define STRICT_ASAN_FINALIZATION_CHECKING 0
 
 template<typename Header>
 void ThreadHeap<Header>::sweep()
 {
+    for (HeapPage<Header>* page = m_firstPage; page; page = page->next()) {
+        page->countUnmarkedObjects();
+    }
     ASSERT(isConsistentForSweeping());
 #if defined(ADDRESS_SANITIZER) && STRICT_ASAN_FINALIZATION_CHECKING
     // When using ASan do a pre-sweep where all unmarked objects are
     // poisoned before calling their finalizer methods. This can catch
     // the case where the finalizer of an object tries to modify
     // another object as part of finalization.
     for (HeapPage<Header>* page = m_firstPage; page; page = page->next())
         page->poisonUnmarkedObjects();
 #endif
     sweepNormalPages();
@@ skipping 371 matching lines @@
         Header* header = reinterpret_cast<Header*>(headerAddress);
         ASSERT(header->size() < blinkPagePayloadSize());
 
         if (!header->isFree() && !header->isMarked())
             ASAN_POISON_MEMORY_REGION(header->payload(), header->payloadSize());
         headerAddress += header->size();
     }
 }
 #endif
 
+template<typename Header>
+void HeapPage<Header>::countUnmarkedObjects()
+{
+    MutexLocker locker(uomMutex());
+    for (Address headerAddress = payload(); headerAddress < end(); ) {
+        Header* header = reinterpret_cast<Header*>(headerAddress);
+        ASSERT(header->size() < blinkPagePayloadSize());
+
+        if (!header->isFree() && !header->isMarked()) {
+            String className(classOf(header->payload()));
+            ObjectAgeMap::AddResult result = uom().add(className, AgeHistogram());
+            result.storedValue->value.data[header->age()]++;
+        }
+        headerAddress += header->size();
+    }
+}
+
 template<>
 inline void HeapPage<FinalizedHeapObjectHeader>::finalize(FinalizedHeapObjectHeader* header)
 {
     header->finalize();
 }
 
 template<>
 inline void HeapPage<HeapObjectHeader>::finalize(HeapObjectHeader* header)
 {
     ASSERT(gcInfo());
@@ skipping 141 matching lines @@
             // when doing weakness for ephemerons. Hence we only check
             // when called within.
             ASSERT(!ThreadState::isAnyThreadInGC() || Heap::containedInHeapOrOrphanedPage(header));
         }
 #endif
         ASSERT(objectPointer);
         if (header->isMarked())
             return;
         header->mark();
 #if ENABLE(GC_PROFILE_MARKING)
+        header->incAge();
+        
         MutexLocker locker(objectGraphMutex());
         String className(classOf(objectPointer));
         {
             LiveObjectMap::AddResult result = currentlyLive().add(className, LiveObjectSet());
             result.storedValue->value.add(reinterpret_cast<uintptr_t>(objectPointer));
         }
+        {
+            MutexLocker locker(momMutex());
+            ObjectAgeMap::AddResult result = mom().add(className, AgeHistogram());
+            result.storedValue->value.data[header->age()]++;
+        }
         ObjectGraph::AddResult result = objectGraph().add(reinterpret_cast<uintptr_t>(objectPointer), std::make_pair(reinterpret_cast<uintptr_t>(m_hostObject), m_hostName));
         ASSERT(result.isNewEntry);
         // fprintf(stderr, "%s[%p] -> %s[%p]\n", m_hostName.ascii().data(), m_hostObject, className.ascii().data(), objectPointer);
 #endif
         if (callback)
             Heap::pushTraceCallback(m_markingStack, const_cast<void*>(objectPointer), callback);
     }
 
     virtual void mark(HeapObjectHeader* header, TraceCallback callback) override
     {
@@ skipping 76 matching lines @@
         }
 
         previouslyLive().swap(currentlyLive());
         currentlyLive().clear();
 
         for (HashSet<uintptr_t>::iterator it = objectsToFindPath().begin(), end = objectsToFindPath().end(); it != end; ++it) {
             dumpPathToObjectFromObjectGraph(objectGraph(), *it);
         }
     }
 
+    void reportMarkingStats()
+    {
+        MutexLocker locker(momMutex());
+        RefPtr<TracedValue> json = TracedValue::create();
+        for (ObjectAgeMap::iterator it = mom().begin(), end = mom().end(); it != end; ++it) {
+            json->beginArray(it->key.ascii().data());
+            for (size_t i = 0; i < 8; ++i) {
+                json->pushInteger(it->value.data[i]);
+            }
+            json->endArray();
+        }
+        TRACE_EVENT_OBJECT_SNAPSHOT_WITH_ID("blink_gc", "MarkingStats", (unsigned long long)0, json.release());
+        mom().clear();
+    }
+
     static void reportStillAlive(LiveObjectSet current, LiveObjectSet previous)
     {
         int count = 0;
 
         fprintf(stderr, " [previously %u]", previous.size());
         for (LiveObjectSet::iterator it = current.begin(), end = current.end(); it != end; ++it) {
             if (previous.find(*it) == previous.end())
                 continue;
             count++;
         }
@@ skipping 337 matching lines @@
 #endif
 
 void Heap::prepareForGC()
 {
     ASSERT(ThreadState::isAnyThreadInGC());
     ThreadState::AttachedThreadStateSet& threads = ThreadState::attachedThreads();
     for (ThreadState::AttachedThreadStateSet::iterator it = threads.begin(), end = threads.end(); it != end; ++it)
         (*it)->prepareForGC();
 }
 
+void Heap::reportSweepingStats()
+{
+    MutexLocker locker(uomMutex());
+    RefPtr<TracedValue> json = TracedValue::create();
+    for (ObjectAgeMap::iterator it = uom().begin(), end = uom().end(); it != end; ++it) {
+        json->beginArray(it->key.ascii().data());
+        for (size_t i = 0; i < 8; ++i) {
+            json->pushInteger(it->value.data[i]);
+        }
+        json->endArray();
+    }
+    TRACE_EVENT_OBJECT_SNAPSHOT_WITH_ID("blink_gc", "SweepingStats", (unsigned long long)0, json.release());
+    uom().clear();
+}
+
 void Heap::collectGarbage(ThreadState::StackState stackState, ThreadState::CauseOfGC cause)
 {
     ThreadState* state = ThreadState::current();
     state->clearGCRequested();
 
+#if ENABLE(GC_PROFILE_FREE_LIST)
+    state->snapshotFreeListIfNecessary();
+#endif
+
     GCScope gcScope(stackState);
     // Check if we successfully parked the other threads. If not we bail out of the GC.
     if (!gcScope.allThreadsParked()) {
         ThreadState::current()->setGCRequested();
         return;
     }
 
     if (state->isMainThread())
         ScriptForbiddenScope::enter();
 
@@ skipping 37 matching lines @@
 
     postMarkingProcessing();
     globalWeakProcessing();
 
     // Now we can delete all orphaned pages because there are no dangling
     // pointers to the orphaned pages. (If we have such dangling pointers,
     // we should have crashed during marking before getting here.)
     orphanedPagePool()->decommitOrphanedPages();
 
 #if ENABLE(GC_PROFILE_MARKING)
-    static_cast<MarkingVisitor*>(s_markingVisitor)->reportStats();
+    //static_cast<MarkingVisitor*>(s_markingVisitor)->reportStats();
+    static_cast<MarkingVisitor*>(s_markingVisitor)->reportMarkingStats();
 #endif
 
     if (Platform::current()) {
         Platform::current()->histogramCustomCounts("BlinkGC.CollectGarbage", WTF::currentTimeMS() - timeStamp, 0, 10 * 1000, 50);
         Platform::current()->histogramCustomCounts("BlinkGC.TotalObjectSpace", Heap::allocatedObjectSize() / 1024, 0, 4 * 1024 * 1024, 50);
         Platform::current()->histogramCustomCounts("BlinkGC.TotalAllocatedSpace", Heap::allocatedSpace() / 1024, 0, 4 * 1024 * 1024, 50);
     }
 
     if (state->isMainThread())
         ScriptForbiddenScope::exit();
@@ skipping 329 matching lines @@
 bool Heap::s_shutdownCalled = false;
 bool Heap::s_lastGCWasConservative = false;
 FreePagePool* Heap::s_freePagePool;
 OrphanedPagePool* Heap::s_orphanedPagePool;
 Heap::RegionTree* Heap::s_regionTree = 0;
 size_t Heap::s_allocatedObjectSize = 0;
 size_t Heap::s_allocatedSpace = 0;
 size_t Heap::s_markedObjectSize = 0;
 
 } // namespace blink