[PATCH 1/3] libext2fs: ext2fs_node_split

[PATCH 1/3] libext2fs: ext2fs_node_split

[Eric Sandeen]

When called for a given handle, this function  will split the
current node such that half of the node's entries will be moved
to a new tree block.  The parent will then be updated to point
to the (now smaller) original node as well as the new node.

If the root node is requested to be split, it will move all
entries out to a new node, and leave a single entry in the
root pointing to that new node.

If the reqested split node's parent is full it will recursively
split up to the root to make room for the new node's insertion.

If you ask to split a non-root node with only one entry,
it will refuse (we'd have an empty node otherwise).

It also updates the i_blocks count when a new block has
successfully been connected to the tree.

Signed-off-by: Eric Sandeen <sandeen@redhat.com>
---
 lib/ext2fs/ext2_err.et.in |    3 +
 lib/ext2fs/extent.c       |  227 +++++++++++++++++++++++++++++++++++++++++++++
 lib/ext2fs/extent_dbg.ct  |    3 +
 3 files changed, 233 insertions(+), 0 deletions(-)

diff --git a/lib/ext2fs/ext2_err.et.in b/lib/ext2fs/ext2_err.et.in
index 9047a8f..73f9def 100644
--- a/lib/ext2fs/ext2_err.et.in
+++ b/lib/ext2fs/ext2_err.et.in
@@ -401,6 +401,9 @@ ec	EXT2_ET_OP_NOT_SUPPORTED,
 ec	EXT2_ET_CANT_INSERT_EXTENT,
 	"No room to insert extent in node"
 
+ec	EXT2_ET_CANT_SPLIT_EXTENT,
+	"Splitting would result in empty node"
+
 ec	EXT2_ET_EXTENT_NOT_FOUND,
 	"Extent not found"
 
diff --git a/lib/ext2fs/extent.c b/lib/ext2fs/extent.c
index b76abdc..41b5307 100644
--- a/lib/ext2fs/extent.c
+++ b/lib/ext2fs/extent.c
@@ -676,6 +676,206 @@ errcode_t ext2fs_extent_replace(ext2_extent_handle_t handle,
 	return 0;
 }
 
+/*
+ * 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_node_split(ext2_extent_handle_t handle, int flags)
+{
+	errcode_t			retval = 0;
+	blk_t				new_node_pblk;
+	blk64_t				new_node_start;
+	blk64_t				orig_lblk;
+	int				orig_height;
+	char				*block_buf = NULL;
+	struct ext2fs_extent		extent;
+	struct extent_path		*path;
+	struct ext3_extent		*ex;
+	struct ext3_extent_header	*eh, *neweh;
+	char				*cp;
+	int				tocopy;
+	int				new_root = 0;
+	struct ext2_extent_info		info;
+
+	/* basic sanity */
+	EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE);
+
+	if (!(handle->fs->flags & EXT2_FLAG_RW))
+		return EXT2_ET_RO_FILSYS;
+
+	if (!handle->path)
+		return EXT2_ET_NO_CURRENT_NODE;
+
+	dbg_printf("splitting node at level %d\n", handle->level);
+
+	retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent);
+	if (retval)
+		goto done;
+
+	retval = ext2fs_extent_get_info(handle, &info);
+	if (retval)
+		goto done;
+
+	/* save the position we were originally splitting... */
+	orig_height = info.max_depth - info.curr_level;
+	orig_lblk = extent.e_lblk;
+
+	/* Is there room in the parent for a new entry? */
+	if (handle->level &&
+			(handle->path[handle->level - 1].entries >=
+		 	 handle->path[handle->level - 1].max_entries)) {
+
+		dbg_printf("parent level %d full; splitting it too\n",
+							handle->level - 1);
+		/* split the parent */
+		retval = ext2fs_extent_get(handle, EXT2_EXTENT_UP, &extent);
+		if (retval)
+			goto done;
+		retval = ext2fs_node_split(handle, 0);
+		if (retval)
+			goto done;
+
+		/* get handle back to our original split position */
+		retval = extent_goto(handle, orig_height, orig_lblk);
+		if (retval)
+			goto done;
+	}
+
+	/* At this point, parent should have room for this split */
+	path = handle->path + handle->level;
+	if (!path->curr)
+		return EXT2_ET_NO_CURRENT_NODE;
+
+	/* extent header of the current node we'll split */
+	eh = (struct ext3_extent_header *)path->buf;
+
+	/* splitting root level means moving them all out */
+	if (handle->level == 0) {
+		new_root = 1;
+		tocopy = ext2fs_le16_to_cpu(eh->eh_entries);
+	} else {
+		tocopy = ext2fs_le16_to_cpu(eh->eh_entries) / 2;
+	}
+
+	dbg_printf("will copy out %d of %d entries at level %d\n",
+				tocopy, ext2fs_le16_to_cpu(eh->eh_entries),
+				handle->level);
+
+	/* XXX um, can we make an empty node? */
+	if (!tocopy) {
+		dbg_printf("Nothing to copy to new block!\n");
+		retval = EXT2_ET_CANT_SPLIT_EXTENT;
+		goto done;
+	}
+
+	/* first we need a new block, or can do nothing. */
+	block_buf = malloc(handle->fs->blocksize);
+	if (!block_buf) {
+		retval = ENOMEM;
+		goto done;
+	}
+
+	/* XXX FIXME this needs a decent goal block */
+	retval = ext2fs_alloc_block(handle->fs, 0, block_buf, &new_node_pblk);
+	if (retval)
+		goto done;
+
+	dbg_printf("will copy to new node at block %llu\n", new_node_pblk);
+
+	/* Copy data into new block buffer */
+	/* First the header for the new block... */
+	neweh = (struct ext3_extent_header *) block_buf;
+	memcpy(neweh, eh, sizeof(struct ext3_extent_header));
+	neweh->eh_entries = ext2fs_cpu_to_le16(tocopy);
+	neweh->eh_max = ext2fs_cpu_to_le16((handle->fs->blocksize -
+			 sizeof(struct ext3_extent_header)) /
+				sizeof(struct ext3_extent));
+
+	/* then the entries for the new block... */
+	memcpy(EXT_FIRST_INDEX(neweh),
+		EXT_FIRST_INDEX(eh) +
+			(ext2fs_le16_to_cpu(eh->eh_entries) - tocopy),
+		sizeof(struct ext3_extent_idx) * tocopy);
+
+	new_node_start = ext2fs_le32_to_cpu(EXT_FIRST_INDEX(neweh)->ei_block);
+
+	/* ...and write the new node block out to disk. */
+	retval = io_channel_write_blk(handle->fs->io, new_node_pblk, 1, block_buf);
+
+	if (retval)
+		goto done;
+
+	/* OK! we've created the new node; now adjust the tree */
+
+	/* current path now has fewer active entries, we copied some out */
+	if (handle->level == 0) {
+		path->entries = 1;
+		path->left = path->max_entries - 1;
+		handle->max_depth++;
+		eh->eh_depth = ext2fs_cpu_to_le16(handle->max_depth);
+	} else {
+		path->entries -= tocopy;
+		path->left -= tocopy;
+	}
+
+	eh->eh_entries = ext2fs_cpu_to_le16(path->entries);
+	/* this writes out the node, incl. the modified header */
+	retval = update_path(handle);
+	if (retval)
+		goto done;
+
+	/* now go up and insert/replace index for new node we created */
+	if (new_root) {
+		retval = ext2fs_extent_get(handle, EXT2_EXTENT_FIRST_SIB, &extent);
+		if (retval)
+			goto done;
+
+		extent.e_lblk = new_node_start;
+		extent.e_pblk = new_node_pblk;
+		extent.e_len = handle->path[0].end_blk - extent.e_lblk;
+		retval = ext2fs_extent_replace(handle, 0, &extent);
+		if (retval)
+			goto done;
+	} else {
+		__u32 new_node_length;
+
+		retval = ext2fs_extent_get(handle, EXT2_EXTENT_UP, &extent);
+		/* will insert after this one; it's length is shorter now */
+		new_node_length = new_node_start - extent.e_lblk;
+		extent.e_len -= new_node_length;
+		retval = ext2fs_extent_replace(handle, 0, &extent);
+		if (retval)
+			goto done;
+
+		/* now set up the new extent and insert it */
+		extent.e_lblk = new_node_start;
+		extent.e_pblk = new_node_pblk;
+		extent.e_len = new_node_length;
+		retval = ext2fs_extent_insert(handle, EXT2_EXTENT_INSERT_AFTER, &extent);
+		if (retval)
+			goto done;
+	}
+
+	/* get handle back to our original position */
+	retval = extent_goto(handle, orig_height, orig_lblk);
+	if (retval)
+		goto done;
+
+	/* new node hooked in, so update inode block count (do this here?) */
+	handle->inode->i_blocks += handle->fs->blocksize / 512;
+	retval = ext2fs_write_inode_full(handle->fs, handle->ino,
+		handle->inode, EXT2_INODE_SIZE(handle->fs->super));
+	if (retval)
+		goto done;
+
+done:
+	if (block_buf)
+		free(block_buf);
+
+	return retval;
+}
+
 errcode_t ext2fs_extent_insert(ext2_extent_handle_t handle, int flags,
 				      struct ext2fs_extent *extent)
 {
@@ -998,6 +1198,33 @@ void do_replace_node(int argc, char *argv[])
 	do_current_node(argc, argv);
 }
 
