ReactOS  0.4.12-dev-375-g61fed54
fat.c
Go to the documentation of this file.
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 
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 
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 
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 
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 
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 
290 {
291  return fs->data_start + ((off_t)cluster - 2) * (uint64_t)fs->cluster_size;
292 }
293 
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 
315 {
316  if (fs->cluster_owner == NULL)
317  return NULL;
318  else
319  return fs->cluster_owner[cluster];
320 }
321 
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 
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 
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 
427 {
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 
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 }
DOS_FILE * get_owner(DOS_FS *fs, uint32_t cluster)
Definition: fat.c:314
off_t alloc_rootdir_entry(DOS_FS *fs, DIR_ENT *de, const char *pattern, int gen_name)
Definition: check.c:74
Definition: get.c:139
int memcmp(void *Buffer1, void *Buffer2, ACPI_SIZE Count)
Definition: utclib.c:112
Definition: send.c:33
#define free
Definition: debug_ros.c:5
#define FAT_IS_BAD(fs, v)
Definition: fsck.fat.h:232
__kernel_off_t off_t
Definition: linux.h:201
const GLint * first
Definition: glext.h:5794
uint8_t entry
Definition: isohybrid.c:63
GLintptr offset
Definition: glext.h:5920
void set_fat(DOS_FS *fs, uint32_t cluster, int32_t new)
Definition: fat.c:189
void read_fat(DOS_FS *fs)
Definition: fat.c:81
#define htole16(x)
Definition: storage32.h:546
static void tag_free(DOS_FS *fs, DOS_FILE *owner, uint32_t *num_refs, uint32_t start_cluster)
Definition: fat.c:378
#define interactive
Definition: rosglue.h:34
Definition: fs.h:235
void fs_write(off_t pos, int size, void *data)
Definition: io.c:344
#define FAT_IS_EOF(fs, v)
Definition: fsck.fat.h:226
#define verbose
Definition: rosglue.h:36
int fs_test(off_t pos, int size)
Definition: io.c:322
GLenum GLclampf GLint i
Definition: glfuncs.h:14
#define e
Definition: ke_i.h:82
static PVOID ptr
Definition: dispmode.c:27
#define FAT_MIN_BAD(fs)
Definition: fsck.fat.h:230
smooth NULL
Definition: ftsmooth.c:416
#define offsetof(TYPE, MEMBER)
#define htole32(x)
Definition: storage32.h:543
#define off_t
Definition: dosfsck.h:5
#define ULL(a, b)
Definition: format_msg.c:27
uint32_t next_cluster(DOS_FS *fs, uint32_t cluster)
Definition: fat.c:276
GLsizeiptr size
Definition: glext.h:5919
char get_key(const char *valid, const char *prompt)
Definition: common.c:184
#define FAT_EOF
Definition: mkdosfs.c:378
void fs_read(off_t pos, int size, void *data)
Definition: io.c:282
void set_owner(DOS_FS *fs, uint32_t cluster, DOS_FILE *owner)
Definition: fat.c:303
GLint GLenum GLsizei GLsizei GLsizei GLint GLsizei const GLvoid * data
Definition: gl.h:1950
int rw
Definition: fsck.fat.h:192
#define memcpy(s1, s2, n)
Definition: mkisofs.h:878
#define FAT_BAD
Definition: mkdosfs.c:379
GLsizei const GLfloat * value
Definition: glext.h:6069
#define uint64_t
Definition: nsiface.idl:62
INT32 int32_t
Definition: types.h:71
void fix_bad(DOS_FS *fs)
Definition: fat.c:322
int bad_cluster(DOS_FS *fs, uint32_t cluster)
Definition: fat.c:258
static unsigned __int64 next
Definition: rand_nt.c:6
uint32_t reserved
Definition: fsck.fat.h:194
uint32_t value
Definition: fsck.fat.h:193
#define alloc
Definition: rosglue.h:13
UINT32 uint32_t
Definition: types.h:75
off_t cluster_start(DOS_FS *fs, uint32_t cluster)
Definition: fat.c:289
void reclaim_file(DOS_FS *fs)
Definition: fat.c:426
uint32_t update_free(DOS_FS *fs)
Definition: fat.c:531
#define die(str)
Definition: mkdosfs.c:347
void exit(int exitcode)
Definition: _exit.c:33
#define memset(x, y, z)
Definition: compat.h:39
#define FAT_EXTD(fs)
Definition: fsck.fat.h:235
static unsigned char * fat
Definition: mkdosfs.c:542
void reclaim_free(DOS_FS *fs)
Definition: fat.c:340
void get_fat(FAT_ENTRY *entry, void *fat, uint32_t cluster, DOS_FS *fs)
Definition: fat.c:41
#define printf
Definition: config.h:203