fsck.c revision 866c86a6376598c1e72141de2805ba0f43e6daaa
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
118	if (ret != SEG_TYPE_NODE && ret != SEG_TYPE_CUR_NODE) {
119		ASSERT_MSG("Summary footer is not for node segment");
120		return -EINVAL;
121	}
122
123	if (le32_to_cpu(sum_entry.nid) != nid) {
124		DBG(0, "nid                       [0x%x]\n", nid);
125		DBG(0, "target blk_addr           [0x%x]\n", blk_addr);
126		DBG(0, "summary blk_addr          [0x%x]\n",
127					GET_SUM_BLKADDR(sbi,
128					GET_SEGNO(sbi, blk_addr)));
129		DBG(0, "seg no / offset           [0x%x / 0x%x]\n",
130					GET_SEGNO(sbi, blk_addr),
131					OFFSET_IN_SEG(sbi, blk_addr));
132		DBG(0, "summary_entry.nid         [0x%x]\n",
133					le32_to_cpu(sum_entry.nid));
134		DBG(0, "--> node block's nid      [0x%x]\n", nid);
135		ASSERT_MSG("Invalid node seg summary\n");
136		return -EINVAL;
137	}
138	return 0;
139}
140
141static int is_valid_ssa_data_blk(struct f2fs_sb_info *sbi, u32 blk_addr,
142		u32 parent_nid, u16 idx_in_node, u8 version)
143{
144	int ret = 0;
145	struct f2fs_summary sum_entry;
146
147	ret = get_sum_entry(sbi, blk_addr, &sum_entry);
148
149	if (ret != SEG_TYPE_DATA && ret != SEG_TYPE_CUR_DATA) {
150		ASSERT_MSG("Summary footer is not for data segment");
151		return -EINVAL;
152	}
153
154	if (le32_to_cpu(sum_entry.nid) != parent_nid ||
155			sum_entry.version != version ||
156			le16_to_cpu(sum_entry.ofs_in_node) != idx_in_node) {
157
158		DBG(0, "summary_entry.nid         [0x%x]\n",
159					le32_to_cpu(sum_entry.nid));
160		DBG(0, "summary_entry.version     [0x%x]\n",
161					sum_entry.version);
162		DBG(0, "summary_entry.ofs_in_node [0x%x]\n",
163					le16_to_cpu(sum_entry.ofs_in_node));
164		DBG(0, "parent nid                [0x%x]\n", parent_nid);
165		DBG(0, "version from nat          [0x%x]\n", version);
166		DBG(0, "idx in parent node        [0x%x]\n", idx_in_node);
167
168		DBG(0, "Target data block addr    [0x%x]\n", blk_addr);
169		ASSERT_MSG("Invalid data seg summary\n");
170		return -EINVAL;
171	}
172	return 0;
173}
174
175static int sanity_check_nid(struct f2fs_sb_info *sbi, u32 nid,
176			struct f2fs_node *node_blk,
177			enum FILE_TYPE ftype, enum NODE_TYPE ntype,
178			struct node_info *ni)
179{
180	struct f2fs_fsck *fsck = F2FS_FSCK(sbi);
181	int ret;
182
183	if (!IS_VALID_NID(sbi, nid)) {
184		ASSERT_MSG("nid is not valid. [0x%x]", nid);
185		return -EINVAL;
186	}
187
188	get_node_info(sbi, nid, ni);
189	if (ni->blk_addr == NEW_ADDR) {
190		ASSERT_MSG("nid is NEW_ADDR. [0x%x]", nid);
191		return -EINVAL;
192	}
193
194	if (!IS_VALID_BLK_ADDR(sbi, ni->blk_addr)) {
195		ASSERT_MSG("blkaddres is not valid. [0x%x]", ni->blk_addr);
196		return -EINVAL;
197	}
198
199	if (is_valid_ssa_node_blk(sbi, nid, ni->blk_addr)) {
200		ASSERT_MSG("summary node block is not valid. [0x%x]", nid);
201		return -EINVAL;
202	}
203
204	ret = dev_read_block(node_blk, ni->blk_addr);
205	ASSERT(ret >= 0);
206
207	if (ntype == TYPE_INODE &&
208			node_blk->footer.nid != node_blk->footer.ino) {
209		ASSERT_MSG("nid[0x%x] footer.nid[0x%x] footer.ino[0x%x]",
210				nid, le32_to_cpu(node_blk->footer.nid),
211				le32_to_cpu(node_blk->footer.ino));
212		return -EINVAL;
213	}
214	if (ntype != TYPE_INODE &&
215			node_blk->footer.nid == node_blk->footer.ino) {
216		ASSERT_MSG("nid[0x%x] footer.nid[0x%x] footer.ino[0x%x]",
217				nid, le32_to_cpu(node_blk->footer.nid),
218				le32_to_cpu(node_blk->footer.ino));
219		return -EINVAL;
220	}
221
222	if (le32_to_cpu(node_blk->footer.nid) != nid) {
223		ASSERT_MSG("nid[0x%x] blk_addr[0x%x] footer.nid[0x%x]",
224				nid, ni->blk_addr,
225				le32_to_cpu(node_blk->footer.nid));
226		return -EINVAL;
227	}
228
229	if (ntype == TYPE_XATTR) {
230		u32 flag = le32_to_cpu(node_blk->footer.flag);
231
232		if ((flag >> OFFSET_BIT_SHIFT) != XATTR_NODE_OFFSET) {
233			ASSERT_MSG("xnid[0x%x] has wrong ofs:[0x%x]",
234					nid, flag);
235			return -EINVAL;
236		}
237	}
238
239	if ((ntype == TYPE_INODE && ftype == F2FS_FT_DIR) ||
240			(ntype == TYPE_XATTR && ftype == F2FS_FT_XATTR)) {
241		/* not included '.' & '..' */
242		if (f2fs_test_main_bitmap(sbi, ni->blk_addr) != 0) {
243			ASSERT_MSG("Duplicated node blk. nid[0x%x][0x%x]\n",
244					nid, ni->blk_addr);
245			return -EINVAL;
246		}
247	}
248
249	/* workaround to fix later */
250	if (ftype != F2FS_FT_ORPHAN ||
251			f2fs_test_bit(nid, fsck->nat_area_bitmap) != 0)
252		f2fs_clear_bit(nid, fsck->nat_area_bitmap);
253	else
254		ASSERT_MSG("orphan or xattr nid is duplicated [0x%x]\n",
255				nid);
256
257	if (f2fs_test_sit_bitmap(sbi, ni->blk_addr) == 0)
258		ASSERT_MSG("SIT bitmap is 0x0. blk_addr[0x%x]",
259				ni->blk_addr);
260
261	if (f2fs_test_main_bitmap(sbi, ni->blk_addr) == 0) {
262		fsck->chk.valid_blk_cnt++;
263		fsck->chk.valid_node_cnt++;
264	}
265	return 0;
266}
267
268static int fsck_chk_xattr_blk(struct f2fs_sb_info *sbi, u32 ino,
269					u32 x_nid, u32 *blk_cnt)
270{
271	struct f2fs_node *node_blk = NULL;
272	struct node_info ni;
273	int ret = 0;
274
275	if (x_nid == 0x0)
276		return 0;
277
278	node_blk = (struct f2fs_node *)calloc(BLOCK_SZ, 1);
279	ASSERT(node_blk != NULL);
280
281	/* Sanity check */
282	if (sanity_check_nid(sbi, x_nid, node_blk,
283				F2FS_FT_XATTR, TYPE_XATTR, &ni)) {
284		ret = -EINVAL;
285		goto out;
286	}
287
288	*blk_cnt = *blk_cnt + 1;
289	f2fs_set_main_bitmap(sbi, ni.blk_addr);
290	DBG(2, "ino[0x%x] x_nid[0x%x]\n", ino, x_nid);
291out:
292	free(node_blk);
293	return ret;
294}
295
296int fsck_chk_node_blk(struct f2fs_sb_info *sbi, struct f2fs_inode *inode,
297		u32 nid, enum FILE_TYPE ftype, enum NODE_TYPE ntype,
298		u32 *blk_cnt)
299{
300	struct node_info ni;
301	struct f2fs_node *node_blk = NULL;
302
303	node_blk = (struct f2fs_node *)calloc(BLOCK_SZ, 1);
304	ASSERT(node_blk != NULL);
305
306	if (sanity_check_nid(sbi, nid, node_blk, ftype, ntype, &ni))
307		goto err;
308
309	if (ntype == TYPE_INODE) {
310		fsck_chk_inode_blk(sbi, nid, ftype, node_blk, blk_cnt, &ni);
311	} else {
312		f2fs_set_main_bitmap(sbi, ni.blk_addr);
313
314		switch (ntype) {
315		case TYPE_DIRECT_NODE:
316			fsck_chk_dnode_blk(sbi, inode, nid, ftype, node_blk,
317					blk_cnt, &ni);
318			break;
319		case TYPE_INDIRECT_NODE:
320			fsck_chk_idnode_blk(sbi, inode, ftype, node_blk,
321					blk_cnt);
322			break;
323		case TYPE_DOUBLE_INDIRECT_NODE:
324			fsck_chk_didnode_blk(sbi, inode, ftype, node_blk,
325					blk_cnt);
326			break;
327		default:
328			ASSERT(0);
329		}
330	}
331	free(node_blk);
332	return 0;
333err:
334	free(node_blk);
335	return -EINVAL;
336}
337
338/* start with valid nid and blkaddr */
339void fsck_chk_inode_blk(struct f2fs_sb_info *sbi, u32 nid,
340		enum FILE_TYPE ftype, struct f2fs_node *node_blk,
341		u32 *blk_cnt, struct node_info *ni)
342{
343	struct f2fs_fsck *fsck = F2FS_FSCK(sbi);
344	u32 child_cnt = 0, child_files = 0;
345	enum NODE_TYPE ntype;
346	u32 i_links = le32_to_cpu(node_blk->i.i_links);
347	u64 i_blocks = le64_to_cpu(node_blk->i.i_blocks);
348	unsigned int idx = 0;
349	int need_fix = 0;
350	int ret;
351
352	if (f2fs_test_main_bitmap(sbi, ni->blk_addr) == 0)
353		fsck->chk.valid_inode_cnt++;
354
355	if (ftype == F2FS_FT_DIR) {
356		f2fs_set_main_bitmap(sbi, ni->blk_addr);
357	} else {
358		if (f2fs_test_main_bitmap(sbi, ni->blk_addr) == 0) {
359			f2fs_set_main_bitmap(sbi, ni->blk_addr);
360			if (i_links > 1) {
361				/* First time. Create new hard link node */
362				add_into_hard_link_list(sbi, nid, i_links);
363				fsck->chk.multi_hard_link_files++;
364			}
365		} else {
366			DBG(3, "[0x%x] has hard links [0x%x]\n", nid, i_links);
367			if (find_and_dec_hard_link_list(sbi, nid)) {
368				ASSERT_MSG("[0x%x] needs more i_links=0x%x",
369						nid, i_links);
370				if (config.fix_on) {
371					node_blk->i.i_links =
372						cpu_to_le32(i_links + 1);
373					need_fix = 1;
374					FIX_MSG("File: 0x%x "
375						"i_links= 0x%x -> 0x%x",
376						nid, i_links, i_links + 1);
377				}
378			}
379			/* No need to go deep into the node */
380			return;
381		}
382	}
383
384	if (fsck_chk_xattr_blk(sbi, nid,
385			le32_to_cpu(node_blk->i.i_xattr_nid), blk_cnt) &&
386			config.fix_on) {
387		node_blk->i.i_xattr_nid = 0;
388		need_fix = 1;
389		FIX_MSG("Remove xattr block: 0x%x, x_nid = 0x%x",
390				nid, le32_to_cpu(node_blk->i.i_xattr_nid));
391	}
392
393	if (ftype == F2FS_FT_CHRDEV || ftype == F2FS_FT_BLKDEV ||
394			ftype == F2FS_FT_FIFO || ftype == F2FS_FT_SOCK)
395		goto check;
396	if((node_blk->i.i_inline & F2FS_INLINE_DATA)){
397		DBG(3, "ino[0x%x] has inline data!\n", nid);
398		goto check;
399	}
400	if((node_blk->i.i_inline & F2FS_INLINE_DENTRY)){
401		DBG(3, "ino[0x%x] has inline dentry!\n", nid);
402		ret = fsck_chk_inline_dentries(sbi, node_blk,
403					&child_cnt, &child_files);
404		if (ret < 0) {
405			/* should fix this bug all the time */
406			need_fix = 1;
407		}
408		goto check;
409	}
410
411	/* check data blocks in inode */
412	for (idx = 0; idx < ADDRS_PER_INODE(&node_blk->i); idx++) {
413		if (le32_to_cpu(node_blk->i.i_addr[idx]) != 0) {
414			ret = fsck_chk_data_blk(sbi,
415					le32_to_cpu(node_blk->i.i_addr[idx]),
416					&child_cnt, &child_files,
417					(i_blocks == *blk_cnt),
418					ftype, nid, idx, ni->version);
419			if (!ret) {
420				*blk_cnt = *blk_cnt + 1;
421			} else if (config.fix_on) {
422				node_blk->i.i_addr[idx] = 0;
423				need_fix = 1;
424				FIX_MSG("[0x%x] i_addr[%d] = 0", nid, idx);
425			}
426		}
427	}
428
429	/* check node blocks in inode */
430	for (idx = 0; idx < 5; idx++) {
431		if (idx == 0 || idx == 1)
432			ntype = TYPE_DIRECT_NODE;
433		else if (idx == 2 || idx == 3)
434			ntype = TYPE_INDIRECT_NODE;
435		else if (idx == 4)
436			ntype = TYPE_DOUBLE_INDIRECT_NODE;
437		else
438			ASSERT(0);
439
440		if (le32_to_cpu(node_blk->i.i_nid[idx]) != 0) {
441			ret = fsck_chk_node_blk(sbi, &node_blk->i,
442					le32_to_cpu(node_blk->i.i_nid[idx]),
443					ftype, ntype, blk_cnt);
444			if (!ret) {
445				*blk_cnt = *blk_cnt + 1;
446			} else if (config.fix_on) {
447				node_blk->i.i_nid[idx] = 0;
448				need_fix = 1;
449				FIX_MSG("[0x%x] i_nid[%d] = 0", nid, idx);
450			}
451		}
452	}
453check:
454	if (ftype == F2FS_FT_DIR)
455		DBG(1, "Directory Inode: 0x%x [%s] depth: %d has %d files\n\n",
456				le32_to_cpu(node_blk->footer.ino),
457				node_blk->i.i_name,
458				le32_to_cpu(node_blk->i.i_current_depth),
459				child_files);
460	if (ftype == F2FS_FT_ORPHAN)
461		DBG(1, "Orphan Inode: 0x%x [%s] i_blocks: %u\n\n",
462				le32_to_cpu(node_blk->footer.ino),
463				node_blk->i.i_name,
464				(u32)i_blocks);
465
466	if (i_blocks != *blk_cnt) {
467		ASSERT_MSG("ino: 0x%x has i_blocks: %08"PRIx64", "
468				"but has %u blocks",
469				nid, i_blocks, *blk_cnt);
470		if (config.fix_on) {
471			node_blk->i.i_blocks = cpu_to_le64(*blk_cnt);
472			need_fix = 1;
473			FIX_MSG("[0x%x] i_blocks=0x%08"PRIx64" -> 0x%x",
474					nid, i_blocks, *blk_cnt);
475		}
476	}
477	if (ftype == F2FS_FT_DIR && i_links != child_cnt) {
478		ASSERT_MSG("ino: 0x%x has i_links: %u but real links: %u",
479				nid, i_links, child_cnt);
480		if (config.fix_on) {
481			node_blk->i.i_links = cpu_to_le32(child_cnt);
482			need_fix = 1;
483			FIX_MSG("Dir: 0x%x i_links= 0x%x -> 0x%x",
484						nid, i_links, child_cnt);
485		}
486	}
487
488	if (ftype == F2FS_FT_ORPHAN && i_links)
489		ASSERT_MSG("ino: 0x%x is orphan inode, but has i_links: %u",
490				nid, i_links);
491	if (need_fix) {
492		ret = dev_write_block(node_blk, ni->blk_addr);
493		ASSERT(ret >= 0);
494	}
495}
496
497int fsck_chk_dnode_blk(struct f2fs_sb_info *sbi, struct f2fs_inode *inode,
498		u32 nid, enum FILE_TYPE ftype, struct f2fs_node *node_blk,
499		u32 *blk_cnt, struct node_info *ni)
500{
501	int idx, ret;
502	u32 child_cnt = 0, child_files = 0;
503
504	for (idx = 0; idx < ADDRS_PER_BLOCK; idx++) {
505		if (le32_to_cpu(node_blk->dn.addr[idx]) == 0x0)
506			continue;
507		ret = fsck_chk_data_blk(sbi,
508			le32_to_cpu(node_blk->dn.addr[idx]),
509			&child_cnt, &child_files,
510			le64_to_cpu(inode->i_blocks) == *blk_cnt, ftype,
511			nid, idx, ni->version);
512		if (!ret)
513			*blk_cnt = *blk_cnt + 1;
514	}
515	return 0;
516}
517
518int fsck_chk_idnode_blk(struct f2fs_sb_info *sbi, struct f2fs_inode *inode,
519		enum FILE_TYPE ftype, struct f2fs_node *node_blk, u32 *blk_cnt)
520{
521	int ret;
522	int i = 0;
523
524	for (i = 0 ; i < NIDS_PER_BLOCK; i++) {
525		if (le32_to_cpu(node_blk->in.nid[i]) == 0x0)
526			continue;
527		ret = fsck_chk_node_blk(sbi, inode,
528				le32_to_cpu(node_blk->in.nid[i]),
529				ftype, TYPE_DIRECT_NODE, blk_cnt);
530		if (!ret)
531			*blk_cnt = *blk_cnt + 1;
532		else if (ret == -EINVAL)
533			printf("delete in.nid[i] = 0;\n");
534	}
535	return 0;
536}
537
538int fsck_chk_didnode_blk(struct f2fs_sb_info *sbi, struct f2fs_inode *inode,
539		enum FILE_TYPE ftype, struct f2fs_node *node_blk, u32 *blk_cnt)
540{
541	int i = 0;
542	int ret = 0;
543
544	for (i = 0; i < NIDS_PER_BLOCK; i++) {
545		if (le32_to_cpu(node_blk->in.nid[i]) == 0x0)
546			continue;
547		ret = fsck_chk_node_blk(sbi, inode,
548				le32_to_cpu(node_blk->in.nid[i]),
549				ftype, TYPE_INDIRECT_NODE, blk_cnt);
550		if (!ret)
551			*blk_cnt = *blk_cnt + 1;
552		else if (ret == -EINVAL)
553			printf("delete in.nid[i] = 0;\n");
554	}
555	return 0;
556}
557
558static void print_dentry(__u32 depth, __u8 *name,
559		unsigned long *bitmap,
560		struct f2fs_dir_entry *dentry,
561		int max, int idx, int last_blk)
562{
563	int last_de = 0;
564	int next_idx = 0;
565	int name_len;
566	unsigned int i;
567	int bit_offset;
568
569	if (config.dbg_lv != -1)
570		return;
571
572	name_len = le16_to_cpu(dentry[idx].name_len);
573	next_idx = idx + (name_len + F2FS_SLOT_LEN - 1) / F2FS_SLOT_LEN;
574
575	bit_offset = find_next_bit(bitmap, max, next_idx);
576	if (bit_offset >= max && last_blk)
577		last_de = 1;
578
579	if (tree_mark_size <= depth) {
580		tree_mark_size *= 2;
581		tree_mark = realloc(tree_mark, tree_mark_size);
582	}
583
584	if (last_de)
585		tree_mark[depth] = '`';
586	else
587		tree_mark[depth] = '|';
588
589	if (tree_mark[depth - 1] == '`')
590		tree_mark[depth - 1] = ' ';
591
592
593	for (i = 1; i < depth; i++)
594		printf("%c   ", tree_mark[i]);
595	printf("%c-- %s 0x%x\n", last_de ? '`' : '|',
596				name, le32_to_cpu(dentry[idx].ino));
597}
598
599static int __chk_dentries(struct f2fs_sb_info *sbi, u32 *child_cnt,
600			u32* child_files,
601			unsigned long *bitmap,
602			struct f2fs_dir_entry *dentry,
603			__u8 (*filenames)[F2FS_SLOT_LEN],
604			int max, int last_blk)
605{
606	struct f2fs_fsck *fsck = F2FS_FSCK(sbi);
607	enum FILE_TYPE ftype;
608	int dentries = 0;
609	u32 blk_cnt;
610	u8 *name;
611	u32 hash_code;
612	u16 name_len;;
613	int ret = 0;
614	int fixed = 0;
615	int i;
616
617	for (i = 0; i < max;) {
618		if (test_bit(i, bitmap) == 0) {
619			i++;
620			continue;
621		}
622
623		name_len = le16_to_cpu(dentry[i].name_len);
624		name = calloc(name_len + 1, 1);
625		memcpy(name, filenames[i], name_len);
626		hash_code = f2fs_dentry_hash((const unsigned char *)name,
627								name_len);
628
629		/* fix hash_code made by old buggy code */
630		if (le32_to_cpu(dentry[i].hash_code) != hash_code) {
631			dentry[i].hash_code = hash_code;
632			fixed = 1;
633			FIX_MSG("hash_code[%d] of %s", i, name);
634		}
635
636		ftype = dentry[i].file_type;
637
638		/* Becareful. 'dentry.file_type' is not imode. */
639		if (ftype == F2FS_FT_DIR) {
640			*child_cnt = *child_cnt + 1;
641			if ((name[0] == '.' && name_len == 1) ||
642				(name[0] == '.' && name[1] == '.' &&
643							name_len == 2)) {
644				i++;
645				free(name);
646				continue;
647			}
648		}
649
650		DBG(1, "[%3u]-[0x%x] name[%s] len[0x%x] ino[0x%x] type[0x%x]\n",
651				fsck->dentry_depth, i, name, name_len,
652				le32_to_cpu(dentry[i].ino),
653				dentry[i].file_type);
654
655		print_dentry(fsck->dentry_depth, name, bitmap,
656						dentry, max, i, 1);
657
658		blk_cnt = 1;
659		ret = fsck_chk_node_blk(sbi,
660				NULL, le32_to_cpu(dentry[i].ino),
661				ftype, TYPE_INODE, &blk_cnt);
662
663		if (ret && config.fix_on) {
664			int j;
665			int slots = (name_len + F2FS_SLOT_LEN - 1) /
666				F2FS_SLOT_LEN;
667			for (j = 0; j < slots; j++)
668				clear_bit(i + j, bitmap);
669			FIX_MSG("Unlink [0x%x] - %s len[0x%x], type[0x%x]",
670					le32_to_cpu(dentry[i].ino),
671					name, name_len,
672					dentry[i].file_type);
673			i += slots;
674			free(name);
675			continue;
676		}
677
678		i += (name_len + F2FS_SLOT_LEN - 1) / F2FS_SLOT_LEN;
679		dentries++;
680		*child_files = *child_files + 1;
681		free(name);
682	}
683	return fixed ? -1 : dentries;
684}
685
686int fsck_chk_inline_dentries(struct f2fs_sb_info *sbi,
687		struct f2fs_node *node_blk, u32 *child_cnt, u32 *child_files)
688{
689	struct f2fs_fsck *fsck = F2FS_FSCK(sbi);
690	struct f2fs_inline_dentry *de_blk;
691	int dentries;
692
693	de_blk = inline_data_addr(node_blk);
694	ASSERT(de_blk != NULL);
695
696	fsck->dentry_depth++;
697	dentries = __chk_dentries(sbi, child_cnt, child_files,
698			(unsigned long *)de_blk->dentry_bitmap,
699			de_blk->dentry, de_blk->filename,
700			NR_INLINE_DENTRY, 1);
701	if (dentries < 0) {
702		DBG(1, "[%3d] Inline Dentry Block Fixed hash_codes\n\n",
703			fsck->dentry_depth);
704	} else {
705		DBG(1, "[%3d] Inline Dentry Block Done : "
706				"dentries:%d in %d slots (len:%d)\n\n",
707			fsck->dentry_depth, dentries,
708			(int)NR_INLINE_DENTRY, F2FS_NAME_LEN);
709	}
710	fsck->dentry_depth--;
711	return dentries;
712}
713
714int fsck_chk_dentry_blk(struct f2fs_sb_info *sbi, u32 blk_addr,
715		u32 *child_cnt, u32 *child_files, int last_blk)
716{
717	struct f2fs_fsck *fsck = F2FS_FSCK(sbi);
718	struct f2fs_dentry_block *de_blk;
719	int dentries, ret;
720
721	de_blk = (struct f2fs_dentry_block *)calloc(BLOCK_SZ, 1);
722	ASSERT(de_blk != NULL);
723
724	ret = dev_read_block(de_blk, blk_addr);
725	ASSERT(ret >= 0);
726
727	fsck->dentry_depth++;
728	dentries = __chk_dentries(sbi, child_cnt, child_files,
729			(unsigned long *)de_blk->dentry_bitmap,
730			de_blk->dentry, de_blk->filename,
731			NR_DENTRY_IN_BLOCK, last_blk);
732
733	if (dentries < 0) {
734		ret = dev_write_block(de_blk, blk_addr);
735		ASSERT(ret >= 0);
736		DBG(1, "[%3d] Dentry Block [0x%x] Fixed hash_codes\n\n",
737			fsck->dentry_depth, blk_addr);
738	} else {
739		DBG(1, "[%3d] Dentry Block [0x%x] Done : "
740				"dentries:%d in %d slots (len:%d)\n\n",
741			fsck->dentry_depth, blk_addr, dentries,
742			NR_DENTRY_IN_BLOCK, F2FS_NAME_LEN);
743	}
744	fsck->dentry_depth--;
745	free(de_blk);
746	return 0;
747}
748
749int fsck_chk_data_blk(struct f2fs_sb_info *sbi, u32 blk_addr,
750		u32 *child_cnt, u32 *child_files, int last_blk,
751		enum FILE_TYPE ftype, u32 parent_nid, u16 idx_in_node, u8 ver)
752{
753	struct f2fs_fsck *fsck = F2FS_FSCK(sbi);
754
755	/* Is it reserved block? */
756	if (blk_addr == NEW_ADDR) {
757		fsck->chk.valid_blk_cnt++;
758		return 0;
759	}
760
761	if (!IS_VALID_BLK_ADDR(sbi, blk_addr)) {
762		ASSERT_MSG("blkaddres is not valid. [0x%x]", blk_addr);
763		return -EINVAL;
764	}
765
766	if (is_valid_ssa_data_blk(sbi, blk_addr, parent_nid,
767						idx_in_node, ver)) {
768		ASSERT_MSG("summary data block is not valid. [0x%x]",
769						parent_nid);
770		return -EINVAL;
771	}
772
773	if (f2fs_test_sit_bitmap(sbi, blk_addr) == 0)
774		ASSERT_MSG("SIT bitmap is 0x0. blk_addr[0x%x]", blk_addr);
775
776	if (f2fs_test_main_bitmap(sbi, blk_addr) != 0)
777		ASSERT_MSG("Duplicated data [0x%x]. pnid[0x%x] idx[0x%x]",
778				blk_addr, parent_nid, idx_in_node);
779
780	f2fs_set_main_bitmap(sbi, blk_addr);
781
782	fsck->chk.valid_blk_cnt++;
783
784	if (ftype == F2FS_FT_DIR)
785		return fsck_chk_dentry_blk(sbi, blk_addr, child_cnt,
786				child_files, last_blk);
787	return 0;
788}
789
790void fsck_chk_orphan_node(struct f2fs_sb_info *sbi)
791{
792	u32 blk_cnt = 0;
793	block_t start_blk, orphan_blkaddr, i, j;
794	struct f2fs_orphan_block *orphan_blk;
795	struct f2fs_checkpoint *ckpt = F2FS_CKPT(sbi);
796
797	if (!is_set_ckpt_flags(ckpt, CP_ORPHAN_PRESENT_FLAG))
798		return;
799
800	if (config.fix_on)
801		return;
802
803	start_blk = __start_cp_addr(sbi) + 1 +
804		le32_to_cpu(F2FS_RAW_SUPER(sbi)->cp_payload);
805	orphan_blkaddr = __start_sum_addr(sbi) - 1;
806	orphan_blk = calloc(BLOCK_SZ, 1);
807
808	for (i = 0; i < orphan_blkaddr; i++) {
809		int ret = dev_read_block(orphan_blk, start_blk + i);
810
811		ASSERT(ret >= 0);
812
813		for (j = 0; j < le32_to_cpu(orphan_blk->entry_count); j++) {
814			nid_t ino = le32_to_cpu(orphan_blk->ino[j]);
815			DBG(1, "[%3d] ino [0x%x]\n", i, ino);
816			blk_cnt = 1;
817			fsck_chk_node_blk(sbi, NULL, ino,
818					F2FS_FT_ORPHAN, TYPE_INODE, &blk_cnt);
819		}
820		memset(orphan_blk, 0, BLOCK_SZ);
821	}
822	free(orphan_blk);
823}
824
825void fsck_init(struct f2fs_sb_info *sbi)
826{
827	struct f2fs_fsck *fsck = F2FS_FSCK(sbi);
828	struct f2fs_sm_info *sm_i = SM_I(sbi);
829
830	/*
831	 * We build three bitmap for main/sit/nat so that may check consistency
832	 * of filesystem.
833	 * 1. main_area_bitmap will be used to check whether all blocks of main
834	 *    area is used or not.
835	 * 2. nat_area_bitmap has bitmap information of used nid in NAT.
836	 * 3. sit_area_bitmap has bitmap information of used main block.
837	 * At Last sequence, we compare main_area_bitmap with sit_area_bitmap.
838	 */
839	fsck->nr_main_blks = sm_i->main_segments << sbi->log_blocks_per_seg;
840	fsck->main_area_bitmap_sz = (fsck->nr_main_blks + 7) / 8;
841	fsck->main_area_bitmap = calloc(fsck->main_area_bitmap_sz, 1);
842	ASSERT(fsck->main_area_bitmap != NULL);
843
844	build_nat_area_bitmap(sbi);
845
846	build_sit_area_bitmap(sbi);
847
848	tree_mark = calloc(tree_mark_size, 1);
849	ASSERT(tree_mark != NULL);
850}
851
852static void fix_nat_entries(struct f2fs_sb_info *sbi)
853{
854	struct f2fs_fsck *fsck = F2FS_FSCK(sbi);
855	u32 i;
856
857	for (i = 0; i < fsck->nr_nat_entries; i++)
858		if (f2fs_test_bit(i, fsck->nat_area_bitmap) != 0)
859			nullify_nat_entry(sbi, i);
860}
861
862static void fix_checkpoint(struct f2fs_sb_info *sbi)
863{
864	struct f2fs_fsck *fsck = F2FS_FSCK(sbi);
865	struct f2fs_super_block *raw_sb = sbi->raw_super;
866	struct f2fs_checkpoint *ckp = F2FS_CKPT(sbi);
867	unsigned long long cp_blk_no;
868	u32 i;
869	int ret;
870	u_int32_t crc = 0;
871
872	ckp->ckpt_flags = cpu_to_le32(CP_UMOUNT_FLAG);
873	ckp->cp_pack_total_block_count =
874		cpu_to_le32(8 + le32_to_cpu(raw_sb->cp_payload));
875	ckp->cp_pack_start_sum = cpu_to_le32(1 +
876				le32_to_cpu(raw_sb->cp_payload));
877
878	ckp->free_segment_count = cpu_to_le32(fsck->chk.free_segs);
879	ckp->valid_block_count = cpu_to_le32(fsck->chk.valid_blk_cnt);
880	ckp->valid_node_count = cpu_to_le32(fsck->chk.valid_node_cnt);
881	ckp->valid_inode_count = cpu_to_le32(fsck->chk.valid_inode_cnt);
882
883	crc = f2fs_cal_crc32(F2FS_SUPER_MAGIC, ckp, CHECKSUM_OFFSET);
884	*((__le32 *)((unsigned char *)ckp + CHECKSUM_OFFSET)) =
885							cpu_to_le32(crc);
886
887	cp_blk_no = le32_to_cpu(raw_sb->cp_blkaddr);
888	if (sbi->cur_cp == 2)
889		cp_blk_no += 1 << le32_to_cpu(raw_sb->log_blocks_per_seg);
890
891	ret = dev_write_block(ckp, cp_blk_no++);
892	ASSERT(ret >= 0);
893
894	for (i = 0; i < le32_to_cpu(raw_sb->cp_payload); i++) {
895		ret = dev_write_block(((unsigned char *)ckp) + i * F2FS_BLKSIZE,
896								cp_blk_no++);
897		ASSERT(ret >= 0);
898	}
899
900	for (i = 0; i < NO_CHECK_TYPE; i++) {
901		struct curseg_info *curseg = CURSEG_I(sbi, i);
902
903		ret = dev_write_block(curseg->sum_blk, cp_blk_no++);
904		ASSERT(ret >= 0);
905	}
906
907	ret = dev_write_block(ckp, cp_blk_no++);
908	ASSERT(ret >= 0);
909}
910
911int check_curseg_offset(struct f2fs_sb_info *sbi)
912{
913	int i;
914
915	for (i = 0; i < NO_CHECK_TYPE; i++) {
916		struct curseg_info *curseg = CURSEG_I(sbi, i);
917		struct seg_entry *se;
918
919		se = get_seg_entry(sbi, curseg->segno);
920		if (f2fs_test_bit(curseg->next_blkoff,
921				(const char *)se->cur_valid_map) == 1) {
922			ASSERT_MSG("Next block offset is not free, type:%d", i);
923			return -EINVAL;
924		}
925	}
926	return 0;
927}
928
929int fsck_verify(struct f2fs_sb_info *sbi)
930{
931	unsigned int i = 0;
932	int ret = 0;
933	u32 nr_unref_nid = 0;
934	struct f2fs_fsck *fsck = F2FS_FSCK(sbi);
935	struct hard_link_node *node = NULL;
936
937	printf("\n");
938
939	for (i = 0; i < fsck->nr_nat_entries; i++) {
940		if (f2fs_test_bit(i, fsck->nat_area_bitmap) != 0) {
941			printf("NID[0x%x] is unreachable\n", i);
942			nr_unref_nid++;
943		}
944	}
945
946	if (fsck->hard_link_list_head != NULL) {
947		node = fsck->hard_link_list_head;
948		while (node) {
949			printf("NID[0x%x] has [0x%x] more unreachable links\n",
950					node->nid, node->links);
951			node = node->next;
952		}
953		config.bug_on = 1;
954	}
955
956	printf("[FSCK] Unreachable nat entries                       ");
957	if (nr_unref_nid == 0x0) {
958		printf(" [Ok..] [0x%x]\n", nr_unref_nid);
959	} else {
960		printf(" [Fail] [0x%x]\n", nr_unref_nid);
961		ret = EXIT_ERR_CODE;
962		config.bug_on = 1;
963	}
964
965	printf("[FSCK] SIT valid block bitmap checking                ");
966	if (memcmp(fsck->sit_area_bitmap, fsck->main_area_bitmap,
967					fsck->sit_area_bitmap_sz) == 0x0) {
968		printf("[Ok..]\n");
969	} else {
970		printf("[Fail]\n");
971		ret = EXIT_ERR_CODE;
972		config.bug_on = 1;
973	}
974
975	printf("[FSCK] Hard link checking for regular file           ");
976	if (fsck->hard_link_list_head == NULL) {
977		printf(" [Ok..] [0x%x]\n", fsck->chk.multi_hard_link_files);
978	} else {
979		printf(" [Fail] [0x%x]\n", fsck->chk.multi_hard_link_files);
980		ret = EXIT_ERR_CODE;
981		config.bug_on = 1;
982	}
983
984	printf("[FSCK] valid_block_count matching with CP            ");
985	if (sbi->total_valid_block_count == fsck->chk.valid_blk_cnt) {
986		printf(" [Ok..] [0x%x]\n", (u32)fsck->chk.valid_blk_cnt);
987	} else {
988		printf(" [Fail] [0x%x]\n", (u32)fsck->chk.valid_blk_cnt);
989		ret = EXIT_ERR_CODE;
990		config.bug_on = 1;
991	}
992
993	printf("[FSCK] valid_node_count matcing with CP (de lookup)  ");
994	if (sbi->total_valid_node_count == fsck->chk.valid_node_cnt) {
995		printf(" [Ok..] [0x%x]\n", fsck->chk.valid_node_cnt);
996	} else {
997		printf(" [Fail] [0x%x]\n", fsck->chk.valid_node_cnt);
998		ret = EXIT_ERR_CODE;
999		config.bug_on = 1;
1000	}
1001
1002	printf("[FSCK] valid_node_count matcing with CP (nat lookup) ");
1003	if (sbi->total_valid_node_count == fsck->chk.valid_nat_entry_cnt) {
1004		printf(" [Ok..] [0x%x]\n", fsck->chk.valid_nat_entry_cnt);
1005	} else {
1006		printf(" [Fail] [0x%x]\n", fsck->chk.valid_nat_entry_cnt);
1007		ret = EXIT_ERR_CODE;
1008		config.bug_on = 1;
1009	}
1010
1011	printf("[FSCK] valid_inode_count matched with CP             ");
1012	if (sbi->total_valid_inode_count == fsck->chk.valid_inode_cnt) {
1013		printf(" [Ok..] [0x%x]\n", fsck->chk.valid_inode_cnt);
1014	} else {
1015		printf(" [Fail] [0x%x]\n", fsck->chk.valid_inode_cnt);
1016		ret = EXIT_ERR_CODE;
1017		config.bug_on = 1;
1018	}
1019
1020	printf("[FSCK] free segment_count matched with CP            ");
1021	if (le32_to_cpu(F2FS_CKPT(sbi)->free_segment_count) ==
1022						fsck->chk.sit_free_segs) {
1023		printf(" [Ok..] [0x%x]\n", fsck->chk.sit_free_segs);
1024	} else {
1025		printf(" [Fail] [0x%x]\n", fsck->chk.sit_free_segs);
1026		ret = EXIT_ERR_CODE;
1027		config.bug_on = 1;
1028	}
1029
1030	printf("[FSCK] next block offset is free                     ");
1031	if (check_curseg_offset(sbi) == 0) {
1032		printf(" [Ok..]\n");
1033	} else {
1034		printf(" [Fail]\n");
1035		ret = EXIT_ERR_CODE;
1036		config.bug_on = 1;
1037	}
1038
1039	printf("[FSCK] other corrupted bugs                          ");
1040	if (config.bug_on == 0) {
1041		printf(" [Ok..]\n");
1042	} else {
1043		printf(" [Fail]\n");
1044		ret = EXIT_ERR_CODE;
1045		config.bug_on = 1;
1046	}
1047
1048	/* fix global metadata */
1049	if (config.bug_on && config.fix_on) {
1050		fix_nat_entries(sbi);
1051		rewrite_sit_area_bitmap(sbi);
1052		fix_checkpoint(sbi);
1053	}
1054	return ret;
1055}
1056
1057void fsck_free(struct f2fs_sb_info *sbi)
1058{
1059	struct f2fs_fsck *fsck = F2FS_FSCK(sbi);
1060	if (fsck->main_area_bitmap)
1061		free(fsck->main_area_bitmap);
1062
1063	if (fsck->nat_area_bitmap)
1064		free(fsck->nat_area_bitmap);
1065
1066	if (fsck->sit_area_bitmap)
1067		free(fsck->sit_area_bitmap);
1068
1069	if (tree_mark)
1070		free(tree_mark);
1071}
1072