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

[Randy Dunlap]

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".

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

> +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?

> +
> +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?

> +
> +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?

> +
> +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?

> +
> +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 (?)

> +
> +
> +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