1/* 2 * Copyright (c) 2000-2002, 2004-2008 Apple Inc. All rights reserved. 3 * 4 * @APPLE_LICENSE_HEADER_START@ 5 * 6 * This file contains Original Code and/or Modifications of Original Code 7 * as defined in and that are subject to the Apple Public Source License 8 * Version 2.0 (the 'License'). You may not use this file except in 9 * compliance with the License. Please obtain a copy of the License at 10 * http://www.opensource.apple.com/apsl/ and read it before using this 11 * file. 12 * 13 * The Original Code and all software distributed under the License are 14 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 15 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 16 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 17 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 18 * Please see the License for the specific language governing rights and 19 * limitations under the License. 20 * 21 * @APPLE_LICENSE_HEADER_END@ 22 */ 23 24#include "Scavenger.h" 25#include <sys/stat.h> 26 27#define DEBUG_HARDLINKCHECK 0 28 29/* If set, the node in hash is initialized and has valid inodeID */ 30#define LINKINFO_INIT 0x01 31/* If set, verification of corresponding inode is completed successfully */ 32#define LINKINFO_CHECK 0x02 33 34/* info saved for each indirect link encountered */ 35struct IndirectLinkInfo { 36 /* linkID is link reference number for file hard links, and 37 * inodeID for directory hard links. 38 */ 39 UInt32 linkID; 40 UInt32 linkCount; 41 UInt32 flags; 42 struct HardLinkList *list; 43}; 44 45#define VISITED_INODE_ID 1 46 47struct HardLinkInfo { 48 UInt32 privDirID; 49 SGlobPtr globals; 50 uint32_t priv_dir_itime; /* Creation (initialization) time of metadata folder */ 51 uint32_t root_dir_itime; /* Creation (initialization) time of root folder */ 52 PrimeBuckets *fileBucket; 53}; 54 55struct HardLinkList { 56 UInt32 prev; 57 UInt32 fileID; 58 UInt32 next; 59}; 60 61HFSPlusCatalogKey gMetaDataDirKey = { 62 48, /* key length */ 63 2, /* parent directory ID */ 64 { 65 21, /* number of unicode characters */ 66 { 67 '\0','\0','\0','\0', 68 'H','F','S','+',' ', 69 'P','r','i','v','a','t','e',' ', 70 'D','a','t','a' 71 } 72 } 73}; 74 75/* private local routines */ 76static int GetPrivateDir(SGlobPtr gp, CatalogRecord *rec); 77static int GetRootDir(SGlobPtr gp, CatalogRecord *rec); 78static int RecordOrphanOpenUnlink(SGlobPtr gp, UInt32 parID, unsigned char * filename); 79static int RecordBadHardLinkChainFirst(SGlobPtr, UInt32, UInt32, UInt32); 80static int RecordBadHardLinkNext(SGlobPtr gp, UInt32 fileID, UInt32 is, UInt32 shouldbe); 81static int RecordBadHardLinkPrev(SGlobPtr gp, UInt32 fileID, UInt32 is, UInt32 shouldbe); 82static int RecordBadLinkCount(SGlobPtr gp, UInt32 inodeID, UInt32 is, UInt32 shouldbe) ; 83static int RecordOrphanLink(SGlobPtr gp, Boolean isdir, UInt32 linkID); 84static int RecordOrphanInode(SGlobPtr gp, Boolean isdir, UInt32 inodeID); 85static void hash_insert(UInt32 linkID, int totalSlots, int slotsUsed, struct IndirectLinkInfo *linkInfo); 86static struct IndirectLinkInfo * hash_search(UInt32 linkID, int totalSlots, int slotsUsed, struct IndirectLinkInfo *linkInfo); 87 88/* 89 * Some functions used when sorting the hard link chain. 90 * chain_compare() is used by qsort; find_id is just a linear 91 * search to find a specific fileID; and tsort does a 92 * topological sort on the linked list. 93 */ 94static int 95chain_compare(const void *a1, const void *a2) { 96 struct HardLinkList *left = (struct HardLinkList*)a1; 97 struct HardLinkList *right = (struct HardLinkList*)a2; 98 99 return (left->prev - right->prev); 100} 101 102static int 103find_id(struct HardLinkList *list, int nel, int id) 104{ 105 int i; 106 for (i = 0; i < nel; i++) { 107 if (list[i].fileID == id) 108 return i; 109 } 110 return 0; 111} 112 113static int 114tsort(struct HardLinkList *list, int nel) 115{ 116 struct HardLinkList *tmp; 117 int cur_indx, tmp_indx = 0; 118 119 int rv = 0; 120 121 tmp = calloc(sizeof(struct HardLinkList), nel); 122 if (tmp == NULL) { 123 rv = ENOMEM; 124 goto done; 125 } 126 127 /* 128 * Since we only check list.next when doing the sort, we want to 129 * start with nodes that have prev == 0 (ones at the top of the 130 * graph, in other words). If there aren't any with a prev of 0, 131 * then the chain is broken somehow, and we'll repair it later. 132 */ 133 qsort(list, nel, sizeof(list[0]), chain_compare); 134 135 for (cur_indx = 0; cur_indx < nel; cur_indx++) { 136 int i; 137 /* Skip nodes we've already come across */ 138 if (list[cur_indx].fileID == 0) 139 continue; 140 141 /* Copy this node over to the new list */ 142 tmp[tmp_indx++] = list[cur_indx]; 143 list[cur_indx].fileID = 0; 144 145 /* ... and then find all its children. */ 146 for (i = tmp[tmp_indx-1].next; i != 0; ) { 147 // look for the node in list with that fileID 148 int j = find_id(list, nel, i); 149 if (j == 0) { 150 // We couldn't find it 151 // So we're done 152 i = 0; 153 } else { 154 // we add this one to tmp 155 tmp[tmp_indx++] = list[j]; 156 list[j].fileID = 0; 157 i = tmp[tmp_indx-1].next; 158 } 159 } 160 } 161 162 /* Copy the temporary list over, and we're done. */ 163 memcpy(list, tmp, nel * sizeof(struct HardLinkList)); 164done: 165 if (tmp) { 166 free(tmp); 167 } 168 169 return rv; 170} 171 172/* 173 * CheckHardLinkList 174 * 175 * Verify that the linked list of hard link nodes (the catalog entries, not the indirect 176 * node in the private metadata directory) are correct and sane. If any discrepancies 177 * are detected, create repair order. 178 * 179 * To do this, we need to topologically sort the list, and then ensure that the prev/next 180 * chains are correct. 181 * 182 */ 183static int 184CheckHardLinkList(SGlobPtr gp, UInt32 inodeID, struct HardLinkList *list, int calc_link_count, UInt32 firstID) 185{ 186 int retval; 187 int indx; 188 189 if (list == NULL) { 190 if (fsckGetVerbosity(gp->context) >= kDebugLog) { 191 plog("\tCheckHardLinkList: list=NULL for inodeID = %u\n", inodeID); 192 } 193 return ENOMEM; 194 } 195 /* 196 * If we have a list, then we sort and verify it. It's pretty easy, once 197 * we're sorted, and tsort() above does the hard work for that. 198 */ 199 if (calc_link_count > 1) { 200 retval = tsort(list, calc_link_count); 201 if (retval) { 202 goto done; 203 } 204 } 205 206 /* Previous link of first link should always be zero */ 207 if (list[0].prev != 0) { 208 RecordBadHardLinkPrev(gp, list[0].fileID, list[0].prev, 0); 209 } 210 211 /* First ID in the inode should match the ID of the first hard link */ 212 if (list[0].fileID != firstID) { 213 RecordBadHardLinkChainFirst(gp, inodeID, firstID, list[0].fileID); 214 } 215 216 /* Check if the previous/next IDs for all nodes except the first node are valid */ 217 for (indx = 1; indx < calc_link_count; indx++) { 218 if (list[indx-1].next != list[indx].fileID) { 219 RecordBadHardLinkNext(gp, list[indx-1].fileID, list[indx-1].next, list[indx].fileID); 220 } 221 222 if (list[indx].prev != list[indx-1].fileID) { 223 RecordBadHardLinkPrev(gp, list[indx].fileID, list[indx].prev, list[indx-1].fileID); 224 } 225 } 226 227 /* Next ID for the last link should always be zero */ 228 if (list[calc_link_count-1].next != 0) { 229 RecordBadHardLinkNext(gp, list[calc_link_count-1].fileID, list[calc_link_count-1].next, 0); 230 } 231 232done: 233#if DEBUG_HARDLINKCHECK 234 /* This is just for debugging -- it's useful to know what the list looks like */ 235 if (fsckGetVerbosity(gp->context) >= kDebugLog) { 236 for (indx = 0; indx < calc_link_count; indx++) { 237 fplog(stderr, "CNID %u: #%u: <%u, %u, %u>\n", inodeID, indx, list[indx].prev, list[indx].fileID, list[indx].next); 238 } 239 } 240#endif 241 242 return 0; 243} 244 245/* 246 * HardLinkCheckBegin 247 * 248 * Get ready to capture indirect link info. 249 * Called before iterating over all the catalog leaf nodes. 250 */ 251int 252HardLinkCheckBegin(SGlobPtr gp, void** cookie) 253{ 254 struct HardLinkInfo *info; 255 CatalogRecord rec; 256 CatalogRecord rootFolder; 257 UInt32 folderID; 258 259 if (GetPrivateDir(gp, &rec) == 0) { 260 folderID = rec.hfsPlusFolder.folderID; 261 } else { 262 folderID = 0; 263 } 264 265 info = (struct HardLinkInfo *) malloc(sizeof(struct HardLinkInfo)); 266 267 if (info == NULL) { 268 if (fsckGetVerbosity(gp->context) >= kDebugLog) { 269 plog("hardLinkCheckBegin: malloc(%zu) failed\n", sizeof(struct HardLinkInfo)); 270 } 271 return 1; 272 } 273 274 info->privDirID = folderID; 275 info->priv_dir_itime = folderID ? rec.hfsPlusFolder.createDate : 0; 276 if (GetRootDir(gp, &rootFolder) == 0) { 277 info->root_dir_itime = rootFolder.hfsPlusFolder.createDate; 278 } else { 279 info->root_dir_itime = 0; 280 } 281 282 info->globals = gp; 283 284 /* We will use the ID of private metadata directory for file hard 285 * links to skip over hard link inode for an alias from directory 286 * hard link checks. 287 */ 288 gp->filelink_priv_dir_id = folderID; 289 290 291 info->fileBucket = calloc(1, sizeof(PrimeBuckets)); 292 if (info->fileBucket == NULL) { 293 if (fsckGetVerbosity(gp->context) >= kDebugLog) { 294 plog("HardLinkCheckBegin: prime bucket allocation failed\n"); 295 } 296 } 297 298 * cookie = info; 299 return (0); 300} 301 302/* 303 * HardLinkCheckEnd 304 * 305 * Dispose of captured data. 306 * Called after calling CheckHardLinks. 307 */ 308void 309HardLinkCheckEnd(void * cookie) 310{ 311 if (cookie) { 312 struct HardLinkInfo * infoPtr; 313 314 infoPtr = (struct HardLinkInfo *) cookie; 315 if (infoPtr->fileBucket) { 316 free(infoPtr->fileBucket); 317 infoPtr->fileBucket = NULL; 318 } 319 DisposeMemory(cookie); 320 } 321 322} 323 324/* Structures for file hard link hash used when a 325 * file hard link created in pre-Leopard OS is detected 326 * i.e. the file inode and hard links do not have the 327 * kHFSHasLinkChainBit set, and the first link, the 328 * previous link and the next link IDs are zero. The 329 * link count for such hard links cannot be verified 330 * using CRT, therefore it is accounted in this hash. 331 */ 332#define FILELINK_HASH_SIZE 257 333 334struct filelink_hash { 335 UInt32 link_ref_num; 336 UInt32 found_link_count; 337 UInt32 calc_link_count; 338 struct filelink_hash *next; 339}; 340 341struct filelink_hash **filelink_head = NULL; 342UInt32 filelink_entry_count = 0; 343 344/* Search and return pointer to the entry for given inode ID. 345 * If no entry is found, return NULL. 346 */ 347static struct filelink_hash *filelink_hash_search(UInt32 link_ref_num) 348{ 349 struct filelink_hash *cur; 350 351 if (filelink_head == NULL) { 352 return NULL; 353 } 354 355 cur = filelink_head[link_ref_num % FILELINK_HASH_SIZE]; 356 while (cur) { 357 if (link_ref_num == cur->link_ref_num) { 358 break; 359 } 360 cur = cur->next; 361 } 362 363 return cur; 364} 365 366/* Allocate and insert entry for given inode ID in the 367 * hash. The caller function is responsible for searching 368 * for duplicates before calling this function. 369 * Returns the pointer to the new hash entry. 370 */ 371static struct filelink_hash *filelink_hash_insert(UInt32 link_ref_num) 372{ 373 struct filelink_hash *cur; 374 375 cur = malloc(sizeof(struct filelink_hash)); 376 if (!cur) { 377 return cur; 378 } 379 cur->link_ref_num = link_ref_num; 380 cur->found_link_count = 0; 381 cur->calc_link_count = 0; 382 cur->next = filelink_head[link_ref_num % FILELINK_HASH_SIZE]; 383 filelink_head[link_ref_num % FILELINK_HASH_SIZE] = cur; 384 filelink_entry_count++; 385 return cur; 386} 387 388/* Update the hash with information about a file hard link 389 * that points to given inode ID. The calculated link count 390 * for given inode is incremented. 391 * Returns zero if the value was successfully updated to hash, 392 * and ENOMEM on error. 393 */ 394static int filelink_hash_link(UInt32 link_ref_num) 395{ 396 struct filelink_hash *cur; 397 398 /* If no hash exists, allocate the hash */ 399 if (filelink_head == NULL) { 400 filelink_head = calloc(FILELINK_HASH_SIZE, sizeof(struct filelink_hash *)); 401 if (filelink_head == NULL) { 402 return ENOMEM; 403 } 404 } 405 406 cur = filelink_hash_search(link_ref_num); 407 if (!cur) { 408 cur = filelink_hash_insert(link_ref_num); 409 } 410 if (cur) { 411 cur->calc_link_count++; 412 return 0; 413 } 414 415 return ENOMEM; 416} 417 418/* Update the hash with information about given file inode. 419 * The found link count in the hash is updated with the 420 * link count value provided. 421 * Returns zero if the value was successfully updated to hash, 422 * and ENOMEM on error. 423 */ 424int filelink_hash_inode(UInt32 link_ref_num, UInt32 linkCount) 425{ 426 struct filelink_hash *cur; 427 428 /* If no hash exists, allocate the hash */ 429 if (filelink_head == NULL) { 430 filelink_head = calloc(FILELINK_HASH_SIZE, sizeof(struct filelink_hash *)); 431 if (filelink_head == NULL) { 432 return ENOMEM; 433 } 434 } 435 436 cur = filelink_hash_search(link_ref_num); 437 if (!cur) { 438 cur = filelink_hash_insert(link_ref_num); 439 } 440 if (cur) { 441 cur->found_link_count = linkCount; 442 return 0; 443 } 444 return ENOMEM; 445} 446 447/* If the file link hash was used to account for 448 * link count of file hard links created on pre-Leopard 449 * OS, destroy the hash by freeing all allocated 450 * memory. 451 */ 452static void filelink_hash_destroy(void) 453{ 454 int i; 455 struct filelink_hash *cur; 456 457 for (i = 0; i < FILELINK_HASH_SIZE; i++) { 458 while (filelink_head[i]) { 459 cur = filelink_head[i]; 460 filelink_head[i] = cur->next; 461 free (cur); 462 } 463 } 464 free(filelink_head); 465 filelink_head = NULL; 466 filelink_entry_count = 0; 467} 468 469/* 470 * CaptureHardLink 471 * 472 * Capture indirect link info. 473 * Called for every indirect link in the catalog. 474 */ 475void 476CaptureHardLink(void *cookie, const HFSPlusCatalogFile *file) 477{ 478 struct HardLinkInfo * info = (struct HardLinkInfo *) cookie; 479 480 /* A file hard link created on pre-Leopard OS does not 481 * have kHFSHasLinkChainBit set or prev/next link IDs. 482 * Ignore such file hard links from all check and CRT account 483 * and instead account the information in hash to verify the 484 * link counts later. 485 */ 486 if ((info->fileBucket == NULL) || 487 (((file->flags & kHFSHasLinkChainMask) == 0) && 488 (file->hl_prevLinkID == 0) && 489 (file->hl_nextLinkID == 0))) { 490 filelink_hash_link(file->hl_linkReference); 491 } else { 492 /* For file hard links, add link reference number 493 * and catalog link ID pair to the prime buckets. 494 */ 495 hardlink_add_bucket(info->fileBucket, file->hl_linkReference, 496 file->fileID); 497 498 if ((file->flags & kHFSHasLinkChainMask) == 0) { 499 record_link_badchain(info->globals, false); 500 } 501 } 502 if ((info->priv_dir_itime && file->createDate != info->priv_dir_itime) && 503 (info->root_dir_itime && file->createDate != info->root_dir_itime)) { 504 RepairOrderPtr p; 505 char str1[12]; 506 char str2[12]; 507 uint32_t correct; 508 509 if (debug) 510 plog("Hard Link catalog entry %u has bad time %u (should be %u, or at least %u)\n", 511 file->fileID, file->createDate, info->priv_dir_itime, info->root_dir_itime); 512 correct = info->priv_dir_itime; 513 514 p = AllocMinorRepairOrder(info->globals, 0); 515 if (p == NULL) { 516 if (debug) 517 plog("Unable to allocate hard link time repair order!"); 518 return; 519 } 520 521 fsckPrint(info->globals->context, E_BadHardLinkDate); 522 snprintf(str1, sizeof(str1), "%u", correct); 523 snprintf(str2, sizeof(str2), "%u", file->createDate); 524 fsckPrint(info->globals->context, E_BadValue, str1, str2); 525 526 p->type = E_BadHardLinkDate; 527 p->parid = file->fileID; 528 p->correct = info->priv_dir_itime; 529 p->incorrect = file->createDate; 530 } 531 532 return; 533} 534 535/* 536 * RepairHardLinkChains 537 * 538 * Cycle through the catalog tree, and generate repair orders for hard 539 * links that may be broken. 540 */ 541int 542RepairHardLinkChains(SGlobPtr gp, Boolean isdir) 543{ 544 int result = 0; 545 struct IndirectLinkInfo *linkInfo = NULL; 546 CatalogRecord rec; 547 HFSPlusCatalogKey *keyp; 548 BTreeIterator iterator; 549 FSBufferDescriptor btrec; 550 UInt16 reclen; 551 UInt32 linkID, inodeID; 552 UInt32 metadirid; 553 SFCB *fcb; 554 size_t prefixlen; 555 int slotsUsed = 0, slots = 0; 556 char *prefixName; 557 UInt32 folderID; 558 UInt32 link_ref_num; 559 int entries; 560 UInt32 flags; 561 562 if (isdir) { 563 metadirid = gp->dirlink_priv_dir_id; 564 prefixlen = strlen(HFS_DIRINODE_PREFIX); 565 prefixName = HFS_DIRINODE_PREFIX; 566 } else { 567 metadirid = gp->filelink_priv_dir_id; 568 prefixlen = strlen(HFS_INODE_PREFIX); 569 prefixName = HFS_INODE_PREFIX; 570 } 571 572 if (metadirid == 0) { 573 if (fsckGetVerbosity(gp->context) >= kDebugLog) { 574 if (isdir) { 575 plog ("\tPrivate directory for dirlinks not found. Stopping repairs.\n"); 576 } else { 577 plog ("\tPrivate directory for filelinks not found. Stopping repairs.\n"); 578 } 579 } 580 result = ENOENT; 581 goto done; 582 } 583 584 // Initialize the hash 585 if (GetPrivateDir(gp, &rec) == 0 && rec.hfsPlusFolder.valence != 0) { 586 entries = rec.hfsPlusFolder.valence + 10; 587 folderID = rec.hfsPlusFolder.folderID; 588 } else { 589 entries = 1000; 590 folderID = 0; 591 } 592 593 for (slots = 1; slots <= entries; slots <<= 1) 594 continue; 595 if (slots < (entries + (entries/3))) 596 slots <<= 1; 597 linkInfo = calloc(slots, sizeof(struct IndirectLinkInfo)); 598 if (linkInfo == NULL) { 599 if (fsckGetVerbosity(gp->context) >= kDebugLog) { 600 plog("RepairHardLinkChains: calloc(%d, %zu) failed\n", slots, sizeof(struct IndirectLinkInfo)); 601 } 602 result = ENOMEM; 603 goto done; 604 } 605 // Done initializing the hash 606 607 // Set up the catalog BTree iterator 608 // (start from the root folder, and work our way down) 609 fcb = gp->calculatedCatalogFCB; 610 ClearMemory(&iterator, sizeof(iterator)); 611 keyp = (HFSPlusCatalogKey*)&iterator.key; 612 BuildCatalogKey(kHFSRootFolderID, NULL, true, (CatalogKey*)keyp); 613 btrec.bufferAddress = &rec; 614 btrec.itemCount = 1; 615 btrec.itemSize = sizeof(rec); 616 617 /* Counter for number of inodes found and verified in the 618 * hash. When an inode is found when checking the hard links, 619 * the value is incremented. When an inode's linked list and 620 * link count are verified, the value is decremented. If 621 * this value remains non-zero at the end, there are 622 * orphan hard links. 623 */ 624 entries = 0; 625 626 /* 627 * This chunk of code iterates through the entire catalog BTree. 628 * For each hard link node (that is, the "directory entry" that 629 * points to the actual node in the metadata directory), it may 630 * add it to the hash (if it doesn't exist yet; it also then increments 631 * the link count for that "inode"); it also creates an array 632 * of <previous, fileid, next> for the linked list. 633 */ 634 for (result = BTIterateRecord(fcb, kBTreeFirstRecord, &iterator, &btrec, &reclen); 635 result == 0; 636 result = BTIterateRecord(fcb, kBTreeNextRecord, &iterator, &btrec, &reclen)) { 637 HFSPlusCatalogFile *file = &rec.hfsPlusFile; 638 Boolean islink = false; 639 640 if (rec.recordType != kHFSPlusFileRecord) 641 continue; 642 643 if (isdir) { 644 /* Assume that this is a directory hard link if 645 * the atleast one value in finder info corresponds to 646 * alias, and the alias is not a file inode, and 647 * either the inode number is greater than 648 * kHFSFirstUserCatalogNodeID or the flag has 649 * kHFSHasLinkChainBit set. 650 */ 651 if (((file->userInfo.fdType == kHFSAliasType) || 652 (file->userInfo.fdCreator == kHFSAliasCreator) || 653 (file->userInfo.fdFlags & kIsAlias)) && 654 (keyp->parentID != gp->filelink_priv_dir_id) && 655 ((file->hl_linkReference >= kHFSFirstUserCatalogNodeID) || 656 (file->flags & kHFSHasLinkChainMask))) { 657 flags = rec.hfsPlusFile.flags; 658 islink = true; 659 } 660 } else if (file->userInfo.fdType == kHardLinkFileType && 661 file->userInfo.fdCreator == kHFSPlusCreator) { 662 flags = rec.hfsPlusFile.flags; 663 islink = true; 664 } 665 if (islink) { 666 struct IndirectLinkInfo *li = NULL; 667 struct HardLinkList *tlist = NULL; 668 int i; 669 int count; 670 671 linkID = file->fileID; 672 inodeID = file->bsdInfo.special.iNodeNum; 673 674 /* Now that we are in repair, all hard links should 675 * have this bit set because we upgrade all pre-Leopard 676 * file hard links to Leopard hard links on any 677 * file hard link repairs. 678 */ 679 if ((flags & kHFSHasLinkChainMask) == 0) { 680 record_link_badflags(gp, linkID, isdir, flags, 681 flags | kHFSHasLinkChainMask); 682 } 683 684 /* For directory hard links, check ownerFlags and 685 * finderInfo because we could have missed creating 686 * repair orders in verification. Verification could 687 * have stopped before we saw this record because it 688 * stops as soon as it determines that it needs full 689 * knowledge of hard links on the disk during repair. 690 */ 691 if (isdir) { 692 /* Check if the directory hard link has UF_IMMUTABLE bit set */ 693 if ((file->bsdInfo.ownerFlags & UF_IMMUTABLE) == 0) { 694 record_dirlink_badownerflags(gp, file->fileID, 695 file->bsdInfo.ownerFlags, 696 file->bsdInfo.ownerFlags | UF_IMMUTABLE, true); 697 } 698 699 /* Check Finder Info */ 700 if ((file->userInfo.fdType != kHFSAliasType) || 701 (file->userInfo.fdCreator != kHFSAliasCreator) || 702 ((file->userInfo.fdFlags & kIsAlias) == 0)) { 703 record_link_badfinderinfo(gp, file->fileID, true); 704 } 705 } 706 707 /* For directory hard links, hash using inodeID. For 708 * file hard links, hash using link reference number 709 * (which is same as inode ID for file hard links 710 * created post-Tiger). For each inodeID, add the 711 * <prev, id, next> triad. 712 */ 713 li = hash_search(inodeID, slots, slotsUsed, linkInfo); 714 if (li) { 715 li->linkCount++; 716 } else { 717 entries++; 718 /* hash_insert() initializes linkCount to 1 */ 719 hash_insert(inodeID, slots, slotsUsed++, linkInfo); 720 li = hash_search(inodeID, slots, slotsUsed, linkInfo); 721 } 722 if (li == NULL) { 723 /* 724 * Either the hash passed in should have the entry, or 725 * the one we just created should (because we just added it); 726 * either way, if it's not here, we've got something weird 727 * going on, so let's just abort now. 728 */ 729 result = ENOENT; 730 goto done; 731 } 732 733 count = li->linkCount - 1; 734 /* Reallocate memory to store information about file/directory hard links */ 735 if ((count % 10) == 0) { 736 tlist = realloc(li->list, (count + 10) * sizeof(struct HardLinkList)); 737 if (tlist == NULL) { 738 free(li->list); 739 li->list = NULL; 740 result = ENOMEM; 741 goto done; 742 } else { 743 li->list = tlist; // May be the same 744 for (i = count; i < (count + 10); i++) { 745 memset(&li->list[i], 0, sizeof(li->list[i])); 746 } 747 } 748 } 749 750 /* Store information about this hard link */ 751 if (li->list) { 752 li->list[count].fileID = linkID; 753 li->list[count].prev = file->hl_prevLinkID; 754 li->list[count].next = file->hl_nextLinkID; 755 } 756 } 757 } 758 759 if (result == btNotFound) 760 result = 0; // If we hit the end of the catalog tree, that's okay 761 762 if (result) { 763 goto done; 764 } 765 766 /* 767 * Next, we iterate through the metadata directory, and check the linked list. 768 */ 769 770 ClearMemory(&iterator, sizeof(iterator)); 771 keyp = (HFSPlusCatalogKey*)&iterator.key; 772 BuildCatalogKey(metadirid, NULL, true, (CatalogKey*)keyp); 773 btrec.bufferAddress = &rec; 774 btrec.itemCount = 1; 775 btrec.itemSize = sizeof(rec); 776 777 for (result = BTSearchRecord(fcb, &iterator, kInvalidMRUCacheKey, &btrec, &reclen, &iterator); 778 result == 0; 779 result = BTIterateRecord(fcb, kBTreeNextRecord, &iterator, &btrec, &reclen)) { 780 unsigned char filename[64]; 781 size_t len; 782 struct IndirectLinkInfo *li = NULL; 783 784 if (rec.recordType == kHFSPlusFolderThreadRecord || 785 rec.recordType == kHFSPlusFileThreadRecord) 786 continue; 787 if (keyp->parentID != metadirid) 788 break; 789 if ((isdir && rec.recordType != kHFSPlusFolderRecord) || 790 (!isdir && rec.recordType != kHFSPlusFileRecord)) 791 continue; 792 (void)utf_encodestr(keyp->nodeName.unicode, 793 keyp->nodeName.length * 2, 794 filename, &len, sizeof(filename)); 795 filename[len] = 0; 796 if (strstr((char*)filename, prefixName) != (char*)filename) 797 continue; 798 799 if (isdir) { 800 inodeID = rec.hfsPlusFolder.folderID; 801 link_ref_num = 0; 802 flags = rec.hfsPlusFolder.flags; 803 li = hash_search(inodeID, slots, slotsUsed, linkInfo); 804 } else { 805 inodeID = rec.hfsPlusFile.fileID; 806 link_ref_num = atol((char*)&filename[prefixlen]); 807 flags = rec.hfsPlusFile.flags; 808 li = hash_search(link_ref_num, slots, slotsUsed, linkInfo); 809 } 810 811 /* file/directory inode should always have kHFSHasLinkChainBit set */ 812 if ((flags & kHFSHasLinkChainMask) == 0) { 813 record_inode_badflags(gp, inodeID, isdir, flags, 814 flags | kHFSHasLinkChainMask, true); 815 } 816 817 if (li) { 818 UInt32 first_link_id = 0; 819 uint32_t linkCount = 0; 820 821 result = get_first_link_id(gp, &rec, inodeID, isdir, &first_link_id); 822 if (result != 0) { 823 if (fsckGetVerbosity(gp->context) >= kDebugLog) 824 plog("\tError getting first link ID for inode = %u (result=%d)\n", inodeID, result); 825 } 826 827 /* Check and create repairs for doubly linked list */ 828 result = CheckHardLinkList(gp, inodeID, li->list, li->linkCount, first_link_id); 829 830 linkCount = isdir ? rec.hfsPlusFolder.bsdInfo.special.linkCount : rec.hfsPlusFile.bsdInfo.special.linkCount; 831 if (linkCount != li->linkCount) { 832 RecordBadLinkCount(gp, inodeID, linkCount, li->linkCount); 833 } 834 835 li->flags |= LINKINFO_CHECK; 836 entries--; 837 } else { 838 /* Not found in hash, this is orphaned file/directory inode */ 839 RecordOrphanInode(gp, isdir, inodeID); 840 } 841 } 842 843 if (result == btNotFound) { 844 result = 0; 845 } 846 if (result) { 847 goto done; 848 } 849 850 /* Check for orphan hard links */ 851 if (entries) { 852 int i, j; 853 for (i = 0; i < slots; i++) { 854 /* If node is initialized but never checked, record orphan link */ 855 if ((linkInfo[i].flags & LINKINFO_INIT) && 856 ((linkInfo[i].flags & LINKINFO_CHECK) == 0)) { 857 for (j = 0; j < linkInfo[i].linkCount; j++) { 858 RecordOrphanLink(gp, isdir, linkInfo[i].list[j].fileID); 859 } 860 } 861 } 862 } 863 864done: 865 if (linkInfo) { 866 int i; 867 for (i = 0; i < slots; i++) { 868 if (linkInfo[i].list) 869 free(linkInfo[i].list); 870 } 871 free(linkInfo); 872 } 873 874 return result; 875} 876 877/* 878 * CheckHardLinks 879 * 880 * Check indirect node link counts against the indirect 881 * links that were found. There are 4 possible problems 882 * that can occur. 883 * 1. orphaned indirect node (i.e. no links found) 884 * 2. orphaned indirect link (i.e. indirect node missing) 885 * 3. incorrect link count 886 * 4. indirect link id was 0 (i.e. link id wasn't preserved) 887 */ 888int 889CheckHardLinks(void *cookie) 890{ 891 struct HardLinkInfo *info = (struct HardLinkInfo *)cookie; 892 SGlobPtr gp; 893 UInt32 folderID; 894 SFCB * fcb; 895 CatalogRecord rec; 896 HFSPlusCatalogKey * keyp; 897 BTreeIterator iterator; 898 FSBufferDescriptor btrec; 899 UInt16 reclen; 900 size_t len; 901 size_t prefixlen; 902 int result; 903 unsigned char filename[64]; 904 PrimeBuckets *catBucket; 905 906 /* All done if no hard links exist. */ 907 if (info == NULL) 908 return (0); 909 910 gp = info->globals; 911 fsckPrint(gp->context, hfsHardLinkCheck); 912 913 folderID = info->privDirID; 914 915 catBucket = calloc(1, sizeof(PrimeBuckets)); 916 if (catBucket == NULL) { 917 if (fsckGetVerbosity(gp->context) >= kDebugLog) { 918 plog("CheckHardLinks: calloc(1, %zu) failed\n", sizeof(PrimeBuckets)); 919 } 920 result = ENOMEM; 921 goto exit; 922 } 923 924 925 fcb = gp->calculatedCatalogFCB; 926 prefixlen = strlen(HFS_INODE_PREFIX); 927 ClearMemory(&iterator, sizeof(iterator)); 928 keyp = (HFSPlusCatalogKey*)&iterator.key; 929 btrec.bufferAddress = &rec; 930 btrec.itemCount = 1; 931 btrec.itemSize = sizeof(rec); 932 /* 933 * position iterator at folder thread record 934 * (i.e. one record before first child) 935 */ 936 ClearMemory(&iterator, sizeof(iterator)); 937 BuildCatalogKey(folderID, NULL, true, (CatalogKey *)keyp); 938 result = BTSearchRecord(fcb, &iterator, kInvalidMRUCacheKey, &btrec, 939 &reclen, &iterator); 940 if ((result != 0) && (result != btNotFound)) { 941 goto exit; 942 } 943 944 /* Visit all the children in private directory. */ 945 for (;;) { 946 result = BTIterateRecord(fcb, kBTreeNextRecord, &iterator, 947 &btrec, &reclen); 948 if (result || keyp->parentID != folderID) 949 break; 950 951 if (rec.recordType != kHFSPlusFileRecord) 952 continue; 953 954 (void) utf_encodestr(keyp->nodeName.unicode, 955 keyp->nodeName.length * 2, 956 filename, &len, sizeof(filename)); 957 filename[len] = '\0'; 958 959 /* Report Orphaned nodes only in debug mode */ 960 if ((strstr((char *)filename, HFS_DELETE_PREFIX) == (char *)filename) && 961 (fsckGetVerbosity(gp->context) == kDebugLog)) { 962 RecordOrphanOpenUnlink(gp, folderID, filename); 963 continue; 964 } 965 966 if (strstr((char *)filename, HFS_INODE_PREFIX) != (char *)filename) 967 continue; 968 969 result = inode_check(gp, catBucket, (CatalogRecord*)&rec, (CatalogKey*)keyp, false); 970 if (result) { 971 break; 972 } 973 filename[0] = '\0'; 974 } 975 976 if (result == btNotFound) { 977 result = 0; 978 } 979 980 /* 981 * If we've reached this point, and result is clean, 982 * then we need to compare the two hard link 983 * buckets: if they don't match, then we have a hard link chain error, and 984 * need to either repair it, or just mark the error. 985 */ 986 if ((result == 0) && (info->fileBucket != NULL)) { 987 result = compare_prime_buckets(catBucket, info->fileBucket); 988 if (result) { 989 record_link_badchain(gp, false); 990 if (fsckGetVerbosity(gp->context) >= kDebugLog) { 991 plog("\tfilelink prime buckets do not match\n"); 992 } 993 goto exit; 994 } 995 } 996 997 /* If hard links created in pre-Leopard OS were detected, they were 998 * added to the hash for checking link counts later. Check the 999 * link counts from the hash. Note that the hard links created in 1000 * pre-Leopard OS do not have kHFSHasLinkChainBit set in the inode 1001 * and the hard links, and the first/prev/next ID is zero --- and 1002 * hence they were ignored from CRT check and added to hash. 1003 */ 1004 if (filelink_entry_count) { 1005 int i; 1006 struct filelink_hash *cur; 1007 1008 /* Since pre-Leopard OS hard links were detected, they 1009 * should be updated to new version. This is however 1010 * an opportunistic repair and no corruption will be 1011 * reported. This will be performed only if any other 1012 * file hard link repairs are performed. 1013 */ 1014 if (fsckGetVerbosity(gp->context) >= kDebugLog) { 1015 plog("\tCheckHardLinks: found %u pre-Leopard file inodes.\n", filelink_entry_count); 1016 } 1017 1018 for (i = 0; i < FILELINK_HASH_SIZE; i++) { 1019 cur = filelink_head[i]; 1020 while (cur) { 1021 if ((cur->found_link_count == 0) || 1022 (cur->calc_link_count == 0) || 1023 (cur->found_link_count != cur->calc_link_count)) { 1024 record_link_badchain(gp, false); 1025 goto exit; 1026 } 1027 cur = cur->next; 1028 } 1029 } 1030 } 1031 1032exit: 1033 if (filelink_entry_count) { 1034 filelink_hash_destroy(); 1035 } 1036 1037 if (catBucket) 1038 free(catBucket); 1039 1040 return (result); 1041} 1042 1043/* 1044 * GetPrivateDir 1045 * 1046 * Get catalog entry for the "HFS+ Private Data" directory. 1047 * The indirect nodes are stored in this directory. 1048 */ 1049static int 1050GetPrivateDir(SGlobPtr gp, CatalogRecord * rec) 1051{ 1052 HFSPlusCatalogKey * keyp; 1053 BTreeIterator iterator; 1054 FSBufferDescriptor btrec; 1055 UInt16 reclen; 1056 int result; 1057 Boolean isHFSPlus; 1058 1059 isHFSPlus = VolumeObjectIsHFSPlus( ); 1060 if (!isHFSPlus) 1061 return (-1); 1062 1063 ClearMemory(&iterator, sizeof(iterator)); 1064 keyp = (HFSPlusCatalogKey*)&iterator.key; 1065 1066 btrec.bufferAddress = rec; 1067 btrec.itemCount = 1; 1068 btrec.itemSize = sizeof(CatalogRecord); 1069 1070 /* look up record for HFS+ private folder */ 1071 ClearMemory(&iterator, sizeof(iterator)); 1072 CopyMemory(&gMetaDataDirKey, keyp, sizeof(gMetaDataDirKey)); 1073 result = BTSearchRecord(gp->calculatedCatalogFCB, &iterator, 1074 kInvalidMRUCacheKey, &btrec, &reclen, &iterator); 1075 1076 return (result); 1077} 1078 1079/* 1080 * GetRootDir 1081 * 1082 * Get catalog entry for the Root Folder. 1083 */ 1084static int 1085GetRootDir(SGlobPtr gp, CatalogRecord * rec) 1086{ 1087 CatalogKey key; 1088 uint16_t recSize; 1089 int result; 1090 Boolean isHFSPlus; 1091 1092 isHFSPlus = VolumeObjectIsHFSPlus( ); 1093 if (!isHFSPlus) 1094 return (-1); 1095 1096 result = GetCatalogRecordByID(gp, kHFSRootFolderID, isHFSPlus, &key, rec, &recSize); 1097 1098 return (result); 1099} 1100 1101/* 1102 * RecordOrphanLink 1103 * 1104 * Record a repair to delete an orphaned hard links, i.e. hard links 1105 * that do not have any corresponding inode. 1106 */ 1107static int 1108RecordOrphanLink(SGlobPtr gp, Boolean isdir, UInt32 linkID) 1109{ 1110 RepairOrderPtr p; 1111 1112 fsckPrint(gp->context, isdir ? E_OrphanDirLink : E_OrphanFileLink, linkID); 1113 1114 p = AllocMinorRepairOrder(gp, 0); 1115 if (p == NULL) 1116 return ENOMEM; 1117 1118 p->type = isdir ? E_OrphanDirLink : E_OrphanFileLink; 1119 p->parid = linkID; 1120 1121 gp->CatStat |= S_LinkErrRepair; 1122 1123 return 0; 1124} 1125 1126/* 1127 * RecordOrphanInode 1128 * 1129 * Record a repair for orphan inode i.e. inodes that do not have 1130 * any corresponding hard links. 1131 */ 1132static int 1133RecordOrphanInode(SGlobPtr gp, Boolean isdir, UInt32 inodeID) 1134{ 1135 RepairOrderPtr p; 1136 1137 fsckPrint(gp->context, isdir ? E_OrphanDirInode : E_OrphanFileInode, inodeID); 1138 1139 p = AllocMinorRepairOrder(gp, 0); 1140 if (p == NULL) 1141 return ENOMEM; 1142 1143 p->type = isdir ? E_OrphanDirInode : E_OrphanFileInode; 1144 p->parid = inodeID; 1145 1146 gp->CatStat |= S_LinkErrRepair; 1147 1148 return 0; 1149} 1150 1151/* 1152 * RecordOrphanOpenUnlink 1153 * 1154 * This is only called when debugging is turned on. Don't 1155 * record an actual error, just print out a message. 1156 */ 1157static int 1158RecordOrphanOpenUnlink(SGlobPtr gp, UInt32 parID, unsigned char* filename) 1159{ 1160 fsckPrint(gp->context, E_UnlinkedFile, filename); 1161 1162 return (noErr); 1163} 1164 1165 1166static int 1167RecordBadHardLinkChainFirst(SGlobPtr gp, UInt32 fileID, UInt32 is, UInt32 shouldbe) 1168{ 1169 RepairOrderPtr p; 1170 char goodstr[16], badstr[16]; 1171 1172 fsckPrint(gp->context, E_InvalidLinkChainFirst, fileID); 1173 sprintf(goodstr, "%u", shouldbe); 1174 sprintf(badstr, "%u", is); 1175 fsckPrint(gp->context, E_BadValue, goodstr, badstr); 1176 1177 p = AllocMinorRepairOrder(gp, 0); 1178 1179 if (p == NULL) { 1180 return (ENOMEM); 1181 } 1182 1183 p->type = E_InvalidLinkChainFirst; 1184 p->incorrect = is; 1185 p->correct = shouldbe; 1186 p->hint = 0; 1187 p->parid = fileID; // *Not* the parent ID! 1188 gp->CatStat |= S_LinkErrRepair; 1189 1190 return (0); 1191} 1192 1193 1194static int 1195RecordBadHardLinkPrev(SGlobPtr gp, UInt32 fileID, UInt32 is, UInt32 shouldbe) 1196{ 1197 RepairOrderPtr p; 1198 char goodstr[16], badstr[16]; 1199 1200 fsckPrint(gp->context, E_InvalidLinkChainPrev, fileID); 1201 sprintf(goodstr, "%u", shouldbe); 1202 sprintf(badstr, "%u", is); 1203 fsckPrint(gp->context, E_BadValue, goodstr, badstr); 1204 1205 p = AllocMinorRepairOrder(gp, 0); 1206 if (p == NULL) 1207 return (R_NoMem); 1208 1209 p->type = E_InvalidLinkChainPrev; 1210 p->incorrect = is; 1211 p->correct = shouldbe; 1212 p->hint = 0; 1213 p->parid = fileID; // *Not* the parent ID 1214 gp->CatStat |= S_LinkCount; 1215 return (0); 1216} 1217 1218static int 1219RecordBadHardLinkNext(SGlobPtr gp, UInt32 fileID, UInt32 is, UInt32 shouldbe) 1220{ 1221 RepairOrderPtr p; 1222 char goodstr[16], badstr[16]; 1223 1224 fsckPrint(gp->context, E_InvalidLinkChainNext, fileID); 1225 1226 sprintf(goodstr, "%u", shouldbe); 1227 sprintf(badstr, "%u", is); 1228 fsckPrint(gp->context, E_BadValue, goodstr, badstr); 1229 1230 p = AllocMinorRepairOrder(gp, 0); 1231 if (p == NULL) 1232 return (R_NoMem); 1233 1234 p->type = E_InvalidLinkChainNext; 1235 p->incorrect = is; 1236 p->correct = shouldbe; 1237 p->hint = 0; 1238 p->parid = fileID; // *Not* the parent ID 1239 gp->CatStat |= S_LinkCount; 1240 return (0); 1241} 1242 1243static int 1244RecordBadLinkCount(SGlobPtr gp, UInt32 inodeID, UInt32 is, UInt32 shouldbe) 1245{ 1246 RepairOrderPtr p; 1247 char goodstr[16], badstr[16]; 1248 fsckPrint(gp->context, E_InvalidLinkCount, inodeID); 1249 1250 sprintf(goodstr, "%u", shouldbe); 1251 sprintf(badstr, "%u", is); 1252 fsckPrint(gp->context, E_BadValue, goodstr, badstr); 1253 1254 p = AllocMinorRepairOrder(gp, 0); 1255 if (p == NULL) 1256 return (R_NoMem); 1257 1258 p->type = E_InvalidLinkCount; 1259 p->incorrect = is; 1260 p->correct = shouldbe; 1261 p->hint = 0; 1262 p->parid = inodeID; // *Not* the parent ID 1263 return (0); 1264} 1265 1266 1267static void 1268hash_insert(UInt32 linkID, int totalSlots, int slotsUsed, struct IndirectLinkInfo *linkInfo) 1269{ 1270 int i, last; 1271 1272 i = linkID & (totalSlots - 1); 1273 1274 last = (i + (totalSlots-1)) % totalSlots; 1275 while ((i != last) && 1276 (linkInfo[i].flags & LINKINFO_INIT) && 1277 (linkInfo[i].linkID != linkID)) { 1278 i = (i + 1) % totalSlots; 1279 } 1280 1281 if ((linkInfo[i].flags & LINKINFO_INIT) == 0) { 1282 if (linkInfo[i].list) { 1283 plog ("hash: overwriting data! (old:%u, new:%u)\n", linkInfo[i].linkID, linkID); 1284 exit(13); 1285 } 1286 linkInfo[i].flags |= LINKINFO_INIT; 1287 linkInfo[i].linkID = linkID; 1288 linkInfo[i].linkCount = 1; 1289 } else if (linkInfo[i].linkID == linkID) { 1290 plog("hash: duplicate insert! (%d)\n", linkID); 1291 exit(13); 1292 } else { 1293 plog("hash table full (%d entries) \n", slotsUsed); 1294 exit(14); 1295 } 1296} 1297 1298 1299static struct IndirectLinkInfo * 1300hash_search(UInt32 linkID, int totalSlots, int slotsUsed, struct IndirectLinkInfo *linkInfo) 1301{ 1302 int i, last; 1303 int p = 1; 1304 1305 1306 i = linkID & (totalSlots - 1); 1307 1308 last = (i + (slotsUsed-1)) % totalSlots; 1309 while ((i != last) && 1310 (linkInfo[i].flags & LINKINFO_INIT) && 1311 (linkInfo[i].linkID != linkID)) { 1312 i = (i + 1) % totalSlots; 1313 ++p; 1314 } 1315 1316 if ((linkInfo[i].flags & LINKINFO_INIT) && 1317 (linkInfo[i].linkID == linkID)) { 1318 return (&linkInfo[i]); 1319 } else { 1320 return (NULL); 1321 } 1322} 1323