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