Here is some thoughts about enhancing ext3 to rescue deleted files.

The main idea is to be "lazy". That is, not to delete
old information, before it is really necessary. Thus
one has a possibility to rescue the old data.

My understanding is that mke2fs per default does not nuke the
data blocks.  So that is already "lazy". The things to analyze
is then the inodes and the superblock.

The superblock is already backed up a number of times.
I think one could easily have a copy also of the
"old superblock" - a special area  reserved for the previous
superblock, and made when making an mke2fs. 

Inodes. My idea is to not clear the inodes, when they
are marked as free, but to mark them also
as deleted, the reference count (=0) could be used for that, and then retain the data there.
This also in normal operation on the fs, and I think this is how it is done today.
Probably inodes are currently not cleared under normal operation currently, but just
marked as free. That is probably no code change as of today.

When doing a mke2fs - one should then first check whether
the old fs - if any - was ext2. If not, I see no reason not to
blank all inodes. In this way we are sure that
at the birth of the partition as an ext2 fs, all inodes were cleared.
If it was an ext2 fs, then the inodes
are probably valid, or some fsck thingie could go and try to
repair things - so we do our lazy allocation of inodes,
that is, we read in all the inodes, and then just set the 
free_inode flag. The rest is the just the existing data, dirty as they may be. 
This will cost a read of all existing inode data, which is doubling
of the IO for mke2fs.

When taking a inode from the bitmap free list, the inode is blanked.
The bitmap free inode list should be round-robin per block group,
so that newer deletions can be found for longer time. 

Normal fsck would then check the file tree for consistency,
no change. It would also check the inode table as usual
to rebuild the inode bitmap. Normal fsck would discard inodes 
that have an earlier status change date than the creation of the fs,
seeing that these are inodes from the previous incarnation of the fs.
This is on the assumption that the status change date is 
normally always set via a systems call, and thus it is reliable
that this indicates when the inode was last changed.

rescue fsck would check the inode table, and
create a tree like lost+found (possibly named /salvaged)
for inodes that are not deleted but 
which are free. Duplicate allocated
data blocks would be blanked, and the file possibly marked.

In the case of an accdential mke2fs, where only a few
blocks are allocated on the new fs, the whole old fs would
thus be fully salvageable,
maybe except the root, but maybe this can be a special case and we
can use the old superblock there, or some special blocks.
I think the accidential mke2fs is one of the relatively more
common errors (and the one I did), so special care for that
specific error could be implemented.

rescue fsck should also be doable on not infant fs,
one could make the mke2fs error, do a little work, and
then discover the error, and then have a good chance
of getting most back alive anyway.


rescuing deleted files on the fs, an old deleted files on the old
fs, and also newly deleted files on a new
fs could be done by fsck looking thru the inode table for free 
inodes with the 'deleted' bit set, and reallocate it
in a lost+found like tree called /deleted.

Cost: it does not cost much space. No extra space needed for
inodes. A little extra space needed for the old superblock,
and the old root inode, but this is a one time charge.
One bit in every inode for the deleted bit, this is
needed to be able to create a valid complete tree of the
old fs,  from walking all the inodes, and it can then be utilized
to rescue deleted files too. At mke2fs time there is a doubling of the IO
as all inodes need to be read in before written.

bloating: I think the stuff should be quite simple
to code, and should easily fit into normal mke2fs, e2fsck
and the kernel driver, so it could be maintained in normal code,
and no special utilities should be necessary.

Special consideration should be given to not damage the fs
further, when trying to rescue it. That is, no new inodes
like /salvaged and /deleted should overwrite useful
inodes, and no new blocks, eg for entries in /salvaged or /deleted
should be used, that could contain valid data from the old fs.
This could be done by keeping all such data incore in the rescue
program like e2fsck, until the check is complete, and some
unused areas in the combined rescued fs have been identified.
Another approach is to reserve such areas in advance and record
this in the superblock, eg inode 3, 4 and 5 for /lost+found
/salvaged and /deleted, and then some blocks reserved for directory
data probably at the very end of the fs. I dont know how much data that would be,
but in the case of fully recovering an empty fs, this would be next
to nothing, as the old directories would also be recoverable.

For new fs with another layout of inodes etc: well, maybe
one could copy the old inode list over, I am not sure of that.
The old superblock can be useful here, to determine 
the layout of the old fs. Existence of the old superblock should be
checked at every umount, and written if not there,
but forced writing of it should only be done by mke2fs.
This would allow for migration for older filesystems
to be able to use the new rescue facility, without
users not actually doing anything active to do migration.