⚠ Archived content — this site is no longer maintained.   Current WebKit documentation is at docs.webkit.org.

Changeset 261667 in webkit


Ignore:
Timestamp:
May 13, 2020, 6:09:19 PM (6 years ago)
Author:
ysuzuki@apple.com
Message:

[bmalloc] Introduce lock-less ObjectType query
​https://bugs.webkit.org/show_bug.cgi?id=211809

Reviewed by Mark Lam.

This patch introduces ObjectTypeTable, which allows lock-less ObjectType query for Chunk*.
It has bit-vector to store ObjectType per address. And each bit represents 1MB of VA region since
Chunk*'s size is at least 1MB and ObjectType is 1bit data. Every time we extend this bit-vector
to support larger VA region, we do not free the old bit-vector. Since we always allocate power-of-2
sized bit-vector, # of extension is limited and it does not waste much memory because Chunk's size
is enough large (1MB). Since each 4KB page on macOS can represent a bit-vector for 32GB VA region,
in practice, this extension almost never happens. I verified that 4KB page can handle memory
allocations in JetStream2 and Gmail.

  • CMakeLists.txt:
  • bmalloc.xcodeproj/project.pbxproj:
  • bmalloc/Algorithm.h:

(bmalloc::roundUpToPowerOfTwo):

  • bmalloc/Deallocator.cpp:

(bmalloc::Deallocator::deallocateSlowCase):

  • bmalloc/Heap.cpp:

(bmalloc::Heap::freeableMemory):
(bmalloc::Heap::decommitLargeRange):
(bmalloc::Heap::scavenge):
(bmalloc::Heap::scavengeToHighWatermark):
(bmalloc::Heap::allocateSmallChunk):
(bmalloc::Heap::deallocateSmallChunk):
(bmalloc::Heap::deallocateSmallLine):
(bmalloc::Heap::splitAndAllocate):
(bmalloc::Heap::isLarge): Deleted.

  • bmalloc/Heap.h:

(bmalloc::Heap::isLarge):

  • bmalloc/ObjectType.cpp:

(bmalloc::objectType):

  • bmalloc/ObjectTypeTable.cpp: Added.

(bmalloc::ObjectTypeTable::set):

  • bmalloc/ObjectTypeTable.h: Added.

(bmalloc::ObjectTypeTable::convertToIndex):
(bmalloc::ObjectTypeTable::Bits::Bits):
(bmalloc::ObjectTypeTable::Bits::previous const):
(bmalloc::ObjectTypeTable::Bits::begin const):
(bmalloc::ObjectTypeTable::Bits::end const):
(bmalloc::ObjectTypeTable::Bits::count const):
(bmalloc::ObjectTypeTable::Bits::sizeInBytes const):
(bmalloc::ObjectTypeTable::Bits::words const):
(bmalloc::ObjectTypeTable::Bits::words):
(bmalloc::ObjectTypeTable::ObjectTypeTable):
(bmalloc::ObjectTypeTable::get):
(bmalloc::ObjectTypeTable::Bits::get):
(bmalloc::ObjectTypeTable::Bits::set):
(bmalloc::ObjectTypeTable::Bits::wordForIndex):

  • bmalloc/Scavenger.cpp:

(bmalloc::Scavenger::scavenge):
(bmalloc::Scavenger::partialScavenge):
(bmalloc::Scavenger::freeableMemory):

