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*46792Smckusick static char sccsid[] = "@(#)traverse.c 5.7 (Berkeley) 02/28/91"; 946584Storek #endif /* not lint */ 1022041Sdist 111426Sroot #include "dump.h" 121426Sroot 13*46792Smckusick void dmpindir(); 14*46792Smckusick #define HASDUMPEDFILE 0x1 15*46792Smckusick #define HASSUBDIRS 0x2 1646584Storek 1746584Storek /* 1846584Storek * This is an estimation of the number of TP_BSIZE blocks in the file. 1946584Storek * It estimates the number of blocks in files with holes by assuming 2046584Storek * that all of the blocks accounted for by di_blocks are data blocks 2146584Storek * (when some of the blocks are usually used for indirect pointers); 2246584Storek * hence the estimate may be high. 2346584Storek */ 24*46792Smckusick long 25*46792Smckusick blockest(ip) 2646584Storek struct dinode *ip; 2746584Storek { 28*46792Smckusick long blkest, sizeest; 2946584Storek 3046584Storek /* 3146584Storek * ip->di_size is the size of the file in bytes. 3246584Storek * ip->di_blocks stores the number of sectors actually in the file. 3346584Storek * If there are more sectors than the size would indicate, this just 3446584Storek * means that there are indirect blocks in the file or unused 3546584Storek * sectors in the last file block; we can safely ignore these 36*46792Smckusick * (blkest = sizeest below). 3746584Storek * If the file is bigger than the number of sectors would indicate, 3846584Storek * then the file has holes in it. In this case we must use the 3946584Storek * block count to estimate the number of data blocks used, but 4046584Storek * we use the actual size for estimating the number of indirect 41*46792Smckusick * dump blocks (sizeest vs. blkest in the indirect block 42*46792Smckusick * calculation). 4346584Storek */ 44*46792Smckusick blkest = howmany(dbtob(ip->di_blocks), TP_BSIZE); 45*46792Smckusick sizeest = howmany(ip->di_size, TP_BSIZE); 46*46792Smckusick if (blkest > sizeest) 47*46792Smckusick blkest = sizeest; 4846584Storek if (ip->di_size > sblock->fs_bsize * NDADDR) { 4946584Storek /* calculate the number of indirect blocks on the dump tape */ 50*46792Smckusick blkest += 51*46792Smckusick howmany(sizeest - NDADDR * sblock->fs_bsize / TP_BSIZE, 5246584Storek TP_NINDIR); 5346584Storek } 54*46792Smckusick return (blkest + 1); 5546584Storek } 5646584Storek 57*46792Smckusick /* 58*46792Smckusick * Dump pass 1. 59*46792Smckusick * 60*46792Smckusick * Walk the inode list for a filesystem to find all allocated inodes 61*46792Smckusick * that have been modified since the previous dump time. Also, find all 62*46792Smckusick * the directories in the filesystem. 63*46792Smckusick */ 64*46792Smckusick mapfiles(maxino, tapesize) 65*46792Smckusick ino_t maxino; 66*46792Smckusick long *tapesize; 6746584Storek { 68*46792Smckusick register int mode; 69*46792Smckusick register ino_t ino; 70*46792Smckusick register struct dinode *dp; 71*46792Smckusick int anydirskipped = 0; 7246584Storek 73*46792Smckusick for (ino = 0; ino < maxino; ino++) { 74*46792Smckusick dp = getino(ino); 75*46792Smckusick if ((mode = (dp->di_mode & IFMT)) == 0) 76*46792Smckusick continue; 77*46792Smckusick SETINO(ino, usedinomap); 78*46792Smckusick if (mode == IFDIR) 79*46792Smckusick SETINO(ino, dumpdirmap); 80*46792Smckusick if (dp->di_mtime >= spcl.c_ddate || 81*46792Smckusick dp->di_ctime >= spcl.c_ddate) { 82*46792Smckusick SETINO(ino, dumpinomap); 83*46792Smckusick if (mode != IFREG && mode != IFDIR && mode != IFLNK) { 84*46792Smckusick *tapesize += 1; 85*46792Smckusick continue; 86*46792Smckusick } 87*46792Smckusick *tapesize += blockest(dp); 88*46792Smckusick continue; 89*46792Smckusick } 90*46792Smckusick if (mode == IFDIR) 91*46792Smckusick anydirskipped = 1; 92*46792Smckusick } 93*46792Smckusick /* 94*46792Smckusick * Restore gets very upset if the root is not dumped, 95*46792Smckusick * so ensure that it always is dumped. 96*46792Smckusick */ 97*46792Smckusick SETINO(ROOTINO, usedinomap); 98*46792Smckusick return (anydirskipped); 9946584Storek } 10046584Storek 101*46792Smckusick /* 102*46792Smckusick * Dump pass 2. 103*46792Smckusick * 104*46792Smckusick * Scan each directory on the filesystem to see if it has any modified 105*46792Smckusick * files in it. If it does, and has not already been added to the dump 106*46792Smckusick * list (because it was itself modified), then add it. If a directory 107*46792Smckusick * has not been modified itself, contains no modified files and has no 108*46792Smckusick * subdirectories, then it can be deleted from the dump list and from 109*46792Smckusick * the list of directories. By deleting it from the list of directories, 110*46792Smckusick * its parent may now qualify for the same treatment on this or a later 111*46792Smckusick * pass using this algorithm. 112*46792Smckusick */ 113*46792Smckusick mapdirs(maxino, tapesize) 114*46792Smckusick ino_t maxino; 115*46792Smckusick long *tapesize; 116*46792Smckusick { 117*46792Smckusick register struct dinode *dp; 118*46792Smckusick register int i, bits; 11925797Smckusick register char *map; 120*46792Smckusick register ino_t ino; 121*46792Smckusick long filesize, blkcnt = 0; 122*46792Smckusick int ret, change = 0; 1231426Sroot 124*46792Smckusick for (map = dumpdirmap, ino = 0; ino < maxino; ) { 12546584Storek if ((ino % NBBY) == 0) 126*46792Smckusick bits = *map++; 127*46792Smckusick else 128*46792Smckusick bits >>= 1; 1294702Smckusic ino++; 130*46792Smckusick if ((bits & 1) == 0 || TSTINO(ino, dumpinomap)) 131*46792Smckusick continue; 132*46792Smckusick dp = getino(ino); 133*46792Smckusick filesize = dp->di_size; 134*46792Smckusick for (ret = 0, i = 0; filesize > 0 && i < NDADDR; i++) { 135*46792Smckusick if (dp->di_db[i] != 0) 136*46792Smckusick ret |= searchdir(ino, dp->di_db[i], 137*46792Smckusick dblksize(sblock, dp, i)); 138*46792Smckusick if (ret & HASDUMPEDFILE) 139*46792Smckusick filesize = 0; 140*46792Smckusick else 141*46792Smckusick filesize -= sblock->fs_bsize; 142*46792Smckusick } 143*46792Smckusick for (i = 0; filesize > 0 && i < NIADDR; i++) { 144*46792Smckusick if (dp->di_ib[i] == 0) 145*46792Smckusick continue; 146*46792Smckusick ret |= dirindir(ino, dp->di_ib[i], i, &filesize); 147*46792Smckusick } 148*46792Smckusick if (ret & HASDUMPEDFILE) { 149*46792Smckusick if (!TSTINO(ino, dumpinomap)) { 150*46792Smckusick SETINO(ino, dumpinomap); 151*46792Smckusick *tapesize += blockest(dp); 152*46792Smckusick } 153*46792Smckusick change = 1; 154*46792Smckusick continue; 155*46792Smckusick } 156*46792Smckusick if ((ret & HASSUBDIRS) == 0) { 157*46792Smckusick if (!TSTINO(ino, dumpinomap)) { 158*46792Smckusick CLRINO(ino, dumpdirmap); 159*46792Smckusick change = 1; 160*46792Smckusick } 161*46792Smckusick } 1621426Sroot } 163*46792Smckusick return (change); 1641426Sroot } 1651426Sroot 166*46792Smckusick /* 167*46792Smckusick * Read indirect blocks, and pass the data blocks to be searched 168*46792Smckusick * as directories. Quit as soon as any entry is found that will 169*46792Smckusick * require the directory to be dumped. 170*46792Smckusick */ 171*46792Smckusick dirindir(ino, blkno, level, filesize) 172*46792Smckusick ino_t ino; 173*46792Smckusick daddr_t blkno; 174*46792Smckusick int level, *filesize; 1751426Sroot { 176*46792Smckusick int ret = 0; 177*46792Smckusick register int i; 178*46792Smckusick daddr_t idblk[MAXNINDIR]; 1791426Sroot 180*46792Smckusick bread(fsbtodb(sblock, blkno), (char *)idblk, sblock->fs_bsize); 181*46792Smckusick if (level <= 0) { 182*46792Smckusick for (i = 0; *filesize > 0 && i < NINDIR(sblock); i++) { 183*46792Smckusick blkno = idblk[i]; 184*46792Smckusick if (blkno != 0) 185*46792Smckusick ret |= searchdir(ino, blkno, sblock->fs_bsize); 186*46792Smckusick if (ret & HASDUMPEDFILE) 187*46792Smckusick *filesize = 0; 188*46792Smckusick else 189*46792Smckusick *filesize -= sblock->fs_bsize; 1901426Sroot } 191*46792Smckusick return (ret); 1925329Smckusic } 193*46792Smckusick level--; 194*46792Smckusick for (i = 0; *filesize > 0 && i < NINDIR(sblock); i++) { 195*46792Smckusick blkno = idblk[i]; 196*46792Smckusick if (blkno != 0) 197*46792Smckusick ret |= dirindir(ino, blkno, level, filesize); 1985329Smckusic } 199*46792Smckusick return (ret); 2001426Sroot } 2011426Sroot 202*46792Smckusick /* 203*46792Smckusick * Scan a disk block containing directory information looking to see if 204*46792Smckusick * any of the entries are on the dump list and to see if the directory 205*46792Smckusick * contains any subdirectories. 206*46792Smckusick */ 207*46792Smckusick searchdir(ino, blkno, size) 208*46792Smckusick ino_t ino; 209*46792Smckusick daddr_t blkno; 210*46792Smckusick register int size; 2115329Smckusic { 212*46792Smckusick register struct direct *dp; 213*46792Smckusick register long loc; 214*46792Smckusick char dblk[MAXBSIZE]; 2155329Smckusic 216*46792Smckusick bread(fsbtodb(sblock, blkno), dblk, size); 217*46792Smckusick for (loc = 0; loc < size; ) { 218*46792Smckusick dp = (struct direct *)(dblk + loc); 219*46792Smckusick if (dp->d_reclen == 0) { 220*46792Smckusick msg("corrupted directory, inumber %d\n", ino); 221*46792Smckusick break; 2225329Smckusic } 223*46792Smckusick loc += dp->d_reclen; 224*46792Smckusick if (dp->d_ino == 0) 225*46792Smckusick continue; 226*46792Smckusick if (dp->d_name[0] == '.') { 227*46792Smckusick if (dp->d_name[1] == '\0') 228*46792Smckusick continue; 229*46792Smckusick if (dp->d_name[1] == '.' && dp->d_name[2] == '\0') 230*46792Smckusick continue; 2315329Smckusic } 232*46792Smckusick if (TSTINO(dp->d_ino, dumpinomap)) 233*46792Smckusick return (HASDUMPEDFILE); 234*46792Smckusick if (TSTINO(dp->d_ino, dumpdirmap)) 235*46792Smckusick return (HASSUBDIRS); 2365329Smckusic } 237*46792Smckusick return (0); 2385329Smckusic } 2395329Smckusic 240*46792Smckusick /* 241*46792Smckusick * Dump passes 3 and 4. 242*46792Smckusick * 243*46792Smckusick * Dump the contents of an inode to tape. 244*46792Smckusick */ 24546584Storek void 246*46792Smckusick dumpino(ip, ino) 24717234Smckusick struct dinode *ip; 248*46792Smckusick ino_t ino; 24917234Smckusick { 250*46792Smckusick int mode, level, cnt; 2514777Smckusic long size; 2521426Sroot 253*46792Smckusick if (newtape) { 2541426Sroot newtape = 0; 255*46792Smckusick dumpmap(dumpinomap, TS_BITS, ino); 2561426Sroot } 257*46792Smckusick CLRINO(ino, dumpinomap); 2581426Sroot spcl.c_dinode = *ip; 2591426Sroot spcl.c_type = TS_INODE; 2601426Sroot spcl.c_count = 0; 261*46792Smckusick /* 262*46792Smckusick * Check for freed inode. 263*46792Smckusick */ 264*46792Smckusick if ((mode = (ip->di_mode & IFMT)) == 0) 26517234Smckusick return; 266*46792Smckusick if ((mode != IFDIR && mode != IFREG && mode != IFLNK) || 267*46792Smckusick ip->di_size == 0) { 268*46792Smckusick writeheader(ino); 2691426Sroot return; 2701426Sroot } 2715329Smckusic if (ip->di_size > NDADDR * sblock->fs_bsize) 272*46792Smckusick cnt = NDADDR * sblock->fs_frag; 2734777Smckusic else 274*46792Smckusick cnt = howmany(ip->di_size, sblock->fs_fsize); 275*46792Smckusick blksout(&ip->di_db[0], cnt, ino); 276*46792Smckusick if ((size = ip->di_size - NDADDR * sblock->fs_bsize) <= 0) 2774777Smckusic return; 278*46792Smckusick for (level = 0; level < NIADDR; level++) { 279*46792Smckusick dmpindir(ino, ip->di_ib[level], level, &size); 2804777Smckusic if (size <= 0) 2814777Smckusic return; 2824777Smckusic } 2831426Sroot } 2841426Sroot 285*46792Smckusick /* 286*46792Smckusick * Read indirect blocks, and pass the data blocks to be dumped. 287*46792Smckusick */ 28846584Storek void 289*46792Smckusick dmpindir(ino, blk, level, size) 290*46792Smckusick ino_t ino; 2914777Smckusic daddr_t blk; 292*46792Smckusick int level; 2934777Smckusic long *size; 2941426Sroot { 2954777Smckusic int i, cnt; 2965329Smckusic daddr_t idblk[MAXNINDIR]; 2971426Sroot 2984777Smckusic if (blk != 0) 2995329Smckusic bread(fsbtodb(sblock, blk), (char *)idblk, sblock->fs_bsize); 3004777Smckusic else 30146584Storek bzero((char *)idblk, sblock->fs_bsize); 302*46792Smckusick if (level <= 0) { 3035329Smckusic if (*size < NINDIR(sblock) * sblock->fs_bsize) 3045329Smckusic cnt = howmany(*size, sblock->fs_fsize); 3054777Smckusic else 3065329Smckusic cnt = NINDIR(sblock) * sblock->fs_frag; 3075329Smckusic *size -= NINDIR(sblock) * sblock->fs_bsize; 308*46792Smckusick blksout(&idblk[0], cnt, ino); 3094777Smckusic return; 3101426Sroot } 311*46792Smckusick level--; 3125329Smckusic for (i = 0; i < NINDIR(sblock); i++) { 313*46792Smckusick dmpindir(ino, idblk[i], level, size); 3144777Smckusic if (*size <= 0) 3154777Smckusic return; 3164777Smckusic } 3171426Sroot } 3181426Sroot 319*46792Smckusick /* 320*46792Smckusick * Collect up the data into tape record sized buffers and output them. 321*46792Smckusick */ 32246584Storek void 323*46792Smckusick blksout(blkp, frags, ino) 3244777Smckusic daddr_t *blkp; 3254777Smckusic int frags; 326*46792Smckusick ino_t ino; 3274777Smckusic { 32846584Storek register daddr_t *bp; 3295329Smckusic int i, j, count, blks, tbperdb; 3304777Smckusic 3319403Smckusick blks = howmany(frags * sblock->fs_fsize, TP_BSIZE); 33246584Storek tbperdb = sblock->fs_bsize >> tp_bshift; 3334777Smckusic for (i = 0; i < blks; i += TP_NINDIR) { 3344777Smckusic if (i + TP_NINDIR > blks) 3354777Smckusic count = blks; 3364777Smckusic else 3374777Smckusic count = i + TP_NINDIR; 3384777Smckusic for (j = i; j < count; j++) 3395329Smckusic if (blkp[j / tbperdb] != 0) 3404777Smckusic spcl.c_addr[j - i] = 1; 3414777Smckusic else 3424777Smckusic spcl.c_addr[j - i] = 0; 3434777Smckusic spcl.c_count = count - i; 344*46792Smckusick writeheader(ino); 34546584Storek bp = &blkp[i / tbperdb]; 34646584Storek for (j = i; j < count; j += tbperdb, bp++) 34746584Storek if (*bp != 0) 3485329Smckusic if (j + tbperdb <= count) 349*46792Smckusick dumpblock(*bp, sblock->fs_bsize); 3504777Smckusic else 351*46792Smckusick dumpblock(*bp, (count - j) * TP_BSIZE); 3524777Smckusic spcl.c_type = TS_ADDR; 3534777Smckusic } 3544777Smckusic } 3554777Smckusic 356*46792Smckusick /* 357*46792Smckusick * Dump a map to the tape. 358*46792Smckusick */ 35946584Storek void 360*46792Smckusick dumpmap(map, type, ino) 3615329Smckusic char *map; 362*46792Smckusick int type; 363*46792Smckusick ino_t ino; 3641426Sroot { 365*46792Smckusick register int i; 3661426Sroot char *cp; 3671426Sroot 368*46792Smckusick spcl.c_type = type; 369*46792Smckusick spcl.c_count = howmany(mapsize * sizeof(char), TP_BSIZE); 370*46792Smckusick writeheader(ino); 3715329Smckusic for (i = 0, cp = map; i < spcl.c_count; i++, cp += TP_BSIZE) 372*46792Smckusick writerec(cp); 3731426Sroot } 3741426Sroot 375*46792Smckusick /* 376*46792Smckusick * Write a header record to the dump tape. 377*46792Smckusick */ 37846584Storek void 379*46792Smckusick writeheader(ino) 380*46792Smckusick ino_t ino; 3811426Sroot { 382*46792Smckusick register long sum, cnt, *lp; 3831426Sroot 3841426Sroot spcl.c_inumber = ino; 3858368Smckusick spcl.c_magic = NFS_MAGIC; 3861426Sroot spcl.c_checksum = 0; 387*46792Smckusick lp = (long *)&spcl; 388*46792Smckusick sum = 0; 389*46792Smckusick cnt = sizeof(union u_spcl) / (4 * sizeof(long)); 390*46792Smckusick while (--cnt >= 0) { 391*46792Smckusick sum += *lp++; 392*46792Smckusick sum += *lp++; 393*46792Smckusick sum += *lp++; 394*46792Smckusick sum += *lp++; 39524168Smckusick } 396*46792Smckusick spcl.c_checksum = CHECKSUM - sum; 397*46792Smckusick writerec((char *)&spcl); 3981426Sroot } 3991426Sroot 4004702Smckusic struct dinode * 401*46792Smckusick getino(inum) 402*46792Smckusick ino_t inum; 4034702Smckusic { 4044702Smckusic static daddr_t minino, maxino; 405*46792Smckusick static struct dinode inoblock[MAXINOPB]; 4064702Smckusic 407*46792Smckusick curino = inum; 408*46792Smckusick if (inum >= minino && inum < maxino) 409*46792Smckusick return (&inoblock[inum - minino]); 410*46792Smckusick bread(fsbtodb(sblock, itod(sblock, inum)), inoblock, sblock->fs_bsize); 411*46792Smckusick minino = inum - (inum % INOPB(sblock)); 4125329Smckusic maxino = minino + INOPB(sblock); 413*46792Smckusick return (&inoblock[inum - minino]); 4144702Smckusic } 4154702Smckusic 416*46792Smckusick /* 417*46792Smckusick * Read a chunk of data from the disk. 418*46792Smckusick * Try to recover from hard errors by reading in sector sized pieces. 419*46792Smckusick * Error recovery is attempted at most BREADEMAX times before seeking 420*46792Smckusick * consent from the operator to continue. 421*46792Smckusick */ 4221426Sroot int breaderrors = 0; 4231426Sroot #define BREADEMAX 32 4241426Sroot 42546584Storek void 426*46792Smckusick bread(blkno, buf, size) 427*46792Smckusick daddr_t blkno; 428*46792Smckusick char *buf; 429*46792Smckusick int size; 4301426Sroot { 431*46792Smckusick int cnt, i; 43234359Skarels extern int errno; 4331426Sroot 43415095Smckusick loop: 435*46792Smckusick if (lseek(diskfd, (long)(blkno << dev_bshift), 0) < 0) 4361426Sroot msg("bread: lseek fails\n"); 437*46792Smckusick if ((cnt = read(diskfd, buf, size)) == size) 43815095Smckusick return; 439*46792Smckusick if (blkno + (size / dev_bsize) > fsbtodb(sblock, sblock->fs_size)) { 44015095Smckusick /* 44115095Smckusick * Trying to read the final fragment. 44215095Smckusick * 44315095Smckusick * NB - dump only works in TP_BSIZE blocks, hence 44430560Smckusick * rounds `dev_bsize' fragments up to TP_BSIZE pieces. 44515095Smckusick * It should be smarter about not actually trying to 44615095Smckusick * read more than it can get, but for the time being 44715095Smckusick * we punt and scale back the read only when it gets 44815095Smckusick * us into trouble. (mkm 9/25/83) 44915095Smckusick */ 450*46792Smckusick size -= dev_bsize; 45115095Smckusick goto loop; 4521426Sroot } 45346584Storek msg("read error from %s [block %d]: count=%d, got=%d, errno=%d (%s)\n", 454*46792Smckusick disk, blkno, size, cnt, errno, strerror(errno)); 45546584Storek if (++breaderrors > BREADEMAX) { 45615095Smckusick msg("More than %d block read errors from %d\n", 45715095Smckusick BREADEMAX, disk); 45815095Smckusick broadcast("DUMP IS AILING!\n"); 45915095Smckusick msg("This is an unrecoverable error.\n"); 46015095Smckusick if (!query("Do you want to attempt to continue?")){ 46115095Smckusick dumpabort(); 46215095Smckusick /*NOTREACHED*/ 46315095Smckusick } else 46415095Smckusick breaderrors = 0; 46515095Smckusick } 46634359Skarels /* 46734359Skarels * Zero buffer, then try to read each sector of buffer separately. 46834359Skarels */ 469*46792Smckusick bzero(buf, size); 470*46792Smckusick for (i = 0; i < size; i += dev_bsize, buf += dev_bsize, blkno++) { 471*46792Smckusick if (lseek(diskfd, (long)(blkno << dev_bshift), 0) < 0) 47234359Skarels msg("bread: lseek2 fails!\n"); 473*46792Smckusick if ((cnt = read(diskfd, buf, dev_bsize)) != dev_bsize) 47434359Skarels msg(" read error from %s [sector %d, errno %d]\n", 475*46792Smckusick disk, blkno, errno); 47634359Skarels } 4771426Sroot } 478