+void do_split_node(int argc, char *argv[])
+{
+	errcode_t	retval;
+	struct ext2fs_extent extent;
+	char *cmd;
+	int err;
+	int flags = 0;
+
+	if (check_fs_open(argv[0]))
+		return;
+
+	if (check_fs_read_write(argv[0]))
+		return;
+
+	if (!current_handle) {
+		com_err(argv[0], 0, "Extent handle not open");
+		return;
+	}
+
+	retval = ext2fs_node_split(current_handle, flags);
+	if (retval) {
+		com_err(cmd, retval, 0);
+		return;
+	}
+	do_current_node(argc, argv);
+}
+
 void do_insert_node(int argc, char *argv[])
 {
 	errcode_t	retval;
diff --git a/lib/ext2fs/extent_dbg.ct b/lib/ext2fs/extent_dbg.ct
index 41299fa..788fdab 100644
--- a/lib/ext2fs/extent_dbg.ct
+++ b/lib/ext2fs/extent_dbg.ct
@@ -52,6 +52,9 @@ request do_delete_node, "Delete node",
 request do_insert_node, "Insert node",
 	insert_node, insert;
 
+request do_split_node, "Split node",
+	split_node, split;
+
 request do_replace_node, "Insert node",
 	replace_node, replace;
 
-- 
1.5.4.1

Re: [PATCH 1/3] libext2fs: ext2fs_node_split

[Theodore Tso]

On Thu, May 15, 2008 at 01:17:42PM -0500, Eric Sandeen wrote:
> When called for a given handle, this function  will split the
> current node such that half of the node's entries will be moved
> to a new tree block.  The parent will then be updated to point
> to the (now smaller) original node as well as the new node.

This patch looks good.  One minor nit; if you're going to define new
functions which are intended to be exported, then they need to be
defined in the ext2fs.h header file --- otherwise, it should be
declared static, to prevent function leakage.  Should
ext2fs_node_split() be exported?  There doesn't seem to be any reason
*not* to export it, but at the same time, there doesn't seem to be a
good reason to export, either.

I'd tend to keep it static for now; what do other people think?

        	    	    	       	    	 - Ted

Re: [PATCH 1/3] libext2fs: ext2fs_node_split

[Eric Sandeen]

Theodore Tso wrote:
> On Thu, May 15, 2008 at 01:17:42PM -0500, Eric Sandeen wrote:
>> When called for a given handle, this function  will split the
>> current node such that half of the node's entries will be moved
>> to a new tree block.  The parent will then be updated to point
>> to the (now smaller) original node as well as the new node.
> 
> This patch looks good.  One minor nit; if you're going to define new
> functions which are intended to be exported, then they need to be
> defined in the ext2fs.h header file --- otherwise, it should be
> declared static, to prevent function leakage.  Should
> ext2fs_node_split() be exported?  There doesn't seem to be any reason
> *not* to export it, but at the same time, there doesn't seem to be a
> good reason to export, either.
> 
> I'd tend to keep it static for now; what do other people think?

I'd say static until needed otherwise...

an  _extent_split might be more useful for a public interface;
_node_split is getting awfully low level IMHO.

-Eric

Re: [PATCH 1/3] libext2fs: ext2fs_node_split

[Theodore Tso]

> +	/* splitting root level means moving them all out */
> +	if (handle->level == 0) {
> +		new_root = 1;
> +		tocopy = ext2fs_le16_to_cpu(eh->eh_entries);
> +	} else {
> +		tocopy = ext2fs_le16_to_cpu(eh->eh_entries) / 2;
> +	}

This is probably in the "would be nice" category, but if we know that
we are appending to the file, it might actually be better to move all
of the entries into one block, and create an empty block to the right.
That way, the average density of the leaf nodes will be much closer to
100%, instead of 50% full.

This optimization is far more important in the kernel, though.

     		     	      		       - Ted

[PATCH 2/3] libext2fs: allow ext2fs_extent_insert to split if needed

[Eric Sandeen]

If ext2fs_extent_insert finds that the requested node
for insertion is full, it will currently fail.

With this patch it will split as necessary to make room.

Signed-off-by: Eric Sandeen <sandeen@redhat.com>
---
 lib/ext2fs/extent.c |   11 ++++++++---
 1 files changed, 8 insertions(+), 3 deletions(-)

diff --git a/lib/ext2fs/extent.c b/lib/ext2fs/extent.c
index 41b5307..8a6eaa2 100644
--- a/lib/ext2fs/extent.c
+++ b/lib/ext2fs/extent.c
@@ -894,8 +894,13 @@ errcode_t ext2fs_extent_insert(ext2_extent_handle_t handle, int flags,
 
 	path = handle->path + handle->level;
 
-	if (path->entries >= path->max_entries)
-		return EXT2_ET_CANT_INSERT_EXTENT;
+	if (path->entries >= path->max_entries) {
+		dbg_printf("node full - splitting\n");
+		retval = ext2fs_node_split(handle, 0);
+		if (retval)
+			goto errout;
+		path = handle->path + handle->level;
+	}
 
 	eh = (struct ext3_extent_header *) path->buf;
 	if (path->curr) {
@@ -1245,7 +1250,7 @@ void do_insert_node(int argc, char *argv[])
 	}
 
 	if (argc != 4) {
-		fprintf(stderr, "usage: %s <lblk> <len> <pblk>\n", cmd);
+		fprintf(stderr, "usage: %s [--after] <lblk> <len> <pblk>\n", cmd);
 		return;
 	}
 
-- 
1.5.4.1

[PATCH 3/3] libext2fs: add ext2fs_extent_set_bmap

[Eric Sandeen]

Allows unmapping or remapping single mapped logical blocks,
and mapping currently unmapped blocks.

Also implements ext2fs_extent_fix_parents() to fix parent
index logical starts, if the first index of a node changes
its logical start block.

Currently this results in new single-block extents; I think
perhaps ext2fs_extent_insert should grow a flag to request
merging with a nearby extent?

Signed-off-by: Eric Sandeen <sandeen@redhat.com>
---
 lib/ext2fs/extent.c      |  263 ++++++++++++++++++++++++++++++++++++++++++++++
 lib/ext2fs/extent_dbg.ct |    3 +
 2 files changed, 266 insertions(+), 0 deletions(-)

diff --git a/lib/ext2fs/extent.c b/lib/ext2fs/extent.c
index 8a6eaa2..821c05f 100644
--- a/lib/ext2fs/extent.c
+++ b/lib/ext2fs/extent.c
@@ -637,6 +637,64 @@ errcode_t ext2fs_extent_goto(ext2_extent_handle_t handle,
 	return extent_goto(handle, 0, blk);
 }
 
+/*
+ * Traverse back up to root fixing parents of current node as needed.
+ *
+ * If we changed start of first entry in a node, fix parent index start
+ * and so on.
+ *
+ * Safe to call for any position in node; if not at the first entry,
+ * will  simply return.
+ */
+errcode_t ext2fs_extent_fix_parents(ext2_extent_handle_t handle)
+{
+	int				retval = 0;
+	blk64_t				start;
+	struct extent_path		*path;
+	struct ext2fs_extent		extent;
+
+	EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE);
+
+	if (!(handle->fs->flags & EXT2_FLAG_RW))
+		return EXT2_ET_RO_FILSYS;
+
+	if (!handle->path)
+		return EXT2_ET_NO_CURRENT_NODE;
+
+	path = handle->path + handle->level;
+	if (!path->curr)
+		return EXT2_ET_NO_CURRENT_NODE;
+
+	retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent);
+	if (retval)
+		goto done;
+
+	/* modified node's start block */
+	start = extent.e_lblk;
+
+	/* traverse up until index not first, or startblk matches, or top */
+	while (handle->level > 0 &&
+	       (path->left == path->entries - 1)) {
+		retval = ext2fs_extent_get(handle, EXT2_EXTENT_UP, &extent);
+		if (retval)
+			goto done;
+		if (extent.e_lblk == start)
+			break;
+		path = handle->path + handle->level;
+		extent.e_len += (extent.e_lblk - start);
+		extent.e_lblk = start;
+		retval = ext2fs_extent_replace(handle, 0, &extent);
+		if (retval)
+			goto done;
+		update_path(handle);
+	}
+
+	/* put handle back to where we started */
+	retval = ext2fs_extent_goto(handle, start);
+done:
+	return retval;
+}
+
 errcode_t ext2fs_extent_replace(ext2_extent_handle_t handle, 
 				int flags EXT2FS_ATTR((unused)),
 				struct ext2fs_extent *extent)
