e2dis: a Jigdo-like tool for Ext2+ FS

e2dis: a Jigdo-like tool for Ext2+ FS

[Ivan Shmakov]

	A couple of weeks ago I've started working on a tool
	(tentantively named “Ext2 disassembler”) to walk through an
	Ext2+ filesystem (or an image of) and produce the mapping of
	files' (inodes') relative block numbers to the image's (or
	“physical”) block numbers.

	The version-that-works (apparently) is almost done, pending
	upload to a publicly-accessible Git repository.

	However, there's a considerable amount of work to be done so
	that the tool will become really usable.  Therefore, I'd
	appreciate any help with it.

	TIA.

    Why I'm interested in that?

	Recently, there was a discussion in debian-devel@ on whether the
	Debian project should provide images for easy deployment within
	“virtual” environments (such as KVM, Xen, etc.)

	Such images (which, I assume, will use a filesystem supported by
	e2fsprogs) are going to be quite large: hundreds MiB to a few
	GiB's (depending on the intended usage) per architecture per
	version.

	Earlier, to reduce the burden of mirroring of the ISO 9660 (CD,
	DVD, etc.) images, the Jigdo (for Jigsaw Download) tool was
	introduced.  The tool uses SHA-1 to associate pieces of a
	filesystem image with the contents of the files of a specified
	set.  As the result, the tool produces the association map,
	which has the parts of the image for which no matching files are
	known embedded.  (A helper file, which contains the URI's the
	files may be downloaded from, is also generated.)

	Given such an association map, and the files, the tool is
	capable of restoring the image.

	The tool is filesystem-agnostic.  Unfortunately, it relies on
	the fact that the files on the ISO 9660 filesystem are never
	fragmented.  Which doesn't hold for Ext2+.

	However, given the knowledge of the filesystem, it's possible to
	solve the task of describing the parts of a given image as being
	parts of the files specified.

    Done

	The tool iterates over the inodes, and records the
	logical-to-physical blocks correspondence.  All the “chunks”
	belonging to the same inode are marked as such.

	The mapping is written to a SQLite database.

    To do

	Message digests are to be computed and recorded just as well.

	Non-payload blocks are to be annotated as well.

	A tool to reassemble the image.

	Command line interface.  (Preferably compliant to the GNU Coding
	Standards.)

-- 
FSF associate member #7257

--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: e2dis: a Jigdo-like tool for Ext2+ FS

[Ivan Shmakov]

>>>>> Ivan Shmakov <ivan@gray.siamics.net> writes:

[…]

 > The version-that-works (apparently) is almost done, pending upload to
 > a publicly-accessible Git repository.

	Done.

http://gray.siamics.net/~ivan/archives/git/gitweb.cgi/?p=e2dis.git
http://waterlily.siamics.net/~ivan/archives/git/gitweb.cgi/?p=e2dis.git

http://gray.siamics.net/~ivan/archives/git/e2dis.git/
http://waterlily.siamics.net/~ivan/archives/git/e2dis.git/

[…]

-- 
FSF associate member #7257

--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: e2dis: a Jigdo-like tool for Ext2+ FS

[Lukas Czerner]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 2961 bytes --]

On Sat, 13 Aug 2011, Ivan Shmakov wrote:

> 	A couple of weeks ago I've started working on a tool
> 	(tentantively named “Ext2 disassembler”) to walk through an
> 	Ext2+ filesystem (or an image of) and produce the mapping of
> 	files' (inodes') relative block numbers to the image's (or
> 	“physical”) block numbers.

Hi Ivan,

I have not seen your code, but that sounds like something that debugfs
(part of e2fsprogs) is already doing very well (and a lot more). This is
exactly the "extN disassembler" you're talking about and with a little
bit of scripting around it you should be able dig any information you
desire from the file system so I do not think that new application is
needed. But I might be wrong, just take a look at it.

Thanks!
-Lukas

