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