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