@@ -938,6 +996,175 @@ errout:
 	return retval;
 }
 
+/*
+ * Sets the physical block for a logical file block in the extent tree.
+ *
+ * May: map unmapped, unmap mapped, or remap mapped blocks.
+ *
+ * Mapping an unmapped block adds a single-block extent.
+ *
+ * Unmapping first or last block modifies extent in-place
+ *  - But may need to fix parent's starts too in first-block case
+ *
+ * Mapping any unmapped block requires adding a (single-block) extent
+ * and inserting into proper point in tree.
+ *
+ * Modifying (unmapping or remapping) a block in the middle
+ * of an extent requires splitting the extent.
+ *  - Remapping case requires new single-block extent.
+ *
+ * Remapping first or last block adds an extent.
+ *
+ * We really need extent adding to be smart about merging.
+ */
+
+errcode_t ext2fs_extent_set_bmap(ext2_extent_handle_t handle,
+				 blk64_t logical, blk64_t physical)
+{
+	int			retval = 0;
+	int			mapped = 1; /* logical is mapped? */
+	struct extent_path	*path;
+	struct ext2fs_extent	extent;
+	struct ext2fs_extent	newextent;
+
+	EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE);
+
+	if (!(handle->fs->flags & EXT2_FLAG_RW))
+		return EXT2_ET_RO_FILSYS;
+
+	/* go to the logical spot we want to (re/un)map */
+	retval = ext2fs_extent_goto(handle, logical);
+	if (retval) {
+		if (retval == EXT2_ET_EXTENT_NOT_FOUND) {
+			retval = 0;
+			mapped = 0;
+			if (!physical) {
+				dbg_printf("block already unmapped\n");
+				goto done;
+			}
+		} else
+			goto done;
+	}
+
+	if (!handle->path)
+		return EXT2_ET_NO_CURRENT_NODE;
+
+	path = handle->path + handle->level;
+	if (!path->curr)
+		return EXT2_ET_NO_CURRENT_NODE;
+
+	/*
+	 * This may be the extent *before* the requested logical,
+	 * if it's currently unmapped.
+	 */
+	retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent);
+	if (retval)
+		goto done;
+
+	/* check if already pointing to the requested physical */
+	if (mapped && extent.e_pblk + (logical - extent.e_lblk) == physical) {
+		dbg_printf("physical block unchanged\n");
+		goto done;
+	}
+
+	/* if (re)mapping, set up new extent, we'll insert it later */
+	if (physical) {
+		newextent.e_len = 1;
+		newextent.e_pblk = physical;
+		newextent.e_lblk = logical;
+		newextent.e_flags = EXT2_EXTENT_FLAGS_LEAF;
+	}
+
+	if (!mapped) {
+		dbg_printf("mapping unmapped logical block\n");
+		retval = ext2fs_extent_insert(handle,
+				EXT2_EXTENT_INSERT_AFTER, &newextent);
+		if (retval)
+			goto done;
+		retval = ext2fs_extent_fix_parents(handle);
+		if (retval)
+			goto done;
+	} else if (logical == extent.e_lblk + extent.e_len - 1 &&
+		   extent.e_len == 1)  {
+		dbg_printf("(re/un)mapping only block in extent\n");
+		if (physical) {
+			extent.e_pblk = physical;
+			retval = ext2fs_extent_replace(handle, 0, &extent);
+		} else {
+			retval = ext2fs_extent_delete(handle, 0);
+			if (retval)
+				goto done;
+			retval = ext2fs_extent_fix_parents(handle);
+		}
+
+		if (retval)
+			goto done;
+	} else if (logical == extent.e_lblk + extent.e_len - 1)  {
+		dbg_printf("(re/un)mapping last block in extent\n");
+		extent.e_len--;
+		retval = ext2fs_extent_replace(handle, 0, &extent);
+		if (retval)
+			goto done;
+		if (physical) {
+			retval = ext2fs_extent_insert(handle,
+					EXT2_EXTENT_INSERT_AFTER, &newextent);
+			if (retval)
+				goto done;
+		}
+	} else if (logical == extent.e_lblk) {
+		dbg_printf("(re/un)mapping first block in extent\n");
+		extent.e_pblk++;
+		extent.e_lblk++;
+		extent.e_len--;
+		retval = ext2fs_extent_replace(handle, 0, &extent);
+		if (retval)
+			goto done;
+		if (physical) {
+			/* insert new extent ahead of current */
+			retval = ext2fs_extent_insert(handle,
+					0, &newextent);
+			if (retval)
+				goto done;
+		} else {
+			retval = ext2fs_extent_fix_parents(handle);
+			if (retval)
+				goto done;
+		}
+	} else {
+		__u32	orig_length;
+
+		dbg_printf("(re/un)mapping in middle of extent\n");
+		/* need to split this extent; later */
+
+		orig_length = extent.e_len;
+
+		/* shorten pre-split extent */
+		extent.e_len = (logical - extent.e_lblk);
+		retval = ext2fs_extent_replace(handle, 0, &extent);
+		if (retval)
+			goto done;
+		/* insert our new extent, if any */
+		if (physical) {
+			/* insert new extent after current */
+			retval = ext2fs_extent_insert(handle,
+					EXT2_EXTENT_INSERT_AFTER, &newextent);
+			if (retval)
+				goto done;
+		}
+		/* add post-split extent */
+		extent.e_pblk += extent.e_len + 1;
+		extent.e_lblk += extent.e_len + 1;
+		extent.e_len = orig_length - extent.e_len - 1;
+		retval = ext2fs_extent_insert(handle,
+				EXT2_EXTENT_INSERT_AFTER, &extent);
+		if (retval)
+			goto done;
+	}
+
+done:
+	return retval;
+}
+
 errcode_t ext2fs_extent_delete(ext2_extent_handle_t handle, 
 			       int flags EXT2FS_ATTR((unused)))
 {
@@ -1277,6 +1504,42 @@ void do_insert_node(int argc, char *argv[])
 	do_current_node(argc, argv);
 }
 
