summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDarrick J. Wong <darrick.wong@oracle.com>2014-05-01 16:15:05 -0700
committerTheodore Ts'o <tytso@mit.edu>2014-08-02 19:18:39 -0400
commit07c479dd977d25986b32218f28987c1f6a370ab8 (patch)
tree369762a53a73f96a427df263d5a8f22b9b23107c
parentbaa3544609da3c9bbe7e253b83f32df74e1015de (diff)
downloade2fsprogs-07c479dd977d25986b32218f28987c1f6a370ab8.tar.gz
libext2fs: when appending to a file, don't split an index block in equal halves
When we're appending an extent to the end of a file and the index block is full, don't split the index block into two half-full index blocks because this leaves us with under utilized index blocks, at least in the fallocate case. Instead, copy the last extent from the full block into the new block. This isn't perfect utilization, but there's a lot of work involved in teaching extent.c to be able to goto a nonexistent node in a newly allocated (and empty) extent block. This patch does not fix the general problem of keeping the extent tree balanced. Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com> Signed-off-by: Theodore Ts'o <tytso@mit.edu>
-rw-r--r--lib/ext2fs/extent.c79
1 files changed, 72 insertions, 7 deletions
diff --git a/lib/ext2fs/extent.c b/lib/ext2fs/extent.c
index 0bf82ea4..c12bc930 100644
--- a/lib/ext2fs/extent.c
+++ b/lib/ext2fs/extent.c
@@ -29,6 +29,8 @@
#include "ext2fsP.h"
#include "e2image.h"
+#undef DEBUG
+
/*
* Definitions to be dropped in lib/ext2fs/ext2fs.h
*/
@@ -121,11 +123,39 @@ static void dbg_print_extent(char *desc, struct ext2fs_extent *extent)
}
+static void dump_path(const char *tag, struct ext2_extent_handle *handle,
+ struct extent_path *path)
+{
+ struct extent_path *ppp = path;
+ printf("%s: level=%d\n", tag, handle->level);
+
+ do {
+ printf("%s: path=%ld buf=%p entries=%d max_entries=%d left=%d "
+ "visit_num=%d flags=0x%x end_blk=%llu curr=%p(%ld)\n",
+ tag, (ppp - handle->path), ppp->buf, ppp->entries,
+ ppp->max_entries, ppp->left, ppp->visit_num, ppp->flags,
+ ppp->end_blk, ppp->curr, ppp->curr - (void *)ppp->buf);
+ printf(" ");
+ dbg_show_header((struct ext3_extent_header *)ppp->buf);
+ if (ppp->curr) {
+ printf(" ");
+ dbg_show_index(ppp->curr);
+ printf(" ");
+ dbg_show_extent(ppp->curr);
+ }
+ ppp--;
+ } while (ppp >= handle->path);
+ fflush(stdout);
+
+ return;
+}
+
#else
#define dbg_show_header(eh) do { } while (0)
#define dbg_show_index(ix) do { } while (0)
#define dbg_show_extent(ex) do { } while (0)
#define dbg_print_extent(desc, ex) do { } while (0)
+#define dump_path(tag, handle, path) do { } while (0)
#endif
/*
@@ -814,12 +844,31 @@ errcode_t ext2fs_extent_replace(ext2_extent_handle_t handle,
return 0;
}
+static int splitting_at_eof(struct ext2_extent_handle *handle,
+ struct extent_path *path)
+{
+ struct extent_path *ppp = path;
+ dump_path(__func__, handle, path);
+
+ if (handle->level == 0)
+ return 0;
+
+ do {
+ if (ppp->left)
+ return 0;
+ ppp--;
+ } while (ppp >= handle->path);
+
+ return 1;
+}
+
/*
* allocate a new block, move half the current node to it, and update parent
*
* handle will be left pointing at original record.
*/
-errcode_t ext2fs_extent_node_split(ext2_extent_handle_t handle)
+static errcode_t extent_node_split(ext2_extent_handle_t handle,
+ int expand_allowed)
{
errcode_t retval = 0;
blk64_t new_node_pblk;
@@ -834,6 +883,7 @@ errcode_t ext2fs_extent_node_split(ext2_extent_handle_t handle)
int tocopy;
int new_root = 0;
struct ext2_extent_info info;
+ int no_balance;
/* basic sanity */
EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE);
@@ -874,7 +924,7 @@ errcode_t ext2fs_extent_node_split(ext2_extent_handle_t handle)
goto done;
goal_blk = extent.e_pblk;
- retval = ext2fs_extent_node_split(handle);
+ retval = extent_node_split(handle, expand_allowed);
if (retval)
goto done;
@@ -889,6 +939,14 @@ errcode_t ext2fs_extent_node_split(ext2_extent_handle_t handle)
if (!path->curr)
return EXT2_ET_NO_CURRENT_NODE;
+ /*
+ * Normally, we try to split a full node in half. This doesn't turn
+ * out so well if we're tacking extents on the end of the file because
+ * then we're stuck with a tree of half-full extent blocks. This of
+ * course doesn't apply to the root level.
+ */
+ no_balance = expand_allowed ? splitting_at_eof(handle, path) : 0;
+
/* extent header of the current node we'll split */
eh = (struct ext3_extent_header *)path->buf;
@@ -904,7 +962,10 @@ errcode_t ext2fs_extent_node_split(ext2_extent_handle_t handle)
memset(newpath, 0,
((handle->max_depth+2) * sizeof(struct extent_path)));
} else {
- tocopy = ext2fs_le16_to_cpu(eh->eh_entries) / 2;
+ if (no_balance)
+ tocopy = 1;
+ else
+ tocopy = ext2fs_le16_to_cpu(eh->eh_entries) / 2;
}
#ifdef DEBUG
@@ -913,7 +974,7 @@ errcode_t ext2fs_extent_node_split(ext2_extent_handle_t handle)
handle->level);
#endif
- if (!tocopy) {
+ if (!tocopy && !no_balance) {
#ifdef DEBUG
printf("Nothing to copy to new block!\n");
#endif
@@ -1032,8 +1093,7 @@ errcode_t ext2fs_extent_node_split(ext2_extent_handle_t handle)
goto done;
/* new node hooked in, so update inode block count (do this here?) */
- handle->inode->i_blocks += (handle->fs->blocksize *
- EXT2FS_CLUSTER_RATIO(handle->fs)) / 512;
+ ext2fs_iblk_add_blocks(handle->fs, handle->inode, 1);
retval = ext2fs_write_inode(handle->fs, handle->ino,
handle->inode);
if (retval)
@@ -1047,6 +1107,11 @@ done:
return retval;
}
+errcode_t ext2fs_extent_node_split(ext2_extent_handle_t handle)
+{
+ return extent_node_split(handle, 0);
+}
+
errcode_t ext2fs_extent_insert(ext2_extent_handle_t handle, int flags,
struct ext2fs_extent *extent)
{
@@ -1078,7 +1143,7 @@ errcode_t ext2fs_extent_insert(ext2_extent_handle_t handle, int flags,
printf("node full (level %d) - splitting\n",
handle->level);
#endif
- retval = ext2fs_extent_node_split(handle);
+ retval = extent_node_split(handle, 1);
if (retval)
return retval;
path = handle->path + handle->level;