Changeset 241449 in webkit


Ignore:
Timestamp:
Feb 13, 2019 12:34:19 PM (5 years ago)
Author:
mark.lam@apple.com
Message:

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 Michael Saboff.

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

Location:
trunk/Source/JavaScriptCore
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • trunk/Source/JavaScriptCore/ChangeLog

    r241447 r241449  
     12019-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
    1262019-02-13  Tadeu Zagallo  <tzagallo@apple.com>
    227
  • trunk/Source/JavaScriptCore/runtime/StructureIDTable.cpp

    r241280 r241449  
    3232namespace JSC {
    3333
     34#if USE(JSVALUE64)
     35
    3436StructureIDTable::StructureIDTable()
    3537    : m_table(makeUniqueArray<StructureOrOffset>(s_initialSize))
    36     , m_size(0)
    3738    , m_capacity(s_initialSize)
    3839{
    3940    // We pre-allocate the first offset so that the null Structure
    4041    // 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
     48void 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;
    4299}
    43100
     
    61118    // Update the capacity.
    62119    m_capacity = newCapacity;
     120
     121    makeFreeListFromRange(m_size, m_capacity - 1);
    63122}
    64123
     
    70129StructureID StructureIDTable::allocateID(Structure* structure)
    71130{
    72 #if USE(JSVALUE64)
    73131    if (!m_firstFreeOffset) {
    74132        RELEASE_ASSERT(m_capacity <= UINT_MAX);
    75133        if (m_size == m_capacity)
    76134            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);
    92137    }
    93138
     
    102147    ASSERT(!isNuked(result));
    103148    return result;
    104 #else
    105     ASSERT(!isNuked(structure));
    106     return structure;
    107 #endif
    108149}
    109150
    110151void StructureIDTable::deallocateID(Structure* structure, StructureID structureID)
    111152{
    112 #if USE(JSVALUE64)
    113153    ASSERT(structureID != s_unusedID);
    114154    RELEASE_ASSERT(table()[structureID].structure == structure);
     
    130170        m_lastFreeOffset = structureID;
    131171    }
    132 #else
    133     UNUSED_PARAM(structure);
    134     UNUSED_PARAM(structureID);
    135 #endif
    136172}
    137173
     174#endif // USE(JSVALUE64)
     175
    138176} // namespace JSC
  • trunk/Source/JavaScriptCore/runtime/StructureIDTable.h

    r241280 r241449  
    5757    return id & ~nukedStructureIDBit();
    5858}
    59 #else
     59#else // not USE(JSVALUE64)
    6060typedef Structure* StructureID;
    6161
     
    7979    return bitwise_cast<StructureID>(bitwise_cast<uintptr_t>(id) & ~bitwise_cast<uintptr_t>(nukedStructureIDBit()));
    8080}
    81 #endif
     81#endif // not USE(JSVALUE64)
     82
     83#if USE(JSVALUE64)
    8284
    8385class StructureIDTable {
     
    98100private:
    99101    void resize(size_t newCapacity);
     102    void makeFreeListFromRange(uint32_t first, uint32_t last);
    100103
    101104    union StructureOrOffset {
     
    116119    UniqueArray<StructureOrOffset> m_table;
    117120
    118     size_t m_size;
     121    size_t m_size { 0 };
    119122    size_t m_capacity;
    120123
    121124    WeakRandom m_weakRandom;
    122125
    123 #if USE(JSVALUE64)
    124126    static const StructureID s_unusedID = unusedPointer;
    125 #endif
    126127};
    127128
    128129inline Structure* StructureIDTable::get(StructureID structureID)
    129130{
    130 #if USE(JSVALUE64)
    131131    ASSERT_WITH_SECURITY_IMPLICATION(structureID);
    132132    ASSERT_WITH_SECURITY_IMPLICATION(!isNuked(structureID));
    133133    ASSERT_WITH_SECURITY_IMPLICATION(structureID < m_capacity);
    134134    return table()[structureID].structure;
    135 #else
    136     return structureID;
    137 #endif
    138135}
    139136
     137#else // not USE(JSVALUE64)
     138
     139class StructureIDTable {
     140    friend class LLIntOffsetsExtractor;
     141public:
     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
    140157} // namespace JSC
Note: See TracChangeset for help on using the changeset viewer.