1 /* fat.c - Read/write access to the FAT
2
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>
6
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.
11
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.
16
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/>.
19
20 The complete text of the GNU General Public License
21 can be found in /usr/share/common-licenses/GPL-3 file.
22 */
23
24 /* FAT32, VFAT, Atari format support, and various fixes additions May 1998
25 * by Roman Hodek <Roman.Hodek@informatik.uni-erlangen.de> */
26
27 #include "vfatlib.h"
28
29 #define NDEBUG
30 #include <debug.h>
31
32
33 /**
34 * Fetch the FAT entry for a specified cluster.
35 *
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)
40 */
get_fat(FAT_ENTRY * entry,void * fat,uint32_t cluster,DOS_FS * fs)41 void get_fat(FAT_ENTRY * entry, void *fat, uint32_t cluster, DOS_FS * fs)
42 {
43 unsigned char *ptr;
44
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));
48 }
49
50 switch (fs->fat_bits) {
51 case 12:
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));
55 break;
56 case 16:
57 entry->value = le16toh(((unsigned short *)fat)[cluster]);
58 break;
59 case 32:
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. */
62 {
63 uint32_t e = le32toh(((unsigned int *)fat)[cluster]);
64 entry->value = e & 0xfffffff;
65 entry->reserved = e >> 28;
66 }
67 break;
68 default:
69 die("Bad FAT entry size: %d bits.", fs->fat_bits);
70 }
71 }
72
73 /**
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.
78 *
79 * @param[inout] fs Information about the filesystem
80 */
read_fat(DOS_FS * fs)81 void read_fat(DOS_FS * fs)
82 {
83 int eff_size, alloc_size;
84 uint32_t i;
85 void *first, *second = NULL;
86 int first_ok, second_ok;
87 uint32_t total_num_clusters;
88
89 /* Clean up from previous pass */
90 if (fs->fat)
91 free(fs->fat);
92 if (fs->cluster_owner)
93 free(fs->cluster_owner);
94 fs->fat = NULL;
95 fs->cluster_owner = NULL;
96
97 total_num_clusters = fs->data_clusters + 2;
98 eff_size = (total_num_clusters * fs->fat_bits + 7) / 8ULL;
99
100 if (fs->fat_bits != 12)
101 alloc_size = eff_size;
102 else
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;
106
107 first = alloc(alloc_size);
108 fs_read(fs->fat_start, eff_size, first);
109 if (fs->nfats > 1) {
110 second = alloc(alloc_size);
111 fs_read(fs->fat_start + fs->fat_size, eff_size, second);
112 }
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);
122 }
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);
127 }
128 if (first_ok && second_ok) {
129 if (interactive) {
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);
134 } else {
135 fs_write(fs->fat_start, eff_size, second);
136 memcpy(first, second, eff_size);
137 }
138 } else {
139 printf("FATs differ but appear to be intact. Using first "
140 "FAT.\n");
141 fs_write(fs->fat_start + fs->fat_size, eff_size, first);
142 }
143 }
144 if (!first_ok && !second_ok) {
145 printf("Both FATs appear to be corrupt. Giving up.\n");
146 exit(1);
147 }
148 }
149 if (second) {
150 free(second);
151 }
152 fs->fat = (unsigned char *)first;
153
154 fs->cluster_owner = alloc(total_num_clusters * sizeof(DOS_FILE *));
155 memset(fs->cluster_owner, 0, (total_num_clusters * sizeof(DOS_FILE *)));
156
157 /* Truncate any cluster chains that link to something out of range */
158 for (i = 2; i < fs->data_clusters + 2; i++) {
159 FAT_ENTRY curEntry;
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",
163 (long)(i - 2));
164 set_fat(fs, i, -1);
165 }
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));
171 set_fat(fs, i, -1);
172 }
173 }
174 }
175
176 /**
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.
180 *
181 * @param[in,out] fs Information about the filesystem
182 * @param[in] cluster Cluster to change
183 * @param[in] new Cluster to link to
184 * Special values:
185 * 0 == free cluster
186 * -1 == end-of-chain
187 * -2 == bad cluster
188 */
set_fat(DOS_FS * fs,uint32_t cluster,int32_t new)189 void set_fat(DOS_FS * fs, uint32_t cluster, int32_t new)
190 {
191 unsigned char *data = NULL;
192 int size;
193 off_t offs;
194
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));
198 }
199
200 if (new == -1)
201 new = FAT_EOF(fs);
202 else if ((long)new == -2)
203 new = FAT_BAD(fs);
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));
207 }
208
209 switch (fs->fat_bits) {
210 case 12:
211 data = fs->fat + cluster * 3 / 2;
212 offs = fs->fat_start + cluster * 3 / 2;
213 if (cluster & 1) {
214 FAT_ENTRY prevEntry;
215 get_fat(&prevEntry, fs->fat, cluster - 1, fs);
216 data[0] = ((new & 0xf) << 4) | (prevEntry.value >> 8);
217 data[1] = new >> 4;
218 } else {
219 FAT_ENTRY subseqEntry;
220 if (cluster != fs->data_clusters + 1)
221 get_fat(&subseqEntry, fs->fat, cluster + 1, fs);
222 else
223 subseqEntry.value = 0;
224 data[0] = new & 0xff;
225 data[1] = (new >> 8) | ((0xff & subseqEntry.value) << 4);
226 }
227 size = 2;
228 break;
229 case 16:
230 data = fs->fat + cluster * 2;
231 offs = fs->fat_start + cluster * 2;
232 *(unsigned short *)data = htole16(new);
233 size = 2;
234 break;
235 case 32:
236 {
237 FAT_ENTRY curEntry;
238 get_fat(&curEntry, fs->fat, cluster, fs);
239
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));
246 size = 4;
247 }
248 break;
249 default:
250 die("Bad FAT entry size: %d bits.", fs->fat_bits);
251 }
252 fs_write(offs, size, data);
253 if (fs->nfats > 1) {
254 fs_write(offs + fs->fat_size, size, data);
255 }
256 }
257
bad_cluster(DOS_FS * fs,uint32_t cluster)258 int bad_cluster(DOS_FS * fs, uint32_t cluster)
259 {
260 FAT_ENTRY curEntry;
261 get_fat(&curEntry, fs->fat, cluster, fs);
262
263 return FAT_IS_BAD(fs, curEntry.value);
264 }
265
266 /**
267 * Get the cluster to which the specified cluster is linked.
268 * If the linked cluster is marked bad, abort.
269 *
270 * @param[in] fs Information about the filesystem
271 * @param[in] cluster Cluster to follow
272 *
273 * @return -1 'cluster' is at the end of the chain
274 * @return Other values Next cluster in this chain
275 */
next_cluster(DOS_FS * fs,uint32_t cluster)276 uint32_t next_cluster(DOS_FS * fs, uint32_t cluster)
277 {
278 uint32_t value;
279 FAT_ENTRY curEntry;
280
281 get_fat(&curEntry, fs->fat, cluster, fs);
282
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;
287 }
288
cluster_start(DOS_FS * fs,uint32_t cluster)289 off_t cluster_start(DOS_FS * fs, uint32_t cluster)
290 {
291 return fs->data_start + ((off_t)cluster - 2) * (uint64_t)fs->cluster_size;
292 }
293
294 /**
295 * Update internal bookkeeping to show that the specified cluster belongs
296 * to the specified dentry.
297 *
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
301 * (may be NULL)
302 */
set_owner(DOS_FS * fs,uint32_t cluster,DOS_FILE * owner)303 void set_owner(DOS_FS * fs, uint32_t cluster, DOS_FILE * owner)
304 {
305 if (fs->cluster_owner == NULL)
306 die("Internal error: attempt to set owner in non-existent table");
307
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;
312 }
313
get_owner(DOS_FS * fs,uint32_t cluster)314 DOS_FILE *get_owner(DOS_FS * fs, uint32_t cluster)
315 {
316 if (fs->cluster_owner == NULL)
317 return NULL;
318 else
319 return fs->cluster_owner[cluster];
320 }
321
fix_bad(DOS_FS * fs)322 void fix_bad(DOS_FS * fs)
323 {
324 uint32_t i;
325
326 if (verbose)
327 printf("Checking for bad clusters.\n");
328 for (i = 2; i < fs->data_clusters + 2; i++) {
329 FAT_ENTRY curEntry;
330 get_fat(&curEntry, fs->fat, i, fs);
331
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);
335 set_fat(fs, i, -2);
336 }
337 }
338 }
339
reclaim_free(DOS_FS * fs)340 void reclaim_free(DOS_FS * fs)
341 {
342 int reclaimed;
343 uint32_t i;
344
345 if (verbose)
346 printf("Checking for unused clusters.\n");
347 reclaimed = 0;
348 for (i = 2; i < fs->data_clusters + 2; i++) {
349 FAT_ENTRY curEntry;
350 get_fat(&curEntry, fs->fat, i, fs);
351
352 if (!get_owner(fs, i) && curEntry.value &&
353 #ifndef __REACTOS__
354 !FAT_IS_BAD(fs, curEntry.value)) {
355 #else
356 !FAT_IS_BAD(fs, curEntry.value) && rw) {
357 #endif
358 set_fat(fs, i, 0);
359 reclaimed++;
360 }
361 }
362 if (reclaimed)
363 printf("Reclaimed %d unused cluster%s (%llu bytes).\n", (int)reclaimed,
364 reclaimed == 1 ? "" : "s",
365 (unsigned long long)reclaimed * fs->cluster_size);
366 }
367
368 /**
369 * Assign the specified owner to all orphan chains (except cycles).
370 * Break cross-links between orphan chains.
371 *
372 * @param[in,out] fs Information about the filesystem
373 * @param[in] owner dentry to be assigned ownership of orphans
374 * @param[in,out] num_refs For each orphan cluster [index], how many
375 * clusters link to it.
376 * @param[in] start_cluster Where to start scanning for orphans
377 */
378 static void tag_free(DOS_FS * fs, DOS_FILE * owner, uint32_t *num_refs,
379 uint32_t start_cluster)
380 {
381 int prev;
382 uint32_t i, walk;
383
384 if (start_cluster == 0)
385 start_cluster = 2;
386
387 for (i = start_cluster; i < fs->data_clusters + 2; i++) {
388 FAT_ENTRY curEntry;
389 get_fat(&curEntry, fs->fat, i, fs);
390
391 /* If the current entry is the head of an un-owned chain... */
392 if (curEntry.value && !FAT_IS_BAD(fs, curEntry.value) &&
393 !get_owner(fs, i) && !num_refs[i]) {
394 prev = 0;
395 /* Walk the chain, claiming ownership as we go */
396 for (walk = i; walk != -1; walk = next_cluster(fs, walk)) {
397 if (!get_owner(fs, walk)) {
398 set_owner(fs, walk, owner);
399 } else {
400 /* We've run into cross-links between orphaned chains,
401 * or a cycle with a tail.
402 * Terminate this orphan chain (break the link)
403 */
404 set_fat(fs, prev, -1);
405
406 /* This is not necessary because 'walk' is owned and thus
407 * will never become the head of a chain (the only case
408 * that would matter during reclaim to files).
409 * It's easier to decrement than to prove that it's
410 * unnecessary.
411 */
412 num_refs[walk]--;
413 break;
414 }
415 prev = walk;
416 }
417 }
418 }
419 }
420
421 /**
422 * Recover orphan chains to files, handling any cycles or cross-links.
423 *
424 * @param[in,out] fs Information about the filesystem
425 */
426 void reclaim_file(DOS_FS * fs)
427 {
428 DOS_FILE orphan;
429 int reclaimed, files;
430 int changed = 0;
431 uint32_t i, next, walk;
432 uint32_t *num_refs = NULL; /* Only for orphaned clusters */
433 uint32_t total_num_clusters;
434
435 if (verbose)
436 printf("Reclaiming unconnected clusters.\n");
437
438 total_num_clusters = fs->data_clusters + 2;
439 num_refs = alloc(total_num_clusters * sizeof(uint32_t));
440 memset(num_refs, 0, (total_num_clusters * sizeof(uint32_t)));
441
442 /* Guarantee that all orphan chains (except cycles) end cleanly
443 * with an end-of-chain mark.
444 */
445
446 for (i = 2; i < total_num_clusters; i++) {
447 FAT_ENTRY curEntry;
448 get_fat(&curEntry, fs->fat, i, fs);
449
450 next = curEntry.value;
451 if (!get_owner(fs, i) && next && next < fs->data_clusters + 2) {
452 /* Cluster is linked, but not owned (orphan) */
453 FAT_ENTRY nextEntry;
454 get_fat(&nextEntry, fs->fat, next, fs);
455
456 /* Mark it end-of-chain if it links into an owned cluster,
457 * a free cluster, or a bad cluster.
458 */
459 if (get_owner(fs, next) || !nextEntry.value ||
460 FAT_IS_BAD(fs, nextEntry.value))
461 set_fat(fs, i, -1);
462 else
463 num_refs[next]++;
464 }
465 }
466
467 /* Scan until all the orphans are accounted for,
468 * and all cycles and cross-links are broken
469 */
470 do {
471 tag_free(fs, &orphan, num_refs, changed);
472 changed = 0;
473
474 /* Any unaccounted-for orphans must be part of a cycle */
475 for (i = 2; i < total_num_clusters; i++) {
476 FAT_ENTRY curEntry;
477 get_fat(&curEntry, fs->fat, i, fs);
478
479 if (curEntry.value && !FAT_IS_BAD(fs, curEntry.value) &&
480 !get_owner(fs, i)) {
481 if (!num_refs[curEntry.value]--)
482 die("Internal error: num_refs going below zero");
483 set_fat(fs, i, -1);
484 changed = curEntry.value;
485 printf("Broke cycle at cluster %lu in free chain.\n", (unsigned long)i);
486
487 /* If we've created a new chain head,
488 * tag_free() can claim it
489 */
490 if (num_refs[curEntry.value] == 0)
491 break;
492 }
493 }
494 }
495 while (changed);
496
497 #ifdef __REACTOS__
498 if (rw) {
499 #endif
500 /* Now we can start recovery */
501 files = reclaimed = 0;
502 for (i = 2; i < total_num_clusters; i++)
503 /* If this cluster is the head of an orphan chain... */
504 if (get_owner(fs, i) == &orphan && !num_refs[i]) {
505 DIR_ENT de;
506 off_t offset;
507 files++;
508 offset = alloc_rootdir_entry(fs, &de, "FSCK%04dREC", 1);
509 de.start = htole16(i & 0xffff);
510 if (fs->fat_bits == 32)
511 de.starthi = htole16(i >> 16);
512 for (walk = i; walk > 0 && walk != -1;
513 walk = next_cluster(fs, walk)) {
514 de.size = htole32(le32toh(de.size) + fs->cluster_size);
515 reclaimed++;
516 }
517 fs_write(offset, sizeof(DIR_ENT), &de);
518 }
519 if (reclaimed)
520 printf("Reclaimed %d unused cluster%s (%llu bytes) in %d chain%s.\n",
521 reclaimed, reclaimed == 1 ? "" : "s",
522 (unsigned long long)reclaimed * fs->cluster_size, files,
523 files == 1 ? "" : "s");
524 #ifdef __REACTOS__
525 }
526 #endif
527
528 free(num_refs);
529 }
530
531 uint32_t update_free(DOS_FS * fs)
532 {
533 uint32_t i;
534 uint32_t free = 0;
535 int do_set = 0;
536
537 for (i = 2; i < fs->data_clusters + 2; i++) {
538 FAT_ENTRY curEntry;
539 get_fat(&curEntry, fs->fat, i, fs);
540
541 if (!get_owner(fs, i) && !FAT_IS_BAD(fs, curEntry.value))
542 ++free;
543 }
544
545 if (!fs->fsinfo_start)
546 return free;
547
548 if (verbose)
549 printf("Checking free cluster summary.\n");
550 if (fs->free_clusters != 0xFFFFFFFF) {
551 if (free != fs->free_clusters) {
552 printf("Free cluster summary wrong (%ld vs. really %ld)\n",
553 (long)fs->free_clusters, (long)free);
554 if (interactive)
555 printf("1) Correct\n2) Don't correct\n");
556 else
557 #ifdef __REACTOS__
558 if (rw)
559 #endif
560 printf(" Auto-correcting.\n");
561 #ifndef __REACTOS__
562 if (!interactive || get_key("12", "?") == '1')
563 #else
564 if ((!interactive && rw) || (interactive && get_key("12", "?") == '1'))
565 #endif
566 do_set = 1;
567 }
568 } else {
569 printf("Free cluster summary uninitialized (should be %ld)\n", (long)free);
570 if (rw) {
571 if (interactive)
572 printf("1) Set it\n2) Leave it uninitialized\n");
573 else
574 printf(" Auto-setting.\n");
575 if (!interactive || get_key("12", "?") == '1')
576 do_set = 1;
577 }
578 }
579
580 if (do_set) {
581 uint32_t le_free = htole32(free);
582 fs->free_clusters = free;
583 fs_write(fs->fsinfo_start + offsetof(struct info_sector, free_clusters),
584 sizeof(le_free), &le_free);
585 }
586
587 return free;
588 }
589