node.c 59.0 KB
Newer Older
J
Jaegeuk Kim 已提交
1
/*
J
Jaegeuk Kim 已提交
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
 * fs/f2fs/node.c
 *
 * Copyright (c) 2012 Samsung Electronics Co., Ltd.
 *             http://www.samsung.com/
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License version 2 as
 * published by the Free Software Foundation.
 */
#include <linux/fs.h>
#include <linux/f2fs_fs.h>
#include <linux/mpage.h>
#include <linux/backing-dev.h>
#include <linux/blkdev.h>
#include <linux/pagevec.h>
#include <linux/swap.h>

#include "f2fs.h"
#include "node.h"
#include "segment.h"
J
Jaegeuk Kim 已提交
22
#include "trace.h"
23
#include <trace/events/f2fs.h>
J
Jaegeuk Kim 已提交
24

25 26
#define on_build_free_nids(nmi) mutex_is_locked(&nm_i->build_lock)

J
Jaegeuk Kim 已提交
27 28
static struct kmem_cache *nat_entry_slab;
static struct kmem_cache *free_nid_slab;
29
static struct kmem_cache *nat_entry_set_slab;
J
Jaegeuk Kim 已提交
30

31
bool available_free_memory(struct f2fs_sb_info *sbi, int type)
32
{
33
	struct f2fs_nm_info *nm_i = NM_I(sbi);
34
	struct sysinfo val;
35
	unsigned long avail_ram;
36
	unsigned long mem_size = 0;
37
	bool res = false;
38 39

	si_meminfo(&val);
40 41 42 43

	/* only uses low memory */
	avail_ram = val.totalram - val.totalhigh;

44 45 46
	/*
	 * give 25%, 25%, 50%, 50%, 50% memory for each components respectively
	 */
47
	if (type == FREE_NIDS) {
C
Chao Yu 已提交
48 49
		mem_size = (nm_i->nid_cnt[FREE_NID_LIST] *
				sizeof(struct free_nid)) >> PAGE_SHIFT;
50
		res = mem_size < ((avail_ram * nm_i->ram_thresh / 100) >> 2);
51
	} else if (type == NAT_ENTRIES) {
52
		mem_size = (nm_i->nat_cnt * sizeof(struct nat_entry)) >>
53
							PAGE_SHIFT;
54
		res = mem_size < ((avail_ram * nm_i->ram_thresh / 100) >> 2);
55 56
		if (excess_cached_nats(sbi))
			res = false;
57 58 59 60 61
	} else if (type == DIRTY_DENTS) {
		if (sbi->sb->s_bdi->wb.dirty_exceeded)
			return false;
		mem_size = get_pages(sbi, F2FS_DIRTY_DENTS);
		res = mem_size < ((avail_ram * nm_i->ram_thresh / 100) >> 1);
62 63 64 65
	} else if (type == INO_ENTRIES) {
		int i;

		for (i = 0; i <= UPDATE_INO; i++)
66
			mem_size += (sbi->im[i].ino_num *
67
				sizeof(struct ino_entry)) >> PAGE_SHIFT;
68
		res = mem_size < ((avail_ram * nm_i->ram_thresh / 100) >> 1);
69
	} else if (type == EXTENT_CACHE) {
70 71
		mem_size = (atomic_read(&sbi->total_ext_tree) *
				sizeof(struct extent_tree) +
72
				atomic_read(&sbi->total_ext_node) *
73
				sizeof(struct extent_node)) >> PAGE_SHIFT;
74
		res = mem_size < ((avail_ram * nm_i->ram_thresh / 100) >> 1);
75
	} else {
76 77
		if (!sbi->sb->s_bdi->wb.dirty_exceeded)
			return true;
78 79
	}
	return res;
80 81
}

J
Jaegeuk Kim 已提交
82 83 84 85 86 87 88 89 90 91 92 93 94
static void clear_node_page_dirty(struct page *page)
{
	struct address_space *mapping = page->mapping;
	unsigned int long flags;

	if (PageDirty(page)) {
		spin_lock_irqsave(&mapping->tree_lock, flags);
		radix_tree_tag_clear(&mapping->page_tree,
				page_index(page),
				PAGECACHE_TAG_DIRTY);
		spin_unlock_irqrestore(&mapping->tree_lock, flags);

		clear_page_dirty_for_io(page);
95
		dec_page_count(F2FS_M_SB(mapping), F2FS_DIRTY_NODES);
J
Jaegeuk Kim 已提交
96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121
	}
	ClearPageUptodate(page);
}

static struct page *get_current_nat_page(struct f2fs_sb_info *sbi, nid_t nid)
{
	pgoff_t index = current_nat_addr(sbi, nid);
	return get_meta_page(sbi, index);
}

static struct page *get_next_nat_page(struct f2fs_sb_info *sbi, nid_t nid)
{
	struct page *src_page;
	struct page *dst_page;
	pgoff_t src_off;
	pgoff_t dst_off;
	void *src_addr;
	void *dst_addr;
	struct f2fs_nm_info *nm_i = NM_I(sbi);

	src_off = current_nat_addr(sbi, nid);
	dst_off = next_nat_addr(sbi, src_off);

	/* get current nat block page with lock */
	src_page = get_meta_page(sbi, src_off);
	dst_page = grab_meta_page(sbi, dst_off);
122
	f2fs_bug_on(sbi, PageDirty(src_page));
J
Jaegeuk Kim 已提交
123 124 125

	src_addr = page_address(src_page);
	dst_addr = page_address(dst_page);
126
	memcpy(dst_addr, src_addr, PAGE_SIZE);
J
Jaegeuk Kim 已提交
127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153
	set_page_dirty(dst_page);
	f2fs_put_page(src_page, 1);

	set_to_next_nat(nm_i, nid);

	return dst_page;
}

static struct nat_entry *__lookup_nat_cache(struct f2fs_nm_info *nm_i, nid_t n)
{
	return radix_tree_lookup(&nm_i->nat_root, n);
}

static unsigned int __gang_lookup_nat_cache(struct f2fs_nm_info *nm_i,
		nid_t start, unsigned int nr, struct nat_entry **ep)
{
	return radix_tree_gang_lookup(&nm_i->nat_root, (void **)ep, start, nr);
}

static void __del_from_nat_cache(struct f2fs_nm_info *nm_i, struct nat_entry *e)
{
	list_del(&e->list);
	radix_tree_delete(&nm_i->nat_root, nat_get_nid(e));
	nm_i->nat_cnt--;
	kmem_cache_free(nat_entry_slab, e);
}

154 155 156 157 158 159 160 161
static void __set_nat_cache_dirty(struct f2fs_nm_info *nm_i,
						struct nat_entry *ne)
{
	nid_t set = NAT_BLOCK_OFFSET(ne->ni.nid);
	struct nat_entry_set *head;

	if (get_nat_flag(ne, IS_DIRTY))
		return;
162

163 164
	head = radix_tree_lookup(&nm_i->nat_set_root, set);
	if (!head) {
165
		head = f2fs_kmem_cache_alloc(nat_entry_set_slab, GFP_NOFS);
166 167 168 169 170

		INIT_LIST_HEAD(&head->entry_list);
		INIT_LIST_HEAD(&head->set_list);
		head->set = set;
		head->entry_cnt = 0;
171
		f2fs_radix_tree_insert(&nm_i->nat_set_root, set, head);
172 173 174 175 176 177 178 179 180 181
	}
	list_move_tail(&ne->list, &head->entry_list);
	nm_i->dirty_nat_cnt++;
	head->entry_cnt++;
	set_nat_flag(ne, IS_DIRTY, true);
}

static void __clear_nat_cache_dirty(struct f2fs_nm_info *nm_i,
						struct nat_entry *ne)
{
182
	nid_t set = NAT_BLOCK_OFFSET(ne->ni.nid);
183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200
	struct nat_entry_set *head;

	head = radix_tree_lookup(&nm_i->nat_set_root, set);
	if (head) {
		list_move_tail(&ne->list, &nm_i->nat_entries);
		set_nat_flag(ne, IS_DIRTY, false);
		head->entry_cnt--;
		nm_i->dirty_nat_cnt--;
	}
}

static unsigned int __gang_lookup_nat_set(struct f2fs_nm_info *nm_i,
		nid_t start, unsigned int nr, struct nat_entry_set **ep)
{
	return radix_tree_gang_lookup(&nm_i->nat_set_root, (void **)ep,
							start, nr);
}

J
Jaegeuk Kim 已提交
201
int need_dentry_mark(struct f2fs_sb_info *sbi, nid_t nid)
J
Jaegeuk Kim 已提交
202 203 204
{
	struct f2fs_nm_info *nm_i = NM_I(sbi);
	struct nat_entry *e;
J
Jaegeuk Kim 已提交
205
	bool need = false;
J
Jaegeuk Kim 已提交
206

207
	down_read(&nm_i->nat_tree_lock);
J
Jaegeuk Kim 已提交
208
	e = __lookup_nat_cache(nm_i, nid);
J
Jaegeuk Kim 已提交
209 210 211 212 213
	if (e) {
		if (!get_nat_flag(e, IS_CHECKPOINTED) &&
				!get_nat_flag(e, HAS_FSYNCED_INODE))
			need = true;
	}
214
	up_read(&nm_i->nat_tree_lock);
J
Jaegeuk Kim 已提交
215
	return need;
J
Jaegeuk Kim 已提交
216 217
}

J
Jaegeuk Kim 已提交
218
bool is_checkpointed_node(struct f2fs_sb_info *sbi, nid_t nid)
219 220 221
{
	struct f2fs_nm_info *nm_i = NM_I(sbi);
	struct nat_entry *e;
J
Jaegeuk Kim 已提交
222
	bool is_cp = true;
223

224
	down_read(&nm_i->nat_tree_lock);
J
Jaegeuk Kim 已提交
225 226 227
	e = __lookup_nat_cache(nm_i, nid);
	if (e && !get_nat_flag(e, IS_CHECKPOINTED))
		is_cp = false;
228
	up_read(&nm_i->nat_tree_lock);
J
Jaegeuk Kim 已提交
229
	return is_cp;
230 231
}

232
bool need_inode_block_update(struct f2fs_sb_info *sbi, nid_t ino)
233 234 235
{
	struct f2fs_nm_info *nm_i = NM_I(sbi);
	struct nat_entry *e;
236
	bool need_update = true;
237

238
	down_read(&nm_i->nat_tree_lock);
239 240 241 242 243
	e = __lookup_nat_cache(nm_i, ino);
	if (e && get_nat_flag(e, HAS_LAST_FSYNC) &&
			(get_nat_flag(e, IS_CHECKPOINTED) ||
			 get_nat_flag(e, HAS_FSYNCED_INODE)))
		need_update = false;
244
	up_read(&nm_i->nat_tree_lock);
245
	return need_update;
246 247
}

248 249
static struct nat_entry *grab_nat_entry(struct f2fs_nm_info *nm_i, nid_t nid,
								bool no_fail)
J
Jaegeuk Kim 已提交
250 251 252
{
	struct nat_entry *new;

253 254 255 256 257 258 259 260 261 262 263 264 265
	if (no_fail) {
		new = f2fs_kmem_cache_alloc(nat_entry_slab, GFP_NOFS);
		f2fs_radix_tree_insert(&nm_i->nat_root, nid, new);
	} else {
		new = kmem_cache_alloc(nat_entry_slab, GFP_NOFS);
		if (!new)
			return NULL;
		if (radix_tree_insert(&nm_i->nat_root, nid, new)) {
			kmem_cache_free(nat_entry_slab, new);
			return NULL;
		}
	}

J
Jaegeuk Kim 已提交
266 267
	memset(new, 0, sizeof(struct nat_entry));
	nat_set_nid(new, nid);
268
	nat_reset_flag(new);
J
Jaegeuk Kim 已提交
269 270 271 272 273
	list_add_tail(&new->list, &nm_i->nat_entries);
	nm_i->nat_cnt++;
	return new;
}

274
static void cache_nat_entry(struct f2fs_sb_info *sbi, nid_t nid,
J
Jaegeuk Kim 已提交
275 276
						struct f2fs_nat_entry *ne)
{
277
	struct f2fs_nm_info *nm_i = NM_I(sbi);
J
Jaegeuk Kim 已提交
278
	struct nat_entry *e;
279

J
Jaegeuk Kim 已提交
280 281
	e = __lookup_nat_cache(nm_i, nid);
	if (!e) {
282 283 284
		e = grab_nat_entry(nm_i, nid, false);
		if (e)
			node_info_from_raw_nat(&e->ni, ne);
285
	} else {
E
Eric Biggers 已提交
286 287 288
		f2fs_bug_on(sbi, nat_get_ino(e) != le32_to_cpu(ne->ino) ||
				nat_get_blkaddr(e) !=
					le32_to_cpu(ne->block_addr) ||
289
				nat_get_version(e) != ne->version);
J
Jaegeuk Kim 已提交
290 291 292 293
	}
}

static void set_node_addr(struct f2fs_sb_info *sbi, struct node_info *ni,
294
			block_t new_blkaddr, bool fsync_done)
