Commit | Line | Data |
---|---|---|
79aa58f4 KM |
1 | /*- |
2 | * Copyright (c) 1992 Keith Muller. | |
f547d164 KB |
3 | * Copyright (c) 1992, 1993 |
4 | * The Regents of the University of California. All rights reserved. | |
79aa58f4 KM |
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 | * | |
f547d164 | 11 | * @(#)tables.h 8.1 (Berkeley) %G% |
79aa58f4 KM |
12 | */ |
13 | ||
14 | /* | |
15 | * data structures and constants used by the different databases kept by pax | |
16 | */ | |
17 | ||
18 | /* | |
19 | * Hash Table Sizes MUST BE PRIME, if set too small performance suffers. | |
20 | * Probably safe to expect 500000 inodes per tape. Assuming good key | |
21 | * distribution (inodes) chains of under 50 long (worse case) is ok. | |
22 | */ | |
23 | #define L_TAB_SZ 2503 /* hard link hash table size */ | |
24 | #define F_TAB_SZ 50503 /* file time hash table size */ | |
25 | #define N_TAB_SZ 541 /* interactive rename hash table */ | |
26 | #define D_TAB_SZ 317 /* unique device mapping table */ | |
27 | #define A_TAB_SZ 317 /* ftree dir access time reset table */ | |
28 | #define MAXKEYLEN 64 /* max number of chars for hash */ | |
29 | ||
30 | /* | |
31 | * file hard link structure (hashed by dev/ino and chained) used to find the | |
32 | * hard links in a file system or with some archive formats (cpio) | |
33 | */ | |
34 | typedef struct hrdlnk { | |
35 | char *name; /* name of first file seen with this ino/dev */ | |
36 | dev_t dev; /* files device number */ | |
37 | ino_t ino; /* files inode number */ | |
38 | u_long nlink; /* expected link count */ | |
39 | struct hrdlnk *fow; | |
40 | } HRDLNK; | |
41 | ||
42 | /* | |
43 | * Archive write update file time table (the -u, -C flag), hashed by filename. | |
44 | * Filenames are stored in a scratch file at seek offset into the file. The | |
45 | * file time (mod time) and the file name length (for a quick check) are | |
46 | * stored in a hash table node. We were forced to use a scratch file because | |
47 | * with -u, the mtime for every node in the archive must always be available | |
48 | * to compare against (and this data can get REALLY large with big archives). | |
49 | * By being careful to read only when we have a good chance of a match, the | |
50 | * performance loss is not measurable (and the size of the archive we can | |
51 | * handle is greatly increased). | |
52 | */ | |
53 | typedef struct ftm { | |
54 | int namelen; /* file name length */ | |
55 | time_t mtime; /* files last modification time */ | |
56 | off_t seek; /* loacation in scratch file */ | |
57 | struct ftm *fow; | |
58 | } FTM; | |
59 | ||
60 | /* | |
61 | * Interactive rename table (-i flag), hashed by orig filename. | |
62 | * We assume this will not be a large table as this mapping data can only be | |
63 | * obtained through interactive input by the user. Nobody is going to type in | |
64 | * changes for 500000 files? We use chaining to resolve collisions. | |
65 | */ | |
66 | ||
67 | typedef struct namt { | |
68 | char *oname; /* old name */ | |
69 | char *nname; /* new name typed in by the user */ | |
70 | struct namt *fow; | |
71 | } NAMT; | |
72 | ||
73 | /* | |
74 | * Unique device mapping tables. Some protocols (e.g. cpio) require that the | |
75 | * <c_dev,c_ino> pair will uniquely identify a file in an archive unless they | |
76 | * are links to the same file. Appending to archives can break this. For those | |
77 | * protocols that have this requirement we map c_dev to a unique value not seen | |
78 | * in the archive when we append. We also try to handle inode truncation with | |
79 | * this table. (When the inode field in the archive header are too small, we | |
80 | * remap the dev on writes to remove accidental collisions). | |
81 | * | |
82 | * The list is hashed by device number using chain collision resolution. Off of | |
83 | * each DEVT are linked the various remaps for this device based on those bits | |
84 | * in the inode which were truncated. For example if we are just remapping to | |
85 | * avoid a device number during an update append, off the DEVT we would have | |
86 | * only a single DLIST that has a truncation id of 0 (no inode bits were | |
87 | * stripped for this device so far). When we spot inode truncation we create | |
88 | * a new mapping based on the set of bits in the inode which were stripped off. | |
89 | * so if the top four bits of the inode are stripped and they have a pattern of | |
90 | * 0110...... (where . are those bits not truncated) we would have a mapping | |
91 | * assigned for all inodes that has the same 0110.... pattern (with this dev | |
92 | * number of course). This keeps the mapping sparse and should be able to store | |
93 | * close to the limit of files which can be represented by the optimal | |
94 | * combination of dev and inode bits, and without creating a fouled up archive. | |
95 | * Note we also remap truncated devs in the same way (an exercise for the | |
96 | * dedicated reader; always wanted to say that...:) | |
97 | */ | |
98 | ||
99 | typedef struct devt { | |
100 | dev_t dev; /* the orig device number we now have to map */ | |
101 | struct devt *fow; /* new device map list */ | |
102 | struct dlist *list; /* map list based on inode truncation bits */ | |
103 | } DEVT; | |
104 | ||
105 | typedef struct dlist { | |
106 | ino_t trunc_bits; /* truncation pattern for a specific map */ | |
107 | dev_t dev; /* the new device id we use */ | |
108 | struct dlist *fow; | |
109 | } DLIST; | |
110 | ||
111 | /* | |
112 | * ftree directory access time reset table. When we are done with with a | |
113 | * subtree we reset the access and mod time of the directory when the tflag is | |
114 | * set. Not really explicitly specified in the pax spec, but easy and fast to | |
115 | * do (and this may have even been intended in the spec, it is not clear). | |
116 | * table is hashed by inode with chaining. | |
117 | */ | |
118 | ||
119 | typedef struct atdir { | |
120 | char *name; /* name of directory to reset */ | |
121 | dev_t dev; /* dev and inode for fast lookup */ | |
122 | ino_t ino; | |
123 | time_t mtime; /* access and mod time to reset to */ | |
124 | time_t atime; | |
125 | struct atdir *fow; | |
126 | } ATDIR; | |
127 | ||
128 | /* | |
129 | * created directory time and mode storage entry. After pax is finished during | |
130 | * extraction or copy, we must reset directory access modes and times that | |
131 | * may have been modified after creation (they no longer have the specified | |
132 | * times and/or modes). We must reset time in the reverse order of creation, | |
133 | * because entries are added from the top of the file tree to the bottom. | |
134 | * We MUST reset times from leaf to root (it will not work the other | |
135 | * direction). Entries are recorded into a spool file to make reverse | |
136 | * reading faster. | |
137 | */ | |
138 | ||
139 | typedef struct dirdata { | |
140 | int nlen; /* length of the directory name (includes \0) */ | |
141 | off_t npos; /* position in file where this dir name starts */ | |
142 | mode_t mode; /* file mode to restore */ | |
143 | time_t mtime; /* mtime to set */ | |
144 | time_t atime; /* atime to set */ | |
145 | int frc_mode; /* do we force mode settings? */ | |
146 | } DIRDATA; |