node.c 50.2 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"
22
#include <trace/events/f2fs.h>
J
Jaegeuk Kim 已提交
23

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

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

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

	si_meminfo(&val);
39 40 41 42 43

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

	/* give 25%, 25%, 50%, 50% memory for each components respectively */
44
	if (type == FREE_NIDS) {
45 46 47
		mem_size = (nm_i->fcnt * sizeof(struct free_nid)) >>
							PAGE_CACHE_SHIFT;
		res = mem_size < ((avail_ram * nm_i->ram_thresh / 100) >> 2);
48
	} else if (type == NAT_ENTRIES) {
49 50 51
		mem_size = (nm_i->nat_cnt * sizeof(struct nat_entry)) >>
							PAGE_CACHE_SHIFT;
		res = mem_size < ((avail_ram * nm_i->ram_thresh / 100) >> 2);
52
	} else if (type == DIRTY_DENTS) {
53 54
		if (sbi->sb->s_bdi->dirty_exceeded)
			return false;
55
		mem_size = get_pages(sbi, F2FS_DIRTY_DENTS);
56 57 58 59 60 61 62
		res = mem_size < ((avail_ram * nm_i->ram_thresh / 100) >> 1);
	} else if (type == INO_ENTRIES) {
		int i;

		if (sbi->sb->s_bdi->dirty_exceeded)
			return false;
		for (i = 0; i <= UPDATE_INO; i++)
63 64
			mem_size += (sbi->im[i].ino_num *
				sizeof(struct ino_entry)) >> PAGE_CACHE_SHIFT;
65
		res = mem_size < ((avail_ram * nm_i->ram_thresh / 100) >> 1);
66 67
	}
	return res;
68 69
}

J
Jaegeuk Kim 已提交
70 71 72 73 74 75 76 77 78 79 80 81 82
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);
83
		dec_page_count(F2FS_M_SB(mapping), F2FS_DIRTY_NODES);
J
Jaegeuk Kim 已提交
84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109
	}
	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);
110
	f2fs_bug_on(sbi, PageDirty(src_page));
J
Jaegeuk Kim 已提交
111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141

	src_addr = page_address(src_page);
	dst_addr = page_address(dst_page);
	memcpy(dst_addr, src_addr, PAGE_CACHE_SIZE);
	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);
}

142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192
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;
retry:
	head = radix_tree_lookup(&nm_i->nat_set_root, set);
	if (!head) {
		head = f2fs_kmem_cache_alloc(nat_entry_set_slab, GFP_ATOMIC);

		INIT_LIST_HEAD(&head->entry_list);
		INIT_LIST_HEAD(&head->set_list);
		head->set = set;
		head->entry_cnt = 0;

		if (radix_tree_insert(&nm_i->nat_set_root, set, head)) {
			cond_resched();
			goto retry;
		}
	}
	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)
{
	nid_t set = ne->ni.nid / NAT_ENTRY_PER_BLOCK;
	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);
}

193
bool is_checkpointed_node(struct f2fs_sb_info *sbi, nid_t nid)
J
Jaegeuk Kim 已提交
194 195 196
{
	struct f2fs_nm_info *nm_i = NM_I(sbi);
	struct nat_entry *e;
197
	bool is_cp = true;
J
Jaegeuk Kim 已提交
198 199 200

	read_lock(&nm_i->nat_tree_lock);
	e = __lookup_nat_cache(nm_i, nid);
201
	if (e && !get_nat_flag(e, IS_CHECKPOINTED))
202
		is_cp = false;
J
Jaegeuk Kim 已提交
203 204 205 206
	read_unlock(&nm_i->nat_tree_lock);
	return is_cp;
}

207
bool has_fsynced_inode(struct f2fs_sb_info *sbi, nid_t ino)
208 209 210
{
	struct f2fs_nm_info *nm_i = NM_I(sbi);
	struct nat_entry *e;
211
	bool fsynced = false;
212 213

	read_lock(&nm_i->nat_tree_lock);
214 215 216
	e = __lookup_nat_cache(nm_i, ino);
	if (e && get_nat_flag(e, HAS_FSYNCED_INODE))
		fsynced = true;
217
	read_unlock(&nm_i->nat_tree_lock);
218
	return fsynced;
219 220
}

221
bool need_inode_block_update(struct f2fs_sb_info *sbi, nid_t ino)
222 223 224
{
	struct f2fs_nm_info *nm_i = NM_I(sbi);
	struct nat_entry *e;
225
	bool need_update = true;
226

227 228 229 230 231 232 233 234
	read_lock(&nm_i->nat_tree_lock);
	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;
	read_unlock(&nm_i->nat_tree_lock);
	return need_update;
235 236
}

J
Jaegeuk Kim 已提交
237 238 239 240 241 242 243 244 245 246 247 248 249
static struct nat_entry *grab_nat_entry(struct f2fs_nm_info *nm_i, nid_t nid)
{
	struct nat_entry *new;

	new = kmem_cache_alloc(nat_entry_slab, GFP_ATOMIC);
	if (!new)
		return NULL;
	if (radix_tree_insert(&nm_i->nat_root, nid, new)) {
		kmem_cache_free(nat_entry_slab, new);
		return NULL;
	}
	memset(new, 0, sizeof(struct nat_entry));
	nat_set_nid(new, nid);
250
	nat_reset_flag(new);
J
Jaegeuk Kim 已提交
251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268
	list_add_tail(&new->list, &nm_i->nat_entries);
	nm_i->nat_cnt++;
	return new;
}

static void cache_nat_entry(struct f2fs_nm_info *nm_i, nid_t nid,
						struct f2fs_nat_entry *ne)
{
	struct nat_entry *e;
retry:
	write_lock(&nm_i->nat_tree_lock);
	e = __lookup_nat_cache(nm_i, nid);
	if (!e) {
		e = grab_nat_entry(nm_i, nid);
		if (!e) {
			write_unlock(&nm_i->nat_tree_lock);
			goto retry;
		}
269
		node_info_from_raw_nat(&e->ni, ne);
J
Jaegeuk Kim 已提交
270 271 272 273 274
	}
	write_unlock(&nm_i->nat_tree_lock);
}

static void set_node_addr(struct f2fs_sb_info *sbi, struct node_info *ni,
275
			block_t new_blkaddr, bool fsync_done)
J
Jaegeuk Kim 已提交
276 277 278 279 280 281 282 283 284 285 286 287 288
{
	struct f2fs_nm_info *nm_i = NM_I(sbi);
	struct nat_entry *e;
retry:
	write_lock(&nm_i->nat_tree_lock);
	e = __lookup_nat_cache(nm_i, ni->nid);
	if (!e) {
		e = grab_nat_entry(nm_i, ni->nid);
		if (!e) {
			write_unlock(&nm_i->nat_tree_lock);
			goto retry;
		}
		e->ni = *ni;
289
		f2fs_bug_on(sbi, ni->blk_addr == NEW_ADDR);
J
Jaegeuk Kim 已提交
290 291 292 293 294 295 296
	} 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.
		 */
		e->ni = *ni;
297
		f2fs_bug_on(sbi, ni->blk_addr != NULL_ADDR);
J
Jaegeuk Kim 已提交
298 299 300
	}

	/* sanity check */
301 302
	f2fs_bug_on(sbi, nat_get_blkaddr(e) != ni->blk_addr);
	f2fs_bug_on(sbi, nat_get_blkaddr(e) == NULL_ADDR &&
J
Jaegeuk Kim 已提交
303
			new_blkaddr == NULL_ADDR);
304
	f2fs_bug_on(sbi, nat_get_blkaddr(e) == NEW_ADDR &&
J
Jaegeuk Kim 已提交
305
			new_blkaddr == NEW_ADDR);
306
	f2fs_bug_on(sbi, nat_get_blkaddr(e) != NEW_ADDR &&
J
Jaegeuk Kim 已提交
307 308 309
			nat_get_blkaddr(e) != NULL_ADDR &&
			new_blkaddr == NEW_ADDR);

A
arter97 已提交
310
	/* increment version no as node is removed */
J
Jaegeuk Kim 已提交
311 312 313 314 315 316 317
	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));
	}

	/* change address */
	nat_set_blkaddr(e, new_blkaddr);
318 319
	if (new_blkaddr == NEW_ADDR || new_blkaddr == NULL_ADDR)
		set_nat_flag(e, IS_CHECKPOINTED, false);
J
Jaegeuk Kim 已提交
320
	__set_nat_cache_dirty(nm_i, e);
321 322 323

	/* update fsync_mark if its inode nat entry is still alive */
	e = __lookup_nat_cache(nm_i, ni->ino);
324 325 326 327 328
	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);
	}
J
Jaegeuk Kim 已提交
329 330 331
	write_unlock(&nm_i->nat_tree_lock);
}

