Recovery domains: an organizing principle for recoverable operating systems

ABSTRACT

We describe a strategy for enabling existing commodity operating systems to recover from unexpected run-time errors in nearly any part of the kernel, including core kernel components. Our approach is dynamic and request-oriented; it isolates the effects of a fault to the requests that caused the fault rather than to static kernel components. This approach is based on a notion of "recovery domains," an organizing principle to enable rollback of state affected by a request in a multithreaded system with minimal impact on other requests or threads. We have applied this approach on v2.4.22 and v2.6.27 of the Linux kernel and it required 132 lines of changed or new code: the other changes are all performed by a simple instrumentation pass of a compiler. Our experiments show that the approach is able to recover from otherwise fatal faults with minimal collateral impact during a recovery event.

REFERENCES

• 1: Philip A. Bernstein , Vassco Hadzilacos , Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 2: Thomas C. Bressoud , Fred B. Schneider, Hypervisor-based fault tolerance, ACM Transactions on Computer Systems (TOCS), v.14 n.1, p.80-107, Feb. 1996 [doi>10.1145/225535.225538]
• 3: George Candea , Shinichi Kawamoto , Yuichi Fujiki , Greg Friedman , Armando Fox, Microreboot — A technique for cheap recovery, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.3-3, December 06-08, 2004, San Francisco, CA
• 4: John Criswell , Andrew Lenharth , Dinakar Dhurjati , Vikram Adve, Secure virtual architecture: a safe execution environment for commodity operating systems, Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles, October 14-17, 2007, Stevenson, Washington, USA
• 5: Dinakar Dhurjati , Sumant Kowshik , Vikram Adve, SAFECode: enforcing alias analysis for weakly typed languages, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 6: E. N. (Mootaz) Elnozahy , Lorenzo Alvisi , Yi-Min Wang , David B. Johnson, A survey of rollback-recovery protocols in message-passing systems, ACM Computing Surveys (CSUR), v.34 n.3, p.375-408, September 2002 [doi>10.1145/568522.568525]
• 7: Wu-chun Feng, Making a Case for Efficient Supercomputing, Queue, v.1 n.7, 10-01-2003 [doi>10.1145/957717.957772]
• 8: Jim Gray, The transaction concept: virtues and limitations (invited paper), Proceedings of the seventh international conference on Very Large Data Bases, p.144-154, September 09-11, 1981, Cannes, France
• 9: Haryadi S. Gunawi , Vijayan Prabhakaran , Swetha Krishnan , Andrea C. Arpaci-Dusseau , Remzi H. Arpaci-Dusseau, Improving file system reliability with I/O shepherding, Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles, October 14-17, 2007, Stevenson, Washington, USA
• 10: Maurice Herlihy , J. Eliot B. Moss, Transactional memory: architectural support for lock-free data structures, Proceedings of the 20th annual international symposium on Computer architecture, p.289-300, May 16-19, 1993, San Diego, California, United States
• 11: G. C. Hunt, J. R. Larus, M. Abadi, M. Aiken, P. Barham, M. Fýhndrich, C. H. O. Hodson, S. Levi, N. Murphy, B. Steensgaard, D. Tarditi, T. Wobber, and B. Zill. An overview of the Singularity project. Technical Report MSR-TR-2005-135, Microsoft Research, October 2005.
• 12: Chris Lattner , Vikram Adve, LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, p.75, March 20-24, 2004, Palo Alto, California
• 13: David E. Lowell , Subhachandra Chandra , Peter M. Chen, Exploring failure transparency and the limits of generic recovery, Proceedings of the 4th conference on Symposium on Operating System Design & Implementation, p.20-20, October 22-25, 2000, San Diego, California
• 14: David E. Lowell , Peter M. Chen, Free transactions with Rio Vista, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.92-101, October 05-08, 1997, Saint Malo, France
• 15: Chi Cao Minh , Martin Trautmann , JaeWoong Chung , Austen McDonald , Nathan Bronson , Jared Casper , Christos Kozyrakis , Kunle Olukotun, An effective hybrid transactional memory system with strong isolation guarantees, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 16: George C. Necula , Jeremy Condit , Matthew Harren , Scott McPeak , Westley Weimer, CCured: type-safe retrofitting of legacy software, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.3, p.477-526, May 2005 [doi>10.1145/1065887.1065892]
• 17: Christopher J. Rossbach , Owen S. Hofmann , Donald E. Porter , Hany E. Ramadan , Bhandari Aditya , Emmett Witchel, TxLinux: using and managing hardware transactional memory in an operating system, Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles, October 14-17, 2007, Stevenson, Washington, USA
• 18: 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
• 19: Nir Shavit , Dan Touitou, Software transactional memory, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.204-213, August 20-23, 1995, Ottowa, Ontario, Canada [doi>10.1145/224964.224987]
• 20: A. Shinnar, D. Tarditi, M. Plesko, and B. Steensgaard. Integrating support for undo with exception handling. Technical Report MSR-TR-2004-140, Microsoft Research, Dec. 2004.
• 21: P. Starzetz and W. Purczynski. Linux kernel setsockopt MCAST_MSFILTER integer overflow vulnerability, 2004. http://www.securityfocus.com/bid/10179.
• 22: Michael M. Swift , Muthukaruppan Annamalai , Brian N. Bershad , Henry M. Levy, Recovering device drivers, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.1-1, December 06-08, 2004, San Francisco, CA
• 23: Michael M. Swift , Brian N. Bershad , Henry M. Levy, Improving the reliability of commodity operating systems, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 24: I. L. Traiger. Trends in systems aspects of database management. In In Int'l Conf. on Databases, pages 1--21, 1983.
• 25: W. Weimer and G. Necula. Finding and preventing run-time error handling mistakes, 2004.
• 26: C. M. F. Rubira , Zhixue Wu, Fault Tolerance in Concurrent Object-Oriented Software through Coordinated Error Recovery, Proceedings of the Twenty-Fifth International Symposium on Fault-Tolerant Computing, p.499, June 27-30, 1995
• 27: Feng Zhou , Jeremy Condit , Zachary Anderson , Ilya Bagrak , Rob Ennals , Matthew Harren , George Necula , Eric Brewer, SafeDrive: safe and recoverable extensions using language-based techniques, Proceedings of the 7th symposium on Operating systems design and implementation, November 06-08, 2006, Seattle, Washington

INDEX TERMS

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

General Terms:
Design, Measurement, Reliability

Keywords:
akeso, automatic fault recovery, recovery domains