include/linux/rbtree_latch.h

   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
  33 #ifndef RB_TREE_LATCH_H
  34 #define RB_TREE_LATCH_H
  35
  36 #include <linux/rbtree.h>
  37 #include <linux/seqlock.h>
  38
  39 struct latch_tree_node {
  40         struct rb_node node[2];
  41 };
  42
  43 struct latch_tree_root {
  44         seqcount_t      seq;
  45         struct rb_root  tree[2];
  46 };
  47
  48 /**
  49  * latch_tree_ops - operators to define the tree order
  50  * @less: used for insertion; provides the (partial) order between two elements.
  51  * @comp: used for lookups; provides the order between the search key and an element.
  52  *
  53  * The operators are related like:
  54  *
  55  *      comp(a->key,b) < 0  := less(a,b)
  56  *      comp(a->key,b) > 0  := less(b,a)
  57  *      comp(a->key,b) == 0 := !less(a,b) && !less(b,a)
  58  *
  59  * If these operators define a partial order on the elements we make no
  60  * guarantee on which of the elements matching the key is found. See
  61  * latch_tree_find().
  62  */
  63 struct latch_tree_ops {
  64         bool (*less)(struct latch_tree_node *a, struct latch_tree_node *b);
  65         int  (*comp)(void *key,                 struct latch_tree_node *b);
  66 };
  67
  68 static __always_inline struct latch_tree_node *
  69 __lt_from_rb(struct rb_node *node, int idx)
  70 {
  71         return container_of(node, struct latch_tree_node, node[idx]);
  72 }
  73
  74 static __always_inline void
  75 __lt_insert(struct latch_tree_node *ltn, struct latch_tree_root *ltr, int idx,
  76             bool (*less)(struct latch_tree_node *a, struct latch_tree_node *b))
  77 {
  78         struct rb_root *root = &ltr->tree[idx];
  79         struct rb_node **link = &root->rb_node;
  80         struct rb_node *node = &ltn->node[idx];
  81         struct rb_node *parent = NULL;
  82         struct latch_tree_node *ltp;
  83
  84         while (*link) {
  85                 parent = *link;
  86                 ltp = __lt_from_rb(parent, idx);
  87
  88                 if (less(ltn, ltp))
  89                         link = &parent->rb_left;
  90                 else
  91                         link = &parent->rb_right;
  92         }
  93
  94         rb_link_node_rcu(node, parent, link);
  95         rb_insert_color(node, root);
  96 }
  97
  98 static __always_inline void
  99 __lt_erase(struct latch_tree_node *ltn, struct latch_tree_root *ltr, int idx)
 100 {
 101         rb_erase(&ltn->node[idx], &ltr->tree[idx]);
 102 }
 103
 104 static __always_inline struct latch_tree_node *
 105 __lt_find(void *key, struct latch_tree_root *ltr, int idx,
 106           int (*comp)(void *key, struct latch_tree_node *node))
 107 {
 108         struct rb_node *node = rcu_dereference_raw(ltr->tree[idx].rb_node);
 109         struct latch_tree_node *ltn;
 110         int c;
 111
 112         while (node) {
 113                 ltn = __lt_from_rb(node, idx);
 114                 c = comp(key, ltn);
 115
 116                 if (c < 0)
 117                         node = rcu_dereference_raw(node->rb_left);
 118                 else if (c > 0)
 119                         node = rcu_dereference_raw(node->rb_right);
 120                 else
 121                         return ltn;
 122         }
 123
 124         return NULL;
 125 }
 126
 127 /**
 128  * latch_tree_insert() - insert @node into the trees @root
 129  * @node: nodes to insert
 130  * @root: trees to insert @node into
 131  * @ops: operators defining the node order
 132  *
 133  * It inserts @node into @root in an ordered fashion such that we can always
 134  * observe one complete tree. See the comment for raw_write_seqcount_latch().
 135  *
 136  * The inserts use rcu_assign_pointer() to publish the element such that the
 137  * tree structure is stored before we can observe the new @node.
 138  *
 139  * All modifications (latch_tree_insert, latch_tree_remove) are assumed to be
 140  * serialized.
 141  */
 142 static __always_inline void
 143 latch_tree_insert(struct latch_tree_node *node,
 144                   struct latch_tree_root *root,
 145                   const struct latch_tree_ops *ops)
 146 {
 147         raw_write_seqcount_latch(&root->seq);
 148         __lt_insert(node, root, 0, ops->less);
 149         raw_write_seqcount_latch(&root->seq);
 150         __lt_insert(node, root, 1, ops->less);
 151 }
 152
 153 /**
 154  * latch_tree_erase() - removes @node from the trees @root
 155  * @node: nodes to remote
 156  * @root: trees to remove @node from
 157  * @ops: operators defining the node order
 158  *
 159  * Removes @node from the trees @root in an ordered fashion such that we can
 160  * always observe one complete tree. See the comment for
 161  * raw_write_seqcount_latch().
 162  *
 163  * It is assumed that @node will observe one RCU quiescent state before being
 164  * reused of freed.
 165  *
 166  * All modifications (latch_tree_insert, latch_tree_remove) are assumed to be
 167  * serialized.
 168  */
 169 static __always_inline void
 170 latch_tree_erase(struct latch_tree_node *node,
 171                  struct latch_tree_root *root,
 172                  const struct latch_tree_ops *ops)
 173 {
 174         raw_write_seqcount_latch(&root->seq);
 175         __lt_erase(node, root, 0);
 176         raw_write_seqcount_latch(&root->seq);
 177         __lt_erase(node, root, 1);
 178 }
 179
 180 /**
 181  * latch_tree_find() - find the node matching @key in the trees @root
 182  * @key: search key
 183  * @root: trees to search for @key
 184  * @ops: operators defining the node order
 185  *
 186  * Does a lockless lookup in the trees @root for the node matching @key.
 187  *
 188  * It is assumed that this is called while holding the appropriate RCU read
 189  * side lock.
 190  *
 191  * If the operators define a partial order on the elements (there are multiple
 192  * elements which have the same key value) it is undefined which of these
 193  * elements will be found. Nor is it possible to iterate the tree to find
 194  * further elements with the same key value.
 195  *
 196  * Returns: a pointer to the node matching @key or NULL.
 197  */
 198 static __always_inline struct latch_tree_node *
 199 latch_tree_find(void *key, struct latch_tree_root *root,
 200                 const struct latch_tree_ops *ops)
 201 {
 202         struct latch_tree_node *node;
 203         unsigned int seq;
 204
 205         do {
 206                 seq = raw_read_seqcount_latch(&root->seq);
 207                 node = __lt_find(key, root, seq & 1, ops->comp);
 208         } while (read_seqcount_retry(&root->seq, seq));
 209
 210         return node;
 211 }
 212
 213 #endif /* RB_TREE_LATCH_H */