1 /* 2 * Copyright (C) 1995, 1996, 1997 Wolfgang Solfrank 3 * Copyright (c) 1995 Martin Husemann 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 14 * THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND ANY EXPRESS OR 15 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 16 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 17 * IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY DIRECT, INDIRECT, 18 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 19 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 20 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 21 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 23 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 24 */ 25 26 27 #include <sys/cdefs.h> 28 #ifndef lint 29 __RCSID("$NetBSD: fat.c,v 1.18 2006/06/05 16:51:18 christos Exp $"); 30 static const char rcsid[] = 31 "$FreeBSD$"; 32 #endif /* not lint */ 33 34 #include <stdlib.h> 35 #include <string.h> 36 #include <ctype.h> 37 #include <stdio.h> 38 #include <unistd.h> 39 40 #include "ext.h" 41 #include "fsutil.h" 42 43 static int checkclnum(struct bootblock *, u_int, cl_t, cl_t *); 44 static int clustdiffer(cl_t, cl_t *, cl_t *, u_int); 45 static int tryclear(struct bootblock *, struct fatEntry *, cl_t, cl_t *); 46 static int _readfat(int, struct bootblock *, u_int, u_char **); 47 48 /*- 49 * The first 2 FAT entries contain pseudo-cluster numbers with the following 50 * layout: 51 * 52 * 31...... ........ ........ .......0 53 * rrrr1111 11111111 11111111 mmmmmmmm FAT32 entry 0 54 * rrrrsh11 11111111 11111111 11111xxx FAT32 entry 1 55 * 56 * 11111111 mmmmmmmm FAT16 entry 0 57 * sh111111 11111xxx FAT16 entry 1 58 * 59 * r = reserved 60 * m = BPB media ID byte 61 * s = clean flag (1 = dismounted; 0 = still mounted) 62 * h = hard error flag (1 = ok; 0 = I/O error) 63 * x = any value ok 64 */ 65 66 int 67 checkdirty(int fs, struct bootblock *boot) 68 { 69 off_t off; 70 u_char *buffer; 71 int ret = 0; 72 size_t len; 73 74 if (boot->ClustMask != CLUST16_MASK && boot->ClustMask != CLUST32_MASK) 75 return 0; 76 77 off = boot->bpbResSectors; 78 off *= boot->bpbBytesPerSec; 79 80 buffer = malloc(len = boot->bpbBytesPerSec); 81 if (buffer == NULL) { 82 perr("No space for FAT sectors (%zu)", len); 83 return 1; 84 } 85 86 if (lseek(fs, off, SEEK_SET) != off) { 87 perr("Unable to read FAT"); 88 goto err; 89 } 90 91 if ((size_t)read(fs, buffer, boot->bpbBytesPerSec) != 92 boot->bpbBytesPerSec) { 93 perr("Unable to read FAT"); 94 goto err; 95 } 96 97 /* 98 * If we don't understand the FAT, then the file system must be 99 * assumed to be unclean. 100 */ 101 if (buffer[0] != boot->bpbMedia || buffer[1] != 0xff) 102 goto err; 103 if (boot->ClustMask == CLUST16_MASK) { 104 if ((buffer[2] & 0xf8) != 0xf8 || (buffer[3] & 0x3f) != 0x3f) 105 goto err; 106 } else { 107 if (buffer[2] != 0xff || (buffer[3] & 0x0f) != 0x0f 108 || (buffer[4] & 0xf8) != 0xf8 || buffer[5] != 0xff 109 || buffer[6] != 0xff || (buffer[7] & 0x03) != 0x03) 110 goto err; 111 } 112 113 /* 114 * Now check the actual clean flag (and the no-error flag). 115 */ 116 if (boot->ClustMask == CLUST16_MASK) { 117 if ((buffer[3] & 0xc0) == 0xc0) 118 ret = 1; 119 } else { 120 if ((buffer[7] & 0x0c) == 0x0c) 121 ret = 1; 122 } 123 124 err: 125 free(buffer); 126 return ret; 127 } 128 129 /* 130 * Check a cluster number for valid value 131 */ 132 static int 133 checkclnum(struct bootblock *boot, u_int fat, cl_t cl, cl_t *next) 134 { 135 if (*next >= (CLUST_RSRVD&boot->ClustMask)) 136 *next |= ~boot->ClustMask; 137 if (*next == CLUST_FREE) { 138 boot->NumFree++; 139 return FSOK; 140 } 141 if (*next == CLUST_BAD) { 142 boot->NumBad++; 143 return FSOK; 144 } 145 if (*next < CLUST_FIRST 146 || (*next >= boot->NumClusters && *next < CLUST_EOFS)) { 147 pwarn("Cluster %u in FAT %d continues with %s cluster number %u\n", 148 cl, fat, 149 *next < CLUST_RSRVD ? "out of range" : "reserved", 150 *next&boot->ClustMask); 151 if (ask(0, "Truncate")) { 152 *next = CLUST_EOF; 153 return FSFATMOD; 154 } 155 return FSERROR; 156 } 157 return FSOK; 158 } 159 160 /* 161 * Read a FAT from disk. Returns 1 if successful, 0 otherwise. 162 */ 163 static int 164 _readfat(int fs, struct bootblock *boot, u_int no, u_char **buffer) 165 { 166 off_t off; 167 size_t len; 168 169 *buffer = malloc(len = boot->FATsecs * boot->bpbBytesPerSec); 170 if (*buffer == NULL) { 171 perr("No space for FAT sectors (%zu)", len); 172 return 0; 173 } 174 175 off = boot->bpbResSectors + no * boot->FATsecs; 176 off *= boot->bpbBytesPerSec; 177 178 if (lseek(fs, off, SEEK_SET) != off) { 179 perr("Unable to read FAT"); 180 goto err; 181 } 182 183 if ((size_t)read(fs, *buffer, boot->FATsecs * boot->bpbBytesPerSec) 184 != boot->FATsecs * boot->bpbBytesPerSec) { 185 perr("Unable to read FAT"); 186 goto err; 187 } 188 189 return 1; 190 191 err: 192 free(*buffer); 193 return 0; 194 } 195 196 /* 197 * Read a FAT and decode it into internal format 198 */ 199 int 200 readfat(int fs, struct bootblock *boot, u_int no, struct fatEntry **fp) 201 { 202 struct fatEntry *fat; 203 u_char *buffer, *p; 204 cl_t cl; 205 int ret = FSOK; 206 size_t len; 207 208 boot->NumFree = boot->NumBad = 0; 209 210 if (!_readfat(fs, boot, no, &buffer)) 211 return FSFATAL; 212 213 fat = malloc(len = boot->NumClusters * sizeof(struct fatEntry)); 214 if (fat == NULL) { 215 perr("No space for FAT clusters (%zu)", len); 216 free(buffer); 217 return FSFATAL; 218 } 219 (void)memset(fat, 0, len); 220 221 if (buffer[0] != boot->bpbMedia 222 || buffer[1] != 0xff || buffer[2] != 0xff 223 || (boot->ClustMask == CLUST16_MASK && buffer[3] != 0xff) 224 || (boot->ClustMask == CLUST32_MASK 225 && ((buffer[3]&0x0f) != 0x0f 226 || buffer[4] != 0xff || buffer[5] != 0xff 227 || buffer[6] != 0xff || (buffer[7]&0x0f) != 0x0f))) { 228 229 /* Windows 95 OSR2 (and possibly any later) changes 230 * the FAT signature to 0xXXffff7f for FAT16 and to 231 * 0xXXffff0fffffff07 for FAT32 upon boot, to know that the 232 * file system is dirty if it doesn't reboot cleanly. 233 * Check this special condition before errorring out. 234 */ 235 if (buffer[0] == boot->bpbMedia && buffer[1] == 0xff 236 && buffer[2] == 0xff 237 && ((boot->ClustMask == CLUST16_MASK && buffer[3] == 0x7f) 238 || (boot->ClustMask == CLUST32_MASK 239 && buffer[3] == 0x0f && buffer[4] == 0xff 240 && buffer[5] == 0xff && buffer[6] == 0xff 241 && buffer[7] == 0x07))) 242 ret |= FSDIRTY; 243 else { 244 /* just some odd byte sequence in FAT */ 245 246 switch (boot->ClustMask) { 247 case CLUST32_MASK: 248 pwarn("%s (%02x%02x%02x%02x%02x%02x%02x%02x)\n", 249 "FAT starts with odd byte sequence", 250 buffer[0], buffer[1], buffer[2], buffer[3], 251 buffer[4], buffer[5], buffer[6], buffer[7]); 252 break; 253 case CLUST16_MASK: 254 pwarn("%s (%02x%02x%02x%02x)\n", 255 "FAT starts with odd byte sequence", 256 buffer[0], buffer[1], buffer[2], buffer[3]); 257 break; 258 default: 259 pwarn("%s (%02x%02x%02x)\n", 260 "FAT starts with odd byte sequence", 261 buffer[0], buffer[1], buffer[2]); 262 break; 263 } 264 265 266 if (ask(1, "Correct")) 267 ret |= FSFIXFAT; 268 } 269 } 270 switch (boot->ClustMask) { 271 case CLUST32_MASK: 272 p = buffer + 8; 273 break; 274 case CLUST16_MASK: 275 p = buffer + 4; 276 break; 277 default: 278 p = buffer + 3; 279 break; 280 } 281 for (cl = CLUST_FIRST; cl < boot->NumClusters;) { 282 switch (boot->ClustMask) { 283 case CLUST32_MASK: 284 fat[cl].next = p[0] + (p[1] << 8) 285 + (p[2] << 16) + (p[3] << 24); 286 fat[cl].next &= boot->ClustMask; 287 ret |= checkclnum(boot, no, cl, &fat[cl].next); 288 cl++; 289 p += 4; 290 break; 291 case CLUST16_MASK: 292 fat[cl].next = p[0] + (p[1] << 8); 293 ret |= checkclnum(boot, no, cl, &fat[cl].next); 294 cl++; 295 p += 2; 296 break; 297 default: 298 fat[cl].next = (p[0] + (p[1] << 8)) & 0x0fff; 299 ret |= checkclnum(boot, no, cl, &fat[cl].next); 300 cl++; 301 if (cl >= boot->NumClusters) 302 break; 303 fat[cl].next = ((p[1] >> 4) + (p[2] << 4)) & 0x0fff; 304 ret |= checkclnum(boot, no, cl, &fat[cl].next); 305 cl++; 306 p += 3; 307 break; 308 } 309 } 310 311 free(buffer); 312 if (ret & FSFATAL) { 313 free(fat); 314 *fp = NULL; 315 } else 316 *fp = fat; 317 return ret; 318 } 319 320 /* 321 * Get type of reserved cluster 322 */ 323 const char * 324 rsrvdcltype(cl_t cl) 325 { 326 if (cl == CLUST_FREE) 327 return "free"; 328 if (cl < CLUST_BAD) 329 return "reserved"; 330 if (cl > CLUST_BAD) 331 return "as EOF"; 332 return "bad"; 333 } 334 335 static int 336 clustdiffer(cl_t cl, cl_t *cp1, cl_t *cp2, u_int fatnum) 337 { 338 if (*cp1 == CLUST_FREE || *cp1 >= CLUST_RSRVD) { 339 if (*cp2 == CLUST_FREE || *cp2 >= CLUST_RSRVD) { 340 if ((*cp1 != CLUST_FREE && *cp1 < CLUST_BAD 341 && *cp2 != CLUST_FREE && *cp2 < CLUST_BAD) 342 || (*cp1 > CLUST_BAD && *cp2 > CLUST_BAD)) { 343 pwarn("Cluster %u is marked %s with different indicators\n", 344 cl, rsrvdcltype(*cp1)); 345 if (ask(1, "Fix")) { 346 *cp2 = *cp1; 347 return FSFATMOD; 348 } 349 return FSFATAL; 350 } 351 pwarn("Cluster %u is marked %s in FAT 0, %s in FAT %u\n", 352 cl, rsrvdcltype(*cp1), rsrvdcltype(*cp2), fatnum); 353 if (ask(0, "Use FAT 0's entry")) { 354 *cp2 = *cp1; 355 return FSFATMOD; 356 } 357 if (ask(0, "Use FAT %u's entry", fatnum)) { 358 *cp1 = *cp2; 359 return FSFATMOD; 360 } 361 return FSFATAL; 362 } 363 pwarn("Cluster %u is marked %s in FAT 0, but continues with cluster %u in FAT %d\n", 364 cl, rsrvdcltype(*cp1), *cp2, fatnum); 365 if (ask(0, "Use continuation from FAT %u", fatnum)) { 366 *cp1 = *cp2; 367 return FSFATMOD; 368 } 369 if (ask(0, "Use mark from FAT 0")) { 370 *cp2 = *cp1; 371 return FSFATMOD; 372 } 373 return FSFATAL; 374 } 375 if (*cp2 == CLUST_FREE || *cp2 >= CLUST_RSRVD) { 376 pwarn("Cluster %u continues with cluster %u in FAT 0, but is marked %s in FAT %u\n", 377 cl, *cp1, rsrvdcltype(*cp2), fatnum); 378 if (ask(0, "Use continuation from FAT 0")) { 379 *cp2 = *cp1; 380 return FSFATMOD; 381 } 382 if (ask(0, "Use mark from FAT %d", fatnum)) { 383 *cp1 = *cp2; 384 return FSFATMOD; 385 } 386 return FSERROR; 387 } 388 pwarn("Cluster %u continues with cluster %u in FAT 0, but with cluster %u in FAT %u\n", 389 cl, *cp1, *cp2, fatnum); 390 if (ask(0, "Use continuation from FAT 0")) { 391 *cp2 = *cp1; 392 return FSFATMOD; 393 } 394 if (ask(0, "Use continuation from FAT %u", fatnum)) { 395 *cp1 = *cp2; 396 return FSFATMOD; 397 } 398 return FSERROR; 399 } 400 401 /* 402 * Compare two FAT copies in memory. Resolve any conflicts and merge them 403 * into the first one. 404 */ 405 int 406 comparefat(struct bootblock *boot, struct fatEntry *first, 407 struct fatEntry *second, u_int fatnum) 408 { 409 cl_t cl; 410 int ret = FSOK; 411 412 for (cl = CLUST_FIRST; cl < boot->NumClusters; cl++) 413 if (first[cl].next != second[cl].next) 414 ret |= clustdiffer(cl, &first[cl].next, &second[cl].next, fatnum); 415 return ret; 416 } 417 418 void 419 clearchain(struct bootblock *boot, struct fatEntry *fat, cl_t head) 420 { 421 cl_t p, q; 422 423 for (p = head; p >= CLUST_FIRST && p < boot->NumClusters; p = q) { 424 if (fat[p].head != head) 425 break; 426 q = fat[p].next; 427 fat[p].next = fat[p].head = CLUST_FREE; 428 fat[p].length = 0; 429 } 430 } 431 432 int 433 tryclear(struct bootblock *boot, struct fatEntry *fat, cl_t head, cl_t *truncp) 434 { 435 if (ask(0, "Clear chain starting at %u", head)) { 436 clearchain(boot, fat, head); 437 return FSFATMOD; 438 } else if (ask(0, "Truncate")) { 439 *truncp = CLUST_EOF; 440 return FSFATMOD; 441 } else 442 return FSERROR; 443 } 444 445 /* 446 * Check a complete FAT in-memory for crosslinks 447 */ 448 int 449 checkfat(struct bootblock *boot, struct fatEntry *fat) 450 { 451 cl_t head, p, h, n; 452 u_int len; 453 int ret = 0; 454 int conf; 455 456 /* 457 * pass 1: figure out the cluster chains. 458 */ 459 for (head = CLUST_FIRST; head < boot->NumClusters; head++) { 460 /* find next untravelled chain */ 461 if (fat[head].head != 0 /* cluster already belongs to some chain */ 462 || fat[head].next == CLUST_FREE 463 || fat[head].next == CLUST_BAD) 464 continue; /* skip it. */ 465 466 /* follow the chain and mark all clusters on the way */ 467 for (len = 0, p = head; 468 p >= CLUST_FIRST && p < boot->NumClusters; 469 p = fat[p].next) { 470 fat[p].head = head; 471 len++; 472 } 473 474 /* the head record gets the length */ 475 fat[head].length = fat[head].next == CLUST_FREE ? 0 : len; 476 } 477 478 /* 479 * pass 2: check for crosslinked chains (we couldn't do this in pass 1 because 480 * we didn't know the real start of the chain then - would have treated partial 481 * chains as interlinked with their main chain) 482 */ 483 for (head = CLUST_FIRST; head < boot->NumClusters; head++) { 484 /* find next untravelled chain */ 485 if (fat[head].head != head) 486 continue; 487 488 /* follow the chain to its end (hopefully) */ 489 for (p = head; 490 (n = fat[p].next) >= CLUST_FIRST && n < boot->NumClusters; 491 p = n) 492 if (fat[n].head != head) 493 break; 494 if (n >= CLUST_EOFS) 495 continue; 496 497 if (n == CLUST_FREE || n >= CLUST_RSRVD) { 498 pwarn("Cluster chain starting at %u ends with cluster marked %s\n", 499 head, rsrvdcltype(n)); 500 ret |= tryclear(boot, fat, head, &fat[p].next); 501 continue; 502 } 503 if (n < CLUST_FIRST || n >= boot->NumClusters) { 504 pwarn("Cluster chain starting at %u ends with cluster out of range (%u)\n", 505 head, n); 506 ret |= tryclear(boot, fat, head, &fat[p].next); 507 continue; 508 } 509 pwarn("Cluster chains starting at %u and %u are linked at cluster %u\n", 510 head, fat[n].head, n); 511 conf = tryclear(boot, fat, head, &fat[p].next); 512 if (ask(0, "Clear chain starting at %u", h = fat[n].head)) { 513 if (conf == FSERROR) { 514 /* 515 * Transfer the common chain to the one not cleared above. 516 */ 517 for (p = n; 518 p >= CLUST_FIRST && p < boot->NumClusters; 519 p = fat[p].next) { 520 if (h != fat[p].head) { 521 /* 522 * Have to reexamine this chain. 523 */ 524 head--; 525 break; 526 } 527 fat[p].head = head; 528 } 529 } 530 clearchain(boot, fat, h); 531 conf |= FSFATMOD; 532 } 533 ret |= conf; 534 } 535 536 return ret; 537 } 538 539 /* 540 * Write out FATs encoding them from the internal format 541 */ 542 int 543 writefat(int fs, struct bootblock *boot, struct fatEntry *fat, int correct_fat) 544 { 545 u_char *buffer, *p; 546 cl_t cl; 547 u_int i; 548 size_t fatsz; 549 off_t off; 550 int ret = FSOK; 551 552 buffer = malloc(fatsz = boot->FATsecs * boot->bpbBytesPerSec); 553 if (buffer == NULL) { 554 perr("No space for FAT sectors (%zu)", fatsz); 555 return FSFATAL; 556 } 557 memset(buffer, 0, fatsz); 558 boot->NumFree = 0; 559 p = buffer; 560 if (correct_fat) { 561 *p++ = (u_char)boot->bpbMedia; 562 *p++ = 0xff; 563 *p++ = 0xff; 564 switch (boot->ClustMask) { 565 case CLUST16_MASK: 566 *p++ = 0xff; 567 break; 568 case CLUST32_MASK: 569 *p++ = 0x0f; 570 *p++ = 0xff; 571 *p++ = 0xff; 572 *p++ = 0xff; 573 *p++ = 0x0f; 574 break; 575 } 576 } else { 577 /* use same FAT signature as the old FAT has */ 578 int count; 579 u_char *old_fat; 580 581 switch (boot->ClustMask) { 582 case CLUST32_MASK: 583 count = 8; 584 break; 585 case CLUST16_MASK: 586 count = 4; 587 break; 588 default: 589 count = 3; 590 break; 591 } 592 593 if (!_readfat(fs, boot, boot->ValidFat >= 0 ? boot->ValidFat :0, 594 &old_fat)) { 595 free(buffer); 596 return FSFATAL; 597 } 598 599 memcpy(p, old_fat, count); 600 free(old_fat); 601 p += count; 602 } 603 604 for (cl = CLUST_FIRST; cl < boot->NumClusters; cl++) { 605 switch (boot->ClustMask) { 606 case CLUST32_MASK: 607 if (fat[cl].next == CLUST_FREE) 608 boot->NumFree++; 609 *p++ = (u_char)fat[cl].next; 610 *p++ = (u_char)(fat[cl].next >> 8); 611 *p++ = (u_char)(fat[cl].next >> 16); 612 *p &= 0xf0; 613 *p++ |= (fat[cl].next >> 24)&0x0f; 614 break; 615 case CLUST16_MASK: 616 if (fat[cl].next == CLUST_FREE) 617 boot->NumFree++; 618 *p++ = (u_char)fat[cl].next; 619 *p++ = (u_char)(fat[cl].next >> 8); 620 break; 621 default: 622 if (fat[cl].next == CLUST_FREE) 623 boot->NumFree++; 624 if (cl + 1 < boot->NumClusters 625 && fat[cl + 1].next == CLUST_FREE) 626 boot->NumFree++; 627 *p++ = (u_char)fat[cl].next; 628 *p++ = (u_char)((fat[cl].next >> 8) & 0xf) 629 |(u_char)(fat[cl+1].next << 4); 630 *p++ = (u_char)(fat[++cl].next >> 4); 631 break; 632 } 633 } 634 for (i = 0; i < boot->bpbFATs; i++) { 635 off = boot->bpbResSectors + i * boot->FATsecs; 636 off *= boot->bpbBytesPerSec; 637 if (lseek(fs, off, SEEK_SET) != off 638 || (size_t)write(fs, buffer, fatsz) != fatsz) { 639 perr("Unable to write FAT"); 640 ret = FSFATAL; /* Return immediately? XXX */ 641 } 642 } 643 free(buffer); 644 return ret; 645 } 646 647 /* 648 * Check a complete in-memory FAT for lost cluster chains 649 */ 650 int 651 checklost(int dosfs, struct bootblock *boot, struct fatEntry *fat) 652 { 653 cl_t head; 654 int mod = FSOK; 655 int ret; 656 657 for (head = CLUST_FIRST; head < boot->NumClusters; head++) { 658 /* find next untravelled chain */ 659 if (fat[head].head != head 660 || fat[head].next == CLUST_FREE 661 || (fat[head].next >= CLUST_RSRVD 662 && fat[head].next < CLUST_EOFS) 663 || (fat[head].flags & FAT_USED)) 664 continue; 665 666 pwarn("Lost cluster chain at cluster %u\n%d Cluster(s) lost\n", 667 head, fat[head].length); 668 mod |= ret = reconnect(dosfs, boot, fat, head); 669 if (mod & FSFATAL) 670 break; 671 if (ret == FSERROR && ask(0, "Clear")) { 672 clearchain(boot, fat, head); 673 mod |= FSFATMOD; 674 } 675 } 676 finishlf(); 677 678 if (boot->bpbFSInfo) { 679 ret = 0; 680 if (boot->FSFree != boot->NumFree) { 681 pwarn("Free space in FSInfo block (%d) not correct (%d)\n", 682 boot->FSFree, boot->NumFree); 683 if (ask(1, "Fix")) { 684 boot->FSFree = boot->NumFree; 685 ret = 1; 686 } 687 } 688 if (ret) 689 mod |= writefsinfo(dosfs, boot); 690 } 691 692 return mod; 693 } 694