Improving the reliability of commodity operating systems

ABSTRACT

Despite decades of research in extensible operating system technology, extensions such as device drivers remain a significant cause of system failures. In Windows XP, for example, drivers account for 85% of recently reported failures. This paper describes Nooks, a reliability subsystem that seeks to greatly enhance OS reliability by isolating the OS from driver failures. The Nooks approach is practical: rather than guaranteeing complete fault tolerance through a new (and incompatible) OS or driver architecture, our goal is to prevent the vast majority of driver-caused crashes with little or no change to existing driver and system code. To achieve this, Nooks isolates drivers within lightweight protection domains inside the kernel address space, where hardware and software prevent them from corrupting the kernel. Nooks also tracks a driver's use of kernel resources to hasten automatic clean-up during recovery.To prove the viability of our approach, we implemented Nooks in the Linux operating system and used it to fault-isolate several device drivers. Our results show that Nooks offers a substantial increase in the reliability of operating systems, catching and quickly recovering from many faults that would otherwise crash the system. In a series of 2000 fault-injection tests, Nooks recovered automatically from 99% of the faults that caused Linux to crash.While Nooks was designed for drivers, our techniques generalize to other kernel extensions, as well. We demonstrate this by isolating a kernel-mode file system and an in-kernel Internet service. Overall, because Nooks supports existing C-language extensions, runs on a commodity operating system and hardware, and enables automated recovery, it represents a substantial step beyond the specialized architectures and type-safe languages required by previous efforts directed at safe extensibility.

REFERENCES

