[unix-history] / usr / src / sys / ufs / ffs / ufs_bmap.c

/*
 * Copyright (c) 1989, 1991, 1993
 *	The Regents of the University of California.  All rights reserved.
 *
 * %sccs.include.redist.c%
 *
 *	@(#)ufs_bmap.c	8.1 (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/trace.h>

#include <miscfs/specfs/specdev.h>

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

/*
 * 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
ufs_bmap(ap)
	struct vop_bmap_args /* {
		struct vnode *a_vp;
		daddr_t  a_bn;
		struct vnode **a_vpp;
		daddr_t *a_bnp;
		int *a_runp;
	} */ *ap;
{
	/*
	 * Check for underlying vnode requests and ensure that logical
	 * to physical mapping is requested.
	 */
	if (ap->a_vpp != NULL)
		*ap->a_vpp = VTOI(ap->a_vp)->i_devvp;
	if (ap->a_bnp == NULL)
		return (0);

	return (ufs_bmaparray(ap->a_vp, ap->a_bn, ap->a_bnp, NULL, NULL,
	    ap->a_runp));
}

/*
 * Indirect blocks are now on the vnode for the file.  They are given negative
 * logical block 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.
 *
 * ufs_bmaparray does the bmap conversion, and if requested returns the
 * array of logical blocks which must be traversed to get to a block.
 * Each entry contains the offset into that block that gets you to the
 * next block and the disk address of the block (if it is assigned).
 */

