[bmalloc] IsoHeap should have lower tier using shared IsoPage
authorysuzuki@apple.com <ysuzuki@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 20 Apr 2019 03:29:40 +0000 (03:29 +0000)
committerysuzuki@apple.com <ysuzuki@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 20 Apr 2019 03:29:40 +0000 (03:29 +0000)
https://bugs.webkit.org/show_bug.cgi?id=196837

Reviewed by Filip Pizlo.

IsoHeap had a scalability problem. Once one instance is allocated from IsoHeap, it immediately allocates 16KB page for this type.
But some types allocate only a few instances. It leads to memory wastage, and it also limits the scalability of IsoHeap since
we need to carefully select classes which will be confined in IsoHeap due to this characteristics. If we can remove this wastage,
we can apply IsoHeap more aggressively without causing memory regression, this is the goal of this patch.

In this patch, we introduce a slow tier to IsoHeap allocation. Initially, the allocator for a certain type allocates instances from
a shared page with the other allocators, and eventually, the allocator tiers up and gets dedicated pages if instances of the type
are allocated a lot. This "shared" tier is slow, but it is totally OK because we will tier up to the normal fast tier if allocation
frequently happens. Even the instance is allocated from pages shared with the other allocators, we still make the allocated memory
region dedicated to the specific type: once a memory region is allocated for a certain type from a shared page, this region continues
being used only for this type even after this memory is freed. To summarize the changes:

1. We introduce "shared" tier to IsoHeap allocation. Up to N (N = 8 for now, but we can pick any power-of-two numbers up to 32) allocations,
   we continue using this tier. We allocate memory from shared pages so that we do not waste 16KB pages for types which only allocates a few instances.

2. We eventually tier up to the "fast" tier, and eventually tier down to the "shared" tier too. We measure the period between slow paths,
   and switch the appropriate tier for the type. Currently, we use 1 seconds as heuristics. We also count # of allocations per cycle to
   avoid pathological slow downs.

3. Shared page mechanism must keep the characteristics of IsoHeap. Once a memory region is allocated for a certain type, this memory region
   must be dedicated to this type. We keep track the allocated memory regions from shared pages in IsoHeapImpl, and ensure that we never
   reuse a memory region for a different type.

This patch improves PLUM2 by 1.4% (128.4MB v.s. 126.62MB), and early Speedometer2 results are performance-neutral.

* CMakeLists.txt:
* bmalloc.xcodeproj/project.pbxproj:
* bmalloc/Algorithm.h:
(bmalloc::roundUpToMultipleOfImpl):
(bmalloc::roundUpToMultipleOf):
* bmalloc/BCompiler.h:
* bmalloc/BExport.h:
* bmalloc/FreeList.h:
* bmalloc/IsoAllocator.h:
* bmalloc/IsoAllocatorInlines.h:
(bmalloc::IsoAllocator<Config>::allocateSlow):
* bmalloc/IsoDeallocator.h:
* bmalloc/IsoDeallocatorInlines.h:
(bmalloc::IsoDeallocator<Config>::deallocate):
* bmalloc/IsoHeapImpl.h:
* bmalloc/IsoHeapImplInlines.h:
(bmalloc::IsoHeapImpl<Config>::scavenge):
(bmalloc::IsoHeapImpl<Config>::forEachLiveObject):
(bmalloc::IsoHeapImpl<Config>::updateAllocationMode):
(bmalloc::IsoHeapImpl<Config>::allocateFromShared):
* bmalloc/IsoPage.h:
(bmalloc::IsoPageBase::IsoPageBase):
(bmalloc::IsoPageBase::isShared const):
* bmalloc/IsoPageInlines.h:
(bmalloc::IsoPage<Config>::IsoPage):
(bmalloc::IsoPageBase::pageFor):
(bmalloc::IsoPage<Config>::pageFor):
(bmalloc::IsoPage<Config>::free):
* bmalloc/IsoSharedConfig.h: Copied from Source/bmalloc/bmalloc/BExport.h.
* bmalloc/IsoSharedHeap.cpp: Copied from Source/bmalloc/bmalloc/BExport.h.
* bmalloc/IsoSharedHeap.h: Copied from Source/bmalloc/bmalloc/IsoAllocator.h.
(bmalloc::VariadicBumpAllocator::VariadicBumpAllocator):
(bmalloc::IsoSharedHeap::IsoSharedHeap):
* bmalloc/IsoSharedHeapInlines.h: Added.
(bmalloc::VariadicBumpAllocator::allocate):
(bmalloc::IsoSharedHeap::allocateNew):
(bmalloc::IsoSharedHeap::allocateSlow):
* bmalloc/IsoSharedPage.cpp: Copied from Source/bmalloc/bmalloc/BExport.h.
(bmalloc::IsoSharedPage::tryCreate):
* bmalloc/IsoSharedPage.h: Copied from Source/bmalloc/bmalloc/IsoDeallocator.h.
(bmalloc::IsoSharedPage::IsoSharedPage):
(bmalloc::indexSlotFor):
* bmalloc/IsoSharedPageInlines.h: Added.
(bmalloc::IsoSharedPage::free):
(bmalloc::IsoSharedPage::startAllocating):
(bmalloc::IsoSharedPage::stopAllocating):
* bmalloc/IsoTLS.h:
* bmalloc/IsoTLSInlines.h:
(bmalloc::IsoTLS::deallocateImpl):
(bmalloc::IsoTLS::deallocateFast):
(bmalloc::IsoTLS::deallocateSlow):
* bmalloc/StdLibExtras.h:
(bmalloc::bitwise_cast):
* test/testbmalloc.cpp:
(testIsoMallocAndFreeFast):
(run):

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

