skip to main content
10.1145/1023833.1023872acmconferencesArticle/Chapter ViewAbstractPublication PagesesweekConference Proceedingsconference-collections
Article

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

Published: 22 September 2004 Publication History

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 and Maia Ginsburg. Modern Compiler Implementation in C. Cambridge Univ. Press, January 1998.
[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 Necula, and Eric Brewer. Cappricio: Scalable Threads for Internet Services. In Proc., ACM Symposium on Operating Systems Principles (SOSP), October 2003.
[6]
H-J. Boehm and M. Weiser. Garbage Collection in an Uncooperative Environment. Software-Practice and Experience, pages 807--820, September 1988.
[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, and M.J. Irwin. Tuning Garbage Collection in an Embedded Java Environment. In Eighth International Symposium on High-Performance Computer Architecture (HPCA'02), pages 92--106, Boston, Massachusettes, February 2002. IEEE.
[9]
Manuvir Das. Unification-based pointer analysis with directional assignments. In Proceedings of the SIGPLAN '00 Conference on Program Language Design and Implementation, pages 35--46, Vancouver, BC, June 2000.
[10]
Amer Diwan, J. Eliot Moss, and Kathryn McKinley. Simple and effective analysis of statically-typed object-oriented programs. In Proc. of the 11th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, pages 292--305. ACM Press, 1996.
[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]
Jakob Engblom. Static properties of commercial embedded real-time programs and their implication for worst-case execution time analysis. In Proc. of the IEEE Real-Time Technology & Applications Symposium (RTAS), June 1999.
[14]
M. Game and A. Booker. Codepack: Code compression for PowerPC processors. MicroNews 5(1), 1999.
[15]
John Hennessy and David Patterson. Computer Architecture: A Quantitative Approach. Morgan Kaufmann, Palo Alto, CA, third edition, 2002.
[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, Jlio C. B. Mattos, Gustavo Spellmeier, and Luigi Carro. A Study on a Garbage Collector for Embedded Applications. In 15th Symposium on Integrated Circuits and Systems Design, pages 127--134, Porto Alegre, Brazil, September 2002. IEEE.
[19]
Sergei Y. Larin and Thomas M. Conte. Compiler-Driven Cached Code Compression Schemes for Embedded ILP Processors. In 32nd Int'l Symposium on Microarchitecture, pages 82--92, Haifa, Israel, November 1999. IEEE.
[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 V. Neville-Neil. Programming Without A Net. ACM Queue: Tomorrow's Computing Today, 1(2):16--23, April 2003.
[26]
Patrik Persson. Live memory analysis for garbage collection in embedded systems. In Proceedings of the ACM SIGPLAN 1999 workshop on Languages, compilers, and tools for embedded systems, pages 45--54. ACM Press, 1999.
[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 Solomon. Data Compression: The Complete Reference. Springer-Verlag Inc., New York, 2000.
[30]
Bjarne Steensgaard. Points-to analysis in almost linear time. In Symposium on Principles of Programming Languages (POPL), St. Petersburg Beach, FL, January 1996.
[31]
Krishnan Sundaresan and Nihar R. Mahapatra. Code Compression Techniques for Embedded Systems and Their Effectiveness . In IEEE Computer Society Annual Symposium on VLSI (ISVLSI'03), pages 262--263, Tampa, Florida, February 2003. IEEE.
[32]
MSP430 Ultra-Low-Power MCUs. Texas Instruments, 2004. http://focus.ti.com/lit/ml/slab034g/slab034g.pdf.
[33]
Sumesh Udayakumaran and Rajeev Barua. Compiler-decided dynamic memory allocation for scratch-pad based embedded systems. In Proceedings of the international conference on Compilers, architectures and synthesis for embedded systems, pages 276--286. ACM Press, 2003.
[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 and Rajiv Gupta. Data Compression Transformations for Dynamically Allocated Data Structures. In Proceedings of the International Conference on Compiler Construction LNCS 2304, pages 14--28, April 2002.

Cited By

View all
  • (2019)Secure Industrial Internet of Things Critical Infrastructure Node DesignIEEE Internet of Things Journal10.1109/JIOT.2019.29032426:5(8021-8037)Online publication date: Oct-2019
  • (2017)StackMMU: Dynamic stack sharing for embedded systems2017 22nd IEEE International Conference on Emerging Technologies and Factory Automation (ETFA)10.1109/ETFA.2017.8247614(1-9)Online publication date: Sep-2017
  • (2014)Proving the Absence of Stack OverflowsProceedings of the 33rd International Conference on Computer Safety, Reliability, and Security - Volume 866610.1007/978-3-319-10506-2_14(202-213)Online publication date: 10-Sep-2014
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
CASES '04: Proceedings of the 2004 international conference on Compilers, architecture, and synthesis for embedded systems
September 2004
324 pages
ISBN:1581138903
DOI:10.1145/1023833
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 September 2004

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. data compression
  2. heap overflow
  3. out-of-memory errors
  4. reliability
  5. reuse
  6. runtime checks
  7. stack overflow

Qualifiers

  • Article

Conference

CASES04

Acceptance Rates

Overall Acceptance Rate 52 of 230 submissions, 23%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 16 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2019)Secure Industrial Internet of Things Critical Infrastructure Node DesignIEEE Internet of Things Journal10.1109/JIOT.2019.29032426:5(8021-8037)Online publication date: Oct-2019
  • (2017)StackMMU: Dynamic stack sharing for embedded systems2017 22nd IEEE International Conference on Emerging Technologies and Factory Automation (ETFA)10.1109/ETFA.2017.8247614(1-9)Online publication date: Sep-2017
  • (2014)Proving the Absence of Stack OverflowsProceedings of the 33rd International Conference on Computer Safety, Reliability, and Security - Volume 866610.1007/978-3-319-10506-2_14(202-213)Online publication date: 10-Sep-2014
  • (2009)Eliminating the call stack to save RAMACM SIGPLAN Notices10.1145/1543136.154246144:7(60-69)Online publication date: 19-Jun-2009
  • (2009)Eliminating the call stack to save RAMProceedings of the 2009 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems10.1145/1542452.1542461(60-69)Online publication date: 19-Jun-2009
  • (2009)MEMMUACM Transactions on Embedded Computing Systems10.1145/1509288.15092958:3(1-33)Online publication date: 22-Apr-2009
  • (2007)Offline compression for on-chip ramACM SIGPLAN Notices10.1145/1273442.125077642:6(363-372)Online publication date: 10-Jun-2007
  • (2007)Offline compression for on-chip ramProceedings of the 28th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/1250734.1250776(363-372)Online publication date: 15-Jun-2007
  • (2006)Automated compile-time and run-time techniques to increase usable memory in MMU-less embedded systemsProceedings of the 2006 international conference on Compilers, architecture and synthesis for embedded systems10.1145/1176760.1176777(125-135)Online publication date: 22-Oct-2006
  • (2006)A software reproduction of virtual memory for deeply embedded systemsProceedings of the 6th international conference on Computational Science and Its Applications - Volume Part I10.1007/11751540_109(1000-1009)Online publication date: 8-May-2006
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media