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