Memory overflow protection for embedded systems using run-time checks, reuse and compression

ABSTRACT

Out-of-memory errors are a serious source of unreliability in most embedded systems. Applications run out of main memory because of the frequent difficulty of estimating the memory requirement before deployment, either because it depends on input data, or because certain language features prevent estimation. The typical lack of disks and virtual memory in embedded systems has two serious consequences when an out-of-memory error occurs. First, there is no swap space for the application to grow into, and the system crashes. Second, since protection from virtual memory is usually absent, the fact that a segment has exceeded its bounds is not even detected and hence no pre-crash remedial action is possible.This work improves system reliability in two ways. First it proposes a low-overhead system of run-time checks by which the out-of-memory errors are detected just before they will happen, by using carefully optimized compiler-inserted run-time check code. Such error detection enables the designer to incorporate system-specific remedial action, such as transfer to manual control, shutting down of non-critical tasks, or other actions. Second, this work proposes five related techniques that can grow the stack or heap segment after it is out of memory, into previously un-utilized space such as dead variables and space freed by compressed live variables. These techniques can avoid the out-of-memory error if the extra space recovered is enough to complete execution.Results from our benchmarks show that the overheads from the system of run-time checks for detecting memory overflow are extremely low: the run-time and code-size overheads are 1.1% and 0.09% on average. When the reuse functionality is included, the run-time and code-size overheads increase to only 3.2%and 2.33%, but the method is able to grow the stack or heap beyond its overflow by an amount that ranges from 0.7% to 93.5% of the combined stack and heap size.

REFERENCES