J
Jaegeuk Kim 已提交
295 296 297
{
	struct f2fs_nm_info *nm_i = NM_I(sbi);
	struct nat_entry *e;
298

299
	down_write(&nm_i->nat_tree_lock);
J
Jaegeuk Kim 已提交
300 301
	e = __lookup_nat_cache(nm_i, ni->nid);
	if (!e) {
302
		e = grab_nat_entry(nm_i, ni->nid, true);
303
		copy_node_info(&e->ni, ni);
304
		f2fs_bug_on(sbi, ni->blk_addr == NEW_ADDR);
J
Jaegeuk Kim 已提交
305 306 307 308 309 310
	} else if (new_blkaddr == NEW_ADDR) {
		/*
		 * when nid is reallocated,
		 * previous nat entry can be remained in nat cache.
		 * So, reinitialize it with new information.
		 */
311
		copy_node_info(&e->ni, ni);
312
		f2fs_bug_on(sbi, ni->blk_addr != NULL_ADDR);
J
Jaegeuk Kim 已提交
313 314 315
	}

	/* sanity check */
316 317
	f2fs_bug_on(sbi, nat_get_blkaddr(e) != ni->blk_addr);
	f2fs_bug_on(sbi, nat_get_blkaddr(e) == NULL_ADDR &&
J
Jaegeuk Kim 已提交
318
			new_blkaddr == NULL_ADDR);
319
	f2fs_bug_on(sbi, nat_get_blkaddr(e) == NEW_ADDR &&
J
Jaegeuk Kim 已提交
320
			new_blkaddr == NEW_ADDR);
321
	f2fs_bug_on(sbi, nat_get_blkaddr(e) != NEW_ADDR &&
J
Jaegeuk Kim 已提交
322 323 324
			nat_get_blkaddr(e) != NULL_ADDR &&
			new_blkaddr == NEW_ADDR);

A
arter97 已提交
325
	/* increment version no as node is removed */
J
Jaegeuk Kim 已提交
326 327 328
	if (nat_get_blkaddr(e) != NEW_ADDR && new_blkaddr == NULL_ADDR) {
		unsigned char version = nat_get_version(e);
		nat_set_version(e, inc_node_version(version));
J
Jaegeuk Kim 已提交
329 330 331 332

		/* in order to reuse the nid */
		if (nm_i->next_scan_nid > ni->nid)
			nm_i->next_scan_nid = ni->nid;
J
Jaegeuk Kim 已提交
333 334 335 336
	}

	/* change address */
	nat_set_blkaddr(e, new_blkaddr);
337 338
	if (new_blkaddr == NEW_ADDR || new_blkaddr == NULL_ADDR)
		set_nat_flag(e, IS_CHECKPOINTED, false);
J
Jaegeuk Kim 已提交
339
	__set_nat_cache_dirty(nm_i, e);
340 341

	/* update fsync_mark if its inode nat entry is still alive */
342 343
	if (ni->nid != ni->ino)
		e = __lookup_nat_cache(nm_i, ni->ino);
344 345 346 347 348
	if (e) {
		if (fsync_done && ni->nid == ni->ino)
			set_nat_flag(e, HAS_FSYNCED_INODE, true);
		set_nat_flag(e, HAS_LAST_FSYNC, fsync_done);
	}
349
	up_write(&nm_i->nat_tree_lock);
J
Jaegeuk Kim 已提交
350 351
}

352
int try_to_free_nats(struct f2fs_sb_info *sbi, int nr_shrink)
J
Jaegeuk Kim 已提交
353 354
{
	struct f2fs_nm_info *nm_i = NM_I(sbi);
J
Jaegeuk Kim 已提交
355
	int nr = nr_shrink;
J
Jaegeuk Kim 已提交
356

357 358
	if (!down_write_trylock(&nm_i->nat_tree_lock))
		return 0;
J
Jaegeuk Kim 已提交
359 360 361 362 363 364 365 366

	while (nr_shrink && !list_empty(&nm_i->nat_entries)) {
		struct nat_entry *ne;
		ne = list_first_entry(&nm_i->nat_entries,
					struct nat_entry, list);
		__del_from_nat_cache(nm_i, ne);
		nr_shrink--;
	}
367
	up_write(&nm_i->nat_tree_lock);
J
Jaegeuk Kim 已提交
368
	return nr - nr_shrink;
J
Jaegeuk Kim 已提交
369 370
}

J
Jaegeuk Kim 已提交
371
/*
A
arter97 已提交
372
 * This function always returns success
J
Jaegeuk Kim 已提交
373 374 375 376 377
 */
void get_node_info(struct f2fs_sb_info *sbi, nid_t nid, struct node_info *ni)
{
	struct f2fs_nm_info *nm_i = NM_I(sbi);
	struct curseg_info *curseg = CURSEG_I(sbi, CURSEG_HOT_DATA);
378
	struct f2fs_journal *journal = curseg->journal;
J
Jaegeuk Kim 已提交
379 380 381 382 383 384 385 386 387 388
	nid_t start_nid = START_NID(nid);
	struct f2fs_nat_block *nat_blk;
	struct page *page = NULL;
	struct f2fs_nat_entry ne;
	struct nat_entry *e;
	int i;

	ni->nid = nid;

	/* Check nat cache */
389
	down_read(&nm_i->nat_tree_lock);
J
Jaegeuk Kim 已提交
390 391 392 393 394
	e = __lookup_nat_cache(nm_i, nid);
	if (e) {
		ni->ino = nat_get_ino(e);
		ni->blk_addr = nat_get_blkaddr(e);
		ni->version = nat_get_version(e);
395
		up_read(&nm_i->nat_tree_lock);
J
Jaegeuk Kim 已提交
396
		return;
397
	}
J
Jaegeuk Kim 已提交
398

399 400
	memset(&ne, 0, sizeof(struct f2fs_nat_entry));

J
Jaegeuk Kim 已提交
401
	/* Check current segment summary */
402
	down_read(&curseg->journal_rwsem);
403
	i = lookup_journal_in_cursum(journal, NAT_JOURNAL, nid, 0);
J
Jaegeuk Kim 已提交
404
	if (i >= 0) {
405
		ne = nat_in_journal(journal, i);
J
Jaegeuk Kim 已提交
406 407
		node_info_from_raw_nat(ni, &ne);
	}
408
	up_read(&curseg->journal_rwsem);
J
Jaegeuk Kim 已提交
409 410 411 412 413 414 415 416 417 418
	if (i >= 0)
		goto cache;

	/* Fill node_info from nat page */
	page = get_current_nat_page(sbi, start_nid);
	nat_blk = (struct f2fs_nat_block *)page_address(page);
	ne = nat_blk->entries[nid - start_nid];
	node_info_from_raw_nat(ni, &ne);
	f2fs_put_page(page, 1);
cache:
419
	up_read(&nm_i->nat_tree_lock);
J
Jaegeuk Kim 已提交
420
	/* cache nat entry */
421
	down_write(&nm_i->nat_tree_lock);
422
	cache_nat_entry(sbi, nid, &ne);
423
	up_write(&nm_i->nat_tree_lock);
J
Jaegeuk Kim 已提交
424 425
}

426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448
/*
 * readahead MAX_RA_NODE number of node pages.
 */
static void ra_node_pages(struct page *parent, int start, int n)
{
	struct f2fs_sb_info *sbi = F2FS_P_SB(parent);
	struct blk_plug plug;
	int i, end;
	nid_t nid;

	blk_start_plug(&plug);

	/* Then, try readahead for siblings of the desired node */
	end = start + n;
	end = min(end, NIDS_PER_BLOCK);
	for (i = start; i < end; i++) {
		nid = get_nid(parent, i, false);
		ra_node_page(sbi, nid);
	}

	blk_finish_plug(&plug);
}

449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479
pgoff_t get_next_page_offset(struct dnode_of_data *dn, pgoff_t pgofs)
{
	const long direct_index = ADDRS_PER_INODE(dn->inode);
	const long direct_blks = ADDRS_PER_BLOCK;
	const long indirect_blks = ADDRS_PER_BLOCK * NIDS_PER_BLOCK;
	unsigned int skipped_unit = ADDRS_PER_BLOCK;
	int cur_level = dn->cur_level;
	int max_level = dn->max_level;
	pgoff_t base = 0;

	if (!dn->max_level)
		return pgofs + 1;

	while (max_level-- > cur_level)
		skipped_unit *= NIDS_PER_BLOCK;

	switch (dn->max_level) {
	case 3:
		base += 2 * indirect_blks;
	case 2:
		base += 2 * direct_blks;
	case 1:
		base += direct_index;
		break;
	default:
		f2fs_bug_on(F2FS_I_SB(dn->inode), 1);
	}

	return ((pgofs - base) / skipped_unit + 1) * skipped_unit + base;
}

J
Jaegeuk Kim 已提交
480
/*
J
Jaegeuk Kim 已提交
481 482 483
 * The maximum depth is four.
 * Offset[0] will have raw inode offset.
 */
484
static int get_node_path(struct inode *inode, long block,
485
				int offset[4], unsigned int noffset[4])
J
Jaegeuk Kim 已提交
486
{
487
	const long direct_index = ADDRS_PER_INODE(inode);
J
Jaegeuk Kim 已提交
488 489 490 491 492 493 494 495 496 497
	const long direct_blks = ADDRS_PER_BLOCK;
	const long dptrs_per_blk = NIDS_PER_BLOCK;
	const long indirect_blks = ADDRS_PER_BLOCK * NIDS_PER_BLOCK;
	const long dindirect_blks = indirect_blks * NIDS_PER_BLOCK;
	int n = 0;
	int level = 0;

	noffset[0] = 0;

	if (block < direct_index) {
498
		offset[n] = block;
J
Jaegeuk Kim 已提交
499 500 501 502 503 504
		goto got;
	}
	block -= direct_index;
	if (block < direct_blks) {
		offset[n++] = NODE_DIR1_BLOCK;
		noffset[n] = 1;
505
		offset[n] = block;
J
Jaegeuk Kim 已提交
506 507 508 509 510 511 512
		level = 1;
		goto got;
	}
	block -= direct_blks;
	if (block < direct_blks) {
		offset[n++] = NODE_DIR2_BLOCK;
		noffset[n] = 2;
513
		offset[n] = block;
J
Jaegeuk Kim 已提交
514 515 516 517 518 519 520 521 522
		level = 1;
		goto got;
	}
	block -= direct_blks;
	if (block < indirect_blks) {
		offset[n++] = NODE_IND1_BLOCK;
		noffset[n] = 3;
		offset[n++] = block / direct_blks;
		noffset[n] = 4 + offset[n - 1];
523
		offset[n] = block % direct_blks;
J
Jaegeuk Kim 已提交
524 525 526 527 528 529 530 531 532
		level = 2;
		goto got;
	}
	block -= indirect_blks;
	if (block < indirect_blks) {
		offset[n++] = NODE_IND2_BLOCK;
		noffset[n] = 4 + dptrs_per_blk;
		offset[n++] = block / direct_blks;
		noffset[n] = 5 + dptrs_per_blk + offset[n - 1];
533
		offset[n] = block % direct_blks;
J
Jaegeuk Kim 已提交
534 535 536 537 538 539 540 541 542 543 544 545 546 547
		level = 2;
		goto got;
	}
	block -= indirect_blks;
	if (block < dindirect_blks) {
		offset[n++] = NODE_DIND_BLOCK;
		noffset[n] = 5 + (dptrs_per_blk * 2);
		offset[n++] = block / indirect_blks;
		noffset[n] = 6 + (dptrs_per_blk * 2) +
			      offset[n - 1] * (dptrs_per_blk + 1);
		offset[n++] = (block / direct_blks) % dptrs_per_blk;
		noffset[n] = 7 + (dptrs_per_blk * 2) +
			      offset[n - 2] * (dptrs_per_blk + 1) +
			      offset[n - 1];
548
		offset[n] = block % direct_blks;
J
Jaegeuk Kim 已提交
549 550 551 552 553 554 555 556 557 558 559
		level = 3;
		goto got;
	} else {
		BUG();
	}
got:
	return level;
}

/*
 * Caller should call f2fs_put_dnode(dn).
C
Chao Yu 已提交
560 561
 * Also, it should grab and release a rwsem by calling f2fs_lock_op() and
 * f2fs_unlock_op() only if ro is not set RDONLY_NODE.
562
 * In the case of RDONLY_NODE, we don't need to care about mutex.
J
Jaegeuk Kim 已提交
563
 */
564
int get_dnode_of_data(struct dnode_of_data *dn, pgoff_t index, int mode)
J
Jaegeuk Kim 已提交
565
{
566
	struct f2fs_sb_info *sbi = F2FS_I_SB(dn->inode);
J
Jaegeuk Kim 已提交
567
	struct page *npage[4];
568
	struct page *parent = NULL;
J
Jaegeuk Kim 已提交
569 570 571
	int offset[4];
	unsigned int noffset[4];
	nid_t nids[4];
572
	int level, i = 0;
J
Jaegeuk Kim 已提交
573 574
	int err = 0;

575
	level = get_node_path(dn->inode, index, offset, noffset);
J
Jaegeuk Kim 已提交
576 577

	nids[0] = dn->inode->i_ino;
578
	npage[0] = dn->inode_page;
J
Jaegeuk Kim 已提交
579

580 581 582 583 584
	if (!npage[0]) {
		npage[0] = get_node_page(sbi, nids[0]);
		if (IS_ERR(npage[0]))
			return PTR_ERR(npage[0]);
	}
585 586 587

	/* if inline_data is set, should not report any block indices */
	if (f2fs_has_inline_data(dn->inode) && index) {
588
		err = -ENOENT;
589 590 591 592
		f2fs_put_page(npage[0], 1);
		goto release_out;
	}

J
Jaegeuk Kim 已提交
593
	parent = npage[0];
594 595
	if (level != 0)
		nids[1] = get_nid(parent, offset[0], true);
J
Jaegeuk Kim 已提交
596 597 598 599 600 601 602
	dn->inode_page = npage[0];
	dn->inode_page_locked = true;

	/* get indirect or direct nodes */
	for (i = 1; i <= level; i++) {
		bool done = false;

603
		if (!nids[i] && mode == ALLOC_NODE) {
J
Jaegeuk Kim 已提交
604 605 606 607 608 609 610
			/* alloc new node */
			if (!alloc_nid(sbi, &(nids[i]))) {
				err = -ENOSPC;
				goto release_pages;
			}

			dn->nid = nids[i];
611
			npage[i] = new_node_page(dn, noffset[i], NULL);
J
Jaegeuk Kim 已提交
612 613 614 615 616 617 618 619 620
			if (IS_ERR(npage[i])) {
				alloc_nid_failed(sbi, nids[i]);
				err = PTR_ERR(npage[i]);
				goto release_pages;
			}

			set_nid(parent, offset[i - 1], nids[i], i == 1);
			alloc_nid_done(sbi, nids[i]);
			done = true;
621
		} else if (mode == LOOKUP_NODE_RA && i == level && level > 1) {
J
Jaegeuk Kim 已提交
622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661
			npage[i] = get_node_page_ra(parent, offset[i - 1]);
			if (IS_ERR(npage[i])) {
				err = PTR_ERR(npage[i]);
				goto release_pages;
			}
			done = true;
		}
		if (i == 1) {
			dn->inode_page_locked = false;
			unlock_page(parent);
		} else {
			f2fs_put_page(parent, 1);
		}

		if (!done) {
			npage[i] = get_node_page(sbi, nids[i]);
			if (IS_ERR(npage[i])) {
				err = PTR_ERR(npage[i]);
				f2fs_put_page(npage[0], 0);
				goto release_out;
			}
		}
		if (i < level) {
			parent = npage[i];
			nids[i + 1] = get_nid(parent, offset[i], false);
		}
	}
	dn->nid = nids[level];
	dn->ofs_in_node = offset[level];
	dn->node_page = npage[level];
	dn->data_blkaddr = datablock_addr(dn->node_page, dn->ofs_in_node);
	return 0;

release_pages:
	f2fs_put_page(parent, 1);
	if (i > 1)
		f2fs_put_page(npage[0], 0);
release_out:
	dn->inode_page = NULL;
	dn->node_page = NULL;
662 663 664
	if (err == -ENOENT) {
		dn->cur_level = i;
		dn->max_level = level;
665
		dn->ofs_in_node = offset[level];
666
	}
J
Jaegeuk Kim 已提交
667 668 669 670 671
	return err;
}

