RE: [PATCH] refcount_t: documentation for memory ordering differences

From: Reshetova, Elena
Date: Tue Nov 07 2017 - 03:50:54 EST



Hi Randy,

Thank you for your corrections! I will fix the language-related issues in the
next version. More on content below.

> On 11/06/2017 05:32 AM, Elena Reshetova wrote:
> > Some functions from refcount_t API provide different
> > memory ordering guarantees that their atomic counterparts.
> > This adds a document outlining the differences and
> > showing examples.
> >
> > Signed-off-by: Elena Reshetova <elena.reshetova@xxxxxxxxx>
> > ---
> > Documentation/refcount-vs-atomic.txt | 234
> +++++++++++++++++++++++++++++++++++
> > 1 file changed, 234 insertions(+)
> > create mode 100644 Documentation/refcount-vs-atomic.txt
> >
> > diff --git a/Documentation/refcount-vs-atomic.txt b/Documentation/refcount-vs-
> atomic.txt
> > new file mode 100644
> > index 0000000..09efd2b
> > --- /dev/null
> > +++ b/Documentation/refcount-vs-atomic.txt
> > @@ -0,0 +1,234 @@
> > +==================================
> > +refcount_t API compare to atomic_t
> > +==================================
> > +
> > +The goal of refcount_t API is to provide a minimal API for implementing
> > +object's reference counters. While a generic architecture-independent
> > +implementation from lib/refcount.c uses atomic operations underneath,
> > +there is a number of differences between some of the refcount_*() and
>
> there are
>
> > +atomic_*() functions with regards to the memory ordering guarantees.
> > +This document outlines the differences and provides respective examples
> > +in order to help maintainers validate their code against the change in
> > +these memory ordering guarantees.
> > +
> > +memory-barriers.txt and atomic_t.txt provide more background to the
> > +memory ordering in general and for atomic operations specifically.
> > +
> > +Summary of the differences
> > +==========================
> > +
> > + 1) There is no difference between respective non-RMW ops, i.e.
> > + refcount_set() & refcount_read() have exactly the same ordering
> > + guarantees (meaning fully unordered) as atomic_set() and atomic_read().
> > + 2) For the increment-based ops that return no value (namely
> > + refcount_inc() & refcount_add()) memory ordering guarantees are
> > + exactly the same (meaning fully unordered) as respective atomic
> > + functions (atomic_inc() & atomic_add()).
> > + 3) For the decrement-based ops that return no value (namely
> > + refcount_dec()) memory ordering guarantees are slightly
> > + stronger than respective atomic counterpart (atomic_dec()).
> > + While atomic_dec() is fully unordered, refcount_dec() does
> > + provide a RELEASE memory ordering guarantee (see next section).
> > + 4) For the rest of increment-based RMW ops (refcount_inc_not_zero(),
> > + refcount_add_not_zero()) the memory ordering guarantees are relaxed
> > + compare to their atomic counterparts (atomic_inc_not_zero()).
>
> compared
>
> > + Refcount variants provide no memory ordering guarantees apart from
> > + control dependency on success, while atomics provide a full memory
>
> provide full memory
>
> > + ordering guarantees (see next section).
> > + 5) The rest of decrement-based RMW ops (refcount_dec_and_test(),
> > + refcount_sub_and_test(), refcount_dec_if_one(), refcount_dec_not_one())
> > + provide only RELEASE memory ordering and control dependency on success
> > + (see next section). The respective atomic counterparts
> > + (atomic_dec_and_test(), atomic_sub_and_test()) provide full memory ordering.
> > + 6) The lock-based RMW ops (refcount_dec_and_lock() &
> > + refcount_dec_and_mutex_lock()) alway provide RELEASE memory ordering
> > + and ACQUIRE memory ordering & control dependency on success
> > + (see next section). The respective atomic counterparts
> > + (atomic_dec_and_lock() & atomic_dec_and_mutex_lock())
> > + provide full memory ordering.
> > +
> > +
> > +
> > +Details and examples
> > +====================
> > +
> > +Here we consider the cases 3)-6) that do present differences together
> > +with respective examples.
> > +
> > +case 3) - decrement-based RMW ops that return no value
> > +------------------------------------------------------
> > +
> > +Function changes:
> > + atomic_dec() --> refcount_dec()
> > +
> > +Memory ordering guarantee changes:
> > + fully unordered --> RELEASE ordering
> > +
> > +RELEASE ordering guarantees that prior loads and stores are
> > +completed before the operation. Implemented using smp_store_release().
> > +
> > +Examples:
> > +~~~~~~~~~
> > +
> > +For fully unordered operations stores to a, b and c can
> > +happen in any sequence:
> > +
> > +P0(int *a, int *b, int *c)
> > + {
> > + WRITE_ONCE(*a, 1);
> > + WRITE_ONCE(*b, 1);
> > + WRITE_ONCE(*c, 1);
> > + }
> > +
> > +
> > +For a RELEASE ordered operation, read and write from/to @a
>
> read or write (??)
>
> > +is guaranteed to happen before store to @b. There are no
>
> If you want to keep "read and write" above, please change "is" to "are".

