Attachment 361899 Details for Bug 194566 – proposed patch.

[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:

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

Flags:

msaboff: review+

Actions: View | Formatted Diff | Diff

Attachments on bug 194566: 361863 | 361899