+void do_set_bmap(int argc, char **argv)
+{
+	errcode_t	retval;
+	blk_t		logical;
+	blk_t		physical;
+	char *cmd;
+	int err;
+
+	if (check_fs_read_write(argv[0]))
+		return;
+
+	cmd = argv[0];
+
+	if (argc != 3) {
+		fprintf(stderr, "usage: %s <lblk> <pblk>\n", cmd);
+		return;
+	}
+
+	logical = parse_ulong(argv[1], cmd,
+				    "logical block", &err);
+	if (err)
+		return;
+
+	physical = parse_ulong(argv[2], cmd,
+				    "physical block", &err);
+	if (err)
+		return;
+
+	retval = ext2fs_extent_set_bmap(current_handle, logical, (blk64_t) physical);
+	if (retval) {
+		com_err(cmd, retval, 0);
+		return;
+	}
+	do_current_node(argc, argv);
+}
+
 void do_print_all(int argc, char **argv)
 {
 	struct ext2fs_extent	extent;
diff --git a/lib/ext2fs/extent_dbg.ct b/lib/ext2fs/extent_dbg.ct
index 788fdab..d0571f4 100644
--- a/lib/ext2fs/extent_dbg.ct
+++ b/lib/ext2fs/extent_dbg.ct
@@ -55,6 +55,9 @@ request do_insert_node, "Insert node",
 request do_split_node, "Split node",
 	split_node, split;
 
+request do_set_bmap, "Set block mapping",
+	set_bmap;
+
 request do_replace_node, "Insert node",
 	replace_node, replace;
 
-- 
1.5.4.1

[PATCH 0/3] e2fsprogs set_bmap & friends V2

[Eric Sandeen]

resend of the original 3 patches first, to address Ted's minor comments.

Then will follow up with the extent_delete fixups as a separate patch.

-Eric

[PATCH 1/3] libext2fs: ext2fs_node_split

[Eric Sandeen]

When called for a given handle, this function  will split the
current node such that half of the node's entries will be moved
to a new tree block.  The parent will then be updated to point
to the (now smaller) original node as well as the new node.

If the root node is requested to be split, it will move all
entries out to a new node, and leave a single entry in the
root pointing to that new node.

If the reqested split node's parent is full it will recursively
split up to the root to make room for the new node's insertion.

If you ask to split a non-root node with only one entry,
it will refuse (we'd have an empty node otherwise).

It also updates the i_blocks count when a new block has
successfully been connected to the tree.

Signed-off-by: Eric Sandeen <sandeen@redhat.com>
---
 lib/ext2fs/ext2_err.et.in |    3 +
 lib/ext2fs/extent.c       |  227 +++++++++++++++++++++++++++++++++++++++++++++
 lib/ext2fs/extent_dbg.ct  |    3 +
 3 files changed, 233 insertions(+), 0 deletions(-)

diff --git a/lib/ext2fs/ext2_err.et.in b/lib/ext2fs/ext2_err.et.in
index 9047a8f..73f9def 100644
--- a/lib/ext2fs/ext2_err.et.in
+++ b/lib/ext2fs/ext2_err.et.in
@@ -401,6 +401,9 @@ ec	EXT2_ET_OP_NOT_SUPPORTED,
 ec	EXT2_ET_CANT_INSERT_EXTENT,
 	"No room to insert extent in node"
 
+ec	EXT2_ET_CANT_SPLIT_EXTENT,
+	"Splitting would result in empty node"
+
 ec	EXT2_ET_EXTENT_NOT_FOUND,
 	"Extent not found"
 
diff --git a/lib/ext2fs/extent.c b/lib/ext2fs/extent.c
index b76abdc..5ec5c3e 100644
--- a/lib/ext2fs/extent.c
+++ b/lib/ext2fs/extent.c
@@ -676,6 +676,206 @@ errcode_t ext2fs_extent_replace(ext2_extent_handle_t handle,
 	return 0;
 }
 
+/*
+ * allocate a new block, move half the current node to it, and update parent
+ *
+ * handle will be left pointing at original record.
+ */
+static errcode_t ext2fs_node_split(ext2_extent_handle_t handle, int flags)
+{
+	errcode_t			retval = 0;
+	blk_t				new_node_pblk;
+	blk64_t				new_node_start;
+	blk64_t				orig_lblk;
+	int				orig_height;
+	char				*block_buf = NULL;
+	struct ext2fs_extent		extent;
+	struct extent_path		*path;
+	struct ext3_extent		*ex;
+	struct ext3_extent_header	*eh, *neweh;
+	char				*cp;
+	int				tocopy;
+	int				new_root = 0;
+	struct ext2_extent_info		info;
+
+	/* basic sanity */
+	EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE);
+
+	if (!(handle->fs->flags & EXT2_FLAG_RW))
+		return EXT2_ET_RO_FILSYS;
+
+	if (!handle->path)
+		return EXT2_ET_NO_CURRENT_NODE;
+
+	dbg_printf("splitting node at level %d\n", handle->level);
+
+	retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent);
+	if (retval)
+		goto done;
+
+	retval = ext2fs_extent_get_info(handle, &info);
+	if (retval)
+		goto done;
+
+	/* save the position we were originally splitting... */
+	orig_height = info.max_depth - info.curr_level;
+	orig_lblk = extent.e_lblk;
+
+	/* Is there room in the parent for a new entry? */
+	if (handle->level &&
+			(handle->path[handle->level - 1].entries >=
+		 	 handle->path[handle->level - 1].max_entries)) {
+
+		dbg_printf("parent level %d full; splitting it too\n",
+							handle->level - 1);
+		/* split the parent */
+		retval = ext2fs_extent_get(handle, EXT2_EXTENT_UP, &extent);
+		if (retval)
+			goto done;
+		retval = ext2fs_node_split(handle, 0);
+		if (retval)
+			goto done;
+
+		/* get handle back to our original split position */
+		retval = extent_goto(handle, orig_height, orig_lblk);
+		if (retval)
+			goto done;
+	}
+
+	/* At this point, parent should have room for this split */
+	path = handle->path + handle->level;
+	if (!path->curr)
+		return EXT2_ET_NO_CURRENT_NODE;
+
+	/* extent header of the current node we'll split */
+	eh = (struct ext3_extent_header *)path->buf;
+
+	/* splitting root level means moving them all out */
+	if (handle->level == 0) {
+		new_root = 1;
+		tocopy = ext2fs_le16_to_cpu(eh->eh_entries);
+	} else {
+		tocopy = ext2fs_le16_to_cpu(eh->eh_entries) / 2;
+	}
+
+	dbg_printf("will copy out %d of %d entries at level %d\n",
+				tocopy, ext2fs_le16_to_cpu(eh->eh_entries),
+				handle->level);
+
+	/* XXX um, can we make an empty node? */
+	if (!tocopy) {
+		dbg_printf("Nothing to copy to new block!\n");
+		retval = EXT2_ET_CANT_SPLIT_EXTENT;
+		goto done;
+	}
+
+	/* first we need a new block, or can do nothing. */
+	block_buf = malloc(handle->fs->blocksize);
+	if (!block_buf) {
+		retval = ENOMEM;
+		goto done;
+	}
+
+	/* XXX FIXME this needs a decent goal block */
+	retval = ext2fs_alloc_block(handle->fs, 0, block_buf, &new_node_pblk);
+	if (retval)
+		goto done;
+
+	dbg_printf("will copy to new node at block %llu\n", new_node_pblk);
+
+	/* Copy data into new block buffer */
+	/* First the header for the new block... */
+	neweh = (struct ext3_extent_header *) block_buf;
+	memcpy(neweh, eh, sizeof(struct ext3_extent_header));
+	neweh->eh_entries = ext2fs_cpu_to_le16(tocopy);
+	neweh->eh_max = ext2fs_cpu_to_le16((handle->fs->blocksize -
+			 sizeof(struct ext3_extent_header)) /
+				sizeof(struct ext3_extent));
+
+	/* then the entries for the new block... */
+	memcpy(EXT_FIRST_INDEX(neweh),
+		EXT_FIRST_INDEX(eh) +
+			(ext2fs_le16_to_cpu(eh->eh_entries) - tocopy),
+		sizeof(struct ext3_extent_idx) * tocopy);
+
+	new_node_start = ext2fs_le32_to_cpu(EXT_FIRST_INDEX(neweh)->ei_block);
+
+	/* ...and write the new node block out to disk. */
+	retval = io_channel_write_blk(handle->fs->io, new_node_pblk, 1, block_buf);
+
+	if (retval)
+		goto done;
+
+	/* OK! we've created the new node; now adjust the tree */
+
+	/* current path now has fewer active entries, we copied some out */
+	if (handle->level == 0) {
+		path->entries = 1;
+		path->left = path->max_entries - 1;
+		handle->max_depth++;
+		eh->eh_depth = ext2fs_cpu_to_le16(handle->max_depth);
+	} else {
+		path->entries -= tocopy;
+		path->left -= tocopy;
+	}
+
+	eh->eh_entries = ext2fs_cpu_to_le16(path->entries);
+	/* this writes out the node, incl. the modified header */
+	retval = update_path(handle);
+	if (retval)
+		goto done;
+
+	/* now go up and insert/replace index for new node we created */
+	if (new_root) {
+		retval = ext2fs_extent_get(handle, EXT2_EXTENT_FIRST_SIB, &extent);
+		if (retval)
+			goto done;
+
+		extent.e_lblk = new_node_start;
+		extent.e_pblk = new_node_pblk;
+		extent.e_len = handle->path[0].end_blk - extent.e_lblk;
+		retval = ext2fs_extent_replace(handle, 0, &extent);
+		if (retval)
+			goto done;
+	} else {
+		__u32 new_node_length;
+
+		retval = ext2fs_extent_get(handle, EXT2_EXTENT_UP, &extent);
+		/* will insert after this one; it's length is shorter now */
+		new_node_length = new_node_start - extent.e_lblk;
+		extent.e_len -= new_node_length;
+		retval = ext2fs_extent_replace(handle, 0, &extent);
+		if (retval)
+			goto done;
+
+		/* now set up the new extent and insert it */
+		extent.e_lblk = new_node_start;
+		extent.e_pblk = new_node_pblk;
+		extent.e_len = new_node_length;
+		retval = ext2fs_extent_insert(handle, EXT2_EXTENT_INSERT_AFTER, &extent);
+		if (retval)
+			goto done;
+	}
+
+	/* get handle back to our original position */
+	retval = extent_goto(handle, orig_height, orig_lblk);
+	if (retval)
+		goto done;
+
+	/* new node hooked in, so update inode block count (do this here?) */
+	handle->inode->i_blocks += handle->fs->blocksize / 512;
+	retval = ext2fs_write_inode_full(handle->fs, handle->ino,
+		handle->inode, EXT2_INODE_SIZE(handle->fs->super));
+	if (retval)
+		goto done;
+
+done:
+	if (block_buf)
+		free(block_buf);
+
+	return retval;
+}
+
 errcode_t ext2fs_extent_insert(ext2_extent_handle_t handle, int flags,
 				      struct ext2fs_extent *extent)
 {
@@ -998,6 +1198,33 @@ void do_replace_node(int argc, char *argv[])
 	do_current_node(argc, argv);
 }
 
