Commit | Line | Data |
---|---|---|
805e021f CE |
1 | /* |
2 | * CMUCS AFStools | |
3 | * dumpscan - routines for scanning and manipulating AFS volume dumps | |
4 | * | |
5 | * Copyright (c) 1998, 2001, 2004 Carnegie Mellon University | |
6 | * All Rights Reserved. | |
7 | * | |
8 | * Permission to use, copy, modify and distribute this software and its | |
9 | * documentation is hereby granted, provided that both the copyright | |
10 | * notice and this permission notice appear in all copies of the | |
11 | * software, derivative works or modified versions, and any portions | |
12 | * thereof, and that both notices appear in supporting documentation. | |
13 | * | |
14 | * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS" | |
15 | * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR | |
16 | * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE. | |
17 | * | |
18 | * Carnegie Mellon requests users of this software to return to | |
19 | * | |
20 | * Software Distribution Coordinator or Software_Distribution@CS.CMU.EDU | |
21 | * School of Computer Science | |
22 | * Carnegie Mellon University | |
23 | * Pittsburgh PA 15213-3890 | |
24 | * | |
25 | * any improvements or extensions that they make and grant Carnegie Mellon | |
26 | * the rights to redistribute these changes. | |
27 | */ | |
28 | ||
29 | /* directory.c - AFS directory parsing and generation */ | |
30 | /* See the end of this file for a description of the directory format */ | |
31 | ||
32 | #include <errno.h> | |
33 | #include <sys/types.h> | |
34 | #include <stdlib.h> | |
35 | #include <string.h> | |
36 | #include <netinet/in.h> | |
37 | ||
38 | #include "dumpscan.h" | |
39 | #include "dumpscan_errs.h" | |
40 | #include "xf_errs.h" | |
41 | #include "dumpfmt.h" | |
42 | #include "internal.h" | |
43 | ||
44 | #include <afs/dir.h> | |
45 | ||
46 | struct dir_state { | |
47 | unsigned char **dirpages; | |
48 | int npages; | |
49 | ||
50 | afs_dir_header *dh; /* Directory header */ | |
51 | afs_dir_page *page; /* Current page */ | |
52 | int pageno; /* Current page # */ | |
53 | int entno; /* Current (next avail) entry # */ | |
54 | int used; /* # entries used in this page */ | |
55 | }; | |
56 | ||
57 | static afs_dir_page page; | |
58 | ||
59 | #define bmbyte(bm,x) bm[(x)>>3] | |
60 | #define bmbit(x) (1 << ((x) & 7)) | |
61 | ||
62 | #define allocbit(x) (bmbyte(page.header.freebitmap,x) & bmbit(x)) | |
63 | #define setallocbit(bm,x) (bmbyte(bm,x) |= bmbit(x)) | |
64 | ||
65 | #define DPHE (DHE + 1) | |
66 | ||
67 | /* Hash function used in AFS directories. */ | |
68 | static int namehash(char *name, int buckets, int seed) | |
69 | { | |
70 | int hval = seed, tval; | |
71 | ||
72 | while (*name) hval = (hval * 173) + *name++; | |
73 | tval = hval & (buckets - 1); | |
74 | return tval ? hval < 0 ? buckets - tval : tval : 0; | |
75 | } | |
76 | ||
77 | #if 0 | |
78 | static void fixup(char *name, int l) | |
79 | { | |
80 | name += 16; | |
81 | l -= 15; | |
82 | ||
83 | while (l-- > 0) { | |
84 | name[0] = name[4]; | |
85 | name++; | |
86 | } | |
87 | } | |
88 | #endif | |
89 | ||
90 | afs_uint32 parse_directory(XFILE *X, dump_parser *p, afs_vnode *v, | |
91 | afs_uint32 size, int toeof) | |
92 | { | |
93 | afs_dir_entry de; | |
94 | int pgno, i, l, n; | |
95 | afs_int32 r; | |
96 | dt_uint64 where; | |
97 | ||
98 | if (p->print_flags & DSPRINT_DIR) { | |
99 | printf(" VNode Uniqifier Name\n"); | |
100 | printf(" ========== ========== ==============================\n"); | |
101 | } | |
102 | if ((p->flags & DSFLAG_SEEK) && (r = xftell(X, &where))) return r; | |
103 | for (pgno = 0; toeof || size; pgno++, size -= (toeof ? 0 : AFS_PAGESIZE)) { | |
104 | if ((p->flags & DSFLAG_SEEK) && (r = xfseek(X, &where))) return r; | |
105 | if ((r = xfread(X, &page, AFS_PAGESIZE))) { | |
106 | if (toeof && r == ERROR_XFILE_EOF) break; | |
107 | return r; | |
108 | } | |
109 | if ((p->flags & DSFLAG_SEEK) && (r = xftell(X, &where))) return r; | |
110 | if (page.header.tag != htons(1234)) { | |
111 | if (p->cb_error) | |
112 | (p->cb_error)(DSERR_MAGIC, 1, p->err_refcon, | |
113 | "Invalid page tag (%d) in page %d", | |
114 | ntohs(page.header.tag), pgno); | |
115 | return DSERR_MAGIC; | |
116 | } | |
117 | for (i = (pgno ? 1 : DPHE); i < EPP; i++) { | |
118 | if (!allocbit(i)) continue; | |
119 | if (page.entry[i].flag != FFIRST) { | |
120 | if (p->cb_error) | |
121 | (p->cb_error)(DSERR_MAGIC, 0, p->err_refcon, | |
122 | "Invalid entry flag %d in entry %d/%d; skipping...", | |
123 | page.entry[i].flag, pgno, i); | |
124 | continue; | |
125 | } | |
126 | n = (EPP - i - 1) * 32 + 16; | |
127 | for (l = 0; n && page.entry[i].name[l]; l++, n--); | |
128 | if (page.entry[i].name[l]) { | |
129 | if (p->cb_error) | |
130 | (p->cb_error)(DSERR_FMT, 0, p->err_refcon, | |
131 | "Filename too long in entry %d/%d; skipping page", | |
132 | pgno, i); | |
133 | break; | |
134 | } | |
135 | /* fixup(page.entry[i].name, l); */ | |
136 | if (pgno) de.slot = i - 1 + (pgno - 1) * (EPP - 1) + (EPP - DPHE); | |
137 | else de.slot = i - DPHE; | |
138 | de.name = page.entry[i].name; | |
139 | de.vnode = ntohl(page.entry[i].vnode); | |
140 | de.uniq = ntohl(page.entry[i].vunique); | |
141 | if (p->print_flags & DSPRINT_DIR) | |
142 | printf(" %10d %10d %s\n", de.vnode, de.uniq, de.name); | |
143 | if (p->cb_dirent) { | |
144 | r = (p->cb_dirent)(v, &de, X, p->refcon); | |
145 | } | |
146 | if (p->cb_dirent && (r = (p->cb_dirent)(v, &de, X, p->refcon))) | |
147 | return r; | |
148 | i += ((l + 16) >> 5); | |
149 | } | |
150 | } | |
151 | if ((p->flags & DSFLAG_SEEK) && (r = xfseek(X, &where))) return r; | |
152 | return 0; | |
153 | } | |
154 | ||
155 | ||
156 | afs_uint32 ParseDirectory(XFILE *X, dump_parser *p, afs_uint32 size, int toeof) | |
157 | { | |
158 | afs_uint32 r; | |
159 | ||
160 | r = parse_directory(X, p, 0, size, toeof); | |
161 | return r; | |
162 | } | |
163 | ||
164 | ||
165 | typedef struct { | |
166 | char **name; | |
167 | afs_uint32 *vnode; | |
168 | afs_uint32 *vuniq; | |
169 | } dirlookup_stat; | |
170 | ||
171 | ||
172 | static afs_uint32 dirlookup_cb(afs_vnode *v, afs_dir_entry *de, | |
173 | XFILE *X, void *refcon) | |
174 | { | |
175 | dirlookup_stat *s = (dirlookup_stat *)refcon; | |
176 | ||
177 | if (s->name && s->name[0]) { /* Search by filename */ | |
178 | if (strcmp(de->name, s->name[0])) return 0; /* Not it! */ | |
179 | if (s->vnode) s->vnode[0] = de->vnode; | |
180 | if (s->vuniq) s->vuniq[0] = de->uniq; | |
181 | } else if (s->vnode) { /* Search by vnode */ | |
182 | if (de->vnode != s->vnode[0]) return 0; /* Not it! */ | |
183 | if (s->name) { | |
184 | s->name[0] = strdup(de->name); | |
185 | if (!s->name[0]) return ENOMEM; | |
186 | } | |
187 | if (s->vuniq) s->vuniq[0] = de->uniq; | |
188 | } | |
189 | return DSERR_DONE; | |
190 | } | |
191 | ||
192 | ||
193 | /* Look up an entry in a directory, by name or vnode. | |
194 | * If *name is NULL, we are looking up by vnode. | |
195 | * Otherwise, we are looking for a filename. | |
196 | * In any event, any of name, vnode, vuniq that are | |
197 | * neither NULL nor the search key are filled in on | |
198 | * success. | |
199 | * | |
200 | * Call this with X pointing to the start of the directory, | |
201 | * and size set to the length of the directory. | |
202 | * Returns 0 on success, whether or not the entry is found. | |
203 | */ | |
204 | afs_uint32 DirectoryLookup(XFILE *X, dump_parser *p, afs_uint32 size, | |
205 | char **name, afs_uint32 *vnode, afs_uint32 *vuniq) | |
206 | { | |
207 | dump_parser my_p; | |
208 | dirlookup_stat my_s; | |
209 | afs_uint32 r; | |
210 | ||
211 | memset(&my_s, 0, sizeof(my_s)); | |
212 | my_s.name = name; | |
213 | my_s.vnode = vnode; | |
214 | my_s.vuniq = vuniq; | |
215 | ||
216 | memset(&my_p, 0, sizeof(my_p)); | |
217 | my_p.refcon = (void *)&my_s; | |
218 | my_p.err_refcon = p->err_refcon; | |
219 | my_p.cb_error = p->cb_error; | |
220 | my_p.cb_dirent = dirlookup_cb; | |
221 | ||
222 | r = parse_directory(X, &my_p, 0, size, 0); | |
223 | if (!r) r = DSERR_DONE; | |
224 | return handle_return(r, X, 0, p); | |
225 | } | |
226 | ||
227 | ||
228 | static int allocpage(struct dir_state *ds, int reserve) | |
229 | { | |
230 | unsigned char **dirpages; | |
231 | int i; | |
232 | ||
233 | dirpages = malloc((ds->npages + 1) * sizeof(unsigned char *)); | |
234 | if (!dirpages) return ENOMEM; | |
235 | if (ds->dirpages) { | |
236 | memcpy(dirpages, ds->dirpages, ds->npages * sizeof(unsigned char *)); | |
237 | free(ds->dirpages); | |
238 | } | |
239 | ds->dirpages = dirpages; | |
240 | ||
241 | ds->dirpages[ds->npages] = malloc(AFS_PAGESIZE); | |
242 | if (!ds->dirpages[ds->npages]) return ENOMEM; | |
243 | ds->pageno = ds->npages++; | |
244 | ||
245 | ds->page = (afs_dir_page *)(ds->dirpages[ds->pageno]); | |
246 | memset(ds->page, 0, AFS_PAGESIZE); | |
247 | ds->page->header.tag = htons(AFS_DIR_MAGIC); | |
248 | ds->entno = ds->used = reserve; | |
249 | for (i = 0; i < reserve; i++) | |
250 | setallocbit(ds->page->header.freebitmap, i); | |
251 | return 0; | |
252 | } | |
253 | ||
254 | ||
255 | afs_uint32 Dir_Init(struct dir_state **dsp) | |
256 | { | |
257 | afs_uint32 r; | |
258 | ||
259 | *dsp = calloc(1, sizeof(struct dir_state)); | |
260 | if (!*dsp) return ENOMEM; | |
261 | if ((r = allocpage(*dsp, DPHE))) return r; | |
262 | (*dsp)->dh = (afs_dir_header *)((*dsp)->page); | |
263 | return 0; | |
264 | } | |
265 | ||
266 | ||
267 | afs_uint32 Dir_AddEntry(struct dir_state *ds, char *name, | |
268 | afs_uint32 vnode, afs_uint32 unique) | |
269 | { | |
270 | afs_uint32 r; | |
271 | int l = strlen(name) + 1; | |
272 | int ne = l > 16 ? 1 + ((l - 16) / 32) + !!((l - 16) % 32) : 1; | |
273 | int hash = namehash(name, NHASHENT, 0); | |
274 | ||
275 | if (ne > EPP - 1) return ENAMETOOLONG; | |
276 | if (ds->entno + ne > EPP) { | |
277 | if (ds->pageno < 128) ds->dh->allomap[ds->pageno] = ds->used; | |
278 | if ((r = allocpage(ds, 1))) return r; | |
279 | } | |
280 | ds->page->entry[ds->entno].flag = FFIRST; | |
281 | ds->page->entry[ds->entno].next = ds->dh->hash[hash]; | |
282 | ds->page->entry[ds->entno].vnode = htonl(vnode); | |
283 | ds->page->entry[ds->entno].vunique = htonl(unique); | |
284 | strcpy(ds->page->entry[ds->entno].name, name); | |
285 | ds->dh->hash[hash] = htons((ds->pageno * EPP) + ds->entno); | |
286 | while (ne--) { | |
287 | setallocbit(ds->page->header.freebitmap, ds->entno); | |
288 | ds->used++; | |
289 | ds->entno++; | |
290 | } | |
291 | return 0; | |
292 | } | |
293 | ||
294 | ||
295 | afs_uint32 Dir_Finalize(struct dir_state *ds) | |
296 | { | |
297 | int pages = ds->pageno + 1; | |
298 | ||
299 | if (ds->pageno < 128) ds->dh->allomap[ds->pageno] = ds->used; | |
300 | ds->dh->pagehdr.pgcount = htons(pages); | |
301 | return 0; | |
302 | } | |
303 | ||
304 | ||
305 | afs_uint32 Dir_EmitData(struct dir_state *ds, XFILE *X, int dotag) | |
306 | { | |
307 | afs_uint32 r, size; | |
308 | int i; | |
309 | ||
310 | size = ds->npages * AFS_PAGESIZE; | |
311 | if (dotag && (r = WriteTagInt32(X, VTAG_DATA, size))) return r; | |
312 | for (i = 0; i < ds->npages; i++) { | |
313 | if ((r = xfwrite(X, ds->dirpages[i], AFS_PAGESIZE))) return r; | |
314 | } | |
315 | return 0; | |
316 | } | |
317 | ||
318 | ||
319 | afs_uint32 Dir_Free(struct dir_state *ds) | |
320 | { | |
321 | int i; | |
322 | ||
323 | for (i = 0; i < ds->npages; i++) | |
324 | free(ds->dirpages[i]); | |
325 | free(ds->dirpages); | |
326 | free(ds); | |
327 | return 0; | |
328 | } | |
329 | ||
330 | ||
331 | /* AFS directory format: | |
332 | * AFS directories are stored in volume dumps in exactly the same format | |
333 | * that is used on disk, which makes them relatively easy to dump and restore, | |
334 | * but means we have to do some work to interpret them. | |
335 | * | |
336 | * The ACL for a directory is stored on disk in the last part of a "large" | |
337 | * (directory) vnode. This part of the vnode, which has fixed size | |
338 | * SIZEOF_LARGEDISKVNODE - SIZEOF_SMALLDISKVNODE, is copied directly into | |
339 | * the dump file with a tag of 'A' (VTAG_ACL). The structure of this | |
340 | * section is described in <afs/acl.h>. | |
341 | * | |
342 | * The name-to-vnode mappings are also stored exactly as they appear on | |
343 | * disk, using the file data ('f') attribute. As usual, this attribute | |
344 | * consists of a 32-bit number containing the size, immediately followed | |
345 | * by the data itself. The interesting structures and constants are | |
346 | * defined in <afs/dir.h> | |
347 | * | |
348 | * A directory consists of one or more 'pages', each of which is 2K | |
349 | * (AFS_PAGESIZE). Each page contains EPP (currently 64) 'entries', each | |
350 | * of which is 32 bytes. The first page begins with a DirHeader, which | |
351 | * is DHE entries long, and includes a PageHeader. All other pages begin | |
352 | * with just a PageHeader, which is 1 entry long. Every other entry is | |
353 | * a DirEntry, a DirXEntry (name extension), or unused. | |
354 | * | |
355 | * A Page Header contains the following elements: | |
356 | * - pgcount contains a count of the number of pages in the directory, | |
357 | * if the directory is new-style (>128 pages), or 0 if it is | |
358 | * old-style. This field is meaningful only in the Dir Header. | |
359 | * - tag a magic number, which must be 1234 | |
360 | * - freecount apparently unused | |
361 | * - freebitmap A bitmap of free entries. Each byte corresponds to 8 | |
362 | * entries, with the least significant bit referring to the | |
363 | * first of those. Each bit is set iff the corresponding | |
364 | * entry is allocated. Entries used by the page and dir | |
365 | * headers are considered allocated. | |
366 | * | |
367 | * A Dir Header consists of a Page Header, followed by an allocation map | |
368 | * and hash table. The allocation map contains one byte for each of the | |
369 | * first 128 pages; that byte contains the number of entries in that page | |
370 | * that are allocated. Every page that actually exists has at peast one | |
371 | * entry allocated (the Page Header); if a byte in this map is 0, it means | |
372 | * that the page does not yet exist. | |
373 | * | |
374 | * Each bucket in the hash table is a linked list, using 'blob numbers' | |
375 | * as pointers. A blob number is defined as (page# * EPP) + entry#. | |
376 | * The head of each chain is kept in the hash table, and the next pointers | |
377 | * are kept in the 'next' entry of each directory. | |
378 | * | |
379 | * Directory entries themselves contain the following elements: | |
380 | * - flag Set to FFIRST iff this is the first blob in an entry | |
381 | * (otherwise it will be a name continuation). This is | |
382 | * probably not reliable. | |
383 | * - length Unused | |
384 | * - next Pointer to the next element in this hash chain | |
385 | * - fid FileID (vnode and uniquifier) | |
386 | * - name Filename (null-terminated) | |
387 | */ |