26 files changed:
Source/bmalloc/CMakeLists.txt
Source/bmalloc/ChangeLog
Source/bmalloc/bmalloc.xcodeproj/project.pbxproj
Source/bmalloc/bmalloc/Algorithm.h
Source/bmalloc/bmalloc/BCompiler.h
Source/bmalloc/bmalloc/BExport.h
Source/bmalloc/bmalloc/FreeList.h
Source/bmalloc/bmalloc/IsoAllocator.h
Source/bmalloc/bmalloc/IsoAllocatorInlines.h
Source/bmalloc/bmalloc/IsoDeallocator.h
Source/bmalloc/bmalloc/IsoDeallocatorInlines.h
Source/bmalloc/bmalloc/IsoHeapImpl.h
Source/bmalloc/bmalloc/IsoHeapImplInlines.h
Source/bmalloc/bmalloc/IsoPage.h
Source/bmalloc/bmalloc/IsoPageInlines.h
Source/bmalloc/bmalloc/IsoSharedConfig.h [new file with mode: 0644]
Source/bmalloc/bmalloc/IsoSharedHeap.cpp [new file with mode: 0644]
Source/bmalloc/bmalloc/IsoSharedHeap.h [new file with mode: 0644]
Source/bmalloc/bmalloc/IsoSharedHeapInlines.h [new file with mode: 0644]
Source/bmalloc/bmalloc/IsoSharedPage.cpp [new file with mode: 0644]
Source/bmalloc/bmalloc/IsoSharedPage.h [new file with mode: 0644]
Source/bmalloc/bmalloc/IsoSharedPageInlines.h [new file with mode: 0644]
Source/bmalloc/bmalloc/IsoTLS.h
Source/bmalloc/bmalloc/IsoTLSInlines.h
Source/bmalloc/bmalloc/StdLibExtras.h
Source/bmalloc/test/testbmalloc.cpp

