-/*\r
- * Copyright (c) 2013 Grzegorz Kostka (kostka.grzegorz@gmail.com)\r
- *\r
- *\r
- * HelenOS:\r
- * Copyright (c) 2012 Martin Sucha\r
- * Copyright (c) 2012 Frantisek Princ\r
- * All rights reserved.\r
- *\r
- * Redistribution and use in source and binary forms, with or without\r
- * modification, are permitted provided that the following conditions\r
- * are met:\r
- *\r
- * - Redistributions of source code must retain the above copyright\r
- * notice, this list of conditions and the following disclaimer.\r
- * - Redistributions in binary form must reproduce the above copyright\r
- * notice, this list of conditions and the following disclaimer in the\r
- * documentation and/or other materials provided with the distribution.\r
- * - The name of the author may not be used to endorse or promote products\r
- * derived from this software without specific prior written permission.\r
- *\r
- * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR\r
- * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES\r
- * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.\r
- * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,\r
- * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT\r
- * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,\r
- * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY\r
- * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT\r
- * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF\r
- * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.\r
- */\r
-\r
-/** @addtogroup lwext4\r
- * @{\r
- */\r
-/**\r
- * @file ext4_extent.c\r
- * @brief More complex filesystem functions.\r
- */\r
-\r
-#include <ext4_config.h>\r
-#include <ext4_extent.h>\r
-#include <ext4_inode.h>\r
-#include <ext4_super.h>\r
-#include <ext4_blockdev.h>\r
-#include <ext4_balloc.h>\r
-\r
-#include <string.h>\r
-#include <stdlib.h>\r
-\r
-uint32_t ext4_extent_get_first_block(struct ext4_extent *extent)\r
-{\r
- return to_le32(extent->first_block);\r
-}\r
-\r
-\r
-void ext4_extent_set_first_block(struct ext4_extent *extent, uint32_t iblock)\r
-{\r
- extent->first_block = to_le32(iblock);\r
-}\r
-\r
-\r
-uint16_t ext4_extent_get_block_count(struct ext4_extent *extent)\r
-{\r
- return to_le16(extent->block_count);\r
-}\r
-\r
-\r
-void ext4_extent_set_block_count(struct ext4_extent *extent, uint16_t count)\r
-{\r
- extent->block_count = to_le16(count);\r
-}\r
-\r
-\r
-uint64_t ext4_extent_get_start(struct ext4_extent *extent)\r
-{\r
- return ((uint64_t)to_le16(extent->start_hi)) << 32 |\r
- ((uint64_t)to_le32(extent->start_lo));\r
-}\r
-\r
-\r
-void ext4_extent_set_start(struct ext4_extent *extent, uint64_t fblock)\r
-{\r
- extent->start_lo = to_le32((fblock << 32) >> 32);\r
- extent->start_hi = to_le16((uint16_t)(fblock >> 32));\r
-}\r
-\r
-\r
-uint32_t ext4_extent_index_get_first_block(struct ext4_extent_index *index)\r
-{\r
- return to_le32(index->first_block);\r
-}\r
-\r
-\r
-void ext4_extent_index_set_first_block(struct ext4_extent_index *index,\r
- uint32_t iblock)\r
-{\r
- index->first_block = to_le32(iblock);\r
-}\r
-\r
-\r
-uint64_t ext4_extent_index_get_leaf(struct ext4_extent_index *index)\r
-{\r
- return ((uint64_t) to_le16(index->leaf_hi)) << 32 |\r
- ((uint64_t)to_le32(index->leaf_lo));\r
-}\r
-\r
-void ext4_extent_index_set_leaf(struct ext4_extent_index *index,\r
- uint64_t fblock)\r
-{\r
- index->leaf_lo = to_le32((fblock << 32) >> 32);\r
- index->leaf_hi = to_le16((uint16_t) (fblock >> 32));\r
-}\r
-\r
-\r
-uint16_t ext4_extent_header_get_magic(struct ext4_extent_header *header)\r
-{\r
- return to_le16(header->magic);\r
-}\r
-\r
-\r
-void ext4_extent_header_set_magic(struct ext4_extent_header *header,\r
- uint16_t magic)\r
-{\r
- header->magic = to_le16(magic);\r
-}\r
-\r
-\r
-uint16_t ext4_extent_header_get_entries_count(struct ext4_extent_header *header)\r
-{\r
- return to_le16(header->entries_count);\r
-}\r
-\r
-\r
-void ext4_extent_header_set_entries_count(struct ext4_extent_header *header,\r
- uint16_t count)\r
-{\r
- header->entries_count = to_le16(count);\r
-}\r
-\r
-\r
-uint16_t ext4_extent_header_get_max_entries_count(struct ext4_extent_header *header)\r
-{\r
- return to_le16(header->max_entries_count);\r
-}\r
-\r
-\r
-void ext4_extent_header_set_max_entries_count(struct ext4_extent_header *header,\r
- uint16_t max_count)\r
-{\r
- header->max_entries_count = to_le16(max_count);\r
-}\r
-\r
-\r
-uint16_t ext4_extent_header_get_depth(struct ext4_extent_header *header)\r
-{\r
- return to_le16(header->depth);\r
-}\r
-\r
-\r
-void ext4_extent_header_set_depth(struct ext4_extent_header *header,\r
- uint16_t depth)\r
-{\r
- header->depth = to_le16(depth);\r
-}\r
-\r
-\r
-uint32_t ext4_extent_header_get_generation(struct ext4_extent_header *header)\r
-{\r
- return to_le32(header->generation);\r
-}\r
-\r
-\r
-void ext4_extent_header_set_generation(struct ext4_extent_header *header,\r
- uint32_t generation)\r
-{\r
- header->generation = to_le32(generation);\r
-}\r
-\r
-/**@brief Binary search in extent index node.\r
- * @param header Extent header of index node\r
- * @param index Output value - found index will be set here\r
- * @param iblock Logical block number to find in index node */\r
-static void ext4_extent_binsearch_idx(struct ext4_extent_header *header,\r
- struct ext4_extent_index **index, uint32_t iblock)\r
-{\r
- struct ext4_extent_index *r;\r
- struct ext4_extent_index *l;\r
- struct ext4_extent_index *m;\r
-\r
- uint16_t entries_count =\r
- ext4_extent_header_get_entries_count(header);\r
-\r
- /* Initialize bounds */\r
- l = EXT4_EXTENT_FIRST_INDEX(header) + 1;\r
- r = EXT4_EXTENT_FIRST_INDEX(header) + entries_count - 1;\r
-\r
- /* Do binary search */\r
- while (l <= r) {\r
- m = l + (r - l) / 2;\r
- uint32_t first_block = ext4_extent_index_get_first_block(m);\r
-\r
- if (iblock < first_block)\r
- r = m - 1;\r
- else\r
- l = m + 1;\r
- }\r
-\r
- /* Set output value */\r
- *index = l - 1;\r
-}\r
-\r
-/**@brief Binary search in extent leaf node.\r
- * @param header Extent header of leaf node\r
- * @param extent Output value - found extent will be set here,\r
- * or NULL if node is empty\r
- * @param iblock Logical block number to find in leaf node */\r
-static void ext4_extent_binsearch(struct ext4_extent_header *header,\r
- struct ext4_extent **extent, uint32_t iblock)\r
-{\r
- struct ext4_extent *r;\r
- struct ext4_extent *l;\r
- struct ext4_extent *m;\r
-\r
- uint16_t entries_count =\r
- ext4_extent_header_get_entries_count(header);\r
-\r
- if (entries_count == 0) {\r
- /* this leaf is empty */\r
- *extent = NULL;\r
- return;\r
- }\r
-\r
- /* Initialize bounds */\r
- l = EXT4_EXTENT_FIRST(header) + 1;\r
- r = EXT4_EXTENT_FIRST(header) + entries_count - 1;\r
-\r
- /* Do binary search */\r
- while (l <= r) {\r
- m = l + (r - l) / 2;\r
- uint32_t first_block = ext4_extent_get_first_block(m);\r
-\r
- if (iblock < first_block)\r
- r = m - 1;\r
- else\r
- l = m + 1;\r
- }\r
-\r
- /* Set output value */\r
- *extent = l - 1;\r
-}\r
-\r
-\r
-int ext4_extent_find_block(struct ext4_inode_ref *inode_ref, uint32_t iblock,\r
- uint32_t *fblock)\r
-{\r
- /* Compute bound defined by i-node size */\r
- uint64_t inode_size =\r
- ext4_inode_get_size(&inode_ref->fs->sb, inode_ref->inode);\r
-\r
- uint32_t block_size =\r
- ext4_sb_get_block_size(&inode_ref->fs->sb);\r
-\r
- uint32_t last_idx = (inode_size - 1) / block_size;\r
-\r
- /* Check if requested iblock is not over size of i-node */\r
- if (iblock > last_idx) {\r
- *fblock = 0;\r
- return EOK;\r
- }\r
-\r
- struct ext4_block block;\r
- block.lb_id = 0;\r
-\r
- /* Walk through extent tree */\r
- struct ext4_extent_header *header =\r
- ext4_inode_get_extent_header(inode_ref->inode);\r
-\r
- while (ext4_extent_header_get_depth(header) != 0) {\r
- /* Search index in node */\r
- struct ext4_extent_index *index;\r
- ext4_extent_binsearch_idx(header, &index, iblock);\r
-\r
- /* Load child node and set values for the next iteration */\r
- uint64_t child = ext4_extent_index_get_leaf(index);\r
-\r
- if (block.lb_id)\r
- ext4_block_set(inode_ref->fs->bdev, &block);\r
-\r
-\r
- int rc = ext4_block_get(inode_ref->fs->bdev, &block, child);\r
- if (rc != EOK)\r
- return rc;\r
-\r
- header = (struct ext4_extent_header *)block.data;\r
- }\r
-\r
- /* Search extent in the leaf block */\r
- struct ext4_extent* extent = NULL;\r
- ext4_extent_binsearch(header, &extent, iblock);\r
-\r
- /* Prevent empty leaf */\r
- if (extent == NULL) {\r
- *fblock = 0;\r
- } else {\r
- /* Compute requested physical block address */\r
- uint32_t phys_block;\r
- uint32_t first = ext4_extent_get_first_block(extent);\r
- phys_block = ext4_extent_get_start(extent) + iblock - first;\r
-\r
- *fblock = phys_block;\r
- }\r
-\r
- /* Cleanup */\r
- if (block.lb_id)\r
- ext4_block_set(inode_ref->fs->bdev, &block);\r
-\r
- return EOK;\r
-}\r
-\r
-/**@brief Find extent for specified iblock.\r
- * This function is used for finding block in the extent tree with\r
- * saving the path through the tree for possible future modifications.\r
- * @param inode_ref I-node to read extent tree from\r
- * @param iblock Iblock to find extent for\r
- * @param ret_path Output value for loaded path from extent tree\r
- * @return Error code */\r
-static int ext4_extent_find_extent(struct ext4_inode_ref *inode_ref,\r
- uint32_t iblock, struct ext4_extent_path **ret_path)\r
-{\r
- struct ext4_extent_header *eh =\r
- ext4_inode_get_extent_header(inode_ref->inode);\r
-\r
- uint16_t depth = ext4_extent_header_get_depth(eh);\r
- uint16_t i;\r
- struct ext4_extent_path *tmp_path;\r
-\r
- /* Added 2 for possible tree growing */\r
- tmp_path = malloc(sizeof(struct ext4_extent_path) * (depth + 2));\r
- if (tmp_path == NULL)\r
- return ENOMEM;\r
-\r
- /* Initialize structure for algorithm start */\r
- tmp_path[0].block = inode_ref->block;\r
- tmp_path[0].header = eh;\r
-\r
- /* Walk through the extent tree */\r
- uint16_t pos = 0;\r
- int rc;\r
- while (ext4_extent_header_get_depth(eh) != 0) {\r
- /* Search index in index node by iblock */\r
- ext4_extent_binsearch_idx(tmp_path[pos].header,\r
- &tmp_path[pos].index, iblock);\r
-\r
- tmp_path[pos].depth = depth;\r
- tmp_path[pos].extent = NULL;\r
-\r
- ext4_assert(tmp_path[pos].index != 0);\r
-\r
- /* Load information for the next iteration */\r
- uint64_t fblock = ext4_extent_index_get_leaf(tmp_path[pos].index);\r
-\r
- struct ext4_block block;\r
- rc = ext4_block_get(inode_ref->fs->bdev, &block, fblock);\r
- if (rc != EOK)\r
- goto cleanup;\r
-\r
- pos++;\r
-\r
- eh = (struct ext4_extent_header *)block.data;\r
- tmp_path[pos].block = block;\r
- tmp_path[pos].header = eh;\r
- }\r
-\r
- tmp_path[pos].depth = 0;\r
- tmp_path[pos].extent = NULL;\r
- tmp_path[pos].index = NULL;\r
-\r
- /* Find extent in the leaf node */\r
- ext4_extent_binsearch(tmp_path[pos].header, &tmp_path[pos].extent, iblock);\r
- *ret_path = tmp_path;\r
-\r
- return EOK;\r
-\r
-cleanup:\r
- /*\r
- * Put loaded blocks\r
- * From 1: 0 is a block with inode data\r
- */\r
- for (i = 1; i < tmp_path->depth; ++i) {\r
- if (tmp_path[i].block.lb_id)\r
- ext4_block_set(inode_ref->fs->bdev, &tmp_path[i].block);\r
- }\r
-\r
- /* Destroy temporary data structure */\r
- free(tmp_path);\r
-\r
- return rc;\r
-}\r
-\r
-/**@brief Release extent and all data blocks covered by the extent.\r
- * @param inode_ref I-node to release extent and block from\r
- * @param extent Extent to release\r
- * @return Error code */\r
-static int ext4_extent_release(struct ext4_inode_ref *inode_ref,\r
- struct ext4_extent *extent)\r
-{\r
- /* Compute number of the first physical block to release */\r
- uint64_t start = ext4_extent_get_start(extent);\r
- uint16_t block_count = ext4_extent_get_block_count(extent);\r
-\r
- return ext4_balloc_free_blocks(inode_ref, start, block_count);\r
-}\r
-\r
-/** Recursively release the whole branch of the extent tree.\r
- * For each entry of the node release the subbranch and finally release\r
- * the node. In the leaf node all extents will be released.\r
- * @param inode_ref I-node where the branch is released\r
- * @param index Index in the non-leaf node to be released\r
- * with the whole subtree\r
- * @return Error code */\r
-static int ext4_extent_release_branch(struct ext4_inode_ref *inode_ref,\r
- struct ext4_extent_index *index)\r
-{\r
- uint32_t fblock = ext4_extent_index_get_leaf(index);\r
- uint32_t i;\r
- struct ext4_block block;\r
- int rc = ext4_block_get(inode_ref->fs->bdev, &block, fblock);\r
- if (rc != EOK)\r
- return rc;\r
-\r
- struct ext4_extent_header *header = (void *)block.data;\r
-\r
- if (ext4_extent_header_get_depth(header)) {\r
- /* The node is non-leaf, do recursion */\r
- struct ext4_extent_index *idx = EXT4_EXTENT_FIRST_INDEX(header);\r
-\r
- /* Release all subbranches */\r
- for (i = 0; i < ext4_extent_header_get_entries_count(header);\r
- ++i, ++idx) {\r
- rc = ext4_extent_release_branch(inode_ref, idx);\r
- if (rc != EOK)\r
- return rc;\r
- }\r
- } else {\r
- /* Leaf node reached */\r
- struct ext4_extent *ext = EXT4_EXTENT_FIRST(header);\r
-\r
- /* Release all extents and stop recursion */\r
- for (i = 0; i < ext4_extent_header_get_entries_count(header);\r
- ++i, ++ext) {\r
- rc = ext4_extent_release(inode_ref, ext);\r
- if (rc != EOK)\r
- return rc;\r
- }\r
- }\r
-\r
- /* Release data block where the node was stored */\r
-\r
- rc = ext4_block_set(inode_ref->fs->bdev, &block);\r
- if (rc != EOK)\r
- return rc;\r
-\r
- ext4_balloc_free_block(inode_ref, fblock);\r
-\r
- return EOK;\r
-}\r
-\r
-\r
-int ext4_extent_release_blocks_from(struct ext4_inode_ref *inode_ref,\r
- uint32_t iblock_from)\r
-{\r
- /* Find the first extent to modify */\r
- struct ext4_extent_path *path;\r
- uint16_t i;\r
- int rc = ext4_extent_find_extent(inode_ref, iblock_from, &path);\r
- if (rc != EOK)\r
- return rc;\r
-\r
- /* Jump to last item of the path (extent) */\r
- struct ext4_extent_path *path_ptr = path;\r
- while (path_ptr->depth != 0)\r
- path_ptr++;\r
-\r
- ext4_assert(path_ptr->extent != NULL);\r
-\r
- /* First extent maybe released partially */\r
- uint32_t first_iblock =\r
- ext4_extent_get_first_block(path_ptr->extent);\r
- uint32_t first_fblock =\r
- ext4_extent_get_start(path_ptr->extent) + iblock_from - first_iblock;\r
-\r
- uint16_t block_count = ext4_extent_get_block_count(path_ptr->extent);\r
-\r
- uint16_t delete_count = block_count -\r
- (ext4_extent_get_start(path_ptr->extent) - first_fblock);\r
-\r
- /* Release all blocks */\r
- rc = ext4_balloc_free_blocks(inode_ref, first_fblock, delete_count);\r
- if (rc != EOK)\r
- goto cleanup;\r
-\r
- /* Correct counter */\r
- block_count -= delete_count;\r
- ext4_extent_set_block_count(path_ptr->extent, block_count);\r
-\r
- /* Initialize the following loop */\r
- uint16_t entries =\r
- ext4_extent_header_get_entries_count(path_ptr->header);\r
- struct ext4_extent *tmp_ext = path_ptr->extent + 1;\r
- struct ext4_extent *stop_ext = EXT4_EXTENT_FIRST(path_ptr->header) + entries;\r
-\r
- /* If first extent empty, release it */\r
- if (block_count == 0)\r
- entries--;\r
-\r
- /* Release all successors of the first extent in the same node */\r
- while (tmp_ext < stop_ext) {\r
- first_fblock = ext4_extent_get_start(tmp_ext);\r
- delete_count = ext4_extent_get_block_count(tmp_ext);\r
-\r
- rc = ext4_balloc_free_blocks(inode_ref, first_fblock, delete_count);\r
- if (rc != EOK)\r
- goto cleanup;\r
-\r
- entries--;\r
- tmp_ext++;\r
- }\r
-\r
- ext4_extent_header_set_entries_count(path_ptr->header, entries);\r
- path_ptr->block.dirty = true;\r
-\r
- /* If leaf node is empty, parent entry must be modified */\r
- bool remove_parent_record = false;\r
-\r
- /* Don't release root block (including inode data) !!! */\r
- if ((path_ptr != path) && (entries == 0)) {\r
- rc = ext4_balloc_free_block(inode_ref, path_ptr->block.lb_id);\r
- if (rc != EOK)\r
- goto cleanup;\r
-\r
- remove_parent_record = true;\r
- }\r
-\r
- /* Jump to the parent */\r
- --path_ptr;\r
-\r
- /* Release all successors in all tree levels */\r
- while (path_ptr >= path) {\r
- entries = ext4_extent_header_get_entries_count(path_ptr->header);\r
- struct ext4_extent_index *index = path_ptr->index + 1;\r
- struct ext4_extent_index *stop =\r
- EXT4_EXTENT_FIRST_INDEX(path_ptr->header) + entries;\r
-\r
- /* Correct entries count because of changes in the previous iteration */\r
- if (remove_parent_record)\r
- entries--;\r
-\r
- /* Iterate over all entries and release the whole subtrees */\r
- while (index < stop) {\r
- rc = ext4_extent_release_branch(inode_ref, index);\r
- if (rc != EOK)\r
- goto cleanup;\r
-\r
- ++index;\r
- --entries;\r
- }\r
-\r
- ext4_extent_header_set_entries_count(path_ptr->header, entries);\r
- path_ptr->block.dirty = true;\r
-\r
- /* Free the node if it is empty */\r
- if ((entries == 0) && (path_ptr != path)) {\r
- rc = ext4_balloc_free_block(inode_ref, path_ptr->block.lb_id);\r
- if (rc != EOK)\r
- goto cleanup;\r
-\r
- /* Mark parent to be checked */\r
- remove_parent_record = true;\r
- } else\r
- remove_parent_record = false;\r
-\r
- --path_ptr;\r
- }\r
-\r
- if(!entries)\r
- ext4_extent_header_set_depth(path->header, 0);\r
-\r
-cleanup:\r
- /*\r
- * Put loaded blocks\r
- * starting from 1: 0 is a block with inode data\r
- */\r
- for (i = 1; i <= path->depth; ++i) {\r
- if (path[i].block.lb_id)\r
- ext4_block_set(inode_ref->fs->bdev, &path[i].block);\r
- }\r
-\r
- /* Destroy temporary data structure */\r
- free(path);\r
-\r
- return rc;\r
-}\r
-\r
-/**@brief Append new extent to the i-node and do some splitting if necessary.\r
- * @param inode_ref I-node to append extent to\r
- * @param path Path in the extent tree for possible splitting\r
- * @param last_path_item Input/output parameter for pointer to the last\r
- * valid item in the extent tree path\r
- * @param iblock Logical index of block to append extent for\r
- * @return Error code */\r
-static int ext4_extent_append_extent(struct ext4_inode_ref *inode_ref,\r
- struct ext4_extent_path *path, uint32_t iblock)\r
-{\r
- struct ext4_extent_path *path_ptr = path + path->depth;\r
-\r
- uint32_t block_size =\r
- ext4_sb_get_block_size(&inode_ref->fs->sb);\r
-\r
- /* Start splitting */\r
- while (path_ptr > path) {\r
- uint16_t entries =\r
- ext4_extent_header_get_entries_count(path_ptr->header);\r
- uint16_t limit =\r
- ext4_extent_header_get_max_entries_count(path_ptr->header);\r
-\r
- if (entries == limit) {\r
- /* Full node - allocate block for new one */\r
- uint32_t fblock;\r
- int rc = ext4_balloc_alloc_block(inode_ref, &fblock);\r
- if (rc != EOK)\r
- return rc;\r
-\r
- struct ext4_block block;\r
- rc = ext4_block_get(inode_ref->fs->bdev, &block, fblock);\r
- if (rc != EOK) {\r
- ext4_balloc_free_block(inode_ref, fblock);\r
- return rc;\r
- }\r
-\r
- /* Put back not modified old block */\r
- ext4_block_set(inode_ref->fs->bdev, &path_ptr->block);\r
-\r
- /* Initialize newly allocated block and remember it */\r
- memset(block.data, 0, block_size);\r
- path_ptr->block = block;\r
-\r
- /* Update pointers in extent path structure */\r
- path_ptr->header = (void *)block.data;\r
- if (path_ptr->depth) {\r
- path_ptr->index = EXT4_EXTENT_FIRST_INDEX(path_ptr->header);\r
- ext4_extent_index_set_first_block(path_ptr->index, iblock);\r
- ext4_extent_index_set_leaf(path_ptr->index,\r
- (path_ptr + 1)->block.lb_id);\r
- limit = (block_size - sizeof(struct ext4_extent_header)) /\r
- sizeof(struct ext4_extent_index);\r
- } else {\r
- path_ptr->extent = EXT4_EXTENT_FIRST(path_ptr->header);\r
- ext4_extent_set_first_block(path_ptr->extent, iblock);\r
- limit = (block_size - sizeof(struct ext4_extent_header)) /\r
- sizeof(struct ext4_extent);\r
- }\r
-\r
- /* Initialize on-disk structure (header) */\r
- ext4_extent_header_set_entries_count(path_ptr->header, 1);\r
- ext4_extent_header_set_max_entries_count(path_ptr->header, limit);\r
- ext4_extent_header_set_magic(path_ptr->header, EXT4_EXTENT_MAGIC);\r
- ext4_extent_header_set_depth(path_ptr->header, path_ptr->depth);\r
- ext4_extent_header_set_generation(path_ptr->header, 0);\r
-\r
- path_ptr->block.dirty = true;\r
-\r
- /* Jump to the preceeding item */\r
- path_ptr--;\r
- } else {\r
- /* Node with free space */\r
- if (path_ptr->depth) {\r
- path_ptr->index = EXT4_EXTENT_FIRST_INDEX(path_ptr->header) + entries;\r
- ext4_extent_index_set_first_block(path_ptr->index, iblock);\r
- ext4_extent_index_set_leaf(path_ptr->index,\r
- (path_ptr + 1)->block.lb_id);\r
- } else {\r
- path_ptr->extent = EXT4_EXTENT_FIRST(path_ptr->header) + entries;\r
- ext4_extent_set_first_block(path_ptr->extent, iblock);\r
- }\r
-\r
- ext4_extent_header_set_entries_count(path_ptr->header, entries + 1);\r
- path_ptr->block.dirty = true;\r
-\r
- /* No more splitting needed */\r
- return EOK;\r
- }\r
- }\r
-\r
- ext4_assert(path_ptr == path);\r
-\r
- /* Should be the root split too? */\r
-\r
- uint16_t entries = ext4_extent_header_get_entries_count(path->header);\r
- uint16_t limit = ext4_extent_header_get_max_entries_count(path->header);\r
-\r
- if (entries == limit) {\r
- uint32_t new_fblock;\r
- int rc = ext4_balloc_alloc_block(inode_ref, &new_fblock);\r
- if (rc != EOK)\r
- return rc;\r
-\r
- struct ext4_block block;\r
- rc = ext4_block_get(inode_ref->fs->bdev, &block, new_fblock);\r
- if (rc != EOK)\r
- return rc;\r
-\r
- /* Initialize newly allocated block */\r
- memset(block.data, 0, block_size);\r
-\r
- /* Move data from root to the new block */\r
- memcpy(block.data, inode_ref->inode->blocks,\r
- EXT4_INODE_BLOCKS * sizeof(uint32_t));\r
-\r
- /* Data block is initialized */\r
-\r
- struct ext4_block *root_block = &path->block;\r
- uint16_t root_depth = path->depth;\r
- struct ext4_extent_header *root_header = path->header;\r
-\r
- /* Make space for tree growing */\r
- struct ext4_extent_path *new_root = path;\r
- struct ext4_extent_path *old_root = path + 1;\r
-\r
- size_t nbytes = sizeof(struct ext4_extent_path) * (path->depth + 1);\r
- memmove(old_root, new_root, nbytes);\r
- memset(new_root, 0, sizeof(struct ext4_extent_path));\r
-\r
- /* Update old root structure */\r
- old_root->block = block;\r
- old_root->header = (struct ext4_extent_header *)block.data;\r
-\r
- /* Add new entry and update limit for entries */\r
- if (old_root->depth) {\r
- limit = (block_size - sizeof(struct ext4_extent_header)) /\r
- sizeof(struct ext4_extent_index);\r
- old_root->index = EXT4_EXTENT_FIRST_INDEX(old_root->header) + entries;\r
- ext4_extent_index_set_first_block(old_root->index, iblock);\r
- ext4_extent_index_set_leaf(old_root->index,\r
- (old_root + 1)->block.lb_id);\r
- old_root->extent = NULL;\r
- } else {\r
- limit = (block_size - sizeof(struct ext4_extent_header)) /\r
- sizeof(struct ext4_extent);\r
- old_root->extent = EXT4_EXTENT_FIRST(old_root->header) + entries;\r
- ext4_extent_set_first_block(old_root->extent, iblock);\r
- old_root->index = NULL;\r
- }\r
-\r
- ext4_extent_header_set_entries_count(old_root->header, entries + 1);\r
- ext4_extent_header_set_max_entries_count(old_root->header, limit);\r
-\r
- old_root->block.dirty = true;\r
-\r
- /* Re-initialize new root metadata */\r
- new_root->depth = root_depth + 1;\r
- new_root->block = *root_block;\r
- new_root->header = root_header;\r
- new_root->extent = NULL;\r
- new_root->index = EXT4_EXTENT_FIRST_INDEX(new_root->header);\r
-\r
- ext4_extent_header_set_depth(new_root->header, new_root->depth);\r
-\r
- /* Create new entry in root */\r
- ext4_extent_header_set_entries_count(new_root->header, 1);\r
- ext4_extent_index_set_first_block(new_root->index, 0);\r
- ext4_extent_index_set_leaf(new_root->index, new_fblock);\r
-\r
- new_root->block.dirty = true;\r
- } else {\r
- if (path->depth) {\r
- path->index = EXT4_EXTENT_FIRST_INDEX(path->header) + entries;\r
- ext4_extent_index_set_first_block(path->index, iblock);\r
- ext4_extent_index_set_leaf(path->index, (path + 1)->block.lb_id);\r
- } else {\r
- path->extent = EXT4_EXTENT_FIRST(path->header) + entries;\r
- ext4_extent_set_first_block(path->extent, iblock);\r
- }\r
-\r
- ext4_extent_header_set_entries_count(path->header, entries + 1);\r
- path->block.dirty = true;\r
- }\r
-\r
- return EOK;\r
-}\r
-\r
-\r
-int ext4_extent_append_block(struct ext4_inode_ref *inode_ref,\r
- uint32_t *iblock, uint32_t *fblock, bool update_size)\r
-{\r
- uint16_t i;\r
- struct ext4_sblock *sb = &inode_ref->fs->sb;\r
- uint64_t inode_size = ext4_inode_get_size(sb, inode_ref->inode);\r
- uint32_t block_size = ext4_sb_get_block_size(sb);\r
-\r
- /* Calculate number of new logical block */\r
- uint32_t new_block_idx = 0;\r
- if (inode_size > 0) {\r
- if ((inode_size % block_size) != 0)\r
- inode_size += block_size - (inode_size % block_size);\r
-\r
- new_block_idx = inode_size / block_size;\r
- }\r
-\r
- /* Load the nearest leaf (with extent) */\r
- struct ext4_extent_path *path;\r
- int rc = ext4_extent_find_extent(inode_ref, new_block_idx, &path);\r
- if (rc != EOK)\r
- return rc;\r
-\r
- /* Jump to last item of the path (extent) */\r
- struct ext4_extent_path *path_ptr = path;\r
- while (path_ptr->depth != 0)\r
- path_ptr++;\r
-\r
- /* Add new extent to the node if not present */\r
- if (path_ptr->extent == NULL)\r
- goto append_extent;\r
-\r
- uint16_t block_count = ext4_extent_get_block_count(path_ptr->extent);\r
- uint16_t block_limit = (1 << 15);\r
-\r
- uint32_t phys_block = 0;\r
- if (block_count < block_limit) {\r
- /* There is space for new block in the extent */\r
- if (block_count == 0) {\r
- /* Existing extent is empty */\r
- rc = ext4_balloc_alloc_block(inode_ref, &phys_block);\r
- if (rc != EOK)\r
- goto finish;\r
-\r
- /* Initialize extent */\r
- ext4_extent_set_first_block(path_ptr->extent, new_block_idx);\r
- ext4_extent_set_start(path_ptr->extent, phys_block);\r
- ext4_extent_set_block_count(path_ptr->extent, 1);\r
-\r
- /* Update i-node */\r
- if (update_size) {\r
- ext4_inode_set_size(inode_ref->inode, inode_size + block_size);\r
- inode_ref->dirty = true;\r
- }\r
-\r
- path_ptr->block.dirty = true;\r
-\r
- goto finish;\r
- } else {\r
- /* Existing extent contains some blocks */\r
- phys_block = ext4_extent_get_start(path_ptr->extent);\r
- phys_block += ext4_extent_get_block_count(path_ptr->extent);\r
-\r
- /* Check if the following block is free for allocation */\r
- bool free;\r
- rc = ext4_balloc_try_alloc_block(inode_ref, phys_block, &free);\r
- if (rc != EOK)\r
- goto finish;\r
-\r
- if (!free) {\r
- /* Target is not free, new block must be appended to new extent */\r
- goto append_extent;\r
- }\r
-\r
- /* Update extent */\r
- ext4_extent_set_block_count(path_ptr->extent, block_count + 1);\r
-\r
- /* Update i-node */\r
- if (update_size) {\r
- ext4_inode_set_size(inode_ref->inode, inode_size + block_size);\r
- inode_ref->dirty = true;\r
- }\r
-\r
- path_ptr->block.dirty = true;\r
-\r
- goto finish;\r
- }\r
- }\r
-\r
-\r
-append_extent:\r
- /* Append new extent to the tree */\r
- phys_block = 0;\r
-\r
- /* Allocate new data block */\r
- rc = ext4_balloc_alloc_block(inode_ref, &phys_block);\r
- if (rc != EOK)\r
- goto finish;\r
-\r
- /* Append extent for new block (includes tree splitting if needed) */\r
- rc = ext4_extent_append_extent(inode_ref, path, new_block_idx);\r
- if (rc != EOK) {\r
- ext4_balloc_free_block(inode_ref, phys_block);\r
- goto finish;\r
- }\r
-\r
- uint32_t tree_depth = ext4_extent_header_get_depth(path->header);\r
- path_ptr = path + tree_depth;\r
-\r
- /* Initialize newly created extent */\r
- ext4_extent_set_block_count(path_ptr->extent, 1);\r
- ext4_extent_set_first_block(path_ptr->extent, new_block_idx);\r
- ext4_extent_set_start(path_ptr->extent, phys_block);\r
-\r
- /* Update i-node */\r
- if (update_size) {\r
- ext4_inode_set_size(inode_ref->inode, inode_size + block_size);\r
- inode_ref->dirty = true;\r
- }\r
-\r
- path_ptr->block.dirty = true;\r
-\r
-finish:\r
- /* Set return values */\r
- *iblock = new_block_idx;\r
- *fblock = phys_block;\r
-\r
- /*\r
- * Put loaded blocks\r
- * starting from 1: 0 is a block with inode data\r
- */\r
- for (i = 1; i <= path->depth; ++i) {\r
- if (path[i].block.lb_id)\r
- ext4_block_set(inode_ref->fs->bdev, &path[i].block);\r
- }\r
-\r
- /* Destroy temporary data structure */\r
- free(path);\r
-\r
- return rc;\r
-}\r
-\r
-/**\r
- * @}\r
- */\r
+/*
+ * Copyright (c) 2015 Grzegorz Kostka (kostka.grzegorz@gmail.com)
+ * Copyright (c) 2015 Kaho Ng (ngkaho1234@gmail.com)
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * - Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ * - The name of the author may not be used to endorse or promote products
+ * derived from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "ext4_config.h"
+#include "ext4_blockdev.h"
+#include "ext4_fs.h"
+#include "ext4_super.h"
+#include "ext4_crc32.h"
+#include "ext4_balloc.h"
+#include "ext4_debug.h"
+
+#include <stdlib.h>
+#include <string.h>
+#include <inttypes.h>
+#include <stddef.h>
+
+#include "ext4_extent.h"
+
+/*
+ * used by extent splitting.
+ */
+#define EXT4_EXT_MARK_UNWRIT1 0x02 /* mark first half unwritten */
+#define EXT4_EXT_MARK_UNWRIT2 0x04 /* mark second half unwritten */
+#define EXT4_EXT_DATA_VALID1 0x08 /* first half contains valid data */
+#define EXT4_EXT_DATA_VALID2 0x10 /* second half contains valid data */
+#define EXT4_EXT_NO_COMBINE 0x20 /* do not combine two extents */
+
+static struct ext4_extent_tail *
+find_ext4_extent_tail(struct ext4_extent_header *eh)
+{
+ return (struct ext4_extent_tail *)(((char *)eh) +
+ EXT4_EXTENT_TAIL_OFFSET(eh));
+}
+
+static struct ext4_extent_header *ext_inode_hdr(struct ext4_inode *inode)
+{
+ return (struct ext4_extent_header *)inode->blocks;
+}
+
+static struct ext4_extent_header *ext_block_hdr(struct ext4_block *block)
+{
+ return (struct ext4_extent_header *)block->data;
+}
+
+static uint16_t ext_depth(struct ext4_inode *inode)
+{
+ return to_le16(ext_inode_hdr(inode)->depth);
+}
+
+static uint16_t ext4_ext_get_actual_len(struct ext4_extent *ext)
+{
+ return (to_le16(ext->block_count) <= EXT_INIT_MAX_LEN
+ ? to_le16(ext->block_count)
+ : (to_le16(ext->block_count) - EXT_INIT_MAX_LEN));
+}
+
+static void ext4_ext_mark_initialized(struct ext4_extent *ext)
+{
+ ext->block_count = to_le16(ext4_ext_get_actual_len(ext));
+}
+
+static void ext4_ext_mark_unwritten(struct ext4_extent *ext)
+{
+ ext->block_count |= to_le16(EXT_INIT_MAX_LEN);
+}
+
+static int ext4_ext_is_unwritten(struct ext4_extent *ext)
+{
+ /* Extent with ee_len of 0x8000 is treated as an initialized extent */
+ return (to_le16(ext->block_count) > EXT_INIT_MAX_LEN);
+}
+
+/*
+ * ext4_ext_pblock:
+ * combine low and high parts of physical block number into ext4_fsblk_t
+ */
+static ext4_fsblk_t ext4_ext_pblock(struct ext4_extent *ex)
+{
+ ext4_fsblk_t block;
+
+ block = to_le32(ex->start_lo);
+ block |= ((ext4_fsblk_t)to_le16(ex->start_hi) << 31) << 1;
+ return block;
+}
+
+/*
+ * ext4_idx_pblock:
+ * combine low and high parts of a leaf physical block number into ext4_fsblk_t
+ */
+static ext4_fsblk_t ext4_idx_pblock(struct ext4_extent_index *ix)
+{
+ ext4_fsblk_t block;
+
+ block = to_le32(ix->leaf_lo);
+ block |= ((ext4_fsblk_t)to_le16(ix->leaf_hi) << 31) << 1;
+ return block;
+}
+
+/*
+ * ext4_ext_store_pblock:
+ * stores a large physical block number into an extent struct,
+ * breaking it into parts
+ */
+static void ext4_ext_store_pblock(struct ext4_extent *ex, ext4_fsblk_t pb)
+{
+ ex->start_lo = to_le32((uint32_t)(pb & 0xffffffff));
+ ex->start_hi = to_le16((uint16_t)((pb >> 32)) & 0xffff);
+}
+
+/*
+ * ext4_idx_store_pblock:
+ * stores a large physical block number into an index struct,
+ * breaking it into parts
+ */
+static void ext4_idx_store_pblock(struct ext4_extent_index *ix, ext4_fsblk_t pb)
+{
+ ix->leaf_lo = to_le32((uint32_t)(pb & 0xffffffff));
+ ix->leaf_hi = to_le16((uint16_t)((pb >> 32)) & 0xffff);
+}
+
+static int ext4_allocate_single_block(struct ext4_inode_ref *inode_ref,
+ ext4_fsblk_t goal,
+ ext4_fsblk_t *blockp)
+{
+ return ext4_balloc_alloc_block(inode_ref, goal, blockp);
+}
+
+static ext4_fsblk_t ext4_new_meta_blocks(struct ext4_inode_ref *inode_ref,
+ ext4_fsblk_t goal,
+ uint32_t flags __unused,
+ uint32_t *count, int *errp)
+{
+ ext4_fsblk_t block = 0;
+
+ *errp = ext4_allocate_single_block(inode_ref, goal, &block);
+ if (count)
+ *count = 1;
+ return block;
+}
+
+static void ext4_ext_free_blocks(struct ext4_inode_ref *inode_ref,
+ ext4_fsblk_t block, uint32_t count,
+ uint32_t flags __unused)
+{
+ ext4_balloc_free_blocks(inode_ref, block, count);
+}
+
+static size_t ext4_ext_space_block(struct ext4_inode_ref *inode_ref)
+{
+ size_t size;
+ uint32_t block_size = ext4_sb_get_block_size(&inode_ref->fs->sb);
+
+ size = (block_size - sizeof(struct ext4_extent_header)) /
+ sizeof(struct ext4_extent);
+#ifdef AGGRESSIVE_TEST
+ if (size > 6)
+ size = 6;
+#endif
+ return size;
+}
+
+static size_t ext4_ext_space_block_idx(struct ext4_inode_ref *inode_ref)
+{
+ size_t size;
+ uint32_t block_size = ext4_sb_get_block_size(&inode_ref->fs->sb);
+
+ size = (block_size - sizeof(struct ext4_extent_header)) /
+ sizeof(struct ext4_extent_index);
+#ifdef AGGRESSIVE_TEST
+ if (size > 5)
+ size = 5;
+#endif
+ return size;
+}
+
+static size_t ext4_ext_space_root(struct ext4_inode_ref *inode_ref)
+{
+ size_t size;
+
+ size = sizeof(inode_ref->inode->blocks);
+ size -= sizeof(struct ext4_extent_header);
+ size /= sizeof(struct ext4_extent);
+#ifdef AGGRESSIVE_TEST
+ if (size > 3)
+ size = 3;
+#endif
+ return size;
+}
+
+static size_t ext4_ext_space_root_idx(struct ext4_inode_ref *inode_ref)
+{
+ size_t size;
+
+ size = sizeof(inode_ref->inode->blocks);
+ size -= sizeof(struct ext4_extent_header);
+ size /= sizeof(struct ext4_extent_index);
+#ifdef AGGRESSIVE_TEST
+ if (size > 4)
+ size = 4;
+#endif
+ return size;
+}
+
+static size_t ext4_ext_max_entries(struct ext4_inode_ref *inode_ref,
+ uint32_t depth)
+{
+ size_t max;
+
+ if (depth == ext_depth(inode_ref->inode)) {
+ if (depth == 0)
+ max = ext4_ext_space_root(inode_ref);
+ else
+ max = ext4_ext_space_root_idx(inode_ref);
+ } else {
+ if (depth == 0)
+ max = ext4_ext_space_block(inode_ref);
+ else
+ max = ext4_ext_space_block_idx(inode_ref);
+ }
+
+ return max;
+}
+
+static ext4_fsblk_t ext4_ext_find_goal(struct ext4_inode_ref *inode_ref,
+ struct ext4_extent_path *path,
+ ext4_lblk_t block)
+{
+ if (path) {
+ uint32_t depth = path->depth;
+ struct ext4_extent *ex;
+
+ /*
+ * Try to predict block placement assuming that we are
+ * filling in a file which will eventually be
+ * non-sparse --- i.e., in the case of libbfd writing
+ * an ELF object sections out-of-order but in a way
+ * the eventually results in a contiguous object or
+ * executable file, or some database extending a table
+ * space file. However, this is actually somewhat
+ * non-ideal if we are writing a sparse file such as
+ * qemu or KVM writing a raw image file that is going
+ * to stay fairly sparse, since it will end up
+ * fragmenting the file system's free space. Maybe we
+ * should have some hueristics or some way to allow
+ * userspace to pass a hint to file system,
+ * especially if the latter case turns out to be
+ * common.
+ */
+ ex = path[depth].extent;
+ if (ex) {
+ ext4_fsblk_t ext_pblk = ext4_ext_pblock(ex);
+ ext4_lblk_t ext_block = to_le32(ex->first_block);
+
+ if (block > ext_block)
+ return ext_pblk + (block - ext_block);
+ else
+ return ext_pblk - (ext_block - block);
+ }
+
+ /* it looks like index is empty;
+ * try to find starting block from index itself */
+ if (path[depth].block.lb_id)
+ return path[depth].block.lb_id;
+ }
+
+ /* OK. use inode's group */
+ return ext4_fs_inode_to_goal_block(inode_ref);
+}
+
+/*
+ * Allocation for a meta data block
+ */
+static ext4_fsblk_t ext4_ext_new_meta_block(struct ext4_inode_ref *inode_ref,
+ struct ext4_extent_path *path,
+ struct ext4_extent *ex, int *err,
+ uint32_t flags)
+{
+ ext4_fsblk_t goal, newblock;
+
+ goal = ext4_ext_find_goal(inode_ref, path, to_le32(ex->first_block));
+ newblock = ext4_new_meta_blocks(inode_ref, goal, flags, NULL, err);
+ return newblock;
+}
+
+#if CONFIG_META_CSUM_ENABLE
+static uint32_t ext4_ext_block_csum(struct ext4_inode_ref *inode_ref,
+ struct ext4_extent_header *eh)
+{
+ uint32_t checksum = 0;
+ struct ext4_sblock *sb = &inode_ref->fs->sb;
+
+ if (ext4_sb_feature_ro_com(sb, EXT4_FRO_COM_METADATA_CSUM)) {
+ uint32_t ino_index = to_le32(inode_ref->index);
+ uint32_t ino_gen =
+ to_le32(ext4_inode_get_generation(inode_ref->inode));
+ /* First calculate crc32 checksum against fs uuid */
+ checksum = ext4_crc32c(EXT4_CRC32_INIT, sb->uuid,
+ sizeof(sb->uuid));
+ /* Then calculate crc32 checksum against inode number
+ * and inode generation */
+ checksum = ext4_crc32c(checksum, &ino_index,
+ sizeof(ino_index));
+ checksum = ext4_crc32c(checksum, &ino_gen,
+ sizeof(ino_gen));
+ /* Finally calculate crc32 checksum against
+ * the entire extent block up to the checksum field */
+ checksum = ext4_crc32c(checksum, eh,
+ EXT4_EXTENT_TAIL_OFFSET(eh));
+ }
+ return checksum;
+}
+#else
+#define ext4_ext_block_csum(...) 0
+#endif
+
+static void ext4_extent_block_csum_set(struct ext4_inode_ref *inode_ref __unused,
+ struct ext4_extent_header *eh)
+{
+ struct ext4_extent_tail *tail;
+
+ tail = find_ext4_extent_tail(eh);
+ tail->et_checksum = to_le32(ext4_ext_block_csum(inode_ref, eh));
+}
+
+static int ext4_ext_dirty(struct ext4_inode_ref *inode_ref,
+ struct ext4_extent_path *path)
+{
+ if (path->block.lb_id)
+ ext4_trans_set_block_dirty(path->block.buf);
+ else
+ inode_ref->dirty = true;
+
+ return EOK;
+}
+
+static void ext4_ext_drop_refs(struct ext4_inode_ref *inode_ref,
+ struct ext4_extent_path *path, bool keep_other)
+{
+ int32_t depth, i;
+
+ if (!path)
+ return;
+ if (keep_other)
+ depth = 0;
+ else
+ depth = path->depth;
+
+ for (i = 0; i <= depth; i++, path++) {
+ if (path->block.lb_id) {
+ if (ext4_bcache_test_flag(path->block.buf, BC_DIRTY))
+ ext4_extent_block_csum_set(inode_ref,
+ path->header);
+
+ ext4_block_set(inode_ref->fs->bdev, &path->block);
+ }
+ }
+}
+
+/*
+ * Check that whether the basic information inside the extent header
+ * is correct or not.
+ */
+static int ext4_ext_check(struct ext4_inode_ref *inode_ref,
+ struct ext4_extent_header *eh, uint16_t depth,
+ ext4_fsblk_t pblk __unused)
+{
+ struct ext4_extent_tail *tail;
+ struct ext4_sblock *sb = &inode_ref->fs->sb;
+ const char *error_msg;
+ (void)error_msg;
+
+ if (to_le16(eh->magic) != EXT4_EXTENT_MAGIC) {
+ error_msg = "invalid magic";
+ goto corrupted;
+ }
+ if (to_le16(eh->depth) != depth) {
+ error_msg = "unexpected eh_depth";
+ goto corrupted;
+ }
+ if (eh->max_entries_count == 0) {
+ error_msg = "invalid eh_max";
+ goto corrupted;
+ }
+ if (to_le16(eh->entries_count) > to_le16(eh->max_entries_count)) {
+ error_msg = "invalid eh_entries";
+ goto corrupted;
+ }
+
+ tail = find_ext4_extent_tail(eh);
+ if (ext4_sb_feature_ro_com(sb, EXT4_FRO_COM_METADATA_CSUM)) {
+ if (tail->et_checksum != to_le32(ext4_ext_block_csum(inode_ref, eh))) {
+ ext4_dbg(DEBUG_EXTENT,
+ DBG_WARN "Extent block checksum failed."
+ "Blocknr: %" PRIu64"\n",
+ pblk);
+
+ }
+ }
+
+ return EOK;
+
+corrupted:
+ ext4_dbg(DEBUG_EXTENT, "Bad extents B+ tree block: %s. "
+ "Blocknr: %" PRId64 "\n",
+ error_msg, pblk);
+ return EIO;
+}
+
+static int read_extent_tree_block(struct ext4_inode_ref *inode_ref,
+ ext4_fsblk_t pblk, int32_t depth,
+ struct ext4_block *bh,
+ uint32_t flags __unused)
+{
+ int err;
+
+ err = ext4_trans_block_get(inode_ref->fs->bdev, bh, pblk);
+ if (err != EOK)
+ goto errout;
+
+ err = ext4_ext_check(inode_ref, ext_block_hdr(bh), depth, pblk);
+ if (err != EOK)
+ goto errout;
+
+ return EOK;
+errout:
+ if (bh->lb_id)
+ ext4_block_set(inode_ref->fs->bdev, bh);
+
+ return err;
+}
+
+/*
+ * ext4_ext_binsearch_idx:
+ * binary search for the closest index of the given block
+ * the header must be checked before calling this
+ */
+static void ext4_ext_binsearch_idx(struct ext4_extent_path *path,
+ ext4_lblk_t block)
+{
+ struct ext4_extent_header *eh = path->header;
+ struct ext4_extent_index *r, *l, *m;
+
+ l = EXT_FIRST_INDEX(eh) + 1;
+ r = EXT_LAST_INDEX(eh);
+ while (l <= r) {
+ m = l + (r - l) / 2;
+ if (block < to_le32(m->first_block))
+ r = m - 1;
+ else
+ l = m + 1;
+ }
+
+ path->index = l - 1;
+}
+
+/*
+ * ext4_ext_binsearch:
+ * binary search for closest extent of the given block
+ * the header must be checked before calling this
+ */
+static void ext4_ext_binsearch(struct ext4_extent_path *path, ext4_lblk_t block)
+{
+ struct ext4_extent_header *eh = path->header;
+ struct ext4_extent *r, *l, *m;
+
+ if (eh->entries_count == 0) {
+ /*
+ * this leaf is empty:
+ * we get such a leaf in split/add case
+ */
+ return;
+ }
+
+ l = EXT_FIRST_EXTENT(eh) + 1;
+ r = EXT_LAST_EXTENT(eh);
+
+ while (l <= r) {
+ m = l + (r - l) / 2;
+ if (block < to_le32(m->first_block))
+ r = m - 1;
+ else
+ l = m + 1;
+ }
+
+ path->extent = l - 1;
+}
+
+static int ext4_find_extent(struct ext4_inode_ref *inode_ref, ext4_lblk_t block,
+ struct ext4_extent_path **orig_path, uint32_t flags)
+{
+ struct ext4_extent_header *eh;
+ struct ext4_block bh = EXT4_BLOCK_ZERO();
+ ext4_fsblk_t buf_block = 0;
+ struct ext4_extent_path *path = *orig_path;
+ int32_t depth, ppos = 0;
+ int32_t i;
+ int ret;
+
+ eh = ext_inode_hdr(inode_ref->inode);
+ depth = ext_depth(inode_ref->inode);
+
+ if (path) {
+ ext4_ext_drop_refs(inode_ref, path, 0);
+ if (depth > path[0].maxdepth) {
+ free(path);
+ *orig_path = path = NULL;
+ }
+ }
+ if (!path) {
+ int32_t path_depth = depth + 1;
+ /* account possible depth increase */
+ path = calloc(1, sizeof(struct ext4_extent_path) *
+ (path_depth + 1));
+ if (!path)
+ return ENOMEM;
+ path[0].maxdepth = path_depth;
+ }
+ path[0].header = eh;
+ path[0].block = bh;
+
+ i = depth;
+ /* walk through the tree */
+ while (i) {
+ ext4_ext_binsearch_idx(path + ppos, block);
+ path[ppos].p_block = ext4_idx_pblock(path[ppos].index);
+ path[ppos].depth = i;
+ path[ppos].extent = NULL;
+ buf_block = path[ppos].p_block;
+
+ i--;
+ ppos++;
+ if (!path[ppos].block.lb_id ||
+ path[ppos].block.lb_id != buf_block) {
+ ret = read_extent_tree_block(inode_ref, buf_block, i,
+ &bh, flags);
+ if (ret != EOK) {
+ goto err;
+ }
+ if (ppos > depth) {
+ ext4_block_set(inode_ref->fs->bdev, &bh);
+ ret = EIO;
+ goto err;
+ }
+
+ eh = ext_block_hdr(&bh);
+ path[ppos].block = bh;
+ path[ppos].header = eh;
+ }
+ }
+
+ path[ppos].depth = i;
+ path[ppos].extent = NULL;
+ path[ppos].index = NULL;
+
+ /* find extent */
+ ext4_ext_binsearch(path + ppos, block);
+ /* if not an empty leaf */
+ if (path[ppos].extent)
+ path[ppos].p_block = ext4_ext_pblock(path[ppos].extent);
+
+ *orig_path = path;
+
+ ret = EOK;
+ return ret;
+
+err:
+ ext4_ext_drop_refs(inode_ref, path, 0);
+ free(path);
+ if (orig_path)
+ *orig_path = NULL;
+ return ret;
+}
+
+static void ext4_ext_init_header(struct ext4_inode_ref *inode_ref,
+ struct ext4_extent_header *eh, int32_t depth)
+{
+ eh->entries_count = 0;
+ eh->max_entries_count = to_le16(ext4_ext_max_entries(inode_ref, depth));
+ eh->magic = to_le16(EXT4_EXTENT_MAGIC);
+ eh->depth = depth;
+}
+
+/*
+ * Be cautious, the buffer_head returned is not yet mark dirtied. */
+static int ext4_ext_split_node(struct ext4_inode_ref *inode_ref,
+ struct ext4_extent_path *path, int32_t at,
+ struct ext4_extent *newext,
+ ext4_fsblk_t *sibling, struct ext4_block *new_bh)
+{
+ int ret;
+ ext4_fsblk_t newblock;
+ struct ext4_block bh = EXT4_BLOCK_ZERO();
+ int32_t depth = ext_depth(inode_ref->inode);
+
+ ext4_assert(sibling);
+
+ /* FIXME: currently we split at the point after the current extent. */
+ newblock = ext4_ext_new_meta_block(inode_ref, path, newext, &ret, 0);
+ if (ret)
+ goto cleanup;
+
+ /* For write access.# */
+ ret = ext4_trans_block_get_noread(inode_ref->fs->bdev, &bh, newblock);
+ if (ret != EOK)
+ goto cleanup;
+
+ if (at == depth) {
+ /* start copy from next extent */
+ ptrdiff_t m = EXT_MAX_EXTENT(path[at].header) - path[at].extent;
+ struct ext4_extent_header *neh;
+ neh = ext_block_hdr(&bh);
+ ext4_ext_init_header(inode_ref, neh, 0);
+ if (m) {
+ struct ext4_extent *ex;
+ ex = EXT_FIRST_EXTENT(neh);
+ memmove(ex, path[at].extent + 1,
+ sizeof(struct ext4_extent) * m);
+ neh->entries_count =
+ to_le16(to_le16(neh->entries_count) + m);
+ path[at].header->entries_count = to_le16(
+ to_le16(path[at].header->entries_count) - m);
+ ret = ext4_ext_dirty(inode_ref, path + at);
+ if (ret)
+ goto cleanup;
+ }
+ } else {
+ ptrdiff_t m = EXT_MAX_INDEX(path[at].header) - path[at].index;
+ struct ext4_extent_header *neh;
+ neh = ext_block_hdr(&bh);
+ ext4_ext_init_header(inode_ref, neh, depth - at);
+ if (m) {
+ struct ext4_extent_index *ix;
+ ix = EXT_FIRST_INDEX(neh);
+ memmove(ix, path[at].index + 1,
+ sizeof(struct ext4_extent) * m);
+ neh->entries_count =
+ to_le16(to_le16(neh->entries_count) + m);
+ path[at].header->entries_count = to_le16(
+ to_le16(path[at].header->entries_count) - m);
+ ret = ext4_ext_dirty(inode_ref, path + at);
+ if (ret)
+ goto cleanup;
+ }
+ }
+cleanup:
+ if (ret) {
+ if (bh.lb_id) {
+ ext4_block_set(inode_ref->fs->bdev, &bh);
+ }
+ if (newblock)
+ ext4_ext_free_blocks(inode_ref, newblock, 1, 0);
+
+ newblock = 0;
+ }
+ *sibling = newblock;
+ *new_bh = bh;
+ return ret;
+}
+
+static ext4_lblk_t ext4_ext_block_index(struct ext4_extent_header *eh)
+{
+ if (eh->depth)
+ return to_le32(EXT_FIRST_INDEX(eh)->first_block);
+
+ return to_le32(EXT_FIRST_EXTENT(eh)->first_block);
+}
+
+struct ext_split_trans {
+ ext4_fsblk_t ptr;
+ struct ext4_extent_path path;
+ int switch_to;
+};
+
+static int ext4_ext_insert_index(struct ext4_inode_ref *inode_ref,
+ struct ext4_extent_path *path,
+ int32_t at,
+ struct ext4_extent *newext,
+ ext4_lblk_t insert_index,
+ ext4_fsblk_t insert_block,
+ struct ext_split_trans *spt,
+ bool *need_grow)
+{
+ struct ext4_extent_index *ix;
+ struct ext4_extent_path *curp = path + at;
+ struct ext4_block bh = EXT4_BLOCK_ZERO();
+ int32_t len;
+ int err;
+ struct ext4_extent_header *eh;
+
+ *need_grow = false;
+
+ if (curp->index && insert_index == to_le32(curp->index->first_block))
+ return EIO;
+
+ if (to_le16(curp->header->entries_count) ==
+ to_le16(curp->header->max_entries_count)) {
+ if (at) {
+ struct ext4_extent_header *neh;
+ err = ext4_ext_split_node(inode_ref, path, at, newext,
+ &spt->ptr, &bh);
+ if (err != EOK)
+ goto out;
+
+ neh = ext_block_hdr(&bh);
+ if (insert_index > to_le32(curp->index->first_block)) {
+ /* Make decision which node should be used to
+ * insert the index.*/
+ if (to_le16(neh->entries_count) >
+ to_le16(curp->header->entries_count)) {
+ eh = curp->header;
+ /* insert after */
+ ix = EXT_LAST_INDEX(eh) + 1;
+ } else {
+ eh = neh;
+ ix = EXT_FIRST_INDEX(eh);
+ }
+ } else {
+ eh = curp->header;
+ /* insert before */
+ ix = EXT_LAST_INDEX(eh);
+ }
+ } else {
+ err = EOK;
+ *need_grow = true;
+ goto out;
+ }
+ } else {
+ eh = curp->header;
+ if (curp->index == NULL) {
+ ix = EXT_FIRST_INDEX(eh);
+ curp->index = ix;
+ } else if (insert_index > to_le32(curp->index->first_block)) {
+ /* insert after */
+ ix = curp->index + 1;
+ } else {
+ /* insert before */
+ ix = curp->index;
+ }
+ }
+
+ len = EXT_LAST_INDEX(eh) - ix + 1;
+ ext4_assert(len >= 0);
+ if (len > 0)
+ memmove(ix + 1, ix, len * sizeof(struct ext4_extent_index));
+
+ if (ix > EXT_MAX_INDEX(eh)) {
+ err = EIO;
+ goto out;
+ }
+
+ ix->first_block = to_le32(insert_index);
+ ext4_idx_store_pblock(ix, insert_block);
+ eh->entries_count = to_le16(to_le16(eh->entries_count) + 1);
+
+ if (ix > EXT_LAST_INDEX(eh)) {
+ err = EIO;
+ goto out;
+ }
+
+ if (eh == curp->header)
+ err = ext4_ext_dirty(inode_ref, curp);
+ else
+ err = EOK;
+
+out:
+ if (err != EOK || *need_grow) {
+ if (bh.lb_id)
+ ext4_block_set(inode_ref->fs->bdev, &bh);
+
+ spt->ptr = 0;
+ } else if (bh.lb_id) {
+ /* If we got a sibling leaf. */
+ ext4_extent_block_csum_set(inode_ref, ext_block_hdr(&bh));
+ ext4_trans_set_block_dirty(bh.buf);
+
+ spt->path.p_block = ext4_idx_pblock(ix);
+ spt->path.depth = to_le16(eh->depth);
+ spt->path.maxdepth = 0;
+ spt->path.extent = NULL;
+ spt->path.index = ix;
+ spt->path.header = eh;
+ spt->path.block = bh;
+
+ /*
+ * If newext->ee_block can be included into the
+ * right sub-tree.
+ */
+ if (to_le32(newext->first_block) >=
+ ext4_ext_block_index(ext_block_hdr(&bh)))
+ spt->switch_to = 1;
+ else {
+ curp->index = ix;
+ curp->p_block = ext4_idx_pblock(ix);
+ }
+
+ } else {
+ spt->ptr = 0;
+ curp->index = ix;
+ curp->p_block = ext4_idx_pblock(ix);
+ }
+ return err;
+}
+
+/*
+ * ext4_ext_correct_indexes:
+ * if leaf gets modified and modified extent is first in the leaf,
+ * then we have to correct all indexes above.
+ */
+static int ext4_ext_correct_indexes(struct ext4_inode_ref *inode_ref,
+ struct ext4_extent_path *path)
+{
+ struct ext4_extent_header *eh;
+ int32_t depth = ext_depth(inode_ref->inode);
+ struct ext4_extent *ex;
+ uint32_t border;
+ int32_t k;
+ int err = EOK;
+
+ eh = path[depth].header;
+ ex = path[depth].extent;
+
+ if (ex == NULL || eh == NULL)
+ return EIO;
+
+ if (depth == 0) {
+ /* there is no tree at all */
+ return EOK;
+ }
+
+ if (ex != EXT_FIRST_EXTENT(eh)) {
+ /* we correct tree if first leaf got modified only */
+ return EOK;
+ }
+
+ k = depth - 1;
+ border = path[depth].extent->first_block;
+ path[k].index->first_block = border;
+ err = ext4_ext_dirty(inode_ref, path + k);
+ if (err != EOK)
+ return err;
+
+ while (k--) {
+ /* change all left-side indexes */
+ if (path[k + 1].index != EXT_FIRST_INDEX(path[k + 1].header))
+ break;
+ path[k].index->first_block = border;
+ err = ext4_ext_dirty(inode_ref, path + k);
+ if (err != EOK)
+ break;
+ }
+
+ return err;
+}
+
+static bool ext4_ext_can_prepend(struct ext4_extent *ex1,
+ struct ext4_extent *ex2)
+{
+ if (ext4_ext_pblock(ex2) + ext4_ext_get_actual_len(ex2) !=
+ ext4_ext_pblock(ex1))
+ return false;
+
+#ifdef AGGRESSIVE_TEST
+ if (ext4_ext_get_actual_len(ex1) + ext4_ext_get_actual_len(ex2) > 4)
+ return 0;
+#else
+ if (ext4_ext_is_unwritten(ex1)) {
+ if (ext4_ext_get_actual_len(ex1) +
+ ext4_ext_get_actual_len(ex2) >
+ EXT_UNWRITTEN_MAX_LEN)
+ return false;
+ } else if (ext4_ext_get_actual_len(ex1) + ext4_ext_get_actual_len(ex2) >
+ EXT_INIT_MAX_LEN)
+ return false;
+#endif
+
+ if (to_le32(ex2->first_block) + ext4_ext_get_actual_len(ex2) !=
+ to_le32(ex1->first_block))
+ return false;
+
+ return true;
+}
+
+static bool ext4_ext_can_append(struct ext4_extent *ex1,
+ struct ext4_extent *ex2)
+{
+ if (ext4_ext_pblock(ex1) + ext4_ext_get_actual_len(ex1) !=
+ ext4_ext_pblock(ex2))
+ return false;
+
+#ifdef AGGRESSIVE_TEST
+ if (ext4_ext_get_actual_len(ex1) + ext4_ext_get_actual_len(ex2) > 4)
+ return 0;
+#else
+ if (ext4_ext_is_unwritten(ex1)) {
+ if (ext4_ext_get_actual_len(ex1) +
+ ext4_ext_get_actual_len(ex2) >
+ EXT_UNWRITTEN_MAX_LEN)
+ return false;
+ } else if (ext4_ext_get_actual_len(ex1) + ext4_ext_get_actual_len(ex2) >
+ EXT_INIT_MAX_LEN)
+ return false;
+#endif
+
+ if (to_le32(ex1->first_block) + ext4_ext_get_actual_len(ex1) !=
+ to_le32(ex2->first_block))
+ return false;
+
+ return true;
+}
+
+static int ext4_ext_insert_leaf(struct ext4_inode_ref *inode_ref,
+ struct ext4_extent_path *path,
+ int32_t at,
+ struct ext4_extent *newext,
+ struct ext_split_trans *spt,
+ uint32_t flags,
+ bool *need_grow)
+{
+ struct ext4_extent_path *curp = path + at;
+ struct ext4_extent *ex = curp->extent;
+ struct ext4_block bh = EXT4_BLOCK_ZERO();
+ int32_t len;
+ int err = EOK;
+ int unwritten;
+ struct ext4_extent_header *eh = NULL;
+
+ *need_grow = false;
+
+ if (curp->extent &&
+ to_le32(newext->first_block) == to_le32(curp->extent->first_block))
+ return EIO;
+
+ if (!(flags & EXT4_EXT_NO_COMBINE)) {
+ if (curp->extent && ext4_ext_can_append(curp->extent, newext)) {
+ unwritten = ext4_ext_is_unwritten(curp->extent);
+ curp->extent->block_count =
+ to_le16(ext4_ext_get_actual_len(curp->extent) +
+ ext4_ext_get_actual_len(newext));
+ if (unwritten)
+ ext4_ext_mark_unwritten(curp->extent);
+ err = ext4_ext_dirty(inode_ref, curp);
+ goto out;
+ }
+
+ if (curp->extent &&
+ ext4_ext_can_prepend(curp->extent, newext)) {
+ unwritten = ext4_ext_is_unwritten(curp->extent);
+ curp->extent->first_block = newext->first_block;
+ curp->extent->block_count =
+ to_le16(ext4_ext_get_actual_len(curp->extent) +
+ ext4_ext_get_actual_len(newext));
+ if (unwritten)
+ ext4_ext_mark_unwritten(curp->extent);
+ err = ext4_ext_dirty(inode_ref, curp);
+ goto out;
+ }
+ }
+
+ if (to_le16(curp->header->entries_count) ==
+ to_le16(curp->header->max_entries_count)) {
+ if (at) {
+ struct ext4_extent_header *neh;
+ err = ext4_ext_split_node(inode_ref, path, at, newext,
+ &spt->ptr, &bh);
+ if (err != EOK)
+ goto out;
+
+ neh = ext_block_hdr(&bh);
+ if (to_le32(newext->first_block) >
+ to_le32(curp->extent->first_block)) {
+ if (to_le16(neh->entries_count) >
+ to_le16(curp->header->entries_count)) {
+ eh = curp->header;
+ /* insert after */
+ ex = EXT_LAST_EXTENT(eh) + 1;
+ } else {
+ eh = neh;
+ ex = EXT_FIRST_EXTENT(eh);
+ }
+ } else {
+ eh = curp->header;
+ /* insert before */
+ ex = EXT_LAST_EXTENT(eh);
+ }
+ } else {
+ err = EOK;
+ *need_grow = true;
+ goto out;
+ }
+ } else {
+ eh = curp->header;
+ if (curp->extent == NULL) {
+ ex = EXT_FIRST_EXTENT(eh);
+ curp->extent = ex;
+ } else if (to_le32(newext->first_block) >
+ to_le32(curp->extent->first_block)) {
+ /* insert after */
+ ex = curp->extent + 1;
+ } else {
+ /* insert before */
+ ex = curp->extent;
+ }
+ }
+
+ len = EXT_LAST_EXTENT(eh) - ex + 1;
+ ext4_assert(len >= 0);
+ if (len > 0)
+ memmove(ex + 1, ex, len * sizeof(struct ext4_extent));
+
+ if (ex > EXT_MAX_EXTENT(eh)) {
+ err = EIO;
+ goto out;
+ }
+
+ ex->first_block = newext->first_block;
+ ex->block_count = newext->block_count;
+ ext4_ext_store_pblock(ex, ext4_ext_pblock(newext));
+ eh->entries_count = to_le16(to_le16(eh->entries_count) + 1);
+
+ if (ex > EXT_LAST_EXTENT(eh)) {
+ err = EIO;
+ goto out;
+ }
+
+ if (eh == curp->header) {
+ err = ext4_ext_correct_indexes(inode_ref, path);
+ if (err != EOK)
+ goto out;
+ err = ext4_ext_dirty(inode_ref, curp);
+ } else
+ err = EOK;
+
+out:
+ if (err != EOK || *need_grow) {
+ if (bh.lb_id)
+ ext4_block_set(inode_ref->fs->bdev, &bh);
+
+ spt->ptr = 0;
+ } else if (bh.lb_id) {
+ /* If we got a sibling leaf. */
+ ext4_extent_block_csum_set(inode_ref, ext_block_hdr(&bh));
+ ext4_trans_set_block_dirty(bh.buf);
+
+ spt->path.p_block = ext4_ext_pblock(ex);
+ spt->path.depth = to_le16(eh->depth);
+ spt->path.maxdepth = 0;
+ spt->path.extent = ex;
+ spt->path.index = NULL;
+ spt->path.header = eh;
+ spt->path.block = bh;
+
+ /*
+ * If newext->ee_block can be included into the
+ * right sub-tree.
+ */
+ if (to_le32(newext->first_block) >=
+ ext4_ext_block_index(ext_block_hdr(&bh)))
+ spt->switch_to = 1;
+ else {
+ curp->extent = ex;
+ curp->p_block = ext4_ext_pblock(ex);
+ }
+
+ } else {
+ spt->ptr = 0;
+ curp->extent = ex;
+ curp->p_block = ext4_ext_pblock(ex);
+ }
+
+ return err;
+}
+
+/*
+ * ext4_ext_grow_indepth:
+ * implements tree growing procedure:
+ * - allocates new block
+ * - moves top-level data (index block or leaf) into the new block
+ * - initializes new top-level, creating index that points to the
+ * just created block
+ */
+static int ext4_ext_grow_indepth(struct ext4_inode_ref *inode_ref,
+ uint32_t flags)
+{
+ struct ext4_extent_header *neh;
+ struct ext4_block bh = EXT4_BLOCK_ZERO();
+ ext4_fsblk_t newblock, goal = 0;
+ int err = EOK;
+
+ /* Try to prepend new index to old one */
+ if (ext_depth(inode_ref->inode))
+ goal = ext4_idx_pblock(
+ EXT_FIRST_INDEX(ext_inode_hdr(inode_ref->inode)));
+ else
+ goal = ext4_fs_inode_to_goal_block(inode_ref);
+
+ newblock = ext4_new_meta_blocks(inode_ref, goal, flags, NULL, &err);
+ if (newblock == 0)
+ return err;
+
+ /* # */
+ err = ext4_trans_block_get_noread(inode_ref->fs->bdev, &bh, newblock);
+ if (err != EOK) {
+ ext4_ext_free_blocks(inode_ref, newblock, 1, 0);
+ return err;
+ }
+
+ /* move top-level index/leaf into new block */
+ memmove(bh.data, inode_ref->inode->blocks,
+ sizeof(inode_ref->inode->blocks));
+
+ /* set size of new block */
+ neh = ext_block_hdr(&bh);
+ /* old root could have indexes or leaves
+ * so calculate e_max right way */
+ if (ext_depth(inode_ref->inode))
+ neh->max_entries_count =
+ to_le16(ext4_ext_space_block_idx(inode_ref));
+ else
+ neh->max_entries_count =
+ to_le16(ext4_ext_space_block(inode_ref));
+
+ neh->magic = to_le16(EXT4_EXTENT_MAGIC);
+ ext4_extent_block_csum_set(inode_ref, neh);
+
+ /* Update top-level index: num,max,pointer */
+ neh = ext_inode_hdr(inode_ref->inode);
+ neh->entries_count = to_le16(1);
+ ext4_idx_store_pblock(EXT_FIRST_INDEX(neh), newblock);
+ if (neh->depth == 0) {
+ /* Root extent block becomes index block */
+ neh->max_entries_count =
+ to_le16(ext4_ext_space_root_idx(inode_ref));
+ EXT_FIRST_INDEX(neh)
+ ->first_block = EXT_FIRST_EXTENT(neh)->first_block;
+ }
+ neh->depth = to_le16(to_le16(neh->depth) + 1);
+
+ ext4_trans_set_block_dirty(bh.buf);
+ inode_ref->dirty = true;
+ ext4_block_set(inode_ref->fs->bdev, &bh);
+
+ return err;
+}
+
+__unused static void print_path(struct ext4_extent_path *path)
+{
+ int32_t i = path->depth;
+ while (i >= 0) {
+
+ ptrdiff_t a =
+ (path->extent)
+ ? (path->extent - EXT_FIRST_EXTENT(path->header))
+ : 0;
+ ptrdiff_t b =
+ (path->index)
+ ? (path->index - EXT_FIRST_INDEX(path->header))
+ : 0;
+
+ (void)a;
+ (void)b;
+ ext4_dbg(DEBUG_EXTENT,
+ "depth %" PRId32 ", p_block: %" PRIu64 ","
+ "p_ext offset: %td, p_idx offset: %td\n",
+ i, path->p_block, a, b);
+ i--;
+ path++;
+ }
+}
+
+static void ext4_ext_replace_path(struct ext4_inode_ref *inode_ref,
+ struct ext4_extent_path *path,
+ struct ext_split_trans *spt,
+ int32_t level)
+{
+ int32_t depth = ext_depth(inode_ref->inode);
+ int32_t i = depth - level;
+ ext4_ext_drop_refs(inode_ref, path + i, 1);
+ path[i] = spt[level].path;
+}
+
+static int ext4_ext_insert_extent(struct ext4_inode_ref *inode_ref,
+ struct ext4_extent_path **ppath,
+ struct ext4_extent *newext, uint32_t flags)
+{
+ int32_t i, depth, level;
+ int ret = EOK;
+ ext4_fsblk_t ptr = 0;
+ bool need_grow = false;
+ struct ext4_extent_path *path = *ppath;
+ struct ext_split_trans *spt = NULL;
+ struct ext_split_trans newblock;
+
+ memset(&newblock, 0, sizeof(newblock));
+
+ depth = ext_depth(inode_ref->inode);
+ for (i = depth, level = 0; i >= 0; i--, level++)
+ if (EXT_HAS_FREE_INDEX(path + i))
+ break;
+
+ if (level) {
+ spt = calloc(1, sizeof(struct ext_split_trans) * (level));
+ if (!spt) {
+ ret = ENOMEM;
+ goto out;
+ }
+ }
+ i = 0;
+again:
+ depth = ext_depth(inode_ref->inode);
+
+ do {
+ if (!i) {
+ ret = ext4_ext_insert_leaf(inode_ref, path, depth - i,
+ newext, &newblock, flags,
+ &need_grow);
+ } else {
+ ret = ext4_ext_insert_index(
+ inode_ref, path, depth - i, newext,
+ ext4_ext_block_index(
+ ext_block_hdr(&spt[i - 1].path.block)),
+ spt[i - 1].ptr, &newblock,
+ &need_grow);
+ }
+ ptr = newblock.ptr;
+
+ if (ret != EOK)
+ goto out;
+
+ else if (spt && ptr && !ret) {
+ /* Prepare for the next iteration after splitting. */
+ spt[i] = newblock;
+ }
+
+ i++;
+ } while (ptr != 0 && i <= depth);
+
+ if (need_grow) {
+ ret = ext4_ext_grow_indepth(inode_ref, 0);
+ if (ret)
+ goto out;
+ ret = ext4_find_extent(inode_ref, to_le32(newext->first_block),
+ ppath, 0);
+ if (ret)
+ goto out;
+ i = depth;
+ path = *ppath;
+ goto again;
+ }
+out:
+ if (ret) {
+ if (path)
+ ext4_ext_drop_refs(inode_ref, path, 0);
+
+ while (--level >= 0 && spt) {
+ if (spt[level].ptr) {
+ ext4_ext_free_blocks(inode_ref, spt[level].ptr,
+ 1, 0);
+ ext4_ext_drop_refs(inode_ref, &spt[level].path,
+ 1);
+ }
+ }
+ } else {
+ while (--level >= 0 && spt) {
+ if (spt[level].switch_to)
+ ext4_ext_replace_path(inode_ref, path, spt,
+ level);
+ else if (spt[level].ptr)
+ ext4_ext_drop_refs(inode_ref, &spt[level].path,
+ 1);
+ }
+ }
+ if (spt)
+ free(spt);
+
+ return ret;
+}
+
+static void ext4_ext_remove_blocks(struct ext4_inode_ref *inode_ref,
+ struct ext4_extent *ex, ext4_lblk_t from,
+ ext4_lblk_t to)
+{
+ ext4_lblk_t len = to - from + 1;
+ ext4_lblk_t num;
+ ext4_fsblk_t start;
+ num = from - to_le32(ex->first_block);
+ start = ext4_ext_pblock(ex) + num;
+ ext4_dbg(DEBUG_EXTENT,
+ "Freeing %" PRIu32 " at %" PRIu64 ", %" PRIu32 "\n", from,
+ start, len);
+
+ ext4_ext_free_blocks(inode_ref, start, len, 0);
+}
+
+static int ext4_ext_remove_idx(struct ext4_inode_ref *inode_ref,
+ struct ext4_extent_path *path, int32_t depth)
+{
+ int err = EOK;
+ int32_t i = depth;
+ ext4_fsblk_t leaf;
+
+ /* free index block */
+ leaf = ext4_idx_pblock(path[i].index);
+
+ if (path[i].index != EXT_LAST_INDEX(path[i].header)) {
+ ptrdiff_t len = EXT_LAST_INDEX(path[i].header) - path[i].index;
+ memmove(path[i].index, path[i].index + 1,
+ len * sizeof(struct ext4_extent_index));
+ }
+
+ path[i].header->entries_count =
+ to_le16(to_le16(path[i].header->entries_count) - 1);
+ err = ext4_ext_dirty(inode_ref, path + i);
+ if (err != EOK)
+ return err;
+
+ ext4_dbg(DEBUG_EXTENT, "IDX: Freeing %" PRIu32 " at %" PRIu64 ", %d\n",
+ to_le32(path[i].index->first_block), leaf, 1);
+ ext4_ext_free_blocks(inode_ref, leaf, 1, 0);
+
+ while (i > 0) {
+ if (path[i].index != EXT_FIRST_INDEX(path[i].header))
+ break;
+
+ path[i - 1].index->first_block = path[i].index->first_block;
+ err = ext4_ext_dirty(inode_ref, path + i - 1);
+ if (err != EOK)
+ break;
+
+ i--;
+ }
+ return err;
+}
+
+static int ext4_ext_remove_leaf(struct ext4_inode_ref *inode_ref,
+ struct ext4_extent_path *path, ext4_lblk_t from,
+ ext4_lblk_t to)
+{
+
+ int32_t depth = ext_depth(inode_ref->inode);
+ struct ext4_extent *ex = path[depth].extent;
+ struct ext4_extent *start_ex, *ex2 = NULL;
+ struct ext4_extent_header *eh = path[depth].header;
+ int32_t len;
+ int err = EOK;
+ uint16_t new_entries;
+
+ start_ex = ex;
+ new_entries = to_le16(eh->entries_count);
+ while (ex <= EXT_LAST_EXTENT(path[depth].header) &&
+ to_le32(ex->first_block) <= to) {
+ int32_t new_len = 0;
+ int unwritten;
+ ext4_lblk_t start, new_start;
+ ext4_fsblk_t newblock;
+ new_start = start = to_le32(ex->first_block);
+ len = ext4_ext_get_actual_len(ex);
+ newblock = ext4_ext_pblock(ex);
+ if (start < from) {
+ len -= from - start;
+ new_len = from - start;
+ start = from;
+ start_ex++;
+ } else {
+ if (start + len - 1 > to) {
+ len -= start + len - 1 - to;
+ new_len = start + len - 1 - to;
+ new_start = to + 1;
+ newblock += to + 1 - start;
+ ex2 = ex;
+ }
+ }
+
+ ext4_ext_remove_blocks(inode_ref, ex, start, start + len - 1);
+ ex->first_block = to_le32(new_start);
+ if (!new_len)
+ new_entries--;
+ else {
+ unwritten = ext4_ext_is_unwritten(ex);
+ ex->block_count = to_le16(new_len);
+ ext4_ext_store_pblock(ex, newblock);
+ if (unwritten)
+ ext4_ext_mark_unwritten(ex);
+ }
+
+ ex += 1;
+ }
+
+ if (ex2 == NULL)
+ ex2 = ex;
+
+ if (ex2 <= EXT_LAST_EXTENT(eh))
+ memmove(start_ex, ex2, EXT_LAST_EXTENT(eh) - ex2 + 1);
+
+ eh->entries_count = to_le16(new_entries);
+ ext4_ext_dirty(inode_ref, path + depth);
+ if (path[depth].extent == EXT_FIRST_EXTENT(eh) && eh->entries_count)
+ err = ext4_ext_correct_indexes(inode_ref, path);
+
+ /* if this leaf is free, then we should
+ * remove it from index block above */
+ if (err == EOK && eh->entries_count == 0 && path[depth].block.lb_id)
+ err = ext4_ext_remove_idx(inode_ref, path, depth - 1);
+ else if (depth > 0)
+ path[depth - 1].index++;
+
+ return err;
+}
+
+static bool ext4_ext_more_to_rm(struct ext4_extent_path *path, ext4_lblk_t to)
+{
+ if (!to_le16(path->header->entries_count))
+ return false;
+
+ if (path->index > EXT_LAST_INDEX(path->header))
+ return false;
+
+ if (to_le32(path->index->first_block) > to)
+ return false;
+
+ return true;
+}
+
+int ext4_extent_remove_space(struct ext4_inode_ref *inode_ref, ext4_lblk_t from,
+ ext4_lblk_t to)
+{
+ struct ext4_extent_path *path = NULL;
+ int ret = EOK;
+ int32_t depth = ext_depth(inode_ref->inode);
+ int32_t i;
+
+ ret = ext4_find_extent(inode_ref, from, &path, 0);
+ if (ret)
+ goto out;
+
+ if (!path[depth].extent) {
+ ret = EOK;
+ goto out;
+ }
+
+ bool in_range = IN_RANGE(from, to_le32(path[depth].extent->first_block),
+ ext4_ext_get_actual_len(path[depth].extent));
+
+ if (!in_range) {
+ ret = EOK;
+ goto out;
+ }
+
+ /* If we do remove_space inside the range of an extent */
+ if ((to_le32(path[depth].extent->first_block) < from) &&
+ (to < to_le32(path[depth].extent->first_block) +
+ ext4_ext_get_actual_len(path[depth].extent) - 1)) {
+
+ struct ext4_extent *ex = path[depth].extent, newex;
+ int unwritten = ext4_ext_is_unwritten(ex);
+ ext4_lblk_t ee_block = to_le32(ex->first_block);
+ int32_t len = ext4_ext_get_actual_len(ex);
+ ext4_fsblk_t newblock =
+ to + 1 - ee_block + ext4_ext_pblock(ex);
+
+ ex->block_count = to_le16(from - ee_block);
+ if (unwritten)
+ ext4_ext_mark_unwritten(ex);
+
+ ext4_ext_dirty(inode_ref, path + depth);
+
+ newex.first_block = to_le32(to + 1);
+ newex.block_count = to_le16(ee_block + len - 1 - to);
+ ext4_ext_store_pblock(&newex, newblock);
+ if (unwritten)
+ ext4_ext_mark_unwritten(&newex);
+
+ ret = ext4_ext_insert_extent(inode_ref, &path, &newex, 0);
+ goto out;
+ }
+
+ i = depth;
+ while (i >= 0) {
+ if (i == depth) {
+ struct ext4_extent_header *eh;
+ struct ext4_extent *first_ex, *last_ex;
+ ext4_lblk_t leaf_from, leaf_to;
+ eh = path[i].header;
+ ext4_assert(to_le16(eh->entries_count) > 0);
+ first_ex = EXT_FIRST_EXTENT(eh);
+ last_ex = EXT_LAST_EXTENT(eh);
+ leaf_from = to_le32(first_ex->first_block);
+ leaf_to = to_le32(last_ex->first_block) +
+ ext4_ext_get_actual_len(last_ex) - 1;
+ if (leaf_from < from)
+ leaf_from = from;
+
+ if (leaf_to > to)
+ leaf_to = to;
+
+ ext4_ext_remove_leaf(inode_ref, path, leaf_from,
+ leaf_to);
+ ext4_ext_drop_refs(inode_ref, path + i, 0);
+ i--;
+ continue;
+ }
+
+ struct ext4_extent_header *eh;
+ eh = path[i].header;
+ if (ext4_ext_more_to_rm(path + i, to)) {
+ struct ext4_block bh = EXT4_BLOCK_ZERO();
+ if (path[i + 1].block.lb_id)
+ ext4_ext_drop_refs(inode_ref, path + i + 1, 0);
+
+ ret = read_extent_tree_block(inode_ref,
+ ext4_idx_pblock(path[i].index),
+ depth - i - 1, &bh, 0);
+ if (ret)
+ goto out;
+
+ path[i].p_block =
+ ext4_idx_pblock(path[i].index);
+ path[i + 1].block = bh;
+ path[i + 1].header = ext_block_hdr(&bh);
+ path[i + 1].depth = depth - i - 1;
+ if (i + 1 == depth)
+ path[i + 1].extent = EXT_FIRST_EXTENT(
+ path[i + 1].header);
+ else
+ path[i + 1].index =
+ EXT_FIRST_INDEX(path[i + 1].header);
+
+ i++;
+ } else {
+ if (i > 0) {
+ if (!eh->entries_count)
+ ret = ext4_ext_remove_idx(inode_ref, path,
+ i - 1);
+ else
+ path[i - 1].index++;
+
+ }
+
+ if (i)
+ ext4_block_set(inode_ref->fs->bdev,
+ &path[i].block);
+
+
+ i--;
+ }
+
+ }
+
+ /* TODO: flexible tree reduction should be here */
+ if (path->header->entries_count == 0) {
+ /*
+ * truncate to zero freed all the tree,
+ * so we need to correct eh_depth
+ */
+ ext_inode_hdr(inode_ref->inode)->depth = 0;
+ ext_inode_hdr(inode_ref->inode)->max_entries_count =
+ to_le16(ext4_ext_space_root(inode_ref));
+ ret = ext4_ext_dirty(inode_ref, path);
+ }
+
+out:
+ ext4_ext_drop_refs(inode_ref, path, 0);
+ free(path);
+ path = NULL;
+ return ret;
+}
+
+static int ext4_ext_split_extent_at(struct ext4_inode_ref *inode_ref,
+ struct ext4_extent_path **ppath,
+ ext4_lblk_t split, uint32_t split_flag)
+{
+ struct ext4_extent *ex, newex;
+ ext4_fsblk_t newblock;
+ ext4_lblk_t ee_block;
+ int32_t ee_len;
+ int32_t depth = ext_depth(inode_ref->inode);
+ int err = EOK;
+
+ ex = (*ppath)[depth].extent;
+ ee_block = to_le32(ex->first_block);
+ ee_len = ext4_ext_get_actual_len(ex);
+ newblock = split - ee_block + ext4_ext_pblock(ex);
+
+ if (split == ee_block) {
+ /*
+ * case b: block @split is the block that the extent begins with
+ * then we just change the state of the extent, and splitting
+ * is not needed.
+ */
+ if (split_flag & EXT4_EXT_MARK_UNWRIT2)
+ ext4_ext_mark_unwritten(ex);
+ else
+ ext4_ext_mark_initialized(ex);
+
+ err = ext4_ext_dirty(inode_ref, *ppath + depth);
+ goto out;
+ }
+
+ ex->block_count = to_le16(split - ee_block);
+ if (split_flag & EXT4_EXT_MARK_UNWRIT1)
+ ext4_ext_mark_unwritten(ex);
+
+ err = ext4_ext_dirty(inode_ref, *ppath + depth);
+ if (err != EOK)
+ goto out;
+
+ newex.first_block = to_le32(split);
+ newex.block_count = to_le16(ee_len - (split - ee_block));
+ ext4_ext_store_pblock(&newex, newblock);
+ if (split_flag & EXT4_EXT_MARK_UNWRIT2)
+ ext4_ext_mark_unwritten(&newex);
+ err = ext4_ext_insert_extent(inode_ref, ppath, &newex,
+ EXT4_EXT_NO_COMBINE);
+ if (err != EOK)
+ goto restore_extent_len;
+
+out:
+ return err;
+restore_extent_len:
+ ex->block_count = to_le16(ee_len);
+ err = ext4_ext_dirty(inode_ref, *ppath + depth);
+ return err;
+}
+
+static int ext4_ext_convert_to_initialized(struct ext4_inode_ref *inode_ref,
+ struct ext4_extent_path **ppath,
+ ext4_lblk_t split, uint32_t blocks)
+{
+ int32_t depth = ext_depth(inode_ref->inode), err = EOK;
+ struct ext4_extent *ex = (*ppath)[depth].extent;
+
+ ext4_assert(to_le32(ex->first_block) <= split);
+
+ if (split + blocks ==
+ to_le32(ex->first_block) + ext4_ext_get_actual_len(ex)) {
+ /* split and initialize right part */
+ err = ext4_ext_split_extent_at(inode_ref, ppath, split,
+ EXT4_EXT_MARK_UNWRIT1);
+ } else if (to_le32(ex->first_block) == split) {
+ /* split and initialize left part */
+ err = ext4_ext_split_extent_at(inode_ref, ppath, split + blocks,
+ EXT4_EXT_MARK_UNWRIT2);
+ } else {
+ /* split 1 extent to 3 and initialize the 2nd */
+ err = ext4_ext_split_extent_at(inode_ref, ppath, split + blocks,
+ EXT4_EXT_MARK_UNWRIT1 |
+ EXT4_EXT_MARK_UNWRIT2);
+ if (!err) {
+ err = ext4_ext_split_extent_at(inode_ref, ppath, split,
+ EXT4_EXT_MARK_UNWRIT1);
+ }
+ }
+
+ return err;
+}
+
+static ext4_lblk_t ext4_ext_next_allocated_block(struct ext4_extent_path *path)
+{
+ int32_t depth;
+
+ depth = path->depth;
+
+ if (depth == 0 && path->extent == NULL)
+ return EXT_MAX_BLOCKS;
+
+ while (depth >= 0) {
+ if (depth == path->depth) {
+ /* leaf */
+ if (path[depth].extent &&
+ path[depth].extent !=
+ EXT_LAST_EXTENT(path[depth].header))
+ return to_le32(
+ path[depth].extent[1].first_block);
+ } else {
+ /* index */
+ if (path[depth].index !=
+ EXT_LAST_INDEX(path[depth].header))
+ return to_le32(
+ path[depth].index[1].first_block);
+ }
+ depth--;
+ }
+
+ return EXT_MAX_BLOCKS;
+}
+
+static int ext4_ext_zero_unwritten_range(struct ext4_inode_ref *inode_ref,
+ ext4_fsblk_t block,
+ uint32_t blocks_count)
+{
+ int err = EOK;
+ uint32_t i;
+ uint32_t block_size = ext4_sb_get_block_size(&inode_ref->fs->sb);
+ for (i = 0; i < blocks_count; i++) {
+ struct ext4_block bh = EXT4_BLOCK_ZERO();
+ err = ext4_trans_block_get_noread(inode_ref->fs->bdev, &bh, block + i);
+ if (err != EOK)
+ break;
+
+ memset(bh.data, 0, block_size);
+ ext4_trans_set_block_dirty(bh.buf);
+ err = ext4_block_set(inode_ref->fs->bdev, &bh);
+ if (err != EOK)
+ break;
+ }
+ return err;
+}
+
+int ext4_extent_get_blocks(struct ext4_inode_ref *inode_ref, ext4_fsblk_t iblock,
+ uint32_t max_blocks, ext4_fsblk_t *result, bool create,
+ uint32_t *blocks_count)
+{
+ struct ext4_extent_path *path = NULL;
+ struct ext4_extent newex, *ex;
+ ext4_fsblk_t goal;
+ int err = EOK;
+ int32_t depth;
+ uint32_t allocated = 0;
+ ext4_fsblk_t next, newblock;
+
+ if (result)
+ *result = 0;
+
+ if (blocks_count)
+ *blocks_count = 0;
+
+ /* find extent for this block */
+ err = ext4_find_extent(inode_ref, iblock, &path, 0);
+ if (err != EOK) {
+ path = NULL;
+ goto out2;
+ }
+
+ depth = ext_depth(inode_ref->inode);
+
+ /*
+ * consistent leaf must not be empty
+ * this situations is possible, though, _during_ tree modification
+ * this is why assert can't be put in ext4_ext_find_extent()
+ */
+ ex = path[depth].extent;
+ if (ex) {
+ ext4_lblk_t ee_block = to_le32(ex->first_block);
+ ext4_fsblk_t ee_start = ext4_ext_pblock(ex);
+ uint16_t ee_len = ext4_ext_get_actual_len(ex);
+ /* if found exent covers block, simple return it */
+ if (IN_RANGE(iblock, ee_block, ee_len)) {
+ /* number of remain blocks in the extent */
+ allocated = ee_len - (iblock - ee_block);
+
+ if (!ext4_ext_is_unwritten(ex)) {
+ newblock = iblock - ee_block + ee_start;
+ goto out;
+ }
+
+ if (!create) {
+ newblock = 0;
+ goto out;
+ }
+
+ uint32_t zero_range;
+ zero_range = allocated;
+ if (zero_range > max_blocks)
+ zero_range = max_blocks;
+
+ newblock = iblock - ee_block + ee_start;
+ err = ext4_ext_zero_unwritten_range(inode_ref, newblock,
+ zero_range);
+ if (err != EOK)
+ goto out2;
+
+ err = ext4_ext_convert_to_initialized(inode_ref, &path,
+ iblock, zero_range);
+ if (err != EOK)
+ goto out2;
+
+ goto out;
+ }
+ }
+
+ /*
+ * requested block isn't allocated yet
+ * we couldn't try to create block if create flag is zero
+ */
+ if (!create) {
+ goto out2;
+ }
+
+ /* find next allocated block so that we know how many
+ * blocks we can allocate without ovelapping next extent */
+ next = ext4_ext_next_allocated_block(path);
+ allocated = next - iblock;
+ if (allocated > max_blocks)
+ allocated = max_blocks;
+
+ /* allocate new block */
+ goal = ext4_ext_find_goal(inode_ref, path, iblock);
+ newblock = ext4_new_meta_blocks(inode_ref, goal, 0, &allocated, &err);
+ if (!newblock)
+ goto out2;
+
+ /* try to insert new extent into found leaf and return */
+ newex.first_block = to_le32(iblock);
+ ext4_ext_store_pblock(&newex, newblock);
+ newex.block_count = to_le16(allocated);
+ err = ext4_ext_insert_extent(inode_ref, &path, &newex, 0);
+ if (err != EOK) {
+ /* free data blocks we just allocated */
+ ext4_ext_free_blocks(inode_ref, ext4_ext_pblock(&newex),
+ to_le16(newex.block_count), 0);
+ goto out2;
+ }
+
+ /* previous routine could use block we allocated */
+ newblock = ext4_ext_pblock(&newex);
+
+out:
+ if (allocated > max_blocks)
+ allocated = max_blocks;
+
+ if (result)
+ *result = newblock;
+
+ if (blocks_count)
+ *blocks_count = allocated;
+
+out2:
+ if (path) {
+ ext4_ext_drop_refs(inode_ref, path, 0);
+ free(path);
+ }
+
+ return err;
+}
projects / lwext4.git / blobdiff