[RFC][PATCH 0/1] ext4: Undelete Feature for Ext4

[RFC][PATCH 0/1] ext4: Undelete Feature for Ext4

[Lubos Uhliarik]

Hi all,

I'm sending you a patch (see the 1/1 patch) which should make
undelete process for deleted files on ext4 easier. I do this 
patch as a part of my Barchelor's thesis with support of Red Hat
company. 

The main changes in patch are following:

a) commented out zeroing ex->ee_len, ee->start_hi and ee->start_lo,
because these entries are essential for undelete process

b) only in inode structure, storing original value of eh->depth and
eh->entries. These values are stored to unused entry eh_generation in
struct ext4_extent_header after all extents have been definitely
removed. eh->entries is 16 bits value and is stored in first half of 32
bits of eh->generation. eh->depth is also 16 bits value and is stored in
second half of eh->generation. For storing these valued, I wrote macros
to ext4_extents.h. It's should NOT cause problems to store values in 
eh->generation, because eh->generation is used only, when file is NOT
deleted. After delete process, eh->generation can have any value.

c) if deletion process removes extents from block, which is not inode
(eh->depth > 0), then I'm storing only eh->entries original value to
eh->generation, because eh->depth will stay untouched. 

d) if delete process removes all extent_idx structures from block, which
is not in inode (eh->depth > 0), then I'm storing also only eh->entries
original value. But in this case, I need to store original eh->entries
value for each level separately, because delete process is changing
eh->entries value during walking through extent tree. This problem is
solved by allocating array, where I will store original values


This patch shouldn't break ext4, I tested it with xfs_tests and tests 
were successfull.

I also successfully created undelete application, based on e2fslibs,
which demonstrates undelete process. (link:
https://github.com/uhliarik/ext4-undelete )


Thanks! 
Lubos Uhliarik

Re: [RFC][PATCH 0/1] ext4: Undelete Feature for Ext4

[tytso]

On Tue, Mar 18, 2014 at 04:09:30PM +0100, Lubos Uhliarik wrote:
> The main changes in patch are following:
> 
> a) commented out zeroing ex->ee_len, ee->start_hi and ee->start_lo,
> because these entries are essential for undelete process

The reason why we have to zero out ex->ee_len, etc. is because the
truncate operation can sometimes span multiple journal transactions.
So as a result, we need to keep the file system consistent if we are
interrupted (i.e., via a power fail event) while in the middle of a
truncate operation.

It's a rare case, but it can happen if the journal is almost full at
the time when the truncate eoperation has started, such that there is
no room for to exntend the transaction handle, and so we are forced to
start a new transaction (and possibly wait for a journal checkpoint
operation).

In theory, it would be possible to figure out in advance whether or
not we could fit the truncate in a single transaction, but it would
require making the truncate operation be a two-pass operation --- once
to determine how many blocks needs to be modified, and once to
actually do the truncate operation.

> This patch shouldn't break ext4, I tested it with xfs_tests and tests 
> were successfull.

I'm guessing you didn't do power fail testing --- and this is very
important when messing with the design truncate/unlink code path.

Regards,

						- Ted

Re: [RFC][PATCH 0/1] ext4: Undelete Feature for Ext4

[Lukáš Czerner]

On Tue, 18 Mar 2014, tytso@mit.edu wrote:

> Date: Tue, 18 Mar 2014 13:14:26 -0400
> From: tytso@mit.edu
> To: Lubos Uhliarik <uhliarik@seznam.cz>
> Cc: linux-ext4@vger.kernel.org, lczerner@redhat.com, vojnar@fit.vutbr.cz
> Subject: Re: [RFC][PATCH 0/1] ext4: Undelete Feature for Ext4
> 
> On Tue, Mar 18, 2014 at 04:09:30PM +0100, Lubos Uhliarik wrote:
> > The main changes in patch are following:
> > 
> > a) commented out zeroing ex->ee_len, ee->start_hi and ee->start_lo,
> > because these entries are essential for undelete process
> 
> The reason why we have to zero out ex->ee_len, etc. is because the
> truncate operation can sometimes span multiple journal transactions.
> So as a result, we need to keep the file system consistent if we are
> interrupted (i.e., via a power fail event) while in the middle of a
> truncate operation.
> 
> It's a rare case, but it can happen if the journal is almost full at
> the time when the truncate eoperation has started, such that there is
> no room for to exntend the transaction handle, and so we are forced to
> start a new transaction (and possibly wait for a journal checkpoint
> operation).
> 
> In theory, it would be possible to figure out in advance whether or
> not we could fit the truncate in a single transaction, but it would
> require making the truncate operation be a two-pass operation --- once
> to determine how many blocks needs to be modified, and once to
> actually do the truncate operation.

Hi Lubos,

that's what we've been discussing including the power failure
testing. Have you managed to make a power failure test for this ? I
kind of forgot to ask you about that today.

Also, if I recall correctly you mentioned that we should be ok with
the respect of power failure in the middle of truncate, but I do not
recall the details, can you try to look into that again ?

Thanks!
-Lukas

> 
> > This patch shouldn't break ext4, I tested it with xfs_tests and tests 
> > were successfull.
> 
> I'm guessing you didn't do power fail testing --- and this is very
> important when messing with the design truncate/unlink code path.
> 
> Regards,
> 
> 						- Ted
> 