332
int try_to_free_nats(struct f2fs_sb_info *sbi, int nr_shrink)
J
Jaegeuk Kim 已提交
333 334 335
{
	struct f2fs_nm_info *nm_i = NM_I(sbi);

336
	if (available_free_memory(sbi, NAT_ENTRIES))
J
Jaegeuk Kim 已提交
337 338 339 340 341 342 343 344 345 346 347 348 349 350
		return 0;

	write_lock(&nm_i->nat_tree_lock);
	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--;
	}
	write_unlock(&nm_i->nat_tree_lock);
	return nr_shrink;
}

J
Jaegeuk Kim 已提交
351
/*
A
arter97 已提交
352
 * This function always returns success
J
Jaegeuk Kim 已提交
353 354 355 356 357 358 359 360 361 362 363 364 365
 */
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);
	struct f2fs_summary_block *sum = curseg->sum_blk;
	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;

366
	memset(&ne, 0, sizeof(struct f2fs_nat_entry));
J
Jaegeuk Kim 已提交
367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402
	ni->nid = nid;

	/* Check nat cache */
	read_lock(&nm_i->nat_tree_lock);
	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);
	}
	read_unlock(&nm_i->nat_tree_lock);
	if (e)
		return;

	/* Check current segment summary */
	mutex_lock(&curseg->curseg_mutex);
	i = lookup_journal_in_cursum(sum, NAT_JOURNAL, nid, 0);
	if (i >= 0) {
		ne = nat_in_journal(sum, i);
		node_info_from_raw_nat(ni, &ne);
	}
	mutex_unlock(&curseg->curseg_mutex);
	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:
	/* cache nat entry */
	cache_nat_entry(NM_I(sbi), nid, &ne);
}

J
Jaegeuk Kim 已提交
403
/*
J
Jaegeuk Kim 已提交
404 405 406
 * The maximum depth is four.
 * Offset[0] will have raw inode offset.
 */
407 408
static int get_node_path(struct f2fs_inode_info *fi, long block,
				int offset[4], unsigned int noffset[4])
J
Jaegeuk Kim 已提交
409
{
410
	const long direct_index = ADDRS_PER_INODE(fi);
J
Jaegeuk Kim 已提交
411 412 413 414 415 416 417 418 419 420
	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) {
421
		offset[n] = block;
J
Jaegeuk Kim 已提交
422 423 424 425 426 427
		goto got;
	}
	block -= direct_index;
	if (block < direct_blks) {
		offset[n++] = NODE_DIR1_BLOCK;
		noffset[n] = 1;
428
		offset[n] = block;
J
Jaegeuk Kim 已提交
429 430 431 432 433 434 435
		level = 1;
		goto got;
	}
	block -= direct_blks;
	if (block < direct_blks) {
		offset[n++] = NODE_DIR2_BLOCK;
		noffset[n] = 2;
436
		offset[n] = block;
J
Jaegeuk Kim 已提交
437 438 439 440 441 442 443 444 445
		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];
446
		offset[n] = block % direct_blks;
J
Jaegeuk Kim 已提交
447 448 449 450 451 452 453 454 455
		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];
456
		offset[n] = block % direct_blks;
J
Jaegeuk Kim 已提交
457 458 459 460 461 462 463 464 465 466 467 468 469 470
		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];
471
		offset[n] = block % direct_blks;
J
Jaegeuk Kim 已提交
472 473 474 475 476 477 478 479 480 481 482
		level = 3;
		goto got;
	} else {
		BUG();
	}
got:
	return level;
}

/*
 * Caller should call f2fs_put_dnode(dn).
C
Chao Yu 已提交
483 484
 * 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.
485
 * In the case of RDONLY_NODE, we don't need to care about mutex.
J
Jaegeuk Kim 已提交
486
 */
487
int get_dnode_of_data(struct dnode_of_data *dn, pgoff_t index, int mode)
J
Jaegeuk Kim 已提交
488
{
489
	struct f2fs_sb_info *sbi = F2FS_I_SB(dn->inode);
J
Jaegeuk Kim 已提交
490 491 492 493 494 495 496 497
	struct page *npage[4];
	struct page *parent;
	int offset[4];
	unsigned int noffset[4];
	nid_t nids[4];
	int level, i;
	int err = 0;

498
	level = get_node_path(F2FS_I(dn->inode), index, offset, noffset);
J
Jaegeuk Kim 已提交
499 500

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

503 504 505 506 507
	if (!npage[0]) {
		npage[0] = get_node_page(sbi, nids[0]);
		if (IS_ERR(npage[0]))
			return PTR_ERR(npage[0]);
	}
J
Jaegeuk Kim 已提交
508
	parent = npage[0];
509 510
	if (level != 0)
		nids[1] = get_nid(parent, offset[0], true);
J
Jaegeuk Kim 已提交
511 512 513 514 515 516 517
	dn->inode_page = npage[0];
	dn->inode_page_locked = true;

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

518
		if (!nids[i] && mode == ALLOC_NODE) {
J
Jaegeuk Kim 已提交
519 520 521 522 523 524 525
			/* alloc new node */
			if (!alloc_nid(sbi, &(nids[i]))) {
				err = -ENOSPC;
				goto release_pages;
			}

			dn->nid = nids[i];
526
			npage[i] = new_node_page(dn, noffset[i], NULL);
J
Jaegeuk Kim 已提交
527 528 529 530 531 532 533 534 535
			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;
536
		} else if (mode == LOOKUP_NODE_RA && i == level && level > 1) {
J
Jaegeuk Kim 已提交
537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581
			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;
	return err;
}

static void truncate_node(struct dnode_of_data *dn)
{
582
	struct f2fs_sb_info *sbi = F2FS_I_SB(dn->inode);
J
Jaegeuk Kim 已提交
583 584 585
	struct node_info ni;

	get_node_info(sbi, dn->nid, &ni);
586
	if (dn->inode->i_blocks == 0) {
587
		f2fs_bug_on(sbi, ni.blk_addr != NULL_ADDR);
588 589
		goto invalidate;
	}
590
	f2fs_bug_on(sbi, ni.blk_addr == NULL_ADDR);
J
Jaegeuk Kim 已提交
591 592

	/* Deallocate node address */
593
	invalidate_blocks(sbi, ni.blk_addr);
594
	dec_valid_node_count(sbi, dn->inode);
595
	set_node_addr(sbi, &ni, NULL_ADDR, false);
J
Jaegeuk Kim 已提交
596 597 598 599 600 601 602

	if (dn->nid == dn->inode->i_ino) {
		remove_orphan_inode(sbi, dn->nid);
		dec_valid_inode_count(sbi);
	} else {
		sync_inode_page(dn);
	}
603
invalidate:
J
Jaegeuk Kim 已提交
604 605 606 607
	clear_node_page_dirty(dn->node_page);
	F2FS_SET_SB_DIRT(sbi);

	f2fs_put_page(dn->node_page, 1);
608 609 610 611

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

J
Jaegeuk Kim 已提交
612
	dn->node_page = NULL;
613
	trace_f2fs_truncate_node(dn->inode, dn->nid, ni.blk_addr);
J
Jaegeuk Kim 已提交
614 615 616 617 618 619 620 621 622 623
}

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

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

	/* get direct node */
624
	page = get_node_page(F2FS_I_SB(dn->inode), dn->nid);
J
Jaegeuk Kim 已提交
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
	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;

652 653
	trace_f2fs_truncate_nodes_enter(dn->inode, dn->nid, dn->data_blkaddr);

654
	page = get_node_page(F2FS_I_SB(dn->inode), dn->nid);
655 656
	if (IS_ERR(page)) {
		trace_f2fs_truncate_nodes_exit(dn->inode, PTR_ERR(page));
J
Jaegeuk Kim 已提交
657
		return PTR_ERR(page);
658
	}
J
Jaegeuk Kim 已提交
659

660
	rn = F2FS_NODE(page);
J
Jaegeuk Kim 已提交
661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699
	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;
			set_nid(page, i, 0, false);
		}
	} 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)) {
				set_nid(page, i, 0, false);
				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);
	}
700
	trace_f2fs_truncate_nodes_exit(dn->inode, freed);
J
Jaegeuk Kim 已提交
701 702 703 704
	return freed;

out_err:
	f2fs_put_page(page, 1);
705
	trace_f2fs_truncate_nodes_exit(dn->inode, ret);
J
Jaegeuk Kim 已提交
706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723
	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 */
724
	for (i = 0; i < idx + 1; i++) {
A
arter97 已提交
725
		/* reference count'll be increased */
726
		pages[i] = get_node_page(F2FS_I_SB(dn->inode), nid[i]);
J
Jaegeuk Kim 已提交
727 728
		if (IS_ERR(pages[i])) {
			err = PTR_ERR(pages[i]);
729
			idx = i - 1;
J
Jaegeuk Kim 已提交
730 731 732 733 734 735
			goto fail;
		}
		nid[i + 1] = get_nid(pages[i], offset[i + 1], false);
	}

	/* free direct nodes linked to a partial indirect node */