I think I also didn't add a "read" in the example, thank you for pointing out,
will fix.

>
> Are "write" and "store" the same? They seem to be used interchangeably.

Yes, "write" and "store" is the same thing, maybe I should indeed stick to just one
way of presenting it not to confuse anyone.

>
> > +guarantees on the order of store/read to/from @c:
> > +
> > +P0(int *a, int *b, int *c)
> > + {
> > + READ_ONCE(*a);
> > + WRITE_ONCE(*a, 1);
> > + smp_store_release(b, 1);
> > + WRITE_ONCE(*c, 1);
> > + READ_ONCE(*c);
> > + }
> > +
> > +
> > +case 4) - increment-based RMW ops that return a value
> > +-----------------------------------------------------
> > +
> > +Function changes:
> > + atomic_inc_not_zero() --> refcount_inc_not_zero()
> > + no atomic counterpart --> refcount_add_not_zero()
> > +
> > +Memory ordering guarantees changes:
> > + fully ordered --> control dependency on success for stores
> > +
> > +Control dependency on success guarantees that if a reference for an
> > +object was successfully obtained (reference counter increment or
> > +addition happened, functions returned true), then further stores are ordered
> > +against this operation. Control dependency on stores are not implemented
> > +using any explicit barriers, but we rely on CPU not to speculate on stores.
> > +
> > +*Note*: we really assume here that necessary ordering is provided as a result
> > +of obtaining pointer to the object!
> > +
> > +Examples:
> > +~~~~~~~~~
> > +
> > +For a fully ordered atomic operation smp_mb() barriers are inserted before
> > +and after the actual operation:
> > +
> > +P0(int *a, int *b, int *c)
> > + {
> > + WRITE_ONCE(*b, 2);
> > + READ_ONCE(*c);
> > + if ( ({ smp_mb(); ret = do_atomic_inc_not_zero(*a); smp_mb(); ret }) ) {
> > + safely_perform_operation_on_object_protected_by_@a();
> > + ...
> > + }
> > + WRITE_ONCE(*c, 2);
> > + READ_ONCE(*b);
> > + }
>
> fix indentation above? or is it meant to be funky?

Ups, wasn't funky when I sent it, will check my editor settings.