+void do_split_node(int argc, char *argv[])
+{
+	errcode_t	retval;
+	struct ext2fs_extent extent;
+	char *cmd;
+	int err;
+	int flags = 0;
+
+	if (check_fs_open(argv[0]))
+		return;
+
+	if (check_fs_read_write(argv[0]))
+		return;
+
+	if (!current_handle) {
+		com_err(argv[0], 0, "Extent handle not open");
+		return;
+	}
+
+	retval = ext2fs_node_split(current_handle, flags);
+	if (retval) {
+		com_err(cmd, retval, 0);
+		return;
+	}
+	do_current_node(argc, argv);
+}
+
 void do_insert_node(int argc, char *argv[])
 {
 	errcode_t	retval;
diff --git a/lib/ext2fs/extent_dbg.ct b/lib/ext2fs/extent_dbg.ct
index 41299fa..788fdab 100644
--- a/lib/ext2fs/extent_dbg.ct
+++ b/lib/ext2fs/extent_dbg.ct
@@ -52,6 +52,9 @@ request do_delete_node, "Delete node",
 request do_insert_node, "Insert node",
 	insert_node, insert;
 
+request do_split_node, "Split node",
+	split_node, split;
+
 request do_replace_node, "Insert node",
 	replace_node, replace;
 
-- 1.5.4.1

Re: [PATCH 1/3] libext2fs: ext2fs_node_split

[Theodore Tso]

FYI, I applied the following change to your patch to add support for
correct goal_block calculation.  We may eventually want to factor this
out into its own libext2fs function, since there are other places in
libext2fs which are defaulting the goal block to 0, and it would be
good to make things consistent (and flex_bg allocation policy aware).

    	     	    	       	    	    	       - Ted

diff --git a/lib/ext2fs/extent.c b/lib/ext2fs/extent.c
index b85a259..0fa2b2b 100644
--- a/lib/ext2fs/extent.c
+++ b/lib/ext2fs/extent.c
@@ -687,6 +687,7 @@ static errcode_t ext2fs_node_split(ext2_extent_handle_t handle, int flags)
 	blk_t				new_node_pblk;
 	blk64_t				new_node_start;
 	blk64_t				orig_lblk;
+	blk64_t				goal_blk = 0;
 	int				orig_height;
 	char				*block_buf = NULL;
 	struct ext2fs_extent		extent;
@@ -732,6 +733,8 @@ static errcode_t ext2fs_node_split(ext2_extent_handle_t handle, int flags)
 		retval = ext2fs_extent_get(handle, EXT2_EXTENT_UP, &extent);
 		if (retval)
 			goto done;
+		goal_blk = extent.e_pblk;
+
 		retval = ext2fs_node_split(handle, 0);
 		if (retval)
 			goto done;
@@ -762,7 +765,6 @@ static errcode_t ext2fs_node_split(ext2_extent_handle_t handle, int flags)
 				tocopy, ext2fs_le16_to_cpu(eh->eh_entries),
 				handle->level);
 