736
	for (i = offset[idx + 1]; i < NIDS_PER_BLOCK; i++) {
J
Jaegeuk Kim 已提交
737 738 739 740 741 742 743 744 745 746
		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;
		set_nid(pages[idx], i, 0, false);
	}

747
	if (offset[idx + 1] == 0) {
J
Jaegeuk Kim 已提交
748 749 750 751 752 753 754
		dn->node_page = pages[idx];
		dn->nid = nid[idx];
		truncate_node(dn);
	} else {
		f2fs_put_page(pages[idx], 1);
	}
	offset[idx]++;
755 756
	offset[idx + 1] = 0;
	idx--;
J
Jaegeuk Kim 已提交
757
fail:
758
	for (i = idx; i >= 0; i--)
J
Jaegeuk Kim 已提交
759
		f2fs_put_page(pages[i], 1);
760 761 762

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

J
Jaegeuk Kim 已提交
763 764 765
	return err;
}

J
Jaegeuk Kim 已提交
766
/*
J
Jaegeuk Kim 已提交
767 768 769 770
 * All the block addresses of data and nodes should be nullified.
 */
int truncate_inode_blocks(struct inode *inode, pgoff_t from)
{
771
	struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
J
Jaegeuk Kim 已提交
772 773
	int err = 0, cont = 1;
	int level, offset[4], noffset[4];
J
Jaegeuk Kim 已提交
774
	unsigned int nofs = 0;
775
	struct f2fs_inode *ri;
J
Jaegeuk Kim 已提交
776 777 778
	struct dnode_of_data dn;
	struct page *page;

779 780
	trace_f2fs_truncate_inode_blocks_enter(inode, from);

781
	level = get_node_path(F2FS_I(inode), from, offset, noffset);
782
restart:
J
Jaegeuk Kim 已提交
783
	page = get_node_page(sbi, inode->i_ino);
784 785
	if (IS_ERR(page)) {
		trace_f2fs_truncate_inode_blocks_exit(inode, PTR_ERR(page));
J
Jaegeuk Kim 已提交
786
		return PTR_ERR(page);
787
	}
J
Jaegeuk Kim 已提交
788 789 790 791

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

792
	ri = F2FS_INODE(page);
J
Jaegeuk Kim 已提交
793 794 795 796 797 798 799 800 801
	switch (level) {
	case 0:
	case 1:
		nofs = noffset[1];
		break;
	case 2:
		nofs = noffset[1];
		if (!offset[level - 1])
			goto skip_partial;
802
		err = truncate_partial_nodes(&dn, ri, offset, level);
J
Jaegeuk Kim 已提交
803 804 805 806 807 808 809 810
		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;
811
		err = truncate_partial_nodes(&dn, ri, offset, level);
J
Jaegeuk Kim 已提交
812 813 814 815 816 817 818 819 820
		if (err < 0 && err != -ENOENT)
			goto fail;
		break;
	default:
		BUG();
	}

skip_partial:
	while (cont) {
821
		dn.nid = le32_to_cpu(ri->i_nid[offset[0] - NODE_DIR1_BLOCK]);
J
Jaegeuk Kim 已提交
822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843
		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 &&
844
				ri->i_nid[offset[0] - NODE_DIR1_BLOCK]) {
J
Jaegeuk Kim 已提交
845
			lock_page(page);
846
			if (unlikely(page->mapping != NODE_MAPPING(sbi))) {
847 848 849
				f2fs_put_page(page, 1);
				goto restart;
			}
850
			f2fs_wait_on_page_writeback(page, NODE);
851
			ri->i_nid[offset[0] - NODE_DIR1_BLOCK] = 0;
J
Jaegeuk Kim 已提交
852 853 854 855 856 857 858 859 860
			set_page_dirty(page);
			unlock_page(page);
		}
		offset[1] = 0;
		offset[0]++;
		nofs += err;
	}
fail:
	f2fs_put_page(page, 0);
861
	trace_f2fs_truncate_inode_blocks_exit(inode, err);
J
Jaegeuk Kim 已提交
862 863 864
	return err > 0 ? 0 : err;
}

865 866
int truncate_xattr_node(struct inode *inode, struct page *page)
{
867
	struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
868 869 870 871 872 873 874 875 876 877 878 879
	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);

	F2FS_I(inode)->i_xattr_nid = 0;
J
Jaegeuk Kim 已提交
880 881 882 883

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

884 885 886
	set_new_dnode(&dn, inode, page, npage, nid);

	if (page)
887
		dn.inode_page_locked = true;
888 889 890 891
	truncate_node(&dn);
	return 0;
}

892
/*
C
Chao Yu 已提交
893 894
 * Caller should grab and release a rwsem by calling f2fs_lock_op() and
 * f2fs_unlock_op().
895
 */
G
Gu Zheng 已提交
896
void remove_inode_page(struct inode *inode)
J
Jaegeuk Kim 已提交
897 898 899
{
	struct dnode_of_data dn;

900 901
	set_new_dnode(&dn, inode, NULL, NULL, inode->i_ino);
	if (get_dnode_of_data(&dn, 0, LOOKUP_NODE))
G
Gu Zheng 已提交
902
		return;
J
Jaegeuk Kim 已提交
903

904 905
	if (truncate_xattr_node(inode, dn.inode_page)) {
		f2fs_put_dnode(&dn);
G
Gu Zheng 已提交
906
		return;
J
Jaegeuk Kim 已提交
907
	}
908 909 910 911 912 913

	/* 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 已提交
914
	/* 0 is possible, after f2fs_new_inode() has failed */
915 916
	f2fs_bug_on(F2FS_I_SB(inode),
			inode->i_blocks != 0 && inode->i_blocks != 1);
917 918

	/* will put inode & node pages */
919
	truncate_node(&dn);
J
Jaegeuk Kim 已提交
920 921
}

