tables.c

早期freebsd实现

	/*
	 * not in table, add it
	 */
	if ((pt = (FTM *)malloc(sizeof(FTM))) != NULL) {
		/*
		 * add the name at the end of the scratch file, saving the
		 * offset. add the file to the head of the hash chain
		 */
		if ((pt->seek = lseek(ffd, (off_t)0, SEEK_END)) >= 0) {
			if (write(ffd, arcn->name, namelen) == namelen) {
				pt->mtime = arcn->sb.st_mtime;
				pt->namelen = namelen;
				pt->fow = ftab[indx];
				ftab[indx] = pt;
				return(0);
			}
			syswarn(1, errno, "Failed write to file time table");
		} else 
			syswarn(1, errno, "Failed seek on file time table");
	} else
		warn(1, "File time table ran out of memory");

	if (pt != NULL)
		(void)free((char *)pt);
	return(-1);
}

/*
 * Interactive rename table routines
 *
 * The interactive rename table keeps track of the new names that the user
 * assignes to files from tty input. Since this map is unique for each file
 * we must store it in case there is a reference to the file later in archive
 * (a link). Otherwise we will be unable to find the file we know was
 * extracted. The remapping of these files is stored in a memory based hash
 * table (it is assumed since input must come from /dev/tty, it is unlikely to
 * be a very large table).
 */

/*
 * name_start()
 *	create the interactive rename table
 * Return:
 *	0 if successful, -1 otherwise
 */

#if __STDC__
int
name_start(void)
#else
int
name_start()
#endif
{
	if (ntab != NULL)
		return(0);
 	if ((ntab = (NAMT **)calloc(N_TAB_SZ, sizeof(NAMT *))) == NULL) {
                warn(1, "Cannot allocate memory for interactive rename table");
                return(-1);
        }
	return(0);
}

/*
 * add_name()
 *	add the new name to old name mapping just created by the user.
 *	If an old name mapping is found (there may be duplicate names on an
 *	archive) only the most recent is kept.
 * Return:
 *	0 if added, -1 otherwise
 */

#if __STDC__
int
add_name(register char *oname, int onamelen, char *nname)
#else
int
add_name(oname, onamelen, nname)
	register char *oname;
	int onamelen;
	char *nname;
#endif
{
	register NAMT *pt;
	register u_int indx;

	if (ntab == NULL) {
		/*
		 * should never happen
		 */
		warn(0, "No interactive rename table, links may fail\n");
		return(0); 
	}

	/*
	 * look to see if we have already mapped this file, if so we
	 * will update it
	 */
	indx = st_hash(oname, onamelen, N_TAB_SZ);
	if ((pt = ntab[indx]) != NULL) {
		/*
		 * look down the has chain for the file
		 */
		while ((pt != NULL) && (strcmp(oname, pt->oname) != 0))
			pt = pt->fow;

		if (pt != NULL) {
			/*
			 * found an old mapping, replace it with the new one
			 * the user just input (if it is different)
			 */
			if (strcmp(nname, pt->nname) == 0)
				return(0);

			(void)free((char *)pt->nname);
			if ((pt->nname = strdup(nname)) == NULL) {
				warn(1, "Cannot update rename table");
				return(-1);
			}
			return(0);
		}
	}

	/*
	 * this is a new mapping, add it to the table
	 */
	if ((pt = (NAMT *)malloc(sizeof(NAMT))) != NULL) {
		if ((pt->oname = strdup(oname)) != NULL) {
			if ((pt->nname = strdup(nname)) != NULL) {
				pt->fow = ntab[indx];
				ntab[indx] = pt;
				return(0);
			}
			(void)free((char *)pt->oname);
		}
		(void)free((char *)pt);
	}
	warn(1, "Interactive rename table out of memory");
	return(-1);
}

/*
 * sub_name()
 *	look up a link name to see if it points at a file that has been
 *	remapped by the user. If found, the link is adjusted to contain the
 *	new name (oname is the link to name)
 */

#if __STDC__
void
sub_name(register char *oname, int *onamelen)
#else
void
sub_name(oname, onamelen)
	register char *oname;
	int *onamelen;
#endif
{
	register NAMT *pt;
	register u_int indx;

	if (ntab == NULL)
		return;
	/*
	 * look the name up in the hash table
	 */
	indx = st_hash(oname, *onamelen, N_TAB_SZ);
	if ((pt = ntab[indx]) == NULL)
		return;

	while (pt != NULL) {
		/*
		 * walk down the hash cahin looking for a match
		 */
		if (strcmp(oname, pt->oname) == 0) {
			/*
			 * found it, replace it with the new name
			 * and return (we know that oname has enough space)
			 */
			*onamelen = l_strncpy(oname, pt->nname, PAXPATHLEN+1);
			return;
		}
		pt = pt->fow;
	}

	/*
	 * no match, just return
	 */
	return;
}
    
