traverse.c revision 1.35
1 /* $NetBSD: traverse.c,v 1.35 2002/09/30 10:48:49 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.35 2002/09/30 10:48:49 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 *tape_size -= blockest(ip); 423 } 424 /* 425 * Add back to dumpdirmap and remove from usedinomap 426 * to propagate nodump. 427 */ 428 if ((ip->di_mode & IFMT) == IFDIR) { 429 SETINO(ino, dumpdirmap); 430 CLRINO(ino, usedinomap); 431 ret |= HASSUBDIRS; 432 } 433 } else { 434 if (TSTINO(ino, dumpinomap)) { 435 ret |= HASDUMPEDFILE; 436 if (ret & HASSUBDIRS) 437 break; 438 } 439 if (TSTINO(ino, dumpdirmap)) { 440 ret |= HASSUBDIRS; 441 if (ret & HASDUMPEDFILE) 442 break; 443 } 444 } 445 } 446 return (ret); 447 } 448 449 /* 450 * Dump passes 3 and 4. 451 * 452 * Dump the contents of an inode to tape. 453 */ 454 void 455 dumpino(struct dinode *dp, ino_t ino) 456 { 457 int ind_level, cnt; 458 fsizeT size; 459 char buf[TP_BSIZE]; 460 461 if (newtape) { 462 newtape = 0; 463 dumpmap(dumpinomap, TS_BITS, ino); 464 } 465 CLRINO(ino, dumpinomap); 466 if (needswap) 467 ffs_dinode_swap(dp, &spcl.c_dinode); 468 else 469 spcl.c_dinode = *dp; 470 spcl.c_type = iswap32(TS_INODE); 471 spcl.c_count = 0; 472 switch (dp->di_mode & IFMT) { 473 474 case 0: 475 /* 476 * Freed inode. 477 */ 478 return; 479 480 case IFLNK: 481 /* 482 * Check for short symbolic link. 483 */ 484 if (dp->di_size > 0 && 485 #ifdef FS_44INODEFMT 486 (dp->di_size < ufsib->ufs_maxsymlinklen || 487 (ufsib->ufs_maxsymlinklen == 0 && dp->di_blocks == 0)) 488 #else 489 dp->di_blocks == 0 490 #endif 491 ) { 492 spcl.c_addr[0] = 1; 493 spcl.c_count = iswap32(1); 494 writeheader(ino); 495 memmove(buf, dp->di_shortlink, (u_long)dp->di_size); 496 buf[dp->di_size] = '\0'; 497 writerec(buf, 0); 498 return; 499 } 500 /* fall through */ 501 502 case IFDIR: 503 case IFREG: 504 if (dp->di_size > 0) 505 break; 506 /* fall through */ 507 508 case IFIFO: 509 case IFSOCK: 510 case IFCHR: 511 case IFBLK: 512 writeheader(ino); 513 return; 514 515 default: 516 msg("Warning: undefined file type 0%o\n", dp->di_mode & IFMT); 517 return; 518 } 519 if (dp->di_size > NDADDR * ufsib->ufs_bsize) 520 cnt = NDADDR * ufsib->ufs_frag; 521 else 522 cnt = howmany(dp->di_size, ufsib->ufs_fsize); 523 blksout(&dp->di_db[0], cnt, ino); 524 if ((size = dp->di_size - NDADDR * ufsib->ufs_bsize) <= 0) 525 return; 526 for (ind_level = 0; ind_level < NIADDR; ind_level++) { 527 dmpindir(ino, dp->di_ib[ind_level], ind_level, &size); 528 if (size <= 0) 529 return; 530 } 531 } 532 533 /* 534 * Read indirect blocks, and pass the data blocks to be dumped. 535 */ 536 static void 537 dmpindir(ino_t ino, daddr_t blk, int ind_level, fsizeT *size) 538 { 539 int i, cnt; 540 daddr_t idblk[MAXNINDIR]; 541 542 if (blk != 0) 543 bread(fsatoda(ufsib, iswap32(blk)), (char *)idblk, 544 (int) ufsib->ufs_bsize); 545 else 546 memset(idblk, 0, (int)ufsib->ufs_bsize); 547 if (ind_level <= 0) { 548 if (*size < ufsib->ufs_nindir * ufsib->ufs_bsize) 549 cnt = howmany(*size, ufsib->ufs_fsize); 550 else 551 cnt = ufsib->ufs_nindir * ufsib->ufs_frag; 552 *size -= ufsib->ufs_nindir * ufsib->ufs_bsize; 553 blksout(&idblk[0], cnt, ino); 554 return; 555 } 556 ind_level--; 557 for (i = 0; i < ufsib->ufs_nindir; i++) { 558 dmpindir(ino, idblk[i], ind_level, size); 559 if (*size <= 0) 560 return; 561 } 562 } 563 564 /* 565 * Collect up the data into tape record sized buffers and output them. 566 */ 567 void 568 blksout(daddr_t *blkp, int frags, ino_t ino) 569 { 570 daddr_t *bp; 571 int i, j, count, blks, tbperdb; 572 573 blks = howmany(frags * ufsib->ufs_fsize, TP_BSIZE); 574 tbperdb = ufsib->ufs_bsize >> tp_bshift; 575 for (i = 0; i < blks; i += TP_NINDIR) { 576 if (i + TP_NINDIR > blks) 577 count = blks; 578 else 579 count = i + TP_NINDIR; 580 for (j = i; j < count; j++) 581 if (blkp[j / tbperdb] != 0) 582 spcl.c_addr[j - i] = 1; 583 else 584 spcl.c_addr[j - i] = 0; 585 spcl.c_count = iswap32(count - i); 586 writeheader(ino); 587 bp = &blkp[i / tbperdb]; 588 for (j = i; j < count; j += tbperdb, bp++) 589 if (*bp != 0) { 590 if (j + tbperdb <= count) 591 dumpblock(iswap32(*bp), (int)ufsib->ufs_bsize); 592 else 593 dumpblock(iswap32(*bp), (count - j) * TP_BSIZE); 594 } 595 spcl.c_type = iswap32(TS_ADDR); 596 } 597 } 598 599 /* 600 * Dump a map to the tape. 601 */ 602 void 603 dumpmap(char *map, int type, ino_t ino) 604 { 605 int i; 606 char *cp; 607 608 spcl.c_type = iswap32(type); 609 spcl.c_count = iswap32(howmany(mapsize * sizeof(char), TP_BSIZE)); 610 writeheader(ino); 611 for (i = 0, cp = map; i < iswap32(spcl.c_count); i++, cp += TP_BSIZE) 612 writerec(cp, 0); 613 } 614 615 /* 616 * Write a header record to the dump tape. 617 */ 618 void 619 writeheader(ino_t ino) 620 { 621 int32_t sum, cnt, *lp; 622 623 spcl.c_inumber = iswap32(ino); 624 spcl.c_magic = iswap32(NFS_MAGIC); 625 spcl.c_checksum = 0; 626 lp = (int32_t *)&spcl; 627 sum = 0; 628 cnt = sizeof(union u_spcl) / (4 * sizeof(int32_t)); 629 while (--cnt >= 0) { 630 sum += iswap32(*lp++); 631 sum += iswap32(*lp++); 632 sum += iswap32(*lp++); 633 sum += iswap32(*lp++); 634 } 635 spcl.c_checksum = iswap32(CHECKSUM - sum); 636 writerec((char *)&spcl, 1); 637 } 638
Indexes created Tue Sep 23 14:10:03 GMT 2025