Re: [RFC][PATCH 0/1] ext4: Undelete Feature for Ext4

[Lubos Uhliarik]

Hi Tytso,

I tried to do some power failure tests, but I was unable to simulate an
error, as you described.

I analysed code by myself, but I don't see any problem with starting a
new transaction in function ext4_ext_rm_leaf. If in this function new
transaction is created and system will crash in the middle of deleting
the file, eh_entries in extent_header will have correct value, so it
shouldn't cause any problem (eh_entries is decremented in the same
transaction, as zeroing out ex->len etc.). 

I hope, you will understand, what I want to say. 

If I'm wrong, please let me know.

Regards,

Lubos

tytso@mit.edu píše v Út 18. 03. 2014 v 13:14 -0400:
> On Tue, Mar 18, 2014 at 04:09:30PM +0100, Lubos Uhliarik wrote:
> > The main changes in patch are following:
> > 
> > a) commented out zeroing ex->ee_len, ee->start_hi and ee->start_lo,
> > because these entries are essential for undelete process
> 
> The reason why we have to zero out ex->ee_len, etc. is because the
> truncate operation can sometimes span multiple journal transactions.
> So as a result, we need to keep the file system consistent if we are
> interrupted (i.e., via a power fail event) while in the middle of a
> truncate operation.
> 
> It's a rare case, but it can happen if the journal is almost full at
> the time when the truncate eoperation has started, such that there is
> no room for to exntend the transaction handle, and so we are forced to
> start a new transaction (and possibly wait for a journal checkpoint
> operation).
> 
> In theory, it would be possible to figure out in advance whether or
> not we could fit the truncate in a single transaction, but it would
> require making the truncate operation be a two-pass operation --- once
> to determine how many blocks needs to be modified, and once to
> actually do the truncate operation.
> 
> > This patch shouldn't break ext4, I tested it with xfs_tests and tests 
> > were successfull.
> 
> I'm guessing you didn't do power fail testing --- and this is very
> important when messing with the design truncate/unlink code path.
> 
> Regards,
> 
> 						- 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: [RFC][PATCH 0/1] ext4: Undelete Feature for Ext4

[Lubos Uhliarik]

Hi Tytso

I'm trying to respond on your email ones again - more in detail.

tytso@mit.edu wrote:
> On Tue, Mar 18, 2014 at 04:09:30PM +0100, Lubos Uhliarik wrote:
> > The main changes in patch are following:
> > 
> > a) commented out zeroing ex->ee_len, ee->start_hi and ee->start_lo,
> > because these entries are essential for undelete process
> 
> The reason why we have to zero out ex->ee_len, etc. is because the
> truncate operation can sometimes span multiple journal transactions.
> So as a result, we need to keep the file system consistent if we are
> interrupted (i.e., via a power fail event) while in the middle of a
> truncate operation.
> 
> It's a rare case, but it can happen if the journal is almost full at
> the time when the truncate eoperation has started, such that there is
> no room for to exntend the transaction handle, and so we are forced to
> start a new transaction (and possibly wait for a journal checkpoint
> operation).

Yes, as I noticed in the function ext4_ext_rm_leaf in /fs/ext4/extents.c
file, there is a call of the function ext4_ext_truncate_extend_restart,
which can cause, that unlink operation will be devided into multiple
journal operations.

But, there should NOT be any problem with file system consistency in my
opinion, because decremention value of eh->eh_entries is in the same
transaction, as the block of code which will keep ex->ee_len, etc.
entries. 

So, if a new transaction is started, in eh->eh_entries will be correct
value of extents, which are in a block. 

New value of eh->eh_entries after decreasing after one iteration (one
extent removal) is written to the disk together with change of block
bitmap.

Between lines 2698
if (num == 0)
	/* this extent is removed; mark slot entirely unused */
	ext4_ext_store_pblock(ex, 0);

and 2727 

le16_add_cpu(&eh->eh_entries, -1);

in file fs/ext4/extents.c is no function call, which can mark block
dirty. That kind of function (ext4_ext_dirty) is called at line 2731. 

> 
> In theory, it would be possible to figure out in advance whether or
> not we could fit the truncate in a single transaction, but it would
> require making the truncate operation be a two-pass operation --- once
> to determine how many blocks needs to be modified, and once to
> actually do the truncate operation.




> 
> > This patch shouldn't break ext4, I tested it with xfs_tests and tests 
> > were successfull.
> 
> I'm guessing you didn't do power fail testing --- and this is very
> important when messing with the design truncate/unlink code path.

I did power failure testing, but I was unable to divide undelete process
into more transactions. I created the ext4 with the smallest possible
journal, but it didn't help, even I was creating and deleting 20 very
fragmented files at one moment. I didn't get any file system error,
which couldn't be repaired by replaying the journal. Anyway, as I wrote
before, I checked the code and I didn't see any problem, why it should
cause file system inconsistency.

If you have any questions, please ask me and I will try to respond
immediately, because my profesor needs to know, if this patch can be
considered as a part of next kernel version. Thank you. 

> 
> Regards,
> 
> 						- Ted

Kind regards,
Lubos