MallocBench should have a stress test for correctness
authorggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 3 Sep 2014 20:59:58 +0000 (20:59 +0000)
committerggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 3 Sep 2014 20:59:58 +0000 (20:59 +0000)
https://bugs.webkit.org/show_bug.cgi?id=136468

Reviewed by Andreas Kling.

Added a stress test that allocates randomized sizes of randomized
lifetimes in randomized order.

This version of the test reproduces the EWS crash seen in bmalloc
(<https://bugs.webkit.org/show_bug.cgi?id=132629>).

* MallocBench/MallocBench.xcodeproj/project.pbxproj:
* MallocBench/MallocBench/Benchmark.cpp: Sort!
* MallocBench/MallocBench/stress.cpp: Added.
(Object::Object):
(SizeStream::SizeStream):
(SizeStream::next):
(benchmark_stress): Usually, we random(0). Surprisingly, though, only
random(1) reproduces the bug I was looking for.
* MallocBench/MallocBench/stress.h: Added.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@173223 268f45cc-cd09-0410-ab3c-d52691b4dbfc

PerformanceTests/ChangeLog
PerformanceTests/MallocBench/MallocBench.xcodeproj/project.pbxproj
PerformanceTests/MallocBench/MallocBench/Benchmark.cpp
PerformanceTests/MallocBench/MallocBench/stress.cpp [new file with mode: 0644]
PerformanceTests/MallocBench/MallocBench/stress.h [new file with mode: 0644]

index e761f39..30e24f7 100644 (file)
@@ -1,3 +1,26 @@
+2014-09-02  Geoffrey Garen  <ggaren@apple.com>
+
+        MallocBench should have a stress test for correctness
+        https://bugs.webkit.org/show_bug.cgi?id=136468
+
+        Reviewed by Andreas Kling.
+
+        Added a stress test that allocates randomized sizes of randomized
+        lifetimes in randomized order.
+
+        This version of the test reproduces the EWS crash seen in bmalloc
+        (<https://bugs.webkit.org/show_bug.cgi?id=132629>).
+
+        * MallocBench/MallocBench.xcodeproj/project.pbxproj:
+        * MallocBench/MallocBench/Benchmark.cpp: Sort!
+        * MallocBench/MallocBench/stress.cpp: Added.
+        (Object::Object):
+        (SizeStream::SizeStream):
+        (SizeStream::next):
+        (benchmark_stress): Usually, we random(0). Surprisingly, though, only
+        random(1) reproduces the bug I was looking for.
+        * MallocBench/MallocBench/stress.h: Added.
+
 2014-06-02  Ryosuke Niwa  <rniwa@webkit.org>
 
         Rename DoYouEvenBench 0.17 to Speedometer 1.0 and add a new look.
index 6f6633f..2867523 100644 (file)
@@ -35,6 +35,7 @@
                14CC393F18EA8184004AFE34 /* mbmalloc.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 14CC391C18EA6759004AFE34 /* mbmalloc.cpp */; };
                14CE4A6017BD355800288DAA /* big.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 14CE4A5E17BD355800288DAA /* big.cpp */; };
                14E11932177ECC8B003A8D15 /* CPUCount.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 14E11930177ECC8B003A8D15 /* CPUCount.cpp */; };
+               14FCA36119A7C917001CFDA9 /* stress.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 14FCA35F19A7C917001CFDA9 /* stress.cpp */; };
 /* End PBXBuildFile section */
 
 /* Begin PBXCopyFilesBuildPhase section */
                14E11930177ECC8B003A8D15 /* CPUCount.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CPUCount.cpp; sourceTree = "<group>"; };
                14E11931177ECC8B003A8D15 /* CPUCount.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = CPUCount.h; sourceTree = "<group>"; };
                14E11934177F5219003A8D15 /* mbmalloc.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = mbmalloc.h; path = MallocBench/mbmalloc.h; sourceTree = "<group>"; };
+               14FCA35F19A7C917001CFDA9 /* stress.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = stress.cpp; path = MallocBench/stress.cpp; sourceTree = "<group>"; };
+               14FCA36019A7C917001CFDA9 /* stress.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = stress.h; path = MallocBench/stress.h; sourceTree = "<group>"; };
 /* End PBXFileReference section */
 
 /* Begin PBXFrameworksBuildPhase section */
                                1447AE8A18FB584200B3D7FF /* reddit.cpp */,
                                1447AE8B18FB584200B3D7FF /* reddit.h */,
                                1447AE8C18FB584200B3D7FF /* reddit.ops */,
+                               14FCA35F19A7C917001CFDA9 /* stress.cpp */,
+                               14FCA36019A7C917001CFDA9 /* stress.h */,
                                1447AE9818FB59D900B3D7FF /* theverge_memory_warning.ops */,
                                1447AE8D18FB584200B3D7FF /* theverge.cpp */,
                                1447AE8E18FB584200B3D7FF /* theverge.h */,
                                1444AE96177E8DF200F8030A /* message.cpp in Sources */,
                                14452CEF177D47110097E057 /* churn.cpp in Sources */,
                                14452CB0177D24460097E057 /* main.cpp in Sources */,
+                               14FCA36119A7C917001CFDA9 /* stress.cpp in Sources */,
                                14C5008D184016CF007A531D /* facebook.cpp in Sources */,
                                1447AE9018FB584200B3D7FF /* flickr.cpp in Sources */,
                                14976EC8177E3649006B819A /* list.cpp in Sources */,
index 684fa0b..4993c30 100644 (file)
@@ -35,6 +35,7 @@
 #include "medium.h"
 #include "message.h"
 #include "reddit.h"
+#include "stress.h"
 #include "theverge.h"
 #include "tree.h"
 #include <dispatch/dispatch.h>
