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 32 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()
+{
+    AtomicallyInitializedStaticReference(Mutex, mutex, new Mutex);
+    return mutex;
+}
+
+static ObjectAgeMap& mom()
+{
+    static ObjectAgeMap momap;
+    return momap;
+}
+
+static Mutex& momMutex()
+{
+    AtomicallyInitializedStaticReference(Mutex, mutex, new Mutex);
+    return mutex;
+}
+
 #if ENABLE(GC_PROFILE_MARKING)
 static String classOf(const void* object)
 {
     if (const GCInfo* gcInfo = Heap::findGCInfo(reinterpret_cast<Address>(const_cast<void*>(object))))
         return gcInfo->m_className;
     return "unknown";
 }
 #endif
 
 static bool vTableInitialized(void* objectPointer)
@@ skipping 460 matching lines @@
 
 void LargeObject::removeFromHeap(ThreadHeap* heap)
 {
     heap->freeLargeObject(this);
 }
 
 ThreadHeap::ThreadHeap(ThreadState* state, int index)
     : m_currentAllocationPoint(nullptr)
     , 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(nullptr)
     , m_firstLargeObject(nullptr)
     , m_firstUnsweptPage(nullptr)
     , m_firstUnsweptLargeObject(nullptr)
     , m_threadState(state)
     , m_index(index)
     , m_promptlyFreedSize(0)
 {
     clearFreeLists();
 }
@@ skipping 43 matching lines @@
 void ThreadHeap::setAllocationPoint(Address point, size_t size)
 {
 #if ENABLE(ASSERT)
     if (point) {
         ASSERT(size);
         BaseHeapPage* page = pageFromObject(point);
         ASSERT(!page->isLargeObject());
         ASSERT(size <= static_cast<HeapPage*>(page)->payloadSize());
     }
 #endif
+#if ENABLE(GC_PROFILE_FREE_LIST)
+    m_allocationPointSizeSum += size;
+    ++m_setAllocationPointCount;
+#endif
     if (hasCurrentAllocationArea())
         addToFreeList(currentAllocationPoint(), remainingAllocationSize());
     updateRemainingAllocationSize();
     m_currentAllocationPoint = point;
     m_lastRemainingAllocationSize = m_remainingAllocationSize = size;
 }
 
 Address ThreadHeap::outOfLineAllocate(size_t allocationSize, size_t gcInfoIndex)
 {
+#if ENABLE(GC_PROFILE_FREE_LIST)
+    m_threadState->snapshotFreeListIfNecessary();
+#endif
     ASSERT(allocationSize > remainingAllocationSize());
     ASSERT(allocationSize >= allocationGranularity);
 
     // 1. If this allocation is big enough, allocate a large object.
     if (allocationSize >= largeObjectSizeThreshold)
         return allocateLargeObject(allocationSize, gcInfoIndex);
 
     // 2. Check if we should trigger a GC.
     updateRemainingAllocationSize();
     threadState()->scheduleGCOrForceConservativeGCIfNeeded();
@@ skipping 222 matching lines @@
         ScriptForbiddenScope::exit();
 }
 
 #if ENABLE(ASSERT)
 static bool isLargeObjectAligned(LargeObject* largeObject, Address address)
 {
     // Check that a large object is blinkPageSize aligned (modulo the osPageSize
     // for the guard page).
     return reinterpret_cast<Address>(largeObject) - WTF::kSystemPageSize == roundToBlinkPageStart(reinterpret_cast<Address>(largeObject));
 }
+#endif
 
+#if ENABLE(ASSERT) || ENABLE(GC_PROFILE_MARKING)
 BaseHeapPage* ThreadHeap::findPageFromAddress(Address address)
 {
     for (HeapPage* page = m_firstPage; page; page = page->next()) {
         if (page->contains(address))
             return page;
     }
     for (HeapPage* page = m_firstUnsweptPage; page; page = page->next()) {
         if (page->contains(address))
             return page;
     }
     for (LargeObject* largeObject = m_firstLargeObject; largeObject; largeObject = largeObject->next()) {
         ASSERT(isLargeObjectAligned(largeObject, address));
         if (largeObject->contains(address))
             return largeObject;
     }
     for (LargeObject* largeObject = m_firstUnsweptLargeObject; largeObject; largeObject = largeObject->next()) {
         ASSERT(isLargeObjectAligned(largeObject, address));
         if (largeObject->contains(address))
             return largeObject;
     }
     return nullptr;
 }
 #endif
 
+#if ENABLE(GC_PROFILE_FREE_LIST)
+void ThreadHeap::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* 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
 void ThreadHeap::snapshot(TracedValue* json, ThreadState::SnapshotInfo* info)
 {
     ASSERT(isConsistentForSweeping());
     size_t previousPageCount = info->pageCount;
 
     json->beginArray("pages");
     for (HeapPage* 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 @@
     // space.
     if (static_cast<HeapPage*>(page)->payloadSize() != size && !entry->shouldAddToFreeList())
         return;
 #endif
     int index = bucketIndexForSize(size);
     entry->link(&m_freeLists[index]);
     if (index > m_biggestFreeListIndex)
         m_biggestFreeListIndex = index;
 }
 
+#if ENABLE(GC_PROFILE_FREE_LIST)
+void FreeList::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
+
 bool ThreadHeap::expandObject(HeapObjectHeader* header, size_t newSize)
 {
     // It's possible that Vector requests a smaller expanded size because
     // Vector::shrinkCapacity can set a capacity smaller than the actual payload
     // size.
     if (header->payloadSize() >= newSize)
         return true;
     size_t allocationSize = allocationSizeFromSize(newSize);
     ASSERT(allocationSize > header->size());
     size_t expandSize = allocationSize - header->size();
@@ skipping 793 matching lines @@
     }
 }
 #endif
 
 size_t LargeObject::objectPayloadSizeForTesting()
 {
     markAsSwept();
     return payloadSize();
 }
 
