diff options
Diffstat (limited to 'Documentation/RCU/rcuref.txt')
| -rw-r--r-- | Documentation/RCU/rcuref.txt | 87 |
1 files changed, 40 insertions, 47 deletions
diff --git a/Documentation/RCU/rcuref.txt b/Documentation/RCU/rcuref.txt index a23fee66064d..3f60db41b2f0 100644 --- a/Documentation/RCU/rcuref.txt +++ b/Documentation/RCU/rcuref.txt | |||
| @@ -1,74 +1,67 @@ | |||
| 1 | Refcounter framework for elements of lists/arrays protected by | 1 | Refcounter design for elements of lists/arrays protected by RCU. |
| 2 | RCU. | ||
| 3 | 2 | ||
| 4 | Refcounting on elements of lists which are protected by traditional | 3 | Refcounting on elements of lists which are protected by traditional |
| 5 | reader/writer spinlocks or semaphores are straight forward as in: | 4 | reader/writer spinlocks or semaphores are straight forward as in: |
| 6 | 5 | ||
| 7 | 1. 2. | 6 | 1. 2. |
| 8 | add() search_and_reference() | 7 | add() search_and_reference() |
| 9 | { { | 8 | { { |
| 10 | alloc_object read_lock(&list_lock); | 9 | alloc_object read_lock(&list_lock); |
| 11 | ... search_for_element | 10 | ... search_for_element |
| 12 | atomic_set(&el->rc, 1); atomic_inc(&el->rc); | 11 | atomic_set(&el->rc, 1); atomic_inc(&el->rc); |
| 13 | write_lock(&list_lock); ... | 12 | write_lock(&list_lock); ... |
| 14 | add_element read_unlock(&list_lock); | 13 | add_element read_unlock(&list_lock); |
| 15 | ... ... | 14 | ... ... |
| 16 | write_unlock(&list_lock); } | 15 | write_unlock(&list_lock); } |
| 17 | } | 16 | } |
| 18 | 17 | ||
| 19 | 3. 4. | 18 | 3. 4. |
| 20 | release_referenced() delete() | 19 | release_referenced() delete() |
| 21 | { { | 20 | { { |
| 22 | ... write_lock(&list_lock); | 21 | ... write_lock(&list_lock); |
| 23 | atomic_dec(&el->rc, relfunc) ... | 22 | atomic_dec(&el->rc, relfunc) ... |
| 24 | ... delete_element | 23 | ... delete_element |
| 25 | } write_unlock(&list_lock); | 24 | } write_unlock(&list_lock); |
| 26 | ... | 25 | ... |
| 27 | if (atomic_dec_and_test(&el->rc)) | 26 | if (atomic_dec_and_test(&el->rc)) |
| 28 | kfree(el); | 27 | kfree(el); |
| 29 | ... | 28 | ... |
| 30 | } | 29 | } |
| 31 | 30 | ||
| 32 | If this list/array is made lock free using rcu as in changing the | 31 | 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 | 32 | 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 | 33 | in search_and_reference to rcu_read_lock(), the atomic_get in |
| 35 | search_and_reference could potentially hold reference to an element which | 34 | 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 | 35 | has already been deleted from the list/array. atomic_inc_not_zero takes |
| 37 | care of this scenario. search_and_reference should look as; | 36 | care of this scenario. search_and_reference should look as; |
| 38 | 37 | ||
| 39 | 1. 2. | 38 | 1. 2. |
| 40 | add() search_and_reference() | 39 | add() search_and_reference() |
| 41 | { { | 40 | { { |
| 42 | alloc_object rcu_read_lock(); | 41 | alloc_object rcu_read_lock(); |
| 43 | ... search_for_element | 42 | ... search_for_element |
| 44 | atomic_set(&el->rc, 1); if (rcuref_inc_lf(&el->rc)) { | 43 | atomic_set(&el->rc, 1); if (atomic_inc_not_zero(&el->rc)) { |
| 45 | write_lock(&list_lock); rcu_read_unlock(); | 44 | write_lock(&list_lock); rcu_read_unlock(); |
| 46 | return FAIL; | 45 | return FAIL; |
| 47 | add_element } | 46 | add_element } |
| 48 | ... ... | 47 | ... ... |
| 49 | write_unlock(&list_lock); rcu_read_unlock(); | 48 | write_unlock(&list_lock); rcu_read_unlock(); |
| 50 | } } | 49 | } } |
| 51 | 3. 4. | 50 | 3. 4. |
| 52 | release_referenced() delete() | 51 | release_referenced() delete() |
| 53 | { { | 52 | { { |
| 54 | ... write_lock(&list_lock); | 53 | ... write_lock(&list_lock); |
| 55 | rcuref_dec(&el->rc, relfunc) ... | 54 | atomic_dec(&el->rc, relfunc) ... |
| 56 | ... delete_element | 55 | ... delete_element |
| 57 | } write_unlock(&list_lock); | 56 | } write_unlock(&list_lock); |
| 58 | ... | 57 | ... |
| 59 | if (rcuref_dec_and_test(&el->rc)) | 58 | if (atomic_dec_and_test(&el->rc)) |
| 60 | call_rcu(&el->head, el_free); | 59 | call_rcu(&el->head, el_free); |
| 61 | ... | 60 | ... |
| 62 | } | 61 | } |
| 63 | 62 | ||
| 64 | Sometimes, reference to the element need to be obtained in the | 63 | 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 | 64 | update (write) stream. In such cases, atomic_inc_not_zero might be an |
| 66 | since the spinlock serialising list updates are held. rcuref_inc | 65 | overkill since the spinlock serialising list updates are held. atomic_inc |
| 67 | is to be used in such cases. | 66 | is to be used in such cases. |
| 68 | For arches which do not have cmpxchg rcuref_inc_lf | 67 | |
| 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. | ||