RFR: 8233073: Make BitMap accessors more memory ordering friendly

Tue Oct 29 14:59:40 UTC 2019

Hi,

On 10/29/19 2:40 PM, erik.osterlund at oracle.com wrote:
> 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/

Looks good to me. I like the par_at() approach.

/Per

> 
> Incremental:
> http://cr.openjdk.java.net/~eosterlund/8233073/webrev.00_01/
> 
> Thanks,
> /Erik