Merge tag 'sirf-iobrg2regmap-for-4.2' of git://git.kernel.org/pub/scm/linux/kernel...
[firefly-linux-kernel-4.4.55.git] / include / linux / rbtree_latch.h
1 /*
2  * Latched RB-trees
3  *
4  * Copyright (C) 2015 Intel Corp., Peter Zijlstra <peterz@infradead.org>
5  *
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.
9  *
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.
13  *
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.
19  *
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.
24  *
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.
30  */
31
32 #ifndef RB_TREE_LATCH_H
33 #define RB_TREE_LATCH_H
34
35 #include <linux/rbtree.h>
36 #include <linux/seqlock.h>
37
38 struct latch_tree_node {
39         struct rb_node node[2];
40 };
41
42 struct latch_tree_root {
43         seqcount_t      seq;
44         struct rb_root  tree[2];
45 };
46
47 /**
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.
51  *
52  * The operators are related like:
53  *
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)
57  *
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
60  * latch_tree_find().
61  */
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);
65 };
66
67 static __always_inline struct latch_tree_node *
68 __lt_from_rb(struct rb_node *node, int idx)
69 {
70         return container_of(node, struct latch_tree_node, node[idx]);
71 }
72
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))
76 {
77         struct rb_root *root = &ltr->tree[idx];
78         struct rb_node **link = &root->rb_node;
79         struct rb_node *node = &ltn->node[idx];
80         struct rb_node *parent = NULL;
81         struct latch_tree_node *ltp;
82
83         while (*link) {
84                 parent = *link;
85                 ltp = __lt_from_rb(parent, idx);
86
87                 if (less(ltn, ltp))
88                         link = &parent->rb_left;
89                 else
90                         link = &parent->rb_right;
91         }
92
93         rb_link_node_rcu(node, parent, link);
94         rb_insert_color(node, root);
95 }
96
97 static __always_inline void
98 __lt_erase(struct latch_tree_node *ltn, struct latch_tree_root *ltr, int idx)
99 {
100         rb_erase(&ltn->node[idx], &ltr->tree[idx]);
101 }
102
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))
106 {
107         struct rb_node *node = rcu_dereference_raw(ltr->tree[idx].rb_node);
108         struct latch_tree_node *ltn;
109         int c;
110
111         while (node) {
112                 ltn = __lt_from_rb(node, idx);
113                 c = comp(key, ltn);
114
115                 if (c < 0)
116                         node = rcu_dereference_raw(node->rb_left);
117                 else if (c > 0)
118                         node = rcu_dereference_raw(node->rb_right);
119                 else
120                         return ltn;
121         }
122
123         return NULL;
124 }
125
126 /**
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
131  *
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().
134  *
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.
137  *
138  * All modifications (latch_tree_insert, latch_tree_remove) are assumed to be
139  * serialized.
140  */
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)
145 {
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);
150 }
151
152 /**
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
157  *
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().
161  *
162  * It is assumed that @node will observe one RCU quiescent state before being
163  * reused of freed.
164  *
165  * All modifications (latch_tree_insert, latch_tree_remove) are assumed to be
166  * serialized.
167  */
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)
172 {
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);
177 }
178
179 /**
180  * latch_tree_find() - find the node matching @key in the trees @root
181  * @key: search key
182  * @root: trees to search for @key
183  * @ops: operators defining the node order
184  *
185  * Does a lockless lookup in the trees @root for the node matching @key.
186  *
187  * It is assumed that this is called while holding the appropriate RCU read
188  * side lock.
189  *
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.
194  *
195  * Returns: a pointer to the node matching @key or NULL.
196  */
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)
200 {
201         struct latch_tree_node *node;
202         unsigned int seq;
203
204         do {
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));
208
209         return node;
210 }
211
212 #endif /* RB_TREE_LATCH_H */