Changeset 181305 in webkit


Ignore:
Timestamp:
Mar 9, 2015 7:18:24 PM (9 years ago)
Author:
mark.lam@apple.com
Message:

8-bit version of weakCompareAndSwap() can cause an infinite loop.
https://webkit.org/b/142513>

Reviewed by Filip Pizlo.

Source/JavaScriptCore:

Added a test that exercises the 8-bit CAS from multiple threads. The threads
will contend to set bits in a large array of bytes using the CAS function.

  • API/tests/CompareAndSwapTest.cpp: Added.

(Bitmap::Bitmap):
(Bitmap::numBits):
(Bitmap::clearAll):
(Bitmap::concurrentTestAndSet):
(setBitThreadFunc):
(testCompareAndSwap):

  • API/tests/testapi.c:

(main):

Source/WTF:

Presently, Bitmap::concurrentTestAndSet() uses the 8-bit version of
weakCompareAndSwap() (which compares and swaps an uint8_t value).
Bitmap::concurrentTestAndSet() has a loop that checks if a bit in the
byte of interest has been set. If not, it will call the 8-bit CAS
function to set the bit.

Under the covers, for ARM, the 8-bit CAS function actually works with a
32-bit CAS. The 8-bit CAS will first fetch the 32-bit value in memory
that should contain the 8-bit value, and check if it contains the
expected byte. If the value in memory doesn't have the expected byte,
it will return early to its caller. The expectation is that the caller
will reload the byte from memory and call the 8-bit CAS again.

Unfortunately, this code path that returns early does not have a
compiler fence. Without a compiler fence, the C++ compiler can
optimize away the reloading of the expected byte value, leaving it
unchanged. As a result, we'll have a infinite loop here that checks a
value that will never change, and the loop will not terminate until the
value changes.

The fix is to eliminate the early return check in the 8-bit CAS, and
have it always call down to the 32-bit CAS. The 32-bit CAS has a
compiler fence which will prevent this issue.

  • wtf/Atomics.h:

(WTF::weakCompareAndSwap):

Location:
trunk/Source
Files:
1 added
7 edited

Legend:

