Changeset 244481 in webkit


Ignore:
Timestamp:
Apr 19, 2019 8:29:40 PM (5 years ago)
Author:
ysuzuki@apple.com
Message:

[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.
  1. 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.
  1. 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):

Location:
trunk/Source/bmalloc
Files:
2 added
19 edited
5 copied

Legend:

Unmodified
Added
Removed

  • trunk/Source/bmalloc/CMakeLists.txt

    r233773 r244481  
    2020    bmalloc/IsoHeapImpl.cpp
    2121    bmalloc/IsoPage.cpp
     22    bmalloc/IsoSharedHeap.cpp
     23    bmalloc/IsoSharedPage.cpp
    2224    bmalloc/IsoTLS.cpp
    2325    bmalloc/IsoTLSEntry.cpp

  • trunk/Source/bmalloc/ChangeLog

    r244422 r244481  
     12019-04-19  Yusuke Suzuki  <ysuzuki@apple.com>
     2
     3        [bmalloc] IsoHeap should have lower tier using shared IsoPage
     4        https://bugs.webkit.org/show_bug.cgi?id=196837
     5
     6        Reviewed by Filip Pizlo.
     7
     8        IsoHeap had a scalability problem. Once one instance is allocated from IsoHeap, it immediately allocates 16KB page for this type.
     9        But some types allocate only a few instances. It leads to memory wastage, and it also limits the scalability of IsoHeap since
     10        we need to carefully select classes which will be confined in IsoHeap due to this characteristics. If we can remove this wastage,
     11        we can apply IsoHeap more aggressively without causing memory regression, this is the goal of this patch.
     12
     13        In this patch, we introduce a slow tier to IsoHeap allocation. Initially, the allocator for a certain type allocates instances from
     14        a shared page with the other allocators, and eventually, the allocator tiers up and gets dedicated pages if instances of the type
     15        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
     16        frequently happens. Even the instance is allocated from pages shared with the other allocators, we still make the allocated memory
     17        region dedicated to the specific type: once a memory region is allocated for a certain type from a shared page, this region continues
     18        being used only for this type even after this memory is freed. To summarize the changes:
     19
     20        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,
     21           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.
     22
     23        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,
     24           and switch the appropriate tier for the type. Currently, we use 1 seconds as heuristics. We also count # of allocations per cycle to
     25           avoid pathological slow downs.
     26
     27        3. Shared page mechanism must keep the characteristics of IsoHeap. Once a memory region is allocated for a certain type, this memory region
     28           must be dedicated to this type. We keep track the allocated memory regions from shared pages in IsoHeapImpl, and ensure that we never
     29           reuse a memory region for a different type.
     30
     31        This patch improves PLUM2 by 1.4% (128.4MB v.s. 126.62MB), and early Speedometer2 results are performance-neutral.
     32
     33        * CMakeLists.txt:
     34        * bmalloc.xcodeproj/project.pbxproj:
     35        * bmalloc/Algorithm.h:
     36        (bmalloc::roundUpToMultipleOfImpl):
     37        (bmalloc::roundUpToMultipleOf):
     38        * bmalloc/BCompiler.h:
     39        * bmalloc/BExport.h:
     40        * bmalloc/FreeList.h:
     41        * bmalloc/IsoAllocator.h:
     42        * bmalloc/IsoAllocatorInlines.h:
     43        (bmalloc::IsoAllocator<Config>::allocateSlow):
     44        * bmalloc/IsoDeallocator.h:
     45        * bmalloc/IsoDeallocatorInlines.h:
     46        (bmalloc::IsoDeallocator<Config>::deallocate):
     47        * bmalloc/IsoHeapImpl.h:
     48        * bmalloc/IsoHeapImplInlines.h:
     49        (bmalloc::IsoHeapImpl<Config>::scavenge):
     50        (bmalloc::IsoHeapImpl<Config>::forEachLiveObject):
     51        (bmalloc::IsoHeapImpl<Config>::updateAllocationMode):
     52        (bmalloc::IsoHeapImpl<Config>::allocateFromShared):
     53        * bmalloc/IsoPage.h:
     54        (bmalloc::IsoPageBase::IsoPageBase):
     55        (bmalloc::IsoPageBase::isShared const):
     56        * bmalloc/IsoPageInlines.h:
     57        (bmalloc::IsoPage<Config>::IsoPage):
     58        (bmalloc::IsoPageBase::pageFor):
     59        (bmalloc::IsoPage<Config>::pageFor):
     60        (bmalloc::IsoPage<Config>::free):
     61        * bmalloc/IsoSharedConfig.h: Copied from Source/bmalloc/bmalloc/BExport.h.
     62        * bmalloc/IsoSharedHeap.cpp: Copied from Source/bmalloc/bmalloc/BExport.h.
     63        * bmalloc/IsoSharedHeap.h: Copied from Source/bmalloc/bmalloc/IsoAllocator.h.
     64        (bmalloc::VariadicBumpAllocator::VariadicBumpAllocator):
     65        (bmalloc::IsoSharedHeap::IsoSharedHeap):
     66        * bmalloc/IsoSharedHeapInlines.h: Added.
     67        (bmalloc::VariadicBumpAllocator::allocate):
     68        (bmalloc::IsoSharedHeap::allocateNew):
     69        (bmalloc::IsoSharedHeap::allocateSlow):
     70        * bmalloc/IsoSharedPage.cpp: Copied from Source/bmalloc/bmalloc/BExport.h.
     71        (bmalloc::IsoSharedPage::tryCreate):
     72        * bmalloc/IsoSharedPage.h: Copied from Source/bmalloc/bmalloc/IsoDeallocator.h.
     73        (bmalloc::IsoSharedPage::IsoSharedPage):
     74        (bmalloc::indexSlotFor):
     75        * bmalloc/IsoSharedPageInlines.h: Added.
     76        (bmalloc::IsoSharedPage::free):
     77        (bmalloc::IsoSharedPage::startAllocating):
     78        (bmalloc::IsoSharedPage::stopAllocating):
     79        * bmalloc/IsoTLS.h:
     80        * bmalloc/IsoTLSInlines.h:
     81        (bmalloc::IsoTLS::deallocateImpl):
     82        (bmalloc::IsoTLS::deallocateFast):
     83        (bmalloc::IsoTLS::deallocateSlow):
     84        * bmalloc/StdLibExtras.h:
     85        (bmalloc::bitwise_cast):
     86        * test/testbmalloc.cpp:
     87        (testIsoMallocAndFreeFast):
     88        (run):
     89
    1902019-04-18  Yusuke Suzuki  <ysuzuki@apple.com>
    291

  • trunk/Source/bmalloc/bmalloc.xcodeproj/project.pbxproj

    r243357 r244481  
    145145                DE8B13B321CC5D9F00A63FCD /* BVMTags.h in Headers */ = {isa = PBXBuildFile; fileRef = DE8B13B221CC5D9F00A63FCD /* BVMTags.h */; settings = {ATTRIBUTES = (Private, ); }; };
    146146                E31E74802238CA5C005D084A /* StaticPerProcess.h in Headers */ = {isa = PBXBuildFile; fileRef = E31E747F2238CA5B005D084A /* StaticPerProcess.h */; settings = {ATTRIBUTES = (Private, ); }; };
     147                E3A413C9226061140037F470 /* IsoSharedPageInlines.h in Headers */ = {isa = PBXBuildFile; fileRef = E3A413C8226061140037F470 /* IsoSharedPageInlines.h */; settings = {ATTRIBUTES = (Private, ); }; };
     148                E3F24402225D2C0100A0E0C3 /* IsoSharedPage.h in Headers */ = {isa = PBXBuildFile; fileRef = E3F24401225D2C0100A0E0C3 /* IsoSharedPage.h */; settings = {ATTRIBUTES = (Private, ); }; };
     149                E3F24404225D2C7600A0E0C3 /* IsoSharedPage.cpp in Sources */ = {isa = PBXBuildFile; fileRef = E3F24403225D2C7600A0E0C3 /* IsoSharedPage.cpp */; };
     150                E3FBB5A0225EADB000DB6FBD /* IsoSharedConfig.h in Headers */ = {isa = PBXBuildFile; fileRef = E3FBB59D225EADB000DB6FBD /* IsoSharedConfig.h */; settings = {ATTRIBUTES = (Private, ); }; };
     151                E3FBB5A1225EADB000DB6FBD /* IsoSharedHeap.cpp in Sources */ = {isa = PBXBuildFile; fileRef = E3FBB59E225EADB000DB6FBD /* IsoSharedHeap.cpp */; };
     152                E3FBB5A2225EADB000DB6FBD /* IsoSharedHeap.h in Headers */ = {isa = PBXBuildFile; fileRef = E3FBB59F225EADB000DB6FBD /* IsoSharedHeap.h */; settings = {ATTRIBUTES = (Private, ); }; };
     153                E3FBB5A4225ECAD200DB6FBD /* IsoSharedHeapInlines.h in Headers */ = {isa = PBXBuildFile; fileRef = E3FBB5A3225ECAD200DB6FBD /* IsoSharedHeapInlines.h */; settings = {ATTRIBUTES = (Private, ); }; };
    147154/* End PBXBuildFile section */
    148155
    … …  
    312319                DE8B13B221CC5D9F00A63FCD /* BVMTags.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; name = BVMTags.h; path = bmalloc/BVMTags.h; sourceTree = "<group>"; };
    313320                E31E747F2238CA5B005D084A /* StaticPerProcess.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = StaticPerProcess.h; path = bmalloc/StaticPerProcess.h; sourceTree = "<group>"; };
     321                E3A413C8226061140037F470 /* IsoSharedPageInlines.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = IsoSharedPageInlines.h; path = bmalloc/IsoSharedPageInlines.h; sourceTree = "<group>"; };
     322                E3F24401225D2C0100A0E0C3 /* IsoSharedPage.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = IsoSharedPage.h; path = bmalloc/IsoSharedPage.h; sourceTree = "<group>"; };
     323                E3F24403225D2C7600A0E0C3 /* IsoSharedPage.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = IsoSharedPage.cpp; path = bmalloc/IsoSharedPage.cpp; sourceTree = "<group>"; };
     324                E3FBB59D225EADB000DB6FBD /* IsoSharedConfig.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = IsoSharedConfig.h; path = bmalloc/IsoSharedConfig.h; sourceTree = "<group>"; };
     325                E3FBB59E225EADB000DB6FBD /* IsoSharedHeap.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = IsoSharedHeap.cpp; path = bmalloc/IsoSharedHeap.cpp; sourceTree = "<group>"; };
     326                E3FBB59F225EADB000DB6FBD /* IsoSharedHeap.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = IsoSharedHeap.h; path = bmalloc/IsoSharedHeap.h; sourceTree = "<group>"; };
     327                E3FBB5A3225ECAD200DB6FBD /* IsoSharedHeapInlines.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = IsoSharedHeapInlines.h; path = bmalloc/IsoSharedHeapInlines.h; sourceTree = "<group>"; };
    314328/* End PBXFileReference section */
    315329
    … …  
    392406                                0F7EB80A1F9541AE00F1ABCB /* IsoPageInlines.h */,
    393407                                0F7EB8041F9541AD00F1ABCB /* IsoPageTrigger.h */,
     408                                E3FBB59D225EADB000DB6FBD /* IsoSharedConfig.h */,
     409                                E3FBB59E225EADB000DB6FBD /* IsoSharedHeap.cpp */,
     410                                E3FBB59F225EADB000DB6FBD /* IsoSharedHeap.h */,
     411                                E3FBB5A3225ECAD200DB6FBD /* IsoSharedHeapInlines.h */,
     412                                E3F24403225D2C7600A0E0C3 /* IsoSharedPage.cpp */,
     413                                E3F24401225D2C0100A0E0C3 /* IsoSharedPage.h */,
     414                                E3A413C8226061140037F470 /* IsoSharedPageInlines.h */,
    394415                                0F7EB80F1F9541AE00F1ABCB /* IsoTLS.cpp */,
    395416                                0F7EB81B1F9541AF00F1ABCB /* IsoTLS.h */,
    … …  
    639660                                0F7EB8311F9541B000F1ABCB /* IsoPageInlines.h in Headers */,
    640661                                0F7EB82B1F9541B000F1ABCB /* IsoPageTrigger.h in Headers */,
     662                                E3FBB5A0225EADB000DB6FBD /* IsoSharedConfig.h in Headers */,
     663                                E3FBB5A2225EADB000DB6FBD /* IsoSharedHeap.h in Headers */,
     664                                E3FBB5A4225ECAD200DB6FBD /* IsoSharedHeapInlines.h in Headers */,
     665                                E3F24402225D2C0100A0E0C3 /* IsoSharedPage.h in Headers */,
     666                                E3A413C9226061140037F470 /* IsoSharedPageInlines.h in Headers */,
    641667                                0F7EB8421F9541B000F1ABCB /* IsoTLS.h in Headers */,
    642668                                0F7EB8431F9541B000F1ABCB /* IsoTLSAllocatorEntry.h in Headers */,
    … …  
    810836                                0F7EB83B1F9541B000F1ABCB /* IsoHeapImpl.cpp in Sources */,
    811837                                0F5549EF1FB54704007FF75A /* IsoPage.cpp in Sources */,
     838                                E3FBB5A1225EADB000DB6FBD /* IsoSharedHeap.cpp in Sources */,
     839                                E3F24404225D2C7600A0E0C3 /* IsoSharedPage.cpp in Sources */,
    812840                                0F7EB8361F9541B000F1ABCB /* IsoTLS.cpp in Sources */,
    813841                                0F7EB8321F9541B000F1ABCB /* IsoTLSEntry.cpp in Sources */,

  • trunk/Source/bmalloc/bmalloc/Algorithm.h

    r240193 r244481  
    7272}
    7373
    74 template<typename T> inline T roundUpToMultipleOf(size_t divisor, T x)
     74template<typename T> constexpr T roundUpToMultipleOfImpl(size_t divisor, T x)
    7575{
    76     BASSERT(isPowerOfTwo(divisor));
    7776    static_assert(sizeof(T) == sizeof(uintptr_t), "sizeof(T) must be equal to sizeof(uintptr_t).");
    7877    return static_cast<T>((static_cast<uintptr_t>(x) + (divisor - 1)) & ~(divisor - 1));
    7978}
    8079
    81 template<size_t divisor, typename T> inline T roundUpToMultipleOf(T x)
     80template<typename T> inline T roundUpToMultipleOf(size_t divisor, T x)
     81{
     82    BASSERT(isPowerOfTwo(divisor));
     83    return roundUpToMultipleOfImpl(divisor, x);
     84}
     85
     86template<size_t divisor, typename T> constexpr T roundUpToMultipleOf(T x)
    8287{
    8388    static_assert(isPowerOfTwo(divisor), "'divisor' must be a power of two.");
    84     return roundUpToMultipleOf(divisor, x);
     89    return roundUpToMultipleOfImpl(divisor, x);
    8590}
    8691

  • trunk/Source/bmalloc/bmalloc/BCompiler.h

    r236450 r244481  
    5555#endif
    5656
     57/* BFALLTHROUGH */
     58
     59#if !defined(BFALLTHROUGH) && defined(__cplusplus) && defined(__has_cpp_attribute)
     60
     61#if __has_cpp_attribute(fallthrough)
     62#define BFALLTHROUGH [[fallthrough]]
     63#elif __has_cpp_attribute(clang::fallthrough)
     64#define BFALLTHROUGH [[clang::fallthrough]]
     65#elif __has_cpp_attribute(gnu::fallthrough)
     66#define BFALLTHROUGH [[gnu::fallthrough]]
     67#endif
     68
     69#endif // !defined(BFALLTHROUGH) && defined(__cplusplus) && defined(__has_cpp_attribute)
     70
     71#if !defined(BFALLTHROUGH)
     72#define BFALLTHROUGH
     73#endif

  • trunk/Source/bmalloc/bmalloc/BExport.h

    r226958 r244481  
    3333#define BEXPORT
    3434#endif
     35
     36#define BNOEXPORT

  • trunk/Source/bmalloc/bmalloc/FreeList.h

    r224537 r244481  
    3232namespace bmalloc {
    3333
     34class VariadicBumpAllocator;
     35
    3436struct FreeCell {
    3537    static uintptr_t scramble(FreeCell* cell, uintptr_t secret)
    … …  
    5860class FreeList {
    5961public:
     62    friend class VariadicBumpAllocator;
     63
    6064    BEXPORT FreeList();
    6165    BEXPORT ~FreeList();

  • trunk/Source/bmalloc/bmalloc/IsoAllocator.h

    r224537 r244481  
    3333template<typename Config> class IsoHeapImpl;
    3434
     35enum class AllocationMode : uint8_t { Init, Fast, Shared };
     36
    3537template<typename Config>
    3638class IsoAllocator {
    … …  
    3941    ~IsoAllocator();
    4042   
     43    AllocationMode considerUsingSharedAllocation();
     44
    4145    void* allocate(bool abortOnFailure);
    4246    void scavenge();

  • trunk/Source/bmalloc/bmalloc/IsoAllocatorInlines.h

    r224537 r244481  
    2929#include "EligibilityResult.h"
    3030#include "IsoAllocator.h"
    31 #include "IsoHeapImpl.h"
     31#include "IsoHeapImplInlines.h"
    3232#include "IsoPage.h"
    3333
    … …  
    6262{
    6363    std::lock_guard<Mutex> locker(m_heap->lock);
     64
     65    AllocationMode allocationMode = m_heap->updateAllocationMode();
     66    if (allocationMode == AllocationMode::Shared) {
     67        if (m_currentPage) {
     68            m_currentPage->stopAllocating(m_freeList);
     69            m_currentPage = nullptr;
     70            m_freeList.clear();
     71        }
     72        return m_heap->allocateFromShared(abortOnFailure);
     73    }
     74
     75    BASSERT(allocationMode == AllocationMode::Fast);
    6476   
    6577    EligibilityResult<Config> result = m_heap->takeFirstEligible();

  • trunk/Source/bmalloc/bmalloc/IsoDeallocator.h

    r230308 r244481  
    4242    ~IsoDeallocator();
    4343   
    44     void deallocate(void* p);
     44    template<typename Type>
     45    void deallocate(api::IsoHeap<Type>&, void* p);
    4546    void scavenge();
    4647   

  • trunk/Source/bmalloc/bmalloc/IsoDeallocatorInlines.h

    r224537 r244481  
    2929#include "IsoDeallocator.h"
    3030#include "IsoPage.h"
     31#include "IsoSharedPage.h"
    3132#include "Mutex.h"
    3233#include <mutex>
    … …  
    4647
    4748template<typename Config>
    48 void IsoDeallocator<Config>::deallocate(void* ptr)
     49template<typename Type>
     50void IsoDeallocator<Config>::deallocate(api::IsoHeap<Type>& handle, void* ptr)
    4951{
    5052    static constexpr bool verbose = false;
    5153    if (verbose)
    5254        fprintf(stderr, "%p: deallocating %p of size %u\n", &IsoPage<Config>::pageFor(ptr)->heap(), ptr, Config::objectSize);
     55
     56    // For allocation from shared pages, we deallocate immediately rather than batching deallocations with object log.
     57    // The batching delays the reclamation of the shared cells, which can make allocator mistakenly think that "we exhaust shared
     58    // cells because this is allocated a lot". Since the number of shared cells are limited, this immediate deallocation path
     59    // should be rarely taken. If we see frequent malloc-and-free pattern, we tier up the allocator from shared mode to fast mode.
     60    IsoPageBase* page = IsoPageBase::pageFor(ptr);
     61    if (page->isShared()) {
     62        std::lock_guard<Mutex> locker(*m_lock);
     63        static_cast<IsoSharedPage*>(page)->free<Config>(handle, ptr);
     64        return;
     65    }
    5366
    5467    if (m_objectLog.size() == m_objectLog.capacity())

  • trunk/Source/bmalloc/bmalloc/IsoHeapImpl.h

    r243144 r244481  
    2727
    2828#include "BMalloced.h"
     29#include "IsoAllocator.h"
    2930#include "IsoDirectoryPage.h"
    3031#include "IsoTLSAllocatorEntry.h"
    … …  
    3839    MAKE_BMALLOCED;
    3940public:
     41    static constexpr unsigned maxAllocationFromShared = 8;
     42    static constexpr unsigned maxAllocationFromSharedMask = maxAllocationFromShared - 1;
     43    static_assert(maxAllocationFromShared <= bmalloc::alignment, "");
     44    static_assert(isPowerOfTwo(maxAllocationFromShared), "");
     45
    4046    virtual ~IsoHeapImplBase();
    4147   
    … …  
    4652    void scavengeNow();
    4753    static void finishScavenging(Vector<DeferredDecommit>&);
    48    
     54
    4955protected:
    5056    IsoHeapImplBase();
    5157    void addToAllIsoHeaps();
    5258
    53 private:
     59    friend class IsoSharedPage;
    5460    friend class AllIsoHeaps;
    5561   
    5662    IsoHeapImplBase* m_next { nullptr };
     63    std::chrono::steady_clock::time_point m_slowPathTimePoint;
     64    std::array<void*, maxAllocationFromShared> m_sharedCells { };
     65    unsigned m_numberOfAllocationsFromSharedInOneCycle { 0 };
     66    unsigned m_usableBits { maxAllocationFromSharedMask };
     67    AllocationMode m_allocationMode { AllocationMode::Init };
    5768};
    5869
    … …  
    99110    void isNowFreeable(void* ptr, size_t bytes);
    100111    void isNoLongerFreeable(void* ptr, size_t bytes);
     112
     113    AllocationMode updateAllocationMode();
     114    void* allocateFromShared(bool abortOnFailure);
    101115   
    102116    // It's almost always the caller's responsibility to grab the lock. This lock comes from the

  • trunk/Source/bmalloc/bmalloc/IsoHeapImplInlines.h

    r243144 r244481  
    2828#include "IsoHeapImpl.h"
    2929#include "IsoTLSDeallocatorEntry.h"
     30#include "IsoSharedHeapInlines.h"
     31#include "IsoSharedPageInlines.h"
    3032
    3133namespace bmalloc {
    … …  
    108110        });
    109111    m_directoryHighWatermark = 0;
     112    m_numberOfAllocationsFromSharedInOneCycle = 0;
     113    m_allocationMode = AllocationMode::Init;
    110114}
    111115
    … …  
    177181            page.forEachLiveObject(func);
    178182        });
     183    for (unsigned index = 0; index < maxAllocationFromShared; ++index) {
     184        void* pointer = m_sharedCells[index];
     185        if (pointer && !(m_usableBits & (1U << index)))
     186            func(pointer);
     187    }
    179188}
    180189
    … …  
    222231}
    223232
     233template<typename Config>
     234AllocationMode IsoHeapImpl<Config>::updateAllocationMode()
     235{
     236    // Exhaust shared free cells, which means we should start activating the fast allocation mode for this type.
     237    if (!m_usableBits) {
     238        m_slowPathTimePoint = std::chrono::steady_clock::now();
     239        return AllocationMode::Fast;
     240    }
     241
     242    switch (m_allocationMode) {
     243    case AllocationMode::Shared:
     244        // Currently in the shared allocation mode. Until we exhaust shared free cells, continue using the shared allocation mode.
     245        // But if we allocate so many shared cells within very short period, we should use the fast allocation mode instead.
     246        // This avoids the following pathological case.
     247        //
     248        //     for (int i = 0; i < 1e6; ++i) {
     249        //         auto* ptr = allocate();
     250        //         ...
     251        //         free(ptr);
     252        //     }
     253        if (m_numberOfAllocationsFromSharedInOneCycle <= IsoPage<Config>::numObjects)
     254            return AllocationMode::Shared;
     255        BFALLTHROUGH;
     256
     257    case AllocationMode::Fast: {
     258        // The allocation pattern may change. We should check the allocation rate and decide which mode is more appropriate.
     259        // If we don't go to the allocation slow path during 1~ seconds, we think the allocation becomes quiescent state.
     260        auto now = std::chrono::steady_clock::now();
     261        if ((now - m_slowPathTimePoint) < std::chrono::seconds(1)) {
     262            m_slowPathTimePoint = now;
     263            return AllocationMode::Fast;
     264        }
     265
     266        m_numberOfAllocationsFromSharedInOneCycle = 0;
     267        m_slowPathTimePoint = now;
     268        return AllocationMode::Shared;
     269    }
     270
     271    case AllocationMode::Init:
     272        m_slowPathTimePoint = std::chrono::steady_clock::now();
     273        return AllocationMode::Shared;
     274    }
     275
     276    return AllocationMode::Shared;
     277}
     278
     279template<typename Config>
     280void* IsoHeapImpl<Config>::allocateFromShared(bool abortOnFailure)
     281{
     282    static constexpr bool verbose = false;
     283
     284    unsigned indexPlusOne = __builtin_ffs(m_usableBits);
     285    BASSERT(indexPlusOne);
     286    unsigned index = indexPlusOne - 1;
     287    void* result = result = m_sharedCells[index];
     288    if (result) {
     289        if (verbose)
     290            fprintf(stderr, "%p: allocated %p from shared again of size %u\n", this, result, Config::objectSize);
     291    } else {
     292        constexpr unsigned objectSizeWithHeapImplPointer = Config::objectSize + sizeof(uint8_t);
     293        result = IsoSharedHeap::get()->allocateNew<objectSizeWithHeapImplPointer>(abortOnFailure);
     294        if (!result)
     295            return nullptr;
     296        if (verbose)
     297            fprintf(stderr, "%p: allocated %p from shared of size %u\n", this, result, Config::objectSize);
     298        BASSERT(index < IsoHeapImplBase::maxAllocationFromShared);
     299        *indexSlotFor<Config>(result) = index;
     300        m_sharedCells[index] = result;
     301    }
     302    BASSERT(result);
     303    m_usableBits &= (~(1U << index));
     304    ++m_numberOfAllocationsFromSharedInOneCycle;
     305    return result;
     306}
     307
    224308} // namespace bmalloc
    225309

  • trunk/Source/bmalloc/bmalloc/IsoPage.h

    r225125 r244481  
    3333namespace bmalloc {
    3434
     35class IsoHeapImplBase;
    3536template<typename Config> class IsoDirectoryBase;
    3637template<typename Config> class IsoHeapImpl;
    … …  
    3940public:   
    4041    static constexpr size_t pageSize = 16384;
     42
     43    explicit IsoPageBase(bool isShared)
     44        : m_isShared(isShared)
     45    {
     46    }
     47
     48    static IsoPageBase* pageFor(void*);
     49
     50    bool isShared() const { return m_isShared; }
    4151   
    4252protected:
    4353    BEXPORT static void* allocatePageMemory();
     54
     55    bool m_isShared { false };
    4456};
    4557
    … …  
    8294    }
    8395   
    84     IsoDirectoryBase<Config>& m_directory;
    85     unsigned m_index { UINT_MAX };
    86    
    8796    // The possible states of a page are as follows. We mark these states by their corresponding
    8897    // eligible, empty, and committed bits (respectively).
    … …  
    102111
    103112    // This must have a trivial destructor.
    104    
    105     unsigned m_allocBits[bitsArrayLength(numObjects)];
    106     unsigned m_numNonEmptyWords { 0 };
     113
    107114    bool m_eligibilityHasBeenNoted { true };
    108115    bool m_isInUseForAllocation { false };
    109116    DeferredTrigger<IsoPageTrigger::Eligible> m_eligibilityTrigger;
    110117    DeferredTrigger<IsoPageTrigger::Empty> m_emptyTrigger;
     118
     119    IsoDirectoryBase<Config>& m_directory;
     120    unsigned m_index { UINT_MAX };
     121   
     122    unsigned m_allocBits[bitsArrayLength(numObjects)];
     123    unsigned m_numNonEmptyWords { 0 };
    111124};
    112125

  • trunk/Source/bmalloc/bmalloc/IsoPageInlines.h

    r242892 r244481  
    2828#include "CryptoRandom.h"
    2929#include "IsoDirectory.h"
     30#include "IsoHeapImpl.h"
    3031#include "IsoPage.h"
    3132#include "StdLibExtras.h"
    … …  
    4647template<typename Config>
    4748IsoPage<Config>::IsoPage(IsoDirectoryBase<Config>& directory, unsigned index)
    48     : m_directory(directory)
     49    : IsoPageBase(false)
     50    , m_directory(directory)
    4951    , m_index(index)
    5052{
    … …  
    5254}
    5355
     56inline IsoPageBase* IsoPageBase::pageFor(void* ptr)
     57{
     58    return reinterpret_cast<IsoPageBase*>(reinterpret_cast<uintptr_t>(ptr) & ~(pageSize - 1));
     59}
     60
    5461template<typename Config>
    5562IsoPage<Config>* IsoPage<Config>::pageFor(void* ptr)
    5663{
    57     return reinterpret_cast<IsoPage<Config>*>(reinterpret_cast<uintptr_t>(ptr) & ~(pageSize - 1));
     64    return reinterpret_cast<IsoPage<Config>*>(IsoPageBase::pageFor(ptr));
    5865}
    5966
    … …  
    6168void IsoPage<Config>::free(void* passedPtr)
    6269{
     70    BASSERT(!m_isShared);
    6371    unsigned offset = static_cast<char*>(passedPtr) - reinterpret_cast<char*>(this);
    6472    unsigned index = offset / Config::objectSize;

  • trunk/Source/bmalloc/bmalloc/IsoSharedConfig.h

    r244480 r244481  
    11/*
    2  * Copyright (C) 2017 Apple Inc. All rights reserved.
     2 * Copyright (C) 2019 Apple Inc. All rights reserved.
    33 *
    44 * Redistribution and use in source and binary forms, with or without
    … …  
    2121 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
    2222 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
    23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
     23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
    2424 */
    2525
    2626#pragma once
    2727
    28 #include "BPlatform.h"
     28#include "IsoConfig.h"
    2929
    30 #if BUSE(EXPORT_MACROS)
    31 #define BEXPORT __attribute__((visibility("default")))
    32 #else
    33 #define BEXPORT
    34 #endif
     30namespace bmalloc {
     31
     32static constexpr unsigned alignmentForIsoSharedAllocation = 16;
     33
     34} // namespace bmalloc
     35

  • trunk/Source/bmalloc/bmalloc/IsoSharedHeap.cpp

    r244480 r244481  
    11/*
    2  * Copyright (C) 2017 Apple Inc. All rights reserved.
     2 * Copyright (C) 2019 Apple Inc. All rights reserved.
    33 *
    44 * Redistribution and use in source and binary forms, with or without
    … …  
    2121 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
    2222 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
    23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
     23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
    2424 */
    2525
    26 #pragma once
     26#include "IsoSharedHeap.h"
    2727
    28 #include "BPlatform.h"
     28namespace bmalloc {
    2929
    30 #if BUSE(EXPORT_MACROS)
    31 #define BEXPORT __attribute__((visibility("default")))
    32 #else
    33 #define BEXPORT
    34 #endif
     30DEFINE_STATIC_PER_PROCESS_STORAGE(IsoSharedHeap);
     31
     32} // namespace bmalloc

  • trunk/Source/bmalloc/bmalloc/IsoSharedHeap.h

    r244480 r244481  
    11/*
    2  * Copyright (C) 2017 Apple Inc. All rights reserved.
     2 * Copyright (C) 2019 Apple Inc. All rights reserved.
    33 *
    44 * Redistribution and use in source and binary forms, with or without
    … …  
    2121 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
    2222 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
    23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
     23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
    2424 */
    2525
    2626#pragma once
    2727
    28 #include "FreeList.h"
     28#include "IsoSharedConfig.h"
     29#include "IsoSharedPage.h"
     30#include "StaticPerProcess.h"
    2931
    3032namespace bmalloc {
    3133
    32 template<typename Config> class IsoPage;
    33 template<typename Config> class IsoHeapImpl;
     34class AllIsoHeaps;
    3435
    35 template<typename Config>
    36 class IsoAllocator {
     36class VariadicBumpAllocator {
    3737public:
    38     IsoAllocator(IsoHeapImpl<Config>&);
    39     ~IsoAllocator();
    40    
    41     void* allocate(bool abortOnFailure);
    42     void scavenge();
    43    
     38    VariadicBumpAllocator() = default;
     39
     40    VariadicBumpAllocator(char* payloadEnd, unsigned remaining)
     41        : m_payloadEnd(payloadEnd)
     42        , m_remaining(remaining)
     43    {
     44    }
     45
     46    template<unsigned, typename Func>
     47    void* allocate(const Func& slowPath);
     48
    4449private:
     50    char* m_payloadEnd { nullptr };
     51    unsigned m_remaining { 0 };
     52};
     53
     54class IsoSharedHeap : public StaticPerProcess<IsoSharedHeap> {
     55public:
     56    IsoSharedHeap(std::lock_guard<Mutex>&)
     57    {
     58    }
     59
     60    template<unsigned>
     61    void* allocateNew(bool abortOnFailure);
     62
     63private:
     64    template<unsigned>
    4565    void* allocateSlow(bool abortOnFailure);
    46    
    47     IsoHeapImpl<Config>* m_heap { nullptr };
    48     FreeList m_freeList;
    49     IsoPage<Config>* m_currentPage { nullptr };
     66
     67    IsoSharedPage* m_currentPage { nullptr };
     68    VariadicBumpAllocator m_allocator;
    5069};
     70DECLARE_STATIC_PER_PROCESS_STORAGE(IsoSharedHeap);
    5171
    5272} // namespace bmalloc
    5373
     74

  • trunk/Source/bmalloc/bmalloc/IsoSharedPage.cpp

    r244480 r244481  
    11/*
    2  * Copyright (C) 2017 Apple Inc. All rights reserved.
     2 * Copyright (C) 2019 Apple Inc. All rights reserved.
    33 *
    44 * Redistribution and use in source and binary forms, with or without
    … …  
    2121 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
    2222 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
    23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
     23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
    2424 */
    2525
    26 #pragma once
     26#include "IsoSharedPage.h"
    2727
    28 #include "BPlatform.h"
     28#include "StdLibExtras.h"
     29#include "VMAllocate.h"
    2930
    30 #if BUSE(EXPORT_MACROS)
    31 #define BEXPORT __attribute__((visibility("default")))
    32 #else
    33 #define BEXPORT
    34 #endif
     31namespace bmalloc {
     32
     33IsoSharedPage* IsoSharedPage::tryCreate()
     34{
     35    void* memory = allocatePageMemory();
     36    if (!memory)
     37        return nullptr;
     38
     39    return new (memory) IsoSharedPage();
     40}
     41
     42
     43} // namespace bmalloc

  • trunk/Source/bmalloc/bmalloc/IsoSharedPage.h

    r244480 r244481  
    11/*
    2  * Copyright (C) 2017 Apple Inc. All rights reserved.
     2 * Copyright (C) 2019 Apple Inc. All rights reserved.
    33 *
    44 * Redistribution and use in source and binary forms, with or without
    … …  
    2121 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
    2222 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
    23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
     23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
    2424 */
    2525
    2626#pragma once
    2727
    28 #include "FixedVector.h"
     28#include "IsoHeap.h"
    2929#include "IsoPage.h"
    30 #include "Mutex.h"
     30#include "IsoSharedConfig.h"
    3131
    3232namespace bmalloc {
    3333
     34class IsoHeapImplBase;
     35
     36class IsoSharedPage : public IsoPageBase {
     37public:
     38    BEXPORT static IsoSharedPage* tryCreate();
     39
     40    template<typename Config, typename Type>
     41    void free(api::IsoHeap<Type>&, void*);
     42    VariadicBumpAllocator startAllocating();
     43    void stopAllocating();
     44
     45private:
     46    IsoSharedPage()
     47        : IsoPageBase(true)
     48    {
     49    }
     50};
     51
    3452template<typename Config>
    35 class IsoDeallocator {
    36 public:
    37     static constexpr unsigned logsPerPage = 2;
    38     static constexpr unsigned logCapacity =
    39         (IsoPageBase::pageSize / Config::objectSize + logsPerPage - 1) / logsPerPage;
    40    
    41     IsoDeallocator(Mutex& lock);
    42     ~IsoDeallocator();
    43    
    44     void deallocate(void* p);
    45     void scavenge();
    46    
    47 private:
    48     Mutex* m_lock;
    49     FixedVector<void*, logCapacity> m_objectLog;
    50 };
     53uint8_t* indexSlotFor(void* ptr)
     54{
     55    BASSERT(IsoPageBase::pageFor(ptr)->isShared());
     56    return static_cast<uint8_t*>(ptr) + Config::objectSize;
     57}
    5158
    5259} // namespace bmalloc

  • trunk/Source/bmalloc/bmalloc/IsoTLS.h

    r241847 r244481  
    7070    static void deallocateImpl(api::IsoHeap<Type>&, void* p);
    7171   
    72     template<typename Config>
    73     void deallocateFast(unsigned offset, void* p);
     72    template<typename Config, typename Type>
     73    void deallocateFast(api::IsoHeap<Type>&, unsigned offset, void* p);
    7474   
    7575    template<typename Config, typename Type>

  • trunk/Source/bmalloc/bmalloc/IsoTLSInlines.h

    r242938 r244481  
    114114        deallocateSlow<Config>(handle, p);
    115115    else
    116         tls->deallocateFast<Config>(offset, p);
     116        tls->deallocateFast<Config>(handle, offset, p);
    117117}
    118118
    119 template<typename Config>
    120 void IsoTLS::deallocateFast(unsigned offset, void* p)
     119template<typename Config, typename Type>
     120void IsoTLS::deallocateFast(api::IsoHeap<Type>& handle, unsigned offset, void* p)
    121121{
    122     reinterpret_cast<IsoDeallocator<Config>*>(m_data + offset)->deallocate(p);
     122    reinterpret_cast<IsoDeallocator<Config>*>(m_data + offset)->deallocate(handle, p);
    123123}
    124124
    … …  
    146146    IsoTLS* tls = ensureEntries(std::max(handle.allocatorOffset(), handle.deallocatorOffset()));
    147147   
    148     tls->deallocateFast<Config>(handle.deallocatorOffset(), p);
     148    tls->deallocateFast<Config>(handle, handle.deallocatorOffset(), p);
    149149}
    150150

  • trunk/Source/bmalloc/bmalloc/StdLibExtras.h

    r242892 r244481  
    4343#endif
    4444    typename std::remove_const<ToType>::type to { };
    45     std::memcpy(static_cast<void*>(&to), static_cast<void*>(&from), sizeof(to));
     45    memcpy(static_cast<void*>(&to), static_cast<void*>(&from), sizeof(to));
    4646    return to;
    4747}

  • trunk/Source/bmalloc/test/testbmalloc.cpp

    r242938 r244481  
    256256}
    257257
     258static void testIsoMallocAndFreeFast()
     259{
     260    static IsoHeap<char[256]> heap;
     261    void* ptr = nullptr;
     262    for (int i = 0; i < 1e6; ++i) {
     263        ptr = heap.allocate();
     264        heap.deallocate(ptr);
     265    }
     266    CHECK(!IsoPageBase::pageFor(ptr)->isShared());
     267}
     268
    258269class BisoMalloced {
    259     MAKE_BISO_MALLOCED(BisoMalloced);
     270    MAKE_BISO_MALLOCED(BisoMalloced, BNOEXPORT);
    260271public:
    261272    BisoMalloced(int x, float y)
    … …  
    311322    RUN(testIsoFlipFlopFragmentedPagesScavengeInMiddle());
    312323    RUN(testIsoFlipFlopFragmentedPagesScavengeInMiddle288());
     324    RUN(testIsoMallocAndFreeFast());
    313325    RUN(testBisoMalloced());
    314326    RUN(testBisoMallocedInline());
Note: See TracChangeset for help on using the changeset viewer.