[PATCH 1/5] Fix tst_extents build

[PATCH 1/5] Fix tst_extents build

[Eric Sandeen]

tst_extents needs libdl & libuuid to build, for me

Signed-off-by: Eric Sandeen <sandeen@redhat.com>
---
 lib/ext2fs/Makefile.in |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/lib/ext2fs/Makefile.in b/lib/ext2fs/Makefile.in
index 4f49575..1ed3b07 100644
--- a/lib/ext2fs/Makefile.in
+++ b/lib/ext2fs/Makefile.in
@@ -312,7 +312,7 @@ tst_extents: $(srcdir)/extent.c extent_dbg.c $(DEBUG_OBJS) $(LIBSS) $(LIBE2P) $(
 	@$(CC) -o tst_extents $(srcdir)/extent.c extent_dbg.c \
 		$(ALL_CFLAGS) -DDEBUG $(DEBUG_OBJS) $(LIBSS) $(LIBE2P) \
 		$(LIBUUID) $(STATIC_LIBEXT2FS) $(LIBBLKID) $(LIBCOM_ERR) \
-		-I $(top_srcdir)/debugfs
+		-I $(top_srcdir)/debugfs -ldl -luuid
 
 tst_csum: tst_csum.c csum.c $(STATIC_LIBEXT2FS)
 	@echo "	LD $@"
-- 
1.5.4.1

Re: [PATCH 1/5] Fix tst_extents build

[Theodore Tso]

On Mon, Apr 07, 2008 at 10:00:56PM -0500, Eric Sandeen wrote:
> tst_extents needs libdl & libuuid to build, for me
> 
> @@ -312,7 +312,7 @@ tst_extents: $(srcdir)/extent.c extent_dbg.c $(DEBUG_OBJS) $(LIBSS) $(LIBE2P) $(
>  	@$(CC) -o tst_extents $(srcdir)/extent.c extent_dbg.c \
>  		$(ALL_CFLAGS) -DDEBUG $(DEBUG_OBJS) $(LIBSS) $(LIBE2P) \
>  		$(LIBUUID) $(STATIC_LIBEXT2FS) $(LIBBLKID) $(LIBCOM_ERR) \
> -		-I $(top_srcdir)/debugfs
> +		-I $(top_srcdir)/debugfs -ldl -luuid

Thanks for pointing this out; my development environment I always
build with elf shared libraries enabled, so I didn't notice this
problem.

$(LIBUUID) was already included, but in the wrong place.  So it was
just a matter of reordering the library link order.

This is the fixed I ultimately checked in.

						- Ted

commit daf7a6e5d1621d4d84feabedb286e23dc5ad7dbb
Author: Theodore Ts'o <tytso@mit.edu>
Date:   Thu Apr 17 16:54:24 2008 -0400

    Fix tst_extents build when building w/o dynamic libraries
    
    $(LIBSS) should automatically include @DLOPEN_LIB@ so the right thing
    happens for programs that need to use the ss library.
    
    Reorder the library link order for tst_extents since the blkid library
    uses libuuid functions.
    
    Thanks to Eric Sandeen for pointing this problem out!
    
    Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>

diff --git a/MCONFIG.in b/MCONFIG.in
index 8cd2ccf..80ddbd8 100644
--- a/MCONFIG.in
+++ b/MCONFIG.in
@@ -72,7 +72,7 @@ DEVMAPPER_LIBS = @DEVMAPPER_LIBS@
 STATIC_DEVMAPPER_LIBS = @STATIC_DEVMAPPER_LIBS@
 
 LIB = $(top_builddir)/lib
-LIBSS = $(LIB)/libss@LIB_EXT@
+LIBSS = $(LIB)/libss@LIB_EXT@ @DLOPEN_LIB@
 LIBCOM_ERR = $(LIB)/libcom_err@LIB_EXT@
 LIBE2P = $(LIB)/libe2p@LIB_EXT@
 LIBEXT2FS = $(LIB)/libext2fs@LIB_EXT@
@@ -82,7 +82,7 @@ LIBINTL = @LIBINTL@
 DEPLIBUUID = $(LIB)/libuuid@LIB_EXT@
 DEPLIBBLKID = $(LIB)/libblkid@LIB_EXT@
 
-STATIC_LIBSS = $(LIB)/libss@STATIC_LIB_EXT@
+STATIC_LIBSS = $(LIB)/libss@STATIC_LIB_EXT@ @DLOPEN_LIB@
 STATIC_LIBCOM_ERR = $(LIB)/libcom_err@STATIC_LIB_EXT@
 STATIC_LIBE2P = $(LIB)/libe2p@STATIC_LIB_EXT@
 STATIC_LIBEXT2FS = $(LIB)/libext2fs@STATIC_LIB_EXT@
@@ -91,7 +91,7 @@ STATIC_LIBBLKID = $(LIB)/libblkid@STATIC_LIB_EXT@ $(STATIC_DEVMAPPER_LIBS)
 DEPSTATIC_LIBUUID = $(LIB)/libuuid@STATIC_LIB_EXT@
 DEPSTATIC_LIBBLKID = $(LIB)/libblkid@STATIC_LIB_EXT@
 
-PROFILED_LIBSS = $(LIB)/libss@PROFILED_LIB_EXT@
+PROFILED_LIBSS = $(LIB)/libss@PROFILED_LIB_EXT@ @DLOPEN_LIB@
 PROFILED_LIBCOM_ERR = $(LIB)/libcom_err@PROFILED_LIB_EXT@
 PROFILED_LIBE2P = $(LIB)/libe2p@PROFILED_LIB_EXT@
 PROFILED_LIBEXT2FS = $(LIB)/libext2fs@PROFILED_LIB_EXT@
diff --git a/debugfs/Makefile.in b/debugfs/Makefile.in
index bdba326..cb3efcb 100644
--- a/debugfs/Makefile.in
+++ b/debugfs/Makefile.in
@@ -8,7 +8,6 @@ VPATH = @srcdir@
 top_builddir = ..
 my_dir = debugfs
 INSTALL = @INSTALL@
-DLOPEN_LIB = @DLOPEN_LIB@
 
 @MCONFIG@
 
@@ -26,7 +25,7 @@ SRCS= debug_cmds.c $(srcdir)/debugfs.c $(srcdir)/util.c $(srcdir)/ls.c \
 	$(srcdir)/htree.c $(srcdir)/unused.c
 
 LIBS= $(LIBEXT2FS) $(LIBE2P) $(LIBSS) $(LIBCOM_ERR) $(LIBBLKID) \
-	$(LIBUUID) $(DLOPEN_LIB)
+	$(LIBUUID)
 DEPLIBS= $(LIBEXT2FS) $(LIBE2P) $(LIBSS) $(LIBCOM_ERR) $(DEPLIBBLKID) $(DEPLIBUUID)
 
 .c.o:
diff --git a/lib/ext2fs/Makefile.in b/lib/ext2fs/Makefile.in
index 677e2d6..b5f67e6 100644
--- a/lib/ext2fs/Makefile.in
+++ b/lib/ext2fs/Makefile.in
@@ -305,7 +305,7 @@ tst_extents: $(srcdir)/extent.c extent_dbg.c $(DEBUG_OBJS) $(LIBSS) $(LIBE2P) $(
 	@echo "	LD $@"
 	@$(CC) -o tst_extents $(srcdir)/extent.c extent_dbg.c \
 		$(ALL_CFLAGS) -DDEBUG $(DEBUG_OBJS) $(LIBSS) $(LIBE2P) \
-		$(LIBUUID) $(STATIC_LIBEXT2FS) $(LIBBLKID) $(LIBCOM_ERR) \
+		$(STATIC_LIBEXT2FS) $(LIBBLKID) $(LIBUUID) $(LIBCOM_ERR) \
 		-I $(top_srcdir)/debugfs
 
 tst_csum: tst_csum.c csum.c $(STATIC_LIBEXT2FS)

[PATCH 2/5] print a bit more info for the tst_extents info command

[Eric Sandeen]

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

diff --git a/lib/ext2fs/extent.c b/lib/ext2fs/extent.c
index e7733c5..76f6f65 100644
--- a/lib/ext2fs/extent.c
+++ b/lib/ext2fs/extent.c
@@ -1087,6 +1087,7 @@ void do_print_all(int argc, char **argv)
 
 void do_info(int argc, char **argv)
 {
+	struct ext2fs_extent	extent;
 	struct ext2_extent_info	info;
 	errcode_t		retval;
 
@@ -1104,6 +1105,15 @@ void do_info(int argc, char **argv)
 		return;
 	}
 
+	retval = ext2fs_extent_get(current_handle,
+				   EXT2_EXTENT_CURRENT, &extent);
+	if (retval) {
+		com_err(argv[0], retval, 0);
+		return;
+	}
+
+	dbg_print_extent(0, &extent);
+
 	printf("Current handle location: %d/%d (max: %d, bytes %d), level %d/%d\n",
 	       info.curr_entry, info.num_entries, info.max_entries,
 	       info.bytes_avail, info.curr_level, info.max_depth);
-- 
1.5.4.1

Re: [PATCH 2/5] print a bit more info for the tst_extents info command

[Theodore Tso]

On Mon, Apr 07, 2008 at 10:00:57PM -0500, Eric Sandeen wrote:
> 
> Signed-off-by: Eric Sandeen <sandeen@redhat.com>

Thanks, applied.

					- Ted

[PATCH 3/5] fix ext2fs_extent_insert when at last extent in node

[Eric Sandeen]

ext2fs_extent_insert() only did a memmove if path->left
was > 0, but if we are at the last extent in the node,
path->left == 0, and this node must be moved before the
current extent is replaced with the newly inserted node.

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

diff --git a/lib/ext2fs/extent.c b/lib/ext2fs/extent.c
index 76f6f65..9f19e7b 100644
--- a/lib/ext2fs/extent.c
+++ b/lib/ext2fs/extent.c
@@ -689,7 +689,7 @@ errcode_t ext2fs_extent_insert(ext2_extent_handle_t handle, int flags,
 
 	path->curr = ix;
 
-	if (path->left > 0)
+	if (path->left >= 0)
 		memmove(ix + 1, ix,
 			(path->left+1) * sizeof(struct ext3_extent_idx));
 	path->left++;
-- 
1.5.4.1

Re: [PATCH 3/5] fix ext2fs_extent_insert when at last extent in node

[Theodore Tso]

On Mon, Apr 07, 2008 at 10:00:58PM -0500, Eric Sandeen wrote:
> ext2fs_extent_insert() only did a memmove if path->left
> was > 0, but if we are at the last extent in the node,
> path->left == 0, and this node must be moved before the
> current extent is replaced with the newly inserted node.

Thanks, applied.

					- Ted

[PATCH 4/5] make extent_goto() deterministic when logical block not found

[Eric Sandeen]

Make sure that extent_goto() leaves us at the last extent
prior to the requested logical block, if the logical block
requested lands in a hole.

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

diff --git a/lib/ext2fs/extent.c b/lib/ext2fs/extent.c
index 9f19e7b..e7b7e85 100644
--- a/lib/ext2fs/extent.c
+++ b/lib/ext2fs/extent.c
@@ -553,6 +553,12 @@ errcode_t ext2fs_extent_free_path(ext2_extent_path_t path)
 }
 #endif
 
+/*
+ * Go to the node at leaf_level which contains logical block blk.
+ *
+ * If "blk" has no mapping (hole) then handle is left at last
+ * extent before blk.
+ */
 static errcode_t extent_goto(ext2_extent_handle_t handle,
 			     int leaf_level, blk64_t blk)
 {
@@ -566,11 +572,16 @@ static errcode_t extent_goto(ext2_extent_handle_t handle,
 	dbg_print_extent("root", &extent);
 	while (1) {
 		if (handle->level - leaf_level == handle->max_depth) {
+			/* block is in this &extent */
 			if ((blk >= extent.e_lblk) &&
 			    (blk < extent.e_lblk + extent.e_len))
 				return 0;
-			if (blk < extent.e_lblk)
+			if (blk < extent.e_lblk) {
+				retval = ext2fs_extent_get(handle,
+							   EXT2_EXTENT_PREV_SIB,
+							   &extent);
 				return EXT2_ET_EXTENT_NOT_FOUND;
+			}
 			retval = ext2fs_extent_get(handle,
 						   EXT2_EXTENT_NEXT_SIB,
 						   &extent);
-- 
1.5.4.1

Re: [PATCH 4/5] make extent_goto() deterministic when logical block not found

[Theodore Tso]

On Mon, Apr 07, 2008 at 10:00:59PM -0500, Eric Sandeen wrote:
> Make sure that extent_goto() leaves us at the last extent
> prior to the requested logical block, if the logical block
> requested lands in a hole.

Thanks, applied.  You do realize this won't necessarily do the right
thing if the sparse file doesn't have a block mapped at logical block
#0, and you then do an extent_goto() block 0, right?  Also, if
extent_get(EXT2_EXTENT_PREV_SIB) fails for various reasons, it still
could be non-deterministic.  Code that depends on this may want to do
some sanity checking.

Also, it might be prudent to check the return value here:

> +				retval = ext2fs_extent_get(handle,
> +							   EXT2_EXTENT_PREV_SIB,
> +							   &extent);
>  				return EXT2_ET_EXTENT_NOT_FOUND;

and return either the error returned by ext2fs_extent_get, or possibly
invent a new error code, say EXT2_ET_EXTENT_GOTO_BACKUP_FAILED and
return that if retval is non-zero.

I've left this as-is for now but there might be a potential robustness
problem hiding here.

						- Ted

[PATCH 5/5] Preliminary ext2fs_extent_set_bmap

[Eric Sandeen]

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

Does not yet handle cases where the current extent must
be split (unmapping or remapping in the middle of an
extent) or where the parent index node is full (would
require splitting the parent).

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

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

diff --git a/lib/ext2fs/extent.c b/lib/ext2fs/extent.c
index e7b7e85..d907e66 100644
--- a/lib/ext2fs/extent.c
+++ b/lib/ext2fs/extent.c
@@ -628,6 +628,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)
@@ -724,6 +782,139 @@ errout:
 	return retval;
 }
 
+/*
+ * TODO:
+ * Handle remapping block in middle of extent (requires splitting node)
+ * Handle case where parent is full (requires splitting parent)
+ */
+/* NB: if unmapping or mapping an unmapped block, does not change i_count */
+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;
+
+	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 {
+			printf("fixing parents\n");
+			retval = ext2fs_extent_fix_parents(handle);
+			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 {
+		dbg_printf("(re/un)mapping in middle of extent\n");
+		/* need to split this extent; later */
+		retval = EXT2_ET_OP_NOT_SUPPORTED;
+		goto done;
+	}
+
+done:
+	return retval;
+}
+
 errcode_t ext2fs_extent_delete(ext2_extent_handle_t handle, 
 			       int flags EXT2FS_ATTR((unused)))
 {
@@ -1009,7 +1200,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;
 	}
 
@@ -1036,6 +1227,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 41299fa..bfd959f 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_set_bmap, "Set block mapping",
+	set_bmap;
+
 request do_replace_node, "Insert node",
 	replace_node, replace;
 
-- 
1.5.4.1