dirent.c 13.9 KB
Newer Older
1 2 3 4 5 6 7 8 9 10
// SPDX-License-Identifier: GPL-2.0

#include "bcachefs.h"
#include "bkey_methods.h"
#include "btree_update.h"
#include "extents.h"
#include "dirent.h"
#include "fs.h"
#include "keylist.h"
#include "str_hash.h"
11
#include "subvolume.h"
12 13 14 15 16 17 18 19

#include <linux/dcache.h>

unsigned bch2_dirent_name_bytes(struct bkey_s_c_dirent d)
{
	unsigned len = bkey_val_bytes(d.k) -
		offsetof(struct bch_dirent, d_name);

20
	return strnlen(d.v->d_name, len);
21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
}

static u64 bch2_dirent_hash(const struct bch_hash_info *info,
			    const struct qstr *name)
{
	struct bch_str_hash_ctx ctx;

	bch2_str_hash_init(&ctx, info);
	bch2_str_hash_update(&ctx, info, name->name, name->len);

	/* [0,2) reserved for dots */
	return max_t(u64, bch2_str_hash_end(&ctx, info), 2);
}

static u64 dirent_hash_key(const struct bch_hash_info *info, const void *key)
{
	return bch2_dirent_hash(info, key);
}

static u64 dirent_hash_bkey(const struct bch_hash_info *info, struct bkey_s_c k)
{
	struct bkey_s_c_dirent d = bkey_s_c_to_dirent(k);
	struct qstr name = QSTR_INIT(d.v->d_name, bch2_dirent_name_bytes(d));

	return bch2_dirent_hash(info, &name);
}

static bool dirent_cmp_key(struct bkey_s_c _l, const void *_r)
{
	struct bkey_s_c_dirent l = bkey_s_c_to_dirent(_l);
	int len = bch2_dirent_name_bytes(l);
	const struct qstr *r = _r;

	return len - r->len ?: memcmp(l.v->d_name, r->name, len);
}

static bool dirent_cmp_bkey(struct bkey_s_c _l, struct bkey_s_c _r)
{
	struct bkey_s_c_dirent l = bkey_s_c_to_dirent(_l);
	struct bkey_s_c_dirent r = bkey_s_c_to_dirent(_r);
	int l_len = bch2_dirent_name_bytes(l);
	int r_len = bch2_dirent_name_bytes(r);

	return l_len - r_len ?: memcmp(l.v->d_name, r.v->d_name, l_len);
}

67 68 69 70 71 72 73 74 75
static bool dirent_is_visible(subvol_inum inum, struct bkey_s_c k)
{
	struct bkey_s_c_dirent d = bkey_s_c_to_dirent(k);

	if (d.v->d_type == DT_SUBVOL)
		return le32_to_cpu(d.v->d_parent_subvol) == inum.subvol;
	return true;
}

76
const struct bch_hash_desc bch2_dirent_hash_desc = {
77
	.btree_id	= BTREE_ID_dirents,
78
	.key_type	= KEY_TYPE_dirent,
79 80 81 82
	.hash_key	= dirent_hash_key,
	.hash_bkey	= dirent_hash_bkey,
	.cmp_key	= dirent_cmp_key,
	.cmp_bkey	= dirent_cmp_bkey,
83
	.is_visible	= dirent_is_visible,
84 85
};

86
int bch2_dirent_invalid(const struct bch_fs *c, struct bkey_s_c k,
87
			int rw, struct printbuf *err)
88
{
89
	struct bkey_s_c_dirent d = bkey_s_c_to_dirent(k);
90 91
	unsigned len;

92
	if (bkey_val_bytes(k.k) < sizeof(struct bch_dirent)) {
93
		prt_printf(err, "incorrect value size (%zu < %zu)",
94
		       bkey_val_bytes(k.k), sizeof(*d.v));
95
		return -BCH_ERR_invalid_bkey;
96
	}
97

98
	len = bch2_dirent_name_bytes(d);
99
	if (!len) {
100
		prt_printf(err, "empty name");
101
		return -BCH_ERR_invalid_bkey;
102 103 104
	}

	if (bkey_val_u64s(k.k) > dirent_val_u64s(len)) {
105
		prt_printf(err, "value too big (%zu > %u)",
106
		       bkey_val_u64s(k.k), dirent_val_u64s(len));
107
		return -BCH_ERR_invalid_bkey;
108 109 110
	}

	if (len > BCH_NAME_MAX) {
111
		prt_printf(err, "dirent name too big (%u > %u)",
112
		       len, BCH_NAME_MAX);
113
		return -BCH_ERR_invalid_bkey;
114 115 116
	}

	if (len == 1 && !memcmp(d.v->d_name, ".", 1)) {
117
		prt_printf(err, "invalid name");
118
		return -BCH_ERR_invalid_bkey;
119 120 121
	}

	if (len == 2 && !memcmp(d.v->d_name, "..", 2)) {
122
		prt_printf(err, "invalid name");
123
		return -BCH_ERR_invalid_bkey;
124 125 126
	}

	if (memchr(d.v->d_name, '/', len)) {
127
		prt_printf(err, "invalid name");
128
		return -BCH_ERR_invalid_bkey;
129
	}
130

131
	if (d.v->d_type != DT_SUBVOL &&
132
	    le64_to_cpu(d.v->d_inum) == d.k->p.inode) {
133
		prt_printf(err, "dirent points to own directory");
134
		return -BCH_ERR_invalid_bkey;
135
	}
136

137
	return 0;
138 139
}

