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