usr/src/sys/ufs/lfs/lfs_balloc.c

/*
 * Copyright (c) 1989, 1991 Regents of the University of California.
 * All rights reserved.
 *
 * %sccs.include.redist.c%
 *
 *	@(#)lfs_balloc.c	7.29 (Berkeley) %G%
 */

#include <sys/param.h>
#include <sys/buf.h>
#include <sys/proc.h>
#include <sys/vnode.h>
#include <sys/mount.h>
#include <sys/resourcevar.h>
#include <sys/specdev.h>
#include <sys/trace.h>

#include <ufs/ufs/quota.h>
#include <ufs/ufs/inode.h>
#include <ufs/ufs/ufsmount.h>

#include <ufs/lfs/lfs.h>
#include <ufs/lfs/lfs_extern.h>

int lfs_getlbns __P((struct vnode *, daddr_t, INDIR *, int *));

/*
 * Bmap converts a the logical block number of a file to its physical block
 * number on the disk. The conversion is done by using the logical block
 * number to index into the array of block pointers described by the dinode.
 */
int
lfs_bmap (ap)
	struct vop_bmap_args *ap;
#define vp (ap->a_vp)
#define bn (ap->a_bn)
#define vpp (ap->a_vpp)
#define bnp (ap->a_bnp)
{
#ifdef VERBOSE
	printf("lfs_bmap\n");
#endif
	/*
	 * Check for underlying vnode requests and ensure that logical
	 * to physical mapping is requested.
	 */
	if (vpp != NULL)
		*vpp = VTOI(vp)->i_devvp;
	if (bnp == NULL)
		return (0);

	return (lfs_bmaparray(vp, bn, bnp, NULL, NULL));
}
#undef vp
#undef bn
#undef vpp
#undef bnp

/*
 * LFS has a different version of bmap from FFS because of a naming conflict.
 * In FFS, meta blocks are given real disk addresses at allocation time, and
 * are linked into the device vnode, using a logical block number which is
 * the same as the physical block number.  This can't be done by LFS because
 * blocks aren't given disk addresses until they're written, so there's no
 * way to distinguish the meta-data blocks for one file from any other file.
 * This means that meta-data blocks have to be on the vnode for the file so
 * they can be found, and have to have "names" different from the standard
 * data blocks.  To do this, we divide the name space into positive and
 * negative block numbers, and give the meta-data blocks negative logical
 * numbers.  Indirect blocks are addressed by the negative address of the
 * first data block to which they point.  Double indirect blocks are addressed
 * by one less than the address of the first indirect block to which they
 * point.  Triple indirect blocks are addressed by one less than the address
 * of the first double indirect block to which they point.
 */
