2 * Copyright (C) 1995, 1996, 1997 Wolfgang Solfrank
3 * Copyright (c) 1995 Martin Husemann
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
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.
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.
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.4 2003/11/01 17:15:58 drhodus Exp $
38 #include <sys/cdefs.h>
49 static int checkclnum(struct bootblock
*, int, cl_t
, cl_t
*);
50 static int clustdiffer(cl_t
, cl_t
*, cl_t
*, int);
51 static int tryclear(struct bootblock
*, struct fatEntry
*, cl_t
, cl_t
*);
52 static int _readfat(int, struct bootblock
*, int, u_char
**);
55 * Check a cluster number for valid value
58 checkclnum(struct bootblock
*boot
, int fat
, cl_t cl
, cl_t
*next
)
60 if (*next
>= (CLUST_RSRVD
&boot
->ClustMask
))
61 *next
|= ~boot
->ClustMask
;
62 if (*next
== CLUST_FREE
) {
66 if (*next
== CLUST_BAD
) {
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",
74 *next
< CLUST_RSRVD
? "out of range" : "reserved",
75 *next
&boot
->ClustMask
);
76 if (ask(0, "Truncate")) {
86 * Read a FAT from disk. Returns 1 if successful, 0 otherwise.
89 _readfat(int fs
, struct bootblock
*boot
, int no
, u_char
**buffer
)
93 *buffer
= malloc(boot
->FATsecs
* boot
->BytesPerSec
);
94 if (*buffer
== NULL
) {
95 perror("No space for FAT");
99 off
= boot
->ResSectors
+ no
* boot
->FATsecs
;
100 off
*= boot
->BytesPerSec
;
102 if (lseek(fs
, off
, SEEK_SET
) != off
) {
103 perror("Unable to read FAT");
107 if (read(fs
, *buffer
, boot
->FATsecs
* boot
->BytesPerSec
)
108 != boot
->FATsecs
* boot
->BytesPerSec
) {
109 perror("Unable to read FAT");
121 * Read a FAT and decode it into internal format
124 readfat(int fs
, struct bootblock
*boot
, int no
, struct fatEntry
**fp
)
126 struct fatEntry
*fat
;
131 boot
->NumFree
= boot
->NumBad
= 0;
133 if (!_readfat(fs
, boot
, no
, &buffer
))
136 fat
= calloc(boot
->NumClusters
, sizeof(struct fatEntry
));
138 perror("No space for FAT");
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))) {
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.
157 if (buffer
[0] == boot
->Media
&& buffer
[1] == 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)))
166 /* just some odd byte sequence in FAT */
168 switch (boot
->ClustMask
) {
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]);
176 pwarn("%s (%02x%02x%02x%02x)\n",
177 "FAT starts with odd byte sequence",
178 buffer
[0], buffer
[1], buffer
[2], buffer
[3]);
181 pwarn("%s (%02x%02x%02x)\n",
182 "FAT starts with odd byte sequence",
183 buffer
[0], buffer
[1], buffer
[2]);
188 if (ask(1, "Correct"))
192 switch (boot
->ClustMask
) {
203 for (cl
= CLUST_FIRST
; cl
< boot
->NumClusters
;) {
204 switch (boot
->ClustMask
) {
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
);
214 fat
[cl
].next
= p
[0] + (p
[1] << 8);
215 ret
|= checkclnum(boot
, no
, cl
, &fat
[cl
].next
);
220 fat
[cl
].next
= (p
[0] + (p
[1] << 8)) & 0x0fff;
221 ret
|= checkclnum(boot
, no
, cl
, &fat
[cl
].next
);
223 if (cl
>= boot
->NumClusters
)
225 fat
[cl
].next
= ((p
[1] >> 4) + (p
[2] << 4)) & 0x0fff;
226 ret
|= checkclnum(boot
, no
, cl
, &fat
[cl
].next
);
239 * Get type of reserved cluster
244 if (cl
== CLUST_FREE
)
254 clustdiffer(cl_t cl
, cl_t
*cp1
, cl_t
*cp2
, int fatnum
)
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
));
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")) {
275 if (ask(0, "use FAT %d's entry", fatnum
)) {
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
)) {
287 if (ask(0, "Use mark from FAT 0")) {
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")) {
300 if (ask(0, "Use mark from FAT %d", fatnum
)) {
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")) {
312 if (ask(0, "Use continuation from FAT %d", fatnum
)) {
320 * Compare two FAT copies in memory. Resolve any conflicts and merge them
321 * into the first one.
324 comparefat(struct bootblock
*boot
, struct fatEntry
*first
,
325 struct fatEntry
*second
, int fatnum
)
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
);
337 clearchain(struct bootblock
*boot
, struct fatEntry
*fat
, cl_t head
)
341 for (p
= head
; p
>= CLUST_FIRST
&& p
< boot
->NumClusters
; p
= q
) {
342 if (fat
[p
].head
!= head
)
345 fat
[p
].next
= fat
[p
].head
= CLUST_FREE
;
351 tryclear(struct bootblock
*boot
, struct fatEntry
*fat
, cl_t head
, cl_t
*trunc
)
353 if (ask(0, "Clear chain starting at %u", head
)) {
354 clearchain(boot
, fat
, head
);
356 } else if (ask(0, "Truncate")) {
364 * Check a complete FAT in-memory for crosslinks
367 checkfat(struct bootblock
*boot
, struct fatEntry
*fat
)
375 * pass 1: figure out the cluster chains.
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. */
384 /* follow the chain and mark all clusters on the way */
385 for (len
= 0, p
= head
;
386 p
>= CLUST_FIRST
&& p
< boot
->NumClusters
;
392 /* the head record gets the length */
393 fat
[head
].length
= fat
[head
].next
== CLUST_FREE
? 0 : len
;
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)
401 for (head
= CLUST_FIRST
; head
< boot
->NumClusters
; head
++) {
402 /* find next untravelled chain */
403 if (fat
[head
].head
!= head
)
406 /* follow the chain to its end (hopefully) */
408 (n
= fat
[p
].next
) >= CLUST_FIRST
&& n
< boot
->NumClusters
;
410 if (fat
[n
].head
!= head
)
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
);
421 if (n
< CLUST_FIRST
|| n
>= boot
->NumClusters
) {
422 pwarn("Cluster chain starting at %u ends with cluster out of range (%u)\n",
424 ret
|= tryclear(boot
, fat
, head
, &fat
[p
].next
);
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
) {
433 * Transfer the common chain to the one not cleared above.
436 p
>= CLUST_FIRST
&& p
< boot
->NumClusters
;
438 if (h
!= fat
[p
].head
) {
440 * Have to reexamine this chain.
448 clearchain(boot
, fat
, h
);
458 * Write out FATs encoding them from the internal format
461 writefat(int fs
, struct bootblock
*boot
, struct fatEntry
*fat
, int correct_fat
)
470 buffer
= malloc(fatsz
= boot
->FATsecs
* boot
->BytesPerSec
);
471 if (buffer
== NULL
) {
472 perror("No space for FAT");
475 memset(buffer
, 0, fatsz
);
479 *p
++ = (u_char
)boot
->Media
;
482 switch (boot
->ClustMask
) {
495 /* use same FAT signature as the old FAT has */
499 switch (boot
->ClustMask
) {
511 if (!_readfat(fs
, boot
, boot
->ValidFat
>= 0 ? boot
->ValidFat
:0,
517 memcpy(p
, old_fat
, count
);
522 for (cl
= CLUST_FIRST
; cl
< boot
->NumClusters
; cl
++) {
523 switch (boot
->ClustMask
) {
525 if (fat
[cl
].next
== CLUST_FREE
)
527 *p
++ = (u_char
)fat
[cl
].next
;
528 *p
++ = (u_char
)(fat
[cl
].next
>> 8);
529 *p
++ = (u_char
)(fat
[cl
].next
>> 16);
531 *p
++ |= (fat
[cl
].next
>> 24)&0x0f;
534 if (fat
[cl
].next
== CLUST_FREE
)
536 *p
++ = (u_char
)fat
[cl
].next
;
537 *p
++ = (u_char
)(fat
[cl
].next
>> 8);
540 if (fat
[cl
].next
== CLUST_FREE
)
542 if (cl
+ 1 < boot
->NumClusters
543 && fat
[cl
+ 1].next
== CLUST_FREE
)
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);
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 */
566 * Check a complete in-memory FAT for lost cluster chains
569 checklost(int dosfs
, struct bootblock
*boot
, struct fatEntry
*fat
)
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
))
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
);
589 if (ret
== FSERROR
&& ask(0, "Clear")) {
590 clearchain(boot
, fat
, head
);
598 if (boot
->FSFree
!= boot
->NumFree
) {
599 pwarn("Free space in FSInfo block (%d) not correct (%d)\n",
600 boot
->FSFree
, boot
->NumFree
);
602 boot
->FSFree
= boot
->NumFree
;
606 if (boot
->NumFree
&& fat
[boot
->FSNext
].next
!= CLUST_FREE
) {
607 pwarn("Next free cluster in FSInfo block (%u) not free\n",
610 for (head
= CLUST_FIRST
; head
< boot
->NumClusters
; head
++)
611 if (fat
[head
].next
== CLUST_FREE
) {
618 mod
|= writefsinfo(dosfs
, boot
);