node.c 51.4 KB
Newer Older
Jaegeuk Kim's avatar
Jaegeuk Kim committed
1
/*
Jaegeuk Kim's avatar
Jaegeuk Kim committed
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"
Jaegeuk Kim's avatar
Jaegeuk Kim committed
22
#include "trace.h"
23
#include <trace/events/f2fs.h>
Jaegeuk Kim's avatar
Jaegeuk Kim committed
24

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

Jaegeuk Kim's avatar
Jaegeuk Kim committed
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;
Jaegeuk Kim's avatar
Jaegeuk Kim committed
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) {
48 49 50
		mem_size = (nm_i->fcnt * sizeof(struct free_nid)) >>
							PAGE_CACHE_SHIFT;
		res = mem_size < ((avail_ram * nm_i->ram_thresh / 100) >> 2);
51
	} else if (type == NAT_ENTRIES) {
52 53 54
		mem_size = (nm_i->nat_cnt * sizeof(struct nat_entry)) >>
							PAGE_CACHE_SHIFT;
		res = mem_size < ((avail_ram * nm_i->ram_thresh / 100) >> 2);
55 56 57 58 59
	} 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);
60 61 62 63
	} else if (type == INO_ENTRIES) {
		int i;

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

Jaegeuk Kim's avatar
Jaegeuk Kim committed
80 81 82 83 84 85 86 87 88 89 90 91 92
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);
93
		dec_page_count(F2FS_M_SB(mapping), F2FS_DIRTY_NODES);
Jaegeuk Kim's avatar
Jaegeuk Kim committed
94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119
	}
	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);
120
	f2fs_bug_on(sbi, PageDirty(src_page));
Jaegeuk Kim's avatar
Jaegeuk Kim committed
121 122 123 124 125 126 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

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

152 153 154 155 156 157 158 159
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;
160

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

		INIT_LIST_HEAD(&head->entry_list);
		INIT_LIST_HEAD(&head->set_list);
		head->set = set;
		head->entry_cnt = 0;
169
		f2fs_radix_tree_insert(&nm_i->nat_set_root, set, head);
170 171 172 173 174 175 176 177 178 179
	}
	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)
{
180
	nid_t set = NAT_BLOCK_OFFSET(ne->ni.nid);
181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198
	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);
}

Jaegeuk Kim's avatar
Jaegeuk Kim committed
199
int need_dentry_mark(struct f2fs_sb_info *sbi, nid_t nid)
Jaegeuk Kim's avatar
Jaegeuk Kim committed
200 201 202
{
	struct f2fs_nm_info *nm_i = NM_I(sbi);
	struct nat_entry *e;
Jaegeuk Kim's avatar
Jaegeuk Kim committed
203
	bool need = false;
Jaegeuk Kim's avatar
Jaegeuk Kim committed
204

205
	down_read(&nm_i->nat_tree_lock);
Jaegeuk Kim's avatar
Jaegeuk Kim committed
206
	e = __lookup_nat_cache(nm_i, nid);
Jaegeuk Kim's avatar
Jaegeuk Kim committed
207 208 209 210 211
	if (e) {
		if (!get_nat_flag(e, IS_CHECKPOINTED) &&
				!get_nat_flag(e, HAS_FSYNCED_INODE))
			need = true;
	}
212
	up_read(&nm_i->nat_tree_lock);
Jaegeuk Kim's avatar
Jaegeuk Kim committed
213
	return need;
Jaegeuk Kim's avatar
Jaegeuk Kim committed
214 215
}

Jaegeuk Kim's avatar
Jaegeuk Kim committed
216
bool is_checkpointed_node(struct f2fs_sb_info *sbi, nid_t nid)
217 218 219
{
	struct f2fs_nm_info *nm_i = NM_I(sbi);
	struct nat_entry *e;
Jaegeuk Kim's avatar
Jaegeuk Kim committed
220
	bool is_cp = true;
221

222
	down_read(&nm_i->nat_tree_lock);
Jaegeuk Kim's avatar
Jaegeuk Kim committed
223 224 225
	e = __lookup_nat_cache(nm_i, nid);
	if (e && !get_nat_flag(e, IS_CHECKPOINTED))
		is_cp = false;
226
	up_read(&nm_i->nat_tree_lock);
Jaegeuk Kim's avatar
Jaegeuk Kim committed
227
	return is_cp;
228 229
}

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

236
	down_read(&nm_i->nat_tree_lock);
237 238 239 240 241
	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;
242
	up_read(&nm_i->nat_tree_lock);
243
	return need_update;
244 245
}

Jaegeuk Kim's avatar
Jaegeuk Kim committed
246 247 248 249
static struct nat_entry *grab_nat_entry(struct f2fs_nm_info *nm_i, nid_t nid)
{
	struct nat_entry *new;

250
	new = f2fs_kmem_cache_alloc(nat_entry_slab, GFP_NOFS);
251
	f2fs_radix_tree_insert(&nm_i->nat_root, nid, new);
Jaegeuk Kim's avatar
Jaegeuk Kim committed
252 253
	memset(new, 0, sizeof(struct nat_entry));
	nat_set_nid(new, nid);
254
	nat_reset_flag(new);
Jaegeuk Kim's avatar
Jaegeuk Kim committed
255 256 257 258 259 260 261 262 263
	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;
264

265
	down_write(&nm_i->nat_tree_lock);
Jaegeuk Kim's avatar
Jaegeuk Kim committed
266 267 268
	e = __lookup_nat_cache(nm_i, nid);
	if (!e) {
		e = grab_nat_entry(nm_i, nid);
269
		node_info_from_raw_nat(&e->ni, ne);
Jaegeuk Kim's avatar
Jaegeuk Kim committed
270
	}
271
	up_write(&nm_i->nat_tree_lock);
Jaegeuk Kim's avatar
Jaegeuk Kim committed
272 273 274
}

static void set_node_addr(struct f2fs_sb_info *sbi, struct node_info *ni,
275
			block_t new_blkaddr, bool fsync_done)
Jaegeuk Kim's avatar
Jaegeuk Kim committed
276 277 278
{
	struct f2fs_nm_info *nm_i = NM_I(sbi);
	struct nat_entry *e;
279

280
	down_write(&nm_i->nat_tree_lock);
Jaegeuk Kim's avatar
Jaegeuk Kim committed
281 282 283
	e = __lookup_nat_cache(nm_i, ni->nid);
	if (!e) {
		e = grab_nat_entry(nm_i, ni->nid);
284
		copy_node_info(&e->ni, ni);
285
		f2fs_bug_on(sbi, ni->blk_addr == NEW_ADDR);
Jaegeuk Kim's avatar
Jaegeuk Kim committed
286 287 288 289 290 291
	} 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.
		 */
