Lines Matching refs:t
290 struct bset_tree *t = b->set; in bch_btree_keys_free() local
293 kfree(t->prev); in bch_btree_keys_free()
295 free_pages((unsigned long) t->prev, in bch_btree_keys_free()
299 kfree(t->tree); in bch_btree_keys_free()
301 free_pages((unsigned long) t->tree, in bch_btree_keys_free()
304 free_pages((unsigned long) t->data, b->page_order); in bch_btree_keys_free()
306 t->prev = NULL; in bch_btree_keys_free()
307 t->tree = NULL; in bch_btree_keys_free()
308 t->data = NULL; in bch_btree_keys_free()
314 struct bset_tree *t = b->set; in bch_btree_keys_alloc() local
316 BUG_ON(t->data); in bch_btree_keys_alloc()
320 t->data = (void *) __get_free_pages(gfp, b->page_order); in bch_btree_keys_alloc()
321 if (!t->data) in bch_btree_keys_alloc()
324 t->tree = bset_tree_bytes(b) < PAGE_SIZE in bch_btree_keys_alloc()
327 if (!t->tree) in bch_btree_keys_alloc()
330 t->prev = bset_prev_bytes(b) < PAGE_SIZE in bch_btree_keys_alloc()
333 if (!t->prev) in bch_btree_keys_alloc()
422 static unsigned to_inorder(unsigned j, struct bset_tree *t) in to_inorder() argument
424 return __to_inorder(j, t->size, t->extra); in to_inorder()
442 static unsigned inorder_to_tree(unsigned j, struct bset_tree *t) in inorder_to_tree() argument
444 return __inorder_to_tree(j, t->size, t->extra); in inorder_to_tree()
503 static struct bkey *cacheline_to_bkey(struct bset_tree *t, unsigned cacheline, in cacheline_to_bkey() argument
506 return ((void *) t->data) + cacheline * BSET_CACHELINE + offset * 8; in cacheline_to_bkey()
509 static unsigned bkey_to_cacheline(struct bset_tree *t, struct bkey *k) in bkey_to_cacheline() argument
511 return ((void *) k - (void *) t->data) / BSET_CACHELINE; in bkey_to_cacheline()
514 static unsigned bkey_to_cacheline_offset(struct bset_tree *t, in bkey_to_cacheline_offset() argument
518 return (u64 *) k - (u64 *) cacheline_to_bkey(t, cacheline, 0); in bkey_to_cacheline_offset()
521 static struct bkey *tree_to_bkey(struct bset_tree *t, unsigned j) in tree_to_bkey() argument
523 return cacheline_to_bkey(t, to_inorder(j, t), t->tree[j].m); in tree_to_bkey()
526 static struct bkey *tree_to_prev_bkey(struct bset_tree *t, unsigned j) in tree_to_prev_bkey() argument
528 return (void *) (((uint64_t *) tree_to_bkey(t, j)) - t->prev[j]); in tree_to_prev_bkey()
535 static struct bkey *table_to_bkey(struct bset_tree *t, unsigned cacheline) in table_to_bkey() argument
537 return cacheline_to_bkey(t, cacheline, t->prev[cacheline]); in table_to_bkey()
554 static void make_bfloat(struct bset_tree *t, unsigned j) in make_bfloat() argument
556 struct bkey_float *f = &t->tree[j]; in make_bfloat()
557 struct bkey *m = tree_to_bkey(t, j); in make_bfloat()
558 struct bkey *p = tree_to_prev_bkey(t, j); in make_bfloat()
561 ? t->data->start in make_bfloat()
562 : tree_to_prev_bkey(t, j >> ffs(j)); in make_bfloat()
565 ? bset_bkey_idx(t->data, t->data->keys - bkey_u64s(&t->end)) in make_bfloat()
566 : tree_to_bkey(t, j >> (ffz(j) + 1)); in make_bfloat()
589 static void bset_alloc_tree(struct btree_keys *b, struct bset_tree *t) in bset_alloc_tree() argument
591 if (t != b->set) { in bset_alloc_tree()
592 unsigned j = roundup(t[-1].size, in bset_alloc_tree()
595 t->tree = t[-1].tree + j; in bset_alloc_tree()
596 t->prev = t[-1].prev + j; in bset_alloc_tree()
599 while (t < b->set + MAX_BSETS) in bset_alloc_tree()
600 t++->size = 0; in bset_alloc_tree()
605 struct bset_tree *t = bset_tree_last(b); in bch_bset_build_unwritten_tree() local
610 bset_alloc_tree(b, t); in bch_bset_build_unwritten_tree()
612 if (t->tree != b->set->tree + btree_keys_cachelines(b)) { in bch_bset_build_unwritten_tree()
613 t->prev[0] = bkey_to_cacheline_offset(t, 0, t->data->start); in bch_bset_build_unwritten_tree()
614 t->size = 1; in bch_bset_build_unwritten_tree()
636 struct bset_tree *t = bset_tree_last(b); in bch_bset_build_written_tree() local
637 struct bkey *prev = NULL, *k = t->data->start; in bch_bset_build_written_tree()
642 bset_alloc_tree(b, t); in bch_bset_build_written_tree()
644 t->size = min_t(unsigned, in bch_bset_build_written_tree()
645 bkey_to_cacheline(t, bset_bkey_last(t->data)), in bch_bset_build_written_tree()
646 b->set->tree + btree_keys_cachelines(b) - t->tree); in bch_bset_build_written_tree()
648 if (t->size < 2) { in bch_bset_build_written_tree()
649 t->size = 0; in bch_bset_build_written_tree()
653 t->extra = (t->size - rounddown_pow_of_two(t->size - 1)) << 1; in bch_bset_build_written_tree()
656 for (j = inorder_next(0, t->size); in bch_bset_build_written_tree()
658 j = inorder_next(j, t->size)) { in bch_bset_build_written_tree()
659 while (bkey_to_cacheline(t, k) < cacheline) in bch_bset_build_written_tree()
662 t->prev[j] = bkey_u64s(prev); in bch_bset_build_written_tree()
663 t->tree[j].m = bkey_to_cacheline_offset(t, cacheline++, k); in bch_bset_build_written_tree()
666 while (bkey_next(k) != bset_bkey_last(t->data)) in bch_bset_build_written_tree()
669 t->end = *k; in bch_bset_build_written_tree()
672 for (j = inorder_next(0, t->size); in bch_bset_build_written_tree()
674 j = inorder_next(j, t->size)) in bch_bset_build_written_tree()
675 make_bfloat(t, j); in bch_bset_build_written_tree()
683 struct bset_tree *t; in bch_bset_fix_invalidated_key() local
686 for (t = b->set; t <= bset_tree_last(b); t++) in bch_bset_fix_invalidated_key()
687 if (k < bset_bkey_last(t->data)) in bch_bset_fix_invalidated_key()
692 if (!t->size || !bset_written(b, t)) in bch_bset_fix_invalidated_key()
695 inorder = bkey_to_cacheline(t, k); in bch_bset_fix_invalidated_key()
697 if (k == t->data->start) in bch_bset_fix_invalidated_key()
700 if (bkey_next(k) == bset_bkey_last(t->data)) { in bch_bset_fix_invalidated_key()
701 t->end = *k; in bch_bset_fix_invalidated_key()
705 j = inorder_to_tree(inorder, t); in bch_bset_fix_invalidated_key()
708 j < t->size && in bch_bset_fix_invalidated_key()
709 k == tree_to_bkey(t, j)) in bch_bset_fix_invalidated_key()
711 make_bfloat(t, j); in bch_bset_fix_invalidated_key()
713 } while (j < t->size); in bch_bset_fix_invalidated_key()
715 j = inorder_to_tree(inorder + 1, t); in bch_bset_fix_invalidated_key()
718 j < t->size && in bch_bset_fix_invalidated_key()
719 k == tree_to_prev_bkey(t, j)) in bch_bset_fix_invalidated_key()
721 make_bfloat(t, j); in bch_bset_fix_invalidated_key()
723 } while (j < t->size); in bch_bset_fix_invalidated_key()
728 struct bset_tree *t, in bch_bset_fix_lookup_table() argument
732 unsigned j = bkey_to_cacheline(t, k); in bch_bset_fix_lookup_table()
735 if (!t->size) in bch_bset_fix_lookup_table()
742 while (j < t->size && in bch_bset_fix_lookup_table()
743 table_to_bkey(t, j) <= k) in bch_bset_fix_lookup_table()
749 for (; j < t->size; j++) { in bch_bset_fix_lookup_table()
750 t->prev[j] += shift; in bch_bset_fix_lookup_table()
752 if (t->prev[j] > 7) { in bch_bset_fix_lookup_table()
753 k = table_to_bkey(t, j - 1); in bch_bset_fix_lookup_table()
755 while (k < cacheline_to_bkey(t, j, 0)) in bch_bset_fix_lookup_table()
758 t->prev[j] = bkey_to_cacheline_offset(t, j, k); in bch_bset_fix_lookup_table()
762 if (t->size == b->set->tree + btree_keys_cachelines(b) - t->tree) in bch_bset_fix_lookup_table()
767 for (k = table_to_bkey(t, t->size - 1); in bch_bset_fix_lookup_table()
768 k != bset_bkey_last(t->data); in bch_bset_fix_lookup_table()
770 if (t->size == bkey_to_cacheline(t, k)) { in bch_bset_fix_lookup_table()
771 t->prev[t->size] = bkey_to_cacheline_offset(t, t->size, k); in bch_bset_fix_lookup_table()
772 t->size++; in bch_bset_fix_lookup_table()
802 struct bset_tree *t = bset_tree_last(b); in bch_bset_insert() local
805 BUG_ON(bset_byte_offset(b, t->data) + in bch_bset_insert()
806 __set_bytes(t->data, t->data->keys + bkey_u64s(insert)) > in bch_bset_insert()
811 (void *) bset_bkey_last(t->data) - (void *) where); in bch_bset_insert()
813 t->data->keys += bkey_u64s(insert); in bch_bset_insert()
815 bch_bset_fix_lookup_table(b, t, where); in bch_bset_insert()
871 static struct bset_search_iter bset_search_write_set(struct bset_tree *t, in bset_search_write_set() argument
874 unsigned li = 0, ri = t->size; in bset_search_write_set()
879 if (bkey_cmp(table_to_bkey(t, m), search) > 0) in bset_search_write_set()
886 table_to_bkey(t, li), in bset_search_write_set()
887 ri < t->size ? table_to_bkey(t, ri) : bset_bkey_last(t->data) in bset_search_write_set()
891 static struct bset_search_iter bset_search_tree(struct bset_tree *t, in bset_search_tree() argument
900 p &= ((int) (p - t->size)) >> 31; in bset_search_tree()
902 prefetch(&t->tree[p]); in bset_search_tree()
905 f = &t->tree[j]; in bset_search_tree()
920 n = (bkey_cmp(tree_to_bkey(t, j), search) > 0) in bset_search_tree()
923 } while (n < t->size); in bset_search_tree()
925 inorder = to_inorder(j, t); in bset_search_tree()
932 l = cacheline_to_bkey(t, inorder, f->m); in bset_search_tree()
934 if (++inorder != t->size) { in bset_search_tree()
935 f = &t->tree[inorder_next(j, t->size)]; in bset_search_tree()
936 r = cacheline_to_bkey(t, inorder, f->m); in bset_search_tree()
938 r = bset_bkey_last(t->data); in bset_search_tree()
940 r = cacheline_to_bkey(t, inorder, f->m); in bset_search_tree()
943 f = &t->tree[inorder_prev(j, t->size)]; in bset_search_tree()
944 l = cacheline_to_bkey(t, inorder, f->m); in bset_search_tree()
946 l = t->data->start; in bset_search_tree()
952 struct bkey *__bch_bset_search(struct btree_keys *b, struct bset_tree *t, in __bch_bset_search() argument
972 if (unlikely(!t->size)) { in __bch_bset_search()
973 i.l = t->data->start; in __bch_bset_search()
974 i.r = bset_bkey_last(t->data); in __bch_bset_search()
975 } else if (bset_written(b, t)) { in __bch_bset_search()
983 if (unlikely(bkey_cmp(search, &t->end) >= 0)) in __bch_bset_search()
984 return bset_bkey_last(t->data); in __bch_bset_search()
986 if (unlikely(bkey_cmp(search, t->data->start) < 0)) in __bch_bset_search()
987 return t->data->start; in __bch_bset_search()
989 i = bset_search_tree(t, search); in __bch_bset_search()
992 t->size < bkey_to_cacheline(t, bset_bkey_last(t->data))); in __bch_bset_search()
994 i = bset_search_write_set(t, search); in __bch_bset_search()
998 BUG_ON(bset_written(b, t) && in __bch_bset_search()
999 i.l != t->data->start && in __bch_bset_search()
1000 bkey_cmp(tree_to_prev_bkey(t, in __bch_bset_search()
1001 inorder_to_tree(bkey_to_cacheline(t, i.l), t)), in __bch_bset_search()
1004 BUG_ON(i.r != bset_bkey_last(t->data) && in __bch_bset_search()
1313 struct bset_tree *t = &b->set[i]; in bch_btree_keys_stats() local
1314 size_t bytes = t->data->keys * sizeof(uint64_t); in bch_btree_keys_stats()
1317 if (bset_written(b, t)) { in bch_btree_keys_stats()
1321 stats->floats += t->size - 1; in bch_btree_keys_stats()
1323 for (j = 1; j < t->size; j++) in bch_btree_keys_stats()
1324 if (t->tree[j].exponent == 127) in bch_btree_keys_stats()