Dynamic and adaptive updates of non-quiescent subsystems in commodity operating system kernels

ABSTRACT

Continuously running systems require kernel software updates applied to them without downtime. Facilitating fast reboots, or delaying an update may not be a suitable solution in many environments, especially in pay-per-use high-performance computing clusters and mission critical systems. Such systems will not reap the benefits of new kernel features, and will continue to operate with kernel security holes unpatched, at least until the next scheduled maintenance downtime. To address these problems we developed an on-the-fly kernel updating system that enables commodity operating systems to gain adaptive and mutative capabilities without kernel recompilation or reboot. Our system, DynAMOS, employs a novel and efficient dynamic code instrumentation technique termed adaptive function cloning. Execution flow can be switched adaptively among multiple editions of functions, possibly concurrently running. This approach becomes the foundation for dynamic replacement of non-quiescent kernel subsystems when the timeliness of an update depends on synchronization of multiple kernel paths. We illustrate our experience by dynamically updating core subsystems of the Linux kernel.

REFERENCES

• 1: J. Appavoo , K. Hui , C. A. N. Soules , R. W. Wisniewski , D. M. Da Silva , O. Krieger , M. A. Auslander , D. J. Edelsohn , B. Gamsa , G. R. Ganger , P. McKenney , M. Ostrowski , B. Rosenburg , M. Stumm , J. Xenidis, Enabling autonomic behavior in systems software with hot swapping, IBM Systems Journal, v.42 n.1, p.60-76, January 2003
• 2: Andrew Baumann , Gernot Heiser , Jonathan Appavoo , Dilma Da Silva , Orran Krieger , Robert W. Wisniewski , Jeremy Kerr, Providing dynamic update in an operating system, Proceedings of the USENIX Annual Technical Conference 2005 on USENIX Annual Technical Conference, p.32-32, April 10-15, 2005, Anaheim, CA
• 3: Bryan M. Cantrill , Michael W. Shapiro , Adam H. Leventhal, Dynamic instrumentation of production systems, Proceedings of the USENIX Annual Technical Conference 2004 on USENIX Annual Technical Conference, p.2-2, June 27-July 02, 2004, Boston, MA
• 4: Cowan, C., Autrey, T., Krasic, C., Pu, C., and Walpole, J. Fast concurrent dynamic linking for an adaptive operating system, 1996.
• 5: David J. Pearce. Instrumenting the Linux Kernel, MS thesis, 2000.
• 6: Michael William Hicks , Scott M. Nettles, Dynamic software updating, University of Pennsylvania, Philadelphia, PA, 2001
• 7: Michael Hicks , Jonathan T. Moore , Scott Nettles, Dynamic software updating, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.13-23, June 2001, Snowbird, Utah, United States
• 8: Hollingsworth, J. K., Miller, B. P., and Cargille, J. Dynamic program instrumentation for scalable performance tools. 1994 Scalable High Performance Computing (May 1994).
• 9: Galen Hunt , Doug Brubacher, Detours: binary interception of Win32 functions, Proceedings of the 3rd conference on USENIX Windows NT Symposium, p.14-14, July 12-15, 1999, Seattle, Washington
• 10: James R. Larus , Eric Schnarr, EEL: machine-independent executable editing, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.291-300, June 18-21, 1995, La Jolla, California, United States
• 11: Insup Lee, Dymos: a dynamic modification system, The University of Wisconsin - Madison, 1983
• 12: Linus Torvalds and William Lee Irwin III. Make pipe data be a circular list of pages. LWN.net (January 2005).
• 13: Chi-Keung Luk , Robert Cohn , Robert Muth , Harish Patil , Artur Klauser , Geoff Lowney , Steven Wallace , Vijay Janapa Reddi , Kim Hazelwood, Pin: building customized program analysis tools with dynamic instrumentation, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 14: Maebe, J., and Bosschere, K. D. Instrumenting self-modifying code. In Proceedings of the Fifth International Workshop on Automated Debugging (AADEBUG 2003) (September 2003).
• 15: Maebe, J., Ronsse, M., and Bosschere, K. D. Diota: Dynamic instrumentation, optimization and transformation of applications. In Compendium of Workshops and Tutorials held in conjuction with PACT '02 (2002).
• 16: Maebe, J., Ronsse, M., and Bosschere, K. D. Instrumenting JVMs at the machine code level. In 3rd PA3CT-symposium (September 2003).
• 17: Iulian Neamtiu , Michael Hicks , Gareth Stoyle , Manuel Oriol, Practical dynamic software updating for C, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 18: David J. Pearce , Paul H. J. Kelly , Tony Field , Uli Harder, GILK: A Dynamic Instrumentation Tool for the Linux Kernel, Proceedings of the 12th International Conference on Computer Performance Evaluation, Modelling Techniques and Tools, p.220-226, April 14-17, 2002
• 19: Kyung Dong Ryu , Jeffrey K. Hollingsworth, Linger Longer: fine-grain cycle stealing for networks of workstations, Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM), p.1-12, November 07-13, 1998, San Jose, CA
• 20: Ryu, K. D., Pachapurkar, N., and Fong, L. L. Adaptive memory paging for efficient gang scheduling of parallel applications. In IPDPS 2004 (April 2004).
• 21: M. Seltzer , C. Small, Self-Monitoring and Self-Adapting Operating Systems, Proceedings of the 6th Workshop on Hot Topics in Operating Systems (HotOS-VI), p.124, May 05-06, 1997
• 22: Srivastava, A., Edwards, A., and Vo, H. Vulcan: Binary transformation in a distributed environment. Tech. Rep MSR-TR-2001-50, April 2001.
• 23: Amitabh Srivastava , Alan Eustace, ATOM: a system for building customized program analysis tools, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.196-205, June 20-24, 1994, Orlando, Florida, United States
• 24: Ariel Tamches , Barton P. Miller, Fine-grained dynamic instrumentation of commodity operating system kernels, Proceedings of the third symposium on Operating systems design and implementation, p.117-130, February 1999, New Orleans, Louisiana, United States

INDEX TERMS

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

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection

General Terms:
Algorithms, Design, Reliability, Security

Keywords:
DynAMOS, adaptive operating system, dynamic instrumentation, dynamic software updates, function cloning