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 */ 5209b88252SAvantika Mathur static 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 969102e4faSShen Feng static int ext4_ext_journal_restart(handle_t *handle, int needed) 97a86c6181SAlex Tomas { 98a86c6181SAlex Tomas int err; 99a86c6181SAlex Tomas 1000390131bSFrank Mayhar if (!ext4_handle_valid(handle)) 1010390131bSFrank Mayhar return 0; 102a86c6181SAlex Tomas if (handle->h_buffer_credits > needed) 1039102e4faSShen Feng return 0; 1049102e4faSShen Feng err = ext4_journal_extend(handle, needed); 1050123c939STheodore Ts'o if (err <= 0) 1069102e4faSShen Feng return err; 1079102e4faSShen Feng return ext4_journal_restart(handle, needed); 108a86c6181SAlex Tomas } 109a86c6181SAlex Tomas 110a86c6181SAlex Tomas /* 111a86c6181SAlex Tomas * could return: 112a86c6181SAlex Tomas * - EROFS 113a86c6181SAlex Tomas * - ENOMEM 114a86c6181SAlex Tomas */ 115a86c6181SAlex Tomas static int ext4_ext_get_access(handle_t *handle, struct inode *inode, 116a86c6181SAlex Tomas struct ext4_ext_path *path) 117a86c6181SAlex Tomas { 118a86c6181SAlex Tomas if (path->p_bh) { 119a86c6181SAlex Tomas /* path points to block */ 120a86c6181SAlex Tomas return ext4_journal_get_write_access(handle, path->p_bh); 121a86c6181SAlex Tomas } 122a86c6181SAlex Tomas /* path points to leaf/index in inode body */ 123a86c6181SAlex Tomas /* we use in-core data, no need to protect them */ 124a86c6181SAlex Tomas return 0; 125a86c6181SAlex Tomas } 126a86c6181SAlex Tomas 127a86c6181SAlex Tomas /* 128a86c6181SAlex Tomas * could return: 129a86c6181SAlex Tomas * - EROFS 130a86c6181SAlex Tomas * - ENOMEM 131a86c6181SAlex Tomas * - EIO 132a86c6181SAlex Tomas */ 133a86c6181SAlex Tomas static int ext4_ext_dirty(handle_t *handle, struct inode *inode, 134a86c6181SAlex Tomas struct ext4_ext_path *path) 135a86c6181SAlex Tomas { 136a86c6181SAlex Tomas int err; 137a86c6181SAlex Tomas if (path->p_bh) { 138a86c6181SAlex Tomas /* path points to block */ 1390390131bSFrank Mayhar err = ext4_handle_dirty_metadata(handle, inode, path->p_bh); 140a86c6181SAlex Tomas } else { 141a86c6181SAlex Tomas /* path points to leaf/index in inode body */ 142a86c6181SAlex Tomas err = ext4_mark_inode_dirty(handle, inode); 143a86c6181SAlex Tomas } 144a86c6181SAlex Tomas return err; 145a86c6181SAlex Tomas } 146a86c6181SAlex Tomas 147f65e6fbaSAlex Tomas static ext4_fsblk_t ext4_ext_find_goal(struct inode *inode, 148a86c6181SAlex Tomas struct ext4_ext_path *path, 149725d26d3SAneesh Kumar K.V ext4_lblk_t block) 150a86c6181SAlex Tomas { 151a86c6181SAlex Tomas struct ext4_inode_info *ei = EXT4_I(inode); 152f65e6fbaSAlex Tomas ext4_fsblk_t bg_start; 15374d3487fSValerie Clement ext4_fsblk_t last_block; 154f65e6fbaSAlex Tomas ext4_grpblk_t colour; 155a86c6181SAlex Tomas int depth; 156a86c6181SAlex Tomas 157a86c6181SAlex Tomas if (path) { 158a86c6181SAlex Tomas struct ext4_extent *ex; 159a86c6181SAlex Tomas depth = path->p_depth; 160a86c6181SAlex Tomas 161a86c6181SAlex Tomas /* try to predict block placement */ 1627e028976SAvantika Mathur ex = path[depth].p_ext; 1637e028976SAvantika Mathur if (ex) 164f65e6fbaSAlex Tomas return ext_pblock(ex)+(block-le32_to_cpu(ex->ee_block)); 165a86c6181SAlex Tomas 166d0d856e8SRandy Dunlap /* it looks like index is empty; 167d0d856e8SRandy Dunlap * try to find starting block from index itself */ 168a86c6181SAlex Tomas if (path[depth].p_bh) 169a86c6181SAlex Tomas return path[depth].p_bh->b_blocknr; 170a86c6181SAlex Tomas } 171a86c6181SAlex Tomas 172a86c6181SAlex Tomas /* OK. use inode's group */ 173a86c6181SAlex Tomas bg_start = (ei->i_block_group * EXT4_BLOCKS_PER_GROUP(inode->i_sb)) + 174a86c6181SAlex Tomas le32_to_cpu(EXT4_SB(inode->i_sb)->s_es->s_first_data_block); 17574d3487fSValerie Clement last_block = ext4_blocks_count(EXT4_SB(inode->i_sb)->s_es) - 1; 17674d3487fSValerie Clement 17774d3487fSValerie Clement if (bg_start + EXT4_BLOCKS_PER_GROUP(inode->i_sb) <= last_block) 178a86c6181SAlex Tomas colour = (current->pid % 16) * 179a86c6181SAlex Tomas (EXT4_BLOCKS_PER_GROUP(inode->i_sb) / 16); 18074d3487fSValerie Clement else 18174d3487fSValerie Clement colour = (current->pid % 16) * ((last_block - bg_start) / 16); 182a86c6181SAlex Tomas return bg_start + colour + block; 183a86c6181SAlex Tomas } 184a86c6181SAlex Tomas 185654b4908SAneesh Kumar K.V /* 186654b4908SAneesh Kumar K.V * Allocation for a meta data block 187654b4908SAneesh Kumar K.V */ 188f65e6fbaSAlex Tomas static ext4_fsblk_t 189654b4908SAneesh Kumar K.V ext4_ext_new_meta_block(handle_t *handle, struct inode *inode, 190a86c6181SAlex Tomas struct ext4_ext_path *path, 191a86c6181SAlex Tomas struct ext4_extent *ex, int *err) 192a86c6181SAlex Tomas { 193f65e6fbaSAlex Tomas ext4_fsblk_t goal, newblock; 194a86c6181SAlex Tomas 195a86c6181SAlex Tomas goal = ext4_ext_find_goal(inode, path, le32_to_cpu(ex->ee_block)); 19697df5d15STheodore Ts'o newblock = ext4_new_meta_blocks(handle, inode, goal, NULL, err); 197a86c6181SAlex Tomas return newblock; 198a86c6181SAlex Tomas } 199a86c6181SAlex Tomas 20009b88252SAvantika Mathur static int ext4_ext_space_block(struct inode *inode) 201a86c6181SAlex Tomas { 202a86c6181SAlex Tomas int size; 203a86c6181SAlex Tomas 204a86c6181SAlex Tomas size = (inode->i_sb->s_blocksize - sizeof(struct ext4_extent_header)) 205a86c6181SAlex Tomas / sizeof(struct ext4_extent); 206bbf2f9fbSRobert P. J. Day #ifdef AGGRESSIVE_TEST 207a86c6181SAlex Tomas if (size > 6) 208a86c6181SAlex Tomas size = 6; 209a86c6181SAlex Tomas #endif 210a86c6181SAlex Tomas return size; 211a86c6181SAlex Tomas } 212a86c6181SAlex Tomas 21309b88252SAvantika Mathur static int ext4_ext_space_block_idx(struct inode *inode) 214a86c6181SAlex Tomas { 215a86c6181SAlex Tomas int size; 216a86c6181SAlex Tomas 217a86c6181SAlex Tomas size = (inode->i_sb->s_blocksize - sizeof(struct ext4_extent_header)) 218a86c6181SAlex Tomas / sizeof(struct ext4_extent_idx); 219bbf2f9fbSRobert P. J. Day #ifdef AGGRESSIVE_TEST 220a86c6181SAlex Tomas if (size > 5) 221a86c6181SAlex Tomas size = 5; 222a86c6181SAlex Tomas #endif 223a86c6181SAlex Tomas return size; 224a86c6181SAlex Tomas } 225a86c6181SAlex Tomas 22609b88252SAvantika Mathur static int ext4_ext_space_root(struct inode *inode) 227a86c6181SAlex Tomas { 228a86c6181SAlex Tomas int size; 229a86c6181SAlex Tomas 230a86c6181SAlex Tomas size = sizeof(EXT4_I(inode)->i_data); 231a86c6181SAlex Tomas size -= sizeof(struct ext4_extent_header); 232a86c6181SAlex Tomas size /= sizeof(struct ext4_extent); 233bbf2f9fbSRobert P. J. Day #ifdef AGGRESSIVE_TEST 234a86c6181SAlex Tomas if (size > 3) 235a86c6181SAlex Tomas size = 3; 236a86c6181SAlex Tomas #endif 237a86c6181SAlex Tomas return size; 238a86c6181SAlex Tomas } 239a86c6181SAlex Tomas 24009b88252SAvantika Mathur static int ext4_ext_space_root_idx(struct inode *inode) 241a86c6181SAlex Tomas { 242a86c6181SAlex Tomas int size; 243a86c6181SAlex Tomas 244a86c6181SAlex Tomas size = sizeof(EXT4_I(inode)->i_data); 245a86c6181SAlex Tomas size -= sizeof(struct ext4_extent_header); 246a86c6181SAlex Tomas size /= sizeof(struct ext4_extent_idx); 247bbf2f9fbSRobert P. J. Day #ifdef AGGRESSIVE_TEST 248a86c6181SAlex Tomas if (size > 4) 249a86c6181SAlex Tomas size = 4; 250a86c6181SAlex Tomas #endif 251a86c6181SAlex Tomas return size; 252a86c6181SAlex Tomas } 253a86c6181SAlex Tomas 254d2a17637SMingming Cao /* 255d2a17637SMingming Cao * Calculate the number of metadata blocks needed 256d2a17637SMingming Cao * to allocate @blocks 257d2a17637SMingming Cao * Worse case is one block per extent 258d2a17637SMingming Cao */ 259d2a17637SMingming Cao int ext4_ext_calc_metadata_amount(struct inode *inode, int blocks) 260d2a17637SMingming Cao { 261d2a17637SMingming Cao int lcap, icap, rcap, leafs, idxs, num; 262d2a17637SMingming Cao int newextents = blocks; 263d2a17637SMingming Cao 264d2a17637SMingming Cao rcap = ext4_ext_space_root_idx(inode); 265d2a17637SMingming Cao lcap = ext4_ext_space_block(inode); 266d2a17637SMingming Cao icap = ext4_ext_space_block_idx(inode); 267d2a17637SMingming Cao 268d2a17637SMingming Cao /* number of new leaf blocks needed */ 269d2a17637SMingming Cao num = leafs = (newextents + lcap - 1) / lcap; 270d2a17637SMingming Cao 271d2a17637SMingming Cao /* 272d2a17637SMingming Cao * Worse case, we need separate index block(s) 273d2a17637SMingming Cao * to link all new leaf blocks 274d2a17637SMingming Cao */ 275d2a17637SMingming Cao idxs = (leafs + icap - 1) / icap; 276d2a17637SMingming Cao do { 277d2a17637SMingming Cao num += idxs; 278d2a17637SMingming Cao idxs = (idxs + icap - 1) / icap; 279d2a17637SMingming Cao } while (idxs > rcap); 280d2a17637SMingming Cao 281d2a17637SMingming Cao return num; 282d2a17637SMingming Cao } 283d2a17637SMingming Cao 284c29c0ae7SAlex Tomas static int 285c29c0ae7SAlex Tomas ext4_ext_max_entries(struct inode *inode, int depth) 286c29c0ae7SAlex Tomas { 287c29c0ae7SAlex Tomas int max; 288c29c0ae7SAlex Tomas 289c29c0ae7SAlex Tomas if (depth == ext_depth(inode)) { 290c29c0ae7SAlex Tomas if (depth == 0) 291c29c0ae7SAlex Tomas max = ext4_ext_space_root(inode); 292c29c0ae7SAlex Tomas else 293c29c0ae7SAlex Tomas max = ext4_ext_space_root_idx(inode); 294c29c0ae7SAlex Tomas } else { 295c29c0ae7SAlex Tomas if (depth == 0) 296c29c0ae7SAlex Tomas max = ext4_ext_space_block(inode); 297c29c0ae7SAlex Tomas else 298c29c0ae7SAlex Tomas max = ext4_ext_space_block_idx(inode); 299c29c0ae7SAlex Tomas } 300c29c0ae7SAlex Tomas 301c29c0ae7SAlex Tomas return max; 302c29c0ae7SAlex Tomas } 303c29c0ae7SAlex Tomas 304c29c0ae7SAlex Tomas static int __ext4_ext_check_header(const char *function, struct inode *inode, 305c29c0ae7SAlex Tomas struct ext4_extent_header *eh, 306c29c0ae7SAlex Tomas int depth) 307c29c0ae7SAlex Tomas { 308c29c0ae7SAlex Tomas const char *error_msg; 309c29c0ae7SAlex Tomas int max = 0; 310c29c0ae7SAlex Tomas 311c29c0ae7SAlex Tomas if (unlikely(eh->eh_magic != EXT4_EXT_MAGIC)) { 312c29c0ae7SAlex Tomas error_msg = "invalid magic"; 313c29c0ae7SAlex Tomas goto corrupted; 314c29c0ae7SAlex Tomas } 315c29c0ae7SAlex Tomas if (unlikely(le16_to_cpu(eh->eh_depth) != depth)) { 316c29c0ae7SAlex Tomas error_msg = "unexpected eh_depth"; 317c29c0ae7SAlex Tomas goto corrupted; 318c29c0ae7SAlex Tomas } 319c29c0ae7SAlex Tomas if (unlikely(eh->eh_max == 0)) { 320c29c0ae7SAlex Tomas error_msg = "invalid eh_max"; 321c29c0ae7SAlex Tomas goto corrupted; 322c29c0ae7SAlex Tomas } 323c29c0ae7SAlex Tomas max = ext4_ext_max_entries(inode, depth); 324c29c0ae7SAlex Tomas if (unlikely(le16_to_cpu(eh->eh_max) > max)) { 325c29c0ae7SAlex Tomas error_msg = "too large eh_max"; 326c29c0ae7SAlex Tomas goto corrupted; 327c29c0ae7SAlex Tomas } 328c29c0ae7SAlex Tomas if (unlikely(le16_to_cpu(eh->eh_entries) > le16_to_cpu(eh->eh_max))) { 329c29c0ae7SAlex Tomas error_msg = "invalid eh_entries"; 330c29c0ae7SAlex Tomas goto corrupted; 331c29c0ae7SAlex Tomas } 332c29c0ae7SAlex Tomas return 0; 333c29c0ae7SAlex Tomas 334c29c0ae7SAlex Tomas corrupted: 335c29c0ae7SAlex Tomas ext4_error(inode->i_sb, function, 336c29c0ae7SAlex Tomas "bad header in inode #%lu: %s - magic %x, " 337c29c0ae7SAlex Tomas "entries %u, max %u(%u), depth %u(%u)", 338c29c0ae7SAlex Tomas inode->i_ino, error_msg, le16_to_cpu(eh->eh_magic), 339c29c0ae7SAlex Tomas le16_to_cpu(eh->eh_entries), le16_to_cpu(eh->eh_max), 340c29c0ae7SAlex Tomas max, le16_to_cpu(eh->eh_depth), depth); 341c29c0ae7SAlex Tomas 342c29c0ae7SAlex Tomas return -EIO; 343c29c0ae7SAlex Tomas } 344c29c0ae7SAlex Tomas 345c29c0ae7SAlex Tomas #define ext4_ext_check_header(inode, eh, depth) \ 34646e665e9SHarvey Harrison __ext4_ext_check_header(__func__, inode, eh, depth) 347c29c0ae7SAlex Tomas 348a86c6181SAlex Tomas #ifdef EXT_DEBUG 349a86c6181SAlex Tomas static void ext4_ext_show_path(struct inode *inode, struct ext4_ext_path *path) 350a86c6181SAlex Tomas { 351a86c6181SAlex Tomas int k, l = path->p_depth; 352a86c6181SAlex Tomas 353a86c6181SAlex Tomas ext_debug("path:"); 354a86c6181SAlex Tomas for (k = 0; k <= l; k++, path++) { 355a86c6181SAlex Tomas if (path->p_idx) { 3562ae02107SMingming Cao ext_debug(" %d->%llu", le32_to_cpu(path->p_idx->ei_block), 357f65e6fbaSAlex Tomas idx_pblock(path->p_idx)); 358a86c6181SAlex Tomas } else if (path->p_ext) { 3592ae02107SMingming Cao ext_debug(" %d:%d:%llu ", 360a86c6181SAlex Tomas le32_to_cpu(path->p_ext->ee_block), 361a2df2a63SAmit Arora ext4_ext_get_actual_len(path->p_ext), 362f65e6fbaSAlex Tomas ext_pblock(path->p_ext)); 363a86c6181SAlex Tomas } else 364a86c6181SAlex Tomas ext_debug(" []"); 365a86c6181SAlex Tomas } 366a86c6181SAlex Tomas ext_debug("\n"); 367a86c6181SAlex Tomas } 368a86c6181SAlex Tomas 369a86c6181SAlex Tomas static void ext4_ext_show_leaf(struct inode *inode, struct ext4_ext_path *path) 370a86c6181SAlex Tomas { 371a86c6181SAlex Tomas int depth = ext_depth(inode); 372a86c6181SAlex Tomas struct ext4_extent_header *eh; 373a86c6181SAlex Tomas struct ext4_extent *ex; 374a86c6181SAlex Tomas int i; 375a86c6181SAlex Tomas 376a86c6181SAlex Tomas if (!path) 377a86c6181SAlex Tomas return; 378a86c6181SAlex Tomas 379a86c6181SAlex Tomas eh = path[depth].p_hdr; 380a86c6181SAlex Tomas ex = EXT_FIRST_EXTENT(eh); 381a86c6181SAlex Tomas 382a86c6181SAlex Tomas for (i = 0; i < le16_to_cpu(eh->eh_entries); i++, ex++) { 3832ae02107SMingming Cao ext_debug("%d:%d:%llu ", le32_to_cpu(ex->ee_block), 384a2df2a63SAmit Arora ext4_ext_get_actual_len(ex), ext_pblock(ex)); 385a86c6181SAlex Tomas } 386a86c6181SAlex Tomas ext_debug("\n"); 387a86c6181SAlex Tomas } 388a86c6181SAlex Tomas #else 389a86c6181SAlex Tomas #define ext4_ext_show_path(inode, path) 390a86c6181SAlex Tomas #define ext4_ext_show_leaf(inode, path) 391a86c6181SAlex Tomas #endif 392a86c6181SAlex Tomas 393b35905c1SAneesh Kumar K.V void ext4_ext_drop_refs(struct ext4_ext_path *path) 394a86c6181SAlex Tomas { 395a86c6181SAlex Tomas int depth = path->p_depth; 396a86c6181SAlex Tomas int i; 397a86c6181SAlex Tomas 398a86c6181SAlex Tomas for (i = 0; i <= depth; i++, path++) 399a86c6181SAlex Tomas if (path->p_bh) { 400a86c6181SAlex Tomas brelse(path->p_bh); 401a86c6181SAlex Tomas path->p_bh = NULL; 402a86c6181SAlex Tomas } 403a86c6181SAlex Tomas } 404a86c6181SAlex Tomas 405a86c6181SAlex Tomas /* 406d0d856e8SRandy Dunlap * ext4_ext_binsearch_idx: 407d0d856e8SRandy Dunlap * binary search for the closest index of the given block 408c29c0ae7SAlex Tomas * the header must be checked before calling this 409a86c6181SAlex Tomas */ 410a86c6181SAlex Tomas static void 411725d26d3SAneesh Kumar K.V ext4_ext_binsearch_idx(struct inode *inode, 412725d26d3SAneesh Kumar K.V struct ext4_ext_path *path, ext4_lblk_t block) 413a86c6181SAlex Tomas { 414a86c6181SAlex Tomas struct ext4_extent_header *eh = path->p_hdr; 415a86c6181SAlex Tomas struct ext4_extent_idx *r, *l, *m; 416a86c6181SAlex Tomas 417a86c6181SAlex Tomas 418bba90743SEric Sandeen ext_debug("binsearch for %u(idx): ", block); 419a86c6181SAlex Tomas 420a86c6181SAlex Tomas l = EXT_FIRST_INDEX(eh) + 1; 421e9f410b1SDmitry Monakhov r = EXT_LAST_INDEX(eh); 422a86c6181SAlex Tomas while (l <= r) { 423a86c6181SAlex Tomas m = l + (r - l) / 2; 424a86c6181SAlex Tomas if (block < le32_to_cpu(m->ei_block)) 425a86c6181SAlex Tomas r = m - 1; 426a86c6181SAlex Tomas else 427a86c6181SAlex Tomas l = m + 1; 42826d535edSDmitry Monakhov ext_debug("%p(%u):%p(%u):%p(%u) ", l, le32_to_cpu(l->ei_block), 42926d535edSDmitry Monakhov m, le32_to_cpu(m->ei_block), 43026d535edSDmitry Monakhov r, le32_to_cpu(r->ei_block)); 431a86c6181SAlex Tomas } 432a86c6181SAlex Tomas 433a86c6181SAlex Tomas path->p_idx = l - 1; 434f65e6fbaSAlex Tomas ext_debug(" -> %d->%lld ", le32_to_cpu(path->p_idx->ei_block), 43526d535edSDmitry Monakhov idx_pblock(path->p_idx)); 436a86c6181SAlex Tomas 437a86c6181SAlex Tomas #ifdef CHECK_BINSEARCH 438a86c6181SAlex Tomas { 439a86c6181SAlex Tomas struct ext4_extent_idx *chix, *ix; 440a86c6181SAlex Tomas int k; 441a86c6181SAlex Tomas 442a86c6181SAlex Tomas chix = ix = EXT_FIRST_INDEX(eh); 443a86c6181SAlex Tomas for (k = 0; k < le16_to_cpu(eh->eh_entries); k++, ix++) { 444a86c6181SAlex Tomas if (k != 0 && 445a86c6181SAlex Tomas le32_to_cpu(ix->ei_block) <= le32_to_cpu(ix[-1].ei_block)) { 4464776004fSTheodore Ts'o printk(KERN_DEBUG "k=%d, ix=0x%p, " 4474776004fSTheodore Ts'o "first=0x%p\n", k, 448a86c6181SAlex Tomas ix, EXT_FIRST_INDEX(eh)); 4494776004fSTheodore Ts'o printk(KERN_DEBUG "%u <= %u\n", 450a86c6181SAlex Tomas le32_to_cpu(ix->ei_block), 451a86c6181SAlex Tomas le32_to_cpu(ix[-1].ei_block)); 452a86c6181SAlex Tomas } 453a86c6181SAlex Tomas BUG_ON(k && le32_to_cpu(ix->ei_block) 454a86c6181SAlex Tomas <= le32_to_cpu(ix[-1].ei_block)); 455a86c6181SAlex Tomas if (block < le32_to_cpu(ix->ei_block)) 456a86c6181SAlex Tomas break; 457a86c6181SAlex Tomas chix = ix; 458a86c6181SAlex Tomas } 459a86c6181SAlex Tomas BUG_ON(chix != path->p_idx); 460a86c6181SAlex Tomas } 461a86c6181SAlex Tomas #endif 462a86c6181SAlex Tomas 463a86c6181SAlex Tomas } 464a86c6181SAlex Tomas 465a86c6181SAlex Tomas /* 466d0d856e8SRandy Dunlap * ext4_ext_binsearch: 467d0d856e8SRandy Dunlap * binary search for closest extent of the given block 468c29c0ae7SAlex Tomas * the header must be checked before calling this 469a86c6181SAlex Tomas */ 470a86c6181SAlex Tomas static void 471725d26d3SAneesh Kumar K.V ext4_ext_binsearch(struct inode *inode, 472725d26d3SAneesh Kumar K.V struct ext4_ext_path *path, ext4_lblk_t block) 473a86c6181SAlex Tomas { 474a86c6181SAlex Tomas struct ext4_extent_header *eh = path->p_hdr; 475a86c6181SAlex Tomas struct ext4_extent *r, *l, *m; 476a86c6181SAlex Tomas 477a86c6181SAlex Tomas if (eh->eh_entries == 0) { 478a86c6181SAlex Tomas /* 479d0d856e8SRandy Dunlap * this leaf is empty: 480a86c6181SAlex Tomas * we get such a leaf in split/add case 481a86c6181SAlex Tomas */ 482a86c6181SAlex Tomas return; 483a86c6181SAlex Tomas } 484a86c6181SAlex Tomas 485bba90743SEric Sandeen ext_debug("binsearch for %u: ", block); 486a86c6181SAlex Tomas 487a86c6181SAlex Tomas l = EXT_FIRST_EXTENT(eh) + 1; 488e9f410b1SDmitry Monakhov r = EXT_LAST_EXTENT(eh); 489a86c6181SAlex Tomas 490a86c6181SAlex Tomas while (l <= r) { 491a86c6181SAlex Tomas m = l + (r - l) / 2; 492a86c6181SAlex Tomas if (block < le32_to_cpu(m->ee_block)) 493a86c6181SAlex Tomas r = m - 1; 494a86c6181SAlex Tomas else 495a86c6181SAlex Tomas l = m + 1; 49626d535edSDmitry Monakhov ext_debug("%p(%u):%p(%u):%p(%u) ", l, le32_to_cpu(l->ee_block), 49726d535edSDmitry Monakhov m, le32_to_cpu(m->ee_block), 49826d535edSDmitry Monakhov r, le32_to_cpu(r->ee_block)); 499a86c6181SAlex Tomas } 500a86c6181SAlex Tomas 501a86c6181SAlex Tomas path->p_ext = l - 1; 5022ae02107SMingming Cao ext_debug(" -> %d:%llu:%d ", 503a86c6181SAlex Tomas le32_to_cpu(path->p_ext->ee_block), 504f65e6fbaSAlex Tomas ext_pblock(path->p_ext), 505a2df2a63SAmit Arora ext4_ext_get_actual_len(path->p_ext)); 506a86c6181SAlex Tomas 507a86c6181SAlex Tomas #ifdef CHECK_BINSEARCH 508a86c6181SAlex Tomas { 509a86c6181SAlex Tomas struct ext4_extent *chex, *ex; 510a86c6181SAlex Tomas int k; 511a86c6181SAlex Tomas 512a86c6181SAlex Tomas chex = ex = EXT_FIRST_EXTENT(eh); 513a86c6181SAlex Tomas for (k = 0; k < le16_to_cpu(eh->eh_entries); k++, ex++) { 514a86c6181SAlex Tomas BUG_ON(k && le32_to_cpu(ex->ee_block) 515a86c6181SAlex Tomas <= le32_to_cpu(ex[-1].ee_block)); 516a86c6181SAlex Tomas if (block < le32_to_cpu(ex->ee_block)) 517a86c6181SAlex Tomas break; 518a86c6181SAlex Tomas chex = ex; 519a86c6181SAlex Tomas } 520a86c6181SAlex Tomas BUG_ON(chex != path->p_ext); 521a86c6181SAlex Tomas } 522a86c6181SAlex Tomas #endif 523a86c6181SAlex Tomas 524a86c6181SAlex Tomas } 525a86c6181SAlex Tomas 526a86c6181SAlex Tomas int ext4_ext_tree_init(handle_t *handle, struct inode *inode) 527a86c6181SAlex Tomas { 528a86c6181SAlex Tomas struct ext4_extent_header *eh; 529a86c6181SAlex Tomas 530a86c6181SAlex Tomas eh = ext_inode_hdr(inode); 531a86c6181SAlex Tomas eh->eh_depth = 0; 532a86c6181SAlex Tomas eh->eh_entries = 0; 533a86c6181SAlex Tomas eh->eh_magic = EXT4_EXT_MAGIC; 534a86c6181SAlex Tomas eh->eh_max = cpu_to_le16(ext4_ext_space_root(inode)); 535a86c6181SAlex Tomas ext4_mark_inode_dirty(handle, inode); 536a86c6181SAlex Tomas ext4_ext_invalidate_cache(inode); 537a86c6181SAlex Tomas return 0; 538a86c6181SAlex Tomas } 539a86c6181SAlex Tomas 540a86c6181SAlex Tomas struct ext4_ext_path * 541725d26d3SAneesh Kumar K.V ext4_ext_find_extent(struct inode *inode, ext4_lblk_t block, 542725d26d3SAneesh Kumar K.V struct ext4_ext_path *path) 543a86c6181SAlex Tomas { 544a86c6181SAlex Tomas struct ext4_extent_header *eh; 545a86c6181SAlex Tomas struct buffer_head *bh; 546a86c6181SAlex Tomas short int depth, i, ppos = 0, alloc = 0; 547a86c6181SAlex Tomas 548a86c6181SAlex Tomas eh = ext_inode_hdr(inode); 549c29c0ae7SAlex Tomas depth = ext_depth(inode); 550c29c0ae7SAlex Tomas if (ext4_ext_check_header(inode, eh, depth)) 551a86c6181SAlex Tomas return ERR_PTR(-EIO); 552a86c6181SAlex Tomas 553a86c6181SAlex Tomas 554a86c6181SAlex Tomas /* account possible depth increase */ 555a86c6181SAlex Tomas if (!path) { 5565d4958f9SAvantika Mathur path = kzalloc(sizeof(struct ext4_ext_path) * (depth + 2), 557a86c6181SAlex Tomas GFP_NOFS); 558a86c6181SAlex Tomas if (!path) 559a86c6181SAlex Tomas return ERR_PTR(-ENOMEM); 560a86c6181SAlex Tomas alloc = 1; 561a86c6181SAlex Tomas } 562a86c6181SAlex Tomas path[0].p_hdr = eh; 5631973adcbSShen Feng path[0].p_bh = NULL; 564a86c6181SAlex Tomas 565c29c0ae7SAlex Tomas i = depth; 566a86c6181SAlex Tomas /* walk through the tree */ 567a86c6181SAlex Tomas while (i) { 568a86c6181SAlex Tomas ext_debug("depth %d: num %d, max %d\n", 569a86c6181SAlex Tomas ppos, le16_to_cpu(eh->eh_entries), le16_to_cpu(eh->eh_max)); 570c29c0ae7SAlex Tomas 571a86c6181SAlex Tomas ext4_ext_binsearch_idx(inode, path + ppos, block); 572f65e6fbaSAlex Tomas path[ppos].p_block = idx_pblock(path[ppos].p_idx); 573a86c6181SAlex Tomas path[ppos].p_depth = i; 574a86c6181SAlex Tomas path[ppos].p_ext = NULL; 575a86c6181SAlex Tomas 576a86c6181SAlex Tomas bh = sb_bread(inode->i_sb, path[ppos].p_block); 577a86c6181SAlex Tomas if (!bh) 578a86c6181SAlex Tomas goto err; 579a86c6181SAlex Tomas 580a86c6181SAlex Tomas eh = ext_block_hdr(bh); 581a86c6181SAlex Tomas ppos++; 582a86c6181SAlex Tomas BUG_ON(ppos > depth); 583a86c6181SAlex Tomas path[ppos].p_bh = bh; 584a86c6181SAlex Tomas path[ppos].p_hdr = eh; 585a86c6181SAlex Tomas i--; 586a86c6181SAlex Tomas 587c29c0ae7SAlex Tomas if (ext4_ext_check_header(inode, eh, i)) 588a86c6181SAlex Tomas goto err; 589a86c6181SAlex Tomas } 590a86c6181SAlex Tomas 591a86c6181SAlex Tomas path[ppos].p_depth = i; 592a86c6181SAlex Tomas path[ppos].p_ext = NULL; 593a86c6181SAlex Tomas path[ppos].p_idx = NULL; 594a86c6181SAlex Tomas 595a86c6181SAlex Tomas /* find extent */ 596a86c6181SAlex Tomas ext4_ext_binsearch(inode, path + ppos, block); 5971973adcbSShen Feng /* if not an empty leaf */ 5981973adcbSShen Feng if (path[ppos].p_ext) 5991973adcbSShen Feng path[ppos].p_block = ext_pblock(path[ppos].p_ext); 600a86c6181SAlex Tomas 601a86c6181SAlex Tomas ext4_ext_show_path(inode, path); 602a86c6181SAlex Tomas 603a86c6181SAlex Tomas return path; 604a86c6181SAlex Tomas 605a86c6181SAlex Tomas err: 606a86c6181SAlex Tomas ext4_ext_drop_refs(path); 607a86c6181SAlex Tomas if (alloc) 608a86c6181SAlex Tomas kfree(path); 609a86c6181SAlex Tomas return ERR_PTR(-EIO); 610a86c6181SAlex Tomas } 611a86c6181SAlex Tomas 612a86c6181SAlex Tomas /* 613d0d856e8SRandy Dunlap * ext4_ext_insert_index: 614d0d856e8SRandy Dunlap * insert new index [@logical;@ptr] into the block at @curp; 615d0d856e8SRandy Dunlap * check where to insert: before @curp or after @curp 616a86c6181SAlex Tomas */ 617a86c6181SAlex Tomas static int ext4_ext_insert_index(handle_t *handle, struct inode *inode, 618a86c6181SAlex Tomas struct ext4_ext_path *curp, 619f65e6fbaSAlex Tomas int logical, ext4_fsblk_t ptr) 620a86c6181SAlex Tomas { 621a86c6181SAlex Tomas struct ext4_extent_idx *ix; 622a86c6181SAlex Tomas int len, err; 623a86c6181SAlex Tomas 6247e028976SAvantika Mathur err = ext4_ext_get_access(handle, inode, curp); 6257e028976SAvantika Mathur if (err) 626a86c6181SAlex Tomas return err; 627a86c6181SAlex Tomas 628a86c6181SAlex Tomas BUG_ON(logical == le32_to_cpu(curp->p_idx->ei_block)); 629a86c6181SAlex Tomas len = EXT_MAX_INDEX(curp->p_hdr) - curp->p_idx; 630a86c6181SAlex Tomas if (logical > le32_to_cpu(curp->p_idx->ei_block)) { 631a86c6181SAlex Tomas /* insert after */ 632a86c6181SAlex Tomas if (curp->p_idx != EXT_LAST_INDEX(curp->p_hdr)) { 633a86c6181SAlex Tomas len = (len - 1) * sizeof(struct ext4_extent_idx); 634a86c6181SAlex Tomas len = len < 0 ? 0 : len; 63526d535edSDmitry Monakhov ext_debug("insert new index %d after: %llu. " 636a86c6181SAlex Tomas "move %d from 0x%p to 0x%p\n", 637a86c6181SAlex Tomas logical, ptr, len, 638a86c6181SAlex Tomas (curp->p_idx + 1), (curp->p_idx + 2)); 639a86c6181SAlex Tomas memmove(curp->p_idx + 2, curp->p_idx + 1, len); 640a86c6181SAlex Tomas } 641a86c6181SAlex Tomas ix = curp->p_idx + 1; 642a86c6181SAlex Tomas } else { 643a86c6181SAlex Tomas /* insert before */ 644a86c6181SAlex Tomas len = len * sizeof(struct ext4_extent_idx); 645a86c6181SAlex Tomas len = len < 0 ? 0 : len; 64626d535edSDmitry Monakhov ext_debug("insert new index %d before: %llu. " 647a86c6181SAlex Tomas "move %d from 0x%p to 0x%p\n", 648a86c6181SAlex Tomas logical, ptr, len, 649a86c6181SAlex Tomas curp->p_idx, (curp->p_idx + 1)); 650a86c6181SAlex Tomas memmove(curp->p_idx + 1, curp->p_idx, len); 651a86c6181SAlex Tomas ix = curp->p_idx; 652a86c6181SAlex Tomas } 653a86c6181SAlex Tomas 654a86c6181SAlex Tomas ix->ei_block = cpu_to_le32(logical); 655f65e6fbaSAlex Tomas ext4_idx_store_pblock(ix, ptr); 656e8546d06SMarcin Slusarz le16_add_cpu(&curp->p_hdr->eh_entries, 1); 657a86c6181SAlex Tomas 658a86c6181SAlex Tomas BUG_ON(le16_to_cpu(curp->p_hdr->eh_entries) 659a86c6181SAlex Tomas > le16_to_cpu(curp->p_hdr->eh_max)); 660a86c6181SAlex Tomas BUG_ON(ix > EXT_LAST_INDEX(curp->p_hdr)); 661a86c6181SAlex Tomas 662a86c6181SAlex Tomas err = ext4_ext_dirty(handle, inode, curp); 663a86c6181SAlex Tomas ext4_std_error(inode->i_sb, err); 664a86c6181SAlex Tomas 665a86c6181SAlex Tomas return err; 666a86c6181SAlex Tomas } 667a86c6181SAlex Tomas 668a86c6181SAlex Tomas /* 669d0d856e8SRandy Dunlap * ext4_ext_split: 670d0d856e8SRandy Dunlap * inserts new subtree into the path, using free index entry 671d0d856e8SRandy Dunlap * at depth @at: 672a86c6181SAlex Tomas * - allocates all needed blocks (new leaf and all intermediate index blocks) 673a86c6181SAlex Tomas * - makes decision where to split 674d0d856e8SRandy Dunlap * - moves remaining extents and index entries (right to the split point) 675a86c6181SAlex Tomas * into the newly allocated blocks 676d0d856e8SRandy Dunlap * - initializes subtree 677a86c6181SAlex Tomas */ 678a86c6181SAlex Tomas static int ext4_ext_split(handle_t *handle, struct inode *inode, 679a86c6181SAlex Tomas struct ext4_ext_path *path, 680a86c6181SAlex Tomas struct ext4_extent *newext, int at) 681a86c6181SAlex Tomas { 682a86c6181SAlex Tomas struct buffer_head *bh = NULL; 683a86c6181SAlex Tomas int depth = ext_depth(inode); 684a86c6181SAlex Tomas struct ext4_extent_header *neh; 685a86c6181SAlex Tomas struct ext4_extent_idx *fidx; 686a86c6181SAlex Tomas struct ext4_extent *ex; 687a86c6181SAlex Tomas int i = at, k, m, a; 688f65e6fbaSAlex Tomas ext4_fsblk_t newblock, oldblock; 689a86c6181SAlex Tomas __le32 border; 690f65e6fbaSAlex Tomas ext4_fsblk_t *ablocks = NULL; /* array of allocated blocks */ 691a86c6181SAlex Tomas int err = 0; 692a86c6181SAlex Tomas 693a86c6181SAlex Tomas /* make decision: where to split? */ 694d0d856e8SRandy Dunlap /* FIXME: now decision is simplest: at current extent */ 695a86c6181SAlex Tomas 696d0d856e8SRandy Dunlap /* if current leaf will be split, then we should use 697a86c6181SAlex Tomas * border from split point */ 698a86c6181SAlex Tomas BUG_ON(path[depth].p_ext > EXT_MAX_EXTENT(path[depth].p_hdr)); 699a86c6181SAlex Tomas if (path[depth].p_ext != EXT_MAX_EXTENT(path[depth].p_hdr)) { 700a86c6181SAlex Tomas border = path[depth].p_ext[1].ee_block; 701d0d856e8SRandy Dunlap ext_debug("leaf will be split." 702a86c6181SAlex Tomas " next leaf starts at %d\n", 703a86c6181SAlex Tomas le32_to_cpu(border)); 704a86c6181SAlex Tomas } else { 705a86c6181SAlex Tomas border = newext->ee_block; 706a86c6181SAlex Tomas ext_debug("leaf will be added." 707a86c6181SAlex Tomas " next leaf starts at %d\n", 708a86c6181SAlex Tomas le32_to_cpu(border)); 709a86c6181SAlex Tomas } 710a86c6181SAlex Tomas 711a86c6181SAlex Tomas /* 712d0d856e8SRandy Dunlap * If error occurs, then we break processing 713d0d856e8SRandy Dunlap * and mark filesystem read-only. index won't 714a86c6181SAlex Tomas * be inserted and tree will be in consistent 715d0d856e8SRandy Dunlap * state. Next mount will repair buffers too. 716a86c6181SAlex Tomas */ 717a86c6181SAlex Tomas 718a86c6181SAlex Tomas /* 719d0d856e8SRandy Dunlap * Get array to track all allocated blocks. 720d0d856e8SRandy Dunlap * We need this to handle errors and free blocks 721d0d856e8SRandy Dunlap * upon them. 722a86c6181SAlex Tomas */ 7235d4958f9SAvantika Mathur ablocks = kzalloc(sizeof(ext4_fsblk_t) * depth, GFP_NOFS); 724a86c6181SAlex Tomas if (!ablocks) 725a86c6181SAlex Tomas return -ENOMEM; 726a86c6181SAlex Tomas 727a86c6181SAlex Tomas /* allocate all needed blocks */ 728a86c6181SAlex Tomas ext_debug("allocate %d blocks for indexes/leaf\n", depth - at); 729a86c6181SAlex Tomas for (a = 0; a < depth - at; a++) { 730654b4908SAneesh Kumar K.V newblock = ext4_ext_new_meta_block(handle, inode, path, 731654b4908SAneesh Kumar K.V newext, &err); 732a86c6181SAlex Tomas if (newblock == 0) 733a86c6181SAlex Tomas goto cleanup; 734a86c6181SAlex Tomas ablocks[a] = newblock; 735a86c6181SAlex Tomas } 736a86c6181SAlex Tomas 737a86c6181SAlex Tomas /* initialize new leaf */ 738a86c6181SAlex Tomas newblock = ablocks[--a]; 739a86c6181SAlex Tomas BUG_ON(newblock == 0); 740a86c6181SAlex Tomas bh = sb_getblk(inode->i_sb, newblock); 741a86c6181SAlex Tomas if (!bh) { 742a86c6181SAlex Tomas err = -EIO; 743a86c6181SAlex Tomas goto cleanup; 744a86c6181SAlex Tomas } 745a86c6181SAlex Tomas lock_buffer(bh); 746a86c6181SAlex Tomas 7477e028976SAvantika Mathur err = ext4_journal_get_create_access(handle, bh); 7487e028976SAvantika Mathur if (err) 749a86c6181SAlex Tomas goto cleanup; 750a86c6181SAlex Tomas 751a86c6181SAlex Tomas neh = ext_block_hdr(bh); 752a86c6181SAlex Tomas neh->eh_entries = 0; 753a86c6181SAlex Tomas neh->eh_max = cpu_to_le16(ext4_ext_space_block(inode)); 754a86c6181SAlex Tomas neh->eh_magic = EXT4_EXT_MAGIC; 755a86c6181SAlex Tomas neh->eh_depth = 0; 756a86c6181SAlex Tomas ex = EXT_FIRST_EXTENT(neh); 757a86c6181SAlex Tomas 758d0d856e8SRandy Dunlap /* move remainder of path[depth] to the new leaf */ 759a86c6181SAlex Tomas BUG_ON(path[depth].p_hdr->eh_entries != path[depth].p_hdr->eh_max); 760a86c6181SAlex Tomas /* start copy from next extent */ 761a86c6181SAlex Tomas /* TODO: we could do it by single memmove */ 762a86c6181SAlex Tomas m = 0; 763a86c6181SAlex Tomas path[depth].p_ext++; 764a86c6181SAlex Tomas while (path[depth].p_ext <= 765a86c6181SAlex Tomas EXT_MAX_EXTENT(path[depth].p_hdr)) { 7662ae02107SMingming Cao ext_debug("move %d:%llu:%d in new leaf %llu\n", 767a86c6181SAlex Tomas le32_to_cpu(path[depth].p_ext->ee_block), 768f65e6fbaSAlex Tomas ext_pblock(path[depth].p_ext), 769a2df2a63SAmit Arora ext4_ext_get_actual_len(path[depth].p_ext), 770a86c6181SAlex Tomas newblock); 771a86c6181SAlex Tomas /*memmove(ex++, path[depth].p_ext++, 772a86c6181SAlex Tomas sizeof(struct ext4_extent)); 773a86c6181SAlex Tomas neh->eh_entries++;*/ 774a86c6181SAlex Tomas path[depth].p_ext++; 775a86c6181SAlex Tomas m++; 776a86c6181SAlex Tomas } 777a86c6181SAlex Tomas if (m) { 778a86c6181SAlex Tomas memmove(ex, path[depth].p_ext-m, sizeof(struct ext4_extent)*m); 779e8546d06SMarcin Slusarz le16_add_cpu(&neh->eh_entries, m); 780a86c6181SAlex Tomas } 781a86c6181SAlex Tomas 782a86c6181SAlex Tomas set_buffer_uptodate(bh); 783a86c6181SAlex Tomas unlock_buffer(bh); 784a86c6181SAlex Tomas 7850390131bSFrank Mayhar err = ext4_handle_dirty_metadata(handle, inode, bh); 7867e028976SAvantika Mathur if (err) 787a86c6181SAlex Tomas goto cleanup; 788a86c6181SAlex Tomas brelse(bh); 789a86c6181SAlex Tomas bh = NULL; 790a86c6181SAlex Tomas 791a86c6181SAlex Tomas /* correct old leaf */ 792a86c6181SAlex Tomas if (m) { 7937e028976SAvantika Mathur err = ext4_ext_get_access(handle, inode, path + depth); 7947e028976SAvantika Mathur if (err) 795a86c6181SAlex Tomas goto cleanup; 796e8546d06SMarcin Slusarz le16_add_cpu(&path[depth].p_hdr->eh_entries, -m); 7977e028976SAvantika Mathur err = ext4_ext_dirty(handle, inode, path + depth); 7987e028976SAvantika Mathur if (err) 799a86c6181SAlex Tomas goto cleanup; 800a86c6181SAlex Tomas 801a86c6181SAlex Tomas } 802a86c6181SAlex Tomas 803a86c6181SAlex Tomas /* create intermediate indexes */ 804a86c6181SAlex Tomas k = depth - at - 1; 805a86c6181SAlex Tomas BUG_ON(k < 0); 806a86c6181SAlex Tomas if (k) 807a86c6181SAlex Tomas ext_debug("create %d intermediate indices\n", k); 808a86c6181SAlex Tomas /* insert new index into current index block */ 809a86c6181SAlex Tomas /* current depth stored in i var */ 810a86c6181SAlex Tomas i = depth - 1; 811a86c6181SAlex Tomas while (k--) { 812a86c6181SAlex Tomas oldblock = newblock; 813a86c6181SAlex Tomas newblock = ablocks[--a]; 814bba90743SEric Sandeen bh = sb_getblk(inode->i_sb, newblock); 815a86c6181SAlex Tomas if (!bh) { 816a86c6181SAlex Tomas err = -EIO; 817a86c6181SAlex Tomas goto cleanup; 818a86c6181SAlex Tomas } 819a86c6181SAlex Tomas lock_buffer(bh); 820a86c6181SAlex Tomas 8217e028976SAvantika Mathur err = ext4_journal_get_create_access(handle, bh); 8227e028976SAvantika Mathur if (err) 823a86c6181SAlex Tomas goto cleanup; 824a86c6181SAlex Tomas 825a86c6181SAlex Tomas neh = ext_block_hdr(bh); 826a86c6181SAlex Tomas neh->eh_entries = cpu_to_le16(1); 827a86c6181SAlex Tomas neh->eh_magic = EXT4_EXT_MAGIC; 828a86c6181SAlex Tomas neh->eh_max = cpu_to_le16(ext4_ext_space_block_idx(inode)); 829a86c6181SAlex Tomas neh->eh_depth = cpu_to_le16(depth - i); 830a86c6181SAlex Tomas fidx = EXT_FIRST_INDEX(neh); 831a86c6181SAlex Tomas fidx->ei_block = border; 832f65e6fbaSAlex Tomas ext4_idx_store_pblock(fidx, oldblock); 833a86c6181SAlex Tomas 834bba90743SEric Sandeen ext_debug("int.index at %d (block %llu): %u -> %llu\n", 835bba90743SEric Sandeen i, newblock, le32_to_cpu(border), oldblock); 836a86c6181SAlex Tomas /* copy indexes */ 837a86c6181SAlex Tomas m = 0; 838a86c6181SAlex Tomas path[i].p_idx++; 839a86c6181SAlex Tomas 840a86c6181SAlex Tomas ext_debug("cur 0x%p, last 0x%p\n", path[i].p_idx, 841a86c6181SAlex Tomas EXT_MAX_INDEX(path[i].p_hdr)); 842a86c6181SAlex Tomas BUG_ON(EXT_MAX_INDEX(path[i].p_hdr) != 843a86c6181SAlex Tomas EXT_LAST_INDEX(path[i].p_hdr)); 844a86c6181SAlex Tomas while (path[i].p_idx <= EXT_MAX_INDEX(path[i].p_hdr)) { 84526d535edSDmitry Monakhov ext_debug("%d: move %d:%llu in new index %llu\n", i, 846a86c6181SAlex Tomas le32_to_cpu(path[i].p_idx->ei_block), 847f65e6fbaSAlex Tomas idx_pblock(path[i].p_idx), 848a86c6181SAlex Tomas newblock); 849a86c6181SAlex Tomas /*memmove(++fidx, path[i].p_idx++, 850a86c6181SAlex Tomas sizeof(struct ext4_extent_idx)); 851a86c6181SAlex Tomas neh->eh_entries++; 852a86c6181SAlex Tomas BUG_ON(neh->eh_entries > neh->eh_max);*/ 853a86c6181SAlex Tomas path[i].p_idx++; 854a86c6181SAlex Tomas m++; 855a86c6181SAlex Tomas } 856a86c6181SAlex Tomas if (m) { 857a86c6181SAlex Tomas memmove(++fidx, path[i].p_idx - m, 858a86c6181SAlex Tomas sizeof(struct ext4_extent_idx) * m); 859e8546d06SMarcin Slusarz le16_add_cpu(&neh->eh_entries, m); 860a86c6181SAlex Tomas } 861a86c6181SAlex Tomas set_buffer_uptodate(bh); 862a86c6181SAlex Tomas unlock_buffer(bh); 863a86c6181SAlex Tomas 8640390131bSFrank Mayhar err = ext4_handle_dirty_metadata(handle, inode, bh); 8657e028976SAvantika Mathur if (err) 866a86c6181SAlex Tomas goto cleanup; 867a86c6181SAlex Tomas brelse(bh); 868a86c6181SAlex Tomas bh = NULL; 869a86c6181SAlex Tomas 870a86c6181SAlex Tomas /* correct old index */ 871a86c6181SAlex Tomas if (m) { 872a86c6181SAlex Tomas err = ext4_ext_get_access(handle, inode, path + i); 873a86c6181SAlex Tomas if (err) 874a86c6181SAlex Tomas goto cleanup; 875e8546d06SMarcin Slusarz le16_add_cpu(&path[i].p_hdr->eh_entries, -m); 876a86c6181SAlex Tomas err = ext4_ext_dirty(handle, inode, path + i); 877a86c6181SAlex Tomas if (err) 878a86c6181SAlex Tomas goto cleanup; 879a86c6181SAlex Tomas } 880a86c6181SAlex Tomas 881a86c6181SAlex Tomas i--; 882a86c6181SAlex Tomas } 883a86c6181SAlex Tomas 884a86c6181SAlex Tomas /* insert new index */ 885a86c6181SAlex Tomas err = ext4_ext_insert_index(handle, inode, path + at, 886a86c6181SAlex Tomas le32_to_cpu(border), newblock); 887a86c6181SAlex Tomas 888a86c6181SAlex Tomas cleanup: 889a86c6181SAlex Tomas if (bh) { 890a86c6181SAlex Tomas if (buffer_locked(bh)) 891a86c6181SAlex Tomas unlock_buffer(bh); 892a86c6181SAlex Tomas brelse(bh); 893a86c6181SAlex Tomas } 894a86c6181SAlex Tomas 895a86c6181SAlex Tomas if (err) { 896a86c6181SAlex Tomas /* free all allocated blocks in error case */ 897a86c6181SAlex Tomas for (i = 0; i < depth; i++) { 898a86c6181SAlex Tomas if (!ablocks[i]) 899a86c6181SAlex Tomas continue; 900c9de560dSAlex Tomas ext4_free_blocks(handle, inode, ablocks[i], 1, 1); 901a86c6181SAlex Tomas } 902a86c6181SAlex Tomas } 903a86c6181SAlex Tomas kfree(ablocks); 904a86c6181SAlex Tomas 905a86c6181SAlex Tomas return err; 906a86c6181SAlex Tomas } 907a86c6181SAlex Tomas 908a86c6181SAlex Tomas /* 909d0d856e8SRandy Dunlap * ext4_ext_grow_indepth: 910d0d856e8SRandy Dunlap * implements tree growing procedure: 911a86c6181SAlex Tomas * - allocates new block 912a86c6181SAlex Tomas * - moves top-level data (index block or leaf) into the new block 913d0d856e8SRandy Dunlap * - initializes new top-level, creating index that points to the 914a86c6181SAlex Tomas * just created block 915a86c6181SAlex Tomas */ 916a86c6181SAlex Tomas static int ext4_ext_grow_indepth(handle_t *handle, struct inode *inode, 917a86c6181SAlex Tomas struct ext4_ext_path *path, 918a86c6181SAlex Tomas struct ext4_extent *newext) 919a86c6181SAlex Tomas { 920a86c6181SAlex Tomas struct ext4_ext_path *curp = path; 921a86c6181SAlex Tomas struct ext4_extent_header *neh; 922a86c6181SAlex Tomas struct ext4_extent_idx *fidx; 923a86c6181SAlex Tomas struct buffer_head *bh; 924f65e6fbaSAlex Tomas ext4_fsblk_t newblock; 925a86c6181SAlex Tomas int err = 0; 926a86c6181SAlex Tomas 927654b4908SAneesh Kumar K.V newblock = ext4_ext_new_meta_block(handle, inode, path, newext, &err); 928a86c6181SAlex Tomas if (newblock == 0) 929a86c6181SAlex Tomas return err; 930a86c6181SAlex Tomas 931a86c6181SAlex Tomas bh = sb_getblk(inode->i_sb, newblock); 932a86c6181SAlex Tomas if (!bh) { 933a86c6181SAlex Tomas err = -EIO; 934a86c6181SAlex Tomas ext4_std_error(inode->i_sb, err); 935a86c6181SAlex Tomas return err; 936a86c6181SAlex Tomas } 937a86c6181SAlex Tomas lock_buffer(bh); 938a86c6181SAlex Tomas 9397e028976SAvantika Mathur err = ext4_journal_get_create_access(handle, bh); 9407e028976SAvantika Mathur if (err) { 941a86c6181SAlex Tomas unlock_buffer(bh); 942a86c6181SAlex Tomas goto out; 943a86c6181SAlex Tomas } 944a86c6181SAlex Tomas 945a86c6181SAlex Tomas /* move top-level index/leaf into new block */ 946a86c6181SAlex Tomas memmove(bh->b_data, curp->p_hdr, sizeof(EXT4_I(inode)->i_data)); 947a86c6181SAlex Tomas 948a86c6181SAlex Tomas /* set size of new block */ 949a86c6181SAlex Tomas neh = ext_block_hdr(bh); 950a86c6181SAlex Tomas /* old root could have indexes or leaves 951a86c6181SAlex Tomas * so calculate e_max right way */ 952a86c6181SAlex Tomas if (ext_depth(inode)) 953a86c6181SAlex Tomas neh->eh_max = cpu_to_le16(ext4_ext_space_block_idx(inode)); 954a86c6181SAlex Tomas else 955a86c6181SAlex Tomas neh->eh_max = cpu_to_le16(ext4_ext_space_block(inode)); 956a86c6181SAlex Tomas neh->eh_magic = EXT4_EXT_MAGIC; 957a86c6181SAlex Tomas set_buffer_uptodate(bh); 958a86c6181SAlex Tomas unlock_buffer(bh); 959a86c6181SAlex Tomas 9600390131bSFrank Mayhar err = ext4_handle_dirty_metadata(handle, inode, bh); 9617e028976SAvantika Mathur if (err) 962a86c6181SAlex Tomas goto out; 963a86c6181SAlex Tomas 964a86c6181SAlex Tomas /* create index in new top-level index: num,max,pointer */ 9657e028976SAvantika Mathur err = ext4_ext_get_access(handle, inode, curp); 9667e028976SAvantika Mathur if (err) 967a86c6181SAlex Tomas goto out; 968a86c6181SAlex Tomas 969a86c6181SAlex Tomas curp->p_hdr->eh_magic = EXT4_EXT_MAGIC; 970a86c6181SAlex Tomas curp->p_hdr->eh_max = cpu_to_le16(ext4_ext_space_root_idx(inode)); 971a86c6181SAlex Tomas curp->p_hdr->eh_entries = cpu_to_le16(1); 972a86c6181SAlex Tomas curp->p_idx = EXT_FIRST_INDEX(curp->p_hdr); 973e9f410b1SDmitry Monakhov 974e9f410b1SDmitry Monakhov if (path[0].p_hdr->eh_depth) 975e9f410b1SDmitry Monakhov curp->p_idx->ei_block = 976e9f410b1SDmitry Monakhov EXT_FIRST_INDEX(path[0].p_hdr)->ei_block; 977e9f410b1SDmitry Monakhov else 978e9f410b1SDmitry Monakhov curp->p_idx->ei_block = 979e9f410b1SDmitry Monakhov EXT_FIRST_EXTENT(path[0].p_hdr)->ee_block; 980f65e6fbaSAlex Tomas ext4_idx_store_pblock(curp->p_idx, newblock); 981a86c6181SAlex Tomas 982a86c6181SAlex Tomas neh = ext_inode_hdr(inode); 983a86c6181SAlex Tomas fidx = EXT_FIRST_INDEX(neh); 9842ae02107SMingming Cao ext_debug("new root: num %d(%d), lblock %d, ptr %llu\n", 985a86c6181SAlex Tomas le16_to_cpu(neh->eh_entries), le16_to_cpu(neh->eh_max), 986f65e6fbaSAlex Tomas le32_to_cpu(fidx->ei_block), idx_pblock(fidx)); 987a86c6181SAlex Tomas 988a86c6181SAlex Tomas neh->eh_depth = cpu_to_le16(path->p_depth + 1); 989a86c6181SAlex Tomas err = ext4_ext_dirty(handle, inode, curp); 990a86c6181SAlex Tomas out: 991a86c6181SAlex Tomas brelse(bh); 992a86c6181SAlex Tomas 993a86c6181SAlex Tomas return err; 994a86c6181SAlex Tomas } 995a86c6181SAlex Tomas 996a86c6181SAlex Tomas /* 997d0d856e8SRandy Dunlap * ext4_ext_create_new_leaf: 998d0d856e8SRandy Dunlap * finds empty index and adds new leaf. 999d0d856e8SRandy Dunlap * if no free index is found, then it requests in-depth growing. 1000a86c6181SAlex Tomas */ 1001a86c6181SAlex Tomas static int ext4_ext_create_new_leaf(handle_t *handle, struct inode *inode, 1002a86c6181SAlex Tomas struct ext4_ext_path *path, 1003a86c6181SAlex Tomas struct ext4_extent *newext) 1004a86c6181SAlex Tomas { 1005a86c6181SAlex Tomas struct ext4_ext_path *curp; 1006a86c6181SAlex Tomas int depth, i, err = 0; 1007a86c6181SAlex Tomas 1008a86c6181SAlex Tomas repeat: 1009a86c6181SAlex Tomas i = depth = ext_depth(inode); 1010a86c6181SAlex Tomas 1011a86c6181SAlex Tomas /* walk up to the tree and look for free index entry */ 1012a86c6181SAlex Tomas curp = path + depth; 1013a86c6181SAlex Tomas while (i > 0 && !EXT_HAS_FREE_INDEX(curp)) { 1014a86c6181SAlex Tomas i--; 1015a86c6181SAlex Tomas curp--; 1016a86c6181SAlex Tomas } 1017a86c6181SAlex Tomas 1018d0d856e8SRandy Dunlap /* we use already allocated block for index block, 1019d0d856e8SRandy Dunlap * so subsequent data blocks should be contiguous */ 1020a86c6181SAlex Tomas if (EXT_HAS_FREE_INDEX(curp)) { 1021a86c6181SAlex Tomas /* if we found index with free entry, then use that 1022a86c6181SAlex Tomas * entry: create all needed subtree and add new leaf */ 1023a86c6181SAlex Tomas err = ext4_ext_split(handle, inode, path, newext, i); 1024787e0981SShen Feng if (err) 1025787e0981SShen Feng goto out; 1026a86c6181SAlex Tomas 1027a86c6181SAlex Tomas /* refill path */ 1028a86c6181SAlex Tomas ext4_ext_drop_refs(path); 1029a86c6181SAlex Tomas path = ext4_ext_find_extent(inode, 1030725d26d3SAneesh Kumar K.V (ext4_lblk_t)le32_to_cpu(newext->ee_block), 1031a86c6181SAlex Tomas path); 1032a86c6181SAlex Tomas if (IS_ERR(path)) 1033a86c6181SAlex Tomas err = PTR_ERR(path); 1034a86c6181SAlex Tomas } else { 1035a86c6181SAlex Tomas /* tree is full, time to grow in depth */ 1036a86c6181SAlex Tomas err = ext4_ext_grow_indepth(handle, inode, path, newext); 1037a86c6181SAlex Tomas if (err) 1038a86c6181SAlex Tomas goto out; 1039a86c6181SAlex Tomas 1040a86c6181SAlex Tomas /* refill path */ 1041a86c6181SAlex Tomas ext4_ext_drop_refs(path); 1042a86c6181SAlex Tomas path = ext4_ext_find_extent(inode, 1043725d26d3SAneesh Kumar K.V (ext4_lblk_t)le32_to_cpu(newext->ee_block), 1044a86c6181SAlex Tomas path); 1045a86c6181SAlex Tomas if (IS_ERR(path)) { 1046a86c6181SAlex Tomas err = PTR_ERR(path); 1047a86c6181SAlex Tomas goto out; 1048a86c6181SAlex Tomas } 1049a86c6181SAlex Tomas 1050a86c6181SAlex Tomas /* 1051d0d856e8SRandy Dunlap * only first (depth 0 -> 1) produces free space; 1052d0d856e8SRandy Dunlap * in all other cases we have to split the grown tree 1053a86c6181SAlex Tomas */ 1054a86c6181SAlex Tomas depth = ext_depth(inode); 1055a86c6181SAlex Tomas if (path[depth].p_hdr->eh_entries == path[depth].p_hdr->eh_max) { 1056d0d856e8SRandy Dunlap /* now we need to split */ 1057a86c6181SAlex Tomas goto repeat; 1058a86c6181SAlex Tomas } 1059a86c6181SAlex Tomas } 1060a86c6181SAlex Tomas 1061a86c6181SAlex Tomas out: 1062a86c6181SAlex Tomas return err; 1063a86c6181SAlex Tomas } 1064a86c6181SAlex Tomas 1065a86c6181SAlex Tomas /* 10661988b51eSAlex Tomas * search the closest allocated block to the left for *logical 10671988b51eSAlex Tomas * and returns it at @logical + it's physical address at @phys 10681988b51eSAlex Tomas * if *logical is the smallest allocated block, the function 10691988b51eSAlex Tomas * returns 0 at @phys 10701988b51eSAlex Tomas * return value contains 0 (success) or error code 10711988b51eSAlex Tomas */ 10721988b51eSAlex Tomas int 10731988b51eSAlex Tomas ext4_ext_search_left(struct inode *inode, struct ext4_ext_path *path, 10741988b51eSAlex Tomas ext4_lblk_t *logical, ext4_fsblk_t *phys) 10751988b51eSAlex Tomas { 10761988b51eSAlex Tomas struct ext4_extent_idx *ix; 10771988b51eSAlex Tomas struct ext4_extent *ex; 1078b939e376SAneesh Kumar K.V int depth, ee_len; 10791988b51eSAlex Tomas 10801988b51eSAlex Tomas BUG_ON(path == NULL); 10811988b51eSAlex Tomas depth = path->p_depth; 10821988b51eSAlex Tomas *phys = 0; 10831988b51eSAlex Tomas 10841988b51eSAlex Tomas if (depth == 0 && path->p_ext == NULL) 10851988b51eSAlex Tomas return 0; 10861988b51eSAlex Tomas 10871988b51eSAlex Tomas /* usually extent in the path covers blocks smaller 10881988b51eSAlex Tomas * then *logical, but it can be that extent is the 10891988b51eSAlex Tomas * first one in the file */ 10901988b51eSAlex Tomas 10911988b51eSAlex Tomas ex = path[depth].p_ext; 1092b939e376SAneesh Kumar K.V ee_len = ext4_ext_get_actual_len(ex); 10931988b51eSAlex Tomas if (*logical < le32_to_cpu(ex->ee_block)) { 10941988b51eSAlex Tomas BUG_ON(EXT_FIRST_EXTENT(path[depth].p_hdr) != ex); 10951988b51eSAlex Tomas while (--depth >= 0) { 10961988b51eSAlex Tomas ix = path[depth].p_idx; 10971988b51eSAlex Tomas BUG_ON(ix != EXT_FIRST_INDEX(path[depth].p_hdr)); 10981988b51eSAlex Tomas } 10991988b51eSAlex Tomas return 0; 11001988b51eSAlex Tomas } 11011988b51eSAlex Tomas 1102b939e376SAneesh Kumar K.V BUG_ON(*logical < (le32_to_cpu(ex->ee_block) + ee_len)); 11031988b51eSAlex Tomas 1104b939e376SAneesh Kumar K.V *logical = le32_to_cpu(ex->ee_block) + ee_len - 1; 1105b939e376SAneesh Kumar K.V *phys = ext_pblock(ex) + ee_len - 1; 11061988b51eSAlex Tomas return 0; 11071988b51eSAlex Tomas } 11081988b51eSAlex Tomas 11091988b51eSAlex Tomas /* 11101988b51eSAlex Tomas * search the closest allocated block to the right for *logical 11111988b51eSAlex Tomas * and returns it at @logical + it's physical address at @phys 11121988b51eSAlex Tomas * if *logical is the smallest allocated block, the function 11131988b51eSAlex Tomas * returns 0 at @phys 11141988b51eSAlex Tomas * return value contains 0 (success) or error code 11151988b51eSAlex Tomas */ 11161988b51eSAlex Tomas int 11171988b51eSAlex Tomas ext4_ext_search_right(struct inode *inode, struct ext4_ext_path *path, 11181988b51eSAlex Tomas ext4_lblk_t *logical, ext4_fsblk_t *phys) 11191988b51eSAlex Tomas { 11201988b51eSAlex Tomas struct buffer_head *bh = NULL; 11211988b51eSAlex Tomas struct ext4_extent_header *eh; 11221988b51eSAlex Tomas struct ext4_extent_idx *ix; 11231988b51eSAlex Tomas struct ext4_extent *ex; 11241988b51eSAlex Tomas ext4_fsblk_t block; 1125b939e376SAneesh Kumar K.V int depth, ee_len; 11261988b51eSAlex Tomas 11271988b51eSAlex Tomas BUG_ON(path == NULL); 11281988b51eSAlex Tomas depth = path->p_depth; 11291988b51eSAlex Tomas *phys = 0; 11301988b51eSAlex Tomas 11311988b51eSAlex Tomas if (depth == 0 && path->p_ext == NULL) 11321988b51eSAlex Tomas return 0; 11331988b51eSAlex Tomas 11341988b51eSAlex Tomas /* usually extent in the path covers blocks smaller 11351988b51eSAlex Tomas * then *logical, but it can be that extent is the 11361988b51eSAlex Tomas * first one in the file */ 11371988b51eSAlex Tomas 11381988b51eSAlex Tomas ex = path[depth].p_ext; 1139b939e376SAneesh Kumar K.V ee_len = ext4_ext_get_actual_len(ex); 11401988b51eSAlex Tomas if (*logical < le32_to_cpu(ex->ee_block)) { 11411988b51eSAlex Tomas BUG_ON(EXT_FIRST_EXTENT(path[depth].p_hdr) != ex); 11421988b51eSAlex Tomas while (--depth >= 0) { 11431988b51eSAlex Tomas ix = path[depth].p_idx; 11441988b51eSAlex Tomas BUG_ON(ix != EXT_FIRST_INDEX(path[depth].p_hdr)); 11451988b51eSAlex Tomas } 11461988b51eSAlex Tomas *logical = le32_to_cpu(ex->ee_block); 11471988b51eSAlex Tomas *phys = ext_pblock(ex); 11481988b51eSAlex Tomas return 0; 11491988b51eSAlex Tomas } 11501988b51eSAlex Tomas 1151b939e376SAneesh Kumar K.V BUG_ON(*logical < (le32_to_cpu(ex->ee_block) + ee_len)); 11521988b51eSAlex Tomas 11531988b51eSAlex Tomas if (ex != EXT_LAST_EXTENT(path[depth].p_hdr)) { 11541988b51eSAlex Tomas /* next allocated block in this leaf */ 11551988b51eSAlex Tomas ex++; 11561988b51eSAlex Tomas *logical = le32_to_cpu(ex->ee_block); 11571988b51eSAlex Tomas *phys = ext_pblock(ex); 11581988b51eSAlex Tomas return 0; 11591988b51eSAlex Tomas } 11601988b51eSAlex Tomas 11611988b51eSAlex Tomas /* go up and search for index to the right */ 11621988b51eSAlex Tomas while (--depth >= 0) { 11631988b51eSAlex Tomas ix = path[depth].p_idx; 11641988b51eSAlex Tomas if (ix != EXT_LAST_INDEX(path[depth].p_hdr)) 116525f1ee3aSWu Fengguang goto got_index; 11661988b51eSAlex Tomas } 11671988b51eSAlex Tomas 116825f1ee3aSWu Fengguang /* we've gone up to the root and found no index to the right */ 11691988b51eSAlex Tomas return 0; 11701988b51eSAlex Tomas 117125f1ee3aSWu Fengguang got_index: 11721988b51eSAlex Tomas /* we've found index to the right, let's 11731988b51eSAlex Tomas * follow it and find the closest allocated 11741988b51eSAlex Tomas * block to the right */ 11751988b51eSAlex Tomas ix++; 11761988b51eSAlex Tomas block = idx_pblock(ix); 11771988b51eSAlex Tomas while (++depth < path->p_depth) { 11781988b51eSAlex Tomas bh = sb_bread(inode->i_sb, block); 11791988b51eSAlex Tomas if (bh == NULL) 11801988b51eSAlex Tomas return -EIO; 11811988b51eSAlex Tomas eh = ext_block_hdr(bh); 11821988b51eSAlex Tomas if (ext4_ext_check_header(inode, eh, depth)) { 11831988b51eSAlex Tomas put_bh(bh); 11841988b51eSAlex Tomas return -EIO; 11851988b51eSAlex Tomas } 11861988b51eSAlex Tomas ix = EXT_FIRST_INDEX(eh); 11871988b51eSAlex Tomas block = idx_pblock(ix); 11881988b51eSAlex Tomas put_bh(bh); 11891988b51eSAlex Tomas } 11901988b51eSAlex Tomas 11911988b51eSAlex Tomas bh = sb_bread(inode->i_sb, block); 11921988b51eSAlex Tomas if (bh == NULL) 11931988b51eSAlex Tomas return -EIO; 11941988b51eSAlex Tomas eh = ext_block_hdr(bh); 11951988b51eSAlex Tomas if (ext4_ext_check_header(inode, eh, path->p_depth - depth)) { 11961988b51eSAlex Tomas put_bh(bh); 11971988b51eSAlex Tomas return -EIO; 11981988b51eSAlex Tomas } 11991988b51eSAlex Tomas ex = EXT_FIRST_EXTENT(eh); 12001988b51eSAlex Tomas *logical = le32_to_cpu(ex->ee_block); 12011988b51eSAlex Tomas *phys = ext_pblock(ex); 12021988b51eSAlex Tomas put_bh(bh); 12031988b51eSAlex Tomas return 0; 12041988b51eSAlex Tomas } 12051988b51eSAlex Tomas 12061988b51eSAlex Tomas /* 1207d0d856e8SRandy Dunlap * ext4_ext_next_allocated_block: 1208d0d856e8SRandy Dunlap * returns allocated block in subsequent extent or EXT_MAX_BLOCK. 1209d0d856e8SRandy Dunlap * NOTE: it considers block number from index entry as 1210d0d856e8SRandy Dunlap * allocated block. Thus, index entries have to be consistent 1211d0d856e8SRandy Dunlap * with leaves. 1212a86c6181SAlex Tomas */ 1213725d26d3SAneesh Kumar K.V static ext4_lblk_t 1214a86c6181SAlex Tomas ext4_ext_next_allocated_block(struct ext4_ext_path *path) 1215a86c6181SAlex Tomas { 1216a86c6181SAlex Tomas int depth; 1217a86c6181SAlex Tomas 1218a86c6181SAlex Tomas BUG_ON(path == NULL); 1219a86c6181SAlex Tomas depth = path->p_depth; 1220a86c6181SAlex Tomas 1221a86c6181SAlex Tomas if (depth == 0 && path->p_ext == NULL) 1222a86c6181SAlex Tomas return EXT_MAX_BLOCK; 1223a86c6181SAlex Tomas 1224a86c6181SAlex Tomas while (depth >= 0) { 1225a86c6181SAlex Tomas if (depth == path->p_depth) { 1226a86c6181SAlex Tomas /* leaf */ 1227a86c6181SAlex Tomas if (path[depth].p_ext != 1228a86c6181SAlex Tomas EXT_LAST_EXTENT(path[depth].p_hdr)) 1229a86c6181SAlex Tomas return le32_to_cpu(path[depth].p_ext[1].ee_block); 1230a86c6181SAlex Tomas } else { 1231a86c6181SAlex Tomas /* index */ 1232a86c6181SAlex Tomas if (path[depth].p_idx != 1233a86c6181SAlex Tomas EXT_LAST_INDEX(path[depth].p_hdr)) 1234a86c6181SAlex Tomas return le32_to_cpu(path[depth].p_idx[1].ei_block); 1235a86c6181SAlex Tomas } 1236a86c6181SAlex Tomas depth--; 1237a86c6181SAlex Tomas } 1238a86c6181SAlex Tomas 1239a86c6181SAlex Tomas return EXT_MAX_BLOCK; 1240a86c6181SAlex Tomas } 1241a86c6181SAlex Tomas 1242a86c6181SAlex Tomas /* 1243d0d856e8SRandy Dunlap * ext4_ext_next_leaf_block: 1244a86c6181SAlex Tomas * returns first allocated block from next leaf or EXT_MAX_BLOCK 1245a86c6181SAlex Tomas */ 1246725d26d3SAneesh Kumar K.V static ext4_lblk_t ext4_ext_next_leaf_block(struct inode *inode, 1247a86c6181SAlex Tomas struct ext4_ext_path *path) 1248a86c6181SAlex Tomas { 1249a86c6181SAlex Tomas int depth; 1250a86c6181SAlex Tomas 1251a86c6181SAlex Tomas BUG_ON(path == NULL); 1252a86c6181SAlex Tomas depth = path->p_depth; 1253a86c6181SAlex Tomas 1254a86c6181SAlex Tomas /* zero-tree has no leaf blocks at all */ 1255a86c6181SAlex Tomas if (depth == 0) 1256a86c6181SAlex Tomas return EXT_MAX_BLOCK; 1257a86c6181SAlex Tomas 1258a86c6181SAlex Tomas /* go to index block */ 1259a86c6181SAlex Tomas depth--; 1260a86c6181SAlex Tomas 1261a86c6181SAlex Tomas while (depth >= 0) { 1262a86c6181SAlex Tomas if (path[depth].p_idx != 1263a86c6181SAlex Tomas EXT_LAST_INDEX(path[depth].p_hdr)) 1264725d26d3SAneesh Kumar K.V return (ext4_lblk_t) 1265725d26d3SAneesh Kumar K.V le32_to_cpu(path[depth].p_idx[1].ei_block); 1266a86c6181SAlex Tomas depth--; 1267a86c6181SAlex Tomas } 1268a86c6181SAlex Tomas 1269a86c6181SAlex Tomas return EXT_MAX_BLOCK; 1270a86c6181SAlex Tomas } 1271a86c6181SAlex Tomas 1272a86c6181SAlex Tomas /* 1273d0d856e8SRandy Dunlap * ext4_ext_correct_indexes: 1274d0d856e8SRandy Dunlap * if leaf gets modified and modified extent is first in the leaf, 1275d0d856e8SRandy Dunlap * then we have to correct all indexes above. 1276a86c6181SAlex Tomas * TODO: do we need to correct tree in all cases? 1277a86c6181SAlex Tomas */ 12781d03ec98SAneesh Kumar K.V static int ext4_ext_correct_indexes(handle_t *handle, struct inode *inode, 1279a86c6181SAlex Tomas struct ext4_ext_path *path) 1280a86c6181SAlex Tomas { 1281a86c6181SAlex Tomas struct ext4_extent_header *eh; 1282a86c6181SAlex Tomas int depth = ext_depth(inode); 1283a86c6181SAlex Tomas struct ext4_extent *ex; 1284a86c6181SAlex Tomas __le32 border; 1285a86c6181SAlex Tomas int k, err = 0; 1286a86c6181SAlex Tomas 1287a86c6181SAlex Tomas eh = path[depth].p_hdr; 1288a86c6181SAlex Tomas ex = path[depth].p_ext; 1289a86c6181SAlex Tomas BUG_ON(ex == NULL); 1290a86c6181SAlex Tomas BUG_ON(eh == NULL); 1291a86c6181SAlex Tomas 1292a86c6181SAlex Tomas if (depth == 0) { 1293a86c6181SAlex Tomas /* there is no tree at all */ 1294a86c6181SAlex Tomas return 0; 1295a86c6181SAlex Tomas } 1296a86c6181SAlex Tomas 1297a86c6181SAlex Tomas if (ex != EXT_FIRST_EXTENT(eh)) { 1298a86c6181SAlex Tomas /* we correct tree if first leaf got modified only */ 1299a86c6181SAlex Tomas return 0; 1300a86c6181SAlex Tomas } 1301a86c6181SAlex Tomas 1302a86c6181SAlex Tomas /* 1303d0d856e8SRandy Dunlap * TODO: we need correction if border is smaller than current one 1304a86c6181SAlex Tomas */ 1305a86c6181SAlex Tomas k = depth - 1; 1306a86c6181SAlex Tomas border = path[depth].p_ext->ee_block; 13077e028976SAvantika Mathur err = ext4_ext_get_access(handle, inode, path + k); 13087e028976SAvantika Mathur if (err) 1309a86c6181SAlex Tomas return err; 1310a86c6181SAlex Tomas path[k].p_idx->ei_block = border; 13117e028976SAvantika Mathur err = ext4_ext_dirty(handle, inode, path + k); 13127e028976SAvantika Mathur if (err) 1313a86c6181SAlex Tomas return err; 1314a86c6181SAlex Tomas 1315a86c6181SAlex Tomas while (k--) { 1316a86c6181SAlex Tomas /* change all left-side indexes */ 1317a86c6181SAlex Tomas if (path[k+1].p_idx != EXT_FIRST_INDEX(path[k+1].p_hdr)) 1318a86c6181SAlex Tomas break; 13197e028976SAvantika Mathur err = ext4_ext_get_access(handle, inode, path + k); 13207e028976SAvantika Mathur if (err) 1321a86c6181SAlex Tomas break; 1322a86c6181SAlex Tomas path[k].p_idx->ei_block = border; 13237e028976SAvantika Mathur err = ext4_ext_dirty(handle, inode, path + k); 13247e028976SAvantika Mathur if (err) 1325a86c6181SAlex Tomas break; 1326a86c6181SAlex Tomas } 1327a86c6181SAlex Tomas 1328a86c6181SAlex Tomas return err; 1329a86c6181SAlex Tomas } 1330a86c6181SAlex Tomas 133109b88252SAvantika Mathur static int 1332a86c6181SAlex Tomas ext4_can_extents_be_merged(struct inode *inode, struct ext4_extent *ex1, 1333a86c6181SAlex Tomas struct ext4_extent *ex2) 1334a86c6181SAlex Tomas { 1335749269faSAmit Arora unsigned short ext1_ee_len, ext2_ee_len, max_len; 1336a2df2a63SAmit Arora 1337a2df2a63SAmit Arora /* 1338a2df2a63SAmit Arora * Make sure that either both extents are uninitialized, or 1339a2df2a63SAmit Arora * both are _not_. 1340a2df2a63SAmit Arora */ 1341a2df2a63SAmit Arora if (ext4_ext_is_uninitialized(ex1) ^ ext4_ext_is_uninitialized(ex2)) 1342a2df2a63SAmit Arora return 0; 1343a2df2a63SAmit Arora 1344749269faSAmit Arora if (ext4_ext_is_uninitialized(ex1)) 1345749269faSAmit Arora max_len = EXT_UNINIT_MAX_LEN; 1346749269faSAmit Arora else 1347749269faSAmit Arora max_len = EXT_INIT_MAX_LEN; 1348749269faSAmit Arora 1349a2df2a63SAmit Arora ext1_ee_len = ext4_ext_get_actual_len(ex1); 1350a2df2a63SAmit Arora ext2_ee_len = ext4_ext_get_actual_len(ex2); 1351a2df2a63SAmit Arora 1352a2df2a63SAmit Arora if (le32_to_cpu(ex1->ee_block) + ext1_ee_len != 135363f57933SAndrew Morton le32_to_cpu(ex2->ee_block)) 1354a86c6181SAlex Tomas return 0; 1355a86c6181SAlex Tomas 1356471d4011SSuparna Bhattacharya /* 1357471d4011SSuparna Bhattacharya * To allow future support for preallocated extents to be added 1358471d4011SSuparna Bhattacharya * as an RO_COMPAT feature, refuse to merge to extents if 1359d0d856e8SRandy Dunlap * this can result in the top bit of ee_len being set. 1360471d4011SSuparna Bhattacharya */ 1361749269faSAmit Arora if (ext1_ee_len + ext2_ee_len > max_len) 1362471d4011SSuparna Bhattacharya return 0; 1363bbf2f9fbSRobert P. J. Day #ifdef AGGRESSIVE_TEST 1364b939e376SAneesh Kumar K.V if (ext1_ee_len >= 4) 1365a86c6181SAlex Tomas return 0; 1366a86c6181SAlex Tomas #endif 1367a86c6181SAlex Tomas 1368a2df2a63SAmit Arora if (ext_pblock(ex1) + ext1_ee_len == ext_pblock(ex2)) 1369a86c6181SAlex Tomas return 1; 1370a86c6181SAlex Tomas return 0; 1371a86c6181SAlex Tomas } 1372a86c6181SAlex Tomas 1373a86c6181SAlex Tomas /* 137456055d3aSAmit Arora * This function tries to merge the "ex" extent to the next extent in the tree. 137556055d3aSAmit Arora * It always tries to merge towards right. If you want to merge towards 137656055d3aSAmit Arora * left, pass "ex - 1" as argument instead of "ex". 137756055d3aSAmit Arora * Returns 0 if the extents (ex and ex+1) were _not_ merged and returns 137856055d3aSAmit Arora * 1 if they got merged. 137956055d3aSAmit Arora */ 138056055d3aSAmit Arora int ext4_ext_try_to_merge(struct inode *inode, 138156055d3aSAmit Arora struct ext4_ext_path *path, 138256055d3aSAmit Arora struct ext4_extent *ex) 138356055d3aSAmit Arora { 138456055d3aSAmit Arora struct ext4_extent_header *eh; 138556055d3aSAmit Arora unsigned int depth, len; 138656055d3aSAmit Arora int merge_done = 0; 138756055d3aSAmit Arora int uninitialized = 0; 138856055d3aSAmit Arora 138956055d3aSAmit Arora depth = ext_depth(inode); 139056055d3aSAmit Arora BUG_ON(path[depth].p_hdr == NULL); 139156055d3aSAmit Arora eh = path[depth].p_hdr; 139256055d3aSAmit Arora 139356055d3aSAmit Arora while (ex < EXT_LAST_EXTENT(eh)) { 139456055d3aSAmit Arora if (!ext4_can_extents_be_merged(inode, ex, ex + 1)) 139556055d3aSAmit Arora break; 139656055d3aSAmit Arora /* merge with next extent! */ 139756055d3aSAmit Arora if (ext4_ext_is_uninitialized(ex)) 139856055d3aSAmit Arora uninitialized = 1; 139956055d3aSAmit Arora ex->ee_len = cpu_to_le16(ext4_ext_get_actual_len(ex) 140056055d3aSAmit Arora + ext4_ext_get_actual_len(ex + 1)); 140156055d3aSAmit Arora if (uninitialized) 140256055d3aSAmit Arora ext4_ext_mark_uninitialized(ex); 140356055d3aSAmit Arora 140456055d3aSAmit Arora if (ex + 1 < EXT_LAST_EXTENT(eh)) { 140556055d3aSAmit Arora len = (EXT_LAST_EXTENT(eh) - ex - 1) 140656055d3aSAmit Arora * sizeof(struct ext4_extent); 140756055d3aSAmit Arora memmove(ex + 1, ex + 2, len); 140856055d3aSAmit Arora } 1409e8546d06SMarcin Slusarz le16_add_cpu(&eh->eh_entries, -1); 141056055d3aSAmit Arora merge_done = 1; 141156055d3aSAmit Arora WARN_ON(eh->eh_entries == 0); 141256055d3aSAmit Arora if (!eh->eh_entries) 141356055d3aSAmit Arora ext4_error(inode->i_sb, "ext4_ext_try_to_merge", 141456055d3aSAmit Arora "inode#%lu, eh->eh_entries = 0!", inode->i_ino); 141556055d3aSAmit Arora } 141656055d3aSAmit Arora 141756055d3aSAmit Arora return merge_done; 141856055d3aSAmit Arora } 141956055d3aSAmit Arora 142056055d3aSAmit Arora /* 142125d14f98SAmit Arora * check if a portion of the "newext" extent overlaps with an 142225d14f98SAmit Arora * existing extent. 142325d14f98SAmit Arora * 142425d14f98SAmit Arora * If there is an overlap discovered, it updates the length of the newext 142525d14f98SAmit Arora * such that there will be no overlap, and then returns 1. 142625d14f98SAmit Arora * If there is no overlap found, it returns 0. 142725d14f98SAmit Arora */ 142825d14f98SAmit Arora unsigned int ext4_ext_check_overlap(struct inode *inode, 142925d14f98SAmit Arora struct ext4_extent *newext, 143025d14f98SAmit Arora struct ext4_ext_path *path) 143125d14f98SAmit Arora { 1432725d26d3SAneesh Kumar K.V ext4_lblk_t b1, b2; 143325d14f98SAmit Arora unsigned int depth, len1; 143425d14f98SAmit Arora unsigned int ret = 0; 143525d14f98SAmit Arora 143625d14f98SAmit Arora b1 = le32_to_cpu(newext->ee_block); 1437a2df2a63SAmit Arora len1 = ext4_ext_get_actual_len(newext); 143825d14f98SAmit Arora depth = ext_depth(inode); 143925d14f98SAmit Arora if (!path[depth].p_ext) 144025d14f98SAmit Arora goto out; 144125d14f98SAmit Arora b2 = le32_to_cpu(path[depth].p_ext->ee_block); 144225d14f98SAmit Arora 144325d14f98SAmit Arora /* 144425d14f98SAmit Arora * get the next allocated block if the extent in the path 144525d14f98SAmit Arora * is before the requested block(s) 144625d14f98SAmit Arora */ 144725d14f98SAmit Arora if (b2 < b1) { 144825d14f98SAmit Arora b2 = ext4_ext_next_allocated_block(path); 144925d14f98SAmit Arora if (b2 == EXT_MAX_BLOCK) 145025d14f98SAmit Arora goto out; 145125d14f98SAmit Arora } 145225d14f98SAmit Arora 1453725d26d3SAneesh Kumar K.V /* check for wrap through zero on extent logical start block*/ 145425d14f98SAmit Arora if (b1 + len1 < b1) { 145525d14f98SAmit Arora len1 = EXT_MAX_BLOCK - b1; 145625d14f98SAmit Arora newext->ee_len = cpu_to_le16(len1); 145725d14f98SAmit Arora ret = 1; 145825d14f98SAmit Arora } 145925d14f98SAmit Arora 146025d14f98SAmit Arora /* check for overlap */ 146125d14f98SAmit Arora if (b1 + len1 > b2) { 146225d14f98SAmit Arora newext->ee_len = cpu_to_le16(b2 - b1); 146325d14f98SAmit Arora ret = 1; 146425d14f98SAmit Arora } 146525d14f98SAmit Arora out: 146625d14f98SAmit Arora return ret; 146725d14f98SAmit Arora } 146825d14f98SAmit Arora 146925d14f98SAmit Arora /* 1470d0d856e8SRandy Dunlap * ext4_ext_insert_extent: 1471d0d856e8SRandy Dunlap * tries to merge requsted extent into the existing extent or 1472d0d856e8SRandy Dunlap * inserts requested extent as new one into the tree, 1473d0d856e8SRandy Dunlap * creating new leaf in the no-space case. 1474a86c6181SAlex Tomas */ 1475a86c6181SAlex Tomas int ext4_ext_insert_extent(handle_t *handle, struct inode *inode, 1476a86c6181SAlex Tomas struct ext4_ext_path *path, 1477a86c6181SAlex Tomas struct ext4_extent *newext) 1478a86c6181SAlex Tomas { 1479a86c6181SAlex Tomas struct ext4_extent_header *eh; 1480a86c6181SAlex Tomas struct ext4_extent *ex, *fex; 1481a86c6181SAlex Tomas struct ext4_extent *nearex; /* nearest extent */ 1482a86c6181SAlex Tomas struct ext4_ext_path *npath = NULL; 1483725d26d3SAneesh Kumar K.V int depth, len, err; 1484725d26d3SAneesh Kumar K.V ext4_lblk_t next; 1485a2df2a63SAmit Arora unsigned uninitialized = 0; 1486a86c6181SAlex Tomas 1487a2df2a63SAmit Arora BUG_ON(ext4_ext_get_actual_len(newext) == 0); 1488a86c6181SAlex Tomas depth = ext_depth(inode); 1489a86c6181SAlex Tomas ex = path[depth].p_ext; 1490a86c6181SAlex Tomas BUG_ON(path[depth].p_hdr == NULL); 1491a86c6181SAlex Tomas 1492a86c6181SAlex Tomas /* try to insert block into found extent and return */ 1493a86c6181SAlex Tomas if (ex && ext4_can_extents_be_merged(inode, ex, newext)) { 14942ae02107SMingming Cao ext_debug("append %d block to %d:%d (from %llu)\n", 1495a2df2a63SAmit Arora ext4_ext_get_actual_len(newext), 1496a86c6181SAlex Tomas le32_to_cpu(ex->ee_block), 1497a2df2a63SAmit Arora ext4_ext_get_actual_len(ex), ext_pblock(ex)); 14987e028976SAvantika Mathur err = ext4_ext_get_access(handle, inode, path + depth); 14997e028976SAvantika Mathur if (err) 1500a86c6181SAlex Tomas return err; 1501a2df2a63SAmit Arora 1502a2df2a63SAmit Arora /* 1503a2df2a63SAmit Arora * ext4_can_extents_be_merged should have checked that either 1504a2df2a63SAmit Arora * both extents are uninitialized, or both aren't. Thus we 1505a2df2a63SAmit Arora * need to check only one of them here. 1506a2df2a63SAmit Arora */ 1507a2df2a63SAmit Arora if (ext4_ext_is_uninitialized(ex)) 1508a2df2a63SAmit Arora uninitialized = 1; 1509a2df2a63SAmit Arora ex->ee_len = cpu_to_le16(ext4_ext_get_actual_len(ex) 1510a2df2a63SAmit Arora + ext4_ext_get_actual_len(newext)); 1511a2df2a63SAmit Arora if (uninitialized) 1512a2df2a63SAmit Arora ext4_ext_mark_uninitialized(ex); 1513a86c6181SAlex Tomas eh = path[depth].p_hdr; 1514a86c6181SAlex Tomas nearex = ex; 1515a86c6181SAlex Tomas goto merge; 1516a86c6181SAlex Tomas } 1517a86c6181SAlex Tomas 1518a86c6181SAlex Tomas repeat: 1519a86c6181SAlex Tomas depth = ext_depth(inode); 1520a86c6181SAlex Tomas eh = path[depth].p_hdr; 1521a86c6181SAlex Tomas if (le16_to_cpu(eh->eh_entries) < le16_to_cpu(eh->eh_max)) 1522a86c6181SAlex Tomas goto has_space; 1523a86c6181SAlex Tomas 1524a86c6181SAlex Tomas /* probably next leaf has space for us? */ 1525a86c6181SAlex Tomas fex = EXT_LAST_EXTENT(eh); 1526a86c6181SAlex Tomas next = ext4_ext_next_leaf_block(inode, path); 1527a86c6181SAlex Tomas if (le32_to_cpu(newext->ee_block) > le32_to_cpu(fex->ee_block) 1528a86c6181SAlex Tomas && next != EXT_MAX_BLOCK) { 1529a86c6181SAlex Tomas ext_debug("next leaf block - %d\n", next); 1530a86c6181SAlex Tomas BUG_ON(npath != NULL); 1531a86c6181SAlex Tomas npath = ext4_ext_find_extent(inode, next, NULL); 1532a86c6181SAlex Tomas if (IS_ERR(npath)) 1533a86c6181SAlex Tomas return PTR_ERR(npath); 1534a86c6181SAlex Tomas BUG_ON(npath->p_depth != path->p_depth); 1535a86c6181SAlex Tomas eh = npath[depth].p_hdr; 1536a86c6181SAlex Tomas if (le16_to_cpu(eh->eh_entries) < le16_to_cpu(eh->eh_max)) { 1537a86c6181SAlex Tomas ext_debug("next leaf isnt full(%d)\n", 1538a86c6181SAlex Tomas le16_to_cpu(eh->eh_entries)); 1539a86c6181SAlex Tomas path = npath; 1540a86c6181SAlex Tomas goto repeat; 1541a86c6181SAlex Tomas } 1542a86c6181SAlex Tomas ext_debug("next leaf has no free space(%d,%d)\n", 1543a86c6181SAlex Tomas le16_to_cpu(eh->eh_entries), le16_to_cpu(eh->eh_max)); 1544a86c6181SAlex Tomas } 1545a86c6181SAlex Tomas 1546a86c6181SAlex Tomas /* 1547d0d856e8SRandy Dunlap * There is no free space in the found leaf. 1548d0d856e8SRandy Dunlap * We're gonna add a new leaf in the tree. 1549a86c6181SAlex Tomas */ 1550a86c6181SAlex Tomas err = ext4_ext_create_new_leaf(handle, inode, path, newext); 1551a86c6181SAlex Tomas if (err) 1552a86c6181SAlex Tomas goto cleanup; 1553a86c6181SAlex Tomas depth = ext_depth(inode); 1554a86c6181SAlex Tomas eh = path[depth].p_hdr; 1555a86c6181SAlex Tomas 1556a86c6181SAlex Tomas has_space: 1557a86c6181SAlex Tomas nearex = path[depth].p_ext; 1558a86c6181SAlex Tomas 15597e028976SAvantika Mathur err = ext4_ext_get_access(handle, inode, path + depth); 15607e028976SAvantika Mathur if (err) 1561a86c6181SAlex Tomas goto cleanup; 1562a86c6181SAlex Tomas 1563a86c6181SAlex Tomas if (!nearex) { 1564a86c6181SAlex Tomas /* there is no extent in this leaf, create first one */ 15652ae02107SMingming Cao ext_debug("first extent in the leaf: %d:%llu:%d\n", 1566a86c6181SAlex Tomas le32_to_cpu(newext->ee_block), 1567f65e6fbaSAlex Tomas ext_pblock(newext), 1568a2df2a63SAmit Arora ext4_ext_get_actual_len(newext)); 1569a86c6181SAlex Tomas path[depth].p_ext = EXT_FIRST_EXTENT(eh); 1570a86c6181SAlex Tomas } else if (le32_to_cpu(newext->ee_block) 1571a86c6181SAlex Tomas > le32_to_cpu(nearex->ee_block)) { 1572a86c6181SAlex Tomas /* BUG_ON(newext->ee_block == nearex->ee_block); */ 1573a86c6181SAlex Tomas if (nearex != EXT_LAST_EXTENT(eh)) { 1574a86c6181SAlex Tomas len = EXT_MAX_EXTENT(eh) - nearex; 1575a86c6181SAlex Tomas len = (len - 1) * sizeof(struct ext4_extent); 1576a86c6181SAlex Tomas len = len < 0 ? 0 : len; 15772ae02107SMingming Cao ext_debug("insert %d:%llu:%d after: nearest 0x%p, " 1578a86c6181SAlex Tomas "move %d from 0x%p to 0x%p\n", 1579a86c6181SAlex Tomas le32_to_cpu(newext->ee_block), 1580f65e6fbaSAlex Tomas ext_pblock(newext), 1581a2df2a63SAmit Arora ext4_ext_get_actual_len(newext), 1582a86c6181SAlex Tomas nearex, len, nearex + 1, nearex + 2); 1583a86c6181SAlex Tomas memmove(nearex + 2, nearex + 1, len); 1584a86c6181SAlex Tomas } 1585a86c6181SAlex Tomas path[depth].p_ext = nearex + 1; 1586a86c6181SAlex Tomas } else { 1587a86c6181SAlex Tomas BUG_ON(newext->ee_block == nearex->ee_block); 1588a86c6181SAlex Tomas len = (EXT_MAX_EXTENT(eh) - nearex) * sizeof(struct ext4_extent); 1589a86c6181SAlex Tomas len = len < 0 ? 0 : len; 15902ae02107SMingming Cao ext_debug("insert %d:%llu:%d before: nearest 0x%p, " 1591a86c6181SAlex Tomas "move %d from 0x%p to 0x%p\n", 1592a86c6181SAlex Tomas le32_to_cpu(newext->ee_block), 1593f65e6fbaSAlex Tomas ext_pblock(newext), 1594a2df2a63SAmit Arora ext4_ext_get_actual_len(newext), 1595a86c6181SAlex Tomas nearex, len, nearex + 1, nearex + 2); 1596a86c6181SAlex Tomas memmove(nearex + 1, nearex, len); 1597a86c6181SAlex Tomas path[depth].p_ext = nearex; 1598a86c6181SAlex Tomas } 1599a86c6181SAlex Tomas 1600e8546d06SMarcin Slusarz le16_add_cpu(&eh->eh_entries, 1); 1601a86c6181SAlex Tomas nearex = path[depth].p_ext; 1602a86c6181SAlex Tomas nearex->ee_block = newext->ee_block; 1603b377611dSAneesh Kumar K.V ext4_ext_store_pblock(nearex, ext_pblock(newext)); 1604a86c6181SAlex Tomas nearex->ee_len = newext->ee_len; 1605a86c6181SAlex Tomas 1606a86c6181SAlex Tomas merge: 1607a86c6181SAlex Tomas /* try to merge extents to the right */ 160856055d3aSAmit Arora ext4_ext_try_to_merge(inode, path, nearex); 1609a86c6181SAlex Tomas 1610a86c6181SAlex Tomas /* try to merge extents to the left */ 1611a86c6181SAlex Tomas 1612a86c6181SAlex Tomas /* time to correct all indexes above */ 1613a86c6181SAlex Tomas err = ext4_ext_correct_indexes(handle, inode, path); 1614a86c6181SAlex Tomas if (err) 1615a86c6181SAlex Tomas goto cleanup; 1616a86c6181SAlex Tomas 1617a86c6181SAlex Tomas err = ext4_ext_dirty(handle, inode, path + depth); 1618a86c6181SAlex Tomas 1619a86c6181SAlex Tomas cleanup: 1620a86c6181SAlex Tomas if (npath) { 1621a86c6181SAlex Tomas ext4_ext_drop_refs(npath); 1622a86c6181SAlex Tomas kfree(npath); 1623a86c6181SAlex Tomas } 1624a86c6181SAlex Tomas ext4_ext_invalidate_cache(inode); 1625a86c6181SAlex Tomas return err; 1626a86c6181SAlex Tomas } 1627a86c6181SAlex Tomas 16286873fa0dSEric Sandeen int ext4_ext_walk_space(struct inode *inode, ext4_lblk_t block, 16296873fa0dSEric Sandeen ext4_lblk_t num, ext_prepare_callback func, 16306873fa0dSEric Sandeen void *cbdata) 16316873fa0dSEric Sandeen { 16326873fa0dSEric Sandeen struct ext4_ext_path *path = NULL; 16336873fa0dSEric Sandeen struct ext4_ext_cache cbex; 16346873fa0dSEric Sandeen struct ext4_extent *ex; 16356873fa0dSEric Sandeen ext4_lblk_t next, start = 0, end = 0; 16366873fa0dSEric Sandeen ext4_lblk_t last = block + num; 16376873fa0dSEric Sandeen int depth, exists, err = 0; 16386873fa0dSEric Sandeen 16396873fa0dSEric Sandeen BUG_ON(func == NULL); 16406873fa0dSEric Sandeen BUG_ON(inode == NULL); 16416873fa0dSEric Sandeen 16426873fa0dSEric Sandeen while (block < last && block != EXT_MAX_BLOCK) { 16436873fa0dSEric Sandeen num = last - block; 16446873fa0dSEric Sandeen /* find extent for this block */ 16456873fa0dSEric Sandeen path = ext4_ext_find_extent(inode, block, path); 16466873fa0dSEric Sandeen if (IS_ERR(path)) { 16476873fa0dSEric Sandeen err = PTR_ERR(path); 16486873fa0dSEric Sandeen path = NULL; 16496873fa0dSEric Sandeen break; 16506873fa0dSEric Sandeen } 16516873fa0dSEric Sandeen 16526873fa0dSEric Sandeen depth = ext_depth(inode); 16536873fa0dSEric Sandeen BUG_ON(path[depth].p_hdr == NULL); 16546873fa0dSEric Sandeen ex = path[depth].p_ext; 16556873fa0dSEric Sandeen next = ext4_ext_next_allocated_block(path); 16566873fa0dSEric Sandeen 16576873fa0dSEric Sandeen exists = 0; 16586873fa0dSEric Sandeen if (!ex) { 16596873fa0dSEric Sandeen /* there is no extent yet, so try to allocate 16606873fa0dSEric Sandeen * all requested space */ 16616873fa0dSEric Sandeen start = block; 16626873fa0dSEric Sandeen end = block + num; 16636873fa0dSEric Sandeen } else if (le32_to_cpu(ex->ee_block) > block) { 16646873fa0dSEric Sandeen /* need to allocate space before found extent */ 16656873fa0dSEric Sandeen start = block; 16666873fa0dSEric Sandeen end = le32_to_cpu(ex->ee_block); 16676873fa0dSEric Sandeen if (block + num < end) 16686873fa0dSEric Sandeen end = block + num; 16696873fa0dSEric Sandeen } else if (block >= le32_to_cpu(ex->ee_block) 16706873fa0dSEric Sandeen + ext4_ext_get_actual_len(ex)) { 16716873fa0dSEric Sandeen /* need to allocate space after found extent */ 16726873fa0dSEric Sandeen start = block; 16736873fa0dSEric Sandeen end = block + num; 16746873fa0dSEric Sandeen if (end >= next) 16756873fa0dSEric Sandeen end = next; 16766873fa0dSEric Sandeen } else if (block >= le32_to_cpu(ex->ee_block)) { 16776873fa0dSEric Sandeen /* 16786873fa0dSEric Sandeen * some part of requested space is covered 16796873fa0dSEric Sandeen * by found extent 16806873fa0dSEric Sandeen */ 16816873fa0dSEric Sandeen start = block; 16826873fa0dSEric Sandeen end = le32_to_cpu(ex->ee_block) 16836873fa0dSEric Sandeen + ext4_ext_get_actual_len(ex); 16846873fa0dSEric Sandeen if (block + num < end) 16856873fa0dSEric Sandeen end = block + num; 16866873fa0dSEric Sandeen exists = 1; 16876873fa0dSEric Sandeen } else { 16886873fa0dSEric Sandeen BUG(); 16896873fa0dSEric Sandeen } 16906873fa0dSEric Sandeen BUG_ON(end <= start); 16916873fa0dSEric Sandeen 16926873fa0dSEric Sandeen if (!exists) { 16936873fa0dSEric Sandeen cbex.ec_block = start; 16946873fa0dSEric Sandeen cbex.ec_len = end - start; 16956873fa0dSEric Sandeen cbex.ec_start = 0; 16966873fa0dSEric Sandeen cbex.ec_type = EXT4_EXT_CACHE_GAP; 16976873fa0dSEric Sandeen } else { 16986873fa0dSEric Sandeen cbex.ec_block = le32_to_cpu(ex->ee_block); 16996873fa0dSEric Sandeen cbex.ec_len = ext4_ext_get_actual_len(ex); 17006873fa0dSEric Sandeen cbex.ec_start = ext_pblock(ex); 17016873fa0dSEric Sandeen cbex.ec_type = EXT4_EXT_CACHE_EXTENT; 17026873fa0dSEric Sandeen } 17036873fa0dSEric Sandeen 17046873fa0dSEric Sandeen BUG_ON(cbex.ec_len == 0); 17056873fa0dSEric Sandeen err = func(inode, path, &cbex, ex, cbdata); 17066873fa0dSEric Sandeen ext4_ext_drop_refs(path); 17076873fa0dSEric Sandeen 17086873fa0dSEric Sandeen if (err < 0) 17096873fa0dSEric Sandeen break; 17106873fa0dSEric Sandeen 17116873fa0dSEric Sandeen if (err == EXT_REPEAT) 17126873fa0dSEric Sandeen continue; 17136873fa0dSEric Sandeen else if (err == EXT_BREAK) { 17146873fa0dSEric Sandeen err = 0; 17156873fa0dSEric Sandeen break; 17166873fa0dSEric Sandeen } 17176873fa0dSEric Sandeen 17186873fa0dSEric Sandeen if (ext_depth(inode) != depth) { 17196873fa0dSEric Sandeen /* depth was changed. we have to realloc path */ 17206873fa0dSEric Sandeen kfree(path); 17216873fa0dSEric Sandeen path = NULL; 17226873fa0dSEric Sandeen } 17236873fa0dSEric Sandeen 17246873fa0dSEric Sandeen block = cbex.ec_block + cbex.ec_len; 17256873fa0dSEric Sandeen } 17266873fa0dSEric Sandeen 17276873fa0dSEric Sandeen if (path) { 17286873fa0dSEric Sandeen ext4_ext_drop_refs(path); 17296873fa0dSEric Sandeen kfree(path); 17306873fa0dSEric Sandeen } 17316873fa0dSEric Sandeen 17326873fa0dSEric Sandeen return err; 17336873fa0dSEric Sandeen } 17346873fa0dSEric Sandeen 173509b88252SAvantika Mathur static void 1736725d26d3SAneesh Kumar K.V ext4_ext_put_in_cache(struct inode *inode, ext4_lblk_t block, 1737dd54567aSMingming Cao __u32 len, ext4_fsblk_t start, int type) 1738a86c6181SAlex Tomas { 1739a86c6181SAlex Tomas struct ext4_ext_cache *cex; 1740a86c6181SAlex Tomas BUG_ON(len == 0); 1741a86c6181SAlex Tomas cex = &EXT4_I(inode)->i_cached_extent; 1742a86c6181SAlex Tomas cex->ec_type = type; 1743a86c6181SAlex Tomas cex->ec_block = block; 1744a86c6181SAlex Tomas cex->ec_len = len; 1745a86c6181SAlex Tomas cex->ec_start = start; 1746a86c6181SAlex Tomas } 1747a86c6181SAlex Tomas 1748a86c6181SAlex Tomas /* 1749d0d856e8SRandy Dunlap * ext4_ext_put_gap_in_cache: 1750d0d856e8SRandy Dunlap * calculate boundaries of the gap that the requested block fits into 1751a86c6181SAlex Tomas * and cache this gap 1752a86c6181SAlex Tomas */ 175309b88252SAvantika Mathur static void 1754a86c6181SAlex Tomas ext4_ext_put_gap_in_cache(struct inode *inode, struct ext4_ext_path *path, 1755725d26d3SAneesh Kumar K.V ext4_lblk_t block) 1756a86c6181SAlex Tomas { 1757a86c6181SAlex Tomas int depth = ext_depth(inode); 1758725d26d3SAneesh Kumar K.V unsigned long len; 1759725d26d3SAneesh Kumar K.V ext4_lblk_t lblock; 1760a86c6181SAlex Tomas struct ext4_extent *ex; 1761a86c6181SAlex Tomas 1762a86c6181SAlex Tomas ex = path[depth].p_ext; 1763a86c6181SAlex Tomas if (ex == NULL) { 1764a86c6181SAlex Tomas /* there is no extent yet, so gap is [0;-] */ 1765a86c6181SAlex Tomas lblock = 0; 1766a86c6181SAlex Tomas len = EXT_MAX_BLOCK; 1767a86c6181SAlex Tomas ext_debug("cache gap(whole file):"); 1768a86c6181SAlex Tomas } else if (block < le32_to_cpu(ex->ee_block)) { 1769a86c6181SAlex Tomas lblock = block; 1770a86c6181SAlex Tomas len = le32_to_cpu(ex->ee_block) - block; 1771bba90743SEric Sandeen ext_debug("cache gap(before): %u [%u:%u]", 1772bba90743SEric Sandeen block, 1773bba90743SEric Sandeen le32_to_cpu(ex->ee_block), 1774bba90743SEric Sandeen ext4_ext_get_actual_len(ex)); 1775a86c6181SAlex Tomas } else if (block >= le32_to_cpu(ex->ee_block) 1776a2df2a63SAmit Arora + ext4_ext_get_actual_len(ex)) { 1777725d26d3SAneesh Kumar K.V ext4_lblk_t next; 1778a86c6181SAlex Tomas lblock = le32_to_cpu(ex->ee_block) 1779a2df2a63SAmit Arora + ext4_ext_get_actual_len(ex); 1780725d26d3SAneesh Kumar K.V 1781725d26d3SAneesh Kumar K.V next = ext4_ext_next_allocated_block(path); 1782bba90743SEric Sandeen ext_debug("cache gap(after): [%u:%u] %u", 1783bba90743SEric Sandeen le32_to_cpu(ex->ee_block), 1784bba90743SEric Sandeen ext4_ext_get_actual_len(ex), 1785bba90743SEric Sandeen block); 1786725d26d3SAneesh Kumar K.V BUG_ON(next == lblock); 1787725d26d3SAneesh Kumar K.V len = next - lblock; 1788a86c6181SAlex Tomas } else { 1789a86c6181SAlex Tomas lblock = len = 0; 1790a86c6181SAlex Tomas BUG(); 1791a86c6181SAlex Tomas } 1792a86c6181SAlex Tomas 1793bba90743SEric Sandeen ext_debug(" -> %u:%lu\n", lblock, len); 1794a86c6181SAlex Tomas ext4_ext_put_in_cache(inode, lblock, len, 0, EXT4_EXT_CACHE_GAP); 1795a86c6181SAlex Tomas } 1796a86c6181SAlex Tomas 179709b88252SAvantika Mathur static int 1798725d26d3SAneesh Kumar K.V ext4_ext_in_cache(struct inode *inode, ext4_lblk_t block, 1799a86c6181SAlex Tomas struct ext4_extent *ex) 1800a86c6181SAlex Tomas { 1801a86c6181SAlex Tomas struct ext4_ext_cache *cex; 1802a86c6181SAlex Tomas 1803a86c6181SAlex Tomas cex = &EXT4_I(inode)->i_cached_extent; 1804a86c6181SAlex Tomas 1805a86c6181SAlex Tomas /* has cache valid data? */ 1806a86c6181SAlex Tomas if (cex->ec_type == EXT4_EXT_CACHE_NO) 1807a86c6181SAlex Tomas return EXT4_EXT_CACHE_NO; 1808a86c6181SAlex Tomas 1809a86c6181SAlex Tomas BUG_ON(cex->ec_type != EXT4_EXT_CACHE_GAP && 1810a86c6181SAlex Tomas cex->ec_type != EXT4_EXT_CACHE_EXTENT); 1811a86c6181SAlex Tomas if (block >= cex->ec_block && block < cex->ec_block + cex->ec_len) { 1812a86c6181SAlex Tomas ex->ee_block = cpu_to_le32(cex->ec_block); 1813f65e6fbaSAlex Tomas ext4_ext_store_pblock(ex, cex->ec_start); 1814a86c6181SAlex Tomas ex->ee_len = cpu_to_le16(cex->ec_len); 1815bba90743SEric Sandeen ext_debug("%u cached by %u:%u:%llu\n", 1816bba90743SEric Sandeen block, 1817bba90743SEric Sandeen cex->ec_block, cex->ec_len, cex->ec_start); 1818a86c6181SAlex Tomas return cex->ec_type; 1819a86c6181SAlex Tomas } 1820a86c6181SAlex Tomas 1821a86c6181SAlex Tomas /* not in cache */ 1822a86c6181SAlex Tomas return EXT4_EXT_CACHE_NO; 1823a86c6181SAlex Tomas } 1824a86c6181SAlex Tomas 1825a86c6181SAlex Tomas /* 1826d0d856e8SRandy Dunlap * ext4_ext_rm_idx: 1827d0d856e8SRandy Dunlap * removes index from the index block. 1828d0d856e8SRandy Dunlap * It's used in truncate case only, thus all requests are for 1829d0d856e8SRandy Dunlap * last index in the block only. 1830a86c6181SAlex Tomas */ 18311d03ec98SAneesh Kumar K.V static int ext4_ext_rm_idx(handle_t *handle, struct inode *inode, 1832a86c6181SAlex Tomas struct ext4_ext_path *path) 1833a86c6181SAlex Tomas { 1834a86c6181SAlex Tomas struct buffer_head *bh; 1835a86c6181SAlex Tomas int err; 1836f65e6fbaSAlex Tomas ext4_fsblk_t leaf; 1837a86c6181SAlex Tomas 1838a86c6181SAlex Tomas /* free index block */ 1839a86c6181SAlex Tomas path--; 1840f65e6fbaSAlex Tomas leaf = idx_pblock(path->p_idx); 1841a86c6181SAlex Tomas BUG_ON(path->p_hdr->eh_entries == 0); 18427e028976SAvantika Mathur err = ext4_ext_get_access(handle, inode, path); 18437e028976SAvantika Mathur if (err) 1844a86c6181SAlex Tomas return err; 1845e8546d06SMarcin Slusarz le16_add_cpu(&path->p_hdr->eh_entries, -1); 18467e028976SAvantika Mathur err = ext4_ext_dirty(handle, inode, path); 18477e028976SAvantika Mathur if (err) 1848a86c6181SAlex Tomas return err; 18492ae02107SMingming Cao ext_debug("index is empty, remove it, free block %llu\n", leaf); 1850a86c6181SAlex Tomas bh = sb_find_get_block(inode->i_sb, leaf); 1851a86c6181SAlex Tomas ext4_forget(handle, 1, inode, bh, leaf); 1852c9de560dSAlex Tomas ext4_free_blocks(handle, inode, leaf, 1, 1); 1853a86c6181SAlex Tomas return err; 1854a86c6181SAlex Tomas } 1855a86c6181SAlex Tomas 1856a86c6181SAlex Tomas /* 1857ee12b630SMingming Cao * ext4_ext_calc_credits_for_single_extent: 1858ee12b630SMingming Cao * This routine returns max. credits that needed to insert an extent 1859ee12b630SMingming Cao * to the extent tree. 1860ee12b630SMingming Cao * When pass the actual path, the caller should calculate credits 1861ee12b630SMingming Cao * under i_data_sem. 1862a86c6181SAlex Tomas */ 1863525f4ed8SMingming Cao int ext4_ext_calc_credits_for_single_extent(struct inode *inode, int nrblocks, 1864a86c6181SAlex Tomas struct ext4_ext_path *path) 1865a86c6181SAlex Tomas { 1866a86c6181SAlex Tomas if (path) { 1867ee12b630SMingming Cao int depth = ext_depth(inode); 1868f3bd1f3fSMingming Cao int ret = 0; 1869ee12b630SMingming Cao 1870a86c6181SAlex Tomas /* probably there is space in leaf? */ 1871a86c6181SAlex Tomas if (le16_to_cpu(path[depth].p_hdr->eh_entries) 1872ee12b630SMingming Cao < le16_to_cpu(path[depth].p_hdr->eh_max)) { 1873ee12b630SMingming Cao 1874ee12b630SMingming Cao /* 1875ee12b630SMingming Cao * There are some space in the leaf tree, no 1876ee12b630SMingming Cao * need to account for leaf block credit 1877ee12b630SMingming Cao * 1878ee12b630SMingming Cao * bitmaps and block group descriptor blocks 1879ee12b630SMingming Cao * and other metadat blocks still need to be 1880ee12b630SMingming Cao * accounted. 1881ee12b630SMingming Cao */ 1882525f4ed8SMingming Cao /* 1 bitmap, 1 block group descriptor */ 1883ee12b630SMingming Cao ret = 2 + EXT4_META_TRANS_BLOCKS(inode->i_sb); 1884ee12b630SMingming Cao } 1885ee12b630SMingming Cao } 1886ee12b630SMingming Cao 1887525f4ed8SMingming Cao return ext4_chunk_trans_blocks(inode, nrblocks); 1888a86c6181SAlex Tomas } 1889a86c6181SAlex Tomas 1890a86c6181SAlex Tomas /* 1891ee12b630SMingming Cao * How many index/leaf blocks need to change/allocate to modify nrblocks? 1892ee12b630SMingming Cao * 1893ee12b630SMingming Cao * if nrblocks are fit in a single extent (chunk flag is 1), then 1894ee12b630SMingming Cao * in the worse case, each tree level index/leaf need to be changed 1895ee12b630SMingming Cao * if the tree split due to insert a new extent, then the old tree 1896ee12b630SMingming Cao * index/leaf need to be updated too 1897ee12b630SMingming Cao * 1898ee12b630SMingming Cao * If the nrblocks are discontiguous, they could cause 1899ee12b630SMingming Cao * the whole tree split more than once, but this is really rare. 1900a86c6181SAlex Tomas */ 1901525f4ed8SMingming Cao int ext4_ext_index_trans_blocks(struct inode *inode, int nrblocks, int chunk) 1902ee12b630SMingming Cao { 1903ee12b630SMingming Cao int index; 1904ee12b630SMingming Cao int depth = ext_depth(inode); 1905a86c6181SAlex Tomas 1906ee12b630SMingming Cao if (chunk) 1907ee12b630SMingming Cao index = depth * 2; 1908ee12b630SMingming Cao else 1909ee12b630SMingming Cao index = depth * 3; 1910a86c6181SAlex Tomas 1911ee12b630SMingming Cao return index; 1912a86c6181SAlex Tomas } 1913a86c6181SAlex Tomas 1914a86c6181SAlex Tomas static int ext4_remove_blocks(handle_t *handle, struct inode *inode, 1915a86c6181SAlex Tomas struct ext4_extent *ex, 1916725d26d3SAneesh Kumar K.V ext4_lblk_t from, ext4_lblk_t to) 1917a86c6181SAlex Tomas { 1918a86c6181SAlex Tomas struct buffer_head *bh; 1919a2df2a63SAmit Arora unsigned short ee_len = ext4_ext_get_actual_len(ex); 1920c9de560dSAlex Tomas int i, metadata = 0; 1921a86c6181SAlex Tomas 1922c9de560dSAlex Tomas if (S_ISDIR(inode->i_mode) || S_ISLNK(inode->i_mode)) 1923c9de560dSAlex Tomas metadata = 1; 1924a86c6181SAlex Tomas #ifdef EXTENTS_STATS 1925a86c6181SAlex Tomas { 1926a86c6181SAlex Tomas struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb); 1927a86c6181SAlex Tomas spin_lock(&sbi->s_ext_stats_lock); 1928a86c6181SAlex Tomas sbi->s_ext_blocks += ee_len; 1929a86c6181SAlex Tomas sbi->s_ext_extents++; 1930a86c6181SAlex Tomas if (ee_len < sbi->s_ext_min) 1931a86c6181SAlex Tomas sbi->s_ext_min = ee_len; 1932a86c6181SAlex Tomas if (ee_len > sbi->s_ext_max) 1933a86c6181SAlex Tomas sbi->s_ext_max = ee_len; 1934a86c6181SAlex Tomas if (ext_depth(inode) > sbi->s_depth_max) 1935a86c6181SAlex Tomas sbi->s_depth_max = ext_depth(inode); 1936a86c6181SAlex Tomas spin_unlock(&sbi->s_ext_stats_lock); 1937a86c6181SAlex Tomas } 1938a86c6181SAlex Tomas #endif 1939a86c6181SAlex Tomas if (from >= le32_to_cpu(ex->ee_block) 1940a2df2a63SAmit Arora && to == le32_to_cpu(ex->ee_block) + ee_len - 1) { 1941a86c6181SAlex Tomas /* tail removal */ 1942725d26d3SAneesh Kumar K.V ext4_lblk_t num; 1943f65e6fbaSAlex Tomas ext4_fsblk_t start; 1944725d26d3SAneesh Kumar K.V 1945a2df2a63SAmit Arora num = le32_to_cpu(ex->ee_block) + ee_len - from; 1946a2df2a63SAmit Arora start = ext_pblock(ex) + ee_len - num; 1947725d26d3SAneesh Kumar K.V ext_debug("free last %u blocks starting %llu\n", num, start); 1948a86c6181SAlex Tomas for (i = 0; i < num; i++) { 1949a86c6181SAlex Tomas bh = sb_find_get_block(inode->i_sb, start + i); 1950a86c6181SAlex Tomas ext4_forget(handle, 0, inode, bh, start + i); 1951a86c6181SAlex Tomas } 1952c9de560dSAlex Tomas ext4_free_blocks(handle, inode, start, num, metadata); 1953a86c6181SAlex Tomas } else if (from == le32_to_cpu(ex->ee_block) 1954a2df2a63SAmit Arora && to <= le32_to_cpu(ex->ee_block) + ee_len - 1) { 1955725d26d3SAneesh Kumar K.V printk(KERN_INFO "strange request: removal %u-%u from %u:%u\n", 1956a2df2a63SAmit Arora from, to, le32_to_cpu(ex->ee_block), ee_len); 1957a86c6181SAlex Tomas } else { 1958725d26d3SAneesh Kumar K.V printk(KERN_INFO "strange request: removal(2) " 1959725d26d3SAneesh Kumar K.V "%u-%u from %u:%u\n", 1960a2df2a63SAmit Arora from, to, le32_to_cpu(ex->ee_block), ee_len); 1961a86c6181SAlex Tomas } 1962a86c6181SAlex Tomas return 0; 1963a86c6181SAlex Tomas } 1964a86c6181SAlex Tomas 1965a86c6181SAlex Tomas static int 1966a86c6181SAlex Tomas ext4_ext_rm_leaf(handle_t *handle, struct inode *inode, 1967725d26d3SAneesh Kumar K.V struct ext4_ext_path *path, ext4_lblk_t start) 1968a86c6181SAlex Tomas { 1969a86c6181SAlex Tomas int err = 0, correct_index = 0; 1970a86c6181SAlex Tomas int depth = ext_depth(inode), credits; 1971a86c6181SAlex Tomas struct ext4_extent_header *eh; 1972725d26d3SAneesh Kumar K.V ext4_lblk_t a, b, block; 1973725d26d3SAneesh Kumar K.V unsigned num; 1974725d26d3SAneesh Kumar K.V ext4_lblk_t ex_ee_block; 1975a86c6181SAlex Tomas unsigned short ex_ee_len; 1976a2df2a63SAmit Arora unsigned uninitialized = 0; 1977a86c6181SAlex Tomas struct ext4_extent *ex; 1978a86c6181SAlex Tomas 1979c29c0ae7SAlex Tomas /* the header must be checked already in ext4_ext_remove_space() */ 1980725d26d3SAneesh Kumar K.V ext_debug("truncate since %u in leaf\n", start); 1981a86c6181SAlex Tomas if (!path[depth].p_hdr) 1982a86c6181SAlex Tomas path[depth].p_hdr = ext_block_hdr(path[depth].p_bh); 1983a86c6181SAlex Tomas eh = path[depth].p_hdr; 1984a86c6181SAlex Tomas BUG_ON(eh == NULL); 1985a86c6181SAlex Tomas 1986a86c6181SAlex Tomas /* find where to start removing */ 1987a86c6181SAlex Tomas ex = EXT_LAST_EXTENT(eh); 1988a86c6181SAlex Tomas 1989a86c6181SAlex Tomas ex_ee_block = le32_to_cpu(ex->ee_block); 1990a2df2a63SAmit Arora if (ext4_ext_is_uninitialized(ex)) 1991a2df2a63SAmit Arora uninitialized = 1; 1992a2df2a63SAmit Arora ex_ee_len = ext4_ext_get_actual_len(ex); 1993a86c6181SAlex Tomas 1994a86c6181SAlex Tomas while (ex >= EXT_FIRST_EXTENT(eh) && 1995a86c6181SAlex Tomas ex_ee_block + ex_ee_len > start) { 1996a86c6181SAlex Tomas ext_debug("remove ext %lu:%u\n", ex_ee_block, ex_ee_len); 1997a86c6181SAlex Tomas path[depth].p_ext = ex; 1998a86c6181SAlex Tomas 1999a86c6181SAlex Tomas a = ex_ee_block > start ? ex_ee_block : start; 2000a86c6181SAlex Tomas b = ex_ee_block + ex_ee_len - 1 < EXT_MAX_BLOCK ? 2001a86c6181SAlex Tomas ex_ee_block + ex_ee_len - 1 : EXT_MAX_BLOCK; 2002a86c6181SAlex Tomas 2003a86c6181SAlex Tomas ext_debug(" border %u:%u\n", a, b); 2004a86c6181SAlex Tomas 2005a86c6181SAlex Tomas if (a != ex_ee_block && b != ex_ee_block + ex_ee_len - 1) { 2006a86c6181SAlex Tomas block = 0; 2007a86c6181SAlex Tomas num = 0; 2008a86c6181SAlex Tomas BUG(); 2009a86c6181SAlex Tomas } else if (a != ex_ee_block) { 2010a86c6181SAlex Tomas /* remove tail of the extent */ 2011a86c6181SAlex Tomas block = ex_ee_block; 2012a86c6181SAlex Tomas num = a - block; 2013a86c6181SAlex Tomas } else if (b != ex_ee_block + ex_ee_len - 1) { 2014a86c6181SAlex Tomas /* remove head of the extent */ 2015a86c6181SAlex Tomas block = a; 2016a86c6181SAlex Tomas num = b - a; 2017a86c6181SAlex Tomas /* there is no "make a hole" API yet */ 2018a86c6181SAlex Tomas BUG(); 2019a86c6181SAlex Tomas } else { 2020a86c6181SAlex Tomas /* remove whole extent: excellent! */ 2021a86c6181SAlex Tomas block = ex_ee_block; 2022a86c6181SAlex Tomas num = 0; 2023a86c6181SAlex Tomas BUG_ON(a != ex_ee_block); 2024a86c6181SAlex Tomas BUG_ON(b != ex_ee_block + ex_ee_len - 1); 2025a86c6181SAlex Tomas } 2026a86c6181SAlex Tomas 202734071da7STheodore Ts'o /* 202834071da7STheodore Ts'o * 3 for leaf, sb, and inode plus 2 (bmap and group 202934071da7STheodore Ts'o * descriptor) for each block group; assume two block 203034071da7STheodore Ts'o * groups plus ex_ee_len/blocks_per_block_group for 203134071da7STheodore Ts'o * the worst case 203234071da7STheodore Ts'o */ 203334071da7STheodore Ts'o credits = 7 + 2*(ex_ee_len/EXT4_BLOCKS_PER_GROUP(inode->i_sb)); 2034a86c6181SAlex Tomas if (ex == EXT_FIRST_EXTENT(eh)) { 2035a86c6181SAlex Tomas correct_index = 1; 2036a86c6181SAlex Tomas credits += (ext_depth(inode)) + 1; 2037a86c6181SAlex Tomas } 2038a86c6181SAlex Tomas credits += 2 * EXT4_QUOTA_TRANS_BLOCKS(inode->i_sb); 2039a86c6181SAlex Tomas 20409102e4faSShen Feng err = ext4_ext_journal_restart(handle, credits); 20419102e4faSShen Feng if (err) 2042a86c6181SAlex Tomas goto out; 2043a86c6181SAlex Tomas 2044a86c6181SAlex Tomas err = ext4_ext_get_access(handle, inode, path + depth); 2045a86c6181SAlex Tomas if (err) 2046a86c6181SAlex Tomas goto out; 2047a86c6181SAlex Tomas 2048a86c6181SAlex Tomas err = ext4_remove_blocks(handle, inode, ex, a, b); 2049a86c6181SAlex Tomas if (err) 2050a86c6181SAlex Tomas goto out; 2051a86c6181SAlex Tomas 2052a86c6181SAlex Tomas if (num == 0) { 2053d0d856e8SRandy Dunlap /* this extent is removed; mark slot entirely unused */ 2054f65e6fbaSAlex Tomas ext4_ext_store_pblock(ex, 0); 2055e8546d06SMarcin Slusarz le16_add_cpu(&eh->eh_entries, -1); 2056a86c6181SAlex Tomas } 2057a86c6181SAlex Tomas 2058a86c6181SAlex Tomas ex->ee_block = cpu_to_le32(block); 2059a86c6181SAlex Tomas ex->ee_len = cpu_to_le16(num); 2060749269faSAmit Arora /* 2061749269faSAmit Arora * Do not mark uninitialized if all the blocks in the 2062749269faSAmit Arora * extent have been removed. 2063749269faSAmit Arora */ 2064749269faSAmit Arora if (uninitialized && num) 2065a2df2a63SAmit Arora ext4_ext_mark_uninitialized(ex); 2066a86c6181SAlex Tomas 2067a86c6181SAlex Tomas err = ext4_ext_dirty(handle, inode, path + depth); 2068a86c6181SAlex Tomas if (err) 2069a86c6181SAlex Tomas goto out; 2070a86c6181SAlex Tomas 20712ae02107SMingming Cao ext_debug("new extent: %u:%u:%llu\n", block, num, 2072f65e6fbaSAlex Tomas ext_pblock(ex)); 2073a86c6181SAlex Tomas ex--; 2074a86c6181SAlex Tomas ex_ee_block = le32_to_cpu(ex->ee_block); 2075a2df2a63SAmit Arora ex_ee_len = ext4_ext_get_actual_len(ex); 2076a86c6181SAlex Tomas } 2077a86c6181SAlex Tomas 2078a86c6181SAlex Tomas if (correct_index && eh->eh_entries) 2079a86c6181SAlex Tomas err = ext4_ext_correct_indexes(handle, inode, path); 2080a86c6181SAlex Tomas 2081a86c6181SAlex Tomas /* if this leaf is free, then we should 2082a86c6181SAlex Tomas * remove it from index block above */ 2083a86c6181SAlex Tomas if (err == 0 && eh->eh_entries == 0 && path[depth].p_bh != NULL) 2084a86c6181SAlex Tomas err = ext4_ext_rm_idx(handle, inode, path + depth); 2085a86c6181SAlex Tomas 2086a86c6181SAlex Tomas out: 2087a86c6181SAlex Tomas return err; 2088a86c6181SAlex Tomas } 2089a86c6181SAlex Tomas 2090a86c6181SAlex Tomas /* 2091d0d856e8SRandy Dunlap * ext4_ext_more_to_rm: 2092d0d856e8SRandy Dunlap * returns 1 if current index has to be freed (even partial) 2093a86c6181SAlex Tomas */ 209409b88252SAvantika Mathur static int 2095a86c6181SAlex Tomas ext4_ext_more_to_rm(struct ext4_ext_path *path) 2096a86c6181SAlex Tomas { 2097a86c6181SAlex Tomas BUG_ON(path->p_idx == NULL); 2098a86c6181SAlex Tomas 2099a86c6181SAlex Tomas if (path->p_idx < EXT_FIRST_INDEX(path->p_hdr)) 2100a86c6181SAlex Tomas return 0; 2101a86c6181SAlex Tomas 2102a86c6181SAlex Tomas /* 2103d0d856e8SRandy Dunlap * if truncate on deeper level happened, it wasn't partial, 2104a86c6181SAlex Tomas * so we have to consider current index for truncation 2105a86c6181SAlex Tomas */ 2106a86c6181SAlex Tomas if (le16_to_cpu(path->p_hdr->eh_entries) == path->p_block) 2107a86c6181SAlex Tomas return 0; 2108a86c6181SAlex Tomas return 1; 2109a86c6181SAlex Tomas } 2110a86c6181SAlex Tomas 21111d03ec98SAneesh Kumar K.V static int ext4_ext_remove_space(struct inode *inode, ext4_lblk_t start) 2112a86c6181SAlex Tomas { 2113a86c6181SAlex Tomas struct super_block *sb = inode->i_sb; 2114a86c6181SAlex Tomas int depth = ext_depth(inode); 2115a86c6181SAlex Tomas struct ext4_ext_path *path; 2116a86c6181SAlex Tomas handle_t *handle; 2117a86c6181SAlex Tomas int i = 0, err = 0; 2118a86c6181SAlex Tomas 2119725d26d3SAneesh Kumar K.V ext_debug("truncate since %u\n", start); 2120a86c6181SAlex Tomas 2121a86c6181SAlex Tomas /* probably first extent we're gonna free will be last in block */ 2122a86c6181SAlex Tomas handle = ext4_journal_start(inode, depth + 1); 2123a86c6181SAlex Tomas if (IS_ERR(handle)) 2124a86c6181SAlex Tomas return PTR_ERR(handle); 2125a86c6181SAlex Tomas 2126a86c6181SAlex Tomas ext4_ext_invalidate_cache(inode); 2127a86c6181SAlex Tomas 2128a86c6181SAlex Tomas /* 2129d0d856e8SRandy Dunlap * We start scanning from right side, freeing all the blocks 2130d0d856e8SRandy Dunlap * after i_size and walking into the tree depth-wise. 2131a86c6181SAlex Tomas */ 2132216553c4SJosef Bacik path = kzalloc(sizeof(struct ext4_ext_path) * (depth + 1), GFP_NOFS); 2133a86c6181SAlex Tomas if (path == NULL) { 2134a86c6181SAlex Tomas ext4_journal_stop(handle); 2135a86c6181SAlex Tomas return -ENOMEM; 2136a86c6181SAlex Tomas } 2137a86c6181SAlex Tomas path[0].p_hdr = ext_inode_hdr(inode); 2138c29c0ae7SAlex Tomas if (ext4_ext_check_header(inode, path[0].p_hdr, depth)) { 2139a86c6181SAlex Tomas err = -EIO; 2140a86c6181SAlex Tomas goto out; 2141a86c6181SAlex Tomas } 2142a86c6181SAlex Tomas path[0].p_depth = depth; 2143a86c6181SAlex Tomas 2144a86c6181SAlex Tomas while (i >= 0 && err == 0) { 2145a86c6181SAlex Tomas if (i == depth) { 2146a86c6181SAlex Tomas /* this is leaf block */ 2147a86c6181SAlex Tomas err = ext4_ext_rm_leaf(handle, inode, path, start); 2148d0d856e8SRandy Dunlap /* root level has p_bh == NULL, brelse() eats this */ 2149a86c6181SAlex Tomas brelse(path[i].p_bh); 2150a86c6181SAlex Tomas path[i].p_bh = NULL; 2151a86c6181SAlex Tomas i--; 2152a86c6181SAlex Tomas continue; 2153a86c6181SAlex Tomas } 2154a86c6181SAlex Tomas 2155a86c6181SAlex Tomas /* this is index block */ 2156a86c6181SAlex Tomas if (!path[i].p_hdr) { 2157a86c6181SAlex Tomas ext_debug("initialize header\n"); 2158a86c6181SAlex Tomas path[i].p_hdr = ext_block_hdr(path[i].p_bh); 2159a86c6181SAlex Tomas } 2160a86c6181SAlex Tomas 2161a86c6181SAlex Tomas if (!path[i].p_idx) { 2162d0d856e8SRandy Dunlap /* this level hasn't been touched yet */ 2163a86c6181SAlex Tomas path[i].p_idx = EXT_LAST_INDEX(path[i].p_hdr); 2164a86c6181SAlex Tomas path[i].p_block = le16_to_cpu(path[i].p_hdr->eh_entries)+1; 2165a86c6181SAlex Tomas ext_debug("init index ptr: hdr 0x%p, num %d\n", 2166a86c6181SAlex Tomas path[i].p_hdr, 2167a86c6181SAlex Tomas le16_to_cpu(path[i].p_hdr->eh_entries)); 2168a86c6181SAlex Tomas } else { 2169d0d856e8SRandy Dunlap /* we were already here, see at next index */ 2170a86c6181SAlex Tomas path[i].p_idx--; 2171a86c6181SAlex Tomas } 2172a86c6181SAlex Tomas 2173a86c6181SAlex Tomas ext_debug("level %d - index, first 0x%p, cur 0x%p\n", 2174a86c6181SAlex Tomas i, EXT_FIRST_INDEX(path[i].p_hdr), 2175a86c6181SAlex Tomas path[i].p_idx); 2176a86c6181SAlex Tomas if (ext4_ext_more_to_rm(path + i)) { 2177c29c0ae7SAlex Tomas struct buffer_head *bh; 2178a86c6181SAlex Tomas /* go to the next level */ 21792ae02107SMingming Cao ext_debug("move to level %d (block %llu)\n", 2180f65e6fbaSAlex Tomas i + 1, idx_pblock(path[i].p_idx)); 2181a86c6181SAlex Tomas memset(path + i + 1, 0, sizeof(*path)); 2182c29c0ae7SAlex Tomas bh = sb_bread(sb, idx_pblock(path[i].p_idx)); 2183c29c0ae7SAlex Tomas if (!bh) { 2184a86c6181SAlex Tomas /* should we reset i_size? */ 2185a86c6181SAlex Tomas err = -EIO; 2186a86c6181SAlex Tomas break; 2187a86c6181SAlex Tomas } 2188c29c0ae7SAlex Tomas if (WARN_ON(i + 1 > depth)) { 2189c29c0ae7SAlex Tomas err = -EIO; 2190c29c0ae7SAlex Tomas break; 2191c29c0ae7SAlex Tomas } 2192c29c0ae7SAlex Tomas if (ext4_ext_check_header(inode, ext_block_hdr(bh), 2193c29c0ae7SAlex Tomas depth - i - 1)) { 2194c29c0ae7SAlex Tomas err = -EIO; 2195c29c0ae7SAlex Tomas break; 2196c29c0ae7SAlex Tomas } 2197c29c0ae7SAlex Tomas path[i + 1].p_bh = bh; 2198a86c6181SAlex Tomas 2199d0d856e8SRandy Dunlap /* save actual number of indexes since this 2200d0d856e8SRandy Dunlap * number is changed at the next iteration */ 2201a86c6181SAlex Tomas path[i].p_block = le16_to_cpu(path[i].p_hdr->eh_entries); 2202a86c6181SAlex Tomas i++; 2203a86c6181SAlex Tomas } else { 2204d0d856e8SRandy Dunlap /* we finished processing this index, go up */ 2205a86c6181SAlex Tomas if (path[i].p_hdr->eh_entries == 0 && i > 0) { 2206d0d856e8SRandy Dunlap /* index is empty, remove it; 2207a86c6181SAlex Tomas * handle must be already prepared by the 2208a86c6181SAlex Tomas * truncatei_leaf() */ 2209a86c6181SAlex Tomas err = ext4_ext_rm_idx(handle, inode, path + i); 2210a86c6181SAlex Tomas } 2211d0d856e8SRandy Dunlap /* root level has p_bh == NULL, brelse() eats this */ 2212a86c6181SAlex Tomas brelse(path[i].p_bh); 2213a86c6181SAlex Tomas path[i].p_bh = NULL; 2214a86c6181SAlex Tomas i--; 2215a86c6181SAlex Tomas ext_debug("return to level %d\n", i); 2216a86c6181SAlex Tomas } 2217a86c6181SAlex Tomas } 2218a86c6181SAlex Tomas 2219a86c6181SAlex Tomas /* TODO: flexible tree reduction should be here */ 2220a86c6181SAlex Tomas if (path->p_hdr->eh_entries == 0) { 2221a86c6181SAlex Tomas /* 2222d0d856e8SRandy Dunlap * truncate to zero freed all the tree, 2223d0d856e8SRandy Dunlap * so we need to correct eh_depth 2224a86c6181SAlex Tomas */ 2225a86c6181SAlex Tomas err = ext4_ext_get_access(handle, inode, path); 2226a86c6181SAlex Tomas if (err == 0) { 2227a86c6181SAlex Tomas ext_inode_hdr(inode)->eh_depth = 0; 2228a86c6181SAlex Tomas ext_inode_hdr(inode)->eh_max = 2229a86c6181SAlex Tomas cpu_to_le16(ext4_ext_space_root(inode)); 2230a86c6181SAlex Tomas err = ext4_ext_dirty(handle, inode, path); 2231a86c6181SAlex Tomas } 2232a86c6181SAlex Tomas } 2233a86c6181SAlex Tomas out: 2234a86c6181SAlex Tomas ext4_ext_drop_refs(path); 2235a86c6181SAlex Tomas kfree(path); 2236a86c6181SAlex Tomas ext4_journal_stop(handle); 2237a86c6181SAlex Tomas 2238a86c6181SAlex Tomas return err; 2239a86c6181SAlex Tomas } 2240a86c6181SAlex Tomas 2241a86c6181SAlex Tomas /* 2242a86c6181SAlex Tomas * called at mount time 2243a86c6181SAlex Tomas */ 2244a86c6181SAlex Tomas void ext4_ext_init(struct super_block *sb) 2245a86c6181SAlex Tomas { 2246a86c6181SAlex Tomas /* 2247a86c6181SAlex Tomas * possible initialization would be here 2248a86c6181SAlex Tomas */ 2249a86c6181SAlex Tomas 2250a86c6181SAlex Tomas if (test_opt(sb, EXTENTS)) { 22514776004fSTheodore Ts'o printk(KERN_INFO "EXT4-fs: file extents enabled"); 2252bbf2f9fbSRobert P. J. Day #ifdef AGGRESSIVE_TEST 2253bbf2f9fbSRobert P. J. Day printk(", aggressive tests"); 2254a86c6181SAlex Tomas #endif 2255a86c6181SAlex Tomas #ifdef CHECK_BINSEARCH 2256a86c6181SAlex Tomas printk(", check binsearch"); 2257a86c6181SAlex Tomas #endif 2258a86c6181SAlex Tomas #ifdef EXTENTS_STATS 2259a86c6181SAlex Tomas printk(", stats"); 2260a86c6181SAlex Tomas #endif 2261a86c6181SAlex Tomas printk("\n"); 2262a86c6181SAlex Tomas #ifdef EXTENTS_STATS 2263a86c6181SAlex Tomas spin_lock_init(&EXT4_SB(sb)->s_ext_stats_lock); 2264a86c6181SAlex Tomas EXT4_SB(sb)->s_ext_min = 1 << 30; 2265a86c6181SAlex Tomas EXT4_SB(sb)->s_ext_max = 0; 2266a86c6181SAlex Tomas #endif 2267a86c6181SAlex Tomas } 2268a86c6181SAlex Tomas } 2269a86c6181SAlex Tomas 2270a86c6181SAlex Tomas /* 2271a86c6181SAlex Tomas * called at umount time 2272a86c6181SAlex Tomas */ 2273a86c6181SAlex Tomas void ext4_ext_release(struct super_block *sb) 2274a86c6181SAlex Tomas { 2275a86c6181SAlex Tomas if (!test_opt(sb, EXTENTS)) 2276a86c6181SAlex Tomas return; 2277a86c6181SAlex Tomas 2278a86c6181SAlex Tomas #ifdef EXTENTS_STATS 2279a86c6181SAlex Tomas if (EXT4_SB(sb)->s_ext_blocks && EXT4_SB(sb)->s_ext_extents) { 2280a86c6181SAlex Tomas struct ext4_sb_info *sbi = EXT4_SB(sb); 2281a86c6181SAlex Tomas printk(KERN_ERR "EXT4-fs: %lu blocks in %lu extents (%lu ave)\n", 2282a86c6181SAlex Tomas sbi->s_ext_blocks, sbi->s_ext_extents, 2283a86c6181SAlex Tomas sbi->s_ext_blocks / sbi->s_ext_extents); 2284a86c6181SAlex Tomas printk(KERN_ERR "EXT4-fs: extents: %lu min, %lu max, max depth %lu\n", 2285a86c6181SAlex Tomas sbi->s_ext_min, sbi->s_ext_max, sbi->s_depth_max); 2286a86c6181SAlex Tomas } 2287a86c6181SAlex Tomas #endif 2288a86c6181SAlex Tomas } 2289a86c6181SAlex Tomas 2290093a088bSAneesh Kumar K.V static void bi_complete(struct bio *bio, int error) 2291093a088bSAneesh Kumar K.V { 2292093a088bSAneesh Kumar K.V complete((struct completion *)bio->bi_private); 2293093a088bSAneesh Kumar K.V } 2294093a088bSAneesh Kumar K.V 2295093a088bSAneesh Kumar K.V /* FIXME!! we need to try to merge to left or right after zero-out */ 2296093a088bSAneesh Kumar K.V static int ext4_ext_zeroout(struct inode *inode, struct ext4_extent *ex) 2297093a088bSAneesh Kumar K.V { 2298093a088bSAneesh Kumar K.V int ret = -EIO; 2299093a088bSAneesh Kumar K.V struct bio *bio; 2300093a088bSAneesh Kumar K.V int blkbits, blocksize; 2301093a088bSAneesh Kumar K.V sector_t ee_pblock; 2302093a088bSAneesh Kumar K.V struct completion event; 2303093a088bSAneesh Kumar K.V unsigned int ee_len, len, done, offset; 2304093a088bSAneesh Kumar K.V 2305093a088bSAneesh Kumar K.V 2306093a088bSAneesh Kumar K.V blkbits = inode->i_blkbits; 2307093a088bSAneesh Kumar K.V blocksize = inode->i_sb->s_blocksize; 2308093a088bSAneesh Kumar K.V ee_len = ext4_ext_get_actual_len(ex); 2309093a088bSAneesh Kumar K.V ee_pblock = ext_pblock(ex); 2310093a088bSAneesh Kumar K.V 2311093a088bSAneesh Kumar K.V /* convert ee_pblock to 512 byte sectors */ 2312093a088bSAneesh Kumar K.V ee_pblock = ee_pblock << (blkbits - 9); 2313093a088bSAneesh Kumar K.V 2314093a088bSAneesh Kumar K.V while (ee_len > 0) { 2315093a088bSAneesh Kumar K.V 2316093a088bSAneesh Kumar K.V if (ee_len > BIO_MAX_PAGES) 2317093a088bSAneesh Kumar K.V len = BIO_MAX_PAGES; 2318093a088bSAneesh Kumar K.V else 2319093a088bSAneesh Kumar K.V len = ee_len; 2320093a088bSAneesh Kumar K.V 2321093a088bSAneesh Kumar K.V bio = bio_alloc(GFP_NOIO, len); 2322093a088bSAneesh Kumar K.V if (!bio) 2323093a088bSAneesh Kumar K.V return -ENOMEM; 2324093a088bSAneesh Kumar K.V bio->bi_sector = ee_pblock; 2325093a088bSAneesh Kumar K.V bio->bi_bdev = inode->i_sb->s_bdev; 2326093a088bSAneesh Kumar K.V 2327093a088bSAneesh Kumar K.V done = 0; 2328093a088bSAneesh Kumar K.V offset = 0; 2329093a088bSAneesh Kumar K.V while (done < len) { 2330093a088bSAneesh Kumar K.V ret = bio_add_page(bio, ZERO_PAGE(0), 2331093a088bSAneesh Kumar K.V blocksize, offset); 2332093a088bSAneesh Kumar K.V if (ret != blocksize) { 2333093a088bSAneesh Kumar K.V /* 2334093a088bSAneesh Kumar K.V * We can't add any more pages because of 2335093a088bSAneesh Kumar K.V * hardware limitations. Start a new bio. 2336093a088bSAneesh Kumar K.V */ 2337093a088bSAneesh Kumar K.V break; 2338093a088bSAneesh Kumar K.V } 2339093a088bSAneesh Kumar K.V done++; 2340093a088bSAneesh Kumar K.V offset += blocksize; 2341093a088bSAneesh Kumar K.V if (offset >= PAGE_CACHE_SIZE) 2342093a088bSAneesh Kumar K.V offset = 0; 2343093a088bSAneesh Kumar K.V } 2344093a088bSAneesh Kumar K.V 2345093a088bSAneesh Kumar K.V init_completion(&event); 2346093a088bSAneesh Kumar K.V bio->bi_private = &event; 2347093a088bSAneesh Kumar K.V bio->bi_end_io = bi_complete; 2348093a088bSAneesh Kumar K.V submit_bio(WRITE, bio); 2349093a088bSAneesh Kumar K.V wait_for_completion(&event); 2350093a088bSAneesh Kumar K.V 2351093a088bSAneesh Kumar K.V if (test_bit(BIO_UPTODATE, &bio->bi_flags)) 2352093a088bSAneesh Kumar K.V ret = 0; 2353093a088bSAneesh Kumar K.V else { 2354093a088bSAneesh Kumar K.V ret = -EIO; 2355093a088bSAneesh Kumar K.V break; 2356093a088bSAneesh Kumar K.V } 2357093a088bSAneesh Kumar K.V bio_put(bio); 2358093a088bSAneesh Kumar K.V ee_len -= done; 2359093a088bSAneesh Kumar K.V ee_pblock += done << (blkbits - 9); 2360093a088bSAneesh Kumar K.V } 2361093a088bSAneesh Kumar K.V return ret; 2362093a088bSAneesh Kumar K.V } 2363093a088bSAneesh Kumar K.V 23643977c965SAneesh Kumar K.V #define EXT4_EXT_ZERO_LEN 7 23653977c965SAneesh Kumar K.V 236656055d3aSAmit Arora /* 236756055d3aSAmit Arora * This function is called by ext4_ext_get_blocks() if someone tries to write 236856055d3aSAmit Arora * to an uninitialized extent. It may result in splitting the uninitialized 236956055d3aSAmit Arora * extent into multiple extents (upto three - one initialized and two 237056055d3aSAmit Arora * uninitialized). 237156055d3aSAmit Arora * There are three possibilities: 237256055d3aSAmit Arora * a> There is no split required: Entire extent should be initialized 237356055d3aSAmit Arora * b> Splits in two extents: Write is happening at either end of the extent 237456055d3aSAmit Arora * c> Splits in three extents: Somone is writing in middle of the extent 237556055d3aSAmit Arora */ 2376725d26d3SAneesh Kumar K.V static int ext4_ext_convert_to_initialized(handle_t *handle, 2377725d26d3SAneesh Kumar K.V struct inode *inode, 237856055d3aSAmit Arora struct ext4_ext_path *path, 2379725d26d3SAneesh Kumar K.V ext4_lblk_t iblock, 2380*498e5f24STheodore Ts'o unsigned int max_blocks) 238156055d3aSAmit Arora { 238295c3889cSAneesh Kumar K.V struct ext4_extent *ex, newex, orig_ex; 238356055d3aSAmit Arora struct ext4_extent *ex1 = NULL; 238456055d3aSAmit Arora struct ext4_extent *ex2 = NULL; 238556055d3aSAmit Arora struct ext4_extent *ex3 = NULL; 238656055d3aSAmit Arora struct ext4_extent_header *eh; 2387725d26d3SAneesh Kumar K.V ext4_lblk_t ee_block; 2388725d26d3SAneesh Kumar K.V unsigned int allocated, ee_len, depth; 238956055d3aSAmit Arora ext4_fsblk_t newblock; 239056055d3aSAmit Arora int err = 0; 239156055d3aSAmit Arora int ret = 0; 239256055d3aSAmit Arora 239356055d3aSAmit Arora depth = ext_depth(inode); 239456055d3aSAmit Arora eh = path[depth].p_hdr; 239556055d3aSAmit Arora ex = path[depth].p_ext; 239656055d3aSAmit Arora ee_block = le32_to_cpu(ex->ee_block); 239756055d3aSAmit Arora ee_len = ext4_ext_get_actual_len(ex); 239856055d3aSAmit Arora allocated = ee_len - (iblock - ee_block); 239956055d3aSAmit Arora newblock = iblock - ee_block + ext_pblock(ex); 240056055d3aSAmit Arora ex2 = ex; 240195c3889cSAneesh Kumar K.V orig_ex.ee_block = ex->ee_block; 240295c3889cSAneesh Kumar K.V orig_ex.ee_len = cpu_to_le16(ee_len); 240395c3889cSAneesh Kumar K.V ext4_ext_store_pblock(&orig_ex, ext_pblock(ex)); 240456055d3aSAmit Arora 24059df5643aSAneesh Kumar K.V err = ext4_ext_get_access(handle, inode, path + depth); 24069df5643aSAneesh Kumar K.V if (err) 24079df5643aSAneesh Kumar K.V goto out; 24083977c965SAneesh Kumar K.V /* If extent has less than 2*EXT4_EXT_ZERO_LEN zerout directly */ 24093977c965SAneesh Kumar K.V if (ee_len <= 2*EXT4_EXT_ZERO_LEN) { 24103977c965SAneesh Kumar K.V err = ext4_ext_zeroout(inode, &orig_ex); 24113977c965SAneesh Kumar K.V if (err) 24123977c965SAneesh Kumar K.V goto fix_extent_len; 24133977c965SAneesh Kumar K.V /* update the extent length and mark as initialized */ 24143977c965SAneesh Kumar K.V ex->ee_block = orig_ex.ee_block; 24153977c965SAneesh Kumar K.V ex->ee_len = orig_ex.ee_len; 24163977c965SAneesh Kumar K.V ext4_ext_store_pblock(ex, ext_pblock(&orig_ex)); 24173977c965SAneesh Kumar K.V ext4_ext_dirty(handle, inode, path + depth); 2418161e7b7cSAneesh Kumar K.V /* zeroed the full extent */ 2419161e7b7cSAneesh Kumar K.V return allocated; 24203977c965SAneesh Kumar K.V } 24219df5643aSAneesh Kumar K.V 242256055d3aSAmit Arora /* ex1: ee_block to iblock - 1 : uninitialized */ 242356055d3aSAmit Arora if (iblock > ee_block) { 242456055d3aSAmit Arora ex1 = ex; 242556055d3aSAmit Arora ex1->ee_len = cpu_to_le16(iblock - ee_block); 242656055d3aSAmit Arora ext4_ext_mark_uninitialized(ex1); 242756055d3aSAmit Arora ex2 = &newex; 242856055d3aSAmit Arora } 242956055d3aSAmit Arora /* 243056055d3aSAmit Arora * for sanity, update the length of the ex2 extent before 243156055d3aSAmit Arora * we insert ex3, if ex1 is NULL. This is to avoid temporary 243256055d3aSAmit Arora * overlap of blocks. 243356055d3aSAmit Arora */ 243456055d3aSAmit Arora if (!ex1 && allocated > max_blocks) 243556055d3aSAmit Arora ex2->ee_len = cpu_to_le16(max_blocks); 243656055d3aSAmit Arora /* ex3: to ee_block + ee_len : uninitialised */ 243756055d3aSAmit Arora if (allocated > max_blocks) { 243856055d3aSAmit Arora unsigned int newdepth; 24393977c965SAneesh Kumar K.V /* If extent has less than EXT4_EXT_ZERO_LEN zerout directly */ 24403977c965SAneesh Kumar K.V if (allocated <= EXT4_EXT_ZERO_LEN) { 2441d03856bdSAneesh Kumar K.V /* 2442d03856bdSAneesh Kumar K.V * iblock == ee_block is handled by the zerouout 2443d03856bdSAneesh Kumar K.V * at the beginning. 2444d03856bdSAneesh Kumar K.V * Mark first half uninitialized. 24453977c965SAneesh Kumar K.V * Mark second half initialized and zero out the 24463977c965SAneesh Kumar K.V * initialized extent 24473977c965SAneesh Kumar K.V */ 24483977c965SAneesh Kumar K.V ex->ee_block = orig_ex.ee_block; 24493977c965SAneesh Kumar K.V ex->ee_len = cpu_to_le16(ee_len - allocated); 24503977c965SAneesh Kumar K.V ext4_ext_mark_uninitialized(ex); 24513977c965SAneesh Kumar K.V ext4_ext_store_pblock(ex, ext_pblock(&orig_ex)); 24523977c965SAneesh Kumar K.V ext4_ext_dirty(handle, inode, path + depth); 24533977c965SAneesh Kumar K.V 24543977c965SAneesh Kumar K.V ex3 = &newex; 24553977c965SAneesh Kumar K.V ex3->ee_block = cpu_to_le32(iblock); 24563977c965SAneesh Kumar K.V ext4_ext_store_pblock(ex3, newblock); 24573977c965SAneesh Kumar K.V ex3->ee_len = cpu_to_le16(allocated); 24583977c965SAneesh Kumar K.V err = ext4_ext_insert_extent(handle, inode, path, ex3); 24593977c965SAneesh Kumar K.V if (err == -ENOSPC) { 24603977c965SAneesh Kumar K.V err = ext4_ext_zeroout(inode, &orig_ex); 24613977c965SAneesh Kumar K.V if (err) 24623977c965SAneesh Kumar K.V goto fix_extent_len; 24633977c965SAneesh Kumar K.V ex->ee_block = orig_ex.ee_block; 24643977c965SAneesh Kumar K.V ex->ee_len = orig_ex.ee_len; 24653977c965SAneesh Kumar K.V ext4_ext_store_pblock(ex, ext_pblock(&orig_ex)); 24663977c965SAneesh Kumar K.V ext4_ext_dirty(handle, inode, path + depth); 2467d03856bdSAneesh Kumar K.V /* blocks available from iblock */ 2468161e7b7cSAneesh Kumar K.V return allocated; 24693977c965SAneesh Kumar K.V 24703977c965SAneesh Kumar K.V } else if (err) 24713977c965SAneesh Kumar K.V goto fix_extent_len; 24723977c965SAneesh Kumar K.V 2473161e7b7cSAneesh Kumar K.V /* 2474161e7b7cSAneesh Kumar K.V * We need to zero out the second half because 2475161e7b7cSAneesh Kumar K.V * an fallocate request can update file size and 2476161e7b7cSAneesh Kumar K.V * converting the second half to initialized extent 2477161e7b7cSAneesh Kumar K.V * implies that we can leak some junk data to user 2478161e7b7cSAneesh Kumar K.V * space. 2479161e7b7cSAneesh Kumar K.V */ 2480161e7b7cSAneesh Kumar K.V err = ext4_ext_zeroout(inode, ex3); 2481161e7b7cSAneesh Kumar K.V if (err) { 2482161e7b7cSAneesh Kumar K.V /* 2483161e7b7cSAneesh Kumar K.V * We should actually mark the 2484161e7b7cSAneesh Kumar K.V * second half as uninit and return error 2485161e7b7cSAneesh Kumar K.V * Insert would have changed the extent 2486161e7b7cSAneesh Kumar K.V */ 2487161e7b7cSAneesh Kumar K.V depth = ext_depth(inode); 2488161e7b7cSAneesh Kumar K.V ext4_ext_drop_refs(path); 2489161e7b7cSAneesh Kumar K.V path = ext4_ext_find_extent(inode, 2490161e7b7cSAneesh Kumar K.V iblock, path); 2491161e7b7cSAneesh Kumar K.V if (IS_ERR(path)) { 2492161e7b7cSAneesh Kumar K.V err = PTR_ERR(path); 2493161e7b7cSAneesh Kumar K.V return err; 2494161e7b7cSAneesh Kumar K.V } 2495d03856bdSAneesh Kumar K.V /* get the second half extent details */ 2496161e7b7cSAneesh Kumar K.V ex = path[depth].p_ext; 2497161e7b7cSAneesh Kumar K.V err = ext4_ext_get_access(handle, inode, 2498161e7b7cSAneesh Kumar K.V path + depth); 2499161e7b7cSAneesh Kumar K.V if (err) 2500161e7b7cSAneesh Kumar K.V return err; 2501161e7b7cSAneesh Kumar K.V ext4_ext_mark_uninitialized(ex); 2502161e7b7cSAneesh Kumar K.V ext4_ext_dirty(handle, inode, path + depth); 2503161e7b7cSAneesh Kumar K.V return err; 2504161e7b7cSAneesh Kumar K.V } 2505161e7b7cSAneesh Kumar K.V 2506161e7b7cSAneesh Kumar K.V /* zeroed the second half */ 25073977c965SAneesh Kumar K.V return allocated; 25083977c965SAneesh Kumar K.V } 250956055d3aSAmit Arora ex3 = &newex; 251056055d3aSAmit Arora ex3->ee_block = cpu_to_le32(iblock + max_blocks); 251156055d3aSAmit Arora ext4_ext_store_pblock(ex3, newblock + max_blocks); 251256055d3aSAmit Arora ex3->ee_len = cpu_to_le16(allocated - max_blocks); 251356055d3aSAmit Arora ext4_ext_mark_uninitialized(ex3); 251456055d3aSAmit Arora err = ext4_ext_insert_extent(handle, inode, path, ex3); 2515093a088bSAneesh Kumar K.V if (err == -ENOSPC) { 2516093a088bSAneesh Kumar K.V err = ext4_ext_zeroout(inode, &orig_ex); 2517093a088bSAneesh Kumar K.V if (err) 2518093a088bSAneesh Kumar K.V goto fix_extent_len; 2519093a088bSAneesh Kumar K.V /* update the extent length and mark as initialized */ 252095c3889cSAneesh Kumar K.V ex->ee_block = orig_ex.ee_block; 252195c3889cSAneesh Kumar K.V ex->ee_len = orig_ex.ee_len; 252295c3889cSAneesh Kumar K.V ext4_ext_store_pblock(ex, ext_pblock(&orig_ex)); 252395c3889cSAneesh Kumar K.V ext4_ext_dirty(handle, inode, path + depth); 2524161e7b7cSAneesh Kumar K.V /* zeroed the full extent */ 2525d03856bdSAneesh Kumar K.V /* blocks available from iblock */ 2526161e7b7cSAneesh Kumar K.V return allocated; 2527093a088bSAneesh Kumar K.V 2528093a088bSAneesh Kumar K.V } else if (err) 2529093a088bSAneesh Kumar K.V goto fix_extent_len; 253056055d3aSAmit Arora /* 253156055d3aSAmit Arora * The depth, and hence eh & ex might change 253256055d3aSAmit Arora * as part of the insert above. 253356055d3aSAmit Arora */ 253456055d3aSAmit Arora newdepth = ext_depth(inode); 253595c3889cSAneesh Kumar K.V /* 253695c3889cSAneesh Kumar K.V * update the extent length after successfull insert of the 253795c3889cSAneesh Kumar K.V * split extent 253895c3889cSAneesh Kumar K.V */ 253995c3889cSAneesh Kumar K.V orig_ex.ee_len = cpu_to_le16(ee_len - 254095c3889cSAneesh Kumar K.V ext4_ext_get_actual_len(ex3)); 254156055d3aSAmit Arora depth = newdepth; 2542b35905c1SAneesh Kumar K.V ext4_ext_drop_refs(path); 2543b35905c1SAneesh Kumar K.V path = ext4_ext_find_extent(inode, iblock, path); 254456055d3aSAmit Arora if (IS_ERR(path)) { 254556055d3aSAmit Arora err = PTR_ERR(path); 254656055d3aSAmit Arora goto out; 254756055d3aSAmit Arora } 254856055d3aSAmit Arora eh = path[depth].p_hdr; 254956055d3aSAmit Arora ex = path[depth].p_ext; 255056055d3aSAmit Arora if (ex2 != &newex) 255156055d3aSAmit Arora ex2 = ex; 25529df5643aSAneesh Kumar K.V 25539df5643aSAneesh Kumar K.V err = ext4_ext_get_access(handle, inode, path + depth); 25549df5643aSAneesh Kumar K.V if (err) 25559df5643aSAneesh Kumar K.V goto out; 2556d03856bdSAneesh Kumar K.V 255756055d3aSAmit Arora allocated = max_blocks; 25583977c965SAneesh Kumar K.V 25593977c965SAneesh Kumar K.V /* If extent has less than EXT4_EXT_ZERO_LEN and we are trying 25603977c965SAneesh Kumar K.V * to insert a extent in the middle zerout directly 25613977c965SAneesh Kumar K.V * otherwise give the extent a chance to merge to left 25623977c965SAneesh Kumar K.V */ 25633977c965SAneesh Kumar K.V if (le16_to_cpu(orig_ex.ee_len) <= EXT4_EXT_ZERO_LEN && 25643977c965SAneesh Kumar K.V iblock != ee_block) { 25653977c965SAneesh Kumar K.V err = ext4_ext_zeroout(inode, &orig_ex); 25663977c965SAneesh Kumar K.V if (err) 25673977c965SAneesh Kumar K.V goto fix_extent_len; 25683977c965SAneesh Kumar K.V /* update the extent length and mark as initialized */ 25693977c965SAneesh Kumar K.V ex->ee_block = orig_ex.ee_block; 25703977c965SAneesh Kumar K.V ex->ee_len = orig_ex.ee_len; 25713977c965SAneesh Kumar K.V ext4_ext_store_pblock(ex, ext_pblock(&orig_ex)); 25723977c965SAneesh Kumar K.V ext4_ext_dirty(handle, inode, path + depth); 2573161e7b7cSAneesh Kumar K.V /* zero out the first half */ 2574d03856bdSAneesh Kumar K.V /* blocks available from iblock */ 2575161e7b7cSAneesh Kumar K.V return allocated; 25763977c965SAneesh Kumar K.V } 257756055d3aSAmit Arora } 257856055d3aSAmit Arora /* 257956055d3aSAmit Arora * If there was a change of depth as part of the 258056055d3aSAmit Arora * insertion of ex3 above, we need to update the length 258156055d3aSAmit Arora * of the ex1 extent again here 258256055d3aSAmit Arora */ 258356055d3aSAmit Arora if (ex1 && ex1 != ex) { 258456055d3aSAmit Arora ex1 = ex; 258556055d3aSAmit Arora ex1->ee_len = cpu_to_le16(iblock - ee_block); 258656055d3aSAmit Arora ext4_ext_mark_uninitialized(ex1); 258756055d3aSAmit Arora ex2 = &newex; 258856055d3aSAmit Arora } 258956055d3aSAmit Arora /* ex2: iblock to iblock + maxblocks-1 : initialised */ 259056055d3aSAmit Arora ex2->ee_block = cpu_to_le32(iblock); 259156055d3aSAmit Arora ext4_ext_store_pblock(ex2, newblock); 259256055d3aSAmit Arora ex2->ee_len = cpu_to_le16(allocated); 259356055d3aSAmit Arora if (ex2 != ex) 259456055d3aSAmit Arora goto insert; 259556055d3aSAmit Arora /* 259656055d3aSAmit Arora * New (initialized) extent starts from the first block 259756055d3aSAmit Arora * in the current extent. i.e., ex2 == ex 259856055d3aSAmit Arora * We have to see if it can be merged with the extent 259956055d3aSAmit Arora * on the left. 260056055d3aSAmit Arora */ 260156055d3aSAmit Arora if (ex2 > EXT_FIRST_EXTENT(eh)) { 260256055d3aSAmit Arora /* 260356055d3aSAmit Arora * To merge left, pass "ex2 - 1" to try_to_merge(), 260456055d3aSAmit Arora * since it merges towards right _only_. 260556055d3aSAmit Arora */ 260656055d3aSAmit Arora ret = ext4_ext_try_to_merge(inode, path, ex2 - 1); 260756055d3aSAmit Arora if (ret) { 260856055d3aSAmit Arora err = ext4_ext_correct_indexes(handle, inode, path); 260956055d3aSAmit Arora if (err) 261056055d3aSAmit Arora goto out; 261156055d3aSAmit Arora depth = ext_depth(inode); 261256055d3aSAmit Arora ex2--; 261356055d3aSAmit Arora } 261456055d3aSAmit Arora } 261556055d3aSAmit Arora /* 261656055d3aSAmit Arora * Try to Merge towards right. This might be required 261756055d3aSAmit Arora * only when the whole extent is being written to. 261856055d3aSAmit Arora * i.e. ex2 == ex and ex3 == NULL. 261956055d3aSAmit Arora */ 262056055d3aSAmit Arora if (!ex3) { 262156055d3aSAmit Arora ret = ext4_ext_try_to_merge(inode, path, ex2); 262256055d3aSAmit Arora if (ret) { 262356055d3aSAmit Arora err = ext4_ext_correct_indexes(handle, inode, path); 262456055d3aSAmit Arora if (err) 262556055d3aSAmit Arora goto out; 262656055d3aSAmit Arora } 262756055d3aSAmit Arora } 262856055d3aSAmit Arora /* Mark modified extent as dirty */ 262956055d3aSAmit Arora err = ext4_ext_dirty(handle, inode, path + depth); 263056055d3aSAmit Arora goto out; 263156055d3aSAmit Arora insert: 263256055d3aSAmit Arora err = ext4_ext_insert_extent(handle, inode, path, &newex); 2633093a088bSAneesh Kumar K.V if (err == -ENOSPC) { 2634093a088bSAneesh Kumar K.V err = ext4_ext_zeroout(inode, &orig_ex); 2635093a088bSAneesh Kumar K.V if (err) 2636093a088bSAneesh Kumar K.V goto fix_extent_len; 2637093a088bSAneesh Kumar K.V /* update the extent length and mark as initialized */ 2638093a088bSAneesh Kumar K.V ex->ee_block = orig_ex.ee_block; 2639093a088bSAneesh Kumar K.V ex->ee_len = orig_ex.ee_len; 2640093a088bSAneesh Kumar K.V ext4_ext_store_pblock(ex, ext_pblock(&orig_ex)); 2641093a088bSAneesh Kumar K.V ext4_ext_dirty(handle, inode, path + depth); 2642161e7b7cSAneesh Kumar K.V /* zero out the first half */ 2643161e7b7cSAneesh Kumar K.V return allocated; 2644093a088bSAneesh Kumar K.V } else if (err) 2645093a088bSAneesh Kumar K.V goto fix_extent_len; 2646093a088bSAneesh Kumar K.V out: 2647093a088bSAneesh Kumar K.V return err ? err : allocated; 2648093a088bSAneesh Kumar K.V 2649093a088bSAneesh Kumar K.V fix_extent_len: 265095c3889cSAneesh Kumar K.V ex->ee_block = orig_ex.ee_block; 265195c3889cSAneesh Kumar K.V ex->ee_len = orig_ex.ee_len; 265295c3889cSAneesh Kumar K.V ext4_ext_store_pblock(ex, ext_pblock(&orig_ex)); 265395c3889cSAneesh Kumar K.V ext4_ext_mark_uninitialized(ex); 265495c3889cSAneesh Kumar K.V ext4_ext_dirty(handle, inode, path + depth); 2655093a088bSAneesh Kumar K.V return err; 265656055d3aSAmit Arora } 265756055d3aSAmit Arora 2658c278bfecSAneesh Kumar K.V /* 2659f5ab0d1fSMingming Cao * Block allocation/map/preallocation routine for extents based files 2660f5ab0d1fSMingming Cao * 2661f5ab0d1fSMingming Cao * 2662c278bfecSAneesh Kumar K.V * Need to be called with 26630e855ac8SAneesh Kumar K.V * down_read(&EXT4_I(inode)->i_data_sem) if not allocating file system block 26640e855ac8SAneesh Kumar K.V * (ie, create is zero). Otherwise down_write(&EXT4_I(inode)->i_data_sem) 2665f5ab0d1fSMingming Cao * 2666f5ab0d1fSMingming Cao * return > 0, number of of blocks already mapped/allocated 2667f5ab0d1fSMingming Cao * if create == 0 and these are pre-allocated blocks 2668f5ab0d1fSMingming Cao * buffer head is unmapped 2669f5ab0d1fSMingming Cao * otherwise blocks are mapped 2670f5ab0d1fSMingming Cao * 2671f5ab0d1fSMingming Cao * return = 0, if plain look up failed (blocks have not been allocated) 2672f5ab0d1fSMingming Cao * buffer head is unmapped 2673f5ab0d1fSMingming Cao * 2674f5ab0d1fSMingming Cao * return < 0, error case. 2675c278bfecSAneesh Kumar K.V */ 2676f65e6fbaSAlex Tomas int ext4_ext_get_blocks(handle_t *handle, struct inode *inode, 2677725d26d3SAneesh Kumar K.V ext4_lblk_t iblock, 2678*498e5f24STheodore Ts'o unsigned int max_blocks, struct buffer_head *bh_result, 2679a86c6181SAlex Tomas int create, int extend_disksize) 2680a86c6181SAlex Tomas { 2681a86c6181SAlex Tomas struct ext4_ext_path *path = NULL; 268256055d3aSAmit Arora struct ext4_extent_header *eh; 2683a86c6181SAlex Tomas struct ext4_extent newex, *ex; 2684*498e5f24STheodore Ts'o ext4_fsblk_t newblock; 2685*498e5f24STheodore Ts'o int err = 0, depth, ret, cache_type; 2686*498e5f24STheodore Ts'o unsigned int allocated = 0; 2687c9de560dSAlex Tomas struct ext4_allocation_request ar; 268861628a3fSMingming Cao loff_t disksize; 2689a86c6181SAlex Tomas 2690a86c6181SAlex Tomas __clear_bit(BH_New, &bh_result->b_state); 2691*498e5f24STheodore Ts'o ext_debug("blocks %u/%u requested for inode %u\n", 2692bba90743SEric Sandeen iblock, max_blocks, inode->i_ino); 2693a86c6181SAlex Tomas 2694a86c6181SAlex Tomas /* check in cache */ 2695*498e5f24STheodore Ts'o cache_type = ext4_ext_in_cache(inode, iblock, &newex); 2696*498e5f24STheodore Ts'o if (cache_type) { 2697*498e5f24STheodore Ts'o if (cache_type == EXT4_EXT_CACHE_GAP) { 2698a86c6181SAlex Tomas if (!create) { 269956055d3aSAmit Arora /* 270056055d3aSAmit Arora * block isn't allocated yet and 270156055d3aSAmit Arora * user doesn't want to allocate it 270256055d3aSAmit Arora */ 2703a86c6181SAlex Tomas goto out2; 2704a86c6181SAlex Tomas } 2705a86c6181SAlex Tomas /* we should allocate requested block */ 2706*498e5f24STheodore Ts'o } else if (cache_type == EXT4_EXT_CACHE_EXTENT) { 2707a86c6181SAlex Tomas /* block is already allocated */ 2708a86c6181SAlex Tomas newblock = iblock 2709a86c6181SAlex Tomas - le32_to_cpu(newex.ee_block) 2710f65e6fbaSAlex Tomas + ext_pblock(&newex); 2711d0d856e8SRandy Dunlap /* number of remaining blocks in the extent */ 2712b939e376SAneesh Kumar K.V allocated = ext4_ext_get_actual_len(&newex) - 2713a86c6181SAlex Tomas (iblock - le32_to_cpu(newex.ee_block)); 2714a86c6181SAlex Tomas goto out; 2715a86c6181SAlex Tomas } else { 2716a86c6181SAlex Tomas BUG(); 2717a86c6181SAlex Tomas } 2718a86c6181SAlex Tomas } 2719a86c6181SAlex Tomas 2720a86c6181SAlex Tomas /* find extent for this block */ 2721a86c6181SAlex Tomas path = ext4_ext_find_extent(inode, iblock, NULL); 2722a86c6181SAlex Tomas if (IS_ERR(path)) { 2723a86c6181SAlex Tomas err = PTR_ERR(path); 2724a86c6181SAlex Tomas path = NULL; 2725a86c6181SAlex Tomas goto out2; 2726a86c6181SAlex Tomas } 2727a86c6181SAlex Tomas 2728a86c6181SAlex Tomas depth = ext_depth(inode); 2729a86c6181SAlex Tomas 2730a86c6181SAlex Tomas /* 2731d0d856e8SRandy Dunlap * consistent leaf must not be empty; 2732d0d856e8SRandy Dunlap * this situation is possible, though, _during_ tree modification; 2733a86c6181SAlex Tomas * this is why assert can't be put in ext4_ext_find_extent() 2734a86c6181SAlex Tomas */ 2735a86c6181SAlex Tomas BUG_ON(path[depth].p_ext == NULL && depth != 0); 273656055d3aSAmit Arora eh = path[depth].p_hdr; 2737a86c6181SAlex Tomas 27387e028976SAvantika Mathur ex = path[depth].p_ext; 27397e028976SAvantika Mathur if (ex) { 2740725d26d3SAneesh Kumar K.V ext4_lblk_t ee_block = le32_to_cpu(ex->ee_block); 2741f65e6fbaSAlex Tomas ext4_fsblk_t ee_start = ext_pblock(ex); 2742a2df2a63SAmit Arora unsigned short ee_len; 2743471d4011SSuparna Bhattacharya 2744471d4011SSuparna Bhattacharya /* 2745471d4011SSuparna Bhattacharya * Uninitialized extents are treated as holes, except that 274656055d3aSAmit Arora * we split out initialized portions during a write. 2747471d4011SSuparna Bhattacharya */ 2748a2df2a63SAmit Arora ee_len = ext4_ext_get_actual_len(ex); 2749d0d856e8SRandy Dunlap /* if found extent covers block, simply return it */ 2750a86c6181SAlex Tomas if (iblock >= ee_block && iblock < ee_block + ee_len) { 2751a86c6181SAlex Tomas newblock = iblock - ee_block + ee_start; 2752d0d856e8SRandy Dunlap /* number of remaining blocks in the extent */ 2753a86c6181SAlex Tomas allocated = ee_len - (iblock - ee_block); 2754bba90743SEric Sandeen ext_debug("%u fit into %lu:%d -> %llu\n", iblock, 2755a86c6181SAlex Tomas ee_block, ee_len, newblock); 275656055d3aSAmit Arora 2757a2df2a63SAmit Arora /* Do not put uninitialized extent in the cache */ 275856055d3aSAmit Arora if (!ext4_ext_is_uninitialized(ex)) { 2759a2df2a63SAmit Arora ext4_ext_put_in_cache(inode, ee_block, 2760a2df2a63SAmit Arora ee_len, ee_start, 2761a2df2a63SAmit Arora EXT4_EXT_CACHE_EXTENT); 2762a86c6181SAlex Tomas goto out; 2763a86c6181SAlex Tomas } 276456055d3aSAmit Arora if (create == EXT4_CREATE_UNINITIALIZED_EXT) 276556055d3aSAmit Arora goto out; 2766e067ba00SAneesh Kumar K.V if (!create) { 2767e067ba00SAneesh Kumar K.V /* 2768e067ba00SAneesh Kumar K.V * We have blocks reserved already. We 2769e067ba00SAneesh Kumar K.V * return allocated blocks so that delalloc 2770e067ba00SAneesh Kumar K.V * won't do block reservation for us. But 2771e067ba00SAneesh Kumar K.V * the buffer head will be unmapped so that 2772e067ba00SAneesh Kumar K.V * a read from the block returns 0s. 2773e067ba00SAneesh Kumar K.V */ 2774e067ba00SAneesh Kumar K.V if (allocated > max_blocks) 2775e067ba00SAneesh Kumar K.V allocated = max_blocks; 2776953e622bSEric Sandeen set_buffer_unwritten(bh_result); 277756055d3aSAmit Arora goto out2; 2778e067ba00SAneesh Kumar K.V } 277956055d3aSAmit Arora 278056055d3aSAmit Arora ret = ext4_ext_convert_to_initialized(handle, inode, 278156055d3aSAmit Arora path, iblock, 278256055d3aSAmit Arora max_blocks); 2783dbf9d7daSDmitry Monakhov if (ret <= 0) { 2784dbf9d7daSDmitry Monakhov err = ret; 278556055d3aSAmit Arora goto out2; 2786dbf9d7daSDmitry Monakhov } else 278756055d3aSAmit Arora allocated = ret; 278856055d3aSAmit Arora goto outnew; 278956055d3aSAmit Arora } 2790a86c6181SAlex Tomas } 2791a86c6181SAlex Tomas 2792a86c6181SAlex Tomas /* 2793d0d856e8SRandy Dunlap * requested block isn't allocated yet; 2794a86c6181SAlex Tomas * we couldn't try to create block if create flag is zero 2795a86c6181SAlex Tomas */ 2796a86c6181SAlex Tomas if (!create) { 279756055d3aSAmit Arora /* 279856055d3aSAmit Arora * put just found gap into cache to speed up 279956055d3aSAmit Arora * subsequent requests 280056055d3aSAmit Arora */ 2801a86c6181SAlex Tomas ext4_ext_put_gap_in_cache(inode, path, iblock); 2802a86c6181SAlex Tomas goto out2; 2803a86c6181SAlex Tomas } 2804a86c6181SAlex Tomas /* 2805c2ea3fdeSTheodore Ts'o * Okay, we need to do block allocation. 2806a86c6181SAlex Tomas */ 2807a86c6181SAlex Tomas 2808c9de560dSAlex Tomas /* find neighbour allocated blocks */ 2809c9de560dSAlex Tomas ar.lleft = iblock; 2810c9de560dSAlex Tomas err = ext4_ext_search_left(inode, path, &ar.lleft, &ar.pleft); 2811c9de560dSAlex Tomas if (err) 2812c9de560dSAlex Tomas goto out2; 2813c9de560dSAlex Tomas ar.lright = iblock; 2814c9de560dSAlex Tomas err = ext4_ext_search_right(inode, path, &ar.lright, &ar.pright); 2815c9de560dSAlex Tomas if (err) 2816c9de560dSAlex Tomas goto out2; 281725d14f98SAmit Arora 2818749269faSAmit Arora /* 2819749269faSAmit Arora * See if request is beyond maximum number of blocks we can have in 2820749269faSAmit Arora * a single extent. For an initialized extent this limit is 2821749269faSAmit Arora * EXT_INIT_MAX_LEN and for an uninitialized extent this limit is 2822749269faSAmit Arora * EXT_UNINIT_MAX_LEN. 2823749269faSAmit Arora */ 2824749269faSAmit Arora if (max_blocks > EXT_INIT_MAX_LEN && 2825749269faSAmit Arora create != EXT4_CREATE_UNINITIALIZED_EXT) 2826749269faSAmit Arora max_blocks = EXT_INIT_MAX_LEN; 2827749269faSAmit Arora else if (max_blocks > EXT_UNINIT_MAX_LEN && 2828749269faSAmit Arora create == EXT4_CREATE_UNINITIALIZED_EXT) 2829749269faSAmit Arora max_blocks = EXT_UNINIT_MAX_LEN; 2830749269faSAmit Arora 283125d14f98SAmit Arora /* Check if we can really insert (iblock)::(iblock+max_blocks) extent */ 283225d14f98SAmit Arora newex.ee_block = cpu_to_le32(iblock); 283325d14f98SAmit Arora newex.ee_len = cpu_to_le16(max_blocks); 283425d14f98SAmit Arora err = ext4_ext_check_overlap(inode, &newex, path); 283525d14f98SAmit Arora if (err) 2836b939e376SAneesh Kumar K.V allocated = ext4_ext_get_actual_len(&newex); 283725d14f98SAmit Arora else 2838a86c6181SAlex Tomas allocated = max_blocks; 2839c9de560dSAlex Tomas 2840c9de560dSAlex Tomas /* allocate new block */ 2841c9de560dSAlex Tomas ar.inode = inode; 2842c9de560dSAlex Tomas ar.goal = ext4_ext_find_goal(inode, path, iblock); 2843c9de560dSAlex Tomas ar.logical = iblock; 2844c9de560dSAlex Tomas ar.len = allocated; 2845c9de560dSAlex Tomas if (S_ISREG(inode->i_mode)) 2846c9de560dSAlex Tomas ar.flags = EXT4_MB_HINT_DATA; 2847c9de560dSAlex Tomas else 2848c9de560dSAlex Tomas /* disable in-core preallocation for non-regular files */ 2849c9de560dSAlex Tomas ar.flags = 0; 2850c9de560dSAlex Tomas newblock = ext4_mb_new_blocks(handle, &ar, &err); 2851a86c6181SAlex Tomas if (!newblock) 2852a86c6181SAlex Tomas goto out2; 28532ae02107SMingming Cao ext_debug("allocate new block: goal %llu, found %llu/%lu\n", 2854*498e5f24STheodore Ts'o ar.goal, newblock, allocated); 2855a86c6181SAlex Tomas 2856a86c6181SAlex Tomas /* try to insert new extent into found leaf and return */ 2857f65e6fbaSAlex Tomas ext4_ext_store_pblock(&newex, newblock); 2858c9de560dSAlex Tomas newex.ee_len = cpu_to_le16(ar.len); 2859a2df2a63SAmit Arora if (create == EXT4_CREATE_UNINITIALIZED_EXT) /* Mark uninitialized */ 2860a2df2a63SAmit Arora ext4_ext_mark_uninitialized(&newex); 2861a86c6181SAlex Tomas err = ext4_ext_insert_extent(handle, inode, path, &newex); 2862315054f0SAlex Tomas if (err) { 2863315054f0SAlex Tomas /* free data blocks we just allocated */ 2864c9de560dSAlex Tomas /* not a good idea to call discard here directly, 2865c9de560dSAlex Tomas * but otherwise we'd need to call it every free() */ 2866c2ea3fdeSTheodore Ts'o ext4_discard_preallocations(inode); 2867315054f0SAlex Tomas ext4_free_blocks(handle, inode, ext_pblock(&newex), 2868b939e376SAneesh Kumar K.V ext4_ext_get_actual_len(&newex), 0); 2869a86c6181SAlex Tomas goto out2; 2870315054f0SAlex Tomas } 2871a86c6181SAlex Tomas 2872a86c6181SAlex Tomas /* previous routine could use block we allocated */ 2873f65e6fbaSAlex Tomas newblock = ext_pblock(&newex); 2874b939e376SAneesh Kumar K.V allocated = ext4_ext_get_actual_len(&newex); 287556055d3aSAmit Arora outnew: 287661628a3fSMingming Cao if (extend_disksize) { 287761628a3fSMingming Cao disksize = ((loff_t) iblock + ar.len) << inode->i_blkbits; 287861628a3fSMingming Cao if (disksize > i_size_read(inode)) 287961628a3fSMingming Cao disksize = i_size_read(inode); 288061628a3fSMingming Cao if (disksize > EXT4_I(inode)->i_disksize) 288161628a3fSMingming Cao EXT4_I(inode)->i_disksize = disksize; 288261628a3fSMingming Cao } 2883a379cd1dSAneesh Kumar K.V 2884953e622bSEric Sandeen set_buffer_new(bh_result); 2885a86c6181SAlex Tomas 2886a2df2a63SAmit Arora /* Cache only when it is _not_ an uninitialized extent */ 2887a2df2a63SAmit Arora if (create != EXT4_CREATE_UNINITIALIZED_EXT) 2888a86c6181SAlex Tomas ext4_ext_put_in_cache(inode, iblock, allocated, newblock, 2889a86c6181SAlex Tomas EXT4_EXT_CACHE_EXTENT); 2890a86c6181SAlex Tomas out: 2891a86c6181SAlex Tomas if (allocated > max_blocks) 2892a86c6181SAlex Tomas allocated = max_blocks; 2893a86c6181SAlex Tomas ext4_ext_show_leaf(inode, path); 2894953e622bSEric Sandeen set_buffer_mapped(bh_result); 2895a86c6181SAlex Tomas bh_result->b_bdev = inode->i_sb->s_bdev; 2896a86c6181SAlex Tomas bh_result->b_blocknr = newblock; 2897a86c6181SAlex Tomas out2: 2898a86c6181SAlex Tomas if (path) { 2899a86c6181SAlex Tomas ext4_ext_drop_refs(path); 2900a86c6181SAlex Tomas kfree(path); 2901a86c6181SAlex Tomas } 2902a86c6181SAlex Tomas return err ? err : allocated; 2903a86c6181SAlex Tomas } 2904a86c6181SAlex Tomas 2905cf108bcaSJan Kara void ext4_ext_truncate(struct inode *inode) 2906a86c6181SAlex Tomas { 2907a86c6181SAlex Tomas struct address_space *mapping = inode->i_mapping; 2908a86c6181SAlex Tomas struct super_block *sb = inode->i_sb; 2909725d26d3SAneesh Kumar K.V ext4_lblk_t last_block; 2910a86c6181SAlex Tomas handle_t *handle; 2911a86c6181SAlex Tomas int err = 0; 2912a86c6181SAlex Tomas 2913a86c6181SAlex Tomas /* 2914a86c6181SAlex Tomas * probably first extent we're gonna free will be last in block 2915a86c6181SAlex Tomas */ 2916f3bd1f3fSMingming Cao err = ext4_writepage_trans_blocks(inode); 2917a86c6181SAlex Tomas handle = ext4_journal_start(inode, err); 2918cf108bcaSJan Kara if (IS_ERR(handle)) 2919a86c6181SAlex Tomas return; 2920a86c6181SAlex Tomas 2921cf108bcaSJan Kara if (inode->i_size & (sb->s_blocksize - 1)) 2922cf108bcaSJan Kara ext4_block_truncate_page(handle, mapping, inode->i_size); 2923a86c6181SAlex Tomas 29249ddfc3dcSJan Kara if (ext4_orphan_add(handle, inode)) 29259ddfc3dcSJan Kara goto out_stop; 29269ddfc3dcSJan Kara 29270e855ac8SAneesh Kumar K.V down_write(&EXT4_I(inode)->i_data_sem); 2928a86c6181SAlex Tomas ext4_ext_invalidate_cache(inode); 2929a86c6181SAlex Tomas 2930c2ea3fdeSTheodore Ts'o ext4_discard_preallocations(inode); 2931c9de560dSAlex Tomas 2932a86c6181SAlex Tomas /* 2933d0d856e8SRandy Dunlap * TODO: optimization is possible here. 2934d0d856e8SRandy Dunlap * Probably we need not scan at all, 2935d0d856e8SRandy Dunlap * because page truncation is enough. 2936a86c6181SAlex Tomas */ 2937a86c6181SAlex Tomas 2938a86c6181SAlex Tomas /* we have to know where to truncate from in crash case */ 2939a86c6181SAlex Tomas EXT4_I(inode)->i_disksize = inode->i_size; 2940a86c6181SAlex Tomas ext4_mark_inode_dirty(handle, inode); 2941a86c6181SAlex Tomas 2942a86c6181SAlex Tomas last_block = (inode->i_size + sb->s_blocksize - 1) 2943a86c6181SAlex Tomas >> EXT4_BLOCK_SIZE_BITS(sb); 2944a86c6181SAlex Tomas err = ext4_ext_remove_space(inode, last_block); 2945a86c6181SAlex Tomas 2946a86c6181SAlex Tomas /* In a multi-transaction truncate, we only make the final 294756055d3aSAmit Arora * transaction synchronous. 294856055d3aSAmit Arora */ 2949a86c6181SAlex Tomas if (IS_SYNC(inode)) 29500390131bSFrank Mayhar ext4_handle_sync(handle); 2951a86c6181SAlex Tomas 2952a86c6181SAlex Tomas out_stop: 29539ddfc3dcSJan Kara up_write(&EXT4_I(inode)->i_data_sem); 2954a86c6181SAlex Tomas /* 2955d0d856e8SRandy Dunlap * If this was a simple ftruncate() and the file will remain alive, 2956a86c6181SAlex Tomas * then we need to clear up the orphan record which we created above. 2957a86c6181SAlex Tomas * However, if this was a real unlink then we were called by 2958a86c6181SAlex Tomas * ext4_delete_inode(), and we allow that function to clean up the 2959a86c6181SAlex Tomas * orphan info for us. 2960a86c6181SAlex Tomas */ 2961a86c6181SAlex Tomas if (inode->i_nlink) 2962a86c6181SAlex Tomas ext4_orphan_del(handle, inode); 2963a86c6181SAlex Tomas 2964ef737728SSolofo Ramangalahy inode->i_mtime = inode->i_ctime = ext4_current_time(inode); 2965ef737728SSolofo Ramangalahy ext4_mark_inode_dirty(handle, inode); 2966a86c6181SAlex Tomas ext4_journal_stop(handle); 2967a86c6181SAlex Tomas } 2968a86c6181SAlex Tomas 2969fd28784aSAneesh Kumar K.V static void ext4_falloc_update_inode(struct inode *inode, 2970fd28784aSAneesh Kumar K.V int mode, loff_t new_size, int update_ctime) 2971fd28784aSAneesh Kumar K.V { 2972fd28784aSAneesh Kumar K.V struct timespec now; 2973fd28784aSAneesh Kumar K.V 2974fd28784aSAneesh Kumar K.V if (update_ctime) { 2975fd28784aSAneesh Kumar K.V now = current_fs_time(inode->i_sb); 2976fd28784aSAneesh Kumar K.V if (!timespec_equal(&inode->i_ctime, &now)) 2977fd28784aSAneesh Kumar K.V inode->i_ctime = now; 2978fd28784aSAneesh Kumar K.V } 2979fd28784aSAneesh Kumar K.V /* 2980fd28784aSAneesh Kumar K.V * Update only when preallocation was requested beyond 2981fd28784aSAneesh Kumar K.V * the file size. 2982fd28784aSAneesh Kumar K.V */ 2983cf17fea6SAneesh Kumar K.V if (!(mode & FALLOC_FL_KEEP_SIZE)) { 2984cf17fea6SAneesh Kumar K.V if (new_size > i_size_read(inode)) 2985fd28784aSAneesh Kumar K.V i_size_write(inode, new_size); 2986cf17fea6SAneesh Kumar K.V if (new_size > EXT4_I(inode)->i_disksize) 2987cf17fea6SAneesh Kumar K.V ext4_update_i_disksize(inode, new_size); 2988fd28784aSAneesh Kumar K.V } 2989fd28784aSAneesh Kumar K.V 2990fd28784aSAneesh Kumar K.V } 2991fd28784aSAneesh Kumar K.V 2992a2df2a63SAmit Arora /* 2993a2df2a63SAmit Arora * preallocate space for a file. This implements ext4's fallocate inode 2994a2df2a63SAmit Arora * operation, which gets called from sys_fallocate system call. 2995a2df2a63SAmit Arora * For block-mapped files, posix_fallocate should fall back to the method 2996a2df2a63SAmit Arora * of writing zeroes to the required new blocks (the same behavior which is 2997a2df2a63SAmit Arora * expected for file systems which do not support fallocate() system call). 2998a2df2a63SAmit Arora */ 2999a2df2a63SAmit Arora long ext4_fallocate(struct inode *inode, int mode, loff_t offset, loff_t len) 3000a2df2a63SAmit Arora { 3001a2df2a63SAmit Arora handle_t *handle; 3002725d26d3SAneesh Kumar K.V ext4_lblk_t block; 3003fd28784aSAneesh Kumar K.V loff_t new_size; 3004*498e5f24STheodore Ts'o unsigned int max_blocks; 3005a2df2a63SAmit Arora int ret = 0; 3006a2df2a63SAmit Arora int ret2 = 0; 3007a2df2a63SAmit Arora int retries = 0; 3008a2df2a63SAmit Arora struct buffer_head map_bh; 3009a2df2a63SAmit Arora unsigned int credits, blkbits = inode->i_blkbits; 3010a2df2a63SAmit Arora 3011a2df2a63SAmit Arora /* 3012a2df2a63SAmit Arora * currently supporting (pre)allocate mode for extent-based 3013a2df2a63SAmit Arora * files _only_ 3014a2df2a63SAmit Arora */ 3015a2df2a63SAmit Arora if (!(EXT4_I(inode)->i_flags & EXT4_EXTENTS_FL)) 3016a2df2a63SAmit Arora return -EOPNOTSUPP; 3017a2df2a63SAmit Arora 3018a2df2a63SAmit Arora /* preallocation to directories is currently not supported */ 3019a2df2a63SAmit Arora if (S_ISDIR(inode->i_mode)) 3020a2df2a63SAmit Arora return -ENODEV; 3021a2df2a63SAmit Arora 3022a2df2a63SAmit Arora block = offset >> blkbits; 3023fd28784aSAneesh Kumar K.V /* 3024fd28784aSAneesh Kumar K.V * We can't just convert len to max_blocks because 3025fd28784aSAneesh Kumar K.V * If blocksize = 4096 offset = 3072 and len = 2048 3026fd28784aSAneesh Kumar K.V */ 3027a2df2a63SAmit Arora max_blocks = (EXT4_BLOCK_ALIGN(len + offset, blkbits) >> blkbits) 3028a2df2a63SAmit Arora - block; 3029a2df2a63SAmit Arora /* 3030f3bd1f3fSMingming Cao * credits to insert 1 extent into extent tree 3031a2df2a63SAmit Arora */ 3032f3bd1f3fSMingming Cao credits = ext4_chunk_trans_blocks(inode, max_blocks); 303355bd725aSAneesh Kumar K.V mutex_lock(&inode->i_mutex); 3034a2df2a63SAmit Arora retry: 3035a2df2a63SAmit Arora while (ret >= 0 && ret < max_blocks) { 3036a2df2a63SAmit Arora block = block + ret; 3037a2df2a63SAmit Arora max_blocks = max_blocks - ret; 3038a2df2a63SAmit Arora handle = ext4_journal_start(inode, credits); 3039a2df2a63SAmit Arora if (IS_ERR(handle)) { 3040a2df2a63SAmit Arora ret = PTR_ERR(handle); 3041a2df2a63SAmit Arora break; 3042a2df2a63SAmit Arora } 304355bd725aSAneesh Kumar K.V ret = ext4_get_blocks_wrap(handle, inode, block, 3044a2df2a63SAmit Arora max_blocks, &map_bh, 3045d2a17637SMingming Cao EXT4_CREATE_UNINITIALIZED_EXT, 0, 0); 3046221879c9SAneesh Kumar K.V if (ret <= 0) { 30472c98615dSAneesh Kumar K.V #ifdef EXT4FS_DEBUG 30482c98615dSAneesh Kumar K.V WARN_ON(ret <= 0); 30492c98615dSAneesh Kumar K.V printk(KERN_ERR "%s: ext4_ext_get_blocks " 30502c98615dSAneesh Kumar K.V "returned error inode#%lu, block=%u, " 30512c98615dSAneesh Kumar K.V "max_blocks=%lu", __func__, 3052bba90743SEric Sandeen inode->i_ino, block, max_blocks); 30532c98615dSAneesh Kumar K.V #endif 3054a2df2a63SAmit Arora ext4_mark_inode_dirty(handle, inode); 3055a2df2a63SAmit Arora ret2 = ext4_journal_stop(handle); 3056a2df2a63SAmit Arora break; 3057a2df2a63SAmit Arora } 3058fd28784aSAneesh Kumar K.V if ((block + ret) >= (EXT4_BLOCK_ALIGN(offset + len, 3059fd28784aSAneesh Kumar K.V blkbits) >> blkbits)) 3060fd28784aSAneesh Kumar K.V new_size = offset + len; 3061fd28784aSAneesh Kumar K.V else 3062fd28784aSAneesh Kumar K.V new_size = (block + ret) << blkbits; 3063a2df2a63SAmit Arora 3064fd28784aSAneesh Kumar K.V ext4_falloc_update_inode(inode, mode, new_size, 3065fd28784aSAneesh Kumar K.V buffer_new(&map_bh)); 3066a2df2a63SAmit Arora ext4_mark_inode_dirty(handle, inode); 3067a2df2a63SAmit Arora ret2 = ext4_journal_stop(handle); 3068a2df2a63SAmit Arora if (ret2) 3069a2df2a63SAmit Arora break; 3070a2df2a63SAmit Arora } 3071fd28784aSAneesh Kumar K.V if (ret == -ENOSPC && 3072fd28784aSAneesh Kumar K.V ext4_should_retry_alloc(inode->i_sb, &retries)) { 3073fd28784aSAneesh Kumar K.V ret = 0; 3074a2df2a63SAmit Arora goto retry; 3075a2df2a63SAmit Arora } 307655bd725aSAneesh Kumar K.V mutex_unlock(&inode->i_mutex); 3077a2df2a63SAmit Arora return ret > 0 ? ret2 : ret; 3078a2df2a63SAmit Arora } 30796873fa0dSEric Sandeen 30806873fa0dSEric Sandeen /* 30816873fa0dSEric Sandeen * Callback function called for each extent to gather FIEMAP information. 30826873fa0dSEric Sandeen */ 30836873fa0dSEric Sandeen int ext4_ext_fiemap_cb(struct inode *inode, struct ext4_ext_path *path, 30846873fa0dSEric Sandeen struct ext4_ext_cache *newex, struct ext4_extent *ex, 30856873fa0dSEric Sandeen void *data) 30866873fa0dSEric Sandeen { 30876873fa0dSEric Sandeen struct fiemap_extent_info *fieinfo = data; 30886873fa0dSEric Sandeen unsigned long blksize_bits = inode->i_sb->s_blocksize_bits; 30896873fa0dSEric Sandeen __u64 logical; 30906873fa0dSEric Sandeen __u64 physical; 30916873fa0dSEric Sandeen __u64 length; 30926873fa0dSEric Sandeen __u32 flags = 0; 30936873fa0dSEric Sandeen int error; 30946873fa0dSEric Sandeen 30956873fa0dSEric Sandeen logical = (__u64)newex->ec_block << blksize_bits; 30966873fa0dSEric Sandeen 30976873fa0dSEric Sandeen if (newex->ec_type == EXT4_EXT_CACHE_GAP) { 30986873fa0dSEric Sandeen pgoff_t offset; 30996873fa0dSEric Sandeen struct page *page; 31006873fa0dSEric Sandeen struct buffer_head *bh = NULL; 31016873fa0dSEric Sandeen 31026873fa0dSEric Sandeen offset = logical >> PAGE_SHIFT; 31036873fa0dSEric Sandeen page = find_get_page(inode->i_mapping, offset); 31046873fa0dSEric Sandeen if (!page || !page_has_buffers(page)) 31056873fa0dSEric Sandeen return EXT_CONTINUE; 31066873fa0dSEric Sandeen 31076873fa0dSEric Sandeen bh = page_buffers(page); 31086873fa0dSEric Sandeen 31096873fa0dSEric Sandeen if (!bh) 31106873fa0dSEric Sandeen return EXT_CONTINUE; 31116873fa0dSEric Sandeen 31126873fa0dSEric Sandeen if (buffer_delay(bh)) { 31136873fa0dSEric Sandeen flags |= FIEMAP_EXTENT_DELALLOC; 31146873fa0dSEric Sandeen page_cache_release(page); 31156873fa0dSEric Sandeen } else { 31166873fa0dSEric Sandeen page_cache_release(page); 31176873fa0dSEric Sandeen return EXT_CONTINUE; 31186873fa0dSEric Sandeen } 31196873fa0dSEric Sandeen } 31206873fa0dSEric Sandeen 31216873fa0dSEric Sandeen physical = (__u64)newex->ec_start << blksize_bits; 31226873fa0dSEric Sandeen length = (__u64)newex->ec_len << blksize_bits; 31236873fa0dSEric Sandeen 31246873fa0dSEric Sandeen if (ex && ext4_ext_is_uninitialized(ex)) 31256873fa0dSEric Sandeen flags |= FIEMAP_EXTENT_UNWRITTEN; 31266873fa0dSEric Sandeen 31276873fa0dSEric Sandeen /* 31286873fa0dSEric Sandeen * If this extent reaches EXT_MAX_BLOCK, it must be last. 31296873fa0dSEric Sandeen * 31306873fa0dSEric Sandeen * Or if ext4_ext_next_allocated_block is EXT_MAX_BLOCK, 31316873fa0dSEric Sandeen * this also indicates no more allocated blocks. 31326873fa0dSEric Sandeen * 31336873fa0dSEric Sandeen * XXX this might miss a single-block extent at EXT_MAX_BLOCK 31346873fa0dSEric Sandeen */ 31356873fa0dSEric Sandeen if (logical + length - 1 == EXT_MAX_BLOCK || 31366873fa0dSEric Sandeen ext4_ext_next_allocated_block(path) == EXT_MAX_BLOCK) 31376873fa0dSEric Sandeen flags |= FIEMAP_EXTENT_LAST; 31386873fa0dSEric Sandeen 31396873fa0dSEric Sandeen error = fiemap_fill_next_extent(fieinfo, logical, physical, 31406873fa0dSEric Sandeen length, flags); 31416873fa0dSEric Sandeen if (error < 0) 31426873fa0dSEric Sandeen return error; 31436873fa0dSEric Sandeen if (error == 1) 31446873fa0dSEric Sandeen return EXT_BREAK; 31456873fa0dSEric Sandeen 31466873fa0dSEric Sandeen return EXT_CONTINUE; 31476873fa0dSEric Sandeen } 31486873fa0dSEric Sandeen 31496873fa0dSEric Sandeen /* fiemap flags we can handle specified here */ 31506873fa0dSEric Sandeen #define EXT4_FIEMAP_FLAGS (FIEMAP_FLAG_SYNC|FIEMAP_FLAG_XATTR) 31516873fa0dSEric Sandeen 31526873fa0dSEric Sandeen int ext4_xattr_fiemap(struct inode *inode, struct fiemap_extent_info *fieinfo) 31536873fa0dSEric Sandeen { 31546873fa0dSEric Sandeen __u64 physical = 0; 31556873fa0dSEric Sandeen __u64 length; 31566873fa0dSEric Sandeen __u32 flags = FIEMAP_EXTENT_LAST; 31576873fa0dSEric Sandeen int blockbits = inode->i_sb->s_blocksize_bits; 31586873fa0dSEric Sandeen int error = 0; 31596873fa0dSEric Sandeen 31606873fa0dSEric Sandeen /* in-inode? */ 31616873fa0dSEric Sandeen if (EXT4_I(inode)->i_state & EXT4_STATE_XATTR) { 31626873fa0dSEric Sandeen struct ext4_iloc iloc; 31636873fa0dSEric Sandeen int offset; /* offset of xattr in inode */ 31646873fa0dSEric Sandeen 31656873fa0dSEric Sandeen error = ext4_get_inode_loc(inode, &iloc); 31666873fa0dSEric Sandeen if (error) 31676873fa0dSEric Sandeen return error; 31686873fa0dSEric Sandeen physical = iloc.bh->b_blocknr << blockbits; 31696873fa0dSEric Sandeen offset = EXT4_GOOD_OLD_INODE_SIZE + 31706873fa0dSEric Sandeen EXT4_I(inode)->i_extra_isize; 31716873fa0dSEric Sandeen physical += offset; 31726873fa0dSEric Sandeen length = EXT4_SB(inode->i_sb)->s_inode_size - offset; 31736873fa0dSEric Sandeen flags |= FIEMAP_EXTENT_DATA_INLINE; 31746873fa0dSEric Sandeen } else { /* external block */ 31756873fa0dSEric Sandeen physical = EXT4_I(inode)->i_file_acl << blockbits; 31766873fa0dSEric Sandeen length = inode->i_sb->s_blocksize; 31776873fa0dSEric Sandeen } 31786873fa0dSEric Sandeen 31796873fa0dSEric Sandeen if (physical) 31806873fa0dSEric Sandeen error = fiemap_fill_next_extent(fieinfo, 0, physical, 31816873fa0dSEric Sandeen length, flags); 31826873fa0dSEric Sandeen return (error < 0 ? error : 0); 31836873fa0dSEric Sandeen } 31846873fa0dSEric Sandeen 31856873fa0dSEric Sandeen int ext4_fiemap(struct inode *inode, struct fiemap_extent_info *fieinfo, 31866873fa0dSEric Sandeen __u64 start, __u64 len) 31876873fa0dSEric Sandeen { 31886873fa0dSEric Sandeen ext4_lblk_t start_blk; 31896873fa0dSEric Sandeen ext4_lblk_t len_blks; 31906873fa0dSEric Sandeen int error = 0; 31916873fa0dSEric Sandeen 31926873fa0dSEric Sandeen /* fallback to generic here if not in extents fmt */ 31936873fa0dSEric Sandeen if (!(EXT4_I(inode)->i_flags & EXT4_EXTENTS_FL)) 31946873fa0dSEric Sandeen return generic_block_fiemap(inode, fieinfo, start, len, 31956873fa0dSEric Sandeen ext4_get_block); 31966873fa0dSEric Sandeen 31976873fa0dSEric Sandeen if (fiemap_check_flags(fieinfo, EXT4_FIEMAP_FLAGS)) 31986873fa0dSEric Sandeen return -EBADR; 31996873fa0dSEric Sandeen 32006873fa0dSEric Sandeen if (fieinfo->fi_flags & FIEMAP_FLAG_XATTR) { 32016873fa0dSEric Sandeen error = ext4_xattr_fiemap(inode, fieinfo); 32026873fa0dSEric Sandeen } else { 32036873fa0dSEric Sandeen start_blk = start >> inode->i_sb->s_blocksize_bits; 32046873fa0dSEric Sandeen len_blks = len >> inode->i_sb->s_blocksize_bits; 32056873fa0dSEric Sandeen 32066873fa0dSEric Sandeen /* 32076873fa0dSEric Sandeen * Walk the extent tree gathering extent information. 32086873fa0dSEric Sandeen * ext4_ext_fiemap_cb will push extents back to user. 32096873fa0dSEric Sandeen */ 32106873fa0dSEric Sandeen down_write(&EXT4_I(inode)->i_data_sem); 32116873fa0dSEric Sandeen error = ext4_ext_walk_space(inode, start_blk, len_blks, 32126873fa0dSEric Sandeen ext4_ext_fiemap_cb, fieinfo); 32136873fa0dSEric Sandeen up_write(&EXT4_I(inode)->i_data_sem); 32146873fa0dSEric Sandeen } 32156873fa0dSEric Sandeen 32166873fa0dSEric Sandeen return error; 32176873fa0dSEric Sandeen } 32186873fa0dSEric Sandeen 3219