From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1756324AbdKOH4S (ORCPT ); Wed, 15 Nov 2017 02:56:18 -0500 Received: from mga01.intel.com ([192.55.52.88]:47218 "EHLO mga01.intel.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1755287AbdKOH4B (ORCPT ); Wed, 15 Nov 2017 02:56:01 -0500 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.44,398,1505804400"; d="scan'208";a="2834811" From: Elena Reshetova To: peterz@infradead.org Cc: linux-kernel@vger.kernel.org, gregkh@linuxfoundation.org, keescook@chromium.org, tglx@linutronix.de, mingo@redhat.com, ishkamiel@gmail.com, paulmck@linux.vnet.ibm.com, stern@rowland.harvard.edu, Elena Reshetova Subject: [PATCH] refcount_t: documentation for memory ordering differences Date: Wed, 15 Nov 2017 09:55:51 +0200 Message-Id: <1510732551-25547-2-git-send-email-elena.reshetova@intel.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1510732551-25547-1-git-send-email-elena.reshetova@intel.com> References: <1510732551-25547-1-git-send-email-elena.reshetova@intel.com> Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 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 --- 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 0000000..e703039 --- /dev/null +++ b/Documentation/refcount-vs-atomic.txt @@ -0,0 +1,124 @@ +================================== +refcount_t API compare to atomic_t +================================== + +The goal of refcount_t API is to provide a minimal API for implementing +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. + +Notation +======== + +An absence of memory ordering guarantees (i.e. fully unordered) +in case of atomics & refcounters only provides 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. +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). 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 +--------------------- + +Function changes: + atomic_set() --> refcount_set() + atomic_read() --> refcount_read() + +Memory ordering guarantee changes: + fully unordered --> 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 + + +case 3) - decrement-based RMW ops that return no value +------------------------------------------------------ +Function changes: + atomic_dec() --> refcount_dec() + +Memory ordering guarantee changes: + fully unordered --> RELEASE ordering + + +case 4) - increment-based RMW ops that return a value +----------------------------------------------------- + +Function changes: + atomic_inc_not_zero() --> refcount_inc_not_zero() + no atomic counterpart --> 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: + atomic_dec_and_test() --> refcount_dec_and_test() + atomic_sub_and_test() --> refcount_sub_and_test() + no atomic counterpart --> 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: atomic_add_unless() only provides full order on success. + + +case 6) - lock-based RMW +------------------------ + +Function changes: + + atomic_dec_and_lock() --> refcount_dec_and_lock() + atomic_dec_and_mutex_lock() --> refcount_dec_and_mutex_lock() + +Memory ordering guarantees changes: + fully ordered --> RELEASE ordering + control dependency + + hold spin_lock() on success -- 2.7.4