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