extent_cache.c

   1// SPDX-License-Identifier: GPL-2.0
   2/*
   3 * f2fs extent cache support
   4 *
   5 * Copyright (c) 2015 Motorola Mobility
   6 * Copyright (c) 2015 Samsung Electronics
   7 * Authors: Jaegeuk Kim <jaegeuk@kernel.org>
   8 *          Chao Yu <chao2.yu@samsung.com>
   9 *
  10 * block_age-based extent cache added by:
  11 * Copyright (c) 2022 xiaomi Co., Ltd.
  12 *             http://www.xiaomi.com/
  13 */
  14
  15#include <linux/fs.h>
  16#include <linux/f2fs_fs.h>
  17
  18#include "f2fs.h"
  19#include "node.h"
  20#include <trace/events/f2fs.h>
  21
  22bool sanity_check_extent_cache(struct inode *inode, struct folio *ifolio)
  23{
  24	struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
  25	struct f2fs_extent *i_ext = &F2FS_INODE(ifolio)->i_ext;
  26	struct extent_info ei;
  27	int devi;
  28
  29	get_read_extent_info(&ei, i_ext);
  30
  31	if (!ei.len)
  32		return true;
  33
  34	if (!f2fs_is_valid_blkaddr(sbi, ei.blk, DATA_GENERIC_ENHANCE) ||
  35	    !f2fs_is_valid_blkaddr(sbi, ei.blk + ei.len - 1,
  36					DATA_GENERIC_ENHANCE)) {
  37		f2fs_warn(sbi, "%s: inode (ino=%lx) extent info [%u, %u, %u] is incorrect, run fsck to fix",
  38			  __func__, inode->i_ino,
  39			  ei.blk, ei.fofs, ei.len);
  40		return false;
  41	}
  42
  43	if (!IS_DEVICE_ALIASING(inode))
  44		return true;
  45
  46	for (devi = 0; devi < sbi->s_ndevs; devi++) {
  47		if (FDEV(devi).start_blk != ei.blk ||
  48				FDEV(devi).end_blk != ei.blk + ei.len - 1)
  49			continue;
  50
  51		if (devi == 0) {
  52			f2fs_warn(sbi,
  53			    "%s: inode (ino=%lx) is an alias of meta device",
  54			    __func__, inode->i_ino);
  55			return false;
  56		}
  57
  58		if (bdev_is_zoned(FDEV(devi).bdev)) {
  59			f2fs_warn(sbi,
  60			    "%s: device alias inode (ino=%lx)'s extent info "
  61			    "[%u, %u, %u] maps to zoned block device",
  62			    __func__, inode->i_ino, ei.blk, ei.fofs, ei.len);
  63			return false;
  64		}
  65		return true;
  66	}
  67
  68	f2fs_warn(sbi, "%s: device alias inode (ino=%lx)'s extent info "
  69			"[%u, %u, %u] is inconsistent w/ any devices",
  70			__func__, inode->i_ino, ei.blk, ei.fofs, ei.len);
  71	return false;
  72}
  73
  74static void __set_extent_info(struct extent_info *ei,
  75				unsigned int fofs, unsigned int len,
  76				block_t blk, bool keep_clen,
  77				unsigned long age, unsigned long last_blocks,
  78				enum extent_type type)
  79{
  80	ei->fofs = fofs;
  81	ei->len = len;
  82
  83	if (type == EX_READ) {
  84		ei->blk = blk;
  85		if (keep_clen)
  86			return;
  87#ifdef CONFIG_F2FS_FS_COMPRESSION
  88		ei->c_len = 0;
  89#endif
  90	} else if (type == EX_BLOCK_AGE) {
  91		ei->age = age;
  92		ei->last_blocks = last_blocks;
  93	}
  94}
  95
  96static bool __init_may_extent_tree(struct inode *inode, enum extent_type type)
  97{
  98	if (type == EX_READ)
  99		return test_opt(F2FS_I_SB(inode), READ_EXTENT_CACHE) &&
 100			S_ISREG(inode->i_mode);
 101	if (type == EX_BLOCK_AGE)
 102		return test_opt(F2FS_I_SB(inode), AGE_EXTENT_CACHE) &&
 103			(S_ISREG(inode->i_mode) || S_ISDIR(inode->i_mode));
 104	return false;
 105}
 106
 107static bool __may_extent_tree(struct inode *inode, enum extent_type type)
 108{
 109	if (IS_DEVICE_ALIASING(inode) && type == EX_READ)
 110		return true;
 111
 112	/*
 113	 * for recovered files during mount do not create extents
 114	 * if shrinker is not registered.
 115	 */
 116	if (list_empty(&F2FS_I_SB(inode)->s_list))
 117		return false;
 118
 119	if (!__init_may_extent_tree(inode, type))
 120		return false;
 121
 122	if (type == EX_READ) {
 123		if (is_inode_flag_set(inode, FI_NO_EXTENT))
 124			return false;
 125		if (is_inode_flag_set(inode, FI_COMPRESSED_FILE) &&
 126				 !f2fs_sb_has_readonly(F2FS_I_SB(inode)))
 127			return false;
 128	} else if (type == EX_BLOCK_AGE) {
 129		if (is_inode_flag_set(inode, FI_COMPRESSED_FILE))
 130			return false;
 131		if (file_is_cold(inode))
 132			return false;
 133	}
 134	return true;
 135}
 136
 137static void __try_update_largest_extent(struct extent_tree *et,
 138						struct extent_node *en)
 139{
 140	if (et->type != EX_READ)
 141		return;
 142	if (en->ei.len <= et->largest.len)
 143		return;
 144
 145	et->largest = en->ei;
 146	et->largest_updated = true;
 147}
 148
 149static bool __is_extent_mergeable(struct extent_info *back,
 150		struct extent_info *front, enum extent_type type)
 151{
 152	if (type == EX_READ) {
 153#ifdef CONFIG_F2FS_FS_COMPRESSION
 154		if (back->c_len && back->len != back->c_len)
 155			return false;
 156		if (front->c_len && front->len != front->c_len)
 157			return false;
 158#endif
 159		return (back->fofs + back->len == front->fofs &&
 160				back->blk + back->len == front->blk);
 161	} else if (type == EX_BLOCK_AGE) {
 162		return (back->fofs + back->len == front->fofs &&
 163			abs(back->age - front->age) <= SAME_AGE_REGION &&
 164			abs(back->last_blocks - front->last_blocks) <=
 165							SAME_AGE_REGION);
 166	}
 167	return false;
 168}
 169
 170static bool __is_back_mergeable(struct extent_info *cur,
 171		struct extent_info *back, enum extent_type type)
 172{
 173	return __is_extent_mergeable(back, cur, type);
 174}
 175
 176static bool __is_front_mergeable(struct extent_info *cur,
 177		struct extent_info *front, enum extent_type type)
 178{
 179	return __is_extent_mergeable(cur, front, type);
 180}
 181
 182static struct extent_node *__lookup_extent_node(struct rb_root_cached *root,
 183			struct extent_node *cached_en, unsigned int fofs)
 184{
 185	struct rb_node *node = root->rb_root.rb_node;
 186	struct extent_node *en;
 187
 188	/* check a cached entry */
 189	if (cached_en && cached_en->ei.fofs <= fofs &&
 190			cached_en->ei.fofs + cached_en->ei.len > fofs)
 191		return cached_en;
 192
 193	/* check rb_tree */
 194	while (node) {
 195		en = rb_entry(node, struct extent_node, rb_node);
 196
 197		if (fofs < en->ei.fofs)
 198			node = node->rb_left;
 199		else if (fofs >= en->ei.fofs + en->ei.len)
 200			node = node->rb_right;
 201		else
 202			return en;
 203	}
 204	return NULL;
 205}
 206
 207/*
 208 * lookup rb entry in position of @fofs in rb-tree,
 209 * if hit, return the entry, otherwise, return NULL
 210 * @prev_ex: extent before fofs
 211 * @next_ex: extent after fofs
 212 * @insert_p: insert point for new extent at fofs
 213 * in order to simplify the insertion after.
 214 * tree must stay unchanged between lookup and insertion.
 215 */
 216static struct extent_node *__lookup_extent_node_ret(struct rb_root_cached *root,
 217				struct extent_node *cached_en,
 218				unsigned int fofs,
 219				struct extent_node **prev_entry,
 220				struct extent_node **next_entry,
 221				struct rb_node ***insert_p,
 222				struct rb_node **insert_parent,
 223				bool *leftmost)
 224{
 225	struct rb_node **pnode = &root->rb_root.rb_node;
 226	struct rb_node *parent = NULL, *tmp_node;
 227	struct extent_node *en = cached_en;
 228
 229	*insert_p = NULL;
 230	*insert_parent = NULL;
 231	*prev_entry = NULL;
 232	*next_entry = NULL;
 233
 234	if (RB_EMPTY_ROOT(&root->rb_root))
 235		return NULL;
 236
 237	if (en && en->ei.fofs <= fofs && en->ei.fofs + en->ei.len > fofs)
 238		goto lookup_neighbors;
 239
 240	*leftmost = true;
 241
 242	while (*pnode) {
 243		parent = *pnode;
 244		en = rb_entry(*pnode, struct extent_node, rb_node);
 245
 246		if (fofs < en->ei.fofs) {
 247			pnode = &(*pnode)->rb_left;
 248		} else if (fofs >= en->ei.fofs + en->ei.len) {
 249			pnode = &(*pnode)->rb_right;
 250			*leftmost = false;
 251		} else {
 252			goto lookup_neighbors;
 253		}
 254	}
 255
 256	*insert_p = pnode;
 257	*insert_parent = parent;
 258
 259	en = rb_entry(parent, struct extent_node, rb_node);
 260	tmp_node = parent;
 261	if (parent && fofs > en->ei.fofs)
 262		tmp_node = rb_next(parent);
 263	*next_entry = rb_entry_safe(tmp_node, struct extent_node, rb_node);
 264
 265	tmp_node = parent;
 266	if (parent && fofs < en->ei.fofs)
 267		tmp_node = rb_prev(parent);
 268	*prev_entry = rb_entry_safe(tmp_node, struct extent_node, rb_node);
 269	return NULL;
 270
 271lookup_neighbors:
 272	if (fofs == en->ei.fofs) {
 273		/* lookup prev node for merging backward later */
 274		tmp_node = rb_prev(&en->rb_node);
 275		*prev_entry = rb_entry_safe(tmp_node,
 276					struct extent_node, rb_node);
 277	}
 278	if (fofs == en->ei.fofs + en->ei.len - 1) {
 279		/* lookup next node for merging frontward later */
 280		tmp_node = rb_next(&en->rb_node);
 281		*next_entry = rb_entry_safe(tmp_node,
 282					struct extent_node, rb_node);
 283	}
 284	return en;
 285}
 286
 287static struct kmem_cache *extent_tree_slab;
 288static struct kmem_cache *extent_node_slab;
 289
 290static struct extent_node *__attach_extent_node(struct f2fs_sb_info *sbi,
 291				struct extent_tree *et, struct extent_info *ei,
 292				struct rb_node *parent, struct rb_node **p,
 293				bool leftmost)
 294{
 295	struct extent_tree_info *eti = &sbi->extent_tree[et->type];
 296	struct extent_node *en;
 297
 298	en = f2fs_kmem_cache_alloc(extent_node_slab, GFP_ATOMIC, false, sbi);
 299	if (!en)
 300		return NULL;
 301
 302	en->ei = *ei;
 303	INIT_LIST_HEAD(&en->list);
 304	en->et = et;
 305
 306	rb_link_node(&en->rb_node, parent, p);
 307	rb_insert_color_cached(&en->rb_node, &et->root, leftmost);
 308	atomic_inc(&et->node_cnt);
 309	atomic_inc(&eti->total_ext_node);
 310	return en;
 311}
 312
 313static void __detach_extent_node(struct f2fs_sb_info *sbi,
 314				struct extent_tree *et, struct extent_node *en)
 315{
 316	struct extent_tree_info *eti = &sbi->extent_tree[et->type];
 317
 318	rb_erase_cached(&en->rb_node, &et->root);
 319	atomic_dec(&et->node_cnt);
 320	atomic_dec(&eti->total_ext_node);
 321
 322	if (et->cached_en == en)
 323		et->cached_en = NULL;
 324	kmem_cache_free(extent_node_slab, en);
 325}
 326
 327/*
 328 * Flow to release an extent_node:
 329 * 1. list_del_init
 330 * 2. __detach_extent_node
 331 * 3. kmem_cache_free.
 332 */
 333static void __release_extent_node(struct f2fs_sb_info *sbi,
 334			struct extent_tree *et, struct extent_node *en)
 335{
 336	struct extent_tree_info *eti = &sbi->extent_tree[et->type];
 337
 338	spin_lock(&eti->extent_lock);
 339	f2fs_bug_on(sbi, list_empty(&en->list));
 340	list_del_init(&en->list);
 341	spin_unlock(&eti->extent_lock);
 342
 343	__detach_extent_node(sbi, et, en);
 344}
 345
 346static struct extent_tree *__grab_extent_tree(struct inode *inode,
 347						enum extent_type type)
 348{
 349	struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
 350	struct extent_tree_info *eti = &sbi->extent_tree[type];
 351	struct extent_tree *et;
 352	nid_t ino = inode->i_ino;
 353
 354	mutex_lock(&eti->extent_tree_lock);
 355	et = radix_tree_lookup(&eti->extent_tree_root, ino);
 356	if (!et) {
 357		et = f2fs_kmem_cache_alloc(extent_tree_slab,
 358					GFP_NOFS, true, NULL);
 359		f2fs_radix_tree_insert(&eti->extent_tree_root, ino, et);
 360		memset(et, 0, sizeof(struct extent_tree));
 361		et->ino = ino;
 362		et->type = type;
 363		et->root = RB_ROOT_CACHED;
 364		et->cached_en = NULL;
 365		rwlock_init(&et->lock);
 366		INIT_LIST_HEAD(&et->list);
 367		atomic_set(&et->node_cnt, 0);
 368		atomic_inc(&eti->total_ext_tree);
 369	} else {
 370		atomic_dec(&eti->total_zombie_tree);
 371		list_del_init(&et->list);
 372	}
 373	mutex_unlock(&eti->extent_tree_lock);
 374
 375	/* never died until evict_inode */
 376	F2FS_I(inode)->extent_tree[type] = et;
 377
 378	return et;
 379}
 380
 381static unsigned int __free_extent_tree(struct f2fs_sb_info *sbi,
 382				struct extent_tree *et, unsigned int nr_shrink)
 383{
 384	struct rb_node *node, *next;
 385	struct extent_node *en;
 386	unsigned int count;
 387
 388	node = rb_first_cached(&et->root);
 389
 390	for (count = 0; node && count < nr_shrink; count++) {
 391		next = rb_next(node);
 392		en = rb_entry(node, struct extent_node, rb_node);
 393		__release_extent_node(sbi, et, en);
 394		node = next;
 395	}
 396
 397	return count;
 398}
 399
 400static void __drop_largest_extent(struct extent_tree *et,
 401					pgoff_t fofs, unsigned int len)
 402{
 403	if (fofs < (pgoff_t)et->largest.fofs + et->largest.len &&
 404			fofs + len > et->largest.fofs) {
 405		et->largest.len = 0;
 406		et->largest_updated = true;
 407	}
 408}
 409
 410void f2fs_init_read_extent_tree(struct inode *inode, struct folio *ifolio)
 411{
 412	struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
 413	struct extent_tree_info *eti = &sbi->extent_tree[EX_READ];
 414	struct f2fs_extent *i_ext = &F2FS_INODE(ifolio)->i_ext;
 415	struct extent_tree *et;
 416	struct extent_node *en;
 417	struct extent_info ei = {0};
 418
 419	if (!__may_extent_tree(inode, EX_READ)) {
 420		/* drop largest read extent */
 421		if (i_ext->len) {
 422			f2fs_folio_wait_writeback(ifolio, NODE, true, true);
 423			i_ext->len = 0;
 424			folio_mark_dirty(ifolio);
 425		}
 426		set_inode_flag(inode, FI_NO_EXTENT);
 427		return;
 428	}
 429
 430	et = __grab_extent_tree(inode, EX_READ);
 431
 432	get_read_extent_info(&ei, i_ext);
 433
 434	write_lock(&et->lock);
 435	if (atomic_read(&et->node_cnt) || !ei.len)
 436		goto skip;
 437
 438	if (IS_DEVICE_ALIASING(inode)) {
 439		et->largest = ei;
 440		goto skip;
 441	}
 442
 443	en = __attach_extent_node(sbi, et, &ei, NULL,
 444				&et->root.rb_root.rb_node, true);
 445	if (en) {
 446		et->largest = en->ei;
 447		et->cached_en = en;
 448
 449		spin_lock(&eti->extent_lock);
 450		list_add_tail(&en->list, &eti->extent_list);
 451		spin_unlock(&eti->extent_lock);
 452	}
 453skip:
 454	/* Let's drop, if checkpoint got corrupted. */
 455	if (f2fs_cp_error(sbi)) {
 456		et->largest.len = 0;
 457		et->largest_updated = true;
 458	}
 459	write_unlock(&et->lock);
 460}
 461
 462void f2fs_init_age_extent_tree(struct inode *inode)
 463{
 464	if (!__init_may_extent_tree(inode, EX_BLOCK_AGE))
 465		return;
 466	__grab_extent_tree(inode, EX_BLOCK_AGE);
 467}
 468
 469void f2fs_init_extent_tree(struct inode *inode)
 470{
 471	/* initialize read cache */
 472	if (__init_may_extent_tree(inode, EX_READ))
 473		__grab_extent_tree(inode, EX_READ);
 474
 475	/* initialize block age cache */
 476	if (__init_may_extent_tree(inode, EX_BLOCK_AGE))
 477		__grab_extent_tree(inode, EX_BLOCK_AGE);
 478}
 479
 480static bool __lookup_extent_tree(struct inode *inode, pgoff_t pgofs,
 481			struct extent_info *ei, enum extent_type type)
 482{
 483	struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
 484	struct extent_tree_info *eti = &sbi->extent_tree[type];
 485	struct extent_tree *et = F2FS_I(inode)->extent_tree[type];
 486	struct extent_node *en;
 487	bool ret = false;
 488
 489	if (!et)
 490		return false;
 491
 492	trace_f2fs_lookup_extent_tree_start(inode, pgofs, type);
 493
 494	read_lock(&et->lock);
 495
 496	if (type == EX_READ &&
 497			et->largest.fofs <= pgofs &&
 498			(pgoff_t)et->largest.fofs + et->largest.len > pgofs) {
 499		*ei = et->largest;
 500		ret = true;
 501		stat_inc_largest_node_hit(sbi);
 502		goto out;
 503	}
 504
 505	if (IS_DEVICE_ALIASING(inode)) {
 506		ret = false;
 507		goto out;
 508	}
 509
 510	en = __lookup_extent_node(&et->root, et->cached_en, pgofs);
 511	if (!en)
 512		goto out;
 513
 514	if (en == et->cached_en)
 515		stat_inc_cached_node_hit(sbi, type);
 516	else
 517		stat_inc_rbtree_node_hit(sbi, type);
 518
 519	*ei = en->ei;
 520	spin_lock(&eti->extent_lock);
 521	if (!list_empty(&en->list)) {
 522		list_move_tail(&en->list, &eti->extent_list);
 523		et->cached_en = en;
 524	}
 525	spin_unlock(&eti->extent_lock);
 526	ret = true;
 527out:
 528	stat_inc_total_hit(sbi, type);
 529	read_unlock(&et->lock);
 530
 531	if (type == EX_READ)
 532		trace_f2fs_lookup_read_extent_tree_end(inode, pgofs, ei);
 533	else if (type == EX_BLOCK_AGE)
 534		trace_f2fs_lookup_age_extent_tree_end(inode, pgofs, ei);
 535	return ret;
 536}
 537
 538static struct extent_node *__try_merge_extent_node(struct f2fs_sb_info *sbi,
 539				struct extent_tree *et, struct extent_info *ei,
 540				struct extent_node *prev_ex,
 541				struct extent_node *next_ex)
 542{
 543	struct extent_tree_info *eti = &sbi->extent_tree[et->type];
 544	struct extent_node *en = NULL;
 545
 546	if (prev_ex && __is_back_mergeable(ei, &prev_ex->ei, et->type)) {
 547		prev_ex->ei.len += ei->len;
 548		ei = &prev_ex->ei;
 549		en = prev_ex;
 550	}
 551
 552	if (next_ex && __is_front_mergeable(ei, &next_ex->ei, et->type)) {
 553		next_ex->ei.fofs = ei->fofs;
 554		next_ex->ei.len += ei->len;
 555		if (et->type == EX_READ)
 556			next_ex->ei.blk = ei->blk;
 557		if (en)
 558			__release_extent_node(sbi, et, prev_ex);
 559
 560		en = next_ex;
 561	}
 562
 563	if (!en)
 564		return NULL;
 565
 566	__try_update_largest_extent(et, en);
 567
 568	spin_lock(&eti->extent_lock);
 569	if (!list_empty(&en->list)) {
 570		list_move_tail(&en->list, &eti->extent_list);
 571		et->cached_en = en;
 572	}
 573	spin_unlock(&eti->extent_lock);
 574	return en;
 575}
 576
 577static struct extent_node *__insert_extent_tree(struct f2fs_sb_info *sbi,
 578				struct extent_tree *et, struct extent_info *ei,
 579				struct rb_node **insert_p,
 580				struct rb_node *insert_parent,
 581				bool leftmost)
 582{
 583	struct extent_tree_info *eti = &sbi->extent_tree[et->type];
 584	struct rb_node **p = &et->root.rb_root.rb_node;
 585	struct rb_node *parent = NULL;
 586	struct extent_node *en = NULL;
 587
 588	if (insert_p && insert_parent) {
 589		parent = insert_parent;
 590		p = insert_p;
 591		goto do_insert;
 592	}
 593
 594	leftmost = true;
 595
 596	/* look up extent_node in the rb tree */
 597	while (*p) {
 598		parent = *p;
 599		en = rb_entry(parent, struct extent_node, rb_node);
 600
 601		if (ei->fofs < en->ei.fofs) {
 602			p = &(*p)->rb_left;
 603		} else if (ei->fofs >= en->ei.fofs + en->ei.len) {
 604			p = &(*p)->rb_right;
 605			leftmost = false;
 606		} else {
 607			f2fs_err_ratelimited(sbi, "%s: corrupted extent, type: %d, "
 608				"extent node in rb tree [%u, %u, %u], age [%llu, %llu], "
 609				"extent node to insert [%u, %u, %u], age [%llu, %llu]",
 610				__func__, et->type, en->ei.fofs, en->ei.blk, en->ei.len, en->ei.age,
 611				en->ei.last_blocks, ei->fofs, ei->blk, ei->len, ei->age, ei->last_blocks);
 612			f2fs_bug_on(sbi, 1);
 613			return NULL;
 614		}
 615	}
 616
 617do_insert:
 618	en = __attach_extent_node(sbi, et, ei, parent, p, leftmost);
 619	if (!en)
 620		return NULL;
 621
 622	__try_update_largest_extent(et, en);
 623
 624	/* update in global extent list */
 625	spin_lock(&eti->extent_lock);
 626	list_add_tail(&en->list, &eti->extent_list);
 627	et->cached_en = en;
 628	spin_unlock(&eti->extent_lock);
 629	return en;
 630}
 631
 632static unsigned int __destroy_extent_node(struct inode *inode,
 633					enum extent_type type)
 634{
 635	struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
 636	struct extent_tree *et = F2FS_I(inode)->extent_tree[type];
 637	unsigned int nr_shrink = type == EX_READ ?
 638				READ_EXTENT_CACHE_SHRINK_NUMBER :
 639				AGE_EXTENT_CACHE_SHRINK_NUMBER;
 640	unsigned int node_cnt = 0;
 641
 642	if (!et || !atomic_read(&et->node_cnt))
 643		return 0;
 644
 645	while (atomic_read(&et->node_cnt)) {
 646		write_lock(&et->lock);
 647		node_cnt += __free_extent_tree(sbi, et, nr_shrink);
 648		write_unlock(&et->lock);
 649	}
 650
 651	f2fs_bug_on(sbi, atomic_read(&et->node_cnt));
 652
 653	return node_cnt;
 654}
 655
 656static void __update_extent_tree_range(struct inode *inode,
 657			struct extent_info *tei, enum extent_type type)
 658{
 659	struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
 660	struct extent_tree *et = F2FS_I(inode)->extent_tree[type];
 661	struct extent_node *en = NULL, *en1 = NULL;
 662	struct extent_node *prev_en = NULL, *next_en = NULL;
 663	struct extent_info ei, dei, prev;
 664	struct rb_node **insert_p = NULL, *insert_parent = NULL;
 665	unsigned int fofs = tei->fofs, len = tei->len;
 666	unsigned int end = fofs + len;
 667	bool updated = false;
 668	bool leftmost = false;
 669
 670	if (!et)
 671		return;
 672
 673	if (unlikely(len == 0)) {
 674		f2fs_err_ratelimited(sbi, "%s: extent len is zero, type: %d, "
 675			"extent [%u, %u, %u], age [%llu, %llu]",
 676			__func__, type, tei->fofs, tei->blk, tei->len,
 677			tei->age, tei->last_blocks);
 678		f2fs_bug_on(sbi, 1);
 679		return;
 680	}
 681
 682	if (type == EX_READ)
 683		trace_f2fs_update_read_extent_tree_range(inode, fofs, len,
 684						tei->blk, 0);
 685	else if (type == EX_BLOCK_AGE)
 686		trace_f2fs_update_age_extent_tree_range(inode, fofs, len,
 687						tei->age, tei->last_blocks);
 688
 689	write_lock(&et->lock);
 690
 691	if (type == EX_READ) {
 692		if (is_inode_flag_set(inode, FI_NO_EXTENT)) {
 693			write_unlock(&et->lock);
 694			return;
 695		}
 696
 697		prev = et->largest;
 698		dei.len = 0;
 699
 700		/*
 701		 * drop largest extent before lookup, in case it's already
 702		 * been shrunk from extent tree
 703		 */
 704		__drop_largest_extent(et, fofs, len);
 705	}
 706
 707	/* 1. lookup first extent node in range [fofs, fofs + len - 1] */
 708	en = __lookup_extent_node_ret(&et->root,
 709					et->cached_en, fofs,
 710					&prev_en, &next_en,
 711					&insert_p, &insert_parent,
 712					&leftmost);
 713	if (!en)
 714		en = next_en;
 715
 716	/* 2. invalidate all extent nodes in range [fofs, fofs + len - 1] */
 717	while (en && en->ei.fofs < end) {
 718		unsigned int org_end;
 719		int parts = 0;	/* # of parts current extent split into */
 720
 721		next_en = en1 = NULL;
 722
 723		dei = en->ei;
 724		org_end = dei.fofs + dei.len;
 725		f2fs_bug_on(sbi, fofs >= org_end);
 726
 727		if (fofs > dei.fofs && (type != EX_READ ||
 728				fofs - dei.fofs >= F2FS_MIN_EXTENT_LEN)) {
 729			en->ei.len = fofs - en->ei.fofs;
 730			prev_en = en;
 731			parts = 1;
 732		}
 733
 734		if (end < org_end && (type != EX_READ ||
 735			(org_end - end >= F2FS_MIN_EXTENT_LEN &&
 736			atomic_read(&et->node_cnt) <
 737					sbi->max_read_extent_count))) {
 738			if (parts) {
 739				__set_extent_info(&ei,
 740					end, org_end - end,
 741					end - dei.fofs + dei.blk, false,
 742					dei.age, dei.last_blocks,
 743					type);
 744				en1 = __insert_extent_tree(sbi, et, &ei,
 745							NULL, NULL, true);
 746				next_en = en1;
 747			} else {
 748				__set_extent_info(&en->ei,
 749					end, en->ei.len - (end - dei.fofs),
 750					en->ei.blk + (end - dei.fofs), true,
 751					dei.age, dei.last_blocks,
 752					type);
 753				next_en = en;
 754			}
 755			parts++;
 756		}
 757
 758		if (!next_en) {
 759			struct rb_node *node = rb_next(&en->rb_node);
 760
 761			next_en = rb_entry_safe(node, struct extent_node,
 762						rb_node);
 763		}
 764
 765		if (parts)
 766			__try_update_largest_extent(et, en);
 767		else
 768			__release_extent_node(sbi, et, en);
 769
 770		/*
 771		 * if original extent is split into zero or two parts, extent
 772		 * tree has been altered by deletion or insertion, therefore
 773		 * invalidate pointers regard to tree.
 774		 */
 775		if (parts != 1) {
 776			insert_p = NULL;
 777			insert_parent = NULL;
 778		}
 779		en = next_en;
 780	}
 781
 782	if (type == EX_BLOCK_AGE)
 783		goto update_age_extent_cache;
 784
 785	/* 3. update extent in read extent cache */
 786	BUG_ON(type != EX_READ);
 787
 788	if (tei->blk) {
 789		__set_extent_info(&ei, fofs, len, tei->blk, false,
 790				  0, 0, EX_READ);
 791		if (!__try_merge_extent_node(sbi, et, &ei, prev_en, next_en))
 792			__insert_extent_tree(sbi, et, &ei,
 793					insert_p, insert_parent, leftmost);
 794
 795		/* give up extent_cache, if split and small updates happen */
 796		if (dei.len >= 1 &&
 797				prev.len < F2FS_MIN_EXTENT_LEN &&
 798				et->largest.len < F2FS_MIN_EXTENT_LEN) {
 799			et->largest.len = 0;
 800			et->largest_updated = true;
 801			set_inode_flag(inode, FI_NO_EXTENT);
 802		}
 803	}
 804
 805	if (et->largest_updated) {
 806		et->largest_updated = false;
 807		updated = true;
 808	}
 809	goto out_read_extent_cache;
 810update_age_extent_cache:
 811	if (tei->last_blocks == F2FS_EXTENT_AGE_INVALID)
 812		goto out_read_extent_cache;
 813
 814	__set_extent_info(&ei, fofs, len, 0, false,
 815			tei->age, tei->last_blocks, EX_BLOCK_AGE);
 816	if (!__try_merge_extent_node(sbi, et, &ei, prev_en, next_en))
 817		__insert_extent_tree(sbi, et, &ei,
 818					insert_p, insert_parent, leftmost);
 819out_read_extent_cache:
 820	write_unlock(&et->lock);
 821
 822	if (is_inode_flag_set(inode, FI_NO_EXTENT))
 823		__destroy_extent_node(inode, EX_READ);
 824
 825	if (updated)
 826		f2fs_mark_inode_dirty_sync(inode, true);
 827}
 828
 829#ifdef CONFIG_F2FS_FS_COMPRESSION
 830void f2fs_update_read_extent_tree_range_compressed(struct inode *inode,
 831				pgoff_t fofs, block_t blkaddr, unsigned int llen,
 832				unsigned int c_len)
 833{
 834	struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
 835	struct extent_tree *et = F2FS_I(inode)->extent_tree[EX_READ];
 836	struct extent_node *en = NULL;
 837	struct extent_node *prev_en = NULL, *next_en = NULL;
 838	struct extent_info ei;
 839	struct rb_node **insert_p = NULL, *insert_parent = NULL;
 840	bool leftmost = false;
 841
 842	trace_f2fs_update_read_extent_tree_range(inode, fofs, llen,
 843						blkaddr, c_len);
 844
 845	/* it is safe here to check FI_NO_EXTENT w/o et->lock in ro image */
 846	if (is_inode_flag_set(inode, FI_NO_EXTENT))
 847		return;
 848
 849	write_lock(&et->lock);
 850
 851	en = __lookup_extent_node_ret(&et->root,
 852					et->cached_en, fofs,
 853					&prev_en, &next_en,
 854					&insert_p, &insert_parent,
 855					&leftmost);
 856	if (en)
 857		goto unlock_out;
 858
 859	__set_extent_info(&ei, fofs, llen, blkaddr, true, 0, 0, EX_READ);
 860	ei.c_len = c_len;
 861
 862	if (!__try_merge_extent_node(sbi, et, &ei, prev_en, next_en))
 863		__insert_extent_tree(sbi, et, &ei,
 864				insert_p, insert_parent, leftmost);
 865unlock_out:
 866	write_unlock(&et->lock);
 867}
 868#endif
 869
 870static unsigned long long __calculate_block_age(struct f2fs_sb_info *sbi,
 871						unsigned long long new,
 872						unsigned long long old)
 873{
 874	unsigned int rem_old, rem_new;
 875	unsigned long long res;
 876	unsigned int weight = sbi->last_age_weight;
 877
 878	res = div_u64_rem(new, 100, &rem_new) * (100 - weight)
 879		+ div_u64_rem(old, 100, &rem_old) * weight;
 880
 881	if (rem_new)
 882		res += rem_new * (100 - weight) / 100;
 883	if (rem_old)
 884		res += rem_old * weight / 100;
 885
 886	return res;
 887}
 888
 889/* This returns a new age and allocated blocks in ei */
 890static int __get_new_block_age(struct inode *inode, struct extent_info *ei,
 891						block_t blkaddr)
 892{
 893	struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
 894	loff_t f_size = i_size_read(inode);
 895	unsigned long long cur_blocks =
 896				atomic64_read(&sbi->allocated_data_blocks);
 897	struct extent_info tei = *ei;	/* only fofs and len are valid */
 898
 899	/*
 900	 * When I/O is not aligned to a PAGE_SIZE, update will happen to the last
 901	 * file block even in seq write. So don't record age for newly last file
 902	 * block here.
 903	 */
 904	if ((f_size >> PAGE_SHIFT) == ei->fofs && f_size & (PAGE_SIZE - 1) &&
 905			blkaddr == NEW_ADDR)
 906		return -EINVAL;
 907
 908	if (__lookup_extent_tree(inode, ei->fofs, &tei, EX_BLOCK_AGE)) {
 909		unsigned long long cur_age;
 910
 911		if (cur_blocks >= tei.last_blocks)
 912			cur_age = cur_blocks - tei.last_blocks;
 913		else
 914			/* allocated_data_blocks overflow */
 915			cur_age = (ULLONG_MAX - 1) - tei.last_blocks + cur_blocks;
 916
 917		if (tei.age)
 918			ei->age = __calculate_block_age(sbi, cur_age, tei.age);
 919		else
 920			ei->age = cur_age;
 921		ei->last_blocks = cur_blocks;
 922		WARN_ON(ei->age > cur_blocks);
 923		return 0;
 924	}
 925
 926	f2fs_bug_on(sbi, blkaddr == NULL_ADDR);
 927
 928	/* the data block was allocated for the first time */
 929	if (blkaddr == NEW_ADDR)
 930		goto out;
 931
 932	if (__is_valid_data_blkaddr(blkaddr) &&
 933	    !f2fs_is_valid_blkaddr(sbi, blkaddr, DATA_GENERIC_ENHANCE))
 934		return -EINVAL;
 935out:
 936	/*
 937	 * init block age with zero, this can happen when the block age extent
 938	 * was reclaimed due to memory constraint or system reboot
 939	 */
 940	ei->age = 0;
 941	ei->last_blocks = cur_blocks;
 942	return 0;
 943}
 944
 945static void __update_extent_cache(struct dnode_of_data *dn, enum extent_type type)
 946{
 947	struct extent_info ei = {};
 948
 949	if (!__may_extent_tree(dn->inode, type))
 950		return;
 951
 952	ei.fofs = f2fs_start_bidx_of_node(ofs_of_node(dn->node_folio), dn->inode) +
 953								dn->ofs_in_node;
 954	ei.len = 1;
 955
 956	if (type == EX_READ) {
 957		if (dn->data_blkaddr == NEW_ADDR)
 958			ei.blk = NULL_ADDR;
 959		else
 960			ei.blk = dn->data_blkaddr;
 961	} else if (type == EX_BLOCK_AGE) {
 962		if (__get_new_block_age(dn->inode, &ei, dn->data_blkaddr))
 963			return;
 964	}
 965	__update_extent_tree_range(dn->inode, &ei, type);
 966}
 967
 968static unsigned int __shrink_extent_tree(struct f2fs_sb_info *sbi, int nr_shrink,
 969					enum extent_type type)
 970{
 971	struct extent_tree_info *eti = &sbi->extent_tree[type];
 972	struct extent_tree *et, *next;
 973	struct extent_node *en;
 974	unsigned int node_cnt = 0, tree_cnt = 0;
 975	int remained;
 976
 977	if (!atomic_read(&eti->total_zombie_tree))
 978		goto free_node;
 979
 980	if (!mutex_trylock(&eti->extent_tree_lock))
 981		goto out;
 982
 983	/* 1. remove unreferenced extent tree */
 984	list_for_each_entry_safe(et, next, &eti->zombie_list, list) {
 985		if (atomic_read(&et->node_cnt)) {
 986			write_lock(&et->lock);
 987			node_cnt += __free_extent_tree(sbi, et,
 988					nr_shrink - node_cnt - tree_cnt);
 989			write_unlock(&et->lock);
 990		}
 991
 992		if (atomic_read(&et->node_cnt))
 993			goto unlock_out;
 994
 995		list_del_init(&et->list);
 996		radix_tree_delete(&eti->extent_tree_root, et->ino);
 997		kmem_cache_free(extent_tree_slab, et);
 998		atomic_dec(&eti->total_ext_tree);
 999		atomic_dec(&eti->total_zombie_tree);
1000		tree_cnt++;
1001
1002		if (node_cnt + tree_cnt >= nr_shrink)
1003			goto unlock_out;
1004		cond_resched();
1005	}
1006	mutex_unlock(&eti->extent_tree_lock);
1007
1008free_node:
1009	/* 2. remove LRU extent entries */
1010	if (!mutex_trylock(&eti->extent_tree_lock))
1011		goto out;
1012
1013	remained = nr_shrink - (node_cnt + tree_cnt);
1014
1015	spin_lock(&eti->extent_lock);
1016	for (; remained > 0; remained--) {
1017		if (list_empty(&eti->extent_list))
1018			break;
1019		en = list_first_entry(&eti->extent_list,
1020					struct extent_node, list);
1021		et = en->et;
1022		if (!write_trylock(&et->lock)) {
1023			/* refresh this extent node's position in extent list */
1024			list_move_tail(&en->list, &eti->extent_list);
1025			continue;
1026		}
1027
1028		list_del_init(&en->list);
1029		spin_unlock(&eti->extent_lock);
1030
1031		__detach_extent_node(sbi, et, en);
1032
1033		write_unlock(&et->lock);
1034		node_cnt++;
1035		spin_lock(&eti->extent_lock);
1036	}
1037	spin_unlock(&eti->extent_lock);
1038
1039unlock_out:
1040	mutex_unlock(&eti->extent_tree_lock);
1041out:
1042	trace_f2fs_shrink_extent_tree(sbi, node_cnt, tree_cnt, type);
1043
1044	return node_cnt + tree_cnt;
1045}
1046
1047/* read extent cache operations */
1048bool f2fs_lookup_read_extent_cache(struct inode *inode, pgoff_t pgofs,
1049				struct extent_info *ei)
1050{
1051	if (!__may_extent_tree(inode, EX_READ))
1052		return false;
1053
1054	return __lookup_extent_tree(inode, pgofs, ei, EX_READ);
1055}
1056
1057bool f2fs_lookup_read_extent_cache_block(struct inode *inode, pgoff_t index,
1058				block_t *blkaddr)
1059{
1060	struct extent_info ei = {};
1061
1062	if (!f2fs_lookup_read_extent_cache(inode, index, &ei))
1063		return false;
1064	*blkaddr = ei.blk + index - ei.fofs;
1065	return true;
1066}
1067
1068void f2fs_update_read_extent_cache(struct dnode_of_data *dn)
1069{
1070	return __update_extent_cache(dn, EX_READ);
1071}
1072
1073void f2fs_update_read_extent_cache_range(struct dnode_of_data *dn,
1074				pgoff_t fofs, block_t blkaddr, unsigned int len)
1075{
1076	struct extent_info ei = {
1077		.fofs = fofs,
1078		.len = len,
1079		.blk = blkaddr,
1080	};
1081
1082	if (!__may_extent_tree(dn->inode, EX_READ))
1083		return;
1084
1085	__update_extent_tree_range(dn->inode, &ei, EX_READ);
1086}
1087
1088unsigned int f2fs_shrink_read_extent_tree(struct f2fs_sb_info *sbi, int nr_shrink)
1089{
1090	if (!test_opt(sbi, READ_EXTENT_CACHE))
1091		return 0;
1092
1093	return __shrink_extent_tree(sbi, nr_shrink, EX_READ);
1094}
1095
1096/* block age extent cache operations */
1097bool f2fs_lookup_age_extent_cache(struct inode *inode, pgoff_t pgofs,
1098				struct extent_info *ei)
1099{
1100	if (!__may_extent_tree(inode, EX_BLOCK_AGE))
1101		return false;
1102
1103	return __lookup_extent_tree(inode, pgofs, ei, EX_BLOCK_AGE);
1104}
1105
1106void f2fs_update_age_extent_cache(struct dnode_of_data *dn)
1107{
1108	return __update_extent_cache(dn, EX_BLOCK_AGE);
1109}
1110
1111void f2fs_update_age_extent_cache_range(struct dnode_of_data *dn,
1112				pgoff_t fofs, unsigned int len)
1113{
1114	struct extent_info ei = {
1115		.fofs = fofs,
1116		.len = len,
1117		.last_blocks = F2FS_EXTENT_AGE_INVALID,
1118	};
1119
1120	if (!__may_extent_tree(dn->inode, EX_BLOCK_AGE))
1121		return;
1122
1123	__update_extent_tree_range(dn->inode, &ei, EX_BLOCK_AGE);
1124}
1125
1126unsigned int f2fs_shrink_age_extent_tree(struct f2fs_sb_info *sbi, int nr_shrink)
1127{
1128	if (!test_opt(sbi, AGE_EXTENT_CACHE))
1129		return 0;
1130
1131	return __shrink_extent_tree(sbi, nr_shrink, EX_BLOCK_AGE);
1132}
1133
1134void f2fs_destroy_extent_node(struct inode *inode)
1135{
1136	__destroy_extent_node(inode, EX_READ);
1137	__destroy_extent_node(inode, EX_BLOCK_AGE);
1138}
1139
1140static void __drop_extent_tree(struct inode *inode, enum extent_type type)
1141{
1142	struct extent_tree *et = F2FS_I(inode)->extent_tree[type];
1143	bool updated = false;
1144
1145	if (!__may_extent_tree(inode, type))
1146		return;
1147
1148	write_lock(&et->lock);
1149	if (type == EX_READ) {
1150		set_inode_flag(inode, FI_NO_EXTENT);
1151		if (et->largest.len) {
1152			et->largest.len = 0;
1153			updated = true;
1154		}
1155	}
1156	write_unlock(&et->lock);
1157
1158	__destroy_extent_node(inode, type);
1159
1160	if (updated)
1161		f2fs_mark_inode_dirty_sync(inode, true);
1162}
1163
1164void f2fs_drop_extent_tree(struct inode *inode)
1165{
1166	__drop_extent_tree(inode, EX_READ);
1167	__drop_extent_tree(inode, EX_BLOCK_AGE);
1168}
1169
1170static void __destroy_extent_tree(struct inode *inode, enum extent_type type)
1171{
1172	struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
1173	struct extent_tree_info *eti = &sbi->extent_tree[type];
1174	struct extent_tree *et = F2FS_I(inode)->extent_tree[type];
1175	unsigned int node_cnt = 0;
1176
1177	if (!et)
1178		return;
1179
1180	if (inode->i_nlink && !is_bad_inode(inode) &&
1181					atomic_read(&et->node_cnt)) {
1182		mutex_lock(&eti->extent_tree_lock);
1183		list_add_tail(&et->list, &eti->zombie_list);
1184		atomic_inc(&eti->total_zombie_tree);
1185		mutex_unlock(&eti->extent_tree_lock);
1186		return;
1187	}
1188
1189	/* free all extent info belong to this extent tree */
1190	node_cnt = __destroy_extent_node(inode, type);
1191
1192	/* delete extent tree entry in radix tree */
1193	mutex_lock(&eti->extent_tree_lock);
1194	f2fs_bug_on(sbi, atomic_read(&et->node_cnt));
1195	radix_tree_delete(&eti->extent_tree_root, inode->i_ino);
1196	kmem_cache_free(extent_tree_slab, et);
1197	atomic_dec(&eti->total_ext_tree);
1198	mutex_unlock(&eti->extent_tree_lock);
1199
1200	F2FS_I(inode)->extent_tree[type] = NULL;
1201
1202	trace_f2fs_destroy_extent_tree(inode, node_cnt, type);
1203}
1204
1205void f2fs_destroy_extent_tree(struct inode *inode)
1206{
1207	__destroy_extent_tree(inode, EX_READ);
1208	__destroy_extent_tree(inode, EX_BLOCK_AGE);
1209}
1210
1211static void __init_extent_tree_info(struct extent_tree_info *eti)
1212{
1213	INIT_RADIX_TREE(&eti->extent_tree_root, GFP_NOIO);
1214	mutex_init(&eti->extent_tree_lock);
1215	INIT_LIST_HEAD(&eti->extent_list);
1216	spin_lock_init(&eti->extent_lock);
1217	atomic_set(&eti->total_ext_tree, 0);
1218	INIT_LIST_HEAD(&eti->zombie_list);
1219	atomic_set(&eti->total_zombie_tree, 0);
1220	atomic_set(&eti->total_ext_node, 0);
1221}
1222
1223void f2fs_init_extent_cache_info(struct f2fs_sb_info *sbi)
1224{
1225	__init_extent_tree_info(&sbi->extent_tree[EX_READ]);
1226	__init_extent_tree_info(&sbi->extent_tree[EX_BLOCK_AGE]);
1227
1228	/* initialize for block age extents */
1229	atomic64_set(&sbi->allocated_data_blocks, 0);
1230	sbi->hot_data_age_threshold = DEF_HOT_DATA_AGE_THRESHOLD;
1231	sbi->warm_data_age_threshold = DEF_WARM_DATA_AGE_THRESHOLD;
1232	sbi->last_age_weight = LAST_AGE_WEIGHT;
1233	sbi->max_read_extent_count = DEF_MAX_READ_EXTENT_COUNT;
1234}
1235
1236int __init f2fs_create_extent_cache(void)
1237{
1238	extent_tree_slab = f2fs_kmem_cache_create("f2fs_extent_tree",
1239			sizeof(struct extent_tree));
1240	if (!extent_tree_slab)
1241		return -ENOMEM;
1242	extent_node_slab = f2fs_kmem_cache_create("f2fs_extent_node",
1243			sizeof(struct extent_node));
1244	if (!extent_node_slab) {
1245		kmem_cache_destroy(extent_tree_slab);
1246		return -ENOMEM;
1247	}
1248	return 0;
1249}
1250
1251void f2fs_destroy_extent_cache(void)
1252{
1253	kmem_cache_destroy(extent_node_slab);
1254	kmem_cache_destroy(extent_tree_slab);
1255}