1 /*-
2 * SPDX-License-Identifier: BSD-3-Clause
3 *
4 * Copyright (c) 1989, 1991, 1993
5 * The Regents of the University of California. All rights reserved.
6 * (c) UNIX System Laboratories, Inc.
7 * All or some portions of this file are derived from material licensed
8 * to the University of California by American Telephone and Telegraph
9 * Co. or Unix System Laboratories, Inc. and are reproduced herein with
10 * the permission of UNIX System Laboratories, Inc.
11 *
12 * Redistribution and use in source and binary forms, with or without
13 * modification, are permitted provided that the following conditions
14 * are met:
15 * 1. Redistributions of source code must retain the above copyright
16 * notice, this list of conditions and the following disclaimer.
17 * 2. Redistributions in binary form must reproduce the above copyright
18 * notice, this list of conditions and the following disclaimer in the
19 * documentation and/or other materials provided with the distribution.
20 * 3. Neither the name of the University nor the names of its contributors
21 * may be used to endorse or promote products derived from this software
22 * without specific prior written permission.
23 *
24 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
25 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
26 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
27 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
28 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
29 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
30 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
33 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
34 * SUCH DAMAGE.
35 *
36 * @(#)ufs_bmap.c 8.7 (Berkeley) 3/21/95
37 * $FreeBSD$
38 */
39
40 #include <sys/param.h>
41 #include <sys/systm.h>
42 #include <sys/bio.h>
43 #include <sys/buf.h>
44 #include <sys/endian.h>
45 #include <sys/proc.h>
46 #include <sys/vnode.h>
47 #include <sys/mount.h>
48 #include <sys/racct.h>
49 #include <sys/resourcevar.h>
50 #include <sys/stat.h>
51
52 #include <fs/ext2fs/fs.h>
53 #include <fs/ext2fs/inode.h>
54 #include <fs/ext2fs/ext2fs.h>
55 #include <fs/ext2fs/ext2_dinode.h>
56 #include <fs/ext2fs/ext2_extern.h>
57 #include <fs/ext2fs/ext2_mount.h>
58
59 /*
60 * Bmap converts the logical block number of a file to its physical block
61 * number on the disk. The conversion is done by using the logical block
62 * number to index into the array of block pointers described by the dinode.
63 */
64 int
65 ext2_bmap(struct vop_bmap_args *ap)
66 {
67 daddr_t blkno;
68 int error;
69
70 /*
71 * Check for underlying vnode requests and ensure that logical
72 * to physical mapping is requested.
73 */
74 if (ap->a_bop != NULL)
75 *ap->a_bop = &VTOI(ap->a_vp)->i_devvp->v_bufobj;
76 if (ap->a_bnp == NULL)
77 return (0);
78
79 if (VTOI(ap->a_vp)->i_flag & IN_E4EXTENTS)
80 error = ext4_bmapext(ap->a_vp, ap->a_bn, &blkno,
81 ap->a_runp, ap->a_runb);
82 else
83 error = ext2_bmaparray(ap->a_vp, ap->a_bn, &blkno,
84 ap->a_runp, ap->a_runb);
85 *ap->a_bnp = blkno;
86 return (error);
87 }
88
89 /*
90 * Convert the logical block number of a file to its physical block number
91 * on the disk within ext4 extents.
92 */
93 int
94 ext4_bmapext(struct vnode *vp, int32_t bn, int64_t *bnp, int *runp, int *runb)
95 {
96 struct inode *ip;
97 struct m_ext2fs *fs;
98 struct mount *mp;
99 struct ext2mount *ump;
100 struct ext4_extent_header *ehp;
101 struct ext4_extent *ep;
102 struct ext4_extent_path *path = NULL;
103 daddr_t lbn;
104 int error, depth, maxrun = 0, bsize;
105
106 ip = VTOI(vp);
107 fs = ip->i_e2fs;
108 mp = vp->v_mount;
109 ump = VFSTOEXT2(mp);
110 lbn = bn;
111 ehp = (struct ext4_extent_header *)ip->i_data;
112 depth = le16toh(ehp->eh_depth);
113 bsize = EXT2_BLOCK_SIZE(ump->um_e2fs);
114
115 *bnp = -1;
116 if (runp != NULL) {
117 maxrun = mp->mnt_iosize_max / bsize - 1;
118 *runp = 0;
119 }
120 if (runb != NULL)
121 *runb = 0;
122
123 error = ext4_ext_find_extent(ip, lbn, &path);
124 if (error)
125 return (error);
126
127 ep = path[depth].ep_ext;
128 if(ep) {
129 if (lbn < le32toh(ep->e_blk)) {
130 if (runp != NULL) {
131 *runp = min(maxrun, le32toh(ep->e_blk) - lbn - 1);
132 }
133 } else if (le32toh(ep->e_blk) <= lbn &&
134 lbn < le32toh(ep->e_blk) + le16toh(ep->e_len)) {
135 *bnp = fsbtodb(fs, lbn - le32toh(ep->e_blk) +
136 (le32toh(ep->e_start_lo) |
137 (daddr_t)le16toh(ep->e_start_hi) << 32));
138 if (runp != NULL) {
139 *runp = min(maxrun,
140 le16toh(ep->e_len) -
141 (lbn - le32toh(ep->e_blk)) - 1);
142 }
143 if (runb != NULL)
144 *runb = min(maxrun, lbn - le32toh(ep->e_blk));
145 } else {
146 if (runb != NULL)
147 *runb = min(maxrun, le32toh(ep->e_blk) + lbn -
148 le16toh(ep->e_len));
149 }
150 }
151
152 ext4_ext_path_free(path);
153
154 return (error);
155 }
156
157 static int
158 readindir(struct vnode *vp, e2fs_lbn_t lbn, e2fs_daddr_t daddr, struct buf **bpp)
159 {
160 struct buf *bp;
161 struct mount *mp;
162 struct ext2mount *ump;
163 int error;
164
165 mp = vp->v_mount;
166 ump = VFSTOEXT2(mp);
167
168 bp = getblk(vp, lbn, mp->mnt_stat.f_iosize, 0, 0, 0);
169 if ((bp->b_flags & B_CACHE) == 0) {
170 KASSERT(daddr != 0,
171 ("readindir: indirect block not in cache"));
172
173 bp->b_blkno = blkptrtodb(ump, daddr);
174 bp->b_iocmd = BIO_READ;
175 bp->b_flags &= ~B_INVAL;
176 bp->b_ioflags &= ~BIO_ERROR;
177 vfs_busy_pages(bp, 0);
178 bp->b_iooffset = dbtob(bp->b_blkno);
179 bstrategy(bp);
180 #ifdef RACCT
181 if (racct_enable) {
182 PROC_LOCK(curproc);
183 racct_add_buf(curproc, bp, 0);
184 PROC_UNLOCK(curproc);
185 }
186 #endif
187 curthread->td_ru.ru_inblock++;
188 error = bufwait(bp);
189 if (error != 0) {
190 brelse(bp);
191 return (error);
192 }
193 }
194 *bpp = bp;
195 return (0);
196 }
197
198 /*
199 * Indirect blocks are now on the vnode for the file. They are given negative
200 * logical block numbers. Indirect blocks are addressed by the negative
201 * address of the first data block to which they point. Double indirect blocks
202 * are addressed by one less than the address of the first indirect block to
203 * which they point. Triple indirect blocks are addressed by one less than
204 * the address of the first double indirect block to which they point.
205 *
206 * ext2_bmaparray does the bmap conversion, and if requested returns the
207 * array of logical blocks which must be traversed to get to a block.
208 * Each entry contains the offset into that block that gets you to the
209 * next block and the disk address of the block (if it is assigned).
210 */
211
212 int
213 ext2_bmaparray(struct vnode *vp, daddr_t bn, daddr_t *bnp, int *runp, int *runb)
214 {
215 struct inode *ip;
216 struct buf *bp;
217 struct ext2mount *ump;
218 struct mount *mp;
219 struct indir a[EXT2_NIADDR + 1], *ap;
220 daddr_t daddr;
221 e2fs_lbn_t metalbn;
222 int error, num, maxrun = 0, bsize;
223 int *nump;
224
225 ap = NULL;
226 ip = VTOI(vp);
227 mp = vp->v_mount;
228 ump = VFSTOEXT2(mp);
229
230 bsize = EXT2_BLOCK_SIZE(ump->um_e2fs);
231
232 if (runp) {
233 maxrun = mp->mnt_iosize_max / bsize - 1;
234 *runp = 0;
235 }
236 if (runb)
237 *runb = 0;
238
239 ap = a;
240 nump = #
241 error = ext2_getlbns(vp, bn, ap, nump);
242 if (error)
243 return (error);
244
245 num = *nump;
246 if (num == 0) {
247 *bnp = blkptrtodb(ump, ip->i_db[bn]);
248 if (*bnp == 0) {
249 *bnp = -1;
250 } else if (runp) {
251 daddr_t bnb = bn;
252
253 for (++bn; bn < EXT2_NDADDR && *runp < maxrun &&
254 is_sequential(ump, ip->i_db[bn - 1], ip->i_db[bn]);
255 ++bn, ++*runp);
256 bn = bnb;
257 if (runb && (bn > 0)) {
258 for (--bn; (bn >= 0) && (*runb < maxrun) &&
259 is_sequential(ump, ip->i_db[bn],
260 ip->i_db[bn + 1]);
261 --bn, ++*runb);
262 }
263 }
264 return (0);
265 }
266
267 /* Get disk address out of indirect block array */
268 daddr = ip->i_ib[ap->in_off];
269
270 for (bp = NULL, ++ap; --num; ++ap) {
271 /*
272 * Exit the loop if there is no disk address assigned yet and
273 * the indirect block isn't in the cache, or if we were
274 * looking for an indirect block and we've found it.
275 */
276
277 metalbn = ap->in_lbn;
278 if ((daddr == 0 && !incore(&vp->v_bufobj, metalbn)) || metalbn == bn)
279 break;
280 /*
281 * If we get here, we've either got the block in the cache
282 * or we have a disk address for it, go fetch it.
283 */
284 if (bp)
285 bqrelse(bp);
286 error = readindir(vp, metalbn, daddr, &bp);
287 if (error != 0)
288 return (error);
289
290 daddr = le32toh(((e2fs_daddr_t *)bp->b_data)[ap->in_off]);
291 if (num == 1 && daddr && runp) {
292 for (bn = ap->in_off + 1;
293 bn < MNINDIR(ump) && *runp < maxrun &&
294 is_sequential(ump,
295 ((e2fs_daddr_t *)bp->b_data)[bn - 1],
296 ((e2fs_daddr_t *)bp->b_data)[bn]);
297 ++bn, ++*runp);
298 bn = ap->in_off;
299 if (runb && bn) {
300 for (--bn; bn >= 0 && *runb < maxrun &&
301 is_sequential(ump,
302 ((e2fs_daddr_t *)bp->b_data)[bn],
303 ((e2fs_daddr_t *)bp->b_data)[bn + 1]);
304 --bn, ++*runb);
305 }
306 }
307 }
308 if (bp)
309 bqrelse(bp);
310
311 *bnp = blkptrtodb(ump, daddr);
312 if (*bnp == 0) {
313 *bnp = -1;
314 }
315 return (0);
316 }
317
318 static e2fs_lbn_t
319 lbn_count(struct ext2mount *ump, int level)
320
321 {
322 e2fs_lbn_t blockcnt;
323
324 for (blockcnt = 1; level > 0; level--)
325 blockcnt *= MNINDIR(ump);
326 return (blockcnt);
327 }
328
329 int
330 ext2_bmap_seekdata(struct vnode *vp, off_t *offp)
331 {
332 struct buf *bp;
333 struct indir a[EXT2_NIADDR + 1], *ap;
334 struct inode *ip;
335 struct mount *mp;
336 struct ext2mount *ump;
337 e2fs_daddr_t bn, daddr, nextbn;
338 uint64_t bsize;
339 off_t numblks;
340 int error, num, num1, off;
341
342 bp = NULL;
343 error = 0;
344 ip = VTOI(vp);
345 mp = vp->v_mount;
346 ump = VFSTOEXT2(mp);
347
348 if (vp->v_type != VREG)
349 return (EINVAL);
350 if (*offp < 0 || *offp >= ip->i_size)
351 return (ENXIO);
352
353 bsize = mp->mnt_stat.f_iosize;
354 for (bn = *offp / bsize, numblks = howmany(ip->i_size, bsize);
355 bn < numblks; bn = nextbn) {
356 if (bn < EXT2_NDADDR) {
357 daddr = ip->i_db[bn];
358 if (daddr != 0)
359 break;
360 nextbn = bn + 1;
361 continue;
362 }
363
364 ap = a;
365 error = ext2_getlbns(vp, bn, ap, &num);
366 if (error != 0)
367 break;
368 MPASS(num >= 2);
369 daddr = ip->i_ib[ap->in_off];
370 ap++, num--;
371 for (nextbn = EXT2_NDADDR, num1 = num - 1; num1 > 0; num1--)
372 nextbn += lbn_count(ump, num1);
373 if (daddr == 0) {
374 nextbn += lbn_count(ump, num);
375 continue;
376 }
377
378 for (; daddr != 0 && num > 0; ap++, num--) {
379 if (bp != NULL)
380 bqrelse(bp);
381 error = readindir(vp, ap->in_lbn, daddr, &bp);
382 if (error != 0)
383 return (error);
384
385 /*
386 * Scan the indirect block until we find a non-zero
387 * pointer.
388 */
389 off = ap->in_off;
390 do {
391 daddr = le32toh(((e2fs_daddr_t *)bp->b_data)[off]);
392 } while (daddr == 0 && ++off < MNINDIR(ump));
393 nextbn += off * lbn_count(ump, num - 1);
394
395 /*
396 * We need to recompute the LBNs of indirect
397 * blocks, so restart with the updated block offset.
398 */
399 if (off != ap->in_off)
400 break;
401 }
402 if (num == 0) {
403 /*
404 * We found a data block.
405 */
406 bn = nextbn;
407 break;
408 }
409 }
410 if (bp != NULL)
411 bqrelse(bp);
412 if (bn >= numblks)
413 error = ENXIO;
414 if (error == 0 && *offp < bn * bsize)
415 *offp = bn * bsize;
416 return (error);
417 }
418
419 /*
420 * Create an array of logical block number/offset pairs which represent the
421 * path of indirect blocks required to access a data block. The first "pair"
422 * contains the logical block number of the appropriate single, double or
423 * triple indirect block and the offset into the inode indirect block array.
424 * Note, the logical block number of the inode single/double/triple indirect
425 * block appears twice in the array, once with the offset into the i_ib and
426 * once with the offset into the page itself.
427 */
428 int
429 ext2_getlbns(struct vnode *vp, daddr_t bn, struct indir *ap, int *nump)
430 {
431 long blockcnt;
432 e2fs_lbn_t metalbn, realbn;
433 struct ext2mount *ump;
434 int i, numlevels, off;
435 int64_t qblockcnt;
436
437 ump = VFSTOEXT2(vp->v_mount);
438 if (nump)
439 *nump = 0;
440 numlevels = 0;
441 realbn = bn;
442 if ((long)bn < 0)
443 bn = -(long)bn;
444
445 /* The first EXT2_NDADDR blocks are direct blocks. */
446 if (bn < EXT2_NDADDR)
447 return (0);
448
449 /*
450 * Determine the number of levels of indirection. After this loop
451 * is done, blockcnt indicates the number of data blocks possible
452 * at the previous level of indirection, and EXT2_NIADDR - i is the
453 * number of levels of indirection needed to locate the requested block.
454 */
455 for (blockcnt = 1, i = EXT2_NIADDR, bn -= EXT2_NDADDR; ;
456 i--, bn -= blockcnt) {
457 if (i == 0)
458 return (EFBIG);
459 /*
460 * Use int64_t's here to avoid overflow for triple indirect
461 * blocks when longs have 32 bits and the block size is more
462 * than 4K.
463 */
464 qblockcnt = (int64_t)blockcnt * MNINDIR(ump);
465 if (bn < qblockcnt)
466 break;
467 blockcnt = qblockcnt;
468 }
469
470 /* Calculate the address of the first meta-block. */
471 if (realbn >= 0)
472 metalbn = -(realbn - bn + EXT2_NIADDR - i);
473 else
474 metalbn = -(-realbn - bn + EXT2_NIADDR - i);
475
476 /*
477 * At each iteration, off is the offset into the bap array which is
478 * an array of disk addresses at the current level of indirection.
479 * The logical block number and the offset in that block are stored
480 * into the argument array.
481 */
482 ap->in_lbn = metalbn;
483 ap->in_off = off = EXT2_NIADDR - i;
484 ap++;
485 for (++numlevels; i <= EXT2_NIADDR; i++) {
486 /* If searching for a meta-data block, quit when found. */
487 if (metalbn == realbn)
488 break;
489
490 off = (bn / blockcnt) % MNINDIR(ump);
491
492 ++numlevels;
493 ap->in_lbn = metalbn;
494 ap->in_off = off;
495 ++ap;
496
497 metalbn -= -1 + off * blockcnt;
498 blockcnt /= MNINDIR(ump);
499 }
500 if (nump)
501 *nump = numlevels;
502 return (0);
503 }
Cache object: 96e8b48a1e5078aa2ccd73e713575a24
|