1/*	$NetBSD: fat.c,v 1.30 2019/06/04 00:08:00 christos 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.30 2019/06/04 00:08:00 christos 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		uint32_t len;
359		cl_t p;
360
361		for (p = head, len = 0;
362		    p >= CLUST_FIRST && p < boot->NumClusters;
363		    p = fat[p].next, len++)
364			continue;
365		*truncp = CLUST_EOF;
366		fat[head].length = len;
367		return FSFATMOD;
368	} else
369		return FSERROR;
370}
371
372/*
373 * Check a complete FAT in-memory for crosslinks
374 */
375int
376checkfat(struct bootblock *boot, struct fatEntry *fat)
377{
378	cl_t head, p, h, n;
379	u_int len;
380	int ret = 0;
381	int conf;
382
383	/*
384	 * pass 1: figure out the cluster chains.
385	 */
386	for (head = CLUST_FIRST; head < boot->NumClusters; head++) {
387		/* find next untravelled chain */
388		if (fat[head].head != 0		/* cluster already belongs to some chain */
389		    || fat[head].next == CLUST_FREE
390		    || fat[head].next == CLUST_BAD)
391			continue;		/* skip it. */
392
393		/* follow the chain and mark all clusters on the way */
394		for (len = 0, p = head;
395		     p >= CLUST_FIRST && p < boot->NumClusters &&
396		     fat[p].head != head;
397		     p = fat[p].next) {
398			fat[p].head = head;
399			len++;
400		}
401
402		/* the head record gets the length */
403		fat[head].length = fat[head].next == CLUST_FREE ? 0 : len;
404	}
405
406	/*
407	 * pass 2: check for crosslinked chains (we couldn't do this in pass 1 because
408	 * we didn't know the real start of the chain then - would have treated partial
409	 * chains as interlinked with their main chain)
410	 */
411	for (head = CLUST_FIRST; head < boot->NumClusters; head++) {
412		/* find next untravelled chain */
413		if (fat[head].head != head)
414			continue;
415
416		/* follow the chain to its end (hopefully) */
417		for (len = fat[head].length, p = head;
418		     (n = fat[p].next) >= CLUST_FIRST && n < boot->NumClusters;
419		     p = n)
420			if (fat[n].head != head || len-- < 2)
421				break;
422		if (n >= CLUST_EOFS)
423			continue;
424
425		if (n == CLUST_FREE || n >= CLUST_RSRVD) {
426			pwarn("Cluster chain starting at %u ends with cluster marked %s\n",
427			      head, rsrvdcltype(n));
428clear:
429			ret |= tryclear(boot, fat, head, &fat[p].next);
430			continue;
431		}
432		if (n < CLUST_FIRST || n >= boot->NumClusters) {
433			pwarn("Cluster chain starting at %u ends with cluster out of range (%u)\n",
434			    head, n);
435			goto clear;
436		}
437		if (head == fat[n].head) {
438			pwarn("Cluster chain starting at %u loops at cluster %u\n",
439
440			    head, p);
441			goto clear;
442		}
443		pwarn("Cluster chains starting at %u and %u are linked at cluster %u\n",
444		      head, fat[n].head, n);
445		conf = tryclear(boot, fat, head, &fat[p].next);
446		if (ask(0, "Clear chain starting at %u", h = fat[n].head)) {
447			if (conf == FSERROR) {
448				/*
449				 * Transfer the common chain to the one not cleared above.
450				 */
451				for (p = n;
452				     p >= CLUST_FIRST && p < boot->NumClusters;
453				     p = fat[p].next) {
454					if (h != fat[p].head) {
455						/*
456						 * Have to reexamine this chain.
457						 */
458						head--;
459						break;
460					}
461					fat[p].head = head;
462				}
463			}
464			clearchain(boot, fat, h);
465			conf |= FSFATMOD;
466		}
467		ret |= conf;
468	}
469
470	return ret;
471}
472
473/*
474 * Write out FATs encoding them from the internal format
475 */
476int
477writefat(int fs, struct bootblock *boot, struct fatEntry *fat, int correct_fat)
478{
479	u_char *buffer, *p;
480	cl_t cl;
481	u_int i;
482	size_t fatsz;
483	off_t off;
484	int ret = FSOK;
485
486	buffer = malloc(fatsz = boot->FATsecs * boot->BytesPerSec);
487	if (buffer == NULL) {
488		perr("No space for FAT sectors (%zu)", fatsz);
489		return FSFATAL;
490	}
491	memset(buffer, 0, fatsz);
492	boot->NumFree = 0;
493	p = buffer;
494	if (correct_fat) {
495		*p++ = (u_char)boot->Media;
496		*p++ = 0xff;
497		*p++ = 0xff;
498		switch (boot->ClustMask) {
499		case CLUST16_MASK:
500			*p++ = 0xff;
501			break;
502		case CLUST32_MASK:
503			*p++ = 0x0f;
504			*p++ = 0xff;
505			*p++ = 0xff;
506			*p++ = 0xff;
507			*p++ = 0x0f;
508			break;
509		}
510	} else {
511		/* use same FAT signature as the old FAT has */
512		int count;
513		u_char *old_fat;
514
515		switch (boot->ClustMask) {
516		case CLUST32_MASK:
517			count = 8;
518			break;
519		case CLUST16_MASK:
520			count = 4;
521			break;
522		default:
523			count = 3;
524			break;
525		}
526
527		if (!_readfat(fs, boot, boot->ValidFat >= 0 ? boot->ValidFat :0,
528					 &old_fat)) {
529			free(buffer);
530			return FSFATAL;
531		}
532
533		memcpy(p, old_fat, count);
534		free(old_fat);
535		p += count;
536	}
537
538	for (cl = CLUST_FIRST; cl < boot->NumClusters; cl++) {
539		switch (boot->ClustMask) {
540		case CLUST32_MASK:
541			if (fat[cl].next == CLUST_FREE)
542				boot->NumFree++;
543			*p++ = (u_char)fat[cl].next;
544			*p++ = (u_char)(fat[cl].next >> 8);
545			*p++ = (u_char)(fat[cl].next >> 16);
546			*p &= 0xf0;
547			*p++ |= (fat[cl].next >> 24)&0x0f;
548			break;
549		case CLUST16_MASK:
550			if (fat[cl].next == CLUST_FREE)
551				boot->NumFree++;
552			*p++ = (u_char)fat[cl].next;
553			*p++ = (u_char)(fat[cl].next >> 8);
554			break;
555		default:
556			if (fat[cl].next == CLUST_FREE)
557				boot->NumFree++;
558			*p++ = (u_char)fat[cl].next;
559			*p = (u_char)((fat[cl].next >> 8) & 0xf);
560			cl++;
561			if (cl >= boot->NumClusters)
562				break;
563			if (fat[cl].next == CLUST_FREE)
564				boot->NumFree++;
565			*p++ |= (u_char)(fat[cl].next << 4);
566			*p++ = (u_char)(fat[cl].next >> 4);
567			break;
568		}
569	}
570	for (i = 0; i < boot->FATs; i++) {
571		off = boot->ResSectors + i * boot->FATsecs;
572		off *= boot->BytesPerSec;
573		if (lseek(fs, off, SEEK_SET) != off
574		    || (size_t)write(fs, buffer, fatsz) != fatsz) {
575			perr("Unable to write FAT");
576			ret = FSFATAL; /* Return immediately?		XXX */
577		}
578	}
579	free(buffer);
580	return ret;
581}
582
583/*
584 * Check a complete in-memory FAT for lost cluster chains
585 */
586int
587checklost(int dosfs, struct bootblock *boot, struct fatEntry *fat)
588{
589	cl_t head;
590	int mod = FSOK;
591	int ret;
592
593	for (head = CLUST_FIRST; head < boot->NumClusters; head++) {
594		/* find next untravelled chain */
595		if (fat[head].head != head
596		    || fat[head].next == CLUST_FREE
597		    || (fat[head].next >= CLUST_RSRVD
598			&& fat[head].next < CLUST_EOFS)
599		    || (fat[head].flags & FAT_USED))
600			continue;
601
602		pwarn("Lost cluster chain at cluster %u\n%d Cluster(s) lost\n",
603		      head, fat[head].length);
604		mod |= ret = reconnect(dosfs, boot, fat, head);
605		if (mod & FSFATAL)
606			break;
607		if (ret == FSERROR && ask(0, "Clear")) {
608			clearchain(boot, fat, head);
609			mod |= FSFATMOD;
610		}
611	}
612	finishlf();
613
614	if (boot->FSInfo) {
615		ret = 0;
616		if (boot->FSFree != 0xffffffffU &&
617		    boot->FSFree != boot->NumFree) {
618			pwarn("Free space in FSInfo block (%u) not correct (%u)\n",
619			      boot->FSFree, boot->NumFree);
620			if (ask(1, "fix")) {
621				boot->FSFree = boot->NumFree;
622				ret = 1;
623			}
624		}
625		if (boot->FSNext != 0xffffffffU &&
626		    (boot->FSNext >= boot->NumClusters ||
627		    (boot->NumFree && fat[boot->FSNext].next != CLUST_FREE))) {
628			pwarn("Next free cluster in FSInfo block (%u) %s\n",
629			      boot->FSNext,
630			      (boot->FSNext >= boot->NumClusters) ? "invalid" : "not free");
631			if (ask(1, "fix"))
632				for (head = CLUST_FIRST; head < boot->NumClusters; head++)
633					if (fat[head].next == CLUST_FREE) {
634						boot->FSNext = head;
635						ret = 1;
636						break;
637					}
638		}
639		if (ret)
640			mod |= writefsinfo(dosfs, boot);
641	}
642
643	return mod;
644}
645