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