Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 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 { |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 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; |
Kent Overstreet | d6fd3b1 | 2013-07-24 17:20:19 -0700 | [diff] [blame] | 128 | struct btree *parent; |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 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 | |
Kent Overstreet | 5794351 | 2013-04-25 13:58:35 -0700 | [diff] [blame] | 145 | /* For outstanding btree writes, used as a lock - protects write_idx */ |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 146 | struct closure_with_waitlist io; |
| 147 | |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 148 | struct list_head list; |
| 149 | struct delayed_work work; |
| 150 | |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 151 | struct btree_write writes[2]; |
| 152 | struct bio *bio; |
| 153 | }; |
| 154 | |
| 155 | #define BTREE_FLAG(flag) \ |
| 156 | static inline bool btree_node_ ## flag(struct btree *b) \ |
| 157 | { return test_bit(BTREE_NODE_ ## flag, &b->flags); } \ |
| 158 | \ |
| 159 | static inline void set_btree_node_ ## flag(struct btree *b) \ |
| 160 | { set_bit(BTREE_NODE_ ## flag, &b->flags); } \ |
| 161 | |
| 162 | enum btree_flags { |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 163 | BTREE_NODE_io_error, |
| 164 | BTREE_NODE_dirty, |
| 165 | BTREE_NODE_write_idx, |
| 166 | }; |
| 167 | |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 168 | BTREE_FLAG(io_error); |
| 169 | BTREE_FLAG(dirty); |
| 170 | BTREE_FLAG(write_idx); |
| 171 | |
| 172 | static inline struct btree_write *btree_current_write(struct btree *b) |
| 173 | { |
| 174 | return b->writes + btree_node_write_idx(b); |
| 175 | } |
| 176 | |
| 177 | static inline struct btree_write *btree_prev_write(struct btree *b) |
| 178 | { |
| 179 | return b->writes + (btree_node_write_idx(b) ^ 1); |
| 180 | } |
| 181 | |
| 182 | static inline unsigned bset_offset(struct btree *b, struct bset *i) |
| 183 | { |
| 184 | return (((size_t) i) - ((size_t) b->sets->data)) >> 9; |
| 185 | } |
| 186 | |
| 187 | static inline struct bset *write_block(struct btree *b) |
| 188 | { |
| 189 | return ((void *) b->sets[0].data) + b->written * block_bytes(b->c); |
| 190 | } |
| 191 | |
| 192 | static inline bool bset_written(struct btree *b, struct bset_tree *t) |
| 193 | { |
| 194 | return t->data < write_block(b); |
| 195 | } |
| 196 | |
| 197 | static inline bool bkey_written(struct btree *b, struct bkey *k) |
| 198 | { |
| 199 | return k < write_block(b)->start; |
| 200 | } |
| 201 | |
| 202 | static inline void set_gc_sectors(struct cache_set *c) |
| 203 | { |
| 204 | atomic_set(&c->sectors_to_gc, c->sb.bucket_size * c->nbuckets / 8); |
| 205 | } |
| 206 | |
| 207 | static inline bool bch_ptr_invalid(struct btree *b, const struct bkey *k) |
| 208 | { |
| 209 | return __bch_ptr_invalid(b->c, b->level, k); |
| 210 | } |
| 211 | |
| 212 | static inline struct bkey *bch_btree_iter_init(struct btree *b, |
| 213 | struct btree_iter *iter, |
| 214 | struct bkey *search) |
| 215 | { |
| 216 | return __bch_btree_iter_init(b, iter, search, b->sets); |
| 217 | } |
| 218 | |
Kent Overstreet | e7c590e | 2013-09-10 18:39:16 -0700 | [diff] [blame] | 219 | void __bkey_put(struct cache_set *c, struct bkey *k); |
| 220 | |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 221 | /* Looping macros */ |
| 222 | |
| 223 | #define for_each_cached_btree(b, c, iter) \ |
| 224 | for (iter = 0; \ |
| 225 | iter < ARRAY_SIZE((c)->bucket_hash); \ |
| 226 | iter++) \ |
| 227 | hlist_for_each_entry_rcu((b), (c)->bucket_hash + iter, hash) |
| 228 | |
| 229 | #define for_each_key_filter(b, k, iter, filter) \ |
| 230 | for (bch_btree_iter_init((b), (iter), NULL); \ |
| 231 | ((k) = bch_btree_iter_next_filter((iter), b, filter));) |
| 232 | |
| 233 | #define for_each_key(b, k, iter) \ |
| 234 | for (bch_btree_iter_init((b), (iter), NULL); \ |
| 235 | ((k) = bch_btree_iter_next(iter));) |
| 236 | |
| 237 | /* Recursing down the btree */ |
| 238 | |
| 239 | struct btree_op { |
| 240 | struct closure cl; |
| 241 | struct cache_set *c; |
| 242 | |
| 243 | /* Journal entry we have a refcount on */ |
| 244 | atomic_t *journal; |
| 245 | |
| 246 | /* Bio to be inserted into the cache */ |
| 247 | struct bio *cache_bio; |
| 248 | |
| 249 | unsigned inode; |
| 250 | |
| 251 | uint16_t write_prio; |
| 252 | |
| 253 | /* Btree level at which we start taking write locks */ |
| 254 | short lock; |
| 255 | |
| 256 | /* Btree insertion type */ |
| 257 | enum { |
| 258 | BTREE_INSERT, |
| 259 | BTREE_REPLACE |
| 260 | } type:8; |
| 261 | |
| 262 | unsigned csum:1; |
Kent Overstreet | 84f0db0 | 2013-07-24 17:24:52 -0700 | [diff] [blame] | 263 | unsigned bypass:1; |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 264 | unsigned flush_journal:1; |
| 265 | |
| 266 | unsigned insert_data_done:1; |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 267 | unsigned insert_collision:1; |
| 268 | |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 269 | BKEY_PADDED(replace); |
| 270 | }; |
| 271 | |
| 272 | void bch_btree_op_init_stack(struct btree_op *); |
| 273 | |
| 274 | static inline void rw_lock(bool w, struct btree *b, int level) |
| 275 | { |
| 276 | w ? down_write_nested(&b->lock, level + 1) |
| 277 | : down_read_nested(&b->lock, level + 1); |
| 278 | if (w) |
| 279 | b->seq++; |
| 280 | } |
| 281 | |
| 282 | static inline void rw_unlock(bool w, struct btree *b) |
| 283 | { |
| 284 | #ifdef CONFIG_BCACHE_EDEBUG |
| 285 | unsigned i; |
| 286 | |
Kent Overstreet | 5794351 | 2013-04-25 13:58:35 -0700 | [diff] [blame] | 287 | if (w && b->key.ptr[0]) |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 288 | for (i = 0; i <= b->nsets; i++) |
| 289 | bch_check_key_order(b, b->sets[i].data); |
| 290 | #endif |
| 291 | |
| 292 | if (w) |
| 293 | b->seq++; |
| 294 | (w ? up_write : up_read)(&b->lock); |
| 295 | } |
| 296 | |
Kent Overstreet | 5794351 | 2013-04-25 13:58:35 -0700 | [diff] [blame] | 297 | void bch_btree_node_read(struct btree *); |
Kent Overstreet | 5794351 | 2013-04-25 13:58:35 -0700 | [diff] [blame] | 298 | void bch_btree_node_write(struct btree *, struct closure *); |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 299 | |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 300 | void bch_btree_set_root(struct btree *); |
Kent Overstreet | 35fcd84 | 2013-07-24 17:29:09 -0700 | [diff] [blame] | 301 | struct btree *bch_btree_node_alloc(struct cache_set *, int); |
Kent Overstreet | e8e1d46 | 2013-07-24 17:27:07 -0700 | [diff] [blame] | 302 | struct btree *bch_btree_node_get(struct cache_set *, struct bkey *, int, bool); |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 303 | |
Kent Overstreet | e7c590e | 2013-09-10 18:39:16 -0700 | [diff] [blame] | 304 | int bch_btree_insert_check_key(struct btree *, struct btree_op *, |
| 305 | struct bkey *); |
Kent Overstreet | 4f3d401 | 2013-09-10 18:46:36 -0700 | [diff] [blame] | 306 | int bch_btree_insert(struct btree_op *, struct cache_set *, struct keylist *); |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 307 | |
Kent Overstreet | 72a4451 | 2013-10-24 17:19:26 -0700 | [diff] [blame] | 308 | int bch_gc_thread_start(struct cache_set *); |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 309 | size_t bch_btree_gc_finish(struct cache_set *); |
Kent Overstreet | 72a4451 | 2013-10-24 17:19:26 -0700 | [diff] [blame] | 310 | void bch_moving_gc(struct cache_set *); |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 311 | int bch_btree_check(struct cache_set *, struct btree_op *); |
| 312 | uint8_t __bch_btree_mark_key(struct cache_set *, int, struct bkey *); |
| 313 | |
Kent Overstreet | 72a4451 | 2013-10-24 17:19:26 -0700 | [diff] [blame] | 314 | static inline void wake_up_gc(struct cache_set *c) |
| 315 | { |
| 316 | if (c->gc_thread) |
| 317 | wake_up_process(c->gc_thread); |
| 318 | } |
| 319 | |
Kent Overstreet | 48dad8b | 2013-09-10 18:48:51 -0700 | [diff] [blame] | 320 | #define MAP_DONE 0 |
| 321 | #define MAP_CONTINUE 1 |
| 322 | |
| 323 | #define MAP_ALL_NODES 0 |
| 324 | #define MAP_LEAF_NODES 1 |
| 325 | |
| 326 | #define MAP_END_KEY 1 |
| 327 | |
| 328 | typedef int (btree_map_nodes_fn)(struct btree_op *, struct btree *); |
| 329 | int __bch_btree_map_nodes(struct btree_op *, struct cache_set *, |
| 330 | struct bkey *, btree_map_nodes_fn *, int); |
| 331 | |
| 332 | static inline int bch_btree_map_nodes(struct btree_op *op, struct cache_set *c, |
| 333 | struct bkey *from, btree_map_nodes_fn *fn) |
| 334 | { |
| 335 | return __bch_btree_map_nodes(op, c, from, fn, MAP_ALL_NODES); |
| 336 | } |
| 337 | |
| 338 | static inline int bch_btree_map_leaf_nodes(struct btree_op *op, |
| 339 | struct cache_set *c, |
| 340 | struct bkey *from, |
| 341 | btree_map_nodes_fn *fn) |
| 342 | { |
| 343 | return __bch_btree_map_nodes(op, c, from, fn, MAP_LEAF_NODES); |
| 344 | } |
| 345 | |
| 346 | typedef int (btree_map_keys_fn)(struct btree_op *, struct btree *, |
| 347 | struct bkey *); |
| 348 | int bch_btree_map_keys(struct btree_op *, struct cache_set *, |
| 349 | struct bkey *, btree_map_keys_fn *, int); |
| 350 | |
| 351 | typedef bool (keybuf_pred_fn)(struct keybuf *, struct bkey *); |
| 352 | |
Kent Overstreet | 72c2706 | 2013-06-05 06:24:39 -0700 | [diff] [blame] | 353 | void bch_keybuf_init(struct keybuf *); |
Kent Overstreet | 48dad8b | 2013-09-10 18:48:51 -0700 | [diff] [blame] | 354 | void bch_refill_keybuf(struct cache_set *, struct keybuf *, |
| 355 | struct bkey *, keybuf_pred_fn *); |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 356 | bool bch_keybuf_check_overlapping(struct keybuf *, struct bkey *, |
| 357 | struct bkey *); |
| 358 | void bch_keybuf_del(struct keybuf *, struct keybuf_key *); |
| 359 | struct keybuf_key *bch_keybuf_next(struct keybuf *); |
Kent Overstreet | 72c2706 | 2013-06-05 06:24:39 -0700 | [diff] [blame] | 360 | struct keybuf_key *bch_keybuf_next_rescan(struct cache_set *, struct keybuf *, |
| 361 | struct bkey *, keybuf_pred_fn *); |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 362 | |
| 363 | #endif |