Skip to contentSkip to conversation

e2fsprogs set_bmap & friends V2

PATCH In review Eric Sandeen 2 participants 7 messages May 20, 2008 – Jun 2, 2008

lore
Share & tools
lore

Eric Sandeen

author
#0 lore raw

cover e2fsprogs set_bmap & friends V2

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

author
#1 lore raw

PATCH 1/3 libext2fs: ext2fs_node_split

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 <[email protected]>
---
 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(-)
lib/ext2fs/ext2_err.et.in +3 -0
index 9047a8f..73f9def 100644
@@ -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"
lib/ext2fs/extent.c +227 -0

239 lines not on this page · raw message

lib/ext2fs/extent_dbg.ct +3 -0
index 41299fa..788fdab 100644
@@ -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

#2 lore raw

Re: [PATCH 1/3] libext2fs: ext2fs_node_split

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

lib/ext2fs/extent.c +14 -3
index b85a259..0fa2b2b 100644
@@ -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;
#3 lore raw

Re: [PATCH 1/3] libext2fs: ext2fs_node_split

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

lib/ext2fs/extent.c +16 -2
index 29f6cdd..d421a4b 100644
@@ -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);
author
#4 lore raw

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

In reply to 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, unless an EXT2_EXTENT_INSERT_NOSPLIT flag is sent in.

Signed-off-by Eric Sandeen <[email protected]>
---
 lib/ext2fs/ext2fs.h |    4 ++--
 lib/ext2fs/extent.c |   15 ++++++++++++---
 2 files changed, 14 insertions(+), 5 deletions(-)
lib/ext2fs/ext2fs.h +2 -2
index 7a1d966..30ca906 100644
@@ -332,8 +332,8 @@ typedef struct ext2_extent_path *ext2_extent_path_t;
 /*
  * Flags used by ext2fs_extent_insert()
  */
-
-#define EXT2_EXTENT_INSERT_AFTER  0x0001
+#define EXT2_EXTENT_INSERT_AFTER	0x0001 /* insert after handle loc'n */
+#define EXT2_EXTENT_INSERT_NOSPLIT	0x0002 /* insert may not cause split */
 
 /*
  * Data structure returned by ext2fs_extent_get_info()
lib/ext2fs/extent.c +12 -3
index 5ec5c3e..34719d5 100644
@@ -894,8 +894,17 @@ 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) {
+		if (flags & EXT2_EXTENT_INSERT_NOSPLIT) {
+			return EXT2_ET_CANT_INSERT_EXTENT;
+		} else {
+			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 +1254,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

author
#5 lore raw

PATCH 3/3 libext2fs: add ext2fs_extent_set_bmap

In reply to 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 <[email protected]>
---
 lib/ext2fs/ext2fs.h      |    2 +
 lib/ext2fs/extent.c      |  263 ++++++++++++++++++++++++++++++++++++++++++++++
 lib/ext2fs/extent_dbg.ct |    3 +
 3 files changed, 268 insertions(+), 0 deletions(-)
lib/ext2fs/ext2fs.h +2 -0
index 30ca906..c6ac317 100644
@@ -814,6 +814,8 @@ extern errcode_t ext2fs_extent_replace(ext2_extent_handle_t handle, int flags,
 				       struct ext2fs_extent *extent);
 extern errcode_t ext2fs_extent_insert(ext2_extent_handle_t handle, int flags,
 				      struct ext2fs_extent *extent);
+extern errcode_t ext2fs_extent_set_bmap(ext2_extent_handle_t handle,
+                                 blk64_t logical, blk64_t physical);
 extern errcode_t ext2fs_extent_delete(ext2_extent_handle_t handle, int flags);
 extern errcode_t ext2fs_extent_get_info(ext2_extent_handle_t handle,
 					struct ext2_extent_info *info);
lib/ext2fs/extent.c +263 -0

281 lines not on this page · raw message

lib/ext2fs/extent_dbg.ct +3 -0
index 788fdab..d0571f4 100644
@@ -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

#6 lore raw

Re: [PATCH 3/3] libext2fs: add ext2fs_extent_set_bmap

FYI, I've applied the following changes to your patch, so that ext2fs_set_bmap() will not cause any side effects to the current position of the extent handle. This is going to prove very useful when we wire up set_bmap() into various functions like ext2fs_block_iterate() which will be iterating over the extent tree.

(I also renamed ext2fs_node_split() to extent_node_split(), since (a) the name makes more sense, and (b) it's a static function, so it doesn't need the ext2fs_ prefix.)

- Ted

lib/ext2fs/extent.c +33 -7
index b084783..77362b6 100644
@@ -739,12 +739,13 @@ errcode_t ext2fs_extent_replace(ext2_extent_handle_t handle,
  *
  * handle will be left pointing at original record.
  */
-static errcode_t ext2fs_node_split(ext2_extent_handle_t handle, int flags)
+static errcode_t extent_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;
+	blk64_t				goal_blk = 0;
 	int				orig_height;
 	char				*block_buf = NULL;
 	struct ext2fs_extent		extent;

@@ -790,7 +791,9 @@ 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;
-		retval = ext2fs_node_split(handle, 0);
+		goal_blk = extent.e_pblk;
+
+		retval = extent_node_split(handle, 0);
 		if (retval)
 			goto done;
 

@@ -820,7 +823,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;

@@ -834,8 +836,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;
 

@@ -957,7 +968,7 @@ errcode_t ext2fs_extent_insert(ext2_extent_handle_t handle, int flags,
 			return EXT2_ET_CANT_INSERT_EXTENT;
 		} else {
 			dbg_printf("node full - splitting\n");
-			retval = ext2fs_node_split(handle, 0);
+			retval = extent_node_split(handle, 0);
 			if (retval)
 				goto errout;
 			path = handle->path + handle->level;

@@ -1027,15 +1038,26 @@ errcode_t ext2fs_extent_set_bmap(ext2_extent_handle_t handle,
 {
 	int			retval = 0;
 	int			mapped = 1; /* logical is mapped? */
+	int			orig_height;
+	blk64_t			orig_lblk;
 	struct extent_path	*path;
 	struct ext2fs_extent	extent;
 	struct ext2fs_extent	newextent;
+	struct ext2_extent_info	info;
 
 	EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE);
 
 	if (!(handle->fs->flags & EXT2_FLAG_RW))
 		return EXT2_ET_RO_FILSYS;
 
+	/* save our original location in the extent tree */
+	if (!(retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent)))
+		return retval;
+	if (!(retval = ext2fs_extent_get_info(handle, &info)))
+		return retval;
+	orig_height = info.max_depth - info.curr_level;
+	orig_lblk = extent.e_lblk;
+
 	/* go to the logical spot we want to (re/un)map */
 	retval = ext2fs_extent_goto(handle, logical);
 	if (retval) {

@@ -1166,6 +1188,10 @@ errcode_t ext2fs_extent_set_bmap(ext2_extent_handle_t handle,
 	}
 
 done:
+	/* get handle back to its position */
+	if (orig_height > handle->max_depth)
+		orig_height = handle->max_depth; /* In case we shortened the tree */
+	extent_goto(handle, orig_height, orig_lblk);
 	return retval;
 }
 

@@ -1453,7 +1479,7 @@ void do_split_node(int argc, char *argv[])
 		return;
 	}
 
-	retval = ext2fs_node_split(current_handle, flags);
+	retval = extent_node_split(current_handle, flags);
 	if (retval) {
 		com_err(cmd, retval, 0);
 		return;