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