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