RFR (S) 8211926: Catastrophic size_t underflow in BitMap::*_large methods

[Kim Barrett]

> On Nov 8, 2018, at 6:30 PM, Aleksey Shipilev <shade at redhat.com> wrote:
> 
> On 11/08/2018 10:41 PM, Kim Barrett wrote:
>> 
>> ------------------------------------------------------------------------------ 
>> src/hotspot/share/utilities/bitMap.inline.hpp
>> 240   assert(beg <= end, "underflow");
>> 245   assert(beg <= end, "underflow");
>> 
>> These new checks should instead be using verify_range.
> 
> I don't think they should: verify_range operates on bit indexes, and here beg/end are the word
> indexes? While this would always work (famous last words), since word indexes are always below bit
> indexes, this would introduce weird dependency on verify_range with implicitly reintepreted
> arguments. It seems to me to-the-point asserts win here.

Oh, you are right!  Sorry about that.

>> src/hotspot/share/utilities/bitMap.cpp
>> 277   assert(beg_full_word < end_full_word,
>> 278          "Performance: The range includes at least one full word");
>> 
>> 295   assert(beg_full_word < end_full_word,
>> 296          "Performance: The range includes at least one full word");
>> 
>> For either of these assertions to trip, the value of SMALL_RANGE_WORDS
>> would have needed to be poorly chosen.  Better would be a static
>> assertion on the value of SMALL_RANGE_WORDS.
> 
> Or, you can think about it this way: this is a precondition for calling the code below, so it should
> be near the code that needs it, and it should test the exact invariant that we would like to hold
> true. Statically asserting small_range_words runs into risk of missing the errors in conditions
> involving small_range_words. But, I have no energy to fight it, reverted.

I don't have a problem with the check being near the dependent code;
indeed, I think it should be there. Rather, I have problem with the
form of the check.  The check and associated comment you added to
src/hotspot/share/utilities/bitMap.hpp
would be better placed with the dependent code.

> I realized (late) that your suggestion has a much nicer check shape (a + b >= c), adopted.

Yes, that helps; see below.

> 
>> I don't buy the backport argument here.  set_large_range is untouched
>> since the initial mercurial checkin.  The only change since then to
>> clear_large_range is JDK-8152188 (JDK 9), which changed the similar
>> assert there to the potentially underflowing conditional call to
>> set_range that is being addressed here.
> 
> What JDK-8152188 teaches me is that seemingly trivial code had introduced the bug, which we have
> noticed years later. This is why I am resisting rewriting the code any more than necessary, and
> instead willing to point-fix the actual bug, with maybe a little code homogenizing, and provide the
> regression test to make sure the exact bug does not happen anymore. This is my backport argument:
> make the fix as trivial+obvious as possible to avoid introducing more bugs in backports.

The underflow problem existed from the initial mercurial checkin, in
the assert condition.  JDK-8152188 didn't change any behavior in that
underflow case.

I'm also not really a fan of ham-stringing current improvements for
reasons of backporting. But using the better comparison works for me,
so I think your new proposed check is fine. It still suffers from the
(theoretical) potential overflow from JDK-8213415, but that's a
separate issue.

> I believe new patch is as straightforward as it could be, see:
>  http://cr.openjdk.java.net/~shade/8211926/webrev.03/

I was about ready to approve, but took another look at the new test.
Unfortunately, I think it has some problems.

Most importantly, BITMAP_SIZE is too small for the actual large code
to be invoked. With small_range_words being 32, one needs a range size
of 2K bits (on 64bit platforms) to exceed that. And just increasing it
may make this test take an excessive amount of time to run. (I was
already wondering how long it takes, being quadradic in BITMAP_SIZE.)

I think it would be sufficient for l to range from 0 to bit_index(2),
with r ranging from l to BITMAP_SIZE in power of 2 steps, e.g.
something like

  for (idx_t r = l, step = 1; r < BITMAP_SIZE; r += step, step <<= 1) {
    ...
  }

and change BITMAP_SIZE to some multiple of bit_index(small_range_words),
perhaps 3 or 4.  Maybe add a couple edge cases to ensure r hits some
word boundaries.

Also, a style nit for BITMAP_SIZE: HotSpot code generally uses "static
const" rather than "const static" (though there are a small number of
the latter).

I'm not sure the distinction between ResourceBitMap and CHeapBitMap is
really all that interesting for the purpose of this set of tests.

The tests could use TEST rather than TEST_VM if a static buffer were
used for the BitMap storage, rather than using dynamic allocation.
(That's what test_bitMap_search.cpp does. It seems that
test_bitMap_setops.cpp takes yet another tack, using ::malloc.) I
don't object to the current approach, but I think gtests that don't
depend on a functioning VM are preferable where possible and not too
onerous.