292
		copy_node_info(&e->ni, ni);
293
		f2fs_bug_on(sbi, ni->blk_addr != NULL_ADDR);
Jaegeuk Kim's avatar
Jaegeuk Kim committed
294 295 296
	}

	/* sanity check */
297 298
	f2fs_bug_on(sbi, nat_get_blkaddr(e) != ni->blk_addr);
	f2fs_bug_on(sbi, nat_get_blkaddr(e) == NULL_ADDR &&
Jaegeuk Kim's avatar
Jaegeuk Kim committed
299
			new_blkaddr == NULL_ADDR);
300
	f2fs_bug_on(sbi, nat_get_blkaddr(e) == NEW_ADDR &&
Jaegeuk Kim's avatar
Jaegeuk Kim committed
301
			new_blkaddr == NEW_ADDR);
302
	f2fs_bug_on(sbi, nat_get_blkaddr(e) != NEW_ADDR &&
Jaegeuk Kim's avatar
Jaegeuk Kim committed
303 304 305
			nat_get_blkaddr(e) != NULL_ADDR &&
			new_blkaddr == NEW_ADDR);

arter97's avatar
arter97 committed
306
	/* increment version no as node is removed */
Jaegeuk Kim's avatar
Jaegeuk Kim committed
307 308 309
	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));
