Bug ID: JDK-8178348 left_n_bits(0) invokes undefined behavior

Versions (Unresolved/Resolved/Fixed)

The Version table provides details related to the release that this issue/RFE will be addressed.

Unresolved : Release in which this issue/RFE will be addressed.
Resolved: Release in which this issue/RFE has been resolved.
Fixed : Release in which this issue/RFE has been fixed. The release containing this fix may be available for download as an Early Access Release or a General Availability Release.

To download the current JDK release, click here.

JDK 17
17 b14Fixed

The current definition of left_n_bits is

#define left_n_bits(n) \
  (right_n_bits(n) << (((n) >= BitsPerWord) ? 0 : (BitsPerWord - (n))))

When n == 0, this reduces to

  (right_n_bits(0) << BitsPerWord)

According to C++03 5.8/2, the behavior of a shift expression is undefined if the right operand is greater than or equal to the length in bits of the promoted left operand.  So a shift by BitsPerWord invokes undefined behavior.

Changeset: 4b5c664b Author: Harold Seigel <hseigel@openjdk.org> Date: 2021-03-12 19:00:36 +0000 URL: https://git.openjdk.java.net/jdk/commit/4b5c664b
12-03-2021
Maybe we should just delete the left_n_bits macro. It's only used here in .../globalDefinitions.cpp: STATIC_ASSERT(left_n_bits(3) == (intptr_t) LP64_ONLY(0xE000000000000000) NOT_LP64(0xE0000000)); STATIC_ASSERT(left_n_bits(1\|2) == (intptr_t) LP64_ONLY(0xE000000000000000) NOT_LP64(0xE0000000));
10-03-2021
For the case of 0 < n < BitsPerWord, C++14 changed the behavior of left-shift in such a way that the use by left_n_bits is okay, and no longer undefined behavior. The case of n == 0 is still broken, since it produces a shift amount of BitsPerWord, which is always UB. http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_defects.html#1457
29-10-2019
I was able to deal with the BitMap::get_next_zero_offset problem by eliminating the use of left_n_bits (JDK-8178352), rather than by fixing left_n_bits, so deassigning. All of nth_bit, right_n_bits, and left_n_bits have cases that invoke undefined behavior. They, and all the rest of the bitfield manipulation operations, really ought to be dealing with unsigned values rather than signed.
04-05-2017
I've had an actual encounter with this undefined behavior. The new test for BitMap search operations (JDK-8169039) fails in a product build on Macs. I tracked that down to Clang "miscompiling" a call to BitMap::get_next_zero_offset with a constant 0 start offset, due to a use of left_n_bits therein; see JDK-8178352. (I suspect any other constant start offset whose value is 0 mod 64 would be similarly "miscompiled".)
09-04-2017
Note that when n < BitsPerWord, the left shift of the (signed) right_n_bits value is also undefined, due to overflow.
09-04-2017

Relates :	JDK-8233144 - undefined behavior: signed integer overflow
Relates :	JDK-8178352 - BitMap::get_next_zero_offset may give wrong result on Mac
Relates :	JDK-8169039 - Add unit tests for BitMap search operations