tables.c

早期freebsd实现

/*-
 * Copyright (c) 1992 Keith Muller.
 * Copyright (c) 1992, 1993
 *	The Regents of the University of California.  All rights reserved.
 *
 * This code is derived from software contributed to Berkeley by
 * Keith Muller of the University of California, San Diego.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *	This product includes software developed by the University of
 *	California, Berkeley and its contributors.
 * 4. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#ifndef lint
static char sccsid[] = "@(#)tables.c	8.1 (Berkeley) 5/31/93";
#endif /* not lint */

#include <sys/types.h>
#include <sys/time.h>
#include <sys/stat.h>
#include <sys/param.h>
#include <sys/fcntl.h>
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <unistd.h>
#include <errno.h>
#include <stdlib.h>
#include "pax.h"
#include "tables.h"
#include "extern.h"

/*
 * Routines for controlling the contents of all the different databases pax
 * keeps. Tables are dynamically created only when they are needed. The
 * goal was speed and the ability to work with HUGE archives. The databases
 * were kept simple, but do have complex rules for when the contents change.
 * As of this writing, the posix library functions were more complex than
 * needed for this application (pax databases have very short lifetimes and
 * do not survive after pax is finished). Pax is required to handle very
 * large archives. These database routines carefully combine memory usage and
 * temporary file storage in ways which will not significantly impact runtime
 * performance while allowing the largest possible archives to be handled.
 * Trying to force the fit to the posix databases routines was not considered
 * time well spent.
 */

static HRDLNK **ltab = NULL;	/* hard link table for detecting hard links */
static FTM **ftab = NULL;	/* file time table for updating arch */
static NAMT **ntab = NULL;	/* interactive rename storage table */
static DEVT **dtab = NULL;	/* device/inode mapping tables */
static ATDIR **atab = NULL;	/* file tree directory time reset table */
static int dirfd = -1;		/* storage for setting created dir time/mode */
static u_long dircnt;		/* entries in dir time/mode storage */
static int ffd = -1;		/* tmp file for file time table name storage */

static DEVT *chk_dev __P((dev_t, int));

/*
 * hard link table routines
 *
 * The hard link table tries to detect hard links to files using the device and 
 * inode values. We do this when writing an archive, so we can tell the format
 * write routine that this file is a hard link to another file. The format
 * write routine then can store this file in whatever way it wants (as a hard
 * link if the format supports that like tar, or ignore this info like cpio).
 * (Actually a field in the format driver table tells us if the format wants
 * hard link info. if not, we do not waste time looking for them). We also use
 * the same table when reading an archive. In that situation, this table is
 * used by the format read routine to detect hard links from stored dev and
 * inode numbers (like cpio). This will allow pax to create a link when one
 * can be detected by the archive format.
 */

/*
 * lnk_start
 *	Creates the hard link table.
 * Return:
 *	0 if created, -1 if failure
 */

#if __STDC__
int
lnk_start(void)
#else
int
lnk_start()
#endif
{
	if (ltab != NULL)
		return(0);
 	if ((ltab = (HRDLNK **)calloc(L_TAB_SZ, sizeof(HRDLNK *))) == NULL) {
                warn(1, "Cannot allocate memory for hard link table");
                return(-1);
        }
	return(0);
}

/*
 * chk_lnk()
 *	Looks up entry in hard link hash table. If found, it copies the name
 *	of the file it is linked to (we already saw that file) into ln_name.
 *	lnkcnt is decremented and if goes to 1 the node is deleted from the
 *	database. (We have seen all the links to this file). If not found,
 *	we add the file to the database if it has the potential for having
 *	hard links to other files we may process (it has a link count > 1)
 * Return:
 *	if found returns 1; if not found returns 0; -1 on error
 */

#if __STDC__
int
chk_lnk(register ARCHD *arcn)
#else
int
chk_lnk(arcn)
	register ARCHD *arcn;
