1b2441318SGreg Kroah-Hartman // SPDX-License-Identifier: GPL-2.0 2cafe5635SKent Overstreet /* 3cafe5635SKent Overstreet * Code for working with individual keys, and sorted sets of keys with in a 4cafe5635SKent Overstreet * btree node 5cafe5635SKent Overstreet * 6cafe5635SKent Overstreet * Copyright 2012 Google, Inc. 7cafe5635SKent Overstreet */ 8cafe5635SKent Overstreet 946f5aa88SJoe Perches #define pr_fmt(fmt) "bcache: %s() " fmt, __func__ 1089ebb4a2SKent Overstreet 1189ebb4a2SKent Overstreet #include "util.h" 1289ebb4a2SKent Overstreet #include "bset.h" 13cafe5635SKent Overstreet 14dc9d98d6SKent Overstreet #include <linux/console.h> 15e6017571SIngo Molnar #include <linux/sched/clock.h> 16cafe5635SKent Overstreet #include <linux/random.h> 17cd953ed0SGeert Uytterhoeven #include <linux/prefetch.h> 18cafe5635SKent Overstreet 19dc9d98d6SKent Overstreet #ifdef CONFIG_BCACHE_DEBUG 20dc9d98d6SKent Overstreet 216f10f7d1SColy Li void bch_dump_bset(struct btree_keys *b, struct bset *i, unsigned int set) 22dc9d98d6SKent Overstreet { 23dc9d98d6SKent Overstreet struct bkey *k, *next; 24dc9d98d6SKent Overstreet 25dc9d98d6SKent Overstreet for (k = i->start; k < bset_bkey_last(i); k = next) { 26dc9d98d6SKent Overstreet next = bkey_next(k); 27dc9d98d6SKent Overstreet 286ae63e35SColy Li pr_err("block %u key %u/%u: ", set, 296f10f7d1SColy Li (unsigned int) ((u64 *) k - i->d), i->keys); 30dc9d98d6SKent Overstreet 31dc9d98d6SKent Overstreet if (b->ops->key_dump) 32dc9d98d6SKent Overstreet b->ops->key_dump(b, k); 33dc9d98d6SKent Overstreet else 3446f5aa88SJoe Perches pr_cont("%llu:%llu\n", KEY_INODE(k), KEY_OFFSET(k)); 35dc9d98d6SKent Overstreet 36dc9d98d6SKent Overstreet if (next < bset_bkey_last(i) && 37dc9d98d6SKent Overstreet bkey_cmp(k, b->ops->is_extents ? 38dc9d98d6SKent Overstreet &START_KEY(next) : next) > 0) 396ae63e35SColy Li pr_err("Key skipped backwards\n"); 40dc9d98d6SKent Overstreet } 41dc9d98d6SKent Overstreet } 42dc9d98d6SKent Overstreet 43dc9d98d6SKent Overstreet void bch_dump_bucket(struct btree_keys *b) 44dc9d98d6SKent Overstreet { 456f10f7d1SColy Li unsigned int i; 46dc9d98d6SKent Overstreet 47dc9d98d6SKent Overstreet console_lock(); 48dc9d98d6SKent Overstreet for (i = 0; i <= b->nsets; i++) 49dc9d98d6SKent Overstreet bch_dump_bset(b, b->set[i].data, 50dc9d98d6SKent Overstreet bset_sector_offset(b, b->set[i].data)); 51dc9d98d6SKent Overstreet console_unlock(); 52dc9d98d6SKent Overstreet } 53dc9d98d6SKent Overstreet 54dc9d98d6SKent Overstreet int __bch_count_data(struct btree_keys *b) 55dc9d98d6SKent Overstreet { 566f10f7d1SColy Li unsigned int ret = 0; 57dc9d98d6SKent Overstreet struct btree_iter iter; 58dc9d98d6SKent Overstreet struct bkey *k; 59dc9d98d6SKent Overstreet 60dc9d98d6SKent Overstreet if (b->ops->is_extents) 61dc9d98d6SKent Overstreet for_each_key(b, k, &iter) 62dc9d98d6SKent Overstreet ret += KEY_SIZE(k); 63dc9d98d6SKent Overstreet return ret; 64dc9d98d6SKent Overstreet } 65dc9d98d6SKent Overstreet 66dc9d98d6SKent Overstreet void __bch_check_keys(struct btree_keys *b, const char *fmt, ...) 67dc9d98d6SKent Overstreet { 68dc9d98d6SKent Overstreet va_list args; 69dc9d98d6SKent Overstreet struct bkey *k, *p = NULL; 70dc9d98d6SKent Overstreet struct btree_iter iter; 71dc9d98d6SKent Overstreet const char *err; 72dc9d98d6SKent Overstreet 73dc9d98d6SKent Overstreet for_each_key(b, k, &iter) { 74dc9d98d6SKent Overstreet if (b->ops->is_extents) { 75dc9d98d6SKent Overstreet err = "Keys out of order"; 76dc9d98d6SKent Overstreet if (p && bkey_cmp(&START_KEY(p), &START_KEY(k)) > 0) 77dc9d98d6SKent Overstreet goto bug; 78dc9d98d6SKent Overstreet 79dc9d98d6SKent Overstreet if (bch_ptr_invalid(b, k)) 80dc9d98d6SKent Overstreet continue; 81dc9d98d6SKent Overstreet 82dc9d98d6SKent Overstreet err = "Overlapping keys"; 83dc9d98d6SKent Overstreet if (p && bkey_cmp(p, &START_KEY(k)) > 0) 84dc9d98d6SKent Overstreet goto bug; 85dc9d98d6SKent Overstreet } else { 86dc9d98d6SKent Overstreet if (bch_ptr_bad(b, k)) 87dc9d98d6SKent Overstreet continue; 88dc9d98d6SKent Overstreet 89dc9d98d6SKent Overstreet err = "Duplicate keys"; 90dc9d98d6SKent Overstreet if (p && !bkey_cmp(p, k)) 91dc9d98d6SKent Overstreet goto bug; 92dc9d98d6SKent Overstreet } 93dc9d98d6SKent Overstreet p = k; 94dc9d98d6SKent Overstreet } 95dc9d98d6SKent Overstreet #if 0 96dc9d98d6SKent Overstreet err = "Key larger than btree node key"; 97dc9d98d6SKent Overstreet if (p && bkey_cmp(p, &b->key) > 0) 98dc9d98d6SKent Overstreet goto bug; 99dc9d98d6SKent Overstreet #endif 100dc9d98d6SKent Overstreet return; 101dc9d98d6SKent Overstreet bug: 102dc9d98d6SKent Overstreet bch_dump_bucket(b); 103dc9d98d6SKent Overstreet 104dc9d98d6SKent Overstreet va_start(args, fmt); 105dc9d98d6SKent Overstreet vprintk(fmt, args); 106dc9d98d6SKent Overstreet va_end(args); 107dc9d98d6SKent Overstreet 108dc9d98d6SKent Overstreet panic("bch_check_keys error: %s:\n", err); 109dc9d98d6SKent Overstreet } 110dc9d98d6SKent Overstreet 111dc9d98d6SKent Overstreet static void bch_btree_iter_next_check(struct btree_iter *iter) 112dc9d98d6SKent Overstreet { 113dc9d98d6SKent Overstreet struct bkey *k = iter->data->k, *next = bkey_next(k); 114dc9d98d6SKent Overstreet 115dc9d98d6SKent Overstreet if (next < iter->data->end && 116dc9d98d6SKent Overstreet bkey_cmp(k, iter->b->ops->is_extents ? 117dc9d98d6SKent Overstreet &START_KEY(next) : next) > 0) { 118dc9d98d6SKent Overstreet bch_dump_bucket(iter->b); 119dc9d98d6SKent Overstreet panic("Key skipped backwards\n"); 120dc9d98d6SKent Overstreet } 121dc9d98d6SKent Overstreet } 122dc9d98d6SKent Overstreet 123dc9d98d6SKent Overstreet #else 124dc9d98d6SKent Overstreet 125dc9d98d6SKent Overstreet static inline void bch_btree_iter_next_check(struct btree_iter *iter) {} 126dc9d98d6SKent Overstreet 127dc9d98d6SKent Overstreet #endif 128dc9d98d6SKent Overstreet 129cafe5635SKent Overstreet /* Keylists */ 130cafe5635SKent Overstreet 1316f10f7d1SColy Li int __bch_keylist_realloc(struct keylist *l, unsigned int u64s) 132cafe5635SKent Overstreet { 133c2f95ae2SKent Overstreet size_t oldsize = bch_keylist_nkeys(l); 134085d2a3dSKent Overstreet size_t newsize = oldsize + u64s; 135c2f95ae2SKent Overstreet uint64_t *old_keys = l->keys_p == l->inline_keys ? NULL : l->keys_p; 136c2f95ae2SKent Overstreet uint64_t *new_keys; 137cafe5635SKent Overstreet 138cafe5635SKent Overstreet newsize = roundup_pow_of_two(newsize); 139cafe5635SKent Overstreet 140cafe5635SKent Overstreet if (newsize <= KEYLIST_INLINE || 141cafe5635SKent Overstreet roundup_pow_of_two(oldsize) == newsize) 142cafe5635SKent Overstreet return 0; 143cafe5635SKent Overstreet 144c2f95ae2SKent Overstreet new_keys = krealloc(old_keys, sizeof(uint64_t) * newsize, GFP_NOIO); 145cafe5635SKent Overstreet 146c2f95ae2SKent Overstreet if (!new_keys) 147cafe5635SKent Overstreet return -ENOMEM; 148cafe5635SKent Overstreet 149c2f95ae2SKent Overstreet if (!old_keys) 150c2f95ae2SKent Overstreet memcpy(new_keys, l->inline_keys, sizeof(uint64_t) * oldsize); 151cafe5635SKent Overstreet 152c2f95ae2SKent Overstreet l->keys_p = new_keys; 153c2f95ae2SKent Overstreet l->top_p = new_keys + oldsize; 154cafe5635SKent Overstreet 155cafe5635SKent Overstreet return 0; 156cafe5635SKent Overstreet } 157cafe5635SKent Overstreet 15806c1526dSColy Li /* Pop the top key of keylist by pointing l->top to its previous key */ 159cafe5635SKent Overstreet struct bkey *bch_keylist_pop(struct keylist *l) 160cafe5635SKent Overstreet { 161c2f95ae2SKent Overstreet struct bkey *k = l->keys; 162cafe5635SKent Overstreet 163cafe5635SKent Overstreet if (k == l->top) 164cafe5635SKent Overstreet return NULL; 165cafe5635SKent Overstreet 166cafe5635SKent Overstreet while (bkey_next(k) != l->top) 167cafe5635SKent Overstreet k = bkey_next(k); 168cafe5635SKent Overstreet 169cafe5635SKent Overstreet return l->top = k; 170cafe5635SKent Overstreet } 171cafe5635SKent Overstreet 17206c1526dSColy Li /* Pop the bottom key of keylist and update l->top_p */ 17326c949f8SKent Overstreet void bch_keylist_pop_front(struct keylist *l) 17426c949f8SKent Overstreet { 175c2f95ae2SKent Overstreet l->top_p -= bkey_u64s(l->keys); 17626c949f8SKent Overstreet 177c2f95ae2SKent Overstreet memmove(l->keys, 178c2f95ae2SKent Overstreet bkey_next(l->keys), 179c2f95ae2SKent Overstreet bch_keylist_bytes(l)); 18026c949f8SKent Overstreet } 18126c949f8SKent Overstreet 182cafe5635SKent Overstreet /* Key/pointer manipulation */ 183cafe5635SKent Overstreet 184cafe5635SKent Overstreet void bch_bkey_copy_single_ptr(struct bkey *dest, const struct bkey *src, 1856f10f7d1SColy Li unsigned int i) 186cafe5635SKent Overstreet { 187cafe5635SKent Overstreet BUG_ON(i > KEY_PTRS(src)); 188cafe5635SKent Overstreet 189cafe5635SKent Overstreet /* Only copy the header, key, and one pointer. */ 190cafe5635SKent Overstreet memcpy(dest, src, 2 * sizeof(uint64_t)); 191cafe5635SKent Overstreet dest->ptr[0] = src->ptr[i]; 192cafe5635SKent Overstreet SET_KEY_PTRS(dest, 1); 193cafe5635SKent Overstreet /* We didn't copy the checksum so clear that bit. */ 194cafe5635SKent Overstreet SET_KEY_CSUM(dest, 0); 195cafe5635SKent Overstreet } 196cafe5635SKent Overstreet 197cafe5635SKent Overstreet bool __bch_cut_front(const struct bkey *where, struct bkey *k) 198cafe5635SKent Overstreet { 1996f10f7d1SColy Li unsigned int i, len = 0; 200cafe5635SKent Overstreet 201cafe5635SKent Overstreet if (bkey_cmp(where, &START_KEY(k)) <= 0) 202cafe5635SKent Overstreet return false; 203cafe5635SKent Overstreet 204cafe5635SKent Overstreet if (bkey_cmp(where, k) < 0) 205cafe5635SKent Overstreet len = KEY_OFFSET(k) - KEY_OFFSET(where); 206cafe5635SKent Overstreet else 207cafe5635SKent Overstreet bkey_copy_key(k, where); 208cafe5635SKent Overstreet 209cafe5635SKent Overstreet for (i = 0; i < KEY_PTRS(k); i++) 210cafe5635SKent Overstreet SET_PTR_OFFSET(k, i, PTR_OFFSET(k, i) + KEY_SIZE(k) - len); 211cafe5635SKent Overstreet 212cafe5635SKent Overstreet BUG_ON(len > KEY_SIZE(k)); 213cafe5635SKent Overstreet SET_KEY_SIZE(k, len); 214cafe5635SKent Overstreet return true; 215cafe5635SKent Overstreet } 216cafe5635SKent Overstreet 217cafe5635SKent Overstreet bool __bch_cut_back(const struct bkey *where, struct bkey *k) 218cafe5635SKent Overstreet { 2196f10f7d1SColy Li unsigned int len = 0; 220cafe5635SKent Overstreet 221cafe5635SKent Overstreet if (bkey_cmp(where, k) >= 0) 222cafe5635SKent Overstreet return false; 223cafe5635SKent Overstreet 224cafe5635SKent Overstreet BUG_ON(KEY_INODE(where) != KEY_INODE(k)); 225cafe5635SKent Overstreet 226cafe5635SKent Overstreet if (bkey_cmp(where, &START_KEY(k)) > 0) 227cafe5635SKent Overstreet len = KEY_OFFSET(where) - KEY_START(k); 228cafe5635SKent Overstreet 229cafe5635SKent Overstreet bkey_copy_key(k, where); 230cafe5635SKent Overstreet 231cafe5635SKent Overstreet BUG_ON(len > KEY_SIZE(k)); 232cafe5635SKent Overstreet SET_KEY_SIZE(k, len); 233cafe5635SKent Overstreet return true; 234cafe5635SKent Overstreet } 235cafe5635SKent Overstreet 236ee811287SKent Overstreet /* Auxiliary search trees */ 237ee811287SKent Overstreet 238ee811287SKent Overstreet /* 32 bits total: */ 239ee811287SKent Overstreet #define BKEY_MID_BITS 3 240ee811287SKent Overstreet #define BKEY_EXPONENT_BITS 7 241ee811287SKent Overstreet #define BKEY_MANTISSA_BITS (32 - BKEY_MID_BITS - BKEY_EXPONENT_BITS) 242ee811287SKent Overstreet #define BKEY_MANTISSA_MASK ((1 << BKEY_MANTISSA_BITS) - 1) 243ee811287SKent Overstreet 244ee811287SKent Overstreet struct bkey_float { 2456f10f7d1SColy Li unsigned int exponent:BKEY_EXPONENT_BITS; 2466f10f7d1SColy Li unsigned int m:BKEY_MID_BITS; 2476f10f7d1SColy Li unsigned int mantissa:BKEY_MANTISSA_BITS; 248ee811287SKent Overstreet } __packed; 249ee811287SKent Overstreet 250ee811287SKent Overstreet /* 251ee811287SKent Overstreet * BSET_CACHELINE was originally intended to match the hardware cacheline size - 252ee811287SKent Overstreet * it used to be 64, but I realized the lookup code would touch slightly less 253ee811287SKent Overstreet * memory if it was 128. 254ee811287SKent Overstreet * 255ee811287SKent Overstreet * It definites the number of bytes (in struct bset) per struct bkey_float in 256ee811287SKent Overstreet * the auxiliar search tree - when we're done searching the bset_float tree we 257ee811287SKent Overstreet * have this many bytes left that we do a linear search over. 258ee811287SKent Overstreet * 259ee811287SKent Overstreet * Since (after level 5) every level of the bset_tree is on a new cacheline, 260ee811287SKent Overstreet * we're touching one fewer cacheline in the bset tree in exchange for one more 261ee811287SKent Overstreet * cacheline in the linear search - but the linear search might stop before it 262ee811287SKent Overstreet * gets to the second cacheline. 263ee811287SKent Overstreet */ 264ee811287SKent Overstreet 265ee811287SKent Overstreet #define BSET_CACHELINE 128 266ee811287SKent Overstreet 267ee811287SKent Overstreet /* Space required for the btree node keys */ 268a85e968eSKent Overstreet static inline size_t btree_keys_bytes(struct btree_keys *b) 269ee811287SKent Overstreet { 270ee811287SKent Overstreet return PAGE_SIZE << b->page_order; 271ee811287SKent Overstreet } 272ee811287SKent Overstreet 273a85e968eSKent Overstreet static inline size_t btree_keys_cachelines(struct btree_keys *b) 274ee811287SKent Overstreet { 275ee811287SKent Overstreet return btree_keys_bytes(b) / BSET_CACHELINE; 276ee811287SKent Overstreet } 277ee811287SKent Overstreet 278ee811287SKent Overstreet /* Space required for the auxiliary search trees */ 279a85e968eSKent Overstreet static inline size_t bset_tree_bytes(struct btree_keys *b) 280ee811287SKent Overstreet { 281ee811287SKent Overstreet return btree_keys_cachelines(b) * sizeof(struct bkey_float); 282ee811287SKent Overstreet } 283ee811287SKent Overstreet 284ee811287SKent Overstreet /* Space required for the prev pointers */ 285a85e968eSKent Overstreet static inline size_t bset_prev_bytes(struct btree_keys *b) 286ee811287SKent Overstreet { 287ee811287SKent Overstreet return btree_keys_cachelines(b) * sizeof(uint8_t); 288ee811287SKent Overstreet } 289ee811287SKent Overstreet 290ee811287SKent Overstreet /* Memory allocation */ 291ee811287SKent Overstreet 292a85e968eSKent Overstreet void bch_btree_keys_free(struct btree_keys *b) 293ee811287SKent Overstreet { 294a85e968eSKent Overstreet struct bset_tree *t = b->set; 295ee811287SKent Overstreet 296ee811287SKent Overstreet if (bset_prev_bytes(b) < PAGE_SIZE) 297ee811287SKent Overstreet kfree(t->prev); 298ee811287SKent Overstreet else 299ee811287SKent Overstreet free_pages((unsigned long) t->prev, 300ee811287SKent Overstreet get_order(bset_prev_bytes(b))); 301ee811287SKent Overstreet 302ee811287SKent Overstreet if (bset_tree_bytes(b) < PAGE_SIZE) 303ee811287SKent Overstreet kfree(t->tree); 304ee811287SKent Overstreet else 305ee811287SKent Overstreet free_pages((unsigned long) t->tree, 306ee811287SKent Overstreet get_order(bset_tree_bytes(b))); 307ee811287SKent Overstreet 308ee811287SKent Overstreet free_pages((unsigned long) t->data, b->page_order); 309ee811287SKent Overstreet 310ee811287SKent Overstreet t->prev = NULL; 311ee811287SKent Overstreet t->tree = NULL; 312ee811287SKent Overstreet t->data = NULL; 313ee811287SKent Overstreet } 314ee811287SKent Overstreet 315b0d30981SColy Li int bch_btree_keys_alloc(struct btree_keys *b, 316b0d30981SColy Li unsigned int page_order, 317b0d30981SColy Li gfp_t gfp) 318ee811287SKent Overstreet { 319a85e968eSKent Overstreet struct bset_tree *t = b->set; 320ee811287SKent Overstreet 321ee811287SKent Overstreet BUG_ON(t->data); 322ee811287SKent Overstreet 323ee811287SKent Overstreet b->page_order = page_order; 324ee811287SKent Overstreet 325*5fe48867SColy Li t->data = (void *) __get_free_pages(__GFP_COMP|gfp, b->page_order); 326ee811287SKent Overstreet if (!t->data) 327ee811287SKent Overstreet goto err; 328ee811287SKent Overstreet 329ee811287SKent Overstreet t->tree = bset_tree_bytes(b) < PAGE_SIZE 330ee811287SKent Overstreet ? kmalloc(bset_tree_bytes(b), gfp) 331ee811287SKent Overstreet : (void *) __get_free_pages(gfp, get_order(bset_tree_bytes(b))); 332ee811287SKent Overstreet if (!t->tree) 333ee811287SKent Overstreet goto err; 334ee811287SKent Overstreet 335ee811287SKent Overstreet t->prev = bset_prev_bytes(b) < PAGE_SIZE 336ee811287SKent Overstreet ? kmalloc(bset_prev_bytes(b), gfp) 337ee811287SKent Overstreet : (void *) __get_free_pages(gfp, get_order(bset_prev_bytes(b))); 338ee811287SKent Overstreet if (!t->prev) 339ee811287SKent Overstreet goto err; 340ee811287SKent Overstreet 341ee811287SKent Overstreet return 0; 342ee811287SKent Overstreet err: 343ee811287SKent Overstreet bch_btree_keys_free(b); 344ee811287SKent Overstreet return -ENOMEM; 345ee811287SKent Overstreet } 346a85e968eSKent Overstreet 347a85e968eSKent Overstreet void bch_btree_keys_init(struct btree_keys *b, const struct btree_keys_ops *ops, 348a85e968eSKent Overstreet bool *expensive_debug_checks) 349a85e968eSKent Overstreet { 350a85e968eSKent Overstreet b->ops = ops; 351a85e968eSKent Overstreet b->expensive_debug_checks = expensive_debug_checks; 352a85e968eSKent Overstreet b->nsets = 0; 353a85e968eSKent Overstreet b->last_set_unwritten = 0; 354a85e968eSKent Overstreet 355a85e968eSKent Overstreet /* 356bd9026c8SColy Li * struct btree_keys in embedded in struct btree, and struct 357bd9026c8SColy Li * bset_tree is embedded into struct btree_keys. They are all 358bd9026c8SColy Li * initialized as 0 by kzalloc() in mca_bucket_alloc(), and 359bd9026c8SColy Li * b->set[0].data is allocated in bch_btree_keys_alloc(), so we 360bd9026c8SColy Li * don't have to initiate b->set[].size and b->set[].data here 361bd9026c8SColy Li * any more. 362a85e968eSKent Overstreet */ 363a85e968eSKent Overstreet } 364ee811287SKent Overstreet 365cafe5635SKent Overstreet /* Binary tree stuff for auxiliary search trees */ 366cafe5635SKent Overstreet 367b467a6acSColy Li /* 368b467a6acSColy Li * return array index next to j when does in-order traverse 369b467a6acSColy Li * of a binary tree which is stored in a linear array 370b467a6acSColy Li */ 3716f10f7d1SColy Li static unsigned int inorder_next(unsigned int j, unsigned int size) 372cafe5635SKent Overstreet { 373cafe5635SKent Overstreet if (j * 2 + 1 < size) { 374cafe5635SKent Overstreet j = j * 2 + 1; 375cafe5635SKent Overstreet 376cafe5635SKent Overstreet while (j * 2 < size) 377cafe5635SKent Overstreet j *= 2; 378cafe5635SKent Overstreet } else 379cafe5635SKent Overstreet j >>= ffz(j) + 1; 380cafe5635SKent Overstreet 381cafe5635SKent Overstreet return j; 382cafe5635SKent Overstreet } 383cafe5635SKent Overstreet 384b467a6acSColy Li /* 385b467a6acSColy Li * return array index previous to j when does in-order traverse 386b467a6acSColy Li * of a binary tree which is stored in a linear array 387b467a6acSColy Li */ 3886f10f7d1SColy Li static unsigned int inorder_prev(unsigned int j, unsigned int size) 389cafe5635SKent Overstreet { 390cafe5635SKent Overstreet if (j * 2 < size) { 391cafe5635SKent Overstreet j = j * 2; 392cafe5635SKent Overstreet 393cafe5635SKent Overstreet while (j * 2 + 1 < size) 394cafe5635SKent Overstreet j = j * 2 + 1; 395cafe5635SKent Overstreet } else 396cafe5635SKent Overstreet j >>= ffs(j); 397cafe5635SKent Overstreet 398cafe5635SKent Overstreet return j; 399cafe5635SKent Overstreet } 400cafe5635SKent Overstreet 4013be11dbaSColy Li /* 4023be11dbaSColy Li * I have no idea why this code works... and I'm the one who wrote it 403cafe5635SKent Overstreet * 404cafe5635SKent Overstreet * However, I do know what it does: 405cafe5635SKent Overstreet * Given a binary tree constructed in an array (i.e. how you normally implement 406cafe5635SKent Overstreet * a heap), it converts a node in the tree - referenced by array index - to the 407cafe5635SKent Overstreet * index it would have if you did an inorder traversal. 408cafe5635SKent Overstreet * 409cafe5635SKent Overstreet * Also tested for every j, size up to size somewhere around 6 million. 410cafe5635SKent Overstreet * 411cafe5635SKent Overstreet * The binary tree starts at array index 1, not 0 412cafe5635SKent Overstreet * extra is a function of size: 413cafe5635SKent Overstreet * extra = (size - rounddown_pow_of_two(size - 1)) << 1; 414cafe5635SKent Overstreet */ 4156f10f7d1SColy Li static unsigned int __to_inorder(unsigned int j, 4166f10f7d1SColy Li unsigned int size, 4176f10f7d1SColy Li unsigned int extra) 418cafe5635SKent Overstreet { 4196f10f7d1SColy Li unsigned int b = fls(j); 4206f10f7d1SColy Li unsigned int shift = fls(size - 1) - b; 421cafe5635SKent Overstreet 422cafe5635SKent Overstreet j ^= 1U << (b - 1); 423cafe5635SKent Overstreet j <<= 1; 424cafe5635SKent Overstreet j |= 1; 425cafe5635SKent Overstreet j <<= shift; 426cafe5635SKent Overstreet 427cafe5635SKent Overstreet if (j > extra) 428cafe5635SKent Overstreet j -= (j - extra) >> 1; 429cafe5635SKent Overstreet 430cafe5635SKent Overstreet return j; 431cafe5635SKent Overstreet } 432cafe5635SKent Overstreet 433b467a6acSColy Li /* 434b467a6acSColy Li * Return the cacheline index in bset_tree->data, where j is index 435b467a6acSColy Li * from a linear array which stores the auxiliar binary tree 436b467a6acSColy Li */ 4376f10f7d1SColy Li static unsigned int to_inorder(unsigned int j, struct bset_tree *t) 438cafe5635SKent Overstreet { 439cafe5635SKent Overstreet return __to_inorder(j, t->size, t->extra); 440cafe5635SKent Overstreet } 441cafe5635SKent Overstreet 4426f10f7d1SColy Li static unsigned int __inorder_to_tree(unsigned int j, 4436f10f7d1SColy Li unsigned int size, 4446f10f7d1SColy Li unsigned int extra) 445cafe5635SKent Overstreet { 4466f10f7d1SColy Li unsigned int shift; 447cafe5635SKent Overstreet 448cafe5635SKent Overstreet if (j > extra) 449cafe5635SKent Overstreet j += j - extra; 450cafe5635SKent Overstreet 451cafe5635SKent Overstreet shift = ffs(j); 452cafe5635SKent Overstreet 453cafe5635SKent Overstreet j >>= shift; 454cafe5635SKent Overstreet j |= roundup_pow_of_two(size) >> shift; 455cafe5635SKent Overstreet 456cafe5635SKent Overstreet return j; 457cafe5635SKent Overstreet } 458cafe5635SKent Overstreet 459b467a6acSColy Li /* 460b467a6acSColy Li * Return an index from a linear array which stores the auxiliar binary 461b467a6acSColy Li * tree, j is the cacheline index of t->data. 462b467a6acSColy Li */ 4636f10f7d1SColy Li static unsigned int inorder_to_tree(unsigned int j, struct bset_tree *t) 464cafe5635SKent Overstreet { 465cafe5635SKent Overstreet return __inorder_to_tree(j, t->size, t->extra); 466cafe5635SKent Overstreet } 467cafe5635SKent Overstreet 468cafe5635SKent Overstreet #if 0 469cafe5635SKent Overstreet void inorder_test(void) 470cafe5635SKent Overstreet { 471cafe5635SKent Overstreet unsigned long done = 0; 472cafe5635SKent Overstreet ktime_t start = ktime_get(); 473cafe5635SKent Overstreet 4746f10f7d1SColy Li for (unsigned int size = 2; 475cafe5635SKent Overstreet size < 65536000; 476cafe5635SKent Overstreet size++) { 477b0d30981SColy Li unsigned int extra = 478b0d30981SColy Li (size - rounddown_pow_of_two(size - 1)) << 1; 4796f10f7d1SColy Li unsigned int i = 1, j = rounddown_pow_of_two(size - 1); 480cafe5635SKent Overstreet 481cafe5635SKent Overstreet if (!(size % 4096)) 4826ae63e35SColy Li pr_notice("loop %u, %llu per us\n", size, 483cafe5635SKent Overstreet done / ktime_us_delta(ktime_get(), start)); 484cafe5635SKent Overstreet 485cafe5635SKent Overstreet while (1) { 486cafe5635SKent Overstreet if (__inorder_to_tree(i, size, extra) != j) 487cafe5635SKent Overstreet panic("size %10u j %10u i %10u", size, j, i); 488cafe5635SKent Overstreet 489cafe5635SKent Overstreet if (__to_inorder(j, size, extra) != i) 490cafe5635SKent Overstreet panic("size %10u j %10u i %10u", size, j, i); 491cafe5635SKent Overstreet 492cafe5635SKent Overstreet if (j == rounddown_pow_of_two(size) - 1) 493cafe5635SKent Overstreet break; 494cafe5635SKent Overstreet 495cafe5635SKent Overstreet BUG_ON(inorder_prev(inorder_next(j, size), size) != j); 496cafe5635SKent Overstreet 497cafe5635SKent Overstreet j = inorder_next(j, size); 498cafe5635SKent Overstreet i++; 499cafe5635SKent Overstreet } 500cafe5635SKent Overstreet 501cafe5635SKent Overstreet done += size - 1; 502cafe5635SKent Overstreet } 503cafe5635SKent Overstreet } 504cafe5635SKent Overstreet #endif 505cafe5635SKent Overstreet 506cafe5635SKent Overstreet /* 50748a73025SPhil Viana * Cacheline/offset <-> bkey pointer arithmetic: 508cafe5635SKent Overstreet * 509cafe5635SKent Overstreet * t->tree is a binary search tree in an array; each node corresponds to a key 510cafe5635SKent Overstreet * in one cacheline in t->set (BSET_CACHELINE bytes). 511cafe5635SKent Overstreet * 512cafe5635SKent Overstreet * This means we don't have to store the full index of the key that a node in 513cafe5635SKent Overstreet * the binary tree points to; to_inorder() gives us the cacheline, and then 514cafe5635SKent Overstreet * bkey_float->m gives us the offset within that cacheline, in units of 8 bytes. 515cafe5635SKent Overstreet * 51648a73025SPhil Viana * cacheline_to_bkey() and friends abstract out all the pointer arithmetic to 517cafe5635SKent Overstreet * make this work. 518cafe5635SKent Overstreet * 519cafe5635SKent Overstreet * To construct the bfloat for an arbitrary key we need to know what the key 520cafe5635SKent Overstreet * immediately preceding it is: we have to check if the two keys differ in the 521cafe5635SKent Overstreet * bits we're going to store in bkey_float->mantissa. t->prev[j] stores the size 522cafe5635SKent Overstreet * of the previous key so we can walk backwards to it from t->tree[j]'s key. 523cafe5635SKent Overstreet */ 524cafe5635SKent Overstreet 5256f10f7d1SColy Li static struct bkey *cacheline_to_bkey(struct bset_tree *t, 5266f10f7d1SColy Li unsigned int cacheline, 5276f10f7d1SColy Li unsigned int offset) 528cafe5635SKent Overstreet { 529cafe5635SKent Overstreet return ((void *) t->data) + cacheline * BSET_CACHELINE + offset * 8; 530cafe5635SKent Overstreet } 531cafe5635SKent Overstreet 5326f10f7d1SColy Li static unsigned int bkey_to_cacheline(struct bset_tree *t, struct bkey *k) 533cafe5635SKent Overstreet { 534cafe5635SKent Overstreet return ((void *) k - (void *) t->data) / BSET_CACHELINE; 535cafe5635SKent Overstreet } 536cafe5635SKent Overstreet 5376f10f7d1SColy Li static unsigned int bkey_to_cacheline_offset(struct bset_tree *t, 5386f10f7d1SColy Li unsigned int cacheline, 5399dd6358aSKent Overstreet struct bkey *k) 540cafe5635SKent Overstreet { 5419dd6358aSKent Overstreet return (u64 *) k - (u64 *) cacheline_to_bkey(t, cacheline, 0); 542cafe5635SKent Overstreet } 543cafe5635SKent Overstreet 5446f10f7d1SColy Li static struct bkey *tree_to_bkey(struct bset_tree *t, unsigned int j) 545cafe5635SKent Overstreet { 546cafe5635SKent Overstreet return cacheline_to_bkey(t, to_inorder(j, t), t->tree[j].m); 547cafe5635SKent Overstreet } 548cafe5635SKent Overstreet 5496f10f7d1SColy Li static struct bkey *tree_to_prev_bkey(struct bset_tree *t, unsigned int j) 550cafe5635SKent Overstreet { 551cafe5635SKent Overstreet return (void *) (((uint64_t *) tree_to_bkey(t, j)) - t->prev[j]); 552cafe5635SKent Overstreet } 553cafe5635SKent Overstreet 554cafe5635SKent Overstreet /* 555cafe5635SKent Overstreet * For the write set - the one we're currently inserting keys into - we don't 556cafe5635SKent Overstreet * maintain a full search tree, we just keep a simple lookup table in t->prev. 557cafe5635SKent Overstreet */ 5586f10f7d1SColy Li static struct bkey *table_to_bkey(struct bset_tree *t, unsigned int cacheline) 559cafe5635SKent Overstreet { 560cafe5635SKent Overstreet return cacheline_to_bkey(t, cacheline, t->prev[cacheline]); 561cafe5635SKent Overstreet } 562cafe5635SKent Overstreet 563cafe5635SKent Overstreet static inline uint64_t shrd128(uint64_t high, uint64_t low, uint8_t shift) 564cafe5635SKent Overstreet { 565cafe5635SKent Overstreet low >>= shift; 566cafe5635SKent Overstreet low |= (high << 1) << (63U - shift); 567cafe5635SKent Overstreet return low; 568cafe5635SKent Overstreet } 569cafe5635SKent Overstreet 570b467a6acSColy Li /* 571b467a6acSColy Li * Calculate mantissa value for struct bkey_float. 572b467a6acSColy Li * If most significant bit of f->exponent is not set, then 573b467a6acSColy Li * - f->exponent >> 6 is 0 574b467a6acSColy Li * - p[0] points to bkey->low 575b467a6acSColy Li * - p[-1] borrows bits from KEY_INODE() of bkey->high 576b467a6acSColy Li * if most isgnificant bits of f->exponent is set, then 577b467a6acSColy Li * - f->exponent >> 6 is 1 578b467a6acSColy Li * - p[0] points to bits from KEY_INODE() of bkey->high 579b467a6acSColy Li * - p[-1] points to other bits from KEY_INODE() of 580b467a6acSColy Li * bkey->high too. 581b467a6acSColy Li * See make_bfloat() to check when most significant bit of f->exponent 582b467a6acSColy Li * is set or not. 583b467a6acSColy Li */ 5846f10f7d1SColy Li static inline unsigned int bfloat_mantissa(const struct bkey *k, 585cafe5635SKent Overstreet struct bkey_float *f) 586cafe5635SKent Overstreet { 587cafe5635SKent Overstreet const uint64_t *p = &k->low - (f->exponent >> 6); 5881fae7cf0SColy Li 589cafe5635SKent Overstreet return shrd128(p[-1], p[0], f->exponent & 63) & BKEY_MANTISSA_MASK; 590cafe5635SKent Overstreet } 591cafe5635SKent Overstreet 5926f10f7d1SColy Li static void make_bfloat(struct bset_tree *t, unsigned int j) 593cafe5635SKent Overstreet { 594cafe5635SKent Overstreet struct bkey_float *f = &t->tree[j]; 595cafe5635SKent Overstreet struct bkey *m = tree_to_bkey(t, j); 596cafe5635SKent Overstreet struct bkey *p = tree_to_prev_bkey(t, j); 597cafe5635SKent Overstreet 598cafe5635SKent Overstreet struct bkey *l = is_power_of_2(j) 599cafe5635SKent Overstreet ? t->data->start 600cafe5635SKent Overstreet : tree_to_prev_bkey(t, j >> ffs(j)); 601cafe5635SKent Overstreet 602cafe5635SKent Overstreet struct bkey *r = is_power_of_2(j + 1) 603fafff81cSKent Overstreet ? bset_bkey_idx(t->data, t->data->keys - bkey_u64s(&t->end)) 604cafe5635SKent Overstreet : tree_to_bkey(t, j >> (ffz(j) + 1)); 605cafe5635SKent Overstreet 606cafe5635SKent Overstreet BUG_ON(m < l || m > r); 607cafe5635SKent Overstreet BUG_ON(bkey_next(p) != m); 608cafe5635SKent Overstreet 609b467a6acSColy Li /* 610b467a6acSColy Li * If l and r have different KEY_INODE values (different backing 611b467a6acSColy Li * device), f->exponent records how many least significant bits 612b467a6acSColy Li * are different in KEY_INODE values and sets most significant 613b467a6acSColy Li * bits to 1 (by +64). 614b467a6acSColy Li * If l and r have same KEY_INODE value, f->exponent records 615b467a6acSColy Li * how many different bits in least significant bits of bkey->low. 616b467a6acSColy Li * See bfloat_mantiss() how the most significant bit of 617b467a6acSColy Li * f->exponent is used to calculate bfloat mantissa value. 618b467a6acSColy Li */ 619cafe5635SKent Overstreet if (KEY_INODE(l) != KEY_INODE(r)) 620cafe5635SKent Overstreet f->exponent = fls64(KEY_INODE(r) ^ KEY_INODE(l)) + 64; 621cafe5635SKent Overstreet else 622cafe5635SKent Overstreet f->exponent = fls64(r->low ^ l->low); 623cafe5635SKent Overstreet 624cafe5635SKent Overstreet f->exponent = max_t(int, f->exponent - BKEY_MANTISSA_BITS, 0); 625cafe5635SKent Overstreet 626cafe5635SKent Overstreet /* 627cafe5635SKent Overstreet * Setting f->exponent = 127 flags this node as failed, and causes the 628cafe5635SKent Overstreet * lookup code to fall back to comparing against the original key. 629cafe5635SKent Overstreet */ 630cafe5635SKent Overstreet 631cafe5635SKent Overstreet if (bfloat_mantissa(m, f) != bfloat_mantissa(p, f)) 632cafe5635SKent Overstreet f->mantissa = bfloat_mantissa(m, f) - 1; 633cafe5635SKent Overstreet else 634cafe5635SKent Overstreet f->exponent = 127; 635cafe5635SKent Overstreet } 636cafe5635SKent Overstreet 637a85e968eSKent Overstreet static void bset_alloc_tree(struct btree_keys *b, struct bset_tree *t) 638cafe5635SKent Overstreet { 639a85e968eSKent Overstreet if (t != b->set) { 6406f10f7d1SColy Li unsigned int j = roundup(t[-1].size, 641cafe5635SKent Overstreet 64 / sizeof(struct bkey_float)); 642cafe5635SKent Overstreet 643cafe5635SKent Overstreet t->tree = t[-1].tree + j; 644cafe5635SKent Overstreet t->prev = t[-1].prev + j; 645cafe5635SKent Overstreet } 646cafe5635SKent Overstreet 647a85e968eSKent Overstreet while (t < b->set + MAX_BSETS) 648cafe5635SKent Overstreet t++->size = 0; 649cafe5635SKent Overstreet } 650cafe5635SKent Overstreet 651a85e968eSKent Overstreet static void bch_bset_build_unwritten_tree(struct btree_keys *b) 652cafe5635SKent Overstreet { 653ee811287SKent Overstreet struct bset_tree *t = bset_tree_last(b); 654cafe5635SKent Overstreet 655a85e968eSKent Overstreet BUG_ON(b->last_set_unwritten); 656a85e968eSKent Overstreet b->last_set_unwritten = 1; 657a85e968eSKent Overstreet 658cafe5635SKent Overstreet bset_alloc_tree(b, t); 659cafe5635SKent Overstreet 660a85e968eSKent Overstreet if (t->tree != b->set->tree + btree_keys_cachelines(b)) { 6619dd6358aSKent Overstreet t->prev[0] = bkey_to_cacheline_offset(t, 0, t->data->start); 662cafe5635SKent Overstreet t->size = 1; 663cafe5635SKent Overstreet } 664cafe5635SKent Overstreet } 665cafe5635SKent Overstreet 666a85e968eSKent Overstreet void bch_bset_init_next(struct btree_keys *b, struct bset *i, uint64_t magic) 667ee811287SKent Overstreet { 668a85e968eSKent Overstreet if (i != b->set->data) { 669a85e968eSKent Overstreet b->set[++b->nsets].data = i; 670a85e968eSKent Overstreet i->seq = b->set->data->seq; 671ee811287SKent Overstreet } else 672ee811287SKent Overstreet get_random_bytes(&i->seq, sizeof(uint64_t)); 673ee811287SKent Overstreet 674ee811287SKent Overstreet i->magic = magic; 675ee811287SKent Overstreet i->version = 0; 676ee811287SKent Overstreet i->keys = 0; 677ee811287SKent Overstreet 678ee811287SKent Overstreet bch_bset_build_unwritten_tree(b); 679ee811287SKent Overstreet } 680ee811287SKent Overstreet 681b467a6acSColy Li /* 682b467a6acSColy Li * Build auxiliary binary tree 'struct bset_tree *t', this tree is used to 683b467a6acSColy Li * accelerate bkey search in a btree node (pointed by bset_tree->data in 684b467a6acSColy Li * memory). After search in the auxiliar tree by calling bset_search_tree(), 685b467a6acSColy Li * a struct bset_search_iter is returned which indicates range [l, r] from 686b467a6acSColy Li * bset_tree->data where the searching bkey might be inside. Then a followed 687b467a6acSColy Li * linear comparison does the exact search, see __bch_bset_search() for how 688b467a6acSColy Li * the auxiliary tree is used. 689b467a6acSColy Li */ 690a85e968eSKent Overstreet void bch_bset_build_written_tree(struct btree_keys *b) 691cafe5635SKent Overstreet { 692ee811287SKent Overstreet struct bset_tree *t = bset_tree_last(b); 6939dd6358aSKent Overstreet struct bkey *prev = NULL, *k = t->data->start; 6946f10f7d1SColy Li unsigned int j, cacheline = 1; 695cafe5635SKent Overstreet 696a85e968eSKent Overstreet b->last_set_unwritten = 0; 697a85e968eSKent Overstreet 698cafe5635SKent Overstreet bset_alloc_tree(b, t); 699cafe5635SKent Overstreet 7006f10f7d1SColy Li t->size = min_t(unsigned int, 701fafff81cSKent Overstreet bkey_to_cacheline(t, bset_bkey_last(t->data)), 702a85e968eSKent Overstreet b->set->tree + btree_keys_cachelines(b) - t->tree); 703cafe5635SKent Overstreet 704cafe5635SKent Overstreet if (t->size < 2) { 705cafe5635SKent Overstreet t->size = 0; 706cafe5635SKent Overstreet return; 707cafe5635SKent Overstreet } 708cafe5635SKent Overstreet 709cafe5635SKent Overstreet t->extra = (t->size - rounddown_pow_of_two(t->size - 1)) << 1; 710cafe5635SKent Overstreet 711cafe5635SKent Overstreet /* First we figure out where the first key in each cacheline is */ 712cafe5635SKent Overstreet for (j = inorder_next(0, t->size); 713cafe5635SKent Overstreet j; 714cafe5635SKent Overstreet j = inorder_next(j, t->size)) { 7159dd6358aSKent Overstreet while (bkey_to_cacheline(t, k) < cacheline) 7169dd6358aSKent Overstreet prev = k, k = bkey_next(k); 717cafe5635SKent Overstreet 7189dd6358aSKent Overstreet t->prev[j] = bkey_u64s(prev); 7199dd6358aSKent Overstreet t->tree[j].m = bkey_to_cacheline_offset(t, cacheline++, k); 720cafe5635SKent Overstreet } 721cafe5635SKent Overstreet 722fafff81cSKent Overstreet while (bkey_next(k) != bset_bkey_last(t->data)) 723cafe5635SKent Overstreet k = bkey_next(k); 724cafe5635SKent Overstreet 725cafe5635SKent Overstreet t->end = *k; 726cafe5635SKent Overstreet 727cafe5635SKent Overstreet /* Then we build the tree */ 728cafe5635SKent Overstreet for (j = inorder_next(0, t->size); 729cafe5635SKent Overstreet j; 730cafe5635SKent Overstreet j = inorder_next(j, t->size)) 731cafe5635SKent Overstreet make_bfloat(t, j); 732cafe5635SKent Overstreet } 733cafe5635SKent Overstreet 734829a60b9SKent Overstreet /* Insert */ 735829a60b9SKent Overstreet 736a85e968eSKent Overstreet void bch_bset_fix_invalidated_key(struct btree_keys *b, struct bkey *k) 737cafe5635SKent Overstreet { 738cafe5635SKent Overstreet struct bset_tree *t; 7396f10f7d1SColy Li unsigned int inorder, j = 1; 740cafe5635SKent Overstreet 741a85e968eSKent Overstreet for (t = b->set; t <= bset_tree_last(b); t++) 742fafff81cSKent Overstreet if (k < bset_bkey_last(t->data)) 743cafe5635SKent Overstreet goto found_set; 744cafe5635SKent Overstreet 745cafe5635SKent Overstreet BUG(); 746cafe5635SKent Overstreet found_set: 747cafe5635SKent Overstreet if (!t->size || !bset_written(b, t)) 748cafe5635SKent Overstreet return; 749cafe5635SKent Overstreet 750cafe5635SKent Overstreet inorder = bkey_to_cacheline(t, k); 751cafe5635SKent Overstreet 752cafe5635SKent Overstreet if (k == t->data->start) 753cafe5635SKent Overstreet goto fix_left; 754cafe5635SKent Overstreet 755fafff81cSKent Overstreet if (bkey_next(k) == bset_bkey_last(t->data)) { 756cafe5635SKent Overstreet t->end = *k; 757cafe5635SKent Overstreet goto fix_right; 758cafe5635SKent Overstreet } 759cafe5635SKent Overstreet 760cafe5635SKent Overstreet j = inorder_to_tree(inorder, t); 761cafe5635SKent Overstreet 762cafe5635SKent Overstreet if (j && 763cafe5635SKent Overstreet j < t->size && 764cafe5635SKent Overstreet k == tree_to_bkey(t, j)) 765cafe5635SKent Overstreet fix_left: do { 766cafe5635SKent Overstreet make_bfloat(t, j); 767cafe5635SKent Overstreet j = j * 2; 768cafe5635SKent Overstreet } while (j < t->size); 769cafe5635SKent Overstreet 770cafe5635SKent Overstreet j = inorder_to_tree(inorder + 1, t); 771cafe5635SKent Overstreet 772cafe5635SKent Overstreet if (j && 773cafe5635SKent Overstreet j < t->size && 774cafe5635SKent Overstreet k == tree_to_prev_bkey(t, j)) 775cafe5635SKent Overstreet fix_right: do { 776cafe5635SKent Overstreet make_bfloat(t, j); 777cafe5635SKent Overstreet j = j * 2 + 1; 778cafe5635SKent Overstreet } while (j < t->size); 779cafe5635SKent Overstreet } 780cafe5635SKent Overstreet 781a85e968eSKent Overstreet static void bch_bset_fix_lookup_table(struct btree_keys *b, 782ee811287SKent Overstreet struct bset_tree *t, 783ee811287SKent Overstreet struct bkey *k) 784cafe5635SKent Overstreet { 7856f10f7d1SColy Li unsigned int shift = bkey_u64s(k); 7866f10f7d1SColy Li unsigned int j = bkey_to_cacheline(t, k); 787cafe5635SKent Overstreet 788cafe5635SKent Overstreet /* We're getting called from btree_split() or btree_gc, just bail out */ 789cafe5635SKent Overstreet if (!t->size) 790cafe5635SKent Overstreet return; 791cafe5635SKent Overstreet 7923be11dbaSColy Li /* 7933be11dbaSColy Li * k is the key we just inserted; we need to find the entry in the 794cafe5635SKent Overstreet * lookup table for the first key that is strictly greater than k: 795cafe5635SKent Overstreet * it's either k's cacheline or the next one 796cafe5635SKent Overstreet */ 7979dd6358aSKent Overstreet while (j < t->size && 798cafe5635SKent Overstreet table_to_bkey(t, j) <= k) 799cafe5635SKent Overstreet j++; 800cafe5635SKent Overstreet 8013be11dbaSColy Li /* 8023be11dbaSColy Li * Adjust all the lookup table entries, and find a new key for any that 803cafe5635SKent Overstreet * have gotten too big 804cafe5635SKent Overstreet */ 805cafe5635SKent Overstreet for (; j < t->size; j++) { 806cafe5635SKent Overstreet t->prev[j] += shift; 807cafe5635SKent Overstreet 808cafe5635SKent Overstreet if (t->prev[j] > 7) { 809cafe5635SKent Overstreet k = table_to_bkey(t, j - 1); 810cafe5635SKent Overstreet 811cafe5635SKent Overstreet while (k < cacheline_to_bkey(t, j, 0)) 812cafe5635SKent Overstreet k = bkey_next(k); 813cafe5635SKent Overstreet 8149dd6358aSKent Overstreet t->prev[j] = bkey_to_cacheline_offset(t, j, k); 815cafe5635SKent Overstreet } 816cafe5635SKent Overstreet } 817cafe5635SKent Overstreet 818a85e968eSKent Overstreet if (t->size == b->set->tree + btree_keys_cachelines(b) - t->tree) 819cafe5635SKent Overstreet return; 820cafe5635SKent Overstreet 821cafe5635SKent Overstreet /* Possibly add a new entry to the end of the lookup table */ 822cafe5635SKent Overstreet 823cafe5635SKent Overstreet for (k = table_to_bkey(t, t->size - 1); 824fafff81cSKent Overstreet k != bset_bkey_last(t->data); 825cafe5635SKent Overstreet k = bkey_next(k)) 826cafe5635SKent Overstreet if (t->size == bkey_to_cacheline(t, k)) { 827b0d30981SColy Li t->prev[t->size] = 828b0d30981SColy Li bkey_to_cacheline_offset(t, t->size, k); 829cafe5635SKent Overstreet t->size++; 830cafe5635SKent Overstreet } 831cafe5635SKent Overstreet } 832cafe5635SKent Overstreet 8330f49cf3dSNicholas Swenson /* 8340f49cf3dSNicholas Swenson * Tries to merge l and r: l should be lower than r 8350f49cf3dSNicholas Swenson * Returns true if we were able to merge. If we did merge, l will be the merged 8360f49cf3dSNicholas Swenson * key, r will be untouched. 8370f49cf3dSNicholas Swenson */ 8380f49cf3dSNicholas Swenson bool bch_bkey_try_merge(struct btree_keys *b, struct bkey *l, struct bkey *r) 8390f49cf3dSNicholas Swenson { 8400f49cf3dSNicholas Swenson if (!b->ops->key_merge) 8410f49cf3dSNicholas Swenson return false; 8420f49cf3dSNicholas Swenson 8430f49cf3dSNicholas Swenson /* 8440f49cf3dSNicholas Swenson * Generic header checks 8450f49cf3dSNicholas Swenson * Assumes left and right are in order 8460f49cf3dSNicholas Swenson * Left and right must be exactly aligned 8470f49cf3dSNicholas Swenson */ 8483bdad1e4SNicholas Swenson if (!bch_bkey_equal_header(l, r) || 8490f49cf3dSNicholas Swenson bkey_cmp(l, &START_KEY(r))) 8500f49cf3dSNicholas Swenson return false; 8510f49cf3dSNicholas Swenson 8520f49cf3dSNicholas Swenson return b->ops->key_merge(b, l, r); 8530f49cf3dSNicholas Swenson } 8540f49cf3dSNicholas Swenson 855a85e968eSKent Overstreet void bch_bset_insert(struct btree_keys *b, struct bkey *where, 856ee811287SKent Overstreet struct bkey *insert) 857cafe5635SKent Overstreet { 858ee811287SKent Overstreet struct bset_tree *t = bset_tree_last(b); 859cafe5635SKent Overstreet 860a85e968eSKent Overstreet BUG_ON(!b->last_set_unwritten); 861ee811287SKent Overstreet BUG_ON(bset_byte_offset(b, t->data) + 862ee811287SKent Overstreet __set_bytes(t->data, t->data->keys + bkey_u64s(insert)) > 863ee811287SKent Overstreet PAGE_SIZE << b->page_order); 864cafe5635SKent Overstreet 865ee811287SKent Overstreet memmove((uint64_t *) where + bkey_u64s(insert), 866ee811287SKent Overstreet where, 867ee811287SKent Overstreet (void *) bset_bkey_last(t->data) - (void *) where); 868cafe5635SKent Overstreet 869ee811287SKent Overstreet t->data->keys += bkey_u64s(insert); 870ee811287SKent Overstreet bkey_copy(where, insert); 871ee811287SKent Overstreet bch_bset_fix_lookup_table(b, t, where); 872cafe5635SKent Overstreet } 873cafe5635SKent Overstreet 8746f10f7d1SColy Li unsigned int bch_btree_insert_key(struct btree_keys *b, struct bkey *k, 875829a60b9SKent Overstreet struct bkey *replace_key) 876829a60b9SKent Overstreet { 8776f10f7d1SColy Li unsigned int status = BTREE_INSERT_STATUS_NO_INSERT; 878829a60b9SKent Overstreet struct bset *i = bset_tree_last(b)->data; 879829a60b9SKent Overstreet struct bkey *m, *prev = NULL; 880829a60b9SKent Overstreet struct btree_iter iter; 88131b90956SColy Li struct bkey preceding_key_on_stack = ZERO_KEY; 88231b90956SColy Li struct bkey *preceding_key_p = &preceding_key_on_stack; 883829a60b9SKent Overstreet 884829a60b9SKent Overstreet BUG_ON(b->ops->is_extents && !KEY_SIZE(k)); 885829a60b9SKent Overstreet 88631b90956SColy Li /* 88731b90956SColy Li * If k has preceding key, preceding_key_p will be set to address 88831b90956SColy Li * of k's preceding key; otherwise preceding_key_p will be set 88931b90956SColy Li * to NULL inside preceding_key(). 89031b90956SColy Li */ 89131b90956SColy Li if (b->ops->is_extents) 89231b90956SColy Li preceding_key(&START_KEY(k), &preceding_key_p); 89331b90956SColy Li else 89431b90956SColy Li preceding_key(k, &preceding_key_p); 89531b90956SColy Li 89631b90956SColy Li m = bch_btree_iter_init(b, &iter, preceding_key_p); 897829a60b9SKent Overstreet 898829a60b9SKent Overstreet if (b->ops->insert_fixup(b, k, &iter, replace_key)) 899829a60b9SKent Overstreet return status; 900829a60b9SKent Overstreet 901829a60b9SKent Overstreet status = BTREE_INSERT_STATUS_INSERT; 902829a60b9SKent Overstreet 903829a60b9SKent Overstreet while (m != bset_bkey_last(i) && 904829a60b9SKent Overstreet bkey_cmp(k, b->ops->is_extents ? &START_KEY(m) : m) > 0) 905829a60b9SKent Overstreet prev = m, m = bkey_next(m); 906829a60b9SKent Overstreet 907829a60b9SKent Overstreet /* prev is in the tree, if we merge we're done */ 908829a60b9SKent Overstreet status = BTREE_INSERT_STATUS_BACK_MERGE; 909829a60b9SKent Overstreet if (prev && 910829a60b9SKent Overstreet bch_bkey_try_merge(b, prev, k)) 911829a60b9SKent Overstreet goto merged; 912829a60b9SKent Overstreet #if 0 913829a60b9SKent Overstreet status = BTREE_INSERT_STATUS_OVERWROTE; 914829a60b9SKent Overstreet if (m != bset_bkey_last(i) && 915829a60b9SKent Overstreet KEY_PTRS(m) == KEY_PTRS(k) && !KEY_SIZE(m)) 916829a60b9SKent Overstreet goto copy; 917829a60b9SKent Overstreet #endif 918829a60b9SKent Overstreet status = BTREE_INSERT_STATUS_FRONT_MERGE; 919829a60b9SKent Overstreet if (m != bset_bkey_last(i) && 920829a60b9SKent Overstreet bch_bkey_try_merge(b, k, m)) 921829a60b9SKent Overstreet goto copy; 922829a60b9SKent Overstreet 923829a60b9SKent Overstreet bch_bset_insert(b, m, k); 924829a60b9SKent Overstreet copy: bkey_copy(m, k); 925829a60b9SKent Overstreet merged: 926829a60b9SKent Overstreet return status; 927829a60b9SKent Overstreet } 928829a60b9SKent Overstreet 929829a60b9SKent Overstreet /* Lookup */ 930829a60b9SKent Overstreet 931cafe5635SKent Overstreet struct bset_search_iter { 932cafe5635SKent Overstreet struct bkey *l, *r; 933cafe5635SKent Overstreet }; 934cafe5635SKent Overstreet 935a85e968eSKent Overstreet static struct bset_search_iter bset_search_write_set(struct bset_tree *t, 936cafe5635SKent Overstreet const struct bkey *search) 937cafe5635SKent Overstreet { 9386f10f7d1SColy Li unsigned int li = 0, ri = t->size; 939cafe5635SKent Overstreet 940cafe5635SKent Overstreet while (li + 1 != ri) { 9416f10f7d1SColy Li unsigned int m = (li + ri) >> 1; 942cafe5635SKent Overstreet 943cafe5635SKent Overstreet if (bkey_cmp(table_to_bkey(t, m), search) > 0) 944cafe5635SKent Overstreet ri = m; 945cafe5635SKent Overstreet else 946cafe5635SKent Overstreet li = m; 947cafe5635SKent Overstreet } 948cafe5635SKent Overstreet 949cafe5635SKent Overstreet return (struct bset_search_iter) { 950cafe5635SKent Overstreet table_to_bkey(t, li), 951fafff81cSKent Overstreet ri < t->size ? table_to_bkey(t, ri) : bset_bkey_last(t->data) 952cafe5635SKent Overstreet }; 953cafe5635SKent Overstreet } 954cafe5635SKent Overstreet 955a85e968eSKent Overstreet static struct bset_search_iter bset_search_tree(struct bset_tree *t, 956cafe5635SKent Overstreet const struct bkey *search) 957cafe5635SKent Overstreet { 958cafe5635SKent Overstreet struct bkey *l, *r; 959cafe5635SKent Overstreet struct bkey_float *f; 9606f10f7d1SColy Li unsigned int inorder, j, n = 1; 961cafe5635SKent Overstreet 962cafe5635SKent Overstreet do { 9636f10f7d1SColy Li unsigned int p = n << 4; 9641fae7cf0SColy Li 965f960facbSColy Li if (p < t->size) 966cafe5635SKent Overstreet prefetch(&t->tree[p]); 967cafe5635SKent Overstreet 968cafe5635SKent Overstreet j = n; 969cafe5635SKent Overstreet f = &t->tree[j]; 970cafe5635SKent Overstreet 971944a4f34SColy Li if (likely(f->exponent != 127)) { 972944a4f34SColy Li if (f->mantissa >= bfloat_mantissa(search, f)) 973944a4f34SColy Li n = j * 2; 974cafe5635SKent Overstreet else 975944a4f34SColy Li n = j * 2 + 1; 976944a4f34SColy Li } else { 977944a4f34SColy Li if (bkey_cmp(tree_to_bkey(t, j), search) > 0) 978944a4f34SColy Li n = j * 2; 979944a4f34SColy Li else 980944a4f34SColy Li n = j * 2 + 1; 981944a4f34SColy Li } 982cafe5635SKent Overstreet } while (n < t->size); 983cafe5635SKent Overstreet 984cafe5635SKent Overstreet inorder = to_inorder(j, t); 985cafe5635SKent Overstreet 986cafe5635SKent Overstreet /* 987cafe5635SKent Overstreet * n would have been the node we recursed to - the low bit tells us if 988cafe5635SKent Overstreet * we recursed left or recursed right. 989cafe5635SKent Overstreet */ 990cafe5635SKent Overstreet if (n & 1) { 991cafe5635SKent Overstreet l = cacheline_to_bkey(t, inorder, f->m); 992cafe5635SKent Overstreet 993cafe5635SKent Overstreet if (++inorder != t->size) { 994cafe5635SKent Overstreet f = &t->tree[inorder_next(j, t->size)]; 995cafe5635SKent Overstreet r = cacheline_to_bkey(t, inorder, f->m); 996cafe5635SKent Overstreet } else 997fafff81cSKent Overstreet r = bset_bkey_last(t->data); 998cafe5635SKent Overstreet } else { 999cafe5635SKent Overstreet r = cacheline_to_bkey(t, inorder, f->m); 1000cafe5635SKent Overstreet 1001cafe5635SKent Overstreet if (--inorder) { 1002cafe5635SKent Overstreet f = &t->tree[inorder_prev(j, t->size)]; 1003cafe5635SKent Overstreet l = cacheline_to_bkey(t, inorder, f->m); 1004cafe5635SKent Overstreet } else 1005cafe5635SKent Overstreet l = t->data->start; 1006cafe5635SKent Overstreet } 1007cafe5635SKent Overstreet 1008cafe5635SKent Overstreet return (struct bset_search_iter) {l, r}; 1009cafe5635SKent Overstreet } 1010cafe5635SKent Overstreet 1011c052dd9aSKent Overstreet struct bkey *__bch_bset_search(struct btree_keys *b, struct bset_tree *t, 1012cafe5635SKent Overstreet const struct bkey *search) 1013cafe5635SKent Overstreet { 1014cafe5635SKent Overstreet struct bset_search_iter i; 1015cafe5635SKent Overstreet 1016cafe5635SKent Overstreet /* 1017cafe5635SKent Overstreet * First, we search for a cacheline, then lastly we do a linear search 1018cafe5635SKent Overstreet * within that cacheline. 1019cafe5635SKent Overstreet * 1020cafe5635SKent Overstreet * To search for the cacheline, there's three different possibilities: 1021cafe5635SKent Overstreet * * The set is too small to have a search tree, so we just do a linear 1022cafe5635SKent Overstreet * search over the whole set. 1023cafe5635SKent Overstreet * * The set is the one we're currently inserting into; keeping a full 1024cafe5635SKent Overstreet * auxiliary search tree up to date would be too expensive, so we 1025cafe5635SKent Overstreet * use a much simpler lookup table to do a binary search - 1026cafe5635SKent Overstreet * bset_search_write_set(). 1027cafe5635SKent Overstreet * * Or we use the auxiliary search tree we constructed earlier - 1028cafe5635SKent Overstreet * bset_search_tree() 1029cafe5635SKent Overstreet */ 1030cafe5635SKent Overstreet 1031cafe5635SKent Overstreet if (unlikely(!t->size)) { 1032cafe5635SKent Overstreet i.l = t->data->start; 1033fafff81cSKent Overstreet i.r = bset_bkey_last(t->data); 1034c052dd9aSKent Overstreet } else if (bset_written(b, t)) { 1035cafe5635SKent Overstreet /* 1036cafe5635SKent Overstreet * Each node in the auxiliary search tree covers a certain range 1037cafe5635SKent Overstreet * of bits, and keys above and below the set it covers might 1038cafe5635SKent Overstreet * differ outside those bits - so we have to special case the 1039cafe5635SKent Overstreet * start and end - handle that here: 1040cafe5635SKent Overstreet */ 1041cafe5635SKent Overstreet 1042cafe5635SKent Overstreet if (unlikely(bkey_cmp(search, &t->end) >= 0)) 1043fafff81cSKent Overstreet return bset_bkey_last(t->data); 1044cafe5635SKent Overstreet 1045cafe5635SKent Overstreet if (unlikely(bkey_cmp(search, t->data->start) < 0)) 1046cafe5635SKent Overstreet return t->data->start; 1047cafe5635SKent Overstreet 1048a85e968eSKent Overstreet i = bset_search_tree(t, search); 1049a85e968eSKent Overstreet } else { 1050c052dd9aSKent Overstreet BUG_ON(!b->nsets && 1051a85e968eSKent Overstreet t->size < bkey_to_cacheline(t, bset_bkey_last(t->data))); 1052a85e968eSKent Overstreet 1053a85e968eSKent Overstreet i = bset_search_write_set(t, search); 1054a85e968eSKent Overstreet } 1055cafe5635SKent Overstreet 1056c052dd9aSKent Overstreet if (btree_keys_expensive_checks(b)) { 1057c052dd9aSKent Overstreet BUG_ON(bset_written(b, t) && 1058cafe5635SKent Overstreet i.l != t->data->start && 1059cafe5635SKent Overstreet bkey_cmp(tree_to_prev_bkey(t, 1060cafe5635SKent Overstreet inorder_to_tree(bkey_to_cacheline(t, i.l), t)), 1061cafe5635SKent Overstreet search) > 0); 1062cafe5635SKent Overstreet 1063fafff81cSKent Overstreet BUG_ON(i.r != bset_bkey_last(t->data) && 1064cafe5635SKent Overstreet bkey_cmp(i.r, search) <= 0); 1065280481d0SKent Overstreet } 1066cafe5635SKent Overstreet 1067cafe5635SKent Overstreet while (likely(i.l != i.r) && 1068cafe5635SKent Overstreet bkey_cmp(i.l, search) <= 0) 1069cafe5635SKent Overstreet i.l = bkey_next(i.l); 1070cafe5635SKent Overstreet 1071cafe5635SKent Overstreet return i.l; 1072cafe5635SKent Overstreet } 1073cafe5635SKent Overstreet 1074cafe5635SKent Overstreet /* Btree iterator */ 1075cafe5635SKent Overstreet 1076911c9610SKent Overstreet typedef bool (btree_iter_cmp_fn)(struct btree_iter_set, 1077911c9610SKent Overstreet struct btree_iter_set); 1078911c9610SKent Overstreet 1079cafe5635SKent Overstreet static inline bool btree_iter_cmp(struct btree_iter_set l, 1080cafe5635SKent Overstreet struct btree_iter_set r) 1081cafe5635SKent Overstreet { 1082911c9610SKent Overstreet return bkey_cmp(l.k, r.k) > 0; 1083cafe5635SKent Overstreet } 1084cafe5635SKent Overstreet 1085cafe5635SKent Overstreet static inline bool btree_iter_end(struct btree_iter *iter) 1086cafe5635SKent Overstreet { 1087cafe5635SKent Overstreet return !iter->used; 1088cafe5635SKent Overstreet } 1089cafe5635SKent Overstreet 1090cafe5635SKent Overstreet void bch_btree_iter_push(struct btree_iter *iter, struct bkey *k, 1091cafe5635SKent Overstreet struct bkey *end) 1092cafe5635SKent Overstreet { 1093cafe5635SKent Overstreet if (k != end) 1094cafe5635SKent Overstreet BUG_ON(!heap_add(iter, 1095cafe5635SKent Overstreet ((struct btree_iter_set) { k, end }), 1096cafe5635SKent Overstreet btree_iter_cmp)); 1097cafe5635SKent Overstreet } 1098cafe5635SKent Overstreet 1099c052dd9aSKent Overstreet static struct bkey *__bch_btree_iter_init(struct btree_keys *b, 1100911c9610SKent Overstreet struct btree_iter *iter, 1101911c9610SKent Overstreet struct bkey *search, 1102911c9610SKent Overstreet struct bset_tree *start) 1103cafe5635SKent Overstreet { 1104cafe5635SKent Overstreet struct bkey *ret = NULL; 11051fae7cf0SColy Li 1106cafe5635SKent Overstreet iter->size = ARRAY_SIZE(iter->data); 1107cafe5635SKent Overstreet iter->used = 0; 1108cafe5635SKent Overstreet 1109280481d0SKent Overstreet #ifdef CONFIG_BCACHE_DEBUG 1110280481d0SKent Overstreet iter->b = b; 1111280481d0SKent Overstreet #endif 1112280481d0SKent Overstreet 1113c052dd9aSKent Overstreet for (; start <= bset_tree_last(b); start++) { 1114cafe5635SKent Overstreet ret = bch_bset_search(b, start, search); 1115fafff81cSKent Overstreet bch_btree_iter_push(iter, ret, bset_bkey_last(start->data)); 1116cafe5635SKent Overstreet } 1117cafe5635SKent Overstreet 1118cafe5635SKent Overstreet return ret; 1119cafe5635SKent Overstreet } 1120cafe5635SKent Overstreet 1121c052dd9aSKent Overstreet struct bkey *bch_btree_iter_init(struct btree_keys *b, 1122911c9610SKent Overstreet struct btree_iter *iter, 1123911c9610SKent Overstreet struct bkey *search) 1124911c9610SKent Overstreet { 1125c052dd9aSKent Overstreet return __bch_btree_iter_init(b, iter, search, b->set); 1126911c9610SKent Overstreet } 1127911c9610SKent Overstreet 1128911c9610SKent Overstreet static inline struct bkey *__bch_btree_iter_next(struct btree_iter *iter, 1129911c9610SKent Overstreet btree_iter_cmp_fn *cmp) 1130cafe5635SKent Overstreet { 113142361469SBart Van Assche struct btree_iter_set b __maybe_unused; 1132cafe5635SKent Overstreet struct bkey *ret = NULL; 1133cafe5635SKent Overstreet 1134cafe5635SKent Overstreet if (!btree_iter_end(iter)) { 1135280481d0SKent Overstreet bch_btree_iter_next_check(iter); 1136280481d0SKent Overstreet 1137cafe5635SKent Overstreet ret = iter->data->k; 1138cafe5635SKent Overstreet iter->data->k = bkey_next(iter->data->k); 1139cafe5635SKent Overstreet 1140cafe5635SKent Overstreet if (iter->data->k > iter->data->end) { 1141cc0f4eaaSKent Overstreet WARN_ONCE(1, "bset was corrupt!\n"); 1142cafe5635SKent Overstreet iter->data->k = iter->data->end; 1143cafe5635SKent Overstreet } 1144cafe5635SKent Overstreet 1145cafe5635SKent Overstreet if (iter->data->k == iter->data->end) 114642361469SBart Van Assche heap_pop(iter, b, cmp); 1147cafe5635SKent Overstreet else 1148911c9610SKent Overstreet heap_sift(iter, 0, cmp); 1149cafe5635SKent Overstreet } 1150cafe5635SKent Overstreet 1151cafe5635SKent Overstreet return ret; 1152cafe5635SKent Overstreet } 1153cafe5635SKent Overstreet 1154911c9610SKent Overstreet struct bkey *bch_btree_iter_next(struct btree_iter *iter) 1155911c9610SKent Overstreet { 1156911c9610SKent Overstreet return __bch_btree_iter_next(iter, btree_iter_cmp); 1157911c9610SKent Overstreet 1158911c9610SKent Overstreet } 1159911c9610SKent Overstreet 1160cafe5635SKent Overstreet struct bkey *bch_btree_iter_next_filter(struct btree_iter *iter, 1161a85e968eSKent Overstreet struct btree_keys *b, ptr_filter_fn fn) 1162cafe5635SKent Overstreet { 1163cafe5635SKent Overstreet struct bkey *ret; 1164cafe5635SKent Overstreet 1165cafe5635SKent Overstreet do { 1166cafe5635SKent Overstreet ret = bch_btree_iter_next(iter); 1167cafe5635SKent Overstreet } while (ret && fn(b, ret)); 1168cafe5635SKent Overstreet 1169cafe5635SKent Overstreet return ret; 1170cafe5635SKent Overstreet } 1171cafe5635SKent Overstreet 1172cafe5635SKent Overstreet /* Mergesort */ 1173cafe5635SKent Overstreet 117467539e85SKent Overstreet void bch_bset_sort_state_free(struct bset_sort_state *state) 117567539e85SKent Overstreet { 1176d19936a2SKent Overstreet mempool_exit(&state->pool); 117767539e85SKent Overstreet } 117867539e85SKent Overstreet 11796f10f7d1SColy Li int bch_bset_sort_state_init(struct bset_sort_state *state, 11806f10f7d1SColy Li unsigned int page_order) 118167539e85SKent Overstreet { 118267539e85SKent Overstreet spin_lock_init(&state->time.lock); 118367539e85SKent Overstreet 118467539e85SKent Overstreet state->page_order = page_order; 118567539e85SKent Overstreet state->crit_factor = int_sqrt(1 << page_order); 118667539e85SKent Overstreet 1187d19936a2SKent Overstreet return mempool_init_page_pool(&state->pool, 1, page_order); 118867539e85SKent Overstreet } 118967539e85SKent Overstreet 1190a85e968eSKent Overstreet static void btree_mergesort(struct btree_keys *b, struct bset *out, 1191cafe5635SKent Overstreet struct btree_iter *iter, 1192cafe5635SKent Overstreet bool fixup, bool remove_stale) 1193cafe5635SKent Overstreet { 1194911c9610SKent Overstreet int i; 1195cafe5635SKent Overstreet struct bkey *k, *last = NULL; 1196ef71ec00SKent Overstreet BKEY_PADDED(k) tmp; 1197a85e968eSKent Overstreet bool (*bad)(struct btree_keys *, const struct bkey *) = remove_stale 1198cafe5635SKent Overstreet ? bch_ptr_bad 1199cafe5635SKent Overstreet : bch_ptr_invalid; 1200cafe5635SKent Overstreet 1201911c9610SKent Overstreet /* Heapify the iterator, using our comparison function */ 1202911c9610SKent Overstreet for (i = iter->used / 2 - 1; i >= 0; --i) 120365d45231SKent Overstreet heap_sift(iter, i, b->ops->sort_cmp); 1204911c9610SKent Overstreet 1205cafe5635SKent Overstreet while (!btree_iter_end(iter)) { 120665d45231SKent Overstreet if (b->ops->sort_fixup && fixup) 120765d45231SKent Overstreet k = b->ops->sort_fixup(iter, &tmp.k); 1208ef71ec00SKent Overstreet else 1209ef71ec00SKent Overstreet k = NULL; 1210cafe5635SKent Overstreet 1211ef71ec00SKent Overstreet if (!k) 121265d45231SKent Overstreet k = __bch_btree_iter_next(iter, b->ops->sort_cmp); 1213ef71ec00SKent Overstreet 1214cafe5635SKent Overstreet if (bad(b, k)) 1215cafe5635SKent Overstreet continue; 1216cafe5635SKent Overstreet 1217cafe5635SKent Overstreet if (!last) { 1218cafe5635SKent Overstreet last = out->start; 1219cafe5635SKent Overstreet bkey_copy(last, k); 122065d45231SKent Overstreet } else if (!bch_bkey_try_merge(b, last, k)) { 1221cafe5635SKent Overstreet last = bkey_next(last); 1222cafe5635SKent Overstreet bkey_copy(last, k); 1223cafe5635SKent Overstreet } 1224cafe5635SKent Overstreet } 1225cafe5635SKent Overstreet 1226cafe5635SKent Overstreet out->keys = last ? (uint64_t *) bkey_next(last) - out->d : 0; 1227cafe5635SKent Overstreet 122846f5aa88SJoe Perches pr_debug("sorted %i keys\n", out->keys); 1229cafe5635SKent Overstreet } 1230cafe5635SKent Overstreet 1231a85e968eSKent Overstreet static void __btree_sort(struct btree_keys *b, struct btree_iter *iter, 12326f10f7d1SColy Li unsigned int start, unsigned int order, bool fixup, 123367539e85SKent Overstreet struct bset_sort_state *state) 1234cafe5635SKent Overstreet { 1235cafe5635SKent Overstreet uint64_t start_time; 12360a451145SKent Overstreet bool used_mempool = false; 1237501d52a9SKent Overstreet struct bset *out = (void *) __get_free_pages(__GFP_NOWARN|GFP_NOWAIT, 1238cafe5635SKent Overstreet order); 1239cafe5635SKent Overstreet if (!out) { 12403572324aSKent Overstreet struct page *outp; 12413572324aSKent Overstreet 124267539e85SKent Overstreet BUG_ON(order > state->page_order); 124367539e85SKent Overstreet 1244d19936a2SKent Overstreet outp = mempool_alloc(&state->pool, GFP_NOIO); 12453572324aSKent Overstreet out = page_address(outp); 12460a451145SKent Overstreet used_mempool = true; 1247a85e968eSKent Overstreet order = state->page_order; 1248cafe5635SKent Overstreet } 1249cafe5635SKent Overstreet 1250cafe5635SKent Overstreet start_time = local_clock(); 1251cafe5635SKent Overstreet 125267539e85SKent Overstreet btree_mergesort(b, out, iter, fixup, false); 1253cafe5635SKent Overstreet b->nsets = start; 1254cafe5635SKent Overstreet 1255cafe5635SKent Overstreet if (!start && order == b->page_order) { 1256cafe5635SKent Overstreet /* 1257cafe5635SKent Overstreet * Our temporary buffer is the same size as the btree node's 1258cafe5635SKent Overstreet * buffer, we can just swap buffers instead of doing a big 1259cafe5635SKent Overstreet * memcpy() 12607a0bc2a8SColy Li * 12617a0bc2a8SColy Li * Don't worry event 'out' is allocated from mempool, it can 12627a0bc2a8SColy Li * still be swapped here. Because state->pool is a page mempool 12637a0bc2a8SColy Li * creaated by by mempool_init_page_pool(), which allocates 12647a0bc2a8SColy Li * pages by alloc_pages() indeed. 1265cafe5635SKent Overstreet */ 1266cafe5635SKent Overstreet 1267a85e968eSKent Overstreet out->magic = b->set->data->magic; 1268a85e968eSKent Overstreet out->seq = b->set->data->seq; 1269a85e968eSKent Overstreet out->version = b->set->data->version; 1270a85e968eSKent Overstreet swap(out, b->set->data); 1271cafe5635SKent Overstreet } else { 1272a85e968eSKent Overstreet b->set[start].data->keys = out->keys; 1273a85e968eSKent Overstreet memcpy(b->set[start].data->start, out->start, 1274fafff81cSKent Overstreet (void *) bset_bkey_last(out) - (void *) out->start); 1275cafe5635SKent Overstreet } 1276cafe5635SKent Overstreet 12770a451145SKent Overstreet if (used_mempool) 1278d19936a2SKent Overstreet mempool_free(virt_to_page(out), &state->pool); 1279cafe5635SKent Overstreet else 1280cafe5635SKent Overstreet free_pages((unsigned long) out, order); 1281cafe5635SKent Overstreet 1282a85e968eSKent Overstreet bch_bset_build_written_tree(b); 1283cafe5635SKent Overstreet 128465d22e91SKent Overstreet if (!start) 128567539e85SKent Overstreet bch_time_stats_update(&state->time, start_time); 1286cafe5635SKent Overstreet } 1287cafe5635SKent Overstreet 12886f10f7d1SColy Li void bch_btree_sort_partial(struct btree_keys *b, unsigned int start, 128967539e85SKent Overstreet struct bset_sort_state *state) 1290cafe5635SKent Overstreet { 129189ebb4a2SKent Overstreet size_t order = b->page_order, keys = 0; 1292cafe5635SKent Overstreet struct btree_iter iter; 129389ebb4a2SKent Overstreet int oldsize = bch_count_data(b); 1294280481d0SKent Overstreet 129589ebb4a2SKent Overstreet __bch_btree_iter_init(b, &iter, NULL, &b->set[start]); 1296cafe5635SKent Overstreet 1297cafe5635SKent Overstreet if (start) { 12986f10f7d1SColy Li unsigned int i; 1299cafe5635SKent Overstreet 130089ebb4a2SKent Overstreet for (i = start; i <= b->nsets; i++) 130189ebb4a2SKent Overstreet keys += b->set[i].data->keys; 1302cafe5635SKent Overstreet 130389ebb4a2SKent Overstreet order = get_order(__set_bytes(b->set->data, keys)); 1304cafe5635SKent Overstreet } 1305cafe5635SKent Overstreet 130689ebb4a2SKent Overstreet __btree_sort(b, &iter, start, order, false, state); 1307cafe5635SKent Overstreet 130889ebb4a2SKent Overstreet EBUG_ON(oldsize >= 0 && bch_count_data(b) != oldsize); 1309cafe5635SKent Overstreet } 1310cafe5635SKent Overstreet 1311a85e968eSKent Overstreet void bch_btree_sort_and_fix_extents(struct btree_keys *b, 1312a85e968eSKent Overstreet struct btree_iter *iter, 131367539e85SKent Overstreet struct bset_sort_state *state) 1314cafe5635SKent Overstreet { 131567539e85SKent Overstreet __btree_sort(b, iter, 0, b->page_order, true, state); 1316cafe5635SKent Overstreet } 1317cafe5635SKent Overstreet 131889ebb4a2SKent Overstreet void bch_btree_sort_into(struct btree_keys *b, struct btree_keys *new, 131967539e85SKent Overstreet struct bset_sort_state *state) 1320cafe5635SKent Overstreet { 1321cafe5635SKent Overstreet uint64_t start_time = local_clock(); 1322cafe5635SKent Overstreet struct btree_iter iter; 13231fae7cf0SColy Li 132489ebb4a2SKent Overstreet bch_btree_iter_init(b, &iter, NULL); 1325cafe5635SKent Overstreet 132689ebb4a2SKent Overstreet btree_mergesort(b, new->set->data, &iter, false, true); 1327cafe5635SKent Overstreet 132867539e85SKent Overstreet bch_time_stats_update(&state->time, start_time); 1329cafe5635SKent Overstreet 133089ebb4a2SKent Overstreet new->set->size = 0; // XXX: why? 1331cafe5635SKent Overstreet } 1332cafe5635SKent Overstreet 13336ded34d1SKent Overstreet #define SORT_CRIT (4096 / sizeof(uint64_t)) 13346ded34d1SKent Overstreet 133589ebb4a2SKent Overstreet void bch_btree_sort_lazy(struct btree_keys *b, struct bset_sort_state *state) 1336cafe5635SKent Overstreet { 13376f10f7d1SColy Li unsigned int crit = SORT_CRIT; 13386ded34d1SKent Overstreet int i; 1339cafe5635SKent Overstreet 13406ded34d1SKent Overstreet /* Don't sort if nothing to do */ 134189ebb4a2SKent Overstreet if (!b->nsets) 13426ded34d1SKent Overstreet goto out; 1343cafe5635SKent Overstreet 134489ebb4a2SKent Overstreet for (i = b->nsets - 1; i >= 0; --i) { 134567539e85SKent Overstreet crit *= state->crit_factor; 13466ded34d1SKent Overstreet 134789ebb4a2SKent Overstreet if (b->set[i].data->keys < crit) { 134867539e85SKent Overstreet bch_btree_sort_partial(b, i, state); 13496ded34d1SKent Overstreet return; 13506ded34d1SKent Overstreet } 1351cafe5635SKent Overstreet } 1352cafe5635SKent Overstreet 13536ded34d1SKent Overstreet /* Sort if we'd overflow */ 135489ebb4a2SKent Overstreet if (b->nsets + 1 == MAX_BSETS) { 135567539e85SKent Overstreet bch_btree_sort(b, state); 13566ded34d1SKent Overstreet return; 13576ded34d1SKent Overstreet } 13586ded34d1SKent Overstreet 13596ded34d1SKent Overstreet out: 136089ebb4a2SKent Overstreet bch_bset_build_written_tree(b); 1361cafe5635SKent Overstreet } 1362cafe5635SKent Overstreet 1363f67342ddSKent Overstreet void bch_btree_keys_stats(struct btree_keys *b, struct bset_stats *stats) 1364cafe5635SKent Overstreet { 13656f10f7d1SColy Li unsigned int i; 1366cafe5635SKent Overstreet 1367f67342ddSKent Overstreet for (i = 0; i <= b->nsets; i++) { 1368f67342ddSKent Overstreet struct bset_tree *t = &b->set[i]; 1369cafe5635SKent Overstreet size_t bytes = t->data->keys * sizeof(uint64_t); 1370cafe5635SKent Overstreet size_t j; 1371cafe5635SKent Overstreet 1372f67342ddSKent Overstreet if (bset_written(b, t)) { 1373cafe5635SKent Overstreet stats->sets_written++; 1374cafe5635SKent Overstreet stats->bytes_written += bytes; 1375cafe5635SKent Overstreet 1376cafe5635SKent Overstreet stats->floats += t->size - 1; 1377cafe5635SKent Overstreet 1378cafe5635SKent Overstreet for (j = 1; j < t->size; j++) 1379cafe5635SKent Overstreet if (t->tree[j].exponent == 127) 1380cafe5635SKent Overstreet stats->failed++; 1381cafe5635SKent Overstreet } else { 1382cafe5635SKent Overstreet stats->sets_unwritten++; 1383cafe5635SKent Overstreet stats->bytes_unwritten += bytes; 1384cafe5635SKent Overstreet } 1385cafe5635SKent Overstreet } 1386cafe5635SKent Overstreet } 1387