static void truncate_node(struct dnode_of_data *dn)
{
672
	struct f2fs_sb_info *sbi = F2FS_I_SB(dn->inode);
J
Jaegeuk Kim 已提交
673 674 675
	struct node_info ni;

	get_node_info(sbi, dn->nid, &ni);
676
	if (dn->inode->i_blocks == 0) {
677
		f2fs_bug_on(sbi, ni.blk_addr != NULL_ADDR);
678 679
		goto invalidate;
	}
680
	f2fs_bug_on(sbi, ni.blk_addr == NULL_ADDR);
J
Jaegeuk Kim 已提交
681 682

	/* Deallocate node address */
683
	invalidate_blocks(sbi, ni.blk_addr);
684
	dec_valid_node_count(sbi, dn->inode);
685
	set_node_addr(sbi, &ni, NULL_ADDR, false);
J
Jaegeuk Kim 已提交
686 687 688 689

	if (dn->nid == dn->inode->i_ino) {
		remove_orphan_inode(sbi, dn->nid);
		dec_valid_inode_count(sbi);
690
		f2fs_inode_synced(dn->inode);
J
Jaegeuk Kim 已提交
691
	}
692
invalidate:
J
Jaegeuk Kim 已提交
693
	clear_node_page_dirty(dn->node_page);
694
	set_sbi_flag(sbi, SBI_IS_DIRTY);
J
Jaegeuk Kim 已提交
695 696

	f2fs_put_page(dn->node_page, 1);
697 698 699 700

	invalidate_mapping_pages(NODE_MAPPING(sbi),
			dn->node_page->index, dn->node_page->index);

J
Jaegeuk Kim 已提交
701
	dn->node_page = NULL;
702
	trace_f2fs_truncate_node(dn->inode, dn->nid, ni.blk_addr);
J
Jaegeuk Kim 已提交
703 704 705 706 707 708 709 710 711 712
}

static int truncate_dnode(struct dnode_of_data *dn)
{
	struct page *page;

	if (dn->nid == 0)
		return 1;

	/* get direct node */
713
	page = get_node_page(F2FS_I_SB(dn->inode), dn->nid);
J
Jaegeuk Kim 已提交
714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740
	if (IS_ERR(page) && PTR_ERR(page) == -ENOENT)
		return 1;
	else if (IS_ERR(page))
		return PTR_ERR(page);

	/* Make dnode_of_data for parameter */
	dn->node_page = page;
	dn->ofs_in_node = 0;
	truncate_data_blocks(dn);
	truncate_node(dn);
	return 1;
}

static int truncate_nodes(struct dnode_of_data *dn, unsigned int nofs,
						int ofs, int depth)
{
	struct dnode_of_data rdn = *dn;
	struct page *page;
	struct f2fs_node *rn;
	nid_t child_nid;
	unsigned int child_nofs;
	int freed = 0;
	int i, ret;

	if (dn->nid == 0)
		return NIDS_PER_BLOCK + 1;

741 742
	trace_f2fs_truncate_nodes_enter(dn->inode, dn->nid, dn->data_blkaddr);

743
	page = get_node_page(F2FS_I_SB(dn->inode), dn->nid);
744 745
	if (IS_ERR(page)) {
		trace_f2fs_truncate_nodes_exit(dn->inode, PTR_ERR(page));
J
Jaegeuk Kim 已提交
746
		return PTR_ERR(page);
747
	}
J
Jaegeuk Kim 已提交
748

749 750
	ra_node_pages(page, ofs, NIDS_PER_BLOCK);

751
	rn = F2FS_NODE(page);
J
Jaegeuk Kim 已提交
752 753 754 755 756 757 758 759 760
	if (depth < 3) {
		for (i = ofs; i < NIDS_PER_BLOCK; i++, freed++) {
			child_nid = le32_to_cpu(rn->in.nid[i]);
			if (child_nid == 0)
				continue;
			rdn.nid = child_nid;
			ret = truncate_dnode(&rdn);
			if (ret < 0)
				goto out_err;
761 762
			if (set_nid(page, i, 0, false))
				dn->node_changed = true;
J
Jaegeuk Kim 已提交
763 764 765 766 767 768 769 770 771 772 773 774
		}
	} else {
		child_nofs = nofs + ofs * (NIDS_PER_BLOCK + 1) + 1;
		for (i = ofs; i < NIDS_PER_BLOCK; i++) {
			child_nid = le32_to_cpu(rn->in.nid[i]);
			if (child_nid == 0) {
				child_nofs += NIDS_PER_BLOCK + 1;
				continue;
			}
			rdn.nid = child_nid;
			ret = truncate_nodes(&rdn, child_nofs, 0, depth - 1);
			if (ret == (NIDS_PER_BLOCK + 1)) {
775 776
				if (set_nid(page, i, 0, false))
					dn->node_changed = true;
J
Jaegeuk Kim 已提交
777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792
				child_nofs += ret;
			} else if (ret < 0 && ret != -ENOENT) {
				goto out_err;
			}
		}
		freed = child_nofs;
	}

	if (!ofs) {
		/* remove current indirect node */
		dn->node_page = page;
		truncate_node(dn);
		freed++;
	} else {
		f2fs_put_page(page, 1);
	}
793
	trace_f2fs_truncate_nodes_exit(dn->inode, freed);
J
Jaegeuk Kim 已提交
794 795 796 797
	return freed;

out_err:
	f2fs_put_page(page, 1);
798
	trace_f2fs_truncate_nodes_exit(dn->inode, ret);
J
Jaegeuk Kim 已提交
799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816
	return ret;
}

static int truncate_partial_nodes(struct dnode_of_data *dn,
			struct f2fs_inode *ri, int *offset, int depth)
{
	struct page *pages[2];
	nid_t nid[3];
	nid_t child_nid;
	int err = 0;
	int i;
	int idx = depth - 2;

	nid[0] = le32_to_cpu(ri->i_nid[offset[0] - NODE_DIR1_BLOCK]);
	if (!nid[0])
		return 0;

	/* get indirect nodes in the path */
817
	for (i = 0; i < idx + 1; i++) {
A
arter97 已提交
818
		/* reference count'll be increased */
819
		pages[i] = get_node_page(F2FS_I_SB(dn->inode), nid[i]);
J
Jaegeuk Kim 已提交
820 821
		if (IS_ERR(pages[i])) {
			err = PTR_ERR(pages[i]);
822
			idx = i - 1;
J
Jaegeuk Kim 已提交
823 824 825 826 827
			goto fail;
		}
		nid[i + 1] = get_nid(pages[i], offset[i + 1], false);
	}

828 829
	ra_node_pages(pages[idx], offset[idx + 1], NIDS_PER_BLOCK);

J
Jaegeuk Kim 已提交
830
	/* free direct nodes linked to a partial indirect node */
831
	for (i = offset[idx + 1]; i < NIDS_PER_BLOCK; i++) {
J
Jaegeuk Kim 已提交
832 833 834 835 836 837 838
		child_nid = get_nid(pages[idx], i, false);
		if (!child_nid)
			continue;
		dn->nid = child_nid;
		err = truncate_dnode(dn);
		if (err < 0)
			goto fail;
839 840
		if (set_nid(pages[idx], i, 0, false))
			dn->node_changed = true;
J
Jaegeuk Kim 已提交
841 842
	}

843
	if (offset[idx + 1] == 0) {
J
Jaegeuk Kim 已提交
844 845 846 847 848 849 850
		dn->node_page = pages[idx];
		dn->nid = nid[idx];
		truncate_node(dn);
	} else {
		f2fs_put_page(pages[idx], 1);
	}
	offset[idx]++;
851 852
	offset[idx + 1] = 0;
	idx--;
J
Jaegeuk Kim 已提交
853
fail:
854
	for (i = idx; i >= 0; i--)
J
Jaegeuk Kim 已提交
855
		f2fs_put_page(pages[i], 1);
856 857 858

	trace_f2fs_truncate_partial_nodes(dn->inode, nid, depth, err);

J
Jaegeuk Kim 已提交
859 860 861
	return err;
}

J
Jaegeuk Kim 已提交
862
/*
J
Jaegeuk Kim 已提交
863 864 865 866
 * All the block addresses of data and nodes should be nullified.
 */
int truncate_inode_blocks(struct inode *inode, pgoff_t from)
{
867
	struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
J
Jaegeuk Kim 已提交
868 869
	int err = 0, cont = 1;
	int level, offset[4], noffset[4];
J
Jaegeuk Kim 已提交
870
	unsigned int nofs = 0;
871
	struct f2fs_inode *ri;
J
Jaegeuk Kim 已提交
872 873 874
	struct dnode_of_data dn;
	struct page *page;

875 876
	trace_f2fs_truncate_inode_blocks_enter(inode, from);

877
	level = get_node_path(inode, from, offset, noffset);
878

J
Jaegeuk Kim 已提交
879
	page = get_node_page(sbi, inode->i_ino);
880 881
	if (IS_ERR(page)) {
		trace_f2fs_truncate_inode_blocks_exit(inode, PTR_ERR(page));
J
Jaegeuk Kim 已提交
882
		return PTR_ERR(page);
883
	}
J
Jaegeuk Kim 已提交
884 885 886 887

	set_new_dnode(&dn, inode, page, NULL, 0);
	unlock_page(page);

888
	ri = F2FS_INODE(page);
J
Jaegeuk Kim 已提交
889 890 891 892 893 894 895 896 897
	switch (level) {
	case 0:
	case 1:
		nofs = noffset[1];
		break;
	case 2:
		nofs = noffset[1];
		if (!offset[level - 1])
			goto skip_partial;
898
		err = truncate_partial_nodes(&dn, ri, offset, level);
J
Jaegeuk Kim 已提交
899 900 901 902 903 904 905 906
		if (err < 0 && err != -ENOENT)
			goto fail;
		nofs += 1 + NIDS_PER_BLOCK;
		break;
	case 3:
		nofs = 5 + 2 * NIDS_PER_BLOCK;
		if (!offset[level - 1])
			goto skip_partial;
907
		err = truncate_partial_nodes(&dn, ri, offset, level);
J
Jaegeuk Kim 已提交
908 909 910 911 912 913 914 915 916
		if (err < 0 && err != -ENOENT)
			goto fail;
		break;
	default:
		BUG();
	}

skip_partial:
	while (cont) {
917
		dn.nid = le32_to_cpu(ri->i_nid[offset[0] - NODE_DIR1_BLOCK]);
J
Jaegeuk Kim 已提交
918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939
		switch (offset[0]) {
		case NODE_DIR1_BLOCK:
		case NODE_DIR2_BLOCK:
			err = truncate_dnode(&dn);
			break;

		case NODE_IND1_BLOCK:
		case NODE_IND2_BLOCK:
			err = truncate_nodes(&dn, nofs, offset[1], 2);
			break;

		case NODE_DIND_BLOCK:
			err = truncate_nodes(&dn, nofs, offset[1], 3);
			cont = 0;
			break;

		default:
			BUG();
		}
		if (err < 0 && err != -ENOENT)
			goto fail;
		if (offset[1] == 0 &&
940
				ri->i_nid[offset[0] - NODE_DIR1_BLOCK]) {
J
Jaegeuk Kim 已提交
941
			lock_page(page);
942
			BUG_ON(page->mapping != NODE_MAPPING(sbi));
943
			f2fs_wait_on_page_writeback(page, NODE, true);
944
			ri->i_nid[offset[0] - NODE_DIR1_BLOCK] = 0;
J
Jaegeuk Kim 已提交
945 946 947 948 949 950 951 952 953
			set_page_dirty(page);
			unlock_page(page);
		}
		offset[1] = 0;
		offset[0]++;
		nofs += err;
	}
fail:
	f2fs_put_page(page, 0);
954
	trace_f2fs_truncate_inode_blocks_exit(inode, err);
J
Jaegeuk Kim 已提交
955 956 957
	return err > 0 ? 0 : err;
}

