Date: Thu, 28 Aug 1997 09:39:29 -0700 (MST) From: Terry Lambert <terry@lambert.org> To: toor@dyson.iquest.net (John S. Dyson) Cc: terry@lambert.org, Shimon@i-connect.net, peter@spinner.dialix.com.au, petrilli@amber.org, smp@FreeBSD.ORG, peters@gil.com.au, mestery@winternet.com Subject: Re: A how does it work question. Message-ID: <199708281639.JAA01045@phaeton.artisoft.com> In-Reply-To: <199708281529.KAA02111@dyson.iquest.net> from "John S. Dyson" at Aug 28, 97 10:29:58 am
next in thread | previous in thread | raw e-mail | index | archive | help
> > For a general soloution instead, which will work with all FS's, even > > under stacking, a graphical soloution is required. You precompute > > Warshal's over the graph for everything but the next event to be > > added. This lets you (1) recompute it in linear time (O(n)), and > > (2) run dependencies between stacked layers. > > > Sounds like 72lbs of code to me :-). It's not. It's within 5% of writes to RAM, according to the Ganger/Patt paper, which is a less general soloution to the problem Soft Updates solves (it's FFS specific). The idea is that there is a dependency graph traversal that is static (not dynamic, as it probably needs to be) hard coded in dependency order. The updates which occur at intervals flush the dependency ordered operations to disk. The update code described in the paper was *also* FS specific. The correct way to do this (IMO) is to register a dependency graph at mount time, with a node/node resoloution procedure for each dependency relationship. For FFS, this is just the Ganger/Patt FFS code which runs at the update interval. Since this code was ripped out of FFS proper, this is not additional overhead. The only difference is that after you do this, it's now possible to order dependencies in FS's other than FFS, and between stacked FS layers (by inserting them into a hierarchy, very much like mounted FS's are inserted into your root hiearchy. There's a trivially more expensive registration process at mount, but on the whole it's a large net win: the I/O is still going to be much more expensive than the function pointer dereference and the O(n) traversal to the root of the dependency graph (n=the number of levels in the dependency hierarchy) to insert new "events" (any scheduled "soft" writes are effectively events). Anyway, just reread the Ganger/Patt paper with an eye towards stacking an FS and stil having the updates work, and the "meta" picture becomes pretty obvious pretty fast... Regards, Terry Lambert terry@lambert.org --- Any opinions in this posting are my own and not those of my present or previous employers.
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199708281639.JAA01045>