Dynamic memory management for programmable devices

ABSTRACT

The paper presents the design and implementation of a novel dynamic memory-management scheme for ESP---a language for programmable devices. The firmware for programmable devices has to be fast and reliable. To support high performance, ESP provides an explicit memory-management interface that can be implemented efficiently. To ensure reliability, ESP uses a model checker to verify memory safety.The VMMC firmware is used as a case study to evaluate the effectiveness of this memory-management scheme. We find that the Spin model checker is able to exhaustively verify memory safety of the firmware; the largest process took 67.6 seconds and used 34.45 Mbytes of memory to verify. We also find that the runtime overhead to maintain the reference counts is small; the additional overhead accounts for 7.35% of the total message processing cost (in the worst case) over a malloc/free interface.

REFERENCES

• 1: Anurag Acharya , Mustafa Uysal , Joel Saltz, Active disks: programming model, algorithms and evaluation, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.81-91, October 02-07, 1998, San Jose, California, United States
• 2: Raoul A. F. Bhoedjang , Tim Rühl , Henri E. Bal, User-Level Network Interface Protocols, Computer, v.31 n.11, p.53-60, November 1998 [doi>10.1109/2.730737 ]
• 3: Angelos Bilas , Cheng Liao , Jaswinder Pal Singh, Using network interface support to avoid asynchronous protocol processing in shared virtual memory systems, Proceedings of the 26th annual international symposium on Computer architecture, p.282-293, May 01-04, 1999, Atlanta, Georgia, United States
• 4: Nanette J. Boden , Danny Cohen , Robert E. Felderman , Alan E. Kulawik , Charles L. Seitz , Jakov N. Seizovic , Wen-King Su, Myrinet: A Gigabit-per-Second Local Area Network, IEEE Micro, v.15 n.1, p.29-36, February 1995 [doi>10.1109/40.342015 ]
• 5: M. by Ben Zorn. Debugging Tools for Dynamic Storage Allocation and Memory Management. http://www.cs.colorado.edu/homes/zorn/public_html/breakMallocDebug.html, 2001
• 6: Y. Chen, S. N. Damianakis, S. Kumar, X. Yu, and K. Li. Porting a User-Level Communication Architecture to NT: Experiences and Performance. In Usenix Windows NT Symposium, 1999
• 7: Yoo C. Chung , Soo-Mook Moon , Kemal Ebcioğlu , Dan Sahlin, Reducing sweep time for a nearly empty heap, Proceedings of the 27th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.378-389, January 19-21, 2000, Boston, MA, USA [doi>10.1145/325694.325744]
• 8: Robert DeLine , Manuel Fähndrich, Enforcing high-level protocols in low-level software, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.59-69, June 2001, Snowbird, Utah, United States
• 9: C. Dubnicki, A. Bilas, Y. Chen, S. Damianakis, and K. Li. VMMC-2: Efficient Support for Reliable, Connection-Oriented Communication. In Hot Interconnects, 1997
• 10: Cezary Dubnicki , Angelos Bilas , Kai Li, Design and Implementation of Virtual Memory-Mapped Communication on Myrinet, Proceedings of the 11th International Symposium on Parallel Processing, p.388, April 01-05, 1997
• 11: David Evans, Static detection of dynamic memory errors, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.44-53, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 12: Dan Grossman , Greg Morrisett , Trevor Jim , Michael Hicks , Yanling Wang , James Cheney, Region-based memory management in cyclone, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 13: R. Hastings and B. Joyce. Purify: Fast Detection of Memory Leaks and Access Errors. In Winter USENIX Conference, 1992
• 14: C. A. R. Hoare, Communicating sequential processes, Communications of the ACM, v.21 n.8, p.666-677, Aug. 1978 [doi>10.1145/359576.359585]
• 15: Gerard J. Holzmann, The Model Checker SPIN, IEEE Transactions on Software Engineering, v.23 n.5, p.279-295, May 1997 [doi>10.1109/32.588521 ]
• 16: S. Kumar. ESP: A Language for Programmable Devices. Technical report, Princeton University, Department of Computer Science Department, January 2002
• 17: Sanjeev Kumar , Yitzhak Mandelbaum , Xiang Yu , Kai Li, ESP: a language for programmable devices, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.309-320, June 2001, Snowbird, Utah, United States
• 18: Scott Pakin , Mario Lauria , Andrew Chien, High performance messaging on workstations: Illinois fast messages (FM) for Myrinet, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.55-es, December 04-08, 1995, San Diego, California, United States [doi>10.1145/224170.224360]
• 19: Mads Tofte , Jean-Pierre Talpin, Implementation of the typed call-by-value λ-calculus using a stack of regions, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.188-201, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.177855]
• 20: T. von Eicken , A. Basu , V. Buch , W. Vogels, U-Net: a user-level network interface for parallel and distributed computing (includes URL), Proceedings of the fifteenth ACM symposium on Operating systems principles, p.40-53, December 03-06, 1995, Copper Mountain, Colorado, United States
• 21: Thorsten von Eicken , David E. Culler , Seth Copen Goldstein , Klaus Erik Schauser, Active messages: a mechanism for integrated communication and computation, Proceedings of the 19th annual international symposium on Computer architecture, p.256-266, May 19-21, 1992, Queensland, Australia
• 22: Thorsten von Eicken , Werner Vogels, Evolution of the Virtual Interface Architecture, Computer, v.31 n.11, p.61-68, November 1998 [doi>10.1109/2.730738 ]
• 23: D. Wagner, J. S. Foster, E. A. Brewer, and A. Aiken. A First Step Towards Automated Detection of Buffer Overrun Vulnerabilities. In Network and Distributed System Security Symposium, 2000
• 24: Simon Walton , Anne Hutton , Joe Touch, High-Speed Data Paths in Host-Based Routers, Computer, v.31 n.11, p.46-52, November 1998 [doi>10.1109/2.730736 ]
• 25: Randolph Y. Wang , Thomas E. Anderson , David A. Patterson, Virtual log based file systems for a programmable disk, Proceedings of the third symposium on Operating systems design and implementation, p.29-43, February 1999, New Orleans, Louisiana, United States
• 26: Paul R. Wilson, Uniprocessor Garbage Collection Techniques, Proceedings of the International Workshop on Memory Management, p.1-42, September 17-19, 1992
• 27: Steven Cameron Woo , Moriyoshi Ohara , Evan Torrie , Jaswinder Pal Singh , Anoop Gupta, The SPLASH-2 programs: characterization and methodological considerations, Proceedings of the 22nd annual international symposium on Computer architecture, p.24-36, June 22-24, 1995, S. Margherita Ligure, Italy

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Dynamic storage management

General Terms:
Design, Languages, Performance

Keywords:
dynamic memory management, model checking, programmable devices, reference counting