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