1 /* $OpenBSD: fat.c,v 1.27 2015/12/10 17:26:59 mmcc Exp $ */
2 /* $NetBSD: fat.c,v 1.8 1997/10/17 11:19:53 ws Exp $ */
3
4 /*
5 * Copyright (C) 1995, 1996, 1997 Wolfgang Solfrank
6 * Copyright (c) 1995 Martin Husemann
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29 #include <stdlib.h>
30 #include <string.h>
31 #include <ctype.h>
32 #include <stdio.h>
33 #include <unistd.h>
34
35 #include "ext.h"
36
37 static int checkclnum(struct bootblock *, int, cl_t, cl_t *);
38 static int clustdiffer(cl_t, cl_t *, cl_t *, int);
39 static int tryclear(struct bootblock *, struct fatEntry *, cl_t, cl_t *);
40
41 /*
42 * Check a cluster number for valid value
43 */
44 static int
checkclnum(struct bootblock * boot,int fat,cl_t cl,cl_t * next)45 checkclnum(struct bootblock *boot, int fat, cl_t cl, cl_t *next)
46 {
47 if (*next >= (CLUST_RSRVD&boot->ClustMask))
48 *next |= ~boot->ClustMask;
49 if (*next == CLUST_FREE) {
50 boot->NumFree++;
51 return (FSOK);
52 }
53 if (*next == CLUST_BAD) {
54 boot->NumBad++;
55 return (FSOK);
56 }
57 if (*next < CLUST_FIRST
58 || (*next >= boot->NumClusters && *next < CLUST_EOFS)) {
59 pwarn("Cluster %u in FAT %d continues with %s cluster number %u\n",
60 cl, fat,
61 *next < CLUST_RSRVD ? "out of range" : "reserved",
62 *next&boot->ClustMask);
63 if (ask(0, "Truncate")) {
64 *next = CLUST_EOF;
65 return (FSFATMOD);
66 }
67 return (FSERROR);
68 }
69 return (FSOK);
70 }
71
72 /*
73 * Read a FAT and decode it into internal format
74 */
75 int
readfat(int fs,struct bootblock * boot,int no,struct fatEntry ** fp)76 readfat(int fs, struct bootblock *boot, int no, struct fatEntry **fp)
77 {
78 struct fatEntry *fat;
79 u_char *buffer, *p;
80 cl_t cl;
81 off_t off;
82 int ret = FSOK;
83
84 boot->NumFree = boot->NumBad = 0;
85 fat = calloc(boot->NumClusters, sizeof(struct fatEntry));
86 buffer = calloc(boot->FATsecs, boot->BytesPerSec);
87 if (fat == NULL || buffer == NULL) {
88 xperror("No space for FAT");
89 free(fat);
90 free(buffer);
91 return (FSFATAL);
92 }
93
94 off = boot->ResSectors + no * boot->FATsecs;
95 off *= boot->BytesPerSec;
96
97 if (lseek(fs, off, SEEK_SET) != off) {
98 xperror("Unable to read FAT");
99 free(buffer);
100 free(fat);
101 return (FSFATAL);
102 }
103
104 if (read(fs, buffer, boot->FATsecs * boot->BytesPerSec)
105 != boot->FATsecs * boot->BytesPerSec) {
106 xperror("Unable to read FAT");
107 free(buffer);
108 free(fat);
109 return (FSFATAL);
110 }
111
112 if (buffer[0] != boot->Media
113 || buffer[1] != 0xff || buffer[2] != 0xff
114 || (boot->ClustMask == CLUST16_MASK && buffer[3] != 0xff)
115 || (boot->ClustMask == CLUST32_MASK
116 && ((buffer[3]&0x0f) != 0x0f
117 || buffer[4] != 0xff || buffer[5] != 0xff
118 || buffer[6] != 0xff || (buffer[7]&0x0f) != 0x0f))) {
119 static const char msg[] = "FAT starts with odd byte sequence ";
120
121 switch (boot->ClustMask) {
122 case CLUST32_MASK:
123 pwarn("%s(%02x%02x%02x%02x%02x%02x%02x%02x)\n", msg,
124 buffer[0], buffer[1], buffer[2], buffer[3],
125 buffer[4], buffer[5], buffer[6], buffer[7]);
126 break;
127 case CLUST16_MASK:
128 pwarn("%s(%02x%02x%02x%02x)\n", msg,
129 buffer[0], buffer[1], buffer[2], buffer[3]);
130 break;
131 default:
132 pwarn("%s(%02x%02x%02x)\n", msg,
133 buffer[0], buffer[1], buffer[2]);
134 break;
135 }
136 if (ask(1, "Correct"))
137 ret |= FSFATMOD;
138 }
139 switch (boot->ClustMask) {
140 case CLUST32_MASK:
141 p = buffer + 8;
142 break;
143 case CLUST16_MASK:
144 p = buffer + 4;
145 break;
146 default:
147 p = buffer + 3;
148 break;
149 }
150 for (cl = CLUST_FIRST; cl < boot->NumClusters;) {
151 switch (boot->ClustMask) {
152 case CLUST32_MASK:
153 fat[cl].next = p[0] + (p[1] << 8)
154 + (p[2] << 16) + (p[3] << 24);
155 fat[cl].next &= boot->ClustMask;
156 ret |= checkclnum(boot, no, cl, &fat[cl].next);
157 cl++;
158 p += 4;
159 break;
160 case CLUST16_MASK:
161 fat[cl].next = p[0] + (p[1] << 8);
162 ret |= checkclnum(boot, no, cl, &fat[cl].next);
163 cl++;
164 p += 2;
165 break;
166 default:
167 fat[cl].next = (p[0] + (p[1] << 8)) & 0x0fff;
168 ret |= checkclnum(boot, no, cl, &fat[cl].next);
169 cl++;
170 if (cl >= boot->NumClusters)
171 break;
172 fat[cl].next = ((p[1] >> 4) + (p[2] << 4)) & 0x0fff;
173 ret |= checkclnum(boot, no, cl, &fat[cl].next);
174 cl++;
175 p += 3;
176 break;
177 }
178 }
179
180 free(buffer);
181 if (ret & FSFATAL) {
182 free(fat);
183 *fp = NULL;
184 } else
185 *fp = fat;
186 return (ret);
187 }
188
189 /*
190 * Get type of reserved cluster
191 */
192 char *
rsrvdcltype(cl_t cl)193 rsrvdcltype(cl_t cl)
194 {
195 if (cl == CLUST_FREE)
196 return ("free");
197 if (cl < CLUST_BAD)
198 return ("reserved");
199 if (cl > CLUST_BAD)
200 return ("as EOF");
201 return ("bad");
202 }
203
204 static int
clustdiffer(cl_t cl,cl_t * cp1,cl_t * cp2,int fatnum)205 clustdiffer(cl_t cl, cl_t *cp1, cl_t *cp2, int fatnum)
206 {
207 if (*cp1 == CLUST_FREE || *cp1 >= CLUST_RSRVD) {
208 if (*cp2 == CLUST_FREE || *cp2 >= CLUST_RSRVD) {
209 if ((*cp1 != CLUST_FREE && *cp1 < CLUST_BAD
210 && *cp2 != CLUST_FREE && *cp2 < CLUST_BAD)
211 || (*cp1 > CLUST_BAD && *cp2 > CLUST_BAD)) {
212 pwarn("Cluster %u is marked %s with different indicators, ",
213 cl, rsrvdcltype(*cp1));
214 if (ask(1, "fix")) {
215 *cp2 = *cp1;
216 return (FSFATMOD);
217 }
218 return (FSFATAL);
219 }
220 pwarn("Cluster %u is marked %s in FAT 0, %s in FAT %d\n",
221 cl, rsrvdcltype(*cp1), rsrvdcltype(*cp2), fatnum);
222 if (ask(0, "use FAT 0's entry")) {
223 *cp2 = *cp1;
224 return (FSFATMOD);
225 }
226 if (ask(0, "use FAT %d's entry", fatnum)) {
227 *cp1 = *cp2;
228 return (FSFATMOD);
229 }
230 return (FSFATAL);
231 }
232 pwarn("Cluster %u is marked %s in FAT 0, but continues with cluster %u in FAT %d\n",
233 cl, rsrvdcltype(*cp1), *cp2, fatnum);
234 if (ask(0, "Use continuation from FAT %d", fatnum)) {
235 *cp1 = *cp2;
236 return (FSFATMOD);
237 }
238 if (ask(0, "Use mark from FAT 0")) {
239 *cp2 = *cp1;
240 return (FSFATMOD);
241 }
242 return (FSFATAL);
243 }
244 if (*cp2 == CLUST_FREE || *cp2 >= CLUST_RSRVD) {
245 pwarn("Cluster %u continues with cluster %u in FAT 0, but is marked %s in FAT %d\n",
246 cl, *cp1, rsrvdcltype(*cp2), fatnum);
247 if (ask(0, "Use continuation from FAT 0")) {
248 *cp2 = *cp1;
249 return (FSFATMOD);
250 }
251 if (ask(0, "Use mark from FAT %d", fatnum)) {
252 *cp1 = *cp2;
253 return (FSFATMOD);
254 }
255 return (FSERROR);
256 }
257 pwarn("Cluster %u continues with cluster %u in FAT 0, but with cluster %u in FAT %d\n",
258 cl, *cp1, *cp2, fatnum);
259 if (ask(0, "Use continuation from FAT 0")) {
260 *cp2 = *cp1;
261 return (FSFATMOD);
262 }
263 if (ask(0, "Use continuation from FAT %d", fatnum)) {
264 *cp1 = *cp2;
265 return (FSFATMOD);
266 }
267 return (FSERROR);
268 }
269
270 /*
271 * Compare two FAT copies in memory. Resolve any conflicts and merge them
272 * into the first one.
273 */
274 int
comparefat(struct bootblock * boot,struct fatEntry * first,struct fatEntry * second,int fatnum)275 comparefat(struct bootblock *boot, struct fatEntry *first,
276 struct fatEntry *second, int fatnum)
277 {
278 cl_t cl;
279 int ret = FSOK;
280
281 for (cl = CLUST_FIRST; cl < boot->NumClusters; cl++)
282 if (first[cl].next != second[cl].next)
283 ret |= clustdiffer(cl, &first[cl].next, &second[cl].next, fatnum);
284 return (ret);
285 }
286
287 void
clearchain(struct bootblock * boot,struct fatEntry * fat,cl_t head)288 clearchain(struct bootblock *boot, struct fatEntry *fat, cl_t head)
289 {
290 cl_t p, q;
291
292 for (p = head; p >= CLUST_FIRST && p < boot->NumClusters; p = q) {
293 if (fat[p].head != head)
294 break;
295 q = fat[p].next;
296 fat[p].next = fat[p].head = CLUST_FREE;
297 fat[p].length = 0;
298 }
299 }
300
301 int
tryclear(struct bootblock * boot,struct fatEntry * fat,cl_t head,cl_t * trunc)302 tryclear(struct bootblock *boot, struct fatEntry *fat, cl_t head, cl_t *trunc)
303 {
304 u_int len;
305 cl_t p;
306
307 if (ask(0, "Clear chain starting at %u", head)) {
308 clearchain(boot, fat, head);
309 return FSFATMOD;
310 } else if (ask(0, "Truncate")) {
311 *trunc = CLUST_EOF;
312 len = 0;
313 for (p = head; p >= CLUST_FIRST && p < boot->NumClusters;
314 p = fat[p].next) {
315 len++;
316 }
317 fat[head].length = len;
318 return FSFATMOD;
319 } else
320 return FSERROR;
321 }
322
323 /*
324 * Check a complete FAT in-memory for crosslinks
325 */
326 int
checkfat(struct bootblock * boot,struct fatEntry * fat)327 checkfat(struct bootblock *boot, struct fatEntry *fat)
328 {
329 cl_t head, p, h, n;
330 u_int len;
331 int ret = 0;
332 int conf;
333
334 /*
335 * pass 1: figure out the cluster chains.
336 */
337 for (head = CLUST_FIRST; head < boot->NumClusters; head++) {
338 /* find next untravelled chain */
339 if (fat[head].head != 0 /* cluster already belongs to some chain */
340 || fat[head].next == CLUST_FREE
341 || fat[head].next == CLUST_BAD)
342 continue; /* skip it. */
343
344 /* follow the chain and mark all clusters on the way */
345 for (len = 0, p = head;
346 p >= CLUST_FIRST && p < boot->NumClusters &&
347 fat[p].head != head;
348 p = fat[p].next) {
349 fat[p].head = head;
350 len++;
351 }
352
353 /* the head record gets the length */
354 fat[head].length = fat[head].next == CLUST_FREE ? 0 : len;
355 }
356
357 /*
358 * pass 2: check for crosslinked chains (we couldn't do this in pass 1 because
359 * we didn't know the real start of the chain then - would have treated partial
360 * chains as interlinked with their main chain)
361 */
362 for (head = CLUST_FIRST; head < boot->NumClusters; head++) {
363 /* find next untravelled chain */
364 if (fat[head].head != head)
365 continue;
366
367 /* follow the chain to its end (hopefully) */
368 for (len = fat[head].length, p = head;
369 (n = fat[p].next) >= CLUST_FIRST && n < boot->NumClusters;
370 p = n) {
371 /* len is always off by one due to n assignment */
372 if (fat[n].head != head || len-- < 2)
373 break;
374 }
375 if (n >= CLUST_EOFS)
376 continue;
377
378 if (n == CLUST_FREE || n >= CLUST_RSRVD) {
379 pwarn("Cluster chain starting at %u ends with cluster marked %s\n",
380 head, rsrvdcltype(n));
381 ret |= tryclear(boot, fat, head, &fat[p].next);
382 continue;
383 }
384 if (n < CLUST_FIRST || n >= boot->NumClusters) {
385 pwarn("Cluster chain starting at %u ends with cluster out of range (%u)\n",
386 head, n);
387 ret |= tryclear(boot, fat, head, &fat[p].next);
388 continue;
389 }
390 if (head == fat[n].head) {
391 pwarn("Cluster chain starting at %u loops at cluster %u\n",
392 head, p);
393 ret |= tryclear(boot, fat, head, &fat[p].next);
394 continue;
395 }
396 pwarn("Cluster chains starting at %u and %u are linked at cluster %u\n",
397 head, fat[n].head, n);
398 conf = tryclear(boot, fat, head, &fat[p].next);
399 if (ask(0, "Clear chain starting at %u", h = fat[n].head)) {
400 if (conf == FSERROR) {
401 /*
402 * Transfer the common chain to the one not cleared above.
403 */
404 for (p = n;
405 p >= CLUST_FIRST && p < boot->NumClusters;
406 p = fat[p].next) {
407 if (h != fat[p].head) {
408 /*
409 * Have to reexamine this chain.
410 */
411 head--;
412 break;
413 }
414 fat[p].head = head;
415 }
416 }
417 clearchain(boot, fat, h);
418 conf |= FSFATMOD;
419 }
420 ret |= conf;
421 }
422
423 return (ret);
424 }
425
426 /*
427 * Write out FATs encoding them from the internal format
428 */
429 int
writefat(int fs,struct bootblock * boot,struct fatEntry * fat)430 writefat(int fs, struct bootblock *boot, struct fatEntry *fat)
431 {
432 u_char *buffer, *p;
433 cl_t cl;
434 int i;
435 u_int32_t fatsz;
436 off_t off;
437 int ret = FSOK;
438
439 fatsz = boot->FATsecs * boot->BytesPerSec;
440 buffer = calloc(boot->FATsecs, boot->BytesPerSec);
441 if (buffer == NULL) {
442 xperror("No space for FAT");
443 return (FSFATAL);
444 }
445 (void)memset(buffer, 0, fatsz);
446 boot->NumFree = 0;
447 p = buffer;
448 *p++ = (u_char)boot->Media;
449 *p++ = 0xff;
450 *p++ = 0xff;
451 switch (boot->ClustMask) {
452 case CLUST16_MASK:
453 *p++ = 0xff;
454 break;
455 case CLUST32_MASK:
456 *p++ = 0x0f;
457 *p++ = 0xff;
458 *p++ = 0xff;
459 *p++ = 0xff;
460 *p++ = 0x0f;
461 break;
462 }
463 for (cl = CLUST_FIRST; cl < boot->NumClusters; cl++) {
464 switch (boot->ClustMask) {
465 case CLUST32_MASK:
466 if (fat[cl].next == CLUST_FREE)
467 boot->NumFree++;
468 *p++ = (u_char)fat[cl].next;
469 *p++ = (u_char)(fat[cl].next >> 8);
470 *p++ = (u_char)(fat[cl].next >> 16);
471 *p &= 0xf0;
472 *p++ |= (fat[cl].next >> 24)&0x0f;
473 break;
474 case CLUST16_MASK:
475 if (fat[cl].next == CLUST_FREE)
476 boot->NumFree++;
477 *p++ = (u_char)fat[cl].next;
478 *p++ = (u_char)(fat[cl].next >> 8);
479 break;
480 default:
481 if (fat[cl].next == CLUST_FREE)
482 boot->NumFree++;
483 *p++ = (u_char)fat[cl].next;
484 *p = (u_char)((fat[cl].next >> 8) & 0xf);
485 cl++;
486 if (cl >= boot->NumClusters)
487 break;
488 if (fat[cl].next == CLUST_FREE)
489 boot->NumFree++;
490 *p++ |= (u_char)(fat[cl].next << 4);
491 *p++ = (u_char)(fat[cl].next >> 4);
492 break;
493 }
494 }
495 for (i = 0; i < boot->FATs; i++) {
496 off = boot->ResSectors + i * boot->FATsecs;
497 off *= boot->BytesPerSec;
498 if (lseek(fs, off, SEEK_SET) != off
499 || write(fs, buffer, fatsz) != fatsz) {
500 xperror("Unable to write FAT");
501 ret = FSFATAL; /* Return immediately? XXX */
502 }
503 }
504 free(buffer);
505 return (ret);
506 }
507
508 /*
509 * Check a complete in-memory FAT for lost cluster chains
510 */
511 int
checklost(int dosfs,struct bootblock * boot,struct fatEntry * fat)512 checklost(int dosfs, struct bootblock *boot, struct fatEntry *fat)
513 {
514 cl_t head;
515 int mod = FSOK;
516 int ret;
517
518 for (head = CLUST_FIRST; head < boot->NumClusters; head++) {
519 /* find next untravelled chain */
520 if (fat[head].head != head
521 || fat[head].next == CLUST_FREE
522 || (fat[head].next >= CLUST_RSRVD
523 && fat[head].next < CLUST_EOFS)
524 || (fat[head].flags & FAT_USED))
525 continue;
526
527 pwarn("Lost cluster chain at cluster %u\n%d Cluster(s) lost\n",
528 head, fat[head].length);
529 mod |= ret = reconnect(dosfs, boot, fat, head);
530 if (mod & FSFATAL)
531 break;
532 if (ret == FSERROR && ask(0, "Clear")) {
533 clearchain(boot, fat, head);
534 mod |= FSFATMOD;
535 }
536 }
537 finishlf();
538
539 if (boot->FSInfo) {
540 ret = 0;
541 if (boot->FSFree != 0xffffffff &&
542 boot->FSFree != boot->NumFree) {
543 pwarn("Free space in FSInfo block (%u) not correct (%u)\n",
544 boot->FSFree, boot->NumFree);
545 if (ask(1, "fix")) {
546 boot->FSFree = boot->NumFree;
547 ret = 1;
548 }
549 }
550 if (boot->FSNext != 0xffffffff &&
551 boot->NumFree && (boot->FSNext >= boot->NumClusters ||
552 fat[boot->FSNext].next != CLUST_FREE)) {
553 pwarn("Next free cluster in FSInfo block (%u) not free\n",
554 boot->FSNext);
555 if (ask(1, "fix"))
556 for (head = CLUST_FIRST; head < boot->NumClusters; head++)
557 if (fat[head].next == CLUST_FREE) {
558 boot->FSNext = head;
559 ret = 1;
560 break;
561 }
562 }
563 if (ret)
564 mod |= writefsinfo(dosfs, boot);
565 }
566
567 return (mod);
568 }
569