index aeead58..f33bd52 100644 (file)
@@ -19,6 +19,8 @@ set(bmalloc_SOURCES
     bmalloc/HeapKind.cpp
     bmalloc/IsoHeapImpl.cpp
     bmalloc/IsoPage.cpp
+    bmalloc/IsoSharedHeap.cpp
+    bmalloc/IsoSharedPage.cpp
     bmalloc/IsoTLS.cpp
     bmalloc/IsoTLSEntry.cpp
     bmalloc/IsoTLSLayout.cpp
index b5b1398..0b7b18e 100644 (file)
@@ -1,3 +1,92 @@
+2019-04-19  Yusuke Suzuki  <ysuzuki@apple.com>
+
+        [bmalloc] IsoHeap should have lower tier using shared IsoPage
+        https://bugs.webkit.org/show_bug.cgi?id=196837
+
+        Reviewed by Filip Pizlo.
+
+        IsoHeap had a scalability problem. Once one instance is allocated from IsoHeap, it immediately allocates 16KB page for this type.
+        But some types allocate only a few instances. It leads to memory wastage, and it also limits the scalability of IsoHeap since
+        we need to carefully select classes which will be confined in IsoHeap due to this characteristics. If we can remove this wastage,
+        we can apply IsoHeap more aggressively without causing memory regression, this is the goal of this patch.
+
+        In this patch, we introduce a slow tier to IsoHeap allocation. Initially, the allocator for a certain type allocates instances from
+        a shared page with the other allocators, and eventually, the allocator tiers up and gets dedicated pages if instances of the type
+        are allocated a lot. This "shared" tier is slow, but it is totally OK because we will tier up to the normal fast tier if allocation
+        frequently happens. Even the instance is allocated from pages shared with the other allocators, we still make the allocated memory
+        region dedicated to the specific type: once a memory region is allocated for a certain type from a shared page, this region continues
+        being used only for this type even after this memory is freed. To summarize the changes:
+
+        1. We introduce "shared" tier to IsoHeap allocation. Up to N (N = 8 for now, but we can pick any power-of-two numbers up to 32) allocations,
+           we continue using this tier. We allocate memory from shared pages so that we do not waste 16KB pages for types which only allocates a few instances.
+
+        2. We eventually tier up to the "fast" tier, and eventually tier down to the "shared" tier too. We measure the period between slow paths,
+           and switch the appropriate tier for the type. Currently, we use 1 seconds as heuristics. We also count # of allocations per cycle to
+           avoid pathological slow downs.
+
+        3. Shared page mechanism must keep the characteristics of IsoHeap. Once a memory region is allocated for a certain type, this memory region
+           must be dedicated to this type. We keep track the allocated memory regions from shared pages in IsoHeapImpl, and ensure that we never
+           reuse a memory region for a different type.
+
+        This patch improves PLUM2 by 1.4% (128.4MB v.s. 126.62MB), and early Speedometer2 results are performance-neutral.
+
+        * CMakeLists.txt:
+        * bmalloc.xcodeproj/project.pbxproj:
+        * bmalloc/Algorithm.h:
+        (bmalloc::roundUpToMultipleOfImpl):
+        (bmalloc::roundUpToMultipleOf):
+        * bmalloc/BCompiler.h:
+        * bmalloc/BExport.h:
+        * bmalloc/FreeList.h:
+        * bmalloc/IsoAllocator.h:
+        * bmalloc/IsoAllocatorInlines.h:
+        (bmalloc::IsoAllocator<Config>::allocateSlow):
+        * bmalloc/IsoDeallocator.h:
+        * bmalloc/IsoDeallocatorInlines.h:
+        (bmalloc::IsoDeallocator<Config>::deallocate):
+        * bmalloc/IsoHeapImpl.h:
+        * bmalloc/IsoHeapImplInlines.h:
+        (bmalloc::IsoHeapImpl<Config>::scavenge):
+        (bmalloc::IsoHeapImpl<Config>::forEachLiveObject):
+        (bmalloc::IsoHeapImpl<Config>::updateAllocationMode):
+        (bmalloc::IsoHeapImpl<Config>::allocateFromShared):
+        * bmalloc/IsoPage.h:
+        (bmalloc::IsoPageBase::IsoPageBase):
+        (bmalloc::IsoPageBase::isShared const):
+        * bmalloc/IsoPageInlines.h:
+        (bmalloc::IsoPage<Config>::IsoPage):
+        (bmalloc::IsoPageBase::pageFor):
+        (bmalloc::IsoPage<Config>::pageFor):
+        (bmalloc::IsoPage<Config>::free):
+        * bmalloc/IsoSharedConfig.h: Copied from Source/bmalloc/bmalloc/BExport.h.
+        * bmalloc/IsoSharedHeap.cpp: Copied from Source/bmalloc/bmalloc/BExport.h.
+        * bmalloc/IsoSharedHeap.h: Copied from Source/bmalloc/bmalloc/IsoAllocator.h.
+        (bmalloc::VariadicBumpAllocator::VariadicBumpAllocator):
+        (bmalloc::IsoSharedHeap::IsoSharedHeap):
+        * bmalloc/IsoSharedHeapInlines.h: Added.
+        (bmalloc::VariadicBumpAllocator::allocate):
+        (bmalloc::IsoSharedHeap::allocateNew):
+        (bmalloc::IsoSharedHeap::allocateSlow):
+        * bmalloc/IsoSharedPage.cpp: Copied from Source/bmalloc/bmalloc/BExport.h.
+        (bmalloc::IsoSharedPage::tryCreate):
+        * bmalloc/IsoSharedPage.h: Copied from Source/bmalloc/bmalloc/IsoDeallocator.h.
+        (bmalloc::IsoSharedPage::IsoSharedPage):
+        (bmalloc::indexSlotFor):
+        * bmalloc/IsoSharedPageInlines.h: Added.
+        (bmalloc::IsoSharedPage::free):
+        (bmalloc::IsoSharedPage::startAllocating):
+        (bmalloc::IsoSharedPage::stopAllocating):
+        * bmalloc/IsoTLS.h:
+        * bmalloc/IsoTLSInlines.h:
+        (bmalloc::IsoTLS::deallocateImpl):
+        (bmalloc::IsoTLS::deallocateFast):
+        (bmalloc::IsoTLS::deallocateSlow):
+        * bmalloc/StdLibExtras.h:
+        (bmalloc::bitwise_cast):
+        * test/testbmalloc.cpp:
+        (testIsoMallocAndFreeFast):
+        (run):
+
 2019-04-18  Yusuke Suzuki  <ysuzuki@apple.com>
 
         Unreviewed, fix build failure
index 233806e..92f85cf 100644 (file)
                AD14AD2A202529C700890E3B /* ProcessCheck.mm in Sources */ = {isa = PBXBuildFile; fileRef = AD14AD28202529B000890E3B /* ProcessCheck.mm */; };
                DE8B13B321CC5D9F00A63FCD /* BVMTags.h in Headers */ = {isa = PBXBuildFile; fileRef = DE8B13B221CC5D9F00A63FCD /* BVMTags.h */; settings = {ATTRIBUTES = (Private, ); }; };
                E31E74802238CA5C005D084A /* StaticPerProcess.h in Headers */ = {isa = PBXBuildFile; fileRef = E31E747F2238CA5B005D084A /* StaticPerProcess.h */; settings = {ATTRIBUTES = (Private, ); }; };
+               E3A413C9226061140037F470 /* IsoSharedPageInlines.h in Headers */ = {isa = PBXBuildFile; fileRef = E3A413C8226061140037F470 /* IsoSharedPageInlines.h */; settings = {ATTRIBUTES = (Private, ); }; };
+               E3F24402225D2C0100A0E0C3 /* IsoSharedPage.h in Headers */ = {isa = PBXBuildFile; fileRef = E3F24401225D2C0100A0E0C3 /* IsoSharedPage.h */; settings = {ATTRIBUTES = (Private, ); }; };
+               E3F24404225D2C7600A0E0C3 /* IsoSharedPage.cpp in Sources */ = {isa = PBXBuildFile; fileRef = E3F24403225D2C7600A0E0C3 /* IsoSharedPage.cpp */; };
+               E3FBB5A0225EADB000DB6FBD /* IsoSharedConfig.h in Headers */ = {isa = PBXBuildFile; fileRef = E3FBB59D225EADB000DB6FBD /* IsoSharedConfig.h */; settings = {ATTRIBUTES = (Private, ); }; };
+               E3FBB5A1225EADB000DB6FBD /* IsoSharedHeap.cpp in Sources */ = {isa = PBXBuildFile; fileRef = E3FBB59E225EADB000DB6FBD /* IsoSharedHeap.cpp */; };
+               E3FBB5A2225EADB000DB6FBD /* IsoSharedHeap.h in Headers */ = {isa = PBXBuildFile; fileRef = E3FBB59F225EADB000DB6FBD /* IsoSharedHeap.h */; settings = {ATTRIBUTES = (Private, ); }; };
+               E3FBB5A4225ECAD200DB6FBD /* IsoSharedHeapInlines.h in Headers */ = {isa = PBXBuildFile; fileRef = E3FBB5A3225ECAD200DB6FBD /* IsoSharedHeapInlines.h */; settings = {ATTRIBUTES = (Private, ); }; };
 /* End PBXBuildFile section */
 
 /* Begin PBXContainerItemProxy section */
                AD14AD28202529B000890E3B /* ProcessCheck.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; name = ProcessCheck.mm; path = bmalloc/ProcessCheck.mm; sourceTree = "<group>"; };
                DE8B13B221CC5D9F00A63FCD /* BVMTags.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; name = BVMTags.h; path = bmalloc/BVMTags.h; sourceTree = "<group>"; };
                E31E747F2238CA5B005D084A /* StaticPerProcess.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = StaticPerProcess.h; path = bmalloc/StaticPerProcess.h; sourceTree = "<group>"; };
+               E3A413C8226061140037F470 /* IsoSharedPageInlines.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = IsoSharedPageInlines.h; path = bmalloc/IsoSharedPageInlines.h; sourceTree = "<group>"; };
+               E3F24401225D2C0100A0E0C3 /* IsoSharedPage.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = IsoSharedPage.h; path = bmalloc/IsoSharedPage.h; sourceTree = "<group>"; };
+               E3F24403225D2C7600A0E0C3 /* IsoSharedPage.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = IsoSharedPage.cpp; path = bmalloc/IsoSharedPage.cpp; sourceTree = "<group>"; };
+               E3FBB59D225EADB000DB6FBD /* IsoSharedConfig.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = IsoSharedConfig.h; path = bmalloc/IsoSharedConfig.h; sourceTree = "<group>"; };
+               E3FBB59E225EADB000DB6FBD /* IsoSharedHeap.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = IsoSharedHeap.cpp; path = bmalloc/IsoSharedHeap.cpp; sourceTree = "<group>"; };
+               E3FBB59F225EADB000DB6FBD /* IsoSharedHeap.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = IsoSharedHeap.h; path = bmalloc/IsoSharedHeap.h; sourceTree = "<group>"; };
+               E3FBB5A3225ECAD200DB6FBD /* IsoSharedHeapInlines.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = IsoSharedHeapInlines.h; path = bmalloc/IsoSharedHeapInlines.h; sourceTree = "<group>"; };
 /* End PBXFileReference section */
 
 /* Begin PBXFrameworksBuildPhase section */
                                0F7EB8071F9541AD00F1ABCB /* IsoPage.h */,
                                0F7EB80A1F9541AE00F1ABCB /* IsoPageInlines.h */,
                                0F7EB8041F9541AD00F1ABCB /* IsoPageTrigger.h */,
+                               E3FBB59D225EADB000DB6FBD /* IsoSharedConfig.h */,
+                               E3FBB59E225EADB000DB6FBD /* IsoSharedHeap.cpp */,
+                               E3FBB59F225EADB000DB6FBD /* IsoSharedHeap.h */,
+                               E3FBB5A3225ECAD200DB6FBD /* IsoSharedHeapInlines.h */,
+                               E3F24403225D2C7600A0E0C3 /* IsoSharedPage.cpp */,
+                               E3F24401225D2C0100A0E0C3 /* IsoSharedPage.h */,
+                               E3A413C8226061140037F470 /* IsoSharedPageInlines.h */,
                                0F7EB80F1F9541AE00F1ABCB /* IsoTLS.cpp */,
                                0F7EB81B1F9541AF00F1ABCB /* IsoTLS.h */,
                                0F7EB81C1F9541AF00F1ABCB /* IsoTLSAllocatorEntry.h */,
                                0F7EB82E1F9541B000F1ABCB /* IsoPage.h in Headers */,
                                0F7EB8311F9541B000F1ABCB /* IsoPageInlines.h in Headers */,
                                0F7EB82B1F9541B000F1ABCB /* IsoPageTrigger.h in Headers */,
+                               E3FBB5A0225EADB000DB6FBD /* IsoSharedConfig.h in Headers */,
+                               E3FBB5A2225EADB000DB6FBD /* IsoSharedHeap.h in Headers */,
+                               E3FBB5A4225ECAD200DB6FBD /* IsoSharedHeapInlines.h in Headers */,
+                               E3F24402225D2C0100A0E0C3 /* IsoSharedPage.h in Headers */,
+                               E3A413C9226061140037F470 /* IsoSharedPageInlines.h in Headers */,
                                0F7EB8421F9541B000F1ABCB /* IsoTLS.h in Headers */,
                                0F7EB8431F9541B000F1ABCB /* IsoTLSAllocatorEntry.h in Headers */,
                                0F7EB8481F9541B000F1ABCB /* IsoTLSAllocatorEntryInlines.h in Headers */,
                                0FD557331F7EDB7B00B1F0A3 /* HeapKind.cpp in Sources */,
                                0F7EB83B1F9541B000F1ABCB /* IsoHeapImpl.cpp in Sources */,
                                0F5549EF1FB54704007FF75A /* IsoPage.cpp in Sources */,
+                               E3FBB5A1225EADB000DB6FBD /* IsoSharedHeap.cpp in Sources */,
+                               E3F24404225D2C7600A0E0C3 /* IsoSharedPage.cpp in Sources */,
                                0F7EB8361F9541B000F1ABCB /* IsoTLS.cpp in Sources */,
                                0F7EB8321F9541B000F1ABCB /* IsoTLSEntry.cpp in Sources */,
                                0F7EB83F1F9541B000F1ABCB /* IsoTLSLayout.cpp in Sources */,
index d872598..b387eda 100644 (file)
@@ -71,17 +71,22 @@ constexpr bool isPowerOfTwo(T size)
     return size && !(size & (size - 1));
 }
 
