1a86c6181SAlex Tomas /* 2a86c6181SAlex Tomas * Copyright (c) 2003-2006, Cluster File Systems, Inc, info@clusterfs.com 3a86c6181SAlex Tomas * Written by Alex Tomas <alex@clusterfs.com> 4a86c6181SAlex Tomas * 5a86c6181SAlex Tomas * Architecture independence: 6a86c6181SAlex Tomas * Copyright (c) 2005, Bull S.A. 7a86c6181SAlex Tomas * Written by Pierre Peiffer <pierre.peiffer@bull.net> 8a86c6181SAlex Tomas * 9a86c6181SAlex Tomas * This program is free software; you can redistribute it and/or modify 10a86c6181SAlex Tomas * it under the terms of the GNU General Public License version 2 as 11a86c6181SAlex Tomas * published by the Free Software Foundation. 12a86c6181SAlex Tomas * 13a86c6181SAlex Tomas * This program is distributed in the hope that it will be useful, 14a86c6181SAlex Tomas * but WITHOUT ANY WARRANTY; without even the implied warranty of 15a86c6181SAlex Tomas * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16a86c6181SAlex Tomas * GNU General Public License for more details. 17a86c6181SAlex Tomas * 18a86c6181SAlex Tomas * You should have received a copy of the GNU General Public Licens 19a86c6181SAlex Tomas * along with this program; if not, write to the Free Software 20a86c6181SAlex Tomas * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111- 21a86c6181SAlex Tomas */ 22a86c6181SAlex Tomas 23a86c6181SAlex Tomas /* 24a86c6181SAlex Tomas * Extents support for EXT4 25a86c6181SAlex Tomas * 26a86c6181SAlex Tomas * TODO: 27a86c6181SAlex Tomas * - ext4*_error() should be used in some situations 28a86c6181SAlex Tomas * - analyze all BUG()/BUG_ON(), use -EIO where appropriate 29a86c6181SAlex Tomas * - smart tree reduction 30a86c6181SAlex Tomas */ 31a86c6181SAlex Tomas 32a86c6181SAlex Tomas #include <linux/module.h> 33a86c6181SAlex Tomas #include <linux/fs.h> 34a86c6181SAlex Tomas #include <linux/time.h> 35cd02ff0bSMingming Cao #include <linux/jbd2.h> 36a86c6181SAlex Tomas #include <linux/highuid.h> 37a86c6181SAlex Tomas #include <linux/pagemap.h> 38a86c6181SAlex Tomas #include <linux/quotaops.h> 39a86c6181SAlex Tomas #include <linux/string.h> 40a86c6181SAlex Tomas #include <linux/slab.h> 41a2df2a63SAmit Arora #include <linux/falloc.h> 42a86c6181SAlex Tomas #include <asm/uaccess.h> 436873fa0dSEric Sandeen #include <linux/fiemap.h> 443dcf5451SChristoph Hellwig #include "ext4_jbd2.h" 453dcf5451SChristoph Hellwig #include "ext4_extents.h" 46a86c6181SAlex Tomas 47a86c6181SAlex Tomas 48d0d856e8SRandy Dunlap /* 49d0d856e8SRandy Dunlap * ext_pblock: 50d0d856e8SRandy Dunlap * combine low and high parts of physical block number into ext4_fsblk_t 51d0d856e8SRandy Dunlap */ 52748de673SAkira Fujita ext4_fsblk_t ext_pblock(struct ext4_extent *ex) 53f65e6fbaSAlex Tomas { 54f65e6fbaSAlex Tomas ext4_fsblk_t block; 55f65e6fbaSAlex Tomas 56b377611dSAneesh Kumar K.V block = le32_to_cpu(ex->ee_start_lo); 57f65e6fbaSAlex Tomas block |= ((ext4_fsblk_t) le16_to_cpu(ex->ee_start_hi) << 31) << 1; 58f65e6fbaSAlex Tomas return block; 59f65e6fbaSAlex Tomas } 60f65e6fbaSAlex Tomas 61d0d856e8SRandy Dunlap /* 62d0d856e8SRandy Dunlap * idx_pblock: 63d0d856e8SRandy Dunlap * combine low and high parts of a leaf physical block number into ext4_fsblk_t 64d0d856e8SRandy Dunlap */ 65c14c6fd5SAneesh Kumar K.V ext4_fsblk_t idx_pblock(struct ext4_extent_idx *ix) 66f65e6fbaSAlex Tomas { 67f65e6fbaSAlex Tomas ext4_fsblk_t block; 68f65e6fbaSAlex Tomas 69d8dd0b45SAneesh Kumar K.V block = le32_to_cpu(ix->ei_leaf_lo); 70f65e6fbaSAlex Tomas block |= ((ext4_fsblk_t) le16_to_cpu(ix->ei_leaf_hi) << 31) << 1; 71f65e6fbaSAlex Tomas return block; 72f65e6fbaSAlex Tomas } 73f65e6fbaSAlex Tomas 74d0d856e8SRandy Dunlap /* 75d0d856e8SRandy Dunlap * ext4_ext_store_pblock: 76d0d856e8SRandy Dunlap * stores a large physical block number into an extent struct, 77d0d856e8SRandy Dunlap * breaking it into parts 78d0d856e8SRandy Dunlap */ 79c14c6fd5SAneesh Kumar K.V void ext4_ext_store_pblock(struct ext4_extent *ex, ext4_fsblk_t pb) 80f65e6fbaSAlex Tomas { 81b377611dSAneesh Kumar K.V ex->ee_start_lo = cpu_to_le32((unsigned long) (pb & 0xffffffff)); 82f65e6fbaSAlex Tomas ex->ee_start_hi = cpu_to_le16((unsigned long) ((pb >> 31) >> 1) & 0xffff); 83f65e6fbaSAlex Tomas } 84f65e6fbaSAlex Tomas 85d0d856e8SRandy Dunlap /* 86d0d856e8SRandy Dunlap * ext4_idx_store_pblock: 87d0d856e8SRandy Dunlap * stores a large physical block number into an index struct, 88d0d856e8SRandy Dunlap * breaking it into parts 89d0d856e8SRandy Dunlap */ 9009b88252SAvantika Mathur static void ext4_idx_store_pblock(struct ext4_extent_idx *ix, ext4_fsblk_t pb) 91f65e6fbaSAlex Tomas { 92d8dd0b45SAneesh Kumar K.V ix->ei_leaf_lo = cpu_to_le32((unsigned long) (pb & 0xffffffff)); 93f65e6fbaSAlex Tomas ix->ei_leaf_hi = cpu_to_le16((unsigned long) ((pb >> 31) >> 1) & 0xffff); 94f65e6fbaSAlex Tomas } 95f65e6fbaSAlex Tomas 96487caeefSJan Kara static int ext4_ext_truncate_extend_restart(handle_t *handle, 97487caeefSJan Kara struct inode *inode, 98487caeefSJan Kara int needed) 99a86c6181SAlex Tomas { 100a86c6181SAlex Tomas int err; 101a86c6181SAlex Tomas 1020390131bSFrank Mayhar if (!ext4_handle_valid(handle)) 1030390131bSFrank Mayhar return 0; 104a86c6181SAlex Tomas if (handle->h_buffer_credits > needed) 1059102e4faSShen Feng return 0; 1069102e4faSShen Feng err = ext4_journal_extend(handle, needed); 1070123c939STheodore Ts'o if (err <= 0) 1089102e4faSShen Feng return err; 109487caeefSJan Kara err = ext4_truncate_restart_trans(handle, inode, needed); 110487caeefSJan Kara /* 111487caeefSJan Kara * We have dropped i_data_sem so someone might have cached again 112487caeefSJan Kara * an extent we are going to truncate. 113487caeefSJan Kara */ 114487caeefSJan Kara ext4_ext_invalidate_cache(inode); 115487caeefSJan Kara 116487caeefSJan Kara return err; 117a86c6181SAlex Tomas } 118a86c6181SAlex Tomas 119a86c6181SAlex Tomas /* 120a86c6181SAlex Tomas * could return: 121a86c6181SAlex Tomas * - EROFS 122a86c6181SAlex Tomas * - ENOMEM 123a86c6181SAlex Tomas */ 124a86c6181SAlex Tomas static int ext4_ext_get_access(handle_t *handle, struct inode *inode, 125a86c6181SAlex Tomas struct ext4_ext_path *path) 126a86c6181SAlex Tomas { 127a86c6181SAlex Tomas if (path->p_bh) { 128a86c6181SAlex Tomas /* path points to block */ 129a86c6181SAlex Tomas return ext4_journal_get_write_access(handle, path->p_bh); 130a86c6181SAlex Tomas } 131a86c6181SAlex Tomas /* path points to leaf/index in inode body */ 132a86c6181SAlex Tomas /* we use in-core data, no need to protect them */ 133a86c6181SAlex Tomas return 0; 134a86c6181SAlex Tomas } 135a86c6181SAlex Tomas 136a86c6181SAlex Tomas /* 137a86c6181SAlex Tomas * could return: 138a86c6181SAlex Tomas * - EROFS 139a86c6181SAlex Tomas * - ENOMEM 140a86c6181SAlex Tomas * - EIO 141a86c6181SAlex Tomas */ 142a86c6181SAlex Tomas static int ext4_ext_dirty(handle_t *handle, struct inode *inode, 143a86c6181SAlex Tomas struct ext4_ext_path *path) 144a86c6181SAlex Tomas { 145a86c6181SAlex Tomas int err; 146a86c6181SAlex Tomas if (path->p_bh) { 147a86c6181SAlex Tomas /* path points to block */ 1480390131bSFrank Mayhar err = ext4_handle_dirty_metadata(handle, inode, path->p_bh); 149a86c6181SAlex Tomas } else { 150a86c6181SAlex Tomas /* path points to leaf/index in inode body */ 151a86c6181SAlex Tomas err = ext4_mark_inode_dirty(handle, inode); 152a86c6181SAlex Tomas } 153a86c6181SAlex Tomas return err; 154a86c6181SAlex Tomas } 155a86c6181SAlex Tomas 156f65e6fbaSAlex Tomas static ext4_fsblk_t ext4_ext_find_goal(struct inode *inode, 157a86c6181SAlex Tomas struct ext4_ext_path *path, 158725d26d3SAneesh Kumar K.V ext4_lblk_t block) 159a86c6181SAlex Tomas { 160a86c6181SAlex Tomas struct ext4_inode_info *ei = EXT4_I(inode); 161f65e6fbaSAlex Tomas ext4_fsblk_t bg_start; 16274d3487fSValerie Clement ext4_fsblk_t last_block; 163f65e6fbaSAlex Tomas ext4_grpblk_t colour; 164a4912123STheodore Ts'o ext4_group_t block_group; 165a4912123STheodore Ts'o int flex_size = ext4_flex_bg_size(EXT4_SB(inode->i_sb)); 166a86c6181SAlex Tomas int depth; 167a86c6181SAlex Tomas 168a86c6181SAlex Tomas if (path) { 169a86c6181SAlex Tomas struct ext4_extent *ex; 170a86c6181SAlex Tomas depth = path->p_depth; 171a86c6181SAlex Tomas 172a86c6181SAlex Tomas /* try to predict block placement */ 1737e028976SAvantika Mathur ex = path[depth].p_ext; 1747e028976SAvantika Mathur if (ex) 175f65e6fbaSAlex Tomas return ext_pblock(ex)+(block-le32_to_cpu(ex->ee_block)); 176a86c6181SAlex Tomas 177d0d856e8SRandy Dunlap /* it looks like index is empty; 178d0d856e8SRandy Dunlap * try to find starting block from index itself */ 179a86c6181SAlex Tomas if (path[depth].p_bh) 180a86c6181SAlex Tomas return path[depth].p_bh->b_blocknr; 181a86c6181SAlex Tomas } 182a86c6181SAlex Tomas 183a86c6181SAlex Tomas /* OK. use inode's group */ 184a4912123STheodore Ts'o block_group = ei->i_block_group; 185a4912123STheodore Ts'o if (flex_size >= EXT4_FLEX_SIZE_DIR_ALLOC_SCHEME) { 186a4912123STheodore Ts'o /* 187a4912123STheodore Ts'o * If there are at least EXT4_FLEX_SIZE_DIR_ALLOC_SCHEME 188a4912123STheodore Ts'o * block groups per flexgroup, reserve the first block 189a4912123STheodore Ts'o * group for directories and special files. Regular 190a4912123STheodore Ts'o * files will start at the second block group. This 191a4912123STheodore Ts'o * tends to speed up directory access and improves 192a4912123STheodore Ts'o * fsck times. 193a4912123STheodore Ts'o */ 194a4912123STheodore Ts'o block_group &= ~(flex_size-1); 195a4912123STheodore Ts'o if (S_ISREG(inode->i_mode)) 196a4912123STheodore Ts'o block_group++; 197a4912123STheodore Ts'o } 198a4912123STheodore Ts'o bg_start = (block_group * EXT4_BLOCKS_PER_GROUP(inode->i_sb)) + 199a86c6181SAlex Tomas le32_to_cpu(EXT4_SB(inode->i_sb)->s_es->s_first_data_block); 20074d3487fSValerie Clement last_block = ext4_blocks_count(EXT4_SB(inode->i_sb)->s_es) - 1; 20174d3487fSValerie Clement 202a4912123STheodore Ts'o /* 203a4912123STheodore Ts'o * If we are doing delayed allocation, we don't need take 204a4912123STheodore Ts'o * colour into account. 205a4912123STheodore Ts'o */ 206a4912123STheodore Ts'o if (test_opt(inode->i_sb, DELALLOC)) 207a4912123STheodore Ts'o return bg_start; 208a4912123STheodore Ts'o 20974d3487fSValerie Clement if (bg_start + EXT4_BLOCKS_PER_GROUP(inode->i_sb) <= last_block) 210a86c6181SAlex Tomas colour = (current->pid % 16) * 211a86c6181SAlex Tomas (EXT4_BLOCKS_PER_GROUP(inode->i_sb) / 16); 21274d3487fSValerie Clement else 21374d3487fSValerie Clement colour = (current->pid % 16) * ((last_block - bg_start) / 16); 214a86c6181SAlex Tomas return bg_start + colour + block; 215a86c6181SAlex Tomas } 216a86c6181SAlex Tomas 217654b4908SAneesh Kumar K.V /* 218654b4908SAneesh Kumar K.V * Allocation for a meta data block 219654b4908SAneesh Kumar K.V */ 220f65e6fbaSAlex Tomas static ext4_fsblk_t 221654b4908SAneesh Kumar K.V ext4_ext_new_meta_block(handle_t *handle, struct inode *inode, 222a86c6181SAlex Tomas struct ext4_ext_path *path, 223a86c6181SAlex Tomas struct ext4_extent *ex, int *err) 224a86c6181SAlex Tomas { 225f65e6fbaSAlex Tomas ext4_fsblk_t goal, newblock; 226a86c6181SAlex Tomas 227a86c6181SAlex Tomas goal = ext4_ext_find_goal(inode, path, le32_to_cpu(ex->ee_block)); 22897df5d15STheodore Ts'o newblock = ext4_new_meta_blocks(handle, inode, goal, NULL, err); 229a86c6181SAlex Tomas return newblock; 230a86c6181SAlex Tomas } 231a86c6181SAlex Tomas 23255ad63bfSTheodore Ts'o static inline int ext4_ext_space_block(struct inode *inode, int check) 233a86c6181SAlex Tomas { 234a86c6181SAlex Tomas int size; 235a86c6181SAlex Tomas 236a86c6181SAlex Tomas size = (inode->i_sb->s_blocksize - sizeof(struct ext4_extent_header)) 237a86c6181SAlex Tomas / sizeof(struct ext4_extent); 23855ad63bfSTheodore Ts'o if (!check) { 239bbf2f9fbSRobert P. J. Day #ifdef AGGRESSIVE_TEST 240a86c6181SAlex Tomas if (size > 6) 241a86c6181SAlex Tomas size = 6; 242a86c6181SAlex Tomas #endif 24355ad63bfSTheodore Ts'o } 244a86c6181SAlex Tomas return size; 245a86c6181SAlex Tomas } 246a86c6181SAlex Tomas 24755ad63bfSTheodore Ts'o static inline int ext4_ext_space_block_idx(struct inode *inode, int check) 248a86c6181SAlex Tomas { 249a86c6181SAlex Tomas int size; 250a86c6181SAlex Tomas 251a86c6181SAlex Tomas size = (inode->i_sb->s_blocksize - sizeof(struct ext4_extent_header)) 252a86c6181SAlex Tomas / sizeof(struct ext4_extent_idx); 25355ad63bfSTheodore Ts'o if (!check) { 254bbf2f9fbSRobert P. J. Day #ifdef AGGRESSIVE_TEST 255a86c6181SAlex Tomas if (size > 5) 256a86c6181SAlex Tomas size = 5; 257a86c6181SAlex Tomas #endif 25855ad63bfSTheodore Ts'o } 259a86c6181SAlex Tomas return size; 260a86c6181SAlex Tomas } 261a86c6181SAlex Tomas 26255ad63bfSTheodore Ts'o static inline int ext4_ext_space_root(struct inode *inode, int check) 263a86c6181SAlex Tomas { 264a86c6181SAlex Tomas int size; 265a86c6181SAlex Tomas 266a86c6181SAlex Tomas size = sizeof(EXT4_I(inode)->i_data); 267a86c6181SAlex Tomas size -= sizeof(struct ext4_extent_header); 268a86c6181SAlex Tomas size /= sizeof(struct ext4_extent); 26955ad63bfSTheodore Ts'o if (!check) { 270bbf2f9fbSRobert P. J. Day #ifdef AGGRESSIVE_TEST 271a86c6181SAlex Tomas if (size > 3) 272a86c6181SAlex Tomas size = 3; 273a86c6181SAlex Tomas #endif 27455ad63bfSTheodore Ts'o } 275a86c6181SAlex Tomas return size; 276a86c6181SAlex Tomas } 277a86c6181SAlex Tomas 27855ad63bfSTheodore Ts'o static inline int ext4_ext_space_root_idx(struct inode *inode, int check) 279a86c6181SAlex Tomas { 280a86c6181SAlex Tomas int size; 281a86c6181SAlex Tomas 282a86c6181SAlex Tomas size = sizeof(EXT4_I(inode)->i_data); 283a86c6181SAlex Tomas size -= sizeof(struct ext4_extent_header); 284a86c6181SAlex Tomas size /= sizeof(struct ext4_extent_idx); 28555ad63bfSTheodore Ts'o if (!check) { 286bbf2f9fbSRobert P. J. Day #ifdef AGGRESSIVE_TEST 287a86c6181SAlex Tomas if (size > 4) 288a86c6181SAlex Tomas size = 4; 289a86c6181SAlex Tomas #endif 29055ad63bfSTheodore Ts'o } 291a86c6181SAlex Tomas return size; 292a86c6181SAlex Tomas } 293a86c6181SAlex Tomas 294d2a17637SMingming Cao /* 295d2a17637SMingming Cao * Calculate the number of metadata blocks needed 296d2a17637SMingming Cao * to allocate @blocks 297d2a17637SMingming Cao * Worse case is one block per extent 298d2a17637SMingming Cao */ 299d2a17637SMingming Cao int ext4_ext_calc_metadata_amount(struct inode *inode, int blocks) 300d2a17637SMingming Cao { 301d2a17637SMingming Cao int lcap, icap, rcap, leafs, idxs, num; 302d2a17637SMingming Cao int newextents = blocks; 303d2a17637SMingming Cao 30455ad63bfSTheodore Ts'o rcap = ext4_ext_space_root_idx(inode, 0); 30555ad63bfSTheodore Ts'o lcap = ext4_ext_space_block(inode, 0); 30655ad63bfSTheodore Ts'o icap = ext4_ext_space_block_idx(inode, 0); 307d2a17637SMingming Cao 308d2a17637SMingming Cao /* number of new leaf blocks needed */ 309d2a17637SMingming Cao num = leafs = (newextents + lcap - 1) / lcap; 310d2a17637SMingming Cao 311d2a17637SMingming Cao /* 312d2a17637SMingming Cao * Worse case, we need separate index block(s) 313d2a17637SMingming Cao * to link all new leaf blocks 314d2a17637SMingming Cao */ 315d2a17637SMingming Cao idxs = (leafs + icap - 1) / icap; 316d2a17637SMingming Cao do { 317d2a17637SMingming Cao num += idxs; 318d2a17637SMingming Cao idxs = (idxs + icap - 1) / icap; 319d2a17637SMingming Cao } while (idxs > rcap); 320d2a17637SMingming Cao 321d2a17637SMingming Cao return num; 322d2a17637SMingming Cao } 323d2a17637SMingming Cao 324c29c0ae7SAlex Tomas static int 325c29c0ae7SAlex Tomas ext4_ext_max_entries(struct inode *inode, int depth) 326c29c0ae7SAlex Tomas { 327c29c0ae7SAlex Tomas int max; 328c29c0ae7SAlex Tomas 329c29c0ae7SAlex Tomas if (depth == ext_depth(inode)) { 330c29c0ae7SAlex Tomas if (depth == 0) 33155ad63bfSTheodore Ts'o max = ext4_ext_space_root(inode, 1); 332c29c0ae7SAlex Tomas else 33355ad63bfSTheodore Ts'o max = ext4_ext_space_root_idx(inode, 1); 334c29c0ae7SAlex Tomas } else { 335c29c0ae7SAlex Tomas if (depth == 0) 33655ad63bfSTheodore Ts'o max = ext4_ext_space_block(inode, 1); 337c29c0ae7SAlex Tomas else 33855ad63bfSTheodore Ts'o max = ext4_ext_space_block_idx(inode, 1); 339c29c0ae7SAlex Tomas } 340c29c0ae7SAlex Tomas 341c29c0ae7SAlex Tomas return max; 342c29c0ae7SAlex Tomas } 343c29c0ae7SAlex Tomas 34456b19868SAneesh Kumar K.V static int ext4_valid_extent(struct inode *inode, struct ext4_extent *ext) 34556b19868SAneesh Kumar K.V { 3466fd058f7STheodore Ts'o ext4_fsblk_t block = ext_pblock(ext); 34756b19868SAneesh Kumar K.V int len = ext4_ext_get_actual_len(ext); 348e84a26ceSTheodore Ts'o 3496fd058f7STheodore Ts'o return ext4_data_block_valid(EXT4_SB(inode->i_sb), block, len); 35056b19868SAneesh Kumar K.V } 35156b19868SAneesh Kumar K.V 35256b19868SAneesh Kumar K.V static int ext4_valid_extent_idx(struct inode *inode, 35356b19868SAneesh Kumar K.V struct ext4_extent_idx *ext_idx) 35456b19868SAneesh Kumar K.V { 3556fd058f7STheodore Ts'o ext4_fsblk_t block = idx_pblock(ext_idx); 356e84a26ceSTheodore Ts'o 3576fd058f7STheodore Ts'o return ext4_data_block_valid(EXT4_SB(inode->i_sb), block, 1); 35856b19868SAneesh Kumar K.V } 35956b19868SAneesh Kumar K.V 36056b19868SAneesh Kumar K.V static int ext4_valid_extent_entries(struct inode *inode, 36156b19868SAneesh Kumar K.V struct ext4_extent_header *eh, 36256b19868SAneesh Kumar K.V int depth) 36356b19868SAneesh Kumar K.V { 36456b19868SAneesh Kumar K.V struct ext4_extent *ext; 36556b19868SAneesh Kumar K.V struct ext4_extent_idx *ext_idx; 36656b19868SAneesh Kumar K.V unsigned short entries; 36756b19868SAneesh Kumar K.V if (eh->eh_entries == 0) 36856b19868SAneesh Kumar K.V return 1; 36956b19868SAneesh Kumar K.V 37056b19868SAneesh Kumar K.V entries = le16_to_cpu(eh->eh_entries); 37156b19868SAneesh Kumar K.V 37256b19868SAneesh Kumar K.V if (depth == 0) { 37356b19868SAneesh Kumar K.V /* leaf entries */ 37456b19868SAneesh Kumar K.V ext = EXT_FIRST_EXTENT(eh); 37556b19868SAneesh Kumar K.V while (entries) { 37656b19868SAneesh Kumar K.V if (!ext4_valid_extent(inode, ext)) 37756b19868SAneesh Kumar K.V return 0; 37856b19868SAneesh Kumar K.V ext++; 37956b19868SAneesh Kumar K.V entries--; 38056b19868SAneesh Kumar K.V } 38156b19868SAneesh Kumar K.V } else { 38256b19868SAneesh Kumar K.V ext_idx = EXT_FIRST_INDEX(eh); 38356b19868SAneesh Kumar K.V while (entries) { 38456b19868SAneesh Kumar K.V if (!ext4_valid_extent_idx(inode, ext_idx)) 38556b19868SAneesh Kumar K.V return 0; 38656b19868SAneesh Kumar K.V ext_idx++; 38756b19868SAneesh Kumar K.V entries--; 38856b19868SAneesh Kumar K.V } 38956b19868SAneesh Kumar K.V } 39056b19868SAneesh Kumar K.V return 1; 39156b19868SAneesh Kumar K.V } 39256b19868SAneesh Kumar K.V 39356b19868SAneesh Kumar K.V static int __ext4_ext_check(const char *function, struct inode *inode, 394c29c0ae7SAlex Tomas struct ext4_extent_header *eh, 395c29c0ae7SAlex Tomas int depth) 396c29c0ae7SAlex Tomas { 397c29c0ae7SAlex Tomas const char *error_msg; 398c29c0ae7SAlex Tomas int max = 0; 399c29c0ae7SAlex Tomas 400c29c0ae7SAlex Tomas if (unlikely(eh->eh_magic != EXT4_EXT_MAGIC)) { 401c29c0ae7SAlex Tomas error_msg = "invalid magic"; 402c29c0ae7SAlex Tomas goto corrupted; 403c29c0ae7SAlex Tomas } 404c29c0ae7SAlex Tomas if (unlikely(le16_to_cpu(eh->eh_depth) != depth)) { 405c29c0ae7SAlex Tomas error_msg = "unexpected eh_depth"; 406c29c0ae7SAlex Tomas goto corrupted; 407c29c0ae7SAlex Tomas } 408c29c0ae7SAlex Tomas if (unlikely(eh->eh_max == 0)) { 409c29c0ae7SAlex Tomas error_msg = "invalid eh_max"; 410c29c0ae7SAlex Tomas goto corrupted; 411c29c0ae7SAlex Tomas } 412c29c0ae7SAlex Tomas max = ext4_ext_max_entries(inode, depth); 413c29c0ae7SAlex Tomas if (unlikely(le16_to_cpu(eh->eh_max) > max)) { 414c29c0ae7SAlex Tomas error_msg = "too large eh_max"; 415c29c0ae7SAlex Tomas goto corrupted; 416c29c0ae7SAlex Tomas } 417c29c0ae7SAlex Tomas if (unlikely(le16_to_cpu(eh->eh_entries) > le16_to_cpu(eh->eh_max))) { 418c29c0ae7SAlex Tomas error_msg = "invalid eh_entries"; 419c29c0ae7SAlex Tomas goto corrupted; 420c29c0ae7SAlex Tomas } 42156b19868SAneesh Kumar K.V if (!ext4_valid_extent_entries(inode, eh, depth)) { 42256b19868SAneesh Kumar K.V error_msg = "invalid extent entries"; 42356b19868SAneesh Kumar K.V goto corrupted; 42456b19868SAneesh Kumar K.V } 425c29c0ae7SAlex Tomas return 0; 426c29c0ae7SAlex Tomas 427c29c0ae7SAlex Tomas corrupted: 428c29c0ae7SAlex Tomas ext4_error(inode->i_sb, function, 42956b19868SAneesh Kumar K.V "bad header/extent in inode #%lu: %s - magic %x, " 430c29c0ae7SAlex Tomas "entries %u, max %u(%u), depth %u(%u)", 431c29c0ae7SAlex Tomas inode->i_ino, error_msg, le16_to_cpu(eh->eh_magic), 432c29c0ae7SAlex Tomas le16_to_cpu(eh->eh_entries), le16_to_cpu(eh->eh_max), 433c29c0ae7SAlex Tomas max, le16_to_cpu(eh->eh_depth), depth); 434c29c0ae7SAlex Tomas 435c29c0ae7SAlex Tomas return -EIO; 436c29c0ae7SAlex Tomas } 437c29c0ae7SAlex Tomas 43856b19868SAneesh Kumar K.V #define ext4_ext_check(inode, eh, depth) \ 43956b19868SAneesh Kumar K.V __ext4_ext_check(__func__, inode, eh, depth) 440c29c0ae7SAlex Tomas 4417a262f7cSAneesh Kumar K.V int ext4_ext_check_inode(struct inode *inode) 4427a262f7cSAneesh Kumar K.V { 4437a262f7cSAneesh Kumar K.V return ext4_ext_check(inode, ext_inode_hdr(inode), ext_depth(inode)); 4447a262f7cSAneesh Kumar K.V } 4457a262f7cSAneesh Kumar K.V 446a86c6181SAlex Tomas #ifdef EXT_DEBUG 447a86c6181SAlex Tomas static void ext4_ext_show_path(struct inode *inode, struct ext4_ext_path *path) 448a86c6181SAlex Tomas { 449a86c6181SAlex Tomas int k, l = path->p_depth; 450a86c6181SAlex Tomas 451a86c6181SAlex Tomas ext_debug("path:"); 452a86c6181SAlex Tomas for (k = 0; k <= l; k++, path++) { 453a86c6181SAlex Tomas if (path->p_idx) { 4542ae02107SMingming Cao ext_debug(" %d->%llu", le32_to_cpu(path->p_idx->ei_block), 455f65e6fbaSAlex Tomas idx_pblock(path->p_idx)); 456a86c6181SAlex Tomas } else if (path->p_ext) { 457553f9008SMingming ext_debug(" %d:[%d]%d:%llu ", 458a86c6181SAlex Tomas le32_to_cpu(path->p_ext->ee_block), 459553f9008SMingming ext4_ext_is_uninitialized(path->p_ext), 460a2df2a63SAmit Arora ext4_ext_get_actual_len(path->p_ext), 461f65e6fbaSAlex Tomas ext_pblock(path->p_ext)); 462a86c6181SAlex Tomas } else 463a86c6181SAlex Tomas ext_debug(" []"); 464a86c6181SAlex Tomas } 465a86c6181SAlex Tomas ext_debug("\n"); 466a86c6181SAlex Tomas } 467a86c6181SAlex Tomas 468a86c6181SAlex Tomas static void ext4_ext_show_leaf(struct inode *inode, struct ext4_ext_path *path) 469a86c6181SAlex Tomas { 470a86c6181SAlex Tomas int depth = ext_depth(inode); 471a86c6181SAlex Tomas struct ext4_extent_header *eh; 472a86c6181SAlex Tomas struct ext4_extent *ex; 473a86c6181SAlex Tomas int i; 474a86c6181SAlex Tomas 475a86c6181SAlex Tomas if (!path) 476a86c6181SAlex Tomas return; 477a86c6181SAlex Tomas 478a86c6181SAlex Tomas eh = path[depth].p_hdr; 479a86c6181SAlex Tomas ex = EXT_FIRST_EXTENT(eh); 480a86c6181SAlex Tomas 481553f9008SMingming ext_debug("Displaying leaf extents for inode %lu\n", inode->i_ino); 482553f9008SMingming 483a86c6181SAlex Tomas for (i = 0; i < le16_to_cpu(eh->eh_entries); i++, ex++) { 484553f9008SMingming ext_debug("%d:[%d]%d:%llu ", le32_to_cpu(ex->ee_block), 485553f9008SMingming ext4_ext_is_uninitialized(ex), 486a2df2a63SAmit Arora ext4_ext_get_actual_len(ex), ext_pblock(ex)); 487a86c6181SAlex Tomas } 488a86c6181SAlex Tomas ext_debug("\n"); 489a86c6181SAlex Tomas } 490a86c6181SAlex Tomas #else 491a86c6181SAlex Tomas #define ext4_ext_show_path(inode, path) 492a86c6181SAlex Tomas #define ext4_ext_show_leaf(inode, path) 493a86c6181SAlex Tomas #endif 494a86c6181SAlex Tomas 495b35905c1SAneesh Kumar K.V void ext4_ext_drop_refs(struct ext4_ext_path *path) 496a86c6181SAlex Tomas { 497a86c6181SAlex Tomas int depth = path->p_depth; 498a86c6181SAlex Tomas int i; 499a86c6181SAlex Tomas 500a86c6181SAlex Tomas for (i = 0; i <= depth; i++, path++) 501a86c6181SAlex Tomas if (path->p_bh) { 502a86c6181SAlex Tomas brelse(path->p_bh); 503a86c6181SAlex Tomas path->p_bh = NULL; 504a86c6181SAlex Tomas } 505a86c6181SAlex Tomas } 506a86c6181SAlex Tomas 507a86c6181SAlex Tomas /* 508d0d856e8SRandy Dunlap * ext4_ext_binsearch_idx: 509d0d856e8SRandy Dunlap * binary search for the closest index of the given block 510c29c0ae7SAlex Tomas * the header must be checked before calling this 511a86c6181SAlex Tomas */ 512a86c6181SAlex Tomas static void 513725d26d3SAneesh Kumar K.V ext4_ext_binsearch_idx(struct inode *inode, 514725d26d3SAneesh Kumar K.V struct ext4_ext_path *path, ext4_lblk_t block) 515a86c6181SAlex Tomas { 516a86c6181SAlex Tomas struct ext4_extent_header *eh = path->p_hdr; 517a86c6181SAlex Tomas struct ext4_extent_idx *r, *l, *m; 518a86c6181SAlex Tomas 519a86c6181SAlex Tomas 520bba90743SEric Sandeen ext_debug("binsearch for %u(idx): ", block); 521a86c6181SAlex Tomas 522a86c6181SAlex Tomas l = EXT_FIRST_INDEX(eh) + 1; 523e9f410b1SDmitry Monakhov r = EXT_LAST_INDEX(eh); 524a86c6181SAlex Tomas while (l <= r) { 525a86c6181SAlex Tomas m = l + (r - l) / 2; 526a86c6181SAlex Tomas if (block < le32_to_cpu(m->ei_block)) 527a86c6181SAlex Tomas r = m - 1; 528a86c6181SAlex Tomas else 529a86c6181SAlex Tomas l = m + 1; 53026d535edSDmitry Monakhov ext_debug("%p(%u):%p(%u):%p(%u) ", l, le32_to_cpu(l->ei_block), 53126d535edSDmitry Monakhov m, le32_to_cpu(m->ei_block), 53226d535edSDmitry Monakhov r, le32_to_cpu(r->ei_block)); 533a86c6181SAlex Tomas } 534a86c6181SAlex Tomas 535a86c6181SAlex Tomas path->p_idx = l - 1; 536f65e6fbaSAlex Tomas ext_debug(" -> %d->%lld ", le32_to_cpu(path->p_idx->ei_block), 53726d535edSDmitry Monakhov idx_pblock(path->p_idx)); 538a86c6181SAlex Tomas 539a86c6181SAlex Tomas #ifdef CHECK_BINSEARCH 540a86c6181SAlex Tomas { 541a86c6181SAlex Tomas struct ext4_extent_idx *chix, *ix; 542a86c6181SAlex Tomas int k; 543a86c6181SAlex Tomas 544a86c6181SAlex Tomas chix = ix = EXT_FIRST_INDEX(eh); 545a86c6181SAlex Tomas for (k = 0; k < le16_to_cpu(eh->eh_entries); k++, ix++) { 546a86c6181SAlex Tomas if (k != 0 && 547a86c6181SAlex Tomas le32_to_cpu(ix->ei_block) <= le32_to_cpu(ix[-1].ei_block)) { 5484776004fSTheodore Ts'o printk(KERN_DEBUG "k=%d, ix=0x%p, " 5494776004fSTheodore Ts'o "first=0x%p\n", k, 550a86c6181SAlex Tomas ix, EXT_FIRST_INDEX(eh)); 5514776004fSTheodore Ts'o printk(KERN_DEBUG "%u <= %u\n", 552a86c6181SAlex Tomas le32_to_cpu(ix->ei_block), 553a86c6181SAlex Tomas le32_to_cpu(ix[-1].ei_block)); 554a86c6181SAlex Tomas } 555a86c6181SAlex Tomas BUG_ON(k && le32_to_cpu(ix->ei_block) 556a86c6181SAlex Tomas <= le32_to_cpu(ix[-1].ei_block)); 557a86c6181SAlex Tomas if (block < le32_to_cpu(ix->ei_block)) 558a86c6181SAlex Tomas break; 559a86c6181SAlex Tomas chix = ix; 560a86c6181SAlex Tomas } 561a86c6181SAlex Tomas BUG_ON(chix != path->p_idx); 562a86c6181SAlex Tomas } 563a86c6181SAlex Tomas #endif 564a86c6181SAlex Tomas 565a86c6181SAlex Tomas } 566a86c6181SAlex Tomas 567a86c6181SAlex Tomas /* 568d0d856e8SRandy Dunlap * ext4_ext_binsearch: 569d0d856e8SRandy Dunlap * binary search for closest extent of the given block 570c29c0ae7SAlex Tomas * the header must be checked before calling this 571a86c6181SAlex Tomas */ 572a86c6181SAlex Tomas static void 573725d26d3SAneesh Kumar K.V ext4_ext_binsearch(struct inode *inode, 574725d26d3SAneesh Kumar K.V struct ext4_ext_path *path, ext4_lblk_t block) 575a86c6181SAlex Tomas { 576a86c6181SAlex Tomas struct ext4_extent_header *eh = path->p_hdr; 577a86c6181SAlex Tomas struct ext4_extent *r, *l, *m; 578a86c6181SAlex Tomas 579a86c6181SAlex Tomas if (eh->eh_entries == 0) { 580a86c6181SAlex Tomas /* 581d0d856e8SRandy Dunlap * this leaf is empty: 582a86c6181SAlex Tomas * we get such a leaf in split/add case 583a86c6181SAlex Tomas */ 584a86c6181SAlex Tomas return; 585a86c6181SAlex Tomas } 586a86c6181SAlex Tomas 587bba90743SEric Sandeen ext_debug("binsearch for %u: ", block); 588a86c6181SAlex Tomas 589a86c6181SAlex Tomas l = EXT_FIRST_EXTENT(eh) + 1; 590e9f410b1SDmitry Monakhov r = EXT_LAST_EXTENT(eh); 591a86c6181SAlex Tomas 592a86c6181SAlex Tomas while (l <= r) { 593a86c6181SAlex Tomas m = l + (r - l) / 2; 594a86c6181SAlex Tomas if (block < le32_to_cpu(m->ee_block)) 595a86c6181SAlex Tomas r = m - 1; 596a86c6181SAlex Tomas else 597a86c6181SAlex Tomas l = m + 1; 59826d535edSDmitry Monakhov ext_debug("%p(%u):%p(%u):%p(%u) ", l, le32_to_cpu(l->ee_block), 59926d535edSDmitry Monakhov m, le32_to_cpu(m->ee_block), 60026d535edSDmitry Monakhov r, le32_to_cpu(r->ee_block)); 601a86c6181SAlex Tomas } 602a86c6181SAlex Tomas 603a86c6181SAlex Tomas path->p_ext = l - 1; 604553f9008SMingming ext_debug(" -> %d:%llu:[%d]%d ", 605a86c6181SAlex Tomas le32_to_cpu(path->p_ext->ee_block), 606f65e6fbaSAlex Tomas ext_pblock(path->p_ext), 607553f9008SMingming ext4_ext_is_uninitialized(path->p_ext), 608a2df2a63SAmit Arora ext4_ext_get_actual_len(path->p_ext)); 609a86c6181SAlex Tomas 610a86c6181SAlex Tomas #ifdef CHECK_BINSEARCH 611a86c6181SAlex Tomas { 612a86c6181SAlex Tomas struct ext4_extent *chex, *ex; 613a86c6181SAlex Tomas int k; 614a86c6181SAlex Tomas 615a86c6181SAlex Tomas chex = ex = EXT_FIRST_EXTENT(eh); 616a86c6181SAlex Tomas for (k = 0; k < le16_to_cpu(eh->eh_entries); k++, ex++) { 617a86c6181SAlex Tomas BUG_ON(k && le32_to_cpu(ex->ee_block) 618a86c6181SAlex Tomas <= le32_to_cpu(ex[-1].ee_block)); 619a86c6181SAlex Tomas if (block < le32_to_cpu(ex->ee_block)) 620a86c6181SAlex Tomas break; 621a86c6181SAlex Tomas chex = ex; 622a86c6181SAlex Tomas } 623a86c6181SAlex Tomas BUG_ON(chex != path->p_ext); 624a86c6181SAlex Tomas } 625a86c6181SAlex Tomas #endif 626a86c6181SAlex Tomas 627a86c6181SAlex Tomas } 628a86c6181SAlex Tomas 629a86c6181SAlex Tomas int ext4_ext_tree_init(handle_t *handle, struct inode *inode) 630a86c6181SAlex Tomas { 631a86c6181SAlex Tomas struct ext4_extent_header *eh; 632a86c6181SAlex Tomas 633a86c6181SAlex Tomas eh = ext_inode_hdr(inode); 634a86c6181SAlex Tomas eh->eh_depth = 0; 635a86c6181SAlex Tomas eh->eh_entries = 0; 636a86c6181SAlex Tomas eh->eh_magic = EXT4_EXT_MAGIC; 63755ad63bfSTheodore Ts'o eh->eh_max = cpu_to_le16(ext4_ext_space_root(inode, 0)); 638a86c6181SAlex Tomas ext4_mark_inode_dirty(handle, inode); 639a86c6181SAlex Tomas ext4_ext_invalidate_cache(inode); 640a86c6181SAlex Tomas return 0; 641a86c6181SAlex Tomas } 642a86c6181SAlex Tomas 643a86c6181SAlex Tomas struct ext4_ext_path * 644725d26d3SAneesh Kumar K.V ext4_ext_find_extent(struct inode *inode, ext4_lblk_t block, 645725d26d3SAneesh Kumar K.V struct ext4_ext_path *path) 646a86c6181SAlex Tomas { 647a86c6181SAlex Tomas struct ext4_extent_header *eh; 648a86c6181SAlex Tomas struct buffer_head *bh; 649a86c6181SAlex Tomas short int depth, i, ppos = 0, alloc = 0; 650a86c6181SAlex Tomas 651a86c6181SAlex Tomas eh = ext_inode_hdr(inode); 652c29c0ae7SAlex Tomas depth = ext_depth(inode); 653a86c6181SAlex Tomas 654a86c6181SAlex Tomas /* account possible depth increase */ 655a86c6181SAlex Tomas if (!path) { 6565d4958f9SAvantika Mathur path = kzalloc(sizeof(struct ext4_ext_path) * (depth + 2), 657a86c6181SAlex Tomas GFP_NOFS); 658a86c6181SAlex Tomas if (!path) 659a86c6181SAlex Tomas return ERR_PTR(-ENOMEM); 660a86c6181SAlex Tomas alloc = 1; 661a86c6181SAlex Tomas } 662a86c6181SAlex Tomas path[0].p_hdr = eh; 6631973adcbSShen Feng path[0].p_bh = NULL; 664a86c6181SAlex Tomas 665c29c0ae7SAlex Tomas i = depth; 666a86c6181SAlex Tomas /* walk through the tree */ 667a86c6181SAlex Tomas while (i) { 6687a262f7cSAneesh Kumar K.V int need_to_validate = 0; 6697a262f7cSAneesh Kumar K.V 670a86c6181SAlex Tomas ext_debug("depth %d: num %d, max %d\n", 671a86c6181SAlex Tomas ppos, le16_to_cpu(eh->eh_entries), le16_to_cpu(eh->eh_max)); 672c29c0ae7SAlex Tomas 673a86c6181SAlex Tomas ext4_ext_binsearch_idx(inode, path + ppos, block); 674f65e6fbaSAlex Tomas path[ppos].p_block = idx_pblock(path[ppos].p_idx); 675a86c6181SAlex Tomas path[ppos].p_depth = i; 676a86c6181SAlex Tomas path[ppos].p_ext = NULL; 677a86c6181SAlex Tomas 6787a262f7cSAneesh Kumar K.V bh = sb_getblk(inode->i_sb, path[ppos].p_block); 6797a262f7cSAneesh Kumar K.V if (unlikely(!bh)) 680a86c6181SAlex Tomas goto err; 6817a262f7cSAneesh Kumar K.V if (!bh_uptodate_or_lock(bh)) { 6827a262f7cSAneesh Kumar K.V if (bh_submit_read(bh) < 0) { 6837a262f7cSAneesh Kumar K.V put_bh(bh); 6847a262f7cSAneesh Kumar K.V goto err; 6857a262f7cSAneesh Kumar K.V } 6867a262f7cSAneesh Kumar K.V /* validate the extent entries */ 6877a262f7cSAneesh Kumar K.V need_to_validate = 1; 6887a262f7cSAneesh Kumar K.V } 689a86c6181SAlex Tomas eh = ext_block_hdr(bh); 690a86c6181SAlex Tomas ppos++; 691a86c6181SAlex Tomas BUG_ON(ppos > depth); 692a86c6181SAlex Tomas path[ppos].p_bh = bh; 693a86c6181SAlex Tomas path[ppos].p_hdr = eh; 694a86c6181SAlex Tomas i--; 695a86c6181SAlex Tomas 6967a262f7cSAneesh Kumar K.V if (need_to_validate && ext4_ext_check(inode, eh, i)) 697a86c6181SAlex Tomas goto err; 698a86c6181SAlex Tomas } 699a86c6181SAlex Tomas 700a86c6181SAlex Tomas path[ppos].p_depth = i; 701a86c6181SAlex Tomas path[ppos].p_ext = NULL; 702a86c6181SAlex Tomas path[ppos].p_idx = NULL; 703a86c6181SAlex Tomas 704a86c6181SAlex Tomas /* find extent */ 705a86c6181SAlex Tomas ext4_ext_binsearch(inode, path + ppos, block); 7061973adcbSShen Feng /* if not an empty leaf */ 7071973adcbSShen Feng if (path[ppos].p_ext) 7081973adcbSShen Feng path[ppos].p_block = ext_pblock(path[ppos].p_ext); 709a86c6181SAlex Tomas 710a86c6181SAlex Tomas ext4_ext_show_path(inode, path); 711a86c6181SAlex Tomas 712a86c6181SAlex Tomas return path; 713a86c6181SAlex Tomas 714a86c6181SAlex Tomas err: 715a86c6181SAlex Tomas ext4_ext_drop_refs(path); 716a86c6181SAlex Tomas if (alloc) 717a86c6181SAlex Tomas kfree(path); 718a86c6181SAlex Tomas return ERR_PTR(-EIO); 719a86c6181SAlex Tomas } 720a86c6181SAlex Tomas 721a86c6181SAlex Tomas /* 722d0d856e8SRandy Dunlap * ext4_ext_insert_index: 723d0d856e8SRandy Dunlap * insert new index [@logical;@ptr] into the block at @curp; 724d0d856e8SRandy Dunlap * check where to insert: before @curp or after @curp 725a86c6181SAlex Tomas */ 7260031462bSMingming Cao int ext4_ext_insert_index(handle_t *handle, struct inode *inode, 727a86c6181SAlex Tomas struct ext4_ext_path *curp, 728f65e6fbaSAlex Tomas int logical, ext4_fsblk_t ptr) 729a86c6181SAlex Tomas { 730a86c6181SAlex Tomas struct ext4_extent_idx *ix; 731a86c6181SAlex Tomas int len, err; 732a86c6181SAlex Tomas 7337e028976SAvantika Mathur err = ext4_ext_get_access(handle, inode, curp); 7347e028976SAvantika Mathur if (err) 735a86c6181SAlex Tomas return err; 736a86c6181SAlex Tomas 737a86c6181SAlex Tomas BUG_ON(logical == le32_to_cpu(curp->p_idx->ei_block)); 738a86c6181SAlex Tomas len = EXT_MAX_INDEX(curp->p_hdr) - curp->p_idx; 739a86c6181SAlex Tomas if (logical > le32_to_cpu(curp->p_idx->ei_block)) { 740a86c6181SAlex Tomas /* insert after */ 741a86c6181SAlex Tomas if (curp->p_idx != EXT_LAST_INDEX(curp->p_hdr)) { 742a86c6181SAlex Tomas len = (len - 1) * sizeof(struct ext4_extent_idx); 743a86c6181SAlex Tomas len = len < 0 ? 0 : len; 74426d535edSDmitry Monakhov ext_debug("insert new index %d after: %llu. " 745a86c6181SAlex Tomas "move %d from 0x%p to 0x%p\n", 746a86c6181SAlex Tomas logical, ptr, len, 747a86c6181SAlex Tomas (curp->p_idx + 1), (curp->p_idx + 2)); 748a86c6181SAlex Tomas memmove(curp->p_idx + 2, curp->p_idx + 1, len); 749a86c6181SAlex Tomas } 750a86c6181SAlex Tomas ix = curp->p_idx + 1; 751a86c6181SAlex Tomas } else { 752a86c6181SAlex Tomas /* insert before */ 753a86c6181SAlex Tomas len = len * sizeof(struct ext4_extent_idx); 754a86c6181SAlex Tomas len = len < 0 ? 0 : len; 75526d535edSDmitry Monakhov ext_debug("insert new index %d before: %llu. " 756a86c6181SAlex Tomas "move %d from 0x%p to 0x%p\n", 757a86c6181SAlex Tomas logical, ptr, len, 758a86c6181SAlex Tomas curp->p_idx, (curp->p_idx + 1)); 759a86c6181SAlex Tomas memmove(curp->p_idx + 1, curp->p_idx, len); 760a86c6181SAlex Tomas ix = curp->p_idx; 761a86c6181SAlex Tomas } 762a86c6181SAlex Tomas 763a86c6181SAlex Tomas ix->ei_block = cpu_to_le32(logical); 764f65e6fbaSAlex Tomas ext4_idx_store_pblock(ix, ptr); 765e8546d06SMarcin Slusarz le16_add_cpu(&curp->p_hdr->eh_entries, 1); 766a86c6181SAlex Tomas 767a86c6181SAlex Tomas BUG_ON(le16_to_cpu(curp->p_hdr->eh_entries) 768a86c6181SAlex Tomas > le16_to_cpu(curp->p_hdr->eh_max)); 769a86c6181SAlex Tomas BUG_ON(ix > EXT_LAST_INDEX(curp->p_hdr)); 770a86c6181SAlex Tomas 771a86c6181SAlex Tomas err = ext4_ext_dirty(handle, inode, curp); 772a86c6181SAlex Tomas ext4_std_error(inode->i_sb, err); 773a86c6181SAlex Tomas 774a86c6181SAlex Tomas return err; 775a86c6181SAlex Tomas } 776a86c6181SAlex Tomas 777a86c6181SAlex Tomas /* 778d0d856e8SRandy Dunlap * ext4_ext_split: 779d0d856e8SRandy Dunlap * inserts new subtree into the path, using free index entry 780d0d856e8SRandy Dunlap * at depth @at: 781a86c6181SAlex Tomas * - allocates all needed blocks (new leaf and all intermediate index blocks) 782a86c6181SAlex Tomas * - makes decision where to split 783d0d856e8SRandy Dunlap * - moves remaining extents and index entries (right to the split point) 784a86c6181SAlex Tomas * into the newly allocated blocks 785d0d856e8SRandy Dunlap * - initializes subtree 786a86c6181SAlex Tomas */ 787a86c6181SAlex Tomas static int ext4_ext_split(handle_t *handle, struct inode *inode, 788a86c6181SAlex Tomas struct ext4_ext_path *path, 789a86c6181SAlex Tomas struct ext4_extent *newext, int at) 790a86c6181SAlex Tomas { 791a86c6181SAlex Tomas struct buffer_head *bh = NULL; 792a86c6181SAlex Tomas int depth = ext_depth(inode); 793a86c6181SAlex Tomas struct ext4_extent_header *neh; 794a86c6181SAlex Tomas struct ext4_extent_idx *fidx; 795a86c6181SAlex Tomas struct ext4_extent *ex; 796a86c6181SAlex Tomas int i = at, k, m, a; 797f65e6fbaSAlex Tomas ext4_fsblk_t newblock, oldblock; 798a86c6181SAlex Tomas __le32 border; 799f65e6fbaSAlex Tomas ext4_fsblk_t *ablocks = NULL; /* array of allocated blocks */ 800a86c6181SAlex Tomas int err = 0; 801a86c6181SAlex Tomas 802a86c6181SAlex Tomas /* make decision: where to split? */ 803d0d856e8SRandy Dunlap /* FIXME: now decision is simplest: at current extent */ 804a86c6181SAlex Tomas 805d0d856e8SRandy Dunlap /* if current leaf will be split, then we should use 806a86c6181SAlex Tomas * border from split point */ 807a86c6181SAlex Tomas BUG_ON(path[depth].p_ext > EXT_MAX_EXTENT(path[depth].p_hdr)); 808a86c6181SAlex Tomas if (path[depth].p_ext != EXT_MAX_EXTENT(path[depth].p_hdr)) { 809a86c6181SAlex Tomas border = path[depth].p_ext[1].ee_block; 810d0d856e8SRandy Dunlap ext_debug("leaf will be split." 811a86c6181SAlex Tomas " next leaf starts at %d\n", 812a86c6181SAlex Tomas le32_to_cpu(border)); 813a86c6181SAlex Tomas } else { 814a86c6181SAlex Tomas border = newext->ee_block; 815a86c6181SAlex Tomas ext_debug("leaf will be added." 816a86c6181SAlex Tomas " next leaf starts at %d\n", 817a86c6181SAlex Tomas le32_to_cpu(border)); 818a86c6181SAlex Tomas } 819a86c6181SAlex Tomas 820a86c6181SAlex Tomas /* 821d0d856e8SRandy Dunlap * If error occurs, then we break processing 822d0d856e8SRandy Dunlap * and mark filesystem read-only. index won't 823a86c6181SAlex Tomas * be inserted and tree will be in consistent 824d0d856e8SRandy Dunlap * state. Next mount will repair buffers too. 825a86c6181SAlex Tomas */ 826a86c6181SAlex Tomas 827a86c6181SAlex Tomas /* 828d0d856e8SRandy Dunlap * Get array to track all allocated blocks. 829d0d856e8SRandy Dunlap * We need this to handle errors and free blocks 830d0d856e8SRandy Dunlap * upon them. 831a86c6181SAlex Tomas */ 8325d4958f9SAvantika Mathur ablocks = kzalloc(sizeof(ext4_fsblk_t) * depth, GFP_NOFS); 833a86c6181SAlex Tomas if (!ablocks) 834a86c6181SAlex Tomas return -ENOMEM; 835a86c6181SAlex Tomas 836a86c6181SAlex Tomas /* allocate all needed blocks */ 837a86c6181SAlex Tomas ext_debug("allocate %d blocks for indexes/leaf\n", depth - at); 838a86c6181SAlex Tomas for (a = 0; a < depth - at; a++) { 839654b4908SAneesh Kumar K.V newblock = ext4_ext_new_meta_block(handle, inode, path, 840654b4908SAneesh Kumar K.V newext, &err); 841a86c6181SAlex Tomas if (newblock == 0) 842a86c6181SAlex Tomas goto cleanup; 843a86c6181SAlex Tomas ablocks[a] = newblock; 844a86c6181SAlex Tomas } 845a86c6181SAlex Tomas 846a86c6181SAlex Tomas /* initialize new leaf */ 847a86c6181SAlex Tomas newblock = ablocks[--a]; 848a86c6181SAlex Tomas BUG_ON(newblock == 0); 849a86c6181SAlex Tomas bh = sb_getblk(inode->i_sb, newblock); 850a86c6181SAlex Tomas if (!bh) { 851a86c6181SAlex Tomas err = -EIO; 852a86c6181SAlex Tomas goto cleanup; 853a86c6181SAlex Tomas } 854a86c6181SAlex Tomas lock_buffer(bh); 855a86c6181SAlex Tomas 8567e028976SAvantika Mathur err = ext4_journal_get_create_access(handle, bh); 8577e028976SAvantika Mathur if (err) 858a86c6181SAlex Tomas goto cleanup; 859a86c6181SAlex Tomas 860a86c6181SAlex Tomas neh = ext_block_hdr(bh); 861a86c6181SAlex Tomas neh->eh_entries = 0; 86255ad63bfSTheodore Ts'o neh->eh_max = cpu_to_le16(ext4_ext_space_block(inode, 0)); 863a86c6181SAlex Tomas neh->eh_magic = EXT4_EXT_MAGIC; 864a86c6181SAlex Tomas neh->eh_depth = 0; 865a86c6181SAlex Tomas ex = EXT_FIRST_EXTENT(neh); 866a86c6181SAlex Tomas 867d0d856e8SRandy Dunlap /* move remainder of path[depth] to the new leaf */ 868a86c6181SAlex Tomas BUG_ON(path[depth].p_hdr->eh_entries != path[depth].p_hdr->eh_max); 869a86c6181SAlex Tomas /* start copy from next extent */ 870a86c6181SAlex Tomas /* TODO: we could do it by single memmove */ 871a86c6181SAlex Tomas m = 0; 872a86c6181SAlex Tomas path[depth].p_ext++; 873a86c6181SAlex Tomas while (path[depth].p_ext <= 874a86c6181SAlex Tomas EXT_MAX_EXTENT(path[depth].p_hdr)) { 875553f9008SMingming ext_debug("move %d:%llu:[%d]%d in new leaf %llu\n", 876a86c6181SAlex Tomas le32_to_cpu(path[depth].p_ext->ee_block), 877f65e6fbaSAlex Tomas ext_pblock(path[depth].p_ext), 878553f9008SMingming ext4_ext_is_uninitialized(path[depth].p_ext), 879a2df2a63SAmit Arora ext4_ext_get_actual_len(path[depth].p_ext), 880a86c6181SAlex Tomas newblock); 881a86c6181SAlex Tomas /*memmove(ex++, path[depth].p_ext++, 882a86c6181SAlex Tomas sizeof(struct ext4_extent)); 883a86c6181SAlex Tomas neh->eh_entries++;*/ 884a86c6181SAlex Tomas path[depth].p_ext++; 885a86c6181SAlex Tomas m++; 886a86c6181SAlex Tomas } 887a86c6181SAlex Tomas if (m) { 888a86c6181SAlex Tomas memmove(ex, path[depth].p_ext-m, sizeof(struct ext4_extent)*m); 889e8546d06SMarcin Slusarz le16_add_cpu(&neh->eh_entries, m); 890a86c6181SAlex Tomas } 891a86c6181SAlex Tomas 892a86c6181SAlex Tomas set_buffer_uptodate(bh); 893a86c6181SAlex Tomas unlock_buffer(bh); 894a86c6181SAlex Tomas 8950390131bSFrank Mayhar err = ext4_handle_dirty_metadata(handle, inode, bh); 8967e028976SAvantika Mathur if (err) 897a86c6181SAlex Tomas goto cleanup; 898a86c6181SAlex Tomas brelse(bh); 899a86c6181SAlex Tomas bh = NULL; 900a86c6181SAlex Tomas 901a86c6181SAlex Tomas /* correct old leaf */ 902a86c6181SAlex Tomas if (m) { 9037e028976SAvantika Mathur err = ext4_ext_get_access(handle, inode, path + depth); 9047e028976SAvantika Mathur if (err) 905a86c6181SAlex Tomas goto cleanup; 906e8546d06SMarcin Slusarz le16_add_cpu(&path[depth].p_hdr->eh_entries, -m); 9077e028976SAvantika Mathur err = ext4_ext_dirty(handle, inode, path + depth); 9087e028976SAvantika Mathur if (err) 909a86c6181SAlex Tomas goto cleanup; 910a86c6181SAlex Tomas 911a86c6181SAlex Tomas } 912a86c6181SAlex Tomas 913a86c6181SAlex Tomas /* create intermediate indexes */ 914a86c6181SAlex Tomas k = depth - at - 1; 915a86c6181SAlex Tomas BUG_ON(k < 0); 916a86c6181SAlex Tomas if (k) 917a86c6181SAlex Tomas ext_debug("create %d intermediate indices\n", k); 918a86c6181SAlex Tomas /* insert new index into current index block */ 919a86c6181SAlex Tomas /* current depth stored in i var */ 920a86c6181SAlex Tomas i = depth - 1; 921a86c6181SAlex Tomas while (k--) { 922a86c6181SAlex Tomas oldblock = newblock; 923a86c6181SAlex Tomas newblock = ablocks[--a]; 924bba90743SEric Sandeen bh = sb_getblk(inode->i_sb, newblock); 925a86c6181SAlex Tomas if (!bh) { 926a86c6181SAlex Tomas err = -EIO; 927a86c6181SAlex Tomas goto cleanup; 928a86c6181SAlex Tomas } 929a86c6181SAlex Tomas lock_buffer(bh); 930a86c6181SAlex Tomas 9317e028976SAvantika Mathur err = ext4_journal_get_create_access(handle, bh); 9327e028976SAvantika Mathur if (err) 933a86c6181SAlex Tomas goto cleanup; 934a86c6181SAlex Tomas 935a86c6181SAlex Tomas neh = ext_block_hdr(bh); 936a86c6181SAlex Tomas neh->eh_entries = cpu_to_le16(1); 937a86c6181SAlex Tomas neh->eh_magic = EXT4_EXT_MAGIC; 93855ad63bfSTheodore Ts'o neh->eh_max = cpu_to_le16(ext4_ext_space_block_idx(inode, 0)); 939a86c6181SAlex Tomas neh->eh_depth = cpu_to_le16(depth - i); 940a86c6181SAlex Tomas fidx = EXT_FIRST_INDEX(neh); 941a86c6181SAlex Tomas fidx->ei_block = border; 942f65e6fbaSAlex Tomas ext4_idx_store_pblock(fidx, oldblock); 943a86c6181SAlex Tomas 944bba90743SEric Sandeen ext_debug("int.index at %d (block %llu): %u -> %llu\n", 945bba90743SEric Sandeen i, newblock, le32_to_cpu(border), oldblock); 946a86c6181SAlex Tomas /* copy indexes */ 947a86c6181SAlex Tomas m = 0; 948a86c6181SAlex Tomas path[i].p_idx++; 949a86c6181SAlex Tomas 950a86c6181SAlex Tomas ext_debug("cur 0x%p, last 0x%p\n", path[i].p_idx, 951a86c6181SAlex Tomas EXT_MAX_INDEX(path[i].p_hdr)); 952a86c6181SAlex Tomas BUG_ON(EXT_MAX_INDEX(path[i].p_hdr) != 953a86c6181SAlex Tomas EXT_LAST_INDEX(path[i].p_hdr)); 954a86c6181SAlex Tomas while (path[i].p_idx <= EXT_MAX_INDEX(path[i].p_hdr)) { 95526d535edSDmitry Monakhov ext_debug("%d: move %d:%llu in new index %llu\n", i, 956a86c6181SAlex Tomas le32_to_cpu(path[i].p_idx->ei_block), 957f65e6fbaSAlex Tomas idx_pblock(path[i].p_idx), 958a86c6181SAlex Tomas newblock); 959a86c6181SAlex Tomas /*memmove(++fidx, path[i].p_idx++, 960a86c6181SAlex Tomas sizeof(struct ext4_extent_idx)); 961a86c6181SAlex Tomas neh->eh_entries++; 962a86c6181SAlex Tomas BUG_ON(neh->eh_entries > neh->eh_max);*/ 963a86c6181SAlex Tomas path[i].p_idx++; 964a86c6181SAlex Tomas m++; 965a86c6181SAlex Tomas } 966a86c6181SAlex Tomas if (m) { 967a86c6181SAlex Tomas memmove(++fidx, path[i].p_idx - m, 968a86c6181SAlex Tomas sizeof(struct ext4_extent_idx) * m); 969e8546d06SMarcin Slusarz le16_add_cpu(&neh->eh_entries, m); 970a86c6181SAlex Tomas } 971a86c6181SAlex Tomas set_buffer_uptodate(bh); 972a86c6181SAlex Tomas unlock_buffer(bh); 973a86c6181SAlex Tomas 9740390131bSFrank Mayhar err = ext4_handle_dirty_metadata(handle, inode, bh); 9757e028976SAvantika Mathur if (err) 976a86c6181SAlex Tomas goto cleanup; 977a86c6181SAlex Tomas brelse(bh); 978a86c6181SAlex Tomas bh = NULL; 979a86c6181SAlex Tomas 980a86c6181SAlex Tomas /* correct old index */ 981a86c6181SAlex Tomas if (m) { 982a86c6181SAlex Tomas err = ext4_ext_get_access(handle, inode, path + i); 983a86c6181SAlex Tomas if (err) 984a86c6181SAlex Tomas goto cleanup; 985e8546d06SMarcin Slusarz le16_add_cpu(&path[i].p_hdr->eh_entries, -m); 986a86c6181SAlex Tomas err = ext4_ext_dirty(handle, inode, path + i); 987a86c6181SAlex Tomas if (err) 988a86c6181SAlex Tomas goto cleanup; 989a86c6181SAlex Tomas } 990a86c6181SAlex Tomas 991a86c6181SAlex Tomas i--; 992a86c6181SAlex Tomas } 993a86c6181SAlex Tomas 994a86c6181SAlex Tomas /* insert new index */ 995a86c6181SAlex Tomas err = ext4_ext_insert_index(handle, inode, path + at, 996a86c6181SAlex Tomas le32_to_cpu(border), newblock); 997a86c6181SAlex Tomas 998a86c6181SAlex Tomas cleanup: 999a86c6181SAlex Tomas if (bh) { 1000a86c6181SAlex Tomas if (buffer_locked(bh)) 1001a86c6181SAlex Tomas unlock_buffer(bh); 1002a86c6181SAlex Tomas brelse(bh); 1003a86c6181SAlex Tomas } 1004a86c6181SAlex Tomas 1005a86c6181SAlex Tomas if (err) { 1006a86c6181SAlex Tomas /* free all allocated blocks in error case */ 1007a86c6181SAlex Tomas for (i = 0; i < depth; i++) { 1008a86c6181SAlex Tomas if (!ablocks[i]) 1009a86c6181SAlex Tomas continue; 1010*e6362609STheodore Ts'o ext4_free_blocks(handle, inode, 0, ablocks[i], 1, 1011*e6362609STheodore Ts'o EXT4_FREE_BLOCKS_METADATA); 1012a86c6181SAlex Tomas } 1013a86c6181SAlex Tomas } 1014a86c6181SAlex Tomas kfree(ablocks); 1015a86c6181SAlex Tomas 1016a86c6181SAlex Tomas return err; 1017a86c6181SAlex Tomas } 1018a86c6181SAlex Tomas 1019a86c6181SAlex Tomas /* 1020d0d856e8SRandy Dunlap * ext4_ext_grow_indepth: 1021d0d856e8SRandy Dunlap * implements tree growing procedure: 1022a86c6181SAlex Tomas * - allocates new block 1023a86c6181SAlex Tomas * - moves top-level data (index block or leaf) into the new block 1024d0d856e8SRandy Dunlap * - initializes new top-level, creating index that points to the 1025a86c6181SAlex Tomas * just created block 1026a86c6181SAlex Tomas */ 1027a86c6181SAlex Tomas static int ext4_ext_grow_indepth(handle_t *handle, struct inode *inode, 1028a86c6181SAlex Tomas struct ext4_ext_path *path, 1029a86c6181SAlex Tomas struct ext4_extent *newext) 1030a86c6181SAlex Tomas { 1031a86c6181SAlex Tomas struct ext4_ext_path *curp = path; 1032a86c6181SAlex Tomas struct ext4_extent_header *neh; 1033a86c6181SAlex Tomas struct ext4_extent_idx *fidx; 1034a86c6181SAlex Tomas struct buffer_head *bh; 1035f65e6fbaSAlex Tomas ext4_fsblk_t newblock; 1036a86c6181SAlex Tomas int err = 0; 1037a86c6181SAlex Tomas 1038654b4908SAneesh Kumar K.V newblock = ext4_ext_new_meta_block(handle, inode, path, newext, &err); 1039a86c6181SAlex Tomas if (newblock == 0) 1040a86c6181SAlex Tomas return err; 1041a86c6181SAlex Tomas 1042a86c6181SAlex Tomas bh = sb_getblk(inode->i_sb, newblock); 1043a86c6181SAlex Tomas if (!bh) { 1044a86c6181SAlex Tomas err = -EIO; 1045a86c6181SAlex Tomas ext4_std_error(inode->i_sb, err); 1046a86c6181SAlex Tomas return err; 1047a86c6181SAlex Tomas } 1048a86c6181SAlex Tomas lock_buffer(bh); 1049a86c6181SAlex Tomas 10507e028976SAvantika Mathur err = ext4_journal_get_create_access(handle, bh); 10517e028976SAvantika Mathur if (err) { 1052a86c6181SAlex Tomas unlock_buffer(bh); 1053a86c6181SAlex Tomas goto out; 1054a86c6181SAlex Tomas } 1055a86c6181SAlex Tomas 1056a86c6181SAlex Tomas /* move top-level index/leaf into new block */ 1057a86c6181SAlex Tomas memmove(bh->b_data, curp->p_hdr, sizeof(EXT4_I(inode)->i_data)); 1058a86c6181SAlex Tomas 1059a86c6181SAlex Tomas /* set size of new block */ 1060a86c6181SAlex Tomas neh = ext_block_hdr(bh); 1061a86c6181SAlex Tomas /* old root could have indexes or leaves 1062a86c6181SAlex Tomas * so calculate e_max right way */ 1063a86c6181SAlex Tomas if (ext_depth(inode)) 106455ad63bfSTheodore Ts'o neh->eh_max = cpu_to_le16(ext4_ext_space_block_idx(inode, 0)); 1065a86c6181SAlex Tomas else 106655ad63bfSTheodore Ts'o neh->eh_max = cpu_to_le16(ext4_ext_space_block(inode, 0)); 1067a86c6181SAlex Tomas neh->eh_magic = EXT4_EXT_MAGIC; 1068a86c6181SAlex Tomas set_buffer_uptodate(bh); 1069a86c6181SAlex Tomas unlock_buffer(bh); 1070a86c6181SAlex Tomas 10710390131bSFrank Mayhar err = ext4_handle_dirty_metadata(handle, inode, bh); 10727e028976SAvantika Mathur if (err) 1073a86c6181SAlex Tomas goto out; 1074a86c6181SAlex Tomas 1075a86c6181SAlex Tomas /* create index in new top-level index: num,max,pointer */ 10767e028976SAvantika Mathur err = ext4_ext_get_access(handle, inode, curp); 10777e028976SAvantika Mathur if (err) 1078a86c6181SAlex Tomas goto out; 1079a86c6181SAlex Tomas 1080a86c6181SAlex Tomas curp->p_hdr->eh_magic = EXT4_EXT_MAGIC; 108155ad63bfSTheodore Ts'o curp->p_hdr->eh_max = cpu_to_le16(ext4_ext_space_root_idx(inode, 0)); 1082a86c6181SAlex Tomas curp->p_hdr->eh_entries = cpu_to_le16(1); 1083a86c6181SAlex Tomas curp->p_idx = EXT_FIRST_INDEX(curp->p_hdr); 1084e9f410b1SDmitry Monakhov 1085e9f410b1SDmitry Monakhov if (path[0].p_hdr->eh_depth) 1086e9f410b1SDmitry Monakhov curp->p_idx->ei_block = 1087e9f410b1SDmitry Monakhov EXT_FIRST_INDEX(path[0].p_hdr)->ei_block; 1088e9f410b1SDmitry Monakhov else 1089e9f410b1SDmitry Monakhov curp->p_idx->ei_block = 1090e9f410b1SDmitry Monakhov EXT_FIRST_EXTENT(path[0].p_hdr)->ee_block; 1091f65e6fbaSAlex Tomas ext4_idx_store_pblock(curp->p_idx, newblock); 1092a86c6181SAlex Tomas 1093a86c6181SAlex Tomas neh = ext_inode_hdr(inode); 1094a86c6181SAlex Tomas fidx = EXT_FIRST_INDEX(neh); 10952ae02107SMingming Cao ext_debug("new root: num %d(%d), lblock %d, ptr %llu\n", 1096a86c6181SAlex Tomas le16_to_cpu(neh->eh_entries), le16_to_cpu(neh->eh_max), 1097f65e6fbaSAlex Tomas le32_to_cpu(fidx->ei_block), idx_pblock(fidx)); 1098a86c6181SAlex Tomas 1099a86c6181SAlex Tomas neh->eh_depth = cpu_to_le16(path->p_depth + 1); 1100a86c6181SAlex Tomas err = ext4_ext_dirty(handle, inode, curp); 1101a86c6181SAlex Tomas out: 1102a86c6181SAlex Tomas brelse(bh); 1103a86c6181SAlex Tomas 1104a86c6181SAlex Tomas return err; 1105a86c6181SAlex Tomas } 1106a86c6181SAlex Tomas 1107a86c6181SAlex Tomas /* 1108d0d856e8SRandy Dunlap * ext4_ext_create_new_leaf: 1109d0d856e8SRandy Dunlap * finds empty index and adds new leaf. 1110d0d856e8SRandy Dunlap * if no free index is found, then it requests in-depth growing. 1111a86c6181SAlex Tomas */ 1112a86c6181SAlex Tomas static int ext4_ext_create_new_leaf(handle_t *handle, struct inode *inode, 1113a86c6181SAlex Tomas struct ext4_ext_path *path, 1114a86c6181SAlex Tomas struct ext4_extent *newext) 1115a86c6181SAlex Tomas { 1116a86c6181SAlex Tomas struct ext4_ext_path *curp; 1117a86c6181SAlex Tomas int depth, i, err = 0; 1118a86c6181SAlex Tomas 1119a86c6181SAlex Tomas repeat: 1120a86c6181SAlex Tomas i = depth = ext_depth(inode); 1121a86c6181SAlex Tomas 1122a86c6181SAlex Tomas /* walk up to the tree and look for free index entry */ 1123a86c6181SAlex Tomas curp = path + depth; 1124a86c6181SAlex Tomas while (i > 0 && !EXT_HAS_FREE_INDEX(curp)) { 1125a86c6181SAlex Tomas i--; 1126a86c6181SAlex Tomas curp--; 1127a86c6181SAlex Tomas } 1128a86c6181SAlex Tomas 1129d0d856e8SRandy Dunlap /* we use already allocated block for index block, 1130d0d856e8SRandy Dunlap * so subsequent data blocks should be contiguous */ 1131a86c6181SAlex Tomas if (EXT_HAS_FREE_INDEX(curp)) { 1132a86c6181SAlex Tomas /* if we found index with free entry, then use that 1133a86c6181SAlex Tomas * entry: create all needed subtree and add new leaf */ 1134a86c6181SAlex Tomas err = ext4_ext_split(handle, inode, path, newext, i); 1135787e0981SShen Feng if (err) 1136787e0981SShen Feng goto out; 1137a86c6181SAlex Tomas 1138a86c6181SAlex Tomas /* refill path */ 1139a86c6181SAlex Tomas ext4_ext_drop_refs(path); 1140a86c6181SAlex Tomas path = ext4_ext_find_extent(inode, 1141725d26d3SAneesh Kumar K.V (ext4_lblk_t)le32_to_cpu(newext->ee_block), 1142a86c6181SAlex Tomas path); 1143a86c6181SAlex Tomas if (IS_ERR(path)) 1144a86c6181SAlex Tomas err = PTR_ERR(path); 1145a86c6181SAlex Tomas } else { 1146a86c6181SAlex Tomas /* tree is full, time to grow in depth */ 1147a86c6181SAlex Tomas err = ext4_ext_grow_indepth(handle, inode, path, newext); 1148a86c6181SAlex Tomas if (err) 1149a86c6181SAlex Tomas goto out; 1150a86c6181SAlex Tomas 1151a86c6181SAlex Tomas /* refill path */ 1152a86c6181SAlex Tomas ext4_ext_drop_refs(path); 1153a86c6181SAlex Tomas path = ext4_ext_find_extent(inode, 1154725d26d3SAneesh Kumar K.V (ext4_lblk_t)le32_to_cpu(newext->ee_block), 1155a86c6181SAlex Tomas path); 1156a86c6181SAlex Tomas if (IS_ERR(path)) { 1157a86c6181SAlex Tomas err = PTR_ERR(path); 1158a86c6181SAlex Tomas goto out; 1159a86c6181SAlex Tomas } 1160a86c6181SAlex Tomas 1161a86c6181SAlex Tomas /* 1162d0d856e8SRandy Dunlap * only first (depth 0 -> 1) produces free space; 1163d0d856e8SRandy Dunlap * in all other cases we have to split the grown tree 1164a86c6181SAlex Tomas */ 1165a86c6181SAlex Tomas depth = ext_depth(inode); 1166a86c6181SAlex Tomas if (path[depth].p_hdr->eh_entries == path[depth].p_hdr->eh_max) { 1167d0d856e8SRandy Dunlap /* now we need to split */ 1168a86c6181SAlex Tomas goto repeat; 1169a86c6181SAlex Tomas } 1170a86c6181SAlex Tomas } 1171a86c6181SAlex Tomas 1172a86c6181SAlex Tomas out: 1173a86c6181SAlex Tomas return err; 1174a86c6181SAlex Tomas } 1175a86c6181SAlex Tomas 1176a86c6181SAlex Tomas /* 11771988b51eSAlex Tomas * search the closest allocated block to the left for *logical 11781988b51eSAlex Tomas * and returns it at @logical + it's physical address at @phys 11791988b51eSAlex Tomas * if *logical is the smallest allocated block, the function 11801988b51eSAlex Tomas * returns 0 at @phys 11811988b51eSAlex Tomas * return value contains 0 (success) or error code 11821988b51eSAlex Tomas */ 11831988b51eSAlex Tomas int 11841988b51eSAlex Tomas ext4_ext_search_left(struct inode *inode, struct ext4_ext_path *path, 11851988b51eSAlex Tomas ext4_lblk_t *logical, ext4_fsblk_t *phys) 11861988b51eSAlex Tomas { 11871988b51eSAlex Tomas struct ext4_extent_idx *ix; 11881988b51eSAlex Tomas struct ext4_extent *ex; 1189b939e376SAneesh Kumar K.V int depth, ee_len; 11901988b51eSAlex Tomas 11911988b51eSAlex Tomas BUG_ON(path == NULL); 11921988b51eSAlex Tomas depth = path->p_depth; 11931988b51eSAlex Tomas *phys = 0; 11941988b51eSAlex Tomas 11951988b51eSAlex Tomas if (depth == 0 && path->p_ext == NULL) 11961988b51eSAlex Tomas return 0; 11971988b51eSAlex Tomas 11981988b51eSAlex Tomas /* usually extent in the path covers blocks smaller 11991988b51eSAlex Tomas * then *logical, but it can be that extent is the 12001988b51eSAlex Tomas * first one in the file */ 12011988b51eSAlex Tomas 12021988b51eSAlex Tomas ex = path[depth].p_ext; 1203b939e376SAneesh Kumar K.V ee_len = ext4_ext_get_actual_len(ex); 12041988b51eSAlex Tomas if (*logical < le32_to_cpu(ex->ee_block)) { 12051988b51eSAlex Tomas BUG_ON(EXT_FIRST_EXTENT(path[depth].p_hdr) != ex); 12061988b51eSAlex Tomas while (--depth >= 0) { 12071988b51eSAlex Tomas ix = path[depth].p_idx; 12081988b51eSAlex Tomas BUG_ON(ix != EXT_FIRST_INDEX(path[depth].p_hdr)); 12091988b51eSAlex Tomas } 12101988b51eSAlex Tomas return 0; 12111988b51eSAlex Tomas } 12121988b51eSAlex Tomas 1213b939e376SAneesh Kumar K.V BUG_ON(*logical < (le32_to_cpu(ex->ee_block) + ee_len)); 12141988b51eSAlex Tomas 1215b939e376SAneesh Kumar K.V *logical = le32_to_cpu(ex->ee_block) + ee_len - 1; 1216b939e376SAneesh Kumar K.V *phys = ext_pblock(ex) + ee_len - 1; 12171988b51eSAlex Tomas return 0; 12181988b51eSAlex Tomas } 12191988b51eSAlex Tomas 12201988b51eSAlex Tomas /* 12211988b51eSAlex Tomas * search the closest allocated block to the right for *logical 12221988b51eSAlex Tomas * and returns it at @logical + it's physical address at @phys 12231988b51eSAlex Tomas * if *logical is the smallest allocated block, the function 12241988b51eSAlex Tomas * returns 0 at @phys 12251988b51eSAlex Tomas * return value contains 0 (success) or error code 12261988b51eSAlex Tomas */ 12271988b51eSAlex Tomas int 12281988b51eSAlex Tomas ext4_ext_search_right(struct inode *inode, struct ext4_ext_path *path, 12291988b51eSAlex Tomas ext4_lblk_t *logical, ext4_fsblk_t *phys) 12301988b51eSAlex Tomas { 12311988b51eSAlex Tomas struct buffer_head *bh = NULL; 12321988b51eSAlex Tomas struct ext4_extent_header *eh; 12331988b51eSAlex Tomas struct ext4_extent_idx *ix; 12341988b51eSAlex Tomas struct ext4_extent *ex; 12351988b51eSAlex Tomas ext4_fsblk_t block; 1236395a87bfSEric Sandeen int depth; /* Note, NOT eh_depth; depth from top of tree */ 1237395a87bfSEric Sandeen int ee_len; 12381988b51eSAlex Tomas 12391988b51eSAlex Tomas BUG_ON(path == NULL); 12401988b51eSAlex Tomas depth = path->p_depth; 12411988b51eSAlex Tomas *phys = 0; 12421988b51eSAlex Tomas 12431988b51eSAlex Tomas if (depth == 0 && path->p_ext == NULL) 12441988b51eSAlex Tomas return 0; 12451988b51eSAlex Tomas 12461988b51eSAlex Tomas /* usually extent in the path covers blocks smaller 12471988b51eSAlex Tomas * then *logical, but it can be that extent is the 12481988b51eSAlex Tomas * first one in the file */ 12491988b51eSAlex Tomas 12501988b51eSAlex Tomas ex = path[depth].p_ext; 1251b939e376SAneesh Kumar K.V ee_len = ext4_ext_get_actual_len(ex); 12521988b51eSAlex Tomas if (*logical < le32_to_cpu(ex->ee_block)) { 12531988b51eSAlex Tomas BUG_ON(EXT_FIRST_EXTENT(path[depth].p_hdr) != ex); 12541988b51eSAlex Tomas while (--depth >= 0) { 12551988b51eSAlex Tomas ix = path[depth].p_idx; 12561988b51eSAlex Tomas BUG_ON(ix != EXT_FIRST_INDEX(path[depth].p_hdr)); 12571988b51eSAlex Tomas } 12581988b51eSAlex Tomas *logical = le32_to_cpu(ex->ee_block); 12591988b51eSAlex Tomas *phys = ext_pblock(ex); 12601988b51eSAlex Tomas return 0; 12611988b51eSAlex Tomas } 12621988b51eSAlex Tomas 1263b939e376SAneesh Kumar K.V BUG_ON(*logical < (le32_to_cpu(ex->ee_block) + ee_len)); 12641988b51eSAlex Tomas 12651988b51eSAlex Tomas if (ex != EXT_LAST_EXTENT(path[depth].p_hdr)) { 12661988b51eSAlex Tomas /* next allocated block in this leaf */ 12671988b51eSAlex Tomas ex++; 12681988b51eSAlex Tomas *logical = le32_to_cpu(ex->ee_block); 12691988b51eSAlex Tomas *phys = ext_pblock(ex); 12701988b51eSAlex Tomas return 0; 12711988b51eSAlex Tomas } 12721988b51eSAlex Tomas 12731988b51eSAlex Tomas /* go up and search for index to the right */ 12741988b51eSAlex Tomas while (--depth >= 0) { 12751988b51eSAlex Tomas ix = path[depth].p_idx; 12761988b51eSAlex Tomas if (ix != EXT_LAST_INDEX(path[depth].p_hdr)) 127725f1ee3aSWu Fengguang goto got_index; 12781988b51eSAlex Tomas } 12791988b51eSAlex Tomas 128025f1ee3aSWu Fengguang /* we've gone up to the root and found no index to the right */ 12811988b51eSAlex Tomas return 0; 12821988b51eSAlex Tomas 128325f1ee3aSWu Fengguang got_index: 12841988b51eSAlex Tomas /* we've found index to the right, let's 12851988b51eSAlex Tomas * follow it and find the closest allocated 12861988b51eSAlex Tomas * block to the right */ 12871988b51eSAlex Tomas ix++; 12881988b51eSAlex Tomas block = idx_pblock(ix); 12891988b51eSAlex Tomas while (++depth < path->p_depth) { 12901988b51eSAlex Tomas bh = sb_bread(inode->i_sb, block); 12911988b51eSAlex Tomas if (bh == NULL) 12921988b51eSAlex Tomas return -EIO; 12931988b51eSAlex Tomas eh = ext_block_hdr(bh); 1294395a87bfSEric Sandeen /* subtract from p_depth to get proper eh_depth */ 129556b19868SAneesh Kumar K.V if (ext4_ext_check(inode, eh, path->p_depth - depth)) { 12961988b51eSAlex Tomas put_bh(bh); 12971988b51eSAlex Tomas return -EIO; 12981988b51eSAlex Tomas } 12991988b51eSAlex Tomas ix = EXT_FIRST_INDEX(eh); 13001988b51eSAlex Tomas block = idx_pblock(ix); 13011988b51eSAlex Tomas put_bh(bh); 13021988b51eSAlex Tomas } 13031988b51eSAlex Tomas 13041988b51eSAlex Tomas bh = sb_bread(inode->i_sb, block); 13051988b51eSAlex Tomas if (bh == NULL) 13061988b51eSAlex Tomas return -EIO; 13071988b51eSAlex Tomas eh = ext_block_hdr(bh); 130856b19868SAneesh Kumar K.V if (ext4_ext_check(inode, eh, path->p_depth - depth)) { 13091988b51eSAlex Tomas put_bh(bh); 13101988b51eSAlex Tomas return -EIO; 13111988b51eSAlex Tomas } 13121988b51eSAlex Tomas ex = EXT_FIRST_EXTENT(eh); 13131988b51eSAlex Tomas *logical = le32_to_cpu(ex->ee_block); 13141988b51eSAlex Tomas *phys = ext_pblock(ex); 13151988b51eSAlex Tomas put_bh(bh); 13161988b51eSAlex Tomas return 0; 13171988b51eSAlex Tomas } 13181988b51eSAlex Tomas 13191988b51eSAlex Tomas /* 1320d0d856e8SRandy Dunlap * ext4_ext_next_allocated_block: 1321d0d856e8SRandy Dunlap * returns allocated block in subsequent extent or EXT_MAX_BLOCK. 1322d0d856e8SRandy Dunlap * NOTE: it considers block number from index entry as 1323d0d856e8SRandy Dunlap * allocated block. Thus, index entries have to be consistent 1324d0d856e8SRandy Dunlap * with leaves. 1325a86c6181SAlex Tomas */ 1326725d26d3SAneesh Kumar K.V static ext4_lblk_t 1327a86c6181SAlex Tomas ext4_ext_next_allocated_block(struct ext4_ext_path *path) 1328a86c6181SAlex Tomas { 1329a86c6181SAlex Tomas int depth; 1330a86c6181SAlex Tomas 1331a86c6181SAlex Tomas BUG_ON(path == NULL); 1332a86c6181SAlex Tomas depth = path->p_depth; 1333a86c6181SAlex Tomas 1334a86c6181SAlex Tomas if (depth == 0 && path->p_ext == NULL) 1335a86c6181SAlex Tomas return EXT_MAX_BLOCK; 1336a86c6181SAlex Tomas 1337a86c6181SAlex Tomas while (depth >= 0) { 1338a86c6181SAlex Tomas if (depth == path->p_depth) { 1339a86c6181SAlex Tomas /* leaf */ 1340a86c6181SAlex Tomas if (path[depth].p_ext != 1341a86c6181SAlex Tomas EXT_LAST_EXTENT(path[depth].p_hdr)) 1342a86c6181SAlex Tomas return le32_to_cpu(path[depth].p_ext[1].ee_block); 1343a86c6181SAlex Tomas } else { 1344a86c6181SAlex Tomas /* index */ 1345a86c6181SAlex Tomas if (path[depth].p_idx != 1346a86c6181SAlex Tomas EXT_LAST_INDEX(path[depth].p_hdr)) 1347a86c6181SAlex Tomas return le32_to_cpu(path[depth].p_idx[1].ei_block); 1348a86c6181SAlex Tomas } 1349a86c6181SAlex Tomas depth--; 1350a86c6181SAlex Tomas } 1351a86c6181SAlex Tomas 1352a86c6181SAlex Tomas return EXT_MAX_BLOCK; 1353a86c6181SAlex Tomas } 1354a86c6181SAlex Tomas 1355a86c6181SAlex Tomas /* 1356d0d856e8SRandy Dunlap * ext4_ext_next_leaf_block: 1357a86c6181SAlex Tomas * returns first allocated block from next leaf or EXT_MAX_BLOCK 1358a86c6181SAlex Tomas */ 1359725d26d3SAneesh Kumar K.V static ext4_lblk_t ext4_ext_next_leaf_block(struct inode *inode, 1360a86c6181SAlex Tomas struct ext4_ext_path *path) 1361a86c6181SAlex Tomas { 1362a86c6181SAlex Tomas int depth; 1363a86c6181SAlex Tomas 1364a86c6181SAlex Tomas BUG_ON(path == NULL); 1365a86c6181SAlex Tomas depth = path->p_depth; 1366a86c6181SAlex Tomas 1367a86c6181SAlex Tomas /* zero-tree has no leaf blocks at all */ 1368a86c6181SAlex Tomas if (depth == 0) 1369a86c6181SAlex Tomas return EXT_MAX_BLOCK; 1370a86c6181SAlex Tomas 1371a86c6181SAlex Tomas /* go to index block */ 1372a86c6181SAlex Tomas depth--; 1373a86c6181SAlex Tomas 1374a86c6181SAlex Tomas while (depth >= 0) { 1375a86c6181SAlex Tomas if (path[depth].p_idx != 1376a86c6181SAlex Tomas EXT_LAST_INDEX(path[depth].p_hdr)) 1377725d26d3SAneesh Kumar K.V return (ext4_lblk_t) 1378725d26d3SAneesh Kumar K.V le32_to_cpu(path[depth].p_idx[1].ei_block); 1379a86c6181SAlex Tomas depth--; 1380a86c6181SAlex Tomas } 1381a86c6181SAlex Tomas 1382a86c6181SAlex Tomas return EXT_MAX_BLOCK; 1383a86c6181SAlex Tomas } 1384a86c6181SAlex Tomas 1385a86c6181SAlex Tomas /* 1386d0d856e8SRandy Dunlap * ext4_ext_correct_indexes: 1387d0d856e8SRandy Dunlap * if leaf gets modified and modified extent is first in the leaf, 1388d0d856e8SRandy Dunlap * then we have to correct all indexes above. 1389a86c6181SAlex Tomas * TODO: do we need to correct tree in all cases? 1390a86c6181SAlex Tomas */ 13911d03ec98SAneesh Kumar K.V static int ext4_ext_correct_indexes(handle_t *handle, struct inode *inode, 1392a86c6181SAlex Tomas struct ext4_ext_path *path) 1393a86c6181SAlex Tomas { 1394a86c6181SAlex Tomas struct ext4_extent_header *eh; 1395a86c6181SAlex Tomas int depth = ext_depth(inode); 1396a86c6181SAlex Tomas struct ext4_extent *ex; 1397a86c6181SAlex Tomas __le32 border; 1398a86c6181SAlex Tomas int k, err = 0; 1399a86c6181SAlex Tomas 1400a86c6181SAlex Tomas eh = path[depth].p_hdr; 1401a86c6181SAlex Tomas ex = path[depth].p_ext; 1402a86c6181SAlex Tomas BUG_ON(ex == NULL); 1403a86c6181SAlex Tomas BUG_ON(eh == NULL); 1404a86c6181SAlex Tomas 1405a86c6181SAlex Tomas if (depth == 0) { 1406a86c6181SAlex Tomas /* there is no tree at all */ 1407a86c6181SAlex Tomas return 0; 1408a86c6181SAlex Tomas } 1409a86c6181SAlex Tomas 1410a86c6181SAlex Tomas if (ex != EXT_FIRST_EXTENT(eh)) { 1411a86c6181SAlex Tomas /* we correct tree if first leaf got modified only */ 1412a86c6181SAlex Tomas return 0; 1413a86c6181SAlex Tomas } 1414a86c6181SAlex Tomas 1415a86c6181SAlex Tomas /* 1416d0d856e8SRandy Dunlap * TODO: we need correction if border is smaller than current one 1417a86c6181SAlex Tomas */ 1418a86c6181SAlex Tomas k = depth - 1; 1419a86c6181SAlex Tomas border = path[depth].p_ext->ee_block; 14207e028976SAvantika Mathur err = ext4_ext_get_access(handle, inode, path + k); 14217e028976SAvantika Mathur if (err) 1422a86c6181SAlex Tomas return err; 1423a86c6181SAlex Tomas path[k].p_idx->ei_block = border; 14247e028976SAvantika Mathur err = ext4_ext_dirty(handle, inode, path + k); 14257e028976SAvantika Mathur if (err) 1426a86c6181SAlex Tomas return err; 1427a86c6181SAlex Tomas 1428a86c6181SAlex Tomas while (k--) { 1429a86c6181SAlex Tomas /* change all left-side indexes */ 1430a86c6181SAlex Tomas if (path[k+1].p_idx != EXT_FIRST_INDEX(path[k+1].p_hdr)) 1431a86c6181SAlex Tomas break; 14327e028976SAvantika Mathur err = ext4_ext_get_access(handle, inode, path + k); 14337e028976SAvantika Mathur if (err) 1434a86c6181SAlex Tomas break; 1435a86c6181SAlex Tomas path[k].p_idx->ei_block = border; 14367e028976SAvantika Mathur err = ext4_ext_dirty(handle, inode, path + k); 14377e028976SAvantika Mathur if (err) 1438a86c6181SAlex Tomas break; 1439a86c6181SAlex Tomas } 1440a86c6181SAlex Tomas 1441a86c6181SAlex Tomas return err; 1442a86c6181SAlex Tomas } 1443a86c6181SAlex Tomas 1444748de673SAkira Fujita int 1445a86c6181SAlex Tomas ext4_can_extents_be_merged(struct inode *inode, struct ext4_extent *ex1, 1446a86c6181SAlex Tomas struct ext4_extent *ex2) 1447a86c6181SAlex Tomas { 1448749269faSAmit Arora unsigned short ext1_ee_len, ext2_ee_len, max_len; 1449a2df2a63SAmit Arora 1450a2df2a63SAmit Arora /* 1451a2df2a63SAmit Arora * Make sure that either both extents are uninitialized, or 1452a2df2a63SAmit Arora * both are _not_. 1453a2df2a63SAmit Arora */ 1454a2df2a63SAmit Arora if (ext4_ext_is_uninitialized(ex1) ^ ext4_ext_is_uninitialized(ex2)) 1455a2df2a63SAmit Arora return 0; 1456a2df2a63SAmit Arora 1457749269faSAmit Arora if (ext4_ext_is_uninitialized(ex1)) 1458749269faSAmit Arora max_len = EXT_UNINIT_MAX_LEN; 1459749269faSAmit Arora else 1460749269faSAmit Arora max_len = EXT_INIT_MAX_LEN; 1461749269faSAmit Arora 1462a2df2a63SAmit Arora ext1_ee_len = ext4_ext_get_actual_len(ex1); 1463a2df2a63SAmit Arora ext2_ee_len = ext4_ext_get_actual_len(ex2); 1464a2df2a63SAmit Arora 1465a2df2a63SAmit Arora if (le32_to_cpu(ex1->ee_block) + ext1_ee_len != 146663f57933SAndrew Morton le32_to_cpu(ex2->ee_block)) 1467a86c6181SAlex Tomas return 0; 1468a86c6181SAlex Tomas 1469471d4011SSuparna Bhattacharya /* 1470471d4011SSuparna Bhattacharya * To allow future support for preallocated extents to be added 1471471d4011SSuparna Bhattacharya * as an RO_COMPAT feature, refuse to merge to extents if 1472d0d856e8SRandy Dunlap * this can result in the top bit of ee_len being set. 1473471d4011SSuparna Bhattacharya */ 1474749269faSAmit Arora if (ext1_ee_len + ext2_ee_len > max_len) 1475471d4011SSuparna Bhattacharya return 0; 1476bbf2f9fbSRobert P. J. Day #ifdef AGGRESSIVE_TEST 1477b939e376SAneesh Kumar K.V if (ext1_ee_len >= 4) 1478a86c6181SAlex Tomas return 0; 1479a86c6181SAlex Tomas #endif 1480a86c6181SAlex Tomas 1481a2df2a63SAmit Arora if (ext_pblock(ex1) + ext1_ee_len == ext_pblock(ex2)) 1482a86c6181SAlex Tomas return 1; 1483a86c6181SAlex Tomas return 0; 1484a86c6181SAlex Tomas } 1485a86c6181SAlex Tomas 1486a86c6181SAlex Tomas /* 148756055d3aSAmit Arora * This function tries to merge the "ex" extent to the next extent in the tree. 148856055d3aSAmit Arora * It always tries to merge towards right. If you want to merge towards 148956055d3aSAmit Arora * left, pass "ex - 1" as argument instead of "ex". 149056055d3aSAmit Arora * Returns 0 if the extents (ex and ex+1) were _not_ merged and returns 149156055d3aSAmit Arora * 1 if they got merged. 149256055d3aSAmit Arora */ 149356055d3aSAmit Arora int ext4_ext_try_to_merge(struct inode *inode, 149456055d3aSAmit Arora struct ext4_ext_path *path, 149556055d3aSAmit Arora struct ext4_extent *ex) 149656055d3aSAmit Arora { 149756055d3aSAmit Arora struct ext4_extent_header *eh; 149856055d3aSAmit Arora unsigned int depth, len; 149956055d3aSAmit Arora int merge_done = 0; 150056055d3aSAmit Arora int uninitialized = 0; 150156055d3aSAmit Arora 150256055d3aSAmit Arora depth = ext_depth(inode); 150356055d3aSAmit Arora BUG_ON(path[depth].p_hdr == NULL); 150456055d3aSAmit Arora eh = path[depth].p_hdr; 150556055d3aSAmit Arora 150656055d3aSAmit Arora while (ex < EXT_LAST_EXTENT(eh)) { 150756055d3aSAmit Arora if (!ext4_can_extents_be_merged(inode, ex, ex + 1)) 150856055d3aSAmit Arora break; 150956055d3aSAmit Arora /* merge with next extent! */ 151056055d3aSAmit Arora if (ext4_ext_is_uninitialized(ex)) 151156055d3aSAmit Arora uninitialized = 1; 151256055d3aSAmit Arora ex->ee_len = cpu_to_le16(ext4_ext_get_actual_len(ex) 151356055d3aSAmit Arora + ext4_ext_get_actual_len(ex + 1)); 151456055d3aSAmit Arora if (uninitialized) 151556055d3aSAmit Arora ext4_ext_mark_uninitialized(ex); 151656055d3aSAmit Arora 151756055d3aSAmit Arora if (ex + 1 < EXT_LAST_EXTENT(eh)) { 151856055d3aSAmit Arora len = (EXT_LAST_EXTENT(eh) - ex - 1) 151956055d3aSAmit Arora * sizeof(struct ext4_extent); 152056055d3aSAmit Arora memmove(ex + 1, ex + 2, len); 152156055d3aSAmit Arora } 1522e8546d06SMarcin Slusarz le16_add_cpu(&eh->eh_entries, -1); 152356055d3aSAmit Arora merge_done = 1; 152456055d3aSAmit Arora WARN_ON(eh->eh_entries == 0); 152556055d3aSAmit Arora if (!eh->eh_entries) 152656055d3aSAmit Arora ext4_error(inode->i_sb, "ext4_ext_try_to_merge", 152756055d3aSAmit Arora "inode#%lu, eh->eh_entries = 0!", inode->i_ino); 152856055d3aSAmit Arora } 152956055d3aSAmit Arora 153056055d3aSAmit Arora return merge_done; 153156055d3aSAmit Arora } 153256055d3aSAmit Arora 153356055d3aSAmit Arora /* 153425d14f98SAmit Arora * check if a portion of the "newext" extent overlaps with an 153525d14f98SAmit Arora * existing extent. 153625d14f98SAmit Arora * 153725d14f98SAmit Arora * If there is an overlap discovered, it updates the length of the newext 153825d14f98SAmit Arora * such that there will be no overlap, and then returns 1. 153925d14f98SAmit Arora * If there is no overlap found, it returns 0. 154025d14f98SAmit Arora */ 154125d14f98SAmit Arora unsigned int ext4_ext_check_overlap(struct inode *inode, 154225d14f98SAmit Arora struct ext4_extent *newext, 154325d14f98SAmit Arora struct ext4_ext_path *path) 154425d14f98SAmit Arora { 1545725d26d3SAneesh Kumar K.V ext4_lblk_t b1, b2; 154625d14f98SAmit Arora unsigned int depth, len1; 154725d14f98SAmit Arora unsigned int ret = 0; 154825d14f98SAmit Arora 154925d14f98SAmit Arora b1 = le32_to_cpu(newext->ee_block); 1550a2df2a63SAmit Arora len1 = ext4_ext_get_actual_len(newext); 155125d14f98SAmit Arora depth = ext_depth(inode); 155225d14f98SAmit Arora if (!path[depth].p_ext) 155325d14f98SAmit Arora goto out; 155425d14f98SAmit Arora b2 = le32_to_cpu(path[depth].p_ext->ee_block); 155525d14f98SAmit Arora 155625d14f98SAmit Arora /* 155725d14f98SAmit Arora * get the next allocated block if the extent in the path 155825d14f98SAmit Arora * is before the requested block(s) 155925d14f98SAmit Arora */ 156025d14f98SAmit Arora if (b2 < b1) { 156125d14f98SAmit Arora b2 = ext4_ext_next_allocated_block(path); 156225d14f98SAmit Arora if (b2 == EXT_MAX_BLOCK) 156325d14f98SAmit Arora goto out; 156425d14f98SAmit Arora } 156525d14f98SAmit Arora 1566725d26d3SAneesh Kumar K.V /* check for wrap through zero on extent logical start block*/ 156725d14f98SAmit Arora if (b1 + len1 < b1) { 156825d14f98SAmit Arora len1 = EXT_MAX_BLOCK - b1; 156925d14f98SAmit Arora newext->ee_len = cpu_to_le16(len1); 157025d14f98SAmit Arora ret = 1; 157125d14f98SAmit Arora } 157225d14f98SAmit Arora 157325d14f98SAmit Arora /* check for overlap */ 157425d14f98SAmit Arora if (b1 + len1 > b2) { 157525d14f98SAmit Arora newext->ee_len = cpu_to_le16(b2 - b1); 157625d14f98SAmit Arora ret = 1; 157725d14f98SAmit Arora } 157825d14f98SAmit Arora out: 157925d14f98SAmit Arora return ret; 158025d14f98SAmit Arora } 158125d14f98SAmit Arora 158225d14f98SAmit Arora /* 1583d0d856e8SRandy Dunlap * ext4_ext_insert_extent: 1584d0d856e8SRandy Dunlap * tries to merge requsted extent into the existing extent or 1585d0d856e8SRandy Dunlap * inserts requested extent as new one into the tree, 1586d0d856e8SRandy Dunlap * creating new leaf in the no-space case. 1587a86c6181SAlex Tomas */ 1588a86c6181SAlex Tomas int ext4_ext_insert_extent(handle_t *handle, struct inode *inode, 1589a86c6181SAlex Tomas struct ext4_ext_path *path, 15900031462bSMingming Cao struct ext4_extent *newext, int flag) 1591a86c6181SAlex Tomas { 1592a86c6181SAlex Tomas struct ext4_extent_header *eh; 1593a86c6181SAlex Tomas struct ext4_extent *ex, *fex; 1594a86c6181SAlex Tomas struct ext4_extent *nearex; /* nearest extent */ 1595a86c6181SAlex Tomas struct ext4_ext_path *npath = NULL; 1596725d26d3SAneesh Kumar K.V int depth, len, err; 1597725d26d3SAneesh Kumar K.V ext4_lblk_t next; 1598a2df2a63SAmit Arora unsigned uninitialized = 0; 1599a86c6181SAlex Tomas 1600a2df2a63SAmit Arora BUG_ON(ext4_ext_get_actual_len(newext) == 0); 1601a86c6181SAlex Tomas depth = ext_depth(inode); 1602a86c6181SAlex Tomas ex = path[depth].p_ext; 1603a86c6181SAlex Tomas BUG_ON(path[depth].p_hdr == NULL); 1604a86c6181SAlex Tomas 1605a86c6181SAlex Tomas /* try to insert block into found extent and return */ 16060031462bSMingming Cao if (ex && (flag != EXT4_GET_BLOCKS_DIO_CREATE_EXT) 16070031462bSMingming Cao && ext4_can_extents_be_merged(inode, ex, newext)) { 1608553f9008SMingming ext_debug("append [%d]%d block to %d:[%d]%d (from %llu)\n", 1609553f9008SMingming ext4_ext_is_uninitialized(newext), 1610a2df2a63SAmit Arora ext4_ext_get_actual_len(newext), 1611a86c6181SAlex Tomas le32_to_cpu(ex->ee_block), 1612553f9008SMingming ext4_ext_is_uninitialized(ex), 1613a2df2a63SAmit Arora ext4_ext_get_actual_len(ex), ext_pblock(ex)); 16147e028976SAvantika Mathur err = ext4_ext_get_access(handle, inode, path + depth); 16157e028976SAvantika Mathur if (err) 1616a86c6181SAlex Tomas return err; 1617a2df2a63SAmit Arora 1618a2df2a63SAmit Arora /* 1619a2df2a63SAmit Arora * ext4_can_extents_be_merged should have checked that either 1620a2df2a63SAmit Arora * both extents are uninitialized, or both aren't. Thus we 1621a2df2a63SAmit Arora * need to check only one of them here. 1622a2df2a63SAmit Arora */ 1623a2df2a63SAmit Arora if (ext4_ext_is_uninitialized(ex)) 1624a2df2a63SAmit Arora uninitialized = 1; 1625a2df2a63SAmit Arora ex->ee_len = cpu_to_le16(ext4_ext_get_actual_len(ex) 1626a2df2a63SAmit Arora + ext4_ext_get_actual_len(newext)); 1627a2df2a63SAmit Arora if (uninitialized) 1628a2df2a63SAmit Arora ext4_ext_mark_uninitialized(ex); 1629a86c6181SAlex Tomas eh = path[depth].p_hdr; 1630a86c6181SAlex Tomas nearex = ex; 1631a86c6181SAlex Tomas goto merge; 1632a86c6181SAlex Tomas } 1633a86c6181SAlex Tomas 1634a86c6181SAlex Tomas repeat: 1635a86c6181SAlex Tomas depth = ext_depth(inode); 1636a86c6181SAlex Tomas eh = path[depth].p_hdr; 1637a86c6181SAlex Tomas if (le16_to_cpu(eh->eh_entries) < le16_to_cpu(eh->eh_max)) 1638a86c6181SAlex Tomas goto has_space; 1639a86c6181SAlex Tomas 1640a86c6181SAlex Tomas /* probably next leaf has space for us? */ 1641a86c6181SAlex Tomas fex = EXT_LAST_EXTENT(eh); 1642a86c6181SAlex Tomas next = ext4_ext_next_leaf_block(inode, path); 1643a86c6181SAlex Tomas if (le32_to_cpu(newext->ee_block) > le32_to_cpu(fex->ee_block) 1644a86c6181SAlex Tomas && next != EXT_MAX_BLOCK) { 1645a86c6181SAlex Tomas ext_debug("next leaf block - %d\n", next); 1646a86c6181SAlex Tomas BUG_ON(npath != NULL); 1647a86c6181SAlex Tomas npath = ext4_ext_find_extent(inode, next, NULL); 1648a86c6181SAlex Tomas if (IS_ERR(npath)) 1649a86c6181SAlex Tomas return PTR_ERR(npath); 1650a86c6181SAlex Tomas BUG_ON(npath->p_depth != path->p_depth); 1651a86c6181SAlex Tomas eh = npath[depth].p_hdr; 1652a86c6181SAlex Tomas if (le16_to_cpu(eh->eh_entries) < le16_to_cpu(eh->eh_max)) { 1653a86c6181SAlex Tomas ext_debug("next leaf isnt full(%d)\n", 1654a86c6181SAlex Tomas le16_to_cpu(eh->eh_entries)); 1655a86c6181SAlex Tomas path = npath; 1656a86c6181SAlex Tomas goto repeat; 1657a86c6181SAlex Tomas } 1658a86c6181SAlex Tomas ext_debug("next leaf has no free space(%d,%d)\n", 1659a86c6181SAlex Tomas le16_to_cpu(eh->eh_entries), le16_to_cpu(eh->eh_max)); 1660a86c6181SAlex Tomas } 1661a86c6181SAlex Tomas 1662a86c6181SAlex Tomas /* 1663d0d856e8SRandy Dunlap * There is no free space in the found leaf. 1664d0d856e8SRandy Dunlap * We're gonna add a new leaf in the tree. 1665a86c6181SAlex Tomas */ 1666a86c6181SAlex Tomas err = ext4_ext_create_new_leaf(handle, inode, path, newext); 1667a86c6181SAlex Tomas if (err) 1668a86c6181SAlex Tomas goto cleanup; 1669a86c6181SAlex Tomas depth = ext_depth(inode); 1670a86c6181SAlex Tomas eh = path[depth].p_hdr; 1671a86c6181SAlex Tomas 1672a86c6181SAlex Tomas has_space: 1673a86c6181SAlex Tomas nearex = path[depth].p_ext; 1674a86c6181SAlex Tomas 16757e028976SAvantika Mathur err = ext4_ext_get_access(handle, inode, path + depth); 16767e028976SAvantika Mathur if (err) 1677a86c6181SAlex Tomas goto cleanup; 1678a86c6181SAlex Tomas 1679a86c6181SAlex Tomas if (!nearex) { 1680a86c6181SAlex Tomas /* there is no extent in this leaf, create first one */ 1681553f9008SMingming ext_debug("first extent in the leaf: %d:%llu:[%d]%d\n", 1682a86c6181SAlex Tomas le32_to_cpu(newext->ee_block), 1683f65e6fbaSAlex Tomas ext_pblock(newext), 1684553f9008SMingming ext4_ext_is_uninitialized(newext), 1685a2df2a63SAmit Arora ext4_ext_get_actual_len(newext)); 1686a86c6181SAlex Tomas path[depth].p_ext = EXT_FIRST_EXTENT(eh); 1687a86c6181SAlex Tomas } else if (le32_to_cpu(newext->ee_block) 1688a86c6181SAlex Tomas > le32_to_cpu(nearex->ee_block)) { 1689a86c6181SAlex Tomas /* BUG_ON(newext->ee_block == nearex->ee_block); */ 1690a86c6181SAlex Tomas if (nearex != EXT_LAST_EXTENT(eh)) { 1691a86c6181SAlex Tomas len = EXT_MAX_EXTENT(eh) - nearex; 1692a86c6181SAlex Tomas len = (len - 1) * sizeof(struct ext4_extent); 1693a86c6181SAlex Tomas len = len < 0 ? 0 : len; 1694553f9008SMingming ext_debug("insert %d:%llu:[%d]%d after: nearest 0x%p, " 1695a86c6181SAlex Tomas "move %d from 0x%p to 0x%p\n", 1696a86c6181SAlex Tomas le32_to_cpu(newext->ee_block), 1697f65e6fbaSAlex Tomas ext_pblock(newext), 1698553f9008SMingming ext4_ext_is_uninitialized(newext), 1699a2df2a63SAmit Arora ext4_ext_get_actual_len(newext), 1700a86c6181SAlex Tomas nearex, len, nearex + 1, nearex + 2); 1701a86c6181SAlex Tomas memmove(nearex + 2, nearex + 1, len); 1702a86c6181SAlex Tomas } 1703a86c6181SAlex Tomas path[depth].p_ext = nearex + 1; 1704a86c6181SAlex Tomas } else { 1705a86c6181SAlex Tomas BUG_ON(newext->ee_block == nearex->ee_block); 1706a86c6181SAlex Tomas len = (EXT_MAX_EXTENT(eh) - nearex) * sizeof(struct ext4_extent); 1707a86c6181SAlex Tomas len = len < 0 ? 0 : len; 1708553f9008SMingming ext_debug("insert %d:%llu:[%d]%d before: nearest 0x%p, " 1709a86c6181SAlex Tomas "move %d from 0x%p to 0x%p\n", 1710a86c6181SAlex Tomas le32_to_cpu(newext->ee_block), 1711f65e6fbaSAlex Tomas ext_pblock(newext), 1712553f9008SMingming ext4_ext_is_uninitialized(newext), 1713a2df2a63SAmit Arora ext4_ext_get_actual_len(newext), 1714a86c6181SAlex Tomas nearex, len, nearex + 1, nearex + 2); 1715a86c6181SAlex Tomas memmove(nearex + 1, nearex, len); 1716a86c6181SAlex Tomas path[depth].p_ext = nearex; 1717a86c6181SAlex Tomas } 1718a86c6181SAlex Tomas 1719e8546d06SMarcin Slusarz le16_add_cpu(&eh->eh_entries, 1); 1720a86c6181SAlex Tomas nearex = path[depth].p_ext; 1721a86c6181SAlex Tomas nearex->ee_block = newext->ee_block; 1722b377611dSAneesh Kumar K.V ext4_ext_store_pblock(nearex, ext_pblock(newext)); 1723a86c6181SAlex Tomas nearex->ee_len = newext->ee_len; 1724a86c6181SAlex Tomas 1725a86c6181SAlex Tomas merge: 1726a86c6181SAlex Tomas /* try to merge extents to the right */ 17270031462bSMingming Cao if (flag != EXT4_GET_BLOCKS_DIO_CREATE_EXT) 172856055d3aSAmit Arora ext4_ext_try_to_merge(inode, path, nearex); 1729a86c6181SAlex Tomas 1730a86c6181SAlex Tomas /* try to merge extents to the left */ 1731a86c6181SAlex Tomas 1732a86c6181SAlex Tomas /* time to correct all indexes above */ 1733a86c6181SAlex Tomas err = ext4_ext_correct_indexes(handle, inode, path); 1734a86c6181SAlex Tomas if (err) 1735a86c6181SAlex Tomas goto cleanup; 1736a86c6181SAlex Tomas 1737a86c6181SAlex Tomas err = ext4_ext_dirty(handle, inode, path + depth); 1738a86c6181SAlex Tomas 1739a86c6181SAlex Tomas cleanup: 1740a86c6181SAlex Tomas if (npath) { 1741a86c6181SAlex Tomas ext4_ext_drop_refs(npath); 1742a86c6181SAlex Tomas kfree(npath); 1743a86c6181SAlex Tomas } 1744a86c6181SAlex Tomas ext4_ext_invalidate_cache(inode); 1745a86c6181SAlex Tomas return err; 1746a86c6181SAlex Tomas } 1747a86c6181SAlex Tomas 17486873fa0dSEric Sandeen int ext4_ext_walk_space(struct inode *inode, ext4_lblk_t block, 17496873fa0dSEric Sandeen ext4_lblk_t num, ext_prepare_callback func, 17506873fa0dSEric Sandeen void *cbdata) 17516873fa0dSEric Sandeen { 17526873fa0dSEric Sandeen struct ext4_ext_path *path = NULL; 17536873fa0dSEric Sandeen struct ext4_ext_cache cbex; 17546873fa0dSEric Sandeen struct ext4_extent *ex; 17556873fa0dSEric Sandeen ext4_lblk_t next, start = 0, end = 0; 17566873fa0dSEric Sandeen ext4_lblk_t last = block + num; 17576873fa0dSEric Sandeen int depth, exists, err = 0; 17586873fa0dSEric Sandeen 17596873fa0dSEric Sandeen BUG_ON(func == NULL); 17606873fa0dSEric Sandeen BUG_ON(inode == NULL); 17616873fa0dSEric Sandeen 17626873fa0dSEric Sandeen while (block < last && block != EXT_MAX_BLOCK) { 17636873fa0dSEric Sandeen num = last - block; 17646873fa0dSEric Sandeen /* find extent for this block */ 17656873fa0dSEric Sandeen path = ext4_ext_find_extent(inode, block, path); 17666873fa0dSEric Sandeen if (IS_ERR(path)) { 17676873fa0dSEric Sandeen err = PTR_ERR(path); 17686873fa0dSEric Sandeen path = NULL; 17696873fa0dSEric Sandeen break; 17706873fa0dSEric Sandeen } 17716873fa0dSEric Sandeen 17726873fa0dSEric Sandeen depth = ext_depth(inode); 17736873fa0dSEric Sandeen BUG_ON(path[depth].p_hdr == NULL); 17746873fa0dSEric Sandeen ex = path[depth].p_ext; 17756873fa0dSEric Sandeen next = ext4_ext_next_allocated_block(path); 17766873fa0dSEric Sandeen 17776873fa0dSEric Sandeen exists = 0; 17786873fa0dSEric Sandeen if (!ex) { 17796873fa0dSEric Sandeen /* there is no extent yet, so try to allocate 17806873fa0dSEric Sandeen * all requested space */ 17816873fa0dSEric Sandeen start = block; 17826873fa0dSEric Sandeen end = block + num; 17836873fa0dSEric Sandeen } else if (le32_to_cpu(ex->ee_block) > block) { 17846873fa0dSEric Sandeen /* need to allocate space before found extent */ 17856873fa0dSEric Sandeen start = block; 17866873fa0dSEric Sandeen end = le32_to_cpu(ex->ee_block); 17876873fa0dSEric Sandeen if (block + num < end) 17886873fa0dSEric Sandeen end = block + num; 17896873fa0dSEric Sandeen } else if (block >= le32_to_cpu(ex->ee_block) 17906873fa0dSEric Sandeen + ext4_ext_get_actual_len(ex)) { 17916873fa0dSEric Sandeen /* need to allocate space after found extent */ 17926873fa0dSEric Sandeen start = block; 17936873fa0dSEric Sandeen end = block + num; 17946873fa0dSEric Sandeen if (end >= next) 17956873fa0dSEric Sandeen end = next; 17966873fa0dSEric Sandeen } else if (block >= le32_to_cpu(ex->ee_block)) { 17976873fa0dSEric Sandeen /* 17986873fa0dSEric Sandeen * some part of requested space is covered 17996873fa0dSEric Sandeen * by found extent 18006873fa0dSEric Sandeen */ 18016873fa0dSEric Sandeen start = block; 18026873fa0dSEric Sandeen end = le32_to_cpu(ex->ee_block) 18036873fa0dSEric Sandeen + ext4_ext_get_actual_len(ex); 18046873fa0dSEric Sandeen if (block + num < end) 18056873fa0dSEric Sandeen end = block + num; 18066873fa0dSEric Sandeen exists = 1; 18076873fa0dSEric Sandeen } else { 18086873fa0dSEric Sandeen BUG(); 18096873fa0dSEric Sandeen } 18106873fa0dSEric Sandeen BUG_ON(end <= start); 18116873fa0dSEric Sandeen 18126873fa0dSEric Sandeen if (!exists) { 18136873fa0dSEric Sandeen cbex.ec_block = start; 18146873fa0dSEric Sandeen cbex.ec_len = end - start; 18156873fa0dSEric Sandeen cbex.ec_start = 0; 18166873fa0dSEric Sandeen cbex.ec_type = EXT4_EXT_CACHE_GAP; 18176873fa0dSEric Sandeen } else { 18186873fa0dSEric Sandeen cbex.ec_block = le32_to_cpu(ex->ee_block); 18196873fa0dSEric Sandeen cbex.ec_len = ext4_ext_get_actual_len(ex); 18206873fa0dSEric Sandeen cbex.ec_start = ext_pblock(ex); 18216873fa0dSEric Sandeen cbex.ec_type = EXT4_EXT_CACHE_EXTENT; 18226873fa0dSEric Sandeen } 18236873fa0dSEric Sandeen 18246873fa0dSEric Sandeen BUG_ON(cbex.ec_len == 0); 18256873fa0dSEric Sandeen err = func(inode, path, &cbex, ex, cbdata); 18266873fa0dSEric Sandeen ext4_ext_drop_refs(path); 18276873fa0dSEric Sandeen 18286873fa0dSEric Sandeen if (err < 0) 18296873fa0dSEric Sandeen break; 18306873fa0dSEric Sandeen 18316873fa0dSEric Sandeen if (err == EXT_REPEAT) 18326873fa0dSEric Sandeen continue; 18336873fa0dSEric Sandeen else if (err == EXT_BREAK) { 18346873fa0dSEric Sandeen err = 0; 18356873fa0dSEric Sandeen break; 18366873fa0dSEric Sandeen } 18376873fa0dSEric Sandeen 18386873fa0dSEric Sandeen if (ext_depth(inode) != depth) { 18396873fa0dSEric Sandeen /* depth was changed. we have to realloc path */ 18406873fa0dSEric Sandeen kfree(path); 18416873fa0dSEric Sandeen path = NULL; 18426873fa0dSEric Sandeen } 18436873fa0dSEric Sandeen 18446873fa0dSEric Sandeen block = cbex.ec_block + cbex.ec_len; 18456873fa0dSEric Sandeen } 18466873fa0dSEric Sandeen 18476873fa0dSEric Sandeen if (path) { 18486873fa0dSEric Sandeen ext4_ext_drop_refs(path); 18496873fa0dSEric Sandeen kfree(path); 18506873fa0dSEric Sandeen } 18516873fa0dSEric Sandeen 18526873fa0dSEric Sandeen return err; 18536873fa0dSEric Sandeen } 18546873fa0dSEric Sandeen 185509b88252SAvantika Mathur static void 1856725d26d3SAneesh Kumar K.V ext4_ext_put_in_cache(struct inode *inode, ext4_lblk_t block, 1857dd54567aSMingming Cao __u32 len, ext4_fsblk_t start, int type) 1858a86c6181SAlex Tomas { 1859a86c6181SAlex Tomas struct ext4_ext_cache *cex; 1860a86c6181SAlex Tomas BUG_ON(len == 0); 18612ec0ae3aSTheodore Ts'o spin_lock(&EXT4_I(inode)->i_block_reservation_lock); 1862a86c6181SAlex Tomas cex = &EXT4_I(inode)->i_cached_extent; 1863a86c6181SAlex Tomas cex->ec_type = type; 1864a86c6181SAlex Tomas cex->ec_block = block; 1865a86c6181SAlex Tomas cex->ec_len = len; 1866a86c6181SAlex Tomas cex->ec_start = start; 18672ec0ae3aSTheodore Ts'o spin_unlock(&EXT4_I(inode)->i_block_reservation_lock); 1868a86c6181SAlex Tomas } 1869a86c6181SAlex Tomas 1870a86c6181SAlex Tomas /* 1871d0d856e8SRandy Dunlap * ext4_ext_put_gap_in_cache: 1872d0d856e8SRandy Dunlap * calculate boundaries of the gap that the requested block fits into 1873a86c6181SAlex Tomas * and cache this gap 1874a86c6181SAlex Tomas */ 187509b88252SAvantika Mathur static void 1876a86c6181SAlex Tomas ext4_ext_put_gap_in_cache(struct inode *inode, struct ext4_ext_path *path, 1877725d26d3SAneesh Kumar K.V ext4_lblk_t block) 1878a86c6181SAlex Tomas { 1879a86c6181SAlex Tomas int depth = ext_depth(inode); 1880725d26d3SAneesh Kumar K.V unsigned long len; 1881725d26d3SAneesh Kumar K.V ext4_lblk_t lblock; 1882a86c6181SAlex Tomas struct ext4_extent *ex; 1883a86c6181SAlex Tomas 1884a86c6181SAlex Tomas ex = path[depth].p_ext; 1885a86c6181SAlex Tomas if (ex == NULL) { 1886a86c6181SAlex Tomas /* there is no extent yet, so gap is [0;-] */ 1887a86c6181SAlex Tomas lblock = 0; 1888a86c6181SAlex Tomas len = EXT_MAX_BLOCK; 1889a86c6181SAlex Tomas ext_debug("cache gap(whole file):"); 1890a86c6181SAlex Tomas } else if (block < le32_to_cpu(ex->ee_block)) { 1891a86c6181SAlex Tomas lblock = block; 1892a86c6181SAlex Tomas len = le32_to_cpu(ex->ee_block) - block; 1893bba90743SEric Sandeen ext_debug("cache gap(before): %u [%u:%u]", 1894bba90743SEric Sandeen block, 1895bba90743SEric Sandeen le32_to_cpu(ex->ee_block), 1896bba90743SEric Sandeen ext4_ext_get_actual_len(ex)); 1897a86c6181SAlex Tomas } else if (block >= le32_to_cpu(ex->ee_block) 1898a2df2a63SAmit Arora + ext4_ext_get_actual_len(ex)) { 1899725d26d3SAneesh Kumar K.V ext4_lblk_t next; 1900a86c6181SAlex Tomas lblock = le32_to_cpu(ex->ee_block) 1901a2df2a63SAmit Arora + ext4_ext_get_actual_len(ex); 1902725d26d3SAneesh Kumar K.V 1903725d26d3SAneesh Kumar K.V next = ext4_ext_next_allocated_block(path); 1904bba90743SEric Sandeen ext_debug("cache gap(after): [%u:%u] %u", 1905bba90743SEric Sandeen le32_to_cpu(ex->ee_block), 1906bba90743SEric Sandeen ext4_ext_get_actual_len(ex), 1907bba90743SEric Sandeen block); 1908725d26d3SAneesh Kumar K.V BUG_ON(next == lblock); 1909725d26d3SAneesh Kumar K.V len = next - lblock; 1910a86c6181SAlex Tomas } else { 1911a86c6181SAlex Tomas lblock = len = 0; 1912a86c6181SAlex Tomas BUG(); 1913a86c6181SAlex Tomas } 1914a86c6181SAlex Tomas 1915bba90743SEric Sandeen ext_debug(" -> %u:%lu\n", lblock, len); 1916a86c6181SAlex Tomas ext4_ext_put_in_cache(inode, lblock, len, 0, EXT4_EXT_CACHE_GAP); 1917a86c6181SAlex Tomas } 1918a86c6181SAlex Tomas 191909b88252SAvantika Mathur static int 1920725d26d3SAneesh Kumar K.V ext4_ext_in_cache(struct inode *inode, ext4_lblk_t block, 1921a86c6181SAlex Tomas struct ext4_extent *ex) 1922a86c6181SAlex Tomas { 1923a86c6181SAlex Tomas struct ext4_ext_cache *cex; 19242ec0ae3aSTheodore Ts'o int ret = EXT4_EXT_CACHE_NO; 1925a86c6181SAlex Tomas 19262ec0ae3aSTheodore Ts'o /* 19272ec0ae3aSTheodore Ts'o * We borrow i_block_reservation_lock to protect i_cached_extent 19282ec0ae3aSTheodore Ts'o */ 19292ec0ae3aSTheodore Ts'o spin_lock(&EXT4_I(inode)->i_block_reservation_lock); 1930a86c6181SAlex Tomas cex = &EXT4_I(inode)->i_cached_extent; 1931a86c6181SAlex Tomas 1932a86c6181SAlex Tomas /* has cache valid data? */ 1933a86c6181SAlex Tomas if (cex->ec_type == EXT4_EXT_CACHE_NO) 19342ec0ae3aSTheodore Ts'o goto errout; 1935a86c6181SAlex Tomas 1936a86c6181SAlex Tomas BUG_ON(cex->ec_type != EXT4_EXT_CACHE_GAP && 1937a86c6181SAlex Tomas cex->ec_type != EXT4_EXT_CACHE_EXTENT); 1938a86c6181SAlex Tomas if (block >= cex->ec_block && block < cex->ec_block + cex->ec_len) { 1939a86c6181SAlex Tomas ex->ee_block = cpu_to_le32(cex->ec_block); 1940f65e6fbaSAlex Tomas ext4_ext_store_pblock(ex, cex->ec_start); 1941a86c6181SAlex Tomas ex->ee_len = cpu_to_le16(cex->ec_len); 1942bba90743SEric Sandeen ext_debug("%u cached by %u:%u:%llu\n", 1943bba90743SEric Sandeen block, 1944bba90743SEric Sandeen cex->ec_block, cex->ec_len, cex->ec_start); 19452ec0ae3aSTheodore Ts'o ret = cex->ec_type; 1946a86c6181SAlex Tomas } 19472ec0ae3aSTheodore Ts'o errout: 19482ec0ae3aSTheodore Ts'o spin_unlock(&EXT4_I(inode)->i_block_reservation_lock); 19492ec0ae3aSTheodore Ts'o return ret; 1950a86c6181SAlex Tomas } 1951a86c6181SAlex Tomas 1952a86c6181SAlex Tomas /* 1953d0d856e8SRandy Dunlap * ext4_ext_rm_idx: 1954d0d856e8SRandy Dunlap * removes index from the index block. 1955d0d856e8SRandy Dunlap * It's used in truncate case only, thus all requests are for 1956d0d856e8SRandy Dunlap * last index in the block only. 1957a86c6181SAlex Tomas */ 19581d03ec98SAneesh Kumar K.V static int ext4_ext_rm_idx(handle_t *handle, struct inode *inode, 1959a86c6181SAlex Tomas struct ext4_ext_path *path) 1960a86c6181SAlex Tomas { 1961a86c6181SAlex Tomas int err; 1962f65e6fbaSAlex Tomas ext4_fsblk_t leaf; 1963a86c6181SAlex Tomas 1964a86c6181SAlex Tomas /* free index block */ 1965a86c6181SAlex Tomas path--; 1966f65e6fbaSAlex Tomas leaf = idx_pblock(path->p_idx); 1967a86c6181SAlex Tomas BUG_ON(path->p_hdr->eh_entries == 0); 19687e028976SAvantika Mathur err = ext4_ext_get_access(handle, inode, path); 19697e028976SAvantika Mathur if (err) 1970a86c6181SAlex Tomas return err; 1971e8546d06SMarcin Slusarz le16_add_cpu(&path->p_hdr->eh_entries, -1); 19727e028976SAvantika Mathur err = ext4_ext_dirty(handle, inode, path); 19737e028976SAvantika Mathur if (err) 1974a86c6181SAlex Tomas return err; 19752ae02107SMingming Cao ext_debug("index is empty, remove it, free block %llu\n", leaf); 1976*e6362609STheodore Ts'o ext4_free_blocks(handle, inode, 0, leaf, 1, 1977*e6362609STheodore Ts'o EXT4_FREE_BLOCKS_METADATA | EXT4_FREE_BLOCKS_FORGET); 1978a86c6181SAlex Tomas return err; 1979a86c6181SAlex Tomas } 1980a86c6181SAlex Tomas 1981a86c6181SAlex Tomas /* 1982ee12b630SMingming Cao * ext4_ext_calc_credits_for_single_extent: 1983ee12b630SMingming Cao * This routine returns max. credits that needed to insert an extent 1984ee12b630SMingming Cao * to the extent tree. 1985ee12b630SMingming Cao * When pass the actual path, the caller should calculate credits 1986ee12b630SMingming Cao * under i_data_sem. 1987a86c6181SAlex Tomas */ 1988525f4ed8SMingming Cao int ext4_ext_calc_credits_for_single_extent(struct inode *inode, int nrblocks, 1989a86c6181SAlex Tomas struct ext4_ext_path *path) 1990a86c6181SAlex Tomas { 1991a86c6181SAlex Tomas if (path) { 1992ee12b630SMingming Cao int depth = ext_depth(inode); 1993f3bd1f3fSMingming Cao int ret = 0; 1994ee12b630SMingming Cao 1995a86c6181SAlex Tomas /* probably there is space in leaf? */ 1996a86c6181SAlex Tomas if (le16_to_cpu(path[depth].p_hdr->eh_entries) 1997ee12b630SMingming Cao < le16_to_cpu(path[depth].p_hdr->eh_max)) { 1998ee12b630SMingming Cao 1999ee12b630SMingming Cao /* 2000ee12b630SMingming Cao * There are some space in the leaf tree, no 2001ee12b630SMingming Cao * need to account for leaf block credit 2002ee12b630SMingming Cao * 2003ee12b630SMingming Cao * bitmaps and block group descriptor blocks 2004ee12b630SMingming Cao * and other metadat blocks still need to be 2005ee12b630SMingming Cao * accounted. 2006ee12b630SMingming Cao */ 2007525f4ed8SMingming Cao /* 1 bitmap, 1 block group descriptor */ 2008ee12b630SMingming Cao ret = 2 + EXT4_META_TRANS_BLOCKS(inode->i_sb); 20095887e98bSAneesh Kumar K.V return ret; 2010ee12b630SMingming Cao } 2011ee12b630SMingming Cao } 2012ee12b630SMingming Cao 2013525f4ed8SMingming Cao return ext4_chunk_trans_blocks(inode, nrblocks); 2014a86c6181SAlex Tomas } 2015a86c6181SAlex Tomas 2016a86c6181SAlex Tomas /* 2017ee12b630SMingming Cao * How many index/leaf blocks need to change/allocate to modify nrblocks? 2018ee12b630SMingming Cao * 2019ee12b630SMingming Cao * if nrblocks are fit in a single extent (chunk flag is 1), then 2020ee12b630SMingming Cao * in the worse case, each tree level index/leaf need to be changed 2021ee12b630SMingming Cao * if the tree split due to insert a new extent, then the old tree 2022ee12b630SMingming Cao * index/leaf need to be updated too 2023ee12b630SMingming Cao * 2024ee12b630SMingming Cao * If the nrblocks are discontiguous, they could cause 2025ee12b630SMingming Cao * the whole tree split more than once, but this is really rare. 2026a86c6181SAlex Tomas */ 2027525f4ed8SMingming Cao int ext4_ext_index_trans_blocks(struct inode *inode, int nrblocks, int chunk) 2028ee12b630SMingming Cao { 2029ee12b630SMingming Cao int index; 2030ee12b630SMingming Cao int depth = ext_depth(inode); 2031a86c6181SAlex Tomas 2032ee12b630SMingming Cao if (chunk) 2033ee12b630SMingming Cao index = depth * 2; 2034ee12b630SMingming Cao else 2035ee12b630SMingming Cao index = depth * 3; 2036a86c6181SAlex Tomas 2037ee12b630SMingming Cao return index; 2038a86c6181SAlex Tomas } 2039a86c6181SAlex Tomas 2040a86c6181SAlex Tomas static int ext4_remove_blocks(handle_t *handle, struct inode *inode, 2041a86c6181SAlex Tomas struct ext4_extent *ex, 2042725d26d3SAneesh Kumar K.V ext4_lblk_t from, ext4_lblk_t to) 2043a86c6181SAlex Tomas { 2044a2df2a63SAmit Arora unsigned short ee_len = ext4_ext_get_actual_len(ex); 2045*e6362609STheodore Ts'o int flags = EXT4_FREE_BLOCKS_FORGET; 2046a86c6181SAlex Tomas 2047c9de560dSAlex Tomas if (S_ISDIR(inode->i_mode) || S_ISLNK(inode->i_mode)) 2048*e6362609STheodore Ts'o flags |= EXT4_FREE_BLOCKS_METADATA; 2049a86c6181SAlex Tomas #ifdef EXTENTS_STATS 2050a86c6181SAlex Tomas { 2051a86c6181SAlex Tomas struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb); 2052a86c6181SAlex Tomas spin_lock(&sbi->s_ext_stats_lock); 2053a86c6181SAlex Tomas sbi->s_ext_blocks += ee_len; 2054a86c6181SAlex Tomas sbi->s_ext_extents++; 2055a86c6181SAlex Tomas if (ee_len < sbi->s_ext_min) 2056a86c6181SAlex Tomas sbi->s_ext_min = ee_len; 2057a86c6181SAlex Tomas if (ee_len > sbi->s_ext_max) 2058a86c6181SAlex Tomas sbi->s_ext_max = ee_len; 2059a86c6181SAlex Tomas if (ext_depth(inode) > sbi->s_depth_max) 2060a86c6181SAlex Tomas sbi->s_depth_max = ext_depth(inode); 2061a86c6181SAlex Tomas spin_unlock(&sbi->s_ext_stats_lock); 2062a86c6181SAlex Tomas } 2063a86c6181SAlex Tomas #endif 2064a86c6181SAlex Tomas if (from >= le32_to_cpu(ex->ee_block) 2065a2df2a63SAmit Arora && to == le32_to_cpu(ex->ee_block) + ee_len - 1) { 2066a86c6181SAlex Tomas /* tail removal */ 2067725d26d3SAneesh Kumar K.V ext4_lblk_t num; 2068f65e6fbaSAlex Tomas ext4_fsblk_t start; 2069725d26d3SAneesh Kumar K.V 2070a2df2a63SAmit Arora num = le32_to_cpu(ex->ee_block) + ee_len - from; 2071a2df2a63SAmit Arora start = ext_pblock(ex) + ee_len - num; 2072725d26d3SAneesh Kumar K.V ext_debug("free last %u blocks starting %llu\n", num, start); 2073*e6362609STheodore Ts'o ext4_free_blocks(handle, inode, 0, start, num, flags); 2074a86c6181SAlex Tomas } else if (from == le32_to_cpu(ex->ee_block) 2075a2df2a63SAmit Arora && to <= le32_to_cpu(ex->ee_block) + ee_len - 1) { 2076725d26d3SAneesh Kumar K.V printk(KERN_INFO "strange request: removal %u-%u from %u:%u\n", 2077a2df2a63SAmit Arora from, to, le32_to_cpu(ex->ee_block), ee_len); 2078a86c6181SAlex Tomas } else { 2079725d26d3SAneesh Kumar K.V printk(KERN_INFO "strange request: removal(2) " 2080725d26d3SAneesh Kumar K.V "%u-%u from %u:%u\n", 2081a2df2a63SAmit Arora from, to, le32_to_cpu(ex->ee_block), ee_len); 2082a86c6181SAlex Tomas } 2083a86c6181SAlex Tomas return 0; 2084a86c6181SAlex Tomas } 2085a86c6181SAlex Tomas 2086a86c6181SAlex Tomas static int 2087a86c6181SAlex Tomas ext4_ext_rm_leaf(handle_t *handle, struct inode *inode, 2088725d26d3SAneesh Kumar K.V struct ext4_ext_path *path, ext4_lblk_t start) 2089a86c6181SAlex Tomas { 2090a86c6181SAlex Tomas int err = 0, correct_index = 0; 2091a86c6181SAlex Tomas int depth = ext_depth(inode), credits; 2092a86c6181SAlex Tomas struct ext4_extent_header *eh; 2093725d26d3SAneesh Kumar K.V ext4_lblk_t a, b, block; 2094725d26d3SAneesh Kumar K.V unsigned num; 2095725d26d3SAneesh Kumar K.V ext4_lblk_t ex_ee_block; 2096a86c6181SAlex Tomas unsigned short ex_ee_len; 2097a2df2a63SAmit Arora unsigned uninitialized = 0; 2098a86c6181SAlex Tomas struct ext4_extent *ex; 2099a86c6181SAlex Tomas 2100c29c0ae7SAlex Tomas /* the header must be checked already in ext4_ext_remove_space() */ 2101725d26d3SAneesh Kumar K.V ext_debug("truncate since %u in leaf\n", start); 2102a86c6181SAlex Tomas if (!path[depth].p_hdr) 2103a86c6181SAlex Tomas path[depth].p_hdr = ext_block_hdr(path[depth].p_bh); 2104a86c6181SAlex Tomas eh = path[depth].p_hdr; 2105a86c6181SAlex Tomas BUG_ON(eh == NULL); 2106a86c6181SAlex Tomas 2107a86c6181SAlex Tomas /* find where to start removing */ 2108a86c6181SAlex Tomas ex = EXT_LAST_EXTENT(eh); 2109a86c6181SAlex Tomas 2110a86c6181SAlex Tomas ex_ee_block = le32_to_cpu(ex->ee_block); 2111a2df2a63SAmit Arora ex_ee_len = ext4_ext_get_actual_len(ex); 2112a86c6181SAlex Tomas 2113a86c6181SAlex Tomas while (ex >= EXT_FIRST_EXTENT(eh) && 2114a86c6181SAlex Tomas ex_ee_block + ex_ee_len > start) { 2115a41f2071SAneesh Kumar K.V 2116a41f2071SAneesh Kumar K.V if (ext4_ext_is_uninitialized(ex)) 2117a41f2071SAneesh Kumar K.V uninitialized = 1; 2118a41f2071SAneesh Kumar K.V else 2119a41f2071SAneesh Kumar K.V uninitialized = 0; 2120a41f2071SAneesh Kumar K.V 2121553f9008SMingming ext_debug("remove ext %u:[%d]%d\n", ex_ee_block, 2122553f9008SMingming uninitialized, ex_ee_len); 2123a86c6181SAlex Tomas path[depth].p_ext = ex; 2124a86c6181SAlex Tomas 2125a86c6181SAlex Tomas a = ex_ee_block > start ? ex_ee_block : start; 2126a86c6181SAlex Tomas b = ex_ee_block + ex_ee_len - 1 < EXT_MAX_BLOCK ? 2127a86c6181SAlex Tomas ex_ee_block + ex_ee_len - 1 : EXT_MAX_BLOCK; 2128a86c6181SAlex Tomas 2129a86c6181SAlex Tomas ext_debug(" border %u:%u\n", a, b); 2130a86c6181SAlex Tomas 2131a86c6181SAlex Tomas if (a != ex_ee_block && b != ex_ee_block + ex_ee_len - 1) { 2132a86c6181SAlex Tomas block = 0; 2133a86c6181SAlex Tomas num = 0; 2134a86c6181SAlex Tomas BUG(); 2135a86c6181SAlex Tomas } else if (a != ex_ee_block) { 2136a86c6181SAlex Tomas /* remove tail of the extent */ 2137a86c6181SAlex Tomas block = ex_ee_block; 2138a86c6181SAlex Tomas num = a - block; 2139a86c6181SAlex Tomas } else if (b != ex_ee_block + ex_ee_len - 1) { 2140a86c6181SAlex Tomas /* remove head of the extent */ 2141a86c6181SAlex Tomas block = a; 2142a86c6181SAlex Tomas num = b - a; 2143a86c6181SAlex Tomas /* there is no "make a hole" API yet */ 2144a86c6181SAlex Tomas BUG(); 2145a86c6181SAlex Tomas } else { 2146a86c6181SAlex Tomas /* remove whole extent: excellent! */ 2147a86c6181SAlex Tomas block = ex_ee_block; 2148a86c6181SAlex Tomas num = 0; 2149a86c6181SAlex Tomas BUG_ON(a != ex_ee_block); 2150a86c6181SAlex Tomas BUG_ON(b != ex_ee_block + ex_ee_len - 1); 2151a86c6181SAlex Tomas } 2152a86c6181SAlex Tomas 215334071da7STheodore Ts'o /* 215434071da7STheodore Ts'o * 3 for leaf, sb, and inode plus 2 (bmap and group 215534071da7STheodore Ts'o * descriptor) for each block group; assume two block 215634071da7STheodore Ts'o * groups plus ex_ee_len/blocks_per_block_group for 215734071da7STheodore Ts'o * the worst case 215834071da7STheodore Ts'o */ 215934071da7STheodore Ts'o credits = 7 + 2*(ex_ee_len/EXT4_BLOCKS_PER_GROUP(inode->i_sb)); 2160a86c6181SAlex Tomas if (ex == EXT_FIRST_EXTENT(eh)) { 2161a86c6181SAlex Tomas correct_index = 1; 2162a86c6181SAlex Tomas credits += (ext_depth(inode)) + 1; 2163a86c6181SAlex Tomas } 2164a86c6181SAlex Tomas credits += 2 * EXT4_QUOTA_TRANS_BLOCKS(inode->i_sb); 2165a86c6181SAlex Tomas 2166487caeefSJan Kara err = ext4_ext_truncate_extend_restart(handle, inode, credits); 21679102e4faSShen Feng if (err) 2168a86c6181SAlex Tomas goto out; 2169a86c6181SAlex Tomas 2170a86c6181SAlex Tomas err = ext4_ext_get_access(handle, inode, path + depth); 2171a86c6181SAlex Tomas if (err) 2172a86c6181SAlex Tomas goto out; 2173a86c6181SAlex Tomas 2174a86c6181SAlex Tomas err = ext4_remove_blocks(handle, inode, ex, a, b); 2175a86c6181SAlex Tomas if (err) 2176a86c6181SAlex Tomas goto out; 2177a86c6181SAlex Tomas 2178a86c6181SAlex Tomas if (num == 0) { 2179d0d856e8SRandy Dunlap /* this extent is removed; mark slot entirely unused */ 2180f65e6fbaSAlex Tomas ext4_ext_store_pblock(ex, 0); 2181e8546d06SMarcin Slusarz le16_add_cpu(&eh->eh_entries, -1); 2182a86c6181SAlex Tomas } 2183a86c6181SAlex Tomas 2184a86c6181SAlex Tomas ex->ee_block = cpu_to_le32(block); 2185a86c6181SAlex Tomas ex->ee_len = cpu_to_le16(num); 2186749269faSAmit Arora /* 2187749269faSAmit Arora * Do not mark uninitialized if all the blocks in the 2188749269faSAmit Arora * extent have been removed. 2189749269faSAmit Arora */ 2190749269faSAmit Arora if (uninitialized && num) 2191a2df2a63SAmit Arora ext4_ext_mark_uninitialized(ex); 2192a86c6181SAlex Tomas 2193a86c6181SAlex Tomas err = ext4_ext_dirty(handle, inode, path + depth); 2194a86c6181SAlex Tomas if (err) 2195a86c6181SAlex Tomas goto out; 2196a86c6181SAlex Tomas 21972ae02107SMingming Cao ext_debug("new extent: %u:%u:%llu\n", block, num, 2198f65e6fbaSAlex Tomas ext_pblock(ex)); 2199a86c6181SAlex Tomas ex--; 2200a86c6181SAlex Tomas ex_ee_block = le32_to_cpu(ex->ee_block); 2201a2df2a63SAmit Arora ex_ee_len = ext4_ext_get_actual_len(ex); 2202a86c6181SAlex Tomas } 2203a86c6181SAlex Tomas 2204a86c6181SAlex Tomas if (correct_index && eh->eh_entries) 2205a86c6181SAlex Tomas err = ext4_ext_correct_indexes(handle, inode, path); 2206a86c6181SAlex Tomas 2207a86c6181SAlex Tomas /* if this leaf is free, then we should 2208a86c6181SAlex Tomas * remove it from index block above */ 2209a86c6181SAlex Tomas if (err == 0 && eh->eh_entries == 0 && path[depth].p_bh != NULL) 2210a86c6181SAlex Tomas err = ext4_ext_rm_idx(handle, inode, path + depth); 2211a86c6181SAlex Tomas 2212a86c6181SAlex Tomas out: 2213a86c6181SAlex Tomas return err; 2214a86c6181SAlex Tomas } 2215a86c6181SAlex Tomas 2216a86c6181SAlex Tomas /* 2217d0d856e8SRandy Dunlap * ext4_ext_more_to_rm: 2218d0d856e8SRandy Dunlap * returns 1 if current index has to be freed (even partial) 2219a86c6181SAlex Tomas */ 222009b88252SAvantika Mathur static int 2221a86c6181SAlex Tomas ext4_ext_more_to_rm(struct ext4_ext_path *path) 2222a86c6181SAlex Tomas { 2223a86c6181SAlex Tomas BUG_ON(path->p_idx == NULL); 2224a86c6181SAlex Tomas 2225a86c6181SAlex Tomas if (path->p_idx < EXT_FIRST_INDEX(path->p_hdr)) 2226a86c6181SAlex Tomas return 0; 2227a86c6181SAlex Tomas 2228a86c6181SAlex Tomas /* 2229d0d856e8SRandy Dunlap * if truncate on deeper level happened, it wasn't partial, 2230a86c6181SAlex Tomas * so we have to consider current index for truncation 2231a86c6181SAlex Tomas */ 2232a86c6181SAlex Tomas if (le16_to_cpu(path->p_hdr->eh_entries) == path->p_block) 2233a86c6181SAlex Tomas return 0; 2234a86c6181SAlex Tomas return 1; 2235a86c6181SAlex Tomas } 2236a86c6181SAlex Tomas 22371d03ec98SAneesh Kumar K.V static int ext4_ext_remove_space(struct inode *inode, ext4_lblk_t start) 2238a86c6181SAlex Tomas { 2239a86c6181SAlex Tomas struct super_block *sb = inode->i_sb; 2240a86c6181SAlex Tomas int depth = ext_depth(inode); 2241a86c6181SAlex Tomas struct ext4_ext_path *path; 2242a86c6181SAlex Tomas handle_t *handle; 2243a86c6181SAlex Tomas int i = 0, err = 0; 2244a86c6181SAlex Tomas 2245725d26d3SAneesh Kumar K.V ext_debug("truncate since %u\n", start); 2246a86c6181SAlex Tomas 2247a86c6181SAlex Tomas /* probably first extent we're gonna free will be last in block */ 2248a86c6181SAlex Tomas handle = ext4_journal_start(inode, depth + 1); 2249a86c6181SAlex Tomas if (IS_ERR(handle)) 2250a86c6181SAlex Tomas return PTR_ERR(handle); 2251a86c6181SAlex Tomas 2252a86c6181SAlex Tomas ext4_ext_invalidate_cache(inode); 2253a86c6181SAlex Tomas 2254a86c6181SAlex Tomas /* 2255d0d856e8SRandy Dunlap * We start scanning from right side, freeing all the blocks 2256d0d856e8SRandy Dunlap * after i_size and walking into the tree depth-wise. 2257a86c6181SAlex Tomas */ 2258216553c4SJosef Bacik path = kzalloc(sizeof(struct ext4_ext_path) * (depth + 1), GFP_NOFS); 2259a86c6181SAlex Tomas if (path == NULL) { 2260a86c6181SAlex Tomas ext4_journal_stop(handle); 2261a86c6181SAlex Tomas return -ENOMEM; 2262a86c6181SAlex Tomas } 2263a86c6181SAlex Tomas path[0].p_hdr = ext_inode_hdr(inode); 226456b19868SAneesh Kumar K.V if (ext4_ext_check(inode, path[0].p_hdr, depth)) { 2265a86c6181SAlex Tomas err = -EIO; 2266a86c6181SAlex Tomas goto out; 2267a86c6181SAlex Tomas } 2268a86c6181SAlex Tomas path[0].p_depth = depth; 2269a86c6181SAlex Tomas 2270a86c6181SAlex Tomas while (i >= 0 && err == 0) { 2271a86c6181SAlex Tomas if (i == depth) { 2272a86c6181SAlex Tomas /* this is leaf block */ 2273a86c6181SAlex Tomas err = ext4_ext_rm_leaf(handle, inode, path, start); 2274d0d856e8SRandy Dunlap /* root level has p_bh == NULL, brelse() eats this */ 2275a86c6181SAlex Tomas brelse(path[i].p_bh); 2276a86c6181SAlex Tomas path[i].p_bh = NULL; 2277a86c6181SAlex Tomas i--; 2278a86c6181SAlex Tomas continue; 2279a86c6181SAlex Tomas } 2280a86c6181SAlex Tomas 2281a86c6181SAlex Tomas /* this is index block */ 2282a86c6181SAlex Tomas if (!path[i].p_hdr) { 2283a86c6181SAlex Tomas ext_debug("initialize header\n"); 2284a86c6181SAlex Tomas path[i].p_hdr = ext_block_hdr(path[i].p_bh); 2285a86c6181SAlex Tomas } 2286a86c6181SAlex Tomas 2287a86c6181SAlex Tomas if (!path[i].p_idx) { 2288d0d856e8SRandy Dunlap /* this level hasn't been touched yet */ 2289a86c6181SAlex Tomas path[i].p_idx = EXT_LAST_INDEX(path[i].p_hdr); 2290a86c6181SAlex Tomas path[i].p_block = le16_to_cpu(path[i].p_hdr->eh_entries)+1; 2291a86c6181SAlex Tomas ext_debug("init index ptr: hdr 0x%p, num %d\n", 2292a86c6181SAlex Tomas path[i].p_hdr, 2293a86c6181SAlex Tomas le16_to_cpu(path[i].p_hdr->eh_entries)); 2294a86c6181SAlex Tomas } else { 2295d0d856e8SRandy Dunlap /* we were already here, see at next index */ 2296a86c6181SAlex Tomas path[i].p_idx--; 2297a86c6181SAlex Tomas } 2298a86c6181SAlex Tomas 2299a86c6181SAlex Tomas ext_debug("level %d - index, first 0x%p, cur 0x%p\n", 2300a86c6181SAlex Tomas i, EXT_FIRST_INDEX(path[i].p_hdr), 2301a86c6181SAlex Tomas path[i].p_idx); 2302a86c6181SAlex Tomas if (ext4_ext_more_to_rm(path + i)) { 2303c29c0ae7SAlex Tomas struct buffer_head *bh; 2304a86c6181SAlex Tomas /* go to the next level */ 23052ae02107SMingming Cao ext_debug("move to level %d (block %llu)\n", 2306f65e6fbaSAlex Tomas i + 1, idx_pblock(path[i].p_idx)); 2307a86c6181SAlex Tomas memset(path + i + 1, 0, sizeof(*path)); 2308c29c0ae7SAlex Tomas bh = sb_bread(sb, idx_pblock(path[i].p_idx)); 2309c29c0ae7SAlex Tomas if (!bh) { 2310a86c6181SAlex Tomas /* should we reset i_size? */ 2311a86c6181SAlex Tomas err = -EIO; 2312a86c6181SAlex Tomas break; 2313a86c6181SAlex Tomas } 2314c29c0ae7SAlex Tomas if (WARN_ON(i + 1 > depth)) { 2315c29c0ae7SAlex Tomas err = -EIO; 2316c29c0ae7SAlex Tomas break; 2317c29c0ae7SAlex Tomas } 231856b19868SAneesh Kumar K.V if (ext4_ext_check(inode, ext_block_hdr(bh), 2319c29c0ae7SAlex Tomas depth - i - 1)) { 2320c29c0ae7SAlex Tomas err = -EIO; 2321c29c0ae7SAlex Tomas break; 2322c29c0ae7SAlex Tomas } 2323c29c0ae7SAlex Tomas path[i + 1].p_bh = bh; 2324a86c6181SAlex Tomas 2325d0d856e8SRandy Dunlap /* save actual number of indexes since this 2326d0d856e8SRandy Dunlap * number is changed at the next iteration */ 2327a86c6181SAlex Tomas path[i].p_block = le16_to_cpu(path[i].p_hdr->eh_entries); 2328a86c6181SAlex Tomas i++; 2329a86c6181SAlex Tomas } else { 2330d0d856e8SRandy Dunlap /* we finished processing this index, go up */ 2331a86c6181SAlex Tomas if (path[i].p_hdr->eh_entries == 0 && i > 0) { 2332d0d856e8SRandy Dunlap /* index is empty, remove it; 2333a86c6181SAlex Tomas * handle must be already prepared by the 2334a86c6181SAlex Tomas * truncatei_leaf() */ 2335a86c6181SAlex Tomas err = ext4_ext_rm_idx(handle, inode, path + i); 2336a86c6181SAlex Tomas } 2337d0d856e8SRandy Dunlap /* root level has p_bh == NULL, brelse() eats this */ 2338a86c6181SAlex Tomas brelse(path[i].p_bh); 2339a86c6181SAlex Tomas path[i].p_bh = NULL; 2340a86c6181SAlex Tomas i--; 2341a86c6181SAlex Tomas ext_debug("return to level %d\n", i); 2342a86c6181SAlex Tomas } 2343a86c6181SAlex Tomas } 2344a86c6181SAlex Tomas 2345a86c6181SAlex Tomas /* TODO: flexible tree reduction should be here */ 2346a86c6181SAlex Tomas if (path->p_hdr->eh_entries == 0) { 2347a86c6181SAlex Tomas /* 2348d0d856e8SRandy Dunlap * truncate to zero freed all the tree, 2349d0d856e8SRandy Dunlap * so we need to correct eh_depth 2350a86c6181SAlex Tomas */ 2351a86c6181SAlex Tomas err = ext4_ext_get_access(handle, inode, path); 2352a86c6181SAlex Tomas if (err == 0) { 2353a86c6181SAlex Tomas ext_inode_hdr(inode)->eh_depth = 0; 2354a86c6181SAlex Tomas ext_inode_hdr(inode)->eh_max = 235555ad63bfSTheodore Ts'o cpu_to_le16(ext4_ext_space_root(inode, 0)); 2356a86c6181SAlex Tomas err = ext4_ext_dirty(handle, inode, path); 2357a86c6181SAlex Tomas } 2358a86c6181SAlex Tomas } 2359a86c6181SAlex Tomas out: 2360a86c6181SAlex Tomas ext4_ext_drop_refs(path); 2361a86c6181SAlex Tomas kfree(path); 2362a86c6181SAlex Tomas ext4_journal_stop(handle); 2363a86c6181SAlex Tomas 2364a86c6181SAlex Tomas return err; 2365a86c6181SAlex Tomas } 2366a86c6181SAlex Tomas 2367a86c6181SAlex Tomas /* 2368a86c6181SAlex Tomas * called at mount time 2369a86c6181SAlex Tomas */ 2370a86c6181SAlex Tomas void ext4_ext_init(struct super_block *sb) 2371a86c6181SAlex Tomas { 2372a86c6181SAlex Tomas /* 2373a86c6181SAlex Tomas * possible initialization would be here 2374a86c6181SAlex Tomas */ 2375a86c6181SAlex Tomas 237683982b6fSTheodore Ts'o if (EXT4_HAS_INCOMPAT_FEATURE(sb, EXT4_FEATURE_INCOMPAT_EXTENTS)) { 237790576c0bSTheodore Ts'o #if defined(AGGRESSIVE_TEST) || defined(CHECK_BINSEARCH) || defined(EXTENTS_STATS) 23784776004fSTheodore Ts'o printk(KERN_INFO "EXT4-fs: file extents enabled"); 2379bbf2f9fbSRobert P. J. Day #ifdef AGGRESSIVE_TEST 2380bbf2f9fbSRobert P. J. Day printk(", aggressive tests"); 2381a86c6181SAlex Tomas #endif 2382a86c6181SAlex Tomas #ifdef CHECK_BINSEARCH 2383a86c6181SAlex Tomas printk(", check binsearch"); 2384a86c6181SAlex Tomas #endif 2385a86c6181SAlex Tomas #ifdef EXTENTS_STATS 2386a86c6181SAlex Tomas printk(", stats"); 2387a86c6181SAlex Tomas #endif 2388a86c6181SAlex Tomas printk("\n"); 238990576c0bSTheodore Ts'o #endif 2390a86c6181SAlex Tomas #ifdef EXTENTS_STATS 2391a86c6181SAlex Tomas spin_lock_init(&EXT4_SB(sb)->s_ext_stats_lock); 2392a86c6181SAlex Tomas EXT4_SB(sb)->s_ext_min = 1 << 30; 2393a86c6181SAlex Tomas EXT4_SB(sb)->s_ext_max = 0; 2394a86c6181SAlex Tomas #endif 2395a86c6181SAlex Tomas } 2396a86c6181SAlex Tomas } 2397a86c6181SAlex Tomas 2398a86c6181SAlex Tomas /* 2399a86c6181SAlex Tomas * called at umount time 2400a86c6181SAlex Tomas */ 2401a86c6181SAlex Tomas void ext4_ext_release(struct super_block *sb) 2402a86c6181SAlex Tomas { 240383982b6fSTheodore Ts'o if (!EXT4_HAS_INCOMPAT_FEATURE(sb, EXT4_FEATURE_INCOMPAT_EXTENTS)) 2404a86c6181SAlex Tomas return; 2405a86c6181SAlex Tomas 2406a86c6181SAlex Tomas #ifdef EXTENTS_STATS 2407a86c6181SAlex Tomas if (EXT4_SB(sb)->s_ext_blocks && EXT4_SB(sb)->s_ext_extents) { 2408a86c6181SAlex Tomas struct ext4_sb_info *sbi = EXT4_SB(sb); 2409a86c6181SAlex Tomas printk(KERN_ERR "EXT4-fs: %lu blocks in %lu extents (%lu ave)\n", 2410a86c6181SAlex Tomas sbi->s_ext_blocks, sbi->s_ext_extents, 2411a86c6181SAlex Tomas sbi->s_ext_blocks / sbi->s_ext_extents); 2412a86c6181SAlex Tomas printk(KERN_ERR "EXT4-fs: extents: %lu min, %lu max, max depth %lu\n", 2413a86c6181SAlex Tomas sbi->s_ext_min, sbi->s_ext_max, sbi->s_depth_max); 2414a86c6181SAlex Tomas } 2415a86c6181SAlex Tomas #endif 2416a86c6181SAlex Tomas } 2417a86c6181SAlex Tomas 2418093a088bSAneesh Kumar K.V static void bi_complete(struct bio *bio, int error) 2419093a088bSAneesh Kumar K.V { 2420093a088bSAneesh Kumar K.V complete((struct completion *)bio->bi_private); 2421093a088bSAneesh Kumar K.V } 2422093a088bSAneesh Kumar K.V 2423093a088bSAneesh Kumar K.V /* FIXME!! we need to try to merge to left or right after zero-out */ 2424093a088bSAneesh Kumar K.V static int ext4_ext_zeroout(struct inode *inode, struct ext4_extent *ex) 2425093a088bSAneesh Kumar K.V { 2426093a088bSAneesh Kumar K.V int ret = -EIO; 2427093a088bSAneesh Kumar K.V struct bio *bio; 2428093a088bSAneesh Kumar K.V int blkbits, blocksize; 2429093a088bSAneesh Kumar K.V sector_t ee_pblock; 2430093a088bSAneesh Kumar K.V struct completion event; 2431093a088bSAneesh Kumar K.V unsigned int ee_len, len, done, offset; 2432093a088bSAneesh Kumar K.V 2433093a088bSAneesh Kumar K.V 2434093a088bSAneesh Kumar K.V blkbits = inode->i_blkbits; 2435093a088bSAneesh Kumar K.V blocksize = inode->i_sb->s_blocksize; 2436093a088bSAneesh Kumar K.V ee_len = ext4_ext_get_actual_len(ex); 2437093a088bSAneesh Kumar K.V ee_pblock = ext_pblock(ex); 2438093a088bSAneesh Kumar K.V 2439093a088bSAneesh Kumar K.V /* convert ee_pblock to 512 byte sectors */ 2440093a088bSAneesh Kumar K.V ee_pblock = ee_pblock << (blkbits - 9); 2441093a088bSAneesh Kumar K.V 2442093a088bSAneesh Kumar K.V while (ee_len > 0) { 2443093a088bSAneesh Kumar K.V 2444093a088bSAneesh Kumar K.V if (ee_len > BIO_MAX_PAGES) 2445093a088bSAneesh Kumar K.V len = BIO_MAX_PAGES; 2446093a088bSAneesh Kumar K.V else 2447093a088bSAneesh Kumar K.V len = ee_len; 2448093a088bSAneesh Kumar K.V 2449093a088bSAneesh Kumar K.V bio = bio_alloc(GFP_NOIO, len); 2450093a088bSAneesh Kumar K.V bio->bi_sector = ee_pblock; 2451093a088bSAneesh Kumar K.V bio->bi_bdev = inode->i_sb->s_bdev; 2452093a088bSAneesh Kumar K.V 2453093a088bSAneesh Kumar K.V done = 0; 2454093a088bSAneesh Kumar K.V offset = 0; 2455093a088bSAneesh Kumar K.V while (done < len) { 2456093a088bSAneesh Kumar K.V ret = bio_add_page(bio, ZERO_PAGE(0), 2457093a088bSAneesh Kumar K.V blocksize, offset); 2458093a088bSAneesh Kumar K.V if (ret != blocksize) { 2459093a088bSAneesh Kumar K.V /* 2460093a088bSAneesh Kumar K.V * We can't add any more pages because of 2461093a088bSAneesh Kumar K.V * hardware limitations. Start a new bio. 2462093a088bSAneesh Kumar K.V */ 2463093a088bSAneesh Kumar K.V break; 2464093a088bSAneesh Kumar K.V } 2465093a088bSAneesh Kumar K.V done++; 2466093a088bSAneesh Kumar K.V offset += blocksize; 2467093a088bSAneesh Kumar K.V if (offset >= PAGE_CACHE_SIZE) 2468093a088bSAneesh Kumar K.V offset = 0; 2469093a088bSAneesh Kumar K.V } 2470093a088bSAneesh Kumar K.V 2471093a088bSAneesh Kumar K.V init_completion(&event); 2472093a088bSAneesh Kumar K.V bio->bi_private = &event; 2473093a088bSAneesh Kumar K.V bio->bi_end_io = bi_complete; 2474093a088bSAneesh Kumar K.V submit_bio(WRITE, bio); 2475093a088bSAneesh Kumar K.V wait_for_completion(&event); 2476093a088bSAneesh Kumar K.V 2477093a088bSAneesh Kumar K.V if (test_bit(BIO_UPTODATE, &bio->bi_flags)) 2478093a088bSAneesh Kumar K.V ret = 0; 2479093a088bSAneesh Kumar K.V else { 2480093a088bSAneesh Kumar K.V ret = -EIO; 2481093a088bSAneesh Kumar K.V break; 2482093a088bSAneesh Kumar K.V } 2483093a088bSAneesh Kumar K.V bio_put(bio); 2484093a088bSAneesh Kumar K.V ee_len -= done; 2485093a088bSAneesh Kumar K.V ee_pblock += done << (blkbits - 9); 2486093a088bSAneesh Kumar K.V } 2487093a088bSAneesh Kumar K.V return ret; 2488093a088bSAneesh Kumar K.V } 2489093a088bSAneesh Kumar K.V 24903977c965SAneesh Kumar K.V #define EXT4_EXT_ZERO_LEN 7 249156055d3aSAmit Arora /* 249256055d3aSAmit Arora * This function is called by ext4_ext_get_blocks() if someone tries to write 249356055d3aSAmit Arora * to an uninitialized extent. It may result in splitting the uninitialized 249456055d3aSAmit Arora * extent into multiple extents (upto three - one initialized and two 249556055d3aSAmit Arora * uninitialized). 249656055d3aSAmit Arora * There are three possibilities: 249756055d3aSAmit Arora * a> There is no split required: Entire extent should be initialized 249856055d3aSAmit Arora * b> Splits in two extents: Write is happening at either end of the extent 249956055d3aSAmit Arora * c> Splits in three extents: Somone is writing in middle of the extent 250056055d3aSAmit Arora */ 2501725d26d3SAneesh Kumar K.V static int ext4_ext_convert_to_initialized(handle_t *handle, 2502725d26d3SAneesh Kumar K.V struct inode *inode, 250356055d3aSAmit Arora struct ext4_ext_path *path, 2504725d26d3SAneesh Kumar K.V ext4_lblk_t iblock, 2505498e5f24STheodore Ts'o unsigned int max_blocks) 250656055d3aSAmit Arora { 250795c3889cSAneesh Kumar K.V struct ext4_extent *ex, newex, orig_ex; 250856055d3aSAmit Arora struct ext4_extent *ex1 = NULL; 250956055d3aSAmit Arora struct ext4_extent *ex2 = NULL; 251056055d3aSAmit Arora struct ext4_extent *ex3 = NULL; 251156055d3aSAmit Arora struct ext4_extent_header *eh; 2512725d26d3SAneesh Kumar K.V ext4_lblk_t ee_block; 2513725d26d3SAneesh Kumar K.V unsigned int allocated, ee_len, depth; 251456055d3aSAmit Arora ext4_fsblk_t newblock; 251556055d3aSAmit Arora int err = 0; 251656055d3aSAmit Arora int ret = 0; 251756055d3aSAmit Arora 251856055d3aSAmit Arora depth = ext_depth(inode); 251956055d3aSAmit Arora eh = path[depth].p_hdr; 252056055d3aSAmit Arora ex = path[depth].p_ext; 252156055d3aSAmit Arora ee_block = le32_to_cpu(ex->ee_block); 252256055d3aSAmit Arora ee_len = ext4_ext_get_actual_len(ex); 252356055d3aSAmit Arora allocated = ee_len - (iblock - ee_block); 252456055d3aSAmit Arora newblock = iblock - ee_block + ext_pblock(ex); 252556055d3aSAmit Arora ex2 = ex; 252695c3889cSAneesh Kumar K.V orig_ex.ee_block = ex->ee_block; 252795c3889cSAneesh Kumar K.V orig_ex.ee_len = cpu_to_le16(ee_len); 252895c3889cSAneesh Kumar K.V ext4_ext_store_pblock(&orig_ex, ext_pblock(ex)); 252956055d3aSAmit Arora 25309df5643aSAneesh Kumar K.V err = ext4_ext_get_access(handle, inode, path + depth); 25319df5643aSAneesh Kumar K.V if (err) 25329df5643aSAneesh Kumar K.V goto out; 25333977c965SAneesh Kumar K.V /* If extent has less than 2*EXT4_EXT_ZERO_LEN zerout directly */ 25343977c965SAneesh Kumar K.V if (ee_len <= 2*EXT4_EXT_ZERO_LEN) { 25353977c965SAneesh Kumar K.V err = ext4_ext_zeroout(inode, &orig_ex); 25363977c965SAneesh Kumar K.V if (err) 25373977c965SAneesh Kumar K.V goto fix_extent_len; 25383977c965SAneesh Kumar K.V /* update the extent length and mark as initialized */ 25393977c965SAneesh Kumar K.V ex->ee_block = orig_ex.ee_block; 25403977c965SAneesh Kumar K.V ex->ee_len = orig_ex.ee_len; 25413977c965SAneesh Kumar K.V ext4_ext_store_pblock(ex, ext_pblock(&orig_ex)); 25423977c965SAneesh Kumar K.V ext4_ext_dirty(handle, inode, path + depth); 2543161e7b7cSAneesh Kumar K.V /* zeroed the full extent */ 2544161e7b7cSAneesh Kumar K.V return allocated; 25453977c965SAneesh Kumar K.V } 25469df5643aSAneesh Kumar K.V 254756055d3aSAmit Arora /* ex1: ee_block to iblock - 1 : uninitialized */ 254856055d3aSAmit Arora if (iblock > ee_block) { 254956055d3aSAmit Arora ex1 = ex; 255056055d3aSAmit Arora ex1->ee_len = cpu_to_le16(iblock - ee_block); 255156055d3aSAmit Arora ext4_ext_mark_uninitialized(ex1); 255256055d3aSAmit Arora ex2 = &newex; 255356055d3aSAmit Arora } 255456055d3aSAmit Arora /* 255556055d3aSAmit Arora * for sanity, update the length of the ex2 extent before 255656055d3aSAmit Arora * we insert ex3, if ex1 is NULL. This is to avoid temporary 255756055d3aSAmit Arora * overlap of blocks. 255856055d3aSAmit Arora */ 255956055d3aSAmit Arora if (!ex1 && allocated > max_blocks) 256056055d3aSAmit Arora ex2->ee_len = cpu_to_le16(max_blocks); 256156055d3aSAmit Arora /* ex3: to ee_block + ee_len : uninitialised */ 256256055d3aSAmit Arora if (allocated > max_blocks) { 256356055d3aSAmit Arora unsigned int newdepth; 25643977c965SAneesh Kumar K.V /* If extent has less than EXT4_EXT_ZERO_LEN zerout directly */ 25653977c965SAneesh Kumar K.V if (allocated <= EXT4_EXT_ZERO_LEN) { 2566d03856bdSAneesh Kumar K.V /* 2567d03856bdSAneesh Kumar K.V * iblock == ee_block is handled by the zerouout 2568d03856bdSAneesh Kumar K.V * at the beginning. 2569d03856bdSAneesh Kumar K.V * Mark first half uninitialized. 25703977c965SAneesh Kumar K.V * Mark second half initialized and zero out the 25713977c965SAneesh Kumar K.V * initialized extent 25723977c965SAneesh Kumar K.V */ 25733977c965SAneesh Kumar K.V ex->ee_block = orig_ex.ee_block; 25743977c965SAneesh Kumar K.V ex->ee_len = cpu_to_le16(ee_len - allocated); 25753977c965SAneesh Kumar K.V ext4_ext_mark_uninitialized(ex); 25763977c965SAneesh Kumar K.V ext4_ext_store_pblock(ex, ext_pblock(&orig_ex)); 25773977c965SAneesh Kumar K.V ext4_ext_dirty(handle, inode, path + depth); 25783977c965SAneesh Kumar K.V 25793977c965SAneesh Kumar K.V ex3 = &newex; 25803977c965SAneesh Kumar K.V ex3->ee_block = cpu_to_le32(iblock); 25813977c965SAneesh Kumar K.V ext4_ext_store_pblock(ex3, newblock); 25823977c965SAneesh Kumar K.V ex3->ee_len = cpu_to_le16(allocated); 25830031462bSMingming Cao err = ext4_ext_insert_extent(handle, inode, path, 25840031462bSMingming Cao ex3, 0); 25853977c965SAneesh Kumar K.V if (err == -ENOSPC) { 25863977c965SAneesh Kumar K.V err = ext4_ext_zeroout(inode, &orig_ex); 25873977c965SAneesh Kumar K.V if (err) 25883977c965SAneesh Kumar K.V goto fix_extent_len; 25893977c965SAneesh Kumar K.V ex->ee_block = orig_ex.ee_block; 25903977c965SAneesh Kumar K.V ex->ee_len = orig_ex.ee_len; 25913977c965SAneesh Kumar K.V ext4_ext_store_pblock(ex, ext_pblock(&orig_ex)); 25923977c965SAneesh Kumar K.V ext4_ext_dirty(handle, inode, path + depth); 2593d03856bdSAneesh Kumar K.V /* blocks available from iblock */ 2594161e7b7cSAneesh Kumar K.V return allocated; 25953977c965SAneesh Kumar K.V 25963977c965SAneesh Kumar K.V } else if (err) 25973977c965SAneesh Kumar K.V goto fix_extent_len; 25983977c965SAneesh Kumar K.V 2599161e7b7cSAneesh Kumar K.V /* 2600161e7b7cSAneesh Kumar K.V * We need to zero out the second half because 2601161e7b7cSAneesh Kumar K.V * an fallocate request can update file size and 2602161e7b7cSAneesh Kumar K.V * converting the second half to initialized extent 2603161e7b7cSAneesh Kumar K.V * implies that we can leak some junk data to user 2604161e7b7cSAneesh Kumar K.V * space. 2605161e7b7cSAneesh Kumar K.V */ 2606161e7b7cSAneesh Kumar K.V err = ext4_ext_zeroout(inode, ex3); 2607161e7b7cSAneesh Kumar K.V if (err) { 2608161e7b7cSAneesh Kumar K.V /* 2609161e7b7cSAneesh Kumar K.V * We should actually mark the 2610161e7b7cSAneesh Kumar K.V * second half as uninit and return error 2611161e7b7cSAneesh Kumar K.V * Insert would have changed the extent 2612161e7b7cSAneesh Kumar K.V */ 2613161e7b7cSAneesh Kumar K.V depth = ext_depth(inode); 2614161e7b7cSAneesh Kumar K.V ext4_ext_drop_refs(path); 2615161e7b7cSAneesh Kumar K.V path = ext4_ext_find_extent(inode, 2616161e7b7cSAneesh Kumar K.V iblock, path); 2617161e7b7cSAneesh Kumar K.V if (IS_ERR(path)) { 2618161e7b7cSAneesh Kumar K.V err = PTR_ERR(path); 2619161e7b7cSAneesh Kumar K.V return err; 2620161e7b7cSAneesh Kumar K.V } 2621d03856bdSAneesh Kumar K.V /* get the second half extent details */ 2622161e7b7cSAneesh Kumar K.V ex = path[depth].p_ext; 2623161e7b7cSAneesh Kumar K.V err = ext4_ext_get_access(handle, inode, 2624161e7b7cSAneesh Kumar K.V path + depth); 2625161e7b7cSAneesh Kumar K.V if (err) 2626161e7b7cSAneesh Kumar K.V return err; 2627161e7b7cSAneesh Kumar K.V ext4_ext_mark_uninitialized(ex); 2628161e7b7cSAneesh Kumar K.V ext4_ext_dirty(handle, inode, path + depth); 2629161e7b7cSAneesh Kumar K.V return err; 2630161e7b7cSAneesh Kumar K.V } 2631161e7b7cSAneesh Kumar K.V 2632161e7b7cSAneesh Kumar K.V /* zeroed the second half */ 26333977c965SAneesh Kumar K.V return allocated; 26343977c965SAneesh Kumar K.V } 263556055d3aSAmit Arora ex3 = &newex; 263656055d3aSAmit Arora ex3->ee_block = cpu_to_le32(iblock + max_blocks); 263756055d3aSAmit Arora ext4_ext_store_pblock(ex3, newblock + max_blocks); 263856055d3aSAmit Arora ex3->ee_len = cpu_to_le16(allocated - max_blocks); 263956055d3aSAmit Arora ext4_ext_mark_uninitialized(ex3); 26400031462bSMingming Cao err = ext4_ext_insert_extent(handle, inode, path, ex3, 0); 2641093a088bSAneesh Kumar K.V if (err == -ENOSPC) { 2642093a088bSAneesh Kumar K.V err = ext4_ext_zeroout(inode, &orig_ex); 2643093a088bSAneesh Kumar K.V if (err) 2644093a088bSAneesh Kumar K.V goto fix_extent_len; 2645093a088bSAneesh Kumar K.V /* update the extent length and mark as initialized */ 264695c3889cSAneesh Kumar K.V ex->ee_block = orig_ex.ee_block; 264795c3889cSAneesh Kumar K.V ex->ee_len = orig_ex.ee_len; 264895c3889cSAneesh Kumar K.V ext4_ext_store_pblock(ex, ext_pblock(&orig_ex)); 264995c3889cSAneesh Kumar K.V ext4_ext_dirty(handle, inode, path + depth); 2650161e7b7cSAneesh Kumar K.V /* zeroed the full extent */ 2651d03856bdSAneesh Kumar K.V /* blocks available from iblock */ 2652161e7b7cSAneesh Kumar K.V return allocated; 2653093a088bSAneesh Kumar K.V 2654093a088bSAneesh Kumar K.V } else if (err) 2655093a088bSAneesh Kumar K.V goto fix_extent_len; 265656055d3aSAmit Arora /* 265756055d3aSAmit Arora * The depth, and hence eh & ex might change 265856055d3aSAmit Arora * as part of the insert above. 265956055d3aSAmit Arora */ 266056055d3aSAmit Arora newdepth = ext_depth(inode); 266195c3889cSAneesh Kumar K.V /* 266273ac36eaSColy Li * update the extent length after successful insert of the 266395c3889cSAneesh Kumar K.V * split extent 266495c3889cSAneesh Kumar K.V */ 266595c3889cSAneesh Kumar K.V orig_ex.ee_len = cpu_to_le16(ee_len - 266695c3889cSAneesh Kumar K.V ext4_ext_get_actual_len(ex3)); 266756055d3aSAmit Arora depth = newdepth; 2668b35905c1SAneesh Kumar K.V ext4_ext_drop_refs(path); 2669b35905c1SAneesh Kumar K.V path = ext4_ext_find_extent(inode, iblock, path); 267056055d3aSAmit Arora if (IS_ERR(path)) { 267156055d3aSAmit Arora err = PTR_ERR(path); 267256055d3aSAmit Arora goto out; 267356055d3aSAmit Arora } 267456055d3aSAmit Arora eh = path[depth].p_hdr; 267556055d3aSAmit Arora ex = path[depth].p_ext; 267656055d3aSAmit Arora if (ex2 != &newex) 267756055d3aSAmit Arora ex2 = ex; 26789df5643aSAneesh Kumar K.V 26799df5643aSAneesh Kumar K.V err = ext4_ext_get_access(handle, inode, path + depth); 26809df5643aSAneesh Kumar K.V if (err) 26819df5643aSAneesh Kumar K.V goto out; 2682d03856bdSAneesh Kumar K.V 268356055d3aSAmit Arora allocated = max_blocks; 26843977c965SAneesh Kumar K.V 26853977c965SAneesh Kumar K.V /* If extent has less than EXT4_EXT_ZERO_LEN and we are trying 26863977c965SAneesh Kumar K.V * to insert a extent in the middle zerout directly 26873977c965SAneesh Kumar K.V * otherwise give the extent a chance to merge to left 26883977c965SAneesh Kumar K.V */ 26893977c965SAneesh Kumar K.V if (le16_to_cpu(orig_ex.ee_len) <= EXT4_EXT_ZERO_LEN && 26903977c965SAneesh Kumar K.V iblock != ee_block) { 26913977c965SAneesh Kumar K.V err = ext4_ext_zeroout(inode, &orig_ex); 26923977c965SAneesh Kumar K.V if (err) 26933977c965SAneesh Kumar K.V goto fix_extent_len; 26943977c965SAneesh Kumar K.V /* update the extent length and mark as initialized */ 26953977c965SAneesh Kumar K.V ex->ee_block = orig_ex.ee_block; 26963977c965SAneesh Kumar K.V ex->ee_len = orig_ex.ee_len; 26973977c965SAneesh Kumar K.V ext4_ext_store_pblock(ex, ext_pblock(&orig_ex)); 26983977c965SAneesh Kumar K.V ext4_ext_dirty(handle, inode, path + depth); 2699161e7b7cSAneesh Kumar K.V /* zero out the first half */ 2700d03856bdSAneesh Kumar K.V /* blocks available from iblock */ 2701161e7b7cSAneesh Kumar K.V return allocated; 27023977c965SAneesh Kumar K.V } 270356055d3aSAmit Arora } 270456055d3aSAmit Arora /* 270556055d3aSAmit Arora * If there was a change of depth as part of the 270656055d3aSAmit Arora * insertion of ex3 above, we need to update the length 270756055d3aSAmit Arora * of the ex1 extent again here 270856055d3aSAmit Arora */ 270956055d3aSAmit Arora if (ex1 && ex1 != ex) { 271056055d3aSAmit Arora ex1 = ex; 271156055d3aSAmit Arora ex1->ee_len = cpu_to_le16(iblock - ee_block); 271256055d3aSAmit Arora ext4_ext_mark_uninitialized(ex1); 271356055d3aSAmit Arora ex2 = &newex; 271456055d3aSAmit Arora } 271556055d3aSAmit Arora /* ex2: iblock to iblock + maxblocks-1 : initialised */ 271656055d3aSAmit Arora ex2->ee_block = cpu_to_le32(iblock); 271756055d3aSAmit Arora ext4_ext_store_pblock(ex2, newblock); 271856055d3aSAmit Arora ex2->ee_len = cpu_to_le16(allocated); 271956055d3aSAmit Arora if (ex2 != ex) 272056055d3aSAmit Arora goto insert; 272156055d3aSAmit Arora /* 272256055d3aSAmit Arora * New (initialized) extent starts from the first block 272356055d3aSAmit Arora * in the current extent. i.e., ex2 == ex 272456055d3aSAmit Arora * We have to see if it can be merged with the extent 272556055d3aSAmit Arora * on the left. 272656055d3aSAmit Arora */ 272756055d3aSAmit Arora if (ex2 > EXT_FIRST_EXTENT(eh)) { 272856055d3aSAmit Arora /* 272956055d3aSAmit Arora * To merge left, pass "ex2 - 1" to try_to_merge(), 273056055d3aSAmit Arora * since it merges towards right _only_. 273156055d3aSAmit Arora */ 273256055d3aSAmit Arora ret = ext4_ext_try_to_merge(inode, path, ex2 - 1); 273356055d3aSAmit Arora if (ret) { 273456055d3aSAmit Arora err = ext4_ext_correct_indexes(handle, inode, path); 273556055d3aSAmit Arora if (err) 273656055d3aSAmit Arora goto out; 273756055d3aSAmit Arora depth = ext_depth(inode); 273856055d3aSAmit Arora ex2--; 273956055d3aSAmit Arora } 274056055d3aSAmit Arora } 274156055d3aSAmit Arora /* 274256055d3aSAmit Arora * Try to Merge towards right. This might be required 274356055d3aSAmit Arora * only when the whole extent is being written to. 274456055d3aSAmit Arora * i.e. ex2 == ex and ex3 == NULL. 274556055d3aSAmit Arora */ 274656055d3aSAmit Arora if (!ex3) { 274756055d3aSAmit Arora ret = ext4_ext_try_to_merge(inode, path, ex2); 274856055d3aSAmit Arora if (ret) { 274956055d3aSAmit Arora err = ext4_ext_correct_indexes(handle, inode, path); 275056055d3aSAmit Arora if (err) 275156055d3aSAmit Arora goto out; 275256055d3aSAmit Arora } 275356055d3aSAmit Arora } 275456055d3aSAmit Arora /* Mark modified extent as dirty */ 275556055d3aSAmit Arora err = ext4_ext_dirty(handle, inode, path + depth); 275656055d3aSAmit Arora goto out; 275756055d3aSAmit Arora insert: 27580031462bSMingming Cao err = ext4_ext_insert_extent(handle, inode, path, &newex, 0); 2759093a088bSAneesh Kumar K.V if (err == -ENOSPC) { 2760093a088bSAneesh Kumar K.V err = ext4_ext_zeroout(inode, &orig_ex); 2761093a088bSAneesh Kumar K.V if (err) 2762093a088bSAneesh Kumar K.V goto fix_extent_len; 2763093a088bSAneesh Kumar K.V /* update the extent length and mark as initialized */ 2764093a088bSAneesh Kumar K.V ex->ee_block = orig_ex.ee_block; 2765093a088bSAneesh Kumar K.V ex->ee_len = orig_ex.ee_len; 2766093a088bSAneesh Kumar K.V ext4_ext_store_pblock(ex, ext_pblock(&orig_ex)); 2767093a088bSAneesh Kumar K.V ext4_ext_dirty(handle, inode, path + depth); 2768161e7b7cSAneesh Kumar K.V /* zero out the first half */ 2769161e7b7cSAneesh Kumar K.V return allocated; 2770093a088bSAneesh Kumar K.V } else if (err) 2771093a088bSAneesh Kumar K.V goto fix_extent_len; 2772093a088bSAneesh Kumar K.V out: 2773553f9008SMingming ext4_ext_show_leaf(inode, path); 2774093a088bSAneesh Kumar K.V return err ? err : allocated; 2775093a088bSAneesh Kumar K.V 2776093a088bSAneesh Kumar K.V fix_extent_len: 277795c3889cSAneesh Kumar K.V ex->ee_block = orig_ex.ee_block; 277895c3889cSAneesh Kumar K.V ex->ee_len = orig_ex.ee_len; 277995c3889cSAneesh Kumar K.V ext4_ext_store_pblock(ex, ext_pblock(&orig_ex)); 278095c3889cSAneesh Kumar K.V ext4_ext_mark_uninitialized(ex); 278195c3889cSAneesh Kumar K.V ext4_ext_dirty(handle, inode, path + depth); 2782093a088bSAneesh Kumar K.V return err; 278356055d3aSAmit Arora } 278456055d3aSAmit Arora 2785c278bfecSAneesh Kumar K.V /* 27860031462bSMingming Cao * This function is called by ext4_ext_get_blocks() from 27870031462bSMingming Cao * ext4_get_blocks_dio_write() when DIO to write 27880031462bSMingming Cao * to an uninitialized extent. 27890031462bSMingming Cao * 27900031462bSMingming Cao * Writing to an uninitized extent may result in splitting the uninitialized 27910031462bSMingming Cao * extent into multiple /intialized unintialized extents (up to three) 27920031462bSMingming Cao * There are three possibilities: 27930031462bSMingming Cao * a> There is no split required: Entire extent should be uninitialized 27940031462bSMingming Cao * b> Splits in two extents: Write is happening at either end of the extent 27950031462bSMingming Cao * c> Splits in three extents: Somone is writing in middle of the extent 27960031462bSMingming Cao * 27970031462bSMingming Cao * One of more index blocks maybe needed if the extent tree grow after 27980031462bSMingming Cao * the unintialized extent split. To prevent ENOSPC occur at the IO 27990031462bSMingming Cao * complete, we need to split the uninitialized extent before DIO submit 28000031462bSMingming Cao * the IO. The uninitilized extent called at this time will be split 28010031462bSMingming Cao * into three uninitialized extent(at most). After IO complete, the part 28020031462bSMingming Cao * being filled will be convert to initialized by the end_io callback function 28030031462bSMingming Cao * via ext4_convert_unwritten_extents(). 2804ba230c3fSMingming * 2805ba230c3fSMingming * Returns the size of uninitialized extent to be written on success. 28060031462bSMingming Cao */ 28070031462bSMingming Cao static int ext4_split_unwritten_extents(handle_t *handle, 28080031462bSMingming Cao struct inode *inode, 28090031462bSMingming Cao struct ext4_ext_path *path, 28100031462bSMingming Cao ext4_lblk_t iblock, 28110031462bSMingming Cao unsigned int max_blocks, 28120031462bSMingming Cao int flags) 28130031462bSMingming Cao { 28140031462bSMingming Cao struct ext4_extent *ex, newex, orig_ex; 28150031462bSMingming Cao struct ext4_extent *ex1 = NULL; 28160031462bSMingming Cao struct ext4_extent *ex2 = NULL; 28170031462bSMingming Cao struct ext4_extent *ex3 = NULL; 28180031462bSMingming Cao struct ext4_extent_header *eh; 28190031462bSMingming Cao ext4_lblk_t ee_block; 28200031462bSMingming Cao unsigned int allocated, ee_len, depth; 28210031462bSMingming Cao ext4_fsblk_t newblock; 28220031462bSMingming Cao int err = 0; 28230031462bSMingming Cao 28240031462bSMingming Cao ext_debug("ext4_split_unwritten_extents: inode %lu," 28250031462bSMingming Cao "iblock %llu, max_blocks %u\n", inode->i_ino, 28260031462bSMingming Cao (unsigned long long)iblock, max_blocks); 28270031462bSMingming Cao depth = ext_depth(inode); 28280031462bSMingming Cao eh = path[depth].p_hdr; 28290031462bSMingming Cao ex = path[depth].p_ext; 28300031462bSMingming Cao ee_block = le32_to_cpu(ex->ee_block); 28310031462bSMingming Cao ee_len = ext4_ext_get_actual_len(ex); 28320031462bSMingming Cao allocated = ee_len - (iblock - ee_block); 28330031462bSMingming Cao newblock = iblock - ee_block + ext_pblock(ex); 28340031462bSMingming Cao ex2 = ex; 28350031462bSMingming Cao orig_ex.ee_block = ex->ee_block; 28360031462bSMingming Cao orig_ex.ee_len = cpu_to_le16(ee_len); 28370031462bSMingming Cao ext4_ext_store_pblock(&orig_ex, ext_pblock(ex)); 28380031462bSMingming Cao 28390031462bSMingming Cao /* 2840ba230c3fSMingming * If the uninitialized extent begins at the same logical 2841ba230c3fSMingming * block where the write begins, and the write completely 2842ba230c3fSMingming * covers the extent, then we don't need to split it. 28430031462bSMingming Cao */ 2844ba230c3fSMingming if ((iblock == ee_block) && (allocated <= max_blocks)) 2845ba230c3fSMingming return allocated; 28460031462bSMingming Cao 28470031462bSMingming Cao err = ext4_ext_get_access(handle, inode, path + depth); 28480031462bSMingming Cao if (err) 28490031462bSMingming Cao goto out; 28500031462bSMingming Cao /* ex1: ee_block to iblock - 1 : uninitialized */ 28510031462bSMingming Cao if (iblock > ee_block) { 28520031462bSMingming Cao ex1 = ex; 28530031462bSMingming Cao ex1->ee_len = cpu_to_le16(iblock - ee_block); 28540031462bSMingming Cao ext4_ext_mark_uninitialized(ex1); 28550031462bSMingming Cao ex2 = &newex; 28560031462bSMingming Cao } 28570031462bSMingming Cao /* 28580031462bSMingming Cao * for sanity, update the length of the ex2 extent before 28590031462bSMingming Cao * we insert ex3, if ex1 is NULL. This is to avoid temporary 28600031462bSMingming Cao * overlap of blocks. 28610031462bSMingming Cao */ 28620031462bSMingming Cao if (!ex1 && allocated > max_blocks) 28630031462bSMingming Cao ex2->ee_len = cpu_to_le16(max_blocks); 28640031462bSMingming Cao /* ex3: to ee_block + ee_len : uninitialised */ 28650031462bSMingming Cao if (allocated > max_blocks) { 28660031462bSMingming Cao unsigned int newdepth; 28670031462bSMingming Cao ex3 = &newex; 28680031462bSMingming Cao ex3->ee_block = cpu_to_le32(iblock + max_blocks); 28690031462bSMingming Cao ext4_ext_store_pblock(ex3, newblock + max_blocks); 28700031462bSMingming Cao ex3->ee_len = cpu_to_le16(allocated - max_blocks); 28710031462bSMingming Cao ext4_ext_mark_uninitialized(ex3); 28720031462bSMingming Cao err = ext4_ext_insert_extent(handle, inode, path, ex3, flags); 28730031462bSMingming Cao if (err == -ENOSPC) { 28740031462bSMingming Cao err = ext4_ext_zeroout(inode, &orig_ex); 28750031462bSMingming Cao if (err) 28760031462bSMingming Cao goto fix_extent_len; 28770031462bSMingming Cao /* update the extent length and mark as initialized */ 28780031462bSMingming Cao ex->ee_block = orig_ex.ee_block; 28790031462bSMingming Cao ex->ee_len = orig_ex.ee_len; 28800031462bSMingming Cao ext4_ext_store_pblock(ex, ext_pblock(&orig_ex)); 28810031462bSMingming Cao ext4_ext_dirty(handle, inode, path + depth); 28820031462bSMingming Cao /* zeroed the full extent */ 28830031462bSMingming Cao /* blocks available from iblock */ 28840031462bSMingming Cao return allocated; 28850031462bSMingming Cao 28860031462bSMingming Cao } else if (err) 28870031462bSMingming Cao goto fix_extent_len; 28880031462bSMingming Cao /* 28890031462bSMingming Cao * The depth, and hence eh & ex might change 28900031462bSMingming Cao * as part of the insert above. 28910031462bSMingming Cao */ 28920031462bSMingming Cao newdepth = ext_depth(inode); 28930031462bSMingming Cao /* 28940031462bSMingming Cao * update the extent length after successful insert of the 28950031462bSMingming Cao * split extent 28960031462bSMingming Cao */ 28970031462bSMingming Cao orig_ex.ee_len = cpu_to_le16(ee_len - 28980031462bSMingming Cao ext4_ext_get_actual_len(ex3)); 28990031462bSMingming Cao depth = newdepth; 29000031462bSMingming Cao ext4_ext_drop_refs(path); 29010031462bSMingming Cao path = ext4_ext_find_extent(inode, iblock, path); 29020031462bSMingming Cao if (IS_ERR(path)) { 29030031462bSMingming Cao err = PTR_ERR(path); 29040031462bSMingming Cao goto out; 29050031462bSMingming Cao } 29060031462bSMingming Cao eh = path[depth].p_hdr; 29070031462bSMingming Cao ex = path[depth].p_ext; 29080031462bSMingming Cao if (ex2 != &newex) 29090031462bSMingming Cao ex2 = ex; 29100031462bSMingming Cao 29110031462bSMingming Cao err = ext4_ext_get_access(handle, inode, path + depth); 29120031462bSMingming Cao if (err) 29130031462bSMingming Cao goto out; 29140031462bSMingming Cao 29150031462bSMingming Cao allocated = max_blocks; 29160031462bSMingming Cao } 29170031462bSMingming Cao /* 29180031462bSMingming Cao * If there was a change of depth as part of the 29190031462bSMingming Cao * insertion of ex3 above, we need to update the length 29200031462bSMingming Cao * of the ex1 extent again here 29210031462bSMingming Cao */ 29220031462bSMingming Cao if (ex1 && ex1 != ex) { 29230031462bSMingming Cao ex1 = ex; 29240031462bSMingming Cao ex1->ee_len = cpu_to_le16(iblock - ee_block); 29250031462bSMingming Cao ext4_ext_mark_uninitialized(ex1); 29260031462bSMingming Cao ex2 = &newex; 29270031462bSMingming Cao } 29280031462bSMingming Cao /* 29290031462bSMingming Cao * ex2: iblock to iblock + maxblocks-1 : to be direct IO written, 29300031462bSMingming Cao * uninitialised still. 29310031462bSMingming Cao */ 29320031462bSMingming Cao ex2->ee_block = cpu_to_le32(iblock); 29330031462bSMingming Cao ext4_ext_store_pblock(ex2, newblock); 29340031462bSMingming Cao ex2->ee_len = cpu_to_le16(allocated); 29350031462bSMingming Cao ext4_ext_mark_uninitialized(ex2); 29360031462bSMingming Cao if (ex2 != ex) 29370031462bSMingming Cao goto insert; 29380031462bSMingming Cao /* Mark modified extent as dirty */ 29390031462bSMingming Cao err = ext4_ext_dirty(handle, inode, path + depth); 29400031462bSMingming Cao ext_debug("out here\n"); 29410031462bSMingming Cao goto out; 29420031462bSMingming Cao insert: 29430031462bSMingming Cao err = ext4_ext_insert_extent(handle, inode, path, &newex, flags); 29440031462bSMingming Cao if (err == -ENOSPC) { 29450031462bSMingming Cao err = ext4_ext_zeroout(inode, &orig_ex); 29460031462bSMingming Cao if (err) 29470031462bSMingming Cao goto fix_extent_len; 29480031462bSMingming Cao /* update the extent length and mark as initialized */ 29490031462bSMingming Cao ex->ee_block = orig_ex.ee_block; 29500031462bSMingming Cao ex->ee_len = orig_ex.ee_len; 29510031462bSMingming Cao ext4_ext_store_pblock(ex, ext_pblock(&orig_ex)); 29520031462bSMingming Cao ext4_ext_dirty(handle, inode, path + depth); 29530031462bSMingming Cao /* zero out the first half */ 29540031462bSMingming Cao return allocated; 29550031462bSMingming Cao } else if (err) 29560031462bSMingming Cao goto fix_extent_len; 29570031462bSMingming Cao out: 29580031462bSMingming Cao ext4_ext_show_leaf(inode, path); 29590031462bSMingming Cao return err ? err : allocated; 29600031462bSMingming Cao 29610031462bSMingming Cao fix_extent_len: 29620031462bSMingming Cao ex->ee_block = orig_ex.ee_block; 29630031462bSMingming Cao ex->ee_len = orig_ex.ee_len; 29640031462bSMingming Cao ext4_ext_store_pblock(ex, ext_pblock(&orig_ex)); 29650031462bSMingming Cao ext4_ext_mark_uninitialized(ex); 29660031462bSMingming Cao ext4_ext_dirty(handle, inode, path + depth); 29670031462bSMingming Cao return err; 29680031462bSMingming Cao } 29690031462bSMingming Cao static int ext4_convert_unwritten_extents_dio(handle_t *handle, 29700031462bSMingming Cao struct inode *inode, 29710031462bSMingming Cao struct ext4_ext_path *path) 29720031462bSMingming Cao { 29730031462bSMingming Cao struct ext4_extent *ex; 29740031462bSMingming Cao struct ext4_extent_header *eh; 29750031462bSMingming Cao int depth; 29760031462bSMingming Cao int err = 0; 29770031462bSMingming Cao int ret = 0; 29780031462bSMingming Cao 29790031462bSMingming Cao depth = ext_depth(inode); 29800031462bSMingming Cao eh = path[depth].p_hdr; 29810031462bSMingming Cao ex = path[depth].p_ext; 29820031462bSMingming Cao 29830031462bSMingming Cao err = ext4_ext_get_access(handle, inode, path + depth); 29840031462bSMingming Cao if (err) 29850031462bSMingming Cao goto out; 29860031462bSMingming Cao /* first mark the extent as initialized */ 29870031462bSMingming Cao ext4_ext_mark_initialized(ex); 29880031462bSMingming Cao 29890031462bSMingming Cao /* 29900031462bSMingming Cao * We have to see if it can be merged with the extent 29910031462bSMingming Cao * on the left. 29920031462bSMingming Cao */ 29930031462bSMingming Cao if (ex > EXT_FIRST_EXTENT(eh)) { 29940031462bSMingming Cao /* 29950031462bSMingming Cao * To merge left, pass "ex - 1" to try_to_merge(), 29960031462bSMingming Cao * since it merges towards right _only_. 29970031462bSMingming Cao */ 29980031462bSMingming Cao ret = ext4_ext_try_to_merge(inode, path, ex - 1); 29990031462bSMingming Cao if (ret) { 30000031462bSMingming Cao err = ext4_ext_correct_indexes(handle, inode, path); 30010031462bSMingming Cao if (err) 30020031462bSMingming Cao goto out; 30030031462bSMingming Cao depth = ext_depth(inode); 30040031462bSMingming Cao ex--; 30050031462bSMingming Cao } 30060031462bSMingming Cao } 30070031462bSMingming Cao /* 30080031462bSMingming Cao * Try to Merge towards right. 30090031462bSMingming Cao */ 30100031462bSMingming Cao ret = ext4_ext_try_to_merge(inode, path, ex); 30110031462bSMingming Cao if (ret) { 30120031462bSMingming Cao err = ext4_ext_correct_indexes(handle, inode, path); 30130031462bSMingming Cao if (err) 30140031462bSMingming Cao goto out; 30150031462bSMingming Cao depth = ext_depth(inode); 30160031462bSMingming Cao } 30170031462bSMingming Cao /* Mark modified extent as dirty */ 30180031462bSMingming Cao err = ext4_ext_dirty(handle, inode, path + depth); 30190031462bSMingming Cao out: 30200031462bSMingming Cao ext4_ext_show_leaf(inode, path); 30210031462bSMingming Cao return err; 30220031462bSMingming Cao } 30230031462bSMingming Cao 30240031462bSMingming Cao static int 30250031462bSMingming Cao ext4_ext_handle_uninitialized_extents(handle_t *handle, struct inode *inode, 30260031462bSMingming Cao ext4_lblk_t iblock, unsigned int max_blocks, 30270031462bSMingming Cao struct ext4_ext_path *path, int flags, 30280031462bSMingming Cao unsigned int allocated, struct buffer_head *bh_result, 30290031462bSMingming Cao ext4_fsblk_t newblock) 30300031462bSMingming Cao { 30310031462bSMingming Cao int ret = 0; 30320031462bSMingming Cao int err = 0; 30338d5d02e6SMingming Cao ext4_io_end_t *io = EXT4_I(inode)->cur_aio_dio; 30340031462bSMingming Cao 30350031462bSMingming Cao ext_debug("ext4_ext_handle_uninitialized_extents: inode %lu, logical" 30360031462bSMingming Cao "block %llu, max_blocks %u, flags %d, allocated %u", 30370031462bSMingming Cao inode->i_ino, (unsigned long long)iblock, max_blocks, 30380031462bSMingming Cao flags, allocated); 30390031462bSMingming Cao ext4_ext_show_leaf(inode, path); 30400031462bSMingming Cao 30410031462bSMingming Cao /* DIO get_block() before submit the IO, split the extent */ 30420031462bSMingming Cao if (flags == EXT4_GET_BLOCKS_DIO_CREATE_EXT) { 30430031462bSMingming Cao ret = ext4_split_unwritten_extents(handle, 30440031462bSMingming Cao inode, path, iblock, 30450031462bSMingming Cao max_blocks, flags); 30465f524950SMingming /* 30475f524950SMingming * Flag the inode(non aio case) or end_io struct (aio case) 30485f524950SMingming * that this IO needs to convertion to written when IO is 30495f524950SMingming * completed 30505f524950SMingming */ 30518d5d02e6SMingming Cao if (io) 30528d5d02e6SMingming Cao io->flag = DIO_AIO_UNWRITTEN; 30535f524950SMingming else 30545f524950SMingming EXT4_I(inode)->i_state |= EXT4_STATE_DIO_UNWRITTEN; 30550031462bSMingming Cao goto out; 30560031462bSMingming Cao } 30575f524950SMingming /* async DIO end_io complete, convert the filled extent to written */ 30580031462bSMingming Cao if (flags == EXT4_GET_BLOCKS_DIO_CONVERT_EXT) { 30590031462bSMingming Cao ret = ext4_convert_unwritten_extents_dio(handle, inode, 30600031462bSMingming Cao path); 30610031462bSMingming Cao goto out2; 30620031462bSMingming Cao } 30630031462bSMingming Cao /* buffered IO case */ 30640031462bSMingming Cao /* 30650031462bSMingming Cao * repeat fallocate creation request 30660031462bSMingming Cao * we already have an unwritten extent 30670031462bSMingming Cao */ 30680031462bSMingming Cao if (flags & EXT4_GET_BLOCKS_UNINIT_EXT) 30690031462bSMingming Cao goto map_out; 30700031462bSMingming Cao 30710031462bSMingming Cao /* buffered READ or buffered write_begin() lookup */ 30720031462bSMingming Cao if ((flags & EXT4_GET_BLOCKS_CREATE) == 0) { 30730031462bSMingming Cao /* 30740031462bSMingming Cao * We have blocks reserved already. We 30750031462bSMingming Cao * return allocated blocks so that delalloc 30760031462bSMingming Cao * won't do block reservation for us. But 30770031462bSMingming Cao * the buffer head will be unmapped so that 30780031462bSMingming Cao * a read from the block returns 0s. 30790031462bSMingming Cao */ 30800031462bSMingming Cao set_buffer_unwritten(bh_result); 30810031462bSMingming Cao goto out1; 30820031462bSMingming Cao } 30830031462bSMingming Cao 30840031462bSMingming Cao /* buffered write, writepage time, convert*/ 30850031462bSMingming Cao ret = ext4_ext_convert_to_initialized(handle, inode, 30860031462bSMingming Cao path, iblock, 30870031462bSMingming Cao max_blocks); 30880031462bSMingming Cao out: 30890031462bSMingming Cao if (ret <= 0) { 30900031462bSMingming Cao err = ret; 30910031462bSMingming Cao goto out2; 30920031462bSMingming Cao } else 30930031462bSMingming Cao allocated = ret; 30940031462bSMingming Cao set_buffer_new(bh_result); 30950031462bSMingming Cao map_out: 30960031462bSMingming Cao set_buffer_mapped(bh_result); 30970031462bSMingming Cao out1: 30980031462bSMingming Cao if (allocated > max_blocks) 30990031462bSMingming Cao allocated = max_blocks; 31000031462bSMingming Cao ext4_ext_show_leaf(inode, path); 31010031462bSMingming Cao bh_result->b_bdev = inode->i_sb->s_bdev; 31020031462bSMingming Cao bh_result->b_blocknr = newblock; 31030031462bSMingming Cao out2: 31040031462bSMingming Cao if (path) { 31050031462bSMingming Cao ext4_ext_drop_refs(path); 31060031462bSMingming Cao kfree(path); 31070031462bSMingming Cao } 31080031462bSMingming Cao return err ? err : allocated; 31090031462bSMingming Cao } 31100031462bSMingming Cao /* 3111f5ab0d1fSMingming Cao * Block allocation/map/preallocation routine for extents based files 3112f5ab0d1fSMingming Cao * 3113f5ab0d1fSMingming Cao * 3114c278bfecSAneesh Kumar K.V * Need to be called with 31150e855ac8SAneesh Kumar K.V * down_read(&EXT4_I(inode)->i_data_sem) if not allocating file system block 31160e855ac8SAneesh Kumar K.V * (ie, create is zero). Otherwise down_write(&EXT4_I(inode)->i_data_sem) 3117f5ab0d1fSMingming Cao * 3118f5ab0d1fSMingming Cao * return > 0, number of of blocks already mapped/allocated 3119f5ab0d1fSMingming Cao * if create == 0 and these are pre-allocated blocks 3120f5ab0d1fSMingming Cao * buffer head is unmapped 3121f5ab0d1fSMingming Cao * otherwise blocks are mapped 3122f5ab0d1fSMingming Cao * 3123f5ab0d1fSMingming Cao * return = 0, if plain look up failed (blocks have not been allocated) 3124f5ab0d1fSMingming Cao * buffer head is unmapped 3125f5ab0d1fSMingming Cao * 3126f5ab0d1fSMingming Cao * return < 0, error case. 3127c278bfecSAneesh Kumar K.V */ 3128f65e6fbaSAlex Tomas int ext4_ext_get_blocks(handle_t *handle, struct inode *inode, 3129725d26d3SAneesh Kumar K.V ext4_lblk_t iblock, 3130498e5f24STheodore Ts'o unsigned int max_blocks, struct buffer_head *bh_result, 3131c2177057STheodore Ts'o int flags) 3132a86c6181SAlex Tomas { 3133a86c6181SAlex Tomas struct ext4_ext_path *path = NULL; 313456055d3aSAmit Arora struct ext4_extent_header *eh; 3135a86c6181SAlex Tomas struct ext4_extent newex, *ex; 3136498e5f24STheodore Ts'o ext4_fsblk_t newblock; 3137498e5f24STheodore Ts'o int err = 0, depth, ret, cache_type; 3138498e5f24STheodore Ts'o unsigned int allocated = 0; 3139c9de560dSAlex Tomas struct ext4_allocation_request ar; 31408d5d02e6SMingming Cao ext4_io_end_t *io = EXT4_I(inode)->cur_aio_dio; 3141a86c6181SAlex Tomas 3142a86c6181SAlex Tomas __clear_bit(BH_New, &bh_result->b_state); 314384fe3befSMingming ext_debug("blocks %u/%u requested for inode %lu\n", 3144bba90743SEric Sandeen iblock, max_blocks, inode->i_ino); 3145a86c6181SAlex Tomas 3146a86c6181SAlex Tomas /* check in cache */ 3147498e5f24STheodore Ts'o cache_type = ext4_ext_in_cache(inode, iblock, &newex); 3148498e5f24STheodore Ts'o if (cache_type) { 3149498e5f24STheodore Ts'o if (cache_type == EXT4_EXT_CACHE_GAP) { 3150c2177057STheodore Ts'o if ((flags & EXT4_GET_BLOCKS_CREATE) == 0) { 315156055d3aSAmit Arora /* 315256055d3aSAmit Arora * block isn't allocated yet and 315356055d3aSAmit Arora * user doesn't want to allocate it 315456055d3aSAmit Arora */ 3155a86c6181SAlex Tomas goto out2; 3156a86c6181SAlex Tomas } 3157a86c6181SAlex Tomas /* we should allocate requested block */ 3158498e5f24STheodore Ts'o } else if (cache_type == EXT4_EXT_CACHE_EXTENT) { 3159a86c6181SAlex Tomas /* block is already allocated */ 3160a86c6181SAlex Tomas newblock = iblock 3161a86c6181SAlex Tomas - le32_to_cpu(newex.ee_block) 3162f65e6fbaSAlex Tomas + ext_pblock(&newex); 3163d0d856e8SRandy Dunlap /* number of remaining blocks in the extent */ 3164b939e376SAneesh Kumar K.V allocated = ext4_ext_get_actual_len(&newex) - 3165a86c6181SAlex Tomas (iblock - le32_to_cpu(newex.ee_block)); 3166a86c6181SAlex Tomas goto out; 3167a86c6181SAlex Tomas } else { 3168a86c6181SAlex Tomas BUG(); 3169a86c6181SAlex Tomas } 3170a86c6181SAlex Tomas } 3171a86c6181SAlex Tomas 3172a86c6181SAlex Tomas /* find extent for this block */ 3173a86c6181SAlex Tomas path = ext4_ext_find_extent(inode, iblock, NULL); 3174a86c6181SAlex Tomas if (IS_ERR(path)) { 3175a86c6181SAlex Tomas err = PTR_ERR(path); 3176a86c6181SAlex Tomas path = NULL; 3177a86c6181SAlex Tomas goto out2; 3178a86c6181SAlex Tomas } 3179a86c6181SAlex Tomas 3180a86c6181SAlex Tomas depth = ext_depth(inode); 3181a86c6181SAlex Tomas 3182a86c6181SAlex Tomas /* 3183d0d856e8SRandy Dunlap * consistent leaf must not be empty; 3184d0d856e8SRandy Dunlap * this situation is possible, though, _during_ tree modification; 3185a86c6181SAlex Tomas * this is why assert can't be put in ext4_ext_find_extent() 3186a86c6181SAlex Tomas */ 3187a86c6181SAlex Tomas BUG_ON(path[depth].p_ext == NULL && depth != 0); 318856055d3aSAmit Arora eh = path[depth].p_hdr; 3189a86c6181SAlex Tomas 31907e028976SAvantika Mathur ex = path[depth].p_ext; 31917e028976SAvantika Mathur if (ex) { 3192725d26d3SAneesh Kumar K.V ext4_lblk_t ee_block = le32_to_cpu(ex->ee_block); 3193f65e6fbaSAlex Tomas ext4_fsblk_t ee_start = ext_pblock(ex); 3194a2df2a63SAmit Arora unsigned short ee_len; 3195471d4011SSuparna Bhattacharya 3196471d4011SSuparna Bhattacharya /* 3197471d4011SSuparna Bhattacharya * Uninitialized extents are treated as holes, except that 319856055d3aSAmit Arora * we split out initialized portions during a write. 3199471d4011SSuparna Bhattacharya */ 3200a2df2a63SAmit Arora ee_len = ext4_ext_get_actual_len(ex); 3201d0d856e8SRandy Dunlap /* if found extent covers block, simply return it */ 3202a86c6181SAlex Tomas if (iblock >= ee_block && iblock < ee_block + ee_len) { 3203a86c6181SAlex Tomas newblock = iblock - ee_block + ee_start; 3204d0d856e8SRandy Dunlap /* number of remaining blocks in the extent */ 3205a86c6181SAlex Tomas allocated = ee_len - (iblock - ee_block); 320684fe3befSMingming ext_debug("%u fit into %u:%d -> %llu\n", iblock, 3207a86c6181SAlex Tomas ee_block, ee_len, newblock); 320856055d3aSAmit Arora 3209a2df2a63SAmit Arora /* Do not put uninitialized extent in the cache */ 321056055d3aSAmit Arora if (!ext4_ext_is_uninitialized(ex)) { 3211a2df2a63SAmit Arora ext4_ext_put_in_cache(inode, ee_block, 3212a2df2a63SAmit Arora ee_len, ee_start, 3213a2df2a63SAmit Arora EXT4_EXT_CACHE_EXTENT); 3214a86c6181SAlex Tomas goto out; 3215a86c6181SAlex Tomas } 32160031462bSMingming Cao ret = ext4_ext_handle_uninitialized_extents(handle, 32170031462bSMingming Cao inode, iblock, max_blocks, path, 32180031462bSMingming Cao flags, allocated, bh_result, newblock); 32190031462bSMingming Cao return ret; 322056055d3aSAmit Arora } 3221a86c6181SAlex Tomas } 3222a86c6181SAlex Tomas 3223a86c6181SAlex Tomas /* 3224d0d856e8SRandy Dunlap * requested block isn't allocated yet; 3225a86c6181SAlex Tomas * we couldn't try to create block if create flag is zero 3226a86c6181SAlex Tomas */ 3227c2177057STheodore Ts'o if ((flags & EXT4_GET_BLOCKS_CREATE) == 0) { 322856055d3aSAmit Arora /* 322956055d3aSAmit Arora * put just found gap into cache to speed up 323056055d3aSAmit Arora * subsequent requests 323156055d3aSAmit Arora */ 3232a86c6181SAlex Tomas ext4_ext_put_gap_in_cache(inode, path, iblock); 3233a86c6181SAlex Tomas goto out2; 3234a86c6181SAlex Tomas } 3235a86c6181SAlex Tomas /* 3236c2ea3fdeSTheodore Ts'o * Okay, we need to do block allocation. 3237a86c6181SAlex Tomas */ 3238a86c6181SAlex Tomas 3239c9de560dSAlex Tomas /* find neighbour allocated blocks */ 3240c9de560dSAlex Tomas ar.lleft = iblock; 3241c9de560dSAlex Tomas err = ext4_ext_search_left(inode, path, &ar.lleft, &ar.pleft); 3242c9de560dSAlex Tomas if (err) 3243c9de560dSAlex Tomas goto out2; 3244c9de560dSAlex Tomas ar.lright = iblock; 3245c9de560dSAlex Tomas err = ext4_ext_search_right(inode, path, &ar.lright, &ar.pright); 3246c9de560dSAlex Tomas if (err) 3247c9de560dSAlex Tomas goto out2; 324825d14f98SAmit Arora 3249749269faSAmit Arora /* 3250749269faSAmit Arora * See if request is beyond maximum number of blocks we can have in 3251749269faSAmit Arora * a single extent. For an initialized extent this limit is 3252749269faSAmit Arora * EXT_INIT_MAX_LEN and for an uninitialized extent this limit is 3253749269faSAmit Arora * EXT_UNINIT_MAX_LEN. 3254749269faSAmit Arora */ 3255749269faSAmit Arora if (max_blocks > EXT_INIT_MAX_LEN && 3256c2177057STheodore Ts'o !(flags & EXT4_GET_BLOCKS_UNINIT_EXT)) 3257749269faSAmit Arora max_blocks = EXT_INIT_MAX_LEN; 3258749269faSAmit Arora else if (max_blocks > EXT_UNINIT_MAX_LEN && 3259c2177057STheodore Ts'o (flags & EXT4_GET_BLOCKS_UNINIT_EXT)) 3260749269faSAmit Arora max_blocks = EXT_UNINIT_MAX_LEN; 3261749269faSAmit Arora 326225d14f98SAmit Arora /* Check if we can really insert (iblock)::(iblock+max_blocks) extent */ 326325d14f98SAmit Arora newex.ee_block = cpu_to_le32(iblock); 326425d14f98SAmit Arora newex.ee_len = cpu_to_le16(max_blocks); 326525d14f98SAmit Arora err = ext4_ext_check_overlap(inode, &newex, path); 326625d14f98SAmit Arora if (err) 3267b939e376SAneesh Kumar K.V allocated = ext4_ext_get_actual_len(&newex); 326825d14f98SAmit Arora else 3269a86c6181SAlex Tomas allocated = max_blocks; 3270c9de560dSAlex Tomas 3271c9de560dSAlex Tomas /* allocate new block */ 3272c9de560dSAlex Tomas ar.inode = inode; 3273c9de560dSAlex Tomas ar.goal = ext4_ext_find_goal(inode, path, iblock); 3274c9de560dSAlex Tomas ar.logical = iblock; 3275c9de560dSAlex Tomas ar.len = allocated; 3276c9de560dSAlex Tomas if (S_ISREG(inode->i_mode)) 3277c9de560dSAlex Tomas ar.flags = EXT4_MB_HINT_DATA; 3278c9de560dSAlex Tomas else 3279c9de560dSAlex Tomas /* disable in-core preallocation for non-regular files */ 3280c9de560dSAlex Tomas ar.flags = 0; 3281c9de560dSAlex Tomas newblock = ext4_mb_new_blocks(handle, &ar, &err); 3282a86c6181SAlex Tomas if (!newblock) 3283a86c6181SAlex Tomas goto out2; 328484fe3befSMingming ext_debug("allocate new block: goal %llu, found %llu/%u\n", 3285498e5f24STheodore Ts'o ar.goal, newblock, allocated); 3286a86c6181SAlex Tomas 3287a86c6181SAlex Tomas /* try to insert new extent into found leaf and return */ 3288f65e6fbaSAlex Tomas ext4_ext_store_pblock(&newex, newblock); 3289c9de560dSAlex Tomas newex.ee_len = cpu_to_le16(ar.len); 32908d5d02e6SMingming Cao /* Mark uninitialized */ 32918d5d02e6SMingming Cao if (flags & EXT4_GET_BLOCKS_UNINIT_EXT){ 3292a2df2a63SAmit Arora ext4_ext_mark_uninitialized(&newex); 32938d5d02e6SMingming Cao /* 32948d5d02e6SMingming Cao * io_end structure was created for every async 32958d5d02e6SMingming Cao * direct IO write to the middle of the file. 32968d5d02e6SMingming Cao * To avoid unecessary convertion for every aio dio rewrite 32978d5d02e6SMingming Cao * to the mid of file, here we flag the IO that is really 32988d5d02e6SMingming Cao * need the convertion. 32995f524950SMingming * For non asycn direct IO case, flag the inode state 33005f524950SMingming * that we need to perform convertion when IO is done. 33018d5d02e6SMingming Cao */ 33025f524950SMingming if (flags == EXT4_GET_BLOCKS_DIO_CREATE_EXT) { 33035f524950SMingming if (io) 33048d5d02e6SMingming Cao io->flag = DIO_AIO_UNWRITTEN; 33055f524950SMingming else 33065f524950SMingming EXT4_I(inode)->i_state |= 33075f524950SMingming EXT4_STATE_DIO_UNWRITTEN;; 33085f524950SMingming } 33098d5d02e6SMingming Cao } 33100031462bSMingming Cao err = ext4_ext_insert_extent(handle, inode, path, &newex, flags); 3311315054f0SAlex Tomas if (err) { 3312315054f0SAlex Tomas /* free data blocks we just allocated */ 3313c9de560dSAlex Tomas /* not a good idea to call discard here directly, 3314c9de560dSAlex Tomas * but otherwise we'd need to call it every free() */ 3315c2ea3fdeSTheodore Ts'o ext4_discard_preallocations(inode); 3316*e6362609STheodore Ts'o ext4_free_blocks(handle, inode, 0, ext_pblock(&newex), 3317b939e376SAneesh Kumar K.V ext4_ext_get_actual_len(&newex), 0); 3318a86c6181SAlex Tomas goto out2; 3319315054f0SAlex Tomas } 3320a86c6181SAlex Tomas 3321a86c6181SAlex Tomas /* previous routine could use block we allocated */ 3322f65e6fbaSAlex Tomas newblock = ext_pblock(&newex); 3323b939e376SAneesh Kumar K.V allocated = ext4_ext_get_actual_len(&newex); 3324953e622bSEric Sandeen set_buffer_new(bh_result); 3325a86c6181SAlex Tomas 3326a2df2a63SAmit Arora /* Cache only when it is _not_ an uninitialized extent */ 3327c2177057STheodore Ts'o if ((flags & EXT4_GET_BLOCKS_UNINIT_EXT) == 0) 3328a86c6181SAlex Tomas ext4_ext_put_in_cache(inode, iblock, allocated, newblock, 3329a86c6181SAlex Tomas EXT4_EXT_CACHE_EXTENT); 3330a86c6181SAlex Tomas out: 3331a86c6181SAlex Tomas if (allocated > max_blocks) 3332a86c6181SAlex Tomas allocated = max_blocks; 3333a86c6181SAlex Tomas ext4_ext_show_leaf(inode, path); 3334953e622bSEric Sandeen set_buffer_mapped(bh_result); 3335a86c6181SAlex Tomas bh_result->b_bdev = inode->i_sb->s_bdev; 3336a86c6181SAlex Tomas bh_result->b_blocknr = newblock; 3337a86c6181SAlex Tomas out2: 3338a86c6181SAlex Tomas if (path) { 3339a86c6181SAlex Tomas ext4_ext_drop_refs(path); 3340a86c6181SAlex Tomas kfree(path); 3341a86c6181SAlex Tomas } 3342a86c6181SAlex Tomas return err ? err : allocated; 3343a86c6181SAlex Tomas } 3344a86c6181SAlex Tomas 3345cf108bcaSJan Kara void ext4_ext_truncate(struct inode *inode) 3346a86c6181SAlex Tomas { 3347a86c6181SAlex Tomas struct address_space *mapping = inode->i_mapping; 3348a86c6181SAlex Tomas struct super_block *sb = inode->i_sb; 3349725d26d3SAneesh Kumar K.V ext4_lblk_t last_block; 3350a86c6181SAlex Tomas handle_t *handle; 3351a86c6181SAlex Tomas int err = 0; 3352a86c6181SAlex Tomas 3353a86c6181SAlex Tomas /* 3354a86c6181SAlex Tomas * probably first extent we're gonna free will be last in block 3355a86c6181SAlex Tomas */ 3356f3bd1f3fSMingming Cao err = ext4_writepage_trans_blocks(inode); 3357a86c6181SAlex Tomas handle = ext4_journal_start(inode, err); 3358cf108bcaSJan Kara if (IS_ERR(handle)) 3359a86c6181SAlex Tomas return; 3360a86c6181SAlex Tomas 3361cf108bcaSJan Kara if (inode->i_size & (sb->s_blocksize - 1)) 3362cf108bcaSJan Kara ext4_block_truncate_page(handle, mapping, inode->i_size); 3363a86c6181SAlex Tomas 33649ddfc3dcSJan Kara if (ext4_orphan_add(handle, inode)) 33659ddfc3dcSJan Kara goto out_stop; 33669ddfc3dcSJan Kara 33670e855ac8SAneesh Kumar K.V down_write(&EXT4_I(inode)->i_data_sem); 3368a86c6181SAlex Tomas ext4_ext_invalidate_cache(inode); 3369a86c6181SAlex Tomas 3370c2ea3fdeSTheodore Ts'o ext4_discard_preallocations(inode); 3371c9de560dSAlex Tomas 3372a86c6181SAlex Tomas /* 3373d0d856e8SRandy Dunlap * TODO: optimization is possible here. 3374d0d856e8SRandy Dunlap * Probably we need not scan at all, 3375d0d856e8SRandy Dunlap * because page truncation is enough. 3376a86c6181SAlex Tomas */ 3377a86c6181SAlex Tomas 3378a86c6181SAlex Tomas /* we have to know where to truncate from in crash case */ 3379a86c6181SAlex Tomas EXT4_I(inode)->i_disksize = inode->i_size; 3380a86c6181SAlex Tomas ext4_mark_inode_dirty(handle, inode); 3381a86c6181SAlex Tomas 3382a86c6181SAlex Tomas last_block = (inode->i_size + sb->s_blocksize - 1) 3383a86c6181SAlex Tomas >> EXT4_BLOCK_SIZE_BITS(sb); 3384a86c6181SAlex Tomas err = ext4_ext_remove_space(inode, last_block); 3385a86c6181SAlex Tomas 3386a86c6181SAlex Tomas /* In a multi-transaction truncate, we only make the final 338756055d3aSAmit Arora * transaction synchronous. 338856055d3aSAmit Arora */ 3389a86c6181SAlex Tomas if (IS_SYNC(inode)) 33900390131bSFrank Mayhar ext4_handle_sync(handle); 3391a86c6181SAlex Tomas 3392a86c6181SAlex Tomas out_stop: 33939ddfc3dcSJan Kara up_write(&EXT4_I(inode)->i_data_sem); 3394a86c6181SAlex Tomas /* 3395d0d856e8SRandy Dunlap * If this was a simple ftruncate() and the file will remain alive, 3396a86c6181SAlex Tomas * then we need to clear up the orphan record which we created above. 3397a86c6181SAlex Tomas * However, if this was a real unlink then we were called by 3398a86c6181SAlex Tomas * ext4_delete_inode(), and we allow that function to clean up the 3399a86c6181SAlex Tomas * orphan info for us. 3400a86c6181SAlex Tomas */ 3401a86c6181SAlex Tomas if (inode->i_nlink) 3402a86c6181SAlex Tomas ext4_orphan_del(handle, inode); 3403a86c6181SAlex Tomas 3404ef737728SSolofo Ramangalahy inode->i_mtime = inode->i_ctime = ext4_current_time(inode); 3405ef737728SSolofo Ramangalahy ext4_mark_inode_dirty(handle, inode); 3406a86c6181SAlex Tomas ext4_journal_stop(handle); 3407a86c6181SAlex Tomas } 3408a86c6181SAlex Tomas 3409fd28784aSAneesh Kumar K.V static void ext4_falloc_update_inode(struct inode *inode, 3410fd28784aSAneesh Kumar K.V int mode, loff_t new_size, int update_ctime) 3411fd28784aSAneesh Kumar K.V { 3412fd28784aSAneesh Kumar K.V struct timespec now; 3413fd28784aSAneesh Kumar K.V 3414fd28784aSAneesh Kumar K.V if (update_ctime) { 3415fd28784aSAneesh Kumar K.V now = current_fs_time(inode->i_sb); 3416fd28784aSAneesh Kumar K.V if (!timespec_equal(&inode->i_ctime, &now)) 3417fd28784aSAneesh Kumar K.V inode->i_ctime = now; 3418fd28784aSAneesh Kumar K.V } 3419fd28784aSAneesh Kumar K.V /* 3420fd28784aSAneesh Kumar K.V * Update only when preallocation was requested beyond 3421fd28784aSAneesh Kumar K.V * the file size. 3422fd28784aSAneesh Kumar K.V */ 3423cf17fea6SAneesh Kumar K.V if (!(mode & FALLOC_FL_KEEP_SIZE)) { 3424cf17fea6SAneesh Kumar K.V if (new_size > i_size_read(inode)) 3425fd28784aSAneesh Kumar K.V i_size_write(inode, new_size); 3426cf17fea6SAneesh Kumar K.V if (new_size > EXT4_I(inode)->i_disksize) 3427cf17fea6SAneesh Kumar K.V ext4_update_i_disksize(inode, new_size); 3428fd28784aSAneesh Kumar K.V } 3429fd28784aSAneesh Kumar K.V 3430fd28784aSAneesh Kumar K.V } 3431fd28784aSAneesh Kumar K.V 3432a2df2a63SAmit Arora /* 3433a2df2a63SAmit Arora * preallocate space for a file. This implements ext4's fallocate inode 3434a2df2a63SAmit Arora * operation, which gets called from sys_fallocate system call. 3435a2df2a63SAmit Arora * For block-mapped files, posix_fallocate should fall back to the method 3436a2df2a63SAmit Arora * of writing zeroes to the required new blocks (the same behavior which is 3437a2df2a63SAmit Arora * expected for file systems which do not support fallocate() system call). 3438a2df2a63SAmit Arora */ 3439a2df2a63SAmit Arora long ext4_fallocate(struct inode *inode, int mode, loff_t offset, loff_t len) 3440a2df2a63SAmit Arora { 3441a2df2a63SAmit Arora handle_t *handle; 3442725d26d3SAneesh Kumar K.V ext4_lblk_t block; 3443fd28784aSAneesh Kumar K.V loff_t new_size; 3444498e5f24STheodore Ts'o unsigned int max_blocks; 3445a2df2a63SAmit Arora int ret = 0; 3446a2df2a63SAmit Arora int ret2 = 0; 3447a2df2a63SAmit Arora int retries = 0; 3448a2df2a63SAmit Arora struct buffer_head map_bh; 3449a2df2a63SAmit Arora unsigned int credits, blkbits = inode->i_blkbits; 3450a2df2a63SAmit Arora 3451a2df2a63SAmit Arora /* 3452a2df2a63SAmit Arora * currently supporting (pre)allocate mode for extent-based 3453a2df2a63SAmit Arora * files _only_ 3454a2df2a63SAmit Arora */ 3455a2df2a63SAmit Arora if (!(EXT4_I(inode)->i_flags & EXT4_EXTENTS_FL)) 3456a2df2a63SAmit Arora return -EOPNOTSUPP; 3457a2df2a63SAmit Arora 3458a2df2a63SAmit Arora /* preallocation to directories is currently not supported */ 3459a2df2a63SAmit Arora if (S_ISDIR(inode->i_mode)) 3460a2df2a63SAmit Arora return -ENODEV; 3461a2df2a63SAmit Arora 3462a2df2a63SAmit Arora block = offset >> blkbits; 3463fd28784aSAneesh Kumar K.V /* 3464fd28784aSAneesh Kumar K.V * We can't just convert len to max_blocks because 3465fd28784aSAneesh Kumar K.V * If blocksize = 4096 offset = 3072 and len = 2048 3466fd28784aSAneesh Kumar K.V */ 3467a2df2a63SAmit Arora max_blocks = (EXT4_BLOCK_ALIGN(len + offset, blkbits) >> blkbits) 3468a2df2a63SAmit Arora - block; 3469a2df2a63SAmit Arora /* 3470f3bd1f3fSMingming Cao * credits to insert 1 extent into extent tree 3471a2df2a63SAmit Arora */ 3472f3bd1f3fSMingming Cao credits = ext4_chunk_trans_blocks(inode, max_blocks); 347355bd725aSAneesh Kumar K.V mutex_lock(&inode->i_mutex); 3474a2df2a63SAmit Arora retry: 3475a2df2a63SAmit Arora while (ret >= 0 && ret < max_blocks) { 3476a2df2a63SAmit Arora block = block + ret; 3477a2df2a63SAmit Arora max_blocks = max_blocks - ret; 3478a2df2a63SAmit Arora handle = ext4_journal_start(inode, credits); 3479a2df2a63SAmit Arora if (IS_ERR(handle)) { 3480a2df2a63SAmit Arora ret = PTR_ERR(handle); 3481a2df2a63SAmit Arora break; 3482a2df2a63SAmit Arora } 348379ffab34SAneesh Kumar K.V map_bh.b_state = 0; 348412b7ac17STheodore Ts'o ret = ext4_get_blocks(handle, inode, block, 3485a2df2a63SAmit Arora max_blocks, &map_bh, 3486c2177057STheodore Ts'o EXT4_GET_BLOCKS_CREATE_UNINIT_EXT); 3487221879c9SAneesh Kumar K.V if (ret <= 0) { 34882c98615dSAneesh Kumar K.V #ifdef EXT4FS_DEBUG 34892c98615dSAneesh Kumar K.V WARN_ON(ret <= 0); 34902c98615dSAneesh Kumar K.V printk(KERN_ERR "%s: ext4_ext_get_blocks " 34912c98615dSAneesh Kumar K.V "returned error inode#%lu, block=%u, " 34929fd9784cSThadeu Lima de Souza Cascardo "max_blocks=%u", __func__, 3493bba90743SEric Sandeen inode->i_ino, block, max_blocks); 34942c98615dSAneesh Kumar K.V #endif 3495a2df2a63SAmit Arora ext4_mark_inode_dirty(handle, inode); 3496a2df2a63SAmit Arora ret2 = ext4_journal_stop(handle); 3497a2df2a63SAmit Arora break; 3498a2df2a63SAmit Arora } 3499fd28784aSAneesh Kumar K.V if ((block + ret) >= (EXT4_BLOCK_ALIGN(offset + len, 3500fd28784aSAneesh Kumar K.V blkbits) >> blkbits)) 3501fd28784aSAneesh Kumar K.V new_size = offset + len; 3502fd28784aSAneesh Kumar K.V else 3503fd28784aSAneesh Kumar K.V new_size = (block + ret) << blkbits; 3504a2df2a63SAmit Arora 3505fd28784aSAneesh Kumar K.V ext4_falloc_update_inode(inode, mode, new_size, 3506fd28784aSAneesh Kumar K.V buffer_new(&map_bh)); 3507a2df2a63SAmit Arora ext4_mark_inode_dirty(handle, inode); 3508a2df2a63SAmit Arora ret2 = ext4_journal_stop(handle); 3509a2df2a63SAmit Arora if (ret2) 3510a2df2a63SAmit Arora break; 3511a2df2a63SAmit Arora } 3512fd28784aSAneesh Kumar K.V if (ret == -ENOSPC && 3513fd28784aSAneesh Kumar K.V ext4_should_retry_alloc(inode->i_sb, &retries)) { 3514fd28784aSAneesh Kumar K.V ret = 0; 3515a2df2a63SAmit Arora goto retry; 3516a2df2a63SAmit Arora } 351755bd725aSAneesh Kumar K.V mutex_unlock(&inode->i_mutex); 3518a2df2a63SAmit Arora return ret > 0 ? ret2 : ret; 3519a2df2a63SAmit Arora } 35206873fa0dSEric Sandeen 35216873fa0dSEric Sandeen /* 35220031462bSMingming Cao * This function convert a range of blocks to written extents 35230031462bSMingming Cao * The caller of this function will pass the start offset and the size. 35240031462bSMingming Cao * all unwritten extents within this range will be converted to 35250031462bSMingming Cao * written extents. 35260031462bSMingming Cao * 35270031462bSMingming Cao * This function is called from the direct IO end io call back 35280031462bSMingming Cao * function, to convert the fallocated extents after IO is completed. 3529109f5565SMingming * Returns 0 on success. 35300031462bSMingming Cao */ 35310031462bSMingming Cao int ext4_convert_unwritten_extents(struct inode *inode, loff_t offset, 35320031462bSMingming Cao loff_t len) 35330031462bSMingming Cao { 35340031462bSMingming Cao handle_t *handle; 35350031462bSMingming Cao ext4_lblk_t block; 35360031462bSMingming Cao unsigned int max_blocks; 35370031462bSMingming Cao int ret = 0; 35380031462bSMingming Cao int ret2 = 0; 35390031462bSMingming Cao struct buffer_head map_bh; 35400031462bSMingming Cao unsigned int credits, blkbits = inode->i_blkbits; 35410031462bSMingming Cao 35420031462bSMingming Cao block = offset >> blkbits; 35430031462bSMingming Cao /* 35440031462bSMingming Cao * We can't just convert len to max_blocks because 35450031462bSMingming Cao * If blocksize = 4096 offset = 3072 and len = 2048 35460031462bSMingming Cao */ 35470031462bSMingming Cao max_blocks = (EXT4_BLOCK_ALIGN(len + offset, blkbits) >> blkbits) 35480031462bSMingming Cao - block; 35490031462bSMingming Cao /* 35500031462bSMingming Cao * credits to insert 1 extent into extent tree 35510031462bSMingming Cao */ 35520031462bSMingming Cao credits = ext4_chunk_trans_blocks(inode, max_blocks); 35530031462bSMingming Cao while (ret >= 0 && ret < max_blocks) { 35540031462bSMingming Cao block = block + ret; 35550031462bSMingming Cao max_blocks = max_blocks - ret; 35560031462bSMingming Cao handle = ext4_journal_start(inode, credits); 35570031462bSMingming Cao if (IS_ERR(handle)) { 35580031462bSMingming Cao ret = PTR_ERR(handle); 35590031462bSMingming Cao break; 35600031462bSMingming Cao } 35610031462bSMingming Cao map_bh.b_state = 0; 35620031462bSMingming Cao ret = ext4_get_blocks(handle, inode, block, 35630031462bSMingming Cao max_blocks, &map_bh, 35640031462bSMingming Cao EXT4_GET_BLOCKS_DIO_CONVERT_EXT); 35650031462bSMingming Cao if (ret <= 0) { 35660031462bSMingming Cao WARN_ON(ret <= 0); 35670031462bSMingming Cao printk(KERN_ERR "%s: ext4_ext_get_blocks " 35680031462bSMingming Cao "returned error inode#%lu, block=%u, " 35690031462bSMingming Cao "max_blocks=%u", __func__, 35700031462bSMingming Cao inode->i_ino, block, max_blocks); 35710031462bSMingming Cao } 35720031462bSMingming Cao ext4_mark_inode_dirty(handle, inode); 35730031462bSMingming Cao ret2 = ext4_journal_stop(handle); 35740031462bSMingming Cao if (ret <= 0 || ret2 ) 35750031462bSMingming Cao break; 35760031462bSMingming Cao } 35770031462bSMingming Cao return ret > 0 ? ret2 : ret; 35780031462bSMingming Cao } 35790031462bSMingming Cao /* 35806873fa0dSEric Sandeen * Callback function called for each extent to gather FIEMAP information. 35816873fa0dSEric Sandeen */ 35823a06d778SAneesh Kumar K.V static int ext4_ext_fiemap_cb(struct inode *inode, struct ext4_ext_path *path, 35836873fa0dSEric Sandeen struct ext4_ext_cache *newex, struct ext4_extent *ex, 35846873fa0dSEric Sandeen void *data) 35856873fa0dSEric Sandeen { 35866873fa0dSEric Sandeen struct fiemap_extent_info *fieinfo = data; 3587c9877b20SEric Sandeen unsigned char blksize_bits = inode->i_sb->s_blocksize_bits; 35886873fa0dSEric Sandeen __u64 logical; 35896873fa0dSEric Sandeen __u64 physical; 35906873fa0dSEric Sandeen __u64 length; 35916873fa0dSEric Sandeen __u32 flags = 0; 35926873fa0dSEric Sandeen int error; 35936873fa0dSEric Sandeen 35946873fa0dSEric Sandeen logical = (__u64)newex->ec_block << blksize_bits; 35956873fa0dSEric Sandeen 35966873fa0dSEric Sandeen if (newex->ec_type == EXT4_EXT_CACHE_GAP) { 35976873fa0dSEric Sandeen pgoff_t offset; 35986873fa0dSEric Sandeen struct page *page; 35996873fa0dSEric Sandeen struct buffer_head *bh = NULL; 36006873fa0dSEric Sandeen 36016873fa0dSEric Sandeen offset = logical >> PAGE_SHIFT; 36026873fa0dSEric Sandeen page = find_get_page(inode->i_mapping, offset); 36036873fa0dSEric Sandeen if (!page || !page_has_buffers(page)) 36046873fa0dSEric Sandeen return EXT_CONTINUE; 36056873fa0dSEric Sandeen 36066873fa0dSEric Sandeen bh = page_buffers(page); 36076873fa0dSEric Sandeen 36086873fa0dSEric Sandeen if (!bh) 36096873fa0dSEric Sandeen return EXT_CONTINUE; 36106873fa0dSEric Sandeen 36116873fa0dSEric Sandeen if (buffer_delay(bh)) { 36126873fa0dSEric Sandeen flags |= FIEMAP_EXTENT_DELALLOC; 36136873fa0dSEric Sandeen page_cache_release(page); 36146873fa0dSEric Sandeen } else { 36156873fa0dSEric Sandeen page_cache_release(page); 36166873fa0dSEric Sandeen return EXT_CONTINUE; 36176873fa0dSEric Sandeen } 36186873fa0dSEric Sandeen } 36196873fa0dSEric Sandeen 36206873fa0dSEric Sandeen physical = (__u64)newex->ec_start << blksize_bits; 36216873fa0dSEric Sandeen length = (__u64)newex->ec_len << blksize_bits; 36226873fa0dSEric Sandeen 36236873fa0dSEric Sandeen if (ex && ext4_ext_is_uninitialized(ex)) 36246873fa0dSEric Sandeen flags |= FIEMAP_EXTENT_UNWRITTEN; 36256873fa0dSEric Sandeen 36266873fa0dSEric Sandeen /* 36276873fa0dSEric Sandeen * If this extent reaches EXT_MAX_BLOCK, it must be last. 36286873fa0dSEric Sandeen * 36296873fa0dSEric Sandeen * Or if ext4_ext_next_allocated_block is EXT_MAX_BLOCK, 36306873fa0dSEric Sandeen * this also indicates no more allocated blocks. 36316873fa0dSEric Sandeen * 36326873fa0dSEric Sandeen * XXX this might miss a single-block extent at EXT_MAX_BLOCK 36336873fa0dSEric Sandeen */ 3634c9877b20SEric Sandeen if (ext4_ext_next_allocated_block(path) == EXT_MAX_BLOCK || 3635eefd7f03STheodore Ts'o newex->ec_block + newex->ec_len - 1 == EXT_MAX_BLOCK) { 3636eefd7f03STheodore Ts'o loff_t size = i_size_read(inode); 3637eefd7f03STheodore Ts'o loff_t bs = EXT4_BLOCK_SIZE(inode->i_sb); 3638eefd7f03STheodore Ts'o 36396873fa0dSEric Sandeen flags |= FIEMAP_EXTENT_LAST; 3640eefd7f03STheodore Ts'o if ((flags & FIEMAP_EXTENT_DELALLOC) && 3641eefd7f03STheodore Ts'o logical+length > size) 3642eefd7f03STheodore Ts'o length = (size - logical + bs - 1) & ~(bs-1); 3643eefd7f03STheodore Ts'o } 36446873fa0dSEric Sandeen 36456873fa0dSEric Sandeen error = fiemap_fill_next_extent(fieinfo, logical, physical, 36466873fa0dSEric Sandeen length, flags); 36476873fa0dSEric Sandeen if (error < 0) 36486873fa0dSEric Sandeen return error; 36496873fa0dSEric Sandeen if (error == 1) 36506873fa0dSEric Sandeen return EXT_BREAK; 36516873fa0dSEric Sandeen 36526873fa0dSEric Sandeen return EXT_CONTINUE; 36536873fa0dSEric Sandeen } 36546873fa0dSEric Sandeen 36556873fa0dSEric Sandeen /* fiemap flags we can handle specified here */ 36566873fa0dSEric Sandeen #define EXT4_FIEMAP_FLAGS (FIEMAP_FLAG_SYNC|FIEMAP_FLAG_XATTR) 36576873fa0dSEric Sandeen 36583a06d778SAneesh Kumar K.V static int ext4_xattr_fiemap(struct inode *inode, 36593a06d778SAneesh Kumar K.V struct fiemap_extent_info *fieinfo) 36606873fa0dSEric Sandeen { 36616873fa0dSEric Sandeen __u64 physical = 0; 36626873fa0dSEric Sandeen __u64 length; 36636873fa0dSEric Sandeen __u32 flags = FIEMAP_EXTENT_LAST; 36646873fa0dSEric Sandeen int blockbits = inode->i_sb->s_blocksize_bits; 36656873fa0dSEric Sandeen int error = 0; 36666873fa0dSEric Sandeen 36676873fa0dSEric Sandeen /* in-inode? */ 36686873fa0dSEric Sandeen if (EXT4_I(inode)->i_state & EXT4_STATE_XATTR) { 36696873fa0dSEric Sandeen struct ext4_iloc iloc; 36706873fa0dSEric Sandeen int offset; /* offset of xattr in inode */ 36716873fa0dSEric Sandeen 36726873fa0dSEric Sandeen error = ext4_get_inode_loc(inode, &iloc); 36736873fa0dSEric Sandeen if (error) 36746873fa0dSEric Sandeen return error; 36756873fa0dSEric Sandeen physical = iloc.bh->b_blocknr << blockbits; 36766873fa0dSEric Sandeen offset = EXT4_GOOD_OLD_INODE_SIZE + 36776873fa0dSEric Sandeen EXT4_I(inode)->i_extra_isize; 36786873fa0dSEric Sandeen physical += offset; 36796873fa0dSEric Sandeen length = EXT4_SB(inode->i_sb)->s_inode_size - offset; 36806873fa0dSEric Sandeen flags |= FIEMAP_EXTENT_DATA_INLINE; 36816873fa0dSEric Sandeen } else { /* external block */ 36826873fa0dSEric Sandeen physical = EXT4_I(inode)->i_file_acl << blockbits; 36836873fa0dSEric Sandeen length = inode->i_sb->s_blocksize; 36846873fa0dSEric Sandeen } 36856873fa0dSEric Sandeen 36866873fa0dSEric Sandeen if (physical) 36876873fa0dSEric Sandeen error = fiemap_fill_next_extent(fieinfo, 0, physical, 36886873fa0dSEric Sandeen length, flags); 36896873fa0dSEric Sandeen return (error < 0 ? error : 0); 36906873fa0dSEric Sandeen } 36916873fa0dSEric Sandeen 36926873fa0dSEric Sandeen int ext4_fiemap(struct inode *inode, struct fiemap_extent_info *fieinfo, 36936873fa0dSEric Sandeen __u64 start, __u64 len) 36946873fa0dSEric Sandeen { 36956873fa0dSEric Sandeen ext4_lblk_t start_blk; 36966873fa0dSEric Sandeen ext4_lblk_t len_blks; 36976873fa0dSEric Sandeen int error = 0; 36986873fa0dSEric Sandeen 36996873fa0dSEric Sandeen /* fallback to generic here if not in extents fmt */ 37006873fa0dSEric Sandeen if (!(EXT4_I(inode)->i_flags & EXT4_EXTENTS_FL)) 37016873fa0dSEric Sandeen return generic_block_fiemap(inode, fieinfo, start, len, 37026873fa0dSEric Sandeen ext4_get_block); 37036873fa0dSEric Sandeen 37046873fa0dSEric Sandeen if (fiemap_check_flags(fieinfo, EXT4_FIEMAP_FLAGS)) 37056873fa0dSEric Sandeen return -EBADR; 37066873fa0dSEric Sandeen 37076873fa0dSEric Sandeen if (fieinfo->fi_flags & FIEMAP_FLAG_XATTR) { 37086873fa0dSEric Sandeen error = ext4_xattr_fiemap(inode, fieinfo); 37096873fa0dSEric Sandeen } else { 37106873fa0dSEric Sandeen start_blk = start >> inode->i_sb->s_blocksize_bits; 37116873fa0dSEric Sandeen len_blks = len >> inode->i_sb->s_blocksize_bits; 37126873fa0dSEric Sandeen 37136873fa0dSEric Sandeen /* 37146873fa0dSEric Sandeen * Walk the extent tree gathering extent information. 37156873fa0dSEric Sandeen * ext4_ext_fiemap_cb will push extents back to user. 37166873fa0dSEric Sandeen */ 37170568c518STheodore Ts'o down_read(&EXT4_I(inode)->i_data_sem); 37186873fa0dSEric Sandeen error = ext4_ext_walk_space(inode, start_blk, len_blks, 37196873fa0dSEric Sandeen ext4_ext_fiemap_cb, fieinfo); 37200568c518STheodore Ts'o up_read(&EXT4_I(inode)->i_data_sem); 37216873fa0dSEric Sandeen } 37226873fa0dSEric Sandeen 37236873fa0dSEric Sandeen return error; 37246873fa0dSEric Sandeen } 37256873fa0dSEric Sandeen 3726