kernel: Move GPL'd kernel files to sys/gnu to have them all in one place.
[dragonfly.git] / sys / gnu / vfs / ext2fs / ext2_bmap.c
CommitLineData
1f1db49f
MD
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 * 3. All advertising materials mentioning features or use of this software
19 * must display the following acknowledgement:
20 * This product includes software developed by the University of
21 * California, Berkeley and its contributors.
22 * 4. Neither the name of the University nor the names of its contributors
23 * may be used to endorse or promote products derived from this software
24 * without specific prior written permission.
25 *
26 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
27 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
28 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
29 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
30 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
31 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
32 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
33 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
34 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
35 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
36 * SUCH DAMAGE.
37 *
38 * @(#)ufs_bmap.c 8.7 (Berkeley) 3/21/95
39 * $FreeBSD: src/sys/ufs/ufs/ufs_bmap.c,v 1.34.2.1 2000/03/17 10:12:14 ps Exp $
1f1db49f
MD
40 */
41
42#include <sys/param.h>
43#include <sys/systm.h>
44#include <sys/buf.h>
45#include <sys/proc.h>
46#include <sys/vnode.h>
47#include <sys/mount.h>
48#include <sys/resourcevar.h>
49#include <sys/conf.h>
50
51#include "quota.h"
52#include "dinode.h"
53#include "inode.h"
54#include "ext2_fs_sb.h"
55#include "ext2mount.h"
56#include "ext2_extern.h"
57#include "fs.h"
58
59static int ext2_bmaparray(struct vnode *vp, ext2_daddr_t bn,
60 ext2_daddr_t *bnp, struct indir *ap, int *nump,
61 int *runp, int *runb);
62
63/*
64 * Bmap converts the logical block number of a file to its physical block
65 * number on the disk. The conversion is done by using the logical block
66 * number to index into the array of block pointers described by the dinode.
67 *
68 * BMAP must return the contiguous before and after run in bytes, inclusive
69 * of the returned block.
70 *
08daea96 71 * ext2_bmap(struct vnode *a_vp, off_t a_loffset,
1f1db49f
MD
72 * off_t *a_doffsetp, int *a_runp, int *a_runb)
73 */
74int
75ext2_bmap(struct vop_bmap_args *ap)
76{
77 struct ext2_sb_info *fs;
78 ext2_daddr_t lbn;
79 ext2_daddr_t dbn;
80 int error;
81
82 /*
83 * Check for underlying vnode requests and ensure that logical
84 * to physical mapping is requested.
85 */
1f1db49f
MD
86 if (ap->a_doffsetp == NULL)
87 return (0);
88
89 fs = VTOI(ap->a_vp)->i_e2fs;
90 KKASSERT(((int)ap->a_loffset & ((1 << fs->s_bshift) - 1)) == 0);
91 lbn = ap->a_loffset >> fs->s_bshift;
92
93 error = ext2_bmaparray(ap->a_vp, lbn, &dbn, NULL, NULL,
94 ap->a_runp, ap->a_runb);
95
96 if (error || dbn == (ext2_daddr_t)-1) {
97 *ap->a_doffsetp = NOOFFSET;
98 } else {
99 *ap->a_doffsetp = dbtodoff(fs, dbn);
100 if (ap->a_runp)
101 *ap->a_runp = (*ap->a_runp + 1) << fs->s_bshift;
102 if (ap->a_runb)
103 *ap->a_runb = *ap->a_runb << fs->s_bshift;
104 }
105 return (error);
106}
107
108/*
109 * Indirect blocks are now on the vnode for the file. They are given negative
110 * logical block numbers. Indirect blocks are addressed by the negative
111 * address of the first data block to which they point. Double indirect blocks
112 * are addressed by one less than the address of the first indirect block to
113 * which they point. Triple indirect blocks are addressed by one less than
114 * the address of the first double indirect block to which they point.
115 *
116 * ext2_bmaparray does the bmap conversion, and if requested returns the
117 * array of logical blocks which must be traversed to get to a block.
118 * Each entry contains the offset into that block that gets you to the
119 * next block and the disk address of the block (if it is assigned).
120 */
121static
122int
123ext2_bmaparray(struct vnode *vp, ext2_daddr_t bn, ext2_daddr_t *bnp,
124 struct indir *ap, int *nump, int *runp, int *runb)
125{
126 struct inode *ip;
127 struct buf *bp;
128 struct ext2mount *ump;
129 struct mount *mp;
1f1db49f
MD
130 struct ext2_sb_info *fs;
131 struct indir a[NIADDR+1], *xap;
132 ext2_daddr_t daddr;
133 long metalbn;
134 int error, maxrun, num;
135
136 ip = VTOI(vp);
137 mp = vp->v_mount;
138 ump = VFSTOEXT2(mp);
1f1db49f
MD
139 fs = ip->i_e2fs;
140#ifdef DIAGNOSTIC
141 if ((ap != NULL && nump == NULL) || (ap == NULL && nump != NULL))
142 panic("ext2_bmaparray: invalid arguments");
143#endif
144
145 if (runp) {
146 *runp = 0;
147 }
148
149 if (runb) {
150 *runb = 0;
151 }
152
153 maxrun = mp->mnt_iosize_max / mp->mnt_stat.f_iosize - 1;
154
155 xap = ap == NULL ? a : ap;
156 if (!nump)
157 nump = &num;
158 error = ext2_getlbns(vp, bn, xap, nump);
159 if (error)
160 return (error);
161
162 num = *nump;
163 if (num == 0) {
164 *bnp = blkptrtodb(ump, ip->i_db[bn]);
165 if (*bnp == 0)
166 *bnp = -1;
167 else if (runp) {
168 daddr_t bnb = bn;
169 for (++bn; bn < NDADDR && *runp < maxrun &&
170 is_sequential(ump, ip->i_db[bn - 1], ip->i_db[bn]);
171 ++bn, ++*runp);
172 bn = bnb;
173 if (runb && (bn > 0)) {
174 for (--bn; (bn >= 0) && (*runb < maxrun) &&
175 is_sequential(ump, ip->i_db[bn],
176 ip->i_db[bn+1]);
177 --bn, ++*runb);
178 }
179 }
180 return (0);
181 }
182
183
184 /* Get disk address out of indirect block array */
185 daddr = ip->i_ib[xap->in_off];
186
187 for (bp = NULL, ++xap; --num; ++xap) {
188 /*
189 * Exit the loop if there is no disk address assigned yet and
190 * the indirect block isn't in the cache, or if we were
191 * looking for an indirect block and we've found it.
192 */
193
194 metalbn = xap->in_lbn;
b1c20cfa
MD
195 if ((daddr == 0 &&
196 !findblk(vp, dbtodoff(fs, metalbn), FINDBLK_TEST)) ||
197 metalbn == bn) {
1f1db49f 198 break;
b1c20cfa 199 }
1f1db49f
MD
200 /*
201 * If we get here, we've either got the block in the cache
202 * or we have a disk address for it, go fetch it.
203 */
204 if (bp)
205 bqrelse(bp);
206
207 xap->in_exists = 1;
208 bp = getblk(vp, lblktodoff(fs, metalbn),
209 mp->mnt_stat.f_iosize, 0, 0);
210 if ((bp->b_flags & B_CACHE) == 0) {
211#ifdef DIAGNOSTIC
212 if (!daddr)
213 panic("ext2_bmaparray: indirect block not in cache");
214#endif
ae8e83e6
MD
215 /*
216 * This runs through ext2_strategy using bio2 to
217 * cache the disk offset, then comes back through
218 * bio1. So we want to wait on bio1
219 */
220 bp->b_bio1.bio_done = biodone_sync;
221 bp->b_bio1.bio_flags |= BIO_SYNC;
1f1db49f 222 bp->b_bio2.bio_offset = fsbtodoff(fs, daddr);
1f1db49f 223 bp->b_flags &= ~(B_INVAL|B_ERROR);
10f3fee5
MD
224 bp->b_cmd = BUF_CMD_READ;
225 vfs_busy_pages(bp->b_vp, bp);
1f1db49f 226 vn_strategy(bp->b_vp, &bp->b_bio1);
ae8e83e6 227 error = biowait(&bp->b_bio1, "biord");
1f1db49f
MD
228 if (error) {
229 brelse(bp);
230 return (error);
231 }
232 }
233
234 daddr = ((ext2_daddr_t *)bp->b_data)[xap->in_off];
235 if (num == 1 && daddr && runp) {
236 for (bn = xap->in_off + 1;
237 bn < MNINDIR(ump) && *runp < maxrun &&
238 is_sequential(ump,
239 ((ext2_daddr_t *)bp->b_data)[bn - 1],
240 ((ext2_daddr_t *)bp->b_data)[bn]);
241 ++bn, ++*runp);
242 bn = xap->in_off;
243 if (runb && bn) {
244 for(--bn; bn >= 0 && *runb < maxrun &&
b993bb87 245 is_sequential(ump, ((daddr_t *)bp->b_data)[bn],
1f1db49f 246 ((daddr_t *)bp->b_data)[bn+1]);
b993bb87 247 --bn, ++*runb);
1f1db49f
MD
248 }
249 }
250 }
251 if (bp)
252 bqrelse(bp);
253
254 daddr = blkptrtodb(ump, daddr);
255 *bnp = daddr == 0 ? -1 : daddr;
256 return (0);
257}
258
259/*
260 * Create an array of logical block number/offset pairs which represent the
261 * path of indirect blocks required to access a data block. The first "pair"
262 * contains the logical block number of the appropriate single, double or
263 * triple indirect block and the offset into the inode indirect block array.
264 * Note, the logical block number of the inode single/double/triple indirect
265 * block appears twice in the array, once with the offset into the i_ib and
266 * once with the offset into the page itself.
267 */
268int
269ext2_getlbns(struct vnode *vp, ext2_daddr_t bn, struct indir *ap, int *nump)
270{
271 long blockcnt, metalbn, realbn;
272 struct ext2mount *ump;
273 int i, numlevels, off;
274 int64_t qblockcnt;
275
276 ump = VFSTOEXT2(vp->v_mount);
277 if (nump)
278 *nump = 0;
279 numlevels = 0;
280 realbn = bn;
281 if ((long)bn < 0)
282 bn = -(long)bn;
283
284 /* The first NDADDR blocks are direct blocks. */
285 if (bn < NDADDR)
286 return (0);
287
288 /*
289 * Determine the number of levels of indirection. After this loop
290 * is done, blockcnt indicates the number of data blocks possible
291 * at the previous level of indirection, and NIADDR - i is the number
292 * of levels of indirection needed to locate the requested block.
293 */
294 for (blockcnt = 1, i = NIADDR, bn -= NDADDR;; i--, bn -= blockcnt) {
295 if (i == 0)
296 return (EFBIG);
297 /*
298 * Use int64_t's here to avoid overflow for triple indirect
299 * blocks when longs have 32 bits and the block size is more
300 * than 4K.
301 */
302 qblockcnt = (int64_t)blockcnt * MNINDIR(ump);
303 if (bn < qblockcnt)
304 break;
305 blockcnt = qblockcnt;
306 }
307
308 /* Calculate the address of the first meta-block. */
309 if (realbn >= 0)
310 metalbn = -(realbn - bn + NIADDR - i);
311 else
312 metalbn = -(-realbn - bn + NIADDR - i);
313
314 /*
315 * At each iteration, off is the offset into the bap array which is
316 * an array of disk addresses at the current level of indirection.
317 * The logical block number and the offset in that block are stored
318 * into the argument array.
319 */
320 ap->in_lbn = metalbn;
321 ap->in_off = off = NIADDR - i;
322 ap->in_exists = 0;
323 ap++;
324 for (++numlevels; i <= NIADDR; i++) {
325 /* If searching for a meta-data block, quit when found. */
326 if (metalbn == realbn)
327 break;
328
329 off = (bn / blockcnt) % MNINDIR(ump);
330
331 ++numlevels;
332 ap->in_lbn = metalbn;
333 ap->in_off = off;
334 ap->in_exists = 0;
335 ++ap;
336
337 metalbn -= -1 + off * blockcnt;
338 blockcnt /= MNINDIR(ump);
339 }
340 if (nump)
341 *nump = numlevels;
342 return (0);
343}