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

David Holmes david.holmes at oracle.com
Fri Jul 15 03:16:25 UTC 2016


Hi John,

On 15/07/2016 12:09 PM, John Rose wrote:
> I think we are missing an important opportunity by not supporting single-bit RMW operations in VarHandles.
>
> In particular, the x86 "bts" (bit-test-and-test) "btr" (bit-test-and-reset) and "btc" (bit-test-and-clear) are sometimes the right way to modify some data structure, when the alternative is a load and "cmpxchg" in a loop.  The overall costs are probably the same in the best case, but the loop-based idiom has some danger (relative to the single-instruction idiom) of costs stemming from larger code size.

Is this readily supported on non-x86?

David
-----

> At the JIT level, one can hope that the CAS-based idiom (coded in the current VH API) will be recognized and optimized to a single instruction on x86, but there is a strong risk that this will fail.  It's safer to specify the operation explicitly using a separate VH method.
>
> The particular use case I have in mind is SeqLocks, specifically the writer-enter operation, which needs to change the lock state to "odd", unless it is already "odd", and let the processor know what happened.  An "xadd" cannot do this, but a "cmpxchg" or "bts" can, and the "bts" is preferable.
>
> (In a rather deep sense, getAndAdd is less powerful than testAndSetBit or getAndBitwiseOr,
> because op+ is bijective in each argument, while op| is idempotent.  This means that
> you can operate bitwise on a structure in such a way that your operation disappears
> when the structure is already in some state you are pushing it towards.  Of course,
> you also need a way to "exchange" in the previous value, atomically.)
>
> For a parallel discussion among the gcc folk, where they are working on pattern matching
> of CAS to BTS, see:
>   https://gcc.gnu.org/bugzilla/show_bug.cgi?id=49244
>
> So, here is a specific proposal:
>   https://bugs.openjdk.java.net/browse/JDK-8161444
>   VarHandles should provide access bitwise atomics
>
> In a nutshell, testAndSetBitAcquire behaves as if it were built on top of
> compareAndExchangeAcquire (which it may on some platforms).
> The outgoing value parameter is not a value but a bit position within
> the memory value (zero = LSB, range-checked).  On x86 it compiles
> to "lock;bts" with appropriate fencing.  It is a great candidate for
> building a mutex-enter operation.
>
> For symmetry, I'm also proposing testAndClearBitRelease (or should it
> also be Acquire?) and flipAndGetBit (with Volatile ordering since it is likely
> to be stand-alone).  But it's just symmetry; testAndSetBitAcquire is the
> important part.
>
> What do folks think?  Is "lock;bts" useless for some reason?  (Note that
> the lock prefix is interpreted by modern x86's as a cache transaction
> request, just like xadd, with no external signal.)  Or are there no significant
> single-bit concurrent structures out there?  I know of two:  SeqLocks and
> AtomicMarkableReference (if/when the JVM embraces it).
>
> More background: The SeqLocks are likely to be important for value types
> (when they are too large for native hardware atomics, and must be accessed
> atomically).  Note that many uncontended value types will still need to be used
> with SeqLocks, when structure-tearing must be prevented for one reason
> or another.
>
> (Yet more background:  Non-tearability can be demanded by a value type's definition.
> If this were not possible, values could not embody invariants that affect security.)
>
> Thanks,
> — John
>
> P.S.  For the record here are the important spec. details:
>
> /**
> * Atomically loads the bit at the specified {@code index} in a variable with
> * the memory semantics of {@link #getAcquire}; if the bit is clear,
> * sets it with the memory semantics of {@link #set}; and finally returns
> * the original bit value as a boolean.
> *
> * <p>The variable may be of any primitive type.
> * Bits are numbered from zero, which refers to the arithmetically
> * least-significant bit, to {@code N-1} inclusive, where {@code N} is
> * the number of bits in the variable. Booleans have exactly one bit,
> * while other variables have an appropriate multiple of eight bits.
> *
> * <p>The method signature is of the form {@code (CT, int index)boolean}.
> *
> * <p>The symbolic type descriptor at the call site of {@code testAndSetBitAcquire}
> * must match the access mode type that is the result of calling
> * {@code accessModeType(VarHandle.AccessMode.TEST_AND_SET_BIT_ACQUIRE)} on this
> * VarHandle.
> *
> * @implNote The effects of this method are similar to a call to
> * {@code get} and {@code compareAndExchangeAcquire}, where the new
> * value is obtained from the old value by setting the specified bit.
> * The full effect of {@code testAndSetBitAcquire} would be obtained
> * by retrying the sequence as needed until the bit is either observed
> * to be set, or updated to be set. More efficient implementations may
> * be available on some platforms.
> *
> * @param args the signature-polymorphic parameter list of the form
> * {@code (CT, int index)}
> * , statically represented using varargs.
> * @return a boolean, the original value of the bit (before any update)
> * , statically represented using {@code Object}.
> * @throws UnsupportedOperationException if the access mode is unsupported
> * for this VarHandle.
> * @throws WrongMethodTypeException if the access mode type is not
> * compatible with the caller's symbolic type descriptor.
> * @throws ClassCastException if the access mode type is compatible with the
> * caller's symbolic type descriptor, but a reference cast fails.
> * @throws ClassCastException if the access mode type is compatible with the
> * caller's symbolic type descriptor, but a reference cast fails.
> * @throws IllegalArgumentException if the supplied index is not in the range
> * of zero (inclusive) to the number of bits in the variable (exclusive).
> * @see #getAcquire(Object...)
> * @see #set(Object...)
> * @see #compareAndExchangeAcquire(Object...)
> */
> public final native
> @MethodHandle.PolymorphicSignature
> @HotSpotIntrinsicCandidate
> Object testAndSetBitAcquire(Object... args);
>


More information about the jmm-dev mailing list