// SPDX-License-Identifier: GPL-2.0
/*
* f2fs extent cache support
*
* Copyright (c) 2015 Motorola Mobility
* Copyright (c) 2015 Samsung Electronics
* Authors: Jaegeuk Kim <jaegeuk@kernel.org>
* Chao Yu <chao2.yu@samsung.com>
*/
#include <linux/fs.h>
#include <linux/f2fs_fs.h>
#include "f2fs.h"
#include "node.h"
#include <trace/events/f2fs.h>
static struct rb_entry *__lookup_rb_tree_fast(struct rb_entry *cached_re,
unsigned int ofs)
{
if (cached_re) {
if (cached_re->ofs <= ofs &&
cached_re->ofs + cached_re->len > ofs) {
return cached_re;
}
}
return NULL;
}
static struct rb_entry *__lookup_rb_tree_slow(struct rb_root_cached *root,
unsigned int ofs)
{
struct rb_node *node = root->rb_root.rb_node;
struct rb_entry *re;
while (node) {
re = rb_entry(node, struct rb_entry, rb_node);
if (ofs < re->ofs)
node = node->rb_left;
else if (ofs >= re->ofs + re->len)
node = node->rb_right;
else
return re;
}
return NULL;
}
struct rb_entry *f2fs_lookup_rb_tree(struct rb_root_cached *root,
struct rb_entry *cached_re, unsigned int ofs)
{
struct rb_entry *re;
re = __lookup_rb_tree_fast(cached_re, ofs);
if (!re)
return __lookup_rb_tree_slow(root, ofs);
return re;
}
struct rb_node **f2fs_lookup_rb_tree_for_insert(struct f2fs_sb_info *sbi,
struct rb_root_cached *root,
struct rb_node **parent,
unsigned int ofs, bool *leftmost)
{
struct rb_node **p = &root->rb_root.rb_node;
struct rb_entry *re;
while (*p) {
*parent = *p;
re = rb_entry(*parent, struct rb_entry, rb_node);
if (ofs < re->ofs) {
p = &(*p)->rb_left;
} else if (ofs >= re->ofs + re->len) {
p = &(*p)->rb_right;
*leftmost = false;
} else {
f2fs_bug_on(sbi, 1);
}
}
return p;
}
/*
* lookup rb entry in position of @ofs in rb-tree,
* if hit, return the entry, otherwise, return NULL
* @prev_ex: extent before ofs
* @next_ex: extent after ofs
* @insert_p: insert point for new extent at ofs
* in order to simpfy the insertion after.
* tree must stay unchanged between lookup and insertion.
*/
struct rb_entry *f2fs_lookup_rb_tree_ret(struct rb_root_cached *root,
struct rb_entry *cached_re,
unsigned int ofs,
struct rb_entry **prev_entry,
struct rb_entry **next_entry,
struct rb_node ***insert_p,
struct rb_node **insert_parent,
bool force, bool *leftmost)
{
struct rb_node **pnode = &root->rb_root.rb_node;
struct rb_node *parent = NULL, *tmp_node;
struct rb_entry *re = cached_re;
*insert_p = NULL;
*insert_parent = NULL;
*prev_entry = NULL;
*next_entry = NULL;
if (RB_EMPTY_ROOT(&root->rb_root))
return NULL;
if (re) {
if (re->ofs <= ofs && re->ofs + re->len > ofs)
goto lookup_neighbors;
}
if (leftmost)
*leftmost = true;
while (*pnode) {
parent = *pnode;
re = rb_entry(*pnode, struct rb_entry, rb_node);
if (ofs < re->ofs) {
pnode = &(*pnode)->rb_left;
} else if (ofs >= re->ofs + re->len) {
pnode = &(*pnode)->rb_right;
if (leftmost)
*leftmost = false;
} else {
goto lookup_neighbors;
}
}
*insert_p = pnode;
*insert_parent = parent;
re = rb_entry(parent, struct rb_entry, rb_node);
tmp_node = parent;
if (parent && ofs > re->ofs)
tmp_node = rb_next(parent);
*next_entry = rb_entry_safe(tmp_node, struct rb_entry, rb_node);
tmp_node = parent;
if (parent && ofs < re->ofs)
tmp_node = rb_prev(parent);
*prev_entry = rb_entry_safe(tmp_node, struct rb_entry, rb_node);
return NULL;
lookup_neighbors:
if (ofs == re->ofs || force) {
/* lookup prev node for merging backward later */
tmp_node = rb_prev(&re->rb_