node.c

   1// SPDX-License-Identifier: GPL-2.0
   2/*
   3 * fs/f2fs/node.c
   4 *
   5 * Copyright (c) 2012 Samsung Electronics Co., Ltd.
   6 *             http://www.samsung.com/
   7 */
   8#include <linux/fs.h>
   9#include <linux/f2fs_fs.h>
  10#include <linux/mpage.h>
  11#include <linux/sched/mm.h>
  12#include <linux/blkdev.h>
  13#include <linux/pagevec.h>
  14#include <linux/swap.h>
  15
  16#include "f2fs.h"
  17#include "node.h"
  18#include "segment.h"
  19#include "xattr.h"
  20#include "iostat.h"
  21#include <trace/events/f2fs.h>
  22
  23#define on_f2fs_build_free_nids(nm_i) mutex_is_locked(&(nm_i)->build_lock)
  24
  25static struct kmem_cache *nat_entry_slab;
  26static struct kmem_cache *free_nid_slab;
  27static struct kmem_cache *nat_entry_set_slab;
  28static struct kmem_cache *fsync_node_entry_slab;
  29
  30static inline bool is_invalid_nid(struct f2fs_sb_info *sbi, nid_t nid)
  31{
  32	return nid < F2FS_ROOT_INO(sbi) || nid >= NM_I(sbi)->max_nid;
  33}
  34
  35/*
  36 * Check whether the given nid is within node id range.
  37 */
  38int f2fs_check_nid_range(struct f2fs_sb_info *sbi, nid_t nid)
  39{
  40	if (unlikely(is_invalid_nid(sbi, nid))) {
  41		set_sbi_flag(sbi, SBI_NEED_FSCK);
  42		f2fs_warn(sbi, "%s: out-of-range nid=%x, run fsck to fix.",
  43			  __func__, nid);
  44		f2fs_handle_error(sbi, ERROR_CORRUPTED_INODE);
  45		return -EFSCORRUPTED;
  46	}
  47	return 0;
  48}
  49
  50bool f2fs_available_free_memory(struct f2fs_sb_info *sbi, int type)
  51{
  52	struct f2fs_nm_info *nm_i = NM_I(sbi);
  53	struct discard_cmd_control *dcc = SM_I(sbi)->dcc_info;
  54	struct sysinfo val;
  55	unsigned long avail_ram;
  56	unsigned long mem_size = 0;
  57	bool res = false;
  58
  59	if (!nm_i)
  60		return true;
  61
  62	si_meminfo(&val);
  63
  64	/* only uses low memory */
  65	avail_ram = val.totalram - val.totalhigh;
  66
  67	/*
  68	 * give 25%, 25%, 50%, 50%, 25%, 25% memory for each components respectively
  69	 */
  70	if (type == FREE_NIDS) {
  71		mem_size = (nm_i->nid_cnt[FREE_NID] *
  72				sizeof(struct free_nid)) >> PAGE_SHIFT;
  73		res = mem_size < ((avail_ram * nm_i->ram_thresh / 100) >> 2);
  74	} else if (type == NAT_ENTRIES) {
  75		mem_size = (nm_i->nat_cnt[TOTAL_NAT] *
  76				sizeof(struct nat_entry)) >> PAGE_SHIFT;
  77		res = mem_size < ((avail_ram * nm_i->ram_thresh / 100) >> 2);
  78		if (excess_cached_nats(sbi))
  79			res = false;
  80	} else if (type == DIRTY_DENTS) {
  81		if (sbi->sb->s_bdi->wb.dirty_exceeded)
  82			return false;
  83		mem_size = get_pages(sbi, F2FS_DIRTY_DENTS);
  84		res = mem_size < ((avail_ram * nm_i->ram_thresh / 100) >> 1);
  85	} else if (type == INO_ENTRIES) {
  86		int i;
  87
  88		for (i = 0; i < MAX_INO_ENTRY; i++)
  89			mem_size += sbi->im[i].ino_num *
  90						sizeof(struct ino_entry);
  91		mem_size >>= PAGE_SHIFT;
  92		res = mem_size < ((avail_ram * nm_i->ram_thresh / 100) >> 1);
  93	} else if (type == READ_EXTENT_CACHE || type == AGE_EXTENT_CACHE) {
  94		enum extent_type etype = type == READ_EXTENT_CACHE ?
  95						EX_READ : EX_BLOCK_AGE;
  96		struct extent_tree_info *eti = &sbi->extent_tree[etype];
  97
  98		mem_size = (atomic_read(&eti->total_ext_tree) *
  99				sizeof(struct extent_tree) +
 100				atomic_read(&eti->total_ext_node) *
 101				sizeof(struct extent_node)) >> PAGE_SHIFT;
 102		res = mem_size < ((avail_ram * nm_i->ram_thresh / 100) >> 2);
 103	} else if (type == DISCARD_CACHE) {
 104		mem_size = (atomic_read(&dcc->discard_cmd_cnt) *
 105				sizeof(struct discard_cmd)) >> PAGE_SHIFT;
 106		res = mem_size < (avail_ram * nm_i->ram_thresh / 100);
 107	} else if (type == COMPRESS_PAGE) {
 108#ifdef CONFIG_F2FS_FS_COMPRESSION
 109		unsigned long free_ram = val.freeram;
 110
 111		/*
 112		 * free memory is lower than watermark or cached page count
 113		 * exceed threshold, deny caching compress page.
 114		 */
 115		res = (free_ram > avail_ram * sbi->compress_watermark / 100) &&
 116			(COMPRESS_MAPPING(sbi)->nrpages <
 117			 free_ram * sbi->compress_percent / 100);
 118#else
 119		res = false;
 120#endif
 121	} else {
 122		if (!sbi->sb->s_bdi->wb.dirty_exceeded)
 123			return true;
 124	}
 125	return res;
 126}
 127
 128static void clear_node_folio_dirty(struct folio *folio)
 129{
 130	if (folio_test_dirty(folio)) {
 131		f2fs_clear_page_cache_dirty_tag(folio);
 132		folio_clear_dirty_for_io(folio);
 133		dec_page_count(F2FS_F_SB(folio), F2FS_DIRTY_NODES);
 134	}
 135	folio_clear_uptodate(folio);
 136}
 137
 138static struct folio *get_current_nat_folio(struct f2fs_sb_info *sbi, nid_t nid)
 139{
 140	return f2fs_get_meta_folio_retry(sbi, current_nat_addr(sbi, nid));
 141}
 142
 143static struct folio *get_next_nat_folio(struct f2fs_sb_info *sbi, nid_t nid)
 144{
 145	struct folio *src_folio;
 146	struct folio *dst_folio;
 147	pgoff_t dst_off;
 148	void *src_addr;
 149	void *dst_addr;
 150	struct f2fs_nm_info *nm_i = NM_I(sbi);
 151
 152	dst_off = next_nat_addr(sbi, current_nat_addr(sbi, nid));
 153
 154	/* get current nat block page with lock */
 155	src_folio = get_current_nat_folio(sbi, nid);
 156	if (IS_ERR(src_folio))
 157		return src_folio;
 158	dst_folio = f2fs_grab_meta_folio(sbi, dst_off);
 159	f2fs_bug_on(sbi, folio_test_dirty(src_folio));
 160
 161	src_addr = folio_address(src_folio);
 162	dst_addr = folio_address(dst_folio);
 163	memcpy(dst_addr, src_addr, PAGE_SIZE);
 164	folio_mark_dirty(dst_folio);
 165	f2fs_folio_put(src_folio, true);
 166
 167	set_to_next_nat(nm_i, nid);
 168
 169	return dst_folio;
 170}
 171
 172static struct nat_entry *__alloc_nat_entry(struct f2fs_sb_info *sbi,
 173						nid_t nid, bool no_fail)
 174{
 175	struct nat_entry *new;
 176
 177	new = f2fs_kmem_cache_alloc(nat_entry_slab,
 178					GFP_F2FS_ZERO, no_fail, sbi);
 179	if (new) {
 180		nat_set_nid(new, nid);
 181		nat_reset_flag(new);
 182	}
 183	return new;
 184}
 185
 186static void __free_nat_entry(struct nat_entry *e)
 187{
 188	kmem_cache_free(nat_entry_slab, e);
 189}
 190
 191/* must be locked by nat_tree_lock */
 192static struct nat_entry *__init_nat_entry(struct f2fs_nm_info *nm_i,
 193	struct nat_entry *ne, struct f2fs_nat_entry *raw_ne, bool no_fail, bool init_dirty)
 194{
 195	if (no_fail)
 196		f2fs_radix_tree_insert(&nm_i->nat_root, nat_get_nid(ne), ne);
 197	else if (radix_tree_insert(&nm_i->nat_root, nat_get_nid(ne), ne))
 198		return NULL;
 199
 200	if (raw_ne)
 201		node_info_from_raw_nat(&ne->ni, raw_ne);
 202
 203	if (init_dirty) {
 204		INIT_LIST_HEAD(&ne->list);
 205		nm_i->nat_cnt[TOTAL_NAT]++;
 206		return ne;
 207	}
 208
 209	spin_lock(&nm_i->nat_list_lock);
 210	list_add_tail(&ne->list, &nm_i->nat_entries);
 211	spin_unlock(&nm_i->nat_list_lock);
 212
 213	nm_i->nat_cnt[TOTAL_NAT]++;
 214	nm_i->nat_cnt[RECLAIMABLE_NAT]++;
 215	return ne;
 216}
 217
 218static struct nat_entry *__lookup_nat_cache(struct f2fs_nm_info *nm_i, nid_t n, bool for_dirty)
 219{
 220	struct nat_entry *ne;
 221
 222	ne = radix_tree_lookup(&nm_i->nat_root, n);
 223
 224	/*
 225	 * for recent accessed nat entry which will not be dirtied soon
 226	 * later, move it to tail of lru list.
 227	 */
 228	if (ne && !get_nat_flag(ne, IS_DIRTY) && !for_dirty) {
 229		spin_lock(&nm_i->nat_list_lock);
 230		if (!list_empty(&ne->list))
 231			list_move_tail(&ne->list, &nm_i->nat_entries);
 232		spin_unlock(&nm_i->nat_list_lock);
 233	}
 234
 235	return ne;
 236}
 237
 238static unsigned int __gang_lookup_nat_cache(struct f2fs_nm_info *nm_i,
 239		nid_t start, unsigned int nr, struct nat_entry **ep)
 240{
 241	return radix_tree_gang_lookup(&nm_i->nat_root, (void **)ep, start, nr);
 242}
 243
 244static void __del_from_nat_cache(struct f2fs_nm_info *nm_i, struct nat_entry *e)
 245{
 246	radix_tree_delete(&nm_i->nat_root, nat_get_nid(e));
 247	nm_i->nat_cnt[TOTAL_NAT]--;
 248	nm_i->nat_cnt[RECLAIMABLE_NAT]--;
 249	__free_nat_entry(e);
 250}
 251
 252static struct nat_entry_set *__grab_nat_entry_set(struct f2fs_nm_info *nm_i,
 253							struct nat_entry *ne)
 254{
 255	nid_t set = NAT_BLOCK_OFFSET(ne->ni.nid);
 256	struct nat_entry_set *head;
 257
 258	head = radix_tree_lookup(&nm_i->nat_set_root, set);
 259	if (!head) {
 260		head = f2fs_kmem_cache_alloc(nat_entry_set_slab,
 261						GFP_NOFS, true, NULL);
 262
 263		INIT_LIST_HEAD(&head->entry_list);
 264		INIT_LIST_HEAD(&head->set_list);
 265		head->set = set;
 266		head->entry_cnt = 0;
 267		f2fs_radix_tree_insert(&nm_i->nat_set_root, set, head);
 268	}
 269	return head;
 270}
 271
 272static void __set_nat_cache_dirty(struct f2fs_nm_info *nm_i,
 273		struct nat_entry *ne, bool init_dirty)
 274{
 275	struct nat_entry_set *head;
 276	bool new_ne = nat_get_blkaddr(ne) == NEW_ADDR;
 277
 278	if (!new_ne)
 279		head = __grab_nat_entry_set(nm_i, ne);
 280
 281	/*
 282	 * update entry_cnt in below condition:
 283	 * 1. update NEW_ADDR to valid block address;
 284	 * 2. update old block address to new one;
 285	 */
 286	if (!new_ne && (get_nat_flag(ne, IS_PREALLOC) ||
 287				!get_nat_flag(ne, IS_DIRTY)))
 288		head->entry_cnt++;
 289
 290	set_nat_flag(ne, IS_PREALLOC, new_ne);
 291
 292	if (get_nat_flag(ne, IS_DIRTY))
 293		goto refresh_list;
 294
 295	nm_i->nat_cnt[DIRTY_NAT]++;
 296	if (!init_dirty)
 297		nm_i->nat_cnt[RECLAIMABLE_NAT]--;
 298	set_nat_flag(ne, IS_DIRTY, true);
 299refresh_list:
 300	spin_lock(&nm_i->nat_list_lock);
 301	if (new_ne)
 302		list_del_init(&ne->list);
 303	else
 304		list_move_tail(&ne->list, &head->entry_list);
 305	spin_unlock(&nm_i->nat_list_lock);
 306}
 307
 308static void __clear_nat_cache_dirty(struct f2fs_nm_info *nm_i,
 309		struct nat_entry_set *set, struct nat_entry *ne)
 310{
 311	spin_lock(&nm_i->nat_list_lock);
 312	list_move_tail(&ne->list, &nm_i->nat_entries);
 313	spin_unlock(&nm_i->nat_list_lock);
 314
 315	set_nat_flag(ne, IS_DIRTY, false);
 316	set->entry_cnt--;
 317	nm_i->nat_cnt[DIRTY_NAT]--;
 318	nm_i->nat_cnt[RECLAIMABLE_NAT]++;
 319}
 320
 321static unsigned int __gang_lookup_nat_set(struct f2fs_nm_info *nm_i,
 322		nid_t start, unsigned int nr, struct nat_entry_set **ep)
 323{
 324	return radix_tree_gang_lookup(&nm_i->nat_set_root, (void **)ep,
 325							start, nr);
 326}
 327
 328bool f2fs_in_warm_node_list(struct f2fs_sb_info *sbi, struct folio *folio)
 329{
 330	return is_node_folio(folio) && IS_DNODE(folio) && is_cold_node(folio);
 331}
 332
 333void f2fs_init_fsync_node_info(struct f2fs_sb_info *sbi)
 334{
 335	spin_lock_init(&sbi->fsync_node_lock);
 336	INIT_LIST_HEAD(&sbi->fsync_node_list);
 337	sbi->fsync_seg_id = 0;
 338	sbi->fsync_node_num = 0;
 339}
 340
 341static unsigned int f2fs_add_fsync_node_entry(struct f2fs_sb_info *sbi,
 342		struct folio *folio)
 343{
 344	struct fsync_node_entry *fn;
 345	unsigned long flags;
 346	unsigned int seq_id;
 347
 348	fn = f2fs_kmem_cache_alloc(fsync_node_entry_slab,
 349					GFP_NOFS, true, NULL);
 350
 351	folio_get(folio);
 352	fn->folio = folio;
 353	INIT_LIST_HEAD(&fn->list);
 354
 355	spin_lock_irqsave(&sbi->fsync_node_lock, flags);
 356	list_add_tail(&fn->list, &sbi->fsync_node_list);
 357	fn->seq_id = sbi->fsync_seg_id++;
 358	seq_id = fn->seq_id;
 359	sbi->fsync_node_num++;
 360	spin_unlock_irqrestore(&sbi->fsync_node_lock, flags);
 361
 362	return seq_id;
 363}
 364
 365void f2fs_del_fsync_node_entry(struct f2fs_sb_info *sbi, struct folio *folio)
 366{
 367	struct fsync_node_entry *fn;
 368	unsigned long flags;
 369
 370	spin_lock_irqsave(&sbi->fsync_node_lock, flags);
 371	list_for_each_entry(fn, &sbi->fsync_node_list, list) {
 372		if (fn->folio == folio) {
 373			list_del(&fn->list);
 374			sbi->fsync_node_num--;
 375			spin_unlock_irqrestore(&sbi->fsync_node_lock, flags);
 376			kmem_cache_free(fsync_node_entry_slab, fn);
 377			folio_put(folio);
 378			return;
 379		}
 380	}
 381	spin_unlock_irqrestore(&sbi->fsync_node_lock, flags);
 382	f2fs_bug_on(sbi, 1);
 383}
 384
 385void f2fs_reset_fsync_node_info(struct f2fs_sb_info *sbi)
 386{
 387	unsigned long flags;
 388
 389	spin_lock_irqsave(&sbi->fsync_node_lock, flags);
 390	sbi->fsync_seg_id = 0;
 391	spin_unlock_irqrestore(&sbi->fsync_node_lock, flags);
 392}
 393
 394int f2fs_need_dentry_mark(struct f2fs_sb_info *sbi, nid_t nid)
 395{
 396	struct f2fs_nm_info *nm_i = NM_I(sbi);
 397	struct nat_entry *e;
 398	bool need = false;
 399
 400	f2fs_down_read(&nm_i->nat_tree_lock);
 401	e = __lookup_nat_cache(nm_i, nid, false);
 402	if (e) {
 403		if (!get_nat_flag(e, IS_CHECKPOINTED) &&
 404				!get_nat_flag(e, HAS_FSYNCED_INODE))
 405			need = true;
 406	}
 407	f2fs_up_read(&nm_i->nat_tree_lock);
 408	return need;
 409}
 410
 411bool f2fs_is_checkpointed_node(struct f2fs_sb_info *sbi, nid_t nid)
 412{
 413	struct f2fs_nm_info *nm_i = NM_I(sbi);
 414	struct nat_entry *e;
 415	bool is_cp = true;
 416
 417	f2fs_down_read(&nm_i->nat_tree_lock);
 418	e = __lookup_nat_cache(nm_i, nid, false);
 419	if (e && !get_nat_flag(e, IS_CHECKPOINTED))
 420		is_cp = false;
 421	f2fs_up_read(&nm_i->nat_tree_lock);
 422	return is_cp;
 423}
 424
 425bool f2fs_need_inode_block_update(struct f2fs_sb_info *sbi, nid_t ino)
 426{
 427	struct f2fs_nm_info *nm_i = NM_I(sbi);
 428	struct nat_entry *e;
 429	bool need_update = true;
 430
 431	f2fs_down_read(&nm_i->nat_tree_lock);
 432	e = __lookup_nat_cache(nm_i, ino, false);
 433	if (e && get_nat_flag(e, HAS_LAST_FSYNC) &&
 434			(get_nat_flag(e, IS_CHECKPOINTED) ||
 435			 get_nat_flag(e, HAS_FSYNCED_INODE)))
 436		need_update = false;
 437	f2fs_up_read(&nm_i->nat_tree_lock);
 438	return need_update;
 439}
 440
 441/* must be locked by nat_tree_lock */
 442static void cache_nat_entry(struct f2fs_sb_info *sbi, nid_t nid,
 443						struct f2fs_nat_entry *ne)
 444{
 445	struct f2fs_nm_info *nm_i = NM_I(sbi);
 446	struct nat_entry *new, *e;
 447
 448	/* Let's mitigate lock contention of nat_tree_lock during checkpoint */
 449	if (f2fs_rwsem_is_locked(&sbi->cp_global_sem))
 450		return;
 451
 452	new = __alloc_nat_entry(sbi, nid, false);
 453	if (!new)
 454		return;
 455
 456	f2fs_down_write(&nm_i->nat_tree_lock);
 457	e = __lookup_nat_cache(nm_i, nid, false);
 458	if (!e)
 459		e = __init_nat_entry(nm_i, new, ne, false, false);
 460	else
 461		f2fs_bug_on(sbi, nat_get_ino(e) != le32_to_cpu(ne->ino) ||
 462				nat_get_blkaddr(e) !=
 463					le32_to_cpu(ne->block_addr) ||
 464				nat_get_version(e) != ne->version);
 465	f2fs_up_write(&nm_i->nat_tree_lock);
 466	if (e != new)
 467		__free_nat_entry(new);
 468}
 469
 470static void set_node_addr(struct f2fs_sb_info *sbi, struct node_info *ni,
 471			block_t new_blkaddr, bool fsync_done)
 472{
 473	struct f2fs_nm_info *nm_i = NM_I(sbi);
 474	struct nat_entry *e;
 475	struct nat_entry *new = __alloc_nat_entry(sbi, ni->nid, true);
 476	bool init_dirty = false;
 477
 478	f2fs_down_write(&nm_i->nat_tree_lock);
 479	e = __lookup_nat_cache(nm_i, ni->nid, true);
 480	if (!e) {
 481		init_dirty = true;
 482		e = __init_nat_entry(nm_i, new, NULL, true, true);
 483		copy_node_info(&e->ni, ni);
 484		f2fs_bug_on(sbi, ni->blk_addr == NEW_ADDR);
 485	} else if (new_blkaddr == NEW_ADDR) {
 486		/*
 487		 * when nid is reallocated,
 488		 * previous nat entry can be remained in nat cache.
 489		 * So, reinitialize it with new information.
 490		 */
 491		copy_node_info(&e->ni, ni);
 492		f2fs_bug_on(sbi, ni->blk_addr != NULL_ADDR);
 493	}
 494	/* let's free early to reduce memory consumption */
 495	if (e != new)
 496		__free_nat_entry(new);
 497
 498	/* sanity check */
 499	f2fs_bug_on(sbi, nat_get_blkaddr(e) != ni->blk_addr);
 500	f2fs_bug_on(sbi, nat_get_blkaddr(e) == NULL_ADDR &&
 501			new_blkaddr == NULL_ADDR);
 502	f2fs_bug_on(sbi, nat_get_blkaddr(e) == NEW_ADDR &&
 503			new_blkaddr == NEW_ADDR);
 504	f2fs_bug_on(sbi, __is_valid_data_blkaddr(nat_get_blkaddr(e)) &&
 505			new_blkaddr == NEW_ADDR);
 506
 507	/* increment version no as node is removed */
 508	if (nat_get_blkaddr(e) != NEW_ADDR && new_blkaddr == NULL_ADDR) {
 509		unsigned char version = nat_get_version(e);
 510
 511		nat_set_version(e, inc_node_version(version));
 512	}
 513
 514	/* change address */
 515	nat_set_blkaddr(e, new_blkaddr);
 516	if (!__is_valid_data_blkaddr(new_blkaddr))
 517		set_nat_flag(e, IS_CHECKPOINTED, false);
 518	__set_nat_cache_dirty(nm_i, e, init_dirty);
 519
 520	/* update fsync_mark if its inode nat entry is still alive */
 521	if (ni->nid != ni->ino)
 522		e = __lookup_nat_cache(nm_i, ni->ino, false);
 523	if (e) {
 524		if (fsync_done && ni->nid == ni->ino)
 525			set_nat_flag(e, HAS_FSYNCED_INODE, true);
 526		set_nat_flag(e, HAS_LAST_FSYNC, fsync_done);
 527	}
 528	f2fs_up_write(&nm_i->nat_tree_lock);
 529}
 530
 531int f2fs_try_to_free_nats(struct f2fs_sb_info *sbi, int nr_shrink)
 532{
 533	struct f2fs_nm_info *nm_i = NM_I(sbi);
 534	int nr = nr_shrink;
 535
 536	if (!f2fs_down_write_trylock(&nm_i->nat_tree_lock))
 537		return 0;
 538
 539	spin_lock(&nm_i->nat_list_lock);
 540	while (nr_shrink) {
 541		struct nat_entry *ne;
 542
 543		if (list_empty(&nm_i->nat_entries))
 544			break;
 545
 546		ne = list_first_entry(&nm_i->nat_entries,
 547					struct nat_entry, list);
 548		list_del(&ne->list);
 549		spin_unlock(&nm_i->nat_list_lock);
 550
 551		__del_from_nat_cache(nm_i, ne);
 552		nr_shrink--;
 553
 554		spin_lock(&nm_i->nat_list_lock);
 555	}
 556	spin_unlock(&nm_i->nat_list_lock);
 557
 558	f2fs_up_write(&nm_i->nat_tree_lock);
 559	return nr - nr_shrink;
 560}
 561
 562int f2fs_get_node_info(struct f2fs_sb_info *sbi, nid_t nid,
 563				struct node_info *ni, bool checkpoint_context)
 564{
 565	struct f2fs_nm_info *nm_i = NM_I(sbi);
 566	struct curseg_info *curseg = CURSEG_I(sbi, CURSEG_HOT_DATA);
 567	struct f2fs_journal *journal = curseg->journal;
 568	nid_t start_nid = START_NID(nid);
 569	struct f2fs_nat_block *nat_blk;
 570	struct folio *folio = NULL;
 571	struct f2fs_nat_entry ne;
 572	struct nat_entry *e;
 573	pgoff_t index;
 574	int i;
 575	bool need_cache = true;
 576
 577	ni->flag = 0;
 578	ni->nid = nid;
 579retry:
 580	/* Check nat cache */
 581	f2fs_down_read(&nm_i->nat_tree_lock);
 582	e = __lookup_nat_cache(nm_i, nid, false);
 583	if (e) {
 584		ni->ino = nat_get_ino(e);
 585		ni->blk_addr = nat_get_blkaddr(e);
 586		ni->version = nat_get_version(e);
 587		f2fs_up_read(&nm_i->nat_tree_lock);
 588		if (IS_ENABLED(CONFIG_F2FS_CHECK_FS)) {
 589			need_cache = false;
 590			goto sanity_check;
 591		}
 592		return 0;
 593	}
 594
 595	/*
 596	 * Check current segment summary by trying to grab journal_rwsem first.
 597	 * This sem is on the critical path on the checkpoint requiring the above
 598	 * nat_tree_lock. Therefore, we should retry, if we failed to grab here
 599	 * while not bothering checkpoint.
 600	 */
 601	if (!f2fs_rwsem_is_locked(&sbi->cp_global_sem) || checkpoint_context) {
 602		down_read(&curseg->journal_rwsem);
 603	} else if (f2fs_rwsem_is_contended(&nm_i->nat_tree_lock) ||
 604				!down_read_trylock(&curseg->journal_rwsem)) {
 605		f2fs_up_read(&nm_i->nat_tree_lock);
 606		goto retry;
 607	}
 608
 609	i = f2fs_lookup_journal_in_cursum(sbi, journal, NAT_JOURNAL, nid, 0);
 610	if (i >= 0) {
 611		ne = nat_in_journal(journal, i);
 612		node_info_from_raw_nat(ni, &ne);
 613	}
 614	up_read(&curseg->journal_rwsem);
 615	if (i >= 0) {
 616		f2fs_up_read(&nm_i->nat_tree_lock);
 617		goto sanity_check;
 618	}
 619
 620	/* Fill node_info from nat page */
 621	index = current_nat_addr(sbi, nid);
 622	f2fs_up_read(&nm_i->nat_tree_lock);
 623
 624	folio = f2fs_get_meta_folio(sbi, index);
 625	if (IS_ERR(folio))
 626		return PTR_ERR(folio);
 627
 628	nat_blk = folio_address(folio);
 629	ne = nat_blk->entries[nid - start_nid];
 630	node_info_from_raw_nat(ni, &ne);
 631	f2fs_folio_put(folio, true);
 632sanity_check:
 633	if (__is_valid_data_blkaddr(ni->blk_addr) &&
 634		!f2fs_is_valid_blkaddr(sbi, ni->blk_addr,
 635					DATA_GENERIC_ENHANCE)) {
 636		set_sbi_flag(sbi, SBI_NEED_FSCK);
 637		f2fs_err_ratelimited(sbi,
 638			"f2fs_get_node_info of %pS: inconsistent nat entry, "
 639			"ino:%u, nid:%u, blkaddr:%u, ver:%u, flag:%u",
 640			__builtin_return_address(0),
 641			ni->ino, ni->nid, ni->blk_addr, ni->version, ni->flag);
 642		f2fs_handle_error(sbi, ERROR_INCONSISTENT_NAT);
 643		return -EFSCORRUPTED;
 644	}
 645
 646	/* cache nat entry */
 647	if (need_cache)
 648		cache_nat_entry(sbi, nid, &ne);
 649	return 0;
 650}
 651
 652/*
 653 * readahead MAX_RA_NODE number of node pages.
 654 */
 655static void f2fs_ra_node_pages(struct folio *parent, int start, int n)
 656{
 657	struct f2fs_sb_info *sbi = F2FS_F_SB(parent);
 658	struct blk_plug plug;
 659	int i, end;
 660	nid_t nid;
 661
 662	blk_start_plug(&plug);
 663
 664	/* Then, try readahead for siblings of the desired node */
 665	end = start + n;
 666	end = min(end, (int)NIDS_PER_BLOCK);
 667	for (i = start; i < end; i++) {
 668		nid = get_nid(parent, i, false);
 669		f2fs_ra_node_page(sbi, nid);
 670	}
 671
 672	blk_finish_plug(&plug);
 673}
 674
 675pgoff_t f2fs_get_next_page_offset(struct dnode_of_data *dn, pgoff_t pgofs)
 676{
 677	const long direct_index = ADDRS_PER_INODE(dn->inode);
 678	const long direct_blks = ADDRS_PER_BLOCK(dn->inode);
 679	const long indirect_blks = ADDRS_PER_BLOCK(dn->inode) * NIDS_PER_BLOCK;
 680	unsigned int skipped_unit = ADDRS_PER_BLOCK(dn->inode);
 681	int cur_level = dn->cur_level;
 682	int max_level = dn->max_level;
 683	pgoff_t base = 0;
 684
 685	if (!dn->max_level)
 686		return pgofs + 1;
 687
 688	while (max_level-- > cur_level)
 689		skipped_unit *= NIDS_PER_BLOCK;
 690
 691	switch (dn->max_level) {
 692	case 3:
 693		base += 2 * indirect_blks;
 694		fallthrough;
 695	case 2:
 696		base += 2 * direct_blks;
 697		fallthrough;
 698	case 1:
 699		base += direct_index;
 700		break;
 701	default:
 702		f2fs_bug_on(F2FS_I_SB(dn->inode), 1);
 703	}
 704
 705	return ((pgofs - base) / skipped_unit + 1) * skipped_unit + base;
 706}
 707
 708/*
 709 * The maximum depth is four.
 710 * Offset[0] will have raw inode offset.
 711 */
 712static int get_node_path(struct inode *inode, long block,
 713				int offset[4], unsigned int noffset[4])
 714{
 715	const long direct_index = ADDRS_PER_INODE(inode);
 716	const long direct_blks = ADDRS_PER_BLOCK(inode);
 717	const long dptrs_per_blk = NIDS_PER_BLOCK;
 718	const long indirect_blks = ADDRS_PER_BLOCK(inode) * NIDS_PER_BLOCK;
 719	const long dindirect_blks = indirect_blks * NIDS_PER_BLOCK;
 720	int n = 0;
 721	int level = 0;
 722
 723	noffset[0] = 0;
 724
 725	if (block < direct_index) {
 726		offset[n] = block;
 727		goto got;
 728	}
 729	block -= direct_index;
 730	if (block < direct_blks) {
 731		offset[n++] = NODE_DIR1_BLOCK;
 732		noffset[n] = 1;
 733		offset[n] = block;
 734		level = 1;
 735		goto got;
 736	}
 737	block -= direct_blks;
 738	if (block < direct_blks) {
 739		offset[n++] = NODE_DIR2_BLOCK;
 740		noffset[n] = 2;
 741		offset[n] = block;
 742		level = 1;
 743		goto got;
 744	}
 745	block -= direct_blks;
 746	if (block < indirect_blks) {
 747		offset[n++] = NODE_IND1_BLOCK;
 748		noffset[n] = 3;
 749		offset[n++] = block / direct_blks;
 750		noffset[n] = 4 + offset[n - 1];
 751		offset[n] = block % direct_blks;
 752		level = 2;
 753		goto got;
 754	}
 755	block -= indirect_blks;
 756	if (block < indirect_blks) {
 757		offset[n++] = NODE_IND2_BLOCK;
 758		noffset[n] = 4 + dptrs_per_blk;
 759		offset[n++] = block / direct_blks;
 760		noffset[n] = 5 + dptrs_per_blk + offset[n - 1];
 761		offset[n] = block % direct_blks;
 762		level = 2;
 763		goto got;
 764	}
 765	block -= indirect_blks;
 766	if (block < dindirect_blks) {
 767		offset[n++] = NODE_DIND_BLOCK;
 768		noffset[n] = 5 + (dptrs_per_blk * 2);
 769		offset[n++] = block / indirect_blks;
 770		noffset[n] = 6 + (dptrs_per_blk * 2) +
 771			      offset[n - 1] * (dptrs_per_blk + 1);
 772		offset[n++] = (block / direct_blks) % dptrs_per_blk;
 773		noffset[n] = 7 + (dptrs_per_blk * 2) +
 774			      offset[n - 2] * (dptrs_per_blk + 1) +
 775			      offset[n - 1];
 776		offset[n] = block % direct_blks;
 777		level = 3;
 778		goto got;
 779	} else {
 780		return -E2BIG;
 781	}
 782got:
 783	return level;
 784}
 785
 786static struct folio *f2fs_get_node_folio_ra(struct folio *parent, int start);
 787
 788/*
 789 * Caller should call f2fs_put_dnode(dn).
 790 * Also, it should grab and release a rwsem by calling f2fs_lock_op() and
 791 * f2fs_unlock_op() only if mode is set with ALLOC_NODE.
 792 */
 793int f2fs_get_dnode_of_data(struct dnode_of_data *dn, pgoff_t index, int mode)
 794{
 795	struct f2fs_sb_info *sbi = F2FS_I_SB(dn->inode);
 796	struct folio *nfolio[4];
 797	struct folio *parent = NULL;
 798	int offset[4];
 799	unsigned int noffset[4];
 800	nid_t nids[4];
 801	int level, i = 0;
 802	int err = 0;
 803
 804	level = get_node_path(dn->inode, index, offset, noffset);
 805	if (level < 0)
 806		return level;
 807
 808	nids[0] = dn->inode->i_ino;
 809
 810	if (!dn->inode_folio) {
 811		nfolio[0] = f2fs_get_inode_folio(sbi, nids[0]);
 812		if (IS_ERR(nfolio[0]))
 813			return PTR_ERR(nfolio[0]);
 814	} else {
 815		nfolio[0] = dn->inode_folio;
 816	}
 817
 818	/* if inline_data is set, should not report any block indices */
 819	if (f2fs_has_inline_data(dn->inode) && index) {
 820		err = -ENOENT;
 821		f2fs_folio_put(nfolio[0], true);
 822		goto release_out;
 823	}
 824
 825	parent = nfolio[0];
 826	if (level != 0)
 827		nids[1] = get_nid(parent, offset[0], true);
 828	dn->inode_folio = nfolio[0];
 829	dn->inode_folio_locked = true;
 830
 831	/* get indirect or direct nodes */
 832	for (i = 1; i <= level; i++) {
 833		bool done = false;
 834
 835		if (nids[i] && nids[i] == dn->inode->i_ino) {
 836			err = -EFSCORRUPTED;
 837			f2fs_err_ratelimited(sbi,
 838				"inode mapping table is corrupted, run fsck to fix it, "
 839				"ino:%lu, nid:%u, level:%d, offset:%d",
 840				dn->inode->i_ino, nids[i], level, offset[level]);
 841			set_sbi_flag(sbi, SBI_NEED_FSCK);
 842			goto release_pages;
 843		}
 844
 845		if (!nids[i] && mode == ALLOC_NODE) {
 846			/* alloc new node */
 847			if (!f2fs_alloc_nid(sbi, &(nids[i]))) {
 848				err = -ENOSPC;
 849				goto release_pages;
 850			}
 851
 852			dn->nid = nids[i];
 853			nfolio[i] = f2fs_new_node_folio(dn, noffset[i]);
 854			if (IS_ERR(nfolio[i])) {
 855				f2fs_alloc_nid_failed(sbi, nids[i]);
 856				err = PTR_ERR(nfolio[i]);
 857				goto release_pages;
 858			}
 859
 860			set_nid(parent, offset[i - 1], nids[i], i == 1);
 861			f2fs_alloc_nid_done(sbi, nids[i]);
 862			done = true;
 863		} else if (mode == LOOKUP_NODE_RA && i == level && level > 1) {
 864			nfolio[i] = f2fs_get_node_folio_ra(parent, offset[i - 1]);
 865			if (IS_ERR(nfolio[i])) {
 866				err = PTR_ERR(nfolio[i]);
 867				goto release_pages;
 868			}
 869			done = true;
 870		}
 871		if (i == 1) {
 872			dn->inode_folio_locked = false;
 873			folio_unlock(parent);
 874		} else {
 875			f2fs_folio_put(parent, true);
 876		}
 877
 878		if (!done) {
 879			nfolio[i] = f2fs_get_node_folio(sbi, nids[i],
 880						NODE_TYPE_NON_INODE);
 881			if (IS_ERR(nfolio[i])) {
 882				err = PTR_ERR(nfolio[i]);
 883				f2fs_folio_put(nfolio[0], false);
 884				goto release_out;
 885			}
 886		}
 887		if (i < level) {
 888			parent = nfolio[i];
 889			nids[i + 1] = get_nid(parent, offset[i], false);
 890		}
 891	}
 892	dn->nid = nids[level];
 893	dn->ofs_in_node = offset[level];
 894	dn->node_folio = nfolio[level];
 895	dn->data_blkaddr = f2fs_data_blkaddr(dn);
 896
 897	if (is_inode_flag_set(dn->inode, FI_COMPRESSED_FILE) &&
 898					f2fs_sb_has_readonly(sbi)) {
 899		unsigned int cluster_size = F2FS_I(dn->inode)->i_cluster_size;
 900		unsigned int ofs_in_node = dn->ofs_in_node;
 901		pgoff_t fofs = index;
 902		unsigned int c_len;
 903		block_t blkaddr;
 904
 905		/* should align fofs and ofs_in_node to cluster_size */
 906		if (fofs % cluster_size) {
 907			fofs = round_down(fofs, cluster_size);
 908			ofs_in_node = round_down(ofs_in_node, cluster_size);
 909		}
 910
 911		c_len = f2fs_cluster_blocks_are_contiguous(dn, ofs_in_node);
 912		if (!c_len)
 913			goto out;
 914
 915		blkaddr = data_blkaddr(dn->inode, dn->node_folio, ofs_in_node);
 916		if (blkaddr == COMPRESS_ADDR)
 917			blkaddr = data_blkaddr(dn->inode, dn->node_folio,
 918						ofs_in_node + 1);
 919
 920		f2fs_update_read_extent_tree_range_compressed(dn->inode,
 921					fofs, blkaddr, cluster_size, c_len);
 922	}
 923out:
 924	return 0;
 925
 926release_pages:
 927	f2fs_folio_put(parent, true);
 928	if (i > 1)
 929		f2fs_folio_put(nfolio[0], false);
 930release_out:
 931	dn->inode_folio = NULL;
 932	dn->node_folio = NULL;
 933	if (err == -ENOENT) {
 934		dn->cur_level = i;
 935		dn->max_level = level;
 936		dn->ofs_in_node = offset[level];
 937	}
 938	return err;
 939}
 940
 941static int truncate_node(struct dnode_of_data *dn)
 942{
 943	struct f2fs_sb_info *sbi = F2FS_I_SB(dn->inode);
 944	struct node_info ni;
 945	int err;
 946	pgoff_t index;
 947
 948	err = f2fs_get_node_info(sbi, dn->nid, &ni, false);
 949	if (err)
 950		return err;
 951
 952	if (ni.blk_addr != NEW_ADDR &&
 953		!f2fs_is_valid_blkaddr(sbi, ni.blk_addr, DATA_GENERIC_ENHANCE)) {
 954		f2fs_err_ratelimited(sbi,
 955			"nat entry is corrupted, run fsck to fix it, ino:%u, "
 956			"nid:%u, blkaddr:%u", ni.ino, ni.nid, ni.blk_addr);
 957		set_sbi_flag(sbi, SBI_NEED_FSCK);
 958		f2fs_handle_error(sbi, ERROR_INCONSISTENT_NAT);
 959		return -EFSCORRUPTED;
 960	}
 961
 962	/* Deallocate node address */
 963	f2fs_invalidate_blocks(sbi, ni.blk_addr, 1);
 964	dec_valid_node_count(sbi, dn->inode, dn->nid == dn->inode->i_ino);
 965	set_node_addr(sbi, &ni, NULL_ADDR, false);
 966
 967	if (dn->nid == dn->inode->i_ino) {
 968		f2fs_remove_orphan_inode(sbi, dn->nid);
 969		dec_valid_inode_count(sbi);
 970		f2fs_inode_synced(dn->inode);
 971	}
 972
 973	clear_node_folio_dirty(dn->node_folio);
 974	set_sbi_flag(sbi, SBI_IS_DIRTY);
 975
 976	index = dn->node_folio->index;
 977	f2fs_folio_put(dn->node_folio, true);
 978
 979	invalidate_mapping_pages(NODE_MAPPING(sbi),
 980			index, index);
 981
 982	dn->node_folio = NULL;
 983	trace_f2fs_truncate_node(dn->inode, dn->nid, ni.blk_addr);
 984
 985	return 0;
 986}
 987
 988static int truncate_dnode(struct dnode_of_data *dn)
 989{
 990	struct f2fs_sb_info *sbi = F2FS_I_SB(dn->inode);
 991	struct folio *folio;
 992	int err;
 993
 994	if (dn->nid == 0)
 995		return 1;
 996
 997	/* get direct node */
 998	folio = f2fs_get_node_folio(sbi, dn->nid, NODE_TYPE_NON_INODE);
 999	if (PTR_ERR(folio) == -ENOENT)
1000		return 1;
1001	else if (IS_ERR(folio))
1002		return PTR_ERR(folio);
1003
1004	if (IS_INODE(folio) || ino_of_node(folio) != dn->inode->i_ino) {
1005		f2fs_err(sbi, "incorrect node reference, ino: %lu, nid: %u, ino_of_node: %u",
1006				dn->inode->i_ino, dn->nid, ino_of_node(folio));
1007		set_sbi_flag(sbi, SBI_NEED_FSCK);
1008		f2fs_handle_error(sbi, ERROR_INVALID_NODE_REFERENCE);
1009		f2fs_folio_put(folio, true);
1010		return -EFSCORRUPTED;
1011	}
1012
1013	/* Make dnode_of_data for parameter */
1014	dn->node_folio = folio;
1015	dn->ofs_in_node = 0;
1016	f2fs_truncate_data_blocks_range(dn, ADDRS_PER_BLOCK(dn->inode));
1017	err = truncate_node(dn);
1018	if (err) {
1019		f2fs_folio_put(folio, true);
1020		return err;
1021	}
1022
1023	return 1;
1024}
1025
1026static int truncate_nodes(struct dnode_of_data *dn, unsigned int nofs,
1027						int ofs, int depth)
1028{
1029	struct dnode_of_data rdn = *dn;
1030	struct folio *folio;
1031	struct f2fs_node *rn;
1032	nid_t child_nid;
1033	unsigned int child_nofs;
1034	int freed = 0;
1035	int i, ret;
1036
1037	if (dn->nid == 0)
1038		return NIDS_PER_BLOCK + 1;
1039
1040	trace_f2fs_truncate_nodes_enter(dn->inode, dn->nid, dn->data_blkaddr);
1041
1042	folio = f2fs_get_node_folio(F2FS_I_SB(dn->inode), dn->nid,
1043						NODE_TYPE_NON_INODE);
1044	if (IS_ERR(folio)) {
1045		trace_f2fs_truncate_nodes_exit(dn->inode, PTR_ERR(folio));
1046		return PTR_ERR(folio);
1047	}
1048
1049	f2fs_ra_node_pages(folio, ofs, NIDS_PER_BLOCK);
1050
1051	rn = F2FS_NODE(folio);
1052	if (depth < 3) {
1053		for (i = ofs; i < NIDS_PER_BLOCK; i++, freed++) {
1054			child_nid = le32_to_cpu(rn->in.nid[i]);
1055			if (child_nid == 0)
1056				continue;
1057			rdn.nid = child_nid;
1058			ret = truncate_dnode(&rdn);
1059			if (ret < 0)
1060				goto out_err;
1061			if (set_nid(folio, i, 0, false))
1062				dn->node_changed = true;
1063		}
1064	} else {
1065		child_nofs = nofs + ofs * (NIDS_PER_BLOCK + 1) + 1;
1066		for (i = ofs; i < NIDS_PER_BLOCK; i++) {
1067			child_nid = le32_to_cpu(rn->in.nid[i]);
1068			if (child_nid == 0) {
1069				child_nofs += NIDS_PER_BLOCK + 1;
1070				continue;
1071			}
1072			rdn.nid = child_nid;
1073			ret = truncate_nodes(&rdn, child_nofs, 0, depth - 1);
1074			if (ret == (NIDS_PER_BLOCK + 1)) {
1075				if (set_nid(folio, i, 0, false))
1076					dn->node_changed = true;
1077				child_nofs += ret;
1078			} else if (ret < 0 && ret != -ENOENT) {
1079				goto out_err;
1080			}
1081		}
1082		freed = child_nofs;
1083	}
1084
1085	if (!ofs) {
1086		/* remove current indirect node */
1087		dn->node_folio = folio;
1088		ret = truncate_node(dn);
1089		if (ret)
1090			goto out_err;
1091		freed++;
1092	} else {
1093		f2fs_folio_put(folio, true);
1094	}
1095	trace_f2fs_truncate_nodes_exit(dn->inode, freed);
1096	return freed;
1097
1098out_err:
1099	f2fs_folio_put(folio, true);
1100	trace_f2fs_truncate_nodes_exit(dn->inode, ret);
1101	return ret;
1102}
1103
1104static int truncate_partial_nodes(struct dnode_of_data *dn,
1105			struct f2fs_inode *ri, int *offset, int depth)
1106{
1107	struct folio *folios[2];
1108	nid_t nid[3];
1109	nid_t child_nid;
1110	int err = 0;
1111	int i;
1112	int idx = depth - 2;
1113
1114	nid[0] = get_nid(dn->inode_folio, offset[0], true);
1115	if (!nid[0])
1116		return 0;
1117
1118	/* get indirect nodes in the path */
1119	for (i = 0; i < idx + 1; i++) {
1120		/* reference count'll be increased */
1121		folios[i] = f2fs_get_node_folio(F2FS_I_SB(dn->inode), nid[i],
1122							NODE_TYPE_NON_INODE);
1123		if (IS_ERR(folios[i])) {
1124			err = PTR_ERR(folios[i]);
1125			idx = i - 1;
1126			goto fail;
1127		}
1128		nid[i + 1] = get_nid(folios[i], offset[i + 1], false);
1129	}
1130
1131	f2fs_ra_node_pages(folios[idx], offset[idx + 1], NIDS_PER_BLOCK);
1132
1133	/* free direct nodes linked to a partial indirect node */
1134	for (i = offset[idx + 1]; i < NIDS_PER_BLOCK; i++) {
1135		child_nid = get_nid(folios[idx], i, false);
1136		if (!child_nid)
1137			continue;
1138		dn->nid = child_nid;
1139		err = truncate_dnode(dn);
1140		if (err < 0)
1141			goto fail;
1142		if (set_nid(folios[idx], i, 0, false))
1143			dn->node_changed = true;
1144	}
1145
1146	if (offset[idx + 1] == 0) {
1147		dn->node_folio = folios[idx];
1148		dn->nid = nid[idx];
1149		err = truncate_node(dn);
1150		if (err)
1151			goto fail;
1152	} else {
1153		f2fs_folio_put(folios[idx], true);
1154	}
1155	offset[idx]++;
1156	offset[idx + 1] = 0;
1157	idx--;
1158fail:
1159	for (i = idx; i >= 0; i--)
1160		f2fs_folio_put(folios[i], true);
1161
1162	trace_f2fs_truncate_partial_nodes(dn->inode, nid, depth, err);
1163
1164	return err;
1165}
1166
1167/*
1168 * All the block addresses of data and nodes should be nullified.
1169 */
1170int f2fs_truncate_inode_blocks(struct inode *inode, pgoff_t from)
1171{
1172	struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
1173	int err = 0, cont = 1;
1174	int level, offset[4], noffset[4];
1175	unsigned int nofs = 0;
1176	struct f2fs_inode *ri;
1177	struct dnode_of_data dn;
1178	struct folio *folio;
1179
1180	trace_f2fs_truncate_inode_blocks_enter(inode, from);
1181
1182	level = get_node_path(inode, from, offset, noffset);
1183	if (level <= 0) {
1184		if (!level) {
1185			level = -EFSCORRUPTED;
1186			f2fs_err(sbi, "%s: inode ino=%lx has corrupted node block, from:%lu addrs:%u",
1187					__func__, inode->i_ino,
1188					from, ADDRS_PER_INODE(inode));
1189			set_sbi_flag(sbi, SBI_NEED_FSCK);
1190		}
1191		trace_f2fs_truncate_inode_blocks_exit(inode, level);
1192		return level;
1193	}
1194
1195	folio = f2fs_get_inode_folio(sbi, inode->i_ino);
1196	if (IS_ERR(folio)) {
1197		trace_f2fs_truncate_inode_blocks_exit(inode, PTR_ERR(folio));
1198		return PTR_ERR(folio);
1199	}
1200
1201	set_new_dnode(&dn, inode, folio, NULL, 0);
1202	folio_unlock(folio);
1203
1204	ri = F2FS_INODE(folio);
1205	switch (level) {
1206	case 0:
1207	case 1:
1208		nofs = noffset[1];
1209		break;
1210	case 2:
1211		nofs = noffset[1];
1212		if (!offset[level - 1])
1213			goto skip_partial;
1214		err = truncate_partial_nodes(&dn, ri, offset, level);
1215		if (err < 0 && err != -ENOENT)
1216			goto fail;
1217		nofs += 1 + NIDS_PER_BLOCK;
1218		break;
1219	case 3:
1220		nofs = 5 + 2 * NIDS_PER_BLOCK;
1221		if (!offset[level - 1])
1222			goto skip_partial;
1223		err = truncate_partial_nodes(&dn, ri, offset, level);
1224		if (err < 0 && err != -ENOENT)
1225			goto fail;
1226		break;
1227	default:
1228		BUG();
1229	}
1230
1231skip_partial:
1232	while (cont) {
1233		dn.nid = get_nid(folio, offset[0], true);
1234		switch (offset[0]) {
1235		case NODE_DIR1_BLOCK:
1236		case NODE_DIR2_BLOCK:
1237			err = truncate_dnode(&dn);
1238			break;
1239
1240		case NODE_IND1_BLOCK:
1241		case NODE_IND2_BLOCK:
1242			err = truncate_nodes(&dn, nofs, offset[1], 2);
1243			break;
1244
1245		case NODE_DIND_BLOCK:
1246			err = truncate_nodes(&dn, nofs, offset[1], 3);
1247			cont = 0;
1248			break;
1249
1250		default:
1251			BUG();
1252		}
1253		if (err == -ENOENT) {
1254			set_sbi_flag(F2FS_F_SB(folio), SBI_NEED_FSCK);
1255			f2fs_handle_error(sbi, ERROR_INVALID_BLKADDR);
1256			f2fs_err_ratelimited(sbi,
1257				"truncate node fail, ino:%lu, nid:%u, "
1258				"offset[0]:%d, offset[1]:%d, nofs:%d",
1259				inode->i_ino, dn.nid, offset[0],
1260				offset[1], nofs);
1261			err = 0;
1262		}
1263		if (err < 0)
1264			goto fail;
1265		if (offset[1] == 0 && get_nid(folio, offset[0], true)) {
1266			folio_lock(folio);
1267			BUG_ON(!is_node_folio(folio));
1268			set_nid(folio, offset[0], 0, true);
1269			folio_unlock(folio);
1270		}
1271		offset[1] = 0;
1272		offset[0]++;
1273		nofs += err;
1274	}
1275fail:
1276	f2fs_folio_put(folio, false);
1277	trace_f2fs_truncate_inode_blocks_exit(inode, err);
1278	return err > 0 ? 0 : err;
1279}
1280
1281/* caller must lock inode page */
1282int f2fs_truncate_xattr_node(struct inode *inode)
1283{
1284	struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
1285	nid_t nid = F2FS_I(inode)->i_xattr_nid;
1286	struct dnode_of_data dn;
1287	struct folio *nfolio;
1288	int err;
1289
1290	if (!nid)
1291		return 0;
1292
1293	nfolio = f2fs_get_xnode_folio(sbi, nid);
1294	if (IS_ERR(nfolio))
1295		return PTR_ERR(nfolio);
1296
1297	set_new_dnode(&dn, inode, NULL, nfolio, nid);
1298	err = truncate_node(&dn);
1299	if (err) {
1300		f2fs_folio_put(nfolio, true);
1301		return err;
1302	}
1303
1304	f2fs_i_xnid_write(inode, 0);
1305
1306	return 0;
1307}
1308
1309/*
1310 * Caller should grab and release a rwsem by calling f2fs_lock_op() and
1311 * f2fs_unlock_op().
1312 */
1313int f2fs_remove_inode_page(struct inode *inode)
1314{
1315	struct dnode_of_data dn;
1316	int err;
1317
1318	set_new_dnode(&dn, inode, NULL, NULL, inode->i_ino);
1319	err = f2fs_get_dnode_of_data(&dn, 0, LOOKUP_NODE);
1320	if (err)
1321		return err;
1322
1323	err = f2fs_truncate_xattr_node(inode);
1324	if (err) {
1325		f2fs_put_dnode(&dn);
1326		return err;
1327	}
1328
1329	/* remove potential inline_data blocks */
1330	if (!IS_DEVICE_ALIASING(inode) &&
1331	    (S_ISREG(inode->i_mode) || S_ISDIR(inode->i_mode) ||
1332	     S_ISLNK(inode->i_mode)))
1333		f2fs_truncate_data_blocks_range(&dn, 1);
1334
1335	/* 0 is possible, after f2fs_new_inode() has failed */
1336	if (unlikely(f2fs_cp_error(F2FS_I_SB(inode)))) {
1337		f2fs_put_dnode(&dn);
1338		return -EIO;
1339	}
1340
1341	if (unlikely(inode->i_blocks != 0 && inode->i_blocks != 8)) {
1342		f2fs_warn(F2FS_I_SB(inode),
1343			"f2fs_remove_inode_page: inconsistent i_blocks, ino:%lu, iblocks:%llu",
1344			inode->i_ino, (unsigned long long)inode->i_blocks);
1345		set_sbi_flag(F2FS_I_SB(inode), SBI_NEED_FSCK);
1346	}
1347
1348	/* will put inode & node pages */
1349	err = truncate_node(&dn);
1350	if (err) {
1351		f2fs_put_dnode(&dn);
1352		return err;
1353	}
1354	return 0;
1355}
1356
1357struct folio *f2fs_new_inode_folio(struct inode *inode)
1358{
1359	struct dnode_of_data dn;
1360
1361	/* allocate inode page for new inode */
1362	set_new_dnode(&dn, inode, NULL, NULL, inode->i_ino);
1363
1364	/* caller should f2fs_folio_put(folio, true); */
1365	return f2fs_new_node_folio(&dn, 0);
1366}
1367
1368struct folio *f2fs_new_node_folio(struct dnode_of_data *dn, unsigned int ofs)
1369{
1370	struct f2fs_sb_info *sbi = F2FS_I_SB(dn->inode);
1371	struct node_info new_ni;
1372	struct folio *folio;
1373	int err;
1374
1375	if (unlikely(is_inode_flag_set(dn->inode, FI_NO_ALLOC)))
1376		return ERR_PTR(-EPERM);
1377
1378	folio = f2fs_grab_cache_folio(NODE_MAPPING(sbi), dn->nid, false);
1379	if (IS_ERR(folio))
1380		return folio;
1381
1382	if (unlikely((err = inc_valid_node_count(sbi, dn->inode, !ofs))))
1383		goto fail;
1384
1385#ifdef CONFIG_F2FS_CHECK_FS
1386	err = f2fs_get_node_info(sbi, dn->nid, &new_ni, false);
1387	if (err) {
1388		dec_valid_node_count(sbi, dn->inode, !ofs);
1389		goto fail;
1390	}
1391	if (unlikely(new_ni.blk_addr != NULL_ADDR)) {
1392		err = -EFSCORRUPTED;
1393		dec_valid_node_count(sbi, dn->inode, !ofs);
1394		set_sbi_flag(sbi, SBI_NEED_FSCK);
1395		f2fs_warn_ratelimited(sbi,
1396			"f2fs_new_node_folio: inconsistent nat entry, "
1397			"ino:%u, nid:%u, blkaddr:%u, ver:%u, flag:%u",
1398			new_ni.ino, new_ni.nid, new_ni.blk_addr,
1399			new_ni.version, new_ni.flag);
1400		f2fs_handle_error(sbi, ERROR_INCONSISTENT_NAT);
1401		goto fail;
1402	}
1403#endif
1404	new_ni.nid = dn->nid;
1405	new_ni.ino = dn->inode->i_ino;
1406	new_ni.blk_addr = NULL_ADDR;
1407	new_ni.flag = 0;
1408	new_ni.version = 0;
1409	set_node_addr(sbi, &new_ni, NEW_ADDR, false);
1410
1411	f2fs_folio_wait_writeback(folio, NODE, true, true);
1412	fill_node_footer(folio, dn->nid, dn->inode->i_ino, ofs, true);
1413	set_cold_node(folio, S_ISDIR(dn->inode->i_mode));
1414	if (!folio_test_uptodate(folio))
1415		folio_mark_uptodate(folio);
1416	if (folio_mark_dirty(folio))
1417		dn->node_changed = true;
1418
1419	if (f2fs_has_xattr_block(ofs))
1420		f2fs_i_xnid_write(dn->inode, dn->nid);
1421
1422	if (ofs == 0)
1423		inc_valid_inode_count(sbi);
1424	return folio;
1425fail:
1426	clear_node_folio_dirty(folio);
1427	f2fs_folio_put(folio, true);
1428	return ERR_PTR(err);
1429}
1430
1431/*
1432 * Caller should do after getting the following values.
1433 * 0: f2fs_folio_put(folio, false)
1434 * LOCKED_PAGE or error: f2fs_folio_put(folio, true)
1435 */
1436static int read_node_folio(struct folio *folio, blk_opf_t op_flags)
1437{
1438	struct f2fs_sb_info *sbi = F2FS_F_SB(folio);
1439	struct node_info ni;
1440	struct f2fs_io_info fio = {
1441		.sbi = sbi,
1442		.type = NODE,
1443		.op = REQ_OP_READ,
1444		.op_flags = op_flags,
1445		.folio = folio,
1446		.encrypted_page = NULL,
1447	};
1448	int err;
1449
1450	if (folio_test_uptodate(folio)) {
1451		if (!f2fs_inode_chksum_verify(sbi, folio)) {
1452			folio_clear_uptodate(folio);
1453			return -EFSBADCRC;
1454		}
1455		return LOCKED_PAGE;
1456	}
1457
1458	err = f2fs_get_node_info(sbi, folio->index, &ni, false);
1459	if (err)
1460		return err;
1461
1462	/* NEW_ADDR can be seen, after cp_error drops some dirty node pages */
1463	if (unlikely(ni.blk_addr == NULL_ADDR || ni.blk_addr == NEW_ADDR)) {
1464		folio_clear_uptodate(folio);
1465		return -ENOENT;
1466	}
1467
1468	fio.new_blkaddr = fio.old_blkaddr = ni.blk_addr;
1469
1470	err = f2fs_submit_page_bio(&fio);
1471
1472	if (!err)
1473		f2fs_update_iostat(sbi, NULL, FS_NODE_READ_IO, F2FS_BLKSIZE);
1474
1475	return err;
1476}
1477
1478/*
1479 * Readahead a node page
1480 */
1481void f2fs_ra_node_page(struct f2fs_sb_info *sbi, nid_t nid)
1482{
1483	struct folio *afolio;
1484	int err;
1485
1486	if (!nid)
1487		return;
1488	if (f2fs_check_nid_range(sbi, nid))
1489		return;
1490
1491	afolio = xa_load(&NODE_MAPPING(sbi)->i_pages, nid);
1492	if (afolio)
1493		return;
1494
1495	afolio = f2fs_grab_cache_folio(NODE_MAPPING(sbi), nid, false);
1496	if (IS_ERR(afolio))
1497		return;
1498
1499	err = read_node_folio(afolio, REQ_RAHEAD);
1500	f2fs_folio_put(afolio, err ? true : false);
1501}
1502
1503int f2fs_sanity_check_node_footer(struct f2fs_sb_info *sbi,
1504					struct folio *folio, pgoff_t nid,
1505					enum node_type ntype, bool in_irq)
1506{
1507	if (unlikely(nid != nid_of_node(folio)))
1508		goto out_err;
1509
1510	switch (ntype) {
1511	case NODE_TYPE_INODE:
1512		if (!IS_INODE(folio))
1513			goto out_err;
1514		break;
1515	case NODE_TYPE_XATTR:
1516		if (!f2fs_has_xattr_block(ofs_of_node(folio)))
1517			goto out_err;
1518		break;
1519	case NODE_TYPE_NON_INODE:
1520		if (IS_INODE(folio))
1521			goto out_err;
1522		break;
1523	default:
1524		break;
1525	}
1526	if (time_to_inject(sbi, FAULT_INCONSISTENT_FOOTER))
1527		goto out_err;
1528	return 0;
1529out_err:
1530	set_sbi_flag(sbi, SBI_NEED_FSCK);
1531	f2fs_warn_ratelimited(sbi, "inconsistent node block, node_type:%d, nid:%lu, "
1532		"node_footer[nid:%u,ino:%u,ofs:%u,cpver:%llu,blkaddr:%u]",
1533		ntype, nid, nid_of_node(folio), ino_of_node(folio),
1534		ofs_of_node(folio), cpver_of_node(folio),
1535		next_blkaddr_of_node(folio));
1536
1537	f2fs_handle_error(sbi, ERROR_INCONSISTENT_FOOTER);
1538	return -EFSCORRUPTED;
1539}
1540
1541static struct folio *__get_node_folio(struct f2fs_sb_info *sbi, pgoff_t nid,
1542		struct folio *parent, int start, enum node_type ntype)
1543{
1544	struct folio *folio;
1545	int err;
1546
1547	if (!nid)
1548		return ERR_PTR(-ENOENT);
1549	if (f2fs_check_nid_range(sbi, nid))
1550		return ERR_PTR(-EINVAL);
1551repeat:
1552	folio = f2fs_grab_cache_folio(NODE_MAPPING(sbi), nid, false);
1553	if (IS_ERR(folio))
1554		return folio;
1555
1556	err = read_node_folio(folio, 0);
1557	if (err < 0)
1558		goto out_put_err;
1559	if (err == LOCKED_PAGE)
1560		goto page_hit;
1561
1562	if (parent)
1563		f2fs_ra_node_pages(parent, start + 1, MAX_RA_NODE);
1564
1565	folio_lock(folio);
1566
1567	if (unlikely(!is_node_folio(folio))) {
1568		f2fs_folio_put(folio, true);
1569		goto repeat;
1570	}
1571
1572	if (unlikely(!folio_test_uptodate(folio))) {
1573		err = -EIO;
1574		goto out_put_err;
1575	}
1576
1577	if (!f2fs_inode_chksum_verify(sbi, folio)) {
1578		err = -EFSBADCRC;
1579		goto out_err;
1580	}
1581page_hit:
1582	err = f2fs_sanity_check_node_footer(sbi, folio, nid, ntype, false);
1583	if (!err)
1584		return folio;
1585out_err:
1586	folio_clear_uptodate(folio);
1587out_put_err:
1588	/* ENOENT comes from read_node_folio which is not an error. */
1589	if (err != -ENOENT)
1590		f2fs_handle_page_eio(sbi, folio, NODE);
1591	f2fs_folio_put(folio, true);
1592	return ERR_PTR(err);
1593}
1594
1595struct folio *f2fs_get_node_folio(struct f2fs_sb_info *sbi, pgoff_t nid,
1596						enum node_type node_type)
1597{
1598	return __get_node_folio(sbi, nid, NULL, 0, node_type);
1599}
1600
1601struct folio *f2fs_get_inode_folio(struct f2fs_sb_info *sbi, pgoff_t ino)
1602{
1603	return __get_node_folio(sbi, ino, NULL, 0, NODE_TYPE_INODE);
1604}
1605
1606struct folio *f2fs_get_xnode_folio(struct f2fs_sb_info *sbi, pgoff_t xnid)
1607{
1608	return __get_node_folio(sbi, xnid, NULL, 0, NODE_TYPE_XATTR);
1609}
1610
1611static struct folio *f2fs_get_node_folio_ra(struct folio *parent, int start)
1612{
1613	struct f2fs_sb_info *sbi = F2FS_F_SB(parent);
1614	nid_t nid = get_nid(parent, start, false);
1615
1616	return __get_node_folio(sbi, nid, parent, start, NODE_TYPE_REGULAR);
1617}
1618
1619static void flush_inline_data(struct f2fs_sb_info *sbi, nid_t ino)
1620{
1621	struct inode *inode;
1622	struct folio *folio;
1623	int ret;
1624
1625	/* should flush inline_data before evict_inode */
1626	inode = ilookup(sbi->sb, ino);
1627	if (!inode)
1628		return;
1629
1630	folio = f2fs_filemap_get_folio(inode->i_mapping, 0,
1631					FGP_LOCK|FGP_NOWAIT, 0);
1632	if (IS_ERR(folio))
1633		goto iput_out;
1634
1635	if (!folio_test_uptodate(folio))
1636		goto folio_out;
1637
1638	if (!folio_test_dirty(folio))
1639		goto folio_out;
1640
1641	if (!folio_clear_dirty_for_io(folio))
1642		goto folio_out;
1643
1644	ret = f2fs_write_inline_data(inode, folio);
1645	inode_dec_dirty_pages(inode);
1646	f2fs_remove_dirty_inode(inode);
1647	if (ret)
1648		folio_mark_dirty(folio);
1649folio_out:
1650	f2fs_folio_put(folio, true);
1651iput_out:
1652	iput(inode);
1653}
1654
1655static struct folio *last_fsync_dnode(struct f2fs_sb_info *sbi, nid_t ino)
1656{
1657	pgoff_t index;
1658	struct folio_batch fbatch;
1659	struct folio *last_folio = NULL;
1660	int nr_folios;
1661
1662	folio_batch_init(&fbatch);
1663	index = 0;
1664
1665	while ((nr_folios = filemap_get_folios_tag(NODE_MAPPING(sbi), &index,
1666					(pgoff_t)-1, PAGECACHE_TAG_DIRTY,
1667					&fbatch))) {
1668		int i;
1669
1670		for (i = 0; i < nr_folios; i++) {
1671			struct folio *folio = fbatch.folios[i];
1672
1673			if (unlikely(f2fs_cp_error(sbi))) {
1674				f2fs_folio_put(last_folio, false);
1675				folio_batch_release(&fbatch);
1676				return ERR_PTR(-EIO);
1677			}
1678
1679			if (!IS_DNODE(folio) || !is_cold_node(folio))
1680				continue;
1681			if (ino_of_node(folio) != ino)
1682				continue;
1683
1684			folio_lock(folio);
1685
1686			if (unlikely(!is_node_folio(folio))) {
1687continue_unlock:
1688				folio_unlock(folio);
1689				continue;
1690			}
1691			if (ino_of_node(folio) != ino)
1692				goto continue_unlock;
1693
1694			if (!folio_test_dirty(folio)) {
1695				/* someone wrote it for us */
1696				goto continue_unlock;
1697			}
1698
1699			if (last_folio)
1700				f2fs_folio_put(last_folio, false);
1701
1702			folio_get(folio);
1703			last_folio = folio;
1704			folio_unlock(folio);
1705		}
1706		folio_batch_release(&fbatch);
1707		cond_resched();
1708	}
1709	return last_folio;
1710}
1711
1712static bool __write_node_folio(struct folio *folio, bool atomic, bool *submitted,
1713				struct writeback_control *wbc, bool do_balance,
1714				enum iostat_type io_type, unsigned int *seq_id)
1715{
1716	struct f2fs_sb_info *sbi = F2FS_F_SB(folio);
1717	nid_t nid;
1718	struct node_info ni;
1719	struct f2fs_io_info fio = {
1720		.sbi = sbi,
1721		.ino = ino_of_node(folio),
1722		.type = NODE,
1723		.op = REQ_OP_WRITE,
1724		.op_flags = wbc_to_write_flags(wbc),
1725		.folio = folio,
1726		.encrypted_page = NULL,
1727		.submitted = 0,
1728		.io_type = io_type,
1729		.io_wbc = wbc,
1730	};
1731	unsigned int seq;
1732
1733	trace_f2fs_writepage(folio, NODE);
1734
1735	if (unlikely(f2fs_cp_error(sbi))) {
1736		/* keep node pages in remount-ro mode */
1737		if (F2FS_OPTION(sbi).errors == MOUNT_ERRORS_READONLY)
1738			goto redirty_out;
1739		folio_clear_uptodate(folio);
1740		dec_page_count(sbi, F2FS_DIRTY_NODES);
1741		folio_unlock(folio);
1742		return true;
1743	}
1744
1745	if (unlikely(is_sbi_flag_set(sbi, SBI_POR_DOING)))
1746		goto redirty_out;
1747
1748	if (!is_sbi_flag_set(sbi, SBI_CP_DISABLED) &&
1749			wbc->sync_mode == WB_SYNC_NONE &&
1750			IS_DNODE(folio) && is_cold_node(folio))
1751		goto redirty_out;
1752
1753	/* get old block addr of this node page */
1754	nid = nid_of_node(folio);
1755
1756	if (f2fs_sanity_check_node_footer(sbi, folio, nid,
1757					NODE_TYPE_REGULAR, false)) {
1758		f2fs_handle_critical_error(sbi, STOP_CP_REASON_CORRUPTED_NID);
1759		goto redirty_out;
1760	}
1761
1762	if (f2fs_get_node_info(sbi, nid, &ni, !do_balance))
1763		goto redirty_out;
1764
1765	f2fs_down_read(&sbi->node_write);
1766
1767	/* This page is already truncated */
1768	if (unlikely(ni.blk_addr == NULL_ADDR)) {
1769		folio_clear_uptodate(folio);
1770		dec_page_count(sbi, F2FS_DIRTY_NODES);
1771		f2fs_up_read(&sbi->node_write);
1772		folio_unlock(folio);
1773		return true;
1774	}
1775
1776	if (__is_valid_data_blkaddr(ni.blk_addr) &&
1777		!f2fs_is_valid_blkaddr(sbi, ni.blk_addr,
1778					DATA_GENERIC_ENHANCE)) {
1779		f2fs_up_read(&sbi->node_write);
1780		goto redirty_out;
1781	}
1782
1783	if (atomic) {
1784		if (!test_opt(sbi, NOBARRIER))
1785			fio.op_flags |= REQ_PREFLUSH | REQ_FUA;
1786		if (IS_INODE(folio))
1787			set_dentry_mark(folio,
1788				f2fs_need_dentry_mark(sbi, ino_of_node(folio)));
1789	}
1790
1791	/* should add to global list before clearing PAGECACHE status */
1792	if (f2fs_in_warm_node_list(sbi, folio)) {
1793		seq = f2fs_add_fsync_node_entry(sbi, folio);
1794		if (seq_id)
1795			*seq_id = seq;
1796	}
1797
1798	folio_start_writeback(folio);
1799
1800	fio.old_blkaddr = ni.blk_addr;
1801	f2fs_do_write_node_page(nid, &fio);
1802	set_node_addr(sbi, &ni, fio.new_blkaddr, is_fsync_dnode(folio));
1803	dec_page_count(sbi, F2FS_DIRTY_NODES);
1804	f2fs_up_read(&sbi->node_write);
1805
1806	folio_unlock(folio);
1807
1808	if (unlikely(f2fs_cp_error(sbi))) {
1809		f2fs_submit_merged_write(sbi, NODE);
1810		submitted = NULL;
1811	}
1812	if (submitted)
1813		*submitted = fio.submitted;
1814
1815	if (do_balance)
1816		f2fs_balance_fs(sbi, false);
1817	return true;
1818
1819redirty_out:
1820	folio_redirty_for_writepage(wbc, folio);
1821	folio_unlock(folio);
1822	return false;
1823}
1824
1825int f2fs_move_node_folio(struct folio *node_folio, int gc_type)
1826{
1827	int err = 0;
1828
1829	if (gc_type == FG_GC) {
1830		struct writeback_control wbc = {
1831			.sync_mode = WB_SYNC_ALL,
1832			.nr_to_write = 1,
1833		};
1834
1835		f2fs_folio_wait_writeback(node_folio, NODE, true, true);
1836
1837		folio_mark_dirty(node_folio);
1838
1839		if (!folio_clear_dirty_for_io(node_folio)) {
1840			err = -EAGAIN;
1841			goto out_page;
1842		}
1843
1844		if (!__write_node_folio(node_folio, false, NULL,
1845					&wbc, false, FS_GC_NODE_IO, NULL))
1846			err = -EAGAIN;
1847		goto release_page;
1848	} else {
1849		/* set page dirty and write it */
1850		if (!folio_test_writeback(node_folio))
1851			folio_mark_dirty(node_folio);
1852	}
1853out_page:
1854	folio_unlock(node_folio);
1855release_page:
1856	f2fs_folio_put(node_folio, false);
1857	return err;
1858}
1859
1860int f2fs_fsync_node_pages(struct f2fs_sb_info *sbi, struct inode *inode,
1861			struct writeback_control *wbc, bool atomic,
1862			unsigned int *seq_id)
1863{
1864	pgoff_t index;
1865	struct folio_batch fbatch;
1866	int ret = 0;
1867	struct folio *last_folio = NULL;
1868	bool marked = false;
1869	nid_t ino = inode->i_ino;
1870	int nr_folios;
1871	int nwritten = 0;
1872
1873	if (atomic) {
1874		last_folio = last_fsync_dnode(sbi, ino);
1875		if (IS_ERR_OR_NULL(last_folio))
1876			return PTR_ERR_OR_ZERO(last_folio);
1877	}
1878retry:
1879	folio_batch_init(&fbatch);
1880	index = 0;
1881
1882	while ((nr_folios = filemap_get_folios_tag(NODE_MAPPING(sbi), &index,
1883					(pgoff_t)-1, PAGECACHE_TAG_DIRTY,
1884					&fbatch))) {
1885		int i;
1886
1887		for (i = 0; i < nr_folios; i++) {
1888			struct folio *folio = fbatch.folios[i];
1889			bool submitted = false;
1890
1891			if (unlikely(f2fs_cp_error(sbi))) {
1892				f2fs_folio_put(last_folio, false);
1893				folio_batch_release(&fbatch);
1894				ret = -EIO;
1895				goto out;
1896			}
1897
1898			if (!IS_DNODE(folio) || !is_cold_node(folio))
1899				continue;
1900			if (ino_of_node(folio) != ino)
1901				continue;
1902
1903			folio_lock(folio);
1904
1905			if (unlikely(!is_node_folio(folio))) {
1906continue_unlock:
1907				folio_unlock(folio);
1908				continue;
1909			}
1910			if (ino_of_node(folio) != ino)
1911				goto continue_unlock;
1912
1913			if (!folio_test_dirty(folio) && folio != last_folio) {
1914				/* someone wrote it for us */
1915				goto continue_unlock;
1916			}
1917
1918			f2fs_folio_wait_writeback(folio, NODE, true, true);
1919
1920			set_fsync_mark(folio, 0);
1921			set_dentry_mark(folio, 0);
1922
1923			if (!atomic || folio == last_folio) {
1924				set_fsync_mark(folio, 1);
1925				percpu_counter_inc(&sbi->rf_node_block_count);
1926				if (IS_INODE(folio)) {
1927					if (is_inode_flag_set(inode,
1928								FI_DIRTY_INODE))
1929						f2fs_update_inode(inode, folio);
1930					if (!atomic)
1931						set_dentry_mark(folio,
1932							f2fs_need_dentry_mark(sbi, ino));
1933				}
1934				/* may be written by other thread */
1935				if (!folio_test_dirty(folio))
1936					folio_mark_dirty(folio);
1937			}
1938
1939			if (!folio_clear_dirty_for_io(folio))
1940				goto continue_unlock;
1941
1942			if (!__write_node_folio(folio, atomic &&
1943						folio == last_folio,
1944						&submitted, wbc, true,
1945						FS_NODE_IO, seq_id)) {
1946				f2fs_folio_put(last_folio, false);
1947				folio_batch_release(&fbatch);
1948				ret = -EIO;
1949				goto out;
1950			}
1951			if (submitted)
1952				nwritten++;
1953
1954			if (folio == last_folio) {
1955				f2fs_folio_put(folio, false);
1956				folio_batch_release(&fbatch);
1957				marked = true;
1958				goto out;
1959			}
1960		}
1961		folio_batch_release(&fbatch);
1962		cond_resched();
1963	}
1964	if (atomic && !marked) {
1965		f2fs_debug(sbi, "Retry to write fsync mark: ino=%u, idx=%lx",
1966			   ino, last_folio->index);
1967		folio_lock(last_folio);
1968		f2fs_folio_wait_writeback(last_folio, NODE, true, true);
1969		folio_mark_dirty(last_folio);
1970		folio_unlock(last_folio);
1971		goto retry;
1972	}
1973out:
1974	if (nwritten)
1975		f2fs_submit_merged_write_cond(sbi, NULL, NULL, ino, NODE);
1976	return ret;
1977}
1978
1979static int f2fs_match_ino(struct inode *inode, unsigned long ino, void *data)
1980{
1981	struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
1982	bool clean;
1983
1984	if (inode->i_ino != ino)
1985		return 0;
1986
1987	if (!is_inode_flag_set(inode, FI_DIRTY_INODE))
1988		return 0;
1989
1990	spin_lock(&sbi->inode_lock[DIRTY_META]);
1991	clean = list_empty(&F2FS_I(inode)->gdirty_list);
1992	spin_unlock(&sbi->inode_lock[DIRTY_META]);
1993
1994	if (clean)
1995		return 0;
1996
1997	inode = igrab(inode);
1998	if (!inode)
1999		return 0;
2000	return 1;
2001}
2002
2003static bool flush_dirty_inode(struct folio *folio)
2004{
2005	struct f2fs_sb_info *sbi = F2FS_F_SB(folio);
2006	struct inode *inode;
2007	nid_t ino = ino_of_node(folio);
2008
2009	inode = find_inode_nowait(sbi->sb, ino, f2fs_match_ino, NULL);
2010	if (!inode)
2011		return false;
2012
2013	f2fs_update_inode(inode, folio);
2014	folio_unlock(folio);
2015
2016	iput(inode);
2017	return true;
2018}
2019
2020void f2fs_flush_inline_data(struct f2fs_sb_info *sbi)
2021{
2022	pgoff_t index = 0;
2023	struct folio_batch fbatch;
2024	int nr_folios;
2025
2026	folio_batch_init(&fbatch);
2027
2028	while ((nr_folios = filemap_get_folios_tag(NODE_MAPPING(sbi), &index,
2029					(pgoff_t)-1, PAGECACHE_TAG_DIRTY,
2030					&fbatch))) {
2031		int i;
2032
2033		for (i = 0; i < nr_folios; i++) {
2034			struct folio *folio = fbatch.folios[i];
2035
2036			if (!IS_INODE(folio))
2037				continue;
2038
2039			folio_lock(folio);
2040
2041			if (unlikely(!is_node_folio(folio)))
2042				goto unlock;
2043			if (!folio_test_dirty(folio))
2044				goto unlock;
2045
2046			/* flush inline_data, if it's async context. */
2047			if (folio_test_f2fs_inline(folio)) {
2048				folio_clear_f2fs_inline(folio);
2049				folio_unlock(folio);
2050				flush_inline_data(sbi, ino_of_node(folio));
2051				continue;
2052			}
2053unlock:
2054			folio_unlock(folio);
2055		}
2056		folio_batch_release(&fbatch);
2057		cond_resched();
2058	}
2059}
2060
2061int f2fs_sync_node_pages(struct f2fs_sb_info *sbi,
2062				struct writeback_control *wbc,
2063				bool do_balance, enum iostat_type io_type)
2064{
2065	pgoff_t index;
2066	struct folio_batch fbatch;
2067	int step = 0;
2068	int nwritten = 0;
2069	int ret = 0;
2070	int nr_folios, done = 0;
2071
2072	folio_batch_init(&fbatch);
2073
2074next_step:
2075	index = 0;
2076
2077	while (!done && (nr_folios = filemap_get_folios_tag(NODE_MAPPING(sbi),
2078				&index, (pgoff_t)-1, PAGECACHE_TAG_DIRTY,
2079				&fbatch))) {
2080		int i;
2081
2082		for (i = 0; i < nr_folios; i++) {
2083			struct folio *folio = fbatch.folios[i];
2084			bool submitted = false;
2085
2086			/* give a priority to WB_SYNC threads */
2087			if (atomic_read(&sbi->wb_sync_req[NODE]) &&
2088					wbc->sync_mode == WB_SYNC_NONE) {
2089				done = 1;
2090				break;
2091			}
2092
2093			/*
2094			 * flushing sequence with step:
2095			 * 0. indirect nodes
2096			 * 1. dentry dnodes
2097			 * 2. file dnodes
2098			 */
2099			if (step == 0 && IS_DNODE(folio))
2100				continue;
2101			if (step == 1 && (!IS_DNODE(folio) ||
2102						is_cold_node(folio)))
2103				continue;
2104			if (step == 2 && (!IS_DNODE(folio) ||
2105						!is_cold_node(folio)))
2106				continue;
2107lock_node:
2108			if (wbc->sync_mode == WB_SYNC_ALL)
2109				folio_lock(folio);
2110			else if (!folio_trylock(folio))
2111				continue;
2112
2113			if (unlikely(!is_node_folio(folio))) {
2114continue_unlock:
2115				folio_unlock(folio);
2116				continue;
2117			}
2118
2119			if (!folio_test_dirty(folio)) {
2120				/* someone wrote it for us */
2121				goto continue_unlock;
2122			}
2123
2124			/* flush inline_data/inode, if it's async context. */
2125			if (!do_balance)
2126				goto write_node;
2127
2128			/* flush inline_data */
2129			if (folio_test_f2fs_inline(folio)) {
2130				folio_clear_f2fs_inline(folio);
2131				folio_unlock(folio);
2132				flush_inline_data(sbi, ino_of_node(folio));
2133				goto lock_node;
2134			}
2135
2136			/* flush dirty inode */
2137			if (IS_INODE(folio) && flush_dirty_inode(folio))
2138				goto lock_node;
2139write_node:
2140			f2fs_folio_wait_writeback(folio, NODE, true, true);
2141
2142			if (!folio_clear_dirty_for_io(folio))
2143				goto continue_unlock;
2144
2145			set_fsync_mark(folio, 0);
2146			set_dentry_mark(folio, 0);
2147
2148			if (!__write_node_folio(folio, false, &submitted,
2149					wbc, do_balance, io_type, NULL)) {
2150				folio_batch_release(&fbatch);
2151				ret = -EIO;
2152				goto out;
2153			}
2154			if (submitted)
2155				nwritten++;
2156
2157			if (--wbc->nr_to_write == 0)
2158				break;
2159		}
2160		folio_batch_release(&fbatch);
2161		cond_resched();
2162
2163		if (wbc->nr_to_write == 0) {
2164			step = 2;
2165			break;
2166		}
2167	}
2168
2169	if (step < 2) {
2170		if (!is_sbi_flag_set(sbi, SBI_CP_DISABLED) &&
2171				wbc->sync_mode == WB_SYNC_NONE && step == 1)
2172			goto out;
2173		step++;
2174		goto next_step;
2175	}
2176out:
2177	if (nwritten)
2178		f2fs_submit_merged_write(sbi, NODE);
2179
2180	if (unlikely(f2fs_cp_error(sbi)))
2181		return -EIO;
2182	return ret;
2183}
2184
2185int f2fs_wait_on_node_pages_writeback(struct f2fs_sb_info *sbi,
2186						unsigned int seq_id)
2187{
2188	struct fsync_node_entry *fn;
2189	struct list_head *head = &sbi->fsync_node_list;
2190	unsigned long flags;
2191	unsigned int cur_seq_id = 0;
2192
2193	while (seq_id && cur_seq_id < seq_id) {
2194		struct folio *folio;
2195
2196		spin_lock_irqsave(&sbi->fsync_node_lock, flags);
2197		if (list_empty(head)) {
2198			spin_unlock_irqrestore(&sbi->fsync_node_lock, flags);
2199			break;
2200		}
2201		fn = list_first_entry(head, struct fsync_node_entry, list);
2202		if (fn->seq_id > seq_id) {
2203			spin_unlock_irqrestore(&sbi->fsync_node_lock, flags);
2204			break;
2205		}
2206		cur_seq_id = fn->seq_id;
2207		folio = fn->folio;
2208		folio_get(folio);
2209		spin_unlock_irqrestore(&sbi->fsync_node_lock, flags);
2210
2211		f2fs_folio_wait_writeback(folio, NODE, true, false);
2212
2213		folio_put(folio);
2214	}
2215
2216	return filemap_check_errors(NODE_MAPPING(sbi));
2217}
2218
2219static int f2fs_write_node_pages(struct address_space *mapping,
2220			    struct writeback_control *wbc)
2221{
2222	struct f2fs_sb_info *sbi = F2FS_M_SB(mapping);
2223	struct blk_plug plug;
2224	long diff;
2225
2226	if (unlikely(is_sbi_flag_set(sbi, SBI_POR_DOING)))
2227		goto skip_write;
2228
2229	/* balancing f2fs's metadata in background */
2230	f2fs_balance_fs_bg(sbi, true);
2231
2232	/* collect a number of dirty node pages and write together */
2233	if (wbc->sync_mode != WB_SYNC_ALL &&
2234			get_pages(sbi, F2FS_DIRTY_NODES) <
2235					nr_pages_to_skip(sbi, NODE))
2236		goto skip_write;
2237
2238	if (wbc->sync_mode == WB_SYNC_ALL)
2239		atomic_inc(&sbi->wb_sync_req[NODE]);
2240	else if (atomic_read(&sbi->wb_sync_req[NODE])) {
2241		/* to avoid potential deadlock */
2242		if (current->plug)
2243			blk_finish_plug(current->plug);
2244		goto skip_write;
2245	}
2246
2247	trace_f2fs_writepages(mapping->host, wbc, NODE);
2248
2249	diff = nr_pages_to_write(sbi, NODE, wbc);
2250	blk_start_plug(&plug);
2251	f2fs_sync_node_pages(sbi, wbc, true, FS_NODE_IO);
2252	blk_finish_plug(&plug);
2253	wbc->nr_to_write = max((long)0, wbc->nr_to_write - diff);
2254
2255	if (wbc->sync_mode == WB_SYNC_ALL)
2256		atomic_dec(&sbi->wb_sync_req[NODE]);
2257	return 0;
2258
2259skip_write:
2260	wbc->pages_skipped += get_pages(sbi, F2FS_DIRTY_NODES);
2261	trace_f2fs_writepages(mapping->host, wbc, NODE);
2262	return 0;
2263}
2264
2265static bool f2fs_dirty_node_folio(struct address_space *mapping,
2266		struct folio *folio)
2267{
2268	trace_f2fs_set_page_dirty(folio, NODE);
2269
2270	if (!folio_test_uptodate(folio))
2271		folio_mark_uptodate(folio);
2272#ifdef CONFIG_F2FS_CHECK_FS
2273	if (IS_INODE(folio))
2274		f2fs_inode_chksum_set(F2FS_M_SB(mapping), folio);
2275#endif
2276	if (filemap_dirty_folio(mapping, folio)) {
2277		inc_page_count(F2FS_M_SB(mapping), F2FS_DIRTY_NODES);
2278		folio_set_f2fs_reference(folio);
2279		return true;
2280	}
2281	return false;
2282}
2283
2284/*
2285 * Structure of the f2fs node operations
2286 */
2287const struct address_space_operations f2fs_node_aops = {
2288	.writepages	= f2fs_write_node_pages,
2289	.dirty_folio	= f2fs_dirty_node_folio,
2290	.invalidate_folio = f2fs_invalidate_folio,
2291	.release_folio	= f2fs_release_folio,
2292	.migrate_folio	= filemap_migrate_folio,
2293};
2294
2295static struct free_nid *__lookup_free_nid_list(struct f2fs_nm_info *nm_i,
2296						nid_t n)
2297{
2298	return radix_tree_lookup(&nm_i->free_nid_root, n);
2299}
2300
2301static int __insert_free_nid(struct f2fs_sb_info *sbi,
2302				struct free_nid *i)
2303{
2304	struct f2fs_nm_info *nm_i = NM_I(sbi);
2305	int err = radix_tree_insert(&nm_i->free_nid_root, i->nid, i);
2306
2307	if (err)
2308		return err;
2309
2310	nm_i->nid_cnt[FREE_NID]++;
2311	list_add_tail(&i->list, &nm_i->free_nid_list);
2312	return 0;
2313}
2314
2315static void __remove_free_nid(struct f2fs_sb_info *sbi,
2316			struct free_nid *i, enum nid_state state)
2317{
2318	struct f2fs_nm_info *nm_i = NM_I(sbi);
2319
2320	f2fs_bug_on(sbi, state != i->state);
2321	nm_i->nid_cnt[state]--;
2322	if (state == FREE_NID)
2323		list_del(&i->list);
2324	radix_tree_delete(&nm_i->free_nid_root, i->nid);
2325}
2326
2327static void __move_free_nid(struct f2fs_sb_info *sbi, struct free_nid *i,
2328			enum nid_state org_state, enum nid_state dst_state)
2329{
2330	struct f2fs_nm_info *nm_i = NM_I(sbi);
2331
2332	f2fs_bug_on(sbi, org_state != i->state);
2333	i->state = dst_state;
2334	nm_i->nid_cnt[org_state]--;
2335	nm_i->nid_cnt[dst_state]++;
2336
2337	switch (dst_state) {
2338	case PREALLOC_NID:
2339		list_del(&i->list);
2340		break;
2341	case FREE_NID:
2342		list_add_tail(&i->list, &nm_i->free_nid_list);
2343		break;
2344	default:
2345		BUG_ON(1);
2346	}
2347}
2348
2349static void update_free_nid_bitmap(struct f2fs_sb_info *sbi, nid_t nid,
2350							bool set, bool build)
2351{
2352	struct f2fs_nm_info *nm_i = NM_I(sbi);
2353	unsigned int nat_ofs = NAT_BLOCK_OFFSET(nid);
2354	unsigned int nid_ofs = nid - START_NID(nid);
2355
2356	if (!test_bit_le(nat_ofs, nm_i->nat_block_bitmap))
2357		return;
2358
2359	if (set) {
2360		if (test_bit_le(nid_ofs, nm_i->free_nid_bitmap[nat_ofs]))
2361			return;
2362		__set_bit_le(nid_ofs, nm_i->free_nid_bitmap[nat_ofs]);
2363		nm_i->free_nid_count[nat_ofs]++;
2364	} else {
2365		if (!test_bit_le(nid_ofs, nm_i->free_nid_bitmap[nat_ofs]))
2366			return;
2367		__clear_bit_le(nid_ofs, nm_i->free_nid_bitmap[nat_ofs]);
2368		if (!build)
2369			nm_i->free_nid_count[nat_ofs]--;
2370	}
2371}
2372
2373/* return if the nid is recognized as free */
2374static bool add_free_nid(struct f2fs_sb_info *sbi,
2375				nid_t nid, bool build, bool update)
2376{
2377	struct f2fs_nm_info *nm_i = NM_I(sbi);
2378	struct free_nid *i, *e;
2379	struct nat_entry *ne;
2380	int err;
2381	bool ret = false;
2382
2383	/* 0 nid should not be used */
2384	if (unlikely(nid == 0))
2385		return false;
2386
2387	if (unlikely(f2fs_check_nid_range(sbi, nid)))
2388		return false;
2389
2390	i = f2fs_kmem_cache_alloc(free_nid_slab, GFP_NOFS, true, NULL);
2391	i->nid = nid;
2392	i->state = FREE_NID;
2393
2394	err = radix_tree_preload(GFP_NOFS | __GFP_NOFAIL);
2395	f2fs_bug_on(sbi, err);
2396
2397	err = -EINVAL;
2398
2399	spin_lock(&nm_i->nid_list_lock);
2400
2401	if (build) {
2402		/*
2403		 *   Thread A             Thread B
2404		 *  - f2fs_create
2405		 *   - f2fs_new_inode
2406		 *    - f2fs_alloc_nid
2407		 *     - __insert_nid_to_list(PREALLOC_NID)
2408		 *                     - f2fs_balance_fs_bg
2409		 *                      - f2fs_build_free_nids
2410		 *                       - __f2fs_build_free_nids
2411		 *                        - scan_nat_page
2412		 *                         - add_free_nid
2413		 *                          - __lookup_nat_cache
2414		 *  - f2fs_add_link
2415		 *   - f2fs_init_inode_metadata
2416		 *    - f2fs_new_inode_folio
2417		 *     - f2fs_new_node_folio
2418		 *      - set_node_addr
2419		 *  - f2fs_alloc_nid_done
2420		 *   - __remove_nid_from_list(PREALLOC_NID)
2421		 *                         - __insert_nid_to_list(FREE_NID)
2422		 */
2423		ne = __lookup_nat_cache(nm_i, nid, false);
2424		if (ne && (!get_nat_flag(ne, IS_CHECKPOINTED) ||
2425				nat_get_blkaddr(ne) != NULL_ADDR))
2426			goto err_out;
2427
2428		e = __lookup_free_nid_list(nm_i, nid);
2429		if (e) {
2430			if (e->state == FREE_NID)
2431				ret = true;
2432			goto err_out;
2433		}
2434	}
2435	ret = true;
2436	err = __insert_free_nid(sbi, i);
2437err_out:
2438	if (update) {
2439		update_free_nid_bitmap(sbi, nid, ret, build);
2440		if (!build)
2441			nm_i->available_nids++;
2442	}
2443	spin_unlock(&nm_i->nid_list_lock);
2444	radix_tree_preload_end();
2445
2446	if (err)
2447		kmem_cache_free(free_nid_slab, i);
2448	return ret;
2449}
2450
2451static void remove_free_nid(struct f2fs_sb_info *sbi, nid_t nid)
2452{
2453	struct f2fs_nm_info *nm_i = NM_I(sbi);
2454	struct free_nid *i;
2455	bool need_free = false;
2456
2457	spin_lock(&nm_i->nid_list_lock);
2458	i = __lookup_free_nid_list(nm_i, nid);
2459	if (i && i->state == FREE_NID) {
2460		__remove_free_nid(sbi, i, FREE_NID);
2461		need_free = true;
2462	}
2463	spin_unlock(&nm_i->nid_list_lock);
2464
2465	if (need_free)
2466		kmem_cache_free(free_nid_slab, i);
2467}
2468
2469static int scan_nat_page(struct f2fs_sb_info *sbi,
2470			struct f2fs_nat_block *nat_blk, nid_t start_nid)
2471{
2472	struct f2fs_nm_info *nm_i = NM_I(sbi);
2473	block_t blk_addr;
2474	unsigned int nat_ofs = NAT_BLOCK_OFFSET(start_nid);
2475	int i;
2476
2477	__set_bit_le(nat_ofs, nm_i->nat_block_bitmap);
2478
2479	i = start_nid % NAT_ENTRY_PER_BLOCK;
2480
2481	for (; i < NAT_ENTRY_PER_BLOCK; i++, start_nid++) {
2482		if (unlikely(start_nid >= nm_i->max_nid))
2483			break;
2484
2485		blk_addr = le32_to_cpu(nat_blk->entries[i].block_addr);
2486
2487		if (blk_addr == NEW_ADDR)
2488			return -EFSCORRUPTED;
2489
2490		if (blk_addr == NULL_ADDR) {
2491			add_free_nid(sbi, start_nid, true, true);
2492		} else {
2493			spin_lock(&NM_I(sbi)->nid_list_lock);
2494			update_free_nid_bitmap(sbi, start_nid, false, true);
2495			spin_unlock(&NM_I(sbi)->nid_list_lock);
2496		}
2497	}
2498
2499	return 0;
2500}
2501
2502static void scan_curseg_cache(struct f2fs_sb_info *sbi)
2503{
2504	struct curseg_info *curseg = CURSEG_I(sbi, CURSEG_HOT_DATA);
2505	struct f2fs_journal *journal = curseg->journal;
2506	int i;
2507
2508	down_read(&curseg->journal_rwsem);
2509	for (i = 0; i < nats_in_cursum(journal); i++) {
2510		block_t addr;
2511		nid_t nid;
2512
2513		addr = le32_to_cpu(nat_in_journal(journal, i).block_addr);
2514		nid = le32_to_cpu(nid_in_journal(journal, i));
2515		if (addr == NULL_ADDR)
2516			add_free_nid(sbi, nid, true, false);
2517		else
2518			remove_free_nid(sbi, nid);
2519	}
2520	up_read(&curseg->journal_rwsem);
2521}
2522
2523static void scan_free_nid_bits(struct f2fs_sb_info *sbi)
2524{
2525	struct f2fs_nm_info *nm_i = NM_I(sbi);
2526	unsigned int i, idx;
2527	nid_t nid;
2528
2529	f2fs_down_read(&nm_i->nat_tree_lock);
2530
2531	for (i = 0; i < nm_i->nat_blocks; i++) {
2532		if (!test_bit_le(i, nm_i->nat_block_bitmap))
2533			continue;
2534		if (!nm_i->free_nid_count[i])
2535			continue;
2536		for (idx = 0; idx < NAT_ENTRY_PER_BLOCK; idx++) {
2537			idx = find_next_bit_le(nm_i->free_nid_bitmap[i],
2538						NAT_ENTRY_PER_BLOCK, idx);
2539			if (idx >= NAT_ENTRY_PER_BLOCK)
2540				break;
2541
2542			nid = i * NAT_ENTRY_PER_BLOCK + idx;
2543			add_free_nid(sbi, nid, true, false);
2544
2545			if (nm_i->nid_cnt[FREE_NID] >= MAX_FREE_NIDS)
2546				goto out;
2547		}
2548	}
2549out:
2550	scan_curseg_cache(sbi);
2551
2552	f2fs_up_read(&nm_i->nat_tree_lock);
2553}
2554
2555static int __f2fs_build_free_nids(struct f2fs_sb_info *sbi,
2556						bool sync, bool mount)
2557{
2558	struct f2fs_nm_info *nm_i = NM_I(sbi);
2559	int i = 0, ret;
2560	nid_t nid = nm_i->next_scan_nid;
2561
2562	if (unlikely(nid >= nm_i->max_nid))
2563		nid = 0;
2564
2565	if (unlikely(nid % NAT_ENTRY_PER_BLOCK))
2566		nid = NAT_BLOCK_OFFSET(nid) * NAT_ENTRY_PER_BLOCK;
2567
2568	/* Enough entries */
2569	if (nm_i->nid_cnt[FREE_NID] >= NAT_ENTRY_PER_BLOCK)
2570		return 0;
2571
2572	if (!sync && !f2fs_available_free_memory(sbi, FREE_NIDS))
2573		return 0;
2574
2575	if (!mount) {
2576		/* try to find free nids in free_nid_bitmap */
2577		scan_free_nid_bits(sbi);
2578
2579		if (nm_i->nid_cnt[FREE_NID] >= NAT_ENTRY_PER_BLOCK)
2580			return 0;
2581	}
2582
2583	/* readahead nat pages to be scanned */
2584	f2fs_ra_meta_pages(sbi, NAT_BLOCK_OFFSET(nid), FREE_NID_PAGES,
2585							META_NAT, true);
2586
2587	f2fs_down_read(&nm_i->nat_tree_lock);
2588
2589	while (1) {
2590		if (!test_bit_le(NAT_BLOCK_OFFSET(nid),
2591						nm_i->nat_block_bitmap)) {
2592			struct folio *folio = get_current_nat_folio(sbi, nid);
2593
2594			if (IS_ERR(folio)) {
2595				ret = PTR_ERR(folio);
2596			} else {
2597				ret = scan_nat_page(sbi, folio_address(folio),
2598						nid);
2599				f2fs_folio_put(folio, true);
2600			}
2601
2602			if (ret) {
2603				f2fs_up_read(&nm_i->nat_tree_lock);
2604
2605				if (ret == -EFSCORRUPTED) {
2606					f2fs_err(sbi, "NAT is corrupt, run fsck to fix it");
2607					set_sbi_flag(sbi, SBI_NEED_FSCK);
2608					f2fs_handle_error(sbi,
2609						ERROR_INCONSISTENT_NAT);
2610				}
2611
2612				return ret;
2613			}
2614		}
2615
2616		nid += (NAT_ENTRY_PER_BLOCK - (nid % NAT_ENTRY_PER_BLOCK));
2617		if (unlikely(nid >= nm_i->max_nid))
2618			nid = 0;
2619
2620		if (++i >= FREE_NID_PAGES)
2621			break;
2622	}
2623
2624	/* go to the next free nat pages to find free nids abundantly */
2625	nm_i->next_scan_nid = nid;
2626
2627	/* find free nids from current sum_pages */
2628	scan_curseg_cache(sbi);
2629
2630	f2fs_up_read(&nm_i->nat_tree_lock);
2631
2632	f2fs_ra_meta_pages(sbi, NAT_BLOCK_OFFSET(nm_i->next_scan_nid),
2633					nm_i->ra_nid_pages, META_NAT, false);
2634
2635	return 0;
2636}
2637
2638int f2fs_build_free_nids(struct f2fs_sb_info *sbi, bool sync, bool mount)
2639{
2640	int ret;
2641
2642	mutex_lock(&NM_I(sbi)->build_lock);
2643	ret = __f2fs_build_free_nids(sbi, sync, mount);
2644	mutex_unlock(&NM_I(sbi)->build_lock);
2645
2646	return ret;
2647}
2648
2649/*
2650 * If this function returns success, caller can obtain a new nid
2651 * from second parameter of this function.
2652 * The returned nid could be used ino as well as nid when inode is created.
2653 */
2654bool f2fs_alloc_nid(struct f2fs_sb_info *sbi, nid_t *nid)
2655{
2656	struct f2fs_nm_info *nm_i = NM_I(sbi);
2657	struct free_nid *i = NULL;
2658retry:
2659	if (time_to_inject(sbi, FAULT_ALLOC_NID))
2660		return false;
2661
2662	spin_lock(&nm_i->nid_list_lock);
2663
2664	if (unlikely(nm_i->available_nids == 0)) {
2665		spin_unlock(&nm_i->nid_list_lock);
2666		return false;
2667	}
2668
2669	/* We should not use stale free nids created by f2fs_build_free_nids */
2670	if (nm_i->nid_cnt[FREE_NID] && !on_f2fs_build_free_nids(nm_i)) {
2671		f2fs_bug_on(sbi, list_empty(&nm_i->free_nid_list));
2672		i = list_first_entry(&nm_i->free_nid_list,
2673					struct free_nid, list);
2674
2675		if (unlikely(is_invalid_nid(sbi, i->nid))) {
2676			spin_unlock(&nm_i->nid_list_lock);
2677			f2fs_err(sbi, "Corrupted nid %u in free_nid_list",
2678								i->nid);
2679			f2fs_stop_checkpoint(sbi, false,
2680					STOP_CP_REASON_CORRUPTED_NID);
2681			return false;
2682		}
2683
2684		*nid = i->nid;
2685
2686		__move_free_nid(sbi, i, FREE_NID, PREALLOC_NID);
2687		nm_i->available_nids--;
2688
2689		update_free_nid_bitmap(sbi, *nid, false, false);
2690
2691		spin_unlock(&nm_i->nid_list_lock);
2692		return true;
2693	}
2694	spin_unlock(&nm_i->nid_list_lock);
2695
2696	/* Let's scan nat pages and its caches to get free nids */
2697	if (!f2fs_build_free_nids(sbi, true, false))
2698		goto retry;
2699	return false;
2700}
2701
2702/*
2703 * f2fs_alloc_nid() should be called prior to this function.
2704 */
2705void f2fs_alloc_nid_done(struct f2fs_sb_info *sbi, nid_t nid)
2706{
2707	struct f2fs_nm_info *nm_i = NM_I(sbi);
2708	struct free_nid *i;
2709
2710	spin_lock(&nm_i->nid_list_lock);
2711	i = __lookup_free_nid_list(nm_i, nid);
2712	f2fs_bug_on(sbi, !i);
2713	__remove_free_nid(sbi, i, PREALLOC_NID);
2714	spin_unlock(&nm_i->nid_list_lock);
2715
2716	kmem_cache_free(free_nid_slab, i);
2717}
2718
2719/*
2720 * f2fs_alloc_nid() should be called prior to this function.
2721 */
2722void f2fs_alloc_nid_failed(struct f2fs_sb_info *sbi, nid_t nid)
2723{
2724	struct f2fs_nm_info *nm_i = NM_I(sbi);
2725	struct free_nid *i;
2726	bool need_free = false;
2727
2728	if (!nid)
2729		return;
2730
2731	spin_lock(&nm_i->nid_list_lock);
2732	i = __lookup_free_nid_list(nm_i, nid);
2733	f2fs_bug_on(sbi, !i);
2734
2735	if (!f2fs_available_free_memory(sbi, FREE_NIDS)) {
2736		__remove_free_nid(sbi, i, PREALLOC_NID);
2737		need_free = true;
2738	} else {
2739		__move_free_nid(sbi, i, PREALLOC_NID, FREE_NID);
2740	}
2741
2742	nm_i->available_nids++;
2743
2744	update_free_nid_bitmap(sbi, nid, true, false);
2745
2746	spin_unlock(&nm_i->nid_list_lock);
2747
2748	if (need_free)
2749		kmem_cache_free(free_nid_slab, i);
2750}
2751
2752int f2fs_try_to_free_nids(struct f2fs_sb_info *sbi, int nr_shrink)
2753{
2754	struct f2fs_nm_info *nm_i = NM_I(sbi);
2755	int nr = nr_shrink;
2756
2757	if (nm_i->nid_cnt[FREE_NID] <= MAX_FREE_NIDS)
2758		return 0;
2759
2760	if (!mutex_trylock(&nm_i->build_lock))
2761		return 0;
2762
2763	while (nr_shrink && nm_i->nid_cnt[FREE_NID] > MAX_FREE_NIDS) {
2764		struct free_nid *i, *next;
2765		unsigned int batch = SHRINK_NID_BATCH_SIZE;
2766
2767		spin_lock(&nm_i->nid_list_lock);
2768		list_for_each_entry_safe(i, next, &nm_i->free_nid_list, list) {
2769			if (!nr_shrink || !batch ||
2770				nm_i->nid_cnt[FREE_NID] <= MAX_FREE_NIDS)
2771				break;
2772			__remove_free_nid(sbi, i, FREE_NID);
2773			kmem_cache_free(free_nid_slab, i);
2774			nr_shrink--;
2775			batch--;
2776		}
2777		spin_unlock(&nm_i->nid_list_lock);
2778	}
2779
2780	mutex_unlock(&nm_i->build_lock);
2781
2782	return nr - nr_shrink;
2783}
2784
2785int f2fs_recover_inline_xattr(struct inode *inode, struct folio *folio)
2786{
2787	void *src_addr, *dst_addr;
2788	size_t inline_size;
2789	struct folio *ifolio;
2790	struct f2fs_inode *ri;
2791
2792	ifolio = f2fs_get_inode_folio(F2FS_I_SB(inode), inode->i_ino);
2793	if (IS_ERR(ifolio))
2794		return PTR_ERR(ifolio);
2795
2796	ri = F2FS_INODE(folio);
2797	if (ri->i_inline & F2FS_INLINE_XATTR) {
2798		if (!f2fs_has_inline_xattr(inode)) {
2799			set_inode_flag(inode, FI_INLINE_XATTR);
2800			stat_inc_inline_xattr(inode);
2801		}
2802	} else {
2803		if (f2fs_has_inline_xattr(inode)) {
2804			stat_dec_inline_xattr(inode);
2805			clear_inode_flag(inode, FI_INLINE_XATTR);
2806		}
2807		goto update_inode;
2808	}
2809
2810	dst_addr = inline_xattr_addr(inode, ifolio);
2811	src_addr = inline_xattr_addr(inode, folio);
2812	inline_size = inline_xattr_size(inode);
2813
2814	f2fs_folio_wait_writeback(ifolio, NODE, true, true);
2815	memcpy(dst_addr, src_addr, inline_size);
2816update_inode:
2817	f2fs_update_inode(inode, ifolio);
2818	f2fs_folio_put(ifolio, true);
2819	return 0;
2820}
2821
2822int f2fs_recover_xattr_data(struct inode *inode, struct folio *folio)
2823{
2824	struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
2825	nid_t prev_xnid = F2FS_I(inode)->i_xattr_nid;
2826	nid_t new_xnid;
2827	struct dnode_of_data dn;
2828	struct node_info ni;
2829	struct folio *xfolio;
2830	int err;
2831
2832	if (!prev_xnid)
2833		goto recover_xnid;
2834
2835	/* 1: invalidate the previous xattr nid */
2836	err = f2fs_get_node_info(sbi, prev_xnid, &ni, false);
2837	if (err)
2838		return err;
2839
2840	f2fs_invalidate_blocks(sbi, ni.blk_addr, 1);
2841	dec_valid_node_count(sbi, inode, false);
2842	set_node_addr(sbi, &ni, NULL_ADDR, false);
2843
2844recover_xnid:
2845	/* 2: update xattr nid in inode */
2846	if (!f2fs_alloc_nid(sbi, &new_xnid))
2847		return -ENOSPC;
2848
2849	set_new_dnode(&dn, inode, NULL, NULL, new_xnid);
2850	xfolio = f2fs_new_node_folio(&dn, XATTR_NODE_OFFSET);
2851	if (IS_ERR(xfolio)) {
2852		f2fs_alloc_nid_failed(sbi, new_xnid);
2853		return PTR_ERR(xfolio);
2854	}
2855
2856	f2fs_alloc_nid_done(sbi, new_xnid);
2857	f2fs_update_inode_page(inode);
2858
2859	/* 3: update and set xattr node page dirty */
2860	if (folio) {
2861		memcpy(F2FS_NODE(xfolio), F2FS_NODE(folio),
2862				VALID_XATTR_BLOCK_SIZE);
2863		folio_mark_dirty(xfolio);
2864	}
2865	f2fs_folio_put(xfolio, true);
2866
2867	return 0;
2868}
2869
2870int f2fs_recover_inode_page(struct f2fs_sb_info *sbi, struct folio *folio)
2871{
2872	struct f2fs_inode *src, *dst;
2873	nid_t ino = ino_of_node(folio);
2874	struct node_info old_ni, new_ni;
2875	struct folio *ifolio;
2876	int err;
2877
2878	err = f2fs_get_node_info(sbi, ino, &old_ni, false);
2879	if (err)
2880		return err;
2881
2882	if (unlikely(old_ni.blk_addr != NULL_ADDR))
2883		return -EINVAL;
2884retry:
2885	ifolio = f2fs_grab_cache_folio(NODE_MAPPING(sbi), ino, false);
2886	if (IS_ERR(ifolio)) {
2887		memalloc_retry_wait(GFP_NOFS);
2888		goto retry;
2889	}
2890
2891	/* Should not use this inode from free nid list */
2892	remove_free_nid(sbi, ino);
2893
2894	if (!folio_test_uptodate(ifolio))
2895		folio_mark_uptodate(ifolio);
2896	fill_node_footer(ifolio, ino, ino, 0, true);
2897	set_cold_node(ifolio, false);
2898
2899	src = F2FS_INODE(folio);
2900	dst = F2FS_INODE(ifolio);
2901
2902	memcpy(dst, src, offsetof(struct f2fs_inode, i_ext));
2903	dst->i_size = 0;
2904	dst->i_blocks = cpu_to_le64(1);
2905	dst->i_links = cpu_to_le32(1);
2906	dst->i_xattr_nid = 0;
2907	dst->i_inline = src->i_inline & (F2FS_INLINE_XATTR | F2FS_EXTRA_ATTR);
2908	if (dst->i_inline & F2FS_EXTRA_ATTR) {
2909		dst->i_extra_isize = src->i_extra_isize;
2910
2911		if (f2fs_sb_has_flexible_inline_xattr(sbi) &&
2912			F2FS_FITS_IN_INODE(src, le16_to_cpu(src->i_extra_isize),
2913							i_inline_xattr_size))
2914			dst->i_inline_xattr_size = src->i_inline_xattr_size;
2915
2916		if (f2fs_sb_has_project_quota(sbi) &&
2917			F2FS_FITS_IN_INODE(src, le16_to_cpu(src->i_extra_isize),
2918								i_projid))
2919			dst->i_projid = src->i_projid;
2920
2921		if (f2fs_sb_has_inode_crtime(sbi) &&
2922			F2FS_FITS_IN_INODE(src, le16_to_cpu(src->i_extra_isize),
2923							i_crtime_nsec)) {
2924			dst->i_crtime = src->i_crtime;
2925			dst->i_crtime_nsec = src->i_crtime_nsec;
2926		}
2927	}
2928
2929	new_ni = old_ni;
2930	new_ni.ino = ino;
2931
2932	if (unlikely(inc_valid_node_count(sbi, NULL, true)))
2933		WARN_ON(1);
2934	set_node_addr(sbi, &new_ni, NEW_ADDR, false);
2935	inc_valid_inode_count(sbi);
2936	folio_mark_dirty(ifolio);
2937	f2fs_folio_put(ifolio, true);
2938	return 0;
2939}
2940
2941int f2fs_restore_node_summary(struct f2fs_sb_info *sbi,
2942			unsigned int segno, struct f2fs_summary_block *sum)
2943{
2944	struct f2fs_node *rn;
2945	struct f2fs_summary *sum_entry;
2946	block_t addr;
2947	int i, idx, last_offset, nrpages;
2948
2949	/* scan the node segment */
2950	last_offset = BLKS_PER_SEG(sbi);
2951	addr = START_BLOCK(sbi, segno);
2952	sum_entry = sum_entries(sum);
2953
2954	for (i = 0; i < last_offset; i += nrpages, addr += nrpages) {
2955		nrpages = bio_max_segs(last_offset - i);
2956
2957		/* readahead node pages */
2958		f2fs_ra_meta_pages(sbi, addr, nrpages, META_POR, true);
2959
2960		for (idx = addr; idx < addr + nrpages; idx++) {
2961			struct folio *folio = f2fs_get_tmp_folio(sbi, idx);
2962
2963			if (IS_ERR(folio))
2964				return PTR_ERR(folio);
2965
2966			rn = F2FS_NODE(folio);
2967			sum_entry->nid = rn->footer.nid;
2968			sum_entry->version = 0;
2969			sum_entry->ofs_in_node = 0;
2970			sum_entry++;
2971			f2fs_folio_put(folio, true);
2972		}
2973
2974		invalidate_mapping_pages(META_MAPPING(sbi), addr,
2975							addr + nrpages);
2976	}
2977	return 0;
2978}
2979
2980static void remove_nats_in_journal(struct f2fs_sb_info *sbi)
2981{
2982	struct f2fs_nm_info *nm_i = NM_I(sbi);
2983	struct curseg_info *curseg = CURSEG_I(sbi, CURSEG_HOT_DATA);
2984	struct f2fs_journal *journal = curseg->journal;
2985	int i;
2986	bool init_dirty;
2987
2988	down_write(&curseg->journal_rwsem);
2989	for (i = 0; i < nats_in_cursum(journal); i++) {
2990		struct nat_entry *ne;
2991		struct f2fs_nat_entry raw_ne;
2992		nid_t nid = le32_to_cpu(nid_in_journal(journal, i));
2993
2994		if (f2fs_check_nid_range(sbi, nid))
2995			continue;
2996
2997		init_dirty = false;
2998
2999		raw_ne = nat_in_journal(journal, i);
3000
3001		ne = __lookup_nat_cache(nm_i, nid, true);
3002		if (!ne) {
3003			init_dirty = true;
3004			ne = __alloc_nat_entry(sbi, nid, true);
3005			__init_nat_entry(nm_i, ne, &raw_ne, true, true);
3006		}
3007
3008		/*
3009		 * if a free nat in journal has not been used after last
3010		 * checkpoint, we should remove it from available nids,
3011		 * since later we will add it again.
3012		 */
3013		if (!get_nat_flag(ne, IS_DIRTY) &&
3014				le32_to_cpu(raw_ne.block_addr) == NULL_ADDR) {
3015			spin_lock(&nm_i->nid_list_lock);
3016			nm_i->available_nids--;
3017			spin_unlock(&nm_i->nid_list_lock);
3018		}
3019
3020		__set_nat_cache_dirty(nm_i, ne, init_dirty);
3021	}
3022	update_nats_in_cursum(journal, -i);
3023	up_write(&curseg->journal_rwsem);
3024}
3025
3026static void __adjust_nat_entry_set(struct nat_entry_set *nes,
3027						struct list_head *head, int max)
3028{
3029	struct nat_entry_set *cur;
3030
3031	if (nes->entry_cnt >= max)
3032		goto add_out;
3033
3034	list_for_each_entry(cur, head, set_list) {
3035		if (cur->entry_cnt >= nes->entry_cnt) {
3036			list_add(&nes->set_list, cur->set_list.prev);
3037			return;
3038		}
3039	}
3040add_out:
3041	list_add_tail(&nes->set_list, head);
3042}
3043
3044static void __update_nat_bits(struct f2fs_sb_info *sbi, nid_t start_nid,
3045		const struct f2fs_nat_block *nat_blk)
3046{
3047	struct f2fs_nm_info *nm_i = NM_I(sbi);
3048	unsigned int nat_index = start_nid / NAT_ENTRY_PER_BLOCK;
3049	int valid = 0;
3050	int i = 0;
3051
3052	if (!enabled_nat_bits(sbi, NULL))
3053		return;
3054
3055	if (nat_index == 0) {
3056		valid = 1;
3057		i = 1;
3058	}
3059	for (; i < NAT_ENTRY_PER_BLOCK; i++) {
3060		if (le32_to_cpu(nat_blk->entries[i].block_addr) != NULL_ADDR)
3061			valid++;
3062	}
3063	if (valid == 0) {
3064		__set_bit_le(nat_index, nm_i->empty_nat_bits);
3065		__clear_bit_le(nat_index, nm_i->full_nat_bits);
3066		return;
3067	}
3068
3069	__clear_bit_le(nat_index, nm_i->empty_nat_bits);
3070	if (valid == NAT_ENTRY_PER_BLOCK)
3071		__set_bit_le(nat_index, nm_i->full_nat_bits);
3072	else
3073		__clear_bit_le(nat_index, nm_i->full_nat_bits);
3074}
3075
3076static int __flush_nat_entry_set(struct f2fs_sb_info *sbi,
3077		struct nat_entry_set *set, struct cp_control *cpc)
3078{
3079	struct curseg_info *curseg = CURSEG_I(sbi, CURSEG_HOT_DATA);
3080	struct f2fs_journal *journal = curseg->journal;
3081	nid_t start_nid = set->set * NAT_ENTRY_PER_BLOCK;
3082	bool to_journal = true;
3083	struct f2fs_nat_block *nat_blk;
3084	struct nat_entry *ne, *cur;
3085	struct folio *folio = NULL;
3086
3087	/*
3088	 * there are two steps to flush nat entries:
3089	 * #1, flush nat entries to journal in current hot data summary block.
3090	 * #2, flush nat entries to nat page.
3091	 */
3092	if (enabled_nat_bits(sbi, cpc) ||
3093		!__has_cursum_space(sbi, journal, set->entry_cnt, NAT_JOURNAL))
3094		to_journal = false;
3095
3096	if (to_journal) {
3097		down_write(&curseg->journal_rwsem);
3098	} else {
3099		folio = get_next_nat_folio(sbi, start_nid);
3100		if (IS_ERR(folio))
3101			return PTR_ERR(folio);
3102
3103		nat_blk = folio_address(folio);
3104		f2fs_bug_on(sbi, !nat_blk);
3105	}
3106
3107	/* flush dirty nats in nat entry set */
3108	list_for_each_entry_safe(ne, cur, &set->entry_list, list) {
3109		struct f2fs_nat_entry *raw_ne;
3110		nid_t nid = nat_get_nid(ne);
3111		int offset;
3112
3113		f2fs_bug_on(sbi, nat_get_blkaddr(ne) == NEW_ADDR);
3114
3115		if (to_journal) {
3116			offset = f2fs_lookup_journal_in_cursum(sbi, journal,
3117							NAT_JOURNAL, nid, 1);
3118			f2fs_bug_on(sbi, offset < 0);
3119			raw_ne = &nat_in_journal(journal, offset);
3120			nid_in_journal(journal, offset) = cpu_to_le32(nid);
3121		} else {
3122			raw_ne = &nat_blk->entries[nid - start_nid];
3123		}
3124		raw_nat_from_node_info(raw_ne, &ne->ni);
3125		nat_reset_flag(ne);
3126		__clear_nat_cache_dirty(NM_I(sbi), set, ne);
3127		if (nat_get_blkaddr(ne) == NULL_ADDR) {
3128			add_free_nid(sbi, nid, false, true);
3129		} else {
3130			spin_lock(&NM_I(sbi)->nid_list_lock);
3131			update_free_nid_bitmap(sbi, nid, false, false);
3132			spin_unlock(&NM_I(sbi)->nid_list_lock);
3133		}
3134	}
3135
3136	if (to_journal) {
3137		up_write(&curseg->journal_rwsem);
3138	} else {
3139		__update_nat_bits(sbi, start_nid, nat_blk);
3140		f2fs_folio_put(folio, true);
3141	}
3142
3143	/* Allow dirty nats by node block allocation in write_begin */
3144	if (!set->entry_cnt) {
3145		radix_tree_delete(&NM_I(sbi)->nat_set_root, set->set);
3146		kmem_cache_free(nat_entry_set_slab, set);
3147	}
3148	return 0;
3149}
3150
3151/*
3152 * This function is called during the checkpointing process.
3153 */
3154int f2fs_flush_nat_entries(struct f2fs_sb_info *sbi, struct cp_control *cpc)
3155{
3156	struct f2fs_nm_info *nm_i = NM_I(sbi);
3157	struct curseg_info *curseg = CURSEG_I(sbi, CURSEG_HOT_DATA);
3158	struct f2fs_journal *journal = curseg->journal;
3159	struct nat_entry_set *setvec[NAT_VEC_SIZE];
3160	struct nat_entry_set *set, *tmp;
3161	unsigned int found;
3162	nid_t set_idx = 0;
3163	LIST_HEAD(sets);
3164	int err = 0;
3165
3166	/*
3167	 * during unmount, let's flush nat_bits before checking
3168	 * nat_cnt[DIRTY_NAT].
3169	 */
3170	if (enabled_nat_bits(sbi, cpc)) {
3171		f2fs_down_write(&nm_i->nat_tree_lock);
3172		remove_nats_in_journal(sbi);
3173		f2fs_up_write(&nm_i->nat_tree_lock);
3174	}
3175
3176	if (!nm_i->nat_cnt[DIRTY_NAT])
3177		return 0;
3178
3179	f2fs_down_write(&nm_i->nat_tree_lock);
3180
3181	/*
3182	 * if there are no enough space in journal to store dirty nat
3183	 * entries, remove all entries from journal and merge them
3184	 * into nat entry set.
3185	 */
3186	if (enabled_nat_bits(sbi, cpc) ||
3187		!__has_cursum_space(sbi, journal,
3188			nm_i->nat_cnt[DIRTY_NAT], NAT_JOURNAL))
3189		remove_nats_in_journal(sbi);
3190
3191	while ((found = __gang_lookup_nat_set(nm_i,
3192					set_idx, NAT_VEC_SIZE, setvec))) {
3193		unsigned idx;
3194
3195		set_idx = setvec[found - 1]->set + 1;
3196		for (idx = 0; idx < found; idx++)
3197			__adjust_nat_entry_set(setvec[idx], &sets,
3198					MAX_NAT_JENTRIES(sbi, journal));
3199	}
3200
3201	/* flush dirty nats in nat entry set */
3202	list_for_each_entry_safe(set, tmp, &sets, set_list) {
3203		err = __flush_nat_entry_set(sbi, set, cpc);
3204		if (err)
3205			break;
3206	}
3207
3208	f2fs_up_write(&nm_i->nat_tree_lock);
3209	/* Allow dirty nats by node block allocation in write_begin */
3210
3211	return err;
3212}
3213
3214static int __get_nat_bitmaps(struct f2fs_sb_info *sbi)
3215{
3216	struct f2fs_checkpoint *ckpt = F2FS_CKPT(sbi);
3217	struct f2fs_nm_info *nm_i = NM_I(sbi);
3218	unsigned int nat_bits_bytes = nm_i->nat_blocks / BITS_PER_BYTE;
3219	unsigned int i;
3220	__u64 cp_ver = cur_cp_version(ckpt);
3221	block_t nat_bits_addr;
3222
3223	if (!enabled_nat_bits(sbi, NULL))
3224		return 0;
3225
3226	nm_i->nat_bits_blocks = F2FS_BLK_ALIGN((nat_bits_bytes << 1) + 8);
3227	nm_i->nat_bits = f2fs_kvzalloc(sbi,
3228			F2FS_BLK_TO_BYTES(nm_i->nat_bits_blocks), GFP_KERNEL);
3229	if (!nm_i->nat_bits)
3230		return -ENOMEM;
3231
3232	nat_bits_addr = __start_cp_addr(sbi) + BLKS_PER_SEG(sbi) -
3233						nm_i->nat_bits_blocks;
3234	for (i = 0; i < nm_i->nat_bits_blocks; i++) {
3235		struct folio *folio;
3236
3237		folio = f2fs_get_meta_folio(sbi, nat_bits_addr++);
3238		if (IS_ERR(folio))
3239			return PTR_ERR(folio);
3240
3241		memcpy(nm_i->nat_bits + F2FS_BLK_TO_BYTES(i),
3242					folio_address(folio), F2FS_BLKSIZE);
3243		f2fs_folio_put(folio, true);
3244	}
3245
3246	cp_ver |= (cur_cp_crc(ckpt) << 32);
3247	if (cpu_to_le64(cp_ver) != *(__le64 *)nm_i->nat_bits) {
3248		disable_nat_bits(sbi, true);
3249		return 0;
3250	}
3251
3252	nm_i->full_nat_bits = nm_i->nat_bits + 8;
3253	nm_i->empty_nat_bits = nm_i->full_nat_bits + nat_bits_bytes;
3254
3255	f2fs_notice(sbi, "Found nat_bits in checkpoint");
3256	return 0;
3257}
3258
3259static inline void load_free_nid_bitmap(struct f2fs_sb_info *sbi)
3260{
3261	struct f2fs_nm_info *nm_i = NM_I(sbi);
3262	unsigned int i = 0;
3263	nid_t nid, last_nid;
3264
3265	if (!enabled_nat_bits(sbi, NULL))
3266		return;
3267
3268	for (i = 0; i < nm_i->nat_blocks; i++) {
3269		i = find_next_bit_le(nm_i->empty_nat_bits, nm_i->nat_blocks, i);
3270		if (i >= nm_i->nat_blocks)
3271			break;
3272
3273		__set_bit_le(i, nm_i->nat_block_bitmap);
3274
3275		nid = i * NAT_ENTRY_PER_BLOCK;
3276		last_nid = nid + NAT_ENTRY_PER_BLOCK;
3277
3278		spin_lock(&NM_I(sbi)->nid_list_lock);
3279		for (; nid < last_nid; nid++)
3280			update_free_nid_bitmap(sbi, nid, true, true);
3281		spin_unlock(&NM_I(sbi)->nid_list_lock);
3282	}
3283
3284	for (i = 0; i < nm_i->nat_blocks; i++) {
3285		i = find_next_bit_le(nm_i->full_nat_bits, nm_i->nat_blocks, i);
3286		if (i >= nm_i->nat_blocks)
3287			break;
3288
3289		__set_bit_le(i, nm_i->nat_block_bitmap);
3290	}
3291}
3292
3293static int init_node_manager(struct f2fs_sb_info *sbi)
3294{
3295	struct f2fs_super_block *sb_raw = F2FS_RAW_SUPER(sbi);
3296	struct f2fs_nm_info *nm_i = NM_I(sbi);
3297	unsigned char *version_bitmap;
3298	unsigned int nat_segs;
3299	int err;
3300
3301	nm_i->nat_blkaddr = le32_to_cpu(sb_raw->nat_blkaddr);
3302
3303	/* segment_count_nat includes pair segment so divide to 2. */
3304	nat_segs = le32_to_cpu(sb_raw->segment_count_nat) >> 1;
3305	nm_i->nat_blocks = nat_segs << le32_to_cpu(sb_raw->log_blocks_per_seg);
3306	nm_i->max_nid = NAT_ENTRY_PER_BLOCK * nm_i->nat_blocks;
3307
3308	/* not used nids: 0, node, meta, (and root counted as valid node) */
3309	nm_i->available_nids = nm_i->max_nid - sbi->total_valid_node_count -
3310						F2FS_RESERVED_NODE_NUM;
3311	nm_i->nid_cnt[FREE_NID] = 0;
3312	nm_i->nid_cnt[PREALLOC_NID] = 0;
3313	nm_i->ram_thresh = DEF_RAM_THRESHOLD;
3314	nm_i->ra_nid_pages = DEF_RA_NID_PAGES;
3315	nm_i->dirty_nats_ratio = DEF_DIRTY_NAT_RATIO_THRESHOLD;
3316	nm_i->max_rf_node_blocks = DEF_RF_NODE_BLOCKS;
3317
3318	INIT_RADIX_TREE(&nm_i->free_nid_root, GFP_ATOMIC);
3319	INIT_LIST_HEAD(&nm_i->free_nid_list);
3320	INIT_RADIX_TREE(&nm_i->nat_root, GFP_NOIO);
3321	INIT_RADIX_TREE(&nm_i->nat_set_root, GFP_NOIO);
3322	INIT_LIST_HEAD(&nm_i->nat_entries);
3323	spin_lock_init(&nm_i->nat_list_lock);
3324
3325	mutex_init(&nm_i->build_lock);
3326	spin_lock_init(&nm_i->nid_list_lock);
3327	init_f2fs_rwsem(&nm_i->nat_tree_lock);
3328
3329	nm_i->next_scan_nid = le32_to_cpu(sbi->ckpt->next_free_nid);
3330	nm_i->bitmap_size = __bitmap_size(sbi, NAT_BITMAP);
3331	version_bitmap = __bitmap_ptr(sbi, NAT_BITMAP);
3332	nm_i->nat_bitmap = kmemdup(version_bitmap, nm_i->bitmap_size,
3333					GFP_KERNEL);
3334	if (!nm_i->nat_bitmap)
3335		return -ENOMEM;
3336
3337	if (!test_opt(sbi, NAT_BITS))
3338		disable_nat_bits(sbi, true);
3339
3340	err = __get_nat_bitmaps(sbi);
3341	if (err)
3342		return err;
3343
3344#ifdef CONFIG_F2FS_CHECK_FS
3345	nm_i->nat_bitmap_mir = kmemdup(version_bitmap, nm_i->bitmap_size,
3346					GFP_KERNEL);
3347	if (!nm_i->nat_bitmap_mir)
3348		return -ENOMEM;
3349#endif
3350
3351	return 0;
3352}
3353
3354static int init_free_nid_cache(struct f2fs_sb_info *sbi)
3355{
3356	struct f2fs_nm_info *nm_i = NM_I(sbi);
3357	int i;
3358
3359	nm_i->free_nid_bitmap =
3360		f2fs_kvzalloc(sbi, array_size(sizeof(unsigned char *),
3361					      nm_i->nat_blocks),
3362			      GFP_KERNEL);
3363	if (!nm_i->free_nid_bitmap)
3364		return -ENOMEM;
3365
3366	for (i = 0; i < nm_i->nat_blocks; i++) {
3367		nm_i->free_nid_bitmap[i] = f2fs_kvzalloc(sbi,
3368			f2fs_bitmap_size(NAT_ENTRY_PER_BLOCK), GFP_KERNEL);
3369		if (!nm_i->free_nid_bitmap[i])
3370			return -ENOMEM;
3371	}
3372
3373	nm_i->nat_block_bitmap = f2fs_kvzalloc(sbi, nm_i->nat_blocks / 8,
3374								GFP_KERNEL);
3375	if (!nm_i->nat_block_bitmap)
3376		return -ENOMEM;
3377
3378	nm_i->free_nid_count =
3379		f2fs_kvzalloc(sbi, array_size(sizeof(unsigned short),
3380					      nm_i->nat_blocks),
3381			      GFP_KERNEL);
3382	if (!nm_i->free_nid_count)
3383		return -ENOMEM;
3384	return 0;
3385}
3386
3387int f2fs_build_node_manager(struct f2fs_sb_info *sbi)
3388{
3389	int err;
3390
3391	sbi->nm_info = f2fs_kzalloc(sbi, sizeof(struct f2fs_nm_info),
3392							GFP_KERNEL);
3393	if (!sbi->nm_info)
3394		return -ENOMEM;
3395
3396	err = init_node_manager(sbi);
3397	if (err)
3398		return err;
3399
3400	err = init_free_nid_cache(sbi);
3401	if (err)
3402		return err;
3403
3404	/* load free nid status from nat_bits table */
3405	load_free_nid_bitmap(sbi);
3406
3407	return f2fs_build_free_nids(sbi, true, true);
3408}
3409
3410void f2fs_destroy_node_manager(struct f2fs_sb_info *sbi)
3411{
3412	struct f2fs_nm_info *nm_i = NM_I(sbi);
3413	struct free_nid *i, *next_i;
3414	void *vec[NAT_VEC_SIZE];
3415	struct nat_entry **natvec = (struct nat_entry **)vec;
3416	struct nat_entry_set **setvec = (struct nat_entry_set **)vec;
3417	nid_t nid = 0;
3418	unsigned int found;
3419
3420	if (!nm_i)
3421		return;
3422
3423	/* destroy free nid list */
3424	spin_lock(&nm_i->nid_list_lock);
3425	list_for_each_entry_safe(i, next_i, &nm_i->free_nid_list, list) {
3426		__remove_free_nid(sbi, i, FREE_NID);
3427		spin_unlock(&nm_i->nid_list_lock);
3428		kmem_cache_free(free_nid_slab, i);
3429		spin_lock(&nm_i->nid_list_lock);
3430	}
3431	f2fs_bug_on(sbi, nm_i->nid_cnt[FREE_NID]);
3432	f2fs_bug_on(sbi, nm_i->nid_cnt[PREALLOC_NID]);
3433	f2fs_bug_on(sbi, !list_empty(&nm_i->free_nid_list));
3434	spin_unlock(&nm_i->nid_list_lock);
3435
3436	/* destroy nat cache */
3437	f2fs_down_write(&nm_i->nat_tree_lock);
3438	while ((found = __gang_lookup_nat_cache(nm_i,
3439					nid, NAT_VEC_SIZE, natvec))) {
3440		unsigned idx;
3441
3442		nid = nat_get_nid(natvec[found - 1]) + 1;
3443		for (idx = 0; idx < found; idx++) {
3444			spin_lock(&nm_i->nat_list_lock);
3445			list_del(&natvec[idx]->list);
3446			spin_unlock(&nm_i->nat_list_lock);
3447
3448			__del_from_nat_cache(nm_i, natvec[idx]);
3449		}
3450	}
3451	f2fs_bug_on(sbi, nm_i->nat_cnt[TOTAL_NAT]);
3452
3453	/* destroy nat set cache */
3454	nid = 0;
3455	memset(vec, 0, sizeof(void *) * NAT_VEC_SIZE);
3456	while ((found = __gang_lookup_nat_set(nm_i,
3457					nid, NAT_VEC_SIZE, setvec))) {
3458		unsigned idx;
3459
3460		nid = setvec[found - 1]->set + 1;
3461		for (idx = 0; idx < found; idx++) {
3462			/* entry_cnt is not zero, when cp_error was occurred */
3463			f2fs_bug_on(sbi, !list_empty(&setvec[idx]->entry_list));
3464			radix_tree_delete(&nm_i->nat_set_root, setvec[idx]->set);
3465			kmem_cache_free(nat_entry_set_slab, setvec[idx]);
3466		}
3467	}
3468	f2fs_up_write(&nm_i->nat_tree_lock);
3469
3470	kvfree(nm_i->nat_block_bitmap);
3471	if (nm_i->free_nid_bitmap) {
3472		int i;
3473
3474		for (i = 0; i < nm_i->nat_blocks; i++)
3475			kvfree(nm_i->free_nid_bitmap[i]);
3476		kvfree(nm_i->free_nid_bitmap);
3477	}
3478	kvfree(nm_i->free_nid_count);
3479
3480	kfree(nm_i->nat_bitmap);
3481	kvfree(nm_i->nat_bits);
3482#ifdef CONFIG_F2FS_CHECK_FS
3483	kfree(nm_i->nat_bitmap_mir);
3484#endif
3485	sbi->nm_info = NULL;
3486	kfree(nm_i);
3487}
3488
3489int __init f2fs_create_node_manager_caches(void)
3490{
3491	nat_entry_slab = f2fs_kmem_cache_create("f2fs_nat_entry",
3492			sizeof(struct nat_entry));
3493	if (!nat_entry_slab)
3494		goto fail;
3495
3496	free_nid_slab = f2fs_kmem_cache_create("f2fs_free_nid",
3497			sizeof(struct free_nid));
3498	if (!free_nid_slab)
3499		goto destroy_nat_entry;
3500
3501	nat_entry_set_slab = f2fs_kmem_cache_create("f2fs_nat_entry_set",
3502			sizeof(struct nat_entry_set));
3503	if (!nat_entry_set_slab)
3504		goto destroy_free_nid;
3505
3506	fsync_node_entry_slab = f2fs_kmem_cache_create("f2fs_fsync_node_entry",
3507			sizeof(struct fsync_node_entry));
3508	if (!fsync_node_entry_slab)
3509		goto destroy_nat_entry_set;
3510	return 0;
3511
3512destroy_nat_entry_set:
3513	kmem_cache_destroy(nat_entry_set_slab);
3514destroy_free_nid:
3515	kmem_cache_destroy(free_nid_slab);
3516destroy_nat_entry:
3517	kmem_cache_destroy(nat_entry_slab);
3518fail:
3519	return -ENOMEM;
3520}
3521
3522void f2fs_destroy_node_manager_caches(void)
3523{
3524	kmem_cache_destroy(fsync_node_entry_slab);
3525	kmem_cache_destroy(nat_entry_set_slab);
3526	kmem_cache_destroy(free_nid_slab);
3527	kmem_cache_destroy(nat_entry_slab);
3528}