[PATCH] files: rcuref APIs
[linux-3.10.git] / Documentation / RCU / rcuref.txt
1 Refcounter framework for elements of lists/arrays protected by
2 RCU.
3
4 Refcounting on elements of  lists which are protected by traditional
5 reader/writer spinlocks or semaphores are straight forward as in:
6
7 1.                                      2.
8 add()                                   search_and_reference()
9 {                                       {
10         alloc_object                            read_lock(&list_lock);
11         ...                                     search_for_element
12         atomic_set(&el->rc, 1);                 atomic_inc(&el->rc);
13         write_lock(&list_lock);                 ...
14         add_element                             read_unlock(&list_lock);
15         ...                                     ...
16         write_unlock(&list_lock);       }
17 }
18
19 3.                                      4.
20 release_referenced()                    delete()
21 {                                       {
22         ...                             write_lock(&list_lock);
23         atomic_dec(&el->rc, relfunc)    ...
24         ...                             delete_element
25 }                                       write_unlock(&list_lock);
26                                         ...
27                                         if (atomic_dec_and_test(&el->rc))
28                                                 kfree(el);
29                                         ...
30                                         }
31
32 If this list/array is made lock free using rcu as in changing the
33 write_lock in add() and delete() to spin_lock and changing read_lock
34 in search_and_reference to rcu_read_lock(), the rcuref_get in
35 search_and_reference could potentially hold reference to an element which
36 has already been deleted from the list/array.  rcuref_lf_get_rcu takes
37 care of this scenario. search_and_reference should look as;
38
39 1.                                      2.
40 add()                                   search_and_reference()
41 {                                       {
42         alloc_object                            rcu_read_lock();
43         ...                                     search_for_element
44         atomic_set(&el->rc, 1);                 if (rcuref_inc_lf(&el->rc)) {
45         write_lock(&list_lock);                         rcu_read_unlock();
46                                                         return FAIL;
47         add_element                             }
48         ...                                     ...
49         write_unlock(&list_lock);               rcu_read_unlock();
50 }                                       }
51 3.                                      4.
52 release_referenced()                    delete()
53 {                                       {
54         ...                             write_lock(&list_lock);
55         rcuref_dec(&el->rc, relfunc)    ...
56         ...                             delete_element
57 }                                       write_unlock(&list_lock);
58                                         ...
59                                         if (rcuref_dec_and_test(&el->rc))
60                                                 call_rcu(&el->head, el_free);
61                                         ...
62                                         }
63
64 Sometimes, reference to the element need to be obtained in the
65 update (write) stream.  In such cases, rcuref_inc_lf might be an overkill
66 since the spinlock serialising list updates are held. rcuref_inc
67 is to be used in such cases.
68 For arches which do not have cmpxchg rcuref_inc_lf
69 api uses a hashed spinlock implementation and the same hashed spinlock
70 is acquired in all rcuref_xxx primitives to preserve atomicity.
71 Note: Use rcuref_inc api only if you need to use rcuref_inc_lf on the
72 refcounter atleast at one place.  Mixing rcuref_inc and atomic_xxx api
73 might lead to races. rcuref_inc_lf() must be used in lockfree
74 RCU critical sections only.