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