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/11.0/sys/fs/ext2fs/ext2_extents.c 295523 2016-02-11 15:27:14Z 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 46295523Spfgstatic bool 47295494Spfgext4_ext_binsearch_index(struct inode *ip, struct ext4_extent_path *path, 48295494Spfg daddr_t lbn, daddr_t *first_lbn, daddr_t *last_lbn) 49254260Spfg{ 50254260Spfg struct ext4_extent_header *ehp = path->ep_header; 51295494Spfg struct ext4_extent_index *first, *last, *l, *r, *m; 52254260Spfg 53295494Spfg first = (struct ext4_extent_index *)(char *)(ehp + 1); 54295494Spfg last = first + ehp->eh_ecount - 1; 55295494Spfg l = first; 56295494Spfg r = last; 57254260Spfg while (l <= r) { 58254260Spfg m = l + (r - l) / 2; 59254260Spfg if (lbn < m->ei_blk) 60254260Spfg r = m - 1; 61254260Spfg else 62254260Spfg l = m + 1; 63254260Spfg } 64254260Spfg 65295494Spfg if (l == first) { 66295494Spfg path->ep_sparse_ext.e_blk = *first_lbn; 67295494Spfg path->ep_sparse_ext.e_len = first->ei_blk - *first_lbn; 68295494Spfg path->ep_sparse_ext.e_start_hi = 0; 69295494Spfg path->ep_sparse_ext.e_start_lo = 0; 70295523Spfg path->ep_is_sparse = true; 71295523Spfg return (true); 72295494Spfg } 73254260Spfg path->ep_index = l - 1; 74295494Spfg *first_lbn = path->ep_index->ei_blk; 75295494Spfg if (path->ep_index < last) 76295494Spfg *last_lbn = l->ei_blk - 1; 77295523Spfg return (false); 78254260Spfg} 79254260Spfg 80254260Spfgstatic void 81295494Spfgext4_ext_binsearch(struct inode *ip, struct ext4_extent_path *path, daddr_t lbn, 82295494Spfg daddr_t first_lbn, daddr_t last_lbn) 83254260Spfg{ 84254260Spfg struct ext4_extent_header *ehp = path->ep_header; 85293680Spfg struct ext4_extent *first, *l, *r, *m; 86254260Spfg 87254260Spfg if (ehp->eh_ecount == 0) 88254260Spfg return; 89254260Spfg 90293680Spfg first = (struct ext4_extent *)(char *)(ehp + 1); 91293680Spfg l = first; 92293680Spfg r = first + ehp->eh_ecount - 1; 93254260Spfg while (l <= r) { 94254260Spfg m = l + (r - l) / 2; 95254260Spfg if (lbn < m->e_blk) 96254260Spfg r = m - 1; 97254260Spfg else 98254260Spfg l = m + 1; 99254260Spfg } 100254260Spfg 101293680Spfg if (l == first) { 102295494Spfg path->ep_sparse_ext.e_blk = first_lbn; 103295494Spfg path->ep_sparse_ext.e_len = first->e_blk - first_lbn; 104293680Spfg path->ep_sparse_ext.e_start_hi = 0; 105293680Spfg path->ep_sparse_ext.e_start_lo = 0; 106295523Spfg path->ep_is_sparse = true; 107293680Spfg return; 108293680Spfg } 109254260Spfg path->ep_ext = l - 1; 110293680Spfg if (path->ep_ext->e_blk + path->ep_ext->e_len <= lbn) { 111295494Spfg path->ep_sparse_ext.e_blk = path->ep_ext->e_blk + 112295494Spfg path->ep_ext->e_len; 113293680Spfg if (l <= (first + ehp->eh_ecount - 1)) 114295494Spfg path->ep_sparse_ext.e_len = l->e_blk - 115295494Spfg path->ep_sparse_ext.e_blk; 116295494Spfg else 117295494Spfg path->ep_sparse_ext.e_len = last_lbn - 118295494Spfg path->ep_sparse_ext.e_blk + 1; 119293680Spfg path->ep_sparse_ext.e_start_hi = 0; 120293680Spfg path->ep_sparse_ext.e_start_lo = 0; 121295523Spfg path->ep_is_sparse = true; 122293680Spfg } 123254260Spfg} 124254260Spfg 125254260Spfg/* 126254260Spfg * Find a block in ext4 extent cache. 127254260Spfg */ 128254260Spfgint 129254260Spfgext4_ext_in_cache(struct inode *ip, daddr_t lbn, struct ext4_extent *ep) 130254260Spfg{ 131254260Spfg struct ext4_extent_cache *ecp; 132254260Spfg int ret = EXT4_EXT_CACHE_NO; 133254260Spfg 134254260Spfg ecp = &ip->i_ext_cache; 135254260Spfg 136254260Spfg /* cache is invalid */ 137254260Spfg if (ecp->ec_type == EXT4_EXT_CACHE_NO) 138254260Spfg return (ret); 139254260Spfg 140254260Spfg if (lbn >= ecp->ec_blk && lbn < ecp->ec_blk + ecp->ec_len) { 141254260Spfg ep->e_blk = ecp->ec_blk; 142254260Spfg ep->e_start_lo = ecp->ec_start & 0xffffffff; 143254260Spfg ep->e_start_hi = ecp->ec_start >> 32 & 0xffff; 144254260Spfg ep->e_len = ecp->ec_len; 145254260Spfg ret = ecp->ec_type; 146254260Spfg } 147254260Spfg return (ret); 148254260Spfg} 149254260Spfg 150254260Spfg/* 151254260Spfg * Put an ext4_extent structure in ext4 cache. 152254260Spfg */ 153254260Spfgvoid 154254260Spfgext4_ext_put_cache(struct inode *ip, struct ext4_extent *ep, int type) 155254260Spfg{ 156254260Spfg struct ext4_extent_cache *ecp; 157254260Spfg 158254260Spfg ecp = &ip->i_ext_cache; 159254260Spfg ecp->ec_type = type; 160254260Spfg ecp->ec_blk = ep->e_blk; 161254260Spfg ecp->ec_len = ep->e_len; 162254260Spfg ecp->ec_start = (daddr_t)ep->e_start_hi << 32 | ep->e_start_lo; 163254260Spfg} 164254260Spfg 165254260Spfg/* 166254260Spfg * Find an extent. 167254260Spfg */ 168254260Spfgstruct ext4_extent_path * 169254260Spfgext4_ext_find_extent(struct m_ext2fs *fs, struct inode *ip, 170254260Spfg daddr_t lbn, struct ext4_extent_path *path) 171254260Spfg{ 172254260Spfg struct ext4_extent_header *ehp; 173254260Spfg uint16_t i; 174254260Spfg int error, size; 175254260Spfg daddr_t nblk; 176254260Spfg 177254260Spfg ehp = (struct ext4_extent_header *)(char *)ip->i_db; 178254260Spfg 179254260Spfg if (ehp->eh_magic != EXT4_EXT_MAGIC) 180254260Spfg return (NULL); 181254260Spfg 182254260Spfg path->ep_header = ehp; 183254260Spfg 184295494Spfg daddr_t first_lbn = 0; 185295494Spfg daddr_t last_lbn = lblkno(ip->i_e2fs, ip->i_size); 186295494Spfg 187254260Spfg for (i = ehp->eh_depth; i != 0; --i) { 188295494Spfg path->ep_depth = i; 189254260Spfg path->ep_ext = NULL; 190295494Spfg if (ext4_ext_binsearch_index(ip, path, lbn, &first_lbn, 191295494Spfg &last_lbn)) { 192295494Spfg return (path); 193295494Spfg } 194254260Spfg 195254260Spfg nblk = (daddr_t)path->ep_index->ei_leaf_hi << 32 | 196254260Spfg path->ep_index->ei_leaf_lo; 197254260Spfg size = blksize(fs, ip, nblk); 198254260Spfg if (path->ep_bp != NULL) { 199254260Spfg brelse(path->ep_bp); 200254260Spfg path->ep_bp = NULL; 201254260Spfg } 202254260Spfg error = bread(ip->i_devvp, fsbtodb(fs, nblk), size, NOCRED, 203254260Spfg &path->ep_bp); 204254260Spfg if (error) { 205254260Spfg brelse(path->ep_bp); 206254260Spfg path->ep_bp = NULL; 207254260Spfg return (NULL); 208254260Spfg } 209254260Spfg ehp = (struct ext4_extent_header *)path->ep_bp->b_data; 210254260Spfg path->ep_header = ehp; 211254260Spfg } 212254260Spfg 213254260Spfg path->ep_depth = i; 214254260Spfg path->ep_ext = NULL; 215254260Spfg path->ep_index = NULL; 216295523Spfg path->ep_is_sparse = false; 217254260Spfg 218295494Spfg ext4_ext_binsearch(ip, path, lbn, first_lbn, last_lbn); 219254260Spfg return (path); 220254260Spfg} 221