Some functions from refcount_t API provide different
memory ordering guarantees that their atomic counterparts.
This adds a document outlining these differences.
Signed-off-by: Elena Reshetova <[email protected]>
---
Documentation/core-api/index.rst | 1 +
Documentation/core-api/refcount-vs-atomic.rst | 129 ++++++++++++++++++++++++++
2 files changed, 130 insertions(+)
create mode 100644 Documentation/core-api/refcount-vs-atomic.rst
diff --git a/Documentation/core-api/index.rst b/Documentation/core-api/index.rst
index d5bbe03..d4d54b0 100644
--- a/Documentation/core-api/index.rst
+++ b/Documentation/core-api/index.rst
@@ -14,6 +14,7 @@ Core utilities
kernel-api
assoc_array
atomic_ops
+ refcount-vs-atomic
cpu_hotplug
local_ops
workqueue
diff --git a/Documentation/core-api/refcount-vs-atomic.rst b/Documentation/core-api/refcount-vs-atomic.rst
new file mode 100644
index 0000000..5619d48
--- /dev/null
+++ b/Documentation/core-api/refcount-vs-atomic.rst
@@ -0,0 +1,129 @@
+===================================
+refcount_t API compared to atomic_t
+===================================
+
+The goal of refcount_t API is to provide a minimal API for implementing
+an object's reference counters. While a generic architecture-independent
+implementation from lib/refcount.c uses atomic operations underneath,
+there are a number of differences between some of the refcount_*() and
+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.
+
+Relevant types of memory ordering
+=================================
+
+**Note**: the following section only covers some of the memory
+ordering types that are relevant for the atomics and reference
+counters and used through this document. For a much broader picture
+please consult memory-barriers.txt document.
+
+In the absence of any memory ordering guarantees (i.e. fully unordered)
+atomics & refcounters only provide atomicity and
+program order (po) relation (on the same CPU). It guarantees that
+each atomic_*() and refcount_*() operation is atomic and instructions
+are executed in program order on a single CPU.
+This is implemented using READ_ONCE()/WRITE_ONCE() and
+compare-and-swap primitives.
+
+A strong (full) memory ordering guarantees that all prior loads and
+stores (all po-earlier instructions) on the same CPU are completed
+before any po-later instruction is executed on the same CPU.
+It also guarantees that all po-earlier stores on the same CPU
+and all propagated stores from other CPUs must propagate to all
+other CPUs before any po-later instruction is executed on the original
+CPU (A-cumulative property). This is implemented using smp_mb().
+
+A RELEASE memory ordering guarantees that all prior loads and
+stores (all po-earlier instructions) on the same CPU are completed
+before the operation. It also guarantees that all po-earlier
+stores on the same CPU and all propagated stores from other CPUs
+must propagate to all other CPUs before the release operation
+(A-cumulative property). This is implemented using smp_store_release().
+
+A control dependency (on success) for refcounters guarantees that
+if a reference for an object was successfully obtained (reference
+counter increment or addition happened, function returned true),
+then further stores are ordered against this operation.
+Control dependency on stores are not implemented using any explicit
+barriers, but rely on CPU not to speculate on stores. This is only
+a single CPU relation and provides no guarantees for other CPUs.
+
+
+Comparison of functions
+=======================
+
+case 1) - non-"Read/Modify/Write" (RMW) ops
+-------------------------------------------
+
+Function changes:
+ atomic_set() --> refcount_set()
+ atomic_read() --> refcount_read()
+
+Memory ordering guarantee changes:
+ none (both fully unordered)
+
+case 2) - increment-based ops that return no value
+--------------------------------------------------
+
+Function changes:
+ atomic_inc() --> refcount_inc()
+ atomic_add() --> refcount_add()
+
+Memory ordering guarantee changes:
+ none (both fully unordered)
+
+
+case 3) - decrement-based RMW ops that return no value
+------------------------------------------------------
+Function changes:
+ atomic_dec() --> refcount_dec()
+
+Memory ordering guarantee changes:
+ fully unordered --> RELEASE ordering
+
+
+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
+
+*Note*: we really assume here that necessary ordering is provided as a result
+of obtaining pointer to the object!
+
+
+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
+
+Note: atomic_add_unless() only provides full order on success.
+
+
+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 + control dependency +
+ hold spin_lock() on success
--
2.7.4
From 1585931737320124763@xxx Tue Dec 05 08:26:05 +0000 2017
X-GM-THRID: 1585863812735308798
X-Gmail-Labels: Inbox,Category Forums,HistoricalUnread
Hi Kees,
Thank you for the proof reading. I will fix the typos/language, but
see the comments on bigger things inside.
> On Tue, Nov 14, 2017 at 11:55 PM, Elena Reshetova
> <[email protected]> wrote:
> > Some functions from refcount_t API provide different
> > memory ordering guarantees that their atomic counterparts.
> > This adds a document outlining these differences.
>
> Thanks for writing this up! One bike-shedding thing I'll bring up
> before anyone else does is: please format this in ReST and link to it
> from somewhere (likely developer documentation) in the Documentation/
> index.rst file somewhere.
>
> Perhaps in Documentation/core-api/index.rst ?
Sure, I can do it.
Peter do you have any objections?
>
> Lots of notes here:
> https://www.kernel.org/doc/html/latest/doc-guide/sphinx.html#writing-
> documentation
>
> > Signed-off-by: Elena Reshetova <[email protected]>
> > ---
> > Documentation/refcount-vs-atomic.txt | 124
> +++++++++++++++++++++++++++++++++++
> > 1 file changed, 124 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..e703039
> > --- /dev/null
> > +++ b/Documentation/refcount-vs-atomic.txt
> > @@ -0,0 +1,124 @@
> > +==================================
> > +refcount_t API compare to atomic_t
>
> "compared"
>
> > +==================================
> > +
> > +The goal of refcount_t API is to provide a minimal API for implementing
> > +object's reference counters. While a generic architecture-independent
>
> "an object's"
>
> > +implementation from lib/refcount.c uses atomic operations underneath,
> > +there are a number of differences between some of the refcount_*() and
> > +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.
> > +
> > +Notation
>
> Should this section be called "Types of memory ordering"?
Well, these are only some types of ordering and explained mostly around
refcount_t vs. atomic_t, so it doesn't cover everything...
>
> > +========
> > +
> > +An absence of memory ordering guarantees (i.e. fully unordered)
> > +in case of atomics & refcounters only provides atomicity and
>
> I can't parse this. "In an absense ... atomics & refcounts only provide ... "?
>
> > +program order (po) relation (on the same CPU). It guarantees that
> > +each atomic_*() and refcount_*() operation is atomic and instructions
> > +are executed in program order on a single CPU.
> > +Implemented using READ_ONCE()/WRITE_ONCE() and
> > +compare-and-swap primitives.
>
> For here an later, maybe "This is implemented ..."
>
> > +
> > +A strong (full) memory ordering guarantees that all prior loads and
> > +stores (all po-earlier instructions) on the same CPU are completed
> > +before any po-later instruction is executed on the same CPU.
> > +It also guarantees that all po-earlier stores on the same CPU
> > +and all propagated stores from other CPUs must propagate to all
> > +other CPUs before any po-later instruction is executed on the original
> > +CPU (A-cumulative property). Implemented using smp_mb().
> > +
> > +A RELEASE memory ordering guarantees that all prior loads and
> > +stores (all po-earlier instructions) on the same CPU are completed
> > +before the operation. It also guarantees that all po-earlier
> > +stores on the same CPU and all propagated stores from other CPUs
> > +must propagate to all other CPUs before the release operation
> > +(A-cumulative property). Implemented using smp_store_release().
> > +
> > +A control dependency (on success) for refcounters guarantees that
> > +if a reference for an object was successfully obtained (reference
> > +counter increment or addition happened, function returned true),
> > +then further stores are ordered against this operation.
> > +Control dependency on stores are not implemented using any explicit
> > +barriers, but rely on CPU not to speculate on stores. This is only
> > +a single CPU relation and provides no guarantees for other CPUs.
> > +
> > +
> > +Comparison of functions
> > +==========================
> > +
> > +case 1) - non-RMW ops
>
> Should this be spelled out "Read/Modify/Write"?
Sure.
>
> > +---------------------
> > +
> > +Function changes:
> > + atomic_set() --> refcount_set()
> > + atomic_read() --> refcount_read()
> > +
> > +Memory ordering guarantee changes:
> > + fully unordered --> fully unordered
>
> Maybe say: "none (both fully unordered)"
Ok
>
> > +case 2) - increment-based ops that return no value
> > +--------------------------------------------------
> > +
> > +Function changes:
> > + atomic_inc() --> refcount_inc()
> > + atomic_add() --> refcount_add()
> > +
> > +Memory ordering guarantee changes:
> > + fully unordered --> fully unordered
>
> Same.
>
> > +case 3) - decrement-based RMW ops that return no value
> > +------------------------------------------------------
> > +Function changes:
> > + atomic_dec() --> refcount_dec()
> > +
> > +Memory ordering guarantee changes:
> > + fully unordered --> RELEASE ordering
>
> Should the sections where there is a change include an example of how
> this might matter to a developer?
I tried giving examples in the previous version of this doc, but I found
them to be more confusing than explaining anything, so I left them out
in this new version. What would be really
great here is to find a real example from tree where such a difference would
matter for a refcounter, but I wasn't able to find any cases like this.
For an artificial example, I am really struggling to define a meaningful one,
does anyone have any ideas?
Best Regards,
Elena.
>
> > +
> > +
> > +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
> > +
> > +*Note*: we really assume here that necessary ordering is provided as a result
> > +of obtaining pointer to the object!
>
> Same.
>
> > +
> > +
> > +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
> > +
> > +Note: atomic_add_unless() only provides full order on success.
>
> Same.
>
> > +
> > +
> > +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 + control dependency +
> > + hold spin_lock() on success
>
> Same.
>
> This looks like a good start to helping people answer questions about
> refcount_t memory ordering. Thanks!
>
> -Kees
>
> --
> Kees Cook
> Pixel Security
On Tue, Nov 14, 2017 at 11:55 PM, Elena Reshetova
<[email protected]> wrote:
> Some functions from refcount_t API provide different
> memory ordering guarantees that their atomic counterparts.
> This adds a document outlining these differences.
Thanks for writing this up! One bike-shedding thing I'll bring up
before anyone else does is: please format this in ReST and link to it
from somewhere (likely developer documentation) in the Documentation/
index.rst file somewhere.
Perhaps in Documentation/core-api/index.rst ?
Lots of notes here:
https://www.kernel.org/doc/html/latest/doc-guide/sphinx.html#writing-documentation
> Signed-off-by: Elena Reshetova <[email protected]>
> ---
> Documentation/refcount-vs-atomic.txt | 124 +++++++++++++++++++++++++++++++++++
> 1 file changed, 124 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..e703039
> --- /dev/null
> +++ b/Documentation/refcount-vs-atomic.txt
> @@ -0,0 +1,124 @@
> +==================================
> +refcount_t API compare to atomic_t
"compared"
> +==================================
> +
> +The goal of refcount_t API is to provide a minimal API for implementing
> +object's reference counters. While a generic architecture-independent
"an object's"
> +implementation from lib/refcount.c uses atomic operations underneath,
> +there are a number of differences between some of the refcount_*() and
> +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.
> +
> +Notation
Should this section be called "Types of memory ordering"?
> +========
> +
> +An absence of memory ordering guarantees (i.e. fully unordered)
> +in case of atomics & refcounters only provides atomicity and
I can't parse this. "In an absense ... atomics & refcounts only provide ... "?
> +program order (po) relation (on the same CPU). It guarantees that
> +each atomic_*() and refcount_*() operation is atomic and instructions
> +are executed in program order on a single CPU.
> +Implemented using READ_ONCE()/WRITE_ONCE() and
> +compare-and-swap primitives.
For here an later, maybe "This is implemented ..."
> +
> +A strong (full) memory ordering guarantees that all prior loads and
> +stores (all po-earlier instructions) on the same CPU are completed
> +before any po-later instruction is executed on the same CPU.
> +It also guarantees that all po-earlier stores on the same CPU
> +and all propagated stores from other CPUs must propagate to all
> +other CPUs before any po-later instruction is executed on the original
> +CPU (A-cumulative property). Implemented using smp_mb().
> +
> +A RELEASE memory ordering guarantees that all prior loads and
> +stores (all po-earlier instructions) on the same CPU are completed
> +before the operation. It also guarantees that all po-earlier
> +stores on the same CPU and all propagated stores from other CPUs
> +must propagate to all other CPUs before the release operation
> +(A-cumulative property). Implemented using smp_store_release().
> +
> +A control dependency (on success) for refcounters guarantees that
> +if a reference for an object was successfully obtained (reference
> +counter increment or addition happened, function returned true),
> +then further stores are ordered against this operation.
> +Control dependency on stores are not implemented using any explicit
> +barriers, but rely on CPU not to speculate on stores. This is only
> +a single CPU relation and provides no guarantees for other CPUs.
> +
> +
> +Comparison of functions
> +==========================
> +
> +case 1) - non-RMW ops
Should this be spelled out "Read/Modify/Write"?
> +---------------------
> +
> +Function changes:
> + atomic_set() --> refcount_set()
> + atomic_read() --> refcount_read()
> +
> +Memory ordering guarantee changes:
> + fully unordered --> fully unordered
Maybe say: "none (both fully unordered)"
> +case 2) - increment-based ops that return no value
> +--------------------------------------------------
> +
> +Function changes:
> + atomic_inc() --> refcount_inc()
> + atomic_add() --> refcount_add()
> +
> +Memory ordering guarantee changes:
> + fully unordered --> fully unordered
Same.
> +case 3) - decrement-based RMW ops that return no value
> +------------------------------------------------------
> +Function changes:
> + atomic_dec() --> refcount_dec()
> +
> +Memory ordering guarantee changes:
> + fully unordered --> RELEASE ordering
Should the sections where there is a change include an example of how
this might matter to a developer?
> +
> +
> +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
> +
> +*Note*: we really assume here that necessary ordering is provided as a result
> +of obtaining pointer to the object!
Same.
> +
> +
> +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
> +
> +Note: atomic_add_unless() only provides full order on success.
Same.
> +
> +
> +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 + control dependency +
> + hold spin_lock() on success
Same.
This looks like a good start to helping people answer questions about
refcount_t memory ordering. Thanks!
-Kees
--
Kees Cook
Pixel Security
From 1584118008493682834@xxx Wed Nov 15 07:57:38 +0000 2017
X-GM-THRID: 1584118008493682834
X-Gmail-Labels: Inbox,Category Forums,HistoricalUnread
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 <[email protected]>
> > ---
> > 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
?&ן7ߝ???;?~??m?? L?sh?N???w?_~?M4?M{_???1? ?????ێ??~7?O;?E?f????m?l??ۣ ?jנ???????????+?ƥRz
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 <[email protected]>
> ---
> 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
From 1583324615343508740@xxx Mon Nov 06 13:47:00 +0000 2017
X-GM-THRID: 1583324615343508740
X-Gmail-Labels: Inbox,Category Forums,HistoricalUnread