-template<typename T> inline T roundUpToMultipleOf(size_t divisor, T x)
+template<typename T> constexpr T roundUpToMultipleOfImpl(size_t divisor, T x)
 {
-    BASSERT(isPowerOfTwo(divisor));
     static_assert(sizeof(T) == sizeof(uintptr_t), "sizeof(T) must be equal to sizeof(uintptr_t).");
     return static_cast<T>((static_cast<uintptr_t>(x) + (divisor - 1)) & ~(divisor - 1));
 }
 
-template<size_t divisor, typename T> inline T roundUpToMultipleOf(T x)
+template<typename T> inline T roundUpToMultipleOf(size_t divisor, T x)
+{
+    BASSERT(isPowerOfTwo(divisor));
+    return roundUpToMultipleOfImpl(divisor, x);
+}
+
+template<size_t divisor, typename T> constexpr T roundUpToMultipleOf(T x)
 {
     static_assert(isPowerOfTwo(divisor), "'divisor' must be a power of two.");
-    return roundUpToMultipleOf(divisor, x);
+    return roundUpToMultipleOfImpl(divisor, x);
 }
 
 template<typename T> inline T* roundUpToMultipleOf(size_t divisor, T* x)
index 4ef835a..c824d2b 100644 (file)
 #define BNO_RETURN
 #endif
 
+/* BFALLTHROUGH */
+
+#if !defined(BFALLTHROUGH) && defined(__cplusplus) && defined(__has_cpp_attribute)
+
+#if __has_cpp_attribute(fallthrough)
+#define BFALLTHROUGH [[fallthrough]]
+#elif __has_cpp_attribute(clang::fallthrough)
+#define BFALLTHROUGH [[clang::fallthrough]]
+#elif __has_cpp_attribute(gnu::fallthrough)
+#define BFALLTHROUGH [[gnu::fallthrough]]
+#endif
+
+#endif // !defined(BFALLTHROUGH) && defined(__cplusplus) && defined(__has_cpp_attribute)
+
+#if !defined(BFALLTHROUGH)
+#define BFALLTHROUGH
+#endif
index 34a6071..163d00a 100644 (file)
@@ -32,3 +32,5 @@
 #else
 #define BEXPORT
 #endif
