Attachment 342887 Details for Bug 186698 – Patch

[patch] Patch

bug-186698-20180616130308.patch (text/plain), 53.65 KB, created by Simon Fraser (smfr) on 2018-06-16 13:03:09 PDT

(hide)

Description:

Filename:

MIME Type:

Creator: Simon Fraser (smfr)

Created: 2018-06-16 13:03:09 PDT

Size: 53.65 KB

patch

obsolete

>Subversion Revision: 232909
>diff --git a/Source/WTF/ChangeLog b/Source/WTF/ChangeLog
>index f6a0ee95b35ac5ef7be96aabe4a89bd65827af4a..c9d559cbcbf9b0dfcac510c6b107e096934cbbaa 100644
>--- a/Source/WTF/ChangeLog
>+++ b/Source/WTF/ChangeLog
>@@ -1,3 +1,67 @@
>+2018-06-16  Simon Fraser  <simon.fraser@apple.com>
>+
>+        Make it possible to track call sites that waste Vector capacity
>+        https://bugs.webkit.org/show_bug.cgi?id=186698
>+
>+        Reviewed by NOBODY (OOPS!).
>+        
>+        Add ContainerCapacityTracker which can aggregate data on a per-call site basis (by taking
>+        a stackshot N frames deep, and hashing it), and is informed about allocations, size and 
>+        capacity changes, and frees of container types (e.g. Vector and HashMap).
>+        
>+        When TRACK_VECTOR_CAPACITY is defined in Vector.h, a singleton ContainerCapacityTracker
>+        is used to keep track of all Vectors and their size and capacity changes. Vector gains
>+        an m_trackedID member variable to allow tracking (Vectors can be WTFMoved and std::swapped,
>+        so we can't rely on their address to track them).
>+        
>+        Data about live Vectors can then be dumped with "notifyutil -p com.apple.WebKit.dumpVectorCapacity",
>+        via code in Vector.cpp.
>+        
>+        ContainerCapacityTracker takes care to avoid re-entrancy (allow it to use the container types)
>+        while being callable from different threads.
>+        
>+        * WTF.xcodeproj/project.pbxproj:
>+        * wtf/CMakeLists.txt:
>+        * wtf/ContainerCapacityTracker.cpp: Added.
>+        * wtf/ContainerCapacityTracker.h: Added.
>+        * wtf/SizeLimits.cpp:
>+        * wtf/StackShot.h:
>+        * wtf/Vector.cpp: Added.
>+        (WTF::dumpWastedVectorCapacity):
>+        (WTF::vectorTracker):
>+        * wtf/Vector.h:
>+        (WTF::VectorBufferBase::capacityInBytes const):
>+        (WTF::VectorBufferBase::sizeInBytes const):
>+        (WTF::VectorBufferBase::VectorBufferBase):
>+        (WTF::VectorBufferBase::~VectorBufferBase):
>+        (WTF::VectorBuffer::swap):
>+        (WTF::Vector::from):
>+        (WTF::Vector::sizeInBytes const):
>+        (WTF::Vector::capacityInBytes const):
>+        (WTF::Vector::swap):
>+        (WTF::minCapacity>::Vector):
>+        (WTF::=):
>+        (WTF::minCapacity>::fill):
>+        (WTF::minCapacity>::resize):
>+        (WTF::minCapacity>::shrink):
>+        (WTF::minCapacity>::grow):
>+        (WTF::minCapacity>::reserveCapacity):
>+        (WTF::minCapacity>::tryReserveCapacity):
>+        (WTF::minCapacity>::reserveInitialCapacity):
>+        (WTF::minCapacity>::shrinkCapacity):
>+        (WTF::minCapacity>::append):
>+        (WTF::minCapacity>::tryAppend):
>+        (WTF::minCapacity>::constructAndAppend):
>+        (WTF::minCapacity>::tryConstructAndAppend):
>+        (WTF::minCapacity>::appendSlowCase):
>+        (WTF::minCapacity>::constructAndAppendSlowCase):
>+        (WTF::minCapacity>::tryConstructAndAppendSlowCase):
>+        (WTF::minCapacity>::uncheckedAppend):
>+        (WTF::minCapacity>::insert):
>+        (WTF::minCapacity>::remove):
>+        (WTF::minCapacity>::removeAllMatching):
>+        (WTF::minCapacity>::releaseBuffer):
>+
> 2018-06-15  Basuke Suzuki  <Basuke.Suzuki@sony.com>
> 
>         [WinCairo] Move unrelated features of WorkQueueWin into IPC::Connection
>diff --git a/Source/WTF/WTF.xcodeproj/project.pbxproj b/Source/WTF/WTF.xcodeproj/project.pbxproj
>index ef1b33b7fe0782f1d87405993f6f4106b1066e20..195b07a6537b4fb1f7f4fdbefd3a6ded93bdf93c 100644
>--- a/Source/WTF/WTF.xcodeproj/project.pbxproj
>+++ b/Source/WTF/WTF.xcodeproj/project.pbxproj
>@@ -24,6 +24,7 @@
> 		0F30BA901E78708E002CA847 /* GlobalVersion.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F30BA8A1E78708E002CA847 /* GlobalVersion.cpp */; };
> 		0F30CB5A1FCDF134004B5323 /* ConcurrentPtrHashSet.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F30CB581FCDF133004B5323 /* ConcurrentPtrHashSet.cpp */; };
> 		0F43D8F11DB5ADDC00108FB6 /* AutomaticThread.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F43D8EF1DB5ADDC00108FB6 /* AutomaticThread.cpp */; };
>+		0F5B4DFA20D0DE1800D6F510 /* ContainerCapacityTracker.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F5B4DF920D0DE1700D6F510 /* ContainerCapacityTracker.cpp */; };
> 		0F5BF1761F23D49A0029D91D /* Gigacage.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F5BF1741F23D49A0029D91D /* Gigacage.cpp */; };
> 		0F60F32F1DFCBD1B00416D6C /* LockedPrintStream.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F60F32D1DFCBD1B00416D6C /* LockedPrintStream.cpp */; };
> 		0F66B28A1DC97BAB004A1D3F /* ClockType.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F66B2801DC97BAB004A1D3F /* ClockType.cpp */; };
>@@ -38,6 +39,7 @@
> 		0F8F2B92172E0103007DBDA5 /* CompilationThread.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F8F2B8F172E00F0007DBDA5 /* CompilationThread.cpp */; };
> 		0F9D3360165DBA73005AD387 /* FilePrintStream.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F9D335B165DBA73005AD387 /* FilePrintStream.cpp */; };
> 		0F9D3362165DBA73005AD387 /* PrintStream.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F9D335D165DBA73005AD387 /* PrintStream.cpp */; };
>+		0FD73CBB20D4758400FC7A29 /* Vector.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FD73CBA20D4758300FC7A29 /* Vector.cpp */; };
> 		0FDDBFA71666DFA300C55FEF /* StringPrintStream.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FDDBFA51666DFA300C55FEF /* StringPrintStream.cpp */; };
> 		0FE1646A1B6FFC9600400E7C /* Lock.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FE164681B6FFC9600400E7C /* Lock.cpp */; };
> 		0FE4479C1B7AAA03009498EB /* WordLock.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FE4479A1B7AAA03009498EB /* WordLock.cpp */; };
>@@ -200,6 +202,8 @@
> 		0F4570421BE5B58F0062A629 /* Dominators.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Dominators.h; sourceTree = "<group>"; };
> 		0F4570441BE834410062A629 /* BubbleSort.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = BubbleSort.h; sourceTree = "<group>"; };
> 		0F4D8C711FC1E7CE001D32AC /* SinglyLinkedListWithTail.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SinglyLinkedListWithTail.h; sourceTree = "<group>"; };
>+		0F5B4DF820D0DE1700D6F510 /* ContainerCapacityTracker.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ContainerCapacityTracker.h; sourceTree = "<group>"; };
>+		0F5B4DF920D0DE1700D6F510 /* ContainerCapacityTracker.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ContainerCapacityTracker.cpp; sourceTree = "<group>"; };
> 		0F5BF1651F2317830029D91D /* NaturalLoops.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = NaturalLoops.h; sourceTree = "<group>"; };
> 		0F5BF1741F23D49A0029D91D /* Gigacage.cpp */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.cpp.cpp; path = Gigacage.cpp; sourceTree = "<group>"; };
> 		0F5BF1751F23D49A0029D91D /* Gigacage.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = Gigacage.h; sourceTree = "<group>"; };
>@@ -246,6 +250,7 @@
> 		0FB467831FDE282C003FCB09 /* ConcurrentVector.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ConcurrentVector.h; sourceTree = "<group>"; };
> 		0FC4488216FE9FE100844BE9 /* ProcessID.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ProcessID.h; sourceTree = "<group>"; };
> 		0FC4EDE51696149600F65041 /* CommaPrinter.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = CommaPrinter.h; sourceTree = "<group>"; };
>+		0FD73CBA20D4758300FC7A29 /* Vector.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = Vector.cpp; sourceTree = "<group>"; };
> 		0FD81AC4154FB22E00983E72 /* FastBitVector.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = FastBitVector.h; sourceTree = "<group>"; };
> 		0FDB698D1B7C643A000C1078 /* Condition.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Condition.h; sourceTree = "<group>"; };
> 		0FDDBFA51666DFA300C55FEF /* StringPrintStream.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = StringPrintStream.cpp; sourceTree = "<group>"; };
>@@ -844,6 +849,8 @@
> 				0F30CB591FCDF133004B5323 /* ConcurrentPtrHashSet.h */,
> 				0FB467831FDE282C003FCB09 /* ConcurrentVector.h */,
> 				0FDB698D1B7C643A000C1078 /* Condition.h */,
>+				0F5B4DF920D0DE1700D6F510 /* ContainerCapacityTracker.cpp */,
>+				0F5B4DF820D0DE1700D6F510 /* ContainerCapacityTracker.h */,
> 				0F8E85DA1FD485B000691889 /* CountingLock.cpp */,
> 				0FFBCBFA1FD37E0F0072AAF0 /* CountingLock.h */,
> 				E38C41261EB4E0680042957D /* CPUTime.cpp */,
>@@ -1118,6 +1125,7 @@
> 				7AFEC6AE1EB22AC600DADE36 /* UUID.h */,
> 				A8A4736F151A825B004123FF /* ValueCheck.h */,
> 				7CD0D5A71D55322A000CC9E1 /* Variant.h */,
>+				0FD73CBA20D4758300FC7A29 /* Vector.cpp */,
> 				A8A47370151A825B004123FF /* Vector.h */,
> 				A8A47371151A825B004123FF /* VectorTraits.h */,
> 				A8A47372151A825B004123FF /* VMTags.h */,
>@@ -1461,6 +1469,7 @@
> 				A8A47463151A825B004123FF /* CollatorICU.cpp in Sources */,
> 				0F8F2B92172E0103007DBDA5 /* CompilationThread.cpp in Sources */,
> 				0F30CB5A1FCDF134004B5323 /* ConcurrentPtrHashSet.cpp in Sources */,
>+				0F5B4DFA20D0DE1800D6F510 /* ContainerCapacityTracker.cpp in Sources */,
> 				0F8E85DB1FD485B000691889 /* CountingLock.cpp in Sources */,
> 				E38C41281EB4E0680042957D /* CPUTime.cpp in Sources */,
> 				E38C41251EB4E04C0042957D /* CPUTimeCocoa.mm in Sources */,
>@@ -1564,6 +1573,7 @@
> 				1C181C931D307AB800F5FA16 /* UTextProviderUTF16.cpp in Sources */,
> 				A8A47469151A825B004123FF /* UTF8.cpp in Sources */,
> 				7AFEC6B11EB22B5900DADE36 /* UUID.cpp in Sources */,
>+				0FD73CBB20D4758400FC7A29 /* Vector.cpp in Sources */,
> 				0F66B2921DC97BAB004A1D3F /* WallTime.cpp in Sources */,
> 				1FA47C8A152502DA00568D1B /* WebCoreThread.cpp in Sources */,
> 				0FE4479C1B7AAA03009498EB /* WordLock.cpp in Sources */,
>diff --git a/Source/WTF/wtf/CMakeLists.txt b/Source/WTF/wtf/CMakeLists.txt
>index 0f9f4e1f2da16c312c0dd52d8dbe953b554d344d..3dc7affd6106b1c88961d2fd31045ff6dc6fa261 100644
>--- a/Source/WTF/wtf/CMakeLists.txt
>+++ b/Source/WTF/wtf/CMakeLists.txt
>@@ -35,6 +35,7 @@ set(WTF_PUBLIC_HEADERS
>     ConcurrentPtrHashSet.h
>     ConcurrentVector.h
>     Condition.h
>+    ContainerCapacityTracker.h
>     CountingLock.h
>     CrossThreadCopier.h
>     CrossThreadQueue.h
>@@ -331,6 +332,7 @@ set(WTF_SOURCES
>     ClockType.cpp
>     CompilationThread.cpp
>     ConcurrentPtrHashSet.cpp
>+    ContainerCapacityTracker.cpp
>     CountingLock.cpp
>     CrossThreadCopier.cpp
>     CrossThreadTaskHandler.cpp
>@@ -387,6 +389,7 @@ set(WTF_SOURCES
>     TimeWithDynamicClockType.cpp
>     TimingScope.cpp
>     UUID.cpp
>+    Vector.cpp
>     WTFAssertions.cpp
>     WallTime.cpp
>     WordLock.cpp
>diff --git a/Source/WTF/wtf/ContainerCapacityTracker.cpp b/Source/WTF/wtf/ContainerCapacityTracker.cpp
>new file mode 100644
>index 0000000000000000000000000000000000000000..f2e9b07ecc4462111e69d30e4560860fe851f65d
>--- /dev/null
>+++ b/Source/WTF/wtf/ContainerCapacityTracker.cpp
>@@ -0,0 +1,202 @@
>+/*
>+ * Copyright (C) 2018 Apple 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:
>+ * 1. Redistributions of source code must retain the above copyright
>+ *    notice, this list of conditions and the following disclaimer.
>+ * 2. Redistributions in binary form must reproduce the above copyright
>+ *    notice, this list of conditions and the following disclaimer in the
>+ *    documentation and/or other materials provided with the distribution.
>+ *
>+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
>+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
>+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
>+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
>+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
>+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
>+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
>+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
>+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
>+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
>+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
>+ */
>+
>+#include "config.h"
>+#include "ContainerCapacityTracker.h"
>+
>+#include <unordered_map>
>+#include <wtf/StackShot.h>
>+
>+namespace WTF {
>+
>+AllocationCallSiteData::AllocationCallSiteData(size_t stackDepth, size_t inUsedSize, size_t inCapacity)
>+    : usedSize(inUsedSize)
>+    , capacity(inCapacity)
>+    , m_stack(std::make_unique<StackShot>(stackDepth))
>+{
>+}
>+
>+AllocationCallSiteData::AllocationCallSiteData(const StackShot& stack)
>+    : m_stack(std::make_unique<StackShot>(stack))
>+{
>+}
>+
>+AllocationCallSiteData::AllocationCallSiteData(const AllocationCallSiteData& other)
>+    : count(other.count)
>+    , usedSize(other.usedSize)
>+    , capacity(other.capacity)
>+    , m_stack(std::make_unique<StackShot>(other.stack()))
>+{
>+}
>+
>+AllocationCallSiteData::~AllocationCallSiteData() = default;
>+
>+const StackShot& AllocationCallSiteData::stack() const
>+{
>+    return *m_stack;
>+}
>+
>+struct ContainerAllocationData {
>+    ContainerAllocationData(size_t stackShotSize, size_t inSize, size_t inCapacity)
>+        : allocationStack(stackShotSize)
>+        , size(inSize)
>+        , capacity(inCapacity)
>+    {
>+    
>+    }
>+    StackShot allocationStack;
>+    size_t size;
>+    size_t capacity;
>+};
>+
>+struct ContainerCapacityTracker::ContainerCapacityTrackerImpl {
>+    std::unordered_map<TrackedID, std::unique_ptr<ContainerAllocationData>> m_trackedIDToContainerData;
>+};
>+
>+// To prevent per-thread re-entrancy we take a pointer to an object on the stack, inside m_mutex lock scope.
>+class AvoidRecordingScope {
>+public:
>+    AvoidRecordingScope(ContainerCapacityTracker& tracker, bool* stackObject)
>+        : m_tracker(tracker)
>+    {
>+        m_tracker.m_avoidReentrancy = stackObject;
>+    }
>+
>+    ~AvoidRecordingScope()
>+    {
>+        m_tracker.m_avoidReentrancy = nullptr;
>+    }
>+private:
>+    ContainerCapacityTracker& m_tracker;
>+};
>+
>+ContainerCapacityTracker::ContainerCapacityTracker(size_t aggregationStackDepth)
>+    : m_impl(std::make_unique<ContainerCapacityTrackerImpl>())
>+    , m_aggregationStackDepth(aggregationStackDepth)
>+{
>+}
>+
>+TrackedID ContainerCapacityTracker::recordAllocation(size_t size, size_t capacity)
>+{
>+    std::lock_guard<std::recursive_mutex> lockHolder(m_mutex);
>+
>+    if (m_avoidReentrancy)
>+        return 0;
>+
>+    bool avoidReentrancy = true;
>+    AvoidRecordingScope scope(*this, &avoidReentrancy);
>+
>+    TrackedID objectID = ++m_nextID;
>+
>+    auto insertResult = m_impl->m_trackedIDToContainerData.insert({ objectID, std::make_unique<ContainerAllocationData>(m_aggregationStackDepth, size, capacity) });
>+    if (!insertResult.second) {
>+        WTFLogAlways("ContainerCapacityTracker::recordAllocation saw object %u for the second time", objectID);
>+        WTFLogAlways("Was previously allocated at:");
>+        auto& callSiteData = *insertResult.first->second;
>+        const size_t framesToSkip = 0;
>+        WTFPrintBacktrace(callSiteData.allocationStack.array() + framesToSkip, callSiteData.allocationStack.size() - framesToSkip);
>+    }
>+
>+    return objectID;
>+}
>+
>+void ContainerCapacityTracker::recordSizeAndCapacity(TrackedID objectID, size_t size, size_t capacity)
>+{
>+    ASSERT(size <= capacity);
>+
>+    if (!objectID)
>+        return;
>+
>+    std::lock_guard<std::recursive_mutex> lockHolder(m_mutex);
>+
>+    if (m_avoidReentrancy)
>+        return;
>+
>+    bool avoidReentrancy = true;
>+    AvoidRecordingScope scope(*this, &avoidReentrancy);
>+
>+    auto it = m_impl->m_trackedIDToContainerData.find(objectID);
>+    if (it != m_impl->m_trackedIDToContainerData.end()) {
>+        it->second->size = size;
>+        it->second->capacity = capacity;
>+    } else
>+        WTFLogAlways("ContainerCapacityTracker %p recordSizeAndCapacity failed to find object %u", this, objectID);
>+}
>+
>+void ContainerCapacityTracker::recordFree(TrackedID objectID)
>+{
>+    if (!objectID)
>+        return;
>+
>+    std::lock_guard<std::recursive_mutex> lockHolder(m_mutex);
>+
>+    if (m_avoidReentrancy)
>+        return;
>+
>+    bool avoidReentrancy = true;
>+    AvoidRecordingScope scope(*this, &avoidReentrancy);
>+
>+    auto removedCount = m_impl->m_trackedIDToContainerData.erase(objectID);
>+    if (!removedCount)
>+        WTFLogAlways("ContainerCapacityTracker::recordFree got id %u for which there is no entry", objectID);
>+}
>+
>+std::vector<AllocationCallSiteData> ContainerCapacityTracker::aggregateByCallSite(const WTF::Function<void(TrackedID, AllocationCallSiteData&)>& perObjectCallback)
>+{
>+    std::lock_guard<std::recursive_mutex> lockHolder(m_mutex);
>+
>+    bool avoidReentrancy = true;
>+    AvoidRecordingScope scope(*this, &avoidReentrancy);
>+
>+    typedef unsigned StackShotHash;
>+    std::unordered_map<StackShotHash, std::unique_ptr<AllocationCallSiteData>> callSiteToAllocationAggregate;
>+
>+    for (const auto& it : m_impl->m_trackedIDToContainerData) {
>+        const ContainerAllocationData& allocationData = *it.second;
>+
>+        AllocationCallSiteData* callSiteData;
>+
>+        auto findIt = callSiteToAllocationAggregate.find(allocationData.allocationStack.hash());
>+        if (findIt == callSiteToAllocationAggregate.end()) {
>+            auto insertIt = callSiteToAllocationAggregate.insert({ allocationData.allocationStack.hash(), std::make_unique<AllocationCallSiteData>(allocationData.allocationStack) });
>+            callSiteData = insertIt.first->second.get();
>+        } else
>+            callSiteData = findIt->second.get();
>+
>+        callSiteData->count += 1;
>+        callSiteData->usedSize += allocationData.size;
>+        callSiteData->capacity += allocationData.capacity;
>+
>+        perObjectCallback(it.first, *callSiteData);
>+    }
>+
>+    std::vector<AllocationCallSiteData> result;
>+    for (auto& it : callSiteToAllocationAggregate)
>+        result.push_back(AllocationCallSiteData(*it.second));
>+
>+    return result;
>+}
>+
>+} // namespace WTF
>diff --git a/Source/WTF/wtf/ContainerCapacityTracker.h b/Source/WTF/wtf/ContainerCapacityTracker.h
>new file mode 100644
>index 0000000000000000000000000000000000000000..c3f1f29703fea4c28100c6530faa828df0a930de
>--- /dev/null
>+++ b/Source/WTF/wtf/ContainerCapacityTracker.h
>@@ -0,0 +1,87 @@
>+/*
>+ * Copyright (C) 2018 Apple 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:
>+ * 1. Redistributions of source code must retain the above copyright
>+ *    notice, this list of conditions and the following disclaimer.
>+ * 2. Redistributions in binary form must reproduce the above copyright
>+ *    notice, this list of conditions and the following disclaimer in the
>+ *    documentation and/or other materials provided with the distribution.
>+ *
>+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
>+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
>+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
>+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
>+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
>+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
>+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
>+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
>+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
>+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
>+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
>+ */
>+
>+#ifndef WTF_ContainerCapacityTracker_h
>+#define WTF_ContainerCapacityTracker_h
>+
>+#include <memory>
>+#include <mutex>
>+#include <vector>
>+#include <wtf/Function.h>
>+#include <wtf/Lock.h>
>+
>+namespace WTF {
>+
>+class StackShot;
>+
>+struct AllocationCallSiteData {
>+    AllocationCallSiteData(size_t stackDepth = 0, size_t size = 0, size_t capacity = 0);
>+    AllocationCallSiteData(const StackShot&);
>+    AllocationCallSiteData(const AllocationCallSiteData&);
>+    WTF_EXPORT_PRIVATE ~AllocationCallSiteData();
>+
>+    WTF_EXPORT_PRIVATE const StackShot& stack() const;
>+
>+    size_t count { 0 };
>+    size_t usedSize { 0 };
>+    size_t capacity { 0 };
>+
>+private:
>+    std::unique_ptr<StackShot> m_stack; // Needed to hide StackShot to avoid circular includes.
>+};
>+
>+typedef unsigned TrackedID;
>+
>+class ContainerCapacityTracker {
>+    WTF_MAKE_NONCOPYABLE(ContainerCapacityTracker);
>+    friend class AvoidRecordingScope;
>+public:
>+    // Call sites are aggregated by call stack, using aggregationStackDepth frames.
>+    ContainerCapacityTracker(size_t aggregationStackDepth = 15);
>+    
>+    WTF_EXPORT_PRIVATE TrackedID recordAllocation(size_t size, size_t capacity);
>+    WTF_EXPORT_PRIVATE void recordSizeAndCapacity(TrackedID, size_t size, size_t capacity);
>+    WTF_EXPORT_PRIVATE void recordFree(TrackedID);
>+    
>+    // Return a vector of per callsite data; size and capacity are summed for all allocations with a given call site.
>+    // The passed function allows the caller to do additional processing per allocation.
>+    std::vector<AllocationCallSiteData> aggregateByCallSite(const WTF::Function<void(TrackedID, AllocationCallSiteData&)>&);
>+
>+private:
>+    // Use a pimpl to avoid circular includes between our header and the container class headers.
>+    struct ContainerCapacityTrackerImpl;
>+    std::unique_ptr<ContainerCapacityTrackerImpl> m_impl;
>+    std::recursive_mutex m_mutex;
>+    TrackedID m_nextID { 0 };
>+    const size_t m_aggregationStackDepth;
>+    bool* m_avoidReentrancy { nullptr };
>+};
>+
>+} // namespace WTF
>+
>+using WTF::ContainerCapacityTracker;
>+
>+#endif // WTF_ContainerCapacityTracker_h
>+
>diff --git a/Source/WTF/wtf/HashTable.cpp b/Source/WTF/wtf/HashTable.cpp
>index 0eb6036c863fb113fec891256e5075944114abe1..de4249e26f9b6cb9461182b39362a0a38c5235b9 100644
>--- a/Source/WTF/wtf/HashTable.cpp
>+++ b/Source/WTF/wtf/HashTable.cpp
>@@ -23,6 +23,15 @@
> #include "DataLog.h"
> #include <mutex>
> 
>+#if TRACK_HASHTABLE_CAPACITY
>+#include <wtf/ContainerCapacityTracker.h>
>+#include <wtf/NeverDestroyed.h>
>+
>+#if PLATFORM(COCOA)
>+#include <notify.h>
>+#include <wtf/StackShot.h>
>+#endif
>+
> namespace WTF {
> 
> #if DUMP_HASHTABLE_STATS
>@@ -65,4 +74,63 @@ void HashTableStats::dumpStats()
> 
> #endif
> 
>+#if PLATFORM(COCOA)
>+static void dumpWastedHashTableCapacity()
>+{
>+    auto callSiteData = hashTableTracker().aggregateByCallSite([] (TrackedID, AllocationCallSiteData&) {
>+    });
>+
>+    // Make a vector of raw pointers so we can sort them.
>+    std::vector<AllocationCallSiteData*> callSitePtrs;
>+    for (const auto& siteData : callSiteData) {
>+        if (!siteData.capacity)
>+            continue;
>+        callSitePtrs.push_back(const_cast<AllocationCallSiteData*>(&siteData));
>+    }
>+
>+    // Sort by reverse wastage.
>+    std::sort(callSitePtrs.begin(), callSitePtrs.end(), [] (const AllocationCallSiteData* a, const AllocationCallSiteData* b) {
>+        size_t aWastage = a->capacity - a->usedSize;
>+        size_t bWastage = b->capacity - b->usedSize;
>+        return aWastage > bWastage;
>+    });
>+
>+    const size_t maxCount = 100;
>+
>+    WTFLogAlways("%lu call sites created HashTables (via HashMap or HashSet). Showing %lu sites with most wastage:\n", callSiteData.size(), maxCount);
>+
>+    size_t count = 0;
>+    for (auto siteData : callSitePtrs) {
>+        if (count++ == maxCount)
>+            break;
>+
>+        WTFLogAlways("Wasted capacity: %lu bytes (used %lu of %lu bytes, utilization: %.2f%%) - %lu allocations\n",
>+            siteData->capacity - siteData->usedSize,
>+            siteData->usedSize, siteData->capacity, 100.0 * siteData->usedSize / siteData->capacity,
>+            siteData->count);
>+        const size_t framesToSkip = 7;
>+        WTFPrintBacktrace(siteData->stack().array() + framesToSkip, siteData->stack().size() - framesToSkip);
>+        WTFLogAlways("\n");
>+    }
>+}
>+#endif
>+
>+ContainerCapacityTracker& hashTableTracker()
>+{
>+#if PLATFORM(COCOA)
>+    static std::once_flag initializeOnce;
>+    std::call_once(initializeOnce, [] {
>+        int token;
>+        notify_register_dispatch("com.apple.WebKit.dumpHashTableCapacity", &token, dispatch_get_main_queue(), ^(int) {
>+            dumpWastedHashTableCapacity();
>+        });
>+    });
>+#endif
>+
>+    static NeverDestroyed<WTF::ContainerCapacityTracker> tracker;
>+    return tracker;
>+}
>+
> } // namespace WTF
>+
>+#endif // TRACK_HASHTABLE_CAPACITY
>diff --git a/Source/WTF/wtf/HashTable.h b/Source/WTF/wtf/HashTable.h
>index e6a950fd400936cc4bff3d864a247852eadb35de..703530cb2716222e4c2c56144b0e28228a4d5cad 100644
>--- a/Source/WTF/wtf/HashTable.h
>+++ b/Source/WTF/wtf/HashTable.h
>@@ -42,8 +42,20 @@
> #include <wtf/DataLog.h>
> #endif
> 
>+// Enable TRACK_HASHTABLE_CAPACITY to track call sites that waste HashTable capacity. On Cocoa platforms, the data can be dumped
>+// by running "notifyutil -p com.apple.WebKit.dumpHashTableCapacity".
>+#define TRACK_HASHTABLE_CAPACITY 0
>+
>+#if TRACK_HASHTABLE_CAPACITY
>+#include <wtf/ContainerCapacityTracker.h>
>+#endif
>+
> namespace WTF {
> 
>+#if TRACK_HASHTABLE_CAPACITY
>+WTF_EXPORT_PRIVATE ContainerCapacityTracker& hashTableTracker();
>+#endif
>+
> // Enables internal WTF consistency checks that are invoked automatically. Non-WTF callers can call checkTableConsistency() even if internal checks are disabled.
> #define CHECK_HASHTABLE_CONSISTENCY 0
> 
>@@ -362,6 +374,11 @@ namespace WTF {
> #if CHECK_HASHTABLE_USE_AFTER_DESTRUCTION
>             m_table = (ValueType*)(uintptr_t)0xbbadbeef;
> #endif
>+
>+#if TRACK_HASHTABLE_CAPACITY
>+            hashTableTracker().recordFree(m_trackedID);
>+            m_trackedID = 0;
>+#endif
>         }
> 
>         HashTable(const HashTable&);
>@@ -383,6 +400,9 @@ namespace WTF {
>         unsigned capacity() const { return m_tableSize; }
>         bool isEmpty() const { return !m_keyCount; }
> 
>+        size_t sizeInBytes() const;
>+        size_t capacityInBytes() const;
>+
>         AddResult add(const ValueType& value) { return add<IdentityTranslatorType>(Extractor::extract(value), value); }
>         AddResult add(ValueType&& value) { return add<IdentityTranslatorType>(Extractor::extract(value), WTFMove(value)); }
> 
>@@ -489,6 +509,10 @@ namespace WTF {
>         unsigned m_keyCount;
>         unsigned m_deletedCount;
> 
>+#if TRACK_HASHTABLE_CAPACITY
>+        TrackedID m_trackedID { 0 };
>+#endif
>+
> #if CHECK_HASHTABLE_ITERATORS
>     public:
>         // All access to m_iterators should be guarded with m_mutex.
>@@ -556,6 +580,9 @@ namespace WTF {
>         , m_stats(std::make_unique<Stats>())
> #endif
>     {
>+#if TRACK_HASHTABLE_CAPACITY
>+        m_trackedID = hashTableTracker().recordAllocation(0, 0);
>+#endif
>     }
> 
>     inline unsigned doubleHash(unsigned key)
>@@ -938,7 +965,11 @@ namespace WTF {
>             entry = expand(entry);
> 
>         internalCheckTableConsistency();
>-        
>+
>+#if TRACK_HASHTABLE_CAPACITY
>+        hashTableTracker().recordSizeAndCapacity(m_trackedID, sizeInBytes(), capacityInBytes());
>+#endif
>+
>         return AddResult(makeKnownGoodIterator(entry), true);
>     }
> 
>@@ -977,6 +1008,10 @@ namespace WTF {
> 
>         internalCheckTableConsistency();
> 
>+#if TRACK_HASHTABLE_CAPACITY
>+        hashTableTracker().recordSizeAndCapacity(m_trackedID, sizeInBytes(), capacityInBytes());
>+#endif
>+
>         return AddResult(makeKnownGoodIterator(entry), true);
>     }
> 
>@@ -997,6 +1032,10 @@ namespace WTF {
>         newEntry->~Value();
>         new (NotNull, newEntry) ValueType(WTFMove(entry));
> 
>+#if TRACK_HASHTABLE_CAPACITY
>+        hashTableTracker().recordSizeAndCapacity(m_trackedID, sizeInBytes(), capacityInBytes());
>+#endif
>+
>         return newEntry;
>     }
> 
>@@ -1070,6 +1109,10 @@ namespace WTF {
>         if (shouldShrink())
>             shrink();
> 
>+#if TRACK_HASHTABLE_CAPACITY
>+        hashTableTracker().recordSizeAndCapacity(m_trackedID, sizeInBytes(), capacityInBytes());
>+#endif
>+
>         internalCheckTableConsistency();
>     }
> 
>@@ -1132,7 +1175,11 @@ namespace WTF {
> 
>         if (shouldShrink())
>             shrink();
>-        
>+
>+#if TRACK_HASHTABLE_CAPACITY
>+        hashTableTracker().recordSizeAndCapacity(m_trackedID, sizeInBytes(), capacityInBytes());
>+#endif
>+
>         internalCheckTableConsistency();
>         return removedBucketCount;
>     }
>@@ -1221,6 +1268,10 @@ namespace WTF {
> 
>         fastFree(oldTable);
> 
>+#if TRACK_HASHTABLE_CAPACITY
>+        hashTableTracker().recordSizeAndCapacity(m_trackedID, sizeInBytes(), capacityInBytes());
>+#endif
>+
>         internalCheckTableConsistency();
>         return newEntry;
>     }
>@@ -1238,6 +1289,10 @@ namespace WTF {
>         m_tableSizeMask = 0;
>         m_keyCount = 0;
>         m_deletedCount = 0;
>+
>+#if TRACK_HASHTABLE_CAPACITY
>+        hashTableTracker().recordSizeAndCapacity(m_trackedID, sizeInBytes(), capacityInBytes());
>+#endif
>     }
> 
>     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
>@@ -1255,6 +1310,10 @@ namespace WTF {
>         , m_stats(std::make_unique<Stats>(*other.m_stats))
> #endif
>     {
>+#if TRACK_HASHTABLE_CAPACITY
>+        m_trackedID = hashTableTracker().recordAllocation(sizeInBytes(), capacityInBytes());
>+#endif
>+
>         unsigned otherKeyCount = other.size();
>         if (!otherKeyCount)
>             return;
>@@ -1276,6 +1335,10 @@ namespace WTF {
> 
>         for (const auto& otherValue : other)
>             addUniqueForInitialization<IdentityTranslatorType>(Extractor::extract(otherValue), otherValue);
>+
>+#if TRACK_HASHTABLE_CAPACITY
>+        hashTableTracker().recordSizeAndCapacity(m_trackedID, sizeInBytes(), capacityInBytes());
>+#endif
>     }
> 
>     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
>@@ -1290,6 +1353,14 @@ namespace WTF {
>         std::swap(m_keyCount, other.m_keyCount);
>         std::swap(m_deletedCount, other.m_deletedCount);
> 
>+#if TRACK_HASHTABLE_CAPACITY
>+        std::swap(m_trackedID, other.m_trackedID);
>+
>+        // Not sure if this is necessary. Nothing will have changed.
>+        hashTableTracker().recordSizeAndCapacity(m_trackedID, sizeInBytes(), capacityInBytes());
>+        hashTableTracker().recordSizeAndCapacity(other.m_trackedID, other.sizeInBytes(), other.capacityInBytes());
>+#endif
>+
> #if DUMP_HASHTABLE_STATS_PER_TABLE
>         m_stats.swap(other.m_stats);
> #endif
>@@ -1318,6 +1389,10 @@ namespace WTF {
>         m_keyCount = other.m_keyCount;
>         m_deletedCount = other.m_deletedCount;
> 
>+#if TRACK_HASHTABLE_CAPACITY
>+        std::swap(m_trackedID, other.m_trackedID);
>+#endif
>+
>         other.m_table = nullptr;
>         other.m_tableSize = 0;
>         other.m_tableSizeMask = 0;
>@@ -1328,6 +1403,11 @@ namespace WTF {
>         m_stats = WTFMove(other.m_stats);
>         other.m_stats = nullptr;
> #endif
>+
>+#if TRACK_HASHTABLE_CAPACITY
>+        hashTableTracker().recordSizeAndCapacity(m_trackedID, sizeInBytes(), capacityInBytes());
>+        hashTableTracker().recordSizeAndCapacity(other.m_trackedID, other.sizeInBytes(), other.capacityInBytes());
>+#endif
>     }
> 
>     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
>@@ -1338,6 +1418,18 @@ namespace WTF {
>         return *this;
>     }
> 
>+    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
>+    size_t HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::sizeInBytes() const
>+    {
>+        return size() * sizeof(ValueType);
>+    }
>+
>+    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
>+    size_t HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::capacityInBytes() const
>+    {
>+        return capacity() * sizeof(ValueType);
>+    }
>+
> #if !ASSERT_DISABLED
> 
>     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
>diff --git a/Source/WTF/wtf/SizeLimits.cpp b/Source/WTF/wtf/SizeLimits.cpp
>index b0ad14044f3b8411686d3a1aa8eafb4dab77785c..fbed65fe01022c880e7e669002abd8fe0af9d12e 100644
>--- a/Source/WTF/wtf/SizeLimits.cpp
>+++ b/Source/WTF/wtf/SizeLimits.cpp
>@@ -81,9 +81,12 @@ public:
>     typename std::aligned_storage<sizeof(T), std::alignment_of<T>::value>::type inlineBuffer[inlineCapacity];
> };
> 
>+#if !TRACK_VECTOR_CAPACITY
> static_assert(sizeof(Vector<int>) == sizeof(SameSizeAsVectorWithInlineCapacity<int>), "Vector should stay small!");
> static_assert(sizeof(Vector<int, 1>) == sizeof(SameSizeAsVectorWithInlineCapacity<int, 1>), "Vector should stay small!");
> static_assert(sizeof(Vector<int, 2>) == sizeof(SameSizeAsVectorWithInlineCapacity<int, 2>), "Vector should stay small!");
> static_assert(sizeof(Vector<int, 3>) == sizeof(SameSizeAsVectorWithInlineCapacity<int, 3>), "Vector should stay small!");
>+#endif
>+
> #endif
> }
>diff --git a/Source/WTF/wtf/StackShot.h b/Source/WTF/wtf/StackShot.h
>index 7e32a35bae3c7b56a8be85b7d18d1e5579a0b3fc..fc7cfa6a662481ced4c4adcf55c856f57d5f06fc 100644
>--- a/Source/WTF/wtf/StackShot.h
>+++ b/Source/WTF/wtf/StackShot.h
>@@ -26,6 +26,7 @@
> #pragma once
> 
> #include <wtf/Assertions.h>
>+#include <wtf/HashTraits.h>
> #include <wtf/UniqueArray.h>
> 
> namespace WTF {
>diff --git a/Source/WTF/wtf/Vector.cpp b/Source/WTF/wtf/Vector.cpp
>new file mode 100644
>index 0000000000000000000000000000000000000000..9abb6df014ff6b56fbe7a075d5b84f5129090212
>--- /dev/null
>+++ b/Source/WTF/wtf/Vector.cpp
>@@ -0,0 +1,99 @@
>+/*
>+ * Copyright (C) 2018 Apple 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:
>+ * 1. Redistributions of source code must retain the above copyright
>+ *    notice, this list of conditions and the following disclaimer.
>+ * 2. Redistributions in binary form must reproduce the above copyright
>+ *    notice, this list of conditions and the following disclaimer in the
>+ *    documentation and/or other materials provided with the distribution.
>+ *
>+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
>+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
>+ * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
>+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
>+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
>+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
>+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
>+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
>+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
>+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
>+ * THE POSSIBILITY OF SUCH DAMAGE.
>+ */
>+
>+#include "config.h"
>+#include "Vector.h"
>+
>+#if TRACK_VECTOR_CAPACITY
>+#include <wtf/ContainerCapacityTracker.h>
>+#include <wtf/NeverDestroyed.h>
>+
>+#if PLATFORM(COCOA)
>+#include <notify.h>
>+#include <wtf/StackShot.h>
>+#endif
>+
>+namespace WTF {
>+
>+#if PLATFORM(COCOA)
>+static void dumpWastedVectorCapacity()
>+{
>+    auto callSiteData = vectorTracker().aggregateByCallSite([] (TrackedID, AllocationCallSiteData&) {
>+    });
>+
>+    // Make a vector of raw pointers so we can sort them.
>+    std::vector<AllocationCallSiteData*> callSitePtrs;
>+    for (const auto& siteData : callSiteData) {
>+        if (!siteData.capacity)
>+            continue;
>+        callSitePtrs.push_back(const_cast<AllocationCallSiteData*>(&siteData));
>+    }
>+
>+    // Sort by reverse wastage.
>+    std::sort(callSitePtrs.begin(), callSitePtrs.end(), [] (const AllocationCallSiteData* a, const AllocationCallSiteData* b) {
>+        size_t aWastage = a->capacity - a->usedSize;
>+        size_t bWastage = b->capacity - b->usedSize;
>+        return aWastage > bWastage;
>+    });
>+
>+    const size_t maxCount = 100;
>+
>+    WTFLogAlways("%lu call sites created vectors. Showing %lu sites with most wastage:\n", callSiteData.size(), maxCount);
>+
>+    size_t count = 0;
>+    for (auto siteData : callSitePtrs) {
>+        if (count++ == maxCount)
>+            break;
>+
>+        WTFLogAlways("Wasted capacity: %lu bytes (used %lu of %lu bytes, utilization: %.2f%%) - %lu allocations\n",
>+            siteData->capacity - siteData->usedSize,
>+            siteData->usedSize, siteData->capacity, 100.0 * siteData->usedSize / siteData->capacity,
>+            siteData->count);
>+        const size_t framesToSkip = 7;
>+        WTFPrintBacktrace(siteData->stack().array() + framesToSkip, siteData->stack().size() - framesToSkip);
>+        WTFLogAlways("\n");
>+    }
>+}
>+#endif
>+
>+ContainerCapacityTracker& vectorTracker()
>+{
>+#if PLATFORM(COCOA)
>+    static std::once_flag initializeOnce;
>+    std::call_once(initializeOnce, [] {
>+        int token;
>+        notify_register_dispatch("com.apple.WebKit.dumpVectorCapacity", &token, dispatch_get_main_queue(), ^(int) {
>+            dumpWastedVectorCapacity();
>+        });
>+    });
>+#endif
>+
>+    static NeverDestroyed<WTF::ContainerCapacityTracker> tracker;
>+    return tracker;
>+}
>+
>+} // namespace WTF
>+
>+#endif // TRACK_VECTOR_CAPACITY
>diff --git a/Source/WTF/wtf/Vector.h b/Source/WTF/wtf/Vector.h
>index 66e3be2ae688b0fd5e348c074a5c3f54f890a384..a3d9ccb050369cd12595a2441d732bd6a7adda7a 100644
>--- a/Source/WTF/wtf/Vector.h
>+++ b/Source/WTF/wtf/Vector.h
>@@ -37,12 +37,24 @@
> #include <wtf/ValueCheck.h>
> #include <wtf/VectorTraits.h>
> 
>+// Enable TRACK_VECTOR_CAPACITY to track call sites that waste vector capacity. On Cocoa platforms, the data can be dumped
>+// by running "notifyutil -p com.apple.WebKit.dumpVectorCapacity".
>+#define TRACK_VECTOR_CAPACITY 0
>+
>+#if TRACK_VECTOR_CAPACITY
>+#include <wtf/ContainerCapacityTracker.h>
>+#endif
>+
> #if ASAN_ENABLED
> extern "C" void __sanitizer_annotate_contiguous_container(const void* begin, const void* end, const void* old_mid, const void* new_mid);
> #endif
> 
> namespace WTF {
> 
>+#if TRACK_VECTOR_CAPACITY
>+WTF_EXPORT_PRIVATE ContainerCapacityTracker& vectorTracker();
>+#endif
>+    
> template <bool needsDestruction, typename T>
> struct VectorDestructor;
> 
>@@ -339,6 +351,16 @@ public:
>     static ptrdiff_t bufferMemoryOffset() { return OBJECT_OFFSETOF(VectorBufferBase, m_buffer); }
>     size_t capacity() const { return m_capacity; }
> 
>+    size_t capacityInBytes() const
>+    {
>+        return capacity() * sizeof(T);
>+    }
>+
>+    size_t sizeInBytes() const
>+    {
>+        return m_size * sizeof(T);
>+    }
>+
>     MallocPtr<T> releaseBuffer()
>     {
>         T* buffer = m_buffer;
>@@ -353,6 +375,9 @@ protected:
>         , m_capacity(0)
>         , m_size(0)
>     {
>+#if TRACK_VECTOR_CAPACITY
>+        m_trackedID = vectorTracker().recordAllocation(0, 0);
>+#endif
>     }
> 
>     VectorBufferBase(T* buffer, size_t capacity, size_t size)
>@@ -360,16 +385,26 @@ protected:
>         , m_capacity(capacity)
>         , m_size(size)
>     {
>+#if TRACK_VECTOR_CAPACITY
>+        m_trackedID = vectorTracker().recordAllocation(sizeInBytes(), capacityInBytes());
>+#endif
>     }
> 
>     ~VectorBufferBase()
>     {
>         // FIXME: It would be nice to find a way to ASSERT that m_buffer hasn't leaked here.
>+#if TRACK_VECTOR_CAPACITY
>+        vectorTracker().recordFree(m_trackedID);
>+        m_trackedID = 0;
>+#endif
>     }
> 
>     T* m_buffer;
>     unsigned m_capacity;
>     unsigned m_size; // Only used by the Vector subclass, but placed here to avoid padding the struct.
>+#if TRACK_VECTOR_CAPACITY
>+    TrackedID m_trackedID { 0 };
>+#endif
> };
> 
> template<typename T, size_t inlineCapacity>
>@@ -402,6 +437,9 @@ public:
>     {
>         std::swap(m_buffer, other.m_buffer);
>         std::swap(m_capacity, other.m_capacity);
>+#if TRACK_VECTOR_CAPACITY
>+        std::swap(m_trackedID, other.m_trackedID);
>+#endif
>     }
>     
>     void restoreInlineBufferIfNeeded() { }
>@@ -423,10 +461,16 @@ public:
>     using Base::capacity;
>     using Base::bufferMemoryOffset;
> 
>+    using Base::capacityInBytes;
>+    using Base::sizeInBytes;
>+
>     using Base::releaseBuffer;
> 
> protected:
>     using Base::m_size;
>+#if TRACK_VECTOR_CAPACITY
>+    using Base::m_trackedID;
>+#endif
> 
> private:
>     using Base::m_buffer;
>@@ -514,6 +558,10 @@ public:
>             std::swap(m_buffer, other.m_buffer);
>             std::swap(m_capacity, other.m_capacity);
>         }
>+
>+#if TRACK_VECTOR_CAPACITY
>+        std::swap(m_trackedID, other.m_trackedID);
>+#endif
>     }
> 
>     void restoreInlineBufferIfNeeded()
>@@ -540,6 +588,8 @@ public:
>     using Base::buffer;
>     using Base::capacity;
>     using Base::bufferMemoryOffset;
>+    using Base::capacityInBytes;
>+    using Base::sizeInBytes;
> 
>     MallocPtr<T> releaseBuffer()
>     {
>@@ -550,6 +600,9 @@ public:
> 
> protected:
>     using Base::m_size;
>+#if TRACK_VECTOR_CAPACITY
>+    using Base::m_trackedID;
>+#endif
> 
> private:
>     using Base::m_buffer;
>@@ -658,6 +711,10 @@ public:
>         result.m_size = size;
> 
>         result.uncheckedInitialize<0>(std::forward<Items>(items)...);
>+
>+#if TRACK_VECTOR_CAPACITY
>+        vectorTracker().recordSizeAndCapacity(result.m_trackedID, result.sizeInBytes(), result.capacityInBytes());
>+#endif
>         return result;
>     }
> 
>@@ -685,6 +742,9 @@ public:
>     size_t capacity() const { return Base::capacity(); }
>     bool isEmpty() const { return !size(); }
> 
>+    size_t sizeInBytes() const { return Base::sizeInBytes(); }
>+    size_t capacityInBytes() const { return Base::capacityInBytes(); }
>+
>     T& at(size_t i)
>     {
>         if (UNLIKELY(i >= size()))
>@@ -808,9 +868,17 @@ public:
> 
>         Base::swap(other, m_size, other.m_size);
>         std::swap(m_size, other.m_size);
>+#if TRACK_VECTOR_CAPACITY
>+        std::swap(m_trackedID, other.m_trackedID);
>+#endif
> 
>         asanSetInitialBufferSizeTo(m_size);
>         other.asanSetInitialBufferSizeTo(other.m_size);
>+
>+#if TRACK_VECTOR_CAPACITY
>+        vectorTracker().recordSizeAndCapacity(m_trackedID, sizeInBytes(), capacityInBytes());
>+        vectorTracker().recordSizeAndCapacity(other.m_trackedID, other.sizeInBytes(), other.capacityInBytes());
>+#endif
>     }
> 
>     void reverse();
>@@ -860,6 +928,11 @@ private:
>     using Base::reallocateBuffer;
>     using Base::restoreInlineBufferIfNeeded;
>     using Base::releaseBuffer;
>+
>+#if TRACK_VECTOR_CAPACITY
>+    using Base::m_trackedID;
>+#endif
>+
> #if ASAN_ENABLED
>     using Base::endOfBuffer;
> #endif
>@@ -873,6 +946,10 @@ Vector<T, inlineCapacity, OverflowHandler, minCapacity>::Vector(const Vector& ot
> 
>     if (begin())
>         TypeOperations::uninitializedCopy(other.begin(), other.end(), begin());
>+
>+#if TRACK_VECTOR_CAPACITY
>+    vectorTracker().recordSizeAndCapacity(m_trackedID, sizeInBytes(), capacityInBytes());
>+#endif
> }
> 
> template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
>@@ -884,6 +961,10 @@ Vector<T, inlineCapacity, OverflowHandler, minCapacity>::Vector(const Vector<T,
> 
>     if (begin())
>         TypeOperations::uninitializedCopy(other.begin(), other.end(), begin());
>+
>+#if TRACK_VECTOR_CAPACITY
>+    vectorTracker().recordSizeAndCapacity(m_trackedID, sizeInBytes(), capacityInBytes());
>+#endif
> }
> 
> template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
>@@ -906,6 +987,10 @@ Vector<T, inlineCapacity, OverflowHandler, minCapacity>& Vector<T, inlineCapacit
>     TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end());
>     m_size = other.size();
> 
>+#if TRACK_VECTOR_CAPACITY
>+    vectorTracker().recordSizeAndCapacity(m_trackedID, sizeInBytes(), capacityInBytes());
>+#endif
>+
>     return *this;
> }
> 
>@@ -934,6 +1019,10 @@ Vector<T, inlineCapacity, OverflowHandler, minCapacity>& Vector<T, inlineCapacit
>     TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end());
>     m_size = other.size();
> 
>+#if TRACK_VECTOR_CAPACITY
>+    vectorTracker().recordSizeAndCapacity(m_trackedID, sizeInBytes(), capacityInBytes());
>+#endif
>+
>     return *this;
> }
> 
>@@ -1015,6 +1104,10 @@ void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::fill(const T& val,
>     std::fill(begin(), end(), val);
>     TypeOperations::uninitializedFill(end(), begin() + newSize, val);
>     m_size = newSize;
>+
>+#if TRACK_VECTOR_CAPACITY
>+    vectorTracker().recordSizeAndCapacity(m_trackedID, sizeInBytes(), capacityInBytes());
>+#endif
> }
> 
> template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
>@@ -1086,6 +1179,10 @@ inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::resize(size
>     }
>     
>     m_size = size;
>+
>+#if TRACK_VECTOR_CAPACITY
>+    vectorTracker().recordSizeAndCapacity(m_trackedID, sizeInBytes(), capacityInBytes());
>+#endif
> }
> 
> template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
>@@ -1102,6 +1199,10 @@ void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::shrink(size_t size
>     TypeOperations::destruct(begin() + size, end());
>     asanBufferSizeWillChangeTo(size);
>     m_size = size;
>+
>+#if TRACK_VECTOR_CAPACITY
>+    vectorTracker().recordSizeAndCapacity(m_trackedID, sizeInBytes(), capacityInBytes());
>+#endif
> }
> 
> template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
>@@ -1114,6 +1215,10 @@ void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::grow(size_t size)
>     if (begin())
>         TypeOperations::initializeIfNonPOD(end(), begin() + size);
>     m_size = size;
>+
>+#if TRACK_VECTOR_CAPACITY
>+    vectorTracker().recordSizeAndCapacity(m_trackedID, sizeInBytes(), capacityInBytes());
>+#endif
> }
> 
> template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
>@@ -1177,6 +1282,10 @@ void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::reserveCapacity(si
> 
>     TypeOperations::move(oldBuffer, oldEnd, begin());
>     Base::deallocateBuffer(oldBuffer);
>+
>+#if TRACK_VECTOR_CAPACITY
>+    vectorTracker().recordSizeAndCapacity(m_trackedID, sizeInBytes(), capacityInBytes());
>+#endif
> }
> 
> template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
>@@ -1199,6 +1308,10 @@ bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::tryReserveCapacity
> 
>     TypeOperations::move(oldBuffer, oldEnd, begin());
>     Base::deallocateBuffer(oldBuffer);
>+
>+#if TRACK_VECTOR_CAPACITY
>+    vectorTracker().recordSizeAndCapacity(m_trackedID, sizeInBytes(), capacityInBytes());
>+#endif
>     return true;
> }
> 
>@@ -1209,6 +1322,10 @@ inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::reserveInit
>     ASSERT(capacity() == inlineCapacity);
>     if (initialCapacity > inlineCapacity)
>         Base::allocateBuffer(initialCapacity);
>+
>+#if TRACK_VECTOR_CAPACITY
>+    vectorTracker().recordSizeAndCapacity(m_trackedID, sizeInBytes(), capacityInBytes());
>+#endif
> }
> 
> template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
>@@ -1227,6 +1344,9 @@ void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::shrinkCapacity(siz
>         if (Base::shouldReallocateBuffer(newCapacity)) {
>             Base::reallocateBuffer(newCapacity);
>             asanSetInitialBufferSizeTo(size());
>+#if TRACK_VECTOR_CAPACITY
>+            vectorTracker().recordSizeAndCapacity(m_trackedID, sizeInBytes(), capacityInBytes());
>+#endif
>             return;
>         }
> 
>@@ -1240,6 +1360,10 @@ void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::shrinkCapacity(siz
>     Base::restoreInlineBufferIfNeeded();
> 
>     asanSetInitialBufferSizeTo(size());
>+
>+#if TRACK_VECTOR_CAPACITY
>+    vectorTracker().recordSizeAndCapacity(m_trackedID, sizeInBytes(), capacityInBytes());
>+#endif
> }
> 
> template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
>@@ -1257,6 +1381,10 @@ ALWAYS_INLINE void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::appe
>     T* dest = end();
>     VectorCopier<std::is_trivial<T>::value, U>::uninitializedCopy(data, std::addressof(data[dataSize]), dest);
>     m_size = newSize;
>+
>+#if TRACK_VECTOR_CAPACITY
>+    vectorTracker().recordSizeAndCapacity(m_trackedID, sizeInBytes(), capacityInBytes());
>+#endif
> }
> 
> template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
>@@ -1276,6 +1404,10 @@ ALWAYS_INLINE bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::tryA
>     T* dest = end();
>     VectorCopier<std::is_trivial<T>::value, U>::uninitializedCopy(data, std::addressof(data[dataSize]), dest);
>     m_size = newSize;
>+
>+#if TRACK_VECTOR_CAPACITY
>+    vectorTracker().recordSizeAndCapacity(m_trackedID, sizeInBytes(), capacityInBytes());
>+#endif
>     return true;
> }
> 
>@@ -1287,6 +1419,9 @@ ALWAYS_INLINE void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::appe
>         asanBufferSizeWillChangeTo(m_size + 1);
>         new (NotNull, end()) T(std::forward<U>(value));
>         ++m_size;
>+#if TRACK_VECTOR_CAPACITY
>+        vectorTracker().recordSizeAndCapacity(m_trackedID, sizeInBytes(), capacityInBytes());
>+#endif
>         return;
>     }
> 
>@@ -1301,6 +1436,9 @@ ALWAYS_INLINE void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::cons
>         asanBufferSizeWillChangeTo(m_size + 1);
>         new (NotNull, end()) T(std::forward<Args>(args)...);
>         ++m_size;
>+#if TRACK_VECTOR_CAPACITY
>+        vectorTracker().recordSizeAndCapacity(m_trackedID, sizeInBytes(), capacityInBytes());
>+#endif
>         return;
>     }
> 
>@@ -1315,6 +1453,9 @@ ALWAYS_INLINE bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::tryC
>         asanBufferSizeWillChangeTo(m_size + 1);
>         new (NotNull, end()) T(std::forward<Args>(args)...);
>         ++m_size;
>+#if TRACK_VECTOR_CAPACITY
>+        vectorTracker().recordSizeAndCapacity(m_trackedID, sizeInBytes(), capacityInBytes());
>+#endif
>         return true;
>     }
>     
>@@ -1334,6 +1475,10 @@ void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::appendSlowCase(U&&
>     asanBufferSizeWillChangeTo(m_size + 1);
>     new (NotNull, end()) T(std::forward<U>(*ptr));
>     ++m_size;
>+
>+#if TRACK_VECTOR_CAPACITY
>+    vectorTracker().recordSizeAndCapacity(m_trackedID, sizeInBytes(), capacityInBytes());
>+#endif
> }
> 
> template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
>@@ -1348,6 +1493,10 @@ void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::constructAndAppend
>     asanBufferSizeWillChangeTo(m_size + 1);
>     new (NotNull, end()) T(std::forward<Args>(args)...);
>     ++m_size;
>+
>+#if TRACK_VECTOR_CAPACITY
>+    vectorTracker().recordSizeAndCapacity(m_trackedID, sizeInBytes(), capacityInBytes());
>+#endif
> }
> 
> template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
>@@ -1363,6 +1512,10 @@ bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::tryConstructAndApp
>     asanBufferSizeWillChangeTo(m_size + 1);
>     new (NotNull, end()) T(std::forward<Args>(args)...);
>     ++m_size;
>+
>+#if TRACK_VECTOR_CAPACITY
>+    vectorTracker().recordSizeAndCapacity(m_trackedID, sizeInBytes(), capacityInBytes());
>+#endif
>     return true;
> }
> 
>@@ -1379,6 +1532,10 @@ ALWAYS_INLINE void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::unch
> 
>     new (NotNull, end()) T(std::forward<U>(value));
>     ++m_size;
>+
>+#if TRACK_VECTOR_CAPACITY
>+    vectorTracker().recordSizeAndCapacity(m_trackedID, sizeInBytes(), capacityInBytes());
>+#endif
> }
> 
> template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
>@@ -1405,6 +1562,10 @@ void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::insert(size_t posi
>     TypeOperations::moveOverlapping(spot, end(), spot + dataSize);
>     VectorCopier<std::is_trivial<T>::value, U>::uninitializedCopy(data, std::addressof(data[dataSize]), spot);
>     m_size = newSize;
>+
>+#if TRACK_VECTOR_CAPACITY
>+    vectorTracker().recordSizeAndCapacity(m_trackedID, sizeInBytes(), capacityInBytes());
>+#endif
> }
>  
> template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
>@@ -1425,6 +1586,10 @@ inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::insert(size
>     TypeOperations::moveOverlapping(spot, end(), spot + 1);
>     new (NotNull, spot) T(std::forward<U>(*ptr));
>     ++m_size;
>+
>+#if TRACK_VECTOR_CAPACITY
>+    vectorTracker().recordSizeAndCapacity(m_trackedID, sizeInBytes(), capacityInBytes());
>+#endif
> }
> 
> template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
>@@ -1443,6 +1608,10 @@ inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::remove(size
>     TypeOperations::moveOverlapping(spot + 1, end(), spot);
>     asanBufferSizeWillChangeTo(m_size - 1);
>     --m_size;
>+
>+#if TRACK_VECTOR_CAPACITY
>+    vectorTracker().recordSizeAndCapacity(m_trackedID, sizeInBytes(), capacityInBytes());
>+#endif
> }
> 
> template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
>@@ -1456,6 +1625,10 @@ inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::remove(size
>     TypeOperations::moveOverlapping(endSpot, end(), beginSpot);
>     asanBufferSizeWillChangeTo(m_size - length);
>     m_size -= length;
>+
>+#if TRACK_VECTOR_CAPACITY
>+    vectorTracker().recordSizeAndCapacity(m_trackedID, sizeInBytes(), capacityInBytes());
>+#endif
> }
> 
> template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
>@@ -1513,6 +1686,10 @@ inline unsigned Vector<T, inlineCapacity, OverflowHandler, minCapacity>::removeA
>         TypeOperations::moveOverlapping(holeEnd, end(), holeBegin);
>     asanBufferSizeWillChangeTo(m_size - matchCount);
>     m_size -= matchCount;
>+
>+#if TRACK_VECTOR_CAPACITY
>+    vectorTracker().recordSizeAndCapacity(m_trackedID, sizeInBytes(), capacityInBytes());
>+#endif
>     return matchCount;
> }
> 
>@@ -1553,6 +1730,10 @@ inline MallocPtr<T> Vector<T, inlineCapacity, OverflowHandler, minCapacity>::rel
>     }
>     m_size = 0;
>     // FIXME: Should we call Base::restoreInlineBufferIfNeeded() here?
>+
>+#if TRACK_VECTOR_CAPACITY
>+    vectorTracker().recordSizeAndCapacity(m_trackedID, sizeInBytes(), capacityInBytes());
>+#endif
>     return buffer;
> }
>

Actions: View | Formatted Diff | Diff

Attachments on bug 186698: 342860 | 342861 | 342862 | 342886 | 342887 | 342889 | 342893 | 352346 | 389418 | 425098 | 464809 | 464831