int
lfs_bmaparray(vp, bn, bnp, ap, nump)
	struct vnode *vp;
	register daddr_t bn;
	daddr_t *bnp;
	INDIR *ap;
	int *nump;
{
	USES_VOP_STRATEGY;
	register struct inode *ip;
	struct buf *bp;
	struct lfs *fs;
	struct vnode *devvp;
	INDIR a[NIADDR], *xap;
	daddr_t *bap, daddr;
	long metalbn;
	int error, num, off;


	ip = VTOI(vp);
#ifdef VERBOSE
	printf("lfs_bmap: block number %d, inode %d\n", bn, ip->i_number);
#endif
#ifdef DIAGNOSTIC
	if (ap != NULL && nump == NULL || ap == NULL && nump != NULL)
		panic("lfs_bmaparray: invalid arguments");
#endif

	xap = ap == NULL ? a : ap;
	if (error = lfs_getlbns(vp, bn, xap, nump))
		return (error);

	num = *nump;

	if (num == 0) {
		*bnp = ip->i_db[bn];
		if (*bnp == 0)
			*bnp = UNASSIGNED;
		return (0);
	}


	/* Get disk address out of indirect block array */
	daddr = ip->i_ib[xap->in_off];

	/* Fetch through the indirect blocks. */
	fs = ip->i_lfs;
	devvp = VFSTOUFS(vp->v_mount)->um_devvp;

	for (bp = NULL, ++xap; daddr && --num; ++xap) {
		/* If looking for a meta-block, break out when we find it. */
		metalbn = xap->in_lbn;
		if (metalbn == bn)
			break;

		/*
		 * Read in the appropriate indirect block.  LFS can't do a
		 * bread because bread knows that FFS will hand it the device
		 * vnode, not the file vnode, so the b_dev and b_blkno would
		 * be wrong.
		 *
		 * XXX
		 * This REALLY needs to be fixed, at the very least it needs
		 * to be rethought when the buffer cache goes away.  When it's
		 * fixed, change lfs_bmaparray and lfs_getlbns to take an ip,
		 * not a vp.
		 */
		if (bp)
			brelse(bp);
		bp = getblk(vp, metalbn, fs->lfs_bsize);
		if (bp->b_flags & (B_DONE | B_DELWRI)) {
			trace(TR_BREADHIT, pack(vp, size), metalbn);
		} else {
			trace(TR_BREADMISS, pack(vp, size), metalbn);
			bp->b_blkno = daddr;
			bp->b_flags |= B_READ;
			bp->b_dev = devvp->v_rdev;
			/*
			 * Call a strategy VOP by hand.
			 */
			vop_strategy_a.a_desc = VDESC(vop_strategy);
			vop_strategy_a.a_bp=bp;
			VOCALL(devvp->v_op, VOFFSET(vop_strategy), \
			       &vop_strategy_a);
			curproc->p_stats->p_ru.ru_inblock++;	/* XXX */
			if (error = biowait(bp)) {
				brelse(bp);
				return (error);
			}
		}
		daddr = bp->b_un.b_daddr[xap->in_off];
	}
	if (bp)
		brelse(bp);

	*bnp = daddr == 0 ? UNASSIGNED : daddr;
	return (0);
}

/*
 * Create an array of logical block number/offset pairs which represent the
 * path of indirect blocks required to access a data block.  The first "pair"
 * contains the logical block number of the appropriate single, double or
 * triple indirect block and the offset into the inode indirect block array.
 * Note, the logical block number of the inode single/double/triple indirect
 * block appears twice in the array, once with the offset into the i_ib and
 * once with the offset into the page itself.
 */
int
lfs_getlbns(vp, bn, ap, nump)
	struct vnode *vp;
	register daddr_t bn;
	INDIR *ap;
	int *nump;
{
	struct lfs *fs;
	long metalbn, realbn;
	int j, off, sh;

#ifdef VERBOSE
	printf("lfs_getlbns: bn %d, inode %d\n", bn, VTOI(vp)->i_number);
#endif
	*nump = 0;
	realbn = bn;
	if ((long)bn < 0)
		bn = -(long)bn;

	/* The first NDADDR blocks are direct blocks. */
	if (bn < NDADDR)
		return (0);

	/*
	 * Determine the number of levels of indirection.  After this loop
	 * is done, sh indicates the number of data blocks possible at the
	 * given level of indirection, and NIADDR - j is the number of levels
	 * of indirection needed to locate the requested block.
	 */
	bn -= NDADDR;
	fs = VTOI(vp)->i_lfs;
	sh = 1;
	for (j = NIADDR; j > 0; j--) {
		sh *= NINDIR(fs);
		if (bn < sh)
			break;
		bn -= sh;
	}
	if (j == 0)
		return (EFBIG);

	/* Calculate the address of the first meta-block. */
	if (realbn >= 0)
		metalbn = -(realbn - bn + NIADDR - j);
	else
		metalbn = -(-realbn - bn + NIADDR - j);

	/*
	 * At each iteration, off is the offset into the bap array which is
	 * an array of disk addresses at the current level of indirection.
	 * The logical block number and the offset in that block are stored
	 * into the argument array.
	 */
	++*nump;
	ap->in_lbn = metalbn;
	ap->in_off = off = NIADDR - j;
	ap++;
	for (; j <= NIADDR; j++) {
		/* If searching for a meta-data block, quit when found. */
		if (metalbn == realbn)
			break;

		sh /= NINDIR(fs);
		off = (bn / sh) % NINDIR(fs);

		++*nump;
		ap->in_lbn = metalbn;
		ap->in_off = off;
		++ap;

		metalbn -= -1 + off * sh;
	}
	return (0);
}

