home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Source Code 1993 July / THE_SOURCE_CODE_CD_ROM.iso / bsd_srcs / sbin / restore / symtab.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-10-16  |  15.3 KB  |  630 lines
  1. /*
  2.  * Copyright (c) 1983 The Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * Redistribution and use in source and binary forms, with or without
  6.  * modification, are permitted provided that the following conditions
  7.  * are met:
  8.  * 1. Redistributions of source code must retain the above copyright
  9.  *    notice, this list of conditions and the following disclaimer.
  10.  * 2. Redistributions in binary form must reproduce the above copyright
  11.  *    notice, this list of conditions and the following disclaimer in the
  12.  *    documentation and/or other materials provided with the distribution.
  13.  * 3. All advertising materials mentioning features or use of this software
  14.  *    must display the following acknowledgement:
  15.  *    This product includes software developed by the University of
  16.  *    California, Berkeley and its contributors.
  17.  * 4. Neither the name of the University nor the names of its contributors
  18.  *    may be used to endorse or promote products derived from this software
  19.  *    without specific prior written permission.
  20.  *
  21.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  22.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  23.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  24.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  25.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  26.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  27.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  30.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  31.  * SUCH DAMAGE.
  32.  */
  33.  
  34. #ifndef lint
  35. static char sccsid[] = "@(#)symtab.c    5.7 (Berkeley) 10/16/92";
  36. #endif /* not lint */
  37.  
  38. /*
  39.  * These routines maintain the symbol table which tracks the state
  40.  * of the file system being restored. They provide lookup by either
  41.  * name or inode number. They also provide for creation, deletion,
  42.  * and renaming of entries. Because of the dynamic nature of pathnames,
  43.  * names should not be saved, but always constructed just before they
  44.  * are needed, by calling "myname".
  45.  */
  46.  
  47. #include <sys/param.h>
  48. #include <sys/stat.h>
  49.  
  50. #include <ufs/ufs/dinode.h>
  51.  
  52. #include <errno.h>
  53. #include <fcntl.h>
  54. #include <stdio.h>
  55. #include <stdlib.h>
  56. #include <string.h>
  57. #include <unistd.h>
  58.  
  59. #include "restore.h"
  60. #include "extern.h"
  61.  
  62. /*
  63.  * The following variables define the inode symbol table.
  64.  * The primary hash table is dynamically allocated based on
  65.  * the number of inodes in the file system (maxino), scaled by
  66.  * HASHFACTOR. The variable "entry" points to the hash table;
  67.  * the variable "entrytblsize" indicates its size (in entries).
  68.  */
  69. #define HASHFACTOR 5
  70. static struct entry **entry;
  71. static long entrytblsize;
  72.  
  73. static void         addino __P((ino_t, struct entry *));
  74. static struct entry    *lookupparent __P((char *));
  75. static void         removeentry __P((struct entry *));
  76.  
  77. /*
  78.  * Look up an entry by inode number
  79.  */
  80. struct entry *
  81. lookupino(inum)
  82.     ino_t inum;
  83. {
  84.     register struct entry *ep;
  85.  
  86.     if (inum < ROOTINO || inum >= maxino)
  87.         return (NULL);
  88.     for (ep = entry[inum % entrytblsize]; ep != NULL; ep = ep->e_next)
  89.         if (ep->e_ino == inum)
  90.             return (ep);
  91.     return (NULL);
  92. }
  93.  
  94. /*
  95.  * Add an entry into the entry table
  96.  */
  97. static void
  98. addino(inum, np)
  99.     ino_t inum;
  100.     struct entry *np;
  101. {
  102.     struct entry **epp;
  103.  
  104.     if (inum < ROOTINO || inum >= maxino)
  105.         panic("addino: out of range %d\n", inum);
  106.     epp = &entry[inum % entrytblsize];
  107.     np->e_ino = inum;
  108.     np->e_next = *epp;
  109.     *epp = np;
  110.     if (dflag)
  111.         for (np = np->e_next; np != NULL; np = np->e_next)
  112.             if (np->e_ino == inum)
  113.                 badentry(np, "duplicate inum");
  114. }
  115.  
  116. /*
  117.  * Delete an entry from the entry table
  118.  */
  119. void
  120. deleteino(inum)
  121.     ino_t inum;
  122. {
  123.     register struct entry *next;
  124.     struct entry **prev;
  125.  
  126.     if (inum < ROOTINO || inum >= maxino)
  127.         panic("deleteino: out of range %d\n", inum);
  128.     prev = &entry[inum % entrytblsize];
  129.     for (next = *prev; next != NULL; next = next->e_next) {
  130.         if (next->e_ino == inum) {
  131.             next->e_ino = 0;
  132.             *prev = next->e_next;
  133.             return;
  134.         }
  135.         prev = &next->e_next;
  136.     }
  137.     panic("deleteino: %d not found\n", inum);
  138. }
  139.  
  140. /*
  141.  * Look up an entry by name
  142.  */
  143. struct entry *
  144. lookupname(name)
  145.     char *name;
  146. {
  147.     register struct entry *ep;
  148.     register char *np, *cp;
  149.     char buf[MAXPATHLEN];
  150.  
  151.     cp = name;
  152.     for (ep = lookupino(ROOTINO); ep != NULL; ep = ep->e_entries) {
  153.         for (np = buf; *cp != '/' && *cp != '\0'; )
  154.             *np++ = *cp++;
  155.         *np = '\0';
  156.         for ( ; ep != NULL; ep = ep->e_sibling)
  157.             if (strcmp(ep->e_name, buf) == 0)
  158.                 break;
  159.         if (ep == NULL)
  160.             break;
  161.         if (*cp++ == '\0')
  162.             return (ep);
  163.     }
  164.     return (NULL);
  165. }
  166.  
  167. /*
  168.  * Look up the parent of a pathname
  169.  */
  170. static struct entry *
  171. lookupparent(name)
  172.     char *name;
  173. {
  174.     struct entry *ep;
  175.     char *tailindex;
  176.  
  177.     tailindex = rindex(name, '/');
  178.     if (tailindex == 0)
  179.         return (NULL);
  180.     *tailindex = '\0';
  181.     ep = lookupname(name);
  182.     *tailindex = '/';
  183.     if (ep == NULL)
  184.         return (NULL);
  185.     if (ep->e_type != NODE)
  186.         panic("%s is not a directory\n", name);
  187.     return (ep);
  188. }
  189.  
  190. /*
  191.  * Determine the current pathname of a node or leaf
  192.  */
  193. char *
  194. myname(ep)
  195.     register struct entry *ep;
  196. {
  197.     register char *cp;
  198.     static char namebuf[MAXPATHLEN];
  199.  
  200.     for (cp = &namebuf[MAXPATHLEN - 2]; cp > &namebuf[ep->e_namlen]; ) {
  201.         cp -= ep->e_namlen;
  202.         bcopy(ep->e_name, cp, (long)ep->e_namlen);
  203.         if (ep == lookupino(ROOTINO))
  204.             return (cp);
  205.         *(--cp) = '/';
  206.         ep = ep->e_parent;
  207.     }
  208.     panic("%s: pathname too long\n", cp);
  209.     return(cp);
  210. }
  211.  
  212. /*
  213.  * Unused symbol table entries are linked together on a freelist
  214.  * headed by the following pointer.
  215.  */
  216. static struct entry *freelist = NULL;
  217.  
  218. /*
  219.  * add an entry to the symbol table
  220.  */
  221. struct entry *
  222. addentry(name, inum, type)
  223.     char *name;
  224.     ino_t inum;
  225.     int type;
  226. {
  227.     register struct entry *np, *ep;
  228.  
  229.     if (freelist != NULL) {
  230.         np = freelist;
  231.         freelist = np->e_next;
  232.         bzero((char *)np, (long)sizeof(struct entry));
  233.     } else {
  234.         np = (struct entry *)calloc(1, sizeof(struct entry));
  235.         if (np == NULL)
  236.             panic("no memory to extend symbol table\n");
  237.     }
  238.     np->e_type = type & ~LINK;
  239.     ep = lookupparent(name);
  240.     if (ep == NULL) {
  241.         if (inum != ROOTINO || lookupino(ROOTINO) != NULL)
  242.             panic("bad name to addentry %s\n", name);
  243.         np->e_name = savename(name);
  244.         np->e_namlen = strlen(name);
  245.         np->e_parent = np;
  246.         addino(ROOTINO, np);
  247.         return (np);
  248.     }
  249.     np->e_name = savename(rindex(name, '/') + 1);
  250.     np->e_namlen = strlen(np->e_name);
  251.     np->e_parent = ep;
  252.     np->e_sibling = ep->e_entries;
  253.     ep->e_entries = np;
  254.     if (type & LINK) {
  255.         ep = lookupino(inum);
  256.         if (ep == NULL)
  257.             panic("link to non-existant name\n");
  258.         np->e_ino = inum;
  259.         np->e_links = ep->e_links;
  260.         ep->e_links = np;
  261.     } else if (inum != 0) {
  262.         if (lookupino(inum) != NULL)
  263.             panic("duplicate entry\n");
  264.         addino(inum, np);
  265.     }
  266.     return (np);
  267. }
  268.  
  269. /*
  270.  * delete an entry from the symbol table
  271.  */
  272. void
  273. freeentry(ep)
  274.     register struct entry *ep;
  275. {
  276.     register struct entry *np;
  277.     ino_t inum;
  278.  
  279.     if (ep->e_flags != REMOVED)
  280.         badentry(ep, "not marked REMOVED");
  281.     if (ep->e_type == NODE) {
  282.         if (ep->e_links != NULL)
  283.             badentry(ep, "freeing referenced directory");
  284.         if (ep->e_entries != NULL)
  285.             badentry(ep, "freeing non-empty directory");
  286.     }
  287.     if (ep->e_ino != 0) {
  288.         np = lookupino(ep->e_ino);
  289.         if (np == NULL)
  290.             badentry(ep, "lookupino failed");
  291.         if (np == ep) {
  292.             inum = ep->e_ino;
  293.             deleteino(inum);
  294.             if (ep->e_links != NULL)
  295.                 addino(inum, ep->e_links);
  296.         } else {
  297.             for (; np != NULL; np = np->e_links) {
  298.                 if (np->e_links == ep) {
  299.                     np->e_links = ep->e_links;
  300.                     break;
  301.                 }
  302.             }
  303.             if (np == NULL)
  304.                 badentry(ep, "link not found");
  305.         }
  306.     }
  307.     removeentry(ep);
  308.     freename(ep->e_name);
  309.     ep->e_next = freelist;
  310.     freelist = ep;
  311. }
  312.  
  313. /*
  314.  * Relocate an entry in the tree structure
  315.  */
  316. void
  317. moveentry(ep, newname)
  318.     register struct entry *ep;
  319.     char *newname;
  320. {
  321.     struct entry *np;
  322.     char *cp;
  323.  
  324.     np = lookupparent(newname);
  325.     if (np == NULL)
  326.         badentry(ep, "cannot move ROOT");
  327.     if (np != ep->e_parent) {
  328.         removeentry(ep);
  329.         ep->e_parent = np;
  330.         ep->e_sibling = np->e_entries;
  331.         np->e_entries = ep;
  332.     }
  333.     cp = rindex(newname, '/') + 1;
  334.     freename(ep->e_name);
  335.     ep->e_name = savename(cp);
  336.     ep->e_namlen = strlen(cp);
  337.     if (strcmp(gentempname(ep), ep->e_name) == 0)
  338.         ep->e_flags |= TMPNAME;
  339.     else
  340.         ep->e_flags &= ~TMPNAME;
  341. }
  342.  
  343. /*
  344.  * Remove an entry in the tree structure
  345.  */
  346. static void
  347. removeentry(ep)
  348.     register struct entry *ep;
  349. {
  350.     register struct entry *np;
  351.  
  352.     np = ep->e_parent;
  353.     if (np->e_entries == ep) {
  354.         np->e_entries = ep->e_sibling;
  355.     } else {
  356.         for (np = np->e_entries; np != NULL; np = np->e_sibling) {
  357.             if (np->e_sibling == ep) {
  358.                 np->e_sibling = ep->e_sibling;
  359.                 break;
  360.             }
  361.         }
  362.         if (np == NULL)
  363.             badentry(ep, "cannot find entry in parent list");
  364.     }
  365. }
  366.  
  367. /*
  368.  * Table of unused string entries, sorted by length.
  369.  * 
  370.  * Entries are allocated in STRTBLINCR sized pieces so that names
  371.  * of similar lengths can use the same entry. The value of STRTBLINCR
  372.  * is chosen so that every entry has at least enough space to hold
  373.  * a "struct strtbl" header. Thus every entry can be linked onto an
  374.  * apprpriate free list.
  375.  *
  376.  * NB. The macro "allocsize" below assumes that "struct strhdr"
  377.  *     has a size that is a power of two.
  378.  */
  379. struct strhdr {
  380.     struct strhdr *next;
  381. };
  382.  
  383. #define STRTBLINCR    (sizeof(struct strhdr))
  384. #define allocsize(size)    (((size) + 1 + STRTBLINCR - 1) & ~(STRTBLINCR - 1))
  385.  
  386. static struct strhdr strtblhdr[allocsize(NAME_MAX) / STRTBLINCR];
  387.  
  388. /*
  389.  * Allocate space for a name. It first looks to see if it already
  390.  * has an appropriate sized entry, and if not allocates a new one.
  391.  */
  392. char *
  393. savename(name)
  394.     char *name;
  395. {
  396.     struct strhdr *np;
  397.     long len;
  398.     char *cp;
  399.  
  400.     if (name == NULL)
  401.         panic("bad name\n");
  402.     len = strlen(name);
  403.     np = strtblhdr[len / STRTBLINCR].next;
  404.     if (np != NULL) {
  405.         strtblhdr[len / STRTBLINCR].next = np->next;
  406.         cp = (char *)np;
  407.     } else {
  408.         cp = malloc((unsigned)allocsize(len));
  409.         if (cp == NULL)
  410.             panic("no space for string table\n");
  411.     }
  412.     (void) strcpy(cp, name);
  413.     return (cp);
  414. }
  415.  
  416. /*
  417.  * Free space for a name. The resulting entry is linked onto the
  418.  * appropriate free list.
  419.  */
  420. void
  421. freename(name)
  422.     char *name;
  423. {
  424.     struct strhdr *tp, *np;
  425.     
  426.     tp = &strtblhdr[strlen(name) / STRTBLINCR];
  427.     np = (struct strhdr *)name;
  428.     np->next = tp->next;
  429.     tp->next = np;
  430. }
  431.  
  432. /*
  433.  * Useful quantities placed at the end of a dumped symbol table.
  434.  */
  435. struct symtableheader {
  436.     long    volno;
  437.     long    stringsize;
  438.     long    entrytblsize;
  439.     time_t    dumptime;
  440.     time_t    dumpdate;
  441.     ino_t    maxino;
  442.     long    ntrec;
  443. };
  444.  
  445. /*
  446.  * dump a snapshot of the symbol table
  447.  */
  448. void
  449. dumpsymtable(filename, checkpt)
  450.     char *filename;
  451.     long checkpt;
  452. {
  453.     register struct entry *ep, *tep;
  454.     register ino_t i;
  455.     struct entry temp, *tentry;
  456.     long mynum = 1, stroff = 0;
  457.     FILE *fd;
  458.     struct symtableheader hdr;
  459.  
  460.     vprintf(stdout, "Check pointing the restore\n");
  461.     if (Nflag)
  462.         return;
  463.     if ((fd = fopen(filename, "w")) == NULL) {
  464.         fprintf(stderr, "fopen: %s\n", strerror(errno));
  465.         panic("cannot create save file %s for symbol table\n",
  466.             filename);
  467.     }
  468.     clearerr(fd);
  469.     /*
  470.      * Assign indicies to each entry
  471.      * Write out the string entries
  472.      */
  473.     for (i = ROOTINO; i < maxino; i++) {
  474.         for (ep = lookupino(i); ep != NULL; ep = ep->e_links) {
  475.             ep->e_index = mynum++;
  476.             (void) fwrite(ep->e_name, sizeof(char),
  477.                    (int)allocsize(ep->e_namlen), fd);
  478.         }
  479.     }
  480.     /*
  481.      * Convert pointers to indexes, and output
  482.      */
  483.     tep = &temp;
  484.     stroff = 0;
  485.     for (i = ROOTINO; i < maxino; i++) {
  486.         for (ep = lookupino(i); ep != NULL; ep = ep->e_links) {
  487.             bcopy((char *)ep, (char *)tep,
  488.                 (long)sizeof(struct entry));
  489.             tep->e_name = (char *)stroff;
  490.             stroff += allocsize(ep->e_namlen);
  491.             tep->e_parent = (struct entry *)ep->e_parent->e_index;
  492.             if (ep->e_links != NULL)
  493.                 tep->e_links =
  494.                     (struct entry *)ep->e_links->e_index;
  495.             if (ep->e_sibling != NULL)
  496.                 tep->e_sibling =
  497.                     (struct entry *)ep->e_sibling->e_index;
  498.             if (ep->e_entries != NULL)
  499.                 tep->e_entries =
  500.                     (struct entry *)ep->e_entries->e_index;
  501.             if (ep->e_next != NULL)
  502.                 tep->e_next =
  503.                     (struct entry *)ep->e_next->e_index;
  504.             (void) fwrite((char *)tep, sizeof(struct entry), 1, fd);
  505.         }
  506.     }
  507.     /*
  508.      * Convert entry pointers to indexes, and output
  509.      */
  510.     for (i = 0; i < entrytblsize; i++) {
  511.         if (entry[i] == NULL)
  512.             tentry = NULL;
  513.         else
  514.             tentry = (struct entry *)entry[i]->e_index;
  515.         (void) fwrite((char *)&tentry, sizeof(struct entry *), 1, fd);
  516.     }
  517.     hdr.volno = checkpt;
  518.     hdr.maxino = maxino;
  519.     hdr.entrytblsize = entrytblsize;
  520.     hdr.stringsize = stroff;
  521.     hdr.dumptime = dumptime;
  522.     hdr.dumpdate = dumpdate;
  523.     hdr.ntrec = ntrec;
  524.     (void) fwrite((char *)&hdr, sizeof(struct symtableheader), 1, fd);
  525.     if (ferror(fd)) {
  526.         fprintf(stderr, "fwrite: %s\n", strerror(errno));
  527.         panic("output error to file %s writing symbol table\n",
  528.             filename);
  529.     }
  530.     (void) fclose(fd);
  531. }
  532.  
  533. /*
  534.  * Initialize a symbol table from a file
  535.  */
  536. void
  537. initsymtable(filename)
  538.     char *filename;
  539. {
  540.     char *base;
  541.     long tblsize;
  542.     register struct entry *ep;
  543.     struct entry *baseep, *lep;
  544.     struct symtableheader hdr;
  545.     struct stat stbuf;
  546.     register long i;
  547.     int fd;
  548.  
  549.     vprintf(stdout, "Initialize symbol table.\n");
  550.     if (filename == NULL) {
  551.         entrytblsize = maxino / HASHFACTOR;
  552.         entry = (struct entry **)
  553.             calloc((unsigned)entrytblsize, sizeof(struct entry *));
  554.         if (entry == (struct entry **)NULL)
  555.             panic("no memory for entry table\n");
  556.         ep = addentry(".", ROOTINO, NODE);
  557.         ep->e_flags |= NEW;
  558.         return;
  559.     }
  560.     if ((fd = open(filename, O_RDONLY, 0)) < 0) {
  561.         fprintf(stderr, "open: %s\n", strerror(errno));
  562.         panic("cannot open symbol table file %s\n", filename);
  563.     }
  564.     if (fstat(fd, &stbuf) < 0) {
  565.         fprintf(stderr, "stat: %s\n", strerror(errno));
  566.         panic("cannot stat symbol table file %s\n", filename);
  567.     }
  568.     tblsize = stbuf.st_size - sizeof(struct symtableheader);
  569.     base = calloc(sizeof(char), (unsigned)tblsize);
  570.     if (base == NULL)
  571.         panic("cannot allocate space for symbol table\n");
  572.     if (read(fd, base, (int)tblsize) < 0 ||
  573.         read(fd, (char *)&hdr, sizeof(struct symtableheader)) < 0) {
  574.         fprintf(stderr, "read: %s\n", strerror(errno));
  575.         panic("cannot read symbol table file %s\n", filename);
  576.     }
  577.     switch (command) {
  578.     case 'r':
  579.         /*
  580.          * For normal continuation, insure that we are using
  581.          * the next incremental tape
  582.          */
  583.         if (hdr.dumpdate != dumptime) {
  584.             if (hdr.dumpdate < dumptime)
  585.                 fprintf(stderr, "Incremental tape too low\n");
  586.             else
  587.                 fprintf(stderr, "Incremental tape too high\n");
  588.             done(1);
  589.         }
  590.         break;
  591.     case 'R':
  592.         /*
  593.          * For restart, insure that we are using the same tape
  594.          */
  595.         curfile.action = SKIP;
  596.         dumptime = hdr.dumptime;
  597.         dumpdate = hdr.dumpdate;
  598.         if (!bflag)
  599.             newtapebuf(hdr.ntrec);
  600.         getvol(hdr.volno);
  601.         break;
  602.     default:
  603.         panic("initsymtable called from command %c\n", command);
  604.         break;
  605.     }
  606.     maxino = hdr.maxino;
  607.     entrytblsize = hdr.entrytblsize;
  608.     entry = (struct entry **)
  609.         (base + tblsize - (entrytblsize * sizeof(struct entry *)));
  610.     baseep = (struct entry *)(base + hdr.stringsize - sizeof(struct entry));
  611.     lep = (struct entry *)entry;
  612.     for (i = 0; i < entrytblsize; i++) {
  613.         if (entry[i] == NULL)
  614.             continue;
  615.         entry[i] = &baseep[(long)entry[i]];
  616.     }
  617.     for (ep = &baseep[1]; ep < lep; ep++) {
  618.         ep->e_name = base + (long)ep->e_name;
  619.         ep->e_parent = &baseep[(long)ep->e_parent];
  620.         if (ep->e_sibling != NULL)
  621.             ep->e_sibling = &baseep[(long)ep->e_sibling];
  622.         if (ep->e_links != NULL)
  623.             ep->e_links = &baseep[(long)ep->e_links];
  624.         if (ep->e_entries != NULL)
  625.             ep->e_entries = &baseep[(long)ep->e_entries];
  626.         if (ep->e_next != NULL)
  627.             ep->e_next = &baseep[(long)ep->e_next];
  628.     }
  629. }
  630.