rcuref.txt 4.2 KB

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