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: releng/11.0/sys/fs/ext2fs/ext2_extents.c 295523 2016-02-11 15:27:14Z pfg $
   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 {
   50         struct ext4_extent_header *ehp = path->ep_header;
   51         struct ext4_extent_index *first, *last, *l, *r, *m;
   52 
   53         first = (struct ext4_extent_index *)(char *)(ehp + 1);
   54         last = first + ehp->eh_ecount - 1;
   55         l = first;
   56         r = last;
   57         while (l <= r) {
   58                 m = l + (r - l) / 2;
   59                 if (lbn < m->ei_blk)
   60                         r = m - 1;
   61                 else
   62                         l = m + 1;
   63         }
   64 
   65         if (l == first) {
   66                 path->ep_sparse_ext.e_blk = *first_lbn;
   67                 path->ep_sparse_ext.e_len = first->ei_blk - *first_lbn;
   68                 path->ep_sparse_ext.e_start_hi = 0;
   69                 path->ep_sparse_ext.e_start_lo = 0;
   70                 path->ep_is_sparse = true;
   71                 return (true);
   72         }
   73         path->ep_index = l - 1;
   74         *first_lbn = path->ep_index->ei_blk;
   75         if (path->ep_index < last)
   76                 *last_lbn = l->ei_blk - 1;
   77         return (false);
   78 }
   79 
   80 static void
   81 ext4_ext_binsearch(struct inode *ip, struct ext4_extent_path *path, daddr_t lbn,
   82                 daddr_t first_lbn, daddr_t last_lbn)
   83 {
   84         struct ext4_extent_header *ehp = path->ep_header;
   85         struct ext4_extent *first, *l, *r, *m;
   86 
   87         if (ehp->eh_ecount == 0)
   88                 return;
   89 
   90         first = (struct ext4_extent *)(char *)(ehp + 1);
   91         l = first;
   92         r = first + ehp->eh_ecount - 1;
   93         while (l <= r) {
   94                 m = l + (r - l) / 2;
   95                 if (lbn < m->e_blk)
   96                         r = m - 1;
   97                 else
   98                         l = m + 1;
   99         }
  100 
  101         if (l == first) {
  102                 path->ep_sparse_ext.e_blk = first_lbn;
  103                 path->ep_sparse_ext.e_len = first->e_blk - first_lbn;
  104                 path->ep_sparse_ext.e_start_hi = 0;
  105                 path->ep_sparse_ext.e_start_lo = 0;
  106                 path->ep_is_sparse = true;
  107                 return;
  108         }
  109         path->ep_ext = l - 1;
  110         if (path->ep_ext->e_blk + path->ep_ext->e_len <= lbn) {
  111                 path->ep_sparse_ext.e_blk = path->ep_ext->e_blk +
  112                     path->ep_ext->e_len;
  113                 if (l <= (first + ehp->eh_ecount - 1))
  114                         path->ep_sparse_ext.e_len = l->e_blk -
  115                             path->ep_sparse_ext.e_blk;
  116                 else
  117                         path->ep_sparse_ext.e_len = last_lbn -
  118                             path->ep_sparse_ext.e_blk + 1;
  119                 path->ep_sparse_ext.e_start_hi = 0;
  120                 path->ep_sparse_ext.e_start_lo = 0;
  121                 path->ep_is_sparse = true;
  122         }
  123 }
  124 
  125 /*
  126  * Find a block in ext4 extent cache.
  127  */
  128 int
  129 ext4_ext_in_cache(struct inode *ip, daddr_t lbn, struct ext4_extent *ep)
  130 {
  131         struct ext4_extent_cache *ecp;
  132         int ret = EXT4_EXT_CACHE_NO;
  133 
  134         ecp = &ip->i_ext_cache;
  135 
  136         /* cache is invalid */
  137         if (ecp->ec_type == EXT4_EXT_CACHE_NO)
  138                 return (ret);
  139 
  140         if (lbn >= ecp->ec_blk && lbn < ecp->ec_blk + ecp->ec_len) {
  141                 ep->e_blk = ecp->ec_blk;
  142                 ep->e_start_lo = ecp->ec_start & 0xffffffff;
  143                 ep->e_start_hi = ecp->ec_start >> 32 & 0xffff;
  144                 ep->e_len = ecp->ec_len;
  145                 ret = ecp->ec_type;
  146         }
  147         return (ret);
  148 }
  149 
  150 /*
  151  * Put an ext4_extent structure in ext4 cache.
  152  */
  153 void
  154 ext4_ext_put_cache(struct inode *ip, struct ext4_extent *ep, int type)
  155 {
  156         struct ext4_extent_cache *ecp;
  157 
  158         ecp = &ip->i_ext_cache;
  159         ecp->ec_type = type;
  160         ecp->ec_blk = ep->e_blk;
  161         ecp->ec_len = ep->e_len;
  162         ecp->ec_start = (daddr_t)ep->e_start_hi << 32 | ep->e_start_lo;
  163 }
  164 
  165 /*
  166  * Find an extent.
  167  */
  168 struct ext4_extent_path *
  169 ext4_ext_find_extent(struct m_ext2fs *fs, struct inode *ip,
  170                      daddr_t lbn, struct ext4_extent_path *path)
  171 {
  172         struct ext4_extent_header *ehp;
  173         uint16_t i;
  174         int error, size;
  175         daddr_t nblk;
  176 
  177         ehp = (struct ext4_extent_header *)(char *)ip->i_db;
  178 
  179         if (ehp->eh_magic != EXT4_EXT_MAGIC)
  180                 return (NULL);
  181 
  182         path->ep_header = ehp;
  183 
  184         daddr_t first_lbn = 0;
  185         daddr_t last_lbn = lblkno(ip->i_e2fs, ip->i_size);
  186 
  187         for (i = ehp->eh_depth; i != 0; --i) {
  188                 path->ep_depth = i;
  189                 path->ep_ext = NULL;
  190                 if (ext4_ext_binsearch_index(ip, path, lbn, &first_lbn,
  191                     &last_lbn)) {
  192                         return (path);
  193                 }
  194 
  195                 nblk = (daddr_t)path->ep_index->ei_leaf_hi << 32 |
  196                     path->ep_index->ei_leaf_lo;
  197                 size = blksize(fs, ip, nblk);
  198                 if (path->ep_bp != NULL) {
  199                         brelse(path->ep_bp);
  200                         path->ep_bp = NULL;
  201                 }
  202                 error = bread(ip->i_devvp, fsbtodb(fs, nblk), size, NOCRED,
  203                             &path->ep_bp);
  204                 if (error) {
  205                         brelse(path->ep_bp);
  206                         path->ep_bp = NULL;
  207                         return (NULL);
  208                 }
  209                 ehp = (struct ext4_extent_header *)path->ep_bp->b_data;
  210                 path->ep_header = ehp;
  211         }
  212 
  213         path->ep_depth = i;
  214         path->ep_ext = NULL;
  215         path->ep_index = NULL;
  216         path->ep_is_sparse = false;
  217 
  218         ext4_ext_binsearch(ip, path, lbn, first_lbn, last_lbn);
  219         return (path);
  220 }

Cache object: 5570677ce7607c7893e709adf8cdc9fc

[ 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