directory.c

/*
 * CMUCS AFStools
 * dumpscan - routines for scanning and manipulating AFS volume dumps
 *
 * Copyright (c) 1998, 2001, 2004 Carnegie Mellon University
 * All Rights Reserved.
 * 
 * Permission to use, copy, modify and distribute this software and its
 * documentation is hereby granted, provided that both the copyright
 * notice and this permission notice appear in all copies of the
 * software, derivative works or modified versions, and any portions
 * thereof, and that both notices appear in supporting documentation.
 *
 * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
 * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
 * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
 *
 * Carnegie Mellon requests users of this software to return to
 *
 *  Software Distribution Coordinator  or  Software_Distribution@CS.CMU.EDU
 *  School of Computer Science
 *  Carnegie Mellon University
 *  Pittsburgh PA 15213-3890
 *
 * any improvements or extensions that they make and grant Carnegie Mellon
 * the rights to redistribute these changes.
 */

/* directory.c - AFS directory parsing and generation */
/* See the end of this file for a description of the directory format */

#include <errno.h>
#include <sys/types.h>
#include <stdlib.h>
#include <string.h>
#include <netinet/in.h>

#include "dumpscan.h"
#include "dumpscan_errs.h"
#include "xf_errs.h"
#include "dumpfmt.h"
#include "internal.h"

#include <afs/dir.h>

struct dir_state {
  unsigned char **dirpages;
  int npages;

  afs_dir_header *dh;        /* Directory header */
  afs_dir_page *page;        /* Current page */
  int pageno;                /* Current page # */
  int entno;                 /* Current (next avail) entry # */
  int used;                  /* # entries used in this page */
};

static afs_dir_page page;

#define bmbyte(bm,x) bm[(x)>>3]
#define bmbit(x) (1 << ((x) & 7))

#define allocbit(x) (bmbyte(page.header.freebitmap,x) & bmbit(x))
#define setallocbit(bm,x) (bmbyte(bm,x) |= bmbit(x))

#define DPHE (DHE + 1)

/* Hash function used in AFS directories.  */
static int namehash(char *name, int buckets, int seed)
{   
  int hval = seed, tval;

  while (*name) hval = (hval * 173) + *name++;
  tval = hval & (buckets - 1);
  return tval ? hval < 0 ? buckets - tval : tval : 0;
}

afs_uint32 parse_directory(XFILE *X, dump_parser *p, afs_vnode *v,
                        afs_uint32 size, int toeof)
{
  afs_dir_entry de;
  int pgno, i, l, n;
  int r;
  u_int64 where;

  if (p->print_flags & DSPRINT_DIR) {
    printf("  VNode      Uniqifier   Name\n");
    printf("  ========== ==========  ==============================\n");
  }
  if ((p->flags & DSFLAG_SEEK) && (r = xftell(X, &where))) return r;
  for (pgno = 0; toeof || size; pgno++, size -= (toeof ? 0 : AFS_PAGESIZE)) {
    if ((p->flags & DSFLAG_SEEK) && (r = xfseek(X, &where))) return r;
    if (r = xfread(X, &page, AFS_PAGESIZE)) {
      if (toeof && r == ERROR_XFILE_EOF) break;
      return r;
    }
    if ((p->flags & DSFLAG_SEEK) && (r = xftell(X, &where))) return r;
    if (page.header.tag != htons(1234)) {
      if (p->cb_error)
        (p->cb_error)(DSERR_MAGIC, 1, p->err_refcon,
                      "Invalid page tag (%d) in page %d",
                      ntohs(page.header.tag), pgno);
      return DSERR_MAGIC;
    }
    for (i = (pgno ? 1 : DPHE); i < EPP; i++) {
      if (!allocbit(i)) continue;
      if (page.entry[i].flag != FFIRST) {
        if (p->cb_error)
          (p->cb_error)(DSERR_MAGIC, 0, p->err_refcon,
                        "Invalid entry flag %d in entry %d/%d; skipping...",
                        page.entry[i].flag, pgno, i);
        continue;
      }
      n = (EPP - i - 1) * 32 + 16;
      for (l = 0; n && page.entry[i].name[l]; l++, n--);
      if (page.entry[i].name[l]) {
        if (p->cb_error)
          (p->cb_error)(DSERR_FMT, 0, p->err_refcon,
                        "Filename too long in entry %d/%d; skipping page",
                        pgno, i);
        break;
      }
      if (pgno) de.slot = i - 1 + (pgno - 1) * (EPP - 1) + (EPP - DPHE);
      else de.slot = i - DPHE;
      de.name  = page.entry[i].name;
      de.vnode = ntohl(page.entry[i].vnode);
      de.uniq  = ntohl(page.entry[i].vunique);
      if (p->print_flags & DSPRINT_DIR)
        printf("  %10d %10d  %s\n", de.vnode, de.uniq, de.name);
      if (p->cb_dirent && (r = (p->cb_dirent)(v, &de, X, p->refcon)))
        return r;
      i += ((l + 16) >> 5);
    }
  }
  if ((p->flags & DSFLAG_SEEK) && (r = xfseek(X, &where))) return r;
  return 0;
}


