Use one virtual allocation for all gigacages and their runways
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 10 Oct 2017 04:28:18 +0000 (04:28 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 10 Oct 2017 04:28:18 +0000 (04:28 +0000)
https://bugs.webkit.org/show_bug.cgi?id=178050

Reviewed by Saam Barati.

* bmalloc/Gigacage.cpp:
(Gigacage::ensureGigacage):
(Gigacage::runway): Deleted.
(Gigacage::totalSize): Deleted.
* bmalloc/Gigacage.h:

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

Source/bmalloc/CMakeLists.txt
Source/bmalloc/ChangeLog
Source/bmalloc/bmalloc.xcodeproj/project.pbxproj
Source/bmalloc/bmalloc/BAssert.h
Source/bmalloc/bmalloc/CryptoRandom.cpp [new file with mode: 0644]
Source/bmalloc/bmalloc/CryptoRandom.h [new file with mode: 0644]
Source/bmalloc/bmalloc/Gigacage.cpp
Source/bmalloc/bmalloc/Gigacage.h

index 3b849fd..ee3ab99 100644 (file)
@@ -8,6 +8,7 @@ set(bmalloc_SOURCES
     bmalloc/Allocator.cpp
     bmalloc/AvailableMemory.cpp
     bmalloc/Cache.cpp
+    bmalloc/CryptoRandom.cpp
     bmalloc/Deallocator.cpp
     bmalloc/DebugHeap.cpp
     bmalloc/Environment.cpp
index 821c80a..67f2a1a 100644 (file)
@@ -1,3 +1,16 @@
+2017-10-07  Filip Pizlo  <fpizlo@apple.com>
+
+        Use one virtual allocation for all gigacages and their runways
+        https://bugs.webkit.org/show_bug.cgi?id=178050
+
+        Reviewed by Saam Barati.
+
+        * bmalloc/Gigacage.cpp:
+        (Gigacage::ensureGigacage):
+        (Gigacage::runway): Deleted.
+        (Gigacage::totalSize): Deleted.
+        * bmalloc/Gigacage.h:
+
 2017-09-29  Filip Pizlo  <fpizlo@apple.com>
 
         Enable gigacage on iOS
index ff45305..f64fd9f 100644 (file)
@@ -15,6 +15,8 @@
                0F5BF1521F22E1570029D91D /* Scavenger.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F5BF1501F22E1570029D91D /* Scavenger.cpp */; };
                0F5BF1531F22E1570029D91D /* Scavenger.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F5BF1511F22E1570029D91D /* Scavenger.h */; settings = {ATTRIBUTES = (Private, ); }; };
                0F5BF1731F23C5710029D91D /* BExport.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F5BF1721F23C5710029D91D /* BExport.h */; settings = {ATTRIBUTES = (Private, ); }; };
+               0F74B93E1F89713E00B935D3 /* CryptoRandom.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F74B93C1F89713E00B935D3 /* CryptoRandom.h */; };
+               0F74B93F1F89713E00B935D3 /* CryptoRandom.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F74B93D1F89713E00B935D3 /* CryptoRandom.cpp */; };
                0FD557331F7EDB7B00B1F0A3 /* HeapKind.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FD557321F7EDB7B00B1F0A3 /* HeapKind.cpp */; };
                1400274918F89C1300115C97 /* Heap.h in Headers */ = {isa = PBXBuildFile; fileRef = 14DA320C18875B09007269E0 /* Heap.h */; settings = {ATTRIBUTES = (Private, ); }; };
                1400274A18F89C2300115C97 /* VMHeap.h in Headers */ = {isa = PBXBuildFile; fileRef = 144F7BFC18BFC517003537F3 /* VMHeap.h */; settings = {ATTRIBUTES = (Private, ); }; };
