snj doesn't like my accent, so use proper English month names.
[netbsd-mini2440.git] / sbin / fsck_msdos / fat.c
blobe80917a13c782a133ae630490cb0c9a3a2d06ea3
1 /* $NetBSD: fat.c,v 1.21 2008/07/24 14:23:16 matthias Exp $ */
3 /*
4 * Copyright (C) 1995, 1996, 1997 Wolfgang Solfrank
5 * Copyright (c) 1995 Martin Husemann
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.
16 * THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND ANY EXPRESS OR
17 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
18 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
19 * IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY DIRECT, INDIRECT,
20 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
21 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
25 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 #include <sys/cdefs.h>
30 #ifndef lint
31 __RCSID("$NetBSD: fat.c,v 1.21 2008/07/24 14:23:16 matthias Exp $");
32 #endif /* not lint */
34 #include <stdlib.h>
35 #include <string.h>
36 #include <ctype.h>
37 #include <stdio.h>
38 #include <unistd.h>
40 #include "ext.h"
41 #include "fsutil.h"
43 static int checkclnum(struct bootblock *, u_int, cl_t, cl_t *);
44 static int clustdiffer(cl_t, cl_t *, cl_t *, u_int);
45 static int tryclear(struct bootblock *, struct fatEntry *, cl_t, cl_t *);
46 static int _readfat(int, struct bootblock *, u_int, u_char **);
49 * Check a cluster number for valid value
51 static int
52 checkclnum(struct bootblock *boot, u_int fat, cl_t cl, cl_t *next)
54 if (*next >= (CLUST_RSRVD&boot->ClustMask))
55 *next |= ~boot->ClustMask;
56 if (*next == CLUST_FREE) {
57 boot->NumFree++;
58 return FSOK;
60 if (*next == CLUST_BAD) {
61 boot->NumBad++;
62 return FSOK;
64 if (*next < CLUST_FIRST
65 || (*next >= boot->NumClusters && *next < CLUST_EOFS)) {
66 pwarn("Cluster %u in FAT %u 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;
74 return FSERROR;
76 return FSOK;
80 * Read a FAT from disk. Returns 1 if successful, 0 otherwise.
82 static int
83 _readfat(int fs, struct bootblock *boot, u_int no, u_char **buffer)
85 off_t off;
86 size_t len;
88 *buffer = malloc(len = boot->FATsecs * boot->BytesPerSec);
89 if (*buffer == NULL) {
90 perr("No space for FAT sectors (%zu)", len);
91 return 0;
94 off = boot->ResSectors + no * boot->FATsecs;
95 off *= boot->BytesPerSec;
97 if (lseek(fs, off, SEEK_SET) != off) {
98 perr("Unable to read FAT");
99 goto err;
102 if ((size_t)read(fs, *buffer, boot->FATsecs * boot->BytesPerSec)
103 != boot->FATsecs * boot->BytesPerSec) {
104 perr("Unable to read FAT");
105 goto err;
108 return 1;
110 err:
111 free(*buffer);
112 return 0;
116 * Read a FAT and decode it into internal format
119 readfat(int fs, struct bootblock *boot, u_int no, struct fatEntry **fp)
121 struct fatEntry *fat;
122 u_char *buffer, *p;
123 cl_t cl;
124 int ret = FSOK;
125 size_t len;
127 boot->NumFree = boot->NumBad = 0;
129 if (!_readfat(fs, boot, no, &buffer))
130 return FSFATAL;
132 fat = malloc(len = boot->NumClusters * sizeof(struct fatEntry));
133 if (fat == NULL) {
134 perr("No space for FAT clusters (%zu)", len);
135 free(buffer);
136 return FSFATAL;
138 (void)memset(fat, 0, len);
140 if (buffer[0] != boot->Media
141 || buffer[1] != 0xff || buffer[2] != 0xff
142 || (boot->ClustMask == CLUST16_MASK && buffer[3] != 0xff)
143 || (boot->ClustMask == CLUST32_MASK
144 && ((buffer[3]&0x0f) != 0x0f
145 || buffer[4] != 0xff || buffer[5] != 0xff
146 || buffer[6] != 0xff || (buffer[7]&0x0f) != 0x0f))) {
148 /* Windows 95 OSR2 (and possibly any later) changes
149 * the FAT signature to 0xXXffff7f for FAT16 and to
150 * 0xXXffff0fffffff07 for FAT32 upon boot, to know that the
151 * filesystem is dirty if it doesn't reboot cleanly.
152 * Check this special condition before errorring out.
154 if (buffer[0] == boot->Media && buffer[1] == 0xff
155 && buffer[2] == 0xff
156 && ((boot->ClustMask == CLUST16_MASK && buffer[3] == 0x7f)
157 || (boot->ClustMask == CLUST32_MASK
158 && buffer[3] == 0x0f && buffer[4] == 0xff
159 && buffer[5] == 0xff && buffer[6] == 0xff
160 && buffer[7] == 0x07)))
161 ret |= FSDIRTY;
162 else {
163 /* just some odd byte sequence in FAT */
165 switch (boot->ClustMask) {
166 case CLUST32_MASK:
167 pwarn("%s (%02x%02x%02x%02x%02x%02x%02x%02x)\n",
168 "FAT starts with odd byte sequence",
169 buffer[0], buffer[1], buffer[2], buffer[3],
170 buffer[4], buffer[5], buffer[6], buffer[7]);
171 break;
172 case CLUST16_MASK:
173 pwarn("%s (%02x%02x%02x%02x)\n",
174 "FAT starts with odd byte sequence",
175 buffer[0], buffer[1], buffer[2], buffer[3]);
176 break;
177 default:
178 pwarn("%s (%02x%02x%02x)\n",
179 "FAT starts with odd byte sequence",
180 buffer[0], buffer[1], buffer[2]);
181 break;
185 if (ask(1, "Correct"))
186 ret |= FSFIXFAT;
189 switch (boot->ClustMask) {
190 case CLUST32_MASK:
191 p = buffer + 8;
192 break;
193 case CLUST16_MASK:
194 p = buffer + 4;
195 break;
196 default:
197 p = buffer + 3;
198 break;
200 for (cl = CLUST_FIRST; cl < boot->NumClusters;) {
201 switch (boot->ClustMask) {
202 case CLUST32_MASK:
203 fat[cl].next = p[0] + (p[1] << 8)
204 + (p[2] << 16) + (p[3] << 24);
205 fat[cl].next &= boot->ClustMask;
206 ret |= checkclnum(boot, no, cl, &fat[cl].next);
207 cl++;
208 p += 4;
209 break;
210 case CLUST16_MASK:
211 fat[cl].next = p[0] + (p[1] << 8);
212 ret |= checkclnum(boot, no, cl, &fat[cl].next);
213 cl++;
214 p += 2;
215 break;
216 default:
217 fat[cl].next = (p[0] + (p[1] << 8)) & 0x0fff;
218 ret |= checkclnum(boot, no, cl, &fat[cl].next);
219 cl++;
220 if (cl >= boot->NumClusters)
221 break;
222 fat[cl].next = ((p[1] >> 4) + (p[2] << 4)) & 0x0fff;
223 ret |= checkclnum(boot, no, cl, &fat[cl].next);
224 cl++;
225 p += 3;
226 break;
230 free(buffer);
231 if (ret & FSFATAL) {
232 free(fat);
233 *fp = NULL;
234 } else
235 *fp = fat;
236 return ret;
240 * Get type of reserved cluster
242 const char *
243 rsrvdcltype(cl_t cl)
245 if (cl == CLUST_FREE)
246 return "free";
247 if (cl < CLUST_BAD)
248 return "reserved";
249 if (cl > CLUST_BAD)
250 return "as EOF";
251 return "bad";
254 static int
255 clustdiffer(cl_t cl, cl_t *cp1, cl_t *cp2, u_int fatnum)
257 if (*cp1 == CLUST_FREE || *cp1 >= CLUST_RSRVD) {
258 if (*cp2 == CLUST_FREE || *cp2 >= CLUST_RSRVD) {
259 if ((*cp1 != CLUST_FREE && *cp1 < CLUST_BAD
260 && *cp2 != CLUST_FREE && *cp2 < CLUST_BAD)
261 || (*cp1 > CLUST_BAD && *cp2 > CLUST_BAD)) {
262 pwarn("Cluster %u is marked %s with different indicators, ",
263 cl, rsrvdcltype(*cp1));
264 if (ask(1, "fix")) {
265 *cp2 = *cp1;
266 return FSFATMOD;
268 return FSFATAL;
270 pwarn("Cluster %u is marked %s in FAT 0, %s in FAT %u\n",
271 cl, rsrvdcltype(*cp1), rsrvdcltype(*cp2), fatnum);
272 if (ask(0, "use FAT 0's entry")) {
273 *cp2 = *cp1;
274 return FSFATMOD;
276 if (ask(0, "use FAT %u's entry", fatnum)) {
277 *cp1 = *cp2;
278 return FSFATMOD;
280 return FSFATAL;
282 pwarn("Cluster %u is marked %s in FAT 0, but continues with cluster %u in FAT %u\n",
283 cl, rsrvdcltype(*cp1), *cp2, fatnum);
284 if (ask(0, "Use continuation from FAT %u", fatnum)) {
285 *cp1 = *cp2;
286 return FSFATMOD;
288 if (ask(0, "Use mark from FAT 0")) {
289 *cp2 = *cp1;
290 return FSFATMOD;
292 return FSFATAL;
294 if (*cp2 == CLUST_FREE || *cp2 >= CLUST_RSRVD) {
295 pwarn("Cluster %u continues with cluster %u in FAT 0, but is marked %s in FAT %u\n",
296 cl, *cp1, rsrvdcltype(*cp2), fatnum);
297 if (ask(0, "Use continuation from FAT 0")) {
298 *cp2 = *cp1;
299 return FSFATMOD;
301 if (ask(0, "Use mark from FAT %u", fatnum)) {
302 *cp1 = *cp2;
303 return FSFATMOD;
305 return FSERROR;
307 pwarn("Cluster %u continues with cluster %u in FAT 0, but with cluster %u in FAT %u\n",
308 cl, *cp1, *cp2, fatnum);
309 if (ask(0, "Use continuation from FAT 0")) {
310 *cp2 = *cp1;
311 return FSFATMOD;
313 if (ask(0, "Use continuation from FAT %u", fatnum)) {
314 *cp1 = *cp2;
315 return FSFATMOD;
317 return FSERROR;
321 * Compare two FAT copies in memory. Resolve any conflicts and merge them
322 * into the first one.
325 comparefat(struct bootblock *boot, struct fatEntry *first,
326 struct fatEntry *second, u_int fatnum)
328 cl_t cl;
329 int ret = FSOK;
331 for (cl = CLUST_FIRST; cl < boot->NumClusters; cl++)
332 if (first[cl].next != second[cl].next)
333 ret |= clustdiffer(cl, &first[cl].next, &second[cl].next, fatnum);
334 return ret;
337 void
338 clearchain(struct bootblock *boot, struct fatEntry *fat, cl_t head)
340 cl_t p, q;
342 for (p = head; p >= CLUST_FIRST && p < boot->NumClusters; p = q) {
343 if (fat[p].head != head)
344 break;
345 q = fat[p].next;
346 fat[p].next = fat[p].head = CLUST_FREE;
347 fat[p].length = 0;
352 tryclear(struct bootblock *boot, struct fatEntry *fat, cl_t head, cl_t *truncp)
354 if (ask(0, "Clear chain starting at %u", head)) {
355 clearchain(boot, fat, head);
356 return FSFATMOD;
357 } else if (ask(0, "Truncate")) {
358 *truncp = CLUST_EOF;
359 return FSFATMOD;
360 } else
361 return FSERROR;
365 * Check a complete FAT in-memory for crosslinks
368 checkfat(struct bootblock *boot, struct fatEntry *fat)
370 cl_t head, p, h, n;
371 u_int len;
372 int ret = 0;
373 int conf;
376 * pass 1: figure out the cluster chains.
378 for (head = CLUST_FIRST; head < boot->NumClusters; head++) {
379 /* find next untravelled chain */
380 if (fat[head].head != 0 /* cluster already belongs to some chain */
381 || fat[head].next == CLUST_FREE
382 || fat[head].next == CLUST_BAD)
383 continue; /* skip it. */
385 /* follow the chain and mark all clusters on the way */
386 for (len = 0, p = head;
387 p >= CLUST_FIRST && p < boot->NumClusters;
388 p = fat[p].next) {
389 fat[p].head = head;
390 len++;
393 /* the head record gets the length */
394 fat[head].length = fat[head].next == CLUST_FREE ? 0 : len;
398 * pass 2: check for crosslinked chains (we couldn't do this in pass 1 because
399 * we didn't know the real start of the chain then - would have treated partial
400 * chains as interlinked with their main chain)
402 for (head = CLUST_FIRST; head < boot->NumClusters; head++) {
403 /* find next untravelled chain */
404 if (fat[head].head != head)
405 continue;
407 /* follow the chain to its end (hopefully) */
408 for (p = head;
409 (n = fat[p].next) >= CLUST_FIRST && n < boot->NumClusters;
410 p = n)
411 if (fat[n].head != head)
412 break;
413 if (n >= CLUST_EOFS)
414 continue;
416 if (n == CLUST_FREE || n >= CLUST_RSRVD) {
417 pwarn("Cluster chain starting at %u ends with cluster marked %s\n",
418 head, rsrvdcltype(n));
419 ret |= tryclear(boot, fat, head, &fat[p].next);
420 continue;
422 if (n < CLUST_FIRST || n >= boot->NumClusters) {
423 pwarn("Cluster chain starting at %u ends with cluster out of range (%u)\n",
424 head, n);
425 ret |= tryclear(boot, fat, head, &fat[p].next);
426 continue;
428 pwarn("Cluster chains starting at %u and %u are linked at cluster %u\n",
429 head, fat[n].head, n);
430 conf = tryclear(boot, fat, head, &fat[p].next);
431 if (ask(0, "Clear chain starting at %u", h = fat[n].head)) {
432 if (conf == FSERROR) {
434 * Transfer the common chain to the one not cleared above.
436 for (p = n;
437 p >= CLUST_FIRST && p < boot->NumClusters;
438 p = fat[p].next) {
439 if (h != fat[p].head) {
441 * Have to reexamine this chain.
443 head--;
444 break;
446 fat[p].head = head;
449 clearchain(boot, fat, h);
450 conf |= FSFATMOD;
452 ret |= conf;
455 return ret;
459 * Write out FATs encoding them from the internal format
462 writefat(int fs, struct bootblock *boot, struct fatEntry *fat, int correct_fat)
464 u_char *buffer, *p;
465 cl_t cl;
466 u_int i;
467 size_t fatsz;
468 off_t off;
469 int ret = FSOK;
471 buffer = malloc(fatsz = boot->FATsecs * boot->BytesPerSec);
472 if (buffer == NULL) {
473 perr("No space for FAT sectors (%zu)", fatsz);
474 return FSFATAL;
476 memset(buffer, 0, fatsz);
477 boot->NumFree = 0;
478 p = buffer;
479 if (correct_fat) {
480 *p++ = (u_char)boot->Media;
481 *p++ = 0xff;
482 *p++ = 0xff;
483 switch (boot->ClustMask) {
484 case CLUST16_MASK:
485 *p++ = 0xff;
486 break;
487 case CLUST32_MASK:
488 *p++ = 0x0f;
489 *p++ = 0xff;
490 *p++ = 0xff;
491 *p++ = 0xff;
492 *p++ = 0x0f;
493 break;
495 } else {
496 /* use same FAT signature as the old FAT has */
497 int count;
498 u_char *old_fat;
500 switch (boot->ClustMask) {
501 case CLUST32_MASK:
502 count = 8;
503 break;
504 case CLUST16_MASK:
505 count = 4;
506 break;
507 default:
508 count = 3;
509 break;
512 if (!_readfat(fs, boot, boot->ValidFat >= 0 ? boot->ValidFat :0,
513 &old_fat)) {
514 free(buffer);
515 return FSFATAL;
518 memcpy(p, old_fat, count);
519 free(old_fat);
520 p += count;
523 for (cl = CLUST_FIRST; cl < boot->NumClusters; cl++) {
524 switch (boot->ClustMask) {
525 case CLUST32_MASK:
526 if (fat[cl].next == CLUST_FREE)
527 boot->NumFree++;
528 *p++ = (u_char)fat[cl].next;
529 *p++ = (u_char)(fat[cl].next >> 8);
530 *p++ = (u_char)(fat[cl].next >> 16);
531 *p &= 0xf0;
532 *p++ |= (fat[cl].next >> 24)&0x0f;
533 break;
534 case CLUST16_MASK:
535 if (fat[cl].next == CLUST_FREE)
536 boot->NumFree++;
537 *p++ = (u_char)fat[cl].next;
538 *p++ = (u_char)(fat[cl].next >> 8);
539 break;
540 default:
541 if (fat[cl].next == CLUST_FREE)
542 boot->NumFree++;
543 if (cl + 1 < boot->NumClusters
544 && fat[cl + 1].next == CLUST_FREE)
545 boot->NumFree++;
546 *p++ = (u_char)fat[cl].next;
547 *p++ = (u_char)((fat[cl].next >> 8) & 0xf)
548 |(u_char)(fat[cl+1].next << 4);
549 *p++ = (u_char)(fat[++cl].next >> 4);
550 break;
553 for (i = 0; i < boot->FATs; i++) {
554 off = boot->ResSectors + i * boot->FATsecs;
555 off *= boot->BytesPerSec;
556 if (lseek(fs, off, SEEK_SET) != off
557 || (size_t)write(fs, buffer, fatsz) != fatsz) {
558 perr("Unable to write FAT");
559 ret = FSFATAL; /* Return immediately? XXX */
562 free(buffer);
563 return ret;
567 * Check a complete in-memory FAT for lost cluster chains
570 checklost(int dosfs, struct bootblock *boot, struct fatEntry *fat)
572 cl_t head;
573 int mod = FSOK;
574 int ret;
576 for (head = CLUST_FIRST; head < boot->NumClusters; head++) {
577 /* find next untravelled chain */
578 if (fat[head].head != head
579 || fat[head].next == CLUST_FREE
580 || (fat[head].next >= CLUST_RSRVD
581 && fat[head].next < CLUST_EOFS)
582 || (fat[head].flags & FAT_USED))
583 continue;
585 pwarn("Lost cluster chain at cluster %u\n%d Cluster(s) lost\n",
586 head, fat[head].length);
587 mod |= ret = reconnect(dosfs, boot, fat, head);
588 if (mod & FSFATAL)
589 break;
590 if (ret == FSERROR && ask(0, "Clear")) {
591 clearchain(boot, fat, head);
592 mod |= FSFATMOD;
595 finishlf();
597 if (boot->FSInfo) {
598 ret = 0;
599 if (boot->FSFree != boot->NumFree) {
600 pwarn("Free space in FSInfo block (%d) not correct (%d)\n",
601 boot->FSFree, boot->NumFree);
602 if (ask(1, "fix")) {
603 boot->FSFree = boot->NumFree;
604 ret = 1;
607 if (boot->FSNext >= boot->NumClusters || (boot->NumFree && fat[boot->FSNext].next != CLUST_FREE)) {
608 pwarn("Next free cluster in FSInfo block (%u) %s\n",
609 boot->FSNext,
610 (boot->FSNext >= boot->NumClusters) ? "invalid" : "not free");
611 if (ask(1, "fix"))
612 for (head = CLUST_FIRST; head < boot->NumClusters; head++)
613 if (fat[head].next == CLUST_FREE) {
614 boot->FSNext = head;
615 ret = 1;
616 break;
619 if (ret)
620 mod |= writefsinfo(dosfs, boot);
623 return mod;