Changeset 274608 in webkit


Ignore:
Timestamp:
Mar 17, 2021 7:40:00 PM (3 years ago)
Author:
mark.lam@apple.com
Message:

Fix race condition in ConcurrentPtrHashSet.
​https://bugs.webkit.org/show_bug.cgi?id=223241
rdar://74637896

Reviewed by Yusuke Suzuki.

JSTests:

  • stress/race-to-add-opaque-roots-in-ConcurrentPtrHashSet.js: Added.

Source/WTF:

There exists a race condition where ConcurrentPtrHashSet::resizeIfNecessary() may
not capture an entry added by ConcurrentPtrHashSet::addSlow() concurrently.

ConcurrentPtrHashSet::addSlow() currently does the following:

{

if (table->load.exchangeAdd(1) >= table->maxLoad()) (a1)

return resizeAndAdd(ptr); (a2)


for (;;) {

void* oldEntry = table->array[index].compareExchangeStrong(nullptr, ptr); (a3)
if (!oldEntry) {

if (m_table.load() != table) { (a4)

We added an entry to an old table! We need to reexecute the add on the new table.
return add(ptr); (a5)

}
return true; (a6)

}
if (oldEntry == ptr)

return false;

... set index to next entry slot to try.

}

}

ConcurrentPtrHashSet::resizeIfNecessary() currently does the following:

{

auto locker = holdLock(m_lock); (r1)
Table* table = m_table.loadRelaxed();
if (table->load.loadRelaxed() < table->maxLoad())

return;

(r2)

std::unique_ptr<Table> newTable = Table::create(table->size * 2);
...
for (unsigned i = 0; i < table->size; ++i) { (r3)

void* ptr = table->array[i].loadRelaxed();
if (!ptr)

continue;


... copy ptr to newTable. (r4)

}


...
m_table.store(newTable.get()); (r5)
...

}

Let's say thread T1 is executing addSlow(), and thread T2 is concurrently executing
resizeIfNecessary().

Consider the following scenario (in chronological order):

  1. T2 has arrived at just before (r5) i.e. it is already done copying the entries in the old m_table.
  2. T1 executes (a3) and writes a new entry into m_table.
  3. T1 checks that the table hasn't been replaced at (a4), and sees that it has not.
  4. T1 returns at (a6), thinking that its new entry is committed.
  5. T2 sets the new m_table at (r5), thereby discarding the new entry that T1 has just written.

The fix is to set m_table to a newly introduced m_stubTable at (r2). m_stubTable
is set up with a size of 0, and load value of 10. This means it is always full.
With this, the following scenarios can play out:

Scenario 1: T2 installs m_stubTable before T1 reaches (a1)

  1. At (a1), T1 sees that m_table (which is m_stubTable) is full.
  2. T1 calls resizeAndAdd() at (a2), which ends up calling resizeIfNecessary() and blocking on the lock at (r1).

Scenario 2: T2 installs m_stubTable after T1 reaches just before (a3)

  1. T1 writes the new entry at (a3).
  2. T1 checks m_table at (a4), and sees that it has changed (now pointing to m_stubTable).
  3. T1 calls add() again at (a5) to redo the operation, and ends with scenario 1.

Scenario 3: T2 installs m_stubTable after T1 reaches (a3), but before (a4)

  1. The new entry has already been added, but we don't know if it made the cut off for T2 to copy it or not. But, it doesn't matter because ...
  2. T1 checks m_table at (a4), and sees that it has changed (now pointing to m_stubTable).
  3. T1 calls add() again at (a5) to redo the operation, and ends with scenario 1.

