1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
|
/* $OpenBSD: tables.h,v 1.15 2015/03/09 04:23:29 guenther Exp $ */
/* $NetBSD: tables.h,v 1.3 1995/03/21 09:07:47 cgd Exp $ */
/*-
* Copyright (c) 1992 Keith Muller.
* Copyright (c) 1992, 1993
* The Regents of the University of California. All rights reserved.
*
* This code is derived from software contributed to Berkeley by
* Keith Muller of the University of California, San Diego.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* 3. Neither the name of the University nor the names of its contributors
* may be used to endorse or promote products derived from this software
* without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*
* @(#)tables.h 8.1 (Berkeley) 5/31/93
*/
/*
* data structures and constants used by the different databases kept by pax
*/
/*
* Hash Table Sizes MUST BE PRIME, if set too small performance suffers.
* Probably safe to expect 500000 inodes per tape. Assuming good key
* distribution (inodes) chains of under 50 long (worst case) is ok.
*/
#define L_TAB_SZ 2503 /* hard link hash table size */
#define F_TAB_SZ 50503 /* file time hash table size */
#define N_TAB_SZ 541 /* interactive rename hash table */
#define D_TAB_SZ 317 /* unique device mapping table */
#define A_TAB_SZ 317 /* ftree dir access time reset table */
#define SL_TAB_SZ 317 /* escape symlink tables */
#define MAXKEYLEN 64 /* max number of chars for hash */
#define DIRP_SIZE 64 /* initial size of created dir table */
/*
* file hard link structure (hashed by dev/ino and chained) used to find the
* hard links in a file system or with some archive formats (cpio)
*/
typedef struct hrdlnk {
ino_t ino; /* files inode number */
char *name; /* name of first file seen with this ino/dev */
dev_t dev; /* files device number */
u_long nlink; /* expected link count */
struct hrdlnk *fow;
} HRDLNK;
/*
* Archive write update file time table (the -u, -C flag), hashed by filename.
* Filenames are stored in a scratch file at seek offset into the file. The
* file time (mod time) and the file name length (for a quick check) are
* stored in a hash table node. We were forced to use a scratch file because
* with -u, the mtime for every node in the archive must always be available
* to compare against (and this data can get REALLY large with big archives).
* By being careful to read only when we have a good chance of a match, the
* performance loss is not measurable (and the size of the archive we can
* handle is greatly increased).
*/
typedef struct ftm {
off_t seek; /* location in scratch file */
time_t mtime; /* files last modification time */
struct ftm *fow;
int namelen; /* file name length */
} FTM;
/*
* Interactive rename table (-i flag), hashed by orig filename.
* We assume this will not be a large table as this mapping data can only be
* obtained through interactive input by the user. Nobody is going to type in
* changes for 500000 files? We use chaining to resolve collisions.
*/
typedef struct namt {
char *oname; /* old name */
char *nname; /* new name typed in by the user */
struct namt *fow;
} NAMT;
/*
* Unique device mapping tables. Some protocols (e.g. cpio) require that the
* <c_dev,c_ino> pair will uniquely identify a file in an archive unless they
* are links to the same file. Appending to archives can break this. For those
* protocols that have this requirement we map c_dev to a unique value not seen
* in the archive when we append. We also try to handle inode truncation with
* this table. (When the inode field in the archive header are too small, we
* remap the dev on writes to remove accidental collisions).
*
* The list is hashed by device number using chain collision resolution. Off of
* each DEVT are linked the various remaps for this device based on those bits
* in the inode which were truncated. For example if we are just remapping to
* avoid a device number during an update append, off the DEVT we would have
* only a single DLIST that has a truncation id of 0 (no inode bits were
* stripped for this device so far). When we spot inode truncation we create
* a new mapping based on the set of bits in the inode which were stripped off.
* so if the top four bits of the inode are stripped and they have a pattern of
* 0110...... (where . are those bits not truncated) we would have a mapping
* assigned for all inodes that has the same 0110.... pattern (with this dev
* number of course). This keeps the mapping sparse and should be able to store
* close to the limit of files which can be represented by the optimal
* combination of dev and inode bits, and without creating a fouled up archive.
* Note we also remap truncated devs in the same way (an exercise for the
* dedicated reader; always wanted to say that...:)
*/
typedef struct devt {
dev_t dev; /* the orig device number we now have to map */
struct devt *fow; /* new device map list */
struct dlist *list; /* map list based on inode truncation bits */
} DEVT;
typedef struct dlist {
ino_t trunc_bits; /* truncation pattern for a specific map */
dev_t dev; /* the new device id we use */
struct dlist *fow;
} DLIST;
/*
* ftree directory access time reset table. When we are done with a
* subtree we reset the access and mod time of the directory when the tflag is
* set. Not really explicitly specified in the pax spec, but easy and fast to
* do (and this may have even been intended in the spec, it is not clear).
* table is hashed by inode with chaining.
*/
typedef struct atdir {
struct file_times ft;
struct atdir *fow;
} ATDIR;
/*
* created directory time and mode storage entry. After pax is finished during
* extraction or copy, we must reset directory access modes and times that
* may have been modified after creation (they no longer have the specified
* times and/or modes). We must reset time in the reverse order of creation,
* because entries are added from the top of the file tree to the bottom.
* We MUST reset times from leaf to root (it will not work the other
* direction).
*/
typedef struct dirdata {
struct file_times ft;
u_int16_t mode; /* file mode to restore */
u_int16_t frc_mode; /* do we force mode settings? */
} DIRDATA;
|
