sys/fs/ext2fs/ext2_bmap.c

   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 = &num;
 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         /*
 312          * Since this is FFS independent code, we are out of scope for the
 313          * definitions of BLK_NOCOPY and BLK_SNAP, but we do know that they
 314          * will fall in the range 1..um_seqinc, so we use that test and
 315          * return a request for a zeroed out buffer if attempts are made
 316          * to read a BLK_NOCOPY or BLK_SNAP block.
 317          */
 318         if ((ip->i_flags & SF_SNAPSHOT) && daddr > 0 && daddr < ump->um_seqinc) {
 319                 *bnp = -1;
 320                 return (0);
 321         }
 322         *bnp = blkptrtodb(ump, daddr);
 323         if (*bnp == 0) {
 324                 *bnp = -1;
 325         }
 326         return (0);
 327 }
 328
 329 static e2fs_lbn_t
 330 lbn_count(struct ext2mount *ump, int level)
 331
 332 {
 333         e2fs_lbn_t blockcnt;
 334
 335         for (blockcnt = 1; level > 0; level--)
 336                 blockcnt *= MNINDIR(ump);
 337         return (blockcnt);
 338 }
 339
 340 int
 341 ext2_bmap_seekdata(struct vnode *vp, off_t *offp)
 342 {
 343         struct buf *bp;
 344         struct indir a[EXT2_NIADDR + 1], *ap;
 345         struct inode *ip;
 346         struct mount *mp;
 347         struct ext2mount *ump;
 348         e2fs_daddr_t bn, daddr, nextbn;
 349         uint64_t bsize;
 350         off_t numblks;
 351         int error, num, num1, off;
 352
 353         bp = NULL;
 354         error = 0;
 355         ip = VTOI(vp);
 356         mp = vp->v_mount;
 357         ump = VFSTOEXT2(mp);
 358
 359         if (vp->v_type != VREG || (ip->i_flags & SF_SNAPSHOT) != 0)
 360                 return (EINVAL);
 361         if (*offp < 0 || *offp >= ip->i_size)
 362                 return (ENXIO);
 363
 364         bsize = mp->mnt_stat.f_iosize;
 365         for (bn = *offp / bsize, numblks = howmany(ip->i_size, bsize);
 366             bn < numblks; bn = nextbn) {
 367                 if (bn < EXT2_NDADDR) {
 368                         daddr = ip->i_db[bn];
 369                         if (daddr != 0)
 370                                 break;
 371                         nextbn = bn + 1;
 372                         continue;
 373                 }
 374
 375                 ap = a;
 376                 error = ext2_getlbns(vp, bn, ap, &num);
 377                 if (error != 0)
 378                         break;
 379                 MPASS(num >= 2);
 380                 daddr = ip->i_ib[ap->in_off];
 381                 ap++, num--;
 382                 for (nextbn = EXT2_NDADDR, num1 = num - 1; num1 > 0; num1--)
 383                         nextbn += lbn_count(ump, num1);
 384                 if (daddr == 0) {
 385                         nextbn += lbn_count(ump, num);
 386                         continue;
 387                 }
 388
 389                 for (; daddr != 0 && num > 0; ap++, num--) {
 390                         if (bp != NULL)
 391                                 bqrelse(bp);
 392                         error = readindir(vp, ap->in_lbn, daddr, &bp);
 393                         if (error != 0)
 394                                 return (error);
 395
 396                         /*
 397                          * Scan the indirect block until we find a non-zero
 398                          * pointer.
 399                          */
 400                         off = ap->in_off;
 401                         do {
 402                                 daddr = le32toh(((e2fs_daddr_t *)bp->b_data)[off]);
 403                         } while (daddr == 0 && ++off < MNINDIR(ump));
 404                         nextbn += off * lbn_count(ump, num - 1);
 405
 406                         /*
 407                          * We need to recompute the LBNs of indirect
 408                          * blocks, so restart with the updated block offset.
 409                          */
 410                         if (off != ap->in_off)
 411                                 break;
 412                 }
 413                 if (num == 0) {
 414                         /*
 415                          * We found a data block.
 416                          */
 417                         bn = nextbn;
 418                         break;
 419                 }
 420         }
 421         if (bp != NULL)
 422                 bqrelse(bp);
 423         if (bn >= numblks)
 424                 error = ENXIO;
 425         if (error == 0 && *offp < bn * bsize)
 426                 *offp = bn * bsize;
 427         return (error);
 428 }
 429
 430 /*
 431  * Create an array of logical block number/offset pairs which represent the
 432  * path of indirect blocks required to access a data block.  The first "pair"
 433  * contains the logical block number of the appropriate single, double or
 434  * triple indirect block and the offset into the inode indirect block array.
 435  * Note, the logical block number of the inode single/double/triple indirect
 436  * block appears twice in the array, once with the offset into the i_ib and
 437  * once with the offset into the page itself.
 438  */
 439 int
 440 ext2_getlbns(struct vnode *vp, daddr_t bn, struct indir *ap, int *nump)
 441 {
 442         long blockcnt;
 443         e2fs_lbn_t metalbn, realbn;
 444         struct ext2mount *ump;
 445         int i, numlevels, off;
 446         int64_t qblockcnt;
 447
 448         ump = VFSTOEXT2(vp->v_mount);
 449         if (nump)
 450                 *nump = 0;
 451         numlevels = 0;
 452         realbn = bn;
 453         if ((long)bn < 0)
 454                 bn = -(long)bn;
 455
 456         /* The first EXT2_NDADDR blocks are direct blocks. */
 457         if (bn < EXT2_NDADDR)
 458                 return (0);
 459
 460         /*
 461          * Determine the number of levels of indirection.  After this loop
 462          * is done, blockcnt indicates the number of data blocks possible
 463          * at the previous level of indirection, and EXT2_NIADDR - i is the
 464          * number of levels of indirection needed to locate the requested block.
 465          */
 466         for (blockcnt = 1, i = EXT2_NIADDR, bn -= EXT2_NDADDR; ;
 467             i--, bn -= blockcnt) {
 468                 if (i == 0)
 469                         return (EFBIG);
 470                 /*
 471                  * Use int64_t's here to avoid overflow for triple indirect
 472                  * blocks when longs have 32 bits and the block size is more
 473                  * than 4K.
 474                  */
 475                 qblockcnt = (int64_t)blockcnt * MNINDIR(ump);
 476                 if (bn < qblockcnt)
 477                         break;
 478                 blockcnt = qblockcnt;
 479         }
 480
 481         /* Calculate the address of the first meta-block. */
 482         if (realbn >= 0)
 483                 metalbn = -(realbn - bn + EXT2_NIADDR - i);
 484         else
 485                 metalbn = -(-realbn - bn + EXT2_NIADDR - i);
 486
 487         /*
 488          * At each iteration, off is the offset into the bap array which is
 489          * an array of disk addresses at the current level of indirection.
 490          * The logical block number and the offset in that block are stored
 491          * into the argument array.
 492          */
 493         ap->in_lbn = metalbn;
 494         ap->in_off = off = EXT2_NIADDR - i;
 495         ap++;
 496         for (++numlevels; i <= EXT2_NIADDR; i++) {
 497                 /* If searching for a meta-data block, quit when found. */
 498                 if (metalbn == realbn)
 499                         break;
 500
 501                 off = (bn / blockcnt) % MNINDIR(ump);
 502
 503                 ++numlevels;
 504                 ap->in_lbn = metalbn;
 505                 ap->in_off = off;
 506                 ++ap;
 507
 508                 metalbn -= -1 + off * blockcnt;
 509                 blockcnt /= MNINDIR(ump);
 510         }
 511         if (nump)
 512                 *nump = numlevels;
 513         return (0);
 514 }