10.2 Reference Counting

Reference counting tracks the number of references to a given object in order to prevent that object from being prematurely freed. Although this is a conceptually simple technique, many devils hide in the details. After all, if the object was not subject to being prematurely freed, there would be no need for the reference counter. But if the object is subject to being prematurely freed, what prevents that object from being freed during the reference-acquisition process itself?

There are a number of possible answers to this question, including:

  1. A lock residing outside of the object must be held while manipulating the reference count. Note that there are a wide variety of types of locks, however, pretty much any type will suffice.
  2. The object is created with a non-zero reference count, and new references may be acquired only when the current value of the reference counter is non-zero. Once acquired, a reference may be handed off to some other entity.
  3. An existence guarantee is provided for the object, so that it cannot be freed during any time interval when some entity might be attempting to acquire a reference. Existence guarantees are often provided by automatic garbage collectors, and, as will be seen in Section [*], they can also be provided by RCU.
  4. A type-safety guarantee is provided for the object, and there is in addition some identity check that can be performed once the reference is acquired. Type-safety guarantees can be provided by special-purpose memory allocators, and can also be provided by the SLAB_DESTROY_BY_RCU feature within the Linux kernel, again, as will be seen in Section [*].

Of course, any mechanism that provides existence guarantees by definition also provides type-safety guarantees. This section will therefore group the last two answers together under the rubric of RCU, leaving us with three general categories of reference-acquisition protection, namely, locking, reference counting, and RCU.

Quick Quiz 10.1: Why not implement reference-acquisition using a simple compare-and-swap operation that only acquires a reference if the reference counter is non-zero? End Quick Quiz


Table: Reference Counting and Synchronization Mechanisms
  Release Synchronization
Acquisition   Reference  
Synchronization Locking Counting RCU
Locking - CAM CA
Reference A AM A
Counting      
RCU CA MCA CA


Given that the key reference-counting issue is synchronization between acquisition of a reference and freeing of the object, we have nine possible combinations of mechanisms, as shown in Table [*]. This table divides reference-counting mechanisms into the following broad categories:

  1. Simple counting with neither atomic operations, memory barriers, nor alignment constraints (``-'').
  2. Atomic counting without memory barriers (``A'').
  3. Atomic counting, with memory barriers required only on release (``AM'').
  4. Atomic counting with a check combined with the atomic acquisition operation, and with memory barriers required only on release (``CAM'').
  5. Atomic counting with a check combined with the atomic acquisition operation (``CA'').
  6. Atomic counting with a check combined with the atomic acquisition operation, and with memory barriers also required on acquisition (``MCA'').
However, because all Linux-kernel atomic operations that return a value are defined to contain memory barriers, all release operations contain memory barriers, and all checked acquisition operations also contain memory barriers. Therefore, cases ``CA'' and ``MCA'' are equivalent to ``CAM'', so that there are sections below for only the first four cases: ``-'', ``A'', ``AM'', and ``CAM''. The Linux primitives that support reference counting are presented in Section [*]. Later sections cite optimizations that can improve performance if reference acquisition and release is very frequent, and the reference count need be checked for zero only very rarely.



Subsections
Paul E. McKenney 2011-12-16