• 1: Apache Project. http://httpd.apache.orgApache HTTP server version 2.0, 2000. Available at http://httpd.apache.org.
• 2: Brian N. Bershad , Thomas E. Anderson , Edward D. Lazowska , Henry M. Levy, Lightweight remote procedure call, ACM Transactions on Computer Systems (TOCS), v.8 n.1, p.37-55, Feb. 1990 [doi>10.1145/77648.77650]
• 3: B. N. Bershad , S. Savage , P. Pardyak , E. G. Sirer , M. E. Fiuczynski , D. Becker , C. Chambers , S. Eggers, Extensibility safety and performance in the SPIN operating system, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.267-283, December 03-06, 1995, Copper Mountain, Colorado, United States
• 4: Andrew D. Birrell , Bruce Jay Nelson, Implementing remote procedure calls, ACM Transactions on Computer Systems (TOCS), v.2 n.1, p.39-59, February 1984 [doi>10.1145/2080.357392]
• 5: Daniel Bovet , Marco Cesati , Andy Oram, Understanding the Linux Kernel, Second Edition, O'Reilly & Associates, Inc., Sebastopol, CA, 2002
• 6: George Candea , Armando Fox, Recursive Restartability: Turning the Reboot Sledgehammer into a Scalpel, Proceedings of the Eighth Workshop on Hot Topics in Operating Systems, p.125, May 20-22, 2001
• 7: J. Chapin , M. Rosenblum , S. Devine , T. Lahiri , D. Teodosiu , A. Gupta, Hive: fault containment for shared-memory multiprocessors, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.12-25, December 03-06, 1995, Copper Mountain, Colorado, United States
• 8: Jeffrey S. Chase , Henry M. Levy , Michael J. Feeley , Edward D. Lazowska, Sharing and protection in a single-address-space operating system, ACM Transactions on Computer Systems (TOCS), v.12 n.4, p.271-307, Nov. 1994 [doi>10.1145/195792.195795]
• 9: Peter M. Chen , Brian D. Noble, When Virtual Is Better Than Real, Proceedings of the Eighth Workshop on Hot Topics in Operating Systems, p.133, May 20-22, 2001
• 10: Andy Chou , Junfeng Yang , Benjamin Chelf , Seth Hallem , Dawson Engler, An empirical study of operating systems errors, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 11: Helen Custer, Inside Windows NT, Microcomputer Applications, Suisun City, CA, 1992
• 12: Jack B. Dennis , Earl C. Van Horn, Programming semantics for multiprogrammed computations, Communications of the ACM, v.9 n.3, p.143-155, March 1966 [doi>10.1145/365230.365252]
• 13: Richard P. Draves , Brian N. Bershad , Richard F. Rashid , Randall W. Dean, Using continuations to implement thread management and communication in operating systems, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.122-136, October 13-16, 1991, Pacific Grove, California, United States
• 14: D. Engler, B. Chelf, A. Chou, and S. Hallem. Checking system rules using system-specific, programmer-written compiler extensions. In Proceedings of the 4th USENIX Symposium on Operating Systems Design and Implementation, pages 1--16, 2000.
• 15: 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
• 16: R. S. Fabry, Capability-based addressing, Communications of the ACM, v.17 n.7, p.403-412, July 1974 [doi>10.1145/361011.361070]
• 17: Bryan Ford , Godmar Back , Greg Benson , Jay Lepreau , Albert Lin , Olin Shivers, The Flux OSKit: a substrate for kernel and language research, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.38-51, October 05-08, 1997, Saint Malo, France
• 18: A. Forin, D. Golub, and B. Bershad. An I/O system for Mach. In Proc. Usenix Mach Symposium, pages 163--176, Nov. 1991.
• 19: J. Gettys, P. L. Carlton, and S. McGregor. http://www.hpl.hp.com/techreports/Compaq-DEC/CRL-90-8.pdfThe X window system version 11. Technical Report CRL-90-08, Digital Equipment Corporation, Dec. 1900.
• 20: A. Gillen, D. Kusnetzky, and S. McLaron. The role of Linux in reducing the cost of enterprise computing, Jan. 2002. IDC white paper.
• 21: James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 22: J. C. Haarsten. The Bluetooth radio system. IEEE Personal Communications Magazine, 7(1):28--36, Feb. 2000.
• 23: Steven M. Hand, Self-paging in the Nemesis operating system, Proceedings of the third symposium on Operating systems design and implementation, p.73-86, February 1999, New Orleans, Louisiana, United States
• 24: Hewlett Packard. http://www.hp.com/hpinfo/newsroom/press/31oct01a.htmHewlett Packard Digital Entertainment Center, Oct. 2001. http://www.hp.com/hpinfo/newsroom/press/31oct01a.htm.
• 25: Merle E. Houdek , Frank G. Soltis , Roy L. Hoffman, IBM System/38 support for capability-based addressing, Proceedings of the 8th annual symposium on Computer Architecture, p.341-348, May 12-14, 1981, Minneapolis, Minnesota, United States
• 26: Mei-Chen Hsueh , Timothy K. Tsai , Ravishankar K. Iyer, Fault Injection Techniques and Tools, Computer, v.30 n.4, p.75-82, April 1997 [doi>10.1109/2.585157]
• 27: Intel Corporation. The IA-32 Architecture Software Developer's Manual, Volume 1: Basic Architecture. Intel Corporation, Jan. 2002. Available at http://www.intel.com/design/pentium4/manuals/24547010.pdf.
• 28: R. Jones. http://www.netperf.orgNetperf: A network performance benchmark, version 2.1, 1995. Available at http://www.netperf.org.
• 29: Eric J. Koldinger , Jeffrey S. Chase , Susan J. Eggers, Architecture support for single address space operating systems, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.175-186, October 12-15, 1992, Boston, Massachusetts, United States
• 30: Henry M. Levy, Capability-Based Computer Systems, Butterworth-Heinemann, Newton, MA, 1984
• 31: J. Liedtke, On micro-kernel construction, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.237-250, December 03-06, 1995, Copper Mountain, Colorado, United States
• 32: Microsoft Corporation. http://www.microsoft.com/hwdev/download/hardware/fatgen103.pdf FAT: General overview of on-disk format, version 1.03, Dec. 2000.
• 33: D. Mosberger and T. Jin. httperf: A tool for measuring web server performance. In First Workshop on Internet Server Performance, pages 59---67, June 1998. ACM.
• 34: George C. Necula , Peter Lee, Safe kernel extensions without run-time checking, Proceedings of the second USENIX symposium on Operating systems design and implementation, p.229-243, October 29-November 01, 1996, Seattle, Washington, United States
• 35: Wee Teck Ng , Peter M. Chen, The Systematic Improvement of Fault Tolerance in the Rio File Cache, Proceedings of the Twenty-Ninth Annual International Symposium on Fault-Tolerant Computing, p.76, June 15-18, 1999
• 36: Elliot I. Organick, A programmer's view of the Intel 432 system, McGraw-Hill, Inc., New York, NY, 1983
• 37: David Patterson , Aaron Brown , Pete Broadwell , George Candea , Mike Chen , James Cutler , Patricia Enriquez , Armando Fox , Emre Kiciman , Matthew Merzbacher , David Oppenheimer , Naveen Sastry , William Tetzlaff , Jonathan Traupman , Noah Treuhaft, Recovery Oriented Computing (ROC): Motivation, Definition, Techniques,, University of California at Berkeley, Berkeley, CA, 2002
• 38: Project-UDI. Introduction to UDI version 1.0. Technical report, Project UDI, Aug. 1999.
• 39: Rob Short, Vice President of Windows Core Technology, Microsoft Corp. private communication, 2003.
• 40: Jerome H. Saltzer, Protection and the control of information sharing in multics, Communications of the ACM, v.17 n.7, p.388-402, July 1974 [doi>10.1145/361011.361067]
• 41: Frank Schmuck , Jim Wylie, Experience with transactions in QuickSilver, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.239-253, October 13-16, 1991, Pacific Grove, California, United States
• 42: M. Schroeder , M. Burrows, Performance of Firefly RPC, Proceedings of the twelfth ACM symposium on Operating systems principles, p.83-90, November 1989
• 43: Margo I. Seltzer , Yasuhiro Endo , Christopher Small , Keith A. Smith, Dealing with disaster: surviving misbehaved kernel extensions, Proceedings of the second USENIX symposium on Operating systems design and implementation, p.213-227, October 29-November 01, 1996, Seattle, Washington, United States
• 44: Standard Performance Evaluation Corporation. http://www.spec.org/osg/web99/The SPECweb99 benchmark, 1999.
• 45: Jeremy Sugerman , Ganesh Venkitachalam , Beng-Hong Lim, Virtualizing I/O Devices on VMware Workstation's Hosted Virtual Machine Monitor, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.1-14, June 25-30, 2001
• 46: Mark Sullivan , Michael Stonebraker, Using Write Protected Data Structures To Improve Software Fault Tolerance in Highly Available Database Management Systems, Proceedings of the 17th International Conference on Very Large Data Bases, p.171-180, September 03-06, 1991
• 47: P. Thurrott. Windows 2000 server: The road to gold, part two: Developing windows. Paul Thurrott's SuperSite for Windows, Jan. 2003.
• 48: TiVo Corporation. www.tivo.com TiVo digital video recorder, 2001. www.tivo.com.
• 49: V. Uhlig, U. Dannowski, E. Skoglund, A. Haeberlen, and G. Heiser. Performance of address-space multiplexing on the Pentium. Technical Report 2002-1, University of Karlsruhe, 2002.
• 50: A. van de Ven. http://www.fenrus.demon.nl/kHTTPd: Linux HTTP accelerator. Available at http://www.fenrus.demon.nl/.
• 51: Robert Wahbe , Steven Lucco , Thomas E. Anderson , Susan L. Graham, Efficient software-based fault isolation, Proceedings of the fourteenth ACM symposium on Operating systems principles, p.203-216, December 05-08, 1993, Asheville, North Carolina, United States
• 52: D. A. Wheeler. http://www.dwheeler.com/sloc/redhat71-v1/redhat71sloc.htmlMore than a gigabuck: Estimating GNU/Linux's size, July 2002. Available at http://www.dwheeler.com/sloc/redhat71-v1/redhat71sloc.html.
• 53: A. Whitaker, M. Shaw, and S. D. Gribble. Denali: Lightweight virtual machines for distributed and networked applications. In Proceedings of the 5th USENIX Symposium on Operating Systems Design and Implementation, pages 195--209, Dec. 2002.
• 54: Emmett Witchel , Josh Cates , Krste Asanović, Mondrian memory protection, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 55: M. Young, M. Accetta, R. Baron, W. Bolosky, D. Golub, R. Rashid, and A. Tevanian. Mach: A new kernel foundation for UNIX development. In Proceedings of the 1986 Summer USENIX Conference, pages 93--113, June 1986.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.5 Reliability
          Subjects: Fault-tolerance

General Terms:
Management, Reliability

Keywords:
I/O, device drivers, protection, recovery, virtual memory