1 // SPDX-License-Identifier: GPL-2.0 2 3 #include "bcachefs.h" 4 #include "btree_cache.h" 5 #include "btree_io.h" 6 #include "btree_journal_iter.h" 7 #include "btree_node_scan.h" 8 #include "btree_update_interior.h" 9 #include "buckets.h" 10 #include "error.h" 11 #include "journal_io.h" 12 #include "recovery_passes.h" 13 14 #include <linux/kthread.h> 15 #include <linux/min_heap.h> 16 #include <linux/sched/sysctl.h> 17 #include <linux/sort.h> 18 19 struct find_btree_nodes_worker { 20 struct closure *cl; 21 struct find_btree_nodes *f; 22 struct bch_dev *ca; 23 }; 24 25 static void found_btree_node_to_text(struct printbuf *out, struct bch_fs *c, const struct found_btree_node *n) 26 { 27 bch2_btree_id_level_to_text(out, n->btree_id, n->level); 28 prt_printf(out, " seq=%u journal_seq=%llu cookie=%llx ", 29 n->seq, n->journal_seq, n->cookie); 30 bch2_bpos_to_text(out, n->min_key); 31 prt_str(out, "-"); 32 bch2_bpos_to_text(out, n->max_key); 33 34 if (n->range_updated) 35 prt_str(out, " range updated"); 36 37 for (unsigned i = 0; i < n->nr_ptrs; i++) { 38 prt_char(out, ' '); 39 bch2_extent_ptr_to_text(out, c, n->ptrs + i); 40 } 41 } 42 43 static void found_btree_nodes_to_text(struct printbuf *out, struct bch_fs *c, found_btree_nodes nodes) 44 { 45 printbuf_indent_add(out, 2); 46 darray_for_each(nodes, i) { 47 found_btree_node_to_text(out, c, i); 48 prt_newline(out); 49 } 50 printbuf_indent_sub(out, 2); 51 } 52 53 static void found_btree_node_to_key(struct bkey_i *k, const struct found_btree_node *f) 54 { 55 struct bkey_i_btree_ptr_v2 *bp = bkey_btree_ptr_v2_init(k); 56 57 set_bkey_val_u64s(&bp->k, sizeof(struct bch_btree_ptr_v2) / sizeof(u64) + f->nr_ptrs); 58 bp->k.p = f->max_key; 59 bp->v.seq = cpu_to_le64(f->cookie); 60 bp->v.sectors_written = 0; 61 bp->v.flags = 0; 62 bp->v.sectors_written = cpu_to_le16(f->sectors_written); 63 bp->v.min_key = f->min_key; 64 SET_BTREE_PTR_RANGE_UPDATED(&bp->v, f->range_updated); 65 memcpy(bp->v.start, f->ptrs, sizeof(struct bch_extent_ptr) * f->nr_ptrs); 66 } 67 68 static inline u64 bkey_journal_seq(struct bkey_s_c k) 69 { 70 switch (k.k->type) { 71 case KEY_TYPE_inode_v3: 72 return le64_to_cpu(bkey_s_c_to_inode_v3(k).v->bi_journal_seq); 73 default: 74 return 0; 75 } 76 } 77 78 static bool found_btree_node_is_readable(struct btree_trans *trans, 79 struct found_btree_node *f) 80 { 81 struct { __BKEY_PADDED(k, BKEY_BTREE_PTR_VAL_U64s_MAX); } tmp; 82 83 found_btree_node_to_key(&tmp.k, f); 84 85 struct btree *b = bch2_btree_node_get_noiter(trans, &tmp.k, f->btree_id, f->level, false); 86 bool ret = !IS_ERR_OR_NULL(b); 87 if (!ret) 88 return ret; 89 90 f->sectors_written = b->written; 91 f->journal_seq = le64_to_cpu(b->data->keys.journal_seq); 92 93 struct bkey_s_c k; 94 struct bkey unpacked; 95 struct btree_node_iter iter; 96 for_each_btree_node_key_unpack(b, k, &iter, &unpacked) 97 f->journal_seq = max(f->journal_seq, bkey_journal_seq(k)); 98 99 six_unlock_read(&b->c.lock); 100 101 /* 102 * We might update this node's range; if that happens, we need the node 103 * to be re-read so the read path can trim keys that are no longer in 104 * this node 105 */ 106 if (b != btree_node_root(trans->c, b)) 107 bch2_btree_node_evict(trans, &tmp.k); 108 return ret; 109 } 110 111 static int found_btree_node_cmp_cookie(const void *_l, const void *_r) 112 { 113 const struct found_btree_node *l = _l; 114 const struct found_btree_node *r = _r; 115 116 return cmp_int(l->btree_id, r->btree_id) ?: 117 cmp_int(l->level, r->level) ?: 118 cmp_int(l->cookie, r->cookie); 119 } 120 121 /* 122 * Given two found btree nodes, if their sequence numbers are equal, take the 123 * one that's readable: 124 */ 125 static int found_btree_node_cmp_time(const struct found_btree_node *l, 126 const struct found_btree_node *r) 127 { 128 return cmp_int(l->seq, r->seq) ?: 129 cmp_int(l->journal_seq, r->journal_seq); 130 } 131 132 static int found_btree_node_cmp_pos(const void *_l, const void *_r) 133 { 134 const struct found_btree_node *l = _l; 135 const struct found_btree_node *r = _r; 136 137 return cmp_int(l->btree_id, r->btree_id) ?: 138 -cmp_int(l->level, r->level) ?: 139 bpos_cmp(l->min_key, r->min_key) ?: 140 -found_btree_node_cmp_time(l, r); 141 } 142 143 static inline bool found_btree_node_cmp_pos_less(const void *l, const void *r, void *arg) 144 { 145 return found_btree_node_cmp_pos(l, r) < 0; 146 } 147 148 static inline void found_btree_node_swap(void *_l, void *_r, void *arg) 149 { 150 struct found_btree_node *l = _l; 151 struct found_btree_node *r = _r; 152 153 swap(*l, *r); 154 } 155 156 static const struct min_heap_callbacks found_btree_node_heap_cbs = { 157 .less = found_btree_node_cmp_pos_less, 158 .swp = found_btree_node_swap, 159 }; 160 161 static void try_read_btree_node(struct find_btree_nodes *f, struct bch_dev *ca, 162 struct bio *bio, struct btree_node *bn, u64 offset) 163 { 164 struct bch_fs *c = container_of(f, struct bch_fs, found_btree_nodes); 165 166 bio_reset(bio, ca->disk_sb.bdev, REQ_OP_READ); 167 bio->bi_iter.bi_sector = offset; 168 bch2_bio_map(bio, bn, PAGE_SIZE); 169 170 u64 submit_time = local_clock(); 171 submit_bio_wait(bio); 172 173 bch2_account_io_completion(ca, BCH_MEMBER_ERROR_read, submit_time, !bio->bi_status); 174 175 if (bio->bi_status) { 176 bch_err_dev_ratelimited(ca, 177 "IO error in try_read_btree_node() at %llu: %s", 178 offset, bch2_blk_status_to_str(bio->bi_status)); 179 return; 180 } 181 182 if (le64_to_cpu(bn->magic) != bset_magic(c)) 183 return; 184 185 if (bch2_csum_type_is_encryption(BSET_CSUM_TYPE(&bn->keys))) { 186 if (!c->chacha20) 187 return; 188 189 struct nonce nonce = btree_nonce(&bn->keys, 0); 190 unsigned bytes = (void *) &bn->keys - (void *) &bn->flags; 191 192 bch2_encrypt(c, BSET_CSUM_TYPE(&bn->keys), nonce, &bn->flags, bytes); 193 } 194 195 if (btree_id_is_alloc(BTREE_NODE_ID(bn))) 196 return; 197 198 if (BTREE_NODE_LEVEL(bn) >= BTREE_MAX_DEPTH) 199 return; 200 201 if (BTREE_NODE_ID(bn) >= BTREE_ID_NR_MAX) 202 return; 203 204 rcu_read_lock(); 205 struct found_btree_node n = { 206 .btree_id = BTREE_NODE_ID(bn), 207 .level = BTREE_NODE_LEVEL(bn), 208 .seq = BTREE_NODE_SEQ(bn), 209 .cookie = le64_to_cpu(bn->keys.seq), 210 .min_key = bn->min_key, 211 .max_key = bn->max_key, 212 .nr_ptrs = 1, 213 .ptrs[0].type = 1 << BCH_EXTENT_ENTRY_ptr, 214 .ptrs[0].offset = offset, 215 .ptrs[0].dev = ca->dev_idx, 216 .ptrs[0].gen = bucket_gen_get(ca, sector_to_bucket(ca, offset)), 217 }; 218 rcu_read_unlock(); 219 220 if (bch2_trans_run(c, found_btree_node_is_readable(trans, &n))) { 221 mutex_lock(&f->lock); 222 if (BSET_BIG_ENDIAN(&bn->keys) != CPU_BIG_ENDIAN) { 223 bch_err(c, "try_read_btree_node() can't handle endian conversion"); 224 f->ret = -EINVAL; 225 goto unlock; 226 } 227 228 if (darray_push(&f->nodes, n)) 229 f->ret = -ENOMEM; 230 unlock: 231 mutex_unlock(&f->lock); 232 } 233 } 234 235 static int read_btree_nodes_worker(void *p) 236 { 237 struct find_btree_nodes_worker *w = p; 238 struct bch_fs *c = container_of(w->f, struct bch_fs, found_btree_nodes); 239 struct bch_dev *ca = w->ca; 240 void *buf = (void *) __get_free_page(GFP_KERNEL); 241 struct bio *bio = bio_alloc(NULL, 1, 0, GFP_KERNEL); 242 unsigned long last_print = jiffies; 243 244 if (!buf || !bio) { 245 bch_err(c, "read_btree_nodes_worker: error allocating bio/buf"); 246 w->f->ret = -ENOMEM; 247 goto err; 248 } 249 250 for (u64 bucket = ca->mi.first_bucket; bucket < ca->mi.nbuckets; bucket++) 251 for (unsigned bucket_offset = 0; 252 bucket_offset + btree_sectors(c) <= ca->mi.bucket_size; 253 bucket_offset += btree_sectors(c)) { 254 if (time_after(jiffies, last_print + HZ * 30)) { 255 u64 cur_sector = bucket * ca->mi.bucket_size + bucket_offset; 256 u64 end_sector = ca->mi.nbuckets * ca->mi.bucket_size; 257 258 bch_info(ca, "%s: %2u%% done", __func__, 259 (unsigned) div64_u64(cur_sector * 100, end_sector)); 260 last_print = jiffies; 261 } 262 263 u64 sector = bucket * ca->mi.bucket_size + bucket_offset; 264 265 if (c->sb.version_upgrade_complete >= bcachefs_metadata_version_mi_btree_bitmap && 266 !bch2_dev_btree_bitmap_marked_sectors(ca, sector, btree_sectors(c))) 267 continue; 268 269 try_read_btree_node(w->f, ca, bio, buf, sector); 270 } 271 err: 272 bio_put(bio); 273 free_page((unsigned long) buf); 274 percpu_ref_put(&ca->io_ref[READ]); 275 closure_put(w->cl); 276 kfree(w); 277 return 0; 278 } 279 280 static int read_btree_nodes(struct find_btree_nodes *f) 281 { 282 struct bch_fs *c = container_of(f, struct bch_fs, found_btree_nodes); 283 struct closure cl; 284 int ret = 0; 285 286 closure_init_stack(&cl); 287 288 for_each_online_member(c, ca) { 289 if (!(ca->mi.data_allowed & BIT(BCH_DATA_btree))) 290 continue; 291 292 struct find_btree_nodes_worker *w = kmalloc(sizeof(*w), GFP_KERNEL); 293 if (!w) { 294 percpu_ref_put(&ca->io_ref[READ]); 295 ret = -ENOMEM; 296 goto err; 297 } 298 299 w->cl = &cl; 300 w->f = f; 301 w->ca = ca; 302 303 struct task_struct *t = kthread_create(read_btree_nodes_worker, w, "read_btree_nodes/%s", ca->name); 304 ret = PTR_ERR_OR_ZERO(t); 305 if (ret) { 306 percpu_ref_put(&ca->io_ref[READ]); 307 kfree(w); 308 bch_err_msg(c, ret, "starting kthread"); 309 break; 310 } 311 312 closure_get(&cl); 313 percpu_ref_get(&ca->io_ref[READ]); 314 wake_up_process(t); 315 } 316 err: 317 while (closure_sync_timeout(&cl, sysctl_hung_task_timeout_secs * HZ / 2)) 318 ; 319 return f->ret ?: ret; 320 } 321 322 static bool nodes_overlap(const struct found_btree_node *l, 323 const struct found_btree_node *r) 324 { 325 return (l->btree_id == r->btree_id && 326 l->level == r->level && 327 bpos_gt(l->max_key, r->min_key)); 328 } 329 330 static int handle_overwrites(struct bch_fs *c, 331 struct found_btree_node *l, 332 found_btree_nodes *nodes_heap) 333 { 334 struct found_btree_node *r; 335 336 while ((r = min_heap_peek(nodes_heap)) && 337 nodes_overlap(l, r)) { 338 int cmp = found_btree_node_cmp_time(l, r); 339 340 if (cmp > 0) { 341 if (bpos_cmp(l->max_key, r->max_key) >= 0) 342 min_heap_pop(nodes_heap, &found_btree_node_heap_cbs, NULL); 343 else { 344 r->range_updated = true; 345 r->min_key = bpos_successor(l->max_key); 346 r->range_updated = true; 347 min_heap_sift_down(nodes_heap, 0, &found_btree_node_heap_cbs, NULL); 348 } 349 } else if (cmp < 0) { 350 BUG_ON(bpos_eq(l->min_key, r->min_key)); 351 352 l->max_key = bpos_predecessor(r->min_key); 353 l->range_updated = true; 354 } else if (r->level) { 355 min_heap_pop(nodes_heap, &found_btree_node_heap_cbs, NULL); 356 } else { 357 if (bpos_cmp(l->max_key, r->max_key) >= 0) 358 min_heap_pop(nodes_heap, &found_btree_node_heap_cbs, NULL); 359 else { 360 r->range_updated = true; 361 r->min_key = bpos_successor(l->max_key); 362 r->range_updated = true; 363 min_heap_sift_down(nodes_heap, 0, &found_btree_node_heap_cbs, NULL); 364 } 365 } 366 } 367 368 return 0; 369 } 370 371 int bch2_scan_for_btree_nodes(struct bch_fs *c) 372 { 373 struct find_btree_nodes *f = &c->found_btree_nodes; 374 struct printbuf buf = PRINTBUF; 375 found_btree_nodes nodes_heap = {}; 376 size_t dst; 377 int ret = 0; 378 379 if (f->nodes.nr) 380 return 0; 381 382 mutex_init(&f->lock); 383 384 ret = read_btree_nodes(f); 385 if (ret) 386 return ret; 387 388 if (!f->nodes.nr) { 389 bch_err(c, "%s: no btree nodes found", __func__); 390 ret = -EINVAL; 391 goto err; 392 } 393 394 if (0 && c->opts.verbose) { 395 printbuf_reset(&buf); 396 prt_printf(&buf, "%s: nodes found:\n", __func__); 397 found_btree_nodes_to_text(&buf, c, f->nodes); 398 bch2_print_string_as_lines(KERN_INFO, buf.buf); 399 } 400 401 sort(f->nodes.data, f->nodes.nr, sizeof(f->nodes.data[0]), found_btree_node_cmp_cookie, NULL); 402 403 dst = 0; 404 darray_for_each(f->nodes, i) { 405 struct found_btree_node *prev = dst ? f->nodes.data + dst - 1 : NULL; 406 407 if (prev && 408 prev->cookie == i->cookie) { 409 if (prev->nr_ptrs == ARRAY_SIZE(prev->ptrs)) { 410 bch_err(c, "%s: found too many replicas for btree node", __func__); 411 ret = -EINVAL; 412 goto err; 413 } 414 prev->ptrs[prev->nr_ptrs++] = i->ptrs[0]; 415 } else { 416 f->nodes.data[dst++] = *i; 417 } 418 } 419 f->nodes.nr = dst; 420 421 sort(f->nodes.data, f->nodes.nr, sizeof(f->nodes.data[0]), found_btree_node_cmp_pos, NULL); 422 423 if (0 && c->opts.verbose) { 424 printbuf_reset(&buf); 425 prt_printf(&buf, "%s: nodes after merging replicas:\n", __func__); 426 found_btree_nodes_to_text(&buf, c, f->nodes); 427 bch2_print_string_as_lines(KERN_INFO, buf.buf); 428 } 429 430 swap(nodes_heap, f->nodes); 431 432 { 433 /* darray must have same layout as a heap */ 434 min_heap_char real_heap; 435 BUILD_BUG_ON(sizeof(nodes_heap.nr) != sizeof(real_heap.nr)); 436 BUILD_BUG_ON(sizeof(nodes_heap.size) != sizeof(real_heap.size)); 437 BUILD_BUG_ON(offsetof(found_btree_nodes, nr) != offsetof(min_heap_char, nr)); 438 BUILD_BUG_ON(offsetof(found_btree_nodes, size) != offsetof(min_heap_char, size)); 439 } 440 441 min_heapify_all(&nodes_heap, &found_btree_node_heap_cbs, NULL); 442 443 if (nodes_heap.nr) { 444 ret = darray_push(&f->nodes, *min_heap_peek(&nodes_heap)); 445 if (ret) 446 goto err; 447 448 min_heap_pop(&nodes_heap, &found_btree_node_heap_cbs, NULL); 449 } 450 451 while (true) { 452 ret = handle_overwrites(c, &darray_last(f->nodes), &nodes_heap); 453 if (ret) 454 goto err; 455 456 if (!nodes_heap.nr) 457 break; 458 459 ret = darray_push(&f->nodes, *min_heap_peek(&nodes_heap)); 460 if (ret) 461 goto err; 462 463 min_heap_pop(&nodes_heap, &found_btree_node_heap_cbs, NULL); 464 } 465 466 for (struct found_btree_node *n = f->nodes.data; n < &darray_last(f->nodes); n++) 467 BUG_ON(nodes_overlap(n, n + 1)); 468 469 if (0 && c->opts.verbose) { 470 printbuf_reset(&buf); 471 prt_printf(&buf, "%s: nodes found after overwrites:\n", __func__); 472 found_btree_nodes_to_text(&buf, c, f->nodes); 473 bch2_print_string_as_lines(KERN_INFO, buf.buf); 474 } else { 475 bch_info(c, "btree node scan found %zu nodes after overwrites", f->nodes.nr); 476 } 477 478 eytzinger0_sort(f->nodes.data, f->nodes.nr, sizeof(f->nodes.data[0]), found_btree_node_cmp_pos, NULL); 479 err: 480 darray_exit(&nodes_heap); 481 printbuf_exit(&buf); 482 return ret; 483 } 484 485 static int found_btree_node_range_start_cmp(const void *_l, const void *_r) 486 { 487 const struct found_btree_node *l = _l; 488 const struct found_btree_node *r = _r; 489 490 return cmp_int(l->btree_id, r->btree_id) ?: 491 -cmp_int(l->level, r->level) ?: 492 bpos_cmp(l->max_key, r->min_key); 493 } 494 495 #define for_each_found_btree_node_in_range(_f, _search, _idx) \ 496 for (size_t _idx = eytzinger0_find_gt((_f)->nodes.data, (_f)->nodes.nr, \ 497 sizeof((_f)->nodes.data[0]), \ 498 found_btree_node_range_start_cmp, &search); \ 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)) 504 505 bool bch2_btree_node_is_stale(struct bch_fs *c, struct btree *b) 506 { 507 struct find_btree_nodes *f = &c->found_btree_nodes; 508 509 struct found_btree_node search = { 510 .btree_id = b->c.btree_id, 511 .level = b->c.level, 512 .min_key = b->data->min_key, 513 .max_key = b->key.k.p, 514 }; 515 516 for_each_found_btree_node_in_range(f, search, idx) 517 if (f->nodes.data[idx].seq > BTREE_NODE_SEQ(b->data)) 518 return true; 519 return false; 520 } 521 522 bool bch2_btree_has_scanned_nodes(struct bch_fs *c, enum btree_id btree) 523 { 524 struct found_btree_node search = { 525 .btree_id = btree, 526 .level = 0, 527 .min_key = POS_MIN, 528 .max_key = SPOS_MAX, 529 }; 530 531 for_each_found_btree_node_in_range(&c->found_btree_nodes, search, idx) 532 return true; 533 return false; 534 } 535 536 int bch2_get_scanned_nodes(struct bch_fs *c, enum btree_id btree, 537 unsigned level, struct bpos node_min, struct bpos node_max) 538 { 539 if (btree_id_is_alloc(btree)) 540 return 0; 541 542 struct find_btree_nodes *f = &c->found_btree_nodes; 543 544 int ret = bch2_run_explicit_recovery_pass(c, BCH_RECOVERY_PASS_scan_for_btree_nodes); 545 if (ret) 546 return ret; 547 548 if (c->opts.verbose) { 549 struct printbuf buf = PRINTBUF; 550 551 prt_str(&buf, "recovery "); 552 bch2_btree_id_level_to_text(&buf, btree, level); 553 prt_str(&buf, " "); 554 bch2_bpos_to_text(&buf, node_min); 555 prt_str(&buf, " - "); 556 bch2_bpos_to_text(&buf, node_max); 557 558 bch_info(c, "%s(): %s", __func__, buf.buf); 559 printbuf_exit(&buf); 560 } 561 562 struct found_btree_node search = { 563 .btree_id = btree, 564 .level = level, 565 .min_key = node_min, 566 .max_key = node_max, 567 }; 568 569 for_each_found_btree_node_in_range(f, search, idx) { 570 struct found_btree_node n = f->nodes.data[idx]; 571 572 n.range_updated |= bpos_lt(n.min_key, node_min); 573 n.min_key = bpos_max(n.min_key, node_min); 574 575 n.range_updated |= bpos_gt(n.max_key, node_max); 576 n.max_key = bpos_min(n.max_key, node_max); 577 578 struct { __BKEY_PADDED(k, BKEY_BTREE_PTR_VAL_U64s_MAX); } tmp; 579 580 found_btree_node_to_key(&tmp.k, &n); 581 582 if (c->opts.verbose) { 583 struct printbuf buf = PRINTBUF; 584 bch2_bkey_val_to_text(&buf, c, bkey_i_to_s_c(&tmp.k)); 585 bch_verbose(c, "%s(): recovering %s", __func__, buf.buf); 586 printbuf_exit(&buf); 587 } 588 589 BUG_ON(bch2_bkey_validate(c, bkey_i_to_s_c(&tmp.k), 590 (struct bkey_validate_context) { 591 .from = BKEY_VALIDATE_btree_node, 592 .level = level + 1, 593 .btree = btree, 594 })); 595 596 ret = bch2_journal_key_insert(c, btree, level + 1, &tmp.k); 597 if (ret) 598 return ret; 599 } 600 601 return 0; 602 } 603 604 void bch2_find_btree_nodes_exit(struct find_btree_nodes *f) 605 { 606 darray_exit(&f->nodes); 607 } 608