1// SPDX-License-Identifier: GPL-2.0 2 3#include "bcachefs.h" 4#include "bkey_buf.h" 5#include "bkey_methods.h" 6#include "btree_update.h" 7#include "extents.h" 8#include "dirent.h" 9#include "fs.h" 10#include "keylist.h" 11#include "str_hash.h" 12#include "subvolume.h" 13 14#include <linux/dcache.h> 15 16static unsigned bch2_dirent_name_bytes(struct bkey_s_c_dirent d) 17{ 18 unsigned bkey_u64s = bkey_val_u64s(d.k); 19 unsigned bkey_bytes = bkey_u64s * sizeof(u64); 20 u64 last_u64 = ((u64*)d.v)[bkey_u64s - 1]; 21#if CPU_BIG_ENDIAN 22 unsigned trailing_nuls = last_u64 ? __builtin_ctzll(last_u64) / 8 : 64 / 8; 23#else 24 unsigned trailing_nuls = last_u64 ? __builtin_clzll(last_u64) / 8 : 64 / 8; 25#endif 26 27 return bkey_bytes - 28 offsetof(struct bch_dirent, d_name) - 29 trailing_nuls; 30} 31 32struct qstr bch2_dirent_get_name(struct bkey_s_c_dirent d) 33{ 34 return (struct qstr) QSTR_INIT(d.v->d_name, bch2_dirent_name_bytes(d)); 35} 36 37static u64 bch2_dirent_hash(const struct bch_hash_info *info, 38 const struct qstr *name) 39{ 40 struct bch_str_hash_ctx ctx; 41 42 bch2_str_hash_init(&ctx, info); 43 bch2_str_hash_update(&ctx, info, name->name, name->len); 44 45 /* [0,2) reserved for dots */ 46 return max_t(u64, bch2_str_hash_end(&ctx, info), 2); 47} 48 49static u64 dirent_hash_key(const struct bch_hash_info *info, const void *key) 50{ 51 return bch2_dirent_hash(info, key); 52} 53 54static u64 dirent_hash_bkey(const struct bch_hash_info *info, struct bkey_s_c k) 55{ 56 struct bkey_s_c_dirent d = bkey_s_c_to_dirent(k); 57 struct qstr name = bch2_dirent_get_name(d); 58 59 return bch2_dirent_hash(info, &name); 60} 61 62static bool dirent_cmp_key(struct bkey_s_c _l, const void *_r) 63{ 64 struct bkey_s_c_dirent l = bkey_s_c_to_dirent(_l); 65 const struct qstr l_name = bch2_dirent_get_name(l); 66 const struct qstr *r_name = _r; 67 68 return !qstr_eq(l_name, *r_name); 69} 70 71static bool dirent_cmp_bkey(struct bkey_s_c _l, struct bkey_s_c _r) 72{ 73 struct bkey_s_c_dirent l = bkey_s_c_to_dirent(_l); 74 struct bkey_s_c_dirent r = bkey_s_c_to_dirent(_r); 75 const struct qstr l_name = bch2_dirent_get_name(l); 76 const struct qstr r_name = bch2_dirent_get_name(r); 77 78 return !qstr_eq(l_name, r_name); 79} 80 81static bool dirent_is_visible(subvol_inum inum, struct bkey_s_c k) 82{ 83 struct bkey_s_c_dirent d = bkey_s_c_to_dirent(k); 84 85 if (d.v->d_type == DT_SUBVOL) 86 return le32_to_cpu(d.v->d_parent_subvol) == inum.subvol; 87 return true; 88} 89 90const struct bch_hash_desc bch2_dirent_hash_desc = { 91 .btree_id = BTREE_ID_dirents, 92 .key_type = KEY_TYPE_dirent, 93 .hash_key = dirent_hash_key, 94 .hash_bkey = dirent_hash_bkey, 95 .cmp_key = dirent_cmp_key, 96 .cmp_bkey = dirent_cmp_bkey, 97 .is_visible = dirent_is_visible, 98}; 99 100int bch2_dirent_invalid(struct bch_fs *c, struct bkey_s_c k, 101 enum bkey_invalid_flags flags, 102 struct printbuf *err) 103{ 104 struct bkey_s_c_dirent d = bkey_s_c_to_dirent(k); 105 struct qstr d_name = bch2_dirent_get_name(d); 106 int ret = 0; 107 108 bkey_fsck_err_on(!d_name.len, c, err, 109 dirent_empty_name, 110 "empty name"); 111 112 bkey_fsck_err_on(bkey_val_u64s(k.k) > dirent_val_u64s(d_name.len), c, err, 113 dirent_val_too_big, 114 "value too big (%zu > %u)", 115 bkey_val_u64s(k.k), dirent_val_u64s(d_name.len)); 116 117 /* 118 * Check new keys don't exceed the max length 119 * (older keys may be larger.) 120 */ 121 bkey_fsck_err_on((flags & BKEY_INVALID_COMMIT) && d_name.len > BCH_NAME_MAX, c, err, 122 dirent_name_too_long, 123 "dirent name too big (%u > %u)", 124 d_name.len, BCH_NAME_MAX); 125 126 bkey_fsck_err_on(d_name.len != strnlen(d_name.name, d_name.len), c, err, 127 dirent_name_embedded_nul, 128 "dirent has stray data after name's NUL"); 129 130 bkey_fsck_err_on((d_name.len == 1 && !memcmp(d_name.name, ".", 1)) || 131 (d_name.len == 2 && !memcmp(d_name.name, "..", 2)), c, err, 132 dirent_name_dot_or_dotdot, 133 "invalid name"); 134 135 bkey_fsck_err_on(memchr(d_name.name, '/', d_name.len), c, err, 136 dirent_name_has_slash, 137 "name with /"); 138 139 bkey_fsck_err_on(d.v->d_type != DT_SUBVOL && 140 le64_to_cpu(d.v->d_inum) == d.k->p.inode, c, err, 141 dirent_to_itself, 142 "dirent points to own directory"); 143fsck_err: 144 return ret; 145} 146 147void bch2_dirent_to_text(struct printbuf *out, struct bch_fs *c, struct bkey_s_c k) 148{ 149 struct bkey_s_c_dirent d = bkey_s_c_to_dirent(k); 150 struct qstr d_name = bch2_dirent_get_name(d); 151 152 prt_printf(out, "%.*s -> ", d_name.len, d_name.name); 153 154 if (d.v->d_type != DT_SUBVOL) 155 prt_printf(out, "%llu", le64_to_cpu(d.v->d_inum)); 156 else 157 prt_printf(out, "%u -> %u", 158 le32_to_cpu(d.v->d_parent_subvol), 159 le32_to_cpu(d.v->d_child_subvol)); 160 161 prt_printf(out, " type %s", bch2_d_type_str(d.v->d_type)); 162} 163 164static struct bkey_i_dirent *dirent_create_key(struct btree_trans *trans, 165 subvol_inum dir, u8 type, 166 const struct qstr *name, u64 dst) 167{ 168 struct bkey_i_dirent *dirent; 169 unsigned u64s = BKEY_U64s + dirent_val_u64s(name->len); 170 171 if (name->len > BCH_NAME_MAX) 172 return ERR_PTR(-ENAMETOOLONG); 173 174 BUG_ON(u64s > U8_MAX); 175 176 dirent = bch2_trans_kmalloc(trans, u64s * sizeof(u64)); 177 if (IS_ERR(dirent)) 178 return dirent; 179 180 bkey_dirent_init(&dirent->k_i); 181 dirent->k.u64s = u64s; 182 183 if (type != DT_SUBVOL) { 184 dirent->v.d_inum = cpu_to_le64(dst); 185 } else { 186 dirent->v.d_parent_subvol = cpu_to_le32(dir.subvol); 187 dirent->v.d_child_subvol = cpu_to_le32(dst); 188 } 189 190 dirent->v.d_type = type; 191 192 memcpy(dirent->v.d_name, name->name, name->len); 193 memset(dirent->v.d_name + name->len, 0, 194 bkey_val_bytes(&dirent->k) - 195 offsetof(struct bch_dirent, d_name) - 196 name->len); 197 198 EBUG_ON(bch2_dirent_name_bytes(dirent_i_to_s_c(dirent)) != name->len); 199 200 return dirent; 201} 202 203int bch2_dirent_create_snapshot(struct btree_trans *trans, 204 u32 dir_subvol, u64 dir, u32 snapshot, 205 const struct bch_hash_info *hash_info, 206 u8 type, const struct qstr *name, u64 dst_inum, 207 u64 *dir_offset, 208 bch_str_hash_flags_t str_hash_flags) 209{ 210 subvol_inum dir_inum = { .subvol = dir_subvol, .inum = dir }; 211 struct bkey_i_dirent *dirent; 212 int ret; 213 214 dirent = dirent_create_key(trans, dir_inum, type, name, dst_inum); 215 ret = PTR_ERR_OR_ZERO(dirent); 216 if (ret) 217 return ret; 218 219 dirent->k.p.inode = dir; 220 dirent->k.p.snapshot = snapshot; 221 222 ret = bch2_hash_set_in_snapshot(trans, bch2_dirent_hash_desc, hash_info, 223 dir_inum, snapshot, 224 &dirent->k_i, str_hash_flags, 225 BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE); 226 *dir_offset = dirent->k.p.offset; 227 228 return ret; 229} 230 231int bch2_dirent_create(struct btree_trans *trans, subvol_inum dir, 232 const struct bch_hash_info *hash_info, 233 u8 type, const struct qstr *name, u64 dst_inum, 234 u64 *dir_offset, 235 bch_str_hash_flags_t str_hash_flags) 236{ 237 struct bkey_i_dirent *dirent; 238 int ret; 239 240 dirent = dirent_create_key(trans, dir, type, name, dst_inum); 241 ret = PTR_ERR_OR_ZERO(dirent); 242 if (ret) 243 return ret; 244 245 ret = bch2_hash_set(trans, bch2_dirent_hash_desc, hash_info, 246 dir, &dirent->k_i, str_hash_flags); 247 *dir_offset = dirent->k.p.offset; 248 249 return ret; 250} 251 252static void dirent_copy_target(struct bkey_i_dirent *dst, 253 struct bkey_s_c_dirent src) 254{ 255 dst->v.d_inum = src.v->d_inum; 256 dst->v.d_type = src.v->d_type; 257} 258 259int bch2_dirent_read_target(struct btree_trans *trans, subvol_inum dir, 260 struct bkey_s_c_dirent d, subvol_inum *target) 261{ 262 struct bch_subvolume s; 263 int ret = 0; 264 265 if (d.v->d_type == DT_SUBVOL && 266 le32_to_cpu(d.v->d_parent_subvol) != dir.subvol) 267 return 1; 268 269 if (likely(d.v->d_type != DT_SUBVOL)) { 270 target->subvol = dir.subvol; 271 target->inum = le64_to_cpu(d.v->d_inum); 272 } else { 273 target->subvol = le32_to_cpu(d.v->d_child_subvol); 274 275 ret = bch2_subvolume_get(trans, target->subvol, true, BTREE_ITER_CACHED, &s); 276 277 target->inum = le64_to_cpu(s.inode); 278 } 279 280 return ret; 281} 282 283int bch2_dirent_rename(struct btree_trans *trans, 284 subvol_inum src_dir, struct bch_hash_info *src_hash, 285 subvol_inum dst_dir, struct bch_hash_info *dst_hash, 286 const struct qstr *src_name, subvol_inum *src_inum, u64 *src_offset, 287 const struct qstr *dst_name, subvol_inum *dst_inum, u64 *dst_offset, 288 enum bch_rename_mode mode) 289{ 290 struct btree_iter src_iter = { NULL }; 291 struct btree_iter dst_iter = { NULL }; 292 struct bkey_s_c old_src, old_dst = bkey_s_c_null; 293 struct bkey_i_dirent *new_src = NULL, *new_dst = NULL; 294 struct bpos dst_pos = 295 POS(dst_dir.inum, bch2_dirent_hash(dst_hash, dst_name)); 296 unsigned src_update_flags = 0; 297 bool delete_src, delete_dst; 298 int ret = 0; 299 300 memset(src_inum, 0, sizeof(*src_inum)); 301 memset(dst_inum, 0, sizeof(*dst_inum)); 302 303 /* Lookup src: */ 304 ret = bch2_hash_lookup(trans, &src_iter, bch2_dirent_hash_desc, 305 src_hash, src_dir, src_name, 306 BTREE_ITER_INTENT); 307 if (ret) 308 goto out; 309 310 old_src = bch2_btree_iter_peek_slot(&src_iter); 311 ret = bkey_err(old_src); 312 if (ret) 313 goto out; 314 315 ret = bch2_dirent_read_target(trans, src_dir, 316 bkey_s_c_to_dirent(old_src), src_inum); 317 if (ret) 318 goto out; 319 320 /* Lookup dst: */ 321 if (mode == BCH_RENAME) { 322 /* 323 * Note that we're _not_ checking if the target already exists - 324 * we're relying on the VFS to do that check for us for 325 * correctness: 326 */ 327 ret = bch2_hash_hole(trans, &dst_iter, bch2_dirent_hash_desc, 328 dst_hash, dst_dir, dst_name); 329 if (ret) 330 goto out; 331 } else { 332 ret = bch2_hash_lookup(trans, &dst_iter, bch2_dirent_hash_desc, 333 dst_hash, dst_dir, dst_name, 334 BTREE_ITER_INTENT); 335 if (ret) 336 goto out; 337 338 old_dst = bch2_btree_iter_peek_slot(&dst_iter); 339 ret = bkey_err(old_dst); 340 if (ret) 341 goto out; 342 343 ret = bch2_dirent_read_target(trans, dst_dir, 344 bkey_s_c_to_dirent(old_dst), dst_inum); 345 if (ret) 346 goto out; 347 } 348 349 if (mode != BCH_RENAME_EXCHANGE) 350 *src_offset = dst_iter.pos.offset; 351 352 /* Create new dst key: */ 353 new_dst = dirent_create_key(trans, dst_dir, 0, dst_name, 0); 354 ret = PTR_ERR_OR_ZERO(new_dst); 355 if (ret) 356 goto out; 357 358 dirent_copy_target(new_dst, bkey_s_c_to_dirent(old_src)); 359 new_dst->k.p = dst_iter.pos; 360 361 /* Create new src key: */ 362 if (mode == BCH_RENAME_EXCHANGE) { 363 new_src = dirent_create_key(trans, src_dir, 0, src_name, 0); 364 ret = PTR_ERR_OR_ZERO(new_src); 365 if (ret) 366 goto out; 367 368 dirent_copy_target(new_src, bkey_s_c_to_dirent(old_dst)); 369 new_src->k.p = src_iter.pos; 370 } else { 371 new_src = bch2_trans_kmalloc(trans, sizeof(struct bkey_i)); 372 ret = PTR_ERR_OR_ZERO(new_src); 373 if (ret) 374 goto out; 375 376 bkey_init(&new_src->k); 377 new_src->k.p = src_iter.pos; 378 379 if (bkey_le(dst_pos, src_iter.pos) && 380 bkey_lt(src_iter.pos, dst_iter.pos)) { 381 /* 382 * We have a hash collision for the new dst key, 383 * and new_src - the key we're deleting - is between 384 * new_dst's hashed slot and the slot we're going to be 385 * inserting it into - oops. This will break the hash 386 * table if we don't deal with it: 387 */ 388 if (mode == BCH_RENAME) { 389 /* 390 * If we're not overwriting, we can just insert 391 * new_dst at the src position: 392 */ 393 new_src = new_dst; 394 new_src->k.p = src_iter.pos; 395 goto out_set_src; 396 } else { 397 /* If we're overwriting, we can't insert new_dst 398 * at a different slot because it has to 399 * overwrite old_dst - just make sure to use a 400 * whiteout when deleting src: 401 */ 402 new_src->k.type = KEY_TYPE_hash_whiteout; 403 } 404 } else { 405 /* Check if we need a whiteout to delete src: */ 406 ret = bch2_hash_needs_whiteout(trans, bch2_dirent_hash_desc, 407 src_hash, &src_iter); 408 if (ret < 0) 409 goto out; 410 411 if (ret) 412 new_src->k.type = KEY_TYPE_hash_whiteout; 413 } 414 } 415 416 if (new_dst->v.d_type == DT_SUBVOL) 417 new_dst->v.d_parent_subvol = cpu_to_le32(dst_dir.subvol); 418 419 if ((mode == BCH_RENAME_EXCHANGE) && 420 new_src->v.d_type == DT_SUBVOL) 421 new_src->v.d_parent_subvol = cpu_to_le32(src_dir.subvol); 422 423 ret = bch2_trans_update(trans, &dst_iter, &new_dst->k_i, 0); 424 if (ret) 425 goto out; 426out_set_src: 427 /* 428 * If we're deleting a subvolume we need to really delete the dirent, 429 * not just emit a whiteout in the current snapshot - there can only be 430 * single dirent that points to a given subvolume. 431 * 432 * IOW, we don't maintain multiple versions in different snapshots of 433 * dirents that point to subvolumes - dirents that point to subvolumes 434 * are only visible in one particular subvolume so it's not necessary, 435 * and it would be particularly confusing for fsck to have to deal with. 436 */ 437 delete_src = bkey_s_c_to_dirent(old_src).v->d_type == DT_SUBVOL && 438 new_src->k.p.snapshot != old_src.k->p.snapshot; 439 440 delete_dst = old_dst.k && 441 bkey_s_c_to_dirent(old_dst).v->d_type == DT_SUBVOL && 442 new_dst->k.p.snapshot != old_dst.k->p.snapshot; 443 444 if (!delete_src || !bkey_deleted(&new_src->k)) { 445 ret = bch2_trans_update(trans, &src_iter, &new_src->k_i, src_update_flags); 446 if (ret) 447 goto out; 448 } 449 450 if (delete_src) { 451 bch2_btree_iter_set_snapshot(&src_iter, old_src.k->p.snapshot); 452 ret = bch2_btree_iter_traverse(&src_iter) ?: 453 bch2_btree_delete_at(trans, &src_iter, BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE); 454 if (ret) 455 goto out; 456 } 457 458 if (delete_dst) { 459 bch2_btree_iter_set_snapshot(&dst_iter, old_dst.k->p.snapshot); 460 ret = bch2_btree_iter_traverse(&dst_iter) ?: 461 bch2_btree_delete_at(trans, &dst_iter, BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE); 462 if (ret) 463 goto out; 464 } 465 466 if (mode == BCH_RENAME_EXCHANGE) 467 *src_offset = new_src->k.p.offset; 468 *dst_offset = new_dst->k.p.offset; 469out: 470 bch2_trans_iter_exit(trans, &src_iter); 471 bch2_trans_iter_exit(trans, &dst_iter); 472 return ret; 473} 474 475int bch2_dirent_lookup_trans(struct btree_trans *trans, 476 struct btree_iter *iter, 477 subvol_inum dir, 478 const struct bch_hash_info *hash_info, 479 const struct qstr *name, subvol_inum *inum, 480 unsigned flags) 481{ 482 int ret = bch2_hash_lookup(trans, iter, bch2_dirent_hash_desc, 483 hash_info, dir, name, flags); 484 if (ret) 485 return ret; 486 487 struct bkey_s_c k = bch2_btree_iter_peek_slot(iter); 488 ret = bkey_err(k); 489 if (ret) 490 goto err; 491 492 ret = bch2_dirent_read_target(trans, dir, bkey_s_c_to_dirent(k), inum); 493 if (ret > 0) 494 ret = -ENOENT; 495err: 496 if (ret) 497 bch2_trans_iter_exit(trans, iter); 498 return ret; 499} 500 501u64 bch2_dirent_lookup(struct bch_fs *c, subvol_inum dir, 502 const struct bch_hash_info *hash_info, 503 const struct qstr *name, subvol_inum *inum) 504{ 505 struct btree_trans *trans = bch2_trans_get(c); 506 struct btree_iter iter = { NULL }; 507 508 int ret = lockrestart_do(trans, 509 bch2_dirent_lookup_trans(trans, &iter, dir, hash_info, name, inum, 0)); 510 bch2_trans_iter_exit(trans, &iter); 511 bch2_trans_put(trans); 512 return ret; 513} 514 515int bch2_empty_dir_snapshot(struct btree_trans *trans, u64 dir, u32 subvol, u32 snapshot) 516{ 517 struct btree_iter iter; 518 struct bkey_s_c k; 519 int ret; 520 521 for_each_btree_key_upto_norestart(trans, iter, BTREE_ID_dirents, 522 SPOS(dir, 0, snapshot), 523 POS(dir, U64_MAX), 0, k, ret) 524 if (k.k->type == KEY_TYPE_dirent) { 525 struct bkey_s_c_dirent d = bkey_s_c_to_dirent(k); 526 if (d.v->d_type == DT_SUBVOL && le32_to_cpu(d.v->d_parent_subvol) != subvol) 527 continue; 528 ret = -BCH_ERR_ENOTEMPTY_dir_not_empty; 529 break; 530 } 531 bch2_trans_iter_exit(trans, &iter); 532 533 return ret; 534} 535 536int bch2_empty_dir_trans(struct btree_trans *trans, subvol_inum dir) 537{ 538 u32 snapshot; 539 540 return bch2_subvolume_get_snapshot(trans, dir.subvol, &snapshot) ?: 541 bch2_empty_dir_snapshot(trans, dir.inum, dir.subvol, snapshot); 542} 543 544int bch2_readdir(struct bch_fs *c, subvol_inum inum, struct dir_context *ctx) 545{ 546 struct btree_trans *trans = bch2_trans_get(c); 547 struct btree_iter iter; 548 struct bkey_s_c k; 549 struct bkey_s_c_dirent dirent; 550 subvol_inum target; 551 u32 snapshot; 552 struct bkey_buf sk; 553 struct qstr name; 554 int ret; 555 556 bch2_bkey_buf_init(&sk); 557retry: 558 bch2_trans_begin(trans); 559 560 ret = bch2_subvolume_get_snapshot(trans, inum.subvol, &snapshot); 561 if (ret) 562 goto err; 563 564 for_each_btree_key_upto_norestart(trans, iter, BTREE_ID_dirents, 565 SPOS(inum.inum, ctx->pos, snapshot), 566 POS(inum.inum, U64_MAX), 0, k, ret) { 567 if (k.k->type != KEY_TYPE_dirent) 568 continue; 569 570 dirent = bkey_s_c_to_dirent(k); 571 572 ret = bch2_dirent_read_target(trans, inum, dirent, &target); 573 if (ret < 0) 574 break; 575 if (ret) 576 continue; 577 578 /* dir_emit() can fault and block: */ 579 bch2_bkey_buf_reassemble(&sk, c, k); 580 dirent = bkey_i_to_s_c_dirent(sk.k); 581 bch2_trans_unlock(trans); 582 583 name = bch2_dirent_get_name(dirent); 584 585 ctx->pos = dirent.k->p.offset; 586 if (!dir_emit(ctx, name.name, 587 name.len, 588 target.inum, 589 vfs_d_type(dirent.v->d_type))) 590 break; 591 ctx->pos = dirent.k->p.offset + 1; 592 593 /* 594 * read_target looks up subvolumes, we can overflow paths if the 595 * directory has many subvolumes in it 596 */ 597 ret = btree_trans_too_many_iters(trans); 598 if (ret) 599 break; 600 } 601 bch2_trans_iter_exit(trans, &iter); 602err: 603 if (bch2_err_matches(ret, BCH_ERR_transaction_restart)) 604 goto retry; 605 606 bch2_trans_put(trans); 607 bch2_bkey_buf_exit(&sk, c); 608 609 return ret; 610} 611