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