[PATCH] docs: refcount_t documentation

[PATCH] docs: refcount_t documentation

[Elena Reshetova]

Some functions from refcount_t API provide different
memory ordering guarantees that their atomic counterparts.
This adds a document outlining these differences (
Documentation/core-api/refcount-vs-atomic.rst) as well as
some other minor improvements.

Signed-off-by: Elena Reshetova <elena.reshetova@intel.com>
Signed-off-by: Kees Cook <keescook@chromium.org>
---
 Documentation/core-api/index.rst              |   1 +
 Documentation/core-api/refcount-vs-atomic.rst | 150 ++++++++++++++++++++++++++
 Documentation/driver-api/basics.rst           |  21 ++--
 include/linux/refcount.h                      |   2 +-
 4 files changed, 167 insertions(+), 7 deletions(-)
 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..83351c2
--- /dev/null
+++ b/Documentation/core-api/refcount-vs-atomic.rst
@@ -0,0 +1,150 @@
+===================================
+refcount_t API compared to atomic_t
+===================================
+
+.. contents:: :local:
+
+Introduction
+============
+
+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.
+
+The terms used through this document try to follow the formal LKMM defined in
+github.com/aparri/memory-model/blob/master/Documentation/explanation.txt
+
+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 :c:func:`READ_ONCE`/:c:func:`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 :c:func:`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
+:c:func:`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:
+
+ * :c:func:`atomic_set` --> :c:func:`refcount_set`
+ * :c:func:`atomic_read` --> :c:func:`refcount_read`
+
+Memory ordering guarantee changes:
+
+ * none (both fully unordered)
+
+
+case 2) - increment-based ops that return no value
+--------------------------------------------------
+
+Function changes:
+
+ * :c:func:`atomic_inc` --> :c:func:`refcount_inc`
+ * :c:func:`atomic_add` --> :c:func:`refcount_add`
+
+Memory ordering guarantee changes:
+
+ * none (both fully unordered)
+
+case 3) - decrement-based RMW ops that return no value
+------------------------------------------------------
+
+Function changes:
+
+ * :c:func:`atomic_dec` --> :c:func:`refcount_dec`
+
+Memory ordering guarantee changes:
+
+ * fully unordered --> RELEASE ordering
+
+
+case 4) - increment-based RMW ops that return a value
+-----------------------------------------------------
+
+Function changes:
+
+ * :c:func:`atomic_inc_not_zero` --> :c:func:`refcount_inc_not_zero`
+ * no atomic counterpart --> :c:func:`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:
+
+ * :c:func:`atomic_dec_and_test` --> :c:func:`refcount_dec_and_test`
+ * :c:func:`atomic_sub_and_test` --> :c:func:`refcount_sub_and_test`
+ * no atomic counterpart --> :c:func:`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:: :c:func:`atomic_add_unless` only provides full order on success.
+
+
+case 6) - lock-based RMW
+------------------------
+
+Function changes:
+
+ * :c:func:`atomic_dec_and_lock` --> :c:func:`refcount_dec_and_lock`
+ * :c:func:`atomic_dec_and_mutex_lock` --> :c:func:`refcount_dec_and_mutex_lock`
+
+Memory ordering guarantees changes:
+
+ * fully ordered --> RELEASE ordering + control dependency + hold
+   :c:func:`spin_lock` on success
diff --git a/Documentation/driver-api/basics.rst b/Documentation/driver-api/basics.rst
index 73fa7d4..826e85d 100644
--- a/Documentation/driver-api/basics.rst
+++ b/Documentation/driver-api/basics.rst
@@ -13,12 +13,6 @@ Driver device table
 .. kernel-doc:: include/linux/mod_devicetable.h
    :internal:
 
-Atomic and pointer manipulation
--------------------------------
-
-.. kernel-doc:: arch/x86/include/asm/atomic.h
-   :internal:
-
 Delaying, scheduling, and timer routines
 ----------------------------------------
 
@@ -85,6 +79,21 @@ Internal Functions
 .. kernel-doc:: kernel/kthread.c
    :export:
 
+Reference counting
+------------------
+
+.. kernel-doc:: include/linux/refcount.h
+   :internal:
+
+.. kernel-doc:: lib/refcount.c
+   :export:
+
+Atomics
+-------
+
+.. kernel-doc:: arch/x86/include/asm/atomic.h
+   :internal:
+
 Kernel objects manipulation
 ---------------------------
 
diff --git a/include/linux/refcount.h b/include/linux/refcount.h
index e828658..4193c41 100644
--- a/include/linux/refcount.h
+++ b/include/linux/refcount.h
@@ -8,7 +8,7 @@
 #include <linux/kernel.h>
 
 /**
- * refcount_t - variant of atomic_t specialized for reference counts
+ * struct refcount_t - variant of atomic_t specialized for reference counts
  * @refs: atomic_t counter field
  *
  * The counter saturates at UINT_MAX and will not move once
-- 
2.7.4

Re: [PATCH] docs: refcount_t documentation

[Jonathan Corbet]

On Tue,  5 Dec 2017 12:46:35 +0200
Elena Reshetova <elena.reshetova@intel.com> wrote:

> Some functions from refcount_t API provide different
> memory ordering guarantees that their atomic counterparts.
> This adds a document outlining these differences (
> Documentation/core-api/refcount-vs-atomic.rst) as well as
> some other minor improvements.

This seems generally good to me.  Did you want me to take it through the
docs tree (including the refcount.h change) or did you have some other
path in mind?

Thanks,

jon

Re: [PATCH] docs: refcount_t documentation

[Kees Cook]

On Thu, Dec 7, 2017 at 9:58 AM, Jonathan Corbet <corbet@lwn.net> wrote:
> On Tue,  5 Dec 2017 12:46:35 +0200
> Elena Reshetova <elena.reshetova@intel.com> wrote:
>
>> Some functions from refcount_t API provide different
>> memory ordering guarantees that their atomic counterparts.
>> This adds a document outlining these differences (
>> Documentation/core-api/refcount-vs-atomic.rst) as well as
>> some other minor improvements.
>
> This seems generally good to me.  Did you want me to take it through the
> docs tree (including the refcount.h change) or did you have some other
> path in mind?

FWIW, I had assumed this would go via the docs tree.

-Kees

-- 
Kees Cook
Pixel Security

Re: [PATCH] docs: refcount_t documentation

[Jonathan Corbet]

On Tue,  5 Dec 2017 12:46:35 +0200
Elena Reshetova <elena.reshetova@intel.com> wrote:

> Some functions from refcount_t API provide different
> memory ordering guarantees that their atomic counterparts.
> This adds a document outlining these differences (
> Documentation/core-api/refcount-vs-atomic.rst) as well as
> some other minor improvements.

I've applied this, thanks, it looks good.

One thing I noticed, though, is that this landed in the core-api manual,
while the refcount_t documentation is in the driver-api manual.  The
cross-references work just fine and such, but this still doesn't seem quite
right.  Probably what should be done is to have all the refcount_t
material in core-api; I may do that if I get a moment.

Thanks,

jon

Re: [PATCH] docs: refcount_t documentation

[Kees Cook]

On Mon, Dec 11, 2017 at 1:42 PM, Jonathan Corbet <corbet@lwn.net> wrote:
> On Tue,  5 Dec 2017 12:46:35 +0200
> Elena Reshetova <elena.reshetova@intel.com> wrote:
>
>> Some functions from refcount_t API provide different
>> memory ordering guarantees that their atomic counterparts.
>> This adds a document outlining these differences (
>> Documentation/core-api/refcount-vs-atomic.rst) as well as
>> some other minor improvements.
>
> I've applied this, thanks, it looks good.
>
> One thing I noticed, though, is that this landed in the core-api manual,
> while the refcount_t documentation is in the driver-api manual.  The
> cross-references work just fine and such, but this still doesn't seem quite
> right.  Probably what should be done is to have all the refcount_t
> material in core-api; I may do that if I get a moment.

I did notice that, yeah. It seemed like a bunch of kernel-doc was
living in the driver-api manual, where it should be in core. Since
atomics were already there, I put refcount_t there...

-Kees

-- 
Kees Cook
Pixel Security