int
lfs_balloc(vp, iosize, lbn, bpp)
	struct vnode *vp;
	u_long iosize;
	daddr_t lbn;
	struct buf **bpp;
{
	USES_VOP_BMAP;
	struct buf *bp;
	struct inode *ip;
	struct lfs *fs;
	daddr_t daddr;
	int error, newblock;

	ip = VTOI(vp);
	fs = ip->i_lfs;

	/*
	 * Three cases: it's a block beyond the end of file, it's a block in
	 * the file that may or may not have been assigned a disk address or
	 * we're writing an entire block.  Note, if the daddr is unassigned,
	 * the block might still have existed in the cache.  If it did, make
	 * sure we don't count it as a new block or zero out its contents.
	 */
	newblock = ip->i_size <= lbn << fs->lfs_bshift;
	if (!newblock && (error = VOP_BMAP(vp, lbn, NULL, &daddr)))
		return (error);

	if (newblock || daddr == UNASSIGNED || iosize == fs->lfs_bsize) {
		*bpp = bp = getblk(vp, lbn, fs->lfs_bsize);
		if (newblock ||
		    daddr == UNASSIGNED && !(bp->b_flags & B_CACHE)) {
			++ip->i_blocks;
			if (iosize != fs->lfs_bsize)
				clrbuf(bp);
		}
		return (0);
	}
	return (bread(vp, lbn, fs->lfs_bsize, NOCRED, bpp));

}
Commit	Line	Data
	1	/*
	2	* Copyright (c) 1989, 1991 Regents of the University of California.
	3	* All rights reserved.
	4	*
	5	* %sccs.include.redist.c%
	6	*
	7	* @(#)lfs_balloc.c 7.29 (Berkeley) %G%
	8	*/
	9
	10	#include <sys/param.h>
	11	#include <sys/buf.h>
	12	#include <sys/proc.h>
	13	#include <sys/vnode.h>
	14	#include <sys/mount.h>
	15	#include <sys/resourcevar.h>
	16	#include <sys/specdev.h>
	17	#include <sys/trace.h>
	18
	19	#include <ufs/ufs/quota.h>
	20	#include <ufs/ufs/inode.h>
	21	#include <ufs/ufs/ufsmount.h>
	22
	23	#include <ufs/lfs/lfs.h>
	24	#include <ufs/lfs/lfs_extern.h>
	25
	26	int lfs_getlbns __P((struct vnode , daddr_t, INDIR , int *));
	27
	28	/*
	29	* Bmap converts a the logical block number of a file to its physical block
	30	* number on the disk. The conversion is done by using the logical block
	31	* number to index into the array of block pointers described by the dinode.
	32	*/
	33	int
	34	lfs_bmap (ap)
	35	struct vop_bmap_args *ap;
	36	#define vp (ap->a_vp)
	37	#define bn (ap->a_bn)
	38	#define vpp (ap->a_vpp)
	39	#define bnp (ap->a_bnp)
	40	{
	41	#ifdef VERBOSE
	42	printf("lfs_bmap\n");
	43	#endif
	44	/*
	45	* Check for underlying vnode requests and ensure that logical
	46	* to physical mapping is requested.
	47	*/
	48	if (vpp != NULL)
	49	*vpp = VTOI(vp)->i_devvp;
	50	if (bnp == NULL)
	51	return (0);
	52
	53	return (lfs_bmaparray(vp, bn, bnp, NULL, NULL));
	54	}
	55	#undef vp
	56	#undef bn
	57	#undef vpp
	58	#undef bnp
	59
	60	/*
	61	* LFS has a different version of bmap from FFS because of a naming conflict.
	62	* In FFS, meta blocks are given real disk addresses at allocation time, and
	63	* are linked into the device vnode, using a logical block number which is
	64	* the same as the physical block number. This can't be done by LFS because
	65	* blocks aren't given disk addresses until they're written, so there's no
	66	* way to distinguish the meta-data blocks for one file from any other file.
	67	* This means that meta-data blocks have to be on the vnode for the file so
	68	* they can be found, and have to have "names" different from the standard
	69	* data blocks. To do this, we divide the name space into positive and
	70	* negative block numbers, and give the meta-data blocks negative logical
	71	* numbers. Indirect blocks are addressed by the negative address of the
	72	* first data block to which they point. Double indirect blocks are addressed
	73	* by one less than the address of the first indirect block to which they
	74	* point. Triple indirect blocks are addressed by one less than the address
	75	* of the first double indirect block to which they point.
	76	*/
	77	int
	78	lfs_bmaparray(vp, bn, bnp, ap, nump)
	79	struct vnode *vp;
	80	register daddr_t bn;
	81	daddr_t *bnp;
	82	INDIR *ap;
	83	int *nump;
	84	{
	85	USES_VOP_STRATEGY;
	86	register struct inode *ip;
	87	struct buf *bp;
	88	struct lfs *fs;
	89	struct vnode *devvp;
	90	INDIR a[NIADDR], *xap;
	91	daddr_t *bap, daddr;
	92	long metalbn;
	93	int error, num, off;
	94
	95
	96	ip = VTOI(vp);
	97	#ifdef VERBOSE
	98	printf("lfs_bmap: block number %d, inode %d\n", bn, ip->i_number);
	99	#endif
	100	#ifdef DIAGNOSTIC
	101	if (ap != NULL && nump == NULL \|\| ap == NULL && nump != NULL)
	102	panic("lfs_bmaparray: invalid arguments");
	103	#endif
	104
	105	xap = ap == NULL ? a : ap;
	106	if (error = lfs_getlbns(vp, bn, xap, nump))
	107	return (error);
	108
	109	num = *nump;
	110
	111	if (num == 0) {
	112	*bnp = ip->i_db[bn];
	113	if (*bnp == 0)
	114	*bnp = UNASSIGNED;
	115	return (0);
	116	}
	117
	118
	119	/* Get disk address out of indirect block array */
	120	daddr = ip->i_ib[xap->in_off];
	121
	122	/* Fetch through the indirect blocks. */
	123	fs = ip->i_lfs;
	124	devvp = VFSTOUFS(vp->v_mount)->um_devvp;
	125
	126	for (bp = NULL, ++xap; daddr && --num; ++xap) {
	127	/* If looking for a meta-block, break out when we find it. */
	128	metalbn = xap->in_lbn;
	129	if (metalbn == bn)
	130	break;
	131
	132	/*
	133	* Read in the appropriate indirect block. LFS can't do a
	134	* bread because bread knows that FFS will hand it the device
	135	* vnode, not the file vnode, so the b_dev and b_blkno would
	136	* be wrong.
	137	*
	138	* XXX
	139	* This REALLY needs to be fixed, at the very least it needs
	140	* to be rethought when the buffer cache goes away. When it's
	141	* fixed, change lfs_bmaparray and lfs_getlbns to take an ip,
	142	* not a vp.
	143	*/
	144	if (bp)
	145	brelse(bp);
	146	bp = getblk(vp, metalbn, fs->lfs_bsize);
	147	if (bp->b_flags & (B_DONE \| B_DELWRI)) {
	148	trace(TR_BREADHIT, pack(vp, size), metalbn);
	149	} else {
	150	trace(TR_BREADMISS, pack(vp, size), metalbn);
	151	bp->b_blkno = daddr;
	152	bp->b_flags \|= B_READ;
	153	bp->b_dev = devvp->v_rdev;
	154	/*
	155	* Call a strategy VOP by hand.
	156	*/
	157	vop_strategy_a.a_desc = VDESC(vop_strategy);
	158	vop_strategy_a.a_bp=bp;
	159	VOCALL(devvp->v_op, VOFFSET(vop_strategy), \
	160	&vop_strategy_a);
	161	curproc->p_stats->p_ru.ru_inblock++; /* XXX */
	162	if (error = biowait(bp)) {
	163	brelse(bp);
	164	return (error);
	165	}
	166	}
	167	daddr = bp->b_un.b_daddr[xap->in_off];
	168	}
	169	if (bp)
	170	brelse(bp);
	171
	172	*bnp = daddr == 0 ? UNASSIGNED : daddr;
	173	return (0);
	174	}
	175
	176	/*
	177	* Create an array of logical block number/offset pairs which represent the
	178	* path of indirect blocks required to access a data block. The first "pair"
	179	* contains the logical block number of the appropriate single, double or
	180	* triple indirect block and the offset into the inode indirect block array.
	181	* Note, the logical block number of the inode single/double/triple indirect
	182	* block appears twice in the array, once with the offset into the i_ib and
	183	* once with the offset into the page itself.
	184	*/
	185	int
	186	lfs_getlbns(vp, bn, ap, nump)
	187	struct vnode *vp;
	188	register daddr_t bn;
	189	INDIR *ap;
	190	int *nump;
	191	{
	192	struct lfs *fs;
	193	long metalbn, realbn;
	194	int j, off, sh;
	195
	196	#ifdef VERBOSE
	197	printf("lfs_getlbns: bn %d, inode %d\n", bn, VTOI(vp)->i_number);
	198	#endif
	199	*nump = 0;
	200	realbn = bn;
	201	if ((long)bn < 0)
	202	bn = -(long)bn;
	203
	204	/* The first NDADDR blocks are direct blocks. */
	205	if (bn < NDADDR)
	206	return (0);
	207
	208	/*
	209	* Determine the number of levels of indirection. After this loop
	210	* is done, sh indicates the number of data blocks possible at the
	211	* given level of indirection, and NIADDR - j is the number of levels
	212	* of indirection needed to locate the requested block.
	213	*/
	214	bn -= NDADDR;
	215	fs = VTOI(vp)->i_lfs;
	216	sh = 1;
	217	for (j = NIADDR; j > 0; j--) {
	218	sh *= NINDIR(fs);
	219	if (bn < sh)
	220	break;
	221	bn -= sh;
	222	}
	223	if (j == 0)
	224	return (EFBIG);
	225
	226	/* Calculate the address of the first meta-block. */
	227	if (realbn >= 0)
	228	metalbn = -(realbn - bn + NIADDR - j);
	229	else
	230	metalbn = -(-realbn - bn + NIADDR - j);
	231
	232	/*
	233	* At each iteration, off is the offset into the bap array which is
	234	* an array of disk addresses at the current level of indirection.
	235	* The logical block number and the offset in that block are stored
	236	* into the argument array.
	237	*/
	238	++*nump;
	239	ap->in_lbn = metalbn;
	240	ap->in_off = off = NIADDR - j;
	241	ap++;
	242	for (; j <= NIADDR; j++) {
	243	/* If searching for a meta-data block, quit when found. */
	244	if (metalbn == realbn)
	245	break;
	246
	247	sh /= NINDIR(fs);
	248	off = (bn / sh) % NINDIR(fs);
	249
	250	++*nump;
	251	ap->in_lbn = metalbn;
	252	ap->in_off = off;
	253	++ap;
	254
	255	metalbn -= -1 + off * sh;
	256	}
	257	return (0);
	258	}
	259
	260	int
	261	lfs_balloc(vp, iosize, lbn, bpp)
	262	struct vnode *vp;
	263	u_long iosize;
	264	daddr_t lbn;
	265	struct buf **bpp;
	266	{
	267	USES_VOP_BMAP;
	268	struct buf *bp;
	269	struct inode *ip;
	270	struct lfs *fs;
	271	daddr_t daddr;
	272	int error, newblock;
	273
	274	ip = VTOI(vp);
	275	fs = ip->i_lfs;
	276
	277	/*
	278	* Three cases: it's a block beyond the end of file, it's a block in
	279	* the file that may or may not have been assigned a disk address or
	280	* we're writing an entire block. Note, if the daddr is unassigned,
	281	* the block might still have existed in the cache. If it did, make
	282	* sure we don't count it as a new block or zero out its contents.
	283	*/
	284	newblock = ip->i_size <= lbn << fs->lfs_bshift;
	285	if (!newblock && (error = VOP_BMAP(vp, lbn, NULL, &daddr)))
	286	return (error);
	287
	288	if (newblock \|\| daddr == UNASSIGNED \|\| iosize == fs->lfs_bsize) {
	289	*bpp = bp = getblk(vp, lbn, fs->lfs_bsize);
	290	if (newblock \|\|
	291	daddr == UNASSIGNED && !(bp->b_flags & B_CACHE)) {
	292	++ip->i_blocks;
	293	if (iosize != fs->lfs_bsize)
	294	clrbuf(bp);
	295	}
	296	return (0);
	297	}
	298	return (bread(vp, lbn, fs->lfs_bsize, NOCRED, bpp));
	299
	300	}