Trash mechanism

[Alexander Larsson]

On Wed, 2004-08-25 at 23:31, David Faure wrote:
> Hello Alexander,
> thanks for the detailed answer!
> 
> On Wednesday 25 August 2004 15:32, Alexander Larsson wrote:
> > > Could someone tell me if Nautilus uses some kind of metadata file already,
> > > to store the original location of the file, the date of deletion, the original mtime etc.?
> > 
> > No, but i've long wanted to have that so you can do "put back" on
> > trashed files. We do however move files to the trash instead of
> > copying them, so atime and mtime are not modified. 
> 
> In fact even if we move files between partitions we can preserve atime/mtime
> (people who use vfat for their $HOME don't count :). So OK, no need for
> mtime there either (this was also the conclusion of the old discussion: better
> not define a complete redundant filesystem, so we should store as little
> metadata as possible, which currently seems to be only
> - original location
> - original filename [see bottom of mail]
> - date of deletion

Yes, this makes sense.

> > If a trash dir couldn't be found/created we deny trashing the file and
> > asks the user if they'd like to delete it instead. If a trash
> > directory was found we just move the file/directory to the trash
> > directory as-is.
> This is something I plan to do differently in KDE;
> I have a different opinion on http://bugzilla.redhat.com/bugzilla/long_list.cgi?buglist=78671
> and it's that 
> 1) if there's no way to move to a directory on the same partition (no permission),
> or it doesn't make sense to do so (e.g. removeable media, as you pointed out)
> 2) and there's enough space in $HOME/.Trash,
> then we should move the file, even though it's across partitions.

Well. Lets take a common situation such as removing all the files on a
floppy, or in a more modern situation, a SecureDigital flashcard from
your camera. 

Removing the files is just a metadata operation that is really fast.
However if you copy files to a trash on another disk, this could
potentially take a long time. Reading all the images from my SD card
takes several minutes. Will the user really expect this normally fast
operation to get a progress dialog and take several minutes to execute.

I would expect you actually use the trash for only a very small amount
of the files you trash, therefore I think it makes sense only when we
can implement this function in a way that that its cost to the user is
very small. In the case of removable media this is frequently not true.

However, for some places, such as another partition on a fixed disk it
might make sense. The problem is that its very hard to detect these
cases in a good way, since all mounts are just mounts in unix. You can't
know what is removable or not without lots of code and heuristics. Also,
even in the case of another local HD, copying can take a lot of time if
the files are large, although perhaps we shouldn't save very large files
in the trash. 

I'm sure if we change to copying we will get bugreports on trashing
files on non-homedir partition taking ages. You just can't ever please
all users. :(

> But we don't have to agree on what the user experience should be,
> only on the location and contents of the trash-can directories :)

Yeah.

> > When viewing the trashcan we locate all the trash directories
> > currently on the system and present a unified trash directory from this.
> Yes. trash:/ ? The URI-discussion is another one, but maybe we can
> even agree on a uri scheme here. OTOH it doesn't matter much, people
> are not going to exchange trash uris :)

Yeah, we use trash: here. However, its not currently implemented as a
gnome-vfs backend, so only nautilus can use it. I'd like to change that
though. Unifying the uri isn't extremely important as you say, but otoh
it should be pretty obvious how to do, so we might as well try.

> > * Finding the trash directory is fast
> > * Trashing a file, if possible, is an atomic, constant time operation
> >   that will never error out due to out-of-space or other issue.Even  
> >   trashing large files is instant, which is important because the user
> >   don't expect trashing to be a costly operations, especially
> >   considering that most trash operations are never undone.
> One thing users expect even less, is to see the software refusing to do
> what they asked for - in cases where it's actually possible :)
> 
> I mean, I even saw people requesting "trashing" files from remote filesystems.
> Yeah, we both know people request weird stuff, but still :)

Well, they request the operation that we expose in the ui for removing
files. I'm not sure they request the priviledge to wait five minutes
while copying all the files on their camera. Anyway, this is obviously a
judgement call that each implementer can choose to do however he likes.

