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