MAGPIE: PRECISE GARBAGE COLLECTION FOR C by Adam Wick A dissertation submitted to the faculty of The University of Utah in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Computer Science School of Computing The University of Utah December 2006 UMI Number: 3241833 Copyright 2006 by Wick, Adam All rights reserved. INFORMATION TO USERS The quality of this reproduction is dependent upon the quality of the copy submitted. Broken or indistinct print, colored or poor quality illustrations and photographs, print bleed-through, substandard margins, and improper alignment can adversely affect reproduction. In the unlikely event that the author did not send a complete manuscript and there are missing pages, these will be noted.
Also, if unauthorized copyright material had to be removed, a note will indicate the deletion. ® UMI UMI Microform 3241833 Copyright 2007 by ProQuest Information and Learning Company. All rights reserved. This microform edition is protected against unauthorized copying under Title 17, United States Code.
ProQuest Information and Learning Company 300 North Zeeb Road P. Box 1346 Ann Arbor, MI 48106-1346 Copyright © Adam Wick 2006 All Rights Reserved THE UNIVERSITY OF UTAH GRADUATE SCHOOL SUPERVISORY COMMITTEE APPROVAL of a dissertation submitted by Adam Wick This dissertation has been read by each member of the following supervisory committee and by majority vote has been found to be satisfactory. Chair: 2— MatthewF latt alloc Lé LfOL [ ' hyilson Tei’ V 3/2 l2s Ta. Kent Dybvig a THE UNIVERSITY OF UTAH GRADUATE SCHOOL FINAL READING APPROVAL To the Graduate Council of the University of Utah: I have read the dissertation of Adam Wick in its final form and have found that (1) its format, citations, and bibliographic style are consistent and acceptable; (2) its illustrative materials including figures, tables, and charts are in place; and (3) the final manuscript is satisfactory to the Supervisory Committee and is ready for submission to The Graduate School.
7[1 (06 Z2[keer Date Matthew Flatt Chair, Supervisory Committee Approved for the Major Department M. bey Martin Berzins Chair /Dean Approved for the Graduate Council a ee he Oe David S. Chapman ` Dean of The Graduate School ABSTRACT C and C++ provide fast, flexible substrata for programs requiring speed or tight coupling with the operating system or hardware. Both languages have well established user and code bases, including programs still in use after decades of development.
Unfortunately, with C and C+-+’s speed and flexibility come increased complexity, including complication in managing memory. Programs must create and destroy objects explicitly, and small mistakes in doing so can cause severe complications. In other languages, precise garbage collection solves these problems by having the computer manage the program’s memory. However, until now, adding precise garbage collection to standard C programs has been a considerable amount of work.
This dissertation describes Magpie, a system that uses several analyses and conversion techniques to relieve much of the burden of this conversion. It also describes the effects of the conversion on several sample programs. Finally, debugging tools and language runtimes can perform additional inter- esting tasks given an existing garbage collection infrastructure. This dissertation outlines several such extensions, and discusses one —- memory accounting — in detail.
iv LIST OF FIGURES. eee viii LIST OF LABLES. PRECISE COLLECTION AND C PROGRAMS .1 Memory Management Paradigms.1 Static Allocation / No Deallocation.2 Manual Memory Management.3 Compilers and Garbage Collection. THE HIGH LEVEL DESIGN OF MACPIE.1 Co: ee eee eee eens 13 2.2 The Mechanics of Garbage Collection .1 The Design of Magpie .2 Dealing with Libraries.3 In-Source Flags .3 Limitations of Magpie vs.1 Limitations of Magpie.2 Comparisons to Boehm.1 Generating the Input.
ccc eee eens 25 3. eee eee và 30 3.4 Call Graph Analysis.5 Garbage Collector Generatlon.caaIáaáaaa eee eee eens 38 IMPLEMENTING MAGPIE.1 Implementing the Allocation Analysis.1 Gathering the Allocation Analysis Information.2 Converting the Allocation Points.2 Implementing the Structure Analysis.1 Coping with Too Many Structures.2 Creating the Traversal Routines.3 Implementing the Call Graph AnalÌysis.4 Implementing the Stack Conversion.1 Overview of the Stack Conversion.2 Internal Variable Shape Forms .3 Caveats Regarding Optimizations.4 Adding Stack Frames.2 Array and Tagged Saves. cc eee ees 61 4.5 Removing Stack FYames. ccc eee eens 63 4.6 Dealing with Shared Libraries .7 Implementing the Garbage Collector.
cc eee eee 66 4.3 Tuning the Garbage Collector .8 Threads and Magpie. eee eens 68 THE COST OF CONVERSION.1 An Overview of the Benchmarks.2 Converting the Benchmarks.1 Using Boehm with the Benchmarks. ce eee eens 73 5.3 Unions in the Benchmarks. ee eee tees 78 5.3 The Cost in Time .1 Comparing Base and NoGC .2 Comparing NoGC and NoÓp£_.3 Comparing NoOpt and MÍagpie.4 The Cost of ÂutOfAaBgBÌnE.5 Comparing Base, Boehm and Mlagpie.7 Possible Shadow Variable Ôptimization.0 Final Discussions on Space and Time .1 Object Deallocation Costs.3 Smaller Object SlZ@§.
ceeee 96 EXPLOITING PRECISE GC: MEMORY ACCOUNTING .2 Assignment Hand-In Server .2 Consumer-Based Âccounting.3 Accounting in the Examples .2 Hand-In Server. eee nee eens 106 6.00 eee eee eee 106 6.2 Vertically Communicating Processes.3 Horizontally Communicating Processes.4 Libraries and Callbacks.5 Producer-Based Âccounting. cc c eee eens 110 6. kg ng kh nh eee vy và 113 6.6 Comparisons to Existing Systems.1 Magpie for C/VM Inierfaces.
cee eee eens 118 7. 0 0 ccc eee een ees 123 vii LIST OF FIGURES 1.1 A screenshot of Apple’s Safari web browser using nearly 3 gigabytes of memory after a couple of hours of normal usage.1 The high-level design of the Magpie toolset.1 The allocation analysis window for the top source file libtop.2 An example of the allocation analysis window where the object in question is a tagged objeCf.3 The structure analysis window for the top source file libtop.4 The difference between (a) an array of struct foos and (b) an array of pointers to struct foos. The latter case is considerably more common in ĐTAGẨIC€.0 eee ee ee 32 3.9 An example of entering in the information for the “an array of inline objects, of size” case. Note that the field in question does not, in fact, declare such a thing; this figure is merely an example of the information needed in these cases.
eee ee eee 33 3.6 An example of entering in a custom traversal function. Again, this is a fictitious example; there is no reason to write a traverser for this field.7 The structure analysis GUI for unions.1 Exemplars of the four kinds of shadow stack frames in Magpie.1 The memory behavior of the 164.2 The memory behavior of the 175.3 The memory behavior of the 176.4 The memory behavior of the 179.5 The memory behavior of the 181.6 The memory behavior of the 183.7 The memory behavior of the 186.8 The memory behavior of the 188.9 The memory behavior of the 197.10 The memory behavior of the 254.11 The memory behavior of the 256.12 The memory behavior of the 300.1 The three interprocess communication patterns. The filled circle rep- resents the parent process, with the hollow circles representing child processes. The arrows represent directions of communication.2 The four steps of the accounting procedure.3 A potential heap layout, mid-collection.
The grayed objects have been marked by the collector. cece eee eee ix LIST OF TABLES 5.1 An overview of the size of the various benchmarks used. All prepro- cessed files generated on Mac OS/X 10.2 The cost of the allocation analysis for each of the benchmark pro- grams. Parse time is the time spent in parsing and massaging the source into the correct internal formats.
User time is the amount of time the programmer spends answering questions. All times approxi- Mate, 2. ee nee eee eae 74 5.3 The cost of the structure analysis for each of the benchmark programs. Parse time is the time spend in parsing and massaging the source in the correct internal formats.
User time is the amount of time the programmer spends answering questions. All times approximate.4 The cost of the automatic conversions. Conversion time is the time spent by Magpie in the various analyses, transformations and addi- tions required to take the original file and create the internal repre- sentation of the converted file. Total convert time includes parsing, unparsing and recompilation of the file.5 The number of unions in each of the benchmark programs, and how they are handled for the conversion.6 The impact of the Magpie conversion on executable sizes.7 The performance impact of garbage collection on the benchmarks.
80 CHAPTER 1 PRECISE COLLECTION AND C PROGRAMS Memory management is one of the most tedious and error-prone tasks in soft- ware development. Small, unnoticed memory-management mistakes can cause crashes, security problems, slow degradation of program performance, and OS crashes. While testing catches many of these errors, some remain even in released software.1 for an example of Apple’s Safari web browser afflicted with a slow memory leak. Reliance on legacy code exacerbates the memory-management problem.
Many companies and institutions rely on programs they have used for decades; programs that have been modified by many different hands as managers add new requirements and users find new bugs. Often, the original programmer(s) for the application have moved to other companies, and program maintenance is left to people unfamiliar with the program’s design. Worse, documentation on the program’s design and implementation is usually either out of date or nonexistent, particularly with regard to memory management conventions. A programmer new to the project may need to spend weeks or months to find and correctly fix memory errors.
Rewriting legacy programs is often impractical or unwise; redeveloping a com- plex system using modern languages, tools, and designs may take years. Further, the redesign will introduce new bugs to be tracked and fixed. If the original program is critical for the company or institution, spending years to correct one problem — only to potentially introduce different problems — is an expensive risk with minimal hope of reward. The subject of this dissertation, Magpie, is one solution to this problem.
Magpie solves much of the problem of memory-management bugs by modifying a program threa liên: 4 Tà Figure 1. A screenshot of Apple’s Safari web browser using nearly 3 gigabytes of memory after a couple of hours of normal usage. to use garbage collection. Thus, the converted program automatically performs its own memory management, rather than relying on the programmer to get everything correct.
Thesis: Precise garbage collection offers advantages to programmers over manual memory management, through ease of programming, a lessening of memory errors, and increased tool support. Furthermore, these advantages are available for typical C-implemented programs with proper tool support. A tool can simplify the process of converting existing code to use precise collection, bringing these advantages to normal C programmers. Magpie is a tool to demonstrate this thesis.
Magpie contrasts with existing tools to aid in detecting memory errors in existing programs. These tools run the gamut from academic type systems, reworking of language runtimes, dynamic checking tools and complicated software analyses. This chapter continues with a survey of the subject of memory management, and the problems inherent with each memory management strategy, with the conclusion that precise garbage collection is often the best solution. It then outlines the contributions of this dissertation, and concludes with a roadmap for the remainder of the dissertation.1 Memory Management Paradigms Most programs manage memory using one or more of four basic memory- management strategies: static allocation, manual memory management, reference counting and garbage collection.
Each of the basic strategies has advantages and disadvantages with regard to space utilization and performance. Most have tool sets associated with them to aid in their adoption or in their use. This section examines each of these four basic strategies.1 Static Allocation / No Deallocation In some basic programs, very little memory is used; either no memory is al- located, or there is no need to deallocate any memory allocated. Simple student exercises, some simple command-line utilities, and even some more complex utilities (such as compression utilities) may fall under this category.