#endif
{
	register HRDLNK *pt;
	register HRDLNK **ppt;
	register u_int indx;

	if (ltab == NULL)
		return(-1);
	/*
	 * ignore those nodes that cannot have hard links
	 */
	if ((arcn->type == PAX_DIR) || (arcn->sb.st_nlink <= 1))
		return(0);

	/*
	 * hash inode number and look for this file
	 */
	indx = ((unsigned)arcn->sb.st_ino) % L_TAB_SZ;
	if ((pt = ltab[indx]) != NULL) {
		/*
		 * it's hash chain in not empty, walk down looking for it
		 */
		ppt = &(ltab[indx]);
		while (pt != NULL) {
			if ((pt->ino == arcn->sb.st_ino) &&
			    (pt->dev == arcn->sb.st_dev))
				break;
			ppt = &(pt->fow);
			pt = pt->fow;
		}

		if (pt != NULL) {
			/*
			 * found a link. set the node type and copy in the
			 * name of the file it is to link to. we need to
			 * handle hardlinks to regular files differently than
			 * other links.
			 */
			arcn->ln_nlen = l_strncpy(arcn->ln_name, pt->name,
				PAXPATHLEN+1);
			if (arcn->type == PAX_REG)
				arcn->type = PAX_HRG;
			else
				arcn->type = PAX_HLK;

			/*
			 * if we have found all the links to this file, remove
			 * it from the database
			 */
			if (--pt->nlink <= 1) {
				*ppt = pt->fow;
				(void)free((char *)pt->name);
				(void)free((char *)pt);
			}
			return(1);
		}
	}

	/*
	 * we never saw this file before. It has links so we add it to the
	 * front of this hash chain
	 */
	if ((pt = (HRDLNK *)malloc(sizeof(HRDLNK))) != NULL) {
		if ((pt->name = strdup(arcn->name)) != NULL) {
			pt->dev = arcn->sb.st_dev;
			pt->ino = arcn->sb.st_ino;
			pt->nlink = arcn->sb.st_nlink;
			pt->fow = ltab[indx];
			ltab[indx] = pt;
			return(0);
		}
		(void)free((char *)pt);
	}

	warn(1, "Hard link table out of memory");
	return(-1);
}

/*
 * purg_lnk
 *	remove reference for a file that we may have added to the data base as
 *	a potential source for hard links. We ended up not using the file, so
 *	we do not want to accidently point another file at it later on.
 */

#if __STDC__
void
purg_lnk(register ARCHD *arcn)
#else
void
purg_lnk(arcn)
	register ARCHD *arcn;
#endif
{
	register HRDLNK *pt;
	register HRDLNK **ppt;
	register u_int indx;

	if (ltab == NULL)
		return;
	/*
	 * do not bother to look if it could not be in the database
	 */
	if ((arcn->sb.st_nlink <= 1) || (arcn->type == PAX_DIR) ||
	    (arcn->type == PAX_HLK) || (arcn->type == PAX_HRG))
		return;

	/*
	 * find the hash chain for this inode value, if empty return
	 */
	indx = ((unsigned)arcn->sb.st_ino) % L_TAB_SZ;
	if ((pt = ltab[indx]) == NULL)
		return;

	/*
	 * walk down the list looking for the inode/dev pair, unlink and
	 * free if found
	 */
	ppt = &(ltab[indx]);
	while (pt != NULL) {
		if ((pt->ino == arcn->sb.st_ino) &&
		    (pt->dev == arcn->sb.st_dev))
			break;
		ppt = &(pt->fow);
		pt = pt->fow;
	}
	if (pt == NULL)
		return;

	/*
	 * remove and free it
	 */
	*ppt = pt->fow;
	(void)free((char *)pt->name);
	(void)free((char *)pt);
}

/*
 * lnk_end()
 *	pull apart a existing link table so we can reuse it. We do this between
 *	read and write phases of append with update. (The format may have
 *	used the link table, and we need to start with a fresh table for the
 *	write phase
 */

#if __STDC__
void
lnk_end(void)
#else
void
lnk_end()
#endif
{
	register int i;
	register HRDLNK *pt;
	register HRDLNK *ppt;

	if (ltab == NULL)
		return;

	for (i = 0; i < L_TAB_SZ; ++i) {
		if (ltab[i] == NULL)
			continue;
		pt = ltab[i];
		ltab[i] = NULL;

		/*
		 * free up each entry on this chain
		 */
		while (pt != NULL) {
			ppt = pt;
			pt = ppt->fow;
			(void)free((char *)ppt->name);
			(void)free((char *)ppt);
		}
	}
	return;
}

