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