WebKit Bugzilla
Attachment 361899 Details for
Bug 194566
: Create a randomized free list for new StructureIDs on StructureIDTable resize.
Home
|
New
|
Browse
|
Search
|
[?]
|
Reports
|
Requests
|
Help
|
New Account
|
Log In
Remember
[x]
|
Forgot Password
Login:
[x]
[patch]
proposed patch.
bug-194566.patch (text/plain), 7.69 KB, created by
Mark Lam
on 2019-02-12 22:55:51 PST
(
hide
)
Description:
proposed patch.
Filename:
MIME Type:
Creator:
Mark Lam
Created:
2019-02-12 22:55:51 PST
Size:
7.69 KB
patch
obsolete
>Index: Source/JavaScriptCore/ChangeLog >=================================================================== >--- Source/JavaScriptCore/ChangeLog (revision 241347) >+++ Source/JavaScriptCore/ChangeLog (working copy) >@@ -1,3 +1,28 @@ >+2019-02-12 Mark Lam <mark.lam@apple.com> >+ >+ Create a randomized free list for new StructureIDs on StructureIDTable resize. >+ https://bugs.webkit.org/show_bug.cgi?id=194566 >+ <rdar://problem/47975502> >+ >+ Reviewed by NOBODY (OOPS!). >+ >+ Also isolate 32-bit implementation of StructureIDTable out more so the 64-bit >+ implementation is a little easier to read. >+ >+ This patch appears to be perf neutral on JetStream2 (as run from the command line). >+ >+ * runtime/StructureIDTable.cpp: >+ (JSC::StructureIDTable::StructureIDTable): >+ (JSC::StructureIDTable::makeFreeListFromRange): >+ (JSC::StructureIDTable::resize): >+ (JSC::StructureIDTable::allocateID): >+ (JSC::StructureIDTable::deallocateID): >+ * runtime/StructureIDTable.h: >+ (JSC::StructureIDTable::get): >+ (JSC::StructureIDTable::deallocateID): >+ (JSC::StructureIDTable::allocateID): >+ (JSC::StructureIDTable::flushOldTables): >+ > 2019-02-12 Saam barati <sbarati@apple.com> > > JSScript needs to retain its cache path NSURL* >Index: Source/JavaScriptCore/runtime/StructureIDTable.cpp >=================================================================== >--- Source/JavaScriptCore/runtime/StructureIDTable.cpp (revision 241339) >+++ Source/JavaScriptCore/runtime/StructureIDTable.cpp (working copy) >@@ -31,14 +31,71 @@ > > namespace JSC { > >+#if USE(JSVALUE64) >+ > StructureIDTable::StructureIDTable() > : m_table(makeUniqueArray<StructureOrOffset>(s_initialSize)) >- , m_size(0) > , m_capacity(s_initialSize) > { > // We pre-allocate the first offset so that the null Structure > // can still be represented as the StructureID '0'. >- allocateID(0); >+ table()[0].structure = nullptr; >+ >+ makeFreeListFromRange(1, m_capacity - 1); >+ ASSERT(m_size == m_capacity); >+} >+ >+void StructureIDTable::makeFreeListFromRange(uint32_t first, uint32_t last) >+{ >+ ASSERT(!m_firstFreeOffset); >+ ASSERT(!m_lastFreeOffset); >+ >+ // Put all the new IDs on the free list sequentially. >+ uint32_t head = first; >+ uint32_t tail = last; >+ for (uint32_t i = first; i < last; ++i) >+ table()[i].offset = i + 1; >+ table()[last].offset = 0; >+ >+ // Randomize the free list. >+ uint32_t size = last - first + 1; >+ uint32_t maxIterations = (size * 2) / 3; >+ for (uint32_t count = 0; count < maxIterations; ++count) { >+ // Move a random pick either to the head or the tail of the free list. >+ uint32_t random = m_weakRandom.getUint32(); >+ uint32_t nodeBefore = first + (random % size); >+ uint32_t pick = table()[nodeBefore].offset; >+ if (pick) { >+ uint32_t nodeAfter = table()[pick].offset; >+ table()[nodeBefore].offset = nodeAfter; >+ if ((random & 1) || !nodeAfter) { >+ // Move to the head. >+ table()[pick].offset = head; >+ head = pick; >+ if (!nodeAfter) >+ tail = nodeBefore; >+ } else { >+ // Move to the tail. >+ table()[pick].offset = 0; >+ table()[tail].offset = pick; >+ tail = pick; >+ } >+ } >+ } >+ >+ // Cut list in half and swap halves. >+ uint32_t cut = first + (m_weakRandom.getUint32() % size); >+ uint32_t afterCut = table()[cut].offset; >+ if (afterCut) { >+ table()[tail].offset = head; >+ tail = cut; >+ head = afterCut; >+ table()[cut].offset = 0; >+ } >+ >+ m_firstFreeOffset = head; >+ m_lastFreeOffset = tail; >+ m_size = m_capacity; > } > > void StructureIDTable::resize(size_t newCapacity) >@@ -60,6 +117,8 @@ void StructureIDTable::resize(size_t new > > // Update the capacity. > m_capacity = newCapacity; >+ >+ makeFreeListFromRange(m_size, m_capacity - 1); > } > > void StructureIDTable::flushOldTables() >@@ -69,26 +128,12 @@ void StructureIDTable::flushOldTables() > > StructureID StructureIDTable::allocateID(Structure* structure) > { >-#if USE(JSVALUE64) > if (!m_firstFreeOffset) { > RELEASE_ASSERT(m_capacity <= UINT_MAX); > if (m_size == m_capacity) > resize(m_capacity * 2); >- ASSERT(m_size < m_capacity); >- >- StructureOrOffset newEntry; >- newEntry.structure = structure; >- >- if (m_size == s_unusedID) { >- m_size++; >- return allocateID(structure); >- } >- >- StructureID result = m_size; >- table()[result] = newEntry; >- m_size++; >- ASSERT(!isNuked(result)); >- return result; >+ ASSERT(m_size == m_capacity); >+ ASSERT(m_firstFreeOffset); > } > > ASSERT(m_firstFreeOffset != s_unusedID); >@@ -101,15 +146,10 @@ StructureID StructureIDTable::allocateID > table()[result].structure = structure; > ASSERT(!isNuked(result)); > return result; >-#else >- ASSERT(!isNuked(structure)); >- return structure; >-#endif > } > > void StructureIDTable::deallocateID(Structure* structure, StructureID structureID) > { >-#if USE(JSVALUE64) > ASSERT(structureID != s_unusedID); > RELEASE_ASSERT(table()[structureID].structure == structure); > >@@ -129,10 +169,8 @@ void StructureIDTable::deallocateID(Stru > table()[m_lastFreeOffset].offset = structureID; > m_lastFreeOffset = structureID; > } >-#else >- UNUSED_PARAM(structure); >- UNUSED_PARAM(structureID); >-#endif > } > >+#endif // USE(JSVALUE64) >+ > } // namespace JSC >Index: Source/JavaScriptCore/runtime/StructureIDTable.h >=================================================================== >--- Source/JavaScriptCore/runtime/StructureIDTable.h (revision 241339) >+++ Source/JavaScriptCore/runtime/StructureIDTable.h (working copy) >@@ -56,7 +56,7 @@ inline StructureID decontaminate(Structu > { > return id & ~nukedStructureIDBit(); > } >-#else >+#else // not USE(JSVALUE64) > typedef Structure* StructureID; > > inline StructureID nukedStructureIDBit() >@@ -78,7 +78,9 @@ inline StructureID decontaminate(Structu > { > return bitwise_cast<StructureID>(bitwise_cast<uintptr_t>(id) & ~bitwise_cast<uintptr_t>(nukedStructureIDBit())); > } >-#endif >+#endif // not USE(JSVALUE64) >+ >+#if USE(JSVALUE64) > > class StructureIDTable { > friend class LLIntOffsetsExtractor; >@@ -97,6 +99,7 @@ public: > > private: > void resize(size_t newCapacity); >+ void makeFreeListFromRange(uint32_t first, uint32_t last); > > union StructureOrOffset { > WTF_MAKE_FAST_ALLOCATED; >@@ -115,26 +118,40 @@ private: > uint32_t m_lastFreeOffset { 0 }; > UniqueArray<StructureOrOffset> m_table; > >- size_t m_size; >+ size_t m_size { 0 }; > size_t m_capacity; > > WeakRandom m_weakRandom; > >-#if USE(JSVALUE64) > static const StructureID s_unusedID = unusedPointer; >-#endif > }; > > inline Structure* StructureIDTable::get(StructureID structureID) > { >-#if USE(JSVALUE64) > ASSERT_WITH_SECURITY_IMPLICATION(structureID); > ASSERT_WITH_SECURITY_IMPLICATION(!isNuked(structureID)); > ASSERT_WITH_SECURITY_IMPLICATION(structureID < m_capacity); > return table()[structureID].structure; >-#else >- return structureID; >-#endif > } > >+#else // not USE(JSVALUE64) >+ >+class StructureIDTable { >+ friend class LLIntOffsetsExtractor; >+public: >+ StructureIDTable() = default; >+ >+ Structure* get(StructureID structureID) { return structureID; } >+ void deallocateID(Structure*, StructureID) { } >+ StructureID allocateID(Structure* structure) >+ { >+ ASSERT(!isNuked(structure)); >+ return structure; >+ }; >+ >+ void flushOldTables() { } >+}; >+ >+#endif // not USE(JSVALUE64) >+ > } // namespace JSC
You cannot view the attachment while viewing its details because your browser does not support IFRAMEs.
View the attachment on a separate page
.
View Attachment As Diff
View Attachment As Raw
Flags:
msaboff
:
review+
Actions:
View
|
Formatted Diff
|
Diff
Attachments on
bug 194566
:
361863
| 361899