btree_gc.c | Explore in Territory

// SPDX-License-Identifier: GPL-2.0
/*
 * Copyright (C) 2010 Kent Overstreet <[email protected]>
 * Copyright (C) 2014 Datera Inc.
 */

#include "bcachefs.h"
#include "alloc_background.h"
#include "alloc_foreground.h"
#include "backpointers.h"
#include "bkey_methods.h"
#include "bkey_buf.h"
#include "btree_journal_iter.h"
#include "btree_key_cache.h"
#include "btree_locking.h"
#include "btree_node_scan.h"
#include "btree_update_interior.h"
#include "btree_io.h"
#include "btree_gc.h"
#include "buckets.h"
#include "clock.h"
#include "debug.h"
#include "disk_accounting.h"
#include "ec.h"
#include "error.h"
#include "extents.h"
#include "journal.h"
#include "keylist.h"
#include "move.h"
#include "recovery_passes.h"
#include "reflink.h"
#include "replicas.h"
#include "super-io.h"
#include "trace.h"

#include <linux/slab.h>
#include <linux/bitops.h>
#include <linux/freezer.h>
#include <linux/kthread.h>
#include <linux/preempt.h>
#include <linux/rcupdate.h>
#include <linux/sched/task.h>

#define DROP_THIS_NODE …
#define DROP_PREV_NODE …
#define DID_FILL_FROM_SCAN …

static const char * const bch2_gc_phase_strs[] = …;

void bch2_gc_pos_to_text(struct printbuf *out, struct gc_pos *p)
{ … }

static struct bkey_s unsafe_bkey_s_c_to_s(struct bkey_s_c k)
{ … }

static inline void __gc_pos_set(struct bch_fs *c, struct gc_pos new_pos)
{ … }

static inline void gc_pos_set(struct bch_fs *c, struct gc_pos new_pos)
{ … }

static void btree_ptr_to_v2(struct btree *b, struct bkey_i_btree_ptr_v2 *dst)
{ … }

static int set_node_min(struct bch_fs *c, struct btree *b, struct bpos new_min)
{ … }

static int set_node_max(struct bch_fs *c, struct btree *b, struct bpos new_max)
{ … }

static int btree_check_node_boundaries(struct btree_trans *trans, struct btree *b,
				       struct btree *prev, struct btree *cur,
				       struct bpos *pulled_from_scan)
{ … }

static int btree_repair_node_end(struct btree_trans *trans, struct btree *b,
				 struct btree *child, struct bpos *pulled_from_scan)
{ … }

static int bch2_btree_repair_topology_recurse(struct btree_trans *trans, struct btree *b,
					      struct bpos *pulled_from_scan)
{ … }

int bch2_check_topology(struct bch_fs *c)
{ … }

/* marking of btree keys/nodes: */

static int bch2_gc_mark_key(struct btree_trans *trans, enum btree_id btree_id,
			    unsigned level, struct btree **prev,
			    struct btree_iter *iter, struct bkey_s_c k,
			    bool initial)
{ … }

static int bch2_gc_btree(struct btree_trans *trans, enum btree_id btree, bool initial)
{ … }

static inline int btree_id_gc_phase_cmp(enum btree_id l, enum btree_id r)
{ … }

static int bch2_gc_btrees(struct bch_fs *c)
{ … }

static int bch2_mark_superblocks(struct bch_fs *c)
{ … }

static void bch2_gc_free(struct bch_fs *c)
{ … }

static int bch2_gc_start(struct bch_fs *c)
{ … }

/* returns true if not equal */
static inline bool bch2_alloc_v4_cmp(struct bch_alloc_v4 l,
				     struct bch_alloc_v4 r)
{ … }

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

static int bch2_gc_alloc_done(struct bch_fs *c)
{ … }

static int bch2_gc_alloc_start(struct bch_fs *c)
{ … }

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

static int bch2_gc_reflink_done(struct bch_fs *c)
{ … }

static int bch2_gc_reflink_start(struct bch_fs *c)
{ … }

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

static int bch2_gc_stripes_done(struct bch_fs *c)
{ … }

/**
 * bch2_check_allocations - walk all references to buckets, and recompute them:
 *
 * @c:			filesystem object
 *
 * Returns: 0 on success, or standard errcode on failure
 *
 * Order matters here:
 *  - Concurrent GC relies on the fact that we have a total ordering for
 *    everything that GC walks - see  gc_will_visit_node(),
 *    gc_will_visit_root()
 *
 *  - also, references move around in the course of index updates and
 *    various other crap: everything needs to agree on the ordering
 *    references are allowed to move around in - e.g., we're allowed to
 *    start with a reference owned by an open_bucket (the allocator) and
 *    move it to the btree, but not the reverse.
 *
 *    This is necessary to ensure that gc doesn't miss references that
 *    move around - if references move backwards in the ordering GC
 *    uses, GC could skip past them
 */
int bch2_check_allocations(struct bch_fs *c)
{ … }

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

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

int bch2_gc_gens(struct bch_fs *c)
{ … }

static void bch2_gc_gens_work(struct work_struct *work)
{ … }

void bch2_gc_gens_async(struct bch_fs *c)
{ … }

void bch2_fs_gc_init(struct bch_fs *c)
{ … }
linux/fs/bcachefs/btree_gc.c
