delayed-refs-tests.c

   1// SPDX-License-Identifier: GPL-2.0
   2#include <linux/sizes.h>
   3#include "btrfs-tests.h"
   4#include "../transaction.h"
   5#include "../delayed-ref.h"
   6#include "../extent-tree.h"
   7
   8#define FAKE_ROOT_OBJECTID 256
   9#define FAKE_BYTENR 0
  10#define FAKE_LEVEL 1
  11#define FAKE_INO 256
  12#define FAKE_FILE_OFFSET 0
  13#define FAKE_PARENT SZ_1M
  14
  15struct ref_head_check {
  16	u64 bytenr;
  17	u64 num_bytes;
  18	int ref_mod;
  19	int total_ref_mod;
  20	int must_insert;
  21};
  22
  23struct ref_node_check {
  24	u64 bytenr;
  25	u64 num_bytes;
  26	int ref_mod;
  27	enum btrfs_delayed_ref_action action;
  28	u8 type;
  29	u64 parent;
  30	u64 root;
  31	u64 owner;
  32	u64 offset;
  33};
  34
  35static enum btrfs_ref_type ref_type_from_disk_ref_type(u8 type)
  36{
  37	if ((type == BTRFS_TREE_BLOCK_REF_KEY) ||
  38	    (type == BTRFS_SHARED_BLOCK_REF_KEY))
  39		return BTRFS_REF_METADATA;
  40	return BTRFS_REF_DATA;
  41}
  42
  43static void delete_delayed_ref_head(struct btrfs_trans_handle *trans,
  44				    struct btrfs_delayed_ref_head *head)
  45{
  46	struct btrfs_fs_info *fs_info = trans->fs_info;
  47	struct btrfs_delayed_ref_root *delayed_refs =
  48		&trans->transaction->delayed_refs;
  49
  50	spin_lock(&delayed_refs->lock);
  51	spin_lock(&head->lock);
  52	btrfs_delete_ref_head(fs_info, delayed_refs, head);
  53	spin_unlock(&head->lock);
  54	spin_unlock(&delayed_refs->lock);
  55
  56	btrfs_delayed_ref_unlock(head);
  57	btrfs_put_delayed_ref_head(head);
  58}
  59
  60static void delete_delayed_ref_node(struct btrfs_delayed_ref_head *head,
  61				    struct btrfs_delayed_ref_node *node)
  62{
  63	rb_erase_cached(&node->ref_node, &head->ref_tree);
  64	RB_CLEAR_NODE(&node->ref_node);
  65	if (!list_empty(&node->add_list))
  66		list_del_init(&node->add_list);
  67	btrfs_put_delayed_ref(node);
  68}
  69
  70static int validate_ref_head(struct btrfs_delayed_ref_head *head,
  71			     struct ref_head_check *check)
  72{
  73	if (head->bytenr != check->bytenr) {
  74		test_err("invalid bytenr have: %llu want: %llu", head->bytenr,
  75			 check->bytenr);
  76		return -EINVAL;
  77	}
  78
  79	if (head->num_bytes != check->num_bytes) {
  80		test_err("invalid num_bytes have: %llu want: %llu",
  81			 head->num_bytes, check->num_bytes);
  82		return -EINVAL;
  83	}
  84
  85	if (head->ref_mod != check->ref_mod) {
  86		test_err("invalid ref_mod have: %d want: %d", head->ref_mod,
  87			 check->ref_mod);
  88		return -EINVAL;
  89	}
  90
  91	if (head->total_ref_mod != check->total_ref_mod) {
  92		test_err("invalid total_ref_mod have: %d want: %d",
  93			 head->total_ref_mod, check->total_ref_mod);
  94		return -EINVAL;
  95	}
  96
  97	if (head->must_insert_reserved != check->must_insert) {
  98		test_err("invalid must_insert have: %d want: %d",
  99			 head->must_insert_reserved, check->must_insert);
 100		return -EINVAL;
 101	}
 102
 103	return 0;
 104}
 105
 106static int validate_ref_node(struct btrfs_delayed_ref_node *node,
 107			     struct ref_node_check *check)
 108{
 109	if (node->bytenr != check->bytenr) {
 110		test_err("invalid bytenr have: %llu want: %llu", node->bytenr,
 111			 check->bytenr);
 112		return -EINVAL;
 113	}
 114
 115	if (node->num_bytes != check->num_bytes) {
 116		test_err("invalid num_bytes have: %llu want: %llu",
 117			 node->num_bytes, check->num_bytes);
 118		return -EINVAL;
 119	}
 120
 121	if (node->ref_mod != check->ref_mod) {
 122		test_err("invalid ref_mod have: %d want: %d", node->ref_mod,
 123			 check->ref_mod);
 124		return -EINVAL;
 125	}
 126
 127	if (node->action != check->action) {
 128		test_err("invalid action have: %d want: %d", node->action,
 129			 check->action);
 130		return -EINVAL;
 131	}
 132
 133	if (node->parent != check->parent) {
 134		test_err("invalid parent have: %llu want: %llu", node->parent,
 135			 check->parent);
 136		return -EINVAL;
 137	}
 138
 139	if (node->ref_root != check->root) {
 140		test_err("invalid root have: %llu want: %llu", node->ref_root,
 141			 check->root);
 142		return -EINVAL;
 143	}
 144
 145	if (node->type != check->type) {
 146		test_err("invalid type have: %d want: %d", node->type,
 147			 check->type);
 148		return -EINVAL;
 149	}
 150
 151	if (btrfs_delayed_ref_owner(node) != check->owner) {
 152		test_err("invalid owner have: %llu want: %llu",
 153			 btrfs_delayed_ref_owner(node), check->owner);
 154		return -EINVAL;
 155	}
 156
 157	if (btrfs_delayed_ref_offset(node) != check->offset) {
 158		test_err("invalid offset have: %llu want: %llu",
 159			 btrfs_delayed_ref_offset(node), check->offset);
 160		return -EINVAL;
 161	}
 162
 163	return 0;
 164}
 165
 166static int simple_test(struct btrfs_trans_handle *trans,
 167		       struct ref_head_check *head_check,
 168		       struct ref_node_check *node_check)
 169{
 170	struct btrfs_delayed_ref_root *delayed_refs =
 171		&trans->transaction->delayed_refs;
 172	struct btrfs_fs_info *fs_info = trans->fs_info;
 173	struct btrfs_delayed_ref_head *head;
 174	struct btrfs_delayed_ref_node *node;
 175	struct btrfs_ref ref = {
 176		.type = ref_type_from_disk_ref_type(node_check->type),
 177		.action = node_check->action,
 178		.parent = node_check->parent,
 179		.ref_root = node_check->root,
 180		.bytenr = node_check->bytenr,
 181		.num_bytes = fs_info->nodesize,
 182	};
 183	int ret;
 184
 185	if (ref.type == BTRFS_REF_METADATA)
 186		btrfs_init_tree_ref(&ref, node_check->owner, node_check->root,
 187				    false);
 188	else
 189		btrfs_init_data_ref(&ref, node_check->owner, node_check->offset,
 190				    node_check->root, true);
 191
 192	if (ref.type == BTRFS_REF_METADATA)
 193		ret = btrfs_add_delayed_tree_ref(trans, &ref, NULL);
 194	else
 195		ret = btrfs_add_delayed_data_ref(trans, &ref, 0);
 196	if (ret) {
 197		test_err("failed ref action %d", ret);
 198		return ret;
 199	}
 200
 201	head = btrfs_select_ref_head(fs_info, delayed_refs);
 202	if (IS_ERR_OR_NULL(head)) {
 203		if (IS_ERR(head))
 204			test_err("failed to select delayed ref head: %ld",
 205				 PTR_ERR(head));
 206		else
 207			test_err("failed to find delayed ref head");
 208		return -EINVAL;
 209	}
 210
 211	ret = -EINVAL;
 212	if (validate_ref_head(head, head_check))
 213		goto out;
 214
 215	spin_lock(&head->lock);
 216	node = btrfs_select_delayed_ref(head);
 217	spin_unlock(&head->lock);
 218	if (!node) {
 219		test_err("failed to select delayed ref");
 220		goto out;
 221	}
 222
 223	if (validate_ref_node(node, node_check))
 224		goto out;
 225	ret = 0;
 226out:
 227	btrfs_unselect_ref_head(delayed_refs, head);
 228	btrfs_destroy_delayed_refs(trans->transaction);
 229	return ret;
 230}
 231
 232/*
 233 * These are simple tests, make sure that our btrfs_ref's get turned into the
 234 * appropriate btrfs_delayed_ref_node based on their settings and action.
 235 */
 236static int simple_tests(struct btrfs_trans_handle *trans)
 237{
 238	struct btrfs_fs_info *fs_info = trans->fs_info;
 239	struct ref_head_check head_check = {
 240		.bytenr = FAKE_BYTENR,
 241		.num_bytes = fs_info->nodesize,
 242		.ref_mod = 1,
 243		.total_ref_mod = 1,
 244	};
 245	struct ref_node_check node_check = {
 246		.bytenr = FAKE_BYTENR,
 247		.num_bytes = fs_info->nodesize,
 248		.ref_mod = 1,
 249		.action = BTRFS_ADD_DELAYED_REF,
 250		.type = BTRFS_TREE_BLOCK_REF_KEY,
 251		.parent = 0,
 252		.root = FAKE_ROOT_OBJECTID,
 253		.owner = FAKE_LEVEL,
 254		.offset = 0,
 255	};
 256
 257	if (simple_test(trans, &head_check, &node_check)) {
 258		test_err("single add tree block failed");
 259		return -EINVAL;
 260	}
 261
 262	node_check.type = BTRFS_EXTENT_DATA_REF_KEY;
 263	node_check.owner = FAKE_INO;
 264	node_check.offset = FAKE_FILE_OFFSET;
 265
 266	if (simple_test(trans, &head_check, &node_check)) {
 267		test_err("single add extent data failed");
 268		return -EINVAL;
 269	}
 270
 271	node_check.parent = FAKE_PARENT;
 272	node_check.type = BTRFS_SHARED_BLOCK_REF_KEY;
 273	node_check.owner = FAKE_LEVEL;
 274	node_check.offset = 0;
 275
 276	if (simple_test(trans, &head_check, &node_check)) {
 277		test_err("single add shared block failed");
 278		return -EINVAL;
 279	}
 280
 281	node_check.type = BTRFS_SHARED_DATA_REF_KEY;
 282	node_check.owner = FAKE_INO;
 283	node_check.offset = FAKE_FILE_OFFSET;
 284
 285	if (simple_test(trans, &head_check, &node_check)) {
 286		test_err("single add shared data failed");
 287		return -EINVAL;
 288	}
 289
 290	head_check.ref_mod = -1;
 291	head_check.total_ref_mod = -1;
 292	node_check.action = BTRFS_DROP_DELAYED_REF;
 293	node_check.type = BTRFS_TREE_BLOCK_REF_KEY;
 294	node_check.owner = FAKE_LEVEL;
 295	node_check.offset = 0;
 296	node_check.parent = 0;
 297
 298	if (simple_test(trans, &head_check, &node_check)) {
 299		test_err("single drop tree block failed");
 300		return -EINVAL;
 301	}
 302
 303	node_check.type = BTRFS_EXTENT_DATA_REF_KEY;
 304	node_check.owner = FAKE_INO;
 305	node_check.offset = FAKE_FILE_OFFSET;
 306
 307	if (simple_test(trans, &head_check, &node_check)) {
 308		test_err("single drop extent data failed");
 309		return -EINVAL;
 310	}
 311
 312	node_check.parent = FAKE_PARENT;
 313	node_check.type = BTRFS_SHARED_BLOCK_REF_KEY;
 314	node_check.owner = FAKE_LEVEL;
 315	node_check.offset = 0;
 316	if (simple_test(trans, &head_check, &node_check)) {
 317		test_err("single drop shared block failed");
 318		return -EINVAL;
 319	}
 320
 321	node_check.type = BTRFS_SHARED_DATA_REF_KEY;
 322	node_check.owner = FAKE_INO;
 323	node_check.offset = FAKE_FILE_OFFSET;
 324	if (simple_test(trans, &head_check, &node_check)) {
 325		test_err("single drop shared data failed");
 326		return -EINVAL;
 327	}
 328
 329	return 0;
 330}
 331
 332/*
 333 * Merge tests, validate that we do delayed ref merging properly, the ref counts
 334 * all end up properly, and delayed refs are deleted once they're no longer
 335 * needed.
 336 */
 337static int merge_tests(struct btrfs_trans_handle *trans,
 338		       enum btrfs_ref_type type)
 339{
 340	struct btrfs_fs_info *fs_info = trans->fs_info;
 341	struct btrfs_delayed_ref_head *head = NULL;
 342	struct btrfs_delayed_ref_node *node;
 343	struct btrfs_ref ref = {
 344		.type = type,
 345		.action = BTRFS_ADD_DELAYED_REF,
 346		.parent = 0,
 347		.ref_root = FAKE_ROOT_OBJECTID,
 348		.bytenr = FAKE_BYTENR,
 349		.num_bytes = fs_info->nodesize,
 350	};
 351	struct ref_head_check head_check = {
 352		.bytenr = FAKE_BYTENR,
 353		.num_bytes = fs_info->nodesize,
 354		.ref_mod = 0,
 355		.total_ref_mod = 0,
 356	};
 357	struct ref_node_check node_check = {
 358		.bytenr = FAKE_BYTENR,
 359		.num_bytes = fs_info->nodesize,
 360		.ref_mod = 2,
 361		.action = BTRFS_ADD_DELAYED_REF,
 362		.parent = 0,
 363		.root = FAKE_ROOT_OBJECTID,
 364	};
 365	int ret;
 366
 367	/*
 368	 * First add a ref and then drop it, make sure we get a head ref with a
 369	 * 0 total ref mod and no nodes.
 370	 */
 371	if (type == BTRFS_REF_METADATA) {
 372		node_check.type = BTRFS_TREE_BLOCK_REF_KEY;
 373		node_check.owner = FAKE_LEVEL;
 374		btrfs_init_tree_ref(&ref, FAKE_LEVEL, FAKE_ROOT_OBJECTID, false);
 375	} else {
 376		node_check.type = BTRFS_EXTENT_DATA_REF_KEY;
 377		node_check.owner = FAKE_INO;
 378		node_check.offset = FAKE_FILE_OFFSET;
 379		btrfs_init_data_ref(&ref, FAKE_INO, FAKE_FILE_OFFSET,
 380				    FAKE_ROOT_OBJECTID, true);
 381	}
 382
 383	if (type == BTRFS_REF_METADATA)
 384		ret = btrfs_add_delayed_tree_ref(trans, &ref, NULL);
 385	else
 386		ret = btrfs_add_delayed_data_ref(trans, &ref, 0);
 387	if (ret) {
 388		test_err("failed ref action %d", ret);
 389		return ret;
 390	}
 391
 392	ref.action = BTRFS_DROP_DELAYED_REF;
 393	if (type == BTRFS_REF_METADATA)
 394		ret = btrfs_add_delayed_tree_ref(trans, &ref, NULL);
 395	else
 396		ret = btrfs_add_delayed_data_ref(trans, &ref, 0);
 397	if (ret) {
 398		test_err("failed ref action %d", ret);
 399		goto out;
 400	}
 401
 402	head = btrfs_select_ref_head(fs_info, &trans->transaction->delayed_refs);
 403	if (IS_ERR_OR_NULL(head)) {
 404		if (IS_ERR(head))
 405			test_err("failed to select delayed ref head: %ld",
 406				 PTR_ERR(head));
 407		else
 408			test_err("failed to find delayed ref head");
 409		goto out;
 410	}
 411
 412	ret = -EINVAL;
 413	if (validate_ref_head(head, &head_check)) {
 414		test_err("single add and drop failed");
 415		goto out;
 416	}
 417
 418	spin_lock(&head->lock);
 419	node = btrfs_select_delayed_ref(head);
 420	spin_unlock(&head->lock);
 421	if (node) {
 422		test_err("found node when none should exist");
 423		goto out;
 424	}
 425
 426	delete_delayed_ref_head(trans, head);
 427	head = NULL;
 428
 429	/*
 430	 * Add a ref, then add another ref, make sure we get a head ref with a
 431	 * 2 total ref mod and 1 node.
 432	 */
 433	ref.action = BTRFS_ADD_DELAYED_REF;
 434	if (type == BTRFS_REF_METADATA)
 435		ret = btrfs_add_delayed_tree_ref(trans, &ref, NULL);
 436	else
 437		ret = btrfs_add_delayed_data_ref(trans, &ref, 0);
 438	if (ret) {
 439		test_err("failed ref action %d", ret);
 440		goto out;
 441	}
 442
 443	if (type == BTRFS_REF_METADATA)
 444		ret = btrfs_add_delayed_tree_ref(trans, &ref, NULL);
 445	else
 446		ret = btrfs_add_delayed_data_ref(trans, &ref, 0);
 447	if (ret) {
 448		test_err("failed ref action %d", ret);
 449		goto out;
 450	}
 451
 452	head = btrfs_select_ref_head(fs_info, &trans->transaction->delayed_refs);
 453	if (IS_ERR_OR_NULL(head)) {
 454		if (IS_ERR(head))
 455			test_err("failed to select delayed ref head: %ld",
 456				 PTR_ERR(head));
 457		else
 458			test_err("failed to find delayed ref head");
 459		goto out;
 460	}
 461
 462	head_check.ref_mod = 2;
 463	head_check.total_ref_mod = 2;
 464	ret = -EINVAL;
 465	if (validate_ref_head(head, &head_check)) {
 466		test_err("double add failed");
 467		goto out;
 468	}
 469
 470	spin_lock(&head->lock);
 471	node = btrfs_select_delayed_ref(head);
 472	spin_unlock(&head->lock);
 473	if (!node) {
 474		test_err("failed to select delayed ref");
 475		goto out;
 476	}
 477
 478	if (validate_ref_node(node, &node_check)) {
 479		test_err("node check failed");
 480		goto out;
 481	}
 482
 483	delete_delayed_ref_node(head, node);
 484
 485	spin_lock(&head->lock);
 486	node = btrfs_select_delayed_ref(head);
 487	spin_unlock(&head->lock);
 488	if (node) {
 489		test_err("found node when none should exist");
 490		goto out;
 491	}
 492	delete_delayed_ref_head(trans, head);
 493	head = NULL;
 494
 495	/* Add two drop refs, make sure they are merged properly. */
 496	ref.action = BTRFS_DROP_DELAYED_REF;
 497	if (type == BTRFS_REF_METADATA)
 498		ret = btrfs_add_delayed_tree_ref(trans, &ref, NULL);
 499	else
 500		ret = btrfs_add_delayed_data_ref(trans, &ref, 0);
 501	if (ret) {
 502		test_err("failed ref action %d", ret);
 503		goto out;
 504	}
 505
 506	if (type == BTRFS_REF_METADATA)
 507		ret = btrfs_add_delayed_tree_ref(trans, &ref, NULL);
 508	else
 509		ret = btrfs_add_delayed_data_ref(trans, &ref, 0);
 510	if (ret) {
 511		test_err("failed ref action %d", ret);
 512		goto out;
 513	}
 514
 515	head = btrfs_select_ref_head(fs_info, &trans->transaction->delayed_refs);
 516	if (IS_ERR_OR_NULL(head)) {
 517		if (IS_ERR(head))
 518			test_err("failed to select delayed ref head: %ld",
 519				 PTR_ERR(head));
 520		else
 521			test_err("failed to find delayed ref head");
 522		goto out;
 523	}
 524
 525	head_check.ref_mod = -2;
 526	head_check.total_ref_mod = -2;
 527	ret = -EINVAL;
 528	if (validate_ref_head(head, &head_check)) {
 529		test_err("double drop failed");
 530		goto out;
 531	}
 532
 533	node_check.action = BTRFS_DROP_DELAYED_REF;
 534	spin_lock(&head->lock);
 535	node = btrfs_select_delayed_ref(head);
 536	spin_unlock(&head->lock);
 537	if (!node) {
 538		test_err("failed to select delayed ref");
 539		goto out;
 540	}
 541
 542	if (validate_ref_node(node, &node_check)) {
 543		test_err("node check failed");
 544		goto out;
 545	}
 546
 547	delete_delayed_ref_node(head, node);
 548
 549	spin_lock(&head->lock);
 550	node = btrfs_select_delayed_ref(head);
 551	spin_unlock(&head->lock);
 552	if (node) {
 553		test_err("found node when none should exist");
 554		goto out;
 555	}
 556	delete_delayed_ref_head(trans, head);
 557	head = NULL;
 558
 559	/* Add multiple refs, then drop until we go negative again. */
 560	ref.action = BTRFS_ADD_DELAYED_REF;
 561	for (int i = 0; i < 10; i++) {
 562		if (type == BTRFS_REF_METADATA)
 563			ret = btrfs_add_delayed_tree_ref(trans, &ref, NULL);
 564		else
 565			ret = btrfs_add_delayed_data_ref(trans, &ref, 0);
 566		if (ret) {
 567			test_err("failed ref action %d", ret);
 568			goto out;
 569		}
 570	}
 571
 572	ref.action = BTRFS_DROP_DELAYED_REF;
 573	for (int i = 0; i < 12; i++) {
 574		if (type == BTRFS_REF_METADATA)
 575			ret = btrfs_add_delayed_tree_ref(trans, &ref, NULL);
 576		else
 577			ret = btrfs_add_delayed_data_ref(trans, &ref, 0);
 578		if (ret) {
 579			test_err("failed ref action %d", ret);
 580			goto out;
 581		}
 582	}
 583
 584	head = btrfs_select_ref_head(fs_info, &trans->transaction->delayed_refs);
 585	if (IS_ERR_OR_NULL(head)) {
 586		if (IS_ERR(head))
 587			test_err("failed to select delayed ref head: %ld",
 588				 PTR_ERR(head));
 589		else
 590			test_err("failed to find delayed ref head");
 591		ret = -EINVAL;
 592		goto out;
 593	}
 594
 595	head_check.ref_mod = -2;
 596	head_check.total_ref_mod = -2;
 597	ret = -EINVAL;
 598	if (validate_ref_head(head, &head_check)) {
 599		test_err("double drop failed");
 600		goto out;
 601	}
 602
 603	spin_lock(&head->lock);
 604	node = btrfs_select_delayed_ref(head);
 605	spin_unlock(&head->lock);
 606	if (!node) {
 607		test_err("failed to select delayed ref");
 608		goto out;
 609	}
 610
 611	if (validate_ref_node(node, &node_check)) {
 612		test_err("node check failed");
 613		goto out;
 614	}
 615
 616	delete_delayed_ref_node(head, node);
 617
 618	spin_lock(&head->lock);
 619	node = btrfs_select_delayed_ref(head);
 620	spin_unlock(&head->lock);
 621	if (node) {
 622		test_err("found node when none should exist");
 623		goto out;
 624	}
 625
 626	delete_delayed_ref_head(trans, head);
 627	head = NULL;
 628
 629	/* Drop multiple refs, then add until we go positive again. */
 630	ref.action = BTRFS_DROP_DELAYED_REF;
 631	for (int i = 0; i < 10; i++) {
 632		if (type == BTRFS_REF_METADATA)
 633			ret = btrfs_add_delayed_tree_ref(trans, &ref, NULL);
 634		else
 635			ret = btrfs_add_delayed_data_ref(trans, &ref, 0);
 636		if (ret) {
 637			test_err("failed ref action %d", ret);
 638			goto out;
 639		}
 640	}
 641
 642	ref.action = BTRFS_ADD_DELAYED_REF;
 643	for (int i = 0; i < 12; i++) {
 644		if (type == BTRFS_REF_METADATA)
 645			ret = btrfs_add_delayed_tree_ref(trans, &ref, NULL);
 646		else
 647			ret = btrfs_add_delayed_data_ref(trans, &ref, 0);
 648		if (ret) {
 649			test_err("failed ref action %d", ret);
 650			goto out;
 651		}
 652	}
 653
 654	head = btrfs_select_ref_head(fs_info, &trans->transaction->delayed_refs);
 655	if (IS_ERR_OR_NULL(head)) {
 656		if (IS_ERR(head))
 657			test_err("failed to select delayed ref head: %ld",
 658				 PTR_ERR(head));
 659		else
 660			test_err("failed to find delayed ref head");
 661		ret = -EINVAL;
 662		goto out;
 663	}
 664
 665	head_check.ref_mod = 2;
 666	head_check.total_ref_mod = 2;
 667	ret = -EINVAL;
 668	if (validate_ref_head(head, &head_check)) {
 669		test_err("add and drop to positive failed");
 670		goto out;
 671	}
 672
 673	node_check.action = BTRFS_ADD_DELAYED_REF;
 674	spin_lock(&head->lock);
 675	node = btrfs_select_delayed_ref(head);
 676	spin_unlock(&head->lock);
 677	if (!node) {
 678		test_err("failed to select delayed ref");
 679		goto out;
 680	}
 681
 682	if (validate_ref_node(node, &node_check)) {
 683		test_err("node check failed");
 684		goto out;
 685	}
 686
 687	delete_delayed_ref_node(head, node);
 688
 689	spin_lock(&head->lock);
 690	node = btrfs_select_delayed_ref(head);
 691	spin_unlock(&head->lock);
 692	if (node) {
 693		test_err("found node when none should exist");
 694		goto out;
 695	}
 696	delete_delayed_ref_head(trans, head);
 697	head = NULL;
 698
 699	/*
 700	 * Add a bunch of refs with different roots and parents, then drop them
 701	 * all, make sure everything is properly merged.
 702	 */
 703	ref.action = BTRFS_ADD_DELAYED_REF;
 704	for (int i = 0; i < 50; i++) {
 705		if (!(i % 2)) {
 706			ref.parent = 0;
 707			ref.ref_root = FAKE_ROOT_OBJECTID + i;
 708		} else {
 709			ref.parent = FAKE_PARENT + (i * fs_info->nodesize);
 710		}
 711		if (type == BTRFS_REF_METADATA)
 712			ret = btrfs_add_delayed_tree_ref(trans, &ref, NULL);
 713		else
 714			ret = btrfs_add_delayed_data_ref(trans, &ref, 0);
 715		if (ret) {
 716			test_err("failed ref action %d", ret);
 717			goto out;
 718		}
 719	}
 720
 721	ref.action = BTRFS_DROP_DELAYED_REF;
 722	for (int i = 0; i < 50; i++) {
 723		if (!(i % 2)) {
 724			ref.parent = 0;
 725			ref.ref_root = FAKE_ROOT_OBJECTID + i;
 726		} else {
 727			ref.parent = FAKE_PARENT + (i * fs_info->nodesize);
 728		}
 729		if (type == BTRFS_REF_METADATA)
 730			ret = btrfs_add_delayed_tree_ref(trans, &ref, NULL);
 731		else
 732			ret = btrfs_add_delayed_data_ref(trans, &ref, 0);
 733		if (ret) {
 734			test_err("failed ref action %d", ret);
 735			goto out;
 736		}
 737	}
 738
 739	head = btrfs_select_ref_head(fs_info, &trans->transaction->delayed_refs);
 740	if (IS_ERR_OR_NULL(head)) {
 741		if (IS_ERR(head))
 742			test_err("failed to select delayed ref head: %ld",
 743				 PTR_ERR(head));
 744		else
 745			test_err("failed to find delayed ref head");
 746		ret = -EINVAL;
 747		goto out;
 748	}
 749
 750	head_check.ref_mod = 0;
 751	head_check.total_ref_mod = 0;
 752	ret = -EINVAL;
 753	if (validate_ref_head(head, &head_check)) {
 754		test_err("add and drop multiple failed");
 755		goto out;
 756	}
 757
 758	spin_lock(&head->lock);
 759	node = btrfs_select_delayed_ref(head);
 760	spin_unlock(&head->lock);
 761	if (node) {
 762		test_err("found node when none should exist");
 763		goto out;
 764	}
 765	ret = 0;
 766out:
 767	if (!IS_ERR_OR_NULL(head))
 768		btrfs_unselect_ref_head(&trans->transaction->delayed_refs, head);
 769	btrfs_destroy_delayed_refs(trans->transaction);
 770	return ret;
 771}
 772
 773/*
 774 * Basic test to validate we always get the add operations first followed by any
 775 * delete operations.
 776 */
 777static int select_delayed_refs_test(struct btrfs_trans_handle *trans)
 778{
 779	struct btrfs_delayed_ref_root *delayed_refs =
 780		&trans->transaction->delayed_refs;
 781	struct btrfs_fs_info *fs_info = trans->fs_info;
 782	struct btrfs_delayed_ref_head *head = NULL;
 783	struct btrfs_delayed_ref_node *node;
 784	struct btrfs_ref ref = {
 785		.type = BTRFS_REF_METADATA,
 786		.action = BTRFS_DROP_DELAYED_REF,
 787		.parent = 0,
 788		.ref_root = FAKE_ROOT_OBJECTID,
 789		.bytenr = FAKE_BYTENR,
 790		.num_bytes = fs_info->nodesize,
 791	};
 792	struct ref_head_check head_check = {
 793		.bytenr = FAKE_BYTENR,
 794		.num_bytes = fs_info->nodesize,
 795		.ref_mod = 0,
 796		.total_ref_mod = 0,
 797	};
 798	struct ref_node_check node_check = {
 799		.bytenr = FAKE_BYTENR,
 800		.num_bytes = fs_info->nodesize,
 801		.ref_mod = 1,
 802		.action = BTRFS_ADD_DELAYED_REF,
 803		.type = BTRFS_TREE_BLOCK_REF_KEY,
 804		.parent = 0,
 805		.owner = FAKE_LEVEL,
 806		.offset = 0,
 807	};
 808	int ret;
 809
 810	/* Add the drop first. */
 811	btrfs_init_tree_ref(&ref, FAKE_LEVEL, FAKE_ROOT_OBJECTID, false);
 812	ret = btrfs_add_delayed_tree_ref(trans, &ref, NULL);
 813	if (ret) {
 814		test_err("failed ref action %d", ret);
 815		return ret;
 816	}
 817
 818	/*
 819	 * Now add the add, and make it a different root so it's logically later
 820	 * in the rb tree.
 821	 */
 822	ref.action = BTRFS_ADD_DELAYED_REF;
 823	ref.ref_root = FAKE_ROOT_OBJECTID + 1;
 824	ret = btrfs_add_delayed_tree_ref(trans, &ref, NULL);
 825	if (ret) {
 826		test_err("failed ref action %d", ret);
 827		goto out;
 828	}
 829
 830	head = btrfs_select_ref_head(fs_info, delayed_refs);
 831	if (IS_ERR_OR_NULL(head)) {
 832		if (IS_ERR(head))
 833			test_err("failed to select delayed ref head: %ld",
 834				 PTR_ERR(head));
 835		else
 836			test_err("failed to find delayed ref head");
 837		ret = -EINVAL;
 838		head = NULL;
 839		goto out;
 840	}
 841
 842	ret = -EINVAL;
 843	if (validate_ref_head(head, &head_check)) {
 844		test_err("head check failed");
 845		goto out;
 846	}
 847
 848	spin_lock(&head->lock);
 849	node = btrfs_select_delayed_ref(head);
 850	spin_unlock(&head->lock);
 851	if (!node) {
 852		test_err("failed to select delayed ref");
 853		goto out;
 854	}
 855
 856	node_check.root = FAKE_ROOT_OBJECTID + 1;
 857	if (validate_ref_node(node, &node_check)) {
 858		test_err("node check failed");
 859		goto out;
 860	}
 861	delete_delayed_ref_node(head, node);
 862
 863	spin_lock(&head->lock);
 864	node = btrfs_select_delayed_ref(head);
 865	spin_unlock(&head->lock);
 866	if (!node) {
 867		test_err("failed to select delayed ref");
 868		goto out;
 869	}
 870
 871	node_check.action = BTRFS_DROP_DELAYED_REF;
 872	node_check.root = FAKE_ROOT_OBJECTID;
 873	if (validate_ref_node(node, &node_check)) {
 874		test_err("node check failed");
 875		goto out;
 876	}
 877	delete_delayed_ref_node(head, node);
 878	delete_delayed_ref_head(trans, head);
 879	head = NULL;
 880
 881	/*
 882	 * Now we're going to do the same thing, but we're going to have an add
 883	 * that gets deleted because of a merge, and make sure we still have
 884	 * another add in place.
 885	 */
 886	ref.action = BTRFS_DROP_DELAYED_REF;
 887	ref.ref_root = FAKE_ROOT_OBJECTID;
 888	ret = btrfs_add_delayed_tree_ref(trans, &ref, NULL);
 889	if (ret) {
 890		test_err("failed ref action %d", ret);
 891		goto out;
 892	}
 893
 894	ref.action = BTRFS_ADD_DELAYED_REF;
 895	ref.ref_root = FAKE_ROOT_OBJECTID + 1;
 896	ret = btrfs_add_delayed_tree_ref(trans, &ref, NULL);
 897	if (ret) {
 898		test_err("failed ref action %d", ret);
 899		goto out;
 900	}
 901
 902	ref.action = BTRFS_DROP_DELAYED_REF;
 903	ret = btrfs_add_delayed_tree_ref(trans, &ref, NULL);
 904	if (ret) {
 905		test_err("failed ref action %d", ret);
 906		goto out;
 907	}
 908
 909	ref.action = BTRFS_ADD_DELAYED_REF;
 910	ref.ref_root = FAKE_ROOT_OBJECTID + 2;
 911	ret = btrfs_add_delayed_tree_ref(trans, &ref, NULL);
 912	if (ret) {
 913		test_err("failed ref action %d", ret);
 914		goto out;
 915	}
 916
 917	head = btrfs_select_ref_head(fs_info, delayed_refs);
 918	if (IS_ERR_OR_NULL(head)) {
 919		if (IS_ERR(head))
 920			test_err("failed to select delayed ref head: %ld",
 921				 PTR_ERR(head));
 922		else
 923			test_err("failed to find delayed ref head");
 924		ret = -EINVAL;
 925		head = NULL;
 926		goto out;
 927	}
 928
 929	ret = -EINVAL;
 930	if (validate_ref_head(head, &head_check)) {
 931		test_err("head check failed");
 932		goto out;
 933	}
 934
 935	spin_lock(&head->lock);
 936	node = btrfs_select_delayed_ref(head);
 937	spin_unlock(&head->lock);
 938	if (!node) {
 939		test_err("failed to select delayed ref");
 940		goto out;
 941	}
 942
 943	node_check.action = BTRFS_ADD_DELAYED_REF;
 944	node_check.root = FAKE_ROOT_OBJECTID + 2;
 945	if (validate_ref_node(node, &node_check)) {
 946		test_err("node check failed");
 947		goto out;
 948	}
 949	delete_delayed_ref_node(head, node);
 950
 951	spin_lock(&head->lock);
 952	node = btrfs_select_delayed_ref(head);
 953	spin_unlock(&head->lock);
 954	if (!node) {
 955		test_err("failed to select delayed ref");
 956		goto out;
 957	}
 958
 959	node_check.action = BTRFS_DROP_DELAYED_REF;
 960	node_check.root = FAKE_ROOT_OBJECTID;
 961	if (validate_ref_node(node, &node_check)) {
 962		test_err("node check failed");
 963		goto out;
 964	}
 965	delete_delayed_ref_node(head, node);
 966	ret = 0;
 967out:
 968	if (head)
 969		btrfs_unselect_ref_head(delayed_refs, head);
 970	btrfs_destroy_delayed_refs(trans->transaction);
 971	return ret;
 972}
 973
 974int btrfs_test_delayed_refs(u32 sectorsize, u32 nodesize)
 975{
 976	struct btrfs_transaction *transaction;
 977	struct btrfs_trans_handle trans;
 978	struct btrfs_fs_info *fs_info;
 979	int ret;
 980
 981	test_msg("running delayed refs tests");
 982
 983	fs_info = btrfs_alloc_dummy_fs_info(nodesize, sectorsize);
 984	if (!fs_info) {
 985		test_std_err(TEST_ALLOC_FS_INFO);
 986		return -ENOMEM;
 987	}
 988	transaction = kmalloc(sizeof(*transaction), GFP_KERNEL);
 989	if (!transaction) {
 990		test_std_err(TEST_ALLOC_TRANSACTION);
 991		ret = -ENOMEM;
 992		goto out_free_fs_info;
 993	}
 994	btrfs_init_dummy_trans(&trans, fs_info);
 995	btrfs_init_dummy_transaction(transaction, fs_info);
 996	trans.transaction = transaction;
 997
 998	ret = simple_tests(&trans);
 999	if (!ret) {
1000		test_msg("running delayed refs merge tests on metadata refs");
1001		ret = merge_tests(&trans, BTRFS_REF_METADATA);
1002	}
1003
1004	if (!ret) {
1005		test_msg("running delayed refs merge tests on data refs");
1006		ret = merge_tests(&trans, BTRFS_REF_DATA);
1007	}
1008
1009	if (!ret)
1010		ret = select_delayed_refs_test(&trans);
1011
1012	kfree(transaction);
1013out_free_fs_info:
1014	btrfs_free_dummy_fs_info(fs_info);
1015	return ret;
1016}