source: trunk/athena/etc/track/stamp.c @ 1252

/*
 *      $Source: /afs/dev.mit.edu/source/repository/athena/etc/track/stamp.c,v $
 *      $Header: /afs/dev.mit.edu/source/repository/athena/etc/track/stamp.c,v 4.8 1988-06-21 19:44:36 don Exp $
 *
 *      $Log: not supported by cvs2svn $
 * Revision 4.7  88/06/20  18:57:38  don
 * support for stamp.c version 4.4 :
 * this version's dec_entry has less static state, because it
 * detects that the entry hasn't been processed before, in a better way.
 * 
 * Revision 4.6  88/06/10  15:58:39  don
 * changed DEV usage to RDEV.
 * 
 * Revision 4.5  88/06/10  14:29:57  don
 * better error-handling on encountering sockets.
 * 
 * Revision 4.4  88/05/26  13:59:55  don
 * cosmetics in sort_entries(): fixed indentation, and added comments.
 * 
 * Revision 4.3  88/05/25  21:25:02  don
 * fixed a bug in sort_entries: only one descendant was getting added
 * to each entry's exception-list.
 * 
 * Revision 4.2  88/05/24  17:41:08  don
 * beefed up garbled-statfile messages, to aid in finding a bug.
 * the bug is a garbled-statfile message at the end of an update.
 * this is intermittent.
 * 
 * Revision 4.1  88/05/04  18:14:26  shanzer
 * fixed a bug in sort_entries(); its augmentation of a parent-entry's
 * exception-list didn't always work.   -don
 * 
 * Revision 4.0  88/04/14  16:43:00  don
 * this version is not compatible with prior versions.
 * it offers, chiefly, link-exporting, i.e., "->" systax in exception-lists.
 * it also offers sped-up exception-checking, via hash-tables.
 * a bug remains in -nopullflag support: if the entry's to-name top-level
 * dir doesn't exist, update_file doesn't get over it.
 * the fix should be put into the updated() routine, or possibly dec_entry().
 * 
 * Revision 3.0  88/03/09  13:17:47  don
 * this version is incompatible with prior versions. it offers:
 * 1) checksum-handling for regular files, to detect filesystem corruption.
 * 2) more concise & readable "updating" messages & error messages.
 * 3) better update-simulation when nopullflag is set.
 * 4) more support for non-default comparison-files.
 * finally, the "currentness" data-structure has replaced the statbufs
 * used before, so that the notion of currency is more readily extensible.
 * note: the statfile format has been changed.
 * 
 * Revision 2.5  88/02/23  19:21:36  don
 * fixed pushpath() & poppath() so that pushing "" onto a path-stack
 * doesn't push  a '/' as well. for example, pushpath( "/bin", "") should
 * yield "/bin", instead of "/bin/". this was causing findparent() to fail
 * when track needs to create bin under the subsciber's mount-point.
 * 
 * Revision 2.4  88/01/29  18:24:02  don
 * bug fixes. also, now track can update the root.
 * 
 * Revision 2.3  87/12/03  19:50:02  don
 * moved SIGN macro to track.h.
 * 
 * Revision 2.2  87/12/03  17:31:15  don
 * fixed rt-port bug in dec_statfile's use of sscanf():
 * can't fill a short int directly, because sscanf will interpret it
 * as a long-int, and on the rt, short* gets converted to int* via
 * truncation!
 * 
 * Revision 2.1  87/12/01  16:44:54  don
 * fixed bugs in readstat's traversal of entries] and statfile:
 * cur_ent is no longer global, but is now part of get_next_match's
 * state. also, last_match() was causing entries[]'s last element to be
 * skipped.
 * 
 * Revision 2.0  87/11/30  15:19:43  don
 * general rewrite; got rid of stamp data-type, with its attendant garbage,
 * cleaned up pathname-handling. readstat & writestat now sort overything
 * by pathname, which simplifies traversals/lookup. should be comprehensible
 * now.
 * 
 * Revision 1.1  87/02/12  21:15:36  rfrench
 * Initial revision
 * 
 */

