Messages in this thread | | | From | "Reshetova, Elena" <> | Subject | RE: [PATCH] refcount_t: documentation for memory ordering differences | Date | Tue, 7 Nov 2017 08:49:08 +0000 |
| |
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@intel.com> > > --- > > 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
| |