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