afs_uint32 ParseDirectory(XFILE *X, dump_parser *p, afs_uint32 size, int toeof)
{
  parse_directory(X, p, 0, size, toeof);
  return 0;
}


typedef struct {
  char **name;
  afs_uint32 *vnode;
  afs_uint32 *vuniq;
} dirlookup_stat;


static afs_uint32 dirlookup_cb(afs_vnode *v, afs_dir_entry *de,
                            XFILE *X, void *refcon)
{
  dirlookup_stat *s = (dirlookup_stat *)refcon;

  if (s->name && s->name[0]) {                  /* Search by filename */
    if (strcmp(de->name, s->name[0])) return 0; /* Not it! */
    if (s->vnode) s->vnode[0] = de->vnode;
    if (s->vuniq) s->vuniq[0] = de->uniq;
  } else if (s->vnode) {                        /* Search by vnode */
    if (de->vnode != s->vnode[0]) return 0;     /* Not it! */
    if (s->name) {
      s->name[0] = (char *)malloc(strlen(de->name) + 1);
      if (!s->name[0]) return ENOMEM;
      strcpy(s->name[0], de->name);
    }
    if (s->vuniq) s->vuniq[0] = de->uniq;
  }
  return DSERR_DONE;
}


/* Look up an entry in a directory, by name or vnode.
 * If *name is NULL, we are looking up by vnode.
 * Otherwise, we are looking for a filename.
 * In any event, any of name, vnode, vuniq that are
 * neither NULL nor the search key are filled in on
 * success.
 *
 * Call this with X pointing to the start of the directory,
 * and size set to the length of the directory.
 * Returns 0 on success, whether or not the entry is found.
 */
afs_uint32 DirectoryLookup(XFILE *X, dump_parser *p, afs_uint32 size,
                    char **name, afs_uint32 *vnode, afs_uint32 *vuniq)
{
  dump_parser my_p;
  dirlookup_stat my_s;
  afs_uint32 r;

  memset(&my_s, 0, sizeof(my_s));
  my_s.name  = name;
  my_s.vnode = vnode;
  my_s.vuniq = vuniq;

  memset(&my_p, 0, sizeof(my_p));
  my_p.refcon = (void *)&my_s;
  my_p.err_refcon = p->err_refcon;
  my_p.cb_error = p->cb_error;
  my_p.cb_dirent  = dirlookup_cb;

  r = parse_directory(X, &my_p, 0, size, 0);
  if (!r) r = DSERR_DONE;
  return handle_return(r, X, 0, p);
}


static int allocpage(struct dir_state *ds, int reserve)
{
  unsigned char **dirpages;
  int i;

  dirpages = malloc((ds->npages + 1) * sizeof(unsigned char *));
  if (!dirpages) return ENOMEM;
  if (ds->dirpages) {
    memcpy(dirpages, ds->dirpages, ds->npages * sizeof(unsigned char *));
    free(ds->dirpages);
  }
  ds->dirpages = dirpages;

  ds->dirpages[ds->npages] = malloc(AFS_PAGESIZE);
  if (!ds->dirpages[ds->npages]) return ENOMEM;
  ds->pageno = ds->npages++;

  ds->page = (afs_dir_page *)(ds->dirpages[ds->pageno]);
  memset(ds->page, 0, AFS_PAGESIZE);
  ds->page->header.tag = htons(AFS_DIR_MAGIC);
  ds->entno = ds->used = reserve;
  for (i = 0; i < reserve; i++)
    setallocbit(ds->page->header.freebitmap, i);
  return 0;
}


afs_uint32 Dir_Init(struct dir_state **dsp)
{
  afs_uint32 r;

  *dsp = malloc(sizeof(struct dir_state));
  if (!*dsp) return ENOMEM;
  memset(*dsp, 0, sizeof(struct dir_state));
  if ((r = allocpage(*dsp, DPHE))) return r;
  (*dsp)->dh = (afs_dir_header *)((*dsp)->page);
  return 0;
}


