xref: /titanic_52/usr/src/cmd/fs.d/pcfs/fsck/dir.c (revision 9acbbeaf2a1ffe5c14b244867d427714fab43c5c)
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 directories.
31  */
32 #include <stdio.h>
33 #include <string.h>
34 #include <unistd.h>
35 #include <stdlib.h>
36 #include <libintl.h>
37 #include <ctype.h>
38 #include <sys/param.h>
39 #include <sys/time.h>
40 #include <sys/dktp/fdisk.h>
41 #include <sys/fs/pc_fs.h>
42 #include <sys/fs/pc_dir.h>
43 #include <sys/fs/pc_label.h>
44 #include "pcfs_common.h"
45 #include "fsck_pcfs.h"
46 
47 extern	int32_t	HiddenClusterCount;
48 extern	int32_t	FileClusterCount;
49 extern	int32_t	DirClusterCount;
50 extern	int32_t	HiddenFileCount;
51 extern	int32_t	LastCluster;
52 extern	int32_t	FileCount;
53 extern	int32_t	BadCount;
54 extern	int32_t	DirCount;
55 extern	int32_t	FATSize;
56 extern	off64_t	PartitionOffset;
57 extern	bpb_t	TheBIOSParameterBlock;
58 extern	int	ReadOnly;
59 extern	int	IsFAT32;
60 extern	int	Verbose;
61 
62 static uchar_t *CHKsList = NULL;
63 
64 ClusterContents	TheRootDir;
65 int32_t	RootDirSize;
66 int	RootDirModified;
67 int	OkayToRelink = 1;
68 
69 /*
70  *  We import these routines from the pc_subr.c file in the kernel.
71  */
72 extern void pc_tvtopct(timestruc_t *, struct pctime *);
73 extern int pc_validchar(char);
74 
75 /*
76  * We have a bunch of routines for handling CHK names.  A CHK name is
77  * simply a file name of the form "FILEnnnn.CHK", where the n's are the
78  * digits in the numbers from 1 to 9999.  There are always four digits
79  * used, leading zeros are added as necessary.
80  *
81  * We use CHK names to link orphaned cluster chains back into the file
82  * system's root directory under an auspicious name so that the user
83  * may be able to recover some of their data.
84  *
85  * We use these routines to ensure CHK names we use don't conflict
86  * with any already present in the file system.
87  */
88 static int
89 hasCHKName(struct pcdir *dp)
90 {
91 	return (dp->pcd_filename[CHKNAME_F] == 'F' &&
92 	    dp->pcd_filename[CHKNAME_I] == 'I' &&
93 	    dp->pcd_filename[CHKNAME_L] == 'L' &&
94 	    dp->pcd_filename[CHKNAME_E] == 'E' &&
95 	    isdigit(dp->pcd_filename[CHKNAME_THOUSANDS]) &&
96 	    isdigit(dp->pcd_filename[CHKNAME_HUNDREDS]) &&
97 	    isdigit(dp->pcd_filename[CHKNAME_TENS]) &&
98 	    isdigit(dp->pcd_filename[CHKNAME_ONES]) &&
99 	    dp->pcd_ext[CHKNAME_C] == 'C' &&
100 	    dp->pcd_ext[CHKNAME_H] == 'H' &&
101 	    dp->pcd_ext[CHKNAME_K] == 'K');
102 }
103 
104 void
105 addEntryToCHKList(int chkNumber)
106 {
107 	/* silent failure on bogus value */
108 	if (chkNumber < 0 || chkNumber > MAXCHKVAL)
109 		return;
110 	CHKsList[chkNumber / NBBY] |= (1 << (chkNumber % NBBY));
111 }
112 
113 static void
114 addToCHKList(struct pcdir *dp)
115 {
116 	int chknum;
117 
118 	chknum = 1000 * (dp->pcd_filename[CHKNAME_THOUSANDS] - '0');
119 	chknum += 100 * (dp->pcd_filename[CHKNAME_HUNDREDS] - '0');
120 	chknum += 10 * (dp->pcd_filename[CHKNAME_TENS] - '0');
121 	chknum += (dp->pcd_filename[CHKNAME_ONES] - '0');
122 	addEntryToCHKList(chknum);
123 }
124 
125 static int
126 inUseCHKName(int chkNumber)
127 {
128 	return (CHKsList[chkNumber / NBBY] & (1 << (chkNumber % NBBY)));
129 }
130 
131 static void
132 appendToPath(struct pcdir *dp, char *thePath, int *theLen)
133 {
134 	int i = 0;
135 
136 	/*
137 	 * Sometimes caller doesn't care about keeping track of the path
138 	 */
139 	if (thePath == NULL)
140 		return;
141 
142 	/*
143 	 *  Prepend /
144 	 */
145 	if (*theLen < MAXPATHLEN)
146 		*(thePath + (*theLen)++) = '/';
147 	/*
148 	 *  Print out the file name part, but only up to the first
149 	 *  space.
150 	 */
151 	while (*theLen < MAXPATHLEN && i < PCFNAMESIZE) {
152 		/*
153 		 *  When we start seeing spaces we assume that's the
154 		 *  end of the interesting characters in the name.
155 		 */
156 		if ((dp->pcd_filename[i] == ' ') ||
157 		    !(pc_validchar(dp->pcd_filename[i])))
158 			break;
159 		*(thePath + (*theLen)++) = dp->pcd_filename[i++];
160 	}
161 	/*
162 	 *  Leave now, if we don't have an extension (or room for one)
163 	 */
164 	if ((dp->pcd_ext[i] == ' ') || ((*theLen) >= MAXPATHLEN) ||
165 	    (!(pc_validchar(dp->pcd_ext[i]))))
166 		return;
167 	/*
168 	 *  Tack on the extension
169 	 */
170 	*(thePath + (*theLen)++) = '.';
171 	i = 0;
172 	while ((*theLen < MAXPATHLEN) && (i < PCFEXTSIZE)) {
173 		if ((dp->pcd_ext[i] == ' ') || !(pc_validchar(dp->pcd_ext[i])))
174 			break;
175 		*(thePath + (*theLen)++) = dp->pcd_ext[i++];
176 	}
177 }
178 
179 static void
180 printName(FILE *outDest, struct pcdir *dp)
181 {
182 	int i;
183 	for (i = 0; i < PCFNAMESIZE; i++) {
184 		if ((dp->pcd_filename[i] == ' ') ||
185 		    !(pc_validchar(dp->pcd_filename[i])))
186 			break;
187 		(void) fprintf(outDest, "%c", dp->pcd_filename[i]);
188 	}
189 	(void) fprintf(outDest, ".");
190 	for (i = 0; i < PCFEXTSIZE; i++) {
191 		if (!(pc_validchar(dp->pcd_ext[i])))
192 			break;
193 		(void) fprintf(outDest, "%c", dp->pcd_ext[i]);
194 	}
195 }
196 
197 /*
198  *  sanityCheckSize
199  *	Make sure the size in the directory entry matches what is
200  *	actually allocated.  If there is a mismatch, orphan all
201  *	the allocated clusters.  Returns SIZE_MATCHED if everything matches
202  *	up, TRUNCATED to indicate truncation was necessary.
203  */
204 static int
205 sanityCheckSize(int fd, struct pcdir *dp, int32_t actualClusterCount,
206     int isDir, int32_t startCluster, struct nameinfo *fullPathName,
207     struct pcdir **orphanEntry)
208 {
209 	uint32_t sizeFromDir;
210 	int32_t ignorei = 0;
211 	int64_t bpc;
212 
213 	bpc = TheBIOSParameterBlock.bpb.sectors_per_cluster *
214 	    TheBIOSParameterBlock.bpb.bytes_per_sector;
215 	sizeFromDir = extractSize(dp);
216 	if (isDir) {
217 		if (sizeFromDir == 0)
218 			return (SIZE_MATCHED);
219 	} else {
220 		if ((sizeFromDir > ((actualClusterCount - 1) * bpc)) &&
221 		    (sizeFromDir <= (actualClusterCount * bpc)))
222 			return (SIZE_MATCHED);
223 	}
224 	if (fullPathName != NULL) {
225 		fullPathName->references++;
226 		(void) fprintf(stderr, "%s\n", fullPathName->fullName);
227 	}
228 	squirrelPath(fullPathName, startCluster);
229 	(void) fprintf(stderr,
230 	    gettext("Truncating chain due to incorrect size "
231 	    "in directory.  Size from directory = %u bytes,\n"), sizeFromDir);
232 	if (actualClusterCount == 0) {
233 		(void) fprintf(stderr,
234 		    gettext("Zero bytes are allocated to the file.\n"));
235 	} else {
236 		(void) fprintf(stderr,
237 		    gettext("Allocated size in range %llu - %llu bytes.\n"),
238 		    ((actualClusterCount - 1) * bpc) + 1,
239 		    (actualClusterCount * bpc));
240 	}
241 	/*
242 	 * Use splitChain() to make an orphan that is the entire allocation
243 	 * chain.
244 	 */
245 	splitChain(fd, dp, startCluster, orphanEntry, &ignorei);
246 	return (TRUNCATED);
247 }
248 
249 static int
250 noteUsage(int fd, int32_t startAt, struct pcdir *dp, struct pcdir *lp,
251     int32_t longEntryStartCluster, int isHidden, int isDir,
252     struct nameinfo *fullPathName)
253 {
254 	struct pcdir *orphanEntry;
255 	int32_t chain = startAt;
256 	int32_t count = 0;
257 	int savePathNextIteration = 0;
258 	int haveBad = 0;
259 	ClusterInfo *tmpl = NULL;
260 
261 	while ((chain >= FIRST_CLUSTER) && (chain <= LastCluster)) {
262 		if ((markInUse(fd, chain, dp, lp, longEntryStartCluster,
263 		    isHidden ? HIDDEN : VISIBLE, &tmpl))
264 			!= CLINFO_NEWLY_ALLOCED)
265 			break;
266 		count++;
267 		if (savePathNextIteration == 1) {
268 			savePathNextIteration = 0;
269 			if (fullPathName != NULL)
270 				fullPathName->references++;
271 			squirrelPath(fullPathName, chain);
272 		}
273 		if (isMarkedBad(chain)) {
274 			haveBad = 1;
275 			savePathNextIteration = 1;
276 		}
277 		if (isHidden)
278 			HiddenClusterCount++;
279 		else if (isDir)
280 			DirClusterCount++;
281 		else
282 			FileClusterCount++;
283 		chain = nextInChain(chain);
284 	}
285 	/*
286 	 * Do a sanity check on the file size in the directory entry.
287 	 * This may create an orphaned cluster chain.
288 	 */
289 	if (sanityCheckSize(fd, dp, count, isDir, startAt,
290 	    fullPathName, &orphanEntry) == TRUNCATED) {
291 		/*
292 		 * The pre-existing directory entry has been truncated,
293 		 * so the chain associated with it no longer has any
294 		 * bad clusters.  Instead, the new orphan has them.
295 		 */
296 		if (haveBad > 0) {
297 			truncChainWithBadCluster(fd, orphanEntry, startAt);
298 		}
299 		haveBad = 0;
300 	}
301 	return (haveBad);
302 }
303 
304 static void
305 storeInfoAboutEntry(int fd, struct pcdir *dp, struct pcdir *ldp, int depth,
306     int32_t longEntryStartCluster, char *fullPath, int *fullLen)
307 {
308 	struct nameinfo *pathCopy;
309 	int32_t start;
310 	int haveBad;
311 	int hidden = (dp->pcd_attr & PCA_HIDDEN || dp->pcd_attr & PCA_SYSTEM);
312 	int dir = (dp->pcd_attr & PCA_DIR);
313 	int i;
314 
315 	if (hidden)
316 		HiddenFileCount++;
317 	else if (dir)
318 		DirCount++;
319 	else
320 		FileCount++;
321 	appendToPath(dp, fullPath, fullLen);
322 
323 	/*
324 	 * Make a copy of the name at this point.  We may want it to
325 	 * note the original source of an orphaned cluster.
326 	 */
327 	if ((pathCopy =
328 	    (struct nameinfo *)malloc(sizeof (struct nameinfo))) != NULL) {
329 		if ((pathCopy->fullName =
330 		    (char *)malloc(*fullLen + 1)) != NULL) {
331 			pathCopy->references = 0;
332 			(void) strncpy(pathCopy->fullName, fullPath, *fullLen);
333 			pathCopy->fullName[*fullLen] = '\0';
334 		} else {
335 			free(pathCopy);
336 			pathCopy = NULL;
337 		}
338 	}
339 	if (Verbose) {
340 		for (i = 0; i < depth; i++)
341 			(void) fprintf(stderr, "  ");
342 		if (hidden)
343 			(void) fprintf(stderr, "[");
344 		else if (dir)
345 			(void) fprintf(stderr, "|_");
346 		else
347 			(void) fprintf(stderr, gettext("(%06d) "), FileCount);
348 		printName(stderr, dp);
349 		if (hidden)
350 			(void) fprintf(stderr, "]");
351 		(void) fprintf(stderr,
352 		    gettext(", %u bytes, start cluster %d"),
353 		    extractSize(dp), extractStartCluster(dp));
354 		(void) fprintf(stderr, "\n");
355 	}
356 	start = extractStartCluster(dp);
357 	haveBad = noteUsage(fd, start, dp, ldp, longEntryStartCluster,
358 	    hidden, dir, pathCopy);
359 	if (haveBad > 0) {
360 		if (dir && pathCopy->fullName != NULL) {
361 			(void) fprintf(stderr,
362 			    gettext("Adjusting for bad allocation units in "
363 			    "the meta-data of:\n  "));
364 			(void) fprintf(stderr, pathCopy->fullName);
365 			(void) fprintf(stderr, "\n");
366 		}
367 		truncChainWithBadCluster(fd, dp, start);
368 	}
369 	if ((pathCopy != NULL) && (pathCopy->references == 0)) {
370 		free(pathCopy->fullName);
371 		free(pathCopy);
372 	}
373 }
374 
375 static void
376 storeInfoAboutLabel(struct pcdir *dp)
377 {
378 	/*
379 	 * XXX eventually depth should be passed to this routine just
380 	 * as it is with storeInfoAboutEntry().  If it isn't zero, then
381 	 * we've got a bogus directory entry.
382 	 */
383 	if (Verbose) {
384 		(void) fprintf(stderr, gettext("** "));
385 		printName(stderr, dp);
386 		(void) fprintf(stderr, gettext(" **\n"));
387 	}
388 }
389 
390 static void
391 searchChecks(struct pcdir *dp, int operation, char matchRequired,
392     struct pcdir **found)
393 {
394 	/*
395 	 *  We support these searching operations:
396 	 *
397 	 *  PCFS_FIND_ATTR
398 	 *	look for the first file with a certain attribute
399 	 *	(e.g, find all hidden files)
400 	 *  PCFS_FIND_STATUS
401 	 *	look for the first file with a certain status
402 	 *	(e.g., the file has been marked deleted; making
403 	 *	its directory entry reusable)
404 	 *  PCFS_FIND_CHKS
405 	 *	look for all files with short names of the form
406 	 *	FILENNNN.CHK.  These are the file names we give
407 	 *	to chains of orphaned clusters we relink into the
408 	 *	file system.  This find facility allows us to seek
409 	 *	out all existing files of this naming form so that
410 	 *	we may create unique file names for new orphans.
411 	 */
412 	if (operation == PCFS_FIND_ATTR && dp->pcd_attr == matchRequired) {
413 		*found = dp;
414 	} else if (operation == PCFS_FIND_STATUS &&
415 	    dp->pcd_filename[0] == matchRequired) {
416 		*found = dp;
417 	} else if (operation == PCFS_FIND_CHKS && hasCHKName(dp)) {
418 		addToCHKList(dp);
419 	}
420 }
421 
422 static void
423 catalogEntry(int fd, struct pcdir *dp, struct pcdir *longdp,
424     int32_t currentCluster, int depth, char *recordPath, int *pathLen)
425 {
426 	if (dp->pcd_attr & PCA_LABEL) {
427 		storeInfoAboutLabel(dp);
428 	} else {
429 		storeInfoAboutEntry(fd, dp, longdp, depth, currentCluster,
430 		    recordPath, pathLen);
431 	}
432 }
433 
434 /*
435  * visitNodes()
436  *
437  * This is the main workhouse routine for traversing pcfs metadata.
438  * There isn't a lot to the metadata.  Basically there is a root
439  * directory somewhere (either in its own special place outside the
440  * data area or in a data cluster).  The root directory (and all other
441  * directories) are filled with a number of fixed size entries.  An
442  * entry has the filename and extension, the file's attributes, the
443  * file's size, and the starting data cluster of the storage allocated
444  * to the file.  To determine which clusters are assigned to the file,
445  * you start at the starting cluster entry in the FAT, and follow the
446  * chain of entries in the FAT.
447  *
448  *	Arguments are:
449  *	fd
450  *		descriptor for accessing the raw file system data
451  *	currentCluster
452  *		original caller supplies the initial starting cluster,
453  *		subsequent recursive calls are made with updated
454  *		cluster numbers for the sub-directories.
455  *	dirData
456  *		pointer to the directory data bytes
457  *	dirDataLen
458  *		size of the whole buffer of data bytes (usually it is
459  *		the size of a cluster, but the root directory on
460  *		FAT12/16 is not necessarily the same size as a cluster).
461  *	depth
462  *		original caller should set it to zero (assuming they are
463  *		starting from the root directory).  This number is used to
464  *		change the indentation of file names presented as debug info.
465  *	descend
466  *		boolean indicates if we should descend into subdirectories.
467  *	operation
468  *		what, if any, matching should be performed.
469  *		The PCFS_TRAVERSE_ALL operation is a depth first traversal
470  *		of all nodes in the metadata tree, that tracks all the
471  *		clusters in use (according to the meta-data, at least)
472  *	matchRequired
473  *		value to be matched (if any)
474  *	found
475  *		output parameter
476  *		used to return pointer to a directory entry that matches
477  *		the search requirement
478  *		original caller should pass in a pointer to a NULL pointer.
479  *	lastDirCluster
480  *		output parameter
481  *		if no match found, last cluster num of starting directory
482  *	dirEnd
483  *		output parameter
484  *		if no match found, return parameter stores pointer to where
485  *		new directory entry could be appended to existing directory
486  *	recordPath
487  *		output parameter
488  *		as files are discovered, and directories traversed, this
489  *		buffer is used to store the current full path name.
490  *	pathLen
491  *		output parameter
492  *		this is in the integer length of the current full path name.
493  */
494 static void
495 visitNodes(int fd, int32_t currentCluster, ClusterContents *dirData,
496     int32_t dirDataLen, int depth, int descend, int operation,
497     char matchRequired,  struct pcdir **found, int32_t *lastDirCluster,
498     struct pcdir **dirEnd, char *recordPath, int *pathLen)
499 {
500 	struct pcdir *longdp = NULL;
501 	struct pcdir *dp;
502 	int32_t longStart;
503 	int withinLongName = 0;
504 	int saveLen = *pathLen;
505 
506 	dp = dirData->dirp;
507 
508 	/*
509 	 *  A directory entry where the first character of the name is
510 	 *  PCD_UNUSED indicates the end of the directory.
511 	 */
512 	while ((uchar_t *)dp < dirData->bytes + dirDataLen &&
513 	    dp->pcd_filename[0] != PCD_UNUSED) {
514 		/*
515 		 *  Handle the special case find operations.
516 		 */
517 		searchChecks(dp, operation, matchRequired, found);
518 		if (*found)
519 			break;
520 		/*
521 		 * Are we looking at part of a long file name entry?
522 		 * If so, we may need to note the start of the name.
523 		 * We don't do any further processing of long file
524 		 * name entries.
525 		 *
526 		 * We also skip deleted entries and the '.' and '..'
527 		 * entries.
528 		 */
529 		if ((dp->pcd_attr & PCDL_LFN_BITS) == PCDL_LFN_BITS) {
530 			if (!withinLongName) {
531 				withinLongName++;
532 				longStart = currentCluster;
533 				longdp = dp;
534 			}
535 			dp++;
536 			continue;
537 		} else if ((dp->pcd_filename[0] == PCD_ERASED) ||
538 		    (dp->pcd_filename[0] == '.')) {
539 			/*
540 			 * XXX - if we were within a long name, then
541 			 * its existence is bogus, because it is not
542 			 * attached to any real file.
543 			 */
544 			withinLongName = 0;
545 			dp++;
546 			continue;
547 		}
548 		withinLongName = 0;
549 		if (operation == PCFS_TRAVERSE_ALL)
550 			catalogEntry(fd, dp, longdp, longStart, depth,
551 			    recordPath, pathLen);
552 		longdp = NULL;
553 		longStart = 0;
554 		if (dp->pcd_attr & PCA_DIR && descend == PCFS_VISIT_SUBDIRS) {
555 			traverseDir(fd, extractStartCluster(dp), depth + 1,
556 			    descend, operation, matchRequired, found,
557 			    lastDirCluster, dirEnd, recordPath, pathLen);
558 			if (*found)
559 				break;
560 		}
561 		dp++;
562 		*pathLen = saveLen;
563 	}
564 	if (*found)
565 		return;
566 	if ((uchar_t *)dp < dirData->bytes + dirDataLen) {
567 		/*
568 		 * We reached the end of directory before the end of
569 		 * our provided data (a cluster).  That means this cluster
570 		 * is the last one in this directory's chain.  It also
571 		 * means we've just looked at the last directory entry.
572 		 */
573 		*lastDirCluster = currentCluster;
574 		*dirEnd = dp;
575 		return;
576 	}
577 	/*
578 	 * If there is more to the directory we'll go get it otherwise we
579 	 * are done traversing this directory.
580 	 */
581 	if ((currentCluster == FAKE_ROOTDIR_CLUST) ||
582 	    (lastInFAT(currentCluster))) {
583 		*lastDirCluster = currentCluster;
584 		return;
585 	} else {
586 		traverseDir(fd, nextInChain(currentCluster),
587 		    depth, descend, operation, matchRequired,
588 		    found, lastDirCluster, dirEnd, recordPath, pathLen);
589 		*pathLen = saveLen;
590 	}
591 }
592 
593 /*
594  *  traverseFromRoot()
595  *	For use with 12 and 16 bit FATs that have a root directory outside
596  *	of the file system.  This is a general purpose routine that
597  *	can be used simply to visit all of the nodes in the metadata or
598  *	to find the first instance of something, e.g., the first directory
599  *	entry where the file is marked deleted.
600  *
601  *	Inputs are described in the commentary for visitNodes() above.
602  */
603 void
604 traverseFromRoot(int fd, int depth, int descend, int operation,
605     char matchRequired,  struct pcdir **found, int32_t *lastDirCluster,
606     struct pcdir **dirEnd, char *recordPath, int *pathLen)
607 {
608 	visitNodes(fd, FAKE_ROOTDIR_CLUST, &TheRootDir, RootDirSize, depth,
609 	    descend, operation, matchRequired, found, lastDirCluster, dirEnd,
610 	    recordPath, pathLen);
611 }
612 
613 /*
614  *  traverseDir()
615  *	For use with all FATs outside of the initial root directory on
616  *	12 and 16 bit FAT file systems.  This is a general purpose routine
617  *	that can be used simply to visit all of the nodes in the metadata or
618  *	to find the first instance of something, e.g., the first directory
619  *	entry where the file is marked deleted.
620  *
621  *	Unique Input is:
622  *	startAt
623  *		starting cluster of the directory
624  *
625  *	This is the cluster that is the first one in this directory.
626  *	We read it right away, so we can provide it as data to visitNodes().
627  *	Note that we cache this cluster as we read it, because it is
628  *	metadata and we cache all metadata.  By doing so, we can
629  *	keep pointers to directory entries for quickly moving around and
630  *	fixing up any problems we find.  Of course if we get a big
631  *	filesystem with a huge amount of metadata we may be hosed, as
632  *	we'll likely run out of memory.
633  *
634  *	I believe in the future this will have to be addressed.  It
635  *	may be possible to do more of the processing of problems
636  *	within directories as they are cached, so that when memory
637  *	runs short we can free cached directories we are already
638  *	finished visiting.
639  *
640  *	The remainder of inputs are described in visitNodes() comments.
641  */
642 void
643 traverseDir(int fd, int32_t startAt, int depth, int descend, int operation,
644     char matchRequired,  struct pcdir **found, int32_t *lastDirCluster,
645     struct pcdir **dirEnd, char *recordPath, int *pathLen)
646 {
647 	ClusterContents dirdata;
648 	int32_t dirdatasize = 0;
649 
650 	if (startAt < FIRST_CLUSTER || startAt > LastCluster)
651 		return;
652 
653 	if (readCluster(fd, startAt, &(dirdata.bytes), &dirdatasize,
654 	    RDCLUST_DO_CACHE) != RDCLUST_GOOD) {
655 		(void) fprintf(stderr,
656 		    gettext("Unable to get more directory entries!\n"));
657 		return;
658 	}
659 
660 	if (operation == PCFS_TRAVERSE_ALL) {
661 		if (Verbose)
662 			(void) fprintf(stderr,
663 			    gettext("Directory traversal enters "
664 			    "allocation unit %d.\n"), startAt);
665 	}
666 	visitNodes(fd, startAt, &dirdata, dirdatasize, depth, descend,
667 	    operation, matchRequired, found, lastDirCluster, dirEnd,
668 	    recordPath, pathLen);
669 }
670 
671 void
672 createCHKNameList(int fd)
673 {
674 	struct pcdir *ignorep1, *ignorep2;
675 	int32_t ignore32;
676 	char *ignorecp = NULL;
677 	char ignore = '\0';
678 	int ignoreint = 0;
679 
680 	ignorep1 = ignorep2 = NULL;
681 	if (!OkayToRelink || CHKsList != NULL)
682 		return;
683 
684 	/*
685 	 *  Allocate an array to keep a bit map of the integer
686 	 *  values used in CHK names.
687 	 */
688 	if ((CHKsList =
689 	    (uchar_t *)calloc(1, idivceil(MAXCHKVAL, NBBY))) == NULL) {
690 		OkayToRelink = 0;
691 		return;
692 	}
693 
694 	/*
695 	 *  Search the root directory for all the files with names of
696 	 *  the form FILEXXXX.CHK.  The root directory is an area
697 	 *  outside of the file space on FAT12 and FAT16 file systems.
698 	 *  On FAT32 file systems, the root directory is in a file
699 	 *  area cluster just like any other directory.
700 	 */
701 	if (!IsFAT32) {
702 		traverseFromRoot(fd, 0, PCFS_NO_SUBDIRS, PCFS_FIND_CHKS,
703 		    ignore, &ignorep1, &ignore32, &ignorep2, ignorecp,
704 		    &ignoreint);
705 	} else {
706 		DirCount++;
707 		traverseDir(fd, TheBIOSParameterBlock.bpb32.root_dir_clust,
708 		    0, PCFS_NO_SUBDIRS, PCFS_FIND_CHKS, ignore,
709 		    &ignorep1, &ignore32, &ignorep2, ignorecp, &ignoreint);
710 	}
711 }
712 
713 
714 char *
715 nextAvailableCHKName(int *chosen)
716 {
717 	static char nameBuf[PCFNAMESIZE];
718 	int i;
719 
720 	if (!OkayToRelink)
721 		return (NULL);
722 
723 	nameBuf[CHKNAME_F] = 'F';
724 	nameBuf[CHKNAME_I] = 'I';
725 	nameBuf[CHKNAME_L] = 'L';
726 	nameBuf[CHKNAME_E] = 'E';
727 
728 	for (i = 1; i <= MAXCHKVAL; i++) {
729 		if (!inUseCHKName(i))
730 			break;
731 	}
732 	if (i <= MAXCHKVAL) {
733 		nameBuf[CHKNAME_THOUSANDS] = '0' + (i / 1000);
734 		nameBuf[CHKNAME_HUNDREDS] = '0' + ((i % 1000) / 100);
735 		nameBuf[CHKNAME_TENS] = '0' + ((i % 100) / 10);
736 		nameBuf[CHKNAME_ONES] = '0' + (i % 10);
737 		*chosen = i;
738 		return (nameBuf);
739 	} else {
740 		(void) fprintf(stderr,
741 		    gettext("Sorry, no names available for "
742 		    "relinking orphan chains!\n"));
743 		OkayToRelink = 0;
744 		return (NULL);
745 	}
746 }
747 
748 uint32_t
749 extractSize(struct pcdir *dp)
750 {
751 	uint32_t returnMe;
752 
753 	read_32_bits((uchar_t *)&(dp->pcd_size), &returnMe);
754 	return (returnMe);
755 }
756 
757 int32_t
758 extractStartCluster(struct pcdir *dp)
759 {
760 	uint32_t lo, hi;
761 
762 	if (IsFAT32) {
763 		read_16_bits((uchar_t *)&(dp->un.pcd_scluster_hi), &hi);
764 		read_16_bits((uchar_t *)&(dp->pcd_scluster_lo), &lo);
765 		return ((int32_t)((hi << 16) | lo));
766 	} else {
767 		read_16_bits((uchar_t *)&(dp->pcd_scluster_lo), &lo);
768 		return ((int32_t)lo);
769 	}
770 }
771 
772 static struct pcdir *
773 findAvailableRootDirEntSlot(int fd, int32_t *clusterWithSlot)
774 {
775 	struct pcdir *deletedEntry = NULL;
776 	struct pcdir *appendPoint = NULL;
777 	char *ignorecp = NULL;
778 	int ignore = 0;
779 
780 	*clusterWithSlot = 0;
781 
782 	/*
783 	 *  First off, try to find an erased entry in the root
784 	 *  directory.  The root directory is an area outside of the
785 	 *  file space on FAT12 and FAT16 file systems.  On FAT32 file
786 	 *  systems, the root directory is in a file area cluster just
787 	 *  like any other directory.
788 	 */
789 	if (!IsFAT32) {
790 		traverseFromRoot(fd, 0, PCFS_NO_SUBDIRS, PCFS_FIND_STATUS,
791 		    PCD_ERASED, &deletedEntry, clusterWithSlot,
792 		    &appendPoint, ignorecp, &ignore);
793 	} else {
794 		DirCount++;
795 		traverseDir(fd, TheBIOSParameterBlock.bpb32.root_dir_clust,
796 		    0, PCFS_NO_SUBDIRS, PCFS_FIND_STATUS, PCD_ERASED,
797 		    &deletedEntry, clusterWithSlot, &appendPoint, ignorecp,
798 		    &ignore);
799 	}
800 	/*
801 	 *  If we found a deleted file in the directory we'll overwrite
802 	 *  that entry.
803 	 */
804 	if (deletedEntry)
805 		return (deletedEntry);
806 	/*
807 	 *  If there is room at the end of the existing directory, we
808 	 *  should place the new entry there.
809 	 */
810 	if (appendPoint)
811 		return (appendPoint);
812 	/*
813 	 *  XXX need to grow the directory
814 	 */
815 	return (NULL);
816 }
817 
818 static void
819 insertDirEnt(struct pcdir *slot, struct pcdir *entry, int32_t clusterWithSlot)
820 {
821 	(void) memcpy(slot, entry, sizeof (struct pcdir));
822 	markClusterModified(clusterWithSlot);
823 }
824 
825 static void
826 getNow(timestruc_t *ts)
827 {
828 	struct timeval	tv;
829 
830 	if (gettimeofday(&tv, NULL) == 0) {
831 		ts->tv_sec = tv.tv_sec;
832 		ts->tv_nsec = tv.tv_usec * 1000;
833 	} else {
834 		/* Failed to get time, set create time to the Solaris epoch */
835 		ts->tv_sec = 0;
836 		ts->tv_nsec = 0;
837 	}
838 }
839 
840 /*
841  *  FAT file systems store the following time information in a directory
842  *  entry:
843  *		creation time
844  *		creation date
845  *		last access date
846  *		last modify time
847  *		last modify date
848  *
849  *  No access time is kept.
850  */
851 static void
852 updateDirEnt_CreatTime(struct pcdir *dp)
853 {
854 	timestruc_t	ts;
855 
856 	getNow(&ts);
857 	pc_tvtopct(&ts, &(dp->pcd_crtime)); /* sets creation time/date */
858 	dp->pcd_crtime_msec = 0;
859 	markClusterModified(findImpactedCluster(dp));
860 }
861 
862 static void
863 updateDirEnt_ModTimes(struct pcdir *dp)
864 {
865 	timestruc_t	ts;
866 
867 	getNow(&ts);
868 	pc_tvtopct(&ts, &(dp->pcd_mtime)); /* sets modification time/date */
869 	dp->pcd_ladate = dp->pcd_mtime.pct_date; /* sets access date */
870 	dp->pcd_attr |= PCA_ARCH;
871 	markClusterModified(findImpactedCluster(dp));
872 }
873 
874 struct pcdir *
875 addRootDirEnt(int fd, struct pcdir *new)
876 {
877 	struct pcdir *added;
878 	int32_t inCluster;
879 
880 	if ((added = findAvailableRootDirEntSlot(fd, &inCluster)) != NULL) {
881 		insertDirEnt(added, new, inCluster);
882 		return (added);
883 	}
884 	return (NULL);
885 }
886 
887 /*
888  *  FAT12 and FAT16 have a root directory outside the normal file space,
889  *  so we have separate routines for finding and reading the root directory.
890  */
891 static off64_t
892 seekRootDirectory(int fd)
893 {
894 	off64_t seekto;
895 
896 	/*
897 	 *  The RootDir immediately follows the FATs, which in
898 	 *  turn immediately follow the reserved sectors.
899 	 */
900 	seekto = (off64_t)TheBIOSParameterBlock.bpb.resv_sectors *
901 		    TheBIOSParameterBlock.bpb.bytes_per_sector +
902 		    (off64_t)FATSize * TheBIOSParameterBlock.bpb.num_fats +
903 		    (off64_t)PartitionOffset;
904 	if (Verbose)
905 		(void) fprintf(stderr,
906 		    gettext("Seeking root directory @%lld.\n"), seekto);
907 	return (lseek64(fd, seekto, SEEK_SET));
908 }
909 
910 void
911 getRootDirectory(int fd)
912 {
913 	ssize_t bytesRead;
914 
915 	if (TheRootDir.bytes != NULL)
916 		return;
917 	else if ((TheRootDir.bytes = (uchar_t *)malloc(RootDirSize)) == NULL) {
918 		mountSanityCheckFails();
919 		perror(gettext("No memory for a copy of the root directory"));
920 		(void) close(fd);
921 		exit(8);
922 	}
923 
924 	if (seekRootDirectory(fd) < 0) {
925 		mountSanityCheckFails();
926 		perror(gettext("Cannot seek to RootDir"));
927 		(void) close(fd);
928 		exit(8);
929 	}
930 
931 	if (Verbose)
932 		(void) fprintf(stderr,
933 		    gettext("Reading root directory.\n"));
934 	if ((bytesRead = read(fd, TheRootDir.bytes, RootDirSize)) !=
935 	    RootDirSize) {
936 		mountSanityCheckFails();
937 		if (bytesRead < 0) {
938 			perror(gettext("Cannot read a RootDir"));
939 		} else {
940 			(void) fprintf(stderr,
941 			    gettext("Short read of RootDir\n"));
942 		}
943 		(void) close(fd);
944 		exit(8);
945 	}
946 	if (Verbose) {
947 		(void) fprintf(stderr,
948 		    gettext("Dump of root dir's first 256 bytes.\n"));
949 		header_for_dump();
950 		dump_bytes(TheRootDir.bytes, 256);
951 	}
952 }
953 
954 void
955 writeRootDirMods(int fd)
956 {
957 	ssize_t bytesWritten;
958 
959 	if (!TheRootDir.bytes) {
960 		(void) fprintf(stderr,
961 		    gettext("Internal error: No Root directory to write\n"));
962 		(void) close(fd);
963 		exit(12);
964 	}
965 	if (!RootDirModified) {
966 		if (Verbose) {
967 			(void) fprintf(stderr,
968 			    gettext("No root directory changes need to "
969 			    "be written.\n"));
970 		}
971 		return;
972 	}
973 	if (ReadOnly)
974 		return;
975 	if (Verbose)
976 		(void) fprintf(stderr,
977 		    gettext("Writing root directory.\n"));
978 	if (seekRootDirectory(fd) < 0) {
979 		perror(gettext("Cannot write the RootDir (seek failed)"));
980 		(void) close(fd);
981 		exit(12);
982 	}
983 	if ((bytesWritten = write(fd, TheRootDir.bytes, RootDirSize)) !=
984 	    RootDirSize) {
985 		if (bytesWritten < 0) {
986 			perror(gettext("Cannot write the RootDir"));
987 		} else {
988 			(void) fprintf(stderr,
989 			    gettext("Short write of root directory\n"));
990 		}
991 		(void) close(fd);
992 		exit(12);
993 	}
994 	RootDirModified = 0;
995 }
996 
997 struct pcdir *
998 newDirEnt(struct pcdir *copyme)
999 {
1000 	struct pcdir *ndp;
1001 
1002 	if ((ndp = (struct pcdir *)calloc(1, sizeof (struct pcdir))) == NULL) {
1003 		(void) fprintf(stderr, gettext("Out of memory to create a "
1004 		    "new directory entry!\n"));
1005 		return (ndp);
1006 	}
1007 	if (copyme)
1008 		(void) memcpy(ndp, copyme, sizeof (struct pcdir));
1009 	ndp->pcd_ext[CHKNAME_C] = 'C';
1010 	ndp->pcd_ext[CHKNAME_H] = 'H';
1011 	ndp->pcd_ext[CHKNAME_K] = 'K';
1012 	updateDirEnt_CreatTime(ndp);
1013 	updateDirEnt_ModTimes(ndp);
1014 	return (ndp);
1015 }
1016 
1017 void
1018 updateDirEnt_Size(struct pcdir *dp, uint32_t newSize)
1019 {
1020 	uchar_t *p = (uchar_t *)&(dp->pcd_size);
1021 	store_32_bits(&p, newSize);
1022 	markClusterModified(findImpactedCluster(dp));
1023 }
1024 
1025 void
1026 updateDirEnt_Start(struct pcdir *dp, int32_t newStart)
1027 {
1028 	uchar_t *p = (uchar_t *)&(dp->pcd_scluster_lo);
1029 	store_16_bits(&p, newStart & 0xffff);
1030 	if (IsFAT32) {
1031 		p = (uchar_t *)&(dp->un.pcd_scluster_hi);
1032 		store_16_bits(&p, newStart >> 16);
1033 	}
1034 	markClusterModified(findImpactedCluster(dp));
1035 }
1036 
1037 void
1038 updateDirEnt_Name(struct pcdir *dp, char *newName)
1039 {
1040 	int i;
1041 
1042 	for (i = 0; i < PCFNAMESIZE; i++) {
1043 		if (*newName)
1044 			dp->pcd_filename[i] = *newName++;
1045 		else
1046 			dp->pcd_filename[i] = ' ';
1047 	}
1048 	markClusterModified(findImpactedCluster(dp));
1049 }
1050