/*
 * device/inode mapping table routines
 * (used with formats that store device and inodes fields)
 *
 * device/inode mapping tables remap the device field in a archive header. The
 * device/inode fields are used to determine when files are hard links to each
 * other. However these values have very little meaning outside of that. This
 * database is used to solve one of two different problems.
 *
 * 1) when files are appended to an archive, while the new files may have hard
 * links to each other, you cannot determine if they have hard links to any
 * file already stored on the archive from a prior run of pax. We must assume
 * that these inode/device pairs are unique only within a SINGLE run of pax
 * (which adds a set of files to an archive). So we have to make sure the
 * inode/dev pairs we add each time are always unique. We do this by observing
 * while the inode field is very dense, the use of the dev field is fairly
 * sparse. Within each run of pax, we remap any device number of a new archive
 * member that has a device number used in a prior run and already stored in a
 * file on the archive. During the read phase of the append, we store the
 * device numbers used and mark them to not be used by any file during the
 * write phase. If during write we go to use one of those old device numbers,
 * we remap it to a new value.
 *
 * 2) Often the fields in the archive header used to store these values are
 * too small to store the entire value. The result is an inode or device value
 * which can be truncated. This really can foul up an archive. With truncation
 * we end up creating links between files that are really not links (after
 * truncation the inodes are the same value). We address that by detecting
 * truncation and forcing a remap of the device field to split truncated
 * inodes away from each other. Each truncation creates a pattern of bits that
 * are removed. We use this pattern of truncated bits to partition the inodes
 * on a single device to many different devices (each one represented by the
 * truncated bit pattern). All inodes on the same device that have the same
 * truncation pattern are mapped to the same new device. Two inodes that
 * truncate to the same value clearly will always have different truncation
 * bit patterns, so they will be split from away each other. When we spot
 * device truncation we remap the device number to a non truncated value.
 * (for more info see table.h for the data structures involved).
 */

/*
 * dev_start()
 *	create the device mapping table
 * Return:
 *	0 if successful, -1 otherwise
 */

#if __STDC__
int
dev_start(void)
#else
int
dev_start()
#endif
{
	if (dtab != NULL)
		return(0);
 	if ((dtab = (DEVT **)calloc(D_TAB_SZ, sizeof(DEVT *))) == NULL) {
                warn(1, "Cannot allocate memory for device mapping table");
                return(-1);
        }
	return(0);
}

/*
 * add_dev()
 *	add a device number to the table. this will force the device to be
 *	remapped to a new value if it be used during a write phase. This
 *	function is called during the read phase of an append to prohibit the
 *	use of any device number already in the archive.
 * Return:
 *	0 if added ok, -1 otherwise
 */

#if __STDC__
int
add_dev(register ARCHD *arcn)
#else
int
add_dev(arcn)
	register ARCHD *arcn;
#endif
{
	if (chk_dev(arcn->sb.st_dev, 1) == NULL)
		return(-1);
	return(0);
}

/*
 * chk_dev()
 *	check for a device value in the device table. If not found and the add
 *	flag is set, it is added. This does NOT assign any mapping values, just
 *	adds the device number as one that need to be remapped. If this device
 *	is alread mapped, just return with a pointer to that entry.
 * Return:
 *	pointer to the entry for this device in the device map table. Null
 *	if the add flag is not set and the device is not in the table (it is
 *	not been seen yet). If add is set and the device cannot be added, null
 *	is returned (indicates an error).
 */

#if __STDC__
static DEVT *
chk_dev(dev_t dev, int add)
#else
static DEVT *
chk_dev(dev, add)
	dev_t dev;
	int add;
