Changeset 263195 in webkit
- Timestamp:
- Jun 17, 2020 6:55:49 PM (4 years ago)
- Location:
- trunk/Source
- Files:
-
- 13 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/Source/JavaScriptCore/ChangeLog
r263193 r263195 1 2020-06-17 Mark Lam <mark.lam@apple.com> 2 3 Replace JSC::FreeList linked list with a Bitmap. 4 https://bugs.webkit.org/show_bug.cgi?id=213071 5 6 Reviewed by Filip Pizlo. 7 8 Implement an alternative to the linked list FreeList. This alternative uses 9 a Bitmap to record which atom in the block is available for allocation. 10 11 The intuition here is that allocation using the Bitmap implementation will do: 12 2 loads - m_currentRowBitmap, m_currentMarkedBlockRowAddress 13 1 store - m_currentRowBitmap 14 15 whereas the linked list implementation will do: 16 3 loads - m_scrambledHead, m_secret, result->scrambledNext 17 1 store - m_scrambledHead 18 19 and result->scrambledNext is from a different region of code and therefore not 20 in the same cache line. 21 22 The downside of the Bitmap implementation is that it uses more instructions. 23 24 This change is currently only enabled for x86_64, which shows about a 0.8% 25 progression on Speedometer 2. 26 27 It appears to be about a 1% regression on ARM64E. Hence, for now, we keep the 28 linked list implementation for ARM64 builds. 29 30 This is how the Bitmap FreeList works: 31 32 1. The Bitmap implementation only replaces the linked list implementation. It 33 does not replace the bump allocator. 34 35 2. The Bitmap allocator keeps a m_bitmap that is initialized in 36 MarkedBlock::Handle::specializedSweep() to have a bit set for each atom 37 location that is available for allocation (i.e. is free). Note that a cell 38 is usually allocated using more than 1 atom. Only the bit corresponding to 39 the first atom (in that cell length range of free atoms) will be set. 40 41 This is consistent with how bits in MarkedBlock::Footer::m_marks and 42 MarkedBlock::Footer::m_newlyAllocated are set i.e. only the bit for the first 43 atom in the cell can be set. 44 45 3. The allocation algorithm thinks of the MarkedBlock as consisting of rows 46 of atoms, where the number of atoms in a row equals the number of bits in 47 a AtomsBitmap::Word. On 64-bit CPUs, this would be 64. 48 49 We will start allocating from the last (highest numbered) row down to the 50 first (row 0). As we allocate, we will only update m_currentRowIndex and 51 m_currentRowBitmap. m_bitmap will not be updated. This is so in order to 52 reduce the number of instructions executed during an allocation. 53 54 When m_currentRowIndex points to N, the AtomsBitmap::Word for row N in 55 m_bitmap will have been copied into m_currentRowBitmap. This is the row 56 that we will be allocating from until the row is exhausted. 57 58 This is how we know whether an atom is available for allocation or not: 59 i. Atoms in any rows above m_currentRowIndex are guaranteed to be 60 allocated already (because we allocate downwards), and hence, are not 61 available. 62 ii. For row m_currentRowIndex, m_currentRowBitmap is the source of truth 63 on which atoms in the row are available for allocation. 64 iii. For rows below m_currentRowIndex, m_bitmap is the source of truth on 65 which atoms are available for allocation. 66 67 When m_currentRowIndex reaches 0, the info in m_bitmap is completely 68 obsoleted, and m_currentRowBitmap holds the availability info for row 0. 69 When both m_currentRowIndex and m_currentRowBitmap are 0, then we have 70 completely exhausted the block and no more atoms are available for 71 allocation. 72 73 4. Allocation happens in 3 paths: fast, middle, slow. 74 75 The fast path checks m_currentRowBitmap. If it's not 0, then we compute the 76 bit number of the lowest set bit in it. That bit number will be used together 77 with m_currentMarkedBlockRowAddress to compute the address of the atom 78 location available for allocation. m_currentRowBitmap will be updated to clear 79 the bit for the atom that has just ben allocated. 80 81 If m_currentRowBitmap is 0, then we'll go to the middle path. 82 83 The middle path checks m_currentRowIndex to see if we have more rows to allocate 84 from. For each m_currentRowIndex, we check its corresponding AtomsBitmap::Word 85 in m_bitmap. If the word is non-zero, we copy it to m_currentRowBitmap and 86 jump to the fast path to do the allocation. The middle path will update 87 m_currentRowIndex to point to the current row we're allocating from. 88 89 If we have decremented m_currentRowIndex down to 0 but still can't find a 90 non-zero AtomsBitmap::Word in m_bitmap, then the block has been exhausted, and 91 we'll go to the slow path. 92 93 The slow path is analogous to the old slow path i.e. we try to refill the 94 LocalAllocator with a new MarkedBlock. 95 96 5. On the layout of fields in FreeList (see changes in FreeList.h), we try to 97 preserve the positions of the bump allocator fields. The only change we made 98 there is n the location of m_cellSize. It is now moved up next to m_remaining, 99 and m_originalSize is moved down. This is because m_originalSize is only 100 accessed in the slow path, and m_cellSize is accessed in the bump allocation 101 path. 102 103 Next, we try to put Bitmap allocation fields where the linked list fields 104 would have been. The one bit of trickiness is that we'll put 105 m_currentMarkedBlockRowAddress in a union with m_payloadEnd. This is because 106 m_payloadEnd is only used in the bump allocation path. If m_remaining is 0, 107 then we can reuse this location for m_currentMarkedBlockRowAddress. 108 109 With this, we would have 4 bytes of padding after m_currentRowIndex. For 110 compactness, we put m_originalSize there in that space. For builds that use 111 the linked list implementation, m_originalSize will be located below after 112 m_cellSize. 113 114 * ftl/FTLLowerDFGToB3.cpp: 115 (JSC::FTL::DFG::LowerDFGToB3::allocateHeapCell): 116 * heap/FreeList.cpp: 117 (JSC::FreeList::clear): 118 (JSC::FreeList::initializeAtomsBitmap): 119 (JSC::FreeList::initializeBump): 120 (JSC::FreeList::contains const): 121 (JSC::FreeList::dump const): 122 * heap/FreeList.h: 123 (JSC::FreeList::bitmapIsEmpty const): 124 (JSC::FreeList::allocationWillFail const): 125 (JSC::FreeList::offsetOfCurrentRowBitmap): 126 (JSC::FreeList::offsetOfBitmapRows): 127 (JSC::FreeList::offsetOfCurrentRowIndex): 128 (JSC::FreeList::offsetOfCurrentMarkedBlockRowAddress): 129 (JSC::FreeList::offsetOfRemaining): 130 (JSC::FreeList::atomsBitmap): 131 (JSC::FreeList::bitmapRows const): 132 (JSC::FreeList::offsetOfOriginalSize): Deleted. 133 * heap/FreeListInlines.h: 134 (JSC::FreeList::allocate): 135 (JSC::FreeList::forEach const): 136 * heap/LocalAllocator.cpp: 137 (JSC::LocalAllocator::isFreeListedCell const): 138 * heap/MarkedBlock.h: 139 (JSC::MarkedBlock::Handle::atomAt const): 140 * heap/MarkedBlockInlines.h: 141 (JSC::MarkedBlock::Handle::specializedSweep): 142 * jit/AssemblyHelpers.cpp: 143 (JSC::AssemblyHelpers::emitAllocateWithNonNullAllocator): 144 * jit/AssemblyHelpers.h: 145 (JSC::AssemblyHelpers::emitAllocateWithNonNullAllocator): 146 1 147 2020-06-17 Mark Lam <mark.lam@apple.com> 2 148 -
trunk/Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp
r263165 r263195 15080 15080 else 15081 15081 patchpoint->appendSomeRegisterWithClobber(allocator); 15082 patchpoint->numGPScratchRegisters++; 15082 #if ENABLE(BITMAP_FREELIST) 15083 constexpr unsigned scratchRegistersNeeded = 3; 15084 constexpr unsigned allocatorScratch = 3; 15085 #else 15086 constexpr unsigned scratchRegistersNeeded = 1; 15087 constexpr unsigned allocatorScratch = 1; 15088 #endif 15089 patchpoint->numGPScratchRegisters += scratchRegistersNeeded; 15083 15090 patchpoint->resultConstraints = { ValueRep::SomeEarlyRegister }; 15084 15091 … … 15093 15100 GPRReg allocatorGPR; 15094 15101 if (actualAllocator.isConstant()) 15095 allocatorGPR = params.gpScratch( 1);15102 allocatorGPR = params.gpScratch(allocatorScratch); 15096 15103 else 15097 15104 allocatorGPR = params[1].gpr(); … … 15105 15112 jit.emitAllocateWithNonNullAllocator( 15106 15113 params[0].gpr(), actualAllocator, allocatorGPR, params.gpScratch(0), 15107 jumpToSlowPath); 15114 jumpToSlowPath 15115 #if ENABLE(BITMAP_FREELIST) 15116 , params.gpScratch(1), params.gpScratch(2) 15117 #endif 15118 ); 15108 15119 15109 15120 CCallHelpers::Jump jumpToSuccess; -
trunk/Source/JavaScriptCore/heap/FreeList.cpp
r261755 r263195 1 1 /* 2 * Copyright (C) 2016-20 17Apple Inc. All rights reserved.2 * Copyright (C) 2016-2020 Apple Inc. All rights reserved. 3 3 * 4 4 * Redistribution and use in source and binary forms, with or without … … 40 40 void FreeList::clear() 41 41 { 42 #if ENABLE(BITMAP_FREELIST) 43 m_currentRowBitmap = 0; 44 m_currentRowIndex = 0; 45 #else 42 46 m_scrambledHead = 0; 43 47 m_secret = 0; 48 #endif 44 49 m_payloadEnd = nullptr; 45 50 m_remaining = 0; 46 51 m_originalSize = 0; 47 52 } 53 54 #if ENABLE(BITMAP_FREELIST) 55 56 void FreeList::initializeAtomsBitmap(MarkedBlock::Handle* block, AtomsBitmap& freeAtoms, unsigned bytes) 57 { 58 #if ASSERT_ENABLED 59 m_markedBlock = block; 60 #endif 61 ASSERT_UNUSED(freeAtoms, &freeAtoms == &m_bitmap); 62 // m_bitmap has already been filled in by MarkedBlock::Handle::specializedSweep(). 63 64 m_currentRowBitmap = 0; 65 size_t rowIndex = AtomsBitmap::numberOfWords; 66 while (rowIndex--) { 67 auto rowBitmap = m_bitmap.wordAt(rowIndex); 68 if (rowBitmap) { 69 m_currentRowBitmap = rowBitmap; 70 break; 71 } 72 } 73 ASSERT(m_currentRowBitmap || m_bitmap.isEmpty()); 74 m_currentRowIndex = m_currentRowBitmap ? rowIndex : 0; 75 76 size_t firstAtomInRow = m_currentRowIndex * atomsPerRow; 77 m_currentMarkedBlockRowAddress = bitwise_cast<Atom*>(block->atomAt(firstAtomInRow)); 78 m_originalSize = bytes; 79 } 80 81 #else 82 // Linked List implementation. 48 83 49 84 void FreeList::initializeList(FreeCell* head, uintptr_t secret, unsigned bytes) … … 57 92 } 58 93 94 #endif // ENABLE(BITMAP_FREELIST) 95 59 96 void FreeList::initializeBump(char* payloadEnd, unsigned remaining) 60 97 { 98 #if ENABLE(BITMAP_FREELIST) 99 m_currentRowBitmap = 0; 100 m_currentRowIndex = 0; 101 #else 61 102 m_scrambledHead = 0; 62 103 m_secret = 0; 104 #endif 63 105 m_payloadEnd = payloadEnd; 64 106 m_remaining = remaining; … … 66 108 } 67 109 68 bool FreeList::contains(HeapCell* target ) const110 bool FreeList::contains(HeapCell* target, MarkedBlock::Handle* currentBlock) const 69 111 { 70 112 if (m_remaining) { … … 74 116 } 75 117 118 #if ENABLE(BITMAP_FREELIST) 119 if (bitmapIsEmpty()) 120 return false; 121 122 // currentBlock may be null if the allocator has been reset (and therefore, 123 // the FreeList cleared. Hence, we should only check this assertion after 124 // we check if the FreeList bitmap is empty above. 125 ASSERT(m_markedBlock == currentBlock); 126 if (!currentBlock->contains(target)) 127 return false; 128 129 unsigned atomNumber = currentBlock->block().atomNumber(target); 130 unsigned rowIndex = atomNumber / atomsPerRow; 131 if (rowIndex > m_currentRowIndex) 132 return false; 133 if (rowIndex == m_currentRowIndex) { 134 constexpr AtomsBitmap::Word one = 1; 135 unsigned firstAtomInRow = rowIndex * atomsPerRow; 136 unsigned atomIndexInRow = atomNumber - firstAtomInRow; 137 return m_currentRowBitmap & (one << atomIndexInRow); 138 } 139 return m_bitmap.get(atomNumber); 140 141 #else 142 UNUSED_PARAM(currentBlock); 76 143 FreeCell* candidate = head(); 77 144 while (candidate) { … … 80 147 candidate = candidate->next(m_secret); 81 148 } 82 83 149 return false; 150 #endif 84 151 } 85 152 86 153 void FreeList::dump(PrintStream& out) const 87 154 { 155 #if ENABLE(BITMAP_FREELIST) 156 if (m_remaining) 157 out.print("{payloadEnd = ", RawPointer(m_payloadEnd), ", remaining = ", m_remaining, ", originalSize = ", m_originalSize, "}"); 158 else 159 out.print("{currentRowBitmap = ", m_currentRowBitmap, ", currentRowIndex = ", m_currentRowIndex, ", originalSize = ", m_originalSize, "}"); 160 #else 88 161 out.print("{head = ", RawPointer(head()), ", secret = ", m_secret, ", payloadEnd = ", RawPointer(m_payloadEnd), ", remaining = ", m_remaining, ", originalSize = ", m_originalSize, "}"); 162 #endif 89 163 } 90 164 -
trunk/Source/JavaScriptCore/heap/FreeList.h
r253443 r263195 1 1 /* 2 * Copyright (C) 2016-20 19Apple Inc. All rights reserved.2 * Copyright (C) 2016-2020 Apple Inc. All rights reserved. 3 3 * 4 4 * Redistribution and use in source and binary forms, with or without … … 26 26 #pragma once 27 27 28 #include "MarkedBlock.h" 28 29 #include <wtf/Noncopyable.h> 29 30 #include <wtf/PrintStream.h> 31 #include <wtf/StdIntExtras.h> 30 32 31 33 namespace JSC { … … 33 35 class HeapCell; 34 36 37 #if CPU(X86_64) 38 #define ENABLE_BITMAP_FREELIST 1 39 #else 40 #define ENABLE_BITMAP_FREELIST 0 41 #endif 42 43 #if !ENABLE(BITMAP_FREELIST) 35 44 struct FreeCell { 36 45 static uintptr_t scramble(FreeCell* cell, uintptr_t secret) … … 59 68 uintptr_t scrambledNext; 60 69 }; 70 #endif 61 71 62 72 class FreeList { … … 67 77 void clear(); 68 78 69 JS_EXPORT_PRIVATE void initializeList(FreeCell* head, uintptr_t secret, unsigned bytes);70 79 JS_EXPORT_PRIVATE void initializeBump(char* payloadEnd, unsigned remaining); 71 80 72 bool allocationWillFail() const { return !head() && !m_remaining; }73 81 bool allocationWillSucceed() const { return !allocationWillFail(); } 74 82 … … 76 84 HeapCell* allocate(const Func& slowPath); 77 85 78 bool contains(HeapCell* ) const;86 bool contains(HeapCell*, MarkedBlock::Handle* currentBlock) const; 79 87 80 88 template<typename Func> … … 83 91 unsigned originalSize() const { return m_originalSize; } 84 92 93 #if ENABLE(BITMAP_FREELIST) 94 using Atom = MarkedBlock::Atom; 95 using AtomsBitmap = MarkedBlock::AtomsBitmap; 96 97 static constexpr size_t atomsPerRow = AtomsBitmap::bitsInWord; 98 static constexpr size_t atomsRowBytes = atomsPerRow * sizeof(Atom); 99 static constexpr unsigned atomSizeShift = WTF::log2Constexpr(sizeof(Atom)); 100 static_assert((static_cast<size_t>(1) << atomSizeShift) == sizeof(Atom)); 101 102 JS_EXPORT_PRIVATE void initializeAtomsBitmap(MarkedBlock::Handle*, AtomsBitmap& freeAtoms, unsigned bytes); 103 104 bool bitmapIsEmpty() const 105 { 106 // Remember, we don't actually clear the bits in m_bitmap as we allocate 107 // the atoms. Instead, m_currentRowBitmap and m_currentRowIndex tells us 108 // if there atoms still available for allocation. See comment blob below 109 // at the declaration of m_currentRowIndex for more details. 110 return !m_currentRowBitmap && !m_currentRowIndex; 111 } 112 bool allocationWillFail() const { return bitmapIsEmpty() && !m_remaining; } 113 114 static ptrdiff_t offsetOfCurrentRowBitmap() { return OBJECT_OFFSETOF(FreeList, m_currentRowBitmap); } 115 116 // We're deliberately returning the address of 1 word before m_bitmap so that 117 // we can schedule instructions better i.e. to do a load before decrementing the 118 // row index. 119 static ptrdiff_t offsetOfBitmapRows() { return OBJECT_OFFSETOF(FreeList, m_bitmap) - sizeof(AtomsBitmap::Word); } 120 121 static ptrdiff_t offsetOfCurrentRowIndex() { return OBJECT_OFFSETOF(FreeList, m_currentRowIndex); } 122 static ptrdiff_t offsetOfCurrentMarkedBlockRowAddress() { return OBJECT_OFFSETOF(FreeList, m_currentMarkedBlockRowAddress); } 123 #else 124 JS_EXPORT_PRIVATE void initializeList(FreeCell* head, uintptr_t secret, unsigned bytes); 125 126 bool allocationWillFail() const { return !head() && !m_remaining; } 127 85 128 static ptrdiff_t offsetOfScrambledHead() { return OBJECT_OFFSETOF(FreeList, m_scrambledHead); } 86 129 static ptrdiff_t offsetOfSecret() { return OBJECT_OFFSETOF(FreeList, m_secret); } 130 #endif 131 87 132 static ptrdiff_t offsetOfPayloadEnd() { return OBJECT_OFFSETOF(FreeList, m_payloadEnd); } 88 133 static ptrdiff_t offsetOfRemaining() { return OBJECT_OFFSETOF(FreeList, m_remaining); } 89 static ptrdiff_t offsetOfOriginalSize() { return OBJECT_OFFSETOF(FreeList, m_originalSize); }90 134 static ptrdiff_t offsetOfCellSize() { return OBJECT_OFFSETOF(FreeList, m_cellSize); } 91 135 … … 95 139 96 140 private: 141 142 #if ENABLE(BITMAP_FREELIST) 143 AtomsBitmap& atomsBitmap() { return m_bitmap; } 144 AtomsBitmap::Word* bitmapRows() const 145 { 146 // See comment about offsetOfBitmapRows(). 147 return bitwise_cast<AtomsBitmap::Word*>(&m_bitmap) - 1; 148 } 149 150 // This allocation algorithm thinks of the MarkedBlock as consisting of rows 151 // of atoms, where the number of atoms in a row equals the number of bits in 152 // a AtomsBitmap::Word. On 64-bit CPUs, this would be 64. 153 // 154 // We will start allocating from the last (highest numbered) row down to the 155 // first (row 0). As we allocate, we will only update m_currentRowIndex and 156 // m_currentRowBitmap. m_bitmap will not be updated. This is so in oder to 157 // reduce the number of instructions executed during an allocation. 158 // 159 // When m_currentRowIndex points to N, the AtomsBitmap::Word for row N in 160 // m_bitmap will have been copied into m_currentRowBitmap. This is the row 161 // that we will be allocating from until the row is exhausted. 162 // 163 // This is how we know whether an atom is available for allocation or not: 164 // 1. Atoms in any rows above m_currentRowIndex are guaranteed to be 165 // allocated already (because we allocate downwards), and hence, are not 166 // available. 167 // 2. For row m_currentRowIndex, m_currentRowBitmap is the source of truth 168 // on which atoms in the row are available for allocation. 169 // 3. For rows below m_currentRowIndex, m_bitmap is the source of truth on 170 // which atoms are available for allocation. 171 // 172 // When m_currentRowIndex reaches 0, the info in m_bitmap is completely 173 // obsoleted, and m_currentRowBitmap holds the availability info for row 0. 174 // When both m_currentRowIndex and m_currentRowBitmap are 0, then we have 175 // completely exhausted the block and no more atoms are available for 176 // allocation. 177 178 AtomsBitmap::Word m_currentRowBitmap { 0 }; 179 unsigned m_currentRowIndex { 0 }; 180 unsigned m_originalSize { 0 }; 181 182 #else 97 183 FreeCell* head() const { return FreeCell::descramble(m_scrambledHead, m_secret); } 98 184 99 185 uintptr_t m_scrambledHead { 0 }; 100 186 uintptr_t m_secret { 0 }; 101 char* m_payloadEnd { nullptr }; 187 #endif 188 189 union { 190 char* m_payloadEnd { nullptr }; 191 #if ENABLE(BITMAP_FREELIST) 192 Atom* m_currentMarkedBlockRowAddress; 193 #endif 194 }; 102 195 unsigned m_remaining { 0 }; 196 unsigned m_cellSize { 0 }; 197 198 #if ENABLE(BITMAP_FREELIST) 199 AtomsBitmap m_bitmap; 200 #else 103 201 unsigned m_originalSize { 0 }; 104 unsigned m_cellSize { 0 }; 202 #endif 203 204 #if ASSERT_ENABLED 205 MarkedBlock::Handle* m_markedBlock { nullptr }; 206 #endif 207 208 friend class MarkedBlock; 105 209 }; 106 210 -
trunk/Source/JavaScriptCore/heap/FreeListInlines.h
r232132 r263195 1 1 /* 2 * Copyright (C) 2017 Apple Inc. All rights reserved.2 * Copyright (C) 2017-2020 Apple Inc. All rights reserved. 3 3 * 4 4 * Redistribution and use in source and binary forms, with or without … … 27 27 28 28 #include "FreeList.h" 29 #include "MarkedBlock.h"29 #include <wtf/MathExtras.h> 30 30 31 31 namespace JSC { … … 41 41 return bitwise_cast<HeapCell*>(m_payloadEnd - remaining - cellSize); 42 42 } 43 43 44 #if ENABLE(BITMAP_FREELIST) 45 AtomsBitmap::Word rowBitmap = m_currentRowBitmap; 46 do { 47 if (rowBitmap) { 48 constexpr AtomsBitmap::Word one = 1; 49 unsigned atomIndexInRow = ctz(rowBitmap); 50 auto* cell = bitwise_cast<HeapCell*>(&m_currentMarkedBlockRowAddress[atomIndexInRow]); 51 rowBitmap &= ~(one << atomIndexInRow); 52 m_currentRowBitmap = rowBitmap; 53 return cell; 54 } 55 56 unsigned rowIndex = m_currentRowIndex; 57 auto* rowAddress = m_currentMarkedBlockRowAddress; 58 while (rowIndex) { 59 // We load before decrementing rowIndex because bitmapRows() points 60 // to 1 word before m_bitmap. See comments about offsetOfBitmapRows() 61 // for why we do this. 62 rowBitmap = bitmapRows()[rowIndex--]; 63 rowAddress -= atomsPerRow; 64 if (rowBitmap) 65 break; 66 } 67 m_currentMarkedBlockRowAddress = rowAddress; 68 m_currentRowIndex = rowIndex; 69 } while (rowBitmap); 70 71 m_currentRowBitmap = rowBitmap; 72 ASSERT(bitmapIsEmpty()); 73 return slowPath(); 74 75 #else // !ENABLE(BITMAP_FREELIST) 44 76 FreeCell* result = head(); 45 77 if (UNLIKELY(!result)) … … 48 80 m_scrambledHead = result->scrambledNext; 49 81 return bitwise_cast<HeapCell*>(result); 82 #endif // !ENABLE(BITMAP_FREELIST) 50 83 } 51 84 … … 57 90 func(bitwise_cast<HeapCell*>(m_payloadEnd - remaining)); 58 91 } else { 92 #if ENABLE(BITMAP_FREELIST) 93 if (bitmapIsEmpty()) 94 return; 95 96 AtomsBitmap::Word rowBitmap = m_currentRowBitmap; 97 unsigned rowIndex = m_currentRowIndex; 98 Atom* currentMarkedBlockRowAddress = m_currentMarkedBlockRowAddress; 99 do { 100 while (rowBitmap) { 101 constexpr AtomsBitmap::Word one = 1; 102 unsigned atomIndexInRow = ctz(rowBitmap); 103 auto* cell = bitwise_cast<HeapCell*>(¤tMarkedBlockRowAddress[atomIndexInRow]); 104 rowBitmap &= ~(one << atomIndexInRow); 105 func(cell); 106 } 107 108 while (rowIndex) { 109 // We load before decrementing rowIndex because bitmapRows() points 110 // to 1 word before m_bitmap. See comments about offsetOfBitmapRows() 111 // for why we do this. 112 rowBitmap = bitmapRows()[rowIndex--]; 113 currentMarkedBlockRowAddress -= atomsPerRow; 114 if (rowBitmap) 115 break; 116 } 117 } while (rowBitmap); 118 #else 59 119 for (FreeCell* cell = head(); cell;) { 60 120 // We can use this to overwrite free objects before destroying the free list. So, we need … … 64 124 cell = next; 65 125 } 126 #endif 66 127 } 67 128 } 68 129 69 130 } // namespace JSC 70 -
trunk/Source/JavaScriptCore/heap/LocalAllocator.cpp
r261755 r263195 1 1 /* 2 * Copyright (C) 2018-20 19Apple Inc. All rights reserved.2 * Copyright (C) 2018-2020 Apple Inc. All rights reserved. 3 3 * 4 4 * Redistribution and use in source and binary forms, with or without … … 273 273 // objects to be in the dead-but-not-destructed state. 274 274 // FIXME: Get rid of this abomination. https://bugs.webkit.org/show_bug.cgi?id=181655 275 return m_freeList.contains(bitwise_cast<HeapCell*>(target) );275 return m_freeList.contains(bitwise_cast<HeapCell*>(target), m_currentBlock); 276 276 } 277 277 -
trunk/Source/JavaScriptCore/heap/MarkedBlock.h
r258857 r263195 2 2 * Copyright (C) 1999-2000 Harri Porten (porten@kde.org) 3 3 * Copyright (C) 2001 Peter Kelly (pmk@post.com) 4 * Copyright (C) 2003-20 19Apple Inc. All rights reserved.4 * Copyright (C) 2003-2020 Apple Inc. All rights reserved. 5 5 * 6 6 * This library is free software; you can redistribute it and/or … … 85 85 static_assert(!(MarkedBlock::blockSize & (MarkedBlock::blockSize - 1)), "MarkedBlock::blockSize must be a power of two."); 86 86 87 using AtomsBitmap = Bitmap<atomsPerBlock>; 88 87 89 struct VoidFunctor { 88 90 typedef void ReturnType; … … 204 206 void* start() const { return &m_block->atoms()[0]; } 205 207 void* end() const { return &m_block->atoms()[m_endAtom]; } 208 void* atomAt(size_t i) const { return &m_block->atoms()[i]; } 206 209 bool contains(void* p) const { return start() <= p && p < end(); } 207 210 … … 295 298 HeapVersion m_newlyAllocatedVersion; 296 299 297 Bitmap<atomsPerBlock>m_marks;298 Bitmap<atomsPerBlock>m_newlyAllocated;300 AtomsBitmap m_marks; 301 AtomsBitmap m_newlyAllocated; 299 302 }; 300 303 … … 337 340 void setNewlyAllocated(const void*); 338 341 void clearNewlyAllocated(const void*); 339 const Bitmap<atomsPerBlock>& newlyAllocated() const;342 const AtomsBitmap& newlyAllocated() const; 340 343 341 344 HeapVersion newlyAllocatedVersion() const { return footer().m_newlyAllocatedVersion; } … … 375 378 HeapVersion markingVersion() const { return footer().m_markingVersion; } 376 379 377 const Bitmap<atomsPerBlock>& marks() const;380 const AtomsBitmap& marks() const; 378 381 379 382 CountingLock& lock() { return footer().m_lock; } … … 400 403 inline bool marksConveyLivenessDuringMarking(HeapVersion markingVersion); 401 404 inline bool marksConveyLivenessDuringMarking(HeapVersion myMarkingVersion, HeapVersion markingVersion); 405 406 friend class FreeList; 402 407 }; 403 408 -
trunk/Source/JavaScriptCore/heap/MarkedBlockInlines.h
r261464 r263195 304 304 } 305 305 306 #if ENABLE(BITMAP_FREELIST) 307 AtomsBitmap localFreeAtoms; 308 AtomsBitmap& freeAtoms = freeList ? freeList->atomsBitmap() : localFreeAtoms; 309 size_t count = 0; 310 311 auto handleDeadCell = [&] (size_t i) { 312 HeapCell* cell = reinterpret_cast_ptr<HeapCell*>(atomAt(i)); 313 314 if (destructionMode != BlockHasNoDestructors) 315 destroy(cell); 316 317 if (sweepMode == SweepToFreeList) { 318 if (scribbleMode == Scribble) 319 scribble(cell, cellSize); 320 ++count; 321 } 322 }; 323 324 bool isEmpty = true; 325 326 AtomsBitmap cellLocations; 327 cellLocations.setEachNthBit(m_atomsPerCell, 0, m_endAtom); 328 329 if (emptyMode == NotEmpty) { 330 if (marksMode == MarksNotStale) { 331 freeAtoms = footer.m_marks; 332 if (newlyAllocatedMode == HasNewlyAllocated) 333 freeAtoms |= footer.m_newlyAllocated; 334 } else if (newlyAllocatedMode == HasNewlyAllocated) 335 freeAtoms = footer.m_newlyAllocated; 336 // At this point, a set bit in freeAtoms represents live cells. 337 isEmpty = freeAtoms.isEmpty(); 338 339 // Invert the bits at each cell location so that the ones for live cells 340 // are cleared, and the ones for dead cells are set. 341 freeAtoms ^= cellLocations; 342 } else 343 freeAtoms = cellLocations; // all cells are free. 344 345 // We only want to discard the newlyAllocated bits if we're creating a FreeList, 346 // otherwise we would lose information on what's currently alive. 347 if (sweepMode == SweepToFreeList && newlyAllocatedMode == HasNewlyAllocated) 348 footer.m_newlyAllocatedVersion = MarkedSpace::nullVersion; 349 350 if (space()->isMarking()) 351 footer.m_lock.unlock(); 352 353 if (destructionMode != BlockHasNoDestructors) 354 freeAtoms.forEachSetBit(handleDeadCell); 355 356 if (sweepMode == SweepToFreeList) { 357 freeList->initializeAtomsBitmap(this, freeAtoms, count * cellSize); 358 setIsFreeListed(); 359 } else if (isEmpty) 360 m_directory->setIsEmpty(NoLockingNecessary, this, true); 361 if (false) 362 dataLog("Slowly swept block ", RawPointer(&block), " with cell size ", cellSize, " and attributes ", m_attributes, ": ", pointerDump(freeList), "\n"); 363 364 #else // not ENABLE(BITMAP_FREELIST) 365 306 366 // This produces a free list that is ordered in reverse through the block. 307 367 // This is fine, since the allocation code makes no assumptions about the … … 362 422 if (false) 363 423 dataLog("Slowly swept block ", RawPointer(&block), " with cell size ", cellSize, " and attributes ", m_attributes, ": ", pointerDump(freeList), "\n"); 424 #endif // ENABLE(BITMAP_FREELIST) 364 425 } 365 426 -
trunk/Source/JavaScriptCore/jit/AssemblyHelpers.cpp
r263049 r263195 504 504 #endif 505 505 506 void AssemblyHelpers::emitAllocateWithNonNullAllocator(GPRReg resultGPR, const JITAllocator& allocator, GPRReg allocatorGPR, GPRReg scratchGPR, JumpList& slowPath )506 void AssemblyHelpers::emitAllocateWithNonNullAllocator(GPRReg resultGPR, const JITAllocator& allocator, GPRReg allocatorGPR, GPRReg scratchGPR, JumpList& slowPath, Optional<GPRReg> optionalScratchGPR2, Optional<GPRReg> optionalScratchGPR3) 507 507 { 508 508 if (Options::forceGCSlowPaths()) { … … 517 517 518 518 Jump popPath; 519 Jump done;519 JumpList done; 520 520 521 521 if (allocator.isConstant()) … … 535 535 addPtr(payloadEndAddr, resultGPR); 536 536 537 done = jump();537 done.append(jump()); 538 538 539 #if ENABLE(BITMAP_FREELIST) 540 ASSERT(resultGPR != scratchGPR); 541 542 auto rowIndexGPR = resultGPR; 543 auto rowBitmapGPR = scratchGPR; 544 545 GPRReg scratchGPR2 = optionalScratchGPR2 ? optionalScratchGPR2.value() : scratchRegister(); 546 ASSERT(scratchGPR2 != resultGPR); 547 ASSERT(scratchGPR2 != scratchGPR); 548 549 auto rowAddressGPR = scratchGPR2; 550 auto clearBit64ScratchGPR = scratchGPR2; 551 552 bool canPreloadRowAddressGPR = false; 553 if (optionalScratchGPR3) { 554 clearBit64ScratchGPR = optionalScratchGPR3.value(); 555 canPreloadRowAddressGPR = true; 556 } else if (isX86_64()) { 557 // x86_64's clearBit64() does actually need to use clearBit64ScratchGPR. 558 // So, we can preload the row address into it. 559 clearBit64ScratchGPR = InvalidGPRReg; 560 canPreloadRowAddressGPR = true; 561 #if CPU(ARM64) 562 } else if (isARM64()) { 563 // ARM64's fast path does actually need to use the memoryTempRegister. 564 // So, we can use that for the clearBit64ScratchGPR and allow the 565 // row address to be preloaded in scratchGPR2. 566 clearBit64ScratchGPR = getCachedMemoryTempRegisterIDAndInvalidate(); 567 canPreloadRowAddressGPR = true; 568 #endif 569 } 570 ASSERT(clearBit64ScratchGPR != resultGPR); 571 ASSERT(clearBit64ScratchGPR != scratchGPR); 572 if (canPreloadRowAddressGPR) 573 ASSERT(clearBit64ScratchGPR != scratchGPR2); 574 575 // The code below for rowBitmapGPR relies on this. 576 static_assert(sizeof(FreeList::AtomsBitmap::Word) == sizeof(uint64_t)); 577 578 // Check for middle path: have another row to visit? 579 Label checkForMoreRows = label(); 580 581 load32(Address(allocatorGPR, LocalAllocator::offsetOfFreeList() + FreeList::offsetOfCurrentRowIndex()), rowIndexGPR); 582 583 if (!canPreloadRowAddressGPR) 584 loadPtr(Address(allocatorGPR, LocalAllocator::offsetOfFreeList() + FreeList::offsetOfCurrentMarkedBlockRowAddress()), rowAddressGPR); 585 586 slowPath.append(branchTestPtr(Zero, rowIndexGPR)); 587 588 // Middle path: there is another row left to visit. 589 Jump foundNonEmptyRow; 590 Label checkNextRow = label(); 591 { 592 // Load the next row bitmap and point m_currentMarkedBlockRowAddress to the next row. 593 594 // Note: offsetOfBitmapRows() points to 1 word before m_bitmap. We do this 595 // deliberately because it allows us to schedule instructions better and 596 // do this load before the decrement below. 597 load64(BaseIndex(allocatorGPR, rowIndexGPR, TimesEight, LocalAllocator::offsetOfFreeList() + FreeList::offsetOfBitmapRows()), rowBitmapGPR); 598 599 sub64(TrustedImm32(1), rowIndexGPR); 600 subPtr(TrustedImm32(FreeList::atomsRowBytes), rowAddressGPR); 601 602 foundNonEmptyRow = branchTest64(NonZero, rowBitmapGPR); 603 branchTestPtr(NonZero, rowIndexGPR).linkTo(checkNextRow, this); 604 } 605 606 // Slow path: no more rows. 607 // Both rowIndexGPR and rowBitmapGPR should be null here. 608 store32(rowIndexGPR, Address(allocatorGPR, LocalAllocator::offsetOfFreeList() + FreeList::offsetOfCurrentRowIndex())); 609 store64(rowBitmapGPR, Address(allocatorGPR, LocalAllocator::offsetOfFreeList() + FreeList::offsetOfCurrentRowBitmap())); 610 slowPath.append(jump()); 611 612 // Transition from middle path back to fast path to allocate. 613 foundNonEmptyRow.link(this); 614 storePtr(rowAddressGPR, Address(allocatorGPR, LocalAllocator::offsetOfFreeList() + FreeList::offsetOfCurrentMarkedBlockRowAddress())); 615 store32(rowIndexGPR, Address(allocatorGPR, LocalAllocator::offsetOfFreeList() + FreeList::offsetOfCurrentRowIndex())); 616 617 Jump allocateFromCurrentRow = jump(); 618 539 619 popPath.link(this); 540 620 621 // Check for fast path: have available bit in m_currentRowBitmap? 622 load64(Address(allocatorGPR, LocalAllocator::offsetOfFreeList() + FreeList::offsetOfCurrentRowBitmap()), rowBitmapGPR); 623 624 if (canPreloadRowAddressGPR) { 625 // Preload the row address needed on the fast and middle path. 626 loadPtr(Address(allocatorGPR, LocalAllocator::offsetOfFreeList() + FreeList::offsetOfCurrentMarkedBlockRowAddress()), rowAddressGPR); 627 } 628 629 branchTest64(Zero, rowBitmapGPR).linkTo(checkForMoreRows, this); 630 631 // Fast path: we have a bit to use. 632 allocateFromCurrentRow.link(this); 633 { 634 // Remove this bit from m_currentRowBitmap. 635 auto atomIndexInRowGPR = resultGPR; 636 countTrailingZeros64WithoutNullCheck(rowBitmapGPR, atomIndexInRowGPR); 637 clearBit64(atomIndexInRowGPR, rowBitmapGPR, clearBit64ScratchGPR); 638 639 if (!canPreloadRowAddressGPR) 640 loadPtr(Address(allocatorGPR, LocalAllocator::offsetOfFreeList() + FreeList::offsetOfCurrentMarkedBlockRowAddress()), rowAddressGPR); 641 642 store64(rowBitmapGPR, Address(allocatorGPR, LocalAllocator::offsetOfFreeList() + FreeList::offsetOfCurrentRowBitmap())); 643 644 // Compute atom address of this bit. 645 ASSERT(resultGPR == atomIndexInRowGPR); 646 shiftAndAdd(rowAddressGPR, resultGPR, FreeList::atomSizeShift, resultGPR); 647 } 648 649 #else 650 UNUSED_PARAM(optionalScratchGPR2); 651 UNUSED_PARAM(optionalScratchGPR3); 652 653 popPath.link(this); 654 541 655 loadPtr(Address(allocatorGPR, LocalAllocator::offsetOfFreeList() + FreeList::offsetOfScrambledHead()), resultGPR); 542 656 xorPtr(Address(allocatorGPR, LocalAllocator::offsetOfFreeList() + FreeList::offsetOfSecret()), resultGPR); … … 547 661 loadPtr(Address(resultGPR, FreeCell::offsetOfScrambledNext()), scratchGPR); 548 662 storePtr(scratchGPR, Address(allocatorGPR, LocalAllocator::offsetOfFreeList() + FreeList::offsetOfScrambledHead())); 549 663 #endif 664 550 665 done.link(this); 551 666 } -
trunk/Source/JavaScriptCore/jit/AssemblyHelpers.h
r263151 r263195 45 45 #include "TypeofType.h" 46 46 #include "VM.h" 47 #include <wtf/Optional.h> 47 48 48 49 namespace JSC { … … 1952 1953 // value of allocatorGPR is. Additionally, if the allocator is not null, then there is no need 1953 1954 // to populate allocatorGPR - this code will ignore the contents of allocatorGPR. 1954 void emitAllocateWithNonNullAllocator(GPRReg resultGPR, const JITAllocator& allocator, GPRReg allocatorGPR, GPRReg scratchGPR, JumpList& slowPath);1955 1955 void emitAllocateWithNonNullAllocator(GPRReg resultGPR, const JITAllocator&, GPRReg allocatorGPR, GPRReg scratchGPR, JumpList& slowPath, Optional<GPRReg> scratchGPR2 = { }, Optional<GPRReg> scratchGPR3 = { }); 1956 1956 1957 void emitAllocate(GPRReg resultGPR, const JITAllocator& allocator, GPRReg allocatorGPR, GPRReg scratchGPR, JumpList& slowPath); 1957 1958 -
trunk/Source/WTF/ChangeLog
r263178 r263195 1 2020-06-17 Mark Lam <mark.lam@apple.com> 2 3 Replace JSC::FreeList linked list with a Bitmap. 4 https://bugs.webkit.org/show_bug.cgi?id=213071 5 6 Reviewed by Filip Pizlo. 7 8 1. Use countOfBits<> template to compute the number of bits. 9 2. Introduce log2() and log2Constexpr() utility functions. 10 3. Make Bitmap<>::forEachSetBit() a little bit more efficient: we don't need to 11 keep iterating if the bitmap word is already empty of bits. 12 13 * wtf/Bitmap.h: 14 (WTF::WordType>::forEachSetBit const): 15 * wtf/MathExtras.h: 16 (WTF::clzConstexpr): 17 (WTF::clz): 18 (WTF::ctzConstexpr): 19 (WTF::ctz): 20 (WTF::getMSBSet): 21 (WTF::getMSBSetConstexpr): 22 (WTF::log2): 23 (WTF::log2Constexpr): 24 1 25 2020-06-17 David Kilzer <ddkilzer@apple.com> 2 26 -
trunk/Source/WTF/wtf/Bitmap.h
r262211 r263195 131 131 unsigned hash() const; 132 132 133 // Low level interface. 134 using Word = WordType; 135 static constexpr unsigned bitsInWord = countOfBits<WordType>; 136 static constexpr unsigned numberOfWords = (bitmapSize + bitsInWord - 1) / bitsInWord; 137 WordType wordAt(size_t wordIndex) const { return bits[wordIndex]; } 138 133 139 private: 134 static constexpr unsigned wordSize = sizeof(WordType) * 8;135 static constexpr unsigned words = (bitmapSize + wordSize - 1) / wordSize;140 static constexpr unsigned wordSize = bitsInWord; 141 static constexpr unsigned words = numberOfWords; 136 142 137 143 // the literal '1' is of type signed int. We want to use an unsigned … … 378 384 for (size_t i = 0; i < words; ++i) { 379 385 WordType word = bits[i]; 380 if (!word)381 continue;382 386 size_t base = i * wordSize; 383 for (size_t j = 0; j < wordSize; ++j) { 387 size_t j = 0; 388 for (; word; ++j) { 384 389 if (word & 1) 385 390 func(base + j); 386 391 word >>= 1; 387 392 } 393 ASSERT(j <= wordSize); 388 394 } 389 395 } -
trunk/Source/WTF/wtf/MathExtras.h
r259537 r263195 594 594 constexpr unsigned clzConstexpr(T value) 595 595 { 596 constexpr unsigned bitSize = sizeof(T) * CHAR_BIT;596 constexpr unsigned bitSize = countOfBits<T>; 597 597 598 598 using UT = typename std::make_unsigned<T>::type; … … 611 611 inline unsigned clz(T value) 612 612 { 613 constexpr unsigned bitSize = sizeof(T) * CHAR_BIT;613 constexpr unsigned bitSize = countOfBits<T>; 614 614 615 615 using UT = typename std::make_unsigned<T>::type; … … 617 617 618 618 #if COMPILER(GCC_COMPATIBLE) 619 constexpr unsigned bitSize64 = sizeof(uint64_t) * CHAR_BIT;619 constexpr unsigned bitSize64 = countOfBits<uint64_t>; 620 620 if (uValue) 621 621 return __builtin_clzll(uValue) - (bitSize64 - bitSize); … … 639 639 constexpr unsigned ctzConstexpr(T value) 640 640 { 641 constexpr unsigned bitSize = sizeof(T) * CHAR_BIT;641 constexpr unsigned bitSize = countOfBits<T>; 642 642 643 643 using UT = typename std::make_unsigned<T>::type; … … 658 658 inline unsigned ctz(T value) 659 659 { 660 constexpr unsigned bitSize = sizeof(T) * CHAR_BIT;660 constexpr unsigned bitSize = countOfBits<T>; 661 661 662 662 using UT = typename std::make_unsigned<T>::type; … … 696 696 inline unsigned getMSBSet(T t) 697 697 { 698 constexpr unsigned bitSize = sizeof(T) * CHAR_BIT;698 constexpr unsigned bitSize = countOfBits<T>; 699 699 ASSERT(t); 700 700 return bitSize - 1 - clz(t); … … 704 704 constexpr unsigned getMSBSetConstexpr(T t) 705 705 { 706 constexpr unsigned bitSize = sizeof(T) * CHAR_BIT;706 constexpr unsigned bitSize = countOfBits<T>; 707 707 ASSERT_UNDER_CONSTEXPR_CONTEXT(t); 708 708 return bitSize - 1 - clzConstexpr(t); 709 709 } 710 711 template<typename T> unsigned log2(T value) { return getMSBSet(value); } 712 template<typename T> constexpr unsigned log2Constexpr(T value) { return getMSBSetConstexpr(value); } 710 713 711 714 } // namespace WTF
Note: See TracChangeset
for help on using the changeset viewer.