#ifndef lint
static char *rcsid_header_h = "$Header: /afs/dev.mit.edu/source/repository/athena/etc/track/stamp.c,v 4.8 1988-06-21 19:44:36 don Exp $";
#endif lint

#include "mit-copyright.h"

#include "track.h"

/* XXX
 * convert right-shifted st_mode type-bits to corresponding formats:
 * S_IFCHR = 0020000 gets mapped to elt 1 of the array,
 * S_IFDIR = 0040000 => elt 2 of the array,
 * S_IFBLK = 0060000 => elt 3 of the array,
 * S_IFREG = 0100000 => elt 4 of the array,
 * S_IFLNK = 0120000 => elt 5 of the array,
 * S_IFSOCK= 0140000 => elt 6 of the array, ( only for error messagess),
 * S_IFMT  = 0170000 => elt 7 of the array, ( dropping 1 bit).
 */
static char *write_formats[] = {
        "*ERROR (write_statline): %s's file type is 0.\n",
        "c%s %c%d(%d.%d.%o)\n",         /* S_IFCHR */
        "d%s %c%d(%d.%d.%o)\n",         /* S_IFDIR */
        "b%s %c%d(%d.%d.%o)\n",         /* S_IFBLK */
        "f%s %c%x(%d.%d.%o)%ld\n",      /* S_IFREG */
        "l%s %c%s\n",                   /* S_IFLNK */
        "*ERROR (write_statline): can't track socket %s.\n",
        "*ERROR (write_statline): bad type S_IFMT %s.\n"
};

static char *read_formats[] = {
        "",
        "%d(%d.%d.%o)\n",       /* S_IFCHR */
        "%d(%d.%d.%o)\n",       /* S_IFDIR */
        "%d(%d.%d.%o)\n",       /* S_IFBLK */
        "%x(%d.%d.%o)%ld\n",    /* S_IFREG */
        "",                     /* S_IFLNK */
        "",                     /* S_IFSOCK */
        ""                      /* S_IFMT */
};

char type_char[] = " cdbfls*89ABCDEF";

/*
 * Place a time-stamp line in the format:
 *       type file uid.gid.mode.time
 * or a suitable derivate thereof
 */

write_statline( path, c)
char **path; struct currentness *c;
{
        char  *format, *linebuf, *name;
        int same_name;
        unsigned int type;
        struct stat fromstat, *s;
        unsigned size, curr1 = 0, extra = 0;

        if ( cur_line >= maxlines) {
                maxlines += MAXLINES;
                size = maxlines * sizeof statfilebufs[0];
                statfilebufs =
                        (Statline *) ( cur_line ?
                                       realloc( (char *) statfilebufs, size)
                                      : malloc( size));
                if ( ! statfilebufs) {
                        sprintf( errmsg, "alloc failed: %d statfile lines\n",
                                 cur_line);
                        do_panic();
                }
        }
        /*
         * set up type-dependent currency data:
         */

        s = &c->sbuf;

        switch( type = TYPE( *s)) {
        case S_IFREG:
                curr1 = c->cksum;
                extra = TIME( *s);
                break;
        case S_IFLNK:
                curr1 = (unsigned int) c->link;
                break;
        case S_IFDIR:
                curr1 = 0;
                break;
        case S_IFBLK:
                curr1 = RDEV( *s);
                break;
        case S_IFCHR:
                curr1 = RDEV( *s);
                break;
        case S_IFSOCK:
                sprintf( errmsg, "can't track socket %s.\n", path[ ROOT]);
                do_gripe();
                return( type);
        case S_IFMT:
        default:
                sprintf( errmsg,
                "bad type for inode %d, pathname %s.\n\tapparent type = %c\n",
                    c->sbuf.st_ino, path[ ROOT], type_char[ type >> 13]);
                do_panic();
        }
        /* set up name & sortkey:
         * root is a special case:
         * its "relative path" is "", which dec_statfile() can't read.
         */
        name = path[ NAME];
        if ( !*name) name = "/";

        KEYCPY( statfilebufs[ cur_line].sortkey, name);

        linebuf = statfilebufs[ cur_line].line;

        /* if this entry's fromfile != cmpfile,
         * the subscribing machine needs to know:
         */
        same_name = ! strcmp( path[ NAME], c->name);

        /* to choose printing format, convert type-bits to array-index:
         * the formats specify 3-7 arguments, according to type:
         */
        format = write_formats[ type >> 13];

        sprintf( linebuf, format, name, same_name ? '=' : '~' , curr1,
                 UID( *s), GID( *s), MODE( *s), extra);

        cur_line++;

        if ( verboseflag)
                fputs( linebuf, stderr);

        if ( same_name);
        else if ( ! (*statf)( path[ ROOT], &fromstat))
                type = TYPE( fromstat);
        else {
                sprintf( errmsg, "(write_statline) can't %s %s\n",
                         statn, path[ ROOT]);
                do_panic();
        }
        return( type);
}

