// 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)