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

/* Just an arbitrary number so we can be sure this happened */
#define BACKREF_FOUND_SHARED 6

struct extent_inode_elem {
        u64 inum;
        u64 offset;
        struct extent_inode_elem *next;
};

static int check_extent_in_eb(const struct btrfs_key *key,
                              const struct extent_buffer *eb,
                              const struct btrfs_file_extent_item *fi,
                              u64 extent_item_pos,
                              struct extent_inode_elem **eie,
                              bool ignore_offset)
{
        u64 offset = 0;
        struct extent_inode_elem *e;

        if (!ignore_offset &&
            !btrfs_file_extent_compression(eb, fi) &&
            !btrfs_file_extent_encryption(eb, fi) &&
            !btrfs_file_extent_other_encoding(eb, fi)) {
                u64 data_offset;
                u64 data_len;

                data_offset = btrfs_file_extent_offset(eb, fi);
                data_len = btrfs_file_extent_num_bytes(eb, fi);

                if (extent_item_pos < data_offset ||
                    extent_item_pos >= data_offset + data_len)
                        return 1;
                offset = extent_item_pos - data_offset;
        }

        e = kmalloc(sizeof(*e), GFP_NOFS);
        if (!e)
                return -ENOMEM;

        e->next = *eie;
        e->inum = key->objectid;
        e->offset = key->offset + offset;
        *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(const struct extent_buffer *eb,
                             u64 wanted_disk_byte, u64 extent_item_pos,
                             struct extent_inode_elem **eie,
                             bool ignore_offset)
{
        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 != wanted_disk_byte)
                        continue;

                ret = check_extent_in_eb(&key, eb, fi, extent_item_pos, eie, ignore_offset);
                if (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 {
        u64 root_objectid;
        u64 inum;
        int share_count;
};

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,
                                        SLAB_MEM_SPREAD,
                                        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(struct prelim_ref *ref1,
                              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 void update_share_count(struct share_check *sc, int oldcount,
                               int newcount)
{
        if ((!sc) || (oldcount == 0 && newcount < 1))
                return;

        if (oldcount > 0 && newcount < 1)
                sc->share_count--;
        else if (oldcount < 1 && newcount > 0)
                sc->share_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 **p;
        struct rb_node *parent = NULL;
        struct prelim_ref *ref;
        int result;
        bool leftmost = true;

        root = &preftree->root;
        p = &root->rb_root.rb_node;

        while (*p) {
                parent = *p;
                ref =