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