@@ -91,6 +93,8 @@
                0F5BF1501F22E1570029D91D /* Scavenger.cpp */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.cpp.cpp; name = Scavenger.cpp; path = bmalloc/Scavenger.cpp; sourceTree = "<group>"; };
                0F5BF1511F22E1570029D91D /* Scavenger.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; name = Scavenger.h; path = bmalloc/Scavenger.h; sourceTree = "<group>"; };
                0F5BF1721F23C5710029D91D /* BExport.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; name = BExport.h; path = bmalloc/BExport.h; sourceTree = "<group>"; };
+               0F74B93C1F89713E00B935D3 /* CryptoRandom.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = CryptoRandom.h; path = bmalloc/CryptoRandom.h; sourceTree = "<group>"; };
+               0F74B93D1F89713E00B935D3 /* CryptoRandom.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = CryptoRandom.cpp; path = bmalloc/CryptoRandom.cpp; sourceTree = "<group>"; };
                0FD557321F7EDB7B00B1F0A3 /* HeapKind.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = HeapKind.cpp; path = bmalloc/HeapKind.cpp; sourceTree = "<group>"; };
                140FA00219CE429C00FFD3C8 /* BumpRange.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = BumpRange.h; path = bmalloc/BumpRange.h; sourceTree = "<group>"; };
                140FA00419CE4B6800FFD3C8 /* LineMetadata.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = LineMetadata.h; path = bmalloc/LineMetadata.h; sourceTree = "<group>"; };
                                0F5BF1721F23C5710029D91D /* BExport.h */,
                                1413E460189DCE1E00546D68 /* BInline.h */,
                                14C919C818FCC59F0028DB43 /* BPlatform.h */,
+                               0F74B93D1F89713E00B935D3 /* CryptoRandom.cpp */,
+                               0F74B93C1F89713E00B935D3 /* CryptoRandom.h */,
                                14D9DB4517F2447100EAAB79 /* FixedVector.h */,
                                0FD557321F7EDB7B00B1F0A3 /* HeapKind.cpp */,
                                0F5BF1461F22A8B10029D91D /* HeapKind.h */,
                                14C919C918FCC59F0028DB43 /* BPlatform.h in Headers */,
                                4426E2831C839547008EB042 /* BSoftLinking.h in Headers */,
                                14DD789C18F48D4A00950702 /* BumpAllocator.h in Headers */,
+                               0F74B93E1F89713E00B935D3 /* CryptoRandom.h in Headers */,
                                140FA00319CE429C00FFD3C8 /* BumpRange.h in Headers */,
                                14DD789918F48D4A00950702 /* Cache.h in Headers */,
                                147DC6E31CA5B70B00724E8D /* Chunk.h in Headers */,
                                142B44361E2839E7001DA6E9 /* DebugHeap.cpp in Sources */,
                                14895D911A3A319C0006235D /* Environment.cpp in Sources */,
                                14F271C718EA3990008C152F /* Heap.cpp in Sources */,
+                               0F74B93F1F89713E00B935D3 /* CryptoRandom.cpp in Sources */,
                                0F5BF14F1F22DEAF0029D91D /* Gigacage.cpp in Sources */,
                                144C07F41C7B70260051BB6A /* LargeMap.cpp in Sources */,
                                4426E2801C838EE0008EB042 /* Logging.cpp in Sources */,
index e162ac4..6194e18 100644 (file)
 
 #define BCRASH() do { \
     *(int*)0xbbadbeef = 0; \
-} while (0);
+} while (0)
 
 #endif // defined(NDEBUG) && BOS(DARWIN)
 
 #define BASSERT_IMPL(x) do { \
     if (!(x)) \
         BCRASH(); \
-} while (0);
+} while (0)
 
 #define RELEASE_BASSERT(x) BASSERT_IMPL(x)
 
@@ -82,7 +82,7 @@
         BLOG_ERROR("ASSERTION FAILED: " #x " :: " format, ##__VA_ARGS__); \
         BCRASH(); \
     } \
-} while (0);
+} while (0)
 #endif
 
 #define UNUSED(x) ((void)x)