310 311 312 313

		/* in order to reuse the nid */
		if (nm_i->next_scan_nid > ni->nid)
			nm_i->next_scan_nid = ni->nid;
Jaegeuk Kim's avatar
Jaegeuk Kim committed
314 315 316 317
	}

	/* 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);
Jaegeuk Kim's avatar
Jaegeuk Kim committed
320
	__set_nat_cache_dirty(nm_i, e);
321 322

	/* update fsync_mark if its inode nat entry is still alive */
323 324
	if (ni->nid != ni->ino)
		e = __lookup_nat_cache(nm_i, ni->ino);
325 326 327 328 329
	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);
	}
330
	up_write(&nm_i->nat_tree_lock);
Jaegeuk Kim's avatar
Jaegeuk Kim committed
331 332
}

333
int try_to_free_nats(struct f2fs_sb_info *sbi, int nr_shrink)
Jaegeuk Kim's avatar
Jaegeuk Kim committed
334 335
{
	struct f2fs_nm_info *nm_i = NM_I(sbi);
Jaegeuk Kim's avatar
Jaegeuk Kim committed
336
	int nr = nr_shrink;
Jaegeuk Kim's avatar
Jaegeuk Kim committed
337

Jaegeuk Kim's avatar
Jaegeuk Kim committed
338
	if (!down_write_trylock(&nm_i->nat_tree_lock))
Jaegeuk Kim's avatar
Jaegeuk Kim committed
339 340 341 342 343 344 345 346 347
		return 0;

	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--;
	}
348
	up_write(&nm_i->nat_tree_lock);
Jaegeuk Kim's avatar
Jaegeuk Kim committed
349
	return nr - nr_shrink;
Jaegeuk Kim's avatar
Jaegeuk Kim committed
350 351
}

Jaegeuk Kim's avatar
Jaegeuk Kim committed
352
/*
arter97's avatar
arter97 committed
353
 * This function always returns success
Jaegeuk Kim's avatar
Jaegeuk Kim committed
354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369
 */
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;

	ni->nid = nid;

	/* Check nat cache */
370
	down_read(&nm_i->nat_tree_lock);
Jaegeuk Kim's avatar
Jaegeuk Kim committed
371 372 373 374 375 376
	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);
	}
377
	up_read(&nm_i->nat_tree_lock);
Jaegeuk Kim's avatar
Jaegeuk Kim committed
378 379 380
	if (e)
		return;

381 382
	memset(&ne, 0, sizeof(struct f2fs_nat_entry));

Jaegeuk Kim's avatar
Jaegeuk Kim committed
383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404
	/* 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);
}

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

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

500
	level = get_node_path(F2FS_I(dn->inode), index, offset, noffset);
Jaegeuk Kim's avatar
Jaegeuk Kim committed
501 502

	nids[0] = dn->inode->i_ino;
503
	npage[0] = dn->inode_page;
Jaegeuk Kim's avatar
Jaegeuk Kim committed
504

505 506 507 508 509
	if (!npage[0]) {
		npage[0] = get_node_page(sbi, nids[0]);
		if (IS_ERR(npage[0]))
			return PTR_ERR(npage[0]);
	}
510 511 512

	/* if inline_data is set, should not report any block indices */
	if (f2fs_has_inline_data(dn->inode) && index) {
513
		err = -ENOENT;
514 515 516 517
		f2fs_put_page(npage[0], 1);
		goto release_out;
	}

Jaegeuk Kim's avatar
Jaegeuk Kim committed
518
	parent = npage[0];
519 520
	if (level != 0)
		nids[1] = get_nid(parent, offset[0], true);
Jaegeuk Kim's avatar
Jaegeuk Kim committed
521 522 523 524 525 526 527
	dn->inode_page = npage[0];
	dn->inode_page_locked = true;

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

