fsck.c revision 269eac2e0346e92fa1428bbfbc3fa50233f8c4ef
1/**
2 * fsck.c
3 *
4 * Copyright (c) 2013 Samsung Electronics Co., Ltd.
5 *             http://www.samsung.com/
6 *
7 * This program is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License version 2 as
9 * published by the Free Software Foundation.
10 */
11#include "fsck.h"
12
13char *tree_mark;
14uint32_t tree_mark_size = 256;
15
16static inline int f2fs_set_main_bitmap(struct f2fs_sb_info *sbi, u32 blk)
17{
18	struct f2fs_fsck *fsck = F2FS_FSCK(sbi);
19
20	return f2fs_set_bit(BLKOFF_FROM_MAIN(sbi, blk), fsck->main_area_bitmap);
21}
22
23static inline int f2fs_test_main_bitmap(struct f2fs_sb_info *sbi, u32 blk)
24{
25	struct f2fs_fsck *fsck = F2FS_FSCK(sbi);
26
27	return f2fs_test_bit(BLKOFF_FROM_MAIN(sbi, blk),
28						fsck->main_area_bitmap);
29}
30
31static inline int f2fs_test_sit_bitmap(struct f2fs_sb_info *sbi, u32 blk)
32{
33	struct f2fs_fsck *fsck = F2FS_FSCK(sbi);
34
35	return f2fs_test_bit(BLKOFF_FROM_MAIN(sbi, blk), fsck->sit_area_bitmap);
36}
37
38static int add_into_hard_link_list(struct f2fs_sb_info *sbi,
39						u32 nid, u32 link_cnt)
40{
41	struct f2fs_fsck *fsck = F2FS_FSCK(sbi);
42	struct hard_link_node *node = NULL, *tmp = NULL, *prev = NULL;
43
44	node = calloc(sizeof(struct hard_link_node), 1);
45	ASSERT(node != NULL);
46
47	node->nid = nid;
48	node->links = link_cnt;
49	node->next = NULL;
50
51	if (fsck->hard_link_list_head == NULL) {
52		fsck->hard_link_list_head = node;
53		goto out;
54	}
55
56	tmp = fsck->hard_link_list_head;
57
58	/* Find insertion position */
59	while (tmp && (nid < tmp->nid)) {
60		ASSERT(tmp->nid != nid);
61		prev = tmp;
62		tmp = tmp->next;
63	}
64
65	if (tmp == fsck->hard_link_list_head) {
66		node->next = tmp;
67		fsck->hard_link_list_head = node;
68	} else {
69		prev->next = node;
70		node->next = tmp;
71	}
72
73out:
74	DBG(2, "ino[0x%x] has hard links [0x%x]\n", nid, link_cnt);
75	return 0;
76}
77
78static int find_and_dec_hard_link_list(struct f2fs_sb_info *sbi, u32 nid)
79{
80	struct f2fs_fsck *fsck = F2FS_FSCK(sbi);
81	struct hard_link_node *node = NULL, *prev = NULL;
82
83	if (fsck->hard_link_list_head == NULL)
84		return -EINVAL;
85
86	node = fsck->hard_link_list_head;
87
88	while (node && (nid < node->nid)) {
89		prev = node;
90		node = node->next;
91	}
92
93	if (node == NULL || (nid != node->nid))
94		return -EINVAL;
95
96	/* Decrease link count */
97	node->links = node->links - 1;
98
99	/* if link count becomes one, remove the node */
100	if (node->links == 1) {
101		if (fsck->hard_link_list_head == node)
102			fsck->hard_link_list_head = node->next;
103		else
104			prev->next = node->next;
105		free(node);
106	}
107	return 0;
108}
109
110static int is_valid_ssa_node_blk(struct f2fs_sb_info *sbi, u32 nid,
111							u32 blk_addr)
112{
113	int ret = 0;
114	struct f2fs_summary sum_entry;
115
116	ret = get_sum_entry(sbi, blk_addr, &sum_entry);
117	ASSERT(ret >= 0);
118
119	if (ret == SEG_TYPE_DATA || ret == SEG_TYPE_CUR_DATA) {
120		ASSERT_MSG("Summary footer is not for node segment\n");
121	} else if (ret == SEG_TYPE_NODE) {
122		if (le32_to_cpu(sum_entry.nid) != nid) {
123			DBG(0, "nid                       [0x%x]\n", nid);
124			DBG(0, "target blk_addr           [0x%x]\n", blk_addr);
125			DBG(0, "summary blk_addr          [0x%x]\n",
126					GET_SUM_BLKADDR(sbi,
127						GET_SEGNO(sbi, blk_addr)));
128			DBG(0, "seg no / offset           [0x%x / 0x%x]\n",
129					GET_SEGNO(sbi, blk_addr),
130						OFFSET_IN_SEG(sbi, blk_addr));
131			DBG(0, "summary_entry.nid         [0x%x]\n",
132					le32_to_cpu(sum_entry.nid));
133			DBG(0, "--> node block's nid      [0x%x]\n", nid);
134			ASSERT_MSG("Invalid node seg summary\n");
135			return -EINVAL;
136		}
137		return 0;
138	} else if (ret == SEG_TYPE_CUR_NODE) {
139		/* current node segment has no ssa */
140		return 0;
141	} else {
142		ASSERT_MSG("Invalid return value of 'get_sum_entry'");
143	}
144	return -EINVAL;
145}
146
147static int is_valid_ssa_data_blk(struct f2fs_sb_info *sbi, u32 blk_addr,
148		u32 parent_nid, u16 idx_in_node, u8 version)
149{
150	int ret = 0;
151	struct f2fs_summary sum_entry;
152
153	ret = get_sum_entry(sbi, blk_addr, &sum_entry);
154	ASSERT(ret == SEG_TYPE_DATA || ret == SEG_TYPE_CUR_DATA);
155
156	if (le32_to_cpu(sum_entry.nid) != parent_nid ||
157			sum_entry.version != version ||
158			le16_to_cpu(sum_entry.ofs_in_node) != idx_in_node) {
159
160		DBG(0, "summary_entry.nid         [0x%x]\n",
161					le32_to_cpu(sum_entry.nid));
162		DBG(0, "summary_entry.version     [0x%x]\n",
163					sum_entry.version);
164		DBG(0, "summary_entry.ofs_in_node [0x%x]\n",
165					le16_to_cpu(sum_entry.ofs_in_node));
166		DBG(0, "parent nid                [0x%x]\n", parent_nid);
167		DBG(0, "version from nat          [0x%x]\n", version);
168		DBG(0, "idx in parent node        [0x%x]\n", idx_in_node);
169
170		DBG(0, "Target data block addr    [0x%x]\n", blk_addr);
171		ASSERT_MSG("Invalid data seg summary\n");
172	}
173	return 1;
174}
175
176static int sanity_check_nid(struct f2fs_sb_info *sbi, u32 nid,
177			struct f2fs_node *node_blk,
178			enum FILE_TYPE ftype, enum NODE_TYPE ntype,
179			struct node_info *ni)
180{
181	struct f2fs_fsck *fsck = F2FS_FSCK(sbi);
182	int ret;
183
184	if (!IS_VALID_NID(sbi, nid)) {
185		ASSERT_MSG("nid is not valid. [0x%x]", nid);
186		return -EINVAL;
187	}
188
189	get_node_info(sbi, nid, ni);
190	if (ni->blk_addr == NEW_ADDR) {
191		ASSERT_MSG("nid is NEW_ADDR. [0x%x]", nid);
192		return -EINVAL;
193	}
194
195	if (!IS_VALID_BLK_ADDR(sbi, ni->blk_addr)) {
196		ASSERT_MSG("blkaddres is not valid. [0x%x]", ni->blk_addr);
197		return -EINVAL;
198	}
199
200	if (is_valid_ssa_node_blk(sbi, nid, ni->blk_addr)) {
201		ASSERT_MSG("summary node block is not valid. [0x%x]", nid);
202		return -EINVAL;
203	}
204
205	ret = dev_read_block(node_blk, ni->blk_addr);
206	ASSERT(ret >= 0);
207
208	if (ntype == TYPE_INODE &&
209			node_blk->footer.nid != node_blk->footer.ino) {
210		ASSERT_MSG("nid[0x%x] footer.nid[0x%x] footer.ino[0x%x]",
211				nid, le32_to_cpu(node_blk->footer.nid),
212				le32_to_cpu(node_blk->footer.ino));
213		return -EINVAL;
214	}
215	if (ntype != TYPE_INODE &&
216			node_blk->footer.nid == node_blk->footer.ino) {
217		ASSERT_MSG("nid[0x%x] footer.nid[0x%x] footer.ino[0x%x]",
218				nid, le32_to_cpu(node_blk->footer.nid),
219				le32_to_cpu(node_blk->footer.ino));
220		return -EINVAL;
221	}
222
223	if (le32_to_cpu(node_blk->footer.nid) != nid) {
224		ASSERT_MSG("nid[0x%x] blk_addr[0x%x] footer.nid[0x%x]",
225				nid, ni->blk_addr,
226				le32_to_cpu(node_blk->footer.nid));
227		return -EINVAL;
228	}
229
230	if (ntype == TYPE_XATTR) {
231		u32 flag = le32_to_cpu(node_blk->footer.flag);
232
233		if ((flag >> OFFSET_BIT_SHIFT) != XATTR_NODE_OFFSET) {
234			ASSERT_MSG("xnid[0x%x] has wrong ofs:[0x%x]",
235					nid, flag);
236			return -EINVAL;
237		}
238	}
239
240	if ((ntype == TYPE_INODE && ftype == F2FS_FT_DIR) ||
241			(ntype == TYPE_XATTR && ftype == F2FS_FT_XATTR)) {
242		/* not included '.' & '..' */
243		if (f2fs_test_main_bitmap(sbi, ni->blk_addr) != 0) {
244			ASSERT_MSG("Duplicated node blk. nid[0x%x][0x%x]\n",
245					nid, ni->blk_addr);
246			return -EINVAL;
247		}
248	}
249
250	/* workaround to fix later */
251	if (ftype != F2FS_FT_ORPHAN ||
252			f2fs_test_bit(nid, fsck->nat_area_bitmap) != 0)
253		f2fs_clear_bit(nid, fsck->nat_area_bitmap);
254	else
255		ASSERT_MSG("orphan or xattr nid is duplicated [0x%x]\n",
256				nid);
257
258	if (f2fs_test_sit_bitmap(sbi, ni->blk_addr) == 0)
259		ASSERT_MSG("SIT bitmap is 0x0. blk_addr[0x%x]",
260				ni->blk_addr);
261
262	if (f2fs_test_main_bitmap(sbi, ni->blk_addr) == 0) {
263		fsck->chk.valid_blk_cnt++;
264		fsck->chk.valid_node_cnt++;
265	}
266	return 0;
267}
268
269int fsck_chk_node_blk(struct f2fs_sb_info *sbi, struct f2fs_inode *inode,
270		u32 nid, enum FILE_TYPE ftype, enum NODE_TYPE ntype,
271		u32 *blk_cnt)
272{
273	struct node_info ni;
274	struct f2fs_node *node_blk = NULL;
275
276	node_blk = (struct f2fs_node *)calloc(BLOCK_SZ, 1);
277	ASSERT(node_blk != NULL);
278
279	if (sanity_check_nid(sbi, nid, node_blk, ftype, ntype, &ni))
280		goto err;
281
282	if (ntype == TYPE_INODE) {
283		fsck_chk_inode_blk(sbi, nid, ftype, node_blk, blk_cnt, &ni);
284	} else {
285		f2fs_set_main_bitmap(sbi, ni.blk_addr);
286
287		switch (ntype) {
288		case TYPE_DIRECT_NODE:
289			fsck_chk_dnode_blk(sbi, inode, nid, ftype, node_blk,
290					blk_cnt, &ni);
291			break;
292		case TYPE_INDIRECT_NODE:
293			fsck_chk_idnode_blk(sbi, inode, ftype, node_blk,
294					blk_cnt);
295			break;
296		case TYPE_DOUBLE_INDIRECT_NODE:
297			fsck_chk_didnode_blk(sbi, inode, ftype, node_blk,
298					blk_cnt);
299			break;
300		default:
301			ASSERT(0);
302		}
303	}
304	free(node_blk);
305	return 0;
306err:
307	free(node_blk);
308	return -EINVAL;
309}
310
311/* start with valid nid and blkaddr */
312void fsck_chk_inode_blk(struct f2fs_sb_info *sbi, u32 nid,
313		enum FILE_TYPE ftype, struct f2fs_node *node_blk,
314		u32 *blk_cnt, struct node_info *ni)
315{
316	struct f2fs_fsck *fsck = F2FS_FSCK(sbi);
317	u32 child_cnt = 0, child_files = 0;
318	enum NODE_TYPE ntype;
319	u32 i_links = le32_to_cpu(node_blk->i.i_links);
320	u64 i_blocks = le64_to_cpu(node_blk->i.i_blocks);
321	unsigned int idx = 0;
322	int need_fix = 0;
323	int ret;
324
325	if (f2fs_test_main_bitmap(sbi, ni->blk_addr) == 0)
326		fsck->chk.valid_inode_cnt++;
327
328	if (ftype == F2FS_FT_DIR) {
329		f2fs_set_main_bitmap(sbi, ni->blk_addr);
330	} else {
331		if (f2fs_test_main_bitmap(sbi, ni->blk_addr) == 0) {
332			f2fs_set_main_bitmap(sbi, ni->blk_addr);
333			if (i_links > 1) {
334				/* First time. Create new hard link node */
335				add_into_hard_link_list(sbi, nid, i_links);
336				fsck->chk.multi_hard_link_files++;
337			}
338		} else {
339			DBG(3, "[0x%x] has hard links [0x%x]\n", nid, i_links);
340			if (find_and_dec_hard_link_list(sbi, nid)) {
341				ASSERT_MSG("[0x%x] needs more i_links=0x%x",
342						nid, i_links);
343				if (config.fix_cnt) {
344					node_blk->i.i_links =
345						cpu_to_le32(i_links + 1);
346					need_fix = 1;
347					FIX_MSG("File: 0x%x "
348						"i_links= 0x%x -> 0x%x",
349						nid, i_links, i_links + 1);
350				}
351			}
352			/* No need to go deep into the node */
353			return;
354		}
355	}
356
357	fsck_chk_xattr_blk(sbi, nid,
358			le32_to_cpu(node_blk->i.i_xattr_nid), blk_cnt);
359
360	if (ftype == F2FS_FT_CHRDEV || ftype == F2FS_FT_BLKDEV ||
361			ftype == F2FS_FT_FIFO || ftype == F2FS_FT_SOCK)
362		goto check;
363	if((node_blk->i.i_inline & F2FS_INLINE_DATA)){
364		DBG(3, "ino[0x%x] has inline data!\n", nid);
365		goto check;
366	}
367
368	/* check data blocks in inode */
369	for (idx = 0; idx < ADDRS_PER_INODE(&node_blk->i); idx++) {
370		if (le32_to_cpu(node_blk->i.i_addr[idx]) != 0) {
371			ret = fsck_chk_data_blk(sbi,
372					le32_to_cpu(node_blk->i.i_addr[idx]),
373					&child_cnt, &child_files,
374					(i_blocks == *blk_cnt),
375					ftype, nid, idx, ni->version);
376			if (!ret) {
377				*blk_cnt = *blk_cnt + 1;
378			} else if (config.fix_cnt) {
379				node_blk->i.i_addr[idx] = 0;
380				need_fix = 1;
381				FIX_MSG("[0x%x] i_addr[%d] = 0", nid, idx);
382			}
383		}
384	}
385
386	/* check node blocks in inode */
387	for (idx = 0; idx < 5; idx++) {
388		if (idx == 0 || idx == 1)
389			ntype = TYPE_DIRECT_NODE;
390		else if (idx == 2 || idx == 3)
391			ntype = TYPE_INDIRECT_NODE;
392		else if (idx == 4)
393			ntype = TYPE_DOUBLE_INDIRECT_NODE;
394		else
395			ASSERT(0);
396
397		if (le32_to_cpu(node_blk->i.i_nid[idx]) != 0) {
398			ret = fsck_chk_node_blk(sbi, &node_blk->i,
399					le32_to_cpu(node_blk->i.i_nid[idx]),
400					ftype, ntype, blk_cnt);
401			if (!ret) {
402				*blk_cnt = *blk_cnt + 1;
403			} else if (config.fix_cnt) {
404				node_blk->i.i_nid[idx] = 0;
405				need_fix = 1;
406				FIX_MSG("[0x%x] i_nid[%d] = 0", nid, idx);
407			}
408		}
409	}
410check:
411	if (ftype == F2FS_FT_DIR)
412		DBG(1, "Directory Inode: 0x%x [%s] depth: %d has %d files\n\n",
413				le32_to_cpu(node_blk->footer.ino),
414				node_blk->i.i_name,
415				le32_to_cpu(node_blk->i.i_current_depth),
416				child_files);
417	if (ftype == F2FS_FT_ORPHAN)
418		DBG(1, "Orphan Inode: 0x%x [%s] i_blocks: %u\n\n",
419				le32_to_cpu(node_blk->footer.ino),
420				node_blk->i.i_name,
421				(u32)i_blocks);
422
423	if (i_blocks != *blk_cnt) {
424		ASSERT_MSG("ino: 0x%x has i_blocks: %lu, but has %u blocks",
425				nid, i_blocks, *blk_cnt);
426		if (config.fix_cnt) {
427			node_blk->i.i_blocks = cpu_to_le64(*blk_cnt);
428			need_fix = 1;
429			FIX_MSG("[0x%x] i_blocks=0x%lx -> 0x%x",
430					nid, i_blocks, *blk_cnt);
431		}
432	}
433	if (ftype == F2FS_FT_DIR && i_links != child_cnt) {
434		ASSERT_MSG("ino: 0x%x has i_links: %u but real links: %u",
435				nid, i_links, child_cnt);
436		if (config.fix_cnt) {
437			node_blk->i.i_links = cpu_to_le32(child_cnt);
438			need_fix = 1;
439			FIX_MSG("Dir: 0x%x i_links= 0x%x -> 0x%x",
440						nid, i_links, child_cnt);
441		}
442	}
443
444	if (ftype == F2FS_FT_ORPHAN && i_links)
445		ASSERT_MSG("ino: 0x%x is orphan inode, but has i_links: %u",
446				nid, i_links);
447	if (need_fix) {
448		ret = dev_write_block(node_blk, ni->blk_addr);
449		ASSERT(ret >= 0);
450	}
451}
452
453int fsck_chk_dnode_blk(struct f2fs_sb_info *sbi, struct f2fs_inode *inode,
454		u32 nid, enum FILE_TYPE ftype, struct f2fs_node *node_blk,
455		u32 *blk_cnt, struct node_info *ni)
456{
457	int idx, ret;
458	u32 child_cnt = 0, child_files = 0;
459
460	for (idx = 0; idx < ADDRS_PER_BLOCK; idx++) {
461		if (le32_to_cpu(node_blk->dn.addr[idx]) == 0x0)
462			continue;
463		ret = fsck_chk_data_blk(sbi,
464			le32_to_cpu(node_blk->dn.addr[idx]),
465			&child_cnt, &child_files,
466			le64_to_cpu(inode->i_blocks) == *blk_cnt, ftype,
467			nid, idx, ni->version);
468		if (!ret)
469			*blk_cnt = *blk_cnt + 1;
470	}
471	return 0;
472}
473
474int fsck_chk_idnode_blk(struct f2fs_sb_info *sbi, struct f2fs_inode *inode,
475		enum FILE_TYPE ftype, struct f2fs_node *node_blk, u32 *blk_cnt)
476{
477	int ret;
478	int i = 0;
479
480	for (i = 0 ; i < NIDS_PER_BLOCK; i++) {
481		if (le32_to_cpu(node_blk->in.nid[i]) == 0x0)
482			continue;
483		ret = fsck_chk_node_blk(sbi, inode,
484				le32_to_cpu(node_blk->in.nid[i]),
485				ftype, TYPE_DIRECT_NODE, blk_cnt);
486		if (!ret)
487			*blk_cnt = *blk_cnt + 1;
488		else if (ret == -EINVAL)
489			printf("delete in.nid[i] = 0;\n");
490	}
491	return 0;
492}
493
494int fsck_chk_didnode_blk(struct f2fs_sb_info *sbi, struct f2fs_inode *inode,
495		enum FILE_TYPE ftype, struct f2fs_node *node_blk, u32 *blk_cnt)
496{
497	int i = 0;
498	int ret = 0;
499
500	for (i = 0; i < NIDS_PER_BLOCK; i++) {
501		if (le32_to_cpu(node_blk->in.nid[i]) == 0x0)
502			continue;
503		ret = fsck_chk_node_blk(sbi, inode,
504				le32_to_cpu(node_blk->in.nid[i]),
505				ftype, TYPE_INDIRECT_NODE, blk_cnt);
506		if (!ret)
507			*blk_cnt = *blk_cnt + 1;
508		else if (ret == -EINVAL)
509			printf("delete in.nid[i] = 0;\n");
510	}
511	return 0;
512}
513
514static void print_dentry(__u32 depth, __u8 *name,
515		struct f2fs_dentry_block *de_blk, int idx, int last_blk)
516{
517	int last_de = 0;
518	int next_idx = 0;
519	int name_len;
520	unsigned int i;
521	int bit_offset;
522
523	if (config.dbg_lv != -1)
524		return;
525
526	name_len = le16_to_cpu(de_blk->dentry[idx].name_len);
527	next_idx = idx + (name_len + F2FS_SLOT_LEN - 1) / F2FS_SLOT_LEN;
528
529	bit_offset = find_next_bit((unsigned long *)de_blk->dentry_bitmap,
530			NR_DENTRY_IN_BLOCK, next_idx);
531	if (bit_offset >= NR_DENTRY_IN_BLOCK && last_blk)
532		last_de = 1;
533
534	if (tree_mark_size <= depth) {
535		tree_mark_size *= 2;
536		tree_mark = realloc(tree_mark, tree_mark_size);
537	}
538
539	if (last_de)
540		tree_mark[depth] = '`';
541	else
542		tree_mark[depth] = '|';
543
544	if (tree_mark[depth - 1] == '`')
545		tree_mark[depth - 1] = ' ';
546
547
548	for (i = 1; i < depth; i++)
549		printf("%c   ", tree_mark[i]);
550	printf("%c-- %s 0x%x\n", last_de ? '`' : '|',
551				name, le32_to_cpu(de_blk->dentry[idx].ino));
552}
553
554int fsck_chk_dentry_blk(struct f2fs_sb_info *sbi, u32 blk_addr,
555		u32 *child_cnt, u32 *child_files, int last_blk)
556{
557	struct f2fs_fsck *fsck = F2FS_FSCK(sbi);
558	int i;
559	int ret = 0;
560	int dentries = 0;
561	u8 *name;
562	u32 hash_code;
563	u32 blk_cnt;
564	u16 name_len;;
565
566	enum FILE_TYPE ftype;
567	struct f2fs_dentry_block *de_blk;
568
569	de_blk = (struct f2fs_dentry_block *)calloc(BLOCK_SZ, 1);
570	ASSERT(de_blk != NULL);
571
572	ret = dev_read_block(de_blk, blk_addr);
573	ASSERT(ret >= 0);
574
575	fsck->dentry_depth++;
576
577	for (i = 0; i < NR_DENTRY_IN_BLOCK;) {
578		if (test_bit(i, (unsigned long *)de_blk->dentry_bitmap) == 0) {
579			i++;
580			continue;
581		}
582
583		name_len = le16_to_cpu(de_blk->dentry[i].name_len);
584		name = calloc(name_len + 1, 1);
585		memcpy(name, de_blk->filename[i], name_len);
586		hash_code = f2fs_dentry_hash((const unsigned char *)name,
587								name_len);
588
589		ASSERT(le32_to_cpu(de_blk->dentry[i].hash_code) == hash_code);
590
591		ftype = de_blk->dentry[i].file_type;
592
593		/* Becareful. 'dentry.file_type' is not imode. */
594		if (ftype == F2FS_FT_DIR) {
595			*child_cnt = *child_cnt + 1;
596			if ((name[0] == '.' && name_len == 1) ||
597				(name[0] == '.' && name[1] == '.' &&
598							name_len == 2)) {
599				i++;
600				free(name);
601				continue;
602			}
603		}
604
605		DBG(1, "[%3u]-[0x%x] name[%s] len[0x%x] ino[0x%x] type[0x%x]\n",
606				fsck->dentry_depth, i, name, name_len,
607				le32_to_cpu(de_blk->dentry[i].ino),
608				de_blk->dentry[i].file_type);
609
610		print_dentry(fsck->dentry_depth, name, de_blk, i, last_blk);
611
612		blk_cnt = 1;
613		ret = fsck_chk_node_blk(sbi,
614				NULL,
615				le32_to_cpu(de_blk->dentry[i].ino),
616				ftype,
617				TYPE_INODE,
618				&blk_cnt);
619
620		if (ret)
621			printf("TODO: delete dentry\n");
622
623		i += (name_len + F2FS_SLOT_LEN - 1) / F2FS_SLOT_LEN;
624		dentries++;
625		*child_files = *child_files + 1;
626		free(name);
627	}
628
629	DBG(1, "[%3d] Dentry Block [0x%x] Done : "
630				"dentries:%d in %d slots (len:%d)\n\n",
631			fsck->dentry_depth, blk_addr, dentries,
632			NR_DENTRY_IN_BLOCK, F2FS_NAME_LEN);
633	fsck->dentry_depth--;
634
635	free(de_blk);
636	return 0;
637}
638
639int fsck_chk_data_blk(struct f2fs_sb_info *sbi, u32 blk_addr,
640		u32 *child_cnt, u32 *child_files, int last_blk,
641		enum FILE_TYPE ftype, u32 parent_nid, u16 idx_in_node, u8 ver)
642{
643	struct f2fs_fsck *fsck = F2FS_FSCK(sbi);
644
645	/* Is it reserved block? */
646	if (blk_addr == NEW_ADDR) {
647		fsck->chk.valid_blk_cnt++;
648		return 0;
649	}
650
651	if (!IS_VALID_BLK_ADDR(sbi, blk_addr)) {
652		ASSERT_MSG("blkaddres is not valid. [0x%x]", blk_addr);
653		return 0;
654	}
655
656	is_valid_ssa_data_blk(sbi, blk_addr, parent_nid, idx_in_node, ver);
657
658	if (f2fs_test_sit_bitmap(sbi, blk_addr) == 0)
659		ASSERT_MSG("SIT bitmap is 0x0. blk_addr[0x%x]", blk_addr);
660
661	if (f2fs_test_main_bitmap(sbi, blk_addr) != 0)
662		ASSERT_MSG("Duplicated data [0x%x]. pnid[0x%x] idx[0x%x]",
663				blk_addr, parent_nid, idx_in_node);
664
665	f2fs_set_main_bitmap(sbi, blk_addr);
666
667	fsck->chk.valid_blk_cnt++;
668
669	if (ftype == F2FS_FT_DIR)
670		return fsck_chk_dentry_blk(sbi, blk_addr, child_cnt,
671				child_files, last_blk);
672	return 0;
673}
674
675void fsck_chk_orphan_node(struct f2fs_sb_info *sbi)
676{
677	u32 blk_cnt = 0;
678	block_t start_blk, orphan_blkaddr, i, j;
679	struct f2fs_orphan_block *orphan_blk;
680	struct f2fs_checkpoint *ckpt = F2FS_CKPT(sbi);
681
682	if (!is_set_ckpt_flags(ckpt, CP_ORPHAN_PRESENT_FLAG))
683		return;
684
685	if (config.fix_cnt)
686		return;
687
688	start_blk = __start_cp_addr(sbi) + 1 +
689		le32_to_cpu(F2FS_RAW_SUPER(sbi)->cp_payload);
690	orphan_blkaddr = __start_sum_addr(sbi) - 1;
691	orphan_blk = calloc(BLOCK_SZ, 1);
692
693	for (i = 0; i < orphan_blkaddr; i++) {
694		int ret = dev_read_block(orphan_blk, start_blk + i);
695
696		ASSERT(ret >= 0);
697
698		for (j = 0; j < le32_to_cpu(orphan_blk->entry_count); j++) {
699			nid_t ino = le32_to_cpu(orphan_blk->ino[j]);
700			DBG(1, "[%3d] ino [0x%x]\n", i, ino);
701			blk_cnt = 1;
702			ret = fsck_chk_node_blk(sbi, NULL, ino,
703					F2FS_FT_ORPHAN, TYPE_INODE, &blk_cnt);
704			if (ret == -EINVAL)
705				printf("TODO: nothing?\n");
706		}
707		memset(orphan_blk, 0, BLOCK_SZ);
708	}
709	free(orphan_blk);
710}
711
712void fsck_chk_xattr_blk(struct f2fs_sb_info *sbi, u32 ino,
713		u32 x_nid, u32 *blk_cnt)
714{
715	struct f2fs_node *node_blk = NULL;
716	struct node_info ni;
717
718	if (x_nid == 0x0)
719		return;
720
721	node_blk = (struct f2fs_node *)calloc(BLOCK_SZ, 1);
722	ASSERT(node_blk != NULL);
723
724	/* Sanity check */
725	if (sanity_check_nid(sbi, x_nid, node_blk,
726				F2FS_FT_XATTR, TYPE_XATTR, &ni)) {
727		/* TODO: drop xattr node */
728		printf("drop xattr node\n");
729		goto out;
730	}
731
732	*blk_cnt = *blk_cnt + 1;
733	f2fs_set_main_bitmap(sbi, ni.blk_addr);
734	DBG(2, "ino[0x%x] x_nid[0x%x]\n", ino, x_nid);
735out:
736	free(node_blk);
737}
738
739void fsck_init(struct f2fs_sb_info *sbi)
740{
741	struct f2fs_fsck *fsck = F2FS_FSCK(sbi);
742	struct f2fs_sm_info *sm_i = SM_I(sbi);
743
744	/*
745	 * We build three bitmap for main/sit/nat so that may check consistency
746	 * of filesystem.
747	 * 1. main_area_bitmap will be used to check whether all blocks of main
748	 *    area is used or not.
749	 * 2. nat_area_bitmap has bitmap information of used nid in NAT.
750	 * 3. sit_area_bitmap has bitmap information of used main block.
751	 * At Last sequence, we compare main_area_bitmap with sit_area_bitmap.
752	 */
753	fsck->nr_main_blks = sm_i->main_segments << sbi->log_blocks_per_seg;
754	fsck->main_area_bitmap_sz = (fsck->nr_main_blks + 7) / 8;
755	fsck->main_area_bitmap = calloc(fsck->main_area_bitmap_sz, 1);
756	ASSERT(fsck->main_area_bitmap != NULL);
757
758	build_nat_area_bitmap(sbi);
759
760	build_sit_area_bitmap(sbi);
761
762	tree_mark = calloc(tree_mark_size, 1);
763	ASSERT(tree_mark != NULL);
764}
765
766int fsck_verify(struct f2fs_sb_info *sbi)
767{
768	unsigned int i = 0;
769	int ret = 0;
770	u32 nr_unref_nid = 0;
771	struct f2fs_fsck *fsck = F2FS_FSCK(sbi);
772	struct hard_link_node *node = NULL;
773
774	printf("\n");
775
776	for (i = 0; i < fsck->nr_nat_entries; i++) {
777		if (f2fs_test_bit(i, fsck->nat_area_bitmap) != 0) {
778			printf("NID[0x%x] is unreachable\n", i);
779			nr_unref_nid++;
780		}
781	}
782
783	if (fsck->hard_link_list_head != NULL) {
784		node = fsck->hard_link_list_head;
785		while (node) {
786			printf("NID[0x%x] has [0x%x] more unreachable links\n",
787					node->nid, node->links);
788			node = node->next;
789		}
790		config.bug_on = 1;
791	}
792
793	printf("[FSCK] Unreachable nat entries                       ");
794	if (nr_unref_nid == 0x0) {
795		printf(" [Ok..] [0x%x]\n", nr_unref_nid);
796	} else {
797		printf(" [Fail] [0x%x]\n", nr_unref_nid);
798		ret = EXIT_ERR_CODE;
799		config.bug_on = 1;
800	}
801
802	printf("[FSCK] SIT valid block bitmap checking                ");
803	if (memcmp(fsck->sit_area_bitmap, fsck->main_area_bitmap,
804					fsck->sit_area_bitmap_sz) == 0x0) {
805		printf("[Ok..]\n");
806	} else {
807		printf("[Fail]\n");
808		ret = EXIT_ERR_CODE;
809		config.bug_on = 1;
810	}
811
812	printf("[FSCK] Hard link checking for regular file           ");
813	if (fsck->hard_link_list_head == NULL) {
814		printf(" [Ok..] [0x%x]\n", fsck->chk.multi_hard_link_files);
815	} else {
816		printf(" [Fail] [0x%x]\n", fsck->chk.multi_hard_link_files);
817		ret = EXIT_ERR_CODE;
818		config.bug_on = 1;
819	}
820
821	printf("[FSCK] valid_block_count matching with CP            ");
822	if (sbi->total_valid_block_count == fsck->chk.valid_blk_cnt) {
823		printf(" [Ok..] [0x%x]\n", (u32)fsck->chk.valid_blk_cnt);
824	} else {
825		printf(" [Fail] [0x%x]\n", (u32)fsck->chk.valid_blk_cnt);
826		ret = EXIT_ERR_CODE;
827		config.bug_on = 1;
828	}
829
830	printf("[FSCK] valid_node_count matcing with CP (de lookup)  ");
831	if (sbi->total_valid_node_count == fsck->chk.valid_node_cnt) {
832		printf(" [Ok..] [0x%x]\n", fsck->chk.valid_node_cnt);
833	} else {
834		printf(" [Fail] [0x%x]\n", fsck->chk.valid_node_cnt);
835		ret = EXIT_ERR_CODE;
836		config.bug_on = 1;
837	}
838
839	printf("[FSCK] valid_node_count matcing with CP (nat lookup) ");
840	if (sbi->total_valid_node_count == fsck->chk.valid_nat_entry_cnt) {
841		printf(" [Ok..] [0x%x]\n", fsck->chk.valid_nat_entry_cnt);
842	} else {
843		printf(" [Fail] [0x%x]\n", fsck->chk.valid_nat_entry_cnt);
844		ret = EXIT_ERR_CODE;
845		config.bug_on = 1;
846	}
847
848	printf("[FSCK] valid_inode_count matched with CP             ");
849	if (sbi->total_valid_inode_count == fsck->chk.valid_inode_cnt) {
850		printf(" [Ok..] [0x%x]\n", fsck->chk.valid_inode_cnt);
851	} else {
852		printf(" [Fail] [0x%x]\n", fsck->chk.valid_inode_cnt);
853		ret = EXIT_ERR_CODE;
854		config.bug_on = 1;
855	}
856	return ret;
857}
858
859void fsck_free(struct f2fs_sb_info *sbi)
860{
861	struct f2fs_fsck *fsck = F2FS_FSCK(sbi);
862	if (fsck->main_area_bitmap)
863		free(fsck->main_area_bitmap);
864
865	if (fsck->nat_area_bitmap)
866		free(fsck->nat_area_bitmap);
867
868	if (fsck->sit_area_bitmap)
869		free(fsck->sit_area_bitmap);
870
871	if (tree_mark)
872		free(tree_mark);
873}
874