147082Smckusick /*- 247082Smckusick * Copyright (c) 1980, 1988, 1991 The Regents of the University of California. 347082Smckusick * All rights reserved. 447082Smckusick * 547082Smckusick * %sccs.include.redist.c% 622041Sdist */ 75329Smckusic 822041Sdist #ifndef lint 9*54070Smckusick static char sccsid[] = "@(#)traverse.c 5.18 (Berkeley) 06/18/92"; 1046584Storek #endif /* not lint */ 1122041Sdist 1250499Smckusick #ifdef sunos 1350499Smckusick #include <stdio.h> 1450499Smckusick #include <ctype.h> 1546795Sbostic #include <sys/param.h> 1651605Sbostic #include <ufs/fs.h> 1750499Smckusick #else 1850499Smckusick #include <sys/param.h> 19*54070Smckusick #include <ufs/ffs/fs.h> 20*54070Smckusick #endif 2153657Smckusick #include <sys/time.h> 22*54070Smckusick #include <sys/stat.h> 2351605Sbostic #include <ufs/ufs/dir.h> 2451605Sbostic #include <ufs/ufs/dinode.h> 2546795Sbostic #include <protocols/dumprestore.h> 2646795Sbostic #ifdef __STDC__ 2746795Sbostic #include <unistd.h> 2846795Sbostic #include <string.h> 2946795Sbostic #endif 301426Sroot #include "dump.h" 311426Sroot 3246792Smckusick void dmpindir(); 3346792Smckusick #define HASDUMPEDFILE 0x1 3446792Smckusick #define HASSUBDIRS 0x2 3546584Storek 3646584Storek /* 3746584Storek * This is an estimation of the number of TP_BSIZE blocks in the file. 3846584Storek * It estimates the number of blocks in files with holes by assuming 3946584Storek * that all of the blocks accounted for by di_blocks are data blocks 4046584Storek * (when some of the blocks are usually used for indirect pointers); 4146584Storek * hence the estimate may be high. 4246584Storek */ 4346792Smckusick long 4447058Smckusick blockest(dp) 4547058Smckusick register struct dinode *dp; 4646584Storek { 4746792Smckusick long blkest, sizeest; 4846584Storek 4946584Storek /* 5047058Smckusick * dp->di_size is the size of the file in bytes. 5147058Smckusick * dp->di_blocks stores the number of sectors actually in the file. 5246584Storek * If there are more sectors than the size would indicate, this just 5346584Storek * means that there are indirect blocks in the file or unused 5446584Storek * sectors in the last file block; we can safely ignore these 5546792Smckusick * (blkest = sizeest below). 5646584Storek * If the file is bigger than the number of sectors would indicate, 5746584Storek * then the file has holes in it. In this case we must use the 5846584Storek * block count to estimate the number of data blocks used, but 5946584Storek * we use the actual size for estimating the number of indirect 6046792Smckusick * dump blocks (sizeest vs. blkest in the indirect block 6146792Smckusick * calculation). 6246584Storek */ 6347058Smckusick blkest = howmany(dbtob(dp->di_blocks), TP_BSIZE); 6447058Smckusick sizeest = howmany(dp->di_size, TP_BSIZE); 6546792Smckusick if (blkest > sizeest) 6646792Smckusick blkest = sizeest; 6747058Smckusick if (dp->di_size > sblock->fs_bsize * NDADDR) { 6846584Storek /* calculate the number of indirect blocks on the dump tape */ 6946792Smckusick blkest += 7046792Smckusick howmany(sizeest - NDADDR * sblock->fs_bsize / TP_BSIZE, 7146584Storek TP_NINDIR); 7246584Storek } 7346792Smckusick return (blkest + 1); 7446584Storek } 7546584Storek 7646792Smckusick /* 7746792Smckusick * Dump pass 1. 7846792Smckusick * 7946792Smckusick * Walk the inode list for a filesystem to find all allocated inodes 8046792Smckusick * that have been modified since the previous dump time. Also, find all 8146792Smckusick * the directories in the filesystem. 8246792Smckusick */ 8346792Smckusick mapfiles(maxino, tapesize) 8446792Smckusick ino_t maxino; 8546792Smckusick long *tapesize; 8646584Storek { 8746792Smckusick register int mode; 8846792Smckusick register ino_t ino; 8946792Smckusick register struct dinode *dp; 9046792Smckusick int anydirskipped = 0; 9146584Storek 9246792Smckusick for (ino = 0; ino < maxino; ino++) { 9346792Smckusick dp = getino(ino); 9446792Smckusick if ((mode = (dp->di_mode & IFMT)) == 0) 9546792Smckusick continue; 9646792Smckusick SETINO(ino, usedinomap); 9746792Smckusick if (mode == IFDIR) 9846792Smckusick SETINO(ino, dumpdirmap); 99*54070Smckusick if ((dp->di_mtime.ts_sec >= spcl.c_ddate || 100*54070Smckusick dp->di_ctime.ts_sec >= spcl.c_ddate) 101*54070Smckusick #ifndef sunos 102*54070Smckusick && (dp->di_flags & NODUMP) != NODUMP 103*54070Smckusick #endif 104*54070Smckusick ) { 10546792Smckusick SETINO(ino, dumpinomap); 10646792Smckusick if (mode != IFREG && mode != IFDIR && mode != IFLNK) { 10746792Smckusick *tapesize += 1; 10846792Smckusick continue; 10946792Smckusick } 11046792Smckusick *tapesize += blockest(dp); 11146792Smckusick continue; 11246792Smckusick } 11346792Smckusick if (mode == IFDIR) 11446792Smckusick anydirskipped = 1; 11546792Smckusick } 11646792Smckusick /* 11746792Smckusick * Restore gets very upset if the root is not dumped, 11846792Smckusick * so ensure that it always is dumped. 11946792Smckusick */ 12051374Smckusick SETINO(ROOTINO, dumpinomap); 12146792Smckusick return (anydirskipped); 12246584Storek } 12346584Storek 12446792Smckusick /* 12546792Smckusick * Dump pass 2. 12646792Smckusick * 12746792Smckusick * Scan each directory on the filesystem to see if it has any modified 12846792Smckusick * files in it. If it does, and has not already been added to the dump 12946792Smckusick * list (because it was itself modified), then add it. If a directory 13046792Smckusick * has not been modified itself, contains no modified files and has no 13146792Smckusick * subdirectories, then it can be deleted from the dump list and from 13246792Smckusick * the list of directories. By deleting it from the list of directories, 13346792Smckusick * its parent may now qualify for the same treatment on this or a later 13446792Smckusick * pass using this algorithm. 13546792Smckusick */ 13646792Smckusick mapdirs(maxino, tapesize) 13746792Smckusick ino_t maxino; 13846792Smckusick long *tapesize; 13946792Smckusick { 14046792Smckusick register struct dinode *dp; 14147058Smckusick register int i, dirty; 14225797Smckusick register char *map; 14346792Smckusick register ino_t ino; 144*54070Smckusick long filesize; 14546792Smckusick int ret, change = 0; 1461426Sroot 14746792Smckusick for (map = dumpdirmap, ino = 0; ino < maxino; ) { 14846584Storek if ((ino % NBBY) == 0) 14947058Smckusick dirty = *map++; 15046792Smckusick else 15147058Smckusick dirty >>= 1; 1524702Smckusic ino++; 15347058Smckusick if ((dirty & 1) == 0 || TSTINO(ino, dumpinomap)) 15446792Smckusick continue; 15546792Smckusick dp = getino(ino); 15646792Smckusick filesize = dp->di_size; 15746792Smckusick for (ret = 0, i = 0; filesize > 0 && i < NDADDR; i++) { 15846792Smckusick if (dp->di_db[i] != 0) 15946792Smckusick ret |= searchdir(ino, dp->di_db[i], 16046796Smckusick dblksize(sblock, dp, i), filesize); 16146792Smckusick if (ret & HASDUMPEDFILE) 16246792Smckusick filesize = 0; 16346792Smckusick else 16446792Smckusick filesize -= sblock->fs_bsize; 16546792Smckusick } 16646792Smckusick for (i = 0; filesize > 0 && i < NIADDR; i++) { 16746792Smckusick if (dp->di_ib[i] == 0) 16846792Smckusick continue; 16946792Smckusick ret |= dirindir(ino, dp->di_ib[i], i, &filesize); 17046792Smckusick } 17146792Smckusick if (ret & HASDUMPEDFILE) { 17246792Smckusick if (!TSTINO(ino, dumpinomap)) { 17346792Smckusick SETINO(ino, dumpinomap); 17446792Smckusick *tapesize += blockest(dp); 17546792Smckusick } 17646792Smckusick change = 1; 17746792Smckusick continue; 17846792Smckusick } 17946792Smckusick if ((ret & HASSUBDIRS) == 0) { 18046792Smckusick if (!TSTINO(ino, dumpinomap)) { 18146792Smckusick CLRINO(ino, dumpdirmap); 18246792Smckusick change = 1; 18346792Smckusick } 18446792Smckusick } 1851426Sroot } 18646792Smckusick return (change); 1871426Sroot } 1881426Sroot 18946792Smckusick /* 19046792Smckusick * Read indirect blocks, and pass the data blocks to be searched 19146792Smckusick * as directories. Quit as soon as any entry is found that will 19246792Smckusick * require the directory to be dumped. 19346792Smckusick */ 194*54070Smckusick dirindir(ino, blkno, ind_level, filesize) 19546792Smckusick ino_t ino; 19646792Smckusick daddr_t blkno; 197*54070Smckusick int ind_level; 198*54070Smckusick long *filesize; 1991426Sroot { 20046792Smckusick int ret = 0; 20146792Smckusick register int i; 20246792Smckusick daddr_t idblk[MAXNINDIR]; 2031426Sroot 204*54070Smckusick bread(fsbtodb(sblock, blkno), (char *)idblk, (int)sblock->fs_bsize); 205*54070Smckusick if (ind_level <= 0) { 20646792Smckusick for (i = 0; *filesize > 0 && i < NINDIR(sblock); i++) { 20746792Smckusick blkno = idblk[i]; 20846792Smckusick if (blkno != 0) 20946796Smckusick ret |= searchdir(ino, blkno, sblock->fs_bsize, 210*54070Smckusick *filesize); 21146792Smckusick if (ret & HASDUMPEDFILE) 21246792Smckusick *filesize = 0; 21346792Smckusick else 21446792Smckusick *filesize -= sblock->fs_bsize; 2151426Sroot } 21646792Smckusick return (ret); 2175329Smckusic } 218*54070Smckusick ind_level--; 21946792Smckusick for (i = 0; *filesize > 0 && i < NINDIR(sblock); i++) { 22046792Smckusick blkno = idblk[i]; 22146792Smckusick if (blkno != 0) 222*54070Smckusick ret |= dirindir(ino, blkno, ind_level, filesize); 2235329Smckusic } 22446792Smckusick return (ret); 2251426Sroot } 2261426Sroot 22746792Smckusick /* 22846792Smckusick * Scan a disk block containing directory information looking to see if 22946792Smckusick * any of the entries are on the dump list and to see if the directory 23046792Smckusick * contains any subdirectories. 23146792Smckusick */ 23246796Smckusick searchdir(ino, blkno, size, filesize) 23346792Smckusick ino_t ino; 23446792Smckusick daddr_t blkno; 235*54070Smckusick register long size; 236*54070Smckusick long filesize; 2375329Smckusic { 23846792Smckusick register struct direct *dp; 23946792Smckusick register long loc; 24046792Smckusick char dblk[MAXBSIZE]; 2415329Smckusic 242*54070Smckusick bread(fsbtodb(sblock, blkno), dblk, (int)size); 24346796Smckusick if (filesize < size) 24446796Smckusick size = filesize; 24546792Smckusick for (loc = 0; loc < size; ) { 24646792Smckusick dp = (struct direct *)(dblk + loc); 24746792Smckusick if (dp->d_reclen == 0) { 24846792Smckusick msg("corrupted directory, inumber %d\n", ino); 24946792Smckusick break; 2505329Smckusic } 25146792Smckusick loc += dp->d_reclen; 25246792Smckusick if (dp->d_ino == 0) 25346792Smckusick continue; 25446792Smckusick if (dp->d_name[0] == '.') { 25546792Smckusick if (dp->d_name[1] == '\0') 25646792Smckusick continue; 25746792Smckusick if (dp->d_name[1] == '.' && dp->d_name[2] == '\0') 25846792Smckusick continue; 2595329Smckusic } 26046792Smckusick if (TSTINO(dp->d_ino, dumpinomap)) 26146792Smckusick return (HASDUMPEDFILE); 26246792Smckusick if (TSTINO(dp->d_ino, dumpdirmap)) 26346792Smckusick return (HASSUBDIRS); 2645329Smckusic } 26546792Smckusick return (0); 2665329Smckusic } 2675329Smckusic 26846792Smckusick /* 26946792Smckusick * Dump passes 3 and 4. 27046792Smckusick * 27146792Smckusick * Dump the contents of an inode to tape. 27246792Smckusick */ 27346584Storek void 27447058Smckusick dumpino(dp, ino) 27547058Smckusick register struct dinode *dp; 27646792Smckusick ino_t ino; 27717234Smckusick { 278*54070Smckusick int mode, ind_level, cnt; 2794777Smckusic long size; 2801426Sroot 28146792Smckusick if (newtape) { 2821426Sroot newtape = 0; 28346792Smckusick dumpmap(dumpinomap, TS_BITS, ino); 2841426Sroot } 28546792Smckusick CLRINO(ino, dumpinomap); 28647058Smckusick spcl.c_dinode = *dp; 2871426Sroot spcl.c_type = TS_INODE; 2881426Sroot spcl.c_count = 0; 28946792Smckusick /* 29046792Smckusick * Check for freed inode. 29146792Smckusick */ 29247058Smckusick if ((mode = (dp->di_mode & IFMT)) == 0) 29317234Smckusick return; 29446792Smckusick if ((mode != IFDIR && mode != IFREG && mode != IFLNK) || 29547058Smckusick dp->di_size == 0) { 29646792Smckusick writeheader(ino); 2971426Sroot return; 2981426Sroot } 29947058Smckusick if (dp->di_size > NDADDR * sblock->fs_bsize) 30046792Smckusick cnt = NDADDR * sblock->fs_frag; 3014777Smckusic else 30247058Smckusick cnt = howmany(dp->di_size, sblock->fs_fsize); 30347058Smckusick blksout(&dp->di_db[0], cnt, ino); 30447058Smckusick if ((size = dp->di_size - NDADDR * sblock->fs_bsize) <= 0) 3054777Smckusic return; 306*54070Smckusick for (ind_level = 0; ind_level < NIADDR; ind_level++) { 307*54070Smckusick dmpindir(ino, dp->di_ib[ind_level], ind_level, &size); 3084777Smckusic if (size <= 0) 3094777Smckusic return; 3104777Smckusic } 3111426Sroot } 3121426Sroot 31346792Smckusick /* 31446792Smckusick * Read indirect blocks, and pass the data blocks to be dumped. 31546792Smckusick */ 31646584Storek void 317*54070Smckusick dmpindir(ino, blk, ind_level, size) 31846792Smckusick ino_t ino; 3194777Smckusic daddr_t blk; 320*54070Smckusick int ind_level; 3214777Smckusic long *size; 3221426Sroot { 3234777Smckusic int i, cnt; 3245329Smckusic daddr_t idblk[MAXNINDIR]; 3251426Sroot 3264777Smckusic if (blk != 0) 327*54070Smckusick bread(fsbtodb(sblock, blk), (char *)idblk, (int) sblock->fs_bsize); 3284777Smckusic else 329*54070Smckusick bzero((char *)idblk, (int)sblock->fs_bsize); 330*54070Smckusick if (ind_level <= 0) { 3315329Smckusic if (*size < NINDIR(sblock) * sblock->fs_bsize) 3325329Smckusic cnt = howmany(*size, sblock->fs_fsize); 3334777Smckusic else 3345329Smckusic cnt = NINDIR(sblock) * sblock->fs_frag; 3355329Smckusic *size -= NINDIR(sblock) * sblock->fs_bsize; 33646792Smckusick blksout(&idblk[0], cnt, ino); 3374777Smckusic return; 3381426Sroot } 339*54070Smckusick ind_level--; 3405329Smckusic for (i = 0; i < NINDIR(sblock); i++) { 341*54070Smckusick dmpindir(ino, idblk[i], ind_level, size); 3424777Smckusic if (*size <= 0) 3434777Smckusic return; 3444777Smckusic } 3451426Sroot } 3461426Sroot 34746792Smckusick /* 34846792Smckusick * Collect up the data into tape record sized buffers and output them. 34946792Smckusick */ 35046584Storek void 35146792Smckusick blksout(blkp, frags, ino) 3524777Smckusic daddr_t *blkp; 3534777Smckusic int frags; 35446792Smckusick ino_t ino; 3554777Smckusic { 35646584Storek register daddr_t *bp; 3575329Smckusic int i, j, count, blks, tbperdb; 3584777Smckusic 3599403Smckusick blks = howmany(frags * sblock->fs_fsize, TP_BSIZE); 36046584Storek tbperdb = sblock->fs_bsize >> tp_bshift; 3614777Smckusic for (i = 0; i < blks; i += TP_NINDIR) { 3624777Smckusic if (i + TP_NINDIR > blks) 3634777Smckusic count = blks; 3644777Smckusic else 3654777Smckusic count = i + TP_NINDIR; 3664777Smckusic for (j = i; j < count; j++) 3675329Smckusic if (blkp[j / tbperdb] != 0) 3684777Smckusic spcl.c_addr[j - i] = 1; 3694777Smckusic else 3704777Smckusic spcl.c_addr[j - i] = 0; 3714777Smckusic spcl.c_count = count - i; 37246792Smckusick writeheader(ino); 37346584Storek bp = &blkp[i / tbperdb]; 37446584Storek for (j = i; j < count; j += tbperdb, bp++) 37546584Storek if (*bp != 0) 3765329Smckusic if (j + tbperdb <= count) 377*54070Smckusick dumpblock(*bp, (int)sblock->fs_bsize); 3784777Smckusic else 37946792Smckusick dumpblock(*bp, (count - j) * TP_BSIZE); 3804777Smckusic spcl.c_type = TS_ADDR; 3814777Smckusic } 3824777Smckusic } 3834777Smckusic 38446792Smckusick /* 38546792Smckusick * Dump a map to the tape. 38646792Smckusick */ 38746584Storek void 38846792Smckusick dumpmap(map, type, ino) 3895329Smckusic char *map; 39046792Smckusick int type; 39146792Smckusick ino_t ino; 3921426Sroot { 39346792Smckusick register int i; 3941426Sroot char *cp; 3951426Sroot 39646792Smckusick spcl.c_type = type; 39746792Smckusick spcl.c_count = howmany(mapsize * sizeof(char), TP_BSIZE); 39846792Smckusick writeheader(ino); 3995329Smckusic for (i = 0, cp = map; i < spcl.c_count; i++, cp += TP_BSIZE) 40046792Smckusick writerec(cp); 4011426Sroot } 4021426Sroot 40346792Smckusick /* 40446792Smckusick * Write a header record to the dump tape. 40546792Smckusick */ 40646584Storek void 40746792Smckusick writeheader(ino) 40846792Smckusick ino_t ino; 4091426Sroot { 41046792Smckusick register long sum, cnt, *lp; 4111426Sroot 4121426Sroot spcl.c_inumber = ino; 4138368Smckusick spcl.c_magic = NFS_MAGIC; 4141426Sroot spcl.c_checksum = 0; 41546792Smckusick lp = (long *)&spcl; 41646792Smckusick sum = 0; 41746792Smckusick cnt = sizeof(union u_spcl) / (4 * sizeof(long)); 41846792Smckusick while (--cnt >= 0) { 41946792Smckusick sum += *lp++; 42046792Smckusick sum += *lp++; 42146792Smckusick sum += *lp++; 42246792Smckusick sum += *lp++; 42324168Smckusick } 42446792Smckusick spcl.c_checksum = CHECKSUM - sum; 42546792Smckusick writerec((char *)&spcl); 4261426Sroot } 4271426Sroot 4284702Smckusic struct dinode * 42946792Smckusick getino(inum) 43046792Smckusick ino_t inum; 4314702Smckusic { 4324702Smckusic static daddr_t minino, maxino; 43346792Smckusick static struct dinode inoblock[MAXINOPB]; 4344702Smckusic 43546792Smckusick curino = inum; 43646792Smckusick if (inum >= minino && inum < maxino) 43746792Smckusick return (&inoblock[inum - minino]); 438*54070Smckusick bread(fsbtodb(sblock, itod(sblock, inum)), (char *)inoblock, 439*54070Smckusick (int)sblock->fs_bsize); 44046792Smckusick minino = inum - (inum % INOPB(sblock)); 4415329Smckusic maxino = minino + INOPB(sblock); 44246792Smckusick return (&inoblock[inum - minino]); 4434702Smckusic } 4444702Smckusic 44546792Smckusick /* 44646792Smckusick * Read a chunk of data from the disk. 44746792Smckusick * Try to recover from hard errors by reading in sector sized pieces. 44846792Smckusick * Error recovery is attempted at most BREADEMAX times before seeking 44946792Smckusick * consent from the operator to continue. 45046792Smckusick */ 4511426Sroot int breaderrors = 0; 4521426Sroot #define BREADEMAX 32 4531426Sroot 45446584Storek void 45546792Smckusick bread(blkno, buf, size) 45646792Smckusick daddr_t blkno; 45746792Smckusick char *buf; 45846792Smckusick int size; 4591426Sroot { 46046792Smckusick int cnt, i; 46134359Skarels extern int errno; 4621426Sroot 46315095Smckusick loop: 464*54070Smckusick if ((int)lseek(diskfd, ((off_t)blkno << dev_bshift), 0) < 0) 4651426Sroot msg("bread: lseek fails\n"); 46646792Smckusick if ((cnt = read(diskfd, buf, size)) == size) 46715095Smckusick return; 46846792Smckusick if (blkno + (size / dev_bsize) > fsbtodb(sblock, sblock->fs_size)) { 46915095Smckusick /* 47015095Smckusick * Trying to read the final fragment. 47115095Smckusick * 47215095Smckusick * NB - dump only works in TP_BSIZE blocks, hence 47330560Smckusick * rounds `dev_bsize' fragments up to TP_BSIZE pieces. 47415095Smckusick * It should be smarter about not actually trying to 47515095Smckusick * read more than it can get, but for the time being 47615095Smckusick * we punt and scale back the read only when it gets 47715095Smckusick * us into trouble. (mkm 9/25/83) 47815095Smckusick */ 47946792Smckusick size -= dev_bsize; 48015095Smckusick goto loop; 4811426Sroot } 48250905Smckusick if (cnt == -1) 48350905Smckusick msg("read error from %s: %s: [block %d]: count=%d\n", 48450905Smckusick disk, strerror(errno), blkno, size); 48550905Smckusick else 48650905Smckusick msg("short read error from %s: [block %d]: count=%d, got=%d\n", 48750905Smckusick disk, blkno, size, cnt); 48846584Storek if (++breaderrors > BREADEMAX) { 48915095Smckusick msg("More than %d block read errors from %d\n", 49015095Smckusick BREADEMAX, disk); 49115095Smckusick broadcast("DUMP IS AILING!\n"); 49215095Smckusick msg("This is an unrecoverable error.\n"); 49315095Smckusick if (!query("Do you want to attempt to continue?")){ 49415095Smckusick dumpabort(); 49515095Smckusick /*NOTREACHED*/ 49615095Smckusick } else 49715095Smckusick breaderrors = 0; 49815095Smckusick } 49934359Skarels /* 50034359Skarels * Zero buffer, then try to read each sector of buffer separately. 50134359Skarels */ 50246792Smckusick bzero(buf, size); 50346792Smckusick for (i = 0; i < size; i += dev_bsize, buf += dev_bsize, blkno++) { 504*54070Smckusick if ((int)lseek(diskfd, ((off_t)blkno << dev_bshift), 0) < 0) 50534359Skarels msg("bread: lseek2 fails!\n"); 506*54070Smckusick if ((cnt = read(diskfd, buf, (int)dev_bsize)) == dev_bsize) 50750905Smckusick continue; 50850905Smckusick if (cnt == -1) { 50950905Smckusick msg("read error from %s: %s: [sector %d]: count=%d\n", 51050905Smckusick disk, strerror(errno), blkno, dev_bsize); 51150905Smckusick continue; 51250905Smckusick } 51350905Smckusick msg("short read error from %s: [sector %d]: count=%d, got=%d\n", 51450905Smckusick disk, blkno, dev_bsize, cnt); 51534359Skarels } 5161426Sroot } 517