Experience with safe manual memory-management in cyclone

ABSTRACT

The goal of the Cyclone project is to investigate type safety for low-level languages such as C. Our most difficult challenge has been providing programmers control over memory management while retaining type safety. This paper reports on our experience trying to integrate and effectively use two previously proposed, type-safe memory management mechanisms: statically-scoped regions and unique pointers. We found that these typing mechanisms can be combined to build alternative memory-management abstractions, such as reference counted objects and arenas with dynamic lifetimes, and thus provide a flexible basis. Our experience---porting C programs and building new applications for resource-constrained systems---confirms that experts can use these features to improve memory footprint and sometimes to improve throughput when used instead of, or in combination with, conservative garbage collection.

REFERENCES

• 1: Peter Achten and Rinus Plasmeijer. The ins and outs of Clean I/O. Journal of Functional Programming, 5(1):81--110, 1995.
• 2: Alexander Aiken , Manuel Fähndrich , Raph Levien, Better static memory management: improving region-based analysis of higher-order languages, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.174-185, June 18-21, 1995, La Jolla, California, United States
• 3: Alex Aiken , Jeffrey S. Foster , John Kodumal , Tachio Terauchi, Checking and inferring local non-aliasing, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 4: Henry G. Baker, Lively linear Lisp: “look ma, no garbage!”, ACM SIGPLAN Notices, v.27 n.8, p.89-98, Aug. 1992 [doi>10.1145/142137.142162]
• 5: Gregory Bellella, editor. The Real-Time Specification for Java. Addison-Wesley, 2000.
• 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: Chandrasekhar Boyapati , Alexandru Salcianu , William Beebee, Jr. , Martin Rinard, Ownership types for safe region-based memory management in real-time Java, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 8: John Boyland, Alias burying: unique variables without destructive reads, Software—Practice & Experience, v.31 n.6, p.533-553, May 2001 [doi>10.1002/spe.370]
• 9: Dave Clarke and Tobias Wrigstad. External uniqueness is unique enough. In European Conference on Object-Oriented Programming (ECOOP), pages 176--200, July 2003.
• 10: Cyclone, version 0.8. Available at http://www.eecs.harvard.edu/~greg/cyclone/.
• 11: 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
• 12: Manuel Fahndrich , Robert DeLine, Adoption and focus: practical linear types for imperative programming, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 13: Matthew Fluet and Daniel Wang. Implementation and performance evaluation of a safe runtime system in Cyclone. In Informal Proceedings of the SPACE 2004 Workshop, January 2004.
• 14: David Gay , Alex Aiken, Language support for regions, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.70-80, June 2001, Snowbird, Utah, United States
• 15: 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
• 16: Niels Hallenberg , Martin Elsman , Mads Tofte, Combining region inference and garbage collection, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 17: Douglas E. Harms , Bruce W. Weide, Copying and Swapping: Influences on the Design of Reusable Software Components, IEEE Transactions on Software Engineering, v.17 n.5, p.424-435, May 1991 [doi>10.1109/32.90445]
• 18: Christopher Kirk Hawblitzel , Thorsten Von Eicken, Adding operating system structure to language-based protection, 2000
• 19: Fritz Henglein , Henning Makholm , Henning Niss, A direct approach to control-flow sensitive region-based memory management, Proceedings of the 3rd ACM SIGPLAN international conference on Principles and practice of declarative programming, p.175-186, September 05-07, 2001, Florence, Italy [doi>10.1145/773184.773203]
• 20: Maurice Herlihy, Wait-free synchronization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.1, p.124-149, Jan. 1991 [doi>10.1145/114005.102808]
• 21: Matthew Hertz and Emery Berger. Automatic vs. explicit memory management: Settling the performance debate. Technical Report CS TR-04-17, University of Massachussetts Department of Computer Science, 2004.
• 22: Michael Hicks, Adithya Nagajaran, and Robbert van Renesse. MediaNet: User-defined adaptive scheduling for streaming data. In Proc. IEEE Conference on Open Architectures and Network Programming (OPENARCH), pages 87--96, April 2003.
• 23: Trevor Jim , J. Greg Morrisett , Dan Grossman , Michael W. Hicks , James Cheney , Yanling Wang, Cyclone: A Safe Dialect of C, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.275-288, June 10-15, 2002
• 24: Doug Lea. A memory allocator. http://gee.cs.oswego.edu/dl/html/malloc.html.
• 25: David Mazières, A Toolkit for User-Level File Systems, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.261-274, June 25-30, 2001
• 26: Mike Muuss. The story of TTCP. http://ftp.arl.mil/~mike/ttcp.html.
• 27: Niels Provos. libevent --- an event notification library. http://www.monkey.org/provos/libevent/.
• 28: Frederick Smith , David Walker , J. Gregory Morrisett, Alias Types, Proceedings of the 9th European Symposium on Programming Languages and Systems, p.366-381, April 02, 2000
• 29: Tachio Terauchi and Alex Aiken. Memory management with use-counted regions. Technical Report UCB//CSD-04-1314, University of California, Berkeley, March 2004.
• 30: Mads Tofte, Lars Birkedal, Martin Elsman, Niels Hallenberg, Tommy Højfel Olesen, and Peter Sestoft. Programming with regions in the ML Kit (for version 4. Technical report, IT University of Copenhagen, September 2001.
• 31: Mads Tofte , Jean-Pierre Talpin, Region-based memory management, Information and Computation, v.132 n.2, p.109-176, Feb. 1, 1997 [doi>10.1006/inco.1996.2613]
• 32: Philip Wadler. Linear types can change the world! In Programming Concepts and Methods, April 1990. IFIP TC 2 Working Conference.
• 33: David Walker , Karl Crary , Greg Morrisett, Typed memory management via static capabilities, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.4, p.701-771, July 2000 [doi>10.1145/363911.363923]
• 34: David Walker , J. Gregory Morrisett, Alias Types for Recursive Data Structures, Selected papers from the Third International Workshop on Types in Compilation, p.177-206, September 21, 2000
• 35: David Walker , Kevin Watkins, On regions and linear types (extended abstract), Proceedings of the sixth ACM SIGPLAN international conference on Functional programming, September 03-05, 2001, Florence, Italy
• 36: Daniel C. Wang , Andrew W. Appel, Type-preserving garbage collectors, Proceedings of the 28th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.166-178, January 2001, London, United Kingdom
• 37: Hongwei Xi and Frank Pfenning. Dependent types in practical programming. pages 214--227, January 1999.
• 38: Benjamin Zorn, The measured cost of conservative garbage collection, Software—Practice & Experience, v.23 n.7, p.733-756, July 1993 [doi>10.1002/spe.4380230704]

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Polymorphism

General Terms:
Experimentation, Languages, Reliability

Keywords:
cyclone, memory management, memory safety, regions, unique pointers