Undefined behavior ParkingLot.cpp on lockHashtable()

• Component: Web Template Framework
• Status: RESOLVED INVALID

[Jonathan Bedard]

The pattern used by the for loop in this function (i.e.: for(...;i--;)) results in undefined behavior when i reaches 0.

[Jonathan Bedard]

Created attachment 285373 [details]
Patch

[Build Bot]

Comment on attachment 285373 [details]
Patch

Attachment 285373 [details] did not pass mac-ews (mac):
Output: http://webkit-queues.webkit.org/results/1813820

Number of test failures exceeded the failure limit.

[Build Bot]

Created attachment 285378 [details]
Archive of layout-test-results from ews103 for mac-yosemite

The attached test failures were seen while running run-webkit-tests on the mac-ews.
Bot: ews103  Port: mac-yosemite  Platform: Mac OS X 10.10.5

[Build Bot]

Comment on attachment 285373 [details]
Patch

Attachment 285373 [details] did not pass mac-debug-ews (mac):
Output: http://webkit-queues.webkit.org/results/1813813

Number of test failures exceeded the failure limit.

[Build Bot]

Created attachment 285379 [details]
Archive of layout-test-results from ews113 for mac-yosemite

The attached test failures were seen while running run-webkit-tests on the mac-debug-ews.
Bot: ews113  Port: mac-yosemite  Platform: Mac OS X 10.10.5

[Build Bot]

Comment on attachment 285373 [details]
Patch

Attachment 285373 [details] did not pass mac-wk2-ews (mac-wk2):
Output: http://webkit-queues.webkit.org/results/1813823

Number of test failures exceeded the failure limit.

[Build Bot]

Created attachment 285380 [details]
Archive of layout-test-results from ews107 for mac-yosemite-wk2

The attached test failures were seen while running run-webkit-tests on the mac-wk2-ews.
Bot: ews107  Port: mac-yosemite-wk2  Platform: Mac OS X 10.10.5

[Build Bot]

Comment on attachment 285373 [details]
Patch

Attachment 285373 [details] did not pass ios-sim-ews (ios-simulator-wk2):
Output: http://webkit-queues.webkit.org/results/1813819

Number of test failures exceeded the failure limit.

[Build Bot]

Created attachment 285381 [details]
Archive of layout-test-results from ews121 for ios-simulator-wk2

The attached test failures were seen while running run-webkit-tests on the ios-sim-ews.
Bot: ews121  Port: ios-simulator-wk2  Platform: Mac OS X 10.11.5

[Daniel Bates]

Comment on attachment 285373 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=285373&action=review

> Source/WTF/wtf/ParkingLot.cpp:-297
> -        for (unsigned i = currentHashtable->size; i--;) {

Can you explain how this is undefined behavior? Or can you post the compiler warning? By [basic.fundamental] (4) and footnote (46) of the C++ standard (*) "unsigned arithmetic does not overflow":

"Unsigned integers, declared unsigned, shall obey the laws of arithmetic modulo 2^n where n is the number of bits in the value representation of that particular size of integer. [46]"

And the footnote [46] reads "This implies that unsigned arithmetic does not overflow because a result that cannot be represented by the resulting unsigned integer type is reduced modulo the number that is one greater than the largest value that can be represented by the resulting unsigned integer type."

(*) <http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3337.pdf>

> Source/WTF/wtf/ParkingLot.cpp:297
> +        unsigned i = currentHashtable->size+1;

Nit: Missing a space on both sides of the '+'.

[Jonathan Bedard]

First, a minor note to Daniel's nit, it's interesting that the style checker didn't catch that, because it probably should have.

Second, and to address the larger issue brought up by Daniel, further investigation has revealed that this behavior is defined, just 'suspicious' (according to clang).  Due to some local changes I have made and the time it takes to compile clang with the undefined behavior sanitizer flags on, I do not have the exact error.  I do, however, know the format:

<File location and line number>: runtime error: <type> overflow: <operation> cannot be represented in type '<type>'

https://bugs.webkit.org/show_bug.cgi?id=160565 has an example of another unsigned type overflowing.

Some brief digging has revealed that clang is combining some 'suspicious' behaviors with 'undefined' behaviors, and this is a case of 'suspicious' behavior, but, as per C++ 2014 standard 3.9.1, 4, unsigned types overflow with modulo 2^n, which is our desired behavior in this case.  In short, the behavior corrected here is both defined and desired.

Undefined behavior sanitizer information: http://clang.llvm.org/docs/UndefinedBehaviorSanitizer.html

C++ standard:
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4296.pdf

No fix is needed.  Marking as resolved.