On incremental file system development

ABSTRACT

Developing file systems from scratch is difficult and error prone. Using layered, or stackable, file systems is a powerful technique to incrementally extend the functionality of existing file systems on commodity OSes at runtime. In this article, we analyze the evolution of layering from historical models to what is found in four different present day commodity OSes: Solaris, FreeBSD, Linux, and Microsoft Windows. We classify layered file systems into five types based on their functionality and identify the requirements that each class imposes on the OS. We then present five major design issues that we encountered during our experience of developing over twenty layered file systems on four OSes. We discuss how we have addressed each of these issues on current OSes, and present insights into useful OS and VFS features that would provide future developers more versatile solutions for incremental file system development.

REFERENCES

• 1: Anderson, D., Chase, J., and Vadhat, A. 2000. Interposed request routing for scalable network storage. In Proceedings of the 4th USENIX Symposium on Operating System Design and Implementation (OSDI) (San Diego, CA). 259--272.
• 2: Appavoo, J., Auslander, M., DaSilva, D., Edelsohn, D., Krieger, O., Ostrowski, M., Rosenburg, B., Wisniewski, R., and Xenidis, J. 2002. K42 overview. www.research.ibm.com/K42/
• 3: Akshat Aranya , Charles P. Wright , Erez Zadok, Tracefs: A File System to Trace Them All, Proceedings of the 3rd USENIX Conference on File and Storage Technologies, March 31-31, 2004, San Francisco, CA
• 4: Andrea C. Arpaci-Dusseau , Remzi H. Arpaci-Dusseau, Information and control in gray-box systems, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 5: Ayers, L. 1997. E2compr: Transparent file compression for Linux. Linux Gazette 18. www.linuxgazette.com/issue18/e2compr.html
• 6: Balzer, R. and Goldman, N. 1999. Mediating connectors. In Proceedings of the 19th IEEE International Conference on Distributed Computing Systems Workshop (Austin, TX). 72--77.
• 7: Matt Blaze, A cryptographic file system for UNIX, Proceedings of the 1st ACM conference on Computer and communications security, p.9-16, November 03-05, 1993, Fairfax, Virginia, United States [doi>10.1145/168588.168590]
• 8: Nathan C. Burnett , John Bent , Andrea C. Arpaci-Dusseau , Remzi H. Arpaci-Dusseau, Exploiting Gray-Box Knowledge of Buffer-Cache Management, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.29-44, June 10-15, 2002
• 9: Cluster File Systems, Inc. 2002. Lustre: A scalable, high-performance file system. www.lustre.org/docs/whitepaper.pdf
• 10: Mark D. Corner , Brian D. Noble, Zero-interaction authentication, Proceedings of the 8th annual international conference on Mobile computing and networking, September 23-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570645.570647]
• 11: Frank Dabek , M. Frans Kaashoek , David Karger , Robert Morris , Ion Stoica, Wide-area cooperative storage with CFS, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 12: D. R. Engler , M. F. Kaashoek , J. O'Toole, Jr., Exokernel: an operating system architecture for application-level resource management, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.251-266, December 03-06, 1995, Copper Mountain, Colorado, United States
• 13: Ghormley, D. P., Petrou, D., Rodrigues, S. H., and Anderson, T. E. 1998. SLIC: An extensibility system for commodity operating systems. In Proceedings of the Annual USENIX Technical Conference. (Berkeley, CA). 39--52.
• 14: Goh, E.-J., Shacham, H., Modadugu, N., and Boneh, D. 2003. Sirius: Securing remote untrusted storage. In Proceedings of the 10th Network and Distributed System Security (NDSS) Symposium. (San Diego, CA). 131--145.
• 15: Guy, R. G., Heidemann, J. S., Mak, W., Page Jr., T. W., Popek, G. J., and Rothmeier, D. 1990. Implementation of the Ficus replicated file system. In Proceedings of the Summer USENIX Technical Conference. (Anaheim, CA). 63--71.
• 16: Halcrow, M. A. 2004. Demands, solutions, and improvements for Linux filesystem security. In Proceedings of the 2004 Linux Symposium (Ottawa, Canada). 269--286.
• 17: Harder, B. 2001. Microsoft Windows XP system restore. http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dnwxp/html/windowsxpsystemrestore.asp
• 18: Heidemann, J. S. and Popek, G. J. 1991. A layered approach to file system development. Tech. Rep. CSD-910007, UCLA.
• 19: John S. Heidemann , Gerald J. Popek, File-system development with stackable layers, ACM Transactions on Computer Systems (TOCS), v.12 n.1, p.58-89, Feb. 1994 [doi>10.1145/174613.174616]
• 20: J. Heidemann , G. Popek, Performance of cache coherence in stackable filing, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.127-141, December 03-06, 1995, Copper Mountain, Colorado, United States
• 21: Hofmeyr, S. A., Somayaji, A., and Forrest, S. 1998. Intrusion detection using sequences of system calls. J. Comput. Security 6, 151--180.
• 22: Indra Networks. 2004. StorCompress. www.indranetworks.com/StorCompress.pdf
• 23: Michael B. Jones, Interposition agents: transparently interposing user code at the system interface, Proceedings of the fourteenth ACM symposium on Operating systems principles, p.80-93, December 05-08, 1993, Asheville, North Carolina, United States
• 24: Joukov, N., Rai, A., and Zadok, E. 2005. Increasing distributed storage survivability with a stackable raid-like file system. In Proceedings of the 2005 IEEE/ACM Workshop on Cluster Security, in conjunction with the 5th IEEE/ACM International Symposium on Cluster Computing and the Grid (CCGrid) (Cardiff, UK). 82--89.
• 25: Kashyap, A., Dave, J., Zubair, M., Wright, C. P., and Zadok, E. 2004. Using the Berkeley database in the Linux kernel. www.fsl.cs.sunysb.edu/project-kbdb.html
• 26: Swapnil Patil , Anand Kashyap , Gopalan Sivathanu , Erez Zadok, FS: An In-Kernel Integrity Checker and Intrusion Detection File System, Proceedings of the 18th USENIX conference on System administration, November 14-19, 2004, Atlanta, GA
• 27: Katcher, J. 1997. PostMark: A new filesystem benchmark. Tech. Rep. TR3022, Network Appliance. www.netapp.com/tech_library/3022.html
• 28: Angelos D. Keromytis , Janak Parekh , Philip N. Gross , Gail Kaiser , Vishal Misra , Jason Nieh , Dan Rubenstein , Sal Stolfo, A holistic approach to service survivability, Proceedings of the 2003 ACM workshop on Survivable and self-regenerative systems: in association with 10th ACM Conference on Computer and Communications Security, p.11-22, October 31-31, 2003, Fairfax, VA [doi>10.1145/1036921.1036923]
• 29: Yousef A. Khalidi , Michael N. Nelson, Extensible file systems in spring, Proceedings of the fourteenth ACM symposium on Operating systems principles, p.1-14, December 05-08, 1993, Asheville, North Carolina, United States
• 30: Kleiman, S. R. 1986. Vnodes: An architecture for multiple file system types in Sun UNIX. In Proceedings of the Summer USENIX Technical Conference. (Atlanta, GA). 238--247.
• 31: Klotzbücher, M. 2004. Development of a Linux overlay filesystem for software updates in embedded systems. M.S. thesis, Universität Konstanz, Konstanz, Germany.
• 32: MacDonald, J., Reiser, H., and Zarochentcev, A. 2002. Reiser4 transaction design document. www.namesys.com/txn-doc.html
• 33: David Mazières, A Toolkit for User-Level File Systems, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.261-274, June 25-30, 2001
• 34: Microsoft Corporation. 2004a. File system filter manager: Filter driver development guide. www.microsoft.com/whdc/driver/filterdrv/default.mspx
• 35: Microsoft Corporation. 2004b. Installable file system development kit. www.microsoft.com/whdc/devtools/ifskit/default.mspx
• 36: Microsoft Corporation. 2004c. Microsoft MSDN WinFS documentation. http://msdn.microsoft.com/data/winfs/
• 37: Miretskiy, Y., Das, A., Wright, C. P., and Zadok, E. 2004. Avfs: An on-access antivirus file system. In Proceedings of the 13th USENIX Security Symposium (Security) (San Diego, CA). 73--88.
• 38: Kiran-Kumar Muniswamy-Reddy , Charles P. Wright , Andrew Himmer , Erez Zadok, A Versatile and User-Oriented Versioning File System, Proceedings of the 3rd USENIX Conference on File and Storage Technologies, March 31-31, 2004, San Francisco, CA
• 39: Rajeev Nagar, Windows NT file system internals: a developer's guide, O'Reilly & Associates, Inc., Sebastopol, CA, 1997
• 40: Network Associates Technology, Inc. 2004. McAfee. www.mcafee.com
• 41: Nugent, J., Arpaci-Dusseau, A., and Arpaci-Dusseau, R. 2003. Controlling your PLACE in the file system with gray-box techniques. In Proceedings of the Annual USENIX Technical Conference (San Antonio, TX). 311--323.
• 42: Walter Oney, Programming the Microsoft Windows Driver Model, Second Edition, Microsoft Press, Redmond, WA, 2002
• 43: Pendry, J. S. and McKusick, M. K. 1995. Union mounts in 4.4BSD-Lite. In Proceedings of the USENIX Technical Conference on UNIX and Advanced Computing Systems (New Orleans, LA). 25--33.
• 44: Phillips, D. 2001. A directory index for EXT2. In Proceedings of the 5th Annual Linux Showcase and Conference (Oakland, CA). 173--182.
• 45: Rosenthal, D. S. H. 1990. Evolving the Vnode interface. In Proceedings of the Summer USENIX Technical Conference. (Anaheim, CA). 107--118.
• 46: Rosenthal, D. S. H. 1992. Requirements for a “stacking” vnode/VFS interface. Tech. Rep. SD-01-02-N014, UNIX International.
• 47: Schaefer, M. 2000. The migration filesystem. www.cril.ch/schaefer/anciens_projets/mfs.html
• 48: Seltzer, M. and Yigit, O. 1991. A new hashing package for UNIX. In Proceedings of the Winter USENIX Technical Conference (Dallas, TX). 173--184.
• 49: Shanahan, D. P. 2000. CryptosFS: Fast cryptographic secure nfs. M.S. thesis, University of Dublin, Dublin, Ireland.
• 50: Shepler, S., Callaghan, B., Robinson, D., Thurlow, R., Beame, C., Eisler, M., and Noveck, D. 2000. NFS version 4 protocol. Tech. Rep. RFC 3010, Network Working Group. Dec.
• 51: Muthian Sivathanu , Vijayan Prabhakaran , Florentina I. Popovici , Timothy E. Denehy , Andrea C. Arpaci-Dusseau , Remzi H. Arpaci-Dusseau, Semantically-Smart Disk Systems, Proceedings of the 2nd USENIX Conference on File and Storage Technologies, March 31-31, 2003, San Francisco, CA
• 52: Skinner, G. C. and Wong, T. K. 1993. “Stacking” vnodes: A progress report. In Proceedings of the Summer USENIX Technical Conference (Cincinnati, OH). 161--174.
• 53: SMCC. 1992. Lofs---Loopback Virtual File System. Sun Microsystems, Inc. SunOS 5.5.1 Reference Manual, Section 7.
• 54: David A. Solomon , Mark Russinovich, Inside Microsoft Windows 2000, Microsoft Press, Redmond, WA, 2000
• 55: Sophos. 2004. Sophos Plc. www.sophos.com
• 56: SunSoft. 1994. Cache file system (CacheFS). Tech. rep., Sun Microsystems, Inc. (Feb.)
• 57: Symantec. 2004. Norton antivirus. www.symantec.com
• 58: Szeredi, M. 2005. Filesystem in userspace. fuse.sourceforge.net
• 59: Tzachar, N. 2003. SRFS kernel module. Tech. Rep., Ben Gurion University (Sept.) www.cs.bgu.ac.il/~srfs/publications/implementation_report.pdf
• 60: Charles P. Wright , Jay Dave , Puja Gupta , Harikesavan Krishnan , David P. Quigley , Erez Zadok , Mohammad Nayyer Zubair, Versatility and Unix semantics in namespace unification, ACM Transactions on Storage (TOS), v.2 n.1, p.74-105, February 2006 [doi>10.1145/1138041.1138045]
• 61: Wright, C. P., Martino, M., and Zadok, E. 2003. NCryptfs: A secure and convenient cryptographic file system. In Proceedings of the Annual USENIX Technical Conference. (San Antonio, TX). 197--210.
• 62: Erez Zadok , Jason Nieh, Fist: a system for stackable file-system code generation, 2001
• 63: Erez Zadok , Johan M. Andersen , Ion Badulescu , Jason Nieh, Fast Indexing: Support for Size-Changing Algorithms in Stackable File Systems, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.289-304, June 25-30, 2001
• 64: Zadok, E. and Bădulescu, I. 1999. A stackable file system interface for Linux. In Proceedings of the LinuxExpo Conference. (Raleigh, NC). 141--151.
• 65: Zadok, E., Bădulescu, I., and Shender, A. 1999. Extending file systems using stackable templates. In Proceedings of the Annual USENIX Technical Conference. (Monterey, CA). 57--70.
• 66: Zadok, E. and Nieh, J. 2000. FiST: A language for stackable file systems. In Proceedings of the Annual USENIX Technical Conference. (San Diego, CA). 55--70.
• 67: Zadok, E., Osborn, J., Shater, A., Wright, C. P., Muniswamy-Reddy, K., and Nieh, J. 2004. Reducing storage management costs via informed user-based policies. In Proceedings of the 12th NASA Goddard, 21st IEEE Conference on Mass Storage Systems and Technologies (MSST) (College Park, MD). 193--197.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.7 Distribution, Maintenance, and Enhancement
          Subjects: Portability

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
        D.2.13 Reusable Software
            Subjects: Reuse models
  D.4 OPERATING SYSTEMS
      D.4.3 File Systems Management
          Subjects: File organization
      D.4.7 Organization and Design

General Terms:
Design

Keywords:
I/O manager, IRP, Layered file systems, VFS, extensibility, stackable file systems, vnode