-	/* XXX um, can we make an empty node? */
 	if (!tocopy) {
 		dbg_printf("Nothing to copy to new block!\n");
 		retval = EXT2_ET_CANT_SPLIT_EXTENT;
@@ -776,8 +778,17 @@ static errcode_t ext2fs_node_split(ext2_extent_handle_t handle, int flags)
 		goto done;
 	}
 
-	/* XXX FIXME this needs a decent goal block */
-	retval = ext2fs_alloc_block(handle->fs, 0, block_buf, &new_node_pblk);
+	if (!goal_blk) {
+		dgrp_t	group = ext2fs_group_of_ino(handle->fs, handle->ino);
+		__u8	log_flex = handle->fs->super->s_log_groups_per_flex;
+
+		if (log_flex)
+			group = group & ~((1 << (log_flex)) - 1);
+		goal_blk = (group * handle->fs->super->s_blocks_per_group) +
+			handle->fs->super->s_first_data_block;
+	}
+	retval = ext2fs_alloc_block(handle->fs, (blk_t) goal_blk, block_buf, 
+				    &new_node_pblk);
 	if (retval)
 		goto done;
 

Re: [PATCH 1/3] libext2fs: ext2fs_node_split

[Theodore Tso]

FYI, while doing some more testing, I found another bug in this patch.
It doesn't reallocate and update the handle->path array, with the net
result future operations will result in a core dump as we overrun the
handle->path array and fetch an illegal pointer from handle->path[n].buf.