Scenario 4: T2 installs m_stubTable after T1 reaches (a4)

  1. The new entry has already been added.
  2. T1 checks m_table at (a4), and sees that it has NOT changed (because T2 hasn't installed m_stubTable yet). This means T2's copy loop is guaranteed to not have started yet i.e. the new entry will definitely be picked up by the copy loop.
  3. T1 returns at (a6), and all is well.
  • wtf/ConcurrentPtrHashSet.cpp:

(WTF::ConcurrentPtrHashSet::deleteOldTables):
(WTF::ConcurrentPtrHashSet::initialize):
(WTF::ConcurrentPtrHashSet::containsImplSlow const):
(WTF::ConcurrentPtrHashSet::sizeSlow const):
(WTF::ConcurrentPtrHashSet::resizeIfNecessary):
(WTF::ConcurrentPtrHashSet::Table::initializeStub):

  • wtf/ConcurrentPtrHashSet.h:
Location:
trunk
Files:
1 added
4 edited

Legend:

Unmodified
Added
Removed

  • trunk/JSTests/ChangeLog

    r274552 r274608  
     12021-03-17  Mark Lam  <mark.lam@apple.com>
     2
     3        Fix race condition in ConcurrentPtrHashSet.
     4        https://bugs.webkit.org/show_bug.cgi?id=223241
     5        rdar://74637896
     6
     7        Reviewed by Yusuke Suzuki.
     8
     9        * stress/race-to-add-opaque-roots-in-ConcurrentPtrHashSet.js: Added.
     10
    1112021-03-16  Ross Kirsling  <ross.kirsling@sony.com>
    212

  • trunk/Source/WTF/ChangeLog

    r274603 r274608  
     12021-03-17  Mark Lam  <mark.lam@apple.com>
     2
     3        Fix race condition in ConcurrentPtrHashSet.
     4        https://bugs.webkit.org/show_bug.cgi?id=223241
     5        rdar://74637896
     6
     7        Reviewed by Yusuke Suzuki.
     8
     9        There exists a race condition where ConcurrentPtrHashSet::resizeIfNecessary() may
     10        not capture an entry added by ConcurrentPtrHashSet::addSlow() concurrently.
     11
     12        ConcurrentPtrHashSet::addSlow() currently does the following:
     13
     14            {
     15                if (table->load.exchangeAdd(1) >= table->maxLoad())     // (a1)
     16                    return resizeAndAdd(ptr);                           // (a2)
     17   
     18                for (;;) {
     19                    void* oldEntry = table->array[index].compareExchangeStrong(nullptr, ptr);   // (a3)
     20                    if (!oldEntry) {
     21                        if (m_table.load() != table) {                  // (a4)
     22                            // We added an entry to an old table! We need to reexecute the add on the new table.
     23                            return add(ptr);                            // (a5)
     24                        }
     25                        return true;                                    // (a6)
     26                    }
     27                    if (oldEntry == ptr)
     28                        return false;
     29
     30                    ... // set index to next entry slot to try.
     31                }
     32            }
     33
     34        ConcurrentPtrHashSet::resizeIfNecessary() currently does the following:
     35
     36            {
     37                auto locker = holdLock(m_lock);                         // (r1)
     38                Table* table = m_table.loadRelaxed();
     39                if (table->load.loadRelaxed() < table->maxLoad())
     40                    return;
     41
     42                // (r2)
     43
     44                std::unique_ptr<Table> newTable = Table::create(table->size * 2);
     45                ...
     46                for (unsigned i = 0; i < table->size; ++i) {            // (r3)
     47                    void* ptr = table->array[i].loadRelaxed();
     48                    if (!ptr)
     49                        continue;
     50       
     51                    ... // copy ptr to newTable.                        // (r4)
     52                }
     53   
     54                ...
     55                m_table.store(newTable.get());                          // (r5)
     56                ...
     57            }
     58
     59        Let's say thread T1 is executing addSlow(), and thread T2 is concurrently executing
     60        resizeIfNecessary().
     61
     62        Consider the following scenario (in chronological order):
     63        1. T2 has arrived at just before (r5) i.e. it is already done copying the entries
     64           in the old m_table. 
     65        2. T1 executes (a3) and writes a new entry into m_table.
     66        3. T1 checks that the table hasn't been replaced at (a4), and sees that it has
     67           not.
     68        4. T1 returns at (a6), thinking that its new entry is committed.
     69        5. T2 sets the new m_table at (r5), thereby discarding the new entry that T1 has
     70           just written.
     71
     72        The fix is to set m_table to a newly introduced m_stubTable at (r2).  m_stubTable
     73        is set up with a size of 0, and load value of 10.  This means it is always full.
     74        With this, the following scenarios can play out:
     75
     76        Scenario 1: T2 installs m_stubTable before T1 reaches (a1)
     77
     78        1. At (a1), T1 sees that m_table (which is m_stubTable) is full.
     79        2. T1 calls resizeAndAdd() at (a2), which ends up calling resizeIfNecessary()
     80           and blocking on the lock at (r1).
     81
     82        Scenario 2: T2 installs m_stubTable after T1 reaches just before (a3)
     83
     84        1. T1 writes the new entry at (a3).
     85        2. T1 checks m_table at (a4), and sees that it has changed (now pointing to
     86           m_stubTable).
     87        3. T1 calls add() again at (a5) to redo the operation, and ends with scenario 1.
     88
     89        Scenario 3: T2 installs m_stubTable after T1 reaches (a3), but before (a4)
     90
     91        1. The new entry has already been added, but we don't know if it made the cut off
     92           for T2 to copy it or not.  But, it doesn't matter because ...
     93        2. T1 checks m_table at (a4), and sees that it has changed (now pointing to
     94           m_stubTable).
     95        3. T1 calls add() again at (a5) to redo the operation, and ends with scenario 1.
     96
     97        Scenario 4: T2 installs m_stubTable after T1 reaches (a4)
     98
     99        1. The new entry has already been added.
     100        2. T1 checks m_table at (a4), and sees that it has NOT changed (because T2 hasn't
     101           installed m_stubTable yet).  This means T2's copy loop is guaranteed to not
     102           have started yet i.e. the new entry will definitely be picked up by the copy
     103           loop.
     104        3. T1 returns at (a6), and all is well.
     105
     106        * wtf/ConcurrentPtrHashSet.cpp:
     107        (WTF::ConcurrentPtrHashSet::deleteOldTables):
     108        (WTF::ConcurrentPtrHashSet::initialize):
     109        (WTF::ConcurrentPtrHashSet::containsImplSlow const):
     110        (WTF::ConcurrentPtrHashSet::sizeSlow const):
     111        (WTF::ConcurrentPtrHashSet::resizeIfNecessary):
     112        (WTF::ConcurrentPtrHashSet::Table::initializeStub):
     113        * wtf/ConcurrentPtrHashSet.h:
     114
    11152021-03-17  Alex Christensen  <achristensen@webkit.org>
    2116

  • trunk/Source/WTF/wtf/ConcurrentPtrHashSet.cpp

    r261661 r274608  
    11/*
    2  * Copyright (C) 2017 Apple Inc. All rights reserved.
     2 * Copyright (C) 2017-2021 Apple Inc. All rights reserved.
    33 *
    44 * Redistribution and use in source and binary forms, with or without
    … …  
    4343    // some bad crashes if we did make that mistake.
    4444    auto locker = holdLock(m_lock);
    45    
     45
     46    ASSERT(m_table.loadRelaxed() != &m_stubTable);
    4647    m_allTables.removeAllMatching(
    4748        [&] (std::unique_ptr<Table>& table) -> bool {
    … …  
    6667    m_table.storeRelaxed(table.get());
    6768    m_allTables.append(WTFMove(table));
     69    m_stubTable.initializeStub();
    6870}
    6971
    … …  
    8991}
    9092
     93bool ConcurrentPtrHashSet::containsImplSlow(void* ptr) const
     94{
     95    auto locker = holdLock(m_lock);
     96    ASSERT(m_table.loadRelaxed() != &m_stubTable);
     97    return containsImpl(ptr);
     98}
     99
     100size_t ConcurrentPtrHashSet::sizeSlow() const
     101{
     102    auto locker = holdLock(m_lock);
     103    ASSERT(m_table.loadRelaxed() != &m_stubTable);
     104    return size();
     105}
     106
    91107void ConcurrentPtrHashSet::resizeIfNecessary()
    92108{
    93109    auto locker = holdLock(m_lock);
    94110    Table* table = m_table.loadRelaxed();
     111    ASSERT(table != &m_stubTable);
    95112    if (table->load.loadRelaxed() < table->maxLoad())
    96113        return;
    97    
     114
     115    // Stubbing out m_table with m_stubTable here is necessary to ensure that
     116    // we don't miss copying any entries that may be concurrently be added.
     117    //
     118    // If addSlow() completes before this stubbing, the new entry is guaranteed
     119    // to be copied below.
     120    //
     121    // If addSlow() completes after this stubbing, addSlow()  will check m_table
     122    // before it finishes, and detect that its newly added entry may not have
     123    // made it in. As a result, it will try to re-add the entry, and end up
     124    // blocking on resizeIfNecessary() until the resizing is donw. This is
     125    // because m_stubTable will tell addSlow() think that the table is out of
     126    // space and it needs to resize. NOTE: m_stubTable always says it is out of
     127    // space.
     128    m_table.store(&m_stubTable);
     129
    98130    std::unique_ptr<Table> newTable = Table::create(table->size * 2);
    99131    unsigned mask = newTable->mask;
    … …  
    122154   
    123155    newTable->load.storeRelaxed(load);
    124    
     156
    125157    m_table.store(newTable.get());
     158
     159    // addSlow() will always start by exchangeAdd'ing 1 to the current m_table's
     160    // load value before checking if it exceeds its max allowed load. For the
     161    // real m_table, this is not an issue because at most, it will accummulate
     162    // up to N extra adds above max load, where N is the number of threads
     163    // concurrrently adding entries.
     164    //
     165    // However, m_table may be replaced with m_stubTable for each resize
     166    // operation. As a result, the cummulative error on its load value
     167    // may far exceed N (as specified above). To fix this, we always reset it
     168    // here to prevent an overflow. Note: a load of stubDefaultLoadValue means
     169    // that m_stubTable is full since its size is 0.
     170    //
     171    // In practice, this won't matter because we most likely won't do so many
     172    // resize operations such that this will get to the point of overflowing.
     173    // However, since resizing is not in the fast path, let's just be pedantic
     174    // and reset it for correctness.
     175    m_stubTable.load.store(Table::stubDefaultLoadValue);
     176
    126177    m_allTables.append(WTFMove(newTable));
    127178}
    … …  
    144195}
    145196
     197void ConcurrentPtrHashSet::Table::initializeStub()
     198{
     199    // The stub table is set up to look like it is already filled up. This is
     200    // so that it can be used during resizing to force all attempts to add to
     201    // be routed to resizeAndAdd() where it will block until the resizing is
     202    // done.
     203    size = 0;
     204    mask = 0;
     205    load.storeRelaxed(stubDefaultLoadValue);
     206    array[0].storeRelaxed(nullptr);
     207}
     208
    146209} // namespace WTF
    147210

  • trunk/Source/WTF/wtf/ConcurrentPtrHashSet.h

    r272192 r274608  
    7575    size_t size() const
    7676    {
    77         return m_table.loadRelaxed()->load.loadRelaxed();
     77        Table* table = m_table.loadRelaxed();
     78        if (table == &m_stubTable)
     79            return sizeSlow();
     80        return table->load.loadRelaxed();
    7881    }
    7982   
    … …  
    9194       
    9295        static std::unique_ptr<Table> create(unsigned size);
    93        
     96        void initializeStub();
     97
    9498        unsigned maxLoad() const { return size / 2; }
    95        
     99
     100        // This can be any value >= 1 because the stub's size is 0, ensuring that
     101        // m_stubTable is always seen as "full". We choose 10 for no reason other
     102        // than it gives some warm fuzzies since it is greater than 1.
     103        static constexpr unsigned stubDefaultLoadValue = 10;
     104
    96105        unsigned size; // This is immutable.
    97106        unsigned mask; // This is immutable.
    … …  
    123132    {
    124133        Table* table = m_table.loadRelaxed();
     134        if (table == &m_stubTable)
     135            return containsImplSlow(ptr);
     136
    125137        unsigned mask = table->mask;
    126138        unsigned startIndex = hash(ptr) & mask;
    … …  
    156168   
    157169    WTF_EXPORT_PRIVATE bool addSlow(Table* table, unsigned mask, unsigned startIndex, unsigned index, void* ptr);
     170    WTF_EXPORT_PRIVATE bool containsImplSlow(void* ptr) const;
     171    WTF_EXPORT_PRIVATE size_t sizeSlow() const;
    158172
    159173    void resizeIfNecessary();
    160174    bool resizeAndAdd(void* ptr);
    161    
     175
    162176    Vector<std::unique_ptr<Table>, 4> m_allTables;
    163177    Atomic<Table*> m_table; // This is never null.
    164     Lock m_lock; // We just use this to control resize races.
     178    Table m_stubTable;
     179    mutable Lock m_lock; // We just use this to control resize races.
    165180};
    166181
Note: See TracChangeset for help on using the changeset viewer.