home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Source Code 1993 July / THE_SOURCE_CODE_CD_ROM.iso / bsd_srcs / sbin / dump / traverse.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-01-25  |  14.5 KB  |  581 lines
  1. /*-
  2.  * Copyright (c) 1980, 1988, 1991 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[] = "@(#)traverse.c    5.22 (Berkeley) 1/25/93";
  36. #endif /* not lint */
  37.  
  38. #ifdef sunos
  39. #include <stdio.h>
  40. #include <ctype.h>
  41. #include <sys/param.h>
  42. #include <ufs/fs.h>
  43. #else
  44. #include <sys/param.h>
  45. #include <ufs/ffs/fs.h>
  46. #endif
  47. #include <sys/time.h>
  48. #include <sys/stat.h>
  49. #include <ufs/ufs/dir.h>
  50. #include <ufs/ufs/dinode.h>
  51. #include <protocols/dumprestore.h>
  52. #ifdef __STDC__
  53. #include <unistd.h>
  54. #include <string.h>
  55. #endif
  56. #include "dump.h"
  57.  
  58. void    dmpindir();
  59. #define    HASDUMPEDFILE    0x1
  60. #define    HASSUBDIRS    0x2
  61.  
  62. /*
  63.  * This is an estimation of the number of TP_BSIZE blocks in the file.
  64.  * It estimates the number of blocks in files with holes by assuming
  65.  * that all of the blocks accounted for by di_blocks are data blocks
  66.  * (when some of the blocks are usually used for indirect pointers);
  67.  * hence the estimate may be high.
  68.  */
  69. long
  70. blockest(dp)
  71.     register struct dinode *dp;
  72. {
  73.     long blkest, sizeest;
  74.  
  75.     /*
  76.      * dp->di_size is the size of the file in bytes.
  77.      * dp->di_blocks stores the number of sectors actually in the file.
  78.      * If there are more sectors than the size would indicate, this just
  79.      *    means that there are indirect blocks in the file or unused
  80.      *    sectors in the last file block; we can safely ignore these
  81.      *    (blkest = sizeest below).
  82.      * If the file is bigger than the number of sectors would indicate,
  83.      *    then the file has holes in it.    In this case we must use the
  84.      *    block count to estimate the number of data blocks used, but
  85.      *    we use the actual size for estimating the number of indirect
  86.      *    dump blocks (sizeest vs. blkest in the indirect block
  87.      *    calculation).
  88.      */
  89.     blkest = howmany(dbtob(dp->di_blocks), TP_BSIZE);
  90.     sizeest = howmany(dp->di_size, TP_BSIZE);
  91.     if (blkest > sizeest)
  92.         blkest = sizeest;
  93.     if (dp->di_size > sblock->fs_bsize * NDADDR) {
  94.         /* calculate the number of indirect blocks on the dump tape */
  95.         blkest +=
  96.             howmany(sizeest - NDADDR * sblock->fs_bsize / TP_BSIZE,
  97.             TP_NINDIR);
  98.     }
  99.     return (blkest + 1);
  100. }
  101.  
  102. /*
  103.  * Dump pass 1.
  104.  *
  105.  * Walk the inode list for a filesystem to find all allocated inodes
  106.  * that have been modified since the previous dump time. Also, find all
  107.  * the directories in the filesystem.
  108.  */
  109. mapfiles(maxino, tapesize)
  110.     ino_t maxino;
  111.     long *tapesize;
  112. {
  113.     register int mode;
  114.     register ino_t ino;
  115.     register struct dinode *dp;
  116.     int anydirskipped = 0;
  117.  
  118.     for (ino = 0; ino <= maxino; ino++) {
  119.         dp = getino(ino);
  120.         if ((mode = (dp->di_mode & IFMT)) == 0)
  121.             continue;
  122.         SETINO(ino, usedinomap);
  123.         if (mode == IFDIR)
  124.             SETINO(ino, dumpdirmap);
  125.         if ((dp->di_mtime.ts_sec >= spcl.c_ddate ||
  126.             dp->di_ctime.ts_sec >= spcl.c_ddate)
  127. #ifndef sunos
  128.             && (dp->di_flags & NODUMP) != NODUMP
  129. #endif
  130.             ) {
  131.             SETINO(ino, dumpinomap);
  132.             if (mode != IFREG && mode != IFDIR && mode != IFLNK) {
  133.                 *tapesize += 1;
  134.                 continue;
  135.             }
  136.             *tapesize += blockest(dp);
  137.             continue;
  138.         }
  139.         if (mode == IFDIR)
  140.             anydirskipped = 1;
  141.     }
  142.     /*
  143.      * Restore gets very upset if the root is not dumped,
  144.      * so ensure that it always is dumped.
  145.      */
  146.     SETINO(ROOTINO, dumpinomap);
  147.     return (anydirskipped);
  148. }
  149.  
  150. /*
  151.  * Dump pass 2.
  152.  *
  153.  * Scan each directory on the filesystem to see if it has any modified
  154.  * files in it. If it does, and has not already been added to the dump
  155.  * list (because it was itself modified), then add it. If a directory
  156.  * has not been modified itself, contains no modified files and has no
  157.  * subdirectories, then it can be deleted from the dump list and from
  158.  * the list of directories. By deleting it from the list of directories,
  159.  * its parent may now qualify for the same treatment on this or a later
  160.  * pass using this algorithm.
  161.  */
  162. mapdirs(maxino, tapesize)
  163.     ino_t maxino;
  164.     long *tapesize;
  165. {
  166.     register struct    dinode *dp;
  167.     register int i, isdir;
  168.     register char *map;
  169.     register ino_t ino;
  170.     long filesize;
  171.     int ret, change = 0;
  172.  
  173.     for (map = dumpdirmap, ino = 0; ino < maxino; ) {
  174.         if ((ino % NBBY) == 0)
  175.             isdir = *map++;
  176.         else
  177.             isdir >>= 1;
  178.         ino++;
  179.         if ((isdir & 1) == 0 || TSTINO(ino, dumpinomap))
  180.             continue;
  181.         dp = getino(ino);
  182.         filesize = dp->di_size;
  183.         for (ret = 0, i = 0; filesize > 0 && i < NDADDR; i++) {
  184.             if (dp->di_db[i] != 0)
  185.                 ret |= searchdir(ino, dp->di_db[i],
  186.                     (long)dblksize(sblock, dp, i),
  187.                     filesize);
  188.             if (ret & HASDUMPEDFILE)
  189.                 filesize = 0;
  190.             else
  191.                 filesize -= sblock->fs_bsize;
  192.         }
  193.         for (i = 0; filesize > 0 && i < NIADDR; i++) {
  194.             if (dp->di_ib[i] == 0)
  195.                 continue;
  196.             ret |= dirindir(ino, dp->di_ib[i], i, &filesize);
  197.         }
  198.         if (ret & HASDUMPEDFILE) {
  199.             SETINO(ino, dumpinomap);
  200.             *tapesize += blockest(dp);
  201.             change = 1;
  202.             continue;
  203.         }
  204.         if ((ret & HASSUBDIRS) == 0) {
  205.             if (!TSTINO(ino, dumpinomap)) {
  206.                 CLRINO(ino, dumpdirmap);
  207.                 change = 1;
  208.             }
  209.         }
  210.     }
  211.     return (change);
  212. }
  213.  
  214. /*
  215.  * Read indirect blocks, and pass the data blocks to be searched
  216.  * as directories. Quit as soon as any entry is found that will
  217.  * require the directory to be dumped.
  218.  */
  219. dirindir(ino, blkno, ind_level, filesize)
  220.     ino_t ino;
  221.     daddr_t blkno;
  222.     int ind_level;
  223.     long *filesize;
  224. {
  225.     int ret = 0;
  226.     register int i;
  227.     daddr_t    idblk[MAXNINDIR];
  228.  
  229.     bread(fsbtodb(sblock, blkno), (char *)idblk, (int)sblock->fs_bsize);
  230.     if (ind_level <= 0) {
  231.         for (i = 0; *filesize > 0 && i < NINDIR(sblock); i++) {
  232.             blkno = idblk[i];
  233.             if (blkno != 0)
  234.                 ret |= searchdir(ino, blkno, sblock->fs_bsize,
  235.                     *filesize);
  236.             if (ret & HASDUMPEDFILE)
  237.                 *filesize = 0;
  238.             else
  239.                 *filesize -= sblock->fs_bsize;
  240.         }
  241.         return (ret);
  242.     }
  243.     ind_level--;
  244.     for (i = 0; *filesize > 0 && i < NINDIR(sblock); i++) {
  245.         blkno = idblk[i];
  246.         if (blkno != 0)
  247.             ret |= dirindir(ino, blkno, ind_level, filesize);
  248.     }
  249.     return (ret);
  250. }
  251.  
  252. /*
  253.  * Scan a disk block containing directory information looking to see if
  254.  * any of the entries are on the dump list and to see if the directory
  255.  * contains any subdirectories.
  256.  */
  257. searchdir(ino, blkno, size, filesize)
  258.     ino_t ino;
  259.     daddr_t blkno;
  260.     register long size;
  261.     long filesize;
  262. {
  263.     register struct direct *dp;
  264.     register long loc, ret = 0;
  265.     char dblk[MAXBSIZE];
  266.  
  267.     bread(fsbtodb(sblock, blkno), dblk, (int)size);
  268.     if (filesize < size)
  269.         size = filesize;
  270.     for (loc = 0; loc < size; ) {
  271.         dp = (struct direct *)(dblk + loc);
  272.         if (dp->d_reclen == 0) {
  273.             msg("corrupted directory, inumber %d\n", ino);
  274.             break;
  275.         }
  276.         loc += dp->d_reclen;
  277.         if (dp->d_ino == 0)
  278.             continue;
  279.         if (dp->d_name[0] == '.') {
  280.             if (dp->d_name[1] == '\0')
  281.                 continue;
  282.             if (dp->d_name[1] == '.' && dp->d_name[2] == '\0')
  283.                 continue;
  284.         }
  285.         if (TSTINO(dp->d_ino, dumpinomap)) {
  286.             ret |= HASDUMPEDFILE;
  287.             if (ret & HASSUBDIRS)
  288.                 break;
  289.         }
  290.         if (TSTINO(dp->d_ino, dumpdirmap)) {
  291.             ret |= HASSUBDIRS;
  292.             if (ret & HASDUMPEDFILE)
  293.                 break;
  294.         }
  295.     }
  296.     return (ret);
  297. }
  298.  
  299. /*
  300.  * Dump passes 3 and 4.
  301.  *
  302.  * Dump the contents of an inode to tape.
  303.  */
  304. void
  305. dumpino(dp, ino)
  306.     register struct dinode *dp;
  307.     ino_t ino;
  308. {
  309.     int ind_level, cnt;
  310.     long size;
  311.     char buf[TP_BSIZE];
  312.  
  313.     if (newtape) {
  314.         newtape = 0;
  315.         dumpmap(dumpinomap, TS_BITS, ino);
  316.     }
  317.     CLRINO(ino, dumpinomap);
  318.     spcl.c_dinode = *dp;
  319.     spcl.c_type = TS_INODE;
  320.     spcl.c_count = 0;
  321.     switch (IFTODT(dp->di_mode)) {
  322.  
  323.     case DT_UNKNOWN:
  324.         /*
  325.          * Freed inode.
  326.          */
  327.         return;
  328.  
  329.     case DT_LNK:
  330.         /*
  331.          * Check for short symbolic link.
  332.          */
  333.         if (dp->di_size > 0 &&
  334.             dp->di_size < sblock->fs_maxsymlinklen) {
  335.             spcl.c_addr[0] = 1;
  336.             spcl.c_count = 1;
  337.             writeheader(ino);
  338.             bcopy((caddr_t)dp->di_shortlink, buf,
  339.                 (u_long)dp->di_size);
  340.             buf[dp->di_size] = '\0';
  341.             writerec(buf, 0);
  342.             return;
  343.         }
  344.         /* fall through */
  345.  
  346.     case DT_DIR:
  347.     case DT_REG:
  348.         if (dp->di_size > 0)
  349.             break;
  350.         /* fall through */
  351.  
  352.     case DT_FIFO:
  353.     case DT_SOCK:
  354.     case DT_CHR:
  355.     case DT_BLK:
  356.         writeheader(ino);
  357.         return;
  358.  
  359.     default:
  360.         msg("Warning: undefined file type 0%o\n", dp->di_mode & IFMT);
  361.         return;
  362.     }
  363.     if (dp->di_size > NDADDR * sblock->fs_bsize)
  364.         cnt = NDADDR * sblock->fs_frag;
  365.     else
  366.         cnt = howmany(dp->di_size, sblock->fs_fsize);
  367.     blksout(&dp->di_db[0], cnt, ino);
  368.     if ((size = dp->di_size - NDADDR * sblock->fs_bsize) <= 0)
  369.         return;
  370.     for (ind_level = 0; ind_level < NIADDR; ind_level++) {
  371.         dmpindir(ino, dp->di_ib[ind_level], ind_level, &size);
  372.         if (size <= 0)
  373.             return;
  374.     }
  375. }
  376.  
  377. /*
  378.  * Read indirect blocks, and pass the data blocks to be dumped.
  379.  */
  380. void
  381. dmpindir(ino, blk, ind_level, size)
  382.     ino_t ino;
  383.     daddr_t blk;
  384.     int ind_level;
  385.     long *size;
  386. {
  387.     int i, cnt;
  388.     daddr_t idblk[MAXNINDIR];
  389.  
  390.     if (blk != 0)
  391.         bread(fsbtodb(sblock, blk), (char *)idblk, (int) sblock->fs_bsize);
  392.     else
  393.         bzero((char *)idblk, (int)sblock->fs_bsize);
  394.     if (ind_level <= 0) {
  395.         if (*size < NINDIR(sblock) * sblock->fs_bsize)
  396.             cnt = howmany(*size, sblock->fs_fsize);
  397.         else
  398.             cnt = NINDIR(sblock) * sblock->fs_frag;
  399.         *size -= NINDIR(sblock) * sblock->fs_bsize;
  400.         blksout(&idblk[0], cnt, ino);
  401.         return;
  402.     }
  403.     ind_level--;
  404.     for (i = 0; i < NINDIR(sblock); i++) {
  405.         dmpindir(ino, idblk[i], ind_level, size);
  406.         if (*size <= 0)
  407.             return;
  408.     }
  409. }
  410.  
  411. /*
  412.  * Collect up the data into tape record sized buffers and output them.
  413.  */
  414. void
  415. blksout(blkp, frags, ino)
  416.     daddr_t *blkp;
  417.     int frags;
  418.     ino_t ino;
  419. {
  420.     register daddr_t *bp;
  421.     int i, j, count, blks, tbperdb;
  422.  
  423.     blks = howmany(frags * sblock->fs_fsize, TP_BSIZE);
  424.     tbperdb = sblock->fs_bsize >> tp_bshift;
  425.     for (i = 0; i < blks; i += TP_NINDIR) {
  426.         if (i + TP_NINDIR > blks)
  427.             count = blks;
  428.         else
  429.             count = i + TP_NINDIR;
  430.         for (j = i; j < count; j++)
  431.             if (blkp[j / tbperdb] != 0)
  432.                 spcl.c_addr[j - i] = 1;
  433.             else
  434.                 spcl.c_addr[j - i] = 0;
  435.         spcl.c_count = count - i;
  436.         writeheader(ino);
  437.         bp = &blkp[i / tbperdb];
  438.         for (j = i; j < count; j += tbperdb, bp++)
  439.             if (*bp != 0)
  440.                 if (j + tbperdb <= count)
  441.                     dumpblock(*bp, (int)sblock->fs_bsize);
  442.                 else
  443.                     dumpblock(*bp, (count - j) * TP_BSIZE);
  444.         spcl.c_type = TS_ADDR;
  445.     }
  446. }
  447.  
  448. /*
  449.  * Dump a map to the tape.
  450.  */
  451. void
  452. dumpmap(map, type, ino)
  453.     char *map;
  454.     int type;
  455.     ino_t ino;
  456. {
  457.     register int i;
  458.     char *cp;
  459.  
  460.     spcl.c_type = type;
  461.     spcl.c_count = howmany(mapsize * sizeof(char), TP_BSIZE);
  462.     writeheader(ino);
  463.     for (i = 0, cp = map; i < spcl.c_count; i++, cp += TP_BSIZE)
  464.         writerec(cp, 0);
  465. }
  466.  
  467. /*
  468.  * Write a header record to the dump tape.
  469.  */
  470. void
  471. writeheader(ino)
  472.     ino_t ino;
  473. {
  474.     register long sum, cnt, *lp;
  475.  
  476.     spcl.c_inumber = ino;
  477.     spcl.c_magic = NFS_MAGIC;
  478.     spcl.c_checksum = 0;
  479.     lp = (long *)&spcl;
  480.     sum = 0;
  481.     cnt = sizeof(union u_spcl) / (4 * sizeof(long));
  482.     while (--cnt >= 0) {
  483.         sum += *lp++;
  484.         sum += *lp++;
  485.         sum += *lp++;
  486.         sum += *lp++;
  487.     }
  488.     spcl.c_checksum = CHECKSUM - sum;
  489.     writerec((char *)&spcl, 1);
  490. }
  491.  
  492. struct dinode *
  493. getino(inum)
  494.     ino_t inum;
  495. {
  496.     static daddr_t minino, maxino;
  497.     static struct dinode inoblock[MAXINOPB];
  498.  
  499.     curino = inum;
  500.     if (inum >= minino && inum < maxino)
  501.         return (&inoblock[inum - minino]);
  502.     bread(fsbtodb(sblock, itod(sblock, inum)), (char *)inoblock,
  503.         (int)sblock->fs_bsize);
  504.     minino = inum - (inum % INOPB(sblock));
  505.     maxino = minino + INOPB(sblock);
  506.     return (&inoblock[inum - minino]);
  507. }
  508.  
  509. /*
  510.  * Read a chunk of data from the disk.
  511.  * Try to recover from hard errors by reading in sector sized pieces.
  512.  * Error recovery is attempted at most BREADEMAX times before seeking
  513.  * consent from the operator to continue.
  514.  */
  515. int    breaderrors = 0;        
  516. #define    BREADEMAX 32
  517.  
  518. void
  519. bread(blkno, buf, size)
  520.     daddr_t blkno;
  521.     char *buf;
  522.     int size;    
  523. {
  524.     int cnt, i;
  525.     extern int errno;
  526.  
  527. loop:
  528.     if ((int)lseek(diskfd, ((off_t)blkno << dev_bshift), 0) < 0)
  529.         msg("bread: lseek fails\n");
  530.     if ((cnt = read(diskfd, buf, size)) == size)
  531.         return;
  532.     if (blkno + (size / dev_bsize) > fsbtodb(sblock, sblock->fs_size)) {
  533.         /*
  534.          * Trying to read the final fragment.
  535.          *
  536.          * NB - dump only works in TP_BSIZE blocks, hence
  537.          * rounds `dev_bsize' fragments up to TP_BSIZE pieces.
  538.          * It should be smarter about not actually trying to
  539.          * read more than it can get, but for the time being
  540.          * we punt and scale back the read only when it gets
  541.          * us into trouble. (mkm 9/25/83)
  542.          */
  543.         size -= dev_bsize;
  544.         goto loop;
  545.     }
  546.     if (cnt == -1)
  547.         msg("read error from %s: %s: [block %d]: count=%d\n",
  548.             disk, strerror(errno), blkno, size);
  549.     else
  550.         msg("short read error from %s: [block %d]: count=%d, got=%d\n",
  551.             disk, blkno, size, cnt);
  552.     if (++breaderrors > BREADEMAX) {
  553.         msg("More than %d block read errors from %d\n",
  554.             BREADEMAX, disk);
  555.         broadcast("DUMP IS AILING!\n");
  556.         msg("This is an unrecoverable error.\n");
  557.         if (!query("Do you want to attempt to continue?")){
  558.             dumpabort(0);
  559.             /*NOTREACHED*/
  560.         } else
  561.             breaderrors = 0;
  562.     }
  563.     /*
  564.      * Zero buffer, then try to read each sector of buffer separately.
  565.      */
  566.     bzero(buf, size);
  567.     for (i = 0; i < size; i += dev_bsize, buf += dev_bsize, blkno++) {
  568.         if ((int)lseek(diskfd, ((off_t)blkno << dev_bshift), 0) < 0)
  569.             msg("bread: lseek2 fails!\n");
  570.         if ((cnt = read(diskfd, buf, (int)dev_bsize)) == dev_bsize)
  571.             continue;
  572.         if (cnt == -1) {
  573.             msg("read error from %s: %s: [sector %d]: count=%d\n",
  574.                 disk, strerror(errno), blkno, dev_bsize);
  575.             continue;
  576.         }
  577.         msg("short read error from %s: [sector %d]: count=%d, got=%d\n",
  578.             disk, blkno, dev_bsize, cnt);
  579.     }
  580. }
  581.