958 959
int truncate_xattr_node(struct inode *inode, struct page *page)
{
960
	struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
961 962 963 964 965 966 967 968 969 970 971
	nid_t nid = F2FS_I(inode)->i_xattr_nid;
	struct dnode_of_data dn;
	struct page *npage;

	if (!nid)
		return 0;

	npage = get_node_page(sbi, nid);
	if (IS_ERR(npage))
		return PTR_ERR(npage);

972
	f2fs_i_xnid_write(inode, 0);
J
Jaegeuk Kim 已提交
973 974 975 976

	/* need to do checkpoint during fsync */
	F2FS_I(inode)->xattr_ver = cur_cp_version(F2FS_CKPT(sbi));

977 978 979
	set_new_dnode(&dn, inode, page, npage, nid);

	if (page)
980
		dn.inode_page_locked = true;
981 982 983 984
	truncate_node(&dn);
	return 0;
}

985
/*
C
Chao Yu 已提交
986 987
 * Caller should grab and release a rwsem by calling f2fs_lock_op() and
 * f2fs_unlock_op().
988
 */
C
Chao Yu 已提交
989
int remove_inode_page(struct inode *inode)
J
Jaegeuk Kim 已提交
990 991
{
	struct dnode_of_data dn;
C
Chao Yu 已提交
992
	int err;
J
Jaegeuk Kim 已提交
993

994
	set_new_dnode(&dn, inode, NULL, NULL, inode->i_ino);
C
Chao Yu 已提交
995 996 997
	err = get_dnode_of_data(&dn, 0, LOOKUP_NODE);
	if (err)
		return err;
J
Jaegeuk Kim 已提交
998

C
Chao Yu 已提交
999 1000
	err = truncate_xattr_node(inode, dn.inode_page);
	if (err) {
1001
		f2fs_put_dnode(&dn);
C
Chao Yu 已提交
1002
		return err;
J
Jaegeuk Kim 已提交
1003
	}
1004 1005 1006 1007 1008 1009

	/* remove potential inline_data blocks */
	if (S_ISREG(inode->i_mode) || S_ISDIR(inode->i_mode) ||
				S_ISLNK(inode->i_mode))
		truncate_data_blocks_range(&dn, 1);

A
arter97 已提交
1010
	/* 0 is possible, after f2fs_new_inode() has failed */
1011 1012
	f2fs_bug_on(F2FS_I_SB(inode),
			inode->i_blocks != 0 && inode->i_blocks != 1);
1013 1014

	/* will put inode & node pages */
1015
	truncate_node(&dn);
C
Chao Yu 已提交
1016
	return 0;
J
Jaegeuk Kim 已提交
1017 1018
}

1019
struct page *new_inode_page(struct inode *inode)
J
Jaegeuk Kim 已提交
1020 1021 1022 1023 1024
{
	struct dnode_of_data dn;

	/* allocate inode page for new inode */
	set_new_dnode(&dn, inode, NULL, NULL, inode->i_ino);
1025 1026

	/* caller should f2fs_put_page(page, 1); */
1027
	return new_node_page(&dn, 0, NULL);
J
Jaegeuk Kim 已提交
1028 1029
}

1030 1031
struct page *new_node_page(struct dnode_of_data *dn,
				unsigned int ofs, struct page *ipage)
J
Jaegeuk Kim 已提交
1032
{
1033
	struct f2fs_sb_info *sbi = F2FS_I_SB(dn->inode);
J
Jaegeuk Kim 已提交
1034 1035 1036 1037
	struct node_info old_ni, new_ni;
	struct page *page;
	int err;

1038
	if (unlikely(is_inode_flag_set(dn->inode, FI_NO_ALLOC)))
J
Jaegeuk Kim 已提交
1039 1040
		return ERR_PTR(-EPERM);

1041
	page = f2fs_grab_cache_page(NODE_MAPPING(sbi), dn->nid, false);
J
Jaegeuk Kim 已提交
1042 1043 1044
	if (!page)
		return ERR_PTR(-ENOMEM);

1045
	if (unlikely(!inc_valid_node_count(sbi, dn->inode))) {
1046 1047 1048
		err = -ENOSPC;
		goto fail;
	}
J
Jaegeuk Kim 已提交
1049

1050
	get_node_info(sbi, dn->nid, &old_ni);
J
Jaegeuk Kim 已提交
1051 1052

	/* Reinitialize old_ni with new node page */
1053
	f2fs_bug_on(sbi, old_ni.blk_addr != NULL_ADDR);
J
Jaegeuk Kim 已提交
1054 1055
	new_ni = old_ni;
	new_ni.ino = dn->inode->i_ino;
1056
	set_node_addr(sbi, &new_ni, NEW_ADDR, false);
1057

1058
	f2fs_wait_on_page_writeback(page, NODE, true);
1059
	fill_node_footer(page, dn->nid, dn->inode->i_ino, ofs, true);
1060
	set_cold_node(dn->inode, page);
1061 1062
	if (!PageUptodate(page))
		SetPageUptodate(page);
1063 1064
	if (set_page_dirty(page))
		dn->node_changed = true;
J
Jaegeuk Kim 已提交
1065

1066
	if (f2fs_has_xattr_block(ofs))
1067
		f2fs_i_xnid_write(dn->inode, dn->nid);
1068

J
Jaegeuk Kim 已提交
1069 1070 1071 1072 1073
	if (ofs == 0)
		inc_valid_inode_count(sbi);
	return page;

fail:
1074
	clear_node_page_dirty(page);
J
Jaegeuk Kim 已提交
1075 1076 1077 1078
	f2fs_put_page(page, 1);
	return ERR_PTR(err);
}

1079 1080 1081
/*
 * Caller should do after getting the following values.
 * 0: f2fs_put_page(page, 0)
1082
 * LOCKED_PAGE or error: f2fs_put_page(page, 1)
1083
 */
M
Mike Christie 已提交
1084
static int read_node_page(struct page *page, int op_flags)
J
Jaegeuk Kim 已提交
1085
{
1086
	struct f2fs_sb_info *sbi = F2FS_P_SB(page);
J
Jaegeuk Kim 已提交
1087
	struct node_info ni;
1088
	struct f2fs_io_info fio = {
1089
		.sbi = sbi,
1090
		.type = NODE,
M
Mike Christie 已提交
1091 1092
		.op = REQ_OP_READ,
		.op_flags = op_flags,
1093
		.page = page,
1094
		.encrypted_page = NULL,
1095
	};
J
Jaegeuk Kim 已提交
1096

1097 1098 1099
	if (PageUptodate(page))
		return LOCKED_PAGE;

J
Jaegeuk Kim 已提交
1100 1101
	get_node_info(sbi, page->index, &ni);

1102
	if (unlikely(ni.blk_addr == NULL_ADDR)) {
1103
		ClearPageUptodate(page);
J
Jaegeuk Kim 已提交
1104
		return -ENOENT;
1105 1106
	}

1107
	fio.new_blkaddr = fio.old_blkaddr = ni.blk_addr;
1108
	return f2fs_submit_page_bio(&fio);
J
Jaegeuk Kim 已提交
1109 1110
}

J
Jaegeuk Kim 已提交
1111
/*
J
Jaegeuk Kim 已提交
1112 1113 1114 1115 1116
 * Readahead a node page
 */
void ra_node_page(struct f2fs_sb_info *sbi, nid_t nid)
{
	struct page *apage;
1117
	int err;
J
Jaegeuk Kim 已提交
1118

1119 1120 1121 1122
	if (!nid)
		return;
	f2fs_bug_on(sbi, check_nid_range(sbi, nid));

1123 1124 1125 1126
	rcu_read_lock();
	apage = radix_tree_lookup(&NODE_MAPPING(sbi)->page_tree, nid);
	rcu_read_unlock();
	if (apage)
1127
		return;
J
Jaegeuk Kim 已提交
1128

1129
	apage = f2fs_grab_cache_page(NODE_MAPPING(sbi), nid, false);
J
Jaegeuk Kim 已提交
1130 1131 1132
	if (!apage)
		return;

1133
	err = read_node_page(apage, REQ_RAHEAD);
1134
	f2fs_put_page(apage, err ? 1 : 0);
J
Jaegeuk Kim 已提交
1135 1136
}

J
Jaegeuk Kim 已提交
1137
static struct page *__get_node_page(struct f2fs_sb_info *sbi, pgoff_t nid,
1138
					struct page *parent, int start)
J
Jaegeuk Kim 已提交
1139 1140
{
	struct page *page;
1141
	int err;
J
Jaegeuk Kim 已提交
1142 1143 1144

	if (!nid)
		return ERR_PTR(-ENOENT);
1145
	f2fs_bug_on(sbi, check_nid_range(sbi, nid));
1146
repeat:
1147
	page = f2fs_grab_cache_page(NODE_MAPPING(sbi), nid, false);
J
Jaegeuk Kim 已提交
1148 1149 1150
	if (!page)
		return ERR_PTR(-ENOMEM);

1151
	err = read_node_page(page, 0);
1152 1153
	if (err < 0) {
		f2fs_put_page(page, 1);
J
Jaegeuk Kim 已提交
1154
		return ERR_PTR(err);
1155
	} else if (err == LOCKED_PAGE) {
1156
		goto page_hit;
1157
	}
J
Jaegeuk Kim 已提交
1158

1159
	if (parent)
1160
		ra_node_pages(parent, start + 1, MAX_RA_NODE);
1161

J
Jaegeuk Kim 已提交
1162
	lock_page(page);
1163

1164
	if (unlikely(page->mapping != NODE_MAPPING(sbi))) {
1165 1166 1167
		f2fs_put_page(page, 1);
		goto repeat;
	}
1168 1169 1170

	if (unlikely(!PageUptodate(page)))
		goto out_err;
1171
page_hit:
1172 1173 1174 1175 1176 1177 1178
	if(unlikely(nid != nid_of_node(page))) {
		f2fs_bug_on(sbi, 1);
		ClearPageUptodate(page);
out_err:
		f2fs_put_page(page, 1);
		return ERR_PTR(-EIO);
	}
J
Jaegeuk Kim 已提交
1179 1180 1181
	return page;
}

1182 1183 1184 1185 1186 1187 1188 1189 1190 1191 1192 1193 1194
struct page *get_node_page(struct f2fs_sb_info *sbi, pgoff_t nid)
{
	return __get_node_page(sbi, nid, NULL, 0);
}

struct page *get_node_page_ra(struct page *parent, int start)
{
	struct f2fs_sb_info *sbi = F2FS_P_SB(parent);
	nid_t nid = get_nid(parent, start, false);

	return __get_node_page(sbi, nid, parent, start);
}

1195 1196 1197 1198
static void flush_inline_data(struct f2fs_sb_info *sbi, nid_t ino)
{
	struct inode *inode;
	struct page *page;
1199
	int ret;
1200 1201 1202 1203 1204 1205

	/* should flush inline_data before evict_inode */
	inode = ilookup(sbi->sb, ino);
	if (!inode)
		return;

1206
	page = pagecache_get_page(inode->i_mapping, 0, FGP_LOCK|FGP_NOWAIT, 0);
1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218
	if (!page)
		goto iput_out;

	if (!PageUptodate(page))
		goto page_out;

	if (!PageDirty(page))
		goto page_out;

	if (!clear_page_dirty_for_io(page))
		goto page_out;

1219 1220
	ret = f2fs_write_inline_data(inode, page);
	inode_dec_dirty_pages(inode);
1221
	remove_dirty_inode(inode);
1222
	if (ret)
1223 1224
		set_page_dirty(page);
page_out:
1225
	f2fs_put_page(page, 1);
1226 1227 1228 1229
iput_out:
	iput(inode);
}

1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260
void move_node_page(struct page *node_page, int gc_type)
{
	if (gc_type == FG_GC) {
		struct f2fs_sb_info *sbi = F2FS_P_SB(node_page);
		struct writeback_control wbc = {
			.sync_mode = WB_SYNC_ALL,
			.nr_to_write = 1,
			.for_reclaim = 0,
		};

		set_page_dirty(node_page);
		f2fs_wait_on_page_writeback(node_page, NODE, true);

		f2fs_bug_on(sbi, PageWriteback(node_page));
		if (!clear_page_dirty_for_io(node_page))
			goto out_page;

		if (NODE_MAPPING(sbi)->a_ops->writepage(node_page, &wbc))
			unlock_page(node_page);
		goto release_page;
	} else {
		/* set page dirty and write it */
		if (!PageWriteback(node_page))
			set_page_dirty(node_page);
	}
out_page:
	unlock_page(node_page);
release_page:
	f2fs_put_page(node_page, 0);
}

1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320
static struct page *last_fsync_dnode(struct f2fs_sb_info *sbi, nid_t ino)
{
	pgoff_t index, end;
	struct pagevec pvec;
	struct page *last_page = NULL;

	pagevec_init(&pvec, 0);
	index = 0;
	end = ULONG_MAX;

	while (index <= end) {
		int i, nr_pages;
		nr_pages = pagevec_lookup_tag(&pvec, NODE_MAPPING(sbi), &index,
				PAGECACHE_TAG_DIRTY,
				min(end - index, (pgoff_t)PAGEVEC_SIZE-1) + 1);
		if (nr_pages == 0)
			break;

		for (i = 0; i < nr_pages; i++) {
			struct page *page = pvec.pages[i];

			if (unlikely(f2fs_cp_error(sbi))) {
				f2fs_put_page(last_page, 0);
				pagevec_release(&pvec);
				return ERR_PTR(-EIO);
			}

			if (!IS_DNODE(page) || !is_cold_node(page))
				continue;
			if (ino_of_node(page) != ino)
				continue;

			lock_page(page);

			if (unlikely(page->mapping != NODE_MAPPING(sbi))) {
continue_unlock:
				unlock_page(page);
				continue;
			}
			if (ino_of_node(page) != ino)
				goto continue_unlock;

			if (!PageDirty(page)) {
				/* someone wrote it for us */
				goto continue_unlock;
			}

			if (last_page)
				f2fs_put_page(last_page, 0);

			get_page(page);
			last_page = page;
			unlock_page(page);
		}
		pagevec_release(&pvec);
		cond_resched();
	}
	return last_page;
}

