path: root/fs/btrfs/ref-verify.c

// SPDX-License-Identifier: GPL-2.0
/*
 * Copyright (C) 2014 Facebook.  All rights reserved.
 */

#include <linux/sched.h>
#include <linux/stacktrace.h>
#include "messages.h"
#include "ctree.h"
#include "disk-io.h"
#include "locking.h"
#include "delayed-ref.h"
#include "ref-verify.h"
#include "fs.h"
#include "accessors.h"

/*
 * Used to keep track the roots and number of refs each root has for a given
 * bytenr.  This just tracks the number of direct references, no shared
 * references.
 */
struct root_entry {
	u64 root_objectid;
	u64 num_refs;
	struct rb_node node;
};

/*
 * These are meant to represent what should exist in the extent tree, these can
 * be used to verify the extent tree is consistent as these should all match
 * what the extent tree says.
 */
struct ref_entry {
	u64 root_objectid;
	u64 parent;
	u64 owner;
	u64 offset;
	u64 num_refs;
	struct rb_node node;
};

#define MAX_TRACE	16

/*
 * Whenever we add/remove a reference we record the action.  The action maps
 * back to the delayed ref action.  We hold the ref we are changing in the
 * action so we can account for the history properly, and we record the root we
 * were called with since it could be different from ref_root.  We also store
 * stack traces because that's how I roll.
 */
struct ref_action {
	int action;
	u64 root;
	struct ref_entry ref;
	struct list_head list;
	unsigned long trace[MAX_TRACE];
	unsigned int trace_len;
};

/*
 * One of these for every block we reference, it holds the roots and references
 * to it as well as all of the ref actions that have occurred to it.  We never
 * free it until we unmount the file system in order to make sure re-allocations
 * are happening properly.
 */
struct block_entry {
	u64 bytenr;
	u64 len;
	u64 num_refs;
	int metadata;
	int from_disk;
	struct rb_root roots;
	struct rb_root refs;
	struct rb_node node;
	struct list_head actions;
};

static int block_entry_bytenr_key_cmp(const void *key, const struct rb_node *node)
{
	const u64 *bytenr = key;
	const struct block_entry *entry = rb_entry(node, struct block_entry, node);

	if (entry->bytenr < *bytenr)
		return 1;
	else if (entry->bytenr > *bytenr)
		return -1;

	return 0;
}

static int block_entry_bytenr_cmp(struct rb_node *new, const struct rb_node *existing)
{
	const struct block_entry *new_entry = rb_entry(new, struct block_entry, node);

	return block_entry_bytenr_key_cmp(&new_entry->bytenr, existing);
}

static struct block_entry *insert_block_entry(struct rb_root *root,
					      struct block_entry *be)
{
	struct rb_node *node;

	node = rb_find_add(&be->node, root, block_entry_bytenr_cmp);
	return rb_entry_safe(node, struct block_entry, node);
}

static struct block_entry *lookup_block_entry(struct rb_root *root, u64 bytenr)
{
	struct rb_node *node;

	node = rb_find(&bytenr, root, block_entry_bytenr_key_cmp);
	return rb_entry_safe(node, struct block_entry, node);
}

static int root_entry_root_objectid_key_cmp(const void *key, const struct rb_node *node)
{
	const u64 *objectid = key;
	const struct root_entry *entry = rb_entry(node, struct root_entry, node);

	if (entry->root_objectid < *objectid)
		return 1;
	else if (entry->root_objectid > *objectid)
		return -1;

	return 0;
}

static int root_entry_root_objectid_cmp(struct rb_node *new, const struct rb_node *existing)
{
	const struct root_entry *new_entry = rb_entry(new, struct root_entry, node);

	return root_entry_root_objectid_key_cmp(&new_entry->root_objectid, existing);
}

static struct root_entry *insert_root_entry(struct rb_root *root,
					    struct root_entry *re)
{
	struct rb_node *node;

	node = rb_find_add(&re->node, root, root_entry_root_objectid_cmp);
	return rb_entry_safe(node, struct root_entry, node);
}

static int comp_refs(struct ref_entry *ref1, struct