snapshot.c | Explore in Territory

// SPDX-License-Identifier: GPL-2.0

#include "bcachefs.h"
#include "bkey_buf.h"
#include "btree_key_cache.h"
#include "btree_update.h"
#include "buckets.h"
#include "errcode.h"
#include "error.h"
#include "fs.h"
#include "recovery_passes.h"
#include "snapshot.h"

#include <linux/random.h>

/*
 * Snapshot trees:
 *
 * Keys in BTREE_ID_snapshot_trees identify a whole tree of snapshot nodes; they
 * exist to provide a stable identifier for the whole lifetime of a snapshot
 * tree.
 */

void bch2_snapshot_tree_to_text(struct printbuf *out, struct bch_fs *c,
				struct bkey_s_c k)
{ … }

int bch2_snapshot_tree_invalid(struct bch_fs *c, struct bkey_s_c k,
			       enum bch_validate_flags flags,
			       struct printbuf *err)
{ … }

int bch2_snapshot_tree_lookup(struct btree_trans *trans, u32 id,
			      struct bch_snapshot_tree *s)
{ … }

struct bkey_i_snapshot_tree *
__bch2_snapshot_tree_create(struct btree_trans *trans)
{ … }

static int bch2_snapshot_tree_create(struct btree_trans *trans,
				u32 root_id, u32 subvol_id, u32 *tree_id)
{ … }

/* Snapshot nodes: */

static bool __bch2_snapshot_is_ancestor_early(struct snapshot_table *t, u32 id, u32 ancestor)
{ … }

static bool bch2_snapshot_is_ancestor_early(struct bch_fs *c, u32 id, u32 ancestor)
{ … }

static inline u32 get_ancestor_below(struct snapshot_table *t, u32 id, u32 ancestor)
{ … }

static bool test_ancestor_bitmap(struct snapshot_table *t, u32 id, u32 ancestor)
{ … }

bool __bch2_snapshot_is_ancestor(struct bch_fs *c, u32 id, u32 ancestor)
{ … }

static noinline struct snapshot_t *__snapshot_t_mut(struct bch_fs *c, u32 id)
{ … }

static inline struct snapshot_t *snapshot_t_mut(struct bch_fs *c, u32 id)
{ … }

void bch2_snapshot_to_text(struct printbuf *out, struct bch_fs *c,
			   struct bkey_s_c k)
{ … }

int bch2_snapshot_invalid(struct bch_fs *c, struct bkey_s_c k,
			  enum bch_validate_flags flags,
			  struct printbuf *err)
{ … }

static void __set_is_ancestor_bitmap(struct bch_fs *c, u32 id)
{ … }

static void set_is_ancestor_bitmap(struct bch_fs *c, u32 id)
{ … }

static int __bch2_mark_snapshot(struct btree_trans *trans,
		       enum btree_id btree, unsigned level,
		       struct bkey_s_c old, struct bkey_s_c new,
		       enum btree_iter_update_trigger_flags flags)
{ … }

int bch2_mark_snapshot(struct btree_trans *trans,
		       enum btree_id btree, unsigned level,
		       struct bkey_s_c old, struct bkey_s new,
		       enum btree_iter_update_trigger_flags flags)
{ … }

int bch2_snapshot_lookup(struct btree_trans *trans, u32 id,
			 struct bch_snapshot *s)
{ … }

static int bch2_snapshot_live(struct btree_trans *trans, u32 id)
{ … }

/*
 * If @k is a snapshot with just one live child, it's part of a linear chain,
 * which we consider to be an equivalence class: and then after snapshot
 * deletion cleanup, there should only be a single key at a given position in
 * this equivalence class.
 *
 * This sets the equivalence class of @k to be the child's equivalence class, if
 * it's part of such a linear chain: this correctly sets equivalence classes on
 * startup if we run leaf to root (i.e. in natural key order).
 */
static int bch2_snapshot_set_equiv(struct btree_trans *trans, struct bkey_s_c k)
{ … }

