1Reference-count design for elements of lists/arrays protected by RCU.
2
3
4Please note that the percpu-ref feature is likely your first
5stop if you need to combine reference counts and RCU.  Please see
6include/linux/percpu-refcount.h for more information.  However, in
7those unusual cases where percpu-ref would consume too much memory,
8please read on.
9
10------------------------------------------------------------------------
11
12Reference counting on elements of lists which are protected by traditional
13reader/writer spinlocks or semaphores are straightforward:
14
151.				2.
16add()				search_and_reference()
17{				{
18    alloc_object		    read_lock(&list_lock);
19    ...				    search_for_element
20    atomic_set(&el->rc, 1);	    atomic_inc(&el->rc);
21    write_lock(&list_lock);	     ...
22    add_element			    read_unlock(&list_lock);
23    ...				    ...
24    write_unlock(&list_lock);	}
25}
26
273.					4.
28release_referenced()			delete()
29{					{
30    ...					    write_lock(&list_lock);
31    atomic_dec(&el->rc, relfunc)	    ...
32    ...					    remove_element
33}					    write_unlock(&list_lock);
34 					    ...
35					    if (atomic_dec_and_test(&el->rc))
36					        kfree(el);
37					    ...
38					}
39
40If this list/array is made lock free using RCU as in changing the
41write_lock() in add() and delete() to spin_lock() and changing read_lock()
42in search_and_reference() to rcu_read_lock(), the atomic_inc() in
43search_and_reference() could potentially hold reference to an element which
44has already been deleted from the list/array.  Use atomic_inc_not_zero()
45in this scenario as follows:
46
471.					2.
48add()					search_and_reference()
49{					{
50    alloc_object			    rcu_read_lock();
51    ...					    search_for_element
52    atomic_set(&el->rc, 1);		    if (!atomic_inc_not_zero(&el->rc)) {
53    spin_lock(&list_lock);		        rcu_read_unlock();
54					        return FAIL;
55    add_element				    }
56    ...					    ...
57    spin_unlock(&list_lock);		    rcu_read_unlock();
58}					}
593.					4.
60release_referenced()			delete()
61{					{
62    ...					    spin_lock(&list_lock);
63    if (atomic_dec_and_test(&el->rc))       ...
64        call_rcu(&el->head, el_free);       remove_element
65    ...                                     spin_unlock(&list_lock);
66} 					    ...
67					    if (atomic_dec_and_test(&el->rc))
68					        call_rcu(&el->head, el_free);
69					    ...
70					}
71
72Sometimes, a reference to the element needs to be obtained in the
73update (write) stream.  In such cases, atomic_inc_not_zero() might be
74overkill, since we hold the update-side spinlock.  One might instead
75use atomic_inc() in such cases.
76
77It is not always convenient to deal with "FAIL" in the
78search_and_reference() code path.  In such cases, the
79atomic_dec_and_test() may be moved from delete() to el_free()
80as follows:
81
821.					2.
83add()					search_and_reference()
84{					{
85    alloc_object			    rcu_read_lock();
86    ...					    search_for_element
87    atomic_set(&el->rc, 1);		    atomic_inc(&el->rc);
88    spin_lock(&list_lock);		    ...
89
90    add_element				    rcu_read_unlock();
91    ...					}
92    spin_unlock(&list_lock);		4.
93}					delete()
943.					{
95release_referenced()			    spin_lock(&list_lock);
96{					    ...
97    ...					    remove_element
98    if (atomic_dec_and_test(&el->rc))       spin_unlock(&list_lock);
99        kfree(el);			    ...
100    ...                                     call_rcu(&el->head, el_free);
101} 					    ...
1025.					}
103void el_free(struct rcu_head *rhp)
104{
105    release_referenced();
106}
107
108The key point is that the initial reference added by add() is not removed
109until after a grace period has elapsed following removal.  This means that
110search_and_reference() cannot find this element, which means that the value
111of el->rc cannot increase.  Thus, once it reaches zero, there are no
112readers that can or ever will be able to reference the element.  The
113element can therefore safely be freed.  This in turn guarantees that if
114any reader finds the element, that reader may safely acquire a reference
115without checking the value of the reference counter.
116
117In cases where delete() can sleep, synchronize_rcu() can be called from
118delete(), so that el_free() can be subsumed into delete as follows:
119
1204.
121delete()
122{
123    spin_lock(&list_lock);
124    ...
125    remove_element
126    spin_unlock(&list_lock);
127    ...
128    synchronize_rcu();
129    if (atomic_dec_and_test(&el->rc))
130    	kfree(el);
131    ...
132}
133