xref: /original-bsd/bin/pax/tables.c (revision 3631e65b)
1 /*-
2  * Copyright (c) 1992 Keith Muller.
3  * Copyright (c) 1992, 1993
4  *	The Regents of the University of California.  All rights reserved.
5  *
6  * This code is derived from software contributed to Berkeley by
7  * Keith Muller of the University of California, San Diego.
8  *
9  * %sccs.include.redist.c%
10  */
11 
12 #ifndef lint
13 static char sccsid[] = "@(#)tables.c	8.1 (Berkeley) 05/31/93";
14 #endif /* not lint */
15 
16 #include <sys/types.h>
17 #include <sys/time.h>
18 #include <sys/stat.h>
19 #include <sys/param.h>
20 #include <sys/fcntl.h>
21 #include <stdio.h>
22 #include <ctype.h>
23 #include <string.h>
24 #include <unistd.h>
25 #include <errno.h>
26 #include <stdlib.h>
27 #include "pax.h"
28 #include "tables.h"
29 #include "extern.h"
30 
31 /*
32  * Routines for controlling the contents of all the different databases pax
33  * keeps. Tables are dynamically created only when they are needed. The
34  * goal was speed and the ability to work with HUGE archives. The databases
35  * were kept simple, but do have complex rules for when the contents change.
36  * As of this writing, the posix library functions were more complex than
37  * needed for this application (pax databases have very short lifetimes and
38  * do not survive after pax is finished). Pax is required to handle very
39  * large archives. These database routines carefully combine memory usage and
40  * temporary file storage in ways which will not significantly impact runtime
41  * performance while allowing the largest possible archives to be handled.
42  * Trying to force the fit to the posix databases routines was not considered
43  * time well spent.
44  */
45 
46 static HRDLNK **ltab = NULL;	/* hard link table for detecting hard links */
47 static FTM **ftab = NULL;	/* file time table for updating arch */
48 static NAMT **ntab = NULL;	/* interactive rename storage table */
49 static DEVT **dtab = NULL;	/* device/inode mapping tables */
50 static ATDIR **atab = NULL;	/* file tree directory time reset table */
51 static int dirfd = -1;		/* storage for setting created dir time/mode */
52 static u_long dircnt;		/* entries in dir time/mode storage */
53 static int ffd = -1;		/* tmp file for file time table name storage */
54 
55 static DEVT *chk_dev __P((dev_t, int));
56 
57 /*
58  * hard link table routines
59  *
60  * The hard link table tries to detect hard links to files using the device and
61  * inode values. We do this when writing an archive, so we can tell the format
62  * write routine that this file is a hard link to another file. The format
63  * write routine then can store this file in whatever way it wants (as a hard
64  * link if the format supports that like tar, or ignore this info like cpio).
65  * (Actually a field in the format driver table tells us if the format wants
66  * hard link info. if not, we do not waste time looking for them). We also use
67  * the same table when reading an archive. In that situation, this table is
68  * used by the format read routine to detect hard links from stored dev and
69  * inode numbers (like cpio). This will allow pax to create a link when one
70  * can be detected by the archive format.
71  */
72 
73 /*
74  * lnk_start
75  *	Creates the hard link table.
76  * Return:
77  *	0 if created, -1 if failure
78  */
79 
80 #if __STDC__
81 int
lnk_start(void)82 lnk_start(void)
83 #else
84 int
85 lnk_start()
86 #endif
87 {
88 	if (ltab != NULL)
89 		return(0);
90  	if ((ltab = (HRDLNK **)calloc(L_TAB_SZ, sizeof(HRDLNK *))) == NULL) {
91                 warn(1, "Cannot allocate memory for hard link table");
92                 return(-1);
93         }
94 	return(0);
95 }
96 
97 /*
98  * chk_lnk()
99  *	Looks up entry in hard link hash table. If found, it copies the name
100  *	of the file it is linked to (we already saw that file) into ln_name.
101  *	lnkcnt is decremented and if goes to 1 the node is deleted from the
102  *	database. (We have seen all the links to this file). If not found,
103  *	we add the file to the database if it has the potential for having
104  *	hard links to other files we may process (it has a link count > 1)
105  * Return:
106  *	if found returns 1; if not found returns 0; -1 on error
107  */
108 
109 #if __STDC__
110 int
chk_lnk(register ARCHD * arcn)111 chk_lnk(register ARCHD *arcn)
112 #else
113 int
114 chk_lnk(arcn)
115 	register ARCHD *arcn;
116 #endif
117 {
118 	register HRDLNK *pt;
119 	register HRDLNK **ppt;
120 	register u_int indx;
121 
122 	if (ltab == NULL)
123 		return(-1);
124 	/*
125 	 * ignore those nodes that cannot have hard links
126 	 */
127 	if ((arcn->type == PAX_DIR) || (arcn->sb.st_nlink <= 1))
128 		return(0);
129 
130 	/*
131 	 * hash inode number and look for this file
132 	 */
133 	indx = ((unsigned)arcn->sb.st_ino) % L_TAB_SZ;
134 	if ((pt = ltab[indx]) != NULL) {
135 		/*
136 		 * it's hash chain in not empty, walk down looking for it
137 		 */
138 		ppt = &(ltab[indx]);
139 		while (pt != NULL) {
140 			if ((pt->ino == arcn->sb.st_ino) &&
141 			    (pt->dev == arcn->sb.st_dev))
142 				break;
143 			ppt = &(pt->fow);
144 			pt = pt->fow;
145 		}
146 
147 		if (pt != NULL) {
148 			/*
149 			 * found a link. set the node type and copy in the
150 			 * name of the file it is to link to. we need to
151 			 * handle hardlinks to regular files differently than
152 			 * other links.
153 			 */
154 			arcn->ln_nlen = l_strncpy(arcn->ln_name, pt->name,
155 				PAXPATHLEN+1);
156 			if (arcn->type == PAX_REG)
157 				arcn->type = PAX_HRG;
158 			else
159 				arcn->type = PAX_HLK;
160 
161 			/*
162 			 * if we have found all the links to this file, remove
163 			 * it from the database
164 			 */
165 			if (--pt->nlink <= 1) {
166 				*ppt = pt->fow;
167 				(void)free((char *)pt->name);
168 				(void)free((char *)pt);
169 			}
170 			return(1);
171 		}
172 	}
173 
174 	/*
175 	 * we never saw this file before. It has links so we add it to the
176 	 * front of this hash chain
177 	 */
178 	if ((pt = (HRDLNK *)malloc(sizeof(HRDLNK))) != NULL) {
179 		if ((pt->name = strdup(arcn->name)) != NULL) {
180 			pt->dev = arcn->sb.st_dev;
181 			pt->ino = arcn->sb.st_ino;
182 			pt->nlink = arcn->sb.st_nlink;
183 			pt->fow = ltab[indx];
184 			ltab[indx] = pt;
185 			return(0);
186 		}
187 		(void)free((char *)pt);
188 	}
189 
190 	warn(1, "Hard link table out of memory");
191 	return(-1);
192 }
193 
194 /*
195  * purg_lnk
196  *	remove reference for a file that we may have added to the data base as
197  *	a potential source for hard links. We ended up not using the file, so
198  *	we do not want to accidently point another file at it later on.
199  */
200 
201 #if __STDC__
202 void
purg_lnk(register ARCHD * arcn)203 purg_lnk(register ARCHD *arcn)
204 #else
205 void
206 purg_lnk(arcn)
207 	register ARCHD *arcn;
208 #endif
209 {
210 	register HRDLNK *pt;
211 	register HRDLNK **ppt;
212 	register u_int indx;
213 
214 	if (ltab == NULL)
215 		return;
216 	/*
217 	 * do not bother to look if it could not be in the database
218 	 */
219 	if ((arcn->sb.st_nlink <= 1) || (arcn->type == PAX_DIR) ||
220 	    (arcn->type == PAX_HLK) || (arcn->type == PAX_HRG))
221 		return;
222 
223 	/*
224 	 * find the hash chain for this inode value, if empty return
225 	 */
226 	indx = ((unsigned)arcn->sb.st_ino) % L_TAB_SZ;
227 	if ((pt = ltab[indx]) == NULL)
228 		return;
229 
230 	/*
231 	 * walk down the list looking for the inode/dev pair, unlink and
232 	 * free if found
233 	 */
234 	ppt = &(ltab[indx]);
235 	while (pt != NULL) {
236 		if ((pt->ino == arcn->sb.st_ino) &&
237 		    (pt->dev == arcn->sb.st_dev))
238 			break;
239 		ppt = &(pt->fow);
240 		pt = pt->fow;
241 	}
242 	if (pt == NULL)
243 		return;
244 
245 	/*
246 	 * remove and free it
247 	 */
248 	*ppt = pt->fow;
249 	(void)free((char *)pt->name);
250 	(void)free((char *)pt);
251 }
252 
253 /*
254  * lnk_end()
255  *	pull apart a existing link table so we can reuse it. We do this between
256  *	read and write phases of append with update. (The format may have
257  *	used the link table, and we need to start with a fresh table for the
258  *	write phase
259  */
260 
261 #if __STDC__
262 void
lnk_end(void)263 lnk_end(void)
264 #else
265 void
266 lnk_end()
267 #endif
268 {
269 	register int i;
270 	register HRDLNK *pt;
271 	register HRDLNK *ppt;
272 
273 	if (ltab == NULL)
274 		return;
275 
276 	for (i = 0; i < L_TAB_SZ; ++i) {
277 		if (ltab[i] == NULL)
278 			continue;
279 		pt = ltab[i];
280 		ltab[i] = NULL;
281 
282 		/*
283 		 * free up each entry on this chain
284 		 */
285 		while (pt != NULL) {
286 			ppt = pt;
287 			pt = ppt->fow;
288 			(void)free((char *)ppt->name);
289 			(void)free((char *)ppt);
290 		}
291 	}
292 	return;
293 }
294 
295 /*
296  * modification time table routines
297  *
298  * The modification time table keeps track of last modification times for all
299  * files stored in an archive during a write phase when -u is set. We only
300  * add a file to the archive if it is newer than a file with the same name
301  * already stored on the archive (if there is no other file with the same
302  * name on the archive it is added). This applies to writes and appends.
303  * An append with an -u must read the archive and store the modification time
304  * for every file on that archive before starting the write phase. It is clear
305  * that this is one HUGE database. To save memory space, the actual file names
306  * are stored in a scatch file and indexed by an in memory hash table. The
307  * hash table is indexed by hashing the file path. The nodes in the table store
308  * the length of the filename and the lseek offset within the scratch file
309  * where the actual name is stored. Since there are never any deletions to this
310  * table, fragmentation of the scratch file is never a issue. Lookups seem to
311  * not exhibit any locality at all (files in the database are rarely
312  * looked up more than once...). So caching is just a waste of memory. The
313  * only limitation is the amount of scatch file space available to store the
314  * path names.
315  */
316 
317 /*
318  * ftime_start()
319  *	create the file time hash table and open for read/write the scratch
320  *	file. (after created it is unlinked, so when we exit we leave
321  *	no witnesses).
322  * Return:
323  *	0 if the table and file was created ok, -1 otherwise
324  */
325 
326 #if __STDC__
327 int
ftime_start(void)328 ftime_start(void)
329 #else
330 int
331 ftime_start()
332 #endif
333 {
334 	char *pt;
335 
336 	if (ftab != NULL)
337 		return(0);
338  	if ((ftab = (FTM **)calloc(F_TAB_SZ, sizeof(FTM *))) == NULL) {
339                 warn(1, "Cannot allocate memory for file time table");
340                 return(-1);
341         }
342 
343 	/*
344 	 * get random name and create temporary scratch file, unlink name
345 	 * so it will get removed on exit
346 	 */
347 	if ((pt = tempnam((char *)NULL, (char *)NULL)) == NULL)
348 		return(-1);
349 	(void)unlink(pt);
350 
351 	if ((ffd = open(pt, O_RDWR | O_CREAT,  S_IRWXU)) < 0) {
352 		syswarn(1, errno, "Unable to open temporary file: %s", pt);
353 		return(-1);
354 	}
355 
356 	(void)unlink(pt);
357 	return(0);
358 }
359 
360 /*
361  * chk_ftime()
362  *	looks up entry in file time hash table. If not found, the file is
363  *	added to the hash table and the file named stored in the scratch file.
364  *	If a file with the same name is found, the file times are compared and
365  *	the most recent file time is retained. If the new file was younger (or
366  *	was not in the database) the new file is selected for storage.
367  * Return:
368  *	0 if file should be added to the archive, 1 if it should be skipped,
369  *	-1 on error
370  */
371 
372 #if __STDC__
373 int
chk_ftime(register ARCHD * arcn)374 chk_ftime(register ARCHD *arcn)
375 #else
376 int
377 chk_ftime(arcn)
378 	register ARCHD *arcn;
379 #endif
380 {
381 	register FTM *pt;
382 	register int namelen;
383 	register u_int indx;
384 	char ckname[PAXPATHLEN+1];
385 
386 	/*
387 	 * no info, go ahead and add to archive
388 	 */
389 	if (ftab == NULL)
390 		return(0);
391 
392 	/*
393 	 * hash the pathname and look up in table
394 	 */
395 	namelen = arcn->nlen;
396 	indx = st_hash(arcn->name, namelen, F_TAB_SZ);
397 	if ((pt = ftab[indx]) != NULL) {
398 		/*
399 		 * the hash chain is not empty, walk down looking for match
400 		 * only read up the path names if the lengths match, speeds
401 		 * up the search a lot
402 		 */
403 		while (pt != NULL) {
404 			if (pt->namelen == namelen) {
405 				/*
406 				 * potential match, have to read the name
407 				 * from the scratch file.
408 				 */
409 				if (lseek(ffd,pt->seek,SEEK_SET) != pt->seek) {
410 					syswarn(1, errno,
411 					    "Failed ftime table seek");
412 					return(-1);
413 				}
414 				if (read(ffd, ckname, namelen) != namelen) {
415 					syswarn(1, errno,
416 					    "Failed ftime table read");
417 					return(-1);
418 				}
419 
420 				/*
421 				 * if the names match, we are done
422 				 */
423 				if (!strncmp(ckname, arcn->name, namelen))
424 					break;
425 			}
426 
427 			/*
428 			 * try the next entry on the chain
429 			 */
430 			pt = pt->fow;
431 		}
432 
433 		if (pt != NULL) {
434 			/*
435 			 * found the file, compare the times, save the newer
436 			 */
437 			if (arcn->sb.st_mtime > pt->mtime) {
438 				/*
439 				 * file is newer
440 				 */
441 				pt->mtime = arcn->sb.st_mtime;
442 				return(0);
443 			}
444 			/*
445 			 * file is older
446 			 */
447 			return(1);
448 		}
449 	}
450 
451 	/*
452 	 * not in table, add it
453 	 */
454 	if ((pt = (FTM *)malloc(sizeof(FTM))) != NULL) {
455 		/*
456 		 * add the name at the end of the scratch file, saving the
457 		 * offset. add the file to the head of the hash chain
458 		 */
459 		if ((pt->seek = lseek(ffd, (off_t)0, SEEK_END)) >= 0) {
460 			if (write(ffd, arcn->name, namelen) == namelen) {
461 				pt->mtime = arcn->sb.st_mtime;
462 				pt->namelen = namelen;
463 				pt->fow = ftab[indx];
464 				ftab[indx] = pt;
465 				return(0);
466 			}
467 			syswarn(1, errno, "Failed write to file time table");
468 		} else
469 			syswarn(1, errno, "Failed seek on file time table");
470 	} else
471 		warn(1, "File time table ran out of memory");
472 
473 	if (pt != NULL)
474 		(void)free((char *)pt);
475 	return(-1);
476 }
477 
478 /*
479  * Interactive rename table routines
480  *
481  * The interactive rename table keeps track of the new names that the user
482  * assignes to files from tty input. Since this map is unique for each file
483  * we must store it in case there is a reference to the file later in archive
484  * (a link). Otherwise we will be unable to find the file we know was
485  * extracted. The remapping of these files is stored in a memory based hash
486  * table (it is assumed since input must come from /dev/tty, it is unlikely to
487  * be a very large table).
488  */
489 
490 /*
491  * name_start()
492  *	create the interactive rename table
493  * Return:
494  *	0 if successful, -1 otherwise
495  */
496 
497 #if __STDC__
498 int
name_start(void)499 name_start(void)
500 #else
501 int
502 name_start()
503 #endif
504 {
505 	if (ntab != NULL)
506 		return(0);
507  	if ((ntab = (NAMT **)calloc(N_TAB_SZ, sizeof(NAMT *))) == NULL) {
508                 warn(1, "Cannot allocate memory for interactive rename table");
509                 return(-1);
510         }
511 	return(0);
512 }
513 
514 /*
515  * add_name()
516  *	add the new name to old name mapping just created by the user.
517  *	If an old name mapping is found (there may be duplicate names on an
518  *	archive) only the most recent is kept.
519  * Return:
520  *	0 if added, -1 otherwise
521  */
522 
523 #if __STDC__
524 int
add_name(register char * oname,int onamelen,char * nname)525 add_name(register char *oname, int onamelen, char *nname)
526 #else
527 int
528 add_name(oname, onamelen, nname)
529 	register char *oname;
530 	int onamelen;
531 	char *nname;
532 #endif
533 {
534 	register NAMT *pt;
535 	register u_int indx;
536 
537 	if (ntab == NULL) {
538 		/*
539 		 * should never happen
540 		 */
541 		warn(0, "No interactive rename table, links may fail\n");
542 		return(0);
543 	}
544 
545 	/*
546 	 * look to see if we have already mapped this file, if so we
547 	 * will update it
548 	 */
549 	indx = st_hash(oname, onamelen, N_TAB_SZ);
550 	if ((pt = ntab[indx]) != NULL) {
551 		/*
552 		 * look down the has chain for the file
553 		 */
554 		while ((pt != NULL) && (strcmp(oname, pt->oname) != 0))
555 			pt = pt->fow;
556 
557 		if (pt != NULL) {
558 			/*
559 			 * found an old mapping, replace it with the new one
560 			 * the user just input (if it is different)
561 			 */
562 			if (strcmp(nname, pt->nname) == 0)
563 				return(0);
564 
565 			(void)free((char *)pt->nname);
566 			if ((pt->nname = strdup(nname)) == NULL) {
567 				warn(1, "Cannot update rename table");
568 				return(-1);
569 			}
570 			return(0);
571 		}
572 	}
573 
574 	/*
575 	 * this is a new mapping, add it to the table
576 	 */
577 	if ((pt = (NAMT *)malloc(sizeof(NAMT))) != NULL) {
578 		if ((pt->oname = strdup(oname)) != NULL) {
579 			if ((pt->nname = strdup(nname)) != NULL) {
580 				pt->fow = ntab[indx];
581 				ntab[indx] = pt;
582 				return(0);
583 			}
584 			(void)free((char *)pt->oname);
585 		}
586 		(void)free((char *)pt);
587 	}
588 	warn(1, "Interactive rename table out of memory");
589 	return(-1);
590 }
591 
592 /*
593  * sub_name()
594  *	look up a link name to see if it points at a file that has been
595  *	remapped by the user. If found, the link is adjusted to contain the
596  *	new name (oname is the link to name)
597  */
598 
599 #if __STDC__
600 void
sub_name(register char * oname,int * onamelen)601 sub_name(register char *oname, int *onamelen)
602 #else
603 void
604 sub_name(oname, onamelen)
605 	register char *oname;
606 	int *onamelen;
607 #endif
608 {
609 	register NAMT *pt;
610 	register u_int indx;
611 
612 	if (ntab == NULL)
613 		return;
614 	/*
615 	 * look the name up in the hash table
616 	 */
617 	indx = st_hash(oname, *onamelen, N_TAB_SZ);
618 	if ((pt = ntab[indx]) == NULL)
619 		return;
620 
621 	while (pt != NULL) {
622 		/*
623 		 * walk down the hash cahin looking for a match
624 		 */
625 		if (strcmp(oname, pt->oname) == 0) {
626 			/*
627 			 * found it, replace it with the new name
628 			 * and return (we know that oname has enough space)
629 			 */
630 			*onamelen = l_strncpy(oname, pt->nname, PAXPATHLEN+1);
631 			return;
632 		}
633 		pt = pt->fow;
634 	}
635 
636 	/*
637 	 * no match, just return
638 	 */
639 	return;
640 }
641 
642 /*
643  * device/inode mapping table routines
644  * (used with formats that store device and inodes fields)
645  *
646  * device/inode mapping tables remap the device field in a archive header. The
647  * device/inode fields are used to determine when files are hard links to each
648  * other. However these values have very little meaning outside of that. This
649  * database is used to solve one of two different problems.
650  *
651  * 1) when files are appended to an archive, while the new files may have hard
652  * links to each other, you cannot determine if they have hard links to any
653  * file already stored on the archive from a prior run of pax. We must assume
654  * that these inode/device pairs are unique only within a SINGLE run of pax
655  * (which adds a set of files to an archive). So we have to make sure the
656  * inode/dev pairs we add each time are always unique. We do this by observing
657  * while the inode field is very dense, the use of the dev field is fairly
658  * sparse. Within each run of pax, we remap any device number of a new archive
659  * member that has a device number used in a prior run and already stored in a
660  * file on the archive. During the read phase of the append, we store the
661  * device numbers used and mark them to not be used by any file during the
662  * write phase. If during write we go to use one of those old device numbers,
663  * we remap it to a new value.
664  *
665  * 2) Often the fields in the archive header used to store these values are
666  * too small to store the entire value. The result is an inode or device value
667  * which can be truncated. This really can foul up an archive. With truncation
668  * we end up creating links between files that are really not links (after
669  * truncation the inodes are the same value). We address that by detecting
670  * truncation and forcing a remap of the device field to split truncated
671  * inodes away from each other. Each truncation creates a pattern of bits that
672  * are removed. We use this pattern of truncated bits to partition the inodes
673  * on a single device to many different devices (each one represented by the
674  * truncated bit pattern). All inodes on the same device that have the same
675  * truncation pattern are mapped to the same new device. Two inodes that
676  * truncate to the same value clearly will always have different truncation
677  * bit patterns, so they will be split from away each other. When we spot
678  * device truncation we remap the device number to a non truncated value.
679  * (for more info see table.h for the data structures involved).
680  */
681 
682 /*
683  * dev_start()
684  *	create the device mapping table
685  * Return:
686  *	0 if successful, -1 otherwise
687  */
688 
689 #if __STDC__
690 int
dev_start(void)691 dev_start(void)
692 #else
693 int
694 dev_start()
695 #endif
696 {
697 	if (dtab != NULL)
698 		return(0);
699  	if ((dtab = (DEVT **)calloc(D_TAB_SZ, sizeof(DEVT *))) == NULL) {
700                 warn(1, "Cannot allocate memory for device mapping table");
701                 return(-1);
702         }
703 	return(0);
704 }
705 
706 /*
707  * add_dev()
708  *	add a device number to the table. this will force the device to be
709  *	remapped to a new value if it be used during a write phase. This
710  *	function is called during the read phase of an append to prohibit the
711  *	use of any device number already in the archive.
712  * Return:
713  *	0 if added ok, -1 otherwise
714  */
715 
716 #if __STDC__
717 int
add_dev(register ARCHD * arcn)718 add_dev(register ARCHD *arcn)
719 #else
720 int
721 add_dev(arcn)
722 	register ARCHD *arcn;
723 #endif
724 {
725 	if (chk_dev(arcn->sb.st_dev, 1) == NULL)
726 		return(-1);
727 	return(0);
728 }
729 
730 /*
731  * chk_dev()
732  *	check for a device value in the device table. If not found and the add
733  *	flag is set, it is added. This does NOT assign any mapping values, just
734  *	adds the device number as one that need to be remapped. If this device
735  *	is alread mapped, just return with a pointer to that entry.
736  * Return:
737  *	pointer to the entry for this device in the device map table. Null
738  *	if the add flag is not set and the device is not in the table (it is
739  *	not been seen yet). If add is set and the device cannot be added, null
740  *	is returned (indicates an error).
741  */
742 
743 #if __STDC__
744 static DEVT *
chk_dev(dev_t dev,int add)745 chk_dev(dev_t dev, int add)
746 #else
747 static DEVT *
748 chk_dev(dev, add)
749 	dev_t dev;
750 	int add;
751 #endif
752 {
753 	register DEVT *pt;
754 	register u_int indx;
755 
756 	if (dtab == NULL)
757 		return(NULL);
758 	/*
759 	 * look to see if this device is already in the table
760 	 */
761 	indx = ((unsigned)dev) % D_TAB_SZ;
762 	if ((pt = dtab[indx]) != NULL) {
763 		while ((pt != NULL) && (pt->dev != dev))
764 			pt = pt->fow;
765 
766 		/*
767 		 * found it, return a pointer to it
768 		 */
769 		if (pt != NULL)
770 			return(pt);
771 	}
772 
773 	/*
774 	 * not in table, we add it only if told to as this may just be a check
775 	 * to see if a device number is being used.
776 	 */
777 	if (add == 0)
778 		return(NULL);
779 
780 	/*
781 	 * allocate a node for this device and add it to the front of the hash
782 	 * chain. Note we do not assign remaps values here, so the pt->list
783 	 * list must be NULL.
784 	 */
785 	if ((pt = (DEVT *)malloc(sizeof(DEVT))) == NULL) {
786 		warn(1, "Device map table out of memory");
787 		return(NULL);
788 	}
789 	pt->dev = dev;
790 	pt->list = NULL;
791 	pt->fow = dtab[indx];
792 	dtab[indx] = pt;
793 	return(pt);
794 }
795 /*
796  * map_dev()
797  *	given an inode and device storage mask (the mask has a 1 for each bit
798  *	the archive format is able to store in a header), we check for inode
799  *	and device truncation and remap the device as required. Device mapping
800  *	can also occur when during the read phase of append a device number was
801  *	seen (and was marked as do not use during the write phase). WE ASSUME
802  *	that unsigned longs are the same size or bigger than the fields used
803  *	for ino_t and dev_t. If not the types will have to be changed.
804  * Return:
805  *	0 if all ok, -1 otherwise.
806  */
807 
808 #if __STDC__
809 int
map_dev(register ARCHD * arcn,u_long dev_mask,u_long ino_mask)810 map_dev(register ARCHD *arcn, u_long dev_mask, u_long ino_mask)
811 #else
812 int
813 map_dev(arcn, dev_mask, ino_mask)
814 	register ARCHD *arcn;
815 	u_long dev_mask;
816 	u_long ino_mask;
817 #endif
818 {
819 	register DEVT *pt;
820 	register DLIST *dpt;
821 	static dev_t lastdev = 0;	/* next device number to try */
822 	int trc_ino = 0;
823 	int trc_dev = 0;
824 	ino_t trunc_bits = 0;
825 	ino_t nino;
826 
827 	if (dtab == NULL)
828 		return(0);
829 	/*
830 	 * check for device and inode truncation, and extract the truncated
831 	 * bit pattern.
832 	 */
833 	if ((arcn->sb.st_dev & (dev_t)dev_mask) != arcn->sb.st_dev)
834 		++trc_dev;
835 	if ((nino = arcn->sb.st_ino & (ino_t)ino_mask) != arcn->sb.st_ino) {
836 		++trc_ino;
837 		trunc_bits = arcn->sb.st_ino & (ino_t)(~ino_mask);
838 	}
839 
840 	/*
841 	 * see if this device is already being mapped, look up the device
842 	 * then find the truncation bit pattern which applies
843 	 */
844 	if ((pt = chk_dev(arcn->sb.st_dev, 0)) != NULL) {
845 		/*
846 		 * this device is already marked to be remapped
847 		 */
848 		for (dpt = pt->list; dpt != NULL; dpt = dpt->fow)
849 			if (dpt->trunc_bits == trunc_bits)
850 				break;
851 
852 		if (dpt != NULL) {
853 			/*
854 			 * we are being remapped for this device and pattern
855 			 * change the device number to be stored and return
856 			 */
857 			arcn->sb.st_dev = dpt->dev;
858 			arcn->sb.st_ino = nino;
859 			return(0);
860 		}
861 	} else {
862 		/*
863 		 * this device is not being remapped YET. if we do not have any
864 		 * form of truncation, we do not need a remap
865 		 */
866 		if (!trc_ino && !trc_dev)
867 			return(0);
868 
869 		/*
870 		 * we have truncation, have to add this as a device to remap
871 		 */
872 		if ((pt = chk_dev(arcn->sb.st_dev, 1)) == NULL)
873 			goto bad;
874 
875 		/*
876 		 * if we just have a truncated inode, we have to make sure that
877 		 * all future inodes that do not truncate (they have the
878 		 * truncation pattern of all 0's) continue to map to the same
879 		 * device number. We probably have already written inodes with
880 		 * this device number to the archive with the truncation
881 		 * pattern of all 0's. So we add the mapping for all 0's to the
882 		 * same device number.
883 		 */
884 		if (!trc_dev && (trunc_bits != 0)) {
885 			if ((dpt = (DLIST *)malloc(sizeof(DLIST))) == NULL)
886 				goto bad;
887 			dpt->trunc_bits = 0;
888 			dpt->dev = arcn->sb.st_dev;
889 			dpt->fow = pt->list;
890 			pt->list = dpt;
891 		}
892 	}
893 
894 	/*
895 	 * look for a device number not being used. We must watch for wrap
896 	 * around on lastdev (so we do not get stuck looking forever!)
897 	 */
898 	while (++lastdev > 0) {
899 		if (chk_dev(lastdev, 0) != NULL)
900 			continue;
901 		/*
902 		 * found an unused value. If we have reached truncation point
903 		 * for this format we are hosed, so we give up. Otherwise we
904 		 * mark it as being used.
905 		 */
906 		if (((lastdev & ((dev_t)dev_mask)) != lastdev) ||
907 		    (chk_dev(lastdev, 1) == NULL))
908 			goto bad;
909 		break;
910 	}
911 
912 	if ((lastdev <= 0) || ((dpt = (DLIST *)malloc(sizeof(DLIST))) == NULL))
913 		goto bad;
914 
915 	/*
916 	 * got a new device number, store it under this truncation pattern.
917 	 * change the device number this file is being stored with.
918 	 */
919 	dpt->trunc_bits = trunc_bits;
920 	dpt->dev = lastdev;
921 	dpt->fow = pt->list;
922 	pt->list = dpt;
923 	arcn->sb.st_dev = lastdev;
924 	arcn->sb.st_ino = nino;
925 	return(0);
926 
927     bad:
928 	warn(1, "Unable to fix truncated inode/device field when storing %s",
929 	    arcn->name);
930 	warn(0, "Archive may create improper hard links when extracted");
931 	return(0);
932 }
933 
934 /*
935  * directory access/mod time reset table routines (for directories READ by pax)
936  *
937  * The pax -t flag requires that access times of archive files to be the same
938  * before being read by pax. For regular files, access time is restored after
939  * the file has been copied. This database provides the same functionality for
940  * directories read during file tree traversal. Restoring directory access time
941  * is more complex than files since directories may be read several times until
942  * all the descendants in their subtree are visited by fts. Directory access
943  * and modification times are stored during the fts pre-order visit (done
944  * before any descendants in the subtree is visited) and restored after the
945  * fts post-order visit (after all the descendants have been visited). In the
946  * case of premature exit from a subtree (like from the effects of -n), any
947  * directory entries left in this database are reset during final cleanup
948  * operations of pax. Entries are hashed by inode number for fast lookup.
949  */
950 
951 /*
952  * atdir_start()
953  *	create the directory access time database for directories READ by pax.
954  * Return:
955  *	0 is created ok, -1 otherwise.
956  */
957 
958 #if __STDC__
959 int
atdir_start(void)960 atdir_start(void)
961 #else
962 int
963 atdir_start()
964 #endif
965 {
966 	if (atab != NULL)
967 		return(0);
968  	if ((atab = (ATDIR **)calloc(A_TAB_SZ, sizeof(ATDIR *))) == NULL) {
969                 warn(1,"Cannot allocate space for directory access time table");
970                 return(-1);
971         }
972 	return(0);
973 }
974 
975 
976 /*
977  * atdir_end()
978  *	walk through the directory access time table and reset the access time
979  *	of any directory who still has an entry left in the database. These
980  *	entries are for directories READ by pax
981  */
982 
983 #if __STDC__
984 void
atdir_end(void)985 atdir_end(void)
986 #else
987 void
988 atdir_end()
989 #endif
990 {
991 	register ATDIR *pt;
992 	register int i;
993 
994 	if (atab == NULL)
995 		return;
996 	/*
997 	 * for each non-empty hash table entry reset all the directories
998 	 * chained there.
999 	 */
1000 	for (i = 0; i < A_TAB_SZ; ++i) {
1001 		if ((pt = atab[i]) == NULL)
1002 			continue;
1003 		/*
1004 		 * remember to force the times, set_ftime() looks at pmtime
1005 		 * and patime, which only applies to things CREATED by pax,
1006 		 * not read by pax. Read time reset is controlled by -t.
1007 		 */
1008 		for (; pt != NULL; pt = pt->fow)
1009 			set_ftime(pt->name, pt->mtime, pt->atime, 1);
1010 	}
1011 }
1012 
1013 /*
1014  * add_atdir()
1015  *	add a directory to the directory access time table. Table is hashed
1016  *	and chained by inode number. This is for directories READ by pax
1017  */
1018 
1019 #if __STDC__
1020 void
add_atdir(char * fname,dev_t dev,ino_t ino,time_t mtime,time_t atime)1021 add_atdir(char *fname, dev_t dev, ino_t ino, time_t mtime, time_t atime)
1022 #else
1023 void
1024 add_atdir(fname, dev, ino, mtime, atime)
1025 	char *fname;
1026 	dev_t dev;
1027 	ino_t ino;
1028 	time_t mtime;
1029 	time_t atime;
1030 #endif
1031 {
1032 	register ATDIR *pt;
1033 	register u_int indx;
1034 
1035 	if (atab == NULL)
1036 		return;
1037 
1038 	/*
1039 	 * make sure this directory is not already in the table, if so just
1040 	 * return (the older entry always has the correct time). The only
1041 	 * way this will happen is when the same subtree can be traversed by
1042 	 * different args to pax and the -n option is aborting fts out of a
1043 	 * subtree before all the post-order visits have been made).
1044 	 */
1045 	indx = ((unsigned)ino) % A_TAB_SZ;
1046 	if ((pt = atab[indx]) != NULL) {
1047 		while (pt != NULL) {
1048 			if ((pt->ino == ino) && (pt->dev == dev))
1049 				break;
1050 			pt = pt->fow;
1051 		}
1052 
1053 		/*
1054 		 * oops, already there. Leave it alone.
1055 		 */
1056 		if (pt != NULL)
1057 			return;
1058 	}
1059 
1060 	/*
1061 	 * add it to the front of the hash chain
1062 	 */
1063 	if ((pt = (ATDIR *)malloc(sizeof(ATDIR))) != NULL) {
1064 		if ((pt->name = strdup(fname)) != NULL) {
1065 			pt->dev = dev;
1066 			pt->ino = ino;
1067 			pt->mtime = mtime;
1068 			pt->atime = atime;
1069 			pt->fow = atab[indx];
1070 			atab[indx] = pt;
1071 			return;
1072 		}
1073 		(void)free((char *)pt);
1074 	}
1075 
1076 	warn(1, "Directory access time reset table ran out of memory");
1077 	return;
1078 }
1079 
1080 /*
1081  * get_atdir()
1082  *	look up a directory by inode and device number to obtain the access
1083  *	and modification time you want to set to. If found, the modification
1084  *	and access time parameters are set and the entry is removed from the
1085  *	table (as it is no longer needed). These are for directories READ by
1086  *	pax
1087  * Return:
1088  *	0 if found, -1 if not found.
1089  */
1090 
1091 #if __STDC__
1092 int
get_atdir(dev_t dev,ino_t ino,time_t * mtime,time_t * atime)1093 get_atdir(dev_t dev, ino_t ino, time_t *mtime, time_t *atime)
1094 #else
1095 int
1096 get_atdir(dev, ino, mtime, atime)
1097 	dev_t dev;
1098 	ino_t ino;
1099 	time_t *mtime;
1100 	time_t *atime;
1101 #endif
1102 {
1103 	register ATDIR *pt;
1104 	register ATDIR **ppt;
1105 	register u_int indx;
1106 
1107 	if (atab == NULL)
1108 		return(-1);
1109 	/*
1110 	 * hash by inode and search the chain for an inode and device match
1111 	 */
1112 	indx = ((unsigned)ino) % A_TAB_SZ;
1113 	if ((pt = atab[indx]) == NULL)
1114 		return(-1);
1115 
1116 	ppt = &(atab[indx]);
1117 	while (pt != NULL) {
1118 		if ((pt->ino == ino) && (pt->dev == dev))
1119 			break;
1120 		/*
1121 		 * no match, go to next one
1122 		 */
1123 		ppt = &(pt->fow);
1124 		pt = pt->fow;
1125 	}
1126 
1127 	/*
1128 	 * return if we did not find it.
1129 	 */
1130 	if (pt == NULL)
1131 		return(-1);
1132 
1133 	/*
1134 	 * found it. return the times and remove the entry from the table.
1135 	 */
1136 	*ppt = pt->fow;
1137 	*mtime = pt->mtime;
1138 	*atime = pt->atime;
1139 	(void)free((char *)pt->name);
1140 	(void)free((char *)pt);
1141 	return(0);
1142 }
1143 
1144 /*
1145  * directory access mode and time storage routines (for directories CREATED
1146  * by pax).
1147  *
1148  * Pax requires that extracted directories, by default, have their access/mod
1149  * times and permissions set to the values specified in the archive. During the
1150  * actions of extracting (and creating the destination subtree during -rw copy)
1151  * directories extracted may be modified after being created. Even worse is
1152  * that these directories may have been created with file permissions which
1153  * prohibits any descendants of these directories from being extracted. When
1154  * directories are created by pax, access rights may be added to permit the
1155  * creation of files in their subtree. Every time pax creates a directory, the
1156  * times and file permissions specified by the archive are stored. After all
1157  * files have been extracted (or copied), these directories have their times
1158  * and file modes reset to the stored values. The directory info is restored in
1159  * reverse order as entries were added to the data file from root to leaf. To
1160  * restore atime properly, we must go backwards. The data file consists of
1161  * records with two parts, the file name followed by a DIRDATA trailer. The
1162  * fixed sized trailer contains the size of the name plus the off_t location in
1163  * the file. To restore we work backwards through the file reading the trailer
1164  * then the file name.
1165  */
1166 
1167 /*
1168  * dir_start()
1169  *	set up the directory time and file mode storage for directories CREATED
1170  *	by pax.
1171  * Return:
1172  *	0 if ok, -1 otherwise
1173  */
1174 
1175 #if __STDC__
1176 int
dir_start(void)1177 dir_start(void)
1178 #else
1179 int
1180 dir_start()
1181 #endif
1182 {
1183 	char *pt;
1184 
1185 	if (dirfd != -1)
1186 		return(0);
1187 	if ((pt = tempnam((char *)NULL, (char *)NULL)) == NULL)
1188 		return(-1);
1189 
1190 	/*
1191 	 * unlink the file so it goes away at termination by itself
1192 	 */
1193 	(void)unlink(pt);
1194 	if ((dirfd = open(pt, O_RDWR|O_CREAT, 0600)) >= 0) {
1195 		(void)unlink(pt);
1196 		return(0);
1197 	}
1198 	warn(1, "Unable to create temporary file for directory times: %s", pt);
1199 	return(-1);
1200 }
1201 
1202 /*
1203  * add_dir()
1204  *	add the mode and times for a newly CREATED directory
1205  *	name is name of the directory, psb the stat buffer with the data in it,
1206  *	frc_mode is a flag that says whether to force the setting of the mode
1207  *	(ignoring the user set values for preserving file mode). Frc_mode is
1208  *	for the case where we created a file and found that the resulting
1209  *	directory was not writeable and the user asked for file modes to NOT
1210  *	be preserved. (we have to preserve what was created by default, so we
1211  *	have to force the setting at the end. this is stated explicitly in the
1212  *	pax spec)
1213  */
1214 
1215 #if __STDC__
1216 void
add_dir(char * name,int nlen,struct stat * psb,int frc_mode)1217 add_dir(char *name, int nlen, struct stat *psb, int frc_mode)
1218 #else
1219 void
1220 add_dir(name, nlen, psb, frc_mode)
1221 	char *name;
1222 	int nlen;
1223 	struct stat *psb;
1224 	int frc_mode;
1225 #endif
1226 {
1227 	DIRDATA dblk;
1228 
1229 	if (dirfd < 0)
1230 		return;
1231 
1232 	/*
1233 	 * get current position (where file name will start) so we can store it
1234 	 * in the trailer
1235 	 */
1236 	if ((dblk.npos = lseek(dirfd, 0L, SEEK_CUR)) < 0) {
1237 		warn(1,"Unable to store mode and times for directory: %s",name);
1238 		return;
1239 	}
1240 
1241 	/*
1242 	 * write the file name followed by the trailer
1243 	 */
1244 	dblk.nlen = nlen + 1;
1245 	dblk.mode = psb->st_mode & 0xffff;
1246 	dblk.mtime = psb->st_mtime;
1247 	dblk.atime = psb->st_atime;
1248 	dblk.frc_mode = frc_mode;
1249 	if ((write(dirfd, name, dblk.nlen) == dblk.nlen) &&
1250 	    (write(dirfd, (char *)&dblk, sizeof(dblk)) == sizeof(dblk))) {
1251 		++dircnt;
1252 		return;
1253 	}
1254 
1255 	warn(1,"Unable to store mode and times for created directory: %s",name);
1256 	return;
1257 }
1258 
1259 /*
1260  * proc_dir()
1261  *	process all file modes and times stored for directories CREATED
1262  *	by pax
1263  */
1264 
1265 #if __STDC__
1266 void
proc_dir(void)1267 proc_dir(void)
1268 #else
1269 void
1270 proc_dir()
1271 #endif
1272 {
1273 	char name[PAXPATHLEN+1];
1274 	DIRDATA dblk;
1275 	u_long cnt;
1276 
1277 	if (dirfd < 0)
1278 		return;
1279 	/*
1280 	 * read backwards through the file and process each directory
1281 	 */
1282 	for (cnt = 0; cnt < dircnt; ++cnt) {
1283 		/*
1284 		 * read the trailer, then the file name, if this fails
1285 		 * just give up.
1286 		 */
1287 		if (lseek(dirfd, -((off_t)sizeof(dblk)), SEEK_CUR) < 0)
1288 			break;
1289 		if (read(dirfd,(char *)&dblk, sizeof(dblk)) != sizeof(dblk))
1290 			break;
1291 		if (lseek(dirfd, dblk.npos, SEEK_SET) < 0)
1292 			break;
1293 		if (read(dirfd, name, dblk.nlen) != dblk.nlen)
1294 			break;
1295 		if (lseek(dirfd, dblk.npos, SEEK_SET) < 0)
1296 			break;
1297 
1298 		/*
1299 		 * frc_mode set, make sure we set the file modes even if
1300 		 * the user didn't ask for it (see file_subs.c for more info)
1301 		 */
1302 		if (pmode || dblk.frc_mode)
1303 			set_pmode(name, dblk.mode);
1304 		if (patime || pmtime)
1305 			set_ftime(name, dblk.mtime, dblk.atime, 0);
1306 	}
1307 
1308 	(void)close(dirfd);
1309 	dirfd = -1;
1310 	if (cnt != dircnt)
1311 		warn(1,"Unable to set mode and times for created directories");
1312 	return;
1313 }
1314 
1315 /*
1316  * database independent routines
1317  */
1318 
1319 /*
1320  * st_hash()
1321  *	hashes filenames to a u_int for hashing into a table. Looks at the tail
1322  *	end of file, as this provides far better distribution than any other
1323  *	part of the name. For performance reasons we only care about the last
1324  *	MAXKEYLEN chars (should be at LEAST large enough to pick off the file
1325  *	name). Was tested on 500,000 name file tree traversal from the root
1326  *	and gave almost a perfectly uniform distribution of keys when used with
1327  *	prime sized tables (MAXKEYLEN was 128 in test). Hashes (sizeof int)
1328  *	chars at a time and pads with 0 for last addition.
1329  * Return:
1330  *	the hash value of the string MOD (%) the table size.
1331  */
1332 
1333 #if __STDC__
1334 u_int
st_hash(char * name,int len,int tabsz)1335 st_hash(char *name, int len, int tabsz)
1336 #else
1337 u_int
1338 st_hash(name, len, tabsz)
1339 	char *name;
1340 	int len;
1341 	int tabsz;
1342 #endif
1343 {
1344 	register char *pt;
1345 	register char *dest;
1346 	register char *end;
1347 	register int i;
1348 	register u_int key = 0;
1349 	register int steps;
1350 	register int res;
1351 	u_int val;
1352 
1353 	/*
1354 	 * only look at the tail up to MAXKEYLEN, we do not need to waste
1355 	 * time here (remember these are pathnames, the tail is what will
1356 	 * spread out the keys)
1357 	 */
1358 	if (len > MAXKEYLEN) {
1359                 pt = &(name[len - MAXKEYLEN]);
1360 		len = MAXKEYLEN;
1361 	} else
1362 		pt = name;
1363 
1364 	/*
1365 	 * calculate the number of u_int size steps in the string and if
1366 	 * there is a runt to deal with
1367 	 */
1368 	steps = len/sizeof(u_int);
1369 	res = len % sizeof(u_int);
1370 
1371 	/*
1372 	 * add up the value of the string in unsigned integer sized pieces
1373 	 * too bad we cannot have unsigned int aligned strings, then we
1374 	 * could avoid the expensive copy.
1375 	 */
1376 	for (i = 0; i < steps; ++i) {
1377 		end = pt + sizeof(u_int);
1378 		dest = (char *)&val;
1379 		while (pt < end)
1380 			*dest++ = *pt++;
1381 		key += val;
1382 	}
1383 
1384 	/*
1385 	 * add in the runt padded with zero to the right
1386 	 */
1387 	if (res) {
1388 		val = 0;
1389 		end = pt + res;
1390 		dest = (char *)&val;
1391 		while (pt < end)
1392 			*dest++ = *pt++;
1393 		key += val;
1394 	}
1395 
1396 	/*
1397 	 * return the result mod the table size
1398 	 */
1399 	return(key % tabsz);
1400 }
1401