> 
> 	The version-that-works (apparently) is almost done, pending
> 	upload to a publicly-accessible Git repository.
> 
> 	However, there's a considerable amount of work to be done so
> 	that the tool will become really usable.  Therefore, I'd
> 	appreciate any help with it.
> 
> 	TIA.
> 
>     Why I'm interested in that?
> 
> 	Recently, there was a discussion in debian-devel@ on whether the
> 	Debian project should provide images for easy deployment within
> 	“virtual” environments (such as KVM, Xen, etc.)
> 
> 	Such images (which, I assume, will use a filesystem supported by
> 	e2fsprogs) are going to be quite large: hundreds MiB to a few
> 	GiB's (depending on the intended usage) per architecture per
> 	version.
> 
> 	Earlier, to reduce the burden of mirroring of the ISO 9660 (CD,
> 	DVD, etc.) images, the Jigdo (for Jigsaw Download) tool was
> 	introduced.  The tool uses SHA-1 to associate pieces of a
> 	filesystem image with the contents of the files of a specified
> 	set.  As the result, the tool produces the association map,
> 	which has the parts of the image for which no matching files are
> 	known embedded.  (A helper file, which contains the URI's the
> 	files may be downloaded from, is also generated.)
> 
> 	Given such an association map, and the files, the tool is
> 	capable of restoring the image.
> 
> 	The tool is filesystem-agnostic.  Unfortunately, it relies on
> 	the fact that the files on the ISO 9660 filesystem are never
> 	fragmented.  Which doesn't hold for Ext2+.
> 
> 	However, given the knowledge of the filesystem, it's possible to
> 	solve the task of describing the parts of a given image as being
> 	parts of the files specified.
> 
>     Done
> 
> 	The tool iterates over the inodes, and records the
> 	logical-to-physical blocks correspondence.  All the “chunks”
> 	belonging to the same inode are marked as such.
> 
> 	The mapping is written to a SQLite database.
> 
>     To do
> 
> 	Message digests are to be computed and recorded just as well.
> 
> 	Non-payload blocks are to be annotated as well.
> 
> 	A tool to reassemble the image.
> 
> 	Command line interface.  (Preferably compliant to the GNU Coding
> 	Standards.)
> 
> 

-- 

Re: e2dis: a Jigdo-like tool for Ext2+ FS

[Ivan Shmakov]

>>>>> Lukas Czerner <lczerner@redhat.com> writes:
>>>>> On Sat, 13 Aug 2011, Ivan Shmakov wrote:

 >> A couple of weeks ago I've started working on a tool (tentantively
 >> named “Ext2 disassembler”) to walk through an Ext2+ filesystem (or
 >> an image of) and produce the mapping of files' (inodes') relative
 >> block numbers to the image's (or “physical”) block numbers.

 > I have not seen your code, but that sounds like something that
 > debugfs (part of e2fsprogs) is already doing very well (and a lot
 > more).  This is exactly the "extN disassembler" you're talking about

	Not quite.  The meaning of “disassembler” here is that the image
	is torn in parts, which could later be assembled together to
	form exactly the same image (by an “image assembler” tool.)

	It's not implied that e2dis will ever produce some sort of
	human-readable output (as its primary result.)  For that,
	debugfs(8) should indeed suffice.

 > and with a little bit of scripting around it you should be able dig
 > any information you desire from the file system so I do not think
 > that new application is needed.  But I might be wrong, just take a
 > look at it.

	Indeed, my first try was to use debugfs(8).  However, there're
	several issues with it:

	• I see no way to obtain the list of used inodes in debugfs(8)
	  (as of 1.41.12 debian 2); therefore, I have had to resort to
	  trying the ‘stat’ command on every possible inode number;

	• also, the (binary) filesystem data is serialized into ASCII by
	  debugfs(8) and is parsed afterwards by the invoking tool,
	  which is computationally-inefficient; (especially if applied
	  to a filesystem with size in the order of several GiB's, and
	  the number of used inodes in the order of tens of thousands,
	  or more);

	• moreover, I see no claims that the output of the debugfs(8)
	  ‘stat’ command won't ever change (neither I see the formal
	  description of the aforementioned output — its source is the
	  only form of specification I could rely); my guess is that the
	  C API, being documented, is going to be much more stable;

	That being said, the most of the code I've written so far is
	concerned /not/ with the filesystems per se (i. e., libext2fs
	calls), but with data recording: representing the data in a
	compact way, interfacing SQLite, etc.  (The SHA-1 computation
	and GNU-style CLI will require some coding as well, thus making
	the Ext2+ FS-specific parts even smaller when compared to the
	overall code size.)

