xref: /illumos-gate/usr/src/cmd/fs.d/pcfs/fsck/clusters.c (revision 7c478bd9)
1 /*
2  * CDDL HEADER START
3  *
4  * The contents of this file are subject to the terms of the
5  * Common Development and Distribution License, Version 1.0 only
6  * (the "License").  You may not use this file except in compliance
7  * with the License.
8  *
9  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
10  * or http://www.opensolaris.org/os/licensing.
11  * See the License for the specific language governing permissions
12  * and limitations under the License.
13  *
14  * When distributing Covered Code, include this CDDL HEADER in each
15  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
16  * If applicable, add the following below this CDDL HEADER, with the
17  * fields enclosed by brackets "[]" replaced with your own identifying
18  * information: Portions Copyright [yyyy] [name of copyright owner]
19  *
20  * CDDL HEADER END
21  */
22 /*
23  * Copyright (c) 1999,2000 by Sun Microsystems, Inc.
24  * All rights reserved.
25  */
26 
27 #pragma ident	"%Z%%M%	%I%	%E% SMI"
28 
29 /*
30  * fsck_pcfs -- routines for manipulating clusters.
31  */
32 #include <stdio.h>
33 #include <string.h>
34 #include <unistd.h>
35 #include <stdlib.h>
36 #include <libintl.h>
37 #include <errno.h>
38 #include <sys/dktp/fdisk.h>
39 #include <sys/fs/pc_fs.h>
40 #include <sys/fs/pc_dir.h>
41 #include <sys/fs/pc_label.h>
42 #include "pcfs_common.h"
43 #include "fsck_pcfs.h"
44 
45 extern	ClusterContents	TheRootDir;
46 extern	off64_t		FirstClusterOffset;
47 extern	off64_t		PartitionOffset;
48 extern	int32_t		BytesPerCluster;
49 extern	int32_t		TotalClusters;
50 extern	int32_t		LastCluster;
51 extern	int32_t		RootDirSize;
52 extern	int32_t		FATSize;
53 extern	bpb_t		TheBIOSParameterBlock;
54 extern	short		FATEntrySize;
55 extern	int		RootDirModified;
56 extern	int		OkayToRelink;
57 extern	int		ReadOnly;
58 extern	int		IsFAT32;
59 extern	int		Verbose;
60 
61 static	struct pcdir	BlankPCDIR;
62 static	CachedCluster	*ClusterCache;
63 static	ClusterInfo	**InUse;
64 static	int32_t		ReservedClusterCount;
65 static	int32_t		AllocedClusterCount;
66 static	int32_t		FreeClusterCount;
67 static	int32_t		BadClusterCount;
68 
69 /*
70  * Internal statistics
71  */
72 static	int32_t		CachedClusterCount;
73 
74 int32_t	HiddenClusterCount;
75 int32_t	FileClusterCount;
76 int32_t	DirClusterCount;
77 int32_t	HiddenFileCount;
78 int32_t	FileCount;
79 int32_t	DirCount;
80 
81 static int32_t orphanSizeLookup(int32_t clusterNum);
82 
83 static void
84 freeNameInfo(int32_t clusterNum)
85 {
86 	/* silent failure for bogus clusters */
87 	if (clusterNum < FIRST_CLUSTER || clusterNum > LastCluster)
88 		return;
89 	if (InUse[clusterNum - FIRST_CLUSTER]->path != NULL) {
90 		if (InUse[clusterNum - FIRST_CLUSTER]->path->references > 1) {
91 			InUse[clusterNum - FIRST_CLUSTER]->path->references--;
92 		} else {
93 			free(InUse[clusterNum - FIRST_CLUSTER]->path->fullName);
94 			free(InUse[clusterNum - FIRST_CLUSTER]->path);
95 		}
96 		InUse[clusterNum - FIRST_CLUSTER]->path = NULL;
97 	}
98 }
99 
100 static void
101 printOrphanPath(int32_t clusterNum)
102 {
103 	/* silent failure for bogus clusters */
104 	if (clusterNum < FIRST_CLUSTER || clusterNum > LastCluster)
105 		return;
106 	if (InUse[clusterNum - FIRST_CLUSTER]->path != NULL) {
107 		(void) printf(gettext("\nOrphaned allocation units originally "
108 		    "allocated to:\n"));
109 		(void) printf("%s\n",
110 		    InUse[clusterNum - FIRST_CLUSTER]->path->fullName);
111 		freeNameInfo(clusterNum);
112 	} else {
113 		(void) printf(gettext("\nOrphaned allocation units originally "
114 		    "allocated to an unknown file or directory:\n"));
115 		(void) printf(gettext("Orphaned chain begins with allocation "
116 		    "unit %d.\n"), clusterNum);
117 	}
118 }
119 
120 static void
121 printOrphanSize(int32_t clusterNum)
122 {
123 	int32_t size = orphanSizeLookup(clusterNum);
124 
125 	if (size > 0) {
126 		(void) printf(gettext("%d bytes in the orphaned chain of "
127 		    "allocation units.\n"), size);
128 		if (Verbose) {
129 			(void) printf(gettext("[Starting at allocation "
130 			    "unit %d]\n"), clusterNum);
131 		}
132 	}
133 }
134 
135 static void
136 printOrphanInfo(int32_t clusterNum)
137 {
138 	printOrphanPath(clusterNum);
139 	printOrphanSize(clusterNum);
140 }
141 
142 static int
143 askAboutFreeing(int32_t clusterNum)
144 {
145 	/*
146 	 * If it is not OkayToRelink, we haven't already printed the size
147 	 * of the orphaned chain.
148 	 */
149 	if (!OkayToRelink)
150 		printOrphanInfo(clusterNum);
151 	/*
152 	 *  If we are in preen mode, preenBail won't return.
153 	 */
154 	preenBail("Need user confirmation to free orphaned chain.\n");
155 
156 	(void) printf(
157 	    gettext("Free the allocation units in the orphaned chain ? "
158 	    "(y/n) "));
159 	return (yes());
160 }
161 
162 static int
163 askAboutRelink(int32_t clusterNum)
164 {
165 	/*
166 	 * Display the size of the chain for the user to consider.
167 	 */
168 	printOrphanInfo(clusterNum);
169 	/*
170 	 *  If we are in preen mode, preenBail won't return.
171 	 */
172 	preenBail("Need user confirmation to re-link orphaned chain.\n");
173 
174 	(void) printf(gettext("Re-link orphaned chain into file system ? "
175 	    "(y/n) "));
176 
177 	return (yes());
178 }
179 
180 static int
181 isHidden(int32_t clusterNum)
182 {
183 	/* silent failure for bogus clusters */
184 	if (clusterNum < FIRST_CLUSTER || clusterNum > LastCluster)
185 		return (0);
186 
187 	if (InUse[clusterNum - FIRST_CLUSTER] == NULL)
188 		return (0);
189 
190 	return (InUse[clusterNum - FIRST_CLUSTER]->flags & CLINFO_HIDDEN);
191 }
192 
193 static int
194 isInUse(int32_t clusterNum)
195 {
196 	/* silent failure for bogus clusters */
197 	if (clusterNum < FIRST_CLUSTER || clusterNum > LastCluster)
198 		return (0);
199 
200 	return ((InUse[clusterNum - FIRST_CLUSTER] != NULL) &&
201 		(InUse[clusterNum - FIRST_CLUSTER]->dirent != NULL));
202 }
203 
204 /*
205  *  Caller's may request that we cache the data from a readCluster.
206  *  The xxxClusterxxxCachexxx routines handle looking for cached data
207  *  or initially caching the data.
208  *
209  *  XXX - facilitate releasing cached data for low memory situations.
210  */
211 static CachedCluster *
212 findClusterCacheEntry(int32_t clusterNum)
213 {
214 	CachedCluster *loop = ClusterCache;
215 
216 	while (loop != NULL) {
217 		if (loop->clusterNum == clusterNum)
218 			return (loop);
219 		loop = loop->next;
220 	}
221 	return (NULL);
222 }
223 
224 static uchar_t *
225 findClusterDataInTheCache(int32_t clusterNum)
226 {
227 	CachedCluster *loop = ClusterCache;
228 
229 	while (loop) {
230 		if (loop->clusterNum == clusterNum)
231 			return (loop->clusterData.bytes);
232 		loop = loop->next;
233 	}
234 	return (NULL);
235 }
236 
237 static uchar_t *
238 addToCache(int32_t clusterNum, uchar_t *buf, int32_t *datasize)
239 {
240 	CachedCluster *new;
241 	uchar_t *cp;
242 
243 	if ((new = (CachedCluster *)malloc(sizeof (CachedCluster))) == NULL) {
244 		perror(gettext("No memory for cached cluster info"));
245 		return (buf);
246 	}
247 	new->clusterNum = clusterNum;
248 	new->modified = 0;
249 
250 	if ((cp = (uchar_t *)calloc(1, BytesPerCluster)) == NULL) {
251 		perror(gettext("No memory for cached copy of cluster"));
252 		free(new);
253 		return (buf);
254 	}
255 	(void) memcpy(cp, buf, *datasize);
256 	new->clusterData.bytes = cp;
257 
258 	if (Verbose) {
259 		(void) fprintf(stderr,
260 		    gettext("Allocation unit %d cached.\n"), clusterNum);
261 	}
262 	if (ClusterCache == NULL) {
263 		ClusterCache = new;
264 		new->next = NULL;
265 	} else if (new->clusterNum < ClusterCache->clusterNum) {
266 		new->next = ClusterCache;
267 		ClusterCache = new;
268 	} else {
269 		CachedCluster *loop = ClusterCache;
270 		CachedCluster *trailer = NULL;
271 
272 		while (loop && new->clusterNum > loop->clusterNum) {
273 			trailer = loop;
274 			loop = loop->next;
275 		}
276 		trailer->next = new;
277 		if (loop) {
278 			new->next = loop;
279 		} else {
280 			new->next = NULL;
281 		}
282 	}
283 	CachedClusterCount++;
284 	return (new->clusterData.bytes);
285 }
286 
287 static int
288 seekCluster(int fd, int32_t clusterNum)
289 {
290 	off64_t seekto;
291 	int saveError;
292 
293 	seekto = FirstClusterOffset +
294 	    ((off64_t)clusterNum - FIRST_CLUSTER) * BytesPerCluster;
295 	if (lseek64(fd, seekto, SEEK_SET) != seekto) {
296 		saveError = errno;
297 		(void) fprintf(stderr,
298 		    gettext("Seek to Allocation unit #%d failed: "),
299 		    clusterNum);
300 		(void) fprintf(stderr, strerror(saveError));
301 		(void) fprintf(stderr, "\n");
302 		return (0);
303 	}
304 	return (1);
305 }
306 
307 /*
308  *  getcluster
309  *	Get cluster bytes off the disk.  We always read those bytes into
310  *	the same static buffer.  If the caller wants his own copy of the
311  *	data he'll have to make his own copy.  We'll return all the data
312  *	read, even if it's short of a full cluster.  This is for future use
313  *	when we might want to relocate any salvagable data from bad clusters.
314  */
315 static int
316 getCluster(int fd, int32_t clusterNum, uchar_t **data, int32_t *datasize)
317 {
318 	static uchar_t *clusterBuffer = NULL;
319 	int saveError;
320 	int try;
321 
322 	*datasize = 0;
323 	*data = NULL;
324 
325 	if (clusterNum < FIRST_CLUSTER || clusterNum > LastCluster)
326 		return (RDCLUST_BADINPUT);
327 
328 	if (clusterBuffer == NULL &&
329 	    (clusterBuffer = (uchar_t *)malloc(BytesPerCluster)) == NULL) {
330 		perror(gettext("No memory for a cluster data buffer"));
331 		return (RDCLUST_MEMERR);
332 	}
333 
334 	for (try = 0; try < RDCLUST_MAX_RETRY; try++) {
335 		if (!seekCluster(fd, clusterNum))
336 			return (RDCLUST_FAIL);
337 		if ((*datasize = read(fd, clusterBuffer, BytesPerCluster)) ==
338 		    BytesPerCluster) {
339 			*data = clusterBuffer;
340 			return (RDCLUST_GOOD);
341 		}
342 	}
343 	if (*datasize >= 0) {
344 		*data = clusterBuffer;
345 		(void) fprintf(stderr,
346 		    gettext("Short read of allocation unit #%d\n"), clusterNum);
347 	} else {
348 		saveError = errno;
349 		(void) fprintf(stderr, "Allocation unit %d:", clusterNum);
350 		(void) fprintf(stderr, strerror(saveError));
351 		(void) fprintf(stderr, "\n");
352 	}
353 	return (RDCLUST_FAIL);
354 }
355 
356 static void
357 writeCachedCluster(int fd, CachedCluster *clustInfo)
358 {
359 	ssize_t bytesWritten;
360 
361 	if (ReadOnly)
362 		return;
363 
364 	if (Verbose)
365 		(void) fprintf(stderr,
366 		    gettext("Allocation unit %d modified.\n"),
367 		    clustInfo->clusterNum);
368 
369 	if (seekCluster(fd, clustInfo->clusterNum) == NULL)
370 		return;
371 
372 	if ((bytesWritten = write(fd, clustInfo->clusterData.bytes,
373 	    BytesPerCluster)) != BytesPerCluster) {
374 		if (bytesWritten < 0) {
375 			perror(gettext("Failed to write modified "
376 			    "allocation unit"));
377 		} else {
378 			(void) fprintf(stderr,
379 			    gettext("Short write of allocation unit %d\n"),
380 			    clustInfo->clusterNum);
381 		}
382 		(void) close(fd);
383 		exit(13);
384 	}
385 }
386 
387 /*
388  * It's cheaper to allocate a lot at a time; malloc overhead pushes
389  * you over the brink much more quickly if you don't.
390  * This numbers seems to be a fair trade-off between reduced malloc overhead
391  * and additional overhead by over-allocating.
392  */
393 
394 #define	CHUNKSIZE	1024
395 
396 static ClusterInfo *pool;
397 
398 static ClusterInfo *
399 newClusterInfo(void)
400 {
401 
402 	ClusterInfo *ret;
403 
404 	if (pool == NULL) {
405 		int i;
406 
407 		pool = (ClusterInfo *)malloc(sizeof (ClusterInfo) * CHUNKSIZE);
408 
409 		if (pool == NULL) {
410 			perror(
411 			    gettext("Out of memory for cluster information"));
412 			exit(9);
413 		}
414 
415 		for (i = 0; i < CHUNKSIZE - 1; i++)
416 			pool[i].nextfree = &pool[i+1];
417 
418 		pool[CHUNKSIZE-1].nextfree = NULL;
419 	}
420 	ret = pool;
421 	pool = pool->nextfree;
422 
423 	memset(ret, 0, sizeof (*ret));
424 
425 	return (ret);
426 }
427 
428 /* Should be called with verified arguments */
429 
430 static ClusterInfo *
431 cloneClusterInfo(int32_t clusterNum)
432 {
433 	ClusterInfo *cl = InUse[clusterNum - FIRST_CLUSTER];
434 
435 	if (cl->refcnt > 1) {
436 		ClusterInfo *newCl = newClusterInfo();
437 		cl->refcnt--;
438 		*newCl = *cl;
439 		newCl->refcnt = 1;
440 		if (newCl->path)
441 			newCl->path->references++;
442 		InUse[clusterNum - FIRST_CLUSTER] = newCl;
443 	}
444 	return (InUse[clusterNum - FIRST_CLUSTER]);
445 }
446 
447 static void
448 updateFlags(int32_t clusterNum, int newflags)
449 {
450 	ClusterInfo *cl = InUse[clusterNum - FIRST_CLUSTER];
451 
452 	if (cl->flags != newflags && cl->refcnt > 1)
453 		cl = cloneClusterInfo(clusterNum);
454 
455 	cl->flags = newflags;
456 }
457 
458 static void
459 freeClusterInfo(ClusterInfo *old)
460 {
461 	if (--old->refcnt <= 0) {
462 		if (old->path && --old->path->references <= 0) {
463 			free(old->path->fullName);
464 			free(old->path);
465 		}
466 		old->nextfree = pool;
467 		pool = old;
468 	}
469 }
470 
471 /*
472  * Allocate entries in our sparse array of cluster information.
473  * Returns non-zero if the structure already has been allocated
474  * (for those keeping score at home).
475  *
476  * The template parameter, if non-NULL, is used to facilitate sharing
477  * the ClusterInfo nodes for the clusters belonging to the same file.
478  * The first call to allocInUse for a new file should have *template
479  * set to 0; on return, *template then points to the newly allocated
480  * ClusterInfo.  Second and further calls keep the same value
481  * in *template and that ClusterInfo ndoe is then used for all
482  * entries in the file.  Code that modifies the ClusterInfo nodes
483  * should take care proper sharing semantics are maintained (i.e.,
484  * copy-on-write using cloneClusterInfo())
485  *
486  * The ClusterInfo used in the template is guaranted to be in use in
487  * at least one other cluster as we never return a value if we didn't
488  * set it first.  So we can overwrite it without the possibility of a leak.
489  */
490 static int
491 allocInUse(int32_t clusterNum, ClusterInfo **template)
492 {
493 	ClusterInfo *newCl;
494 
495 	if (InUse[clusterNum - FIRST_CLUSTER] != NULL)
496 		return (CLINFO_PREVIOUSLY_ALLOCED);
497 
498 	if (template != NULL && *template != NULL)
499 		newCl = *template;
500 	else {
501 		newCl = newClusterInfo();
502 		if (template)
503 			*template = newCl;
504 	}
505 
506 	InUse[clusterNum - FIRST_CLUSTER] = newCl;
507 	newCl->refcnt++;
508 
509 	return (CLINFO_NEWLY_ALLOCED);
510 }
511 
512 static void
513 markFree(int32_t clusterNum)
514 {
515 	/* silent failure for bogus clusters */
516 	if (clusterNum < FIRST_CLUSTER || clusterNum > LastCluster)
517 		return;
518 
519 	if (InUse[clusterNum - FIRST_CLUSTER]) {
520 		if (InUse[clusterNum - FIRST_CLUSTER]->saved)
521 			free(InUse[clusterNum - FIRST_CLUSTER]->saved);
522 		freeClusterInfo(InUse[clusterNum - FIRST_CLUSTER]);
523 		InUse[clusterNum - FIRST_CLUSTER] = NULL;
524 	}
525 }
526 
527 static void
528 markOrphan(int fd, int32_t clusterNum, struct pcdir *dp)
529 {
530 	/* silent failure for bogus clusters */
531 	if (clusterNum < FIRST_CLUSTER || clusterNum > LastCluster)
532 		return;
533 
534 	(void) markInUse(fd, clusterNum, dp, NULL, 0, VISIBLE, NULL);
535 	if (InUse[clusterNum - FIRST_CLUSTER] != NULL)
536 		updateFlags(clusterNum,
537 		    InUse[clusterNum - FIRST_CLUSTER]->flags | CLINFO_ORPHAN);
538 }
539 
540 static void
541 markBad(int32_t clusterNum, uchar_t *recovered, int32_t recoveredLen)
542 {
543 	/* silent failure for bogus clusters */
544 	if (clusterNum < FIRST_CLUSTER || clusterNum > LastCluster)
545 		return;
546 
547 	(void) allocInUse(clusterNum, NULL);
548 
549 	if (recoveredLen) {
550 		(void) cloneClusterInfo(clusterNum);
551 		InUse[clusterNum - FIRST_CLUSTER]->saved = recovered;
552 	}
553 	updateFlags(clusterNum,
554 	    InUse[clusterNum - FIRST_CLUSTER]->flags | CLINFO_BAD);
555 
556 	BadClusterCount++;
557 	if (Verbose)
558 		(void) fprintf(stderr,
559 		    gettext("Allocation unit %d marked bad.\n"), clusterNum);
560 }
561 
562 static void
563 clearOrphan(int32_t c)
564 {
565 	/* silent failure for bogus clusters */
566 	if (c < FIRST_CLUSTER || c > LastCluster)
567 		return;
568 	if (InUse[c - FIRST_CLUSTER] != NULL)
569 		updateFlags(c,
570 		    InUse[c - FIRST_CLUSTER]->flags & ~CLINFO_ORPHAN);
571 }
572 
573 static void
574 clearInUse(int32_t c)
575 {
576 	ClusterInfo **clp;
577 
578 	/* silent failure for bogus clusters */
579 	if (c < FIRST_CLUSTER || c > LastCluster)
580 		return;
581 
582 	clp = &InUse[c - FIRST_CLUSTER];
583 	if (*clp != NULL) {
584 		freeClusterInfo(*clp);
585 		*clp = NULL;
586 	}
587 }
588 
589 static void
590 clearAllClusters_InUse()
591 {
592 	int32_t cc;
593 	for (cc = FIRST_CLUSTER; cc < LastCluster; cc++) {
594 		clearInUse(cc);
595 	}
596 }
597 
598 static void
599 makeUseTable(void)
600 {
601 	if (InUse != NULL) {
602 		clearAllClusters_InUse();
603 		return;
604 	}
605 	if ((InUse = (ClusterInfo **)
606 	    calloc(TotalClusters, sizeof (ClusterInfo *))) == NULL) {
607 		perror(gettext("No memory for internal table"));
608 		exit(9);
609 	}
610 }
611 
612 static void
613 countClusters(void)
614 {
615 	int32_t c;
616 
617 	BadClusterCount = HiddenClusterCount =
618 	    AllocedClusterCount = FreeClusterCount = 0;
619 
620 	for (c = FIRST_CLUSTER; c < LastCluster; c++) {
621 		if (badInFAT(c)) {
622 			BadClusterCount++;
623 		} else if (isMarkedBad(c)) {
624 			/*
625 			 * This catches the bad sectors found
626 			 * during thorough verify that have never been
627 			 * allocated to a file.  Without this check, we
628 			 * count these guys as free.
629 			 */
630 			BadClusterCount++;
631 			markBadInFAT(c);
632 		} else if (isHidden(c)) {
633 			HiddenClusterCount++;
634 		} else if (isInUse(c)) {
635 			AllocedClusterCount++;
636 		} else {
637 			FreeClusterCount++;
638 		}
639 	}
640 }
641 
642 /*
643  * summarizeFAT
644  *	Mark orphans without directory entries as allocated.
645  *	XXX - these chains should be reclaimed!
646  *	XXX - merge this routine with countClusters (same loop, duh.)
647  */
648 static void
649 summarizeFAT(int fd)
650 {
651 	int32_t c;
652 	ClusterInfo *tmpl = NULL;
653 
654 	for (c = FIRST_CLUSTER; c < LastCluster; c++) {
655 		if (!freeInFAT(c) && !badInFAT(c) && !reservedInFAT(c) &&
656 		    !isInUse(c)) {
657 			(void) markInUse(fd, c, &BlankPCDIR, NULL, 0, VISIBLE,
658 				&tmpl);
659 		}
660 	}
661 }
662 
663 static void
664 getReadyToSearch(int fd)
665 {
666 	getFAT(fd);
667 	if (!IsFAT32)
668 		getRootDirectory(fd);
669 }
670 
671 
672 static char PathName[MAXPATHLEN];
673 
674 static void
675 summarize(int fd, int includeFAT)
676 {
677 	struct pcdir *ignorep1, *ignorep2 = NULL;
678 	int32_t ignore32;
679 	char ignore;
680 	int pathlen;
681 
682 	ReservedClusterCount = 0;
683 	AllocedClusterCount = 0;
684 	HiddenClusterCount = 0;
685 	FileClusterCount = 0;
686 	FreeClusterCount = 0;
687 	DirClusterCount = 0;
688 	BadClusterCount = 0;
689 	HiddenFileCount = 0;
690 	FileCount = 0;
691 	DirCount = 0;
692 	ignorep1 = ignorep2 = NULL;
693 	ignore = '\0';
694 
695 	PathName[0] = '\0';
696 	pathlen = 0;
697 
698 	getReadyToSearch(fd);
699 	/*
700 	 *  Traverse the full meta-data tree to talley what clusters
701 	 * are in use.  The root directory is an area outside of the
702 	 * file space on FAT12 and FAT16 file systems.  On FAT32 file
703 	 * systems, the root directory is in a file area cluster just
704 	 * like any other directory.
705 	 */
706 	if (!IsFAT32) {
707 		traverseFromRoot(fd, 0, PCFS_VISIT_SUBDIRS, PCFS_TRAVERSE_ALL,
708 		    ignore, &ignorep1, &ignore32, &ignorep2, PathName,
709 		    &pathlen);
710 	} else {
711 		DirCount++;
712 		traverseDir(fd, TheBIOSParameterBlock.bpb32.root_dir_clust,
713 		    0, PCFS_VISIT_SUBDIRS, PCFS_TRAVERSE_ALL, ignore,
714 		    &ignorep1, &ignore32, &ignorep2, PathName, &pathlen);
715 	}
716 
717 	if (includeFAT)
718 		summarizeFAT(fd);
719 	countClusters();
720 }
721 
722 int
723 isMarkedBad(int32_t clusterNum)
724 {
725 	/* silent failure for bogus clusters */
726 	if (clusterNum < FIRST_CLUSTER || clusterNum > LastCluster)
727 		return (0);
728 
729 	if (InUse[clusterNum - FIRST_CLUSTER] == NULL)
730 		return (0);
731 
732 	return (InUse[clusterNum - FIRST_CLUSTER]->flags & CLINFO_BAD);
733 }
734 
735 static int
736 isMarkedOrphan(int32_t clusterNum)
737 {
738 	/* silent failure for bogus clusters */
739 	if (clusterNum < FIRST_CLUSTER || clusterNum > LastCluster)
740 		return (0);
741 
742 	if (InUse[clusterNum - FIRST_CLUSTER] == NULL)
743 		return (0);
744 
745 	return (InUse[clusterNum - FIRST_CLUSTER]->flags & CLINFO_ORPHAN);
746 }
747 
748 static void
749 orphanChain(int fd, int32_t c, struct pcdir *ndp)
750 {
751 	ClusterInfo *tmpl = NULL;
752 
753 	/* silent failure for bogus clusters */
754 	if (c < FIRST_CLUSTER || c > LastCluster)
755 		return;
756 	clearInUse(c);
757 	markOrphan(fd, c, ndp);
758 	c = nextInChain(c);
759 	while (c != 0) {
760 		clearInUse(c);
761 		clearOrphan(c);
762 		(void) markInUse(fd, c, ndp, NULL, 0, VISIBLE, &tmpl);
763 		c = nextInChain(c);
764 	}
765 }
766 
767 static int32_t
768 findAFreeCluster(int32_t startAt)
769 {
770 	int32_t look = startAt;
771 
772 	for (;;) {
773 		if (freeInFAT(look)) {
774 			break;
775 		}
776 		if (look == LastCluster)
777 			look = FIRST_CLUSTER;
778 		else
779 			look++;
780 		if (look == startAt)
781 			break;
782 	}
783 	if (look != startAt)
784 		return (look);
785 	else
786 		return (0);
787 }
788 
789 static void
790 setEndOfDirectory(struct pcdir *dp)
791 {
792 	dp->pcd_filename[0] = PCD_UNUSED;
793 }
794 
795 static void
796 emergencyEndOfDirectory(int fd, int32_t secondToLast)
797 {
798 	ClusterContents dirdata;
799 	int32_t dirdatasize = 0;
800 
801 	if (readCluster(fd, secondToLast, &(dirdata.bytes), &dirdatasize,
802 	    RDCLUST_DO_CACHE) != RDCLUST_GOOD) {
803 		(void) fprintf(stderr,
804 		    gettext("Unable to read allocation unit %d.\n"),
805 		    secondToLast);
806 		(void) fprintf(stderr,
807 		    gettext("Cannot allocate a new allocation unit to hold an"
808 		    " end-of-directory marker.\nCannot access allocation unit"
809 		    " to overwrite existing directory entry with\nthe marker."
810 		    "  Needed directory truncation has failed.  Giving up.\n"));
811 		(void) close(fd);
812 		exit(11);
813 	}
814 	setEndOfDirectory(dirdata.dirp);
815 	markClusterModified(secondToLast);
816 }
817 
818 static void
819 makeNewEndOfDirectory(struct pcdir *entry, int32_t secondToLast,
820     int32_t newCluster, ClusterContents *newData)
821 {
822 	setEndOfDirectory(newData->dirp);
823 	markClusterModified(newCluster);
824 	/*
825 	 *  There are two scenarios.  One is that we truncated the
826 	 *  directory in the very beginning.  The other is that we
827 	 *  truncated it in the middle or at the end.  In the first
828 	 *  scenario, the secondToLast argument is not a valid cluster
829 	 *  (it's zero), and so we actually need to change the start
830 	 *  cluster for the directory to this new start cluster.  In
831 	 *  the second scenario, the secondToLast cluster we received
832 	 *  as an argument needs to be pointed at the new end of
833 	 *  directory.
834 	 */
835 	if (secondToLast == 0) {
836 		updateDirEnt_Start(entry, newCluster);
837 	} else {
838 		writeFATEntry(secondToLast, newCluster);
839 	}
840 	markLastInFAT(newCluster);
841 }
842 
843 static void
844 createNewEndOfDirectory(int fd, struct pcdir *entry, int32_t secondToLast)
845 {
846 	ClusterContents dirdata;
847 	int32_t dirdatasize = 0;
848 	int32_t freeCluster;
849 
850 	if (((freeCluster = findAFreeCluster(secondToLast)) != 0)) {
851 		if (readCluster(fd, freeCluster, &(dirdata.bytes),
852 		    &dirdatasize, RDCLUST_DO_CACHE) == RDCLUST_GOOD) {
853 			if (Verbose) {
854 				(void) fprintf(stderr,
855 				    gettext("Grabbed allocation unit #%d "
856 				    "for truncated\ndirectory's new end "
857 				    "of directory.\n"), freeCluster);
858 			}
859 			makeNewEndOfDirectory(entry, secondToLast,
860 			    freeCluster, &dirdata);
861 			return;
862 		}
863 	}
864 	if (secondToLast == 0) {
865 		if (freeCluster == 0) {
866 			(void) fprintf(stderr, gettext("File system full.\n"));
867 		} else {
868 			(void) fprintf(stderr,
869 			    gettext("Unable to read allocation unit %d.\n"),
870 			    freeCluster);
871 		}
872 		(void) fprintf(stderr,
873 		    gettext("Cannot allocate a new allocation unit to hold "
874 		    "an end-of-directory marker.\nNo existing directory "
875 		    "entries can be overwritten with the marker,\n"
876 		    "the only unit allocated to the directory is "
877 		    "inaccessible.\nNeeded directory truncation has failed.  "
878 		    "Giving up.\n"));
879 		(void) close(fd);
880 		exit(11);
881 	}
882 	emergencyEndOfDirectory(fd, secondToLast);
883 }
884 
885 /*
886  * truncAtCluster
887  *	Given a directory entry and a cluster number, search through
888  *	the cluster chain for the entry and make the cluster previous
889  *	to the given cluster in the chain the last cluster in the file.
890  *	The number of orphaned bytes is returned.  For a chain that's
891  *	a directory we need to do some special handling, since we'll be
892  *	getting rid of the end of directory notice by truncating.
893  */
894 static int64_t
895 truncAtCluster(int fd, struct pcdir *entry, int32_t cluster)
896 {
897 	uint32_t oldSize, newSize;
898 	int32_t prev, count, follow;
899 	int dir = (entry->pcd_attr & PCA_DIR);
900 
901 	prev = 0; count = 0;
902 	follow = extractStartCluster(entry);
903 	while (follow != cluster && follow >= FIRST_CLUSTER &&
904 	    follow <= LastCluster) {
905 		prev = follow;
906 		count++;
907 		follow = nextInChain(follow);
908 	}
909 	if (follow != cluster) {
910 		/*
911 		 *  We didn't find the cluster they wanted to trunc at
912 		 *  anywhere in the entry's chain.  So we'll leave the
913 		 *  entry alone, and return a negative value so they
914 		 *  can know something is wrong.
915 		 */
916 		return (-1);
917 	}
918 	if (Verbose) {
919 		(void) fprintf(stderr,
920 		    gettext("Chain truncation at unit #%d\n"), cluster);
921 	}
922 	if (!dir) {
923 		oldSize = extractSize(entry);
924 		newSize = count *
925 		    TheBIOSParameterBlock.bpb.sectors_per_cluster *
926 		    TheBIOSParameterBlock.bpb.bytes_per_sector;
927 		if (newSize == 0)
928 			updateDirEnt_Start(entry, 0);
929 	} else {
930 		newSize = 0;
931 	}
932 	updateDirEnt_Size(entry, newSize);
933 	if (dir) {
934 		createNewEndOfDirectory(fd, entry, prev);
935 	} else if (prev != 0) {
936 		markLastInFAT(prev);
937 	}
938 	if (dir) {
939 		/*
940 		 * We don't really know what the size of a directory is
941 		 * but it is important for us to know if this truncation
942 		 * results in an orphan with any size.  The value we
943 		 * return from this routine for a normal file is the
944 		 * number of bytes left in the chain.  For a directory
945 		 * we can't be exact, and the caller doesn't really
946 		 * expect us to be.  For a directory the caller only
947 		 * cares if there are zero bytes left or more than
948 		 * zero bytes left.  We'll return 1 to indicate
949 		 * more than zero.
950 		 */
951 		if ((follow = nextInChain(follow)) != 0)
952 			return (1);
953 		else
954 			return (0);
955 	}
956 	/*
957 	 * newSize should always be smaller than the old one, since
958 	 * we are decreasing the number of clusters allocated to the file.
959 	 */
960 	return ((int64_t)oldSize - (int64_t)newSize);
961 }
962 
963 static struct pcdir *
964 updateOrphanedChainMetadata(int fd, struct pcdir *dp, int32_t endCluster,
965     int isBad)
966 {
967 	struct pcdir *ndp = NULL;
968 	int64_t remainder;
969 	char *newName = NULL;
970 	int chosenName;
971 	int dir = (dp->pcd_attr & PCA_DIR);
972 
973 	/*
974 	 *  If the truncation fails, (which ought not to happen),
975 	 *  there's no need to go any further, we just return
976 	 *  a null value for the new directory entry pointer.
977 	 */
978 	remainder = truncAtCluster(fd, dp, endCluster);
979 	if (remainder < 0)
980 		return (ndp);
981 	if (!dir && isBad) {
982 		/*
983 		 *  Subtract out the bad cluster from the remaining size
984 		 *  We always assume the cluster being deleted from the
985 		 *  file is full size, but that might not be the case
986 		 *  for the last cluster of the file, so that is why
987 		 *  we check for negative remainder value.
988 		 */
989 		remainder -= TheBIOSParameterBlock.bpb.sectors_per_cluster *
990 		    TheBIOSParameterBlock.bpb.bytes_per_sector;
991 		if (remainder < 0)
992 			remainder = 0;
993 	}
994 	/*
995 	 * Build a new directory entry for the rest of the chain.
996 	 * Later, if the user okays it, we'll link this entry into the
997 	 * root directory.  The new entry will start out as a
998 	 * copy of the truncated entry.
999 	 */
1000 	if ((remainder != 0) &&
1001 	    ((newName = nextAvailableCHKName(&chosenName)) != NULL) &&
1002 	    ((ndp = newDirEnt(dp)) != NULL)) {
1003 		if (Verbose) {
1004 			if (dir)
1005 				(void) fprintf(stderr,
1006 				    gettext("Orphaned directory chain.\n"));
1007 			else
1008 				(void) fprintf(stderr,
1009 				    gettext("Orphaned chain, %u bytes.\n"),
1010 				    (uint32_t)remainder);
1011 		}
1012 		if (!dir)
1013 			updateDirEnt_Size(ndp, (uint32_t)remainder);
1014 		if (isBad)
1015 			updateDirEnt_Start(ndp, nextInChain(endCluster));
1016 		else
1017 			updateDirEnt_Start(ndp, endCluster);
1018 		updateDirEnt_Name(ndp, newName);
1019 		addEntryToCHKList(chosenName);
1020 	}
1021 	return (ndp);
1022 }
1023 
1024 /*
1025  *  splitChain()
1026  *
1027  *	split a cluster allocation chain into two cluster chains
1028  *	around a given cluster (problemCluster).  This results in two
1029  *	separate directory entries; the original (dp), and one we hope
1030  *	to create and return a pointer to to the caller (*newdp).
1031  *	This second entry is the orphan chain, and it may end up in
1032  *	the root directory as a FILEnnnn.CHK file.  We also return the
1033  *	starting cluster of the orphan chain to the caller (*orphanStart).
1034  */
1035 void
1036 splitChain(int fd, struct pcdir *dp, int32_t problemCluster,
1037     struct pcdir **newdp, int32_t *orphanStart)
1038 {
1039 	struct pcdir *ndp = NULL;
1040 	int isBad = isMarkedBad(problemCluster);
1041 
1042 	ndp = updateOrphanedChainMetadata(fd, dp, problemCluster, isBad);
1043 	*newdp = ndp;
1044 	clearInUse(problemCluster);
1045 	if (isBad) {
1046 		clearOrphan(problemCluster);
1047 		*orphanStart = nextInChain(problemCluster);
1048 		orphanChain(fd, *orphanStart, ndp);
1049 		markBadInFAT(problemCluster);
1050 	} else {
1051 		*orphanStart = problemCluster;
1052 		orphanChain(fd, problemCluster, ndp);
1053 	}
1054 }
1055 
1056 /*
1057  *  freeOrphan
1058  *
1059  *  User has requested that an orphaned cluster chain be freed back
1060  *  into the file area.
1061  */
1062 static void
1063 freeOrphan(int32_t c)
1064 {
1065 	int32_t n;
1066 
1067 	/*
1068 	 * Free the directory entry we explicitly created for
1069 	 * the orphaned clusters.
1070 	 */
1071 	if (InUse[c - FIRST_CLUSTER]->dirent != NULL)
1072 		free(InUse[c - FIRST_CLUSTER]->dirent);
1073 	/*
1074 	 * Then mark the clusters themselves as available.
1075 	 */
1076 	do {
1077 		n = nextInChain(c);
1078 		markFreeInFAT(c);
1079 		markFree(c);
1080 		c = n;
1081 	} while (c != 0);
1082 }
1083 
1084 /*
1085  *  Rewrite the InUse field for a cluster chain.  Can be used on a partial
1086  *  chain if provided with a stopAtCluster.
1087  */
1088 static void
1089 redoInUse(int fd, int32_t c, struct pcdir *ndp, int32_t stopAtCluster)
1090 {
1091 	while (c && c != stopAtCluster) {
1092 		clearInUse(c);
1093 		(void) markInUse(fd, c, ndp, NULL, 0, VISIBLE, NULL);
1094 		c = nextInChain(c);
1095 	}
1096 }
1097 
1098 static struct pcdir *
1099 orphanDirEntLookup(int32_t clusterNum)
1100 {
1101 	if (clusterNum < FIRST_CLUSTER || clusterNum > LastCluster)
1102 		return (NULL);
1103 
1104 	if (isInUse(clusterNum)) {
1105 		return (InUse[clusterNum - FIRST_CLUSTER]->dirent);
1106 	} else {
1107 		return (NULL);
1108 	}
1109 }
1110 
1111 static int32_t
1112 orphanSizeLookup(int32_t clusterNum)
1113 {
1114 	/* silent failure for bogus clusters */
1115 	if (clusterNum < FIRST_CLUSTER || clusterNum > LastCluster)
1116 		return (-1);
1117 
1118 	if (isInUse(clusterNum)) {
1119 		return (extractSize(InUse[clusterNum - FIRST_CLUSTER]->dirent));
1120 	} else {
1121 		return (-1);
1122 	}
1123 }
1124 
1125 /*
1126  *  linkOrphan
1127  *
1128  *  User has requested that an orphaned cluster chain be brought back
1129  *  into the file system.  So we have to make a new directory entry
1130  *  in the root directory and point it at the cluster chain.
1131  */
1132 static void
1133 linkOrphan(int fd, int32_t start)
1134 {
1135 	struct pcdir *newEnt = NULL;
1136 	struct pcdir *dp;
1137 
1138 	if ((dp = orphanDirEntLookup(start)) != NULL) {
1139 		newEnt = addRootDirEnt(fd, dp);
1140 	} else {
1141 		(void) printf(gettext("Re-link of orphaned chain failed."
1142 		    "  Allocation units will remain orphaned.\n"));
1143 	}
1144 	/*
1145 	 *  A cluster isn't really InUse() unless it is referenced,
1146 	 *  so if newEnt is NULL here, we are in effect using markInUse()
1147 	 *  to note that the cluster is NOT in use.
1148 	 */
1149 	redoInUse(fd, start, newEnt, 0);
1150 }
1151 
1152 /*
1153  *  relinkCreatedOrphans
1154  *
1155  *  While marking clusters as bad, we can create orphan cluster
1156  *  chains.  Since we were the ones doing the marking, we were able to
1157  *  keep track of the orphans we created.  Now we want to go through
1158  *  all those chains and either get them back into the file system or
1159  *  free them depending on the user's input.
1160  */
1161 static void
1162 relinkCreatedOrphans(int fd)
1163 {
1164 	int32_t c;
1165 
1166 	for (c = FIRST_CLUSTER; c < LastCluster; c++) {
1167 		if (isMarkedOrphan(c)) {
1168 			if (OkayToRelink && askAboutRelink(c)) {
1169 				linkOrphan(fd, c);
1170 			} else if (askAboutFreeing(c)) {
1171 				freeOrphan(c);
1172 			}
1173 			clearOrphan(c);
1174 		}
1175 	}
1176 }
1177 
1178 /*
1179  *  relinkFATOrphans
1180  *
1181  *  We want to find orphans not represented in the meta-data.
1182  *  These are chains marked in the FAT as being in use but
1183  *  not referenced anywhere by any directory entries.
1184  *  We'll go through the whole FAT and mark the first cluster
1185  *  in any such chain as an orphan.  Then we can just use
1186  *  the relinkCreatedOrphans routine to get them back into the
1187  *  file system or free'ed depending on the user's input.
1188  */
1189 static void
1190 relinkFATOrphans(int fd)
1191 {
1192 	struct pcdir *ndp = NULL;
1193 	int32_t cc, c, n;
1194 	int32_t bpc, newSize;
1195 	char *newName;
1196 	int chosenName;
1197 
1198 	for (c = FIRST_CLUSTER; c < LastCluster; c++) {
1199 		if (freeInFAT(c) || badInFAT(c) ||
1200 		    reservedInFAT(c) || isInUse(c))
1201 			continue;
1202 		cc = 1;
1203 		n = c;
1204 		while (n = nextInChain(n))
1205 			cc++;
1206 		bpc = TheBIOSParameterBlock.bpb.sectors_per_cluster *
1207 		    TheBIOSParameterBlock.bpb.bytes_per_sector;
1208 		newSize = cc * bpc;
1209 		if (((newName = nextAvailableCHKName(&chosenName)) != NULL) &&
1210 		    ((ndp = newDirEnt(NULL)) != NULL)) {
1211 			updateDirEnt_Size(ndp, newSize);
1212 			updateDirEnt_Start(ndp, c);
1213 			updateDirEnt_Name(ndp, newName);
1214 			addEntryToCHKList(chosenName);
1215 		}
1216 		orphanChain(fd, c, ndp);
1217 	}
1218 	relinkCreatedOrphans(fd);
1219 }
1220 
1221 static void
1222 relinkOrphans(int fd)
1223 {
1224 	relinkCreatedOrphans(fd);
1225 	relinkFATOrphans(fd);
1226 }
1227 
1228 static void
1229 checkForFATLoop(int32_t clusterNum)
1230 {
1231 	int32_t prev = clusterNum;
1232 	int32_t follow;
1233 
1234 	if (clusterNum < FIRST_CLUSTER || clusterNum > LastCluster)
1235 		return;
1236 
1237 	follow = nextInChain(clusterNum);
1238 	while (follow != clusterNum && follow >= FIRST_CLUSTER &&
1239 	    follow <= LastCluster) {
1240 		prev = follow;
1241 		follow = nextInChain(follow);
1242 	}
1243 	if (follow == clusterNum) {
1244 		/*
1245 		 * We found a loop.  Eradicate it by changing
1246 		 * the last cluster in the loop to be last
1247 		 * in the chain instead instead of pointing
1248 		 * back to the first cluster.
1249 		 */
1250 		markLastInFAT(prev);
1251 	}
1252 }
1253 
1254 static void
1255 sharedChainError(int fd, int32_t clusterNum, struct pcdir *badEntry)
1256 {
1257 	/*
1258 	 * If we have shared clusters, it is either because the
1259 	 * cluster somehow got assigned to multiple files and/or
1260 	 * because of a loop in the cluster chain.  In either
1261 	 * case we want to truncate the offending file at the
1262 	 * cluster of contention.  Then, we will want to run
1263 	 * through the remainder of the chain. If we find ourselves
1264 	 * back at the top, we will know there is a loop in the
1265 	 * FAT we need to remove.
1266 	 */
1267 	if (Verbose)
1268 		(void) fprintf(stderr,
1269 		    gettext("Truncating chain due to duplicate allocation of "
1270 		    "unit %d.\n"), clusterNum);
1271 	/*
1272 	 * Note that we don't orphan anything here, because the duplicate
1273 	 * part of the chain may be part of another valid chain.
1274 	 */
1275 	(void) truncAtCluster(fd, badEntry, clusterNum);
1276 	checkForFATLoop(clusterNum);
1277 }
1278 
1279 void
1280 truncChainWithBadCluster(int fd, struct pcdir *dp, int32_t startCluster)
1281 {
1282 	struct pcdir *orphanEntry;
1283 	int32_t orphanStartCluster;
1284 	int32_t c = startCluster;
1285 
1286 	while (c != 0) {
1287 		if (isMarkedBad(c)) {
1288 			/*
1289 			 *  splitChain() truncates the current guy and
1290 			 *  then makes an orphan chain out of the remaining
1291 			 *  clusters.  When we come back from the split
1292 			 *  we'll want to continue looking for bad clusters
1293 			 *  in the orphan chain.
1294 			 */
1295 			splitChain(fd, dp, c,
1296 			    &orphanEntry, &orphanStartCluster);
1297 			/*
1298 			 *  There is a chance that we weren't able or weren't
1299 			 *  required to make a directory entry for the
1300 			 *  remaining clusters.  In that case we won't go
1301 			 *  on, because we couldn't make any more splits
1302 			 *  anyway.
1303 			 */
1304 			if (orphanEntry == NULL)
1305 				break;
1306 			c = orphanStartCluster;
1307 			dp = orphanEntry;
1308 			continue;
1309 		}
1310 		c = nextInChain(c);
1311 	}
1312 }
1313 
1314 int32_t
1315 nextInChain(int32_t currentCluster)
1316 {
1317 	int32_t nextCluster;
1318 
1319 	/* silent failure for bogus clusters */
1320 	if (currentCluster < FIRST_CLUSTER || currentCluster > LastCluster)
1321 		return (0);
1322 
1323 	/*
1324 	 * Look up FAT entry of next link in cluster chain,
1325 	 * if this one is the last one return 0 as the next link.
1326 	 */
1327 	nextCluster = readFATEntry(currentCluster);
1328 	if (nextCluster < FIRST_CLUSTER || nextCluster > LastCluster)
1329 		return (0);
1330 
1331 	return (nextCluster);
1332 }
1333 
1334 /*
1335  * findImpactedCluster
1336  *
1337  *	Called when someone modifies what they believe might be a cached
1338  *	cluster entry, but when	they only have a directory entry pointer
1339  *	and not the cluster number.  We have to go dig up what cluster
1340  *	they are modifying.
1341  */
1342 int32_t
1343 findImpactedCluster(struct pcdir *modified)
1344 {
1345 	CachedCluster *loop;
1346 	/*
1347 	 * Check to see if it's in the root directory first
1348 	 */
1349 	if (!IsFAT32 && ((uchar_t *)modified >= TheRootDir.bytes) &&
1350 	    ((uchar_t *)modified < TheRootDir.bytes + RootDirSize))
1351 		return (FAKE_ROOTDIR_CLUST);
1352 
1353 	loop = ClusterCache;
1354 	while (loop) {
1355 		if (((uchar_t *)modified >= loop->clusterData.bytes) &&
1356 		    ((uchar_t *)modified <
1357 		    (loop->clusterData.bytes + BytesPerCluster))) {
1358 			return (loop->clusterNum);
1359 		}
1360 		loop = loop->next;
1361 	}
1362 	/*
1363 	 *  Guess it wasn't cached after all...
1364 	 */
1365 	return (0);
1366 }
1367 
1368 void
1369 writeClusterMods(int fd)
1370 {
1371 	CachedCluster *loop = ClusterCache;
1372 
1373 	while (loop) {
1374 		if (loop->modified)
1375 			writeCachedCluster(fd, loop);
1376 		loop = loop->next;
1377 	}
1378 }
1379 
1380 void
1381 squirrelPath(struct nameinfo *pathInfo, int32_t clusterNum)
1382 {
1383 	/* silent failure for bogus clusters */
1384 	if (clusterNum < FIRST_CLUSTER || clusterNum > LastCluster)
1385 		return;
1386 	if (InUse[clusterNum - FIRST_CLUSTER] == NULL)
1387 		return;
1388 	InUse[clusterNum - FIRST_CLUSTER]->path = pathInfo;
1389 }
1390 
1391 int
1392 markInUse(int fd, int32_t clusterNum, struct pcdir *referencer, struct
1393     pcdir *longRef, int32_t longStartCluster, int isHiddenFile,
1394     ClusterInfo **template)
1395 {
1396 	int alreadyMarked;
1397 	ClusterInfo *cl;
1398 
1399 	/* silent failure for bogus clusters */
1400 	if (clusterNum < FIRST_CLUSTER || clusterNum > LastCluster)
1401 		return (CLINFO_NEWLY_ALLOCED);
1402 
1403 	alreadyMarked = allocInUse(clusterNum, template);
1404 	if ((alreadyMarked == CLINFO_PREVIOUSLY_ALLOCED) &&
1405 	    (isInUse(clusterNum))) {
1406 		sharedChainError(fd, clusterNum, referencer);
1407 		return (CLINFO_PREVIOUSLY_ALLOCED);
1408 	}
1409 	cl = InUse[clusterNum - FIRST_CLUSTER];
1410 	/*
1411 	 * If Cl is newly allocated (refcnt <= 1) we must fill in the fields.
1412 	 * If Cl has different fields, we must clone it.
1413 	 */
1414 
1415 	if (cl->refcnt <= 1 || cl->dirent != referencer ||
1416 	    cl->longent != longRef ||
1417 	    cl->longEntStartClust != longStartCluster) {
1418 		if (cl->refcnt > 1)
1419 			cl = cloneClusterInfo(clusterNum);
1420 		cl->dirent = referencer;
1421 		cl->longent = longRef;
1422 		cl->longEntStartClust = longStartCluster;
1423 		if (isHiddenFile)
1424 			cl->flags |= CLINFO_HIDDEN;
1425 
1426 		/*
1427 		 * Return cl as the template to use for other clusters in
1428 		 * this file
1429 		 */
1430 		if (template)
1431 			*template = cl;
1432 	}
1433 	return (CLINFO_NEWLY_ALLOCED);
1434 }
1435 
1436 void
1437 markClusterModified(int32_t clusterNum)
1438 {
1439 	CachedCluster *c;
1440 
1441 	if (clusterNum == FAKE_ROOTDIR_CLUST) {
1442 		RootDirModified = 1;
1443 		return;
1444 	}
1445 
1446 	/* silent failure for bogus clusters */
1447 	if (clusterNum < FIRST_CLUSTER || clusterNum > LastCluster)
1448 		return;
1449 
1450 	if (c = findClusterCacheEntry(clusterNum)) {
1451 		c->modified = 1;
1452 	} else {
1453 		(void) fprintf(stderr,
1454 		    gettext("Unexpected internal error: "
1455 		    "Missing cache entry [%d]\n"), clusterNum);
1456 		exit(10);
1457 	}
1458 }
1459 
1460 /*
1461  *  readCluster
1462  *	caller wants to read cluster clusterNum.  We should return
1463  *	a pointer to the read data in "data", and fill in the number
1464  *	of bytes read in "datasize".  If shouldCache is non-zero
1465  *	we should allocate cache space to the cluster, otherwise we
1466  *	just return a pointer to a buffer we re-use whenever cacheing
1467  *	is not requested.
1468  */
1469 int
1470 readCluster(int fd, int32_t clusterNum, uchar_t **data, int32_t *datasize,
1471     int shouldCache)
1472 {
1473 	uchar_t *newBuf;
1474 	int rv;
1475 
1476 	*data = NULL;
1477 	if ((*data = findClusterDataInTheCache(clusterNum)) != NULL) {
1478 		*datasize = BytesPerCluster;
1479 		return (RDCLUST_GOOD);
1480 	}
1481 
1482 	rv = getCluster(fd, clusterNum, &newBuf, datasize);
1483 	if (rv != RDCLUST_GOOD)
1484 		return (rv);
1485 
1486 	/*
1487 	 * Caller requested we NOT cache the data from this read.
1488 	 * So, we just return a pointer to the common data buffer.
1489 	 */
1490 	if (shouldCache == 0) {
1491 		*data = newBuf;
1492 		return (rv);
1493 	}
1494 
1495 	/*
1496 	 * Caller requested we cache the data from this read.
1497 	 * So, if we have some data, add it to the cache by
1498 	 * copying it out of the common buffer into new storage.
1499 	 */
1500 	if (*datasize > 0)
1501 		*data = addToCache(clusterNum, newBuf, datasize);
1502 	return (rv);
1503 }
1504 
1505 void
1506 findBadClusters(int fd)
1507 {
1508 	int32_t clusterCount;
1509 	int32_t datasize;
1510 	uchar_t *data;
1511 
1512 	BadClusterCount = 0;
1513 	makeUseTable();
1514 	(void) printf(gettext("** Scanning allocation units\n"));
1515 	for (clusterCount = FIRST_CLUSTER;
1516 	    clusterCount < LastCluster; clusterCount++) {
1517 		if (readCluster(fd, clusterCount,
1518 		    &data, &datasize, RDCLUST_DONT_CACHE) < 0) {
1519 			if (Verbose)
1520 			    (void) fprintf(stderr,
1521 				gettext("\nUnreadable allocation unit %d.\n"),
1522 				clusterCount);
1523 			markBad(clusterCount, data, datasize);
1524 		}
1525 		/*
1526 		 *  Progress meter, display a '.' for every 1000 clusters
1527 		 *  processed.  We don't want to display this when
1528 		 *  we are in verbose mode; verbose mode progress is
1529 		 *  shown by displaying each file name as it is found.
1530 		 */
1531 		if (!Verbose && clusterCount % 1000 == 0)
1532 			(void) printf(".");
1533 	}
1534 	(void) printf(gettext("..done\n"));
1535 }
1536 
1537 void
1538 scanAndFixMetadata(int fd)
1539 {
1540 	/*
1541 	 * First we initialize a few things.
1542 	 */
1543 	makeUseTable();
1544 	getReadyToSearch(fd);
1545 	createCHKNameList(fd);
1546 
1547 	/*
1548 	 * Make initial scan, taking into account any effect that
1549 	 * the bad clusters we may have already discovered have
1550 	 * on meta-data.  We may break up some cluster chains
1551 	 * during this period.  The relinkCreatedOrphans() call
1552 	 * will then give the user the chance to recover stuff
1553 	 * we've created.
1554 	 */
1555 	(void) printf(gettext("** Scanning file system meta-data\n"));
1556 	summarize(fd, NO_FAT_IN_SUMMARY);
1557 	if (Verbose)
1558 		printSummary(stderr);
1559 	(void) printf(gettext("** Correcting any meta-data discrepancies\n"));
1560 	relinkCreatedOrphans(fd);
1561 
1562 	/*
1563 	 * Clear our usage table and go back over everything, this
1564 	 * time including looking for clusters floating free in the FAT.
1565 	 * This may include clusters the user chose to free during the
1566 	 * relink phase.
1567 	 */
1568 	makeUseTable();
1569 	summarize(fd, INCLUDE_FAT_IN_SUMMARY);
1570 	relinkOrphans(fd);
1571 }
1572 
1573 void
1574 printSummary(FILE *outDest)
1575 {
1576 	(void) fprintf(outDest,
1577 	    gettext("%llu bytes.\n"),
1578 	    (uint64_t)
1579 	    TotalClusters * TheBIOSParameterBlock.bpb.sectors_per_cluster *
1580 	    TheBIOSParameterBlock.bpb.bytes_per_sector);
1581 	(void) fprintf(outDest,
1582 	    gettext("%llu bytes in bad sectors.\n"),
1583 	    (uint64_t)
1584 	    BadClusterCount * TheBIOSParameterBlock.bpb.sectors_per_cluster *
1585 	    TheBIOSParameterBlock.bpb.bytes_per_sector);
1586 	(void) fprintf(outDest,
1587 	    gettext("%llu bytes in %d directories.\n"),
1588 	    (uint64_t)
1589 	    DirClusterCount * TheBIOSParameterBlock.bpb.sectors_per_cluster *
1590 	    TheBIOSParameterBlock.bpb.bytes_per_sector, DirCount);
1591 	if (HiddenClusterCount) {
1592 		(void) fprintf(outDest,
1593 		    gettext("%llu bytes in %d hidden files.\n"),
1594 		    (uint64_t)HiddenClusterCount *
1595 		    TheBIOSParameterBlock.bpb.sectors_per_cluster *
1596 		    TheBIOSParameterBlock.bpb.bytes_per_sector,
1597 		    HiddenFileCount);
1598 	}
1599 	(void) fprintf(outDest,
1600 	    gettext("%llu bytes in %d files.\n"),
1601 	    (uint64_t)
1602 	    FileClusterCount * TheBIOSParameterBlock.bpb.sectors_per_cluster *
1603 	    TheBIOSParameterBlock.bpb.bytes_per_sector, FileCount);
1604 	(void) fprintf(outDest,
1605 	    gettext("%llu bytes free.\n"), (uint64_t)FreeClusterCount *
1606 	    TheBIOSParameterBlock.bpb.sectors_per_cluster *
1607 	    TheBIOSParameterBlock.bpb.bytes_per_sector);
1608 	(void) fprintf(outDest,
1609 	    gettext("%d bytes per allocation unit.\n"),
1610 	    TheBIOSParameterBlock.bpb.sectors_per_cluster *
1611 	    TheBIOSParameterBlock.bpb.bytes_per_sector);
1612 	(void) fprintf(outDest,
1613 	    gettext("%d total allocation units.\n"), TotalClusters);
1614 	if (ReservedClusterCount)
1615 	    (void) fprintf(outDest, gettext("%d reserved allocation units.\n"),
1616 		ReservedClusterCount);
1617 	(void) fprintf(outDest,
1618 	    gettext("%d available allocation units.\n"), FreeClusterCount);
1619 }
1620