RFR: 8213415: BitMap::word_index_round_up overflow problems

[Stefan Karlsson]

http://cr.openjdk.java.net/~kbarrett/8213415/open.00/src/hotspot/share/utilities/bitMap.cpp.udiff.html

  template <class Allocator>
  BitMap::bm_word_t* BitMap::reallocate(const Allocator& allocator, 
bm_word_t* old_map, idx_t old_size_in_bits, idx_t new_size_in_bits, bool 
clear) {
+  verify_max_size_limited(new_size_in_bits);
    size_t old_size_in_words = calc_size_in_words(old_size_in_bits);
    size_t new_size_in_words = calc_size_in_words(new_size_in_bits);

calc_size_in_words also calls verify_max_size_limited, so maybe skip 
adding it here?

----------

+void BitMap::verify_max_size_limited(idx_t bit) {
+  assert(bit <= max_size_in_bits(), "out of bounds: " SIZE_FORMAT, bit);
+}

Is the intention to verify that a 'size' is less than or equal to the 
'max possible size'? If that's the case, then I think it would be better 
to use the name size_in_bits. Just like we do for our constructors, 
allocators, and initializers.

Or is this actually meant to check that bit indices are within the max 
range? If that's the case, then why are we using <= instead of < ?

(More about this below)

----------

  void BitMap::verify_range(idx_t beg_index, idx_t end_index) const {
    assert(beg_index <= end_index, "BitMap range error");
    // Note that [0,0) and [size,size) are both valid ranges.
-  if (end_index != _size) verify_index(end_index);
+  assert(end_index <= _size, "BitMap range out of bounds");
  }

This allowance to have beg_index outside of the bit range seems dubious 
to me. It's not something you changed, but I preferred that the old code 
was explicit that there was an odd special case involved.

==========
http://cr.openjdk.java.net/~kbarrett/8213415/open.00/src/hotspot/share/utilities/bitMap.cpp.udiff.html

  inline BitMap::idx_t BitMap::word_index_round_up(idx_t bit) const {
-  idx_t bit_rounded_up = bit + (BitsPerWord - 1);
-  // Check for integer arithmetic overflow.
-  return bit_rounded_up > bit ? word_index(bit_rounded_up) : 
size_in_words();
+  return calc_size_in_words(bit);
  }

It's not intuitive why word_index_round_up can be implemented with a 
calc_size_in_words call. I now understand why you had the <= check and 
'bit' name in verify_max_size_limited.

I would at least have wanted this check in word_index_round_up:
   assert(bit < max_size_in_bits(), "OOB");

but I fear that it won't work in the cases where
beg' is the argument:

   verify_range(beg, end);

   idx_t beg_full_word = word_index_round_up(beg);
   idx_t end_full_word = word_index(end);


and verify_range accepts a beg outside of the bit range, so 
word_index_round_up could actually be called with an OOB bit.

With that said, could we turn this the other way around?:

BitMap::idx_t BitMap::word_index_round_up(idx_t bit) const {
   assert(bit <= max_size_in_bits(), "OOB");
   return word_index(bit + (BitsPerWord - 1));
}

static idx_t calc_size_in_words(idx_t size_in_bits) {
   return word_index_round_up(size_in_bits);
}

It's almost what the code used to look like:

-  static idx_t calc_size_in_words(size_t size_in_bits) {
-    return word_index(size_in_bits + BitsPerWord - 1);
-  }

Thanks,
StefanK

On 2019-05-28 20:10, Kim Barrett wrote:
> Please review this change to BitMap index alignment to check for
> overflows (in debug builds).  Also made a few related API cleanups.
> 
> Constructing a BitMap now ensures the size is such that rounding it up
> to a word boundary won't overflow.  This is the new max_size_in_bits()
> value. This lets us add some asserts and otherwise tidy things up in
> some places by making use of that information.
> 
> This engendered some changes to ParallelGC's ParMarkBitMap.  It no
> longer uses the obsolete BitMap::word_align_up, instead having its own
> internal helper for aligning range ends that knows about invariants in
> ParMarkBitMap.
> 
> Removed the following static functions from BitMap: word_align_up,
> word_align_down, and is_word_aligned.  word_align_up is no longer
> used, after the ParMarkBitMap changes.  The others were only used in a
> small number of places in tests and asserts, and didn't seem worth
> keeping instead of just using align.hpp stuff with BitsPerWord
> alignment value.
> 
> CR:
> https://bugs.openjdk.java.net/browse/JDK-8213415
> 
> Webrev:
> http://cr.openjdk.java.net/~kbarrett/8213415/open.00/
> 
> Testing:
> mach5 tier1-3
>