must flush stderr before reading from the terminal

[unix-history] / usr / src / sbin / restore / symtab.c

diff --git a/usr/src/sbin/restore/symtab.c b/usr/src/sbin/restore/symtab.c
index 75257d7..7e19c68 100644 (file)
--- a/usr/src/sbin/restore/symtab.c
+++ b/usr/src/sbin/restore/symtab.c
@@ -1,23 +1,33 @@
 /* Copyright (c) 1983 Regents of the University of California */
 
 #ifndef lint
 /* Copyright (c) 1983 Regents of the University of California */
 
 #ifndef lint

-static char sccsid[] = "@(#)symtab.c   3.4     (Berkeley)      83/02/28";
+static char sccsid[] = "@(#)symtab.c   3.10    (Berkeley)      83/05/03";

 #endif
 
 #endif
 

+/*
+ * These routines maintain the symbol table which tracks the state
+ * of the file system being restored. They provide lookup by either
+ * name or inode number. They also provide for creation, deletion,
+ * and renaming of entries. Because of the dynamic nature of pathnames,
+ * names should not be saved, but always constructed just before they
+ * are needed, by calling "myname".
+ */
+

 #include "restore.h"
 #include <sys/stat.h>
 #include "restore.h"
 #include <sys/stat.h>

+#include <dir.h>

 
 

-struct symtableheader {
-       long    volno;
-       long    stringsize;
-       time_t  dumptime;
-       time_t  dumpdate;
-       ino_t   maxino;
-};
-
-struct entry *freelist = NIL;
+/*
+ * The following variables define the inode symbol table.
+ * The primary hash table is dynamically allocated based on
+ * the number of inodes in the file system (maxino), scaled by
+ * HASHFACTOR. The variable "entry" points to the hash table;
+ * the variable "entrytblsize" indicates its size (in entries).
+ */
+#define HASHFACTOR 5
+static struct entry **entry;
+static long entrytblsize;

 
 

-#ifndef lookupino

 /*
  * Look up an entry by inode number
  */
 /*
  * Look up an entry by inode number
  */


@@ -25,35 +35,59 @@ struct entry *
 lookupino(inum)
        ino_t inum;
 {
 lookupino(inum)
        ino_t inum;
 {

+       register struct entry *ep;

 
 

-       return (entry[inum]);
+       if (inum < ROOTINO || inum >= maxino)
+               return (NIL);
+       for (ep = entry[inum % entrytblsize]; ep != NIL; ep = ep->e_next)
+               if (ep->e_ino == inum)
+                       return (ep);
+       return (NIL);

 }
 }

-#endif lookupino

 
 

-#ifndef addino

 /*
  * Add an entry into the entry table
  */
 addino(inum, np)
 /*
  * Add an entry into the entry table
  */
 addino(inum, np)

-       long inum;
+       ino_t inum;

        struct entry *np;
 {
        struct entry *np;
 {

+       struct entry **epp;

 
 

-       entry[inum] = np;
+       if (inum < ROOTINO || inum >= maxino)
+               panic("addino: out of range %d\n", inum);
+       epp = &entry[inum % entrytblsize];
+       np->e_ino = inum;
+       np->e_next = *epp;
+       *epp = np;
+       if (dflag)
+               for (np = np->e_next; np != NIL; np = np->e_next)
+                       if (np->e_ino == inum)
+                               badentry(np, "duplicate inum");

 }
 }

-#endif addino

 
 

-#ifndef deleteino

 /*
  * Delete an entry from the entry table
  */
 deleteino(inum)
 /*
  * Delete an entry from the entry table
  */
 deleteino(inum)

-       long inum;
+       ino_t inum;

 {
 {

-
-       entry[inum] = NIL;
+       register struct entry *next;
+       struct entry **prev;
+
+       if (inum < ROOTINO || inum >= maxino)
+               panic("deleteino: out of range %d\n", inum);
+       prev = &entry[inum % entrytblsize];
+       for (next = *prev; next != NIL; next = next->e_next) {
+               if (next->e_ino == inum) {
+                       next->e_ino = 0;
+                       *prev = next->e_next;
+                       return;
+               }
+               prev = &next->e_next;
+       }
+       panic("deleteino: %d not found\n", inum);

 }
 }

