RFR: 8213415: BitMap::word_index_round_up overflow problems

[Kim Barrett]

> On Jun 10, 2019, at 5:34 AM, Stefan Karlsson <stefan.karlsson at oracle.com> wrote:

Thanks for looking at this.

> 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?

Good point.  Done.

> ----------
> 
> +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)

[Clipped the “more below”]

Your comments made me rethink some things, some of which I'd not been
entirely happy with anyway.

verify_max_size_limited is now called verify_valid_size, and is only
used for sizes, not for range boundaries.

word_index_round_up has been entirely eliminated.  Instead, there is
a new internal API used by the range operations: range_begin_align_up,
range_end_align_down, with is_small_range_of_words replaced by
is_small_aligned_range.  This required some fairly mechanical updates
to the implementations of the large range operations.  Fortunately,
there are already gtests in this area, from JDK-8211926.

I think this tidies things up quite a bit, and hope it addresses your issues.

Looking at this also reminded me of some discussion from JDK-8211926
that apparently nobody got around to filing REFs for, so I've done that.

JDK-8225546 Cleanup BitMap index types
JDK-8225547 Improve BitMap large range handling

> 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.

I made this change because I found the old code confusing; I had to
think about it to decide it really would assert iff the range was
invalid. Also, the old error is confusing since the end of a range is
not an index. (Further checking is required for use as an index.) The
change makes the implementation directly correspond to the definition
of a valid range, e.g. 0 <= begin <= end <= size. (With the negative
case impossible because of an unsigned type.)

new webrevs:
full: http://cr.openjdk.java.net/~kbarrett/8213415/open.01/
incr: http://cr.openjdk.java.net/~kbarrett/8213415/open.01.inc/