@@ -57,26 +58,27 @@ struct BenchmarkPair {
 };
 
 static const BenchmarkPair benchmarkPairs[] = {
+    { "balloon", benchmark_balloon },
+    { "big", benchmark_big },
     { "churn", benchmark_churn },
-    { "list_allocate", benchmark_list_allocate },
-    { "list_traverse", benchmark_list_traverse },
-    { "tree_allocate", benchmark_tree_allocate },
-    { "tree_traverse", benchmark_tree_traverse },
-    { "tree_churn", benchmark_tree_churn },
+    { "facebook", benchmark_facebook },
+    { "flickr", benchmark_flickr },
+    { "flickr_memory_warning", benchmark_flickr_memory_warning },
     { "fragment", benchmark_fragment },
     { "fragment_iterate", benchmark_fragment_iterate },
-    { "message_one", benchmark_message_one },
-    { "message_many", benchmark_message_many },
+    { "list_allocate", benchmark_list_allocate },
+    { "list_traverse", benchmark_list_traverse },
     { "medium", benchmark_medium },
-    { "big", benchmark_big },
-    { "facebook", benchmark_facebook },
-    { "balloon", benchmark_balloon },
-    { "flickr", benchmark_flickr },
+    { "message_many", benchmark_message_many },
+    { "message_one", benchmark_message_one },
     { "reddit", benchmark_reddit },
-    { "theverge", benchmark_theverge },
-    { "flickr_memory_warning", benchmark_flickr_memory_warning },
     { "reddit_memory_warning", benchmark_reddit_memory_warning },
+    { "stress", benchmark_stress },
+    { "theverge", benchmark_theverge },
     { "theverge_memory_warning", benchmark_theverge_memory_warning },
+    { "tree_allocate", benchmark_tree_allocate },
+    { "tree_churn", benchmark_tree_churn },
+    { "tree_traverse", benchmark_tree_traverse },
 };
 
 static const size_t benchmarksPairsCount = sizeof(benchmarkPairs) / sizeof(BenchmarkPair);
diff --git a/PerformanceTests/MallocBench/MallocBench/stress.cpp b/PerformanceTests/MallocBench/MallocBench/stress.cpp
new file mode 100644 (file)
index 0000000..755a4e6
--- /dev/null
@@ -0,0 +1,139 @@
+/*
+ * Copyright (C) 2014 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 "Benchmark.h"
+#include "CPUCount.h"
+#include "stress.h"
+#include <array>
+#include <chrono>
+#include <cstdlib>
+#include <memory>
+#include <stddef.h>
+#include <vector>
+
+#include "mbmalloc.h"
+
+static const size_t kB = 1024;
+static const size_t MB = kB * kB;
+
+struct Object {
+    Object(void* pointer, size_t size)
+        : pointer(pointer)
+        , size(size)
+    {
+    }
+
+    void* pointer;
+    size_t size;
+};
+
+class SizeStream {
+public:
+    SizeStream()
+        : m_state(Small)
+        , m_count(0)
+    {
+    }
+
+    size_t next()
+    {
+        switch (m_state) {
+        case Small: {
+            if (++m_count == smallCount) {
+                m_state = Medium;
+                m_count = 0;
+            }
+            return random() % smallMax;
+        }
+                
+        case Medium: {
+            if (++m_count == mediumCount) {
+                m_state = Large;
+                m_count = 0;
+            }
+            return random() % mediumMax;
+        }
+                
+        case Large: {
+            if (++m_count == largeCount) {
+                m_state = Small;
+                m_count = 0;
+            }
+            return random() % largeMax;
+        }
+        }
+    }
+
+private:
+    static const size_t smallCount = 1000;
+    static const size_t smallMax = 16 * kB;
+
+    static const size_t mediumCount = 100;
+    static const size_t mediumMax = 512 * kB;
+    
+    static const size_t largeCount = 10;
+    static const size_t largeMax = 4 * MB;
+
+    enum { Small, Medium, Large } m_state;
+    size_t m_count;
+};
+
+void benchmark_stress(bool isParallel)
+{
+    const size_t heapSize = 100 * MB;
+    const size_t churnSize = .05 * heapSize;
+    const size_t churnCount = 10000;
+    
+    srandom(1); // For consistency between runs.
+
+    std::vector<Object> objects;
+    
+    SizeStream sizeStream;
+    
+    size_t lastSize = 0;
+    for (size_t remaining = heapSize; remaining; remaining -= std::min(remaining, lastSize)) {
+        lastSize = sizeStream.next();
+        Object object(mbmalloc(lastSize), lastSize);
+        objects.push_back(object);
+    }
+    
+    for (size_t i = 0; i < churnCount; ++i) {
+        std::vector<Object> objectsToFree;
+        for (size_t remaining = churnSize; remaining; remaining -= std::min(remaining, lastSize)) {
+            lastSize = sizeStream.next();
+            Object object(mbmalloc(lastSize), lastSize);
+
+            size_t index = random() % objects.size();
+            objectsToFree.push_back(objects[index]);
+            objects[index] = object;
+        }
+
+        for (auto& object : objectsToFree)
+            mbfree(object.pointer, object.size);
+    }
+    
+    for (auto& object : objects)
+        mbfree(object.pointer, object.size);
+}
diff --git a/PerformanceTests/MallocBench/MallocBench/stress.h b/PerformanceTests/MallocBench/MallocBench/stress.h
new file mode 100644 (file)
index 0000000..06f8c42
--- /dev/null
@@ -0,0 +1,31 @@
+/*
+ * Copyright (C) 2014 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 stress_h
+#define stress_h
+
+void benchmark_stress(bool isParallel);
+
+#endif // stress_h