1 /* 2 * Copyright (c) 1980, 1986, 1993 3 * The Regents of the University of California. 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 #if 0 36 static const char sccsid[] = "@(#)inode.c 8.8 (Berkeley) 4/28/95"; 37 #endif 38 static const char rcsid[] = 39 "$FreeBSD: src/sbin/fsck/inode.c,v 1.20 2000/02/28 20:02:41 mckusick Exp $"; 40 #endif /* not lint */ 41 42 #include <sys/param.h> 43 #include <sys/time.h> 44 45 #include <ufs/ufs/dinode.h> 46 #include <ufs/ufs/dir.h> 47 #include <ufs/ffs/fs.h> 48 49 #include <err.h> 50 #include <pwd.h> 51 #include <string.h> 52 53 #include "fsck.h" 54 55 static ino_t startinum; 56 57 static int iblock __P((struct inodesc *, long ilevel, quad_t isize)); 58 59 int 60 ckinode(dp, idesc) 61 struct dinode *dp; 62 register struct inodesc *idesc; 63 { 64 ufs_daddr_t *ap; 65 int ret; 66 long n, ndb, offset; 67 struct dinode dino; 68 quad_t remsize, sizepb; 69 mode_t mode; 70 char pathbuf[MAXPATHLEN + 1]; 71 72 if (idesc->id_fix != IGNORE) 73 idesc->id_fix = DONTKNOW; 74 idesc->id_entryno = 0; 75 idesc->id_filesize = dp->di_size; 76 mode = dp->di_mode & IFMT; 77 if (mode == IFBLK || mode == IFCHR || (mode == IFLNK && 78 dp->di_size < (unsigned)sblock.fs_maxsymlinklen)) 79 return (KEEPON); 80 dino = *dp; 81 ndb = howmany(dino.di_size, sblock.fs_bsize); 82 for (ap = &dino.di_db[0]; ap < &dino.di_db[NDADDR]; ap++) { 83 if (--ndb == 0 && (offset = blkoff(&sblock, dino.di_size)) != 0) 84 idesc->id_numfrags = 85 numfrags(&sblock, fragroundup(&sblock, offset)); 86 else 87 idesc->id_numfrags = sblock.fs_frag; 88 if (*ap == 0) { 89 if (idesc->id_type == DATA && ndb >= 0) { 90 /* An empty block in a directory XXX */ 91 getpathname(pathbuf, idesc->id_number, 92 idesc->id_number); 93 pfatal("DIRECTORY %s: CONTAINS EMPTY BLOCKS", 94 pathbuf); 95 if (reply("ADJUST LENGTH") == 1) { 96 dp = ginode(idesc->id_number); 97 dp->di_size = (ap - &dino.di_db[0]) * 98 sblock.fs_bsize; 99 printf( 100 "YOU MUST RERUN FSCK AFTERWARDS\n"); 101 rerun = 1; 102 inodirty(); 103 104 } 105 } 106 continue; 107 } 108 idesc->id_blkno = *ap; 109 if (idesc->id_type == ADDR) 110 ret = (*idesc->id_func)(idesc); 111 else 112 ret = dirscan(idesc); 113 if (ret & STOP) 114 return (ret); 115 } 116 idesc->id_numfrags = sblock.fs_frag; 117 remsize = dino.di_size - sblock.fs_bsize * NDADDR; 118 sizepb = sblock.fs_bsize; 119 for (ap = &dino.di_ib[0], n = 1; n <= NIADDR; ap++, n++) { 120 if (*ap) { 121 idesc->id_blkno = *ap; 122 ret = iblock(idesc, n, remsize); 123 if (ret & STOP) 124 return (ret); 125 } else { 126 if (idesc->id_type == DATA && remsize > 0) { 127 /* An empty block in a directory XXX */ 128 getpathname(pathbuf, idesc->id_number, 129 idesc->id_number); 130 pfatal("DIRECTORY %s: CONTAINS EMPTY BLOCKS", 131 pathbuf); 132 if (reply("ADJUST LENGTH") == 1) { 133 dp = ginode(idesc->id_number); 134 dp->di_size -= remsize; 135 remsize = 0; 136 printf( 137 "YOU MUST RERUN FSCK AFTERWARDS\n"); 138 rerun = 1; 139 inodirty(); 140 break; 141 } 142 } 143 } 144 sizepb *= NINDIR(&sblock); 145 remsize -= sizepb; 146 } 147 return (KEEPON); 148 } 149 150 static int 151 iblock(idesc, ilevel, isize) 152 struct inodesc *idesc; 153 long ilevel; 154 quad_t isize; 155 { 156 ufs_daddr_t *ap; 157 ufs_daddr_t *aplim; 158 struct bufarea *bp; 159 int i, n, (*func)(), nif; 160 quad_t sizepb; 161 char buf[BUFSIZ]; 162 char pathbuf[MAXPATHLEN + 1]; 163 struct dinode *dp; 164 165 if (idesc->id_type == ADDR) { 166 func = idesc->id_func; 167 if (((n = (*func)(idesc)) & KEEPON) == 0) 168 return (n); 169 } else 170 func = dirscan; 171 if (chkrange(idesc->id_blkno, idesc->id_numfrags)) 172 return (SKIP); 173 bp = getdatablk(idesc->id_blkno, sblock.fs_bsize); 174 ilevel--; 175 for (sizepb = sblock.fs_bsize, i = 0; i < ilevel; i++) 176 sizepb *= NINDIR(&sblock); 177 nif = howmany(isize , sizepb); 178 if (nif > NINDIR(&sblock)) 179 nif = NINDIR(&sblock); 180 if (idesc->id_func == pass1check && nif < NINDIR(&sblock)) { 181 aplim = &bp->b_un.b_indir[NINDIR(&sblock)]; 182 for (ap = &bp->b_un.b_indir[nif]; ap < aplim; ap++) { 183 if (*ap == 0) 184 continue; 185 (void)sprintf(buf, "PARTIALLY TRUNCATED INODE I=%lu", 186 (u_long)idesc->id_number); 187 if (dofix(idesc, buf)) { 188 *ap = 0; 189 dirty(bp); 190 } 191 } 192 flush(fswritefd, bp); 193 } 194 aplim = &bp->b_un.b_indir[nif]; 195 for (ap = bp->b_un.b_indir; ap < aplim; ap++) { 196 if (*ap) { 197 idesc->id_blkno = *ap; 198 if (ilevel == 0) 199 n = (*func)(idesc); 200 else 201 n = iblock(idesc, ilevel, isize); 202 if (n & STOP) { 203 bp->b_flags &= ~B_INUSE; 204 return (n); 205 } 206 } else { 207 if (idesc->id_type == DATA && isize > 0) { 208 /* An empty block in a directory XXX */ 209 getpathname(pathbuf, idesc->id_number, 210 idesc->id_number); 211 pfatal("DIRECTORY %s: CONTAINS EMPTY BLOCKS", 212 pathbuf); 213 if (reply("ADJUST LENGTH") == 1) { 214 dp = ginode(idesc->id_number); 215 dp->di_size -= isize; 216 isize = 0; 217 printf( 218 "YOU MUST RERUN FSCK AFTERWARDS\n"); 219 rerun = 1; 220 inodirty(); 221 bp->b_flags &= ~B_INUSE; 222 return(STOP); 223 } 224 } 225 } 226 isize -= sizepb; 227 } 228 bp->b_flags &= ~B_INUSE; 229 return (KEEPON); 230 } 231 232 /* 233 * Check that a block in a legal block number. 234 * Return 0 if in range, 1 if out of range. 235 */ 236 int 237 chkrange(blk, cnt) 238 ufs_daddr_t blk; 239 int cnt; 240 { 241 register int c; 242 243 if (cnt <= 0 || blk <= 0 || blk > maxfsblock || 244 cnt - 1 > maxfsblock - blk) 245 return (1); 246 if (cnt > sblock.fs_frag || 247 fragnum(&sblock, blk) + cnt > sblock.fs_frag) { 248 if (debug) 249 printf("bad size: blk %ld, offset %ld, size %ld\n", 250 blk, fragnum(&sblock, blk), cnt); 251 return (1); 252 } 253 c = dtog(&sblock, blk); 254 if (blk < cgdmin(&sblock, c)) { 255 if ((blk + cnt) > cgsblock(&sblock, c)) { 256 if (debug) { 257 printf("blk %ld < cgdmin %ld;", 258 (long)blk, (long)cgdmin(&sblock, c)); 259 printf(" blk + cnt %ld > cgsbase %ld\n", 260 (long)(blk + cnt), 261 (long)cgsblock(&sblock, c)); 262 } 263 return (1); 264 } 265 } else { 266 if ((blk + cnt) > cgbase(&sblock, c+1)) { 267 if (debug) { 268 printf("blk %ld >= cgdmin %ld;", 269 (long)blk, (long)cgdmin(&sblock, c)); 270 printf(" blk + cnt %ld > sblock.fs_fpg %ld\n", 271 (long)(blk + cnt), (long)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 ufs_daddr_t iblk; 287 288 if (inumber < ROOTINO || inumber > maxino) 289 errx(EEXIT, "bad inode number %d to ginode", inumber); 290 if (startinum == 0 || 291 inumber < startinum || inumber >= startinum + INOPB(&sblock)) { 292 iblk = ino_to_fsba(&sblock, inumber); 293 if (pbp != 0) 294 pbp->b_flags &= ~B_INUSE; 295 pbp = getdatablk(iblk, sblock.fs_bsize); 296 startinum = (inumber / INOPB(&sblock)) * INOPB(&sblock); 297 } 298 return (&pbp->b_un.b_dinode[inumber % INOPB(&sblock)]); 299 } 300 301 /* 302 * Special purpose version of ginode used to optimize first pass 303 * over all the inodes in numerical order. 304 */ 305 ino_t nextino, lastinum; 306 long readcnt, readpercg, fullcnt, inobufsize, partialcnt, partialsize; 307 struct dinode *inodebuf; 308 309 struct dinode * 310 getnextinode(inumber) 311 ino_t inumber; 312 { 313 long size; 314 ufs_daddr_t dblk; 315 static struct dinode *dp; 316 317 if (inumber != nextino++ || inumber > maxino) 318 errx(EEXIT, "bad inode number %d to nextinode", inumber); 319 if (inumber >= lastinum) { 320 readcnt++; 321 dblk = fsbtodb(&sblock, ino_to_fsba(&sblock, lastinum)); 322 if (readcnt % readpercg == 0) { 323 size = partialsize; 324 lastinum += partialcnt; 325 } else { 326 size = inobufsize; 327 lastinum += fullcnt; 328 } 329 /* 330 * If bread returns an error, it will already have zeroed 331 * out the buffer, so we do not need to do so here. 332 */ 333 (void)bread(fsreadfd, (char *)inodebuf, dblk, size); 334 dp = inodebuf; 335 } 336 return (dp++); 337 } 338 339 void 340 setinodebuf(inum) 341 ino_t inum; 342 { 343 344 if (inum % sblock.fs_ipg != 0) 345 errx(EEXIT, "bad inode number %d to setinodebuf", inum); 346 startinum = 0; 347 nextino = inum; 348 lastinum = inum; 349 readcnt = 0; 350 if (inodebuf != NULL) 351 return; 352 inobufsize = blkroundup(&sblock, INOBUFSIZE); 353 fullcnt = inobufsize / sizeof(struct dinode); 354 readpercg = sblock.fs_ipg / fullcnt; 355 partialcnt = sblock.fs_ipg % fullcnt; 356 partialsize = partialcnt * sizeof(struct dinode); 357 if (partialcnt != 0) { 358 readpercg++; 359 } else { 360 partialcnt = fullcnt; 361 partialsize = inobufsize; 362 } 363 if ((inodebuf = (struct dinode *)malloc((unsigned)inobufsize)) == NULL) 364 errx(EEXIT, "cannot allocate space for inode buffer"); 365 } 366 367 void 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 void 384 cacheino(dp, inumber) 385 register struct dinode *dp; 386 ino_t inumber; 387 { 388 register struct inoinfo *inp; 389 struct inoinfo **inpp; 390 int blks; 391 392 blks = howmany(dp->di_size, sblock.fs_bsize); 393 if (blks > NDADDR) 394 blks = NDADDR + NIADDR; 395 inp = (struct inoinfo *) 396 malloc(sizeof(*inp) + (blks - 1) * sizeof(ufs_daddr_t)); 397 if (inp == NULL) 398 errx(EEXIT, "cannot increase directory list"); 399 inpp = &inphead[inumber % dirhash]; 400 inp->i_nexthash = *inpp; 401 *inpp = inp; 402 inp->i_parent = inumber == ROOTINO ? ROOTINO : (ino_t)0; 403 inp->i_dotdot = (ino_t)0; 404 inp->i_number = inumber; 405 inp->i_isize = dp->di_size; 406 inp->i_numblks = blks * sizeof(ufs_daddr_t); 407 memmove(&inp->i_blks[0], &dp->di_db[0], (size_t)inp->i_numblks); 408 if (inplast == listmax) { 409 listmax += 100; 410 inpsort = (struct inoinfo **)realloc((char *)inpsort, 411 (unsigned)listmax * sizeof(struct inoinfo *)); 412 if (inpsort == NULL) 413 errx(EEXIT, "cannot increase directory list"); 414 } 415 inpsort[inplast++] = inp; 416 } 417 418 /* 419 * Look up an inode cache structure. 420 */ 421 struct inoinfo * 422 getinoinfo(inumber) 423 ino_t inumber; 424 { 425 register struct inoinfo *inp; 426 427 for (inp = inphead[inumber % dirhash]; inp; inp = inp->i_nexthash) { 428 if (inp->i_number != inumber) 429 continue; 430 return (inp); 431 } 432 errx(EEXIT, "cannot find inode %d", inumber); 433 return ((struct inoinfo *)0); 434 } 435 436 /* 437 * Clean up all the inode cache structure. 438 */ 439 void 440 inocleanup() 441 { 442 register struct inoinfo **inpp; 443 444 if (inphead == NULL) 445 return; 446 for (inpp = &inpsort[inplast - 1]; inpp >= inpsort; inpp--) 447 free((char *)(*inpp)); 448 free((char *)inphead); 449 free((char *)inpsort); 450 inphead = inpsort = NULL; 451 } 452 453 void 454 inodirty() 455 { 456 457 dirty(pbp); 458 } 459 460 void 461 clri(idesc, type, flag) 462 register struct inodesc *idesc; 463 char *type; 464 int flag; 465 { 466 register struct dinode *dp; 467 468 dp = ginode(idesc->id_number); 469 if (flag == 1) { 470 pwarn("%s %s", type, 471 (dp->di_mode & IFMT) == IFDIR ? "DIR" : "FILE"); 472 pinode(idesc->id_number); 473 } 474 if (preen || reply("CLEAR") == 1) { 475 if (preen) 476 printf(" (CLEARED)\n"); 477 n_files--; 478 (void)ckinode(dp, idesc); 479 clearinode(dp); 480 inoinfo(idesc->id_number)->ino_state = USTATE; 481 inodirty(); 482 } 483 } 484 485 int 486 findname(idesc) 487 struct inodesc *idesc; 488 { 489 register struct direct *dirp = idesc->id_dirp; 490 491 if (dirp->d_ino != idesc->id_parent || idesc->id_entryno < 2) { 492 idesc->id_entryno++; 493 return (KEEPON); 494 } 495 memmove(idesc->id_name, dirp->d_name, (size_t)dirp->d_namlen + 1); 496 return (STOP|FOUND); 497 } 498 499 int 500 findino(idesc) 501 struct inodesc *idesc; 502 { 503 register struct direct *dirp = idesc->id_dirp; 504 505 if (dirp->d_ino == 0) 506 return (KEEPON); 507 if (strcmp(dirp->d_name, idesc->id_name) == 0 && 508 dirp->d_ino >= ROOTINO && dirp->d_ino <= maxino) { 509 idesc->id_parent = dirp->d_ino; 510 return (STOP|FOUND); 511 } 512 return (KEEPON); 513 } 514 515 int 516 clearentry(idesc) 517 struct inodesc *idesc; 518 { 519 register struct direct *dirp = idesc->id_dirp; 520 521 if (dirp->d_ino != idesc->id_parent || idesc->id_entryno < 2) { 522 idesc->id_entryno++; 523 return (KEEPON); 524 } 525 dirp->d_ino = 0; 526 return (STOP|FOUND|ALTERED); 527 } 528 529 void 530 pinode(ino) 531 ino_t ino; 532 { 533 register struct dinode *dp; 534 register char *p; 535 struct passwd *pw; 536 time_t t; 537 538 printf(" I=%lu ", (u_long)ino); 539 if (ino < ROOTINO || ino > maxino) 540 return; 541 dp = ginode(ino); 542 printf(" OWNER="); 543 if ((pw = getpwuid((int)dp->di_uid)) != 0) 544 printf("%s ", pw->pw_name); 545 else 546 printf("%u ", (unsigned)dp->di_uid); 547 printf("MODE=%o\n", dp->di_mode); 548 if (preen) 549 printf("%s: ", cdevname); 550 printf("SIZE=%qu ", dp->di_size); 551 t = dp->di_mtime; 552 p = ctime(&t); 553 printf("MTIME=%12.12s %4.4s ", &p[4], &p[20]); 554 } 555 556 void 557 blkerror(ino, type, blk) 558 ino_t ino; 559 char *type; 560 ufs_daddr_t blk; 561 { 562 563 pfatal("%ld %s I=%lu", blk, type, ino); 564 printf("\n"); 565 switch (inoinfo(ino)->ino_state) { 566 567 case FSTATE: 568 inoinfo(ino)->ino_state = FCLEAR; 569 return; 570 571 case DSTATE: 572 inoinfo(ino)->ino_state = DCLEAR; 573 return; 574 575 case FCLEAR: 576 case DCLEAR: 577 return; 578 579 default: 580 errx(EEXIT, "BAD STATE %d TO BLKERR", inoinfo(ino)->ino_state); 581 /* NOTREACHED */ 582 } 583 } 584 585 /* 586 * allocate an unused inode 587 */ 588 ino_t 589 allocino(request, type) 590 ino_t request; 591 int type; 592 { 593 register ino_t ino; 594 register struct dinode *dp; 595 struct cg *cgp = &cgrp; 596 int cg; 597 598 if (request == 0) 599 request = ROOTINO; 600 else if (inoinfo(request)->ino_state != USTATE) 601 return (0); 602 for (ino = request; ino < maxino; ino++) 603 if (inoinfo(ino)->ino_state == USTATE) 604 break; 605 if (ino == maxino) 606 return (0); 607 cg = ino_to_cg(&sblock, ino); 608 getblk(&cgblk, cgtod(&sblock, cg), sblock.fs_cgsize); 609 if (!cg_chkmagic(cgp)) 610 pfatal("CG %d: BAD MAGIC NUMBER\n", cg); 611 setbit(cg_inosused(cgp), ino % sblock.fs_ipg); 612 cgp->cg_cs.cs_nifree--; 613 switch (type & IFMT) { 614 case IFDIR: 615 inoinfo(ino)->ino_state = DSTATE; 616 cgp->cg_cs.cs_ndir++; 617 break; 618 case IFREG: 619 case IFLNK: 620 inoinfo(ino)->ino_state = FSTATE; 621 break; 622 default: 623 return (0); 624 } 625 cgdirty(); 626 dp = ginode(ino); 627 dp->di_db[0] = allocblk((long)1); 628 if (dp->di_db[0] == 0) { 629 inoinfo(ino)->ino_state = USTATE; 630 return (0); 631 } 632 dp->di_mode = type; 633 dp->di_flags = 0; 634 dp->di_atime = time(NULL); 635 dp->di_mtime = dp->di_ctime = dp->di_atime; 636 dp->di_mtimensec = dp->di_ctimensec = dp->di_atimensec = 0; 637 dp->di_size = sblock.fs_fsize; 638 dp->di_blocks = btodb(sblock.fs_fsize); 639 n_files++; 640 inodirty(); 641 if (newinofmt) 642 inoinfo(ino)->ino_type = IFTODT(type); 643 return (ino); 644 } 645 646 /* 647 * deallocate an inode 648 */ 649 void 650 freeino(ino) 651 ino_t ino; 652 { 653 struct inodesc idesc; 654 struct dinode *dp; 655 656 memset(&idesc, 0, sizeof(struct inodesc)); 657 idesc.id_type = ADDR; 658 idesc.id_func = pass4check; 659 idesc.id_number = ino; 660 dp = ginode(ino); 661 (void)ckinode(dp, &idesc); 662 clearinode(dp); 663 inodirty(); 664 inoinfo(ino)->ino_state = USTATE; 665 n_files--; 666 } 667