implementing soft-updates
Hi
Does anyone know of any implementation of soft-updates over ext2? I'm starting a project on this for grad school, and I'd like to know of any previous (current?) efforts.
Thanks.
Alexis
Quoted 6 lines · Alexis S. L. Carvalho
Hi
Does anyone know of any implementation of soft-updates over ext2? I'm starting a project on this for grad school, and I'd like to know of any previous (current?) efforts.
Heh, ext3? ;)
Quoted 9 lines · Mike Fedyk
Quoted 6 lines · Alexis S. L. Carvalho
Hi
Does anyone know of any implementation of soft-updates over ext2? I'm starting a project on this for grad school, and I'd like to know of any previous (current?) efforts.
Heh, ext3? ;)
No. Ext3 uses journalling. Soft-updates is something different.
Dominik
Signature · 2 lines
"Those who would give up essential Liberty to purchase a little temporary Safety deserve neither Liberty nor Safety." (Benjamin Franklin)
Quoted 4 lines · Dominik Kubla
Quoted 3 lines · Mike Fedyk
Quoted 2 lines · Alexis S. L. Carvalho
Hi
Quoted 9 lines
Quoted 6 lines
Quoted 4 lines
Does anyone know of any implementation of soft-updates over ext2? I'm starting a project on this for grad school, and I'd like to know of any previous (current?) efforts.
Heh, ext3? ;)
No. Ext3 uses journalling. Soft-updates is something different.
Yes, I know that... (don't for get the ";)"...)
Sorry, I don't know if anyone else has started anyting like this.
It would be interesting to see how the locking would work compared to ext3.
You might get more responces from:
[email protected]
-and-
[email protected]
Since that's where the ext2/3 guys hang out.
Mike
Quoted 3 lines · Alexis S. L. Carvalho
Does anyone know of any implementation of soft-updates over ext2? I'm starting a project on this for grad school, and I'd like to know of any previous (current?) efforts.
That's interesting. Some comments:
It is common for controllers, RAID arrays, and the disks to mess up your ordering. Power failure during a write has been known to scribble on random unrelated parts of the disk. Power failure often creates bad sectors that can only be fixed by a large write that covers the affected area.
Ext2 has deletion time stamps. These are not really good for performance, but they help fsck to know what is going on.
While ext2 fsck doesn't guarantee anything, in practice it is far more reliable than ufs fsck. If you change the algorithms to be like those used by BSD, then you may lose some of the ability to recover. Remember, fsck isn't just for power failures. It tries to piece together a filesystem that has suffered disk corruption caused by attackers, kernel bugs, fdisk screwups, MS-DOS writing past the end of a partition, Windows NT Disk Manager, viruses, disk head crashes, and every other cause you can imagine. If you change fsck to make BSD-style assumptions about write ordering, you weaken the ability to deal with disasters.
I'm sure you are aware of ext3. You should also be aware of tux2. Tux2 uses the phase-tree algorithm to perform atomic updates of the whole filesystem. Tux2 looks horridly slow at first glance, but is actually quite fast. The overhead drops to almost nothing as the number of simultaneous operations goes to infinity. (the overhead asymptoticly approaches 0.1%) While the operations tend to cause fragmentation, they also make defragmentation be really cheap -- you can defragment on-th-fly as part of normal filesystem operations without any additional IO. There is a neat trick you can do with the phase-tree algorithm for better
integrity: make every non-leaf node carry checksums for all directly connected child nodes. (either plain or keyed crypto) Filesystem-level snapshots are easy with the phase-tree algorithm.
Soft-updates are mainly useful for OS wars. Lots of FUD comes flying out of the BSD camp. Ext2 horror stories are rare when you consider just how many millions of users ext2 has. Soft-updates would make our worst problems even worse. The whole point of soft-updates is to have fsck and the kernel trust the metadata a bit more... which is terrible if your VIA motherboard is mangling your metadata before it hits the disk. Not to say that doing well in an OS war isn't a useful goal though!
In case you are still thinking about what to do, here are a few filesystem ideas that you might like:
soft-updates for ext2
ext2 compression (e2compr)
delayed allocation (allocate space only when about to do IO) while rw mounted: defrag, undelete (not trash bin), grow, shrink, fsck get tux2 into production shape
use the phase-tree algorithm for FAT32 (hint: active FAT flags) new phase-tree filesystem, perhaps with JFS or XFS structure make ext2 extents work
make ext2 handle huge block sizes
mark idle filesystems clean; mark dirty before non-atomic updates ACLs compatible with NFSv4, fast, and compact
secure deletion (stop root, not the NSA: zero the name, inode...) tools for in-place filesystem conversion (ufs --> ext2)
HFS+ filesystem
Apple's UID hacks for Darwin (the BSD-like MacOS X kernel) design a fast way to map from inode number to filename(s)
try larger inodes (example: 168-byte, 3 in 512 bytes, 0,1,2,x,4,5,6,x,8...) provide real-time file IO (app buffers do not guarantee bandwidth)
BTW, the unbalanced trees can be good. They provide quick access to file magic (see "file" command) and other header information. We have read-ahead to take care of the rest of the file.
First of all, thanks for your comments.
Thus spake Albert D. Cahalan:
Quoted 6 lines
Quoted 3 lines · Alexis S. L. Carvalho
Does anyone know of any implementation of soft-updates over ext2? I'm starting a project on this for grad school, and I'd like to know of any previous (current?) efforts.
Quoted 7 lines
That's interesting. Some comments:
It is common for controllers, RAID arrays, and the disks to mess up your ordering. Power failure during a write has been known to scribble on random unrelated parts of the disk. Power failure often creates bad sectors that can only be fixed by a large write that covers the affected area.
OK, but if something scribbles on random unrelated parts of the disk there's not much you can do besides praying that fsck will fix it.
Quoted 13 lines
Ext2 has deletion time stamps. These are not really good for performance, but they help fsck to know what is going on.
While ext2 fsck doesn't guarantee anything, in practice it is far more reliable than ufs fsck. If you change the algorithms to be like those used by BSD, then you may lose some of the ability to recover. Remember, fsck isn't just for power failures. It tries to piece together a filesystem that has suffered disk corruption caused by attackers, kernel bugs, fdisk screwups, MS-DOS writing past the end of a partition, Windows NT Disk Manager, viruses, disk head crashes, and every other cause you can imagine. If you change fsck to make BSD-style assumptions about write ordering, you weaken the ability to deal with disasters.
I haven't looked into e2fsck yet, but if/when I get to it, I'll probably add a mode that makes some assumptions about the disk state. If you don't explicitly ask for this mode, you get the current behavior.
Also, this mode would only be run during the boot sequence under a specific situation (the system crashed while running with soft-updates). Note that if you were running a journalling fs, fsck wouldn't be run at all.
Quoted 1 line
I'm sure you are aware of ext3. You should also be aware of tux2.
I read some stuff about tux2 a couple of years ago, but I do have to re-read it all...
Quoted 3 lines
Soft-updates are mainly useful for OS wars. Lots of FUD comes flying out of the BSD camp. Ext2 horror stories are rare when you consider just how many millions of users ext2 has.
Well, I found soft-updates pretty interesting, and I want to play a bit with it. Anyway, given my (lack of) experience with kernel programming I don't believe I'll have anything useful for some time yet...
Quoted 2 lines
In case you are still thinking about what to do, here are a few filesystem ideas that you might like:
<nice list of fs projects>
hmm... I guess I find soft-updates sexy enough... :-)
Thanks
Alexis
Quoted 4 lines · Albert D. Cahalan
In case you are still thinking about what to do, here are a few filesystem ideas that you might like:
ext2 compression (e2compr)
- project needs polishing, integration
Quoted 1 line
delayed allocation (allocate space only when about to do IO)
- Andrew Morton has done this for 2.5
Quoted 1 line
while rw mounted: defrag, undelete (not trash bin), grow, shrink, fsck
- Andrew Morton has implemented for ext3 (kernel space, needs user tool)
Quoted 1 line
make ext2 extents work
- yes, discussion ongoing on ext2-devel, no real progress yet
Quoted 1 line
make ext2 handle huge block sizes
- kernel issues w.r.t. buffers > PAGE_SIZE
Quoted 1 line
mark idle filesystems clean; mark dirty before non-atomic updates
- maybe marginally useful
Quoted 1 line
tools for in-place filesystem conversion (ufs --> ext2)
- existing project
Quoted 1 line
try larger inodes (example: 168-byte, 3 in 512 bytes, 0,1,2,x,4,5,6,x,8...)
- discussion ongoing on ext2-devel with some good progress
Cheers, Andreas
--
Andreas Dilger
http://www-mddsp.enel.ucalgary.ca/People/adilger/
http://sourceforge.net/projects/ext2resize/
Quoted 6 lines · Andreas Dilger
Quoted 4 lines · Albert D. Cahalan
In case you are still thinking about what to do, here are a few filesystem ideas that you might like:
mark idle filesystems clean; mark dirty before non-atomic updates
- maybe marginally useful
I would think far mnore than marginally useful... this would provide
an improved possibility of avoiding fsck, something many people would find desirable. And along that line I'll offer one more idea, not to increment the mount count if a f/s is mounted and no writes are done to the f/s, such as ro mount, noatime mount and no writes, etc. The check for fsck after N mounts was designed to assist with reliability, not be a penalty in boot time.
Signature · 3 lines
bill davidsen <[email protected]> CTO, TMR Associates, Inc Doing interesting things with little computers since 1979.
Quoted 2 lines · Alexis S. L. Carvalho
OK, but if something scribbles on random unrelated parts of the disk there's not much you can do besides praying that fsck will fix it.
Well, the fact that ext2 uses fixed areas of the disk for specific purposes (e.g. inode table) and it has backups of a lot of metadata makes it very possible to recover from random data corruption.
Quoted 2 lines
Note that if you were running a journalling fs, fsck wouldn't be run at all.
Note that this is incorrect. Even with ext3, e2fsck is run on each boot. While in the normal case all it does is journal recovery (takes a few seconds at most) and do a superficial check of the superblock. This is incredibly useful, however, if there was a filesystem error, since e2fsck has a chance to check and cleanup the filesystem before it is put into use.
Cheers, Andreas
--
Andreas Dilger
http://www-mddsp.enel.ucalgary.ca/People/adilger/
http://sourceforge.net/projects/ext2resize/
On Tue, Apr 09, 2002 at 08:41:28PM -0400, Albert D. Cahalan wrote:
...
Quoted 10 lines
While ext2 fsck doesn't guarantee anything, in practice it is far more reliable than ufs fsck. If you change the algorithms to be like those used by BSD, then you may lose some of the ability to recover. Remember, fsck isn't just for power failures. It tries to piece together a filesystem that has suffered disk corruption caused by attackers, kernel bugs, fdisk screwups, MS-DOS writing past the end of a partition, Windows NT Disk Manager, viruses, disk head crashes, and every other cause you can imagine. If you change fsck to make BSD-style assumptions about write ordering, you weaken the ability to deal with disasters.
I disagree. In fact the current BSD softupdate code guarantees that all that ever happens is that freed blocks are not entered into the free block list. Something fsck can fix in background on a life system. See M. Kirk McKusicks BSDcon 02 paper 'Running fsck in background.'
Your argument that faulty hardware may create havoc with your on-disk data structures is something every file system is prone to unless it uses a raw-read-after-write for checking purposes. Something which definitely kills disk performance.
The background fsck capability, just like journalling or logging, are typically only in needed in 24/7 systems (sure, they are nice to have in your home system, but do you _REALLY_ need them? i don't!) and those system typically are run on proven hardware which is operated well within the specs. So please don't construct these kinds of arguments.
The fact that the BSD FFS in it's currently released version (which does not include snapshot and background fsck capability) is considered to be one of the more reliable file systems around, even when softupdates are enabled, speaks for itself. So please just as you don't want horror stories about Linux ext2 spread: don't do it yourself.
Alexis, if you're looking for a rewarding Linux project, don't focus too much on softupdates, the majority of linux users/developers couldn't care less. I wonder sometimes if this is perhaps because BSD did it first?
Read M. Kirk McKusick's paper on fsck and snapshots (it's in the proceedings of this years BSDcon, available from Usenix) and try to implement the snapshot capability for ext2/ext3. Everyone of us who has to do live backups of production systems will thank you if you get that development started. I found that Mr. McKusick is somebody who is very helpful towards people trying to understand his work, so you might get help from him if you get stuck. OTOH if you avoid the buzzword 'softupdates' many Linux file system hackers will be much more inclined to help you out with the Linux part.
Yours,
Dominik Kubla
Signature · 2 lines
"Those who would give up essential Liberty to purchase a little temporary Safety deserve neither Liberty nor Safety." (Benjamin Franklin)
Quoted 13 lines · Dominik Kubla
Quoted 10 lines · Albert D. Cahalan
While ext2 fsck doesn't guarantee anything, in practice it is far more reliable than ufs fsck. If you change the algorithms to be like those used by BSD, then you may lose some of the ability to recover. Remember, fsck isn't just for power failures. It tries to piece together a filesystem that has suffered disk corruption caused by attackers, kernel bugs, fdisk screwups, MS-DOS writing past the end of a partition, Windows NT Disk Manager, viruses, disk head crashes, and every other cause you can imagine. If you change fsck to make BSD-style assumptions about write ordering, you weaken the ability to deal with disasters.
Quoted 4 lines
I disagree. In fact the current BSD softupdate code guarantees that all that ever happens is that freed blocks are not entered into the free block list. Something fsck can fix in background on a life system. See M. Kirk McKusicks BSDcon 02 paper 'Running fsck in background.'
Two cases:
a. proper shutdown -- somewhat OK to never fsck b. unclean shutdown -- may involve kernel crashing
So with an unclean filesystem, _any_ avoidance of fsck is suspect. I have a UPS; when my system boots on an unclean filesystem it's because XFree86 thought it could run a hardware driver in userspace.
Journalling gives you a nice list of recently-touched data structures to examine. The phase-tree algorithm can support low-cost incremental checksumming of the whole filesystem. Soft-updates leave you with... well, is prayer any good? You'd better run fsck at boot, which AFAIK is exactly what is done; you even say "not include [...] background fsck".
Quoted 5 lines
The fact that the BSD FFS in it's currently released version (which does not include snapshot and background fsck capability) is considered to be one of the more reliable file systems around, even when softupdates are enabled, speaks for itself. So please just as you don't want horror stories about Linux ext2 spread: don't do it yourself.
I'm just tired of this: "Back when I used to use Linux 2.1.44 my disks were trashed so bad that I lost everything! So use BSD." Last time I checked, BSD fsck didn't have a set of regression tests like ext2 fsck does. On the BSD mailing lists you can read about fsck getting signal 11. So it's not God's Glorious Filesystem by any means.
Hi!
Quoted 6 lines
I'm just tired of this: "Back when I used to use Linux 2.1.44 my disks were trashed so bad that I lost everything! So use BSD." Last time I checked, BSD fsck didn't have a set of regression tests like ext2 fsck does. On the BSD mailing lists you can read about fsck getting signal 11. So it's not God's Glorious Filesystem by any means.
Actually, I believe I can make current e2fsck mark filesystem clean when it is not [by trashing disk badly and killing lost+found]. If you can mail me recent [static] e2fsck, I can test it and create image where it fails.
Pavel
Signature · 2 lines
Philips Velo 1: 1"x4"x8", 300gram, 60, 12MB, 40bogomips, linux, mutt, details at http://atrey.karlin.mff.cuni.cz/~pavel/velo/index.html.
Quoted 7 lines · Andreas Dilger
Quoted 4 lines · Albert D. Cahalan
In case you are still thinking about what to do, here are a few filesystem ideas that you might like:
ext2 compression (e2compr)
- project needs polishing, integration
Do we want to setup a project on sourceforge for this?
Quoted 3 lines · Dominik Kubla
try to implement the snapshot capability for ext2/ext3. Everyone of us who has to do live backups of production systems will thank you if you get that development started.
LVM can already do snapshots at the device level. It integrates with ext3/XFS/reiserfs via sync_super_lockfs/unlockfs so that what is in the snapshot is a consistent, clean filesystem.
There might need to be a little touchup with ext2 to support these calls, but even in the current state you get a usable filesystem snapshot, with the exception that the filesystem has not been marked clean.
As for a filesystem-level ext2/ext3 snapshot, this has also already been done (sf.net/projects/snapfs). The people who took over that project have removed all of the released files and CVS, but you can still get the CVS from the sourceforge CVS backups. I also have a version here, but don't have any time to work on it.
Cheers, Andreas
--
Andreas Dilger
http://www-mddsp.enel.ucalgary.ca/People/adilger/
http://sourceforge.net/projects/ext2resize/