1 /* $NetBSD: traverse.c,v 1.17 1997/06/05 11:13:27 lukem Exp $ */ 2 3 /*- 4 * Copyright (c) 1980, 1988, 1991, 1993 5 * The Regents of the University of California. All rights reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 1. Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 3. All advertising materials mentioning features or use of this software 16 * must display the following acknowledgement: 17 * This product includes software developed by the University of 18 * California, Berkeley and its contributors. 19 * 4. Neither the name of the University nor the names of its contributors 20 * may be used to endorse or promote products derived from this software 21 * without specific prior written permission. 22 * 23 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 24 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 25 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 26 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 27 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 28 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 29 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 30 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 31 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 32 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 33 * SUCH DAMAGE. 34 */ 35 36 #ifndef lint 37 #if 0 38 static char sccsid[] = "@(#)traverse.c 8.2 (Berkeley) 9/23/93"; 39 #else 40 static char rcsid[] = "$NetBSD: traverse.c,v 1.17 1997/06/05 11:13:27 lukem Exp $"; 41 #endif 42 #endif /* not lint */ 43 44 #include <sys/param.h> 45 #include <sys/time.h> 46 #include <sys/stat.h> 47 #ifdef sunos 48 #include <sys/vnode.h> 49 50 #include <ufs/fs.h> 51 #include <ufs/fsdir.h> 52 #include <ufs/inode.h> 53 #else 54 #include <ufs/ffs/fs.h> 55 #include <ufs/ufs/dir.h> 56 #include <ufs/ufs/dinode.h> 57 #endif 58 59 #include <protocols/dumprestore.h> 60 61 #include <ctype.h> 62 #include <errno.h> 63 #include <fts.h> 64 #include <stdio.h> 65 #ifdef __STDC__ 66 #include <string.h> 67 #include <unistd.h> 68 #endif 69 70 #include "dump.h" 71 72 #define HASDUMPEDFILE 0x1 73 #define HASSUBDIRS 0x2 74 75 #ifdef FS_44INODEFMT 76 typedef quad_t fsizeT; 77 #else 78 typedef int32_t fsizeT; 79 #endif 80 81 static int dirindir __P((ino_t ino, daddr_t blkno, int level, long *size)); 82 static void dmpindir __P((ino_t ino, daddr_t blk, int level, fsizeT *size)); 83 static int searchdir __P((ino_t ino, daddr_t blkno, long size, long filesize)); 84 85 /* 86 * This is an estimation of the number of TP_BSIZE blocks in the file. 87 * It estimates the number of blocks in files with holes by assuming 88 * that all of the blocks accounted for by di_blocks are data blocks 89 * (when some of the blocks are usually used for indirect pointers); 90 * hence the estimate may be high. 91 */ 92 long 93 blockest(dp) 94 struct dinode *dp; 95 { 96 long blkest, sizeest; 97 98 /* 99 * dp->di_size is the size of the file in bytes. 100 * dp->di_blocks stores the number of sectors actually in the file. 101 * If there are more sectors than the size would indicate, this just 102 * means that there are indirect blocks in the file or unused 103 * sectors in the last file block; we can safely ignore these 104 * (blkest = sizeest below). 105 * If the file is bigger than the number of sectors would indicate, 106 * then the file has holes in it. In this case we must use the 107 * block count to estimate the number of data blocks used, but 108 * we use the actual size for estimating the number of indirect 109 * dump blocks (sizeest vs. blkest in the indirect block 110 * calculation). 111 */ 112 blkest = howmany(dbtob(dp->di_blocks), TP_BSIZE); 113 sizeest = howmany(dp->di_size, TP_BSIZE); 114 if (blkest > sizeest) 115 blkest = sizeest; 116 if (dp->di_size > sblock->fs_bsize * NDADDR) { 117 /* calculate the number of indirect blocks on the dump tape */ 118 blkest += 119 howmany(sizeest - NDADDR * sblock->fs_bsize / TP_BSIZE, 120 TP_NINDIR); 121 } 122 return (blkest + 1); 123 } 124 125 /* Auxiliary macro to pick up files changed since previous dump. */ 126 #define CHANGEDSINCE(dp, t) \ 127 ((dp)->di_mtime >= (t) || (dp)->di_ctime >= (t)) 128 129 /* The WANTTODUMP macro decides whether a file should be dumped. */ 130 #ifdef UF_NODUMP 131 #define WANTTODUMP(dp) \ 132 (CHANGEDSINCE(dp, spcl.c_ddate) && \ 133 (nonodump || ((dp)->di_flags & UF_NODUMP) != UF_NODUMP)) 134 #else 135 #define WANTTODUMP(dp) CHANGEDSINCE(dp, spcl.c_ddate) 136 #endif 137 138 /* 139 * Determine if given inode should be dumped 140 */ 141 void 142 mapfileino(ino, tapesize, dirskipped) 143 ino_t ino; 144 long *tapesize; 145 int *dirskipped; 146 { 147 int mode; 148 struct dinode *dp; 149 150 dp = getino(ino); 151 if ((mode = (dp->di_mode & IFMT)) == 0) 152 return; 153 SETINO(ino, usedinomap); 154 if (mode == IFDIR) 155 SETINO(ino, dumpdirmap); 156 if (WANTTODUMP(dp)) { 157 SETINO(ino, dumpinomap); 158 if (mode != IFREG && mode != IFDIR && mode != IFLNK) 159 *tapesize += 1; 160 else 161 *tapesize += blockest(dp); 162 return; 163 } 164 if (mode == IFDIR) 165 *dirskipped = 1; 166 } 167 168 /* 169 * Dump pass 1. 170 * 171 * Walk the inode list for a filesystem to find all allocated inodes 172 * that have been modified since the previous dump time. Also, find all 173 * the directories in the filesystem. 174 */ 175 int 176 mapfiles(maxino, tapesize, disk, dirv) 177 ino_t maxino; 178 long *tapesize; 179 char *disk; 180 char * const *dirv; 181 { 182 int anydirskipped = 0; 183 184 if (dirv != NULL) { 185 char curdir[MAXPATHLEN]; 186 FTS *dirh; 187 FTSENT *entry; 188 int d; 189 190 if (getcwd(curdir, sizeof(curdir)) == NULL) { 191 msg("Can't determine cwd: %s\n", strerror(errno)); 192 dumpabort(0); 193 } 194 if ((dirh = fts_open(dirv, FTS_PHYSICAL|FTS_SEEDOT|FTS_XDEV, 195 (int (*)())NULL)) == NULL) { 196 msg("fts_open failed: %s\n", strerror(errno)); 197 dumpabort(0); 198 } 199 while ((entry = fts_read(dirh)) != NULL) { 200 switch (entry->fts_info) { 201 case FTS_DNR: /* an error */ 202 case FTS_ERR: 203 case FTS_NS: 204 msg("Can't fts_read %s: %s\n", entry->fts_path, 205 strerror(errno)); 206 case FTS_DP: /* already seen dir */ 207 continue; 208 } 209 mapfileino(entry->fts_statp->st_ino, tapesize, 210 &anydirskipped); 211 } 212 (void)fts_close(dirh); 213 214 /* 215 * Add any parent directories 216 */ 217 for (d = 0 ; dirv[d] != NULL ; d++) { 218 char path[MAXPATHLEN]; 219 220 if (dirv[d][0] != '/') 221 (void)snprintf(path, sizeof(path), "%s/%s", 222 curdir, dirv[d]); 223 else 224 (void)snprintf(path, sizeof(path), "%s", 225 dirv[d]); 226 while (strcmp(path, disk) != 0) { 227 char *p; 228 struct stat sb; 229 230 if (*path == '\0') 231 break; 232 if ((p = strrchr(path, '/')) == NULL) 233 break; 234 if (p == path) 235 break; 236 *p = '\0'; 237 if (stat(path, &sb) == -1) { 238 msg("Can't stat %s: %s\n", path, 239 strerror(errno)); 240 break; 241 } 242 mapfileino(sb.st_ino, tapesize, &anydirskipped); 243 } 244 } 245 246 /* 247 * Ensure that the root inode actually appears in the 248 * file list for a subdir 249 */ 250 mapfileino(ROOTINO, tapesize, &anydirskipped); 251 } else { 252 ino_t ino; 253 254 for (ino = ROOTINO; ino < maxino; ino++) { 255 mapfileino(ino, tapesize, &anydirskipped); 256 } 257 } 258 /* 259 * Restore gets very upset if the root is not dumped, 260 * so ensure that it always is dumped. 261 */ 262 SETINO(ROOTINO, dumpinomap); 263 return (anydirskipped); 264 } 265 266 /* 267 * Dump pass 2. 268 * 269 * Scan each directory on the filesystem to see if it has any modified 270 * files in it. If it does, and has not already been added to the dump 271 * list (because it was itself modified), then add it. If a directory 272 * has not been modified itself, contains no modified files and has no 273 * subdirectories, then it can be deleted from the dump list and from 274 * the list of directories. By deleting it from the list of directories, 275 * its parent may now qualify for the same treatment on this or a later 276 * pass using this algorithm. 277 */ 278 int 279 mapdirs(maxino, tapesize) 280 ino_t maxino; 281 long *tapesize; 282 { 283 struct dinode *dp; 284 int i, isdir; 285 char *map; 286 ino_t ino; 287 long filesize; 288 int ret, change = 0; 289 290 isdir = 0; /* XXX just to get gcc to shut up */ 291 for (map = dumpdirmap, ino = 1; ino < maxino; ino++) { 292 if (((ino - 1) % NBBY) == 0) /* map is offset by 1 */ 293 isdir = *map++; 294 else 295 isdir >>= 1; 296 if ((isdir & 1) == 0 || TSTINO(ino, dumpinomap)) 297 continue; 298 dp = getino(ino); 299 filesize = dp->di_size; 300 for (ret = 0, i = 0; filesize > 0 && i < NDADDR; i++) { 301 if (dp->di_db[i] != 0) 302 ret |= searchdir(ino, dp->di_db[i], 303 (long)dblksize(sblock, dp, i), 304 filesize); 305 if (ret & HASDUMPEDFILE) 306 filesize = 0; 307 else 308 filesize -= sblock->fs_bsize; 309 } 310 for (i = 0; filesize > 0 && i < NIADDR; i++) { 311 if (dp->di_ib[i] == 0) 312 continue; 313 ret |= dirindir(ino, dp->di_ib[i], i, &filesize); 314 } 315 if (ret & HASDUMPEDFILE) { 316 SETINO(ino, dumpinomap); 317 *tapesize += blockest(dp); 318 change = 1; 319 continue; 320 } 321 if ((ret & HASSUBDIRS) == 0) { 322 if (!TSTINO(ino, dumpinomap)) { 323 CLRINO(ino, dumpdirmap); 324 change = 1; 325 } 326 } 327 } 328 return (change); 329 } 330 331 /* 332 * Read indirect blocks, and pass the data blocks to be searched 333 * as directories. Quit as soon as any entry is found that will 334 * require the directory to be dumped. 335 */ 336 static int 337 dirindir(ino, blkno, ind_level, filesize) 338 ino_t ino; 339 daddr_t blkno; 340 int ind_level; 341 long *filesize; 342 { 343 int ret = 0; 344 int i; 345 daddr_t idblk[MAXNINDIR]; 346 347 bread(fsbtodb(sblock, blkno), (char *)idblk, (int)sblock->fs_bsize); 348 if (ind_level <= 0) { 349 for (i = 0; *filesize > 0 && i < NINDIR(sblock); i++) { 350 blkno = idblk[i]; 351 if (blkno != 0) 352 ret |= searchdir(ino, blkno, sblock->fs_bsize, 353 *filesize); 354 if (ret & HASDUMPEDFILE) 355 *filesize = 0; 356 else 357 *filesize -= sblock->fs_bsize; 358 } 359 return (ret); 360 } 361 ind_level--; 362 for (i = 0; *filesize > 0 && i < NINDIR(sblock); i++) { 363 blkno = idblk[i]; 364 if (blkno != 0) 365 ret |= dirindir(ino, blkno, ind_level, filesize); 366 } 367 return (ret); 368 } 369 370 /* 371 * Scan a disk block containing directory information looking to see if 372 * any of the entries are on the dump list and to see if the directory 373 * contains any subdirectories. 374 */ 375 static int 376 searchdir(ino, blkno, size, filesize) 377 ino_t ino; 378 daddr_t blkno; 379 long size; 380 long filesize; 381 { 382 struct direct *dp; 383 long loc, ret = 0; 384 char dblk[MAXBSIZE]; 385 386 bread(fsbtodb(sblock, blkno), dblk, (int)size); 387 if (filesize < size) 388 size = filesize; 389 for (loc = 0; loc < size; ) { 390 dp = (struct direct *)(dblk + loc); 391 if (dp->d_reclen == 0) { 392 msg("corrupted directory, inumber %d\n", ino); 393 break; 394 } 395 loc += dp->d_reclen; 396 if (dp->d_ino == 0) 397 continue; 398 if (dp->d_name[0] == '.') { 399 if (dp->d_name[1] == '\0') 400 continue; 401 if (dp->d_name[1] == '.' && dp->d_name[2] == '\0') 402 continue; 403 } 404 if (TSTINO(dp->d_ino, dumpinomap)) { 405 ret |= HASDUMPEDFILE; 406 if (ret & HASSUBDIRS) 407 break; 408 } 409 if (TSTINO(dp->d_ino, dumpdirmap)) { 410 ret |= HASSUBDIRS; 411 if (ret & HASDUMPEDFILE) 412 break; 413 } 414 } 415 return (ret); 416 } 417 418 /* 419 * Dump passes 3 and 4. 420 * 421 * Dump the contents of an inode to tape. 422 */ 423 void 424 dumpino(dp, ino) 425 struct dinode *dp; 426 ino_t ino; 427 { 428 int ind_level, cnt; 429 fsizeT size; 430 char buf[TP_BSIZE]; 431 432 if (newtape) { 433 newtape = 0; 434 dumpmap(dumpinomap, TS_BITS, ino); 435 } 436 CLRINO(ino, dumpinomap); 437 spcl.c_dinode = *dp; 438 spcl.c_type = TS_INODE; 439 spcl.c_count = 0; 440 switch (dp->di_mode & IFMT) { 441 442 case 0: 443 /* 444 * Freed inode. 445 */ 446 return; 447 448 case IFLNK: 449 /* 450 * Check for short symbolic link. 451 */ 452 if (dp->di_size > 0 && 453 #ifdef FS_44INODEFMT 454 (dp->di_size < sblock->fs_maxsymlinklen || 455 (sblock->fs_maxsymlinklen == 0 && dp->di_blocks == 0))) { 456 #else 457 dp->di_blocks == 0) { 458 #endif 459 spcl.c_addr[0] = 1; 460 spcl.c_count = 1; 461 writeheader(ino); 462 memcpy(buf, dp->di_shortlink, (u_long)dp->di_size); 463 buf[dp->di_size] = '\0'; 464 writerec(buf, 0); 465 return; 466 } 467 /* fall through */ 468 469 case IFDIR: 470 case IFREG: 471 if (dp->di_size > 0) 472 break; 473 /* fall through */ 474 475 case IFIFO: 476 case IFSOCK: 477 case IFCHR: 478 case IFBLK: 479 writeheader(ino); 480 return; 481 482 default: 483 msg("Warning: undefined file type 0%o\n", dp->di_mode & IFMT); 484 return; 485 } 486 if (dp->di_size > NDADDR * sblock->fs_bsize) 487 cnt = NDADDR * sblock->fs_frag; 488 else 489 cnt = howmany(dp->di_size, sblock->fs_fsize); 490 blksout(&dp->di_db[0], cnt, ino); 491 if ((size = dp->di_size - NDADDR * sblock->fs_bsize) <= 0) 492 return; 493 for (ind_level = 0; ind_level < NIADDR; ind_level++) { 494 dmpindir(ino, dp->di_ib[ind_level], ind_level, &size); 495 if (size <= 0) 496 return; 497 } 498 } 499 500 /* 501 * Read indirect blocks, and pass the data blocks to be dumped. 502 */ 503 static void 504 dmpindir(ino, blk, ind_level, size) 505 ino_t ino; 506 daddr_t blk; 507 int ind_level; 508 fsizeT *size; 509 { 510 int i, cnt; 511 daddr_t idblk[MAXNINDIR]; 512 513 if (blk != 0) 514 bread(fsbtodb(sblock, blk), (char *)idblk, (int) sblock->fs_bsize); 515 else 516 memset(idblk, 0, (int)sblock->fs_bsize); 517 if (ind_level <= 0) { 518 if (*size < NINDIR(sblock) * sblock->fs_bsize) 519 cnt = howmany(*size, sblock->fs_fsize); 520 else 521 cnt = NINDIR(sblock) * sblock->fs_frag; 522 *size -= NINDIR(sblock) * sblock->fs_bsize; 523 blksout(&idblk[0], cnt, ino); 524 return; 525 } 526 ind_level--; 527 for (i = 0; i < NINDIR(sblock); i++) { 528 dmpindir(ino, idblk[i], ind_level, size); 529 if (*size <= 0) 530 return; 531 } 532 } 533 534 /* 535 * Collect up the data into tape record sized buffers and output them. 536 */ 537 void 538 blksout(blkp, frags, ino) 539 daddr_t *blkp; 540 int frags; 541 ino_t ino; 542 { 543 daddr_t *bp; 544 int i, j, count, blks, tbperdb; 545 546 blks = howmany(frags * sblock->fs_fsize, TP_BSIZE); 547 tbperdb = sblock->fs_bsize >> tp_bshift; 548 for (i = 0; i < blks; i += TP_NINDIR) { 549 if (i + TP_NINDIR > blks) 550 count = blks; 551 else 552 count = i + TP_NINDIR; 553 for (j = i; j < count; j++) 554 if (blkp[j / tbperdb] != 0) 555 spcl.c_addr[j - i] = 1; 556 else 557 spcl.c_addr[j - i] = 0; 558 spcl.c_count = count - i; 559 writeheader(ino); 560 bp = &blkp[i / tbperdb]; 561 for (j = i; j < count; j += tbperdb, bp++) 562 if (*bp != 0) 563 if (j + tbperdb <= count) 564 dumpblock(*bp, (int)sblock->fs_bsize); 565 else 566 dumpblock(*bp, (count - j) * TP_BSIZE); 567 spcl.c_type = TS_ADDR; 568 } 569 } 570 571 /* 572 * Dump a map to the tape. 573 */ 574 void 575 dumpmap(map, type, ino) 576 char *map; 577 int type; 578 ino_t ino; 579 { 580 int i; 581 char *cp; 582 583 spcl.c_type = type; 584 spcl.c_count = howmany(mapsize * sizeof(char), TP_BSIZE); 585 writeheader(ino); 586 for (i = 0, cp = map; i < spcl.c_count; i++, cp += TP_BSIZE) 587 writerec(cp, 0); 588 } 589 590 /* 591 * Write a header record to the dump tape. 592 */ 593 void 594 writeheader(ino) 595 ino_t ino; 596 { 597 int32_t sum, cnt, *lp; 598 599 spcl.c_inumber = ino; 600 spcl.c_magic = NFS_MAGIC; 601 spcl.c_checksum = 0; 602 lp = (int32_t *)&spcl; 603 sum = 0; 604 cnt = sizeof(union u_spcl) / (4 * sizeof(int32_t)); 605 while (--cnt >= 0) { 606 sum += *lp++; 607 sum += *lp++; 608 sum += *lp++; 609 sum += *lp++; 610 } 611 spcl.c_checksum = CHECKSUM - sum; 612 writerec((char *)&spcl, 1); 613 } 614 615 struct dinode * 616 getino(inum) 617 ino_t inum; 618 { 619 static daddr_t minino, maxino; 620 static struct dinode inoblock[MAXINOPB]; 621 622 curino = inum; 623 if (inum >= minino && inum < maxino) 624 return (&inoblock[inum - minino]); 625 bread(fsbtodb(sblock, ino_to_fsba(sblock, inum)), (char *)inoblock, 626 (int)sblock->fs_bsize); 627 minino = inum - (inum % INOPB(sblock)); 628 maxino = minino + INOPB(sblock); 629 return (&inoblock[inum - minino]); 630 } 631 632 /* 633 * Read a chunk of data from the disk. 634 * Try to recover from hard errors by reading in sector sized pieces. 635 * Error recovery is attempted at most BREADEMAX times before seeking 636 * consent from the operator to continue. 637 */ 638 int breaderrors = 0; 639 #define BREADEMAX 32 640 641 void 642 bread(blkno, buf, size) 643 daddr_t blkno; 644 char *buf; 645 int size; 646 { 647 int cnt, i; 648 extern int errno; 649 650 loop: 651 if (lseek(diskfd, ((off_t)blkno << dev_bshift), 0) < 0) 652 msg("bread: lseek fails\n"); 653 if ((cnt = read(diskfd, buf, size)) == size) 654 return; 655 if (blkno + (size / dev_bsize) > fsbtodb(sblock, sblock->fs_size)) { 656 /* 657 * Trying to read the final fragment. 658 * 659 * NB - dump only works in TP_BSIZE blocks, hence 660 * rounds `dev_bsize' fragments up to TP_BSIZE pieces. 661 * It should be smarter about not actually trying to 662 * read more than it can get, but for the time being 663 * we punt and scale back the read only when it gets 664 * us into trouble. (mkm 9/25/83) 665 */ 666 size -= dev_bsize; 667 goto loop; 668 } 669 if (cnt == -1) 670 msg("read error from %s: %s: [block %d]: count=%d\n", 671 disk, strerror(errno), blkno, size); 672 else 673 msg("short read error from %s: [block %d]: count=%d, got=%d\n", 674 disk, blkno, size, cnt); 675 if (++breaderrors > BREADEMAX) { 676 msg("More than %d block read errors from %d\n", 677 BREADEMAX, disk); 678 broadcast("DUMP IS AILING!\n"); 679 msg("This is an unrecoverable error.\n"); 680 if (!query("Do you want to attempt to continue?")){ 681 dumpabort(0); 682 /*NOTREACHED*/ 683 } else 684 breaderrors = 0; 685 } 686 /* 687 * Zero buffer, then try to read each sector of buffer separately. 688 */ 689 memset(buf, 0, size); 690 for (i = 0; i < size; i += dev_bsize, buf += dev_bsize, blkno++) { 691 if (lseek(diskfd, ((off_t)blkno << dev_bshift), 0) < 0) 692 msg("bread: lseek2 fails!\n"); 693 if ((cnt = read(diskfd, buf, (int)dev_bsize)) == dev_bsize) 694 continue; 695 if (cnt == -1) { 696 msg("read error from %s: %s: [sector %d]: count=%d\n", 697 disk, strerror(errno), blkno, dev_bsize); 698 continue; 699 } 700 msg("short read error from %s: [sector %d]: count=%d, got=%d\n", 701 disk, blkno, dev_bsize, cnt); 702 } 703 } 704