diff --git a/Source/bmalloc/bmalloc/CryptoRandom.cpp b/Source/bmalloc/bmalloc/CryptoRandom.cpp
new file mode 100644 (file)
index 0000000..3403dd2
--- /dev/null
@@ -0,0 +1,80 @@
+/*
+ * Copyright (C) 2017 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 "CryptoRandom.h"
+
+#include "BAssert.h"
+#include "BPlatform.h"
+#include <mutex>
+
+#if !BOS(DARWIN)
+#include <errno.h>
+#include <fcntl.h>
+#include <unistd.h>
+#endif
+
+#if BOS(DARWIN)
+typedef struct __CCRandom* CCRandomRef;
+
+extern "C" {
+extern const CCRandomRef kCCRandomDefault;
+int CCRandomCopyBytes(CCRandomRef rnd, void *bytes, size_t count);
+}
+#endif
+
+namespace bmalloc {
+
+void cryptoRandom(unsigned char* buffer, size_t length)
+{
+#if BOS(DARWIN)
+    RELEASE_BASSERT(!CCRandomCopyBytes(kCCRandomDefault, buffer, length));
+#else
+    static std::once_flag onceFlag;
+    static int fd;
+    std::call_once(
+        onceFlag,
+        [] {
+            int ret = 0;
+            do {
+                ret = open("/dev/urandom", O_RDONLY, 0);
+            } while (ret == -1 && errno == EINTR);
+            RELEASE_BASSERT(ret >= 0);
+            fd = ret;
+        });
+    ssize_t amountRead = 0;
+    while (static_cast<size_t>(amountRead) < length) {
+        ssize_t currentRead = read(fd, buffer + amountRead, length - amountRead);
+        // We need to check for both EAGAIN and EINTR since on some systems /dev/urandom
+        // is blocking and on others it is non-blocking.
+        if (currentRead == -1)
+            RELEASE_BASSERT(errno == EAGAIN || errno == EINTR);
+        else
+            amountRead += currentRead;
+    }
+#endif
+}
+
+} // namespace bmalloc
+
diff --git a/Source/bmalloc/bmalloc/CryptoRandom.h b/Source/bmalloc/bmalloc/CryptoRandom.h
new file mode 100644 (file)
index 0000000..16cac5f
--- /dev/null
@@ -0,0 +1,36 @@
+/*
+ * Copyright (C) 2017 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. 
+ */
+
+#pragma once
+
+#include <cstddef>
+#include <inttypes.h>
+
+namespace bmalloc {
+
+void cryptoRandom(unsigned char* buffer, size_t length);
+
+}
+
index 4c4bd19..6a77282 100644 (file)
@@ -25,6 +25,7 @@
 
 #include "Gigacage.h"
 
+#include "CryptoRandom.h"
 #include "Environment.h"
 #include "PerProcess.h"
 #include "VMAllocate.h"
 #if BCPU(ARM64)
 // FIXME: There is no good reason for ARM64 to be special.
 // https://bugs.webkit.org/show_bug.cgi?id=177605
-#define PRIMITIVE_GIGACAGE_RUNWAY 0
+#define GIGACAGE_RUNWAY 0
 #else
 // FIXME: Consider making this 32GB, in case unsigned 32-bit indices find their way into indexed accesses.
 // https://bugs.webkit.org/show_bug.cgi?id=175062
-#define PRIMITIVE_GIGACAGE_RUNWAY (16llu * 1024 * 1024 * 1024)
+#define GIGACAGE_RUNWAY (16llu * 1024 * 1024 * 1024)
 #endif
 
-// FIXME: Reconsider this.
-// https://bugs.webkit.org/show_bug.cgi?id=175921
-#define JSVALUE_GIGACAGE_RUNWAY 0
-#define STRING_GIGACAGE_RUNWAY 0
-
 char g_gigacageBasePtrs[GIGACAGE_BASE_PTRS_SIZE] __attribute__((aligned(GIGACAGE_BASE_PTRS_SIZE)));
 
 using namespace bmalloc;
@@ -117,38 +113,57 @@ void ensureGigacage()
             if (!shouldBeEnabled())
                 return;
             
-            bool ok = true;
+            Kind shuffledKinds[numKinds];
+            for (unsigned i = 0; i < numKinds; ++i)
+                shuffledKinds[i] = static_cast<Kind>(i);
             