528
		if (!nids[i] && mode == ALLOC_NODE) {
Jaegeuk Kim's avatar
Jaegeuk Kim committed
529 530 531 532 533 534 535
			/* alloc new node */
			if (!alloc_nid(sbi, &(nids[i]))) {
				err = -ENOSPC;
				goto release_pages;
			}

			dn->nid = nids[i];
536
			npage[i] = new_node_page(dn, noffset[i], NULL);
Jaegeuk Kim's avatar
Jaegeuk Kim committed
537 538 539 540 541 542 543 544
			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]);
545
			dn->node_changed = true;
Jaegeuk Kim's avatar
Jaegeuk Kim committed
546
			done = true;
547
		} else if (mode == LOOKUP_NODE_RA && i == level && level > 1) {
Jaegeuk Kim's avatar
Jaegeuk Kim committed
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 582 583 584 585 586 587 588 589 590 591 592
			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)
{
593
	struct f2fs_sb_info *sbi = F2FS_I_SB(dn->inode);
Jaegeuk Kim's avatar
Jaegeuk Kim committed
594 595 596
	struct node_info ni;

	get_node_info(sbi, dn->nid, &ni);
597
	if (dn->inode->i_blocks == 0) {
598
		f2fs_bug_on(sbi, ni.blk_addr != NULL_ADDR);
599 600
		goto invalidate;
	}
601
	f2fs_bug_on(sbi, ni.blk_addr == NULL_ADDR);
Jaegeuk Kim's avatar
Jaegeuk Kim committed
602 603

	/* Deallocate node address */
604
	invalidate_blocks(sbi, ni.blk_addr);
605
	dec_valid_node_count(sbi, dn->inode);
606
	set_node_addr(sbi, &ni, NULL_ADDR, false);
Jaegeuk Kim's avatar
Jaegeuk Kim committed
607 608 609 610 611 612 613

	if (dn->nid == dn->inode->i_ino) {
		remove_orphan_inode(sbi, dn->nid);
		dec_valid_inode_count(sbi);
	} else {
		sync_inode_page(dn);
	}
614
invalidate:
Jaegeuk Kim's avatar
Jaegeuk Kim committed
615
	clear_node_page_dirty(dn->node_page);
616
	set_sbi_flag(sbi, SBI_IS_DIRTY);
Jaegeuk Kim's avatar
Jaegeuk Kim committed
617 618

	f2fs_put_page(dn->node_page, 1);
619 620 621 622

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

Jaegeuk Kim's avatar
Jaegeuk Kim committed
623
	dn->node_page = NULL;
624
	trace_f2fs_truncate_node(dn->inode, dn->nid, ni.blk_addr);
Jaegeuk Kim's avatar
Jaegeuk Kim committed
625 626 627 628 629 630 631 632 633 634
}

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

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

	/* get direct node */
635
	page = get_node_page(F2FS_I_SB(dn->inode), dn->nid);
Jaegeuk Kim's avatar
Jaegeuk Kim committed
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 662
	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;

663 664
	trace_f2fs_truncate_nodes_enter(dn->inode, dn->nid, dn->data_blkaddr);

665
	page = get_node_page(F2FS_I_SB(dn->inode), dn->nid);
666 667
	if (IS_ERR(page)) {
		trace_f2fs_truncate_nodes_exit(dn->inode, PTR_ERR(page));
Jaegeuk Kim's avatar
Jaegeuk Kim committed
668
		return PTR_ERR(page);
669
	}
Jaegeuk Kim's avatar
Jaegeuk Kim committed
670

671
	rn = F2FS_NODE(page);
Jaegeuk Kim's avatar
Jaegeuk Kim committed
672 673 674 675 676 677 678 679 680 681
	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);
682
			dn->node_changed = true;
Jaegeuk Kim's avatar
Jaegeuk Kim committed
683 684 685 686 687 688 689 690 691 692 693 694 695
		}
	} 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);