>
> > +
> > +These barriers guarantee that all prior loads and stores (@b and @c)
> > +are completed before the operation, as well as all later loads and
> > +stores (@b and @c) are completed after the operation.
> > +
> > +For a fully unordered refcount operation smp_mb() barriers are absent
> > +and only control dependency on stores is guaranteed:
>
> are
>
> > +
> > +P0(int *a, int *b, int *c)
> > + {
> > + WRITE_ONCE(*b, 2);
> > + READ_ONCE(*c);
> > + if ( ({ ret = do_refcount_inc_not_zero(*a); ret }) ) {
> > + perform_store_operation_on_object_protected_by_@a();
> > + /* here we assume that necessary ordering is provided
> > + * using other means, such as locks etc. */
> > + ...
> > + }
> > + WRITE_ONCE(*c, 2);
> > + READ_ONCE(*b);
> > + }
>
> indentation?

Will fix.

>
> > +
> > +No guarantees on order of stores and loads to/from @b and @c.
> > +
> > +
> > +case 5) - decrement-based RMW ops that return a value
> > +-----------------------------------------------------
> > +
> > +Function changes:
> > + atomic_dec_and_test() --> refcount_dec_and_test()
> > + atomic_sub_and_test() --> refcount_sub_and_test()
> > + no atomic counterpart --> refcount_dec_if_one()
> > + atomic_add_unless(&var, -1, 1) --> refcount_dec_not_one(&var)
> > +
> > +Memory ordering guarantees changes:
> > + fully ordered --> RELEASE ordering + control dependency on success for
> stores
> > +
> > +Note: atomic_add_unless() only provides full order on success.
> > +
> > +Examples:
> > +~~~~~~~~~
> > +
> > +For a fully ordered atomic operation smp_mb() barriers are inserted before
> > +and after the actual operation:
> > +
> > +P0(int *a, int *b, int *c)
> > + {
> > + WRITE_ONCE(*b, 2);
> > + READ_ONCE(*c);
> > + if ( ({ smp_mb(); ret = do_atomic_dec_and_test(*a); smp_mb(); ret }) ) {
> > + safely_free_the_object_protected_by_@a();
> > + ...
> > + }
> > + WRITE_ONCE(*c, 2);
> > + READ_ONCE(*b);
> > + }
>
> indentation?

Yes.

>
> > +
> > +These barriers guarantee that all prior loads and stores (@b and @c)
> > +are completed before the operation, as well as all later loads and
> > +stores (@b and @c) are completed after the operation.
> > +
> > +
> > +P0(int *a, int *b, int *c)
> > + {
> > + WRITE_ONCE(*b, 2);
> > + READ_ONCE(*c);
> > + if ( ({ smp_store_release(*a); ret = do_refcount_dec_and_test(*a); ret }) ) {
> > + safely_free_the_object_protected_by_@a();
> > + /* here we know that this is 1 --> 0 transition
> > + * and therefore we are the last user of this object
> > + * so no concurrency issues are present */
> > + ...
> > + }
> > + WRITE_ONCE(*c, 2);
> > + READ_ONCE(*b);
> > + }
>
> odd indentation intended?

Nowhere intended, will fix.

>
> > +
> > +Here smp_store_release() guarantees that a store to @b and read
> > +from @c happens before the operation. However, there is no
>
> happen
>
> > +guarantee on the order of store to @c and read to @b following
> > +the if cause.
>
> clause (?)

Yes, all typos, thank you very much for the proof reading!
I will wait for more people feedback before sending a new v
corrected version since I think there is probably more to fix in examples.

Best Regards,
Elena.
>
> > +
> > +
> > +case 6) - lock-based RMW
> > +------------------------
> > +
> > +Function changes:
> > +
> > + atomic_dec_and_lock() --> refcount_dec_and_lock()
> > + atomic_dec_and_mutex_lock() --> refcount_dec_and_mutex_lock()
> > +
> > +Memory ordering guarantees changes:
> > + fully ordered --> RELEASE ordering always, and on success ACQUIRE
> > + ordering & control dependency for stores
> > +
> > +
> > +ACQUIRE ordering guarantees that loads and stores issued after the ACQUIRE
> > +operation are completed after the operation. In this case implemented
> > +using spin_lock().
> > +
> > +
> >
>
>
> --
> ~Randy