Safe and timely updates to multi-threaded programs

ABSTRACT

Many dynamic updating systems have been developed that enable a program to be patched while it runs, to fix bugs or add new features. This paper explores techniques for supporting dynamic updates to multi-threaded programs, focusing on the problem of applying an update in a timely fashion while still producing correct behavior. Past work has shown that this tension of safety versus timeliness can be balanced for single-threaded programs. For multi-threaded programs, the task is more difficult because myriad thread interactions complicate understanding the possible program states to which a patch could be applied. Our approach allows the programmer to specify a few program points (e.g., one per thread) at which a patch may be applied, which simplifies reasoning about safety. To improve timeliness, a combination of static analysis and run-time support automatically expands these few points to many more that produce behavior equivalent to the originals. Experiments with thirteen realistic updates to three multi-threaded servers show that we can safely perform a dynamic update within milliseconds when more straightforward alternatives would delay some updates indefinitely.

REFERENCES

• 1: Gautam Altekar , Ilya Bagrak , Paul Burstein , Andrew Schultz, OPUS: online patches and updates for security, Proceedings of the 14th conference on USENIX Security Symposium, p.19-19, July 31-August 05, 2005, Baltimore, MD
• 2: Jeff Arnold , M. Frans Kaashoek, Ksplice: automatic rebootless kernel updates, Proceedings of the 4th ACM European conference on Computer systems, April 01-03, 2009, Nuremberg, Germany [doi>10.1145/1519065.1519085]
• 3: Andrew Baumann , Jonathan Appavoo , Robert W. Wisniewski , Dilma Da Silva , Orran Krieger , Gernot Heiser, Reboots are for hardware: challenges and solutions to updating an operating system on the fly, 2007 USENIX Annual Technical Conference on Proceedings of the USENIX Annual Technical Conference, p.1-14, June 17-22, 2007, Santa Clara, CA
• 4: Haibo Chen , Rong Chen , Fengzhe Zhang , Binyu Zang , Pen-Chung Yew, Live updating operating systems using virtualization, Proceedings of the 2nd international conference on Virtual execution environments, June 14-16, 2006, Ottawa, Ontario, Canada [doi>10.1145/1134760.1134767]
• 5: Haibo Chen , Jie Yu , Rong Chen , Binyu Zang , Pen-Chung Yew, POLUS: A POwerful Live Updating System, Proceedings of the 29th international conference on Software Engineering, p.271-281, May 20-26, 2007 [doi>10.1109/ICSE.2007.65]
• 6: Deepak Gupta , Pankaj Jalote , Gautam Barua, A Formal Framework for On-line Software Version Change, IEEE Transactions on Software Engineering, v.22 n.2, p.120-131, February 1996 [doi>10.1109/32.485222]
• 7: Tim Harris , Simon Marlow , Simon Peyton-Jones , Maurice Herlihy, Composable memory transactions, Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 15-17, 2005, Chicago, IL, USA [doi>10.1145/1065944.1065952]
• 8: Michael Hicks , Scott Nettles, Dynamic software updating, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.6, p.1049-1096, November 2005 [doi>10.1145/1108970.1108971]
• 9: K42. The K42 Project. http://www.research.ibm.com/K42/.
• 10: Insup Lee, Dymos: a dynamic modification system, The University of Wisconsin - Madison, 1983
• 11: Kristis Makris and Rida Bazzi. Multi-threaded dynamic software updates using stack reconstruction. In phUSENIX ATC, 2009.
• 12: Kristis Makris , Kyung Dong Ryu, Dynamic and adaptive updates of non-quiescent subsystems in commodity operating system kernels, Proceedings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems 2007, March 21-23, 2007, Lisbon, Portugal
• 13: Iulian Neamtiu. phPractical Dynamic Software Updating. PhD thesis, University of Maryland, College Park, August 2008.
• 14: Iulian Neamtiu and Michael Hicks. Safe and timely updates to multi-threaded programs. Technical report, UC Riverside, June 2009.
• 15: Iulian Neamtiu , Jeffrey S. Foster , Michael Hicks, Understanding source code evolution using abstract syntax tree matching, Proceedings of the 2005 international workshop on Mining software repositories, p.1-5, May 17-17, 2005, St. Louis, Missouri
• 16: 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
• 17: Iulian Neamtiu , Michael Hicks , Jeffrey S. Foster , Polyvios Pratikakis, Contextual effects for version-consistent dynamic software updating and safe concurrent programming, Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 07-12, 2008, San Francisco, California, USA
• 18: Polyvios Pratikakis , Jeffrey S. Foster , Michael Hicks, LOCKSMITH: context-sensitive correlation analysis for race detection, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 19: Stelios Sidiroglou , Sotiris Ioannidis , Angelos D. Keromytis, Band-aid patching, Proceedings of the 3rd workshop on on Hot Topics in System Dependability, p.6-es, June 26, 2007, Edinburgh, UK
• 20: C. Soules, J. Appavoo, K. Hui, et al. System support for online reconfiguration. In phUSENIX ATC, 2003.
• 21: Gareth Stoyle , Michael Hicks , Gavin Bierman , Peter Sewell , Iulian Neamtiu, Mutatis Mutandis: Safe and predictable dynamic software updating, ACM Transactions on Programming Languages and Systems (TOPLAS), v.29 n.4, p.22-es, August 2007 [doi>10.1145/1255450.1255455]
• 22: Suriya Subramanian , Michael Hicks , Kathryn S. McKinley, Dynamic software updates: a VM-centric approach, Proceedings of the 2009 ACM SIGPLAN conference on Programming language design and implementation, June 15-21, 2009, Dublin, Ireland
• 23: Jean-Pierre Talpin and Pierre Jouvelot. Polymorphic type, region and effect inference. phJFP, 2, 1992.
• 24: Chris Walton. phAbstract Machines for Dynamic Computation. PhD thesis, University of Edinburgh, 2001. ECS-LFCS-01-425.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Program analysis

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Reliability, availability, and serviceability

  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

General Terms:
Languages, Performance, Reliability

Keywords:
dynamic software updating, multi-threading, update safety, update timeliness