1 /* $NetBSD: traverse.c,v 1.34 2001/12/23 12:54:54 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.34 2001/12/23 12:54:54 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 #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 #include <string.h> 60 #include <unistd.h> 61 62 #include "dump.h" 63 64 #define HASDUMPEDFILE 0x1 65 #define HASSUBDIRS 0x2 66 67 #ifdef FS_44INODEFMT 68 typedef quad_t fsizeT; 69 #else 70 typedef int32_t fsizeT; 71 #endif 72 73 static int dirindir(ino_t, daddr_t, int, long *, long *, int); 74 static void dmpindir(ino_t, daddr_t, int, fsizeT *); 75 static int searchdir(ino_t, daddr_t, long, long, long *, int); 76 77 /* 78 * This is an estimation of the number of TP_BSIZE blocks in the file. 79 * It estimates the number of blocks in files with holes by assuming 80 * that all of the blocks accounted for by di_blocks are data blocks 81 * (when some of the blocks are usually used for indirect pointers); 82 * hence the estimate may be high. 83 */ 84 long 85 blockest(struct dinode *dp) 86 { 87 long blkest, sizeest; 88 89 /* 90 * dp->di_size is the size of the file in bytes. 91 * dp->di_blocks stores the number of sectors actually in the file. 92 * If there are more sectors than the size would indicate, this just 93 * means that there are indirect blocks in the file or unused 94 * sectors in the last file block; we can safely ignore these 95 * (blkest = sizeest below). 96 * If the file is bigger than the number of sectors would indicate, 97 * then the file has holes in it. In this case we must use the 98 * block count to estimate the number of data blocks used, but 99 * we use the actual size for estimating the number of indirect 100 * dump blocks (sizeest vs. blkest in the indirect block 101 * calculation). 102 */ 103 blkest = howmany(dbtob((u_int64_t)dp->di_blocks), TP_BSIZE); 104 sizeest = howmany(dp->di_size, TP_BSIZE); 105 if (blkest > sizeest) 106 blkest = sizeest; 107 if (dp->di_size > ufsib->ufs_bsize * NDADDR) { 108 /* calculate the number of indirect blocks on the dump tape */ 109 blkest += 110 howmany(sizeest - NDADDR * ufsib->ufs_bsize / TP_BSIZE, 111 TP_NINDIR); 112 } 113 return (blkest + 1); 114 } 115 116 /* Auxiliary macro to pick up files changed since previous dump. */ 117 #define CHANGEDSINCE(dp, t) \ 118 ((dp)->di_mtime >= (t) || (dp)->di_ctime >= (t)) 119 120 /* The WANTTODUMP macro decides whether a file should be dumped. */ 121 #ifdef UF_NODUMP 122 #define WANTTODUMP(dp) \ 123 (CHANGEDSINCE(dp, iswap32(spcl.c_ddate)) && \ 124 (nonodump || ((dp)->di_flags & UF_NODUMP) != UF_NODUMP)) 125 #else 126 #define WANTTODUMP(dp) CHANGEDSINCE(dp, iswap32(spcl.c_ddate)) 127 #endif 128 129 /* 130 * Determine if given inode should be dumped 131 */ 132 void 133 mapfileino(ino_t ino, long *tape_size, int *dirskipped) 134 { 135 int mode; 136 struct dinode *dp; 137 138 /* 139 * Skip inode if we've already marked it for dumping 140 */ 141 if (TSTINO(ino, usedinomap)) 142 return; 143 dp = getino(ino); 144 if ((mode = (dp->di_mode & IFMT)) == 0) 145 return; 146 /* 147 * Put all dirs in dumpdirmap, inodes that are to be dumped in the 148 * used map. All inode but dirs who have the nodump attribute go 149 * to the usedinomap. 150 */ 151 SETINO(ino, usedinomap); 152 if (mode == IFDIR) 153 SETINO(ino, dumpdirmap); 154 if (WANTTODUMP(dp)) { 155 SETINO(ino, dumpinomap); 156 if (mode != IFREG && mode != IFDIR && mode != IFLNK) 157 *tape_size += 1; 158 else 159 *tape_size += blockest(dp); 160 return; 161 } 162 if (mode == IFDIR) { 163 #ifdef UF_NODUMP 164 if (!nonodump && (dp->di_flags & UF_NODUMP)) 165 CLRINO(ino, usedinomap); 166 #endif 167 *dirskipped = 1; 168 } 169 } 170 171 /* 172 * Dump pass 1. 173 * 174 * Walk the inode list for a file system to find all allocated inodes 175 * that have been modified since the previous dump time. Also, find all 176 * the directories in the file system. 177 * disk may be NULL if dirv is NULL. 178 */ 179 int 180 mapfiles(ino_t maxino, long *tape_size, char *diskname, 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 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, tape_size, 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, diskname) != 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, tape_size, &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, tape_size, &anydirskipped); 251 } else { 252 ino_t ino; 253 254 for (ino = ROOTINO; ino < maxino; ino++) { 255 mapfileino(ino, tape_size, &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 file system 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(ino_t maxino, long *tape_size) 280 { 281 struct dinode *dp, di; 282 int i, isdir, nodump; 283 char *map; 284 ino_t ino; 285 long filesize; 286 int ret, change = 0; 287 288 isdir = 0; /* XXX just to get gcc to shut up */ 289 for (map = dumpdirmap, ino = 1; ino < maxino; ino++) { 290 if (((ino - 1) % NBBY) == 0) /* map is offset by 1 */ 291 isdir = *map++; 292 else 293 isdir >>= 1; 294 /* 295 * If dir has been removed from the used map, it's either 296 * because it had the nodump flag, or it herited it from 297 * its parent. A directory can't be in dumpinomap if 298 * not in usedinomap, but we have to go throuh it anyway 299 * to propagate the nodump attribute. 300 */ 301 nodump = (TSTINO(ino, usedinomap) == 0); 302 if ((isdir & 1) == 0 || 303 (TSTINO(ino, dumpinomap) && nodump == 0)) 304 continue; 305 306 dp = getino(ino); 307 di = *dp; /* inode buf may be changed in searchdir */ 308 filesize = di.di_size; 309 for (ret = 0, i = 0; filesize > 0 && i < NDADDR; i++) { 310 if (di.di_db[i] != 0) 311 ret |= searchdir(ino, iswap32(di.di_db[i]), 312 (long)ufs_dblksize(ufsib, &di, i), 313 filesize, tape_size, nodump); 314 if (ret & HASDUMPEDFILE) 315 filesize = 0; 316 else 317 filesize -= ufsib->ufs_bsize; 318 } 319 for (i = 0; filesize > 0 && i < NIADDR; i++) { 320 if (di.di_ib[i] == 0) 321 continue; 322 ret |= dirindir(ino, di.di_ib[i], i, &filesize, 323 tape_size, nodump); 324 } 325 if (ret & HASDUMPEDFILE) { 326 SETINO(ino, dumpinomap); 327 *tape_size += blockest(&di); 328 change = 1; 329 continue; 330 } 331 if (nodump) { 332 if (ret & HASSUBDIRS) 333 change = 1; /* subdirs have inherited nodump */ 334 CLRINO(ino, dumpdirmap); 335 } else if ((ret & HASSUBDIRS) == 0) { 336 if (!TSTINO(ino, dumpinomap)) { 337 CLRINO(ino, dumpdirmap); 338 change = 1; 339 } 340 } 341 } 342 return (change); 343 } 344 345 /* 346 * Read indirect blocks, and pass the data blocks to be searched 347 * as directories. Quit as soon as any entry is found that will 348 * require the directory to be dumped. 349 */ 350 static int 351 dirindir(ino_t ino, daddr_t blkno, int ind_level, long *filesize, 352 long *tape_size, int nodump) 353 { 354 int ret = 0; 355 int i; 356 daddr_t idblk[MAXNINDIR]; 357 358 bread(fsatoda(ufsib, iswap32(blkno)), (char *)idblk, 359 (int)ufsib->ufs_bsize); 360 if (ind_level <= 0) { 361 for (i = 0; *filesize > 0 && i < ufsib->ufs_nindir; i++) { 362 blkno = idblk[i]; 363 if (blkno != 0) 364 ret |= searchdir(ino, iswap32(blkno), 365 ufsib->ufs_bsize, *filesize, 366 tape_size, nodump); 367 if (ret & HASDUMPEDFILE) 368 *filesize = 0; 369 else 370 *filesize -= ufsib->ufs_bsize; 371 } 372 return (ret); 373 } 374 ind_level--; 375 for (i = 0; *filesize > 0 && i < ufsib->ufs_nindir; i++) { 376 blkno = idblk[i]; 377 if (blkno != 0) 378 ret |= dirindir(ino, blkno, ind_level, filesize, 379 tape_size, nodump); 380 } 381 return (ret); 382 } 383 384 /* 385 * Scan a disk block containing directory information looking to see if 386 * any of the entries are on the dump list and to see if the directory 387 * contains any subdirectories. 388 */ 389 static int 390 searchdir(ino_t dino, daddr_t blkno, long size, long filesize, 391 long *tape_size, int nodump) 392 { 393 struct direct *dp; 394 struct dinode *ip; 395 long loc, ret = 0; 396 char dblk[MAXBSIZE]; 397 ino_t ino; 398 399 bread(fsatoda(ufsib, blkno), dblk, (int)size); 400 if (filesize < size) 401 size = filesize; 402 for (loc = 0; loc < size; ) { 403 dp = (struct direct *)(dblk + loc); 404 if (dp->d_reclen == 0) { 405 msg("corrupted directory, inumber %d\n", dino); 406 break; 407 } 408 loc += iswap16(dp->d_reclen); 409 if (dp->d_ino == 0) 410 continue; 411 if (dp->d_name[0] == '.') { 412 if (dp->d_name[1] == '\0') 413 continue; 414 if (dp->d_name[1] == '.' && dp->d_name[2] == '\0') 415 continue; 416 } 417 ino = iswap32(dp->d_ino); 418 if (nodump) { 419 ip = getino(ino); 420 if (TSTINO(ino, dumpinomap)) { 421 CLRINO(ino, dumpinomap); 422 CLRINO(ino, usedinomap); 423 *tape_size -= blockest(ip); 424 } 425 /* Add dir back to the dir map, to propagate nodump */ 426 if ((ip->di_mode & IFMT) == IFDIR) { 427 SETINO(ino, dumpdirmap); 428 ret |= HASSUBDIRS; 429 } 430 } else { 431 if (TSTINO(ino, dumpinomap)) { 432 ret |= HASDUMPEDFILE; 433 if (ret & HASSUBDIRS) 434 break; 435 } 436 if (TSTINO(ino, dumpdirmap)) { 437 ret |= HASSUBDIRS; 438 if (ret & HASDUMPEDFILE) 439 break; 440 } 441 } 442 } 443 return (ret); 444 } 445 446 /* 447 * Dump passes 3 and 4. 448 * 449 * Dump the contents of an inode to tape. 450 */ 451 void 452 dumpino(struct dinode *dp, ino_t ino) 453 { 454 int ind_level, cnt; 455 fsizeT size; 456 char buf[TP_BSIZE]; 457 458 if (newtape) { 459 newtape = 0; 460 dumpmap(dumpinomap, TS_BITS, ino); 461 } 462 CLRINO(ino, dumpinomap); 463 if (needswap) 464 ffs_dinode_swap(dp, &spcl.c_dinode); 465 else 466 spcl.c_dinode = *dp; 467 spcl.c_type = iswap32(TS_INODE); 468 spcl.c_count = 0; 469 switch (dp->di_mode & IFMT) { 470 471 case 0: 472 /* 473 * Freed inode. 474 */ 475 return; 476 477 case IFLNK: 478 /* 479 * Check for short symbolic link. 480 */ 481 if (dp->di_size > 0 && 482 #ifdef FS_44INODEFMT 483 (dp->di_size < ufsib->ufs_maxsymlinklen || 484 (ufsib->ufs_maxsymlinklen == 0 && dp->di_blocks == 0)) 485 #else 486 dp->di_blocks == 0 487 #endif 488 ) { 489 spcl.c_addr[0] = 1; 490 spcl.c_count = iswap32(1); 491 writeheader(ino); 492 memmove(buf, dp->di_shortlink, (u_long)dp->di_size); 493 buf[dp->di_size] = '\0'; 494 writerec(buf, 0); 495 return; 496 } 497 /* fall through */ 498 499 case IFDIR: 500 case IFREG: 501 if (dp->di_size > 0) 502 break; 503 /* fall through */ 504 505 case IFIFO: 506 case IFSOCK: 507 case IFCHR: 508 case IFBLK: 509 writeheader(ino); 510 return; 511 512 default: 513 msg("Warning: undefined file type 0%o\n", dp->di_mode & IFMT); 514 return; 515 } 516 if (dp->di_size > NDADDR * ufsib->ufs_bsize) 517 cnt = NDADDR * ufsib->ufs_frag; 518 else 519 cnt = howmany(dp->di_size, ufsib->ufs_fsize); 520 blksout(&dp->di_db[0], cnt, ino); 521 if ((size = dp->di_size - NDADDR * ufsib->ufs_bsize) <= 0) 522 return; 523 for (ind_level = 0; ind_level < NIADDR; ind_level++) { 524 dmpindir(ino, dp->di_ib[ind_level], ind_level, &size); 525 if (size <= 0) 526 return; 527 } 528 } 529 530 /* 531 * Read indirect blocks, and pass the data blocks to be dumped. 532 */ 533 static void 534 dmpindir(ino_t ino, daddr_t blk, int ind_level, fsizeT *size) 535 { 536 int i, cnt; 537 daddr_t idblk[MAXNINDIR]; 538 539 if (blk != 0) 540 bread(fsatoda(ufsib, iswap32(blk)), (char *)idblk, 541 (int) ufsib->ufs_bsize); 542 else 543 memset(idblk, 0, (int)ufsib->ufs_bsize); 544 if (ind_level <= 0) { 545 if (*size < ufsib->ufs_nindir * ufsib->ufs_bsize) 546 cnt = howmany(*size, ufsib->ufs_fsize); 547 else 548 cnt = ufsib->ufs_nindir * ufsib->ufs_frag; 549 *size -= ufsib->ufs_nindir * ufsib->ufs_bsize; 550 blksout(&idblk[0], cnt, ino); 551 return; 552 } 553 ind_level--; 554 for (i = 0; i < ufsib->ufs_nindir; i++) { 555 dmpindir(ino, idblk[i], ind_level, size); 556 if (*size <= 0) 557 return; 558 } 559 } 560 561 /* 562 * Collect up the data into tape record sized buffers and output them. 563 */ 564 void 565 blksout(daddr_t *blkp, int frags, ino_t ino) 566 { 567 daddr_t *bp; 568 int i, j, count, blks, tbperdb; 569 570 blks = howmany(frags * ufsib->ufs_fsize, TP_BSIZE); 571 tbperdb = ufsib->ufs_bsize >> tp_bshift; 572 for (i = 0; i < blks; i += TP_NINDIR) { 573 if (i + TP_NINDIR > blks) 574 count = blks; 575 else 576 count = i + TP_NINDIR; 577 for (j = i; j < count; j++) 578 if (blkp[j / tbperdb] != 0) 579 spcl.c_addr[j - i] = 1; 580 else 581 spcl.c_addr[j - i] = 0; 582 spcl.c_count = iswap32(count - i); 583 writeheader(ino); 584 bp = &blkp[i / tbperdb]; 585 for (j = i; j < count; j += tbperdb, bp++) 586 if (*bp != 0) { 587 if (j + tbperdb <= count) 588 dumpblock(iswap32(*bp), (int)ufsib->ufs_bsize); 589 else 590 dumpblock(iswap32(*bp), (count - j) * TP_BSIZE); 591 } 592 spcl.c_type = iswap32(TS_ADDR); 593 } 594 } 595 596 /* 597 * Dump a map to the tape. 598 */ 599 void 600 dumpmap(char *map, int type, ino_t ino) 601 { 602 int i; 603 char *cp; 604 605 spcl.c_type = iswap32(type); 606 spcl.c_count = iswap32(howmany(mapsize * sizeof(char), TP_BSIZE)); 607 writeheader(ino); 608 for (i = 0, cp = map; i < iswap32(spcl.c_count); i++, cp += TP_BSIZE) 609 writerec(cp, 0); 610 } 611 612 /* 613 * Write a header record to the dump tape. 614 */ 615 void 616 writeheader(ino_t ino) 617 { 618 int32_t sum, cnt, *lp; 619 620 spcl.c_inumber = iswap32(ino); 621 spcl.c_magic = iswap32(NFS_MAGIC); 622 spcl.c_checksum = 0; 623 lp = (int32_t *)&spcl; 624 sum = 0; 625 cnt = sizeof(union u_spcl) / (4 * sizeof(int32_t)); 626 while (--cnt >= 0) { 627 sum += iswap32(*lp++); 628 sum += iswap32(*lp++); 629 sum += iswap32(*lp++); 630 sum += iswap32(*lp++); 631 } 632 spcl.c_checksum = iswap32(CHECKSUM - sum); 633 writerec((char *)&spcl, 1); 634 } 635