Article

Free access

Simple garbage-collector-safety

Author:

Hans-J. BoehmAuthors Info & Claims

PLDI '96: Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation

Pages 89 - 98

https://doi.org/10.1145/231379.231394

Published: 01 May 1996 Publication History

Abstract

A conservative garbage collector can typically be used with conventionally compiled programs written in C or C++. But two safety issues must be considered. First, the source code must not hide pointers from the garbage collector. This primarily requires stricter adherence to existing restrictions in the language definition. Second, we must ensure that the compiler will not perform transformations that invalidate this requirement.We argue that the same technique can be used to address both issues. We present an algorithm for annotating source or intermediate code to either check the validity of pointer arithmetic in the source, or to guarantee that under minimal, clearly defined assumptions about the compiler, the optimizer cannot "disguise" pointers. We discuss an implementation based on a preprocessor for the GNU C compiler (gcc), and give some measurements of program slow down.

References

[1]

Standard)(3.159-1989, American National Standard for Information Systems- Programming Language- C, American National Standards Institute, Inc.

[2]

Atkinson, Russ, Alan Demers, Carl Hauser, Christian Jacobi, Peter Kessler, and Mark Weiser, "Experiences Creating a Portable Cedar", Proceedings of the ACM SiGPLAN '89 Conference on Programming Language Design and Implementation, SIGPLAN Notices 24, 7 (July 1989), pp. 322-329.

Digital Library

[3]

Austin, Todd M., Scott E. Breach, and Gurindar S. Sohi, "Efficient Detection of all Pointer and Array Access Errors", Proceedings of the ACM SiGPLAN 94 Conference on Programming Language Design and Implementation, SIGPLAN Notices 29, 6 (June 1994), pp. 290-301.

Digital Library

[4]

Bartlett, Joel F. "Compacting garbage collection with ambiguous roots", Lisp Pointers 1, 6 (April-June 1988), lap. 3-12.

[5]

Bartlett, Joel F., Scheme-O C a Portable Scheme to-C Compiler, WRL Research Report 89/1, Digital Equipment Corporation Western Research Laboratory, January 1989.

[6]

Boehm, Hans-J., "Space Efficient Conservative Garbage Collection", Proceedings of the ACM SiGPLAN ~93 Conference on Programming Language Design and Implementation, SiGPLAN Notices 28, 6 (June 1993), pp. 197-206.

Digital Library

[7]

The SPARC scheduler is available from parcf~p.xerox.com:pub/gc/sched.tar. Z. It also operates in a GC-safe mode, along the lines of {BoehmChase92}.

[8]

An overview of our conservative garbage collector along with the source code can be accessed from ilia://parcftp.xerox.com/p u b / gc/gc.html.

[9]

Boehm, Hans-J, and David Chase, A Proposal for GC-Safe C Compilation, The Journal of C Language Translation 4, 2 (December, 1992), pp. 126-141. Also available (with the publishers permission) from parcftp.xerox.com:pub/gc/boecha, ps.Z.

[10]

Boehm, H., A. Demers, and S. Shenker,"Mostly Parallel Garbage Collection", Proceedings of the ACM SIGPLAN ~1 Conference on Programming Language Design and Implementation, SIGPLAN Notices 26, 6 (June 1991), pp. 157-164.

Digital Library

[11]

Boehm, Hans-J. and Mark Weiser, "Garbage collection in an uncooperative environment", Software Practice & Experience 18, 9 (Sept. 1988), pp. 807-820.

Digital Library

[12]

Diwan, Amer, Eliot Moss, Richard Hudson, "Compiler Support for Garbage Collection in a Static~y Typed Language", ACM SIGPLAN '92 Conference on Programming Language Design and Implementation, SIGPLAN Notices 27, 7 (July 1992), pp. 273-282.

Digital Library

[13]

Detlefs, David, A1 Dosser, and Benjamin Zorn, "Memory Allocation Costs in Large C and C + + Programs", University of Colorado, Boulder Technical Report CU-CS-665-93. Available for ftp from cs.colorado.edu:pub/techreports/zom/CU- CS-665-93.ps.Z.

[14]

Edelson, Daniel, "A Mark-and-Sweep Collector for C + + ", Conference Record of the Nineteenth Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Albuquerque, New Mexico, January 1992, pp. 51-58.

Digital Library

[15]

Ellis, John R., and David L. Detlefs, "Safe Efficient Garbage Collection for C + +", Xerox PARC Technical Report CSL-93-4, September 1993. Also available from parcftp.xerox.com:pub/ellis/gc/gc, ps.

[16]

Fradet, Pascal, "Collecting More Garbage", Proceedings of the 1994 ACM Conference on Lisp and Functional Programming, pp. 24-33.

Digital Library

[17]

Goldberg, Benjamin, 'Wag-Free Garbage Collection for Strongly Typed Programming Languages", ACM SIGPLAN '91 Conference on Programming Language Design and Implementation, SIGPLAN Notices 26, 6 (June 1991), pp. 165-176.

Digital Library

[18]

Hastings, Reed, and Bob Joyce, "Fast Detection of Memory Leaks and Access Errors", Proceedings of the Winter 92 USENIX conference, pp. 125-136.

[19]

Jones, Richard, and Paul Kelly, "Bounds Checking for C", http://wwwala. doc. ic.ac.uk/~ phjk/BoundsChecking.html.

[20]

Omohundro, Stephen M., The Sather Language, ICSI, Berkeley, 1991.

[21]

O'Toole, James, and Scott Nettles, "Concurrent Replicating Garbage Collection", Proceedings of the 1994 ACM Conference on Lisp and Functional Programming, pp. 34-42.

Digital Library

[22]

Rose, John R., and Hans Muller, "Integrating the Scheme and C languages", Proceedings of the 1992 ACM Conference on Lisp and Functional Programming, pp. 247-259.

Digital Library

[23]

Rovner, Paul, "On Adding Garbage Collection and Runtime Types to a Strongly-Typed Statically Checked, Concurrent Language", Technical Report CSL-84-7, Xerox Palo Alto Research Center, Palo Alto, CA, July 1985.

[24]

Schelter, W. F., and M. Ballantyne, "Kyoto Common Lisp", AI Expert 3, 3 (1988), pp. 75-77.

Digital Library

Cited By

Bernhard LRodler MHolz TDavit L(2022)xTag: Mitigating Use-After-Free Vulnerabilities via Software-Based Pointer Tagging on Intel x86-642022 IEEE 7th European Symposium on Security and Privacy (EuroS&P)10.1109/EuroSP53844.2022.00038(502-519)Online publication date: Jun-2022
https://doi.org/10.1109/EuroSP53844.2022.00038
Banerjee SDevecsery DChen PNarayanasamy S(2020)Sound garbage collection for C using pointer provenanceProceedings of the ACM on Programming Languages10.1145/34282444:OOPSLA(1-28)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428244
Ainsworth SJones T(2020)MarkUs: Drop-in use-after-free prevention for low-level languages2020 IEEE Symposium on Security and Privacy (SP)10.1109/SP40000.2020.00058(578-591)Online publication date: May-2020
https://doi.org/10.1109/SP40000.2020.00058
Show More Cited By

Recommendations

Simple garbage-collector-safety

A conservative garbage collector can typically be used with conventionally compiled programs written in C or C++. But two safety issues must be considered. First, the source code must not hide pointers from the garbage collector. This primarily requires ...
A generational on-the-fly garbage collector for Java
PLDI '00: Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation

An on-the-fly garbage collector does not stop the program threads to perform the collection. Instead, the collector executes in a separate thread (or process) in parallel to the program. On-the-fly collectors are useful for multi-threaded applications ...
A concurrent copying garbage collector for languages that distinguish (im)mutable data

This paper describes the design and implementation of a concurrent compacting garbage collector for languages that distinguish mutable data from immutable data (e.g., ML) as well for languages that manipulate only immutable data (e.g., pure functional ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PLDI '96: Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation

May 1996

300 pages

ISBN:0897917952

DOI:10.1145/231379

Chairman:
Charles N. Fischer
Univ. of Wisconsin, Madison

ACM SIGPLAN Notices Volume 31, Issue 5
May 1996
300 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/249069
Editor:
Richard L. Wexelblat
Issue’s Table of Contents

Copyright © 1996 ACM.

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

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 1996

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

PLDI96

Sponsor:

SIGPLAN

PLDI96: Programming Language Design and Implementation

May 21 - 24, 1996

Pennsylvania, Philadelphia, USA

Acceptance Rates

PLDI '96 Paper Acceptance Rate 28 of 112 submissions, 25%;

Overall Acceptance Rate 406 of 2,067 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

39
Total Citations
View Citations
640
Total Downloads

Downloads (Last 12 months)100
Downloads (Last 6 weeks)35

Reflects downloads up to 20 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bernhard LRodler MHolz TDavit L(2022)xTag: Mitigating Use-After-Free Vulnerabilities via Software-Based Pointer Tagging on Intel x86-642022 IEEE 7th European Symposium on Security and Privacy (EuroS&P)10.1109/EuroSP53844.2022.00038(502-519)Online publication date: Jun-2022
https://doi.org/10.1109/EuroSP53844.2022.00038
Banerjee SDevecsery DChen PNarayanasamy S(2020)Sound garbage collection for C using pointer provenanceProceedings of the ACM on Programming Languages10.1145/34282444:OOPSLA(1-28)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428244
Ainsworth SJones T(2020)MarkUs: Drop-in use-after-free prevention for low-level languages2020 IEEE Symposium on Security and Privacy (SP)10.1109/SP40000.2020.00058(578-591)Online publication date: May-2020
https://doi.org/10.1109/SP40000.2020.00058
Schafmeister CWood AVerna DCooper D(2018)Clasp Common Lisp Implementation and OptimizationProceedings of the 11th European Lisp Symposium on European Lisp Symposium10.5555/3323215.3323223(59-64)Online publication date: 18-Apr-2018
https://dl.acm.org/doi/10.5555/3323215.3323223
Schafmeister CDurand IPsota M(2016)CANDO: A Compiled Programming Language for Computer-Aided Nanomaterial Design and Optimization Based on Clasp Common LispProceedings of the 9th European Lisp Symposium on European Lisp Symposium10.5555/3005729.3005738(75-82)Online publication date: 9-May-2016
https://dl.acm.org/doi/10.5555/3005729.3005738
Yiapanis PBrown GLuján M(2015)Compiler-Driven Software Speculation for Thread-Level ParallelismACM Transactions on Programming Languages and Systems10.1145/282150538:2(1-45)Online publication date: 22-Dec-2015
https://dl.acm.org/doi/10.1145/2821505
Bergan TGrossman DCeze L(2014)Symbolic execution of multithreaded programs from arbitrary program contextsACM SIGPLAN Notices10.1145/2714064.266020049:10(491-506)Online publication date: 15-Oct-2014
https://dl.acm.org/doi/10.1145/2714064.2660200
Bergan TGrossman DCeze LBlack AMillstein T(2014)Symbolic execution of multithreaded programs from arbitrary program contextsProceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications10.1145/2660193.2660200(491-506)Online publication date: 15-Oct-2014
https://dl.acm.org/doi/10.1145/2660193.2660200
Johnson NKim HPrabhu PZaks AAugust D(2012)Speculative separation for privatization and reductionsACM SIGPLAN Notices10.1145/2345156.225410747:6(359-370)Online publication date: 11-Jun-2012
https://dl.acm.org/doi/10.1145/2345156.2254107
Johnson NKim HPrabhu PZaks AAugust DVitek JLin HTip F(2012)Speculative separation for privatization and reductionsProceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/2254064.2254107(359-370)Online publication date: 11-Jun-2012
https://dl.acm.org/doi/10.1145/2254064.2254107
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents