/*	$OpenBSD: tables.c,v 1.47 2015/03/19 05:14:24 guenther Exp $	*/

/*	$NetBSD: tables.c,v 1.4 1995/03/21 09:07:45 cgd Exp $	*/

/*-

 * 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. 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.

 */

#include <sys/types.h>

#include <sys/time.h>

#include <sys/stat.h>

#include <fcntl.h>

#include <limits.h>

#include <signal.h>

#include <stdio.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 database 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 DIRDATA *dirp = NULL;	/* storage for setting created dir time/mode */

static size_t dirsize;		/* size of dirp table */

static size_t dircnt = 0;	/* entries in dir time/mode storage */

static int ffd = -1;		/* tmp file for file time table name storage */

/*

 * 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

 */

int

lnk_start(void)

	}

}

/*

 * 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

 */

int

chk_lnk(ARCHD *arcn)

	HRDLNK *pt;

	HRDLNK **ppt;

	u_int indx;

	/*

	 * ignore those nodes that cannot have hard links

	 */

	/*

	 * hash inode number and look for this file

	 */

		/*

		 * its hash chain in not empty, walk down looking for it

		 */

			    (pt->dev == arcn->sb.st_dev))

		}

			/*

			 * 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.

			 */

				sizeof(arcn->ln_name));

			/* XXX truncate? */

			else

			/*

			 * if we have found all the links to this file, remove

			 * it from the database

			 */

			}

		}

	}

	/*

	 * we never saw this file before. It has links so we add it to the

	 * front of this hash chain

	 */

		}

	}

}

/*

 * 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.

 */

void

purg_lnk(ARCHD *arcn)

{

	HRDLNK *pt;

	HRDLNK **ppt;

	u_int indx;

	/*

	 * do not bother to look if it could not be in the database

	 */

	    PAX_IS_HARDLINK(arcn->type))

		return;

	/*

	 * find the hash chain for this inode value, if empty return

	 */

	/*

	 * walk down the list looking for the inode/dev pair, unlink and

	 * free if found

	 */

		    (pt->dev == arcn->sb.st_dev))

	}

	/*

	 * remove and free it

	 */

}

/*

 * 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

 */

void

lnk_end(void)

	int i;

	HRDLNK *pt;

	HRDLNK *ppt;

		/*

		 * free up each entry on this chain

		 */

		}

	}

}

/*

 * 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 scratch 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 from

 * 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 scratch 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

 */

int

ftime_start(void)

{

	}

	/*

	 * get random name and create temporary scratch file, unlink name

	 * so it will get removed on exit

	 */

		    tempfile);

	}

}

/*

 * 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

 */

int

chk_ftime(ARCHD *arcn)

{

	FTM *pt;

	int namelen;

	u_int indx;

	char ckname[PAXPATHLEN+1];

	/*

	 * no info, go ahead and add to archive

	 */

	/*

	 * hash the pathname and look up in table

	 */

		/*

		 * 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

		 */

				/*

				 * potential match, have to read the name

				 * from the scratch file.

				 */

					    "Failed ftime table seek");

				}

					    "Failed ftime table read");

				}

				/*

				 * if the names match, we are done

				 */

			}

			/*

			 * try the next entry on the chain

			 */

		}

			/*

			 * found the file, compare the times, save the newer

			 */

				/*

				 * file is newer

				 */

			}

			/*

			 * file is older

			 */

		}

	}

	/*

	 * not in table, add it

	 */

		/*

		 * add the name at the end of the scratch file, saving the

		 * offset. add the file to the head of the hash chain

		 */

			}

		} else

	} else

}

/*

 * escaping (absolute or w/"..") symlink table routines

 *

 * By default, an archive shouldn't be able extract to outside of the

 * current directory.  What should we do if the archive contains a symlink

 * whose value is either absolute or contains ".." components?  What we'll

 * do is initially create the path as an empty file (to block attempts to

 * reference _through_ it) and instead record its path and desired

 * final value and mode.  Then once all the other archive

 * members are created (but before the pass to set timestamps on

 * directories) we'll process those records, replacing the placeholder with

 * the correct symlink and setting them to the correct mode, owner, group,

 * and timestamps.

 *

 * Note: we also need to handle hardlinks to symlinks (barf) as well as

 * hardlinks whose target is replaced by a later entry in the archive (barf^2).

 *

 * So we track things by dev+ino of the placeholder file, associating with

 * that the value and mode of the final symlink and a list of paths that

 * should all be hardlinks of that.  We'll 'store' the symlink's desired

 * timestamps, owner, and group by setting them on the placeholder file.

 *

 * The operations are:

 * a) create an escaping symlink: create the placeholder file and add an entry

 *    for the new link

 * b) create a hardlink: do the link.  If the target turns out to be a

 *    zero-length file whose dev+ino are in the symlink table, then add this

 *    path to the list of names for that link

 * c) perform deferred processing: for each entry, check each associated path:

 *    if it's a zero-length file with the correct dev+ino then recreate it as

 *    the specified symlink or hardlink to the first such

 */

struct slpath {

	char	*sp_path;

	struct	slpath *sp_next;

};

struct slinode {

	ino_t	sli_ino;

	char	*sli_value;

	struct	slpath sli_paths;

	struct	slinode *sli_fow;		/* hash table chain */

	dev_t	sli_dev;

	mode_t	sli_mode;

};

static struct slinode **slitab = NULL;

/*

 * sltab_start()

 *	create the hash table

 * Return:

 *	0 if the table and file was created ok, -1 otherwise

 */

int

sltab_start(void)

	}

}

/*

 * sltab_add_sym()

 *	Create the placeholder and tracking info for an escaping symlink.

 * Return:

 *	0 on success, -1 otherwise

 */

int

sltab_add_sym(const char *path0, const char *value0, mode_t mode)

{

	struct stat sb;

	struct slinode *s;

	struct slpath *p;

	char *path, *value;

	u_int indx;

	int fd;

	/* create the placeholder */

	}

		}

	}

	}

	/* now check the hash table for conflicting entry */

			continue;

		/*

		 * One of our placeholders got removed behind our back and

		 * we've reused the inode.  Weird, but clean up the mess.

		 */

		}

		goto set_value;

	}

	/* Normal case: create a new node */

	}

}

/*

 * sltab_add_link()

 *	A hardlink was created; if it looks like a placeholder, handle the

 *	tracking.

 * Return:

 *	0 if things are ok, -1 if something went wrong

 */

int

sltab_add_link(const char *path, const struct stat *sb)

	struct slinode *s;

	struct slpath *p;

	u_int indx;

	/* find the hash table entry for this hardlink */

			continue;

		}

				    path);

			}

		}

		/* link it in */

	}

	/* not found */

}

static int

sltab_process_one(struct slinode *s, struct slpath *p, const char *first,

    int in_sig)

{

	struct stat sb;

	mode_t mode;

	int err;

	/*

	 * is it the expected placeholder?  This can fail legimately

	 * if the archive overwrote the link with another, later entry,

	 * so don't warn.

	 */

	    sb.st_ino != s->sli_ino || sb.st_dev != s->sli_dev)

	}

		/* add another hardlink to the existing symlink */

		/*

		 * Couldn't hardlink the symlink for some reason, so we'll

		 * try creating it as its own symlink, but save the error

		 * for reporting if that fails.

		 */

	}

			else

			    qualifier, path);

		}

	}

	/* success, so set the id, mode, and times */

		/* if can't set the ids, force the set[ug]id bits off */

	}

	/*

	 * If we tried to link to first but failed, then this new symlink

	 * might be a better one to try in the future.  Guess from the errno.

	 */

}

/*

 * sltab_process()

 *	Do all the delayed process for escape symlinks

 */

void

sltab_process(int in_sig)

	struct slinode *s;

	struct slpath *p;

	char *first;

	u_int indx;

	/* walk across the entire hash table */

			/* pop this entry */

			while (1) {

				struct slpath *next_p;

			}

			}

		}

	}

}

/*

 * Interactive rename table routines

 *

 * The interactive rename table keeps track of the new names that the user

 * assigns 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

 */

int

name_start(void)

{

	}

}

/*

 * 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

 */

int

add_name(char *oname, int onamelen, char *nname)

{

	NAMT *pt;

	u_int indx;

		/*

		 * should never happen

		 */

	}

	/*

	 * look to see if we have already mapped this file, if so we

	 * will update it

	 */

		/*

		 * look down the has chain for the file

		 */

			/*

			 * found an old mapping, replace it with the new one

			 * the user just input (if it is different)

			 */

			}

		}

	}

	/*

	 * this is a new mapping, add it to the table

	 */

			}

		}

	}

}

/*

 * 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)

 */

void

sub_name(char *oname, int *onamelen, size_t onamesize)

{

	NAMT *pt;

	u_int indx;

	/*

	 * look the name up in the hash table

	 */

		/*

		 * walk down the hash chain looking for a match

		 */

			/*

			 * found it, replace it with the new name

			 * and return (we know that oname has enough space)

			 */

			return;

		}

	}

	/*

	 * no match, just return

	 */

}

#ifndef NOCPIO

/*

 * 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).

 */

static DEVT *chk_dev(dev_t, int);