696
				dn->node_changed = true;
Jaegeuk Kim's avatar
Jaegeuk Kim committed
697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712
				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);
	}
713
	trace_f2fs_truncate_nodes_exit(dn->inode, freed);
Jaegeuk Kim's avatar
Jaegeuk Kim committed
714 715 716 717
	return freed;

out_err:
	f2fs_put_page(page, 1);
718
	trace_f2fs_truncate_nodes_exit(dn->inode, ret);
Jaegeuk Kim's avatar
Jaegeuk Kim committed
719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736
	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 */
737
	for (i = 0; i < idx + 1; i++) {
arter97's avatar
arter97 committed
738
		/* reference count'll be increased */
739
		pages[i] = get_node_page(F2FS_I_SB(dn->inode), nid[i]);
Jaegeuk Kim's avatar
Jaegeuk Kim committed
740 741
		if (IS_ERR(pages[i])) {
			err = PTR_ERR(pages[i]);
742
			idx = i - 1;
Jaegeuk Kim's avatar
Jaegeuk Kim committed
743 744 745 746 747 748
			goto fail;
		}
		nid[i + 1] = get_nid(pages[i], offset[i + 1], false);
	}

	/* free direct nodes linked to a partial indirect node */
749
	for (i = offset[idx + 1]; i < NIDS_PER_BLOCK; i++) {
Jaegeuk Kim's avatar
Jaegeuk Kim committed
750 751 752 753 754 755 756 757
		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);
758
		dn->node_changed = true;
Jaegeuk Kim's avatar
Jaegeuk Kim committed
759 760
	}

761
	if (offset[idx + 1] == 0) {
Jaegeuk Kim's avatar
Jaegeuk Kim committed
762 763 764 765 766 767 768
		dn->node_page = pages[idx];
		dn->nid = nid[idx];
		truncate_node(dn);
	} else {
		f2fs_put_page(pages[idx], 1);
	}
	offset[idx]++;
769 770
	offset[idx + 1] = 0;
	idx--;
Jaegeuk Kim's avatar
Jaegeuk Kim committed
771
fail:
772
	for (i = idx; i >= 0; i--)
Jaegeuk Kim's avatar
Jaegeuk Kim committed
773
		f2fs_put_page(pages[i], 1);
774 775 776

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

Jaegeuk Kim's avatar
Jaegeuk Kim committed
777 778 779
	return err;
}

Jaegeuk Kim's avatar
Jaegeuk Kim committed
780
/*
Jaegeuk Kim's avatar
Jaegeuk Kim committed
781 782 783 784
 * All the block addresses of data and nodes should be nullified.
 */
