1 /* $OpenBSD: inode.c,v 1.36 2011/05/08 14:38:40 otto Exp $ */ 2 /* $NetBSD: inode.c,v 1.23 1996/10/11 20:15:47 thorpej Exp $ */ 3 4 /* 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. Neither the name of the University nor the names of its contributors 17 * may be used to endorse or promote products derived from this software 18 * without specific prior written permission. 19 * 20 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 23 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 30 * SUCH DAMAGE. 31 */ 32 33 #include <sys/param.h> 34 #include <sys/time.h> 35 #include <ufs/ufs/dinode.h> 36 #include <ufs/ufs/dir.h> 37 #include <ufs/ffs/fs.h> 38 #ifndef SMALL 39 #include <pwd.h> 40 #endif 41 #include <stdio.h> 42 #include <stdlib.h> 43 #include <string.h> 44 #include <unistd.h> 45 46 #include "fsck.h" 47 #include "fsutil.h" 48 #include "extern.h" 49 50 static ino_t startinum; 51 52 static int iblock(struct inodesc *, long, off_t); 53 54 int 55 ckinode(union dinode *dp, struct inodesc *idesc) 56 { 57 long ret, ndb, offset; 58 union dinode dino; 59 off_t sizepb, remsize; 60 mode_t mode; 61 int i; 62 char pathbuf[MAXPATHLEN + 1]; 63 64 if (idesc->id_fix != IGNORE) 65 idesc->id_fix = DONTKNOW; 66 idesc->id_entryno = 0; 67 idesc->id_filesize = DIP(dp, di_size); 68 mode = DIP(dp, di_mode) & IFMT; 69 if (mode == IFBLK || mode == IFCHR || (mode == IFLNK && 70 (DIP(dp, di_size) < sblock.fs_maxsymlinklen || 71 (sblock.fs_maxsymlinklen == 0 && DIP(dp, di_blocks) == 0)))) 72 return (KEEPON); 73 if (sblock.fs_magic == FS_UFS1_MAGIC) 74 dino.dp1 = dp->dp1; 75 else 76 dino.dp2 = dp->dp2; 77 ndb = howmany(DIP(&dino, di_size), sblock.fs_bsize); 78 for (i = 0; i < NDADDR; i++) { 79 if (--ndb == 0 && (offset = blkoff(&sblock, 80 DIP(&dino, di_size))) != 0) 81 idesc->id_numfrags = 82 numfrags(&sblock, fragroundup(&sblock, offset)); 83 else 84 idesc->id_numfrags = sblock.fs_frag; 85 if (DIP(&dino, di_db[i]) == 0) { 86 if (idesc->id_type == DATA && ndb >= 0) { 87 /* An empty block in a directory XXX */ 88 getpathname(pathbuf, sizeof pathbuf, 89 idesc->id_number, idesc->id_number); 90 pfatal("DIRECTORY %s: CONTAINS EMPTY BLOCKS", 91 pathbuf); 92 if (reply("ADJUST LENGTH") == 1) { 93 dp = ginode(idesc->id_number); 94 DIP_SET(dp, di_size, 95 i * sblock.fs_bsize); 96 printf( 97 "YOU MUST RERUN FSCK AFTERWARDS\n"); 98 rerun = 1; 99 inodirty(); 100 } 101 } 102 continue; 103 } 104 idesc->id_blkno = DIP(&dino, di_db[i]); 105 if (idesc->id_type == ADDR) 106 ret = (*idesc->id_func)(idesc); 107 else 108 ret = dirscan(idesc); 109 if (ret & STOP) 110 return (ret); 111 } 112 idesc->id_numfrags = sblock.fs_frag; 113 remsize = DIP(&dino, di_size) - sblock.fs_bsize * NDADDR; 114 sizepb = sblock.fs_bsize; 115 for (i = 0; i < NIADDR; i++) { 116 if (DIP(&dino, di_ib[i])) { 117 idesc->id_blkno = DIP(&dino, di_ib[i]); 118 ret = iblock(idesc, i + 1, remsize); 119 if (ret & STOP) 120 return (ret); 121 } else { 122 if (idesc->id_type == DATA && remsize > 0) { 123 /* An empty block in a directory XXX */ 124 getpathname(pathbuf, sizeof pathbuf, 125 idesc->id_number, idesc->id_number); 126 pfatal("DIRECTORY %s: CONTAINS EMPTY BLOCKS", 127 pathbuf); 128 if (reply("ADJUST LENGTH") == 1) { 129 dp = ginode(idesc->id_number); 130 DIP_SET(dp, di_size, 131 DIP(dp, di_size) - remsize); 132 remsize = 0; 133 printf( 134 "YOU MUST RERUN FSCK AFTERWARDS\n"); 135 rerun = 1; 136 inodirty(); 137 break; 138 } 139 } 140 } 141 sizepb *= NINDIR(&sblock); 142 remsize -= sizepb; 143 } 144 return (KEEPON); 145 } 146 147 static int 148 iblock(struct inodesc *idesc, long ilevel, off_t isize) 149 { 150 struct bufarea *bp; 151 int i, n, (*func)(struct inodesc *), nif; 152 off_t sizepb; 153 char buf[BUFSIZ]; 154 char pathbuf[MAXPATHLEN + 1]; 155 union 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 (isize < 0 || 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 if (howmany(isize, sizepb) > NINDIR(&sblock)) 170 nif = NINDIR(&sblock); 171 else 172 nif = howmany(isize, sizepb); 173 if (idesc->id_func == pass1check && nif < NINDIR(&sblock)) { 174 for (i = nif; i < NINDIR(&sblock); i++) { 175 if (IBLK(bp, i) == 0) 176 continue; 177 (void)snprintf(buf, sizeof buf, 178 "PARTIALLY TRUNCATED INODE I=%u", 179 idesc->id_number); 180 if (preen) 181 pfatal("%s", buf); 182 else if (dofix(idesc, buf)) { 183 IBLK_SET(bp, i, 0); 184 dirty(bp); 185 } 186 } 187 flush(fswritefd, bp); 188 } 189 for (i = 0; i < nif; i++) { 190 if (IBLK(bp, i)) { 191 idesc->id_blkno = IBLK(bp, i); 192 if (ilevel == 0) 193 n = (*func)(idesc); 194 else 195 n = iblock(idesc, ilevel, isize); 196 if (n & STOP) { 197 bp->b_flags &= ~B_INUSE; 198 return (n); 199 } 200 } else { 201 if (idesc->id_type == DATA && isize > 0) { 202 /* An empty block in a directory XXX */ 203 getpathname(pathbuf, sizeof pathbuf, 204 idesc->id_number, idesc->id_number); 205 pfatal("DIRECTORY %s: CONTAINS EMPTY BLOCKS", 206 pathbuf); 207 if (reply("ADJUST LENGTH") == 1) { 208 dp = ginode(idesc->id_number); 209 DIP_SET(dp, di_size, 210 DIP(dp, di_size) - isize); 211 isize = 0; 212 printf( 213 "YOU MUST RERUN FSCK AFTERWARDS\n"); 214 rerun = 1; 215 inodirty(); 216 bp->b_flags &= ~B_INUSE; 217 return(STOP); 218 } 219 } 220 } 221 isize -= sizepb; 222 } 223 bp->b_flags &= ~B_INUSE; 224 return (KEEPON); 225 } 226 227 /* 228 * Check that a block in a legal block number. 229 * Return 0 if in range, 1 if out of range. 230 */ 231 int 232 chkrange(daddr64_t blk, int cnt) 233 { 234 int c; 235 236 if (cnt <= 0 || blk <= 0 || blk > maxfsblock || 237 cnt - 1 > maxfsblock - blk) 238 return (1); 239 if (cnt > sblock.fs_frag || 240 fragnum(&sblock, blk) + cnt > sblock.fs_frag) { 241 if (debug) 242 printf("bad size: blk %lld, offset %lld, size %d\n", 243 blk, fragnum(&sblock, blk), cnt); 244 return (1); 245 } 246 c = dtog(&sblock, blk); 247 if (blk < cgdmin(&sblock, c)) { 248 if ((blk + cnt) > cgsblock(&sblock, c)) { 249 if (debug) { 250 printf("blk %lld < cgdmin %lld;", 251 blk, cgdmin(&sblock, c)); 252 printf(" blk + cnt %lld > cgsbase %lld\n", 253 blk + cnt, cgsblock(&sblock, c)); 254 } 255 return (1); 256 } 257 } else { 258 if ((blk + cnt) > cgbase(&sblock, c+1)) { 259 if (debug) { 260 printf("blk %lld >= cgdmin %lld;", 261 blk, cgdmin(&sblock, c)); 262 printf(" blk + cnt %lld > sblock.fs_fpg %d\n", 263 blk+cnt, sblock.fs_fpg); 264 } 265 return (1); 266 } 267 } 268 return (0); 269 } 270 271 /* 272 * General purpose interface for reading inodes. 273 */ 274 union dinode * 275 ginode(ino_t inumber) 276 { 277 daddr64_t iblk; 278 279 if (inumber < ROOTINO || inumber > maxino) 280 errexit("bad inode number %d to ginode\n", inumber); 281 if (startinum == 0 || 282 inumber < startinum || inumber >= startinum + INOPB(&sblock)) { 283 iblk = ino_to_fsba(&sblock, inumber); 284 if (pbp != 0) 285 pbp->b_flags &= ~B_INUSE; 286 pbp = getdatablk(iblk, sblock.fs_bsize); 287 startinum = (inumber / INOPB(&sblock)) * INOPB(&sblock); 288 } 289 if (sblock.fs_magic == FS_UFS1_MAGIC) 290 return ((union dinode *) 291 &pbp->b_un.b_dinode1[inumber % INOPB(&sblock)]); 292 return ((union dinode *)&pbp->b_un.b_dinode2[inumber % INOPB(&sblock)]); 293 } 294 295 /* 296 * Special purpose version of ginode used to optimize first pass 297 * over all the inodes in numerical order. 298 */ 299 ino_t nextino, lastinum; 300 long readcnt, readpercg, fullcnt, inobufsize, partialcnt, partialsize; 301 static caddr_t inodebuf; 302 303 union dinode * 304 getnextinode(ino_t inumber) 305 { 306 long size; 307 daddr64_t dblk; 308 union dinode *dp; 309 static caddr_t nextinop; 310 311 if (inumber != nextino++ || inumber > maxino) 312 errexit("bad inode number %d to nextinode %d\n", inumber, nextino); 313 if (inumber >= lastinum) { 314 readcnt++; 315 dblk = fsbtodb(&sblock, ino_to_fsba(&sblock, lastinum)); 316 if (readcnt % readpercg == 0) { 317 size = partialsize; 318 lastinum += partialcnt; 319 } else { 320 size = inobufsize; 321 lastinum += fullcnt; 322 } 323 (void)bread(fsreadfd, inodebuf, dblk, size); 324 nextinop = inodebuf; 325 } 326 dp = (union dinode *)nextinop; 327 if (sblock.fs_magic == FS_UFS1_MAGIC) 328 nextinop += sizeof(struct ufs1_dinode); 329 else 330 nextinop += sizeof(struct ufs2_dinode); 331 return (dp); 332 } 333 334 void 335 setinodebuf(ino_t inum) 336 { 337 338 startinum = 0; 339 nextino = inum; 340 lastinum = inum; 341 readcnt = 0; 342 if (inodebuf != NULL) 343 return; 344 inobufsize = blkroundup(&sblock, INOBUFSIZE); 345 if (sblock.fs_magic == FS_UFS1_MAGIC) 346 fullcnt = inobufsize / sizeof(struct ufs1_dinode); 347 else 348 fullcnt = inobufsize / sizeof(struct ufs2_dinode); 349 readpercg = sblock.fs_ipg / fullcnt; 350 partialcnt = sblock.fs_ipg % fullcnt; 351 if (sblock.fs_magic == FS_UFS1_MAGIC) 352 partialsize = partialcnt * sizeof(struct ufs1_dinode); 353 else 354 partialsize = partialcnt * sizeof(struct ufs2_dinode); 355 if (partialcnt != 0) { 356 readpercg++; 357 } else { 358 partialcnt = fullcnt; 359 partialsize = inobufsize; 360 } 361 if (inodebuf == NULL && 362 (inodebuf = malloc((unsigned)inobufsize)) == NULL) 363 errexit("Cannot allocate space for inode buffer\n"); 364 } 365 366 void 367 freeinodebuf(void) 368 { 369 370 if (inodebuf != NULL) 371 free(inodebuf); 372 inodebuf = NULL; 373 } 374 375 /* 376 * Routines to maintain information about directory inodes. 377 * This is built during the first pass and used during the 378 * second and third passes. 379 * 380 * Enter inodes into the cache. 381 */ 382 void 383 cacheino(union dinode *dp, ino_t inumber) 384 { 385 struct inoinfo *inp; 386 struct inoinfo **inpp, **newinpsort; 387 unsigned int blks; 388 long newlistmax; 389 int i; 390 391 blks = howmany(DIP(dp, di_size), sblock.fs_bsize); 392 if (blks > NDADDR) 393 blks = NDADDR + NIADDR; 394 inp = malloc(sizeof(*inp) + (blks ? blks - 1 : 0) * sizeof(daddr64_t)); 395 if (inp == NULL) 396 errexit("cannot allocate memory for inode cache\n"); 397 inpp = &inphead[inumber % numdirs]; 398 inp->i_nexthash = *inpp; 399 *inpp = inp; 400 inp->i_child = inp->i_sibling = 0; 401 if (inumber == ROOTINO) 402 inp->i_parent = ROOTINO; 403 else 404 inp->i_parent = 0; 405 inp->i_dotdot = 0; 406 inp->i_number = inumber; 407 inp->i_isize = DIP(dp, di_size); 408 inp->i_numblks = blks; 409 for (i = 0; i < (blks < NDADDR ? blks : NDADDR); i++) 410 inp->i_blks[i] = DIP(dp, di_db[i]); 411 if (blks > NDADDR) 412 for (i = 0; i < NIADDR; i++) 413 inp->i_blks[NDADDR + i] = DIP(dp, di_ib[i]); 414 if (inplast == listmax) { 415 newlistmax = listmax + 100; 416 newinpsort = realloc(inpsort, 417 (unsigned)newlistmax * sizeof(struct inoinfo *)); 418 if (newinpsort == NULL) 419 errexit("cannot increase directory list"); 420 inpsort = newinpsort; 421 listmax = newlistmax; 422 } 423 inpsort[inplast++] = inp; 424 } 425 426 /* 427 * Look up an inode cache structure. 428 */ 429 struct inoinfo * 430 getinoinfo(ino_t inumber) 431 { 432 struct inoinfo *inp; 433 434 for (inp = inphead[inumber % numdirs]; inp; inp = inp->i_nexthash) { 435 if (inp->i_number != inumber) 436 continue; 437 return (inp); 438 } 439 errexit("cannot find inode %d\n", inumber); 440 return (NULL); 441 } 442 443 /* 444 * Clean up all the inode cache structure. 445 */ 446 void 447 inocleanup(void) 448 { 449 struct inoinfo **inpp; 450 451 if (inphead == NULL) 452 return; 453 for (inpp = &inpsort[inplast - 1]; inpp >= inpsort; inpp--) 454 free(*inpp); 455 free(inphead); 456 free(inpsort); 457 inphead = inpsort = NULL; 458 } 459 460 void 461 inodirty(void) 462 { 463 dirty(pbp); 464 } 465 466 void 467 clri(struct inodesc *idesc, char *type, int flag) 468 { 469 union dinode *dp; 470 471 dp = ginode(idesc->id_number); 472 if (flag == 1) { 473 pwarn("%s %s", type, 474 (DIP(dp, di_mode) & IFMT) == IFDIR ? "DIR" : "FILE"); 475 pinode(idesc->id_number); 476 } 477 if (preen || reply("CLEAR") == 1) { 478 if (preen) 479 printf(" (CLEARED)\n"); 480 n_files--; 481 (void)ckinode(dp, idesc); 482 clearinode(dp); 483 SET_ISTATE(idesc->id_number, USTATE); 484 inodirty(); 485 } 486 } 487 488 int 489 findname(struct inodesc *idesc) 490 { 491 struct direct *dirp = idesc->id_dirp; 492 493 if (dirp->d_ino != idesc->id_parent) 494 return (KEEPON); 495 memcpy(idesc->id_name, dirp->d_name, (size_t)dirp->d_namlen + 1); 496 return (STOP|FOUND); 497 } 498 499 int 500 findino(struct inodesc *idesc) 501 { 502 struct direct *dirp = idesc->id_dirp; 503 504 if (dirp->d_ino == 0) 505 return (KEEPON); 506 if (strcmp(dirp->d_name, idesc->id_name) == 0 && 507 dirp->d_ino >= ROOTINO && dirp->d_ino <= maxino) { 508 idesc->id_parent = dirp->d_ino; 509 return (STOP|FOUND); 510 } 511 return (KEEPON); 512 } 513 514 void 515 pinode(ino_t ino) 516 { 517 union dinode *dp; 518 char *p; 519 struct passwd *pw; 520 time_t t; 521 522 printf(" I=%u ", ino); 523 if (ino < ROOTINO || ino > maxino) 524 return; 525 dp = ginode(ino); 526 printf(" OWNER="); 527 #ifndef SMALL 528 if ((pw = getpwuid(DIP(dp, di_uid))) != 0) 529 printf("%s ", pw->pw_name); 530 else 531 #endif 532 printf("%u ", (unsigned)DIP(dp, di_uid)); 533 printf("MODE=%o\n", DIP(dp, di_mode)); 534 if (preen) 535 printf("%s: ", cdevname()); 536 printf("SIZE=%llu ", (unsigned long long)DIP(dp, di_size)); 537 t = DIP(dp, di_mtime); 538 p = ctime(&t); 539 printf("MTIME=%12.12s %4.4s ", &p[4], &p[20]); 540 } 541 542 void 543 blkerror(ino_t ino, char *type, daddr64_t blk) 544 { 545 546 pfatal("%lld %s I=%u", blk, type, ino); 547 printf("\n"); 548 switch (GET_ISTATE(ino)) { 549 550 case FSTATE: 551 SET_ISTATE(ino, FCLEAR); 552 return; 553 554 case DSTATE: 555 SET_ISTATE(ino, DCLEAR); 556 return; 557 558 case FCLEAR: 559 case DCLEAR: 560 return; 561 562 default: 563 errexit("BAD STATE %d TO BLKERR\n", GET_ISTATE(ino)); 564 /* NOTREACHED */ 565 } 566 } 567 568 /* 569 * allocate an unused inode 570 */ 571 ino_t 572 allocino(ino_t request, int type) 573 { 574 ino_t ino; 575 union dinode *dp; 576 struct cg *cgp = &cgrp; 577 int cg; 578 time_t t; 579 struct inostat *info; 580 581 if (request == 0) 582 request = ROOTINO; 583 else if (GET_ISTATE(request) != USTATE) 584 return (0); 585 for (ino = request; ino < maxino; ino++) 586 if (GET_ISTATE(ino) == USTATE) 587 break; 588 if (ino == maxino) 589 return (0); 590 cg = ino_to_cg(&sblock, ino); 591 /* If necessary, extend the inoinfo array. grow exponentially */ 592 if ((ino % sblock.fs_ipg) >= (uint64_t)inostathead[cg].il_numalloced) { 593 unsigned long newalloced, i; 594 newalloced = MIN(sblock.fs_ipg, 595 MAX(2 * inostathead[cg].il_numalloced, 10)); 596 info = calloc(newalloced, sizeof(struct inostat)); 597 if (info == NULL) { 598 pwarn("cannot alloc %lu bytes to extend inoinfo\n", 599 sizeof(struct inostat) * newalloced); 600 return 0; 601 } 602 memmove(info, inostathead[cg].il_stat, 603 inostathead[cg].il_numalloced * sizeof(*info)); 604 for (i = inostathead[cg].il_numalloced; i < newalloced; i++) { 605 info[i].ino_state = USTATE; 606 } 607 if (inostathead[cg].il_numalloced) 608 free(inostathead[cg].il_stat); 609 inostathead[cg].il_stat = info; 610 inostathead[cg].il_numalloced = newalloced; 611 info = inoinfo(ino); 612 } 613 getblk(&cgblk, cgtod(&sblock, cg), sblock.fs_cgsize); 614 if (!cg_chkmagic(cgp)) 615 pfatal("CG %d: BAD MAGIC NUMBER\n", cg); 616 setbit(cg_inosused(cgp), ino % sblock.fs_ipg); 617 cgp->cg_cs.cs_nifree--; 618 619 switch (type & IFMT) { 620 case IFDIR: 621 SET_ISTATE(ino, DSTATE); 622 cgp->cg_cs.cs_ndir++; 623 break; 624 case IFREG: 625 case IFLNK: 626 SET_ISTATE(ino, FSTATE); 627 break; 628 default: 629 return (0); 630 } 631 cgdirty(); 632 dp = ginode(ino); 633 DIP_SET(dp, di_db[0], allocblk(1)); 634 if (DIP(dp, di_db[0]) == 0) { 635 SET_ISTATE(ino, USTATE); 636 return (0); 637 } 638 DIP_SET(dp, di_mode, type); 639 DIP_SET(dp, di_uid, geteuid()); 640 DIP_SET(dp, di_gid, getegid()); 641 DIP_SET(dp, di_flags, 0); 642 (void)time(&t); 643 DIP_SET(dp, di_atime, t); 644 DIP_SET(dp, di_atimensec, 0); 645 DIP_SET(dp, di_mtime, t); 646 DIP_SET(dp, di_mtimensec, 0); 647 DIP_SET(dp, di_ctime, t); 648 DIP_SET(dp, di_ctimensec, 0); 649 DIP_SET(dp, di_size, sblock.fs_fsize); 650 DIP_SET(dp, di_blocks, btodb(sblock.fs_fsize)); 651 n_files++; 652 inodirty(); 653 SET_ITYPE(ino, IFTODT(type)); 654 return (ino); 655 } 656 657 /* 658 * deallocate an inode 659 */ 660 void 661 freeino(ino_t ino) 662 { 663 struct inodesc idesc; 664 union dinode *dp; 665 666 memset(&idesc, 0, sizeof(struct inodesc)); 667 idesc.id_type = ADDR; 668 idesc.id_func = pass4check; 669 idesc.id_number = ino; 670 dp = ginode(ino); 671 (void)ckinode(dp, &idesc); 672 clearinode(dp); 673 inodirty(); 674 SET_ISTATE(ino, USTATE); 675 n_files--; 676 } 677