1 /* 2 * Copyright 2003 Sun Microsystems, Inc. All rights reserved. 3 * Use is subject to license terms. 4 */ 5 6 /* Copyright (c) 1983, 1984, 1985, 1986, 1987, 1988, 1989 AT&T */ 7 /* All Rights Reserved */ 8 9 /* 10 * Copyright (c) 1980, 1986, 1990 The Regents of the University of California. 11 * All rights reserved. 12 * 13 * Redistribution and use in source and binary forms are permitted 14 * provided that: (1) source distributions retain this entire copyright 15 * notice and comment, and (2) distributions including binaries display 16 * the following acknowledgement: ``This product includes software 17 * developed by the University of California, Berkeley and its contributors'' 18 * in the documentation or other materials provided with the distribution 19 * and in all advertising materials mentioning features or use of this 20 * software. Neither the name of the University nor the names of its 21 * contributors may be used to endorse or promote products derived 22 * from this software without specific prior written permission. 23 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR 24 * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED 25 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. 26 */ 27 28 #pragma ident "%Z%%M% %I% %E% SMI" 29 30 #include <stdio.h> 31 #include <string.h> 32 #include <stdlib.h> 33 #include <unistd.h> 34 #include <time.h> 35 #include <sys/param.h> 36 #include <sys/types.h> 37 #include <sys/sysmacros.h> 38 #include <sys/mntent.h> 39 40 #include <sys/vnode.h> 41 #include <sys/fs/ufs_inode.h> 42 #include <sys/fs/ufs_fs.h> 43 #include <sys/fs/ufs_fsdir.h> 44 #include <pwd.h> 45 #include "fsck.h" 46 47 static ino_t startinum = 0; 48 49 extern uint_t largefile_count; 50 51 ckinode(dp, idesc) 52 struct dinode *dp; 53 struct inodesc *idesc; 54 { 55 daddr32_t *ap; 56 int64_t offset; 57 int n, ndb; 58 int ret; 59 struct dinode dino; 60 u_offset_t indir_data_blks; 61 62 idesc->id_entryno = 0; 63 idesc->id_filesize = (offset_t)dp->di_size; 64 if ((dp->di_mode & IFMT) == IFBLK || (dp->di_mode & IFMT) == IFCHR) 65 return (KEEPON); 66 dino = *dp; 67 ndb = howmany(dino.di_size, (u_offset_t)sblock.fs_bsize); 68 for (ap = &dino.di_db[0]; ap < &dino.di_db[NDADDR]; ap++) { 69 if (--ndb == 0 && 70 (offset = blkoff(&sblock, dino.di_size)) != 0) 71 idesc->id_numfrags = 72 numfrags(&sblock, fragroundup(&sblock, offset)); 73 else 74 idesc->id_numfrags = sblock.fs_frag; 75 if (*ap == 0) 76 continue; 77 idesc->id_blkno = *ap; 78 if (idesc->id_type == ADDR || idesc->id_type == ACL) 79 ret = (*idesc->id_func)(idesc); 80 else 81 ret = dirscan(idesc); 82 if (ret & STOP) 83 return (ret); 84 } 85 idesc->id_numfrags = sblock.fs_frag; 86 87 /* 88 * indir_data_blks determine the no. of data blocks 89 * in the previous levels. ie., at level 3 it 90 * is the number of data blocks at level 2, 1, and 0. 91 */ 92 93 for (ap = &dino.di_ib[0], n = 1; n <= NIADDR; ap++, n++) { 94 if (n == 1) { 95 /* SINGLE */ 96 indir_data_blks = NDADDR; 97 } else if (n == 2) { 98 /* DOUBLE */ 99 indir_data_blks = NDADDR + NINDIR(&sblock); 100 } else if (n == 3) { 101 /* TRIPLE */ 102 indir_data_blks = NDADDR + NINDIR(&sblock) + 103 (NINDIR(&sblock) * NINDIR(&sblock)); 104 } 105 if (*ap) { 106 idesc->id_blkno = *ap; 107 ret = iblock(idesc, n, 108 (u_offset_t)howmany(dino.di_size, 109 (u_offset_t)sblock.fs_bsize) - indir_data_blks); 110 if (ret & STOP) 111 return (ret); 112 } else { 113 idesc->id_hasholes = 1; 114 } 115 } 116 return (KEEPON); 117 } 118 119 iblock(idesc, ilevel, iblks) 120 struct inodesc *idesc; 121 int ilevel; 122 u_offset_t iblks; 123 { 124 daddr32_t *ap; 125 daddr32_t *aplim; 126 int i, n, (*func)(); 127 u_offset_t fsbperindirb; 128 offset_t nif; 129 struct bufarea *bp; 130 char buf[BUFSIZ]; 131 extern int dirscan(), pass1check(), pass3bcheck(); 132 133 if (idesc->id_type == ADDR) { 134 func = idesc->id_func; 135 if (((n = (*func)(idesc)) & KEEPON) == 0) 136 return (n); 137 } else if (idesc->id_type == ACL) { 138 func = idesc->id_func; 139 if (chkrange(idesc->id_blkno, idesc->id_numfrags)) 140 return (STOP); 141 } else { /* DATA, ie a directory */ 142 func = dirscan; 143 if (chkrange(idesc->id_blkno, idesc->id_numfrags)) 144 return (SKIP); 145 } 146 bp = getdatablk(idesc->id_blkno, sblock.fs_bsize); 147 ilevel--; 148 for (fsbperindirb = 1, i = 0; i < ilevel; i++) { 149 fsbperindirb *= (u_offset_t)NINDIR(&sblock); 150 } 151 /* 152 * nif indicates the next "free" pointer (as an array index) in this 153 * indirect block, based on counting the blocks remaining in the 154 * file after subtracting all previously processed blocks. 155 * This figure is based on the size field of the inode. 156 * 157 * Note that in normal operation, nif may initially calculated to 158 * be larger than the number of pointers in this block; if that is 159 * the case, nif is limited to the max number of pointers per 160 * indirect block. 161 * 162 * Also note that if an inode is inconsistant (has more blocks 163 * allocated to it than the size field would indicate), the sweep 164 * through any indirect blocks directly pointed at by the inode 165 * continues. Since the block offset of any data blocks referenced 166 * by these indirect blocks is greater than the size of the file, 167 * the index nif may be computed as a negative value. 168 * In this case, we reset nif to indicate that all pointers in 169 * this retrieval block should be zeroed and the resulting 170 * unreferenced data and/or retrieval blocks be recovered 171 * through garbage collection later. 172 */ 173 nif = (offset_t)howmany(iblks, fsbperindirb); 174 if (nif > NINDIR(&sblock)) 175 nif = NINDIR(&sblock); 176 else if (nif < 0) 177 nif = 0; 178 /* 179 * first pass: all "free" retrieval pointers (from [nif] thru 180 * the end of the indirect block) should be zero. (This 181 * assertion does not hold for directories, which may be 182 * truncated without releasing their allocated space) 183 */ 184 if ((idesc->id_func == pass1check || idesc->id_func == pass3bcheck) && 185 nif < NINDIR(&sblock)) { 186 aplim = &bp->b_un.b_indir[NINDIR(&sblock)]; 187 for (ap = &bp->b_un.b_indir[nif]; 188 ap < aplim; ap++) { 189 if (*ap == 0) 190 continue; 191 (void) sprintf(buf, "PARTIALLY TRUNCATED INODE I=%d", 192 idesc->id_number); 193 if (dofix(idesc, buf)) { 194 *ap = 0; 195 dirty(bp); 196 } 197 } 198 flush(fswritefd, bp); 199 } 200 /* 201 * second pass: all retrieval pointers refering to blocks within 202 * a valid range [0..filesize] (both indirect and data blocks) 203 * are respectively examined the same manner as the direct blocks 204 * in the inode are checked in chkinode(). Sweep through 205 * the first pointer in this retrieval block to [nif-1]. 206 */ 207 aplim = &bp->b_un.b_indir[nif]; 208 for (ap = bp->b_un.b_indir; ap < aplim; ap++) { 209 if (*ap) { 210 idesc->id_blkno = *ap; 211 if (ilevel > 0) { 212 n = iblock(idesc, ilevel, iblks); 213 /* 214 * each iteration decrease "remaining block 215 * count" by however many blocks were accessible 216 * by a pointer at this indirect block level. 217 */ 218 iblks -= fsbperindirb; 219 } else { 220 if (!idesc->id_hasholes) { 221 /* 222 * Increment logical block count here. 223 * In the case of direct blocks, it is 224 * done in pass1(). 225 */ 226 idesc->id_llbna++; 227 } 228 n = (*func)(idesc); 229 } 230 if (n & STOP) { 231 brelse(bp); 232 return (n); 233 } 234 } else { 235 idesc->id_hasholes = 1; 236 } 237 } 238 brelse(bp); 239 return (KEEPON); 240 } 241 242 /* 243 * Check that a block is a legal block number. 244 * Return 0 if in range, 1 if out of range. 245 */ 246 chkrange(blk, cnt) 247 daddr32_t blk; 248 int cnt; 249 { 250 int c; 251 252 if ((unsigned)(blk + cnt) > (unsigned)maxfsblock) 253 return (1); 254 c = dtog(&sblock, blk); 255 if (blk < cgdmin(&sblock, c)) { 256 if ((unsigned)(blk + cnt) > (unsigned)cgsblock(&sblock, c)) { 257 if (debug) { 258 printf("blk %d < cgdmin %d;", 259 blk, cgdmin(&sblock, c)); 260 printf(" blk + cnt %d > cgsbase %d\n", 261 blk + cnt, cgsblock(&sblock, c)); 262 } 263 return (1); 264 } 265 } else { 266 if ((unsigned)(blk + cnt) > (unsigned)cgbase(&sblock, c+1)) { 267 if (debug) { 268 printf("blk %d >= cgdmin %d;", 269 blk, cgdmin(&sblock, c)); 270 printf(" blk + cnt %d > sblock.fs_fpg %d\n", 271 blk+cnt, sblock.fs_fpg); 272 } 273 return (1); 274 } 275 } 276 return (0); 277 } 278 279 /* 280 * General purpose interface for reading inodes. 281 */ 282 struct dinode * 283 ginode(inumber) 284 ino_t inumber; 285 { 286 daddr32_t iblk; 287 struct dinode *dp; 288 289 if (inumber < UFSROOTINO || inumber > maxino) 290 errexit("bad inode number %d to ginode\n", inumber); 291 if (startinum == 0 || 292 inumber < startinum || 293 inumber >= (ino_t)(startinum + (ino_t)INOPB(&sblock))) { 294 iblk = itod(&sblock, inumber); 295 if (pbp != 0) { 296 brelse(pbp); 297 } 298 pbp = getdatablk(iblk, sblock.fs_bsize); 299 startinum = 300 (ino_t)((inumber / INOPB(&sblock)) * INOPB(&sblock)); 301 } 302 dp = &pbp->b_un.b_dinode[inumber % INOPB(&sblock)]; 303 dp->di_mode = dp->di_smode; 304 if (dp->di_suid != UID_LONG) dp->di_uid = dp->di_suid; 305 if (dp->di_sgid != GID_LONG) dp->di_gid = dp->di_sgid; 306 return (dp); 307 } 308 309 /* 310 * Special purpose version of ginode used to optimize first pass 311 * over all the inodes in numerical order. 312 */ 313 ino_t nextino, lastinum; 314 int64_t readcnt, readpercg, fullcnt, inobufsize, partialcnt, partialsize; 315 struct dinode *inodebuf; 316 317 struct dinode * 318 getnextinode(inumber) 319 ino_t inumber; 320 { 321 int64_t size; 322 diskaddr_t dblk; 323 static struct dinode *dp; 324 325 if (inumber != nextino++ || inumber > maxino) 326 errexit("bad inode number %d to nextinode\n", inumber); 327 if (inumber >= lastinum) { 328 readcnt++; 329 dblk = fsbtodb(&sblock, itod(&sblock, lastinum)); 330 if (readcnt % readpercg == 0) { 331 size = partialsize; 332 lastinum += partialcnt; 333 } else { 334 size = inobufsize; 335 lastinum += fullcnt; 336 } 337 bread(fsreadfd, (char *)inodebuf, dblk, (long)size); 338 dp = inodebuf; 339 } 340 return (dp++); 341 } 342 343 resetinodebuf() 344 { 345 346 startinum = 0; 347 nextino = 0; 348 lastinum = 0; 349 readcnt = 0; 350 inobufsize = blkroundup(&sblock, INOBUFSIZE); 351 fullcnt = inobufsize / sizeof (struct dinode); 352 readpercg = sblock.fs_ipg / fullcnt; 353 partialcnt = sblock.fs_ipg % fullcnt; 354 partialsize = partialcnt * sizeof (struct dinode); 355 if (partialcnt != 0) { 356 readpercg++; 357 } else { 358 partialcnt = fullcnt; 359 partialsize = inobufsize; 360 } 361 if (inodebuf == NULL && 362 (inodebuf = (struct dinode *)malloc((unsigned)inobufsize)) == NULL) 363 errexit("Cannot allocate space for inode buffer\n"); 364 while (nextino < UFSROOTINO) 365 (void) getnextinode(nextino); 366 } 367 368 freeinodebuf() 369 { 370 371 if (inodebuf != NULL) 372 free((char *)inodebuf); 373 inodebuf = NULL; 374 } 375 376 /* 377 * Routines to maintain information about directory inodes. 378 * This is built during the first pass and used during the 379 * second and third passes. 380 * 381 * Enter inodes into the cache. 382 */ 383 cacheino(dp, inumber) 384 struct dinode *dp; 385 ino_t inumber; 386 { 387 struct inoinfo *inp; 388 struct inoinfo **inpp; 389 uint_t blks; 390 391 blks = NDADDR + NIADDR; 392 inp = (struct inoinfo *) 393 malloc(sizeof (*inp) + (blks - 1) * sizeof (daddr32_t)); 394 if (inp == NULL) 395 return; 396 inpp = &inphead[inumber % numdirs]; 397 inp->i_nexthash = *inpp; 398 *inpp = inp; 399 inp->i_parent = (ino_t)0; 400 inp->i_dotdot = (ino_t)0; 401 inp->i_number = inumber; 402 inp->i_isize = (offset_t)dp->di_size; 403 inp->i_numblks = blks * sizeof (daddr32_t); 404 inp->i_extattr = dp->di_oeftflag; 405 memcpy(&inp->i_blks[0], &dp->di_db[0], inp->i_numblks); 406 if (inplast == listmax) { 407 listmax += 100; 408 inpsort = (struct inoinfo **)realloc((char *)inpsort, 409 (unsigned)listmax * sizeof (struct inoinfo *)); 410 if (inpsort == NULL) 411 errexit("cannot increase directory list"); 412 } 413 inpsort[inplast++] = inp; 414 } 415 416 /* 417 * Look up an inode cache structure. 418 */ 419 struct inoinfo * 420 getinoinfo(inumber) 421 ino_t inumber; 422 { 423 struct inoinfo *inp; 424 425 for (inp = inphead[inumber % numdirs]; inp; inp = inp->i_nexthash) { 426 if (inp->i_number != inumber) 427 continue; 428 return (inp); 429 } 430 errexit("cannot find inode %d\n", inumber); 431 return ((struct inoinfo *)0); 432 } 433 434 /* 435 * Determine whether inode is in cache. 436 */ 437 inocached(inumber) 438 ino_t inumber; 439 { 440 struct inoinfo *inp; 441 442 for (inp = inphead[inumber % numdirs]; inp; inp = inp->i_nexthash) { 443 if (inp->i_number != inumber) 444 continue; 445 return (1); 446 } 447 return (0); 448 } 449 450 /* 451 * Clean up all the inode cache structure. 452 */ 453 inocleanup() 454 { 455 struct inoinfo **inpp; 456 457 if (inphead == NULL) 458 return; 459 for (inpp = &inpsort[inplast - 1]; inpp >= inpsort; inpp--) 460 free((char *)(*inpp)); 461 free((char *)inphead); 462 free((char *)inpsort); 463 inphead = inpsort = NULL; 464 } 465 466 /* 467 * Routines to maintain information about acl inodes. 468 * This is built during the first pass and used during the 469 * second and third passes. 470 * 471 * Enter acl inodes into the cache. 472 */ 473 cacheacl(dp, inumber) 474 struct dinode *dp; 475 ino_t inumber; 476 { 477 struct aclinfo *aclp; 478 struct aclinfo **aclpp; 479 uint_t blks; 480 481 blks = NDADDR + NIADDR; 482 aclp = (struct aclinfo *) 483 malloc(sizeof (*aclp) + (blks - 1) * sizeof (daddr32_t)); 484 if (aclp == NULL) 485 return; 486 aclpp = &aclphead[inumber % numacls]; 487 aclp->i_nexthash = *aclpp; 488 *aclpp = aclp; 489 aclp->i_number = inumber; 490 aclp->i_isize = (offset_t)dp->di_size; 491 aclp->i_numblks = blks * sizeof (daddr32_t); 492 memcpy(&aclp->i_blks[0], &dp->di_db[0], aclp->i_numblks); 493 if (aclplast == aclmax) { 494 aclmax += 100; 495 aclpsort = (struct aclinfo **)realloc((char *)aclpsort, 496 (unsigned)aclmax * sizeof (struct aclinfo *)); 497 if (aclpsort == NULL) 498 errexit("cannot increase acl list"); 499 } 500 aclpsort[aclplast++] = aclp; 501 } 502 503 /* 504 * Look up an acl inode cache structure. 505 */ 506 struct aclinfo * 507 getaclinfo(inum) 508 ino_t inum; 509 { 510 struct aclinfo *aclp; 511 512 for (aclp = aclphead[inum % numacls]; aclp; aclp = aclp->i_nexthash) { 513 if (aclp->i_number != inum) 514 continue; 515 return (aclp); 516 } 517 errexit("cannot find acl inode %d\n", inum); 518 return ((struct aclinfo *)0); 519 } 520 521 /* 522 * Determine whether acl inode is in cache. 523 */ 524 aclcached(inum) 525 ino_t inum; 526 { 527 struct aclinfo *aclp; 528 529 for (aclp = aclphead[inum % numacls]; aclp; aclp = aclp->i_nexthash) { 530 if (aclp->i_number != inum) 531 continue; 532 return (1); 533 } 534 return (0); 535 } 536 537 inodirty() 538 { 539 540 dirty(pbp); 541 } 542 543 clri(idesc, type, flag) 544 struct inodesc *idesc; 545 char *type; 546 int flag; 547 { 548 struct dinode *dp; 549 550 dp = ginode(idesc->id_number); 551 if (flag == 1) { 552 pwarn("%s %s", type, 553 (dp->di_mode & IFMT) == IFDIR ? "DIRECTORY" : "FILE"); 554 pinode(idesc->id_number); 555 } 556 if (preen || reply("CLEAR") == 1) { 557 if (preen) 558 printf(" (CLEARED)\n"); 559 n_files--; 560 if (dp->di_size > (u_offset_t)MAXOFF_T) { 561 largefile_count--; 562 if (debug) 563 printf("clearing file: size %d,count %d\n", 564 dp->di_size, largefile_count); 565 } 566 (void) ckinode(dp, idesc); 567 clearinode(dp); 568 statemap[idesc->id_number] = USTATE; 569 inodirty(); 570 } 571 } 572 573 findname(idesc) 574 struct inodesc *idesc; 575 { 576 struct direct *dirp = idesc->id_dirp; 577 578 if (dirp->d_ino != idesc->id_parent) 579 return (KEEPON); 580 memcpy(idesc->id_name, dirp->d_name, 581 MIN(dirp->d_namlen, MAXNAMLEN) + 1); 582 return (STOP|FOUND); 583 } 584 585 findino(idesc) 586 struct inodesc *idesc; 587 { 588 struct direct *dirp = idesc->id_dirp; 589 590 if (dirp->d_ino == 0) 591 return (KEEPON); 592 if (strcmp(dirp->d_name, idesc->id_name) == 0 && 593 dirp->d_ino >= UFSROOTINO && dirp->d_ino <= maxino) { 594 idesc->id_parent = dirp->d_ino; 595 return (STOP|FOUND); 596 } 597 return (KEEPON); 598 } 599 600 pinode(ino) 601 ino_t ino; 602 { 603 struct dinode *dp; 604 char *p; 605 struct passwd *pw; 606 time_t t; 607 608 printf(" I=%u ", ino); 609 if (ino < UFSROOTINO || ino > maxino) 610 return; 611 dp = ginode(ino); 612 printf(" OWNER="); 613 if ((pw = getpwuid((int)dp->di_uid)) != 0) 614 printf("%s ", pw->pw_name); 615 else 616 printf("%d ", dp->di_uid); 617 printf("MODE=%o\n", dp->di_mode); 618 if (preen) 619 printf("%s: ", devname); 620 printf("SIZE=%lld ", dp->di_size); 621 t = (time_t)dp->di_mtime; 622 p = ctime(&t); 623 printf("MTIME=%12.12s %4.4s ", p + 4, p + 20); 624 } 625 626 blkerror(ino, type, blk) 627 ino_t ino; 628 char *type; 629 daddr32_t blk; 630 { 631 632 pfatal("%ld %s I=%u", blk, type, ino); 633 printf("\n"); 634 switch (statemap[ino]) { 635 636 case FSTATE: 637 statemap[ino] = FCLEAR; 638 return; 639 640 case DSTATE: 641 statemap[ino] = DCLEAR; 642 return; 643 644 case SSTATE: 645 statemap[ino] = SCLEAR; 646 return; 647 648 case FCLEAR: 649 case DCLEAR: 650 case SCLEAR: 651 return; 652 653 default: 654 errexit("BAD STATE %d TO BLKERR\n", statemap[ino]); 655 /* NOTREACHED */ 656 } 657 } 658 659 /* 660 * allocate an unused inode 661 */ 662 ino_t 663 allocino(request, type) 664 ino_t request; 665 int type; 666 { 667 ino_t ino; 668 struct dinode *dp; 669 time_t t; 670 671 if (request == 0) 672 request = UFSROOTINO; 673 else if (statemap[request] != USTATE) 674 return (0); 675 for (ino = request; ino < maxino; ino++) 676 if (statemap[ino] == USTATE) 677 break; 678 if (ino == maxino) 679 return (0); 680 switch (type & IFMT) { 681 case IFDIR: 682 statemap[ino] = DSTATE; 683 break; 684 case IFREG: 685 case IFLNK: 686 statemap[ino] = FSTATE; 687 break; 688 default: 689 return (0); 690 } 691 dp = ginode(ino); 692 dp->di_db[0] = allocblk(1); 693 if (dp->di_db[0] == 0) { 694 statemap[ino] = USTATE; 695 return (0); 696 } 697 dp->di_smode = dp->di_mode = type; 698 time(&t); 699 dp->di_atime = (time32_t)t; 700 dp->di_mtime = dp->di_ctime = dp->di_atime; 701 dp->di_size = (u_offset_t)sblock.fs_fsize; 702 dp->di_blocks = btodb(sblock.fs_fsize); 703 n_files++; 704 inodirty(); 705 return (ino); 706 } 707 708 /* 709 * deallocate an inode 710 */ 711 freeino(ino) 712 ino_t ino; 713 { 714 struct inodesc idesc; 715 extern int pass4check(); 716 struct dinode *dp; 717 718 memset(&idesc, 0, sizeof (struct inodesc)); 719 idesc.id_type = ADDR; 720 idesc.id_func = pass4check; 721 idesc.id_number = ino; 722 idesc.id_fix = DONTKNOW; 723 dp = ginode(ino); 724 (void) ckinode(dp, &idesc); 725 clearinode(dp); 726 inodirty(); 727 statemap[ino] = USTATE; 728 n_files--; 729 } 730