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