87c7fa5f2b64b3842fbe58df88c2cfb1de85a1c0
1 /* fat.c - Read/write access to the FAT
3 Copyright (C) 1993 Werner Almesberger <werner.almesberger@lrc.di.epfl.ch>
4 Copyright (C) 1998 Roman Hodek <Roman.Hodek@informatik.uni-erlangen.de>
5 Copyright (C) 2008-2014 Daniel Baumann <mail@daniel-baumann.ch>
7 This program is free software: you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation, either version 3 of the License, or
10 (at your option) any later version.
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with this program. If not, see <http://www.gnu.org/licenses/>.
20 The complete text of the GNU General Public License
21 can be found in /usr/share/common-licenses/GPL-3 file.
24 /* FAT32, VFAT, Atari format support, and various fixes additions May 1998
25 * by Roman Hodek <Roman.Hodek@informatik.uni-erlangen.de> */
34 * Fetch the FAT entry for a specified cluster.
36 * @param[out] entry Cluster to which cluster of interest is linked
37 * @param[in] fat FAT table for the partition
38 * @param[in] cluster Cluster of interest
39 * @param[in] fs Information from the FAT boot sectors (bits per FAT entry)
41 void get_fat(FAT_ENTRY
* entry
, void *fat
, uint32_t cluster
, DOS_FS
* fs
)
45 if (cluster
> fs
->data_clusters
+ 1) {
46 die("Internal error: cluster out of range in get_fat() (%lu > %lu).",
47 (unsigned long)cluster
, (unsigned long)(fs
->data_clusters
+ 1));
50 switch (fs
->fat_bits
) {
52 ptr
= &((unsigned char *)fat
)[cluster
* 3 / 2];
53 entry
->value
= 0xfff & (cluster
& 1 ? (ptr
[0] >> 4) | (ptr
[1] << 4) :
54 (ptr
[0] | ptr
[1] << 8));
57 entry
->value
= le16toh(((unsigned short *)fat
)[cluster
]);
60 /* According to M$, the high 4 bits of a FAT32 entry are reserved and
61 * are not part of the cluster number. So we cut them off. */
63 uint32_t e
= le32toh(((unsigned int *)fat
)[cluster
]);
64 entry
->value
= e
& 0xfffffff;
65 entry
->reserved
= e
>> 28;
69 die("Bad FAT entry size: %d bits.", fs
->fat_bits
);
74 * Build a bookkeeping structure from the partition's FAT table.
75 * If the partition has multiple FATs and they don't agree, try to pick a winner,
76 * and queue a command to overwrite the loser.
77 * One error that is fixed here is a cluster that links to something out of range.
79 * @param[inout] fs Information about the filesystem
81 void read_fat(DOS_FS
* fs
)
83 int eff_size
, alloc_size
;
85 void *first
, *second
= NULL
;
86 int first_ok
, second_ok
;
87 uint32_t total_num_clusters
;
89 /* Clean up from previous pass */
92 if (fs
->cluster_owner
)
93 free(fs
->cluster_owner
);
95 fs
->cluster_owner
= NULL
;
97 total_num_clusters
= fs
->data_clusters
+ 2;
98 eff_size
= (total_num_clusters
* fs
->fat_bits
+ 7) / 8ULL;
100 if (fs
->fat_bits
!= 12)
101 alloc_size
= eff_size
;
103 /* round up to an even number of FAT entries to avoid special
104 * casing the last entry in get_fat() */
105 alloc_size
= (total_num_clusters
* 12 + 23) / 24 * 3;
107 first
= alloc(alloc_size
);
108 fs_read(fs
->fat_start
, eff_size
, first
);
110 second
= alloc(alloc_size
);
111 fs_read(fs
->fat_start
+ fs
->fat_size
, eff_size
, second
);
113 if (second
&& memcmp(first
, second
, eff_size
) != 0) {
114 FAT_ENTRY first_media
, second_media
;
115 get_fat(&first_media
, first
, 0, fs
);
116 get_fat(&second_media
, second
, 0, fs
);
117 first_ok
= (first_media
.value
& FAT_EXTD(fs
)) == FAT_EXTD(fs
);
118 second_ok
= (second_media
.value
& FAT_EXTD(fs
)) == FAT_EXTD(fs
);
119 if (first_ok
&& !second_ok
) {
120 printf("FATs differ - using first FAT.\n");
121 fs_write(fs
->fat_start
+ fs
->fat_size
, eff_size
, first
);
123 if (!first_ok
&& second_ok
) {
124 printf("FATs differ - using second FAT.\n");
125 fs_write(fs
->fat_start
, eff_size
, second
);
126 memcpy(first
, second
, eff_size
);
128 if (first_ok
&& second_ok
) {
130 printf("FATs differ but appear to be intact. Use which FAT ?\n"
131 "1) Use first FAT\n2) Use second FAT\n");
132 if (get_key("12", "?") == '1') {
133 fs_write(fs
->fat_start
+ fs
->fat_size
, eff_size
, first
);
135 fs_write(fs
->fat_start
, eff_size
, second
);
136 memcpy(first
, second
, eff_size
);
139 printf("FATs differ but appear to be intact. Using first "
141 fs_write(fs
->fat_start
+ fs
->fat_size
, eff_size
, first
);
144 if (!first_ok
&& !second_ok
) {
145 printf("Both FATs appear to be corrupt. Giving up.\n");
152 fs
->fat
= (unsigned char *)first
;
154 fs
->cluster_owner
= alloc(total_num_clusters
* sizeof(DOS_FILE
*));
155 memset(fs
->cluster_owner
, 0, (total_num_clusters
* sizeof(DOS_FILE
*)));
157 /* Truncate any cluster chains that link to something out of range */
158 for (i
= 2; i
< fs
->data_clusters
+ 2; i
++) {
160 get_fat(&curEntry
, fs
->fat
, i
, fs
);
161 if (curEntry
.value
== 1) {
162 printf("Cluster %ld out of range (1). Setting to EOF.\n",
166 if (curEntry
.value
>= fs
->data_clusters
+ 2 &&
167 (curEntry
.value
< FAT_MIN_BAD(fs
))) {
168 printf("Cluster %ld out of range (%ld > %ld). Setting to EOF.\n",
169 (long)(i
- 2), (long)curEntry
.value
,
170 (long)(fs
->data_clusters
+ 2 - 1));
177 * Update the FAT entry for a specified cluster
178 * (i.e., change the cluster it links to).
179 * Queue a command to write out this change.
181 * @param[in,out] fs Information about the filesystem
182 * @param[in] cluster Cluster to change
183 * @param[in] new Cluster to link to
189 void set_fat(DOS_FS
* fs
, uint32_t cluster
, int32_t new)
191 unsigned char *data
= NULL
;
195 if (cluster
> fs
->data_clusters
+ 1) {
196 die("Internal error: cluster out of range in set_fat() (%lu > %lu).",
197 (unsigned long)cluster
, (unsigned long)(fs
->data_clusters
+ 1));
202 else if ((long)new == -2)
204 else if (new > fs
->data_clusters
+ 1) {
205 die("Internal error: new cluster out of range in set_fat() (%lu > %lu).",
206 (unsigned long)new, (unsigned long)(fs
->data_clusters
+ 1));
209 switch (fs
->fat_bits
) {
211 data
= fs
->fat
+ cluster
* 3 / 2;
212 offs
= fs
->fat_start
+ cluster
* 3 / 2;
215 get_fat(&prevEntry
, fs
->fat
, cluster
- 1, fs
);
216 data
[0] = ((new & 0xf) << 4) | (prevEntry
.value
>> 8);
219 FAT_ENTRY subseqEntry
;
220 if (cluster
!= fs
->data_clusters
+ 1)
221 get_fat(&subseqEntry
, fs
->fat
, cluster
+ 1, fs
);
223 subseqEntry
.value
= 0;
224 data
[0] = new & 0xff;
225 data
[1] = (new >> 8) | ((0xff & subseqEntry
.value
) << 4);
230 data
= fs
->fat
+ cluster
* 2;
231 offs
= fs
->fat_start
+ cluster
* 2;
232 *(unsigned short *)data
= htole16(new);
238 get_fat(&curEntry
, fs
->fat
, cluster
, fs
);
240 data
= fs
->fat
+ cluster
* 4;
241 offs
= fs
->fat_start
+ cluster
* 4;
242 /* According to M$, the high 4 bits of a FAT32 entry are reserved and
243 * are not part of the cluster number. So we never touch them. */
244 *(uint32_t *)data
= htole32((new & 0xfffffff) |
245 (curEntry
.reserved
<< 28));
250 die("Bad FAT entry size: %d bits.", fs
->fat_bits
);
252 fs_write(offs
, size
, data
);
254 fs_write(offs
+ fs
->fat_size
, size
, data
);
258 int bad_cluster(DOS_FS
* fs
, uint32_t cluster
)
261 get_fat(&curEntry
, fs
->fat
, cluster
, fs
);
263 return FAT_IS_BAD(fs
, curEntry
.value
);
267 * Get the cluster to which the specified cluster is linked.
268 * If the linked cluster is marked bad, abort.
270 * @param[in] fs Information about the filesystem
271 * @param[in] cluster Cluster to follow
273 * @return -1 'cluster' is at the end of the chain
274 * @return Other values Next cluster in this chain
276 uint32_t next_cluster(DOS_FS
* fs
, uint32_t cluster
)
281 get_fat(&curEntry
, fs
->fat
, cluster
, fs
);
283 value
= curEntry
.value
;
284 if (FAT_IS_BAD(fs
, value
))
285 die("Internal error: next_cluster on bad cluster");
286 return FAT_IS_EOF(fs
, value
) ? -1 : value
;
289 off_t
cluster_start(DOS_FS
* fs
, uint32_t cluster
)
291 return fs
->data_start
+ ((off_t
)cluster
- 2) * (uint64_t)fs
->cluster_size
;
295 * Update internal bookkeeping to show that the specified cluster belongs
296 * to the specified dentry.
298 * @param[in,out] fs Information about the filesystem
299 * @param[in] cluster Cluster being assigned
300 * @param[in] owner Information on dentry that owns this cluster
303 void set_owner(DOS_FS
* fs
, uint32_t cluster
, DOS_FILE
* owner
)
305 if (fs
->cluster_owner
== NULL
)
306 die("Internal error: attempt to set owner in non-existent table");
308 if (owner
&& fs
->cluster_owner
[cluster
]
309 && (fs
->cluster_owner
[cluster
] != owner
))
310 die("Internal error: attempt to change file owner");
311 fs
->cluster_owner
[cluster
] = owner
;
314 DOS_FILE
*get_owner(DOS_FS
* fs
, uint32_t cluster
)
316 if (fs
->cluster_owner
== NULL
)
319 return fs
->cluster_owner
[cluster
];
322 void fix_bad(DOS_FS
* fs
)
327 printf("Checking for bad clusters.\n");
328 for (i
= 2; i
< fs
->data_clusters
+ 2; i
++) {
330 get_fat(&curEntry
, fs
->fat
, i
, fs
);
332 if (!get_owner(fs
, i
) && !FAT_IS_BAD(fs
, curEntry
.value
))
333 if (!fs_test(cluster_start(fs
, i
), fs
->cluster_size
)) {
334 printf("Cluster %lu is unreadable.\n", (unsigned long)i
);
340 void reclaim_free(DOS_FS
* fs
)
346 printf("Checking for unused clusters.\n");
348 for (i
= 2; i
< fs
->data_clusters
+ 2; i
++) {
350 get_fat(&curEntry
, fs
->fat
, i
, fs
);
352 if (!get_owner(fs
, i
) && curEntry
.value
&&
353 !FAT_IS_BAD(fs
, curEntry
.value
)) {
359 printf("Reclaimed %d unused cluster%s (%llu bytes).\n", (int)reclaimed
,
360 reclaimed
== 1 ? "" : "s",
361 (unsigned long long)reclaimed
* fs
->cluster_size
);
365 * Assign the specified owner to all orphan chains (except cycles).
366 * Break cross-links between orphan chains.
368 * @param[in,out] fs Information about the filesystem
369 * @param[in] owner dentry to be assigned ownership of orphans
370 * @param[in,out] num_refs For each orphan cluster [index], how many
371 * clusters link to it.
372 * @param[in] start_cluster Where to start scanning for orphans
374 static void tag_free(DOS_FS
* fs
, DOS_FILE
* owner
, uint32_t *num_refs
,
375 uint32_t start_cluster
)
380 if (start_cluster
== 0)
383 for (i
= start_cluster
; i
< fs
->data_clusters
+ 2; i
++) {
385 get_fat(&curEntry
, fs
->fat
, i
, fs
);
387 /* If the current entry is the head of an un-owned chain... */
388 if (curEntry
.value
&& !FAT_IS_BAD(fs
, curEntry
.value
) &&
389 !get_owner(fs
, i
) && !num_refs
[i
]) {
391 /* Walk the chain, claiming ownership as we go */
392 for (walk
= i
; walk
!= -1; walk
= next_cluster(fs
, walk
)) {
393 if (!get_owner(fs
, walk
)) {
394 set_owner(fs
, walk
, owner
);
396 /* We've run into cross-links between orphaned chains,
397 * or a cycle with a tail.
398 * Terminate this orphan chain (break the link)
400 set_fat(fs
, prev
, -1);
402 /* This is not necessary because 'walk' is owned and thus
403 * will never become the head of a chain (the only case
404 * that would matter during reclaim to files).
405 * It's easier to decrement than to prove that it's
418 * Recover orphan chains to files, handling any cycles or cross-links.
420 * @param[in,out] fs Information about the filesystem
422 void reclaim_file(DOS_FS
* fs
)
425 int reclaimed
, files
;
427 uint32_t i
, next
, walk
;
428 uint32_t *num_refs
= NULL
; /* Only for orphaned clusters */
429 uint32_t total_num_clusters
;
432 printf("Reclaiming unconnected clusters.\n");
434 total_num_clusters
= fs
->data_clusters
+ 2;
435 num_refs
= alloc(total_num_clusters
* sizeof(uint32_t));
436 memset(num_refs
, 0, (total_num_clusters
* sizeof(uint32_t)));
438 /* Guarantee that all orphan chains (except cycles) end cleanly
439 * with an end-of-chain mark.
442 for (i
= 2; i
< total_num_clusters
; i
++) {
444 get_fat(&curEntry
, fs
->fat
, i
, fs
);
446 next
= curEntry
.value
;
447 if (!get_owner(fs
, i
) && next
&& next
< fs
->data_clusters
+ 2) {
448 /* Cluster is linked, but not owned (orphan) */
450 get_fat(&nextEntry
, fs
->fat
, next
, fs
);
452 /* Mark it end-of-chain if it links into an owned cluster,
453 * a free cluster, or a bad cluster.
455 if (get_owner(fs
, next
) || !nextEntry
.value
||
456 FAT_IS_BAD(fs
, nextEntry
.value
))
463 /* Scan until all the orphans are accounted for,
464 * and all cycles and cross-links are broken
467 tag_free(fs
, &orphan
, num_refs
, changed
);
470 /* Any unaccounted-for orphans must be part of a cycle */
471 for (i
= 2; i
< total_num_clusters
; i
++) {
473 get_fat(&curEntry
, fs
->fat
, i
, fs
);
475 if (curEntry
.value
&& !FAT_IS_BAD(fs
, curEntry
.value
) &&
477 if (!num_refs
[curEntry
.value
]--)
478 die("Internal error: num_refs going below zero");
480 changed
= curEntry
.value
;
481 printf("Broke cycle at cluster %lu in free chain.\n", (unsigned long)i
);
483 /* If we've created a new chain head,
484 * tag_free() can claim it
486 if (num_refs
[curEntry
.value
] == 0)
493 /* Now we can start recovery */
494 files
= reclaimed
= 0;
495 for (i
= 2; i
< total_num_clusters
; i
++)
496 /* If this cluster is the head of an orphan chain... */
497 if (get_owner(fs
, i
) == &orphan
&& !num_refs
[i
]) {
501 offset
= alloc_rootdir_entry(fs
, &de
, "FSCK%04dREC");
502 de
.start
= htole16(i
& 0xffff);
503 if (fs
->fat_bits
== 32)
504 de
.starthi
= htole16(i
>> 16);
505 for (walk
= i
; walk
> 0 && walk
!= -1;
506 walk
= next_cluster(fs
, walk
)) {
507 de
.size
= htole32(le32toh(de
.size
) + fs
->cluster_size
);
510 fs_write(offset
, sizeof(DIR_ENT
), &de
);
513 printf("Reclaimed %d unused cluster%s (%llu bytes) in %d chain%s.\n",
514 reclaimed
, reclaimed
== 1 ? "" : "s",
515 (unsigned long long)reclaimed
* fs
->cluster_size
, files
,
516 files
== 1 ? "" : "s");
521 uint32_t update_free(DOS_FS
* fs
)
527 for (i
= 2; i
< fs
->data_clusters
+ 2; i
++) {
529 get_fat(&curEntry
, fs
->fat
, i
, fs
);
531 if (!get_owner(fs
, i
) && !FAT_IS_BAD(fs
, curEntry
.value
))
535 if (!fs
->fsinfo_start
)
539 printf("Checking free cluster summary.\n");
540 if (fs
->free_clusters
!= 0xFFFFFFFF) {
541 if (free
!= fs
->free_clusters
) {
542 printf("Free cluster summary wrong (%ld vs. really %ld)\n",
543 (long)fs
->free_clusters
, (long)free
);
545 printf("1) Correct\n2) Don't correct\n");
547 printf(" Auto-correcting.\n");
548 if (!interactive
|| get_key("12", "?") == '1')
552 printf("Free cluster summary uninitialized (should be %ld)\n", (long)free
);
555 printf("1) Set it\n2) Leave it uninitialized\n");
557 printf(" Auto-setting.\n");
558 if (!interactive
|| get_key("12", "?") == '1')
564 uint32_t le_free
= htole32(free
);
565 fs
->free_clusters
= free
;
566 fs_write(fs
->fsinfo_start
+ offsetof(struct info_sector
, free_clusters
),
567 sizeof(le_free
), &le_free
);