Unmodified
Added
Removed
  • trunk/Source/JavaScriptCore/API/tests/testapi.c

    r181064 r181305  
    5151void testObjectiveCAPI(void);
    5252#endif
     53void testCompareAndSwap();
    5354
    5455bool assertTrue(bool value, const char* message);
     
    11921193    ::SetErrorMode(0);
    11931194#endif
     1195
     1196    testCompareAndSwap();
    11941197
    11951198#if JSC_OBJC_API_ENABLED
  • trunk/Source/JavaScriptCore/ChangeLog

    r181304 r181305  
     12015-03-09  Mark Lam  <mark.lam@apple.com>
     2
     3        8-bit version of weakCompareAndSwap() can cause an infinite loop.
     4        https://webkit.org/b/142513>
     5
     6        Reviewed by Filip Pizlo.
     7
     8        Added a test that exercises the 8-bit CAS from multiple threads.  The threads
     9        will contend to set bits in a large array of bytes using the CAS function.
     10
     11        * API/tests/CompareAndSwapTest.cpp: Added.
     12        (Bitmap::Bitmap):
     13        (Bitmap::numBits):
     14        (Bitmap::clearAll):
     15        (Bitmap::concurrentTestAndSet):
     16        (setBitThreadFunc):
     17        (testCompareAndSwap):
     18        * API/tests/testapi.c:
     19        (main):
     20        * JavaScriptCore.vcxproj/testapi/testapi.vcxproj:
     21        * JavaScriptCore.vcxproj/testapi/testapi.vcxproj.filters:
     22        * JavaScriptCore.xcodeproj/project.pbxproj:
     23
    1242015-03-09  Brent Fulgham  <bfulgham@apple.com>
    225
  • trunk/Source/JavaScriptCore/JavaScriptCore.vcxproj/testapi/testapi.vcxproj

    r173018 r181305  
    293293  <ItemGroup>
    294294    <ClCompile Include="..\..\API\tests\testapi.c" />
     295    <ClCompile Include="..\..\API\tests\CompareAndSwapTest.cpp" />
    295296    <ClCompile Include="..\..\API\tests\CustomGlobalObjectClassTest.c" />
    296297    <ClInclude Include="..\..\API\tests\CustomGlobalObjectClassTest.h" />
  • trunk/Source/JavaScriptCore/JavaScriptCore.vcxproj/testapi/testapi.vcxproj.filters

    r171543 r181305  
    99  <ItemGroup>
    1010    <ClCompile Include="..\..\API\tests\testapi.c" />
     11    <ClCompile Include="..\..\API\tests\CompareAndSwap.cpp" />
    1112    <ClCompile Include="..\..\API\tests\CustomGlobalObjectClassTest.c" />
    1213    <ClInclude Include="..\..\API\tests\CustomGlobalObjectClassTest.h" />
  • trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj

    r181297 r181305  
    16301630                FED94F2F171E3E2300BE77A4 /* Watchdog.h in Headers */ = {isa = PBXBuildFile; fileRef = FED94F2C171E3E2300BE77A4 /* Watchdog.h */; settings = {ATTRIBUTES = (Private, ); }; };
    16311631                FED94F30171E3E2300BE77A4 /* WatchdogMac.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FED94F2D171E3E2300BE77A4 /* WatchdogMac.cpp */; };
     1632                FEF040511AAE662D00BD28B0 /* CompareAndSwapTest.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FEF040501AAE662D00BD28B0 /* CompareAndSwapTest.cpp */; };
    16321633                FEF6835E174343CC00A32E25 /* JITStubsARM.h in Headers */ = {isa = PBXBuildFile; fileRef = FEF6835A174343CC00A32E25 /* JITStubsARM.h */; settings = {ATTRIBUTES = (Private, ); }; };
    16331634                FEF6835F174343CC00A32E25 /* JITStubsARMv7.h in Headers */ = {isa = PBXBuildFile; fileRef = FEF6835B174343CC00A32E25 /* JITStubsARMv7.h */; settings = {ATTRIBUTES = (Private, ); }; };
     
    33763377                FED94F2C171E3E2300BE77A4 /* Watchdog.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Watchdog.h; sourceTree = "<group>"; };
    33773378                FED94F2D171E3E2300BE77A4 /* WatchdogMac.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = WatchdogMac.cpp; sourceTree = "<group>"; };
     3379                FEF040501AAE662D00BD28B0 /* CompareAndSwapTest.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = CompareAndSwapTest.cpp; path = API/tests/CompareAndSwapTest.cpp; sourceTree = "<group>"; };
    33783380                FEF6835A174343CC00A32E25 /* JITStubsARM.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = JITStubsARM.h; sourceTree = "<group>"; };
    33793381                FEF6835B174343CC00A32E25 /* JITStubsARMv7.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = JITStubsARMv7.h; sourceTree = "<group>"; };
     
    37323734                        isa = PBXGroup;
    37333735                        children = (
     3736                                FEF040501AAE662D00BD28B0 /* CompareAndSwapTest.cpp */,
    37343737                                C203281E1981979D0088B499 /* CustomGlobalObjectClassTest.c */,
    37353738                                C203281F1981979D0088B499 /* CustomGlobalObjectClassTest.h */,
     
    67836786                                C288B2DE18A54D3E007BE40B /* DateTests.mm in Sources */,
    67846787                                C2181FC218A948FB0025A235 /* JSExportTests.mm in Sources */,
     6788                                FEF040511AAE662D00BD28B0 /* CompareAndSwapTest.cpp in Sources */,
    67856789                                1440F6100A4F85670005F061 /* testapi.c in Sources */,
    67866790                                86D2221A167EF9440024C804 /* testapi.mm in Sources */,
  • trunk/Source/WTF/ChangeLog

    r181271 r181305  
     12015-03-09  Mark Lam  <mark.lam@apple.com>
     2
     3        8-bit version of weakCompareAndSwap() can cause an infinite loop.
     4        https://webkit.org/b/142513>
     5
     6        Reviewed by Filip Pizlo.
     7
     8        Presently, Bitmap::concurrentTestAndSet() uses the 8-bit version of
     9        weakCompareAndSwap() (which compares and swaps an uint8_t value).
     10        Bitmap::concurrentTestAndSet() has a loop that checks if a bit in the
     11        byte of interest has been set.  If not, it will call the 8-bit CAS
     12        function to set the bit.
     13
     14        Under the covers, for ARM, the 8-bit CAS function actually works with a
     15        32-bit CAS.  The 8-bit CAS will first fetch the 32-bit value in memory
     16        that should contain the 8-bit value, and check if it contains the
     17        expected byte.  If the value in memory doesn't have the expected byte,
     18        it will return early to its caller.  The expectation is that the caller
     19        will reload the byte from memory and call the 8-bit CAS again.
     20
     21        Unfortunately, this code path that returns early does not have a
     22        compiler fence.  Without a compiler fence, the C++ compiler can
     23        optimize away the reloading of the expected byte value, leaving it
     24        unchanged.  As a result, we'll have a infinite loop here that checks a
     25        value that will never change, and the loop will not terminate until the
     26        value changes.
     27
     28        The fix is to eliminate the early return check in the 8-bit CAS, and
     29        have it always call down to the 32-bit CAS.  The 32-bit CAS has a
     30        compiler fence which will prevent this issue.
     31
     32        * wtf/Atomics.h:
     33        (WTF::weakCompareAndSwap):
     34
    1352015-03-09  Martin Robinson  <mrobinson@igalia.com>
    236
  • trunk/Source/WTF/wtf/Atomics.h

    r173949 r181305  
    316316    // Make sure that this load is always issued and never optimized away.
    317317    unsigned oldAlignedValue = *const_cast<volatile unsigned*>(alignedLocation);
    318     union {
    319         uint8_t bytes[sizeof(unsigned)];
    320         unsigned word;
    321     } u;
    322     u.word = oldAlignedValue;
    323     if (u.bytes[locationOffset] != expected)
    324         return false;
    325     u.bytes[locationOffset] = newValue;
    326     unsigned newAlignedValue = u.word;
    327     return weakCompareAndSwap(alignedLocation, oldAlignedValue, newAlignedValue);
     318
     319    struct Splicer {
     320        static unsigned splice(unsigned value, uint8_t byte, uintptr_t byteIndex)
     321        {
     322            union {
     323                unsigned word;
     324                uint8_t bytes[sizeof(unsigned)];
     325            } u;
     326            u.word = value;
     327            u.bytes[byteIndex] = byte;
     328            return u.word;
     329        }
     330    };
     331   
     332    unsigned expectedAlignedValue = Splicer::splice(oldAlignedValue, expected, locationOffset);
     333    unsigned newAlignedValue = Splicer::splice(oldAlignedValue, newValue, locationOffset);
     334
     335    return weakCompareAndSwap(alignedLocation, expectedAlignedValue, newAlignedValue);
    328336#endif
    329337#else
Note: See TracChangeset for help on using the changeset viewer.