4 * Copyright (C) 2015 Intel Corp., Peter Zijlstra <peterz@infradead.org>
6 * Since RB-trees have non-atomic modifications they're not immediately suited
7 * for RCU/lockless queries. Even though we made RB-tree lookups non-fatal for
8 * lockless lookups; we cannot guarantee they return a correct result.
10 * The simplest solution is a seqlock + RB-tree, this will allow lockless
11 * lookups; but has the constraint (inherent to the seqlock) that read sides
12 * cannot nest in write sides.
14 * If we need to allow unconditional lookups (say as required for NMI context
15 * usage) we need a more complex setup; this data structure provides this by
16 * employing the latch technique -- see @raw_write_seqcount_latch -- to
17 * implement a latched RB-tree which does allow for unconditional lookups by
18 * virtue of always having (at least) one stable copy of the tree.
20 * However, while we have the guarantee that there is at all times one stable
21 * copy, this does not guarantee an iteration will not observe modifications.
22 * What might have been a stable copy at the start of the iteration, need not
23 * remain so for the duration of the iteration.
25 * Therefore, this does require a lockless RB-tree iteration to be non-fatal;
26 * see the comment in lib/rbtree.c. Note however that we only require the first
27 * condition -- not seeing partial stores -- because the latch thing isolates
28 * us from loops. If we were to interrupt a modification the lookup would be
29 * pointed at the stable tree and complete while the modification was halted.
32 #ifndef RB_TREE_LATCH_H
33 #define RB_TREE_LATCH_H
35 #include <linux/rbtree.h>
36 #include <linux/seqlock.h>
38 struct latch_tree_node
{
39 struct rb_node node
[2];
42 struct latch_tree_root
{
44 struct rb_root tree
[2];
48 * latch_tree_ops - operators to define the tree order
49 * @less: used for insertion; provides the (partial) order between two elements.
50 * @comp: used for lookups; provides the order between the search key and an element.
52 * The operators are related like:
54 * comp(a->key,b) < 0 := less(a,b)
55 * comp(a->key,b) > 0 := less(b,a)
56 * comp(a->key,b) == 0 := !less(a,b) && !less(b,a)
58 * If these operators define a partial order on the elements we make no
59 * guarantee on which of the elements matching the key is found. See
62 struct latch_tree_ops
{
63 bool (*less
)(struct latch_tree_node
*a
, struct latch_tree_node
*b
);
64 int (*comp
)(void *key
, struct latch_tree_node
*b
);
67 static __always_inline
struct latch_tree_node
*
68 __lt_from_rb(struct rb_node
*node
, int idx
)
70 return container_of(node
, struct latch_tree_node
, node
[idx
]);
73 static __always_inline
void
74 __lt_insert(struct latch_tree_node
*ltn
, struct latch_tree_root
*ltr
, int idx
,
75 bool (*less
)(struct latch_tree_node
*a
, struct latch_tree_node
*b
))
77 struct rb_root
*root
= <r
->tree
[idx
];
78 struct rb_node
**link
= &root
->rb_node
;
79 struct rb_node
*node
= <n
->node
[idx
];
80 struct rb_node
*parent
= NULL
;
81 struct latch_tree_node
*ltp
;
85 ltp
= __lt_from_rb(parent
, idx
);
88 link
= &parent
->rb_left
;
90 link
= &parent
->rb_right
;
93 rb_link_node_rcu(node
, parent
, link
);
94 rb_insert_color(node
, root
);
97 static __always_inline
void
98 __lt_erase(struct latch_tree_node
*ltn
, struct latch_tree_root
*ltr
, int idx
)
100 rb_erase(<n
->node
[idx
], <r
->tree
[idx
]);
103 static __always_inline
struct latch_tree_node
*
104 __lt_find(void *key
, struct latch_tree_root
*ltr
, int idx
,
105 int (*comp
)(void *key
, struct latch_tree_node
*node
))
107 struct rb_node
*node
= rcu_dereference_raw(ltr
->tree
[idx
].rb_node
);
108 struct latch_tree_node
*ltn
;
112 ltn
= __lt_from_rb(node
, idx
);
116 node
= rcu_dereference_raw(node
->rb_left
);
118 node
= rcu_dereference_raw(node
->rb_right
);
127 * latch_tree_insert() - insert @node into the trees @root
128 * @node: nodes to insert
129 * @root: trees to insert @node into
130 * @ops: operators defining the node order
132 * It inserts @node into @root in an ordered fashion such that we can always
133 * observe one complete tree. See the comment for raw_write_seqcount_latch().
135 * The inserts use rcu_assign_pointer() to publish the element such that the
136 * tree structure is stored before we can observe the new @node.
138 * All modifications (latch_tree_insert, latch_tree_remove) are assumed to be
141 static __always_inline
void
142 latch_tree_insert(struct latch_tree_node
*node
,
143 struct latch_tree_root
*root
,
144 const struct latch_tree_ops
*ops
)
146 raw_write_seqcount_latch(&root
->seq
);
147 __lt_insert(node
, root
, 0, ops
->less
);
148 raw_write_seqcount_latch(&root
->seq
);
149 __lt_insert(node
, root
, 1, ops
->less
);
153 * latch_tree_erase() - removes @node from the trees @root
154 * @node: nodes to remote
155 * @root: trees to remove @node from
156 * @ops: operators defining the node order
158 * Removes @node from the trees @root in an ordered fashion such that we can
159 * always observe one complete tree. See the comment for
160 * raw_write_seqcount_latch().
162 * It is assumed that @node will observe one RCU quiescent state before being
165 * All modifications (latch_tree_insert, latch_tree_remove) are assumed to be
168 static __always_inline
void
169 latch_tree_erase(struct latch_tree_node
*node
,
170 struct latch_tree_root
*root
,
171 const struct latch_tree_ops
*ops
)
173 raw_write_seqcount_latch(&root
->seq
);
174 __lt_erase(node
, root
, 0);
175 raw_write_seqcount_latch(&root
->seq
);
176 __lt_erase(node
, root
, 1);
180 * latch_tree_find() - find the node matching @key in the trees @root
182 * @root: trees to search for @key
183 * @ops: operators defining the node order
185 * Does a lockless lookup in the trees @root for the node matching @key.
187 * It is assumed that this is called while holding the appropriate RCU read
190 * If the operators define a partial order on the elements (there are multiple
191 * elements which have the same key value) it is undefined which of these
192 * elements will be found. Nor is it possible to iterate the tree to find
193 * further elements with the same key value.
195 * Returns: a pointer to the node matching @key or NULL.
197 static __always_inline
struct latch_tree_node
*
198 latch_tree_find(void *key
, struct latch_tree_root
*root
,
199 const struct latch_tree_ops
*ops
)
201 struct latch_tree_node
*node
;
205 seq
= raw_read_seqcount_latch(&root
->seq
);
206 node
= __lt_find(key
, root
, seq
& 1, ops
->comp
);
207 } while (read_seqcount_retry(&root
->seq
, seq
));
212 #endif /* RB_TREE_LATCH_H */
This page took 0.044422 seconds and 5 git commands to generate.