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