• 1: High availability design for embedded systems. Technical report, Wind River, Inc. http://www.windriver.com/-whitepapers/high availability design.html.
• 2: Andrew W. Appel, Modern compiler implementation in Java, Cambridge University Press, New York, NY, 1997
• 3: Atmel Microcontrollers based on 8051 Architecture. http://www.atmel.com/products/8051.
• 4: Joel F. Bartlett. Compacting Garbage Collection with Ambiguous Roots. Technical report, DEC Western Research Laboratory, Palo Alto, CA, February 1988.
• 5: Rob von Behren , Jeremy Condit , Feng Zhou , George C. Necula , Eric Brewer, Capriccio: scalable threads for internet services, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 6: Hans-Juergen Boehm , Mark Weiser, Garbage collection in an uncooperative environment, Software—Practice & Experience, v.18 n.9, p.807-820, September 1988 [doi>10.1002/spe.4380180902]
• 7: D. Brylow, N. Damgaard, and J. Palsberg. Stack-size Estimation for Interrupt-driven Microcontrollers. Technical report, Purdue University, June 2000. http://www.brics.dk/ damgaard/Download/zilog-test.pdf.
• 8: G. Chen , R. Shetty , M. Kandemir , N. Vijaykrishnan , M. J. Irwin , M. Wolczko, Tuning Garbage Collection in an Embedded Java Environment, Proceedings of the 8th International Symposium on High-Performance Computer Architecture, p.92, February 02-06, 2002
• 9: Manuvir Das, Unification-based pointer analysis with directional assignments, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.35-46, June 18-21, 2000, Vancouver, British Columbia, Canada
• 10: Amer Diwan , J. Eliot B. Moss , Kathryn S. McKinley, Simple and effective analysis of statically-typed object-oriented programs, Proceedings of the 11th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.292-305, October 06-10, 1996, San Jose, California, United States
• 11: Document No. ARM DDI 0084D, ARM Ltd. ARM7TDMI-S Data sheet, October 1998.
• 12: Michael Durrant. Running Linux on low cost, low power MMU-less processors. August 2000. http://www.linuxdevices.com/articles/AT6245686197.html.
• 13: J. Engblom, Static Properties of Commercial Embedded Real-Time Programs, and Their Implication for Worst-Case Execution Time Analysis, Proceedings of the Fifth IEEE Real-Time Technology and Applications Symposium, p.46, June 02-04, 1999
• 14: M. Game and A. Booker. Codepack: Code compression for PowerPC processors. MicroNews 5(1), 1999.
• 15: John L. Hennessy , David A. Patterson, Computer architecture: a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 02
• 16: Intel i960Sx 32-bit Microprocessor. Intel Corporation. http://www.intel.com/design/i960/documentation/docs sx.htm.
• 17: David Kleidermacher and Mark Griglock. Safety-Critical Operating Systems. Embedded Systems Programming, 14(10), September 2001. http://www.embedded.com/story/OEG20010829S0055.
• 18: Rafael C. Krapf , Júlio C. B. Mattos , Gustavo Spellmeier , Luigi Carro, A Study on a Garbage Collector for Embedded Applications, Proceedings of the 15th symposium on Integrated circuits and systems design, p.127, September 09-14, 2002
• 19: Sergei Y. Larin , Thomas M. Conte, Compiler-driven cached code compression schemes for embedded ILP processors, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.82-92, November 16-18, 1999, Haifa, Israel
• 20: Doug Lea. A Memory Allocator. April 2000. http://gee.cs.oswego.edu/dl/html/malloc.html.
• 21: C.D. Lo. The Design of a Self-Maintained Memory Module for Real-Time Systems. In The 3rd IEEE International Workshop on System-on-Chip for Real-Time Applications, Alberta, Canada, July 2003. IEEE.
• 22: Windows CE.NET. Microsoft Corporation. http://www.microsoft.com/embedded/ce.net/default.aspx.
• 23: Motorola. M68000 User's Manual. Prentice Hall, Englewood Cliffs, NJ.
• 24: M-CORE - MMC2001 Reference Manual. Motorola Corporation, 1998. http://www.motorola.com/SPS/-MCORE/info documentation.htm.
• 25: George Neville-Neil, Programming Without A Net, Queue, v.1 n.2, April 2003 [doi>10.1145/644254.644264]
• 26: Patrik Persson, Live memory analysis for garbage collection in embedded systems, Proceedings of the ACM SIGPLAN 1999 workshop on Languages, compilers, and tools for embedded systems, p.45-54, May 05-05, 1999, Atlanta, Georgia, United States
• 27: Wind River. High Availability Design for Embedded Systems. http://www.windriver.com/whitepapers/-highavailability design.html.
• 28: Matthew Simpson, Surupa Biswas, and Rajeev Barua. Analysis of Compression Algorithms for Program Data. Technical report, U. of Maryland, ECE department, August 2003. http://www.ece.umd.edu/ barua/matt-compress-tr.pdf.
• 29: David Salomon , D. Salomon, Data Compression: The Complete Reference, Springer-Verlag New York, Inc., Secaucus, NJ, 2000
• 30: Bjarne Steensgaard, Points-to analysis in almost linear time, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.32-41, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237727]
• 31: KRISHNAN SUNDARESAN , NIHAR R. MAHAPATRA, Code Compression Techniques for Embedded Systems and Their Effectiveness, Proceedings of the IEEE Computer Society Annual Symposium on VLSI (ISVLSI'03), p.262, February 20-21, 2003
• 32: MSP430 Ultra-Low-Power MCUs. Texas Instruments, 2004. http://focus.ti.com/lit/ml/slab034g/slab034g.pdf.
• 33: Sumesh Udayakumaran , Rajeev Barua, Compiler-decided dynamic memory allocation for scratch-pad based embedded systems, Proceedings of the 2003 international conference on Compilers, architecture and synthesis for embedded systems, October 30-November 01, 2003, San Jose, California, USA [doi>10.1145/951710.951747]
• 34: Paul R. Wilson, Scott F. Kaplan, and Yannis Smaragdakis. The case for compressed caching in virtual memory systems. In Proceedings of the USENIX Annual Technical Conference, Monterey, CA, June 1999.
• 35: Youtao Zhang , Rajiv Gupta, Data Compression Transformations for Dynamically Allocated Data Structures, Proceedings of the 11th International Conference on Compiler Construction, p.14-28, April 08-12, 2002

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors

Additional Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
      D.4.5 Reliability

Keywords:
data compression, heap overflow, out-of-memory errors, reliability, reuse, runtime checks, stack overflow