ufs_bmap.c

Version: - FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10
    1 /*      $NetBSD: ufs_bmap.c,v 1.28.2.3 2005/04/06 11:38:21 tron Exp $   */
    2 
    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.8 (Berkeley) 8/11/95
   37  */
   38 
   39 #include <sys/cdefs.h>
   40 __KERNEL_RCSID(0, "$NetBSD: ufs_bmap.c,v 1.28.2.3 2005/04/06 11:38:21 tron Exp $");
   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/trace.h>
   50 
   51 #include <miscfs/specfs/specdev.h>
   52 
   53 #include <ufs/ufs/inode.h>
   54 #include <ufs/ufs/ufsmount.h>
   55 #include <ufs/ufs/ufs_extern.h>
   56 #include <ufs/ufs/ufs_bswap.h>
   57 
   58 static boolean_t ufs_issequential __P((const struct ufsmount *,
   59                                         daddr_t, daddr_t));
   60 
   61 static boolean_t
   62 ufs_issequential(ump, daddr0, daddr1)
   63         const struct ufsmount *ump;
   64         daddr_t daddr0;
   65         daddr_t daddr1;
   66 {
   67 
   68         /* for ufs, blocks in a hole is not 'contiguous'. */
   69         if (daddr0 == 0)
   70                 return FALSE;
   71 
   72         return (daddr0 + ump->um_seqinc == daddr1);
   73 }
   74 
   75 /*
   76  * Bmap converts a the logical block number of a file to its physical block
   77  * number on the disk. The conversion is done by using the logical block
   78  * number to index into the array of block pointers described by the dinode.
   79  */
   80 int
   81 ufs_bmap(v)
   82         void *v;
   83 {
   84         struct vop_bmap_args /* {
   85                 struct vnode *a_vp;
   86                 daddr_t  a_bn;
   87                 struct vnode **a_vpp;
   88                 daddr_t *a_bnp;
   89                 int *a_runp;
   90         } */ *ap = v;
   91         /*
   92          * Check for underlying vnode requests and ensure that logical
   93          * to physical mapping is requested.
   94          */
   95         if (ap->a_vpp != NULL)
   96                 *ap->a_vpp = VTOI(ap->a_vp)->i_devvp;
   97         if (ap->a_bnp == NULL)
   98                 return (0);
   99 
  100         return (ufs_bmaparray(ap->a_vp, ap->a_bn, ap->a_bnp, NULL, NULL,
  101             ap->a_runp, ufs_issequential));
  102 }
  103 
  104 /*
  105  * Indirect blocks are now on the vnode for the file.  They are given negative
  106  * logical block numbers.  Indirect blocks are addressed by the negative
  107  * address of the first data block to which they point.  Double indirect blocks
  108  * are addressed by one less than the address of the first indirect block to
  109  * which they point.  Triple indirect blocks are addressed by one less than
  110  * the address of the first double indirect block to which they point.
  111  *
  112  * ufs_bmaparray does the bmap conversion, and if requested returns the
  113  * array of logical blocks which must be traversed to get to a block.
  114  * Each entry contains the offset into that block that gets you to the
  115  * next block and the disk address of the block (if it is assigned).
  116  */
  117 
  118 int
  119 ufs_bmaparray(vp, bn, bnp, ap, nump, runp, is_sequential)
  120         struct vnode *vp;
  121         daddr_t bn;
  122         daddr_t *bnp;
  123         struct indir *ap;
  124         int *nump;
  125         int *runp;
  126         ufs_issequential_callback_t is_sequential;
  127 {
  128         struct inode *ip;
  129         struct buf *bp;
  130         struct ufsmount *ump;
  131         struct mount *mp;
  132         struct indir a[NIADDR + 1], *xap;
  133         daddr_t daddr;
  134         daddr_t metalbn;
  135         int error, maxrun = 0, num;
  136 
  137         ip = VTOI(vp);
  138         mp = vp->v_mount;
  139         ump = VFSTOUFS(mp);
  140 #ifdef DIAGNOSTIC
  141         if ((ap != NULL && nump == NULL) || (ap == NULL && nump != NULL))
  142                 panic("ufs_bmaparray: invalid arguments");
  143 #endif
  144 
  145         if (runp) {
  146                 /*
  147                  * XXX
  148                  * If MAXBSIZE is the largest transfer the disks can handle,
  149                  * we probably want maxrun to be 1 block less so that we
  150                  * don't create a block larger than the device can handle.
  151                  */
  152                 *runp = 0;
  153                 maxrun = MAXPHYS / mp->mnt_stat.f_iosize - 1;
  154         }
  155 
  156         if (bn >= 0 && bn < NDADDR) {
  157                 if (nump != NULL)
  158                         *nump = 0;
  159                 if (ip->i_ump->um_fstype == UFS1)
  160                         daddr = ufs_rw32(ip->i_ffs1_db[bn],
  161                             UFS_MPNEEDSWAP(vp->v_mount));
  162                 else
  163                         daddr = ufs_rw64(ip->i_ffs2_db[bn],
  164                             UFS_MPNEEDSWAP(vp->v_mount));
  165                 *bnp = blkptrtodb(ump, daddr);
  166                 if (*bnp == 0)
  167                         *bnp = -1;
  168                 else if (runp) {
  169                         if (ip->i_ump->um_fstype == UFS1) {
  170                                 for (++bn; bn < NDADDR && *runp < maxrun &&
  171                                     is_sequential(ump,
  172                                         ufs_rw32(ip->i_ffs1_db[bn - 1],
  173                                             UFS_MPNEEDSWAP(vp->v_mount)),
  174                                         ufs_rw32(ip->i_ffs1_db[bn],
  175                                             UFS_MPNEEDSWAP(vp->v_mount)));
  176                                     ++bn, ++*runp);
  177                         } else {
  178                                 for (++bn; bn < NDADDR && *runp < maxrun &&
  179                                     is_sequential(ump,
  180                                         ufs_rw64(ip->i_ffs2_db[bn - 1],
  181                                             UFS_MPNEEDSWAP(vp->v_mount)),
  182                                         ufs_rw64(ip->i_ffs2_db[bn],
  183                                             UFS_MPNEEDSWAP(vp->v_mount)));
  184                                     ++bn, ++*runp);
  185                         }
  186                 }
  187                 return (0);
  188         }
  189 
  190         xap = ap == NULL ? a : ap;
  191         if (!nump)
  192                 nump = &num;
  193         if ((error = ufs_getlbns(vp, bn, xap, nump)) != 0)
  194                 return (error);
  195 
  196         num = *nump;
  197 
  198         /* Get disk address out of indirect block array */
  199         if (ip->i_ump->um_fstype == UFS1)
  200                 daddr = ufs_rw32(ip->i_ffs1_ib[xap->in_off],
  201                     UFS_MPNEEDSWAP(vp->v_mount));
  202         else
  203                 daddr = ufs_rw64(ip->i_ffs2_ib[xap->in_off],
  204                     UFS_MPNEEDSWAP(vp->v_mount));
  205 
  206         for (bp = NULL, ++xap; --num; ++xap) {
  207                 /* 
  208                  * Exit the loop if there is no disk address assigned yet and
  209                  * the indirect block isn't in the cache, or if we were
  210                  * looking for an indirect block and we've found it.
  211                  */
  212 
  213                 metalbn = xap->in_lbn;
  214                 if ((daddr == 0 && !incore(vp, metalbn)) || metalbn == bn)
  215                         break;
  216                 /*
  217                  * If we get here, we've either got the block in the cache
  218                  * or we have a disk address for it, go fetch it.
  219                  */
  220                 if (bp)
  221                         brelse(bp);
  222 
  223                 xap->in_exists = 1;
  224                 bp = getblk(vp, metalbn, mp->mnt_stat.f_iosize, 0, 0);
  225                 if (bp == NULL) {
  226 
  227                         /*
  228                          * getblk() above returns NULL only iff we are
  229                          * pagedaemon.  See the implementation of getblk
  230                          * for detail.
  231                          */
  232 
  233                         return (ENOMEM);
  234                 }
  235                 if (bp->b_flags & (B_DONE | B_DELWRI)) {
  236                         trace(TR_BREADHIT, pack(vp, size), metalbn);
  237                 }
  238 #ifdef DIAGNOSTIC
  239                 else if (!daddr)
  240                         panic("ufs_bmaparry: indirect block not in cache");
  241 #endif
  242                 else {
  243                         trace(TR_BREADMISS, pack(vp, size), metalbn);
  244                         bp->b_blkno = blkptrtodb(ump, daddr);
  245                         bp->b_flags |= B_READ;
  246                         BIO_SETPRIO(bp, BPRIO_TIMECRITICAL);
  247                         VOP_STRATEGY(vp, bp);
  248                         curproc->p_stats->p_ru.ru_inblock++;    /* XXX */
  249                         if ((error = biowait(bp)) != 0) {
  250                                 brelse(bp);
  251                                 return (error);
  252                         }
  253                 }
  254                 if (ip->i_ump->um_fstype == UFS1) {
  255                         daddr = ufs_rw32(((int32_t *)bp->b_data)[xap->in_off],
  256                             UFS_MPNEEDSWAP(mp));
  257                         if (num == 1 && daddr && runp) {
  258                                 for (bn = xap->in_off + 1;
  259                                     bn < MNINDIR(ump) && *runp < maxrun &&
  260                                     is_sequential(ump,
  261                                         ufs_rw32(((int32_t *)bp->b_data)[bn-1],
  262                                             UFS_MPNEEDSWAP(mp)),
  263                                         ufs_rw32(((int32_t *)bp->b_data)[bn],
  264                                             UFS_MPNEEDSWAP(mp)));
  265                                     ++bn, ++*runp);
  266                         }
  267                 } else {
  268                         daddr = ufs_rw64(((int64_t *)bp->b_data)[xap->in_off],
  269                             UFS_MPNEEDSWAP(mp));
  270                         if (num == 1 && daddr && runp) {
  271                                 for (bn = xap->in_off + 1;
  272                                     bn < MNINDIR(ump) && *runp < maxrun &&
  273                                     is_sequential(ump,
  274                                         ufs_rw64(((int64_t *)bp->b_data)[bn-1],
  275                                             UFS_MPNEEDSWAP(mp)),
  276                                         ufs_rw64(((int64_t *)bp->b_data)[bn],
  277                                             UFS_MPNEEDSWAP(mp)));
  278                                     ++bn, ++*runp);
  279                         }
  280                 }
  281         }
  282         if (bp)
  283                 brelse(bp);
  284 
  285         *bnp = blkptrtodb(ump, daddr);
  286         if (*bnp == 0)
  287                 *bnp = -1;
  288         return (0);
  289 }
  290 
  291 /*
  292  * Create an array of logical block number/offset pairs which represent the
  293  * path of indirect blocks required to access a data block.  The first "pair"
  294  * contains the logical block number of the appropriate single, double or
  295  * triple indirect block and the offset into the inode indirect block array.
  296  * Note, the logical block number of the inode single/double/triple indirect
  297  * block appears twice in the array, once with the offset into the i_ffs1_ib and
  298  * once with the offset into the page itself.
  299  */
  300 int
  301 ufs_getlbns(vp, bn, ap, nump)
  302         struct vnode *vp;
  303         daddr_t bn;
  304         struct indir *ap;
  305         int *nump;
  306 {
  307         daddr_t metalbn, realbn;
  308         struct ufsmount *ump;
  309         int64_t blockcnt;
  310         int lbc;
  311         int i, numlevels, off;
  312 
  313         ump = VFSTOUFS(vp->v_mount);
  314         if (nump)
  315                 *nump = 0;
  316         numlevels = 0;
  317         realbn = bn;
  318         if (bn < 0)
  319                 bn = -bn;
  320         KASSERT(bn >= NDADDR);
  321 
  322         /* 
  323          * Determine the number of levels of indirection.  After this loop
  324          * is done, blockcnt indicates the number of data blocks possible
  325          * at the given level of indirection, and NIADDR - i is the number
  326          * of levels of indirection needed to locate the requested block.
  327          */
  328 
  329         bn -= NDADDR;
  330         for (lbc = 0, i = NIADDR;; i--, bn -= blockcnt) {
  331                 if (i == 0)
  332                         return (EFBIG);
  333 
  334                 lbc += ump->um_lognindir;
  335                 blockcnt = (int64_t)1 << lbc;
  336 
  337                 if (bn < blockcnt)
  338                         break;
  339         }
  340 
  341         /* Calculate the address of the first meta-block. */
  342         metalbn = 0;            /* XXX: gcc3 */
  343         if (realbn >= 0)
  344                 metalbn = -(realbn - bn + NIADDR - i);
  345         else
  346                 metalbn = -(-realbn - bn + NIADDR - i);
  347 
  348         /* 
  349          * At each iteration, off is the offset into the bap array which is
  350          * an array of disk addresses at the current level of indirection.
  351          * The logical block number and the offset in that block are stored
  352          * into the argument array.
  353          */
  354         ap->in_lbn = metalbn;
  355         ap->in_off = off = NIADDR - i;
  356         ap->in_exists = 0;
  357         ap++;
  358         for (++numlevels; i <= NIADDR; i++) {
  359                 /* If searching for a meta-data block, quit when found. */
  360                 if (metalbn == realbn)
  361                         break;
  362 
  363                 lbc -= ump->um_lognindir;
  364                 off = (bn >> lbc) & (MNINDIR(ump) - 1);
  365 
  366                 ++numlevels;
  367                 ap->in_lbn = metalbn;
  368                 ap->in_off = off;
  369                 ap->in_exists = 0;
  370                 ++ap;
  371 
  372                 metalbn -= -1 + ((int64_t)off << lbc);
  373         }
  374         if (nump)
  375                 *nump = numlevels;
  376         return (0);
  377 }
Cache object: bfc093cec4066f962b8a0bccc5dfe145
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]
This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.
FreeBSD/Linux Kernel Cross Reference sys/ufs/ufs/ufs_bmap.c

FreeBSD/Linux Kernel Cross Reference
sys/ufs/ufs/ufs_bmap.c
