ref: 9944bc0d5f4e34f0cf3fd4ce8b3661fdc89e1cf2
parent: bf878b59ccb34a4cdafa48dbcdcd57c22f335c03
author: Sigrid Solveig Haflínudóttir <[email protected]>
date: Sun Nov 15 07:42:21 EST 2020
replace extents implementation with the updated one, bsd-licensed
--- a/README.md
+++ b/README.md
@@ -43,7 +43,6 @@
files must be removed first. At this point there are two files
licensed under GPLv2:
* ext4_xattr.c
-* ext4_extents.c
All other modules and headers are BSD-3-Clause licensed code.
--- a/include/ext4_extent.h
+++ b/include/ext4_extent.h
@@ -1,6 +1,7 @@
/*
* Copyright (c) 2013 Grzegorz Kostka ([email protected])
*
+ *
* HelenOS:
* Copyright (c) 2012 Martin Sucha
* Copyright (c) 2012 Frantisek Princ
@@ -46,21 +47,314 @@
#include <ext4_config.h>
#include <ext4_types.h>
+#include <ext4_misc.h>
+
#include <ext4_inode.h>
-void ext4_extent_tree_init(struct ext4_inode_ref *inode_ref);
+/*
+ * Array of ext4_ext_path contains path to some extent.
+ * Creation/lookup routines use it for traversal/splitting/etc.
+ * Truncate uses it to simulate recursive walking.
+ */
+struct ext4_extent_path {+ struct ext4_block block;
+ uint16_t depth;
+ struct ext4_extent_header *header;
+ struct ext4_extent_index *index;
+ struct ext4_extent *extent;
+};
+#define EXT4_EXT_UNWRITTEN_MASK (1L << 15)
-int ext4_extent_get_blocks(struct ext4_inode_ref *inode_ref, ext4_lblk_t iblock,
- uint32_t max_blocks, ext4_fsblk_t *result, bool create,
- uint32_t *blocks_count);
+#define EXT4_EXT_MAX_LEN_WRITTEN (1L << 15)
+#define EXT4_EXT_MAX_LEN_UNWRITTEN \
+ (EXT4_EXT_MAX_LEN_WRITTEN - 1)
+#define EXT4_EXT_GET_LEN(ex) to_le16((ex)->nblocks)
+#define EXT4_EXT_GET_LEN_UNWRITTEN(ex) \
+ (EXT4_EXT_GET_LEN(ex) &= ~(EXT4_EXT_UNWRITTEN_MASK))
+#define EXT4_EXT_SET_LEN(ex, count) \
+ ((ex)->nblocks = to_le16(count))
+#define EXT4_EXT_IS_UNWRITTEN(ex) \
+ (EXT4_EXT_GET_LEN(ex) > EXT4_EXT_MAX_LEN_WRITTEN)
+#define EXT4_EXT_SET_UNWRITTEN(ex) \
+ ((ex)->nblocks |= to_le16(EXT4_EXT_UNWRITTEN_MASK))
+#define EXT4_EXT_SET_WRITTEN(ex) \
+ ((ex)->nblocks &= ~(to_le16(EXT4_EXT_UNWRITTEN_MASK)))
+
+#define EXT4_EXTENT_FIRST(header) \
+ ((struct ext4_extent *)(((char *)(header)) + \
+ sizeof(struct ext4_extent_header)))
+
+#define EXT4_EXTENT_FIRST_INDEX(header) \
+ ((struct ext4_extent_index *)(((char *)(header)) + \
+ sizeof(struct ext4_extent_header)))
+
+#define EXT4_EXTENT_LAST(header) \
+ ((struct ext4_extent *)(((char *)(header)) + \
+ sizeof(struct ext4_extent_header)) + \
+ (header)->nentries - 1)
+
+#define EXT4_EXTENT_LAST_INDEX(header) \
+ ((struct ext4_extent_index *)(((char *)(header)) + \
+ sizeof(struct ext4_extent_header)) + \
+ (header)->nentries - 1)
+
+#define EXT4_EXTENT_SIZE sizeof(struct ext4_extent)
+#define EXT4_EXTENT_INDEX_SIZE sizeof(struct ext4_extent_index)
+
+#define EXT4_EXTENT_TAIL_OFFSET(hdr) \
+ (sizeof(struct ext4_extent_header) + \
+ (sizeof(struct ext4_extent) * to_le16((hdr)->max_nentries)))
+
+#define EXT4_EXTENT_IN_RANGE(iblock, eiblock, len) \
+ ((iblock) >= (eiblock) && (iblock) <= (eiblock) + (len) - 1)
+
+#define EXT4_EXTENT_MAX_BLOCKS ((uint32_t)(-1))
+
+/**@brief Get logical number of the block covered by extent.
+ * @param extent Extent to load number from
+ * @return Logical number of the first block covered by extent */
+static inline uint32_t ext4_extent_get_iblock(struct ext4_extent *extent)
+{+ return to_le32(extent->iblock);
+}
+
+/**@brief Set logical number of the first block covered by extent.
+ * @param extent Extent to set number to
+ * @param iblock Logical number of the first block covered by extent */
+static inline void ext4_extent_set_iblock(struct ext4_extent *extent,
+ ext4_lblk_t iblock)
+{+ extent->iblock = to_le32(iblock);
+}
+
+/**@brief Get number of blocks covered by extent.
+ * @param extent Extent to load count from
+ * @return Number of blocks covered by extent */
+static inline uint16_t ext4_extent_get_nblocks(struct ext4_extent *extent)
+{+ if (EXT4_EXT_IS_UNWRITTEN(extent))
+ return EXT4_EXT_GET_LEN_UNWRITTEN(extent);
+ else
+ return EXT4_EXT_GET_LEN(extent);
+}
+/**@brief Set number of blocks covered by extent.
+ * @param extent Extent to load count from
+ * @param count Number of blocks covered by extent
+ * @param unwritten Whether the extent is unwritten or not */
+static inline void
+ext4_extent_set_nblocks(struct ext4_extent *extent,
+ uint16_t count, bool unwritten)
+{+ EXT4_EXT_SET_LEN(extent, count);
+ if (unwritten)
+ EXT4_EXT_SET_UNWRITTEN(extent);
+}
+
+/**@brief Get physical number of the first block covered by extent.
+ * @param extent Extent to load number
+ * @return Physical number of the first block covered by extent */
+static inline uint64_t ext4_extent_get_fblock(struct ext4_extent *extent)
+{+ return ((uint64_t)to_le16(extent->fblock_hi)) << 32 |
+ ((uint64_t)to_le32(extent->fblock_lo));
+}
+
+
+/**@brief Set physical number of the first block covered by extent.
+ * @param extent Extent to load number
+ * @param fblock Physical number of the first block covered by extent */
+static inline void
+ext4_extent_set_fblock(struct ext4_extent *extent, uint64_t fblock)
+{+ extent->fblock_lo = to_le32((fblock << 32) >> 32);
+ extent->fblock_hi = to_le16((uint16_t)(fblock >> 32));
+}
+
+
+/**@brief Get logical number of the block covered by extent index.
+ * @param index Extent index to load number from
+ * @return Logical number of the first block covered by extent index */
+static inline uint32_t
+ext4_extent_index_get_iblock(struct ext4_extent_index *index)
+{+ return to_le32(index->iblock);
+}
+
+/**@brief Set logical number of the block covered by extent index.
+ * @param index Extent index to set number to
+ * @param iblock Logical number of the first block covered by extent index */
+static inline void
+ext4_extent_index_set_iblock(struct ext4_extent_index *index,
+ uint32_t iblock)
+{+ index->iblock = to_le32(iblock);
+}
+
+/**@brief Get physical number of block where the child node is located.
+ * @param index Extent index to load number from
+ * @return Physical number of the block with child node */
+static inline uint64_t
+ext4_extent_index_get_fblock(struct ext4_extent_index *index)
+{+ return ((uint64_t)to_le16(index->fblock_hi)) << 32 |
+ ((uint64_t)to_le32(index->fblock_lo));
+}
+
+/**@brief Set physical number of block where the child node is located.
+ * @param index Extent index to set number to
+ * @param fblock Ohysical number of the block with child node */
+static inline void ext4_extent_index_set_fblock(struct ext4_extent_index *index,
+ uint64_t fblock)
+{+ index->fblock_lo = to_le32((fblock << 32) >> 32);
+ index->fblock_hi = to_le16((uint16_t)(fblock >> 32));
+}
+
+/**@brief Get magic value from extent header.
+ * @param header Extent header to load value from
+ * @return Magic value of extent header */
+static inline uint16_t
+ext4_extent_header_get_magic(struct ext4_extent_header *header)
+{+ return to_le16(header->magic);
+}
+
+/**@brief Set magic value to extent header.
+ * @param header Extent header to set value to
+ * @param magic Magic value of extent header */
+static inline void ext4_extent_header_set_magic(struct ext4_extent_header *header,
+ uint16_t magic)
+{+ header->magic = to_le16(magic);
+}
+
+/**@brief Get number of entries from extent header
+ * @param header Extent header to get value from
+ * @return Number of entries covered by extent header */
+static inline uint16_t
+ext4_extent_header_get_nentries(struct ext4_extent_header *header)
+{+ return to_le16(header->nentries);
+}
+
+/**@brief Set number of entries to extent header
+ * @param header Extent header to set value to
+ * @param count Number of entries covered by extent header */
+static inline void
+ext4_extent_header_set_nentries(struct ext4_extent_header *header,
+ uint16_t count)
+{+ header->nentries = to_le16(count);
+}
+
+/**@brief Get maximum number of entries from extent header
+ * @param header Extent header to get value from
+ * @return Maximum number of entries covered by extent header */
+static inline uint16_t
+ext4_extent_header_get_max_nentries(struct ext4_extent_header *header)
+{+ return to_le16(header->max_nentries);
+}
+
+/**@brief Set maximum number of entries to extent header
+ * @param header Extent header to set value to
+ * @param max_count Maximum number of entries covered by extent header */
+static inline void
+ext4_extent_header_set_max_nentries(struct ext4_extent_header *header,
+ uint16_t max_count)
+{+ header->max_nentries = to_le16(max_count);
+}
+
+/**@brief Get depth of extent subtree.
+ * @param header Extent header to get value from
+ * @return Depth of extent subtree */
+static inline uint16_t
+ext4_extent_header_get_depth(struct ext4_extent_header *header)
+{+ return to_le16(header->depth);
+}
+
+/**@brief Set depth of extent subtree.
+ * @param header Extent header to set value to
+ * @param depth Depth of extent subtree */
+static inline void
+ext4_extent_header_set_depth(struct ext4_extent_header *header,
+ uint16_t depth)
+{+ header->depth = to_le16(depth);
+}
+
+/**@brief Get generation from extent header
+ * @param header Extent header to get value from
+ * @return Generation */
+static inline uint32_t
+ext4_extent_header_get_generation(struct ext4_extent_header *header)
+{+ return to_le32(header->generation);
+}
+
+/**@brief Set generation to extent header
+ * @param header Extent header to set value to
+ * @param generation Generation */
+static inline void
+ext4_extent_header_set_generation(struct ext4_extent_header *header,
+ uint32_t generation)
+{+ header->generation = to_le32(generation);
+}
+
+/******************************************************************************/
+
+/**TODO: */
+static inline void ext4_extent_tree_init(struct ext4_inode_ref *inode_ref)
+{+ /* Initialize extent root header */
+ struct ext4_extent_header *header =
+ ext4_inode_get_extent_header(inode_ref->inode);
+ ext4_extent_header_set_depth(header, 0);
+ ext4_extent_header_set_nentries(header, 0);
+ ext4_extent_header_set_generation(header, 0);
+ ext4_extent_header_set_magic(header, EXT4_EXTENT_MAGIC);
+
+ uint16_t max_entries = (EXT4_INODE_BLOCKS * sizeof(uint32_t) -
+ sizeof(struct ext4_extent_header)) /
+ sizeof(struct ext4_extent);
+
+ ext4_extent_header_set_max_nentries(header, max_entries);
+ inode_ref->dirty = true;
+}
+
+
+
+/**@brief Extent-based blockmap manipulation
+ * @param inode_ref I-node
+ * @param iblock starting logical block of the inode
+ * @param max_nblocks maximum number of blocks to get from/allocate to blockmap
+ * @param resfblockp return physical block address of the first block of an
+ * extent
+ * @param create true if caller wants to insert mapping or convert
+ * unwritten mapping to written one
+ * @param resnblocksp return number of blocks in an extent (must be smaller than
+ * \p max_nblocks)
+ * @return Error code*/
+int ext4_extent_get_blocks(struct ext4_inode_ref *inode_ref,
+ ext4_lblk_t iblock,
+ ext4_lblk_t max_nblocks,
+ ext4_fsblk_t *resfblockp,
+ bool create,
+ ext4_lblk_t *resnblocksp);
+
+
/**@brief Release all data blocks starting from specified logical block.
* @param inode_ref I-node to release blocks from
* @param iblock_from First logical block to release
* @return Error code */
-int ext4_extent_remove_space(struct ext4_inode_ref *inode_ref, ext4_lblk_t from,
+int ext4_extent_remove_space(struct ext4_inode_ref *inode_ref,
+ ext4_lblk_t from,
ext4_lblk_t to);
--- a/include/ext4_types.h
+++ b/include/ext4_types.h
@@ -617,9 +617,71 @@
#define EXT4_JOURNAL_INO 8
#define EXT4_GOOD_OLD_FIRST_INO 11
-#define EXT_MAX_BLOCKS (ext4_lblk_t) (-1)
-#define IN_RANGE(b, first, len) ((b) >= (first) && (b) <= (first) + (len) - 1)
+#ifdef __plan9__
+#pragma pack on
+#else
+#pragma pack(push)
+#endif
+
+/*
+ * This is the extent tail on-disk structure.
+ * All other extent structures are 12 bytes long. It turns out that
+ * block size % 12 >= 4 for at least all powers of 2 greater than 512, which
+ * covers all valid ext4 block sizes. Therefore, this tail structure can be
+ * crammed into the end of the block without having to rebalance the tree.
+ */
+struct ext4_extent_tail
+{+ uint32_t checksum; /* crc32c(uuid+inum+extent_block) */
+};
+
+/*
+ * This is the extent on-disk structure.
+ * It's used at the bottom of the tree.
+ */
+struct ext4_extent {+ uint32_t iblock; /* First logical block extent covers */
+ uint16_t nblocks; /* Number of blocks covered by extent */
+ uint16_t fblock_hi; /* High 16 bits of physical block */
+ uint32_t fblock_lo; /* Low 32 bits of physical block */
+};
+
+/*
+ * This is index on-disk structure.
+ * It's used at all the levels except the bottom.
+ */
+struct ext4_extent_index {+ uint32_t iblock; /* Index covers logical blocks from 'block' */
+
+ /**
+ * Pointer to the physical block of the next
+ * level. leaf or next index could be there
+ * high 16 bits of physical block
+ */
+ uint32_t fblock_lo;
+ uint16_t fblock_hi;
+ uint16_t padding;
+};
+
+/*
+ * Each block (leaves and indexes), even inode-stored has header.
+ */
+struct ext4_extent_header {+ uint16_t magic;
+ uint16_t nentries; /* Number of valid entries */
+ uint16_t max_nentries; /* Capacity of store in entries */
+ uint16_t depth; /* Has tree real underlying blocks? */
+ uint32_t generation; /* generation of the tree */
+};
+
+#ifdef __plan9__
+#pragma pack off
+#else
+#pragma pack(pop)
+#endif
+
+#define EXT4_EXTENT_MAGIC 0xF30A
/******************************************************************************/
--- a/src/ext4_extent.c
+++ b/src/ext4_extent.c
@@ -1,2150 +1,2294 @@
/*
- * Copyright (c) 2017 Grzegorz Kostka ([email protected])
* Copyright (c) 2017 Kaho Ng ([email protected])
+ * Copyright (c) 2017 Grzegorz Kostka ([email protected])
*
- * This program is free software; you can redistribute it and/or
- * modify it under the terms of the GNU General Public License
- * as published by the Free Software Foundation; either version 2
- * of the License, or (at your option) any later version.
+ *
+ * HelenOS:
+ * Copyright (c) 2012 Martin Sucha
+ * Copyright (c) 2012 Frantisek Princ
+ * All rights reserved.
+ *
+ * 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.h>
+/** @addtogroup lwext4
+ * @{+ */
+/**
+ * @file ext4_extent.c
+ * @brief More complex filesystem functions.
+ */
-#include <ext4_blockdev.h>
-#include <ext4_trans.h>
+#include <ext4_config.h>
+#include <ext4_errno.h>
+#include <ext4_debug.h>
+
#include <ext4_fs.h>
+#include <ext4_trans.h>
+#include <ext4_blockdev.h>
+#include <ext4_extent.h>
+#include <ext4_inode.h>
#include <ext4_super.h>
#include <ext4_crc32.h>
#include <ext4_balloc.h>
-#include <ext4_extent.h>
-#include <stdlib.h>
#include <string.h>
-#include <inttypes.h>
-#include <stddef.h>
+#include <stdlib.h>
-#if CONFIG_EXTENTS_ENABLE
-/*
- * 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 */
+#if CONFIG_EXTENT_ENABLE
-#define EXT4_EXT_UNWRITTEN_MASK (1L << 15)
+/**@brief Return the extent tree depth
+ * @param inode_ref I-node reference the tree belongs to
+ * @return Depth of extent tree */
+static inline uint16_t
+ext4_extent_tree_depth(struct ext4_inode_ref *inode_ref)
+{+ struct ext4_extent_header *eh;
+ eh = ext4_inode_get_extent_header(inode_ref->inode);
+ return ext4_extent_header_get_depth(eh);
+}
-#define EXT4_EXT_MAX_LEN_WRITTEN (1L << 15)
-#define EXT4_EXT_MAX_LEN_UNWRITTEN \
- (EXT4_EXT_MAX_LEN_WRITTEN - 1)
+static struct ext4_extent_tail *
+ext4_extent_get_csum_tail(struct ext4_extent_header *eh)
+{+ return (struct ext4_extent_tail *)(((char *)eh) +
+ EXT4_EXTENT_TAIL_OFFSET(eh));
+}
-#define EXT4_EXT_GET_LEN(ex) to_le16((ex)->block_count)
-#define EXT4_EXT_GET_LEN_UNWRITTEN(ex) \
- (EXT4_EXT_GET_LEN(ex) & ~(EXT4_EXT_UNWRITTEN_MASK))
-#define EXT4_EXT_SET_LEN(ex, count) \
- ((ex)->block_count = to_le16(count))
+#if CONFIG_META_CSUM_ENABLE
+static uint32_t ext4_extent_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;
-#define EXT4_EXT_IS_UNWRITTEN(ex) \
- (EXT4_EXT_GET_LEN(ex) > EXT4_EXT_MAX_LEN_WRITTEN)
-#define EXT4_EXT_SET_UNWRITTEN(ex) \
- ((ex)->block_count |= to_le16(EXT4_EXT_UNWRITTEN_MASK))
-#define EXT4_EXT_SET_WRITTEN(ex) \
- ((ex)->block_count &= ~(to_le16(EXT4_EXT_UNWRITTEN_MASK)))
+ 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;
+}
-/*
- * Array of ext4_ext_path contains path to some extent.
- * Creation/lookup routines use it for traversal/splitting/etc.
- * Truncate uses it to simulate recursive walking.
- */
-struct ext4_extent_path {- ext4_fsblk_t p_block;
- struct ext4_block block;
- int32_t depth;
- int32_t maxdepth;
- struct ext4_extent_header *header;
- struct ext4_extent_index *index;
- struct ext4_extent *extent;
-};
+static bool
+ext4_extent_verify_block_csum(struct ext4_inode_ref *inode_ref,
+ struct ext4_block *block)
+{+ uint16_t rootdepth;
+ struct ext4_extent_tail *tail;
+ struct ext4_extent_header *eh;
-#ifdef __plan9__
-#pragma pack on
-#else
-#pragma pack(push, 1)
-#endif
+ rootdepth = ext4_extent_tree_depth(inode_ref);
-/*
- * This is the extent tail on-disk structure.
- * All other extent structures are 12 bytes long. It turns out that
- * block_size % 12 >= 4 for at least all powers of 2 greater than 512, which
- * covers all valid ext4 block sizes. Therefore, this tail structure can be
- * crammed into the end of the block without having to rebalance the tree.
- */
-struct ext4_extent_tail
-{- uint32_t et_checksum; /* crc32c(uuid+inum+extent_block) */
-};
+ if (!ext4_sb_feature_ro_com(&inode_ref->fs->sb,
+ EXT4_FRO_COM_METADATA_CSUM))
+ return true;
-/*
- * This is the extent on-disk structure.
- * It's used at the bottom of the tree.
- */
-struct ext4_extent {- uint32_t first_block; /* First logical block extent covers */
- uint16_t block_count; /* Number of blocks covered by extent */
- uint16_t start_hi; /* High 16 bits of physical block */
- uint32_t start_lo; /* Low 32 bits of physical block */
-};
+ eh = (struct ext4_extent_header *)block->data;
+ if (ext4_extent_header_get_depth(eh) < rootdepth) {+ tail = ext4_extent_get_csum_tail(eh);
+ return tail->checksum ==
+ to_le32(ext4_extent_block_csum(inode_ref, eh));
+ }
-/*
- * This is index on-disk structure.
- * It's used at all the levels except the bottom.
- */
-struct ext4_extent_index {- uint32_t first_block; /* Index covers logical blocks from 'block' */
+ return true;
+}
+#else /* CONFIG_META_CSUM_ENABLE */
+#define ext4_ext_block_csum(...) 0
+#define ext4_extent_verify_block_csum(...) true
+#endif /* CONFIG_META_CSUM_ENABLE */
- /**
- * Pointer to the physical block of the next
- * level. leaf or next index could be there
- * high 16 bits of physical block
- */
- uint32_t leaf_lo;
- uint16_t leaf_hi;
- uint16_t padding;
-};
+static void
+ext4_extent_block_csum_set(struct ext4_inode_ref *inode_ref,
+ struct ext4_extent_header *eh)
+{+ uint16_t rootdepth;
+ struct ext4_extent_tail *tail;
-/*
- * Each block (leaves and indexes), even inode-stored has header.
- */
-struct ext4_extent_header {- uint16_t magic;
- uint16_t entries_count; /* Number of valid entries */
- uint16_t max_entries_count; /* Capacity of store in entries */
- uint16_t depth; /* Has tree real underlying blocks? */
- uint32_t generation; /* generation of the tree */
-};
+ rootdepth = ext4_extent_tree_depth(inode_ref);
-#ifdef __plan9__
-#pragma pack off
-#else
-#pragma pack(pop)
-#endif
+ if (!ext4_sb_feature_ro_com(&inode_ref->fs->sb,
+ EXT4_FRO_COM_METADATA_CSUM))
+ return;
-#define EXT4_EXTENT_MAGIC 0xF30A
+ if (ext4_extent_header_get_depth(eh) < rootdepth) {+ tail = ext4_extent_get_csum_tail(eh);
+ tail->checksum = to_le32(ext4_extent_block_csum(inode_ref, eh));
+ }
+}
-#define EXT4_EXTENT_FIRST(header) \
- ((struct ext4_extent *)(((char *)(header)) + \
- sizeof(struct ext4_extent_header)))
+#if CONFIG_EXTENT_DEBUG_VERBOSE
+static void
+ext4_extent_print_path(struct ext4_inode_ref *inode_ref,
+ struct ext4_extent_path *path)
+{+ uint16_t rootdepth;
+ struct ext4_extent_path *p;
-#define EXT4_EXTENT_FIRST_INDEX(header) \
- ((struct ext4_extent_index *)(((char *)(header)) + \
- sizeof(struct ext4_extent_header)))
+ rootdepth = ext4_extent_tree_depth(inode_ref);
+ p = path + rootdepth;
-/*
- * EXT_INIT_MAX_LEN is the maximum number of blocks we can have in an
- * initialized extent. This is 2^15 and not (2^16 - 1), since we use the
- * MSB of ee_len field in the extent datastructure to signify if this
- * particular extent is an initialized extent or an uninitialized (i.e.
- * preallocated).
- * EXT_UNINIT_MAX_LEN is the maximum number of blocks we can have in an
- * uninitialized extent.
- * If ee_len is <= 0x8000, it is an initialized extent. Otherwise, it is an
- * uninitialized one. In other words, if MSB of ee_len is set, it is an
- * uninitialized extent with only one special scenario when ee_len = 0x8000.
- * In this case we can not have an uninitialized extent of zero length and
- * thus we make it as a special case of initialized extent with 0x8000 length.
- * This way we get better extent-to-group alignment for initialized extents.
- * Hence, the maximum number of blocks we can have in an *initialized*
- * extent is 2^15 (32768) and in an *uninitialized* extent is 2^15-1 (32767).
- */
-#define EXT_INIT_MAX_LEN (1L << 15)
-#define EXT_UNWRITTEN_MAX_LEN (EXT_INIT_MAX_LEN - 1)
+ ext4_dbg(DEBUG_EXTENT,
+ DBG_INFO "Path address: %p\n", path);
+ while (p >= path) {+ uint16_t i;
+ uint16_t entries =
+ ext4_extent_header_get_nentries(p->header);
+ uint16_t limit =
+ ext4_extent_header_get_max_nentries(p->header);
-#define EXT_EXTENT_SIZE sizeof(struct ext4_extent)
-#define EXT_INDEX_SIZE sizeof(struct ext4_extent_idx)
+ ext4_dbg(DEBUG_EXTENT,
+DBG_INFO "-- Block: %" PRIu64 ", Depth: %" PRIu16 ", Entries: %" PRIu16 ", Limit: %" PRIu16 "\n",
+ p->block.lb_id, p->depth, entries, limit);
+ for (i = 0; i < entries; i++) {+ if (p->depth) {+ struct ext4_extent_index *index;
-#define EXT_FIRST_EXTENT(__hdr__) \
- ((struct ext4_extent *)(((char *)(__hdr__)) + \
- sizeof(struct ext4_extent_header)))
-#define EXT_FIRST_INDEX(__hdr__) \
- ((struct ext4_extent_index *)(((char *)(__hdr__)) + \
- sizeof(struct ext4_extent_header)))
-#define EXT_HAS_FREE_INDEX(__path__) \
- (to_le16((__path__)->header->entries_count) < \
- to_le16((__path__)->header->max_entries_count))
-#define EXT_LAST_EXTENT(__hdr__) \
- (EXT_FIRST_EXTENT((__hdr__)) + to_le16((__hdr__)->entries_count) - 1)
-#define EXT_LAST_INDEX(__hdr__) \
- (EXT_FIRST_INDEX((__hdr__)) + to_le16((__hdr__)->entries_count) - 1)
-#define EXT_MAX_EXTENT(__hdr__) \
- (EXT_FIRST_EXTENT((__hdr__)) + to_le16((__hdr__)->max_entries_count) - 1)
-#define EXT_MAX_INDEX(__hdr__) \
- (EXT_FIRST_INDEX((__hdr__)) + to_le16((__hdr__)->max_entries_count) - 1)
+ index = EXT4_EXTENT_FIRST_INDEX(p->header) + i;
+ ext4_dbg(DEBUG_EXTENT,
+DBG_INFO "Index: iblock: %" PRIu32 ", fsblock: %" PRIu64 "\n",
+ ext4_extent_index_get_iblock(index),
+ ext4_extent_index_get_fblock(index));
+ } else {+ struct ext4_extent *extent;
-#define EXT4_EXTENT_TAIL_OFFSET(hdr) \
- (sizeof(struct ext4_extent_header) + \
- (sizeof(struct ext4_extent) * to_le16((hdr)->max_entries_count)))
+ extent = EXT4_EXTENT_FIRST(p->header) + i;
+ ext4_dbg(DEBUG_EXTENT,
+DBG_INFO "Extent: iblock: %" PRIu32 ", fsblock: %" PRIu64 ", count: %" PRIu16 "\n",
+ ext4_extent_get_iblock(extent),
+ ext4_extent_get_fblock(extent),
+ ext4_extent_get_nblocks(extent));
+ }
+ }
+ p--;
+ }
-/**@brief Get logical number of the block covered by extent.
- * @param extent Extent to load number from
- * @return Logical number of the first block covered by extent */
-static inline uint32_t ext4_extent_get_first_block(struct ext4_extent *extent)
-{- return to_le32(extent->first_block);
+ ext4_dbg(DEBUG_EXTENT,
+ DBG_INFO "====================\n");
}
+#else /* CONFIG_EXTENT_DEBUG_VERBOSE */
+#define ext4_extent_print_path(...)
+#endif /* CONFIG_EXTENT_DEBUG_VERBOSE */
-/**@brief Set logical number of the first block covered by extent.
- * @param extent Extent to set number to
- * @param iblock Logical number of the first block covered by extent */
-static inline void ext4_extent_set_first_block(struct ext4_extent *extent,
- uint32_t iblock)
+/**@brief Binary search in extent index node.
+ * @param header Extent header of index node
+ * @param index Output value - found index will be set here
+ * @param iblock Logical block number to find in index node */
+static void ext4_extent_binsearch_idx(struct ext4_extent_header *header,
+ struct ext4_extent_index **index,
+ ext4_lblk_t iblock)
{- extent->first_block = to_le32(iblock);
-}
+ struct ext4_extent_index *r;
+ struct ext4_extent_index *l;
+ struct ext4_extent_index *m;
-/**@brief Get number of blocks covered by extent.
- * @param extent Extent to load count from
- * @return Number of blocks covered by extent */
-static inline uint16_t ext4_extent_get_block_count(struct ext4_extent *extent)
-{- if (EXT4_EXT_IS_UNWRITTEN(extent))
- return EXT4_EXT_GET_LEN_UNWRITTEN(extent);
- else
- return EXT4_EXT_GET_LEN(extent);
+ uint16_t nentries = ext4_extent_header_get_nentries(header);
+
+ /* Initialize bounds */
+ l = EXT4_EXTENT_FIRST_INDEX(header) + 1;
+ r = EXT4_EXTENT_FIRST_INDEX(header) + nentries - 1;
+
+ /* Do binary search */
+ while (l <= r) {+ m = l + (r - l) / 2;
+ ext4_lblk_t eiiblock = ext4_extent_index_get_iblock(m);
+
+ if (iblock < eiiblock)
+ r = m - 1;
+ else
+ l = m + 1;
+ }
+
+ /* Set output value */
+ *index = l - 1;
}
-/**@brief Set number of blocks covered by extent.
- * @param extent Extent to load count from
- * @param count Number of blocks covered by extent
- * @param unwritten Whether the extent is unwritten or not */
-static inline void ext4_extent_set_block_count(struct ext4_extent *extent,
- uint16_t count, bool unwritten)
-{- EXT4_EXT_SET_LEN(extent, count);
- if (unwritten)
- EXT4_EXT_SET_UNWRITTEN(extent);
-}
-/**@brief Get physical number of the first block covered by extent.
- * @param extent Extent to load number
- * @return Physical number of the first block covered by extent */
-static inline uint64_t ext4_extent_get_start(struct ext4_extent *extent)
+/**@brief Binary search in extent leaf node.
+ * @param header Extent header of leaf node
+ * @param extent Output value - found extent will be set here,
+ * or NULL if node is empty
+ * @param iblock Logical block number to find in leaf node */
+static void ext4_extent_binsearch(struct ext4_extent_header *header,
+ struct ext4_extent **extent,
+ ext4_lblk_t iblock)
{- return ((uint64_t)to_le16(extent->start_hi)) << 32 |
- ((uint64_t)to_le32(extent->start_lo));
-}
+ struct ext4_extent *r;
+ struct ext4_extent *l;
+ struct ext4_extent *m;
+ uint16_t nentries = ext4_extent_header_get_nentries(header);
-/**@brief Set physical number of the first block covered by extent.
- * @param extent Extent to load number
- * @param fblock Physical number of the first block covered by extent */
-static inline void ext4_extent_set_start(struct ext4_extent *extent, uint64_t fblock)
-{- extent->start_lo = to_le32((fblock << 32) >> 32);
- extent->start_hi = to_le16((uint16_t)(fblock >> 32));
-}
+ if (nentries == 0) {+ /* this leaf is empty */
+ *extent = NULL;
+ return;
+ }
+ /* Initialize bounds */
+ l = EXT4_EXTENT_FIRST(header) + 1;
+ r = EXT4_EXTENT_FIRST(header) + nentries - 1;
-/**@brief Get logical number of the block covered by extent index.
- * @param index Extent index to load number from
- * @return Logical number of the first block covered by extent index */
-static inline uint32_t
-ext4_extent_index_get_first_block(struct ext4_extent_index *index)
-{- return to_le32(index->first_block);
-}
+ /* Do binary search */
+ while (l <= r) {+ m = l + (r - l) / 2;
+ ext4_lblk_t eiblock = ext4_extent_get_iblock(m);
-/**@brief Set logical number of the block covered by extent index.
- * @param index Extent index to set number to
- * @param iblock Logical number of the first block covered by extent index */
-static inline void
-ext4_extent_index_set_first_block(struct ext4_extent_index *index,
- uint32_t iblock)
-{- index->first_block = to_le32(iblock);
-}
+ if (iblock < eiblock)
+ r = m - 1;
+ else
+ l = m + 1;
+ }
-/**@brief Get physical number of block where the child node is located.
- * @param index Extent index to load number from
- * @return Physical number of the block with child node */
-static inline uint64_t
-ext4_extent_index_get_leaf(struct ext4_extent_index *index)
-{- return ((uint64_t)to_le16(index->leaf_hi)) << 32 |
- ((uint64_t)to_le32(index->leaf_lo));
+ /* Set output value */
+ *extent = l - 1;
}
-/**@brief Set physical number of block where the child node is located.
- * @param index Extent index to set number to
- * @param fblock Ohysical number of the block with child node */
-static inline void ext4_extent_index_set_leaf(struct ext4_extent_index *index,
- uint64_t fblock)
+static void
+ext4_extent_path_dirty(struct ext4_inode_ref *inode_ref,
+ struct ext4_extent_path *path,
+ uint16_t depth)
{- index->leaf_lo = to_le32((fblock << 32) >> 32);
- index->leaf_hi = to_le16((uint16_t)(fblock >> 32));
-}
+ uint16_t rootdepth;
+ rootdepth = ext4_extent_tree_depth(inode_ref);
-/**@brief Get magic value from extent header.
- * @param header Extent header to load value from
- * @return Magic value of extent header */
-static inline uint16_t
-ext4_extent_header_get_magic(struct ext4_extent_header *header)
-{- return to_le16(header->magic);
+ if (rootdepth != depth) {+ struct ext4_extent_path *p;
+ p = path + depth;
+ ext4_extent_block_csum_set(inode_ref, p->header);
+ ext4_trans_set_block_dirty(p->block.buf);
+ } else
+ inode_ref->dirty = true;
}
-/**@brief Set magic value to extent header.
- * @param header Extent header to set value to
- * @param magic Magic value of extent header */
-static inline void ext4_extent_header_set_magic(struct ext4_extent_header *header,
- uint16_t magic)
+static int
+ext4_extent_path_release(struct ext4_inode_ref *inode_ref,
+ struct ext4_extent_path *path)
{- header->magic = to_le16(magic);
-}
+ int ret = EOK;
+ uint16_t i, rootdepth;
-/**@brief Get number of entries from extent header
- * @param header Extent header to get value from
- * @return Number of entries covered by extent header */
-static inline uint16_t
-ext4_extent_header_get_entries_count(struct ext4_extent_header *header)
-{- return to_le16(header->entries_count);
-}
+ rootdepth = ext4_extent_tree_depth(inode_ref);
-/**@brief Set number of entries to extent header
- * @param header Extent header to set value to
- * @param count Number of entries covered by extent header */
-static inline void
-ext4_extent_header_set_entries_count(struct ext4_extent_header *header,
- uint16_t count)
-{- header->entries_count = to_le16(count);
-}
+ for (i = 0; i < rootdepth; i++) {+ if (path[i].block.lb_id) {+ ret = ext4_block_set(inode_ref->fs->bdev,
+ &path[i].block);
+ if (ret != EOK)
+ break;
+ }
+ }
-/**@brief Get maximum number of entries from extent header
- * @param header Extent header to get value from
- * @return Maximum number of entries covered by extent header */
-static inline uint16_t
-ext4_extent_header_get_max_entries_count(struct ext4_extent_header *header)
-{- return to_le16(header->max_entries_count);
+ return ret;
}
-/**@brief Set maximum number of entries to extent header
- * @param header Extent header to set value to
- * @param max_count Maximum number of entries covered by extent header */
-static inline void
-ext4_extent_header_set_max_entries_count(struct ext4_extent_header *header,
- uint16_t max_count)
+/**@brief Physical block allocation hint for extent tree manipulation
+ * routines
+ * @param inode_ref I-node
+ * @return Physical block allocation hint */
+static ext4_fsblk_t
+ext4_extent_tree_alloc_goal(struct ext4_inode_ref *inode_ref)
{- header->max_entries_count = to_le16(max_count);
-}
+ uint32_t bgid;
+ struct ext4_sblock *sb;
-/**@brief Get depth of extent subtree.
- * @param header Extent header to get value from
- * @return Depth of extent subtree */
-static inline uint16_t
-ext4_extent_header_get_depth(struct ext4_extent_header *header)
-{- return to_le16(header->depth);
-}
+ sb = &inode_ref->fs->sb;
+ bgid = inode_ref->index / ext4_get32(sb, inodes_per_group);
-/**@brief Set depth of extent subtree.
- * @param header Extent header to set value to
- * @param depth Depth of extent subtree */
-static inline void
-ext4_extent_header_set_depth(struct ext4_extent_header *header, uint16_t depth)
-{- header->depth = to_le16(depth);
+ /* Currently for allocations from extent tree manipulation routines,
+ * we try the blocks in the block group the inode table block refers
+ * to */
+ return ext4_fs_first_bg_block_no(sb, bgid);
}
-/**@brief Get generation from extent header
- * @param header Extent header to get value from
- * @return Generation */
-static inline uint32_t
-ext4_extent_header_get_generation(struct ext4_extent_header *header)
+/**@brief Physical block allocation hint for data blocks routines
+ * @param inode_ref I-node
+ * @param path path in the extent tree
+ * @param iblock the starting logical block of the
+ * mapping to be inserted
+ * @return Physical block allocation hint */
+static ext4_fsblk_t
+ext4_extent_data_alloc_goal(struct ext4_inode_ref *inode_ref,
+ struct ext4_extent_path *path,
+ ext4_lblk_t iblock)
{- return to_le32(header->generation);
-}
+ ext4_fsblk_t ret;
+ struct ext4_extent *ext;
-/**@brief Set generation to extent header
- * @param header Extent header to set value to
- * @param generation Generation */
-static inline void
-ext4_extent_header_set_generation(struct ext4_extent_header *header,
- uint32_t generation)
-{- header->generation = to_le32(generation);
+ ext = path[0].extent;
+ if (!ext)
+ /* If there is no mapping yet, we return
+ * ext4_extent_tree_alloc_goal() as hints */
+ return ext4_extent_tree_alloc_goal(inode_ref) + iblock;
+
+ /* We want the whole file to be continuous. */
+ if (ext4_extent_get_iblock(ext) < iblock)
+ ret = ext4_extent_get_fblock(ext) +
+ iblock - ext4_extent_get_iblock(ext);
+ else {+ if (ext4_extent_get_iblock(ext) - iblock >
+ ext4_extent_get_fblock(ext))
+ ret = ext4_extent_get_fblock(ext);
+ else
+ ret = ext4_extent_get_fblock(ext) -
+ (ext4_extent_get_iblock(ext) - iblock);
+ }
+
+ return ret;
}
-void ext4_extent_tree_init(struct ext4_inode_ref *inode_ref)
+/**@brief Verify the extent node block is valid
+ * @param inode_ref I-node
+ * @param block block buffer of the extent node block
+ * @param depth the depth of extent node wanted
+ * @return true if the block passes verification, otherwise false
+ */
+static bool ext4_extent_block_verify(struct ext4_inode_ref *inode_ref,
+ struct ext4_block *block,
+ uint16_t depth)
{- /* Initialize extent root header */
- struct ext4_extent_header *header =
- ext4_inode_get_extent_header(inode_ref->inode);
- ext4_extent_header_set_depth(header, 0);
- ext4_extent_header_set_entries_count(header, 0);
- ext4_extent_header_set_generation(header, 0);
- ext4_extent_header_set_magic(header, EXT4_EXTENT_MAGIC);
+ uint32_t blocksz;
+ uint16_t maxnentries __unused;
+ struct ext4_extent_header *eh;
- uint16_t max_entries = (EXT4_INODE_BLOCKS * sizeof(uint32_t) -
- sizeof(struct ext4_extent_header)) /
- sizeof(struct ext4_extent);
+ eh = (struct ext4_extent_header *)block->data;
+ blocksz = ext4_sb_get_block_size(&inode_ref->fs->sb);
- ext4_extent_header_set_max_entries_count(header, max_entries);
- inode_ref->dirty = true;
-}
+ /* Check if the magic number of the extent node header is correct */
+ if (ext4_extent_header_get_magic(eh) != EXT4_EXTENT_MAGIC) {+ ext4_dbg(DEBUG_EXTENT,
+DBG_ERROR "Extent node block header mismatch! Block number: %" PRIu64 "\n",
+ block->lb_id);
+ return false;
+ }
+ /* Check if the depth field of extent node header matches what the
+ * caller wants */
+ if (ext4_extent_header_get_depth(eh) != depth) {+ ext4_dbg(DEBUG_EXTENT,
+DBG_ERROR "Extent node block depth mismatch! Expected: %" PRIu16 ", Got: %" PRIu16 ". Block number: %" PRIu64 "\n",
+ depth, ext4_extent_header_get_depth(eh),
+ block->lb_id);
+ return false;
+ }
-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));
-}
+ /* Check if the non-root node contains entries */
+ if (!ext4_extent_header_get_nentries(eh)) {+ ext4_dbg(DEBUG_EXTENT,
+DBG_ERROR "Extent node block does not contain any entries! Block number: %" PRIu64 "\n",
+ block->lb_id);
+ return false;
+ }
-static struct ext4_extent_header *ext_inode_hdr(struct ext4_inode *inode)
-{- return (struct ext4_extent_header *)inode->blocks;
-}
+#if !CONFIG_EXTENT_DEBUG_AGGRESSIVE
+ /* Make sure that the maximum entries field of the
+ * extent node header is correct */
+ maxnentries = (blocksz - sizeof(struct ext4_extent_header)) /
+ sizeof(struct ext4_extent);
-static struct ext4_extent_header *ext_block_hdr(struct ext4_block *block)
-{- return (struct ext4_extent_header *)block->data;
-}
+ if (ext4_extent_header_get_max_nentries(eh) != maxnentries) {+ ext4_dbg(DEBUG_EXTENT,
+DBG_ERROR "Incorrect extent node block maximum entries field! Expected: %" PRIu16 ", Got: %" PRIu16 ". Block number: %" PRIu64 "\n",
+ maxnentries,
+ ext4_extent_header_get_max_nentries(eh),
+ block->lb_id);
+ return false;
+ }
+#endif
-static uint16_t ext_depth(struct ext4_inode *inode)
-{- return to_le16(ext_inode_hdr(inode)->depth);
-}
+ /* Check if the checksum of the block is correct */
+ if (!ext4_extent_verify_block_csum(inode_ref,
+ block)) {+ ext4_dbg(DEBUG_EXTENT,
+DBG_ERROR "Extent node block checksum failed! Block number: %" PRIu64"\n",
+ block->lb_id);
+ return false;
+ }
-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));
+ /* The block passes verification */
+ return true;
}
-static void ext4_ext_mark_initialized(struct ext4_extent *ext)
+/**@brief Find extent for specified iblock.
+ * This function is used for finding block in the extent tree with
+ * saving the path through the tree for possible future modifications.
+ * @param inode_ref I-node to read extent tree from
+ * @param iblock Iblock to find extent for
+ * @param ppath Output value - loaded path from extent tree
+ * @return Error code */
+static int ext4_extent_find_extent(struct ext4_inode_ref *inode_ref,
+ ext4_lblk_t iblock,
+ struct ext4_extent_path **ppath)
{- ext->block_count = to_le16(ext4_ext_get_actual_len(ext));
-}
+ struct ext4_extent_header *eh;
+ int ret;
+ uint16_t depth;
+ uint16_t k;
+ struct ext4_extent_path *tpath;
-static void ext4_ext_mark_unwritten(struct ext4_extent *ext)
-{- ext->block_count |= to_le16(EXT_INIT_MAX_LEN);
-}
+ depth = ext4_extent_tree_depth(inode_ref);
+ eh = ext4_inode_get_extent_header(inode_ref->inode);
-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);
-}
+ /* Added 2 for possible tree growing (1 extra depth) */
+ tpath = ext4_malloc(sizeof(struct ext4_extent_path) * (depth + 2));
+ if (tpath == NULL)
+ return ENOMEM;
-/*
- * 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;
+ /* Zero the path array because we need to make sure that
+ * lb_id field of block buffer is zero */
+ memset(tpath, 0, sizeof(struct ext4_extent_path) * (depth + 2));
- block = to_le32(ex->start_lo);
- block |= ((ext4_fsblk_t)to_le16(ex->start_hi) << 31) << 1;
- return block;
-}
+ /* Initialize structure for algorithm start */
+ k = depth;
+ tpath[k].block = inode_ref->block;
+ tpath[k].header = eh;
-/*
- * 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;
+ /* Walk through the extent tree */
+ while ((depth = ext4_extent_header_get_depth(eh)) != 0) {+ /* Search index in index node by iblock */
+ ext4_extent_binsearch_idx(tpath[k].header,
+ &tpath[k].index, iblock);
- block = to_le32(ix->leaf_lo);
- block |= ((ext4_fsblk_t)to_le16(ix->leaf_hi) << 31) << 1;
- return block;
-}
+ tpath[k].depth = depth;
+ tpath[k].extent = NULL;
-/*
- * 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_assert(tpath[k].index != 0);
-/*
- * 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);
-}
+ /* Load information for the next iteration */
+ uint64_t fblock =
+ ext4_extent_index_get_fblock(tpath[k].index);
-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);
-}
+ struct ext4_block block;
+ ret = ext4_trans_block_get(inode_ref->fs->bdev, &block, fblock);
+ if (ret != EOK)
+ goto errout0;
-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;
+ if (!ext4_extent_block_verify(inode_ref, &block, depth - 1)) {+ ret = EIO;
+ goto errout0;
+ }
- USED(flags);
+ k--;
- *errp = ext4_allocate_single_block(inode_ref, goal, &block);
- if (count)
- *count = 1;
- return block;
-}
+ eh = (struct ext4_extent_header *)block.data;
+ tpath[k].block = block;
+ tpath[k].header = eh;
+ }
-static void ext4_ext_free_blocks(struct ext4_inode_ref *inode_ref,
- ext4_fsblk_t block, uint32_t count,
- uint32_t flags __unused)
-{- USED(flags);
- ext4_balloc_free_blocks(inode_ref, block, count);
-}
+ tpath[k].depth = 0;
+ tpath[k].extent = NULL;
+ tpath[k].index = NULL;
-static uint16_t ext4_ext_space_block(struct ext4_inode_ref *inode_ref)
-{- uint16_t size;
- uint32_t block_size = ext4_sb_get_block_size(&inode_ref->fs->sb);
+ /* Find extent in the leaf node */
+ ext4_extent_binsearch(tpath[k].header, &tpath[k].extent,
+ iblock);
+ *ppath = tpath;
- size = (block_size - sizeof(struct ext4_extent_header)) /
- sizeof(struct ext4_extent);
-#ifdef AGGRESSIVE_TEST
- if (size > 6)
- size = 6;
-#endif
- return size;
-}
+ return EOK;
-static uint16_t ext4_ext_space_block_idx(struct ext4_inode_ref *inode_ref)
-{- uint16_t size;
- uint32_t block_size = ext4_sb_get_block_size(&inode_ref->fs->sb);
+errout0:
+ /* Put loaded blocks */
+ ext4_extent_path_release(inode_ref, tpath);
- size = (block_size - sizeof(struct ext4_extent_header)) /
- sizeof(struct ext4_extent_index);
-#ifdef AGGRESSIVE_TEST
- if (size > 5)
- size = 5;
-#endif
- return size;
+ /* Destroy temporary data structure */
+ ext4_free(tpath);
+
+ return ret;
}
-static uint16_t ext4_ext_space_root(struct ext4_inode_ref *inode_ref)
+/**@brief Reload the paths in a cursor starting from the level having invalid
+ * pointer
+ * @param inode_ref I-node the extent tree resides in
+ * @param path Path in the extent tree
+ * @param depth The level to start the reload at
+ * @param right Try to load the rightmost children
+ * @return EOK on success, EIO on corrupted block, or return values of
+ * ext4_trans_block_get(). */
+int ext4_extent_reload_paths(struct ext4_inode_ref *inode_ref,
+ struct ext4_extent_path *path,
+ uint16_t depth,
+ bool right)
{- uint16_t size;
+ int ret = EOK;
+ struct ext4_extent_header *header;
+ struct ext4_extent_path *p;
- USED(inode_ref);
- 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;
-}
+ /* actually we assume our caller starting from index level instead of
+ * extent level */
+ ext4_assert(depth);
-static uint16_t ext4_ext_space_root_idx(struct ext4_inode_ref *inode_ref)
-{- uint16_t size;
+ p = path + depth;
+ header = p->header;
- USED(inode_ref);
- 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;
-}
+ /* XXX: the path becomes invalid at the first place... */
+ if (p->index > EXT4_EXTENT_LAST_INDEX(header))
+ p->index = EXT4_EXTENT_LAST_INDEX(header);
-static uint16_t ext4_ext_max_entries(struct ext4_inode_ref *inode_ref,
- uint32_t depth)
-{- uint16_t max;
+ /* Start reloading all the paths from the child of the specified level
+ * toward the leaf */
+ for (; p > path; --p) {+ struct ext4_extent_path *chldp;
+ struct ext4_extent_index *idx;
- 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);
- }
+ chldp = p - 1;
+ header = p->header; USED(header);
+ idx = p->index;
- return max;
+ /* Release the buffer of child path if the buffer is still
+ * valid */
+ if (chldp->block.lb_id) {+ ret = ext4_block_set(inode_ref->fs->bdev, &chldp->block);
+ if (ret != EOK)
+ goto out;
+ }
+
+ /* Read the block specified by the physical block field of the
+ * index */
+ ret = ext4_trans_block_get(inode_ref->fs->bdev, &chldp->block,
+ ext4_extent_index_get_fblock(idx));
+ if (ret != EOK)
+ goto out;
+
+ header = (struct ext4_extent_header *)chldp->block.data;
+ /* Validate the block content before moving on. */
+ if (!ext4_extent_block_verify(inode_ref,
+ &chldp->block, p->depth - 1)) {+ ret = EIO;
+ goto out;
+ }
+
+ /* Reset the fields of child path */
+ chldp->header = header;
+ chldp->depth = ext4_extent_header_get_depth(header);
+ if (right) {+ if (chldp->depth) {+ chldp->index = EXT4_EXTENT_LAST_INDEX(header);
+ chldp->extent = NULL;
+ } else {+ chldp->extent = EXT4_EXTENT_LAST(header);
+ chldp->index = NULL;
+ }
+ } else {+ if (chldp->depth) {+ chldp->index = EXT4_EXTENT_FIRST_INDEX(header);
+ chldp->extent = NULL;
+ } else {+ chldp->extent = EXT4_EXTENT_FIRST(header);
+ chldp->index = NULL;
+ }
+ }
+ }
+out:
+ return ret;
}
-static ext4_fsblk_t ext4_ext_find_goal(struct ext4_inode_ref *inode_ref,
- struct ext4_extent_path *path,
- ext4_lblk_t block)
+/**@brief Seek to the next extent
+ * @param inode_ref I-node the extent tree resides in
+ * @param path Path in the extent tree
+ * @param nonextp Output value - whether the current extent is the
+ * right-most extent already
+ * @return 0 on success, EIO on currupted block, or return values of
+ * ext4_trans_block_get(). */
+int ext4_extent_increment(struct ext4_inode_ref *inode_ref,
+ struct ext4_extent_path *path,
+ bool *nonextp)
{- if (path) {- uint32_t depth = path->depth;
- struct ext4_extent *ex;
+ int ret = EOK;
+ uint16_t ptr;
+ bool nonext = true;
+ uint16_t depth = 0;
+ struct ext4_extent_path *p;
+ uint16_t rootdepth;
- /*
- * 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);
+ p = path;
+ rootdepth = ext4_extent_tree_depth(inode_ref);
- if (block > ext_block)
- return ext_pblk + (block - ext_block);
- else
- return ext_pblk - (ext_block - block);
+ /* Iterate the paths from the leaf to the root */
+ while (depth <= rootdepth) {+ struct ext4_extent_header *header;
+
+ if (p->depth) {+ ptr = p->index -
+ EXT4_EXTENT_FIRST_INDEX(p->header);
+ } else {+ ptr = p->extent -
+ EXT4_EXTENT_FIRST(p->header);
}
- /* 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;
- }
+ header = p->header;
- /* OK. use inode's group */
- return ext4_fs_inode_to_goal_block(inode_ref);
-}
+ if (ptr < ext4_extent_header_get_nentries(header) - 1)
+ /* We found a path with non-rightmost pointer */
+ break;
-/*
- * 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;
+ /* Move to the parent path */
+ p++;
+ depth++;
+ }
- 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 we can't find a path with a non-rightmost pointer,
+ * we are already on the last extent, just return in this
+ * case */
+ if (depth > rootdepth)
+ goto out;
-#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;
+ /* Increment the pointer once we found a path with non-rightmost
+ * pointer */
+ if (p->depth)
+ p->index++;
+ else
+ p->extent++;
- 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));
+ if (depth) {+ /* We need to reload the paths to leaf if the path iterator
+ * is not pointing to the leaf */
+ ret = ext4_extent_reload_paths(inode_ref, path, depth, false);
+ if (ret != EOK)
+ goto out;
}
- 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;
+ /* Found the next extent */
+ nonext = false;
+out:
+ if (nonextp)
+ *nonextp = nonext;
- tail = find_ext4_extent_tail(eh);
- tail->et_checksum = to_le32(ext4_ext_block_csum(inode_ref, eh));
+ return ret;
}
-static int ext4_ext_dirty(struct ext4_inode_ref *inode_ref,
- struct ext4_extent_path *path)
+/**@brief Seek to the previous extent
+ * @param inode_ref I-node the extent tree resides in
+ * @param path Path in the extent tree
+ * @param noprevp Output value - whether the current extent is the
+ * left-most extent already
+ * @return 0 on success, EIO on currupted block, or return values of
+ * ext4_trans_block_get(). */
+int
+ext4_extent_decrement(struct ext4_inode_ref *inode_ref,
+ struct ext4_extent_path *path,
+ bool *noprevp)
{- if (path->block.lb_id)
- ext4_trans_set_block_dirty(path->block.buf);
- else
- inode_ref->dirty = true;
+ int ret = EOK;
+ uint16_t ptr;
+ bool noprev = true;
+ uint16_t depth = 0;
+ struct ext4_extent_path *p;
+ uint16_t rootdepth;
- return EOK;
-}
+ p = path;
+ rootdepth = ext4_extent_tree_depth(inode_ref);
-static void ext4_ext_drop_refs(struct ext4_inode_ref *inode_ref,
- struct ext4_extent_path *path, bool keep_other)
-{- int32_t depth, i;
+ /* Iterate the paths from the leaf to the root */
+ while (depth <= rootdepth) {+ if (p->depth) {+ ptr = p->index -
+ EXT4_EXTENT_FIRST_INDEX(p->header);
+ } else {+ ptr = p->extent -
+ EXT4_EXTENT_FIRST(p->header);
+ }
- if (!path)
- return;
- if (keep_other)
- depth = 0;
- else
- depth = path->depth;
+ if (ptr)
+ /* We found a path with non-leftmost pointer */
+ break;
- 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);
+ /* Move to the parent path */
+ p++;
+ depth++;
+ }
- ext4_block_set(inode_ref->fs->bdev, &path->block);
- }
+ /* If we can't find a path with a non-leftmost pointer,
+ * we are already on the first extent, just return in this
+ * case */
+ if (depth > rootdepth)
+ goto out;
+
+ /* Decrement the pointer once we found a path with non-leftmost
+ * pointer */
+ if (p->depth)
+ p->index--;
+ else
+ p->extent--;
+
+ if (depth) {+ /* We need to reload the paths to leaf if the path iterator
+ * is not pointing to the leaf */
+ ret = ext4_extent_reload_paths(inode_ref, path, depth, true);
+ if (ret != EOK)
+ goto out;
}
+
+ /* Found the previous extent */
+ noprev = false;
+out:
+ if (noprevp)
+ *noprevp = noprev;
+ return ret;
}
-/*
- * 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)
+
+/**@brief Update the index of nodes starting from leaf
+ * @param inode_ref I-node the extent tree resides in
+ * @param path Path in the extent tree
+ * @param force set this to true if insertion, deletion or modification
+ * of starting logical block of the first index in a node is made at non-leaf
+ * level */
+static void ext4_extent_update_index(struct ext4_inode_ref *inode_ref,
+ struct ext4_extent_path *path,
+ bool force)
{- struct ext4_extent_tail *tail;
- struct ext4_sblock *sb = &inode_ref->fs->sb;
- const char *error_msg;
+ uint16_t rootdepth;
+ struct ext4_extent_path *p;
- USED(pblk);
+ rootdepth = ext4_extent_tree_depth(inode_ref);
- 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;
- }
+ /* Iterate the paths from the parent of the leaf to the root */
+ for (p = path + 1; p <= path + rootdepth; p++) {+ struct ext4_extent_path *chldp;
+ struct ext4_extent_header *child_header;
+ ptrdiff_t chldptr;
- 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);
- }
- }
+ /* This points to the child path of the current path */
+ chldp = p - 1;
+ child_header = chldp->header;
- return EOK;
+ if (!chldp->depth)
+ chldptr = chldp->extent -
+ EXT4_EXTENT_FIRST(child_header);
+ else
+ chldptr = chldp->index -
+ EXT4_EXTENT_FIRST_INDEX(child_header);
-corrupted:
- USED(error_msg);
- ext4_dbg(DEBUG_EXTENT, "Bad extents B+ tree block: %s. "
- "Blocknr: %" PRId64 "\n",
- error_msg, pblk);
- return EIO;
-}
+ /* If the modification on the child node is not made on the
+ * first slot of the node, we are done */
+ if (chldptr)
+ break;
-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;
+ if (p->depth > 1) {+ struct ext4_extent_index *idx = p->index;
+ struct ext4_extent_index *chldidx =
+ chldp->index;
+ ext4_lblk_t iblock, chldiblock;
- USED(flags);
- err = ext4_trans_block_get(inode_ref->fs->bdev, bh, pblk);
- if (err != EOK)
- goto errout;
+ iblock = ext4_extent_index_get_iblock(idx);
+ chldiblock = ext4_extent_index_get_iblock(chldidx);
- err = ext4_ext_check(inode_ref, ext_block_hdr(bh), depth, pblk);
- if (err != EOK)
- goto errout;
+ if (iblock != chldiblock) {+ /* If the starting logical block of the first
+ * index of the child node is modified, we
+ * update the starting logical block of index
+ * pointing to the child node */
+ ext4_extent_index_set_iblock(idx, chldiblock);
+ ext4_extent_path_dirty(inode_ref, path,
+ p->depth);
+ } else if (!force)
+ /* We do not need to continue the iteration */
+ break;
+ } else {+ struct ext4_extent_index *idx = p->index;
+ struct ext4_extent *chldext = chldp->extent;
+ ext4_lblk_t iblock, chldiblock;
- return EOK;
-errout:
- if (bh->lb_id)
- ext4_block_set(inode_ref->fs->bdev, bh);
+ iblock = ext4_extent_index_get_iblock(idx);
+ chldiblock = ext4_extent_get_iblock(chldext);
- return err;
+ if (iblock != chldiblock) {+ /* If the starting logical block of the first
+ * extent of the child node is modified, we
+ * update the starting logical block of index
+ * pointing to the child node */
+ ext4_extent_index_set_iblock(idx, chldiblock);
+ ext4_extent_path_dirty(inode_ref, path,
+ p->depth);
+ } else if (!force)
+ /* We do not need to continue the iteration */
+ break;
+ }
+ };
}
-/*
- * 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)
+/**@brief Make the tree grow up by one level
+ * @param inode_ref I-node the extent tree resides in
+ * @param path Path in the extent tree
+ * @param new_fblock The newly allocated block for tree growth
+ * @return Error code */
+static int ext4_extent_grow_tree(struct ext4_inode_ref *inode_ref,
+ struct ext4_extent_path *path,
+ ext4_fsblk_t newfblock)
{- struct ext4_extent_header *eh = path->header;
- struct ext4_extent_index *r, *l, *m;
+ int rc;
+ uint16_t ptr;
+ struct ext4_block block;
+ ext4_lblk_t chldiblock;
+ uint16_t rootdepth;
+ struct ext4_block rootblock;
+ struct ext4_extent_header *rooteh;
+ struct ext4_extent_path *nrootp;
+ struct ext4_extent_path *rootp;
+ uint32_t blocksz;
+ uint16_t maxnentries;
- 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;
+ rootdepth = ext4_extent_tree_depth(inode_ref);
+ rootp = path + rootdepth;
+ nrootp = rootp + 1;
+ rootblock = rootp->block;
+ rooteh = rootp->header;
+ blocksz = ext4_sb_get_block_size(&inode_ref->fs->sb);
+
+ /* Store the extent/index offset so that we can recover the
+ * pointer to it later */
+ if (rootdepth) {+ ptr = rootp->index -
+ EXT4_EXTENT_FIRST_INDEX(rootp->header);
+ } else {+ ptr = rootp->extent -
+ EXT4_EXTENT_FIRST(rootp->header);
}
+ /* Prepare a buffer for newly allocated block */
+ rc = ext4_trans_block_get_noread(inode_ref->fs->bdev, &block, newfblock);
+ if (rc != EOK)
+ return rc;
- path->index = l - 1;
-}
+ /* Initialize newly allocated block */
+ memset(block.data, 0, blocksz);
-/*
- * 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;
+ /* Move data from root to the new block */
+ memcpy(block.data, inode_ref->inode->blocks,
+ EXT4_INODE_BLOCKS * sizeof(uint32_t));
- if (eh->entries_count == 0) {- /*
- * this leaf is empty:
- * we get such a leaf in split/add case
- */
- return;
+ /* Update old root path */
+ rootp->block = block;
+ rootp->header = (struct ext4_extent_header *)block.data;
+ if (rootp->depth) {+ rootp->index =
+ EXT4_EXTENT_FIRST_INDEX(rootp->header) +
+ ptr;
+
+ maxnentries =
+ (blocksz - sizeof(struct ext4_extent_header)) /
+ sizeof(struct ext4_extent_index);
+#if CONFIG_EXTENT_DEBUG_AGGRESSIVE
+ maxnentries = 5;
+#endif /* CONFIG_EXTENT_DEBUG_AGGRESSIVE */
+ rootp->extent = NULL;
+ chldiblock =
+ ext4_extent_index_get_iblock(EXT4_EXTENT_FIRST_INDEX(rootp->header));
+ } else {+ rootp->extent =
+ EXT4_EXTENT_FIRST(rootp->header) +
+ ptr;
+ maxnentries =
+ (blocksz - sizeof(struct ext4_extent_header)) /
+ sizeof(struct ext4_extent);
+#if CONFIG_EXTENT_DEBUG_AGGRESSIVE
+ maxnentries = 5;
+#endif /* CONFIG_EXTENT_DEBUG_AGGRESSIVE */
+ rootp->index = NULL;
+ chldiblock =
+ ext4_extent_get_iblock(EXT4_EXTENT_FIRST(rootp->header));
}
- l = EXT_FIRST_EXTENT(eh) + 1;
- r = EXT_LAST_EXTENT(eh);
+ /* Re-initialize new root metadata */
+ nrootp->depth = rootdepth + 1;
+ nrootp->block = rootblock;
+ nrootp->header = rooteh;
+ nrootp->extent = NULL;
+ nrootp->index = EXT4_EXTENT_FIRST_INDEX(nrootp->header);
- while (l <= r) {- m = l + (r - l) / 2;
- if (block < to_le32(m->first_block))
- r = m - 1;
- else
- l = m + 1;
- }
+ ext4_extent_header_set_depth(nrootp->header, nrootp->depth);
- path->extent = l - 1;
+ /* Create new entry in root */
+ ext4_extent_header_set_nentries(nrootp->header, 1);
+ ext4_extent_index_set_iblock(nrootp->index, chldiblock);
+ ext4_extent_index_set_fblock(nrootp->index, newfblock);
+
+ /* Since new_root belongs to on-disk inode,
+ * we don't do checksum here */
+ inode_ref->dirty = true;
+
+ /* Set upper limit for entries count of old root */
+ ext4_extent_header_set_max_nentries(rootp->header, maxnentries);
+
+ ext4_extent_path_dirty(inode_ref, path, rootp->depth);
+
+ return EOK;
}
-static int ext4_find_extent(struct ext4_inode_ref *inode_ref, ext4_lblk_t block,
- struct ext4_extent_path **orig_path, uint32_t flags)
+/**@brief Do splitting on the tree if the leaf is full
+ * @param inode_ref I-node the extent tree resides in
+ * @param path Path in the extent tree for possible splitting
+ * @param nslots number of entries that will be inserted to the
+ * leaf in future.
+ * @return Error code */
+static int ext4_extent_split(struct ext4_inode_ref *inode_ref,
+ struct ext4_extent_path *path,
+ uint16_t nslots)
{- struct ext4_extent_header *eh;
- struct ext4_block bh = EXT4_BLOCK_ZERO();
- ext4_fsblk_t buf_block;
- struct ext4_extent_path *path = *orig_path;
- int32_t depth, ppos = 0;
- int32_t i;
int ret;
+ uint16_t i;
+ ext4_fsblk_t goal;
+ uint16_t rootdepth;
+ struct ext4_extent_path *p;
+ uint32_t blocksz;
+ /* Number of new blocks to be allocated */
+ uint16_t nnewfblocks = 0;
+ /* Number of node to be split */
+ uint16_t nsplits = 0;
+ /* Array of new blocks allocated */
+ ext4_fsblk_t *newfblocks;
+ /* The index of the right block inserted last time */
+ ext4_lblk_t lastiblock = 0;
+ /* Whether we updated child path to point to the right block
+ * at the previous round during splitting */
+ bool prevrblock = false;
- eh = ext_inode_hdr(inode_ref->inode);
- depth = ext_depth(inode_ref->inode);
+ blocksz = ext4_sb_get_block_size(&inode_ref->fs->sb);
+ rootdepth = ext4_extent_tree_depth(inode_ref);
+ goal = ext4_extent_tree_alloc_goal(inode_ref);
- if (path) {- ext4_ext_drop_refs(inode_ref, path, 0);
- if (depth > path[0].maxdepth) {- ext4_free(path);
- *orig_path = path = NULL;
+ /* First calculate how many levels will be touched */
+ for (p = path; p <= path + rootdepth; p++) {+ uint16_t entries =
+ ext4_extent_header_get_nentries(p->header);
+ uint16_t limit =
+ ext4_extent_header_get_max_nentries(p->header);
+
+ ext4_assert(entries <= limit);
+ if (!p->depth) {+ if (entries + nslots <= limit)
+ break;
+ } else {+ if (entries < limit)
+ break;
}
+ /* We have to split a node when the tree is full */
+ nnewfblocks++;
+ nsplits++;
}
- if (!path) {- int32_t path_depth = depth + 1;
- /* account possible depth increase */
- path = ext4_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;
+ if (!nnewfblocks)
+ return EOK;
- 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;
- }
+ /* Allocate the array for storing newly allocated blocks */
+ newfblocks = ext4_malloc(sizeof(ext4_fsblk_t) * nnewfblocks);
+ if (!newfblocks)
+ return ENOMEM;
- eh = ext_block_hdr(&bh);
- path[ppos].block = bh;
- path[ppos].header = eh;
- }
+ for (i = 0; i < nnewfblocks; i++) {+ ret = ext4_balloc_alloc_block(inode_ref, goal, newfblocks + i);
+ if (ret != EOK)
+ return ret;
}
- path[ppos].depth = i;
- path[ppos].extent = NULL;
- path[ppos].index = NULL;
+ ext4_dbg(DEBUG_EXTENT,
+ DBG_INFO "nnewfblocks: %" PRIu16 " rootdepth: %" PRIu16 "\n",
+ nnewfblocks, rootdepth);
- /* 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);
+ /* If number of blocks to be allocated is greater than
+ * the depth of root we have to grow the tree */
+ if (nnewfblocks == rootdepth + 1) {+ ext4_dbg(DEBUG_EXTENT, "Growing: \n");
+ nsplits--;
- *orig_path = path;
+ ret = ext4_extent_grow_tree(inode_ref,
+ path, newfblocks[rootdepth]);
+ if (ret != EOK)
+ goto finish;
- ret = EOK;
- return ret;
+ ext4_extent_print_path(inode_ref, path);
-err:
- ext4_ext_drop_refs(inode_ref, path, 0);
- ext4_free(path);
- if (orig_path)
- *orig_path = NULL;
- return ret;
-}
+ /* If we are moving the in-inode leaf to on-block leaf.
+ * we do not need further actions. */
+ if (!rootdepth)
+ goto finish;
-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;
-}
+ ++rootdepth; USED(rootdepth);
+ }
-static int ext4_ext_insert_index(struct ext4_inode_ref *inode_ref,
- struct ext4_extent_path *path, int at,
- ext4_lblk_t insert_index,
- ext4_fsblk_t insert_block, bool set_to_ix)
-{- struct ext4_extent_index *ix;
- struct ext4_extent_path *curp = path + at;
- int len, err;
- struct ext4_extent_header *eh;
+ /* Start splitting */
+ p = path;
+ ext4_dbg(DEBUG_EXTENT, DBG_INFO "Start splitting: \n");
+ for (i = 0; i < nsplits; i++, p++) {+ struct ext4_extent_header *header;
+ uint16_t entries =
+ ext4_extent_header_get_nentries(p->header);
+ uint16_t limit =
+ ext4_extent_header_get_max_nentries(p->header);
+ /* The entry we start shifting to the right block */
+ uint16_t split_ptr = entries / 2;
+ /* The number of entry the right block will have */
+ uint16_t right_entries = entries - split_ptr;
+ /* The current entry */
+ uint16_t curr_ptr;
+ ext4_lblk_t riblock;
+ struct ext4_block block;
- if (curp->index && insert_index == to_le32(curp->index->first_block))
- return EIO;
+ ret = ext4_trans_block_get_noread(inode_ref->fs->bdev,
+ &block, newfblocks[i]);
+ if (ret != EOK)
+ goto finish;
- if (to_le16(curp->header->entries_count) ==
- to_le16(curp->header->max_entries_count))
- return EIO;
+ /* Initialize newly allocated block and remember it */
+ memset(block.data, 0, blocksz);
- 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;
- }
+ header = (void *)block.data;
- if (ix > EXT_MAX_INDEX(eh))
- return EIO;
+ /* Initialize on-disk structure (header) */
+ ext4_extent_header_set_nentries(header,
+ right_entries);
+ ext4_extent_header_set_max_nentries(header, limit);
+ ext4_extent_header_set_magic(header, EXT4_EXTENT_MAGIC);
+ ext4_extent_header_set_depth(header, p->depth);
+ ext4_extent_header_set_generation(header, 0);
- len = EXT_LAST_INDEX(eh) - ix + 1;
- ext4_assert(len >= 0);
- if (len > 0)
- memmove(ix + 1, ix, len * sizeof(struct ext4_extent_index));
+ /* Move some entries from old block to new block */
+ if (p->depth) {+ struct ext4_extent_index *left_index =
+ EXT4_EXTENT_FIRST_INDEX(p->header);
+ struct ext4_extent_index *split_index =
+ left_index + split_ptr;
- 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);
+ riblock = ext4_extent_index_get_iblock(split_index);
+ ext4_dbg(DEBUG_EXTENT,
+ DBG_INFO "depth: %" PRIu32 ", riblock: %" PRIu32 "\n",
+ p->depth, riblock);
- if (ix > EXT_LAST_INDEX(eh)) {- err = EIO;
- goto out;
- }
+ curr_ptr = p->index - left_index;
- err = ext4_ext_dirty(inode_ref, curp);
+ memcpy(EXT4_EXTENT_FIRST_INDEX(header),
+ split_index,
+ right_entries * EXT4_EXTENT_INDEX_SIZE);
+ memset(split_index, 0,
+ right_entries * EXT4_EXTENT_INDEX_SIZE);
+ } else {+ struct ext4_extent *left_extent =
+ EXT4_EXTENT_FIRST(p->header);
+ struct ext4_extent *split_extent =
+ left_extent + split_ptr;
-out:
- if (err == EOK && set_to_ix) {- curp->index = ix;
- curp->p_block = ext4_idx_pblock(ix);
- }
- return err;
-}
+ riblock = ext4_extent_get_iblock(split_extent);
+ ext4_dbg(DEBUG_EXTENT,
+ DBG_INFO "depth: %" PRIu32 ", riblock: %" PRIu32 "\n",
+ p->depth, riblock);
-static int ext4_ext_split_node(struct ext4_inode_ref *inode_ref,
- struct ext4_extent_path *path, int at,
- struct ext4_extent *newext,
- struct ext4_extent_path *npath,
- bool *ins_right_leaf)
-{- int i, npath_at, ret;
- ext4_lblk_t insert_index;
- ext4_fsblk_t newblock;
- int depth = ext_depth(inode_ref->inode);
- npath_at = depth - at;
+ curr_ptr = p->extent - left_extent;
- ext4_assert(at > 0);
+ memcpy(EXT4_EXTENT_FIRST(header),
+ split_extent,
+ right_entries * EXT4_EXTENT_SIZE);
+ memset(split_extent, 0,
+ right_entries * EXT4_EXTENT_SIZE);
+ }
- if (path[depth].extent != EXT_MAX_EXTENT(path[depth].header))
- insert_index = path[depth].extent[1].first_block;
- else
- insert_index = newext->first_block;
+ /* Set entries count in left node */
+ ext4_extent_header_set_nentries(p->header,
+ entries - right_entries);
- for (i = depth; i >= at; i--, npath_at--) {- struct ext4_block bh = EXT4_BLOCK_ZERO();
+ /* Decide whether we need to update the path to
+ * point to right block or not */
+ if (curr_ptr >= split_ptr) {+ /* Update the checksum for the left block */
+ ext4_extent_path_dirty(inode_ref, path, p->depth);
- /* 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 != EOK)
- goto cleanup;
+ /* Put back the left block */
+ ret = ext4_block_set(inode_ref->fs->bdev,
+ &p->block);
+ if (ret != EOK)
+ goto finish;
- /* For write access.*/
- ret = ext4_trans_block_get_noread(inode_ref->fs->bdev, &bh,
- newblock);
- if (ret != EOK)
- goto cleanup;
+ /* Update pointers in extent path structure to
+ * point to right block */
+ p->block = block;
+ p->header = (void *)block.data;
- if (i == depth) {- /* start copy from next extent */
- int m = EXT_MAX_EXTENT(path[i].header) - path[i].extent;
- struct ext4_extent_header *neh;
- struct ext4_extent *ex;
- neh = ext_block_hdr(&bh);
- ex = EXT_FIRST_EXTENT(neh);
- ext4_ext_init_header(inode_ref, neh, 0);
- if (m) {- memmove(ex, path[i].extent + 1,
- sizeof(struct ext4_extent) * m);
- neh->entries_count =
- to_le16(to_le16(neh->entries_count) + m);
- path[i].header->entries_count = to_le16(
- to_le16(path[i].header->entries_count) - m);
- ret = ext4_ext_dirty(inode_ref, path + i);
- if (ret != EOK)
- goto cleanup;
-
- npath[npath_at].p_block = ext4_ext_pblock(ex);
- npath[npath_at].extent = ex;
+ if (p->depth) {+ p->index =
+ EXT4_EXTENT_FIRST_INDEX(p->header) +
+ curr_ptr - split_ptr;
} else {- npath[npath_at].p_block = 0;
- npath[npath_at].extent = NULL;
+ p->extent =
+ EXT4_EXTENT_FIRST(p->header) +
+ curr_ptr - split_ptr;
}
+ } else {+ /* Update the checksum for the right block */
+ ext4_extent_block_csum_set(inode_ref, header);
+ ext4_trans_set_block_dirty(block.buf);
- npath[npath_at].depth = to_le16(neh->depth);
- npath[npath_at].maxdepth = 0;
- npath[npath_at].index = NULL;
- npath[npath_at].header = neh;
- npath[npath_at].block = bh;
+ /* Put back the right block */
+ ret = ext4_block_set(inode_ref->fs->bdev,
+ &block);
+ if (ret != EOK)
+ goto finish;
+ }
- ext4_trans_set_block_dirty(bh.buf);
- } else {- int m = EXT_MAX_INDEX(path[i].header) - path[i].index;
- struct ext4_extent_header *neh;
- struct ext4_extent_index *ix;
- neh = ext_block_hdr(&bh);
- ix = EXT_FIRST_INDEX(neh);
- ext4_ext_init_header(inode_ref, neh, depth - i);
- ix->first_block = to_le32(insert_index);
- ext4_idx_store_pblock(ix,
- npath[npath_at + 1].block.lb_id);
- neh->entries_count = to_le16(1);
- if (m) {- memmove(ix + 1, path[i].index + 1,
- sizeof(struct ext4_extent) * m);
- neh->entries_count =
- to_le16(to_le16(neh->entries_count) + m);
- path[i].header->entries_count = to_le16(
- to_le16(path[i].header->entries_count) - m);
- ret = ext4_ext_dirty(inode_ref, path + i);
- if (ret != EOK)
- goto cleanup;
- }
+ /* Append an index after the current index */
+ if (p->depth) {+ struct ext4_extent_index *index = p->index + 1;
- npath[npath_at].p_block = ext4_idx_pblock(ix);
- npath[npath_at].depth = to_le16(neh->depth);
- npath[npath_at].maxdepth = 0;
- npath[npath_at].extent = NULL;
- npath[npath_at].index = ix;
- npath[npath_at].header = neh;
- npath[npath_at].block = bh;
+ /* If we updated the path to right block in the previous
+ * round, we update the pointer in the path to point to
+ * the right block */
+ if (prevrblock)
+ p->index++;
- ext4_trans_set_block_dirty(bh.buf);
+ if (index <= EXT4_EXTENT_LAST_INDEX(p->header)) {+ uint16_t nindex =
+ EXT4_EXTENT_LAST_INDEX(p->header) -
+ index + 1;
+
+ memmove(index + 1,
+ index,
+ nindex * EXT4_EXTENT_INDEX_SIZE);
+ }
+ memset(index, 0, EXT4_EXTENT_INDEX_SIZE);
+ ext4_extent_index_set_iblock(index, lastiblock);
+ ext4_extent_index_set_fblock(index, newfblocks[i - 1]);
+
+ entries = ext4_extent_header_get_nentries(p->header);
+ ext4_extent_header_set_nentries(p->header,
+ entries + 1);
}
+
+ ext4_extent_path_dirty(inode_ref, path, p->depth);
+
+ /* We may have updated the path to right block in this round */
+ prevrblock = curr_ptr >= split_ptr;
+
+ /* We also update the lastiblock variable to the index of the
+ * right block */
+ lastiblock = riblock;
}
- newblock = 0;
- /*
- * If newext->first_block can be included into the
- * right sub-tree.
- */
- if (to_le32(newext->first_block) < insert_index)
- *ins_right_leaf = false;
- else
- *ins_right_leaf = true;
+ /* Append an index after the current index */
+ if (p->depth) {+ struct ext4_extent_index *index = p->index + 1;
+ uint16_t entries =
+ ext4_extent_header_get_nentries(p->header);
- ret = ext4_ext_insert_index(inode_ref, path, at - 1, insert_index,
- npath[0].block.lb_id, *ins_right_leaf);
+ /* If we updated the path to right block in the previous
+ * round, we update the pointer in the path to point to
+ * the right block */
+ if (prevrblock)
+ p->index++;
-cleanup:
- if (ret != EOK) {- if (newblock)
- ext4_ext_free_blocks(inode_ref, newblock, 1, 0);
+ if (index <= EXT4_EXTENT_LAST_INDEX(p->header)) {+ uint16_t nindex =
+ EXT4_EXTENT_LAST_INDEX(p->header) -
+ index + 1;
- npath_at = depth - at;
- while (npath_at >= 0) {- if (npath[npath_at].block.lb_id) {- newblock = npath[npath_at].block.lb_id;
- ext4_block_set(inode_ref->fs->bdev,
- &npath[npath_at].block);
- ext4_ext_free_blocks(inode_ref, newblock, 1, 0);
- memset(&npath[npath_at].block, 0,
- sizeof(struct ext4_block));
- }
- npath_at--;
+ memmove(index + 1,
+ index,
+ nindex * EXT4_EXTENT_INDEX_SIZE);
}
+ memset(index, 0, EXT4_EXTENT_INDEX_SIZE);
+ ext4_extent_index_set_iblock(index, lastiblock);
+ ext4_extent_index_set_fblock(index, newfblocks[i - 1]);
+ ext4_extent_header_set_nentries(p->header,
+ entries + 1);
+
+ ext4_extent_path_dirty(inode_ref, path, p->depth);
}
+
+ ret = EOK;
+finish:
+ if (ret != EOK)
+ for (i = 0; i < nnewfblocks; i++)
+ ext4_balloc_free_block(inode_ref, newfblocks[i]);
+
+ ext4_free(newfblocks);
return ret;
}
-/*
- * 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)
+/**@brief Insert an extent into the extent tree
+ * @param inode_ref I-node the extent tree resides in
+ * @param path Path in the extent tree for possible splitting
+ * @param ext Extent to be inserted
+ * @return Error code */
+static int ext4_extent_insert(struct ext4_inode_ref *inode_ref,
+ struct ext4_extent_path *path,
+ struct ext4_extent *ext)
{- 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;
+ int ret;
+ uint16_t entries;
+ struct ext4_extent_path *p;
- eh = path[depth].header;
- ex = path[depth].extent;
+ /* Split and grow the tree if necessary */
+ ret = ext4_extent_split(inode_ref, path, 1);
+ if (ret != EOK)
+ return ret;
- if (ex == NULL || eh == NULL)
- return EIO;
+ p = path;
+ entries = ext4_extent_header_get_nentries(p->header);
- if (depth == 0) {- /* there is no tree at all */
- return EOK;
- }
+ ext4_dbg(DEBUG_EXTENT, DBG_INFO "After splitting: \n");
+ ext4_extent_print_path(inode_ref, path);
- if (ex != EXT_FIRST_EXTENT(eh)) {- /* we correct tree if first leaf got modified only */
- return EOK;
+ if (!p->extent) {+ p->extent = EXT4_EXTENT_FIRST(p->header);
+ } else {+ ext4_lblk_t iblock;
+
+ iblock = ext4_extent_get_iblock(p->extent);
+ if (ext4_extent_get_iblock(ext) > iblock)
+ p->extent++;
}
- 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;
+ if (p->extent <= EXT4_EXTENT_LAST(p->header)) {+ uint16_t nextent =
+ EXT4_EXTENT_LAST(p->header) -
+ p->extent + 1;
- 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;
+ ext4_dbg(DEBUG_EXTENT,
+ DBG_INFO "%" PRIu16 " extents to be shifted at leaf\n",
+ nextent);
+
+ memmove(p->extent + 1,
+ p->extent,
+ nextent * EXT4_EXTENT_SIZE);
}
+ memcpy(p->extent, ext, EXT4_EXTENT_SIZE);
+ ext4_extent_header_set_nentries(p->header,
+ entries + 1);
- return err;
-}
+ ext4_extent_path_dirty(inode_ref, path, p->depth);
-static inline 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 0;
+ ext4_dbg(DEBUG_EXTENT, DBG_INFO "Before updating indice: \n");
+ ext4_extent_print_path(inode_ref, path);
-#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 0;
- } else if (ext4_ext_get_actual_len(ex1) + ext4_ext_get_actual_len(ex2) >
- EXT_INIT_MAX_LEN)
- return 0;
-#endif
+ /* Update the index of the first entry in parents node */
+ ext4_extent_update_index(inode_ref, path, false);
- if (to_le32(ex2->first_block) + ext4_ext_get_actual_len(ex2) !=
- to_le32(ex1->first_block))
- return 0;
+ ext4_dbg(DEBUG_EXTENT, DBG_INFO "At the end: \n");
+ ext4_extent_print_path(inode_ref, path);
- return 1;
+ return ret;
}
-static inline bool ext4_ext_can_append(struct ext4_extent *ex1,
- struct ext4_extent *ex2)
+/**@brief Delete an item from the node at @depth pointed
+ * @param inode_ref I-node the extent tree resides in
+ * @param path Path in the extent tree for possible splitting
+ * @param depth The level of the node to be operated on
+ * @return Error code */
+static void
+ext4_extent_delete_item(struct ext4_inode_ref *inode_ref,
+ struct ext4_extent_path *path,
+ uint16_t depth)
{- if (ext4_ext_pblock(ex1) + ext4_ext_get_actual_len(ex1) !=
- ext4_ext_pblock(ex2))
- return 0;
+ uint16_t nitems;
+ struct ext4_extent_header *hdr;
+ struct ext4_extent_path *p;
-#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 0;
- } else if (ext4_ext_get_actual_len(ex1) + ext4_ext_get_actual_len(ex2) >
- EXT_INIT_MAX_LEN)
- return 0;
-#endif
+ p = path + depth;
- if (to_le32(ex1->first_block) + ext4_ext_get_actual_len(ex1) !=
- to_le32(ex2->first_block))
- return 0;
+ hdr = p->header;
+ ext4_assert(ext4_extent_header_get_nentries(hdr));
- return 1;
+ if (p->depth) {+ struct ext4_extent_index *idx;
+
+ idx = p->index;
+ nitems = EXT4_EXTENT_LAST_INDEX(hdr) - (idx + 1) + 1;
+ if (nitems) {+ memmove(idx, idx + 1,
+ nitems * EXT4_EXTENT_INDEX_SIZE);
+ memset(EXT4_EXTENT_LAST(hdr), 0,
+ EXT4_EXTENT_INDEX_SIZE);
+ } else {+ memset(idx, 0, EXT4_EXTENT_INDEX_SIZE);
+ }
+ } else {+ struct ext4_extent *ext;
+
+ ext = p->extent;
+ nitems = EXT4_EXTENT_LAST(hdr) - (ext + 1) + 1;
+ if (nitems) {+ memmove(ext, ext + 1,
+ nitems * EXT4_EXTENT_SIZE);
+ memset(EXT4_EXTENT_LAST(hdr), 0,
+ EXT4_EXTENT_SIZE);
+ } else {+ memset(ext, 0, EXT4_EXTENT_SIZE);
+ }
+ }
+
+ nitems = ext4_extent_header_get_nentries(hdr) - 1;
+ ext4_extent_header_set_nentries(hdr,
+ nitems);
+ ext4_extent_path_dirty(inode_ref, path, p->depth);
}
-static int ext4_ext_insert_leaf(struct ext4_inode_ref *inode_ref,
- struct ext4_extent_path *path, int at,
- struct ext4_extent *newext, int flags,
- bool *need_split)
+/**@brief Remove extents in a leaf starting
+ * from the current extent and having
+ * key less than or equal to @toiblock.
+ * @param inode_ref I-node the tree resides in
+ * @param path Path in the extent tree
+ * @param toiblock The logical block
+ * @param stopp Output value to tell whether the caller should
+ * stop deletion. Will be set to true if an extent having key greater
+ * than @toiblock is met.
+ * @return 0 if there is no error, or return values of blocks
+ * freeing routine. */
+static int
+ext4_extent_delete_leaf(struct ext4_inode_ref *inode_ref,
+ struct ext4_extent_path *path,
+ ext4_lblk_t toiblock,
+ bool *stopp)
{- struct ext4_extent_path *curp = path + at;
- struct ext4_extent *ex = curp->extent;
- int len, err, unwritten;
- struct ext4_extent_header *eh;
+ int ret = EOK;
+ uint16_t nitems;
+ struct ext4_extent *ext;
+ struct ext4_extent_header *hdr;
+ struct ext4_extent_path *p;
- *need_split = false;
+ p = path;
+ *stopp = false;
- if (curp->extent &&
- to_le32(newext->first_block) == to_le32(curp->extent->first_block))
- return EIO;
+ while (1) {+ bool unwritten;
+ uint16_t ptr;
+ uint16_t len;
+ uint16_t flen;
+ ext4_lblk_t endiblock;
+ ext4_lblk_t startiblock;
+ ext4_fsblk_t blocknr;
- 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);
+ hdr = p->header;
+ nitems = ext4_extent_header_get_nentries(hdr);
+ ptr = p->extent - EXT4_EXTENT_FIRST(hdr);
- err = ext4_ext_dirty(inode_ref, curp);
- goto out;
- }
+ ext4_assert(nitems > 0);
- 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);
+ ext = p->extent;
+ blocknr = ext4_extent_get_fblock(ext);
+ startiblock = ext4_extent_get_iblock(ext);
+ endiblock = startiblock + ext4_extent_get_nblocks(ext) - 1;
+ len = endiblock - startiblock + 1;
+ unwritten = EXT4_EXT_IS_UNWRITTEN(ext);
- err = ext4_ext_dirty(inode_ref, curp);
- goto out;
+ /* We have to stop if the extent's key
+ * is greater than @toiblock. */
+ if (toiblock < startiblock) {+ *stopp = true;
+ break;
}
- }
- if (to_le16(curp->header->entries_count) ==
- to_le16(curp->header->max_entries_count)) {- err = EIO;
- *need_split = 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;
+ if (toiblock < endiblock) {+ /* In case @toiblock is smaller than the last
+ * logical block of the extent, we do not
+ * need to delete the extent. We modify it only. */
+
+ /* Unmap the underlying blocks. */
+ flen = toiblock - startiblock + 1;
+ ext4_dbg(DEBUG_EXTENT,
+ DBG_INFO "Freeing: %" PRIu64 ":%" PRIu16 "\n",
+ blocknr, flen);
+ ext4_balloc_free_blocks(inode_ref, blocknr, flen);
+
+ /* Adjust the starting block and length of the
+ * current extent. */
+ blocknr += flen;
+ startiblock = toiblock + 1;
+ len = endiblock - startiblock + 1;
+ ext4_extent_set_iblock(ext, startiblock);
+ ext4_extent_set_nblocks(ext, len, unwritten);
+ ext4_extent_set_fblock(ext, blocknr);
+
+ ext4_extent_path_dirty(inode_ref, path, p->depth);
+
+ *stopp = 1;
+ break;
}
- }
- len = EXT_LAST_EXTENT(eh) - ex + 1;
- ext4_assert(len >= 0);
- if (len > 0)
- memmove(ex + 1, ex, len * sizeof(struct ext4_extent));
+ /* Delete the extent pointed to by the path. */
+ ext4_extent_delete_item(inode_ref, path, 0);
+ nitems--;
- if (ex > EXT_MAX_EXTENT(eh)) {- err = EIO;
- goto out;
+ /* Unmap the underlying blocks. */
+ flen = len;
+ ext4_dbg(DEBUG_EXTENT,
+ DBG_INFO "Freeing: %" PRIu64 ":%" PRIu16 "\n",
+ blocknr, flen);
+ ext4_balloc_free_blocks(inode_ref, blocknr, flen);
+
+ /* There are no more items we could delete. */
+ if (ptr >= nitems)
+ break;
}
+ return ret;
+}
- 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);
+/**@brief Remove the current index at specified level.
+ * @param cur Cursor to an extent tree
+ * @param depth The level where deletion takes place at
+ * @return 0 if there is no error, or return values of blocks
+ * freeing routine. */
+static int
+ext4_extent_delete_node(struct ext4_inode_ref *inode_ref,
+ struct ext4_extent_path *path,
+ uint16_t depth)
+{+ int ret = EOK;
+ ext4_fsblk_t fblock;
+ struct ext4_extent_index *idx;
+ struct ext4_extent_header *hdr;
+ struct ext4_extent_path *p;
- if (ex > EXT_LAST_EXTENT(eh)) {- err = EIO;
- goto out;
- }
+ /* If we leave nothing in the node after deletion of
+ * an item, we free the block and delete the index
+ * of the node. Get the respective key of the node
+ * in the parent level */
+ p = path + depth;
+ hdr = p->header;
+ ext4_assert(ext4_extent_header_get_nentries(hdr) > 0);
+ idx = p->index;
+ fblock = ext4_extent_index_get_fblock(idx);
- err = ext4_ext_correct_indexes(inode_ref, path);
- if (err != EOK)
- goto out;
- err = ext4_ext_dirty(inode_ref, curp);
+ /* Delete the index pointed to by the path. */
+ ext4_extent_delete_item(inode_ref, path, depth);
-out:
- if (err == EOK) {- curp->extent = ex;
- curp->p_block = ext4_ext_pblock(ex);
- }
+ /* Free the block of it. */
+ ext4_dbg(DEBUG_EXTENT,
+ DBG_INFO "Freeing: %" PRIu64 ":%" PRIu16 "\n",
+ fblock, 1);
+ ext4_balloc_free_blocks(inode_ref, fblock, 1);
- return err;
+ return ret;
}
-/*
- * 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
+/**@brief Delete the mapping in extent tree starting from \p fromiblock to
+ * \p toiblock inclusively.
+ * @param cur Cursor to an extent tree
+ * @return 0 on success, ENOENT if there is no item to be deleted,
+ * return values of ext4_ext_increment(), ext4_ext_insert(),
+ * ext4_ext_delete_leaf(), ext4_ext_delete_node() ext4_ext_reload_paths(),
+ * ext4_ext_tree_shrink(). Cursor MUST be discarded after deletion.
*/
-static int ext4_ext_grow_indepth(struct ext4_inode_ref *inode_ref,
- uint32_t flags)
+int ext4_extent_remove_space(struct ext4_inode_ref *inode_ref,
+ ext4_lblk_t fromiblock,
+ ext4_lblk_t toiblock)
{- struct ext4_extent_header *neh;
- struct ext4_block bh = EXT4_BLOCK_ZERO();
- ext4_fsblk_t newblock, goal;
- int err = EOK;
+ int ret;
+ uint16_t nitems;
+ int rootdepth;
+ struct ext4_extent_header *hdr;
+ struct ext4_extent *ext;
+ ext4_lblk_t endiblock;
+ ext4_lblk_t startiblock;
+ struct ext4_extent_path *path, *p;
- /* 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);
+ rootdepth = ext4_extent_tree_depth(inode_ref);
- newblock = ext4_new_meta_blocks(inode_ref, goal, flags, NULL, &err);
- if (newblock == 0)
- return err;
+ ret = ext4_extent_find_extent(inode_ref, fromiblock, &path);
+ if (ret != EOK)
+ return ret;
- /* # */
- 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;
- }
+ p = path;
+ hdr = p->header; USED(hdr);
- /* move top-level index/leaf into new block */
- memmove(bh.data, inode_ref->inode->blocks,
- sizeof(inode_ref->inode->blocks));
+ /* We return EOK even if the whole extent tree is empty. */
+ if (!ext4_extent_header_get_nentries(path->header))
+ goto out;
- /* 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));
+ /* Calculate the last logical block of the current extent. */
+ ext4_dbg(DEBUG_EXTENT, DBG_INFO "At start of remove_space: \n");
+ ext4_extent_print_path(inode_ref, path);
- neh->magic = to_le16(EXT4_EXTENT_MAGIC);
- ext4_extent_block_csum_set(inode_ref, neh);
+ ext = p->extent;
+ startiblock = ext4_extent_get_iblock(ext);
+ endiblock = startiblock + ext4_extent_get_nblocks(ext) - 1;
- /* 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_dbg(DEBUG_EXTENT,
+ DBG_INFO "Extent: %" PRIu32 ":%" PRIu16 "\n",
+ startiblock, endiblock);
- ext4_trans_set_block_dirty(bh.buf);
- inode_ref->dirty = true;
- ext4_block_set(inode_ref->fs->bdev, &bh);
+ if (fromiblock > endiblock) {+ bool nonext;
- return err;
-}
+ /* The last logical block of the current extent is smaller
+ * than the first logical block we are going to remove,
+ * thus we increment the extent pointer of the cursor. */
-static inline void ext4_ext_replace_path(struct ext4_inode_ref *inode_ref,
- struct ext4_extent_path *path,
- struct ext4_extent_path *newpath,
- int at)
-{- ext4_ext_drop_refs(inode_ref, path + at, 1);
- path[at] = *newpath;
- memset(newpath, 0, sizeof(struct ext4_extent_path));
-}
+ /* Increment the extent pointer to point to the
+ * next extent. */
+ ret = ext4_extent_increment(inode_ref, path, &nonext);
+ if (ret != EOK)
+ goto out;
-int ext4_ext_insert_extent(struct ext4_inode_ref *inode_ref,
- struct ext4_extent_path **ppath,
- struct ext4_extent *newext, int flags)
-{- int depth, level = 0, ret;
- struct ext4_extent_path *path = *ppath;
- struct ext4_extent_path *npath = NULL;
- bool ins_right_leaf = false;
- bool need_split;
+ /* The current extent is already the last extent in
+ * the tree, so we just return success here. */
+ if (nonext)
+ goto out;
+ } else if (fromiblock > startiblock) {+ bool unwritten;
+ uint16_t len;
-again:
- depth = ext_depth(inode_ref->inode);
- ret = ext4_ext_insert_leaf(inode_ref, path, depth, newext, flags,
- &need_split);
- if (ret == EIO && need_split == true) {- int i;
- for (i = depth, level = 0; i >= 0; i--, level++)
- if (EXT_HAS_FREE_INDEX(path + i))
- break;
+ /* @fromiblock is in the range of the current extent,
+ * but does not sit right on the starting block.
+ *
+ * In this case we need to modify the current extent.
+ * and free some blocks, since we do not really want
+ * to remove and reinsert a new one. */
- /* Do we need to grow the tree? */
- if (i < 0) {- ret = ext4_ext_grow_indepth(inode_ref, 0);
- if (ret != EOK)
- goto out;
+ len = fromiblock - startiblock;
+ unwritten = EXT4_EXT_IS_UNWRITTEN(ext);
+ ext4_extent_set_nblocks(ext, len, unwritten);
- ret = ext4_find_extent(
- inode_ref, to_le32(newext->first_block), ppath, 0);
- if (ret != EOK)
- goto out;
+ ext4_extent_path_dirty(inode_ref, path, p->depth);
- path = *ppath;
- /*
- * After growing the tree, there should be free space in
- * the only child node of the root.
- */
- level--;
- depth++;
- }
+ /* Free the range of blocks starting from @fromiblock
+ * up to either @endiblock or @toiblock. */
+ if (toiblock < endiblock) {+ uint16_t flen;
+ ext4_fsblk_t blocknr;
+ struct ext4_extent next;
- i = depth - (level - 1);
- /* We split from leaf to the i-th node */
- if (level > 0) {- npath = ext4_calloc(1, sizeof(struct ext4_extent_path) *
- (level));
- if (!npath) {- ret = ENOMEM;
- goto out;
- }
- ret = ext4_ext_split_node(inode_ref, path, i, newext,
- npath, &ins_right_leaf);
- if (ret != EOK)
- goto out;
+ /* In case we free up space inside an extent
+ * while not touching both ends, we need to
+ * unavoidably insert a new extent right after
+ * the modified current extent, and that may
+ * cause tree splitting. */
- while (--level >= 0) {- if (ins_right_leaf)
- ext4_ext_replace_path(inode_ref, path,
- &npath[level],
- i + level);
- else if (npath[level].block.lb_id)
- ext4_ext_drop_refs(inode_ref,
- npath + level, 1);
- }
- }
- goto again;
- }
+ /* Now we need to free up space first. */
+ flen = toiblock - fromiblock + 1;
+ blocknr = ext4_extent_get_fblock(ext) + len;
+ ext4_dbg(DEBUG_EXTENT,
+ DBG_INFO "Freeing: %" PRIu64 ":%" PRIu16 "\n",
+ blocknr, flen);
+ ext4_balloc_free_blocks(inode_ref, blocknr, flen);
-out:
- if (ret != EOK) {- if (path)
- ext4_ext_drop_refs(inode_ref, path, 0);
+ blocknr += flen;
+ startiblock = fromiblock + flen;
+ len = endiblock - startiblock + 1;
- while (--level >= 0 && npath) {- if (npath[level].block.lb_id) {- ext4_fsblk_t block = npath[level].block.lb_id;
- ext4_ext_free_blocks(inode_ref, block, 1, 0);
- ext4_ext_drop_refs(inode_ref, npath + level, 1);
- }
- }
- }
- if (npath)
- ext4_free(npath);
+ ext4_extent_set_iblock(&next, startiblock);
+ ext4_extent_set_nblocks(&next, len, unwritten);
+ ext4_extent_set_fblock(&next, blocknr);
+ ret = ext4_extent_insert(inode_ref, path, &next);
- return ret;
-}
+ /* After we free up the space and insert a new
+ * extent, we are done. */
+ goto out;
+ } else {+ bool nonext;
+ uint16_t flen;
+ ext4_fsblk_t blocknr;
-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);
+ /* Otherwise we do not need any insertion,
+ * which also means that no extra space may be
+ * allocated for tree splitting. */
+ flen = endiblock - fromiblock + 1;
+ blocknr = ext4_extent_get_fblock(ext) + len;
- ext4_ext_free_blocks(inode_ref, start, len, 0);
-}
+ /* Now we need to free up space first. */
+ ext4_dbg(DEBUG_EXTENT,
+ DBG_INFO "Freeing: %" PRIu64 ":%" PRIu16 "\n",
+ blocknr, flen);
+ ext4_balloc_free_blocks(inode_ref, blocknr, flen);
-static int ext4_ext_remove_idx(struct ext4_inode_ref *inode_ref,
- struct ext4_extent_path *path, int32_t depth)
-{- int err;
- 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));
+ /* Increment the extent pointer to point to the
+ * next extent. */
+ ret = ext4_extent_increment(inode_ref, path, &nonext);
+ if (ret != EOK || nonext)
+ goto out;
+ }
}
- 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;
+ while (p <= path + rootdepth) {+ struct ext4_extent_path *chldp;
- 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);
+ hdr = p->header;
- /*
- * We may need to correct the paths after the first extents/indexes in
- * a node being modified.
- *
- * We do not need to consider whether there's any extents presenting or
- * not, as garbage will be cleared soon.
- */
- while (i > 0) {- if (path[i].index != EXT_FIRST_INDEX(path[i].header))
- break;
+ if (!p->depth) {+ bool stop;
- path[i - 1].index->first_block = path[i].index->first_block;
- err = ext4_ext_dirty(inode_ref, path + i - 1);
- if (err != EOK)
- break;
+ /* Delete as much extents as we can. */
+ ret = ext4_extent_delete_leaf(inode_ref,
+ path,
+ toiblock,
+ &stop);
+ if (ret != EOK)
+ goto out;
- i--;
- }
- return err;
-}
+ if (stop) {+ /* Since the current extent has its logical
+ * block number greater than @toiblock,
+ * we are done. */
+ break;
+ }
+ /* Since there are no more items in the leaf,
+ * we have to go one level above to switch to the
+ * next leaf. */
+ p++;
+ continue;
+ }
-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)
-{+ chldp = p - 1;
+ nitems = ext4_extent_header_get_nentries(chldp->header);
- 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;
+ /* Now we don't need the children path anymore. */
+ ext4_block_set(inode_ref->fs->bdev, &chldp->block);
+ if (!nitems) {+ ret = ext4_extent_delete_node(inode_ref, path, p->depth);
+ if (ret != EOK)
+ goto out;
- 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);
- /*
- * The 1st case:
- * The position that we start truncation is inside the range of an
- * extent. Here we should calculate the new length of that extent and
- * may start the removal from the next extent.
- */
- if (start < from) {- len -= from - start;
- new_len = from - start;
- start = from;
- start_ex++;
+ if (p->index > EXT4_EXTENT_LAST_INDEX(hdr)) {+ /* Go one level above */
+ p++;
+ } else {+ ret = ext4_extent_reload_paths(inode_ref, path, p->depth, false);
+ if (ret != EOK)
+ goto out;
+ /* Go to the bottom level (aka the leaf). */
+ p = path;
+ }
} else {- /*
- * The second case:
- * The last block to be truncated is inside the range of an
- * extent. We need to calculate the new length and the new
- * start of the extent.
- */
- if (start + len - 1 > to) {- new_len = start + len - 1 - to;
- len -= new_len;
- new_start = to + 1;
- newblock += to + 1 - start;
- ex2 = ex;
+ if (p->index == EXT4_EXTENT_LAST_INDEX(hdr)) {+ /* Go one level above */
+ p++;
+ } else {+ p->index++;
+ ret = ext4_extent_reload_paths(inode_ref, path, p->depth, false);
+ if (ret != EOK)
+ goto out;
+ /* Go to the bottom level (aka the leaf). */
+ p = path;
}
}
+ }
- ext4_ext_remove_blocks(inode_ref, ex, start, start + len - 1);
- /*
- * Set the first block of the extent if it is presented.
- */
- ex->first_block = to_le32(new_start);
+ /* The above code can only exit in either situations:
+ *
+ * 1. We found that there is no more extents at the right
+ * (p < path)
+ * 2. We found that the next extent has key larger than @toiblock
+ * (p at leaf) */
+ ext4_assert(p == path || p > path + rootdepth);
+ if (p == path) {+ /* We might have removed the leftmost key in the node,
+ * so we need to update the first key of the right
+ * sibling at every level until we meet a non-leftmost
+ * key. */
+ ext4_extent_update_index(inode_ref, path, true);
+ } else {+ /* Put loaded blocks. We won't double-release
+ * in this case since the depth of tree will
+ * be reset to 0. */
+ ext4_extent_path_release(inode_ref, path);
- /*
- * If the new length of the current extent we are working on is
- * zero, remove it.
- */
- 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);
+ hdr = ext4_inode_get_extent_header(inode_ref->inode);
+ if (!ext4_extent_header_get_nentries(hdr)) {+ /* For empty root we need to make sure that the
+ * depth of the root level is 0. */
+ ext4_extent_header_set_nentries(hdr, 0);
+ ext4_extent_header_set_depth(hdr, 0);
+ inode_ref->dirty = true;
}
-
- ex += 1;
}
- if (ex2 == NULL)
- ex2 = ex;
+out:
+ /* Put loaded blocks */
+ ext4_extent_path_release(inode_ref, path);
- /*
- * Move any remaining extents to the starting position of the node.
- */
- if (ex2 <= EXT_LAST_EXTENT(eh))
- memmove(start_ex, ex2, (EXT_LAST_EXTENT(eh) - ex2 + 1) *
- sizeof(struct ext4_extent));
+ /* Destroy temporary data structure */
+ ext4_free(path);
- eh->entries_count = to_le16(new_entries);
- ext4_ext_dirty(inode_ref, path + depth);
-
- /*
- * If the extent pointer is pointed to the first extent of the node, and
- * there's still extents presenting, we may need to correct the indexes
- * of the paths.
- */
- if (path[depth].extent == EXT_FIRST_EXTENT(eh) && eh->entries_count) {- err = ext4_ext_correct_indexes(inode_ref, path);
- if (err != EOK)
- return err;
- }
-
- /* if this leaf is free, then we should
- * remove it from index block above */
- if (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;
+ return ret;
}
-/*
- * Check if there's more to remove at a specific level.
- */
-static bool ext4_ext_more_to_rm(struct ext4_extent_path *path, ext4_lblk_t to)
+/**@brief Zero a range of blocks
+ * @param inode_ref I-node
+ * @param fblock starting block number to be zeroed
+ * @param nblocks number of blocks to be zeroed
+ * @return Error code */
+static int ext4_extent_zero_fblocks(struct ext4_inode_ref *inode_ref,
+ ext4_fsblk_t fblock,
+ ext4_lblk_t nblocks)
{- if (!to_le16(path->header->entries_count))
- return false;
+ int ret = EOK;
+ ext4_lblk_t i;
+ uint32_t blocksz;
- if (path->index > EXT_LAST_INDEX(path->header))
- return false;
+ blocksz = ext4_sb_get_block_size(&inode_ref->fs->sb);
+ for (i = 0; i < nblocks; i++) {+ struct ext4_block bh = EXT4_BLOCK_ZERO();
+ ret = ext4_trans_block_get_noread(inode_ref->fs->bdev, &bh,
+ fblock + i);
+ if (ret != EOK)
+ break;
- if (to_le32(path->index->first_block) > to)
- return false;
-
- return true;
+ memset(bh.data, 0, blocksz);
+ ext4_trans_set_block_dirty(bh.buf);
+ ret = ext4_block_set(inode_ref->fs->bdev, &bh);
+ if (ret != EOK)
+ break;
+ }
+ return ret;
}
-int ext4_extent_remove_space(struct ext4_inode_ref *inode_ref, ext4_lblk_t from,
- ext4_lblk_t to)
+/**@brief Convert unwritten mapping to written one
+ * @param inode_ref I-node
+ * @param path Path in the extent tree
+ * @param iblock starting logical block to be converted
+ * @param nblocks number of blocks to be converted
+ * @return Error code */
+int ext4_extent_convert_written(struct ext4_inode_ref *inode_ref,
+ struct ext4_extent_path *path,
+ ext4_lblk_t iblock,
+ ext4_lblk_t nblocks)
{- struct ext4_extent_path *path = NULL;
int ret;
- int32_t depth = ext_depth(inode_ref->inode);
- int32_t i;
+ ext4_lblk_t eiblock;
+ ext4_lblk_t enblocks;
+ ext4_fsblk_t efblock;
+ struct ext4_extent *ext;
- ret = ext4_find_extent(inode_ref, from, &path, 0);
- if (ret != EOK)
- goto out;
+ ext = path[0].extent;
+ ext4_assert(ext);
- if (!path[depth].extent) {- ret = EOK;
- goto out;
- }
+ eiblock = ext4_extent_get_iblock(ext);
+ enblocks = ext4_extent_get_nblocks(ext);
+ efblock = ext4_extent_get_fblock(ext);
+ ext4_assert(EXT4_EXTENT_IN_RANGE(iblock, eiblock, enblocks));
- bool in_range = IN_RANGE(from, to_le32(path[depth].extent->first_block),
- ext4_ext_get_actual_len(path[depth].extent));
+ /* There are four cases we need to handle */
+ if (iblock == eiblock && nblocks == enblocks) {+ /* Case 1: the whole extent has to be converted.
+ * This is the simplest scenario. We just need
+ * to mark the extent "written", and zero the
+ * blocks covered by the extent */
+ ret = ext4_extent_zero_fblocks(inode_ref, efblock, enblocks);
+ if (ret != EOK)
+ return ret;
+ EXT4_EXT_SET_WRITTEN(ext);
+ ext4_extent_path_dirty(inode_ref, path, 0);
+ } else if (iblock == eiblock) {+ /* Case 2: convert the first part of the extent to written
+ * and insert an unwritten extent after that */
+ ext4_lblk_t newiblock;
+ ext4_lblk_t newnblocks;
+ ext4_fsblk_t newfblock;
+ struct ext4_extent insext;
- if (!in_range) {- ret = EOK;
- goto out;
- }
+ /* The new extent we are going to insert */
+ newiblock = eiblock + nblocks;
+ newnblocks = eiblock + enblocks - newiblock;
+ newfblock = efblock + nblocks;
- /* 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)) {+ /* Zero the blocks covered by the first part of the extent */
+ ret = ext4_extent_zero_fblocks(inode_ref,
+ efblock + iblock - eiblock,
+ nblocks);
+ if (ret != EOK)
+ return ret;
- 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);
+ /* Trim the current extent and convert the extent to written */
+ ext4_extent_set_nblocks(ext, enblocks - nblocks, false);
+ ext4_extent_path_dirty(inode_ref, path, 0);
- ex->block_count = to_le16(from - ee_block);
- if (unwritten)
- ext4_ext_mark_unwritten(ex);
+ /* Insert the new extent */
+ ext4_extent_set_iblock(&insext, newiblock);
+ ext4_extent_set_nblocks(&insext, newnblocks, true);
+ ext4_extent_set_fblock(&insext, newfblock);
+ ret = ext4_extent_insert(inode_ref, path, &insext);
+ if (ret != EOK)
+ /* In case when something happens during insertion
+ * we revert the trimming of the current extent */
+ ext4_extent_set_nblocks(ext, nblocks, true);
+ } else if (iblock + nblocks == eiblock + enblocks) {+ /* Case 3: convert the second part of the extent to written.
+ * We insert an written extent after the current extent */
+ ext4_lblk_t newiblock;
+ ext4_lblk_t newnblocks;
+ ext4_fsblk_t newfblock;
+ struct ext4_extent insext;
- ext4_ext_dirty(inode_ref, path + depth);
+ /* The new extent we are going to insert */
+ newiblock = iblock;
+ newnblocks = nblocks;
+ newfblock = efblock + iblock - eiblock;
- 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);
+ /* Zero the blocks covered by the first part of the extent */
+ ret = ext4_extent_zero_fblocks(inode_ref, newfblock, newnblocks);
+ if (ret != EOK)
+ return ret;
- ret = ext4_ext_insert_extent(inode_ref, &path, &newex, 0);
- goto out;
- }
+ /* Trim the current extent */
+ ext4_extent_set_nblocks(ext, enblocks - nblocks, true);
+ ext4_extent_path_dirty(inode_ref, path, 0);
- 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;
+ /* Insert the new extent */
+ ext4_extent_set_iblock(&insext, newiblock);
+ ext4_extent_set_nblocks(&insext, newnblocks, false);
+ ext4_extent_set_fblock(&insext, newfblock);
+ ret = ext4_extent_insert(inode_ref, path, &insext);
+ if (ret != EOK)
+ /* In case when something happens during insertion
+ * we revert the trimming of the current extent */
+ ext4_extent_set_nblocks(ext, nblocks, true);
+ } else {+ /* Case 4: convert the middle part of the extent to written.
+ * We insert one written extent, follow by an unwritten
+ * extent */
+ ext4_lblk_t newiblock[2];
+ ext4_lblk_t newnblocks[2];
+ ext4_fsblk_t newfblock[2];
+ struct ext4_extent insext;
- if (leaf_to > to)
- leaf_to = to;
+ /* The new extents we are going to insert */
+ newiblock[0] = iblock;
+ newnblocks[0] = nblocks;
+ newfblock[0] = efblock + iblock - eiblock;
+ newiblock[1] = iblock + nblocks;
+ newnblocks[1] = eiblock + enblocks - newiblock[1];
+ newfblock[1] = newfblock[0] + nblocks;
- ext4_ext_remove_leaf(inode_ref, path, leaf_from,
- leaf_to);
- ext4_ext_drop_refs(inode_ref, path + i, 0);
- i--;
- continue;
- }
+ /* Zero the blocks covered by the written extent */
+ ret = ext4_extent_zero_fblocks(inode_ref, newfblock[0],
+ newnblocks[0]);
+ if (ret != EOK)
+ return ret;
- 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);
+ /* We don't want to fail in the middle because we
+ * run out of space. From now on the subsequent
+ * insertions cannot fail */
+ ret = ext4_extent_split(inode_ref, path, 2);
+ if (ret != EOK)
+ return ret;
- ret = read_extent_tree_block(
- inode_ref, ext4_idx_pblock(path[i].index),
- depth - i - 1, &bh, 0);
- if (ret != EOK)
- goto out;
+ /* Trim the current extent */
+ ext4_extent_set_nblocks(ext,
+ enblocks - newnblocks[0] - newnblocks[1],
+ true);
+ ext4_extent_path_dirty(inode_ref, path, 0);
- 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);
+ /* Insert the written extent first */
+ ext4_extent_set_iblock(&insext, newiblock[0]);
+ ext4_extent_set_nblocks(&insext, newnblocks[0], false);
+ ext4_extent_set_fblock(&insext, newfblock[0]);
+ ret = ext4_extent_insert(inode_ref, path, &insext);
+ ext4_assert(ret == EOK);
- i++;
- } else {- if (i > 0) {- /*
- * Garbage entries will finally be cleared here.
- */
- 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--;
- }
+ /* Then insert the unwritten extent */
+ ext4_extent_set_iblock(&insext, newiblock[1]);
+ ext4_extent_set_nblocks(&insext , newnblocks[1], true);
+ ext4_extent_set_fblock(&insext, newfblock[1]);
+ ret = ext4_extent_insert(inode_ref, path, &insext);
+ ext4_assert(ret == EOK);
}
-
- /* 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);
- ext4_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)
+/**@brief Check if the second extent can be appended to the first extent
+ * @param ext the first extent
+ * @param ext2 the second extent
+ * @return true if the two extents can be merged, otherwise false */
+static bool ext4_extent_can_append(struct ext4_extent *ext,
+ struct ext4_extent *ext2)
{- 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;
+ bool unwritten;
+ ext4_lblk_t eiblock[2];
+ ext4_lblk_t enblocks[2];
+ ext4_fsblk_t efblock[2];
- 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);
+ eiblock[0] = ext4_extent_get_iblock(ext);
+ enblocks[0] = ext4_extent_get_nblocks(ext);
+ efblock[0] = ext4_extent_get_fblock(ext);
+ eiblock[1] = ext4_extent_get_iblock(ext2);
+ enblocks[1] = ext4_extent_get_nblocks(ext2);
+ efblock[1] = ext4_extent_get_fblock(ext2);
- 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);
+ /* We can't merge an unwritten extent with a written
+ * extent */
+ if (EXT4_EXT_IS_UNWRITTEN(ext) != EXT4_EXT_IS_UNWRITTEN(ext2))
+ return false;
- err = ext4_ext_dirty(inode_ref, *ppath + depth);
- goto out;
+ unwritten = EXT4_EXT_IS_UNWRITTEN(ext);
+
+ /* Since the starting logical block of the second
+ * extent is greater than that of the first extent,
+ * we check whether we can append the second extent
+ * to the first extent */
+ if (eiblock[0] + enblocks[0] != eiblock[1] ||
+ efblock[0] + enblocks[0] != efblock[1])
+ /* If the two extents are not continuous
+ * in terms of logical block range and
+ * physical block range, we return false */
+ return false;
+
+ /* Check if the total number of blocks of the two extents are
+ * too long.
+ * Note: the maximum length of unwritten extent is shorter than
+ * written extent by one block */
+ if (unwritten) {+#if CONFIG_EXTENT_DEBUG_AGGRESSIVE
+ if (enblocks[0] + enblocks[1] > 3)
+#else /* CONFIG_EXTENT_DEBUG_AGGRESSIVE */
+ if (enblocks[0] + enblocks[1] > EXT4_EXT_MAX_LEN_UNWRITTEN)
+#endif /* CONFIG_EXTENT_DEBUG_AGGRESSIVE */
+ return false;
+ } else {+#if CONFIG_EXTENT_DEBUG_AGGRESSIVE
+ if (enblocks[0] + enblocks[1] > 3)
+#else /* CONFIG_EXTENT_DEBUG_AGGRESSIVE */
+ if (enblocks[0] + enblocks[1] > EXT4_EXT_MAX_LEN_WRITTEN)
+#endif /* CONFIG_EXTENT_DEBUG_AGGRESSIVE */
+ return false;
}
- ex->block_count = to_le16(split - ee_block);
- if (split_flag & EXT4_EXT_MARK_UNWRIT1)
- ext4_ext_mark_unwritten(ex);
+ /* The second extent can be appended to the first extent */
+ return true;
+}
- err = ext4_ext_dirty(inode_ref, *ppath + depth);
- if (err != EOK)
- goto out;
+/**@brief Check if the second extent can be prepended to the first extent
+ * @param ext the first extent
+ * @param ext2 the second extent
+ * @return true if the two extents can be merged, otherwise false */
+static bool ext4_extent_can_prepend(struct ext4_extent *ext,
+ struct ext4_extent *ext2)
+{+ bool unwritten;
+ ext4_lblk_t eiblock[2];
+ ext4_lblk_t enblocks[2];
+ ext4_fsblk_t efblock[2];
- 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;
+ eiblock[0] = ext4_extent_get_iblock(ext);
+ enblocks[0] = ext4_extent_get_nblocks(ext);
+ efblock[0] = ext4_extent_get_fblock(ext);
+ eiblock[1] = ext4_extent_get_iblock(ext2);
+ enblocks[1] = ext4_extent_get_nblocks(ext2);
+ efblock[1] = ext4_extent_get_fblock(ext2);
-out:
- return err;
-restore_extent_len:
- ex->block_count = to_le16(ee_len);
- err = ext4_ext_dirty(inode_ref, *ppath + depth);
- return err;
-}
+ /* We can't merge an unwritten extent with a written
+ * extent */
+ if (EXT4_EXT_IS_UNWRITTEN(ext) != EXT4_EXT_IS_UNWRITTEN(ext2))
+ return false;
-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;
- struct ext4_extent *ex = (*ppath)[depth].extent;
+ unwritten = EXT4_EXT_IS_UNWRITTEN(ext);
- ext4_assert(to_le32(ex->first_block) <= split);
+ /* Since the starting logical block of the second
+ * extent is smaller than that of the first extent,
+ * we check whether we can prepend the second extent
+ * to the first extent */
+ if (eiblock[1] + enblocks[1] != eiblock[0] ||
+ efblock[1] + enblocks[1] != efblock[0])
+ /* If the two extents are not continuous
+ * in terms of logical block range and
+ * physical block range, we return false */
+ return false;
- 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);
+ /* Check if the total number of blocks of the two extents are
+ * too long.
+ * Note: the maximum length of unwritten extent is shorter than
+ * written extent by one block */
+ if (unwritten) {+#if CONFIG_EXTENT_DEBUG_AGGRESSIVE
+ if (enblocks[0] + enblocks[1] > 3)
+#else /* CONFIG_EXTENT_DEBUG_AGGRESSIVE */
+ if (enblocks[0] + enblocks[1] > EXT4_EXT_MAX_LEN_UNWRITTEN)
+#endif /* CONFIG_EXTENT_DEBUG_AGGRESSIVE */
+ return false;
} 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 == EOK) {- err = ext4_ext_split_extent_at(inode_ref, ppath, split,
- EXT4_EXT_MARK_UNWRIT1);
- }
+#if CONFIG_EXTENT_DEBUG_AGGRESSIVE
+ if (enblocks[0] + enblocks[1] > 3)
+#else /* CONFIG_EXTENT_DEBUG_AGGRESSIVE */
+ if (enblocks[0] + enblocks[1] > EXT4_EXT_MAX_LEN_WRITTEN)
+#endif /* CONFIG_EXTENT_DEBUG_AGGRESSIVE */
+ return false;
}
- return err;
+ /* The second extent can be prepended to the first extent */
+ return true;
}
-static ext4_lblk_t ext4_ext_next_allocated_block(struct ext4_extent_path *path)
+/**@brief Allocate multiple number of blocks
+ * @param inode_ref I-node
+ * @param goal physical block allocation hint
+ * @param nblocks number of blocks to be allocated
+ * @param fblockp Output value - starting physical block number
+ * @param nblocksp Output value - the number of blocks allocated
+ * @return Error code */
+static int
+ext4_extent_alloc_datablocks(struct ext4_inode_ref *inode_ref,
+ ext4_fsblk_t goal,
+ ext4_lblk_t nblocks,
+ ext4_fsblk_t *fblockp,
+ ext4_lblk_t *nblocksp)
{- int32_t depth;
+ int ret = EOK;
+ ext4_lblk_t i;
+ ext4_fsblk_t retfblock;
+ ext4_lblk_t retnblocks = 0;
- depth = path->depth;
+ for (i = 0; i < nblocks; ++i, ++retnblocks) {+ bool free = false;
- 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);
+ if (!i) {+ /* We allocate the first block by using
+ * ext4_balloc_alloc_block() so that we
+ * can pass allocation hint to the block
+ * allocator */
+ ret = ext4_balloc_alloc_block(inode_ref,
+ goal,
+ &retfblock);
+ if (ret == EOK)
+ free = true;
} else {- /* index */
- if (path[depth].index !=
- EXT_LAST_INDEX(path[depth].header))
- return to_le32(
- path[depth].index[1].first_block);
+ ext4_fsblk_t blockscnt;
+
+ /* Do a check to make sure that we won't look into
+ * a block number larger than the total number of
+ * blocks we have on this filesystem */
+ blockscnt = ext4_sb_get_blocks_cnt(&inode_ref->fs->sb);
+ if (retfblock + i < blockscnt) {+ ret = ext4_balloc_try_alloc_block(inode_ref,
+ retfblock + i, &free);
+ } else
+ free = false;
}
- 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)
+ /* Stop trying on the next block if we encounter errors, or
+ * if there is insufficient space, or if we can't allocate
+ * blocks continuously */
+ if (ret != EOK || !free)
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;
-}
-__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;
-
- USED(a);
- USED(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++;
+ if (ret == EOK) {+ *fblockp = retfblock;
+ if (nblocksp)
+ *nblocksp = nblocks;
}
+ return ret;
}
-int ext4_extent_get_blocks(struct ext4_inode_ref *inode_ref, ext4_lblk_t iblock,
- uint32_t max_blocks, ext4_fsblk_t *result,
- bool create, uint32_t *blocks_count)
+/**@brief Extent-based blockmap manipulation
+ * @param inode_ref I-node
+ * @param iblock starting logical block of the inode
+ * @param max_nblocks maximum number of blocks to get from/allocate to blockmap
+ * @param resfblockp return physical block address of the first block of an
+ * extent
+ * @param create true if caller wants to insert mapping or convert
+ * unwritten mapping to written one
+ * @param resnblocksp return number of blocks in an extent (must be smaller than
+ * \p max_nblocks)
+ * @return Error code*/
+int ext4_extent_get_blocks(struct ext4_inode_ref *inode_ref,
+ ext4_lblk_t iblock,
+ ext4_lblk_t max_nblocks,
+ ext4_fsblk_t *resfblockp,
+ bool create,
+ ext4_lblk_t *resnblocksp)
{- struct ext4_extent_path *path = NULL;
- struct ext4_extent newex, *ex;
+ int ret;
+ struct ext4_extent_path *path;
+ struct ext4_extent *ext;
+ struct ext4_extent insext;
+ ext4_lblk_t eiblock;
+ ext4_lblk_t enblocks;
+ ext4_fsblk_t efblock;
+ ext4_fsblk_t resfblock;
+ ext4_lblk_t resnblocks = 0;
ext4_fsblk_t goal;
- int err = EOK;
- int32_t depth;
- uint32_t allocated = 0;
- ext4_lblk_t next;
- ext4_fsblk_t newblock;
- if (result)
- *result = 0;
+ /* Seek to the corresponding extent */
+ ret = ext4_extent_find_extent(inode_ref, iblock, &path);
+ if (ret != EOK)
+ return ret;
- if (blocks_count)
- *blocks_count = 0;
+ ext = path[0].extent;
+ if (ext) {+ /* The extent tree is not empty */
+ eiblock = ext4_extent_get_iblock(ext);
+ enblocks = ext4_extent_get_nblocks(ext);
+ efblock = ext4_extent_get_fblock(ext);
+ if (EXT4_EXTENT_IN_RANGE(iblock, eiblock, enblocks)) {+ /* The extent exists and logical block requested falls
+ * into the range of the extent */
+ resfblock = efblock + iblock - eiblock;
+ resnblocks = eiblock + enblocks - iblock;
- /* find extent for this block */
- err = ext4_find_extent(inode_ref, iblock, &path, 0);
- if (err != EOK) {- path = NULL;
- goto out2;
- }
+ /* Trim the result if it is larger than the maximum
+ * length the caller wants */
+ if (resnblocks > max_nblocks)
+ resnblocks = max_nblocks;
- 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 (EXT4_EXT_IS_UNWRITTEN(ext)) {+ if (create)
+ /* Convert the extent to written extent
+ * if the extent is unwritten extent */
+ ret = ext4_extent_convert_written(inode_ref,
+ path,
+ iblock,
+ resnblocks);
+ else
+ /* We are not asked to modify the blockmap
+ * so we just return a hole */
+ resfblock = 0;
}
+ goto cleanup;
+ }
+ if (!create) {+ /* Don't waste time on finding the next extent if we
+ * are not asked to insert mapping, just return a
+ * hole */
+ resfblock = 0;
+ resnblocks = 1;
+ goto cleanup;
+ }
+ if (ext4_extent_get_iblock(ext) < iblock) {+ /* Since the logical block of current extent is smaller
+ * the requested logical block, we seek to the next
+ * extent to find the maximum number of blocks we can
+ * allocate without hitting the starting logical block
+ * of the next extent */
+ bool nonext;
- if (!create) {- newblock = 0;
- goto out;
- }
+ /* Go to the next extent */
+ ret = ext4_extent_increment(inode_ref, path, &nonext);
+ if (ret != EOK)
+ goto cleanup;
- uint32_t zero_range;
- zero_range = allocated;
- if (zero_range > max_blocks)
- zero_range = max_blocks;
+ if (!nonext) {+ /* We successfully reach the next extent */
+ bool noprev;
+ ext4_lblk_t neiblock;
- newblock = iblock - ee_block + ee_start;
- err = ext4_ext_zero_unwritten_range(inode_ref, newblock,
- zero_range);
- if (err != EOK)
- goto out2;
+ ext = path[0].extent;
- err = ext4_ext_convert_to_initialized(
- inode_ref, &path, iblock, zero_range);
- if (err != EOK)
- goto out2;
+ /* The next extent must start at greater logical
+ * block number */
+ ext4_assert(ext4_extent_get_iblock(ext) >
+ iblock);
- goto out;
+ /* Calculate the maximum number of blocks we
+ * can allocate without overlapping with the
+ * next extent */
+ neiblock = ext4_extent_get_iblock(ext);
+ if (max_nblocks > neiblock - iblock)
+ max_nblocks = neiblock - iblock;
+
+ /* Go back to the previous extent */
+ ret = ext4_extent_decrement(inode_ref, path,
+ &noprev);
+ if (ret != EOK)
+ goto cleanup;
+ ext4_assert(!noprev);
+ ext = path[0].extent;
+ }
}
}
- /*
- * requested block isn't allocated yet
- * we couldn't try to create block if create flag is zero
- */
+ /* Return a hole if we are not asked to insert mapping */
if (!create) {- goto out2;
+ resfblock = 0;
+ resnblocks = 1;
+ goto cleanup;
}
- /* 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;
+ /* Multiple data blocks allocation */
+ goal = ext4_extent_data_alloc_goal(inode_ref, path, iblock);
+ ret = ext4_extent_alloc_datablocks(inode_ref, goal, max_nblocks,
+ &resfblock, &max_nblocks);
+ if (ret != EOK)
+ goto cleanup;
- /* 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;
+ ext4_extent_set_iblock(&insext, iblock);
+ ext4_extent_set_nblocks(&insext, max_nblocks, false);
+ ext4_extent_set_fblock(&insext, resfblock);
- /* 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;
- }
+ if (ext && ext4_extent_can_append(ext, &insext)) {+ /* Clang won't complain, it's just to make gcc happy */
+ enblocks = ext4_extent_get_nblocks(ext);
- /* previous routine could use block we allocated */
- newblock = ext4_ext_pblock(&newex);
+ /* If we can append this extent to the current extent */
+ ext4_extent_set_nblocks(ext, enblocks + max_nblocks,
+ EXT4_EXT_IS_UNWRITTEN(ext));
-out:
- if (allocated > max_blocks)
- allocated = max_blocks;
+ ext4_extent_path_dirty(inode_ref, path, 0);
+ } else if (ext && ext4_extent_can_prepend(ext, &insext)) {+ /* Clang won't complain, it's just to make gcc happy */
+ enblocks = ext4_extent_get_nblocks(ext);
- if (result)
- *result = newblock;
+ /* If we can prepend this extent to the current extent */
+ ext4_extent_set_iblock(ext, iblock);
+ ext4_extent_set_nblocks(ext, enblocks + max_nblocks,
+ EXT4_EXT_IS_UNWRITTEN(ext));
+ ext4_extent_set_fblock(ext, resfblock);
- if (blocks_count)
- *blocks_count = allocated;
+ /* If we are working on the first extent in the
+ * first leaf (in case we are actually prepending
+ * mappings) we need to update the index of nodes.
+ *
+ * NOTE: Since we don't seek to the next extent and
+ * try to modify it, prepending should not happen at
+ * any leaves except the first extent of the first leaf */
+ ext4_extent_update_index(inode_ref, path, false);
+ ext4_extent_path_dirty(inode_ref, path, 0);
+ } else {+ /* Finally, insert a new extent into the extent tree */
+ ret = ext4_extent_insert(inode_ref, path, &insext);
+ if (ret != EOK)
+ ext4_balloc_free_blocks(inode_ref, resfblock,
+ max_nblocks);
+ }
-out2:
- if (path) {- ext4_ext_drop_refs(inode_ref, path, 0);
- ext4_free(path);
+ resnblocks = max_nblocks;
+
+cleanup:
+ /* Put loaded blocks */
+ ext4_extent_path_release(inode_ref, path);
+
+ /* Destroy temporary data structure */
+ ext4_free(path);
+
+ if (ret == EOK) {+ if (resfblockp)
+ *resfblockp = resfblock;
+ if (resnblocksp)
+ *resnblocksp = resnblocks;
}
- return err;
+ return ret;
}
-#endif
+
+#endif /* CONFIG_EXTENT_ENABLE */
+
+/**
+ * @}
+ */
--- a/src/ext4_fs.c
+++ b/src/ext4_fs.c
@@ -1231,7 +1231,7 @@
/* Extents require special operation */
if (diff_blocks_cnt) {r = ext4_extent_remove_space(inode_ref, new_blocks_cnt,
- EXT_MAX_BLOCKS);
+ EXT4_EXTENT_MAX_BLOCKS);
if (r != EOK)
return r;