140 141
void bch2_dirent_to_text(struct printbuf *out, struct bch_fs *c,
			 struct bkey_s_c k)
142
{
143 144
	struct bkey_s_c_dirent d = bkey_s_c_to_dirent(k);

145
	prt_printf(out, "%.*s -> %llu type %s",
146 147
	       bch2_dirent_name_bytes(d),
	       d.v->d_name,
148 149 150
	       d.v->d_type != DT_SUBVOL
	       ? le64_to_cpu(d.v->d_inum)
	       : le32_to_cpu(d.v->d_child_subvol),
151
	       bch2_d_type_str(d.v->d_type));
152 153 154
}

static struct bkey_i_dirent *dirent_create_key(struct btree_trans *trans,
155 156
				subvol_inum dir, u8 type,
				const struct qstr *name, u64 dst)
157 158 159 160 161 162 163 164 165 166 167 168 169 170 171
{
	struct bkey_i_dirent *dirent;
	unsigned u64s = BKEY_U64s + dirent_val_u64s(name->len);

	if (name->len > BCH_NAME_MAX)
		return ERR_PTR(-ENAMETOOLONG);

	BUG_ON(u64s > U8_MAX);

	dirent = bch2_trans_kmalloc(trans, u64s * sizeof(u64));
	if (IS_ERR(dirent))
		return dirent;

	bkey_dirent_init(&dirent->k_i);
	dirent->k.u64s = u64s;
172 173 174 175 176 177 178 179

	if (type != DT_SUBVOL) {
		dirent->v.d_inum = cpu_to_le64(dst);
	} else {
		dirent->v.d_parent_subvol = cpu_to_le32(dir.subvol);
		dirent->v.d_child_subvol = cpu_to_le32(dst);
	}

180 181 182 183 184 185 186 187 188 189 190 191 192
	dirent->v.d_type = type;

	memcpy(dirent->v.d_name, name->name, name->len);
	memset(dirent->v.d_name + name->len, 0,
	       bkey_val_bytes(&dirent->k) -
	       offsetof(struct bch_dirent, d_name) -
	       name->len);

	EBUG_ON(bch2_dirent_name_bytes(dirent_i_to_s_c(dirent)) != name->len);

	return dirent;
}

193 194
int bch2_dirent_create(struct btree_trans *trans, subvol_inum dir,
		       const struct bch_hash_info *hash_info,
195
		       u8 type, const struct qstr *name, u64 dst_inum,
196
		       u64 *dir_offset, int flags)
197 198 199 200
{
	struct bkey_i_dirent *dirent;
	int ret;

201
	dirent = dirent_create_key(trans, dir, type, name, dst_inum);
202 203 204 205
	ret = PTR_ERR_OR_ZERO(dirent);
	if (ret)
		return ret;

206
	ret = bch2_hash_set(trans, bch2_dirent_hash_desc, hash_info,
207
			    dir, &dirent->k_i, flags);
208 209 210
	*dir_offset = dirent->k.p.offset;

	return ret;
211 212 213 214 215 216 217 218 219
}

static void dirent_copy_target(struct bkey_i_dirent *dst,
			       struct bkey_s_c_dirent src)
{
	dst->v.d_inum = src.v->d_inum;
	dst->v.d_type = src.v->d_type;
}

220 221
int bch2_dirent_read_target(struct btree_trans *trans, subvol_inum dir,
			    struct bkey_s_c_dirent d, subvol_inum *target)
