RFR: 8233073: Make BitMap accessors more memory ordering friendly

[erik.osterlund at oracle.com]

Hi Kim,

On 10/29/19 2:54 AM, Kim Barrett wrote:
> Should this review be happening on hotspot-dev rather than
> hotspot-gc-dev?  GC is not the only BitMap client; compiler uses them
> too (and generally rather differently).

Perhaps. I presumed that the way it is being changed is only interesting 
for GC folks... but I guess that depends on the direction this is going. 
Let's see...

> ------------------------------------------------------------------------------
> src/hotspot/share/utilities/bitMap.hpp
> 207   bool at(idx_t index, atomic_memory_order memory_order = memory_order_relaxed) const;
>
> My initial reaction here is that I'd prefer adding par_at() rather
> than giving at() a memory order argument.  This would also address the
> question of what the default should be.  For at(), it's nonatomic.
> For par_at() it's acquire.
>
> That would also avoid imposing volatile ordering on at().

I like that idea. Let's give that a shot.

> As you said, existing uses of at() are relaxed/nonatomic.  The code
> rearrangement for MarkBitMap::is_marked() makes me wonder if any of
> the calls should be acquire ordered, but obviously none are now...

Yeah, I also wonder about that...

> ------------------------------------------------------------------------------
> src/hotspot/share/utilities/bitMap.hpp
> 205   // The memory ordering goes up to memory_order_acquire, but not higher. It is
> 206   // assumed that users of the BitMap API will never rely on IRIW consistency.
>
> I think what this means is that memory_order_seq_cst
> (memory_order_conservative in HotSpot) isn't supported? So just as we
> only have Atomic::load (relaxed) and Atomic::load_acquire (acquire).
> That seems okay. But if we aren't going to support the stronger
> semantics, I don't think this should permit the corresponding memory
> order value.
>
> C++11 specifies that atomic load operations cannot have a memory order
> of memory_order_release or memory_order_acq_rel. (Similarly, store
> operations cannot have a memory order of memory_order_consume,
> memory_order_acquire, or memory_order_acq_rel. That isn't relevant for
> this change, as all the modifying operations here are RMW.)
>
> So I think we should just be explicit that only relaxed and acquire
> are supported here.  (And actually make that true; see next comment.)
>
> ------------------------------------------------------------------------------
> src/hotspot/share/utilities/bitMap.inline.hpp
>   55 inline bool BitMap::at(idx_t index, atomic_memory_order memory_order) const {
> ...
>   58   return (load_word_ordered(addr, memory_order) & bit_mask(index)) != 0;
>
> This is using the load_word_ordered helper, but the behavior of that
> function is designed to support the RMW operations, and I think isn't
> really right for at() (see previous comment). The simplest solution to
> get what I'm suggesting would be to add an assert here that the
> memory_order is either relaxed or acquire.

That makes sense. I added the assert.

> ------------------------------------------------------------------------------
> src/hotspot/share/gc/shared/markBitMap.inline.hpp
> 71   return _bm.at(addr_to_offset(addr), memory_order_relaxed);
>
> The memory order argument isn't needed with the current default, and
> wouldn't even be permitted with the above suggestion add par_at.

Indeed. Reverted in favor of par_at.

> ------------------------------------------------------------------------------
>
> I'm not understanding part of the problem description though.  You say
>
>    ... have made the uses of this API more conservative for failed bit
>    flips than it was in the past.
>
> But the pre-existing unordered cases in the setting functions (e.g.
> don't go through cmpxchg) are those where the bit is already set to
> the desired value, so there's no failure to change the bit involved.
> It seems reasonable to me that an acquire (at least) is usually
> desirable on that path, for reasons similar to why one wants an
> acquire on the outside-the-lock test when using the Double Checked
> Locking pattern. But that's not what was said, so I'm not sure I'm
> understanding the point.

By failed bit flips, I specifically meant that the bit flipping function 
(par_set_at) returns false. This happens for two reasons: 1) the bit was 
already set in the original (relaxed) load, or 2) a concurrent thread 
beat us to it in the subsequent CAS. So if the function returns false, 
previously you couldn't know if the load that made the function return 
false had acquire semantics or not. Now with this patch it will have 
acquire semantics (unless the whole operation is specified to have 
relaxed or release semantics), even when the original load already had 
the bit set already. That is what I meant made the API more conservative 
than before. And as you say, I think that is a good thing. Hope this 
explains our misunderstanding.

> ------------------------------------------------------------------------------
>
> The par_xxx_range operations are not being directly modified by this
> change. When only 1 bit is actually involved, they'll delegate to the
> conservative single-bit operations, so are changed to pick up the
> acquire on the already set to the desired value path. Otherwise, they
> always go through conservative cmpxchg as before.  That all seems fine.

Yeah.

I made a new patch that reverts at() to do what it used to (in the .hpp 
file), and added a new par_at() accessor instead with explicit memory 
ordering (asserted to be acquire or relaxed), defaulting to acquire, as 
suggested. I left some innocent cleanups of missing includes in the area 
that I would like to keep anyway.

New webrev:
http://cr.openjdk.java.net/~eosterlund/8233073/webrev.01/

Incremental:
http://cr.openjdk.java.net/~eosterlund/8233073/webrev.00_01/

Thanks,
/Erik