Location:
trunk/Source/bmalloc
Files:
2 added
9 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/bmalloc/CMakeLists.txt

    r261444 r261667  
    3030    bmalloc/Mutex.cpp
    3131    bmalloc/ObjectType.cpp
     32    bmalloc/ObjectTypeTable.cpp
    3233    bmalloc/PerProcess.cpp
    3334    bmalloc/Scavenger.cpp
    … …  
    111112    bmalloc/Object.h
    112113    bmalloc/ObjectType.h
     114    bmalloc/ObjectTypeTable.h
    113115    bmalloc/Packed.h
    114116    bmalloc/PerHeapKind.h

  • trunk/Source/bmalloc/ChangeLog

    r261543 r261667  
     12020-05-13  Yusuke Suzuki  <ysuzuki@apple.com>
     2
     3        [bmalloc] Introduce lock-less ObjectType query
     4        https://bugs.webkit.org/show_bug.cgi?id=211809
     5
     6        Reviewed by Mark Lam.
     7
     8        This patch introduces ObjectTypeTable, which allows lock-less ObjectType query for Chunk*.
     9        It has bit-vector to store ObjectType per address. And each bit represents 1MB of VA region since
     10        Chunk*'s size is at least 1MB and ObjectType is 1bit data. Every time we extend this bit-vector
     11        to support larger VA region, we do not free the old bit-vector. Since we always allocate power-of-2
     12        sized bit-vector, # of extension is limited and it does not waste much memory because Chunk's size
     13        is enough large (1MB). Since each 4KB page on macOS can represent a bit-vector for 32GB VA region,
     14        in practice, this extension almost never happens. I verified that 4KB page can handle memory
     15        allocations in JetStream2 and Gmail.
     16
     17        * CMakeLists.txt:
     18        * bmalloc.xcodeproj/project.pbxproj:
     19        * bmalloc/Algorithm.h:
     20        (bmalloc::roundUpToPowerOfTwo):
     21        * bmalloc/Deallocator.cpp:
     22        (bmalloc::Deallocator::deallocateSlowCase):
     23        * bmalloc/Heap.cpp:
     24        (bmalloc::Heap::freeableMemory):
     25        (bmalloc::Heap::decommitLargeRange):
     26        (bmalloc::Heap::scavenge):
     27        (bmalloc::Heap::scavengeToHighWatermark):
     28        (bmalloc::Heap::allocateSmallChunk):
     29        (bmalloc::Heap::deallocateSmallChunk):
     30        (bmalloc::Heap::deallocateSmallLine):
     31        (bmalloc::Heap::splitAndAllocate):
     32        (bmalloc::Heap::isLarge): Deleted.
     33        * bmalloc/Heap.h:
     34        (bmalloc::Heap::isLarge):
     35        * bmalloc/ObjectType.cpp:
     36        (bmalloc::objectType):
     37        * bmalloc/ObjectTypeTable.cpp: Added.
     38        (bmalloc::ObjectTypeTable::set):
     39        * bmalloc/ObjectTypeTable.h: Added.
     40        (bmalloc::ObjectTypeTable::convertToIndex):
     41        (bmalloc::ObjectTypeTable::Bits::Bits):
     42        (bmalloc::ObjectTypeTable::Bits::previous const):
     43        (bmalloc::ObjectTypeTable::Bits::begin const):
     44        (bmalloc::ObjectTypeTable::Bits::end const):
     45        (bmalloc::ObjectTypeTable::Bits::count const):
     46        (bmalloc::ObjectTypeTable::Bits::sizeInBytes const):
     47        (bmalloc::ObjectTypeTable::Bits::words const):
     48        (bmalloc::ObjectTypeTable::Bits::words):
     49        (bmalloc::ObjectTypeTable::ObjectTypeTable):
     50        (bmalloc::ObjectTypeTable::get):
     51        (bmalloc::ObjectTypeTable::Bits::get):
     52        (bmalloc::ObjectTypeTable::Bits::set):
     53        (bmalloc::ObjectTypeTable::Bits::wordForIndex):
     54        * bmalloc/Scavenger.cpp:
     55        (bmalloc::Scavenger::scavenge):
     56        (bmalloc::Scavenger::partialScavenge):
     57        (bmalloc::Scavenger::freeableMemory):
     58
    1592020-05-11  Basuke Suzuki  <basuke.suzuki@sony.com>
    260

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

    r260712 r261667  
    140140                E31E74802238CA5C005D084A /* StaticPerProcess.h in Headers */ = {isa = PBXBuildFile; fileRef = E31E747F2238CA5B005D084A /* StaticPerProcess.h */; settings = {ATTRIBUTES = (Private, ); }; };
    141141                E328D84D23CEB38900545B18 /* Packed.h in Headers */ = {isa = PBXBuildFile; fileRef = E328D84C23CEB38900545B18 /* Packed.h */; settings = {ATTRIBUTES = (Private, ); }; };
     142                E378A9DF246B68720029C2BB /* ObjectTypeTable.cpp in Sources */ = {isa = PBXBuildFile; fileRef = E378A9DE246B686A0029C2BB /* ObjectTypeTable.cpp */; };
     143                E378A9E0246B68750029C2BB /* ObjectTypeTable.h in Headers */ = {isa = PBXBuildFile; fileRef = E378A9DD246B686A0029C2BB /* ObjectTypeTable.h */; settings = {ATTRIBUTES = (Private, ); }; };
    142144                E3A413C9226061140037F470 /* IsoSharedPageInlines.h in Headers */ = {isa = PBXBuildFile; fileRef = E3A413C8226061140037F470 /* IsoSharedPageInlines.h */; settings = {ATTRIBUTES = (Private, ); }; };
    143145                E3F24402225D2C0100A0E0C3 /* IsoSharedPage.h in Headers */ = {isa = PBXBuildFile; fileRef = E3F24401225D2C0100A0E0C3 /* IsoSharedPage.h */; settings = {ATTRIBUTES = (Private, ); }; };
    … …  
    294296                E31E747F2238CA5B005D084A /* StaticPerProcess.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = StaticPerProcess.h; path = bmalloc/StaticPerProcess.h; sourceTree = "<group>"; };
    295297                E328D84C23CEB38900545B18 /* Packed.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = Packed.h; path = bmalloc/Packed.h; sourceTree = "<group>"; };
     298                E378A9DD246B686A0029C2BB /* ObjectTypeTable.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; name = ObjectTypeTable.h; path = bmalloc/ObjectTypeTable.h; sourceTree = "<group>"; };
     299                E378A9DE246B686A0029C2BB /* ObjectTypeTable.cpp */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.cpp.cpp; name = ObjectTypeTable.cpp; path = bmalloc/ObjectTypeTable.cpp; sourceTree = "<group>"; };
    296300                E3A413C8226061140037F470 /* IsoSharedPageInlines.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = IsoSharedPageInlines.h; path = bmalloc/IsoSharedPageInlines.h; sourceTree = "<group>"; };
    297301                E3F24401225D2C0100A0E0C3 /* IsoSharedPage.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = IsoSharedPage.h; path = bmalloc/IsoSharedPage.h; sourceTree = "<group>"; };
    … …  
    491495                                14105E8318E14374003A106E /* ObjectType.cpp */,
    492496                                1485656018A43DBA00ED6942 /* ObjectType.h */,
     497                                E378A9DE246B686A0029C2BB /* ObjectTypeTable.cpp */,
     498                                E378A9DD246B686A0029C2BB /* ObjectTypeTable.h */,
    493499                                795AB3C6206E0D250074FE76 /* PhysicalPageMap.h */,
    494500                                AD14AD27202529A600890E3B /* ProcessCheck.h */,
    … …  
    646652                                144BE11F1CA346520099C8C0 /* Object.h in Headers */,
    647653                                14DD789318F48D0F00950702 /* ObjectType.h in Headers */,
     654                                E378A9E0246B68750029C2BB /* ObjectTypeTable.h in Headers */,
    648655                                E328D84D23CEB38900545B18 /* Packed.h in Headers */,
    649656                                0F5BF1491F22A8D80029D91D /* PerHeapKind.h in Headers */,
    … …  
    778785                                143CB81C19022BC900B16A45 /* Mutex.cpp in Sources */,
    779786                                14F271C818EA3990008C152F /* ObjectType.cpp in Sources */,
     787                                E378A9DF246B68720029C2BB /* ObjectTypeTable.cpp in Sources */,
    780788                                0F26A7A5205483130090A141 /* PerProcess.cpp in Sources */,
    781789                                AD14AD2A202529C700890E3B /* ProcessCheck.mm in Sources */,

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

    r254708 r261667  
    220220}
    221221
     222// From http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2
     223constexpr uint32_t roundUpToPowerOfTwo(uint32_t v)
     224{
     225    v--;
     226    v |= v >> 1;
     227    v |= v >> 2;
     228    v |= v >> 4;
     229    v |= v >> 8;
     230    v |= v >> 16;
     231    v++;
     232    return v;
     233}
     234
    222235} // namespace bmalloc
    223236

  • trunk/Source/bmalloc/bmalloc/Deallocator.cpp

    r254781 r261667  
    6969        return;
    7070
    71     UniqueLockHolder lock(Heap::mutex());
    72     if (m_heap.isLarge(lock, object)) {
     71    if (m_heap.isLarge(object)) {
     72        UniqueLockHolder lock(Heap::mutex());
    7373        m_heap.deallocateLarge(lock, object);
    7474        return;
    7575    }
    7676
    77     if (m_objectLog.size() == m_objectLog.capacity())
     77    if (m_objectLog.size() == m_objectLog.capacity()) {
     78        UniqueLockHolder lock(Heap::mutex());
    7879        processObjectLog(lock);
     80    }
    7981
    8082    m_objectLog.push(object);

  • trunk/Source/bmalloc/bmalloc/Heap.cpp

    r256088 r261667  
    8585}
    8686
    87 size_t Heap::freeableMemory(const LockHolder&)
     87size_t Heap::freeableMemory(UniqueLockHolder&)
    8888{
    8989    return m_freeableMemory;
    … …  
    102102}
    103103
    104 void Heap::decommitLargeRange(const LockHolder&, LargeRange& range, BulkDecommit& decommitter)
     104void Heap::decommitLargeRange(UniqueLockHolder&, LargeRange& range, BulkDecommit& decommitter)
    105105{
    106106    m_footprint -= range.totalPhysicalSize();
    … …  
    118118
    119119#if BUSE(PARTIAL_SCAVENGE)
    120 void Heap::scavenge(const LockHolder& lock, BulkDecommit& decommitter)
     120void Heap::scavenge(UniqueLockHolder& lock, BulkDecommit& decommitter)
    121121#else
    122 void Heap::scavenge(const LockHolder& lock, BulkDecommit& decommitter, size_t& deferredDecommits)
     122void Heap::scavenge(UniqueLockHolder& lock, BulkDecommit& decommitter, size_t& deferredDecommits)
    123123#endif
    124124{
    … …  
    151151    for (auto& list : m_chunkCache) {
    152152        while (!list.isEmpty())
    153             deallocateSmallChunk(list.pop(), &list - &m_chunkCache[0]);
     153            deallocateSmallChunk(lock, list.pop(), &list - &m_chunkCache[0]);
    154154    }
    155155
    … …  
    173173
    174174#if BUSE(PARTIAL_SCAVENGE)
    175 void Heap::scavengeToHighWatermark(const LockHolder& lock, BulkDecommit& decommitter)
     175void Heap::scavengeToHighWatermark(UniqueLockHolder& lock, BulkDecommit& decommitter)
    176176{
    177177    void* newHighWaterMark = nullptr;
    … …  
    214214        Chunk* chunk = new (memory) Chunk(pageSize);
    215215
    216         m_objectTypes.set(chunk, ObjectType::Small);
     216        m_objectTypes.set(lock, chunk, ObjectType::Small);
    217217
    218218        size_t accountedInFreeable = 0;
    … …  
    245245}
    246246
    247 void Heap::deallocateSmallChunk(Chunk* chunk, size_t pageClass)
    248 {
    249     m_objectTypes.set(chunk, ObjectType::Large);
     247void Heap::deallocateSmallChunk(UniqueLockHolder& lock, Chunk* chunk, size_t pageClass)
     248{
     249    m_objectTypes.set(lock, chunk, ObjectType::Large);
    250250   
    251251    size_t size = m_largeAllocated.remove(chunk);
    … …  
    358358
    359359        if (!m_chunkCache[pageClass].isEmpty())
    360             deallocateSmallChunk(m_chunkCache[pageClass].pop(), pageClass);
     360            deallocateSmallChunk(lock, m_chunkCache[pageClass].pop(), pageClass);
    361361
    362362        m_chunkCache[pageClass].push(chunk);
    … …  
    496496}
    497497
    498 LargeRange Heap::splitAndAllocate(UniqueLockHolder&, LargeRange& range, size_t alignment, size_t size)
     498LargeRange Heap::splitAndAllocate(UniqueLockHolder& lock, LargeRange& range, size_t alignment, size_t size)
    499499{
    500500    RELEASE_BASSERT(isActiveHeapKind(m_kind));
    … …  
    538538    }
    539539
    540     m_objectTypes.set(Chunk::get(range.begin()), ObjectType::Large);
     540    m_objectTypes.set(lock, Chunk::get(range.begin()), ObjectType::Large);
    541541
    542542    m_largeAllocated.set(range.begin(), range.size());
    … …  
    622622}
    623623
    624 bool Heap::isLarge(UniqueLockHolder&, void* object)
    625 {
    626     return m_objectTypes.get(Object(object).chunk()) == ObjectType::Large;
    627 }
    628 
    629624size_t Heap::largeSize(UniqueLockHolder&, void* object)
    630625{

  • trunk/Source/bmalloc/bmalloc/Heap.h

    r256088 r261667  
    3636#include "Mutex.h"
    3737#include "Object.h"
     38#include "ObjectTypeTable.h"
    3839#include "PerHeapKind.h"
    3940#include "PerProcess.h"
    … …  
    7071    void deallocateLarge(UniqueLockHolder&, void*);
    7172
    72     bool isLarge(UniqueLockHolder&, void*);
     73    bool isLarge(void*);
    7374    size_t largeSize(UniqueLockHolder&, void*);
    7475    void shrinkLarge(UniqueLockHolder&, const Range&, size_t);
    7576
    7677#if BUSE(PARTIAL_SCAVENGE)
    77     void scavengeToHighWatermark(const LockHolder&, BulkDecommit&);
    78     void scavenge(const LockHolder&, BulkDecommit&);
     78    void scavengeToHighWatermark(UniqueLockHolder&, BulkDecommit&);
     79    void scavenge(UniqueLockHolder&, BulkDecommit&);
    7980#else
    80     void scavenge(const LockHolder&, BulkDecommit&, size_t& deferredDecommits);
     81    void scavenge(UniqueLockHolder&, BulkDecommit&, size_t& deferredDecommits);
    8182#endif
    82     void scavenge(const LockHolder&, BulkDecommit&, size_t& freed, size_t goal);
     83    void scavenge(UniqueLockHolder&, BulkDecommit&, size_t& freed, size_t goal);
    8384
    84     size_t freeableMemory(const LockHolder&);
     85    size_t freeableMemory(UniqueLockHolder&);
    8586    size_t footprint();
    8687
    … …  
    9394
    9495private:
    95     void decommitLargeRange(const LockHolder&, LargeRange&, BulkDecommit&);
     96    void decommitLargeRange(UniqueLockHolder&, LargeRange&, BulkDecommit&);
    9697
    9798    struct LargeObjectHash {
    … …  
    118119
    119120    void allocateSmallChunk(UniqueLockHolder&, size_t pageClass, FailureAction);
    120     void deallocateSmallChunk(Chunk*, size_t pageClass);
     121    void deallocateSmallChunk(UniqueLockHolder&, Chunk*, size_t pageClass);
    121122
    122123    LargeRange tryAllocateLargeChunk(size_t alignment, size_t);
    … …  
    136137    LargeMap m_largeFree;
    137138
    138     Map<Chunk*, ObjectType, ChunkHash> m_objectTypes;
     139    ObjectTypeTable m_objectTypes;
    139140
    140141    Scavenger* m_scavenger { nullptr };
    … …  
    169170}
    170171
     172inline bool Heap::isLarge(void* object)
     173{
     174    return m_objectTypes.get(Object(object).chunk()) == ObjectType::Large;
     175}
     176
    171177} // namespace bmalloc
    172178

  • trunk/Source/bmalloc/bmalloc/ObjectType.cpp

    r254781 r261667  
    3939            return ObjectType::Small;
    4040
    41         UniqueLockHolder lock(Heap::mutex());
    42         if (heap.isLarge(lock, object))
     41        if (heap.isLarge(object))
    4342            return ObjectType::Large;
    4443    }

  • trunk/Source/bmalloc/bmalloc/Scavenger.cpp

    r259652 r261667  
    224224            size_t deferredDecommits = 0;
    225225#endif
    226             LockHolder lock(Heap::mutex());
     226            UniqueLockHolder lock(Heap::mutex());
    227227            for (unsigned i = numHeaps; i--;) {
    228228                if (!isActiveHeapKind(static_cast<HeapKind>(i)))
    … …  
    298298        {
    299299            PrintTime printTime("\npartialScavenge under lock time");
    300             LockHolder lock(Heap::mutex());
     300            UniqueLockHolder lock(Heap::mutex());
    301301            for (unsigned i = numHeaps; i--;) {
    302302                if (!isActiveHeapKind(static_cast<HeapKind>(i)))
    … …  
    356356    size_t result = 0;
    357357    {
    358         LockHolder lock(Heap::mutex());
     358        UniqueLockHolder lock(Heap::mutex());
    359359        for (unsigned i = numHeaps; i--;) {
    360360            if (!isActiveHeapKind(static_cast<HeapKind>(i)))
Note: See TracChangeset for help on using the changeset viewer.