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