1 /* 2 * Copyright (c) 1980, 1988 Regents of the University of California. 3 * All rights reserved. The Berkeley software License Agreement 4 * specifies the terms and conditions for redistribution. 5 */ 6 7 #ifndef lint 8 static char sccsid[] = "@(#)traverse.c 5.9 (Berkeley) 02/28/91"; 9 #endif /* not lint */ 10 11 #include <sys/param.h> 12 #include <ufs/dir.h> 13 #include <ufs/dinode.h> 14 #include <ufs/fs.h> 15 #include <protocols/dumprestore.h> 16 #ifdef __STDC__ 17 #include <unistd.h> 18 #include <string.h> 19 #endif 20 #include "dump.h" 21 22 void dmpindir(); 23 #define HASDUMPEDFILE 0x1 24 #define HASSUBDIRS 0x2 25 26 /* 27 * This is an estimation of the number of TP_BSIZE blocks in the file. 28 * It estimates the number of blocks in files with holes by assuming 29 * that all of the blocks accounted for by di_blocks are data blocks 30 * (when some of the blocks are usually used for indirect pointers); 31 * hence the estimate may be high. 32 */ 33 long 34 blockest(ip) 35 struct dinode *ip; 36 { 37 long blkest, sizeest; 38 39 /* 40 * ip->di_size is the size of the file in bytes. 41 * ip->di_blocks stores the number of sectors actually in the file. 42 * If there are more sectors than the size would indicate, this just 43 * means that there are indirect blocks in the file or unused 44 * sectors in the last file block; we can safely ignore these 45 * (blkest = sizeest below). 46 * If the file is bigger than the number of sectors would indicate, 47 * then the file has holes in it. In this case we must use the 48 * block count to estimate the number of data blocks used, but 49 * we use the actual size for estimating the number of indirect 50 * dump blocks (sizeest vs. blkest in the indirect block 51 * calculation). 52 */ 53 blkest = howmany(dbtob(ip->di_blocks), TP_BSIZE); 54 sizeest = howmany(ip->di_size, TP_BSIZE); 55 if (blkest > sizeest) 56 blkest = sizeest; 57 if (ip->di_size > sblock->fs_bsize * NDADDR) { 58 /* calculate the number of indirect blocks on the dump tape */ 59 blkest += 60 howmany(sizeest - NDADDR * sblock->fs_bsize / TP_BSIZE, 61 TP_NINDIR); 62 } 63 return (blkest + 1); 64 } 65 66 /* 67 * Dump pass 1. 68 * 69 * Walk the inode list for a filesystem to find all allocated inodes 70 * that have been modified since the previous dump time. Also, find all 71 * the directories in the filesystem. 72 */ 73 mapfiles(maxino, tapesize) 74 ino_t maxino; 75 long *tapesize; 76 { 77 register int mode; 78 register ino_t ino; 79 register struct dinode *dp; 80 int anydirskipped = 0; 81 82 for (ino = 0; ino < maxino; ino++) { 83 dp = getino(ino); 84 if ((mode = (dp->di_mode & IFMT)) == 0) 85 continue; 86 SETINO(ino, usedinomap); 87 if (mode == IFDIR) 88 SETINO(ino, dumpdirmap); 89 if (dp->di_mtime >= spcl.c_ddate || 90 dp->di_ctime >= spcl.c_ddate) { 91 SETINO(ino, dumpinomap); 92 if (mode != IFREG && mode != IFDIR && mode != IFLNK) { 93 *tapesize += 1; 94 continue; 95 } 96 *tapesize += blockest(dp); 97 continue; 98 } 99 if (mode == IFDIR) 100 anydirskipped = 1; 101 } 102 /* 103 * Restore gets very upset if the root is not dumped, 104 * so ensure that it always is dumped. 105 */ 106 SETINO(ROOTINO, usedinomap); 107 return (anydirskipped); 108 } 109 110 /* 111 * Dump pass 2. 112 * 113 * Scan each directory on the filesystem to see if it has any modified 114 * files in it. If it does, and has not already been added to the dump 115 * list (because it was itself modified), then add it. If a directory 116 * has not been modified itself, contains no modified files and has no 117 * subdirectories, then it can be deleted from the dump list and from 118 * the list of directories. By deleting it from the list of directories, 119 * its parent may now qualify for the same treatment on this or a later 120 * pass using this algorithm. 121 */ 122 mapdirs(maxino, tapesize) 123 ino_t maxino; 124 long *tapesize; 125 { 126 register struct dinode *dp; 127 register int i, bits; 128 register char *map; 129 register ino_t ino; 130 long filesize, blkcnt = 0; 131 int ret, change = 0; 132 133 for (map = dumpdirmap, ino = 0; ino < maxino; ) { 134 if ((ino % NBBY) == 0) 135 bits = *map++; 136 else 137 bits >>= 1; 138 ino++; 139 if ((bits & 1) == 0 || TSTINO(ino, dumpinomap)) 140 continue; 141 dp = getino(ino); 142 filesize = dp->di_size; 143 for (ret = 0, i = 0; filesize > 0 && i < NDADDR; i++) { 144 if (dp->di_db[i] != 0) 145 ret |= searchdir(ino, dp->di_db[i], 146 dblksize(sblock, dp, i), filesize); 147 if (ret & HASDUMPEDFILE) 148 filesize = 0; 149 else 150 filesize -= sblock->fs_bsize; 151 } 152 for (i = 0; filesize > 0 && i < NIADDR; i++) { 153 if (dp->di_ib[i] == 0) 154 continue; 155 ret |= dirindir(ino, dp->di_ib[i], i, &filesize); 156 } 157 if (ret & HASDUMPEDFILE) { 158 if (!TSTINO(ino, dumpinomap)) { 159 SETINO(ino, dumpinomap); 160 *tapesize += blockest(dp); 161 } 162 change = 1; 163 continue; 164 } 165 if ((ret & HASSUBDIRS) == 0) { 166 if (!TSTINO(ino, dumpinomap)) { 167 CLRINO(ino, dumpdirmap); 168 change = 1; 169 } 170 } 171 } 172 return (change); 173 } 174 175 /* 176 * Read indirect blocks, and pass the data blocks to be searched 177 * as directories. Quit as soon as any entry is found that will 178 * require the directory to be dumped. 179 */ 180 dirindir(ino, blkno, level, filesize) 181 ino_t ino; 182 daddr_t blkno; 183 int level, *filesize; 184 { 185 int ret = 0; 186 register int i; 187 daddr_t idblk[MAXNINDIR]; 188 189 bread(fsbtodb(sblock, blkno), (char *)idblk, sblock->fs_bsize); 190 if (level <= 0) { 191 for (i = 0; *filesize > 0 && i < NINDIR(sblock); i++) { 192 blkno = idblk[i]; 193 if (blkno != 0) 194 ret |= searchdir(ino, blkno, sblock->fs_bsize, 195 filesize); 196 if (ret & HASDUMPEDFILE) 197 *filesize = 0; 198 else 199 *filesize -= sblock->fs_bsize; 200 } 201 return (ret); 202 } 203 level--; 204 for (i = 0; *filesize > 0 && i < NINDIR(sblock); i++) { 205 blkno = idblk[i]; 206 if (blkno != 0) 207 ret |= dirindir(ino, blkno, level, filesize); 208 } 209 return (ret); 210 } 211 212 /* 213 * Scan a disk block containing directory information looking to see if 214 * any of the entries are on the dump list and to see if the directory 215 * contains any subdirectories. 216 */ 217 searchdir(ino, blkno, size, filesize) 218 ino_t ino; 219 daddr_t blkno; 220 register int size; 221 int filesize; 222 { 223 register struct direct *dp; 224 register long loc; 225 char dblk[MAXBSIZE]; 226 227 bread(fsbtodb(sblock, blkno), dblk, size); 228 if (filesize < size) 229 size = filesize; 230 for (loc = 0; loc < size; ) { 231 dp = (struct direct *)(dblk + loc); 232 if (dp->d_reclen == 0) { 233 msg("corrupted directory, inumber %d\n", ino); 234 break; 235 } 236 loc += dp->d_reclen; 237 if (dp->d_ino == 0) 238 continue; 239 if (dp->d_name[0] == '.') { 240 if (dp->d_name[1] == '\0') 241 continue; 242 if (dp->d_name[1] == '.' && dp->d_name[2] == '\0') 243 continue; 244 } 245 if (TSTINO(dp->d_ino, dumpinomap)) 246 return (HASDUMPEDFILE); 247 if (TSTINO(dp->d_ino, dumpdirmap)) 248 return (HASSUBDIRS); 249 } 250 return (0); 251 } 252 253 /* 254 * Dump passes 3 and 4. 255 * 256 * Dump the contents of an inode to tape. 257 */ 258 void 259 dumpino(ip, ino) 260 struct dinode *ip; 261 ino_t ino; 262 { 263 int mode, level, cnt; 264 long size; 265 266 if (newtape) { 267 newtape = 0; 268 dumpmap(dumpinomap, TS_BITS, ino); 269 } 270 CLRINO(ino, dumpinomap); 271 spcl.c_dinode = *ip; 272 spcl.c_type = TS_INODE; 273 spcl.c_count = 0; 274 /* 275 * Check for freed inode. 276 */ 277 if ((mode = (ip->di_mode & IFMT)) == 0) 278 return; 279 if ((mode != IFDIR && mode != IFREG && mode != IFLNK) || 280 ip->di_size == 0) { 281 writeheader(ino); 282 return; 283 } 284 if (ip->di_size > NDADDR * sblock->fs_bsize) 285 cnt = NDADDR * sblock->fs_frag; 286 else 287 cnt = howmany(ip->di_size, sblock->fs_fsize); 288 blksout(&ip->di_db[0], cnt, ino); 289 if ((size = ip->di_size - NDADDR * sblock->fs_bsize) <= 0) 290 return; 291 for (level = 0; level < NIADDR; level++) { 292 dmpindir(ino, ip->di_ib[level], level, &size); 293 if (size <= 0) 294 return; 295 } 296 } 297 298 /* 299 * Read indirect blocks, and pass the data blocks to be dumped. 300 */ 301 void 302 dmpindir(ino, blk, level, size) 303 ino_t ino; 304 daddr_t blk; 305 int level; 306 long *size; 307 { 308 int i, cnt; 309 daddr_t idblk[MAXNINDIR]; 310 311 if (blk != 0) 312 bread(fsbtodb(sblock, blk), (char *)idblk, sblock->fs_bsize); 313 else 314 bzero((char *)idblk, sblock->fs_bsize); 315 if (level <= 0) { 316 if (*size < NINDIR(sblock) * sblock->fs_bsize) 317 cnt = howmany(*size, sblock->fs_fsize); 318 else 319 cnt = NINDIR(sblock) * sblock->fs_frag; 320 *size -= NINDIR(sblock) * sblock->fs_bsize; 321 blksout(&idblk[0], cnt, ino); 322 return; 323 } 324 level--; 325 for (i = 0; i < NINDIR(sblock); i++) { 326 dmpindir(ino, idblk[i], level, size); 327 if (*size <= 0) 328 return; 329 } 330 } 331 332 /* 333 * Collect up the data into tape record sized buffers and output them. 334 */ 335 void 336 blksout(blkp, frags, ino) 337 daddr_t *blkp; 338 int frags; 339 ino_t ino; 340 { 341 register daddr_t *bp; 342 int i, j, count, blks, tbperdb; 343 344 blks = howmany(frags * sblock->fs_fsize, TP_BSIZE); 345 tbperdb = sblock->fs_bsize >> tp_bshift; 346 for (i = 0; i < blks; i += TP_NINDIR) { 347 if (i + TP_NINDIR > blks) 348 count = blks; 349 else 350 count = i + TP_NINDIR; 351 for (j = i; j < count; j++) 352 if (blkp[j / tbperdb] != 0) 353 spcl.c_addr[j - i] = 1; 354 else 355 spcl.c_addr[j - i] = 0; 356 spcl.c_count = count - i; 357 writeheader(ino); 358 bp = &blkp[i / tbperdb]; 359 for (j = i; j < count; j += tbperdb, bp++) 360 if (*bp != 0) 361 if (j + tbperdb <= count) 362 dumpblock(*bp, sblock->fs_bsize); 363 else 364 dumpblock(*bp, (count - j) * TP_BSIZE); 365 spcl.c_type = TS_ADDR; 366 } 367 } 368 369 /* 370 * Dump a map to the tape. 371 */ 372 void 373 dumpmap(map, type, ino) 374 char *map; 375 int type; 376 ino_t ino; 377 { 378 register int i; 379 char *cp; 380 381 spcl.c_type = type; 382 spcl.c_count = howmany(mapsize * sizeof(char), TP_BSIZE); 383 writeheader(ino); 384 for (i = 0, cp = map; i < spcl.c_count; i++, cp += TP_BSIZE) 385 writerec(cp); 386 } 387 388 /* 389 * Write a header record to the dump tape. 390 */ 391 void 392 writeheader(ino) 393 ino_t ino; 394 { 395 register long sum, cnt, *lp; 396 397 spcl.c_inumber = ino; 398 spcl.c_magic = NFS_MAGIC; 399 spcl.c_checksum = 0; 400 lp = (long *)&spcl; 401 sum = 0; 402 cnt = sizeof(union u_spcl) / (4 * sizeof(long)); 403 while (--cnt >= 0) { 404 sum += *lp++; 405 sum += *lp++; 406 sum += *lp++; 407 sum += *lp++; 408 } 409 spcl.c_checksum = CHECKSUM - sum; 410 writerec((char *)&spcl); 411 } 412 413 struct dinode * 414 getino(inum) 415 ino_t inum; 416 { 417 static daddr_t minino, maxino; 418 static struct dinode inoblock[MAXINOPB]; 419 420 curino = inum; 421 if (inum >= minino && inum < maxino) 422 return (&inoblock[inum - minino]); 423 bread(fsbtodb(sblock, itod(sblock, inum)), inoblock, sblock->fs_bsize); 424 minino = inum - (inum % INOPB(sblock)); 425 maxino = minino + INOPB(sblock); 426 return (&inoblock[inum - minino]); 427 } 428 429 /* 430 * Read a chunk of data from the disk. 431 * Try to recover from hard errors by reading in sector sized pieces. 432 * Error recovery is attempted at most BREADEMAX times before seeking 433 * consent from the operator to continue. 434 */ 435 int breaderrors = 0; 436 #define BREADEMAX 32 437 438 void 439 bread(blkno, buf, size) 440 daddr_t blkno; 441 char *buf; 442 int size; 443 { 444 int cnt, i; 445 extern int errno; 446 447 loop: 448 if (lseek(diskfd, (long)(blkno << dev_bshift), 0) < 0) 449 msg("bread: lseek fails\n"); 450 if ((cnt = read(diskfd, buf, size)) == size) 451 return; 452 if (blkno + (size / dev_bsize) > fsbtodb(sblock, sblock->fs_size)) { 453 /* 454 * Trying to read the final fragment. 455 * 456 * NB - dump only works in TP_BSIZE blocks, hence 457 * rounds `dev_bsize' fragments up to TP_BSIZE pieces. 458 * It should be smarter about not actually trying to 459 * read more than it can get, but for the time being 460 * we punt and scale back the read only when it gets 461 * us into trouble. (mkm 9/25/83) 462 */ 463 size -= dev_bsize; 464 goto loop; 465 } 466 msg("read error from %s [block %d]: count=%d, got=%d, errno=%d (%s)\n", 467 disk, blkno, size, cnt, errno, strerror(errno)); 468 if (++breaderrors > BREADEMAX) { 469 msg("More than %d block read errors from %d\n", 470 BREADEMAX, disk); 471 broadcast("DUMP IS AILING!\n"); 472 msg("This is an unrecoverable error.\n"); 473 if (!query("Do you want to attempt to continue?")){ 474 dumpabort(); 475 /*NOTREACHED*/ 476 } else 477 breaderrors = 0; 478 } 479 /* 480 * Zero buffer, then try to read each sector of buffer separately. 481 */ 482 bzero(buf, size); 483 for (i = 0; i < size; i += dev_bsize, buf += dev_bsize, blkno++) { 484 if (lseek(diskfd, (long)(blkno << dev_bshift), 0) < 0) 485 msg("bread: lseek2 fails!\n"); 486 if ((cnt = read(diskfd, buf, dev_bsize)) != dev_bsize) 487 msg(" read error from %s [sector %d, errno %d]\n", 488 disk, blkno, errno); 489 } 490 } 491