1254260Spfg/*- 2254260Spfg * Copyright (c) 2010 Zheng Liu <lz@freebsd.org> 3254260Spfg * All rights reserved. 4254260Spfg * 5254260Spfg * Redistribution and use in source and binary forms, with or without 6254260Spfg * modification, are permitted provided that the following conditions 7254260Spfg * are met: 8254260Spfg * 1. Redistributions of source code must retain the above copyright 9254260Spfg * notice, this list of conditions and the following disclaimer. 10254260Spfg * 2. Redistributions in binary form must reproduce the above copyright 11254260Spfg * notice, this list of conditions and the following disclaimer in the 12254260Spfg * documentation and/or other materials provided with the distribution. 13254260Spfg * 14254260Spfg * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 15254260Spfg * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 16254260Spfg * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 17254260Spfg * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 18254260Spfg * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 19254260Spfg * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 20254260Spfg * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 21254260Spfg * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 22254260Spfg * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 23254260Spfg * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 24254260Spfg * SUCH DAMAGE. 25254260Spfg * 26254260Spfg * $FreeBSD: releng/10.2/sys/fs/ext2fs/ext2_extents.c 278096 2015-02-02 15:52:11Z pfg $ 27254260Spfg */ 28254260Spfg 29254260Spfg#include <sys/param.h> 30254260Spfg#include <sys/systm.h> 31254260Spfg#include <sys/types.h> 32254260Spfg#include <sys/kernel.h> 33254260Spfg#include <sys/malloc.h> 34254260Spfg#include <sys/vnode.h> 35254260Spfg#include <sys/bio.h> 36254260Spfg#include <sys/buf.h> 37254260Spfg#include <sys/conf.h> 38254260Spfg 39254260Spfg#include <fs/ext2fs/ext2_mount.h> 40254260Spfg#include <fs/ext2fs/fs.h> 41254260Spfg#include <fs/ext2fs/inode.h> 42254260Spfg#include <fs/ext2fs/ext2fs.h> 43254260Spfg#include <fs/ext2fs/ext2_extents.h> 44254260Spfg#include <fs/ext2fs/ext2_extern.h> 45254260Spfg 46254260Spfgstatic void ext4_ext_binsearch_index(struct inode *ip, struct ext4_extent_path 47254260Spfg *path, daddr_t lbn) 48254260Spfg{ 49254260Spfg struct ext4_extent_header *ehp = path->ep_header; 50254260Spfg struct ext4_extent_index *l, *r, *m; 51254260Spfg 52254260Spfg l = (struct ext4_extent_index *)(char *)(ehp + 1); 53254260Spfg r = (struct ext4_extent_index *)(char *)(ehp + 1) + ehp->eh_ecount - 1; 54254260Spfg while (l <= r) { 55254260Spfg m = l + (r - l) / 2; 56254260Spfg if (lbn < m->ei_blk) 57254260Spfg r = m - 1; 58254260Spfg else 59254260Spfg l = m + 1; 60254260Spfg } 61254260Spfg 62254260Spfg path->ep_index = l - 1; 63254260Spfg} 64254260Spfg 65254260Spfgstatic void 66254260Spfgext4_ext_binsearch(struct inode *ip, struct ext4_extent_path *path, daddr_t lbn) 67254260Spfg{ 68254260Spfg struct ext4_extent_header *ehp = path->ep_header; 69254260Spfg struct ext4_extent *l, *r, *m; 70254260Spfg 71254260Spfg if (ehp->eh_ecount == 0) 72254260Spfg return; 73254260Spfg 74254260Spfg l = (struct ext4_extent *)(char *)(ehp + 1); 75254260Spfg r = (struct ext4_extent *)(char *)(ehp + 1) + ehp->eh_ecount - 1; 76254260Spfg while (l <= r) { 77254260Spfg m = l + (r - l) / 2; 78254260Spfg if (lbn < m->e_blk) 79254260Spfg r = m - 1; 80254260Spfg else 81254260Spfg l = m + 1; 82254260Spfg } 83254260Spfg 84254260Spfg path->ep_ext = l - 1; 85254260Spfg} 86254260Spfg 87254260Spfg/* 88254260Spfg * Find a block in ext4 extent cache. 89254260Spfg */ 90254260Spfgint 91254260Spfgext4_ext_in_cache(struct inode *ip, daddr_t lbn, struct ext4_extent *ep) 92254260Spfg{ 93254260Spfg struct ext4_extent_cache *ecp; 94254260Spfg int ret = EXT4_EXT_CACHE_NO; 95254260Spfg 96254260Spfg ecp = &ip->i_ext_cache; 97254260Spfg 98254260Spfg /* cache is invalid */ 99254260Spfg if (ecp->ec_type == EXT4_EXT_CACHE_NO) 100254260Spfg return (ret); 101254260Spfg 102254260Spfg if (lbn >= ecp->ec_blk && lbn < ecp->ec_blk + ecp->ec_len) { 103254260Spfg ep->e_blk = ecp->ec_blk; 104254260Spfg ep->e_start_lo = ecp->ec_start & 0xffffffff; 105254260Spfg ep->e_start_hi = ecp->ec_start >> 32 & 0xffff; 106254260Spfg ep->e_len = ecp->ec_len; 107254260Spfg ret = ecp->ec_type; 108254260Spfg } 109254260Spfg return (ret); 110254260Spfg} 111254260Spfg 112254260Spfg/* 113254260Spfg * Put an ext4_extent structure in ext4 cache. 114254260Spfg */ 115254260Spfgvoid 116254260Spfgext4_ext_put_cache(struct inode *ip, struct ext4_extent *ep, int type) 117254260Spfg{ 118254260Spfg struct ext4_extent_cache *ecp; 119254260Spfg 120254260Spfg ecp = &ip->i_ext_cache; 121254260Spfg ecp->ec_type = type; 122254260Spfg ecp->ec_blk = ep->e_blk; 123254260Spfg ecp->ec_len = ep->e_len; 124254260Spfg ecp->ec_start = (daddr_t)ep->e_start_hi << 32 | ep->e_start_lo; 125254260Spfg} 126254260Spfg 127254260Spfg/* 128254260Spfg * Find an extent. 129254260Spfg */ 130254260Spfgstruct ext4_extent_path * 131254260Spfgext4_ext_find_extent(struct m_ext2fs *fs, struct inode *ip, 132254260Spfg daddr_t lbn, struct ext4_extent_path *path) 133254260Spfg{ 134254260Spfg struct ext4_extent_header *ehp; 135254260Spfg uint16_t i; 136254260Spfg int error, size; 137254260Spfg daddr_t nblk; 138254260Spfg 139254260Spfg ehp = (struct ext4_extent_header *)(char *)ip->i_db; 140254260Spfg 141254260Spfg if (ehp->eh_magic != EXT4_EXT_MAGIC) 142254260Spfg return (NULL); 143254260Spfg 144254260Spfg path->ep_header = ehp; 145254260Spfg 146254260Spfg for (i = ehp->eh_depth; i != 0; --i) { 147254260Spfg ext4_ext_binsearch_index(ip, path, lbn); 148254260Spfg path->ep_depth = 0; 149254260Spfg path->ep_ext = NULL; 150254260Spfg 151254260Spfg nblk = (daddr_t)path->ep_index->ei_leaf_hi << 32 | 152254260Spfg path->ep_index->ei_leaf_lo; 153254260Spfg size = blksize(fs, ip, nblk); 154254260Spfg if (path->ep_bp != NULL) { 155254260Spfg brelse(path->ep_bp); 156254260Spfg path->ep_bp = NULL; 157254260Spfg } 158254260Spfg error = bread(ip->i_devvp, fsbtodb(fs, nblk), size, NOCRED, 159254260Spfg &path->ep_bp); 160254260Spfg if (error) { 161254260Spfg brelse(path->ep_bp); 162254260Spfg path->ep_bp = NULL; 163254260Spfg return (NULL); 164254260Spfg } 165254260Spfg ehp = (struct ext4_extent_header *)path->ep_bp->b_data; 166254260Spfg path->ep_header = ehp; 167254260Spfg } 168254260Spfg 169254260Spfg path->ep_depth = i; 170254260Spfg path->ep_ext = NULL; 171254260Spfg path->ep_index = NULL; 172254260Spfg 173254260Spfg ext4_ext_binsearch(ip, path, lbn); 174254260Spfg return (path); 175254260Spfg} 176