1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335 1336 1337 1338 1339 1340 1341 1342 1343 1344 1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 1387 1388 1389 1390 1391 1392
static int __write_node_page(struct page *page,
				struct writeback_control *wbc)
{
	struct f2fs_sb_info *sbi = F2FS_P_SB(page);
	nid_t nid;
	struct node_info ni;
	struct f2fs_io_info fio = {
		.sbi = sbi,
		.type = NODE,
		.op = REQ_OP_WRITE,
		.op_flags = wbc_to_write_flags(wbc),
		.page = page,
		.encrypted_page = NULL,
	};

	trace_f2fs_writepage(page, NODE);

	if (unlikely(is_sbi_flag_set(sbi, SBI_POR_DOING)))
		goto redirty_out;
	if (unlikely(f2fs_cp_error(sbi)))
		goto redirty_out;

	/* get old block addr of this node page */
	nid = nid_of_node(page);
	f2fs_bug_on(sbi, page->index != nid);

	if (wbc->for_reclaim) {
		if (!down_read_trylock(&sbi->node_write))
			goto redirty_out;
	} else {
		down_read(&sbi->node_write);
	}

	get_node_info(sbi, nid, &ni);

	/* This page is already truncated */
	if (unlikely(ni.blk_addr == NULL_ADDR)) {
		ClearPageUptodate(page);
		dec_page_count(sbi, F2FS_DIRTY_NODES);
		up_read(&sbi->node_write);
		unlock_page(page);
		return 0;
	}

	set_page_writeback(page);
	fio.old_blkaddr = ni.blk_addr;
	write_node_page(nid, &fio);
	set_node_addr(sbi, &ni, fio.new_blkaddr, is_fsync_dnode(page));
	dec_page_count(sbi, F2FS_DIRTY_NODES);
	up_read(&sbi->node_write);

	if (wbc->for_reclaim)
		f2fs_submit_merged_bio_cond(sbi, NULL, page, 0, NODE, WRITE);

	unlock_page(page);

	if (unlikely(f2fs_cp_error(sbi)))
		f2fs_submit_merged_bio(sbi, NODE, WRITE);

	return 0;

redirty_out:
	redirty_page_for_writepage(wbc, page);
	return AOP_WRITEPAGE_ACTIVATE;
}

static int f2fs_write_node_page(struct page *page,
				struct writeback_control *wbc)
{
	return __write_node_page(page, wbc);
}

1393
int fsync_node_pages(struct f2fs_sb_info *sbi, struct inode *inode,
1394
			struct writeback_control *wbc, bool atomic)
J
Jaegeuk Kim 已提交
1395 1396 1397
{
	pgoff_t index, end;
	struct pagevec pvec;
1398
	int ret = 0;
1399 1400
	struct page *last_page = NULL;
	bool marked = false;
1401
	nid_t ino = inode->i_ino;
1402
	int nwritten = 0;
1403

1404 1405 1406 1407 1408 1409
	if (atomic) {
		last_page = last_fsync_dnode(sbi, ino);
		if (IS_ERR_OR_NULL(last_page))
			return PTR_ERR_OR_ZERO(last_page);
	}
retry:
1410 1411 1412 1413 1414 1415 1416 1417 1418 1419 1420 1421 1422 1423 1424 1425
	pagevec_init(&pvec, 0);
	index = 0;
	end = ULONG_MAX;

	while (index <= end) {
		int i, nr_pages;
		nr_pages = pagevec_lookup_tag(&pvec, NODE_MAPPING(sbi), &index,
				PAGECACHE_TAG_DIRTY,
				min(end - index, (pgoff_t)PAGEVEC_SIZE-1) + 1);
		if (nr_pages == 0)
			break;

		for (i = 0; i < nr_pages; i++) {
			struct page *page = pvec.pages[i];

			if (unlikely(f2fs_cp_error(sbi))) {
1426
				f2fs_put_page(last_page, 0);
1427
				pagevec_release(&pvec);
1428 1429
				ret = -EIO;
				goto out;
1430 1431 1432 1433 1434 1435 1436 1437 1438 1439 1440 1441 1442 1443 1444 1445 1446
			}

			if (!IS_DNODE(page) || !is_cold_node(page))
				continue;
			if (ino_of_node(page) != ino)
				continue;

			lock_page(page);

			if (unlikely(page->mapping != NODE_MAPPING(sbi))) {
continue_unlock:
				unlock_page(page);
				continue;
			}
			if (ino_of_node(page) != ino)
				goto continue_unlock;

1447
			if (!PageDirty(page) && page != last_page) {
1448 1449 1450 1451 1452 1453 1454
				/* someone wrote it for us */
				goto continue_unlock;
			}

			f2fs_wait_on_page_writeback(page, NODE, true);
			BUG_ON(PageWriteback(page));

1455 1456
			if (!atomic || page == last_page) {
				set_fsync_mark(page, 1);
1457 1458 1459 1460
				if (IS_INODE(page)) {
					if (is_inode_flag_set(inode,
								FI_DIRTY_INODE))
						update_inode(inode, page);
1461
					set_dentry_mark(page,
1462
						need_dentry_mark(sbi, ino));
1463
				}
1464 1465 1466 1467 1468 1469 1470
				/*  may be written by other thread */
				if (!PageDirty(page))
					set_page_dirty(page);
			}

			if (!clear_page_dirty_for_io(page))
				goto continue_unlock;
1471

1472
			ret = __write_node_page(page, wbc);
1473
			if (ret) {
1474
				unlock_page(page);
1475 1476
				f2fs_put_page(last_page, 0);
				break;
1477 1478
			} else {
				nwritten++;
1479
			}
1480

1481 1482 1483
			if (page == last_page) {
				f2fs_put_page(page, 0);
				marked = true;
1484
				break;
1485
			}
1486 1487 1488 1489
		}
		pagevec_release(&pvec);
		cond_resched();

1490
		if (ret || marked)
1491 1492
			break;
	}
1493 1494 1495 1496 1497
	if (!ret && atomic && !marked) {
		f2fs_msg(sbi->sb, KERN_DEBUG,
			"Retry to write fsync mark: ino=%u, idx=%lx",
					ino, last_page->index);
		lock_page(last_page);
1498
		f2fs_wait_on_page_writeback(last_page, NODE, true);
1499 1500 1501 1502
		set_page_dirty(last_page);
		unlock_page(last_page);
		goto retry;
	}
1503
out:
1504 1505
	if (nwritten)
		f2fs_submit_merged_bio_cond(sbi, NULL, NULL, ino, NODE, WRITE);
1506
	return ret ? -EIO: 0;
1507 1508 1509 1510 1511 1512 1513
}

int sync_node_pages(struct f2fs_sb_info *sbi, struct writeback_control *wbc)
{
	pgoff_t index, end;
	struct pagevec pvec;
	int step = 0;
1514
	int nwritten = 0;
1515
	int ret = 0;
J
Jaegeuk Kim 已提交
1516 1517 1518 1519 1520

	pagevec_init(&pvec, 0);

next_step:
	index = 0;
1521
	end = ULONG_MAX;
J
Jaegeuk Kim 已提交
1522 1523 1524

	while (index <= end) {
		int i, nr_pages;
1525
		nr_pages = pagevec_lookup_tag(&pvec, NODE_MAPPING(sbi), &index,
J
Jaegeuk Kim 已提交
1526 1527 1528 1529 1530 1531 1532 1533
				PAGECACHE_TAG_DIRTY,
				min(end - index, (pgoff_t)PAGEVEC_SIZE-1) + 1);
		if (nr_pages == 0)
			break;

		for (i = 0; i < nr_pages; i++) {
			struct page *page = pvec.pages[i];

C
Chao Yu 已提交
1534 1535
			if (unlikely(f2fs_cp_error(sbi))) {
				pagevec_release(&pvec);
1536 1537
				ret = -EIO;
				goto out;
C
Chao Yu 已提交
1538 1539
			}

J
Jaegeuk Kim 已提交
1540 1541 1542 1543 1544 1545 1546 1547 1548 1549 1550 1551 1552 1553
			/*
			 * flushing sequence with step:
			 * 0. indirect nodes
			 * 1. dentry dnodes
			 * 2. file dnodes
			 */
			if (step == 0 && IS_DNODE(page))
				continue;
			if (step == 1 && (!IS_DNODE(page) ||
						is_cold_node(page)))
				continue;
			if (step == 2 && (!IS_DNODE(page) ||
						!is_cold_node(page)))
				continue;
1554
lock_node:
1555
			if (!trylock_page(page))
J
Jaegeuk Kim 已提交
1556 1557
				continue;

1558
			if (unlikely(page->mapping != NODE_MAPPING(sbi))) {
J
Jaegeuk Kim 已提交
1559 1560 1561 1562 1563 1564 1565 1566 1567 1568
continue_unlock:
				unlock_page(page);
				continue;
			}

			if (!PageDirty(page)) {
				/* someone wrote it for us */
				goto continue_unlock;
			}

1569
			/* flush inline_data */
1570
			if (is_inline_node(page)) {
1571 1572 1573
				clear_inline_node(page);
				unlock_page(page);
				flush_inline_data(sbi, ino_of_node(page));
1574
				goto lock_node;
1575 1576
			}

1577 1578 1579
			f2fs_wait_on_page_writeback(page, NODE, true);

			BUG_ON(PageWriteback(page));
J
Jaegeuk Kim 已提交
1580 1581 1582
			if (!clear_page_dirty_for_io(page))
				goto continue_unlock;

1583 1584
			set_fsync_mark(page, 0);
			set_dentry_mark(page, 0);
1585 1586 1587

			if (NODE_MAPPING(sbi)->a_ops->writepage(page, wbc))
				unlock_page(page);
1588 1589
			else
				nwritten++;
J
Jaegeuk Kim 已提交
1590 1591 1592 1593 1594 1595 1596 1597 1598 1599 1600 1601 1602 1603 1604 1605 1606

			if (--wbc->nr_to_write == 0)
				break;
		}
		pagevec_release(&pvec);
		cond_resched();

		if (wbc->nr_to_write == 0) {
			step = 2;
			break;
		}
	}

	if (step < 2) {
		step++;
		goto next_step;
	}
1607 1608 1609 1610
out:
	if (nwritten)
		f2fs_submit_merged_bio(sbi, NODE, WRITE);
	return ret;
J
Jaegeuk Kim 已提交
1611 1612
}

1613 1614
int wait_on_node_pages_writeback(struct f2fs_sb_info *sbi, nid_t ino)
{
1615
	pgoff_t index = 0, end = ULONG_MAX;
1616
	struct pagevec pvec;
1617
	int ret2, ret = 0;
1618 1619

	pagevec_init(&pvec, 0);
1620 1621 1622 1623 1624 1625 1626 1627

	while (index <= end) {
		int i, nr_pages;
		nr_pages = pagevec_lookup_tag(&pvec, NODE_MAPPING(sbi), &index,
				PAGECACHE_TAG_WRITEBACK,
				min(end - index, (pgoff_t)PAGEVEC_SIZE-1) + 1);
		if (nr_pages == 0)
			break;
1628 1629 1630 1631 1632

		for (i = 0; i < nr_pages; i++) {
			struct page *page = pvec.pages[i];

			/* until radix tree lookup accepts end_index */
1633
			if (unlikely(page->index > end))
1634 1635
				continue;

1636
			if (ino && ino_of_node(page) == ino) {
1637
				f2fs_wait_on_page_writeback(page, NODE, true);
1638 1639 1640
				if (TestClearPageError(page))
					ret = -EIO;
			}
1641 1642 1643 1644 1645
		}
		pagevec_release(&pvec);
		cond_resched();
	}

1646
	ret2 = filemap_check_errors(NODE_MAPPING(sbi));
1647 1648 1649 1650 1651
	if (!ret)
		ret = ret2;
	return ret;
}

J
Jaegeuk Kim 已提交
1652 1653 1654
static int f2fs_write_node_pages(struct address_space *mapping,
			    struct writeback_control *wbc)
{
1655
	struct f2fs_sb_info *sbi = F2FS_M_SB(mapping);
1656
	struct blk_plug plug;
1657
	long diff;
J
Jaegeuk Kim 已提交
1658

1659 1660
	/* balancing f2fs's metadata in background */
	f2fs_balance_fs_bg(sbi);
J
Jaegeuk Kim 已提交
1661

1662
	/* collect a number of dirty node pages and write together */
1663
	if (get_pages(sbi, F2FS_DIRTY_NODES) < nr_pages_to_skip(sbi, NODE))
1664
		goto skip_write;
1665

Y
Yunlei He 已提交
1666 1667
	trace_f2fs_writepages(mapping->host, wbc, NODE);

1668
	diff = nr_pages_to_write(sbi, NODE, wbc);
1669
	wbc->sync_mode = WB_SYNC_NONE;
1670
	blk_start_plug(&plug);
1671
	sync_node_pages(sbi, wbc);
1672
	blk_finish_plug(&plug);
1673
	wbc->nr_to_write = max((long)0, wbc->nr_to_write - diff);
J
Jaegeuk Kim 已提交
1674
	return 0;
1675 1676 1677

skip_write:
	wbc->pages_skipped += get_pages(sbi, F2FS_DIRTY_NODES);
Y
Yunlei He 已提交
1678
	trace_f2fs_writepages(mapping->host, wbc, NODE);
1679
	return 0;
J
Jaegeuk Kim 已提交
1680 1681 1682 1683
}

