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:
- 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.
- 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.
- 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.
- 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:
- Simple counting with neither atomic operations, memory
barriers, nor alignment constraints (``-'').
- Atomic counting without memory barriers (``A'').
- Atomic counting, with memory barriers required only on release
(``AM'').
- Atomic counting with a check combined with the atomic acquisition
operation, and with memory barriers required only on release
(``CAM'').
- Atomic counting with a check combined with the atomic acquisition
operation (``CA'').
- 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