1 /* $NetBSD: fat.c,v 1.9 1998/01/22 18:48:44 ws Exp $ */ 2 3 /* 4 * Copyright (C) 1995, 1996, 1997 Wolfgang Solfrank 5 * Copyright (c) 1995 Martin Husemann 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 1. Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 3. All advertising materials mentioning features or use of this software 16 * must display the following acknowledgement: 17 * This product includes software developed by Martin Husemann 18 * and Wolfgang Solfrank. 19 * 4. Neither the name of the University nor the names of its contributors 20 * may be used to endorse or promote products derived from this software 21 * without specific prior written permission. 22 * 23 * THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND ANY EXPRESS OR 24 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 25 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 26 * IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY DIRECT, INDIRECT, 27 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 28 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 29 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 30 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 31 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 32 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 33 */ 34 35 36 #include <sys/cdefs.h> 37 #ifndef lint 38 __RCSID("$NetBSD: fat.c,v 1.9 1998/01/22 18:48:44 ws 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 #include "fsutil.h" 49 50 static int checkclnum __P((struct bootblock *, int, cl_t, cl_t *)); 51 static int clustdiffer __P((cl_t, cl_t *, cl_t *, int)); 52 static int tryclear __P((struct bootblock *, struct fatEntry *, cl_t, cl_t *)); 53 54 /* 55 * Check a cluster number for valid value 56 */ 57 static int 58 checkclnum(boot, fat, cl, next) 59 struct bootblock *boot; 60 int fat; 61 cl_t cl; 62 cl_t *next; 63 { 64 if (*next >= (CLUST_RSRVD&boot->ClustMask)) 65 *next |= ~boot->ClustMask; 66 if (*next == CLUST_FREE) { 67 boot->NumFree++; 68 return FSOK; 69 } 70 if (*next == CLUST_BAD) { 71 boot->NumBad++; 72 return FSOK; 73 } 74 if (*next < CLUST_FIRST 75 || (*next >= boot->NumClusters && *next < CLUST_EOFS)) { 76 pwarn("Cluster %u in FAT %d continues with %s cluster number %u\n", 77 cl, fat, 78 *next < CLUST_RSRVD ? "out of range" : "reserved", 79 *next&boot->ClustMask); 80 if (ask(0, "Truncate")) { 81 *next = CLUST_EOF; 82 return FSFATMOD; 83 } 84 return FSERROR; 85 } 86 return FSOK; 87 } 88 89 /* 90 * Read a FAT and decode it into internal format 91 */ 92 int 93 readfat(fs, boot, no, fp) 94 int fs; 95 struct bootblock *boot; 96 int no; 97 struct fatEntry **fp; 98 { 99 struct fatEntry *fat; 100 u_char *buffer, *p; 101 cl_t cl; 102 off_t off; 103 int ret = FSOK; 104 105 boot->NumFree = boot->NumBad = 0; 106 fat = malloc(sizeof(struct fatEntry) * boot->NumClusters); 107 buffer = malloc(boot->FATsecs * boot->BytesPerSec); 108 if (fat == NULL || buffer == NULL) { 109 perror("No space for FAT"); 110 if (fat) 111 free(fat); 112 return FSFATAL; 113 } 114 115 memset(fat, 0, sizeof(struct fatEntry) * boot->NumClusters); 116 117 off = boot->ResSectors + no * boot->FATsecs; 118 off *= boot->BytesPerSec; 119 120 if (lseek(fs, off, SEEK_SET) != off) { 121 perror("Unable to read FAT"); 122 free(buffer); 123 free(fat); 124 return FSFATAL; 125 } 126 127 if (read(fs, buffer, boot->FATsecs * boot->BytesPerSec) 128 != boot->FATsecs * boot->BytesPerSec) { 129 perror("Unable to read FAT"); 130 free(buffer); 131 free(fat); 132 return FSFATAL; 133 } 134 135 if (buffer[0] != boot->Media 136 || buffer[1] != 0xff || buffer[2] != 0xff 137 || (boot->ClustMask == CLUST16_MASK && buffer[3] != 0xff) 138 || (boot->ClustMask == CLUST32_MASK 139 && ((buffer[3]&0x0f) != 0x0f 140 || buffer[4] != 0xff || buffer[5] != 0xff 141 || buffer[6] != 0xff || (buffer[7]&0x0f) != 0x0f))) { 142 char *msg; 143 144 switch (boot->ClustMask) { 145 case CLUST32_MASK: 146 msg = "FAT starts with odd byte sequence (%02x%02x%02x%02x%02x%02x%02x%02x)\n"; 147 break; 148 case CLUST16_MASK: 149 msg = "FAT starts with odd byte sequence (%02x%02x%02x%02x)\n"; 150 break; 151 default: 152 msg = "FAT starts with odd byte sequence (%02x%02x%02x)\n"; 153 break; 154 } 155 pwarn(msg, 156 buffer[0], buffer[1], buffer[2], buffer[3], 157 buffer[4], buffer[5], buffer[6], buffer[7]); 158 if (ask(1, "Correct")) 159 ret |= FSFATMOD; 160 } 161 switch (boot->ClustMask) { 162 case CLUST32_MASK: 163 p = buffer + 8; 164 break; 165 case CLUST16_MASK: 166 p = buffer + 4; 167 break; 168 default: 169 p = buffer + 3; 170 break; 171 } 172 for (cl = CLUST_FIRST; cl < boot->NumClusters;) { 173 switch (boot->ClustMask) { 174 case CLUST32_MASK: 175 fat[cl].next = p[0] + (p[1] << 8) 176 + (p[2] << 16) + (p[3] << 24); 177 fat[cl].next &= boot->ClustMask; 178 ret |= checkclnum(boot, no, cl, &fat[cl].next); 179 cl++; 180 p += 4; 181 break; 182 case CLUST16_MASK: 183 fat[cl].next = p[0] + (p[1] << 8); 184 ret |= checkclnum(boot, no, cl, &fat[cl].next); 185 cl++; 186 p += 2; 187 break; 188 default: 189 fat[cl].next = (p[0] + (p[1] << 8)) & 0x0fff; 190 ret |= checkclnum(boot, no, cl, &fat[cl].next); 191 cl++; 192 if (cl >= boot->NumClusters) 193 break; 194 fat[cl].next = ((p[1] >> 4) + (p[2] << 4)) & 0x0fff; 195 ret |= checkclnum(boot, no, cl, &fat[cl].next); 196 cl++; 197 p += 3; 198 break; 199 } 200 } 201 202 free(buffer); 203 *fp = fat; 204 return ret; 205 } 206 207 /* 208 * Get type of reserved cluster 209 */ 210 char * 211 rsrvdcltype(cl) 212 cl_t cl; 213 { 214 if (cl == CLUST_FREE) 215 return "free"; 216 if (cl < CLUST_BAD) 217 return "reserved"; 218 if (cl > CLUST_BAD) 219 return "as EOF"; 220 return "bad"; 221 } 222 223 static int 224 clustdiffer(cl, cp1, cp2, fatnum) 225 cl_t cl; 226 cl_t *cp1; 227 cl_t *cp2; 228 int fatnum; 229 { 230 if (*cp1 == CLUST_FREE || *cp1 >= CLUST_RSRVD) { 231 if (*cp2 == CLUST_FREE || *cp2 >= CLUST_RSRVD) { 232 if ((*cp1 != CLUST_FREE && *cp1 < CLUST_BAD 233 && *cp2 != CLUST_FREE && *cp2 < CLUST_BAD) 234 || (*cp1 > CLUST_BAD && *cp2 > CLUST_BAD)) { 235 pwarn("Cluster %u is marked %s with different indicators, ", 236 cl, rsrvdcltype(*cp1)); 237 if (ask(1, "fix")) { 238 *cp2 = *cp1; 239 return FSFATMOD; 240 } 241 return FSFATAL; 242 } 243 pwarn("Cluster %u is marked %s in FAT 0, %s in FAT %d\n", 244 cl, rsrvdcltype(*cp1), rsrvdcltype(*cp2), fatnum); 245 if (ask(0, "use FAT 0's entry")) { 246 *cp2 = *cp1; 247 return FSFATMOD; 248 } 249 if (ask(0, "use FAT %d's entry", fatnum)) { 250 *cp1 = *cp2; 251 return FSFATMOD; 252 } 253 return FSFATAL; 254 } 255 pwarn("Cluster %u is marked %s in FAT 0, but continues with cluster %u in FAT %d\n", 256 cl, rsrvdcltype(*cp1), *cp2, fatnum); 257 if (ask(0, "Use continuation from FAT %d", fatnum)) { 258 *cp1 = *cp2; 259 return FSFATMOD; 260 } 261 if (ask(0, "Use mark from FAT 0")) { 262 *cp2 = *cp1; 263 return FSFATMOD; 264 } 265 return FSFATAL; 266 } 267 if (*cp2 == CLUST_FREE || *cp2 >= CLUST_RSRVD) { 268 pwarn("Cluster %u continues with cluster %u in FAT 0, but is marked %s in FAT %d\n", 269 cl, *cp1, rsrvdcltype(*cp2), fatnum); 270 if (ask(0, "Use continuation from FAT 0")) { 271 *cp2 = *cp1; 272 return FSFATMOD; 273 } 274 if (ask(0, "Use mark from FAT %d", fatnum)) { 275 *cp1 = *cp2; 276 return FSFATMOD; 277 } 278 return FSERROR; 279 } 280 pwarn("Cluster %u continues with cluster %u in FAT 0, but with cluster %u in FAT %d\n", 281 cl, *cp1, *cp2, fatnum); 282 if (ask(0, "Use continuation from FAT 0")) { 283 *cp2 = *cp1; 284 return FSFATMOD; 285 } 286 if (ask(0, "Use continuation from FAT %d", fatnum)) { 287 *cp1 = *cp2; 288 return FSFATMOD; 289 } 290 return FSERROR; 291 } 292 293 /* 294 * Compare two FAT copies in memory. Resolve any conflicts and merge them 295 * into the first one. 296 */ 297 int 298 comparefat(boot, first, second, fatnum) 299 struct bootblock *boot; 300 struct fatEntry *first; 301 struct fatEntry *second; 302 int fatnum; 303 { 304 cl_t cl; 305 int ret = FSOK; 306 307 for (cl = CLUST_FIRST; cl < boot->NumClusters; cl++) 308 if (first[cl].next != second[cl].next) 309 ret |= clustdiffer(cl, &first[cl].next, &second[cl].next, fatnum); 310 return ret; 311 } 312 313 void 314 clearchain(boot, fat, head) 315 struct bootblock *boot; 316 struct fatEntry *fat; 317 cl_t head; 318 { 319 cl_t p, q; 320 321 for (p = head; p >= CLUST_FIRST && p < boot->NumClusters; p = q) { 322 if (fat[p].head != head) 323 break; 324 q = fat[p].next; 325 fat[p].next = fat[p].head = CLUST_FREE; 326 fat[p].length = 0; 327 } 328 } 329 330 int 331 tryclear(boot, fat, head, trunc) 332 struct bootblock *boot; 333 struct fatEntry *fat; 334 cl_t head; 335 cl_t *trunc; 336 { 337 if (ask(0, "Clear chain starting at %u", head)) { 338 clearchain(boot, fat, head); 339 return FSFATMOD; 340 } else if (ask(0, "Truncate")) { 341 *trunc = CLUST_EOF; 342 return FSFATMOD; 343 } else 344 return FSERROR; 345 } 346 347 /* 348 * Check a complete FAT in-memory for crosslinks 349 */ 350 int 351 checkfat(boot, fat) 352 struct bootblock *boot; 353 struct fatEntry *fat; 354 { 355 cl_t head, p, h, n; 356 u_int len; 357 int ret = 0; 358 int conf; 359 360 /* 361 * pass 1: figure out the cluster chains. 362 */ 363 for (head = CLUST_FIRST; head < boot->NumClusters; head++) { 364 /* find next untravelled chain */ 365 if (fat[head].head != 0 /* cluster already belongs to some chain */ 366 || fat[head].next == CLUST_FREE 367 || fat[head].next == CLUST_BAD) 368 continue; /* skip it. */ 369 370 /* follow the chain and mark all clusters on the way */ 371 for (len = 0, p = head; 372 p >= CLUST_FIRST && p < boot->NumClusters; 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 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