#endif
{
	register DEVT *pt;
	register u_int indx;

	if (dtab == NULL)
		return(NULL);
	/*
	 * look to see if this device is already in the table
	 */
	indx = ((unsigned)dev) % D_TAB_SZ;
	if ((pt = dtab[indx]) != NULL) {
		while ((pt != NULL) && (pt->dev != dev))
			pt = pt->fow;

		/*
		 * found it, return a pointer to it
		 */
		if (pt != NULL)
			return(pt);
	}

	/*
	 * not in table, we add it only if told to as this may just be a check
	 * to see if a device number is being used.
	 */
	if (add == 0)
		return(NULL);

	/*
	 * allocate a node for this device and add it to the front of the hash
	 * chain. Note we do not assign remaps values here, so the pt->list
	 * list must be NULL.
	 */
	if ((pt = (DEVT *)malloc(sizeof(DEVT))) == NULL) {
		warn(1, "Device map table out of memory");
		return(NULL);
	}
	pt->dev = dev;
	pt->list = NULL;
	pt->fow = dtab[indx];
	dtab[indx] = pt;
	return(pt);
}
/*
 * map_dev()
 *	given an inode and device storage mask (the mask has a 1 for each bit
 *	the archive format is able to store in a header), we check for inode
 *	and device truncation and remap the device as required. Device mapping
 *	can also occur when during the read phase of append a device number was
 *	seen (and was marked as do not use during the write phase). WE ASSUME
 *	that unsigned longs are the same size or bigger than the fields used
 *	for ino_t and dev_t. If not the types will have to be changed.
 * Return:
 *	0 if all ok, -1 otherwise.
 */

#if __STDC__
int
map_dev(register ARCHD *arcn, u_long dev_mask, u_long ino_mask)
#else
int
map_dev(arcn, dev_mask, ino_mask)
	register ARCHD *arcn;
	u_long dev_mask;
	u_long ino_mask;
#endif
{
	register DEVT *pt;
	register DLIST *dpt;
	static dev_t lastdev = 0;	/* next device number to try */
	int trc_ino = 0;
	int trc_dev = 0;
	ino_t trunc_bits = 0;
	ino_t nino;

	if (dtab == NULL)
		return(0);
	/*
	 * check for device and inode truncation, and extract the truncated
	 * bit pattern. 
	 */
	if ((arcn->sb.st_dev & (dev_t)dev_mask) != arcn->sb.st_dev)
		++trc_dev;
	if ((nino = arcn->sb.st_ino & (ino_t)ino_mask) != arcn->sb.st_ino) {
		++trc_ino;
		trunc_bits = arcn->sb.st_ino & (ino_t)(~ino_mask);
	}

	/*
	 * see if this device is already being mapped, look up the device
	 * then find the truncation bit pattern which applies
	 */
	if ((pt = chk_dev(arcn->sb.st_dev, 0)) != NULL) {
		/*
		 * this device is already marked to be remapped
		 */
		for (dpt = pt->list; dpt != NULL; dpt = dpt->fow)
			if (dpt->trunc_bits == trunc_bits)
				break;

		if (dpt != NULL) {
			/*
			 * we are being remapped for this device and pattern
			 * change the device number to be stored and return
			 */
			arcn->sb.st_dev = dpt->dev;
			arcn->sb.st_ino = nino;
			return(0);
		}
	} else {
		/*
		 * this device is not being remapped YET. if we do not have any
		 * form of truncation, we do not need a remap
		 */
		if (!trc_ino && !trc_dev)
			return(0);

		/*
		 * we have truncation, have to add this as a device to remap
		 */
		if ((pt = chk_dev(arcn->sb.st_dev, 1)) == NULL)
			goto bad;

		/*
		 * if we just have a truncated inode, we have to make sure that
		 * all future inodes that do not truncate (they have the
		 * truncation pattern of all 0's) continue to map to the same
		 * device number. We probably have already written inodes with
		 * this device number to the archive with the truncation
		 * pattern of all 0's. So we add the mapping for all 0's to the
		 * same device number.
		 */
		if (!trc_dev && (trunc_bits != 0)) {
			if ((dpt = (DLIST *)malloc(sizeof(DLIST))) == NULL)
				goto bad;
			dpt->trunc_bits = 0;
			dpt->dev = arcn->sb.st_dev;
			dpt->fow = pt->list;
			pt->list = dpt;
		}
	}

	/*
	 * look for a device number not being used. We must watch for wrap
	 * around on lastdev (so we do not get stuck looking forever!)
	 */
	while (++lastdev > 0) {
		if (chk_dev(lastdev, 0) != NULL)
			continue;
		/*
		 * found an unused value. If we have reached truncation point
		 * for this format we are hosed, so we give up. Otherwise we
		 * mark it as being used.
		 */
		if (((lastdev & ((dev_t)dev_mask)) != lastdev) ||
		    (chk_dev(lastdev, 1) == NULL))
			goto bad;
		break;
	}

	if ((lastdev <= 0) || ((dpt = (DLIST *)malloc(sizeof(DLIST))) == NULL))
		goto bad;

	/*
	 * got a new device number, store it under this truncation pattern.
	 * change the device number this file is being stored with.
	 */
	dpt->trunc_bits = trunc_bits;
	dpt->dev = lastdev;
	dpt->fow = pt->list;
	pt->list = dpt;
	arcn->sb.st_dev = lastdev;
	arcn->sb.st_ino = nino;
	return(0);