fake_link( root, name, c) char *root, *name; struct currentness *c; {

        /* it is difficult to fool write_statline(),
         * update_file(), and curr_diff() all at once.
         * write_statline() can't take a normal currency in this case,
         * because it can't know the subscriber's fromroot.
         * curr_diff() needs to see a normal link's currency,
         * or else unneccessary link-updates will occur.
         * update_file() can use a normal currency to make a link.
         */
        if ( name != c->name)           /* speed hack for dec_statfile() */
                strcpy( c->name, name);

        if ( *root)
                sprintf( c->link, "%s/%s", root, name);
        else    *c->link = '\0';        /* special case for write_statline() */

        c->cksum = 0;
        clear_stat( &c->sbuf);
        c->sbuf.st_mode = S_IFLNK;
}

sort_stat() {
        int i;

        /* NOTE: this qsort call assumes that each statfilebufs[] element
         * begins with a sortkey as its first field.
         */
        qsort( (char *) statfilebufs, cur_line,
                sizeof( statfilebufs[ 0]), strcmp);

        for ( i = 0; i < cur_line; i++) {
                fputs( statfilebufs[ i].line, statfile);
        }
}

sort_entries() {
        char *tail;
        Table list;
        Entry *A, *C;
        int i, j;

        list.table = NULL;
        list.shift = 0;

        /* NOTE: we assume that each entry begins with a sortkey string.
         * don't include entries[ 0] in the sort:
         */
        qsort( (char *)& entries[ 1], entrycnt - 1,
               sizeof(   entries[ 1]), strcmp);

        /* for each entry's fromfile (call it A),
         * look for A's children amongst the subsequent entries,
         * and add any that you find to A's exception-table.
         * note that this may overfill the hash-table; in this event,
         * we accept the performance-hit, and don't try to rehash.
         */
        for (     A = &entries[ i = 1  ]; i < entrycnt; A = &entries[ ++i]) {
            for ( C = &entries[ j = i+1]; j < entrycnt; C = &entries[ ++j]) {
                switch(  keyncmp( C->sortkey, i)) {
                case 1:  break;                 /* get next A */
                case 0:  tail = C->fromfile + A->keylen;
                         while( '/' == *tail) tail++;
                         if ( A->names.table)
                             store( add_list_elt( tail, DONT_TRACK, NULL),
                                    &A->names);
                         else add_list_elt( tail, DONT_TRACK, LIST( list));
                case -1: continue;      /* unlikely */
                }
                break; /* get next A */
            }
            /* if A doesn't already have an exception-list of names,
             * then we've accumulated the list of descendant-entries
             * in the list{} structure; convert it to a hash-table for A:
             */
            if ( ! list.table);
            else if ( ! A->names.table) {
                     A->names.table = list.table;
                     A->names.shift = list.shift;
                     list.table = NULL;
                     list.shift = 0;
                     list2hashtable( &A->names);
            }
            else {
                     sprintf(errmsg, "sort_entries: internal error\n");
                     do_panic();
            }
        }
}

