// SPDX-License-Identifier: GPL-2.0/* * Copyright (C) 2011 STRATO.  All rights reserved. */ #include <linux/mm.h>#include <linux/rbtree.h>#include <trace/events/btrfs.h>#include "ctree.h"#include "disk-io.h"#include "backref.h"#include "ulist.h"#include "transaction.h"#include "delayed-ref.h"#include "locking.h"#include "misc.h"#include "tree-mod-log.h"#include "fs.h"#include "accessors.h"#include "extent-tree.h"#include "relocation.h"#include "tree-checker.h" /* Just arbitrary numbers so we can be sure one of these happened. */#define BACKREF_FOUND_SHARED     6#define BACKREF_FOUND_NOT_SHARED 7 struct extent_inode_elem {	u64 inum;	u64 offset;	u64 num_bytes;	struct extent_inode_elem *next;}; static int check_extent_in_eb(struct btrfs_backref_walk_ctx *ctx,			      const struct btrfs_key *key,			      const struct extent_buffer *eb,			      const struct btrfs_file_extent_item *fi,			      struct extent_inode_elem **eie){	const u64 data_len = btrfs_file_extent_num_bytes(eb, fi);	u64 offset = key->offset;	struct extent_inode_elem *e;	const u64 *root_ids;	int root_count;	bool cached; 	if (!ctx->ignore_extent_item_pos &&	    !btrfs_file_extent_compression(eb, fi) &&	    !btrfs_file_extent_encryption(eb, fi) &&	    !btrfs_file_extent_other_encoding(eb, fi)) {		u64 data_offset; 		data_offset = btrfs_file_extent_offset(eb, fi); 		if (ctx->extent_item_pos < data_offset ||		    ctx->extent_item_pos >= data_offset + data_len)			return 1;		offset += ctx->extent_item_pos - data_offset;	} 	if (!ctx->indirect_ref_iterator || !ctx->cache_lookup)		goto add_inode_elem; 	cached = ctx->cache_lookup(eb->start, ctx->user_ctx, &root_ids,				   &root_count);	if (!cached)		goto add_inode_elem; 	for (int i = 0; i < root_count; i++) {		int ret; 		ret = ctx->indirect_ref_iterator(key->objectid, offset,						 data_len, root_ids[i],						 ctx->user_ctx);		if (ret)			return ret;	} add_inode_elem:	e = kmalloc_obj(*e, GFP_NOFS);	if (!e)		return -ENOMEM; 	e->next = *eie;	e->inum = key->objectid;	e->offset = offset;	e->num_bytes = data_len;	*eie = e; 	return 0;} static void free_inode_elem_list(struct extent_inode_elem *eie){	struct extent_inode_elem *eie_next; 	for (; eie; eie = eie_next) {		eie_next = eie->next;		kfree(eie);	}} static int find_extent_in_eb(struct btrfs_backref_walk_ctx *ctx,			     const struct extent_buffer *eb,			     struct extent_inode_elem **eie){	u64 disk_byte;	struct btrfs_key key;	struct btrfs_file_extent_item *fi;	int slot;	int nritems;	int extent_type;	int ret; 	/*	 * from the shared data ref, we only have the leaf but we need	 * the key. thus, we must look into all items and see that we	 * find one (some) with a reference to our extent item.	 */	nritems = btrfs_header_nritems(eb);	for (slot = 0; slot < nritems; ++slot) {		btrfs_item_key_to_cpu(eb, &key, slot);		if (key.type != BTRFS_EXTENT_DATA_KEY)			continue;		fi = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);		extent_type = btrfs_file_extent_type(eb, fi);		if (extent_type == BTRFS_FILE_EXTENT_INLINE)			continue;		/* don't skip BTRFS_FILE_EXTENT_PREALLOC, we can handle that */		disk_byte = btrfs_file_extent_disk_bytenr(eb, fi);		if (disk_byte != ctx->bytenr)			continue; 		ret = check_extent_in_eb(ctx, &key, eb, fi, eie);		if (ret == BTRFS_ITERATE_EXTENT_INODES_STOP || ret < 0)			return ret;	} 	return 0;} struct preftree {	struct rb_root_cached root;	unsigned int count;}; #define PREFTREE_INIT	{ .root = RB_ROOT_CACHED, .count = 0 } struct preftrees {	struct preftree direct;    /* BTRFS_SHARED_[DATA|BLOCK]_REF_KEY */	struct preftree indirect;  /* BTRFS_[TREE_BLOCK|EXTENT_DATA]_REF_KEY */	struct preftree indirect_missing_keys;}; /* * Checks for a shared extent during backref search. * * The share_count tracks prelim_refs (direct and indirect) having a * ref->count >0: *  - incremented when a ref->count transitions to >0 *  - decremented when a ref->count transitions to <1 */struct share_check {	struct btrfs_backref_share_check_ctx *ctx;	struct btrfs_root *root;	u64 inum;	u64 data_bytenr;	u64 data_extent_gen;	/*	 * Counts number of inodes that refer to an extent (different inodes in	 * the same root or different roots) that we could find. The sharedness	 * check typically stops once this counter gets greater than 1, so it	 * may not reflect the total number of inodes.	 */	int share_count;	/*	 * The number of times we found our inode refers to the data extent we	 * are determining the sharedness. In other words, how many file extent	 * items we could find for our inode that point to our target data	 * extent. The value we get here after finishing the extent sharedness	 * check may be smaller than reality, but if it ends up being greater	 * than 1, then we know for sure the inode has multiple file extent	 * items that point to our inode, and we can safely assume it's useful	 * to cache the sharedness check result.	 */	int self_ref_count;	bool have_delayed_delete_refs;}; static inline int extent_is_shared(struct share_check *sc){	return (sc && sc->share_count > 1) ? BACKREF_FOUND_SHARED : 0;} static struct kmem_cache *btrfs_prelim_ref_cache; int __init btrfs_prelim_ref_init(void){	btrfs_prelim_ref_cache = kmem_cache_create("btrfs_prelim_ref",					sizeof(struct prelim_ref), 0, 0, NULL);	if (!btrfs_prelim_ref_cache)		return -ENOMEM;	return 0;} void __cold btrfs_prelim_ref_exit(void){	kmem_cache_destroy(btrfs_prelim_ref_cache);} static void free_pref(struct prelim_ref *ref){	kmem_cache_free(btrfs_prelim_ref_cache, ref);} /* * Return 0 when both refs are for the same block (and can be merged). * A -1 return indicates ref1 is a 'lower' block than ref2, while 1 * indicates a 'higher' block. */static int prelim_ref_compare(const struct prelim_ref *ref1,			      const struct prelim_ref *ref2){	if (ref1->level < ref2->level)		return -1;	if (ref1->level > ref2->level)		return 1;	if (ref1->root_id < ref2->root_id)		return -1;	if (ref1->root_id > ref2->root_id)		return 1;	if (ref1->key_for_search.type < ref2->key_for_search.type)		return -1;	if (ref1->key_for_search.type > ref2->key_for_search.type)		return 1;	if (ref1->key_for_search.objectid < ref2->key_for_search.objectid)		return -1;	if (ref1->key_for_search.objectid > ref2->key_for_search.objectid)		return 1;	if (ref1->key_for_search.offset < ref2->key_for_search.offset)		return -1;	if (ref1->key_for_search.offset > ref2->key_for_search.offset)		return 1;	if (ref1->parent < ref2->parent)		return -1;	if (ref1->parent > ref2->parent)		return 1; 	return 0;} static int prelim_ref_rb_add_cmp(const struct rb_node *new,				 const struct rb_node *exist){	const struct prelim_ref *ref_new =		rb_entry(new, struct prelim_ref, rbnode);	const struct prelim_ref *ref_exist =		rb_entry(exist, struct prelim_ref, rbnode); 	/*	 * prelim_ref_compare() expects the first parameter as the existing one,	 * different from the rb_find_add_cached() order.	 */	return prelim_ref_compare(ref_exist, ref_new);} static void update_share_count(struct share_check *sc, int oldcount,			       int newcount, const struct prelim_ref *newref){	if ((!sc) || (oldcount == 0 && newcount < 1))		return; 	if (oldcount > 0 && newcount < 1)		sc->share_count--;	else if (oldcount < 1 && newcount > 0)		sc->share_count++; 	if (newref->root_id == btrfs_root_id(sc->root) &&	    newref->wanted_disk_byte == sc->data_bytenr &&	    newref->key_for_search.objectid == sc->inum)		sc->self_ref_count += newref->count;} /* * Add @newref to the @root rbtree, merging identical refs. * * Callers should assume that newref has been freed after calling. */static void prelim_ref_insert(const struct btrfs_fs_info *fs_info,			      struct preftree *preftree,			      struct prelim_ref *newref,			      struct share_check *sc){	struct rb_root_cached *root;	struct rb_node *exist; 	root = &preftree->root;	exist = rb_find_add_cached(&newref->rbnode, root, prelim_ref_rb_add_cmp);	if (exist) {		struct prelim_ref *ref = rb_entry(exist, struct prelim_ref, rbnode);		/* Identical refs, merge them and free @newref */		struct extent_inode_elem *eie = ref->inode_list; 		while (eie && eie->next)			eie = eie->next; 		if (!eie)			ref->inode_list = newref->inode_list;		else			eie->next = newref->inode_list;		trace_btrfs_prelim_ref_merge(fs_info, ref, newref,							preftree->count);		/*		 * A delayed ref can have newref->count < 0.		 * The ref->count is updated to follow any		 * BTRFS_[ADD|DROP]_DELAYED_REF actions.		 */		update_share_count(sc, ref->count,					ref->count + newref->count, newref);		ref->count += newref->count;		free_pref(newref);		return;	} 	update_share_count(sc, 0, newref->count, newref);	preftree->count++;	trace_btrfs_prelim_ref_insert(fs_info, newref, NULL, preftree->count);} /* * Release the entire tree.  We don't care about internal consistency so * just free everything and then reset the tree root. */static void prelim_release(struct preftree *preftree){	struct prelim_ref *ref, *next_ref; 	rbtree_postorder_for_each_entry_safe(ref, next_ref,					     &preftree->root.rb_root, rbnode) {		free_inode_elem_list(ref->inode_list);		free_pref(ref);	} 	preftree->root = RB_ROOT_CACHED;	preftree->count = 0;} /* * the rules for all callers of this function are: * - obtaining the parent is the goal * - if you add a key, you must know that it is a correct key * - if you cannot add the parent or a correct key, then we will look into the *   block later to set a correct key * * delayed refs * ============ *        backref type | shared | indirect | shared | indirect * information         |   tree |     tree |   data |     data * --------------------+--------+----------+--------+---------- *      parent logical |    y   |     -    |    -   |     - *      key to resolve |    -   |     y    |    y   |     y *  tree block logical |    -   |     -    |    -   |     - *  root for resolving |    y   |     y    |    y   |     y * * - column 1:       we've the parent -> done * - column 2, 3, 4: we use the key to find the parent * * on disk refs (inline or keyed) * ============================== *        backref type | shared | indirect | shared | indirect * information         |   tree |     tree |   data |     data * --------------------+--------+----------+--------+---------- *      parent logical |    y   |     -    |    y   |     - *      key to resolve |    -   |     -    |    -   |     y *  tree block logical |    y   |     y    |    y   |     y *  root for resolving |    -   |     y    |    y   |     y * * - column 1, 3: we've the parent -> done * - column 2:    we take the first key from the block to find the parent *                (see add_missing_keys) * - column 4:    we use the key to find the parent * * additional information that's available but not required to find the parent * block might help in merging entries to gain some speed. */static int add_prelim_ref(const struct btrfs_fs_info *fs_info,			  struct preftree *preftree, u64 root_id,			  const struct btrfs_key *key, int level, u64 parent,			  u64 wanted_disk_byte, int count,			  struct share_check *sc, gfp_t gfp_mask){	struct prelim_ref *ref; 	if (root_id == BTRFS_DATA_RELOC_TREE_OBJECTID)		return 0; 	ref = kmem_cache_alloc(btrfs_prelim_ref_cache, gfp_mask);	if (!ref)		return -ENOMEM; 	ref->root_id = root_id;	if (key)		ref->key_for_search = *key;	else		memset(&ref->key_for_search, 0, sizeof(ref->key_for_search)); 	ref->inode_list = NULL;	ref->level = level;	ref->count = count;	ref->parent = parent;	ref->wanted_disk_byte = wanted_disk_byte;	prelim_ref_insert(fs_info, preftree, ref, sc);	return extent_is_shared(sc);} /* direct refs use root == 0, key == NULL */static int add_direct_ref(const struct btrfs_fs_info *fs_info,			  struct preftrees *preftrees, int level, u64 parent,			  u64 wanted_disk_byte, int count,			  struct share_check *sc, gfp_t gfp_mask){	return add_prelim_ref(fs_info, &preftrees->direct, 0, NULL, level,			      parent, wanted_disk_byte, count, sc, gfp_mask);} /* indirect refs use parent == 0 */static int add_indirect_ref(const struct btrfs_fs_info *fs_info,			    struct preftrees *preftrees, u64 root_id,			    const struct btrfs_key *key, int level,			    u64 wanted_disk_byte, int count,			    struct share_check *sc, gfp_t gfp_mask){	struct preftree *tree = &preftrees->indirect; 	if (!key)		tree = &preftrees->indirect_missing_keys;	return add_prelim_ref(fs_info, tree, root_id, key, level, 0,			      wanted_disk_byte, count, sc, gfp_mask);} static int is_shared_data_backref(struct preftrees *preftrees, u64 bytenr){	struct rb_node **p = &preftrees->direct.root.rb_root.rb_node;	struct rb_node *parent = NULL;	struct prelim_ref *ref = NULL;	struct prelim_ref target = {};	int result; 	target.parent = bytenr; 	while (*p) {		parent = *p;		ref = rb_entry(parent, struct prelim_ref, rbnode);		result = prelim_ref_compare(ref, &target); 		if (result < 0)			p = &(*p)->rb_left;		else if (result > 0)			p = &(*p)->rb_right;		else			return 1;	}	return 0;} static int add_all_parents(struct btrfs_backref_walk_ctx *ctx,			   struct btrfs_root *root, struct btrfs_path *path,			   struct ulist *parents,			   struct preftrees *preftrees, struct prelim_ref *ref,			   int level){	int ret = 0;	int slot;	struct extent_buffer *eb;	struct btrfs_key key;	struct btrfs_key *key_for_search = &ref->key_for_search;	struct btrfs_file_extent_item *fi;	struct extent_inode_elem *eie = NULL, *old = NULL;	u64 disk_byte;	u64 wanted_disk_byte = ref->wanted_disk_byte;	u64 count = 0;	u64 data_offset;	u8 type; 	if (level != 0) {		eb = path->nodes[level];		ret = ulist_add(parents, eb->start, 0, GFP_NOFS);		if (ret < 0)			return ret;		return 0;	} 	/*	 * 1. We normally enter this function with the path already pointing to	 *    the first item to check. But sometimes, we may enter it with	 *    slot == nritems.	 * 2. We are searching for normal backref but bytenr of this leaf	 *    matches shared data backref	 * 3. The leaf owner is not equal to the root we are searching

Lines 1–500 of 3697. Load more