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