Atomic heap transactions and fine-grain interrupts

ABSTRACT

Languages such as Java, ML, Scheme, and Haskell provide automatic storage management, that is, garbage collection. The two fundamental operations performed on a garbage-collected heap are "allocate" and "collect." Because the heap is in an inconsistent state during these operations, they must be performed atomically. Otherwise, a heap client might access the heap during a time when its fundamental invariants do not hold, corrupting the heap.Standard techniques for providing this atomicity guarantee have large latencies and other performance problems that impede their application in high-performance, interruptladen, thread-based systems applications. In particular, the standard techniques prevent thread schedulers from switching threads on VM page faults.We cast the space of possible implementations into a general taxonomy, and describe a new technique that provides a simple, low-overhead, low-latency interlock. We have implemented this technique in a version of SML/NJ, and, because of its applicability to thread-based systems, are currently implementing it in the scheduler of our raw-hardware SML-based kernel, ML/OS. Our technique can be extended to provide other atomic sequences besides storage allocation.

REFERENCES

• Diwan+: Amer Diwan , Eliot Moss , Richard Hudson, Compiler support for garbage collection in a statically typed language, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.273-282, June 15-19, 1992, San Francisco, California, United States
• Feeley: Marc Feeley, Polling efficiently on stock hardware, Proceedings of the conference on Functional programming languages and computer architecture, p.179-187, June 09-11, 1993, Copenhagen, Denmark [doi>10.1145/165180.165205]
• Herlihy: 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]
• JavaGC: James M. Stichnoth , Guei-Yuan Lueh , Michał Cierniak, Support for garbage collection at every instruction in a Java compiler, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.118-127, May 01-04, 1999, Atlanta, Georgia, United States
• LockFree: Andrew W. Appel. To the best of our knowledge, this very clever technique is due to Andrew Appel and remains unpublished. One of us (Shivers) saw Andrew sketch this approach out on a blackboard in the late eighties, point out the critical trivial-abort property, and state that it had been implemented and subsequently abandoned. But no description of the technique can be found in any of Appel's published works, and when pressed, he becomes evasive, claims poor memory, and denies any involvement with the covert manipulation of autonomous processor-states. We note without further comment his long-standing support by powerful Department of Defense agencies.
• ML/OS: Bryan Ford , Godmar Back , Greg Benson , Jay Lepreau , Albert Lin , Olin Shivers, The Flux OSKit: a substrate for kernel and language research, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.38-51, October 05-08, 1997, Saint Malo, France
• ML-threads: J. Gregory Morrisett , Andrew Tolmach, Procs and locks: a portable multiprocessing platform for standard ML of New Jersey, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.198-207, May 19-22, 1993, San Diego, California, United States
• Modula-3: Greg Nelson, Systems programming with Modula-3, Prentice-Hall, Inc., Upper Saddle River, NJ, 1991
• MLRisc: Little has been published on Lal George's MLRisc code-generator compiler back-end. However, on-.line documen'~ation can be found at http://cm.bell-labs.com/cm/cs/ what /smln j/doc/MLRISC/index, html.
• Orbit: David Kranz , Norman Adams , Richard Kelsey , Jonathan Rees , Paul Hudak , James Philbin, ORBIT: an optimizing compiler for scheme, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.219-233, June 25-27, 1986, Palo Alto, California, United States
• ParaCaml: Damien Doligez , Xavier Leroy, A concurrent, generational garbage collector for a multithreaded implementation of ML, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.113-123, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158611]
• PCC: George C. Necula , Peter Lee, Safe kernel extensions without run-time checking, Proceedings of the second USENIX symposium on Operating systems design and implementation, p.229-243, October 29-November 01, 1996, Seattle, Washington, United States
• PCLSR: Alan Bawden. "PCLSRing: Keeping process state modular." Unpublished memo, available via anonymous FTP as ftp://ftp, ai.mit. e du/pub / al an/pc 1 st. memo.
• Qua: Henry Massalin, Synthesis: an efficient implementation of fundamental operating system services, Columbia University, New York, NY, 1992
• RTC-GC: A. W. Appel , J. R. Ellis , K. Li, Real-time concurrent collection on stock multiprocessors, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.11-20, June 20-24, 1988, Atlanta, Georgia, United States
• SML/NJ: Andrew W. Appel and David B. MacQueen. Standard ML of New Jersey. In Third International symposium on Programming Lan.. guage Implementation and Logic Program.- ming, LNCS 528, pages 1-13, Martin Wirsing, editor, August 1991. Springex-Verlag, New York.
• Spur: Mark Hill , Susan Eggers , Jim Larus , George Taylor , Glenn Adams , B. K. Bose , Garth Gibson , Paul Hansen , Jon Keller , Shing Kong , Corinna Lee , Daebum Lee , Joan Pendleton , Scott Ritchie , David Wood , Ben Zorn , Paul Hilfinger , Dave Hodges , Randy Katz , John Ousterhout , Dave Patterson, Design decisions in SPUR, Computer, v.19 n.11, p.8-22, Nov. 1986 [doi>10.1109/MC.1986.1663096]
• T: Jonathan A. Rees , Norman I. Adams IV, T: a dialect of Lisp or LAMBDA: The ultimate software tool, Proceedings of the 1982 ACM symposium on LISP and functional programming, p.114-122, August 15-18, 1982, Pittsburgh, Pennsylvania, United States [doi>10.1145/800068.802142]
• Unimutex: Brian N. Bershad , David D. Redell , John R. Ellis, Fast mutual exclusion for uniprocessors, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.223-233, October 12-15, 1992, Boston, Massachusetts, United States
• Wilson: Paul R. Wilson, Uniprocessor Garbage Collection Techniques, Proceedings of the International Workshop on Memory Management, p.1-42, September 17-19, 1992

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Allocation/deallocation strategies

General Terms:
Languages, Management, Theory