1 // SPDX-License-Identifier: GPL-2.0
2 #ifdef CONFIG_BCACHEFS_TESTS
5 #include "btree_update.h"
6 #include "journal_reclaim.h"
10 #include "linux/kthread.h"
11 #include "linux/random.h"
13 static void delete_test_keys(struct bch_fs *c)
17 ret = bch2_btree_delete_range(c, BTREE_ID_extents,
23 ret = bch2_btree_delete_range(c, BTREE_ID_xattrs,
32 static int test_delete(struct bch_fs *c, u64 nr)
34 struct btree_trans trans;
35 struct btree_iter iter;
36 struct bkey_i_cookie k;
39 bkey_cookie_init(&k.k_i);
40 k.k.p.snapshot = U32_MAX;
42 bch2_trans_init(&trans, c, 0, 0);
43 bch2_trans_iter_init(&trans, &iter, BTREE_ID_xattrs, k.k.p,
46 ret = commit_do(&trans, NULL, NULL, 0,
47 bch2_btree_iter_traverse(&iter) ?:
48 bch2_trans_update(&trans, &iter, &k.k_i, 0));
50 bch_err_msg(c, ret, "update error");
54 pr_info("deleting once");
55 ret = commit_do(&trans, NULL, NULL, 0,
56 bch2_btree_iter_traverse(&iter) ?:
57 bch2_btree_delete_at(&trans, &iter, 0));
59 bch_err_msg(c, ret, "delete error (first)");
63 pr_info("deleting twice");
64 ret = commit_do(&trans, NULL, NULL, 0,
65 bch2_btree_iter_traverse(&iter) ?:
66 bch2_btree_delete_at(&trans, &iter, 0));
68 bch_err_msg(c, ret, "delete error (second)");
72 bch2_trans_iter_exit(&trans, &iter);
73 bch2_trans_exit(&trans);
77 static int test_delete_written(struct bch_fs *c, u64 nr)
79 struct btree_trans trans;
80 struct btree_iter iter;
81 struct bkey_i_cookie k;
84 bkey_cookie_init(&k.k_i);
85 k.k.p.snapshot = U32_MAX;
87 bch2_trans_init(&trans, c, 0, 0);
89 bch2_trans_iter_init(&trans, &iter, BTREE_ID_xattrs, k.k.p,
92 ret = commit_do(&trans, NULL, NULL, 0,
93 bch2_btree_iter_traverse(&iter) ?:
94 bch2_trans_update(&trans, &iter, &k.k_i, 0));
96 bch_err_msg(c, ret, "update error");
100 bch2_trans_unlock(&trans);
101 bch2_journal_flush_all_pins(&c->journal);
103 ret = commit_do(&trans, NULL, NULL, 0,
104 bch2_btree_iter_traverse(&iter) ?:
105 bch2_btree_delete_at(&trans, &iter, 0));
107 bch_err_msg(c, ret, "delete error");
111 bch2_trans_iter_exit(&trans, &iter);
112 bch2_trans_exit(&trans);
116 static int test_iterate(struct bch_fs *c, u64 nr)
118 struct btree_trans trans;
119 struct btree_iter iter = { NULL };
124 bch2_trans_init(&trans, c, 0, 0);
128 pr_info("inserting test keys");
130 for (i = 0; i < nr; i++) {
131 struct bkey_i_cookie k;
133 bkey_cookie_init(&k.k_i);
135 k.k.p.snapshot = U32_MAX;
137 ret = bch2_btree_insert(c, BTREE_ID_xattrs, &k.k_i,
140 bch_err_msg(c, ret, "insert error");
145 pr_info("iterating forwards");
149 ret = for_each_btree_key2_upto(&trans, iter, BTREE_ID_xattrs,
150 SPOS(0, 0, U32_MAX), POS(0, U64_MAX),
152 BUG_ON(k.k->p.offset != i++);
156 bch_err_msg(c, ret, "error iterating forwards");
162 pr_info("iterating backwards");
164 ret = for_each_btree_key_reverse(&trans, iter, BTREE_ID_xattrs,
165 SPOS(0, U64_MAX, U32_MAX), 0, k,
167 BUG_ON(k.k->p.offset != --i);
171 bch_err_msg(c, ret, "error iterating backwards");
177 bch2_trans_iter_exit(&trans, &iter);
178 bch2_trans_exit(&trans);
182 static int test_iterate_extents(struct bch_fs *c, u64 nr)
184 struct btree_trans trans;
185 struct btree_iter iter = { NULL };
190 bch2_trans_init(&trans, c, 0, 0);
194 pr_info("inserting test extents");
196 for (i = 0; i < nr; i += 8) {
197 struct bkey_i_cookie k;
199 bkey_cookie_init(&k.k_i);
200 k.k.p.offset = i + 8;
201 k.k.p.snapshot = U32_MAX;
204 ret = bch2_btree_insert(c, BTREE_ID_extents, &k.k_i,
207 bch_err_msg(c, ret, "insert error");
212 pr_info("iterating forwards");
216 ret = for_each_btree_key2_upto(&trans, iter, BTREE_ID_extents,
217 SPOS(0, 0, U32_MAX), POS(0, U64_MAX),
219 BUG_ON(bkey_start_offset(k.k) != i);
224 bch_err_msg(c, ret, "error iterating forwards");
230 pr_info("iterating backwards");
232 ret = for_each_btree_key_reverse(&trans, iter, BTREE_ID_extents,
233 SPOS(0, U64_MAX, U32_MAX), 0, k,
235 BUG_ON(k.k->p.offset != i);
236 i = bkey_start_offset(k.k);
240 bch_err_msg(c, ret, "error iterating backwards");
246 bch2_trans_iter_exit(&trans, &iter);
247 bch2_trans_exit(&trans);
251 static int test_iterate_slots(struct bch_fs *c, u64 nr)
253 struct btree_trans trans;
254 struct btree_iter iter = { NULL };
259 bch2_trans_init(&trans, c, 0, 0);
263 pr_info("inserting test keys");
265 for (i = 0; i < nr; i++) {
266 struct bkey_i_cookie k;
268 bkey_cookie_init(&k.k_i);
269 k.k.p.offset = i * 2;
270 k.k.p.snapshot = U32_MAX;
272 ret = bch2_btree_insert(c, BTREE_ID_xattrs, &k.k_i,
275 bch_err_msg(c, ret, "insert error");
280 pr_info("iterating forwards");
284 ret = for_each_btree_key2_upto(&trans, iter, BTREE_ID_xattrs,
285 SPOS(0, 0, U32_MAX), POS(0, U64_MAX),
287 BUG_ON(k.k->p.offset != i);
292 bch_err_msg(c, ret, "error iterating forwards");
298 pr_info("iterating forwards by slots");
302 ret = for_each_btree_key2_upto(&trans, iter, BTREE_ID_xattrs,
303 SPOS(0, 0, U32_MAX), POS(0, U64_MAX),
304 BTREE_ITER_SLOTS, k, ({
308 BUG_ON(k.k->p.offset != i);
309 BUG_ON(bkey_deleted(k.k) != (i & 1));
315 bch_err_msg(c, ret, "error iterating forwards by slots");
320 bch2_trans_exit(&trans);
324 static int test_iterate_slots_extents(struct bch_fs *c, u64 nr)
326 struct btree_trans trans;
327 struct btree_iter iter = { NULL };
332 bch2_trans_init(&trans, c, 0, 0);
336 pr_info("inserting test keys");
338 for (i = 0; i < nr; i += 16) {
339 struct bkey_i_cookie k;
341 bkey_cookie_init(&k.k_i);
342 k.k.p.offset = i + 16;
343 k.k.p.snapshot = U32_MAX;
346 ret = bch2_btree_insert(c, BTREE_ID_extents, &k.k_i,
349 bch_err_msg(c, ret, "insert error");
354 pr_info("iterating forwards");
358 ret = for_each_btree_key2_upto(&trans, iter, BTREE_ID_extents,
359 SPOS(0, 0, U32_MAX), POS(0, U64_MAX),
361 BUG_ON(bkey_start_offset(k.k) != i + 8);
362 BUG_ON(k.k->size != 8);
367 bch_err_msg(c, ret, "error iterating forwards");
373 pr_info("iterating forwards by slots");
377 ret = for_each_btree_key2_upto(&trans, iter, BTREE_ID_extents,
378 SPOS(0, 0, U32_MAX), POS(0, U64_MAX),
379 BTREE_ITER_SLOTS, k, ({
382 BUG_ON(bkey_deleted(k.k) != !(i % 16));
384 BUG_ON(bkey_start_offset(k.k) != i);
385 BUG_ON(k.k->size != 8);
390 bch_err_msg(c, ret, "error iterating forwards by slots");
395 bch2_trans_exit(&trans);
400 * XXX: we really want to make sure we've got a btree with depth > 0 for these
403 static int test_peek_end(struct bch_fs *c, u64 nr)
405 struct btree_trans trans;
406 struct btree_iter iter;
409 bch2_trans_init(&trans, c, 0, 0);
410 bch2_trans_iter_init(&trans, &iter, BTREE_ID_xattrs,
411 SPOS(0, 0, U32_MAX), 0);
413 lockrestart_do(&trans, bkey_err(k = bch2_btree_iter_peek_upto(&iter, POS(0, U64_MAX))));
416 lockrestart_do(&trans, bkey_err(k = bch2_btree_iter_peek_upto(&iter, POS(0, U64_MAX))));
419 bch2_trans_iter_exit(&trans, &iter);
420 bch2_trans_exit(&trans);
424 static int test_peek_end_extents(struct bch_fs *c, u64 nr)
426 struct btree_trans trans;
427 struct btree_iter iter;
430 bch2_trans_init(&trans, c, 0, 0);
431 bch2_trans_iter_init(&trans, &iter, BTREE_ID_extents,
432 SPOS(0, 0, U32_MAX), 0);
434 lockrestart_do(&trans, bkey_err(k = bch2_btree_iter_peek_upto(&iter, POS(0, U64_MAX))));
437 lockrestart_do(&trans, bkey_err(k = bch2_btree_iter_peek_upto(&iter, POS(0, U64_MAX))));
440 bch2_trans_iter_exit(&trans, &iter);
441 bch2_trans_exit(&trans);
445 /* extent unit tests */
447 static u64 test_version;
449 static int insert_test_extent(struct bch_fs *c,
452 struct bkey_i_cookie k;
455 bkey_cookie_init(&k.k_i);
456 k.k_i.k.p.offset = end;
457 k.k_i.k.p.snapshot = U32_MAX;
458 k.k_i.k.size = end - start;
459 k.k_i.k.version.lo = test_version++;
461 ret = bch2_btree_insert(c, BTREE_ID_extents, &k.k_i,
468 static int __test_extent_overwrite(struct bch_fs *c,
469 u64 e1_start, u64 e1_end,
470 u64 e2_start, u64 e2_end)
474 ret = insert_test_extent(c, e1_start, e1_end) ?:
475 insert_test_extent(c, e2_start, e2_end);
481 static int test_extent_overwrite_front(struct bch_fs *c, u64 nr)
483 return __test_extent_overwrite(c, 0, 64, 0, 32) ?:
484 __test_extent_overwrite(c, 8, 64, 0, 32);
487 static int test_extent_overwrite_back(struct bch_fs *c, u64 nr)
489 return __test_extent_overwrite(c, 0, 64, 32, 64) ?:
490 __test_extent_overwrite(c, 0, 64, 32, 72);
493 static int test_extent_overwrite_middle(struct bch_fs *c, u64 nr)
495 return __test_extent_overwrite(c, 0, 64, 32, 40);
498 static int test_extent_overwrite_all(struct bch_fs *c, u64 nr)
500 return __test_extent_overwrite(c, 32, 64, 0, 64) ?:
501 __test_extent_overwrite(c, 32, 64, 0, 128) ?:
502 __test_extent_overwrite(c, 32, 64, 32, 64) ?:
503 __test_extent_overwrite(c, 32, 64, 32, 128);
506 static int insert_test_overlapping_extent(struct bch_fs *c, u64 inum, u64 start, u32 len, u32 snapid)
508 struct bkey_i_cookie k;
511 bkey_cookie_init(&k.k_i);
512 k.k_i.k.p.inode = inum;
513 k.k_i.k.p.offset = start + len;
514 k.k_i.k.p.snapshot = snapid;
517 ret = bch2_trans_do(c, NULL, NULL, 0,
518 bch2_btree_insert_nonextent(&trans, BTREE_ID_extents, &k.k_i,
519 BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE));
525 static int test_extent_create_overlapping(struct bch_fs *c, u64 inum)
527 return insert_test_overlapping_extent(c, inum, 0, 16, U32_MAX - 2) ?: /* overwrite entire */
528 insert_test_overlapping_extent(c, inum, 2, 8, U32_MAX - 2) ?:
529 insert_test_overlapping_extent(c, inum, 4, 4, U32_MAX) ?:
530 insert_test_overlapping_extent(c, inum, 32, 8, U32_MAX - 2) ?: /* overwrite front/back */
531 insert_test_overlapping_extent(c, inum, 36, 8, U32_MAX) ?:
532 insert_test_overlapping_extent(c, inum, 60, 8, U32_MAX - 2) ?:
533 insert_test_overlapping_extent(c, inum, 64, 8, U32_MAX);
536 /* snapshot unit tests */
538 /* Test skipping over keys in unrelated snapshots: */
539 static int test_snapshot_filter(struct bch_fs *c, u32 snapid_lo, u32 snapid_hi)
541 struct btree_trans trans;
542 struct btree_iter iter;
544 struct bkey_i_cookie cookie;
547 bkey_cookie_init(&cookie.k_i);
548 cookie.k.p.snapshot = snapid_hi;
549 ret = bch2_btree_insert(c, BTREE_ID_xattrs, &cookie.k_i,
554 bch2_trans_init(&trans, c, 0, 0);
555 bch2_trans_iter_init(&trans, &iter, BTREE_ID_xattrs,
556 SPOS(0, 0, snapid_lo), 0);
557 lockrestart_do(&trans, bkey_err(k = bch2_btree_iter_peek_upto(&iter, POS(0, U64_MAX))));
559 BUG_ON(k.k->p.snapshot != U32_MAX);
561 bch2_trans_iter_exit(&trans, &iter);
562 bch2_trans_exit(&trans);
566 static int test_snapshots(struct bch_fs *c, u64 nr)
568 struct bkey_i_cookie cookie;
570 u32 snapid_subvols[2] = { 1, 1 };
573 bkey_cookie_init(&cookie.k_i);
574 cookie.k.p.snapshot = U32_MAX;
575 ret = bch2_btree_insert(c, BTREE_ID_xattrs, &cookie.k_i,
580 ret = bch2_trans_do(c, NULL, NULL, 0,
581 bch2_snapshot_node_create(&trans, U32_MAX,
588 if (snapids[0] > snapids[1])
589 swap(snapids[0], snapids[1]);
591 ret = test_snapshot_filter(c, snapids[0], snapids[1]);
593 bch_err_msg(c, ret, "from test_snapshot_filter");
602 static u64 test_rand(void)
606 get_random_bytes(&v, sizeof(v));
610 static int rand_insert(struct bch_fs *c, u64 nr)
612 struct btree_trans trans;
613 struct bkey_i_cookie k;
617 bch2_trans_init(&trans, c, 0, 0);
619 for (i = 0; i < nr; i++) {
620 bkey_cookie_init(&k.k_i);
621 k.k.p.offset = test_rand();
622 k.k.p.snapshot = U32_MAX;
624 ret = commit_do(&trans, NULL, NULL, 0,
625 __bch2_btree_insert(&trans, BTREE_ID_xattrs, &k.k_i, 0));
630 bch2_trans_exit(&trans);
634 static int rand_insert_multi(struct bch_fs *c, u64 nr)
636 struct btree_trans trans;
637 struct bkey_i_cookie k[8];
642 bch2_trans_init(&trans, c, 0, 0);
644 for (i = 0; i < nr; i += ARRAY_SIZE(k)) {
645 for (j = 0; j < ARRAY_SIZE(k); j++) {
646 bkey_cookie_init(&k[j].k_i);
647 k[j].k.p.offset = test_rand();
648 k[j].k.p.snapshot = U32_MAX;
651 ret = commit_do(&trans, NULL, NULL, 0,
652 __bch2_btree_insert(&trans, BTREE_ID_xattrs, &k[0].k_i, 0) ?:
653 __bch2_btree_insert(&trans, BTREE_ID_xattrs, &k[1].k_i, 0) ?:
654 __bch2_btree_insert(&trans, BTREE_ID_xattrs, &k[2].k_i, 0) ?:
655 __bch2_btree_insert(&trans, BTREE_ID_xattrs, &k[3].k_i, 0) ?:
656 __bch2_btree_insert(&trans, BTREE_ID_xattrs, &k[4].k_i, 0) ?:
657 __bch2_btree_insert(&trans, BTREE_ID_xattrs, &k[5].k_i, 0) ?:
658 __bch2_btree_insert(&trans, BTREE_ID_xattrs, &k[6].k_i, 0) ?:
659 __bch2_btree_insert(&trans, BTREE_ID_xattrs, &k[7].k_i, 0));
664 bch2_trans_exit(&trans);
668 static int rand_lookup(struct bch_fs *c, u64 nr)
670 struct btree_trans trans;
671 struct btree_iter iter;
676 bch2_trans_init(&trans, c, 0, 0);
677 bch2_trans_iter_init(&trans, &iter, BTREE_ID_xattrs,
678 SPOS(0, 0, U32_MAX), 0);
680 for (i = 0; i < nr; i++) {
681 bch2_btree_iter_set_pos(&iter, SPOS(0, test_rand(), U32_MAX));
683 lockrestart_do(&trans, bkey_err(k = bch2_btree_iter_peek(&iter)));
689 bch2_trans_iter_exit(&trans, &iter);
690 bch2_trans_exit(&trans);
694 static int rand_mixed_trans(struct btree_trans *trans,
695 struct btree_iter *iter,
696 struct bkey_i_cookie *cookie,
702 bch2_btree_iter_set_pos(iter, SPOS(0, pos, U32_MAX));
704 k = bch2_btree_iter_peek(iter);
706 if (ret && !bch2_err_matches(ret, BCH_ERR_transaction_restart))
707 bch_err_msg(trans->c, ret, "lookup error");
711 if (!(i & 3) && k.k) {
712 bkey_cookie_init(&cookie->k_i);
713 cookie->k.p = iter->pos;
714 ret = bch2_trans_update(trans, iter, &cookie->k_i, 0);
720 static int rand_mixed(struct bch_fs *c, u64 nr)
722 struct btree_trans trans;
723 struct btree_iter iter;
724 struct bkey_i_cookie cookie;
728 bch2_trans_init(&trans, c, 0, 0);
729 bch2_trans_iter_init(&trans, &iter, BTREE_ID_xattrs,
730 SPOS(0, 0, U32_MAX), 0);
732 for (i = 0; i < nr; i++) {
734 ret = commit_do(&trans, NULL, NULL, 0,
735 rand_mixed_trans(&trans, &iter, &cookie, i, rand));
740 bch2_trans_iter_exit(&trans, &iter);
741 bch2_trans_exit(&trans);
745 static int __do_delete(struct btree_trans *trans, struct bpos pos)
747 struct btree_iter iter;
751 bch2_trans_iter_init(trans, &iter, BTREE_ID_xattrs, pos,
753 k = bch2_btree_iter_peek(&iter);
761 ret = bch2_btree_delete_at(trans, &iter, 0);
763 bch2_trans_iter_exit(trans, &iter);
767 static int rand_delete(struct bch_fs *c, u64 nr)
769 struct btree_trans trans;
773 bch2_trans_init(&trans, c, 0, 0);
775 for (i = 0; i < nr; i++) {
776 struct bpos pos = SPOS(0, test_rand(), U32_MAX);
778 ret = commit_do(&trans, NULL, NULL, 0,
779 __do_delete(&trans, pos));
784 bch2_trans_exit(&trans);
788 static int seq_insert(struct bch_fs *c, u64 nr)
790 struct btree_iter iter;
792 struct bkey_i_cookie insert;
794 bkey_cookie_init(&insert.k_i);
796 return bch2_trans_run(c,
797 for_each_btree_key_commit(&trans, iter, BTREE_ID_xattrs,
799 BTREE_ITER_SLOTS|BTREE_ITER_INTENT, k,
801 if (iter.pos.offset >= nr)
803 insert.k.p = iter.pos;
804 bch2_trans_update(&trans, &iter, &insert.k_i, 0);
808 static int seq_lookup(struct bch_fs *c, u64 nr)
810 struct btree_iter iter;
813 return bch2_trans_run(c,
814 for_each_btree_key2_upto(&trans, iter, BTREE_ID_xattrs,
815 SPOS(0, 0, U32_MAX), POS(0, U64_MAX),
820 static int seq_overwrite(struct bch_fs *c, u64 nr)
822 struct btree_iter iter;
825 return bch2_trans_run(c,
826 for_each_btree_key_commit(&trans, iter, BTREE_ID_xattrs,
828 BTREE_ITER_INTENT, k,
830 struct bkey_i_cookie u;
832 bkey_reassemble(&u.k_i, k);
833 bch2_trans_update(&trans, &iter, &u.k_i, 0);
837 static int seq_delete(struct bch_fs *c, u64 nr)
839 return bch2_btree_delete_range(c, BTREE_ID_xattrs,
845 typedef int (*perf_test_fn)(struct bch_fs *, u64);
854 wait_queue_head_t ready_wait;
857 struct completion done_completion;
864 static int btree_perf_test_thread(void *data)
866 struct test_job *j = data;
869 if (atomic_dec_and_test(&j->ready)) {
870 wake_up(&j->ready_wait);
871 j->start = sched_clock();
873 wait_event(j->ready_wait, !atomic_read(&j->ready));
876 ret = j->fn(j->c, div64_u64(j->nr, j->nr_threads));
878 bch_err(j->c, "%ps: error %s", j->fn, bch2_err_str(ret));
882 if (atomic_dec_and_test(&j->done)) {
883 j->finish = sched_clock();
884 complete(&j->done_completion);
890 int bch2_btree_perf_test(struct bch_fs *c, const char *testname,
891 u64 nr, unsigned nr_threads)
893 struct test_job j = { .c = c, .nr = nr, .nr_threads = nr_threads };
895 struct printbuf nr_buf = PRINTBUF;
896 struct printbuf per_sec_buf = PRINTBUF;
900 atomic_set(&j.ready, nr_threads);
901 init_waitqueue_head(&j.ready_wait);
903 atomic_set(&j.done, nr_threads);
904 init_completion(&j.done_completion);
906 #define perf_test(_test) \
907 if (!strcmp(testname, #_test)) j.fn = _test
909 perf_test(rand_insert);
910 perf_test(rand_insert_multi);
911 perf_test(rand_lookup);
912 perf_test(rand_mixed);
913 perf_test(rand_delete);
915 perf_test(seq_insert);
916 perf_test(seq_lookup);
917 perf_test(seq_overwrite);
918 perf_test(seq_delete);
920 /* a unit test, not a perf test: */
921 perf_test(test_delete);
922 perf_test(test_delete_written);
923 perf_test(test_iterate);
924 perf_test(test_iterate_extents);
925 perf_test(test_iterate_slots);
926 perf_test(test_iterate_slots_extents);
927 perf_test(test_peek_end);
928 perf_test(test_peek_end_extents);
930 perf_test(test_extent_overwrite_front);
931 perf_test(test_extent_overwrite_back);
932 perf_test(test_extent_overwrite_middle);
933 perf_test(test_extent_overwrite_all);
934 perf_test(test_extent_create_overlapping);
936 perf_test(test_snapshots);
939 pr_err("unknown test %s", testname);
943 //pr_info("running test %s:", testname);
946 btree_perf_test_thread(&j);
948 for (i = 0; i < nr_threads; i++)
949 kthread_run(btree_perf_test_thread, &j,
950 "bcachefs perf test[%u]", i);
952 while (wait_for_completion_interruptible(&j.done_completion))
955 time = j.finish - j.start;
957 scnprintf(name_buf, sizeof(name_buf), "%s:", testname);
958 prt_human_readable_u64(&nr_buf, nr);
959 prt_human_readable_u64(&per_sec_buf, div64_u64(nr * NSEC_PER_SEC, time));
960 printk(KERN_INFO "%-12s %s with %u threads in %5llu sec, %5llu nsec per iter, %5s per sec\n",
961 name_buf, nr_buf.buf, nr_threads,
962 div_u64(time, NSEC_PER_SEC),
963 div_u64(time * nr_threads, nr),
965 printbuf_exit(&per_sec_buf);
966 printbuf_exit(&nr_buf);
970 #endif /* CONFIG_BCACHEFS_TESTS */