/*
- * Copyright (c) 2015 Grzegorz Kostka (kostka.grzegorz@gmail.com)
- * Copyright (c) 2015 Kaho Ng (ngkaho1234@gmail.com)
+ * Copyright (c) 2017 Grzegorz Kostka (kostka.grzegorz@gmail.com)
+ * Copyright (c) 2017 Kaho Ng (ngkaho1234@gmail.com)
*
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- *
- * - Redistributions of source code must retain the above copyright
- * notice, this list of conditions and the following disclaimer.
- * - Redistributions in binary form must reproduce the above copyright
- * notice, this list of conditions and the following disclaimer in the
- * documentation and/or other materials provided with the distribution.
- * - The name of the author may not be used to endorse or promote products
- * derived from this software without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
- * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
- * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
- * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
- * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
- * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
- * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
- * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
- * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
- * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ * 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.
*/
-#include "ext4_config.h"
-#include "ext4_types.h"
-#include "ext4_misc.h"
-#include "ext4_errno.h"
-#include "ext4_debug.h"
+#include <ext4_config.h>
+#include <ext4_types.h>
+#include <ext4_misc.h>
+#include <ext4_errno.h>
+#include <ext4_debug.h>
-#include "ext4_blockdev.h"
-#include "ext4_trans.h"
-#include "ext4_fs.h"
-#include "ext4_super.h"
-#include "ext4_crc32.h"
-#include "ext4_balloc.h"
-#include "ext4_extent.h"
+#include <ext4_blockdev.h>
+#include <ext4_trans.h>
+#include <ext4_fs.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>
+#if CONFIG_EXTENTS_ENABLE
/*
* used by extent splitting.
*/
#define EXT4_EXT_DATA_VALID2 0x10 /* second half contains valid data */
#define EXT4_EXT_NO_COMBINE 0x20 /* do not combine two extents */
+#define EXT4_EXT_UNWRITTEN_MASK (1L << 15)
+
+#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)->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))
+
+#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)))
+
+/*
+ * 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;
+};
+
+
+#pragma pack(push, 1)
+
+/*
+ * 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) */
+};
+
+/*
+ * 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 */
+};
+
+/*
+ * 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' */
+
+ /**
+ * 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;
+};
+
+/*
+ * 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 */
+};
+
+#pragma pack(pop)
+
+
+#define EXT4_EXTENT_MAGIC 0xF30A
+
+#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)))
+
+/*
+ * 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)
+
+#define EXT_EXTENT_SIZE sizeof(struct ext4_extent)
+#define EXT_INDEX_SIZE sizeof(struct ext4_extent_idx)
+
+#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)
+
+#define EXT4_EXTENT_TAIL_OFFSET(hdr) \
+ (sizeof(struct ext4_extent_header) + \
+ (sizeof(struct ext4_extent) * to_le16((hdr)->max_entries_count)))
+
+
+/**@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);
+}
+
+/**@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)
+{
+ extent->first_block = 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_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);
+}
+/**@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)
+{
+ return ((uint64_t)to_le16(extent->start_hi)) << 32 |
+ ((uint64_t)to_le32(extent->start_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_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));
+}
+
+
+/**@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);
+}
+
+/**@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);
+}
+
+/**@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));
+}
+
+/**@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)
+{
+ index->leaf_lo = to_le32((fblock << 32) >> 32);
+ index->leaf_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_entries_count(struct ext4_extent_header *header)
+{
+ return to_le16(header->entries_count);
+}
+
+/**@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);
+}
+
+/**@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);
+}
+
+/**@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)
+{
+ header->max_entries_count = 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);
+}
+
+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_entries_count(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_entries_count(header, max_entries);
+ inode_ref->dirty = true;
+}
+
+
static struct ext4_extent_tail *
find_ext4_extent_tail(struct ext4_extent_header *eh)
{
}
static int ext4_allocate_single_block(struct ext4_inode_ref *inode_ref,
- ext4_fsblk_t goal,
- ext4_fsblk_t *blockp)
+ ext4_fsblk_t goal, ext4_fsblk_t *blockp)
{
return ext4_balloc_alloc_block(inode_ref, goal, blockp);
}
}
static uint16_t ext4_ext_max_entries(struct ext4_inode_ref *inode_ref,
- uint32_t depth)
+ uint32_t depth)
{
uint16_t max;
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));
+ 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));
+ 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
+ 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));
+ checksum =
+ ext4_crc32c(checksum, eh, EXT4_EXTENT_TAIL_OFFSET(eh));
}
return checksum;
}
#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)
+static void
+ext4_extent_block_csum_set(struct ext4_inode_ref *inode_ref __unused,
+ struct ext4_extent_header *eh)
{
struct ext4_extent_tail *tail;
if (path->block.lb_id) {
if (ext4_bcache_test_flag(path->block.buf, BC_DIRTY))
ext4_extent_block_csum_set(inode_ref,
- path->header);
+ path->header);
ext4_block_set(inode_ref->fs->bdev, &path->block);
}
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))) {
+ 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",
+ "Blocknr: %" PRIu64 "\n",
pblk);
-
}
}
if (path) {
ext4_ext_drop_refs(inode_ref, path, 0);
if (depth > path[0].maxdepth) {
- free(path);
+ ext4_free(path);
*orig_path = path = NULL;
}
}
if (!path) {
int32_t path_depth = depth + 1;
/* account possible depth increase */
- path = calloc(1, sizeof(struct ext4_extent_path) *
+ path = ext4_calloc(1, sizeof(struct ext4_extent_path) *
(path_depth + 1));
if (!path)
return ENOMEM;
err:
ext4_ext_drop_refs(inode_ref, path, 0);
- free(path);
+ ext4_free(path);
if (orig_path)
*orig_path = NULL;
return ret;
}
static int ext4_ext_insert_index(struct ext4_inode_ref *inode_ref,
- struct ext4_extent_path *path,
- int at,
+ struct ext4_extent_path *path, int at,
ext4_lblk_t insert_index,
- ext4_fsblk_t insert_block,
- bool set_to_ix)
+ ext4_fsblk_t insert_block, bool set_to_ix)
{
struct ext4_extent_index *ix;
struct ext4_extent_path *curp = path + at;
if (curp->index && insert_index == to_le32(curp->index->first_block))
return EIO;
- if (to_le16(curp->header->entries_count)
- == to_le16(curp->header->max_entries_count))
+ if (to_le16(curp->header->entries_count) ==
+ to_le16(curp->header->max_entries_count))
return EIO;
eh = curp->header;
err = ext4_ext_dirty(inode_ref, curp);
out:
- if (!err && set_to_ix) {
+ if (err == EOK && set_to_ix) {
curp->index = ix;
curp->p_block = ext4_idx_pblock(ix);
}
}
static int ext4_ext_split_node(struct ext4_inode_ref *inode_ref,
- struct ext4_extent_path *path,
- int at,
+ struct ext4_extent_path *path, int at,
struct ext4_extent *newext,
struct ext4_extent_path *npath,
bool *ins_right_leaf)
else
insert_index = newext->first_block;
- for (i = depth;i >= at;i--, npath_at--) {
+ for (i = depth; i >= at; i--, npath_at--) {
struct ext4_block bh = EXT4_BLOCK_ZERO();
- /* 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)
+ /* 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;
/* For write access.*/
- ret = ext4_trans_block_get_noread(inode_ref->fs->bdev, &bh, newblock);
+ ret = ext4_trans_block_get_noread(inode_ref->fs->bdev, &bh,
+ newblock);
if (ret != EOK)
goto cleanup;
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);
+ 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)
+ if (ret != EOK)
goto cleanup;
npath[npath_at].p_block = ext4_ext_pblock(ex);
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);
+ 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);
+ 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)
+ if (ret != EOK)
goto cleanup;
-
}
npath[npath_at].p_block = ext4_idx_pblock(ix);
else
*ins_right_leaf = true;
- ret = ext4_ext_insert_index(inode_ref, path, at - 1,
- insert_index,
- npath[0].block.lb_id,
- *ins_right_leaf);
+ ret = ext4_ext_insert_index(inode_ref, path, at - 1, insert_index,
+ npath[0].block.lb_id, *ins_right_leaf);
cleanup:
- if (ret) {
+ if (ret != EOK) {
if (newblock)
ext4_ext_free_blocks(inode_ref, newblock, 1, 0);
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_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));
+ memset(&npath[npath_at].block, 0,
+ sizeof(struct ext4_block));
}
npath_at--;
}
return err;
}
-static inline bool ext4_ext_can_prepend(struct ext4_extent *ex1, struct ext4_extent *ex2)
+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))
+ if (ext4_ext_pblock(ex2) + ext4_ext_get_actual_len(ex2) !=
+ ext4_ext_pblock(ex1))
return 0;
#ifdef AGGRESSIVE_TEST
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)
+ 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)
+ } else if (ext4_ext_get_actual_len(ex1) + ext4_ext_get_actual_len(ex2) >
+ EXT_INIT_MAX_LEN)
return 0;
#endif
if (to_le32(ex2->first_block) + ext4_ext_get_actual_len(ex2) !=
- to_le32(ex1->first_block))
+ to_le32(ex1->first_block))
return 0;
return 1;
}
-static inline bool ext4_ext_can_append(struct ext4_extent *ex1, struct ext4_extent *ex2)
+static inline bool ext4_ext_can_append(struct ext4_extent *ex1,
+ struct ext4_extent *ex2)
{
- if (ext4_ext_pblock(ex1) + ext4_ext_get_actual_len(ex1)
- != ext4_ext_pblock(ex2))
+ if (ext4_ext_pblock(ex1) + ext4_ext_get_actual_len(ex1) !=
+ ext4_ext_pblock(ex2))
return 0;
#ifdef AGGRESSIVE_TEST
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)
+ 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)
+ } else if (ext4_ext_get_actual_len(ex1) + ext4_ext_get_actual_len(ex2) >
+ EXT_INIT_MAX_LEN)
return 0;
#endif
if (to_le32(ex1->first_block) + ext4_ext_get_actual_len(ex1) !=
- to_le32(ex2->first_block))
+ to_le32(ex2->first_block))
return 0;
return 1;
}
-#define EXT_INODE_HDR_NEED_GROW 0x1
-
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)
+ struct ext4_extent_path *path, int at,
+ struct ext4_extent *newext, int flags,
+ bool *need_split)
{
struct ext4_extent_path *curp = path + at;
struct ext4_extent *ex = curp->extent;
int len, err, unwritten;
struct ext4_extent_header *eh;
- if (curp->extent && to_le32(newext->first_block) == to_le32(curp->extent->first_block))
+ *need_split = false;
+
+ if (curp->extent &&
+ to_le32(newext->first_block) == to_le32(curp->extent->first_block))
return EIO;
if (!(flags & EXT4_EXT_NO_COMBINE)) {
if (curp->extent && ext4_ext_can_append(curp->extent, newext)) {
unwritten = ext4_ext_is_unwritten(curp->extent);
- curp->extent->block_count = to_le16(ext4_ext_get_actual_len(curp->extent)
- + ext4_ext_get_actual_len(newext));
+ 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);
goto out;
}
- if (curp->extent && ext4_ext_can_prepend(curp->extent, newext)) {
+ 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));
+ 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);
}
}
- if (to_le16(curp->header->entries_count)
- == to_le16(curp->header->max_entries_count)) {
- err = EXT_INODE_HDR_NEED_GROW;
+ 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)) {
+ } else if (to_le32(newext->first_block) >
+ to_le32(curp->extent->first_block)) {
/* insert after */
ex = curp->extent + 1;
} else {
}
err = ext4_ext_correct_indexes(inode_ref, path);
- if (err)
+ if (err != EOK)
goto out;
err = ext4_ext_dirty(inode_ref, curp);
out:
- if (!err) {
+ if (err == EOK) {
curp->extent = ex;
curp->p_block = ext4_ext_pblock(ex);
}
return err;
-
}
/*
return err;
}
-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)
+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));
}
-int ext4_ext_insert_extent(struct ext4_inode_ref *inode_ref, struct ext4_extent_path **ppath, struct ext4_extent *newext, int flags)
+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, ret = 0;
+ int depth, level = 0, ret = 0;
struct ext4_extent_path *path = *ppath;
struct ext4_extent_path *npath = NULL;
bool ins_right_leaf = false;
+ bool need_split;
again:
depth = ext_depth(inode_ref->inode);
- ret = ext4_ext_insert_leaf(inode_ref, path, depth,
- newext,
- flags);
- if (ret == EXT_INODE_HDR_NEED_GROW) {
+ 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++)
+ for (i = depth, level = 0; i >= 0; i--, level++)
if (EXT_HAS_FREE_INDEX(path + i))
break;
/* Do we need to grow the tree? */
if (i < 0) {
ret = ext4_ext_grow_indepth(inode_ref, 0);
- if (ret)
+ if (ret != EOK)
goto out;
- ret = ext4_find_extent(inode_ref, to_le32(newext->first_block), ppath, 0);
- if (ret)
+ ret = ext4_find_extent(
+ inode_ref, to_le32(newext->first_block), ppath, 0);
+ if (ret != EOK)
goto out;
path = *ppath;
i = depth - (level - 1);
/* We split from leaf to the i-th node */
if (level > 0) {
- npath = calloc(1, sizeof(struct ext4_extent_path) * (level));
+ 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)
+ ret = ext4_ext_split_node(inode_ref, path, i, newext,
+ npath, &ins_right_leaf);
+ if (ret != EOK)
goto out;
while (--level >= 0) {
if (ins_right_leaf)
- ext4_ext_replace_path(inode_ref,
- path,
- &npath[level],
- i + level);
+ 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);
-
+ ext4_ext_drop_refs(inode_ref,
+ npath + level, 1);
}
}
goto again;
}
out:
- if (ret) {
+ if (ret != EOK) {
if (path)
ext4_ext_drop_refs(inode_ref, path, 0);
while (--level >= 0 && npath) {
if (npath[level].block.lb_id) {
- ext4_fsblk_t block =
- 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)
- free(npath);
+ ext4_free(npath);
return ret;
}
to_le32(path[i].index->first_block), leaf, 1);
ext4_ext_free_blocks(inode_ref, leaf, 1, 0);
+ /*
+ * 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;
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++;
} 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) {
- len -= start + len - 1 - to;
new_len = start + len - 1 - to;
+ len -= new_len;
new_start = to + 1;
newblock += to + 1 - start;
ex2 = ex;
}
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);
+
+ /*
+ * If the new length of the current extent we are working on is
+ * zero, remove it.
+ */
if (!new_len)
new_entries--;
else {
if (ex2 == NULL)
ex2 = ex;
+ /*
+ * 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));
+ memmove(start_ex, ex2, (EXT_LAST_EXTENT(eh) - ex2 + 1) *
+ sizeof(struct ext4_extent));
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;
}
+/*
+ * 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)
{
if (!to_le16(path->header->entries_count))
}
int ext4_extent_remove_space(struct ext4_inode_ref *inode_ref, ext4_lblk_t from,
- ext4_lblk_t to)
+ ext4_lblk_t to)
{
struct ext4_extent_path *path = NULL;
int ret = EOK;
int32_t i;
ret = ext4_find_extent(inode_ref, from, &path, 0);
- if (ret)
+ if (ret != EOK)
goto out;
if (!path[depth].extent) {
}
bool in_range = IN_RANGE(from, to_le32(path[depth].extent->first_block),
- ext4_ext_get_actual_len(path[depth].extent));
+ ext4_ext_get_actual_len(path[depth].extent));
if (!in_range) {
ret = EOK;
/* 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)) {
+ ext4_ext_get_actual_len(path[depth].extent) - 1)) {
struct ext4_extent *ex = path[depth].extent, newex;
int unwritten = ext4_ext_is_unwritten(ex);
ext4_lblk_t ee_block = to_le32(ex->first_block);
int32_t len = ext4_ext_get_actual_len(ex);
- ext4_fsblk_t newblock =
- to + 1 - ee_block + ext4_ext_pblock(ex);
+ ext4_fsblk_t newblock = to + 1 - ee_block + ext4_ext_pblock(ex);
ex->block_count = to_le16(from - ee_block);
if (unwritten)
leaf_to = to;
ext4_ext_remove_leaf(inode_ref, path, leaf_from,
- leaf_to);
+ leaf_to);
ext4_ext_drop_refs(inode_ref, path + i, 0);
i--;
continue;
if (path[i + 1].block.lb_id)
ext4_ext_drop_refs(inode_ref, path + i + 1, 0);
- ret = read_extent_tree_block(inode_ref,
- ext4_idx_pblock(path[i].index),
- depth - i - 1, &bh, 0);
- if (ret)
+ ret = read_extent_tree_block(
+ inode_ref, ext4_idx_pblock(path[i].index),
+ depth - i - 1, &bh, 0);
+ if (ret != EOK)
goto out;
- path[i].p_block =
- ext4_idx_pblock(path[i].index);
+ 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);
+ path[i + 1].extent =
+ EXT_FIRST_EXTENT(path[i + 1].header);
else
path[i + 1].index =
- EXT_FIRST_INDEX(path[i + 1].header);
+ EXT_FIRST_INDEX(path[i + 1].header);
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);
+ 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);
-
+ &path[i].block);
i--;
}
-
}
/* TODO: flexible tree reduction should be here */
out:
ext4_ext_drop_refs(inode_ref, path, 0);
- free(path);
+ ext4_free(path);
path = NULL;
return ret;
}
err = ext4_ext_split_extent_at(inode_ref, ppath, split + blocks,
EXT4_EXT_MARK_UNWRIT1 |
EXT4_EXT_MARK_UNWRIT2);
- if (!err) {
+ if (err == EOK) {
err = ext4_ext_split_extent_at(inode_ref, ppath, split,
EXT4_EXT_MARK_UNWRIT1);
}
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);
+ err = ext4_trans_block_get_noread(inode_ref->fs->bdev, &bh,
+ block + i);
if (err != EOK)
break;
}
}
-
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)
+ uint32_t max_blocks, ext4_fsblk_t *result,
+ bool create, uint32_t *blocks_count)
{
struct ext4_extent_path *path = NULL;
struct ext4_extent newex, *ex;
newblock = iblock - ee_block + ee_start;
err = ext4_ext_zero_unwritten_range(inode_ref, newblock,
- zero_range);
+ zero_range);
if (err != EOK)
goto out2;
- err = ext4_ext_convert_to_initialized(inode_ref, &path,
- iblock, zero_range);
+ err = ext4_ext_convert_to_initialized(
+ inode_ref, &path, iblock, zero_range);
if (err != EOK)
goto out2;
out2:
if (path) {
ext4_ext_drop_refs(inode_ref, path, 0);
- free(path);
+ ext4_free(path);
}
return err;
}
+#endif
projects / lwext4.git / blobdiff