[…]

-- 
FSF associate member #7257

--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: e2dis: a Jigdo-like tool for Ext2+ FS

[Lukas Czerner]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 3425 bytes --]

On Mon, 15 Aug 2011, Ivan Shmakov wrote:

> >>>>> Lukas Czerner <lczerner@redhat.com> writes:
> >>>>> On Sat, 13 Aug 2011, Ivan Shmakov wrote:
> 
>  >> A couple of weeks ago I've started working on a tool (tentantively
>  >> named “Ext2 disassembler”) to walk through an Ext2+ filesystem (or
>  >> an image of) and produce the mapping of files' (inodes') relative
>  >> block numbers to the image's (or “physical”) block numbers.
> 
>  > I have not seen your code, but that sounds like something that
>  > debugfs (part of e2fsprogs) is already doing very well (and a lot
>  > more).  This is exactly the "extN disassembler" you're talking about
> 
> 	Not quite.  The meaning of “disassembler” here is that the image
> 	is torn in parts, which could later be assembled together to
> 	form exactly the same image (by an “image assembler” tool.)

Ok then, I have misunderstood your intentions. I thought that you need
to get logical to physical mappings of inodes.

> 
> 	It's not implied that e2dis will ever produce some sort of
> 	human-readable output (as its primary result.)  For that,
> 	debugfs(8) should indeed suffice.

Ok, I was just implying that you can use debugfs as a tool to figure out
what to read e.g. what physical blocks belongs to what inode. If you
have already tried debugfs and it did not suit you needs I am ok with
that.

> 
>  > and with a little bit of scripting around it you should be able dig
>  > any information you desire from the file system so I do not think
>  > that new application is needed.  But I might be wrong, just take a
>  > look at it.
> 
> 	Indeed, my first try was to use debugfs(8).  However, there're
> 	several issues with it:
> 
> 	• I see no way to obtain the list of used inodes in debugfs(8)
> 	  (as of 1.41.12 debian 2); therefore, I have had to resort to
> 	  trying the ‘stat’ command on every possible inode number;

I am not sure if there is a way to list used inodes in debugfs but it
should be very easy to implement.

> 
> 	• also, the (binary) filesystem data is serialized into ASCII by
> 	  debugfs(8) and is parsed afterwards by the invoking tool,
> 	  which is computationally-inefficient; (especially if applied
> 	  to a filesystem with size in the order of several GiB's, and
> 	  the number of used inodes in the order of tens of thousands,
> 	  or more);

Oh, I was not trying to say that you should use debugfs to dig data out,
but rather to get hint of where data lies in the image.

> 
> 	• moreover, I see no claims that the output of the debugfs(8)
> 	  ‘stat’ command won't ever change (neither I see the formal
> 	  description of the aforementioned output — its source is the
> 	  only form of specification I could rely); my guess is that the
> 	  C API, being documented, is going to be much more stable;

Well, you can probably say that about every tool, but that is not good
enough reason to duplicate the code for everything. Although I am not
saying that you're doing so.

Thanks!
-Lukas

> 
> 	That being said, the most of the code I've written so far is
> 	concerned /not/ with the filesystems per se (i. e., libext2fs
> 	calls), but with data recording: representing the data in a
> 	compact way, interfacing SQLite, etc.  (The SHA-1 computation
> 	and GNU-style CLI will require some coding as well, thus making
> 	the Ext2+ FS-specific parts even smaller when compared to the
> 	overall code size.)

debugfs: list inode numbers?

[Ivan Shmakov]