/*
 * Decode a statfile line into its individual fields.
 * setup TYPE(), UID(), GID(), MODE(), TIME(), & RDEV() contents.
 */

char *
dec_statfile( line, c)
char *line; struct currentness *c;
{
        struct stat *s;
        int *extra = 0;
        char *end, *format, *name, same_name, type;
        int dummy, *curr1 = &dummy, d = 0, u = 0, g = 0, m = 0;

        /* these long-int temps are necessary for pc/rt compatibility:
         * sscanf cannot scan into a short, though it may sometimes succeed
         * in doing so. the difficulty is that it can't know about the
         * target-integer's length, so it assumes that it's long.
         * since the rt will truncate a short's addr, in order to treat
         * it as a long, sscanf's data will often get lost.
         * the solution is to give scanf longs, and then to convert these
         * longs to shorts, explicitly.
         */

        /* for speed, we laboriously parse the type-independent part
         * of the statline without calling sscanf().
         * thus, we avoid copying the pathname strings around,
         * since the caller can re-use the originals,
         * once they're broken out of the line-format.
         */
        type = *line++;
        name = line;
        line = index( line, ' ');
        if ( ! line) {
                sprintf( errmsg, "garbled statfile: bad line =\n%s\n", line);
                sprintf( errmsg, "line has only one field\n");
                do_panic();
        }
        *line++ = '\0';

        /* in the  statfile, which contains only relative pathnames,
         * "/" is the only pathname which can begin with a slash.
         * in entries[], the root appears as "", which is more natural,
         * because "" is "/"'s pathname relative to the mount-point fromroot.
         * and because pushpath() prepends slashes in the right places, anyway.
         * "" is hard to read with sscanf(), so we handle "/" specially:
         */
        if ( '/' != *name);
        else if ( ! name[ 1]) *name = '\0';
        else {
                sprintf(errmsg, "statfile passed an absolute pathname: %s\n",
                        name);
                do_gripe();
        }
        /* the subscriber needs to know whether the currency-data
         * came from the remote fromfile or from the remote cmpfile.
         */
        switch( same_name = *line++) {
        case '=': strcpy( c->name, name);
                  break;
        case '~': *c->name = '\0';
                  break;
        default:
                sprintf( errmsg, "garbled statfile: bad line =\n%s\n", line);
                sprintf( errmsg, "bad equality flag = %c\n", same_name);
                do_panic();
        }
        *c->link = '\0';
        c->cksum = 0;

        /*
         * set up scanf arg's for type-dependent currency-data:
         */

        s = &c->sbuf;
        clear_stat( s);

        switch( type) {
        case 'f':
                s->st_mode = S_IFREG;
                curr1 = ( int*)&c->cksum;
                extra = ( int*)&s->st_mtime;
                break;
        case 'l':       /* more common than dir's */
                s->st_mode = S_IFLNK;
                if ( end = index( line, '\n'))
                        *end = '\0';
                else {
                        sprintf( errmsg, "garbled statfile: bad line =\n%s\n",
                                line);
                        sprintf( errmsg, "line doesn't end with a newline\n");
                        do_panic();
                }
                if ( !*line) fake_link( fromroot, c->name, c);
                else strcpy( c->link, line);
                break;
        case 'd':
                s->st_mode = S_IFDIR;
                curr1 = &dummy;
                break;
        case 'b':
                s->st_mode = S_IFBLK;
                curr1 = &d;
                break;
        case 'c':
                s->st_mode = S_IFCHR;
                curr1 = &d;
                break;
        default:
                sprintf( errmsg, "garbled statfile: bad line =\n%s\n", line);
                sprintf( errmsg, "first char isn't a file-type [fldbc]\n");
                do_panic();
        }
        /* if we've already parsed the line,
         * as in S_IFLNK case, skip the sscanf call:
         */
        if ( *(format = read_formats[ s->st_mode >> 13]))
                sscanf( line, format, curr1, &u, &g, &m, extra);

        s->st_uid   = (short) u;
        s->st_gid   = (short) g;
        s->st_mode |= (short) m & 07777;
        s->st_rdev  = (short) d;
        return( name);
}