-#endif deleteino

 
 /*
  * Look up an entry by name
 
 /*
  * Look up an entry by name


@@ -64,7 +98,7 @@ lookupname(name)
 {
        register struct entry *ep;
        register char *np, *cp;
 {
        register struct entry *ep;
        register char *np, *cp;

-       char buf[BUFSIZ];
+       char buf[MAXPATHLEN];

 
        cp = name;
        for (ep = lookupino(ROOTINO); ep != NIL; ep = ep->e_entries) {
 
        cp = name;
        for (ep = lookupino(ROOTINO); ep != NIL; ep = ep->e_entries) {


@@ -113,9 +147,9 @@ myname(ep)
        register struct entry *ep;
 {
        register char *cp;
        register struct entry *ep;
 {
        register char *cp;

-       static char namebuf[BUFSIZ];
+       static char namebuf[MAXPATHLEN];

 
 

-       for (cp = &namebuf[BUFSIZ - 2]; cp > &namebuf[ep->e_namlen]; ) {
+       for (cp = &namebuf[MAXPATHLEN - 2]; cp > &namebuf[ep->e_namlen]; ) {

                cp -= ep->e_namlen;
                bcopy(ep->e_name, cp, (long)ep->e_namlen);
                if (ep == lookupino(ROOTINO))
                cp -= ep->e_namlen;
                bcopy(ep->e_name, cp, (long)ep->e_namlen);
                if (ep == lookupino(ROOTINO))


@@ -127,6 +161,12 @@ myname(ep)
        return(cp);
 }
 
        return(cp);
 }
 

+/*
+ * Unused symbol table entries are linked together on a freelist
+ * headed by the following pointer.
+ */
+static struct entry *freelist = NIL;
+

 /*
  * add an entry to the symbol table
  */
 /*
  * add an entry to the symbol table
  */


@@ -140,12 +180,11 @@ addentry(name, inum, type)
 
        if (freelist != NIL) {
                np = freelist;
 
        if (freelist != NIL) {
                np = freelist;

-               freelist = np->e_sibling;
+               freelist = np->e_next;

                bzero((char *)np, (long)sizeof(struct entry));
        } else {
                np = (struct entry *)calloc(1, sizeof(struct entry));
        }
                bzero((char *)np, (long)sizeof(struct entry));
        } else {
                np = (struct entry *)calloc(1, sizeof(struct entry));
        }

