Changeset 241280 in webkit

Timestamp:

Feb 11, 2019, 2:44:17 PM (6 years ago)

Author:

mark.lam@apple.com

Message:

Randomize insertion of deallocated StructureIDs into the StructureIDTable's free list.
​https://bugs.webkit.org/show_bug.cgi?id=194512
<rdar://problem/47975465>

Reviewed by Yusuke Suzuki.

• runtime/StructureIDTable.cpp:

(JSC::StructureIDTable::StructureIDTable):
(JSC::StructureIDTable::allocateID):
(JSC::StructureIDTable::deallocateID):

• runtime/StructureIDTable.h:

Location:

trunk/Source/JavaScriptCore

Files:

• ChangeLog (modified) (1 diff)
• runtime/StructureIDTable.cpp (modified) (4 diffs)
• runtime/StructureIDTable.h (modified) (3 diffs)

trunk/Source/JavaScriptCore/ChangeLog

@@ +1 @@
+2019-02-11  Mark Lam  <mark.lam@apple.com>
+
+        Randomize insertion of deallocated StructureIDs into the StructureIDTable's free list.
+        https://bugs.webkit.org/show_bug.cgi?id=194512
+        <rdar://problem/47975465>
+
+        Reviewed by Yusuke Suzuki.
+
+        * runtime/StructureIDTable.cpp:
+        (JSC::StructureIDTable::StructureIDTable):
+        (JSC::StructureIDTable::allocateID):
+        (JSC::StructureIDTable::deallocateID):
+        * runtime/StructureIDTable.h:
+
 2019-02-10  Mark Lam  <mark.lam@apple.com>
 

trunk/Source/JavaScriptCore/runtime/StructureIDTable.cpp

@@ -1 +1 @@
 /*
- * Copyright (C) 2013 Apple Inc. All rights reserved.
+ * Copyright (C) 2013-2019 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
@@ -33 +33 @@
 
 StructureIDTable::StructureIDTable()
-    : m_firstFreeOffset(0)
-    , m_table(makeUniqueArray<StructureOrOffset>(s_initialSize))
+    : m_table(makeUniqueArray<StructureOrOffset>(s_initialSize))
     , m_size(0)
     , m_capacity(s_initialSize)
@@ -97 +96 @@
     StructureID result = m_firstFreeOffset;
     m_firstFreeOffset = table()[m_firstFreeOffset].offset;
+    if (!m_firstFreeOffset)
+        m_lastFreeOffset = 0;
+
     table()[result].structure = structure;
     ASSERT(!isNuked(result));
@@ -111 +113 @@
     ASSERT(structureID != s_unusedID);
     RELEASE_ASSERT(table()[structureID].structure == structure);
-    table()[structureID].offset = m_firstFreeOffset;
-    m_firstFreeOffset = structureID;
+
+    if (!m_firstFreeOffset) {
+        table()[structureID].offset = 0;
+        m_firstFreeOffset = structureID;
+        m_lastFreeOffset = structureID;
+        return;
+    }
+
+    bool insertAtHead = m_weakRandom.getUint32() & 1;
+    if (insertAtHead) {
+        table()[structureID].offset = m_firstFreeOffset;
+        m_firstFreeOffset = structureID;
+    } else {
+        table()[structureID].offset = 0;
+        table()[m_lastFreeOffset].offset = structureID;
+        m_lastFreeOffset = structureID;
+    }
 #else
     UNUSED_PARAM(structure);

trunk/Source/JavaScriptCore/runtime/StructureIDTable.h

@@ -1 +1 @@
 /*
- * Copyright (C) 2013 Apple Inc. All rights reserved.
+ * Copyright (C) 2013-2019 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
@@ -29 +29 @@
 #include <wtf/UniqueArray.h>
 #include <wtf/Vector.h>
+#include <wtf/WeakRandom.h>
 
 namespace JSC {
@@ -111 +112 @@
     Vector<UniqueArray<StructureOrOffset>> m_oldTables;
 
-    uint32_t m_firstFreeOffset;
+    uint32_t m_firstFreeOffset { 0 };
+    uint32_t m_lastFreeOffset { 0 };
     UniqueArray<StructureOrOffset> m_table;
 
     size_t m_size;
     size_t m_capacity;
+
+    WeakRandom m_weakRandom;
 
 #if USE(JSVALUE64)