tables.c revision 76019
1228072Sbapt/*- 2228072Sbapt * Copyright (c) 1992 Keith Muller. 3228072Sbapt * Copyright (c) 1992, 1993 4228072Sbapt * The Regents of the University of California. All rights reserved. 5228072Sbapt * 6228072Sbapt * This code is derived from software contributed to Berkeley by 7228072Sbapt * Keith Muller of the University of California, San Diego. 8228072Sbapt * 9228072Sbapt * Redistribution and use in source and binary forms, with or without 10228072Sbapt * modification, are permitted provided that the following conditions 11228072Sbapt * are met: 12228072Sbapt * 1. Redistributions of source code must retain the above copyright 13228072Sbapt * notice, this list of conditions and the following disclaimer. 14228072Sbapt * 2. Redistributions in binary form must reproduce the above copyright 15228072Sbapt * notice, this list of conditions and the following disclaimer in the 16228072Sbapt * documentation and/or other materials provided with the distribution. 17228072Sbapt * 3. All advertising materials mentioning features or use of this software 18228072Sbapt * must display the following acknowledgement: 19228072Sbapt * This product includes software developed by the University of 20228072Sbapt * California, Berkeley and its contributors. 21228072Sbapt * 4. Neither the name of the University nor the names of its contributors 22228072Sbapt * may be used to endorse or promote products derived from this software 23228072Sbapt * without specific prior written permission. 24228072Sbapt * 25228072Sbapt * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 26228072Sbapt * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 27228072Sbapt * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 28228072Sbapt * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 29228072Sbapt * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 30228072Sbapt * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 31228072Sbapt * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 32228072Sbapt * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 33228072Sbapt * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 34228072Sbapt * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 35228072Sbapt * SUCH DAMAGE. 36228072Sbapt */ 37228072Sbapt 38228072Sbapt#ifndef lint 39228072Sbapt#if 0 40228072Sbaptstatic char sccsid[] = "@(#)tables.c 8.1 (Berkeley) 5/31/93"; 41228072Sbapt#endif 42228072Sbaptstatic const char rcsid[] = 43228072Sbapt "$FreeBSD: head/bin/pax/tables.c 76019 2001-04-26 09:22:28Z kris $"; 44228072Sbapt#endif /* not lint */ 45228072Sbapt 46228072Sbapt#include <sys/types.h> 47228072Sbapt#include <sys/time.h> 48228072Sbapt#include <sys/stat.h> 49228072Sbapt#include <sys/fcntl.h> 50228072Sbapt#include <errno.h> 51228072Sbapt#include <stdio.h> 52228072Sbapt#include <stdlib.h> 53228072Sbapt#include <string.h> 54228072Sbapt#include <unistd.h> 55228072Sbapt#include "pax.h" 56228072Sbapt#include "tables.h" 57228072Sbapt#include "extern.h" 58228072Sbapt 59228072Sbapt/* 60250125Sjkim * Routines for controlling the contents of all the different databases pax 61228072Sbapt * keeps. Tables are dynamically created only when they are needed. The 62228072Sbapt * goal was speed and the ability to work with HUGE archives. The databases 63250125Sjkim * were kept simple, but do have complex rules for when the contents change. 64228072Sbapt * As of this writing, the POSIX library functions were more complex than 65228072Sbapt * needed for this application (pax databases have very short lifetimes and 66228072Sbapt * do not survive after pax is finished). Pax is required to handle very 67228072Sbapt * large archives. These database routines carefully combine memory usage and 68228072Sbapt * temporary file storage in ways which will not significantly impact runtime 69228072Sbapt * performance while allowing the largest possible archives to be handled. 70228072Sbapt * Trying to force the fit to the POSIX databases routines was not considered 71228072Sbapt * time well spent. 72228072Sbapt */ 73228072Sbapt 74228072Sbaptstatic HRDLNK **ltab = NULL; /* hard link table for detecting hard links */ 75228072Sbaptstatic FTM **ftab = NULL; /* file time table for updating arch */ 76228072Sbaptstatic NAMT **ntab = NULL; /* interactive rename storage table */ 77228072Sbaptstatic DEVT **dtab = NULL; /* device/inode mapping tables */ 78228072Sbaptstatic ATDIR **atab = NULL; /* file tree directory time reset table */ 79228072Sbaptstatic int dirfd = -1; /* storage for setting created dir time/mode */ 80228072Sbaptstatic u_long dircnt; /* entries in dir time/mode storage */ 81228072Sbaptstatic int ffd = -1; /* tmp file for file time table name storage */ 82228072Sbapt 83228072Sbaptstatic DEVT *chk_dev __P((dev_t, int)); 84228072Sbapt 85228072Sbapt/* 86228072Sbapt * hard link table routines 87228072Sbapt * 88228072Sbapt * The hard link table tries to detect hard links to files using the device and 89228072Sbapt * inode values. We do this when writing an archive, so we can tell the format 90228072Sbapt * write routine that this file is a hard link to another file. The format 91228072Sbapt * write routine then can store this file in whatever way it wants (as a hard 92228072Sbapt * link if the format supports that like tar, or ignore this info like cpio). 93228072Sbapt * (Actually a field in the format driver table tells us if the format wants 94228072Sbapt * hard link info. if not, we do not waste time looking for them). We also use 95228072Sbapt * the same table when reading an archive. In that situation, this table is 96228072Sbapt * used by the format read routine to detect hard links from stored dev and 97228072Sbapt * inode numbers (like cpio). This will allow pax to create a link when one 98228072Sbapt * can be detected by the archive format. 99228072Sbapt */ 100228072Sbapt 101228072Sbapt/* 102228072Sbapt * lnk_start 103228072Sbapt * Creates the hard link table. 104228072Sbapt * Return: 105228072Sbapt * 0 if created, -1 if failure 106228072Sbapt */ 107228072Sbapt 108228072Sbapt#ifdef __STDC__ 109228072Sbaptint 110228072Sbaptlnk_start(void) 111228072Sbapt#else 112228072Sbaptint 113228072Sbaptlnk_start() 114228072Sbapt#endif 115228072Sbapt{ 116228072Sbapt if (ltab != NULL) 117228072Sbapt return(0); 118228072Sbapt if ((ltab = (HRDLNK **)calloc(L_TAB_SZ, sizeof(HRDLNK *))) == NULL) { 119228072Sbapt paxwarn(1, "Cannot allocate memory for hard link table"); 120228072Sbapt return(-1); 121228072Sbapt } 122228072Sbapt return(0); 123228072Sbapt} 124228072Sbapt 125228072Sbapt/* 126228072Sbapt * chk_lnk() 127228072Sbapt * Looks up entry in hard link hash table. If found, it copies the name 128228072Sbapt * of the file it is linked to (we already saw that file) into ln_name. 129228072Sbapt * lnkcnt is decremented and if goes to 1 the node is deleted from the 130228072Sbapt * database. (We have seen all the links to this file). If not found, 131228072Sbapt * we add the file to the database if it has the potential for having 132228072Sbapt * hard links to other files we may process (it has a link count > 1) 133228072Sbapt * Return: 134228072Sbapt * if found returns 1; if not found returns 0; -1 on error 135228072Sbapt */ 136228072Sbapt 137228072Sbapt#ifdef __STDC__ 138228072Sbaptint 139228072Sbaptchk_lnk(register ARCHD *arcn) 140228072Sbapt#else 141228072Sbaptint 142228072Sbaptchk_lnk(arcn) 143228072Sbapt register ARCHD *arcn; 144228072Sbapt#endif 145228072Sbapt{ 146228072Sbapt register HRDLNK *pt; 147228072Sbapt register HRDLNK **ppt; 148228072Sbapt register u_int indx; 149228072Sbapt 150228072Sbapt if (ltab == NULL) 151228072Sbapt return(-1); 152228072Sbapt /* 153228072Sbapt * ignore those nodes that cannot have hard links 154228072Sbapt */ 155228072Sbapt if ((arcn->type == PAX_DIR) || (arcn->sb.st_nlink <= 1)) 156228072Sbapt return(0); 157228072Sbapt 158228072Sbapt /* 159228072Sbapt * hash inode number and look for this file 160228072Sbapt */ 161228072Sbapt indx = ((unsigned)arcn->sb.st_ino) % L_TAB_SZ; 162228072Sbapt if ((pt = ltab[indx]) != NULL) { 163228072Sbapt /* 164228072Sbapt * it's hash chain in not empty, walk down looking for it 165228072Sbapt */ 166228072Sbapt ppt = &(ltab[indx]); 167228072Sbapt while (pt != NULL) { 168228072Sbapt if ((pt->ino == arcn->sb.st_ino) && 169228072Sbapt (pt->dev == arcn->sb.st_dev)) 170228072Sbapt break; 171228072Sbapt ppt = &(pt->fow); 172228072Sbapt pt = pt->fow; 173228072Sbapt } 174228072Sbapt 175228072Sbapt if (pt != NULL) { 176228072Sbapt /* 177228072Sbapt * found a link. set the node type and copy in the 178228072Sbapt * name of the file it is to link to. we need to 179228072Sbapt * handle hardlinks to regular files differently than 180228072Sbapt * other links. 181228072Sbapt */ 182228072Sbapt arcn->ln_nlen = l_strncpy(arcn->ln_name, pt->name, 183228072Sbapt PAXPATHLEN+1); 184228072Sbapt arcn->ln_name[PAXPATHLEN] = '\0'; 185228072Sbapt if (arcn->type == PAX_REG) 186228072Sbapt arcn->type = PAX_HRG; 187228072Sbapt else 188228072Sbapt arcn->type = PAX_HLK; 189228072Sbapt 190228072Sbapt /* 191228072Sbapt * if we have found all the links to this file, remove 192228072Sbapt * it from the database 193228072Sbapt */ 194228072Sbapt if (--pt->nlink <= 1) { 195228072Sbapt *ppt = pt->fow; 196228072Sbapt (void)free((char *)pt->name); 197228072Sbapt (void)free((char *)pt); 198228072Sbapt } 199228072Sbapt return(1); 200228072Sbapt } 201228072Sbapt } 202228072Sbapt 203228072Sbapt /* 204228072Sbapt * we never saw this file before. It has links so we add it to the 205228072Sbapt * front of this hash chain 206228072Sbapt */ 207228072Sbapt if ((pt = (HRDLNK *)malloc(sizeof(HRDLNK))) != NULL) { 208228072Sbapt if ((pt->name = strdup(arcn->name)) != NULL) { 209228072Sbapt pt->dev = arcn->sb.st_dev; 210228072Sbapt pt->ino = arcn->sb.st_ino; 211228072Sbapt pt->nlink = arcn->sb.st_nlink; 212228072Sbapt pt->fow = ltab[indx]; 213228072Sbapt ltab[indx] = pt; 214228072Sbapt return(0); 215228072Sbapt } 216228072Sbapt (void)free((char *)pt); 217228072Sbapt } 218228072Sbapt 219228072Sbapt paxwarn(1, "Hard link table out of memory"); 220228072Sbapt return(-1); 221228072Sbapt} 222228072Sbapt 223228072Sbapt/* 224228072Sbapt * purg_lnk 225228072Sbapt * remove reference for a file that we may have added to the data base as 226228072Sbapt * a potential source for hard links. We ended up not using the file, so 227228072Sbapt * we do not want to accidently point another file at it later on. 228228072Sbapt */ 229228072Sbapt 230228072Sbapt#ifdef __STDC__ 231228072Sbaptvoid 232228072Sbaptpurg_lnk(register ARCHD *arcn) 233228072Sbapt#else 234228072Sbaptvoid 235228072Sbaptpurg_lnk(arcn) 236228072Sbapt register ARCHD *arcn; 237228072Sbapt#endif 238228072Sbapt{ 239228072Sbapt register HRDLNK *pt; 240228072Sbapt register HRDLNK **ppt; 241228072Sbapt register u_int indx; 242228072Sbapt 243228072Sbapt if (ltab == NULL) 244228072Sbapt return; 245228072Sbapt /* 246228072Sbapt * do not bother to look if it could not be in the database 247228072Sbapt */ 248228072Sbapt if ((arcn->sb.st_nlink <= 1) || (arcn->type == PAX_DIR) || 249228072Sbapt (arcn->type == PAX_HLK) || (arcn->type == PAX_HRG)) 250228072Sbapt return; 251228072Sbapt 252228072Sbapt /* 253228072Sbapt * find the hash chain for this inode value, if empty return 254228072Sbapt */ 255228072Sbapt indx = ((unsigned)arcn->sb.st_ino) % L_TAB_SZ; 256228072Sbapt if ((pt = ltab[indx]) == NULL) 257228072Sbapt return; 258228072Sbapt 259228072Sbapt /* 260228072Sbapt * walk down the list looking for the inode/dev pair, unlink and 261228072Sbapt * free if found 262228072Sbapt */ 263228072Sbapt ppt = &(ltab[indx]); 264228072Sbapt while (pt != NULL) { 265228072Sbapt if ((pt->ino == arcn->sb.st_ino) && 266228072Sbapt (pt->dev == arcn->sb.st_dev)) 267228072Sbapt break; 268228072Sbapt ppt = &(pt->fow); 269228072Sbapt pt = pt->fow; 270228072Sbapt } 271228072Sbapt if (pt == NULL) 272228072Sbapt return; 273228072Sbapt 274228072Sbapt /* 275228072Sbapt * remove and free it 276228072Sbapt */ 277228072Sbapt *ppt = pt->fow; 278228072Sbapt (void)free((char *)pt->name); 279228072Sbapt (void)free((char *)pt); 280228072Sbapt} 281228072Sbapt 282228072Sbapt/* 283228072Sbapt * lnk_end() 284228072Sbapt * pull apart a existing link table so we can reuse it. We do this between 285228072Sbapt * read and write phases of append with update. (The format may have 286228072Sbapt * used the link table, and we need to start with a fresh table for the 287228072Sbapt * write phase 288228072Sbapt */ 289228072Sbapt 290228072Sbapt#ifdef __STDC__ 291228072Sbaptvoid 292228072Sbaptlnk_end(void) 293228072Sbapt#else 294228072Sbaptvoid 295228072Sbaptlnk_end() 296228072Sbapt#endif 297228072Sbapt{ 298228072Sbapt register int i; 299228072Sbapt register HRDLNK *pt; 300228072Sbapt register HRDLNK *ppt; 301228072Sbapt 302228072Sbapt if (ltab == NULL) 303228072Sbapt return; 304228072Sbapt 305228072Sbapt for (i = 0; i < L_TAB_SZ; ++i) { 306228072Sbapt if (ltab[i] == NULL) 307228072Sbapt continue; 308228072Sbapt pt = ltab[i]; 309228072Sbapt ltab[i] = NULL; 310228072Sbapt 311228072Sbapt /* 312228072Sbapt * free up each entry on this chain 313228072Sbapt */ 314228072Sbapt while (pt != NULL) { 315228072Sbapt ppt = pt; 316228072Sbapt pt = ppt->fow; 317228072Sbapt (void)free((char *)ppt->name); 318228072Sbapt (void)free((char *)ppt); 319228072Sbapt } 320228072Sbapt } 321228072Sbapt return; 322228072Sbapt} 323228072Sbapt 324228072Sbapt/* 325228072Sbapt * modification time table routines 326228072Sbapt * 327228072Sbapt * The modification time table keeps track of last modification times for all 328228072Sbapt * files stored in an archive during a write phase when -u is set. We only 329228072Sbapt * add a file to the archive if it is newer than a file with the same name 330228072Sbapt * already stored on the archive (if there is no other file with the same 331228072Sbapt * name on the archive it is added). This applies to writes and appends. 332228072Sbapt * An append with an -u must read the archive and store the modification time 333228072Sbapt * for every file on that archive before starting the write phase. It is clear 334228072Sbapt * that this is one HUGE database. To save memory space, the actual file names 335250125Sjkim * are stored in a scatch file and indexed by an in memory hash table. The 336250125Sjkim * hash table is indexed by hashing the file path. The nodes in the table store 337228072Sbapt * the length of the filename and the lseek offset within the scratch file 338228072Sbapt * where the actual name is stored. Since there are never any deletions to this 339228072Sbapt * table, fragmentation of the scratch file is never a issue. Lookups seem to 340228072Sbapt * not exhibit any locality at all (files in the database are rarely 341228072Sbapt * looked up more than once...). So caching is just a waste of memory. The 342228072Sbapt * only limitation is the amount of scatch file space available to store the 343228072Sbapt * path names. 344228072Sbapt */ 345228072Sbapt 346228072Sbapt/* 347228072Sbapt * ftime_start() 348228072Sbapt * create the file time hash table and open for read/write the scratch 349228072Sbapt * file. (after created it is unlinked, so when we exit we leave 350228072Sbapt * no witnesses). 351228072Sbapt * Return: 352228072Sbapt * 0 if the table and file was created ok, -1 otherwise 353228072Sbapt */ 354228072Sbapt 355228072Sbapt#ifdef __STDC__ 356228072Sbaptint 357228072Sbaptftime_start(void) 358228072Sbapt#else 359228072Sbaptint 360228072Sbaptftime_start() 361228072Sbapt#endif 362228072Sbapt{ 363228072Sbapt 364228072Sbapt if (ftab != NULL) 365228072Sbapt return(0); 366228072Sbapt if ((ftab = (FTM **)calloc(F_TAB_SZ, sizeof(FTM *))) == NULL) { 367228072Sbapt paxwarn(1, "Cannot allocate memory for file time table"); 368228072Sbapt return(-1); 369228072Sbapt } 370228072Sbapt 371250125Sjkim /* 372228072Sbapt * get random name and create temporary scratch file, unlink name 373228072Sbapt * so it will get removed on exit 374228072Sbapt */ 375228072Sbapt memcpy(tempbase, _TFILE_BASE, sizeof(_TFILE_BASE)); 376228072Sbapt if ((ffd = mkstemp(tempfile)) < 0) { 377228072Sbapt syswarn(1, errno, "Unable to create temporary file: %s", 378228072Sbapt tempfile); 379228072Sbapt return(-1); 380228072Sbapt } 381228072Sbapt (void)unlink(tempfile); 382228072Sbapt 383228072Sbapt return(0); 384228072Sbapt} 385228072Sbapt 386228072Sbapt/* 387228072Sbapt * chk_ftime() 388228072Sbapt * looks up entry in file time hash table. If not found, the file is 389228072Sbapt * added to the hash table and the file named stored in the scratch file. 390228072Sbapt * If a file with the same name is found, the file times are compared and 391228072Sbapt * the most recent file time is retained. If the new file was younger (or 392228072Sbapt * was not in the database) the new file is selected for storage. 393228072Sbapt * Return: 394228072Sbapt * 0 if file should be added to the archive, 1 if it should be skipped, 395228072Sbapt * -1 on error 396228072Sbapt */ 397228072Sbapt 398228072Sbapt#ifdef __STDC__ 399228072Sbaptint 400228072Sbaptchk_ftime(register ARCHD *arcn) 401228072Sbapt#else 402228072Sbaptint 403228072Sbaptchk_ftime(arcn) 404228072Sbapt register ARCHD *arcn; 405228072Sbapt#endif 406228072Sbapt{ 407228072Sbapt register FTM *pt; 408228072Sbapt register int namelen; 409228072Sbapt register u_int indx; 410228072Sbapt char ckname[PAXPATHLEN+1]; 411228072Sbapt 412228072Sbapt /* 413228072Sbapt * no info, go ahead and add to archive 414228072Sbapt */ 415228072Sbapt if (ftab == NULL) 416228072Sbapt return(0); 417228072Sbapt 418228072Sbapt /* 419228072Sbapt * hash the pathname and look up in table 420228072Sbapt */ 421228072Sbapt namelen = arcn->nlen; 422228072Sbapt indx = st_hash(arcn->name, namelen, F_TAB_SZ); 423228072Sbapt if ((pt = ftab[indx]) != NULL) { 424228072Sbapt /* 425228072Sbapt * the hash chain is not empty, walk down looking for match 426228072Sbapt * only read up the path names if the lengths match, speeds 427228072Sbapt * up the search a lot 428228072Sbapt */ 429228072Sbapt while (pt != NULL) { 430228072Sbapt if (pt->namelen == namelen) { 431228072Sbapt /* 432228072Sbapt * potential match, have to read the name 433228072Sbapt * from the scratch file. 434228072Sbapt */ 435228072Sbapt if (lseek(ffd,pt->seek,SEEK_SET) != pt->seek) { 436228072Sbapt syswarn(1, errno, 437228072Sbapt "Failed ftime table seek"); 438228072Sbapt return(-1); 439228072Sbapt } 440228072Sbapt if (read(ffd, ckname, namelen) != namelen) { 441228072Sbapt syswarn(1, errno, 442228072Sbapt "Failed ftime table read"); 443228072Sbapt return(-1); 444228072Sbapt } 445228072Sbapt 446228072Sbapt /* 447228072Sbapt * if the names match, we are done 448228072Sbapt */ 449228072Sbapt if (!strncmp(ckname, arcn->name, namelen)) 450228072Sbapt break; 451228072Sbapt } 452228072Sbapt 453228072Sbapt /* 454228072Sbapt * try the next entry on the chain 455228072Sbapt */ 456228072Sbapt pt = pt->fow; 457228072Sbapt } 458228072Sbapt 459228072Sbapt if (pt != NULL) { 460228072Sbapt /* 461228072Sbapt * found the file, compare the times, save the newer 462228072Sbapt */ 463228072Sbapt if (arcn->sb.st_mtime > pt->mtime) { 464228072Sbapt /* 465228072Sbapt * file is newer 466228072Sbapt */ 467228072Sbapt pt->mtime = arcn->sb.st_mtime; 468228072Sbapt return(0); 469228072Sbapt } 470228072Sbapt /* 471228072Sbapt * file is older 472228072Sbapt */ 473228072Sbapt return(1); 474228072Sbapt } 475228072Sbapt } 476228072Sbapt 477228072Sbapt /* 478228072Sbapt * not in table, add it 479228072Sbapt */ 480228072Sbapt if ((pt = (FTM *)malloc(sizeof(FTM))) != NULL) { 481228072Sbapt /* 482228072Sbapt * add the name at the end of the scratch file, saving the 483228072Sbapt * offset. add the file to the head of the hash chain 484228072Sbapt */ 485228072Sbapt if ((pt->seek = lseek(ffd, (off_t)0, SEEK_END)) >= 0) { 486228072Sbapt if (write(ffd, arcn->name, namelen) == namelen) { 487228072Sbapt pt->mtime = arcn->sb.st_mtime; 488228072Sbapt pt->namelen = namelen; 489228072Sbapt pt->fow = ftab[indx]; 490228072Sbapt ftab[indx] = pt; 491228072Sbapt return(0); 492228072Sbapt } 493228072Sbapt syswarn(1, errno, "Failed write to file time table"); 494228072Sbapt } else 495228072Sbapt syswarn(1, errno, "Failed seek on file time table"); 496228072Sbapt } else 497228072Sbapt paxwarn(1, "File time table ran out of memory"); 498228072Sbapt 499228072Sbapt if (pt != NULL) 500228072Sbapt (void)free((char *)pt); 501228072Sbapt return(-1); 502228072Sbapt} 503 504/* 505 * Interactive rename table routines 506 * 507 * The interactive rename table keeps track of the new names that the user 508 * assigns to files from tty input. Since this map is unique for each file 509 * we must store it in case there is a reference to the file later in archive 510 * (a link). Otherwise we will be unable to find the file we know was 511 * extracted. The remapping of these files is stored in a memory based hash 512 * table (it is assumed since input must come from /dev/tty, it is unlikely to 513 * be a very large table). 514 */ 515 516/* 517 * name_start() 518 * create the interactive rename table 519 * Return: 520 * 0 if successful, -1 otherwise 521 */ 522 523#ifdef __STDC__ 524int 525name_start(void) 526#else 527int 528name_start() 529#endif 530{ 531 if (ntab != NULL) 532 return(0); 533 if ((ntab = (NAMT **)calloc(N_TAB_SZ, sizeof(NAMT *))) == NULL) { 534 paxwarn(1, "Cannot allocate memory for interactive rename table"); 535 return(-1); 536 } 537 return(0); 538} 539 540/* 541 * add_name() 542 * add the new name to old name mapping just created by the user. 543 * If an old name mapping is found (there may be duplicate names on an 544 * archive) only the most recent is kept. 545 * Return: 546 * 0 if added, -1 otherwise 547 */ 548 549#ifdef __STDC__ 550int 551add_name(register char *oname, int onamelen, char *nname) 552#else 553int 554add_name(oname, onamelen, nname) 555 register char *oname; 556 int onamelen; 557 char *nname; 558#endif 559{ 560 register NAMT *pt; 561 register u_int indx; 562 563 if (ntab == NULL) { 564 /* 565 * should never happen 566 */ 567 paxwarn(0, "No interactive rename table, links may fail\n"); 568 return(0); 569 } 570 571 /* 572 * look to see if we have already mapped this file, if so we 573 * will update it 574 */ 575 indx = st_hash(oname, onamelen, N_TAB_SZ); 576 if ((pt = ntab[indx]) != NULL) { 577 /* 578 * look down the has chain for the file 579 */ 580 while ((pt != NULL) && (strcmp(oname, pt->oname) != 0)) 581 pt = pt->fow; 582 583 if (pt != NULL) { 584 /* 585 * found an old mapping, replace it with the new one 586 * the user just input (if it is different) 587 */ 588 if (strcmp(nname, pt->nname) == 0) 589 return(0); 590 591 (void)free((char *)pt->nname); 592 if ((pt->nname = strdup(nname)) == NULL) { 593 paxwarn(1, "Cannot update rename table"); 594 return(-1); 595 } 596 return(0); 597 } 598 } 599 600 /* 601 * this is a new mapping, add it to the table 602 */ 603 if ((pt = (NAMT *)malloc(sizeof(NAMT))) != NULL) { 604 if ((pt->oname = strdup(oname)) != NULL) { 605 if ((pt->nname = strdup(nname)) != NULL) { 606 pt->fow = ntab[indx]; 607 ntab[indx] = pt; 608 return(0); 609 } 610 (void)free((char *)pt->oname); 611 } 612 (void)free((char *)pt); 613 } 614 paxwarn(1, "Interactive rename table out of memory"); 615 return(-1); 616} 617 618/* 619 * sub_name() 620 * look up a link name to see if it points at a file that has been 621 * remapped by the user. If found, the link is adjusted to contain the 622 * new name (oname is the link to name) 623 */ 624 625#ifdef __STDC__ 626void 627sub_name(register char *oname, int *onamelen) 628#else 629void 630sub_name(oname, onamelen) 631 register char *oname; 632 int *onamelen; 633#endif 634{ 635 register NAMT *pt; 636 register u_int indx; 637 638 if (ntab == NULL) 639 return; 640 /* 641 * look the name up in the hash table 642 */ 643 indx = st_hash(oname, *onamelen, N_TAB_SZ); 644 if ((pt = ntab[indx]) == NULL) 645 return; 646 647 while (pt != NULL) { 648 /* 649 * walk down the hash chain looking for a match 650 */ 651 if (strcmp(oname, pt->oname) == 0) { 652 /* 653 * found it, replace it with the new name 654 * and return (we know that oname has enough space) 655 */ 656 *onamelen = l_strncpy(oname, pt->nname, PAXPATHLEN+1); 657 oname[PAXPATHLEN] = '\0'; 658 return; 659 } 660 pt = pt->fow; 661 } 662 663 /* 664 * no match, just return 665 */ 666 return; 667} 668 669/* 670 * device/inode mapping table routines 671 * (used with formats that store device and inodes fields) 672 * 673 * device/inode mapping tables remap the device field in a archive header. The 674 * device/inode fields are used to determine when files are hard links to each 675 * other. However these values have very little meaning outside of that. This 676 * database is used to solve one of two different problems. 677 * 678 * 1) when files are appended to an archive, while the new files may have hard 679 * links to each other, you cannot determine if they have hard links to any 680 * file already stored on the archive from a prior run of pax. We must assume 681 * that these inode/device pairs are unique only within a SINGLE run of pax 682 * (which adds a set of files to an archive). So we have to make sure the 683 * inode/dev pairs we add each time are always unique. We do this by observing 684 * while the inode field is very dense, the use of the dev field is fairly 685 * sparse. Within each run of pax, we remap any device number of a new archive 686 * member that has a device number used in a prior run and already stored in a 687 * file on the archive. During the read phase of the append, we store the 688 * device numbers used and mark them to not be used by any file during the 689 * write phase. If during write we go to use one of those old device numbers, 690 * we remap it to a new value. 691 * 692 * 2) Often the fields in the archive header used to store these values are 693 * too small to store the entire value. The result is an inode or device value 694 * which can be truncated. This really can foul up an archive. With truncation 695 * we end up creating links between files that are really not links (after 696 * truncation the inodes are the same value). We address that by detecting 697 * truncation and forcing a remap of the device field to split truncated 698 * inodes away from each other. Each truncation creates a pattern of bits that 699 * are removed. We use this pattern of truncated bits to partition the inodes 700 * on a single device to many different devices (each one represented by the 701 * truncated bit pattern). All inodes on the same device that have the same 702 * truncation pattern are mapped to the same new device. Two inodes that 703 * truncate to the same value clearly will always have different truncation 704 * bit patterns, so they will be split from away each other. When we spot 705 * device truncation we remap the device number to a non truncated value. 706 * (for more info see table.h for the data structures involved). 707 */ 708 709/* 710 * dev_start() 711 * create the device mapping table 712 * Return: 713 * 0 if successful, -1 otherwise 714 */ 715 716#ifdef __STDC__ 717int 718dev_start(void) 719#else 720int 721dev_start() 722#endif 723{ 724 if (dtab != NULL) 725 return(0); 726 if ((dtab = (DEVT **)calloc(D_TAB_SZ, sizeof(DEVT *))) == NULL) { 727 paxwarn(1, "Cannot allocate memory for device mapping table"); 728 return(-1); 729 } 730 return(0); 731} 732 733/* 734 * add_dev() 735 * add a device number to the table. this will force the device to be 736 * remapped to a new value if it be used during a write phase. This 737 * function is called during the read phase of an append to prohibit the 738 * use of any device number already in the archive. 739 * Return: 740 * 0 if added ok, -1 otherwise 741 */ 742 743#ifdef __STDC__ 744int 745add_dev(register ARCHD *arcn) 746#else 747int 748add_dev(arcn) 749 register ARCHD *arcn; 750#endif 751{ 752 if (chk_dev(arcn->sb.st_dev, 1) == NULL) 753 return(-1); 754 return(0); 755} 756 757/* 758 * chk_dev() 759 * check for a device value in the device table. If not found and the add 760 * flag is set, it is added. This does NOT assign any mapping values, just 761 * adds the device number as one that need to be remapped. If this device 762 * is already mapped, just return with a pointer to that entry. 763 * Return: 764 * pointer to the entry for this device in the device map table. Null 765 * if the add flag is not set and the device is not in the table (it is 766 * not been seen yet). If add is set and the device cannot be added, null 767 * is returned (indicates an error). 768 */ 769 770#ifdef __STDC__ 771static DEVT * 772chk_dev(dev_t dev, int add) 773#else 774static DEVT * 775chk_dev(dev, add) 776 dev_t dev; 777 int add; 778#endif 779{ 780 register DEVT *pt; 781 register u_int indx; 782 783 if (dtab == NULL) 784 return(NULL); 785 /* 786 * look to see if this device is already in the table 787 */ 788 indx = ((unsigned)dev) % D_TAB_SZ; 789 if ((pt = dtab[indx]) != NULL) { 790 while ((pt != NULL) && (pt->dev != dev)) 791 pt = pt->fow; 792 793 /* 794 * found it, return a pointer to it 795 */ 796 if (pt != NULL) 797 return(pt); 798 } 799 800 /* 801 * not in table, we add it only if told to as this may just be a check 802 * to see if a device number is being used. 803 */ 804 if (add == 0) 805 return(NULL); 806 807 /* 808 * allocate a node for this device and add it to the front of the hash 809 * chain. Note we do not assign remaps values here, so the pt->list 810 * list must be NULL. 811 */ 812 if ((pt = (DEVT *)malloc(sizeof(DEVT))) == NULL) { 813 paxwarn(1, "Device map table out of memory"); 814 return(NULL); 815 } 816 pt->dev = dev; 817 pt->list = NULL; 818 pt->fow = dtab[indx]; 819 dtab[indx] = pt; 820 return(pt); 821} 822/* 823 * map_dev() 824 * given an inode and device storage mask (the mask has a 1 for each bit 825 * the archive format is able to store in a header), we check for inode 826 * and device truncation and remap the device as required. Device mapping 827 * can also occur when during the read phase of append a device number was 828 * seen (and was marked as do not use during the write phase). WE ASSUME 829 * that unsigned longs are the same size or bigger than the fields used 830 * for ino_t and dev_t. If not the types will have to be changed. 831 * Return: 832 * 0 if all ok, -1 otherwise. 833 */ 834 835#ifdef __STDC__ 836int 837map_dev(register ARCHD *arcn, u_long dev_mask, u_long ino_mask) 838#else 839int 840map_dev(arcn, dev_mask, ino_mask) 841 register ARCHD *arcn; 842 u_long dev_mask; 843 u_long ino_mask; 844#endif 845{ 846 register DEVT *pt; 847 register DLIST *dpt; 848 static dev_t lastdev = 0; /* next device number to try */ 849 int trc_ino = 0; 850 int trc_dev = 0; 851 ino_t trunc_bits = 0; 852 ino_t nino; 853 854 if (dtab == NULL) 855 return(0); 856 /* 857 * check for device and inode truncation, and extract the truncated 858 * bit pattern. 859 */ 860 if ((arcn->sb.st_dev & (dev_t)dev_mask) != arcn->sb.st_dev) 861 ++trc_dev; 862 if ((nino = arcn->sb.st_ino & (ino_t)ino_mask) != arcn->sb.st_ino) { 863 ++trc_ino; 864 trunc_bits = arcn->sb.st_ino & (ino_t)(~ino_mask); 865 } 866 867 /* 868 * see if this device is already being mapped, look up the device 869 * then find the truncation bit pattern which applies 870 */ 871 if ((pt = chk_dev(arcn->sb.st_dev, 0)) != NULL) { 872 /* 873 * this device is already marked to be remapped 874 */ 875 for (dpt = pt->list; dpt != NULL; dpt = dpt->fow) 876 if (dpt->trunc_bits == trunc_bits) 877 break; 878 879 if (dpt != NULL) { 880 /* 881 * we are being remapped for this device and pattern 882 * change the device number to be stored and return 883 */ 884 arcn->sb.st_dev = dpt->dev; 885 arcn->sb.st_ino = nino; 886 return(0); 887 } 888 } else { 889 /* 890 * this device is not being remapped YET. if we do not have any 891 * form of truncation, we do not need a remap 892 */ 893 if (!trc_ino && !trc_dev) 894 return(0); 895 896 /* 897 * we have truncation, have to add this as a device to remap 898 */ 899 if ((pt = chk_dev(arcn->sb.st_dev, 1)) == NULL) 900 goto bad; 901 902 /* 903 * if we just have a truncated inode, we have to make sure that 904 * all future inodes that do not truncate (they have the 905 * truncation pattern of all 0's) continue to map to the same 906 * device number. We probably have already written inodes with 907 * this device number to the archive with the truncation 908 * pattern of all 0's. So we add the mapping for all 0's to the 909 * same device number. 910 */ 911 if (!trc_dev && (trunc_bits != 0)) { 912 if ((dpt = (DLIST *)malloc(sizeof(DLIST))) == NULL) 913 goto bad; 914 dpt->trunc_bits = 0; 915 dpt->dev = arcn->sb.st_dev; 916 dpt->fow = pt->list; 917 pt->list = dpt; 918 } 919 } 920 921 /* 922 * look for a device number not being used. We must watch for wrap 923 * around on lastdev (so we do not get stuck looking forever!) 924 */ 925 while (++lastdev > 0) { 926 if (chk_dev(lastdev, 0) != NULL) 927 continue; 928 /* 929 * found an unused value. If we have reached truncation point 930 * for this format we are hosed, so we give up. Otherwise we 931 * mark it as being used. 932 */ 933 if (((lastdev & ((dev_t)dev_mask)) != lastdev) || 934 (chk_dev(lastdev, 1) == NULL)) 935 goto bad; 936 break; 937 } 938 939 if ((lastdev <= 0) || ((dpt = (DLIST *)malloc(sizeof(DLIST))) == NULL)) 940 goto bad; 941 942 /* 943 * got a new device number, store it under this truncation pattern. 944 * change the device number this file is being stored with. 945 */ 946 dpt->trunc_bits = trunc_bits; 947 dpt->dev = lastdev; 948 dpt->fow = pt->list; 949 pt->list = dpt; 950 arcn->sb.st_dev = lastdev; 951 arcn->sb.st_ino = nino; 952 return(0); 953 954 bad: 955 paxwarn(1, "Unable to fix truncated inode/device field when storing %s", 956 arcn->name); 957 paxwarn(0, "Archive may create improper hard links when extracted"); 958 return(0); 959} 960 961/* 962 * directory access/mod time reset table routines (for directories READ by pax) 963 * 964 * The pax -t flag requires that access times of archive files to be the same 965 * before being read by pax. For regular files, access time is restored after 966 * the file has been copied. This database provides the same functionality for 967 * directories read during file tree traversal. Restoring directory access time 968 * is more complex than files since directories may be read several times until 969 * all the descendants in their subtree are visited by fts. Directory access 970 * and modification times are stored during the fts pre-order visit (done 971 * before any descendants in the subtree is visited) and restored after the 972 * fts post-order visit (after all the descendants have been visited). In the 973 * case of premature exit from a subtree (like from the effects of -n), any 974 * directory entries left in this database are reset during final cleanup 975 * operations of pax. Entries are hashed by inode number for fast lookup. 976 */ 977 978/* 979 * atdir_start() 980 * create the directory access time database for directories READ by pax. 981 * Return: 982 * 0 is created ok, -1 otherwise. 983 */ 984 985#ifdef __STDC__ 986int 987atdir_start(void) 988#else 989int 990atdir_start() 991#endif 992{ 993 if (atab != NULL) 994 return(0); 995 if ((atab = (ATDIR **)calloc(A_TAB_SZ, sizeof(ATDIR *))) == NULL) { 996 paxwarn(1,"Cannot allocate space for directory access time table"); 997 return(-1); 998 } 999 return(0); 1000} 1001 1002 1003/* 1004 * atdir_end() 1005 * walk through the directory access time table and reset the access time 1006 * of any directory who still has an entry left in the database. These 1007 * entries are for directories READ by pax 1008 */ 1009 1010#ifdef __STDC__ 1011void 1012atdir_end(void) 1013#else 1014void 1015atdir_end() 1016#endif 1017{ 1018 register ATDIR *pt; 1019 register int i; 1020 1021 if (atab == NULL) 1022 return; 1023 /* 1024 * for each non-empty hash table entry reset all the directories 1025 * chained there. 1026 */ 1027 for (i = 0; i < A_TAB_SZ; ++i) { 1028 if ((pt = atab[i]) == NULL) 1029 continue; 1030 /* 1031 * remember to force the times, set_ftime() looks at pmtime 1032 * and patime, which only applies to things CREATED by pax, 1033 * not read by pax. Read time reset is controlled by -t. 1034 */ 1035 for (; pt != NULL; pt = pt->fow) 1036 set_ftime(pt->name, pt->mtime, pt->atime, 1); 1037 } 1038} 1039 1040/* 1041 * add_atdir() 1042 * add a directory to the directory access time table. Table is hashed 1043 * and chained by inode number. This is for directories READ by pax 1044 */ 1045 1046#ifdef __STDC__ 1047void 1048add_atdir(char *fname, dev_t dev, ino_t ino, time_t mtime, time_t atime) 1049#else 1050void 1051add_atdir(fname, dev, ino, mtime, atime) 1052 char *fname; 1053 dev_t dev; 1054 ino_t ino; 1055 time_t mtime; 1056 time_t atime; 1057#endif 1058{ 1059 register ATDIR *pt; 1060 register u_int indx; 1061 1062 if (atab == NULL) 1063 return; 1064 1065 /* 1066 * make sure this directory is not already in the table, if so just 1067 * return (the older entry always has the correct time). The only 1068 * way this will happen is when the same subtree can be traversed by 1069 * different args to pax and the -n option is aborting fts out of a 1070 * subtree before all the post-order visits have been made). 1071 */ 1072 indx = ((unsigned)ino) % A_TAB_SZ; 1073 if ((pt = atab[indx]) != NULL) { 1074 while (pt != NULL) { 1075 if ((pt->ino == ino) && (pt->dev == dev)) 1076 break; 1077 pt = pt->fow; 1078 } 1079 1080 /* 1081 * oops, already there. Leave it alone. 1082 */ 1083 if (pt != NULL) 1084 return; 1085 } 1086 1087 /* 1088 * add it to the front of the hash chain 1089 */ 1090 if ((pt = (ATDIR *)malloc(sizeof(ATDIR))) != NULL) { 1091 if ((pt->name = strdup(fname)) != NULL) { 1092 pt->dev = dev; 1093 pt->ino = ino; 1094 pt->mtime = mtime; 1095 pt->atime = atime; 1096 pt->fow = atab[indx]; 1097 atab[indx] = pt; 1098 return; 1099 } 1100 (void)free((char *)pt); 1101 } 1102 1103 paxwarn(1, "Directory access time reset table ran out of memory"); 1104 return; 1105} 1106 1107/* 1108 * get_atdir() 1109 * look up a directory by inode and device number to obtain the access 1110 * and modification time you want to set to. If found, the modification 1111 * and access time parameters are set and the entry is removed from the 1112 * table (as it is no longer needed). These are for directories READ by 1113 * pax 1114 * Return: 1115 * 0 if found, -1 if not found. 1116 */ 1117 1118#ifdef __STDC__ 1119int 1120get_atdir(dev_t dev, ino_t ino, time_t *mtime, time_t *atime) 1121#else 1122int 1123get_atdir(dev, ino, mtime, atime) 1124 dev_t dev; 1125 ino_t ino; 1126 time_t *mtime; 1127 time_t *atime; 1128#endif 1129{ 1130 register ATDIR *pt; 1131 register ATDIR **ppt; 1132 register u_int indx; 1133 1134 if (atab == NULL) 1135 return(-1); 1136 /* 1137 * hash by inode and search the chain for an inode and device match 1138 */ 1139 indx = ((unsigned)ino) % A_TAB_SZ; 1140 if ((pt = atab[indx]) == NULL) 1141 return(-1); 1142 1143 ppt = &(atab[indx]); 1144 while (pt != NULL) { 1145 if ((pt->ino == ino) && (pt->dev == dev)) 1146 break; 1147 /* 1148 * no match, go to next one 1149 */ 1150 ppt = &(pt->fow); 1151 pt = pt->fow; 1152 } 1153 1154 /* 1155 * return if we did not find it. 1156 */ 1157 if (pt == NULL) 1158 return(-1); 1159 1160 /* 1161 * found it. return the times and remove the entry from the table. 1162 */ 1163 *ppt = pt->fow; 1164 *mtime = pt->mtime; 1165 *atime = pt->atime; 1166 (void)free((char *)pt->name); 1167 (void)free((char *)pt); 1168 return(0); 1169} 1170 1171/* 1172 * directory access mode and time storage routines (for directories CREATED 1173 * by pax). 1174 * 1175 * Pax requires that extracted directories, by default, have their access/mod 1176 * times and permissions set to the values specified in the archive. During the 1177 * actions of extracting (and creating the destination subtree during -rw copy) 1178 * directories extracted may be modified after being created. Even worse is 1179 * that these directories may have been created with file permissions which 1180 * prohibits any descendants of these directories from being extracted. When 1181 * directories are created by pax, access rights may be added to permit the 1182 * creation of files in their subtree. Every time pax creates a directory, the 1183 * times and file permissions specified by the archive are stored. After all 1184 * files have been extracted (or copied), these directories have their times 1185 * and file modes reset to the stored values. The directory info is restored in 1186 * reverse order as entries were added to the data file from root to leaf. To 1187 * restore atime properly, we must go backwards. The data file consists of 1188 * records with two parts, the file name followed by a DIRDATA trailer. The 1189 * fixed sized trailer contains the size of the name plus the off_t location in 1190 * the file. To restore we work backwards through the file reading the trailer 1191 * then the file name. 1192 */ 1193 1194/* 1195 * dir_start() 1196 * set up the directory time and file mode storage for directories CREATED 1197 * by pax. 1198 * Return: 1199 * 0 if ok, -1 otherwise 1200 */ 1201 1202#ifdef __STDC__ 1203int 1204dir_start(void) 1205#else 1206int 1207dir_start() 1208#endif 1209{ 1210 1211 if (dirfd != -1) 1212 return(0); 1213 1214 /* 1215 * unlink the file so it goes away at termination by itself 1216 */ 1217 memcpy(tempbase, _TFILE_BASE, sizeof(_TFILE_BASE)); 1218 if ((dirfd = mkstemp(tempfile)) >= 0) { 1219 (void)unlink(tempfile); 1220 return(0); 1221 } 1222 paxwarn(1, "Unable to create temporary file for directory times: %s", 1223 tempfile); 1224 return(-1); 1225} 1226 1227/* 1228 * add_dir() 1229 * add the mode and times for a newly CREATED directory 1230 * name is name of the directory, psb the stat buffer with the data in it, 1231 * frc_mode is a flag that says whether to force the setting of the mode 1232 * (ignoring the user set values for preserving file mode). Frc_mode is 1233 * for the case where we created a file and found that the resulting 1234 * directory was not writeable and the user asked for file modes to NOT 1235 * be preserved. (we have to preserve what was created by default, so we 1236 * have to force the setting at the end. this is stated explicitly in the 1237 * pax spec) 1238 */ 1239 1240#ifdef __STDC__ 1241void 1242add_dir(char *name, int nlen, struct stat *psb, int frc_mode) 1243#else 1244void 1245add_dir(name, nlen, psb, frc_mode) 1246 char *name; 1247 int nlen; 1248 struct stat *psb; 1249 int frc_mode; 1250#endif 1251{ 1252 DIRDATA dblk; 1253 1254 if (dirfd < 0) 1255 return; 1256 1257 /* 1258 * get current position (where file name will start) so we can store it 1259 * in the trailer 1260 */ 1261 if ((dblk.npos = lseek(dirfd, 0L, SEEK_CUR)) < 0) { 1262 paxwarn(1,"Unable to store mode and times for directory: %s",name); 1263 return; 1264 } 1265 1266 /* 1267 * write the file name followed by the trailer 1268 */ 1269 dblk.nlen = nlen + 1; 1270 dblk.mode = psb->st_mode & 0xffff; 1271 dblk.mtime = psb->st_mtime; 1272 dblk.atime = psb->st_atime; 1273 dblk.frc_mode = frc_mode; 1274 if ((write(dirfd, name, dblk.nlen) == dblk.nlen) && 1275 (write(dirfd, (char *)&dblk, sizeof(dblk)) == sizeof(dblk))) { 1276 ++dircnt; 1277 return; 1278 } 1279 1280 paxwarn(1,"Unable to store mode and times for created directory: %s",name); 1281 return; 1282} 1283 1284/* 1285 * proc_dir() 1286 * process all file modes and times stored for directories CREATED 1287 * by pax 1288 */ 1289 1290#ifdef __STDC__ 1291void 1292proc_dir(void) 1293#else 1294void 1295proc_dir() 1296#endif 1297{ 1298 char name[PAXPATHLEN+1]; 1299 DIRDATA dblk; 1300 u_long cnt; 1301 1302 if (dirfd < 0) 1303 return; 1304 /* 1305 * read backwards through the file and process each directory 1306 */ 1307 for (cnt = 0; cnt < dircnt; ++cnt) { 1308 /* 1309 * read the trailer, then the file name, if this fails 1310 * just give up. 1311 */ 1312 if (lseek(dirfd, -((off_t)sizeof(dblk)), SEEK_CUR) < 0) 1313 break; 1314 if (read(dirfd,(char *)&dblk, sizeof(dblk)) != sizeof(dblk)) 1315 break; 1316 if (lseek(dirfd, dblk.npos, SEEK_SET) < 0) 1317 break; 1318 if (read(dirfd, name, dblk.nlen) != dblk.nlen) 1319 break; 1320 if (lseek(dirfd, dblk.npos, SEEK_SET) < 0) 1321 break; 1322 1323 /* 1324 * frc_mode set, make sure we set the file modes even if 1325 * the user didn't ask for it (see file_subs.c for more info) 1326 */ 1327 if (pmode || dblk.frc_mode) 1328 set_pmode(name, dblk.mode); 1329 if (patime || pmtime) 1330 set_ftime(name, dblk.mtime, dblk.atime, 0); 1331 } 1332 1333 (void)close(dirfd); 1334 dirfd = -1; 1335 if (cnt != dircnt) 1336 paxwarn(1,"Unable to set mode and times for created directories"); 1337 return; 1338} 1339 1340/* 1341 * database independent routines 1342 */ 1343 1344/* 1345 * st_hash() 1346 * hashes filenames to a u_int for hashing into a table. Looks at the tail 1347 * end of file, as this provides far better distribution than any other 1348 * part of the name. For performance reasons we only care about the last 1349 * MAXKEYLEN chars (should be at LEAST large enough to pick off the file 1350 * name). Was tested on 500,000 name file tree traversal from the root 1351 * and gave almost a perfectly uniform distribution of keys when used with 1352 * prime sized tables (MAXKEYLEN was 128 in test). Hashes (sizeof int) 1353 * chars at a time and pads with 0 for last addition. 1354 * Return: 1355 * the hash value of the string MOD (%) the table size. 1356 */ 1357 1358#ifdef __STDC__ 1359u_int 1360st_hash(char *name, int len, int tabsz) 1361#else 1362u_int 1363st_hash(name, len, tabsz) 1364 char *name; 1365 int len; 1366 int tabsz; 1367#endif 1368{ 1369 register char *pt; 1370 register char *dest; 1371 register char *end; 1372 register int i; 1373 register u_int key = 0; 1374 register int steps; 1375 register int res; 1376 u_int val; 1377 1378 /* 1379 * only look at the tail up to MAXKEYLEN, we do not need to waste 1380 * time here (remember these are pathnames, the tail is what will 1381 * spread out the keys) 1382 */ 1383 if (len > MAXKEYLEN) { 1384 pt = &(name[len - MAXKEYLEN]); 1385 len = MAXKEYLEN; 1386 } else 1387 pt = name; 1388 1389 /* 1390 * calculate the number of u_int size steps in the string and if 1391 * there is a runt to deal with 1392 */ 1393 steps = len/sizeof(u_int); 1394 res = len % sizeof(u_int); 1395 1396 /* 1397 * add up the value of the string in unsigned integer sized pieces 1398 * too bad we cannot have unsigned int aligned strings, then we 1399 * could avoid the expensive copy. 1400 */ 1401 for (i = 0; i < steps; ++i) { 1402 end = pt + sizeof(u_int); 1403 dest = (char *)&val; 1404 while (pt < end) 1405 *dest++ = *pt++; 1406 key += val; 1407 } 1408 1409 /* 1410 * add in the runt padded with zero to the right 1411 */ 1412 if (res) { 1413 val = 0; 1414 end = pt + res; 1415 dest = (char *)&val; 1416 while (pt < end) 1417 *dest++ = *pt++; 1418 key += val; 1419 } 1420 1421 /* 1422 * return the result mod the table size 1423 */ 1424 return(key % tabsz); 1425} 1426