222
{
223
	struct bch_subvolume s;
224 225
	int ret = 0;

226 227 228
	if (d.v->d_type == DT_SUBVOL &&
	    d.v->d_parent_subvol != dir.subvol)
		return 1;
229 230

	if (likely(d.v->d_type != DT_SUBVOL)) {
231 232
		target->subvol	= dir.subvol;
		target->inum	= le64_to_cpu(d.v->d_inum);
233
	} else {
234
		target->subvol	= le32_to_cpu(d.v->d_child_subvol);
235

236
		ret = bch2_subvolume_get(trans, target->subvol, true, BTREE_ITER_CACHED, &s);
237

238
		target->inum	= le64_to_cpu(s.inode);
239 240 241 242 243
	}

	return ret;
}

244
int bch2_dirent_rename(struct btree_trans *trans,
245 246 247 248 249
		subvol_inum src_dir, struct bch_hash_info *src_hash,
		subvol_inum dst_dir, struct bch_hash_info *dst_hash,
		const struct qstr *src_name, subvol_inum *src_inum, u64 *src_offset,
		const struct qstr *dst_name, subvol_inum *dst_inum, u64 *dst_offset,
		enum bch_rename_mode mode)
250
{
Kent Overstreet's avatar
Kent Overstreet committed
251 252
	struct btree_iter src_iter = { NULL };
	struct btree_iter dst_iter = { NULL };
253
	struct bkey_s_c old_src, old_dst = bkey_s_c_null;
254
	struct bkey_i_dirent *new_src = NULL, *new_dst = NULL;
255
	struct bpos dst_pos =
256
		POS(dst_dir.inum, bch2_dirent_hash(dst_hash, dst_name));
257
	unsigned src_type = 0, dst_type = 0, src_update_flags = 0;
258
	int ret = 0;
259

260 261 262 263 264
	if (src_dir.subvol != dst_dir.subvol)
		return -EXDEV;

	memset(src_inum, 0, sizeof(*src_inum));
	memset(dst_inum, 0, sizeof(*dst_inum));
265

266
	/* Lookup src: */
Kent Overstreet's avatar
Kent Overstreet committed
267 268 269
	ret = bch2_hash_lookup(trans, &src_iter, bch2_dirent_hash_desc,
			       src_hash, src_dir, src_name,
			       BTREE_ITER_INTENT);
270 271 272
	if (ret)
		goto out;

Kent Overstreet's avatar
Kent Overstreet committed
273
	old_src = bch2_btree_iter_peek_slot(&src_iter);
274 275 276 277
	ret = bkey_err(old_src);
	if (ret)
		goto out;

278 279 280 281
	ret = bch2_dirent_read_target(trans, src_dir,
			bkey_s_c_to_dirent(old_src), src_inum);
	if (ret)
		goto out;
282

283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325
	src_type = bkey_s_c_to_dirent(old_src).v->d_type;

	if (src_type == DT_SUBVOL && mode == BCH_RENAME_EXCHANGE)
		return -EOPNOTSUPP;


	/* Lookup dst: */
	if (mode == BCH_RENAME) {
		/*
		 * Note that we're _not_ checking if the target already exists -
		 * we're relying on the VFS to do that check for us for
		 * correctness:
		 */
		ret = bch2_hash_hole(trans, &dst_iter, bch2_dirent_hash_desc,
				     dst_hash, dst_dir, dst_name);
		if (ret)
			goto out;
	} else {
		ret = bch2_hash_lookup(trans, &dst_iter, bch2_dirent_hash_desc,
				       dst_hash, dst_dir, dst_name,
				       BTREE_ITER_INTENT);
		if (ret)
			goto out;

		old_dst = bch2_btree_iter_peek_slot(&dst_iter);
		ret = bkey_err(old_dst);
		if (ret)
			goto out;

		ret = bch2_dirent_read_target(trans, dst_dir,
				bkey_s_c_to_dirent(old_dst), dst_inum);
		if (ret)
			goto out;

		dst_type = bkey_s_c_to_dirent(old_dst).v->d_type;

		if (dst_type == DT_SUBVOL)
			return -EOPNOTSUPP;
	}

	if (mode != BCH_RENAME_EXCHANGE)
		*src_offset = dst_iter.pos.offset;

326
	/* Create new dst key: */
327
	new_dst = dirent_create_key(trans, dst_dir, 0, dst_name, 0);
328 329 330
	ret = PTR_ERR_OR_ZERO(new_dst);
	if (ret)
		goto out;
331 332

	dirent_copy_target(new_dst, bkey_s_c_to_dirent(old_src));
Kent Overstreet's avatar
Kent Overstreet committed
333
	new_dst->k.p = dst_iter.pos;
334 335 336

	/* Create new src key: */
	if (mode == BCH_RENAME_EXCHANGE) {
337
		new_src = dirent_create_key(trans, src_dir, 0, src_name, 0);
338 339 340
		ret = PTR_ERR_OR_ZERO(new_src);
		if (ret)
			goto out;
341 342

		dirent_copy_target(new_src, bkey_s_c_to_dirent(old_dst));
Kent Overstreet's avatar
Kent Overstreet committed
343
		new_src->k.p = src_iter.pos;
344 345
	} else {
		new_src = bch2_trans_kmalloc(trans, sizeof(struct bkey_i));
346 347 348 349
		ret = PTR_ERR_OR_ZERO(new_src);
		if (ret)
			goto out;

350
		bkey_init(&new_src->k);
Kent Overstreet's avatar
Kent Overstreet committed
351
		new_src->k.p = src_iter.pos;
352

353 354
		if (bkey_le(dst_pos, src_iter.pos) &&
		    bkey_lt(src_iter.pos, dst_iter.pos)) {
355 356 357 358 359 360 361 362 363 364 365 366
			/*
			 * We have a hash collision for the new dst key,
			 * and new_src - the key we're deleting - is between
			 * new_dst's hashed slot and the slot we're going to be
			 * inserting it into - oops.  This will break the hash
			 * table if we don't deal with it:
			 */
			if (mode == BCH_RENAME) {
				/*
				 * If we're not overwriting, we can just insert
				 * new_dst at the src position:
				 */
367 368 369
				new_src = new_dst;
				new_src->k.p = src_iter.pos;
				goto out_set_src;
370 371 372 373 374 375
			} else {
				/* If we're overwriting, we can't insert new_dst
				 * at a different slot because it has to
				 * overwrite old_dst - just make sure to use a
				 * whiteout when deleting src:
				 */
376
				new_src->k.type = KEY_TYPE_hash_whiteout;
377 378 379 380
			}
		} else {
			/* Check if we need a whiteout to delete src: */
			ret = bch2_hash_needs_whiteout(trans, bch2_dirent_hash_desc,
Kent Overstreet's avatar
Kent Overstreet committed
381
						       src_hash, &src_iter);
382
			if (ret < 0)
383
				goto out;
384 385

			if (ret)
386
				new_src->k.type = KEY_TYPE_hash_whiteout;
387 388 389
		}
	}

390 391 392
	ret = bch2_trans_update(trans, &dst_iter, &new_dst->k_i, 0);
	if (ret)
		goto out;
393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408
out_set_src:

	/*
	 * If we're deleting a subvolume, we need to really delete the dirent,
	 * not just emit a whiteout in the current snapshot:
	 */
	if (src_type == DT_SUBVOL) {
		bch2_btree_iter_set_snapshot(&src_iter, old_src.k->p.snapshot);
		ret = bch2_btree_iter_traverse(&src_iter);
		if (ret)
			goto out;

		new_src->k.p = src_iter.pos;
		src_update_flags |= BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE;
	}

409 410 411
	ret = bch2_trans_update(trans, &src_iter, &new_src->k_i, src_update_flags);
	if (ret)
		goto out;
412

413 414
	if (mode == BCH_RENAME_EXCHANGE)
		*src_offset = new_src->k.p.offset;
415
	*dst_offset = new_dst->k.p.offset;
416
out:
Kent Overstreet's avatar
Kent Overstreet committed
417 418
	bch2_trans_iter_exit(trans, &src_iter);
	bch2_trans_iter_exit(trans, &dst_iter);
419
	return ret;
420 421
}