static int f2fs_set_node_page_dirty(struct page *page)
{
1684 1685
	trace_f2fs_set_page_dirty(page, NODE);

1686 1687
	if (!PageUptodate(page))
		SetPageUptodate(page);
J
Jaegeuk Kim 已提交
1688
	if (!PageDirty(page)) {
1689
		f2fs_set_page_dirty_nobuffers(page);
1690
		inc_page_count(F2FS_P_SB(page), F2FS_DIRTY_NODES);
J
Jaegeuk Kim 已提交
1691
		SetPagePrivate(page);
J
Jaegeuk Kim 已提交
1692
		f2fs_trace_pid(page);
J
Jaegeuk Kim 已提交
1693 1694 1695 1696 1697
		return 1;
	}
	return 0;
}

J
Jaegeuk Kim 已提交
1698
/*
J
Jaegeuk Kim 已提交
1699 1700 1701 1702 1703 1704
 * Structure of the f2fs node operations
 */
const struct address_space_operations f2fs_node_aops = {
	.writepage	= f2fs_write_node_page,
	.writepages	= f2fs_write_node_pages,
	.set_page_dirty	= f2fs_set_node_page_dirty,
1705 1706
	.invalidatepage	= f2fs_invalidate_page,
	.releasepage	= f2fs_release_page,
1707 1708 1709
#ifdef CONFIG_MIGRATION
	.migratepage    = f2fs_migrate_page,
#endif
J
Jaegeuk Kim 已提交
1710 1711
};

1712 1713
static struct free_nid *__lookup_free_nid_list(struct f2fs_nm_info *nm_i,
						nid_t n)
J
Jaegeuk Kim 已提交
1714
{
1715
	return radix_tree_lookup(&nm_i->free_nid_root, n);
J
Jaegeuk Kim 已提交
1716 1717
}

1718 1719
static int __insert_nid_to_list(struct f2fs_sb_info *sbi,
			struct free_nid *i, enum nid_list list, bool new)
J
Jaegeuk Kim 已提交
1720
{
C
Chao Yu 已提交
1721 1722
	struct f2fs_nm_info *nm_i = NM_I(sbi);

1723 1724 1725 1726 1727 1728
	if (new) {
		int err = radix_tree_insert(&nm_i->free_nid_root, i->nid, i);
		if (err)
			return err;
	}

C
Chao Yu 已提交
1729 1730 1731 1732
	f2fs_bug_on(sbi, list == FREE_NID_LIST ? i->state != NID_NEW :
						i->state != NID_ALLOC);
	nm_i->nid_cnt[list]++;
	list_add_tail(&i->list, &nm_i->nid_list[list]);
1733
	return 0;
C
Chao Yu 已提交
1734 1735 1736
}

static void __remove_nid_from_list(struct f2fs_sb_info *sbi,
1737
			struct free_nid *i, enum nid_list list, bool reuse)
C
Chao Yu 已提交
1738 1739 1740 1741 1742 1743
{
	struct f2fs_nm_info *nm_i = NM_I(sbi);

	f2fs_bug_on(sbi, list == FREE_NID_LIST ? i->state != NID_NEW :
						i->state != NID_ALLOC);
	nm_i->nid_cnt[list]--;
J
Jaegeuk Kim 已提交
1744
	list_del(&i->list);
1745 1746
	if (!reuse)
		radix_tree_delete(&nm_i->free_nid_root, i->nid);
J
Jaegeuk Kim 已提交
1747 1748
}

1749
static int add_free_nid(struct f2fs_sb_info *sbi, nid_t nid, bool build)
J
Jaegeuk Kim 已提交
1750
{
1751
	struct f2fs_nm_info *nm_i = NM_I(sbi);
J
Jaegeuk Kim 已提交
1752
	struct free_nid *i;
1753
	struct nat_entry *ne;
1754
	int err;
1755 1756

	/* 0 nid should not be used */
1757
	if (unlikely(nid == 0))
1758
		return 0;
1759

1760 1761 1762
	if (build) {
		/* do not add allocated nids */
		ne = __lookup_nat_cache(nm_i, nid);
1763
		if (ne && (!get_nat_flag(ne, IS_CHECKPOINTED) ||
1764
				nat_get_blkaddr(ne) != NULL_ADDR))
1765
			return 0;
J
Jaegeuk Kim 已提交
1766
	}
1767 1768

	i = f2fs_kmem_cache_alloc(free_nid_slab, GFP_NOFS);
J
Jaegeuk Kim 已提交
1769 1770 1771
	i->nid = nid;
	i->state = NID_NEW;

1772 1773 1774 1775 1776
	if (radix_tree_preload(GFP_NOFS)) {
		kmem_cache_free(free_nid_slab, i);
		return 0;
	}

C
Chao Yu 已提交
1777
	spin_lock(&nm_i->nid_list_lock);
1778 1779 1780 1781
	err = __insert_nid_to_list(sbi, i, FREE_NID_LIST, true);
	spin_unlock(&nm_i->nid_list_lock);
	radix_tree_preload_end();
	if (err) {
J
Jaegeuk Kim 已提交
1782 1783 1784 1785 1786 1787
		kmem_cache_free(free_nid_slab, i);
		return 0;
	}
	return 1;
}

C
Chao Yu 已提交
1788
static void remove_free_nid(struct f2fs_sb_info *sbi, nid_t nid)
J
Jaegeuk Kim 已提交
1789
{
C
Chao Yu 已提交
1790
	struct f2fs_nm_info *nm_i = NM_I(sbi);
J
Jaegeuk Kim 已提交
1791
	struct free_nid *i;
1792 1793
	bool need_free = false;

C
Chao Yu 已提交
1794
	spin_lock(&nm_i->nid_list_lock);
1795
	i = __lookup_free_nid_list(nm_i, nid);
J
Jaegeuk Kim 已提交
1796
	if (i && i->state == NID_NEW) {
1797
		__remove_nid_from_list(sbi, i, FREE_NID_LIST, false);
1798
		need_free = true;
J
Jaegeuk Kim 已提交
1799
	}
C
Chao Yu 已提交
1800
	spin_unlock(&nm_i->nid_list_lock);
1801 1802 1803

	if (need_free)
		kmem_cache_free(free_nid_slab, i);
J
Jaegeuk Kim 已提交
1804 1805
}

1806
static void scan_nat_page(struct f2fs_sb_info *sbi,
J
Jaegeuk Kim 已提交
1807 1808
			struct page *nat_page, nid_t start_nid)
{
1809
	struct f2fs_nm_info *nm_i = NM_I(sbi);
J
Jaegeuk Kim 已提交
1810 1811 1812 1813 1814 1815 1816
	struct f2fs_nat_block *nat_blk = page_address(nat_page);
	block_t blk_addr;
	int i;

	i = start_nid % NAT_ENTRY_PER_BLOCK;

	for (; i < NAT_ENTRY_PER_BLOCK; i++, start_nid++) {
H
Haicheng Li 已提交
1817

1818
		if (unlikely(start_nid >= nm_i->max_nid))
J
Jaegeuk Kim 已提交
1819
			break;
H
Haicheng Li 已提交
1820 1821

		blk_addr = le32_to_cpu(nat_blk->entries[i].block_addr);
1822
		f2fs_bug_on(sbi, blk_addr == NEW_ADDR);
1823 1824
		if (blk_addr == NULL_ADDR)
			add_free_nid(sbi, start_nid, true);
J
Jaegeuk Kim 已提交
1825 1826 1827
	}
}

1828
static void __build_free_nids(struct f2fs_sb_info *sbi, bool sync)
J
Jaegeuk Kim 已提交
1829 1830 1831
{
	struct f2fs_nm_info *nm_i = NM_I(sbi);
	struct curseg_info *curseg = CURSEG_I(sbi, CURSEG_HOT_DATA);
1832
	struct f2fs_journal *journal = curseg->journal;
1833
	int i = 0;
1834
	nid_t nid = nm_i->next_scan_nid;
J
Jaegeuk Kim 已提交
1835

1836
	/* Enough entries */
C
Chao Yu 已提交
1837
	if (nm_i->nid_cnt[FREE_NID_LIST] >= NAT_ENTRY_PER_BLOCK)
1838
		return;
J
Jaegeuk Kim 已提交
1839

1840
	if (!sync && !available_free_memory(sbi, FREE_NIDS))
1841
		return;
J
Jaegeuk Kim 已提交
1842

1843
	/* readahead nat pages to be scanned */
1844 1845
	ra_meta_pages(sbi, NAT_BLOCK_OFFSET(nid), FREE_NID_PAGES,
							META_NAT, true);
J
Jaegeuk Kim 已提交
1846

1847
	down_read(&nm_i->nat_tree_lock);
1848

J
Jaegeuk Kim 已提交
1849 1850 1851
	while (1) {
		struct page *page = get_current_nat_page(sbi, nid);

1852
		scan_nat_page(sbi, page, nid);
J
Jaegeuk Kim 已提交
1853 1854 1855
		f2fs_put_page(page, 1);

		nid += (NAT_ENTRY_PER_BLOCK - (nid % NAT_ENTRY_PER_BLOCK));
1856
		if (unlikely(nid >= nm_i->max_nid))
J
Jaegeuk Kim 已提交
1857
			nid = 0;
1858

1859
		if (++i >= FREE_NID_PAGES)
J
Jaegeuk Kim 已提交
1860 1861 1862
			break;
	}

1863 1864
	/* go to the next free nat pages to find free nids abundantly */
	nm_i->next_scan_nid = nid;
J
Jaegeuk Kim 已提交
1865 1866

	/* find free nids from current sum_pages */
1867
	down_read(&curseg->journal_rwsem);
1868 1869 1870 1871 1872
	for (i = 0; i < nats_in_cursum(journal); i++) {
		block_t addr;

		addr = le32_to_cpu(nat_in_journal(journal, i).block_addr);
		nid = le32_to_cpu(nid_in_journal(journal, i));
J
Jaegeuk Kim 已提交
1873
		if (addr == NULL_ADDR)
1874
			add_free_nid(sbi, nid, true);
J
Jaegeuk Kim 已提交
1875
		else
C
Chao Yu 已提交
1876
			remove_free_nid(sbi, nid);
J
Jaegeuk Kim 已提交
1877
	}
1878
	up_read(&curseg->journal_rwsem);
1879
	up_read(&nm_i->nat_tree_lock);
C
Chao Yu 已提交
1880 1881

	ra_meta_pages(sbi, NAT_BLOCK_OFFSET(nm_i->next_scan_nid),
C
Chao Yu 已提交
1882
					nm_i->ra_nid_pages, META_NAT, false);
J
Jaegeuk Kim 已提交
1883 1884
}

1885
void build_free_nids(struct f2fs_sb_info *sbi, bool sync)
1886 1887
{
	mutex_lock(&NM_I(sbi)->build_lock);
1888
	__build_free_nids(sbi, sync);
1889 1890 1891
	mutex_unlock(&NM_I(sbi)->build_lock);
}

J
Jaegeuk Kim 已提交
1892 1893 1894 1895 1896 1897 1898 1899 1900 1901
/*
 * If this function returns success, caller can obtain a new nid
 * from second parameter of this function.
 * The returned nid could be used ino as well as nid when inode is created.
 */
bool alloc_nid(struct f2fs_sb_info *sbi, nid_t *nid)
{
	struct f2fs_nm_info *nm_i = NM_I(sbi);
	struct free_nid *i = NULL;
retry:
J
Jaegeuk Kim 已提交
1902
#ifdef CONFIG_F2FS_FAULT_INJECTION
1903
	if (time_to_inject(sbi, FAULT_ALLOC_NID))
J
Jaegeuk Kim 已提交
1904 1905
		return false;
#endif
C
Chao Yu 已提交
1906
	spin_lock(&nm_i->nid_list_lock);
J
Jaegeuk Kim 已提交
1907

1908 1909 1910 1911
	if (unlikely(nm_i->available_nids == 0)) {
		spin_unlock(&nm_i->nid_list_lock);
		return false;
	}
J
Jaegeuk Kim 已提交
1912

1913
	/* We should not use stale free nids created by build_free_nids */
C
Chao Yu 已提交
1914 1915 1916 1917
	if (nm_i->nid_cnt[FREE_NID_LIST] && !on_build_free_nids(nm_i)) {
		f2fs_bug_on(sbi, list_empty(&nm_i->nid_list[FREE_NID_LIST]));
		i = list_first_entry(&nm_i->nid_list[FREE_NID_LIST],
					struct free_nid, list);
1918
		*nid = i->nid;
C
Chao Yu 已提交
1919

1920
		__remove_nid_from_list(sbi, i, FREE_NID_LIST, true);
1921
		i->state = NID_ALLOC;
1922
		__insert_nid_to_list(sbi, i, ALLOC_NID_LIST, false);
1923
		nm_i->available_nids--;
C
Chao Yu 已提交
1924
		spin_unlock(&nm_i->nid_list_lock);
1925 1926
		return true;
	}
C
Chao Yu 已提交
1927
	spin_unlock(&nm_i->nid_list_lock);
1928 1929

	/* Let's scan nat pages and its caches to get free nids */
1930
	build_free_nids(sbi, true);
1931
	goto retry;
J
Jaegeuk Kim 已提交
1932 1933
}

J
Jaegeuk Kim 已提交
1934
/*
J
Jaegeuk Kim 已提交
1935 1936 1937 1938 1939 1940 1941
 * alloc_nid() should be called prior to this function.
 */
