1 // SPDX-License-Identifier: GPL-2.0
27 	bch2_btree_id_level_to_text(out, n->btree_id, n->level);  in found_btree_node_to_text()
29 		   n->seq, n->journal_seq, n->cookie);  in found_btree_node_to_text()
30 	bch2_bpos_to_text(out, n->min_key);  in found_btree_node_to_text()
31 	prt_str(out, "-");  in found_btree_node_to_text()
32 	bch2_bpos_to_text(out, n->max_key);  in found_btree_node_to_text()
34 	if (n->range_updated)  in found_btree_node_to_text()
37 	for (unsigned i = 0; i < n->nr_ptrs; i++) {  in found_btree_node_to_text()
39 		bch2_extent_ptr_to_text(out, c, n->ptrs + i);  in found_btree_node_to_text()
57 	set_bkey_val_u64s(&bp->k, sizeof(struct bch_btree_ptr_v2) / sizeof(u64) + f->nr_ptrs);  in found_btree_node_to_key()
58 	bp->k.p			= f->max_key;  in found_btree_node_to_key()
59 	bp->v.seq		= cpu_to_le64(f->cookie);  in found_btree_node_to_key()
60 	bp->v.sectors_written	= 0;  in found_btree_node_to_key()
61 	bp->v.flags		= 0;  in found_btree_node_to_key()
62 	bp->v.sectors_written	= cpu_to_le16(f->sectors_written);  in found_btree_node_to_key()
63 	bp->v.min_key		= f->min_key;  in found_btree_node_to_key()
64 	SET_BTREE_PTR_RANGE_UPDATED(&bp->v, f->range_updated);  in found_btree_node_to_key()
65 	memcpy(bp->v.start, f->ptrs, sizeof(struct bch_extent_ptr) * f->nr_ptrs);  in found_btree_node_to_key()
70 	switch (k.k->type) {  in bkey_journal_seq()
72 		return le64_to_cpu(bkey_s_c_to_inode_v3(k).v->bi_journal_seq);  in bkey_journal_seq()
85 	struct btree *b = bch2_btree_node_get_noiter(trans, &tmp.k, f->btree_id, f->level, false);  in found_btree_node_is_readable()
90 	f->sectors_written = b->written;  in found_btree_node_is_readable()
91 	f->journal_seq = le64_to_cpu(b->data->keys.journal_seq);  in found_btree_node_is_readable()
97 		f->journal_seq = max(f->journal_seq, bkey_journal_seq(k));  in found_btree_node_is_readable()
99 	six_unlock_read(&b->c.lock);  in found_btree_node_is_readable()
103 	 * to be re-read so the read path can trim keys that are no longer in  in found_btree_node_is_readable()
106 	if (b != btree_node_root(trans->c, b))  in found_btree_node_is_readable()
116 	return  cmp_int(l->btree_id,	r->btree_id) ?:  in found_btree_node_cmp_cookie()
117 		cmp_int(l->level,	r->level) ?:  in found_btree_node_cmp_cookie()
118 		cmp_int(l->cookie,	r->cookie);  in found_btree_node_cmp_cookie()
128 	return  cmp_int(l->seq, r->seq) ?:  in found_btree_node_cmp_time()
129 		cmp_int(l->journal_seq, r->journal_seq);  in found_btree_node_cmp_time()
137 	return  cmp_int(l->btree_id,	r->btree_id) ?:  in found_btree_node_cmp_pos()
138 	       -cmp_int(l->level,	r->level) ?:  in found_btree_node_cmp_pos()
139 		bpos_cmp(l->min_key,	r->min_key) ?:  in found_btree_node_cmp_pos()
140 	       -found_btree_node_cmp_time(l, r);  in found_btree_node_cmp_pos()
166 	bio_reset(bio, ca->disk_sb.bdev, REQ_OP_READ);  in try_read_btree_node()
167 	bio->bi_iter.bi_sector	= offset;  in try_read_btree_node()
173 	bch2_account_io_completion(ca, BCH_MEMBER_ERROR_read, submit_time, !bio->bi_status);  in try_read_btree_node()
175 	if (bio->bi_status) {  in try_read_btree_node()
178 				offset, bch2_blk_status_to_str(bio->bi_status));  in try_read_btree_node()
182 	if (le64_to_cpu(bn->magic) != bset_magic(c))  in try_read_btree_node()
185 	if (bch2_csum_type_is_encryption(BSET_CSUM_TYPE(&bn->keys))) {  in try_read_btree_node()
186 		if (!c->chacha20_key_set)  in try_read_btree_node()
189 		struct nonce nonce = btree_nonce(&bn->keys, 0);  in try_read_btree_node()
190 		unsigned bytes = (void *) &bn->keys - (void *) &bn->flags;  in try_read_btree_node()
192 		bch2_encrypt(c, BSET_CSUM_TYPE(&bn->keys), nonce, &bn->flags, bytes);  in try_read_btree_node()
209 		.cookie		= le64_to_cpu(bn->keys.seq),  in try_read_btree_node()
210 		.min_key	= bn->min_key,  in try_read_btree_node()
211 		.max_key	= bn->max_key,  in try_read_btree_node()
215 		.ptrs[0].dev	= ca->dev_idx,  in try_read_btree_node()
221 		mutex_lock(&f->lock);  in try_read_btree_node()
222 		if (BSET_BIG_ENDIAN(&bn->keys) != CPU_BIG_ENDIAN) {  in try_read_btree_node()
224 			f->ret = -EINVAL;  in try_read_btree_node()
228 		if (darray_push(&f->nodes, n))  in try_read_btree_node()
229 			f->ret = -ENOMEM;  in try_read_btree_node()
231 		mutex_unlock(&f->lock);  in try_read_btree_node()
238 	struct bch_fs *c = container_of(w->f, struct bch_fs, found_btree_nodes);  in read_btree_nodes_worker()
239 	struct bch_dev *ca = w->ca;  in read_btree_nodes_worker()
246 		w->f->ret = -ENOMEM;  in read_btree_nodes_worker()
250 	for (u64 bucket = ca->mi.first_bucket; bucket < ca->mi.nbuckets; bucket++)  in read_btree_nodes_worker()
252 		     bucket_offset + btree_sectors(c) <= ca->mi.bucket_size;  in read_btree_nodes_worker()
255 				u64 cur_sector = bucket * ca->mi.bucket_size + bucket_offset;  in read_btree_nodes_worker()
256 				u64 end_sector = ca->mi.nbuckets * ca->mi.bucket_size;  in read_btree_nodes_worker()
263 			u64 sector = bucket * ca->mi.bucket_size + bucket_offset;  in read_btree_nodes_worker()
265 			if (c->sb.version_upgrade_complete >= bcachefs_metadata_version_mi_btree_bitmap &&  in read_btree_nodes_worker()
269 			try_read_btree_node(w->f, ca, bio, buf, sector);  in read_btree_nodes_worker()
274 	percpu_ref_put(&ca->io_ref[READ]);  in read_btree_nodes_worker()
275 	closure_put(w->cl);  in read_btree_nodes_worker()
289 		if (!(ca->mi.data_allowed & BIT(BCH_DATA_btree)))  in read_btree_nodes()
294 			percpu_ref_put(&ca->io_ref[READ]);  in read_btree_nodes()
295 			ret = -ENOMEM;  in read_btree_nodes()
299 		w->cl		= &cl;  in read_btree_nodes()
300 		w->f		= f;  in read_btree_nodes()
301 		w->ca		= ca;  in read_btree_nodes()
303 …struct task_struct *t = kthread_create(read_btree_nodes_worker, w, "read_btree_nodes/%s", ca->name…  in read_btree_nodes()
306 			percpu_ref_put(&ca->io_ref[READ]);  in read_btree_nodes()
313 		percpu_ref_get(&ca->io_ref[READ]);  in read_btree_nodes()
319 	return f->ret ?: ret;  in read_btree_nodes()
325 	return (l->btree_id	== r->btree_id &&  in nodes_overlap()
326 		l->level	== r->level &&  in nodes_overlap()
327 		bpos_gt(l->max_key, r->min_key));  in nodes_overlap()
341 			if (bpos_cmp(l->max_key, r->max_key) >= 0)  in handle_overwrites()
344 				r->range_updated = true;  in handle_overwrites()
345 				r->min_key = bpos_successor(l->max_key);  in handle_overwrites()
346 				r->range_updated = true;  in handle_overwrites()
350 			BUG_ON(bpos_eq(l->min_key, r->min_key));  in handle_overwrites()
352 			l->max_key = bpos_predecessor(r->min_key);  in handle_overwrites()
353 			l->range_updated = true;  in handle_overwrites()
354 		} else if (r->level) {  in handle_overwrites()
357 			if (bpos_cmp(l->max_key, r->max_key) >= 0)  in handle_overwrites()
360 				r->range_updated = true;  in handle_overwrites()
361 				r->min_key = bpos_successor(l->max_key);  in handle_overwrites()
362 				r->range_updated = true;  in handle_overwrites()
373 	struct find_btree_nodes *f = &c->found_btree_nodes;  in bch2_scan_for_btree_nodes()
379 	if (f->nodes.nr)  in bch2_scan_for_btree_nodes()
382 	mutex_init(&f->lock);  in bch2_scan_for_btree_nodes()
388 	if (!f->nodes.nr) {  in bch2_scan_for_btree_nodes()
390 		ret = -EINVAL;  in bch2_scan_for_btree_nodes()
394 	if (0 && c->opts.verbose) {  in bch2_scan_for_btree_nodes()
397 		found_btree_nodes_to_text(&buf, c, f->nodes);  in bch2_scan_for_btree_nodes()
401 …sort_nonatomic(f->nodes.data, f->nodes.nr, sizeof(f->nodes.data[0]), found_btree_node_cmp_cookie, …  in bch2_scan_for_btree_nodes()
404 	darray_for_each(f->nodes, i) {  in bch2_scan_for_btree_nodes()
405 		struct found_btree_node *prev = dst ? f->nodes.data + dst - 1 : NULL;  in bch2_scan_for_btree_nodes()
408 		    prev->cookie == i->cookie) {  in bch2_scan_for_btree_nodes()
409 			if (prev->nr_ptrs == ARRAY_SIZE(prev->ptrs)) {  in bch2_scan_for_btree_nodes()
411 				ret = -EINVAL;  in bch2_scan_for_btree_nodes()
414 			prev->ptrs[prev->nr_ptrs++] = i->ptrs[0];  in bch2_scan_for_btree_nodes()
416 			f->nodes.data[dst++] = *i;  in bch2_scan_for_btree_nodes()
419 	f->nodes.nr = dst;  in bch2_scan_for_btree_nodes()
421 …sort_nonatomic(f->nodes.data, f->nodes.nr, sizeof(f->nodes.data[0]), found_btree_node_cmp_pos, NUL…  in bch2_scan_for_btree_nodes()
423 	if (0 && c->opts.verbose) {  in bch2_scan_for_btree_nodes()
426 		found_btree_nodes_to_text(&buf, c, f->nodes);  in bch2_scan_for_btree_nodes()
430 	swap(nodes_heap, f->nodes);  in bch2_scan_for_btree_nodes()
444 		ret = darray_push(&f->nodes, *min_heap_peek(&nodes_heap));  in bch2_scan_for_btree_nodes()
452 		ret = handle_overwrites(c, &darray_last(f->nodes), &nodes_heap);  in bch2_scan_for_btree_nodes()
459 		ret = darray_push(&f->nodes, *min_heap_peek(&nodes_heap));  in bch2_scan_for_btree_nodes()
466 	for (struct found_btree_node *n = f->nodes.data; n < &darray_last(f->nodes); n++)  in bch2_scan_for_btree_nodes()
469 	if (0 && c->opts.verbose) {  in bch2_scan_for_btree_nodes()
472 		found_btree_nodes_to_text(&buf, c, f->nodes);  in bch2_scan_for_btree_nodes()
475 		bch_info(c, "btree node scan found %zu nodes after overwrites", f->nodes.nr);  in bch2_scan_for_btree_nodes()
478 …eytzinger0_sort(f->nodes.data, f->nodes.nr, sizeof(f->nodes.data[0]), found_btree_node_cmp_pos, NU…  in bch2_scan_for_btree_nodes()
490 	return  cmp_int(l->btree_id,	r->btree_id) ?:  in found_btree_node_range_start_cmp()
491 	       -cmp_int(l->level,	r->level) ?:  in found_btree_node_range_start_cmp()
492 		bpos_cmp(l->max_key,	r->min_key);  in found_btree_node_range_start_cmp()
496 	for (size_t _idx = eytzinger0_find_gt((_f)->nodes.data, (_f)->nodes.nr,		\
497 					sizeof((_f)->nodes.data[0]),			\
499 	     _idx < (_f)->nodes.nr &&							\
500 	     (_f)->nodes.data[_idx].btree_id == _search.btree_id &&			\
501 	     (_f)->nodes.data[_idx].level == _search.level &&				\
502 	     bpos_lt((_f)->nodes.data[_idx].min_key, _search.max_key);			\
503 	     _idx = eytzinger0_next(_idx, (_f)->nodes.nr))
507 	struct find_btree_nodes *f = &c->found_btree_nodes;  in bch2_btree_node_is_stale()
510 		.btree_id	= b->c.btree_id,  in bch2_btree_node_is_stale()
511 		.level		= b->c.level,  in bch2_btree_node_is_stale()
512 		.min_key	= b->data->min_key,  in bch2_btree_node_is_stale()
513 		.max_key	= b->key.k.p,  in bch2_btree_node_is_stale()
517 		if (f->nodes.data[idx].seq > BTREE_NODE_SEQ(b->data))  in bch2_btree_node_is_stale()
531 	for_each_found_btree_node_in_range(&c->found_btree_nodes, search, idx)  in bch2_btree_has_scanned_nodes()
542 	struct find_btree_nodes *f = &c->found_btree_nodes;  in bch2_get_scanned_nodes()
548 	if (c->opts.verbose) {  in bch2_get_scanned_nodes()
555 		prt_str(&buf, " - ");  in bch2_get_scanned_nodes()
570 		struct found_btree_node n = f->nodes.data[idx];  in bch2_get_scanned_nodes()
582 		if (c->opts.verbose) {  in bch2_get_scanned_nodes()
606 	darray_exit(&f->nodes);  in bch2_find_btree_nodes_exit()