Kent Overstreet's avatar
Kent Overstreet committed
422 423
int __bch2_dirent_lookup_trans(struct btree_trans *trans,
			       struct btree_iter *iter,
424
			       subvol_inum dir,
Kent Overstreet's avatar
Kent Overstreet committed
425
			       const struct bch_hash_info *hash_info,
426
			       const struct qstr *name, subvol_inum *inum,
427
			       unsigned flags)
428
{
429 430
	struct bkey_s_c k;
	struct bkey_s_c_dirent d;
431
	u32 snapshot;
432 433
	int ret;

434 435 436 437
	ret = bch2_subvolume_get_snapshot(trans, dir.subvol, &snapshot);
	if (ret)
		return ret;

438
	ret = bch2_hash_lookup(trans, iter, bch2_dirent_hash_desc,
439
			       hash_info, dir, name, flags);
440 441 442 443 444
	if (ret)
		return ret;

	k = bch2_btree_iter_peek_slot(iter);
	ret = bkey_err(k);
445 446
	if (ret)
		goto err;
447 448 449

	d = bkey_s_c_to_dirent(k);

450
	ret = bch2_dirent_read_target(trans, dir, d, inum);
451 452
	if (ret > 0)
		ret = -ENOENT;
453
err:
454 455 456 457
	if (ret)
		bch2_trans_iter_exit(trans, iter);

	return ret;
458 459
}

