122041Sdist /* 234359Skarels * Copyright (c) 1980, 1988 Regents of the University of California. 322041Sdist * All rights reserved. The Berkeley software License Agreement 422041Sdist * specifies the terms and conditions for redistribution. 522041Sdist */ 65329Smckusic 722041Sdist #ifndef lint 8*46795Sbostic static char sccsid[] = "@(#)traverse.c 5.8 (Berkeley) 02/28/91"; 946584Storek #endif /* not lint */ 1022041Sdist 11*46795Sbostic #include <sys/param.h> 12*46795Sbostic #include <ufs/dir.h> 13*46795Sbostic #include <ufs/dinode.h> 14*46795Sbostic #include <ufs/fs.h> 15*46795Sbostic #include <protocols/dumprestore.h> 16*46795Sbostic #ifdef __STDC__ 17*46795Sbostic #include <unistd.h> 18*46795Sbostic #include <string.h> 19*46795Sbostic #endif 201426Sroot #include "dump.h" 211426Sroot 2246792Smckusick void dmpindir(); 2346792Smckusick #define HASDUMPEDFILE 0x1 2446792Smckusick #define HASSUBDIRS 0x2 2546584Storek 2646584Storek /* 2746584Storek * This is an estimation of the number of TP_BSIZE blocks in the file. 2846584Storek * It estimates the number of blocks in files with holes by assuming 2946584Storek * that all of the blocks accounted for by di_blocks are data blocks 3046584Storek * (when some of the blocks are usually used for indirect pointers); 3146584Storek * hence the estimate may be high. 3246584Storek */ 3346792Smckusick long 3446792Smckusick blockest(ip) 3546584Storek struct dinode *ip; 3646584Storek { 3746792Smckusick long blkest, sizeest; 3846584Storek 3946584Storek /* 4046584Storek * ip->di_size is the size of the file in bytes. 4146584Storek * ip->di_blocks stores the number of sectors actually in the file. 4246584Storek * If there are more sectors than the size would indicate, this just 4346584Storek * means that there are indirect blocks in the file or unused 4446584Storek * sectors in the last file block; we can safely ignore these 4546792Smckusick * (blkest = sizeest below). 4646584Storek * If the file is bigger than the number of sectors would indicate, 4746584Storek * then the file has holes in it. In this case we must use the 4846584Storek * block count to estimate the number of data blocks used, but 4946584Storek * we use the actual size for estimating the number of indirect 5046792Smckusick * dump blocks (sizeest vs. blkest in the indirect block 5146792Smckusick * calculation). 5246584Storek */ 5346792Smckusick blkest = howmany(dbtob(ip->di_blocks), TP_BSIZE); 5446792Smckusick sizeest = howmany(ip->di_size, TP_BSIZE); 5546792Smckusick if (blkest > sizeest) 5646792Smckusick blkest = sizeest; 5746584Storek if (ip->di_size > sblock->fs_bsize * NDADDR) { 5846584Storek /* calculate the number of indirect blocks on the dump tape */ 5946792Smckusick blkest += 6046792Smckusick howmany(sizeest - NDADDR * sblock->fs_bsize / TP_BSIZE, 6146584Storek TP_NINDIR); 6246584Storek } 6346792Smckusick return (blkest + 1); 6446584Storek } 6546584Storek 6646792Smckusick /* 6746792Smckusick * Dump pass 1. 6846792Smckusick * 6946792Smckusick * Walk the inode list for a filesystem to find all allocated inodes 7046792Smckusick * that have been modified since the previous dump time. Also, find all 7146792Smckusick * the directories in the filesystem. 7246792Smckusick */ 7346792Smckusick mapfiles(maxino, tapesize) 7446792Smckusick ino_t maxino; 7546792Smckusick long *tapesize; 7646584Storek { 7746792Smckusick register int mode; 7846792Smckusick register ino_t ino; 7946792Smckusick register struct dinode *dp; 8046792Smckusick int anydirskipped = 0; 8146584Storek 8246792Smckusick for (ino = 0; ino < maxino; ino++) { 8346792Smckusick dp = getino(ino); 8446792Smckusick if ((mode = (dp->di_mode & IFMT)) == 0) 8546792Smckusick continue; 8646792Smckusick SETINO(ino, usedinomap); 8746792Smckusick if (mode == IFDIR) 8846792Smckusick SETINO(ino, dumpdirmap); 8946792Smckusick if (dp->di_mtime >= spcl.c_ddate || 9046792Smckusick dp->di_ctime >= spcl.c_ddate) { 9146792Smckusick SETINO(ino, dumpinomap); 9246792Smckusick if (mode != IFREG && mode != IFDIR && mode != IFLNK) { 9346792Smckusick *tapesize += 1; 9446792Smckusick continue; 9546792Smckusick } 9646792Smckusick *tapesize += blockest(dp); 9746792Smckusick continue; 9846792Smckusick } 9946792Smckusick if (mode == IFDIR) 10046792Smckusick anydirskipped = 1; 10146792Smckusick } 10246792Smckusick /* 10346792Smckusick * Restore gets very upset if the root is not dumped, 10446792Smckusick * so ensure that it always is dumped. 10546792Smckusick */ 10646792Smckusick SETINO(ROOTINO, usedinomap); 10746792Smckusick return (anydirskipped); 10846584Storek } 10946584Storek 11046792Smckusick /* 11146792Smckusick * Dump pass 2. 11246792Smckusick * 11346792Smckusick * Scan each directory on the filesystem to see if it has any modified 11446792Smckusick * files in it. If it does, and has not already been added to the dump 11546792Smckusick * list (because it was itself modified), then add it. If a directory 11646792Smckusick * has not been modified itself, contains no modified files and has no 11746792Smckusick * subdirectories, then it can be deleted from the dump list and from 11846792Smckusick * the list of directories. By deleting it from the list of directories, 11946792Smckusick * its parent may now qualify for the same treatment on this or a later 12046792Smckusick * pass using this algorithm. 12146792Smckusick */ 12246792Smckusick mapdirs(maxino, tapesize) 12346792Smckusick ino_t maxino; 12446792Smckusick long *tapesize; 12546792Smckusick { 12646792Smckusick register struct dinode *dp; 12746792Smckusick register int i, bits; 12825797Smckusick register char *map; 12946792Smckusick register ino_t ino; 13046792Smckusick long filesize, blkcnt = 0; 13146792Smckusick int ret, change = 0; 1321426Sroot 13346792Smckusick for (map = dumpdirmap, ino = 0; ino < maxino; ) { 13446584Storek if ((ino % NBBY) == 0) 13546792Smckusick bits = *map++; 13646792Smckusick else 13746792Smckusick bits >>= 1; 1384702Smckusic ino++; 13946792Smckusick if ((bits & 1) == 0 || TSTINO(ino, dumpinomap)) 14046792Smckusick continue; 14146792Smckusick dp = getino(ino); 14246792Smckusick filesize = dp->di_size; 14346792Smckusick for (ret = 0, i = 0; filesize > 0 && i < NDADDR; i++) { 14446792Smckusick if (dp->di_db[i] != 0) 14546792Smckusick ret |= searchdir(ino, dp->di_db[i], 14646792Smckusick dblksize(sblock, dp, i)); 14746792Smckusick if (ret & HASDUMPEDFILE) 14846792Smckusick filesize = 0; 14946792Smckusick else 15046792Smckusick filesize -= sblock->fs_bsize; 15146792Smckusick } 15246792Smckusick for (i = 0; filesize > 0 && i < NIADDR; i++) { 15346792Smckusick if (dp->di_ib[i] == 0) 15446792Smckusick continue; 15546792Smckusick ret |= dirindir(ino, dp->di_ib[i], i, &filesize); 15646792Smckusick } 15746792Smckusick if (ret & HASDUMPEDFILE) { 15846792Smckusick if (!TSTINO(ino, dumpinomap)) { 15946792Smckusick SETINO(ino, dumpinomap); 16046792Smckusick *tapesize += blockest(dp); 16146792Smckusick } 16246792Smckusick change = 1; 16346792Smckusick continue; 16446792Smckusick } 16546792Smckusick if ((ret & HASSUBDIRS) == 0) { 16646792Smckusick if (!TSTINO(ino, dumpinomap)) { 16746792Smckusick CLRINO(ino, dumpdirmap); 16846792Smckusick change = 1; 16946792Smckusick } 17046792Smckusick } 1711426Sroot } 17246792Smckusick return (change); 1731426Sroot } 1741426Sroot 17546792Smckusick /* 17646792Smckusick * Read indirect blocks, and pass the data blocks to be searched 17746792Smckusick * as directories. Quit as soon as any entry is found that will 17846792Smckusick * require the directory to be dumped. 17946792Smckusick */ 18046792Smckusick dirindir(ino, blkno, level, filesize) 18146792Smckusick ino_t ino; 18246792Smckusick daddr_t blkno; 18346792Smckusick int level, *filesize; 1841426Sroot { 18546792Smckusick int ret = 0; 18646792Smckusick register int i; 18746792Smckusick daddr_t idblk[MAXNINDIR]; 1881426Sroot 18946792Smckusick bread(fsbtodb(sblock, blkno), (char *)idblk, sblock->fs_bsize); 19046792Smckusick if (level <= 0) { 19146792Smckusick for (i = 0; *filesize > 0 && i < NINDIR(sblock); i++) { 19246792Smckusick blkno = idblk[i]; 19346792Smckusick if (blkno != 0) 19446792Smckusick ret |= searchdir(ino, blkno, sblock->fs_bsize); 19546792Smckusick if (ret & HASDUMPEDFILE) 19646792Smckusick *filesize = 0; 19746792Smckusick else 19846792Smckusick *filesize -= sblock->fs_bsize; 1991426Sroot } 20046792Smckusick return (ret); 2015329Smckusic } 20246792Smckusick level--; 20346792Smckusick for (i = 0; *filesize > 0 && i < NINDIR(sblock); i++) { 20446792Smckusick blkno = idblk[i]; 20546792Smckusick if (blkno != 0) 20646792Smckusick ret |= dirindir(ino, blkno, level, filesize); 2075329Smckusic } 20846792Smckusick return (ret); 2091426Sroot } 2101426Sroot 21146792Smckusick /* 21246792Smckusick * Scan a disk block containing directory information looking to see if 21346792Smckusick * any of the entries are on the dump list and to see if the directory 21446792Smckusick * contains any subdirectories. 21546792Smckusick */ 21646792Smckusick searchdir(ino, blkno, size) 21746792Smckusick ino_t ino; 21846792Smckusick daddr_t blkno; 21946792Smckusick register int size; 2205329Smckusic { 22146792Smckusick register struct direct *dp; 22246792Smckusick register long loc; 22346792Smckusick char dblk[MAXBSIZE]; 2245329Smckusic 22546792Smckusick bread(fsbtodb(sblock, blkno), dblk, size); 22646792Smckusick for (loc = 0; loc < size; ) { 22746792Smckusick dp = (struct direct *)(dblk + loc); 22846792Smckusick if (dp->d_reclen == 0) { 22946792Smckusick msg("corrupted directory, inumber %d\n", ino); 23046792Smckusick break; 2315329Smckusic } 23246792Smckusick loc += dp->d_reclen; 23346792Smckusick if (dp->d_ino == 0) 23446792Smckusick continue; 23546792Smckusick if (dp->d_name[0] == '.') { 23646792Smckusick if (dp->d_name[1] == '\0') 23746792Smckusick continue; 23846792Smckusick if (dp->d_name[1] == '.' && dp->d_name[2] == '\0') 23946792Smckusick continue; 2405329Smckusic } 24146792Smckusick if (TSTINO(dp->d_ino, dumpinomap)) 24246792Smckusick return (HASDUMPEDFILE); 24346792Smckusick if (TSTINO(dp->d_ino, dumpdirmap)) 24446792Smckusick return (HASSUBDIRS); 2455329Smckusic } 24646792Smckusick return (0); 2475329Smckusic } 2485329Smckusic 24946792Smckusick /* 25046792Smckusick * Dump passes 3 and 4. 25146792Smckusick * 25246792Smckusick * Dump the contents of an inode to tape. 25346792Smckusick */ 25446584Storek void 25546792Smckusick dumpino(ip, ino) 25617234Smckusick struct dinode *ip; 25746792Smckusick ino_t ino; 25817234Smckusick { 25946792Smckusick int mode, level, cnt; 2604777Smckusic long size; 2611426Sroot 26246792Smckusick if (newtape) { 2631426Sroot newtape = 0; 26446792Smckusick dumpmap(dumpinomap, TS_BITS, ino); 2651426Sroot } 26646792Smckusick CLRINO(ino, dumpinomap); 2671426Sroot spcl.c_dinode = *ip; 2681426Sroot spcl.c_type = TS_INODE; 2691426Sroot spcl.c_count = 0; 27046792Smckusick /* 27146792Smckusick * Check for freed inode. 27246792Smckusick */ 27346792Smckusick if ((mode = (ip->di_mode & IFMT)) == 0) 27417234Smckusick return; 27546792Smckusick if ((mode != IFDIR && mode != IFREG && mode != IFLNK) || 27646792Smckusick ip->di_size == 0) { 27746792Smckusick writeheader(ino); 2781426Sroot return; 2791426Sroot } 2805329Smckusic if (ip->di_size > NDADDR * sblock->fs_bsize) 28146792Smckusick cnt = NDADDR * sblock->fs_frag; 2824777Smckusic else 28346792Smckusick cnt = howmany(ip->di_size, sblock->fs_fsize); 28446792Smckusick blksout(&ip->di_db[0], cnt, ino); 28546792Smckusick if ((size = ip->di_size - NDADDR * sblock->fs_bsize) <= 0) 2864777Smckusic return; 28746792Smckusick for (level = 0; level < NIADDR; level++) { 28846792Smckusick dmpindir(ino, ip->di_ib[level], level, &size); 2894777Smckusic if (size <= 0) 2904777Smckusic return; 2914777Smckusic } 2921426Sroot } 2931426Sroot 29446792Smckusick /* 29546792Smckusick * Read indirect blocks, and pass the data blocks to be dumped. 29646792Smckusick */ 29746584Storek void 29846792Smckusick dmpindir(ino, blk, level, size) 29946792Smckusick ino_t ino; 3004777Smckusic daddr_t blk; 30146792Smckusick int level; 3024777Smckusic long *size; 3031426Sroot { 3044777Smckusic int i, cnt; 3055329Smckusic daddr_t idblk[MAXNINDIR]; 3061426Sroot 3074777Smckusic if (blk != 0) 3085329Smckusic bread(fsbtodb(sblock, blk), (char *)idblk, sblock->fs_bsize); 3094777Smckusic else 31046584Storek bzero((char *)idblk, sblock->fs_bsize); 31146792Smckusick if (level <= 0) { 3125329Smckusic if (*size < NINDIR(sblock) * sblock->fs_bsize) 3135329Smckusic cnt = howmany(*size, sblock->fs_fsize); 3144777Smckusic else 3155329Smckusic cnt = NINDIR(sblock) * sblock->fs_frag; 3165329Smckusic *size -= NINDIR(sblock) * sblock->fs_bsize; 31746792Smckusick blksout(&idblk[0], cnt, ino); 3184777Smckusic return; 3191426Sroot } 32046792Smckusick level--; 3215329Smckusic for (i = 0; i < NINDIR(sblock); i++) { 32246792Smckusick dmpindir(ino, idblk[i], level, size); 3234777Smckusic if (*size <= 0) 3244777Smckusic return; 3254777Smckusic } 3261426Sroot } 3271426Sroot 32846792Smckusick /* 32946792Smckusick * Collect up the data into tape record sized buffers and output them. 33046792Smckusick */ 33146584Storek void 33246792Smckusick blksout(blkp, frags, ino) 3334777Smckusic daddr_t *blkp; 3344777Smckusic int frags; 33546792Smckusick ino_t ino; 3364777Smckusic { 33746584Storek register daddr_t *bp; 3385329Smckusic int i, j, count, blks, tbperdb; 3394777Smckusic 3409403Smckusick blks = howmany(frags * sblock->fs_fsize, TP_BSIZE); 34146584Storek tbperdb = sblock->fs_bsize >> tp_bshift; 3424777Smckusic for (i = 0; i < blks; i += TP_NINDIR) { 3434777Smckusic if (i + TP_NINDIR > blks) 3444777Smckusic count = blks; 3454777Smckusic else 3464777Smckusic count = i + TP_NINDIR; 3474777Smckusic for (j = i; j < count; j++) 3485329Smckusic if (blkp[j / tbperdb] != 0) 3494777Smckusic spcl.c_addr[j - i] = 1; 3504777Smckusic else 3514777Smckusic spcl.c_addr[j - i] = 0; 3524777Smckusic spcl.c_count = count - i; 35346792Smckusick writeheader(ino); 35446584Storek bp = &blkp[i / tbperdb]; 35546584Storek for (j = i; j < count; j += tbperdb, bp++) 35646584Storek if (*bp != 0) 3575329Smckusic if (j + tbperdb <= count) 35846792Smckusick dumpblock(*bp, sblock->fs_bsize); 3594777Smckusic else 36046792Smckusick dumpblock(*bp, (count - j) * TP_BSIZE); 3614777Smckusic spcl.c_type = TS_ADDR; 3624777Smckusic } 3634777Smckusic } 3644777Smckusic 36546792Smckusick /* 36646792Smckusick * Dump a map to the tape. 36746792Smckusick */ 36846584Storek void 36946792Smckusick dumpmap(map, type, ino) 3705329Smckusic char *map; 37146792Smckusick int type; 37246792Smckusick ino_t ino; 3731426Sroot { 37446792Smckusick register int i; 3751426Sroot char *cp; 3761426Sroot 37746792Smckusick spcl.c_type = type; 37846792Smckusick spcl.c_count = howmany(mapsize * sizeof(char), TP_BSIZE); 37946792Smckusick writeheader(ino); 3805329Smckusic for (i = 0, cp = map; i < spcl.c_count; i++, cp += TP_BSIZE) 38146792Smckusick writerec(cp); 3821426Sroot } 3831426Sroot 38446792Smckusick /* 38546792Smckusick * Write a header record to the dump tape. 38646792Smckusick */ 38746584Storek void 38846792Smckusick writeheader(ino) 38946792Smckusick ino_t ino; 3901426Sroot { 39146792Smckusick register long sum, cnt, *lp; 3921426Sroot 3931426Sroot spcl.c_inumber = ino; 3948368Smckusick spcl.c_magic = NFS_MAGIC; 3951426Sroot spcl.c_checksum = 0; 39646792Smckusick lp = (long *)&spcl; 39746792Smckusick sum = 0; 39846792Smckusick cnt = sizeof(union u_spcl) / (4 * sizeof(long)); 39946792Smckusick while (--cnt >= 0) { 40046792Smckusick sum += *lp++; 40146792Smckusick sum += *lp++; 40246792Smckusick sum += *lp++; 40346792Smckusick sum += *lp++; 40424168Smckusick } 40546792Smckusick spcl.c_checksum = CHECKSUM - sum; 40646792Smckusick writerec((char *)&spcl); 4071426Sroot } 4081426Sroot 4094702Smckusic struct dinode * 41046792Smckusick getino(inum) 41146792Smckusick ino_t inum; 4124702Smckusic { 4134702Smckusic static daddr_t minino, maxino; 41446792Smckusick static struct dinode inoblock[MAXINOPB]; 4154702Smckusic 41646792Smckusick curino = inum; 41746792Smckusick if (inum >= minino && inum < maxino) 41846792Smckusick return (&inoblock[inum - minino]); 41946792Smckusick bread(fsbtodb(sblock, itod(sblock, inum)), inoblock, sblock->fs_bsize); 42046792Smckusick minino = inum - (inum % INOPB(sblock)); 4215329Smckusic maxino = minino + INOPB(sblock); 42246792Smckusick return (&inoblock[inum - minino]); 4234702Smckusic } 4244702Smckusic 42546792Smckusick /* 42646792Smckusick * Read a chunk of data from the disk. 42746792Smckusick * Try to recover from hard errors by reading in sector sized pieces. 42846792Smckusick * Error recovery is attempted at most BREADEMAX times before seeking 42946792Smckusick * consent from the operator to continue. 43046792Smckusick */ 4311426Sroot int breaderrors = 0; 4321426Sroot #define BREADEMAX 32 4331426Sroot 43446584Storek void 43546792Smckusick bread(blkno, buf, size) 43646792Smckusick daddr_t blkno; 43746792Smckusick char *buf; 43846792Smckusick int size; 4391426Sroot { 44046792Smckusick int cnt, i; 44134359Skarels extern int errno; 4421426Sroot 44315095Smckusick loop: 44446792Smckusick if (lseek(diskfd, (long)(blkno << dev_bshift), 0) < 0) 4451426Sroot msg("bread: lseek fails\n"); 44646792Smckusick if ((cnt = read(diskfd, buf, size)) == size) 44715095Smckusick return; 44846792Smckusick if (blkno + (size / dev_bsize) > fsbtodb(sblock, sblock->fs_size)) { 44915095Smckusick /* 45015095Smckusick * Trying to read the final fragment. 45115095Smckusick * 45215095Smckusick * NB - dump only works in TP_BSIZE blocks, hence 45330560Smckusick * rounds `dev_bsize' fragments up to TP_BSIZE pieces. 45415095Smckusick * It should be smarter about not actually trying to 45515095Smckusick * read more than it can get, but for the time being 45615095Smckusick * we punt and scale back the read only when it gets 45715095Smckusick * us into trouble. (mkm 9/25/83) 45815095Smckusick */ 45946792Smckusick size -= dev_bsize; 46015095Smckusick goto loop; 4611426Sroot } 46246584Storek msg("read error from %s [block %d]: count=%d, got=%d, errno=%d (%s)\n", 46346792Smckusick disk, blkno, size, cnt, errno, strerror(errno)); 46446584Storek if (++breaderrors > BREADEMAX) { 46515095Smckusick msg("More than %d block read errors from %d\n", 46615095Smckusick BREADEMAX, disk); 46715095Smckusick broadcast("DUMP IS AILING!\n"); 46815095Smckusick msg("This is an unrecoverable error.\n"); 46915095Smckusick if (!query("Do you want to attempt to continue?")){ 47015095Smckusick dumpabort(); 47115095Smckusick /*NOTREACHED*/ 47215095Smckusick } else 47315095Smckusick breaderrors = 0; 47415095Smckusick } 47534359Skarels /* 47634359Skarels * Zero buffer, then try to read each sector of buffer separately. 47734359Skarels */ 47846792Smckusick bzero(buf, size); 47946792Smckusick for (i = 0; i < size; i += dev_bsize, buf += dev_bsize, blkno++) { 48046792Smckusick if (lseek(diskfd, (long)(blkno << dev_bshift), 0) < 0) 48134359Skarels msg("bread: lseek2 fails!\n"); 48246792Smckusick if ((cnt = read(diskfd, buf, dev_bsize)) != dev_bsize) 48334359Skarels msg(" read error from %s [sector %d, errno %d]\n", 48446792Smckusick disk, blkno, errno); 48534359Skarels } 4861426Sroot } 487