>>>>> Lukas Czerner <lczerner@redhat.com> writes:
>>>>> On Mon, 15 Aug 2011, Ivan Shmakov wrote:
>>>>> Lukas Czerner <lczerner@redhat.com> writes:

[…]

 >>> and with a little bit of scripting around it you should be able dig
 >>> any information you desire from the file system so I do not think
 >>> that new application is needed.  But I might be wrong, just take a
 >>> look at it.

 >> Indeed, my first try was to use debugfs(8).  However, there're
 >> several issues with it:

 >> • I see no way to obtain the list of used inodes in debugfs(8)
 >> (as of 1.41.12 debian 2); therefore, I have had to resort to
 >> trying the ‘stat’ command on every possible inode number;

 > I am not sure if there is a way to list used inodes in debugfs but it
 > should be very easy to implement.

	Something along the lines of the following, perhaps (assuming
	ISO C99):

   {
     int only_with_blocks_p
       = 0;
     ext2_inode_scan scan;

     {
       errcode_t r
         = ext2fs_open_inode_scan (e2, 0, &scan);
       assert (r == 0);
     }

     FILE *out
       = stdout;
     errcode_t r;
     ext2_ino_t ino;
     struct ext2_inode inode;
     int column;

     /* FIXME: handle EXT2_ET_BAD_BLOCK_IN_INODE_TABLE, too */
     while (((r = ext2fs_get_next_inode (scan, &ino, &inode)) == 0)
            && ino != 0) {
       if (! only_with_blocks_p
           || ext2fs_inode_has_valid_blocks (inode)) {
         /* skip over the inodes lacking valid blocks, if requested */
	 continue;
       }

       int n
         = fprintf (out, " <%d>");
       assert (n >= 0);
       column += n;
       /* NB: assuming that a typical inode number will be less than 9
              decimal digits long, and that the terminal has 80 columns
              */
       if (column >= 80 - 12) {
         fputc ('\n', out);
       }
     }
     /* FIXME: handle EXT2_ET_BAD_BLOCK_IN_INODE_TABLE, too */
     assert (r == 0);
   }

	Or should I develop a proper patch?

[…]

-- 
FSF associate member #7257

--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: e2dis: a Jigdo-like tool for Ext2+ FS

[Ivan Shmakov]

>>>>> Lukas Czerner <lczerner@redhat.com> writes:
>>>>> On Mon, 15 Aug 2011, Ivan Shmakov wrote:

	BTW, the primary Git repository for the project is now located
	at Gitorious:

git://gitorious.org/e2dis/e2dis-devel.git
http://gitorious.org/e2dis/e2dis-devel.git
https://gitorious.org/e2dis/e2dis-devel

	The most notable improvement that I made recently is that the
	payload message digests are now recorded.  (The support for the
	whole-image and metadata message digests is not yet committed.)

[…]

 >> • moreover, I see no claims that the output of the debugfs(8) ‘stat’
 >> command won't ever change (neither I see the formal description of
 >> the aforementioned output — its source is the only form of
 >> specification I could rely); my guess is that the C API, being
 >> documented, is going to be much more stable;

 > Well, you can probably say that about every tool,

	Why, there're plenty of tools that support either some sort of a
	standardized output, or output that's user-defined (based on
	some standardized items.)  E. g., the output of ls(1) and
	date(1) is defined by POSIX (IEEE Std 1003.1-2008), etc.

 > but that is not good enough reason to duplicate the code for
 > everything.  Although I am not saying that you're doing so.

	I believe that there's very little, if any, code duplication
	between e2dis and debugfs.

[…]

-- 
FSF associate member #7257	Coming soon: Software Freedom Day
http://mail.sf-day.org/lists/listinfo/ planning-ru (ru), sfd-discuss (en)

--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

ext2fs_test_block_bitmap (): Unknown code ext2 47 #0, etc.

[Ivan Shmakov]

>>>>> Ivan Shmakov <ivan@gray.siamics.net> writes:

