1 /* $NetBSD: inode.c,v 1.5 1998/07/28 19:22:54 mycroft Exp $ */ 2 3 /* 4 * Copyright (c) 1997 Manuel Bouyer. 5 * Copyright (c) 1980, 1986, 1993 6 * The Regents of the University of California. All rights reserved. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 1. Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in the 15 * documentation and/or other materials provided with the distribution. 16 * 3. All advertising materials mentioning features or use of this software 17 * must display the following acknowledgement: 18 * This product includes software developed by the University of 19 * California, Berkeley and its contributors. 20 * 4. Neither the name of the University nor the names of its contributors 21 * may be used to endorse or promote products derived from this software 22 * without specific prior written permission. 23 * 24 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 25 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 26 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 27 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 28 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 29 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 30 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 31 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 32 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 33 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 34 * SUCH DAMAGE. 35 */ 36 37 #include <sys/cdefs.h> 38 #ifndef lint 39 #if 0 40 static char sccsid[] = "@(#)inode.c 8.5 (Berkeley) 2/8/95"; 41 #else 42 __RCSID("$NetBSD: inode.c,v 1.5 1998/07/28 19:22:54 mycroft Exp $"); 43 #endif 44 #endif /* not lint */ 45 46 #include <sys/param.h> 47 #include <sys/time.h> 48 #include <ufs/ext2fs/ext2fs_dinode.h> 49 #include <ufs/ext2fs/ext2fs_dir.h> 50 #include <ufs/ext2fs/ext2fs.h> 51 52 #include <ufs/ufs/dinode.h> /* for IFMT & friends */ 53 #ifndef SMALL 54 #include <pwd.h> 55 #endif 56 #include <stdio.h> 57 #include <stdlib.h> 58 #include <string.h> 59 #include <time.h> 60 61 #include "fsck.h" 62 #include "fsutil.h" 63 #include "extern.h" 64 65 /* 66 * CG is stored in fs byte order in memory, so we can't use ino_to_fsba 67 * here. 68 */ 69 70 #define fsck_ino_to_fsba(fs, x) \ 71 (fs2h32((fs)->e2fs_gd[ino_to_cg(fs, x)].ext2bgd_i_tables) + \ 72 (((x)-1) % (fs)->e2fs.e2fs_ipg)/(fs)->e2fs_ipb) 73 74 75 static ino_t startinum; 76 77 static int iblock __P((struct inodesc *, long, u_int64_t)); 78 79 int 80 ckinode(dp, idesc) 81 struct ext2fs_dinode *dp; 82 struct inodesc *idesc; 83 { 84 u_int32_t *ap; 85 long ret, n, ndb; 86 struct ext2fs_dinode dino; 87 u_int64_t remsize, sizepb; 88 mode_t mode; 89 char pathbuf[MAXPATHLEN + 1]; 90 91 if (idesc->id_fix != IGNORE) 92 idesc->id_fix = DONTKNOW; 93 idesc->id_entryno = 0; 94 idesc->id_filesize = fs2h32(dp->e2di_size); 95 mode = fs2h16(dp->e2di_mode) & IFMT; 96 if (mode == IFBLK || mode == IFCHR || (mode == IFLNK && 97 (fs2h32(dp->e2di_size) < EXT2_MAXSYMLINKLEN))) 98 return (KEEPON); 99 dino = *dp; 100 ndb = howmany(fs2h32(dino.e2di_size), sblock.e2fs_bsize); 101 for (ap = &dino.e2di_blocks[0]; ap < &dino.e2di_blocks[NDADDR]; 102 ap++,ndb--) { 103 idesc->id_numfrags = 1; 104 if (*ap == 0) { 105 if (idesc->id_type == DATA && ndb > 0) { 106 /* An empty block in a directory XXX */ 107 getpathname(pathbuf, idesc->id_number, 108 idesc->id_number); 109 pfatal("DIRECTORY %s: CONTAINS EMPTY BLOCKS", 110 pathbuf); 111 if (reply("ADJUST LENGTH") == 1) { 112 dp = ginode(idesc->id_number); 113 dp->e2di_size = h2fs32((ap - &dino.e2di_blocks[0]) * 114 sblock.e2fs_bsize); 115 printf( 116 "YOU MUST RERUN FSCK AFTERWARDS\n"); 117 rerun = 1; 118 inodirty(); 119 } 120 } 121 continue; 122 } 123 idesc->id_blkno = fs2h32(*ap); 124 if (idesc->id_type == ADDR) 125 ret = (*idesc->id_func)(idesc); 126 else 127 ret = dirscan(idesc); 128 if (ret & STOP) 129 return (ret); 130 } 131 idesc->id_numfrags = 1; 132 remsize = fs2h32(dino.e2di_size) - sblock.e2fs_bsize * NDADDR; 133 sizepb = sblock.e2fs_bsize; 134 for (ap = &dino.e2di_blocks[NDADDR], n = 1; n <= NIADDR; ap++, n++) { 135 if (*ap) { 136 idesc->id_blkno = fs2h32(*ap); 137 ret = iblock(idesc, n, remsize); 138 if (ret & STOP) 139 return (ret); 140 } else { 141 if (idesc->id_type == DATA && remsize > 0) { 142 /* An empty block in a directory XXX */ 143 getpathname(pathbuf, idesc->id_number, 144 idesc->id_number); 145 pfatal("DIRECTORY %s: CONTAINS EMPTY BLOCKS", 146 pathbuf); 147 if (reply("ADJUST LENGTH") == 1) { 148 dp = ginode(idesc->id_number); 149 dp->e2di_size = h2fs32(fs2h32(dp->e2di_size) - remsize); 150 remsize = 0; 151 printf( 152 "YOU MUST RERUN FSCK AFTERWARDS\n"); 153 rerun = 1; 154 inodirty(); 155 break; 156 } 157 } 158 } 159 sizepb *= NINDIR(&sblock); 160 remsize -= sizepb; 161 } 162 return (KEEPON); 163 } 164 165 static int 166 iblock(idesc, ilevel, isize) 167 struct inodesc *idesc; 168 long ilevel; 169 u_int64_t isize; 170 { 171 daddr_t *ap; 172 daddr_t *aplim; 173 struct bufarea *bp; 174 int i, n, (*func) __P((struct inodesc *)), nif; 175 u_int64_t sizepb; 176 char buf[BUFSIZ]; 177 char pathbuf[MAXPATHLEN + 1]; 178 struct ext2fs_dinode *dp; 179 180 if (idesc->id_type == ADDR) { 181 func = idesc->id_func; 182 if (((n = (*func)(idesc)) & KEEPON) == 0) 183 return (n); 184 } else 185 func = dirscan; 186 if (chkrange(idesc->id_blkno, idesc->id_numfrags)) 187 return (SKIP); 188 bp = getdatablk(idesc->id_blkno, sblock.e2fs_bsize); 189 ilevel--; 190 for (sizepb = sblock.e2fs_bsize, i = 0; i < ilevel; i++) 191 sizepb *= NINDIR(&sblock); 192 if (isize > sizepb * NINDIR(&sblock)) 193 nif = NINDIR(&sblock); 194 else 195 nif = howmany(isize, sizepb); 196 if (idesc->id_func == pass1check && 197 nif < NINDIR(&sblock)) { 198 aplim = &bp->b_un.b_indir[NINDIR(&sblock)]; 199 for (ap = &bp->b_un.b_indir[nif]; ap < aplim; ap++) { 200 if (*ap == 0) 201 continue; 202 (void)snprintf(buf, sizeof(buf), 203 "PARTIALLY TRUNCATED INODE I=%u", idesc->id_number); 204 if (dofix(idesc, buf)) { 205 *ap = 0; 206 dirty(bp); 207 } 208 } 209 flush(fswritefd, bp); 210 } 211 aplim = &bp->b_un.b_indir[nif]; 212 for (ap = bp->b_un.b_indir; ap < aplim; ap++) { 213 if (*ap) { 214 idesc->id_blkno = fs2h32(*ap); 215 if (ilevel == 0) 216 n = (*func)(idesc); 217 else 218 n = iblock(idesc, ilevel, isize); 219 if (n & STOP) { 220 bp->b_flags &= ~B_INUSE; 221 return (n); 222 } 223 } else { 224 if (idesc->id_type == DATA && isize > 0) { 225 /* An empty block in a directory XXX */ 226 getpathname(pathbuf, idesc->id_number, 227 idesc->id_number); 228 pfatal("DIRECTORY %s: CONTAINS EMPTY BLOCKS", 229 pathbuf); 230 if (reply("ADJUST LENGTH") == 1) { 231 dp = ginode(idesc->id_number); 232 dp->e2di_size = h2fs32(fs2h32(dp->e2di_size) - isize); 233 isize = 0; 234 printf( 235 "YOU MUST RERUN FSCK AFTERWARDS\n"); 236 rerun = 1; 237 inodirty(); 238 bp->b_flags &= ~B_INUSE; 239 return(STOP); 240 } 241 } 242 } 243 isize -= sizepb; 244 } 245 bp->b_flags &= ~B_INUSE; 246 return (KEEPON); 247 } 248 249 /* 250 * Check that a block in a legal block number. 251 * Return 0 if in range, 1 if out of range. 252 */ 253 int 254 chkrange(blk, cnt) 255 daddr_t blk; 256 int cnt; 257 { 258 int c; 259 260 if ((unsigned)(blk + cnt) > maxfsblock) 261 return (1); 262 c = dtog(&sblock, blk); 263 if (blk < sblock.e2fs.e2fs_bpg * c + cgoverhead + 264 sblock.e2fs.e2fs_first_dblock) { 265 if ((blk + cnt) > sblock.e2fs.e2fs_bpg * c + cgoverhead + 266 sblock.e2fs.e2fs_first_dblock) { 267 if (debug) { 268 printf("blk %d < cgdmin %d;", 269 blk, sblock.e2fs.e2fs_bpg * c + cgoverhead + 270 sblock.e2fs.e2fs_first_dblock); 271 printf(" blk + cnt %d > cgsbase %d\n", 272 blk + cnt, sblock.e2fs.e2fs_bpg * c + cgoverhead + 273 sblock.e2fs.e2fs_first_dblock); 274 } 275 return (1); 276 } 277 } else { 278 if ((blk + cnt) > sblock.e2fs.e2fs_bpg * (c + 1) + cgoverhead + 279 sblock.e2fs.e2fs_first_dblock) { 280 if (debug) { 281 printf("blk %d >= cgdmin %d;", 282 blk, sblock.e2fs.e2fs_bpg * c + cgoverhead + 283 sblock.e2fs.e2fs_first_dblock); 284 printf(" blk + cnt %d > cgdmax %d\n", 285 blk+cnt, sblock.e2fs.e2fs_bpg * (c + 1) + cgoverhead + 286 sblock.e2fs.e2fs_first_dblock); 287 } 288 return (1); 289 } 290 } 291 return (0); 292 } 293 294 /* 295 * General purpose interface for reading inodes. 296 */ 297 struct ext2fs_dinode * 298 ginode(inumber) 299 ino_t inumber; 300 { 301 daddr_t iblk; 302 303 if ((inumber < EXT2_FIRSTINO && inumber != EXT2_ROOTINO) 304 || inumber > maxino) 305 errexit("bad inode number %d to ginode\n", inumber); 306 if (startinum == 0 || 307 inumber < startinum || inumber >= startinum + sblock.e2fs_ipb) { 308 iblk = fsck_ino_to_fsba(&sblock, inumber); 309 if (pbp != 0) 310 pbp->b_flags &= ~B_INUSE; 311 pbp = getdatablk(iblk, sblock.e2fs_bsize); 312 startinum = ((inumber -1) / sblock.e2fs_ipb) * sblock.e2fs_ipb + 1; 313 } 314 return (&pbp->b_un.b_dinode[(inumber-1) % sblock.e2fs_ipb]); 315 } 316 317 /* 318 * Special purpose version of ginode used to optimize first pass 319 * over all the inodes in numerical order. 320 */ 321 ino_t nextino, lastinum; 322 long readcnt, readpercg, fullcnt, inobufsize, partialcnt, partialsize; 323 struct ext2fs_dinode *inodebuf; 324 325 struct ext2fs_dinode * 326 getnextinode(inumber) 327 ino_t inumber; 328 { 329 long size; 330 daddr_t dblk; 331 static struct ext2fs_dinode *dp; 332 333 if (inumber != nextino++ || inumber > maxino) 334 errexit("bad inode number %d to nextinode\n", inumber); 335 if (inumber >= lastinum) { 336 readcnt++; 337 dblk = fsbtodb(&sblock, fsck_ino_to_fsba(&sblock, lastinum)); 338 if (readcnt % readpercg == 0) { 339 size = partialsize; 340 lastinum += partialcnt; 341 } else { 342 size = inobufsize; 343 lastinum += fullcnt; 344 } 345 (void)bread(fsreadfd, (char *)inodebuf, dblk, size); 346 dp = inodebuf; 347 } 348 return (dp++); 349 } 350 351 void 352 resetinodebuf() 353 { 354 355 startinum = 0; 356 nextino = 1; 357 lastinum = 1; 358 readcnt = 0; 359 inobufsize = blkroundup(&sblock, INOBUFSIZE); 360 fullcnt = inobufsize / sizeof(struct ext2fs_dinode); 361 readpercg = sblock.e2fs.e2fs_ipg / fullcnt; 362 partialcnt = sblock.e2fs.e2fs_ipg % fullcnt; 363 partialsize = partialcnt * sizeof(struct ext2fs_dinode); 364 if (partialcnt != 0) { 365 readpercg++; 366 } else { 367 partialcnt = fullcnt; 368 partialsize = inobufsize; 369 } 370 if (inodebuf == NULL && 371 (inodebuf = (struct ext2fs_dinode *)malloc((unsigned)inobufsize)) == 372 NULL) 373 errexit("Cannot allocate space for inode buffer\n"); 374 while (nextino < EXT2_ROOTINO) 375 (void)getnextinode(nextino); 376 } 377 378 void 379 freeinodebuf() 380 { 381 382 if (inodebuf != NULL) 383 free((char *)inodebuf); 384 inodebuf = NULL; 385 } 386 387 /* 388 * Routines to maintain information about directory inodes. 389 * This is built during the first pass and used during the 390 * second and third passes. 391 * 392 * Enter inodes into the cache. 393 */ 394 void 395 cacheino(dp, inumber) 396 struct ext2fs_dinode *dp; 397 ino_t inumber; 398 { 399 struct inoinfo *inp; 400 struct inoinfo **inpp; 401 unsigned int blks; 402 403 blks = howmany(fs2h32(dp->e2di_size), sblock.e2fs_bsize); 404 if (blks > NDADDR) 405 blks = NDADDR + NIADDR; 406 inp = (struct inoinfo *) 407 malloc(sizeof(*inp) + (blks - 1) * sizeof(daddr_t)); 408 if (inp == NULL) 409 return; 410 inpp = &inphead[inumber % numdirs]; 411 inp->i_nexthash = *inpp; 412 *inpp = inp; 413 inp->i_child = inp->i_sibling = inp->i_parentp = 0; 414 if (inumber == EXT2_ROOTINO) 415 inp->i_parent = EXT2_ROOTINO; 416 else 417 inp->i_parent = (ino_t)0; 418 inp->i_dotdot = (ino_t)0; 419 inp->i_number = inumber; 420 inp->i_isize = fs2h32(dp->e2di_size); 421 inp->i_numblks = blks * sizeof(daddr_t); 422 memcpy(&inp->i_blks[0], &dp->e2di_blocks[0], (size_t)inp->i_numblks); 423 if (inplast == listmax) { 424 listmax += 100; 425 inpsort = (struct inoinfo **)realloc((char *)inpsort, 426 (unsigned)listmax * sizeof(struct inoinfo *)); 427 if (inpsort == NULL) 428 errexit("cannot increase directory list\n"); 429 } 430 inpsort[inplast++] = inp; 431 } 432 433 /* 434 * Look up an inode cache structure. 435 */ 436 struct inoinfo * 437 getinoinfo(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 (inp); 446 } 447 errexit("cannot find inode %d\n", inumber); 448 return ((struct inoinfo *)0); 449 } 450 451 /* 452 * Clean up all the inode cache structure. 453 */ 454 void 455 inocleanup() 456 { 457 struct inoinfo **inpp; 458 459 if (inphead == NULL) 460 return; 461 for (inpp = &inpsort[inplast - 1]; inpp >= inpsort; inpp--) 462 free((char *)(*inpp)); 463 free((char *)inphead); 464 free((char *)inpsort); 465 inphead = inpsort = NULL; 466 } 467 468 void 469 inodirty() 470 { 471 472 dirty(pbp); 473 } 474 475 void 476 clri(idesc, type, flag) 477 struct inodesc *idesc; 478 char *type; 479 int flag; 480 { 481 struct ext2fs_dinode *dp; 482 483 dp = ginode(idesc->id_number); 484 if (flag == 1) { 485 pwarn("%s %s", type, 486 (dp->e2di_mode & IFMT) == IFDIR ? "DIR" : "FILE"); 487 pinode(idesc->id_number); 488 } 489 if (preen || reply("CLEAR") == 1) { 490 if (preen) 491 printf(" (CLEARED)\n"); 492 n_files--; 493 (void)ckinode(dp, idesc); 494 clearinode(dp); 495 statemap[idesc->id_number] = USTATE; 496 inodirty(); 497 } 498 } 499 500 int 501 findname(idesc) 502 struct inodesc *idesc; 503 { 504 struct ext2fs_direct *dirp = idesc->id_dirp; 505 u_int16_t namlen = fs2h16(dirp->e2d_namlen); 506 507 if (fs2h32(dirp->e2d_ino) != idesc->id_parent) 508 return (KEEPON); 509 memcpy(idesc->id_name, dirp->e2d_name, (size_t)namlen); 510 idesc->id_name[namlen] = '\0'; 511 return (STOP|FOUND); 512 } 513 514 int 515 findino(idesc) 516 struct inodesc *idesc; 517 { 518 struct ext2fs_direct *dirp = idesc->id_dirp; 519 u_int32_t ino = fs2h32(dirp->e2d_ino); 520 521 if (ino == 0) 522 return (KEEPON); 523 if (strcmp(dirp->e2d_name, idesc->id_name) == 0 && 524 (ino == EXT2_ROOTINO || ino >= EXT2_FIRSTINO) 525 && ino <= maxino) { 526 idesc->id_parent = ino; 527 return (STOP|FOUND); 528 } 529 return (KEEPON); 530 } 531 532 void 533 pinode(ino) 534 ino_t ino; 535 { 536 struct ext2fs_dinode *dp; 537 char *p; 538 struct passwd *pw; 539 time_t t; 540 541 printf(" I=%u ", ino); 542 if ((ino < EXT2_FIRSTINO && ino != EXT2_ROOTINO) || ino > maxino) 543 return; 544 dp = ginode(ino); 545 printf(" OWNER="); 546 #ifndef SMALL 547 if ((pw = getpwuid((int)dp->e2di_uid)) != 0) 548 printf("%s ", pw->pw_name); 549 else 550 #endif 551 printf("%u ", (unsigned)fs2h16(dp->e2di_uid)); 552 printf("MODE=%o\n", fs2h16(dp->e2di_mode)); 553 if (preen) 554 printf("%s: ", cdevname()); 555 printf("SIZE=%u ", fs2h32(dp->e2di_size)); 556 t = fs2h32(dp->e2di_mtime); 557 p = ctime(&t); 558 printf("MTIME=%12.12s %4.4s ", &p[4], &p[20]); 559 } 560 561 void 562 blkerror(ino, type, blk) 563 ino_t ino; 564 char *type; 565 daddr_t blk; 566 { 567 568 pfatal("%d %s I=%u", blk, type, ino); 569 printf("\n"); 570 switch (statemap[ino]) { 571 572 case FSTATE: 573 statemap[ino] = FCLEAR; 574 return; 575 576 case DSTATE: 577 statemap[ino] = DCLEAR; 578 return; 579 580 case FCLEAR: 581 case DCLEAR: 582 return; 583 584 default: 585 errexit("BAD STATE %d TO BLKERR\n", statemap[ino]); 586 /* NOTREACHED */ 587 } 588 } 589 590 /* 591 * allocate an unused inode 592 */ 593 ino_t 594 allocino(request, type) 595 ino_t request; 596 int type; 597 { 598 ino_t ino; 599 struct ext2fs_dinode *dp; 600 time_t t; 601 602 if (request == 0) 603 request = EXT2_ROOTINO; 604 else if (statemap[request] != USTATE) 605 return (0); 606 for (ino = request; ino < maxino; ino++) { 607 if ((ino > EXT2_ROOTINO) && (ino < EXT2_FIRSTINO)) 608 continue; 609 if (statemap[ino] == USTATE) 610 break; 611 } 612 if (ino == maxino) 613 return (0); 614 switch (type & IFMT) { 615 case IFDIR: 616 statemap[ino] = DSTATE; 617 break; 618 case IFREG: 619 case IFLNK: 620 statemap[ino] = FSTATE; 621 break; 622 default: 623 return (0); 624 } 625 dp = ginode(ino); 626 dp->e2di_blocks[0] = h2fs32(allocblk()); 627 if (dp->e2di_blocks[0] == 0) { 628 statemap[ino] = USTATE; 629 return (0); 630 } 631 dp->e2di_mode = h2fs16(type); 632 (void)time(&t); 633 dp->e2di_atime = h2fs32(t); 634 dp->e2di_mtime = dp->e2di_ctime = dp->e2di_atime; 635 dp->e2di_dtime = 0; 636 dp->e2di_size = h2fs32(sblock.e2fs_bsize); 637 dp->e2di_nblock = h2fs32(btodb(sblock.e2fs_bsize)); 638 n_files++; 639 inodirty(); 640 return (ino); 641 } 642 643 /* 644 * deallocate an inode 645 */ 646 void 647 freeino(ino) 648 ino_t ino; 649 { 650 struct inodesc idesc; 651 struct ext2fs_dinode *dp; 652 653 memset(&idesc, 0, sizeof(struct inodesc)); 654 idesc.id_type = ADDR; 655 idesc.id_func = pass4check; 656 idesc.id_number = ino; 657 dp = ginode(ino); 658 (void)ckinode(dp, &idesc); 659 clearinode(dp); 660 inodirty(); 661 statemap[ino] = USTATE; 662 n_files--; 663 } 664