1.. SPDX-License-Identifier: GPL-2.0
2
3====================================================================
4Reference-count design for elements of lists/arrays protected by RCU
5====================================================================
6
7
8Please note that the percpu-ref feature is likely your first
9stop if you need to combine reference counts and RCU.  Please see
10include/linux/percpu-refcount.h for more information.  However, in
11those unusual cases where percpu-ref would consume too much memory,
12please read on.
13
14------------------------------------------------------------------------
15
16Reference counting on elements of lists which are protected by traditional
17reader/writer spinlocks or semaphores are straightforward:
18
19CODE LISTING A::
20
21    1.					    2.
22    add()				    search_and_reference()
23    {					    {
24	alloc_object				read_lock(&list_lock);
25	...					search_for_element
26	atomic_set(&el->rc, 1);			atomic_inc(&el->rc);
27	write_lock(&list_lock);			 ...
28	add_element				read_unlock(&list_lock);
29	...					...
30	write_unlock(&list_lock);	   }
31    }
32
33    3.					    4.
34    release_referenced()		    delete()
35    {					    {
36	...					write_lock(&list_lock);
37	if(atomic_dec_and_test(&el->rc))	...
38	    kfree(el);
39	...					remove_element
40    }						write_unlock(&list_lock);
41						...
42						if (atomic_dec_and_test(&el->rc))
43						    kfree(el);
44						...
45					    }
46
47If this list/array is made lock free using RCU as in changing the
48write_lock() in add() and delete() to spin_lock() and changing read_lock()
49in search_and_reference() to rcu_read_lock(), the atomic_inc() in
50search_and_reference() could potentially hold reference to an element which
51has already been deleted from the list/array.  Use atomic_inc_not_zero()
52in this scenario as follows:
53
54CODE LISTING B::
55
56    1.					    2.
57    add()				    search_and_reference()
58    {					    {
59	alloc_object				rcu_read_lock();
60	...					search_for_element
61	atomic_set(&el->rc, 1);			if (!atomic_inc_not_zero(&el->rc)) {
62	spin_lock(&list_lock);			    rcu_read_unlock();
63						    return FAIL;
64	add_element				}
65	...					...
66	spin_unlock(&list_lock);		rcu_read_unlock();
67    }					    }
68    3.					    4.
69    release_referenced()		    delete()
70    {					    {
71	...					spin_lock(&list_lock);
72	if (atomic_dec_and_test(&el->rc))	...
73	    call_rcu(&el->head, el_free);	remove_element
74	...					spin_unlock(&list_lock);
75    }						...
76						if (atomic_dec_and_test(&el->rc))
77						    call_rcu(&el->head, el_free);
78						...
79					    }
80
81Sometimes, a reference to the element needs to be obtained in the
82update (write) stream.	In such cases, atomic_inc_not_zero() might be
83overkill, since we hold the update-side spinlock.  One might instead
84use atomic_inc() in such cases.
85
86It is not always convenient to deal with "FAIL" in the
87search_and_reference() code path.  In such cases, the
88atomic_dec_and_test() may be moved from delete() to el_free()
89as follows:
90
91CODE LISTING C::
92
93    1.					    2.
94    add()				    search_and_reference()
95    {					    {
96	alloc_object				rcu_read_lock();
97	...					search_for_element
98	atomic_set(&el->rc, 1);			atomic_inc(&el->rc);
99	spin_lock(&list_lock);			...
100
101	add_element				rcu_read_unlock();
102	...				    }
103	spin_unlock(&list_lock);	    4.
104    }					    delete()
105    3.					    {
106    release_referenced()			spin_lock(&list_lock);
107    {						...
108	...					remove_element
109	if (atomic_dec_and_test(&el->rc))	spin_unlock(&list_lock);
110	    kfree(el);				...
111	...					call_rcu(&el->head, el_free);
112    }						...
113    5.					    }
114    void el_free(struct rcu_head *rhp)
115    {
116	release_referenced();
117    }
118
119The key point is that the initial reference added by add() is not removed
120until after a grace period has elapsed following removal.  This means that
121search_and_reference() cannot find this element, which means that the value
122of el->rc cannot increase.  Thus, once it reaches zero, there are no
123readers that can or ever will be able to reference the element.	 The
124element can therefore safely be freed.	This in turn guarantees that if
125any reader finds the element, that reader may safely acquire a reference
126without checking the value of the reference counter.
127
128A clear advantage of the RCU-based pattern in listing C over the one
129in listing B is that any call to search_and_reference() that locates
130a given object will succeed in obtaining a reference to that object,
131even given a concurrent invocation of delete() for that same object.
132Similarly, a clear advantage of both listings B and C over listing A is
133that a call to delete() is not delayed even if there are an arbitrarily
134large number of calls to search_and_reference() searching for the same
135object that delete() was invoked on.  Instead, all that is delayed is
136the eventual invocation of kfree(), which is usually not a problem on
137modern computer systems, even the small ones.
138
139In cases where delete() can sleep, synchronize_rcu() can be called from
140delete(), so that el_free() can be subsumed into delete as follows::
141
142    4.
143    delete()
144    {
145	spin_lock(&list_lock);
146	...
147	remove_element
148	spin_unlock(&list_lock);
149	...
150	synchronize_rcu();
151	if (atomic_dec_and_test(&el->rc))
152	    kfree(el);
153	...
154    }
155
156As additional examples in the kernel, the pattern in listing C is used by
157reference counting of struct pid, while the pattern in listing B is used by
158struct posix_acl.
159