/* the match abstractions implement a synchronized traversal
 * of the entries[] array & the statfile. both sets of data
 * are sorted by strcmp() on their sortkeys, which are made
 * via the KEYCPY macro.
 */

/* XXX: not the best, but not the worst approach either.
 * this  allows main() to call readstat() twice, with correct initialization.
 */
int prev_ent = 0;;

int cur_ent = 0;        /* not global! index into entries[]. */

init_next_match() {
        prev_ent = 0;
        cur_ent = 1;
}

int
get_next_match( name)
char *name;
{
        char key[ LINELEN];

        KEYCPY( key, name);

        for ( ; cur_ent < entrycnt; cur_ent++)
                switch ( keyncmp( key, cur_ent)) {
                case 0:  return( cur_ent);
                case -1: return( 0);            /* advance name's    key */
                case 1:  continue;              /* advance cur_ent's key */
                }

        return( -1); /* out of entries */
}

/* last_match:
 * we know that path begins with entnum's fromfile,
 * but path may also match other entries.
 * for example, the path /a/b/c matches the entries /a & /a/b.
 * we want the longest entry that matches.
 * look-ahead to find last sub-list entry that matches
 * the current pathname: this works because by keyncmp,
 *          /   is greater than         /Z...
 *         |    matches                 /a
 *         |    is greater than         /a/a
 *         \    matches                 /a/b
 * /a/b/c  <    is greater than         /a/b/a
 *         /    matches                 /a/b/c
 *         |    is less than            /a/b/c/a
 *         |    is less than            /a/b/d
 *          \   is less than            /a/c...
 * NOTE that the right-hand column is sorted by key,
 * and that the last match is the longest.
 */
int
last_match( path, entnum) char *path; int entnum; {
        int i;
        char key[ LINELEN];

        KEYCPY( key, path);
        for ( i = entnum + 1; i < entrycnt; i++) {
                switch ( keyncmp( key, i)) {
                case -1: break;         /* quit at   /a/b/d */
                case 0:  entnum = i;    /* remember  /a or /a/b */
                case 1:  continue;      /* skip over /a/a */
                }
                break; /* quit loop */
        }
        return( entnum);
}

/* compare the path r with i's sortkey in the following way:
 * if the key is a subpath of r, return 0, as a match.
 * if the key is < or > r, return 1 or -1  respectively.
 */
int
keyncmp( r, i) char *r; int i; {
        char *l;
        int diff, n;

        l = entries[ i].sortkey;
        n = entries[ i].keylen;

        diff = SIGN( strncmp( r, l, n));

        /* if diff == 0 & n != 0 ( l isn't root) &
         * r[n] == '\0' or '\001', we have a match.
         * if n == 0, l is root, which matches everything.
         */
        return( diff? diff: n ? ( (unsigned) r[n] > '\001') : 0);   /* XXX */
}