-            forEachKind(
-                [&] (Kind kind) {
-                    if (!ok)
-                        return;
-                    // FIXME: Randomize where this goes.
-                    // https://bugs.webkit.org/show_bug.cgi?id=175245
-                    basePtr(kind) = tryVMAllocate(alignment(kind), totalSize(kind));
-                    if (!basePtr(kind)) {
-                        if (GIGACAGE_ALLOCATION_CAN_FAIL) {
-                            ok = false;
-                            return;
-                        }
-                        fprintf(stderr, "FATAL: Could not allocate %s gigacage.\n", name(kind));
-                        BCRASH();
-                    }
-                    
-                    vmDeallocatePhysicalPages(basePtr(kind), totalSize(kind));
-                });
+            // We just go ahead and assume that 64 bits is enough randomness. That's trivially true right
+            // now, but would stop being true if we went crazy with gigacages. Based on my math, 21 is the
+            // largest value of n so that n! <= 2^64.
+            static_assert(numKinds <= 21, "too many kinds");
+            uint64_t random;
+            cryptoRandom(reinterpret_cast<unsigned char*>(&random), sizeof(random));
+            for (unsigned i = numKinds; i--;) {
+                unsigned limit = i + 1;
+                unsigned j = static_cast<unsigned>(random % limit);
+                random /= limit;
+                std::swap(shuffledKinds[i], shuffledKinds[j]);
+            }
+
+            auto alignTo = [] (Kind kind, size_t totalSize) -> size_t {
+                return roundUpToMultipleOf(alignment(kind), totalSize);
+            };
+            auto bump = [] (Kind kind, size_t totalSize) -> size_t {
+                return totalSize + size(kind);
+            };
             
-            if (!ok) {
-                forEachKind(
-                    [&] (Kind kind) {
-                        if (!basePtr(kind))
-                            return;
-                        
-                        vmDeallocate(basePtr(kind), totalSize(kind));
-                        
-                        basePtr(kind) = nullptr;
-                    });
-                return;
+            size_t totalSize = 0;
+            size_t maxAlignment = 0;
+            
+            for (Kind kind : shuffledKinds) {
+                totalSize = bump(kind, alignTo(kind, totalSize));
+                maxAlignment = std::max(maxAlignment, alignment(kind));
+            }
+            totalSize += GIGACAGE_RUNWAY;
+            
+            // FIXME: Randomize where this goes.
+            // https://bugs.webkit.org/show_bug.cgi?id=175245
+            void* base = tryVMAllocate(maxAlignment, totalSize);
+            if (!base) {
+                if (GIGACAGE_ALLOCATION_CAN_FAIL) {
+                    vmDeallocate(base, totalSize);
+                    return;
+                }
+                fprintf(stderr, "FATAL: Could not allocate gigacage memory with maxAlignment = %lu, totalSize = %lu.\n", maxAlignment, totalSize);
+                BCRASH();
+            }
+            vmDeallocatePhysicalPages(base, totalSize);
+            
+            size_t nextCage = 0;
+            for (Kind kind : shuffledKinds) {
+                nextCage = alignTo(kind, nextCage);
+                basePtr(kind) = reinterpret_cast<char*>(base) + nextCage;
+                nextCage = bump(kind, nextCage);
             }
             
             protectGigacageBasePtrs();
@@ -157,25 +172,6 @@ void ensureGigacage()
 #endif // GIGACAGE_ENABLED
 }
 
-size_t runway(Kind kind)
-{
-    switch (kind) {
-    case Primitive:
-        return static_cast<size_t>(PRIMITIVE_GIGACAGE_RUNWAY);
-    case JSValue:
-        return static_cast<size_t>(JSVALUE_GIGACAGE_RUNWAY);
-    case String:
-        return static_cast<size_t>(STRING_GIGACAGE_RUNWAY);
-    }
-    BCRASH();
-    return 0;
-}
-
-size_t totalSize(Kind kind)
-{
-    return size(kind) + runway(kind);
-}
-
 void disablePrimitiveGigacage()
 {
     ensureGigacage();
index 3a823db..181a7e6 100644 (file)
@@ -83,6 +83,8 @@ enum Kind {
     String
 };
 
+static constexpr unsigned numKinds = 3;
+
 BEXPORT void ensureGigacage();
 
 BEXPORT void disablePrimitiveGigacage();
@@ -164,9 +166,6 @@ BINLINE size_t mask(Kind kind)
     return GIGACAGE_SIZE_TO_MASK(size(kind));
 }
 
-size_t runway(Kind kind);
-size_t totalSize(Kind kind);
-
 template<typename Func>
 void forEachKind(const Func& func)
 {