void alloc_nid_done(struct f2fs_sb_info *sbi, nid_t nid)
{
	struct f2fs_nm_info *nm_i = NM_I(sbi);
	struct free_nid *i;

C
Chao Yu 已提交
1942
	spin_lock(&nm_i->nid_list_lock);
1943
	i = __lookup_free_nid_list(nm_i, nid);
C
Chao Yu 已提交
1944
	f2fs_bug_on(sbi, !i);
1945
	__remove_nid_from_list(sbi, i, ALLOC_NID_LIST, false);
C
Chao Yu 已提交
1946
	spin_unlock(&nm_i->nid_list_lock);
1947 1948

	kmem_cache_free(free_nid_slab, i);
J
Jaegeuk Kim 已提交
1949 1950
}

J
Jaegeuk Kim 已提交
1951
/*
J
Jaegeuk Kim 已提交
1952 1953 1954 1955
 * alloc_nid() should be called prior to this function.
 */
void alloc_nid_failed(struct f2fs_sb_info *sbi, nid_t nid)
{
1956 1957
	struct f2fs_nm_info *nm_i = NM_I(sbi);
	struct free_nid *i;
1958
	bool need_free = false;
1959

J
Jaegeuk Kim 已提交
1960 1961 1962
	if (!nid)
		return;

C
Chao Yu 已提交
1963
	spin_lock(&nm_i->nid_list_lock);
1964
	i = __lookup_free_nid_list(nm_i, nid);
C
Chao Yu 已提交
1965 1966
	f2fs_bug_on(sbi, !i);

1967
	if (!available_free_memory(sbi, FREE_NIDS)) {
1968
		__remove_nid_from_list(sbi, i, ALLOC_NID_LIST, false);
1969
		need_free = true;
1970
	} else {
1971
		__remove_nid_from_list(sbi, i, ALLOC_NID_LIST, true);
1972
		i->state = NID_NEW;
1973
		__insert_nid_to_list(sbi, i, FREE_NID_LIST, false);
1974
	}
1975 1976 1977

	nm_i->available_nids++;

C
Chao Yu 已提交
1978
	spin_unlock(&nm_i->nid_list_lock);
1979 1980 1981

	if (need_free)
		kmem_cache_free(free_nid_slab, i);
J
Jaegeuk Kim 已提交
1982 1983
}

C
Chao Yu 已提交
1984 1985 1986 1987 1988 1989
int try_to_free_nids(struct f2fs_sb_info *sbi, int nr_shrink)
{
	struct f2fs_nm_info *nm_i = NM_I(sbi);
	struct free_nid *i, *next;
	int nr = nr_shrink;

C
Chao Yu 已提交
1990
	if (nm_i->nid_cnt[FREE_NID_LIST] <= MAX_FREE_NIDS)
1991 1992
		return 0;

C
Chao Yu 已提交
1993 1994 1995
	if (!mutex_trylock(&nm_i->build_lock))
		return 0;

C
Chao Yu 已提交
1996 1997 1998 1999 2000
	spin_lock(&nm_i->nid_list_lock);
	list_for_each_entry_safe(i, next, &nm_i->nid_list[FREE_NID_LIST],
									list) {
		if (nr_shrink <= 0 ||
				nm_i->nid_cnt[FREE_NID_LIST] <= MAX_FREE_NIDS)
C
Chao Yu 已提交
2001
			break;
C
Chao Yu 已提交
2002

2003
		__remove_nid_from_list(sbi, i, FREE_NID_LIST, false);
C
Chao Yu 已提交
2004 2005 2006
		kmem_cache_free(free_nid_slab, i);
		nr_shrink--;
	}
C
Chao Yu 已提交
2007
	spin_unlock(&nm_i->nid_list_lock);
C
Chao Yu 已提交
2008 2009 2010 2011 2012
	mutex_unlock(&nm_i->build_lock);

	return nr - nr_shrink;
}

2013
void recover_inline_xattr(struct inode *inode, struct page *page)
2014 2015 2016 2017 2018 2019
{
	void *src_addr, *dst_addr;
	size_t inline_size;
	struct page *ipage;
	struct f2fs_inode *ri;

2020
	ipage = get_node_page(F2FS_I_SB(inode), inode->i_ino);
2021
	f2fs_bug_on(F2FS_I_SB(inode), IS_ERR(ipage));
2022

2023 2024
	ri = F2FS_INODE(page);
	if (!(ri->i_inline & F2FS_INLINE_XATTR)) {
2025
		clear_inode_flag(inode, FI_INLINE_XATTR);
2026 2027 2028
		goto update_inode;
	}

2029 2030 2031 2032
	dst_addr = inline_xattr_addr(ipage);
	src_addr = inline_xattr_addr(page);
	inline_size = inline_xattr_size(inode);

2033
	f2fs_wait_on_page_writeback(ipage, NODE, true);
2034
	memcpy(dst_addr, src_addr, inline_size);
2035
update_inode:
2036 2037 2038 2039
	update_inode(inode, ipage);
	f2fs_put_page(ipage, 1);
}

2040
void recover_xattr_data(struct inode *inode, struct page *page, block_t blkaddr)
2041
{
2042
	struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
2043 2044 2045 2046 2047 2048 2049 2050 2051 2052
	nid_t prev_xnid = F2FS_I(inode)->i_xattr_nid;
	nid_t new_xnid = nid_of_node(page);
	struct node_info ni;

	/* 1: invalidate the previous xattr nid */
	if (!prev_xnid)
		goto recover_xnid;

	/* Deallocate node address */
	get_node_info(sbi, prev_xnid, &ni);
2053
	f2fs_bug_on(sbi, ni.blk_addr == NULL_ADDR);
2054 2055
	invalidate_blocks(sbi, ni.blk_addr);
	dec_valid_node_count(sbi, inode);
2056
	set_node_addr(sbi, &ni, NULL_ADDR, false);
2057 2058 2059 2060

recover_xnid:
	/* 2: allocate new xattr nid */
	if (unlikely(!inc_valid_node_count(sbi, inode)))
2061
		f2fs_bug_on(sbi, 1);
2062

C
Chao Yu 已提交
2063
	remove_free_nid(sbi, new_xnid);
2064 2065
	get_node_info(sbi, new_xnid, &ni);
	ni.ino = inode->i_ino;
2066
	set_node_addr(sbi, &ni, NEW_ADDR, false);
2067
	f2fs_i_xnid_write(inode, new_xnid);
2068 2069 2070

	/* 3: update xattr blkaddr */
	refresh_sit_entry(sbi, NEW_ADDR, blkaddr);
2071
	set_node_addr(sbi, &ni, blkaddr, false);
2072 2073
}

J
Jaegeuk Kim 已提交
2074 2075
int recover_inode_page(struct f2fs_sb_info *sbi, struct page *page)
{
2076
	struct f2fs_inode *src, *dst;
J
Jaegeuk Kim 已提交
2077 2078 2079 2080
	nid_t ino = ino_of_node(page);
	struct node_info old_ni, new_ni;
	struct page *ipage;

2081 2082 2083 2084
	get_node_info(sbi, ino, &old_ni);

	if (unlikely(old_ni.blk_addr != NULL_ADDR))
		return -EINVAL;
2085
retry:
2086
	ipage = f2fs_grab_cache_page(NODE_MAPPING(sbi), ino, false);
2087 2088 2089 2090
	if (!ipage) {
		congestion_wait(BLK_RW_ASYNC, HZ/50);
		goto retry;
	}
J
Jaegeuk Kim 已提交
2091

A
arter97 已提交
2092
	/* Should not use this inode from free nid list */
C
Chao Yu 已提交
2093
	remove_free_nid(sbi, ino);
J
Jaegeuk Kim 已提交
2094

2095 2096
	if (!PageUptodate(ipage))
		SetPageUptodate(ipage);
J
Jaegeuk Kim 已提交
2097 2098
	fill_node_footer(ipage, ino, ino, 0, true);

2099 2100
	src = F2FS_INODE(page);
	dst = F2FS_INODE(ipage);
J
Jaegeuk Kim 已提交
2101

2102 2103 2104 2105 2106
	memcpy(dst, src, (unsigned long)&src->i_ext - (unsigned long)src);
	dst->i_size = 0;
	dst->i_blocks = cpu_to_le64(1);
	dst->i_links = cpu_to_le32(1);
	dst->i_xattr_nid = 0;
2107
	dst->i_inline = src->i_inline & F2FS_INLINE_XATTR;
J
Jaegeuk Kim 已提交
2108 2109 2110 2111

	new_ni = old_ni;
	new_ni.ino = ino;

2112
	if (unlikely(!inc_valid_node_count(sbi, NULL)))
2113
		WARN_ON(1);
2114
	set_node_addr(sbi, &new_ni, NEW_ADDR, false);
J
Jaegeuk Kim 已提交
2115
	inc_valid_inode_count(sbi);
2116
	set_page_dirty(ipage);
J
Jaegeuk Kim 已提交
2117 2118 2119 2120 2121 2122 2123 2124 2125 2126
	f2fs_put_page(ipage, 1);
	return 0;
}

int restore_node_summary(struct f2fs_sb_info *sbi,
			unsigned int segno, struct f2fs_summary_block *sum)
{
	struct f2fs_node *rn;
	struct f2fs_summary *sum_entry;
	block_t addr;
2127
	int i, idx, last_offset, nrpages;
J
Jaegeuk Kim 已提交
2128 2129 2130 2131 2132 2133

	/* scan the node segment */
	last_offset = sbi->blocks_per_seg;
	addr = START_BLOCK(sbi, segno);
	sum_entry = &sum->entries[0];

2134
	for (i = 0; i < last_offset; i += nrpages, addr += nrpages) {
2135
		nrpages = min(last_offset - i, BIO_MAX_PAGES);
2136

A
arter97 已提交
2137
		/* readahead node pages */
2138
		ra_meta_pages(sbi, addr, nrpages, META_POR, true);
J
Jaegeuk Kim 已提交
2139

2140
		for (idx = addr; idx < addr + nrpages; idx++) {
2141
			struct page *page = get_tmp_page(sbi, idx);
2142

2143 2144 2145 2146 2147 2148
			rn = F2FS_NODE(page);
			sum_entry->nid = rn->footer.nid;
			sum_entry->version = 0;
			sum_entry->ofs_in_node = 0;
			sum_entry++;
			f2fs_put_page(page, 1);
2149
		}
2150

2151
		invalidate_mapping_pages(META_MAPPING(sbi), addr,
2152
							addr + nrpages);
J
Jaegeuk Kim 已提交
2153
	}
2154
	return 0;
J
Jaegeuk Kim 已提交
2155 2156
}

2157
static void remove_nats_in_journal(struct f2fs_sb_info *sbi)
J
Jaegeuk Kim 已提交
2158 2159 2160
{
	struct f2fs_nm_info *nm_i = NM_I(sbi);
	struct curseg_info *curseg = CURSEG_I(sbi, CURSEG_HOT_DATA);
2161
	struct f2fs_journal *journal = curseg->journal;
J
Jaegeuk Kim 已提交
2162 2163
	int i;

2164
	down_write(&curseg->journal_rwsem);
2165
	for (i = 0; i < nats_in_cursum(journal); i++) {
J
Jaegeuk Kim 已提交
2166 2167
		struct nat_entry *ne;
		struct f2fs_nat_entry raw_ne;
2168
		nid_t nid = le32_to_cpu(nid_in_journal(journal, i));
J
Jaegeuk Kim 已提交
2169

2170
		raw_ne = nat_in_journal(journal, i);
2171

J
Jaegeuk Kim 已提交
2172 2173
		ne = __lookup_nat_cache(nm_i, nid);
		if (!ne) {
2174
			ne = grab_nat_entry(nm_i, nid, true);
2175
			node_info_from_raw_nat(&ne->ni, &raw_ne);
J
Jaegeuk Kim 已提交
2176
		}
2177 2178 2179 2180 2181 2182 2183 2184 2185 2186 2187 2188 2189

		/*
		 * if a free nat in journal has not been used after last
		 * checkpoint, we should remove it from available nids,
		 * since later we will add it again.
		 */
		if (!get_nat_flag(ne, IS_DIRTY) &&
				le32_to_cpu(raw_ne.block_addr) == NULL_ADDR) {
			spin_lock(&nm_i->nid_list_lock);
			nm_i->available_nids--;
			spin_unlock(&nm_i->nid_list_lock);
		}

J
Jaegeuk Kim 已提交
2190 2191
		__set_nat_cache_dirty(nm_i, ne);
	}
2192
	update_nats_in_cursum(journal, -i);
2193
	up_write(&curseg->journal_rwsem);
J
Jaegeuk Kim 已提交
2194 2195
}

2196 2197
static void __adjust_nat_entry_set(struct nat_entry_set *nes,
						struct list_head *head, int max)
J
Jaegeuk Kim 已提交
2198
{
2199
	struct nat_entry_set *cur;
J
Jaegeuk Kim 已提交
2200

2201 2202
	if (nes->entry_cnt >= max)
		goto add_out;
J
Jaegeuk Kim 已提交
2203

2204 2205 2206 2207 2208
	list_for_each_entry(cur, head, set_list) {
		if (cur->entry_cnt >= nes->entry_cnt) {
			list_add(&nes->set_list, cur->set_list.prev);
			return;
		}
2209
	}
2210 2211 2212
add_out:
	list_add_tail(&nes->set_list, head);
}
J
Jaegeuk Kim 已提交
2213

2214 2215 2216 2217
static void __flush_nat_entry_set(struct f2fs_sb_info *sbi,
					struct nat_entry_set *set)
{
	struct curseg_info *curseg = CURSEG_I(sbi, CURSEG_HOT_DATA);
2218
	struct f2fs_journal *journal = curseg->journal;
2219 2220 2221 2222 2223
	nid_t start_nid = set->set * NAT_ENTRY_PER_BLOCK;
	bool to_journal = true;
	struct f2fs_nat_block *nat_blk;
	struct nat_entry *ne, *cur;
	struct page *page = NULL;
J
Jaegeuk Kim 已提交
2224

2225 2226 2227 2228 2229
	/*
	 * there are two steps to flush nat entries:
	 * #1, flush nat entries to journal in current hot data summary block.
	 * #2, flush nat entries to nat page.
	 */
2230
	if (!__has_cursum_space(journal, set->entry_cnt, NAT_JOURNAL))
2231 2232 2233
		to_journal = false;

