sbin/fsck_ffs/inode.c

   1 /*-
   2  * SPDX-License-Identifier: BSD-3-Clause
   3  *
   4  * Copyright (c) 1980, 1986, 1993
   5  *      The Regents of the University of California.  All rights reserved.
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  * 1. Redistributions of source code must retain the above copyright
  11  *    notice, this list of conditions and the following disclaimer.
  12  * 2. Redistributions in binary form must reproduce the above copyright
  13  *    notice, this list of conditions and the following disclaimer in the
  14  *    documentation and/or other materials provided with the distribution.
  15  * 3. Neither the name of the University nor the names of its contributors
  16  *    may be used to endorse or promote products derived from this software
  17  *    without specific prior written permission.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  20  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  22  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  23  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  25  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  26  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  27  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  28  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  29  * SUCH DAMAGE.
  30  */
  31
  32 #if 0
  33 #ifndef lint
  34 static const char sccsid[] = "@(#)inode.c       8.8 (Berkeley) 4/28/95";
  35 #endif /* not lint */
  36 #endif
  37 #include <sys/cdefs.h>
  38 __FBSDID("$FreeBSD$");
  39
  40 #include <sys/param.h>
  41 #include <sys/stat.h>
  42 #include <sys/stdint.h>
  43 #include <sys/sysctl.h>
  44
  45 #include <ufs/ufs/dinode.h>
  46 #include <ufs/ufs/dir.h>
  47 #include <ufs/ffs/fs.h>
  48
  49 #include <err.h>
  50 #include <pwd.h>
  51 #include <string.h>
  52 #include <time.h>
  53 #include <libufs.h>
  54
  55 #include "fsck.h"
  56
  57 struct bufarea *icachebp;       /* inode cache buffer */
  58
  59 static int iblock(struct inodesc *, off_t isize, int type);
  60 static ufs2_daddr_t indir_blkatoff(ufs2_daddr_t, ino_t, ufs_lbn_t, ufs_lbn_t,
  61     struct bufarea **);
  62 static int snapclean(struct inodesc *idesc);
  63 static void chkcopyonwrite(struct fs *, ufs2_daddr_t,
  64     ufs2_daddr_t (*checkblkavail)(ufs2_daddr_t, long));
  65
  66 int
  67 ckinode(union dinode *dp, struct inodesc *idesc)
  68 {
  69         off_t remsize, sizepb;
  70         int i, offset, ret;
  71         struct inode ip;
  72         union dinode dino;
  73         ufs2_daddr_t ndb;
  74         mode_t mode;
  75         char pathbuf[MAXPATHLEN + 1];
  76
  77         if (idesc->id_fix != IGNORE)
  78                 idesc->id_fix = DONTKNOW;
  79         idesc->id_dp = dp;
  80         idesc->id_lbn = -1;
  81         idesc->id_lballoc = -1;
  82         idesc->id_level = 0;
  83         idesc->id_entryno = 0;
  84         idesc->id_filesize = DIP(dp, di_size);
  85         mode = DIP(dp, di_mode) & IFMT;
  86         if (mode == IFBLK || mode == IFCHR || (mode == IFLNK &&
  87             DIP(dp, di_size) < (unsigned)sblock.fs_maxsymlinklen))
  88                 return (KEEPON);
  89         if (sblock.fs_magic == FS_UFS1_MAGIC)
  90                 dino.dp1 = dp->dp1;
  91         else
  92                 dino.dp2 = dp->dp2;
  93         ndb = howmany(DIP(&dino, di_size), sblock.fs_bsize);
  94         for (i = 0; i < UFS_NDADDR; i++) {
  95                 idesc->id_lbn++;
  96                 if (--ndb == 0 &&
  97                     (offset = blkoff(&sblock, DIP(&dino, di_size))) != 0)
  98                         idesc->id_numfrags =
  99                                 numfrags(&sblock, fragroundup(&sblock, offset));
 100                 else
 101                         idesc->id_numfrags = sblock.fs_frag;
 102                 if (DIP(&dino, di_db[i]) == 0) {
 103                         if (idesc->id_type == DATA && ndb >= 0) {
 104                                 /* An empty block in a directory XXX */
 105                                 getpathname(pathbuf, idesc->id_number,
 106                                                 idesc->id_number);
 107                                 pfatal("DIRECTORY %s: CONTAINS EMPTY BLOCKS",
 108                                         pathbuf);
 109                                 if (reply("ADJUST LENGTH") == 1) {
 110                                         ginode(idesc->id_number, &ip);
 111                                         DIP_SET(ip.i_dp, di_size,
 112                                             i * sblock.fs_bsize);
 113                                         printf(
 114                                             "YOU MUST RERUN FSCK AFTERWARDS\n");
 115                                         rerun = 1;
 116                                         inodirty(&ip);
 117                                         irelse(&ip);
 118                                 }
 119                         }
 120                         continue;
 121                 }
 122                 idesc->id_blkno = DIP(&dino, di_db[i]);
 123                 if (idesc->id_type != DATA)
 124                         ret = (*idesc->id_func)(idesc);
 125                 else
 126                         ret = dirscan(idesc);
 127                 if (ret & STOP)
 128                         return (ret);
 129         }
 130         idesc->id_numfrags = sblock.fs_frag;
 131         remsize = DIP(&dino, di_size) - sblock.fs_bsize * UFS_NDADDR;
 132         sizepb = sblock.fs_bsize;
 133         for (i = 0; i < UFS_NIADDR; i++) {
 134                 sizepb *= NINDIR(&sblock);
 135                 idesc->id_level = i + 1;
 136                 if (DIP(&dino, di_ib[i])) {
 137                         idesc->id_blkno = DIP(&dino, di_ib[i]);
 138                         ret = iblock(idesc, remsize, BT_LEVEL1 + i);
 139                         if (ret & STOP)
 140                                 return (ret);
 141                 } else if (remsize > 0) {
 142                         idesc->id_lbn += sizepb / sblock.fs_bsize;
 143                         if (idesc->id_type == DATA) {
 144                                 /* An empty block in a directory XXX */
 145                                 getpathname(pathbuf, idesc->id_number,
 146                                                 idesc->id_number);
 147                                 pfatal("DIRECTORY %s: CONTAINS EMPTY BLOCKS",
 148                                         pathbuf);
 149                                 if (reply("ADJUST LENGTH") == 1) {
 150                                         ginode(idesc->id_number, &ip);
 151                                         DIP_SET(ip.i_dp, di_size,
 152                                             DIP(ip.i_dp, di_size) - remsize);
 153                                         remsize = 0;
 154                                         printf(
 155                                             "YOU MUST RERUN FSCK AFTERWARDS\n");
 156                                         rerun = 1;
 157                                         inodirty(&ip);
 158                                         irelse(&ip);
 159                                         break;
 160                                 }
 161                         }
 162                 }
 163                 remsize -= sizepb;
 164         }
 165         return (KEEPON);
 166 }
 167
 168 static int
 169 iblock(struct inodesc *idesc, off_t isize, int type)
 170 {
 171         struct inode ip;
 172         struct bufarea *bp;
 173         int i, n, (*func)(struct inodesc *), nif;
 174         off_t sizepb;
 175         char buf[BUFSIZ];
 176         char pathbuf[MAXPATHLEN + 1];
 177
 178         if (idesc->id_type != DATA) {
 179                 func = idesc->id_func;
 180                 if (((n = (*func)(idesc)) & KEEPON) == 0)
 181                         return (n);
 182         } else
 183                 func = dirscan;
 184         bp = getdatablk(idesc->id_blkno, sblock.fs_bsize, type);
 185         if (bp->b_errs != 0) {
 186                 brelse(bp);
 187                 return (SKIP);
 188         }
 189         idesc->id_bp = bp;
 190         idesc->id_level--;
 191         for (sizepb = sblock.fs_bsize, i = 0; i < idesc->id_level; i++)
 192                 sizepb *= NINDIR(&sblock);
 193         if (howmany(isize, sizepb) > NINDIR(&sblock))
 194                 nif = NINDIR(&sblock);
 195         else
 196                 nif = howmany(isize, sizepb);
 197         if (idesc->id_func == pass1check && nif < NINDIR(&sblock)) {
 198                 for (i = nif; i < NINDIR(&sblock); i++) {
 199                         if (IBLK(bp, i) == 0)
 200                                 continue;
 201                         (void)sprintf(buf, "PARTIALLY TRUNCATED INODE I=%lu",
 202                             (u_long)idesc->id_number);
 203                         if (preen) {
 204                                 pfatal("%s", buf);
 205                         } else if (dofix(idesc, buf)) {
 206                                 IBLK_SET(bp, i, 0);
 207                                 dirty(bp);
 208                         }
 209                 }
 210                 flush(fswritefd, bp);
 211         }
 212         for (i = 0; i < nif; i++) {
 213                 if (IBLK(bp, i)) {
 214                         idesc->id_blkno = IBLK(bp, i);
 215                         bp->b_index = i;
 216                         if (idesc->id_level == 0) {
 217                                 idesc->id_lbn++;
 218                                 n = (*func)(idesc);
 219                         } else {
 220                                 n = iblock(idesc, isize, type - 1);
 221                                 idesc->id_level++;
 222                         }
 223                         if (n & STOP) {
 224                                 brelse(bp);
 225                                 return (n);
 226                         }
 227                 } else {
 228                         idesc->id_lbn += sizepb / sblock.fs_bsize;
 229                         if (idesc->id_type == DATA && isize > 0) {
 230                                 /* An empty block in a directory XXX */
 231                                 getpathname(pathbuf, idesc->id_number,
 232                                                 idesc->id_number);
 233                                 pfatal("DIRECTORY %s: CONTAINS EMPTY BLOCKS",
 234                                         pathbuf);
 235                                 if (reply("ADJUST LENGTH") == 1) {
 236                                         ginode(idesc->id_number, &ip);
 237                                         DIP_SET(ip.i_dp, di_size,
 238                                             DIP(ip.i_dp, di_size) - isize);
 239                                         isize = 0;
 240                                         printf(
 241                                             "YOU MUST RERUN FSCK AFTERWARDS\n");
 242                                         rerun = 1;
 243                                         inodirty(&ip);
 244                                         brelse(bp);
 245                                         return(STOP);
 246                                 }
 247                         }
 248                 }
 249                 isize -= sizepb;
 250         }
 251         brelse(bp);
 252         return (KEEPON);
 253 }
 254
 255 /*
 256  * Finds the disk block address at the specified lbn within the inode
 257  * specified by dp.  This follows the whole tree and honors di_size and
 258  * di_extsize so it is a true test of reachability.  The lbn may be
 259  * negative if an extattr or indirect block is requested.
 260  */
 261 ufs2_daddr_t
 262 ino_blkatoff(union dinode *dp, ino_t ino, ufs_lbn_t lbn, int *frags,
 263     struct bufarea **bpp)
 264 {
 265         ufs_lbn_t tmpval;
 266         ufs_lbn_t cur;
 267         ufs_lbn_t next;
 268         int i;
 269
 270         *frags = 0;
 271         if (bpp != NULL)
 272                 *bpp = NULL;
 273         /*
 274          * Handle extattr blocks first.
 275          */
 276         if (lbn < 0 && lbn >= -UFS_NXADDR) {
 277                 lbn = -1 - lbn;
 278                 if (lbn > lblkno(&sblock, dp->dp2.di_extsize - 1))
 279                         return (0);
 280                 *frags = numfrags(&sblock,
 281                     sblksize(&sblock, dp->dp2.di_extsize, lbn));
 282                 return (dp->dp2.di_extb[lbn]);
 283         }
 284         /*
 285          * Now direct and indirect.
 286          */
 287         if (DIP(dp, di_mode) == IFLNK &&
 288             DIP(dp, di_size) < sblock.fs_maxsymlinklen)
 289                 return (0);
 290         if (lbn >= 0 && lbn < UFS_NDADDR) {
 291                 *frags = numfrags(&sblock,
 292                     sblksize(&sblock, DIP(dp, di_size), lbn));
 293                 return (DIP(dp, di_db[lbn]));
 294         }
 295         *frags = sblock.fs_frag;
 296
 297         for (i = 0, tmpval = NINDIR(&sblock), cur = UFS_NDADDR; i < UFS_NIADDR;
 298             i++, tmpval *= NINDIR(&sblock), cur = next) {
 299                 next = cur + tmpval;
 300                 if (lbn == -cur - i)
 301                         return (DIP(dp, di_ib[i]));
 302                 /*
 303                  * Determine whether the lbn in question is within this tree.
 304                  */
 305                 if (lbn < 0 && -lbn >= next)
 306                         continue;
 307                 if (lbn > 0 && lbn >= next)
 308                         continue;
 309                 if (DIP(dp, di_ib[i]) == 0)
 310                         return (0);
 311                 return (indir_blkatoff(DIP(dp, di_ib[i]), ino, -cur - i, lbn,
 312                     bpp));
 313         }
 314         pfatal("lbn %jd not in ino %ju\n", lbn, (uintmax_t)ino);
 315         return (0);
 316 }
 317
 318 /*
 319  * Fetch an indirect block to find the block at a given lbn.  The lbn
 320  * may be negative to fetch a specific indirect block pointer or positive
 321  * to fetch a specific block.
 322  */
 323 static ufs2_daddr_t
 324 indir_blkatoff(ufs2_daddr_t blk, ino_t ino, ufs_lbn_t cur, ufs_lbn_t lbn,
 325     struct bufarea **bpp)
 326 {
 327         struct bufarea *bp;
 328         ufs_lbn_t lbnadd;
 329         ufs_lbn_t base;
 330         int i, level;
 331
 332         level = lbn_level(cur);
 333         if (level == -1)
 334                 pfatal("Invalid indir lbn %jd in ino %ju\n",
 335                     lbn, (uintmax_t)ino);
 336         if (level == 0 && lbn < 0)
 337                 pfatal("Invalid lbn %jd in ino %ju\n",
 338                     lbn, (uintmax_t)ino);
 339         lbnadd = 1;
 340         base = -(cur + level);
 341         for (i = level; i > 0; i--)
 342                 lbnadd *= NINDIR(&sblock);
 343         if (lbn > 0)
 344                 i = (lbn - base) / lbnadd;
 345         else
 346                 i = (-lbn - base) / lbnadd;
 347         if (i < 0 || i >= NINDIR(&sblock)) {
 348                 pfatal("Invalid indirect index %d produced by lbn %jd "
 349                     "in ino %ju\n", i, lbn, (uintmax_t)ino);
 350                 return (0);
 351         }
 352         if (level == 0)
 353                 cur = base + (i * lbnadd);
 354         else
 355                 cur = -(base + (i * lbnadd)) - (level - 1);
 356         bp = getdatablk(blk, sblock.fs_bsize, BT_LEVEL1 + level);
 357         if (bp->b_errs != 0)
 358                 return (0);
 359         blk = IBLK(bp, i);
 360         bp->b_index = i;
 361         if (cur == lbn || blk == 0) {
 362                 if (bpp != NULL)
 363                         *bpp = bp;
 364                 else
 365                         brelse(bp);
 366                 return (blk);
 367         }
 368         brelse(bp);
 369         if (level == 0)
 370                 pfatal("Invalid lbn %jd at level 0 for ino %ju\n", lbn,
 371                     (uintmax_t)ino);
 372         return (indir_blkatoff(blk, ino, cur, lbn, bpp));
 373 }
 374
 375 /*
 376  * Check that a block in a legal block number.
 377  * Return 0 if in range, 1 if out of range.
 378  */
 379 int
 380 chkrange(ufs2_daddr_t blk, int cnt)
 381 {
 382         int c;
 383
 384         if (cnt <= 0 || blk <= 0 || blk >= maxfsblock ||
 385             cnt > maxfsblock - blk) {
 386                 if (debug)
 387                         printf("out of range: blk %ld, offset %i, size %d\n",
 388                             (long)blk, (int)fragnum(&sblock, blk), cnt);
 389                 return (1);
 390         }
 391         if (cnt > sblock.fs_frag ||
 392             fragnum(&sblock, blk) + cnt > sblock.fs_frag) {
 393                 if (debug)
 394                         printf("bad size: blk %ld, offset %i, size %d\n",
 395                             (long)blk, (int)fragnum(&sblock, blk), cnt);
 396                 return (1);
 397         }
 398         c = dtog(&sblock, blk);
 399         if (blk < cgdmin(&sblock, c)) {
 400                 if ((blk + cnt) > cgsblock(&sblock, c)) {
 401                         if (debug) {
 402                                 printf("blk %ld < cgdmin %ld;",
 403                                     (long)blk, (long)cgdmin(&sblock, c));
 404                                 printf(" blk + cnt %ld > cgsbase %ld\n",
 405                                     (long)(blk + cnt),
 406                                     (long)cgsblock(&sblock, c));
 407                         }
 408                         return (1);
 409                 }
 410         } else {
 411                 if ((blk + cnt) > cgbase(&sblock, c+1)) {
 412                         if (debug)  {
 413                                 printf("blk %ld >= cgdmin %ld;",
 414                                     (long)blk, (long)cgdmin(&sblock, c));
 415                                 printf(" blk + cnt %ld > sblock.fs_fpg %ld\n",
 416                                     (long)(blk + cnt), (long)sblock.fs_fpg);
 417                         }
 418                         return (1);
 419                 }
 420         }
 421         return (0);
 422 }
 423
 424 /*
 425  * General purpose interface for reading inodes.
 426  *
 427  * firstinum and lastinum track contents of getnextino() cache (below).
 428  */
 429 static ino_t firstinum, lastinum;
 430 static struct bufarea inobuf;
 431
 432 void
 433 ginode(ino_t inumber, struct inode *ip)
 434 {
 435         ufs2_daddr_t iblk;
 436
 437         if (inumber < UFS_ROOTINO || inumber > maxino)
 438                 errx(EEXIT, "bad inode number %ju to ginode",
 439                     (uintmax_t)inumber);
 440         ip->i_number = inumber;
 441         if (inumber >= firstinum && inumber < lastinum) {
 442                 /* contents in getnextino() cache */
 443                 ip->i_bp = &inobuf;
 444                 inobuf.b_refcnt++;
 445                 inobuf.b_index = firstinum;
 446         } else if (icachebp != NULL &&
 447             inumber >= icachebp->b_index &&
 448             inumber < icachebp->b_index + INOPB(&sblock)) {
 449                 /* take an additional reference for the returned inode */
 450                 icachebp->b_refcnt++;
 451                 ip->i_bp = icachebp;
 452         } else {
 453                 iblk = ino_to_fsba(&sblock, inumber);
 454                 /* release our cache-hold reference on old icachebp */
 455                 if (icachebp != NULL)
 456                         brelse(icachebp);
 457                 icachebp = getdatablk(iblk, sblock.fs_bsize, BT_INODES);
 458                 if (icachebp->b_errs != 0) {
 459                         icachebp = NULL;
 460                         ip->i_bp = NULL;
 461                         ip->i_dp = &zino;
 462                         return;
 463                 }
 464                 /* take a cache-hold reference on new icachebp */
 465                 icachebp->b_refcnt++;
 466                 icachebp->b_index = rounddown(inumber, INOPB(&sblock));
 467                 ip->i_bp = icachebp;
 468         }
 469         if (sblock.fs_magic == FS_UFS1_MAGIC) {
 470                 ip->i_dp = (union dinode *)
 471                     &ip->i_bp->b_un.b_dinode1[inumber - ip->i_bp->b_index];
 472                 return;
 473         }
 474         ip->i_dp = (union dinode *)
 475             &ip->i_bp->b_un.b_dinode2[inumber - ip->i_bp->b_index];
 476         if (ffs_verify_dinode_ckhash(&sblock, (struct ufs2_dinode *)ip->i_dp)) {
 477                 pwarn("INODE CHECK-HASH FAILED");
 478                 prtinode(ip);
 479                 if (preen || reply("FIX") != 0) {
 480                         if (preen)
 481                                 printf(" (FIXED)\n");
 482                         ffs_update_dinode_ckhash(&sblock,
 483                             (struct ufs2_dinode *)ip->i_dp);
 484                         inodirty(ip);
 485                 }
 486         }
 487 }
 488
 489 /*
 490  * Release a held inode.
 491  */
 492 void
 493 irelse(struct inode *ip)
 494 {
 495
 496         /* Check for failed inode read */
 497         if (ip->i_bp == NULL)
 498                 return;
 499         if (ip->i_bp->b_refcnt <= 0)
 500                 pfatal("irelse: releasing unreferenced ino %ju\n",
 501                     (uintmax_t) ip->i_number);
 502         brelse(ip->i_bp);
 503 }
 504
 505 /*
 506  * Special purpose version of ginode used to optimize first pass
 507  * over all the inodes in numerical order.
 508  */
 509 static ino_t nextinum, lastvalidinum;
 510 static long readcount, readpercg, fullcnt, inobufsize, partialcnt, partialsize;
 511
 512 union dinode *
 513 getnextinode(ino_t inumber, int rebuiltcg)
 514 {
 515         int j;
 516         long size;
 517         mode_t mode;
 518         ufs2_daddr_t ndb, blk;
 519         union dinode *dp;
 520         struct inode ip;
 521         static caddr_t nextinop;
 522
 523         if (inumber != nextinum++ || inumber > lastvalidinum)
 524                 errx(EEXIT, "bad inode number %ju to nextinode",
 525                     (uintmax_t)inumber);
 526         if (inumber >= lastinum) {
 527                 readcount++;
 528                 firstinum = lastinum;
 529                 blk = ino_to_fsba(&sblock, lastinum);
 530                 if (readcount % readpercg == 0) {
 531                         size = partialsize;
 532                         lastinum += partialcnt;
 533                 } else {
 534                         size = inobufsize;
 535                         lastinum += fullcnt;
 536                 }
 537                 /*
 538                  * Flush old contents in case they have been updated.
 539                  * If getblk encounters an error, it will already have zeroed
 540                  * out the buffer, so we do not need to do so here.
 541                  */
 542                 if (inobuf.b_refcnt != 0)
 543                         pfatal("Non-zero getnextinode() ref count %d\n",
 544                             inobuf.b_refcnt);
 545                 flush(fswritefd, &inobuf);
 546                 getblk(&inobuf, blk, size);
 547                 nextinop = inobuf.b_un.b_buf;
 548         }
 549         dp = (union dinode *)nextinop;
 550         if (sblock.fs_magic == FS_UFS1_MAGIC)
 551                 nextinop += sizeof(struct ufs1_dinode);
 552         else
 553                 nextinop += sizeof(struct ufs2_dinode);
 554         if ((ckhashadd & CK_INODE) != 0) {
 555                 ffs_update_dinode_ckhash(&sblock, (struct ufs2_dinode *)dp);
 556                 dirty(&inobuf);
 557         }
 558         if (ffs_verify_dinode_ckhash(&sblock, (struct ufs2_dinode *)dp) != 0) {
 559                 pwarn("INODE CHECK-HASH FAILED");
 560                 ip.i_bp = NULL;
 561                 ip.i_dp = dp;
 562                 ip.i_number = inumber;
 563                 prtinode(&ip);
 564                 if (preen || reply("FIX") != 0) {
 565                         if (preen)
 566                                 printf(" (FIXED)\n");
 567                         ffs_update_dinode_ckhash(&sblock,
 568                             (struct ufs2_dinode *)dp);
 569                         dirty(&inobuf);
 570                 }
 571         }
 572         if (rebuiltcg && (char *)dp == inobuf.b_un.b_buf) {
 573                 /*
 574                  * Try to determine if we have reached the end of the
 575                  * allocated inodes.
 576                  */
 577                 mode = DIP(dp, di_mode) & IFMT;
 578                 if (mode == 0) {
 579                         if (memcmp(dp->dp2.di_db, zino.dp2.di_db,
 580                                 UFS_NDADDR * sizeof(ufs2_daddr_t)) ||
 581                               memcmp(dp->dp2.di_ib, zino.dp2.di_ib,
 582                                 UFS_NIADDR * sizeof(ufs2_daddr_t)) ||
 583                               dp->dp2.di_mode || dp->dp2.di_size)
 584                                 return (NULL);
 585                         return (dp);
 586                 }
 587                 if (!ftypeok(dp))
 588                         return (NULL);
 589                 ndb = howmany(DIP(dp, di_size), sblock.fs_bsize);
 590                 if (ndb < 0)
 591                         return (NULL);
 592                 if (mode == IFBLK || mode == IFCHR)
 593                         ndb++;
 594                 if (mode == IFLNK) {
 595                         /*
 596                          * Fake ndb value so direct/indirect block checks below
 597                          * will detect any garbage after symlink string.
 598                          */
 599                         if (DIP(dp, di_size) < (off_t)sblock.fs_maxsymlinklen) {
 600                                 ndb = howmany(DIP(dp, di_size),
 601                                     sizeof(ufs2_daddr_t));
 602                                 if (ndb > UFS_NDADDR) {
 603                                         j = ndb - UFS_NDADDR;
 604                                         for (ndb = 1; j > 1; j--)
 605                                                 ndb *= NINDIR(&sblock);
 606                                         ndb += UFS_NDADDR;
 607                                 }
 608                         }
 609                 }
 610                 for (j = ndb; ndb < UFS_NDADDR && j < UFS_NDADDR; j++)
 611                         if (DIP(dp, di_db[j]) != 0)
 612                                 return (NULL);
 613                 for (j = 0, ndb -= UFS_NDADDR; ndb > 0; j++)
 614                         ndb /= NINDIR(&sblock);
 615                 for (; j < UFS_NIADDR; j++)
 616                         if (DIP(dp, di_ib[j]) != 0)
 617                                 return (NULL);
 618         }
 619         return (dp);
 620 }
 621
 622 void
 623 setinodebuf(int cg, ino_t inosused)
 624 {
 625         ino_t inum;
 626
 627         inum = cg * sblock.fs_ipg;
 628         lastvalidinum = inum + inosused - 1;
 629         nextinum = inum;
 630         lastinum = inum;
 631         readcount = 0;
 632         /* Flush old contents in case they have been updated */
 633         flush(fswritefd, &inobuf);
 634         inobuf.b_bno = 0;
 635         if (inobuf.b_un.b_buf == NULL) {
 636                 inobufsize = blkroundup(&sblock,
 637                     MAX(INOBUFSIZE, sblock.fs_bsize));
 638                 initbarea(&inobuf, BT_INODES);
 639                 if ((inobuf.b_un.b_buf = Malloc((unsigned)inobufsize)) == NULL)
 640                         errx(EEXIT, "cannot allocate space for inode buffer");
 641         }
 642         fullcnt = inobufsize / ((sblock.fs_magic == FS_UFS1_MAGIC) ?
 643             sizeof(struct ufs1_dinode) : sizeof(struct ufs2_dinode));
 644         readpercg = inosused / fullcnt;
 645         partialcnt = inosused % fullcnt;
 646         partialsize = fragroundup(&sblock,
 647             partialcnt * ((sblock.fs_magic == FS_UFS1_MAGIC) ?
 648             sizeof(struct ufs1_dinode) : sizeof(struct ufs2_dinode)));
 649         if (partialcnt != 0) {
 650                 readpercg++;
 651         } else {
 652                 partialcnt = fullcnt;
 653                 partialsize = inobufsize;
 654         }
 655 }
 656
 657 int
 658 freeblock(struct inodesc *idesc)
 659 {
 660         struct dups *dlp;
 661         struct bufarea *cgbp;
 662         struct cg *cgp;
 663         ufs2_daddr_t blkno;
 664         long size, nfrags;
 665
 666         blkno = idesc->id_blkno;
 667         if (idesc->id_type == SNAP) {
 668                 pfatal("clearing a snapshot dinode\n");
 669                 return (STOP);
 670         }
 671         size = lfragtosize(&sblock, idesc->id_numfrags);
 672         if (snapblkfree(&sblock, blkno, size, idesc->id_number,
 673             std_checkblkavail))
 674                 return (KEEPON);
 675         for (nfrags = idesc->id_numfrags; nfrags > 0; blkno++, nfrags--) {
 676                 if (chkrange(blkno, 1)) {
 677                         return (SKIP);
 678                 } else if (testbmap(blkno)) {
 679                         for (dlp = duplist; dlp; dlp = dlp->next) {
 680                                 if (dlp->dup != blkno)
 681                                         continue;
 682                                 dlp->dup = duplist->dup;
 683                                 dlp = duplist;
 684                                 duplist = duplist->next;
 685                                 free((char *)dlp);
 686                                 break;
 687                         }
 688                         if (dlp == NULL) {
 689                                 clrbmap(blkno);
 690                                 n_blks--;
 691                         }
 692                 }
 693         }
 694         /*
 695          * If all successfully returned, account for them.
 696          */
 697         if (nfrags == 0) {
 698                 cgbp = cglookup(dtog(&sblock, idesc->id_blkno));
 699                 cgp = cgbp->b_un.b_cg;
 700                 if (idesc->id_numfrags == sblock.fs_frag)
 701                         cgp->cg_cs.cs_nbfree++;
 702                 else
 703                         cgp->cg_cs.cs_nffree += idesc->id_numfrags;
 704                 cgdirty(cgbp);
 705         }
 706         return (KEEPON);
 707 }
 708
 709 /*
 710  * Prepare a snapshot file for being removed.
 711  */
 712 void
 713 snapremove(ino_t inum)
 714 {
 715         struct inodesc idesc;
 716         struct inode ip;
 717         int i;
 718
 719         for (i = 0; i < snapcnt; i++)
 720                 if (snaplist[i].i_number == inum)
 721                         break;
 722         if (i == snapcnt)
 723                 ginode(inum, &ip);
 724         else
 725                 ip = snaplist[i];
 726         if ((DIP(ip.i_dp, di_flags) & SF_SNAPSHOT) == 0) {
 727                 printf("snapremove: inode %jd is not a snapshot\n",
 728                     (intmax_t)inum);
 729                 if (i == snapcnt)
 730                         irelse(&ip);
 731                 return;
 732         }
 733         if (debug)
 734                 printf("snapremove: remove %sactive snapshot %jd\n",
 735                     i == snapcnt ? "in" : "", (intmax_t)inum);
 736         /*
 737          * If on active snapshot list, remove it.
 738          */
 739         if (i < snapcnt) {
 740                 for (i++; i < FSMAXSNAP; i++) {
 741                         if (sblock.fs_snapinum[i] == 0)
 742                                 break;
 743                         snaplist[i - 1] = snaplist[i];
 744                         sblock.fs_snapinum[i - 1] = sblock.fs_snapinum[i];
 745                 }
 746                 sblock.fs_snapinum[i - 1] = 0;
 747                 bzero(&snaplist[i - 1], sizeof(struct inode));
 748                 snapcnt--;
 749         }
 750         memset(&idesc, 0, sizeof(struct inodesc));
 751         idesc.id_type = SNAP;
 752         idesc.id_func = snapclean;
 753         idesc.id_number = inum;
 754         (void)ckinode(ip.i_dp, &idesc);
 755         DIP_SET(ip.i_dp, di_flags, DIP(ip.i_dp, di_flags) & ~SF_SNAPSHOT);
 756         inodirty(&ip);
 757         irelse(&ip);
 758 }
 759
 760 static int
 761 snapclean(struct inodesc *idesc)
 762 {
 763         ufs2_daddr_t blkno;
 764         struct bufarea *bp;
 765         union dinode *dp;
 766
 767         blkno = idesc->id_blkno;
 768         if (blkno == 0)
 769                 return (KEEPON);
 770
 771         dp = idesc->id_dp;
 772         if (blkno == BLK_NOCOPY || blkno == BLK_SNAP) {
 773                 if (idesc->id_lbn < UFS_NDADDR) {
 774                         DIP_SET(dp, di_db[idesc->id_lbn], 0);
 775                 } else {
 776                         bp = idesc->id_bp;
 777                         IBLK_SET(bp, bp->b_index, 0);
 778                         dirty(bp);
 779                 }
 780         }
 781         return (KEEPON);
 782 }
 783
 784 /*
 785  * Notification that a block is being freed. Return zero if the free
 786  * should be allowed to proceed. Return non-zero if the snapshot file
 787  * wants to claim the block. The block will be claimed if it is an
 788  * uncopied part of one of the snapshots. It will be freed if it is
 789  * either a BLK_NOCOPY or has already been copied in all of the snapshots.
 790  * If a fragment is being freed, then all snapshots that care about
 791  * it must make a copy since a snapshot file can only claim full sized
 792  * blocks. Note that if more than one snapshot file maps the block,
 793  * we can pick one at random to claim it. Since none of the snapshots
 794  * can change, we are assurred that they will all see the same unmodified
 795  * image. When deleting a snapshot file (see ino_trunc above), we
 796  * must push any of these claimed blocks to one of the other snapshots
 797  * that maps it. These claimed blocks are easily identified as they will
 798  * have a block number equal to their logical block number within the
 799  * snapshot. A copied block can never have this property because they
 800  * must always have been allocated from a BLK_NOCOPY location.
 801  */
 802 int
 803 snapblkfree(struct fs *fs, ufs2_daddr_t bno, long size, ino_t inum,
 804         ufs2_daddr_t (*checkblkavail)(ufs2_daddr_t blkno, long frags))
 805 {
 806         union dinode *dp;
 807         struct inode ip;
 808         struct bufarea *snapbp;
 809         ufs_lbn_t lbn;
 810         ufs2_daddr_t blkno, relblkno;
 811         int i, frags, claimedblk, copydone;
 812
 813         /* If no snapshots, nothing to do */
 814         if (snapcnt == 0)
 815                 return (0);
 816         if (debug)
 817                 printf("snapblkfree: in ino %jd free blkno %jd, size %jd\n",
 818                     (intmax_t)inum, (intmax_t)bno, (intmax_t)size);
 819         relblkno = blknum(fs, bno);
 820         lbn = fragstoblks(fs, relblkno);
 821         /* Direct blocks are always pre-copied */
 822         if (lbn < UFS_NDADDR)
 823                 return (0);
 824         copydone = 0;
 825         claimedblk = 0;
 826         for (i = 0; i < snapcnt; i++) {
 827                 /*
 828                  * Lookup block being freed.
 829                  */
 830                 ip = snaplist[i];
 831                 dp = ip.i_dp;
 832                 blkno = ino_blkatoff(dp, inum != 0 ? inum : ip.i_number,
 833                     lbn, &frags, &snapbp);
 834                 /*
 835                  * Check to see if block needs to be copied.
 836                  */
 837                 if (blkno == 0) {
 838                         /*
 839                          * A block that we map is being freed. If it has not
 840                          * been claimed yet, we will claim or copy it (below).
 841                          */
 842                         claimedblk = 1;
 843                 } else if (blkno == BLK_SNAP) {
 844                         /*
 845                          * No previous snapshot claimed the block,
 846                          * so it will be freed and become a BLK_NOCOPY
 847                          * (don't care) for us.
 848                          */
 849                         if (claimedblk)
 850                                 pfatal("snapblkfree: inconsistent block type");
 851                         IBLK_SET(snapbp, snapbp->b_index, BLK_NOCOPY);
 852                         dirty(snapbp);
 853                         brelse(snapbp);
 854                         continue;
 855                 } else /* BLK_NOCOPY or default */ {
 856                         /*
 857                          * If the snapshot has already copied the block
 858                          * (default), or does not care about the block,
 859                          * it is not needed.
 860                          */
 861                         brelse(snapbp);
 862                         continue;
 863                 }
 864                 /*
 865                  * If this is a full size block, we will just grab it
 866                  * and assign it to the snapshot inode. Otherwise we
 867                  * will proceed to copy it. See explanation for this
 868                  * routine as to why only a single snapshot needs to
 869                  * claim this block.
 870                  */
 871                 if (size == fs->fs_bsize) {
 872                         if (debug)
 873                                 printf("Grabonremove snapshot %ju lbn %jd "
 874                                     "from inum %ju\n", (intmax_t)ip.i_number,
 875                                     (intmax_t)lbn, (uintmax_t)inum);
 876                         IBLK_SET(snapbp, snapbp->b_index, relblkno);
 877                         dirty(snapbp);
 878                         brelse(snapbp);
 879                         DIP_SET(dp, di_blocks,
 880                             DIP(dp, di_blocks) + btodb(size));
 881                         inodirty(&ip);
 882                         return (1);
 883                 }
 884
 885                 /* First time through, read the contents of the old block. */
 886                 if (copydone == 0) {
 887                         copydone = 1;
 888                         if (blread(fsreadfd, copybuf, fsbtodb(fs, relblkno),
 889                             fs->fs_bsize) != 0) {
 890                                 pfatal("Could not read snapshot %ju block "
 891                                     "%jd\n", (intmax_t)ip.i_number,
 892                                     (intmax_t)relblkno);
 893                                 continue;
 894                         }
 895                 }
 896                 /*
 897                  * This allocation will never require any additional
 898                  * allocations for the snapshot inode.
 899                  */
 900                 blkno = allocblk(dtog(fs, relblkno), fs->fs_frag,
 901                     checkblkavail);
 902                 if (blkno == 0) {
 903                         pfatal("Could not allocate block for snapshot %ju\n",
 904                             (intmax_t)ip.i_number);
 905                         continue;
 906                 }
 907                 if (debug)
 908                         printf("Copyonremove: snapino %jd lbn %jd for inum %ju "
 909                             "size %ld new blkno %jd\n", (intmax_t)ip.i_number,
 910                             (intmax_t)lbn, (uintmax_t)inum, size,
 911                             (intmax_t)blkno);
 912                 blwrite(fswritefd, copybuf, fsbtodb(fs, blkno), fs->fs_bsize);
 913                 IBLK_SET(snapbp, snapbp->b_index, blkno);
 914                 dirty(snapbp);
 915                 brelse(snapbp);
 916                 DIP_SET(dp, di_blocks,
 917                     DIP(dp, di_blocks) + btodb(fs->fs_bsize));
 918                 inodirty(&ip);
 919         }
 920         return (0);
 921 }
 922
 923 /*
 924  * Notification that a block is being written. Return if the block
 925  * is part of a snapshot as snapshots never track other snapshots.
 926  * The block will be copied in all of the snapshots that are tracking
 927  * it and have not yet copied it. Some buffers may hold more than one
 928  * block. Here we need to check each block in the buffer.
 929  */
 930 void
 931 copyonwrite(struct fs *fs, struct bufarea *bp,
 932         ufs2_daddr_t (*checkblkavail)(ufs2_daddr_t blkno, long frags))
 933 {
 934         ufs2_daddr_t copyblkno;
 935         long i, numblks;
 936
 937         /* If no snapshots, nothing to do. */
 938         if (snapcnt == 0)
 939                 return;
 940         numblks = blkroundup(fs, bp->b_size) / fs->fs_bsize;
 941         if (debug)
 942                 prtbuf(bp, "copyonwrite: checking %jd block%s in buffer",
 943                     (intmax_t)numblks, numblks > 1 ? "s" : "");
 944         copyblkno = blknum(fs, dbtofsb(fs, bp->b_bno));
 945         for (i = 0; i < numblks; i++) {
 946                 chkcopyonwrite(fs, copyblkno, checkblkavail);
 947                 copyblkno += fs->fs_frag;
 948         }
 949 }
 950
 951 static void
 952 chkcopyonwrite(struct fs *fs, ufs2_daddr_t copyblkno,
 953         ufs2_daddr_t (*checkblkavail)(ufs2_daddr_t blkno, long frags))
 954 {
 955         struct inode ip;
 956         union dinode *dp;
 957         struct bufarea *snapbp;
 958         ufs2_daddr_t blkno;
 959         int i, frags, copydone;
 960         ufs_lbn_t lbn;
 961
 962         lbn = fragstoblks(fs, copyblkno);
 963         /* Direct blocks are always pre-copied */
 964         if (lbn < UFS_NDADDR)
 965                 return;
 966         copydone = 0;
 967         for (i = 0; i < snapcnt; i++) {
 968                 /*
 969                  * Lookup block being freed.
 970                  */
 971                 ip = snaplist[i];
 972                 dp = ip.i_dp;
 973                 blkno = ino_blkatoff(dp, ip.i_number, lbn, &frags, &snapbp);
 974                 /*
 975                  * Check to see if block needs to be copied.
 976                  */
 977                 if (blkno != 0) {
 978                         /*
 979                          * A block that we have already copied or don't track.
 980                          */
 981                         brelse(snapbp);
 982                         continue;
 983                 }
 984                 /* First time through, read the contents of the old block. */
 985                 if (copydone == 0) {
 986                         copydone = 1;
 987                         if (blread(fsreadfd, copybuf, fsbtodb(fs, copyblkno),
 988                             fs->fs_bsize) != 0) {
 989                                 pfatal("Could not read snapshot %ju block "
 990                                     "%jd\n", (intmax_t)ip.i_number,
 991                                     (intmax_t)copyblkno);
 992                                 continue;
 993                         }
 994                 }
 995                 /*
 996                  * This allocation will never require any additional
 997                  * allocations for the snapshot inode.
 998                  */
 999                 if ((blkno = allocblk(dtog(fs, copyblkno), fs->fs_frag,
1000                     checkblkavail)) == 0) {
1001                         pfatal("Could not allocate block for snapshot %ju\n",
1002                             (intmax_t)ip.i_number);
1003                         continue;
1004                 }
1005                 if (debug)
1006                         prtbuf(snapbp, "Copyonwrite: snapino %jd lbn %jd using "
1007                             "blkno %ju setting in buffer",
1008                             (intmax_t)ip.i_number, (intmax_t)lbn,
1009                             (intmax_t)blkno);
1010                 blwrite(fswritefd, copybuf, fsbtodb(fs, blkno), fs->fs_bsize);
1011                 IBLK_SET(snapbp, snapbp->b_index, blkno);
1012                 dirty(snapbp);
1013                 brelse(snapbp);
1014                 DIP_SET(dp, di_blocks,
1015                     DIP(dp, di_blocks) + btodb(fs->fs_bsize));
1016                 inodirty(&ip);
1017         }
1018         return;
1019 }
1020
1021 /*
1022  * Traverse an inode and check that its block count is correct
1023  * fixing it if necessary.
1024  */
1025 void
1026 check_blkcnt(struct inode *ip)
1027 {
1028         struct inodesc idesc;
1029         union dinode *dp;
1030         ufs2_daddr_t ndb;
1031         int j, ret, offset;
1032
1033         dp = ip->i_dp;
1034         memset(&idesc, 0, sizeof(struct inodesc));
1035         idesc.id_func = pass1check;
1036         idesc.id_number = ip->i_number;
1037         idesc.id_type = (DIP(dp, di_flags) & SF_SNAPSHOT) == 0 ? ADDR : SNAP;
1038         (void)ckinode(dp, &idesc);
1039         if (sblock.fs_magic == FS_UFS2_MAGIC && dp->dp2.di_extsize > 0) {
1040                 ndb = howmany(dp->dp2.di_extsize, sblock.fs_bsize);
1041                 for (j = 0; j < UFS_NXADDR; j++) {
1042                         if (--ndb == 0 &&
1043                             (offset = blkoff(&sblock, dp->dp2.di_extsize)) != 0)
1044                                 idesc.id_numfrags = numfrags(&sblock,
1045                                     fragroundup(&sblock, offset));
1046                         else
1047                                 idesc.id_numfrags = sblock.fs_frag;
1048                         if (dp->dp2.di_extb[j] == 0)
1049                                 continue;
1050                         idesc.id_blkno = dp->dp2.di_extb[j];
1051                         ret = (*idesc.id_func)(&idesc);
1052                         if (ret & STOP)
1053                                 break;
1054                 }
1055         }
1056         idesc.id_entryno *= btodb(sblock.fs_fsize);
1057         if (DIP(dp, di_blocks) != idesc.id_entryno) {
1058                 if (!(sujrecovery && preen)) {
1059                         pwarn("INCORRECT BLOCK COUNT I=%lu (%ju should be %ju)",
1060                             (u_long)idesc.id_number,
1061                             (uintmax_t)DIP(dp, di_blocks),
1062                             (uintmax_t)idesc.id_entryno);
1063                         if (preen)
1064                                 printf(" (CORRECTED)\n");
1065                         else if (reply("CORRECT") == 0)
1066                                 return;
1067                 }
1068                 if (bkgrdflag == 0) {
1069                         DIP_SET(dp, di_blocks, idesc.id_entryno);
1070                         inodirty(ip);
1071                 } else {
1072                         cmd.value = idesc.id_number;
1073                         cmd.size = idesc.id_entryno - DIP(dp, di_blocks);
1074                         if (debug)
1075                                 printf("adjblkcnt ino %ju amount %lld\n",
1076                                     (uintmax_t)cmd.value, (long long)cmd.size);
1077                         if (sysctl(adjblkcnt, MIBSIZE, 0, 0,
1078                             &cmd, sizeof cmd) == -1)
1079                                 rwerror("ADJUST INODE BLOCK COUNT", cmd.value);
1080                 }
1081         }
1082 }
1083
1084 void
1085 freeinodebuf(void)
1086 {
1087         struct bufarea *bp;
1088         int i;
1089
1090         /*
1091          * Flush old contents in case they have been updated.
1092          */
1093         flush(fswritefd, &inobuf);
1094         if (inobuf.b_un.b_buf != NULL)
1095                 free((char *)inobuf.b_un.b_buf);
1096         inobuf.b_un.b_buf = NULL;
1097         firstinum = lastinum = 0;
1098         /*
1099          * Reload the snapshot inodes in case any of them changed.
1100          */
1101         for (i = 0; i < snapcnt; i++) {
1102                 bp = snaplist[i].i_bp;
1103                 bp->b_errs = blread(fsreadfd, bp->b_un.b_buf, bp->b_bno,
1104                     bp->b_size);
1105         }
1106 }
1107
1108 /*
1109  * Routines to maintain information about directory inodes.
1110  * This is built during the first pass and used during the
1111  * second and third passes.
1112  *
1113  * Enter inodes into the cache.
1114  */
1115 struct inoinfo *
1116 cacheino(union dinode *dp, ino_t inumber)
1117 {
1118         struct inoinfo *inp;
1119         int i, blks;
1120
1121         if (getinoinfo(inumber) != NULL)
1122                 pfatal("cacheino: duplicate entry for ino %jd\n",
1123                     (intmax_t)inumber);
1124         if (howmany(DIP(dp, di_size), sblock.fs_bsize) > UFS_NDADDR)
1125                 blks = UFS_NDADDR + UFS_NIADDR;
1126         else if (DIP(dp, di_size) > 0)
1127                 blks = howmany(DIP(dp, di_size), sblock.fs_bsize);
1128         else
1129                 blks = 1;
1130         inp = (struct inoinfo *)
1131                 Malloc(sizeof(*inp) + (blks - 1) * sizeof(ufs2_daddr_t));
1132         if (inp == NULL)
1133                 errx(EEXIT, "cannot increase directory list");
1134         SLIST_INSERT_HEAD(&inphash[inumber % dirhash], inp, i_hash);
1135         inp->i_flags = 0;
1136         inp->i_parent = inumber == UFS_ROOTINO ? UFS_ROOTINO : (ino_t)0;
1137         inp->i_dotdot = (ino_t)0;
1138         inp->i_number = inumber;
1139         inp->i_isize = DIP(dp, di_size);
1140         inp->i_depth = DIP(dp, di_dirdepth);
1141         inp->i_numblks = blks;
1142         for (i = 0; i < MIN(blks, UFS_NDADDR); i++)
1143                 inp->i_blks[i] = DIP(dp, di_db[i]);
1144         if (blks > UFS_NDADDR)
1145                 for (i = 0; i < UFS_NIADDR; i++)
1146                         inp->i_blks[UFS_NDADDR + i] = DIP(dp, di_ib[i]);
1147         if (inplast == listmax) {
1148                 listmax += 100;
1149                 inpsort = (struct inoinfo **)reallocarray((char *)inpsort,
1150                     listmax, sizeof(struct inoinfo *));
1151                 if (inpsort == NULL)
1152                         errx(EEXIT, "cannot increase directory list");
1153         }
1154         inpsort[inplast++] = inp;
1155         return (inp);
1156 }
1157
1158 /*
1159  * Look up an inode cache structure.
1160  */
1161 struct inoinfo *
1162 getinoinfo(ino_t inumber)
1163 {
1164         struct inoinfo *inp;
1165
1166         SLIST_FOREACH(inp, &inphash[inumber % dirhash], i_hash) {
1167                 if (inp->i_number != inumber)
1168                         continue;
1169                 return (inp);
1170         }
1171         return (NULL);
1172 }
1173
1174 /*
1175  * Remove an entry from the inode cache and disk-order sorted list.
1176  * Return 0 on success and 1 on failure.
1177  */
1178 int
1179 removecachedino(ino_t inumber)
1180 {
1181         struct inoinfo *inp, **inpp;
1182         char *listtype;
1183
1184         listtype = "hash";
1185         SLIST_FOREACH(inp, &inphash[inumber % dirhash], i_hash) {
1186                 if (inp->i_number != inumber)
1187                         continue;
1188                 SLIST_REMOVE(&inphash[inumber % dirhash], inp, inoinfo, i_hash);
1189                 for (inpp = &inpsort[inplast - 1]; inpp >= inpsort; inpp--) {
1190                         if (*inpp != inp)
1191                                 continue;
1192                         *inpp = inpsort[inplast - 1];
1193                         inplast--;
1194                         free(inp);
1195                         return (0);
1196                 }
1197                 listtype = "sort";
1198                 break;
1199         }
1200         pfatal("removecachedino: entry for ino %jd not found on %s list\n",
1201             (intmax_t)inumber, listtype);
1202         return (1);
1203 }
1204
1205 /*
1206  * Clean up all the inode cache structure.
1207  */
1208 void
1209 inocleanup(void)
1210 {
1211         struct inoinfo **inpp;
1212
1213         if (inphash == NULL)
1214                 return;
1215         for (inpp = &inpsort[inplast - 1]; inpp >= inpsort; inpp--)
1216                 free((char *)(*inpp));
1217         free((char *)inphash);
1218         inphash = NULL;
1219         free((char *)inpsort);
1220         inpsort = NULL;
1221 }
1222
1223 void
1224 inodirty(struct inode *ip)
1225 {
1226
1227         if (sblock.fs_magic == FS_UFS2_MAGIC)
1228                 ffs_update_dinode_ckhash(&sblock,
1229                     (struct ufs2_dinode *)ip->i_dp);
1230         dirty(ip->i_bp);
1231 }
1232
1233 void
1234 clri(struct inodesc *idesc, const char *type, int flag)
1235 {
1236         union dinode *dp;
1237         struct inode ip;
1238
1239         ginode(idesc->id_number, &ip);
1240         dp = ip.i_dp;
1241         if (flag == 1) {
1242                 pwarn("%s %s", type,
1243                     (DIP(dp, di_mode) & IFMT) == IFDIR ? "DIR" : "FILE");
1244                 prtinode(&ip);
1245                 printf("\n");
1246         }
1247         if (preen || reply("CLEAR") == 1) {
1248                 if (preen)
1249                         printf(" (CLEARED)\n");
1250                 n_files--;
1251                 if (bkgrdflag == 0) {
1252                         if (idesc->id_type == SNAP) {
1253                                 snapremove(idesc->id_number);
1254                                 idesc->id_type = ADDR;
1255                         }
1256                         (void)ckinode(dp, idesc);
1257                         inoinfo(idesc->id_number)->ino_state = USTATE;
1258                         clearinode(dp);
1259                         inodirty(&ip);
1260                 } else {
1261                         cmd.value = idesc->id_number;
1262                         cmd.size = -DIP(dp, di_nlink);
1263                         if (debug)
1264                                 printf("adjrefcnt ino %ld amt %lld\n",
1265                                     (long)cmd.value, (long long)cmd.size);
1266                         if (sysctl(adjrefcnt, MIBSIZE, 0, 0,
1267                             &cmd, sizeof cmd) == -1)
1268                                 rwerror("ADJUST INODE", cmd.value);
1269                 }
1270         }
1271         irelse(&ip);
1272 }
1273
1274 int
1275 findname(struct inodesc *idesc)
1276 {
1277         struct direct *dirp = idesc->id_dirp;
1278
1279         if (dirp->d_ino != idesc->id_parent || idesc->id_entryno < 2) {
1280                 idesc->id_entryno++;
1281                 return (KEEPON);
1282         }
1283         memmove(idesc->id_name, dirp->d_name, (size_t)dirp->d_namlen + 1);
1284         return (STOP|FOUND);
1285 }
1286
1287 int
1288 findino(struct inodesc *idesc)
1289 {
1290         struct direct *dirp = idesc->id_dirp;
1291
1292         if (dirp->d_ino == 0)
1293                 return (KEEPON);
1294         if (strcmp(dirp->d_name, idesc->id_name) == 0 &&
1295             dirp->d_ino >= UFS_ROOTINO && dirp->d_ino <= maxino) {
1296                 idesc->id_parent = dirp->d_ino;
1297                 return (STOP|FOUND);
1298         }
1299         return (KEEPON);
1300 }
1301
1302 int
1303 clearentry(struct inodesc *idesc)
1304 {
1305         struct direct *dirp = idesc->id_dirp;
1306
1307         if (dirp->d_ino != idesc->id_parent || idesc->id_entryno < 2) {
1308                 idesc->id_entryno++;
1309                 return (KEEPON);
1310         }
1311         dirp->d_ino = 0;
1312         return (STOP|FOUND|ALTERED);
1313 }
1314
1315 void
1316 prtinode(struct inode *ip)
1317 {
1318         char *p;
1319         union dinode *dp;
1320         struct passwd *pw;
1321         time_t t;
1322
1323         dp = ip->i_dp;
1324         printf(" I=%lu ", (u_long)ip->i_number);
1325         if (ip->i_number < UFS_ROOTINO || ip->i_number > maxino)
1326                 return;
1327         printf(" OWNER=");
1328         if ((pw = getpwuid((int)DIP(dp, di_uid))) != NULL)
1329                 printf("%s ", pw->pw_name);
1330         else
1331                 printf("%u ", (unsigned)DIP(dp, di_uid));
1332         printf("MODE=%o\n", DIP(dp, di_mode));
1333         if (preen)
1334                 printf("%s: ", cdevname);
1335         printf("SIZE=%ju ", (uintmax_t)DIP(dp, di_size));
1336         t = DIP(dp, di_mtime);
1337         if ((p = ctime(&t)) != NULL)
1338                 printf("MTIME=%12.12s %4.4s ", &p[4], &p[20]);
1339 }
1340
1341 void
1342 blkerror(ino_t ino, const char *type, ufs2_daddr_t blk)
1343 {
1344
1345         pfatal("%jd %s I=%ju", (intmax_t)blk, type, (uintmax_t)ino);
1346         printf("\n");
1347         switch (inoinfo(ino)->ino_state) {
1348
1349         case FSTATE:
1350         case FZLINK:
1351                 inoinfo(ino)->ino_state = FCLEAR;
1352                 return;
1353
1354         case DSTATE:
1355         case DZLINK:
1356                 inoinfo(ino)->ino_state = DCLEAR;
1357                 return;
1358
1359         case FCLEAR:
1360         case DCLEAR:
1361                 return;
1362
1363         default:
1364                 errx(EEXIT, "BAD STATE %d TO BLKERR", inoinfo(ino)->ino_state);
1365                 /* NOTREACHED */
1366         }
1367 }
1368
1369 /*
1370  * allocate an unused inode
1371  */
1372 ino_t
1373 allocino(ino_t request, int type)
1374 {
1375         ino_t ino;
1376         struct inode ip;
1377         union dinode *dp;
1378         struct bufarea *cgbp;
1379         struct cg *cgp;
1380         int cg, anyino;
1381
1382         anyino = 0;
1383         if (request == 0) {
1384                 request = UFS_ROOTINO;
1385                 anyino = 1;
1386         } else if (inoinfo(request)->ino_state != USTATE)
1387                 return (0);
1388 retry:
1389         for (ino = request; ino < maxino; ino++)
1390                 if (inoinfo(ino)->ino_state == USTATE)
1391                         break;
1392         if (ino >= maxino)
1393                 return (0);
1394         cg = ino_to_cg(&sblock, ino);
1395         cgbp = cglookup(cg);
1396         cgp = cgbp->b_un.b_cg;
1397         if (!check_cgmagic(cg, cgbp)) {
1398                 if (anyino == 0)
1399                         return (0);
1400                 request = (cg + 1) * sblock.fs_ipg;
1401                 goto retry;
1402         }
1403         setbit(cg_inosused(cgp), ino % sblock.fs_ipg);
1404         cgp->cg_cs.cs_nifree--;
1405         switch (type & IFMT) {
1406         case IFDIR:
1407                 inoinfo(ino)->ino_state = DSTATE;
1408                 cgp->cg_cs.cs_ndir++;
1409                 break;
1410         case IFREG:
1411         case IFLNK:
1412                 inoinfo(ino)->ino_state = FSTATE;
1413                 break;
1414         default:
1415                 return (0);
1416         }
1417         cgdirty(cgbp);
1418         ginode(ino, &ip);
1419         dp = ip.i_dp;
1420         DIP_SET(dp, di_db[0], allocblk(ino_to_cg(&sblock, ino), (long)1,
1421             std_checkblkavail));
1422         if (DIP(dp, di_db[0]) == 0) {
1423                 inoinfo(ino)->ino_state = USTATE;
1424                 irelse(&ip);
1425                 return (0);
1426         }
1427         DIP_SET(dp, di_mode, type);
1428         DIP_SET(dp, di_flags, 0);
1429         DIP_SET(dp, di_atime, time(NULL));
1430         DIP_SET(dp, di_ctime, DIP(dp, di_atime));
1431         DIP_SET(dp, di_mtime, DIP(dp, di_ctime));
1432         DIP_SET(dp, di_mtimensec, 0);
1433         DIP_SET(dp, di_ctimensec, 0);
1434         DIP_SET(dp, di_atimensec, 0);
1435         DIP_SET(dp, di_size, sblock.fs_fsize);
1436         DIP_SET(dp, di_blocks, btodb(sblock.fs_fsize));
1437         n_files++;
1438         inodirty(&ip);
1439         irelse(&ip);
1440         inoinfo(ino)->ino_type = IFTODT(type);
1441         return (ino);
1442 }
1443
1444 /*
1445  * deallocate an inode
1446  */
1447 void
1448 freeino(ino_t ino)
1449 {
1450         struct inodesc idesc;
1451         union dinode *dp;
1452         struct inode ip;
1453
1454         memset(&idesc, 0, sizeof(struct inodesc));
1455         idesc.id_type = ADDR;
1456         idesc.id_func = freeblock;
1457         idesc.id_number = ino;
1458         ginode(ino, &ip);
1459         dp = ip.i_dp;
1460         (void)ckinode(dp, &idesc);
1461         clearinode(dp);
1462         inodirty(&ip);
1463         irelse(&ip);
1464         inoinfo(ino)->ino_state = USTATE;
1465         n_files--;
1466 }