[jmm-dev] bitwise RMW operators, specifically testAndSetBit/BTS

[John Rose]

On Jul 15, 2016, at 12:17 PM, Doug Lea <dl at cs.oswego.edu> wrote:
> 
> On 07/15/2016 12:27 PM, Doug Lea wrote:
> 
>> ... only the getAndX forms seem useful, with only Volatile
>> and Release orderings. Using the default-volatile RMW convention,
>> this would require 6 methods:
>> 
> 
> John suggests the slightly less weird (and thus better):
>  getAndBitwiseOr, getAndBitwiseAnd,  getAndBitwiseXor
>  getAndBitwiseOrRelease, getAndBitwiseAndRelease, getAndBitwiseXorRelease
> that at least separates the two "And"s.
> 
> And in the spirit of not making another premature triage proposal,
> perhaps these should also include Acquire variants:
> getAndBitwiseOrAcquire, getAndBitwiseAndAcquire, getAndBitwiseXorAcquire
> 
> The implicitly-volatile versions should be useful without implementation
> penalty in the Acquire use cases that come to mind, but perhaps there are
> others. Suggestions welcome.

Thanks.  I withdraw the single-bit proposals!  As you note, there
are plausible ways to express bts/btr with full-width bitwise ops.

(The bitwise ones are my real preference anyway, except for the
unpleasant fact that the most common ISA does not support it.
I thought I was being cleverly practical by proposing the single-bit
versions.!

How should these be aligned with compareAndExchange*?
By that I mean the ordering of reads and writes should documented
as no weaker than as if the thing had been implemented in terms of
some corresponding CAS loop.  (Or is there a better way?)

This raises a question about omitting the store.
Suppose the operation turns out to be a no-op.
This can mean that contention is detected or an idempotent
op has already raced to completion.

In that case, should the op include the Release constraint or not?

Put another way, can a reference implementation include
the marked optimization or not:

int getAndBitwiseOr(Object x, int mask) {
  for (;;) {
    int val0 = get(x); // getPlain
    int val1 = val0 & mask;
    if (val1 == val0)  return val0;  // ALLOW THIS OPTIMIZATION?
    int witness = compareAndExchangeRelease(x, val0, val1);
    if (witness == val0)  return val0;
  }
}

The optimization allows getAndBitwiseOr to take a weaker form,
which is generally desirable.  OTOH, if that is a form known to be
useless or problematic, we shouldn't go there.  The usefulness
would stem from the ability of a thread to detect already-done
or contention conditions with the least overhead.  A weaker form
can be strengthened by adding a fence.  A stronger form can be
weakened by adding additional polling logic, but that is clumsy
and error prone.

— John