// SPDX-License-Identifier: GPL-2.0/* * Copyright (C) 2009 Oracle.  All rights reserved. */ #include <linux/sched.h>#include <linux/pagemap.h>#include <linux/writeback.h>#include <linux/blkdev.h>#include <linux/rbtree.h>#include <linux/slab.h>#include <linux/error-injection.h>#include "ctree.h"#include "disk-io.h"#include "transaction.h"#include "volumes.h"#include "locking.h"#include "btrfs_inode.h"#include "async-thread.h"#include "free-space-cache.h"#include "qgroup.h"#include "print-tree.h"#include "delalloc-space.h"#include "block-group.h"#include "backref.h"#include "misc.h"#include "subpage.h"#include "zoned.h"#include "inode-item.h"#include "space-info.h"#include "fs.h"#include "accessors.h"#include "extent-tree.h"#include "root-tree.h"#include "file-item.h"#include "relocation.h"#include "super.h"#include "tree-checker.h"#include "raid-stripe-tree.h"#include "free-space-tree.h" /* * Relocation overview * * [What does relocation do] * * The objective of relocation is to relocate all extents of the target block * group to other block groups. * This is utilized by resize (shrink only), profile converting, compacting * space, or balance routine to spread chunks over devices. * * 		Before		|		After * ------------------------------------------------------------------ *  BG A: 10 data extents	| BG A: deleted *  BG B:  2 data extents	| BG B: 10 data extents (2 old + 8 relocated) *  BG C:  1 extents		| BG C:  3 data extents (1 old + 2 relocated) * * [How does relocation work] * * 1.   Mark the target block group read-only *      New extents won't be allocated from the target block group. * * 2.1  Record each extent in the target block group *      To build a proper map of extents to be relocated. * * 2.2  Build data reloc tree and reloc trees *      Data reloc tree will contain an inode, recording all newly relocated *      data extents. *      There will be only one data reloc tree for one data block group. * *      Reloc tree will be a special snapshot of its source tree, containing *      relocated tree blocks. *      Each tree referring to a tree block in target block group will get its *      reloc tree built. * * 2.3  Swap source tree with its corresponding reloc tree *      Each involved tree only refers to new extents after swap. * * 3.   Cleanup reloc trees and data reloc tree. *      As old extents in the target block group are still referenced by reloc *      trees, we need to clean them up before really freeing the target block *      group. * * The main complexity is in steps 2.2 and 2.3. * * The entry point of relocation is relocate_block_group() function. */ #define RELOCATION_RESERVED_NODES	256/* * map address of tree root to tree */struct mapping_node {	union {		/* Use rb_simple_node for search/insert */		struct {			struct rb_node rb_node;			u64 bytenr;		}; 		struct rb_simple_node simple_node;	};	void *data;}; struct mapping_tree {	struct rb_root rb_root;	spinlock_t lock;}; /* * present a tree block to process */struct tree_block {	union {		/* Use rb_simple_node for search/insert */		struct {			struct rb_node rb_node;			u64 bytenr;		}; 		struct rb_simple_node simple_node;	};	u64 owner;	struct btrfs_key key;	u8 level;	bool key_ready;}; #define MAX_EXTENTS 128 struct file_extent_cluster {	u64 start;	u64 end;	u64 boundary[MAX_EXTENTS];	unsigned int nr;	u64 owning_root;}; /* Stages of data relocation. */enum reloc_stage {	MOVE_DATA_EXTENTS,	UPDATE_DATA_PTRS}; struct reloc_control {	/* block group to relocate */	struct btrfs_block_group *block_group;	/* extent tree */	struct btrfs_root *extent_root;	/* inode for moving data */	struct inode *data_inode; 	struct btrfs_block_rsv *block_rsv; 	struct btrfs_backref_cache backref_cache; 	struct file_extent_cluster cluster;	/* tree blocks have been processed */	struct extent_io_tree processed_blocks;	/* map start of tree root to corresponding reloc tree */	struct mapping_tree reloc_root_tree;	/* list of reloc trees */	struct list_head reloc_roots;	/* list of subvolume trees that get relocated */	struct list_head dirty_subvol_roots;	/* size of metadata reservation for merging reloc trees */	u64 merging_rsv_size;	/* size of relocated tree nodes */	u64 nodes_relocated;	/* reserved size for block group relocation*/	u64 reserved_bytes; 	u64 search_start;	u64 extents_found; 	enum reloc_stage stage;	bool create_reloc_tree;	bool merge_reloc_tree;	bool found_file_extent; 	refcount_t refs;}; static struct reloc_control *get_reloc_control(struct btrfs_fs_info *fs_info){	struct reloc_control *rc; 	/* Quick path, avoid lock contention on fs_info->reloc_ctl_lock. */	if (!data_race(fs_info->reloc_ctl))		return NULL; 	spin_lock(&fs_info->reloc_ctl_lock);	rc = fs_info->reloc_ctl;	if (rc)		refcount_inc(&rc->refs);	spin_unlock(&fs_info->reloc_ctl_lock); 	return rc;} static void __del_reloc_root(struct btrfs_root *root); static noinline_for_stack void free_reloc_roots(struct list_head *list){	struct btrfs_root *reloc_root, *tmp; 	list_for_each_entry_safe(reloc_root, tmp, list, root_list)		__del_reloc_root(reloc_root);} static void put_reloc_control(struct reloc_control *rc){	if (refcount_dec_and_test(&rc->refs)) {		struct mapping_node *node, *tmp; 		if (rc->extent_root)			ASSERT(rc->extent_root->fs_info->reloc_ctl != rc); 		free_reloc_roots(&rc->reloc_roots);		rbtree_postorder_for_each_entry_safe(node, tmp,						     &rc->reloc_root_tree.rb_root,						     rb_node)			kfree(node); 		if (rc->block_group)			btrfs_put_block_group(rc->block_group); 		kfree(rc);	}} /* Helper to delete the 'address of tree root -> reloc tree' mapping. */static void __del_reloc_root(struct btrfs_root *root){	struct btrfs_fs_info *fs_info = root->fs_info;	struct rb_node *rb_node;	struct mapping_node AUTO_KFREE(node);	struct reloc_control *rc;	bool put_ref = false; 	rc = get_reloc_control(fs_info);	if (rc && root->node) {		spin_lock(&rc->reloc_root_tree.lock);		rb_node = rb_simple_search(&rc->reloc_root_tree.rb_root,					   root->commit_root->start);		if (rb_node) {			node = rb_entry(rb_node, struct mapping_node, rb_node);			rb_erase(&node->rb_node, &rc->reloc_root_tree.rb_root);			RB_CLEAR_NODE(&node->rb_node);		}		spin_unlock(&rc->reloc_root_tree.lock);		ASSERT(!node || (struct btrfs_root *)node->data == root);	} 	/*	 * We only put the reloc root here if it's on the list.  There's a lot	 * of places where the pattern is to splice the rc->reloc_roots, process	 * the reloc roots, and then add the reloc root back onto	 * rc->reloc_roots.  If we call __del_reloc_root while it's off of the	 * list we don't want the reference being dropped, because the guy	 * messing with the list is in charge of the reference.	 */	spin_lock(&fs_info->trans_lock);	if (!list_empty(&root->root_list)) {		put_ref = true;		list_del_init(&root->root_list);	}	spin_unlock(&fs_info->trans_lock);	if (put_ref)		btrfs_put_root(root);	if (rc)		put_reloc_control(rc);} static void mark_block_processed(struct reloc_control *rc,				 struct btrfs_backref_node *node){	u32 blocksize; 	if (node->level == 0 ||	    in_range(node->bytenr, rc->block_group->start,		     rc->block_group->length)) {		blocksize = rc->extent_root->fs_info->nodesize;		btrfs_set_extent_bit(&rc->processed_blocks, node->bytenr,				     node->bytenr + blocksize - 1, EXTENT_DIRTY,				     NULL);	}	node->processed = 1;} /* * walk up backref nodes until reach node presents tree root */static struct btrfs_backref_node *walk_up_backref(		struct btrfs_backref_node *node,		struct btrfs_backref_edge *edges[], int *index){	struct btrfs_backref_edge *edge;	int idx = *index; 	while (!list_empty(&node->upper)) {		edge = list_first_entry(&node->upper, struct btrfs_backref_edge,					list[LOWER]);		edges[idx++] = edge;		node = edge->node[UPPER];	}	BUG_ON(node->detached);	*index = idx;	return node;} /* * walk down backref nodes to find start of next reference path */static struct btrfs_backref_node *walk_down_backref(		struct btrfs_backref_edge *edges[], int *index){	struct btrfs_backref_edge *edge;	struct btrfs_backref_node *lower;	int idx = *index; 	while (idx > 0) {		edge = edges[idx - 1];		lower = edge->node[LOWER];		if (list_is_last(&edge->list[LOWER], &lower->upper)) {			idx--;			continue;		}		edge = list_first_entry(&edge->list[LOWER], struct btrfs_backref_edge,					list[LOWER]);		edges[idx - 1] = edge;		*index = idx;		return edge->node[UPPER];	}	*index = 0;	return NULL;} static bool reloc_root_is_dead(const struct btrfs_root *root){	if (test_bit(BTRFS_ROOT_DEAD_RELOC_TREE, &root->state))		return true;	/*	 * Pairs with set_bit/clear_bit in clear_reloc_root() and	 * btrfs_update_reloc_root(). We need to see the updated bit before	 * trying to access root->reloc_root in our callers.	 */	smp_rmb(); 	return false;} /* * Check if this subvolume tree has valid reloc tree. * * Reloc tree after swap is considered dead, thus not considered as valid. * This is enough for most callers, as they don't distinguish dead reloc root * from no reloc root.  But btrfs_should_ignore_reloc_root() below is a * special case. */static bool have_reloc_root(const struct btrfs_root *root){	if (reloc_root_is_dead(root))		return false;	if (!root->reloc_root)		return false;	return true;} bool btrfs_should_ignore_reloc_root(const struct btrfs_root *root){	struct btrfs_root *reloc_root; 	if (!test_bit(BTRFS_ROOT_SHAREABLE, &root->state))		return false; 	/* This root has been merged with its reloc tree, we can ignore it */	if (reloc_root_is_dead(root))		return true; 	reloc_root = root->reloc_root;	if (!reloc_root)		return false; 	if (btrfs_header_generation(reloc_root->commit_root) ==	    root->fs_info->running_transaction->transid)		return false;	/*	 * If there is reloc tree and it was created in previous transaction	 * backref lookup can find the reloc tree, so backref node for the fs	 * tree root is useless for relocation.	 */	return true;} /* * find reloc tree by address of tree root */struct btrfs_root *find_reloc_root(struct btrfs_fs_info *fs_info, u64 bytenr){	struct reloc_control *rc = fs_info->reloc_ctl;	struct rb_node *rb_node;	struct mapping_node *node;	struct btrfs_root *root = NULL; 	ASSERT(rc);	spin_lock(&rc->reloc_root_tree.lock);	rb_node = rb_simple_search(&rc->reloc_root_tree.rb_root, bytenr);	if (rb_node) {		node = rb_entry(rb_node, struct mapping_node, rb_node);		root = node->data;	}	spin_unlock(&rc->reloc_root_tree.lock);	return btrfs_grab_root(root);} /* * For useless nodes, do two major clean ups: * * - Cleanup the children edges and nodes *   If child node is also orphan (no parent) during cleanup, then the child *   node will also be cleaned up. * * - Freeing up leaves (level 0), keeps nodes detached *   For nodes, the node is still cached as "detached" * * Return false if @node is not in the @useless_nodes list. * Return true if @node is in the @useless_nodes list. */static bool handle_useless_nodes(struct reloc_control *rc,				 struct btrfs_backref_node *node){	struct btrfs_backref_cache *cache = &rc->backref_cache;	struct list_head *useless_node = &cache->useless_node;	bool ret = false; 	while (!list_empty(useless_node)) {		struct btrfs_backref_node *cur; 		cur = list_first_entry(useless_node, struct btrfs_backref_node,				 list);		list_del_init(&cur->list); 		/* Only tree root nodes can be added to @useless_nodes */		ASSERT(list_empty(&cur->upper)); 		if (cur == node)			ret = true; 		/* Cleanup the lower edges */		while (!list_empty(&cur->lower)) {			struct btrfs_backref_edge *edge;			struct btrfs_backref_node *lower; 			edge = list_first_entry(&cur->lower, struct btrfs_backref_edge,						list[UPPER]);			list_del(&edge->list[UPPER]);			list_del(&edge->list[LOWER]);			lower = edge->node[LOWER];			btrfs_backref_free_edge(cache, edge); 			/* Child node is also orphan, queue for cleanup */			if (list_empty(&lower->upper))				list_add(&lower->list, useless_node);		}		/* Mark this block processed for relocation */		mark_block_processed(rc, cur); 		/*		 * Backref nodes for tree leaves are deleted from the cache.		 * Backref nodes for upper level tree blocks are left in the		 * cache to avoid unnecessary backref lookup.		 */		if (cur->level > 0) {			cur->detached = 1;		} else {			rb_erase(&cur->rb_node, &cache->rb_root);			btrfs_backref_free_node(cache, cur);		}	}	return ret;} /* * Build backref tree for a given tree block. Root of the backref tree * corresponds the tree block, leaves of the backref tree correspond roots of * b-trees that reference the tree block. * * The basic idea of this function is check backrefs of a given block to find * upper level blocks that reference the block, and then check backrefs of * these upper level blocks recursively. The recursion stops when tree root is * reached or backrefs for the block is cached. * * NOTE: if we find that backrefs for a block are cached, we know backrefs for * all upper level blocks that directly/indirectly reference the block are also * cached. */static noinline_for_stack struct btrfs_backref_node *build_backref_tree(			struct btrfs_trans_handle *trans,

Lines 1–500 of 6283. Load more