3 * dumpscan - routines for scanning and manipulating AFS volume dumps
5 * Copyright (c) 1998, 2001, 2004 Carnegie Mellon University
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.
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.
18 * Carnegie Mellon requests users of this software to return to
20 * Software Distribution Coordinator or Software_Distribution@CS.CMU.EDU
21 * School of Computer Science
22 * Carnegie Mellon University
23 * Pittsburgh PA 15213-3890
25 * any improvements or extensions that they make and grant Carnegie Mellon
26 * the rights to redistribute these changes.
29 /* directory.c - AFS directory parsing and generation */
30 /* See the end of this file for a description of the directory format */
33 #include <sys/types.h>
36 #include <netinet/in.h>
39 #include "dumpscan_errs.h"
47 unsigned char **dirpages
;
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 */
57 static afs_dir_page page
;
59 #define bmbyte(bm,x) bm[(x)>>3]
60 #define bmbit(x) (1 << ((x) & 7))
62 #define allocbit(x) (bmbyte(page.header.freebitmap,x) & bmbit(x))
63 #define setallocbit(bm,x) (bmbyte(bm,x) |= bmbit(x))
65 #define DPHE (DHE + 1)
67 /* Hash function used in AFS directories. */
68 static int namehash(char *name
, int buckets
, int seed
)
70 int hval
= seed
, tval
;
72 while (*name
) hval
= (hval
* 173) + *name
++;
73 tval
= hval
& (buckets
- 1);
74 return tval
? hval
< 0 ? buckets
- tval
: tval
: 0;
78 static void fixup(char *name
, int l
)
90 afs_uint32
parse_directory(XFILE
*X
, dump_parser
*p
, afs_vnode
*v
,
91 afs_uint32 size
, int toeof
)
98 if (p
->print_flags
& DSPRINT_DIR
) {
99 printf(" VNode Uniqifier Name\n");
100 printf(" ========== ========== ==============================\n");
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;
109 if ((p
->flags
& DSFLAG_SEEK
) && (r
= xftell(X
, &where
))) return r
;
110 if (page
.header
.tag
!= htons(1234)) {
112 (p
->cb_error
)(DSERR_MAGIC
, 1, p
->err_refcon
,
113 "Invalid page tag (%d) in page %d",
114 ntohs(page
.header
.tag
), pgno
);
117 for (i
= (pgno
? 1 : DPHE
); i
< EPP
; i
++) {
118 if (!allocbit(i
)) continue;
119 if (page
.entry
[i
].flag
!= FFIRST
) {
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
);
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
]) {
130 (p
->cb_error
)(DSERR_FMT
, 0, p
->err_refcon
,
131 "Filename too long in entry %d/%d; skipping page",
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
);
144 r
= (p
->cb_dirent
)(v
, &de
, X
, p
->refcon
);
146 if (p
->cb_dirent
&& (r
= (p
->cb_dirent
)(v
, &de
, X
, p
->refcon
)))
148 i
+= ((l
+ 16) >> 5);
151 if ((p
->flags
& DSFLAG_SEEK
) && (r
= xfseek(X
, &where
))) return r
;
156 afs_uint32
ParseDirectory(XFILE
*X
, dump_parser
*p
, afs_uint32 size
, int toeof
)
160 r
= parse_directory(X
, p
, 0, size
, toeof
);
172 static afs_uint32
dirlookup_cb(afs_vnode
*v
, afs_dir_entry
*de
,
173 XFILE
*X
, void *refcon
)
175 dirlookup_stat
*s
= (dirlookup_stat
*)refcon
;
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! */
184 s
->name
[0] = strdup(de
->name
);
185 if (!s
->name
[0]) return ENOMEM
;
187 if (s
->vuniq
) s
->vuniq
[0] = de
->uniq
;
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
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.
204 afs_uint32
DirectoryLookup(XFILE
*X
, dump_parser
*p
, afs_uint32 size
,
205 char **name
, afs_uint32
*vnode
, afs_uint32
*vuniq
)
211 memset(&my_s
, 0, sizeof(my_s
));
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
;
222 r
= parse_directory(X
, &my_p
, 0, size
, 0);
223 if (!r
) r
= DSERR_DONE
;
224 return handle_return(r
, X
, 0, p
);
228 static int allocpage(struct dir_state
*ds
, int reserve
)
230 unsigned char **dirpages
;
233 dirpages
= malloc((ds
->npages
+ 1) * sizeof(unsigned char *));
234 if (!dirpages
) return ENOMEM
;
236 memcpy(dirpages
, ds
->dirpages
, ds
->npages
* sizeof(unsigned char *));
239 ds
->dirpages
= dirpages
;
241 ds
->dirpages
[ds
->npages
] = malloc(AFS_PAGESIZE
);
242 if (!ds
->dirpages
[ds
->npages
]) return ENOMEM
;
243 ds
->pageno
= ds
->npages
++;
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
);
255 afs_uint32
Dir_Init(struct dir_state
**dsp
)
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
);
267 afs_uint32
Dir_AddEntry(struct dir_state
*ds
, char *name
,
268 afs_uint32 vnode
, afs_uint32 unique
)
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);
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
;
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
);
287 setallocbit(ds
->page
->header
.freebitmap
, ds
->entno
);
295 afs_uint32
Dir_Finalize(struct dir_state
*ds
)
297 int pages
= ds
->pageno
+ 1;
299 if (ds
->pageno
< 128) ds
->dh
->allomap
[ds
->pageno
] = ds
->used
;
300 ds
->dh
->pagehdr
.pgcount
= htons(pages
);
305 afs_uint32
Dir_EmitData(struct dir_state
*ds
, XFILE
*X
, int dotag
)
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
;
319 afs_uint32
Dir_Free(struct dir_state
*ds
)
323 for (i
= 0; i
< ds
->npages
; i
++)
324 free(ds
->dirpages
[i
]);
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.
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>.
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>
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.
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.
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.
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.
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.
384 * - next Pointer to the next element in this hash chain
385 * - fid FileID (vnode and uniquifier)
386 * - name Filename (null-terminated)