mirror of https://lore.kernel.org/lkml/
 help / color / mirror / Atom feed
From: Elena Reshetova <elena.reshetova@intel.com>
To: corbet@lwn.net
Cc: linux-doc@vger.kernel.org, peterz@infradead.org,
	linux-kernel@vger.kernel.org, keescook@chromium.org,
	david@fromorbit.com, Elena Reshetova <elena.reshetova@intel.com>
Subject: [PATCH] docs: refcount_t documentation
Date: Tue,  5 Dec 2017 12:46:35 +0200	[thread overview]
Message-ID: <1512470795-22626-1-git-send-email-elena.reshetova@intel.com> (raw)

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

             reply	other threads:[~2017-12-05 10:54 UTC|newest]

Thread overview: 5+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2017-12-05 10:46 Elena Reshetova [this message]
2017-12-07 17:58 ` Jonathan Corbet
2017-12-07 17:59   ` Kees Cook
2017-12-11 21:42 ` Jonathan Corbet
2017-12-11 22:17   ` Kees Cook

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=1512470795-22626-1-git-send-email-elena.reshetova@intel.com \
    --to=elena.reshetova@intel.com \
    --cc=corbet@lwn.net \
    --cc=david@fromorbit.com \
    --cc=keescook@chromium.org \
    --cc=linux-doc@vger.kernel.org \
    --cc=linux-kernel@vger.kernel.org \
    --cc=peterz@infradead.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox

all inboxes | Powered by JetHome®