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