next up previous contents
Next: 2.3 Barriers to File Up: 2.2.2 A Stackable Vnode Previous: 2.2.2 A Stackable Vnode Interposition and Composition

Later works [Rosenthal92,Skinner93] established the current terminology for the field, discarding ``stacking'' in favor of ``interposition'' and ``composition.'' The term ``stacking'' was considered at once to have too many implications, to be too vague, and to imply only a linear LIFO structure with no fan-in or fan-out.

Interposition is the new term for stacking. The defining papers [Rosenthal92,Skinner93] explain a particular implementation of interposition based on a new definition of vnode. The new vnode contains only the public fields of the old vnode and a new data structure called a pvnode contains the private fields of the old vnode. A ``vnode chain'' now becomes a single vnode (providing a unique identity for the file) plus a ``chain''4 of linked pvnodes. Interposed functionality is represented by one pvnode per open file.

Pvnodes may contain pointers to other vnodes, with the effect that all the linked vnodes may need to be regarded as a single object. This effect is called composition. Composition, in particular, requires the following two capabilities [Rosenthal92]:

The ability to lock a complete interposition chain with one operation.

Treating an interposition chain as an atomic unit. An operation that failed midway should result in undoing anything that was done when the operation began at the head of the chain.

Figure fig-pvnode-chain shows this structure for a compressing, encrypting file system, that uses UFS as its persistent storage. For each of the three file system layers in the stack, there is one pvnode. Each pvnode contains a pointer back to the file system that it represents, so that the correct operations vector is used. The three pvnodes are linked together in the order of the stack from the top to the bottom. The head of the stack is referenced from a single vnode structure. The purpose of this restructuring that Skinner & Wong had proposed was so that the three pvnodes could be used as one composed entity (shown here as a dashed enclosing box) that could be locked using a single lock variable in the new vnode structure.

Figure: Composition Using Pvnodes

Figure: Composition Using Pvnodes




The linked data structures created by interposition and the corresponding complex semantics arising from composition complicate concurrency control and failure recovery.

One concurrency control problem is how to lock an arbitrarily long interposition chain as cheaply as possible. Another, harder, problem is how to lock more than one chain for multi-vnode operations.

The failure recovery problem arises from composition. If a multi-vnode operation fails midway, it is vital to rollback the operations that have succeeded. Both Rosenthal and Skinner & Wong discuss adapting the database concept of atomic transactions. Specifically, each pvnode would contain routines to abort, commit, and ``prepare''5 the effects of operations on it. However, probably because of the complexity involved, no one has yet implemented transactions in support of composition. Consequently, ``stacks'' of interposed file systems may have failure behavior that is different from single file systems.

next up previous contents
Next: 2.3 Barriers to File Up: 2.2.2 A Stackable Vnode Previous: 2.2.2 A Stackable Vnode
Erez Zadok