University of California Los Angeles Stackable Layers: An Architecture for File System Development A thesis submitted in partial satisfaction of the requirements for the degree Master of Science in Computer Science by John Shelby Heidemann 1991 This document is available as Technical Report CSD-910056 of the UCLA Computer Science Department. A PostScript version is available via anonymous ftp to ftp.cs.ucla.edu as pub/ficus/ucla csd 910056.ps. The author can be reached by electronic mail by [email protected]. This document was last changed August 8, 1991. Unix is a trademark of AT&T. SunOS and NFS are trademarks of Sun Mi- crosystems. PostScript is a trademark of Adobe Systems Incorporated. Apple and HyperCard is a registered trademarks of Apple Computer, Incorporated. (cid:13)c Copyright by John Shelby Heidemann 1991 The thesis of John Shelby Heidemann is approved. Rajive Bagrodia Richard R. Muntz Wesley W. Chu, Committee Co-Chair Gerald J. Popek, Committee Co-Chair University of California, Los Angeles 1991 i To my family| my mother Dorothy and my brother Ben ii Table of Contents 1 Introduction : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 1 1.1 Introduction : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2 1.2 Related Work : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4 1.2.1 Symmetric interfaces : : : : : : : : : : : : : : : : : : : : : 4 1.2.2 File system structuring : : : : : : : : : : : : : : : : : : : : 5 1.2.3 Stackable (cid:12)le systems : : : : : : : : : : : : : : : : : : : : : 5 1.3 Overview of the Thesis : : : : : : : : : : : : : : : : : : : : : : : : 5 2 Interface Design : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 7 2.1 Extensibility : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 9 2.2 Stacking : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 12 2.3 Stack Con(cid:12)guration : : : : : : : : : : : : : : : : : : : : : : : : : : 14 2.4 Interface De(cid:12)nition : : : : : : : : : : : : : : : : : : : : : : : : : : 16 2.5 E(cid:14)ciency : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 16 2.6 Flow of Control : : : : : : : : : : : : : : : : : : : : : : : : : : : : 16 2.7 Opaqueness : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 17 2.8 Summary : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 18 3 Interface Implementation : : : : : : : : : : : : : : : : : : : : : : : 19 3.1 The Existing Interface : : : : : : : : : : : : : : : : : : : : : : : : 21 3.2 Extensibility in the 405 Interface : : : : : : : : : : : : : : : : : : 24 3.3 Stack Creation : : : : : : : : : : : : : : : : : : : : : : : : : : : : 25 3.3.1 Stack con(cid:12)guration : : : : : : : : : : : : : : : : : : : : : : 25 3.3.2 File-level stacking : : : : : : : : : : : : : : : : : : : : : : : 27 3.4 Stacking and Extensibility : : : : : : : : : : : : : : : : : : : : : : 28 3.5 Inter-machine Operation : : : : : : : : : : : : : : : : : : : : : : : 31 3.6 Centralized Interface De(cid:12)nition : : : : : : : : : : : : : : : : : : : 32 3.7 Flow of Control : : : : : : : : : : : : : : : : : : : : : : : : : : : : 33 iii 4 Layering Techniques : : : : : : : : : : : : : : : : : : : : : : : : : : : 37 4.1 A Hypothetical Example : : : : : : : : : : : : : : : : : : : : : : : 38 4.2 Layer Composition : : : : : : : : : : : : : : : : : : : : : : : : : : 41 4.3 Layer Substitution : : : : : : : : : : : : : : : : : : : : : : : : : : 42 4.4 Cooperating Layers : : : : : : : : : : : : : : : : : : : : : : : : : : 44 4.5 Multi-layer Access : : : : : : : : : : : : : : : : : : : : : : : : : : 45 4.6 File System Testing and Veri(cid:12)cation : : : : : : : : : : : : : : : : 46 4.7 Compatibility with Layers : : : : : : : : : : : : : : : : : : : : : : 46 4.8 Out-of-kernel Development : : : : : : : : : : : : : : : : : : : : : : 47 5 Example Layers : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 49 5.1 A Minimal Layer : : : : : : : : : : : : : : : : : : : : : : : : : : : 50 5.1.1 Null layer details : : : : : : : : : : : : : : : : : : : : : : : 50 5.1.2 Layer tuning : : : : : : : : : : : : : : : : : : : : : : : : : : 51 5.1.3 Null layer use : : : : : : : : : : : : : : : : : : : : : : : : : 52 5.2 A Measurements Layer : : : : : : : : : : : : : : : : : : : : : : : : 52 5.3 Transport Layers : : : : : : : : : : : : : : : : : : : : : : : : : : : 54 5.4 Ficus: replicated (cid:12)le services : : : : : : : : : : : : : : : : : : : : : 55 5.5 Interface Versioning Layers : : : : : : : : : : : : : : : : : : : : : : 58 5.6 A Consistency Layer : : : : : : : : : : : : : : : : : : : : : : : : : 58 5.7 Other Layers : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 62 5.8 Summary : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 64 6 Evaluation : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 65 6.1 Interface Performance : : : : : : : : : : : : : : : : : : : : : : : : : 66 6.1.1 Micro-benchmarks : : : : : : : : : : : : : : : : : : : : : : 66 6.1.2 Interface performance : : : : : : : : : : : : : : : : : : : : : 68 6.1.3 Multiple layer performance : : : : : : : : : : : : : : : : : : 69 6.2 Layer Implementation E(cid:11)ort : : : : : : : : : : : : : : : : : : : : : 71 6.2.1 Minimum layer development : : : : : : : : : : : : : : : : : 73 6.2.2 Layer development experience : : : : : : : : : : : : : : : : 75 6.2.3 Layer development examples : : : : : : : : : : : : : : : : : 76 iv 6.2.4 Large scale example : : : : : : : : : : : : : : : : : : : : : 79 6.3 Summary : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 79 7 Related Work : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 81 7.1 The Vnode Interface : : : : : : : : : : : : : : : : : : : : : : : : : 82 7.2 Rosenthal’s Stackable Vnode Interface : : : : : : : : : : : : : : : 83 7.2.1 Stacking con(cid:12)guration : : : : : : : : : : : : : : : : : : : : 83 7.2.2 Stack view consistency : : : : : : : : : : : : : : : : : : : : 84 7.2.3 Interface extensibility : : : : : : : : : : : : : : : : : : : : : 87 7.3 MachObjects : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 87 7.4 The x-kernel : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 88 7.5 Summary : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 89 8 Conclusions : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 91 8.1 Contributions : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 92 8.2 Future Work : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 92 8.3 Summary : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 94 References : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 95 v List of Figures 2.1 A simple (cid:12)le system stack and improvements. : : : : : : : : : : : 13 2.2 A tree of (cid:12)le system layers to provide disk mirroring. : : : : : : : 14 3.1 A typical (cid:12)le system namespace. : : : : : : : : : : : : : : : : : : : 22 3.2 A namespace composed of two subtrees. : : : : : : : : : : : : : : 22 3.3 Operations supported in SunOS 4.0.3. : : : : : : : : : : : : : : : : 23 3.4 Mounting a UFS layer. : : : : : : : : : : : : : : : : : : : : : : : : 26 3.5 Stacking an encryption layer over the UFS. : : : : : : : : : : : : : 27 3.6 A two-level stack of vnodes. : : : : : : : : : : : : : : : : : : : : : 28 3.7 The problem of passing new operations through an old layer. : : : 30 3.8 Upcalls proceeding up a stack and between parallel stacks. : : : : 33 4.1 The Ficus stack of layers. : : : : : : : : : : : : : : : : : : : : : : : 43 4.2 Multi-layer access for transmission of encrypted data. : : : : : : 45 4.3 User-level layer development via transport layers. : : : : : : : : : 48 5.1 Measurement layers analyzing a caching layer. : : : : : : : : : : : 53 5.2 Decomposed Ficus physical and disk storage layers. : : : : : : : : 57 5.3 Logical con(cid:12)guration of a cache consistency layer. : : : : : : : : : 60 5.4 Layer con(cid:12)guration of the prototype cache consistency layer. : : : 61 6.1 Operation invocation under the vnode and 405 interfaces. : : : : : 67 6.2 Elapsed time as layers are added. : : : : : : : : : : : : : : : : : : 71 6.3 System time as layers are added. : : : : : : : : : : : : : : : : : : 72 6.4 A mounted pass-through layer. : : : : : : : : : : : : : : : : : : : 73 7.1 File-system in a (cid:12)le. : : : : : : : : : : : : : : : : : : : : : : : : : 84 7.2 Rosenthal’s v top approach to stack management. : : : : : : : : : 85 vi List of Tables 2.1 Vnode interface evolution in SunOS. : : : : : : : : : : : : : : : : 9 6.1 Modi(cid:12)ed Andrew benchmark comparisons. : : : : : : : : : : : : : 69 6.2 Recursive copy and remove comparisons. : : : : : : : : : : : : : : 70 6.3 Null layer implementation costs. : : : : : : : : : : : : : : : : : : : 74 6.4 A comparison of several (cid:12)le system layers by lines of C code. : : 77 6.5 A evaluation of (cid:12)le system layers by lines of C code. : : : : : : : 77 vii Acknowledgments This work would not have been possible without the support of my advisor, Dr. Gerald Popek, to whom I am most grateful. I would also like to thank the other members of the Ficus Project at UCLA. In particular I would like to thank Richard Guy for the distributed garbage collection algorithms which prompted the construction of a new (cid:12)le system, Tom Page for a careful reading of a draft of this thesis, and Dieter Rothmeier, Wai Mak, and Yuguang Wu for being the (cid:12)rst to use the new interface. I also would like to gratefully acknowledge the support of the Defense Ad- vanced Research Projects Agency and the USENIX Association for their (cid:12)nan- cial support. In the course of this research I was supported by DARPA contracts F29601-87-C-0072 and N00174-91-C-0107, and the 1990-91 USENIX Graduate Research Scholarship. viii