Unreviewed, rolling in r197722.
authorggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 8 Mar 2016 21:21:38 +0000 (21:21 +0000)
committerggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 8 Mar 2016 21:21:38 +0000 (21:21 +0000)
https://bugs.webkit.org/show_bug.cgi?id=155171

The right calculation for our static_assert is actually:

    sizeof(SmallChunk) % vmPageSize + 2 * smallMax <= vmPageSize

instead of:

    sizeof(SmallChunk) % vmPageSize + smallMax <= vmPageSize

smallMax is not enough because line metadata might require us to begin
allocation at an offset as large as smallMax, so we need 2 * smallMax.

Once correct, this static_assert fires, and we fix it by increasing
the alignment of SmallChunk.

Restored changeset:

"bmalloc: Use List<T> instead of Vector<T> in some places"
https://bugs.webkit.org/show_bug.cgi?id=155150
http://trac.webkit.org/changeset/197722

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

Source/bmalloc/ChangeLog
Source/bmalloc/bmalloc.xcodeproj/project.pbxproj
Source/bmalloc/bmalloc/Heap.cpp
Source/bmalloc/bmalloc/Heap.h
Source/bmalloc/bmalloc/List.h [new file with mode: 0644]
Source/bmalloc/bmalloc/SmallChunk.h
Source/bmalloc/bmalloc/SmallPage.h
Source/bmalloc/bmalloc/VMHeap.h

index 0348d41..fec5001 100644 (file)
@@ -1,3 +1,28 @@
+2016-03-08  Geoffrey Garen  <ggaren@apple.com>
+
+        Unreviewed, rolling in r197722.
+        https://bugs.webkit.org/show_bug.cgi?id=155171
+
+        The right calculation for our static_assert is actually:
+
+            sizeof(SmallChunk) % vmPageSize + 2 * smallMax <= vmPageSize
+
+        instead of:
+
+            sizeof(SmallChunk) % vmPageSize + smallMax <= vmPageSize
+
+        smallMax is not enough because line metadata might require us to begin
+        allocation at an offset as large as smallMax, so we need 2 * smallMax.
+
+        Once correct, this static_assert fires, and we fix it by increasing
+        the alignment of SmallChunk.
+
+        Restored changeset:
+
+        "bmalloc: Use List<T> instead of Vector<T> in some places"
+        https://bugs.webkit.org/show_bug.cgi?id=155150
+        http://trac.webkit.org/changeset/197722
+
 2016-03-08  Commit Queue  <commit-queue@webkit.org>
 
         Unreviewed, rolling out r197722.
index 81670f1..f1ff74c 100644 (file)
@@ -12,6 +12,7 @@
                1400274C18F89C3D00115C97 /* SegregatedFreeList.h in Headers */ = {isa = PBXBuildFile; fileRef = 146BEE1E18C841C50002D5A2 /* SegregatedFreeList.h */; settings = {ATTRIBUTES = (Private, ); }; };
                140FA00319CE429C00FFD3C8 /* BumpRange.h in Headers */ = {isa = PBXBuildFile; fileRef = 140FA00219CE429C00FFD3C8 /* BumpRange.h */; settings = {ATTRIBUTES = (Private, ); }; };
                140FA00519CE4B6800FFD3C8 /* LineMetadata.h in Headers */ = {isa = PBXBuildFile; fileRef = 140FA00419CE4B6800FFD3C8 /* LineMetadata.h */; settings = {ATTRIBUTES = (Private, ); }; };
+               141D9B001C8E51C0000ABBA0 /* List.h in Headers */ = {isa = PBXBuildFile; fileRef = 141D9AFF1C8E51C0000ABBA0 /* List.h */; settings = {ATTRIBUTES = (Private, ); }; };
                143CB81C19022BC900B16A45 /* StaticMutex.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 143CB81A19022BC900B16A45 /* StaticMutex.cpp */; };
                143CB81D19022BC900B16A45 /* StaticMutex.h in Headers */ = {isa = PBXBuildFile; fileRef = 143CB81B19022BC900B16A45 /* StaticMutex.h */; settings = {ATTRIBUTES = (Private, ); }; };
                143EF9AF1A9FABF6004F5C77 /* FreeList.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 143EF9AD1A9FABF6004F5C77 /* FreeList.cpp */; };
