fsck.c revision 7dce30f2acad0f1f23d566c43e83d3f0098b1c1b
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 /* check data blocks in inode */ 455 for (idx = 0; idx < ADDRS_PER_INODE(&node_blk->i); idx++) { 456 if (le32_to_cpu(node_blk->i.i_addr[idx]) != 0) { 457 ret = fsck_chk_data_blk(sbi, 458 le32_to_cpu(node_blk->i.i_addr[idx]), 459 &child_cnt, &child_files, 460 (i_blocks == *blk_cnt), 461 ftype, nid, idx, ni->version); 462 if (!ret) { 463 *blk_cnt = *blk_cnt + 1; 464 } else if (config.fix_on) { 465 node_blk->i.i_addr[idx] = 0; 466 need_fix = 1; 467 FIX_MSG("[0x%x] i_addr[%d] = 0", nid, idx); 468 } 469 } 470 } 471 472 /* check node blocks in inode */ 473 for (idx = 0; idx < 5; idx++) { 474 if (idx == 0 || idx == 1) 475 ntype = TYPE_DIRECT_NODE; 476 else if (idx == 2 || idx == 3) 477 ntype = TYPE_INDIRECT_NODE; 478 else if (idx == 4) 479 ntype = TYPE_DOUBLE_INDIRECT_NODE; 480 else 481 ASSERT(0); 482 483 if (le32_to_cpu(node_blk->i.i_nid[idx]) != 0) { 484 ret = fsck_chk_node_blk(sbi, &node_blk->i, 485 le32_to_cpu(node_blk->i.i_nid[idx]), 486 ftype, ntype, blk_cnt); 487 if (!ret) { 488 *blk_cnt = *blk_cnt + 1; 489 } else if (config.fix_on) { 490 node_blk->i.i_nid[idx] = 0; 491 need_fix = 1; 492 FIX_MSG("[0x%x] i_nid[%d] = 0", nid, idx); 493 } 494 } 495 } 496check: 497 if (ftype == F2FS_FT_DIR) 498 DBG(1, "Directory Inode: 0x%x [%s] depth: %d has %d files\n\n", 499 le32_to_cpu(node_blk->footer.ino), 500 node_blk->i.i_name, 501 le32_to_cpu(node_blk->i.i_current_depth), 502 child_files); 503 if (ftype == F2FS_FT_ORPHAN) 504 DBG(1, "Orphan Inode: 0x%x [%s] i_blocks: %u\n\n", 505 le32_to_cpu(node_blk->footer.ino), 506 node_blk->i.i_name, 507 (u32)i_blocks); 508 509 if (i_blocks != *blk_cnt) { 510 ASSERT_MSG("ino: 0x%x has i_blocks: %08"PRIx64", " 511 "but has %u blocks", 512 nid, i_blocks, *blk_cnt); 513 if (config.fix_on) { 514 node_blk->i.i_blocks = cpu_to_le64(*blk_cnt); 515 need_fix = 1; 516 FIX_MSG("[0x%x] i_blocks=0x%08"PRIx64" -> 0x%x", 517 nid, i_blocks, *blk_cnt); 518 } 519 } 520 if (ftype == F2FS_FT_DIR && i_links != child_cnt) { 521 ASSERT_MSG("ino: 0x%x has i_links: %u but real links: %u", 522 nid, i_links, child_cnt); 523 if (config.fix_on) { 524 node_blk->i.i_links = cpu_to_le32(child_cnt); 525 need_fix = 1; 526 FIX_MSG("Dir: 0x%x i_links= 0x%x -> 0x%x", 527 nid, i_links, child_cnt); 528 } 529 } 530 531 if (ftype == F2FS_FT_ORPHAN && i_links) 532 ASSERT_MSG("ino: 0x%x is orphan inode, but has i_links: %u", 533 nid, i_links); 534 if (need_fix) { 535 ret = dev_write_block(node_blk, ni->blk_addr); 536 ASSERT(ret >= 0); 537 } 538} 539 540int fsck_chk_dnode_blk(struct f2fs_sb_info *sbi, struct f2fs_inode *inode, 541 u32 nid, enum FILE_TYPE ftype, struct f2fs_node *node_blk, 542 u32 *blk_cnt, struct node_info *ni) 543{ 544 int idx, ret; 545 u32 child_cnt = 0, child_files = 0; 546 547 for (idx = 0; idx < ADDRS_PER_BLOCK; idx++) { 548 if (le32_to_cpu(node_blk->dn.addr[idx]) == 0x0) 549 continue; 550 ret = fsck_chk_data_blk(sbi, 551 le32_to_cpu(node_blk->dn.addr[idx]), 552 &child_cnt, &child_files, 553 le64_to_cpu(inode->i_blocks) == *blk_cnt, ftype, 554 nid, idx, ni->version); 555 if (!ret) 556 *blk_cnt = *blk_cnt + 1; 557 } 558 return 0; 559} 560 561int fsck_chk_idnode_blk(struct f2fs_sb_info *sbi, struct f2fs_inode *inode, 562 enum FILE_TYPE ftype, struct f2fs_node *node_blk, u32 *blk_cnt) 563{ 564 int ret; 565 int i = 0; 566 567 for (i = 0 ; i < NIDS_PER_BLOCK; i++) { 568 if (le32_to_cpu(node_blk->in.nid[i]) == 0x0) 569 continue; 570 ret = fsck_chk_node_blk(sbi, inode, 571 le32_to_cpu(node_blk->in.nid[i]), 572 ftype, TYPE_DIRECT_NODE, blk_cnt); 573 if (!ret) 574 *blk_cnt = *blk_cnt + 1; 575 else if (ret == -EINVAL) 576 printf("delete in.nid[i] = 0;\n"); 577 } 578 return 0; 579} 580 581int fsck_chk_didnode_blk(struct f2fs_sb_info *sbi, struct f2fs_inode *inode, 582 enum FILE_TYPE ftype, struct f2fs_node *node_blk, u32 *blk_cnt) 583{ 584 int i = 0; 585 int ret = 0; 586 587 for (i = 0; i < NIDS_PER_BLOCK; i++) { 588 if (le32_to_cpu(node_blk->in.nid[i]) == 0x0) 589 continue; 590 ret = fsck_chk_node_blk(sbi, inode, 591 le32_to_cpu(node_blk->in.nid[i]), 592 ftype, TYPE_INDIRECT_NODE, blk_cnt); 593 if (!ret) 594 *blk_cnt = *blk_cnt + 1; 595 else if (ret == -EINVAL) 596 printf("delete in.nid[i] = 0;\n"); 597 } 598 return 0; 599} 600 601static void print_dentry(__u32 depth, __u8 *name, 602 unsigned long *bitmap, 603 struct f2fs_dir_entry *dentry, 604 int max, int idx, int last_blk) 605{ 606 int last_de = 0; 607 int next_idx = 0; 608 int name_len; 609 unsigned int i; 610 int bit_offset; 611 612 if (config.dbg_lv != -1) 613 return; 614 615 name_len = le16_to_cpu(dentry[idx].name_len); 616 next_idx = idx + (name_len + F2FS_SLOT_LEN - 1) / F2FS_SLOT_LEN; 617 618 bit_offset = find_next_bit(bitmap, max, next_idx); 619 if (bit_offset >= max && last_blk) 620 last_de = 1; 621 622 if (tree_mark_size <= depth) { 623 tree_mark_size *= 2; 624 tree_mark = realloc(tree_mark, tree_mark_size); 625 } 626 627 if (last_de) 628 tree_mark[depth] = '`'; 629 else 630 tree_mark[depth] = '|'; 631 632 if (tree_mark[depth - 1] == '`') 633 tree_mark[depth - 1] = ' '; 634 635 636 for (i = 1; i < depth; i++) 637 printf("%c ", tree_mark[i]); 638 printf("%c-- %s 0x%x\n", last_de ? '`' : '|', 639 name, le32_to_cpu(dentry[idx].ino)); 640} 641 642static int __chk_dentries(struct f2fs_sb_info *sbi, u32 *child_cnt, 643 u32* child_files, 644 unsigned long *bitmap, 645 struct f2fs_dir_entry *dentry, 646 __u8 (*filenames)[F2FS_SLOT_LEN], 647 int max, int last_blk) 648{ 649 struct f2fs_fsck *fsck = F2FS_FSCK(sbi); 650 enum FILE_TYPE ftype; 651 int dentries = 0; 652 u32 blk_cnt; 653 u8 *name; 654 u32 hash_code; 655 u16 name_len;; 656 int ret = 0; 657 int fixed = 0; 658 int i; 659 660 for (i = 0; i < max;) { 661 if (test_bit(i, bitmap) == 0) { 662 i++; 663 continue; 664 } 665 if (!IS_VALID_NID(sbi, le32_to_cpu(dentry[i].ino))) { 666 DBG(1, "Bad dentry 0x%x with invalid NID/ino 0x%x", 667 i, le32_to_cpu(dentry[i].ino)); 668 if (config.fix_on) { 669 FIX_MSG("Clear bad dentry 0x%x with bad ino 0x%x", 670 i, le32_to_cpu(dentry[i].ino)); 671 clear_bit(i, bitmap); 672 i++; 673 fixed = 1; 674 continue; 675 } 676 } 677 ftype = dentry[i].file_type; 678 if ((ftype <= F2FS_FT_UNKNOWN || ftype > F2FS_FT_LAST_FILE_TYPE) && config.fix_on) { 679 DBG(1, "Bad dentry 0x%x with unexpected ftype 0x%x", 680 i, ftype); 681 if (config.fix_on) { 682 FIX_MSG("Clear bad dentry 0x%x with bad ftype 0x%x", 683 i, ftype); 684 clear_bit(i, bitmap); 685 i++; 686 fixed = 1; 687 continue; 688 } 689 } 690 name_len = le16_to_cpu(dentry[i].name_len); 691 name = calloc(name_len + 1, 1); 692 memcpy(name, filenames[i], name_len); 693 hash_code = f2fs_dentry_hash((const unsigned char *)name, 694 name_len); 695 696 /* fix hash_code made by old buggy code */ 697 if (le32_to_cpu(dentry[i].hash_code) != hash_code) { 698 dentry[i].hash_code = hash_code; 699 fixed = 1; 700 FIX_MSG("hash_code[%d] of %s", i, name); 701 } 702 703 /* Becareful. 'dentry.file_type' is not imode. */ 704 if (ftype == F2FS_FT_DIR) { 705 *child_cnt = *child_cnt + 1; 706 if ((name[0] == '.' && name_len == 1) || 707 (name[0] == '.' && name[1] == '.' && 708 name_len == 2)) { 709 i++; 710 free(name); 711 continue; 712 } 713 } 714 715 DBG(1, "[%3u]-[0x%x] name[%s] len[0x%x] ino[0x%x] type[0x%x]\n", 716 fsck->dentry_depth, i, name, name_len, 717 le32_to_cpu(dentry[i].ino), 718 dentry[i].file_type); 719 720 print_dentry(fsck->dentry_depth, name, bitmap, 721 dentry, max, i, last_blk); 722 723 blk_cnt = 1; 724 ret = fsck_chk_node_blk(sbi, 725 NULL, le32_to_cpu(dentry[i].ino), 726 ftype, TYPE_INODE, &blk_cnt); 727 728 if (ret && config.fix_on) { 729 int j; 730 int slots = (name_len + F2FS_SLOT_LEN - 1) / 731 F2FS_SLOT_LEN; 732 for (j = 0; j < slots; j++) 733 clear_bit(i + j, bitmap); 734 FIX_MSG("Unlink [0x%x] - %s len[0x%x], type[0x%x]", 735 le32_to_cpu(dentry[i].ino), 736 name, name_len, 737 dentry[i].file_type); 738 i += slots; 739 free(name); 740 fixed = 1; 741 continue; 742 } 743 744 i += (name_len + F2FS_SLOT_LEN - 1) / F2FS_SLOT_LEN; 745 dentries++; 746 *child_files = *child_files + 1; 747 free(name); 748 } 749 return fixed ? -1 : dentries; 750} 751 752int fsck_chk_inline_dentries(struct f2fs_sb_info *sbi, 753 struct f2fs_node *node_blk, u32 *child_cnt, u32 *child_files) 754{ 755 struct f2fs_fsck *fsck = F2FS_FSCK(sbi); 756 struct f2fs_inline_dentry *de_blk; 757 int dentries; 758 759 de_blk = inline_data_addr(node_blk); 760 ASSERT(de_blk != NULL); 761 762 fsck->dentry_depth++; 763 dentries = __chk_dentries(sbi, child_cnt, child_files, 764 (unsigned long *)de_blk->dentry_bitmap, 765 de_blk->dentry, de_blk->filename, 766 NR_INLINE_DENTRY, 1); 767 if (dentries < 0) { 768 DBG(1, "[%3d] Inline Dentry Block Fixed hash_codes\n\n", 769 fsck->dentry_depth); 770 } else { 771 DBG(1, "[%3d] Inline Dentry Block Done : " 772 "dentries:%d in %d slots (len:%d)\n\n", 773 fsck->dentry_depth, dentries, 774 (int)NR_INLINE_DENTRY, F2FS_NAME_LEN); 775 } 776 fsck->dentry_depth--; 777 return dentries; 778} 779 780int fsck_chk_dentry_blk(struct f2fs_sb_info *sbi, u32 blk_addr, 781 u32 *child_cnt, u32 *child_files, int last_blk) 782{ 783 struct f2fs_fsck *fsck = F2FS_FSCK(sbi); 784 struct f2fs_dentry_block *de_blk; 785 int dentries, ret; 786 787 de_blk = (struct f2fs_dentry_block *)calloc(BLOCK_SZ, 1); 788 ASSERT(de_blk != NULL); 789 790 ret = dev_read_block(de_blk, blk_addr); 791 ASSERT(ret >= 0); 792 793 fsck->dentry_depth++; 794 dentries = __chk_dentries(sbi, child_cnt, child_files, 795 (unsigned long *)de_blk->dentry_bitmap, 796 de_blk->dentry, de_blk->filename, 797 NR_DENTRY_IN_BLOCK, last_blk); 798 799 if (dentries < 0) { 800 ret = dev_write_block(de_blk, blk_addr); 801 ASSERT(ret >= 0); 802 DBG(1, "[%3d] Dentry Block [0x%x] Fixed hash_codes\n\n", 803 fsck->dentry_depth, blk_addr); 804 } else { 805 DBG(1, "[%3d] Dentry Block [0x%x] Done : " 806 "dentries:%d in %d slots (len:%d)\n\n", 807 fsck->dentry_depth, blk_addr, dentries, 808 NR_DENTRY_IN_BLOCK, F2FS_NAME_LEN); 809 } 810 fsck->dentry_depth--; 811 free(de_blk); 812 return 0; 813} 814 815int fsck_chk_data_blk(struct f2fs_sb_info *sbi, u32 blk_addr, 816 u32 *child_cnt, u32 *child_files, int last_blk, 817 enum FILE_TYPE ftype, u32 parent_nid, u16 idx_in_node, u8 ver) 818{ 819 struct f2fs_fsck *fsck = F2FS_FSCK(sbi); 820 821 /* Is it reserved block? */ 822 if (blk_addr == NEW_ADDR) { 823 fsck->chk.valid_blk_cnt++; 824 return 0; 825 } 826 827 if (!IS_VALID_BLK_ADDR(sbi, blk_addr)) { 828 ASSERT_MSG("blkaddres is not valid. [0x%x]", blk_addr); 829 return -EINVAL; 830 } 831 832 if (is_valid_ssa_data_blk(sbi, blk_addr, parent_nid, 833 idx_in_node, ver)) { 834 ASSERT_MSG("summary data block is not valid. [0x%x]", 835 parent_nid); 836 return -EINVAL; 837 } 838 839 if (f2fs_test_sit_bitmap(sbi, blk_addr) == 0) 840 ASSERT_MSG("SIT bitmap is 0x0. blk_addr[0x%x]", blk_addr); 841 842 if (f2fs_test_main_bitmap(sbi, blk_addr) != 0) 843 ASSERT_MSG("Duplicated data [0x%x]. pnid[0x%x] idx[0x%x]", 844 blk_addr, parent_nid, idx_in_node); 845 846 847 fsck->chk.valid_blk_cnt++; 848 849 if (ftype == F2FS_FT_DIR) { 850 f2fs_set_main_bitmap(sbi, blk_addr, CURSEG_HOT_DATA); 851 return fsck_chk_dentry_blk(sbi, blk_addr, child_cnt, 852 child_files, last_blk); 853 } else { 854 f2fs_set_main_bitmap(sbi, blk_addr, CURSEG_WARM_DATA); 855 } 856 return 0; 857} 858 859void fsck_chk_orphan_node(struct f2fs_sb_info *sbi) 860{ 861 u32 blk_cnt = 0; 862 block_t start_blk, orphan_blkaddr, i, j; 863 struct f2fs_orphan_block *orphan_blk; 864 struct f2fs_checkpoint *ckpt = F2FS_CKPT(sbi); 865 866 if (!is_set_ckpt_flags(ckpt, CP_ORPHAN_PRESENT_FLAG)) 867 return; 868 869 start_blk = __start_cp_addr(sbi) + 1 + 870 le32_to_cpu(F2FS_RAW_SUPER(sbi)->cp_payload); 871 orphan_blkaddr = __start_sum_addr(sbi) - 1; 872 orphan_blk = calloc(BLOCK_SZ, 1); 873 874 for (i = 0; i < orphan_blkaddr; i++) { 875 int ret = dev_read_block(orphan_blk, start_blk + i); 876 877 ASSERT(ret >= 0); 878 879 for (j = 0; j < le32_to_cpu(orphan_blk->entry_count); j++) { 880 nid_t ino = le32_to_cpu(orphan_blk->ino[j]); 881 DBG(1, "[%3d] ino [0x%x]\n", i, ino); 882 if (config.fix_on) { 883 FIX_MSG("Discard orphan inodes: ino [0x%x]", 884 ino); 885 continue; 886 } 887 blk_cnt = 1; 888 fsck_chk_node_blk(sbi, NULL, ino, 889 F2FS_FT_ORPHAN, TYPE_INODE, &blk_cnt); 890 } 891 memset(orphan_blk, 0, BLOCK_SZ); 892 } 893 free(orphan_blk); 894} 895 896void fsck_init(struct f2fs_sb_info *sbi) 897{ 898 struct f2fs_fsck *fsck = F2FS_FSCK(sbi); 899 struct f2fs_sm_info *sm_i = SM_I(sbi); 900 901 /* 902 * We build three bitmap for main/sit/nat so that may check consistency 903 * of filesystem. 904 * 1. main_area_bitmap will be used to check whether all blocks of main 905 * area is used or not. 906 * 2. nat_area_bitmap has bitmap information of used nid in NAT. 907 * 3. sit_area_bitmap has bitmap information of used main block. 908 * At Last sequence, we compare main_area_bitmap with sit_area_bitmap. 909 */ 910 fsck->nr_main_blks = sm_i->main_segments << sbi->log_blocks_per_seg; 911 fsck->main_area_bitmap_sz = (fsck->nr_main_blks + 7) / 8; 912 fsck->main_area_bitmap = calloc(fsck->main_area_bitmap_sz, 1); 913 ASSERT(fsck->main_area_bitmap != NULL); 914 915 build_nat_area_bitmap(sbi); 916 917 build_sit_area_bitmap(sbi); 918 919 tree_mark = calloc(tree_mark_size, 1); 920 ASSERT(tree_mark != NULL); 921} 922 923static void fix_nat_entries(struct f2fs_sb_info *sbi) 924{ 925 struct f2fs_fsck *fsck = F2FS_FSCK(sbi); 926 u32 i; 927 928 for (i = 0; i < fsck->nr_nat_entries; i++) 929 if (f2fs_test_bit(i, fsck->nat_area_bitmap) != 0) 930 nullify_nat_entry(sbi, i); 931} 932 933static void fix_checkpoint(struct f2fs_sb_info *sbi) 934{ 935 struct f2fs_fsck *fsck = F2FS_FSCK(sbi); 936 struct f2fs_super_block *raw_sb = sbi->raw_super; 937 struct f2fs_checkpoint *ckp = F2FS_CKPT(sbi); 938 unsigned long long cp_blk_no; 939 u32 i; 940 int ret; 941 u_int32_t crc = 0; 942 943 ckp->ckpt_flags = cpu_to_le32(CP_UMOUNT_FLAG); 944 ckp->cp_pack_total_block_count = 945 cpu_to_le32(8 + le32_to_cpu(raw_sb->cp_payload)); 946 ckp->cp_pack_start_sum = cpu_to_le32(1 + 947 le32_to_cpu(raw_sb->cp_payload)); 948 949 ckp->free_segment_count = cpu_to_le32(fsck->chk.free_segs); 950 ckp->valid_block_count = cpu_to_le32(fsck->chk.valid_blk_cnt); 951 ckp->valid_node_count = cpu_to_le32(fsck->chk.valid_node_cnt); 952 ckp->valid_inode_count = cpu_to_le32(fsck->chk.valid_inode_cnt); 953 954 crc = f2fs_cal_crc32(F2FS_SUPER_MAGIC, ckp, CHECKSUM_OFFSET); 955 *((__le32 *)((unsigned char *)ckp + CHECKSUM_OFFSET)) = 956 cpu_to_le32(crc); 957 958 cp_blk_no = le32_to_cpu(raw_sb->cp_blkaddr); 959 if (sbi->cur_cp == 2) 960 cp_blk_no += 1 << le32_to_cpu(raw_sb->log_blocks_per_seg); 961 962 ret = dev_write_block(ckp, cp_blk_no++); 963 ASSERT(ret >= 0); 964 965 for (i = 0; i < le32_to_cpu(raw_sb->cp_payload); i++) { 966 ret = dev_write_block(((unsigned char *)ckp) + i * F2FS_BLKSIZE, 967 cp_blk_no++); 968 ASSERT(ret >= 0); 969 } 970 971 for (i = 0; i < NO_CHECK_TYPE; i++) { 972 struct curseg_info *curseg = CURSEG_I(sbi, i); 973 974 ret = dev_write_block(curseg->sum_blk, cp_blk_no++); 975 ASSERT(ret >= 0); 976 } 977 978 ret = dev_write_block(ckp, cp_blk_no++); 979 ASSERT(ret >= 0); 980} 981 982int check_curseg_offset(struct f2fs_sb_info *sbi) 983{ 984 int i; 985 986 for (i = 0; i < NO_CHECK_TYPE; i++) { 987 struct curseg_info *curseg = CURSEG_I(sbi, i); 988 struct seg_entry *se; 989 990 se = get_seg_entry(sbi, curseg->segno); 991 if (f2fs_test_bit(curseg->next_blkoff, 992 (const char *)se->cur_valid_map) == 1) { 993 ASSERT_MSG("Next block offset is not free, type:%d", i); 994 return -EINVAL; 995 } 996 } 997 return 0; 998} 999 1000int check_sit_types(struct f2fs_sb_info *sbi) 1001{ 1002 unsigned int i; 1003 int err = 0; 1004 1005 for (i = 0; i < TOTAL_SEGS(sbi); i++) { 1006 struct seg_entry *se; 1007 1008 se = get_seg_entry(sbi, i); 1009 if (se->orig_type != se->type) { 1010 FIX_MSG("Wrong segment type [0x%x] %x -> %x", 1011 i, se->orig_type, se->type); 1012 err = -EINVAL; 1013 } 1014 } 1015 return err; 1016} 1017 1018int fsck_verify(struct f2fs_sb_info *sbi) 1019{ 1020 unsigned int i = 0; 1021 int ret = 0; 1022 u32 nr_unref_nid = 0; 1023 struct f2fs_fsck *fsck = F2FS_FSCK(sbi); 1024 struct hard_link_node *node = NULL; 1025 1026 printf("\n"); 1027 1028 for (i = 0; i < fsck->nr_nat_entries; i++) { 1029 if (f2fs_test_bit(i, fsck->nat_area_bitmap) != 0) { 1030 printf("NID[0x%x] is unreachable\n", i); 1031 nr_unref_nid++; 1032 } 1033 } 1034 1035 if (fsck->hard_link_list_head != NULL) { 1036 node = fsck->hard_link_list_head; 1037 while (node) { 1038 printf("NID[0x%x] has [0x%x] more unreachable links\n", 1039 node->nid, node->links); 1040 node = node->next; 1041 } 1042 config.bug_on = 1; 1043 } 1044 1045 printf("[FSCK] Unreachable nat entries "); 1046 if (nr_unref_nid == 0x0) { 1047 printf(" [Ok..] [0x%x]\n", nr_unref_nid); 1048 } else { 1049 printf(" [Fail] [0x%x]\n", nr_unref_nid); 1050 ret = EXIT_ERR_CODE; 1051 config.bug_on = 1; 1052 } 1053 1054 printf("[FSCK] SIT valid block bitmap checking "); 1055 if (memcmp(fsck->sit_area_bitmap, fsck->main_area_bitmap, 1056 fsck->sit_area_bitmap_sz) == 0x0) { 1057 printf("[Ok..]\n"); 1058 } else { 1059 printf("[Fail]\n"); 1060 ret = EXIT_ERR_CODE; 1061 config.bug_on = 1; 1062 } 1063 1064 printf("[FSCK] Hard link checking for regular file "); 1065 if (fsck->hard_link_list_head == NULL) { 1066 printf(" [Ok..] [0x%x]\n", fsck->chk.multi_hard_link_files); 1067 } else { 1068 printf(" [Fail] [0x%x]\n", fsck->chk.multi_hard_link_files); 1069 ret = EXIT_ERR_CODE; 1070 config.bug_on = 1; 1071 } 1072 1073 printf("[FSCK] valid_block_count matching with CP "); 1074 if (sbi->total_valid_block_count == fsck->chk.valid_blk_cnt) { 1075 printf(" [Ok..] [0x%x]\n", (u32)fsck->chk.valid_blk_cnt); 1076 } else { 1077 printf(" [Fail] [0x%x]\n", (u32)fsck->chk.valid_blk_cnt); 1078 ret = EXIT_ERR_CODE; 1079 config.bug_on = 1; 1080 } 1081 1082 printf("[FSCK] valid_node_count matcing with CP (de lookup) "); 1083 if (sbi->total_valid_node_count == fsck->chk.valid_node_cnt) { 1084 printf(" [Ok..] [0x%x]\n", fsck->chk.valid_node_cnt); 1085 } else { 1086 printf(" [Fail] [0x%x]\n", fsck->chk.valid_node_cnt); 1087 ret = EXIT_ERR_CODE; 1088 config.bug_on = 1; 1089 } 1090 1091 printf("[FSCK] valid_node_count matcing with CP (nat lookup) "); 1092 if (sbi->total_valid_node_count == fsck->chk.valid_nat_entry_cnt) { 1093 printf(" [Ok..] [0x%x]\n", fsck->chk.valid_nat_entry_cnt); 1094 } else { 1095 printf(" [Fail] [0x%x]\n", fsck->chk.valid_nat_entry_cnt); 1096 ret = EXIT_ERR_CODE; 1097 config.bug_on = 1; 1098 } 1099 1100 printf("[FSCK] valid_inode_count matched with CP "); 1101 if (sbi->total_valid_inode_count == fsck->chk.valid_inode_cnt) { 1102 printf(" [Ok..] [0x%x]\n", fsck->chk.valid_inode_cnt); 1103 } else { 1104 printf(" [Fail] [0x%x]\n", fsck->chk.valid_inode_cnt); 1105 ret = EXIT_ERR_CODE; 1106 config.bug_on = 1; 1107 } 1108 1109 printf("[FSCK] free segment_count matched with CP "); 1110 if (le32_to_cpu(F2FS_CKPT(sbi)->free_segment_count) == 1111 fsck->chk.sit_free_segs) { 1112 printf(" [Ok..] [0x%x]\n", fsck->chk.sit_free_segs); 1113 } else { 1114 printf(" [Fail] [0x%x]\n", fsck->chk.sit_free_segs); 1115 ret = EXIT_ERR_CODE; 1116 config.bug_on = 1; 1117 } 1118 1119 printf("[FSCK] next block offset is free "); 1120 if (check_curseg_offset(sbi) == 0) { 1121 printf(" [Ok..]\n"); 1122 } else { 1123 printf(" [Fail]\n"); 1124 ret = EXIT_ERR_CODE; 1125 config.bug_on = 1; 1126 } 1127 1128 printf("[FSCK] SIT types "); 1129 if (check_sit_types(sbi) == 0) { 1130 printf(" [Ok..]\n"); 1131 } else { 1132 printf(" [Fail]\n"); 1133 ret = EXIT_ERR_CODE; 1134 config.bug_on = 1; 1135 } 1136 1137 printf("[FSCK] other corrupted bugs "); 1138 if (config.bug_on == 0) { 1139 printf(" [Ok..]\n"); 1140 } else { 1141 printf(" [Fail]\n"); 1142 ret = EXIT_ERR_CODE; 1143 } 1144 1145 /* fix global metadata */ 1146 if (config.bug_on && config.fix_on) { 1147 fix_nat_entries(sbi); 1148 rewrite_sit_area_bitmap(sbi); 1149 fix_checkpoint(sbi); 1150 } 1151 return ret; 1152} 1153 1154void fsck_free(struct f2fs_sb_info *sbi) 1155{ 1156 struct f2fs_fsck *fsck = F2FS_FSCK(sbi); 1157 if (fsck->main_area_bitmap) 1158 free(fsck->main_area_bitmap); 1159 1160 if (fsck->nat_area_bitmap) 1161 free(fsck->nat_area_bitmap); 1162 1163 if (fsck->sit_area_bitmap) 1164 free(fsck->sit_area_bitmap); 1165 1166 if (tree_mark) 1167 free(tree_mark); 1168} 1169