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