/* fsck: */

static u32 bch2_snapshot_child(struct bch_fs *c, u32 id, unsigned child)
{ … }

static u32 bch2_snapshot_left_child(struct bch_fs *c, u32 id)
{ … }

static u32 bch2_snapshot_right_child(struct bch_fs *c, u32 id)
{ … }

static u32 bch2_snapshot_tree_next(struct bch_fs *c, u32 id)
{ … }

static u32 bch2_snapshot_tree_oldest_subvol(struct bch_fs *c, u32 snapshot_root)
{ … }

static int bch2_snapshot_tree_master_subvol(struct btree_trans *trans,
					    u32 snapshot_root, u32 *subvol_id)
{ … }

static int check_snapshot_tree(struct btree_trans *trans,
			       struct btree_iter *iter,
			       struct bkey_s_c k)
{ … }

/*
 * For each snapshot_tree, make sure it points to the root of a snapshot tree
 * and that snapshot entry points back to it, or delete it.
 *
 * And, make sure it points to a subvolume within that snapshot tree, or correct
 * it to point to the oldest subvolume within that snapshot tree.
 */
int bch2_check_snapshot_trees(struct bch_fs *c)
{ … }

/*
 * Look up snapshot tree for @tree_id and find root,
 * make sure @snap_id is a descendent:
 */
static int snapshot_tree_ptr_good(struct btree_trans *trans,
				  u32 snap_id, u32 tree_id)
{ … }

u32 bch2_snapshot_skiplist_get(struct bch_fs *c, u32 id)
{ … }

static int snapshot_skiplist_good(struct btree_trans *trans, u32 id, struct bch_snapshot s)
{ … }

/*
 * snapshot_tree pointer was incorrect: look up root snapshot node, make sure
 * its snapshot_tree pointer is correct (allocate new one if necessary), then
 * update this node's pointer to root node's pointer:
 */
static int snapshot_tree_ptr_repair(struct btree_trans *trans,
				    struct btree_iter *iter,
				    struct bkey_s_c k,
				    struct bch_snapshot *s)
{ … }

static int check_snapshot(struct btree_trans *trans,
			  struct btree_iter *iter,
			  struct bkey_s_c k)
{ … }

int bch2_check_snapshots(struct bch_fs *c)
{ … }

static int check_snapshot_exists(struct btree_trans *trans, u32 id)
{ … }

/* Figure out which snapshot nodes belong in the same tree: */
struct snapshot_tree_reconstruct { … };

static void snapshot_tree_reconstruct_exit(struct snapshot_tree_reconstruct *r)
{ … }

static inline bool same_snapshot(struct snapshot_tree_reconstruct *r, struct bpos pos)
{ … }

static inline bool snapshot_id_lists_have_common(snapshot_id_list *l, snapshot_id_list *r)
{ … }

static void snapshot_id_list_to_text(struct printbuf *out, snapshot_id_list *s)
{ … }

static int snapshot_tree_reconstruct_next(struct bch_fs *c, struct snapshot_tree_reconstruct *r)
{ … }

static int get_snapshot_trees(struct bch_fs *c, struct snapshot_tree_reconstruct *r, struct bpos pos)
{ … }

int bch2_reconstruct_snapshots(struct bch_fs *c)
{ … }

int bch2_check_key_has_snapshot(struct btree_trans *trans,
				struct btree_iter *iter,
				struct bkey_s_c k)
{ … }

/*
 * Mark a snapshot as deleted, for future cleanup:
 */
int bch2_snapshot_node_set_deleted(struct btree_trans *trans, u32 id)
{ … }

static inline void normalize_snapshot_child_pointers(struct bch_snapshot *s)
{ … }

static int bch2_snapshot_node_delete(struct btree_trans *trans, u32 id)
{ … }

static int create_snapids(struct btree_trans *trans, u32 parent, u32 tree,
			  u32 *new_snapids,
			  u32 *snapshot_subvols,
			  unsigned nr_snapids)
{ … }

