Changeset 241449 in webkit
- Timestamp:
- Feb 13, 2019 12:34:19 PM (5 years ago)
- Location:
- trunk/Source/JavaScriptCore
- Files:
-
- 3 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/Source/JavaScriptCore/ChangeLog
r241447 r241449 1 2019-02-13 Mark Lam <mark.lam@apple.com> 2 3 Create a randomized free list for new StructureIDs on StructureIDTable resize. 4 https://bugs.webkit.org/show_bug.cgi?id=194566 5 <rdar://problem/47975502> 6 7 Reviewed by Michael Saboff. 8 9 Also isolate 32-bit implementation of StructureIDTable out more so the 64-bit 10 implementation is a little easier to read. 11 12 This patch appears to be perf neutral on JetStream2 (as run from the command line). 13 14 * runtime/StructureIDTable.cpp: 15 (JSC::StructureIDTable::StructureIDTable): 16 (JSC::StructureIDTable::makeFreeListFromRange): 17 (JSC::StructureIDTable::resize): 18 (JSC::StructureIDTable::allocateID): 19 (JSC::StructureIDTable::deallocateID): 20 * runtime/StructureIDTable.h: 21 (JSC::StructureIDTable::get): 22 (JSC::StructureIDTable::deallocateID): 23 (JSC::StructureIDTable::allocateID): 24 (JSC::StructureIDTable::flushOldTables): 25 1 26 2019-02-13 Tadeu Zagallo <tzagallo@apple.com> 2 27 -
trunk/Source/JavaScriptCore/runtime/StructureIDTable.cpp
r241280 r241449 32 32 namespace JSC { 33 33 34 #if USE(JSVALUE64) 35 34 36 StructureIDTable::StructureIDTable() 35 37 : m_table(makeUniqueArray<StructureOrOffset>(s_initialSize)) 36 , m_size(0)37 38 , m_capacity(s_initialSize) 38 39 { 39 40 // We pre-allocate the first offset so that the null Structure 40 41 // can still be represented as the StructureID '0'. 41 allocateID(0); 42 table()[0].structure = nullptr; 43 44 makeFreeListFromRange(1, m_capacity - 1); 45 ASSERT(m_size == m_capacity); 46 } 47 48 void StructureIDTable::makeFreeListFromRange(uint32_t first, uint32_t last) 49 { 50 ASSERT(!m_firstFreeOffset); 51 ASSERT(!m_lastFreeOffset); 52 53 // Put all the new IDs on the free list sequentially. 54 uint32_t head = first; 55 uint32_t tail = last; 56 for (uint32_t i = first; i < last; ++i) 57 table()[i].offset = i + 1; 58 table()[last].offset = 0; 59 60 // Randomize the free list. 61 uint32_t size = last - first + 1; 62 uint32_t maxIterations = (size * 2) / 3; 63 for (uint32_t count = 0; count < maxIterations; ++count) { 64 // Move a random pick either to the head or the tail of the free list. 65 uint32_t random = m_weakRandom.getUint32(); 66 uint32_t nodeBefore = first + (random % size); 67 uint32_t pick = table()[nodeBefore].offset; 68 if (pick) { 69 uint32_t nodeAfter = table()[pick].offset; 70 table()[nodeBefore].offset = nodeAfter; 71 if ((random & 1) || !nodeAfter) { 72 // Move to the head. 73 table()[pick].offset = head; 74 head = pick; 75 if (!nodeAfter) 76 tail = nodeBefore; 77 } else { 78 // Move to the tail. 79 table()[pick].offset = 0; 80 table()[tail].offset = pick; 81 tail = pick; 82 } 83 } 84 } 85 86 // Cut list in half and swap halves. 87 uint32_t cut = first + (m_weakRandom.getUint32() % size); 88 uint32_t afterCut = table()[cut].offset; 89 if (afterCut) { 90 table()[tail].offset = head; 91 tail = cut; 92 head = afterCut; 93 table()[cut].offset = 0; 94 } 95 96 m_firstFreeOffset = head; 97 m_lastFreeOffset = tail; 98 m_size = m_capacity; 42 99 } 43 100 … … 61 118 // Update the capacity. 62 119 m_capacity = newCapacity; 120 121 makeFreeListFromRange(m_size, m_capacity - 1); 63 122 } 64 123 … … 70 129 StructureID StructureIDTable::allocateID(Structure* structure) 71 130 { 72 #if USE(JSVALUE64)73 131 if (!m_firstFreeOffset) { 74 132 RELEASE_ASSERT(m_capacity <= UINT_MAX); 75 133 if (m_size == m_capacity) 76 134 resize(m_capacity * 2); 77 ASSERT(m_size < m_capacity); 78 79 StructureOrOffset newEntry; 80 newEntry.structure = structure; 81 82 if (m_size == s_unusedID) { 83 m_size++; 84 return allocateID(structure); 85 } 86 87 StructureID result = m_size; 88 table()[result] = newEntry; 89 m_size++; 90 ASSERT(!isNuked(result)); 91 return result; 135 ASSERT(m_size == m_capacity); 136 ASSERT(m_firstFreeOffset); 92 137 } 93 138 … … 102 147 ASSERT(!isNuked(result)); 103 148 return result; 104 #else105 ASSERT(!isNuked(structure));106 return structure;107 #endif108 149 } 109 150 110 151 void StructureIDTable::deallocateID(Structure* structure, StructureID structureID) 111 152 { 112 #if USE(JSVALUE64)113 153 ASSERT(structureID != s_unusedID); 114 154 RELEASE_ASSERT(table()[structureID].structure == structure); … … 130 170 m_lastFreeOffset = structureID; 131 171 } 132 #else133 UNUSED_PARAM(structure);134 UNUSED_PARAM(structureID);135 #endif136 172 } 137 173 174 #endif // USE(JSVALUE64) 175 138 176 } // namespace JSC -
trunk/Source/JavaScriptCore/runtime/StructureIDTable.h
r241280 r241449 57 57 return id & ~nukedStructureIDBit(); 58 58 } 59 #else 59 #else // not USE(JSVALUE64) 60 60 typedef Structure* StructureID; 61 61 … … 79 79 return bitwise_cast<StructureID>(bitwise_cast<uintptr_t>(id) & ~bitwise_cast<uintptr_t>(nukedStructureIDBit())); 80 80 } 81 #endif 81 #endif // not USE(JSVALUE64) 82 83 #if USE(JSVALUE64) 82 84 83 85 class StructureIDTable { … … 98 100 private: 99 101 void resize(size_t newCapacity); 102 void makeFreeListFromRange(uint32_t first, uint32_t last); 100 103 101 104 union StructureOrOffset { … … 116 119 UniqueArray<StructureOrOffset> m_table; 117 120 118 size_t m_size ;121 size_t m_size { 0 }; 119 122 size_t m_capacity; 120 123 121 124 WeakRandom m_weakRandom; 122 125 123 #if USE(JSVALUE64)124 126 static const StructureID s_unusedID = unusedPointer; 125 #endif126 127 }; 127 128 128 129 inline Structure* StructureIDTable::get(StructureID structureID) 129 130 { 130 #if USE(JSVALUE64)131 131 ASSERT_WITH_SECURITY_IMPLICATION(structureID); 132 132 ASSERT_WITH_SECURITY_IMPLICATION(!isNuked(structureID)); 133 133 ASSERT_WITH_SECURITY_IMPLICATION(structureID < m_capacity); 134 134 return table()[structureID].structure; 135 #else136 return structureID;137 #endif138 135 } 139 136 137 #else // not USE(JSVALUE64) 138 139 class StructureIDTable { 140 friend class LLIntOffsetsExtractor; 141 public: 142 StructureIDTable() = default; 143 144 Structure* get(StructureID structureID) { return structureID; } 145 void deallocateID(Structure*, StructureID) { } 146 StructureID allocateID(Structure* structure) 147 { 148 ASSERT(!isNuked(structure)); 149 return structure; 150 }; 151 152 void flushOldTables() { } 153 }; 154 155 #endif // not USE(JSVALUE64) 156 140 157 } // namespace JSC
Note: See TracChangeset
for help on using the changeset viewer.