• Home
  • Raw
  • Download

Lines Matching refs:b

21 void bch_dump_bset(struct btree_keys *b, struct bset *i, unsigned set)  in bch_dump_bset()  argument
31 if (b->ops->key_dump) in bch_dump_bset()
32 b->ops->key_dump(b, k); in bch_dump_bset()
37 bkey_cmp(k, b->ops->is_extents ? in bch_dump_bset()
43 void bch_dump_bucket(struct btree_keys *b) in bch_dump_bucket() argument
48 for (i = 0; i <= b->nsets; i++) in bch_dump_bucket()
49 bch_dump_bset(b, b->set[i].data, in bch_dump_bucket()
50 bset_sector_offset(b, b->set[i].data)); in bch_dump_bucket()
54 int __bch_count_data(struct btree_keys *b) in __bch_count_data() argument
60 if (b->ops->is_extents) in __bch_count_data()
61 for_each_key(b, k, &iter) in __bch_count_data()
66 void __bch_check_keys(struct btree_keys *b, const char *fmt, ...) in __bch_check_keys() argument
73 for_each_key(b, k, &iter) { in __bch_check_keys()
74 if (b->ops->is_extents) { in __bch_check_keys()
79 if (bch_ptr_invalid(b, k)) in __bch_check_keys()
86 if (bch_ptr_bad(b, k)) in __bch_check_keys()
97 if (p && bkey_cmp(p, &b->key) > 0) in __bch_check_keys()
102 bch_dump_bucket(b); in __bch_check_keys()
116 bkey_cmp(k, iter->b->ops->is_extents ? in bch_btree_iter_next_check()
118 bch_dump_bucket(iter->b); in bch_btree_iter_next_check()
266 static inline size_t btree_keys_bytes(struct btree_keys *b) in btree_keys_bytes() argument
268 return PAGE_SIZE << b->page_order; in btree_keys_bytes()
271 static inline size_t btree_keys_cachelines(struct btree_keys *b) in btree_keys_cachelines() argument
273 return btree_keys_bytes(b) / BSET_CACHELINE; in btree_keys_cachelines()
277 static inline size_t bset_tree_bytes(struct btree_keys *b) in bset_tree_bytes() argument
279 return btree_keys_cachelines(b) * sizeof(struct bkey_float); in bset_tree_bytes()
283 static inline size_t bset_prev_bytes(struct btree_keys *b) in bset_prev_bytes() argument
285 return btree_keys_cachelines(b) * sizeof(uint8_t); in bset_prev_bytes()
290 void bch_btree_keys_free(struct btree_keys *b) in bch_btree_keys_free() argument
292 struct bset_tree *t = b->set; in bch_btree_keys_free()
294 if (bset_prev_bytes(b) < PAGE_SIZE) in bch_btree_keys_free()
298 get_order(bset_prev_bytes(b))); in bch_btree_keys_free()
300 if (bset_tree_bytes(b) < PAGE_SIZE) in bch_btree_keys_free()
304 get_order(bset_tree_bytes(b))); in bch_btree_keys_free()
306 free_pages((unsigned long) t->data, b->page_order); in bch_btree_keys_free()
314 int bch_btree_keys_alloc(struct btree_keys *b, unsigned page_order, gfp_t gfp) in bch_btree_keys_alloc() argument
316 struct bset_tree *t = b->set; in bch_btree_keys_alloc()
320 b->page_order = page_order; in bch_btree_keys_alloc()
322 t->data = (void *) __get_free_pages(gfp, b->page_order); in bch_btree_keys_alloc()
326 t->tree = bset_tree_bytes(b) < PAGE_SIZE in bch_btree_keys_alloc()
327 ? kmalloc(bset_tree_bytes(b), gfp) in bch_btree_keys_alloc()
328 : (void *) __get_free_pages(gfp, get_order(bset_tree_bytes(b))); in bch_btree_keys_alloc()
332 t->prev = bset_prev_bytes(b) < PAGE_SIZE in bch_btree_keys_alloc()
333 ? kmalloc(bset_prev_bytes(b), gfp) in bch_btree_keys_alloc()
334 : (void *) __get_free_pages(gfp, get_order(bset_prev_bytes(b))); in bch_btree_keys_alloc()
340 bch_btree_keys_free(b); in bch_btree_keys_alloc()
345 void bch_btree_keys_init(struct btree_keys *b, const struct btree_keys_ops *ops, in bch_btree_keys_init() argument
350 b->ops = ops; in bch_btree_keys_init()
351 b->expensive_debug_checks = expensive_debug_checks; in bch_btree_keys_init()
352 b->nsets = 0; in bch_btree_keys_init()
353 b->last_set_unwritten = 0; in bch_btree_keys_init()
357 b->set[i].size = 0; in bch_btree_keys_init()
363 b->set[i].data = NULL; in bch_btree_keys_init()
410 unsigned b = fls(j); in __to_inorder() local
411 unsigned shift = fls(size - 1) - b; in __to_inorder()
413 j ^= 1U << (b - 1); in __to_inorder()
591 static void bset_alloc_tree(struct btree_keys *b, struct bset_tree *t) in bset_alloc_tree() argument
593 if (t != b->set) { in bset_alloc_tree()
601 while (t < b->set + MAX_BSETS) in bset_alloc_tree()
605 static void bch_bset_build_unwritten_tree(struct btree_keys *b) in bch_bset_build_unwritten_tree() argument
607 struct bset_tree *t = bset_tree_last(b); in bch_bset_build_unwritten_tree()
609 BUG_ON(b->last_set_unwritten); in bch_bset_build_unwritten_tree()
610 b->last_set_unwritten = 1; in bch_bset_build_unwritten_tree()
612 bset_alloc_tree(b, t); in bch_bset_build_unwritten_tree()
614 if (t->tree != b->set->tree + btree_keys_cachelines(b)) { in bch_bset_build_unwritten_tree()
620 void bch_bset_init_next(struct btree_keys *b, struct bset *i, uint64_t magic) in bch_bset_init_next() argument
622 if (i != b->set->data) { in bch_bset_init_next()
623 b->set[++b->nsets].data = i; in bch_bset_init_next()
624 i->seq = b->set->data->seq; in bch_bset_init_next()
632 bch_bset_build_unwritten_tree(b); in bch_bset_init_next()
636 void bch_bset_build_written_tree(struct btree_keys *b) in bch_bset_build_written_tree() argument
638 struct bset_tree *t = bset_tree_last(b); in bch_bset_build_written_tree()
642 b->last_set_unwritten = 0; in bch_bset_build_written_tree()
644 bset_alloc_tree(b, t); in bch_bset_build_written_tree()
648 b->set->tree + btree_keys_cachelines(b) - t->tree); in bch_bset_build_written_tree()
683 void bch_bset_fix_invalidated_key(struct btree_keys *b, struct bkey *k) in bch_bset_fix_invalidated_key() argument
688 for (t = b->set; t <= bset_tree_last(b); t++) in bch_bset_fix_invalidated_key()
694 if (!t->size || !bset_written(b, t)) in bch_bset_fix_invalidated_key()
729 static void bch_bset_fix_lookup_table(struct btree_keys *b, in bch_bset_fix_lookup_table() argument
764 if (t->size == b->set->tree + btree_keys_cachelines(b) - t->tree) in bch_bset_fix_lookup_table()
783 bool bch_bkey_try_merge(struct btree_keys *b, struct bkey *l, struct bkey *r) in bch_bkey_try_merge() argument
785 if (!b->ops->key_merge) in bch_bkey_try_merge()
797 return b->ops->key_merge(b, l, r); in bch_bkey_try_merge()
801 void bch_bset_insert(struct btree_keys *b, struct bkey *where, in bch_bset_insert() argument
804 struct bset_tree *t = bset_tree_last(b); in bch_bset_insert()
806 BUG_ON(!b->last_set_unwritten); in bch_bset_insert()
807 BUG_ON(bset_byte_offset(b, t->data) + in bch_bset_insert()
809 PAGE_SIZE << b->page_order); in bch_bset_insert()
817 bch_bset_fix_lookup_table(b, t, where); in bch_bset_insert()
821 unsigned bch_btree_insert_key(struct btree_keys *b, struct bkey *k, in bch_btree_insert_key() argument
825 struct bset *i = bset_tree_last(b)->data; in bch_btree_insert_key()
831 BUG_ON(b->ops->is_extents && !KEY_SIZE(k)); in bch_btree_insert_key()
838 if (b->ops->is_extents) in bch_btree_insert_key()
843 m = bch_btree_iter_init(b, &iter, preceding_key_p); in bch_btree_insert_key()
845 if (b->ops->insert_fixup(b, k, &iter, replace_key)) in bch_btree_insert_key()
851 bkey_cmp(k, b->ops->is_extents ? &START_KEY(m) : m) > 0) in bch_btree_insert_key()
857 bch_bkey_try_merge(b, prev, k)) in bch_btree_insert_key()
867 bch_bkey_try_merge(b, k, m)) in bch_btree_insert_key()
870 bch_bset_insert(b, m, k); in bch_btree_insert_key()
964 struct bkey *__bch_bset_search(struct btree_keys *b, struct bset_tree *t, in __bch_bset_search() argument
987 } else if (bset_written(b, t)) { in __bch_bset_search()
1003 BUG_ON(!b->nsets && in __bch_bset_search()
1009 if (btree_keys_expensive_checks(b)) { in __bch_bset_search()
1010 BUG_ON(bset_written(b, t) && in __bch_bset_search()
1053 static struct bkey *__bch_btree_iter_init(struct btree_keys *b, in __bch_btree_iter_init() argument
1063 iter->b = b; in __bch_btree_iter_init()
1066 for (; start <= bset_tree_last(b); start++) { in __bch_btree_iter_init()
1067 ret = bch_bset_search(b, start, search); in __bch_btree_iter_init()
1074 struct bkey *bch_btree_iter_init(struct btree_keys *b, in bch_btree_iter_init() argument
1078 return __bch_btree_iter_init(b, iter, search, b->set); in bch_btree_iter_init()
1116 struct btree_keys *b, ptr_filter_fn fn) in bch_btree_iter_next_filter() argument
1122 } while (ret && fn(b, ret)); in bch_btree_iter_next_filter()
1150 static void btree_mergesort(struct btree_keys *b, struct bset *out, in btree_mergesort() argument
1163 heap_sift(iter, i, b->ops->sort_cmp); in btree_mergesort()
1166 if (b->ops->sort_fixup && fixup) in btree_mergesort()
1167 k = b->ops->sort_fixup(iter, &tmp.k); in btree_mergesort()
1172 k = __bch_btree_iter_next(iter, b->ops->sort_cmp); in btree_mergesort()
1174 if (bad(b, k)) in btree_mergesort()
1180 } else if (!bch_bkey_try_merge(b, last, k)) { in btree_mergesort()
1191 static void __btree_sort(struct btree_keys *b, struct btree_iter *iter, in __btree_sort() argument
1212 btree_mergesort(b, out, iter, fixup, false); in __btree_sort()
1213 b->nsets = start; in __btree_sort()
1215 if (!start && order == b->page_order) { in __btree_sort()
1222 out->magic = b->set->data->magic; in __btree_sort()
1223 out->seq = b->set->data->seq; in __btree_sort()
1224 out->version = b->set->data->version; in __btree_sort()
1225 swap(out, b->set->data); in __btree_sort()
1227 b->set[start].data->keys = out->keys; in __btree_sort()
1228 memcpy(b->set[start].data->start, out->start, in __btree_sort()
1237 bch_bset_build_written_tree(b); in __btree_sort()
1243 void bch_btree_sort_partial(struct btree_keys *b, unsigned start, in bch_btree_sort_partial() argument
1246 size_t order = b->page_order, keys = 0; in bch_btree_sort_partial()
1248 int oldsize = bch_count_data(b); in bch_btree_sort_partial()
1250 __bch_btree_iter_init(b, &iter, NULL, &b->set[start]); in bch_btree_sort_partial()
1255 for (i = start; i <= b->nsets; i++) in bch_btree_sort_partial()
1256 keys += b->set[i].data->keys; in bch_btree_sort_partial()
1258 order = get_order(__set_bytes(b->set->data, keys)); in bch_btree_sort_partial()
1261 __btree_sort(b, &iter, start, order, false, state); in bch_btree_sort_partial()
1263 EBUG_ON(oldsize >= 0 && bch_count_data(b) != oldsize); in bch_btree_sort_partial()
1267 void bch_btree_sort_and_fix_extents(struct btree_keys *b, in bch_btree_sort_and_fix_extents() argument
1271 __btree_sort(b, iter, 0, b->page_order, true, state); in bch_btree_sort_and_fix_extents()
1274 void bch_btree_sort_into(struct btree_keys *b, struct btree_keys *new, in bch_btree_sort_into() argument
1280 bch_btree_iter_init(b, &iter, NULL); in bch_btree_sort_into()
1282 btree_mergesort(b, new->set->data, &iter, false, true); in bch_btree_sort_into()
1291 void bch_btree_sort_lazy(struct btree_keys *b, struct bset_sort_state *state) in bch_btree_sort_lazy() argument
1297 if (!b->nsets) in bch_btree_sort_lazy()
1300 for (i = b->nsets - 1; i >= 0; --i) { in bch_btree_sort_lazy()
1303 if (b->set[i].data->keys < crit) { in bch_btree_sort_lazy()
1304 bch_btree_sort_partial(b, i, state); in bch_btree_sort_lazy()
1310 if (b->nsets + 1 == MAX_BSETS) { in bch_btree_sort_lazy()
1311 bch_btree_sort(b, state); in bch_btree_sort_lazy()
1316 bch_bset_build_written_tree(b); in bch_btree_sort_lazy()
1320 void bch_btree_keys_stats(struct btree_keys *b, struct bset_stats *stats) in bch_btree_keys_stats() argument
1324 for (i = 0; i <= b->nsets; i++) { in bch_btree_keys_stats()
1325 struct bset_tree *t = &b->set[i]; in bch_btree_keys_stats()
1329 if (bset_written(b, t)) { in bch_btree_keys_stats()