refcount-vs-atomic.rst 5.6 KB

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