Re: Drawbacks of implementing undelete entirely in user space

Ray Auchterlounie (
Thu, 11 Jul 1996 17:41:25 +0100

In article <>
Darren J Moffat <> wrote:
>On Thu, 4 Jul 1996, Ray Auchterlounie wrote:

>> Erm, I may be very wrong here, but shouldn't there be a check on the
>> length of the name before you append stuff to it ?

>yes, but this was never meant to be the full solution :-)
>> Anyone running the patch care to experiment with what happens if you
>> delete several files with the same 255-character name ?

>At a guess the name, would get truncated by ext2fs and would probably
>result in an infinite loop in the fs code.

I think you just sprintf'ed over the end of a fixed length buffer
though - in which case it rather depends on what you overwrote :)

>Why would we still need a version number ? Since only one file of any
>name could ever exist in a directory then using the inode number of the
>directory it lived in makes it unique anywhere in the fs.
> $ unrm ~/tmp/foo
> UX: unrm multiple files exist please specify version number
> -rw------- 1 darren staff 3969 Jul 5 17:59 foo
> -rw------- 1 darren staff 1237 Jul 5 18:00 foo_1

>This is something completely diffrent, ie a snapshot or versioning
>filesystem - which I think Linux should have.

Hmm, possibly, but it's not quite the same since it only applies to
deleted files. Actually I did some experimenting and there is no need
for a version number - current ext2fs code will not let you create
multiple files of the same name in one directory, but if you do it
another way then it doesn't seem to cause any errors. The only thing
that happens at the moment is that _which_ of the files is returned
from a lookup varies - most likely due to dcache I think, so if we
avoid using that, we can get deterministic behaviour.

$ lsrm ~/tmp/foo*
-rw------- 1 darren staff 1237 Jul 5 18:00 foo
-rw------- 1 darren staff 3969 Jul 5 17:59 foo
$ lsrm /tmp/foo
-rw------- 1 darren staff 1237 Jul 5 18:00 foo

- in this case the most recently deleted file of that name is always

>> large filesystems if .wastebasket is a normal directory you could
>> easily run up against EXT2_LINK_MAX.

>.wastebasket would be a normal directory. <linux/ext2_fs.h> has the
>following declaration:

> #define EXT2_UNDEL_DIR_INO 6 /* Undelete directory inode */

>I'm not sure what the intention was with this, I can only assume that
>somesort of mkwastebasket util similar to mklost+found was intended.

I suspect something more like (from ext2_read_inode in inode.c):

if (inode->i_ino == EXT2_ACL_IDX_INO ||
inode->i_ino == EXT2_ACL_DATA_INO)
/* Nothing to do */ ;
+ else if (inode->i_ino == EXT2_UNDEL_DIR_INO)
+ inode->i_op = &ext2_undelete_inode_operations;
else if (S_ISREG(inode->i_mode))
inode->i_op = &ext2_file_inode_operations;

ie. the undelete directory (and probably everything beneath it) has a
special restricted set of operations.

The only operations needed are probably "readdir" "lookup" and maybe
"unlink" (== purge). Undeleting could be done by creating a new link
to the file (which is an operation on the target directory).

>As for the LINK_MAX why would we be using links ? when a file gets
>unlinked then it is moved to the .wastebasket directory.

If you use subdirectories (eg. inode no. of parent directory) as was
one suggestion, then you need to worry about LINK_MAX - a normal
directory has nlink==subdirectories (including . and ..) so you have a
maximum of LINK_MAX-2 subdirectories. I just counted directories on my
root partition - 560 in 140MB. Most of these will have had something
deleted from them at some point, which means at around 800MB or larger
you could expect problems...

>> If the undelete directory is a reserved inode (one is already
>> allocated for it in the header files) then you could perhaps implement
>> a psuedo directory structure under /.wastebasket (like /proc), maybe
>> storing details of deleted names in an expanded dirent with fields for
>> inode-number-of-directory and deletion-time.

>This sounds like it might have potential, but could get very complex very
>quickly. I'd like to keep undelete as small as possible it has a better
>chance of getting accepted by Linus et al.

Agreed (not forgetting that ext2 is now used in other OSs too) - but I
think using special code for the undelete directory would separate
most of the code out (into eg. undelete.c, like dir.c etc.) and
involve minimal changes to the existing code. Also I think that
some features, like auto-purging when fs needs space, would be easier
to implement using a different directory structure.

Also we perhaps ought to consider whether there should be a common
interface (or implementation) in the vfs layer.

Having seen the patch and looked through the fs code for, I've got a
few ideas on this (no real code yet - that's waiting on a system
upgrade, waiting on a new hd, waiting on some money I'm owed... :( ).
Anyone think we should discuss this somewhere other than dev.kernel ?

[ where it's probably boring lots of people who like rm(1) the way it
is and/or have fast tape drives... :) ]


Ray Auchterlounie                Research Student (still) at:
<>            Signal Processing Group
<>                  Cambridge University Engineering Dept.
                "Don't ask me about my thesis (TM)"