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