922
struct page *new_inode_page(struct inode *inode)
J
Jaegeuk Kim 已提交
923 924 925 926 927
{
	struct dnode_of_data dn;

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

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

933 934
struct page *new_node_page(struct dnode_of_data *dn,
				unsigned int ofs, struct page *ipage)
J
Jaegeuk Kim 已提交
935
{
936
	struct f2fs_sb_info *sbi = F2FS_I_SB(dn->inode);
J
Jaegeuk Kim 已提交
937 938 939 940
	struct node_info old_ni, new_ni;
	struct page *page;
	int err;

941
	if (unlikely(is_inode_flag_set(F2FS_I(dn->inode), FI_NO_ALLOC)))
J
Jaegeuk Kim 已提交
942 943
		return ERR_PTR(-EPERM);

944
	page = grab_cache_page(NODE_MAPPING(sbi), dn->nid);
J
Jaegeuk Kim 已提交
945 946 947
	if (!page)
		return ERR_PTR(-ENOMEM);

948
	if (unlikely(!inc_valid_node_count(sbi, dn->inode))) {
949 950 951
		err = -ENOSPC;
		goto fail;
	}
J
Jaegeuk Kim 已提交
952

953
	get_node_info(sbi, dn->nid, &old_ni);
J
Jaegeuk Kim 已提交
954 955

	/* Reinitialize old_ni with new node page */
956
	f2fs_bug_on(sbi, old_ni.blk_addr != NULL_ADDR);
J
Jaegeuk Kim 已提交
957 958
	new_ni = old_ni;
	new_ni.ino = dn->inode->i_ino;
959
	set_node_addr(sbi, &new_ni, NEW_ADDR, false);
960

961
	f2fs_wait_on_page_writeback(page, NODE);
962
	fill_node_footer(page, dn->nid, dn->inode->i_ino, ofs, true);
963
	set_cold_node(dn->inode, page);
964 965
	SetPageUptodate(page);
	set_page_dirty(page);
J
Jaegeuk Kim 已提交
966

967
	if (f2fs_has_xattr_block(ofs))
968 969
		F2FS_I(dn->inode)->i_xattr_nid = dn->nid;

J
Jaegeuk Kim 已提交
970
	dn->node_page = page;
971 972 973 974
	if (ipage)
		update_inode(dn->inode, ipage);
	else
		sync_inode_page(dn);
J
Jaegeuk Kim 已提交
975 976 977 978 979 980
	if (ofs == 0)
		inc_valid_inode_count(sbi);

	return page;

fail:
981
	clear_node_page_dirty(page);
J
Jaegeuk Kim 已提交
982 983 984 985
	f2fs_put_page(page, 1);
	return ERR_PTR(err);
}

986 987 988 989 990 991
/*
 * Caller should do after getting the following values.
 * 0: f2fs_put_page(page, 0)
 * LOCKED_PAGE: f2fs_put_page(page, 1)
 * error: nothing
 */
992
static int read_node_page(struct page *page, int rw)
J
Jaegeuk Kim 已提交
993
{
994
	struct f2fs_sb_info *sbi = F2FS_P_SB(page);
J
Jaegeuk Kim 已提交
995 996 997 998
	struct node_info ni;

	get_node_info(sbi, page->index, &ni);

999
	if (unlikely(ni.blk_addr == NULL_ADDR)) {
1000
		f2fs_put_page(page, 1);
J
Jaegeuk Kim 已提交
1001
		return -ENOENT;
1002 1003
	}

1004 1005
	if (PageUptodate(page))
		return LOCKED_PAGE;
1006

1007
	return f2fs_submit_page_bio(sbi, page, ni.blk_addr, rw);
J
Jaegeuk Kim 已提交
1008 1009
}

J
Jaegeuk Kim 已提交
1010
/*
J
Jaegeuk Kim 已提交
1011 1012 1013 1014 1015
 * Readahead a node page
 */
void ra_node_page(struct f2fs_sb_info *sbi, nid_t nid)
{
	struct page *apage;
1016
	int err;
J
Jaegeuk Kim 已提交
1017

1018
	apage = find_get_page(NODE_MAPPING(sbi), nid);
1019 1020 1021 1022
	if (apage && PageUptodate(apage)) {
		f2fs_put_page(apage, 0);
		return;
	}
J
Jaegeuk Kim 已提交
1023 1024
	f2fs_put_page(apage, 0);

1025
	apage = grab_cache_page(NODE_MAPPING(sbi), nid);
J
Jaegeuk Kim 已提交
1026 1027 1028
	if (!apage)
		return;

1029 1030
	err = read_node_page(apage, READA);
	if (err == 0)
1031
		f2fs_put_page(apage, 0);
1032 1033
	else if (err == LOCKED_PAGE)
		f2fs_put_page(apage, 1);
J
Jaegeuk Kim 已提交
1034 1035 1036 1037
}

struct page *get_node_page(struct f2fs_sb_info *sbi, pgoff_t nid)
{
1038 1039
	struct page *page;
	int err;
1040
repeat:
1041
	page = grab_cache_page(NODE_MAPPING(sbi), nid);
J
Jaegeuk Kim 已提交
1042 1043 1044 1045
	if (!page)
		return ERR_PTR(-ENOMEM);

	err = read_node_page(page, READ_SYNC);
1046
	if (err < 0)
J
Jaegeuk Kim 已提交
1047
		return ERR_PTR(err);
1048 1049
	else if (err == LOCKED_PAGE)
		goto got_it;
J
Jaegeuk Kim 已提交
1050

1051
	lock_page(page);
1052
	if (unlikely(!PageUptodate(page) || nid != nid_of_node(page))) {
1053 1054 1055
		f2fs_put_page(page, 1);
		return ERR_PTR(-EIO);
	}
1056
	if (unlikely(page->mapping != NODE_MAPPING(sbi))) {
1057 1058 1059
		f2fs_put_page(page, 1);
		goto repeat;
	}
1060
got_it:
J
Jaegeuk Kim 已提交
1061 1062 1063
	return page;
}

J
Jaegeuk Kim 已提交
1064
/*
J
Jaegeuk Kim 已提交
1065 1066 1067 1068 1069
 * Return a locked page for the desired node page.
 * And, readahead MAX_RA_NODE number of node pages.
 */
struct page *get_node_page_ra(struct page *parent, int start)
{
1070
	struct f2fs_sb_info *sbi = F2FS_P_SB(parent);
1071
	struct blk_plug plug;
J
Jaegeuk Kim 已提交
1072
	struct page *page;
1073 1074
	int err, i, end;
	nid_t nid;
J
Jaegeuk Kim 已提交
1075 1076 1077 1078 1079

	/* First, try getting the desired direct node. */
	nid = get_nid(parent, start, false);
	if (!nid)
		return ERR_PTR(-ENOENT);
1080
repeat:
1081
	page = grab_cache_page(NODE_MAPPING(sbi), nid);
J
Jaegeuk Kim 已提交
1082 1083 1084
	if (!page)
		return ERR_PTR(-ENOMEM);

1085
	err = read_node_page(page, READ_SYNC);
1086
	if (err < 0)
J
Jaegeuk Kim 已提交
1087
		return ERR_PTR(err);
1088 1089
	else if (err == LOCKED_PAGE)
		goto page_hit;
J
Jaegeuk Kim 已提交
1090

1091 1092
	blk_start_plug(&plug);

J
Jaegeuk Kim 已提交
1093 1094 1095 1096 1097 1098 1099 1100 1101 1102
	/* Then, try readahead for siblings of the desired node */
	end = start + MAX_RA_NODE;
	end = min(end, NIDS_PER_BLOCK);
	for (i = start + 1; i < end; i++) {
		nid = get_nid(parent, i, false);
		if (!nid)
			continue;
		ra_node_page(sbi, nid);
	}

1103 1104
	blk_finish_plug(&plug);

J
Jaegeuk Kim 已提交
1105
	lock_page(page);
1106
	if (unlikely(page->mapping != NODE_MAPPING(sbi))) {
1107 1108 1109
		f2fs_put_page(page, 1);
		goto repeat;
	}
1110
page_hit:
1111
	if (unlikely(!PageUptodate(page))) {
J
Jaegeuk Kim 已提交
1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128
		f2fs_put_page(page, 1);
		return ERR_PTR(-EIO);
	}
	return page;
}

void sync_inode_page(struct dnode_of_data *dn)
{
	if (IS_INODE(dn->node_page) || dn->inode_page == dn->node_page) {
		update_inode(dn->inode, dn->node_page);
	} else if (dn->inode_page) {
		if (!dn->inode_page_locked)
			lock_page(dn->inode_page);
		update_inode(dn->inode, dn->inode_page);
		if (!dn->inode_page_locked)
			unlock_page(dn->inode_page);
	} else {
1129
		update_inode_page(dn->inode);
J
Jaegeuk Kim 已提交
1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140 1141 1142 1143 1144 1145 1146 1147 1148
	}
}

int sync_node_pages(struct f2fs_sb_info *sbi, nid_t ino,
					struct writeback_control *wbc)
{
	pgoff_t index, end;
	struct pagevec pvec;
	int step = ino ? 2 : 0;
	int nwritten = 0, wrote = 0;

	pagevec_init(&pvec, 0);

next_step:
	index = 0;
	end = LONG_MAX;

	while (index <= end) {
		int i, nr_pages;
1149
		nr_pages = pagevec_lookup_tag(&pvec, NODE_MAPPING(sbi), &index,
J
Jaegeuk Kim 已提交
1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181
				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];

			/*
			 * 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;

			/*
			 * If an fsync mode,
			 * we should not skip writing node pages.
			 */
			if (ino && ino_of_node(page) == ino)
				lock_page(page);
			else if (!trylock_page(page))
				continue;

1182
			if (unlikely(page->mapping != NODE_MAPPING(sbi))) {
J
Jaegeuk Kim 已提交
1183 1184 1185 1186 1187 1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200
continue_unlock:
				unlock_page(page);
				continue;
			}
			if (ino && ino_of_node(page) != ino)
				goto continue_unlock;

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

			if (!clear_page_dirty_for_io(page))
				goto continue_unlock;

			/* called by fsync() */
			if (ino && IS_DNODE(page)) {
				set_fsync_mark(page, 1);
1201 1202 1203 1204 1205 1206 1207
				if (IS_INODE(page)) {
					if (!is_checkpointed_node(sbi, ino) &&
						!has_fsynced_inode(sbi, ino))
						set_dentry_mark(page, 1);
					else
						set_dentry_mark(page, 0);
				}
J
Jaegeuk Kim 已提交
1208 1209 1210 1211 1212
				nwritten++;
			} else {
				set_fsync_mark(page, 0);
				set_dentry_mark(page, 0);
			}
1213 1214 1215 1216 1217

			if (NODE_MAPPING(sbi)->a_ops->writepage(page, wbc))
				unlock_page(page);
			else
				wrote++;
J
Jaegeuk Kim 已提交
1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236

			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;
	}

	if (wrote)
J
Jaegeuk Kim 已提交
1237
		f2fs_submit_merged_bio(sbi, NODE, WRITE);
J
Jaegeuk Kim 已提交
1238 1239 1240
	return nwritten;
}

1241 1242 1243 1244 1245 1246 1247
int wait_on_node_pages_writeback(struct f2fs_sb_info *sbi, nid_t ino)
{
	pgoff_t index = 0, end = LONG_MAX;
	struct pagevec pvec;
	int ret2 = 0, ret = 0;

	pagevec_init(&pvec, 0);
1248 1249 1250 1251 1252 1253 1254 1255

	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;
1256 1257 1258 1259 1260

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

			/* until radix tree lookup accepts end_index */
1261
			if (unlikely(page->index > end))
1262 1263
				continue;

1264
			if (ino && ino_of_node(page) == ino) {
1265
				f2fs_wait_on_page_writeback(page, NODE);
1266 1267 1268
				if (TestClearPageError(page))
					ret = -EIO;
			}
1269 1270 1271 1272 1273
		}
		pagevec_release(&pvec);
		cond_resched();
	}

