1/*-
2 * Copyright (c) 1989, 1991, 1993
3 *	The Regents of the University of California.  All rights reserved.
4 * (c) UNIX System Laboratories, Inc.
5 * All or some portions of this file are derived from material licensed
6 * to the University of California by American Telephone and Telegraph
7 * Co. or Unix System Laboratories, Inc. and are reproduced herein with
8 * the permission of UNIX System Laboratories, Inc.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 * 1. Redistributions of source code must retain the above copyright
14 *    notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 *    notice, this list of conditions and the following disclaimer in the
17 *    documentation and/or other materials provided with the distribution.
18 * 4. Neither the name of the University nor the names of its contributors
19 *    may be used to endorse or promote products derived from this software
20 *    without specific prior written permission.
21 *
22 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
23 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
26 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
27 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
28 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
29 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
31 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32 * SUCH DAMAGE.
33 *
34 *	@(#)ufs_bmap.c	8.7 (Berkeley) 3/21/95
35 */
36
37#include <sys/cdefs.h>
38__FBSDID("$FreeBSD$");
39
40#include <sys/param.h>
41#include <sys/systm.h>
42#include <sys/bio.h>
43#include <sys/buf.h>
44#include <sys/proc.h>
45#include <sys/vnode.h>
46#include <sys/mount.h>
47#include <sys/resourcevar.h>
48#include <sys/stat.h>
49
50#include <ufs/ufs/extattr.h>
51#include <ufs/ufs/quota.h>
52#include <ufs/ufs/inode.h>
53#include <ufs/ufs/ufsmount.h>
54#include <ufs/ufs/ufs_extern.h>
55
56/*
57 * Bmap converts the logical block number of a file to its physical block
58 * number on the disk. The conversion is done by using the logical block
59 * number to index into the array of block pointers described by the dinode.
60 */
61int
62ufs_bmap(ap)
63	struct vop_bmap_args /* {
64		struct vnode *a_vp;
65		daddr_t a_bn;
66		struct bufobj **a_bop;
67		daddr_t *a_bnp;
68		int *a_runp;
69		int *a_runb;
70	} */ *ap;
71{
72	ufs2_daddr_t blkno;
73	int error;
74
75	/*
76	 * Check for underlying vnode requests and ensure that logical
77	 * to physical mapping is requested.
78	 */
79	if (ap->a_bop != NULL)
80		*ap->a_bop = &VTOI(ap->a_vp)->i_devvp->v_bufobj;
81	if (ap->a_bnp == NULL)
82		return (0);
83
84	error = ufs_bmaparray(ap->a_vp, ap->a_bn, &blkno, NULL,
85	    ap->a_runp, ap->a_runb);
86	*ap->a_bnp = blkno;
87	return (error);
88}
89
90/*
91 * Indirect blocks are now on the vnode for the file.  They are given negative
92 * logical block numbers.  Indirect blocks are addressed by the negative
93 * address of the first data block to which they point.  Double indirect blocks
94 * are addressed by one less than the address of the first indirect block to
95 * which they point.  Triple indirect blocks are addressed by one less than
96 * the address of the first double indirect block to which they point.
97 *
98 * ufs_bmaparray does the bmap conversion, and if requested returns the
99 * array of logical blocks which must be traversed to get to a block.
100 * Each entry contains the offset into that block that gets you to the
101 * next block and the disk address of the block (if it is assigned).
102 */
103
104int
105ufs_bmaparray(vp, bn, bnp, nbp, runp, runb)
106	struct vnode *vp;
107	ufs2_daddr_t bn;
108	ufs2_daddr_t *bnp;
109	struct buf *nbp;
110	int *runp;
111	int *runb;
112{
113	struct inode *ip;
114	struct buf *bp;
115	struct ufsmount *ump;
116	struct mount *mp;
117	struct vnode *devvp;
118	struct indir a[NIADDR+1], *ap;
119	ufs2_daddr_t daddr;
120	ufs_lbn_t metalbn;
121	int error, num, maxrun = 0;
122	int *nump;
123
124	ap = NULL;
125	ip = VTOI(vp);
126	mp = vp->v_mount;
127	ump = VFSTOUFS(mp);
128	devvp = ump->um_devvp;
129
130	if (runp) {
131		maxrun = mp->mnt_iosize_max / mp->mnt_stat.f_iosize - 1;
132		*runp = 0;
133	}
134
135	if (runb) {
136		*runb = 0;
137	}
138
139
140	ap = a;
141	nump = &num;
142	error = ufs_getlbns(vp, bn, ap, nump);
143	if (error)
144		return (error);
145
146	num = *nump;
147	if (num == 0) {
148		if (bn >= 0 && bn < NDADDR) {
149			*bnp = blkptrtodb(ump, DIP(ip, i_db[bn]));
150		} else if (bn < 0 && bn >= -NXADDR) {
151			*bnp = blkptrtodb(ump, ip->i_din2->di_extb[-1 - bn]);
152			if (*bnp == 0)
153				*bnp = -1;
154			if (nbp == NULL)
155				panic("ufs_bmaparray: mapping ext data");
156			nbp->b_xflags |= BX_ALTDATA;
157			return (0);
158		} else {
159			panic("ufs_bmaparray: blkno out of range");
160		}
161		/*
162		 * Since this is FFS independent code, we are out of
163		 * scope for the definitions of BLK_NOCOPY and
164		 * BLK_SNAP, but we do know that they will fall in
165		 * the range 1..um_seqinc, so we use that test and
166		 * return a request for a zeroed out buffer if attempts
167		 * are made to read a BLK_NOCOPY or BLK_SNAP block.
168		 */
169		if ((ip->i_flags & SF_SNAPSHOT) && DIP(ip, i_db[bn]) > 0 &&
170		    DIP(ip, i_db[bn]) < ump->um_seqinc) {
171			*bnp = -1;
172		} else if (*bnp == 0) {
173			if (ip->i_flags & SF_SNAPSHOT)
174				*bnp = blkptrtodb(ump, bn * ump->um_seqinc);
175			else
176				*bnp = -1;
177		} else if (runp) {
178			ufs2_daddr_t bnb = bn;
179			for (++bn; bn < NDADDR && *runp < maxrun &&
180			    is_sequential(ump, DIP(ip, i_db[bn - 1]),
181			    DIP(ip, i_db[bn]));
182			    ++bn, ++*runp);
183			bn = bnb;
184			if (runb && (bn > 0)) {
185				for (--bn; (bn >= 0) && (*runb < maxrun) &&
186					is_sequential(ump, DIP(ip, i_db[bn]),
187						DIP(ip, i_db[bn+1]));
188						--bn, ++*runb);
189			}
190		}
191		return (0);
192	}
193
194
195	/* Get disk address out of indirect block array */
196	daddr = DIP(ip, i_ib[ap->in_off]);
197
198	for (bp = NULL, ++ap; --num; ++ap) {
199		/*
200		 * Exit the loop if there is no disk address assigned yet and
201		 * the indirect block isn't in the cache, or if we were
202		 * looking for an indirect block and we've found it.
203		 */
204
205		metalbn = ap->in_lbn;
206		if ((daddr == 0 && !incore(&vp->v_bufobj, metalbn)) || metalbn == bn)
207			break;
208		/*
209		 * If we get here, we've either got the block in the cache
210		 * or we have a disk address for it, go fetch it.
211		 */
212		if (bp)
213			bqrelse(bp);
214
215		bp = getblk(vp, metalbn, mp->mnt_stat.f_iosize, 0, 0, 0);
216		if ((bp->b_flags & B_CACHE) == 0) {
217#ifdef INVARIANTS
218			if (!daddr)
219				panic("ufs_bmaparray: indirect block not in cache");
220#endif
221			bp->b_blkno = blkptrtodb(ump, daddr);
222			bp->b_iocmd = BIO_READ;
223			bp->b_flags &= ~B_INVAL;
224			bp->b_ioflags &= ~BIO_ERROR;
225			vfs_busy_pages(bp, 0);
226			bp->b_iooffset = dbtob(bp->b_blkno);
227			bstrategy(bp);
228			curthread->td_ru.ru_inblock++;
229			error = bufwait(bp);
230			if (error) {
231				brelse(bp);
232				return (error);
233			}
234		}
235
236		if (ip->i_ump->um_fstype == UFS1) {
237			daddr = ((ufs1_daddr_t *)bp->b_data)[ap->in_off];
238			if (num == 1 && daddr && runp) {
239				for (bn = ap->in_off + 1;
240				    bn < MNINDIR(ump) && *runp < maxrun &&
241				    is_sequential(ump,
242				    ((ufs1_daddr_t *)bp->b_data)[bn - 1],
243				    ((ufs1_daddr_t *)bp->b_data)[bn]);
244				    ++bn, ++*runp);
245				bn = ap->in_off;
246				if (runb && bn) {
247					for (--bn; bn >= 0 && *runb < maxrun &&
248					    is_sequential(ump,
249					    ((ufs1_daddr_t *)bp->b_data)[bn],
250					    ((ufs1_daddr_t *)bp->b_data)[bn+1]);
251					    --bn, ++*runb);
252				}
253			}
254			continue;
255		}
256		daddr = ((ufs2_daddr_t *)bp->b_data)[ap->in_off];
257		if (num == 1 && daddr && runp) {
258			for (bn = ap->in_off + 1;
259			    bn < MNINDIR(ump) && *runp < maxrun &&
260			    is_sequential(ump,
261			    ((ufs2_daddr_t *)bp->b_data)[bn - 1],
262			    ((ufs2_daddr_t *)bp->b_data)[bn]);
263			    ++bn, ++*runp);
264			bn = ap->in_off;
265			if (runb && bn) {
266				for (--bn; bn >= 0 && *runb < maxrun &&
267				    is_sequential(ump,
268				    ((ufs2_daddr_t *)bp->b_data)[bn],
269				    ((ufs2_daddr_t *)bp->b_data)[bn + 1]);
270				    --bn, ++*runb);
271			}
272		}
273	}
274	if (bp)
275		bqrelse(bp);
276
277	/*
278	 * Since this is FFS independent code, we are out of scope for the
279	 * definitions of BLK_NOCOPY and BLK_SNAP, but we do know that they
280	 * will fall in the range 1..um_seqinc, so we use that test and
281	 * return a request for a zeroed out buffer if attempts are made
282	 * to read a BLK_NOCOPY or BLK_SNAP block.
283	 */
284	if ((ip->i_flags & SF_SNAPSHOT) && daddr > 0 && daddr < ump->um_seqinc){
285		*bnp = -1;
286		return (0);
287	}
288	*bnp = blkptrtodb(ump, daddr);
289	if (*bnp == 0) {
290		if (ip->i_flags & SF_SNAPSHOT)
291			*bnp = blkptrtodb(ump, bn * ump->um_seqinc);
292		else
293			*bnp = -1;
294	}
295	return (0);
296}
297
298/*
299 * Create an array of logical block number/offset pairs which represent the
300 * path of indirect blocks required to access a data block.  The first "pair"
301 * contains the logical block number of the appropriate single, double or
302 * triple indirect block and the offset into the inode indirect block array.
303 * Note, the logical block number of the inode single/double/triple indirect
304 * block appears twice in the array, once with the offset into the i_ib and
305 * once with the offset into the page itself.
306 */
307int
308ufs_getlbns(vp, bn, ap, nump)
309	struct vnode *vp;
310	ufs2_daddr_t bn;
311	struct indir *ap;
312	int *nump;
313{
314	ufs2_daddr_t blockcnt;
315	ufs_lbn_t metalbn, realbn;
316	struct ufsmount *ump;
317	int i, numlevels, off;
318
319	ump = VFSTOUFS(vp->v_mount);
320	if (nump)
321		*nump = 0;
322	numlevels = 0;
323	realbn = bn;
324	if (bn < 0)
325		bn = -bn;
326
327	/* The first NDADDR blocks are direct blocks. */
328	if (bn < NDADDR)
329		return (0);
330
331	/*
332	 * Determine the number of levels of indirection.  After this loop
333	 * is done, blockcnt indicates the number of data blocks possible
334	 * at the previous level of indirection, and NIADDR - i is the number
335	 * of levels of indirection needed to locate the requested block.
336	 */
337	for (blockcnt = 1, i = NIADDR, bn -= NDADDR;; i--, bn -= blockcnt) {
338		if (i == 0)
339			return (EFBIG);
340		blockcnt *= MNINDIR(ump);
341		if (bn < blockcnt)
342			break;
343	}
344
345	/* Calculate the address of the first meta-block. */
346	if (realbn >= 0)
347		metalbn = -(realbn - bn + NIADDR - i);
348	else
349		metalbn = -(-realbn - bn + NIADDR - i);
350
351	/*
352	 * At each iteration, off is the offset into the bap array which is
353	 * an array of disk addresses at the current level of indirection.
354	 * The logical block number and the offset in that block are stored
355	 * into the argument array.
356	 */
357	ap->in_lbn = metalbn;
358	ap->in_off = off = NIADDR - i;
359	ap++;
360	for (++numlevels; i <= NIADDR; i++) {
361		/* If searching for a meta-data block, quit when found. */
362		if (metalbn == realbn)
363			break;
364
365		blockcnt /= MNINDIR(ump);
366		off = (bn / blockcnt) % MNINDIR(ump);
367
368		++numlevels;
369		ap->in_lbn = metalbn;
370		ap->in_off = off;
371		++ap;
372
373		metalbn -= -1 + off * blockcnt;
374	}
375	if (nump)
376		*nump = numlevels;
377	return (0);
378}
379