@@ -86,6 +87,7 @@
                1417F64618B54A700076FA3F /* EndTag.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = EndTag.h; path = bmalloc/EndTag.h; sourceTree = "<group>"; };
                1417F64F18B7280C0076FA3F /* Syscall.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = Syscall.h; path = bmalloc/Syscall.h; sourceTree = "<group>"; };
                1417F65218BA88A00076FA3F /* AsyncTask.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = AsyncTask.h; path = bmalloc/AsyncTask.h; sourceTree = "<group>"; };
+               141D9AFF1C8E51C0000ABBA0 /* List.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = List.h; path = bmalloc/List.h; sourceTree = "<group>"; };
                1421A87718EE462A00B4DD68 /* Algorithm.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; name = Algorithm.h; path = bmalloc/Algorithm.h; sourceTree = "<group>"; };
                143CB81A19022BC900B16A45 /* StaticMutex.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = StaticMutex.cpp; path = bmalloc/StaticMutex.cpp; sourceTree = "<group>"; };
                143CB81B19022BC900B16A45 /* StaticMutex.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = StaticMutex.h; path = bmalloc/StaticMutex.h; sourceTree = "<group>"; };
                                14C919C818FCC59F0028DB43 /* BPlatform.h */,
                                14D9DB4517F2447100EAAB79 /* FixedVector.h */,
                                1413E460189DCE1E00546D68 /* Inline.h */,
+                               141D9AFF1C8E51C0000ABBA0 /* List.h */,
                                144DCED617A649D90093B2F2 /* Mutex.h */,
                                14446A0717A61FA400F9EA1D /* PerProcess.h */,
                                144469FD17A61F1F00F9EA1D /* PerThread.h */,
                                14DD789818F48D4A00950702 /* Allocator.h in Headers */,
                                14DD78CB18F48D7500950702 /* PerProcess.h in Headers */,
                                14DD789318F48D0F00950702 /* ObjectType.h in Headers */,
+                               141D9B001C8E51C0000ABBA0 /* List.h in Headers */,
                        );
                        runOnlyForDeploymentPostprocessing = 0;
                };