1274
	if (unlikely(test_and_clear_bit(AS_ENOSPC, &NODE_MAPPING(sbi)->flags)))
1275
		ret2 = -ENOSPC;
1276
	if (unlikely(test_and_clear_bit(AS_EIO, &NODE_MAPPING(sbi)->flags)))
1277 1278 1279 1280 1281 1282
		ret2 = -EIO;
	if (!ret)
		ret = ret2;
	return ret;
}

J
Jaegeuk Kim 已提交
1283 1284 1285
static int f2fs_write_node_page(struct page *page,
				struct writeback_control *wbc)
{
1286
	struct f2fs_sb_info *sbi = F2FS_P_SB(page);
J
Jaegeuk Kim 已提交
1287 1288 1289
	nid_t nid;
	block_t new_addr;
	struct node_info ni;
1290 1291
	struct f2fs_io_info fio = {
		.type = NODE,
C
Chris Fries 已提交
1292
		.rw = (wbc->sync_mode == WB_SYNC_ALL) ? WRITE_SYNC : WRITE,
1293
	};
J
Jaegeuk Kim 已提交
1294

1295 1296
	trace_f2fs_writepage(page, NODE);

1297
	if (unlikely(sbi->por_doing))
1298
		goto redirty_out;
1299 1300
	if (unlikely(f2fs_cp_error(sbi)))
		goto redirty_out;
1301

1302
	f2fs_wait_on_page_writeback(page, NODE);
J
Jaegeuk Kim 已提交
1303 1304 1305

	/* get old block addr of this node page */
	nid = nid_of_node(page);
1306
	f2fs_bug_on(sbi, page->index != nid);
J
Jaegeuk Kim 已提交
1307 1308 1309 1310

	get_node_info(sbi, nid, &ni);

	/* This page is already truncated */
1311
	if (unlikely(ni.blk_addr == NULL_ADDR)) {
1312 1313 1314 1315
		dec_page_count(sbi, F2FS_DIRTY_NODES);
		unlock_page(page);
		return 0;
	}
J
Jaegeuk Kim 已提交
1316

1317 1318 1319 1320 1321 1322
	if (wbc->for_reclaim) {
		if (!down_read_trylock(&sbi->node_write))
			goto redirty_out;
	} else {
		down_read(&sbi->node_write);
	}
J
Jaegeuk Kim 已提交
1323
	set_page_writeback(page);
1324
	write_node_page(sbi, page, &fio, nid, ni.blk_addr, &new_addr);
1325
	set_node_addr(sbi, &ni, new_addr, is_fsync_dnode(page));
J
Jaegeuk Kim 已提交
1326
	dec_page_count(sbi, F2FS_DIRTY_NODES);
1327
	up_read(&sbi->node_write);
J
Jaegeuk Kim 已提交
1328 1329
	unlock_page(page);
	return 0;
1330 1331

redirty_out:
1332
	redirty_page_for_writepage(wbc, page);
1333
	return AOP_WRITEPAGE_ACTIVATE;
J
Jaegeuk Kim 已提交
1334 1335 1336 1337 1338
}

static int f2fs_write_node_pages(struct address_space *mapping,
			    struct writeback_control *wbc)
{
1339
	struct f2fs_sb_info *sbi = F2FS_M_SB(mapping);
1340
	long diff;
J
Jaegeuk Kim 已提交
1341

1342 1343
	trace_f2fs_writepages(mapping->host, wbc, NODE);

1344 1345
	/* balancing f2fs's metadata in background */
	f2fs_balance_fs_bg(sbi);
J
Jaegeuk Kim 已提交
1346

1347
	/* collect a number of dirty node pages and write together */
1348
	if (get_pages(sbi, F2FS_DIRTY_NODES) < nr_pages_to_skip(sbi, NODE))
1349
		goto skip_write;
1350

1351
	diff = nr_pages_to_write(sbi, NODE, wbc);
1352
	wbc->sync_mode = WB_SYNC_NONE;
J
Jaegeuk Kim 已提交
1353
	sync_node_pages(sbi, 0, wbc);
1354
	wbc->nr_to_write = max((long)0, wbc->nr_to_write - diff);
J
Jaegeuk Kim 已提交
1355
	return 0;
1356 1357 1358 1359

skip_write:
	wbc->pages_skipped += get_pages(sbi, F2FS_DIRTY_NODES);
	return 0;
J
Jaegeuk Kim 已提交
1360 1361 1362 1363
}

static int f2fs_set_node_page_dirty(struct page *page)
{
1364 1365
	trace_f2fs_set_page_dirty(page, NODE);

J
Jaegeuk Kim 已提交
1366 1367 1368
	SetPageUptodate(page);
	if (!PageDirty(page)) {
		__set_page_dirty_nobuffers(page);
1369
		inc_page_count(F2FS_P_SB(page), F2FS_DIRTY_NODES);
J
Jaegeuk Kim 已提交
1370 1371 1372 1373 1374 1375
		SetPagePrivate(page);
		return 1;
	}
	return 0;
}

1376 1377
static void f2fs_invalidate_node_page(struct page *page, unsigned int offset,
				      unsigned int length)
J
Jaegeuk Kim 已提交
1378 1379 1380
{
	struct inode *inode = page->mapping->host;
	if (PageDirty(page))
1381
		dec_page_count(F2FS_I_SB(inode), F2FS_DIRTY_NODES);
J
Jaegeuk Kim 已提交
1382 1383 1384 1385 1386 1387
	ClearPagePrivate(page);
}

static int f2fs_release_node_page(struct page *page, gfp_t wait)
{
	ClearPagePrivate(page);
1388
	return 1;
J
Jaegeuk Kim 已提交
1389 1390
}

J
Jaegeuk Kim 已提交
1391
/*
J
Jaegeuk Kim 已提交
1392 1393 1394 1395 1396 1397 1398 1399 1400 1401
 * 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,
	.invalidatepage	= f2fs_invalidate_node_page,
	.releasepage	= f2fs_release_node_page,
};

1402 1403
static struct free_nid *__lookup_free_nid_list(struct f2fs_nm_info *nm_i,
						nid_t n)
J
Jaegeuk Kim 已提交
1404
{
1405
	return radix_tree_lookup(&nm_i->free_nid_root, n);
J
Jaegeuk Kim 已提交
1406 1407
}

1408 1409
static void __del_from_free_nid_list(struct f2fs_nm_info *nm_i,
						struct free_nid *i)
J
Jaegeuk Kim 已提交
1410 1411
{
	list_del(&i->list);
1412
	radix_tree_delete(&nm_i->free_nid_root, i->nid);
J
Jaegeuk Kim 已提交
1413 1414
}

1415
static int add_free_nid(struct f2fs_sb_info *sbi, nid_t nid, bool build)
J
Jaegeuk Kim 已提交
1416
{
1417
	struct f2fs_nm_info *nm_i = NM_I(sbi);
J
Jaegeuk Kim 已提交
1418
	struct free_nid *i;
1419 1420
	struct nat_entry *ne;
	bool allocated = false;
J
Jaegeuk Kim 已提交
1421

1422
	if (!available_free_memory(sbi, FREE_NIDS))
H
Haicheng Li 已提交
1423
		return -1;
1424 1425

	/* 0 nid should not be used */
1426
	if (unlikely(nid == 0))
1427
		return 0;
1428

1429 1430 1431 1432
	if (build) {
		/* do not add allocated nids */
		read_lock(&nm_i->nat_tree_lock);
		ne = __lookup_nat_cache(nm_i, nid);
1433
		if (ne &&
1434 1435
			(!get_nat_flag(ne, IS_CHECKPOINTED) ||
				nat_get_blkaddr(ne) != NULL_ADDR))
1436 1437 1438 1439
			allocated = true;
		read_unlock(&nm_i->nat_tree_lock);
		if (allocated)
			return 0;
J
Jaegeuk Kim 已提交
1440
	}
1441 1442

	i = f2fs_kmem_cache_alloc(free_nid_slab, GFP_NOFS);
J
Jaegeuk Kim 已提交
1443 1444 1445 1446
	i->nid = nid;
	i->state = NID_NEW;

	spin_lock(&nm_i->free_nid_list_lock);
1447
	if (radix_tree_insert(&nm_i->free_nid_root, i->nid, i)) {
J
Jaegeuk Kim 已提交
1448 1449 1450 1451 1452 1453 1454 1455 1456 1457 1458 1459 1460
		spin_unlock(&nm_i->free_nid_list_lock);
		kmem_cache_free(free_nid_slab, i);
		return 0;
	}
	list_add_tail(&i->list, &nm_i->free_nid_list);
	nm_i->fcnt++;
	spin_unlock(&nm_i->free_nid_list_lock);
	return 1;
}