460
u64 bch2_dirent_lookup(struct bch_fs *c, subvol_inum dir,
461
		       const struct bch_hash_info *hash_info,
462
		       const struct qstr *name, subvol_inum *inum)
463 464
{
	struct btree_trans trans;
Kent Overstreet's avatar
Kent Overstreet committed
465
	struct btree_iter iter;
466
	int ret;
467

468
	bch2_trans_init(&trans, c, 0, 0);
469 470
retry:
	bch2_trans_begin(&trans);
471 472 473

	ret = __bch2_dirent_lookup_trans(&trans, &iter, dir, hash_info,
					  name, inum, 0);
474
	if (bch2_err_matches(ret, BCH_ERR_transaction_restart))
475
		goto retry;
476 477
	if (!ret)
		bch2_trans_iter_exit(&trans, &iter);
478
	bch2_trans_exit(&trans);
479
	return ret;
480 481
}

482
int bch2_empty_dir_trans(struct btree_trans *trans, subvol_inum dir)
483
{
Kent Overstreet's avatar
Kent Overstreet committed
484
	struct btree_iter iter;
485
	struct bkey_s_c k;
486
	u32 snapshot;
487
	int ret;
488

489 490 491 492
	ret = bch2_subvolume_get_snapshot(trans, dir.subvol, &snapshot);
	if (ret)
		return ret;

493 494 495
	for_each_btree_key_upto_norestart(trans, iter, BTREE_ID_dirents,
			   SPOS(dir.inum, 0, snapshot),
			   POS(dir.inum, U64_MAX), 0, k, ret)
496
		if (k.k->type == KEY_TYPE_dirent) {
497 498 499
			ret = -ENOTEMPTY;
			break;
		}
Kent Overstreet's avatar
Kent Overstreet committed
500
	bch2_trans_iter_exit(trans, &iter);
501 502 503 504

	return ret;
}

505
int bch2_readdir(struct bch_fs *c, subvol_inum inum, struct dir_context *ctx)
506
{
507
	struct btree_trans trans;
Kent Overstreet's avatar
Kent Overstreet committed
508
	struct btree_iter iter;
509 510
	struct bkey_s_c k;
	struct bkey_s_c_dirent dirent;
511
	subvol_inum target;
512
	u32 snapshot;
513
	int ret;
514

515
	bch2_trans_init(&trans, c, 0, 0);
516 517 518 519 520 521
retry:
	bch2_trans_begin(&trans);

	ret = bch2_subvolume_get_snapshot(&trans, inum.subvol, &snapshot);
	if (ret)
		goto err;
522

523 524 525
	for_each_btree_key_upto_norestart(&trans, iter, BTREE_ID_dirents,
			   SPOS(inum.inum, ctx->pos, snapshot),
			   POS(inum.inum, U64_MAX), 0, k, ret) {
526
		if (k.k->type != KEY_TYPE_dirent)
527 528 529 530
			continue;

		dirent = bkey_s_c_to_dirent(k);

531 532 533 534 535 536
		ret = bch2_dirent_read_target(&trans, inum, dirent, &target);
		if (ret < 0)
			break;
		if (ret)
			continue;

537 538 539 540
		/*
		 * XXX: dir_emit() can fault and block, while we're holding
		 * locks
		 */
541 542 543
		ctx->pos = dirent.k->p.offset;
		if (!dir_emit(ctx, dirent.v->d_name,
			      bch2_dirent_name_bytes(dirent),
544
			      target.inum,
545
			      vfs_d_type(dirent.v->d_type)))
546
			break;
547
		ctx->pos = dirent.k->p.offset + 1;
548 549 550 551 552

		/*
		 * read_target looks up subvolumes, we can overflow paths if the
		 * directory has many subvolumes in it
		 */
553 554
		ret = btree_trans_too_many_iters(&trans);
		if (ret)
555
			break;
556
	}
Kent Overstreet's avatar
Kent Overstreet committed
557
	bch2_trans_iter_exit(&trans, &iter);
558
err:
559
	if (bch2_err_matches(ret, BCH_ERR_transaction_restart))
560
		goto retry;
561

562
	bch2_trans_exit(&trans);
563

564
	return ret;
565
}