Dipankar Sarma | c0dfb29 | 2005-09-09 13:04:09 -0700 | [diff] [blame] | 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. |