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