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