> > * If you trash a file with the same name on two different mounts the
> >   merged trash directory has two files with the same name. It still
> >   works, because internally it knows which file is from where, but it
> >   can look a bit strange in the ui.
> I was planning to disambiguate files using file[1].txt file[2].txt or whatever.
> Well, that doesn't really help the user much; it's merely a necessity so
> that the file items have different URLs.

That makes sense.

> > * If you trash a directory you own, that contains a file that you
> >   don't have permissions to remove (say someone else owns it) you end
> >   up with files in the trash dir you can't get rid of, so "empty trash"
> >   stops working.
> That one is pretty nasty. OTOH the same would happen when trying to
> delete (rm -r) the directory in the first place. Checking for this at
> "trashing" time might be better for the user experience, but otoh it might
> take a long time when trashing a huge directory...

Yeah. I don't have a good solution for this.

> Yes. I'm not convinced about storing trash on removable media.
> I'd rather let the "trash" operation move files to $HOME/.Trash in such
> a case.

I'm pretty sure I'd hate using such an approach. Emptying is a very
common operation on removable media (you do it every time you empty a
digital camera and every time you need to use a floppy for something
new), and it would be pretty slow. 

Of course one could expose both trash and delete operations in the ui
and punt the problem to the user. That would work for people who already
know this distinction and the pros and cons of trashing, but it would
imho unnecessarily complicate the ui.

> > * For files in shared directories, for instance a directory used for
> >   people in a project, its unlikely that you have write permissions to
> >   the root of the mountpoint, so you can't trash files there, even if
> >   you have remove permission in the directory.
> Same there.

Yes, in this case it makes sense to put trash in $home. At least for
"small" files. However, its hard to detect this case when trashing a
file.

> > * The algorithm used to locate the trash directory for a file breaks
> >   in the case of devices mounted in multiple locations. The location
> >   you get depends on in which mountpoint the first trashed file on
> >   that device is on. Devices mounted in multiple places is possible in
> >   linux with --bind mounts, although their use is not that common.
> Hmm. Yeah. We use another method of finding the mountpoint for a
> given directory (and the associated device) in KDE: by parsing mtab.
> That's got to be slower, of course... OTOH with proper caching (like you do
> too) it might not matter much.

We do mtab parsing too, for instance to detect all mounted systems
looking for trash directories. However experience has shown me that mtab
parsing is a bit fragile, and its also not very portable (i.e. it needs
lot of ifdefs). 
    
> > Looking at the list of problems, many of the hard-to fix
> > problems are related to removable media. What do other systems
> > (windows, mac, etc) do with trash on removable media? 
> I just checked using a USB key on a friend's laptop, and Windows actually
> doesn't allow trashing files from it, only real deletion. I guess it really only 
> allows moving to trash from local partitions.

Probably. I wonder what happens if you connect a 200Gig USB HD though?
Will it let you trash on that? Maybe if the filesystem is NTFS or
something... Where is the trash actually stored in windows?

I checked out what OS X does by testing my USB flashcard reader. It uses
a way similar to Nautilus. When you trash something on the flash it
creates a ".Trashes" directory on the root of the drive, and under that
it creates a directory with the name being the uid of the user (I guess
that makes some sense, especially on filesystems where you store the
owner as a uid), where it stores the files as-is. 

