Add the DragonFly cvs id and perform general cleanups on cvs/rcs/sccs ids. Most
[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  * $NetBSD: fat.c,v 1.12 2000/10/10 20:24:52 is Exp $
33  * $FreeBSD: src/sbin/fsck_msdosfs/fat.c,v 1.1.2.1 2001/08/01 05:47:56 obrien Exp $
34  * $DragonFly: src/sbin/fsck_msdosfs/fat.c,v 1.2 2003/06/17 04:27:32 dillon Exp $
35  */
36
37
38 #include <sys/cdefs.h>
39
40 #include <stdlib.h>
41 #include <string.h>
42 #include <ctype.h>
43 #include <stdio.h>
44 #include <unistd.h>
45
46 #include "ext.h"
47 #include "fsutil.h"
48
49 static int checkclnum __P((struct bootblock *, int, cl_t, cl_t *));
50 static int clustdiffer __P((cl_t, cl_t *, cl_t *, int));
51 static int tryclear __P((struct bootblock *, struct fatEntry *, cl_t, cl_t *));
52 static int _readfat __P((int, struct bootblock *, int, u_char **));
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 from disk. Returns 1 if successful, 0 otherwise.
91  */
92 static int
93 _readfat(fs, boot, no, buffer)
94         int fs;
95         struct bootblock *boot;
96         int no;
97         u_char **buffer;
98 {
99         off_t off;
100
101         *buffer = malloc(boot->FATsecs * boot->BytesPerSec);
102         if (*buffer == NULL) {
103                 perror("No space for FAT");
104                 return 0;
105         }
106
107         off = boot->ResSectors + no * boot->FATsecs;
108         off *= boot->BytesPerSec;
109
110         if (lseek(fs, off, SEEK_SET) != off) {
111                 perror("Unable to read FAT");
112                 goto err;
113         }
114
115         if (read(fs, *buffer, boot->FATsecs * boot->BytesPerSec)
116             != boot->FATsecs * boot->BytesPerSec) {
117                 perror("Unable to read FAT");
118                 goto err;
119         }
120
121         return 1;
122
123     err:
124         free(*buffer);
125         return 0;
126 }
127
128 /*
129  * Read a FAT and decode it into internal format
130  */
131 int
132 readfat(fs, boot, no, fp)
133         int fs;
134         struct bootblock *boot;
135         int no;
136         struct fatEntry **fp;
137 {
138         struct fatEntry *fat;
139         u_char *buffer, *p;
140         cl_t cl;
141         int ret = FSOK;
142
143         boot->NumFree = boot->NumBad = 0;
144
145         if (!_readfat(fs, boot, no, &buffer))
146                 return FSFATAL;
147                 
148         fat = calloc(boot->NumClusters, sizeof(struct fatEntry));
149         if (fat == NULL) {
150                 perror("No space for FAT");
151                 free(buffer);
152                 return FSFATAL;
153         }
154
155         if (buffer[0] != boot->Media
156             || buffer[1] != 0xff || buffer[2] != 0xff
157             || (boot->ClustMask == CLUST16_MASK && buffer[3] != 0xff)
158             || (boot->ClustMask == CLUST32_MASK
159                 && ((buffer[3]&0x0f) != 0x0f
160                     || buffer[4] != 0xff || buffer[5] != 0xff
161                     || buffer[6] != 0xff || (buffer[7]&0x0f) != 0x0f))) {
162
163                 /* Windows 95 OSR2 (and possibly any later) changes
164                  * the FAT signature to 0xXXffff7f for FAT16 and to
165                  * 0xXXffff0fffffff07 for FAT32 upon boot, to know that the
166                  * filesystem is dirty if it doesn't reboot cleanly.
167                  * Check this special condition before errorring out.
168                  */
169                 if (buffer[0] == boot->Media && buffer[1] == 0xff
170                     && buffer[2] == 0xff
171                     && ((boot->ClustMask == CLUST16_MASK && buffer[3] == 0x7f)
172                         || (boot->ClustMask == CLUST32_MASK
173                             && buffer[3] == 0x0f && buffer[4] == 0xff
174                             && buffer[5] == 0xff && buffer[6] == 0xff
175                             && buffer[7] == 0x07)))
176                         ret |= FSDIRTY;
177                 else {
178                         /* just some odd byte sequence in FAT */
179                                 
180                         switch (boot->ClustMask) {
181                         case CLUST32_MASK:
182                                 pwarn("%s (%02x%02x%02x%02x%02x%02x%02x%02x)\n",
183                                       "FAT starts with odd byte sequence",
184                                       buffer[0], buffer[1], buffer[2], buffer[3],
185                                       buffer[4], buffer[5], buffer[6], buffer[7]);
186                                 break;
187                         case CLUST16_MASK:
188                                 pwarn("%s (%02x%02x%02x%02x)\n",
189                                     "FAT starts with odd byte sequence",
190                                     buffer[0], buffer[1], buffer[2], buffer[3]);
191                                 break;
192                         default:
193                                 pwarn("%s (%02x%02x%02x)\n",
194                                     "FAT starts with odd byte sequence",
195                                     buffer[0], buffer[1], buffer[2]);
196                                 break;
197                         }
198
199         
200                         if (ask(1, "Correct"))
201                                 ret |= FSFIXFAT;
202                 }
203         }
204         switch (boot->ClustMask) {
205         case CLUST32_MASK:
206                 p = buffer + 8;
207                 break;
208         case CLUST16_MASK:
209                 p = buffer + 4;
210                 break;
211         default:
212                 p = buffer + 3;
213                 break;
214         }
215         for (cl = CLUST_FIRST; cl < boot->NumClusters;) {
216                 switch (boot->ClustMask) {
217                 case CLUST32_MASK:
218                         fat[cl].next = p[0] + (p[1] << 8)
219                                        + (p[2] << 16) + (p[3] << 24);
220                         fat[cl].next &= boot->ClustMask;
221                         ret |= checkclnum(boot, no, cl, &fat[cl].next);
222                         cl++;
223                         p += 4;
224                         break;
225                 case CLUST16_MASK:
226                         fat[cl].next = p[0] + (p[1] << 8);
227                         ret |= checkclnum(boot, no, cl, &fat[cl].next);
228                         cl++;
229                         p += 2;
230                         break;
231                 default:
232                         fat[cl].next = (p[0] + (p[1] << 8)) & 0x0fff;
233                         ret |= checkclnum(boot, no, cl, &fat[cl].next);
234                         cl++;
235                         if (cl >= boot->NumClusters)
236                                 break;
237                         fat[cl].next = ((p[1] >> 4) + (p[2] << 4)) & 0x0fff;
238                         ret |= checkclnum(boot, no, cl, &fat[cl].next);
239                         cl++;
240                         p += 3;
241                         break;
242                 }
243         }
244
245         free(buffer);
246         *fp = fat;
247         return ret;
248 }
249
250 /*
251  * Get type of reserved cluster
252  */
253 char *
254 rsrvdcltype(cl)
255         cl_t cl;
256 {
257         if (cl == CLUST_FREE)
258                 return "free";
259         if (cl < CLUST_BAD)
260                 return "reserved";
261         if (cl > CLUST_BAD)
262                 return "as EOF";
263         return "bad";
264 }
265
266 static int
267 clustdiffer(cl, cp1, cp2, fatnum)
268         cl_t cl;
269         cl_t *cp1;
270         cl_t *cp2;
271         int fatnum;
272 {
273         if (*cp1 == CLUST_FREE || *cp1 >= CLUST_RSRVD) {
274                 if (*cp2 == CLUST_FREE || *cp2 >= CLUST_RSRVD) {
275                         if ((*cp1 != CLUST_FREE && *cp1 < CLUST_BAD
276                              && *cp2 != CLUST_FREE && *cp2 < CLUST_BAD)
277                             || (*cp1 > CLUST_BAD && *cp2 > CLUST_BAD)) {
278                                 pwarn("Cluster %u is marked %s with different indicators, ",
279                                       cl, rsrvdcltype(*cp1));
280                                 if (ask(1, "fix")) {
281                                         *cp2 = *cp1;
282                                         return FSFATMOD;
283                                 }
284                                 return FSFATAL;
285                         }
286                         pwarn("Cluster %u is marked %s in FAT 0, %s in FAT %d\n",
287                               cl, rsrvdcltype(*cp1), rsrvdcltype(*cp2), fatnum);
288                         if (ask(0, "use FAT 0's entry")) {
289                                 *cp2 = *cp1;
290                                 return FSFATMOD;
291                         }
292                         if (ask(0, "use FAT %d's entry", fatnum)) {
293                                 *cp1 = *cp2;
294                                 return FSFATMOD;
295                         }
296                         return FSFATAL;
297                 }
298                 pwarn("Cluster %u is marked %s in FAT 0, but continues with cluster %u in FAT %d\n",
299                       cl, rsrvdcltype(*cp1), *cp2, fatnum);
300                 if (ask(0, "Use continuation from FAT %d", fatnum)) {
301                         *cp1 = *cp2;
302                         return FSFATMOD;
303                 }
304                 if (ask(0, "Use mark from FAT 0")) {
305                         *cp2 = *cp1;
306                         return FSFATMOD;
307                 }
308                 return FSFATAL;
309         }
310         if (*cp2 == CLUST_FREE || *cp2 >= CLUST_RSRVD) {
311                 pwarn("Cluster %u continues with cluster %u in FAT 0, but is marked %s in FAT %d\n",
312                       cl, *cp1, rsrvdcltype(*cp2), fatnum);
313                 if (ask(0, "Use continuation from FAT 0")) {
314                         *cp2 = *cp1;
315                         return FSFATMOD;
316                 }
317                 if (ask(0, "Use mark from FAT %d", fatnum)) {
318                         *cp1 = *cp2;
319                         return FSFATMOD;
320                 }
321                 return FSERROR;
322         }
323         pwarn("Cluster %u continues with cluster %u in FAT 0, but with cluster %u in FAT %d\n",
324               cl, *cp1, *cp2, fatnum);
325         if (ask(0, "Use continuation from FAT 0")) {
326                 *cp2 = *cp1;
327                 return FSFATMOD;
328         }
329         if (ask(0, "Use continuation from FAT %d", fatnum)) {
330                 *cp1 = *cp2;
331                 return FSFATMOD;
332         }
333         return FSERROR;
334 }
335
336 /*
337  * Compare two FAT copies in memory. Resolve any conflicts and merge them
338  * into the first one.
339  */
340 int
341 comparefat(boot, first, second, fatnum)
342         struct bootblock *boot;
343         struct fatEntry *first;
344         struct fatEntry *second;
345         int fatnum;
346 {
347         cl_t cl;
348         int ret = FSOK;
349
350         for (cl = CLUST_FIRST; cl < boot->NumClusters; cl++)
351                 if (first[cl].next != second[cl].next)
352                         ret |= clustdiffer(cl, &first[cl].next, &second[cl].next, fatnum);
353         return ret;
354 }
355
356 void
357 clearchain(boot, fat, head)
358         struct bootblock *boot;
359         struct fatEntry *fat;
360         cl_t head;
361 {
362         cl_t p, q;
363
364         for (p = head; p >= CLUST_FIRST && p < boot->NumClusters; p = q) {
365                 if (fat[p].head != head)
366                         break;
367                 q = fat[p].next;
368                 fat[p].next = fat[p].head = CLUST_FREE;
369                 fat[p].length = 0;
370         }
371 }
372
373 int
374 tryclear(boot, fat, head, trunc)
375         struct bootblock *boot;
376         struct fatEntry *fat;
377         cl_t head;
378         cl_t *trunc;
379 {
380         if (ask(0, "Clear chain starting at %u", head)) {
381                 clearchain(boot, fat, head);
382                 return FSFATMOD;
383         } else if (ask(0, "Truncate")) {
384                 *trunc = CLUST_EOF;
385                 return FSFATMOD;
386         } else
387                 return FSERROR;
388 }
389
390 /*
391  * Check a complete FAT in-memory for crosslinks
392  */
393 int
394 checkfat(boot, fat)
395         struct bootblock *boot;
396         struct fatEntry *fat;
397 {
398         cl_t head, p, h, n;
399         u_int len;
400         int ret = 0;
401         int conf;
402
403         /*
404          * pass 1: figure out the cluster chains.
405          */
406         for (head = CLUST_FIRST; head < boot->NumClusters; head++) {
407                 /* find next untravelled chain */
408                 if (fat[head].head != 0         /* cluster already belongs to some chain */
409                     || fat[head].next == CLUST_FREE
410                     || fat[head].next == CLUST_BAD)
411                         continue;               /* skip it. */
412
413                 /* follow the chain and mark all clusters on the way */
414                 for (len = 0, p = head;
415                      p >= CLUST_FIRST && p < boot->NumClusters;
416                      p = fat[p].next) {
417                         fat[p].head = head;
418                         len++;
419                 }
420
421                 /* the head record gets the length */
422                 fat[head].length = fat[head].next == CLUST_FREE ? 0 : len;
423         }
424
425         /*
426          * pass 2: check for crosslinked chains (we couldn't do this in pass 1 because
427          * we didn't know the real start of the chain then - would have treated partial
428          * chains as interlinked with their main chain)
429          */
430         for (head = CLUST_FIRST; head < boot->NumClusters; head++) {
431                 /* find next untravelled chain */
432                 if (fat[head].head != head)
433                         continue;
434
435                 /* follow the chain to its end (hopefully) */
436                 for (p = head;
437                      (n = fat[p].next) >= CLUST_FIRST && n < boot->NumClusters;
438                      p = n)
439                         if (fat[n].head != head)
440                                 break;
441                 if (n >= CLUST_EOFS)
442                         continue;
443
444                 if (n == CLUST_FREE || n >= CLUST_RSRVD) {
445                         pwarn("Cluster chain starting at %u ends with cluster marked %s\n",
446                               head, rsrvdcltype(n));
447                         ret |= tryclear(boot, fat, head, &fat[p].next);
448                         continue;
449                 }
450                 if (n < CLUST_FIRST || n >= boot->NumClusters) {
451                         pwarn("Cluster chain starting at %u ends with cluster out of range (%u)\n",
452                               head, n);
453                         ret |= tryclear(boot, fat, head, &fat[p].next);
454                         continue;
455                 }
456                 pwarn("Cluster chains starting at %u and %u are linked at cluster %u\n",
457                       head, fat[n].head, n);
458                 conf = tryclear(boot, fat, head, &fat[p].next);
459                 if (ask(0, "Clear chain starting at %u", h = fat[n].head)) {
460                         if (conf == FSERROR) {
461                                 /*
462                                  * Transfer the common chain to the one not cleared above.
463                                  */
464                                 for (p = n;
465                                      p >= CLUST_FIRST && p < boot->NumClusters;
466                                      p = fat[p].next) {
467                                         if (h != fat[p].head) {
468                                                 /*
469                                                  * Have to reexamine this chain.
470                                                  */
471                                                 head--;
472                                                 break;
473                                         }
474                                         fat[p].head = head;
475                                 }
476                         }
477                         clearchain(boot, fat, h);
478                         conf |= FSFATMOD;
479                 }
480                 ret |= conf;
481         }
482
483         return ret;
484 }
485
486 /*
487  * Write out FATs encoding them from the internal format
488  */
489 int
490 writefat(fs, boot, fat, correct_fat)
491         int fs;
492         struct bootblock *boot;
493         struct fatEntry *fat;
494         int correct_fat;
495 {
496         u_char *buffer, *p;
497         cl_t cl;
498         int i;
499         u_int32_t fatsz;
500         off_t off;
501         int ret = FSOK;
502
503         buffer = malloc(fatsz = boot->FATsecs * boot->BytesPerSec);
504         if (buffer == NULL) {
505                 perror("No space for FAT");
506                 return FSFATAL;
507         }
508         memset(buffer, 0, fatsz);
509         boot->NumFree = 0;
510         p = buffer;
511         if (correct_fat) {
512                 *p++ = (u_char)boot->Media;
513                 *p++ = 0xff;
514                 *p++ = 0xff;
515                 switch (boot->ClustMask) {
516                 case CLUST16_MASK:
517                         *p++ = 0xff;
518                         break;
519                 case CLUST32_MASK:
520                         *p++ = 0x0f;
521                         *p++ = 0xff;
522                         *p++ = 0xff;
523                         *p++ = 0xff;
524                         *p++ = 0x0f;
525                         break;
526                 }
527         } else {
528                 /* use same FAT signature as the old FAT has */
529                 int count;
530                 u_char *old_fat;
531
532                 switch (boot->ClustMask) {
533                 case CLUST32_MASK:
534                         count = 8;
535                         break;
536                 case CLUST16_MASK:
537                         count = 4;
538                         break;
539                 default:
540                         count = 3;
541                         break;
542                 }
543
544                 if (!_readfat(fs, boot, boot->ValidFat >= 0 ? boot->ValidFat :0,
545                                          &old_fat)) {
546                         free(buffer);
547                         return FSFATAL;
548                 }
549
550                 memcpy(p, old_fat, count);
551                 free(old_fat);
552                 p += count;
553         }
554                         
555         for (cl = CLUST_FIRST; cl < boot->NumClusters; cl++) {
556                 switch (boot->ClustMask) {
557                 case CLUST32_MASK:
558                         if (fat[cl].next == CLUST_FREE)
559                                 boot->NumFree++;
560                         *p++ = (u_char)fat[cl].next;
561                         *p++ = (u_char)(fat[cl].next >> 8);
562                         *p++ = (u_char)(fat[cl].next >> 16);
563                         *p &= 0xf0;
564                         *p++ |= (fat[cl].next >> 24)&0x0f;
565                         break;
566                 case CLUST16_MASK:
567                         if (fat[cl].next == CLUST_FREE)
568                                 boot->NumFree++;
569                         *p++ = (u_char)fat[cl].next;
570                         *p++ = (u_char)(fat[cl].next >> 8);
571                         break;
572                 default:
573                         if (fat[cl].next == CLUST_FREE)
574                                 boot->NumFree++;
575                         if (cl + 1 < boot->NumClusters
576                             && fat[cl + 1].next == CLUST_FREE)
577                                 boot->NumFree++;
578                         *p++ = (u_char)fat[cl].next;
579                         *p++ = (u_char)((fat[cl].next >> 8) & 0xf)
580                                |(u_char)(fat[cl+1].next << 4);
581                         *p++ = (u_char)(fat[++cl].next >> 4);
582                         break;
583                 }
584         }
585         for (i = 0; i < boot->FATs; i++) {
586                 off = boot->ResSectors + i * boot->FATsecs;
587                 off *= boot->BytesPerSec;
588                 if (lseek(fs, off, SEEK_SET) != off
589                     || write(fs, buffer, fatsz) != fatsz) {
590                         perror("Unable to write FAT");
591                         ret = FSFATAL; /* Return immediately?           XXX */
592                 }
593         }
594         free(buffer);
595         return ret;
596 }
597
598 /*
599  * Check a complete in-memory FAT for lost cluster chains
600  */
601 int
602 checklost(dosfs, boot, fat)
603         int dosfs;
604         struct bootblock *boot;
605         struct fatEntry *fat;
606 {
607         cl_t head;
608         int mod = FSOK;
609         int ret;
610         
611         for (head = CLUST_FIRST; head < boot->NumClusters; head++) {
612                 /* find next untravelled chain */
613                 if (fat[head].head != head
614                     || fat[head].next == CLUST_FREE
615                     || (fat[head].next >= CLUST_RSRVD
616                         && fat[head].next < CLUST_EOFS)
617                     || (fat[head].flags & FAT_USED))
618                         continue;
619
620                 pwarn("Lost cluster chain at cluster %u\n%d Cluster(s) lost\n",
621                       head, fat[head].length);
622                 mod |= ret = reconnect(dosfs, boot, fat, head);
623                 if (mod & FSFATAL)
624                         break;
625                 if (ret == FSERROR && ask(0, "Clear")) {
626                         clearchain(boot, fat, head);
627                         mod |= FSFATMOD;
628                 }
629         }
630         finishlf();
631
632         if (boot->FSInfo) {
633                 ret = 0;
634                 if (boot->FSFree != boot->NumFree) {
635                         pwarn("Free space in FSInfo block (%d) not correct (%d)\n",
636                               boot->FSFree, boot->NumFree);
637                         if (ask(1, "fix")) {
638                                 boot->FSFree = boot->NumFree;
639                                 ret = 1;
640                         }
641                 }
642                 if (boot->NumFree && fat[boot->FSNext].next != CLUST_FREE) {
643                         pwarn("Next free cluster in FSInfo block (%u) not free\n",
644                               boot->FSNext);
645                         if (ask(1, "fix"))
646                                 for (head = CLUST_FIRST; head < boot->NumClusters; head++)
647                                         if (fat[head].next == CLUST_FREE) {
648                                                 boot->FSNext = head;
649                                                 ret = 1;
650                                                 break;
651                                         }
652                 }
653                 if (ret)
654                         mod |= writefsinfo(dosfs, boot);
655         }
656
657         return mod;
658 }