1/*	$NetBSD: fat.c,v 1.21 2008/07/24 14:23:16 matthias Exp $	*/
2
3/*
4 * Copyright (C) 1995, 1996, 1997 Wolfgang Solfrank
5 * Copyright (c) 1995 Martin Husemann
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 * 1. Redistributions of source code must retain the above copyright
11 *    notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 *    notice, this list of conditions and the following disclaimer in the
14 *    documentation and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND ANY EXPRESS OR
17 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
18 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
19 * IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY DIRECT, INDIRECT,
20 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
21 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
25 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 */
27
28
29#include <sys/cdefs.h>
30#ifndef lint
31__RCSID("$NetBSD: fat.c,v 1.21 2008/07/24 14:23:16 matthias Exp $");
32#endif /* not lint */
33
34#include <stdlib.h>
35#include <string.h>
36#include <ctype.h>
37#include <stdio.h>
38#include <unistd.h>
39
40#include "ext.h"
41#include "fsutil.h"
42
43static int checkclnum(struct bootblock *, u_int, cl_t, cl_t *);
44static int clustdiffer(cl_t, cl_t *, cl_t *, u_int);
45static int tryclear(struct bootblock *, struct fatEntry *, cl_t, cl_t *);
46static int _readfat(int, struct bootblock *, u_int, u_char **);
47
48/*
49 * Check a cluster number for valid value
50 */
51static int
52checkclnum(struct bootblock *boot, u_int fat, cl_t cl, cl_t *next)
53{
54	if (*next >= (CLUST_RSRVD&boot->ClustMask))
55		*next |= ~boot->ClustMask;
56	if (*next == CLUST_FREE) {
57		boot->NumFree++;
58		return FSOK;
59	}
60	if (*next == CLUST_BAD) {
61		boot->NumBad++;
62		return FSOK;
63	}
64	if (*next < CLUST_FIRST
65	    || (*next >= boot->NumClusters && *next < CLUST_EOFS)) {
66		pwarn("Cluster %u in FAT %u continues with %s cluster number %u\n",
67		      cl, fat,
68		      *next < CLUST_RSRVD ? "out of range" : "reserved",
69		      *next&boot->ClustMask);
70		if (ask(0, "Truncate")) {
71			*next = CLUST_EOF;
72			return FSFATMOD;
73		}
74		return FSERROR;
75	}
76	return FSOK;
77}
78
79/*
80 * Read a FAT from disk. Returns 1 if successful, 0 otherwise.
81 */
82static int
83_readfat(int fs, struct bootblock *boot, u_int no, u_char **buffer)
84{
85	off_t off;
86	size_t len;
87
88	*buffer = malloc(len = boot->FATsecs * boot->BytesPerSec);
89	if (*buffer == NULL) {
90		perr("No space for FAT sectors (%zu)", len);
91		return 0;
92	}
93
94	off = boot->ResSectors + no * boot->FATsecs;
95	off *= boot->BytesPerSec;
96
97	if (lseek(fs, off, SEEK_SET) != off) {
98		perr("Unable to read FAT");
99		goto err;
100	}
101
102	if ((size_t)read(fs, *buffer, boot->FATsecs * boot->BytesPerSec)
103	    != boot->FATsecs * boot->BytesPerSec) {
104		perr("Unable to read FAT");
105		goto err;
106	}
107
108	return 1;
109
110    err:
111	free(*buffer);
112	return 0;
113}
114
115/*
116 * Read a FAT and decode it into internal format
117 */
118int
119readfat(int fs, struct bootblock *boot, u_int no, struct fatEntry **fp)
120{
121	struct fatEntry *fat;
122	u_char *buffer, *p;
123	cl_t cl;
124	int ret = FSOK;
125	size_t len;
126
127	boot->NumFree = boot->NumBad = 0;
128
129	if (!_readfat(fs, boot, no, &buffer))
130		return FSFATAL;
131
132	fat = malloc(len = boot->NumClusters * sizeof(struct fatEntry));
133	if (fat == NULL) {
134		perr("No space for FAT clusters (%zu)", len);
135		free(buffer);
136		return FSFATAL;
137	}
138	(void)memset(fat, 0, len);
139
140	if (buffer[0] != boot->Media
141	    || buffer[1] != 0xff || buffer[2] != 0xff
142	    || (boot->ClustMask == CLUST16_MASK && buffer[3] != 0xff)
143	    || (boot->ClustMask == CLUST32_MASK
144		&& ((buffer[3]&0x0f) != 0x0f
145		    || buffer[4] != 0xff || buffer[5] != 0xff
146		    || buffer[6] != 0xff || (buffer[7]&0x0f) != 0x0f))) {
147
148		/* Windows 95 OSR2 (and possibly any later) changes
149		 * the FAT signature to 0xXXffff7f for FAT16 and to
150		 * 0xXXffff0fffffff07 for FAT32 upon boot, to know that the
151		 * filesystem is dirty if it doesn't reboot cleanly.
152		 * Check this special condition before errorring out.
153		 */
154		if (buffer[0] == boot->Media && buffer[1] == 0xff
155		    && buffer[2] == 0xff
156		    && ((boot->ClustMask == CLUST16_MASK && buffer[3] == 0x7f)
157			|| (boot->ClustMask == CLUST32_MASK
158			    && buffer[3] == 0x0f && buffer[4] == 0xff
159			    && buffer[5] == 0xff && buffer[6] == 0xff
160			    && buffer[7] == 0x07)))
161			ret |= FSDIRTY;
162		else {
163			/* just some odd byte sequence in FAT */
164
165			switch (boot->ClustMask) {
166			case CLUST32_MASK:
167				pwarn("%s (%02x%02x%02x%02x%02x%02x%02x%02x)\n",
168				      "FAT starts with odd byte sequence",
169				      buffer[0], buffer[1], buffer[2], buffer[3],
170				      buffer[4], buffer[5], buffer[6], buffer[7]);
171				break;
172			case CLUST16_MASK:
173				pwarn("%s (%02x%02x%02x%02x)\n",
174				    "FAT starts with odd byte sequence",
175				    buffer[0], buffer[1], buffer[2], buffer[3]);
176				break;
177			default:
178				pwarn("%s (%02x%02x%02x)\n",
179				    "FAT starts with odd byte sequence",
180				    buffer[0], buffer[1], buffer[2]);
181				break;
182			}
183
184
185			if (ask(1, "Correct"))
186				ret |= FSFIXFAT;
187		}
188	}
189	switch (boot->ClustMask) {
190	case CLUST32_MASK:
191		p = buffer + 8;
192		break;
193	case CLUST16_MASK:
194		p = buffer + 4;
195		break;
196	default:
197		p = buffer + 3;
198		break;
199	}
200	for (cl = CLUST_FIRST; cl < boot->NumClusters;) {
201		switch (boot->ClustMask) {
202		case CLUST32_MASK:
203			fat[cl].next = p[0] + (p[1] << 8)
204				       + (p[2] << 16) + (p[3] << 24);
205			fat[cl].next &= boot->ClustMask;
206			ret |= checkclnum(boot, no, cl, &fat[cl].next);
207			cl++;
208			p += 4;
209			break;
210		case CLUST16_MASK:
211			fat[cl].next = p[0] + (p[1] << 8);
212			ret |= checkclnum(boot, no, cl, &fat[cl].next);
213			cl++;
214			p += 2;
215			break;
216		default:
217			fat[cl].next = (p[0] + (p[1] << 8)) & 0x0fff;
218			ret |= checkclnum(boot, no, cl, &fat[cl].next);
219			cl++;
220			if (cl >= boot->NumClusters)
221				break;
222			fat[cl].next = ((p[1] >> 4) + (p[2] << 4)) & 0x0fff;
223			ret |= checkclnum(boot, no, cl, &fat[cl].next);
224			cl++;
225			p += 3;
226			break;
227		}
228	}
229
230	free(buffer);
231	if (ret & FSFATAL) {
232		free(fat);
233		*fp = NULL;
234	} else
235		*fp = fat;
236	return ret;
237}
238
239/*
240 * Get type of reserved cluster
241 */
242const char *
243rsrvdcltype(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
254static int
255clustdiffer(cl_t cl, cl_t *cp1, cl_t *cp2, u_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 %u\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 %u'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 %u\n",
283		      cl, rsrvdcltype(*cp1), *cp2, fatnum);
284		if (ask(0, "Use continuation from FAT %u", 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 %u\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 %u", 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 %u\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 %u", 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 */
324int
325comparefat(struct bootblock *boot, struct fatEntry *first,
326	   struct fatEntry *second, u_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
337void
338clearchain(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
351int
352tryclear(struct bootblock *boot, struct fatEntry *fat, cl_t head, cl_t *truncp)
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		*truncp = CLUST_EOF;
359		return FSFATMOD;
360	} else
361		return FSERROR;
362}
363
364/*
365 * Check a complete FAT in-memory for crosslinks
366 */
367int
368checkfat(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 */
461int
462writefat(int fs, struct bootblock *boot, struct fatEntry *fat, int correct_fat)
463{
464	u_char *buffer, *p;
465	cl_t cl;
466	u_int i;
467	size_t fatsz;
468	off_t off;
469	int ret = FSOK;
470
471	buffer = malloc(fatsz = boot->FATsecs * boot->BytesPerSec);
472	if (buffer == NULL) {
473		perr("No space for FAT sectors (%zu)", fatsz);
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		    || (size_t)write(fs, buffer, fatsz) != fatsz) {
558			perr("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 */
569int
570checklost(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->FSNext >= boot->NumClusters || (boot->NumFree && fat[boot->FSNext].next != CLUST_FREE)) {
608			pwarn("Next free cluster in FSInfo block (%u) %s\n",
609			      boot->FSNext,
610			      (boot->FSNext >= boot->NumClusters) ? "invalid" : "not free");
611			if (ask(1, "fix"))
612				for (head = CLUST_FIRST; head < boot->NumClusters; head++)
613					if (fat[head].next == CLUST_FREE) {
614						boot->FSNext = head;
615						ret = 1;
616						break;
617					}
618		}
619		if (ret)
620			mod |= writefsinfo(dosfs, boot);
621	}
622
623	return mod;
624}
625