10.2.1.2 Atomic Counting

Simple atomic counting may be used in cases where any CPU acquiring a reference must already hold a reference. This style is used when a single CPU creates an object for its own private use, but must allow other CPU, tasks, timer handlers, or I/O completion handlers that it later spawns to also access this object. Any CPU that hands the object off must first acquire a new reference on behalf of the recipient object. In the Linux kernel, the kref primitives are used to implement this style of reference counting, as shown in Figure [*].

Atomic counting is required because locking is not used to protect all reference-count operations, which means that it is possible for two different CPUs to concurrently manipulate the reference count. If normal increment and decrement were used, a pair of CPUs might both fetch the reference count concurrently, perhaps both obtaining the value ``3''. If both of them increment their value, they will both obtain ``4'', and both will store this value back into the counter. Since the new value of the counter should instead be ``5'', one of the two increments has been lost. Therefore, atomic operations must be used both for counter increments and for counter decrements.

If releases are guarded by locking or RCU, memory barriers are not required, but for different reasons. In the case of locking, the locks provide any needed memory barriers (and disabling of compiler optimizations), and the locks also prevent a pair of releases from running concurrently. In the case of RCU, cleanup must be deferred until all currently executing RCU read-side critical sections have completed, and any needed memory barriers or disabling of compiler optimizations will be provided by the RCU infrastructure. Therefore, if two CPUs release the final two references concurrently, the actual cleanup will be deferred until both CPUs exit their RCU read-side critical sections.

Quick Quiz 10.2: Why isn't it necessary to guard against cases where one CPU acquires a reference just after another CPU releases the last reference? End Quick Quiz

Figure: Linux Kernel kref API
\begin{figure}{ \scriptsize
\begin{verbatim}1 struct kref {
2 atomic_t refco...
...ase(kref);
25 return 1;
26 }
27 return 0;
28 }\end{verbatim}
}\end{figure}

The kref structure itself, consisting of a single atomic data item, is shown in lines 1-3 of Figure [*]. The kref_init() function on lines 5-8 initializes the counter to the value ``1''. Note that the atomic_set() primitive is a simple assignment, the name stems from the data type of atomic_t rather than from the operation. The kref_init() function must be invoked during object creation, before the object has been made available to any other CPU.

The kref_get() function on lines 10-14 unconditionally atomically increments the counter. The atomic_inc() primitive does not necessarily explicitly disable compiler optimizations on all platforms, but the fact that the kref primitives are in a separate module and that the Linux kernel build process does no cross-module optimizations has the same effect.

The kref_put() function on lines 16-28 checks for the counter having the value ``1'' on line 22 (in which case no concurrent kref_get() is permitted), or if atomically decrementing the counter results in zero on line 23. In either of these two cases, kref_put() invokes the specified release function and returns ``1'', telling the caller that cleanup was performed. Otherwise, kref_put() returns ``0''.

Quick Quiz 10.3: If the check on line 22 of Figure [*] fails, how could the check on line 23 possibly succeed? End Quick Quiz

Quick Quiz 10.4: How can it possibly be safe to non-atomically check for equality with ``1'' on line 22 of Figure [*]? End Quick Quiz

Paul E. McKenney 2011-12-16