OSDev.org

Solar wrote:Another example. I am using Directory Opus as replacement for Windows Explorer. There's "File" - "Edit" - "View"..., and the top entry in "Edit" is named "Undo". It's even accessed with Ctrl-Z, just as in my favourite text editor. I can undo file deletions, file moves, file renames, lots of stuff. All that Opus does is adding a different UI to the Windows Trashcan. D'oh.

Explorer does this too.

I think our disagreement comes from our individual definitions of "file system" being different. For me, "file system" is not the driver subsystem of an OS, or the File Server of a microkernel, but the physical layout of files and directories on-disk.

I claim that you do not need a "special" file system - like, e.g. EXT4 - to come up with some decent logic for delete, undelete, and wipe. You probably need some metadata / bookkeeping, like when a file was "deleted", but that can be done with "traditional" file systems just as well, with the logic handled in the driver or the OS.

Agree?

Solar wrote: I think our disagreement comes from our individual definitions of "file system" being different. For me, "file system" is not the driver subsystem of an OS, or the File Server of a microkernel, but the physical layout of files and directories on-disk.

That might be part of the confusion, I count the driver plus the physical layout as the file system itself.

I claim that you do not need a "special" file system - like, e.g. EXT4 - to come up with some decent logic for delete, undelete, and wipe. You probably need some metadata / bookkeeping, like when a file was "deleted", but that can be done with "traditional" file systems just as well, with the logic handled in the driver or the OS.

Agree?

No. In most (if not all) current filesystems that "support" undeleting files, files are normally deleted and can only be brought back in special circumstances, among which the accidental not overwriting of the file and the file being contiguous on disk. The result is that the recovery is unreliable, and most certainly not a feature of the filesystem or even the driver. It's more of a bug in a new dress.

However, if you /DO/ put it in the filesystem, where you'd only delete files off the physical disk when you need the space they take, you can save deleted files for the entire content of the disk (no lame 4% / 2GB limit or something like that), and if you need it all you don't have to worry about physically deleting the files off the disk (the file deletion idea is in the filesystem, not as an afterthought).

Seeing as it is very easy to put in this place, it logically works in this place, it is unreliable if put in a different layer, and it cannot even be made to work decently for most cases, I strongly vote for putting it in the filesystem (driver) and not in the operating system in itself. If you want to undelete files that's ok, but don't use the crap left behind by some programs as "recovery information" or "a feature".

This shouldn't be too difficult to implement. As after formatting, the data area of the disk is, at least in FATxx volumes, either zeroed or filled with a particular value. When you write to the disk, check for that value and don't write on anything that's not that value. Then if there aren't anything of that value, then just write anywhere.

The downside of this is speed. As for every write, you may have to do a read as well!

Unless there's a quicker way to do this?

srg

Candy wrote: I count the driver plus the physical layout as the file system itself.

On a dual-boot Windows / Linux system with a shared FAT32 partition, that would mean you're using a different "file system" on the same partition depending on which OS (and driver) you booted.

In most (if not all) current filesystems that "support" undeleting files, files are normally deleted and can only be brought back in special circumstances, among which the accidental not overwriting of the file and the file being contiguous on disk.

Hmpf. Sometimes I feel like I'm unable to make myself clear.

Yes, when the "delete" function of your OS is to write some zeroes to some crucial metadata structure, and the "undelete" function of your OS is to hope that nothing bad has happened in the file system yet, you're in deep horse droppings.

