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