ext2_extents.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 /*-
    2  * Copyright (c) 2010 Zheng Liu <lz@freebsd.org>
    3  * All rights reserved.
    4  *
    5  * Redistribution and use in source and binary forms, with or without
    6  * modification, are permitted provided that the following conditions
    7  * are met:
    8  * 1. Redistributions of source code must retain the above copyright
    9  *    notice, this list of conditions and the following disclaimer.
   10  * 2. Redistributions in binary form must reproduce the above copyright
   11  *    notice, this list of conditions and the following disclaimer in the
   12  *    documentation and/or other materials provided with the distribution.
   13  *
   14  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
   15  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   17  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
   18  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
   19  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
   20  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
   21  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   22  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
   23  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
   24  * SUCH DAMAGE.
   25  *
   26  * $FreeBSD$
   27  */
   28 
   29 #include <sys/param.h>
   30 #include <sys/systm.h>
   31 #include <sys/types.h>
   32 #include <sys/kernel.h>
   33 #include <sys/malloc.h>
   34 #include <sys/vnode.h>
   35 #include <sys/bio.h>
   36 #include <sys/buf.h>
   37 #include <sys/conf.h>
   38 
   39 #include <fs/ext2fs/ext2_mount.h>
   40 #include <fs/ext2fs/fs.h>
   41 #include <fs/ext2fs/inode.h>
   42 #include <fs/ext2fs/ext2fs.h>
   43 #include <fs/ext2fs/ext2_extents.h>
   44 #include <fs/ext2fs/ext2_extern.h>
   45 
   46 static bool
   47 ext4_ext_binsearch_index(struct inode *ip, struct ext4_extent_path *path,
   48     daddr_t lbn, daddr_t *first_lbn, daddr_t *last_lbn){
   49         struct ext4_extent_header *ehp = path->ep_header;
   50         struct ext4_extent_index *first, *last, *l, *r, *m;
   51 
   52         first = (struct ext4_extent_index *)(char *)(ehp + 1);
   53         last = first + ehp->eh_ecount - 1;
   54         l = first;
   55         r = last;
   56         while (l <= r) {
   57                 m = l + (r - l) / 2;
   58                 if (lbn < m->ei_blk)
   59                         r = m - 1;
   60                 else
   61                         l = m + 1;
   62         }
   63 
   64         if (l == first) {
   65                 path->ep_sparse_ext.e_blk = *first_lbn;
   66                 path->ep_sparse_ext.e_len = first->ei_blk - *first_lbn;
   67                 path->ep_sparse_ext.e_start_hi = 0;
   68                 path->ep_sparse_ext.e_start_lo = 0;
   69                 path->ep_is_sparse = true;
   70                 return (true);
   71         }
   72         path->ep_index = l - 1;
   73         *first_lbn = path->ep_index->ei_blk;
   74         if (path->ep_index < last)
   75                 *last_lbn = l->ei_blk - 1;
   76         return (false);
   77 }
   78 
   79 static void
   80 ext4_ext_binsearch(struct inode *ip, struct ext4_extent_path *path, daddr_t lbn,
   81     daddr_t first_lbn, daddr_t last_lbn)
   82 {
   83         struct ext4_extent_header *ehp = path->ep_header;
   84         struct ext4_extent *first, *l, *r, *m;
   85 
   86         if (ehp->eh_ecount == 0)
   87                 return;
   88 
   89         first = (struct ext4_extent *)(char *)(ehp + 1);
   90         l = first;
   91         r = first + ehp->eh_ecount - 1;
   92         while (l <= r) {
   93                 m = l + (r - l) / 2;
   94                 if (lbn < m->e_blk)
   95                         r = m - 1;
   96                 else
   97                         l = m + 1;
   98         }
   99 
  100         if (l == first) {
  101                 path->ep_sparse_ext.e_blk = first_lbn;
  102                 path->ep_sparse_ext.e_len = first->e_blk - first_lbn;
  103                 path->ep_sparse_ext.e_start_hi = 0;
  104                 path->ep_sparse_ext.e_start_lo = 0;
  105                 path->ep_is_sparse = true;
  106                 return;
  107         }
  108         path->ep_ext = l - 1;
  109         if (path->ep_ext->e_blk + path->ep_ext->e_len <= lbn) {
  110                 path->ep_sparse_ext.e_blk = path->ep_ext->e_blk +
  111                     path->ep_ext->e_len;
  112                 if (l <= (first + ehp->eh_ecount - 1))
  113                         path->ep_sparse_ext.e_len = l->e_blk -
  114                             path->ep_sparse_ext.e_blk;
  115                 else
  116                         path->ep_sparse_ext.e_len = last_lbn -
  117                             path->ep_sparse_ext.e_blk + 1;
  118                 path->ep_sparse_ext.e_start_hi = 0;
  119                 path->ep_sparse_ext.e_start_lo = 0;
  120                 path->ep_is_sparse = true;
  121         }
  122 }
  123 
  124 /*
  125  * Find a block in ext4 extent cache.
  126  */
  127 int
  128 ext4_ext_in_cache(struct inode *ip, daddr_t lbn, struct ext4_extent *ep)
  129 {
  130         struct ext4_extent_cache *ecp;
  131         int ret = EXT4_EXT_CACHE_NO;
  132 
  133         ecp = &ip->i_ext_cache;
  134 
  135         /* cache is invalid */
  136         if (ecp->ec_type == EXT4_EXT_CACHE_NO)
  137                 return (ret);
  138 
  139         if (lbn >= ecp->ec_blk && lbn < ecp->ec_blk + ecp->ec_len) {
  140                 ep->e_blk = ecp->ec_blk;
  141                 ep->e_start_lo = ecp->ec_start & 0xffffffff;
  142                 ep->e_start_hi = ecp->ec_start >> 32 & 0xffff;
  143                 ep->e_len = ecp->ec_len;
  144                 ret = ecp->ec_type;
  145         }
  146         return (ret);
  147 }
  148 
  149 /*
  150  * Put an ext4_extent structure in ext4 cache.
  151  */
  152 void
  153 ext4_ext_put_cache(struct inode *ip, struct ext4_extent *ep, int type)
  154 {
  155         struct ext4_extent_cache *ecp;
  156 
  157         ecp = &ip->i_ext_cache;
  158         ecp->ec_type = type;
  159         ecp->ec_blk = ep->e_blk;
  160         ecp->ec_len = ep->e_len;
  161         ecp->ec_start = (daddr_t)ep->e_start_hi << 32 | ep->e_start_lo;
  162 }
  163 
  164 /*
  165  * Find an extent.
  166  */
  167 struct ext4_extent_path *
  168 ext4_ext_find_extent(struct m_ext2fs *fs, struct inode *ip,
  169     daddr_t lbn, struct ext4_extent_path *path)
  170 {
  171         struct ext4_extent_header *ehp;
  172         uint16_t i;
  173         int error, size;
  174         daddr_t nblk;
  175 
  176         ehp = (struct ext4_extent_header *)(char *)ip->i_db;
  177 
  178         if (ehp->eh_magic != EXT4_EXT_MAGIC)
  179                 return (NULL);
  180 
  181         path->ep_header = ehp;
  182 
  183         daddr_t first_lbn = 0;
  184         daddr_t last_lbn = lblkno(ip->i_e2fs, ip->i_size);
  185 
  186         for (i = ehp->eh_depth; i != 0; --i) {
  187                 path->ep_depth = i;
  188                 path->ep_ext = NULL;
  189                 if (ext4_ext_binsearch_index(ip, path, lbn, &first_lbn,
  190                     &last_lbn)) {
  191                         return (path);
  192                 }
  193 
  194                 nblk = (daddr_t)path->ep_index->ei_leaf_hi << 32 |
  195                     path->ep_index->ei_leaf_lo;
  196                 size = blksize(fs, ip, nblk);
  197                 if (path->ep_bp != NULL) {
  198                         brelse(path->ep_bp);
  199                         path->ep_bp = NULL;
  200                 }
  201                 error = bread(ip->i_devvp, fsbtodb(fs, nblk), size, NOCRED,
  202                     &path->ep_bp);
  203                 if (error) {
  204                         brelse(path->ep_bp);
  205                         path->ep_bp = NULL;
  206                         return (NULL);
  207                 }
  208                 ehp = (struct ext4_extent_header *)path->ep_bp->b_data;
  209                 path->ep_header = ehp;
  210         }
  211 
  212         path->ep_depth = i;
  213         path->ep_ext = NULL;
  214         path->ep_index = NULL;
  215         path->ep_is_sparse = false;
  216 
  217         ext4_ext_binsearch(ip, path, lbn, first_lbn, last_lbn);
  218         return (path);
  219 }

Cache object: 525d46e66bfd48185426df9b68cc43bb

[ 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/fs/ext2fs/ext2_extents.c

FreeBSD/Linux Kernel Cross Reference
sys/fs/ext2fs/ext2_extents.c