That's why your OS should be smart enough to hold "deleted" files in a meta-state from which they can be safely and reliably be recovered as long as they're in this state (i.e., "trashcan", or however you'd like to call it.)

However, if you /DO/ put it in the filesystem, where you'd only delete files off the physical disk when you need the space they take, you can save deleted files for the entire content of the disk (no lame 4% / 2GB limit or something like that)...

That's what I claim: This handling can be done just as well in the OS, or the File Server if you're in microkernel land, for any on-disk data structure. You can employ such a scheme for a FAT32 that everyone can read, for a XFS that can handle huge partitions, or an AmigaFFS you keep out of nostalgia.

Seeing as it is very easy to put in this place, it logically works in this place...

You need OS (or tool) support if you want to select a file that you deleted last week for undeletion, unless you want to undo every file operation you did since then sequentially. (Hey, you even need OS / tool support for that!)

Means, you need an "undelete selector", and an "undo", in your user interface anyway, in addition to the file system driver. You just needlessly spreaded the "undelete" logic across two layers.

...it is unreliable if put in a different layer...

How can placing it into data structures (which are hard to change / improve once published) and disk driver code (which runs in rather critical places of your OS) be more reliable than implementing it in user space?

...and it cannot even be made to work decently for most cases...

What in hell are you referring to? Microsoft screwed it up, and KDE screwed it up likewise. Is that proof enough for you that "it cannot be made to work decently"? Damn, we all should stop working on our OS'es immediately, it can't be done better...

If you want to undelete files that's ok, but don't use the crap left behind by some programs as "recovery information" or "a feature".

Not "by some programs", but your OS. The OS decides what std::remove() or DeleteFile() do and what not, right? Regardless of the layer you implement it in, the OS has to also provide ListDeletedFiles() and Undelete(), right? The OS is the level where you can cleanly abstract those functions from the underlying FS driver(s), making the concept more flexible, and allowing you to have Undelete() working even on partitions you share with mainstream operating systems.

Instead you are proposing to work out a new filesystem, throwing away tons of tested, proven, and well supported concepts and driver code, just because it doesn't provide metadata you could just as well hold elsewhere?

Sorry but I'm bewildered. I'd like to have a brain dump from you so I can backtrace where that idea comes from... ???

@ srg:

What you're suggesting is not "Undelete", but "drive compression".

Solar wrote:

Candy wrote: I count the driver plus the physical layout as the file system itself.

On a dual-boot Windows / Linux system with a shared FAT32 partition, that would mean you're using a different "file system" on the same partition depending on which OS (and driver) you booted.

Yes, that's correct. A file system in my view is the set of functions that are supplied by the operating system. If Linux doesn't supply long file names on the exact same disk structures it is in my view a different file system. The bits may be the same, but the view is different, so in my opinion it's something else.

In most (if not all) current filesystems that "support" undeleting files, files are normally deleted and can only be brought back in special circumstances, among which the accidental not overwriting of the file and the file being contiguous on disk.

Hmpf. Sometimes I feel like I'm unable to make myself clear.

Yes, when the "delete" function of your OS is to write some zeroes to some crucial metadata structure, and the "undelete" function of your OS is to hope that nothing bad has happened in the file system yet, you're in deep horse droppings.

That's why your OS should be smart enough to hold "deleted" files in a meta-state from which they can be safely and reliably be recovered as long as they're in this state (i.e., "trashcan", or however you'd like to call it.)

And exactly this is wrong with it. Your file system should hold the information on the files, that's what it's defined to do. If you "delete" a file by moving it to a certain directory, the undeletion information has to be stored alongside it, using some sort of proprietary interface. This adds a layer that administers files on top of the layer that is defined to administer files. That's wrong.

That's what I claim: This handling can be done just as well in the OS, or the File Server if you're in microkernel land, for any on-disk data structure. You can employ such a scheme for a FAT32 that everyone can read, for a XFS that can handle huge partitions, or an AmigaFFS you keep out of nostalgia.

But whatever interface you choose, it's operating system specific, not file system specific. Any different driver would then be unable to undelete files "deleted" by the other, resulting in chaos. If you put it in the FS data you can be sure that all use the same info, and hey surprise, the structure used is *exactly* the same as for normal files. It fits the function perfectly.

Seeing as it is very easy to put in this place, it logically works in this place...

You need OS (or tool) support if you want to select a file that you deleted last week for undeletion, unless you want to undo every file operation you did since then sequentially. (Hey, you even need OS / tool support for that!)

Means, you need an "undelete selector", and an "undo", in your user interface anyway, in addition to the file system driver. You just needlessly spreaded the "undelete" logic across two layers.

The user interface might need to provide the interface, but it most certainly shouldn't provide the mechanism. Separation of mechanism and policy should be one of your design principles

...it is unreliable if put in a different layer...

How can placing it into data structures (which are hard to change / improve once published) and disk driver code (which runs in rather critical places of your OS) be more reliable than implementing it in user space?

The more reliable argument is based on the two types of undelete-info that I know of:

-Windows-trashcan-style: It's more reliable because all info is naturally stored (it was never gone in the first place) and is stored along with the file. Also, when you delete a file, you don't logically free the space associated with it, so I really feel I'm moving a file when I intend to delete it. Undeleting becomes a different form of move then, in my feeling. If I wanted to move the file, I'd move it.
- FAT hope-style: You're hoping for the file to still be there, the clusters not retaken (by accident!), not overwritten, and the file to be contiguous. When you use this sort of undelete, you cannot be sure ANYTHING is kept, making it very unreliable. You should be able to see that without me telling it.
<ker-chop - followup by next post>

</ker-chop follow-up>

...and it cannot even be made to work decently for most cases...

What in hell are you referring to? Microsoft screwed it up, and KDE screwed it up likewise. Is that proof enough for you that "it cannot be made to work decently"? Damn, we all should stop working on our OS'es immediately, it can't be done better...

No, I'm not saying that. Don't pull that farce on me. The undelete-FAT-style cannot be made to work decently, if only because it's just the cr*p left behind by some other programs (programs -> win95, dos, drdos, pcdos, winxp, stuff like that). The trashcan design can be made to work transparently, which it should have been in the first place. Still, the design as you propose breaks a couple of design principles, among which no-percolation and separating-policy-from-mechanism. If you don't adhere to these, I can fully understand you. However, if so, I cannot see you as a good systems designer anymore.

If you want to undelete files that's ok, but don't use the crap left behind by some programs as "recovery information" or "a feature".

Not "by some programs", but your OS. The OS decides what std::remove() or DeleteFile() do and what not, right? Regardless of the layer you implement it in, the OS has to also provide ListDeletedFiles() and Undelete(), right? The OS is the level where you can cleanly abstract those functions from the underlying FS driver(s), making the concept more flexible, and allowing you to have Undelete() working even on partitions you share with mainstream operating systems.

Instead you are proposing to work out a new filesystem, throwing away tons of tested, proven, and well supported concepts and driver code, just because it doesn't provide metadata you could just as well hold elsewhere?

some programs -> your OS and all the other OSes that run on it. You can guess that none of the other OSes is going to support your way, and the ways they use are designed to be feature-packed (both gnu and microsoft do this!). Also, they are not designed to be good, they're designed to be good enough to sell. If that's what you want, use Windows or the GNU system.

As for my own OS, there /IS/ no FS code, and I refuse to copy any from other OSes (see my mission statement @ sf...). My idea of my OS target is that it works good. The methods that are in use don't work good, reliably or portably. If people using other OSes can thoroughly be hit by one of my design choices, then I'm not going to make that choice.

Another of my principles is the principle of least surprise, when I delete a file I expect the file to be gone, and the space to be free. If I subsequently want to use the space, it should be free for me to use, without complaints. If I want to restore the file, the filesystem should at least make a best-effort to keep the file for me. Whether that's in a properly-implemented trash can or in the file system itself doesn't matter for my user interface. However, the principle of least surprise is not just for your OS (and your method) but for other OSes too. If deleting on a different OS is going to leave my disk full of junk (even if it can reuse it!), I'm going to call that OS unreliable for deleting files. That's my point of when I delete, I want delete.

The only way to do this portably is not by using a special structure (no 5 OSes are going to agree on that ever, so it fails my option) but in the file system. That can only be done reliably if you design a new filesystem, which I was planning on anyway (because of a certain feature that I require).

Sorry but I'm bewildered. I'd like to have a brain dump from you so I can backtrace where that idea comes from... ???

I personally don't think ctrl-F is going to work on brain dumps, and if it's not you're going to have one hell of a job figuring out the structures .

And as always, after all the words are spoken, we end up with only minute differences in concept - only without realizing it earlier.

Let's put it this way:

A file system should provide metadata and procedures to properly support undeletion. Most existing ones don't.

An operating system should provide an intuitive (least-surprising) interface to undeletion. Most existing ones don't.

Now the only question is the direction of approach, and where you draw the boundary.

You agreed (more or less) that an "undelete" UI can be implemented on top of inferor file systems. So my solution would be a generic UI that provides an "undelete" metaphor (you'd probably call it "policy"). To interface various different file systems, I would use a plugin system. (I intend to do so anyway.)

And the beauty is, your and my solution aren't even mutual exclusive. The backend plugin for your CandyUndeleteFS would probably consist of only minimal code, since all the metadata and logic is already there. The ext3fs plugin would be more extensive, and leave some kind of "metadata directory" on the hard drive - just like "lost & found" of today.

You would go for the perfect solution, and "force" your users to use your file system or not having undelete at all. I would very much like a perfect solution, but as soon as you meet the heterogenous world I'm willing to compromise (a bit) as long as it benefits the user.

Solar wrote: @ srg:

What you're suggesting is not "Undelete", but "drive compression".

Drive compression? Drive compression is putting the whole file system into a "Compressed Volume file" And reading a writing to that in a way that eliminates slack (so you don't get a 1KB file in a 32KB cluster, with the other 31KB now being wasted).

In what I'm talking about you look at clusters/blocks that have never been used since the last format and only saving new data there, even if what's already been allocated is part of a deleted file. Then once there is no "never been allocated" blocks/clusters left, you write over the deleted files.

Untill all the non allocated blocks/clusters, you can get perfect Undeletes, but afterwards, it's just like the FAT "hope and prey" method.

BTW The trashcan like idea has been on the PC since AFAIK The Undelete that came with DOS 6.2 which was by Central Point Software. In that you had 3 forms of protection. Standard, Delete Tracker and Delete Sentry.

Standard was that FAT "Hope and Pray" Method.

Delete Tracker was "Hope and Pray" but with the added bonus that AFAIK stored the first charachter of the file's name in it's memory. So you didn't need the first char when undeleting.

Delete Sentry was like a Trashcan, although you couldn't empty it, it would remove some of it's entries after a certain period of time. I don't think Windows 95-XP does this.

Would an emptyable Delete Sentry be a good enough comprimise with current File systems?

srg

Solar wrote: And as always, after all the words are spoken, we end up with only minute differences in concept - only without realizing it earlier.

Yup, that's the short version of my posts (and your posts too probably)

Let's put it this way:

A file system should provide metadata and procedures to properly support undeletion. Most existing ones don't.

An operating system should provide an intuitive (least-surprising) interface to undeletion. Most existing ones don't.

Now the only question is the direction of approach, and where you draw the boundary.

Well, yes. That's all true and complies with what I think (still need that braindump? I'm busy but windows keeps saying I don't have enough space, and that it'll take somewhere between 1.9 and 7.6 million minutes... damn win95 bugs...)

You agreed (more or less) that an "undelete" UI can be implemented on top of inferor file systems. So my solution would be a generic UI that provides an "undelete" metaphor (you'd probably call it "policy"). To interface various different file systems, I would use a plugin system. (I intend to do so anyway.)

And the beauty is, your and my solution aren't even mutual exclusive. The backend plugin for your CandyUndeleteFS would probably consist of only minimal code, since all the metadata and logic is already there. The ext3fs plugin would be more extensive, and leave some kind of "metadata directory" on the hard drive - just like "lost & found" of today.

That's again true. BTW, I'd like to call it AFS - Atlantis File System, partition type 3B (if it's free...)

You would go for the perfect solution, and "force" your users to use your file system or not having undelete at all. I would very much like a perfect solution, but as soon as you meet the heterogenous world I'm willing to compromise (a bit) as long as it benefits the user.

And that's exactly where we disagree. In my opinion, your solution benefits the user but only if he uses only your OS. My point is that if he only uses your OS, he's not going to use a non-good filesystem for any reason, when there's the better solution available (and yes, pushing the users in the right direction does sound good to me).

If the user uses other OSes, they are going to be left with files that take place and have no use (from that OSes point of view). Again, that OS is going to make its own temporary files, leaving you with a solution that results in the same situation as the Windows one now is, with the exception that this is by design and in the Windows case it's because of a nonimplemented possible feature.

That's the difference. In the case of the user, I'm going to push him towards the "better" filesystem. Nothing to say that I'm going to actively do that, I'm just going to implement the features each FS offers, and then let the user decide what he/she wants. The FAT FS does NOT offer undeletion capability, the Ext2 FS does NOT offer undeletion. Emulating that for the benefit of the user is going to make the shift to a better filesystem slower thereby slowing technological progress.

Now, ok, that might just be a little too much emphasis. Still, it adds to the problem of people still using FAT on WinXP for instance. It's plain stupid, but because they don't see any advantage, they don't switch. Now, if the NTFS choice would have more advantages, and more obvious advantages (such as a faster, securer, more reliable OS), and the user was aware of these things, the user would choose NTFS over FAT any time. They're not known, so the user doesn't change anything, under the motto "if it ain't broke, don't fix it". Because of that people keep using FAT even though it's nearly the worst filesystem there is. Compare the HTML chaos that is guaranteed to keep existing while IE still has a significant share of the market. There are better alternatives, but since using some emulation and hacking you can use the old idea (bad html) nobody can be bothered to use decent html. Result is technological halt.

The idea of "blocks generations" SRG proposes has something interresting ... However, there are often considerations like "keep files close to their directories" that makes the scheme of forcing all the disk blocks to have been used at least once before reusing a freed block poor, regarding performances ...

Now what additionnal metadata a FS would need to offer "real" undeletion ... that is, an undelete mechanism that is able to tell if the file is completely or only partially recoverable ? but still making 'tagged for deletion' files appear as free space ? ...

Would it also be interresting to have 'deleted files' physically moved to some sort of "graveyard" as a background when they're occupying "strategically important locations" like being close to a frequently used directory or something alike ?

I'd be tempted to say that in addition of the 'free blocks' logical list, there should be a 'could-be-freed' blocks list, which the operating system can order in the way it prefers so that (for instance), more recently deleted files are less likely to be reused than long-deleted files and that files you "typed" with your bare hands are less likely to be reused than files you downloaded from the Net or that result in the application on some tool on some other file ...

I consider wasting a few MB's of drive space a small tradeoff for having undelete / trashcan capabilities under both my own OS and the mainstream OS on the other partition, without having to confuse my user with either the availability of undelete depending on file system (if I go your way), or the semantics of undelete (if I would use D:\recycle the Windows way while offering some other way for the native partition).

I agree with your notion that offering downward compatibility slows overall progress, but sure as damnation it also speeds up acceptance.

...and if you don't want undelete in my OS, well, switch it off.

PS: Stop that braindump before your hard drive dies and you have to run "Recovery" on that...

Pype.Clicker wrote: Now what additionnal metadata a FS would need to offer "real" undeletion ... that is, an undelete mechanism that is able to tell if the file is completely or only partially recoverable ? but still making 'tagged for deletion' files appear as free space ? ...

Yes. I would implement the freeing-deleted-files-when-space-needed function in the filesystem driver, not the OS itself. This way, the OS doesn't have to know how deleted files are maintained, it just knows they are, and that they can be used for free space. By not freeing the diskblocks immediately, you save yourself the trouble of finding them back again later.

Would it also be interresting to have 'deleted files' physically moved to some sort of "graveyard" as a background when they're occupying "strategically important locations" like being close to a frequently used directory or something alike ?

Having a constantly running optimizer that moves the deleted files to the rear end of the disk, that sorts directories etc. based on usage and writing, makes use of subclusters for files that are not being written to (explicitly or implicitly), compresses files that are not used (again explicitly or implicitly), auto-sets ACL's to some decent value for each file (not automatically available for everybody! damn you windows + unix!). Those sort of things, I can see quite a place for such an optimizer. Also, it might just clean out the log you keep on a high-performance USB stick or something without moving parts

Oh, and of course the FS is spannable over multiple different devices for performance and administration issues.

I'd be tempted to say that in addition of the 'free blocks' logical list, there should be a 'could-be-freed' blocks list, which the operating system can order in the way it prefers so that (for instance), more recently deleted files are less likely to be reused than long-deleted files and that files you "typed" with your bare hands are less likely to be reused than files you downloaded from the Net or that result in the application on some tool on some other file ...

I would make that a could-be-deleted files list, since when you reuse a block nothing tells the deleted file that it's actually gone, thereby wrecking the reliability issue again.

As for the files that you typed yourself, I'd sort the list by size and possibly by type (not extension, file type ala clicker's idea). If it's a document you keep it. If it's a huge temp file (cdrom image?) delete it first. That way the functionality is optimized. Still, this all comes down to a best-effort. Just being able to keep files for the space that's available without explicitly calling it in use would make both the free-space counter and the deleted-file-recovery a lot more usable. I don't want to end up using multigigabyte amounts on my harddisk only because of temporary files.

For the can-be-deleted flag, I seriously would like to add cached files. If a file is cached you can easily retrieve it again. Saves you some administration again.

In short, I want a computer that uses my disk space for making my computing experience a better thing (by aligning stuff & caching stuff, and making undeletion possible), but when I want the space, I want the space. The OS should stop using it for caching because I need it for something more important.

And I'd really like to educate users to keep at least 10-20% of the disk free, for performance reasons .

which leads to the final question 'what is important?' (we all know the answer is '42' already ) ...

I mean i'm probably unlikely to be happy if some 'deleted-but-still-recoverable' documents become unrecoverable because the system lacks space for downloading a DiVx, right ?
Especially if those documents are my thesis (you know, that word file i'm editting for about 3 years now )

I'd suggest that each file get a sort of "importance level" which can be set automatically using some heuristics (the program that created the file, the user that made it, the mime type of the file, the importance of the "directory" where it is stored, etc.) and that can be adjusted manually by the user (perhaps using some 'tags' UI)

When disk space is missing for a specific task, the system can automatically permanently delete any file that has a 'lower' importance than your current task, but user agreement should be asked before "equal" or "more" important files are permanently deleted (of course, only among files selected for deletion).

The only trouble here is that the 'importance' is actually computed while the file is "alive" and used when the file has been 'scheduled' for deletion by the user ...