rbtree_latch.h 6.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214
  1. /* SPDX-License-Identifier: GPL-2.0 */
  2. /*
  3. * Latched RB-trees
  4. *
  5. * Copyright (C) 2015 Intel Corp., Peter Zijlstra <peterz@infradead.org>
  6. *
  7. * Since RB-trees have non-atomic modifications they're not immediately suited
  8. * for RCU/lockless queries. Even though we made RB-tree lookups non-fatal for
  9. * lockless lookups; we cannot guarantee they return a correct result.
  10. *
  11. * The simplest solution is a seqlock + RB-tree, this will allow lockless
  12. * lookups; but has the constraint (inherent to the seqlock) that read sides
  13. * cannot nest in write sides.
  14. *
  15. * If we need to allow unconditional lookups (say as required for NMI context
  16. * usage) we need a more complex setup; this data structure provides this by
  17. * employing the latch technique -- see @raw_write_seqcount_latch -- to
  18. * implement a latched RB-tree which does allow for unconditional lookups by
  19. * virtue of always having (at least) one stable copy of the tree.
  20. *
  21. * However, while we have the guarantee that there is at all times one stable
  22. * copy, this does not guarantee an iteration will not observe modifications.
  23. * What might have been a stable copy at the start of the iteration, need not
  24. * remain so for the duration of the iteration.
  25. *
  26. * Therefore, this does require a lockless RB-tree iteration to be non-fatal;
  27. * see the comment in lib/rbtree.c. Note however that we only require the first
  28. * condition -- not seeing partial stores -- because the latch thing isolates
  29. * us from loops. If we were to interrupt a modification the lookup would be
  30. * pointed at the stable tree and complete while the modification was halted.
  31. */
  32. #ifndef RB_TREE_LATCH_H
  33. #define RB_TREE_LATCH_H
  34. #include <linux/rbtree.h>
  35. #include <linux/seqlock.h>
  36. #include <linux/rcupdate.h>
  37. struct latch_tree_node {
  38. struct rb_node node[2];
  39. };
  40. struct latch_tree_root {
  41. seqcount_latch_t seq;
  42. struct rb_root tree[2];
  43. };
  44. /**
  45. * latch_tree_ops - operators to define the tree order
  46. * @less: used for insertion; provides the (partial) order between two elements.
  47. * @comp: used for lookups; provides the order between the search key and an element.
  48. *
  49. * The operators are related like:
  50. *
  51. * comp(a->key,b) < 0 := less(a,b)
  52. * comp(a->key,b) > 0 := less(b,a)
  53. * comp(a->key,b) == 0 := !less(a,b) && !less(b,a)
  54. *
  55. * If these operators define a partial order on the elements we make no
  56. * guarantee on which of the elements matching the key is found. See
  57. * latch_tree_find().
  58. */
  59. struct latch_tree_ops {
  60. bool (*less)(struct latch_tree_node *a, struct latch_tree_node *b);
  61. int (*comp)(void *key, struct latch_tree_node *b);
  62. };
  63. static __always_inline struct latch_tree_node *
  64. __lt_from_rb(struct rb_node *node, int idx)
  65. {
  66. return container_of(node, struct latch_tree_node, node[idx]);
  67. }
  68. static __always_inline void
  69. __lt_insert(struct latch_tree_node *ltn, struct latch_tree_root *ltr, int idx,
  70. bool (*less)(struct latch_tree_node *a, struct latch_tree_node *b))
  71. {
  72. struct rb_root *root = &ltr->tree[idx];
  73. struct rb_node **link = &root->rb_node;
  74. struct rb_node *node = &ltn->node[idx];
  75. struct rb_node *parent = NULL;
  76. struct latch_tree_node *ltp;
  77. while (*link) {
  78. parent = *link;
  79. ltp = __lt_from_rb(parent, idx);
  80. if (less(ltn, ltp))
  81. link = &parent->rb_left;
  82. else
  83. link = &parent->rb_right;
  84. }
  85. rb_link_node_rcu(node, parent, link);
  86. rb_insert_color(node, root);
  87. }
  88. static __always_inline void
  89. __lt_erase(struct latch_tree_node *ltn, struct latch_tree_root *ltr, int idx)
  90. {
  91. rb_erase(&ltn->node[idx], &ltr->tree[idx]);
  92. }
  93. static __always_inline struct latch_tree_node *
  94. __lt_find(void *key, struct latch_tree_root *ltr, int idx,
  95. int (*comp)(void *key, struct latch_tree_node *node))
  96. {
  97. struct rb_node *node = rcu_dereference_raw(ltr->tree[idx].rb_node);
  98. struct latch_tree_node *ltn;
  99. int c;
  100. while (node) {
  101. ltn = __lt_from_rb(node, idx);
  102. c = comp(key, ltn);
  103. if (c < 0)
  104. node = rcu_dereference_raw(node->rb_left);
  105. else if (c > 0)
  106. node = rcu_dereference_raw(node->rb_right);
  107. else
  108. return ltn;
  109. }
  110. return NULL;
  111. }
  112. /**
  113. * latch_tree_insert() - insert @node into the trees @root
  114. * @node: nodes to insert
  115. * @root: trees to insert @node into
  116. * @ops: operators defining the node order
  117. *
  118. * It inserts @node into @root in an ordered fashion such that we can always
  119. * observe one complete tree. See the comment for raw_write_seqcount_latch().
  120. *
  121. * The inserts use rcu_assign_pointer() to publish the element such that the
  122. * tree structure is stored before we can observe the new @node.
  123. *
  124. * All modifications (latch_tree_insert, latch_tree_remove) are assumed to be
  125. * serialized.
  126. */
  127. static __always_inline void
  128. latch_tree_insert(struct latch_tree_node *node,
  129. struct latch_tree_root *root,
  130. const struct latch_tree_ops *ops)
  131. {
  132. raw_write_seqcount_latch(&root->seq);
  133. __lt_insert(node, root, 0, ops->less);
  134. raw_write_seqcount_latch(&root->seq);
  135. __lt_insert(node, root, 1, ops->less);
  136. }
  137. /**
  138. * latch_tree_erase() - removes @node from the trees @root
  139. * @node: nodes to remote
  140. * @root: trees to remove @node from
  141. * @ops: operators defining the node order
  142. *
  143. * Removes @node from the trees @root in an ordered fashion such that we can
  144. * always observe one complete tree. See the comment for
  145. * raw_write_seqcount_latch().
  146. *
  147. * It is assumed that @node will observe one RCU quiescent state before being
  148. * reused of freed.
  149. *
  150. * All modifications (latch_tree_insert, latch_tree_remove) are assumed to be
  151. * serialized.
  152. */
  153. static __always_inline void
  154. latch_tree_erase(struct latch_tree_node *node,
  155. struct latch_tree_root *root,
  156. const struct latch_tree_ops *ops)
  157. {
  158. raw_write_seqcount_latch(&root->seq);
  159. __lt_erase(node, root, 0);
  160. raw_write_seqcount_latch(&root->seq);
  161. __lt_erase(node, root, 1);
  162. }
  163. /**
  164. * latch_tree_find() - find the node matching @key in the trees @root
  165. * @key: search key
  166. * @root: trees to search for @key
  167. * @ops: operators defining the node order
  168. *
  169. * Does a lockless lookup in the trees @root for the node matching @key.
  170. *
  171. * It is assumed that this is called while holding the appropriate RCU read
  172. * side lock.
  173. *
  174. * If the operators define a partial order on the elements (there are multiple
  175. * elements which have the same key value) it is undefined which of these
  176. * elements will be found. Nor is it possible to iterate the tree to find
  177. * further elements with the same key value.
  178. *
  179. * Returns: a pointer to the node matching @key or NULL.
  180. */
  181. static __always_inline struct latch_tree_node *
  182. latch_tree_find(void *key, struct latch_tree_root *root,
  183. const struct latch_tree_ops *ops)
  184. {
  185. struct latch_tree_node *node;
  186. unsigned int seq;
  187. do {
  188. seq = raw_read_seqcount_latch(&root->seq);
  189. node = __lt_find(key, root, seq & 1, ops->comp);
  190. } while (read_seqcount_latch_retry(&root->seq, seq));
  191. return node;
  192. }
  193. #endif /* RB_TREE_LATCH_H */