Nick Piggin | 095975d | 2006-01-08 01:02:19 -0800 | [diff] [blame] | 1 | Refcounter design for elements of lists/arrays protected by RCU. |
Dipankar Sarma | c0dfb29 | 2005-09-09 13:04:09 -0700 | [diff] [blame] | 2 | |
| 3 | Refcounting on elements of lists which are protected by traditional |
| 4 | reader/writer spinlocks or semaphores are straight forward as in: |
| 5 | |
Nick Piggin | 095975d | 2006-01-08 01:02:19 -0800 | [diff] [blame] | 6 | 1. 2. |
| 7 | add() search_and_reference() |
| 8 | { { |
| 9 | alloc_object read_lock(&list_lock); |
| 10 | ... search_for_element |
| 11 | atomic_set(&el->rc, 1); atomic_inc(&el->rc); |
| 12 | write_lock(&list_lock); ... |
| 13 | add_element read_unlock(&list_lock); |
| 14 | ... ... |
| 15 | write_unlock(&list_lock); } |
Dipankar Sarma | c0dfb29 | 2005-09-09 13:04:09 -0700 | [diff] [blame] | 16 | } |
| 17 | |
| 18 | 3. 4. |
| 19 | release_referenced() delete() |
| 20 | { { |
Nick Piggin | 095975d | 2006-01-08 01:02:19 -0800 | [diff] [blame] | 21 | ... write_lock(&list_lock); |
| 22 | atomic_dec(&el->rc, relfunc) ... |
| 23 | ... delete_element |
| 24 | } write_unlock(&list_lock); |
| 25 | ... |
| 26 | if (atomic_dec_and_test(&el->rc)) |
| 27 | kfree(el); |
| 28 | ... |
Dipankar Sarma | c0dfb29 | 2005-09-09 13:04:09 -0700 | [diff] [blame] | 29 | } |
| 30 | |
| 31 | If this list/array is made lock free using rcu as in changing the |
| 32 | write_lock in add() and delete() to spin_lock and changing read_lock |
Nick Piggin | 095975d | 2006-01-08 01:02:19 -0800 | [diff] [blame] | 33 | in search_and_reference to rcu_read_lock(), the atomic_get in |
Dipankar Sarma | c0dfb29 | 2005-09-09 13:04:09 -0700 | [diff] [blame] | 34 | search_and_reference could potentially hold reference to an element which |
Nick Piggin | 095975d | 2006-01-08 01:02:19 -0800 | [diff] [blame] | 35 | has already been deleted from the list/array. atomic_inc_not_zero takes |
Dipankar Sarma | c0dfb29 | 2005-09-09 13:04:09 -0700 | [diff] [blame] | 36 | care of this scenario. search_and_reference should look as; |
| 37 | |
| 38 | 1. 2. |
| 39 | add() search_and_reference() |
| 40 | { { |
Nick Piggin | 095975d | 2006-01-08 01:02:19 -0800 | [diff] [blame] | 41 | alloc_object rcu_read_lock(); |
| 42 | ... search_for_element |
| 43 | atomic_set(&el->rc, 1); if (atomic_inc_not_zero(&el->rc)) { |
| 44 | write_lock(&list_lock); rcu_read_unlock(); |
| 45 | return FAIL; |
| 46 | add_element } |
| 47 | ... ... |
| 48 | write_unlock(&list_lock); rcu_read_unlock(); |
Dipankar Sarma | c0dfb29 | 2005-09-09 13:04:09 -0700 | [diff] [blame] | 49 | } } |
| 50 | 3. 4. |
| 51 | release_referenced() delete() |
| 52 | { { |
Nick Piggin | 095975d | 2006-01-08 01:02:19 -0800 | [diff] [blame] | 53 | ... write_lock(&list_lock); |
| 54 | atomic_dec(&el->rc, relfunc) ... |
| 55 | ... delete_element |
| 56 | } write_unlock(&list_lock); |
| 57 | ... |
| 58 | if (atomic_dec_and_test(&el->rc)) |
| 59 | call_rcu(&el->head, el_free); |
| 60 | ... |
Dipankar Sarma | c0dfb29 | 2005-09-09 13:04:09 -0700 | [diff] [blame] | 61 | } |
| 62 | |
| 63 | Sometimes, reference to the element need to be obtained in the |
Nick Piggin | 095975d | 2006-01-08 01:02:19 -0800 | [diff] [blame] | 64 | update (write) stream. In such cases, atomic_inc_not_zero might be an |
| 65 | overkill since the spinlock serialising list updates are held. atomic_inc |
Dipankar Sarma | c0dfb29 | 2005-09-09 13:04:09 -0700 | [diff] [blame] | 66 | is to be used in such cases. |
Nick Piggin | 095975d | 2006-01-08 01:02:19 -0800 | [diff] [blame] | 67 | |