[…]

 > (The support for the whole-image and metadata message digests is not
 > yet committed.)

	The code is now ready to be committed.  However, I'm getting the
	following message on stderr upon a call (only the first one?) to
	ext2fs_test_block_bitmap ():

--cut--
Unknown code ext2 47 #0 for block bitmap for /dev/stdin
--cut--

	Otherwise, e2dis seems to behave sanely.

	Also, do I understand it correctly that I need to call
	ext2fs_read_block_bitmap () before accessing the block_map
	member of the ext2_filsys structure?

[…]

-- 
FSF associate member #7257	Coming soon: Software Freedom Day
http://mail.sf-day.org/lists/listinfo/ planning-ru (ru), sfd-discuss (en)

--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: ext2fs_test_block_bitmap (): Unknown code ext2 47 #0, etc.

[Ted Ts'o]

On Thu, Aug 18, 2011 at 11:27:30PM +0700, Ivan Shmakov wrote:
> >>>>> Ivan Shmakov <ivan@gray.siamics.net> writes:
> 
> […]
> 
>  > (The support for the whole-image and metadata message digests is not
>  > yet committed.)
> 
> 	The code is now ready to be committed.  However, I'm getting the
> 	following message on stderr upon a call (only the first one?) to
> 	ext2fs_test_block_bitmap ():
> 
> --cut--
> Unknown code ext2 47 #0 for block bitmap for /dev/stdin
> --cut--

You're not getting a human-readable error message because you need to
add the following at the beginning of your program:

	add_error_table(&et_ext2_error_table);

(The error messages are printed by the libcom_err library, and are
defined in lib/ext2fs/ext2_err.et.in, processed to
lib/ext2fs/ext2_err.et, and then compiled to ext2_err.c and ext2_err.h
by the compile_et script in lib/et of e2fsprogs.)

The 47th error message in the ext2 error table, which would have been
printed if you had called add_error_table(), is:

	Illegal block number passed to ext2fs_test_block_bitmap

This means you've passed in a block number which is out-of-range for
the block bitmap.

> 	Also, do I understand it correctly that I need to call
> 	ext2fs_read_block_bitmap () before accessing the block_map
> 	member of the ext2_filsys structure?

Yes, or if you are going to need to read in both the block and inode
bitmaps, you can use ext2fs_read_bitmaps(), which will be more optimal
for reading in the block bitmaps.

							- Ted
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: ext2fs_test_block_bitmap (): Unknown code ext2 47 #0, etc.

[Ivan Shmakov]

>>>>> Ted Ts'o <tytso@mit.edu> writes:
>>>>> On Thu, Aug 18, 2011 at 11:27:30PM +0700, Ivan Shmakov wrote:

[…]

 >> However, I'm getting the following message on stderr upon a call
 >> (only the first one?) to ext2fs_test_block_bitmap ():

 >> --cut--
 >> Unknown code ext2 47 #0 for block bitmap for /dev/stdin
 >> --cut--

 > You're not getting a human-readable error message because you need to
 > add the following at the beginning of your program:

 > add_error_table(&et_ext2_error_table);

	Thanks for the suggestion!

[…]

 > The 47th error message in the ext2 error table, which would have been
 > printed if you had called add_error_table(), is:

 > Illegal block number passed to ext2fs_test_block_bitmap

 > This means you've passed in a block number which is out-of-range for
 > the block bitmap.

	Do I understand it correctly that the block #0 isn't covered by
	any bitmap?  (I guess it's reserved for bootloaders, etc.)

 >> Also, do I understand it correctly that I need to call
 >> ext2fs_read_block_bitmap () before accessing the block_map member of
 >> the ext2_filsys structure?

 > Yes, or if you are going to need to read in both the block and inode
 > bitmaps, you can use ext2fs_read_bitmaps(), which will be more
 > optimal for reading in the block bitmaps.

	ACK.  Thanks.

-- 
FSF associate member #7257	Coming soon: Software Freedom Day
http://mail.sf-day.org/lists/listinfo/ planning-ru (ru), sfd-discuss (en)

--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html