src/tools/directory.c

   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] = (char *)malloc(strlen(de->name) + 1);
 185       if (!s->name[0]) return ENOMEM;
 186       strcpy(s->name[0], de->name);
 187     }
 188     if (s->vuniq) s->vuniq[0] = de->uniq;
 189   }
 190   return DSERR_DONE;
 191 }
 192
 193
 194 /* Look up an entry in a directory, by name or vnode.
 195  * If *name is NULL, we are looking up by vnode.
 196  * Otherwise, we are looking for a filename.
 197  * In any event, any of name, vnode, vuniq that are
 198  * neither NULL nor the search key are filled in on
 199  * success.
 200  *
 201  * Call this with X pointing to the start of the directory,
 202  * and size set to the length of the directory.
 203  * Returns 0 on success, whether or not the entry is found.
 204  */
 205 afs_uint32 DirectoryLookup(XFILE *X, dump_parser *p, afs_uint32 size,
 206                     char **name, afs_uint32 *vnode, afs_uint32 *vuniq)
 207 {
 208   dump_parser my_p;
 209   dirlookup_stat my_s;
 210   afs_uint32 r;
 211
 212   memset(&my_s, 0, sizeof(my_s));
 213   my_s.name  = name;
 214   my_s.vnode = vnode;
 215   my_s.vuniq = vuniq;
 216
 217   memset(&my_p, 0, sizeof(my_p));
 218   my_p.refcon = (void *)&my_s;
 219   my_p.err_refcon = p->err_refcon;
 220   my_p.cb_error = p->cb_error;
 221   my_p.cb_dirent  = dirlookup_cb;
 222
 223   r = parse_directory(X, &my_p, 0, size, 0);
 224   if (!r) r = DSERR_DONE;
 225   return handle_return(r, X, 0, p);
 226 }
 227
 228
 229 static int allocpage(struct dir_state *ds, int reserve)
 230 {
 231   unsigned char **dirpages;
 232   int i;
 233
 234   dirpages = malloc((ds->npages + 1) * sizeof(unsigned char *));
 235   if (!dirpages) return ENOMEM;
 236   if (ds->dirpages) {
 237     memcpy(dirpages, ds->dirpages, ds->npages * sizeof(unsigned char *));
 238     free(ds->dirpages);
 239   }
 240   ds->dirpages = dirpages;
 241
 242   ds->dirpages[ds->npages] = malloc(AFS_PAGESIZE);
 243   if (!ds->dirpages[ds->npages]) return ENOMEM;
 244   ds->pageno = ds->npages++;
 245
 246   ds->page = (afs_dir_page *)(ds->dirpages[ds->pageno]);
 247   memset(ds->page, 0, AFS_PAGESIZE);
 248   ds->page->header.tag = htons(AFS_DIR_MAGIC);
 249   ds->entno = ds->used = reserve;
 250   for (i = 0; i < reserve; i++)
 251     setallocbit(ds->page->header.freebitmap, i);
 252   return 0;
 253 }
 254
 255
 256 afs_uint32 Dir_Init(struct dir_state **dsp)
 257 {
 258   afs_uint32 r;
 259
 260   *dsp = malloc(sizeof(struct dir_state));
 261   if (!*dsp) return ENOMEM;
 262   memset(*dsp, 0, sizeof(struct dir_state));
 263   if ((r = allocpage(*dsp, DPHE))) return r;
 264   (*dsp)->dh = (afs_dir_header *)((*dsp)->page);
 265   return 0;
 266 }
 267
 268
 269 afs_uint32 Dir_AddEntry(struct dir_state *ds, char *name,
 270                         afs_uint32 vnode, afs_uint32 unique)
 271 {
 272   afs_uint32 r;
 273   int l = strlen(name) + 1;
 274   int ne = l > 16 ? 1 + ((l - 16) / 32) + !!((l - 16) % 32) : 1;
 275   int hash = namehash(name, NHASHENT, 0);
 276
 277   if (ne > EPP - 1) return ENAMETOOLONG;
 278   if (ds->entno + ne > EPP) {
 279     if (ds->pageno < 128) ds->dh->allomap[ds->pageno] = ds->used;
 280     if ((r = allocpage(ds, 1))) return r;
 281   }
 282   ds->page->entry[ds->entno].flag    = FFIRST;
 283   ds->page->entry[ds->entno].next    = ds->dh->hash[hash];
 284   ds->page->entry[ds->entno].vnode   = htonl(vnode);
 285   ds->page->entry[ds->entno].vunique = htonl(unique);
 286   strcpy(ds->page->entry[ds->entno].name, name);
 287   ds->dh->hash[hash] = htons((ds->pageno * EPP) + ds->entno);
 288   while (ne--) {
 289     setallocbit(ds->page->header.freebitmap, ds->entno);
 290     ds->used++;
 291     ds->entno++;
 292   }
 293   return 0;
 294 }
 295
 296
 297 afs_uint32 Dir_Finalize(struct dir_state *ds)
 298 {
 299   int pages = ds->pageno + 1;
 300
 301   if (ds->pageno < 128) ds->dh->allomap[ds->pageno] = ds->used;
 302   ds->dh->pagehdr.pgcount = htons(pages);
 303   return 0;
 304 }
 305
 306
 307 afs_uint32 Dir_EmitData(struct dir_state *ds, XFILE *X, int dotag)
 308 {
 309   afs_uint32 r, size;
 310   int i;
 311
 312   size = ds->npages * AFS_PAGESIZE;
 313   if (dotag && (r = WriteTagInt32(X, VTAG_DATA, size))) return r;
 314   for (i = 0; i < ds->npages; i++) {
 315     if ((r = xfwrite(X, ds->dirpages[i], AFS_PAGESIZE))) return r;
 316   }
 317   return 0;
 318 }
 319
 320
 321 afs_uint32 Dir_Free(struct dir_state *ds)
 322 {
 323   int i;
 324
 325   for (i = 0; i < ds->npages; i++)
 326     free(ds->dirpages[i]);
 327   free(ds->dirpages);
 328   free(ds);
 329   return 0;
 330 }
 331
 332
 333 /* AFS directory format:
 334  * AFS directories are stored in volume dumps in exactly the same format
 335  * that is used on disk, which makes them relatively easy to dump and restore,
 336  * but means we have to do some work to interpret them.
 337  *
 338  * The ACL for a directory is stored on disk in the last part of a "large"
 339  * (directory) vnode.  This part of the vnode, which has fixed size
 340  * SIZEOF_LARGEDISKVNODE - SIZEOF_SMALLDISKVNODE, is copied directly into
 341  * the dump file with a tag of 'A' (VTAG_ACL).  The structure of this
 342  * section is described in <afs/acl.h>.
 343  *
 344  * The name-to-vnode mappings are also stored exactly as they appear on
 345  * disk, using the file data ('f') attribute.  As usual, this attribute
 346  * consists of a 32-bit number containing the size, immediately followed
 347  * by the data itself.  The interesting structures and constants are
 348  * defined in <afs/dir.h>
 349  *
 350  * A directory consists of one or more 'pages', each of which is 2K
 351  * (AFS_PAGESIZE).  Each page contains EPP (currently 64) 'entries', each
 352  * of which is 32 bytes.  The first page begins with a DirHeader, which
 353  * is DHE entries long, and includes a PageHeader.  All other pages begin
 354  * with just a PageHeader, which is 1 entry long.  Every other entry is
 355  * a DirEntry, a DirXEntry (name extension), or unused.
 356  *
 357  * A Page Header contains the following elements:
 358  * - pgcount    contains a count of the number of pages in the directory,
 359  *              if the directory is new-style (>128 pages), or 0 if it is
 360  *              old-style.  This field is meaningful only in the Dir Header.
 361  * - tag        a magic number, which must be 1234
 362  * - freecount  apparently unused
 363  * - freebitmap A bitmap of free entries.  Each byte corresponds to 8
 364  *              entries, with the least significant bit referring to the
 365  *              first of those.  Each bit is set iff the corresponding
 366  *              entry is allocated.  Entries used by the page and dir
 367  *              headers are considered allocated.
 368  *
 369  * A Dir Header consists of a Page Header, followed by an allocation map
 370  * and hash table.  The allocation map contains one byte for each of the
 371  * first 128 pages; that byte contains the number of entries in that page
 372  * that are allocated.  Every page that actually exists has at peast one
 373  * entry allocated (the Page Header); if a byte in this map is 0, it means
 374  * that the page does not yet exist.
 375  *
 376  * Each bucket in the hash table is a linked list, using 'blob numbers'
 377  * as pointers.  A blob number is defined as (page# * EPP) + entry#.
 378  * The head of each chain is kept in the hash table, and the next pointers
 379  * are kept in the 'next' entry of each directory.
 380  *
 381  * Directory entries themselves contain the following elements:
 382  * - flag    Set to FFIRST iff this is the first blob in an entry
 383  *           (otherwise it will be a name continuation).  This is
 384  *           probably not reliable.
 385  * - length  Unused
 386  * - next    Pointer to the next element in this hash chain
 387  * - fid     FileID (vnode and uniquifier)
 388  * - name    Filename (null-terminated)
 389  */