Documentation/core-api/refcount-vs-atomic.rst

   1 ===================================
   2 refcount_t API compared to atomic_t
   3 ===================================
   4
   5 .. contents:: :local:
   6
   7 Introduction
   8 ============
   9
  10 The goal of refcount_t API is to provide a minimal API for implementing
  11 an object's reference counters. While a generic architecture-independent
  12 implementation from lib/refcount.c uses atomic operations underneath,
  13 there are a number of differences between some of the ``refcount_*()`` and
  14 ``atomic_*()`` functions with regards to the memory ordering guarantees.
  15 This document outlines the differences and provides respective examples
  16 in order to help maintainers validate their code against the change in
  17 these memory ordering guarantees.
  18
  19 The terms used through this document try to follow the formal LKMM defined in
  20 tools/memory-model/Documentation/explanation.txt.
  21
  22 memory-barriers.txt and atomic_t.txt provide more background to the
  23 memory ordering in general and for atomic operations specifically.
  24
  25 Relevant types of memory ordering
  26 =================================
  27
  28 .. note:: The following section only covers some of the memory
  29    ordering types that are relevant for the atomics and reference
  30    counters and used through this document. For a much broader picture
  31    please consult memory-barriers.txt document.
  32
  33 In the absence of any memory ordering guarantees (i.e. fully unordered)
  34 atomics & refcounters only provide atomicity and
  35 program order (po) relation (on the same CPU). It guarantees that
  36 each ``atomic_*()`` and ``refcount_*()`` operation is atomic and instructions
  37 are executed in program order on a single CPU.
  38 This is implemented using :c:func:`READ_ONCE`/:c:func:`WRITE_ONCE` and
  39 compare-and-swap primitives.
  40
  41 A strong (full) memory ordering guarantees that all prior loads and
  42 stores (all po-earlier instructions) on the same CPU are completed
  43 before any po-later instruction is executed on the same CPU.
  44 It also guarantees that all po-earlier stores on the same CPU
  45 and all propagated stores from other CPUs must propagate to all
  46 other CPUs before any po-later instruction is executed on the original
  47 CPU (A-cumulative property). This is implemented using :c:func:`smp_mb`.
  48
  49 A RELEASE memory ordering guarantees that all prior loads and
  50 stores (all po-earlier instructions) on the same CPU are completed
  51 before the operation. It also guarantees that all po-earlier
  52 stores on the same CPU and all propagated stores from other CPUs
  53 must propagate to all other CPUs before the release operation
  54 (A-cumulative property). This is implemented using
  55 :c:func:`smp_store_release`.
  56
  57 An ACQUIRE memory ordering guarantees that all post loads and
  58 stores (all po-later instructions) on the same CPU are
  59 completed after the acquire operation. It also guarantees that all
  60 po-later stores on the same CPU must propagate to all other CPUs
  61 after the acquire operation executes. This is implemented using
  62 :c:func:`smp_acquire__after_ctrl_dep`.
  63
  64 A control dependency (on success) for refcounters guarantees that
  65 if a reference for an object was successfully obtained (reference
  66 counter increment or addition happened, function returned true),
  67 then further stores are ordered against this operation.
  68 Control dependency on stores are not implemented using any explicit
  69 barriers, but rely on CPU not to speculate on stores. This is only
  70 a single CPU relation and provides no guarantees for other CPUs.
  71
  72
  73 Comparison of functions
  74 =======================
  75
  76 case 1) - non-"Read/Modify/Write" (RMW) ops
  77 -------------------------------------------
  78
  79 Function changes:
  80
  81  * :c:func:`atomic_set` --> :c:func:`refcount_set`
  82  * :c:func:`atomic_read` --> :c:func:`refcount_read`
  83
  84 Memory ordering guarantee changes:
  85
  86  * none (both fully unordered)
  87
  88
  89 case 2) - increment-based ops that return no value
  90 --------------------------------------------------
  91
  92 Function changes:
  93
  94  * :c:func:`atomic_inc` --> :c:func:`refcount_inc`
  95  * :c:func:`atomic_add` --> :c:func:`refcount_add`
  96
  97 Memory ordering guarantee changes:
  98
  99  * none (both fully unordered)
 100
 101 case 3) - decrement-based RMW ops that return no value
 102 ------------------------------------------------------
 103
 104 Function changes:
 105
 106  * :c:func:`atomic_dec` --> :c:func:`refcount_dec`
 107
 108 Memory ordering guarantee changes:
 109
 110  * fully unordered --> RELEASE ordering
 111
 112
 113 case 4) - increment-based RMW ops that return a value
 114 -----------------------------------------------------
 115
 116 Function changes:
 117
 118  * :c:func:`atomic_inc_not_zero` --> :c:func:`refcount_inc_not_zero`
 119  * no atomic counterpart --> :c:func:`refcount_add_not_zero`
 120
 121 Memory ordering guarantees changes:
 122
 123  * fully ordered --> control dependency on success for stores
 124
 125 .. note:: We really assume here that necessary ordering is provided as a
 126    result of obtaining pointer to the object!
 127
 128
 129 case 5) - generic dec/sub decrement-based RMW ops that return a value
 130 ---------------------------------------------------------------------
 131
 132 Function changes:
 133
 134  * :c:func:`atomic_dec_and_test` --> :c:func:`refcount_dec_and_test`
 135  * :c:func:`atomic_sub_and_test` --> :c:func:`refcount_sub_and_test`
 136
 137 Memory ordering guarantees changes:
 138
 139  * fully ordered --> RELEASE ordering + ACQUIRE ordering on success
 140
 141
 142 case 6) other decrement-based RMW ops that return a value
 143 ---------------------------------------------------------
 144
 145 Function changes:
 146
 147  * no atomic counterpart --> :c:func:`refcount_dec_if_one`
 148  * ``atomic_add_unless(&var, -1, 1)`` --> ``refcount_dec_not_one(&var)``
 149
 150 Memory ordering guarantees changes:
 151
 152  * fully ordered --> RELEASE ordering + control dependency
 153
 154 .. note:: :c:func:`atomic_add_unless` only provides full order on success.
 155
 156
 157 case 7) - lock-based RMW
 158 ------------------------
 159
 160 Function changes:
 161
 162  * :c:func:`atomic_dec_and_lock` --> :c:func:`refcount_dec_and_lock`
 163  * :c:func:`atomic_dec_and_mutex_lock` --> :c:func:`refcount_dec_and_mutex_lock`
 164
 165 Memory ordering guarantees changes:
 166
 167  * fully ordered --> RELEASE ordering + control dependency + hold
 168    :c:func:`spin_lock` on success