index 3003ffa..c6cc510 100644 (file)
@@ -93,7 +93,7 @@ void Heap::scavenge(std::unique_lock<StaticMutex>& lock, std::chrono::millisecon
 
 void Heap::scavengeSmallPages(std::unique_lock<StaticMutex>& lock, std::chrono::milliseconds sleepDuration)
 {
-    while (m_smallPages.size()) {
+    while (!m_smallPages.isEmpty()) {
         m_vmHeap.deallocateSmallPage(lock, m_smallPages.pop());
         waitUntilFalse(lock, sleepDuration, m_isAllocatingPages);
     }
@@ -177,16 +177,11 @@ void Heap::allocateSmallBumpRanges(std::lock_guard<StaticMutex>& lock, size_t si
 
 SmallPage* Heap::allocateSmallPage(std::lock_guard<StaticMutex>& lock, size_t sizeClass)
 {
-    Vector<SmallPage*>& smallPagesWithFreeLines = m_smallPagesWithFreeLines[sizeClass];
-    while (smallPagesWithFreeLines.size()) {
-        SmallPage* page = smallPagesWithFreeLines.pop();
-        if (!page->refCount(lock) || page->sizeClass() != sizeClass) // Page was promoted to the pages list.
-            continue;
-        return page;
-    }
+    if (!m_smallPagesWithFreeLines[sizeClass].isEmpty())
+        return m_smallPagesWithFreeLines[sizeClass].pop();
 
     SmallPage* page = [this, &lock]() {
-        if (m_smallPages.size())
+        if (!m_smallPages.isEmpty())
             return m_smallPages.pop();
 
         m_isAllocatingPages = true;
@@ -215,6 +210,7 @@ void Heap::deallocateSmallLine(std::lock_guard<StaticMutex>& lock, SmallLine* li
     if (page->refCount(lock))
         return;
 
+    m_smallPagesWithFreeLines[page->sizeClass()].remove(page);
     m_smallPages.push(page);
     m_scavenger.run();
 }
index 1007784..1e680af 100644 (file)
@@ -29,6 +29,7 @@
 #include "BumpRange.h"
 #include "Environment.h"
 #include "LineMetadata.h"
+#include "List.h"
 #include "Mutex.h"
 #include "SegregatedFreeList.h"
 #include "SmallChunk.h"
@@ -93,9 +94,9 @@ private:
 
     std::array<std::array<LineMetadata, smallLineCount>, smallMax / alignment> m_smallLineMetadata;
 
-    std::array<Vector<SmallPage*>, smallMax / alignment> m_smallPagesWithFreeLines;
+    std::array<List<SmallPage>, smallMax / alignment> m_smallPagesWithFreeLines;
 
-    Vector<SmallPage*> m_smallPages;
+    List<SmallPage> m_smallPages;
 
     SegregatedFreeList m_largeObjects;
     
diff --git a/Source/bmalloc/bmalloc/List.h b/Source/bmalloc/bmalloc/List.h
new file mode 100644 (file)
index 0000000..eb04d2f
--- /dev/null
@@ -0,0 +1,92 @@
+/*
+ * Copyright (C) 2016 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 List_h
+#define List_h
+
+namespace bmalloc {
+
+template<typename T>
+struct ListNode {
+    ListNode()
+        : prev(this)
+        , next(this)
+    {
+    }
+
+    ListNode<T>* prev;
+    ListNode<T>* next;
+};
+
+template<typename T>
+class List {
+    static_assert(std::is_trivially_destructible<T>::value, "List must have a trivial destructor.");
+public:
+    bool isEmpty() { return m_root.next == &m_root; }
+
+    T* head() { return static_cast<T*>(m_root.next); }
+    T* tail() { return static_cast<T*>(m_root.prev); }
+
+    void push(T* node)
+    {
+        ListNode<T>* it = tail();
+        insertAfter(it, node);
+    }
+
+    T* pop()
+    {
+        ListNode<T>* result = tail();
+        remove(result);
+        return static_cast<T*>(result);
+    }
+
+    void insertAfter(ListNode<T>* it, ListNode<T>* node)
+    {
+        ListNode<T>* prev = it;
+        ListNode<T>* next = it->next;
+
+        node->next = next;
+        next->prev = node;
+
+        node->prev = prev;
+        prev->next = node;
+    }
+
+    void remove(ListNode<T>* node)
+    {
+        ListNode<T>* next = node->next;
+        ListNode<T>* prev = node->prev;
+
+        next->prev = prev;
+        prev->next = next;
+    }
+
+private:
+    ListNode<T> m_root;
+};
+
+} // namespace bmalloc
+
+#endif // List_h
index 4b144dc..d38a914 100644 (file)
@@ -48,14 +48,14 @@ public:
 private:
     std::array<SmallLine, smallChunkSize / smallLineSize> m_lines;
     std::array<SmallPage, smallChunkSize / vmPageSize> m_pages;
-    char m_memory[] __attribute__((aligned(smallLineSize+0)));
+    char m_memory[] __attribute__((aligned(2 * smallMax + 0)));
 };
 
 static_assert(!(vmPageSize % smallLineSize), "vmPageSize must be an even multiple of line size");
 static_assert(!(smallChunkSize % smallLineSize), "chunk size must be an even multiple of line size");
 static_assert(
-    sizeof(SmallChunk) - vmPageSize % sizeof(SmallChunk) < vmPageSize - 2 * smallMax,
-        "the first page of object memory in a small chunk can't allocate smallMax");
+    sizeof(SmallChunk) % vmPageSize + 2 * smallMax <= vmPageSize,
+    "the first page of object memory in a small chunk must be able to allocate smallMax");
 
 inline SmallChunk::SmallChunk(std::lock_guard<StaticMutex>& lock)
 {
index f33fb06..21aa461 100644 (file)
 #define SmallPage_h
 
 #include "BAssert.h"
+#include "List.h"
 #include "Mutex.h"
 #include "VMAllocate.h"
 #include <mutex>
 
 namespace bmalloc {
 
-class SmallPage {
+class SmallPage : public ListNode<SmallPage> {
 public:
     static const unsigned char maxRefCount = std::numeric_limits<unsigned char>::max();
     static_assert(smallLineCount < maxRefCount, "maximum line count must fit in SmallPage");
     
     static SmallPage* get(SmallLine*);
 
+    SmallPage()
+        : m_hasFreeLines(true)
+    {
+    }
+
     void ref(std::lock_guard<StaticMutex>&);
     bool deref(std::lock_guard<StaticMutex>&);
     unsigned refCount(std::lock_guard<StaticMutex>&) { return m_refCount; }
index 649e493..d73f0af 100644 (file)
@@ -62,7 +62,7 @@ private:
     LargeObject allocateLargeChunk(std::lock_guard<StaticMutex>&);
     void allocateSuperChunk(std::lock_guard<StaticMutex>&);
 
-    Vector<SmallPage*> m_smallPages;
+    List<SmallPage> m_smallPages;
     SegregatedFreeList m_largeObjects;
 
     Vector<SuperChunk*> m_smallChunks;
@@ -75,7 +75,7 @@ private:
 
 inline SmallPage* VMHeap::allocateSmallPage(std::lock_guard<StaticMutex>& lock)
 {
-    if (!m_smallPages.size())
+    if (m_smallPages.isEmpty())
         allocateSmallChunk(lock);
 
     SmallPage* page = m_smallPages.pop();