traverse.c revision 1.28
1 /* $NetBSD: traverse.c,v 1.28 1999/10/01 04:35:23 perseant 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 #include <sys/cdefs.h> 37 #ifndef lint 38 #if 0 39 static char sccsid[] = "@(#)traverse.c 8.7 (Berkeley) 6/15/95"; 40 #else 41 __RCSID("$NetBSD: traverse.c,v 1.28 1999/10/01 04:35:23 perseant Exp $"); 42 #endif 43 #endif /* not lint */ 44 45 #include <sys/param.h> 46 #include <sys/time.h> 47 #include <sys/stat.h> 48 #ifdef sunos 49 #include <sys/vnode.h> 50 51 #include <ufs/fs.h> 52 #include <ufs/fsdir.h> 53 #include <ufs/inode.h> 54 #else 55 #include <ufs/ufs/dir.h> 56 #include <ufs/ufs/dinode.h> 57 #include <ufs/ffs/fs.h> 58 #include <ufs/ffs/ffs_extern.h> 59 #endif 60 61 #include <protocols/dumprestore.h> 62 63 #include <ctype.h> 64 #include <errno.h> 65 #include <fts.h> 66 #include <stdio.h> 67 #ifdef __STDC__ 68 #include <string.h> 69 #include <unistd.h> 70 #endif 71 72 #include "dump.h" 73 74 #define HASDUMPEDFILE 0x1 75 #define HASSUBDIRS 0x2 76 77 #ifdef FS_44INODEFMT 78 typedef quad_t fsizeT; 79 #else 80 typedef int32_t fsizeT; 81 #endif 82 83 static int dirindir __P((ino_t ino, daddr_t blkno, int level, long *size, 84 long *tapesize, int nodump)); 85 static void dmpindir __P((ino_t ino, daddr_t blk, int level, fsizeT *size)); 86 static int searchdir __P((ino_t ino, daddr_t blkno, long size, long filesize, 87 long *tapesize, int nodump)); 88 89 /* 90 * This is an estimation of the number of TP_BSIZE blocks in the file. 91 * It estimates the number of blocks in files with holes by assuming 92 * that all of the blocks accounted for by di_blocks are data blocks 93 * (when some of the blocks are usually used for indirect pointers); 94 * hence the estimate may be high. 95 */ 96 long 97 blockest(dp) 98 struct dinode *dp; 99 { 100 long blkest, sizeest; 101 102 /* 103 * dp->di_size is the size of the file in bytes. 104 * dp->di_blocks stores the number of sectors actually in the file. 105 * If there are more sectors than the size would indicate, this just 106 * means that there are indirect blocks in the file or unused 107 * sectors in the last file block; we can safely ignore these 108 * (blkest = sizeest below). 109 * If the file is bigger than the number of sectors would indicate, 110 * then the file has holes in it. In this case we must use the 111 * block count to estimate the number of data blocks used, but 112 * we use the actual size for estimating the number of indirect 113 * dump blocks (sizeest vs. blkest in the indirect block 114 * calculation). 115 */ 116 blkest = howmany(dbtob((u_int64_t)dp->di_blocks), TP_BSIZE); 117 sizeest = howmany(dp->di_size, TP_BSIZE); 118 if (blkest > sizeest) 119 blkest = sizeest; 120 if (dp->di_size > ufsib->ufs_bsize * NDADDR) { 121 /* calculate the number of indirect blocks on the dump tape */ 122 blkest += 123 howmany(sizeest - NDADDR * ufsib->ufs_bsize / TP_BSIZE, 124 TP_NINDIR); 125 } 126 return (blkest + 1); 127 } 128 129 /* Auxiliary macro to pick up files changed since previous dump. */ 130 #define CHANGEDSINCE(dp, t) \ 131 ((dp)->di_mtime >= (t) || (dp)->di_ctime >= (t)) 132 133 /* The WANTTODUMP macro decides whether a file should be dumped. */ 134 #ifdef UF_NODUMP 135 #define WANTTODUMP(dp) \ 136 (CHANGEDSINCE(dp, iswap32(spcl.c_ddate)) && \ 137 (nonodump || ((dp)->di_flags & UF_NODUMP) != UF_NODUMP)) 138 #else 139 #define WANTTODUMP(dp) CHANGEDSINCE(dp, iswap32(spcl.c_ddate)) 140 #endif 141 142 /* 143 * Determine if given inode should be dumped 144 */ 145 void 146 mapfileino(ino, tapesize, dirskipped) 147 ino_t ino; 148 long *tapesize; 149 int *dirskipped; 150 { 151 int mode; 152 struct dinode *dp; 153 154 /* 155 * Skip inode if we've already marked it for dumping 156 */ 157 if (TSTINO(ino, usedinomap)) 158 return; 159 dp = getino(ino); 160 if ((mode = (dp->di_mode & IFMT)) == 0) 161 return; 162 /* 163 * Put all dirs in dumpdirmap, inodes that are to be dumped in the 164 * used map. All inode but dirs who have the nodump attribute go 165 * to the usedinomap. 166 */ 167 SETINO(ino, usedinomap); 168 if (mode == IFDIR) 169 SETINO(ino, dumpdirmap); 170 if (WANTTODUMP(dp)) { 171 SETINO(ino, dumpinomap); 172 if (mode != IFREG && mode != IFDIR && mode != IFLNK) 173 *tapesize += 1; 174 else 175 *tapesize += blockest(dp); 176 return; 177 } 178 if (mode == IFDIR) { 179 #ifdef UF_NODUMP 180 if (!nonodump && (dp->di_flags & UF_NODUMP)) 181 CLRINO(ino, usedinomap); 182 #endif 183 *dirskipped = 1; 184 } 185 } 186 187 /* 188 * Dump pass 1. 189 * 190 * Walk the inode list for a filesystem to find all allocated inodes 191 * that have been modified since the previous dump time. Also, find all 192 * the directories in the filesystem. 193 */ 194 int 195 mapfiles(maxino, tapesize, disk, dirv) 196 ino_t maxino; 197 long *tapesize; 198 char *disk; 199 char * const *dirv; 200 { 201 int anydirskipped = 0; 202 203 if (dirv != NULL) { 204 char curdir[MAXPATHLEN]; 205 FTS *dirh; 206 FTSENT *entry; 207 int d; 208 209 if (getcwd(curdir, sizeof(curdir)) == NULL) { 210 msg("Can't determine cwd: %s\n", strerror(errno)); 211 dumpabort(0); 212 } 213 if ((dirh = fts_open(dirv, FTS_PHYSICAL|FTS_SEEDOT|FTS_XDEV, 214 NULL)) == NULL) { 215 msg("fts_open failed: %s\n", strerror(errno)); 216 dumpabort(0); 217 } 218 while ((entry = fts_read(dirh)) != NULL) { 219 switch (entry->fts_info) { 220 case FTS_DNR: /* an error */ 221 case FTS_ERR: 222 case FTS_NS: 223 msg("Can't fts_read %s: %s\n", entry->fts_path, 224 strerror(errno)); 225 case FTS_DP: /* already seen dir */ 226 continue; 227 } 228 mapfileino(entry->fts_statp->st_ino, tapesize, 229 &anydirskipped); 230 } 231 (void)fts_close(dirh); 232 233 /* 234 * Add any parent directories 235 */ 236 for (d = 0 ; dirv[d] != NULL ; d++) { 237 char path[MAXPATHLEN]; 238 239 if (dirv[d][0] != '/') 240 (void)snprintf(path, sizeof(path), "%s/%s", 241 curdir, dirv[d]); 242 else 243 (void)snprintf(path, sizeof(path), "%s", 244 dirv[d]); 245 while (strcmp(path, disk) != 0) { 246 char *p; 247 struct stat sb; 248 249 if (*path == '\0') 250 break; 251 if ((p = strrchr(path, '/')) == NULL) 252 break; 253 if (p == path) 254 break; 255 *p = '\0'; 256 if (stat(path, &sb) == -1) { 257 msg("Can't stat %s: %s\n", path, 258 strerror(errno)); 259 break; 260 } 261 mapfileino(sb.st_ino, tapesize, &anydirskipped); 262 } 263 } 264 265 /* 266 * Ensure that the root inode actually appears in the 267 * file list for a subdir 268 */ 269 mapfileino(ROOTINO, tapesize, &anydirskipped); 270 } else { 271 ino_t ino; 272 273 for (ino = ROOTINO; ino < maxino; ino++) { 274 mapfileino(ino, tapesize, &anydirskipped); 275 } 276 } 277 /* 278 * Restore gets very upset if the root is not dumped, 279 * so ensure that it always is dumped. 280 */ 281 SETINO(ROOTINO, dumpinomap); 282 return (anydirskipped); 283 } 284 285 /* 286 * Dump pass 2. 287 * 288 * Scan each directory on the filesystem to see if it has any modified 289 * files in it. If it does, and has not already been added to the dump 290 * list (because it was itself modified), then add it. If a directory 291 * has not been modified itself, contains no modified files and has no 292 * subdirectories, then it can be deleted from the dump list and from 293 * the list of directories. By deleting it from the list of directories, 294 * its parent may now qualify for the same treatment on this or a later 295 * pass using this algorithm. 296 */ 297 int 298 mapdirs(maxino, tapesize) 299 ino_t maxino; 300 long *tapesize; 301 { 302 struct dinode *dp, di; 303 int i, isdir, nodump; 304 char *map; 305 ino_t ino; 306 long filesize; 307 int ret, change = 0; 308 309 isdir = 0; /* XXX just to get gcc to shut up */ 310 for (map = dumpdirmap, ino = 1; ino < maxino; ino++) { 311 if (((ino - 1) % NBBY) == 0) /* map is offset by 1 */ 312 isdir = *map++; 313 else 314 isdir >>= 1; 315 /* 316 * If dir has been removed from the used map, it's either 317 * because it had the nodump flag, or it herited it from 318 * its parent. A directory can't be in dumpinomap if 319 * not in usedinomap, but we have to go throuh it anyway 320 * to propagate the nodump attribute. 321 */ 322 nodump = (TSTINO(ino, usedinomap) == 0); 323 if ((isdir & 1) == 0 || 324 (TSTINO(ino, dumpinomap) && nodump == 0)) 325 continue; 326 327 dp = getino(ino); 328 di = *dp; /* inode buf may be changed in searchdir */ 329 filesize = di.di_size; 330 for (ret = 0, i = 0; filesize > 0 && i < NDADDR; i++) { 331 if (di.di_db[i] != 0) 332 ret |= searchdir(ino, iswap32(di.di_db[i]), 333 (long)ufs_dblksize(ufsib, &di, i), 334 filesize, tapesize, nodump); 335 if (ret & HASDUMPEDFILE) 336 filesize = 0; 337 else 338 filesize -= ufsib->ufs_bsize; 339 } 340 for (i = 0; filesize > 0 && i < NIADDR; i++) { 341 if (di.di_ib[i] == 0) 342 continue; 343 ret |= dirindir(ino, di.di_ib[i], i, &filesize, 344 tapesize, nodump); 345 } 346 if (ret & HASDUMPEDFILE) { 347 SETINO(ino, dumpinomap); 348 *tapesize += blockest(&di); 349 change = 1; 350 continue; 351 } 352 if (nodump) { 353 if (ret & HASSUBDIRS) 354 change = 1; /* subdirs have inherited nodump */ 355 CLRINO(ino, dumpdirmap); 356 } else if ((ret & HASSUBDIRS) == 0) { 357 if (!TSTINO(ino, dumpinomap)) { 358 CLRINO(ino, dumpdirmap); 359 change = 1; 360 } 361 } 362 } 363 return (change); 364 } 365 366 /* 367 * Read indirect blocks, and pass the data blocks to be searched 368 * as directories. Quit as soon as any entry is found that will 369 * require the directory to be dumped. 370 */ 371 static int 372 dirindir(ino, blkno, ind_level, filesize, tapesize, nodump) 373 ino_t ino; 374 daddr_t blkno; 375 int ind_level; 376 long *filesize; 377 long *tapesize; 378 int nodump; 379 { 380 int ret = 0; 381 int i; 382 daddr_t idblk[MAXNINDIR]; 383 384 bread(fsatoda(ufsib, iswap32(blkno)), (char *)idblk, 385 (int)ufsib->ufs_bsize); 386 if (ind_level <= 0) { 387 for (i = 0; *filesize > 0 && i < ufsib->ufs_nindir; i++) { 388 blkno = idblk[i]; 389 if (blkno != 0) 390 ret |= searchdir(ino, iswap32(blkno), 391 ufsib->ufs_bsize, *filesize, 392 tapesize, nodump); 393 if (ret & HASDUMPEDFILE) 394 *filesize = 0; 395 else 396 *filesize -= ufsib->ufs_bsize; 397 } 398 return (ret); 399 } 400 ind_level--; 401 for (i = 0; *filesize > 0 && i < ufsib->ufs_nindir; i++) { 402 blkno = idblk[i]; 403 if (blkno != 0) 404 ret |= dirindir(ino, blkno, ind_level, filesize, 405 tapesize, nodump); 406 } 407 return (ret); 408 } 409 410 /* 411 * Scan a disk block containing directory information looking to see if 412 * any of the entries are on the dump list and to see if the directory 413 * contains any subdirectories. 414 */ 415 static int 416 searchdir(dino, blkno, size, filesize, tapesize, nodump) 417 ino_t dino; 418 daddr_t blkno; 419 long size; 420 long filesize; 421 long *tapesize; 422 int nodump; 423 { 424 struct direct *dp; 425 struct dinode *ip; 426 long loc, ret = 0; 427 char dblk[MAXBSIZE]; 428 ino_t ino; 429 430 bread(fsatoda(ufsib, blkno), dblk, (int)size); 431 if (filesize < size) 432 size = filesize; 433 for (loc = 0; loc < size; ) { 434 dp = (struct direct *)(dblk + loc); 435 if (dp->d_reclen == 0) { 436 msg("corrupted directory, inumber %d\n", dino); 437 break; 438 } 439 loc += iswap16(dp->d_reclen); 440 if (dp->d_ino == 0) 441 continue; 442 if (dp->d_name[0] == '.') { 443 if (dp->d_name[1] == '\0') 444 continue; 445 if (dp->d_name[1] == '.' && dp->d_name[2] == '\0') 446 continue; 447 } 448 ino = iswap32(dp->d_ino); 449 if (nodump) { 450 ip = getino(ino); 451 if (TSTINO(ino, dumpinomap)) { 452 CLRINO(ino, dumpinomap); 453 CLRINO(ino, usedinomap); 454 *tapesize -= blockest(ip); 455 } 456 /* Add dir back to the dir map, to propagate nodump */ 457 if ((ip->di_mode & IFMT) == IFDIR) { 458 SETINO(ino, dumpdirmap); 459 ret |= HASSUBDIRS; 460 } 461 } else { 462 if (TSTINO(ino, dumpinomap)) { 463 ret |= HASDUMPEDFILE; 464 if (ret & HASSUBDIRS) 465 break; 466 } 467 if (TSTINO(ino, dumpdirmap)) { 468 ret |= HASSUBDIRS; 469 if (ret & HASDUMPEDFILE) 470 break; 471 } 472 } 473 } 474 return (ret); 475 } 476 477 /* 478 * Dump passes 3 and 4. 479 * 480 * Dump the contents of an inode to tape. 481 */ 482 void 483 dumpino(dp, ino) 484 struct dinode *dp; 485 ino_t ino; 486 { 487 int ind_level, cnt; 488 fsizeT size; 489 char buf[TP_BSIZE]; 490 491 if (newtape) { 492 newtape = 0; 493 dumpmap(dumpinomap, TS_BITS, ino); 494 } 495 CLRINO(ino, dumpinomap); 496 if (needswap) 497 ffs_dinode_swap(dp, &spcl.c_dinode); 498 else 499 spcl.c_dinode = *dp; 500 spcl.c_type = iswap32(TS_INODE); 501 spcl.c_count = 0; 502 switch (dp->di_mode & IFMT) { 503 504 case 0: 505 /* 506 * Freed inode. 507 */ 508 return; 509 510 case IFLNK: 511 /* 512 * Check for short symbolic link. 513 */ 514 if (dp->di_size > 0 && 515 #ifdef FS_44INODEFMT 516 (dp->di_size < ufsib->ufs_maxsymlinklen || 517 (ufsib->ufs_maxsymlinklen == 0 && dp->di_blocks == 0))) { 518 #else 519 dp->di_blocks == 0) { 520 #endif 521 spcl.c_addr[0] = 1; 522 spcl.c_count = iswap32(1); 523 writeheader(ino); 524 memmove(buf, dp->di_shortlink, (u_long)dp->di_size); 525 buf[dp->di_size] = '\0'; 526 writerec(buf, 0); 527 return; 528 } 529 /* fall through */ 530 531 case IFDIR: 532 case IFREG: 533 if (dp->di_size > 0) 534 break; 535 /* fall through */ 536 537 case IFIFO: 538 case IFSOCK: 539 case IFCHR: 540 case IFBLK: 541 writeheader(ino); 542 return; 543 544 default: 545 msg("Warning: undefined file type 0%o\n", dp->di_mode & IFMT); 546 return; 547 } 548 if (dp->di_size > NDADDR * ufsib->ufs_bsize) 549 cnt = NDADDR * ufsib->ufs_frag; 550 else 551 cnt = howmany(dp->di_size, ufsib->ufs_fsize); 552 blksout(&dp->di_db[0], cnt, ino); 553 if ((size = dp->di_size - NDADDR * ufsib->ufs_bsize) <= 0) 554 return; 555 for (ind_level = 0; ind_level < NIADDR; ind_level++) { 556 dmpindir(ino, dp->di_ib[ind_level], ind_level, &size); 557 if (size <= 0) 558 return; 559 } 560 } 561 562 /* 563 * Read indirect blocks, and pass the data blocks to be dumped. 564 */ 565 static void 566 dmpindir(ino, blk, ind_level, size) 567 ino_t ino; 568 daddr_t blk; 569 int ind_level; 570 fsizeT *size; 571 { 572 int i, cnt; 573 daddr_t idblk[MAXNINDIR]; 574 575 if (blk != 0) 576 bread(fsatoda(ufsib, iswap32(blk)), (char *)idblk, 577 (int) ufsib->ufs_bsize); 578 else 579 memset(idblk, 0, (int)ufsib->ufs_bsize); 580 if (ind_level <= 0) { 581 if (*size < ufsib->ufs_nindir * ufsib->ufs_bsize) 582 cnt = howmany(*size, ufsib->ufs_fsize); 583 else 584 cnt = ufsib->ufs_nindir * ufsib->ufs_frag; 585 *size -= ufsib->ufs_nindir * ufsib->ufs_bsize; 586 blksout(&idblk[0], cnt, ino); 587 return; 588 } 589 ind_level--; 590 for (i = 0; i < ufsib->ufs_nindir; i++) { 591 dmpindir(ino, idblk[i], ind_level, size); 592 if (*size <= 0) 593 return; 594 } 595 } 596 597 /* 598 * Collect up the data into tape record sized buffers and output them. 599 */ 600 void 601 blksout(blkp, frags, ino) 602 daddr_t *blkp; 603 int frags; 604 ino_t ino; 605 { 606 daddr_t *bp; 607 int i, j, count, blks, tbperdb; 608 609 blks = howmany(frags * ufsib->ufs_fsize, TP_BSIZE); 610 tbperdb = ufsib->ufs_bsize >> tp_bshift; 611 for (i = 0; i < blks; i += TP_NINDIR) { 612 if (i + TP_NINDIR > blks) 613 count = blks; 614 else 615 count = i + TP_NINDIR; 616 for (j = i; j < count; j++) 617 if (blkp[j / tbperdb] != 0) 618 spcl.c_addr[j - i] = 1; 619 else 620 spcl.c_addr[j - i] = 0; 621 spcl.c_count = iswap32(count - i); 622 writeheader(ino); 623 bp = &blkp[i / tbperdb]; 624 for (j = i; j < count; j += tbperdb, bp++) 625 if (*bp != 0) { 626 if (j + tbperdb <= count) 627 dumpblock(iswap32(*bp), (int)ufsib->ufs_bsize); 628 else 629 dumpblock(iswap32(*bp), (count - j) * TP_BSIZE); 630 } 631 spcl.c_type = iswap32(TS_ADDR); 632 } 633 } 634 635 /* 636 * Dump a map to the tape. 637 */ 638 void 639 dumpmap(map, type, ino) 640 char *map; 641 int type; 642 ino_t ino; 643 { 644 int i; 645 char *cp; 646 647 spcl.c_type = iswap32(type); 648 spcl.c_count = iswap32(howmany(mapsize * sizeof(char), TP_BSIZE)); 649 writeheader(ino); 650 for (i = 0, cp = map; i < iswap32(spcl.c_count); i++, cp += TP_BSIZE) 651 writerec(cp, 0); 652 } 653 654 /* 655 * Write a header record to the dump tape. 656 */ 657 void 658 writeheader(ino) 659 ino_t ino; 660 { 661 int32_t sum, cnt, *lp; 662 663 spcl.c_inumber = iswap32(ino); 664 spcl.c_magic = iswap32(NFS_MAGIC); 665 spcl.c_checksum = 0; 666 lp = (int32_t *)&spcl; 667 sum = 0; 668 cnt = sizeof(union u_spcl) / (4 * sizeof(int32_t)); 669 while (--cnt >= 0) { 670 sum += iswap32(*lp++); 671 sum += iswap32(*lp++); 672 sum += iswap32(*lp++); 673 sum += iswap32(*lp++); 674 } 675 spcl.c_checksum = iswap32(CHECKSUM - sum); 676 writerec((char *)&spcl, 1); 677 } 678
Indexes created Tue Sep 23 14:10:03 GMT 2025