RE: [PATCH] refcount_t: documentation for memory ordering differences
On Wed, Nov 29, 2017 at 4:36 AM, Elena Reshetova > wrote: > > 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 > > Thanks for the improvements! > > I have some markup changes to add, but I'll send that as a separate patch. Thank you Kees! I guess I was too minimal on my markup use, so doc was pretty plain before. I have just joined your changes with mine and put both of our sign-off to the resulting patch. I think this way it is easier for reviewers since ultimately content is the same. I will now fix one more thing Randy noticed and then send it to linux-doc and Jon Corbet. Best Regards, Elena. > > Acked-by: Kees Cook > > -Kees > > > --- > > 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 000..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: > > +
Re: [PATCH] refcount_t: documentation for memory ordering differences
On Wed, Nov 29, 2017 at 4:36 AM, Elena Reshetova wrote: > 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 Thanks for the improvements! I have some markup changes to add, but I'll send that as a separate patch. Acked-by: Kees Cook -Kees > --- > 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 000..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 > +---
RE: [PATCH] refcount_t: documentation for memory ordering differences
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 > 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 > > --- > > 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 000..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 > > +-
Re: [PATCH] refcount_t: documentation for memory ordering differences
On Tue, Nov 14, 2017 at 11:55 PM, Elena Reshetova 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 > --- > 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 000..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 chan