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