afs_uint32 Dir_AddEntry(struct dir_state *ds, char *name,
                        afs_uint32 vnode, afs_uint32 unique)
{
  afs_uint32 r;
  int l = strlen(name) + 1;
  int ne = l > 16 ? 1 + ((l - 16) / 32) + !!((l - 16) % 32) : 1;
  int hash = namehash(name, NHASHENT, 0);

  if (ne > EPP - 1) return ENAMETOOLONG;
  if (ds->entno + ne > EPP) {
    if (ds->pageno < 128) ds->dh->allomap[ds->pageno] = ds->used;
    if ((r = allocpage(ds, 1))) return r;
  }
  ds->page->entry[ds->entno].flag    = FFIRST;
  ds->page->entry[ds->entno].next    = ds->dh->hash[hash];
  ds->page->entry[ds->entno].vnode   = htonl(vnode);
  ds->page->entry[ds->entno].vunique = htonl(unique);
  strcpy(ds->page->entry[ds->entno].name, name);
  ds->dh->hash[hash] = htons((ds->pageno * EPP) + ds->entno);
  while (ne--) {
    setallocbit(ds->page->header.freebitmap, ds->entno);
    ds->used++;
    ds->entno++;
  }
  return 0;
}


afs_uint32 Dir_Finalize(struct dir_state *ds)
{
  int pages = ds->pageno + 1;
  
  if (ds->pageno < 128) ds->dh->allomap[ds->pageno] = ds->used;
  ds->dh->pagehdr.pgcount = htons(pages);
  return 0;
}


afs_uint32 Dir_EmitData(struct dir_state *ds, XFILE *X, int dotag)
{
  afs_uint32 r, size;
  int i;

  size = ds->npages * AFS_PAGESIZE;
  if (dotag && (r = WriteTagInt32(X, VTAG_DATA, size))) return r;
  for (i = 0; i < ds->npages; i++) {
    if (r = xfwrite(X, ds->dirpages[i], AFS_PAGESIZE)) return r;
  }
  return 0;
}


afs_uint32 Dir_Free(struct dir_state *ds)
{
  int i;

  for (i = 0; i < ds->npages; i++)
    free(ds->dirpages[i]);
  free(ds->dirpages);
  free(ds);
  return 0;
}


/* AFS directory format:
 * AFS directories are stored in volume dumps in exactly the same format
 * that is used on disk, which makes them relatively easy to dump and restore,
 * but means we have to do some work to interpret them.
 *
 * The ACL for a directory is stored on disk in the last part of a "large"
 * (directory) vnode.  This part of the vnode, which has fixed size
 * SIZEOF_LARGEDISKVNODE - SIZEOF_SMALLDISKVNODE, is copied directly into
 * the dump file with a tag of 'A' (VTAG_ACL).  The structure of this
 * section is described in <afs/acl.h>.
 *
 * The name-to-vnode mappings are also stored exactly as they appear on
 * disk, using the file data ('f') attribute.  As usual, this attribute
 * consists of a 32-bit number containing the size, immediately followed
 * by the data itself.  The interesting structures and constants are
 * defined in <afs/dir.h>
 * 
 * A directory consists of one or more 'pages', each of which is 2K
 * (AFS_PAGESIZE).  Each page contains EPP (currently 64) 'entries', each
 * of which is 32 bytes.  The first page begins with a DirHeader, which
 * is DHE entries long, and includes a PageHeader.  All other pages begin
 * with just a PageHeader, which is 1 entry long.  Every other entry is
 * a DirEntry, a DirXEntry (name extension), or unused.
 *
 * A Page Header contains the following elements:
 * - pgcount    contains a count of the number of pages in the directory,
 *              if the directory is new-style (>128 pages), or 0 if it is
 *              old-style.  This field is meaningful only in the Dir Header.
 * - tag        a magic number, which must be 1234
 * - freecount  apparently unused
 * - freebitmap A bitmap of free entries.  Each byte corresponds to 8
 *              entries, with the least significant bit referring to the
 *              first of those.  Each bit is set iff the corresponding
 *              entry is allocated.  Entries used by the page and dir
 *              headers are considered allocated.
 *
 * A Dir Header consists of a Page Header, followed by an allocation map
 * and hash table.  The allocation map contains one byte for each of the
 * first 128 pages; that byte contains the number of entries in that page
 * that are allocated.  Every page that actually exists has at peast one
 * entry allocated (the Page Header); if a byte in this map is 0, it means
 * that the page does not yet exist.
 *
 * Each bucket in the hash table is a linked list, using 'blob numbers'
 * as pointers.  A blob number is defined as (page# * EPP) + entry#.
 * The head of each chain is kept in the hash table, and the next pointers
 * are kept in the 'next' entry of each directory.
 *
 * Directory entries themselves contain the following elements:
 * - flag    Set to FFIRST iff this is the first blob in an entry
 *           (otherwise it will be a name continuation).  This is
 *           probably not reliable.
 * - length  Unused
 * - next    Pointer to the next element in this hash chain
 * - fid     FileID (vnode and uniquifier)
 * - name    Filename (null-terminated)
 */