Greg Kroah-Hartman | b244131 | 2017-11-01 15:07:57 +0100 | [diff] [blame] | 1 | /* SPDX-License-Identifier: GPL-2.0 */ |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 2 | #ifndef _BCACHE_BTREE_H |
| 3 | #define _BCACHE_BTREE_H |
| 4 | |
| 5 | /* |
| 6 | * THE BTREE: |
| 7 | * |
| 8 | * At a high level, bcache's btree is relatively standard b+ tree. All keys and |
| 9 | * pointers are in the leaves; interior nodes only have pointers to the child |
| 10 | * nodes. |
| 11 | * |
| 12 | * In the interior nodes, a struct bkey always points to a child btree node, and |
| 13 | * the key is the highest key in the child node - except that the highest key in |
| 14 | * an interior node is always MAX_KEY. The size field refers to the size on disk |
| 15 | * of the child node - this would allow us to have variable sized btree nodes |
| 16 | * (handy for keeping the depth of the btree 1 by expanding just the root). |
| 17 | * |
| 18 | * Btree nodes are themselves log structured, but this is hidden fairly |
| 19 | * thoroughly. Btree nodes on disk will in practice have extents that overlap |
| 20 | * (because they were written at different times), but in memory we never have |
| 21 | * overlapping extents - when we read in a btree node from disk, the first thing |
| 22 | * we do is resort all the sets of keys with a mergesort, and in the same pass |
| 23 | * we check for overlapping extents and adjust them appropriately. |
| 24 | * |
| 25 | * struct btree_op is a central interface to the btree code. It's used for |
| 26 | * specifying read vs. write locking, and the embedded closure is used for |
| 27 | * waiting on IO or reserve memory. |
| 28 | * |
| 29 | * BTREE CACHE: |
| 30 | * |
| 31 | * Btree nodes are cached in memory; traversing the btree might require reading |
| 32 | * in btree nodes which is handled mostly transparently. |
| 33 | * |
| 34 | * bch_btree_node_get() looks up a btree node in the cache and reads it in from |
| 35 | * disk if necessary. This function is almost never called directly though - the |
| 36 | * btree() macro is used to get a btree node, call some function on it, and |
| 37 | * unlock the node after the function returns. |
| 38 | * |
| 39 | * The root is special cased - it's taken out of the cache's lru (thus pinning |
| 40 | * it in memory), so we can find the root of the btree by just dereferencing a |
| 41 | * pointer instead of looking it up in the cache. This makes locking a bit |
| 42 | * tricky, since the root pointer is protected by the lock in the btree node it |
| 43 | * points to - the btree_root() macro handles this. |
| 44 | * |
| 45 | * In various places we must be able to allocate memory for multiple btree nodes |
| 46 | * in order to make forward progress. To do this we use the btree cache itself |
| 47 | * as a reserve; if __get_free_pages() fails, we'll find a node in the btree |
| 48 | * cache we can reuse. We can't allow more than one thread to be doing this at a |
| 49 | * time, so there's a lock, implemented by a pointer to the btree_op closure - |
| 50 | * this allows the btree_root() macro to implicitly release this lock. |
| 51 | * |
| 52 | * BTREE IO: |
| 53 | * |
| 54 | * Btree nodes never have to be explicitly read in; bch_btree_node_get() handles |
| 55 | * this. |
| 56 | * |
| 57 | * For writing, we have two btree_write structs embeddded in struct btree - one |
| 58 | * write in flight, and one being set up, and we toggle between them. |
| 59 | * |
| 60 | * Writing is done with a single function - bch_btree_write() really serves two |
| 61 | * different purposes and should be broken up into two different functions. When |
| 62 | * passing now = false, it merely indicates that the node is now dirty - calling |
| 63 | * it ensures that the dirty keys will be written at some point in the future. |
| 64 | * |
| 65 | * When passing now = true, bch_btree_write() causes a write to happen |
| 66 | * "immediately" (if there was already a write in flight, it'll cause the write |
| 67 | * to happen as soon as the previous write completes). It returns immediately |
| 68 | * though - but it takes a refcount on the closure in struct btree_op you passed |
| 69 | * to it, so a closure_sync() later can be used to wait for the write to |
| 70 | * complete. |
| 71 | * |
| 72 | * This is handy because btree_split() and garbage collection can issue writes |
| 73 | * in parallel, reducing the amount of time they have to hold write locks. |
| 74 | * |
| 75 | * LOCKING: |
| 76 | * |
| 77 | * When traversing the btree, we may need write locks starting at some level - |
| 78 | * inserting a key into the btree will typically only require a write lock on |
| 79 | * the leaf node. |
| 80 | * |
| 81 | * This is specified with the lock field in struct btree_op; lock = 0 means we |
| 82 | * take write locks at level <= 0, i.e. only leaf nodes. bch_btree_node_get() |
| 83 | * checks this field and returns the node with the appropriate lock held. |
| 84 | * |
| 85 | * If, after traversing the btree, the insertion code discovers it has to split |
| 86 | * then it must restart from the root and take new locks - to do this it changes |
| 87 | * the lock field and returns -EINTR, which causes the btree_root() macro to |
| 88 | * loop. |
| 89 | * |
| 90 | * Handling cache misses require a different mechanism for upgrading to a write |
| 91 | * lock. We do cache lookups with only a read lock held, but if we get a cache |
| 92 | * miss and we wish to insert this data into the cache, we have to insert a |
| 93 | * placeholder key to detect races - otherwise, we could race with a write and |
| 94 | * overwrite the data that was just written to the cache with stale data from |
| 95 | * the backing device. |
| 96 | * |
| 97 | * For this we use a sequence number that write locks and unlocks increment - to |
| 98 | * insert the check key it unlocks the btree node and then takes a write lock, |
| 99 | * and fails if the sequence number doesn't match. |
| 100 | */ |
| 101 | |
| 102 | #include "bset.h" |
| 103 | #include "debug.h" |
| 104 | |
| 105 | struct btree_write { |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 106 | atomic_t *journal; |
| 107 | |
| 108 | /* If btree_split() frees a btree node, it writes a new pointer to that |
| 109 | * btree node indicating it was freed; it takes a refcount on |
| 110 | * c->prio_blocked because we can't write the gens until the new |
| 111 | * pointer is on disk. This allows btree_write_endio() to release the |
| 112 | * refcount that btree_split() took. |
| 113 | */ |
| 114 | int prio_blocked; |
| 115 | }; |
| 116 | |
| 117 | struct btree { |
| 118 | /* Hottest entries first */ |
| 119 | struct hlist_node hash; |
| 120 | |
| 121 | /* Key/pointer for this btree node */ |
| 122 | BKEY_PADDED(key); |
| 123 | |
| 124 | /* Single bit - set when accessed, cleared by shrinker */ |
| 125 | unsigned long accessed; |
| 126 | unsigned long seq; |
| 127 | struct rw_semaphore lock; |
| 128 | struct cache_set *c; |
Kent Overstreet | d6fd3b1 | 2013-07-24 17:20:19 -0700 | [diff] [blame] | 129 | struct btree *parent; |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 130 | |
Kent Overstreet | 2a28568 | 2014-03-04 16:42:42 -0800 | [diff] [blame] | 131 | struct mutex write_lock; |
| 132 | |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 133 | unsigned long flags; |
| 134 | uint16_t written; /* would be nice to kill */ |
| 135 | uint8_t level; |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 136 | |
Kent Overstreet | a85e968 | 2013-12-20 17:28:16 -0800 | [diff] [blame] | 137 | struct btree_keys keys; |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 138 | |
Kent Overstreet | 5794351 | 2013-04-25 13:58:35 -0700 | [diff] [blame] | 139 | /* For outstanding btree writes, used as a lock - protects write_idx */ |
Kent Overstreet | cb7a583 | 2013-12-16 15:27:25 -0800 | [diff] [blame] | 140 | struct closure io; |
| 141 | struct semaphore io_mutex; |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 142 | |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 143 | struct list_head list; |
| 144 | struct delayed_work work; |
| 145 | |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 146 | struct btree_write writes[2]; |
| 147 | struct bio *bio; |
| 148 | }; |
| 149 | |
| 150 | #define BTREE_FLAG(flag) \ |
| 151 | static inline bool btree_node_ ## flag(struct btree *b) \ |
| 152 | { return test_bit(BTREE_NODE_ ## flag, &b->flags); } \ |
| 153 | \ |
| 154 | static inline void set_btree_node_ ## flag(struct btree *b) \ |
Shenghui Wang | cbb751c | 2018-08-09 15:48:51 +0800 | [diff] [blame] | 155 | { set_bit(BTREE_NODE_ ## flag, &b->flags); } |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 156 | |
| 157 | enum btree_flags { |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 158 | BTREE_NODE_io_error, |
| 159 | BTREE_NODE_dirty, |
| 160 | BTREE_NODE_write_idx, |
| 161 | }; |
| 162 | |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 163 | BTREE_FLAG(io_error); |
| 164 | BTREE_FLAG(dirty); |
| 165 | BTREE_FLAG(write_idx); |
| 166 | |
| 167 | static inline struct btree_write *btree_current_write(struct btree *b) |
| 168 | { |
| 169 | return b->writes + btree_node_write_idx(b); |
| 170 | } |
| 171 | |
| 172 | static inline struct btree_write *btree_prev_write(struct btree *b) |
| 173 | { |
| 174 | return b->writes + (btree_node_write_idx(b) ^ 1); |
| 175 | } |
| 176 | |
Kent Overstreet | 88b9f8c | 2013-12-17 21:46:35 -0800 | [diff] [blame] | 177 | static inline struct bset *btree_bset_first(struct btree *b) |
| 178 | { |
Kent Overstreet | a85e968 | 2013-12-20 17:28:16 -0800 | [diff] [blame] | 179 | return b->keys.set->data; |
Kent Overstreet | 88b9f8c | 2013-12-17 21:46:35 -0800 | [diff] [blame] | 180 | } |
| 181 | |
Kent Overstreet | ee81128 | 2013-12-17 23:49:49 -0800 | [diff] [blame] | 182 | static inline struct bset *btree_bset_last(struct btree *b) |
| 183 | { |
Kent Overstreet | a85e968 | 2013-12-20 17:28:16 -0800 | [diff] [blame] | 184 | return bset_tree_last(&b->keys)->data; |
Kent Overstreet | 88b9f8c | 2013-12-17 21:46:35 -0800 | [diff] [blame] | 185 | } |
| 186 | |
Coly Li | 6f10f7d | 2018-08-11 13:19:44 +0800 | [diff] [blame] | 187 | static inline unsigned int bset_block_offset(struct btree *b, struct bset *i) |
Kent Overstreet | 88b9f8c | 2013-12-17 21:46:35 -0800 | [diff] [blame] | 188 | { |
Kent Overstreet | a85e968 | 2013-12-20 17:28:16 -0800 | [diff] [blame] | 189 | return bset_sector_offset(&b->keys, i) >> b->c->block_bits; |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 190 | } |
| 191 | |
| 192 | static inline void set_gc_sectors(struct cache_set *c) |
| 193 | { |
Kent Overstreet | a1f0358 | 2013-09-10 19:07:00 -0700 | [diff] [blame] | 194 | atomic_set(&c->sectors_to_gc, c->sb.bucket_size * c->nbuckets / 16); |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 195 | } |
| 196 | |
Kent Overstreet | 3a3b6a4 | 2013-07-24 16:46:42 -0700 | [diff] [blame] | 197 | void bkey_put(struct cache_set *c, struct bkey *k); |
Kent Overstreet | e7c590e | 2013-09-10 18:39:16 -0700 | [diff] [blame] | 198 | |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 199 | /* Looping macros */ |
| 200 | |
| 201 | #define for_each_cached_btree(b, c, iter) \ |
| 202 | for (iter = 0; \ |
| 203 | iter < ARRAY_SIZE((c)->bucket_hash); \ |
| 204 | iter++) \ |
| 205 | hlist_for_each_entry_rcu((b), (c)->bucket_hash + iter, hash) |
| 206 | |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 207 | /* Recursing down the btree */ |
| 208 | |
| 209 | struct btree_op { |
Kent Overstreet | 7836541 | 2013-12-17 01:29:34 -0800 | [diff] [blame] | 210 | /* for waiting on btree reserve in btree_split() */ |
Ingo Molnar | ac6424b | 2017-06-20 12:06:13 +0200 | [diff] [blame] | 211 | wait_queue_entry_t wait; |
Kent Overstreet | 7836541 | 2013-12-17 01:29:34 -0800 | [diff] [blame] | 212 | |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 213 | /* Btree level at which we start taking write locks */ |
| 214 | short lock; |
| 215 | |
Coly Li | 6f10f7d | 2018-08-11 13:19:44 +0800 | [diff] [blame] | 216 | unsigned int insert_collision:1; |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 217 | }; |
| 218 | |
Kent Overstreet | b54d693 | 2013-07-24 18:04:18 -0700 | [diff] [blame] | 219 | static inline void bch_btree_op_init(struct btree_op *op, int write_lock_level) |
| 220 | { |
| 221 | memset(op, 0, sizeof(struct btree_op)); |
Kent Overstreet | 7836541 | 2013-12-17 01:29:34 -0800 | [diff] [blame] | 222 | init_wait(&op->wait); |
Kent Overstreet | b54d693 | 2013-07-24 18:04:18 -0700 | [diff] [blame] | 223 | op->lock = write_lock_level; |
| 224 | } |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 225 | |
| 226 | static inline void rw_lock(bool w, struct btree *b, int level) |
| 227 | { |
| 228 | w ? down_write_nested(&b->lock, level + 1) |
| 229 | : down_read_nested(&b->lock, level + 1); |
| 230 | if (w) |
| 231 | b->seq++; |
| 232 | } |
| 233 | |
| 234 | static inline void rw_unlock(bool w, struct btree *b) |
| 235 | { |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 236 | if (w) |
| 237 | b->seq++; |
| 238 | (w ? up_write : up_read)(&b->lock); |
| 239 | } |
| 240 | |
Coly Li | fc2d598 | 2018-08-11 13:19:46 +0800 | [diff] [blame] | 241 | void bch_btree_node_read_done(struct btree *b); |
| 242 | void __bch_btree_node_write(struct btree *b, struct closure *parent); |
| 243 | void bch_btree_node_write(struct btree *b, struct closure *parent); |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 244 | |
Coly Li | fc2d598 | 2018-08-11 13:19:46 +0800 | [diff] [blame] | 245 | void bch_btree_set_root(struct btree *b); |
| 246 | struct btree *__bch_btree_node_alloc(struct cache_set *c, struct btree_op *op, |
| 247 | int level, bool wait, |
| 248 | struct btree *parent); |
| 249 | struct btree *bch_btree_node_get(struct cache_set *c, struct btree_op *op, |
| 250 | struct bkey *k, int level, bool write, |
| 251 | struct btree *parent); |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 252 | |
Coly Li | fc2d598 | 2018-08-11 13:19:46 +0800 | [diff] [blame] | 253 | int bch_btree_insert_check_key(struct btree *b, struct btree_op *op, |
| 254 | struct bkey *check_key); |
| 255 | int bch_btree_insert(struct cache_set *c, struct keylist *keys, |
| 256 | atomic_t *journal_ref, struct bkey *replace_key); |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 257 | |
Coly Li | fc2d598 | 2018-08-11 13:19:46 +0800 | [diff] [blame] | 258 | int bch_gc_thread_start(struct cache_set *c); |
| 259 | void bch_initial_gc_finish(struct cache_set *c); |
| 260 | void bch_moving_gc(struct cache_set *c); |
| 261 | int bch_btree_check(struct cache_set *c); |
| 262 | void bch_initial_mark_key(struct cache_set *c, int level, struct bkey *k); |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 263 | |
Kent Overstreet | 72a4451 | 2013-10-24 17:19:26 -0700 | [diff] [blame] | 264 | static inline void wake_up_gc(struct cache_set *c) |
| 265 | { |
Kent Overstreet | be628be | 2016-10-26 20:31:17 -0700 | [diff] [blame] | 266 | wake_up(&c->gc_wait); |
Kent Overstreet | 72a4451 | 2013-10-24 17:19:26 -0700 | [diff] [blame] | 267 | } |
| 268 | |
Coly Li | cb07ad6 | 2018-12-13 22:53:52 +0800 | [diff] [blame] | 269 | static inline void force_wake_up_gc(struct cache_set *c) |
| 270 | { |
| 271 | /* |
| 272 | * Garbage collection thread only works when sectors_to_gc < 0, |
| 273 | * calling wake_up_gc() won't start gc thread if sectors_to_gc is |
| 274 | * not a nagetive value. |
| 275 | * Therefore sectors_to_gc is set to -1 here, before waking up |
| 276 | * gc thread by calling wake_up_gc(). Then gc_should_run() will |
| 277 | * give a chance to permit gc thread to run. "Give a chance" means |
| 278 | * before going into gc_should_run(), there is still possibility |
| 279 | * that c->sectors_to_gc being set to other positive value. So |
| 280 | * this routine won't 100% make sure gc thread will be woken up |
| 281 | * to run. |
| 282 | */ |
| 283 | atomic_set(&c->sectors_to_gc, -1); |
| 284 | wake_up_gc(c); |
| 285 | } |
| 286 | |
Kent Overstreet | 48dad8b | 2013-09-10 18:48:51 -0700 | [diff] [blame] | 287 | #define MAP_DONE 0 |
| 288 | #define MAP_CONTINUE 1 |
| 289 | |
| 290 | #define MAP_ALL_NODES 0 |
| 291 | #define MAP_LEAF_NODES 1 |
| 292 | |
| 293 | #define MAP_END_KEY 1 |
| 294 | |
Coly Li | fc2d598 | 2018-08-11 13:19:46 +0800 | [diff] [blame] | 295 | typedef int (btree_map_nodes_fn)(struct btree_op *b_op, struct btree *b); |
| 296 | int __bch_btree_map_nodes(struct btree_op *op, struct cache_set *c, |
| 297 | struct bkey *from, btree_map_nodes_fn *fn, int flags); |
Kent Overstreet | 48dad8b | 2013-09-10 18:48:51 -0700 | [diff] [blame] | 298 | |
| 299 | static inline int bch_btree_map_nodes(struct btree_op *op, struct cache_set *c, |
| 300 | struct bkey *from, btree_map_nodes_fn *fn) |
| 301 | { |
| 302 | return __bch_btree_map_nodes(op, c, from, fn, MAP_ALL_NODES); |
| 303 | } |
| 304 | |
| 305 | static inline int bch_btree_map_leaf_nodes(struct btree_op *op, |
| 306 | struct cache_set *c, |
| 307 | struct bkey *from, |
| 308 | btree_map_nodes_fn *fn) |
| 309 | { |
| 310 | return __bch_btree_map_nodes(op, c, from, fn, MAP_LEAF_NODES); |
| 311 | } |
| 312 | |
Coly Li | fc2d598 | 2018-08-11 13:19:46 +0800 | [diff] [blame] | 313 | typedef int (btree_map_keys_fn)(struct btree_op *op, struct btree *b, |
| 314 | struct bkey *k); |
| 315 | int bch_btree_map_keys(struct btree_op *op, struct cache_set *c, |
| 316 | struct bkey *from, btree_map_keys_fn *fn, int flags); |
Kent Overstreet | 48dad8b | 2013-09-10 18:48:51 -0700 | [diff] [blame] | 317 | |
Coly Li | fc2d598 | 2018-08-11 13:19:46 +0800 | [diff] [blame] | 318 | typedef bool (keybuf_pred_fn)(struct keybuf *buf, struct bkey *k); |
Kent Overstreet | 48dad8b | 2013-09-10 18:48:51 -0700 | [diff] [blame] | 319 | |
Coly Li | fc2d598 | 2018-08-11 13:19:46 +0800 | [diff] [blame] | 320 | void bch_keybuf_init(struct keybuf *buf); |
| 321 | void bch_refill_keybuf(struct cache_set *c, struct keybuf *buf, |
| 322 | struct bkey *end, keybuf_pred_fn *pred); |
| 323 | bool bch_keybuf_check_overlapping(struct keybuf *buf, struct bkey *start, |
| 324 | struct bkey *end); |
| 325 | void bch_keybuf_del(struct keybuf *buf, struct keybuf_key *w); |
| 326 | struct keybuf_key *bch_keybuf_next(struct keybuf *buf); |
Coly Li | b0d3098 | 2018-08-11 13:19:47 +0800 | [diff] [blame] | 327 | struct keybuf_key *bch_keybuf_next_rescan(struct cache_set *c, |
| 328 | struct keybuf *buf, |
| 329 | struct bkey *end, |
| 330 | keybuf_pred_fn *pred); |
Tang Junhui | d44c2f9 | 2017-10-30 14:46:33 -0700 | [diff] [blame] | 331 | void bch_update_bucket_in_use(struct cache_set *c, struct gc_stat *stats); |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 332 | #endif |