int
ufs_bmaparray(vp, bn, bnp, ap, nump, runp)
	struct vnode *vp;
	register daddr_t bn;
	daddr_t *bnp;
	struct indir *ap;
	int *nump;
	int *runp;
{
	register struct inode *ip;
	struct buf *bp;
	struct ufsmount *ump;
	struct mount *mp;
	struct vnode *devvp;
	struct indir a[NIADDR], *xap;
	daddr_t *bap, daddr;
	long metalbn;
	int bb, error, maxrun, num, off;
	struct vop_strategy_args vop_strategy_a;

	ip = VTOI(vp);
	mp = vp->v_mount;
	ump = VFSTOUFS(mp);
#ifdef DIAGNOSTIC
	if (ap != NULL && nump == NULL || ap == NULL && nump != NULL)
		panic("ufs_bmaparray: invalid arguments");
#endif

	if (runp) {
		/*
		 * XXX If MAXBSIZE is the largest transfer the disks can
		 * handle, we probably want maxrun to be 1 block less so
		 * that we don't create a block larger than the device
		 * can handle.
		 */
		*runp = 0;
		maxrun = MAXBSIZE / mp->mnt_stat.f_iosize - 1;
	}

	xap = ap == NULL ? a : ap;
	if (!nump)
		nump = &num;
	if (error = ufs_getlbns(vp, bn, xap, nump))
		return (error);

	num = *nump;
	if (num == 0) {
		*bnp = blkptrtodb(ump, ip->i_db[bn]);
		if (*bnp == 0)
			*bnp = -1;
		else if (runp)
			for (++bn; bn < NDADDR && *runp < maxrun &&
			    is_sequential(ump, ip->i_db[bn - 1], ip->i_db[bn]);
			    ++bn, ++*runp);
		return (0);
	}


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

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

	for (bp = NULL, ++xap; --num; ++xap) {
		/* 
		 * Exit the loop if there is no disk address assigned yet and
		 * the indirect block isn't in the cache, or if we were
		 * looking for an indirect block and we've found it.
		 */

		metalbn = xap->in_lbn;
		if (daddr == 0 && !incore(vp, metalbn) || metalbn == bn)
			break;
		/*
		 * If we get here, we've either got the block in the cache
		 * or we have a disk address for it, go fetch it.
		 */
		if (bp)
			brelse(bp);

		xap->in_exists = 1;
		bp = getblk(vp, metalbn, mp->mnt_stat.f_iosize, 0, 0);
		if (bp->b_flags & (B_DONE | B_DELWRI)) {
			trace(TR_BREADHIT, pack(vp, size), metalbn);
		}
#ifdef DIAGNOSTIC
		else if (!daddr)
			panic("ufs_bmaparry: indirect block not in cache");
#endif
		else {
			trace(TR_BREADMISS, pack(vp, size), metalbn);
			bp->b_blkno = blkptrtodb(ump, daddr);
			bp->b_flags |= B_READ;
			VOP_STRATEGY(bp);
			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 (num == 1 && daddr && runp)
			for (bn = xap->in_off + 1;
			    bn < MNINDIR(ump) && *runp < maxrun &&
			    is_sequential(ump, bp->b_un.b_daddr[bn - 1],
			    bp->b_un.b_daddr[bn]);
			    ++bn, ++*runp);
	}
	if (bp)
		brelse(bp);

	daddr = blkptrtodb(ump, daddr);
	*bnp = daddr == 0 ? -1 : 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
ufs_getlbns(vp, bn, ap, nump)
	struct vnode *vp;
	register daddr_t bn;
	struct indir *ap;
	int *nump;
{
	long metalbn, realbn;
	struct ufsmount *ump;
	int j, numlevels, off, sh;

	ump = VFSTOUFS(vp->v_mount);
	if (nump)
		*nump = 0;
	numlevels = 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;
	sh = 1;
	for (j = NIADDR; j > 0; j--) {
		sh *= MNINDIR(ump);
		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.
	 */
	++numlevels;
	ap->in_lbn = metalbn;
	ap->in_off = off = NIADDR - j;
	ap->in_exists = 0;
	ap++;
	for (; j <= NIADDR; j++) {
		/* If searching for a meta-data block, quit when found. */
		if (metalbn == realbn)
			break;

		sh /= MNINDIR(ump);
		off = (bn / sh) % MNINDIR(ump);

		++numlevels;
		ap->in_lbn = metalbn;
		ap->in_off = off;
		ap->in_exists = 0;
		++ap;

		metalbn -= -1 + off * sh;
	}
	if (nump)
		*nump = numlevels;
	return (0);
}
Commit	Line	Data
d886ada0	1	/*
ad0f93d2 KB	2	* Copyright (c) 1989, 1991, 1993
ad0f93d2 KB	3	* The Regents of the University of California. All rights reserved.
d886ada0 MS	4	*
	5	* %sccs.include.redist.c%
	6	*
ad0f93d2	7	* @(#)ufs_bmap.c 8.1 (Berkeley) %G%
d886ada0 MS	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/trace.h>
	17
	18	#include <miscfs/specfs/specdev.h>
	19
	20	#include <ufs/ufs/quota.h>
	21	#include <ufs/ufs/inode.h>
	22	#include <ufs/ufs/ufsmount.h>
	23	#include <ufs/ufs/ufs_extern.h>
	24
	25	/*
	26	* Bmap converts a the logical block number of a file to its physical block
	27	* number on the disk. The conversion is done by using the logical block
	28	* number to index into the array of block pointers described by the dinode.
	29	*/
	30	int
	31	ufs_bmap(ap)
	32	struct vop_bmap_args /* {
	33	struct vnode *a_vp;
	34	daddr_t a_bn;
	35	struct vnode **a_vpp;
	36	daddr_t *a_bnp;
	37	int *a_runp;
	38	} / ap;
	39	{
	40	/*
	41	* Check for underlying vnode requests and ensure that logical
	42	* to physical mapping is requested.
	43	*/
	44	if (ap->a_vpp != NULL)
	45	*ap->a_vpp = VTOI(ap->a_vp)->i_devvp;
	46	if (ap->a_bnp == NULL)
	47	return (0);
	48
	49	return (ufs_bmaparray(ap->a_vp, ap->a_bn, ap->a_bnp, NULL, NULL,
	50	ap->a_runp));
	51	}
	52
	53	/*
	54	* Indirect blocks are now on the vnode for the file. They are given negative
	55	* logical block numbers. Indirect blocks are addressed by the negative
	56	* address of the first data block to which they point. Double indirect blocks
	57	* are addressed by one less than the address of the first indirect block to
	58	* which they point. Triple indirect blocks are addressed by one less than
	59	* the address of the first double indirect block to which they point.
	60	*
	61	* ufs_bmaparray does the bmap conversion, and if requested returns the
	62	* array of logical blocks which must be traversed to get to a block.
	63	* Each entry contains the offset into that block that gets you to the
	64	* next block and the disk address of the block (if it is assigned).
	65	*/
	66
	67	int
	68	ufs_bmaparray(vp, bn, bnp, ap, nump, runp)
	69	struct vnode *vp;
	70	register daddr_t bn;
	71	daddr_t *bnp;
72	struct indir *ap;
73	int *nump;
74	int *runp;
75	{
76	register struct inode *ip;
77	struct buf *bp;
78	struct ufsmount *ump;
79	struct mount *mp;
80	struct vnode *devvp;
81	struct indir a[NIADDR], *xap;
82	daddr_t *bap, daddr;
83	long metalbn;
84	int bb, error, maxrun, num, off;
85	struct vop_strategy_args vop_strategy_a;
86
87	ip = VTOI(vp);
88	mp = vp->v_mount;
89	ump = VFSTOUFS(mp);
90	#ifdef DIAGNOSTIC
91	if (ap != NULL && nump == NULL \|\| ap == NULL && nump != NULL)
92	panic("ufs_bmaparray: invalid arguments");
93	#endif
94
95	if (runp) {
96	/*
97	* XXX If MAXBSIZE is the largest transfer the disks can
98	* handle, we probably want maxrun to be 1 block less so
99	* that we don't create a block larger than the device
100	* can handle.
101	*/
102	*runp = 0;
91124c44	103	maxrun = MAXBSIZE / mp->mnt_stat.f_iosize - 1;
d886ada0 MS	104	}
	105
	106	xap = ap == NULL ? a : ap;
	107	if (!nump)
	108	nump = &num;
	109	if (error = ufs_getlbns(vp, bn, xap, nump))
	110	return (error);
	111
	112	num = *nump;
	113	if (num == 0) {
	114	*bnp = blkptrtodb(ump, ip->i_db[bn]);
	115	if (*bnp == 0)
	116	*bnp = -1;
91124c44	117	else if (runp)
d886ada0 MS	118	for (++bn; bn < NDADDR && *runp < maxrun &&
	119	is_sequential(ump, ip->i_db[bn - 1], ip->i_db[bn]);
	120	++bn, ++*runp);
d886ada0 MS	121	return (0);
	122	}
	123
	124
	125	/* Get disk address out of indirect block array */
	126	daddr = ip->i_ib[xap->in_off];
	127
	128	/* Fetch through the indirect blocks. */
	129	devvp = VFSTOUFS(vp->v_mount)->um_devvp;
	130
	131	for (bp = NULL, ++xap; --num; ++xap) {
	132	/*
	133	* Exit the loop if there is no disk address assigned yet and
	134	* the indirect block isn't in the cache, or if we were
	135	* looking for an indirect block and we've found it.
	136	*/
	137
	138	metalbn = xap->in_lbn;
	139	if (daddr == 0 && !incore(vp, metalbn) \|\| metalbn == bn)
	140	break;
	141	/*
	142	* If we get here, we've either got the block in the cache
	143	* or we have a disk address for it, go fetch it.
	144	*/
	145	if (bp)
	146	brelse(bp);
	147
	148	xap->in_exists = 1;
103a3ab5	149	bp = getblk(vp, metalbn, mp->mnt_stat.f_iosize, 0, 0);
d886ada0 MS	150	if (bp->b_flags & (B_DONE \| B_DELWRI)) {
	151	trace(TR_BREADHIT, pack(vp, size), metalbn);
	152	}
	153	#ifdef DIAGNOSTIC
	154	else if (!daddr)
	155	panic("ufs_bmaparry: indirect block not in cache");
	156	#endif
	157	else {
	158	trace(TR_BREADMISS, pack(vp, size), metalbn);
	159	bp->b_blkno = blkptrtodb(ump, daddr);
	160	bp->b_flags \|= B_READ;
	161	VOP_STRATEGY(bp);
	162	curproc->p_stats->p_ru.ru_inblock++; /* XXX */
	163	if (error = biowait(bp)) {
	164	brelse(bp);
	165	return (error);
	166	}
	167	}
	168
	169	daddr = bp->b_un.b_daddr[xap->in_off];
91124c44	170	if (num == 1 && daddr && runp)
d886ada0 MS	171	for (bn = xap->in_off + 1;
	172	bn < MNINDIR(ump) && *runp < maxrun &&
	173	is_sequential(ump, bp->b_un.b_daddr[bn - 1],
	174	bp->b_un.b_daddr[bn]);
	175	++bn, ++*runp);
d886ada0 MS	176	}
	177	if (bp)
	178	brelse(bp);
	179
	180	daddr = blkptrtodb(ump, daddr);
	181	*bnp = daddr == 0 ? -1 : daddr;
	182	return (0);
	183	}
	184
	185	/*
	186	* Create an array of logical block number/offset pairs which represent the
	187	* path of indirect blocks required to access a data block. The first "pair"
	188	* contains the logical block number of the appropriate single, double or
	189	* triple indirect block and the offset into the inode indirect block array.
	190	* Note, the logical block number of the inode single/double/triple indirect
	191	* block appears twice in the array, once with the offset into the i_ib and
	192	* once with the offset into the page itself.
	193	*/
	194	int
	195	ufs_getlbns(vp, bn, ap, nump)
	196	struct vnode *vp;
	197	register daddr_t bn;
	198	struct indir *ap;
	199	int *nump;
	200	{
	201	long metalbn, realbn;
	202	struct ufsmount *ump;
	203	int j, numlevels, off, sh;
	204
	205	ump = VFSTOUFS(vp->v_mount);
	206	if (nump)
	207	*nump = 0;
	208	numlevels = 0;
	209	realbn = bn;
	210	if ((long)bn < 0)
	211	bn = -(long)bn;
	212
	213	/* The first NDADDR blocks are direct blocks. */
	214	if (bn < NDADDR)
	215	return (0);
	216
	217	/*
	218	* Determine the number of levels of indirection. After this loop
	219	* is done, sh indicates the number of data blocks possible at the
	220	* given level of indirection, and NIADDR - j is the number of levels
	221	* of indirection needed to locate the requested block.
	222	*/
	223	bn -= NDADDR;
	224	sh = 1;
	225	for (j = NIADDR; j > 0; j--) {
	226	sh *= MNINDIR(ump);
	227	if (bn < sh)
	228	break;
	229	bn -= sh;
	230	}
	231	if (j == 0)
	232	return (EFBIG);
	233
	234	/* Calculate the address of the first meta-block. */
	235	if (realbn >= 0)
	236	metalbn = -(realbn - bn + NIADDR - j);
	237	else
	238	metalbn = -(-realbn - bn + NIADDR - j);
	239
240	/*
241	* At each iteration, off is the offset into the bap array which is
242	* an array of disk addresses at the current level of indirection.
243	* The logical block number and the offset in that block are stored
244	* into the argument array.
245	*/
246	++numlevels;
247	ap->in_lbn = metalbn;
248	ap->in_off = off = NIADDR - j;
249	ap->in_exists = 0;
250	ap++;
251	for (; j <= NIADDR; j++) {
252	/* If searching for a meta-data block, quit when found. */
253	if (metalbn == realbn)
254	break;
255
256	sh /= MNINDIR(ump);
257	off = (bn / sh) % MNINDIR(ump);
258
259	++numlevels;
260	ap->in_lbn = metalbn;
261	ap->in_off = off;
262	ap->in_exists = 0;
263	++ap;
264
265	metalbn -= -1 + off * sh;
266	}
267	if (nump)
268	*nump = numlevels;
269	return (0);
270	}