Commit | Line | Data |
---|---|---|
cafe5635 KO |
1 | #ifndef _BCACHE_BTREE_H |
2 | #define _BCACHE_BTREE_H | |
3 | ||
4 | /* | |
5 | * THE BTREE: | |
6 | * | |
7 | * At a high level, bcache's btree is relatively standard b+ tree. All keys and | |
8 | * pointers are in the leaves; interior nodes only have pointers to the child | |
9 | * nodes. | |
10 | * | |
11 | * In the interior nodes, a struct bkey always points to a child btree node, and | |
12 | * the key is the highest key in the child node - except that the highest key in | |
13 | * an interior node is always MAX_KEY. The size field refers to the size on disk | |
14 | * of the child node - this would allow us to have variable sized btree nodes | |
15 | * (handy for keeping the depth of the btree 1 by expanding just the root). | |
16 | * | |
17 | * Btree nodes are themselves log structured, but this is hidden fairly | |
18 | * thoroughly. Btree nodes on disk will in practice have extents that overlap | |
19 | * (because they were written at different times), but in memory we never have | |
20 | * overlapping extents - when we read in a btree node from disk, the first thing | |
21 | * we do is resort all the sets of keys with a mergesort, and in the same pass | |
22 | * we check for overlapping extents and adjust them appropriately. | |
23 | * | |
24 | * struct btree_op is a central interface to the btree code. It's used for | |
25 | * specifying read vs. write locking, and the embedded closure is used for | |
26 | * waiting on IO or reserve memory. | |
27 | * | |
28 | * BTREE CACHE: | |
29 | * | |
30 | * Btree nodes are cached in memory; traversing the btree might require reading | |
31 | * in btree nodes which is handled mostly transparently. | |
32 | * | |
33 | * bch_btree_node_get() looks up a btree node in the cache and reads it in from | |
34 | * disk if necessary. This function is almost never called directly though - the | |
35 | * btree() macro is used to get a btree node, call some function on it, and | |
36 | * unlock the node after the function returns. | |
37 | * | |
38 | * The root is special cased - it's taken out of the cache's lru (thus pinning | |
39 | * it in memory), so we can find the root of the btree by just dereferencing a | |
40 | * pointer instead of looking it up in the cache. This makes locking a bit | |
41 | * tricky, since the root pointer is protected by the lock in the btree node it | |
42 | * points to - the btree_root() macro handles this. | |
43 | * | |
44 | * In various places we must be able to allocate memory for multiple btree nodes | |
45 | * in order to make forward progress. To do this we use the btree cache itself | |
46 | * as a reserve; if __get_free_pages() fails, we'll find a node in the btree | |
47 | * cache we can reuse. We can't allow more than one thread to be doing this at a | |
48 | * time, so there's a lock, implemented by a pointer to the btree_op closure - | |
49 | * this allows the btree_root() macro to implicitly release this lock. | |
50 | * | |
51 | * BTREE IO: | |
52 | * | |
53 | * Btree nodes never have to be explicitly read in; bch_btree_node_get() handles | |
54 | * this. | |
55 | * | |
56 | * For writing, we have two btree_write structs embeddded in struct btree - one | |
57 | * write in flight, and one being set up, and we toggle between them. | |
58 | * | |
59 | * Writing is done with a single function - bch_btree_write() really serves two | |
60 | * different purposes and should be broken up into two different functions. When | |
61 | * passing now = false, it merely indicates that the node is now dirty - calling | |
62 | * it ensures that the dirty keys will be written at some point in the future. | |
63 | * | |
64 | * When passing now = true, bch_btree_write() causes a write to happen | |
65 | * "immediately" (if there was already a write in flight, it'll cause the write | |
66 | * to happen as soon as the previous write completes). It returns immediately | |
67 | * though - but it takes a refcount on the closure in struct btree_op you passed | |
68 | * to it, so a closure_sync() later can be used to wait for the write to | |
69 | * complete. | |
70 | * | |
71 | * This is handy because btree_split() and garbage collection can issue writes | |
72 | * in parallel, reducing the amount of time they have to hold write locks. | |
73 | * | |
74 | * LOCKING: | |
75 | * | |
76 | * When traversing the btree, we may need write locks starting at some level - | |
77 | * inserting a key into the btree will typically only require a write lock on | |
78 | * the leaf node. | |
79 | * | |
80 | * This is specified with the lock field in struct btree_op; lock = 0 means we | |
81 | * take write locks at level <= 0, i.e. only leaf nodes. bch_btree_node_get() | |
82 | * checks this field and returns the node with the appropriate lock held. | |
83 | * | |
84 | * If, after traversing the btree, the insertion code discovers it has to split | |
85 | * then it must restart from the root and take new locks - to do this it changes | |
86 | * the lock field and returns -EINTR, which causes the btree_root() macro to | |
87 | * loop. | |
88 | * | |
89 | * Handling cache misses require a different mechanism for upgrading to a write | |
90 | * lock. We do cache lookups with only a read lock held, but if we get a cache | |
91 | * miss and we wish to insert this data into the cache, we have to insert a | |
92 | * placeholder key to detect races - otherwise, we could race with a write and | |
93 | * overwrite the data that was just written to the cache with stale data from | |
94 | * the backing device. | |
95 | * | |
96 | * For this we use a sequence number that write locks and unlocks increment - to | |
97 | * insert the check key it unlocks the btree node and then takes a write lock, | |
98 | * and fails if the sequence number doesn't match. | |
99 | */ | |
100 | ||
101 | #include "bset.h" | |
102 | #include "debug.h" | |
103 | ||
104 | struct btree_write { | |
cafe5635 KO |
105 | atomic_t *journal; |
106 | ||
107 | /* If btree_split() frees a btree node, it writes a new pointer to that | |
108 | * btree node indicating it was freed; it takes a refcount on | |
109 | * c->prio_blocked because we can't write the gens until the new | |
110 | * pointer is on disk. This allows btree_write_endio() to release the | |
111 | * refcount that btree_split() took. | |
112 | */ | |
113 | int prio_blocked; | |
114 | }; | |
115 | ||
116 | struct btree { | |
117 | /* Hottest entries first */ | |
118 | struct hlist_node hash; | |
119 | ||
120 | /* Key/pointer for this btree node */ | |
121 | BKEY_PADDED(key); | |
122 | ||
123 | /* Single bit - set when accessed, cleared by shrinker */ | |
124 | unsigned long accessed; | |
125 | unsigned long seq; | |
126 | struct rw_semaphore lock; | |
127 | struct cache_set *c; | |
d6fd3b11 | 128 | struct btree *parent; |
cafe5635 KO |
129 | |
130 | unsigned long flags; | |
131 | uint16_t written; /* would be nice to kill */ | |
132 | uint8_t level; | |
133 | uint8_t nsets; | |
134 | uint8_t page_order; | |
135 | ||
136 | /* | |
137 | * Set of sorted keys - the real btree node - plus a binary search tree | |
138 | * | |
139 | * sets[0] is special; set[0]->tree, set[0]->prev and set[0]->data point | |
140 | * to the memory we have allocated for this btree node. Additionally, | |
141 | * set[0]->data points to the entire btree node as it exists on disk. | |
142 | */ | |
143 | struct bset_tree sets[MAX_BSETS]; | |
144 | ||
57943511 | 145 | /* For outstanding btree writes, used as a lock - protects write_idx */ |
cb7a583e KO |
146 | struct closure io; |
147 | struct semaphore io_mutex; | |
cafe5635 | 148 | |
cafe5635 KO |
149 | struct list_head list; |
150 | struct delayed_work work; | |
151 | ||
cafe5635 KO |
152 | struct btree_write writes[2]; |
153 | struct bio *bio; | |
154 | }; | |
155 | ||
156 | #define BTREE_FLAG(flag) \ | |
157 | static inline bool btree_node_ ## flag(struct btree *b) \ | |
158 | { return test_bit(BTREE_NODE_ ## flag, &b->flags); } \ | |
159 | \ | |
160 | static inline void set_btree_node_ ## flag(struct btree *b) \ | |
161 | { set_bit(BTREE_NODE_ ## flag, &b->flags); } \ | |
162 | ||
163 | enum btree_flags { | |
cafe5635 KO |
164 | BTREE_NODE_io_error, |
165 | BTREE_NODE_dirty, | |
166 | BTREE_NODE_write_idx, | |
167 | }; | |
168 | ||
cafe5635 KO |
169 | BTREE_FLAG(io_error); |
170 | BTREE_FLAG(dirty); | |
171 | BTREE_FLAG(write_idx); | |
172 | ||
173 | static inline struct btree_write *btree_current_write(struct btree *b) | |
174 | { | |
175 | return b->writes + btree_node_write_idx(b); | |
176 | } | |
177 | ||
178 | static inline struct btree_write *btree_prev_write(struct btree *b) | |
179 | { | |
180 | return b->writes + (btree_node_write_idx(b) ^ 1); | |
181 | } | |
182 | ||
183 | static inline unsigned bset_offset(struct btree *b, struct bset *i) | |
184 | { | |
185 | return (((size_t) i) - ((size_t) b->sets->data)) >> 9; | |
186 | } | |
187 | ||
88b9f8c4 KO |
188 | static inline struct bset *btree_bset_first(struct btree *b) |
189 | { | |
190 | return b->sets->data; | |
191 | } | |
192 | ||
193 | static inline unsigned bset_byte_offset(struct btree *b, struct bset *i) | |
194 | { | |
195 | return ((size_t) i) - ((size_t) b->sets->data); | |
196 | } | |
197 | ||
198 | static inline unsigned bset_sector_offset(struct btree *b, struct bset *i) | |
199 | { | |
200 | return (((void *) i) - ((void *) btree_bset_first(b))) >> 9; | |
201 | } | |
202 | ||
203 | static inline unsigned bset_block_offset(struct btree *b, struct bset *i) | |
204 | { | |
205 | return bset_sector_offset(b, i) >> b->c->block_bits; | |
206 | } | |
207 | ||
cafe5635 KO |
208 | static inline struct bset *write_block(struct btree *b) |
209 | { | |
210 | return ((void *) b->sets[0].data) + b->written * block_bytes(b->c); | |
211 | } | |
212 | ||
213 | static inline bool bset_written(struct btree *b, struct bset_tree *t) | |
214 | { | |
215 | return t->data < write_block(b); | |
216 | } | |
217 | ||
218 | static inline bool bkey_written(struct btree *b, struct bkey *k) | |
219 | { | |
220 | return k < write_block(b)->start; | |
221 | } | |
222 | ||
223 | static inline void set_gc_sectors(struct cache_set *c) | |
224 | { | |
a1f0358b | 225 | atomic_set(&c->sectors_to_gc, c->sb.bucket_size * c->nbuckets / 16); |
cafe5635 KO |
226 | } |
227 | ||
cafe5635 KO |
228 | static inline struct bkey *bch_btree_iter_init(struct btree *b, |
229 | struct btree_iter *iter, | |
230 | struct bkey *search) | |
231 | { | |
232 | return __bch_btree_iter_init(b, iter, search, b->sets); | |
233 | } | |
234 | ||
d5cc66e9 KO |
235 | static inline bool bch_ptr_invalid(struct btree *b, const struct bkey *k) |
236 | { | |
237 | if (b->level) | |
238 | return bch_btree_ptr_invalid(b->c, k); | |
239 | else | |
240 | return bch_extent_ptr_invalid(b->c, k); | |
241 | } | |
242 | ||
3a3b6a4e | 243 | void bkey_put(struct cache_set *c, struct bkey *k); |
e7c590eb | 244 | |
cafe5635 KO |
245 | /* Looping macros */ |
246 | ||
247 | #define for_each_cached_btree(b, c, iter) \ | |
248 | for (iter = 0; \ | |
249 | iter < ARRAY_SIZE((c)->bucket_hash); \ | |
250 | iter++) \ | |
251 | hlist_for_each_entry_rcu((b), (c)->bucket_hash + iter, hash) | |
252 | ||
253 | #define for_each_key_filter(b, k, iter, filter) \ | |
254 | for (bch_btree_iter_init((b), (iter), NULL); \ | |
255 | ((k) = bch_btree_iter_next_filter((iter), b, filter));) | |
256 | ||
257 | #define for_each_key(b, k, iter) \ | |
258 | for (bch_btree_iter_init((b), (iter), NULL); \ | |
259 | ((k) = bch_btree_iter_next(iter));) | |
260 | ||
261 | /* Recursing down the btree */ | |
262 | ||
263 | struct btree_op { | |
78365411 KO |
264 | /* for waiting on btree reserve in btree_split() */ |
265 | wait_queue_t wait; | |
266 | ||
cafe5635 KO |
267 | /* Btree level at which we start taking write locks */ |
268 | short lock; | |
269 | ||
cafe5635 | 270 | unsigned insert_collision:1; |
cafe5635 KO |
271 | }; |
272 | ||
b54d6934 KO |
273 | static inline void bch_btree_op_init(struct btree_op *op, int write_lock_level) |
274 | { | |
275 | memset(op, 0, sizeof(struct btree_op)); | |
78365411 | 276 | init_wait(&op->wait); |
b54d6934 KO |
277 | op->lock = write_lock_level; |
278 | } | |
cafe5635 KO |
279 | |
280 | static inline void rw_lock(bool w, struct btree *b, int level) | |
281 | { | |
282 | w ? down_write_nested(&b->lock, level + 1) | |
283 | : down_read_nested(&b->lock, level + 1); | |
284 | if (w) | |
285 | b->seq++; | |
286 | } | |
287 | ||
288 | static inline void rw_unlock(bool w, struct btree *b) | |
289 | { | |
cafe5635 KO |
290 | if (w) |
291 | b->seq++; | |
292 | (w ? up_write : up_read)(&b->lock); | |
293 | } | |
294 | ||
57943511 | 295 | void bch_btree_node_read(struct btree *); |
57943511 | 296 | void bch_btree_node_write(struct btree *, struct closure *); |
cafe5635 | 297 | |
cafe5635 | 298 | void bch_btree_set_root(struct btree *); |
bc9389ee | 299 | struct btree *bch_btree_node_alloc(struct cache_set *, int, bool); |
e8e1d468 | 300 | struct btree *bch_btree_node_get(struct cache_set *, struct bkey *, int, bool); |
cafe5635 | 301 | |
e7c590eb KO |
302 | int bch_btree_insert_check_key(struct btree *, struct btree_op *, |
303 | struct bkey *); | |
cc7b8819 KO |
304 | int bch_btree_insert(struct cache_set *, struct keylist *, |
305 | atomic_t *, struct bkey *); | |
cafe5635 | 306 | |
72a44517 | 307 | int bch_gc_thread_start(struct cache_set *); |
cafe5635 | 308 | size_t bch_btree_gc_finish(struct cache_set *); |
72a44517 | 309 | void bch_moving_gc(struct cache_set *); |
c18536a7 | 310 | int bch_btree_check(struct cache_set *); |
cafe5635 KO |
311 | uint8_t __bch_btree_mark_key(struct cache_set *, int, struct bkey *); |
312 | ||
72a44517 KO |
313 | static inline void wake_up_gc(struct cache_set *c) |
314 | { | |
315 | if (c->gc_thread) | |
316 | wake_up_process(c->gc_thread); | |
317 | } | |
318 | ||
48dad8ba KO |
319 | #define MAP_DONE 0 |
320 | #define MAP_CONTINUE 1 | |
321 | ||
322 | #define MAP_ALL_NODES 0 | |
323 | #define MAP_LEAF_NODES 1 | |
324 | ||
325 | #define MAP_END_KEY 1 | |
326 | ||
327 | typedef int (btree_map_nodes_fn)(struct btree_op *, struct btree *); | |
328 | int __bch_btree_map_nodes(struct btree_op *, struct cache_set *, | |
329 | struct bkey *, btree_map_nodes_fn *, int); | |
330 | ||
331 | static inline int bch_btree_map_nodes(struct btree_op *op, struct cache_set *c, | |
332 | struct bkey *from, btree_map_nodes_fn *fn) | |
333 | { | |
334 | return __bch_btree_map_nodes(op, c, from, fn, MAP_ALL_NODES); | |
335 | } | |
336 | ||
337 | static inline int bch_btree_map_leaf_nodes(struct btree_op *op, | |
338 | struct cache_set *c, | |
339 | struct bkey *from, | |
340 | btree_map_nodes_fn *fn) | |
341 | { | |
342 | return __bch_btree_map_nodes(op, c, from, fn, MAP_LEAF_NODES); | |
343 | } | |
344 | ||
345 | typedef int (btree_map_keys_fn)(struct btree_op *, struct btree *, | |
346 | struct bkey *); | |
347 | int bch_btree_map_keys(struct btree_op *, struct cache_set *, | |
348 | struct bkey *, btree_map_keys_fn *, int); | |
349 | ||
350 | typedef bool (keybuf_pred_fn)(struct keybuf *, struct bkey *); | |
351 | ||
72c27061 | 352 | void bch_keybuf_init(struct keybuf *); |
48dad8ba KO |
353 | void bch_refill_keybuf(struct cache_set *, struct keybuf *, |
354 | struct bkey *, keybuf_pred_fn *); | |
cafe5635 KO |
355 | bool bch_keybuf_check_overlapping(struct keybuf *, struct bkey *, |
356 | struct bkey *); | |
357 | void bch_keybuf_del(struct keybuf *, struct keybuf_key *); | |
358 | struct keybuf_key *bch_keybuf_next(struct keybuf *); | |
72c27061 KO |
359 | struct keybuf_key *bch_keybuf_next_rescan(struct cache_set *, struct keybuf *, |
360 | struct bkey *, keybuf_pred_fn *); | |
cafe5635 KO |
361 | |
362 | #endif |