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 16 static 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 32 struct 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 37 static 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 49 static u64 dirent_hash_key(const struct bch_hash_info *info, const void *key) 50 { 51 return bch2_dirent_hash(info, key); 52 } 53 54 static 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 62 static 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 71 static 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 81 static 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 90 const 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 100 int 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"); 143 fsck_err: 144 return ret; 145 } 146 147 void bch2_dirent_to_text(struct printbuf *out, struct bch_fs *c, 148 struct bkey_s_c k) 149 { 150 struct bkey_s_c_dirent d = bkey_s_c_to_dirent(k); 151 struct qstr d_name = bch2_dirent_get_name(d); 152 153 prt_printf(out, "%.*s -> %llu type %s", 154 d_name.len, 155 d_name.name, 156 d.v->d_type != DT_SUBVOL 157 ? le64_to_cpu(d.v->d_inum) 158 : le32_to_cpu(d.v->d_child_subvol), 159 bch2_d_type_str(d.v->d_type)); 160 } 161 162 static struct bkey_i_dirent *dirent_create_key(struct btree_trans *trans, 163 subvol_inum dir, u8 type, 164 const struct qstr *name, u64 dst) 165 { 166 struct bkey_i_dirent *dirent; 167 unsigned u64s = BKEY_U64s + dirent_val_u64s(name->len); 168 169 if (name->len > BCH_NAME_MAX) 170 return ERR_PTR(-ENAMETOOLONG); 171 172 BUG_ON(u64s > U8_MAX); 173 174 dirent = bch2_trans_kmalloc(trans, u64s * sizeof(u64)); 175 if (IS_ERR(dirent)) 176 return dirent; 177 178 bkey_dirent_init(&dirent->k_i); 179 dirent->k.u64s = u64s; 180 181 if (type != DT_SUBVOL) { 182 dirent->v.d_inum = cpu_to_le64(dst); 183 } else { 184 dirent->v.d_parent_subvol = cpu_to_le32(dir.subvol); 185 dirent->v.d_child_subvol = cpu_to_le32(dst); 186 } 187 188 dirent->v.d_type = type; 189 190 memcpy(dirent->v.d_name, name->name, name->len); 191 memset(dirent->v.d_name + name->len, 0, 192 bkey_val_bytes(&dirent->k) - 193 offsetof(struct bch_dirent, d_name) - 194 name->len); 195 196 EBUG_ON(bch2_dirent_name_bytes(dirent_i_to_s_c(dirent)) != name->len); 197 198 return dirent; 199 } 200 201 int bch2_dirent_create_snapshot(struct btree_trans *trans, 202 u64 dir, u32 snapshot, 203 const struct bch_hash_info *hash_info, 204 u8 type, const struct qstr *name, u64 dst_inum, 205 u64 *dir_offset, 206 bch_str_hash_flags_t str_hash_flags) 207 { 208 subvol_inum zero_inum = { 0 }; 209 struct bkey_i_dirent *dirent; 210 int ret; 211 212 dirent = dirent_create_key(trans, zero_inum, type, name, dst_inum); 213 ret = PTR_ERR_OR_ZERO(dirent); 214 if (ret) 215 return ret; 216 217 dirent->k.p.inode = dir; 218 dirent->k.p.snapshot = snapshot; 219 220 ret = bch2_hash_set_snapshot(trans, bch2_dirent_hash_desc, hash_info, 221 zero_inum, snapshot, 222 &dirent->k_i, str_hash_flags, 223 BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE); 224 *dir_offset = dirent->k.p.offset; 225 226 return ret; 227 } 228 229 int bch2_dirent_create(struct btree_trans *trans, subvol_inum dir, 230 const struct bch_hash_info *hash_info, 231 u8 type, const struct qstr *name, u64 dst_inum, 232 u64 *dir_offset, 233 bch_str_hash_flags_t str_hash_flags) 234 { 235 struct bkey_i_dirent *dirent; 236 int ret; 237 238 dirent = dirent_create_key(trans, dir, type, name, dst_inum); 239 ret = PTR_ERR_OR_ZERO(dirent); 240 if (ret) 241 return ret; 242 243 ret = bch2_hash_set(trans, bch2_dirent_hash_desc, hash_info, 244 dir, &dirent->k_i, str_hash_flags); 245 *dir_offset = dirent->k.p.offset; 246 247 return ret; 248 } 249 250 static void dirent_copy_target(struct bkey_i_dirent *dst, 251 struct bkey_s_c_dirent src) 252 { 253 dst->v.d_inum = src.v->d_inum; 254 dst->v.d_type = src.v->d_type; 255 } 256 257 int bch2_dirent_read_target(struct btree_trans *trans, subvol_inum dir, 258 struct bkey_s_c_dirent d, subvol_inum *target) 259 { 260 struct bch_subvolume s; 261 int ret = 0; 262 263 if (d.v->d_type == DT_SUBVOL && 264 le32_to_cpu(d.v->d_parent_subvol) != dir.subvol) 265 return 1; 266 267 if (likely(d.v->d_type != DT_SUBVOL)) { 268 target->subvol = dir.subvol; 269 target->inum = le64_to_cpu(d.v->d_inum); 270 } else { 271 target->subvol = le32_to_cpu(d.v->d_child_subvol); 272 273 ret = bch2_subvolume_get(trans, target->subvol, true, BTREE_ITER_CACHED, &s); 274 275 target->inum = le64_to_cpu(s.inode); 276 } 277 278 return ret; 279 } 280 281 int bch2_dirent_rename(struct btree_trans *trans, 282 subvol_inum src_dir, struct bch_hash_info *src_hash, 283 subvol_inum dst_dir, struct bch_hash_info *dst_hash, 284 const struct qstr *src_name, subvol_inum *src_inum, u64 *src_offset, 285 const struct qstr *dst_name, subvol_inum *dst_inum, u64 *dst_offset, 286 enum bch_rename_mode mode) 287 { 288 struct btree_iter src_iter = { NULL }; 289 struct btree_iter dst_iter = { NULL }; 290 struct bkey_s_c old_src, old_dst = bkey_s_c_null; 291 struct bkey_i_dirent *new_src = NULL, *new_dst = NULL; 292 struct bpos dst_pos = 293 POS(dst_dir.inum, bch2_dirent_hash(dst_hash, dst_name)); 294 unsigned src_type = 0, dst_type = 0, src_update_flags = 0; 295 int ret = 0; 296 297 if (src_dir.subvol != dst_dir.subvol) 298 return -EXDEV; 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 src_type = bkey_s_c_to_dirent(old_src).v->d_type; 321 322 if (src_type == DT_SUBVOL && mode == BCH_RENAME_EXCHANGE) 323 return -EOPNOTSUPP; 324 325 326 /* Lookup dst: */ 327 if (mode == BCH_RENAME) { 328 /* 329 * Note that we're _not_ checking if the target already exists - 330 * we're relying on the VFS to do that check for us for 331 * correctness: 332 */ 333 ret = bch2_hash_hole(trans, &dst_iter, bch2_dirent_hash_desc, 334 dst_hash, dst_dir, dst_name); 335 if (ret) 336 goto out; 337 } else { 338 ret = bch2_hash_lookup(trans, &dst_iter, bch2_dirent_hash_desc, 339 dst_hash, dst_dir, dst_name, 340 BTREE_ITER_INTENT); 341 if (ret) 342 goto out; 343 344 old_dst = bch2_btree_iter_peek_slot(&dst_iter); 345 ret = bkey_err(old_dst); 346 if (ret) 347 goto out; 348 349 ret = bch2_dirent_read_target(trans, dst_dir, 350 bkey_s_c_to_dirent(old_dst), dst_inum); 351 if (ret) 352 goto out; 353 354 dst_type = bkey_s_c_to_dirent(old_dst).v->d_type; 355 356 if (dst_type == DT_SUBVOL) 357 return -EOPNOTSUPP; 358 } 359 360 if (mode != BCH_RENAME_EXCHANGE) 361 *src_offset = dst_iter.pos.offset; 362 363 /* Create new dst key: */ 364 new_dst = dirent_create_key(trans, dst_dir, 0, dst_name, 0); 365 ret = PTR_ERR_OR_ZERO(new_dst); 366 if (ret) 367 goto out; 368 369 dirent_copy_target(new_dst, bkey_s_c_to_dirent(old_src)); 370 new_dst->k.p = dst_iter.pos; 371 372 /* Create new src key: */ 373 if (mode == BCH_RENAME_EXCHANGE) { 374 new_src = dirent_create_key(trans, src_dir, 0, src_name, 0); 375 ret = PTR_ERR_OR_ZERO(new_src); 376 if (ret) 377 goto out; 378 379 dirent_copy_target(new_src, bkey_s_c_to_dirent(old_dst)); 380 new_src->k.p = src_iter.pos; 381 } else { 382 new_src = bch2_trans_kmalloc(trans, sizeof(struct bkey_i)); 383 ret = PTR_ERR_OR_ZERO(new_src); 384 if (ret) 385 goto out; 386 387 bkey_init(&new_src->k); 388 new_src->k.p = src_iter.pos; 389 390 if (bkey_le(dst_pos, src_iter.pos) && 391 bkey_lt(src_iter.pos, dst_iter.pos)) { 392 /* 393 * We have a hash collision for the new dst key, 394 * and new_src - the key we're deleting - is between 395 * new_dst's hashed slot and the slot we're going to be 396 * inserting it into - oops. This will break the hash 397 * table if we don't deal with it: 398 */ 399 if (mode == BCH_RENAME) { 400 /* 401 * If we're not overwriting, we can just insert 402 * new_dst at the src position: 403 */ 404 new_src = new_dst; 405 new_src->k.p = src_iter.pos; 406 goto out_set_src; 407 } else { 408 /* If we're overwriting, we can't insert new_dst 409 * at a different slot because it has to 410 * overwrite old_dst - just make sure to use a 411 * whiteout when deleting src: 412 */ 413 new_src->k.type = KEY_TYPE_hash_whiteout; 414 } 415 } else { 416 /* Check if we need a whiteout to delete src: */ 417 ret = bch2_hash_needs_whiteout(trans, bch2_dirent_hash_desc, 418 src_hash, &src_iter); 419 if (ret < 0) 420 goto out; 421 422 if (ret) 423 new_src->k.type = KEY_TYPE_hash_whiteout; 424 } 425 } 426 427 ret = bch2_trans_update(trans, &dst_iter, &new_dst->k_i, 0); 428 if (ret) 429 goto out; 430 out_set_src: 431 432 /* 433 * If we're deleting a subvolume, we need to really delete the dirent, 434 * not just emit a whiteout in the current snapshot: 435 */ 436 if (src_type == DT_SUBVOL) { 437 bch2_btree_iter_set_snapshot(&src_iter, old_src.k->p.snapshot); 438 ret = bch2_btree_iter_traverse(&src_iter); 439 if (ret) 440 goto out; 441 442 new_src->k.p = src_iter.pos; 443 src_update_flags |= BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE; 444 } 445 446 ret = bch2_trans_update(trans, &src_iter, &new_src->k_i, src_update_flags); 447 if (ret) 448 goto out; 449 450 if (mode == BCH_RENAME_EXCHANGE) 451 *src_offset = new_src->k.p.offset; 452 *dst_offset = new_dst->k.p.offset; 453 out: 454 bch2_trans_iter_exit(trans, &src_iter); 455 bch2_trans_iter_exit(trans, &dst_iter); 456 return ret; 457 } 458 459 int __bch2_dirent_lookup_trans(struct btree_trans *trans, 460 struct btree_iter *iter, 461 subvol_inum dir, 462 const struct bch_hash_info *hash_info, 463 const struct qstr *name, subvol_inum *inum, 464 unsigned flags) 465 { 466 struct bkey_s_c k; 467 struct bkey_s_c_dirent d; 468 u32 snapshot; 469 int ret; 470 471 ret = bch2_subvolume_get_snapshot(trans, dir.subvol, &snapshot); 472 if (ret) 473 return ret; 474 475 ret = bch2_hash_lookup(trans, iter, bch2_dirent_hash_desc, 476 hash_info, dir, name, flags); 477 if (ret) 478 return ret; 479 480 k = bch2_btree_iter_peek_slot(iter); 481 ret = bkey_err(k); 482 if (ret) 483 goto err; 484 485 d = bkey_s_c_to_dirent(k); 486 487 ret = bch2_dirent_read_target(trans, dir, d, inum); 488 if (ret > 0) 489 ret = -ENOENT; 490 err: 491 if (ret) 492 bch2_trans_iter_exit(trans, iter); 493 494 return ret; 495 } 496 497 u64 bch2_dirent_lookup(struct bch_fs *c, subvol_inum dir, 498 const struct bch_hash_info *hash_info, 499 const struct qstr *name, subvol_inum *inum) 500 { 501 struct btree_trans *trans = bch2_trans_get(c); 502 struct btree_iter iter = { NULL }; 503 504 int ret = lockrestart_do(trans, 505 __bch2_dirent_lookup_trans(trans, &iter, dir, hash_info, name, inum, 0)); 506 bch2_trans_iter_exit(trans, &iter); 507 bch2_trans_put(trans); 508 return ret; 509 } 510 511 int bch2_empty_dir_snapshot(struct btree_trans *trans, u64 dir, u32 snapshot) 512 { 513 struct btree_iter iter; 514 struct bkey_s_c k; 515 int ret; 516 517 for_each_btree_key_upto_norestart(trans, iter, BTREE_ID_dirents, 518 SPOS(dir, 0, snapshot), 519 POS(dir, U64_MAX), 0, k, ret) 520 if (k.k->type == KEY_TYPE_dirent) { 521 ret = -ENOTEMPTY; 522 break; 523 } 524 bch2_trans_iter_exit(trans, &iter); 525 526 return ret; 527 } 528 529 int bch2_empty_dir_trans(struct btree_trans *trans, subvol_inum dir) 530 { 531 u32 snapshot; 532 533 return bch2_subvolume_get_snapshot(trans, dir.subvol, &snapshot) ?: 534 bch2_empty_dir_snapshot(trans, dir.inum, snapshot); 535 } 536 537 int bch2_readdir(struct bch_fs *c, subvol_inum inum, struct dir_context *ctx) 538 { 539 struct btree_trans *trans = bch2_trans_get(c); 540 struct btree_iter iter; 541 struct bkey_s_c k; 542 struct bkey_s_c_dirent dirent; 543 subvol_inum target; 544 u32 snapshot; 545 struct bkey_buf sk; 546 struct qstr name; 547 int ret; 548 549 bch2_bkey_buf_init(&sk); 550 retry: 551 bch2_trans_begin(trans); 552 553 ret = bch2_subvolume_get_snapshot(trans, inum.subvol, &snapshot); 554 if (ret) 555 goto err; 556 557 for_each_btree_key_upto_norestart(trans, iter, BTREE_ID_dirents, 558 SPOS(inum.inum, ctx->pos, snapshot), 559 POS(inum.inum, U64_MAX), 0, k, ret) { 560 if (k.k->type != KEY_TYPE_dirent) 561 continue; 562 563 dirent = bkey_s_c_to_dirent(k); 564 565 ret = bch2_dirent_read_target(trans, inum, dirent, &target); 566 if (ret < 0) 567 break; 568 if (ret) 569 continue; 570 571 /* dir_emit() can fault and block: */ 572 bch2_bkey_buf_reassemble(&sk, c, k); 573 dirent = bkey_i_to_s_c_dirent(sk.k); 574 bch2_trans_unlock(trans); 575 576 name = bch2_dirent_get_name(dirent); 577 578 ctx->pos = dirent.k->p.offset; 579 if (!dir_emit(ctx, name.name, 580 name.len, 581 target.inum, 582 vfs_d_type(dirent.v->d_type))) 583 break; 584 ctx->pos = dirent.k->p.offset + 1; 585 586 /* 587 * read_target looks up subvolumes, we can overflow paths if the 588 * directory has many subvolumes in it 589 */ 590 ret = btree_trans_too_many_iters(trans); 591 if (ret) 592 break; 593 } 594 bch2_trans_iter_exit(trans, &iter); 595 err: 596 if (bch2_err_matches(ret, BCH_ERR_transaction_restart)) 597 goto retry; 598 599 bch2_trans_put(trans); 600 bch2_bkey_buf_exit(&sk, c); 601 602 return ret; 603 } 604