static void remove_free_nid(struct f2fs_nm_info *nm_i, nid_t nid)
{
	struct free_nid *i;
1461 1462
	bool need_free = false;

J
Jaegeuk Kim 已提交
1463
	spin_lock(&nm_i->free_nid_list_lock);
1464
	i = __lookup_free_nid_list(nm_i, nid);
J
Jaegeuk Kim 已提交
1465
	if (i && i->state == NID_NEW) {
1466
		__del_from_free_nid_list(nm_i, i);
J
Jaegeuk Kim 已提交
1467
		nm_i->fcnt--;
1468
		need_free = true;
J
Jaegeuk Kim 已提交
1469 1470
	}
	spin_unlock(&nm_i->free_nid_list_lock);
1471 1472 1473

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

1476
static void scan_nat_page(struct f2fs_sb_info *sbi,
J
Jaegeuk Kim 已提交
1477 1478
			struct page *nat_page, nid_t start_nid)
{
1479
	struct f2fs_nm_info *nm_i = NM_I(sbi);
J
Jaegeuk Kim 已提交
1480 1481 1482 1483 1484 1485 1486
	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 已提交
1487

1488
		if (unlikely(start_nid >= nm_i->max_nid))
J
Jaegeuk Kim 已提交
1489
			break;
H
Haicheng Li 已提交
1490 1491

		blk_addr = le32_to_cpu(nat_blk->entries[i].block_addr);
1492
		f2fs_bug_on(sbi, blk_addr == NEW_ADDR);
H
Haicheng Li 已提交
1493
		if (blk_addr == NULL_ADDR) {
1494
			if (add_free_nid(sbi, start_nid, true) < 0)
H
Haicheng Li 已提交
1495 1496
				break;
		}
J
Jaegeuk Kim 已提交
1497 1498 1499 1500 1501 1502 1503 1504
	}
}

static void build_free_nids(struct f2fs_sb_info *sbi)
{
	struct f2fs_nm_info *nm_i = NM_I(sbi);
	struct curseg_info *curseg = CURSEG_I(sbi, CURSEG_HOT_DATA);
	struct f2fs_summary_block *sum = curseg->sum_blk;
1505
	int i = 0;
1506
	nid_t nid = nm_i->next_scan_nid;
J
Jaegeuk Kim 已提交
1507

1508 1509 1510
	/* Enough entries */
	if (nm_i->fcnt > NAT_ENTRY_PER_BLOCK)
		return;
J
Jaegeuk Kim 已提交
1511

1512
	/* readahead nat pages to be scanned */
1513
	ra_meta_pages(sbi, NAT_BLOCK_OFFSET(nid), FREE_NID_PAGES, META_NAT);
J
Jaegeuk Kim 已提交
1514 1515 1516 1517

	while (1) {
		struct page *page = get_current_nat_page(sbi, nid);

1518
		scan_nat_page(sbi, page, nid);
J
Jaegeuk Kim 已提交
1519 1520 1521
		f2fs_put_page(page, 1);

		nid += (NAT_ENTRY_PER_BLOCK - (nid % NAT_ENTRY_PER_BLOCK));
1522
		if (unlikely(nid >= nm_i->max_nid))
J
Jaegeuk Kim 已提交
1523
			nid = 0;
1524 1525

		if (i++ == FREE_NID_PAGES)
J
Jaegeuk Kim 已提交
1526 1527 1528
			break;
	}

1529 1530
	/* go to the next free nat pages to find free nids abundantly */
	nm_i->next_scan_nid = nid;
J
Jaegeuk Kim 已提交
1531 1532 1533 1534 1535 1536 1537

	/* find free nids from current sum_pages */
	mutex_lock(&curseg->curseg_mutex);
	for (i = 0; i < nats_in_cursum(sum); i++) {
		block_t addr = le32_to_cpu(nat_in_journal(sum, i).block_addr);
		nid = le32_to_cpu(nid_in_journal(sum, i));
		if (addr == NULL_ADDR)
1538
			add_free_nid(sbi, nid, true);
J
Jaegeuk Kim 已提交
1539 1540 1541 1542 1543 1544 1545 1546 1547 1548 1549 1550 1551 1552 1553 1554
		else
			remove_free_nid(nm_i, nid);
	}
	mutex_unlock(&curseg->curseg_mutex);
}

/*
 * 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:
1555
	if (unlikely(sbi->total_valid_node_count + 1 > nm_i->available_nids))
1556
		return false;
J
Jaegeuk Kim 已提交
1557 1558 1559

	spin_lock(&nm_i->free_nid_list_lock);

1560
	/* We should not use stale free nids created by build_free_nids */
1561
	if (nm_i->fcnt && !on_build_free_nids(nm_i)) {
1562
		f2fs_bug_on(sbi, list_empty(&nm_i->free_nid_list));
1563
		list_for_each_entry(i, &nm_i->free_nid_list, list)
1564 1565
			if (i->state == NID_NEW)
				break;
J
Jaegeuk Kim 已提交
1566

1567
		f2fs_bug_on(sbi, i->state != NID_NEW);
1568 1569 1570 1571 1572 1573
		*nid = i->nid;
		i->state = NID_ALLOC;
		nm_i->fcnt--;
		spin_unlock(&nm_i->free_nid_list_lock);
		return true;
	}
J
Jaegeuk Kim 已提交
1574
	spin_unlock(&nm_i->free_nid_list_lock);
1575 1576 1577 1578 1579 1580

	/* Let's scan nat pages and its caches to get free nids */
	mutex_lock(&nm_i->build_lock);
	build_free_nids(sbi);
	mutex_unlock(&nm_i->build_lock);
	goto retry;
J
Jaegeuk Kim 已提交
1581 1582
}

J
Jaegeuk Kim 已提交
1583
/*
J
Jaegeuk Kim 已提交
1584 1585 1586 1587 1588 1589 1590 1591
 * 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;

	spin_lock(&nm_i->free_nid_list_lock);
1592
	i = __lookup_free_nid_list(nm_i, nid);
1593
	f2fs_bug_on(sbi, !i || i->state != NID_ALLOC);
1594
	__del_from_free_nid_list(nm_i, i);
J
Jaegeuk Kim 已提交
1595
	spin_unlock(&nm_i->free_nid_list_lock);
1596 1597

	kmem_cache_free(free_nid_slab, i);
J
Jaegeuk Kim 已提交
1598 1599
}

J
Jaegeuk Kim 已提交
1600
/*
J
Jaegeuk Kim 已提交
1601 1602 1603 1604
 * alloc_nid() should be called prior to this function.
 */
void alloc_nid_failed(struct f2fs_sb_info *sbi, nid_t nid)
{
1605 1606
	struct f2fs_nm_info *nm_i = NM_I(sbi);
	struct free_nid *i;
1607
	bool need_free = false;
1608

J
Jaegeuk Kim 已提交
1609 1610 1611
	if (!nid)
		return;

1612
	spin_lock(&nm_i->free_nid_list_lock);
1613
	i = __lookup_free_nid_list(nm_i, nid);
1614
	f2fs_bug_on(sbi, !i || i->state != NID_ALLOC);
1615
	if (!available_free_memory(sbi, FREE_NIDS)) {
1616
		__del_from_free_nid_list(nm_i, i);
1617
		need_free = true;
1618 1619 1620 1621
	} else {
		i->state = NID_NEW;
		nm_i->fcnt++;
	}
1622
	spin_unlock(&nm_i->free_nid_list_lock);
1623 1624 1625

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

1628
void recover_inline_xattr(struct inode *inode, struct page *page)
1629 1630 1631 1632 1633 1634
{
	void *src_addr, *dst_addr;
	size_t inline_size;
	struct page *ipage;
	struct f2fs_inode *ri;

1635
	ipage = get_node_page(F2FS_I_SB(inode), inode->i_ino);
1636
	f2fs_bug_on(F2FS_I_SB(inode), IS_ERR(ipage));
1637

1638 1639 1640 1641 1642 1643
	ri = F2FS_INODE(page);
	if (!(ri->i_inline & F2FS_INLINE_XATTR)) {
		clear_inode_flag(F2FS_I(inode), FI_INLINE_XATTR);
		goto update_inode;
	}

1644 1645 1646 1647
	dst_addr = inline_xattr_addr(ipage);
	src_addr = inline_xattr_addr(page);
	inline_size = inline_xattr_size(inode);

1648
	f2fs_wait_on_page_writeback(ipage, NODE);
1649
	memcpy(dst_addr, src_addr, inline_size);
1650
update_inode:
1651 1652 1653 1654
	update_inode(inode, ipage);
	f2fs_put_page(ipage, 1);
}

1655
void recover_xattr_data(struct inode *inode, struct page *page, block_t blkaddr)
1656
{
1657
	struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
1658 1659 1660 1661 1662 1663 1664 1665 1666 1667
	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);
1668
	f2fs_bug_on(sbi, ni.blk_addr == NULL_ADDR);
1669 1670
	invalidate_blocks(sbi, ni.blk_addr);
	dec_valid_node_count(sbi, inode);
1671
	set_node_addr(sbi, &ni, NULL_ADDR, false);
1672 1673 1674 1675

recover_xnid:
	/* 2: allocate new xattr nid */
	if (unlikely(!inc_valid_node_count(sbi, inode)))
1676
		f2fs_bug_on(sbi, 1);
1677 1678 1679 1680

	remove_free_nid(NM_I(sbi), new_xnid);
	get_node_info(sbi, new_xnid, &ni);
	ni.ino = inode->i_ino;
1681
	set_node_addr(sbi, &ni, NEW_ADDR, false);
1682 1683 1684 1685
	F2FS_I(inode)->i_xattr_nid = new_xnid;

	/* 3: update xattr blkaddr */
	refresh_sit_entry(sbi, NEW_ADDR, blkaddr);
1686
	set_node_addr(sbi, &ni, blkaddr, false);
1687 1688 1689 1690

	update_inode_page(inode);
}

