/*      $NetBSD: ext2fs_extents.c,v 1.3 2016/08/13 07:40:10 christos Exp $      */

/*-
* Copyright (c) 2010 Zheng Liu <[email protected]>
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
*    notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
*    notice, this list of conditions and the following disclaimer in the
*    documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*
* $FreeBSD: head/sys/fs/ext2fs/ext2_extents.c 295523 2016-02-11 15:27:14Z pfg $
*/

#include <sys/cdefs.h>
__KERNEL_RCSID(0, "$NetBSD: ext2fs_extents.c,v 1.3 2016/08/13 07:40:10 christos Exp $");

#include <sys/param.h>
#include <sys/systm.h>
#include <sys/resourcevar.h>
#include <sys/kernel.h>
#include <sys/file.h>
#include <sys/stat.h>
#include <sys/buf.h>
#include <sys/proc.h>
#include <sys/mount.h>
#include <sys/vnode.h>
#include <sys/signalvar.h>
#include <sys/kauth.h>

#include <ufs/ufs/inode.h>
#include <ufs/ufs/ufsmount.h>
#include <ufs/ufs/ufs_extern.h>


#include <ufs/ext2fs/ext2fs.h>
#include <ufs/ext2fs/ext2fs_extents.h>
#include <ufs/ext2fs/ext2fs_extern.h>



static bool
ext4_ext_binsearch_index(struct inode *ip, struct ext4_extent_path *path,
               daddr_t lbn, daddr_t *first_lbn, daddr_t *last_lbn)
{
       struct ext4_extent_header *ehp = path->ep_header;
       struct ext4_extent_index *first, *last, *l, *r, *m;

       first = (struct ext4_extent_index *)(char *)(ehp + 1);
       last = first + ehp->eh_ecount - 1;
       l = first;
       r = last;
       while (l <= r) {
               m = l + (r - l) / 2;
               if (lbn < m->ei_blk)
                       r = m - 1;
               else
                       l = m + 1;
       }

       if (l == first) {
               path->ep_sparse_ext.e_blk = *first_lbn;
               path->ep_sparse_ext.e_len = first->ei_blk - *first_lbn;
               path->ep_sparse_ext.e_start_hi = 0;
               path->ep_sparse_ext.e_start_lo = 0;
               path->ep_is_sparse = true;
               return true;
       }
       path->ep_index = l - 1;
       *first_lbn = path->ep_index->ei_blk;
       if (path->ep_index < last)
               *last_lbn = l->ei_blk - 1;
       return false;
}

static void
ext4_ext_binsearch(struct inode *ip, struct ext4_extent_path *path, daddr_t lbn,
               daddr_t first_lbn, daddr_t last_lbn)
{
       struct ext4_extent_header *ehp = path->ep_header;
       struct ext4_extent *first, *l, *r, *m;

       if (ehp->eh_ecount == 0)
               return;

       first = (struct ext4_extent *)(char *)(ehp + 1);
       l = first;
       r = first + ehp->eh_ecount - 1;
       while (l <= r) {
               m = l + (r - l) / 2;
               if (lbn < m->e_blk)
                       r = m - 1;
               else
                       l = m + 1;
       }

       if (l == first) {
               path->ep_sparse_ext.e_blk = first_lbn;
               path->ep_sparse_ext.e_len = first->e_blk - first_lbn;
               path->ep_sparse_ext.e_start_hi = 0;
               path->ep_sparse_ext.e_start_lo = 0;
               path->ep_is_sparse = true;
               return;
       }
       path->ep_ext = l - 1;
       if (path->ep_ext->e_blk + path->ep_ext->e_len <= lbn) {
               path->ep_sparse_ext.e_blk = path->ep_ext->e_blk +
                   path->ep_ext->e_len;
               if (l <= (first + ehp->eh_ecount - 1))
                       path->ep_sparse_ext.e_len = l->e_blk -
                           path->ep_sparse_ext.e_blk;
               else
                       path->ep_sparse_ext.e_len = last_lbn -
                           path->ep_sparse_ext.e_blk + 1;
               path->ep_sparse_ext.e_start_hi = 0;
               path->ep_sparse_ext.e_start_lo = 0;
               path->ep_is_sparse = true;
       }
}

/*
* Find a block in ext4 extent cache.
*/
int
ext4_ext_in_cache(struct inode *ip, daddr_t lbn, struct ext4_extent *ep)
{
       struct ext4_extent_cache *ecp;
       int ret = EXT4_EXT_CACHE_NO;

       ecp = &ip->inode_ext.e2fs.i_ext_cache;

       /* cache is invalid */
       if (ecp->ec_type == EXT4_EXT_CACHE_NO)
               return ret;

       if (lbn >= ecp->ec_blk && lbn < ecp->ec_blk + ecp->ec_len) {
               ep->e_blk = ecp->ec_blk;
               ep->e_start_lo = ecp->ec_start & 0xffffffff;
               ep->e_start_hi = ecp->ec_start >> 32 & 0xffff;
               ep->e_len = ecp->ec_len;
               ret = ecp->ec_type;
       }
       return ret;
}

/*
* Put an ext4_extent structure in ext4 cache.
*/
void
ext4_ext_put_cache(struct inode *ip, struct ext4_extent *ep, int type)
{
       struct ext4_extent_cache *ecp;

       ecp = &ip->inode_ext.e2fs.i_ext_cache;
       ecp->ec_type = type;
       ecp->ec_blk = ep->e_blk;
       ecp->ec_len = ep->e_len;
       ecp->ec_start = (daddr_t)ep->e_start_hi << 32 | ep->e_start_lo;
}

/*
* Find an extent.
*/
struct ext4_extent_path *
ext4_ext_find_extent(struct m_ext2fs *fs, struct inode *ip,
                    daddr_t lbn, struct ext4_extent_path *path)
{
       struct ext4_extent_header *ehp;
       uint16_t i;
       int error, size;
       daddr_t nblk;

       ehp = (struct ext4_extent_header *)ip->i_din.e2fs_din->e2di_blocks;

       if (ehp->eh_magic != EXT4_EXT_MAGIC)
               return NULL;

       path->ep_header = ehp;

       daddr_t first_lbn = 0;
       daddr_t last_lbn = lblkno(ip->i_e2fs, ip->i_size);

       for (i = ehp->eh_depth; i != 0; --i) {
               path->ep_depth = i;
               path->ep_ext = NULL;
               if (ext4_ext_binsearch_index(ip, path, lbn, &first_lbn,
                   &last_lbn)) {
                       return path;
               }

               nblk = (daddr_t)path->ep_index->ei_leaf_hi << 32 |
                   path->ep_index->ei_leaf_lo;
               size = blksize(fs, ip, nblk);
               if (path->ep_bp != NULL) {
                       brelse(path->ep_bp, 0);
                       path->ep_bp = NULL;
               }
               error = bread(ip->i_devvp, fsbtodb(fs, nblk), size, 0,
                           &path->ep_bp);
               if (error) {
                       brelse(path->ep_bp, 0);
                       path->ep_bp = NULL;
                       return NULL;
               }
               ehp = (struct ext4_extent_header *)path->ep_bp->b_data;
               path->ep_header = ehp;
       }

       path->ep_depth = i;
       path->ep_ext = NULL;
       path->ep_index = NULL;
       path->ep_is_sparse = false;

       ext4_ext_binsearch(ip, path, lbn, first_lbn, last_lbn);
       return path;
}

You are viewing proxied material from ftp.icm.edu.pl. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.