The fix follows....

						- Ted

diff --git a/lib/ext2fs/extent.c b/lib/ext2fs/extent.c
index 29f6cdd..d421a4b 100644
--- a/lib/ext2fs/extent.c
+++ b/lib/ext2fs/extent.c
@@ -772,7 +772,7 @@ static errcode_t extent_node_split(ext2_extent_handle_t handle, int flags)
 	int				orig_height;
 	char				*block_buf = NULL;
 	struct ext2fs_extent		extent;
-	struct extent_path		*path;
+	struct extent_path		*path, *newpath = 0;
 	struct ext3_extent		*ex;
 	struct ext3_extent_header	*eh, *neweh;
 	char				*cp;
@@ -838,6 +838,13 @@ static errcode_t extent_node_split(ext2_extent_handle_t handle, int flags)
 	if (handle->level == 0) {
 		new_root = 1;
 		tocopy = ext2fs_le16_to_cpu(eh->eh_entries);
+		retval = ext2fs_get_mem(((handle->max_depth+2) *
+					 sizeof(struct extent_path)),
+					&newpath);
+		if (retval)
+			goto done;
+		memset(newpath, 0,
+		       ((handle->max_depth+2) * sizeof(struct extent_path)));
 	} else {
 		tocopy = ext2fs_le16_to_cpu(eh->eh_entries) / 2;
 	}
@@ -873,7 +880,7 @@ static errcode_t extent_node_split(ext2_extent_handle_t handle, int flags)
 	if (retval)
 		goto done;
 
-	dbg_printf("will copy to new node at block %llu\n", new_node_pblk);
+	dbg_printf("will copy to new node at block %lu\n", new_node_pblk);
 
 	/* Copy data into new block buffer */
 	/* First the header for the new block... */
@@ -902,6 +909,11 @@ static errcode_t extent_node_split(ext2_extent_handle_t handle, int flags)
 
 	/* current path now has fewer active entries, we copied some out */
 	if (handle->level == 0) {
+		memcpy(newpath, path,
+		       sizeof(struct extent_path) * (handle->max_depth+1));
+		handle->path = newpath;
+		newpath = path;
+		path = handle->path;
 		path->entries = 1;
 		path->left = path->max_entries - 1;
 		handle->max_depth++;
@@ -962,6 +974,8 @@ static errcode_t extent_node_split(ext2_extent_handle_t handle, int flags)
 		goto done;
 
 done:
+	if (newpath)
+		ext2fs_free_mem(&newpath);
 	if (block_buf)
 		free(block_buf);