J
Jaegeuk Kim 已提交
1691 1692
int recover_inode_page(struct f2fs_sb_info *sbi, struct page *page)
{
1693
	struct f2fs_inode *src, *dst;
J
Jaegeuk Kim 已提交
1694 1695 1696 1697
	nid_t ino = ino_of_node(page);
	struct node_info old_ni, new_ni;
	struct page *ipage;

1698 1699 1700 1701 1702
	get_node_info(sbi, ino, &old_ni);

	if (unlikely(old_ni.blk_addr != NULL_ADDR))
		return -EINVAL;

1703
	ipage = grab_cache_page(NODE_MAPPING(sbi), ino);
J
Jaegeuk Kim 已提交
1704 1705 1706
	if (!ipage)
		return -ENOMEM;

A
arter97 已提交
1707
	/* Should not use this inode from free nid list */
J
Jaegeuk Kim 已提交
1708 1709 1710 1711 1712
	remove_free_nid(NM_I(sbi), ino);

	SetPageUptodate(ipage);
	fill_node_footer(ipage, ino, ino, 0, true);

1713 1714
	src = F2FS_INODE(page);
	dst = F2FS_INODE(ipage);
J
Jaegeuk Kim 已提交
1715

1716 1717 1718 1719 1720
	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;
1721
	dst->i_inline = src->i_inline & F2FS_INLINE_XATTR;
J
Jaegeuk Kim 已提交
1722 1723 1724 1725

	new_ni = old_ni;
	new_ni.ino = ino;

1726
	if (unlikely(!inc_valid_node_count(sbi, NULL)))
1727
		WARN_ON(1);
1728
	set_node_addr(sbi, &new_ni, NEW_ADDR, false);
J
Jaegeuk Kim 已提交
1729
	inc_valid_inode_count(sbi);
1730
	set_page_dirty(ipage);
J
Jaegeuk Kim 已提交
1731 1732 1733 1734
	f2fs_put_page(ipage, 1);
	return 0;
}

1735 1736
/*
 * ra_sum_pages() merge contiguous pages into one bio and submit.
A
arter97 已提交
1737
 * these pre-read pages are allocated in bd_inode's mapping tree.
1738
 */
1739
static int ra_sum_pages(struct f2fs_sb_info *sbi, struct page **pages,
1740 1741
				int start, int nrpages)
{
1742 1743 1744
	struct inode *inode = sbi->sb->s_bdev->bd_inode;
	struct address_space *mapping = inode->i_mapping;
	int i, page_idx = start;
J
Jaegeuk Kim 已提交
1745 1746
	struct f2fs_io_info fio = {
		.type = META,
1747
		.rw = READ_SYNC | REQ_META | REQ_PRIO
J
Jaegeuk Kim 已提交
1748
	};
1749

1750 1751 1752 1753
	for (i = 0; page_idx < start + nrpages; page_idx++, i++) {
		/* alloc page in bd_inode for reading node summary info */
		pages[i] = grab_cache_page(mapping, page_idx);
		if (!pages[i])
1754
			break;
1755
		f2fs_submit_page_mbio(sbi, pages[i], page_idx, &fio);
1756 1757
	}

J
Jaegeuk Kim 已提交
1758
	f2fs_submit_merged_bio(sbi, META, READ);
1759
	return i;
1760 1761
}

J
Jaegeuk Kim 已提交
1762 1763 1764 1765 1766
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;
1767
	struct inode *inode = sbi->sb->s_bdev->bd_inode;
J
Jaegeuk Kim 已提交
1768
	block_t addr;
J
Jaegeuk Kim 已提交
1769
	int bio_blocks = MAX_BIO_BLOCKS(sbi);
1770 1771
	struct page *pages[bio_blocks];
	int i, idx, last_offset, nrpages, err = 0;
J
Jaegeuk Kim 已提交
1772 1773 1774 1775 1776 1777

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

1778
	for (i = 0; !err && i < last_offset; i += nrpages, addr += nrpages) {
1779
		nrpages = min(last_offset - i, bio_blocks);
1780

A
arter97 已提交
1781
		/* readahead node pages */
1782
		nrpages = ra_sum_pages(sbi, pages, addr, nrpages);
1783 1784
		if (!nrpages)
			return -ENOMEM;
J
Jaegeuk Kim 已提交
1785

1786
		for (idx = 0; idx < nrpages; idx++) {
1787 1788
			if (err)
				goto skip;
1789

1790 1791
			lock_page(pages[idx]);
			if (unlikely(!PageUptodate(pages[idx]))) {
1792 1793
				err = -EIO;
			} else {
1794
				rn = F2FS_NODE(pages[idx]);
1795 1796 1797 1798 1799
				sum_entry->nid = rn->footer.nid;
				sum_entry->version = 0;
				sum_entry->ofs_in_node = 0;
				sum_entry++;
			}
1800
			unlock_page(pages[idx]);
1801
skip:
1802
			page_cache_release(pages[idx]);
1803
		}
1804 1805 1806

		invalidate_mapping_pages(inode->i_mapping, addr,
							addr + nrpages);
J
Jaegeuk Kim 已提交
1807
	}
1808
	return err;
J
Jaegeuk Kim 已提交
1809 1810
}

1811
static void remove_nats_in_journal(struct f2fs_sb_info *sbi)
J
Jaegeuk Kim 已提交
1812 1813 1814 1815 1816 1817 1818 1819 1820 1821 1822 1823 1824 1825 1826 1827
{
	struct f2fs_nm_info *nm_i = NM_I(sbi);
	struct curseg_info *curseg = CURSEG_I(sbi, CURSEG_HOT_DATA);
	struct f2fs_summary_block *sum = curseg->sum_blk;
	int i;

	mutex_lock(&curseg->curseg_mutex);
	for (i = 0; i < nats_in_cursum(sum); i++) {
		struct nat_entry *ne;
		struct f2fs_nat_entry raw_ne;
		nid_t nid = le32_to_cpu(nid_in_journal(sum, i));

		raw_ne = nat_in_journal(sum, i);
retry:
		write_lock(&nm_i->nat_tree_lock);
		ne = __lookup_nat_cache(nm_i, nid);
1828 1829 1830
		if (ne)
			goto found;

J
Jaegeuk Kim 已提交
1831 1832 1833 1834 1835
		ne = grab_nat_entry(nm_i, nid);
		if (!ne) {
			write_unlock(&nm_i->nat_tree_lock);
			goto retry;
		}
1836
		node_info_from_raw_nat(&ne->ni, &raw_ne);
1837
found:
J
Jaegeuk Kim 已提交
1838 1839 1840 1841 1842 1843 1844
		__set_nat_cache_dirty(nm_i, ne);
		write_unlock(&nm_i->nat_tree_lock);
	}
	update_nats_in_cursum(sum, -i);
	mutex_unlock(&curseg->curseg_mutex);
}

1845 1846
static void __adjust_nat_entry_set(struct nat_entry_set *nes,
						struct list_head *head, int max)
J
Jaegeuk Kim 已提交
1847
{
1848
	struct nat_entry_set *cur;
J
Jaegeuk Kim 已提交
1849

1850 1851
	if (nes->entry_cnt >= max)
		goto add_out;
J
Jaegeuk Kim 已提交
1852

1853 1854 1855 1856 1857
	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;
		}
1858
	}
1859 1860 1861
add_out:
	list_add_tail(&nes->set_list, head);
}
J
Jaegeuk Kim 已提交
1862

1863 1864 1865 1866 1867 1868 1869 1870 1871 1872
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);
	struct f2fs_summary_block *sum = curseg->sum_blk;
	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 已提交
1873

1874 1875 1876 1877 1878
	/*
	 * 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.
	 */
1879 1880 1881 1882 1883 1884 1885 1886 1887 1888
	if (!__has_cursum_space(sum, set->entry_cnt, NAT_JOURNAL))
		to_journal = false;

	if (to_journal) {
		mutex_lock(&curseg->curseg_mutex);
	} else {
		page = get_next_nat_page(sbi, start_nid);
		nat_blk = page_address(page);
		f2fs_bug_on(sbi, !nat_blk);
	}
