Re: Journaling layer update - any really good programmer want to start working on the userland journal scanning utility ? You need to have a LOT of time available!

[Matthew Dillon <dillon@xxxxxxxxxxxxxxxxxxxx>]

:I have a question about this. How far can the UNDO system go? Will it
:be some kind of redo-log (think VxFS here) or will it allow arbitrary
:undo levels? Maybe it sounds crazy, but you could have 'unlimited' undo
:where unlimited amounts to available free disk space. It complicates
:the free block management a bit, but it's certainly doable. Basically
:the journal code should have an undo bitmap. It can allocate any free
:data block to store undo information. As soon as a datablock is needed
:by the sytem the oldest undo datablock gets used to store data. The
:filesystem doesn't need to know about it, just the journaling code,
:although balloc now needs to go through the journal code to make sure
:the undo blocks bitmap gets updated as well. This bitmap could live
:anywhere in the disk.

    The way the UNDO works is that the journal is made 'reversable', meaning
    that you can run the journal forwards and execute the related filesystem
    operations in order to 'track' a filesystem, or you can run the journal
    backwards in order to reverse-time-index a filesystem.  So what you get
    is an infinitely fine-grained undo capability.

    So, for example, lets say someone does a file truncation.  A forward-only
    journal would store this:

    truncate {
	file path / vnode id
	at offset BLAH
    }

    A reversable journal would store this:

    truncate {
	file path / vnode id
	at offset BLAH
	UNDO {
	    extend to offset original_blah
	    write {		(the data that was destroyed)
		at offset
		data
	    }
	    write {
		at offset
		data
	    }
	    
	}
    }

    If someone were to do a write() which overwrites prior data, the UNDO
    section would have to contain the original data.

    If you were to remove a 4GB file the journal would have to store 4GB 
    worth of data to UNDO that operation.

    But what you get is a complete audit trail, the ability to run the 
    journal forwards or backwards when reconstructing a filesystem or
    database, the ability to not only undelete a file but also to restore
    it (or an entire subhierarchy) as-of a particular date, the ability to
    figure out exactly how a security event might have occured, and a host of
    other capabilities.

    The UNDO capability will be optional, of course, but I see a lot of
    people, including myself, using it.  All of that disk space has to be 
    good for something eh? 

    --

    I just finished running a buildworld test with /usr/obj journaled 
    (without UNDO since it isn't done yet).  The buildworld only took 10
    seconds longer to run!  The journal generated from /usr/obj was about
    785 MB uncompressed, and 231 MB compressed.  Of course, nobody would
    want to journal /usr/obj in real life, but it's a good test!

					-Matt
					Matthew Dillon 
					<dillon@xxxxxxxxxxxxx>

:Sounds very well thought out, Matt. Definitely worth a look. I'll try
:to be in IRC during the weekend so maybe we can come up with something.
:
:Cheers,
:-- 
:Miguel Mendez <flynn@xxxxxxxxxxxxxxxxxx>