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*50905Smckusick static char sccsid[] = "@(#)traverse.c 5.13 (Berkeley) 08/28/91"; 1046584Storek #endif /* not lint */ 1122041Sdist 1250499Smckusick #ifdef sunos 1350499Smckusick #include <stdio.h> 1450499Smckusick #include <ctype.h> 1546795Sbostic #include <sys/param.h> 1650499Smckusick #include <sys/stat.h> 1750499Smckusick #include <sys/time.h> 1850499Smckusick #include <sys/dir.h> 1950499Smckusick #include <sys/vnode.h> 2050499Smckusick #include <ufs/inode.h> 2150499Smckusick #else 2250499Smckusick #include <sys/param.h> 2346795Sbostic #include <ufs/dir.h> 2446795Sbostic #include <ufs/dinode.h> 2550499Smckusick #endif 2646795Sbostic #include <ufs/fs.h> 2746795Sbostic #include <protocols/dumprestore.h> 2846795Sbostic #ifdef __STDC__ 2946795Sbostic #include <unistd.h> 3046795Sbostic #include <string.h> 3146795Sbostic #endif 321426Sroot #include "dump.h" 331426Sroot 3446792Smckusick void dmpindir(); 3546792Smckusick #define HASDUMPEDFILE 0x1 3646792Smckusick #define HASSUBDIRS 0x2 3746584Storek 3846584Storek /* 3946584Storek * This is an estimation of the number of TP_BSIZE blocks in the file. 4046584Storek * It estimates the number of blocks in files with holes by assuming 4146584Storek * that all of the blocks accounted for by di_blocks are data blocks 4246584Storek * (when some of the blocks are usually used for indirect pointers); 4346584Storek * hence the estimate may be high. 4446584Storek */ 4546792Smckusick long 4647058Smckusick blockest(dp) 4747058Smckusick register struct dinode *dp; 4846584Storek { 4946792Smckusick long blkest, sizeest; 5046584Storek 5146584Storek /* 5247058Smckusick * dp->di_size is the size of the file in bytes. 5347058Smckusick * dp->di_blocks stores the number of sectors actually in the file. 5446584Storek * If there are more sectors than the size would indicate, this just 5546584Storek * means that there are indirect blocks in the file or unused 5646584Storek * sectors in the last file block; we can safely ignore these 5746792Smckusick * (blkest = sizeest below). 5846584Storek * If the file is bigger than the number of sectors would indicate, 5946584Storek * then the file has holes in it. In this case we must use the 6046584Storek * block count to estimate the number of data blocks used, but 6146584Storek * we use the actual size for estimating the number of indirect 6246792Smckusick * dump blocks (sizeest vs. blkest in the indirect block 6346792Smckusick * calculation). 6446584Storek */ 6547058Smckusick blkest = howmany(dbtob(dp->di_blocks), TP_BSIZE); 6647058Smckusick sizeest = howmany(dp->di_size, TP_BSIZE); 6746792Smckusick if (blkest > sizeest) 6846792Smckusick blkest = sizeest; 6947058Smckusick if (dp->di_size > sblock->fs_bsize * NDADDR) { 7046584Storek /* calculate the number of indirect blocks on the dump tape */ 7146792Smckusick blkest += 7246792Smckusick howmany(sizeest - NDADDR * sblock->fs_bsize / TP_BSIZE, 7346584Storek TP_NINDIR); 7446584Storek } 7546792Smckusick return (blkest + 1); 7646584Storek } 7746584Storek 7846792Smckusick /* 7946792Smckusick * Dump pass 1. 8046792Smckusick * 8146792Smckusick * Walk the inode list for a filesystem to find all allocated inodes 8246792Smckusick * that have been modified since the previous dump time. Also, find all 8346792Smckusick * the directories in the filesystem. 8446792Smckusick */ 8546792Smckusick mapfiles(maxino, tapesize) 8646792Smckusick ino_t maxino; 8746792Smckusick long *tapesize; 8846584Storek { 8946792Smckusick register int mode; 9046792Smckusick register ino_t ino; 9146792Smckusick register struct dinode *dp; 9246792Smckusick int anydirskipped = 0; 9346584Storek 9446792Smckusick for (ino = 0; ino < maxino; ino++) { 9546792Smckusick dp = getino(ino); 9646792Smckusick if ((mode = (dp->di_mode & IFMT)) == 0) 9746792Smckusick continue; 9846792Smckusick SETINO(ino, usedinomap); 9946792Smckusick if (mode == IFDIR) 10046792Smckusick SETINO(ino, dumpdirmap); 10146792Smckusick if (dp->di_mtime >= spcl.c_ddate || 10246792Smckusick dp->di_ctime >= spcl.c_ddate) { 10346792Smckusick SETINO(ino, dumpinomap); 10446792Smckusick if (mode != IFREG && mode != IFDIR && mode != IFLNK) { 10546792Smckusick *tapesize += 1; 10646792Smckusick continue; 10746792Smckusick } 10846792Smckusick *tapesize += blockest(dp); 10946792Smckusick continue; 11046792Smckusick } 11146792Smckusick if (mode == IFDIR) 11246792Smckusick anydirskipped = 1; 11346792Smckusick } 11446792Smckusick /* 11546792Smckusick * Restore gets very upset if the root is not dumped, 11646792Smckusick * so ensure that it always is dumped. 11746792Smckusick */ 11846792Smckusick SETINO(ROOTINO, usedinomap); 11946792Smckusick return (anydirskipped); 12046584Storek } 12146584Storek 12246792Smckusick /* 12346792Smckusick * Dump pass 2. 12446792Smckusick * 12546792Smckusick * Scan each directory on the filesystem to see if it has any modified 12646792Smckusick * files in it. If it does, and has not already been added to the dump 12746792Smckusick * list (because it was itself modified), then add it. If a directory 12846792Smckusick * has not been modified itself, contains no modified files and has no 12946792Smckusick * subdirectories, then it can be deleted from the dump list and from 13046792Smckusick * the list of directories. By deleting it from the list of directories, 13146792Smckusick * its parent may now qualify for the same treatment on this or a later 13246792Smckusick * pass using this algorithm. 13346792Smckusick */ 13446792Smckusick mapdirs(maxino, tapesize) 13546792Smckusick ino_t maxino; 13646792Smckusick long *tapesize; 13746792Smckusick { 13846792Smckusick register struct dinode *dp; 13947058Smckusick register int i, dirty; 14025797Smckusick register char *map; 14146792Smckusick register ino_t ino; 14246792Smckusick long filesize, blkcnt = 0; 14346792Smckusick int ret, change = 0; 1441426Sroot 14546792Smckusick for (map = dumpdirmap, ino = 0; ino < maxino; ) { 14646584Storek if ((ino % NBBY) == 0) 14747058Smckusick dirty = *map++; 14846792Smckusick else 14947058Smckusick dirty >>= 1; 1504702Smckusic ino++; 15147058Smckusick if ((dirty & 1) == 0 || TSTINO(ino, dumpinomap)) 15246792Smckusick continue; 15346792Smckusick dp = getino(ino); 15446792Smckusick filesize = dp->di_size; 15546792Smckusick for (ret = 0, i = 0; filesize > 0 && i < NDADDR; i++) { 15646792Smckusick if (dp->di_db[i] != 0) 15746792Smckusick ret |= searchdir(ino, dp->di_db[i], 15846796Smckusick dblksize(sblock, dp, i), filesize); 15946792Smckusick if (ret & HASDUMPEDFILE) 16046792Smckusick filesize = 0; 16146792Smckusick else 16246792Smckusick filesize -= sblock->fs_bsize; 16346792Smckusick } 16446792Smckusick for (i = 0; filesize > 0 && i < NIADDR; i++) { 16546792Smckusick if (dp->di_ib[i] == 0) 16646792Smckusick continue; 16746792Smckusick ret |= dirindir(ino, dp->di_ib[i], i, &filesize); 16846792Smckusick } 16946792Smckusick if (ret & HASDUMPEDFILE) { 17046792Smckusick if (!TSTINO(ino, dumpinomap)) { 17146792Smckusick SETINO(ino, dumpinomap); 17246792Smckusick *tapesize += blockest(dp); 17346792Smckusick } 17446792Smckusick change = 1; 17546792Smckusick continue; 17646792Smckusick } 17746792Smckusick if ((ret & HASSUBDIRS) == 0) { 17846792Smckusick if (!TSTINO(ino, dumpinomap)) { 17946792Smckusick CLRINO(ino, dumpdirmap); 18046792Smckusick change = 1; 18146792Smckusick } 18246792Smckusick } 1831426Sroot } 18446792Smckusick return (change); 1851426Sroot } 1861426Sroot 18746792Smckusick /* 18846792Smckusick * Read indirect blocks, and pass the data blocks to be searched 18946792Smckusick * as directories. Quit as soon as any entry is found that will 19046792Smckusick * require the directory to be dumped. 19146792Smckusick */ 19246792Smckusick dirindir(ino, blkno, level, filesize) 19346792Smckusick ino_t ino; 19446792Smckusick daddr_t blkno; 19546792Smckusick int level, *filesize; 1961426Sroot { 19746792Smckusick int ret = 0; 19846792Smckusick register int i; 19946792Smckusick daddr_t idblk[MAXNINDIR]; 2001426Sroot 20146792Smckusick bread(fsbtodb(sblock, blkno), (char *)idblk, sblock->fs_bsize); 20246792Smckusick if (level <= 0) { 20346792Smckusick for (i = 0; *filesize > 0 && i < NINDIR(sblock); i++) { 20446792Smckusick blkno = idblk[i]; 20546792Smckusick if (blkno != 0) 20646796Smckusick ret |= searchdir(ino, blkno, sblock->fs_bsize, 20746796Smckusick filesize); 20846792Smckusick if (ret & HASDUMPEDFILE) 20946792Smckusick *filesize = 0; 21046792Smckusick else 21146792Smckusick *filesize -= sblock->fs_bsize; 2121426Sroot } 21346792Smckusick return (ret); 2145329Smckusic } 21546792Smckusick level--; 21646792Smckusick for (i = 0; *filesize > 0 && i < NINDIR(sblock); i++) { 21746792Smckusick blkno = idblk[i]; 21846792Smckusick if (blkno != 0) 21946792Smckusick ret |= dirindir(ino, blkno, level, filesize); 2205329Smckusic } 22146792Smckusick return (ret); 2221426Sroot } 2231426Sroot 22446792Smckusick /* 22546792Smckusick * Scan a disk block containing directory information looking to see if 22646792Smckusick * any of the entries are on the dump list and to see if the directory 22746792Smckusick * contains any subdirectories. 22846792Smckusick */ 22946796Smckusick searchdir(ino, blkno, size, filesize) 23046792Smckusick ino_t ino; 23146792Smckusick daddr_t blkno; 23246792Smckusick register int size; 23346796Smckusick int filesize; 2345329Smckusic { 23546792Smckusick register struct direct *dp; 23646792Smckusick register long loc; 23746792Smckusick char dblk[MAXBSIZE]; 2385329Smckusic 23946792Smckusick bread(fsbtodb(sblock, blkno), dblk, size); 24046796Smckusick if (filesize < size) 24146796Smckusick size = filesize; 24246792Smckusick for (loc = 0; loc < size; ) { 24346792Smckusick dp = (struct direct *)(dblk + loc); 24446792Smckusick if (dp->d_reclen == 0) { 24546792Smckusick msg("corrupted directory, inumber %d\n", ino); 24646792Smckusick break; 2475329Smckusic } 24846792Smckusick loc += dp->d_reclen; 24946792Smckusick if (dp->d_ino == 0) 25046792Smckusick continue; 25146792Smckusick if (dp->d_name[0] == '.') { 25246792Smckusick if (dp->d_name[1] == '\0') 25346792Smckusick continue; 25446792Smckusick if (dp->d_name[1] == '.' && dp->d_name[2] == '\0') 25546792Smckusick continue; 2565329Smckusic } 25746792Smckusick if (TSTINO(dp->d_ino, dumpinomap)) 25846792Smckusick return (HASDUMPEDFILE); 25946792Smckusick if (TSTINO(dp->d_ino, dumpdirmap)) 26046792Smckusick return (HASSUBDIRS); 2615329Smckusic } 26246792Smckusick return (0); 2635329Smckusic } 2645329Smckusic 26546792Smckusick /* 26646792Smckusick * Dump passes 3 and 4. 26746792Smckusick * 26846792Smckusick * Dump the contents of an inode to tape. 26946792Smckusick */ 27046584Storek void 27147058Smckusick dumpino(dp, ino) 27247058Smckusick register struct dinode *dp; 27346792Smckusick ino_t ino; 27417234Smckusick { 27546792Smckusick int mode, level, cnt; 2764777Smckusic long size; 2771426Sroot 27846792Smckusick if (newtape) { 2791426Sroot newtape = 0; 28046792Smckusick dumpmap(dumpinomap, TS_BITS, ino); 2811426Sroot } 28246792Smckusick CLRINO(ino, dumpinomap); 28347058Smckusick spcl.c_dinode = *dp; 2841426Sroot spcl.c_type = TS_INODE; 2851426Sroot spcl.c_count = 0; 28646792Smckusick /* 28746792Smckusick * Check for freed inode. 28846792Smckusick */ 28947058Smckusick if ((mode = (dp->di_mode & IFMT)) == 0) 29017234Smckusick return; 29146792Smckusick if ((mode != IFDIR && mode != IFREG && mode != IFLNK) || 29247058Smckusick dp->di_size == 0) { 29346792Smckusick writeheader(ino); 2941426Sroot return; 2951426Sroot } 29647058Smckusick if (dp->di_size > NDADDR * sblock->fs_bsize) 29746792Smckusick cnt = NDADDR * sblock->fs_frag; 2984777Smckusic else 29947058Smckusick cnt = howmany(dp->di_size, sblock->fs_fsize); 30047058Smckusick blksout(&dp->di_db[0], cnt, ino); 30147058Smckusick if ((size = dp->di_size - NDADDR * sblock->fs_bsize) <= 0) 3024777Smckusic return; 30346792Smckusick for (level = 0; level < NIADDR; level++) { 30447058Smckusick dmpindir(ino, dp->di_ib[level], level, &size); 3054777Smckusic if (size <= 0) 3064777Smckusic return; 3074777Smckusic } 3081426Sroot } 3091426Sroot 31046792Smckusick /* 31146792Smckusick * Read indirect blocks, and pass the data blocks to be dumped. 31246792Smckusick */ 31346584Storek void 31446792Smckusick dmpindir(ino, blk, level, size) 31546792Smckusick ino_t ino; 3164777Smckusic daddr_t blk; 31746792Smckusick int level; 3184777Smckusic long *size; 3191426Sroot { 3204777Smckusic int i, cnt; 3215329Smckusic daddr_t idblk[MAXNINDIR]; 3221426Sroot 3234777Smckusic if (blk != 0) 3245329Smckusic bread(fsbtodb(sblock, blk), (char *)idblk, sblock->fs_bsize); 3254777Smckusic else 32646584Storek bzero((char *)idblk, sblock->fs_bsize); 32746792Smckusick if (level <= 0) { 3285329Smckusic if (*size < NINDIR(sblock) * sblock->fs_bsize) 3295329Smckusic cnt = howmany(*size, sblock->fs_fsize); 3304777Smckusic else 3315329Smckusic cnt = NINDIR(sblock) * sblock->fs_frag; 3325329Smckusic *size -= NINDIR(sblock) * sblock->fs_bsize; 33346792Smckusick blksout(&idblk[0], cnt, ino); 3344777Smckusic return; 3351426Sroot } 33646792Smckusick level--; 3375329Smckusic for (i = 0; i < NINDIR(sblock); i++) { 33846792Smckusick dmpindir(ino, idblk[i], level, size); 3394777Smckusic if (*size <= 0) 3404777Smckusic return; 3414777Smckusic } 3421426Sroot } 3431426Sroot 34446792Smckusick /* 34546792Smckusick * Collect up the data into tape record sized buffers and output them. 34646792Smckusick */ 34746584Storek void 34846792Smckusick blksout(blkp, frags, ino) 3494777Smckusic daddr_t *blkp; 3504777Smckusic int frags; 35146792Smckusick ino_t ino; 3524777Smckusic { 35346584Storek register daddr_t *bp; 3545329Smckusic int i, j, count, blks, tbperdb; 3554777Smckusic 3569403Smckusick blks = howmany(frags * sblock->fs_fsize, TP_BSIZE); 35746584Storek tbperdb = sblock->fs_bsize >> tp_bshift; 3584777Smckusic for (i = 0; i < blks; i += TP_NINDIR) { 3594777Smckusic if (i + TP_NINDIR > blks) 3604777Smckusic count = blks; 3614777Smckusic else 3624777Smckusic count = i + TP_NINDIR; 3634777Smckusic for (j = i; j < count; j++) 3645329Smckusic if (blkp[j / tbperdb] != 0) 3654777Smckusic spcl.c_addr[j - i] = 1; 3664777Smckusic else 3674777Smckusic spcl.c_addr[j - i] = 0; 3684777Smckusic spcl.c_count = count - i; 36946792Smckusick writeheader(ino); 37046584Storek bp = &blkp[i / tbperdb]; 37146584Storek for (j = i; j < count; j += tbperdb, bp++) 37246584Storek if (*bp != 0) 3735329Smckusic if (j + tbperdb <= count) 37446792Smckusick dumpblock(*bp, sblock->fs_bsize); 3754777Smckusic else 37646792Smckusick dumpblock(*bp, (count - j) * TP_BSIZE); 3774777Smckusic spcl.c_type = TS_ADDR; 3784777Smckusic } 3794777Smckusic } 3804777Smckusic 38146792Smckusick /* 38246792Smckusick * Dump a map to the tape. 38346792Smckusick */ 38446584Storek void 38546792Smckusick dumpmap(map, type, ino) 3865329Smckusic char *map; 38746792Smckusick int type; 38846792Smckusick ino_t ino; 3891426Sroot { 39046792Smckusick register int i; 3911426Sroot char *cp; 3921426Sroot 39346792Smckusick spcl.c_type = type; 39446792Smckusick spcl.c_count = howmany(mapsize * sizeof(char), TP_BSIZE); 39546792Smckusick writeheader(ino); 3965329Smckusic for (i = 0, cp = map; i < spcl.c_count; i++, cp += TP_BSIZE) 39746792Smckusick writerec(cp); 3981426Sroot } 3991426Sroot 40046792Smckusick /* 40146792Smckusick * Write a header record to the dump tape. 40246792Smckusick */ 40346584Storek void 40446792Smckusick writeheader(ino) 40546792Smckusick ino_t ino; 4061426Sroot { 40746792Smckusick register long sum, cnt, *lp; 4081426Sroot 4091426Sroot spcl.c_inumber = ino; 4108368Smckusick spcl.c_magic = NFS_MAGIC; 4111426Sroot spcl.c_checksum = 0; 41246792Smckusick lp = (long *)&spcl; 41346792Smckusick sum = 0; 41446792Smckusick cnt = sizeof(union u_spcl) / (4 * sizeof(long)); 41546792Smckusick while (--cnt >= 0) { 41646792Smckusick sum += *lp++; 41746792Smckusick sum += *lp++; 41846792Smckusick sum += *lp++; 41946792Smckusick sum += *lp++; 42024168Smckusick } 42146792Smckusick spcl.c_checksum = CHECKSUM - sum; 42246792Smckusick writerec((char *)&spcl); 4231426Sroot } 4241426Sroot 4254702Smckusic struct dinode * 42646792Smckusick getino(inum) 42746792Smckusick ino_t inum; 4284702Smckusic { 4294702Smckusic static daddr_t minino, maxino; 43046792Smckusick static struct dinode inoblock[MAXINOPB]; 4314702Smckusic 43246792Smckusick curino = inum; 43346792Smckusick if (inum >= minino && inum < maxino) 43446792Smckusick return (&inoblock[inum - minino]); 43546792Smckusick bread(fsbtodb(sblock, itod(sblock, inum)), inoblock, sblock->fs_bsize); 43646792Smckusick minino = inum - (inum % INOPB(sblock)); 4375329Smckusic maxino = minino + INOPB(sblock); 43846792Smckusick return (&inoblock[inum - minino]); 4394702Smckusic } 4404702Smckusic 44146792Smckusick /* 44246792Smckusick * Read a chunk of data from the disk. 44346792Smckusick * Try to recover from hard errors by reading in sector sized pieces. 44446792Smckusick * Error recovery is attempted at most BREADEMAX times before seeking 44546792Smckusick * consent from the operator to continue. 44646792Smckusick */ 4471426Sroot int breaderrors = 0; 4481426Sroot #define BREADEMAX 32 4491426Sroot 45046584Storek void 45146792Smckusick bread(blkno, buf, size) 45246792Smckusick daddr_t blkno; 45346792Smckusick char *buf; 45446792Smckusick int size; 4551426Sroot { 45646792Smckusick int cnt, i; 45734359Skarels extern int errno; 4581426Sroot 45915095Smckusick loop: 46046792Smckusick if (lseek(diskfd, (long)(blkno << dev_bshift), 0) < 0) 4611426Sroot msg("bread: lseek fails\n"); 46246792Smckusick if ((cnt = read(diskfd, buf, size)) == size) 46315095Smckusick return; 46446792Smckusick if (blkno + (size / dev_bsize) > fsbtodb(sblock, sblock->fs_size)) { 46515095Smckusick /* 46615095Smckusick * Trying to read the final fragment. 46715095Smckusick * 46815095Smckusick * NB - dump only works in TP_BSIZE blocks, hence 46930560Smckusick * rounds `dev_bsize' fragments up to TP_BSIZE pieces. 47015095Smckusick * It should be smarter about not actually trying to 47115095Smckusick * read more than it can get, but for the time being 47215095Smckusick * we punt and scale back the read only when it gets 47315095Smckusick * us into trouble. (mkm 9/25/83) 47415095Smckusick */ 47546792Smckusick size -= dev_bsize; 47615095Smckusick goto loop; 4771426Sroot } 478*50905Smckusick if (cnt == -1) 479*50905Smckusick msg("read error from %s: %s: [block %d]: count=%d\n", 480*50905Smckusick disk, strerror(errno), blkno, size); 481*50905Smckusick else 482*50905Smckusick msg("short read error from %s: [block %d]: count=%d, got=%d\n", 483*50905Smckusick disk, blkno, size, cnt); 48446584Storek if (++breaderrors > BREADEMAX) { 48515095Smckusick msg("More than %d block read errors from %d\n", 48615095Smckusick BREADEMAX, disk); 48715095Smckusick broadcast("DUMP IS AILING!\n"); 48815095Smckusick msg("This is an unrecoverable error.\n"); 48915095Smckusick if (!query("Do you want to attempt to continue?")){ 49015095Smckusick dumpabort(); 49115095Smckusick /*NOTREACHED*/ 49215095Smckusick } else 49315095Smckusick breaderrors = 0; 49415095Smckusick } 49534359Skarels /* 49634359Skarels * Zero buffer, then try to read each sector of buffer separately. 49734359Skarels */ 49846792Smckusick bzero(buf, size); 49946792Smckusick for (i = 0; i < size; i += dev_bsize, buf += dev_bsize, blkno++) { 50046792Smckusick if (lseek(diskfd, (long)(blkno << dev_bshift), 0) < 0) 50134359Skarels msg("bread: lseek2 fails!\n"); 502*50905Smckusick if ((cnt = read(diskfd, buf, dev_bsize)) == dev_bsize) 503*50905Smckusick continue; 504*50905Smckusick if (cnt == -1) { 505*50905Smckusick msg("read error from %s: %s: [sector %d]: count=%d\n", 506*50905Smckusick disk, strerror(errno), blkno, dev_bsize); 507*50905Smckusick continue; 508*50905Smckusick } 509*50905Smckusick msg("short read error from %s: [sector %d]: count=%d, got=%d\n", 510*50905Smckusick disk, blkno, dev_bsize, cnt); 51134359Skarels } 5121426Sroot } 513