1 /* $NetBSD: fat.c,v 1.21 2008/07/24 14:23:16 matthias Exp $ */
4 * Copyright (C) 1995, 1996, 1997 Wolfgang Solfrank
5 * Copyright (c) 1995 Martin Husemann
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
16 * THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND ANY EXPRESS OR
17 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
18 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
19 * IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY DIRECT, INDIRECT,
20 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
21 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
25 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 #include <sys/cdefs.h>
31 __RCSID("$NetBSD: fat.c,v 1.21 2008/07/24 14:23:16 matthias Exp $");
43 static int checkclnum(struct bootblock
*, u_int
, cl_t
, cl_t
*);
44 static int clustdiffer(cl_t
, cl_t
*, cl_t
*, u_int
);
45 static int tryclear(struct bootblock
*, struct fatEntry
*, cl_t
, cl_t
*);
46 static int _readfat(int, struct bootblock
*, u_int
, u_char
**);
49 * Check a cluster number for valid value
52 checkclnum(struct bootblock
*boot
, u_int fat
, cl_t cl
, cl_t
*next
)
54 if (*next
>= (CLUST_RSRVD
&boot
->ClustMask
))
55 *next
|= ~boot
->ClustMask
;
56 if (*next
== CLUST_FREE
) {
60 if (*next
== CLUST_BAD
) {
64 if (*next
< CLUST_FIRST
65 || (*next
>= boot
->NumClusters
&& *next
< CLUST_EOFS
)) {
66 pwarn("Cluster %u in FAT %u continues with %s cluster number %u\n",
68 *next
< CLUST_RSRVD
? "out of range" : "reserved",
69 *next
&boot
->ClustMask
);
70 if (ask(0, "Truncate")) {
80 * Read a FAT from disk. Returns 1 if successful, 0 otherwise.
83 _readfat(int fs
, struct bootblock
*boot
, u_int no
, u_char
**buffer
)
88 *buffer
= malloc(len
= boot
->FATsecs
* boot
->BytesPerSec
);
89 if (*buffer
== NULL
) {
90 perr("No space for FAT sectors (%zu)", len
);
94 off
= boot
->ResSectors
+ no
* boot
->FATsecs
;
95 off
*= boot
->BytesPerSec
;
97 if (lseek(fs
, off
, SEEK_SET
) != off
) {
98 perr("Unable to read FAT");
102 if ((size_t)read(fs
, *buffer
, boot
->FATsecs
* boot
->BytesPerSec
)
103 != boot
->FATsecs
* boot
->BytesPerSec
) {
104 perr("Unable to read FAT");
116 * Read a FAT and decode it into internal format
119 readfat(int fs
, struct bootblock
*boot
, u_int no
, struct fatEntry
**fp
)
121 struct fatEntry
*fat
;
127 boot
->NumFree
= boot
->NumBad
= 0;
129 if (!_readfat(fs
, boot
, no
, &buffer
))
132 fat
= malloc(len
= boot
->NumClusters
* sizeof(struct fatEntry
));
134 perr("No space for FAT clusters (%zu)", len
);
138 (void)memset(fat
, 0, len
);
140 if (buffer
[0] != boot
->Media
141 || buffer
[1] != 0xff || buffer
[2] != 0xff
142 || (boot
->ClustMask
== CLUST16_MASK
&& buffer
[3] != 0xff)
143 || (boot
->ClustMask
== CLUST32_MASK
144 && ((buffer
[3]&0x0f) != 0x0f
145 || buffer
[4] != 0xff || buffer
[5] != 0xff
146 || buffer
[6] != 0xff || (buffer
[7]&0x0f) != 0x0f))) {
148 /* Windows 95 OSR2 (and possibly any later) changes
149 * the FAT signature to 0xXXffff7f for FAT16 and to
150 * 0xXXffff0fffffff07 for FAT32 upon boot, to know that the
151 * filesystem is dirty if it doesn't reboot cleanly.
152 * Check this special condition before errorring out.
154 if (buffer
[0] == boot
->Media
&& buffer
[1] == 0xff
156 && ((boot
->ClustMask
== CLUST16_MASK
&& buffer
[3] == 0x7f)
157 || (boot
->ClustMask
== CLUST32_MASK
158 && buffer
[3] == 0x0f && buffer
[4] == 0xff
159 && buffer
[5] == 0xff && buffer
[6] == 0xff
160 && buffer
[7] == 0x07)))
163 /* just some odd byte sequence in FAT */
165 switch (boot
->ClustMask
) {
167 pwarn("%s (%02x%02x%02x%02x%02x%02x%02x%02x)\n",
168 "FAT starts with odd byte sequence",
169 buffer
[0], buffer
[1], buffer
[2], buffer
[3],
170 buffer
[4], buffer
[5], buffer
[6], buffer
[7]);
173 pwarn("%s (%02x%02x%02x%02x)\n",
174 "FAT starts with odd byte sequence",
175 buffer
[0], buffer
[1], buffer
[2], buffer
[3]);
178 pwarn("%s (%02x%02x%02x)\n",
179 "FAT starts with odd byte sequence",
180 buffer
[0], buffer
[1], buffer
[2]);
185 if (ask(1, "Correct"))
189 switch (boot
->ClustMask
) {
200 for (cl
= CLUST_FIRST
; cl
< boot
->NumClusters
;) {
201 switch (boot
->ClustMask
) {
203 fat
[cl
].next
= p
[0] + (p
[1] << 8)
204 + (p
[2] << 16) + (p
[3] << 24);
205 fat
[cl
].next
&= boot
->ClustMask
;
206 ret
|= checkclnum(boot
, no
, cl
, &fat
[cl
].next
);
211 fat
[cl
].next
= p
[0] + (p
[1] << 8);
212 ret
|= checkclnum(boot
, no
, cl
, &fat
[cl
].next
);
217 fat
[cl
].next
= (p
[0] + (p
[1] << 8)) & 0x0fff;
218 ret
|= checkclnum(boot
, no
, cl
, &fat
[cl
].next
);
220 if (cl
>= boot
->NumClusters
)
222 fat
[cl
].next
= ((p
[1] >> 4) + (p
[2] << 4)) & 0x0fff;
223 ret
|= checkclnum(boot
, no
, cl
, &fat
[cl
].next
);
240 * Get type of reserved cluster
245 if (cl
== CLUST_FREE
)
255 clustdiffer(cl_t cl
, cl_t
*cp1
, cl_t
*cp2
, u_int fatnum
)
257 if (*cp1
== CLUST_FREE
|| *cp1
>= CLUST_RSRVD
) {
258 if (*cp2
== CLUST_FREE
|| *cp2
>= CLUST_RSRVD
) {
259 if ((*cp1
!= CLUST_FREE
&& *cp1
< CLUST_BAD
260 && *cp2
!= CLUST_FREE
&& *cp2
< CLUST_BAD
)
261 || (*cp1
> CLUST_BAD
&& *cp2
> CLUST_BAD
)) {
262 pwarn("Cluster %u is marked %s with different indicators, ",
263 cl
, rsrvdcltype(*cp1
));
270 pwarn("Cluster %u is marked %s in FAT 0, %s in FAT %u\n",
271 cl
, rsrvdcltype(*cp1
), rsrvdcltype(*cp2
), fatnum
);
272 if (ask(0, "use FAT 0's entry")) {
276 if (ask(0, "use FAT %u's entry", fatnum
)) {
282 pwarn("Cluster %u is marked %s in FAT 0, but continues with cluster %u in FAT %u\n",
283 cl
, rsrvdcltype(*cp1
), *cp2
, fatnum
);
284 if (ask(0, "Use continuation from FAT %u", fatnum
)) {
288 if (ask(0, "Use mark from FAT 0")) {
294 if (*cp2
== CLUST_FREE
|| *cp2
>= CLUST_RSRVD
) {
295 pwarn("Cluster %u continues with cluster %u in FAT 0, but is marked %s in FAT %u\n",
296 cl
, *cp1
, rsrvdcltype(*cp2
), fatnum
);
297 if (ask(0, "Use continuation from FAT 0")) {
301 if (ask(0, "Use mark from FAT %u", fatnum
)) {
307 pwarn("Cluster %u continues with cluster %u in FAT 0, but with cluster %u in FAT %u\n",
308 cl
, *cp1
, *cp2
, fatnum
);
309 if (ask(0, "Use continuation from FAT 0")) {
313 if (ask(0, "Use continuation from FAT %u", fatnum
)) {
321 * Compare two FAT copies in memory. Resolve any conflicts and merge them
322 * into the first one.
325 comparefat(struct bootblock
*boot
, struct fatEntry
*first
,
326 struct fatEntry
*second
, u_int fatnum
)
331 for (cl
= CLUST_FIRST
; cl
< boot
->NumClusters
; cl
++)
332 if (first
[cl
].next
!= second
[cl
].next
)
333 ret
|= clustdiffer(cl
, &first
[cl
].next
, &second
[cl
].next
, fatnum
);
338 clearchain(struct bootblock
*boot
, struct fatEntry
*fat
, cl_t head
)
342 for (p
= head
; p
>= CLUST_FIRST
&& p
< boot
->NumClusters
; p
= q
) {
343 if (fat
[p
].head
!= head
)
346 fat
[p
].next
= fat
[p
].head
= CLUST_FREE
;
352 tryclear(struct bootblock
*boot
, struct fatEntry
*fat
, cl_t head
, cl_t
*truncp
)
354 if (ask(0, "Clear chain starting at %u", head
)) {
355 clearchain(boot
, fat
, head
);
357 } else if (ask(0, "Truncate")) {
365 * Check a complete FAT in-memory for crosslinks
368 checkfat(struct bootblock
*boot
, struct fatEntry
*fat
)
376 * pass 1: figure out the cluster chains.
378 for (head
= CLUST_FIRST
; head
< boot
->NumClusters
; head
++) {
379 /* find next untravelled chain */
380 if (fat
[head
].head
!= 0 /* cluster already belongs to some chain */
381 || fat
[head
].next
== CLUST_FREE
382 || fat
[head
].next
== CLUST_BAD
)
383 continue; /* skip it. */
385 /* follow the chain and mark all clusters on the way */
386 for (len
= 0, p
= head
;
387 p
>= CLUST_FIRST
&& p
< boot
->NumClusters
;
393 /* the head record gets the length */
394 fat
[head
].length
= fat
[head
].next
== CLUST_FREE
? 0 : len
;
398 * pass 2: check for crosslinked chains (we couldn't do this in pass 1 because
399 * we didn't know the real start of the chain then - would have treated partial
400 * chains as interlinked with their main chain)
402 for (head
= CLUST_FIRST
; head
< boot
->NumClusters
; head
++) {
403 /* find next untravelled chain */
404 if (fat
[head
].head
!= head
)
407 /* follow the chain to its end (hopefully) */
409 (n
= fat
[p
].next
) >= CLUST_FIRST
&& n
< boot
->NumClusters
;
411 if (fat
[n
].head
!= head
)
416 if (n
== CLUST_FREE
|| n
>= CLUST_RSRVD
) {
417 pwarn("Cluster chain starting at %u ends with cluster marked %s\n",
418 head
, rsrvdcltype(n
));
419 ret
|= tryclear(boot
, fat
, head
, &fat
[p
].next
);
422 if (n
< CLUST_FIRST
|| n
>= boot
->NumClusters
) {
423 pwarn("Cluster chain starting at %u ends with cluster out of range (%u)\n",
425 ret
|= tryclear(boot
, fat
, head
, &fat
[p
].next
);
428 pwarn("Cluster chains starting at %u and %u are linked at cluster %u\n",
429 head
, fat
[n
].head
, n
);
430 conf
= tryclear(boot
, fat
, head
, &fat
[p
].next
);
431 if (ask(0, "Clear chain starting at %u", h
= fat
[n
].head
)) {
432 if (conf
== FSERROR
) {
434 * Transfer the common chain to the one not cleared above.
437 p
>= CLUST_FIRST
&& p
< boot
->NumClusters
;
439 if (h
!= fat
[p
].head
) {
441 * Have to reexamine this chain.
449 clearchain(boot
, fat
, h
);
459 * Write out FATs encoding them from the internal format
462 writefat(int fs
, struct bootblock
*boot
, struct fatEntry
*fat
, int correct_fat
)
471 buffer
= malloc(fatsz
= boot
->FATsecs
* boot
->BytesPerSec
);
472 if (buffer
== NULL
) {
473 perr("No space for FAT sectors (%zu)", fatsz
);
476 memset(buffer
, 0, fatsz
);
480 *p
++ = (u_char
)boot
->Media
;
483 switch (boot
->ClustMask
) {
496 /* use same FAT signature as the old FAT has */
500 switch (boot
->ClustMask
) {
512 if (!_readfat(fs
, boot
, boot
->ValidFat
>= 0 ? boot
->ValidFat
:0,
518 memcpy(p
, old_fat
, count
);
523 for (cl
= CLUST_FIRST
; cl
< boot
->NumClusters
; cl
++) {
524 switch (boot
->ClustMask
) {
526 if (fat
[cl
].next
== CLUST_FREE
)
528 *p
++ = (u_char
)fat
[cl
].next
;
529 *p
++ = (u_char
)(fat
[cl
].next
>> 8);
530 *p
++ = (u_char
)(fat
[cl
].next
>> 16);
532 *p
++ |= (fat
[cl
].next
>> 24)&0x0f;
535 if (fat
[cl
].next
== CLUST_FREE
)
537 *p
++ = (u_char
)fat
[cl
].next
;
538 *p
++ = (u_char
)(fat
[cl
].next
>> 8);
541 if (fat
[cl
].next
== CLUST_FREE
)
543 if (cl
+ 1 < boot
->NumClusters
544 && fat
[cl
+ 1].next
== CLUST_FREE
)
546 *p
++ = (u_char
)fat
[cl
].next
;
547 *p
++ = (u_char
)((fat
[cl
].next
>> 8) & 0xf)
548 |(u_char
)(fat
[cl
+1].next
<< 4);
549 *p
++ = (u_char
)(fat
[++cl
].next
>> 4);
553 for (i
= 0; i
< boot
->FATs
; i
++) {
554 off
= boot
->ResSectors
+ i
* boot
->FATsecs
;
555 off
*= boot
->BytesPerSec
;
556 if (lseek(fs
, off
, SEEK_SET
) != off
557 || (size_t)write(fs
, buffer
, fatsz
) != fatsz
) {
558 perr("Unable to write FAT");
559 ret
= FSFATAL
; /* Return immediately? XXX */
567 * Check a complete in-memory FAT for lost cluster chains
570 checklost(int dosfs
, struct bootblock
*boot
, struct fatEntry
*fat
)
576 for (head
= CLUST_FIRST
; head
< boot
->NumClusters
; head
++) {
577 /* find next untravelled chain */
578 if (fat
[head
].head
!= head
579 || fat
[head
].next
== CLUST_FREE
580 || (fat
[head
].next
>= CLUST_RSRVD
581 && fat
[head
].next
< CLUST_EOFS
)
582 || (fat
[head
].flags
& FAT_USED
))
585 pwarn("Lost cluster chain at cluster %u\n%d Cluster(s) lost\n",
586 head
, fat
[head
].length
);
587 mod
|= ret
= reconnect(dosfs
, boot
, fat
, head
);
590 if (ret
== FSERROR
&& ask(0, "Clear")) {
591 clearchain(boot
, fat
, head
);
599 if (boot
->FSFree
!= boot
->NumFree
) {
600 pwarn("Free space in FSInfo block (%d) not correct (%d)\n",
601 boot
->FSFree
, boot
->NumFree
);
603 boot
->FSFree
= boot
->NumFree
;
607 if (boot
->FSNext
>= boot
->NumClusters
|| (boot
->NumFree
&& fat
[boot
->FSNext
].next
!= CLUST_FREE
)) {
608 pwarn("Next free cluster in FSInfo block (%u) %s\n",
610 (boot
->FSNext
>= boot
->NumClusters
) ? "invalid" : "not free");
612 for (head
= CLUST_FIRST
; head
< boot
->NumClusters
; head
++)
613 if (fat
[head
].next
== CLUST_FREE
) {
620 mod
|= writefsinfo(dosfs
, boot
);