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