RFR: 8213415: BitMap::word_index_round_up overflow problems

[Thomas Stüfe]

Hi Kim,

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

+  // Limit max_size_in_bits so aligning up to a word never overflows.
+  static idx_t max_size_in_words() { return
raw_to_words_align_down(~idx_t(0)); }
+  static idx_t max_size_in_bits() { return max_size_in_words() *
BitsPerWord; }

Could we have better comments? I first thought that max_size_in_words()
means bitmap size, only the static specifier ticked me off.

So, if I understand this correctly, we need this since we use the same type
for bit and word indices and since we have a n:1 relationship between those
two the max. bit index is necessary smaller than <type>_MAX?

+  // Assumes relevant validity checking for bit has already been done.
+  static idx_t raw_to_words_align_up(idx_t bit) {
+    return raw_to_words_align_down(bit + (BitsPerWord - 1));
+  }

Interestingly, this could break should we ever have different types for
word- and bit indices. Should we ever want to templatize the underlying
types, eg. to support small bitmaps where 8 or 16 bits would be enough to
encode a bitmap index. Then it could make sense to have a larger type for
word indices than for bit indices and we could overflow here.

(Just idle musings.. we have talked about using different types for bit-
and word-indexes before. I have worked on a patch for this, but it got
snowed under by other work. See:
http://cr.openjdk.java.net/~stuefe/webrevs/bitmap-improvements/bitmap-better-types.
What do you think, does this still make sense?)


+
+  // Verify size_in_bits does not exceed maximum size.
+  static void verify_size(idx_t size_in_bits) NOT_DEBUG_RETURN;

"maximum size" is unclear. Can you make the comment more precise?

Also, could this function be private?

+  // Verify bit is less than size.
+  void verify_index(idx_t bit) const NOT_DEBUG_RETURN;
+  // Verify bit is not greater than size.
+  void verify_limit(idx_t bit) const NOT_DEBUG_RETURN;
+  // Verify [beg,end) is a valid range, e.g. beg <= end <= size().
+  void verify_range(idx_t beg, idx_t end) const NOT_DEBUG_RETURN;

I have a bit of a trouble understanding these variants and how they are
used.

I believe to understand that verify_limit() is to verify range sizes, since
the valid range for a size type is always one larger than that for an index
type, right? But it is used to test indices for validity, for example via
to_words_align_down() -> word_addr(). Which would mean for a 64bit sized
bitmap (1 word size) I can feed an invalid "64" as index to word_addr(),
which verify_limit() would accept but would get me the invalid word index
"1". I would have expected word_addr() to only return usable word adresses
and to assert in this case.

I also feel that if I got it right the naming is the wrong way around. I
would have expected "verify_size()" to refer to the bitmap object map size,
and "verify_limit()" to the type limit (similar to limits.h)..

Cheers, Thomas


On Wed, Nov 27, 2019 at 1:41 AM Kim Barrett <kim.barrett at oracle.com> wrote:

> > On Jun 11, 2019, at 12:42 PM, Kim Barrett <kim.barrett at oracle.com>
> wrote:
> >
> >> On Jun 10, 2019, at 9:14 PM, Kim Barrett <kim.barrett at oracle.com>
> wrote:
> >> new webrevs:
> >> full: http://cr.openjdk.java.net/~kbarrett/8213415/open.01/
> >> incr: http://cr.openjdk.java.net/~kbarrett/8213415/open.01.inc/
> >
> > Stefan and I have been talking about this offline.  We have some ideas
> for further changes in
> > a slightly different direction, so no point in anyone else reviewing the
> open.01 changes right now
> > (or maybe ever).
>
> Finally returning to this.  Stefan Karlsson and Thomas Shatzl had some
> offline feedback on earlier versions that led to some rethinking and
> rework.  This included an attempt to be a little more consistent with
> nomenclature.  There are still some lingering naming issues, which
> might be worth fixing some other time.
>
> The basic approach hasn't changed though.  From the original RFR:
>
> 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.
>
> CR:
> https://bugs.openjdk.java.net/browse/JDK-8213415
>
> New webrev:
> http://cr.openjdk.java.net/~kbarrett/8213415/open.03/
> (No incremental webrev; it wouldn't help that much for BitMap changes,
> and there have been several intervening months since the last one.)
>
> Testing:
> mach5 tier1-5
>
>