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>
diff --git a/lib/ext2fs/extent.c b/lib/ext2fs/extent.c
index 0bf82ea..c12bc93 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 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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
handle->level);
#endif
- if (!tocopy) {
+ if (!tocopy && !no_balance) {
#ifdef DEBUG
printf("Nothing to copy to new block!\n");
#endif
@@ -1032,8 +1093,7 @@
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 @@
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 @@
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;