	if (to_journal) {
2234
		down_write(&curseg->journal_rwsem);
2235 2236 2237 2238 2239
	} else {
		page = get_next_nat_page(sbi, start_nid);
		nat_blk = page_address(page);
		f2fs_bug_on(sbi, !nat_blk);
	}
2240

2241 2242 2243 2244 2245 2246 2247 2248
	/* flush dirty nats in nat entry set */
	list_for_each_entry_safe(ne, cur, &set->entry_list, list) {
		struct f2fs_nat_entry *raw_ne;
		nid_t nid = nat_get_nid(ne);
		int offset;

		if (nat_get_blkaddr(ne) == NEW_ADDR)
			continue;
2249 2250

		if (to_journal) {
2251
			offset = lookup_journal_in_cursum(journal,
2252 2253
							NAT_JOURNAL, nid, 1);
			f2fs_bug_on(sbi, offset < 0);
2254 2255
			raw_ne = &nat_in_journal(journal, offset);
			nid_in_journal(journal, offset) = cpu_to_le32(nid);
2256
		} else {
2257
			raw_ne = &nat_blk->entries[nid - start_nid];
J
Jaegeuk Kim 已提交
2258
		}
2259 2260 2261
		raw_nat_from_node_info(raw_ne, &ne->ni);
		nat_reset_flag(ne);
		__clear_nat_cache_dirty(NM_I(sbi), ne);
2262
		if (nat_get_blkaddr(ne) == NULL_ADDR) {
2263
			add_free_nid(sbi, nid, false);
2264 2265 2266 2267
			spin_lock(&NM_I(sbi)->nid_list_lock);
			NM_I(sbi)->available_nids++;
			spin_unlock(&NM_I(sbi)->nid_list_lock);
		}
2268
	}
J
Jaegeuk Kim 已提交
2269

2270
	if (to_journal)
2271
		up_write(&curseg->journal_rwsem);
2272 2273
	else
		f2fs_put_page(page, 1);
2274

2275 2276 2277 2278
	f2fs_bug_on(sbi, set->entry_cnt);

	radix_tree_delete(&NM_I(sbi)->nat_set_root, set->set);
	kmem_cache_free(nat_entry_set_slab, set);
2279
}
2280

2281 2282 2283 2284 2285 2286 2287
/*
 * This function is called during the checkpointing process.
 */
void flush_nat_entries(struct f2fs_sb_info *sbi)
{
	struct f2fs_nm_info *nm_i = NM_I(sbi);
	struct curseg_info *curseg = CURSEG_I(sbi, CURSEG_HOT_DATA);
2288
	struct f2fs_journal *journal = curseg->journal;
2289
	struct nat_entry_set *setvec[SETVEC_SIZE];
2290 2291 2292 2293 2294
	struct nat_entry_set *set, *tmp;
	unsigned int found;
	nid_t set_idx = 0;
	LIST_HEAD(sets);

2295 2296
	if (!nm_i->dirty_nat_cnt)
		return;
2297

2298
	down_write(&nm_i->nat_tree_lock);
2299

2300 2301 2302 2303 2304
	/*
	 * if there are no enough space in journal to store dirty nat
	 * entries, remove all entries from journal and merge them
	 * into nat entry set.
	 */
2305
	if (!__has_cursum_space(journal, nm_i->dirty_nat_cnt, NAT_JOURNAL))
2306 2307 2308
		remove_nats_in_journal(sbi);

	while ((found = __gang_lookup_nat_set(nm_i,
2309
					set_idx, SETVEC_SIZE, setvec))) {
2310 2311 2312 2313
		unsigned idx;
		set_idx = setvec[found - 1]->set + 1;
		for (idx = 0; idx < found; idx++)
			__adjust_nat_entry_set(setvec[idx], &sets,
2314
						MAX_NAT_JENTRIES(journal));
J
Jaegeuk Kim 已提交
2315
	}
2316

2317 2318 2319 2320
	/* flush dirty nats in nat entry set */
	list_for_each_entry_safe(set, tmp, &sets, set_list)
		__flush_nat_entry_set(sbi, set);

2321
	up_write(&nm_i->nat_tree_lock);
2322

2323
	f2fs_bug_on(sbi, nm_i->dirty_nat_cnt);
J
Jaegeuk Kim 已提交
2324 2325 2326 2327 2328 2329 2330 2331 2332 2333 2334 2335 2336 2337
}

static int init_node_manager(struct f2fs_sb_info *sbi)
{
	struct f2fs_super_block *sb_raw = F2FS_RAW_SUPER(sbi);
	struct f2fs_nm_info *nm_i = NM_I(sbi);
	unsigned char *version_bitmap;
	unsigned int nat_segs, nat_blocks;

	nm_i->nat_blkaddr = le32_to_cpu(sb_raw->nat_blkaddr);

	/* segment_count_nat includes pair segment so divide to 2. */
	nat_segs = le32_to_cpu(sb_raw->segment_count_nat) >> 1;
	nat_blocks = nat_segs << le32_to_cpu(sb_raw->log_blocks_per_seg);
2338

2339 2340
	nm_i->max_nid = NAT_ENTRY_PER_BLOCK * nat_blocks;

2341
	/* not used nids: 0, node, meta, (and root counted as valid node) */
2342 2343
	nm_i->available_nids = nm_i->max_nid - sbi->total_valid_node_count -
							F2FS_RESERVED_NODE_NUM;
C
Chao Yu 已提交
2344 2345
	nm_i->nid_cnt[FREE_NID_LIST] = 0;
	nm_i->nid_cnt[ALLOC_NID_LIST] = 0;
J
Jaegeuk Kim 已提交
2346
	nm_i->nat_cnt = 0;
2347
	nm_i->ram_thresh = DEF_RAM_THRESHOLD;
C
Chao Yu 已提交
2348
	nm_i->ra_nid_pages = DEF_RA_NID_PAGES;
C
Chao Yu 已提交
2349
	nm_i->dirty_nats_ratio = DEF_DIRTY_NAT_RATIO_THRESHOLD;
J
Jaegeuk Kim 已提交
2350

2351
	INIT_RADIX_TREE(&nm_i->free_nid_root, GFP_ATOMIC);
C
Chao Yu 已提交
2352 2353
	INIT_LIST_HEAD(&nm_i->nid_list[FREE_NID_LIST]);
	INIT_LIST_HEAD(&nm_i->nid_list[ALLOC_NID_LIST]);
2354 2355
	INIT_RADIX_TREE(&nm_i->nat_root, GFP_NOIO);
	INIT_RADIX_TREE(&nm_i->nat_set_root, GFP_NOIO);
J
Jaegeuk Kim 已提交
2356 2357 2358
	INIT_LIST_HEAD(&nm_i->nat_entries);

	mutex_init(&nm_i->build_lock);
C
Chao Yu 已提交
2359
	spin_lock_init(&nm_i->nid_list_lock);
2360
	init_rwsem(&nm_i->nat_tree_lock);
J
Jaegeuk Kim 已提交
2361 2362

	nm_i->next_scan_nid = le32_to_cpu(sbi->ckpt->next_free_nid);
A
Alexandru Gheorghiu 已提交
2363
	nm_i->bitmap_size = __bitmap_size(sbi, NAT_BITMAP);
J
Jaegeuk Kim 已提交
2364 2365 2366 2367
	version_bitmap = __bitmap_ptr(sbi, NAT_BITMAP);
	if (!version_bitmap)
		return -EFAULT;

A
Alexandru Gheorghiu 已提交
2368 2369 2370 2371
	nm_i->nat_bitmap = kmemdup(version_bitmap, nm_i->bitmap_size,
					GFP_KERNEL);
	if (!nm_i->nat_bitmap)
		return -ENOMEM;
2372 2373 2374 2375 2376 2377 2378 2379

#ifdef CONFIG_F2FS_CHECK_FS
	nm_i->nat_bitmap_mir = kmemdup(version_bitmap, nm_i->bitmap_size,
					GFP_KERNEL);
	if (!nm_i->nat_bitmap_mir)
		return -ENOMEM;
#endif

J
Jaegeuk Kim 已提交
2380 2381 2382 2383 2384 2385 2386 2387 2388 2389 2390 2391 2392 2393 2394
	return 0;
}

int build_node_manager(struct f2fs_sb_info *sbi)
{
	int err;

	sbi->nm_info = kzalloc(sizeof(struct f2fs_nm_info), GFP_KERNEL);
	if (!sbi->nm_info)
		return -ENOMEM;

	err = init_node_manager(sbi);
	if (err)
		return err;

2395
	build_free_nids(sbi, true);
J
Jaegeuk Kim 已提交
2396 2397 2398 2399 2400 2401 2402 2403
	return 0;
}

void destroy_node_manager(struct f2fs_sb_info *sbi)
{
	struct f2fs_nm_info *nm_i = NM_I(sbi);
	struct free_nid *i, *next_i;
	struct nat_entry *natvec[NATVEC_SIZE];
2404
	struct nat_entry_set *setvec[SETVEC_SIZE];
J
Jaegeuk Kim 已提交
2405 2406 2407 2408 2409 2410 2411
	nid_t nid = 0;
	unsigned int found;

	if (!nm_i)
		return;

	/* destroy free nid list */
C
Chao Yu 已提交
2412 2413 2414
	spin_lock(&nm_i->nid_list_lock);
	list_for_each_entry_safe(i, next_i, &nm_i->nid_list[FREE_NID_LIST],
									list) {
2415
		__remove_nid_from_list(sbi, i, FREE_NID_LIST, false);
C
Chao Yu 已提交
2416
		spin_unlock(&nm_i->nid_list_lock);
2417
		kmem_cache_free(free_nid_slab, i);
C
Chao Yu 已提交
2418
		spin_lock(&nm_i->nid_list_lock);
J
Jaegeuk Kim 已提交
2419
	}
C
Chao Yu 已提交
2420 2421 2422 2423
	f2fs_bug_on(sbi, nm_i->nid_cnt[FREE_NID_LIST]);
	f2fs_bug_on(sbi, nm_i->nid_cnt[ALLOC_NID_LIST]);
	f2fs_bug_on(sbi, !list_empty(&nm_i->nid_list[ALLOC_NID_LIST]));
	spin_unlock(&nm_i->nid_list_lock);
J
Jaegeuk Kim 已提交
2424 2425

	/* destroy nat cache */
2426
	down_write(&nm_i->nat_tree_lock);
J
Jaegeuk Kim 已提交
2427 2428 2429
	while ((found = __gang_lookup_nat_cache(nm_i,
					nid, NATVEC_SIZE, natvec))) {
		unsigned idx;
2430

2431 2432 2433
		nid = nat_get_nid(natvec[found - 1]) + 1;
		for (idx = 0; idx < found; idx++)
			__del_from_nat_cache(nm_i, natvec[idx]);
J
Jaegeuk Kim 已提交
2434
	}
2435
	f2fs_bug_on(sbi, nm_i->nat_cnt);
2436 2437 2438 2439 2440 2441 2442 2443 2444 2445 2446 2447 2448 2449 2450

	/* destroy nat set cache */
	nid = 0;
	while ((found = __gang_lookup_nat_set(nm_i,
					nid, SETVEC_SIZE, setvec))) {
		unsigned idx;

		nid = setvec[found - 1]->set + 1;
		for (idx = 0; idx < found; idx++) {
			/* entry_cnt is not zero, when cp_error was occurred */
			f2fs_bug_on(sbi, !list_empty(&setvec[idx]->entry_list));
			radix_tree_delete(&nm_i->nat_set_root, setvec[idx]->set);
			kmem_cache_free(nat_entry_set_slab, setvec[idx]);
		}
	}
2451
	up_write(&nm_i->nat_tree_lock);
J
Jaegeuk Kim 已提交
2452 2453

	kfree(nm_i->nat_bitmap);
2454 2455 2456
#ifdef CONFIG_F2FS_CHECK_FS
	kfree(nm_i->nat_bitmap_mir);
#endif
J
Jaegeuk Kim 已提交
2457 2458 2459 2460
	sbi->nm_info = NULL;
	kfree(nm_i);
}

2461
int __init create_node_manager_caches(void)
J
Jaegeuk Kim 已提交
2462 2463
{
	nat_entry_slab = f2fs_kmem_cache_create("nat_entry",
2464
			sizeof(struct nat_entry));
J
Jaegeuk Kim 已提交
2465
	if (!nat_entry_slab)
2466
		goto fail;
J
Jaegeuk Kim 已提交
2467 2468

	free_nid_slab = f2fs_kmem_cache_create("free_nid",
2469
			sizeof(struct free_nid));
2470
	if (!free_nid_slab)
2471
		goto destroy_nat_entry;
2472 2473 2474 2475

	nat_entry_set_slab = f2fs_kmem_cache_create("nat_entry_set",
			sizeof(struct nat_entry_set));
	if (!nat_entry_set_slab)
2476
		goto destroy_free_nid;
J
Jaegeuk Kim 已提交
2477
	return 0;
2478

2479
destroy_free_nid:
2480
	kmem_cache_destroy(free_nid_slab);
2481
destroy_nat_entry:
2482 2483 2484
	kmem_cache_destroy(nat_entry_slab);
fail:
	return -ENOMEM;
J
Jaegeuk Kim 已提交
2485 2486 2487 2488
}

void destroy_node_manager_caches(void)
{
2489
	kmem_cache_destroy(nat_entry_set_slab);
J
Jaegeuk Kim 已提交
2490 2491 2492
	kmem_cache_destroy(free_nid_slab);
	kmem_cache_destroy(nat_entry_slab);
}