<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
"http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head><meta http-equiv="content-type" content="text/html; charset=utf-8" />
<title>[184462] releases/WebKitGTK/webkit-2.4/Source</title>
</head>
<body>
<style type="text/css"><!--
#msg dl.meta { border: 1px #006 solid; background: #369; padding: 6px; color: #fff; }
#msg dl.meta dt { float: left; width: 6em; font-weight: bold; }
#msg dt:after { content:':';}
#msg dl, #msg dt, #msg ul, #msg li, #header, #footer, #logmsg { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; }
#msg dl a { font-weight: bold}
#msg dl a:link { color:#fc3; }
#msg dl a:active { color:#ff0; }
#msg dl a:visited { color:#cc6; }
h3 { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; font-weight: bold; }
#msg pre { overflow: auto; background: #ffc; border: 1px #fa0 solid; padding: 6px; }
#logmsg { background: #ffc; border: 1px #fa0 solid; padding: 1em 1em 0 1em; }
#logmsg p, #logmsg pre, #logmsg blockquote { margin: 0 0 1em 0; }
#logmsg p, #logmsg li, #logmsg dt, #logmsg dd { line-height: 14pt; }
#logmsg h1, #logmsg h2, #logmsg h3, #logmsg h4, #logmsg h5, #logmsg h6 { margin: .5em 0; }
#logmsg h1:first-child, #logmsg h2:first-child, #logmsg h3:first-child, #logmsg h4:first-child, #logmsg h5:first-child, #logmsg h6:first-child { margin-top: 0; }
#logmsg ul, #logmsg ol { padding: 0; list-style-position: inside; margin: 0 0 0 1em; }
#logmsg ul { text-indent: -1em; padding-left: 1em; }#logmsg ol { text-indent: -1.5em; padding-left: 1.5em; }
#logmsg > ul, #logmsg > ol { margin: 0 0 1em 0; }
#logmsg pre { background: #eee; padding: 1em; }
#logmsg blockquote { border: 1px solid #fa0; border-left-width: 10px; padding: 1em 1em 0 1em; background: white;}
#logmsg dl { margin: 0; }
#logmsg dt { font-weight: bold; }
#logmsg dd { margin: 0; padding: 0 0 0.5em 0; }
#logmsg dd:before { content:'\00bb';}
#logmsg table { border-spacing: 0px; border-collapse: collapse; border-top: 4px solid #fa0; border-bottom: 1px solid #fa0; background: #fff; }
#logmsg table th { text-align: left; font-weight: normal; padding: 0.2em 0.5em; border-top: 1px dotted #fa0; }
#logmsg table td { text-align: right; border-top: 1px dotted #fa0; padding: 0.2em 0.5em; }
#logmsg table thead th { text-align: center; border-bottom: 1px solid #fa0; }
#logmsg table th.Corner { text-align: left; }
#logmsg hr { border: none 0; border-top: 2px dashed #fa0; height: 1px; }
#header, #footer { color: #fff; background: #636; border: 1px #300 solid; padding: 6px; }
#patch { width: 100%; }
#patch h4 {font-family: verdana,arial,helvetica,sans-serif;font-size:10pt;padding:8px;background:#369;color:#fff;margin:0;}
#patch .propset h4, #patch .binary h4 {margin:0;}
#patch pre {padding:0;line-height:1.2em;margin:0;}
#patch .diff {width:100%;background:#eee;padding: 0 0 10px 0;overflow:auto;}
#patch .propset .diff, #patch .binary .diff {padding:10px 0;}
#patch span {display:block;padding:0 10px;}
#patch .modfile, #patch .addfile, #patch .delfile, #patch .propset, #patch .binary, #patch .copfile {border:1px solid #ccc;margin:10px 0;}
#patch ins {background:#dfd;text-decoration:none;display:block;padding:0 10px;}
#patch del {background:#fdd;text-decoration:none;display:block;padding:0 10px;}
#patch .lines, .info {color:#888;background:#fff;}
--></style>
<div id="msg">
<dl class="meta">
<dt>Revision</dt> <dd><a href="http://trac.webkit.org/projects/webkit/changeset/184462">184462</a></dd>
<dt>Author</dt> <dd>carlosgc@webkit.org</dd>
<dt>Date</dt> <dd>2015-05-18 05:02:56 -0700 (Mon, 18 May 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>Merge <a href="http://trac.webkit.org/projects/webkit/changeset/181305">r181305</a> - 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):
* JavaScriptCore.vcxproj/testapi/testapi.vcxproj:
* JavaScriptCore.vcxproj/testapi/testapi.vcxproj.filters:
* JavaScriptCore.xcodeproj/project.pbxproj:
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):</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#releasesWebKitGTKwebkit24SourceJavaScriptCoreAPIteststestapic">releases/WebKitGTK/webkit-2.4/Source/JavaScriptCore/API/tests/testapi.c</a></li>
<li><a href="#releasesWebKitGTKwebkit24SourceJavaScriptCoreChangeLog">releases/WebKitGTK/webkit-2.4/Source/JavaScriptCore/ChangeLog</a></li>
<li><a href="#releasesWebKitGTKwebkit24SourceWTFChangeLog">releases/WebKitGTK/webkit-2.4/Source/WTF/ChangeLog</a></li>
<li><a href="#releasesWebKitGTKwebkit24SourceWTFwtfAtomicsh">releases/WebKitGTK/webkit-2.4/Source/WTF/wtf/Atomics.h</a></li>
</ul>
<h3>Added Paths</h3>
<ul>
<li><a href="#releasesWebKitGTKwebkit24SourceJavaScriptCoreAPItestsCompareAndSwapTestcpp">releases/WebKitGTK/webkit-2.4/Source/JavaScriptCore/API/tests/CompareAndSwapTest.cpp</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="releasesWebKitGTKwebkit24SourceJavaScriptCoreAPItestsCompareAndSwapTestcpp"></a>
<div class="addfile"><h4>Added: releases/WebKitGTK/webkit-2.4/Source/JavaScriptCore/API/tests/CompareAndSwapTest.cpp (0 => 184462)</h4>
<pre class="diff"><span>
<span class="info">--- releases/WebKitGTK/webkit-2.4/Source/JavaScriptCore/API/tests/CompareAndSwapTest.cpp (rev 0)
+++ releases/WebKitGTK/webkit-2.4/Source/JavaScriptCore/API/tests/CompareAndSwapTest.cpp 2015-05-18 12:02:56 UTC (rev 184462)
</span><span class="lines">@@ -0,0 +1,118 @@
</span><ins>+/*
+ * Copyright (C) 2015 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
+ * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
+ * THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "config.h"
+
+#include <stdio.h>
+#include <thread>
+#include <wtf/Atomics.h>
+
+// Regression test for webkit.org/b/142513
+extern "C" void testCompareAndSwap();
+
+class Bitmap {
+public:
+ Bitmap() { clearAll(); }
+
+ inline void clearAll();
+ inline bool concurrentTestAndSet(size_t n);
+ inline size_t numBits() const { return words * wordSize; }
+
+private:
+ static const size_t Size = 4096*10;
+
+ static const unsigned wordSize = sizeof(uint8_t) * 8;
+ static const unsigned words = (Size + wordSize - 1) / wordSize;
+ static const uint8_t one = 1;
+
+ uint8_t bits[words];
+};
+
+inline void Bitmap::clearAll()
+{
+ memset(&bits, 0, sizeof(bits));
+}
+
+inline bool Bitmap::concurrentTestAndSet(size_t n)
+{
+ uint8_t mask = one << (n % wordSize);
+ size_t index = n / wordSize;
+ uint8_t* wordPtr = &bits[index];
+ uint8_t oldValue;
+ do {
+ oldValue = *wordPtr;
+ if (oldValue & mask)
+ return true;
+ } while (!WTF::weakCompareAndSwap(wordPtr, oldValue, oldValue | mask));
+ return false;
+}
+
+struct Data {
+ Bitmap* bitmap;
+ int id;
+ int numThreads;
+};
+
+static void* setBitThreadFunc(void* p)
+{
+ Data* data = reinterpret_cast<Data*>(p);
+ Bitmap* bitmap = data->bitmap;
+ size_t numBits = bitmap->numBits();
+
+ // The computed start index here is heuristic that seems to maximize (anecdotally)
+ // the chance for the CAS issue to manifest.
+ size_t start = (numBits * (data->numThreads - data->id)) / data->numThreads;
+
+ printf(" started Thread %d\n", data->id);
+ for (size_t i = start; i < numBits; i++)
+ while (!bitmap->concurrentTestAndSet(i)) { }
+ for (size_t i = 0; i < start; i++)
+ while (!bitmap->concurrentTestAndSet(i)) { }
+
+ printf(" finished Thread %d\n", data->id);
+ pthread_exit(nullptr);
+}
+
+void testCompareAndSwap()
+{
+ Bitmap bitmap;
+ const int numThreads = 5;
+ pthread_t threadIDs[numThreads];
+ Data data[numThreads];
+
+ printf("Starting %d threads for CompareAndSwap test. Test should complete without hanging.\n", numThreads);
+ for (int i = 0; i < numThreads; i++) {
+ data[i].bitmap = &bitmap;
+ data[i].id = i;
+ data[i].numThreads = numThreads;
+ pthread_create(&threadIDs[i], 0, &setBitThreadFunc, &data[i]);
+ }
+
+ printf("Waiting for %d threads to join\n", numThreads);
+ for (int i = 0; i < numThreads; i++)
+ pthread_join(threadIDs[i], nullptr);
+
+ printf("PASS: CompareAndSwap test completed without a hang\n");
+}
</ins></span></pre></div>
<a id="releasesWebKitGTKwebkit24SourceJavaScriptCoreAPIteststestapic"></a>
<div class="modfile"><h4>Modified: releases/WebKitGTK/webkit-2.4/Source/JavaScriptCore/API/tests/testapi.c (184461 => 184462)</h4>
<pre class="diff"><span>
<span class="info">--- releases/WebKitGTK/webkit-2.4/Source/JavaScriptCore/API/tests/testapi.c 2015-05-18 11:29:26 UTC (rev 184461)
+++ releases/WebKitGTK/webkit-2.4/Source/JavaScriptCore/API/tests/testapi.c 2015-05-18 12:02:56 UTC (rev 184462)
</span><span class="lines">@@ -46,6 +46,7 @@
</span><span class="cx"> #if JSC_OBJC_API_ENABLED
</span><span class="cx"> void testObjectiveCAPI(void);
</span><span class="cx"> #endif
</span><ins>+void testCompareAndSwap();
</ins><span class="cx">
</span><span class="cx"> extern void JSSynchronousGarbageCollectForDebugging(JSContextRef);
</span><span class="cx">
</span><span class="lines">@@ -1174,6 +1175,8 @@
</span><span class="cx"> ::SetErrorMode(0);
</span><span class="cx"> #endif
</span><span class="cx">
</span><ins>+ testCompareAndSwap();
+
</ins><span class="cx"> #if JSC_OBJC_API_ENABLED
</span><span class="cx"> testObjectiveCAPI();
</span><span class="cx"> #endif
</span></span></pre></div>
<a id="releasesWebKitGTKwebkit24SourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: releases/WebKitGTK/webkit-2.4/Source/JavaScriptCore/ChangeLog (184461 => 184462)</h4>
<pre class="diff"><span>
<span class="info">--- releases/WebKitGTK/webkit-2.4/Source/JavaScriptCore/ChangeLog 2015-05-18 11:29:26 UTC (rev 184461)
+++ releases/WebKitGTK/webkit-2.4/Source/JavaScriptCore/ChangeLog 2015-05-18 12:02:56 UTC (rev 184462)
</span><span class="lines">@@ -1,3 +1,26 @@
</span><ins>+2015-03-09 Mark Lam <mark.lam@apple.com>
+
+ 8-bit version of weakCompareAndSwap() can cause an infinite loop.
+ https://webkit.org/b/142513>
+
+ Reviewed by Filip Pizlo.
+
+ 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):
+ * JavaScriptCore.vcxproj/testapi/testapi.vcxproj:
+ * JavaScriptCore.vcxproj/testapi/testapi.vcxproj.filters:
+ * JavaScriptCore.xcodeproj/project.pbxproj:
+
</ins><span class="cx"> 2014-12-04 Oliver Hunt <oliver@apple.com>
</span><span class="cx">
</span><span class="cx"> Serialization of MapData object provides unsafe access to internal types
</span></span></pre></div>
<a id="releasesWebKitGTKwebkit24SourceWTFChangeLog"></a>
<div class="modfile"><h4>Modified: releases/WebKitGTK/webkit-2.4/Source/WTF/ChangeLog (184461 => 184462)</h4>
<pre class="diff"><span>
<span class="info">--- releases/WebKitGTK/webkit-2.4/Source/WTF/ChangeLog 2015-05-18 11:29:26 UTC (rev 184461)
+++ releases/WebKitGTK/webkit-2.4/Source/WTF/ChangeLog 2015-05-18 12:02:56 UTC (rev 184462)
</span><span class="lines">@@ -1,3 +1,37 @@
</span><ins>+2015-03-09 Mark Lam <mark.lam@apple.com>
+
+ 8-bit version of weakCompareAndSwap() can cause an infinite loop.
+ https://webkit.org/b/142513>
+
+ Reviewed by Filip Pizlo.
+
+ 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):
+
</ins><span class="cx"> 2014-10-22 Byungseon Shin <sun.shin@lge.com>
</span><span class="cx">
</span><span class="cx"> String(new Date(Mar 30 2014 01:00:00)) is wrong in CET
</span></span></pre></div>
<a id="releasesWebKitGTKwebkit24SourceWTFwtfAtomicsh"></a>
<div class="modfile"><h4>Modified: releases/WebKitGTK/webkit-2.4/Source/WTF/wtf/Atomics.h (184461 => 184462)</h4>
<pre class="diff"><span>
<span class="info">--- releases/WebKitGTK/webkit-2.4/Source/WTF/wtf/Atomics.h 2015-05-18 11:29:26 UTC (rev 184461)
+++ releases/WebKitGTK/webkit-2.4/Source/WTF/wtf/Atomics.h 2015-05-18 12:02:56 UTC (rev 184462)
</span><span class="lines">@@ -292,16 +292,24 @@
</span><span class="cx"> unsigned* alignedLocation = bitwise_cast<unsigned*>(alignedLocationValue);
</span><span class="cx"> // Make sure that this load is always issued and never optimized away.
</span><span class="cx"> unsigned oldAlignedValue = *const_cast<volatile unsigned*>(alignedLocation);
</span><del>- union {
- uint8_t bytes[sizeof(unsigned)];
- unsigned word;
- } u;
- u.word = oldAlignedValue;
- if (u.bytes[locationOffset] != expected)
- return false;
- u.bytes[locationOffset] = newValue;
- unsigned newAlignedValue = u.word;
- return weakCompareAndSwap(alignedLocation, oldAlignedValue, newAlignedValue);
</del><ins>+
+ struct Splicer {
+ static unsigned splice(unsigned value, uint8_t byte, uintptr_t byteIndex)
+ {
+ union {
+ unsigned word;
+ uint8_t bytes[sizeof(unsigned)];
+ } u;
+ u.word = value;
+ u.bytes[byteIndex] = byte;
+ return u.word;
+ }
+ };
+
+ unsigned expectedAlignedValue = Splicer::splice(oldAlignedValue, expected, locationOffset);
+ unsigned newAlignedValue = Splicer::splice(oldAlignedValue, newValue, locationOffset);
+
+ return weakCompareAndSwap(alignedLocation, expectedAlignedValue, newAlignedValue);
</ins><span class="cx"> #endif
</span><span class="cx"> #else
</span><span class="cx"> UNUSED_PARAM(location);
</span></span></pre>
</div>
</div>
</body>
</html>