1 /*- 2 * Copyright (c) 1980, 1988, 1991 The Regents of the University of California. 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 3. All advertising materials mentioning features or use of this software 14 * must display the following acknowledgement: 15 * This product includes software developed by the University of 16 * California, Berkeley and its contributors. 17 * 4. Neither the name of the University nor the names of its contributors 18 * may be used to endorse or promote products derived from this software 19 * without specific prior written permission. 20 * 21 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 22 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 24 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 25 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 26 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 27 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 30 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 31 * SUCH DAMAGE. 32 */ 33 34 #ifndef lint 35 /* from: static char sccsid[] = "@(#)traverse.c 5.21 (Berkeley) 7/19/92"; */ 36 static char *rcsid = "$Id: traverse.c,v 1.3 1994/04/25 18:22:50 cgd Exp $"; 37 #endif /* not lint */ 38 39 #ifdef sunos 40 #include <stdio.h> 41 #include <ctype.h> 42 #include <sys/param.h> 43 #include <ufs/fs.h> 44 #else 45 #include <sys/param.h> 46 #include <ufs/fs.h> 47 #endif 48 #include <sys/time.h> 49 #include <sys/stat.h> 50 #include <ufs/dir.h> 51 #include <ufs/dinode.h> 52 #include <protocols/dumprestore.h> 53 #ifdef __STDC__ 54 #include <unistd.h> 55 #include <string.h> 56 #endif 57 #include "dump.h" 58 59 void dmpindir(); 60 #define HASDUMPEDFILE 0x1 61 #define HASSUBDIRS 0x2 62 63 /* 64 * This is an estimation of the number of TP_BSIZE blocks in the file. 65 * It estimates the number of blocks in files with holes by assuming 66 * that all of the blocks accounted for by di_blocks are data blocks 67 * (when some of the blocks are usually used for indirect pointers); 68 * hence the estimate may be high. 69 */ 70 long 71 blockest(dp) 72 register struct dinode *dp; 73 { 74 long blkest, sizeest; 75 76 /* 77 * dp->di_size is the size of the file in bytes. 78 * dp->di_blocks stores the number of sectors actually in the file. 79 * If there are more sectors than the size would indicate, this just 80 * means that there are indirect blocks in the file or unused 81 * sectors in the last file block; we can safely ignore these 82 * (blkest = sizeest below). 83 * If the file is bigger than the number of sectors would indicate, 84 * then the file has holes in it. In this case we must use the 85 * block count to estimate the number of data blocks used, but 86 * we use the actual size for estimating the number of indirect 87 * dump blocks (sizeest vs. blkest in the indirect block 88 * calculation). 89 */ 90 blkest = howmany(dbtob(dp->di_blocks), TP_BSIZE); 91 sizeest = howmany(dp->di_size, TP_BSIZE); 92 if (blkest > sizeest) 93 blkest = sizeest; 94 if (dp->di_size > sblock->fs_bsize * NDADDR) { 95 /* calculate the number of indirect blocks on the dump tape */ 96 blkest += 97 howmany(sizeest - NDADDR * sblock->fs_bsize / TP_BSIZE, 98 TP_NINDIR); 99 } 100 return (blkest + 1); 101 } 102 103 /* 104 * Dump pass 1. 105 * 106 * Walk the inode list for a filesystem to find all allocated inodes 107 * that have been modified since the previous dump time. Also, find all 108 * the directories in the filesystem. 109 */ 110 mapfiles(maxino, tapesize) 111 ino_t maxino; 112 long *tapesize; 113 { 114 register int mode; 115 register ino_t ino; 116 register struct dinode *dp; 117 int anydirskipped = 0; 118 119 for (ino = ROOTINO; ino < maxino; ino++) { 120 dp = getino(ino); 121 if ((mode = (dp->di_mode & IFMT)) == 0) 122 continue; 123 SETINO(ino, usedinomap); 124 if (mode == IFDIR) 125 SETINO(ino, dumpdirmap); 126 if ((dp->di_mtime.ts_sec >= spcl.c_ddate || 127 dp->di_ctime.ts_sec >= spcl.c_ddate) 128 #ifdef BSD44 129 # ifndef sunos 130 && (dp->di_flags & NODUMP) != NODUMP 131 # endif /* sunos */ 132 #endif /* BSD44 */ 133 ) { 134 SETINO(ino, dumpinomap); 135 if (mode != IFREG && mode != IFDIR && mode != IFLNK) { 136 *tapesize += 1; 137 continue; 138 } 139 *tapesize += blockest(dp); 140 continue; 141 } 142 if (mode == IFDIR) 143 anydirskipped = 1; 144 } 145 /* 146 * Restore gets very upset if the root is not dumped, 147 * so ensure that it always is dumped. 148 */ 149 SETINO(ROOTINO, dumpinomap); 150 return (anydirskipped); 151 } 152 153 /* 154 * Dump pass 2. 155 * 156 * Scan each directory on the filesystem to see if it has any modified 157 * files in it. If it does, and has not already been added to the dump 158 * list (because it was itself modified), then add it. If a directory 159 * has not been modified itself, contains no modified files and has no 160 * subdirectories, then it can be deleted from the dump list and from 161 * the list of directories. By deleting it from the list of directories, 162 * its parent may now qualify for the same treatment on this or a later 163 * pass using this algorithm. 164 */ 165 mapdirs(maxino, tapesize) 166 ino_t maxino; 167 long *tapesize; 168 { 169 register struct dinode *dp; 170 register int i, isdir; 171 register char *map; 172 register ino_t ino; 173 long filesize; 174 int ret, change = 0; 175 176 for (map = dumpdirmap, ino = 0; ino < maxino; ) { 177 if ((ino % NBBY) == 0) 178 isdir = *map++; 179 else 180 isdir >>= 1; 181 ino++; 182 if ((isdir & 1) == 0 || TSTINO(ino, dumpinomap)) 183 continue; 184 dp = getino(ino); 185 filesize = dp->di_size; 186 for (ret = 0, i = 0; filesize > 0 && i < NDADDR; i++) { 187 if (dp->di_db[i] != 0) 188 ret |= searchdir(ino, dp->di_db[i], 189 (long)dblksize(sblock, dp, i), 190 filesize); 191 if (ret & HASDUMPEDFILE) 192 filesize = 0; 193 else 194 filesize -= sblock->fs_bsize; 195 } 196 for (i = 0; filesize > 0 && i < NIADDR; i++) { 197 if (dp->di_ib[i] == 0) 198 continue; 199 ret |= dirindir(ino, dp->di_ib[i], i, &filesize); 200 } 201 if (ret & HASDUMPEDFILE) { 202 SETINO(ino, dumpinomap); 203 *tapesize += blockest(dp); 204 change = 1; 205 continue; 206 } 207 if ((ret & HASSUBDIRS) == 0) { 208 if (!TSTINO(ino, dumpinomap)) { 209 CLRINO(ino, dumpdirmap); 210 change = 1; 211 } 212 } 213 } 214 return (change); 215 } 216 217 /* 218 * Read indirect blocks, and pass the data blocks to be searched 219 * as directories. Quit as soon as any entry is found that will 220 * require the directory to be dumped. 221 */ 222 dirindir(ino, blkno, ind_level, filesize) 223 ino_t ino; 224 daddr_t blkno; 225 int ind_level; 226 long *filesize; 227 { 228 int ret = 0; 229 register int i; 230 daddr_t idblk[MAXNINDIR]; 231 232 bread(fsbtodb(sblock, blkno), (char *)idblk, (int)sblock->fs_bsize); 233 if (ind_level <= 0) { 234 for (i = 0; *filesize > 0 && i < NINDIR(sblock); i++) { 235 blkno = idblk[i]; 236 if (blkno != 0) 237 ret |= searchdir(ino, blkno, sblock->fs_bsize, 238 *filesize); 239 if (ret & HASDUMPEDFILE) 240 *filesize = 0; 241 else 242 *filesize -= sblock->fs_bsize; 243 } 244 return (ret); 245 } 246 ind_level--; 247 for (i = 0; *filesize > 0 && i < NINDIR(sblock); i++) { 248 blkno = idblk[i]; 249 if (blkno != 0) 250 ret |= dirindir(ino, blkno, ind_level, filesize); 251 } 252 return (ret); 253 } 254 255 /* 256 * Scan a disk block containing directory information looking to see if 257 * any of the entries are on the dump list and to see if the directory 258 * contains any subdirectories. 259 */ 260 searchdir(ino, blkno, size, filesize) 261 ino_t ino; 262 daddr_t blkno; 263 register long size; 264 long filesize; 265 { 266 register struct direct *dp; 267 register long loc, ret = 0; 268 char dblk[MAXBSIZE]; 269 270 bread(fsbtodb(sblock, blkno), dblk, (int)size); 271 if (filesize < size) 272 size = filesize; 273 for (loc = 0; loc < size; ) { 274 dp = (struct direct *)(dblk + loc); 275 if (dp->d_reclen == 0) { 276 msg("corrupted directory, inumber %d\n", ino); 277 break; 278 } 279 loc += dp->d_reclen; 280 if (dp->d_ino == 0) 281 continue; 282 if (dp->d_name[0] == '.') { 283 if (dp->d_name[1] == '\0') 284 continue; 285 if (dp->d_name[1] == '.' && dp->d_name[2] == '\0') 286 continue; 287 } 288 if (TSTINO(dp->d_ino, dumpinomap)) { 289 ret |= HASDUMPEDFILE; 290 if (ret & HASSUBDIRS) 291 break; 292 } 293 if (TSTINO(dp->d_ino, dumpdirmap)) { 294 ret |= HASSUBDIRS; 295 if (ret & HASDUMPEDFILE) 296 break; 297 } 298 } 299 return (ret); 300 } 301 302 /* 303 * Dump passes 3 and 4. 304 * 305 * Dump the contents of an inode to tape. 306 */ 307 void 308 dumpino(dp, ino) 309 register struct dinode *dp; 310 ino_t ino; 311 { 312 int ind_level, cnt; 313 long size; 314 char buf[TP_BSIZE]; 315 316 if (newtape) { 317 newtape = 0; 318 dumpmap(dumpinomap, TS_BITS, ino); 319 } 320 CLRINO(ino, dumpinomap); 321 spcl.c_dinode = *dp; 322 spcl.c_type = TS_INODE; 323 spcl.c_count = 0; 324 325 switch (IFTODT(dp->di_mode)) { 326 327 case DT_UNKNOWN: 328 /* 329 * Freed inode. 330 */ 331 return; 332 333 case DT_LNK: 334 #ifdef BSD44 335 /* 336 * Check for short symbolic link. 337 */ 338 if (dp->di_size > 0 && 339 dp->di_size < sblock->fs_maxsymlinklen) { 340 spcl.c_addr[0] = 1; 341 spcl.c_count = 1; 342 writeheader(ino); 343 bcopy((caddr_t)dp->di_shortlink, buf, 344 (u_long)dp->di_size); 345 buf[dp->di_size] = '\0'; 346 writerec(buf, 0); 347 return; 348 } 349 #endif 350 #ifdef NetBSD 351 if (DFASTLINK(*dp)) { 352 spcl.c_addr[0] = 1; 353 spcl.c_count = 1; 354 writeheader(ino); 355 bcopy((caddr_t)dp->di_symlink, buf, 356 (u_long)dp->di_size); 357 buf[dp->di_size] = '\0'; 358 writerec(buf, 0); 359 return; 360 } 361 #endif 362 /* fall through */ 363 364 case DT_DIR: 365 case DT_REG: 366 if (dp->di_size > 0) 367 break; 368 /* fall through */ 369 370 case DT_FIFO: 371 case DT_SOCK: 372 case DT_CHR: 373 case DT_BLK: 374 writeheader(ino); 375 return; 376 377 default: 378 msg("Warning: undefined file type 0%o\n", dp->di_mode & IFMT); 379 return; 380 } 381 382 if (dp->di_size > NDADDR * sblock->fs_bsize) 383 cnt = NDADDR * sblock->fs_frag; 384 else 385 cnt = howmany(dp->di_size, sblock->fs_fsize); 386 blksout(&dp->di_db[0], cnt, ino); 387 if ((size = dp->di_size - NDADDR * sblock->fs_bsize) <= 0) 388 return; 389 for (ind_level = 0; ind_level < NIADDR; ind_level++) { 390 dmpindir(ino, dp->di_ib[ind_level], ind_level, &size); 391 if (size <= 0) 392 return; 393 } 394 } 395 396 /* 397 * Read indirect blocks, and pass the data blocks to be dumped. 398 */ 399 void 400 dmpindir(ino, blk, ind_level, size) 401 ino_t ino; 402 daddr_t blk; 403 int ind_level; 404 long *size; 405 { 406 int i, cnt; 407 daddr_t idblk[MAXNINDIR]; 408 409 if (blk != 0) 410 bread(fsbtodb(sblock, blk), (char *)idblk, (int) sblock->fs_bsize); 411 else 412 bzero((char *)idblk, (int)sblock->fs_bsize); 413 if (ind_level <= 0) { 414 if (*size < NINDIR(sblock) * sblock->fs_bsize) 415 cnt = howmany(*size, sblock->fs_fsize); 416 else 417 cnt = NINDIR(sblock) * sblock->fs_frag; 418 *size -= NINDIR(sblock) * sblock->fs_bsize; 419 blksout(&idblk[0], cnt, ino); 420 return; 421 } 422 ind_level--; 423 for (i = 0; i < NINDIR(sblock); i++) { 424 dmpindir(ino, idblk[i], ind_level, size); 425 if (*size <= 0) 426 return; 427 } 428 } 429 430 /* 431 * Collect up the data into tape record sized buffers and output them. 432 */ 433 void 434 blksout(blkp, frags, ino) 435 daddr_t *blkp; 436 int frags; 437 ino_t ino; 438 { 439 register daddr_t *bp; 440 int i, j, count, blks, tbperdb; 441 442 blks = howmany(frags * sblock->fs_fsize, TP_BSIZE); 443 tbperdb = sblock->fs_bsize >> tp_bshift; 444 for (i = 0; i < blks; i += TP_NINDIR) { 445 if (i + TP_NINDIR > blks) 446 count = blks; 447 else 448 count = i + TP_NINDIR; 449 for (j = i; j < count; j++) 450 if (blkp[j / tbperdb] != 0) 451 spcl.c_addr[j - i] = 1; 452 else 453 spcl.c_addr[j - i] = 0; 454 spcl.c_count = count - i; 455 writeheader(ino); 456 bp = &blkp[i / tbperdb]; 457 for (j = i; j < count; j += tbperdb, bp++) 458 if (*bp != 0) 459 if (j + tbperdb <= count) 460 dumpblock(*bp, (int)sblock->fs_bsize); 461 else 462 dumpblock(*bp, (count - j) * TP_BSIZE); 463 spcl.c_type = TS_ADDR; 464 } 465 } 466 467 /* 468 * Dump a map to the tape. 469 */ 470 void 471 dumpmap(map, type, ino) 472 char *map; 473 int type; 474 ino_t ino; 475 { 476 register int i; 477 char *cp; 478 479 spcl.c_type = type; 480 spcl.c_count = howmany(mapsize * sizeof(char), TP_BSIZE); 481 writeheader(ino); 482 for (i = 0, cp = map; i < spcl.c_count; i++, cp += TP_BSIZE) 483 writerec(cp, 0); 484 } 485 486 /* 487 * Write a header record to the dump tape. 488 */ 489 void 490 writeheader(ino) 491 ino_t ino; 492 { 493 register long sum, cnt, *lp; 494 495 spcl.c_inumber = ino; 496 spcl.c_magic = NFS_MAGIC; 497 spcl.c_checksum = 0; 498 lp = (long *)&spcl; 499 sum = 0; 500 cnt = sizeof(union u_spcl) / (4 * sizeof(long)); 501 while (--cnt >= 0) { 502 sum += *lp++; 503 sum += *lp++; 504 sum += *lp++; 505 sum += *lp++; 506 } 507 spcl.c_checksum = CHECKSUM - sum; 508 writerec((char *)&spcl, 1); 509 } 510 511 struct dinode * 512 getino(inum) 513 ino_t inum; 514 { 515 static daddr_t minino, maxino; 516 static struct dinode inoblock[MAXINOPB]; 517 518 curino = inum; 519 if (inum >= minino && inum < maxino) 520 return (&inoblock[inum - minino]); 521 bread(fsbtodb(sblock, itod(sblock, inum)), (char *)inoblock, 522 (int)sblock->fs_bsize); 523 minino = inum - (inum % INOPB(sblock)); 524 maxino = minino + INOPB(sblock); 525 return (&inoblock[inum - minino]); 526 } 527 528 /* 529 * Read a chunk of data from the disk. 530 * Try to recover from hard errors by reading in sector sized pieces. 531 * Error recovery is attempted at most BREADEMAX times before seeking 532 * consent from the operator to continue. 533 */ 534 int breaderrors = 0; 535 #define BREADEMAX 32 536 537 void 538 bread(blkno, buf, size) 539 daddr_t blkno; 540 char *buf; 541 int size; 542 { 543 int cnt, i; 544 extern int errno; 545 546 loop: 547 if ((int)lseek(diskfd, ((off_t)blkno << dev_bshift), 0) < 0) 548 msg("bread: lseek fails\n"); 549 if ((cnt = read(diskfd, buf, size)) == size) 550 return; 551 if (blkno + (size / dev_bsize) > fsbtodb(sblock, sblock->fs_size)) { 552 /* 553 * Trying to read the final fragment. 554 * 555 * NB - dump only works in TP_BSIZE blocks, hence 556 * rounds `dev_bsize' fragments up to TP_BSIZE pieces. 557 * It should be smarter about not actually trying to 558 * read more than it can get, but for the time being 559 * we punt and scale back the read only when it gets 560 * us into trouble. (mkm 9/25/83) 561 */ 562 size -= dev_bsize; 563 goto loop; 564 } 565 if (cnt == -1) 566 msg("read error from %s: %s: [block %d]: count=%d\n", 567 disk, strerror(errno), blkno, size); 568 else 569 msg("short read error from %s: [block %d]: count=%d, got=%d\n", 570 disk, blkno, size, cnt); 571 if (++breaderrors > BREADEMAX) { 572 msg("More than %d block read errors from %d\n", 573 BREADEMAX, disk); 574 broadcast("DUMP IS AILING!\n"); 575 msg("This is an unrecoverable error.\n"); 576 if (!query("Do you want to attempt to continue?")){ 577 dumpabort(0); 578 /*NOTREACHED*/ 579 } else 580 breaderrors = 0; 581 } 582 /* 583 * Zero buffer, then try to read each sector of buffer separately. 584 */ 585 bzero(buf, size); 586 for (i = 0; i < size; i += dev_bsize, buf += dev_bsize, blkno++) { 587 if ((int)lseek(diskfd, ((off_t)blkno << dev_bshift), 0) < 0) 588 msg("bread: lseek2 fails!\n"); 589 if ((cnt = read(diskfd, buf, (int)dev_bsize)) == dev_bsize) 590 continue; 591 if (cnt == -1) { 592 msg("read error from %s: %s: [sector %d]: count=%d\n", 593 disk, strerror(errno), blkno, dev_bsize); 594 continue; 595 } 596 msg("short read error from %s: [sector %d]: count=%d, got=%d\n", 597 disk, blkno, dev_bsize, cnt); 598 } 599 } 600