+void HeapPage::countUnmarkedObjects()
+{
+    MutexLocker locker(uomMutex());
+    for (Address headerAddress = payload(); headerAddress < payloadEnd(); ) {
+        HeapObjectHeader* header = reinterpret_cast<HeapObjectHeader*>(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();
+    }
+}
+
+#if ENABLE(GC_PROFILE_MARKING)
+const GCInfo* LargeObject::findGCInfo(Address address)
+{
+    if (!containedInObjectPayload(address))
+        return nullptr;
+    HeapObjectHeader* header = heapObjectHeader();
+    return Heap::gcInfo(header->gcInfoIndex());
+}
+#endif
+
 #if ENABLE(GC_PROFILE_HEAP)
 void LargeObject::snapshot(TracedValue* json, ThreadState::SnapshotInfo* info)
 {
     HeapObjectHeader* header = heapObjectHeader();
     size_t tag = info->getClassTag(Heap::gcInfo(header->gcInfoIndex()));
     size_t age = header->age();
     if (header->isMarked()) {
         info->liveCount[tag] += 1;
         info->liveSize[tag] += header->size();
         // Count objects that are live when promoted to the final generation.
@@ skipping 139 matching lines @@
             result.storedValue->value.add(reinterpret_cast<uintptr_t>(objectPointer));
         }
         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);
     }
 
     void reportStats()
     {
         fprintf(stderr, "\n---------- AFTER MARKING -------------------\n");
-        for (LiveObjectMap::iterator it = currentlyLive().begin(), end = currentlyLive().payloadEnd(); it != end; ++it) {
+        for (LiveObjectMap::iterator it = currentlyLive().begin(), end = currentlyLive().end(); it != end; ++it) {
             fprintf(stderr, "%s %u", it->key.ascii().data(), it->value.size());
 
             if (it->key == "blink::Document")
                 reportStillAlive(it->value, previouslyLive().get(it->key));
 
             fprintf(stderr, "\n");
         }
 
         previouslyLive().swap(currentlyLive());
         currentlyLive().clear();
 
         for (uintptr_t object : objectsToFindPath()) {
             dumpPathToObjectFromObjectGraph(objectGraph(), object);
         }
     }
 
+    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 (uintptr_t object : current) {
-            if (previous.find(object) == previous.payloadEnd())
+            if (previous.find(object) == previous.end())
                 continue;
             count++;
         }
 
         if (!count)
             return;
 
         fprintf(stderr, " {survived 2GCs %d: ", count);
         for (uintptr_t object : current) {
-            if (previous.find(object) == previous.payloadEnd())
+            if (previous.find(object) == previous.end())
                 continue;
             fprintf(stderr, "%ld", object);
             if (--count)
                 fprintf(stderr, ", ");
         }
         ASSERT(!count);
         fprintf(stderr, "}");
     }
 
     static void dumpPathToObjectFromObjectGraph(const ObjectGraph& graph, uintptr_t target)
     {
         ObjectGraph::const_iterator it = graph.find(target);
-        if (it == graph.payloadEnd())
+        if (it == graph.end())
             return;
         fprintf(stderr, "Path to %lx of %s\n", target, classOf(reinterpret_cast<const void*>(target)).ascii().data());
-        while (it != graph.payloadEnd()) {
+        while (it != graph.end()) {
             fprintf(stderr, "<- %lx of %s\n", it->value.first, it->value.second.utf8().data());
             it = graph.find(it->value.first);
         }
         fprintf(stderr, "\n");
     }
 
     static void dumpPathToObjectOnNextGC(void* p)
     {
         objectsToFindPath().add(reinterpret_cast<uintptr_t>(p));
     }
@@ skipping 293 matching lines @@
 }
 #endif
 
 void Heap::preGC()
 {
     ASSERT(!ThreadState::current()->isInGC());
     for (ThreadState* state : ThreadState::attachedThreads())
         state->preGC();
 }
 
+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::postGC(ThreadState::GCType gcType)
 {
     ASSERT(ThreadState::current()->isInGC());
     for (ThreadState* state : ThreadState::attachedThreads())
         state->postGC(gcType);
 }
 
 void Heap::collectGarbage(ThreadState::StackState stackState, ThreadState::GCType gcType)
 {
     ThreadState* state = ThreadState::current();
     state->setGCState(ThreadState::StoppingOtherThreads);
 
+#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()) {
         state->scheduleGC();
         return;
     }
 
     if (state->isMainThread())
         ScriptForbiddenScope::enter();
@@ skipping 41 matching lines @@
     globalWeakProcessing(s_markingVisitor);
 
     // 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();
 
     postGC(gcType);
 
 #if ENABLE(GC_PROFILE_MARKING)
-    static_cast<MarkingVisitor<GlobalMarking>*>(s_markingVisitor)->reportStats();
+    //static_cast<MarkingVisitor<GlobalMarking>*>(s_markingVisitor)->reportStats();
+    static_cast<MarkingVisitor<GlobalMarking>*>(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 334 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 = nullptr;
 size_t Heap::s_allocatedObjectSize = 0;
 size_t Heap::s_allocatedSpace = 0;
 size_t Heap::s_markedObjectSize = 0;
 
 } // namespace blink