/*
 * modification time table routines
 *
 * The modification time table keeps track of last modification times for all
 * files stored in an archive during a write phase when -u is set. We only
 * add a file to the archive if it is newer than a file with the same name
 * already stored on the archive (if there is no other file with the same
 * name on the archive it is added). This applies to writes and appends.
 * An append with an -u must read the archive and store the modification time
 * for every file on that archive before starting the write phase. It is clear
 * that this is one HUGE database. To save memory space, the actual file names
 * are stored in a scatch file and indexed by an in memory hash table. The
 * hash table is indexed by hashing the file path. The nodes in the table store
 * the length of the filename and the lseek offset within the scratch file 
 * where the actual name is stored. Since there are never any deletions to this
 * table, fragmentation of the scratch file is never a issue. Lookups seem to
 * not exhibit any locality at all (files in the database are rarely 
 * looked up more than once...). So caching is just a waste of memory. The
 * only limitation is the amount of scatch file space available to store the
 * path names.
 */

/*
 * ftime_start()
 *	create the file time hash table and open for read/write the scratch
 *	file. (after created it is unlinked, so when we exit we leave
 *	no witnesses).
 * Return:
 *	0 if the table and file was created ok, -1 otherwise
 */

#if __STDC__
int
ftime_start(void)
#else
int
ftime_start()
#endif
{
	char *pt;

	if (ftab != NULL)
		return(0);
 	if ((ftab = (FTM **)calloc(F_TAB_SZ, sizeof(FTM *))) == NULL) {
                warn(1, "Cannot allocate memory for file time table");
                return(-1);
        }

	/*
	 * get random name and create temporary scratch file, unlink name
	 * so it will get removed on exit
	 */
	if ((pt = tempnam((char *)NULL, (char *)NULL)) == NULL)
		return(-1);
	(void)unlink(pt);

	if ((ffd = open(pt, O_RDWR | O_CREAT,  S_IRWXU)) < 0) {
		syswarn(1, errno, "Unable to open temporary file: %s", pt);
		return(-1);
	}

	(void)unlink(pt);
	return(0);
}

/*
 * chk_ftime()
 *	looks up entry in file time hash table. If not found, the file is
 *	added to the hash table and the file named stored in the scratch file.
 *	If a file with the same name is found, the file times are compared and
 *	the most recent file time is retained. If the new file was younger (or
 *	was not in the database) the new file is selected for storage.
 * Return:
 *	0 if file should be added to the archive, 1 if it should be skipped,
 *	-1 on error
 */

#if __STDC__
int
chk_ftime(register ARCHD *arcn)
#else
int
chk_ftime(arcn)
	register ARCHD *arcn;
#endif
{
	register FTM *pt;
	register int namelen;
	register u_int indx;
	char ckname[PAXPATHLEN+1];

	/*
	 * no info, go ahead and add to archive
	 */
	if (ftab == NULL)
		return(0);

	/*
	 * hash the pathname and look up in table
	 */
	namelen = arcn->nlen;
	indx = st_hash(arcn->name, namelen, F_TAB_SZ);
	if ((pt = ftab[indx]) != NULL) {
		/*
		 * the hash chain is not empty, walk down looking for match
		 * only read up the path names if the lengths match, speeds
		 * up the search a lot
		 */
		while (pt != NULL) {
			if (pt->namelen == namelen) {
				/*
				 * potential match, have to read the name
				 * from the scratch file.
				 */
				if (lseek(ffd,pt->seek,SEEK_SET) != pt->seek) {
					syswarn(1, errno,
					    "Failed ftime table seek");
					return(-1);
				}
				if (read(ffd, ckname, namelen) != namelen) {
					syswarn(1, errno,
					    "Failed ftime table read");
					return(-1);
				}

				/*
				 * if the names match, we are done
				 */
				if (!strncmp(ckname, arcn->name, namelen))
					break;
			}

			/*
			 * try the next entry on the chain
			 */
			pt = pt->fow;
		}

		if (pt != NULL) {
			/*
			 * found the file, compare the times, save the newer
			 */
			if (arcn->sb.st_mtime > pt->mtime) {
				/*
				 * file is newer
				 */
				pt->mtime = arcn->sb.st_mtime;
				return(0);
			} 
			/*
			 * file is older
			 */
			return(1);
		}
	}