If you trash multiple files with the same name they get duplicate names
the normal duplicate name algorithm is used (i.e. its called "foo
(copy).txt" etc). The actual trash location is a merger of all the trash
dirs, and name conflicts between different trash dirs just show up as
two files with the same name. The merging is dynamic, so if you show the
trash and plug in a flash card its trash shows up in the trash window.

For files on the homedir partition there is a ~/.Trash directory where
files are just stored as-is. There is also a /.Trashes directory, but
its empty because its on the same partition as the homedir, so the
homedir .Trash is always used. I guess its useful if you have other HDs
mounted though.

There is a metadata fork stored for the uid dir (called "._$uid"), but
that doesn't seem to contain any data on the files in the directory. No
real metadata about the file is stored, and you can't "put back" the
file from the trash.

> > (Of course, its a bit hard to figure out whether a mountpoint is on
> > removable media in unix.)
> Yes (mtab parsing can help there too)

You mean by looking at the mountpoint name and device name using some
heuristics? Thats what we do for removable media handling atm, and its a
bit fragile. Maybe HAL and sysfs will make that better though.

> > ...  but if an admin creates a writable .Trash directory at the top of a mountpoint, we
> > create .Trash/$user directories in that. 
> That sounds like something nobody will think about doing....
> I don't really see a problem with auto-creating those dirs on non-removeable
> media. But, hmm, maybe people who don't like such "pollution" might want to
> turn it off, could be a checkbox option (using move-to-$HOME if disabled).

Well, the idea would be that the sysadmin could create a writable .Trash
in the top dir even though the top dir isn't otherwise user-writable.
This means we could do same-filesystem trashing on a filesystem where
you otherwise couldn't.

But yeah, often people would not do that. And in that case supporting
move-to-home makes sense.

> The main remaining question is the directory layout under ~/.Trash
> The idea of having info/ (with the metadata files) and files/ (with the actual files
> or directories) sounds good for several reasons:
> * easy transition for you - hmm, ok, except if the user has already deleted an
> info or files directory :/
> * separating metadata and actual user files/dirs, obviously.
> I don't see a need for the tmp/ subdir that was proposed in the mail I linked to,
> we have a mechanism for creating tempfiles in an atomic way already. But the
> other good thing about using subdirs (and leaving ~/.Trash itself without files)
> is that one can easily use any additional subdirs if wanted.
> 
> The metadata/ subdir would contain files with a generated name (any scheme
> is ok, the filename really doesn't matter from an interoperability point of view)
> containing the following three lines:
> <original location>  (path, or optionally URL if we really want to have support for deleting from remote directories)
> <original filename> (see below)
> <date/time of deletion> (ISO 8601 format, i.e. YYYY-MM-DDThh:mm:ssZ)
> 
> The files/ subdir would contain the deleted file or directory, using the same
> generated filename as the one used in metadata. It's important to specify that
> acquiring a tempfilename MUST be done in the metadata/ subdir first, to avoid
> the obvious race condition here.
> We can't just keep the initial filename since this would not make it possible to
> have multiple deleted files with the same name, so let's use the same tempfilename.
> 
> A thought about deleting directories: we only need metadata for the toplevel directory.
> Then we can move the directory to files/, and even if the user wants to restore
> a single file under there, we have all the medata: it can be deduced from the metadata
> for the toplevel directory.
> 
> How does that sound?

It sounds pretty good.

Some comments:

You mention "generated name" for the tempfile, but in like 99% of all
cases there won't be a collision, and i think using the real name is
helpful if you ever manually look into the trash dir. If the real name
doesn't work, using some algorithm like appending " (copy $n)" or
something should work fine.

I agree that metadata is only needed for the toplevel directory.

Why do you store both original location and original filename in the
metadata? Isn't the original filename just basename($original_location)?

What about filesystem operations in trash://? For instance, the names
presented for the files shown in trash:// are not the real filenames, so
if you rename a file then we can't rename the file. Should we instead
rewrite the original filename/location in the metadata? What if you
create a folder there, what do we set the original location to?

What about this usage for trash folders:

If the file is on the same device as $home, use $home/.Trash. Otherwise
check for an existing writable ".Trash" in the top dir of the filesystem
of the file. If it exists, use (create if needed) $topdir/.Trash/$uid as
the trash directory. If the .Trash directory doesn't exists, its up to
the implementation to either create it if possible (I don't recommend
implementations to do this for removable media, but detecting that case
is a bit hard and the detection might differ between implementations),
use $home/.Trash, or just not support trashing the file.

This way each implementation will always use the same directory,
sysadmins *can* set up trash directories for filesystems, and its still
up to the implementations to choose how trashing is handled (unless you
move media between implementations).

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
 Alexander Larsson                                            Red Hat, Inc 
                   alexl at redhat.com    alla at lysator.liu.se 
He's a fast talking pirate stage actor on the run. She's a virginal gypsy 
opera singer with an incredible destiny. They fight crime!