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
6 This program is free software: you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation, either version 3 of the License, or
9 (at your option) any later version.
10
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with this program. If not, see <http://www.gnu.org/licenses/>.
18
19 On Debian systems, the complete text of the GNU General Public License
20 can be found in /usr/share/common-licenses/GPL-3 file.
21 */
22
23 /* FAT32, VFAT, Atari format support, and various fixes additions May 1998
24 * by Roman Hodek <Roman.Hodek@informatik.uni-erlangen.de> */
25
26
27 #include <stdio.h>
28 #include <stdlib.h>
29 #include <string.h>
30 #include <unistd.h>
31
32 #include "common.h"
33 #include "dosfsck.h"
34 #include "io.h"
35 #include "check.h"
36 #include "fat.h"
37
38
get_fat(FAT_ENTRY * entry,void * fat,unsigned long cluster,DOS_FS * fs)39 static void get_fat(FAT_ENTRY *entry,void *fat,unsigned long cluster,DOS_FS *fs)
40 {
41 unsigned char *ptr;
42
43 switch(fs->fat_bits) {
44 case 12:
45 ptr = &((unsigned char *) fat)[cluster*3/2];
46 entry->value = 0xfff & (cluster & 1 ? (ptr[0] >> 4) | (ptr[1] << 4) :
47 (ptr[0] | ptr[1] << 8));
48 break;
49 case 16:
50 entry->value = CF_LE_W(((unsigned short *) fat)[cluster]);
51 break;
52 case 32:
53 /* According to M$, the high 4 bits of a FAT32 entry are reserved and
54 * are not part of the cluster number. So we cut them off. */
55 {
56 unsigned long e = CF_LE_L(((unsigned int *) fat)[cluster]);
57 entry->value = e & 0xfffffff;
58 entry->reserved = e >> 28;
59 }
60 break;
61 default:
62 die("Bad FAT entry size: %d bits.",fs->fat_bits);
63 }
64 entry->owner = NULL;
65 }
66
67
read_fat(DOS_FS * fs)68 void read_fat(DOS_FS *fs)
69 {
70 int eff_size;
71 unsigned long i;
72 void *first,*second = NULL;
73 int first_ok,second_ok;
74
75 eff_size = ((fs->clusters+2ULL)*fs->fat_bits+7)/8ULL;
76 first = alloc(eff_size);
77 fs_read(fs->fat_start,eff_size,first);
78 if (fs->nfats > 1) {
79 second = alloc(eff_size);
80 fs_read(fs->fat_start+fs->fat_size,eff_size,second);
81 }
82 if (second && memcmp(first,second,eff_size) != 0) {
83 FAT_ENTRY first_media, second_media;
84 get_fat(&first_media,first,0,fs);
85 get_fat(&second_media,second,0,fs);
86 first_ok = (first_media.value & FAT_EXTD(fs)) == FAT_EXTD(fs);
87 second_ok = (second_media.value & FAT_EXTD(fs)) == FAT_EXTD(fs);
88 if (first_ok && !second_ok) {
89 printf("FATs differ - using first FAT.\n");
90 fs_write(fs->fat_start+fs->fat_size,eff_size,first);
91 }
92 if (!first_ok && second_ok) {
93 printf("FATs differ - using second FAT.\n");
94 fs_write(fs->fat_start,eff_size,second);
95 memcpy(first,second,eff_size);
96 }
97 if (first_ok && second_ok) {
98 if (interactive) {
99 printf("FATs differ but appear to be intact. Use which FAT ?\n"
100 "1) Use first FAT\n2) Use second FAT\n");
101 if (get_key("12","?") == '1') {
102 fs_write(fs->fat_start+fs->fat_size,eff_size,first);
103 } else {
104 fs_write(fs->fat_start,eff_size,second);
105 memcpy(first,second,eff_size);
106 }
107 }
108 else {
109 printf("FATs differ but appear to be intact. Using first "
110 "FAT.\n");
111 fs_write(fs->fat_start+fs->fat_size,eff_size,first);
112 }
113 }
114 if (!first_ok && !second_ok) {
115 printf("Both FATs appear to be corrupt. Giving up.\n");
116 exit(1);
117 }
118 }
119 if (second) {
120 free(second);
121 }
122 fs->fat = qalloc(&mem_queue,sizeof(FAT_ENTRY)*(fs->clusters+2ULL));
123 for (i = 2; i < fs->clusters+2; i++) get_fat(&fs->fat[i],first,i,fs);
124 for (i = 2; i < fs->clusters+2; i++)
125 if (fs->fat[i].value >= fs->clusters+2 &&
126 (fs->fat[i].value < FAT_MIN_BAD(fs))) {
127 printf("Cluster %ld out of range (%ld > %ld). Setting to EOF.\n",
128 i-2,fs->fat[i].value,fs->clusters+2-1);
129 set_fat(fs,i,-1);
130 }
131 free(first);
132 }
133
134
set_fat(DOS_FS * fs,unsigned long cluster,unsigned long new)135 void set_fat(DOS_FS *fs,unsigned long cluster,unsigned long new)
136 {
137 unsigned char data[4];
138 int size;
139 loff_t offs;
140
141 if ((long)new == -1)
142 new = FAT_EOF(fs);
143 else if ((long)new == -2)
144 new = FAT_BAD(fs);
145 switch( fs->fat_bits ) {
146 case 12:
147 offs = fs->fat_start+cluster*3/2;
148 if (cluster & 1) {
149 data[0] = ((new & 0xf) << 4) | (fs->fat[cluster-1].value >> 8);
150 data[1] = new >> 4;
151 }
152 else {
153 data[0] = new & 0xff;
154 data[1] = (new >> 8) | (cluster == fs->clusters-1 ? 0 :
155 (0xff & fs->fat[cluster+1].value) << 4);
156 }
157 size = 2;
158 break;
159 case 16:
160 offs = fs->fat_start+cluster*2;
161 *(unsigned short *) data = CT_LE_W(new);
162 size = 2;
163 break;
164 case 32:
165 offs = fs->fat_start+cluster*4;
166 /* According to M$, the high 4 bits of a FAT32 entry are reserved and
167 * are not part of the cluster number. So we never touch them. */
168 *(unsigned long *) data = CT_LE_L( (new & 0xfffffff) |
169 (fs->fat[cluster].reserved << 28) );
170 size = 4;
171 break;
172 default:
173 die("Bad FAT entry size: %d bits.",fs->fat_bits);
174 }
175 fs->fat[cluster].value = new;
176 fs_write(offs,size,&data);
177 fs_write(offs+fs->fat_size,size,&data);
178 }
179
180
bad_cluster(DOS_FS * fs,unsigned long cluster)181 int bad_cluster(DOS_FS *fs,unsigned long cluster)
182 {
183 return FAT_IS_BAD(fs,fs->fat[cluster].value);
184 }
185
186
next_cluster(DOS_FS * fs,unsigned long cluster)187 unsigned long next_cluster(DOS_FS *fs,unsigned long cluster)
188 {
189 unsigned long value;
190
191 value = fs->fat[cluster].value;
192 if (FAT_IS_BAD(fs,value))
193 die("Internal error: next_cluster on bad cluster");
194 return FAT_IS_EOF(fs,value) ? -1 : value;
195 }
196
197
cluster_start(DOS_FS * fs,unsigned long cluster)198 loff_t cluster_start(DOS_FS *fs,unsigned long cluster)
199 {
200 return fs->data_start+((loff_t)cluster-2)*(unsigned long long)fs->cluster_size;
201 }
202
203
set_owner(DOS_FS * fs,unsigned long cluster,DOS_FILE * owner)204 void set_owner(DOS_FS *fs,unsigned long cluster,DOS_FILE *owner)
205 {
206 if (owner && fs->fat[cluster].owner)
207 die("Internal error: attempt to change file owner");
208 fs->fat[cluster].owner = owner;
209 }
210
211
get_owner(DOS_FS * fs,unsigned long cluster)212 DOS_FILE *get_owner(DOS_FS *fs,unsigned long cluster)
213 {
214 return fs->fat[cluster].owner;
215 }
216
217
fix_bad(DOS_FS * fs)218 void fix_bad(DOS_FS *fs)
219 {
220 unsigned long i;
221
222 if (verbose)
223 printf("Checking for bad clusters.\n");
224 for (i = 2; i < fs->clusters+2; i++)
225 if (!get_owner(fs,i) && !FAT_IS_BAD(fs,fs->fat[i].value))
226 if (!fs_test(cluster_start(fs,i),fs->cluster_size)) {
227 printf("Cluster %lu is unreadable.\n",i);
228 set_fat(fs,i,-2);
229 }
230 }
231
232
reclaim_free(DOS_FS * fs)233 void reclaim_free(DOS_FS *fs)
234 {
235 int reclaimed;
236 unsigned long i;
237
238 if (verbose)
239 printf("Checking for unused clusters.\n");
240 reclaimed = 0;
241 for (i = 2; i < fs->clusters+2; i++)
242 if (!get_owner(fs,i) && fs->fat[i].value &&
243 !FAT_IS_BAD(fs,fs->fat[i].value)) {
244 set_fat(fs,i,0);
245 reclaimed++;
246 }
247 if (reclaimed)
248 printf("Reclaimed %d unused cluster%s (%llu bytes).\n",reclaimed,
249 reclaimed == 1 ? "" : "s",(unsigned long long)reclaimed*fs->cluster_size);
250 }
251
252
tag_free(DOS_FS * fs,DOS_FILE * ptr)253 static void tag_free(DOS_FS *fs,DOS_FILE *ptr)
254 {
255 DOS_FILE *owner;
256 int prev;
257 unsigned long i,walk;
258
259 for (i = 2; i < fs->clusters+2; i++)
260 if (fs->fat[i].value && !FAT_IS_BAD(fs,fs->fat[i].value) &&
261 !get_owner(fs,i) && !fs->fat[i].prev) {
262 prev = 0;
263 for (walk = i; walk > 0 && walk != -1;
264 walk = next_cluster(fs,walk)) {
265 if (!(owner = get_owner(fs,walk))) set_owner(fs,walk,ptr);
266 else if (owner != ptr)
267 die("Internal error: free chain collides with file");
268 else {
269 set_fat(fs,prev,-1);
270 break;
271 }
272 prev = walk;
273 }
274 }
275 }
276
277
reclaim_file(DOS_FS * fs)278 void reclaim_file(DOS_FS *fs)
279 {
280 DOS_FILE dummy;
281 int reclaimed,files,changed;
282 unsigned long i,next,walk;
283
284 if (verbose)
285 printf("Reclaiming unconnected clusters.\n");
286 for (i = 2; i < fs->clusters+2; i++) fs->fat[i].prev = 0;
287 for (i = 2; i < fs->clusters+2; i++) {
288 next = fs->fat[i].value;
289 if (!get_owner(fs,i) && next && next < fs->clusters+2) {
290 if (get_owner(fs,next) || !fs->fat[next].value ||
291 FAT_IS_BAD(fs,fs->fat[next].value)) set_fat(fs,i,-1);
292 else fs->fat[next].prev++;
293 }
294 }
295 do {
296 tag_free(fs,&dummy);
297 changed = 0;
298 for (i = 2; i < fs->clusters+2; i++)
299 if (fs->fat[i].value && !FAT_IS_BAD(fs,fs->fat[i].value) &&
300 !get_owner(fs, i)) {
301 if (!fs->fat[fs->fat[i].value].prev--)
302 die("Internal error: prev going below zero");
303 set_fat(fs,i,-1);
304 changed = 1;
305 printf("Broke cycle at cluster %lu in free chain.\n",i);
306 break;
307 }
308 }
309 while (changed);
310 files = reclaimed = 0;
311 for (i = 2; i < fs->clusters+2; i++)
312 if (get_owner(fs,i) == &dummy && !fs->fat[i].prev) {
313 DIR_ENT de;
314 loff_t offset;
315 files++;
316 offset = alloc_rootdir_entry(fs,&de,"FSCK%04dREC");
317 de.start = CT_LE_W(i&0xffff);
318 if (fs->fat_bits == 32)
319 de.starthi = CT_LE_W(i>>16);
320 for (walk = i; walk > 0 && walk != -1;
321 walk = next_cluster(fs,walk)) {
322 de.size = CT_LE_L(CF_LE_L(de.size)+fs->cluster_size);
323 reclaimed++;
324 }
325 fs_write(offset,sizeof(DIR_ENT),&de);
326 }
327 if (reclaimed)
328 printf("Reclaimed %d unused cluster%s (%llu bytes) in %d chain%s.\n",
329 reclaimed,reclaimed == 1 ? "" : "s",(unsigned long long)reclaimed*fs->cluster_size,files,
330 files == 1 ? "" : "s");
331 }
332
333
update_free(DOS_FS * fs)334 unsigned long update_free(DOS_FS *fs)
335 {
336 unsigned long i;
337 unsigned long free = 0;
338 int do_set = 0;
339
340 for (i = 2; i < fs->clusters+2; i++)
341 if (!get_owner(fs,i) && !FAT_IS_BAD(fs,fs->fat[i].value))
342 ++free;
343
344 if (!fs->fsinfo_start)
345 return free;
346
347 if (verbose)
348 printf("Checking free cluster summary.\n");
349 if (fs->free_clusters >= 0) {
350 if (free != fs->free_clusters) {
351 printf( "Free cluster summary wrong (%ld vs. really %ld)\n",
352 fs->free_clusters,free);
353 if (interactive)
354 printf( "1) Correct\n2) Don't correct\n" );
355 else printf( " Auto-correcting.\n" );
356 if (!interactive || get_key("12","?") == '1')
357 do_set = 1;
358 }
359 }
360 else {
361 printf( "Free cluster summary uninitialized (should be %ld)\n", free );
362 if (interactive)
363 printf( "1) Set it\n2) Leave it uninitialized\n" );
364 else printf( " Auto-setting.\n" );
365 if (!interactive || get_key("12","?") == '1')
366 do_set = 1;
367 }
368
369 if (do_set) {
370 fs->free_clusters = free;
371 free = CT_LE_L(free);
372 fs_write(fs->fsinfo_start+offsetof(struct info_sector,free_clusters),
373 sizeof(free),&free);
374 }
375
376 return free;
377 }
378
379 /* Local Variables: */
380 /* tab-width: 8 */
381 /* End: */
382