+
+#define BNOEXPORT
index 135aac0..7eca3e0 100644 (file)
@@ -31,6 +31,8 @@
 
 namespace bmalloc {
 
+class VariadicBumpAllocator;
+
 struct FreeCell {
     static uintptr_t scramble(FreeCell* cell, uintptr_t secret)
     {
@@ -57,6 +59,8 @@ struct FreeCell {
 
 class FreeList {
 public:
+    friend class VariadicBumpAllocator;
+
     BEXPORT FreeList();
     BEXPORT ~FreeList();
     
index eb9b041..30472c1 100644 (file)
@@ -32,12 +32,16 @@ namespace bmalloc {
 template<typename Config> class IsoPage;
 template<typename Config> class IsoHeapImpl;
 
+enum class AllocationMode : uint8_t { Init, Fast, Shared };
+
 template<typename Config>
 class IsoAllocator {
 public:
     IsoAllocator(IsoHeapImpl<Config>&);
     ~IsoAllocator();
     
+    AllocationMode considerUsingSharedAllocation();
+
     void* allocate(bool abortOnFailure);
     void scavenge();
     
index 561fae5..606b4b8 100644 (file)
@@ -28,7 +28,7 @@
 #include "BInline.h"
 #include "EligibilityResult.h"
 #include "IsoAllocator.h"
-#include "IsoHeapImpl.h"
+#include "IsoHeapImplInlines.h"
 #include "IsoPage.h"
 
 namespace bmalloc {
@@ -61,6 +61,18 @@ template<typename Config>
 BNO_INLINE void* IsoAllocator<Config>::allocateSlow(bool abortOnFailure)
 {
     std::lock_guard<Mutex> locker(m_heap->lock);
+
+    AllocationMode allocationMode = m_heap->updateAllocationMode();
+    if (allocationMode == AllocationMode::Shared) {
+        if (m_currentPage) {
+            m_currentPage->stopAllocating(m_freeList);
+            m_currentPage = nullptr;
+            m_freeList.clear();
+        }
+        return m_heap->allocateFromShared(abortOnFailure);
+    }
+
+    BASSERT(allocationMode == AllocationMode::Fast);
     
     EligibilityResult<Config> result = m_heap->takeFirstEligible();
     if (result.kind != EligibilityKind::Success) {
index a92c45d..e4f5fb5 100644 (file)
@@ -41,7 +41,8 @@ public:
     IsoDeallocator(Mutex& lock);
     ~IsoDeallocator();
     
-    void deallocate(void* p);
+    template<typename Type>
+    void deallocate(api::IsoHeap<Type>&, void* p);
     void scavenge();
     
 private:
index 2b4d2e2..7103ecb 100644 (file)
@@ -28,6 +28,7 @@
 #include "BInline.h"
 #include "IsoDeallocator.h"
 #include "IsoPage.h"
+#include "IsoSharedPage.h"
 #include "Mutex.h"
 #include <mutex>
 
@@ -45,12 +46,24 @@ IsoDeallocator<Config>::~IsoDeallocator()
 }
 
 template<typename Config>
-void IsoDeallocator<Config>::deallocate(void* ptr)
+template<typename Type>
+void IsoDeallocator<Config>::deallocate(api::IsoHeap<Type>& handle, void* ptr)
 {
     static constexpr bool verbose = false;
     if (verbose)
         fprintf(stderr, "%p: deallocating %p of size %u\n", &IsoPage<Config>::pageFor(ptr)->heap(), ptr, Config::objectSize);
 
+    // For allocation from shared pages, we deallocate immediately rather than batching deallocations with object log.
+    // The batching delays the reclamation of the shared cells, which can make allocator mistakenly think that "we exhaust shared
+    // cells because this is allocated a lot". Since the number of shared cells are limited, this immediate deallocation path
+    // should be rarely taken. If we see frequent malloc-and-free pattern, we tier up the allocator from shared mode to fast mode.
+    IsoPageBase* page = IsoPageBase::pageFor(ptr);
+    if (page->isShared()) {
+        std::lock_guard<Mutex> locker(*m_lock);
+        static_cast<IsoSharedPage*>(page)->free<Config>(handle, ptr);
+        return;
+    }
+
     if (m_objectLog.size() == m_objectLog.capacity())
         scavenge();
     
index 5e643dd..a90197a 100644 (file)
@@ -26,6 +26,7 @@
 #pragma once
 
 #include "BMalloced.h"
+#include "IsoAllocator.h"
 #include "IsoDirectoryPage.h"
 #include "IsoTLSAllocatorEntry.h"
 #include "PhysicalPageMap.h"
@@ -37,6 +38,11 @@ class AllIsoHeaps;
 class BEXPORT IsoHeapImplBase {
     MAKE_BMALLOCED;
 public:
+    static constexpr unsigned maxAllocationFromShared = 8;
+    static constexpr unsigned maxAllocationFromSharedMask = maxAllocationFromShared - 1;
+    static_assert(maxAllocationFromShared <= bmalloc::alignment, "");
+    static_assert(isPowerOfTwo(maxAllocationFromShared), "");
+
     virtual ~IsoHeapImplBase();
     
     virtual void scavenge(Vector<DeferredDecommit>&) = 0;
@@ -45,15 +51,20 @@ public:
     
     void scavengeNow();
     static void finishScavenging(Vector<DeferredDecommit>&);
-    
+
 protected:
     IsoHeapImplBase();
     void addToAllIsoHeaps();
 
-private:
+    friend class IsoSharedPage;
     friend class AllIsoHeaps;
     
     IsoHeapImplBase* m_next { nullptr };
+    std::chrono::steady_clock::time_point m_slowPathTimePoint;
+    std::array<void*, maxAllocationFromShared> m_sharedCells { };
+    unsigned m_numberOfAllocationsFromSharedInOneCycle { 0 };
+    unsigned m_usableBits { maxAllocationFromSharedMask };
+    AllocationMode m_allocationMode { AllocationMode::Init };
 };
 
 template<typename Config>
@@ -98,6 +109,9 @@ public:
 
     void isNowFreeable(void* ptr, size_t bytes);
     void isNoLongerFreeable(void* ptr, size_t bytes);
+
+    AllocationMode updateAllocationMode();
+    void* allocateFromShared(bool abortOnFailure);
     
     // It's almost always the caller's responsibility to grab the lock. This lock comes from the
     // PerProcess<IsoTLSDeallocatorEntry<Config>>::get()->lock. That's pretty weird, and we don't
index 4586f26..23e2b3c 100644 (file)
@@ -27,6 +27,8 @@
 
 #include "IsoHeapImpl.h"
 #include "IsoTLSDeallocatorEntry.h"
+#include "IsoSharedHeapInlines.h"
+#include "IsoSharedPageInlines.h"
 
 namespace bmalloc {
 
@@ -107,6 +109,8 @@ void IsoHeapImpl<Config>::scavenge(Vector<DeferredDecommit>& decommits)
             directory.scavenge(decommits);
         });
     m_directoryHighWatermark = 0;
+    m_numberOfAllocationsFromSharedInOneCycle = 0;
+    m_allocationMode = AllocationMode::Init;
 }
 
 template<typename Config>
@@ -176,6 +180,11 @@ void IsoHeapImpl<Config>::forEachLiveObject(const Func& func)
         [&] (IsoPage<Config>& page) {
             page.forEachLiveObject(func);
         });
+    for (unsigned index = 0; index < maxAllocationFromShared; ++index) {
+        void* pointer = m_sharedCells[index];
+        if (pointer && !(m_usableBits & (1U << index)))
+            func(pointer);
+    }
 }
 
 template<typename Config>
@@ -221,5 +230,80 @@ void IsoHeapImpl<Config>::isNoLongerFreeable(void* ptr, size_t bytes)
     m_freeableMemory -= bytes;
 }
 
+template<typename Config>
+AllocationMode IsoHeapImpl<Config>::updateAllocationMode()
+{
+    // Exhaust shared free cells, which means we should start activating the fast allocation mode for this type.
+    if (!m_usableBits) {
+        m_slowPathTimePoint = std::chrono::steady_clock::now();
+        return AllocationMode::Fast;
+    }
+
+    switch (m_allocationMode) {
+    case AllocationMode::Shared:
+        // Currently in the shared allocation mode. Until we exhaust shared free cells, continue using the shared allocation mode.
+        // But if we allocate so many shared cells within very short period, we should use the fast allocation mode instead.
+        // This avoids the following pathological case.
+        //
+        //     for (int i = 0; i < 1e6; ++i) {
+        //         auto* ptr = allocate();
+        //         ...
+        //         free(ptr);
+        //     }
+        if (m_numberOfAllocationsFromSharedInOneCycle <= IsoPage<Config>::numObjects)
+            return AllocationMode::Shared;
+        BFALLTHROUGH;
+
+    case AllocationMode::Fast: {
+        // The allocation pattern may change. We should check the allocation rate and decide which mode is more appropriate.
+        // If we don't go to the allocation slow path during 1~ seconds, we think the allocation becomes quiescent state.
+        auto now = std::chrono::steady_clock::now();
+        if ((now - m_slowPathTimePoint) < std::chrono::seconds(1)) {
+            m_slowPathTimePoint = now;
+            return AllocationMode::Fast;
+        }
+
+        m_numberOfAllocationsFromSharedInOneCycle = 0;
+        m_slowPathTimePoint = now;
+        return AllocationMode::Shared;
+    }
+
+    case AllocationMode::Init:
+        m_slowPathTimePoint = std::chrono::steady_clock::now();
+        return AllocationMode::Shared;
+    }
+
+    return AllocationMode::Shared;
+}
+
+template<typename Config>
+void* IsoHeapImpl<Config>::allocateFromShared(bool abortOnFailure)
+{
+    static constexpr bool verbose = false;
+
+    unsigned indexPlusOne = __builtin_ffs(m_usableBits);
+    BASSERT(indexPlusOne);
+    unsigned index = indexPlusOne - 1;
+    void* result = result = m_sharedCells[index];
+    if (result) {
+        if (verbose)
+            fprintf(stderr, "%p: allocated %p from shared again of size %u\n", this, result, Config::objectSize);
+    } else {
+        constexpr unsigned objectSizeWithHeapImplPointer = Config::objectSize + sizeof(uint8_t);
+        result = IsoSharedHeap::get()->allocateNew<objectSizeWithHeapImplPointer>(abortOnFailure);
+        if (!result)
+            return nullptr;
+        if (verbose)
+            fprintf(stderr, "%p: allocated %p from shared of size %u\n", this, result, Config::objectSize);
+        BASSERT(index < IsoHeapImplBase::maxAllocationFromShared);
+        *indexSlotFor<Config>(result) = index;
+        m_sharedCells[index] = result;
+    }
+    BASSERT(result);
+    m_usableBits &= (~(1U << index));
+    ++m_numberOfAllocationsFromSharedInOneCycle;
+    return result;
+}
+
 } // namespace bmalloc
 
index b909f04..5425b88 100644 (file)
 
 namespace bmalloc {
 
+class IsoHeapImplBase;
 template<typename Config> class IsoDirectoryBase;
 template<typename Config> class IsoHeapImpl;
 
 class IsoPageBase {
 public:    
     static constexpr size_t pageSize = 16384;
+
+    explicit IsoPageBase(bool isShared)
+        : m_isShared(isShared)
+    {
+    }
+
+    static IsoPageBase* pageFor(void*);
+
+    bool isShared() const { return m_isShared; }
     
 protected:
     BEXPORT static void* allocatePageMemory();
+
+    bool m_isShared { false };
 };
 
 template<typename Config>
@@ -81,9 +93,6 @@ private:
         return (sizeof(IsoPage) + Config::objectSize - 1) / Config::objectSize;
     }
     
-    IsoDirectoryBase<Config>& m_directory;
-    unsigned m_index { UINT_MAX };
-    
     // The possible states of a page are as follows. We mark these states by their corresponding
     // eligible, empty, and committed bits (respectively).
     //
@@ -101,13 +110,17 @@ private:
     // freeing.
 
     // This must have a trivial destructor.
-    
-    unsigned m_allocBits[bitsArrayLength(numObjects)];
-    unsigned m_numNonEmptyWords { 0 };
+
     bool m_eligibilityHasBeenNoted { true };
     bool m_isInUseForAllocation { false };
     DeferredTrigger<IsoPageTrigger::Eligible> m_eligibilityTrigger;
     DeferredTrigger<IsoPageTrigger::Empty> m_emptyTrigger;
+
+    IsoDirectoryBase<Config>& m_directory;
+    unsigned m_index { UINT_MAX };
+    
+    unsigned m_allocBits[bitsArrayLength(numObjects)];
+    unsigned m_numNonEmptyWords { 0 };
 };
 
 } // namespace bmalloc
index c1c69d5..f37b349 100644 (file)
@@ -27,6 +27,7 @@
 
 #include "CryptoRandom.h"
 #include "IsoDirectory.h"
+#include "IsoHeapImpl.h"
 #include "IsoPage.h"
 #include "StdLibExtras.h"
 #include "VMAllocate.h"
@@ -45,21 +46,28 @@ IsoPage<Config>* IsoPage<Config>::tryCreate(IsoDirectoryBase<Config>& directory,
 
 template<typename Config>
 IsoPage<Config>::IsoPage(IsoDirectoryBase<Config>& directory, unsigned index)
-    : m_directory(directory)
+    : IsoPageBase(false)
+    , m_directory(directory)
     , m_index(index)
 {
     memset(m_allocBits, 0, sizeof(m_allocBits));
 }
 
+inline IsoPageBase* IsoPageBase::pageFor(void* ptr)
+{
+    return reinterpret_cast<IsoPageBase*>(reinterpret_cast<uintptr_t>(ptr) & ~(pageSize - 1));
+}
+
 template<typename Config>
 IsoPage<Config>* IsoPage<Config>::pageFor(void* ptr)
 {
-    return reinterpret_cast<IsoPage<Config>*>(reinterpret_cast<uintptr_t>(ptr) & ~(pageSize - 1));
+    return reinterpret_cast<IsoPage<Config>*>(IsoPageBase::pageFor(ptr));
 }
 
 template<typename Config>
 void IsoPage<Config>::free(void* passedPtr)
 {
+    BASSERT(!m_isShared);
     unsigned offset = static_cast<char*>(passedPtr) - reinterpret_cast<char*>(this);
     unsigned index = offset / Config::objectSize;
     
diff --git a/Source/bmalloc/bmalloc/IsoSharedConfig.h b/Source/bmalloc/bmalloc/IsoSharedConfig.h
new file mode 100644 (file)
index 0000000..53f2bb7
--- /dev/null
@@ -0,0 +1,35 @@
+/*
+ * Copyright (C) 2019 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 "IsoConfig.h"
+
+namespace bmalloc {
+
+static constexpr unsigned alignmentForIsoSharedAllocation = 16;
+
+} // namespace bmalloc
+
diff --git a/Source/bmalloc/bmalloc/IsoSharedHeap.cpp b/Source/bmalloc/bmalloc/IsoSharedHeap.cpp
new file mode 100644 (file)
index 0000000..14c67df
--- /dev/null
@@ -0,0 +1,32 @@
+/*
+ * Copyright (C) 2019 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 "IsoSharedHeap.h"
+
+namespace bmalloc {
+
+DEFINE_STATIC_PER_PROCESS_STORAGE(IsoSharedHeap);
+
+} // namespace bmalloc
diff --git a/Source/bmalloc/bmalloc/IsoSharedHeap.h b/Source/bmalloc/bmalloc/IsoSharedHeap.h
new file mode 100644 (file)
index 0000000..c9d04ee
--- /dev/null
@@ -0,0 +1,74 @@
+/*
+ * Copyright (C) 2019 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 "IsoSharedConfig.h"
+#include "IsoSharedPage.h"
+#include "StaticPerProcess.h"
+
+namespace bmalloc {
+
+class AllIsoHeaps;
+
+class VariadicBumpAllocator {
+public:
+    VariadicBumpAllocator() = default;
+
+    VariadicBumpAllocator(char* payloadEnd, unsigned remaining)
+        : m_payloadEnd(payloadEnd)
+        , m_remaining(remaining)
+    {
+    }
+
+    template<unsigned, typename Func>
+    void* allocate(const Func& slowPath);
+
+private:
+    char* m_payloadEnd { nullptr };
+    unsigned m_remaining { 0 };
+};
+
+class IsoSharedHeap : public StaticPerProcess<IsoSharedHeap> {
+public:
+    IsoSharedHeap(std::lock_guard<Mutex>&)
+    {
+    }
+
+    template<unsigned>
+    void* allocateNew(bool abortOnFailure);
+
+private:
+    template<unsigned>
+    void* allocateSlow(bool abortOnFailure);
+
+    IsoSharedPage* m_currentPage { nullptr };
+    VariadicBumpAllocator m_allocator;
+};
+DECLARE_STATIC_PER_PROCESS_STORAGE(IsoSharedHeap);
+
+} // namespace bmalloc
+
+
diff --git a/Source/bmalloc/bmalloc/IsoSharedHeapInlines.h b/Source/bmalloc/bmalloc/IsoSharedHeapInlines.h
new file mode 100644 (file)
index 0000000..3e6356a
--- /dev/null
@@ -0,0 +1,80 @@
+/*
+ * Copyright (C) 2019 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 "IsoSharedHeap.h"
+
+#include "IsoSharedPage.h"
+#include "StdLibExtras.h"
+
+namespace bmalloc {
+
+template<unsigned objectSize, typename Func>
+void* VariadicBumpAllocator::allocate(const Func& slowPath)
+{
+    unsigned remaining = m_remaining;
+    if (!__builtin_usub_overflow(remaining, objectSize, &remaining)) {
+        m_remaining = remaining;
+        return m_payloadEnd - remaining - objectSize;
+    }
+    return slowPath();
+}
+
+template<unsigned passedObjectSize>
+void* IsoSharedHeap::allocateNew(bool abortOnFailure)
+{
+    std::lock_guard<Mutex> locker(mutex());
+    constexpr unsigned objectSize = roundUpToMultipleOf<alignmentForIsoSharedAllocation>(static_cast<uintptr_t>(passedObjectSize));
+    return m_allocator.template allocate<objectSize>(
+        [&] () -> void* {
+            return allocateSlow<passedObjectSize>(abortOnFailure);
+        });
+}
+
+template<unsigned passedObjectSize>
+BNO_INLINE void* IsoSharedHeap::allocateSlow(bool abortOnFailure)
+{
+    Scavenger& scavenger = *Scavenger::get();
+    scavenger.didStartGrowing();
+    scavenger.scheduleIfUnderMemoryPressure(IsoSharedPage::pageSize);
+
+    IsoSharedPage* page = IsoSharedPage::tryCreate();
+    if (!page) {
+        RELEASE_BASSERT(!abortOnFailure);
+        return nullptr;
+    }
+
+    if (m_currentPage)
+        m_currentPage->stopAllocating();
+
+    m_currentPage = page;
+    m_allocator = m_currentPage->startAllocating();
+
+    constexpr unsigned objectSize = roundUpToMultipleOf<alignmentForIsoSharedAllocation>(static_cast<uintptr_t>(passedObjectSize));
+    return m_allocator.allocate<objectSize>([] () { BCRASH(); return nullptr; });
+}
+
+} // namespace bmalloc
diff --git a/Source/bmalloc/bmalloc/IsoSharedPage.cpp b/Source/bmalloc/bmalloc/IsoSharedPage.cpp
new file mode 100644 (file)
index 0000000..25c4424
--- /dev/null
@@ -0,0 +1,43 @@
+/*
+ * Copyright (C) 2019 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 "IsoSharedPage.h"
+
+#include "StdLibExtras.h"
+#include "VMAllocate.h"
+
+namespace bmalloc {
+
+IsoSharedPage* IsoSharedPage::tryCreate()
+{
+    void* memory = allocatePageMemory();
+    if (!memory)
+        return nullptr;
+
+    return new (memory) IsoSharedPage();
+}
+
+
+} // namespace bmalloc
diff --git a/Source/bmalloc/bmalloc/IsoSharedPage.h b/Source/bmalloc/bmalloc/IsoSharedPage.h
new file mode 100644 (file)
index 0000000..224ef20
--- /dev/null
@@ -0,0 +1,60 @@
+/*
+ * Copyright (C) 2019 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 "IsoHeap.h"
+#include "IsoPage.h"
+#include "IsoSharedConfig.h"
+
+namespace bmalloc {
+
+class IsoHeapImplBase;
+
+class IsoSharedPage : public IsoPageBase {
+public:
+    BEXPORT static IsoSharedPage* tryCreate();
+
+    template<typename Config, typename Type>
+    void free(api::IsoHeap<Type>&, void*);
+    VariadicBumpAllocator startAllocating();
+    void stopAllocating();
+
+private:
+    IsoSharedPage()
+        : IsoPageBase(true)
+    {
+    }
+};
+
+template<typename Config>
+uint8_t* indexSlotFor(void* ptr)
+{
+    BASSERT(IsoPageBase::pageFor(ptr)->isShared());
+    return static_cast<uint8_t*>(ptr) + Config::objectSize;
+}
+
+} // namespace bmalloc
+
diff --git a/Source/bmalloc/bmalloc/IsoSharedPageInlines.h b/Source/bmalloc/bmalloc/IsoSharedPageInlines.h
new file mode 100644 (file)
index 0000000..f5730df
--- /dev/null
@@ -0,0 +1,73 @@
+/*
+ * Copyright (C) 2019 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 "IsoPage.h"
+#include "StdLibExtras.h"
+#include "VMAllocate.h"
+
+namespace bmalloc {
+
+// IsoSharedPage never becomes empty state again after we allocate some cells from IsoSharedPage. This makes IsoSharedPage management super simple.
+// This is because empty IsoSharedPage is still split into various different objects that should keep some part of virtual memory region dedicated.
+// We cannot set up bump allocation for such a page. Not freeing IsoSharedPages are OK since IsoSharedPage is only used for the lower tier of IsoHeap.
+template<typename Config, typename Type>
+void IsoSharedPage::free(api::IsoHeap<Type>& handle, void* ptr)
+{
+    auto& heapImpl = handle.impl();
+    uint8_t index = *indexSlotFor<Config>(ptr) & IsoHeapImplBase::maxAllocationFromSharedMask;
+    // IsoDeallocator::deallocate is called from delete operator. This is dispatched by vtable if virtual destructor exists.
+    // If vptr is replaced to the other vptr, we may accidentally chain this pointer to the incorrect HeapImplBase, which totally breaks the IsoHeap's goal.
+    // To harden that, we validate that this pointer is actually allocated for a specific HeapImplBase here by checking whether this pointer is listed in HeapImplBase's shared cells.
+    RELEASE_BASSERT(heapImpl.m_sharedCells[index] == ptr);
+    heapImpl.m_usableBits |= (1U << index);
+}
+
+inline VariadicBumpAllocator IsoSharedPage::startAllocating()
+{
+    static constexpr bool verbose = false;
+
+    if (verbose) {
+        fprintf(stderr, "%p: starting shared allocation.\n", this);
+        fprintf(stderr, "%p: preparing to shared bump.\n", this);
+    }
+
+    char* payloadEnd = reinterpret_cast<char*>(this) + IsoSharedPage::pageSize;
+    unsigned remaining = static_cast<unsigned>(roundDownToMultipleOf<alignmentForIsoSharedAllocation>(static_cast<uintptr_t>(IsoSharedPage::pageSize - sizeof(IsoSharedPage))));
+
+    return VariadicBumpAllocator(payloadEnd, remaining);
+}
+
+inline void IsoSharedPage::stopAllocating()
+{
+    static constexpr bool verbose = false;
+
+    if (verbose)
+        fprintf(stderr, "%p: stopping shared allocation.\n", this);
+}
+
+} // namespace bmalloc
+
index 27effc2..3cd9be9 100644 (file)
@@ -69,8 +69,8 @@ private:
     template<typename Config, typename Type>
     static void deallocateImpl(api::IsoHeap<Type>&, void* p);
     
-    template<typename Config>
-    void deallocateFast(unsigned offset, void* p);
+    template<typename Config, typename Type>
+    void deallocateFast(api::IsoHeap<Type>&, unsigned offset, void* p);
     
     template<typename Config, typename Type>
     static void deallocateSlow(api::IsoHeap<Type>&, void* p);
index 7ec4f7f..1d14b7a 100644 (file)
@@ -113,13 +113,13 @@ void IsoTLS::deallocateImpl(api::IsoHeap<Type>& handle, void* p)
     if (!tls || offset >= tls->m_extent)
         deallocateSlow<Config>(handle, p);
     else
-        tls->deallocateFast<Config>(offset, p);
+        tls->deallocateFast<Config>(handle, offset, p);
 }
 
-template<typename Config>
-void IsoTLS::deallocateFast(unsigned offset, void* p)
+template<typename Config, typename Type>
+void IsoTLS::deallocateFast(api::IsoHeap<Type>& handle, unsigned offset, void* p)
 {
-    reinterpret_cast<IsoDeallocator<Config>*>(m_data + offset)->deallocate(p);
+    reinterpret_cast<IsoDeallocator<Config>*>(m_data + offset)->deallocate(handle, p);
 }
 
 template<typename Config, typename Type>
@@ -145,7 +145,7 @@ BNO_INLINE void IsoTLS::deallocateSlow(api::IsoHeap<Type>& handle, void* p)
     
     IsoTLS* tls = ensureEntries(std::max(handle.allocatorOffset(), handle.deallocatorOffset()));
     
-    tls->deallocateFast<Config>(handle.deallocatorOffset(), p);
+    tls->deallocateFast<Config>(handle, handle.deallocatorOffset(), p);
 }
 
 inline IsoTLS* IsoTLS::get()
index e6b712e..746f640 100644 (file)
@@ -42,7 +42,7 @@ inline ToType bitwise_cast(FromType from)
     static_assert(__is_trivially_copyable(FromType), "bitwise_cast of non-trivially-copyable type!");
 #endif
     typename std::remove_const<ToType>::type to { };
-    std::memcpy(static_cast<void*>(&to), static_cast<void*>(&from), sizeof(to));
+    memcpy(static_cast<void*>(&to), static_cast<void*>(&from), sizeof(to));
     return to;
 }
 
index 0b7c742..d76bc16 100644 (file)
@@ -255,8 +255,19 @@ static void testIsoFlipFlopFragmentedPagesScavengeInMiddle288()
     assertClean(heap);
 }
 
+static void testIsoMallocAndFreeFast()
+{
+    static IsoHeap<char[256]> heap;
+    void* ptr = nullptr;
+    for (int i = 0; i < 1e6; ++i) {
+        ptr = heap.allocate();
+        heap.deallocate(ptr);
+    }
+    CHECK(!IsoPageBase::pageFor(ptr)->isShared());
+}
+
 class BisoMalloced {
-    MAKE_BISO_MALLOCED(BisoMalloced);
+    MAKE_BISO_MALLOCED(BisoMalloced, BNOEXPORT);
 public:
     BisoMalloced(int x, float y)
         : x(x)
@@ -310,6 +321,7 @@ static void run(const char* filter)
     RUN(testIsoFlipFlopFragmentedPages());
     RUN(testIsoFlipFlopFragmentedPagesScavengeInMiddle());
     RUN(testIsoFlipFlopFragmentedPagesScavengeInMiddle288());
+    RUN(testIsoMallocAndFreeFast());
     RUN(testBisoMalloced());
     RUN(testBisoMallocedInline());