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 $
45 static int checkclnum(struct bootblock
*, int, cl_t
, cl_t
*);
46 static int clustdiffer(cl_t
, cl_t
*, cl_t
*, int);
47 static int tryclear(struct bootblock
*, struct fatEntry
*, cl_t
, cl_t
*);
48 static int _readfat(int, struct bootblock
*, int, u_char
**);
51 * Check a cluster number for valid value
54 checkclnum(struct bootblock
*boot
, int fat
, cl_t cl
, cl_t
*next
)
56 if (*next
>= (CLUST_RSRVD
&boot
->ClustMask
))
57 *next
|= ~boot
->ClustMask
;
58 if (*next
== CLUST_FREE
) {
62 if (*next
== CLUST_BAD
) {
66 if (*next
< CLUST_FIRST
67 || (*next
>= boot
->NumClusters
&& *next
< CLUST_EOFS
)) {
68 pwarn("Cluster %u in FAT %d continues with %s cluster number %u\n",
70 *next
< CLUST_RSRVD
? "out of range" : "reserved",
71 *next
&boot
->ClustMask
);
72 if (ask(0, "Truncate")) {
82 * Read a FAT from disk. Returns 1 if successful, 0 otherwise.
85 _readfat(int fs
, struct bootblock
*boot
, int no
, u_char
**buffer
)
89 *buffer
= malloc(boot
->FATsecs
* boot
->BytesPerSec
);
90 if (*buffer
== NULL
) {
91 perror("No space for FAT");
95 off
= boot
->ResSectors
+ no
* boot
->FATsecs
;
96 off
*= boot
->BytesPerSec
;
98 if (lseek(fs
, off
, SEEK_SET
) != off
) {
99 perror("Unable to read FAT");
103 if (read(fs
, *buffer
, boot
->FATsecs
* boot
->BytesPerSec
)
104 != boot
->FATsecs
* boot
->BytesPerSec
) {
105 perror("Unable to read FAT");
117 * Read a FAT and decode it into internal format
120 readfat(int fs
, struct bootblock
*boot
, int no
, struct fatEntry
**fp
)
122 struct fatEntry
*fat
;
127 boot
->NumFree
= boot
->NumBad
= 0;
129 if (!_readfat(fs
, boot
, no
, &buffer
))
132 fat
= calloc(boot
->NumClusters
, sizeof(struct fatEntry
));
134 perror("No space for FAT");
139 if (buffer
[0] != boot
->Media
140 || buffer
[1] != 0xff || buffer
[2] != 0xff
141 || (boot
->ClustMask
== CLUST16_MASK
&& buffer
[3] != 0xff)
142 || (boot
->ClustMask
== CLUST32_MASK
143 && ((buffer
[3]&0x0f) != 0x0f
144 || buffer
[4] != 0xff || buffer
[5] != 0xff
145 || buffer
[6] != 0xff || (buffer
[7]&0x0f) != 0x0f))) {
147 /* Windows 95 OSR2 (and possibly any later) changes
148 * the FAT signature to 0xXXffff7f for FAT16 and to
149 * 0xXXffff0fffffff07 for FAT32 upon boot, to know that the
150 * filesystem is dirty if it doesn't reboot cleanly.
151 * Check this special condition before errorring out.
153 if (buffer
[0] == boot
->Media
&& buffer
[1] == 0xff
155 && ((boot
->ClustMask
== CLUST16_MASK
&& buffer
[3] == 0x7f)
156 || (boot
->ClustMask
== CLUST32_MASK
157 && buffer
[3] == 0x0f && buffer
[4] == 0xff
158 && buffer
[5] == 0xff && buffer
[6] == 0xff
159 && buffer
[7] == 0x07)))
162 /* just some odd byte sequence in FAT */
164 switch (boot
->ClustMask
) {
166 pwarn("%s (%02x%02x%02x%02x%02x%02x%02x%02x)\n",
167 "FAT starts with odd byte sequence",
168 buffer
[0], buffer
[1], buffer
[2], buffer
[3],
169 buffer
[4], buffer
[5], buffer
[6], buffer
[7]);
172 pwarn("%s (%02x%02x%02x%02x)\n",
173 "FAT starts with odd byte sequence",
174 buffer
[0], buffer
[1], buffer
[2], buffer
[3]);
177 pwarn("%s (%02x%02x%02x)\n",
178 "FAT starts with odd byte sequence",
179 buffer
[0], buffer
[1], buffer
[2]);
184 if (ask(1, "Correct"))
188 switch (boot
->ClustMask
) {
199 for (cl
= CLUST_FIRST
; cl
< boot
->NumClusters
;) {
200 switch (boot
->ClustMask
) {
202 fat
[cl
].next
= p
[0] + (p
[1] << 8)
203 + (p
[2] << 16) + (p
[3] << 24);
204 fat
[cl
].next
&= boot
->ClustMask
;
205 ret
|= checkclnum(boot
, no
, cl
, &fat
[cl
].next
);
210 fat
[cl
].next
= p
[0] + (p
[1] << 8);
211 ret
|= checkclnum(boot
, no
, cl
, &fat
[cl
].next
);
216 fat
[cl
].next
= (p
[0] + (p
[1] << 8)) & 0x0fff;
217 ret
|= checkclnum(boot
, no
, cl
, &fat
[cl
].next
);
219 if (cl
>= boot
->NumClusters
)
221 fat
[cl
].next
= ((p
[1] >> 4) + (p
[2] << 4)) & 0x0fff;
222 ret
|= checkclnum(boot
, no
, cl
, &fat
[cl
].next
);
235 * Get type of reserved cluster
240 if (cl
== CLUST_FREE
)
250 clustdiffer(cl_t cl
, cl_t
*cp1
, cl_t
*cp2
, int fatnum
)
252 if (*cp1
== CLUST_FREE
|| *cp1
>= CLUST_RSRVD
) {
253 if (*cp2
== CLUST_FREE
|| *cp2
>= CLUST_RSRVD
) {
254 if ((*cp1
!= CLUST_FREE
&& *cp1
< CLUST_BAD
255 && *cp2
!= CLUST_FREE
&& *cp2
< CLUST_BAD
)
256 || (*cp1
> CLUST_BAD
&& *cp2
> CLUST_BAD
)) {
257 pwarn("Cluster %u is marked %s with different indicators, ",
258 cl
, rsrvdcltype(*cp1
));
265 pwarn("Cluster %u is marked %s in FAT 0, %s in FAT %d\n",
266 cl
, rsrvdcltype(*cp1
), rsrvdcltype(*cp2
), fatnum
);
267 if (ask(0, "use FAT 0's entry")) {
271 if (ask(0, "use FAT %d's entry", fatnum
)) {
277 pwarn("Cluster %u is marked %s in FAT 0, but continues with cluster %u in FAT %d\n",
278 cl
, rsrvdcltype(*cp1
), *cp2
, fatnum
);
279 if (ask(0, "Use continuation from FAT %d", fatnum
)) {
283 if (ask(0, "Use mark from FAT 0")) {
289 if (*cp2
== CLUST_FREE
|| *cp2
>= CLUST_RSRVD
) {
290 pwarn("Cluster %u continues with cluster %u in FAT 0, but is marked %s in FAT %d\n",
291 cl
, *cp1
, rsrvdcltype(*cp2
), fatnum
);
292 if (ask(0, "Use continuation from FAT 0")) {
296 if (ask(0, "Use mark from FAT %d", fatnum
)) {
302 pwarn("Cluster %u continues with cluster %u in FAT 0, but with cluster %u in FAT %d\n",
303 cl
, *cp1
, *cp2
, fatnum
);
304 if (ask(0, "Use continuation from FAT 0")) {
308 if (ask(0, "Use continuation from FAT %d", fatnum
)) {
316 * Compare two FAT copies in memory. Resolve any conflicts and merge them
317 * into the first one.
320 comparefat(struct bootblock
*boot
, struct fatEntry
*first
,
321 struct fatEntry
*second
, int fatnum
)
326 for (cl
= CLUST_FIRST
; cl
< boot
->NumClusters
; cl
++)
327 if (first
[cl
].next
!= second
[cl
].next
)
328 ret
|= clustdiffer(cl
, &first
[cl
].next
, &second
[cl
].next
, fatnum
);
333 clearchain(struct bootblock
*boot
, struct fatEntry
*fat
, cl_t head
)
337 for (p
= head
; p
>= CLUST_FIRST
&& p
< boot
->NumClusters
; p
= q
) {
338 if (fat
[p
].head
!= head
)
341 fat
[p
].next
= fat
[p
].head
= CLUST_FREE
;
347 tryclear(struct bootblock
*boot
, struct fatEntry
*fat
, cl_t head
, cl_t
*trunc
)
349 if (ask(0, "Clear chain starting at %u", head
)) {
350 clearchain(boot
, fat
, head
);
352 } else if (ask(0, "Truncate")) {
360 * Check a complete FAT in-memory for crosslinks
363 checkfat(struct bootblock
*boot
, struct fatEntry
*fat
)
371 * pass 1: figure out the cluster chains.
373 for (head
= CLUST_FIRST
; head
< boot
->NumClusters
; head
++) {
374 /* find next untravelled chain */
375 if (fat
[head
].head
!= 0 /* cluster already belongs to some chain */
376 || fat
[head
].next
== CLUST_FREE
377 || fat
[head
].next
== CLUST_BAD
)
378 continue; /* skip it. */
380 /* follow the chain and mark all clusters on the way */
381 for (len
= 0, p
= head
;
382 p
>= CLUST_FIRST
&& p
< boot
->NumClusters
;
388 /* the head record gets the length */
389 fat
[head
].length
= fat
[head
].next
== CLUST_FREE
? 0 : len
;
393 * pass 2: check for crosslinked chains (we couldn't do this in pass 1 because
394 * we didn't know the real start of the chain then - would have treated partial
395 * chains as interlinked with their main chain)
397 for (head
= CLUST_FIRST
; head
< boot
->NumClusters
; head
++) {
398 /* find next untravelled chain */
399 if (fat
[head
].head
!= head
)
402 /* follow the chain to its end (hopefully) */
404 (n
= fat
[p
].next
) >= CLUST_FIRST
&& n
< boot
->NumClusters
;
406 if (fat
[n
].head
!= head
)
411 if (n
== CLUST_FREE
|| n
>= CLUST_RSRVD
) {
412 pwarn("Cluster chain starting at %u ends with cluster marked %s\n",
413 head
, rsrvdcltype(n
));
414 ret
|= tryclear(boot
, fat
, head
, &fat
[p
].next
);
417 if (n
< CLUST_FIRST
|| n
>= boot
->NumClusters
) {
418 pwarn("Cluster chain starting at %u ends with cluster out of range (%u)\n",
420 ret
|= tryclear(boot
, fat
, head
, &fat
[p
].next
);
423 pwarn("Cluster chains starting at %u and %u are linked at cluster %u\n",
424 head
, fat
[n
].head
, n
);
425 conf
= tryclear(boot
, fat
, head
, &fat
[p
].next
);
426 if (ask(0, "Clear chain starting at %u", h
= fat
[n
].head
)) {
427 if (conf
== FSERROR
) {
429 * Transfer the common chain to the one not cleared above.
432 p
>= CLUST_FIRST
&& p
< boot
->NumClusters
;
434 if (h
!= fat
[p
].head
) {
436 * Have to reexamine this chain.
444 clearchain(boot
, fat
, h
);
454 * Write out FATs encoding them from the internal format
457 writefat(int fs
, struct bootblock
*boot
, struct fatEntry
*fat
, int correct_fat
)
466 buffer
= malloc(fatsz
= boot
->FATsecs
* boot
->BytesPerSec
);
467 if (buffer
== NULL
) {
468 perror("No space for FAT");
471 memset(buffer
, 0, fatsz
);
475 *p
++ = (u_char
)boot
->Media
;
478 switch (boot
->ClustMask
) {
491 /* use same FAT signature as the old FAT has */
495 switch (boot
->ClustMask
) {
507 if (!_readfat(fs
, boot
, boot
->ValidFat
>= 0 ? boot
->ValidFat
:0,
513 memcpy(p
, old_fat
, count
);
518 for (cl
= CLUST_FIRST
; cl
< boot
->NumClusters
; cl
++) {
519 switch (boot
->ClustMask
) {
521 if (fat
[cl
].next
== CLUST_FREE
)
523 *p
++ = (u_char
)fat
[cl
].next
;
524 *p
++ = (u_char
)(fat
[cl
].next
>> 8);
525 *p
++ = (u_char
)(fat
[cl
].next
>> 16);
527 *p
++ |= (fat
[cl
].next
>> 24)&0x0f;
530 if (fat
[cl
].next
== CLUST_FREE
)
532 *p
++ = (u_char
)fat
[cl
].next
;
533 *p
++ = (u_char
)(fat
[cl
].next
>> 8);
536 if (fat
[cl
].next
== CLUST_FREE
)
538 if (cl
+ 1 < boot
->NumClusters
539 && fat
[cl
+ 1].next
== CLUST_FREE
)
541 *p
++ = (u_char
)fat
[cl
].next
;
542 *p
++ = (u_char
)((fat
[cl
].next
>> 8) & 0xf)
543 |(u_char
)(fat
[cl
+1].next
<< 4);
544 *p
++ = (u_char
)(fat
[++cl
].next
>> 4);
548 for (i
= 0; i
< boot
->FATs
; i
++) {
549 off
= boot
->ResSectors
+ i
* boot
->FATsecs
;
550 off
*= boot
->BytesPerSec
;
551 if (lseek(fs
, off
, SEEK_SET
) != off
552 || write(fs
, buffer
, fatsz
) != fatsz
) {
553 perror("Unable to write FAT");
554 ret
= FSFATAL
; /* Return immediately? XXX */
562 * Check a complete in-memory FAT for lost cluster chains
565 checklost(int dosfs
, struct bootblock
*boot
, struct fatEntry
*fat
)
571 for (head
= CLUST_FIRST
; head
< boot
->NumClusters
; head
++) {
572 /* find next untravelled chain */
573 if (fat
[head
].head
!= head
574 || fat
[head
].next
== CLUST_FREE
575 || (fat
[head
].next
>= CLUST_RSRVD
576 && fat
[head
].next
< CLUST_EOFS
)
577 || (fat
[head
].flags
& FAT_USED
))
580 pwarn("Lost cluster chain at cluster %u\n%d Cluster(s) lost\n",
581 head
, fat
[head
].length
);
582 mod
|= ret
= reconnect(dosfs
, boot
, fat
, head
);
585 if (ret
== FSERROR
&& ask(0, "Clear")) {
586 clearchain(boot
, fat
, head
);
594 if (boot
->FSFree
!= boot
->NumFree
) {
595 pwarn("Free space in FSInfo block (%d) not correct (%d)\n",
596 boot
->FSFree
, boot
->NumFree
);
598 boot
->FSFree
= boot
->NumFree
;
602 if (boot
->NumFree
&& (boot
->FSNext
>= boot
->NumClusters
||
603 fat
[boot
->FSNext
].next
!= CLUST_FREE
)) {
604 pwarn("Next free cluster in FSInfo block (%u) not free\n",
607 for (head
= CLUST_FIRST
; head
< boot
->NumClusters
; head
++)
608 if (fat
[head
].next
== CLUST_FREE
) {
615 mod
|= writefsinfo(dosfs
, boot
);