Initial import from FreeBSD RELENG_4:
[dragonfly.git] / sbin / fsck_msdosfs / fat.c
1 /*
2  * Copyright (C) 1995, 1996, 1997 Wolfgang Solfrank
3  * Copyright (c) 1995 Martin Husemann
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  *    notice, this list of conditions and the following disclaimer in the
12  *    documentation and/or other materials provided with the distribution.
13  * 3. All advertising materials mentioning features or use of this software
14  *    must display the following acknowledgement:
15  *      This product includes software developed by Martin Husemann
16  *      and Wolfgang Solfrank.
17  * 4. Neither the name of the University nor the names of its contributors
18  *    may be used to endorse or promote products derived from this software
19  *    without specific prior written permission.
20  *
21  * THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND ANY EXPRESS OR
22  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
23  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
24  * IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY DIRECT, INDIRECT,
25  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
26  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
27  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
28  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
29  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
30  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31  */
32
33
34 #include <sys/cdefs.h>
35 #ifndef lint
36 __RCSID("$NetBSD: fat.c,v 1.12 2000/10/10 20:24:52 is Exp $");
37 static const char rcsid[] =
38   "$FreeBSD: src/sbin/fsck_msdosfs/fat.c,v 1.1.2.1 2001/08/01 05:47:56 obrien 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 static int _readfat __P((int, struct bootblock *, int, u_char **));
54
55 /*
56  * Check a cluster number for valid value
57  */
58 static int
59 checkclnum(boot, fat, cl, next)
60         struct bootblock *boot;
61         int fat;
62         cl_t cl;
63         cl_t *next;
64 {
65         if (*next >= (CLUST_RSRVD&boot->ClustMask))
66                 *next |= ~boot->ClustMask;
67         if (*next == CLUST_FREE) {
68                 boot->NumFree++;
69                 return FSOK;
70         }
71         if (*next == CLUST_BAD) {
72                 boot->NumBad++;
73                 return FSOK;
74         }
75         if (*next < CLUST_FIRST
76             || (*next >= boot->NumClusters && *next < CLUST_EOFS)) {
77                 pwarn("Cluster %u in FAT %d continues with %s cluster number %u\n",
78                       cl, fat,
79                       *next < CLUST_RSRVD ? "out of range" : "reserved",
80                       *next&boot->ClustMask);
81                 if (ask(0, "Truncate")) {
82                         *next = CLUST_EOF;
83                         return FSFATMOD;
84                 }
85                 return FSERROR;
86         }
87         return FSOK;
88 }
89
90 /*
91  * Read a FAT from disk. Returns 1 if successful, 0 otherwise.
92  */
93 static int
94 _readfat(fs, boot, no, buffer)
95         int fs;
96         struct bootblock *boot;
97         int no;
98         u_char **buffer;
99 {
100         off_t off;
101
102         *buffer = malloc(boot->FATsecs * boot->BytesPerSec);
103         if (*buffer == NULL) {
104                 perror("No space for FAT");
105                 return 0;
106         }
107
108         off = boot->ResSectors + no * boot->FATsecs;
109         off *= boot->BytesPerSec;
110
111         if (lseek(fs, off, SEEK_SET) != off) {
112                 perror("Unable to read FAT");
113                 goto err;
114         }
115
116         if (read(fs, *buffer, boot->FATsecs * boot->BytesPerSec)
117             != boot->FATsecs * boot->BytesPerSec) {
118                 perror("Unable to read FAT");
119                 goto err;
120         }
121
122         return 1;
123
124     err:
125         free(*buffer);
126         return 0;
127 }
128
129 /*
130  * Read a FAT and decode it into internal format
131  */
132 int
133 readfat(fs, boot, no, fp)
134         int fs;
135         struct bootblock *boot;
136         int no;
137         struct fatEntry **fp;
138 {
139         struct fatEntry *fat;
140         u_char *buffer, *p;
141         cl_t cl;
142         int ret = FSOK;
143
144         boot->NumFree = boot->NumBad = 0;
145
146         if (!_readfat(fs, boot, no, &buffer))
147                 return FSFATAL;
148                 
149         fat = calloc(boot->NumClusters, sizeof(struct fatEntry));
150         if (fat == NULL) {
151                 perror("No space for FAT");
152                 free(buffer);
153                 return FSFATAL;
154         }
155
156         if (buffer[0] != boot->Media
157             || buffer[1] != 0xff || buffer[2] != 0xff
158             || (boot->ClustMask == CLUST16_MASK && buffer[3] != 0xff)
159             || (boot->ClustMask == CLUST32_MASK
160                 && ((buffer[3]&0x0f) != 0x0f
161                     || buffer[4] != 0xff || buffer[5] != 0xff
162                     || buffer[6] != 0xff || (buffer[7]&0x0f) != 0x0f))) {
163
164                 /* Windows 95 OSR2 (and possibly any later) changes
165                  * the FAT signature to 0xXXffff7f for FAT16 and to
166                  * 0xXXffff0fffffff07 for FAT32 upon boot, to know that the
167                  * filesystem is dirty if it doesn't reboot cleanly.
168                  * Check this special condition before errorring out.
169                  */
170                 if (buffer[0] == boot->Media && buffer[1] == 0xff
171                     && buffer[2] == 0xff
172                     && ((boot->ClustMask == CLUST16_MASK && buffer[3] == 0x7f)
173                         || (boot->ClustMask == CLUST32_MASK
174                             && buffer[3] == 0x0f && buffer[4] == 0xff
175                             && buffer[5] == 0xff && buffer[6] == 0xff
176                             && buffer[7] == 0x07)))
177                         ret |= FSDIRTY;
178                 else {
179                         /* just some odd byte sequence in FAT */
180                                 
181                         switch (boot->ClustMask) {
182                         case CLUST32_MASK:
183                                 pwarn("%s (%02x%02x%02x%02x%02x%02x%02x%02x)\n",
184                                       "FAT starts with odd byte sequence",
185                                       buffer[0], buffer[1], buffer[2], buffer[3],
186                                       buffer[4], buffer[5], buffer[6], buffer[7]);
187                                 break;
188                         case CLUST16_MASK:
189                                 pwarn("%s (%02x%02x%02x%02x)\n",
190                                     "FAT starts with odd byte sequence",
191                                     buffer[0], buffer[1], buffer[2], buffer[3]);
192                                 break;
193                         default:
194                                 pwarn("%s (%02x%02x%02x)\n",
195                                     "FAT starts with odd byte sequence",
196                                     buffer[0], buffer[1], buffer[2]);
197                                 break;
198                         }
199
200         
201                         if (ask(1, "Correct"))
202                                 ret |= FSFIXFAT;
203                 }
204         }
205         switch (boot->ClustMask) {
206         case CLUST32_MASK:
207                 p = buffer + 8;
208                 break;
209         case CLUST16_MASK:
210                 p = buffer + 4;
211                 break;
212         default:
213                 p = buffer + 3;
214                 break;
215         }
216         for (cl = CLUST_FIRST; cl < boot->NumClusters;) {
217                 switch (boot->ClustMask) {
218                 case CLUST32_MASK:
219                         fat[cl].next = p[0] + (p[1] << 8)
220                                        + (p[2] << 16) + (p[3] << 24);
221                         fat[cl].next &= boot->ClustMask;
222                         ret |= checkclnum(boot, no, cl, &fat[cl].next);
223                         cl++;
224                         p += 4;
225                         break;
226                 case CLUST16_MASK:
227                         fat[cl].next = p[0] + (p[1] << 8);
228                         ret |= checkclnum(boot, no, cl, &fat[cl].next);
229                         cl++;
230                         p += 2;
231                         break;
232                 default:
233                         fat[cl].next = (p[0] + (p[1] << 8)) & 0x0fff;
234                         ret |= checkclnum(boot, no, cl, &fat[cl].next);
235                         cl++;
236                         if (cl >= boot->NumClusters)
237                                 break;
238                         fat[cl].next = ((p[1] >> 4) + (p[2] << 4)) & 0x0fff;
239                         ret |= checkclnum(boot, no, cl, &fat[cl].next);
240                         cl++;
241                         p += 3;
242                         break;
243                 }
244         }
245
246         free(buffer);
247         *fp = fat;
248         return ret;
249 }
250
251 /*
252  * Get type of reserved cluster
253  */
254 char *
255 rsrvdcltype(cl)
256         cl_t cl;
257 {
258         if (cl == CLUST_FREE)
259                 return "free";
260         if (cl < CLUST_BAD)
261                 return "reserved";
262         if (cl > CLUST_BAD)
263                 return "as EOF";
264         return "bad";
265 }
266
267 static int
268 clustdiffer(cl, cp1, cp2, fatnum)
269         cl_t cl;
270         cl_t *cp1;
271         cl_t *cp2;
272         int fatnum;
273 {
274         if (*cp1 == CLUST_FREE || *cp1 >= CLUST_RSRVD) {
275                 if (*cp2 == CLUST_FREE || *cp2 >= CLUST_RSRVD) {
276                         if ((*cp1 != CLUST_FREE && *cp1 < CLUST_BAD
277                              && *cp2 != CLUST_FREE && *cp2 < CLUST_BAD)
278                             || (*cp1 > CLUST_BAD && *cp2 > CLUST_BAD)) {
279                                 pwarn("Cluster %u is marked %s with different indicators, ",
280                                       cl, rsrvdcltype(*cp1));
281                                 if (ask(1, "fix")) {
282                                         *cp2 = *cp1;
283                                         return FSFATMOD;
284                                 }
285                                 return FSFATAL;
286                         }
287                         pwarn("Cluster %u is marked %s in FAT 0, %s in FAT %d\n",
288                               cl, rsrvdcltype(*cp1), rsrvdcltype(*cp2), fatnum);
289                         if (ask(0, "use FAT 0's entry")) {
290                                 *cp2 = *cp1;
291                                 return FSFATMOD;
292                         }
293                         if (ask(0, "use FAT %d's entry", fatnum)) {
294                                 *cp1 = *cp2;
295                                 return FSFATMOD;
296                         }
297                         return FSFATAL;
298                 }
299                 pwarn("Cluster %u is marked %s in FAT 0, but continues with cluster %u in FAT %d\n",
300                       cl, rsrvdcltype(*cp1), *cp2, fatnum);
301                 if (ask(0, "Use continuation from FAT %d", fatnum)) {
302                         *cp1 = *cp2;
303                         return FSFATMOD;
304                 }
305                 if (ask(0, "Use mark from FAT 0")) {
306                         *cp2 = *cp1;
307                         return FSFATMOD;
308                 }
309                 return FSFATAL;
310         }
311         if (*cp2 == CLUST_FREE || *cp2 >= CLUST_RSRVD) {
312                 pwarn("Cluster %u continues with cluster %u in FAT 0, but is marked %s in FAT %d\n",
313                       cl, *cp1, rsrvdcltype(*cp2), fatnum);
314                 if (ask(0, "Use continuation from FAT 0")) {
315                         *cp2 = *cp1;
316                         return FSFATMOD;
317                 }
318                 if (ask(0, "Use mark from FAT %d", fatnum)) {
319                         *cp1 = *cp2;
320                         return FSFATMOD;
321                 }
322                 return FSERROR;
323         }
324         pwarn("Cluster %u continues with cluster %u in FAT 0, but with cluster %u in FAT %d\n",
325               cl, *cp1, *cp2, fatnum);
326         if (ask(0, "Use continuation from FAT 0")) {
327                 *cp2 = *cp1;
328                 return FSFATMOD;
329         }
330         if (ask(0, "Use continuation from FAT %d", fatnum)) {
331                 *cp1 = *cp2;
332                 return FSFATMOD;
333         }
334         return FSERROR;
335 }
336
337 /*
338  * Compare two FAT copies in memory. Resolve any conflicts and merge them
339  * into the first one.
340  */
341 int
342 comparefat(boot, first, second, fatnum)
343         struct bootblock *boot;
344         struct fatEntry *first;
345         struct fatEntry *second;
346         int fatnum;
347 {
348         cl_t cl;
349         int ret = FSOK;
350
351         for (cl = CLUST_FIRST; cl < boot->NumClusters; cl++)
352                 if (first[cl].next != second[cl].next)
353                         ret |= clustdiffer(cl, &first[cl].next, &second[cl].next, fatnum);
354         return ret;
355 }
356
357 void
358 clearchain(boot, fat, head)
359         struct bootblock *boot;
360         struct fatEntry *fat;
361         cl_t head;
362 {
363         cl_t p, q;
364
365         for (p = head; p >= CLUST_FIRST && p < boot->NumClusters; p = q) {
366                 if (fat[p].head != head)
367                         break;
368                 q = fat[p].next;
369                 fat[p].next = fat[p].head = CLUST_FREE;
370                 fat[p].length = 0;
371         }
372 }
373
374 int
375 tryclear(boot, fat, head, trunc)
376         struct bootblock *boot;
377         struct fatEntry *fat;
378         cl_t head;
379         cl_t *trunc;
380 {
381         if (ask(0, "Clear chain starting at %u", head)) {
382                 clearchain(boot, fat, head);
383                 return FSFATMOD;
384         } else if (ask(0, "Truncate")) {
385                 *trunc = CLUST_EOF;
386                 return FSFATMOD;
387         } else
388                 return FSERROR;
389 }
390
391 /*
392  * Check a complete FAT in-memory for crosslinks
393  */
394 int
395 checkfat(boot, fat)
396         struct bootblock *boot;
397         struct fatEntry *fat;
398 {
399         cl_t head, p, h, n;
400         u_int len;
401         int ret = 0;
402         int conf;
403
404         /*
405          * pass 1: figure out the cluster chains.
406          */
407         for (head = CLUST_FIRST; head < boot->NumClusters; head++) {
408                 /* find next untravelled chain */
409                 if (fat[head].head != 0         /* cluster already belongs to some chain */
410                     || fat[head].next == CLUST_FREE
411                     || fat[head].next == CLUST_BAD)
412                         continue;               /* skip it. */
413
414                 /* follow the chain and mark all clusters on the way */
415                 for (len = 0, p = head;
416                      p >= CLUST_FIRST && p < boot->NumClusters;
417                      p = fat[p].next) {
418                         fat[p].head = head;
419                         len++;
420                 }
421
422                 /* the head record gets the length */
423                 fat[head].length = fat[head].next == CLUST_FREE ? 0 : len;
424         }
425
426         /*
427          * pass 2: check for crosslinked chains (we couldn't do this in pass 1 because
428          * we didn't know the real start of the chain then - would have treated partial
429          * chains as interlinked with their main chain)
430          */
431         for (head = CLUST_FIRST; head < boot->NumClusters; head++) {
432                 /* find next untravelled chain */
433                 if (fat[head].head != head)
434                         continue;
435
436                 /* follow the chain to its end (hopefully) */
437                 for (p = head;
438                      (n = fat[p].next) >= CLUST_FIRST && n < boot->NumClusters;
439                      p = n)
440                         if (fat[n].head != head)
441                                 break;
442                 if (n >= CLUST_EOFS)
443                         continue;
444
445                 if (n == CLUST_FREE || n >= CLUST_RSRVD) {
446                         pwarn("Cluster chain starting at %u ends with cluster marked %s\n",
447                               head, rsrvdcltype(n));
448                         ret |= tryclear(boot, fat, head, &fat[p].next);
449                         continue;
450                 }
451                 if (n < CLUST_FIRST || n >= boot->NumClusters) {
452                         pwarn("Cluster chain starting at %u ends with cluster out of range (%u)\n",
453                               head, n);
454                         ret |= tryclear(boot, fat, head, &fat[p].next);
455                         continue;
456                 }
457                 pwarn("Cluster chains starting at %u and %u are linked at cluster %u\n",
458                       head, fat[n].head, n);
459                 conf = tryclear(boot, fat, head, &fat[p].next);
460                 if (ask(0, "Clear chain starting at %u", h = fat[n].head)) {
461                         if (conf == FSERROR) {
462                                 /*
463                                  * Transfer the common chain to the one not cleared above.
464                                  */
465                                 for (p = n;
466                                      p >= CLUST_FIRST && p < boot->NumClusters;
467                                      p = fat[p].next) {
468                                         if (h != fat[p].head) {
469                                                 /*
470                                                  * Have to reexamine this chain.
471                                                  */
472                                                 head--;
473                                                 break;
474                                         }
475                                         fat[p].head = head;
476                                 }
477                         }
478                         clearchain(boot, fat, h);
479                         conf |= FSFATMOD;
480                 }
481                 ret |= conf;
482         }
483
484         return ret;
485 }
486
487 /*
488  * Write out FATs encoding them from the internal format
489  */
490 int
491 writefat(fs, boot, fat, correct_fat)
492         int fs;
493         struct bootblock *boot;
494         struct fatEntry *fat;
495         int correct_fat;
496 {
497         u_char *buffer, *p;
498         cl_t cl;
499         int i;
500         u_int32_t fatsz;
501         off_t off;
502         int ret = FSOK;
503
504         buffer = malloc(fatsz = boot->FATsecs * boot->BytesPerSec);
505         if (buffer == NULL) {
506                 perror("No space for FAT");
507                 return FSFATAL;
508         }
509         memset(buffer, 0, fatsz);
510         boot->NumFree = 0;
511         p = buffer;
512         if (correct_fat) {
513                 *p++ = (u_char)boot->Media;
514                 *p++ = 0xff;
515                 *p++ = 0xff;
516                 switch (boot->ClustMask) {
517                 case CLUST16_MASK:
518                         *p++ = 0xff;
519                         break;
520                 case CLUST32_MASK:
521                         *p++ = 0x0f;
522                         *p++ = 0xff;
523                         *p++ = 0xff;
524                         *p++ = 0xff;
525                         *p++ = 0x0f;
526                         break;
527                 }
528         } else {
529                 /* use same FAT signature as the old FAT has */
530                 int count;
531                 u_char *old_fat;
532
533                 switch (boot->ClustMask) {
534                 case CLUST32_MASK:
535                         count = 8;
536                         break;
537                 case CLUST16_MASK:
538                         count = 4;
539                         break;
540                 default:
541                         count = 3;
542                         break;
543                 }
544
545                 if (!_readfat(fs, boot, boot->ValidFat >= 0 ? boot->ValidFat :0,
546                                          &old_fat)) {
547                         free(buffer);
548                         return FSFATAL;
549                 }
550
551                 memcpy(p, old_fat, count);
552                 free(old_fat);
553                 p += count;
554         }
555                         
556         for (cl = CLUST_FIRST; cl < boot->NumClusters; cl++) {
557                 switch (boot->ClustMask) {
558                 case CLUST32_MASK:
559                         if (fat[cl].next == CLUST_FREE)
560                                 boot->NumFree++;
561                         *p++ = (u_char)fat[cl].next;
562                         *p++ = (u_char)(fat[cl].next >> 8);
563                         *p++ = (u_char)(fat[cl].next >> 16);
564                         *p &= 0xf0;
565                         *p++ |= (fat[cl].next >> 24)&0x0f;
566                         break;
567                 case CLUST16_MASK:
568                         if (fat[cl].next == CLUST_FREE)
569                                 boot->NumFree++;
570                         *p++ = (u_char)fat[cl].next;
571                         *p++ = (u_char)(fat[cl].next >> 8);
572                         break;
573                 default:
574                         if (fat[cl].next == CLUST_FREE)
575                                 boot->NumFree++;
576                         if (cl + 1 < boot->NumClusters
577                             && fat[cl + 1].next == CLUST_FREE)
578                                 boot->NumFree++;
579                         *p++ = (u_char)fat[cl].next;
580                         *p++ = (u_char)((fat[cl].next >> 8) & 0xf)
581                                |(u_char)(fat[cl+1].next << 4);
582                         *p++ = (u_char)(fat[++cl].next >> 4);
583                         break;
584                 }
585         }
586         for (i = 0; i < boot->FATs; i++) {
587                 off = boot->ResSectors + i * boot->FATsecs;
588                 off *= boot->BytesPerSec;
589                 if (lseek(fs, off, SEEK_SET) != off
590                     || write(fs, buffer, fatsz) != fatsz) {
591                         perror("Unable to write FAT");
592                         ret = FSFATAL; /* Return immediately?           XXX */
593                 }
594         }
595         free(buffer);
596         return ret;
597 }
598
599 /*
600  * Check a complete in-memory FAT for lost cluster chains
601  */
602 int
603 checklost(dosfs, boot, fat)
604         int dosfs;
605         struct bootblock *boot;
606         struct fatEntry *fat;
607 {
608         cl_t head;
609         int mod = FSOK;
610         int ret;
611         
612         for (head = CLUST_FIRST; head < boot->NumClusters; head++) {
613                 /* find next untravelled chain */
614                 if (fat[head].head != head
615                     || fat[head].next == CLUST_FREE
616                     || (fat[head].next >= CLUST_RSRVD
617                         && fat[head].next < CLUST_EOFS)
618                     || (fat[head].flags & FAT_USED))
619                         continue;
620
621                 pwarn("Lost cluster chain at cluster %u\n%d Cluster(s) lost\n",
622                       head, fat[head].length);
623                 mod |= ret = reconnect(dosfs, boot, fat, head);
624                 if (mod & FSFATAL)
625                         break;
626                 if (ret == FSERROR && ask(0, "Clear")) {
627                         clearchain(boot, fat, head);
628                         mod |= FSFATMOD;
629                 }
630         }
631         finishlf();
632
633         if (boot->FSInfo) {
634                 ret = 0;
635                 if (boot->FSFree != boot->NumFree) {
636                         pwarn("Free space in FSInfo block (%d) not correct (%d)\n",
637                               boot->FSFree, boot->NumFree);
638                         if (ask(1, "fix")) {
639                                 boot->FSFree = boot->NumFree;
640                                 ret = 1;
641                         }
642                 }
643                 if (boot->NumFree && fat[boot->FSNext].next != CLUST_FREE) {
644                         pwarn("Next free cluster in FSInfo block (%u) not free\n",
645                               boot->FSNext);
646                         if (ask(1, "fix"))
647                                 for (head = CLUST_FIRST; head < boot->NumClusters; head++)
648                                         if (fat[head].next == CLUST_FREE) {
649                                                 boot->FSNext = head;
650                                                 ret = 1;
651                                                 break;
652                                         }
653                 }
654                 if (ret)
655                         mod |= writefsinfo(dosfs, boot);
656         }
657
658         return mod;
659 }