int truncate_inode_blocks(struct inode *inode, pgoff_t from)
{
785
	struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
Jaegeuk Kim's avatar
Jaegeuk Kim committed
786 787
	int err = 0, cont = 1;
	int level, offset[4], noffset[4];
Jaegeuk Kim's avatar
Jaegeuk Kim committed
788
	unsigned int nofs = 0;
789
	struct f2fs_inode *ri;
Jaegeuk Kim's avatar
Jaegeuk Kim committed
790 791 792
	struct dnode_of_data dn;
	struct page *page;

793 794
	trace_f2fs_truncate_inode_blocks_enter(inode, from);

795
	level = get_node_path(F2FS_I(inode), from, offset, noffset);
796
restart:
Jaegeuk Kim's avatar
Jaegeuk Kim committed
797
	page = get_node_page(sbi, inode->i_ino);
798 799
	if (IS_ERR(page)) {
		trace_f2fs_truncate_inode_blocks_exit(inode, PTR_ERR(page));
Jaegeuk Kim's avatar
Jaegeuk Kim committed
800
		return PTR_ERR(page);
801
	}
Jaegeuk Kim's avatar
Jaegeuk Kim committed
802 803 804 805

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

806
	ri = F2FS_INODE(page);
Jaegeuk Kim's avatar
Jaegeuk Kim committed
807 808 809 810 811 812 813 814 815
	switch (level) {
	case 0:
	case 1:
		nofs = noffset[1];
		break;
	case 2:
		nofs = noffset[1];
		if (!offset[level - 1])
			goto skip_partial;
816
		err = truncate_partial_nodes(&dn, ri, offset, level);
Jaegeuk Kim's avatar
Jaegeuk Kim committed
817 818 819 820 821 822 823 824
		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;
825
		err = truncate_partial_nodes(&dn, ri, offset, level);
Jaegeuk Kim's avatar
Jaegeuk Kim committed
826 827 828 829 830 831 832 833 834
		if (err < 0 && err != -ENOENT)
			goto fail;
		break;
	default:
		BUG();
	}

skip_partial:
	while (cont) {
835
		dn.nid = le32_to_cpu(ri->i_nid[offset[0] - NODE_DIR1_BLOCK]);
Jaegeuk Kim's avatar
Jaegeuk Kim committed
836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857
		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 &&
858
				ri->i_nid[offset[0] - NODE_DIR1_BLOCK]) {
Jaegeuk Kim's avatar
Jaegeuk Kim committed
859
			lock_page(page);
860
			if (unlikely(page->mapping != NODE_MAPPING(sbi))) {
861 862 863
				f2fs_put_page(page, 1);
				goto restart;
			}
864
			f2fs_wait_on_page_writeback(page, NODE);
865
			ri->i_nid[offset[0] - NODE_DIR1_BLOCK] = 0;
Jaegeuk Kim's avatar
Jaegeuk Kim committed
866 867 868 869 870 871 872 873 874
			set_page_dirty(page);
			unlock_page(page);
		}
		offset[1] = 0;
		offset[0]++;
		nofs += err;
	}
fail:
	f2fs_put_page(page, 0);
875
	trace_f2fs_truncate_inode_blocks_exit(inode, err);
Jaegeuk Kim's avatar
Jaegeuk Kim committed
876 877 878
	return err > 0 ? 0 : err;
}

879 880
int truncate_xattr_node(struct inode *inode, struct page *page)
{
881
	struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
882 883 884 885 886 887 888 889 890 891 892 893
	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;
Jaegeuk Kim's avatar
Jaegeuk Kim committed
894 895 896 897

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

898 899 900
	set_new_dnode(&dn, inode, page, npage, nid);

	if (page)
901
		dn.inode_page_locked = true;
902 903 904 905
	truncate_node(&dn);
	return 0;
}

906
/*
Chao Yu's avatar
Chao Yu committed
907 908
 * Caller should grab and release a rwsem by calling f2fs_lock_op() and
 * f2fs_unlock_op().
909
 */
Chao Yu's avatar
Chao Yu committed
910
int remove_inode_page(struct inode *inode)
Jaegeuk Kim's avatar
Jaegeuk Kim committed
911 912
{
	struct dnode_of_data dn;
Chao Yu's avatar
Chao Yu committed
913
	int err;
Jaegeuk Kim's avatar
Jaegeuk Kim committed
914

915
	set_new_dnode(&dn, inode, NULL, NULL, inode->i_ino);
Chao Yu's avatar
Chao Yu committed
916 917 918
	err = get_dnode_of_data(&dn, 0, LOOKUP_NODE);
	if (err)
		return err;
Jaegeuk Kim's avatar
Jaegeuk Kim committed
919

Chao Yu's avatar
Chao Yu committed
920 921
	err = truncate_xattr_node(inode, dn.inode_page);
	if (err) {
922
		f2fs_put_dnode(&dn);
Chao Yu's avatar
Chao Yu committed
923
		return err;
Jaegeuk Kim's avatar
Jaegeuk Kim committed
924
	}
925 926 927 928 929 930

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

arter97's avatar
arter97 committed
931
	/* 0 is possible, after f2fs_new_inode() has failed */
932 933
	f2fs_bug_on(F2FS_I_SB(inode),
			inode->i_blocks != 0 && inode->i_blocks != 1);
934 935

	/* will put inode & node pages */
936
	truncate_node(&dn);
Chao Yu's avatar
Chao Yu committed
937
	return 0;
Jaegeuk Kim's avatar
Jaegeuk Kim committed
938 939
}