-       np->e_ino = inum;

        np->e_type = type & ~LINK;
        ep = lookupparent(name);
        if (ep == NIL) {
        np->e_type = type & ~LINK;
        ep = lookupparent(name);
        if (ep == NIL) {


@@ -166,6 +205,7 @@ addentry(name, inum, type)
                ep = lookupino(inum);
                if (ep == NIL)
                        panic("link to non-existant name\n");
                ep = lookupino(inum);
                if (ep == NIL)
                        panic("link to non-existant name\n");

+               np->e_ino = inum;

                np->e_links = ep->e_links;
                ep->e_links = np;
        } else if (inum != 0) {
                np->e_links = ep->e_links;
                ep->e_links = np;
        } else if (inum != 0) {


@@ -184,58 +224,39 @@ freeentry(ep)
 {
        register struct entry *np;
 
 {
        register struct entry *np;
 

-       np = lookupino(ep->e_ino);
-       if (np == NIL)
-               badentry(ep, "lookupino failed");

        if (ep->e_flags != REMOVED)
                badentry(ep, "not marked REMOVED");
        if (ep->e_flags != REMOVED)
                badentry(ep, "not marked REMOVED");

-       if (np->e_type == NODE) {
-               if (np == ep && np->e_links != NIL)
+       if (ep->e_type == NODE) {
+               if (ep->e_links != NIL)

                        badentry(ep, "freeing referenced directory");
                if (ep->e_entries != NIL)
                        badentry(ep, "freeing non-empty directory");
        }
                        badentry(ep, "freeing referenced directory");
                if (ep->e_entries != NIL)
                        badentry(ep, "freeing non-empty directory");
        }

-       if (np == ep) {
-               deleteino(ep->e_ino);
-               addino(ep->e_ino, ep->e_links);
-       } else {
-               for (; np != NIL; np = np->e_links) {
-                       if (np->e_links == ep) {
-                               np->e_links = ep->e_links;
-                               break;
+       if (ep->e_ino != 0) {
+               np = lookupino(ep->e_ino);
+               if (np == NIL)
+                       badentry(ep, "lookupino failed");
+               if (np == ep) {
+                       deleteino(ep->e_ino);
+                       if (ep->e_links != NIL)
+                               addino(ep->e_ino, ep->e_links);
+               } else {
+                       for (; np != NIL; np = np->e_links) {
+                               if (np->e_links == ep) {
+                                       np->e_links = ep->e_links;
+                                       break;
+                               }

                        }
                        }

+                       if (np == NIL)
+                               badentry(ep, "link not found");

                }
                }

-               if (np == NIL)
-                       badentry(ep, "link not found");

        }
        removeentry(ep);
        }
        removeentry(ep);

-       free(ep->e_name);
-       if (ep->e_newname != NULL)
-               free(ep->e_newname);
-       ep->e_sibling = freelist;
+       freename(ep->e_name);
+       ep->e_next = freelist;

        freelist = ep;
 }
 
        freelist = ep;
 }
 

-/*
- * change the number associated with an entry
- */
-renumber(ep, newinum)
-       struct entry *ep;
-       ino_t newinum;
-{
-       register struct entry *np;
-
-       if (lookupino(newinum) != NIL)
-               badentry(ep, "renumber to active inum");
-       np = lookupino(ep->e_ino);
-       if (np == NIL)
-               badentry(ep, "lookupino failed");
-       deleteino(ep->e_ino);
-       addino(newinum, ep);
-       for (; np != NIL; np = np->e_links)
-               np->e_ino = newinum;
-}
-

 /*
  * Relocate an entry in the tree structure
  */
 /*
  * Relocate an entry in the tree structure
  */


@@ -245,7 +266,6 @@ moveentry(ep, newname)
 {
        struct entry *np;
        char *cp;
 {
        struct entry *np;
        char *cp;

-       long len;

 
        np = lookupparent(newname);
        if (np == NIL)
 
        np = lookupparent(newname);
        if (np == NIL)


@@ -257,17 +277,10 @@ moveentry(ep, newname)
                np->e_entries = ep;
        }
        cp = rindex(newname, '/') + 1;
                np->e_entries = ep;
        }
        cp = rindex(newname, '/') + 1;

-       len = strlen(cp);
-       if (ep->e_flags & TMPNAME)
-               ep->e_namlen--;
-       if (ep->e_namlen >= len) {
-               strcpy(ep->e_name, cp);
-       } else {
-               free(ep->e_name);
-               ep->e_name = savename(cp);
-       }
-       ep->e_namlen = len;
-       if (cp[len - 1] == TMPCHAR)
+       freename(ep->e_name);
+       ep->e_name = savename(cp);
+       ep->e_namlen = strlen(cp);
+       if (strcmp(gentempname(ep), ep->e_name) == 0)

                ep->e_flags |= TMPNAME;
        else
                ep->e_flags &= ~TMPNAME;
                ep->e_flags |= TMPNAME;
        else
                ep->e_flags &= ~TMPNAME;


@@ -297,24 +310,81 @@ removeentry(ep)
 }
 
 /*
 }
 
 /*

- * allocate space for a name
+ * Table of unused string entries, sorted by length.
+ * 
+ * Entries are allocated in STRTBLINCR sized pieces so that names
+ * of similar lengths can use the same entry. The value of STRTBLINCR
+ * is chosen so that every entry has at least enough space to hold
+ * a "struct strtbl" header. Thus every entry can be linked onto an
+ * apprpriate free list.
+ *
+ * NB. The macro "allocsize" below assumes that "struct strhdr"
+ *     has a size that is a power of two.
+ */
+struct strhdr {
+       struct strhdr *next;
+};
+
+#define STRTBLINCR     (sizeof(struct strhdr))
+#define allocsize(size)        (((size) + 1 + STRTBLINCR - 1) & ~(STRTBLINCR - 1))
+
+static struct strhdr strtblhdr[allocsize(MAXNAMLEN) / STRTBLINCR];
+
+/*
+ * Allocate space for a name. It first looks to see if it already
+ * has an appropriate sized entry, and if not allocates a new one.

  */
 char *
 savename(name)
        char *name;
 {
  */
 char *
 savename(name)
        char *name;
 {

+       struct strhdr *np;

        long len;
        char *cp;
 
        if (name == NULL)
                panic("bad name\n");
        long len;
        char *cp;
 
        if (name == NULL)
                panic("bad name\n");

-       len = strlen(name) + 2;
-       len = (len + 3) & ~3;
-       cp = (char *)malloc((unsigned)len);
-       strcpy(cp, name);
+       len = strlen(name);
+       np = strtblhdr[len / STRTBLINCR].next;
+       if (np != NULL) {
+               strtblhdr[len / STRTBLINCR].next = np->next;
+               cp = (char *)np;
+       } else {
+               cp = malloc((unsigned)allocsize(len));
+               if (cp == NULL)
+                       panic("no space for string table\n");
+       }
+       (void) strcpy(cp, name);

        return (cp);
 }
 
        return (cp);
 }
 

+/*
+ * Free space for a name. The resulting entry is linked onto the
+ * appropriate free list.
+ */
+freename(name)
+       char *name;
+{
+       struct strhdr *tp, *np;
+       
+       tp = &strtblhdr[strlen(name) / STRTBLINCR];
+       np = (struct strhdr *)name;
+       np->next = tp->next;
+       tp->next = np;
+}
+
+/*
+ * Useful quantities placed at the end of a dumped symbol table.
+ */
+struct symtableheader {
+       long    volno;
+       long    stringsize;
+       long    entrytblsize;
+       time_t  dumptime;
+       time_t  dumpdate;
+       ino_t   maxino;
+};
+

 /*
  * dump a snapshot of the symbol table
  */
 /*
  * dump a snapshot of the symbol table
  */


@@ -322,10 +392,10 @@ dumpsymtable(filename, checkpt)
        char *filename;
        long checkpt;
 {
        char *filename;
        long checkpt;
 {

-       register struct entry *ep;
-       register long i;
-       struct entry *next;
-       long mynum = 0, stroff = 0;
+       register struct entry *ep, *tep;
+       register ino_t i;
+       struct entry temp, *tentry;
+       long mynum = 1, stroff = 0;

        FILE *fd;
        struct symtableheader hdr;
 
        FILE *fd;
        struct symtableheader hdr;
 


@@ -342,48 +412,61 @@ dumpsymtable(filename, checkpt)
         */
        for (i = ROOTINO; i < maxino; i++) {
                for (ep = lookupino(i); ep != NIL; ep = ep->e_links) {
         */
        for (i = ROOTINO; i < maxino; i++) {
                for (ep = lookupino(i); ep != NIL; ep = ep->e_links) {

-                       ep->e_newname = (char *)mynum++;
-                       fwrite(ep->e_name, sizeof(char), (int)ep->e_namlen, fd);
-                       ep->e_name = (char *)stroff;
-                       stroff += ep->e_namlen;
+                       ep->e_index = mynum++;
+                       (void) fwrite(ep->e_name, sizeof(char),
+                              (int)allocsize(ep->e_namlen), fd);

                }
        }
                }
        }

-       /*
-        * Convert entry pointers to indexes, and output
-        */
-       for (i = 0; i < maxino; i++) {
-               if (entry[i] == NIL)
-                       continue;
-               entry[i] = (struct entry *)entry[i]->e_newname;
-       }
-       fwrite((char *)entry, sizeof(struct entry *), (int)maxino, fd);

        /*
         * Convert pointers to indexes, and output
         */
        /*
         * Convert pointers to indexes, and output
         */

+       tep = &temp;
+       stroff = 0;

        for (i = ROOTINO; i < maxino; i++) {
        for (i = ROOTINO; i < maxino; i++) {

-               for (ep = lookupino(i); ep != NIL; ep = next) {
-                       next = ep->e_links;
-                       ep->e_parent = (struct entry *)ep->e_parent->e_newname;
-                       ep->e_links = (struct entry *)ep->e_links->e_newname;
-                       ep->e_sibling =
-                               (struct entry *)ep->e_sibling->e_newname;
-                       ep->e_entries =
-                               (struct entry *)ep->e_entries->e_newname;
-                       fwrite((char *)ep, sizeof(struct entry), 1, fd);
+               for (ep = lookupino(i); ep != NIL; ep = ep->e_links) {
+                       bcopy((char *)ep, (char *)tep,
+                               (long)sizeof(struct entry));
+                       tep->e_name = (char *)stroff;
+                       stroff += allocsize(ep->e_namlen);
+                       tep->e_parent = (struct entry *)ep->e_parent->e_index;
+                       if (ep->e_links != NIL)
+                               tep->e_links =
+                                       (struct entry *)ep->e_links->e_index;
+                       if (ep->e_sibling != NIL)
+                               tep->e_sibling =
+                                       (struct entry *)ep->e_sibling->e_index;
+                       if (ep->e_entries != NIL)
+                               tep->e_entries =
+                                       (struct entry *)ep->e_entries->e_index;
+                       if (ep->e_next != NIL)
+                               tep->e_next =
+                                       (struct entry *)ep->e_next->e_index;
+                       (void) fwrite((char *)tep, sizeof(struct entry), 1, fd);

                }
        }
                }
        }

+       /*
+        * Convert entry pointers to indexes, and output
+        */
+       for (i = 0; i < entrytblsize; i++) {
+               if (entry[i] == NIL)
+                       tentry = NIL;
+               else
+                       tentry = (struct entry *)entry[i]->e_index;
+               (void) fwrite((char *)&tentry, sizeof(struct entry *), 1, fd);
+       }

        hdr.volno = checkpt;
        hdr.maxino = maxino;
        hdr.volno = checkpt;
        hdr.maxino = maxino;

+       hdr.entrytblsize = entrytblsize;

        hdr.stringsize = stroff;
        hdr.dumptime = dumptime;
        hdr.dumpdate = dumpdate;
        hdr.stringsize = stroff;
        hdr.dumptime = dumptime;
        hdr.dumpdate = dumpdate;

-       fwrite((char *)&hdr, sizeof(struct symtableheader), 1, fd);
+       (void) fwrite((char *)&hdr, sizeof(struct symtableheader), 1, fd);

        if (ferror(fd)) {
                perror("fwrite");
                panic("output error to file %s writing symbol table\n",
                        filename);
        }
        if (ferror(fd)) {
                perror("fwrite");
                panic("output error to file %s writing symbol table\n",
                        filename);
        }

-       fclose(fd);
+       (void) fclose(fd);

 }
 
 /*
 }
 
 /*


@@ -402,6 +485,16 @@ initsymtable(filename)
        int fd;
 
        vprintf(stdout, "Initialize symbol table.\n");
        int fd;
 
        vprintf(stdout, "Initialize symbol table.\n");

+       if (filename == NULL) {
+               entrytblsize = maxino / HASHFACTOR;
+               entry = (struct entry **)
+                       calloc((unsigned)entrytblsize, sizeof(struct entry *));
+               if (entry == (struct entry **)NIL)
+                       panic("no memory for entry table\n");
+               ep = addentry(".", ROOTINO, NODE);
+               ep->e_flags |= NEW;
+               return;
+       }

        if ((fd = open(filename, 0)) < 0) {
                perror("open");
                panic("cannot open symbol table file %s\n", filename);
        if ((fd = open(filename, 0)) < 0) {
                perror("open");
                panic("cannot open symbol table file %s\n", filename);


@@ -411,7 +504,7 @@ initsymtable(filename)
                panic("cannot stat symbol table file %s\n", filename);
        }
        tblsize = stbuf.st_size - sizeof(struct symtableheader);
                panic("cannot stat symbol table file %s\n", filename);
        }
        tblsize = stbuf.st_size - sizeof(struct symtableheader);

-       base = (char *)malloc((unsigned)tblsize);
+       base = calloc(sizeof(char *), (unsigned)tblsize);

        if (base == NULL)
                panic("cannot allocate space for symbol table\n");
        if (read(fd, base, (int)tblsize) < 0 ||
        if (base == NULL)
                panic("cannot allocate space for symbol table\n");
        if (read(fd, base, (int)tblsize) < 0 ||


@@ -425,8 +518,8 @@ initsymtable(filename)
                 * For normal continuation, insure that we are using
                 * the next incremental tape
                 */
                 * For normal continuation, insure that we are using
                 * the next incremental tape
                 */

-               if (hdr.dumptime != dumpdate) {
-                       if (hdr.dumptime < dumpdate)
+               if (hdr.dumpdate != dumptime) {
+                       if (hdr.dumpdate < dumptime)

                                fprintf(stderr, "Incremental tape too low\n");
                        else
                                fprintf(stderr, "Incremental tape too high\n");
                                fprintf(stderr, "Incremental tape too low\n");
                        else
                                fprintf(stderr, "Incremental tape too high\n");


@@ -447,19 +540,26 @@ initsymtable(filename)
                break;
        }
        maxino = hdr.maxino;
                break;
        }
        maxino = hdr.maxino;

-       entry = (struct entry **)(base + hdr.stringsize);
-       baseep = (struct entry *)(&entry[maxino]);
-       lep = (struct entry *)(base + tblsize);
-       for (i = 0; i < maxino; i++) {
+       entrytblsize = hdr.entrytblsize;
+       entry = (struct entry **)
+               (base + tblsize - (entrytblsize * sizeof(struct entry *)));
+       baseep = (struct entry *)(base + hdr.stringsize - sizeof(struct entry));
+       lep = (struct entry *)entry;
+       for (i = 0; i < entrytblsize; i++) {

                if (entry[i] == NIL)
                        continue;
                entry[i] = &baseep[(long)entry[i]];
        }
                if (entry[i] == NIL)
                        continue;
                entry[i] = &baseep[(long)entry[i]];
        }

-       for (ep = baseep; ep < lep; ep++) {
+       for (ep = &baseep[1]; ep < lep; ep++) {

                ep->e_name = base + (long)ep->e_name;
                ep->e_parent = &baseep[(long)ep->e_parent];
                ep->e_name = base + (long)ep->e_name;
                ep->e_parent = &baseep[(long)ep->e_parent];

-               ep->e_sibling = &baseep[(long)ep->e_sibling];
-               ep->e_links = &baseep[(long)ep->e_links];
-               ep->e_entries = &baseep[(long)ep->e_entries];
+               if (ep->e_sibling != NIL)
+                       ep->e_sibling = &baseep[(long)ep->e_sibling];
+               if (ep->e_links != NIL)
+                       ep->e_links = &baseep[(long)ep->e_links];
+               if (ep->e_entries != NIL)
+                       ep->e_entries = &baseep[(long)ep->e_entries];
+               if (ep->e_next != NIL)
+                       ep->e_next = &baseep[(long)ep->e_next];

        }
 }
        }
 }