Home | History | Annotate | Line # | Download | only in fsck_lfs
inode.c revision 1.5 
      1 /*	$NetBSD: inode.c,v 1.5 2000/05/16 04:55:59 perseant Exp $	*/
      2 
      3 /*
      4  * Copyright (c) 1997, 1998
      5  *      Konrad Schroder.  All rights reserved.
      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. All advertising materials mentioning features or use of this software
     18  *    must display the following acknowledgement:
     19  *	This product includes software developed by the University of
     20  *	California, Berkeley and its contributors.
     21  * 4. Neither the name of the University nor the names of its contributors
     22  *    may be used to endorse or promote products derived from this software
     23  *    without specific prior written permission.
     24  *
     25  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
     26  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
     27  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
     28  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
     29  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
     30  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
     31  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
     32  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
     33  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
     34  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
     35  * SUCH DAMAGE.
     36  */
     37 
     38 #include <sys/param.h>
     39 #include <sys/time.h>
     40 #include <ufs/ufs/dinode.h>
     41 #include <ufs/ufs/dir.h>
     42 #include <sys/mount.h> /* XXX */
     43 #include <ufs/lfs/lfs.h>
     44 #ifndef SMALL
     45 #include <pwd.h>
     46 #endif
     47 #include <stdio.h>
     48 #include <stdlib.h>
     49 #include <string.h>
     50 
     51 #include "fsck.h"
     52 #include "fsutil.h"
     53 #include "extern.h"
     54 
     55 extern SEGUSE *seg_table;
     56 extern daddr_t *din_table;
     57 
     58 static int iblock __P((struct inodesc *, long, u_int64_t));
     59 int blksreqd(struct lfs *, int);
     60 int lfs_maxino(void);
     61 SEGUSE *lfs_gseguse(int, struct bufarea **);
     62 /* static void dump_inoblk __P((struct lfs *, struct dinode *)); */
     63 
     64 /* stolen from lfs_inode.c */
     65 /* Search a block for a specific dinode. */
     66 struct dinode *
     67 lfs_difind(struct lfs *fs, ino_t ino, struct dinode *dip)
     68 {
     69     register int cnt;
     70 
     71     for(cnt=0;cnt<INOPB(fs);cnt++)
     72         if(dip[cnt].di_inumber == ino)
     73             return &(dip[cnt]);
     74     /* printf("lfs_difind: dinode %u not found\n", ino); */
     75     return NULL;
     76 }
     77 
     78 /*
     79  * Calculate the number of blocks required to be able to address data block
     80  * blkno (counting, of course, indirect blocks).  blkno must >=0.
     81  */
     82 int blksreqd(struct lfs *fs, int blkno)
     83 {
     84     long n = blkno;
     85 
     86     if(blkno < NDADDR)
     87         return blkno;
     88     n -= NDADDR;
     89     if(n < NINDIR(fs))
     90         return blkno + 1;
     91     n -= NINDIR(fs);
     92     if(n < NINDIR(fs)*NINDIR(fs))
     93         return blkno + 2 + n/NINDIR(fs) + 1;
     94     n -= NINDIR(fs)*NINDIR(fs);
     95     return blkno + 2 + NINDIR(fs) + n/(NINDIR(fs)*NINDIR(fs)) + 1;
     96 }
     97 
     98 #define BASE_SINDIR (NDADDR)
     99 #define BASE_DINDIR (NDADDR+NINDIR(fs))
    100 #define BASE_TINDIR (NDADDR+NINDIR(fs)+NINDIR(fs)*NINDIR(fs))
    101 
    102 #define D_UNITS (NINDIR(fs))
    103 #define T_UNITS (NINDIR(fs)*NINDIR(fs))
    104 
    105 ufs_daddr_t lfs_bmap(struct lfs *, struct dinode *, ufs_daddr_t);
    106 
    107 ufs_daddr_t lfs_bmap(struct lfs *fs, struct dinode *idinode, ufs_daddr_t lbn)
    108 {
    109 	ufs_daddr_t residue, up, off=0;
    110 	struct bufarea *bp;
    111 
    112 	if(lbn > 0 && lbn > (idinode->di_size-1)/dev_bsize) {
    113 		return UNASSIGNED;
    114 	}
    115 	/*
    116 	 * Indirect blocks: if it is a first-level indirect, pull its
    117 	 * address from the inode; otherwise, call ourselves to find the
    118 	 * address of the parent indirect block, and load that to find
    119 	 * the desired address.
    120 	 */
    121 	if(lbn < 0) {
    122 		lbn *= -1;
    123 		if(lbn == NDADDR) {
    124 			/* printf("lbn %d: single indir base\n", -lbn); */
    125 			return idinode->di_ib[0]; /* single indirect */
    126 		} else if(lbn == BASE_DINDIR+1) {
    127 			/* printf("lbn %d: double indir base\n", -lbn); */
    128 			return idinode->di_ib[1]; /* double indirect */
    129 		} else if(lbn == BASE_TINDIR+2) {
    130 			/* printf("lbn %d: triple indir base\n", -lbn); */
    131 			return idinode->di_ib[2]; /* triple indirect */
    132 		}
    133 
    134 		/*
    135 		 * Find the immediate parent. This is essentially finding the
    136 		 * residue of modulus, and then rounding accordingly.
    137 		 */
    138 		residue = (lbn-NDADDR) % NINDIR(fs);
    139 		if(residue == 1) {
    140 			/* Double indirect.  Parent is the triple. */
    141 			up = idinode->di_ib[2];
    142 			off = (lbn-2-BASE_TINDIR)/(NINDIR(fs)*NINDIR(fs));
    143 			if(up == UNASSIGNED || up == LFS_UNUSED_DADDR)
    144 				return UNASSIGNED;
    145 			/* printf("lbn %d: parent is the triple\n", -lbn); */
    146 			bp = getddblk(up,sblock.lfs_bsize);
    147 			bp->b_flags &= ~B_INUSE;
    148 			return ((daddr_t *)(bp->b_un.b_buf))[off];
    149 		} else /* residue == 0 */ {
    150 			/* Single indirect.  Two cases. */
    151 			if(lbn < BASE_TINDIR) {
    152 				/* Parent is the double, simple */
    153 				up = -(BASE_DINDIR) - 1;
    154 				off = (lbn-BASE_DINDIR) / D_UNITS;
    155 				/* printf("lbn %d: parent is %d/%d\n", -lbn, up,off); */
    156 			} else {
    157 				/* Ancestor is the triple, more complex */
    158 				up = ((lbn-BASE_TINDIR) / T_UNITS)
    159 					* T_UNITS + BASE_TINDIR + 1;
    160 				off = (lbn/D_UNITS) - (up/D_UNITS);
    161 				up = -up;
    162 				/* printf("lbn %d: parent is %d/%d\n", -lbn, up,off); */
    163 			}
    164 		}
    165 	} else {
    166 		/* Direct block.  Its parent must be a single indirect. */
    167 		if(lbn < NDADDR)
    168 			return idinode->di_db[lbn];
    169 		else {
    170 			/* Parent is an indirect block. */
    171 			up = -(((lbn-NDADDR) / D_UNITS) * D_UNITS + NDADDR);
    172 			off = (lbn-NDADDR) % D_UNITS;
    173 			/* printf("lbn %d: parent is %d/%d\n", lbn,up,off); */
    174 		}
    175 	}
    176 	up = lfs_bmap(fs,idinode,up);
    177 	if(up == UNASSIGNED || up == LFS_UNUSED_DADDR)
    178 		return UNASSIGNED;
    179 	bp = getddblk(up,sblock.lfs_bsize);
    180 	bp->b_flags &= ~B_INUSE;
    181 	return ((daddr_t *)(bp->b_un.b_buf))[off];
    182 }
    183 
    184 /*
    185  * This is kind of gross.  We use this to find the nth block
    186  * from a file whose inode has disk address idaddr.  In practice
    187  * we will only use this to find blocks of the ifile.
    188  */
    189 struct bufarea *
    190 getfileblk(struct lfs *fs, struct dinode *idinode, ino_t lbn)
    191 {
    192     struct bufarea *bp;
    193     ufs_daddr_t blkno;
    194     static struct bufarea empty;
    195     static char empty_buf[65536];
    196 
    197     empty.b_un.b_buf = &(empty_buf[0]);
    198 
    199     blkno = lfs_bmap(fs,idinode,lbn);
    200     if(blkno == UNASSIGNED || blkno == LFS_UNUSED_DADDR) {
    201 	    printf("Warning: ifile lbn %d unassigned!\n",lbn);
    202 	    return &empty;
    203     }
    204     bp = getddblk(blkno,sblock.lfs_bsize);
    205     return bp;
    206 }
    207 
    208 #if 0
    209 static struct dinode *gidinode(void)
    210 {
    211     static struct dinode *idinode;
    212 
    213     if(!idinode) {              /* only need to do this once */
    214         idinode = lfs_difind(&sblock,sblock.lfs_ifile,&ifblock);
    215     }
    216     return idinode;
    217 }
    218 #endif
    219 
    220 struct ifile *
    221 lfs_ientry(ino_t ino, struct bufarea **bpp)
    222 {
    223     struct ifile *ifp;
    224 
    225     *bpp = getfileblk(&sblock, lfs_ginode(LFS_IFILE_INUM),
    226 		      ino/sblock.lfs_ifpb + sblock.lfs_cleansz +
    227 		      sblock.lfs_segtabsz);
    228     if(*bpp)
    229     {
    230 	    ifp = (((struct ifile *)((*bpp)->b_un.b_buf)) +
    231 		   (ino%sblock.lfs_ifpb));
    232 	    return ifp;
    233     }
    234     else
    235 	    return NULL;
    236 }
    237 
    238 SEGUSE *
    239 lfs_gseguse(int segnum, struct bufarea **bpp)
    240 {
    241     int blkno;
    242 
    243     blkno = segnum/(sblock.lfs_bsize/sizeof(SEGUSE)) + sblock.lfs_cleansz;
    244     (*bpp) = getfileblk(&sblock,lfs_ginode(LFS_IFILE_INUM),blkno);
    245     return ((SEGUSE *)(*bpp)->b_un.b_buf) + segnum%(sblock.lfs_bsize/sizeof(SEGUSE));
    246 }
    247 
    248 daddr_t
    249 lfs_ino_daddr(ino_t inumber)
    250 {
    251 	daddr_t daddr;
    252 	IFILE *ifp;
    253 	struct bufarea *bp;
    254 
    255 	if(din_table[inumber]) {
    256 		daddr = din_table[inumber];
    257 	} else {
    258 		if(inumber == LFS_IFILE_INUM)
    259 			daddr = sblock.lfs_idaddr;
    260 		else {
    261 			ifp = lfs_ientry(inumber, &bp);
    262 			if(ifp==NULL) {
    263 				return NULL;
    264 			}
    265 			if(ifp->if_daddr == LFS_UNUSED_DADDR) {
    266 				bp->b_flags &= ~B_INUSE;
    267 				return NULL;
    268 			}
    269 
    270 			bp->b_flags &= ~B_INUSE;
    271 			daddr = ifp->if_daddr;
    272 		}
    273 
    274 		din_table[inumber] = daddr;
    275 		seg_table[datosn(&sblock,daddr)].su_nbytes += DINODE_SIZE;
    276 	}
    277 	return daddr;
    278 }
    279 
    280 struct dinode *
    281 lfs_ginode(ino_t inumber)
    282 {
    283     struct ifile *ifp;
    284     struct dinode *din;
    285     struct bufarea *bp;
    286     daddr_t daddr;
    287 
    288     if (inumber > maxino)
    289 	    errexit("bad inode number %d to lfs_ginode\n", inumber);
    290 
    291 #if 0
    292     if (inumber == LFS_IFILE_INUM) {
    293 	    daddr = sblock.lfs_idaddr;
    294 	    if(din_table[LFS_IFILE_INUM] == 0) {
    295 		    din_table[LFS_IFILE_INUM] = daddr;
    296 		    seg_table[datosn(&sblock,daddr)].su_nbytes += DINODE_SIZE;
    297 	    }
    298 	    return gidinode();
    299     }
    300 #endif
    301 
    302     daddr = lfs_ino_daddr(inumber);
    303     if(daddr == 0)
    304 	    return NULL;
    305 
    306     if(pbp)
    307 	    pbp->b_flags &= ~B_INUSE;
    308 
    309     pbp = getddblk(daddr,sblock.lfs_bsize);
    310     din=lfs_difind(&sblock, inumber, pbp->b_un.b_dinode);
    311 
    312     if(din == NULL) {
    313 	    pfatal("INODE %d NOT FOUND\n", inumber);
    314 	    if(reply("free")) {
    315 		    ifp = lfs_ientry(inumber, &bp);
    316 		    ifp->if_daddr = LFS_UNUSED_DADDR;
    317 		    ifp->if_nextfree = sblock.lfs_free;
    318 		    sblock.lfs_free = inumber;
    319 		    sbdirty();
    320 		    dirty(bp);
    321 		    bp->b_flags &= ~B_INUSE;
    322 	    }
    323     }
    324 
    325     return din;
    326 }
    327 
    328 /* imported from lfs_vfsops.c */
    329 int
    330 ino_to_fsba(struct lfs *fs, ino_t ino)
    331 {
    332     daddr_t daddr = LFS_UNUSED_DADDR;
    333     struct ifile *ifp;
    334     struct bufarea *bp;
    335 
    336     /* Translate the inode number to a disk address. */
    337     if (ino == LFS_IFILE_INUM)
    338         daddr = fs->lfs_idaddr;
    339     else {
    340         ifp = lfs_ientry(ino,&bp);
    341         if(ifp) {
    342             daddr = ifp->if_daddr;
    343         } else {
    344             pwarn("Can't locate inode #%ud\n",ino);
    345         }
    346 	bp->b_flags &= ~B_INUSE;
    347     }
    348     return daddr;
    349 }
    350 
    351 /*
    352  * Check validity of held (direct) blocks in an inode.
    353  */
    354 int
    355 ckinode(dp, idesc)
    356     struct dinode *dp;
    357     register struct inodesc *idesc;
    358 {
    359     register ufs_daddr_t *ap;
    360     long ret, n, ndb, offset;
    361     struct dinode dino;
    362     u_int64_t remsize, sizepb;
    363     mode_t mode;
    364     char pathbuf[MAXPATHLEN + 1];
    365 
    366     if (idesc->id_fix != IGNORE)
    367         idesc->id_fix = DONTKNOW;
    368     idesc->id_entryno = 0;
    369     idesc->id_filesize = dp->di_size;
    370     mode = dp->di_mode & IFMT;
    371     if (mode == IFBLK || mode == IFCHR
    372         || (mode == IFLNK &&
    373             (dp->di_size < sblock.lfs_maxsymlinklen ||
    374              (sblock.lfs_maxsymlinklen == 0 && dp->di_blocks == 0))))
    375         return (KEEPON);
    376     dino = *dp;
    377     ndb = howmany(dino.di_size, sblock.lfs_bsize);
    378 
    379     for (ap = &dino.di_db[0]; ap < &dino.di_db[NDADDR]; ap++) {
    380         if (--ndb == 0 && (offset = blkoff(&sblock, dino.di_size)) != 0) {
    381             idesc->id_numfrags =
    382                 numfrags(&sblock, fragroundup(&sblock, offset));
    383         } else
    384             idesc->id_numfrags = sblock.lfs_frag;
    385         if (*ap == 0) {
    386             if (idesc->id_type == DATA && ndb >= 0) {
    387                 /* An empty block in a directory XXX */
    388                 getpathname(pathbuf, idesc->id_number,
    389                             idesc->id_number);
    390                 pfatal("DIRECTORY %s: CONTAINS EMPTY BLOCKS",
    391                        pathbuf);
    392                 if (reply("ADJUST LENGTH") == 1) {
    393                     dp = ginode(idesc->id_number);
    394                     dp->di_size = (ap - &dino.di_db[0]) *
    395                         sblock.lfs_bsize;
    396                     printf(
    397                            "YOU MUST RERUN FSCK AFTERWARDS\n");
    398                     rerun = 1;
    399                     inodirty();
    400                 }
    401             }
    402             continue;
    403         }
    404         idesc->id_blkno = *ap;
    405         idesc->id_lblkno = ap - &dino.di_db[0];
    406         if (idesc->id_type == ADDR) {
    407             ret = (*idesc->id_func)(idesc);
    408         }
    409         else
    410             ret = dirscan(idesc);
    411 	idesc->id_lblkno = 0;
    412         if (ret & STOP)
    413             return (ret);
    414     }
    415     idesc->id_numfrags = sblock.lfs_frag;
    416     remsize = dino.di_size - sblock.lfs_bsize * NDADDR;
    417     sizepb = sblock.lfs_bsize;
    418     for (ap = &dino.di_ib[0], n = 1; n <= NIADDR; ap++, n++) {
    419         if (*ap) {
    420             idesc->id_blkno = *ap;
    421             ret = iblock(idesc, n, remsize);
    422             if (ret & STOP)
    423                 return (ret);
    424         } else {
    425             if (idesc->id_type == DATA && remsize > 0) {
    426                 /* An empty block in a directory XXX */
    427                 getpathname(pathbuf, idesc->id_number,
    428                             idesc->id_number);
    429                 pfatal("DIRECTORY %s: CONTAINS EMPTY BLOCKS",
    430                        pathbuf);
    431                 if (reply("ADJUST LENGTH") == 1) {
    432                     dp = ginode(idesc->id_number);
    433                     dp->di_size -= remsize;
    434                     remsize = 0;
    435                     printf(
    436                            "YOU MUST RERUN FSCK AFTERWARDS\n");
    437                     rerun = 1;
    438                     inodirty();
    439                     break;
    440                 }
    441             }
    442         }
    443         sizepb *= NINDIR(&sblock);
    444         remsize -= sizepb;
    445     }
    446     return (KEEPON);
    447 }
    448 
    449 static int
    450 iblock(idesc, ilevel, isize)
    451     struct inodesc *idesc;
    452     long ilevel;
    453     u_int64_t isize;
    454 {
    455     register daddr_t *ap;
    456     register daddr_t *aplim;
    457     register struct bufarea *bp;
    458     int i, n, (*func) __P((struct inodesc *)), nif;
    459     u_int64_t sizepb;
    460     char pathbuf[MAXPATHLEN + 1], buf[BUFSIZ];
    461     struct dinode *dp;
    462 
    463     if (idesc->id_type == ADDR) {
    464         func = idesc->id_func;
    465         n = (*func)(idesc);
    466         if ((n & KEEPON) == 0)
    467             return (n);
    468     } else
    469         func = dirscan;
    470     if (chkrange(idesc->id_blkno, idesc->id_numfrags))
    471         return (SKIP);
    472     bp = getddblk(idesc->id_blkno, sblock.lfs_bsize);
    473     ilevel--;
    474     for (sizepb = sblock.lfs_bsize, i = 0; i < ilevel; i++)
    475         sizepb *= NINDIR(&sblock);
    476     if (isize > sizepb * NINDIR(&sblock))
    477         nif = NINDIR(&sblock);
    478     else
    479         nif = howmany(isize, sizepb);
    480     if (idesc->id_func == pass1check && nif < NINDIR(&sblock)) {
    481         aplim = &bp->b_un.b_indir[NINDIR(&sblock)];
    482         for (ap = &bp->b_un.b_indir[nif]; ap < aplim; ap++) {
    483             if (*ap == 0)
    484                 continue;
    485             (void)sprintf(buf, "PARTIALLY TRUNCATED INODE I=%u",
    486                           idesc->id_number);
    487             if (dofix(idesc, buf)) {
    488                 *ap = 0;
    489                 dirty(bp);
    490             }
    491         }
    492         flush(fswritefd, bp);
    493     }
    494     aplim = &bp->b_un.b_indir[nif];
    495     for (ap = bp->b_un.b_indir; ap < aplim; ap++) {
    496         if (*ap) {
    497             idesc->id_blkno = *ap;
    498             if (ilevel == 0)
    499                 n = (*func)(idesc);
    500             else
    501                 n = iblock(idesc, ilevel, isize);
    502             if (n & STOP) {
    503                 bp->b_flags &= ~B_INUSE;
    504                 return (n);
    505             }
    506         } else {
    507             if (idesc->id_type == DATA && isize > 0) {
    508                 /* An empty block in a directory XXX */
    509                 getpathname(pathbuf, idesc->id_number,
    510                             idesc->id_number);
    511                 pfatal("DIRECTORY %s: CONTAINS EMPTY BLOCKS",
    512                        pathbuf);
    513                 if (reply("ADJUST LENGTH") == 1) {
    514                     dp = ginode(idesc->id_number);
    515                     dp->di_size -= isize;
    516                     isize = 0;
    517                     printf(
    518                            "YOU MUST RERUN FSCK AFTERWARDS\n");
    519                     rerun = 1;
    520                     inodirty();
    521                     bp->b_flags &= ~B_INUSE;
    522                     return(STOP);
    523                 }
    524             }
    525         }
    526         isize -= sizepb;
    527     }
    528     bp->b_flags &= ~B_INUSE;
    529     return (KEEPON);
    530 }
    531 
    532 /*
    533  * Check that a block in a legal block number.
    534  * Return 0 if in range, 1 if out of range.
    535  */
    536 int
    537 chkrange(blk, cnt)
    538     daddr_t blk;
    539     int cnt;
    540 {
    541     if (blk > fsbtodb(&sblock,maxfsblock)) {
    542         printf("daddr 0x%x too large\n", blk);
    543         return (1);
    544     }
    545     return (0);
    546 }
    547 
    548 /*
    549  * General purpose interface for reading inodes.
    550  */
    551 struct dinode *
    552 ginode(ino_t inumber)
    553 {
    554     return lfs_ginode(inumber);
    555 }
    556 
    557 /*
    558  * Routines to maintain information about directory inodes.
    559  * This is built during the first pass and used during the
    560  * second and third passes.
    561  *
    562  * Enter inodes into the cache.
    563  */
    564 void
    565 cacheino(dp, inumber)
    566     register struct dinode *dp;
    567     ino_t inumber;
    568 {
    569     register struct inoinfo *inp;
    570     struct inoinfo **inpp;
    571     unsigned int blks;
    572 
    573     blks = howmany(dp->di_size, sblock.lfs_bsize);
    574     if (blks > NDADDR)
    575         blks = NDADDR + NIADDR;
    576     inp = (struct inoinfo *)
    577         malloc(sizeof(*inp) + (blks - 1) * sizeof(daddr_t));
    578     if (inp == NULL)
    579         return;
    580     inpp = &inphead[inumber % numdirs];
    581     inp->i_nexthash = *inpp;
    582     *inpp = inp;
    583     inp->i_child = inp->i_sibling = inp->i_parentp = 0;
    584     if (inumber == ROOTINO)
    585         inp->i_parent = ROOTINO;
    586     else
    587         inp->i_parent = (ino_t)0;
    588     inp->i_dotdot = (ino_t)0;
    589     inp->i_number = inumber;
    590     inp->i_isize = dp->di_size;
    591     inp->i_numblks = blks * sizeof(daddr_t);
    592     memcpy(&inp->i_blks[0], &dp->di_db[0], (size_t)inp->i_numblks);
    593     if (inplast == listmax) {
    594         listmax += 100;
    595         inpsort = (struct inoinfo **)realloc((char *)inpsort,
    596                                              (unsigned)listmax * sizeof(struct inoinfo *));
    597         if (inpsort == NULL)
    598             errexit("cannot increase directory list");
    599     }
    600     inpsort[inplast++] = inp;
    601 }
    602 
    603 /*
    604  * Look up an inode cache structure.
    605  */
    606 struct inoinfo *
    607 getinoinfo(inumber)
    608     ino_t inumber;
    609 {
    610     register struct inoinfo *inp;
    611 
    612     for (inp = inphead[inumber % numdirs]; inp; inp = inp->i_nexthash) {
    613         if (inp->i_number != inumber)
    614             continue;
    615         return (inp);
    616     }
    617     errexit("cannot find inode %d\n", inumber);
    618     return ((struct inoinfo *)0);
    619 }
    620 
    621 /*
    622  * Clean up all the inode cache structure.
    623  */
    624 void
    625 inocleanup()
    626 {
    627     register struct inoinfo **inpp;
    628 
    629     if (inphead == NULL)
    630         return;
    631     for (inpp = &inpsort[inplast - 1]; inpp >= inpsort; inpp--)
    632         free((char *)(*inpp));
    633     free((char *)inphead);
    634     free((char *)inpsort);
    635     inphead = inpsort = NULL;
    636 }
    637 
    638 void
    639 inodirty()
    640 {
    641     dirty(pbp);
    642 }
    643 
    644 void
    645 clri(idesc, type, flag)
    646     register struct inodesc *idesc;
    647     char *type;
    648     int flag;
    649 {
    650     register struct dinode *dp;
    651     struct bufarea *bp;
    652     IFILE *ifp;
    653 
    654     dp = ginode(idesc->id_number);
    655     if (flag == 1) {
    656         pwarn("%s %s", type,
    657               (dp->di_mode & IFMT) == IFDIR ? "DIR" : "FILE");
    658         pinode(idesc->id_number);
    659     }
    660     if (preen || reply("CLEAR") == 1) {
    661         if (preen)
    662             printf(" (CLEARED)\n");
    663         n_files--;
    664         (void)ckinode(dp, idesc);
    665         clearinode(dp);
    666         statemap[idesc->id_number] = USTATE;
    667         inodirty();
    668 
    669 	/* Send cleared inode to the free list */
    670 
    671 	ifp = lfs_ientry(idesc->id_number, &bp);
    672 	ifp->if_daddr = LFS_UNUSED_DADDR;
    673 	ifp->if_nextfree = sblock.lfs_free;
    674 	sblock.lfs_free = idesc->id_number;
    675 	sbdirty();
    676 	dirty(bp);
    677 	bp->b_flags &= ~B_INUSE;
    678     }
    679 }
    680 
    681 int
    682 findname(idesc)
    683     struct inodesc *idesc;
    684 {
    685     register struct direct *dirp = idesc->id_dirp;
    686 
    687     if (dirp->d_ino != idesc->id_parent)
    688         return (KEEPON);
    689     memcpy(idesc->id_name, dirp->d_name, (size_t)dirp->d_namlen + 1);
    690     return (STOP|FOUND);
    691 }
    692 
    693 int
    694 findino(idesc)
    695     struct inodesc *idesc;
    696 {
    697     register struct direct *dirp = idesc->id_dirp;
    698 
    699     if (dirp->d_ino == 0)
    700         return (KEEPON);
    701     if (strcmp(dirp->d_name, idesc->id_name) == 0 &&
    702         dirp->d_ino >= ROOTINO && dirp->d_ino <= maxino) {
    703         idesc->id_parent = dirp->d_ino;
    704         return (STOP|FOUND);
    705     }
    706     return (KEEPON);
    707 }
    708 
    709 void
    710 pinode(ino)
    711     ino_t ino;
    712 {
    713     register struct dinode *dp;
    714     register char *p;
    715     struct passwd *pw;
    716     time_t t;
    717 
    718     printf(" I=%u ", ino);
    719     if (ino < ROOTINO || ino > maxino)
    720         return;
    721     dp = ginode(ino);
    722     if(dp) {
    723         printf(" OWNER=");
    724 #ifndef SMALL
    725         if ((pw = getpwuid((int)dp->di_uid)) != 0)
    726             printf("%s ", pw->pw_name);
    727         else
    728 #endif
    729             printf("%u ", (unsigned)dp->di_uid);
    730         printf("MODE=%o\n", dp->di_mode);
    731         if (preen)
    732             printf("%s: ", cdevname());
    733         printf("SIZE=%qu ", (unsigned long long)dp->di_size);
    734         t = dp->di_mtime;
    735         p = ctime(&t);
    736         printf("MTIME=%12.12s %4.4s ", &p[4], &p[20]);
    737     }
    738 }
    739 
    740 void
    741 blkerror(ino, type, blk)
    742     ino_t ino;
    743     char *type;
    744     daddr_t blk;
    745 {
    746 
    747     pfatal("%d %s I=%u", blk, type, ino);
    748     printf("\n");
    749     if(exitonfail)
    750         exit(1);
    751     switch (statemap[ino]) {
    752 
    753       case FSTATE:
    754         statemap[ino] = FCLEAR;
    755         return;
    756 
    757       case DSTATE:
    758         statemap[ino] = DCLEAR;
    759         return;
    760 
    761       case FCLEAR:
    762       case DCLEAR:
    763         return;
    764 
    765       default:
    766         errexit("BAD STATE %d TO BLKERR", statemap[ino]);
    767         /* NOTREACHED */
    768     }
    769 }
    770 
    771 /*
    772  * allocate an unused inode
    773  */
    774 ino_t
    775 allocino(request, type)
    776     ino_t request;
    777     int type;
    778 {
    779     register ino_t ino;
    780     register struct dinode *dp;
    781     time_t t;
    782 
    783     if (request == 0)
    784         request = ROOTINO;
    785     else if (statemap[request] != USTATE)
    786         return (0);
    787     for (ino = request; ino < maxino; ino++)
    788         if (statemap[ino] == USTATE)
    789             break;
    790     if (ino == maxino)
    791         return (0);
    792     switch (type & IFMT) {
    793       case IFDIR:
    794         statemap[ino] = DSTATE;
    795         break;
    796       case IFREG:
    797       case IFLNK:
    798         statemap[ino] = FSTATE;
    799         break;
    800       default:
    801         return (0);
    802     }
    803     dp = ginode(ino);
    804     dp->di_db[0] = allocblk((long)1);
    805     if (dp->di_db[0] == 0) {
    806         statemap[ino] = USTATE;
    807         return (0);
    808     }
    809     dp->di_mode = type;
    810     (void)time(&t);
    811     dp->di_atime = t;
    812     dp->di_mtime = dp->di_ctime = dp->di_atime;
    813     dp->di_size = sblock.lfs_fsize;
    814     dp->di_blocks = btodb(sblock.lfs_fsize);
    815     n_files++;
    816     inodirty();
    817     if (newinofmt)
    818         typemap[ino] = IFTODT(type);
    819     return (ino);
    820 }
    821 
    822 /*
    823  * deallocate an inode
    824  */
    825 void
    826 freeino(ino)
    827     ino_t ino;
    828 {
    829     struct inodesc idesc;
    830     struct dinode *dp;
    831 
    832     memset(&idesc, 0, sizeof(struct inodesc));
    833     idesc.id_type = ADDR;
    834     idesc.id_func = pass4check;
    835     idesc.id_number = ino;
    836     dp = ginode(ino);
    837     (void)ckinode(dp, &idesc);
    838     clearinode(dp);
    839     inodirty();
    840     statemap[ino] = USTATE;
    841 
    842     n_files--;
    843 }
    844