940
struct page *new_inode_page(struct inode *inode)
Jaegeuk Kim's avatar
Jaegeuk Kim committed
941 942 943 944 945
{
	struct dnode_of_data dn;

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

	/* caller should f2fs_put_page(page, 1); */
948
	return new_node_page(&dn, 0, NULL);
Jaegeuk Kim's avatar
Jaegeuk Kim committed
949 950
}

951 952
struct page *new_node_page(struct dnode_of_data *dn,
				unsigned int ofs, struct page *ipage)
Jaegeuk Kim's avatar
Jaegeuk Kim committed
953
{
954
	struct f2fs_sb_info *sbi = F2FS_I_SB(dn->inode);
Jaegeuk Kim's avatar
Jaegeuk Kim committed
955 956 957 958
	struct node_info old_ni, new_ni;
	struct page *page;
	int err;

959
	if (unlikely(is_inode_flag_set(F2FS_I(dn->inode), FI_NO_ALLOC)))
Jaegeuk Kim's avatar
Jaegeuk Kim committed
960 961
		return ERR_PTR(-EPERM);

962
	page = grab_cache_page(NODE_MAPPING(sbi), dn->nid);
Jaegeuk Kim's avatar
Jaegeuk Kim committed
963 964 965
	if (!page)
		return ERR_PTR(-ENOMEM);

966
	if (unlikely(!inc_valid_node_count(sbi, dn->inode))) {
967 968 969
		err = -ENOSPC;
		goto fail;
	}
Jaegeuk Kim's avatar
Jaegeuk Kim committed
970

971
	get_node_info(sbi, dn->nid, &old_ni);
Jaegeuk Kim's avatar
Jaegeuk Kim committed
972 973

	/* Reinitialize old_ni with new node page */
974
	f2fs_bug_on(sbi, old_ni.blk_addr != NULL_ADDR);
Jaegeuk Kim's avatar
Jaegeuk Kim committed
975 976
	new_ni = old_ni;
	new_ni.ino = dn->inode->i_ino;
977
	set_node_addr(sbi, &new_ni, NEW_ADDR, false);
978

979
	f2fs_wait_on_page_writeback(page, NODE);
980
	fill_node_footer(page, dn->nid, dn->inode->i_ino, ofs, true);
981
	set_cold_node(dn->inode, page);
982 983
	SetPageUptodate(page);
	set_page_dirty(page);
Jaegeuk Kim's avatar
Jaegeuk Kim committed
984

985
	if (f2fs_has_xattr_block(ofs))
986 987
		F2FS_I(dn->inode)->i_xattr_nid = dn->nid;

Jaegeuk Kim's avatar
Jaegeuk Kim committed
988
	dn->node_page = page;
989 990 991 992
	if (ipage)
		update_inode(dn->inode, ipage);
	else
		sync_inode_page(dn);
Jaegeuk Kim's avatar
Jaegeuk Kim committed
993 994 995 996 997 998
	if (ofs == 0)
		inc_valid_inode_count(sbi);

	return page;

fail:
999
	clear_node_page_dirty(page);
Jaegeuk Kim's avatar
Jaegeuk Kim committed
1000 1001 1002 1003
	f2fs_put_page(page, 1);
	return ERR_PTR(err);
}

1004 1005 1006
/*
 * Caller should do after getting the following values.
 * 0: f2fs_put_page(page, 0)
1007
 * LOCKED_PAGE or error: f2fs_put_page(page, 1)
1008
 */
1009
static int read_node_page(struct page *page, int rw)
Jaegeuk Kim's avatar
Jaegeuk Kim committed
1010
{
1011
	struct f2fs_sb_info *sbi = F2FS_P_SB(page);