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