1889

1890 1891 1892 1893 1894 1895 1896 1897
	/* 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;
1898 1899

		if (to_journal) {
1900 1901 1902 1903 1904
			offset = lookup_journal_in_cursum(sum,
							NAT_JOURNAL, nid, 1);
			f2fs_bug_on(sbi, offset < 0);
			raw_ne = &nat_in_journal(sum, offset);
			nid_in_journal(sum, offset) = cpu_to_le32(nid);
1905
		} else {
1906
			raw_ne = &nat_blk->entries[nid - start_nid];
J
Jaegeuk Kim 已提交
1907
		}
1908
		raw_nat_from_node_info(raw_ne, &ne->ni);
J
Jaegeuk Kim 已提交
1909

1910 1911 1912 1913
		write_lock(&NM_I(sbi)->nat_tree_lock);
		nat_reset_flag(ne);
		__clear_nat_cache_dirty(NM_I(sbi), ne);
		write_unlock(&NM_I(sbi)->nat_tree_lock);
1914

1915 1916 1917
		if (nat_get_blkaddr(ne) == NULL_ADDR)
			add_free_nid(sbi, nid, false);
	}
J
Jaegeuk Kim 已提交
1918

1919 1920 1921 1922
	if (to_journal)
		mutex_unlock(&curseg->curseg_mutex);
	else
		f2fs_put_page(page, 1);
1923

1924 1925 1926 1927 1928
	if (!set->entry_cnt) {
		radix_tree_delete(&NM_I(sbi)->nat_set_root, set->set);
		kmem_cache_free(nat_entry_set_slab, set);
	}
}
1929

1930 1931 1932 1933 1934 1935 1936 1937 1938 1939 1940 1941 1942 1943 1944 1945 1946 1947 1948 1949 1950 1951 1952 1953 1954 1955 1956 1957 1958 1959 1960 1961
/*
 * 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);
	struct f2fs_summary_block *sum = curseg->sum_blk;
	struct nat_entry_set *setvec[NATVEC_SIZE];
	struct nat_entry_set *set, *tmp;
	unsigned int found;
	nid_t set_idx = 0;
	LIST_HEAD(sets);

	/*
	 * 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.
	 */
	if (!__has_cursum_space(sum, nm_i->dirty_nat_cnt, NAT_JOURNAL))
		remove_nats_in_journal(sbi);

	if (!nm_i->dirty_nat_cnt)
		return;

	while ((found = __gang_lookup_nat_set(nm_i,
					set_idx, NATVEC_SIZE, setvec))) {
		unsigned idx;
		set_idx = setvec[found - 1]->set + 1;
		for (idx = 0; idx < found; idx++)
			__adjust_nat_entry_set(setvec[idx], &sets,
							MAX_NAT_JENTRIES(sum));
J
Jaegeuk Kim 已提交
1962
	}
1963

1964 1965 1966 1967
	/* flush dirty nats in nat entry set */
	list_for_each_entry_safe(set, tmp, &sets, set_list)
		__flush_nat_entry_set(sbi, set);

1968
	f2fs_bug_on(sbi, nm_i->dirty_nat_cnt);
J
Jaegeuk Kim 已提交
1969 1970 1971 1972 1973 1974 1975 1976 1977 1978 1979 1980 1981 1982
}

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);
1983

1984 1985
	nm_i->max_nid = NAT_ENTRY_PER_BLOCK * nat_blocks;

1986
	/* not used nids: 0, node, meta, (and root counted as valid node) */
1987
	nm_i->available_nids = nm_i->max_nid - F2FS_RESERVED_NODE_NUM;
J
Jaegeuk Kim 已提交
1988 1989
	nm_i->fcnt = 0;
	nm_i->nat_cnt = 0;
1990
	nm_i->ram_thresh = DEF_RAM_THRESHOLD;
J
Jaegeuk Kim 已提交
1991

1992
	INIT_RADIX_TREE(&nm_i->free_nid_root, GFP_ATOMIC);
J
Jaegeuk Kim 已提交
1993 1994
	INIT_LIST_HEAD(&nm_i->free_nid_list);
	INIT_RADIX_TREE(&nm_i->nat_root, GFP_ATOMIC);
1995
	INIT_RADIX_TREE(&nm_i->nat_set_root, GFP_ATOMIC);
J
Jaegeuk Kim 已提交
1996 1997 1998 1999 2000 2001 2002
	INIT_LIST_HEAD(&nm_i->nat_entries);

	mutex_init(&nm_i->build_lock);
	spin_lock_init(&nm_i->free_nid_list_lock);
	rwlock_init(&nm_i->nat_tree_lock);

	nm_i->next_scan_nid = le32_to_cpu(sbi->ckpt->next_free_nid);
A
Alexandru Gheorghiu 已提交
2003
	nm_i->bitmap_size = __bitmap_size(sbi, NAT_BITMAP);
J
Jaegeuk Kim 已提交
2004 2005 2006 2007
	version_bitmap = __bitmap_ptr(sbi, NAT_BITMAP);
	if (!version_bitmap)
		return -EFAULT;

A
Alexandru Gheorghiu 已提交
2008 2009 2010 2011
	nm_i->nat_bitmap = kmemdup(version_bitmap, nm_i->bitmap_size,
					GFP_KERNEL);
	if (!nm_i->nat_bitmap)
		return -ENOMEM;
J
Jaegeuk Kim 已提交
2012 2013 2014 2015 2016 2017 2018 2019 2020 2021 2022 2023 2024 2025 2026 2027 2028 2029 2030 2031 2032 2033 2034 2035 2036 2037 2038 2039 2040 2041 2042 2043 2044
	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;

	build_free_nids(sbi);
	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];
	nid_t nid = 0;
	unsigned int found;

	if (!nm_i)
		return;

	/* destroy free nid list */
	spin_lock(&nm_i->free_nid_list_lock);
	list_for_each_entry_safe(i, next_i, &nm_i->free_nid_list, list) {
2045
		f2fs_bug_on(sbi, i->state == NID_ALLOC);
2046
		__del_from_free_nid_list(nm_i, i);
J
Jaegeuk Kim 已提交
2047
		nm_i->fcnt--;
2048 2049 2050
		spin_unlock(&nm_i->free_nid_list_lock);
		kmem_cache_free(free_nid_slab, i);
		spin_lock(&nm_i->free_nid_list_lock);
J
Jaegeuk Kim 已提交
2051
	}
2052
	f2fs_bug_on(sbi, nm_i->fcnt);
J
Jaegeuk Kim 已提交
2053 2054 2055 2056 2057 2058 2059
	spin_unlock(&nm_i->free_nid_list_lock);

	/* destroy nat cache */
	write_lock(&nm_i->nat_tree_lock);
	while ((found = __gang_lookup_nat_cache(nm_i,
					nid, NATVEC_SIZE, natvec))) {
		unsigned idx;
2060 2061 2062
		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 已提交
2063
	}
2064
	f2fs_bug_on(sbi, nm_i->nat_cnt);
J
Jaegeuk Kim 已提交
2065 2066 2067 2068 2069 2070 2071
	write_unlock(&nm_i->nat_tree_lock);

	kfree(nm_i->nat_bitmap);
	sbi->nm_info = NULL;
	kfree(nm_i);
}

2072
int __init create_node_manager_caches(void)
J
Jaegeuk Kim 已提交
2073 2074
{
	nat_entry_slab = f2fs_kmem_cache_create("nat_entry",
2075
			sizeof(struct nat_entry));
J
Jaegeuk Kim 已提交
2076
	if (!nat_entry_slab)
2077
		goto fail;
J
Jaegeuk Kim 已提交
2078 2079

	free_nid_slab = f2fs_kmem_cache_create("free_nid",
2080
			sizeof(struct free_nid));
2081 2082 2083 2084 2085 2086 2087
	if (!free_nid_slab)
		goto destory_nat_entry;

	nat_entry_set_slab = f2fs_kmem_cache_create("nat_entry_set",
			sizeof(struct nat_entry_set));
	if (!nat_entry_set_slab)
		goto destory_free_nid;
J
Jaegeuk Kim 已提交
2088
	return 0;
2089 2090 2091 2092 2093 2094 2095

destory_free_nid:
	kmem_cache_destroy(free_nid_slab);
destory_nat_entry:
	kmem_cache_destroy(nat_entry_slab);
fail:
	return -ENOMEM;
J
Jaegeuk Kim 已提交
2096 2097 2098 2099
}

void destroy_node_manager_caches(void)
{
2100
	kmem_cache_destroy(nat_entry_set_slab);
J
Jaegeuk Kim 已提交
2101 2102 2103
	kmem_cache_destroy(free_nid_slab);
	kmem_cache_destroy(nat_entry_slab);
}