struct currentness *
dec_entry( entnum, fr, to, cmp, tail)
int entnum; char *fr[], *to[], *cmp[], *tail; {
        static struct currentness currency_buf, *entry_currency;
        int i;
        Entry *e;
        static int xref_flag = 0;

        /* this routine's main purpose is to transfer entnum's contents
         * to the paths fr, to, & cmp.
         * for efficiency and data-hiding reasons, we maintain various static
         * data, including the currentness data for readstat's last update.
         */

        /* we avoid calling get_currentness(cmp) redundantly, but not just
         * for efficiency reasons: this helps our update-simulation for
         * nopullflag-support. see update_file().
         * each cmpfile may get updated at most once;
         * if it does, update_file() will mark its currency "out-of-date".
         * xref_flag is set if any entry uses another entry's file
         * as a cmpfile. in this case, we have to search entries[]
         * to see if what we've modified is another entry's cmpfile.
         * if so, propagate the "out-of-date" mark to that entry.
         */
        if ( xref_flag && updated( &currency_buf, NULL)) {
                for ( e = &entries[ i = 1]; i <= entrycnt; e = &entries[ ++i]) {
                        if ( updated( &e->currency, NULL) ||
                             strcmp(   e->cmpfile,   currency_buf.name));
                        else updated( &e->currency, &currency_buf);
                }
        }
        currency_buf.sbuf.st_mode = S_IFMT;     /* kill short-term data. */

        if (    prev_ent != entnum) {
                prev_ent =  entnum;

                /* a subtler, longer search would set this flag less often.
                 */
                if ( ! writeflag)
                        xref_flag = strncmp( entries[ entnum].cmpfile,
                                             entries[ entnum].tofile,
                                     strlen( entries[ entnum].tofile));

                poppath( fr); pushpath( fr,  entries[ entnum].fromfile);
                poppath( to); pushpath( to,  entries[ entnum].tofile);
                poppath(cmp); pushpath( cmp, entries[ entnum].cmpfile);
                
                /* this function-var is global, and used generally.
                 */
                statf = entries[ entnum].followlink ?  stat  :  lstat;
                statn = entries[ entnum].followlink ? "stat" : "lstat";

                entry_currency = &entries[ entnum].currency;
        }
        if ( updated( entry_currency, NULL))
                get_currentness( cmp, entry_currency);

        if ( ! tail || ! *tail )
                return( entry_currency);

        if ( S_IFDIR == TYPE( entry_currency->sbuf)) { /* usual case */
                pushpath( cmp, tail);
                get_currentness( cmp, &currency_buf);
                poppath( cmp);
                return( &currency_buf);
        }
        /* rarely, a directory may have a non-dir as its cmpfile.
         * if the entry's cmpfile isn't a dir, then cmp[ ROOT],
         * is the comparison-file for each of the tofile's dependents.
         */
        return( entry_currency);
}

/* these routines handle a stack of pointers into a character-string,
 * which typically is a UNIX pathname.
 * the first element CNT of the stack points to a depth-counter.
 * the second element ROOT points to the beginning of the pathname string.
 * subsequent elements point to terminal substrings of the pathname.
 * a slash precedes each element.
 */
#define COUNT(p) (*(int*)p[CNT])
char **
initpath( name) char *name; {
        char **p;

        /* for each stack-element, alloc a pointer 
         * and 15 chars for a filename:
         */
        p =      (char **) malloc( stackmax * sizeof NULL);
        p[ CNT] = (char *) malloc( stackmax * 15 + sizeof ((int) 0));
        COUNT( p) = 1;
        p[ ROOT] = p[ CNT] + sizeof ((int) 1);
        strcpy( p[ ROOT], name);
        p[ NAME] = p[ ROOT] + strlen( name);
        return( p);
}
int
pushpath( p, name) char **p; char *name; {
        char *top;

        if ( ! p) return( -1);
        if ( ++COUNT( p) >= stackmax) {
                sprintf( errmsg, "%s\n%s\n%s %d.\n",
                        "path stack overflow: directory too deep:", p[ ROOT],
                        "use -S option, with value >", stackmax);
                do_panic();
        }
        if ( *name) *p[ COUNT( p)]++ = '/';
        top = p[ COUNT( p)];
        strcpy( top, name);
        p[ COUNT( p) + 1] = top + strlen( top);
        return( COUNT( p));
}
poppath( p) char **p; {
        if ( ! p) return;
        else if ( 1 >= COUNT( p)) {
                sprintf(errmsg,"can't pop root from path-stack");
                do_panic();
        }
        else if ( *p[ COUNT( p)]) p[ COUNT( p)]--;
                /* non-null last elt; remove its initial slash */
        *p[  COUNT( p)--] = '\0';
        return;
}