/*
 * Create new snapshot IDs as children of an existing snapshot ID:
 */
static int bch2_snapshot_node_create_children(struct btree_trans *trans, u32 parent,
			      u32 *new_snapids,
			      u32 *snapshot_subvols,
			      unsigned nr_snapids)
{ … }

/*
 * Create a snapshot node that is the root of a new tree:
 */
static int bch2_snapshot_node_create_tree(struct btree_trans *trans,
			      u32 *new_snapids,
			      u32 *snapshot_subvols,
			      unsigned nr_snapids)
{ … }

int bch2_snapshot_node_create(struct btree_trans *trans, u32 parent,
			      u32 *new_snapids,
			      u32 *snapshot_subvols,
			      unsigned nr_snapids)
{ … }

/*
 * If we have an unlinked inode in an internal snapshot node, and the inode
 * really has been deleted in all child snapshots, how does this get cleaned up?
 *
 * first there is the problem of how keys that have been overwritten in all
 * child snapshots get deleted (unimplemented?), but inodes may perhaps be
 * special?
 *
 * also: unlinked inode in internal snapshot appears to not be getting deleted
 * correctly if inode doesn't exist in leaf snapshots
 *
 * solution:
 *
 * for a key in an interior snapshot node that needs work to be done that
 * requires it to be mutated: iterate over all descendent leaf nodes and copy
 * that key to snapshot leaf nodes, where we can mutate it
 */

static int delete_dead_snapshots_process_key(struct btree_trans *trans,
			       struct btree_iter *iter,
			       struct bkey_s_c k,
			       snapshot_id_list *deleted,
			       snapshot_id_list *equiv_seen,
			       struct bpos *last_pos)
{ … }

static int bch2_snapshot_needs_delete(struct btree_trans *trans, struct bkey_s_c k)
{ … }

/*
 * For a given snapshot, if it doesn't have a subvolume that points to it, and
 * it doesn't have child snapshot nodes - it's now redundant and we can mark it
 * as deleted.
 */
static int bch2_delete_redundant_snapshot(struct btree_trans *trans, struct bkey_s_c k)
{ … }

static inline u32 bch2_snapshot_nth_parent_skip(struct bch_fs *c, u32 id, u32 n,
						snapshot_id_list *skip)
{ … }

static int bch2_fix_child_of_deleted_snapshot(struct btree_trans *trans,
					      struct btree_iter *iter, struct bkey_s_c k,
					      snapshot_id_list *deleted)
{ … }

int bch2_delete_dead_snapshots(struct bch_fs *c)
{ … }

void bch2_delete_dead_snapshots_work(struct work_struct *work)
{ … }

void bch2_delete_dead_snapshots_async(struct bch_fs *c)
{ … }

int __bch2_key_has_snapshot_overwrites(struct btree_trans *trans,
				       enum btree_id id,
				       struct bpos pos)
{ … }

static u32 bch2_snapshot_smallest_child(struct bch_fs *c, u32 id)
{ … }

static u32 bch2_snapshot_smallest_descendent(struct bch_fs *c, u32 id)
{ … }

static int bch2_propagate_key_to_snapshot_leaf(struct btree_trans *trans,
					       enum btree_id btree,
					       struct bkey_s_c interior_k,
					       u32 leaf_id, struct bpos *new_min_pos)
{ … }

int bch2_propagate_key_to_snapshot_leaves(struct btree_trans *trans,
					  enum btree_id btree,
					  struct bkey_s_c k,
					  struct bpos *new_min_pos)
{ … }

static int bch2_check_snapshot_needs_deletion(struct btree_trans *trans, struct bkey_s_c k)
{ … }

int bch2_snapshots_read(struct bch_fs *c)
{ … }

void bch2_fs_snapshots_exit(struct bch_fs *c)
{ … }
linux/fs/bcachefs/snapshot.c
