RFR: 8287215: Add method to scan bitmap backwards [v3]

[Kim Barrett]

On Wed, 25 May 2022 10:11:51 GMT, Thomas Schatzl <tschatzl at openjdk.org> wrote:

>> Hi all,
>> 
>>   can I have reviews for this change that adds a method to scan bitmaps backwards? This functionality is necessary for upcoming change to remove on of the mark bitmaps [JDK-8210708](https://bugs.openjdk.java.net/browse/JDK-8210708).
>> 
>> As such this is only an addition of that functionality with no reference (apart from the gtest) from Hotspot itself.
>> 
>> Testing: gtest
>> 
>> Thanks,
>>   Thomas
>
> Thomas Schatzl has updated the pull request incrementally with one additional commit since the last revision:
> 
>   Minor simplification

Changes requested by kbarrett (Reviewer).

src/hotspot/share/utilities/bitMap.hpp line 327:

> 325:   static constexpr idx_t NotFound = ~(idx_t)0;
> 326:   // Find the index of the first bit set scanning from r_index (inclusive) to
> 327:   // l_index (inclusive) backwards.

I don't think r_index should be inclusive.  I think that's surprising (such
ranges are usually half-open, and always so elsewhere in this class).  (It
caught me by surprise; I failed to notice that in the doc and was quite
confused when reviewing the implementation until I realized what was going
on.)  I also think it makes these operations harder to use. Having a closed
range forces the caller to deal with the unrepresentable empty range
explicitly.  A common use-case for such searches is to iterate over the bits;
the inclusive r_index makes that more awkward for the caller.  Obviously this
affects everything else in this change, so I haven't looked at the code very
much yet.

src/hotspot/share/utilities/bitMap.hpp line 328:

> 326:   // Find the index of the first bit set scanning from r_index (inclusive) to
> 327:   // l_index (inclusive) backwards.
> 328:   // Returns that index or NotFound if there is no such bit in the range.

I think that, for consistency, it might be good for the forward search to also
return NotFound when appropriate. That's something that should be done as a
followup though, I think.

src/hotspot/share/utilities/bitMap.inline.hpp line 236:

> 234:   verify_range(l_index, r_index);
> 235:   assert(!aligned_left || is_aligned(l_index, BitsPerWord), "l_index not aligned");
> 236:   assert(sizeof(intptr_t) == sizeof(bm_word_t), "must be for the high bit check");

This assert of size equality should be a static assert.  Also, I'd prefer it was close to the place that "uses" the information.

src/hotspot/share/utilities/bitMap.inline.hpp line 249:

> 247:   // The return value of l_index when no bit is found is BitMap::NotFound.
> 248: 
> 249:   if (l_index <= r_index) {

This condition is always true if the `verify_range` precondition is met.  This is an artifact of making `r_index` inclusive rather than exclusive.

-------------

PR: https://git.openjdk.java.net/jdk/pull/8869