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.8 (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)); 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 if (ret & HASDUMPEDFILE) 196 *filesize = 0; 197 else 198 *filesize -= sblock->fs_bsize; 199 } 200 return (ret); 201 } 202 level--; 203 for (i = 0; *filesize > 0 && i < NINDIR(sblock); i++) { 204 blkno = idblk[i]; 205 if (blkno != 0) 206 ret |= dirindir(ino, blkno, level, filesize); 207 } 208 return (ret); 209 } 210 211 /* 212 * Scan a disk block containing directory information looking to see if 213 * any of the entries are on the dump list and to see if the directory 214 * contains any subdirectories. 215 */ 216 searchdir(ino, blkno, size) 217 ino_t ino; 218 daddr_t blkno; 219 register int size; 220 { 221 register struct direct *dp; 222 register long loc; 223 char dblk[MAXBSIZE]; 224 225 bread(fsbtodb(sblock, blkno), dblk, size); 226 for (loc = 0; loc < size; ) { 227 dp = (struct direct *)(dblk + loc); 228 if (dp->d_reclen == 0) { 229 msg("corrupted directory, inumber %d\n", ino); 230 break; 231 } 232 loc += dp->d_reclen; 233 if (dp->d_ino == 0) 234 continue; 235 if (dp->d_name[0] == '.') { 236 if (dp->d_name[1] == '\0') 237 continue; 238 if (dp->d_name[1] == '.' && dp->d_name[2] == '\0') 239 continue; 240 } 241 if (TSTINO(dp->d_ino, dumpinomap)) 242 return (HASDUMPEDFILE); 243 if (TSTINO(dp->d_ino, dumpdirmap)) 244 return (HASSUBDIRS); 245 } 246 return (0); 247 } 248 249 /* 250 * Dump passes 3 and 4. 251 * 252 * Dump the contents of an inode to tape. 253 */ 254 void 255 dumpino(ip, ino) 256 struct dinode *ip; 257 ino_t ino; 258 { 259 int mode, level, cnt; 260 long size; 261 262 if (newtape) { 263 newtape = 0; 264 dumpmap(dumpinomap, TS_BITS, ino); 265 } 266 CLRINO(ino, dumpinomap); 267 spcl.c_dinode = *ip; 268 spcl.c_type = TS_INODE; 269 spcl.c_count = 0; 270 /* 271 * Check for freed inode. 272 */ 273 if ((mode = (ip->di_mode & IFMT)) == 0) 274 return; 275 if ((mode != IFDIR && mode != IFREG && mode != IFLNK) || 276 ip->di_size == 0) { 277 writeheader(ino); 278 return; 279 } 280 if (ip->di_size > NDADDR * sblock->fs_bsize) 281 cnt = NDADDR * sblock->fs_frag; 282 else 283 cnt = howmany(ip->di_size, sblock->fs_fsize); 284 blksout(&ip->di_db[0], cnt, ino); 285 if ((size = ip->di_size - NDADDR * sblock->fs_bsize) <= 0) 286 return; 287 for (level = 0; level < NIADDR; level++) { 288 dmpindir(ino, ip->di_ib[level], level, &size); 289 if (size <= 0) 290 return; 291 } 292 } 293 294 /* 295 * Read indirect blocks, and pass the data blocks to be dumped. 296 */ 297 void 298 dmpindir(ino, blk, level, size) 299 ino_t ino; 300 daddr_t blk; 301 int level; 302 long *size; 303 { 304 int i, cnt; 305 daddr_t idblk[MAXNINDIR]; 306 307 if (blk != 0) 308 bread(fsbtodb(sblock, blk), (char *)idblk, sblock->fs_bsize); 309 else 310 bzero((char *)idblk, sblock->fs_bsize); 311 if (level <= 0) { 312 if (*size < NINDIR(sblock) * sblock->fs_bsize) 313 cnt = howmany(*size, sblock->fs_fsize); 314 else 315 cnt = NINDIR(sblock) * sblock->fs_frag; 316 *size -= NINDIR(sblock) * sblock->fs_bsize; 317 blksout(&idblk[0], cnt, ino); 318 return; 319 } 320 level--; 321 for (i = 0; i < NINDIR(sblock); i++) { 322 dmpindir(ino, idblk[i], level, size); 323 if (*size <= 0) 324 return; 325 } 326 } 327 328 /* 329 * Collect up the data into tape record sized buffers and output them. 330 */ 331 void 332 blksout(blkp, frags, ino) 333 daddr_t *blkp; 334 int frags; 335 ino_t ino; 336 { 337 register daddr_t *bp; 338 int i, j, count, blks, tbperdb; 339 340 blks = howmany(frags * sblock->fs_fsize, TP_BSIZE); 341 tbperdb = sblock->fs_bsize >> tp_bshift; 342 for (i = 0; i < blks; i += TP_NINDIR) { 343 if (i + TP_NINDIR > blks) 344 count = blks; 345 else 346 count = i + TP_NINDIR; 347 for (j = i; j < count; j++) 348 if (blkp[j / tbperdb] != 0) 349 spcl.c_addr[j - i] = 1; 350 else 351 spcl.c_addr[j - i] = 0; 352 spcl.c_count = count - i; 353 writeheader(ino); 354 bp = &blkp[i / tbperdb]; 355 for (j = i; j < count; j += tbperdb, bp++) 356 if (*bp != 0) 357 if (j + tbperdb <= count) 358 dumpblock(*bp, sblock->fs_bsize); 359 else 360 dumpblock(*bp, (count - j) * TP_BSIZE); 361 spcl.c_type = TS_ADDR; 362 } 363 } 364 365 /* 366 * Dump a map to the tape. 367 */ 368 void 369 dumpmap(map, type, ino) 370 char *map; 371 int type; 372 ino_t ino; 373 { 374 register int i; 375 char *cp; 376 377 spcl.c_type = type; 378 spcl.c_count = howmany(mapsize * sizeof(char), TP_BSIZE); 379 writeheader(ino); 380 for (i = 0, cp = map; i < spcl.c_count; i++, cp += TP_BSIZE) 381 writerec(cp); 382 } 383 384 /* 385 * Write a header record to the dump tape. 386 */ 387 void 388 writeheader(ino) 389 ino_t ino; 390 { 391 register long sum, cnt, *lp; 392 393 spcl.c_inumber = ino; 394 spcl.c_magic = NFS_MAGIC; 395 spcl.c_checksum = 0; 396 lp = (long *)&spcl; 397 sum = 0; 398 cnt = sizeof(union u_spcl) / (4 * sizeof(long)); 399 while (--cnt >= 0) { 400 sum += *lp++; 401 sum += *lp++; 402 sum += *lp++; 403 sum += *lp++; 404 } 405 spcl.c_checksum = CHECKSUM - sum; 406 writerec((char *)&spcl); 407 } 408 409 struct dinode * 410 getino(inum) 411 ino_t inum; 412 { 413 static daddr_t minino, maxino; 414 static struct dinode inoblock[MAXINOPB]; 415 416 curino = inum; 417 if (inum >= minino && inum < maxino) 418 return (&inoblock[inum - minino]); 419 bread(fsbtodb(sblock, itod(sblock, inum)), inoblock, sblock->fs_bsize); 420 minino = inum - (inum % INOPB(sblock)); 421 maxino = minino + INOPB(sblock); 422 return (&inoblock[inum - minino]); 423 } 424 425 /* 426 * Read a chunk of data from the disk. 427 * Try to recover from hard errors by reading in sector sized pieces. 428 * Error recovery is attempted at most BREADEMAX times before seeking 429 * consent from the operator to continue. 430 */ 431 int breaderrors = 0; 432 #define BREADEMAX 32 433 434 void 435 bread(blkno, buf, size) 436 daddr_t blkno; 437 char *buf; 438 int size; 439 { 440 int cnt, i; 441 extern int errno; 442 443 loop: 444 if (lseek(diskfd, (long)(blkno << dev_bshift), 0) < 0) 445 msg("bread: lseek fails\n"); 446 if ((cnt = read(diskfd, buf, size)) == size) 447 return; 448 if (blkno + (size / dev_bsize) > fsbtodb(sblock, sblock->fs_size)) { 449 /* 450 * Trying to read the final fragment. 451 * 452 * NB - dump only works in TP_BSIZE blocks, hence 453 * rounds `dev_bsize' fragments up to TP_BSIZE pieces. 454 * It should be smarter about not actually trying to 455 * read more than it can get, but for the time being 456 * we punt and scale back the read only when it gets 457 * us into trouble. (mkm 9/25/83) 458 */ 459 size -= dev_bsize; 460 goto loop; 461 } 462 msg("read error from %s [block %d]: count=%d, got=%d, errno=%d (%s)\n", 463 disk, blkno, size, cnt, errno, strerror(errno)); 464 if (++breaderrors > BREADEMAX) { 465 msg("More than %d block read errors from %d\n", 466 BREADEMAX, disk); 467 broadcast("DUMP IS AILING!\n"); 468 msg("This is an unrecoverable error.\n"); 469 if (!query("Do you want to attempt to continue?")){ 470 dumpabort(); 471 /*NOTREACHED*/ 472 } else 473 breaderrors = 0; 474 } 475 /* 476 * Zero buffer, then try to read each sector of buffer separately. 477 */ 478 bzero(buf, size); 479 for (i = 0; i < size; i += dev_bsize, buf += dev_bsize, blkno++) { 480 if (lseek(diskfd, (long)(blkno << dev_bshift), 0) < 0) 481 msg("bread: lseek2 fails!\n"); 482 if ((cnt = read(diskfd, buf, dev_bsize)) != dev_bsize) 483 msg(" read error from %s [sector %d, errno %d]\n", 484 disk, blkno, errno); 485 } 486 } 487