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