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 "ctree.h"
#include "disk-io.h"
#include "locking.h"
#include "delayed-ref.h"
#include "ref-verify.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 struct block_entry *insert_block_entry(struct rb_root *root,
					      struct block_entry *be)
{
	struct rb_node **p = &root->rb_node;
	struct rb_node *parent_node = NULL;
	struct block_entry *entry;

	while (*p) {
		parent_node = *p;
		entry = rb_entry(parent_node, struct block_entry, node);
		if (entry->bytenr > be->bytenr)
			p = &(*p)->rb_left;
		else if (entry->bytenr < be->bytenr)
			p = &(*p)->rb_right;
		else
			return entry;
	}

	rb_link_node(&be->node, parent_node, p);
	rb_insert_color(&be->node, root);
	return NULL;
}

static struct block_entry *lookup_block_entry(struct rb_root *root, u64 bytenr)
{
	struct rb_node *n;
	struct block_entry *entry = NULL;

	n = root->rb_node;
	while (n) {
		entry = rb_entry(n, struct block_entry, node);
		if (entry->bytenr < bytenr)
			n = n->rb_right;
		else if (entry->bytenr > bytenr)
			n = n->rb_left;
		else
			return entry;
	}
	return NULL;
}

static struct root_entry *insert_root_entry(struct rb_root *root,
					    struct root_entry *re)
{
	struct rb_node **p = &root->rb_node;
	struct rb_node *parent_node = NULL;
	struct root_entry *entry;

	while (*p) {
		parent_node = *p;
		entry = rb_entry(parent_node, struct root_entry, node);
		if (entry->root_objectid > re->root_objectid)
			p = &(*p)->rb_left;
		else if (entry->root_objectid < re->root_objectid)
			p = &(*p)->rb_right;
		else
			return entry;
	}

	rb_link_node(&re->node, parent_node, p);
	rb_insert_color(&re->node, root);
	return NULL;

}

static int comp_refs(struct ref_entry *ref1, struct ref_entry *ref2)
{
	if (ref1->root_objectid < ref2->root_objectid)
		return -1;
	if (ref1->root_objectid > ref2->root_objectid)
		return 1;
	if (ref1->parent < ref2->parent)
		return -1;
	if (ref1->parent > ref2->parent)
		return 1;
	if (ref1->owner < ref2->owner)
		return -1;
	if (ref1->owner > ref2->owner)
		return 1;
	if (ref1->offset < ref2->offset)
		return -1;
	if (ref1->offset > ref2->offset)
		return 1;
	return 0;
}

static struct ref_entry *insert_ref_entry(struct rb_root *root,
					  struct ref_entry *ref)
{
	struct rb_node **p = &root->rb_node;
	struct rb_node *parent_node = NULL;
	struct ref_entry *entry;
	int cmp;

	while (*p) {
		parent_node = *p;
		entry = rb_entry(parent_node, struct ref_entry, node);
		cmp = comp_refs(entry, ref);
		if (cmp > 0)
			p = &(*p)->rb_left;
		else if (cmp < 0)
			p = &(*p)->rb_right;
		else
			return entry;
	}

	rb_link_node(&ref->node, parent_node