diff --git a/sys/fs/ext2fs/ext2_extents.c b/sys/fs/ext2fs/ext2_extents.c index cc77107785a5..2a3ffbd0e860 100644 --- a/sys/fs/ext2fs/ext2_extents.c +++ b/sys/fs/ext2fs/ext2_extents.c @@ -1,1627 +1,1628 @@ /*- * SPDX-License-Identifier: BSD-2-Clause-FreeBSD * * Copyright (c) 2010 Zheng Liu * 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$ */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include SDT_PROVIDER_DECLARE(ext2fs); /* * ext2fs trace probe: * arg0: verbosity. Higher numbers give more verbose messages * arg1: Textual message */ SDT_PROBE_DEFINE2(ext2fs, , trace, extents, "int", "char*"); static MALLOC_DEFINE(M_EXT2EXTENTS, "ext2_extents", "EXT2 extents"); #ifdef EXT2FS_PRINT_EXTENTS static const bool print_extents_walk = true; static int ext4_ext_check_header(struct inode *, struct ext4_extent_header *); static int ext4_ext_walk_header(struct inode *, struct ext4_extent_header *); static inline e4fs_daddr_t ext4_ext_index_pblock(struct ext4_extent_index *); static inline e4fs_daddr_t ext4_ext_extent_pblock(struct ext4_extent *); static int ext4_ext_blk_check(struct inode *ip, e4fs_daddr_t blk) { struct m_ext2fs *fs; fs = ip->i_e2fs; if (blk < fs->e2fs->e2fs_first_dblock || blk >= fs->e2fs_bcount) return (EIO); return (0); } static int ext4_ext_walk_index(struct inode *ip, struct ext4_extent_index *ex, bool do_walk) { struct m_ext2fs *fs; struct buf *bp; e4fs_daddr_t blk; int error; fs = ip->i_e2fs; if (print_extents_walk) printf(" index %p => (blk %u pblk %ju)\n", ex, le32toh(ex->ei_blk), (uint64_t)le16toh(ex->ei_leaf_hi) << 32 | le32toh(ex->ei_leaf_lo)); if(!do_walk) return (0); blk = ext4_ext_index_pblock(ex); error = ext4_ext_blk_check(ip, blk); if (error) return (error); if ((error = bread(ip->i_devvp, fsbtodb(fs, blk), (int)fs->e2fs_bsize, NOCRED, &bp)) != 0) { brelse(bp); return (error); } error = ext4_ext_walk_header(ip, (struct ext4_extent_header *)bp->b_data); brelse(bp); return (error); } static int ext4_ext_walk_extent(struct inode *ip, struct ext4_extent *ep) { e4fs_daddr_t blk; int error; blk = ext4_ext_extent_pblock(ep); error = ext4_ext_blk_check(ip, blk); if (error) return (error); if (print_extents_walk) printf(" ext %p => (blk %u len %u start %ju)\n", ep, le32toh(ep->e_blk), le16toh(ep->e_len), (uint64_t)blk); return (0); } static int ext4_ext_walk_header(struct inode *ip, struct ext4_extent_header *eh) { int i, error = 0; error = ext4_ext_check_header(ip, eh); if (error) return (error); if (print_extents_walk) printf("header %p => (entries %d max %d depth %d gen %d)\n", eh, le16toh(eh->eh_ecount), le16toh(eh->eh_max), le16toh(eh->eh_depth), le32toh(eh->eh_gen)); for (i = 0; i < le16toh(eh->eh_ecount) && error == 0; i++) if (eh->eh_depth != 0) error = ext4_ext_walk_index(ip, (struct ext4_extent_index *)(eh + 1 + i), true); else error = ext4_ext_walk_extent(ip, (struct ext4_extent *)(eh + 1 + i)); return (error); } static int ext4_ext_print_path(struct inode *ip, struct ext4_extent_path *path) { int k, l, error = 0; l = path->ep_depth; if (print_extents_walk) printf("ip=%ju, Path:\n", ip->i_number); for (k = 0; k <= l && error == 0; k++, path++) { if (path->ep_index) { error = ext4_ext_walk_index(ip, path->ep_index, false); } else if (path->ep_ext) { error = ext4_ext_walk_extent(ip, path->ep_ext); } } return (error); } int ext4_ext_walk(struct inode *ip) { struct ext4_extent_header *ehp; ehp = (struct ext4_extent_header *)ip->i_db; if (print_extents_walk) printf("Extent status:ip=%ju\n", ip->i_number); if (!(ip->i_flag & IN_E4EXTENTS)) return (0); return (ext4_ext_walk_header(ip, ehp)); } #endif static inline struct ext4_extent_header * ext4_ext_inode_header(struct inode *ip) { return ((struct ext4_extent_header *)ip->i_db); } static inline struct ext4_extent_header * ext4_ext_block_header(char *bdata) { return ((struct ext4_extent_header *)bdata); } static inline unsigned short ext4_ext_inode_depth(struct inode *ip) { struct ext4_extent_header *ehp; ehp = (struct ext4_extent_header *)ip->i_data; return (le16toh(ehp->eh_depth)); } static inline e4fs_daddr_t ext4_ext_index_pblock(struct ext4_extent_index *index) { e4fs_daddr_t blk; blk = le32toh(index->ei_leaf_lo); blk |= (e4fs_daddr_t)le16toh(index->ei_leaf_hi) << 32; return (blk); } static inline void ext4_index_store_pblock(struct ext4_extent_index *index, e4fs_daddr_t pb) { index->ei_leaf_lo = htole32(pb & 0xffffffff); index->ei_leaf_hi = htole16((pb >> 32) & 0xffff); } static inline e4fs_daddr_t ext4_ext_extent_pblock(struct ext4_extent *extent) { e4fs_daddr_t blk; blk = le32toh(extent->e_start_lo); blk |= (e4fs_daddr_t)le16toh(extent->e_start_hi) << 32; return (blk); } static inline void ext4_ext_store_pblock(struct ext4_extent *ex, e4fs_daddr_t pb) { ex->e_start_lo = htole32(pb & 0xffffffff); ex->e_start_hi = htole16((pb >> 32) & 0xffff); } 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->i_ext_cache; 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 = htole32(ecp->ec_blk); ep->e_start_lo = htole32(ecp->ec_start & 0xffffffff); ep->e_start_hi = htole16(ecp->ec_start >> 32 & 0xffff); ep->e_len = htole16(ecp->ec_len); ret = ecp->ec_type; } return (ret); } static int ext4_ext_check_header(struct inode *ip, struct ext4_extent_header *eh) { struct m_ext2fs *fs; char *error_msg; fs = ip->i_e2fs; if (le16toh(eh->eh_magic) != EXT4_EXT_MAGIC) { error_msg = "header: invalid magic"; goto corrupted; } if (eh->eh_max == 0) { error_msg = "header: invalid eh_max"; goto corrupted; } if (le16toh(eh->eh_ecount) > le16toh(eh->eh_max)) { error_msg = "header: invalid eh_entries"; goto corrupted; } return (0); corrupted: SDT_PROBE2(ext2fs, , trace, extents, 1, error_msg); return (EIO); } static void ext4_ext_binsearch_index(struct ext4_extent_path *path, int blk) { struct ext4_extent_header *eh; struct ext4_extent_index *r, *l, *m; eh = path->ep_header; KASSERT(le16toh(eh->eh_ecount) <= le16toh(eh->eh_max) && le16toh(eh->eh_ecount) > 0, ("ext4_ext_binsearch_index: bad args")); l = EXT_FIRST_INDEX(eh) + 1; r = EXT_FIRST_INDEX(eh) + le16toh(eh->eh_ecount) - 1; while (l <= r) { m = l + (r - l) / 2; if (blk < le32toh(m->ei_blk)) r = m - 1; else l = m + 1; } path->ep_index = l - 1; } static void ext4_ext_binsearch_ext(struct ext4_extent_path *path, int blk) { struct ext4_extent_header *eh; struct ext4_extent *r, *l, *m; eh = path->ep_header; KASSERT(le16toh(eh->eh_ecount) <= le16toh(eh->eh_max), ("ext4_ext_binsearch_ext: bad args")); if (eh->eh_ecount == 0) return; l = EXT_FIRST_EXTENT(eh) + 1; r = EXT_FIRST_EXTENT(eh) + le16toh(eh->eh_ecount) - 1; while (l <= r) { m = l + (r - l) / 2; if (blk < le32toh(m->e_blk)) r = m - 1; else l = m + 1; } path->ep_ext = l - 1; } static int ext4_ext_fill_path_bdata(struct ext4_extent_path *path, struct buf *bp, uint64_t blk) { KASSERT(path->ep_data == NULL, ("ext4_ext_fill_path_bdata: bad ep_data")); path->ep_data = malloc(bp->b_bufsize, M_EXT2EXTENTS, M_WAITOK); memcpy(path->ep_data, bp->b_data, bp->b_bufsize); path->ep_blk = blk; return (0); } static void ext4_ext_fill_path_buf(struct ext4_extent_path *path, struct buf *bp) { KASSERT(path->ep_data != NULL, ("ext4_ext_fill_path_buf: bad ep_data")); memcpy(bp->b_data, path->ep_data, bp->b_bufsize); } static void ext4_ext_drop_refs(struct ext4_extent_path *path) { int depth, i; if (!path) return; depth = path->ep_depth; for (i = 0; i <= depth; i++, path++) if (path->ep_data) { free(path->ep_data, M_EXT2EXTENTS); path->ep_data = NULL; } } void ext4_ext_path_free(struct ext4_extent_path *path) { if (!path) return; ext4_ext_drop_refs(path); free(path, M_EXT2EXTENTS); } int ext4_ext_find_extent(struct inode *ip, daddr_t block, struct ext4_extent_path **ppath) { struct m_ext2fs *fs; struct ext4_extent_header *eh; struct ext4_extent_path *path; struct buf *bp; uint64_t blk; int error, depth, i, ppos, alloc; fs = ip->i_e2fs; eh = ext4_ext_inode_header(ip); depth = ext4_ext_inode_depth(ip); ppos = 0; alloc = 0; error = ext4_ext_check_header(ip, eh); if (error) return (error); if (ppath == NULL) return (EINVAL); path = *ppath; if (path == NULL) { path = malloc(EXT4_EXT_DEPTH_MAX * sizeof(struct ext4_extent_path), M_EXT2EXTENTS, M_WAITOK | M_ZERO); *ppath = path; alloc = 1; } path[0].ep_header = eh; path[0].ep_data = NULL; /* Walk through the tree. */ i = depth; while (i) { ext4_ext_binsearch_index(&path[ppos], block); blk = ext4_ext_index_pblock(path[ppos].ep_index); path[ppos].ep_depth = i; path[ppos].ep_ext = NULL; error = bread(ip->i_devvp, fsbtodb(ip->i_e2fs, blk), ip->i_e2fs->e2fs_bsize, NOCRED, &bp); if (error) { goto error; } ppos++; if (ppos > depth) { SDT_PROBE2(ext2fs, , trace, extents, 1, "ppos > depth => extent corrupted"); error = EIO; brelse(bp); goto error; } ext4_ext_fill_path_bdata(&path[ppos], bp, blk); bqrelse(bp); eh = ext4_ext_block_header(path[ppos].ep_data); if (ext4_ext_check_header(ip, eh) || ext2_extent_blk_csum_verify(ip, path[ppos].ep_data)) { error = EIO; goto error; } path[ppos].ep_header = eh; i--; } error = ext4_ext_check_header(ip, eh); if (error) goto error; /* Find extent. */ path[ppos].ep_depth = i; path[ppos].ep_header = eh; path[ppos].ep_ext = NULL; path[ppos].ep_index = NULL; ext4_ext_binsearch_ext(&path[ppos], block); return (0); error: ext4_ext_drop_refs(path); if (alloc) free(path, M_EXT2EXTENTS); *ppath = NULL; return (error); } static inline int ext4_ext_space_root(struct inode *ip) { int size; size = sizeof(ip->i_data); size -= sizeof(struct ext4_extent_header); size /= sizeof(struct ext4_extent); return (size); } static inline int ext4_ext_space_block(struct inode *ip) { struct m_ext2fs *fs; int size; fs = ip->i_e2fs; size = (fs->e2fs_bsize - sizeof(struct ext4_extent_header)) / sizeof(struct ext4_extent); return (size); } static inline int ext4_ext_space_block_index(struct inode *ip) { struct m_ext2fs *fs; int size; fs = ip->i_e2fs; size = (fs->e2fs_bsize - sizeof(struct ext4_extent_header)) / sizeof(struct ext4_extent_index); return (size); } void ext4_ext_tree_init(struct inode *ip) { struct ext4_extent_header *ehp; ip->i_flag |= IN_E4EXTENTS; memset(ip->i_data, 0, EXT2_NDADDR + EXT2_NIADDR); ehp = (struct ext4_extent_header *)ip->i_data; ehp->eh_magic = htole16(EXT4_EXT_MAGIC); ehp->eh_max = htole16(ext4_ext_space_root(ip)); ip->i_ext_cache.ec_type = EXT4_EXT_CACHE_NO; ip->i_flag |= IN_CHANGE | IN_UPDATE; ext2_update(ip->i_vnode, 1); } static inline void ext4_ext_put_in_cache(struct inode *ip, uint32_t blk, uint32_t len, uint32_t start, int type) { KASSERT(len != 0, ("ext4_ext_put_in_cache: bad input")); ip->i_ext_cache.ec_type = type; ip->i_ext_cache.ec_blk = blk; ip->i_ext_cache.ec_len = len; ip->i_ext_cache.ec_start = start; } static e4fs_daddr_t ext4_ext_blkpref(struct inode *ip, struct ext4_extent_path *path, e4fs_daddr_t block) { struct m_ext2fs *fs; struct ext4_extent *ex; e4fs_daddr_t bg_start; int depth; fs = ip->i_e2fs; if (path) { depth = path->ep_depth; ex = path[depth].ep_ext; if (ex) { e4fs_daddr_t pblk = ext4_ext_extent_pblock(ex); e2fs_daddr_t blk = le32toh(ex->e_blk); if (block > blk) return (pblk + (block - blk)); else return (pblk - (blk - block)); } /* Try to get block from index itself. */ if (path[depth].ep_data) return (path[depth].ep_blk); } /* Use inode's group. */ bg_start = (ip->i_block_group * EXT2_BLOCKS_PER_GROUP(ip->i_e2fs)) + le32toh(fs->e2fs->e2fs_first_dblock); return (bg_start + block); } static int inline ext4_can_extents_be_merged(struct ext4_extent *ex1, struct ext4_extent *ex2) { if (le32toh(ex1->e_blk) + le16toh(ex1->e_len) != le32toh(ex2->e_blk)) return (0); if (le16toh(ex1->e_len) + le16toh(ex2->e_len) > EXT4_MAX_LEN) return (0); if (ext4_ext_extent_pblock(ex1) + le16toh(ex1->e_len) == ext4_ext_extent_pblock(ex2)) return (1); return (0); } static unsigned ext4_ext_next_leaf_block(struct inode *ip, struct ext4_extent_path *path) { int depth = path->ep_depth; /* Empty tree */ if (depth == 0) return (EXT4_MAX_BLOCKS); /* Go to indexes. */ depth--; while (depth >= 0) { if (path[depth].ep_index != EXT_LAST_INDEX(path[depth].ep_header)) return (le32toh(path[depth].ep_index[1].ei_blk)); depth--; } return (EXT4_MAX_BLOCKS); } static int ext4_ext_dirty(struct inode *ip, struct ext4_extent_path *path) { struct m_ext2fs *fs; struct buf *bp; uint64_t blk; int error; fs = ip->i_e2fs; if (!path) return (EINVAL); if (path->ep_data) { blk = path->ep_blk; bp = getblk(ip->i_devvp, fsbtodb(fs, blk), fs->e2fs_bsize, 0, 0, 0); if (!bp) return (EIO); ext4_ext_fill_path_buf(path, bp); ext2_extent_blk_csum_set(ip, bp->b_data); error = bwrite(bp); } else { ip->i_flag |= IN_CHANGE | IN_UPDATE; error = ext2_update(ip->i_vnode, 1); } return (error); } static int ext4_ext_insert_index(struct inode *ip, struct ext4_extent_path *path, uint32_t lblk, e4fs_daddr_t blk) { struct m_ext2fs *fs; struct ext4_extent_index *idx; int len; fs = ip->i_e2fs; if (lblk == le32toh(path->ep_index->ei_blk)) { SDT_PROBE2(ext2fs, , trace, extents, 1, "lblk == index blk => extent corrupted"); return (EIO); } if (le16toh(path->ep_header->eh_ecount) >= le16toh(path->ep_header->eh_max)) { SDT_PROBE2(ext2fs, , trace, extents, 1, "ecout > maxcount => extent corrupted"); return (EIO); } if (lblk > le32toh(path->ep_index->ei_blk)) { /* Insert after. */ idx = path->ep_index + 1; } else { /* Insert before. */ idx = path->ep_index; } len = EXT_LAST_INDEX(path->ep_header) - idx + 1; if (len > 0) memmove(idx + 1, idx, len * sizeof(struct ext4_extent_index)); if (idx > EXT_MAX_INDEX(path->ep_header)) { SDT_PROBE2(ext2fs, , trace, extents, 1, "index is out of range => extent corrupted"); return (EIO); } idx->ei_blk = htole32(lblk); ext4_index_store_pblock(idx, blk); path->ep_header->eh_ecount = htole16(le16toh(path->ep_header->eh_ecount) + 1); return (ext4_ext_dirty(ip, path)); } static e4fs_daddr_t ext4_ext_alloc_meta(struct inode *ip) { e4fs_daddr_t blk = ext2_alloc_meta(ip); if (blk) { ip->i_blocks += btodb(ip->i_e2fs->e2fs_bsize); ip->i_flag |= IN_CHANGE | IN_UPDATE; ext2_update(ip->i_vnode, 1); } return (blk); } static void ext4_ext_blkfree(struct inode *ip, uint64_t blk, int count, int flags) { struct m_ext2fs *fs; int i, blocksreleased; fs = ip->i_e2fs; blocksreleased = count; for(i = 0; i < count; i++) ext2_blkfree(ip, blk + i, fs->e2fs_bsize); if (ip->i_blocks >= blocksreleased) ip->i_blocks -= (btodb(fs->e2fs_bsize)*blocksreleased); else ip->i_blocks = 0; ip->i_flag |= IN_CHANGE | IN_UPDATE; ext2_update(ip->i_vnode, 1); } static int ext4_ext_split(struct inode *ip, struct ext4_extent_path *path, struct ext4_extent *newext, int at) { struct m_ext2fs *fs; struct buf *bp; int depth = ext4_ext_inode_depth(ip); struct ext4_extent_header *neh; struct ext4_extent_index *fidx; struct ext4_extent *ex; int i = at, k, m, a; e4fs_daddr_t newblk, oldblk; uint32_t border; e4fs_daddr_t *ablks = NULL; int error = 0; fs = ip->i_e2fs; bp = NULL; /* * We will split at current extent for now. */ if (path[depth].ep_ext > EXT_MAX_EXTENT(path[depth].ep_header)) { SDT_PROBE2(ext2fs, , trace, extents, 1, "extent is out of range => extent corrupted"); return (EIO); } if (path[depth].ep_ext != EXT_MAX_EXTENT(path[depth].ep_header)) border = le32toh(path[depth].ep_ext[1].e_blk); else border = le32toh(newext->e_blk); /* Allocate new blocks. */ ablks = malloc(sizeof(e4fs_daddr_t) * depth, M_EXT2EXTENTS, M_WAITOK | M_ZERO); for (a = 0; a < depth - at; a++) { newblk = ext4_ext_alloc_meta(ip); if (newblk == 0) goto cleanup; ablks[a] = newblk; } newblk = ablks[--a]; bp = getblk(ip->i_devvp, fsbtodb(fs, newblk), fs->e2fs_bsize, 0, 0, 0); if (!bp) { error = EIO; goto cleanup; } neh = ext4_ext_block_header(bp->b_data); neh->eh_ecount = 0; neh->eh_max = le16toh(ext4_ext_space_block(ip)); neh->eh_magic = le16toh(EXT4_EXT_MAGIC); neh->eh_depth = 0; ex = EXT_FIRST_EXTENT(neh); if (le16toh(path[depth].ep_header->eh_ecount) != le16toh(path[depth].ep_header->eh_max)) { SDT_PROBE2(ext2fs, , trace, extents, 1, "extents count out of range => extent corrupted"); error = EIO; goto cleanup; } /* Start copy from next extent. */ m = 0; path[depth].ep_ext++; while (path[depth].ep_ext <= EXT_MAX_EXTENT(path[depth].ep_header)) { path[depth].ep_ext++; m++; } if (m) { memmove(ex, path[depth].ep_ext - m, sizeof(struct ext4_extent) * m); neh->eh_ecount = htole16(le16toh(neh->eh_ecount) + m); } ext2_extent_blk_csum_set(ip, bp->b_data); bwrite(bp); bp = NULL; /* Fix old leaf. */ if (m) { path[depth].ep_header->eh_ecount = htole16(le16toh(path[depth].ep_header->eh_ecount) - m); ext4_ext_dirty(ip, path + depth); } /* Create intermediate indexes. */ k = depth - at - 1; KASSERT(k >= 0, ("ext4_ext_split: negative k")); /* Insert new index into current index block. */ i = depth - 1; while (k--) { oldblk = newblk; newblk = ablks[--a]; error = bread(ip->i_devvp, fsbtodb(fs, newblk), (int)fs->e2fs_bsize, NOCRED, &bp); if (error) { goto cleanup; } neh = (struct ext4_extent_header *)bp->b_data; neh->eh_ecount = htole16(1); neh->eh_magic = htole16(EXT4_EXT_MAGIC); neh->eh_max = htole16(ext4_ext_space_block_index(ip)); neh->eh_depth = htole16(depth - i); fidx = EXT_FIRST_INDEX(neh); fidx->ei_blk = htole32(border); ext4_index_store_pblock(fidx, oldblk); m = 0; path[i].ep_index++; while (path[i].ep_index <= EXT_MAX_INDEX(path[i].ep_header)) { path[i].ep_index++; m++; } if (m) { memmove(++fidx, path[i].ep_index - m, sizeof(struct ext4_extent_index) * m); neh->eh_ecount = htole16(le16toh(neh->eh_ecount) + m); } ext2_extent_blk_csum_set(ip, bp->b_data); bwrite(bp); bp = NULL; /* Fix old index. */ if (m) { path[i].ep_header->eh_ecount = htole16(le16toh(path[i].ep_header->eh_ecount) - m); ext4_ext_dirty(ip, path + i); } i--; } error = ext4_ext_insert_index(ip, path + at, border, newblk); cleanup: if (bp) brelse(bp); if (error) { for (i = 0; i < depth; i++) { if (!ablks[i]) continue; ext4_ext_blkfree(ip, ablks[i], 1, 0); } } free(ablks, M_EXT2EXTENTS); return (error); } static int ext4_ext_grow_indepth(struct inode *ip, struct ext4_extent_path *path, struct ext4_extent *newext) { struct m_ext2fs *fs; struct ext4_extent_path *curpath; struct ext4_extent_header *neh; struct buf *bp; e4fs_daddr_t newblk; int error = 0; fs = ip->i_e2fs; curpath = path; newblk = ext4_ext_alloc_meta(ip); if (newblk == 0) return (error); bp = getblk(ip->i_devvp, fsbtodb(fs, newblk), fs->e2fs_bsize, 0, 0, 0); if (!bp) return (EIO); /* Move top-level index/leaf into new block. */ memmove(bp->b_data, curpath->ep_header, sizeof(ip->i_data)); /* Set size of new block */ neh = ext4_ext_block_header(bp->b_data); neh->eh_magic = htole16(EXT4_EXT_MAGIC); if (ext4_ext_inode_depth(ip)) neh->eh_max = htole16(ext4_ext_space_block_index(ip)); else neh->eh_max = htole16(ext4_ext_space_block(ip)); ext2_extent_blk_csum_set(ip, bp->b_data); error = bwrite(bp); if (error) goto out; bp = NULL; curpath->ep_header->eh_magic = htole16(EXT4_EXT_MAGIC); curpath->ep_header->eh_max = htole16(ext4_ext_space_root(ip)); curpath->ep_header->eh_ecount = htole16(1); curpath->ep_index = EXT_FIRST_INDEX(curpath->ep_header); curpath->ep_index->ei_blk = EXT_FIRST_EXTENT(path[0].ep_header)->e_blk; ext4_index_store_pblock(curpath->ep_index, newblk); neh = ext4_ext_inode_header(ip); neh->eh_depth = htole16(path->ep_depth + 1); ext4_ext_dirty(ip, curpath); out: brelse(bp); return (error); } static int ext4_ext_create_new_leaf(struct inode *ip, struct ext4_extent_path *path, struct ext4_extent *newext) { struct ext4_extent_path *curpath; int depth, i, error; repeat: i = depth = ext4_ext_inode_depth(ip); /* Look for free index entry int the tree */ curpath = path + depth; while (i > 0 && !EXT_HAS_FREE_INDEX(curpath)) { i--; curpath--; } /* * We use already allocated block for index block, * so subsequent data blocks should be contiguous. */ if (EXT_HAS_FREE_INDEX(curpath)) { error = ext4_ext_split(ip, path, newext, i); if (error) goto out; /* Refill path. */ ext4_ext_drop_refs(path); error = ext4_ext_find_extent(ip, le32toh(newext->e_blk), &path); if (error) goto out; } else { /* Tree is full, do grow in depth. */ error = ext4_ext_grow_indepth(ip, path, newext); if (error) goto out; /* Refill path. */ ext4_ext_drop_refs(path); error = ext4_ext_find_extent(ip, le32toh(newext->e_blk), &path); if (error) goto out; /* Check and split tree if required. */ depth = ext4_ext_inode_depth(ip); if (le16toh(path[depth].ep_header->eh_ecount) == le16toh(path[depth].ep_header->eh_max)) goto repeat; } out: return (error); } static int ext4_ext_correct_indexes(struct inode *ip, struct ext4_extent_path *path) { struct ext4_extent_header *eh; struct ext4_extent *ex; int32_t border; int depth, k; depth = ext4_ext_inode_depth(ip); eh = path[depth].ep_header; ex = path[depth].ep_ext; if (ex == NULL || eh == NULL) return (EIO); if (!depth) return (0); /* We will correct tree if first leaf got modified only. */ if (ex != EXT_FIRST_EXTENT(eh)) return (0); k = depth - 1; border = le32toh(path[depth].ep_ext->e_blk); path[k].ep_index->ei_blk = htole32(border); ext4_ext_dirty(ip, path + k); while (k--) { /* Change all left-side indexes. */ if (path[k+1].ep_index != EXT_FIRST_INDEX(path[k+1].ep_header)) break; path[k].ep_index->ei_blk = htole32(border); ext4_ext_dirty(ip, path + k); } return (0); } static int ext4_ext_insert_extent(struct inode *ip, struct ext4_extent_path *path, struct ext4_extent *newext) { struct ext4_extent_header * eh; struct ext4_extent *ex, *nex, *nearex; struct ext4_extent_path *npath; int depth, len, error, next; depth = ext4_ext_inode_depth(ip); ex = path[depth].ep_ext; npath = NULL; if (htole16(newext->e_len) == 0 || path[depth].ep_header == NULL) return (EINVAL); /* Insert block into found extent. */ if (ex && ext4_can_extents_be_merged(ex, newext)) { ex->e_len = htole16(le16toh(ex->e_len) + le16toh(newext->e_len)); eh = path[depth].ep_header; nearex = ex; goto merge; } repeat: depth = ext4_ext_inode_depth(ip); eh = path[depth].ep_header; if (le16toh(eh->eh_ecount) < le16toh(eh->eh_max)) goto has_space; /* Try next leaf */ nex = EXT_LAST_EXTENT(eh); next = ext4_ext_next_leaf_block(ip, path); if (le32toh(newext->e_blk) > le32toh(nex->e_blk) && next != EXT4_MAX_BLOCKS) { KASSERT(npath == NULL, ("ext4_ext_insert_extent: bad path")); error = ext4_ext_find_extent(ip, next, &npath); if (error) goto cleanup; if (npath->ep_depth != path->ep_depth) { error = EIO; goto cleanup; } eh = npath[depth].ep_header; if (le16toh(eh->eh_ecount) < le16toh(eh->eh_max)) { path = npath; goto repeat; } } /* * There is no free space in the found leaf, * try to add a new leaf to the tree. */ error = ext4_ext_create_new_leaf(ip, path, newext); if (error) goto cleanup; depth = ext4_ext_inode_depth(ip); eh = path[depth].ep_header; has_space: nearex = path[depth].ep_ext; if (!nearex) { /* Create new extent in the leaf. */ path[depth].ep_ext = EXT_FIRST_EXTENT(eh); } else if (le32toh(newext->e_blk) > le32toh(nearex->e_blk)) { if (nearex != EXT_LAST_EXTENT(eh)) { len = EXT_MAX_EXTENT(eh) - nearex; len = (len - 1) * sizeof(struct ext4_extent); len = len < 0 ? 0 : len; memmove(nearex + 2, nearex + 1, len); } path[depth].ep_ext = nearex + 1; } else { len = (EXT_MAX_EXTENT(eh) - nearex) * sizeof(struct ext4_extent); len = len < 0 ? 0 : len; memmove(nearex + 1, nearex, len); path[depth].ep_ext = nearex; } eh->eh_ecount = htole16(le16toh(eh->eh_ecount) + 1); nearex = path[depth].ep_ext; nearex->e_blk = newext->e_blk; nearex->e_start_lo = newext->e_start_lo; nearex->e_start_hi = newext->e_start_hi; nearex->e_len = newext->e_len; merge: /* Try to merge extents to the right. */ while (nearex < EXT_LAST_EXTENT(eh)) { if (!ext4_can_extents_be_merged(nearex, nearex + 1)) break; /* Merge with next extent. */ nearex->e_len = htole16(le16toh(nearex->e_len) + le16toh(nearex[1].e_len)); if (nearex + 1 < EXT_LAST_EXTENT(eh)) { len = (EXT_LAST_EXTENT(eh) - nearex - 1) * sizeof(struct ext4_extent); memmove(nearex + 1, nearex + 2, len); } eh->eh_ecount = htole16(le16toh(eh->eh_ecount) - 1); KASSERT(le16toh(eh->eh_ecount) != 0, ("ext4_ext_insert_extent: bad ecount")); } /* * Try to merge extents to the left, * start from inexes correction. */ error = ext4_ext_correct_indexes(ip, path); if (error) goto cleanup; ext4_ext_dirty(ip, path + depth); cleanup: if (npath) { ext4_ext_drop_refs(npath); free(npath, M_EXT2EXTENTS); } ip->i_ext_cache.ec_type = EXT4_EXT_CACHE_NO; return (error); } static e4fs_daddr_t ext4_new_blocks(struct inode *ip, daddr_t lbn, e4fs_daddr_t pref, struct ucred *cred, unsigned long *count, int *perror) { struct m_ext2fs *fs; e4fs_daddr_t newblk; /* * We will allocate only single block for now. */ if (*count > 1) return (0); fs = ip->i_e2fs; EXT2_LOCK(ip->i_ump); *perror = ext2_alloc(ip, lbn, pref, (int)fs->e2fs_bsize, cred, &newblk); if (*perror) return (0); if (newblk) { ip->i_flag |= IN_CHANGE | IN_UPDATE; ext2_update(ip->i_vnode, 1); } return (newblk); } int ext4_ext_get_blocks(struct inode *ip, e4fs_daddr_t iblk, unsigned long max_blocks, struct ucred *cred, struct buf **bpp, int *pallocated, daddr_t *nb) { struct m_ext2fs *fs; struct buf *bp = NULL; struct ext4_extent_path *path; struct ext4_extent newex, *ex; e4fs_daddr_t bpref, newblk = 0; unsigned long allocated = 0; int error = 0, depth; if(bpp) *bpp = NULL; *pallocated = 0; /* Check cache. */ path = NULL; if ((bpref = ext4_ext_in_cache(ip, iblk, &newex))) { if (bpref == EXT4_EXT_CACHE_IN) { /* Block is already allocated. */ newblk = iblk - le32toh(newex.e_blk) + ext4_ext_extent_pblock(&newex); allocated = le16toh(newex.e_len) - (iblk - le32toh(newex.e_blk)); goto out; } else { error = EIO; goto out2; } } error = ext4_ext_find_extent(ip, iblk, &path); if (error) { goto out2; } depth = ext4_ext_inode_depth(ip); if (path[depth].ep_ext == NULL && depth != 0) { error = EIO; goto out2; } if ((ex = path[depth].ep_ext)) { uint64_t lblk = le32toh(ex->e_blk); uint16_t e_len = le16toh(ex->e_len); e4fs_daddr_t e_start = ext4_ext_extent_pblock(ex); if (e_len > EXT4_MAX_LEN) goto out2; /* If we found extent covers block, simply return it. */ if (iblk >= lblk && iblk < lblk + e_len) { newblk = iblk - lblk + e_start; allocated = e_len - (iblk - lblk); ext4_ext_put_in_cache(ip, lblk, e_len, e_start, EXT4_EXT_CACHE_IN); goto out; } } /* Allocate the new block. */ if (S_ISREG(ip->i_mode) && (!ip->i_next_alloc_block)) { ip->i_next_alloc_goal = 0; } bpref = ext4_ext_blkpref(ip, path, iblk); allocated = max_blocks; newblk = ext4_new_blocks(ip, iblk, bpref, cred, &allocated, &error); if (!newblk) goto out2; /* Try to insert new extent into found leaf and return. */ newex.e_blk = htole32(iblk); ext4_ext_store_pblock(&newex, newblk); newex.e_len = htole16(allocated); error = ext4_ext_insert_extent(ip, path, &newex); if (error) goto out2; newblk = ext4_ext_extent_pblock(&newex); ext4_ext_put_in_cache(ip, iblk, allocated, newblk, EXT4_EXT_CACHE_IN); *pallocated = 1; out: if (allocated > max_blocks) allocated = max_blocks; if (bpp) { fs = ip->i_e2fs; error = bread(ip->i_devvp, fsbtodb(fs, newblk), fs->e2fs_bsize, cred, &bp); if (error) { brelse(bp); } else { *bpp = bp; } } out2: if (path) { ext4_ext_drop_refs(path); free(path, M_EXT2EXTENTS); } if (nb) *nb = newblk; return (error); } static inline uint16_t ext4_ext_get_actual_len(struct ext4_extent *ext) { return (le16toh(ext->e_len) <= EXT_INIT_MAX_LEN ? le16toh(ext->e_len) : (le16toh(ext->e_len) - EXT_INIT_MAX_LEN)); } static inline struct ext4_extent_header * ext4_ext_header(struct inode *ip) { return ((struct ext4_extent_header *)ip->i_db); } static int ext4_remove_blocks(struct inode *ip, struct ext4_extent *ex, unsigned long from, unsigned long to) { unsigned long num, start; if (from >= le32toh(ex->e_blk) && to == le32toh(ex->e_blk) + ext4_ext_get_actual_len(ex) - 1) { /* Tail cleanup. */ num = le32toh(ex->e_blk) + ext4_ext_get_actual_len(ex) - from; start = ext4_ext_extent_pblock(ex) + ext4_ext_get_actual_len(ex) - num; ext4_ext_blkfree(ip, start, num, 0); } return (0); } static int ext4_ext_rm_index(struct inode *ip, struct ext4_extent_path *path) { e4fs_daddr_t leaf; /* Free index block. */ path--; leaf = ext4_ext_index_pblock(path->ep_index); KASSERT(path->ep_header->eh_ecount != 0, ("ext4_ext_rm_index: bad ecount")); path->ep_header->eh_ecount = htole16(le16toh(path->ep_header->eh_ecount) - 1); ext4_ext_dirty(ip, path); ext4_ext_blkfree(ip, leaf, 1, 0); return (0); } static int ext4_ext_rm_leaf(struct inode *ip, struct ext4_extent_path *path, uint64_t start) { struct ext4_extent_header *eh; struct ext4_extent *ex; unsigned int a, b, block, num; unsigned long ex_blk; unsigned short ex_len; int depth; int error, correct_index; depth = ext4_ext_inode_depth(ip); if (!path[depth].ep_header) { if (path[depth].ep_data == NULL) return (EINVAL); path[depth].ep_header = (struct ext4_extent_header* )path[depth].ep_data; } eh = path[depth].ep_header; if (!eh) { SDT_PROBE2(ext2fs, , trace, extents, 1, "bad header => extent corrupted"); return (EIO); } ex = EXT_LAST_EXTENT(eh); ex_blk = le32toh(ex->e_blk); ex_len = ext4_ext_get_actual_len(ex); error = 0; correct_index = 0; while (ex >= EXT_FIRST_EXTENT(eh) && ex_blk + ex_len > start) { path[depth].ep_ext = ex; a = ex_blk > start ? ex_blk : start; b = (uint64_t)ex_blk + ex_len - 1 < EXT4_MAX_BLOCKS ? ex_blk + ex_len - 1 : EXT4_MAX_BLOCKS; if (a != ex_blk && b != ex_blk + ex_len - 1) return (EINVAL); else if (a != ex_blk) { /* Remove tail of the extent. */ block = ex_blk; num = a - block; } else if (b != ex_blk + ex_len - 1) { /* Remove head of the extent, not implemented. */ return (EINVAL); } else { /* Remove whole extent. */ block = ex_blk; num = 0; } if (ex == EXT_FIRST_EXTENT(eh)) correct_index = 1; error = ext4_remove_blocks(ip, ex, a, b); if (error) goto out; if (num == 0) { ext4_ext_store_pblock(ex, 0); eh->eh_ecount = htole16(le16toh(eh->eh_ecount) - 1); } ex->e_blk = htole32(block); ex->e_len = htole16(num); ext4_ext_dirty(ip, path + depth); ex--; ex_blk = htole32(ex->e_blk); ex_len = ext4_ext_get_actual_len(ex); }; if (correct_index && le16toh(eh->eh_ecount)) error = ext4_ext_correct_indexes(ip, path); /* * If this leaf is free, we should * remove it from index block above. */ if (error == 0 && eh->eh_ecount == 0 && path[depth].ep_data != NULL) error = ext4_ext_rm_index(ip, path + depth); out: return (error); } static struct buf * ext4_read_extent_tree_block(struct inode *ip, e4fs_daddr_t pblk, int depth, int flags) { struct m_ext2fs *fs; struct ext4_extent_header *eh; struct buf *bp; int error; fs = ip->i_e2fs; error = bread(ip->i_devvp, fsbtodb(fs, pblk), fs->e2fs_bsize, NOCRED, &bp); if (error) { return (NULL); } eh = ext4_ext_block_header(bp->b_data); if (le16toh(eh->eh_depth) != depth) { SDT_PROBE2(ext2fs, , trace, extents, 1, "unexpected eh_depth"); goto err; } error = ext4_ext_check_header(ip, eh); if (error) goto err; return (bp); err: brelse(bp); return (NULL); } static int inline ext4_ext_more_to_rm(struct ext4_extent_path *path) { KASSERT(path->ep_index != NULL, ("ext4_ext_more_to_rm: bad index from path")); if (path->ep_index < EXT_FIRST_INDEX(path->ep_header)) return (0); if (le16toh(path->ep_header->eh_ecount) == path->index_count) return (0); return (1); } int ext4_ext_remove_space(struct inode *ip, off_t length, int flags, struct ucred *cred, struct thread *td) { struct buf *bp; struct ext4_extent_header *ehp; struct ext4_extent_path *path; int depth; int i, error; ehp = (struct ext4_extent_header *)ip->i_db; depth = ext4_ext_inode_depth(ip); error = ext4_ext_check_header(ip, ehp); if(error) return (error); path = malloc(sizeof(struct ext4_extent_path) * (depth + 1), M_EXT2EXTENTS, M_WAITOK | M_ZERO); path[0].ep_header = ehp; path[0].ep_depth = depth; i = 0; while (error == 0 && i >= 0) { if (i == depth) { /* This is leaf. */ error = ext4_ext_rm_leaf(ip, path, length); if (error) break; free(path[i].ep_data, M_EXT2EXTENTS); path[i].ep_data = NULL; i--; continue; } /* This is index. */ if (!path[i].ep_header) path[i].ep_header = (struct ext4_extent_header *)path[i].ep_data; if (!path[i].ep_index) { /* This level hasn't touched yet. */ path[i].ep_index = EXT_LAST_INDEX(path[i].ep_header); path[i].index_count = le16toh(path[i].ep_header->eh_ecount) + 1; } else { /* We've already was here, see at next index. */ path[i].ep_index--; } if (ext4_ext_more_to_rm(path + i)) { memset(path + i + 1, 0, sizeof(*path)); bp = ext4_read_extent_tree_block(ip, ext4_ext_index_pblock(path[i].ep_index), path[0].ep_depth - (i + 1), 0); if (!bp) { error = EIO; break; } ext4_ext_fill_path_bdata(&path[i+1], bp, ext4_ext_index_pblock(path[i].ep_index)); brelse(bp); path[i].index_count = le16toh(path[i].ep_header->eh_ecount); i++; } else { if (path[i].ep_header->eh_ecount == 0 && i > 0) { /* Index is empty, remove it. */ error = ext4_ext_rm_index(ip, path + i); } free(path[i].ep_data, M_EXT2EXTENTS); path[i].ep_data = NULL; i--; } } if (path->ep_header->eh_ecount == 0) { /* * Truncate the tree to zero. */ ext4_ext_header(ip)->eh_depth = 0; ext4_ext_header(ip)->eh_max = htole16(ext4_ext_space_root(ip)); ext4_ext_dirty(ip, path); } ext4_ext_drop_refs(path); free(path, M_EXT2EXTENTS); + ip->i_ext_cache.ec_type = EXT4_EXT_CACHE_NO; return (error); }