bcachefs: New on disk format: Backpointers

This patch adds backpointers: we now have a reverse index from device
and offset on that device (specifically, offset within a bucket) back to
btree nodes and (non cached) data extents.

The first 40 backpointers within a bucket are stored in the alloc key;
after that backpointers spill over to the next backpointers btree. This
is to help avoid performance regressions from additional btree updates
on large streaming workloads.

This patch adds all the code for creating, checking and repairing
backpointers. The next patch in the series is going to use backpointers
for copygc - finally getting rid of the need to scan all extents to do
copygc.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

1 files changed, 33 insertions, 2 deletions

diff --git a/fs/bcachefs/recovery.c b/fs/bcachefs/recovery.c
index 61890755d335..55356c117737 100644
--- a/fs/bcachefs/recovery.c
+++ b/fs/bcachefs/recovery.c
@@ -1,6 +1,7 @@
 // SPDX-License-Identifier: GPL-2.0
 
 #include "bcachefs.h"
+#include "backpointers.h"
 #include "bkey_buf.h"
 #include "alloc_background.h"
 #include "btree_gc.h"
@@ -925,6 +926,7 @@ static bool btree_id_is_alloc(enum btree_id id)
 {
 	switch (id) {
 	case BTREE_ID_alloc:
+	case BTREE_ID_backpointers:
 	case BTREE_ID_need_discard:
 	case BTREE_ID_freespace:
 		return true;
@@ -1091,8 +1093,8 @@ int bch2_fs_recovery(struct bch_fs *c)
 	}
 
 	if (!c->opts.nochanges) {
-		if (c->sb.version < bcachefs_metadata_version_new_data_types) {
-			bch_info(c, "version prior to new_data_types, upgrade and fsck required");
+		if (c->sb.version < bcachefs_metadata_version_backpointers) {
+			bch_info(c, "version prior to backpointers, upgrade and fsck required");
 			c->opts.version_upgrade	= true;
 			c->opts.fsck		= true;
 			c->opts.fix_errors	= FSCK_OPT_YES;
@@ -1301,6 +1303,28 @@ use_clean:
 		bch_verbose(c, "done checking lrus");
 		set_bit(BCH_FS_CHECK_LRUS_DONE, &c->flags);
 
+		bch_info(c, "checking backpointers to alloc keys");
+		err = "error checking backpointers to alloc keys";
+		ret = bch2_check_btree_backpointers(c);
+		if (ret)
+			goto err;
+		bch_verbose(c, "done checking backpointers to alloc keys");
+
+		bch_info(c, "checking backpointers to extents");
+		err = "error checking backpointers to extents";
+		ret = bch2_check_backpointers_to_extents(c);
+		if (ret)
+			goto err;
+		bch_verbose(c, "done checking backpointers to extents");
+
+		bch_info(c, "checking extents to backpointers");
+		err = "error checking extents to backpointers";
+		ret = bch2_check_extents_to_backpointers(c);
+		if (ret)
+			goto err;
+		bch_verbose(c, "done checking extents to backpointers");
+		set_bit(BCH_FS_CHECK_BACKPOINTERS_DONE, &c->flags);
+
 		bch_info(c, "checking alloc to lru refs");
 		err = "error checking alloc to lru refs";
 		ret = bch2_check_alloc_to_lru_refs(c);
@@ -1312,6 +1336,7 @@ use_clean:
 		set_bit(BCH_FS_INITIAL_GC_DONE, &c->flags);
 		set_bit(BCH_FS_CHECK_ALLOC_DONE, &c->flags);
 		set_bit(BCH_FS_CHECK_LRUS_DONE, &c->flags);
+		set_bit(BCH_FS_CHECK_BACKPOINTERS_DONE, &c->flags);
 		set_bit(BCH_FS_CHECK_ALLOC_TO_LRU_REFS_DONE, &c->flags);
 		set_bit(BCH_FS_FSCK_DONE, &c->flags);
 
@@ -1471,6 +1496,9 @@ int bch2_fs_initialize(struct bch_fs *c)
 	c->disk_sb.sb->compat[0] |= cpu_to_le64(1ULL << BCH_COMPAT_extents_above_btree_updates_done);
 	c->disk_sb.sb->compat[0] |= cpu_to_le64(1ULL << BCH_COMPAT_bformat_overflow_done);
 
+	if (c->sb.version < bcachefs_metadata_version_backpointers)
+		c->opts.version_upgrade	= true;
+
 	if (c->opts.version_upgrade) {
 		c->disk_sb.sb->version = cpu_to_le16(bcachefs_metadata_version_current);
 		c->disk_sb.sb->features[0] |= cpu_to_le64(BCH_SB_FEATURES_ALL);
@@ -1479,6 +1507,9 @@ int bch2_fs_initialize(struct bch_fs *c)
 	mutex_unlock(&c->sb_lock);
 
 	set_bit(BCH_FS_INITIAL_GC_DONE, &c->flags);
+	set_bit(BCH_FS_CHECK_LRUS_DONE, &c->flags);
+	set_bit(BCH_FS_CHECK_BACKPOINTERS_DONE, &c->flags);
+	set_bit(BCH_FS_CHECK_ALLOC_TO_LRU_REFS_DONE, &c->flags);
 	set_bit(BCH_FS_MAY_GO_RW, &c->flags);
 	set_bit(BCH_FS_FSCK_DONE, &c->flags);