xref: /csrg-svn/bin/pax/tables.c (revision 60676)
157113Smuller /*-
257113Smuller  * Copyright (c) 1992 Keith Muller.
3*60676Sbostic  * Copyright (c) 1992, 1993
4*60676Sbostic  *	The Regents of the University of California.  All rights reserved.
557113Smuller  *
657113Smuller  * This code is derived from software contributed to Berkeley by
757113Smuller  * Keith Muller of the University of California, San Diego.
857113Smuller  *
957113Smuller  * %sccs.include.redist.c%
1057113Smuller  */
1157113Smuller 
1257113Smuller #ifndef lint
13*60676Sbostic static char sccsid[] = "@(#)tables.c	8.1 (Berkeley) 05/31/93";
1457113Smuller #endif /* not lint */
1557113Smuller 
1657113Smuller #include <sys/types.h>
1757113Smuller #include <sys/time.h>
1857113Smuller #include <sys/stat.h>
1957113Smuller #include <sys/param.h>
2057113Smuller #include <sys/fcntl.h>
2157113Smuller #include <stdio.h>
2257113Smuller #include <ctype.h>
2357113Smuller #include <string.h>
2457113Smuller #include <unistd.h>
2557113Smuller #include <errno.h>
2657113Smuller #include <stdlib.h>
2757113Smuller #include "pax.h"
2857113Smuller #include "tables.h"
2957113Smuller #include "extern.h"
3057113Smuller 
3157113Smuller /*
3257113Smuller  * Routines for controlling the contents of all the different databases pax
3357113Smuller  * keeps. Tables are dynamically created only when they are needed. The
3457113Smuller  * goal was speed and the ability to work with HUGE archives. The databases
3557113Smuller  * were kept simple, but do have complex rules for when the contents change.
3657113Smuller  * As of this writing, the posix library functions were more complex than
3757113Smuller  * needed for this application (pax databases have very short lifetimes and
3857113Smuller  * do not survive after pax is finished). Pax is required to handle very
3957113Smuller  * large archives. These database routines carefully combine memory usage and
4057113Smuller  * temporary file storage in ways which will not significantly impact runtime
4157113Smuller  * performance while allowing the largest possible archives to be handled.
4257113Smuller  * Trying to force the fit to the posix databases routines was not considered
4357113Smuller  * time well spent.
4457113Smuller  */
4557113Smuller 
4657113Smuller static HRDLNK **ltab = NULL;	/* hard link table for detecting hard links */
4757113Smuller static FTM **ftab = NULL;	/* file time table for updating arch */
4857113Smuller static NAMT **ntab = NULL;	/* interactive rename storage table */
4957113Smuller static DEVT **dtab = NULL;	/* device/inode mapping tables */
5057113Smuller static ATDIR **atab = NULL;	/* file tree directory time reset table */
5157113Smuller static int dirfd = -1;		/* storage for setting created dir time/mode */
5257113Smuller static u_long dircnt;		/* entries in dir time/mode storage */
5357113Smuller static int ffd = -1;		/* tmp file for file time table name storage */
5457113Smuller 
5557113Smuller static DEVT *chk_dev __P((dev_t, int));
5657113Smuller 
5757113Smuller /*
5857113Smuller  * hard link table routines
5957113Smuller  *
6057113Smuller  * The hard link table tries to detect hard links to files using the device and
6157113Smuller  * inode values. We do this when writing an archive, so we can tell the format
6257113Smuller  * write routine that this file is a hard link to another file. The format
6357113Smuller  * write routine then can store this file in whatever way it wants (as a hard
6457113Smuller  * link if the format supports that like tar, or ignore this info like cpio).
6557113Smuller  * (Actually a field in the format driver table tells us if the format wants
6657113Smuller  * hard link info. if not, we do not waste time looking for them). We also use
6757113Smuller  * the same table when reading an archive. In that situation, this table is
6857113Smuller  * used by the format read routine to detect hard links from stored dev and
6957113Smuller  * inode numbers (like cpio). This will allow pax to create a link when one
7057113Smuller  * can be detected by the archive format.
7157113Smuller  */
7257113Smuller 
7357113Smuller /*
7457113Smuller  * lnk_start
7557113Smuller  *	Creates the hard link table.
7657113Smuller  * Return:
7757113Smuller  *	0 if created, -1 if failure
7857113Smuller  */
7957113Smuller 
8057113Smuller #if __STDC__
8157113Smuller int
lnk_start(void)8257113Smuller lnk_start(void)
8357113Smuller #else
8457113Smuller int
8557113Smuller lnk_start()
8657113Smuller #endif
8757113Smuller {
8857113Smuller 	if (ltab != NULL)
8957113Smuller 		return(0);
9057113Smuller  	if ((ltab = (HRDLNK **)calloc(L_TAB_SZ, sizeof(HRDLNK *))) == NULL) {
9157113Smuller                 warn(1, "Cannot allocate memory for hard link table");
9257113Smuller                 return(-1);
9357113Smuller         }
9457113Smuller 	return(0);
9557113Smuller }
9657113Smuller 
9757113Smuller /*
9857113Smuller  * chk_lnk()
9957113Smuller  *	Looks up entry in hard link hash table. If found, it copies the name
10057113Smuller  *	of the file it is linked to (we already saw that file) into ln_name.
10157113Smuller  *	lnkcnt is decremented and if goes to 1 the node is deleted from the
10257113Smuller  *	database. (We have seen all the links to this file). If not found,
10357113Smuller  *	we add the file to the database if it has the potential for having
10457113Smuller  *	hard links to other files we may process (it has a link count > 1)
10557113Smuller  * Return:
10657113Smuller  *	if found returns 1; if not found returns 0; -1 on error
10757113Smuller  */
10857113Smuller 
10957113Smuller #if __STDC__
11057113Smuller int
chk_lnk(register ARCHD * arcn)11157113Smuller chk_lnk(register ARCHD *arcn)
11257113Smuller #else
11357113Smuller int
11457113Smuller chk_lnk(arcn)
11557113Smuller 	register ARCHD *arcn;
11657113Smuller #endif
11757113Smuller {
11857113Smuller 	register HRDLNK *pt;
11957113Smuller 	register HRDLNK **ppt;
12057113Smuller 	register u_int indx;
12157113Smuller 
12257113Smuller 	if (ltab == NULL)
12357113Smuller 		return(-1);
12457113Smuller 	/*
12557113Smuller 	 * ignore those nodes that cannot have hard links
12657113Smuller 	 */
12757113Smuller 	if ((arcn->type == PAX_DIR) || (arcn->sb.st_nlink <= 1))
12857113Smuller 		return(0);
12957113Smuller 
13057113Smuller 	/*
13157113Smuller 	 * hash inode number and look for this file
13257113Smuller 	 */
13357113Smuller 	indx = ((unsigned)arcn->sb.st_ino) % L_TAB_SZ;
13457113Smuller 	if ((pt = ltab[indx]) != NULL) {
13557113Smuller 		/*
13657113Smuller 		 * it's hash chain in not empty, walk down looking for it
13757113Smuller 		 */
13857113Smuller 		ppt = &(ltab[indx]);
13957113Smuller 		while (pt != NULL) {
14057113Smuller 			if ((pt->ino == arcn->sb.st_ino) &&
14157113Smuller 			    (pt->dev == arcn->sb.st_dev))
14257113Smuller 				break;
14357113Smuller 			ppt = &(pt->fow);
14457113Smuller 			pt = pt->fow;
14557113Smuller 		}
14657113Smuller 
14757113Smuller 		if (pt != NULL) {
14857113Smuller 			/*
14957113Smuller 			 * found a link. set the node type and copy in the
15057113Smuller 			 * name of the file it is to link to. we need to
15157113Smuller 			 * handle hardlinks to regular files differently than
15257113Smuller 			 * other links.
15357113Smuller 			 */
15457113Smuller 			arcn->ln_nlen = l_strncpy(arcn->ln_name, pt->name,
15557113Smuller 				PAXPATHLEN+1);
15657113Smuller 			if (arcn->type == PAX_REG)
15757113Smuller 				arcn->type = PAX_HRG;
15857113Smuller 			else
15957113Smuller 				arcn->type = PAX_HLK;
16057113Smuller 
16157113Smuller 			/*
16257113Smuller 			 * if we have found all the links to this file, remove
16357113Smuller 			 * it from the database
16457113Smuller 			 */
16557113Smuller 			if (--pt->nlink <= 1) {
16657113Smuller 				*ppt = pt->fow;
16757113Smuller 				(void)free((char *)pt->name);
16857113Smuller 				(void)free((char *)pt);
16957113Smuller 			}
17057113Smuller 			return(1);
17157113Smuller 		}
17257113Smuller 	}
17357113Smuller 
17457113Smuller 	/*
17557113Smuller 	 * we never saw this file before. It has links so we add it to the
17657113Smuller 	 * front of this hash chain
17757113Smuller 	 */
17857113Smuller 	if ((pt = (HRDLNK *)malloc(sizeof(HRDLNK))) != NULL) {
17957113Smuller 		if ((pt->name = strdup(arcn->name)) != NULL) {
18057113Smuller 			pt->dev = arcn->sb.st_dev;
18157113Smuller 			pt->ino = arcn->sb.st_ino;
18257113Smuller 			pt->nlink = arcn->sb.st_nlink;
18357113Smuller 			pt->fow = ltab[indx];
18457113Smuller 			ltab[indx] = pt;
18557113Smuller 			return(0);
18657113Smuller 		}
18757113Smuller 		(void)free((char *)pt);
18857113Smuller 	}
18957113Smuller 
19057113Smuller 	warn(1, "Hard link table out of memory");
19157113Smuller 	return(-1);
19257113Smuller }
19357113Smuller 
19457113Smuller /*
19557113Smuller  * purg_lnk
19657113Smuller  *	remove reference for a file that we may have added to the data base as
19757113Smuller  *	a potential source for hard links. We ended up not using the file, so
19857113Smuller  *	we do not want to accidently point another file at it later on.
19957113Smuller  */
20057113Smuller 
20157113Smuller #if __STDC__
20257113Smuller void
purg_lnk(register ARCHD * arcn)20357113Smuller purg_lnk(register ARCHD *arcn)
20457113Smuller #else
20557113Smuller void
20657113Smuller purg_lnk(arcn)
20757113Smuller 	register ARCHD *arcn;
20857113Smuller #endif
20957113Smuller {
21057113Smuller 	register HRDLNK *pt;
21157113Smuller 	register HRDLNK **ppt;
21257113Smuller 	register u_int indx;
21357113Smuller 
21457113Smuller 	if (ltab == NULL)
21557113Smuller 		return;
21657113Smuller 	/*
21757113Smuller 	 * do not bother to look if it could not be in the database
21857113Smuller 	 */
21957113Smuller 	if ((arcn->sb.st_nlink <= 1) || (arcn->type == PAX_DIR) ||
22057113Smuller 	    (arcn->type == PAX_HLK) || (arcn->type == PAX_HRG))
22157113Smuller 		return;
22257113Smuller 
22357113Smuller 	/*
22457113Smuller 	 * find the hash chain for this inode value, if empty return
22557113Smuller 	 */
22657113Smuller 	indx = ((unsigned)arcn->sb.st_ino) % L_TAB_SZ;
22757113Smuller 	if ((pt = ltab[indx]) == NULL)
22857113Smuller 		return;
22957113Smuller 
23057113Smuller 	/*
23157113Smuller 	 * walk down the list looking for the inode/dev pair, unlink and
23257113Smuller 	 * free if found
23357113Smuller 	 */
23457113Smuller 	ppt = &(ltab[indx]);
23557113Smuller 	while (pt != NULL) {
23657113Smuller 		if ((pt->ino == arcn->sb.st_ino) &&
23757113Smuller 		    (pt->dev == arcn->sb.st_dev))
23857113Smuller 			break;
23957113Smuller 		ppt = &(pt->fow);
24057113Smuller 		pt = pt->fow;
24157113Smuller 	}
24257113Smuller 	if (pt == NULL)
24357113Smuller 		return;
24457113Smuller 
24557113Smuller 	/*
24657113Smuller 	 * remove and free it
24757113Smuller 	 */
24857113Smuller 	*ppt = pt->fow;
24957113Smuller 	(void)free((char *)pt->name);
25057113Smuller 	(void)free((char *)pt);
25157113Smuller }
25257113Smuller 
25357113Smuller /*
25457113Smuller  * lnk_end()
25557113Smuller  *	pull apart a existing link table so we can reuse it. We do this between
25657113Smuller  *	read and write phases of append with update. (The format may have
25757113Smuller  *	used the link table, and we need to start with a fresh table for the
25857113Smuller  *	write phase
25957113Smuller  */
26057113Smuller 
26157113Smuller #if __STDC__
26257113Smuller void
lnk_end(void)26357113Smuller lnk_end(void)
26457113Smuller #else
26557113Smuller void
26657113Smuller lnk_end()
26757113Smuller #endif
26857113Smuller {
26957113Smuller 	register int i;
27057113Smuller 	register HRDLNK *pt;
27157113Smuller 	register HRDLNK *ppt;
27257113Smuller 
27357113Smuller 	if (ltab == NULL)
27457113Smuller 		return;
27557113Smuller 
27657113Smuller 	for (i = 0; i < L_TAB_SZ; ++i) {
27757113Smuller 		if (ltab[i] == NULL)
27857113Smuller 			continue;
27957113Smuller 		pt = ltab[i];
28057113Smuller 		ltab[i] = NULL;
28157113Smuller 
28257113Smuller 		/*
28357113Smuller 		 * free up each entry on this chain
28457113Smuller 		 */
28557113Smuller 		while (pt != NULL) {
28657113Smuller 			ppt = pt;
28757113Smuller 			pt = ppt->fow;
28857113Smuller 			(void)free((char *)ppt->name);
28957113Smuller 			(void)free((char *)ppt);
29057113Smuller 		}
29157113Smuller 	}
29257113Smuller 	return;
29357113Smuller }
29457113Smuller 
29557113Smuller /*
29657113Smuller  * modification time table routines
29757113Smuller  *
29857113Smuller  * The modification time table keeps track of last modification times for all
29957113Smuller  * files stored in an archive during a write phase when -u is set. We only
30057113Smuller  * add a file to the archive if it is newer than a file with the same name
30157113Smuller  * already stored on the archive (if there is no other file with the same
30257113Smuller  * name on the archive it is added). This applies to writes and appends.
30357113Smuller  * An append with an -u must read the archive and store the modification time
30457113Smuller  * for every file on that archive before starting the write phase. It is clear
30557113Smuller  * that this is one HUGE database. To save memory space, the actual file names
30657113Smuller  * are stored in a scatch file and indexed by an in memory hash table. The
30757113Smuller  * hash table is indexed by hashing the file path. The nodes in the table store
30857113Smuller  * the length of the filename and the lseek offset within the scratch file
30957113Smuller  * where the actual name is stored. Since there are never any deletions to this
31057113Smuller  * table, fragmentation of the scratch file is never a issue. Lookups seem to
31157113Smuller  * not exhibit any locality at all (files in the database are rarely
31257113Smuller  * looked up more than once...). So caching is just a waste of memory. The
31357113Smuller  * only limitation is the amount of scatch file space available to store the
31457113Smuller  * path names.
31557113Smuller  */
31657113Smuller 
31757113Smuller /*
31857113Smuller  * ftime_start()
31957113Smuller  *	create the file time hash table and open for read/write the scratch
32057113Smuller  *	file. (after created it is unlinked, so when we exit we leave
32157113Smuller  *	no witnesses).
32257113Smuller  * Return:
32357113Smuller  *	0 if the table and file was created ok, -1 otherwise
32457113Smuller  */
32557113Smuller 
32657113Smuller #if __STDC__
32757113Smuller int
ftime_start(void)32857113Smuller ftime_start(void)
32957113Smuller #else
33057113Smuller int
33157113Smuller ftime_start()
33257113Smuller #endif
33357113Smuller {
33457113Smuller 	char *pt;
33557113Smuller 
33657113Smuller 	if (ftab != NULL)
33757113Smuller 		return(0);
33857113Smuller  	if ((ftab = (FTM **)calloc(F_TAB_SZ, sizeof(FTM *))) == NULL) {
33957113Smuller                 warn(1, "Cannot allocate memory for file time table");
34057113Smuller                 return(-1);
34157113Smuller         }
34257113Smuller 
34357113Smuller 	/*
34457113Smuller 	 * get random name and create temporary scratch file, unlink name
34557113Smuller 	 * so it will get removed on exit
34657113Smuller 	 */
34757113Smuller 	if ((pt = tempnam((char *)NULL, (char *)NULL)) == NULL)
34857113Smuller 		return(-1);
34957113Smuller 	(void)unlink(pt);
35057113Smuller 
35157113Smuller 	if ((ffd = open(pt, O_RDWR | O_CREAT,  S_IRWXU)) < 0) {
35257113Smuller 		syswarn(1, errno, "Unable to open temporary file: %s", pt);
35357113Smuller 		return(-1);
35457113Smuller 	}
35557113Smuller 
35657113Smuller 	(void)unlink(pt);
35757113Smuller 	return(0);
35857113Smuller }
35957113Smuller 
36057113Smuller /*
36157113Smuller  * chk_ftime()
36257113Smuller  *	looks up entry in file time hash table. If not found, the file is
36357113Smuller  *	added to the hash table and the file named stored in the scratch file.
36457113Smuller  *	If a file with the same name is found, the file times are compared and
36557113Smuller  *	the most recent file time is retained. If the new file was younger (or
36657113Smuller  *	was not in the database) the new file is selected for storage.
36757113Smuller  * Return:
36857113Smuller  *	0 if file should be added to the archive, 1 if it should be skipped,
36957113Smuller  *	-1 on error
37057113Smuller  */
37157113Smuller 
37257113Smuller #if __STDC__
37357113Smuller int
chk_ftime(register ARCHD * arcn)37457113Smuller chk_ftime(register ARCHD *arcn)
37557113Smuller #else
37657113Smuller int
37757113Smuller chk_ftime(arcn)
37857113Smuller 	register ARCHD *arcn;
37957113Smuller #endif
38057113Smuller {
38157113Smuller 	register FTM *pt;
38257113Smuller 	register int namelen;
38357113Smuller 	register u_int indx;
38457113Smuller 	char ckname[PAXPATHLEN+1];
38557113Smuller 
38657113Smuller 	/*
38757113Smuller 	 * no info, go ahead and add to archive
38857113Smuller 	 */
38957113Smuller 	if (ftab == NULL)
39057113Smuller 		return(0);
39157113Smuller 
39257113Smuller 	/*
39357113Smuller 	 * hash the pathname and look up in table
39457113Smuller 	 */
39557113Smuller 	namelen = arcn->nlen;
39657113Smuller 	indx = st_hash(arcn->name, namelen, F_TAB_SZ);
39757113Smuller 	if ((pt = ftab[indx]) != NULL) {
39857113Smuller 		/*
39957113Smuller 		 * the hash chain is not empty, walk down looking for match
40057113Smuller 		 * only read up the path names if the lengths match, speeds
40157113Smuller 		 * up the search a lot
40257113Smuller 		 */
40357113Smuller 		while (pt != NULL) {
40457113Smuller 			if (pt->namelen == namelen) {
40557113Smuller 				/*
40657113Smuller 				 * potential match, have to read the name
40757113Smuller 				 * from the scratch file.
40857113Smuller 				 */
40957113Smuller 				if (lseek(ffd,pt->seek,SEEK_SET) != pt->seek) {
41057113Smuller 					syswarn(1, errno,
41157113Smuller 					    "Failed ftime table seek");
41257113Smuller 					return(-1);
41357113Smuller 				}
41457113Smuller 				if (read(ffd, ckname, namelen) != namelen) {
41557113Smuller 					syswarn(1, errno,
41657113Smuller 					    "Failed ftime table read");
41757113Smuller 					return(-1);
41857113Smuller 				}
41957113Smuller 
42057113Smuller 				/*
42157113Smuller 				 * if the names match, we are done
42257113Smuller 				 */
42357113Smuller 				if (!strncmp(ckname, arcn->name, namelen))
42457113Smuller 					break;
42557113Smuller 			}
42657113Smuller 
42757113Smuller 			/*
42857113Smuller 			 * try the next entry on the chain
42957113Smuller 			 */
43057113Smuller 			pt = pt->fow;
43157113Smuller 		}
43257113Smuller 
43357113Smuller 		if (pt != NULL) {
43457113Smuller 			/*
43557113Smuller 			 * found the file, compare the times, save the newer
43657113Smuller 			 */
43757113Smuller 			if (arcn->sb.st_mtime > pt->mtime) {
43857113Smuller 				/*
43957113Smuller 				 * file is newer
44057113Smuller 				 */
44157113Smuller 				pt->mtime = arcn->sb.st_mtime;
44257113Smuller 				return(0);
44357113Smuller 			}
44457113Smuller 			/*
44557113Smuller 			 * file is older
44657113Smuller 			 */
44757113Smuller 			return(1);
44857113Smuller 		}
44957113Smuller 	}
45057113Smuller 
45157113Smuller 	/*
45257113Smuller 	 * not in table, add it
45357113Smuller 	 */
45457113Smuller 	if ((pt = (FTM *)malloc(sizeof(FTM))) != NULL) {
45557113Smuller 		/*
45657113Smuller 		 * add the name at the end of the scratch file, saving the
45757113Smuller 		 * offset. add the file to the head of the hash chain
45857113Smuller 		 */
45957113Smuller 		if ((pt->seek = lseek(ffd, (off_t)0, SEEK_END)) >= 0) {
46057113Smuller 			if (write(ffd, arcn->name, namelen) == namelen) {
46157113Smuller 				pt->mtime = arcn->sb.st_mtime;
46257113Smuller 				pt->namelen = namelen;
46357113Smuller 				pt->fow = ftab[indx];
46457113Smuller 				ftab[indx] = pt;
46557113Smuller 				return(0);
46657113Smuller 			}
46757113Smuller 			syswarn(1, errno, "Failed write to file time table");
46857113Smuller 		} else
46957113Smuller 			syswarn(1, errno, "Failed seek on file time table");
47057113Smuller 	} else
47157113Smuller 		warn(1, "File time table ran out of memory");
47257113Smuller 
47357113Smuller 	if (pt != NULL)
47457113Smuller 		(void)free((char *)pt);
47557113Smuller 	return(-1);
47657113Smuller }
47757113Smuller 
47857113Smuller /*
47957113Smuller  * Interactive rename table routines
48057113Smuller  *
48157113Smuller  * The interactive rename table keeps track of the new names that the user
48257113Smuller  * assignes to files from tty input. Since this map is unique for each file
48357113Smuller  * we must store it in case there is a reference to the file later in archive
48457113Smuller  * (a link). Otherwise we will be unable to find the file we know was
48557113Smuller  * extracted. The remapping of these files is stored in a memory based hash
48657113Smuller  * table (it is assumed since input must come from /dev/tty, it is unlikely to
48757113Smuller  * be a very large table).
48857113Smuller  */
48957113Smuller 
49057113Smuller /*
49157113Smuller  * name_start()
49257113Smuller  *	create the interactive rename table
49357113Smuller  * Return:
49457113Smuller  *	0 if successful, -1 otherwise
49557113Smuller  */
49657113Smuller 
49757113Smuller #if __STDC__
49857113Smuller int
name_start(void)49957113Smuller name_start(void)
50057113Smuller #else
50157113Smuller int
50257113Smuller name_start()
50357113Smuller #endif
50457113Smuller {
50557113Smuller 	if (ntab != NULL)
50657113Smuller 		return(0);
50757113Smuller  	if ((ntab = (NAMT **)calloc(N_TAB_SZ, sizeof(NAMT *))) == NULL) {
50857113Smuller                 warn(1, "Cannot allocate memory for interactive rename table");
50957113Smuller                 return(-1);
51057113Smuller         }
51157113Smuller 	return(0);
51257113Smuller }
51357113Smuller 
51457113Smuller /*
51557113Smuller  * add_name()
51657113Smuller  *	add the new name to old name mapping just created by the user.
51757113Smuller  *	If an old name mapping is found (there may be duplicate names on an
51857113Smuller  *	archive) only the most recent is kept.
51957113Smuller  * Return:
52057113Smuller  *	0 if added, -1 otherwise
52157113Smuller  */
52257113Smuller 
52357113Smuller #if __STDC__
52457113Smuller int
add_name(register char * oname,int onamelen,char * nname)52557113Smuller add_name(register char *oname, int onamelen, char *nname)
52657113Smuller #else
52757113Smuller int
52857113Smuller add_name(oname, onamelen, nname)
52957113Smuller 	register char *oname;
53057113Smuller 	int onamelen;
53157113Smuller 	char *nname;
53257113Smuller #endif
53357113Smuller {
53457113Smuller 	register NAMT *pt;
53557113Smuller 	register u_int indx;
53657113Smuller 
53757113Smuller 	if (ntab == NULL) {
53857113Smuller 		/*
53957113Smuller 		 * should never happen
54057113Smuller 		 */
54157113Smuller 		warn(0, "No interactive rename table, links may fail\n");
54257113Smuller 		return(0);
54357113Smuller 	}
54457113Smuller 
54557113Smuller 	/*
54657113Smuller 	 * look to see if we have already mapped this file, if so we
54757113Smuller 	 * will update it
54857113Smuller 	 */
54957113Smuller 	indx = st_hash(oname, onamelen, N_TAB_SZ);
55057113Smuller 	if ((pt = ntab[indx]) != NULL) {
55157113Smuller 		/*
55257113Smuller 		 * look down the has chain for the file
55357113Smuller 		 */
55457113Smuller 		while ((pt != NULL) && (strcmp(oname, pt->oname) != 0))
55557113Smuller 			pt = pt->fow;
55657113Smuller 
55757113Smuller 		if (pt != NULL) {
55857113Smuller 			/*
55957113Smuller 			 * found an old mapping, replace it with the new one
56057113Smuller 			 * the user just input (if it is different)
56157113Smuller 			 */
56257113Smuller 			if (strcmp(nname, pt->nname) == 0)
56357113Smuller 				return(0);
56457113Smuller 
56557113Smuller 			(void)free((char *)pt->nname);
56657113Smuller 			if ((pt->nname = strdup(nname)) == NULL) {
56757113Smuller 				warn(1, "Cannot update rename table");
56857113Smuller 				return(-1);
56957113Smuller 			}
57057113Smuller 			return(0);
57157113Smuller 		}
57257113Smuller 	}
57357113Smuller 
57457113Smuller 	/*
57557113Smuller 	 * this is a new mapping, add it to the table
57657113Smuller 	 */
57757113Smuller 	if ((pt = (NAMT *)malloc(sizeof(NAMT))) != NULL) {
57857113Smuller 		if ((pt->oname = strdup(oname)) != NULL) {
57957113Smuller 			if ((pt->nname = strdup(nname)) != NULL) {
58057113Smuller 				pt->fow = ntab[indx];
58157113Smuller 				ntab[indx] = pt;
58257113Smuller 				return(0);
58357113Smuller 			}
58457113Smuller 			(void)free((char *)pt->oname);
58557113Smuller 		}
58657113Smuller 		(void)free((char *)pt);
58757113Smuller 	}
58857113Smuller 	warn(1, "Interactive rename table out of memory");
58957113Smuller 	return(-1);
59057113Smuller }
59157113Smuller 
59257113Smuller /*
59357113Smuller  * sub_name()
59457113Smuller  *	look up a link name to see if it points at a file that has been
59557113Smuller  *	remapped by the user. If found, the link is adjusted to contain the
59657113Smuller  *	new name (oname is the link to name)
59757113Smuller  */
59857113Smuller 
59957113Smuller #if __STDC__
60057113Smuller void
sub_name(register char * oname,int * onamelen)60157113Smuller sub_name(register char *oname, int *onamelen)
60257113Smuller #else
60357113Smuller void
60457113Smuller sub_name(oname, onamelen)
60557113Smuller 	register char *oname;
60657113Smuller 	int *onamelen;
60757113Smuller #endif
60857113Smuller {
60957113Smuller 	register NAMT *pt;
61057113Smuller 	register u_int indx;
61157113Smuller 
61257113Smuller 	if (ntab == NULL)
61357113Smuller 		return;
61457113Smuller 	/*
61557113Smuller 	 * look the name up in the hash table
61657113Smuller 	 */
61757113Smuller 	indx = st_hash(oname, *onamelen, N_TAB_SZ);
61857113Smuller 	if ((pt = ntab[indx]) == NULL)
61957113Smuller 		return;
62057113Smuller 
62157113Smuller 	while (pt != NULL) {
62257113Smuller 		/*
62357113Smuller 		 * walk down the hash cahin looking for a match
62457113Smuller 		 */
62557113Smuller 		if (strcmp(oname, pt->oname) == 0) {
62657113Smuller 			/*
62757113Smuller 			 * found it, replace it with the new name
62857113Smuller 			 * and return (we know that oname has enough space)
62957113Smuller 			 */
63057113Smuller 			*onamelen = l_strncpy(oname, pt->nname, PAXPATHLEN+1);
63157113Smuller 			return;
63257113Smuller 		}
63357113Smuller 		pt = pt->fow;
63457113Smuller 	}
63557113Smuller 
63657113Smuller 	/*
63757113Smuller 	 * no match, just return
63857113Smuller 	 */
63957113Smuller 	return;
64057113Smuller }
64157113Smuller 
64257113Smuller /*
64357113Smuller  * device/inode mapping table routines
64457113Smuller  * (used with formats that store device and inodes fields)
64557113Smuller  *
64657113Smuller  * device/inode mapping tables remap the device field in a archive header. The
64757113Smuller  * device/inode fields are used to determine when files are hard links to each
64857113Smuller  * other. However these values have very little meaning outside of that. This
64957113Smuller  * database is used to solve one of two different problems.
65057113Smuller  *
65157113Smuller  * 1) when files are appended to an archive, while the new files may have hard
65257113Smuller  * links to each other, you cannot determine if they have hard links to any
65357113Smuller  * file already stored on the archive from a prior run of pax. We must assume
65457113Smuller  * that these inode/device pairs are unique only within a SINGLE run of pax
65557113Smuller  * (which adds a set of files to an archive). So we have to make sure the
65657113Smuller  * inode/dev pairs we add each time are always unique. We do this by observing
65757113Smuller  * while the inode field is very dense, the use of the dev field is fairly
65857113Smuller  * sparse. Within each run of pax, we remap any device number of a new archive
65957113Smuller  * member that has a device number used in a prior run and already stored in a
66057113Smuller  * file on the archive. During the read phase of the append, we store the
66157113Smuller  * device numbers used and mark them to not be used by any file during the
66257113Smuller  * write phase. If during write we go to use one of those old device numbers,
66357113Smuller  * we remap it to a new value.
66457113Smuller  *
66557113Smuller  * 2) Often the fields in the archive header used to store these values are
66657113Smuller  * too small to store the entire value. The result is an inode or device value
66757113Smuller  * which can be truncated. This really can foul up an archive. With truncation
66857113Smuller  * we end up creating links between files that are really not links (after
66957113Smuller  * truncation the inodes are the same value). We address that by detecting
67057113Smuller  * truncation and forcing a remap of the device field to split truncated
67157113Smuller  * inodes away from each other. Each truncation creates a pattern of bits that
67257113Smuller  * are removed. We use this pattern of truncated bits to partition the inodes
67357113Smuller  * on a single device to many different devices (each one represented by the
67457113Smuller  * truncated bit pattern). All inodes on the same device that have the same
67557113Smuller  * truncation pattern are mapped to the same new device. Two inodes that
67657113Smuller  * truncate to the same value clearly will always have different truncation
67757113Smuller  * bit patterns, so they will be split from away each other. When we spot
67857113Smuller  * device truncation we remap the device number to a non truncated value.
67957113Smuller  * (for more info see table.h for the data structures involved).
68057113Smuller  */
68157113Smuller 
68257113Smuller /*
68357113Smuller  * dev_start()
68457113Smuller  *	create the device mapping table
68557113Smuller  * Return:
68657113Smuller  *	0 if successful, -1 otherwise
68757113Smuller  */
68857113Smuller 
68957113Smuller #if __STDC__
69057113Smuller int
dev_start(void)69157113Smuller dev_start(void)
69257113Smuller #else
69357113Smuller int
69457113Smuller dev_start()
69557113Smuller #endif
69657113Smuller {
69757113Smuller 	if (dtab != NULL)
69857113Smuller 		return(0);
69957113Smuller  	if ((dtab = (DEVT **)calloc(D_TAB_SZ, sizeof(DEVT *))) == NULL) {
70057113Smuller                 warn(1, "Cannot allocate memory for device mapping table");
70157113Smuller                 return(-1);
70257113Smuller         }
70357113Smuller 	return(0);
70457113Smuller }
70557113Smuller 
70657113Smuller /*
70757113Smuller  * add_dev()
70857113Smuller  *	add a device number to the table. this will force the device to be
70957113Smuller  *	remapped to a new value if it be used during a write phase. This
71057113Smuller  *	function is called during the read phase of an append to prohibit the
71157113Smuller  *	use of any device number already in the archive.
71257113Smuller  * Return:
71357113Smuller  *	0 if added ok, -1 otherwise
71457113Smuller  */
71557113Smuller 
71657113Smuller #if __STDC__
71757113Smuller int
add_dev(register ARCHD * arcn)71857113Smuller add_dev(register ARCHD *arcn)
71957113Smuller #else
72057113Smuller int
72157113Smuller add_dev(arcn)
72257113Smuller 	register ARCHD *arcn;
72357113Smuller #endif
72457113Smuller {
72557113Smuller 	if (chk_dev(arcn->sb.st_dev, 1) == NULL)
72657113Smuller 		return(-1);
72757113Smuller 	return(0);
72857113Smuller }
72957113Smuller 
73057113Smuller /*
73157113Smuller  * chk_dev()
73257113Smuller  *	check for a device value in the device table. If not found and the add
73357113Smuller  *	flag is set, it is added. This does NOT assign any mapping values, just
73457113Smuller  *	adds the device number as one that need to be remapped. If this device
73557113Smuller  *	is alread mapped, just return with a pointer to that entry.
73657113Smuller  * Return:
73757113Smuller  *	pointer to the entry for this device in the device map table. Null
73857113Smuller  *	if the add flag is not set and the device is not in the table (it is
73957113Smuller  *	not been seen yet). If add is set and the device cannot be added, null
74057113Smuller  *	is returned (indicates an error).
74157113Smuller  */
74257113Smuller 
74357113Smuller #if __STDC__
74457113Smuller static DEVT *
chk_dev(dev_t dev,int add)74557113Smuller chk_dev(dev_t dev, int add)
74657113Smuller #else
74757113Smuller static DEVT *
74857113Smuller chk_dev(dev, add)
74957113Smuller 	dev_t dev;
75057113Smuller 	int add;
75157113Smuller #endif
75257113Smuller {
75357113Smuller 	register DEVT *pt;
75457113Smuller 	register u_int indx;
75557113Smuller 
75657113Smuller 	if (dtab == NULL)
75757113Smuller 		return(NULL);
75857113Smuller 	/*
75957113Smuller 	 * look to see if this device is already in the table
76057113Smuller 	 */
76157113Smuller 	indx = ((unsigned)dev) % D_TAB_SZ;
76257113Smuller 	if ((pt = dtab[indx]) != NULL) {
76357113Smuller 		while ((pt != NULL) && (pt->dev != dev))
76457113Smuller 			pt = pt->fow;
76557113Smuller 
76657113Smuller 		/*
76757113Smuller 		 * found it, return a pointer to it
76857113Smuller 		 */
76957113Smuller 		if (pt != NULL)
77057113Smuller 			return(pt);
77157113Smuller 	}
77257113Smuller 
77357113Smuller 	/*
77457113Smuller 	 * not in table, we add it only if told to as this may just be a check
77557113Smuller 	 * to see if a device number is being used.
77657113Smuller 	 */
77757113Smuller 	if (add == 0)
77857113Smuller 		return(NULL);
77957113Smuller 
78057113Smuller 	/*
78157113Smuller 	 * allocate a node for this device and add it to the front of the hash
78257113Smuller 	 * chain. Note we do not assign remaps values here, so the pt->list
78357113Smuller 	 * list must be NULL.
78457113Smuller 	 */
78557113Smuller 	if ((pt = (DEVT *)malloc(sizeof(DEVT))) == NULL) {
78657113Smuller 		warn(1, "Device map table out of memory");
78757113Smuller 		return(NULL);
78857113Smuller 	}
78957113Smuller 	pt->dev = dev;
79057113Smuller 	pt->list = NULL;
79157113Smuller 	pt->fow = dtab[indx];
79257113Smuller 	dtab[indx] = pt;
79357113Smuller 	return(pt);
79457113Smuller }
79557113Smuller /*
79657113Smuller  * map_dev()
79757113Smuller  *	given an inode and device storage mask (the mask has a 1 for each bit
79857113Smuller  *	the archive format is able to store in a header), we check for inode
79957113Smuller  *	and device truncation and remap the device as required. Device mapping
80057113Smuller  *	can also occur when during the read phase of append a device number was
80157113Smuller  *	seen (and was marked as do not use during the write phase). WE ASSUME
80257113Smuller  *	that unsigned longs are the same size or bigger than the fields used
80357113Smuller  *	for ino_t and dev_t. If not the types will have to be changed.
80457113Smuller  * Return:
80557113Smuller  *	0 if all ok, -1 otherwise.
80657113Smuller  */
80757113Smuller 
80857113Smuller #if __STDC__
80957113Smuller int
map_dev(register ARCHD * arcn,u_long dev_mask,u_long ino_mask)81057113Smuller map_dev(register ARCHD *arcn, u_long dev_mask, u_long ino_mask)
81157113Smuller #else
81257113Smuller int
81357113Smuller map_dev(arcn, dev_mask, ino_mask)
81457113Smuller 	register ARCHD *arcn;
81557113Smuller 	u_long dev_mask;
81657113Smuller 	u_long ino_mask;
81757113Smuller #endif
81857113Smuller {
81957113Smuller 	register DEVT *pt;
82057113Smuller 	register DLIST *dpt;
82157113Smuller 	static dev_t lastdev = 0;	/* next device number to try */
82257113Smuller 	int trc_ino = 0;
82357113Smuller 	int trc_dev = 0;
82457113Smuller 	ino_t trunc_bits = 0;
82557113Smuller 	ino_t nino;
82657113Smuller 
82757113Smuller 	if (dtab == NULL)
82857113Smuller 		return(0);
82957113Smuller 	/*
83057113Smuller 	 * check for device and inode truncation, and extract the truncated
83157113Smuller 	 * bit pattern.
83257113Smuller 	 */
83357113Smuller 	if ((arcn->sb.st_dev & (dev_t)dev_mask) != arcn->sb.st_dev)
83457113Smuller 		++trc_dev;
83557113Smuller 	if ((nino = arcn->sb.st_ino & (ino_t)ino_mask) != arcn->sb.st_ino) {
83657113Smuller 		++trc_ino;
83757113Smuller 		trunc_bits = arcn->sb.st_ino & (ino_t)(~ino_mask);
83857113Smuller 	}
83957113Smuller 
84057113Smuller 	/*
84157113Smuller 	 * see if this device is already being mapped, look up the device
84257113Smuller 	 * then find the truncation bit pattern which applies
84357113Smuller 	 */
84457113Smuller 	if ((pt = chk_dev(arcn->sb.st_dev, 0)) != NULL) {
84557113Smuller 		/*
84657113Smuller 		 * this device is already marked to be remapped
84757113Smuller 		 */
84857113Smuller 		for (dpt = pt->list; dpt != NULL; dpt = dpt->fow)
84957113Smuller 			if (dpt->trunc_bits == trunc_bits)
85057113Smuller 				break;
85157113Smuller 
85257113Smuller 		if (dpt != NULL) {
85357113Smuller 			/*
85457113Smuller 			 * we are being remapped for this device and pattern
85557113Smuller 			 * change the device number to be stored and return
85657113Smuller 			 */
85757113Smuller 			arcn->sb.st_dev = dpt->dev;
85857113Smuller 			arcn->sb.st_ino = nino;
85957113Smuller 			return(0);
86057113Smuller 		}
86157113Smuller 	} else {
86257113Smuller 		/*
86357113Smuller 		 * this device is not being remapped YET. if we do not have any
86457113Smuller 		 * form of truncation, we do not need a remap
86557113Smuller 		 */
86657113Smuller 		if (!trc_ino && !trc_dev)
86757113Smuller 			return(0);
86857113Smuller 
86957113Smuller 		/*
87057113Smuller 		 * we have truncation, have to add this as a device to remap
87157113Smuller 		 */
87257113Smuller 		if ((pt = chk_dev(arcn->sb.st_dev, 1)) == NULL)
87357113Smuller 			goto bad;
87457113Smuller 
87557113Smuller 		/*
87657113Smuller 		 * if we just have a truncated inode, we have to make sure that
87757113Smuller 		 * all future inodes that do not truncate (they have the
87857113Smuller 		 * truncation pattern of all 0's) continue to map to the same
87957113Smuller 		 * device number. We probably have already written inodes with
88057113Smuller 		 * this device number to the archive with the truncation
88157113Smuller 		 * pattern of all 0's. So we add the mapping for all 0's to the
88257113Smuller 		 * same device number.
88357113Smuller 		 */
88457113Smuller 		if (!trc_dev && (trunc_bits != 0)) {
88557113Smuller 			if ((dpt = (DLIST *)malloc(sizeof(DLIST))) == NULL)
88657113Smuller 				goto bad;
88757113Smuller 			dpt->trunc_bits = 0;
88857113Smuller 			dpt->dev = arcn->sb.st_dev;
88957113Smuller 			dpt->fow = pt->list;
89057113Smuller 			pt->list = dpt;
89157113Smuller 		}
89257113Smuller 	}
89357113Smuller 
89457113Smuller 	/*
89557113Smuller 	 * look for a device number not being used. We must watch for wrap
89657113Smuller 	 * around on lastdev (so we do not get stuck looking forever!)
89757113Smuller 	 */
89857113Smuller 	while (++lastdev > 0) {
89957113Smuller 		if (chk_dev(lastdev, 0) != NULL)
90057113Smuller 			continue;
90157113Smuller 		/*
90257113Smuller 		 * found an unused value. If we have reached truncation point
90357113Smuller 		 * for this format we are hosed, so we give up. Otherwise we
90457113Smuller 		 * mark it as being used.
90557113Smuller 		 */
90657113Smuller 		if (((lastdev & ((dev_t)dev_mask)) != lastdev) ||
90757113Smuller 		    (chk_dev(lastdev, 1) == NULL))
90857113Smuller 			goto bad;
90957113Smuller 		break;
91057113Smuller 	}
91157113Smuller 
91257113Smuller 	if ((lastdev <= 0) || ((dpt = (DLIST *)malloc(sizeof(DLIST))) == NULL))
91357113Smuller 		goto bad;
91457113Smuller 
91557113Smuller 	/*
91657113Smuller 	 * got a new device number, store it under this truncation pattern.
91757113Smuller 	 * change the device number this file is being stored with.
91857113Smuller 	 */
91957113Smuller 	dpt->trunc_bits = trunc_bits;
92057113Smuller 	dpt->dev = lastdev;
92157113Smuller 	dpt->fow = pt->list;
92257113Smuller 	pt->list = dpt;
92357113Smuller 	arcn->sb.st_dev = lastdev;
92457113Smuller 	arcn->sb.st_ino = nino;
92557113Smuller 	return(0);
92657113Smuller 
92757113Smuller     bad:
92857113Smuller 	warn(1, "Unable to fix truncated inode/device field when storing %s",
92957113Smuller 	    arcn->name);
93057113Smuller 	warn(0, "Archive may create improper hard links when extracted");
93157113Smuller 	return(0);
93257113Smuller }
93357113Smuller 
93457113Smuller /*
93557113Smuller  * directory access/mod time reset table routines (for directories READ by pax)
93657113Smuller  *
93757113Smuller  * The pax -t flag requires that access times of archive files to be the same
93857113Smuller  * before being read by pax. For regular files, access time is restored after
93957113Smuller  * the file has been copied. This database provides the same functionality for
94057113Smuller  * directories read during file tree traversal. Restoring directory access time
94157113Smuller  * is more complex than files since directories may be read several times until
94257113Smuller  * all the descendants in their subtree are visited by fts. Directory access
94357113Smuller  * and modification times are stored during the fts pre-order visit (done
94457113Smuller  * before any descendants in the subtree is visited) and restored after the
94557113Smuller  * fts post-order visit (after all the descendants have been visited). In the
94657113Smuller  * case of premature exit from a subtree (like from the effects of -n), any
94757113Smuller  * directory entries left in this database are reset during final cleanup
94857113Smuller  * operations of pax. Entries are hashed by inode number for fast lookup.
94957113Smuller  */
95057113Smuller 
95157113Smuller /*
95257113Smuller  * atdir_start()
95357113Smuller  *	create the directory access time database for directories READ by pax.
95457113Smuller  * Return:
95557113Smuller  *	0 is created ok, -1 otherwise.
95657113Smuller  */
95757113Smuller 
95857113Smuller #if __STDC__
95957113Smuller int
atdir_start(void)96057113Smuller atdir_start(void)
96157113Smuller #else
96257113Smuller int
96357113Smuller atdir_start()
96457113Smuller #endif
96557113Smuller {
96657113Smuller 	if (atab != NULL)
96757113Smuller 		return(0);
96857113Smuller  	if ((atab = (ATDIR **)calloc(A_TAB_SZ, sizeof(ATDIR *))) == NULL) {
96957113Smuller                 warn(1,"Cannot allocate space for directory access time table");
97057113Smuller                 return(-1);
97157113Smuller         }
97257113Smuller 	return(0);
97357113Smuller }
97457113Smuller 
97557113Smuller 
97657113Smuller /*
97757113Smuller  * atdir_end()
97857113Smuller  *	walk through the directory access time table and reset the access time
97957113Smuller  *	of any directory who still has an entry left in the database. These
98057113Smuller  *	entries are for directories READ by pax
98157113Smuller  */
98257113Smuller 
98357113Smuller #if __STDC__
98457113Smuller void
atdir_end(void)98557113Smuller atdir_end(void)
98657113Smuller #else
98757113Smuller void
98857113Smuller atdir_end()
98957113Smuller #endif
99057113Smuller {
99157113Smuller 	register ATDIR *pt;
99257113Smuller 	register int i;
99357113Smuller 
99457113Smuller 	if (atab == NULL)
99557113Smuller 		return;
99657113Smuller 	/*
99757113Smuller 	 * for each non-empty hash table entry reset all the directories
99857113Smuller 	 * chained there.
99957113Smuller 	 */
100057113Smuller 	for (i = 0; i < A_TAB_SZ; ++i) {
100157113Smuller 		if ((pt = atab[i]) == NULL)
100257113Smuller 			continue;
100357113Smuller 		/*
100457113Smuller 		 * remember to force the times, set_ftime() looks at pmtime
100557113Smuller 		 * and patime, which only applies to things CREATED by pax,
100657113Smuller 		 * not read by pax. Read time reset is controlled by -t.
100757113Smuller 		 */
100857113Smuller 		for (; pt != NULL; pt = pt->fow)
100957113Smuller 			set_ftime(pt->name, pt->mtime, pt->atime, 1);
101057113Smuller 	}
101157113Smuller }
101257113Smuller 
101357113Smuller /*
101457113Smuller  * add_atdir()
101557113Smuller  *	add a directory to the directory access time table. Table is hashed
101657113Smuller  *	and chained by inode number. This is for directories READ by pax
101757113Smuller  */
101857113Smuller 
101957113Smuller #if __STDC__
102057113Smuller void
add_atdir(char * fname,dev_t dev,ino_t ino,time_t mtime,time_t atime)102157113Smuller add_atdir(char *fname, dev_t dev, ino_t ino, time_t mtime, time_t atime)
102257113Smuller #else
102357113Smuller void
102457113Smuller add_atdir(fname, dev, ino, mtime, atime)
102557113Smuller 	char *fname;
102657113Smuller 	dev_t dev;
102757113Smuller 	ino_t ino;
102857113Smuller 	time_t mtime;
102957113Smuller 	time_t atime;
103057113Smuller #endif
103157113Smuller {
103257113Smuller 	register ATDIR *pt;
103357113Smuller 	register u_int indx;
103457113Smuller 
103557113Smuller 	if (atab == NULL)
103657113Smuller 		return;
103757113Smuller 
103857113Smuller 	/*
103957113Smuller 	 * make sure this directory is not already in the table, if so just
104057113Smuller 	 * return (the older entry always has the correct time). The only
104157113Smuller 	 * way this will happen is when the same subtree can be traversed by
104257113Smuller 	 * different args to pax and the -n option is aborting fts out of a
104357113Smuller 	 * subtree before all the post-order visits have been made).
104457113Smuller 	 */
104557113Smuller 	indx = ((unsigned)ino) % A_TAB_SZ;
104657113Smuller 	if ((pt = atab[indx]) != NULL) {
104757113Smuller 		while (pt != NULL) {
104857113Smuller 			if ((pt->ino == ino) && (pt->dev == dev))
104957113Smuller 				break;
105057113Smuller 			pt = pt->fow;
105157113Smuller 		}
105257113Smuller 
105357113Smuller 		/*
105457113Smuller 		 * oops, already there. Leave it alone.
105557113Smuller 		 */
105657113Smuller 		if (pt != NULL)
105757113Smuller 			return;
105857113Smuller 	}
105957113Smuller 
106057113Smuller 	/*
106157113Smuller 	 * add it to the front of the hash chain
106257113Smuller 	 */
106357113Smuller 	if ((pt = (ATDIR *)malloc(sizeof(ATDIR))) != NULL) {
106457113Smuller 		if ((pt->name = strdup(fname)) != NULL) {
106557113Smuller 			pt->dev = dev;
106657113Smuller 			pt->ino = ino;
106757113Smuller 			pt->mtime = mtime;
106857113Smuller 			pt->atime = atime;
106957113Smuller 			pt->fow = atab[indx];
107057113Smuller 			atab[indx] = pt;
107157113Smuller 			return;
107257113Smuller 		}
107357113Smuller 		(void)free((char *)pt);
107457113Smuller 	}
107557113Smuller 
107657113Smuller 	warn(1, "Directory access time reset table ran out of memory");
107757113Smuller 	return;
107857113Smuller }
107957113Smuller 
108057113Smuller /*
108157113Smuller  * get_atdir()
108257113Smuller  *	look up a directory by inode and device number to obtain the access
108357113Smuller  *	and modification time you want to set to. If found, the modification
108457113Smuller  *	and access time parameters are set and the entry is removed from the
108557113Smuller  *	table (as it is no longer needed). These are for directories READ by
108657113Smuller  *	pax
108757113Smuller  * Return:
108857113Smuller  *	0 if found, -1 if not found.
108957113Smuller  */
109057113Smuller 
109157113Smuller #if __STDC__
109257113Smuller int
get_atdir(dev_t dev,ino_t ino,time_t * mtime,time_t * atime)109357113Smuller get_atdir(dev_t dev, ino_t ino, time_t *mtime, time_t *atime)
109457113Smuller #else
109557113Smuller int
109657113Smuller get_atdir(dev, ino, mtime, atime)
109757113Smuller 	dev_t dev;
109857113Smuller 	ino_t ino;
109957113Smuller 	time_t *mtime;
110057113Smuller 	time_t *atime;
110157113Smuller #endif
110257113Smuller {
110357113Smuller 	register ATDIR *pt;
110457113Smuller 	register ATDIR **ppt;
110557113Smuller 	register u_int indx;
110657113Smuller 
110757113Smuller 	if (atab == NULL)
110857113Smuller 		return(-1);
110957113Smuller 	/*
111057113Smuller 	 * hash by inode and search the chain for an inode and device match
111157113Smuller 	 */
111257113Smuller 	indx = ((unsigned)ino) % A_TAB_SZ;
111357113Smuller 	if ((pt = atab[indx]) == NULL)
111457113Smuller 		return(-1);
111557113Smuller 
111657113Smuller 	ppt = &(atab[indx]);
111757113Smuller 	while (pt != NULL) {
111857113Smuller 		if ((pt->ino == ino) && (pt->dev == dev))
111957113Smuller 			break;
112057113Smuller 		/*
112157113Smuller 		 * no match, go to next one
112257113Smuller 		 */
112357113Smuller 		ppt = &(pt->fow);
112457113Smuller 		pt = pt->fow;
112557113Smuller 	}
112657113Smuller 
112757113Smuller 	/*
112857113Smuller 	 * return if we did not find it.
112957113Smuller 	 */
113057113Smuller 	if (pt == NULL)
113157113Smuller 		return(-1);
113257113Smuller 
113357113Smuller 	/*
113457113Smuller 	 * found it. return the times and remove the entry from the table.
113557113Smuller 	 */
113657113Smuller 	*ppt = pt->fow;
113757113Smuller 	*mtime = pt->mtime;
113857113Smuller 	*atime = pt->atime;
113957113Smuller 	(void)free((char *)pt->name);
114057113Smuller 	(void)free((char *)pt);
114157113Smuller 	return(0);
114257113Smuller }
114357113Smuller 
114457113Smuller /*
114557113Smuller  * directory access mode and time storage routines (for directories CREATED
114657113Smuller  * by pax).
114757113Smuller  *
114857113Smuller  * Pax requires that extracted directories, by default, have their access/mod
114957113Smuller  * times and permissions set to the values specified in the archive. During the
115057113Smuller  * actions of extracting (and creating the destination subtree during -rw copy)
115157113Smuller  * directories extracted may be modified after being created. Even worse is
115257113Smuller  * that these directories may have been created with file permissions which
115357113Smuller  * prohibits any descendants of these directories from being extracted. When
115457113Smuller  * directories are created by pax, access rights may be added to permit the
115557113Smuller  * creation of files in their subtree. Every time pax creates a directory, the
115657113Smuller  * times and file permissions specified by the archive are stored. After all
115757113Smuller  * files have been extracted (or copied), these directories have their times
115857113Smuller  * and file modes reset to the stored values. The directory info is restored in
115957113Smuller  * reverse order as entries were added to the data file from root to leaf. To
116057113Smuller  * restore atime properly, we must go backwards. The data file consists of
116157113Smuller  * records with two parts, the file name followed by a DIRDATA trailer. The
116257113Smuller  * fixed sized trailer contains the size of the name plus the off_t location in
116357113Smuller  * the file. To restore we work backwards through the file reading the trailer
116457113Smuller  * then the file name.
116557113Smuller  */
116657113Smuller 
116757113Smuller /*
116857113Smuller  * dir_start()
116957113Smuller  *	set up the directory time and file mode storage for directories CREATED
117057113Smuller  *	by pax.
117157113Smuller  * Return:
117257113Smuller  *	0 if ok, -1 otherwise
117357113Smuller  */
117457113Smuller 
117557113Smuller #if __STDC__
117657113Smuller int
dir_start(void)117757113Smuller dir_start(void)
117857113Smuller #else
117957113Smuller int
118057113Smuller dir_start()
118157113Smuller #endif
118257113Smuller {
118357113Smuller 	char *pt;
118457113Smuller 
118557113Smuller 	if (dirfd != -1)
118657113Smuller 		return(0);
118757113Smuller 	if ((pt = tempnam((char *)NULL, (char *)NULL)) == NULL)
118857113Smuller 		return(-1);
118957113Smuller 
119057113Smuller 	/*
119157113Smuller 	 * unlink the file so it goes away at termination by itself
119257113Smuller 	 */
119357113Smuller 	(void)unlink(pt);
119457113Smuller 	if ((dirfd = open(pt, O_RDWR|O_CREAT, 0600)) >= 0) {
119557113Smuller 		(void)unlink(pt);
119657113Smuller 		return(0);
119757113Smuller 	}
119857113Smuller 	warn(1, "Unable to create temporary file for directory times: %s", pt);
119957113Smuller 	return(-1);
120057113Smuller }
120157113Smuller 
120257113Smuller /*
120357113Smuller  * add_dir()
120457113Smuller  *	add the mode and times for a newly CREATED directory
120557113Smuller  *	name is name of the directory, psb the stat buffer with the data in it,
120657113Smuller  *	frc_mode is a flag that says whether to force the setting of the mode
120757113Smuller  *	(ignoring the user set values for preserving file mode). Frc_mode is
120857113Smuller  *	for the case where we created a file and found that the resulting
120957113Smuller  *	directory was not writeable and the user asked for file modes to NOT
121057113Smuller  *	be preserved. (we have to preserve what was created by default, so we
121157113Smuller  *	have to force the setting at the end. this is stated explicitly in the
121257113Smuller  *	pax spec)
121357113Smuller  */
121457113Smuller 
121557113Smuller #if __STDC__
121657113Smuller void
add_dir(char * name,int nlen,struct stat * psb,int frc_mode)121757113Smuller add_dir(char *name, int nlen, struct stat *psb, int frc_mode)
121857113Smuller #else
121957113Smuller void
122057113Smuller add_dir(name, nlen, psb, frc_mode)
122157113Smuller 	char *name;
122257113Smuller 	int nlen;
122357113Smuller 	struct stat *psb;
122457113Smuller 	int frc_mode;
122557113Smuller #endif
122657113Smuller {
122757113Smuller 	DIRDATA dblk;
122857113Smuller 
122957113Smuller 	if (dirfd < 0)
123057113Smuller 		return;
123157113Smuller 
123257113Smuller 	/*
123357113Smuller 	 * get current position (where file name will start) so we can store it
123457113Smuller 	 * in the trailer
123557113Smuller 	 */
123657113Smuller 	if ((dblk.npos = lseek(dirfd, 0L, SEEK_CUR)) < 0) {
123757113Smuller 		warn(1,"Unable to store mode and times for directory: %s",name);
123857113Smuller 		return;
123957113Smuller 	}
124057113Smuller 
124157113Smuller 	/*
124257113Smuller 	 * write the file name followed by the trailer
124357113Smuller 	 */
124457113Smuller 	dblk.nlen = nlen + 1;
124557113Smuller 	dblk.mode = psb->st_mode & 0xffff;
124657113Smuller 	dblk.mtime = psb->st_mtime;
124757113Smuller 	dblk.atime = psb->st_atime;
124857113Smuller 	dblk.frc_mode = frc_mode;
124957113Smuller 	if ((write(dirfd, name, dblk.nlen) == dblk.nlen) &&
125057113Smuller 	    (write(dirfd, (char *)&dblk, sizeof(dblk)) == sizeof(dblk))) {
125157113Smuller 		++dircnt;
125257113Smuller 		return;
125357113Smuller 	}
125457113Smuller 
125557113Smuller 	warn(1,"Unable to store mode and times for created directory: %s",name);
125657113Smuller 	return;
125757113Smuller }
125857113Smuller 
125957113Smuller /*
126057113Smuller  * proc_dir()
126157113Smuller  *	process all file modes and times stored for directories CREATED
126257113Smuller  *	by pax
126357113Smuller  */
126457113Smuller 
126557113Smuller #if __STDC__
126657113Smuller void
proc_dir(void)126757113Smuller proc_dir(void)
126857113Smuller #else
126957113Smuller void
127057113Smuller proc_dir()
127157113Smuller #endif
127257113Smuller {
127357113Smuller 	char name[PAXPATHLEN+1];
127457113Smuller 	DIRDATA dblk;
127557113Smuller 	u_long cnt;
127657113Smuller 
127757113Smuller 	if (dirfd < 0)
127857113Smuller 		return;
127957113Smuller 	/*
128057113Smuller 	 * read backwards through the file and process each directory
128157113Smuller 	 */
128257113Smuller 	for (cnt = 0; cnt < dircnt; ++cnt) {
128357113Smuller 		/*
128457113Smuller 		 * read the trailer, then the file name, if this fails
128557113Smuller 		 * just give up.
128657113Smuller 		 */
128757113Smuller 		if (lseek(dirfd, -((off_t)sizeof(dblk)), SEEK_CUR) < 0)
128857113Smuller 			break;
128957113Smuller 		if (read(dirfd,(char *)&dblk, sizeof(dblk)) != sizeof(dblk))
129057113Smuller 			break;
129157113Smuller 		if (lseek(dirfd, dblk.npos, SEEK_SET) < 0)
129257113Smuller 			break;
129357113Smuller 		if (read(dirfd, name, dblk.nlen) != dblk.nlen)
129457113Smuller 			break;
129557113Smuller 		if (lseek(dirfd, dblk.npos, SEEK_SET) < 0)
129657113Smuller 			break;
129757113Smuller 
129857113Smuller 		/*
129957113Smuller 		 * frc_mode set, make sure we set the file modes even if
130057113Smuller 		 * the user didn't ask for it (see file_subs.c for more info)
130157113Smuller 		 */
130257113Smuller 		if (pmode || dblk.frc_mode)
130357113Smuller 			set_pmode(name, dblk.mode);
130457113Smuller 		if (patime || pmtime)
130557113Smuller 			set_ftime(name, dblk.mtime, dblk.atime, 0);
130657113Smuller 	}
130757113Smuller 
130857113Smuller 	(void)close(dirfd);
130957113Smuller 	dirfd = -1;
131057113Smuller 	if (cnt != dircnt)
131157113Smuller 		warn(1,"Unable to set mode and times for created directories");
131257113Smuller 	return;
131357113Smuller }
131457113Smuller 
131557113Smuller /*
131657113Smuller  * database independent routines
131757113Smuller  */
131857113Smuller 
131957113Smuller /*
132057113Smuller  * st_hash()
132157113Smuller  *	hashes filenames to a u_int for hashing into a table. Looks at the tail
132257113Smuller  *	end of file, as this provides far better distribution than any other
132357113Smuller  *	part of the name. For performance reasons we only care about the last
132457113Smuller  *	MAXKEYLEN chars (should be at LEAST large enough to pick off the file
132557113Smuller  *	name). Was tested on 500,000 name file tree traversal from the root
132657113Smuller  *	and gave almost a perfectly uniform distribution of keys when used with
132757113Smuller  *	prime sized tables (MAXKEYLEN was 128 in test). Hashes (sizeof int)
132857113Smuller  *	chars at a time and pads with 0 for last addition.
132957113Smuller  * Return:
133057113Smuller  *	the hash value of the string MOD (%) the table size.
133157113Smuller  */
133257113Smuller 
133357113Smuller #if __STDC__
133457113Smuller u_int
st_hash(char * name,int len,int tabsz)133557113Smuller st_hash(char *name, int len, int tabsz)
133657113Smuller #else
133757113Smuller u_int
133857113Smuller st_hash(name, len, tabsz)
133957113Smuller 	char *name;
134057113Smuller 	int len;
134157113Smuller 	int tabsz;
134257113Smuller #endif
134357113Smuller {
134457113Smuller 	register char *pt;
134557113Smuller 	register char *dest;
134657113Smuller 	register char *end;
134757113Smuller 	register int i;
134857113Smuller 	register u_int key = 0;
134957113Smuller 	register int steps;
135057113Smuller 	register int res;
135157113Smuller 	u_int val;
135257113Smuller 
135357113Smuller 	/*
135457113Smuller 	 * only look at the tail up to MAXKEYLEN, we do not need to waste
135557113Smuller 	 * time here (remember these are pathnames, the tail is what will
135657113Smuller 	 * spread out the keys)
135757113Smuller 	 */
135857113Smuller 	if (len > MAXKEYLEN) {
135957113Smuller                 pt = &(name[len - MAXKEYLEN]);
136057113Smuller 		len = MAXKEYLEN;
136157113Smuller 	} else
136257113Smuller 		pt = name;
136357113Smuller 
136457113Smuller 	/*
136557113Smuller 	 * calculate the number of u_int size steps in the string and if
136657113Smuller 	 * there is a runt to deal with
136757113Smuller 	 */
136857113Smuller 	steps = len/sizeof(u_int);
136957113Smuller 	res = len % sizeof(u_int);
137057113Smuller 
137157113Smuller 	/*
137257113Smuller 	 * add up the value of the string in unsigned integer sized pieces
137357113Smuller 	 * too bad we cannot have unsigned int aligned strings, then we
137457113Smuller 	 * could avoid the expensive copy.
137557113Smuller 	 */
137657113Smuller 	for (i = 0; i < steps; ++i) {
137757113Smuller 		end = pt + sizeof(u_int);
137857113Smuller 		dest = (char *)&val;
137957113Smuller 		while (pt < end)
138057113Smuller 			*dest++ = *pt++;
138157113Smuller 		key += val;
138257113Smuller 	}
138357113Smuller 
138457113Smuller 	/*
138557113Smuller 	 * add in the runt padded with zero to the right
138657113Smuller 	 */
138757113Smuller 	if (res) {
138857113Smuller 		val = 0;
138957113Smuller 		end = pt + res;
139057113Smuller 		dest = (char *)&val;
139157113Smuller 		while (pt < end)
139257113Smuller 			*dest++ = *pt++;
139357113Smuller 		key += val;
139457113Smuller 	}
139557113Smuller 
139657113Smuller 	/*
139757113Smuller 	 * return the result mod the table size
139857113Smuller 	 */
139957113Smuller 	return(key % tabsz);
140057113Smuller }
1401