\documentclass{article} \usepackage{array} %\renewcommand{\Diamond}{\langle\!\rangle} \renewcommand{\Diamond}{} \sloppy \usepackage{epsfig} \newcommand{\BDW}{B{\"o}hm-Demers-Weiser} \newcommand{\cpp}{{C$^{++}$}} \newcommand{\gc}{garbage collector} \newcommand{\scl}{{\tt SizeClass}} \newcommand{\gd}{{\tt gc\_data}} \newcommand{\pgi}{{\tt PageInfo}} \newcommand{\mcc}{mostly-copying collector} %\newcommand{\fgc}{{\sc fgc}} \newcommand{\fgc}{{\em fgc}} \newcommand{\stw}{{\sc stweb}} %\newcommand{\illu}{\begin{center} {\em here goes an illustration} \end{center} } \begin{document} \title{Design and Implementation of the Frugal Garbage Collector (FGC)} \author{Gor V. Nishanov and Sibylle Schupp} \date{} \maketitle \tableofcontents \listoffigures \newpage \begin{abstract} The {\em frugal garbage collector} (\fgc ) is a new, hybrid mark-sweep and \mcc\ for \cpp , aiming at use in generic libraries. \fgc\ is the first \mcc\ (as far as we know) that can cope with \cpp\ template classes where at class design time it is not known yet whether an object has internal pointers or not. Further characteristic properties of \fgc\ include space efficiency and, through an interface to the B{\"o}hm-Weiser-Demers collector, portability. We discuss its design and present the implementation in the style of literate programming. \end{abstract} \section{Introduction} Garbage collection has a history of almost 40 years. Originally introduced in the field of artificial intelligence, garbage collection has become widely accepted as a feature of higher programming languages. Most functional, logic, and object-oriented languages have garbage collection now built in, thereby preventing memory leaks and dangling pointers, which both are well-known as recurring and subtle sources of user errors. However, safety is not the only motivation for the use of automatic memory management; of equal importance is space efficiency. Even in times when ``memory is cheap," lack of memory is still the barrier for certain large-scale applications. A computation with little computing time available will terminate eventually---a computation without enough memory will not. When ``C with classes" \cite{Str83} was developed, only explicit memory management by hand was supported. In the course of several years, however, different kinds of automatic memory management were suggested, both reference counting and garbage collection (see \cite{DeDoZo93,ElDe93,Ede92a}, for a survey see \cite{JoLi96}). Even though the standardization of the \cpp\ language in November 1997 \cite{C++98} cut off the discussion of an extension of the language itself, the need for automatic memory management and garbage collection exists and will even grow, as more libraries and large-scale applications are written in \cpp . Techniques for garbage collection without compiler support, therefore, continue to be explored. In the non-commercial \cpp\ world, there are three widely known collectors: the {\em B\"ohm-Weiser-Demers} collector \cite{BoWe88}, the collector by {\em Bartlett} \cite{Bar88,Bar89}, and the {\em Customisable Memory Management (CMM)} by Attardi and Flagelli \cite{AtFl96, AFI97}. We briefly characterize the three collectors. The {\em B\"ohm-Weiser-Demers} collector is the most frequently \cpp\ collector. It is a highly portable collector, running under all common platforms and regularly maintained. It is also a very efficient collector. Programs using it are competitive with ones using manual allocation. Conceptually, the { B\"ohm-Weiser-Demers} collector belongs to the category of {\em mark-sweep collectors}, as the drawback of whose fragmentation is known. Where fragmentation causes pratical problems, {\em mostly-copying collectors} provide an alternative. Both Bartlett's collector and the CMM framework are \mcc s, in fact, Bartlett's collector for C was the first mostly copying collector. (It later was further developed to a generational collector, as were CMM and the B{\"o}hm-Weiser-Demers collector.) Bartlett's collector emerged from a Scheme-to-C compiler, about 10 years ago. Its application today is limited by the fact that the collector was developed for a restricted selection of machines (DEC Ultrix and Alpha AXP and Sun Sparc). Moreover, the program was written at a time when the \cpp\ language was far from being standardized. Since then, the language has changed and with it, the compiler technology; as a result not every current compiler accepts what GNU g++, v.2.0., and DEC's \cpp compiler 1.0 and 1.2 used to accept. The CMM framework, finally, was developed within the ESPRIT BRA PoSSo project, a package for solving systems of polynomial equations. In this project, it is desirable to switch at run-time between different heaps. The flexibility is achieved through the use of virtual inheritance. The {\em frugal garbage collector}, \fgc , collector is a general-purpose collector, designed for use in (generic) libraries. Rather than having a particular application in mind, a compiler or a large user program, our goal is to provide a memory management component that designers of \cpp\ libraries can freely compose together with other library units. Since libraries constitute foundations on top of which other applications are built, memory management components particularly are subject of rigorous efficiency and portability requirements. The \fgc\ is a hybrid mark-sweep and \mcc\ collector. It supplements the principles in both Bartlett's and the CMM collector by a mark-sweep component, which applies to big objects and saves the cost of copying them. The major design goals for \fgc, their rationale as well as our approach, are summarized as follows: \begin{itemize} \item Space efficiency: There are two sources for space overhead, the overhead for annotating individual objects and the overhead for administrating the entire heap. For \mcc s, the overhead per object is at least one function pointer; \fgc\ keeps this lower bound. For the overhead per heap page there is no lower bound known. Keeping this overhead small, is important, since it is dynamically growing with every heap expansion. In \fgc , the total overhead per page amounts to 4 words, which is very little. \item Support of templates: Mostly-copying collectors expect class designers to provide information about internal pointers of a class. Generic \cpp\ libraries, however, use templates, the instantiation of which obviously is not known at class design time. If the instantiation is not known, the number and location of pointers of a given class is not known either. The \fgc\ collector, consequently, has to find a way to provide the information that a \mcc\ requires under the presence of templates. %Our solution exploits dispatching at compile time (overload % resolution) and template member functions. As far as we know, \fgc\ is the only \mcc\ capable to handle \cpp\ templates. \item Portability: Libraries are developed to run under several platforms. If we want \fgc\ to be integrated into libraries, \fgc\ has to be portable also. Portable garbage collectors are almost a contradiction in itself, given the extent to which a garbage collector depends on a particular system architecture. There is, however, a de-facto portable collector for C and \cpp: the collector by B{\"o}hm, Weiser, and Demers is ported to all common modern platforms. Even though the \BDW \ collector realizes a garbage collector technique different from the one in \fgc , we are able to take advantage of the experience and expertise concentrated in their collector. Through an interface to its system dependent parts, \fgc \ inherits portability from the \BDW \ collector. \end{itemize} The first major design guideline was to keep the use of resources minimal. Given rigorous efficiency criteria, we consider the costs of virtual inheritance, in time and space, too high. In contrast to the CMM approach, our philosophy of flexibility rather follows the spirit of templates and statically resolvable parameterization. The second major design goal was portability. The \fgc\ collector should be executable on all common platforms with compilers compliant with the \cpp\ language as specified in the proposed standard \cite{C++98}. Garbage collection without language support might seem to be a strange undertaking. After all, the first task of a garbage collector is to detect pointers. Without compiler support, how does the collector distinguish, say an integer variable from an address? Moreover, how does it know where to look for potential pointers? Pointers reside in the stack, in registers, in the static areas, and in the heap. What if the collector has no knowledge of the memory layout and of register scheduling? In \cite{BoWe88}, B{\"o}hm and Weiser introduced the technique of {\em conservative} garbage collection in a fully uncooperative environment which treats all addresses as pointers unless proven otherwise. The authors developed several heuristics to keep the chances for misidentifying pointers low. They also developed---highly system-specific---techniques to determine the various regions in memory. The latter techniques carry over to the \fgc\ collector. Though not operating in a fully uncooperative environment, but rather in an environment in which all user-defined pointers can be identified precisely, the \fgc\ collector still lacks the knowledge about the program stack and the location of static regions. Through an interface to the B{\"o}hm-Weiser-Demers collector, however, we are able to get the information required. Garbage collectors are no small programs---\fgc\ in the close sense, without the interface to the B{\"o}hm-Weiser-Demers collector, has about 1500 lines of code. Somewhat necessarily, this code contains low-level passages with direct memory operations that are not very self-explanatory. From the algorithmic view, Jones and Lins \cite{JoLi96} provide a rather complete discussion of the different strategies for automatic memory management. For a full understanding of a working collector, however, the details are what count. Such details are too often hidden in comments in header files, if they are mentioned at all. We therefore decided to present our documentation in the style of literate programming, the style that Donald Knuth introduced to keep sources and their documentation consistent, but also to give the discussion of code the place it deserves. If a garbage collector program is not small, its corresponding literature programming document is not small either. The documentation of the \fgc\ collector comprises approximately 100 pages text, not counting figures, tables, and index. We therefore further decided to present the document in two versions. The ``light" printed version contains this introductory section and an overview and goes then straight to a sample session. Additionally, it contains a large portion of the unshortened version's appendix and its table of contents. The comprehensive documentation of the full source of the \fgc\ collector in the close sense\footnote{The fully working collector includes parts of the B{\"o}hm-Weiser-Demers collector, with some modifications; these files are listed in appendix B, but are not part of our documentation.} is available at the {\em Generic Programming Group\/}'s website as gzip'ed postscript and pdf file: \begin{verbatim} http://www.cs.rpi.edu/research/gpg/designFGC.[ps|pdf].gz \end{verbatim} For readers using the literate programming tool {\tt stweb} or its ancestor {\tt nuweb} and relatives, we also provide the source {\tt designFGC.w.gz}, in the same directory. The complete documentation breaks down into four major parts besides the introductory part and the overview. The first part (section 2) discusses the data structures used in \fgc . The second and third part deal with the collecting (section 4-6) and the allocating (section 7,8) part of \fgc . The fourth part, finally (section 9-11), describes system dependencies, program constants, and debugging functions. A demonstration program in section 12 finishes the article; the appendix lists all output files and, separately, the user's interface. This article is neither an introduction to garbage collection nor a user's guide for \fgc ; it addresses library designers as its direct users. As every \mcc\ does, \fgc\ expects collaboration at the class level, i.e., appropriately designed classes. If a library has been developed without the knowledge of \fgc , certain adjustments are necessary to make the library \fgc -compliant; this article should provide enough information for the necessary adaption. For libraries on top of the Standard Template Library (STL), we have already make provisions and developed an adaptor which makes the transition from a STL-based library to a \fgc -supported library rather convenient. Although the adaptor itself is not discussed in this paper, the sample session will briefly refer to it. Readers of this article should be familiar with the two techniques of mark-sweep and copy-collecting and with the general concept of conservative garbage collection. The \fgc\ started as a project by the first author under the second author's supervision. The first author wrote the major portion of the main program, the second author provided its adaption to applications and the documentation, both worked on debugging and bug-fixing. \paragraph{Acknowledgment} We like to emphasize how valuable the CMM framework and Bartlett's collector were for the design of the \fgc \ collector. We also acknowledge B{\"o}hm, Weiser, Demers and all others that contributed to their collector. This document was generated by \stw , an extension of P. Brigg's nuweb by R. Loos, using the {\sc MiKTeX} implementation of {\sc Latex}. Toby-John Mills helped to prepare the {\sc Latex} figures. \section{Overview} The \fgc\ collector is a garbage collector for \cpp \ programs, written in \cpp\ itself. The collector is conservative in the sense that it runs without support by a \cpp compiler, but it requires cooperation for user-designed classes. This first section gives an overview of the major procedures and the major data structures \fgc\ is made up of. Roughly speaking, the \fgc \ collector belongs to the family of \mcc s.\footnote{It was Bartlett \cite{Bar89} who coined this term.} Mostly-copying collectors are hybrid collectors, the conservative part which implements a mark-sweep and the non-conservative part which implements a copy-collecting policy. However, the \fgc\ collector pushes hybridism one step further. It is a hybrid \mcc , that is a \mcc\ with an additional mark-sweep component in its non-conservative part. What does such characterization imply for the design of the collector? First, like any other tracing collector, \fgc \ performs the three steps of finding roots, processing their target objects, and recursively traversing these objects. Second, like a \mcc , it distinguishes two kinds of heap-allocated objects: those that can be reached from roots (i.e., from the program stack, the static area, or registers) and others that are accessible from within the heap only. As a \mcc, also, the \fgc\ collector does not move the former ones. In contrast to a \mcc , however, the \fgc\ collector does not copy every object it safely could. Instead, it treats big objects in a mark-sweep manner, i.e., it either marks them or sweeps them, but saves the costs to move them. Thus, the collecting cycle of \fgc\ looks as follows: @D collection @{ @< mark pages accessible from roots @> // for each page touched @< mark-sweep or copy-collect @> @} However, the collection phase constitutes only one part of the \fgc\ collector.% \footnote{When we use in the following the term ``collector" we refer to the collecting part in the close sense; to avoid ambiguities we refer to the entire collector by its full name, \fgc .} Before collection comes into the scene, memory has to be allocated and objects have to be placed appropriately. This second task is taken care of by the allocator part of \fgc . The allocator takes a user request for memory and branches according to the requested size. If enough memory is available, big objects are stored in contiguous space; for small objects, a segregation policy applies. If not enough free space is available the allocating part calls the collecting part. If the collecting part does not return enough space, it expands the heap and starts over again. @D allocation @{ if(size < SMALL_SIZE) @< allocate small object @> else @< allocate big object @> // if allocation fails @< collection @> // if collections fails @< heap expansion @> @} So far we have sketched the policy and the design of \fgc . What are the cornerstones of its implementation? As already mentioned, \fgc\ is implemented in \cpp. For reasons of efficiency, however, it does not take advantage of the object-oriented features of \cpp. We consider in particular the costs of virtual inheritance, in time and space, as too expensive. Conceptually most important are the two abstractions of a \emph{heap} and a {\em page}, as the smallest unit of a heap.\footnote{A {\em page} in our terminology is different from a page in the sense of an operating system. We adopted the notion from Bartlett's and the CMM collector.} Two classes correspond to these two concepts: the class \pgi\ describing a single page and the class \gd\ describing the state of the heap as a whole. A third, practically important class is the class {\tt sysDep} that provides the interface to the underlying operating system. In summary, the major components of \fgc\ are the following: @D components @{ @< global heap information @> @< page information table @> @< collection @> @< allocation @> @< heap expansion @> @< system dependencies @> @} In the following sections we explain each component in detail, including all auxiliary data and functions. Beginning with the foundations--- data structures---we then proceed with the collecting part, including the marking and the scanning phase, followed by the allocation and the heap expansion components. The presentation of \fgc\ in the conceptual sense is concluded by the system interface. The remaining sections address auxiliary functionality, including debugging procedures, program and customizable constants, and an example. The appendix lists the organization of output files, with the user interface and the interface to the \BDW\ collector separated. The section macros, finally, maintains an index to source code. \section{Data Structures} Understanding the implementation of \fgc 's allocation and collection parts requires an understanding of the underlying data structures. We therefore begin our presentation with a detailed discussion of the major data structures and their implementation. Some of the details might look reasonable only from the context of their application, but we decided against scattering the various parts of a class over several subsections. Instead, readers might skip what appears to be irrelevant and get back to the corresponding passages when needed. Three classes are in the focus of this section: the two classes \pgi\ and \gd, mentioned already in the overview section, and the class {\tt SizeClass} describing objects of a given small size; this class is a member class of \gd . For these three classes different efficiency concerns apply. The latter two, \gd\ and \scl , are statically allocated and reside on the stack of the user program. But the first one, \pgi\ or better: the table of \pgi s, dynamically grows in the course of the user program---taking up the very same space the garbage collector just intends to manage efficiently. What gave the ''frugal garbage collector'' \fgc\ its name (justified the ``f" in it) is that is keeps the page-information table and thereby the overall overhead of garbage collection very small. We look into the page-information class \pgi \ first, then into the classes \gd \ and \scl . \subsection{The class \pgi} A garbage collector has to have certain information about the heap. It needs to know whether a page is accessible or whether it has already been visited, which objects are stored on it and how many. This meta-description can be stored either on the pages themselves, or, more efficiently, in separate tables. Both Bartlett's and the CMM collector avoid polluting pages and provide tables instead. Each table reflects a particular view on the heap. To give an idea of the different views on the heap, we briefly list the assembly of tables used in Bartlett's collector. His collector includes the tables {\tt clean} and {\tt mark} to identify, and {\tt plink} to link pages, {\tt firstword} and {\tt type} to describe objects, and (for its generational version) the table {\tt space}. Similarly in the CMM collector. The set of side tables there includes the tables {\tt objectMap, livedMap, pageLink}, {\tt pageGroup, pageSpace, firstfreeWord}, and {\tt pageHeap}. Some of the tables are bitmaps, but others have entries of word-size; all tables dynamically grow with the size of the heap. The \fgc\ collector concentrates the various information about the heap in one single table, the {\em page-information table}. Remarkably, the size of the entries of the table is very small. As little as 4 words are sufficient to describe an individual page---two half-words, a pointer, and a union of two words. In this section we present the entry type of the page-information table, the class \pgi . We address its data members first, then its member functions. \subsubsection{Data members} In the \cpp\ object model, the size of an object depends on the size of its data members and member classes; keeping an object small, consequently, means to manage on few data members only. The class \pgi ---the entry type of the page-information table---is small: As little as 4 words are sufficient to describe an individual page---two half-words, a pointer, and a union of two words: @D PageInfo data members @{ unsigned short space; short size; PageInfo* next; union { struct { word toScan, scanned; } wired; struct { unsigned short live, toScan; word scanned; } wired2; struct { word from, to; } normal; struct { signed_word nPages; word nBytes; } big; }; @} We first discuss the different categories of pages, then the intended meaning of the four data members of the \pgi \ class and their possible values. The main focus there will be on the anonymous member union. As indicated by the union, pages fall in three categories: {\em wired}, {\em big}, and, for lack of a better name, {\em normal}. {\em Wired pages} on the one hand denote pages hit by root pointers. In an uncooperative environment like ours these pointers cannot be changed. Nor could the objects they point to be moved: if the garbage collector cannot distinguish pointer variables from non-pointers, a page cannot safely be moved---it consequently is ``wired." Wired pages come in two flavors ({\em wired, wired2}); those that store a description of their live objects in the page-information table and others that cannot do so; we come back to the distinction at the end of this subsection. {\em Big\/} and {\em normal\/} pages on the other hand distinguish pages according to the size of the objects stored on them. {\em Big\/} pages contain (parts of) objects that spread over one or more pages. {\em Normal\/} pages contain objects of size less than half of a page size; due to the segregation policy for allocation, all objects on a normal page are of the same size. The categorization in {\em wired, wired2, normal}, and {\em big} is logically not quite proper insofar there is no common {\em tertium comparationis} for each two of the four types of pages; the four categories rather reflect {three} different views on a page. For reasons of space efficiency, however, these three views are combined. \begin{center} \begin{tabular}{|l|l|}\hline {\em Page category} & {\em Description} \\ \hline wired & object size $<$ 8 words $<$ 1/2 page, cannot be moved\\ wired2 & 8 words $<$ object size $<$ 1/2 page, cannot be moved\\ normal & object size $<$ 1/2 page, can be moved\\ big & object size $\geq$ 1 page, can be moved if not too big\\ \hline \end{tabular} \end{center} With the four categories of pages in mind, let us turn to the explanation of the data members of the \pgi \ class. \subsubsection{The variable {\tt size}} Normal and big pages can be identified through the value of the variable {\tt size}, the second data member of the \pgi\ class. For normal pages, {\tt size} stores the actual size of the objects residing on it, for big objects it marks the first page with a 0 and all continuation pages with -1. The values of {\tt size} therefore range from -1 to the maximal size for objects on a normal page, as defined by the symbolic constant {\tt SMALL\_SIZE}: % @D SMALL\_SIZE @{ enum {SMALL_SIZE = BYTES_PER_PAGE/2/BYTES_PER_WORD}; @} (note that the division operator is left associative). Since {\tt SMALL\_SIZE} evaluates to 64 words (or 256 bytes) for pages of 512 bytes, the variable {\tt size} is declared as an (unsigned) {\tt short}. \begin{center} \begin{tabular}{|l|l|} \hline {\em Page category} & {\em Value of\/} {\tt size} {\em (in words}) \\ \hline big page, start page & 0 \\ big page, continuation page & $\;-1$ \\ normal page with objects of size $n$ words & $2\leq n < \mbox{\tt SMALL\_SIZE}$ \\ \hline \end{tabular} \end{center} One might wonder whether the lower bound of an object size could be 1 word instead of 2 words, but in a \mcc\ there are no objects of size 1---all classes within a \mcc\ have to provide at least a (pointer to a) traverse function, which occupies already one word. (The layout of classes participating in garbage collection will be explained in the sections on scanning and allocation.) \subsubsection{The anonymous union} From the allocator's standpoint a page is either {\em big\/} or {\em normal\/}; the allocator does not know about {\em wired\/} pages. The collector, on the other hand, knows all four kinds of pages and treats each in a special way. {\em Wired pages} are mark-sweep collected, {\em normal pages} copy-collected, and {\em big pages\/} (objects) are treated either way, mark-sweep or copy-collected, depending on the actual size of the big object. The anonymous member union of the \pgi\ class is designed to keep the different information needed to realize the chosen collector strategy. @D union @{ union { struct { word toScan, scanned; } wired; struct { unsigned short live, toScan; word scanned; } wired2; struct { word from, to; } normal; struct { signed_word nPages; word nBytes; } big; }; @} As in the previous subsection, we go through the various variables and discuss their semantics and their possible values. For big, i.e., multi-page objects, we store the total size (in bytes) of the big object in the variable {\tt nBytes} and the actual page number in the variable {\tt nPages}; if {\tt nBytes} is sufficiently small, the big object will be copy-collected. The size {\tt nBytes} of a big object is upwards bound by the size of {\tt word}, a typedef of the built-in type {\tt int}; the value of {\tt nPages} is bound by the number of pages required to held an object of maximal size. \begin{center} \begin{tabular}{|l|l|}\hline {\em Variable} & {\em Value} \\ \hline {\tt nBytes} & $2^{32}-1$ \\ {\tt nPages} & $2^{\mbox{\tt sizeof(word)}}$/BYTES\_PER\_PAGE ($=2^{24}$) \\ \hline \end{tabular} \end{center} Worthwhile to note, the variable {\tt nPages} is of type {\tt signed\_word}. In fact, it stores the page number as a negative value, which later will allow using a forward mechanism (the function {\tt skip()}) to traverse backwards. \begin{figure} \begin{center} \begin{tabular}{|l|} \hline {\tt space} \vline \hspace{2pt} {\tt size} \\ \hline {\tt next} \\ \hline {\tt nBytes} \\ \hline {\tt nPages} \\ \hline \end{tabular} \\ \smallskip \caption{Big page} \end{center} \end{figure} For {normal pages} we store two offsets in the page, {\tt from} and {\tt to}. The first one, {\tt from}, denotes the offset of the most recently allocated object while the second one, {\tt to}, denotes the offset of the first allocated object---which, for sizes equal to a power of 2, coincides with the page boundary. In the illustration below one can also see that {\tt from} has a logically higher address than {\tt to}; for reasons of efficieny, as will become clear later, {normal pages} are filled from the bottom to the top. Strictly speaking, two {\tt short} types would be sufficiently large to held the values of {\tt from} and {\tt to}, but since we deal here with a union we do not effectivly gain space by diminishing their size. \begin{figure} \begin{center} \begin{tabular}{|l|} \hline {\tt space} \vline \hspace{2pt} {\tt size} \\ \hline {\tt next} \\ \hline {\tt to} \\ \hline {\tt from} \\ \hline \end{tabular} \\ \smallskip \caption{Normal page} \end{center} \end{figure} The third type of the anonymous union comprises the two structures {\em wired} and {\em wired2}. The two structures have two members in common, namely {\tt toScan} and {\tt scanned}. Both variables serve as bitmaps in which the $n$th bit represents the $n$th object on a page. When an object on a wired page is hit, its corresponding bit in the {\tt toScan} map is set; after the object has been scanned, the corresponding bit in the {\tt scanned} map is flagged up. For size=2,3 more than 32 objects fit on one page so that one word-bitmap is too small; for these two exceptional cases we provide extra bitmaps and store them on the pages for objects of size 2 and 3, respectively. Different maximal numbers of objects on a page also gives raise to the distinction between {\em wired} and {\em wired2} structures. Both categories of pages contain another bitmap, {\tt live}, needed to identify miss-hits. The {\tt live} bitmap is important when the status of a page changes from normal to wired since it preserves the information that for a normal page was stored as the range {\tt [from, to]}. Depending on the size (hence number) of objects on a page, the {\tt live} bitmap can either fully be stored in the page-info table ({\em wired}) or needs an extra word ({\em wired2}), which we take from the pages themselves. Except for size=4, we can use space that is invalid otherwise (because the object size divides the page size with a remainder) and do not have to waste space. \begin{figure} \begin{center} \begin{tabular}{|l|} \hline {\tt space} \vline \hspace{2pt} {\tt size} \\ \hline {\tt next} \\ \hline {\tt toScan} \\ \hline {\tt scanned} \\ \hline \end{tabular} \\ \smallskip \caption{Wired page} \end{center} \end{figure} \begin{figure} \begin{center} \begin{tabular}{|l|} \hline {\tt space} \vline \hspace{2pt} {\tt size} \\ \hline {\tt next} \\ \hline {\tt live} \vline \hspace{2pt} {\tt toScan} \\ \hline {\tt scanned} \\ \hline \end{tabular} \\ \smallskip \caption{Wired2 page} \end{center} \end{figure} \subsubsection{The variables {\tt space} and {\tt next}} Besides the two data members discussed, there are two more data members in the \pgi\ class: the integer {\tt space} and the pointer {\tt next}. The first one, the variable {\tt space}, corresponds to the {\em To\/} and {\em From\/} space in a classical copy collector. In contrast to the classical approach, however, {\tt space} is not just a flag, but an increasing number, starting with 0 and incremented after each collection cycle. The advantage of this approach is that returned space can easily be identified by comparing its space number with the value of the {\em current space}; if just two values were available, free pages would have to be updated, hence re-visited. Special adjustments, of course, are necessary, when after $2^{16}$ taken pages the {\tt space} variable overflows. The pointer {\tt next}, finally, \pgi 's last data member, is used to link pages of the same (normal, wired, big) kind together in page-specific scanning queues. The page-information table itself, for reasons of efficieny, is stored as an array. \begin{figure}[h] \begin{center} \epsfig{file=Figure4.eps, width=11.5cm, height=1.8cm} \caption{The page-information table} \end{center} \end{figure} % These four variables, {\tt size}, {\tt space}, {\tt next}, and the anonymous union make up the whole \pgi\ object, thus the heap-space overhead per page. Again, with 4 words, the overhead is very little. Each instance of the \pgi\ class describes one page in the heap. Conversely, for each page in the heap there exists an instance of \pgi . However, not all pages in the heap are under control of \fgc . It is important to distinguish pages that ``belong" to \fgc\ from those that happen to be in the range of the heap but have not been allocated by \fgc . For the distinction we introduce a special value, {\tt UNUSABLE\_SPACE}=1, and use the member \pgi{\tt ::space} to set {\tt UNUSABLE\_SPACE} where necessary. \subsubsection{Access to the page-info table} The member functions of the \pgi\ class are divided into access functions, predicates, and mappings from the page-info to the page itself. Some of the member functions are rather straightforward and need no further comments; we will just list them. Immediately clear are the three access functions @D PageInfo access functions @{ void markFree() { space = 0; } void markUnusable() { space = UNUSABLE_SPACE; } void setCount(int n) { size = 0; big.nPages = n;} @} with corresponding predicates @D PageInfo predicates (1) @{ bool isbig() const { return size <= 0; } bool unusable() const { return space == UNUSABLE_SPACE; } @} A second group of predicates checks for free space. With the continuous value for the data member {\tt space} such check is a simple comparison between the actual space number and the value of the global current space, as stored in the variable {\tt gc} (which we discuss in the next section). The first predicate, {\tt free()}, compares two natural numbers, whereas the second predicate, {\tt freeOrUnusable()} integrates into the comparison the value of {\tt UNUSABLE\_SPACE}=-1, wherefore its arguments have to be casted to {\tt signed short}. @D PageInfo predicates (2) @{ inline bool PageInfo::free() const { return space < gc.currentSpace; } inline bool PageInfo::freeOrUnusable() const { return (signed short)space < (signed short)gc.currentSpace; } @} \subsubsection{Access to heap pages} Both predicates just discussed refer to the \pgi\ page descriptors. But during the allocation phase we have to operate on the pages themselves. To get there, we provide the function {\tt data()} which returns the page that corresponds to a given entry in the page-information table. The necessary address computations are a bit twisted; as it is known in the theory of compiler construction as the technique of algebraic simplification and reassociation, we divide the address of a page in a constant and a non-constant part and shift, for reasons of efficiency, as much as possible to the constant part. Essential to the computation is the 1-1 correspondence between the heap and the page-info table: for each page in the heap there exists an entry in the page-info table. Due to the 1-1 correspondence the distance (in pages) of the address of a page {\tt PS} to the start of the heap is the same as the distance of {\tt PS}'s entry in the page-info table to the start of the page-info table. But the latter distance is known: it is the difference between the address of the page-info entry, say {\tt x} for now ({\tt this} in real), to the base address of the page-info table. \begin{verbatim} PS[x] = heapStart + (PageInfo[x]- PageInfo[0]) * PAGEINFO_PER_PAGE \end{verbatim} \begin{figure}[h] \begin{center} \epsfig{file=Figure5.eps, width=11.5cm, height=3cm} \caption{Correspondence between page-info table entries and heap} \end{center} \end{figure} Rewriting the equation (and changing the order of the summands) we gather in a pseudo-constant {\tt gc.PItoPSconstant} that part of the equation that does not depend on the current page and its address: \begin{verbatim} PS[x] = PageInfo[x] * PAGEINFO_PER_PAGE - PageInfo[0] * PAGEINFO_PER_PAGE + heapStart =: PageInfo[x] * PAGEINFO_PER_PAGE + gc.PItoPSconstant \end{verbatim} with @D gc::PItoPSconstant @{ gc.PItoPSconstant = (- word(gc.pageInfos) * PAGEINFOS_PER_PAGE + gc.heapStart); @} Up to two casts, from the {\tt this} pointer to the first {\tt word} of its object and from the result-type back to a pointer to the byte address, the function {\tt data()} performs the computation just described: @D PageInfo::data() @{inline char* PageInfo::data() const { return (char*)(reinterpret_cast(this)* PAGEINFOS_PER_PAGE + gc.PItoPSconstant); } @} \subsubsection{Traversing the page-info table} The \pgi\ table, as the centralized description of the heap, is traversed several times during a collection cycle. In most cases the traversal aims at going from the first object of a page to the ``next first" object. Provided the previous object was small, the ``next first" object is situated on the subsequent page, which implies that we can go from one entry in the \pgi\ table to its neighbor; for big objects, however, which spread over several pages, the ``next first" object is {\em not} on the subsequent page but a few pages later. Consequently, we cannot just look up the adjoint entry in the page-information table but have to skip a few entries. The function {\tt skip()} encapsulates the desired traversal. It moves from the current page-info ({\tt this}) to the next one, or, if the current \pgi\ describes a big object, to the entry that refers to the first page after the big object. The implementation of {\tt skip()} exploits the fact that the page-info table is stored as an array; the pointer arithmetic therefore is legal. @D PageInfo::skip() @{ PageInfo* skip() { return this + (isbig() ? big.nPages : 1); } @} \subsubsection{Queued pages} The last group of functions we discuss here monitor \pgi s that are queued for further scanning. The last bit of the variable {\tt space} (see the previous subsection) is used to encode the current status of a page: odd values indicate a queued page; if a page leaves the queue its space number is made even. Looking at the implementation, we observe that setting and resetting the flag are asymmetrically implemented, a boolean {\em or} operator is used to {\em set}, but an arithmetical {\em -} operator to {\em reset} the flag. The asymmetry shows that pages can be visited multiple times while they are in a queue, but once they have got out of the queue they are definitely processed. @D PageInfo queue test and set @{ void clearInQueueFlag() { assert(space&1); space &= 0xfffe; } void setInQueueFlag() { space |= 1; } bool inQueue() const { return space & 1; } @} Two other member functions of \pgi , {\tt initBig()} and {\tt print()}, are not yet discussed. They will be explained in the sections on allocation and debugging, respectively. There is also a helper class, {\tt PageInfoQueue}, which provides a standard queue (over \pgi 's), the listing of which we safely can omit. \subsection{The class \gd} The previous section dealt with the page-information class, the centralized descriptor of the smallest allocation unit, pages. We now turn to the heap as a whole. The information describing the heap in its entire as well as its current status all is collected in the class \gd . This class also contains all data that are global to the whole collector. For the presentation of the \gd\ class we group its members together in three subsections: heap information, allocation and collection, and construction of the \gd\ class itself. \subsubsection{Heap information} The heap information can be further divided in three categories: book-keeping variables, updating functions, and pointers that access the various regions of the heap. Let us look at pointers first. The heap as a whole is not entirely ``ours." After heap expansion(s), the heap can contain {\em holes}, unusable space, that has not been allocated by \fgc\ and is not at its disposal, therefore. Of its usable parts, furthermore, the page-info table occupies a certain portion. To mark the beginning and end of the various segments, altogether seven pointers are in use: @D gc\_data heap pointers @{ word realHeapStart, realHeapEnd, heapStart, heapEnd; PageInfo* pageInfos, *pageInfosEnd; PageInfo* roamingPtr; // allocation pointer @} where the {\tt roamingPtr} points to the first free page in the heap (after the last allocation). A possible arrangement of these pointers could be the following: \begin{figure}[h] \begin{center} \epsfig{file=Figure6.eps} \caption{Heap start and real heap start} \end{center} \end{figure} but other arrangements are possible as well; for example, the page-info table could reside at the end of the heap. Besides pointers the \gd\ class provides four variables that keep track of the stock of available pages. From their identifiers it is rather clear what each variable stores: {\tt heapPagesCount} counts the total of all pages---allocated and free ones---as the sum of {\tt caMaxAlloced} and {\tt caMinFree}; {\tt collectThreshold} measures the distance (in pages) to the initiation of the next collection phase. % @D gc\_data page counters @{ int collectThreshold; int heapPagesCount; int caMaxAlloced; int caMinFree; @} What are the values for each variable? The value of {\tt heapPagesCount} is upwards bound by the maximal size of the heap; %, that is $2^{\mbox{\tt sizeof(word)}}$ its lower bound is 0, since \fgc\ starts with a heap expansion step. The value of {\tt caMaxAlloced}, next, depends on the pseudo-constant {\tt POLICY\_MAX\_ALLOC()} which, as it is characteristic for a copying collector, divides the heap in two halves for the {\em To} and the {\em From} space. @D POLICY\_MAX\_ALLOCED() @{inline int POLICY_MAX_ALLOCED(int heapPageCount) { return heapPageCount / 2; } @} The variable {\tt collectThreshold}, finally, is upwards bound by {\tt caMaxAlloced} and downwards by the maximal size of an object, i.e., the number of pages to store an object of maximal size; {\tt collectThreshold} can take negative values after a big request. For an easy reference we summarize all values in the following table; the unit in all cases are {\em pages}. \begin{center} \begin{tabular}{|l|l|} \hline {\em Variable} & {\em Values} \\ \hline collectThreshold & $ 2^{\mbox{\tt sizeof(word)}}$/BYTES\_PER\_PAGE - 1 $ \leq x $ \\ & \mbox{\ \ } $\leq $ caMaxAlloced \\ heapPagesCount & 0 $\leq x \leq 2^{\mbox{\tt sizeof(word)}} $ \\ caMaxAlloced & 0 $ \leq x \leq $ { POLICY\_MAX\_ALLOC(heapPagesCount)} \\ caMinFree & heapPagesCount - caMaxAlloced \\ \hline \end{tabular} \end{center} Other quantities such as the number of actually used or the number of free pages now can easily be computed: @D gc\_data page counter functions @{ int allocedPages() const { return caMaxAlloced - collectThreshold; } int freePages() const { return caMinFree + collectThreshold; } int heapPages() const { return heapPagesCount; } @} and @D gc\_data::heapSpanPages() @{ word heapSpanPages() const { return (heapEnd - heapStart)/BYTES_PER_PAGE; } @} The third and last group of members concerned with heap-related tasks are functions to update the book-keeping variables discussed. Two procedures are to consider here: {\tt heapPagesAdd()}, called after each heap expansion, and {\tt freePagesAdd()}, called after each collection. The first function, {\tt heapPagesAdd()}, essentially adjusts the value of the collection threshold. It increases the heap counter {\tt heapPagesCount} by the number $n$ by which the heap got expanded, changes {\tt caMaxAlloced} and {\tt caMinFree} accordingly, and sets the new value of {\tt collectThreshold} as the difference of the new maximum {\tt caMaxAlloced} and the number of actually used pages. @D gc\_data::heapPagesAdd() @{ void heapPagesAdd(word n) { int a = allocedPages(); heapPagesCount += n; caMaxAlloced = POLICY_MAX_ALLOCED( heapPagesCount ); caMinFree = heapPagesCount - caMaxAlloced; collectThreshold = caMaxAlloced - a; printfree(); } @} The second function, {\tt freePagesAdd()}, also updates the threshold, but by the number of gained pages; after the collection phase obviously all recovered pages are available but also, additionally, all pages in the {\em To} space that were allocated during the collection: @D gc\_data::freePagesAdd() @{ void freePagesAdd(int before, int after, int unmovable) { int allocedDuringCollection = after - before; int survivedData = allocedDuringCollection + unmovable; int pagesRecovered = before - survivedData; collectThreshold += pagesRecovered + allocedDuringCollection; @< fprintf(stderr,"collection recovered \%d pages$\backslash$n", pagesRecovered); @> } @} \subsubsection{Allocation and collection}\label{allocationAndCollection} The previous subsection dealt with the pre-and postconditions of allocation and collection. We address now the global data that are important {\em during} either allocation or collection. Of them, the most important ones are the three variables @D gc\_data::xxSpace @{ unsigned short currentSpace, allocSpace, nextSpace; @} The purpose of these variables can best be understood by considering their impact on the individual page {\tt space} numbers. The first variable, {\tt nextSpace}, opens up a new collection cycle: \begin{verbatim} nextSpace = currentSpace + STEP_SIZE; \end{verbatim} All pages with space numbers assigned from then on necessarily survive the collection. The value of {\tt nextSpace} is a multiple of 4; the second variable {\tt allocSpace}, differing from {\tt nextSpace} by 3, \begin{verbatim} gc.allocSpace = gc.nextSpace | 3; // collection \end{verbatim} is to distinguish the {\em To} space in the copy-collecting sense---the space (small) objects are copied to---from space with objects that survive the conservative part of the collector.% \footnote{Increasing the variable {\tt gc.nextSpace} by 3 results in an odd value which indicates the page as queued (see the predicate {\tt inQueue()}).} The third variable, {\tt currentSpace}, finally, keeps the value up to which pages are free. After a collection, all three variables get identical values: \begin{verbatim} gc.allocSpace = gc.currentSpace = gc.nextSpace; \end{verbatim} and the cycle can start over again. \begin{figure}[h] \begin{center} \epsfig{file=Figure7.eps, width=11.5cm} \caption{Space numbers} \end{center} \end{figure} % Why working with increasing page numbers instead of the classical {\em To} and {\em From} flags?\footnote{The concept of a generational collector has already modified the plain binary {\em To}/{\em From} flag.} As should be obvious now, the advantage is that different kinds of pages can be directly identified---increasing space numbers allow for distinctions between free and used pages, between copy-collected and mark-but-not-swept survivors, and also, as we will see in the next paragraph, between {\em grey} and {\em black} pages. Increasing space numbers require of course special means at the boundary of {\tt MAX\_SPACE}-many pages, to handle overflow properly. We will come to overflow handling in the first section on the collector. For now, let us go back to the step size according to which the variable {\tt nextSpace} grows. Obviously, it holds {\tt STEP\_SIZE} = 4 because there are four different states for pages. But which are the four states? Roughly, each of the conservative and the copy-collection part of the hybrid \fgc \ claim two states for themselves. @D colors @{ #define scannedWired (gc.nextSpace+0) #define wiredInQueue (gc.nextSpace+1) #define grey (gc.nextSpace+2) #define black (gc.nextSpace+3) @} Let us start with {\em grey} and {\em black} pages, the terminology introduced by Dijkstra et al. \cite{DLM78} for classical copy collectors. To recall the definition briefly, {\em grey objects} and {\em black objects} both denote objects in the {\em To} space, but {\em black objects} are completely processed whereas {\em grey objects} have their descendants not yet been scanned. While Dijkstra's et. al. deal with objects, we deal with pages. In analogy to their terminology we denote by a {\em grey page} a page with copy-collected objects that is in the process of being scanned, and we denote by a {\em black page} a page that either is completely scanned or does not have to be scanned--- {``big pages"} which, per definition, are excluded from being moved. For \fgc 's conservative mark-sweep part we make a similar difference and distinguish between {\em scannedWired} pages and {\em wiredInQueue} pages. The four different states for pages, or the four ``colors", now explain why {\tt STEP\_SIZE=4}. % \begin{figure}[h] \begin{center} \epsfig{file=Figure8.eps, width=11.5cm} \caption{Space colors} \end{center} \end{figure} % We conclude this subsection with the declaration of three instances of the class {\tt PageInfoQueue} which collect in scanning queues the three different categories of pages. @D gc\_data PageInfoQueue @{ PageInfo* pageBeingScanned; bool repeat; PageInfoQueue bigObjects_q; PageInfoQueue wiredPages_q; PageInfoQueue normalPages_q; @} \subsubsection{Construction} In the \cpp\ object model, construction and initialization happens in a half-automated way. Unless otherwise arranged, the code generator of a \cpp \ compiler, when processing a variable declaration (of a class instance), automatically invokes the default constructor of the class. In order to complete the construction, this class' default constructor initiates the invocation of the default constructors of all its class members (and base classes, which, however, are irrelevant in our context). Construction in \cpp \ generally does not imply initialization; providing appropriate initial values, is part of the design of a default constructor. The default constructor of the \gd\ class does not provide initial values. Such deviation from the standard design of default constructors is legitimate since the use of \gd\ class is very limited---it is used exactly once, through a variable called {\tt gc}, which in turn is declared in the global namespace. Global variables, however, are static variables, which, contrary to others, are initialized (``zero-initialized"). Any default initialization inside the default constructor would duplicate their initialization---and can be omitted, therefore. The task left to the constructor is to provide the opportunity for users to overwrite certain program constants. The three (pseudo-)constants which users possibly want to change are {\tt INI\-TIAL\-\_HEAP\-\_SIZE}, {\tt TOO\_BIG\_TO\_MOVE}, and, as a third quantity, an implicit constant that controls the amount of pages by which the heap is growing. The first constant, {\tt INI\-TIAL\-\_HEAP\-\_SIZE}, determines the number of pages for the very first heap expansion, the second one, {\tt TOO\_BIG\_TO\_MOVE}, defines what is considered to be a big object. Their default values are (in pages) \begin{center} \begin{tabular}{|l|ll|} \hline {\em Name} & {\em Default value} & \\ \hline {\tt INITIAL\_HEAP\_SIZE} & 30 & \\ {\tt TOO\_BIG\_TO\_MOVE} & 19 &\\ \hline \end{tabular} \end{center} % Concerning the rate by which the heap is increased in each expandsion step, its size is doubled, by default. All three constants are defined in the file {\tt const.cc}, and all of them can be overwritten, using environment variables. In the first two cases, the environment variables {\tt FGC\_INITIAL\_HEAP\_SIZE} and {\tt FGC\_TOO\_BIG\_TO\_MOVE} change the values of the corresponding constant directly. We set the variable {\tt initialHeapSize} @D determine initial heap size @{ ptr = getenv("FGC_INITIAL_HEAP_SIZE"); initialHeapSize = ptr ? atoi(ptr) : 0; if(initialHeapSize < INITIAL_HEAP_SIZE) initialHeapSize = INITIAL_HEAP_SIZE; @} and the variable {\tt tooManyBytesToMove}, respectively: @D define what a big object is @{ ptr = getenv("FGC_TOO_BIG_TO_MOVE"); tooManyBytesToMove = ptr ? atoi(ptr) : 0; if(tooManyBytesToMove < TOO_BIG_TO_MOVE) tooManyBytesToMove = TOO_BIG_TO_MOVE; tooManyBytesToMove *= BYTES_PER_PAGE; @} In the third case, the change of the policy of heap increments, the environment variable {\tt FGC\_HEAP\_INCREMENT} communicates with the local variable {\tt heapIncrement}. @D determine heap increment policy @{ ptr = getenv("FGC_HEAP_INCREMENT"); heapIncrement = ptr ? atoi(ptr) : 0; if(heapIncrement < 0) heapIncrement = 0; @} Overwriting default settings essentially is all the default constructor of the \gd\ class does. The only additional call at the end of the function body @D exclude gc object from root detection @{ sysdep.excludeRange( ptr_t(this) , ptr_t(this+1) ); @} is done in support of the conservative part of \fgc; it excludes the region in the stack that the \gd\ object occupies from any further tracing. @D gc\_data::gc\_data() @{ gc_data(){ char* ptr; @< determine initial heap size @> @< define what a big object is @> @< determine heap increment policy @> @< exclude gc object from root detection @> } @} As pointed out above, not all data members of the \gc \ class (have to) appear in the constructor body. To mention two important data members at least by name, we list their declaration, @D gc\_data member classes @{ SmallSize smallSize; SysDep sysdep; @} but we postpone commenting in detail on them. The type of the first one, {\tt SmallSize}, is subject of the next subsection; the type of the second one, {\tt SysDep}, constitutes the whole interface to the underlying operating system and is presented in a separate section. \subsection{The class \scl}\label{TheClassScl} Allocation in classical copy collectors is cheap. Enough space in the {\em To} space provided, allocation means incrementing a free space pointer, by the size of the allocated object. On the other hand, all objects participating in garbage collection have to be scanned recursively for internal pointers. For this purpose they have to be accessed and for that, in particular their size must be known. How to get the object size? The object size could be stored, explicitly, either in the objects themselves or in external tables, but such policy incurs overhead for every object. We pursue a segregation policy instead, placing on a given page only objects of the same small size. With segregation, one entry for a whole page---the variable {\pgi}{\tt ::size}---is sufficient to code the size of all objects residing on the page. Two data structures, the class {\tt SizeClass} and the class {\tt SmallSize}, support the segregation policy. We discuss the first class first; the second class rather is a helper class. As already said, the class {\tt SizeClass} deals with the allocation of objects of the same small size {\tt sz}. The class contains three variables denoting different positions within a page, @D SizeClass position variables @{ char* pageStart; short top; short classTop; static const unsigned char invalid=255; @} two tables to convert offsets into object numbers, @D SizeClass tables @{ unsigned char objectNo[BYTES_PER_PAGE]; unsigned char objectStart[BYTES_PER_PAGE]; @} and, furthermore, four member functions: an initialization function {\tt init()} together with three allocation-related functions: @D SizeClass allocation and collection @{ char* alloc(int size); char* allocDuringCollection(int size); void prepareForCollect(); @} With the exception of the two allocation functions, subject of a later section, we discuss each member now. \subsubsection{Data members} The three position variables, as obvious from their name, point to the beginning of the current page ({\tt pageStart}), to the offset of the last allocated object ({\tt top}), and to the largest possible offset of an object in a page ({\tt classTop}); if the size of these objects is a power of 2, the value of {\tt classTop} equals {\tt PAGE\_SIZE-sizeof(object)}. \begin{figure}[h] \begin{center} \epsfig{file=Figure9.eps, height=2cm} \\ \caption{Page with small objects} \end{center} \end{figure} All three variables initially are set to 0. Once the page is in use, {\tt pageStart} keeps the byte address of the page. The other two variables carry the following values (in words): \begin{center} \begin{tabular}{|l|l|c|} \hline {\em Variable name} & {\em Value } & {\em Initial}\\ \hline pageStart & {\em (byte address)} & 0\\ top & 0 $\leq x \leq $ classTop &0 \\ classTop & {\tt PAGE\_SIZE}/3 + 1 $\leq x \leq $ {\tt PAGE\_SIZE} - 4 & 0\\ \hline \end{tabular} \end{center} % Next to discuss are the two tables {\tt objectNo} and {\tt objectStart}, which both store pre-computed offsets. For each byte on the page, {\tt objectNo} stores the number of the object which the byte belongs to; {\tt objectStart} stores the offset from the byte to the begin of the object it is part of. Both offsets are zero-based; invalid offsets carry the value -1. %\begin{figure}[h] %\begin{center} %\epsfig{file=Figure10.eps, width=11.5cm} %\caption{The table objectStart with sz=5} %\end{center} %\end{figure} \begin{figure}[h] \begin{center} \epsfig{file=Figure11.eps, width=11.5cm} \caption{The table objectNo with sz=5} \end{center} \end{figure} % Two different kinds of initialization take place within the class \scl . One is the initialization of its data members; this task is done by the function {\tt init()}. The second initialization refers to the entry in the page-info table that describes a given page; this task is done by the function {\tt prepareForCollect()}. We look at the {\tt init()} function first. \subsubsection{Initializing data members}\label{InitializingDataMembers} The core of the initialization function {\tt init()} describes the block that deals with the two offset tables, {\tt objectStart} and {\tt objectNo}. The table {\tt objectStart} stores for each byte on page which $n$-th byte it is of an object; the table {\tt objectNo} stores to which $n$-th object a byte belongs to. Given the size {\tt sz} of the objects on the current page, the function loops over the two tables and initializes their entries insofar valid pages correspond to them. Each first byte of an object in the {\tt objectStart} table carries the special value {\tt sz}. If a user-defined pointer hits the first cell after an object---such as the {\tt end-of-storage} pointer in a STL vector or pointers after strings---it points to this first byte and we can retrieve the value there to adjust the pointer to the beginning of the word it ``belongs" to. @D initialize offset tables @{ sz *= BYTES_PER_WORD; int i = 0; int count = 0; while(i + sz <= pageSize) { for(int j = 0; j < sz; ++j) { objectStart[i+j] = (j ? j : sz); // EOS ptr objectNo[i+j] = count; } ++count; i += sz; } @} Invalid offsets are marked with -1: @D mark invalid offsets @{ if (i < pageSize) { objectStart[i]=sz; objectNo[i]= invalid; ++i; } while(i < pageSize) { objectStart[i] = invalid; objectNo[i] = invalid; ++i; } @} What is an invalid offset? Obviously invalid are all bytes on a page that remain when the object-size does not divide the page-size. But there is also another case, which depends on the value of the variable {\tt pagesize}: @D compute pagesize @{ int pageSize = BYTES_PER_PAGE; if( sz < 4 ) pageSize -= 4 * BYTES_PER_WORD; // live3/4,scanned2,toScan2 else if( sz < 8 ) pageSize -= 1 * BYTES_PER_WORD; // live2 @} The value of {\tt pageSize} implies that for objects of size less than 8 the page cannot be used in its entire. More precisely, for pages with objects of size 2,3 there are 4 words reserved and for pages with objects of size 4,5, and 6 there is one word reserved. What are the reserved words used for and why are they taken from pages for small objects? For the answer we have to go back to the data structure \gd\ and its member union which contains two bitmaps {\tt toScan, scanned} for wired pages: \begin{verbatim} union { struct { word toScan, scanned; } wired; struct { unsigned short live, toScan; word scanned; } wired2; // ... }; \end{verbatim} When we discussed the anonymous union we already remarked that a {\tt word}, if considered as bitmap with one bit per object, is not large enough to describe pages with objects of size 2 and 3; a word-bitmap captures $32$ objects but these pages contain {\tt WORDS\_PER\_PAGE}/2 (3), i.e., 64 (42) objects. By adjusting the local variable {\tt pageSize}, $2\cdot 2$ extra words are available to store the two bitmaps {\tt toScan2} and {\tt scanned2}. These additional two bitmaps then are sufficient to flag up the 33rd object and all subsequent ones for pages of size 2,3. However, we reserve more than two words and we also reserve one word for objects of size greater than 2,3 (and less than 8). What is this space good for? In the discussion of the anonymous union we also briefly mentioned the purpose of the bitmap {\tt live}, which stores which objects on a page are live. This information, for a normal page implicitly available through the pointers {\tt from} and {\tt to}, otherwise would get lost when a page becomes wired and the scan procedure would scan objects that are not there any more. With an argument similar to the one for the scanning bitmaps is now easy to see that for pages with objects of size 2,3 two words are necessary to keep the {\tt live} bitmap, for pages with objects of size 4,5, and 6 one word suffices. For all other pages the live bitmap can be stored in an unsigned short in the instance {\tt wired2} of the anonymous union. With these special cases in mind, the function {\tt init()} is straightforward implemented: @D SizeClass::init() @{ void init(int sz) { @< compute pagesize @> @< initialize offset tables @> this->classTop = i - sz; @< mark invalid offsets @> top = 0; pageStart = 0; } @} \subsubsection{Updating the page-info table} Initializing data members is one task, initializing the page-info table another one. In this section we present the function {\tt pre\-pare\-For\-Collect()} which initializes the entry in the page-info table that describes the current page. Pages with small objects---and we are concerned with no others in the entire section--- belong to the category of {normal pages}; normal pages have two members {\tt from} and {\tt to} that indicate the first and the last element on a page (see the subsection on the \pgi \ class). The function {\tt prepareForCollect} initializes {\tt from} with {\tt classTop} and {\tt to} with {\tt top} (note that we are allocating backwards, from {\tt classTop} towards {\tt top}). To lock the page against further access during the collection phase, {\tt pageStart} and {\tt top} then are reset to their initial values 0. @D SizeClass::prepareForCollect() @{void SizeClass::prepareForCollect() { if(!pageStart) return; // no objects on the page PageInfo* p = PageInfoFromPageStart( pageStart ); p->normal.from = classTop; p->normal.to = top; pageStart = 0; top = 0; } @} Inside {\tt prepareForCollect()}, the function {\tt PageInfoFromPageStart} is used. This function is one of the---admittedly tedious---conversion functions we explain in the next subsection. Before getting there, however, we briefly look at the helper class {\tt SmallSize}. \subsubsection{The array class {\tt SmallSize}} The class {\tt SmallSize} is an interface class in the sense that it does not provide any implementation on its own but forwards all allocation and conversion requests to the methods of the corresponding {\tt SizeClass} object. Its initializer calls the initializer of the {\scl} class, \scl{\tt ::init()}, its allocators call the allocators of {\tt SizeClass}, and its functions {\tt objectStart()}, {\tt objectNo()}, and {\tt userObjectNo()} initialize the tables for the \scl\ of a given size {\tt i}. Please note the difference between the two functions {\tt objectNo()} and {\tt userObjectNo()} which reflect two different views on an object. From the users' view the very first word of an object is not visible---it keeps the internally attached traverse function. On the other hand, it is legal from the users view to point to the location directly after an allocated object (e.g., the {\tt end-of-storage} pointer in the STL vector). Converserly, it is legal inside the collector to point to an object's first word and illegal to point after the end of an object. The function {\tt objectNo()} therefore returns directly the value that the corresponding index in the table {\tt objectNo()} has while the function {\tt userObjectNo()} first shifts the index by 1. The only data member of the {\tt SmallSize} class is an array of \scl\ elements. The array {\tt sz} is of size \begin{verbatim} SMALL_SIZE = BYTES_PER_PAGE/2/BYTES_PER_WORD = 64 \end{verbatim} reflecting that there is an instance of the class \scl \ for each small size. The implementation shows that the array is initialized only for the second and all subsequent indices; this is sufficient, since there are no objects of size 0 or 1 word. Altogether, the class {\tt SmallSize} reads as follows: % @D SmallSize @{ @< SMALL\_SIZE @> struct SmallSize { SizeClass sz[SMALL_SIZE]; public: SmallSize() { for(int i = 2; i < SMALL_SIZE; ++i) sz[i].init(i); } char* alloc(int i) { return sz[i].alloc(i); } char* allocDuringCollection(int i) { return sz[i].allocDuringCollection(i); } int objectNo(int i, int offset) { return sz[i].objectNo[offset]; } int userObjectNo(int i, int offset) { return sz[i].objectNo[offset-1]; } // 0< 512 <= offset int objectStart(int i, int offset) { return sz[i].objectStart[offset]; } void prepareForCollect() { for(int i = 2; i < SMALL_SIZE; ++i) sz[i].prepareForCollect(); } }; @} \subsection{Auxiliary functions} In this section we present a few small functions, including two important mappings between the page-info table and the heap, the pseudo-constant {\tt PStoPIconstant} and the function {\tt PageInfoFromPageStart()}. The pseudo-constant {\tt PStoPIconstant} is the counterpart to another pseudo-constant we already encountered: {\tt PItoPSconstant}, the latter one going from the page-info table to a page and the former one the other way around. Both pseudo-constants assume that the start of the heap and of the page-info table are known, both also take advantage of the direct correspondence between heap and page-info table. In case of {\tt PStoPIconstant} the following equation holds: \begin{verbatim} PageInfo[x] = PageInfo[0] + (p - heapStart)/PAGEINFOS_PER_PAGE \end{verbatim} where {\tt p} denotes a pointer into the heap. Rearraning the equation yields \begin{verbatim} PageInfo[x] = p/PAGEINFOS_PER_PAGE + PageInfo[0] - heapStart/PAGEINFOS_PER_PAGE =: p/PAGEINFOS_PER_PAGE + PStoPIconstant \end{verbatim} % To yield a type-correct \cpp \ expression, an additionally cast is necessary, from the \pgi\ pointer {\tt gc.pageInfos} to its first {\tt word}: @D gc::PStoPIconstant @{ gc.PStoPIconstant = word(gc.pageInfos) - gc.heapStart/PAGEINFOS_PER_PAGE; @} The pseudo-constant {\tt PStoPIconstant} can be used to determine the entry in the page-info table that corresponds to a page in the heap a given pointer {\tt p} points to. @D PageInfoFromPageStart() @{ inline PageInfo* PageInfoFromPageStart(char* p) { if(! ( (word(p) >= gc.heapStart && word(p) < gc.heapEnd ) ) ) { fprintf(stderr,"[%d %d) %d\n", gc.heapStart, gc.heapEnd, p); } return PageInfoPtr(word(p) / PAGEINFOS_PER_PAGE + gc.PStoPIconstant); } @} The function {\tt PageInfoFromPageStart()} is used at different points during the \fgc\ program, both in the heap expansion step and in the marking phases; it collaborates with the function {\tt PageStart()}: @D PageStart() @{ inline char* PageStart(word p) { return (char*)(p & ~(BYTES_PER_PAGE-1)); } @} The remaining functions in this section are easy to understand. The first one, {\tt alignUp()}, is used to ``align" the collector's request for memory up to the chunks in which the operating system allocates. @D alignUp() @{ inline size_t alignUp(size_t sz, size_t chunkSize) { --chunkSize; return (sz + chunkSize) & ~chunkSize; } @} The other functions provide access to the two bitmaps {\tt toScan2(), scanned2()}, which are stored in the two last words on pages for object of size 2,3 and to the live-bitmap, which, depending on the size of the objects, occupies the last 4, 3, or 2 words on a page. @D toScan2(), scanned2() @{ inline word& toScan2(char* p) { return wordPtr(p)[126]; } inline word& scanned2(char* p) { return wordPtr(p)[127]; } inline word& live2 (char* p) { return wordPtr(p)[127]; } inline word& live3 (char* p) { return wordPtr(p)[124]; } inline word& live4 (char* p) { return wordPtr(p)[125]; } @} The subsection on auxiliary functions concludes the presentation of the data structures used within \fgc . \section{Collection} With this section we begin the discussion of the functional part of the \fgc\ collector. The discussion is divided up into 5 sections, the three first of which address the collection part and the two remaining ones the allocation part. The collection part includes scanning, marking, and, as the entry point, the function {\tt collect()} which is called when allocation fails. In this section we explain how the function {\tt collect()} prepares the collection and synchronizes the single collection steps. Its signature reads as follows: \begin{verbatim} void collect(int nPages, char* reason=0); \end{verbatim} where the parameter {\tt nPages} reflects the request by the allocator; if the {\tt collect()} function is directly called by users this parameter might carry the value 0, too. In this latter case the second parameter {\tt reason} is initialized with the string {\tt "forced"}; in all other cases the string is left empty. The implementation of the {\tt collect()} function is not much more complex than as already described in the overview section. Its major parts are the following ones: @D collect @{ @< prepare collection @> @< mark pages accessible from roots @> scan(); @< update heap and space variables @> @} We discuss the four parts in the order in which they appear. \subsection{Preparation} By far the largest of the four parts is the preparation step. Roughly, it deals with three different tasks: @D prepare collection @{ @< expansion necessary? @> @< overflow handling of space numbers @> @< set global variables @> @} The preparation starts with a check that makes sure that the potential success of {\tt collect()} is compliant with the general heap policy. If more than {\tt caMaxAlloced/2}---the threshold for heap expansion---are requested, we expand the heap immediately instead of doing so later. @D expansion necessary? @{ if(nPages > gc.caMaxAlloced/2) { expand(nPages, "big alloc request"); return; } ++gc.collectionCount; @} If no expansion is necessary, the global collection variables get their new values and the function {\tt prepareForCollect()} initializes the page-info table: @D set global variables @{ gc.nextSpace = gc.currentSpace + SPACE_STEP; gc.allocSpace = gc.nextSpace | 3; gc.smallSize.prepareForCollect(); @< book-keeping variables @> @} We already encountered (see \ref{allocationAndCollection}) the three variables {\tt next\-Space}, {\tt current\-Space} and {\tt allocSpace}; we observe here again, that the collection starts with the separation of {\tt nextSpace} from {\tt currentSpace} and {\tt allocSpace} from {\tt nextSpace}. % % % Now, what if we are running out of space numbers? Both {\tt gc.currentSpace} and {\tt gc.allocSpace} (and following {\tt gc.currentSpace}) are increased continuously. What, if we have reached {\tt MAX\_SPACE}? Obviously, we have to restart counting again and for that, we have to set {\tt gc.currentSpace} and {\tt gc.nextSpace} to their initial value {\tt SPACE\_STEP}=4. Having done that, however, means having invalidated the program invariant according to which the old space always carries a number strict less than the new space. To reinstate the program invariant, all space numbers have to be corrected: we have to go through the whole page-information table, to mark free pages with 0---the value of the virtual previous current space---and non-free pages with the value of the actual current space; pages with objects that do not participate in garbage collection ({``unusable pages"}) may be skipped, of course. % @D overflow handling of space numbers @{ if(gc.currentSpace >= MAX_SPACE) { PageInfo * p = gc.pageInfos; while(p < gc.pageInfosEnd) if(p->unusable()) p = p->skip(); else { p->space = ( p->free() ) ? 0 : SPACE_STEP; ++p; } gc.currentSpace = gc.nextSpace = SPACE_STEP; } @} The preparation steps done, the collection in a strict sense can be launched. \subsection{Root detection} Rather canonical, the first collection step is to detect root pointers. In a (partially) uncooperative environment like ours, however, where the areas of root pointers are not under control of the garbage collector, heuristics apply. Their development, in particular their application to different platforms, requires a lot of work and expertise. At that point we greatly take advantage of the {\em B{\"o}hm-Weiser-Demers} collector. Although being a mark-sweep collector, its root detection parts are perfectly utizilable for the conservative part of \fgc ---provided we interface their collector appropriately. For the discussion in this section we assume an interface and refeor to the section on the class {\tt SysDep} for a presentation of the interface; this class encapsulates all system-dependent tasks. Given such interface, all we have to do then is to pass on some information: the start and end address of the heap and the tracer function {\tt markFromRoot()}; the root detection itself happens inside the {\tt setEnumParams()} function. When {\tt setEnumParams()} returns the region of the program stack which it supposedly had used the stack gets cleaned with a (rather arbitrary) number of 0's.\footnote{We adopt the nullification heuristic direcly from the \BDW\ collector.} @D mark pages accessible from roots @{ gc.sysdep.setEnumParams(markFromRoot, wordPtr(gc.heapStart), wordPtr(gc.heapEnd)); gc.sysdep.enumRoots(0,0,0,0,0,0,0,0,0,0); @} After the root detection phase all pages hit by root pointers are waiting in queues for further scanning---the next level of pointers has to be followed. The procedure {\tt scan()} addresses the entire task; its detailed presentation is subject of the next section. \subsection{Updating global variables} Suppose scanning is done, what is left to do? First, the space variables {\tt gc.currentSpace} and {\tt gc.allocSpace} must be set to the value of {\tt gc.nextSpace}. Second, we have to check whether the {\tt collect()} function has finished successfully---the resulting number of allocated pages might not yet be high enough. As the last step in the {\tt collect()} function, therefore, we compare the updated value of {\tt gc.allocedPages()} with the number of pages in the heap. Only if {\tt gc.allocedPages()} is at least twice as large as {\tt gc.heapPages()/2},% \footnote{Note that the number 2 is used here in two different meanings: as the halving of the heap in{\em To} and {\em From} space in the latter case and as the expansion factor in the first case.} the default limit for heap expansion, the collection has been successful. Otherwise, the heap must be expanded. @D update heap and space variables @{ gc.allocSpace = gc.nextSpace | 2; gc.currentSpace = gc.nextSpace; @< trace\_collect @> gc.freePagesAdd( allocedBeforeCollection, gc.allocedPages(), gc.unmovablePagesCount ); if( gc.allocedPages() > gc.heapPages()/4 ) { expand(nPages, "not enough pages recovered by collect"); } @} \section{Scanning} The scanning phase starts after the conservative part of \fgc , interfaced by the function {\tt markFromRoot()}, has marked all pages that are hit by roots, i.e., pointers in registers, the stack, or the static area. The root detection itself is imprecise, since the program stack etc. are not under control of \fgc. Once a page in the heap is reached, however, all pointers starting from there are precisely detected, with the help of user-defined traverse functions. In this section we address the recursive step of the collection, in which pointers from and to the heap are followed up. We explain the different scanning policies for pointers to {\em big, normal}, or {\em wired pages} and show how to access the user-defined traverse functions. \subsection{Access to the user-defined traverse function} For each user-defined class there exists a trace function that helps traversing the class to determine its internal pointers. To the \fgc\ collector, the address of the traverse function is known; it is passed as an argument to the allocator part. When the allocator allocates space for an object, it allocates one extra word---which explains the overhead of one word for each object that gets garbage collected---and stores the pointer to the traverse function so that it appears to be the {\em first word } of the object. Of course, this amalgamation is done transparently to users. % \begin{figure}[h] \begin{center} \epsfig{file=Figure12.eps, width=5cm} \\ \caption{Attached traverse function} \end{center} \end{figure} % This memory layout provided, it is clear how to scan a single object. The function {\tt callTraverse()} accesses the field -1, where the traverse function is kept, stores the traverse function as {\tt f} and dereferences {\tt f}. The body of {\tt f} can be applied to the object (identified with its base address, {\tt ObjStart}) that is passed to {\tt callTraverse() } as an argument; qua definition the traverse function knows where to locate internal pointers. As additional safety measures we check whether the location {\tt ObjStart[-1]} contains a zero or a forwarded object; for the dereferenced variable we also check whether it points to a place within the heap. @D callTraverse() @{ inline void callTraverse(char* ObjStart) { register TraverseFunc f = TraverseFuncPtr(ObjStart)[-1]; @< if TRACE\_TRAVERSE defined, print f @> if(f && !forwarded((word)f) && !((unsigned int)*f >= gc.realHeapStart && (unsigned int)*f <= gc.realHeapEnd) ) (*f)((void *)ObjStart); } @} % Having the traverse function available for each {\em object}, what is the scanning policy for entire pages and for the different categories of pages? {\em Normal pages}, to recall the definition briefly, are pages with objects of medium size (that are not ``too big" to copy). These pages are scanned from the beginning to the end; the traverse function is object-wise retrieved and applied. {\em Wired pages}, in contrast, are not scanned thoroughly. Instead, their descriptor {\tt toScan} is looked up and only the objects marked there are further processed. {\em Big pages}, finally, do not have to be scanned in the strict sense. Once the single object that a big page holds is processed there is nothing else on that page waiting for further examinations. Browsing objects and pages is recursive insofar all pages reached have to be scanned as well. Accordingly, the {\tt scan()} function loops over the various scanning queues: % @D scan() @{ static void scan() { PageInfo* page = gc.wiredPages_q.getHead(); do { @< scan queue of wired pages @> @< scan queue of normal pages @> @< scan queue of big pages @> } while(!gc.normalPages_q.empty() || !gc.wiredPages_q.empty()); } @} (It is not necessary to check for an empty queue {\tt gc.bigPages\_q}: if a {big page} is hit from another {big page} none of the two moves and none of the two has to be updated--- nothing has to be done, therefore.) To protect the namespace of the function {\tt scan()} we specify internal linkage for it, via the function declarator {\tt static}. Let us now look in some detail into the various scanning procedures. In all three cases the very first instruction clears the flag which indicates the page as staying in the queue, to determine if a page is touched a second time. \begin{verbatim} void clearInQueueFlag() { assert(space&1); space -= 1; } \end{verbatim} Resetting the queue-flag has a side effect on the status of the page: A page of status {\tt wiredInQueue} changes to {\tt scannedWired}, and a page of status {\tt allocSpace} becomes {\tt grey}: \begin{center} \begin{tabular}{|l|l|} \hline {\em Space number (old)} & {\em Space number (new)} \\ \hline {\tt wiredInQueue=nextSpace+1} & {\tt scannedWired=nextSpace} \\ {\tt allocSpace=nextSpace+3} & {\tt grey=nextSpace+2} \\ \hline \end{tabular} \end{center} Like we said, cleaning the flag is the same for all kinds of pages. All further operations, however, vary with the kind of page. In the following subsections we go through each of the three scanning procedures, starting with {wired pages}. \subsection{Wired Pages} Scanning of wired pages means to loop through the scanning queue and to call {\tt scanWired()} for each page; after every page in the queue has been scanned the queue as a whole is voided. @D scan queue of wired pages @{ page = gc.wiredPages_q.getHead(); @< fprintf(stderr,"scanning wired...$\backslash$n"); @> while(page) { page -> clearInQueueFlag(); scanWired(page); page = page->next; } gc.wiredPages_q.clear(); @} What happens in the main function {\tt scanWired()}? Wired pages, as discussed in the introduction of the class \gd, are represented by two bitmaps, {\tt toScan} and {\tt scanned}. When the function {\tt scanWired()} starts, the bitmap {\tt toScan} has been initialized by the function {\tt markFromRoot()} and can therefore be used to infer which objects have to be scanned and where their traverse function is located. For the inference, {\tt scanWired()} generates a synthezised bitmap that (using a logical {\em and} operation) filters the objects on the page that have to be scanned but have not be scanned yet. Depending on the object size, it uses the {\tt toScan} bitmap either of a {\tt wired} page or the {\tt wired2} page. % @D yet to be scanned @{ pageInfo->size < 8 ? pageInfo->wired.toScan & ~(pageInfo->wired.scanned) : word(pageInfo->wired2.toScan) & ~(pageInfo->wired.scanned); @} Anticipating the outcome of the scanning process, the bitmap {\tt wired.scanned} gets updated by the newly created bitmap {\tt b}: % @D update wired.scanned @{ pageInfo->wired.scanned |= b; @} Preparing a loop through the new bitmap, next, we get the base address of the first object on the page, that is, the start of the page shifted by the size of (the pointer to) the object's traverse function. % @D address of first object on page @{ pageStart + sizeof(TraverseFunc); @} Now we are ready to loop through the bitmap. If its first bit is set, we apply {\tt callTraverse()} to the corresponding object; if it is not set, we go to the beginning of the next object and start over again: @D loop through bitmap b @{ do { if(b & 1) callTraverse(p); p += sz; } while( b >>=1 ); @} All pages we hit while following pointers are entered in the appropriate scanning queue. What happens, however, if we hit our own page? For a {wired page} this implies a change of the original {\tt toScan} bitmap which in turn means that the {\tt scanWired()} procedure has to be repeated; whether or not this case occurs is controlled by the variable {\tt gc.repeat}. The function {\tt scanWired()} now reads as follows: @D scanWired() @{ static inline void scanWired(PageInfo* pageInfo) { short sz = pageInfo->size * BYTES_PER_WORD; char* pageStart = pageInfo->data(); gc.pageBeingScanned = pageInfo; do { gc.repeat = 0; word b = @< yet to be scanned @> if(b) { @< update wired.scanned @> char* p = @< address of first object on page @> @< loop through bitmap b @> } @< continue for objectsize 2,3 @> } while(gc.repeat); } @} The only thing left to explain is the exceptional case for objects of size 2 and 3 words. But this is easy to understand if we remember that the two regular bitmaps {\tt toScan} and {\tt scanned} are too small for pages with objects of size 2 or 3. In section \ref{InitializingDataMembers} we have already seen that these kinds of pages get two additional bitmaps, called {\tt toScan2} and {\tt scanned2}. What does the objectsize 2,3 mean in our current context of {\tt scanWired()}? It requires extending the scanning process to these additional two bitmaps. The program logic in this extra step is exactly the same as for the first two bitmaps; of course, the base case of the loop is not the address of the {\em first} object on the page but of the ({\tt BITS\_PER\_WORD * sz})-th one. @D continue for objectsize 2,3 @{ if(sz < 16) { word b = toScan2(pageStart) & ~scanned2(pageStart); if(b) { scanned2(pageStart) |= b; char* p = pageStart + sizeof(TraverseFunc) + BITS_PER_WORD * sz; do { if(b & 1) callTraverse(p); p += sz; } while(b >>=1) ; } } @} This special case concludes our considerations of wired pages. How are {normal pages} scanned? \subsection{Normal pages} The body of the scan process of normal pages looks similar to the one for {wired pages}: % @D scan queue of normal pages @{ @< fprintf(stderr,"scanning normal...$\backslash$n"); @> page = gc.normalPages_q.getHead(); while(page) { page -> clearInQueueFlag(); scanNormal(page); page = page->next; } gc.pageBeingScanned = 0; gc.normalPages_q.clear(); @} with the main function here being called {\tt scanNormal()}. In contrast to its counterpart {\tt scanWired()}, however, {\tt scanNormal()} scans all objects on a page, i.e., it sequentially steps through the normal page and calls the traverse function for each object on the page: @D breadth-first traversal @{ while(p >= stop) { for (; p >= stop; p -= sz) callTraverse(p); if(gc.smallSize.sz[page->size].pageStart == ps) { top = gc.smallSize.sz[page->size].top; } else { top = 0; } stop=ps + top + sizeof(TraverseFunc); } @} In this implementation, the dependency graph of objects is visited in a breadth-first manner. One might wonder whether depth-first traversal is superior to breadth-first traversal. Generally speaking, breadth-first traversal, hence breadth-first copying groups children of the same generation, while depth-first copying groups children together with their ancestors. Depth-first copying, in theory, therefore seems to keep more likely on one page objects that logically belong together. In practice, the answer depends on the concrete shape of the particular data structures and the topology of the particular program. Where hash tables are used, for example, any spatial relation of logically related objects yet is resolved (see \cite{WLM91}, quoted after \cite{JoLi96}). Here is the entire function {\tt scanNormal()}: % @D scanNormal() @{ static inline void scanNormal(PageInfo* page) { int sz = page->size * BYTES_PER_WORD; char* ps = page->data(); char* p = ps + page->normal.from + sizeof(TraverseFunc); gc.pageBeingScanned = page; if(gc.smallSize.sz[page->size].pageStart == ps) { short top = gc.smallSize.sz[page->size].top; char* stop=ps + top + sizeof(TraverseFunc); @< breadth-first traversal @> page->normal.from = top - sz; } else { for (; p >= ps + sizeof(TraverseFunc); p -= sz) callTraverse(p); } } @} \subsection{Big pages} Big pages, to wind up the section, are rather straightforward to process. We loop through the queue of big pages as before, without resetting the {\tt clear\-In\-Queue\-Flag()} however---once a big page is processed, its only object has been scanned and there is no other object on the page that would force rescanning. % @D scan queue of big pages @{ @< fprintf(stderr,"scanning big...$\backslash$n"); @> page = gc.bigObjects_q.getHead(); while(page) { scanBig(page); page = page->next; } gc.bigObjects_q.clear(); @} The function {\tt scanBig()} itself has nothing to do than to retrieve the traverse function, to dereference it ({\tt *obj}), and to apply its function body to the big object, starting at address {\tt obj + 1}: % @D scanBig() @{ static inline void scanBig(PageInfo* pageInfo) { TraverseFuncPtr obj = TraverseFuncPtr( pageInfo->data() ); if(*obj) (*obj)(obj + 1); } @} \section{Marking} Garbage collection generally distinguishes two kind of pointers: root pointers and others. In a \mcc \ the distinction between root and other pointers also implies the distinction between imprecise and precise pointer detection. In a \mcc , it makes a difference whether a page is hit by a root or a non-root pointer; correspondingly, the two kinds of pages are differently processed. In our presentation we already encountered the procedure {\tt markFromRoot()}, which processes pages hit by root pointers. We will encounter now a related procedure, {\tt moveOrMark()}, that processes pages hit by non-root pointers. For both procedures, {\tt markFromRoot()} and {\tt moveOrMark()}, it is important to recognize ``wrong" pointers. We therefore precede the study of the implementation of both functions with a short section on miss-hits and their detection. \subsection{Miss-hits} A {\em miss-hit} is a hit to an object that is not alive. One might think that miss-hits indicate errors at the user level, but this does not hold true. One source of misidentification comes from uninitialized memory on the stack. Especially if stack frames are large, pointers on a stack can fail to be overwritten by later stack expansions, erroneously appearing to later collection calls then as being alive. Another source of misidentification comes from heap objects that are not fully initialized. If there is no reasonable default value or if there is no reason for a default value---since it only will be overwritten---efficiency considerations make library designers accept objects in this ill-defined state. The vector and deque class in the STL are examples of half-initialized objects which allocate memory in big junks without fully initializing it. As a remedy for the first kind of misidentification, \cite{Boe93} suggests to clear a number of stack frames, a technique, we borrowed for the \fgc, too. It is worthwhile to stress, however, that the risks of misidentification are different for \fgc\ and the \BDW\ collector. If a mark-sweep collector mistakenly identifies a pointer, it leads to memory retention. If a \mcc\ errs, this error results in run-time exceptions as soon as the collector tries to access or scan an object that has already been copied. For \fgc , therefore, misidentifications have to be ruled out. We provide three functions, {\tt missHitNormal()} and {\tt missHitWired()}, to recognize miss-hits to wired or normal pages and {\tt missHit()} to inspect the live bitmap of a page of unknown kind. We present the last two functions. The function {\tt misHit()} investigates the live bitmap. According to the size of objects on a given page this bitmap comprises either one word in the member ({\tt wired2.live}) of the anonymous union in the \pgi\ class or or is stored on the page; for objects of size 2,3 the place of the bitmap on the page depends on whether or not the value of the potential object is less than 32 or not. Correspondingly, the different access functions {\tt live, live2, live3, live4} are called. If the result, {\tt live}, has an entry 0 at the position of the input parameter {\tt no}, the miss-hit is detected and the function returns with false. @D missHit() @{ inline bool missHit(unsigned int no, PageInfo *page, word p, void *pp=0) { register word live; register char * pageStart=PageStart(p); if (page->size > 7) { live=page->wired2.live; } else if ( page->size > 3) { live=live2(pageStart); } else if (no < BITS_PER_WORD) { live=live3(pageStart); } else { live=live4(pageStart); no -= BITS_PER_WORD; } if ( 0 == ( (1< return true; } return false; } @} Compared to the function {\tt missHit()} just discussed, the function {\tt missHitNormal()} is rather simple. It only checks whether the input parameter {\tt no} is less than the variable {\tt to} that marks the last element on a page. @D missHitNormal() @{ inline bool missHitNormal(PageInfo *page, int no, word p, void *pp=0) { if(no < gc.smallSize.objectNo(page->size, page->normal.to) ) { @< if defined(TRACE\_MISSHIT), print address @> return true; } return false; } @} The function {\tt missHitWired()} is similar so that we omitt it here. \subsection{Marking from roots} The procedure {\tt markFromRoot()} has the type \begin{verbatim} inline void markFromRoot(word p) \end{verbatim} where {\tt p} denotes a valid address in the heap. When {\tt markFromRoots()} is called by the system-dependent root detector {\tt setEnumParams()} it gets subsequently all (valid) roots within the heap. Its task then is, to enter the pages reached into the various queues the following {\tt scan()} procedure is operating on. The procedure body of {\tt markFromRoot()} is organized in the following way: % @D markFromRoot() @{ inline void markFromRoot(word p) { @< verify valid heap address @> @< markFromRoot prepare @> @< mark (from root) free or unusable page @> @< mark (from root) big page @> @< mark (from root) normal page @> } @} In the remaining subsection we elaborate on each of the components. The first check, for reasons of safety, makes sure that the argument to {\tt markFromRoot()} really refers to a valid address; if not, the \cpp\ macro {\tt assert} initiates an abort with an appropriate error message. @D verify valid heap address @{ assert(p >= gc.heapStart && p < gc.heapEnd); @} If the argument {\tt p} is valid, the preparation of the marking phase in a closer sense begins. We initialize two local variables, with the beginning of the page where {\tt p} is situated, and with the page-info that describes this page; if the given pointer points to the very first word of a page, we know that it is an end-of-object pointer and set the start of the page it belongs to to the address of the previous page. After the initialization, we perform a first safety check for misshits. @D markFromRoot prepare @{ register char* pageStart = PageStart(p); if( (char *)p == pageStart ) { pageStart -= BYTES_PER_PAGE; if (pageStart < (char *)gc.heapStart) return; } register PageInfo* page = PageInfoFromPageStart(pageStart); @< fprintf(stderr,"markFromRoot hit page \%d$\backslash$n", No(page));@> if(page->space < gc.currentSpace) { @< if TRACE\_MISSHIT defined, print current space @> return; } @} After the initialization the function body branches according to the kind of page. For free pages or pages that are not in the scope of \fgc \ (``unusable"), there is nothing to do: % @D mark (from root) free or unusable page @{ if(page->freeOrUnusable()) return; @} The other cases require some more work; we treat them separately. \subsubsection{Big pages} For big pages, the action to be taken depends on their {\tt space} number and the value of the {\tt size} member. If the space number is greater or equal than the current value of {\tt nextSpace}, we have already hit the object before; nothing has to be done, thus: % @D if page already visited, return @{ if(page->space >= gc.nextSpace) { return; } @} If we land up in the middle of a big object (indicated by the value -1 of the variable {\tt size}) we go back to the beginning of the object. Of use here is the data member {\tt big.nPages} that stores the number $n$ of the current page; it stores $n$ as a negative value, so that we actually step backwards through the {\tt operator+}: % @D if on continuation page, go to the first page-info @{ if(page->size < 0) { page += page->big.nPages; } assert(page->size == 0 && page->big.nPages > 0); pageStart=page->data(); @} % So far we have the input parameter {\tt p} simply {\em treated} as a pointer into a big object. This, of course, is just an assumption; the parameter {\tt p} might even be no pointer at all. Given now the start page of a big object we can rule out at least two failure cases, making thus the imprecise part of \fgc\ a bit more precise. The input parameter certainly is no pointer into the current big object, if it is more than {\tt nPages}, the size of the big object, distant from its base address; furthermore, it is no pointer at all, if it is less than {\tt word (= sizeof(pointer))} distant from the base: % @D if no (valid) pointer, return @{ if( (p - word(pageStart)) > page->big.nBytes ) return; if( (p - word(pageStart)) < sizeof(word) ) return; @} If {\tt p} is not invalid, we can go ahead, color all pages of the big object as black, enter the big object into the queue {\tt gc.bigObjects\_q}, and, for bookkeeping reasons, increase the counter {\tt unmovablePagesCount} by the number of pages the big object occupies. @D blacken pages, add object to queue @{ setSpace(page, page->skip(), black); gc.bigObjects_q.add(page); gc.unmovablePagesCount += page->big.nPages; @} Processing a big page thus summarizes as: @D mark (from root) big page @{ if (page->size <= 0) { @< if page already visited, return @> @< if on continuation page, go to the first page-info @> @< if no (valid) pointer, return @> @< blacken pages, add object to queue @> return; } @} For most parts of \fgc , it holds that a page can fall in three different categories: normal, big, and wired. Not so here, in {\tt markFromRoot()}, where wired pages just are created. Consequently, if the argument {\tt p} to the {\tt markFromRoot()} function does not point to a big page, it necessarily points to a normal page. What are we doing with normal pages? \subsubsection{Normal pages} Normal pages, in fact, are treated rather different from big pages. While big pages remain big pages, normal pages change to wired pages. Such mutation includes several adjustments of the members of the new wired page. The prerequisite of all later steps is to get the {\tt objectNo}, the index of the object on the page: % @D compute object number no @{ register int offset=offsetInPage(p); if(offset == 0 ) { offset = BYTES_PER_PAGE; } if (offset > gc.smallSize.sz[page->size].classTop+page->size*BYTES_PER_WORD) { @< if TRACE\_MISSHIT defined, print offset @> return; } register int no = gc.smallSize.userObjectNo(page->size, offset); if (no == SizeClass::invalid) return; @} A negative value of {\tt no} obviously makes any further efforts meaningless and we return. Otherwise, we branch in two cases: @D mark (from root) normal page @{ @< compute object number no @> @< if page \#no already visited, update toScan @> @< otherwise, initialize toScan \& scanned and queue the page @> @} Let us look at the last two steps in some more detail. Suppose, we visit a page the secod time: what do we have to mark? When it is visited the second time, it has already become a wired page; in particular its member bitmap {\tt toScan} is already initialized. What is left to do, is to set the bit that indicates the object just hit. The bit-setting is done, as usual, by logically {\em or\/}-ing the bitmap with an integral ``1", shifted to the right place. We have to pay attention, however, which bitmap we set the flag up in. If the object number is less than {\tt BITS\_PER\_WORD}=32, the object-number refers to the {\tt no}-th bit in the {\tt toScan} bitmap, otherwise it denotes the offset in the second bitmap {\tt toScan2}. @D if page \#no already visited, update toScan @{ if(page->space >= gc.nextSpace) { if(missHit(no, page, p)) return; if(no < BITS_PER_WORD) { if(page->size > 7) page->wired2.toScan |= 1 << no; else page->wired.toScan |= 1 << no; } else { toScan2(pageStart) |= ( 1 << (no - BITS_PER_WORD) ); } return; } @} This last paragraph described the situation that we have touched the page before. If we visit the page the first time, however, we have to set its space number, {\tt page->space}, to initialize the live bitmap, and to zero-initialize the member {\tt page->wired.scanned} before we, as in the previous case, flag up the {\tt no}-th bit in the {\tt toScan} bitmap. At the end of the block, also in addition to the previous case, we enter the page into the queue of wired pages. The initialization of the various bitmaps, as usual, depends on the size of the objects on the page. @D otherwise, initialize toScan \& scanned and queue the page @{ if(page->space < gc.nextSpace) { ++gc.unmovablePagesCount; register word live; if (page->size > 7) { @< initialize bitmaps for normal pages of size $>$ 7 @> } else if (page->size > 3) { @< initialize bitmaps for normal pages of 3 $<$ size $<$ 7 @> } else { @< initialize bitmaps for normal pages of size 2,3 @> } @< if TRACE\_MISSHIT defined, print live bitmaps @> page->wired.scanned=0; page->space = wiredInQueue; gc.wiredPages_q.add(page); } @} The initialization of a page of a give size depends on its history. If the page used to be a normal page, the live bitmap has to be computed yet. Otherwise, if the page used to be a wired page, the live bitmap can be copied from the value of {\tt scanned}. The following code snippet shows the initialization of pages with objects of size 7 words and greater. For this size, the member {\tt wired2} of the \pgi\ class holds the {\tt live} and the {\tt toScan} bitmap. The live bitmap is initialized using the helper function {\tt liveFromOffset()} while the scan bitmap flags up the appropriate bit through a shift operation. @D initialize bitmaps for normal pages of size $>$ 7 @{ if (page->space & 0x02) { // previously normal page if(missHitNormal(page, no, p)) return; page->wired2.live = liveFromOffset(page->normal.to, gc.smallSize.sz[page->size].classTop, page->size); } else { // previously wired if(missHitWired(page->wired.scanned, no, p)) return; page->wired2.live = page->wired.scanned; } page->wired2.toScan = 1 << no; @} For pages with objects of size greater than 3 (and less than 7) the initialization looks similar, except that the live bitmap is stored on the pages themselves and has to be accessed with the function {\tt live2()}. Pages with objects of size 2,3, on more time, require additional means. As in the previous case the initialization depends on whether the page was a normal or a wired page before. In addition, however, to the previous case we have to branch according to the object number {\tt no}, which either refers to a position in the regular bitmap {\tt toScan} or to a position in the additional bitmap {\tt toScan2}, and which also requires the different initializations of the live-bitmap. As in the previous case, for wired pages, it simply can be copied from the scanning bitmaps. For normal pages, however, the live-bitmap has to be computed as either a two word or an one-word bitmap. % @D initialize bitmaps for normal pages of size 2,3 @{ if (page->space & 0x02) { // previously normal page if(missHitNormal(page, no, p)) return; int toNo=gc.smallSize.objectNo(page->size, page->normal.to); if (toNo < BITS_PER_WORD) { @< object number $<$ 32 (normal page) @> } else { @< object number $\geq$ 32 (normal page) @> } } else { // previously wired if(no < BITS_PER_WORD){ @< object number $<$ 32 (wired page) @> } else { @< object number $\geq$ 32 (wired page) @> } live3(pageStart) = page->wired.scanned; live4(pageStart) = scanned2(pageStart); } scanned2(pageStart) = 0; @} For an object with number $<$ 32 on a normal page we set the proper bit in the {\tt toScan} bitmap and zero-initialize the other one, {\tt toScan2}. Before, we initialize the two-word live bitmap using the functions {\tt live3()} and {\tt live4()}. We initialize the additional bitmap {\tt scanned2} and @D object number $<$ 32 (normal page) @{ // No 0..31 live3(pageStart)= liveFromNo(toNo, BITS_PER_WORD-1); // No 32 .. no(classTop) (computed - 32 ) live4(pageStart) = liveFromNo(0, gc.smallSize.objectNo(page->size, gc.smallSize.sz[page->size].classTop) - BITS_PER_WORD); page->wired.toScan = 1 << no; toScan2(pageStart) = 0; @} For an object with number greater or equal than $<$ 32 on a normal page we proceed in the opposite way and set the bit in the {\tt toScan2} bitmap and zero-initialize the other bitmap, {\tt toScan}. @D object number $\geq$ 32 (normal page) @{ live3(pageStart) = 0; live4(pageStart) = liveFromNo(toNo - BITS_PER_WORD, gc.smallSize.objectNo(page->size, gc.smallSize.sz[page->size].classTop) - BITS_PER_WORD); page->wired.toScan = 0; toScan2(pageStart) = ( 1 << (no - BITS_PER_WORD) ); @} For objects on a wired page, the same logic applies, regarding the initialization of the scan bitmaps, @D object number $<$ 32 (wired page) @{ if(missHitWired(page->wired.scanned, no, p)) return; page->wired.toScan = 1 << no; toScan2(pageStart) = 0; @} that is, we set the proper bit in one bitmap and zero-initialize the other one. @D object number $\geq$ 32 (wired page) @{ if(missHitWired(scanned2(pageStart), no-BITS_PER_WORD, p)) return; page->wired.toScan = 0; toScan2(pageStart) = ( 1 << (no - BITS_PER_WORD) ); @} This concludes our presentation of the {\tt markFromRoot()} procedure. \subsection{Marking from the heap} The procedure we address in this subsection, {\tt moveOrMark()}, looks at first glance very much alike {\tt markFromRoot()}. On the other hand, {\tt moveOrMark()} is the procedure that qualifies \fgc\ as a mostly copying collector---the trace function that users provide to locate internal pointers eventually resolves to {\tt moveOrMark()}. The differences from {\tt moveOrMark()} to {\tt markFromRoot()}, therefore, all show major design features. The signature of {\tt moveOrMark()} reads as \begin{verbatim} inline void moveOrMark(void *pp) \end{verbatim} where the parameter {\tt *pp} denotes an internal pointer of a garbage-collected object. Let us look at the overall structure of the function body first. Very similar to {\tt markFromRoot()}, the function starts off with preparation steps and the trivial cases, and then branches according to the page category. In addition to {\tt markFromRoot()} the {\tt moveOrMark()} function has to handle wired pages too---which do not yet exist when{\tt markFromRoot()} is active. @D moveOrMark() @{ void moveOrMark(void *pp) { @< moveOrMark prepare @> @< move-or-mark trivial cases @> @< move-or-mark big page @> @< move-or-mark normal page @> @< move-or-mark wired page @> } @} The preparation steps are easy to understand. We make sure that the argument {\tt *pp} points to a valid address in the heap; if so, we reserve two local variables to point to the start address of the corresponding page and to the page-info that describes this page. @D moveOrMark prepare @{ word p = *wordPtr(pp); if(p < gc.heapStart || p > gc.heapEnd) return; char *pageStart = PageStart(p); if( (char *)p == pageStart ) { pageStart -= BYTES_PER_PAGE; if(pageStart < (char *)gc.heapStart) return; } register PageInfo *page = PageInfoFromPageStart(pageStart); @< if TRACE\_PAGE\_HIT defined, print page information @> if(page->space < gc.currentSpace || page->space >= grey) { @< if TRACE\_PAGE\_HIT defined, print: "not in current space" @> return; } @} The trivial cases for {\tt markOrMove()}, next, either are pages that are known as free---hence do not have to be moved---or pages that have been moved already. In both cases the space number of the page helps to determine its type: a space number less than {\tt gc.currentSpace} indicates a free page, a space number greater or equal than {\tt grey} indicates a (not wired) page in the new space. @D move-or-mark trivial cases @{ @} All pages from now on can be assumed to be in the old space. We consider first big and normal pages---its their treatment that proves \fgc\ to be a copying collector; then we look at wired pages. So, what are we doing with big pages? \subsubsection{Big pages} For big pages, two different strategies apply, depending on the the object's size. We emphasized in the overview section that the \fgc\ collector is as a {\em hybrid\/} mark-sweep and \mcc . It is here, with big objects, where the mark-sweep part of \fgc\ comes to fruition: only objects that are not ``too big" to move are copy collected; for the really big ones, we save the costs for copying them.\footnote{The environment variable {\tt TOO\_BIG\_TO\_MOVE} determines the borderline.} Let us discuss the copy-collecting part first. In essence, the classical instruction sequence of a copy collector applies: allocate new space for the object, copy the object, and leave the new address in the old space. @D copy collect big object @{ wordPtr fwd = wordPtr(pageStart); if(forwarded(*fwd)) { *wordPtr(pp)=(*fwd)-1 + p - word(pageStart); return; } PageInfo* newPlace = @< allocate nPages @> if(newPlace) { @< copy from fwd to newAddr @> @< forward new address @> *wordPtr(pp) = word(newAddr) + p - word(pageStart); gc.bigObjects_q.add(newPlace); return; } @} How is the implementation done? First, we allocate as many pages as needed to keep the big object: @D allocate nPages @{allocPagesOrFail( page->big.nPages, page->big.nBytes ); @} Next, we point the variable {\tt newAddr} to the object's first page in the new space, the variable {\tt fwd} to its first page in the old space, and copy the entire big object word-wise: @D copy from fwd to newAddr @{ wordPtr newAddr = (wordPtr)newPlace->data(); copyWords(wordPtr(pageStart), wordPtr(pageStart + page->big.nBytes), wordPtr(newAddr) ); @} The new address has to be left at the old address, so that other objects that point to the big object know how to update their pointers. Now, if we simply write the new address somewhere in the space the big object previously occupied, how will such entry be recognizable as a forwarded address? We adopt a technique realized by both Bartlett's and the CMM framework: we store the new address in the {\em first} word of the object's old space. This by itself does not make much sense yet, since the first word of an object already holds a pointer---the pointer to the user-defined traverse function. We know, however, that this pointer points to an {\em even} address.\footnote{ Strictly speaking, we should postulate this property rather than assuming it, since word alignment for data---a fundamental prerequisite of \fgc ---does not automatically imply word alignment for function bodies.} Therefore, if we not only store the new address but logically {\em or\/} it with the integer 1---which makes its value odd---then the forwarded address is well distinguishable from the originally stored address of the traverse function. % @D forward new address @{ *fwd = word(newAddr) | 1; @} % This finishes the copy collecting part for big object. As said before, not all big objects are treated in a copy-collecting manner. As a consequence, the copy-collector part is embedded in an {\tt if} statement that checks the size of the big object. The processing of a big page in summary reads as follows: @D move-or-mark big page @{ if(page->size <= 0) { @< if on continuation page, go to the first page @> @< if no (valid) pointer, return @> if(page->big.nBytes < gc.tooManyBytesToMove) { @< copy collect big object @> } @< blacken pages, add object to queue @> return; } @} \subsubsection{Normal pages} While big pages are processed in a hybrid fashion, normal pages are purely copy-collected. These are the four logical steps performed: % @D move-or-mark normal page @{ @< check and adjust pointer @> if( page->space < gc.nextSpace ) { @< check for misshit @> @< if object already moved, return @> @< otherwise copy object @> } @} The preparation steps include storing both the given pointer's {\tt offset} in the page and its offset within an object, {\tt objStartOffs}. The value 0 of the variable {\tt offset} indicates an end-of-storage pointer to a location after an allocated object. In this case we adjust the pointer by {\tt BYTES\_PER\_PAGE} to associate it with the word it belongs to. %Strictly speaking, the value of {\tt objStartOffs} cannot be less than zero, %but, on the other hand, its value is derived from a user-defined %variable and we should be able to catch potential user errors.% %\footnote{Another source of %irregularities besides user errors includes externally interrupted %\fgc\ calls.} @D check and adjust pointer @{ int offset = offsetInPage(p); int objStartOffs = gc.smallSize.objectStart(page->size, offset); if (offset == 0 ) offset = BYTES_PER_PAGE; register int no = gc.smallSize.userObjectNo(page->size, offset); if (no == SizeClass::invalid) { @< if TRACE\_MISSHIT defined, print pointer to SizeClass::invalid @> return; } @} Next, we check whether the (adjusted) pointer hits an object that is live. @D check for misshit @{ @< if TRACE\_PAGE\_HIT defined, print offset @> if(page->space & 2) { if(missHitNormal(page, no, p, pp) ) return; } else if(no < BITS_PER_WORD) { if(missHitWired(page->wired.scanned, no, p, pp) ) return; } else { if(missHitWired(scanned2(pageStart), no-BITS_PER_WORD, p, pp)) return; } offset -= objStartOffs; @< if TRACE\_PAGE\_HIT defined, printed (adjusted) offset @> @} After these preparation steps, the variable {\tt offset} points to the first word of the object that was hit. This first word of an object, however, as discussed in the previous subsection, is doubly used. It either holds the traverse function to scan the object or it holds the forwarded address to which the object was moved. The predicate {\tt forwarded} checks which of the two cases holds true: @D if object already moved, return @{ wordPtr fwd = wordPtr(pageStart + offset); if( forwarded(*fwd) ) { *wordPtr(pp) = (*fwd)-1 + objStartOffs; @< if TRACE\_PAGE\_HIT defined, print updated pointer @> return; } @} If the object is not forwarded, it is yet to be copied. For this to do, the very first prerequisite is memory. One page is sufficient for the new object; passing on the value of {\tt page->size} we allocate the new page according to the segregation policy for small objects. Next, we copy the object word by word. Finally, we leave the forwarded address on the old page, and mark it as such by {\em or\/}-ing it with 1. @D otherwise copy object @{ wordPtr newPlace = wordPtr(gc.smallSize.allocDuringCollection(page->size)); copyWords( fwd , fwd + page->size, newPlace); *fwd = word(newPlace) | 1; *wordPtr(pp) = word(newPlace) + objStartOffs; @< if TRACE\_PAGE\_HIT defined, print updated pointer @> return; @} So far, we have discussed big pages and normal ones; what is left to explain are wired pages. \subsubsection{Wired pages} Obviously, wired pages do not participate in copy-collection. They have to stay where they are, and the only thing we have to do is to mark which object was hit, provided the hit is legal. The two major steps are to get the index number of an object and to flag up its bit. Depending on the size and number of an object, the bitmap is either member of the structures {\tt wired} or {\tt wired2} or stored on the page itself, where it has to be accessed with the function {\tt toScan2()}. @D move-or-mark wired page @{ if(no < BITS_PER_WORD) { @< if TRACE\_PAGE\_HIT defined, print size @> @< check for miss-hit in wired pages @> if( (page->wired.scanned & (1u << no)) == 0 ) { if(page->size > 7) { page->wired2.toScan |= (unsigned short)(1u << no); } else { page->wired.toScan |= (1u << no); } @< add page to wired queue @> } } else { // no >= BITS_PER_WORD @< check for miss-hit in wired pages (2) @> if( (scanned2(pageStart) & (1u << (no-BITS_PER_WORD) ) ) == 0) { toScan2(pageStart) |= (1u << (no-BITS_PER_WORD) ); @< add page to wired queue @> } } @} After the proper bit is set, the page is appended to the scanning queue for wired pages. @D add page to wired queue @{ if(page == gc.pageBeingScanned) gc.repeat = 1; else if(!(page->inQueue())) { page->setInQueueFlag(); gc.wiredPages_q.add(page); } @} Before processing a page, however, we have to make sure that no dead object was hit. Checking for miss-hit requires retrieving the live bitmap and passing it on to the function {\tt missHitWired()}. As we have seen several times now, the bitmap either is stored in the {\tt wired2} member of an instance of the \pgi\ class or on the pages themselves, where it can be accessed through the functions {\tt live2()} and {\tt live3()}. @D check for miss-hit in wired pages @{ if( (page->size > 7 && missHitWired(page->wired2.live, no, p, pp) ) || (page->size < 8 && page->size > 3 && missHitWired(live2(pageStart), no, p, pp) ) || (page->size < 4 && missHitWired(live3(pageStart), no, p, pp) ) ) return; @} As usual, for pages with objects of size 2 or 3, where the live-bitmap comprises two words, we additionally have to call the function {\tt live4()} which returns the second word of the live bitmap. @D check for miss-hit in wired pages (2) @{ if(missHitWired(live4(pageStart), no, p, pp) ) return; @} This concludes the handling of wired pages and the same time the presentation of the collecting part of \fgc . \section{Allocation} Without allocation, no collection. So far we have talked about the collecting part of \fgc , but we have not talked yet about the second major part of \fgc , the allocator part. The following two section address allocation issues; in this section we look into allocation functions, in the next section into the mechanisms of heap expansion. The major allocation procedures with their signatures are the following ones: \begin{center} \begin{tabular}{|l|} \hline {\tt void* userAlloc(unsigned int size, TraverseFunc func)} \\ {\tt char* allocPages(int nPages, int nBytes)} \\ {\tt void \ PageInfo::initBig(signed\_word nPages, word nBytes)} \\ {\tt char* SizeClass::alloc(int size) }\\ {\tt char* SizeClass::allocDuringCollection(int size)} \\ \hline \end{tabular} \end{center} The functions are related among each other. The next table lists the function name together with their dependencies and additional auxiliary function(s). \begin{center} \begin{tabular}{|l|l|} \hline {\em Function} & {\em Calls} \\ \hline {\tt userAlloc()} & {\tt allocPages()} \\ & {\tt SizeClass::alloc()}\\ {\tt allocPages()} & {\tt allocPagesOrFail()} \\ {\tt SizeClass::alloc() } & {\tt allocOnePage()} \\ {\tt SizeClass::allocDuringCollection()}& {\tt allocOnePage()} \\ {\tt PageInfo::initBig()}& ----\\ \hline \end{tabular} \end{center} \subsection{User interface} We begin our explanation with the logically outermost function {\tt userAlloc()}, the users' interface of the \fgc\ collector which replaces the built-in allocation for dynamically allocated \cpp \ objects. In its simplest form this replacements happens through overloading of the \cpp\ {\tt operator new}: \begin{verbatim} void* operator new(size_t size) { return userAlloc(size, TraverseFunc( trace )); } \end{verbatim} For classes that are implemented with the Standard Template Library \cite{StLe94, MuSa96} \fgc\ is even easier to use---STL classes are already parameterized by an allocator. An adaptor provided that wraps up the {\tt userAlloc()} function in an allocator class---and meets at the same time the \cpp\ specification of an allocator template argument (for an implementation, see \cite{STLSGI, Aus99})---class designers simply replace the standard allocator by the \fgc -tailored one. Generally speaking, different allocation strategies apply for small and big objects. The task of the function {\tt userAlloc()} is to initiate the appropriate allocation strategy and to store the user-defined traverse function which locates an object's internal pointer. The function {\tt userAlloc()} takes two arguments: an unsigned integer, {\tt size}, indicating the number of bytes requested, and the user-defined traverse function {\tt func}.\footnote{Even though the function {\tt userAlloc()} is a global function from \fgc 's standpoint, it has class scope from the user's point of view; the implicitly assumed {\tt this} object, therefore, always exists.} @D userAlloc() @{ void* userAlloc(unsigned int size, TraverseFunc func) { TraverseFuncPtr result; @< return, if traverse function stored at odd address @> @< allocate small object or big object @> @< store traverse function transparently @> } @} The local variable {\tt size} determines which allocation strategy applies: small objects (of size less than 64 words) are administrated by the helper object {\tt gc} and its member {\tt smallSize}; for big objects the global function {\tt allocPages()} applies. The variable {\tt size} measures an allocation request in bytes, as {\tt malloc()} and the {\tt operator new} do; the allocation unit, however, are words. For that, the input parameter {\tt size} first gets converted from bytes to words, using the function {\tt sizeInChunks()}. @D allocate small object or big object @{ size = sizeInChunks(size, BYTES_PER_WORD); @< reserve one additional word @> if(size < SMALL_SIZE) result = (TraverseFuncPtr)gc.smallSize.alloc(size); else result = (TraverseFuncPtr)allocPages( sizeInChunks(size, WORDS_PER_PAGE), size * BYTES_PER_WORD ); @} What is the additional word good for, reserved in the previous code? When the copy-collecting part scans an individual object, it uses the traverse function---the second argument to {\tt userAlloc()}---that the user has provided. It is this traverse function that is stored in the additionally reserved word. On the other hand, user-code should not be affected by the attached function pointer. To keep the {\tt func} pointer transparent we store it as the object's first word and return not its address, but the subsequent word {\tt result++}, that is, the base address of the original object. @D store traverse function transparently @{ *result++ = func; return result; @} The precondition for attaching the (pointer to) the traverse function to the original object, however, is that its address is {\em even}. The copy-collecting part essentially depends on the property that addresses of functions are {\em even}---if they are not, the mechanism of recognizing forwarded objects breaks down entirely (see the discussion of the function {\tt moveOrMark()}). The very first thing to do, therefore, is to make sure, that the function address is ``right." @D return, if traverse function stored at odd address @{ assert( (word(func)&1) == 0); @} The \cpp\ macro {\tt assert} returns with an approriate error message if this fundamenteal assumption on addresses is violated. In the next two sections we discuss the allocation of big and small objects, according to which the function {\tt userAlloc()} branches. \subsection{Allocating big objects} The allocation of big objects comprises three functions: \begin{center} \begin{tabular}{|l|} \hline {\tt char* allocPages(int nPages, int nBytes)} \\ {\tt char* allocPagesOrFail(int nPages, int nBytes)} \\ {\tt void PageInfo::initBig(int nPages, int nBytes)} \\ \hline \end{tabular} \end{center} where {\tt allocPages()} calls {\tt allocPagesOrFail()} and {\tt allocPagesOrFail()} calls {\tt initBig()}. The first two functions refer to pages in the heap while the last one, {\tt initBig()}, is concerned with updating the page-info table. \subsubsection{The driver function} The driver function for the allocation of big objects is the function {\tt allocPages()}. Its logic is straightforward: {\tt allocPages()} gets a request for {\tt nPages}. If {\tt n} new pages would exceed the threshold, the collecting part is called: @D collection necessary? @{ if(gc.collectThreshold <= nPages) { collect(nPages, "threshold reached"); goto AfterCollect; } @} If the threshold is not yet reached, we try to allocate the requested number of pages. The allocation can succeed, but it can also fail---either because the collecting part did not return enough new pages at all or because there are not enough contiguous pages available. In the success case we return the address of the first page, in the failure case we call {\tt collect()}. @D return first page or collect (again) @{ result = allocPagesOrFail(nPages, nBytes); if(result) return result->data(); collect(nPages); @} If the allocation then fails (again), any further collection does not make sense; therefore, we have to expand the heap. After the heap expansion, the helper function {\tt allocPagesOrFail()} necessarily succeeds and we return the first page of the {\tt nPages} allocated ones. @D return first page or expand heap @{ result = allocPagesOrFail(nPages, nBytes); if(result) return result->data(); expand(nPages); return allocPagesOrFail(nPages, nBytes)->data(); @} Here is the entire function body: @D allocPages() @{ inline char* allocPages(int nPages, int nBytes) { PageInfo* result; @< collection necessary? @> @< return first page or collect (again) @> AfterCollect: @< return first page or expand heap @> } @} \subsubsection{Allocation} The actual allocation requires finding {\tt nPages} contiguous pages. The function {\tt allocPagesOrFail()} performs the task in two loops. In the outer loop it searches for the ``first", i.e., closest free page; the loop is organized by jumping to the label {\tt p\_is\_not\_free} and skipping pages that are not free.\footnote{The last {\tt return} statement obviously is never reached, but is required by compilers that check in a simplistic way all control paths.} @D allocPagesOrFail() @{ PageInfo* allocPagesOrFail(int nPages, int nBytes) { register PageInfo* p = gc.roamingPtr; @< allocPagesOrFail bookkeeping @> if(!p->free()) goto p_is_not_free; for(;;) { p_is_free: { @< find n contiguous pages @> } p_is_not_free: do { p = p->skip(); } while( !p->free() ); } return (PageInfo*) 0; // never reached } @} After the outer loop we have found one free page and the roaming pointer {\tt p} points to this page. However, we need not one, but {\tt nPages}-many free pages for the big object. The inner loop therefore checks if the subsequent {\tt nPages} pages are free, too. @D find n contiguous pages @{ register int count = nPages; do { ++p; if(--count == 0) { @< update variables and initialize page-info table @> return p; } } while( p -> free() ); @< if COLLECT\_STATS defined, do bookkeeping (2) @> @< adjust global variables @> @} During the traversal through the heap we reset the roaming pointer {\tt p} to the start page of the big object and call \pgi{\tt ::initBig()} to set the page-info table. @D update variables and initialize page-info table @{ @ gc.roamingPtr = p; p -= nPages; // go to the first page of the object // gc.collectThreshold -= nPages; p->initBig(nPages, nBytes); @} The newly allocated pages, finally, must be marked appropriately in the page-information table. This is the task of the function {\tt initBig()}. \subsubsection{Updating the page-info table} The function {\tt initBig()} goes through the entries in the page-info table that correspond to the pages in the heap with the big object and initializes the corresponding entries in the page-info table. Initialization means to set the four variables {\tt nPages, nBytes, space}, and {\tt size}. As we discussed in the section on the page-info table class, the start page of an big object differs in two points from the continuation pages. First, the {\tt size} variable has value 0 for the start page, but -1 for all subsequent pages. Second, the variable {\tt nPages} denotes the total number of pages on the start page (more precisely: the entry in the page-info that corresponds to the first page), but denotes the negative distance to the start page for all continuation pages. Consequently, the function {\tt initBig()} initiates the entry for the start page separately and loops then through all subsequent entries. The values of the other two data members of the \pgi\ class, {\tt nBytes} and {\tt space}, are the same for all page-info descriptors. It is not necessary, however, to initialize the variable {\tt nBytes} on continuation pages; we save the instruction, therefore. @D PageInfo::initBig() @{ inline void PageInfo::initBig(int nPages, int nBytes) { big.nPages = nPages; big.nBytes = nBytes; space = gc.allocSpace; size = 0; for(int i = 1; i < nPages; ++i) { this[i].space = gc.allocSpace; this[i].size = -1; this[i].big.nPages = -i; } } @} \subsection{Allocating small objects} We know, small objects---objects of size less than half a page---are stored together. Allocating small objects thus essentially means to find ``their" page and to find the right place on this page. We have already seen in \ref{TheClassScl} that instances of the class \scl , one for each small size, overlook the whole allocation process but we haven not looked in detail into the implementation. In this subsection we discuss two functions, {\tt SizeClass::alloc()} and {\tt SizeClass::allocDuringCollection()} to position an object on a given page, and the function {\tt allocOnePage()} to allocate a new page, if necessary. \subsection{Placing objects} The data members of the class \scl\ include a variable {\tt top} that points to the beginning of the last object of a page; in the trivial case, allocation simply means shifting the {\tt top} pointer by the size of the newly allocated object. This trivial case is the same for both {\tt alloc()} and {\tt allocDuringCollection()}: @D allocate one small object @{ top -= (size * BYTES_PER_WORD); return pageStart + top; @} Note that every page is allocated backwards, towards the first word on the page; thereby, the {\tt top} pointer automatically is correctly adjusted, saving one updating instruction. If the current page is full, both functions call the function {\tt allocOnePage}: @D allocate one page @{ PageInfo* pi = allocOnePage(size, classTop); @} and initialize the data members of the \scl\ instance; {\tt pageStart} points to the address of a page in the heap and {\tt top} gets the value of the variable {\tt classTop}, which indicates the offset on the page of objects of the given size. @D initialize new page @{ pageStart = pi->data(); top = classTop; return pageStart + classTop; @} The difference between the two functions {\tt alloc()} and {\tt allocDuringCollection()} lies in the availability of free pages. The function {\tt SizeClass::alloc()} cannot simply assume that always free pages are available---it has to check the status of the threshold and has to call the collector, if necessary. @D SizeClass::alloc() @{ char* SizeClass::alloc(int size) { if(top) { @< allocate one small object @> } else { if(gc.collectThreshold <= 0) collect(1); @< allocate one page @> @< initialize new page @> } } @} The function {\tt SizeClass::allocDuringCollection()}, on the other hand, can save the call to {\tt collect()}. It operates in the {\em To} space, which, provided the heap is divided in two halves, is of the same size than the {\em From} space. Each page in the {\em From} space has its counterpart in the {\em To} space and therefore always enough pages are available. However, {\tt allocDuringCollection()} has to inform the scanning part of the newly allocated page, that is, to add the new page to the queue of pages which yet are to be scanned. With small objects on it, the new page belongs to the category of normal pages. @D SizeClass::allocDuringCollection() @{ char* SizeClass::allocDuringCollection(int size) { if(top) { PageInfo *pi=PageInfoFromPageStart(pageStart); if ( ! pi->inQueue() && pi != gc.pageBeingScanned ) { @< store page in normal queue @> } @< allocate one small object @> } else { @< allocate one page @> @< store page in normal queue @> @< initialize new page @> } } @} \subsection{Allocating a single page} In the previous section we described how to place objects, provided a page in memory is already given. How do we get a page in the first place? Allocating a single page is rather straightforward; all we have to do is to set the roaming pointer to the first free page: @D allocOnePage() @{ inline PageInfo* allocOnePage(int size, int classTop ) { register PageInfo* p = gc.roamingPtr; while(!p->free()) p = p->skip(); @< if COLLECT\_STATS defined, set global variables @> gc.roamingPtr = p + 1; @< initialize normal page @> --gc.collectThreshold; return p; } @} In addition to the allocation we initialize the three data members that characterize a normal page, {\tt space, size}, and the {\tt struct normal}: @D initialize normal page @{ p->space = gc.allocSpace; p->size = size; p->normal.from = classTop; p->normal.to = 0; @} What are the values of each variable? The member {\tt from} indicates the first legal address on the page; it is initialized with the offset variable {\tt classTop} (recall, that we allocate the last object on the page first). which in turn is passed to {\tt allocOnePage() } as an input parameter. The member {\tt to} is set to 0, for obvious reasons. The {\tt size} field, next, is set to the second input parameter to {\tt allocOnePage()}; the field {\tt space}, finally, gets its value from the global variable {\tt allocSpace}. The update of the page-info table concludes the section on allocation. \section{Heap Expansion} Up to now, allocation referred to \fgc 's \emph{idea} of allocation. At some point, however, pages have to come physically into play---the system-dependent allocation function has to ask the underlying operating system for a number of blocks of memory. Logically, the communication with the operating system takes place during the expansion step of the \fgc\ collector. In this section, we discuss the function {\tt expand()}, which initializes the heap expansion, and the function {\tt internalExpand()}, which re-organizes the heap after its expansion. Let us start with an explanation of the function {\tt expand()}. \subsection{Expansion} The function {\tt expand()} gets a number {\tt pagesRequested} and, for debug reason, an explanatory string {\tt reason}. Its implementation breaks down in three tasks: to compute the number of {finally} requested pages ({\tt nPages}), to communicate with the operating system, and to call the function {\tt internalExpand()}. @D expand() @{ void expand(int pagesRequested, char* reason = "no reason"){ @< second and later expansion @> @< first expansion @> @< adjust allocation request @> @< call system allocator @> internalExpand(word(result), word(result) + nBytes); } @} How many pages do we ask the operating system for? Obviously, at least as many as {\tt pagesRequested}. But the \fgc\ collector allows users reserving memory before their program starts. It therefore makes a difference whether {\tt expand()} is called the first time or at any later time. Let us look at the second case first. If the heap is not empty, i.e., if expansion has taken place at least once, we determine the amount of pages by which the heap has to be increased. By default, the heap size is doubled each time, but users can also change the default policy (see the section on constants). If the default strategy applies, we need to know the current size (in pages) of the heap; the function {\tt gc.heapPages()} returns the number. If users overwrote the default strategy, the variable {\tt gc.heapIncrement} is set. @D second and later expansion @{ int nPages; if( @< heap not empty @> ) { @< if TRACE\_EXPAND defined, trace (1) @> if( gc.heapIncrement ) nPages = gc.heapIncrement; else nPages = gc.heapPages(); } @} If we are in the very first expansion phase, however, there is no heap size yet to double. Instead, we have to retrieve the initial heap size: @D first expansion @{ else { @< if TRACE\_COLLECT defined, trace (2) @> nPages = gc.initialHeapSize; } @} Whether in the first or any later call to {\tt expand()}, we have to check whether the heap policy is compliant with the request of memory, i.e., we have to compare the number of requested pages with the number of pages by which the heap increases. If the value of {\tt pagesRequested} is larger than {\tt nPages} (minus the initial size) we add both values to get a new figure of the memory request; this summation implies a silent, but inevitable modification of the (user-)suggested heap increment. For the final value of {\tt nPages}, then, we add the number of pages occupied by the page-info table. @D adjust allocation request @{ if(pagesRequested > nPages - gc.initialHeapSize) nPages += pagesRequested; nPages += 1 + (gc.heapSpanPages() + nPages) / PAGEINFOS_PER_PAGE; @} Now we have got the number of pages we actually want to request. System-dependent allocation function, however, do not operate with pages in our sense. They mostly count in bytes; moreover, they allocate memory in chunks. Using the class {\tt sysdep}, which encapsulates all system-dependent functions, we first align our request (upwards) to a number of bytes that coincides with a unit in which the system allocator operates. Then, we call this allocator with the new value of {\tt nBytes} and keep the resulting pointer to the new free memory in the variable {\tt result}; if the system allocation fails to return a value, an error is printed and the whole \fgc\ program stops. @D call system allocator @{ int nBytes = alignUp(nPages * BYTES_PER_PAGE, gc.sysdep.getVmPageSize() ); void* result = gc.sysdep.alloc(nBytes); if(result == 0) { fprintf(stderr, "EXPAND: Failed allocating %d pages\n", nPages); exit(-1); } @} If new memory is available, {\tt expand()} passes the control on to the function {\tt internalExpand()} and returns. \subsection{Reorganizing the heap} After the expansion step, the heap has a new shape. It is not only larger, but it now can also contain holes---whether the new and the old heap form a contiguous space entirely depends on the operating system. The new heap layout has to be described, i.e., the various pointers, to the beginning or end of the heap, the page-info table, or to free segments have to be updated. So have all other global data. At the same time every page in the new heap, also every page in the ``hole" needs a descriptors, i.e., an entry in the page-info table---and these entries have to be set. Moreover, the page-info table itself has to be extended and, as a consequence, has to move. All these tasks are taken care of by the function {\tt internalExpand()}. This function is one of the longest of the whole \fgc , not so much because of its program logic but more because of the need for case distinctions. Here is the overall structure of the function body: @D internalExpand() @{ static void internalExpand(word newSegmentStart, word newSegmentEnd){ @< initialization and declaration @> @< update heap pointers @> @< move page-info table @> @< update global data @> } @} We break the presentation of the function {\tt internalExpand()} down along these three main blocks. \subsubsection{Updating heap pointers} Updating heap pointers (at that point of the program) includes four pointers: \begin{center} \begin{tabular}{|l|} \hline {\tt newRealHeapStart} \\ {\tt newRealHeapEnd} \\ {\tt holeStart} \\ {\tt holeEnd} \\ \hline \end{tabular} \end{center} % which are declared at the beginning of the function body: @D initialization and declaration @{ word pagesInNewSegment = (newSegmentEnd - newSegmentStart) / BYTES_PER_PAGE; word newRealHeapStart, newRealHeapEnd; word holeStart, holeEnd; @} (There is a difference between the heap and the ``real'' heap, the former one includes the page-info table; we get back to the difference when we discuss moving the page-info table.) The new values of the heap pointers depend on where the new segment has been placed. Generally, there are three possibilities how the old heap and the new segment are arranged: \begin{figure}[h] \begin{center} \epsfig{file=Figure13.eps, height=3cm, width=4.5cm} \caption{Expanded heap} \end{center} \end{figure} % Correspondingly, we distinguish three cases and, additionally, the special case of an empty heap. @D update heap pointers @{ if(newSegmentStart < gc.heapStart) { @< new segment left to the old heap @> } else { if(newSegmentEnd <= gc.heapEnd) { @< new segment inside the old heap @> } if(gc.realHeapStart) { @< new segment right of the old heap @> } else { @< initialize empty heap @> } } @} Let us look at each of the four cases separately. If the new segment is located left to the old heap the pointers assembly looks as follows % \begin{figure}[h] \begin{center} \epsfig{file=Figure14.eps, width=11.5cm} \caption{Expanded heap with hole} \end{center} \end{figure} % % with the corresponding assignments: @D new segment left to the old heap @{ newRealHeapStart = newSegmentStart; newRealHeapEnd = gc.realHeapEnd; holeStart = newSegmentEnd; holeEnd = gc.realHeapStart; @} If the new segment is positioned {\em right} to the old heap the situation is the same, up to symmetry; we omit it therefore. If the new segment lies in between the old heap, however---the second case in the nested {\tt if} statement above---the situation is quite different. In this case, neither {\tt heapStart} nor {\tt heapEnd} have changed. As a consequence, the page-info table does not have to be extended and in particular it does not have to be moved. In other words, we can skip major parts of the {\tt internalExpand()} function and almost directly return from the subroutine. We only have to change the page descriptors that belong to the new space, to mark the formerly unusuable, now new pages as free and to take care of global variables that have changed. @D new segment inside the old heap @{ @< mark new pages as free, update variables @> return; @} To mark the new pages as free, we loop through the corresponding segment in the page-info table and call {\tt markFree()}. Additionally, we update all global data affected by an heap expansion---in this special situation it is only the roaming pointer and the total number of pages available. We set the roaming pointer to the first page of the new segment and let the function {\tt gc.heapPagesAdd()} add the number of pages in the new segment to the previous total of pages. @D mark new pages as free, update variables @{ PageInfo* p = PageInfoFromPageStart((ptr_t)newSegmentStart); gc.roamingPtr = p; for(int n = pagesInNewSegment; --n >= 0;) p++ -> markFree(); gc.heapPagesAdd( pagesInNewSegment ); @} This finishes the special of a new segment that came to be located in the middle of the old heap. The case of an empty heap obviously requires a separate consideration, too. The start and end of the heap have to be initialized---they coincide with start and end of the new segment; the variables {\tt holeStart} and {\tt holeEnd} are set to 0, since no holes could have come up. The global data {\tt gc.currentSpace} and {\tt gc.nextSpace}, finally, are set to {\tt SPACE\_STEP}=4, and, since the program is in the allocation state, the value of {\tt gc.allocSpace} is increased. @D initialize empty heap @{ newRealHeapStart = newSegmentStart; newRealHeapEnd = newSegmentEnd; holeStart = 0; holeEnd = 0; gc.currentSpace = gc.nextSpace = SPACE_STEP; gc.allocSpace = gc.nextSpace | 2; @} \subsubsection{Moving the page-info table} After this first step the heap in its entire, its starting and end point and its potential hole, is described. Next, a page description has to be provided for each page the heap spans over, that is for all used pages, but also for the unusable ones. With these new entries the page-info table will grow. But at the same time the page-info table can not simply be extended ``to the right (or left)"---it would overwrite pages with data. As a consequence, the page-info table has to move. @D move page-info table @{ @< compute required space @> @< prepare move @> @< move table @> @< reserve dummy entry @> @} Computing the space the new page-info table will occupy, is an easy arithmetical excercise, unless the ``hole" is so big that the heap cannot hold the grown page-info table. In this case, we have to expand the heap first. @D heap cannot hold PI @{ if(newBytesInPI > newSegmentEnd - newSegmentStart) { int newPages=pagesInNewSegment + newPagesInPI; #ifdef TRACE_EXPAND fprintf(stderr, "Big hole: allocate %d instead of %d\n", newPages, pagesInNewSegment); #endif expand(newPages, "Hole in the heap"); return; } @} Where do we move the page-info table? The easiest, most efficient way is to use the new space; if we put the table at the beginning of the new, just allocated segment, we know without further tests that enough contiguous, usable pages are available. But, where is this beginning of the new segment? This depends on the relation between the new segment and the old heap, but also on the previous heap expansion and the resulting position of the old page-info table. For the place of the page-info table there are four possible positions: \begin{figure}[h] \begin{center} \epsfig{file=Figure15.eps, width=11.5cm} \caption{Moving the page-information table} \end{center} \end{figure} % Whichever constellation applies, the operations for each segment of memory are the same: the old page-info table has to be copied, the pages in the ``hole" have to be marked as unusable, and the new pages as usable---the only thing that varies are the absolute addresses for the various segments. To avoid reiterating the same sequence of instructions four times we introduce an auxiliary control structure that decodes the current constellation and controls the whole move efficiently. The control structure {\tt control} is an integer array with four entries, one for each of the segment types heap, hole, old page-info table, and new page-info table; in other words, {\tt control[0]} refers to the first segment, {\tt control[1]} to the second segment, etc. The important feature of the array is that each field contains two kinds of information: the kind of segment it is associated with and the size (in pages) of this segment. For this to work in an {\em one}-dimensional array, conventions have to apply: Let $n$ be the value of an (arbitrary) entry of the array {\tt control}. We define the following interpretations: a positive value of $n$ denotes the number of {\em free} pages, a negative value the number of {\em unusable} pages; {\tt LONG\_MAX} indicates the beginning of the heap, and $n=0$ an empty segment. The table summarizes the values and their interpretation: \begin{center} \begin{tabular}{|l|l|}\hline $n>0$ & free pages\\ $n<0$ & unusable pages\\ $n=0$ & empty \\ {\tt LONG\_MAX} & old page-info table \\ \hline \end{tabular} \end{center} The interpretations become clearer when we look how the control array is initialized. We consider first the case that the new segment is (conceptually) left of the old heap. At first, we set pointers to the start of the new page-info table and to the start and end of the heap. If the new segment is left of the old heap, {\tt control[0]} refers to free pages and {\tt control[1]} to the hole (if there is such). How do we get the two values? The first value, the number of free pages, denotes the difference between {\tt pagesInNewSegment} and {\tt newPagesInPI}, the size of the page-info table; following the interpretation above we store the difference as a positive value. The second value, the number of unusable pages, denotes the distance between the two pointers to the beginning and the end of a hole (if there is such); following again the interpretation above, we store is as a {\em negative} value. @D initialize control[0],control[1] @{ newPageInfo = PageInfoPtr(newSegmentStart); newHeapStart = newSegmentStart + newBytesInPI; newHeapEnd = newRealHeapEnd; control[0] = pagesInNewSegment - newPagesInPI; control[1] = -((holeEnd - holeStart) / BYTES_PER_PAGE); otherTwo = control + 2; @} How about the other two entries, {\tt control[2], control[3]}? In the current situation we know that one entry refers to the old page-info table and the other one to the old heap. We also know their values: the start of the heap, according to the convention above, is indicated by the value {\tt LONG\_MAX}; the other entry is derived from the size of the old heap; it will be a positive value, since the pages in the old heap are to be marked as free. Given these values, how do we initialize the other two entries? If in the memory the old page-info table comes before the old heap, we set the first of the other two entries to {\tt gc.pagesInPI}---as it is, as positive value---and the second one to {\tt LONG\_MAX}: @D initialize otherTwo @{ otherTwo[0] = gc.pagesInPI; otherTwo[1] = LONG_MAX; @} If, however, the old heap comes first and then the old page-info table, we change the roles of {\tt otherTwo[0]} and {\tt otherTwo[1]}: @D initialize otherTwo (swapped) @{ otherTwo[0] = LONG_MAX; otherTwo[1] = gc.pagesInPI; @} By now, we have covered two of the four possible cases, with the new segment on the left side of the old heap; the remaining two cases deal with the sitation that the new segment is right to the old heap. But this case now is easy to handle. We simply swap the first two and the second two entries in the array and write to {\tt control[2],control[3]} first, and to the {\tt otherTwo} array later. @D initialize control[2],control[3] @{ newHeapEnd = newSegmentEnd - newBytesInPI; newPageInfo = PageInfoPtr(newHeapEnd); newHeapStart = newRealHeapStart; control[2] = -((holeEnd - holeStart) / BYTES_PER_PAGE); control[3] = pagesInNewSegment - newPagesInPI; otherTwo = control + 0; @} @D prepare move @{ int control[4], *otherTwo; PageInfo* newPageInfo; word newHeapStart, newHeapEnd; if(newSegmentStart < gc.heapStart) { @< initialize control[0],control[1] @> } else { @< initialize control[2],control[3] @> } if(gc.realHeapStart == word(gc.pageInfos)) { @< initialize otherTwo @> } else { @< initialize otherTwo (swapped) @> } @< trace control array @> @} Now that the array is initialized we have to read it, with the same understanding with which it was written, i.e., we first understand an entry in the array as a switch, between the different kinds of memory segments, but once we are inside an {\tt if} branch we interpret it as a value that denotes a number of pages. We step through the array, branch according to the segment-kind, and mark {\tt control[i]}-many pages either as usuable or unusable (via {\tt markFree()} and {\tt markUnusable()}, respectively); when we meet the branch with the old info-table, we copy its pages to the new space. @D move table @{ PageInfo * p = newPageInfo; for(int i = 0; i < 4; ++i) { if (control[i] == LONG_MAX) { for(PageInfo * s = gc.pageInfos; s < gc.pageInfosEnd;) *p++ = *s++; } else if(control[i] > 0) { for(int n = control[i]; --n >= 0;) p++ -> markFree(); } else if(control[i] < 0) { p -> setCount( -control[i] ); for(int n = -control[i]; --n >= 0;) p++ -> markUnusable(); } else; } @} As the last element of the page-info table we reserve a dummy entry, that does not refer to a real page; it is used as a marker during the allocation. @D reserve dummy entry @{ p -> markUnusable(); p -> setCount( newPageInfo - p ); @} \subsubsection{Updating global variables} The internal expansion ends with an update of all global data that are involved in the description of the heap or the page-info table. These data include beginning and end of the page-info table, the heap, and the ``real" heap minus the page-info table. The data member {\tt gc.heapPagesAdd} adds the net pages of the new heap segment to the total number of pages and {\tt gc.pagesInPI} stores the new total of unusable pages for the page-info table. Any change of the base address of the heap requires a recalculation of two fundamental pseudo-constants, {\tt PItoPSconstant} and {\tt PStoPIconstant}, the recalculation of which happens inside the function {\tt recalculateConstants()}. Finally, the roaming pointer to the next free page is set to the first page in the newly allocated heap. @D update global data @{ gc.heapPagesAdd( pagesInNewSegment - newPagesInPI + gc.pagesInPI ); gc.pagesInPI = newPagesInPI; gc.pageInfos = newPageInfo; gc.pageInfosEnd = newPageInfo + usablePages; gc.heapStart = newHeapStart; gc.heapEnd = newHeapEnd; gc.realHeapEnd = newRealHeapEnd; gc.realHeapStart = newRealHeapStart; recalculateConstants(); gc.roamingPtr = PageInfoFromPageStart((ptr_t)newSegmentStart); @} The discussion of the heap expansion finishes the discussion of allocation and also the presentation of the conceptual aspects of the \fgc . The remaining sections are concerned with system dependencies, program constants, and debugging facilities. \section{System Dependencies} All collection of garbage, on the one hand, begins with a search for root pointers, i.e., pointers on the program stack, in registers, and in the static data area. This search is intimitately related to a particular compiler on a particular system: the collector needs to know the address of the stack bottom and the direction in which the stack grows; it has to access registers, and it has to know the segment(s) in memory in which static data can be found. All allocation, on the other hand, has to connect to the system allocator and to the units in which the system function does allocation. Both the initial search and the encapsulation of allocation does not depend on the particular collector type, it is the same for mark-sweep and for copy collectors. For \fgc\ we take advantage of the work done in the B{\"o}hm-Weiser-Demers collector. Their collector already provides, for all common platforms, both procedures for root detection and interfaces to system allocators. In this section we present the class {\tt SysDep} which constitutes \fgc 's interface to the various system-dependent tasks, hence to the B{\"o}hm-Weiser-Demers collector. In essence, the class {\tt SysDep} consists of three kinds of interfaces: @D the struct SysDep @{ struct SysDep { SysDep(); @< interface to the system allocator @> @< interface to the root detector @> @< stack operations @> }; @} Each interface is very lean, containing two procedures each, which mainly wrap up procedures and macros of the B{\"o}hm-Weiser-Demers collector. The latter ones mostly come with a prefix {\tt GC} and are easily distinguishable from the \fgc\ code, thus. We will look at each procedure and its implementation. \subsection{Interface to the system allocator} The interface to the system allocator includes two functions: @D interface to the system allocator @{ static word getVmPageSize(); static void* alloc(word sizeInBytes); @} The implementation of both functions is straightforward. The function {\tt getVmPageSize()}, used during the heap expansion step, directly refers to a variable {\tt GC\_page\_size}, defined in the file {\tt boehm\_os\_dep.c}. @D SysDep::getVmPageSize() @{ word SysDep::getVmPageSize() { return GC_page_size;} @} The following code snippet shows how the variable {\tt GC\_page\_size} is defined: %\begin{verbatim} @D boehm\_os\_dep.c: GC\_page\_size @{ word GC_page_size; # ifdef MSWIN32 void GC_setpagesize() { SYSTEM_INFO sysinfo; GetSystemInfo(&sysinfo); GC_page_size = sysinfo.dwPageSize; } # else # if defined(MPROTECT_VDB) || defined(PROC_VDB) void GC_setpagesize() { GC_page_size = GETPAGESIZE(); } # else /* It's acceptable to fake it. */ void GC_setpagesize() { GC_page_size = HBLKSIZE; } # endif # endif @} %\end{verbatim} % The second function in the allocator interface, the function {\tt alloc()}, simply returns the value of the macr {\tt GET\_MEM}: @D SysDep::alloc() @{ void* SysDep::alloc(word sizeInBytes) { return GET_MEM(sizeInBytes); } @} where {\tt GET\_MEM} defines a pointer to a dynamically allocated block of memory. The code snippet below lists its definition for a few operating systems; for the full definition of the macro {\tt GET\_MEM} see the file {\tt boehm\_gc\_priv.h}. %\begin{verbatim} @D boehm\_gc\_priv.h: GET\_MEM @{ # ifdef PCR char * real_malloc(); # define GET_MEM(bytes) HBLKPTR(real_malloc((size_t)bytes \ + GC_page_size + GC_page_size-1) # else # ifdef OS2 void * os2_alloc(size_t bytes); # define GET_MEM(bytes) HBLKPTR((ptr_t)os2_alloc((size_t)bytes \ + GC_page_size) \ + GC_page_size-1) # else # if defined(AMIGA) || defined(NEXT) || defined(DOS4GW) # define GET_MEM(bytes) HBLKPTR((size_t) \ calloc(1, \ (size_t)bytes + GC_page_size) \ + GC_page_size-1) # else # ifdef MSWIN32 extern ptr_t GC_win32_get_mem(word bytes); # define GET_MEM(bytes) (struct hblk *)GC_win32_get_mem(bytes) # else # ifdef MACOS ... @} %\end{verbatim} \subsection{Interface to the root detector} The interface to the B{\"o}hm-Weiser-Demers collector in the close sense includes the following two functions: @D interface to the root detector @{ static void setEnumParams(EnumRootCallback, wordPtr heapStart, wordPtr heapEnd); static void enumRoots(...); @} The second function {\tt enumRoots()}, is easier to understand, so we look at this one first. In essence, {\tt enumRoots()} calls the function {\tt GC\_push\_roots()},which is the most instrumental function for the root detector: it pushes registers and the static data on the stack and it also traverses the stack. Its full implementation can be found in the file {\tt boehm\_mark\_rts.c}. Before {\tt GC\_push\_roots()} is called, however, stack and registers are cleaned up. @D SysDep::enumRoots() @{ void SysDep::enumRoots(...) { GC_clear_a_few_frames(); GC_noop(0,0,0,0,0,0,0,0,0,0,0,0,0,0); GC_push_roots(true); } @} The first helper function {\tt GC\_clear\_a\_few\_frames()} voids the first entries on the stack: @D GC\_clear\_a\_few\_frames() @{ void GC_clear_a_few_frames() { # define NWORDS 64 volatile unsigned int frames[NWORDS]; register int i; for (i = NWORDS; i > 0; i--) frames[i-1] = 0; } @} whereas the second helper function {\tt GC\_noop()} tries to force that register contents get written back to memory. @D GC\_noop() @{ void GC_noop(...) {} @} The other function in the interface to the B{\"o}hm-Weiser-Demers root detector is the function {\tt setEnumParams()}. This function initializes the structure {\tt \_glob} with start and end of the heap and a callback function; at function invocation time the callback parameter {\tt EnumRootCallback} is bound to the {\tt markRootFromPointers()} function. @D SysDep::setEnumParams() @{ void SysDep::setEnumParams(EnumRootCallback f,wordPtr heapStart, wordPtr heapEnd) { _glob.callback = f; _glob.heapStart = heapStart; _glob.heapEnd = heapEnd; } @} The structure {\tt \_glob} serves as the turnpike between the B{\"o}hm-Weiser-Demers root detector and \fgc . Appropriately initialized, it stores all data needed for dealing with roots. Let us look at its definition and how the structure is used: (the data members that are not initialized in {\tt setEnumParams()} are initialized in the default constructor of {\tt SysDep}: @D SysDep: \_glob @{ struct { void* _GC_heap_bases[MAX_HEAP_SECTS]; void* _GC_stackbottom; mark_rts_globals mark_rts_glob; wordPtr heapStart, heapEnd; EnumRootCallback callback; } _glob; @} The structure {\tt \_glob} It is referred to by two functions: {\tt GC\_push\_conditional()} and {\tt GC\_push\_all\_stack()}. Before finishing the section on root detection we briefly present both functions. The first function, {\tt GC\_push\_conditional()}, accesses the member {\tt \_glob.callback()}---instantiated with the traverse function {\tt markFromRoots()}---and applies it to each word in the heap. @D GC\_push\_conditional() @{ inline void GC_push_conditional(void* a, void* b, bool){ # ifdef TRACE_ROOTS fprintf(stderr,"[%08X - %08X] (%d)\n", a, b, (char*)b-(char*)a); # endif if(_glob.callback == 0) return; register wordPtr i = wordPtr(a); register wordPtr end = wordPtr(b); register word left = word(_glob.heapStart); register word right = word(_glob.heapEnd); for(;i != end; ++i) { if( *i >= left && *i < right ) _glob.callback(*i); } } @} The function {\tt GC\_push\_all\_stack()} also applies the instance of {\tt \_glob.callback()} word-wise to all elements in the heap. In contrast to the previous function, however, there is no boolean parameter flag. @D GC\_push\_all\_stack() @{ inline void GC_push_all_stack(void* a, void* b){ # ifdef TRACE_ROOTS fprintf(stderr,"[%08X - %08X] (%d) stack\n",a, b,(char*)b-(char*)a); # endif if(_glob.callback == 0) return; register wordPtr i = wordPtr(a); register wordPtr end = wordPtr(b); register word left = word(_glob.heapStart); register word right = word(_glob.heapEnd); for(;i != end; ++i) { if( *i >= left && *i < right ) _glob.callback(*i); } } @} \subsection{Stack operations} The system interface provides two operations related to the program stack: @D stack operations @{ static void excludeRange(ptr_t a, ptr_t b); static void setStackBottom(void*); @} The first procedure, {\tt excludeRange()}, passes a start and an end address on to the procedure {\tt GC\_exclude\_static\_roots()} (defined in {\tt boehm\_mark\_roots.c}), which maintains a table for all regions on the stack that safely can be skipped during the search for root pointers. Within \fgc\ the function {\tt excludeRange()} applies to the internal data structures of \fgc , i.e., to the class {\tt gc.data} and to the class {\tt SysDep} itself. @D SysDep::excludeRange() @{ void SysDep::excludeRange(ptr_t a, ptr_t b) { #ifdef TRACE_ROOTS fprintf(stderr,"exclude[%08X,%08X)\n", a,b); #endif GC_exclude_static_roots(a, b); } @} The second procedure, {\tt setStackBottom}, provides the possibility to set the bottom of the stack by hand. @D SysDep::setStackBottom() @{ void SysDep::setStackBottom(void* x) { GC_stackbottom = x; } @} To call the function {\tt setStackBottom()} correctly, users have to introduce a dummy variable as the very first variable in their main program and to pass its address on to the {\tt setStackBottom()} function.\footnote{In the file {\tt boehm\_config.h} it is suggested to wrap up the original main program with the one containing the dummy variable.} The variable {\tt GC\_stackbottom} then automatically points to the bottom of the stack. @D determine stack bottom implicitly @{ #include "gc_private.h" main(int argc, char** argv, char** envp) { int dummy; gc.sysdep.setStackBottom(&dummy); } @} It is, of course, not necessary to set the stack bottom by hand. In any case, the stack bottom is already automatically determined, during the construction of the class {\tt SysDep}. \subsection{Initialization} The last function to discuss in our presentation of the class {\tt SysDep} is its default constructor. The default constructor consists of a sequence of four subroutine calls: @D SysDep::SysDep() @{ SysDep::SysDep() { GC_register_data_segments(); excludeRange(ptr_t(&_glob), ptr_t(&_glob + 1)); GC_setpagesize(); GC_stackbottom = GC_get_stack_base(); } @} Except for the second function, {\tt excludeRange()}, all functions are defined in the file {\tt boehm\_os\_dep.c}: the first one, {\tt GC\_register\_data\_segments()}, allows users to register certain static data as part of the root set; the function {\tt GC\_setpagesize()}, next, helps to determine the size of a page in a particular operating system; and the function {\tt GC\_get\_stack\_base()}, finally, provides an automatic detection of the stack bottom. With the discussion of the constructor function the section on the system interface is complete. \section{Constants} This section is divided in customizable constants, program constants, and a few implicit, but fundamental assumptions on the memory model of the compiler with which \fgc \ is expected to run. Let us start with the customizable constants. There are three constants to tune user programs: \begin{itemize} \item {\tt INITIAL\_HEAP\_SIZE} \item {\tt TOO\_BIG\_TO\_MOVE} \item {\tt POLICY\_MAX\_ALLOCED()} \end{itemize} % {\tt INITIAL\_HEAP\_SIZE} can be used to reserve memory before program start; if it is set it postpones the first call to the collecting part on the one hand, but may waste memory on the other hand. {\tt TOO\_BIG\_TO\_MOVE} defines what a {\em big} object is, that is, an object that does not participate in copy-collection. This constant is used to balance between the time spent for copying and the memory lost due to fragmentation. The function {\tt POLICY\_MAX\_ALLOCED()}, finally, allows user having the heap linearly increased instead of doubled. The constants and their default values are: @D customizable constants @{ #define INITIAL_HEAP_SIZE 30 #define TOO_BIG_TO_MOVE 19 @< POLICY\_MAX\_ALLOCED() @> @} Besides customizable constants, there are constants the correctness of the entire program depends on. Most notably, this includes the size of a page, {\tt BYTES\_PER\_PAGE}. The handling of small objects, for example, depends on its value, as do various other parts of the allocator. This constant should not be changed in any case. Similarly sensitive is the {\tt typedef} {\tt signed\_word}, the step size {\tt SPACE\_STEP}, reflecting the whole collecting strategy, and the size of the non-accessible space {\tt UNUSUABLE\_SPACE}. % \begin{itemize} \item {\tt BYTES\_PRE\_PAGE} \item {\tt SPACE\_STEP} \item {\tt UNUSABLE\_SPACE} \end{itemize} The following preprocessor directives list their initial values and also the initial values of four constants derived. @D program constants @{ #define BYTES_PER_PAGE 512 typedef signed int signed_word; #define UNUSABLE_SPACE 32767 #define SPACE_STEP 4 #define MAX_SPACE (UNUSABLE_SPACE - SPACE_STEP * 3) #define BYTES_PER_WORD sizeof(word) #define BITS_PER_WORD (8 * BYTES_PER_WORD) #define WORDS_PER_PAGE (BYTES_PER_PAGE/BYTES_PER_WORD) @} Besides the explicitly defined constants, there are a few requirements users implicitly are expected to meet. We list them here: \begin{itemize} \item Words start at word boundaries. \item Functions start at even addresses. \item The maximal size of an object is $2^{31}-1$. \end{itemize} \section{Debugging} In this section we present various debug and print functions. None of the functions is difficult to understand, in fact, they all are rather self-explanatory. We find it useful, however, to have them all gathered at one place. The following table lists their name, a brief description of what they are printing, and the file in which the function is defined. The last column notes if a function is called automatically or by users of the \fgc\ collector. (Note that {\tt TRACE\_COLLECT} in the last two entries refers to a \cpp\ preprocessor instruction which has to be defined in order to activate {\tt printfree()} and {\tt printStats()}.) \begin{center} \begin{tabular}{l|l|l|l} {\em Name } & {\em Prints} & {\em File} & {\em Called by}\\ \hline {\tt PageNoFromPtr()} & page number & structs & user \\ {\tt printpi()} & page-info table & dbgprint & user\\ {\tt printgc()} & heap & dbgprint & user\\ {\tt PageInfo::print()} & single page & structs & user \\ {\tt gc\_data::printfree()} & page statistics & structs & {\tt heapPagesAdd} \\ & & & {\tt TRACE\_COLLECT} \\ {\tt PageInfo::printStats()}& collection statistics & structs & {\tt collect}\\ & && {\tt TRACE\_COLLECT}\\ \end{tabular} \end{center} The main thing we want to do in this section is listing the code for each of the functions. We list short implementations first, beginning with the function {\tt PageNoFromPtr()}. Given a pointer into the heap, this functions returns the number (relative to the base heap address) of the corresponding page; in the address computation it uses the 1-1 correspondence between heap pages and entries in the page-info table. @D PageNoFromPtr() @{ inline int No(const PageInfo* pi) { return pi - gc.pageInfos; } inline word PageNoFromPtr(const void* p) { return No(PageInfoFromPageStart(PageStart(word(p)))); } @} The next function {\tt printpi()} loops through the page-info table and calls element-wise {\tt PageInfo::print()} (the latter function we address as the very last in this section). @D printpi() @{ void printpi() { int i=0; fprintf(stderr, "PageInfo:"); fprintf(stderr, "pageInfos: %08x pageInfosEnd: %08x", gc.pageInfos, gc.pageInfosEnd); for(PageInfo* p = gc.pageInfos; p && p <= gc.pageInfosEnd; ++p, ++i) { fprintf(stderr, "%.3d ", i); p->print(); } fprintf(stderr,"\n"); } @} Another short function is {\tt gc\_data::printfree()}. Called after heap expansion by the function {\tt heapPagesAdd()} its output is rather self-explanatory. @D gc\_data::printfree() @{ void printfree() const { #ifdef TRACE_COLLECT fprintf(stderr,"h/a/f/ma/t=%d/%d/%d/%d/%d\n",heapPages(),allocedPages(), freePages(),caMaxAlloced,collectThreshold); #endif } @} The function that users of \fgc\ presumably most frequently deal with is the function {\tt printStats()} which provides the full statistics after each collection cycle. If users un-define the macro {\tt COLLECT\_STATS} they can suppress half of its messages. Again, the print statements give enough explanation: @D PageInfo::printStats() @{ void printStats() { # ifdef COLLECT_STATS fprintf(stderr,"ps/ac pd/dc=%ld/%ld %ld/%ld\n", gc.pagesScanned, gc.allocCount,gc.pagesDiscarded,gc.discardCount); fprintf(stderr,"Average number of bytes moved during collection: %.2lfk\n", gc.bytesMoved/gc.collectionCount/1024 ); fprintf(stderr,"Average number of unmovable data per collection: %.2lfk\n", gc.totalUnmovablePages*BYTES_PER_PAGE/gc.collectionCount/1024 ); # endif fprintf(stderr,"collections count = %d, heap size = %dk\n", gc.collectionCount, gc.heapPages()*BYTES_PER_PAGE/1024); fprintf(stderr,"initial heap size = %dk, too big to move = %dk heap incr = %dk\n", gc.initialHeapSize*BYTES_PER_PAGE/1024, gc.tooManyBytesToMove/1024, gc.heapIncrement*BYTES_PER_PAGE/1024); } @} The next function, {\tt printgc()}, is also part of the small debugging module. Users can call the function to get information about the \gd\ class, more precisely, its pointers into the heap. @D printgc() @{ void printgc() { #define _p(x) (word(gc. x) - gc.realHeapStart) fprintf(stderr,"RH = [ 0x%08x - 0x%08x ) H = [ 0x%08x - 0x%08x )\n", gc.realHeapStart, gc.realHeapEnd, gc.heapStart, gc.heapEnd); fprintf(stderr,"RH = [%d %d) H = [%d %d) PI = [%d %d)\n", 0, _p(realHeapEnd), _p(heapStart), _p(heapEnd), _p(pageInfos), _p(pageInfosEnd)); fprintf(stderr,"freePages = %d, heapSpanPages = %d, pagesInPI = %d\n", gc.freePages(), gc.heapSpanPages(), gc.pagesInPI); #if 0 if(gc.realHeapStart != gc.heapStart) for(int i = 0; i < gc.pagesInPI; ++i) fprintf(stderr," %03x", i * BYTES_PER_PAGE ); for(PageInfo* p = gc.pageInfos; p != gc.pageInfosEnd; ++p) { fprintf(stderr," %03x", word(p->data())-gc.realHeapStart ); } if(gc.realHeapStart == gc.heapStart) for(int i = 0; i <= gc.pagesInPI; ++i) fprintf(stderr," %03x", word(gc.pageInfosEnd[i].data()) -gc.realHeapStart ); fprintf(stderr,"\n"); if(gc.realHeapStart != gc.heapStart) { for(int i = 0; i < gc.pagesInPI; ++i) fprintf(stderr," PI "); } {for(PageInfo* p = gc.pageInfos; p != gc.pageInfosEnd; ++p) { fprintf(stderr," %3s", (p->space == UNUSABLE_SPACE)?"XXX":"..." ); }} if(gc.realHeapStart == gc.heapStart) { for(int i = 0; i < gc.pagesInPI; ++i) fprintf(stderr," PI "); fprintf(stderr," ]"); } fprintf(stderr,"\n"); #endif } @} The last function in this section is the member function {\tt print()} of the \pgi \ class. @D PageInfo::print() @{ #define VERBOSE 1 template T min(T a, T b) { return a < b ? a : b; } void PageInfo::print() const { fprintf(stderr, "@@ 0x%08x ", data()); if(unusable()) {fprintf(stderr," XX");} else if(free()){fprintf(stderr," .. space = %d", space); } else if(size < 0) { fprintf(stderr," _%02d space = %d",-big.nPages+1, space);} if (unusable() || free() || size <0) { fprintf(stderr, "\n"); return; } #if 1 if(gc.currentSpace != gc.nextSpace) { if(space < gc.nextSpace) putchar(' '); else if(space&2) putchar('+'); else putchar('*'); } else { putchar(' '); } #else fprintf(stderr," %02d", space); #endif if(size == 0) { fprintf(stderr," %02d space = %d big (%d Bytes)\n", big.nPages,space,big.nBytes); } else { if(space&2) { int to, from; from = gc.smallSize.sz[size].classTop + size * BYTES_PER_WORD; if( gc.smallSize.sz[size].pageStart == data() ) { to = gc.smallSize.sz[size].top; } else { to = normal.to; } int count = (from - to)/(size*BYTES_PER_WORD) ; fprintf(stderr," %c%d", 'A' + size, min(9,count)); #ifdef VERBOSE if(from <= to) fprintf(stderr, " size = %d from = %d, to = %d\n", size, from, to); else fprintf(stderr, " space = %d size = %d count = %d\n", space,size, count); #endif } else { fprintf(stderr," %c%d", 'A' + size , min(9, countBits(size > 7 ? wired2.toScan:wired.toScan|wired.scanned)) ); #ifdef VERBOSE if (size > 7) { fprintf(stderr, " sp = %d sz = %d ct = %d toScan = 0x%08x scanned = 0x%08x\n", space, size, countBits(wired.scanned), wired2.toScan, wired.scanned); } else if (size > 3) { fprintf(stderr, " sp = %d sz = %d ct = %d toScan = 0x%08x scanned = 0x%08x\n", space, size, countBits(wired.scanned), wired.toScan, wired.scanned); } else { fprintf(stderr, " sp = %d sz = %d ct = %d toScan = 0x%08x%08x scanned = 0x%08x%08x\n", space, size, countBits(wired.scanned)+countBits(scanned2(data() )), wired.toScan, toScan2(data()), wired.scanned, scanned2(data()) ); } #endif } } } @} \newpage \section{Examples} In this section we present two examples. The first example illustrates the two requirements that user-defined classes have to meet. These requirements are illustrated in their bare form even though {\em class designers} merely will have to deal with them directly. Instead, we expect {\em library designer} to provide a means to factor out what does not depend on an individual class and to shift as much as possible from the class designer's side to the library's side. What this shift looks like highly depends on the structure of a library; a solution for an inheritance-based library will look different than one for a template-based library which might even be parameterized by an allocator. For the particular application of \fgc\ to libraries that are implemented with STL, we provide an adaptor ({\tt fgcAdaptor.h}). Though this paper deals with a garbage collector, rather than with adaptors to it, we show in the second example that \fgc\ easily collaborates with classes that use STL. \subsection{User-defined classes} In this section we list a small, contrived example to demonstrate: \begin{itemize} \item How to annotate a class participating in \fgc . \item What to include and how to call \fgc . \end{itemize} Our demonstration program contains the class definition, a test function, and the main program. @O demo.C @{ #include #include "fgc.C" @< demo class @> @< array class @> @< demo function @> @< main program @> @} \subsubsection{Annotating classes} The demonstration class is a small class with one pointer, one automatic and one static variable. As in every \mcc , classes have to both register and inform the collector about their internal pointers. The two relevant functions here are the function {\tt trace()} and the {\tt operator new}. \begin{itemize} \item The function {\tt trace()} encapsulates the \fgc\ function {\tt moveOrMark()} which follows an internal pointer of an object. \item The {\tt operator new} passes on to the \fgc\ function {\tt userAlloc()} the control over the allocation process. Note that {\tt userAlloc()} gets the {\tt trace()} function as its second argument. \end{itemize} The \fgc -compliant class {\tt BaseItem} reads as follows: @D demo class @{ struct BaseItem { BaseItem* next; int id; static int count; explicit BaseItem(BaseItem* n):next(n),id(count++){} @< BaseItem debug @> static void trace(BaseItem *x) { fprintf(stderr,"id, x->pg()); moveOrMark(wordPtr(&x->next)); fprintf(stderr," BaseItemTrace>\n"); } void* operator new(size_t size) { return userAlloc(size, TraverseFunc( trace )); } }; int BaseItem::count; BaseItem* head = 0; @} For debug reasons, we provide the functions {\tt pg() and print()}. %, and {\tt pointers()}. @D BaseItem debug @{ int pg() const { return PageNoFromPtr(this); } void print() { fprintf(stderr,"%d@@%d ",id, pg() ); if(next) next->print(); else fprintf(stderr, "\n"); } @} To increase the collector's workload, we additionally introduce a template array class. The array class has to provide its own definition of the allocation operator and its own trace function. The overloaded {\tt operator new} is identical to the one in previous class, but the trace function, {\tt itrace()}, looks different: The {\tt moveOrMark()} subroutine now takes the address of (the base class') {\tt next } pointer. @D array class @{ template struct Item : public BaseItem { char array[SIZE]; explicit Item(BaseItem* n):BaseItem(n){} static void itrace (Item *x) { fprintf(stderr,"< ItemTrace %d@@%d ", x->id, x->pg()); moveOrMark(wordPtr(&x->next)); fprintf(stderr, " ItemTrace> \n"); } void* operator new(size_t size) { return userAlloc(size, TraverseFunc( itrace )); } }; @} The required two annotations are easy to do in our two examples. What if classes are of a more complex structure, with more data members, subclasses, or hidden pointers, as they come from virtual inheritance? For classes with several internal pointers, the {\tt moveOrMark()} function inside the {\tt trace()} function simply has to be invoked to each of them individually. For classes that are derived from other classes, it is necessary to initiate garbage collection for the ancestors while garbage collecting the child. In the second example, we conveniently let the function {\tt itrace()} handle the {\tt next} pointer in the base class. In more complex examples, the trace function of a child has to explicitly invoke the trace function of its direct parent(s). For hidden pointers, essentially the same logic applies. In the adaptor between \fgc\ and STL-based class libraries, we have already provided support for the design of the trace function, with or without the presence of inheritance. A similar support for other libraries would certainly increase the safe use of \fgc. In the STL adaptor we currently do no provide automatic calls to the trace function of an object a hidden pointer points to, but such support is perfectly possible. %---it %requires the ability to determine the actual location of the hidden pointer, %hence the ability to determine the compiler used, and an understanding %of how a particular compiler treats internal pointers. Let us now return to the example. The demonstration function consists of two loops: @D demo function @{ void test0() { for(int i = 0; i < 100; ++i) head = new Item<10>(head); head =0; for(int i = 0; i < 100; ++i) head = new Item<10>(head); head->print(); } @} The demonstration function is called within in a third loop in the main program. Besides calling the test routine, the {\tt main()} program declares a local parameter, {\tt dummy}. Being the first local variable in the {\tt main()} program, the {\tt dummy} parameter helps to locate the bottom of the program stack.\footnote{As explained earlier, is not necessary to set the stack bottom by hand. The stack bottom can automatically be determined while constructing an instance of the class {\tt sysDep}.} @D main program @{ main() { int dummy; fprintf(stderr, "main at 0x%08x\n", main); gc.sysdep.setStackBottom(&dummy); for(int i = 0; i < 10; ++i) test0(); collect(0); } @} \subsubsection{Compilation} For the compilation of the demonstration program {\tt demo()} there are three things to do. First, the file {\tt sysdep.C} has to be compiled. It is necessary to compile the file separately to prevent undesired compiler optimization which would be possible otherwise, if the file were to be included into the source of the demonstration program. Second, the file {\tt fgc.C} has to be included into the demonstration program, and third, the generated object file has to be {linked} with the object file {\tt sysdep.o} to get an executable main program. \begin{itemize} \item Compile the file {\tt sysdep.C}. \item Include the file {\tt fgc.C} in the test program, generate an object file. \item Link the generated file together with the file {\tt sysdep.o} \end{itemize} % Again, these instructions are directed to library designers. At the level of class design and compilation users simply link a library {\tt libfgc.a} to their own executable. Different \cpp\ compilers expect different extensions for source files, depending on the actual compiler used. The files {\tt demo.C} and {\tt sysdep.C} might have to be renamed, therefore. It is not necessary, however, to rename the file {\tt fgc.C}, which is included, hence not independently translated. For the same reason it is not necessary to rename any of the files included by {\tt fgc.C}. It is important to realize, how sensitive \fgc\ (as every other garbage collector not collaborating with a compiler) is to memory optimizations a compiler might perform. In section 10 we listed the preconditions which a compiler may not violate. The most relevant conditions are the following two: % \begin{itemize} \item Words start at word boundaries. \item Functions start at even addresses. \end{itemize} For the use of VC++, for example, the second condition requires disabling of the flags {\tt -Od} or {\tt -01}; other optimizations such as optimizing speed, are not affected, of course. Similar checks are necessary for other compilers. To wrap things up, the stub of a {\tt Makefile} for the compilation of the file {\tt demo.C} looks as follows: @O Makefile.demo -t @{ CXX = g++ FLAGS = demo: demo.o sysdep.o @$(CXX) -o demo @$(FLAGS) demo.o sysdep.o @} (with extension {\tt .obj} instead of {\tt .o} if necessary). A diligent compiler might notice and complain that in the file {\tt boehm\_mark\_rts.c}, a reference to a local variable is returned. Since this variable is the {\tt dummy} variable any warning safely can be ignored. The Makefiles to create the library {\tt fgc.liba} can be found in the appendix. \subsection{STL-based libraries} Our second example deals with a matrix class (\cite{Wed96}). This class was developed independently from \fgc. It is implemented in STL, which also was not developed with garbage collection in mind. However, each STL container class is parameterized by an allocator and it is this parameter which makes connecting to the garbage collector easy. Provided there is a trace function for each STL container on the one side, and the adaptor {\tt fgcAdaptor.h} on the other side, all that is left to do for clients---the matrix class in the example---is binding their allocation parameter to the garbage collector; everything else in their code is unchanged. In this section we explain how we have to change a header file, containing the matrix class, and a main program for testing the matrix class to make both \fgc\ compliant. The adaptor itself, using template member functions in the spirit of free $\Lambda$-variables, requires a separate discussion which we lead elsewhere. The main file, as given to us, has to be extended by an {\tt include} directive to import the adaptor and the original header file {\tt gc\_matrix.h} has to be replaced by its modification, {\tt gc\_matrixFGC.h}. @D gctFgc.C @{ #include #include "fgcAdaptor.h" // added for use with fgc #include "gc_matrixFGC.h" // modified for use with fgc #include #include #include int main() { int ITER = 20; int n = 3 * 3 * 3 * 2 * 2 ; cout << n << endl; Matrix a(n, n); Matrix b(n, n); Matrix c(n, n); a.rand(); b.rand(); time_t start = clock(); int i; for(i = 0; i < ITER; ++i) { rek_beliebig_mul(a, b, c); } time_t stop = clock(); cout << "time [s] = " << double(stop-start)/CLOCKS_PER_SEC << endl; } @} The header file, the implementation of the matrix class, requires one kind of change only: for each STL container its allocator component has to be replaced by the adaptor component {\tt fgcAlloc}. This type of change is restricted to the declarative part of the source. Moreover, it does not alter any of a variable's attributes---everything else in the implementation of the class therefore remains unchanged. The replacement itself could be done almost fully automatically (note, however, that the template parameter of the {\tt fgcAlloc} class could be instantiated with different types). The following listing illustrates the replacement. It shows the beginning of the class definition up to the renewed declaration of the data member {\tt data}. It then shows the beginning of the definition of a multiplication routine, a function that requires two local variables of type {\tt vector}. The remainder of the function body is omitted as are the other (two) places where we had to exchange a vector's allocator. @D gc\_matrixFGC.h @{ #ifndef _Include_Matrix_H_ #define _Include_Matrix_H_ #include #include template class Matrix2; template class Matrix { private: int col,row; int size; vector > data; // .... }; template void mul(const T* a, const T* b, T* c, const int sz) // a != b != c; sz >= 16!! { const T* d; int n = sz; int n2 = sz << 1; int i = 0; vector > h; vector< mul_stack_t , FgcAlloc > > st; if (sz > 16) { // ... } ... #endif @} Instantiated with \fgc 's allocator {\tt FgcAlloc}, the matrix class gets garbage collected, without any further changes. \newpage \appendix \section{Output Files} The \fgc \ in the close sense, without the (modified) files of the B{\"o}hm-Weiser-Demers collector, consists of 11 source files and two header files. The following table lists the file names and gives a short description. All files except the file {\tt sysdep.C} are included files; their file extension therefore does not matter. The file {\tt sysdep.C} might have to be renamed according to the conventions of the compiler used. \begin{center} \begin{tabular}{|l|l|} \hline {\em Source file} & {\em Description} \\ \hline alloc.C & allocation \\ consts.C & constants \\ collect.C & collection \\ dbprint.C & debug and print \\ expand.C & heap expansion \\ fgc.C & the collector \\ mark.C & mark from roots \\ movemark.C & mark-sweep\& copy collect \\ scan.C & scanning \\ structs.C & data structures \\ sysdep.C & system dependencies \\ \hline \end{tabular} \end{center} % The two header files are {\tt fgc.h} and {\tt sysdep.h}.\\[0.3cm] \begin{center} \begin{tabular}{|l|l|} \hline {\em Header file} & {\em Included by} \\ \hline fgc.h & fgc \\ sysdep.h & sysdep \\ \hline \end{tabular} \end{center} \newpage % for TR This section groups together everything that belongs to a particular file---all definitions discussed in the text, but also those pieces of code that have not been explicitly mentioned in the previous text. Each file has its separate subsection; the subsections follow the alphabetic order of the file names. \subsection{The source file {\tt alloc}} @O alloc.C @{ @< allocOnePage() @> @< SizeClass::alloc() @> @< SizeClass::allocDuringCollection() @> @< PageInfo::initBig() @> @< allocPagesOrFail() @> @< allocPages() @> @< userAlloc() @> @} \paragraph{Auxiliary Definitions} @D if COLLECT\_STATS defined, set global variables @{ # ifdef COLLECT_STATS gc.allocCount++; if(p < gc.roamingPtr) gc.pagesScanned += gc.pageInfosEnd - gc.roamingPtr + p - gc.pageInfos; else gc.pagesScanned += p - gc.roamingPtr; # endif @} @D if COLLECT\_STATS defined, do bookkeeping (1) @{ # ifdef COLLECT_STATS if(p < gc.roamingPtr) gc.pagesScanned += gc.pageInfosEnd - gc.roamingPtr + p - gc.pageInfos; else gc.pagesScanned += p - gc.roamingPtr; # endif @} @D if COLLECT\_STATS defined, do bookkeeping (2) @{ # ifdef COLLECT_STATS ++gc.discardCount; gc.pagesDiscarded += nPages - count; # endif @} @D adjust global variables @{ availablePages -= (nPages - count); if(availablePages <= 0) { STATS(gc.pagesScanned += gc.heapSpanPages()); return 0; } @} @D reserve one additional word @{ ++size; @} @D allocPagesOrFail bookkeeping @{ register int availablePages = gc.freePages(); STATS(gc.allocCount++); @} @D allocate small object @{ @< allocOnePage() @> @< SizeClass::alloc() @> @< SizeClass::allocDuringCollection() @> @} @D allocate big object @{ @< PageInfo::initBig() @> @< allocPagesOrFail() @> @< allocPages() @> @} @D store page in normal queue @{ gc.normalPages_q.add(pi); pi->setInQueueFlag(); @} \subsection{The source file {\tt consts}} @O consts.C @{ @< customizable constants @> @< program constants @> @} \subsection{The source file {\tt collect}} @O collect.C @{ void collect(int nPages, char* reason = 0) { if(nPages == 0) reason = "forced"; #ifdef TRACE_COLLECT if(reason) fprintf(stderr,"collect(%d): %s\n", nPages, reason); #endif @< collect @> STATS( gc.totalUnmovablePages += gc.unmovablePagesCount ); #ifdef TRACE_COLLECT STATS( printStats() ); #endif #ifdef TRACE_HEAP printgc(); printpi(); #endif }; @} \paragraph{Auxiliary Definitions} @D book-keeping variables @{gc.unmovablePagesCount = 0; int allocedBeforeCollection = gc.allocedPages(); @} @D trace\_collect @{#ifdef TRACE_COLLECT fprintf(stderr,"alloced before %d, after %d unmove %d\n", allocedBeforeCollection, gc.allocedPages(), gc.unmovablePagesCount ); #endif @} \subsection{The source file {\tt dbgprint}} @O dbgprint.C @{ @< printpi() @> @< printgc() @> @} \subsection{The source file {\tt expand}} @O expand.C @{ #include void expand(int pagesRequested, char* reason = "no reason"); @< internalExpand() @> @< expand() @> @} \paragraph{Auxiliary Definitions} @D heap not empty @{ gc.heapPages() @} @D if TRACE\_EXPAND defined, trace (1) @{ #ifdef TRACE_EXPAND fprintf(stderr,"expand: %s, %d pages requested\n", reason, pagesRequested); #endif @} @D if TRACE\_COLLECT defined, trace (2) @{ #ifdef TRACE_COLLECT fprintf(stderr,"expand: heap created\n"); #endif @} @D new segment right of the old heap @{ newRealHeapStart = gc.realHeapStart; newRealHeapEnd = newSegmentEnd; holeStart = gc.realHeapEnd; holeEnd = newSegmentStart; @} @D compute required space @{ word pagesIncludingPI = (newRealHeapEnd - newRealHeapStart) /BYTES_PER_PAGE; word usablePages = (pagesIncludingPI * PAGEINFOS_PER_PAGE)/(PAGEINFOS_PER_PAGE + 1); word newPagesInPI = pagesIncludingPI - usablePages; word newBytesInPI = newPagesInPI * BYTES_PER_PAGE; if( (usablePages+1) * BYTES_PER_PAGEINFO > newBytesInPI ) { ++newPagesInPI; --usablePages; newBytesInPI = newPagesInPI * BYTES_PER_PAGE; } @< heap cannot hold PI @> @} @D trace control array @{ #if 0 fprintf(stderr,"control(%ld,%ld,%ld,%ld)\n", control[0], control[1], control[2], control[3]); #endif @} @D heap expansion @{ @< expand() @> @< internalExpand() @> @} \subsection{Header and source files {\tt fgc}} @O fgc.C @{ @< fgc @> @} @O fgc.h @{ #ifndef FGC_H #define FGC_H typedef void (*TraverseFunc)(void*); void* userAlloc(unsigned int size, TraverseFunc func); void moveOrMark(void *pp); void printStats(void); #endif // FGC_H @} \paragraph{Auxiliary files} @D fgc: header files @{ #include #include #include @} @D fgc: debug variables @{ //#define COLLECT_STATS //#define TRACE_COLLECT //#define TRACE_EXPAND //#define TRACE_HEAP //#define TRACE_MARK_FROM_ROOT //#define TRACE_MISSHIT //#define TRACE_PAGE_HIT //#define TRACE_ROOTS //#define TRACE_TRAVERSE //#define TRACE_SCAN #ifdef COLLECT_STATS # define STATS(x) x; #else # define STATS(x) #endif @} \subsection{The source file {\tt mark}} @O mark.C @{ @< markFromRoot() @> @} \paragraph{Auxiliary Definitions} @D initialize bitmaps for normal pages of 3 $<$ size $<$ 7 @{ if (page->space & 0x02) { // previously normal page if(missHitNormal(page, no, p)) return; live2(pageStart) = liveFromOffset(page->normal.to, gc.smallSize.sz[page->size].classTop, page->size); } else { // previously wired if(missHitWired(page->wired.scanned, no, p)) return; live2(pageStart) = page->wired.scanned; } page->wired.toScan = 1 << no; @} @D fprintf(stderr,"markFromRoot hit page \%d$\backslash$n", No(page));@{ # ifdef TRACE_MARK_FROM_ROOT fprintf(stderr,"markFromRoot hit page %d sz %d sp %d data -> 0x%08x\n", No(page), page->size, page->space, page->data()); fprintf(stderr," pointer -> 0x%08x, from/nPages %d to/nBytes %d \n", p, page->big.nPages, page->big.nBytes); # endif @} @D if TRACE\_MISSHIT defined, print current space @{ #if defined(TRACE_MISSHIT) fprintf(stderr, "markFromRoot hit space (%d)space, gc.currentSpace); #endif @} @D if TRACE\_MISSHIT defined, print offset @{ #if defined(TRACE_MISSHIT) fprintf(stderr, "mark: misshit on page size %d : offset=%d, valid 0 - %d\n", page->size, offset, gc.smallSize.sz[page->size].classTop+page->size*BYTES_PER_WORD ); #endif @} @D if TRACE\_MISSHIT defined, print live bitmaps @{ #if defined(TRACE_MISSHIT) fprintf(stderr, "mark: p=0x%08x pg %03d (obj no=%02d sz=%d sp %d ", p, PageNoFromPtr((void *)p), no, page->size, page->space); if (page->space & 2) { if(page->size >7) fprintf(stderr, "to = 0x%03x, classTop = 0x%03x, live = 0x%08x\n", page->normal.to, gc.smallSize.sz[page->size].classTop, page->wired2.live); else if (page->size > 3) { fprintf(stderr, "to = 0x%03x, classTop = 0x%03x, live2 = 0x%08x\n", page->normal.to, gc.smallSize.sz[page->size].classTop, live2(pageStart) ); } else { fprintf(stderr,"to = 0x%03x, classTop = 0x%03x, live3-4 = 0x%08x%08x\n", page->normal.to, gc.smallSize.sz[page->size].classTop, live3(pageStart), live4(pageStart)); } } else { if(page->size > 7) fprintf(stderr, "live=0x%04x, scanned=0x%08x, toScan=0x%04x\n", page->wired2.live, page->wired2.scanned, page->wired2.toScan); else if (page->size > 3) fprintf(stderr, "live2=0x%08x, scanned=0x%08x, toScan=0x%08x\n", live2(pageStart), page->wired.scanned, page->wired.toScan); else fprintf(stderr, "live3/4=0x%08x%08x, scanned/2=0x%08x%08x, toScan/2=0x%08x%08x\n", live3(pageStart), live4(pageStart), page->wired.scanned, scanned2(pageStart), page->wired.toScan, toScan2(pageStart) ); } #endif @} \subsection{The source file {\tt movemark}} @O movemark.C @{ @< moveOrMark() @> @} \paragraph{Auxiliary Definitions} @D if on continuation page, go to the first page @{ if( page->size < 0 ) { page = page->skip(); pageStart = (char*)page->data(); } @} % fprintf(stderr,"moveOrMark hit page \%d$\backslash$n", No(page)); #ifdef %TRACE_PAGE_HIT % fprintf(stderr,"moveOrMark hit page %d\n", No(page)); % #endif % @D if TRACE\_PAGE\_HIT defined, print page information @{ #ifdef TRACE_PAGE_HIT fprintf(stderr, "movemark: from 0x%08x at p %d hit page %d at 0x%08x sz %d sp %d data -> 0x%08x\n", pp, PageNoFromPtr(pp), No(page), p, page->size, page->space, page->data()); #endif @} @D if TRACE\_PAGE\_HIT defined, print: "not in current space" @{ #if defined (TRACE_PAGE_HIT) fprintf(stderr, "moveOrMark hit page at space %d - not in currentspace (%d)", page->space, gc.currentSpace); #endif @} @D if TRACE\_MISSHIT defined, print pointer to SizeClass::invalid @{ #if defined(TRACE_MISSHIT) fprintf(stderr, "movemark: Misshit from 0x%08x at 0x%08x pg %d sz %d offset %d no %d = invalid\n", pp, p, PageNoFromPtr(pageStart), page->size, offset, no); #endif @} @D if TRACE\_PAGE\_HIT defined, print offset @{ #ifdef TRACE_PAGE_HIT fprintf(stderr,"movemark offset = %d no = %d StartOffset = %d, page->size = %d\n", offset, no, objStartOffs, page->size); #endif @} @D if TRACE\_PAGE\_HIT defined, printed (adjusted) offset @{ #ifdef TRACE_PAGE_HIT fprintf(stderr,"movemark StartOffset set to %d, Object starts at %d\n", objStartOffs, offset); #endif @} @D if TRACE\_PAGE\_HIT defined, print updated pointer @{ #ifdef TRACE_PAGE_HIT fprintf(stderr, "Updating pointer from 0x%08x to 0x%08x (+ %d)\n", p, *(wordPtr)pp, objStartOffs); #endif @} @D if TRACE\_PAGE\_HIT defined, print size @{ #ifdef TRACE_PAGE_HIT fprintf(stderr, "moveOrMark smallSize %d sz %d sp %d data -> 0x%08x\n", No(page), page->size, page->space, page->data()); #endif @} \subsection{The source file {\tt scan}} @O scan.C @{ typedef TraverseFunc* TraverseFuncPtr; @< callTraverse() @> @< scanBig() @> @< scanNormal() @> @< scanWired() @> @< scan() @> @} \paragraph{Auxiliary Definitions} @D fprintf(stderr,"scanning wired...$\backslash$n"); @{# ifdef TRACE_SCAN fprintf(stderr,"scanning wired...\n"); # endif @} @D fprintf(stderr,"scanning big...$\backslash$n"); @{# ifdef TRACE_SCAN fprintf(stderr,"scanning big...\n"); # endif @} @D fprintf(stderr,"scanning normal...$\backslash$n"); @{# ifdef TRACE_SCAN fprintf(stderr,"scanning normal...\n"); # endif @} @D if TRACE\_TRAVERSE defined, print f @{ #ifdef TRACE_TRAVERSE fprintf(stderr,"callTraverse calling TraverseFunc(t=%08x) \n", *f, (void *)ObjStart); #endif @} \subsection{The source file {\tt structs}} \subsubsection{The skeleton} @O structs.C @{ @< SizeClass @> @< SmallSize @> @< PageInfo @> typedef PageInfo *PageInfoPtr; @< PageInfoQueue @> @< gc\_data @> @< PageInfo::printStats() @> /*******************************/ @< PageInfo predicates (2) @> const int BYTES_PER_PAGEINFO = sizeof(PageInfo); const int PAGEINFOS_PER_PAGE = BYTES_PER_PAGE/BYTES_PER_PAGEINFO; inline void recalculateConstants() { @< gc::PItoPSconstant @> @< gc::PStoPIconstant @> } @< PageInfo::data() @> @< PageInfoFromPageStart() @> @< PageStart() @> @< PageNoFromPtr() @> @< SizeClass::prepareForCollect() @> inline unsigned sizeInChunks(unsigned size, unsigned chunkSize) { return (size + chunkSize - 1) / chunkSize; } @< alignUp() @> @< toScan2(), scanned2() @> @< colors @> void setSpace(PageInfo* a, PageInfo* b, unsigned short space) { for(; a != b; ++a) a->space = black; } inline bool forwarded(word x){return x&1;} inline word offsetInPage(word p) { return word(p)&(BYTES_PER_PAGE - 1); } inline void copyWords(wordPtr beg, wordPtr end, wordPtr to) { #ifdef COLLECT_STATS gc.bytesMoved += BYTES_PER_WORD * (end - beg); #endif while(beg != end) { *to++ = *beg++; } } int countBits(unsigned x) { int count = 0; while(x) { count += x&1; x >>= 1; } return count; } inline bool isPowerOfTwo(int x) { while( ! (x & 1) ) x >>= 1; return x == 1; } word liveFromOffset(int from, int to, size_t size) { word mask=0; register int nto=gc.smallSize.objectNo(size, to); for(int no=gc.smallSize.objectNo(size, from); // idx 0 is invalid no <= nto && no < BITS_PER_WORD; no++) mask |= 1 << no; #if defined (TRACE_MISSHIT) fprintf(stderr, "liveFromOffset(size=%d, from=%d, to=%d) = 0x%08x\n", size, from, to, mask); #endif return mask; } inline word liveFromNo(int from, int to) { word mask=0; assert (to < BITS_PER_WORD); assert (from <= to); for(; from <= to; from++) mask |= 1 << from; #if defined(TRACE_MISSHIT) fprintf(stderr, "liveFromNo(from=%d, to=%d) = 0x%08x\n", from, to, mask); #endif return mask; } @< missHit() @> @< missHitNormal() @> inline bool missHitWired(word live, int no, word p, void *pp=0) { if ( (1<size, no, (1< @} \subsubsection{Small classes} @D SizeClass @{ struct SizeClass { @< SizeClass position variables @> @< SizeClass tables @> @< SizeClass::init() @> @< SizeClass allocation and collection @> }; @} \paragraph{Auxiliary Definitions} @D page information table @{ PageInfo @} @D gc\_data environment variables @{ int initialHeapSize; int tooManyBytesToMove; int heapIncrement; @} \subsubsection{The page information table } @D PageInfo @{ struct PageInfo { @< PageInfo data members @> @< PageInfo access functions @> @< PageInfo predicates (1) @> void initBig(int nPages, int nBytes); bool free() const; bool freeOrUnusable() const; char* data() const; @< PageInfo::skip() @> void print() const; @< PageInfo queue test and set @> }; @} @D PageInfoQueue @{ class PageInfoQueue { PageInfo* head; PageInfo* tail; public: PageInfo* getHead() {return head;} void clear() { head = tail = 0; } bool empty() const { return head == 0; } void add(PageInfo* p) { assert(p); p->next = 0; if(empty()) { tail = head = p; } else { tail -> next = p; tail = p; } } }; @} \subsubsection{The class \gd} @D gc\_data @{ struct gc_data { signed_word PItoPSconstant, PStoPIconstant; int pagesInPI; @< gc\_data heap pointers @> @< gc\_data page counters @> @< gc\_data page counter functions @> @< gc\_data::printfree() @> @< gc\_data::heapPagesAdd() @> @< gc\_data::freePagesAdd() @> @< gc\_data::heapSpanPages() @> @< gc\_data::xxSpace @> int unmovablePagesCount; @< gc\_data PageInfoQueue @> @< gc\_data::collectionInProgress() @> @< gc\_data member classes @> @< gc\_data environment variables @> @< gc\_data::gc\_data() @> #ifdef COLLECT_STATS long pagesScanned; long allocCount; long pagesDiscarded; long discardCount; double bytesMoved; double totalUnmovablePages; #endif long collectionCount; } gc; @} \paragraph{Auxiliary Definitions} @D fprintf(stderr,"collection recovered \%d pages$\backslash$n", pagesRecovered); @{#ifdef TRACE_COLLECT fprintf(stderr,"collection recovered %d pages\n", pagesRecovered); printfree(); #endif @} @D gc\_data::collectionInProgress() @{ bool collectionInProgess() const { return currentSpace != nextSpace; } @} @D global heap information @{ gc\_data @} @D if defined(TRACE\_MISSHIT), print message @{ #if defined(TRACE_MISSHIT) PageInfo *page=PageInfoFromPageStart(PageStart(p)); fprintf(stderr, "mark: Misshit from 0x%08x at p=0x%08x pg %03d sz %d (obj no=%02d, live=0x%08x)\n", pp, p, PageNoFromPtr((void *)p), page->size, no, live); #endif @} @D if defined(TRACE\_MISSHIT), print address @{ #if defined(TRACE_MISSHIT) PageInfo *page=PageInfoFromPageStart(PageStart(p)); fprintf(stderr, "%smark: Misshit normal from 0x%08x at p=0x%08x pg %03d sz %d (obj no=%02d, to=%03d (@@0x%08x) )\n", pp?"move":"", pp, p, PageNoFromPtr((void *)p), page->size, no, page->normal.to, PageStart(p)+page->normal.to); #endif @} \subsection{Header and source files {\tt sysdep}} @O sysdep.h @{ #ifndef _SYSDEP_H # define _SYSDEP_H @< SysDep typedefs @> @< the struct SysDep @> #endif @} @O sysdep.C @{ /* * Copyright (c) 1998 Rensselaer Polytechnic Institute * * Permission to use, copy, modify, distribute and sell this software * and its documentation for any purpose is hereby granted without fee, * provided that the above copyright notice appear in all copies and * that both that copyright notice and this permission notice appear * in supporting documentation. Rensselaer Polytechnic Institute makes no * representations about the suitability of this software for any * purpose. It is provided "as is" without express or implied warranty. * */ // // This file implements the interface between FGC and // boehm et al. root detection code // #include "sysdep.h" #include "boehm_gc_priv.h" #include #ifdef IRIX5 # include #endif //#define TRACE_ROOTS 1 #define HBLKDISPL(result) 0 #define MAX_HEAP_SECTS 1024 # include "boehm_mark_rts_globals.h" @< SysDep: \_glob @> #define MARK_RTS_GLOBALS_BASE _glob.mark_rts_glob #define GC_heap_bases (_glob._GC_heap_bases) #define GC_stackbottom (_glob._GC_stackbottom) #undef DYNAMIC_LOADING #include "boehm_os_dep.c" #ifdef MSWIN32 # define MSCDECL __cdecl #else # define MSCDECL #endif extern "C" { void MSCDECL GC_push_one(word p); }; #include "boehm_dyn_load.c" #ifndef IRIX5 #include "boehm_mach_dep.c" #else // use boehm_mips_sgi_mach_dep.s instead extern "C" { extern void GC_push_regs(); } #endif @< GC\_push\_conditional() @> @< GC\_push\_all\_stack() @> void GC_abort(const char* msg) { fprintf(stderr, msg); abort(); } void MSCDECL GC_push_one(word p) { # ifdef TRACE_ROOTS fprintf(stderr,"Register: %08X\n", p); # endif if(_glob.callback == 0) return; if( p >= word(_glob.heapStart) && p < word(_glob.heapEnd) ) _glob.callback(p); } #include "boehm_mark_rts.c" @< SysDep::excludeRange() @> @< SysDep::SysDep() @> @< SysDep::getVmPageSize() @> @< SysDep::alloc() @> @< SysDep::setEnumParams() @> @< SysDep::enumRoots() @> @< SysDep::setStackBottom() @> @} \paragraph{Auxiliary Definitions} @D SysDep typedefs @{ typedef unsigned int word; typedef word *wordPtr; typedef char* ptr_t; typedef void (*EnumRootCallback)(word); @} @D system dependencies @{ @} \subsection{Miscellanae} @O boehm_clean.cpp @{ @< GC\_clear\_a\_few\_frames() @> @< GC\_noop() @> @) @D mark-sweep or copy-collect @{ @} \newpage \section{Adapting the B{\"o}hm-Weiser-Demers Collector} Root detection is an essential part of a garbage collector. In the \fgc\ this task is passed on to the B{\"o}hm-Weiser-Demers collector; the portability of \fgc\ in particular results from the portability of their collector. In this section we list those files of the B{\"o}hm-Weiser-Demers collector that are integrated in \fgc ; to avoid blurring the origin, the file names are prefixed with {\tt boehm\_}. None of the files listed is exactly identical with the original file, they all have been modified to work with \fgc . The following table gives the original file name and its name within \fgc . Files of the B{\"o}hm-Weiser-Demers collector that are not listed here, are not requird to run \fgc . \begin{center} \begin{tabular}{|l|l|}\hline {\em Original file name} & {\em Name in \fgc }\\ \hline & boehm\_clean.cpp \\ config.h & boehm\_config.h\\ dyn\_load.c & boehm\_dyn\_load.c \\ gc\_priv. h & boehm\_gc\_priv.c \\ mach\_dep.c & boehm\_mach\_dep.c \\ mark\_rts.c & boehm\_mark\_rts.c \\ & boehm\_mark\_rts\_globals.h \\ os\_dep.c & boehm\_os\_dep.c \\ \hline \end{tabular} \end{center} \section{User Interface} The user interface consists of two files: \begin{itemize} \item The file {\tt fgc.C} \item The file {\tt sysdep.C} \end{itemize} For the second file, {\tt sysdep.C}, see section 9; the first file, {\tt fgc.C}, has not been presented yet. This file gathers the various parts of the collector and imports them using the {\tt include} mechanism: @D included files @{ #include "fgc.h" #include "sysdep.h" #include "boehm_clean.C" #include "consts.C" #include "structs.C" #include "dbgprint.C" #include "expand.C" #include "scan.C" #include "mark.C" #include "collect.C" #include "alloc.C" #include "movemark.C" @} Besides {\tt include} directives, the file {\tt fgc.C} defines several constants for tracing and debugging information. The following lists gives the constant identifiers and their intended meaning. \begin{itemize} \item TRACE\_COLLECT monitors the begin of a collection cycle and the begin of a heap expansion, prints also the number of pages recovered. \item COLLECT\_STATS provides various kinds of statistics regarding preconditions and postconditions of both collection and allocation. Uses the format: ps/ac/dc/pd with \begin{itemize} \item ps: number of pages scanned before enough contiguous pages were found \item ac: allocation count \item dc: number of discards (blocks of free pages not big enough) \item pd: number of pages discarded \end{itemize} \item TRACE\_EXPAND reports any heap expansion. \item TRACE\_HEAP prints the status of the heap and the page-info table. \item TRACE\_MARK\_FROM\_ROOT reports when an object was hit by a root pointer. \item TRACE\_MISSHIT reports when an object was hit that is not alive. \item TRACE\_PAGE\_HIT \item TRACE\_ROOTS prints stack regions and register contents. reports when an object was hit by the user's trace function. \item TRACE\_SCAN prints a message before scanning a particular queue. \item TRACE\_TRAVERSE monitors the function {\tt callTraverse()}. \end{itemize} \newpage @D fgc @{ @< fgc: header files @> @< fgc: debug variables @> @< included files @> @} \section{Makefiles} \subsection{Generic Makefile} @O Makefile -t @{ # -*- Makefile -*- # # Create library fgclib.a # # DOS Users: set MAKE_MODE=UNIX SHELL = /bin/sh #CXX = g++ CXX = /usr/local/egcs/bin/g++ CEXT = C CFLAGS = -O3 LDFLAGS= -32 #-O3 #-g3 # fgc debug options TESTDEFINES = -DTRACE_EXPAND -DTRACE_COLLECT -DTRACE_HEAP \ -DTRACE_SCAN -DDBG -Ddo_dbg -DTRACE_PAGE_HIT \ -DTRACE_MARK_FROM_ROOT -DTRACE_TRAVERSE -DTRACE_MISSHIT # egcs cygnus win32 flag DEFINES = -DHBLKSIZE=1024 -DTRACE_EXPAND -DTRACE_COLLECT #@$(TESTDEFINES) %.o : %.C @$(CXX) @$(DEFINES) @$(CFLAGS) -c @$< -o @$@@ FGCINC = fgc.h sysdep.h boehm_clean.C consts.C structs.C expand.C\ scan.C mark.C collect.C alloc.C movemark.C dbgprint.C SYSDEPINC = boehm_dyn_load.c boehm_config.h boehm_dyn_load.c boehm_gc_priv.h\ boehm_mach_dep.c boehm_mark_rts.c boehm_mark_rts_globals.h\ boehm_os_dep.c lib: fgc.o sysdep.o Makefile ar vr libfgc.a sysdep.o fgc.o cp libfgc.a ../lib sysdep.o: sysdep.@$(CEXT) @$(SYSDEPINC) fgc.o: fgc.@$(CEXT) @$(FGCINC) Makefile test: clean @$(CXX) @$(DEFINES) @$(TESTDEFINES) @$(CFLAGS) -c fgc.C @$(CXX) @$(DEFINES) @$(TESTDEFINES) @$(CFLAGS) -c sysdep.C @$(CXX) @$(DEFINES) @$(TESTDEFINES) @$(CFLAGS) -c demo.C @$(CXX) -o demo @$(DEFINES) @$(TESTDEFINES) @$(CFLAGS) demo.o sysdep.o @@echo testing fgc ...; ./demo 2> tracedemo.tmp; echo @@echo " ... successful \(trace information: see ./tracedemo.tmp\)" clean: -rm *.o core *.tmp veryclean: -rm *.o *.a @} \subsection{SGI Makefile} @O Makefile.sgi -t @{ # -*- Makefile -*- # # Create library fgclib.a # # DOS Users: set MAKE_MODE=UNIX SHELL = /bin/sh #CXX = g++ CXX = /usr/local/egcs/bin/g++ CEXT = C CFLAGS = -O3 LDFLAGS= -32 #-O3 #-g3 # fgc debug options TESTDEFINES = -DTRACE_EXPAND -DTRACE_COLLECT -DTRACE_HEAP \ -DTRACE_SCAN -DDBG -Ddo_dbg -DTRACE_PAGE_HIT \ -DTRACE_MARK_FROM_ROOT -DTRACE_TRAVERSE -DTRACE_MISSHIT # egcs cygnus win32 flag DEFINES = -DHBLKSIZE=1024 -DTRACE_EXPAND -DTRACE_COLLECT #@$(TESTDEFINES) %.o : %.C @$(CXX) @$(DEFINES) @$(CFLAGS) -c @$< -o @$@@ FGCINC = fgc.h sysdep.h boehm_clean.C consts.C structs.C expand.C\ scan.C mark.C collect.C alloc.C movemark.C dbgprint.C SYSDEPINC = boehm_dyn_load.c boehm_config.h boehm_dyn_load.c boehm_gc_priv.h\ boehm_mark_rts.c boehm_mark_rts_globals.h\ boehm_os_dep.c lib: fgc.o sysdep.o boehm_mips_sgi_mach_dep.o boehm_mips_sgi_mach_dep.o Makefile ar vr libfgc.a sysdep.o fgc.o boehm_mips_sgi_mach_dep.o cp libfgc.a ../lib sysdep.o: sysdep.@$(CEXT) @$(SYSDEPINC) fgc.o: fgc.@$(CEXT) @$(FGCINC) Makefile boehm_mips_sgi_mach_dep.o: boehm_mips_sgi_mach_dep.s test: clean @$(CXX) @$(DEFINES) @$(TESTDEFINES) @$(CFLAGS) -c fgc.C @$(CXX) @$(DEFINES) @$(TESTDEFINES) @$(CFLAGS) -c sysdep.C @$(CXX) @$(DEFINES) @$(TESTDEFINES) @$(CFLAGS) -c demo.C @$(CXX) -o demo @$(DEFINES) @$(TESTDEFINES) @$(CFLAGS) demo.o -L../lib -lfgc @@echo testing fgc ...; ./demo 2> tracedemo.tmp; echo @@echo " ... successful \(trace information: see ./tracedemo.tmp\)" clean: -rm *.o core *.tmp veryclean: -rm *.o *.a @} \section{Macros} @m %\section{Identifiers} @u % \section{References} \newpage \bibliography{fgc} \bibliographystyle{plain} \nocite{DeDoZo93} \nocite{Bar88} \nocite{AtFl96} \nocite{JoLi96} \nocite{NiSc98} \nocite{Bar89} \nocite{BoWe88} \nocite{BoDeSh91} \nocite{AFI95} \nocite{AFI97} \nocite{IWMM92} \nocite{IWMM95} \nocite{Che70} \nocite{DLM78} \nocite{ElDe93} \nocite{Str83} \end{document} @O fgc.bib @{ @@MastersThesis{Wed96, author = {Sebastian Wedeniwski}, title = {Generische {M}atrizen und die {I}mplementation schneller {M}atrixoperationen}, school = {(Diplomarbeit), WSI f{\"u}r Informatik, Universit{\"a}t T{\"u}bingen}, year = 1996 } @@Article{Sta84, author = {Stamos, James W.}, title = {Static grouping of small objects to enhance performance of a paged virtual memory}, journal = {ACM Transactions on Computer Systems}, year = 1984, volume = 3, number = 2, pages = {155-180} } @@Article{WLM91, author = {Wilson, Paul R. and Lam, Michael S. and Moher, Thomas G. }, title = {Effective static-graph reorganization to improve locality in garbage collected systems}, journal = {ACM Sigplan Notices}, year = 1991, volume = 6, number = 26, pages = {177-191} } @@InProceedings{Ede92a, author = {Daniel R. Edelson}, title = {Smart pointers: They're smart, but they're not pointers}, booktitle = {USENIX C++ Conference}, editor = {USENIX Association}, year = 1992 } @@techreport{DeDoZo93, author = {David L. Detlefs and Al Dosser and Benjamin Zorn}, title = {Memory Allocation Costs in Large {C} and {C++} Programs}, year = {1993}, month = {August} } @@Unpublished{ElDe93, author = {John R. Ellis and David L. Detlefs}, title = {Safe\, Efficient Garbage Collection for {C}++}, note = {Unpublished}, year = 1993, month = {June}, gorik = {Have it} } @@Article{Che70, author = {C.J. Cheney}, title = {A non-recursive list compacting algorithm}, journal = {Communications of the ACM}, year = 1970, volume = 13, number = 11, pages = {965-975} } @@Article{DLM78, author = {E. Dijkstra and L. Lamport and A. Martin and C. Scholten and E. Steffens}, title = {On-the-fly garbage collection: An exercise in cooperation}, journal = {Communications of the ACM}, year = 1978, volume = 21, number = 11, pages = {965-975} } @@techreport{Bar88, author = "Bartlett, Joel F.", title = "Compacting Garbage Collection with Ambiguous Roots", number = "88/2", URL = "http://www.research.digital.com/wrl/techreports/88.2.ps", institution = "DEC Western Research Laboratory", month = Feb, comment = "Excellent trick here---make newness a page property, not an address-range property, Also in Lisp Pointers 1, 6 (April--June 1988), pp. 2--12", year = 1988 } @@InProceedings{NiSc98, author = {Nishanov, Gor V. and Sibylle Schupp}, title = {Garbage Collection in Generic Libraries}, booktitle = {International Symposium for Memory Managment 1998}, year = 1998 } @@techreport{Bar89, author = "Joel F. Bartlett", title = "Mostly-{C}opying Garbage Collection picks up Generations and {C++}", institution = "DEC Western Research Laboratory", type = "Technical Note", volume = "TN--12", month = oct, year = "1989", URL = "{\tt ftp://gatekeeper.dec.com/pub/DEC/WRL/research-reports/WRL-TN-12.ps}", note = "Available at {\tt ftp://gatekeeper.dec.com/pub/DEC/CCgc}", } @@Article{BoWe88, author = {Hans-J. Boehm and Mark Weiser}, title = {Garbage Collection in an Uncooperative Environment}, journal = {Software Practice \& Experience}, year = 1988, month = {September}, volume = 18, number = 9, pages = {807--820} } @@InProceedings{BoDeSh91, author = {Hans Boehm and Alan Demers and Scott Shenker}, title = {Mostly parallel garbage collection}, booktitle = {Proceedings of the SIGPLAN'92 Conference on Programming Language Design and Implementation}, pages = {157-164}, year = {1991}, month = {June}, volume = 26, number = 6 } @@inproceedings{AFI95, author = {Giuseppe Attardi and Tito Flagella and Pietro Iglio}, title = {Performance Tuning in a Customizable Collector}, booktitle = {Proceedings of International Workshop on Memory Management}, crossref = {IWMM95}, year = 1995 } @@UNPUBLISHED{AFI97, author = {Giuseppe Attardi and Tito Flagella and Pietro Iglio}, title = {A Customisable Memory Management Framework for {C++}}, year = 1997, note = {Available at {\tt ftp://ftp.di.unipi.it/pub/project/posso/cmm/cmm.tgz}}, gorik = {Have it. Avaiable with distribution of Cmm} } @@proceedings{IWMM92, key = "IWMM92", booktitle = "Proceedings of International Workshop on Memory Management", title = "Proceedings of International Workshop on Memory Management", editor = "Yves Bekkers and Jacques Cohen", address = "St Malo, France", publisher = "Springer Verlag", series = "Lecture Notes in Computer Science", volume = 637, month = "16--18~" # sep, year = 1992 } @@proceedings{IWMM95, key = "IWMM95", booktitle = "Proceedings of International Workshop on Memory Management", title = "Proceedings of International Workshop on Memory Management", editor = "Henry Baker", address = "Kinross, Scotland", publisher = "Springer Verlag", series = "Lecture Notes in Computer Science", volume = 986, month = sep, year = 1995 } @@Article{AtFl96, author = {Guiseppe Attardi and Tito Flagella}, title = {Memory Management in the {PoSSo} Solver}, journal = {Journal of Symbolic Computation}, year = 1996, volume = 21, number = 3, month = {Mar} } @@Book{JoLi96, author = {Richard Jones and Rafael Lins}, title = {Garbage Collection. Algorithms for Automatic Dynamic Memory Mangment}, publisher = {John Wiley}, year = 1996 } @@Manual{C++98, title = {C++ Standard, ISO/IEC 14882:1998}, organization = {ANSI-ISO-IEC}, edition = {{ANSI} Standards for Information Technology}, year = 1998 } @@Manual{C++97, title = "X3 {S}ecretariat: Draft Standard---The {C++} Language. X3J16/9 7-14882", organization = "Information Technology Council ({NSITC})", year = 1997, month = "Apr" } @@Article{Str83, author = {Bjarne Stroustrup}, title = {Adding Classes to {C}: An Exercise in Language Evolution}, journal = {Software---Practice and Experience}, year = 1983, volume = 13, pages = {139--161} } @@UNPUBLISHED{STLSGI, author = {Silicon Graphics}, title={{S}tandard {T}emplate {L}ibrary {P}rogramming {G}uide}, year=1998, note={{\tt http://www.sgi.com/Technology/STL/}} } @@Book{MuSa96, author = "David Musser and Atul Saini", title = "STL Tutorial and Reference Guide. C++ Programming with the Standard Template Library", publisher = "Addison-Wesley", year = 1996 } @@Misc{StLe94, author = "Stepanov, Alexander A. and Meng Lee", title = " The {S}tandard {T}emplate {L}ibrary", howpublished = "Available by anonymous ftp from {\tt ftp.rpi.edu/pub/stl.doc.ps.Z}", year = 1994, month = "Sep", annote = "revised July 1995" } @@Book{Aus99, author = {Matt Austern}, title = {Generic Programming and the {STL}}, publisher = {Addison-Wesley}, year = {1999} } @} @O Figure4.eps @{%!PS-Adobe-2.0 EPSF-2.0 %%Title: Figure4.eps %%Creator: fig2dev Version 3.2 Patchlevel 0-beta3 %%CreationDate: Thu Feb 18 13:25:52 1999 %%For: millst@@dishwasher.cs.rpi.edu (Toby-John Mills) %%Orientation: Portrait %%BoundingBox: 0 0 376 75 %%Pages: 0 %%BeginSetup %%EndSetup %%Magnification: 1.0000 %%EndComments /$F2psDict 200 dict def $F2psDict begin $F2psDict /mtrx matrix put /col-1 {0 setgray} bind def /col0 {0.000 0.000 0.000 srgb} bind def /col1 {0.000 0.000 1.000 srgb} bind def /col2 {0.000 1.000 0.000 srgb} bind def /col3 {0.000 1.000 1.000 srgb} bind def /col4 {1.000 0.000 0.000 srgb} bind def /col5 {1.000 0.000 1.000 srgb} bind def /col6 {1.000 1.000 0.000 srgb} bind def /col7 {1.000 1.000 1.000 srgb} bind def /col8 {0.000 0.000 0.560 srgb} bind def /col9 {0.000 0.000 0.690 srgb} bind def /col10 {0.000 0.000 0.820 srgb} bind def /col11 {0.530 0.810 1.000 srgb} bind def /col12 {0.000 0.560 0.000 srgb} bind def /col13 {0.000 0.690 0.000 srgb} bind def /col14 {0.000 0.820 0.000 srgb} bind def /col15 {0.000 0.560 0.560 srgb} bind def /col16 {0.000 0.690 0.690 srgb} bind def /col17 {0.000 0.820 0.820 srgb} bind def /col18 {0.560 0.000 0.000 srgb} bind def /col19 {0.690 0.000 0.000 srgb} bind def /col20 {0.820 0.000 0.000 srgb} bind def /col21 {0.560 0.000 0.560 srgb} bind def /col22 {0.690 0.000 0.690 srgb} bind def /col23 {0.820 0.000 0.820 srgb} bind def /col24 {0.500 0.190 0.000 srgb} bind def /col25 {0.630 0.250 0.000 srgb} bind def /col26 {0.750 0.380 0.000 srgb} bind def /col27 {1.000 0.500 0.500 srgb} bind def /col28 {1.000 0.630 0.630 srgb} bind def /col29 {1.000 0.750 0.750 srgb} bind def /col30 {1.000 0.880 0.880 srgb} bind def /col31 {1.000 0.840 0.000 srgb} bind def end save -3.0 78.0 translate 1 -1 scale /cp {closepath} bind def /ef {eofill} bind def /gr {grestore} bind def /gs {gsave} bind def /sa {save} bind def /rs {restore} bind def /l {lineto} bind def /m {moveto} bind def /rm {rmoveto} bind def /n {newpath} bind def /s {stroke} bind def /sh {show} bind def /slc {setlinecap} bind def /slj {setlinejoin} bind def /slw {setlinewidth} bind def /srgb {setrgbcolor} bind def /rot {rotate} bind def /sc {scale} bind def /sd {setdash} bind def /ff {findfont} bind def /sf {setfont} bind def /scf {scalefont} bind def /sw {stringwidth} bind def /tr {translate} bind def /tnt {dup dup currentrgbcolor 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add srgb} bind def /shd {dup dup currentrgbcolor 4 -2 roll mul 4 -2 roll mul 4 -2 roll mul srgb} bind def /$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def /$F2psEnd {$F2psEnteredState restore end} def %%EndProlog $F2psBegin 10 setmiterlimit n -1000 2294 m -1000 -1000 l 7312 -1000 l 7312 2294 l cp clip 0.06000 0.06000 sc % Polyline 7.500 slw n 2250 607 m 2250 382 l gs col0 s gr % Polyline n 3150 607 m 3150 382 l gs col0 s gr /Times-Roman ff 180.00 scf sf 300 750 m gs 1 -1 sc (next) col0 sh gr % Polyline n 2925 232 m 3000 307 l gs col0 s gr % Polyline n 2925 232 m 2925 157 l gs col0 s gr % Polyline n 5625 232 m 5625 157 l gs col0 s gr % Polyline n 5625 232 m 5550 307 l gs col0 s gr % Polyline n 3825 232 m 3750 307 l gs col0 s gr % Polyline n 3825 232 m 3825 157 l gs col0 s gr % Polyline n 1125 232 m 1050 307 l gs col0 s gr % Polyline n 1125 232 m 1125 157 l gs col0 s gr % Polyline n 1950 232 m 1875 307 l gs col0 s gr % Polyline n 4050 607 m 4050 382 l gs col0 s gr % Polyline n 4950 607 m 4950 382 l gs col0 s gr % Polyline n 5850 607 m 5850 382 l gs col0 s gr % Polyline n 450 607 m 450 382 l gs col0 s gr % Polyline n 1350 607 m 1350 382 l gs col0 s gr % Polyline n 1950 232 m 1950 157 l gs col0 s gr % Polyline n 6300 382 m 6300 1282 l gs col-1 s gr % Polyline n 75 1057 m 6300 1057 l gs col-1 s gr % Polyline n 75 607 m 6300 607 l gs col-1 s gr % Polyline n 75 832 m 6300 832 l gs col-1 s gr % Polyline n 75 382 m 6300 382 l 6300 1282 l 75 1282 l cp gs col-1 s gr % Arc gs n 825.0 757.0 604.7 -172.9 -60.3 arc gs col-1 s gr gr % Polyline n 5400 382 m 5400 1282 l gs col-1 s gr % Polyline n 4500 382 m 4500 1282 l gs col-1 s gr % Polyline n 1800 382 m 1800 1282 l gs col-1 s gr % Arc gs n 1650.0 757.0 604.7 -172.9 -60.3 arc gs col-1 s gr gr % Polyline n 2700 382 m 2700 1282 l gs col-1 s gr % Polyline n 3600 382 m 3600 1282 l gs col-1 s gr % Polyline n 900 382 m 900 1282 l gs col-1 s gr % Polyline n 6300 382 m 75 382 l gs col-1 s gr % Arc gs n 3836.4 2796.7 2721.8 -51.0 -109.6 arcn gs col-1 s gr gr % Arc gs n 4967.0 1830.9 1729.0 -138.4 -67.6 arc gs col-1 s gr gr % Arc gs n 3167.0 1830.9 1729.0 -138.4 -67.6 arc gs col-1 s gr gr $F2psEnd rs @} @O Figure5.eps @{%!PS-Adobe-2.0 EPSF-2.0 %%Title: Figure5.eps %%Creator: fig2dev Version 3.2 Patchlevel 0-beta3 %%CreationDate: Thu Feb 18 13:25:59 1999 %%For: millst@@dishwasher.cs.rpi.edu (Toby-John Mills) %%Orientation: Portrait %%BoundingBox: 0 0 381 142 %%Pages: 0 %%BeginSetup %%EndSetup %%Magnification: 1.0000 %%EndComments /$F2psDict 200 dict def $F2psDict begin $F2psDict /mtrx matrix put /col-1 {0 setgray} bind def /col0 {0.000 0.000 0.000 srgb} bind def /col1 {0.000 0.000 1.000 srgb} bind def /col2 {0.000 1.000 0.000 srgb} bind def /col3 {0.000 1.000 1.000 srgb} bind def /col4 {1.000 0.000 0.000 srgb} bind def /col5 {1.000 0.000 1.000 srgb} bind def /col6 {1.000 1.000 0.000 srgb} bind def /col7 {1.000 1.000 1.000 srgb} bind def /col8 {0.000 0.000 0.560 srgb} bind def /col9 {0.000 0.000 0.690 srgb} bind def /col10 {0.000 0.000 0.820 srgb} bind def /col11 {0.530 0.810 1.000 srgb} bind def /col12 {0.000 0.560 0.000 srgb} bind def /col13 {0.000 0.690 0.000 srgb} bind def /col14 {0.000 0.820 0.000 srgb} bind def /col15 {0.000 0.560 0.560 srgb} bind def /col16 {0.000 0.690 0.690 srgb} bind def /col17 {0.000 0.820 0.820 srgb} bind def /col18 {0.560 0.000 0.000 srgb} bind def /col19 {0.690 0.000 0.000 srgb} bind def /col20 {0.820 0.000 0.000 srgb} bind def /col21 {0.560 0.000 0.560 srgb} bind def /col22 {0.690 0.000 0.690 srgb} bind def /col23 {0.820 0.000 0.820 srgb} bind def /col24 {0.500 0.190 0.000 srgb} bind def /col25 {0.630 0.250 0.000 srgb} bind def /col26 {0.750 0.380 0.000 srgb} bind def /col27 {1.000 0.500 0.500 srgb} bind def /col28 {1.000 0.630 0.630 srgb} bind def /col29 {1.000 0.750 0.750 srgb} bind def /col30 {1.000 0.880 0.880 srgb} bind def /col31 {1.000 0.840 0.000 srgb} bind def end save -4.0 145.0 translate 1 -1 scale /cp {closepath} bind def /ef {eofill} bind def /gr {grestore} bind def /gs {gsave} bind def /sa {save} bind def /rs {restore} bind def /l {lineto} bind def /m {moveto} bind def /rm {rmoveto} bind def /n {newpath} bind def /s {stroke} bind def /sh {show} bind def /slc {setlinecap} bind def /slj {setlinejoin} bind def /slw {setlinewidth} bind def /srgb {setrgbcolor} bind def /rot {rotate} bind def /sc {scale} bind def /sd {setdash} bind def /ff {findfont} bind def /sf {setfont} bind def /scf {scalefont} bind def /sw {stringwidth} bind def /tr {translate} bind def /tnt {dup dup currentrgbcolor 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add srgb} bind def /shd {dup dup currentrgbcolor 4 -2 roll mul 4 -2 roll mul 4 -2 roll mul srgb} bind def /reencdict 12 dict def /ReEncode { reencdict begin /newcodesandnames exch def /newfontname exch def /basefontname exch def /basefontdict basefontname findfont def /newfont basefontdict maxlength dict def basefontdict { exch dup /FID ne { dup /Encoding eq { exch dup length array copy newfont 3 1 roll put } { exch newfont 3 1 roll put } ifelse } { pop pop } ifelse } forall newfont /FontName newfontname put newcodesandnames aload pop 128 1 255 { newfont /Encoding get exch /.notdef put } for newcodesandnames length 2 idiv { newfont /Encoding get 3 1 roll put } repeat newfontname newfont definefont pop end } def /isovec [ 8#200 /grave 8#201 /acute 8#202 /circumflex 8#203 /tilde 8#204 /macron 8#205 /breve 8#206 /dotaccent 8#207 /dieresis 8#210 /ring 8#211 /cedilla 8#212 /hungarumlaut 8#213 /ogonek 8#214 /caron 8#220 /dotlessi 8#230 /oe 8#231 /OE 8#240 /space 8#241 /exclamdown 8#242 /cent 8#243 /sterling 8#244 /currency 8#245 /yen 8#246 /brokenbar 8#247 /section 8#250 /dieresis 8#251 /copyright 8#252 /ordfeminine 8#253 /guillemotleft 8#254 /logicalnot 8#255 /endash 8#256 /registered 8#257 /macron 8#260 /degree 8#261 /plusminus 8#262 /twosuperior 8#263 /threesuperior 8#264 /acute 8#265 /mu 8#266 /paragraph 8#267 /periodcentered 8#270 /cedilla 8#271 /onesuperior 8#272 /ordmasculine 8#273 /guillemotright 8#274 /onequarter 8#275 /onehalf 8#276 /threequarters 8#277 /questiondown 8#300 /Agrave 8#301 /Aacute 8#302 /Acircumflex 8#303 /Atilde 8#304 /Adieresis 8#305 /Aring 8#306 /AE 8#307 /Ccedilla 8#310 /Egrave 8#311 /Eacute 8#312 /Ecircumflex 8#313 /Edieresis 8#314 /Igrave 8#315 /Iacute 8#316 /Icircumflex 8#317 /Idieresis 8#320 /Eth 8#321 /Ntilde 8#322 /Ograve 8#323 /Oacute 8#324 /Ocircumflex 8#325 /Otilde 8#326 /Odieresis 8#327 /multiply 8#330 /Oslash 8#331 /Ugrave 8#332 /Uacute 8#333 /Ucircumflex 8#334 /Udieresis 8#335 /Yacute 8#336 /Thorn 8#337 /germandbls 8#340 /agrave 8#341 /aacute 8#342 /acircumflex 8#343 /atilde 8#344 /adieresis 8#345 /aring 8#346 /ae 8#347 /ccedilla 8#350 /egrave 8#351 /eacute 8#352 /ecircumflex 8#353 /edieresis 8#354 /igrave 8#355 /iacute 8#356 /icircumflex 8#357 /idieresis 8#360 /eth 8#361 /ntilde 8#362 /ograve 8#363 /oacute 8#364 /ocircumflex 8#365 /otilde 8#366 /odieresis 8#367 /divide 8#370 /oslash 8#371 /ugrave 8#372 /uacute 8#373 /ucircumflex 8#374 /udieresis 8#375 /yacute 8#376 /thorn 8#377 /ydieresis] def /Times-Roman /Times-Roman-iso isovec ReEncode /$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def /$F2psEnd {$F2psEnteredState restore end} def %%EndProlog $F2psBegin 10 setmiterlimit n -1000 3412 m -1000 -1000 l 7415 -1000 l 7415 3412 l cp clip 0.06000 0.06000 sc % Polyline 7.500 slw n 3375 225 m 3375 75 l gs col0 s gr % Polyline n 375 225 m 375 75 l gs col0 s gr /Times-Roman-iso ff 180.00 scf sf 225 1800 m gs 1 -1 sc (...) col0 sh gr /Times-Roman-iso ff 180.00 scf sf 5625 1800 m gs 1 -1 sc (...) col0 sh gr % Polyline n 2775 225 m 2775 75 l gs col0 s gr /Times-Roman-iso ff 180.00 scf sf 3525 600 m gs 1 -1 sc (...) col0 sh gr /Times-Roman-iso ff 180.00 scf sf 3525 300 m gs 1 -1 sc (...) col0 sh gr /Times-Roman-iso ff 180.00 scf sf 3525 150 m gs 1 -1 sc (...) col0 sh gr /Times-Roman-iso ff 180.00 scf sf 75 600 m gs 1 -1 sc (...) col0 sh gr /Times-Roman-iso ff 180.00 scf sf 75 450 m gs 1 -1 sc (...) col0 sh gr /Times-Roman-iso ff 180.00 scf sf 75 300 m gs 1 -1 sc (...) col0 sh gr /Times-Roman-iso ff 180.00 scf sf 75 150 m gs 1 -1 sc (...) col0 sh gr % Polyline n 150 75 m 3525 75 l gs col0 s gr % Polyline n 3075 75 m 3075 675 l gs col0 s gr % Polyline n 3525 675 m 150 675 l gs col0 s gr % Polyline n 975 225 m 975 75 l gs col0 s gr % Polyline n 1575 225 m 1575 75 l gs col0 s gr % Polyline n 2175 225 m 2175 75 l gs col0 s gr % Polyline n 975 675 m 2400 1125 l gs col0 s gr /Times-Roman-iso ff 180.00 scf sf 3525 450 m gs 1 -1 sc (...) col0 sh gr % Polyline n 5700 1200 m 300 1200 l gs col0 s gr % Polyline n 300 2400 m 5700 2400 l gs col0 s gr % Polyline n 600 1200 m 600 2400 l gs col0 s gr % Polyline n 5400 1200 m 5400 2400 l gs col0 s gr % Polyline n 150 525 m 3525 525 l gs col-1 s gr % Polyline n 2175 675 m 4800 1125 l gs col-1 s gr % Polyline n 1575 675 m 3600 1125 l gs col-1 s gr % Polyline n 375 675 m 1200 1125 l gs col-1 s gr % Polyline n 2475 75 m 2475 675 l gs col-1 s gr % Polyline n 4200 2400 m 4200 1200 l gs col-1 s gr % Polyline n 3000 1200 m 3000 2400 l gs col-1 s gr % Polyline n 1800 2400 m 1800 1200 l gs col-1 s gr % Polyline n 150 225 m 3525 225 l gs col-1 s gr % Polyline n 3525 375 m 150 375 l gs col-1 s gr % Polyline n 1875 75 m 1875 675 l gs col-1 s gr /Times-Roman-iso ff 180.00 scf sf 3825 450 m gs 1 -1 sc (Page-info table) col-1 sh gr /Times-Roman-iso ff 180.00 scf sf 6000 1875 m gs 1 -1 sc (Heap) col-1 sh gr % Polyline n 675 75 m 675 675 l gs col-1 s gr % Polyline n 1275 75 m 1275 675 l gs col-1 s gr $F2psEnd rs @} @O Figure6.eps @{%!PS-Adobe-2.0 EPSF-2.0 %%Title: Figure6.eps %%Creator: fig2dev Version 3.2 Patchlevel 0-beta3 %%CreationDate: Thu Feb 18 13:26:05 1999 %%For: millst@@dishwasher.cs.rpi.edu (Toby-John Mills) %%Orientation: Portrait %%BoundingBox: 0 0 352 71 %%Pages: 0 %%BeginSetup %%EndSetup %%Magnification: 1.0000 %%EndComments /$F2psDict 200 dict def $F2psDict begin $F2psDict /mtrx matrix put /col-1 {0 setgray} bind def /col0 {0.000 0.000 0.000 srgb} bind def /col1 {0.000 0.000 1.000 srgb} bind def /col2 {0.000 1.000 0.000 srgb} bind def /col3 {0.000 1.000 1.000 srgb} bind def /col4 {1.000 0.000 0.000 srgb} bind def /col5 {1.000 0.000 1.000 srgb} bind def /col6 {1.000 1.000 0.000 srgb} bind def /col7 {1.000 1.000 1.000 srgb} bind def /col8 {0.000 0.000 0.560 srgb} bind def /col9 {0.000 0.000 0.690 srgb} bind def /col10 {0.000 0.000 0.820 srgb} bind def /col11 {0.530 0.810 1.000 srgb} bind def /col12 {0.000 0.560 0.000 srgb} bind def /col13 {0.000 0.690 0.000 srgb} bind def /col14 {0.000 0.820 0.000 srgb} bind def /col15 {0.000 0.560 0.560 srgb} bind def /col16 {0.000 0.690 0.690 srgb} bind def /col17 {0.000 0.820 0.820 srgb} bind def /col18 {0.560 0.000 0.000 srgb} bind def /col19 {0.690 0.000 0.000 srgb} bind def /col20 {0.820 0.000 0.000 srgb} bind def /col21 {0.560 0.000 0.560 srgb} bind def /col22 {0.690 0.000 0.690 srgb} bind def /col23 {0.820 0.000 0.820 srgb} bind def /col24 {0.500 0.190 0.000 srgb} bind def /col25 {0.630 0.250 0.000 srgb} bind def /col26 {0.750 0.380 0.000 srgb} bind def /col27 {1.000 0.500 0.500 srgb} bind def /col28 {1.000 0.630 0.630 srgb} bind def /col29 {1.000 0.750 0.750 srgb} bind def /col30 {1.000 0.880 0.880 srgb} bind def /col31 {1.000 0.840 0.000 srgb} bind def end save 1.0 71.0 translate 1 -1 scale /cp {closepath} bind def /ef {eofill} bind def /gr {grestore} bind def /gs {gsave} bind def /sa {save} bind def /rs {restore} bind def /l {lineto} bind def /m {moveto} bind def /rm {rmoveto} bind def /n {newpath} bind def /s {stroke} bind def /sh {show} bind def /slc {setlinecap} bind def /slj {setlinejoin} bind def /slw {setlinewidth} bind def /srgb {setrgbcolor} bind def /rot {rotate} bind def /sc {scale} bind def /sd {setdash} bind def /ff {findfont} bind def /sf {setfont} bind def /scf {scalefont} bind def /sw {stringwidth} bind def /tr {translate} bind def /tnt {dup dup currentrgbcolor 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add srgb} bind def /shd {dup dup currentrgbcolor 4 -2 roll mul 4 -2 roll mul 4 -2 roll mul srgb} bind def /$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def /$F2psEnd {$F2psEnteredState restore end} def %%EndProlog $F2psBegin 10 setmiterlimit n -1000 2179 m -1000 -1000 l 6838 -1000 l 6838 2179 l cp clip 0.06000 0.06000 sc % Polyline 7.500 slw n 75 225 m 4800 225 l 4800 525 l 75 525 l cp gs col0 s gr % Polyline n 600 525 m 600 225 l gs col0 s gr % Polyline n 4200 525 m 4200 225 l gs col0 s gr % Polyline n 1200 525 m 1200 225 l gs col0 s gr % Polyline n 1800 525 m 1800 225 l gs col0 s gr % Polyline n 2400 525 m 2400 225 l gs col0 s gr % Polyline n 3000 525 m 3000 225 l gs col0 s gr % Polyline n 3600 525 m 3600 225 l gs col0 s gr % Polyline n 4875 600 m 5025 750 l gs col0 s gr % Polyline n 4725 600 m 4575 750 l gs col0 s gr % Polyline n 75 150 m 225 75 l gs col0 s gr % Polyline n 75 150 m 75 75 l gs col0 s gr % Polyline n 75 150 m 150 150 l gs col0 s gr % Polyline n 4650 600 m 4725 600 l gs col0 s gr % Polyline n 4725 600 m 4725 675 l gs col0 s gr % Polyline n 4875 600 m 4950 600 l gs col0 s gr % Polyline n 4875 600 m 4875 675 l gs col0 s gr % Polyline n 75 600 m 75 975 l gs col0 s gr % Polyline n 75 600 m 0 675 l gs col0 s gr % Polyline n 75 600 m 150 675 l gs col0 s gr % Polyline n 1050 600 m 900 750 l gs col0 s gr % Polyline n 1125 525 m 1125 450 l gs col0 s gr % Polyline n 1125 225 m 1125 300 l gs col0 s gr % Polyline n 1050 600 m 1050 675 l gs col0 s gr % Polyline n 1050 600 m 975 600 l gs col0 s gr % Polyline n 1200 600 m 1350 750 l gs col0 s gr % Polyline n 1200 600 m 1200 675 l gs col0 s gr % Polyline n 1200 600 m 1275 600 l gs col0 s gr % Polyline n 75 975 m 150 1050 l gs col0 s gr /Times-Roman ff 180.00 scf sf 5100 900 m gs 1 -1 sc (Heap end) col0 sh gr /Times-Roman ff 180.00 scf sf 300 150 m gs 1 -1 sc (Real heap start) col0 sh gr /Times-Roman ff 180.00 scf sf 150 900 m gs 1 -1 sc (Heap start) col0 sh gr /Times-Roman ff 180.00 scf sf 3450 900 m gs 1 -1 sc (Real heap end) col0 sh gr /Times-Roman ff 180.00 scf sf 1425 900 m gs 1 -1 sc (PageInfo end) col0 sh gr /Times-Roman ff 180.00 scf sf 225 1125 m gs 1 -1 sc (PageInfo start) col0 sh gr $F2psEnd rs @} @O Figure7.eps @{%!PS-Adobe-2.0 EPSF-2.0 %%Title: Figure7.eps %%Creator: fig2dev Version 3.2 Patchlevel 0-beta3 %%CreationDate: Thu Feb 18 13:26:10 1999 %%For: millst@@dishwasher.cs.rpi.edu (Toby-John Mills) %%Orientation: Portrait %%BoundingBox: 0 0 353 41 %%Pages: 0 %%BeginSetup %%EndSetup %%Magnification: 1.0000 %%EndComments /$F2psDict 200 dict def $F2psDict begin $F2psDict /mtrx matrix put /col-1 {0 setgray} bind def /col0 {0.000 0.000 0.000 srgb} bind def /col1 {0.000 0.000 1.000 srgb} bind def /col2 {0.000 1.000 0.000 srgb} bind def /col3 {0.000 1.000 1.000 srgb} bind def /col4 {1.000 0.000 0.000 srgb} bind def /col5 {1.000 0.000 1.000 srgb} bind def /col6 {1.000 1.000 0.000 srgb} bind def /col7 {1.000 1.000 1.000 srgb} bind def /col8 {0.000 0.000 0.560 srgb} bind def /col9 {0.000 0.000 0.690 srgb} bind def /col10 {0.000 0.000 0.820 srgb} bind def /col11 {0.530 0.810 1.000 srgb} bind def /col12 {0.000 0.560 0.000 srgb} bind def /col13 {0.000 0.690 0.000 srgb} bind def /col14 {0.000 0.820 0.000 srgb} bind def /col15 {0.000 0.560 0.560 srgb} bind def /col16 {0.000 0.690 0.690 srgb} bind def /col17 {0.000 0.820 0.820 srgb} bind def /col18 {0.560 0.000 0.000 srgb} bind def /col19 {0.690 0.000 0.000 srgb} bind def /col20 {0.820 0.000 0.000 srgb} bind def /col21 {0.560 0.000 0.560 srgb} bind def /col22 {0.690 0.000 0.690 srgb} bind def /col23 {0.820 0.000 0.820 srgb} bind def /col24 {0.500 0.190 0.000 srgb} bind def /col25 {0.630 0.250 0.000 srgb} bind def /col26 {0.750 0.380 0.000 srgb} bind def /col27 {1.000 0.500 0.500 srgb} bind def /col28 {1.000 0.630 0.630 srgb} bind def /col29 {1.000 0.750 0.750 srgb} bind def /col30 {1.000 0.880 0.880 srgb} bind def /col31 {1.000 0.840 0.000 srgb} bind def end save -8.0 44.0 translate 1 -1 scale /cp {closepath} bind def /ef {eofill} bind def /gr {grestore} bind def /gs {gsave} bind def /sa {save} bind def /rs {restore} bind def /l {lineto} bind def /m {moveto} bind def /rm {rmoveto} bind def /n {newpath} bind def /s {stroke} bind def /sh {show} bind def /slc {setlinecap} bind def /slj {setlinejoin} bind def /slw {setlinewidth} bind def /srgb {setrgbcolor} bind def /rot {rotate} bind def /sc {scale} bind def /sd {setdash} bind def /ff {findfont} bind def /sf {setfont} bind def /scf {scalefont} bind def /sw {stringwidth} bind def /tr {translate} bind def /tnt {dup dup currentrgbcolor 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add srgb} bind def /shd {dup dup currentrgbcolor 4 -2 roll mul 4 -2 roll mul 4 -2 roll mul srgb} bind def /$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def /$F2psEnd {$F2psEnteredState restore end} def %%EndProlog $F2psBegin 10 setmiterlimit n -1000 1729 m -1000 -1000 l 7012 -1000 l 7012 1729 l cp clip 0.06000 0.06000 sc % Polyline 7.500 slw n 150 75 m 6000 75 l gs col0 s gr % Polyline n 375 450 m 375 75 l gs col0 s gr % Polyline n 2175 450 m 2175 75 l gs col0 s gr % Polyline n 2775 450 m 2775 75 l gs col0 s gr % Polyline n 3375 450 m 3375 75 l gs col0 s gr % Polyline n 5175 450 m 5175 75 l gs col0 s gr % Polyline n 5775 450 m 5775 75 l gs col0 s gr % Polyline n 975 450 m 975 75 l gs col0 s gr % Polyline n 1575 450 m 1575 75 l gs col0 s gr % Polyline n 3975 450 m 3975 75 l gs col0 s gr % Polyline n 4575 450 m 4575 75 l gs col0 s gr % Polyline n 150 450 m 6000 450 l gs col0 s gr /Times-Roman ff 180.00 scf sf 300 675 m gs 1 -1 sc (currentSpace) col0 sh gr /Times-Roman ff 180.00 scf sf 2700 675 m gs 1 -1 sc (nextSpace) col0 sh gr /Times-Roman ff 180.00 scf sf 4500 675 m gs 1 -1 sc (allocSpace) col0 sh gr $F2psEnd rs @} @O Figure8.eps @{%!PS-Adobe-2.0 EPSF-2.0 %%Title: Figure8.eps %%Creator: fig2dev Version 3.2 Patchlevel 0-beta3 %%CreationDate: Thu Feb 18 13:26:19 1999 %%For: millst@@dishwasher.cs.rpi.edu (Toby-John Mills) %%Orientation: Portrait %%BoundingBox: 0 0 353 41 %%Pages: 0 %%BeginSetup %%EndSetup %%Magnification: 1.0000 %%EndComments /$F2psDict 200 dict def $F2psDict begin $F2psDict /mtrx matrix put /col-1 {0 setgray} bind def /col0 {0.000 0.000 0.000 srgb} bind def /col1 {0.000 0.000 1.000 srgb} bind def /col2 {0.000 1.000 0.000 srgb} bind def /col3 {0.000 1.000 1.000 srgb} bind def /col4 {1.000 0.000 0.000 srgb} bind def /col5 {1.000 0.000 1.000 srgb} bind def /col6 {1.000 1.000 0.000 srgb} bind def /col7 {1.000 1.000 1.000 srgb} bind def /col8 {0.000 0.000 0.560 srgb} bind def /col9 {0.000 0.000 0.690 srgb} bind def /col10 {0.000 0.000 0.820 srgb} bind def /col11 {0.530 0.810 1.000 srgb} bind def /col12 {0.000 0.560 0.000 srgb} bind def /col13 {0.000 0.690 0.000 srgb} bind def /col14 {0.000 0.820 0.000 srgb} bind def /col15 {0.000 0.560 0.560 srgb} bind def /col16 {0.000 0.690 0.690 srgb} bind def /col17 {0.000 0.820 0.820 srgb} bind def /col18 {0.560 0.000 0.000 srgb} bind def /col19 {0.690 0.000 0.000 srgb} bind def /col20 {0.820 0.000 0.000 srgb} bind def /col21 {0.560 0.000 0.560 srgb} bind def /col22 {0.690 0.000 0.690 srgb} bind def /col23 {0.820 0.000 0.820 srgb} bind def /col24 {0.500 0.190 0.000 srgb} bind def /col25 {0.630 0.250 0.000 srgb} bind def /col26 {0.750 0.380 0.000 srgb} bind def /col27 {1.000 0.500 0.500 srgb} bind def /col28 {1.000 0.630 0.630 srgb} bind def /col29 {1.000 0.750 0.750 srgb} bind def /col30 {1.000 0.880 0.880 srgb} bind def /col31 {1.000 0.840 0.000 srgb} bind def end save -8.0 44.0 translate 1 -1 scale /cp {closepath} bind def /ef {eofill} bind def /gr {grestore} bind def /gs {gsave} bind def /sa {save} bind def /rs {restore} bind def /l {lineto} bind def /m {moveto} bind def /rm {rmoveto} bind def /n {newpath} bind def /s {stroke} bind def /sh {show} bind def /slc {setlinecap} bind def /slj {setlinejoin} bind def /slw {setlinewidth} bind def /srgb {setrgbcolor} bind def /rot {rotate} bind def /sc {scale} bind def /sd {setdash} bind def /ff {findfont} bind def /sf {setfont} bind def /scf {scalefont} bind def /sw {stringwidth} bind def /tr {translate} bind def /tnt {dup dup currentrgbcolor 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add srgb} bind def /shd {dup dup currentrgbcolor 4 -2 roll mul 4 -2 roll mul 4 -2 roll mul srgb} bind def /$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def /$F2psEnd {$F2psEnteredState restore end} def %%EndProlog $F2psBegin 10 setmiterlimit n -1000 1729 m -1000 -1000 l 7012 -1000 l 7012 1729 l cp clip 0.06000 0.06000 sc % Polyline 7.500 slw n 150 75 m 6000 75 l gs col0 s gr % Polyline n 375 450 m 375 75 l gs col0 s gr % Polyline n 2175 450 m 2175 75 l gs col0 s gr % Polyline n 2775 450 m 2775 75 l gs col0 s gr % Polyline n 3375 450 m 3375 75 l gs col0 s gr % Polyline n 5175 450 m 5175 75 l gs col0 s gr % Polyline n 5775 450 m 5775 75 l gs col0 s gr % Polyline n 975 450 m 975 75 l gs col0 s gr % Polyline n 1575 450 m 1575 75 l gs col0 s gr % Polyline n 3975 450 m 3975 75 l gs col0 s gr % Polyline n 4575 450 m 4575 75 l gs col0 s gr % Polyline n 150 450 m 6000 450 l gs col0 s gr /Times-Roman ff 180.00 scf sf 300 675 m gs 1 -1 sc (currentSpace) col0 sh gr /Times-Roman ff 180.00 scf sf 2700 675 m gs 1 -1 sc (nextSpace) col0 sh gr /Times-Roman ff 150.00 scf sf 4725 300 m gs 1 -1 sc (black) col0 sh gr /Times-Roman ff 150.00 scf sf 4125 300 m gs 1 -1 sc (grey) col0 sh gr /Times-Roman ff 150.00 scf sf 3450 225 m gs 1 -1 sc (wired) col0 sh gr /Times-Roman ff 150.00 scf sf 3450 375 m gs 1 -1 sc (InQueue) col0 sh gr /Times-Roman ff 150.00 scf sf 2850 225 m gs 1 -1 sc (scanned) col0 sh gr /Times-Roman ff 150.00 scf sf 2850 375 m gs 1 -1 sc (Wired) col0 sh gr /Times-Roman ff 180.00 scf sf 4500 675 m gs 1 -1 sc (allocSpace) col0 sh gr $F2psEnd rs @} @O Figure9.eps @{%!PS-Adobe-2.0 EPSF-2.0 %%Title: Figure9.eps %%Creator: fig2dev Version 3.2 Patchlevel 0-beta3 %%CreationDate: Thu Feb 18 13:26:25 1999 %%For: millst@@dishwasher.cs.rpi.edu (Toby-John Mills) %%Orientation: Portrait %%BoundingBox: 0 0 183 89 %%Pages: 0 %%BeginSetup %%EndSetup %%Magnification: 1.0000 %%EndComments /$F2psDict 200 dict def $F2psDict begin $F2psDict /mtrx matrix put /col-1 {0 setgray} bind def /col0 {0.000 0.000 0.000 srgb} bind def /col1 {0.000 0.000 1.000 srgb} bind def /col2 {0.000 1.000 0.000 srgb} bind def /col3 {0.000 1.000 1.000 srgb} bind def /col4 {1.000 0.000 0.000 srgb} bind def /col5 {1.000 0.000 1.000 srgb} bind def /col6 {1.000 1.000 0.000 srgb} bind def /col7 {1.000 1.000 1.000 srgb} bind def /col8 {0.000 0.000 0.560 srgb} bind def /col9 {0.000 0.000 0.690 srgb} bind def /col10 {0.000 0.000 0.820 srgb} bind def /col11 {0.530 0.810 1.000 srgb} bind def /col12 {0.000 0.560 0.000 srgb} bind def /col13 {0.000 0.690 0.000 srgb} bind def /col14 {0.000 0.820 0.000 srgb} bind def /col15 {0.000 0.560 0.560 srgb} bind def /col16 {0.000 0.690 0.690 srgb} bind def /col17 {0.000 0.820 0.820 srgb} bind def /col18 {0.560 0.000 0.000 srgb} bind def /col19 {0.690 0.000 0.000 srgb} bind def /col20 {0.820 0.000 0.000 srgb} bind def /col21 {0.560 0.000 0.560 srgb} bind def /col22 {0.690 0.000 0.690 srgb} bind def /col23 {0.820 0.000 0.820 srgb} bind def /col24 {0.500 0.190 0.000 srgb} bind def /col25 {0.630 0.250 0.000 srgb} bind def /col26 {0.750 0.380 0.000 srgb} bind def /col27 {1.000 0.500 0.500 srgb} bind def /col28 {1.000 0.630 0.630 srgb} bind def /col29 {1.000 0.750 0.750 srgb} bind def /col30 {1.000 0.880 0.880 srgb} bind def /col31 {1.000 0.840 0.000 srgb} bind def end save -4.0 89.0 translate 1 -1 scale /cp {closepath} bind def /ef {eofill} bind def /gr {grestore} bind def /gs {gsave} bind def /sa {save} bind def /rs {restore} bind def /l {lineto} bind def /m {moveto} bind def /rm {rmoveto} bind def /n {newpath} bind def /s {stroke} bind def /sh {show} bind def /slc {setlinecap} bind def /slj {setlinejoin} bind def /slw {setlinewidth} bind def /srgb {setrgbcolor} bind def /rot {rotate} bind def /sc {scale} bind def /sd {setdash} bind def /ff {findfont} bind def /sf {setfont} bind def /scf {scalefont} bind def /sw {stringwidth} bind def /tr {translate} bind def /tnt {dup dup currentrgbcolor 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add srgb} bind def /shd {dup dup currentrgbcolor 4 -2 roll mul 4 -2 roll mul 4 -2 roll mul srgb} bind def /$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def /$F2psEnd {$F2psEnteredState restore end} def %%EndProlog $F2psBegin 10 setmiterlimit n -1000 2479 m -1000 -1000 l 4107 -1000 l 4107 2479 l cp clip 0.06000 0.06000 sc % Polyline 7.500 slw n 825 225 m 1950 225 l 1950 1425 l 825 1425 l cp gs col0 s gr % Polyline n 825 825 m 1950 825 l gs col0 s gr % Polyline n 375 825 m 750 825 l gs col0 s gr % Polyline n 750 825 m 675 900 l gs col0 s gr % Polyline n 750 825 m 675 750 l gs col0 s gr % Polyline n 1650 1425 m 1650 1275 l gs col0 s gr % Polyline n 1650 1275 m 1950 1275 l gs col0 s gr % Polyline n 825 1200 m 1200 825 l gs col0 s gr % Polyline n 825 1125 m 1125 825 l gs col0 s gr % Polyline n 825 1050 m 1050 825 l gs col0 s gr % Polyline n 825 900 m 900 825 l gs col0 s gr % Polyline n 825 975 m 975 825 l gs col0 s gr % Polyline n 825 1275 m 1275 825 l gs col0 s gr % Polyline n 825 1350 m 1350 825 l gs col0 s gr % Polyline n 825 1425 m 1425 825 l gs col0 s gr % Polyline n 975 1425 m 1575 825 l gs col0 s gr % Polyline n 900 1425 m 1500 825 l gs col0 s gr % Polyline n 1125 1425 m 1725 825 l gs col0 s gr % Polyline n 1050 1425 m 1650 825 l gs col0 s gr % Polyline n 1200 1425 m 1800 825 l gs col0 s gr % Polyline n 1350 1425 m 1950 825 l gs col0 s gr % Polyline n 1275 1425 m 1875 825 l gs col0 s gr % Polyline n 1500 1425 m 1950 975 l gs col0 s gr % Polyline n 1425 1425 m 1950 900 l gs col0 s gr % Polyline n 1800 1275 m 1950 1125 l gs col0 s gr % Polyline n 1725 1275 m 1950 1050 l gs col0 s gr % Polyline n 1875 1275 m 1950 1275 l gs col0 s gr % Polyline n 1575 1425 m 1650 1350 l gs col0 s gr % Polyline n 1875 1275 m 1950 1200 l gs col0 s gr % Polyline n 2025 1350 m 2100 1275 l gs col0 s gr % Polyline n 2025 1350 m 2100 1425 l gs col0 s gr % Polyline n 2025 1350 m 2325 1350 l gs col0 s gr /Times-Roman ff 180.00 scf sf 75 150 m gs 1 -1 sc (pageStart) col0 sh gr /Times-Roman ff 180.00 scf sf 75 900 m gs 1 -1 sc (top) col0 sh gr /Times-Roman ff 180.00 scf sf 2400 1425 m gs 1 -1 sc (classTop) col0 sh gr $F2psEnd rs @} @O Figure10.eps @{%!PS-Adobe-2.0 EPSF-2.0 %%Title: Figure10.eps %%Creator: fig2dev Version 3.2 Patchlevel 0-beta3 %%CreationDate: Thu Feb 18 13:26:30 1999 %%For: millst@@dishwasher.cs.rpi.edu (Toby-John Mills) %%Orientation: Portrait %%BoundingBox: 0 0 295 25 %%Pages: 0 %%BeginSetup %%EndSetup %%Magnification: 1.0000 %%EndComments /$F2psDict 200 dict def $F2psDict begin $F2psDict /mtrx matrix put /col-1 {0 setgray} bind def /col0 {0.000 0.000 0.000 srgb} bind def /col1 {0.000 0.000 1.000 srgb} bind def /col2 {0.000 1.000 0.000 srgb} bind def /col3 {0.000 1.000 1.000 srgb} bind def /col4 {1.000 0.000 0.000 srgb} bind def /col5 {1.000 0.000 1.000 srgb} bind def /col6 {1.000 1.000 0.000 srgb} bind def /col7 {1.000 1.000 1.000 srgb} bind def /col8 {0.000 0.000 0.560 srgb} bind def /col9 {0.000 0.000 0.690 srgb} bind def /col10 {0.000 0.000 0.820 srgb} bind def /col11 {0.530 0.810 1.000 srgb} bind def /col12 {0.000 0.560 0.000 srgb} bind def /col13 {0.000 0.690 0.000 srgb} bind def /col14 {0.000 0.820 0.000 srgb} bind def /col15 {0.000 0.560 0.560 srgb} bind def /col16 {0.000 0.690 0.690 srgb} bind def /col17 {0.000 0.820 0.820 srgb} bind def /col18 {0.560 0.000 0.000 srgb} bind def /col19 {0.690 0.000 0.000 srgb} bind def /col20 {0.820 0.000 0.000 srgb} bind def /col21 {0.560 0.000 0.560 srgb} bind def /col22 {0.690 0.000 0.690 srgb} bind def /col23 {0.820 0.000 0.820 srgb} bind def /col24 {0.500 0.190 0.000 srgb} bind def /col25 {0.630 0.250 0.000 srgb} bind def /col26 {0.750 0.380 0.000 srgb} bind def /col27 {1.000 0.500 0.500 srgb} bind def /col28 {1.000 0.630 0.630 srgb} bind def /col29 {1.000 0.750 0.750 srgb} bind def /col30 {1.000 0.880 0.880 srgb} bind def /col31 {1.000 0.840 0.000 srgb} bind def end save -3.0 28.0 translate 1 -1 scale /cp {closepath} bind def /ef {eofill} bind def /gr {grestore} bind def /gs {gsave} bind def /sa {save} bind def /rs {restore} bind def /l {lineto} bind def /m {moveto} bind def /rm {rmoveto} bind def /n {newpath} bind def /s {stroke} bind def /sh {show} bind def /slc {setlinecap} bind def /slj {setlinejoin} bind def /slw {setlinewidth} bind def /srgb {setrgbcolor} bind def /rot {rotate} bind def /sc {scale} bind def /sd {setdash} bind def /ff {findfont} bind def /sf {setfont} bind def /scf {scalefont} bind def /sw {stringwidth} bind def /tr {translate} bind def /tnt {dup dup currentrgbcolor 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add srgb} bind def /shd {dup dup currentrgbcolor 4 -2 roll mul 4 -2 roll mul 4 -2 roll mul srgb} bind def /$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def /$F2psEnd {$F2psEnteredState restore end} def %%EndProlog $F2psBegin 10 setmiterlimit n -1000 1462 m -1000 -1000 l 5962 -1000 l 5962 1462 l cp clip 0.06000 0.06000 sc % Polyline 7.500 slw n 75 75 m 4950 75 l gs col0 s gr % Polyline n 375 450 m 375 75 l gs col0 s gr % Polyline n 2175 450 m 2175 75 l gs col0 s gr % Polyline n 2775 450 m 2775 75 l gs col0 s gr % Polyline n 3375 450 m 3375 75 l gs col0 s gr % Polyline n 975 450 m 975 75 l gs col0 s gr % Polyline n 1575 450 m 1575 75 l gs col0 s gr % Polyline n 3975 450 m 3975 75 l gs col0 s gr % Polyline n 4575 450 m 4575 75 l gs col0 s gr % Polyline n 75 450 m 4950 450 l gs col0 s gr % Polyline n 75 450 m 75 75 l gs col0 s gr % Polyline n 675 450 m 675 75 l gs col0 s gr % Polyline n 1275 450 m 1275 75 l gs col0 s gr % Polyline n 1875 450 m 1875 75 l gs col0 s gr % Polyline n 2475 450 m 2475 75 l gs col0 s gr % Polyline n 3675 450 m 3675 75 l gs col0 s gr % Polyline n 4275 450 m 4275 75 l gs col0 s gr % Polyline n 3075 450 m 3075 75 l gs col0 s gr % Polyline n 4950 450 m 4950 75 l gs col0 s gr /Times-Roman ff 180.00 scf sf 450 300 m gs 1 -1 sc (0) col0 sh gr /Times-Roman ff 180.00 scf sf 750 300 m gs 1 -1 sc (0) col0 sh gr /Times-Roman ff 180.00 scf sf 1050 300 m gs 1 -1 sc (0) col0 sh gr /Times-Roman ff 180.00 scf sf 1350 300 m gs 1 -1 sc (0) col0 sh gr /Times-Roman ff 180.00 scf sf 1650 300 m gs 1 -1 sc (1) col0 sh gr /Times-Roman ff 180.00 scf sf 1950 300 m gs 1 -1 sc (1) col0 sh gr /Times-Roman ff 180.00 scf sf 2250 300 m gs 1 -1 sc (1) col0 sh gr /Times-Roman ff 180.00 scf sf 2550 300 m gs 1 -1 sc (1) col0 sh gr /Times-Roman ff 180.00 scf sf 2850 300 m gs 1 -1 sc (1) col0 sh gr /Times-Roman ff 180.00 scf sf 3150 300 m gs 1 -1 sc (2) col0 sh gr /Times-Roman ff 180.00 scf sf 3450 300 m gs 1 -1 sc (2) col0 sh gr /Times-Roman ff 180.00 scf sf 4050 300 m gs 1 -1 sc (2) col0 sh gr /Times-Roman ff 180.00 scf sf 4350 300 m gs 1 -1 sc (2) col0 sh gr /Times-Roman ff 180.00 scf sf 3750 300 m gs 1 -1 sc (2) col0 sh gr /Times-Roman ff 180.00 scf sf 150 300 m gs 1 -1 sc (0) col0 sh gr /Times-Roman ff 180.00 scf sf 4650 300 m gs 1 -1 sc (...) col0 sh gr $F2psEnd rs @} @O Figure11.eps @{%!PS-Adobe-2.0 EPSF-2.0 %%Title: Figure11.eps %%Creator: fig2dev Version 3.2 Patchlevel 0-beta3 %%CreationDate: Thu Feb 18 13:26:40 1999 %%For: millst@@dishwasher.cs.rpi.edu (Toby-John Mills) %%Orientation: Portrait %%BoundingBox: 0 0 295 25 %%Pages: 0 %%BeginSetup %%EndSetup %%Magnification: 1.0000 %%EndComments /$F2psDict 200 dict def $F2psDict begin $F2psDict /mtrx matrix put /col-1 {0 setgray} bind def /col0 {0.000 0.000 0.000 srgb} bind def /col1 {0.000 0.000 1.000 srgb} bind def /col2 {0.000 1.000 0.000 srgb} bind def /col3 {0.000 1.000 1.000 srgb} bind def /col4 {1.000 0.000 0.000 srgb} bind def /col5 {1.000 0.000 1.000 srgb} bind def /col6 {1.000 1.000 0.000 srgb} bind def /col7 {1.000 1.000 1.000 srgb} bind def /col8 {0.000 0.000 0.560 srgb} bind def /col9 {0.000 0.000 0.690 srgb} bind def /col10 {0.000 0.000 0.820 srgb} bind def /col11 {0.530 0.810 1.000 srgb} bind def /col12 {0.000 0.560 0.000 srgb} bind def /col13 {0.000 0.690 0.000 srgb} bind def /col14 {0.000 0.820 0.000 srgb} bind def /col15 {0.000 0.560 0.560 srgb} bind def /col16 {0.000 0.690 0.690 srgb} bind def /col17 {0.000 0.820 0.820 srgb} bind def /col18 {0.560 0.000 0.000 srgb} bind def /col19 {0.690 0.000 0.000 srgb} bind def /col20 {0.820 0.000 0.000 srgb} bind def /col21 {0.560 0.000 0.560 srgb} bind def /col22 {0.690 0.000 0.690 srgb} bind def /col23 {0.820 0.000 0.820 srgb} bind def /col24 {0.500 0.190 0.000 srgb} bind def /col25 {0.630 0.250 0.000 srgb} bind def /col26 {0.750 0.380 0.000 srgb} bind def /col27 {1.000 0.500 0.500 srgb} bind def /col28 {1.000 0.630 0.630 srgb} bind def /col29 {1.000 0.750 0.750 srgb} bind def /col30 {1.000 0.880 0.880 srgb} bind def /col31 {1.000 0.840 0.000 srgb} bind def end save -3.0 28.0 translate 1 -1 scale /cp {closepath} bind def /ef {eofill} bind def /gr {grestore} bind def /gs {gsave} bind def /sa {save} bind def /rs {restore} bind def /l {lineto} bind def /m {moveto} bind def /rm {rmoveto} bind def /n {newpath} bind def /s {stroke} bind def /sh {show} bind def /slc {setlinecap} bind def /slj {setlinejoin} bind def /slw {setlinewidth} bind def /srgb {setrgbcolor} bind def /rot {rotate} bind def /sc {scale} bind def /sd {setdash} bind def /ff {findfont} bind def /sf {setfont} bind def /scf {scalefont} bind def /sw {stringwidth} bind def /tr {translate} bind def /tnt {dup dup currentrgbcolor 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add srgb} bind def /shd {dup dup currentrgbcolor 4 -2 roll mul 4 -2 roll mul 4 -2 roll mul srgb} bind def /$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def /$F2psEnd {$F2psEnteredState restore end} def %%EndProlog $F2psBegin 10 setmiterlimit n -1000 1462 m -1000 -1000 l 5962 -1000 l 5962 1462 l cp clip 0.06000 0.06000 sc % Polyline 7.500 slw n 75 75 m 4950 75 l gs col0 s gr % Polyline n 375 450 m 375 75 l gs col0 s gr % Polyline n 2175 450 m 2175 75 l gs col0 s gr % Polyline n 2775 450 m 2775 75 l gs col0 s gr % Polyline n 3375 450 m 3375 75 l gs col0 s gr % Polyline n 975 450 m 975 75 l gs col0 s gr % Polyline n 1575 450 m 1575 75 l gs col0 s gr % Polyline n 3975 450 m 3975 75 l gs col0 s gr % Polyline n 4575 450 m 4575 75 l gs col0 s gr % Polyline n 75 450 m 4950 450 l gs col0 s gr % Polyline n 75 450 m 75 75 l gs col0 s gr % Polyline n 675 450 m 675 75 l gs col0 s gr % Polyline n 1275 450 m 1275 75 l gs col0 s gr % Polyline n 1875 450 m 1875 75 l gs col0 s gr % Polyline n 2475 450 m 2475 75 l gs col0 s gr % Polyline n 3675 450 m 3675 75 l gs col0 s gr % Polyline n 4275 450 m 4275 75 l gs col0 s gr % Polyline n 3075 450 m 3075 75 l gs col0 s gr % Polyline n 4950 450 m 4950 75 l gs col0 s gr /Times-Roman ff 180.00 scf sf 150 300 m gs 1 -1 sc (0) col0 sh gr /Times-Roman ff 180.00 scf sf 4650 300 m gs 1 -1 sc (...) col0 sh gr /Times-Roman ff 180.00 scf sf 1950 300 m gs 1 -1 sc (1) col0 sh gr /Times-Roman ff 180.00 scf sf 1650 300 m gs 1 -1 sc (0) col0 sh gr /Times-Roman ff 180.00 scf sf 450 300 m gs 1 -1 sc (1) col0 sh gr /Times-Roman ff 180.00 scf sf 3450 300 m gs 1 -1 sc (1) col0 sh gr /Times-Roman ff 180.00 scf sf 2250 300 m gs 1 -1 sc (2) col0 sh gr /Times-Roman ff 180.00 scf sf 3150 300 m gs 1 -1 sc (0) col0 sh gr /Times-Roman ff 180.00 scf sf 3750 300 m gs 1 -1 sc (2) col0 sh gr /Times-Roman ff 180.00 scf sf 750 300 m gs 1 -1 sc (2) col0 sh gr /Times-Roman ff 180.00 scf sf 1050 300 m gs 1 -1 sc (3) col0 sh gr /Times-Roman ff 180.00 scf sf 2550 300 m gs 1 -1 sc (3) col0 sh gr /Times-Roman ff 180.00 scf sf 4050 300 m gs 1 -1 sc (3) col0 sh gr /Times-Roman ff 180.00 scf sf 4350 300 m gs 1 -1 sc (4) col0 sh gr /Times-Roman ff 180.00 scf sf 1350 300 m gs 1 -1 sc (4) col0 sh gr /Times-Roman ff 180.00 scf sf 2850 300 m gs 1 -1 sc (4) col0 sh gr $F2psEnd rs @} @O Figure12.eps @{%!PS-Adobe-2.0 EPSF-2.0 %%Title: Figure12.eps %%Creator: fig2dev Version 3.2 Patchlevel 0-beta3 %%CreationDate: Thu Feb 18 13:26:46 1999 %%For: millst@@dishwasher.cs.rpi.edu (Toby-John Mills) %%Orientation: Portrait %%BoundingBox: 0 0 196 47 %%Pages: 0 %%BeginSetup %%EndSetup %%Magnification: 1.0000 %%EndComments /$F2psDict 200 dict def $F2psDict begin $F2psDict /mtrx matrix put /col-1 {0 setgray} bind def /col0 {0.000 0.000 0.000 srgb} bind def /col1 {0.000 0.000 1.000 srgb} bind def /col2 {0.000 1.000 0.000 srgb} bind def /col3 {0.000 1.000 1.000 srgb} bind def /col4 {1.000 0.000 0.000 srgb} bind def /col5 {1.000 0.000 1.000 srgb} bind def /col6 {1.000 1.000 0.000 srgb} bind def /col7 {1.000 1.000 1.000 srgb} bind def /col8 {0.000 0.000 0.560 srgb} bind def /col9 {0.000 0.000 0.690 srgb} bind def /col10 {0.000 0.000 0.820 srgb} bind def /col11 {0.530 0.810 1.000 srgb} bind def /col12 {0.000 0.560 0.000 srgb} bind def /col13 {0.000 0.690 0.000 srgb} bind def /col14 {0.000 0.820 0.000 srgb} bind def /col15 {0.000 0.560 0.560 srgb} bind def /col16 {0.000 0.690 0.690 srgb} bind def /col17 {0.000 0.820 0.820 srgb} bind def /col18 {0.560 0.000 0.000 srgb} bind def /col19 {0.690 0.000 0.000 srgb} bind def /col20 {0.820 0.000 0.000 srgb} bind def /col21 {0.560 0.000 0.560 srgb} bind def /col22 {0.690 0.000 0.690 srgb} bind def /col23 {0.820 0.000 0.820 srgb} bind def /col24 {0.500 0.190 0.000 srgb} bind def /col25 {0.630 0.250 0.000 srgb} bind def /col26 {0.750 0.380 0.000 srgb} bind def /col27 {1.000 0.500 0.500 srgb} bind def /col28 {1.000 0.630 0.630 srgb} bind def /col29 {1.000 0.750 0.750 srgb} bind def /col30 {1.000 0.880 0.880 srgb} bind def /col31 {1.000 0.840 0.000 srgb} bind def end save -3.0 50.0 translate 1 -1 scale /cp {closepath} bind def /ef {eofill} bind def /gr {grestore} bind def /gs {gsave} bind def /sa {save} bind def /rs {restore} bind def /l {lineto} bind def /m {moveto} bind def /rm {rmoveto} bind def /n {newpath} bind def /s {stroke} bind def /sh {show} bind def /slc {setlinecap} bind def /slj {setlinejoin} bind def /slw {setlinewidth} bind def /srgb {setrgbcolor} bind def /rot {rotate} bind def /sc {scale} bind def /sd {setdash} bind def /ff {findfont} bind def /sf {setfont} bind def /scf {scalefont} bind def /sw {stringwidth} bind def /tr {translate} bind def /tnt {dup dup currentrgbcolor 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add srgb} bind def /shd {dup dup currentrgbcolor 4 -2 roll mul 4 -2 roll mul 4 -2 roll mul srgb} bind def /$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def /$F2psEnd {$F2psEnteredState restore end} def %%EndProlog $F2psBegin 10 setmiterlimit n -1000 1825 m -1000 -1000 l 4312 -1000 l 4312 1825 l cp clip 0.06000 0.06000 sc % Polyline 7.500 slw n 975 375 m 975 75 l gs col0 s gr % Polyline n 75 75 m 3300 75 l 3300 375 l 75 375 l cp gs col0 s gr % Polyline n 975 450 m 1125 600 l 1200 600 l gs col0 s gr % Polyline n 975 450 m 975 525 l gs col0 s gr % Polyline n 975 450 m 1050 450 l gs col0 s gr % Polyline n 1125 750 m 525 225 l gs col0 s gr % Polyline n 1125 750 m 1200 750 l gs col0 s gr % Polyline n 525 225 m 525 300 l gs col0 s gr % Polyline n 525 225 m 600 225 l gs col0 s gr /Times-Roman ff 180.00 scf sf 1800 300 m gs 1 -1 sc (object) col0 sh gr /Times-Roman ff 180.00 scf sf 1275 675 m gs 1 -1 sc (object start) col0 sh gr /Times-Roman ff 180.00 scf sf 1275 825 m gs 1 -1 sc (traverse function) col0 sh gr $F2psEnd rs @} @O Figure13.eps @{%!PS-Adobe-2.0 EPSF-2.0 %%Title: Figure13.eps %%Creator: fig2dev Version 3.2 Patchlevel 0-beta3 %%CreationDate: Tue Mar 2 10:47:18 1999 %%For: millst@@eggbeater.cs.rpi.edu (Toby-John Mills) %%Orientation: Portrait %%BoundingBox: 0 0 147 149 %%Pages: 0 %%BeginSetup %%EndSetup %%Magnification: 1.0000 %%EndComments /$F2psDict 200 dict def $F2psDict begin $F2psDict /mtrx matrix put /col-1 {0 setgray} bind def /col0 {0.000 0.000 0.000 srgb} bind def /col1 {0.000 0.000 1.000 srgb} bind def /col2 {0.000 1.000 0.000 srgb} bind def /col3 {0.000 1.000 1.000 srgb} bind def /col4 {1.000 0.000 0.000 srgb} bind def /col5 {1.000 0.000 1.000 srgb} bind def /col6 {1.000 1.000 0.000 srgb} bind def /col7 {1.000 1.000 1.000 srgb} bind def /col8 {0.000 0.000 0.560 srgb} bind def /col9 {0.000 0.000 0.690 srgb} bind def /col10 {0.000 0.000 0.820 srgb} bind def /col11 {0.530 0.810 1.000 srgb} bind def /col12 {0.000 0.560 0.000 srgb} bind def /col13 {0.000 0.690 0.000 srgb} bind def /col14 {0.000 0.820 0.000 srgb} bind def /col15 {0.000 0.560 0.560 srgb} bind def /col16 {0.000 0.690 0.690 srgb} bind def /col17 {0.000 0.820 0.820 srgb} bind def /col18 {0.560 0.000 0.000 srgb} bind def /col19 {0.690 0.000 0.000 srgb} bind def /col20 {0.820 0.000 0.000 srgb} bind def /col21 {0.560 0.000 0.560 srgb} bind def /col22 {0.690 0.000 0.690 srgb} bind def /col23 {0.820 0.000 0.820 srgb} bind def /col24 {0.500 0.190 0.000 srgb} bind def /col25 {0.630 0.250 0.000 srgb} bind def /col26 {0.750 0.380 0.000 srgb} bind def /col27 {1.000 0.500 0.500 srgb} bind def /col28 {1.000 0.630 0.630 srgb} bind def /col29 {1.000 0.750 0.750 srgb} bind def /col30 {1.000 0.880 0.880 srgb} bind def /col31 {1.000 0.840 0.000 srgb} bind def end save -3.0 152.0 translate 1 -1 scale /cp {closepath} bind def /ef {eofill} bind def /gr {grestore} bind def /gs {gsave} bind def /sa {save} bind def /rs {restore} bind def /l {lineto} bind def /m {moveto} bind def /rm {rmoveto} bind def /n {newpath} bind def /s {stroke} bind def /sh {show} bind def /slc {setlinecap} bind def /slj {setlinejoin} bind def /slw {setlinewidth} bind def /srgb {setrgbcolor} bind def /rot {rotate} bind def /sc {scale} bind def /sd {setdash} bind def /ff {findfont} bind def /sf {setfont} bind def /scf {scalefont} bind def /sw {stringwidth} bind def /tr {translate} bind def /tnt {dup dup currentrgbcolor 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add srgb} bind def /shd {dup dup currentrgbcolor 4 -2 roll mul 4 -2 roll mul 4 -2 roll mul srgb} bind def /$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def /$F2psEnd {$F2psEnteredState restore end} def %%EndProlog $F2psBegin 10 setmiterlimit n -1000 3520 m -1000 -1000 l 3487 -1000 l 3487 3520 l cp clip 0.06000 0.06000 sc % Polyline 7.500 slw n 75 75 m 2475 75 l 2475 375 l 75 375 l cp gs col0 s gr % Polyline n 675 375 m 675 75 l gs col0 s gr % Polyline n 75 900 m 2475 900 l 2475 1200 l 75 1200 l cp gs col0 s gr % Polyline n 975 900 m 975 1200 l gs col0 s gr % Polyline n 1575 900 m 1575 1200 l gs col0 s gr % Polyline n 75 1800 m 2475 1800 l 2475 2100 l 75 2100 l cp gs col0 s gr % Polyline n 1800 2100 m 1800 1800 l gs col0 s gr /Times-Roman ff 180.00 scf sf 1200 600 m gs 1 -1 sc (old heap) col0 sh gr /Times-Roman ff 180.00 scf sf 225 600 m gs 1 -1 sc (new) col0 sh gr /Times-Roman ff 180.00 scf sf 75 750 m gs 1 -1 sc (segment) col0 sh gr /Times-Roman ff 180.00 scf sf 150 1425 m gs 1 -1 sc (old heap) col0 sh gr /Times-Roman ff 180.00 scf sf 1800 1425 m gs 1 -1 sc (old heap) col0 sh gr /Times-Roman ff 180.00 scf sf 1125 1425 m gs 1 -1 sc (new) col0 sh gr /Times-Roman ff 180.00 scf sf 975 1650 m gs 1 -1 sc (segment) col0 sh gr /Times-Roman ff 180.00 scf sf 1800 2475 m gs 1 -1 sc (segment) col0 sh gr /Times-Roman ff 180.00 scf sf 1950 2325 m gs 1 -1 sc (new) col0 sh gr /Times-Roman ff 180.00 scf sf 525 2325 m gs 1 -1 sc (old heap) col0 sh gr $F2psEnd rs @} @O Figure13a.eps @{%!PS-Adobe-2.0 EPSF-2.0 %%Title: Figure13.eps %%Creator: fig2dev Version 3.2 Patchlevel 0-beta3 %%CreationDate: Thu Feb 18 13:26:52 1999 %%For: millst@@dishwasher.cs.rpi.edu (Toby-John Mills) %%Orientation: Portrait %%BoundingBox: 0 0 327 90 %%Pages: 0 %%BeginSetup %%EndSetup %%Magnification: 1.0000 %%EndComments /$F2psDict 200 dict def $F2psDict begin $F2psDict /mtrx matrix put /col-1 {0 setgray} bind def /col0 {0.000 0.000 0.000 srgb} bind def /col1 {0.000 0.000 1.000 srgb} bind def /col2 {0.000 1.000 0.000 srgb} bind def /col3 {0.000 1.000 1.000 srgb} bind def /col4 {1.000 0.000 0.000 srgb} bind def /col5 {1.000 0.000 1.000 srgb} bind def /col6 {1.000 1.000 0.000 srgb} bind def /col7 {1.000 1.000 1.000 srgb} bind def /col8 {0.000 0.000 0.560 srgb} bind def /col9 {0.000 0.000 0.690 srgb} bind def /col10 {0.000 0.000 0.820 srgb} bind def /col11 {0.530 0.810 1.000 srgb} bind def /col12 {0.000 0.560 0.000 srgb} bind def /col13 {0.000 0.690 0.000 srgb} bind def /col14 {0.000 0.820 0.000 srgb} bind def /col15 {0.000 0.560 0.560 srgb} bind def /col16 {0.000 0.690 0.690 srgb} bind def /col17 {0.000 0.820 0.820 srgb} bind def /col18 {0.560 0.000 0.000 srgb} bind def /col19 {0.690 0.000 0.000 srgb} bind def /col20 {0.820 0.000 0.000 srgb} bind def /col21 {0.560 0.000 0.560 srgb} bind def /col22 {0.690 0.000 0.690 srgb} bind def /col23 {0.820 0.000 0.820 srgb} bind def /col24 {0.500 0.190 0.000 srgb} bind def /col25 {0.630 0.250 0.000 srgb} bind def /col26 {0.750 0.380 0.000 srgb} bind def /col27 {1.000 0.500 0.500 srgb} bind def /col28 {1.000 0.630 0.630 srgb} bind def /col29 {1.000 0.750 0.750 srgb} bind def /col30 {1.000 0.880 0.880 srgb} bind def /col31 {1.000 0.840 0.000 srgb} bind def end save -3.0 93.0 translate 1 -1 scale /cp {closepath} bind def /ef {eofill} bind def /gr {grestore} bind def /gs {gsave} bind def /sa {save} bind def /rs {restore} bind def /l {lineto} bind def /m {moveto} bind def /rm {rmoveto} bind def /n {newpath} bind def /s {stroke} bind def /sh {show} bind def /slc {setlinecap} bind def /slj {setlinejoin} bind def /slw {setlinewidth} bind def /srgb {setrgbcolor} bind def /rot {rotate} bind def /sc {scale} bind def /sd {setdash} bind def /ff {findfont} bind def /sf {setfont} bind def /scf {scalefont} bind def /sw {stringwidth} bind def /tr {translate} bind def /tnt {dup dup currentrgbcolor 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add srgb} bind def /shd {dup dup currentrgbcolor 4 -2 roll mul 4 -2 roll mul 4 -2 roll mul srgb} bind def /$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def /$F2psEnd {$F2psEnteredState restore end} def %%EndProlog $F2psBegin 10 setmiterlimit n -1000 2545 m -1000 -1000 l 6487 -1000 l 6487 2545 l cp clip 0.06000 0.06000 sc % Polyline 7.500 slw n 75 75 m 2475 75 l 2475 375 l 75 375 l cp gs col0 s gr % Polyline n 3075 75 m 5475 75 l 5475 375 l 3075 375 l cp gs col0 s gr % Polyline n 4575 75 m 4575 375 l gs col0 s gr % Polyline n 3975 75 m 3975 375 l gs col0 s gr % Polyline n 675 375 m 675 75 l gs col0 s gr % Polyline n 1350 825 m 3750 825 l 3750 1125 l 1350 1125 l cp gs col0 s gr % Polyline n 2025 1125 m 2025 825 l gs col0 s gr /Times-Roman ff 180.00 scf sf 1200 600 m gs 1 -1 sc (old heap) col0 sh gr /Times-Roman ff 180.00 scf sf 3150 600 m gs 1 -1 sc (old heap) col0 sh gr /Times-Roman ff 180.00 scf sf 4725 600 m gs 1 -1 sc (old heap) col0 sh gr /Times-Roman ff 180.00 scf sf 4125 600 m gs 1 -1 sc (new) col0 sh gr /Times-Roman ff 180.00 scf sf 3975 750 m gs 1 -1 sc (segment) col0 sh gr /Times-Roman ff 180.00 scf sf 225 600 m gs 1 -1 sc (new) col0 sh gr /Times-Roman ff 180.00 scf sf 75 750 m gs 1 -1 sc (segment) col0 sh gr /Times-Roman ff 180.00 scf sf 2625 1350 m gs 1 -1 sc (old heap) col0 sh gr /Times-Roman ff 180.00 scf sf 1500 1350 m gs 1 -1 sc (new) col0 sh gr /Times-Roman ff 180.00 scf sf 1350 1500 m gs 1 -1 sc (segment) col0 sh gr $F2psEnd rs @} @O Figure14.eps @{%!PS-Adobe-2.0 EPSF-2.0 %%Title: Figure14.eps %%Creator: fig2dev Version 3.2 Patchlevel 0-beta3 %%CreationDate: Thu Feb 18 13:26:57 1999 %%For: millst@@dishwasher.cs.rpi.edu (Toby-John Mills) %%Orientation: Portrait %%BoundingBox: 0 0 367 67 %%Pages: 0 %%BeginSetup %%EndSetup %%Magnification: 1.0000 %%EndComments /$F2psDict 200 dict def $F2psDict begin $F2psDict /mtrx matrix put /col-1 {0 setgray} bind def /col0 {0.000 0.000 0.000 srgb} bind def /col1 {0.000 0.000 1.000 srgb} bind def /col2 {0.000 1.000 0.000 srgb} bind def /col3 {0.000 1.000 1.000 srgb} bind def /col4 {1.000 0.000 0.000 srgb} bind def /col5 {1.000 0.000 1.000 srgb} bind def /col6 {1.000 1.000 0.000 srgb} bind def /col7 {1.000 1.000 1.000 srgb} bind def /col8 {0.000 0.000 0.560 srgb} bind def /col9 {0.000 0.000 0.690 srgb} bind def /col10 {0.000 0.000 0.820 srgb} bind def /col11 {0.530 0.810 1.000 srgb} bind def /col12 {0.000 0.560 0.000 srgb} bind def /col13 {0.000 0.690 0.000 srgb} bind def /col14 {0.000 0.820 0.000 srgb} bind def /col15 {0.000 0.560 0.560 srgb} bind def /col16 {0.000 0.690 0.690 srgb} bind def /col17 {0.000 0.820 0.820 srgb} bind def /col18 {0.560 0.000 0.000 srgb} bind def /col19 {0.690 0.000 0.000 srgb} bind def /col20 {0.820 0.000 0.000 srgb} bind def /col21 {0.560 0.000 0.560 srgb} bind def /col22 {0.690 0.000 0.690 srgb} bind def /col23 {0.820 0.000 0.820 srgb} bind def /col24 {0.500 0.190 0.000 srgb} bind def /col25 {0.630 0.250 0.000 srgb} bind def /col26 {0.750 0.380 0.000 srgb} bind def /col27 {1.000 0.500 0.500 srgb} bind def /col28 {1.000 0.630 0.630 srgb} bind def /col29 {1.000 0.750 0.750 srgb} bind def /col30 {1.000 0.880 0.880 srgb} bind def /col31 {1.000 0.840 0.000 srgb} bind def end save -12.0 67.0 translate 1 -1 scale /cp {closepath} bind def /ef {eofill} bind def /gr {grestore} bind def /gs {gsave} bind def /sa {save} bind def /rs {restore} bind def /l {lineto} bind def /m {moveto} bind def /rm {rmoveto} bind def /n {newpath} bind def /s {stroke} bind def /sh {show} bind def /slc {setlinecap} bind def /slj {setlinejoin} bind def /slw {setlinewidth} bind def /srgb {setrgbcolor} bind def /rot {rotate} bind def /sc {scale} bind def /sd {setdash} bind def /ff {findfont} bind def /sf {setfont} bind def /scf {scalefont} bind def /sw {stringwidth} bind def /tr {translate} bind def /tnt {dup dup currentrgbcolor 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add srgb} bind def /shd {dup dup currentrgbcolor 4 -2 roll mul 4 -2 roll mul 4 -2 roll mul srgb} bind def /$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def /$F2psEnd {$F2psEnteredState restore end} def %%EndProlog $F2psBegin 10 setmiterlimit n -1000 2104 m -1000 -1000 l 7312 -1000 l 7312 2104 l cp clip 0.06000 0.06000 sc % Polyline 7.500 slw n 450 975 m 300 750 l gs col0 s gr % Polyline n 300 750 m 300 825 l gs col0 s gr % Polyline n 300 750 m 375 750 l gs col0 s gr % Polyline n 450 75 m 300 300 l gs col0 s gr % Polyline n 300 300 m 300 225 l gs col0 s gr % Polyline n 300 300 m 375 300 l gs col0 s gr % Polyline n 3600 675 m 3600 825 l gs col0 s gr % Polyline n 3600 675 m 3525 750 l gs col0 s gr % Polyline n 3600 675 m 3675 750 l gs col0 s gr % Polyline n 3600 225 m 3600 375 l gs col0 s gr % Polyline n 3600 375 m 3525 300 l gs col0 s gr % Polyline n 3600 375 m 3675 300 l gs col0 s gr % Polyline n 2700 675 m 2700 825 l gs col0 s gr % Polyline n 2700 675 m 2625 750 l gs col0 s gr % Polyline n 2700 675 m 2775 750 l gs col0 s gr % Polyline n 2700 375 m 2775 300 l gs col0 s gr % Polyline n 2700 375 m 2700 225 l gs col0 s gr % Polyline n 2700 375 m 2625 300 l gs col0 s gr % Polyline n 6000 75 m 6225 300 l gs col0 s gr % Polyline n 6225 300 m 6150 300 l gs col0 s gr % Polyline n 6225 300 m 6225 225 l gs col0 s gr % Polyline n 6000 975 m 6225 750 l gs col0 s gr % Polyline n 6225 750 m 6150 750 l gs col0 s gr % Polyline n 6225 750 m 6225 825 l gs col0 s gr % Polyline n 225 375 m 6300 375 l 6300 675 l 225 675 l cp gs col0 s gr /Times-Roman ff 180.00 scf sf 525 150 m gs 1 -1 sc (newSegmentStart) col0 sh gr /Times-Roman ff 180.00 scf sf 525 1050 m gs 1 -1 sc (newRealHeapStart) col0 sh gr /Times-Roman ff 180.00 scf sf 2100 150 m gs 1 -1 sc (newSegmentEnd) col0 sh gr /Times-Roman ff 180.00 scf sf 3600 150 m gs 1 -1 sc (realHeapStart) col0 sh gr /Times-Roman ff 180.00 scf sf 3600 1050 m gs 1 -1 sc (holeEnd) col0 sh gr /Times-Roman ff 180.00 scf sf 2700 1050 m gs 1 -1 sc (holeStart) col0 sh gr /Times-Roman ff 180.00 scf sf 4950 150 m gs 1 -1 sc (realHeapEnd) col0 sh gr /Times-Roman ff 180.00 scf sf 4575 1050 m gs 1 -1 sc (newRealHeapEnd) col0 sh gr $F2psEnd rs @} @O Figure15.eps @{%!PS-Adobe-2.0 EPSF-2.0 %%Title: Figure15.eps %%Creator: fig2dev Version 3.2 Patchlevel 0-beta3 %%CreationDate: Thu Feb 18 13:27:08 1999 %%For: millst@@dishwasher.cs.rpi.edu (Toby-John Mills) %%Orientation: Portrait %%BoundingBox: 0 0 384 276 %%Pages: 0 %%BeginSetup %%EndSetup %%Magnification: 1.0000 %%EndComments /$F2psDict 200 dict def $F2psDict begin $F2psDict /mtrx matrix put /col-1 {0 setgray} bind def /col0 {0.000 0.000 0.000 srgb} bind def /col1 {0.000 0.000 1.000 srgb} bind def /col2 {0.000 1.000 0.000 srgb} bind def /col3 {0.000 1.000 1.000 srgb} bind def /col4 {1.000 0.000 0.000 srgb} bind def /col5 {1.000 0.000 1.000 srgb} bind def /col6 {1.000 1.000 0.000 srgb} bind def /col7 {1.000 1.000 1.000 srgb} bind def /col8 {0.000 0.000 0.560 srgb} bind def /col9 {0.000 0.000 0.690 srgb} bind def /col10 {0.000 0.000 0.820 srgb} bind def /col11 {0.530 0.810 1.000 srgb} bind def /col12 {0.000 0.560 0.000 srgb} bind def /col13 {0.000 0.690 0.000 srgb} bind def /col14 {0.000 0.820 0.000 srgb} bind def /col15 {0.000 0.560 0.560 srgb} bind def /col16 {0.000 0.690 0.690 srgb} bind def /col17 {0.000 0.820 0.820 srgb} bind def /col18 {0.560 0.000 0.000 srgb} bind def /col19 {0.690 0.000 0.000 srgb} bind def /col20 {0.820 0.000 0.000 srgb} bind def /col21 {0.560 0.000 0.560 srgb} bind def /col22 {0.690 0.000 0.690 srgb} bind def /col23 {0.820 0.000 0.820 srgb} bind def /col24 {0.500 0.190 0.000 srgb} bind def /col25 {0.630 0.250 0.000 srgb} bind def /col26 {0.750 0.380 0.000 srgb} bind def /col27 {1.000 0.500 0.500 srgb} bind def /col28 {1.000 0.630 0.630 srgb} bind def /col29 {1.000 0.750 0.750 srgb} bind def /col30 {1.000 0.880 0.880 srgb} bind def /col31 {1.000 0.840 0.000 srgb} bind def end save 0.0 275.0 translate 1 -1 scale /cp {closepath} bind def /ef {eofill} bind def /gr {grestore} bind def /gs {gsave} bind def /sa {save} bind def /rs {restore} bind def /l {lineto} bind def /m {moveto} bind def /rm {rmoveto} bind def /n {newpath} bind def /s {stroke} bind def /sh {show} bind def /slc {setlinecap} bind def /slj {setlinejoin} bind def /slw {setlinewidth} bind def /srgb {setrgbcolor} bind def /rot {rotate} bind def /sc {scale} bind def /sd {setdash} bind def /ff {findfont} bind def /sf {setfont} bind def /scf {scalefont} bind def /sw {stringwidth} bind def /tr {translate} bind def /tnt {dup dup currentrgbcolor 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add srgb} bind def /shd {dup dup currentrgbcolor 4 -2 roll mul 4 -2 roll mul 4 -2 roll mul srgb} bind def /reencdict 12 dict def /ReEncode { reencdict begin /newcodesandnames exch def /newfontname exch def /basefontname exch def /basefontdict basefontname findfont def /newfont basefontdict maxlength dict def basefontdict { exch dup /FID ne { dup /Encoding eq { exch dup length array copy newfont 3 1 roll put } { exch newfont 3 1 roll put } ifelse } { pop pop } ifelse } forall newfont /FontName newfontname put newcodesandnames aload pop 128 1 255 { newfont /Encoding get exch /.notdef put } for newcodesandnames length 2 idiv { newfont /Encoding get 3 1 roll put } repeat newfontname newfont definefont pop end } def /isovec [ 8#200 /grave 8#201 /acute 8#202 /circumflex 8#203 /tilde 8#204 /macron 8#205 /breve 8#206 /dotaccent 8#207 /dieresis 8#210 /ring 8#211 /cedilla 8#212 /hungarumlaut 8#213 /ogonek 8#214 /caron 8#220 /dotlessi 8#230 /oe 8#231 /OE 8#240 /space 8#241 /exclamdown 8#242 /cent 8#243 /sterling 8#244 /currency 8#245 /yen 8#246 /brokenbar 8#247 /section 8#250 /dieresis 8#251 /copyright 8#252 /ordfeminine 8#253 /guillemotleft 8#254 /logicalnot 8#255 /endash 8#256 /registered 8#257 /macron 8#260 /degree 8#261 /plusminus 8#262 /twosuperior 8#263 /threesuperior 8#264 /acute 8#265 /mu 8#266 /paragraph 8#267 /periodcentered 8#270 /cedilla 8#271 /onesuperior 8#272 /ordmasculine 8#273 /guillemotright 8#274 /onequarter 8#275 /onehalf 8#276 /threequarters 8#277 /questiondown 8#300 /Agrave 8#301 /Aacute 8#302 /Acircumflex 8#303 /Atilde 8#304 /Adieresis 8#305 /Aring 8#306 /AE 8#307 /Ccedilla 8#310 /Egrave 8#311 /Eacute 8#312 /Ecircumflex 8#313 /Edieresis 8#314 /Igrave 8#315 /Iacute 8#316 /Icircumflex 8#317 /Idieresis 8#320 /Eth 8#321 /Ntilde 8#322 /Ograve 8#323 /Oacute 8#324 /Ocircumflex 8#325 /Otilde 8#326 /Odieresis 8#327 /multiply 8#330 /Oslash 8#331 /Ugrave 8#332 /Uacute 8#333 /Ucircumflex 8#334 /Udieresis 8#335 /Yacute 8#336 /Thorn 8#337 /germandbls 8#340 /agrave 8#341 /aacute 8#342 /acircumflex 8#343 /atilde 8#344 /adieresis 8#345 /aring 8#346 /ae 8#347 /ccedilla 8#350 /egrave 8#351 /eacute 8#352 /ecircumflex 8#353 /edieresis 8#354 /igrave 8#355 /iacute 8#356 /icircumflex 8#357 /idieresis 8#360 /eth 8#361 /ntilde 8#362 /ograve 8#363 /oacute 8#364 /ocircumflex 8#365 /otilde 8#366 /odieresis 8#367 /divide 8#370 /oslash 8#371 /ugrave 8#372 /uacute 8#373 /ucircumflex 8#374 /udieresis 8#375 /yacute 8#376 /thorn 8#377 /ydieresis] def /Times-Roman /Times-Roman-iso isovec ReEncode /$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def /$F2psEnd {$F2psEnteredState restore end} def %%EndProlog $F2psBegin 10 setmiterlimit n -1000 5575 m -1000 -1000 l 7387 -1000 l 7387 5575 l cp clip 0.06000 0.06000 sc % Polyline 7.500 slw n 150 0 m 6375 0 l gs col-1 s gr % Polyline n 75 75 m 150 0 l gs col-1 s gr % Polyline n 6300 375 m 6375 300 l gs col-1 s gr % Polyline n 6300 75 m 6375 0 l gs col-1 s gr % Polyline n 6375 0 m 6375 300 l gs col-1 s gr % Polyline n 900 375 m 900 75 l 975 0 l gs col-1 s gr % Polyline n 2400 375 m 2400 75 l 2475 0 l gs col-1 s gr % Polyline n 3000 375 m 3000 75 l 3075 0 l gs col-1 s gr % Polyline n 75 75 m 6300 75 l 6300 375 l 75 375 l cp gs col-1 s gr % Polyline n 75 900 m 2400 900 l gs col-1 s gr % Polyline n 75 975 m 75 825 l gs col-1 s gr % Polyline n 2400 975 m 2400 825 l gs col-1 s gr % Polyline n 6300 900 m 3000 900 l gs col-1 s gr % Polyline n 3000 975 m 3000 825 l gs col-1 s gr % Polyline n 6300 975 m 6300 825 l gs col-1 s gr % Polyline n 75 1350 m 150 1275 l 6375 1275 l 6300 1350 l gs col-1 s gr % Polyline n 6375 1275 m 6375 1575 l 6300 1650 l gs col-1 s gr % Polyline n 75 1350 m 6300 1350 l 6300 1650 l 75 1650 l cp gs col-1 s gr % Polyline n 1500 1650 m 1500 1350 l 1575 1275 l gs col-1 s gr % Polyline n 2400 1650 m 2400 1350 l 2475 1275 l gs col-1 s gr % Polyline n 3000 1650 m 3000 1350 l 3075 1275 l gs col-1 s gr % Polyline n 75 2475 m 6300 2475 l 6300 2775 l 75 2775 l cp gs col-1 s gr % Polyline n 75 2475 m 150 2400 l 6375 2400 l 6300 2475 l gs col-1 s gr % Polyline n 6375 2400 m 6375 2700 l 6300 2775 l gs col-1 s gr % Polyline n 3075 2775 m 3075 2475 l 3150 2400 l gs col-1 s gr % Polyline n 3675 2775 m 3675 2475 l 3750 2400 l gs col-1 s gr % Polyline n 3675 3375 m 6300 3375 l gs col-1 s gr % Polyline n 75 3375 m 3075 3375 l gs col-1 s gr % Polyline n 75 3450 m 75 3300 l gs col-1 s gr % Polyline n 3075 3450 m 3075 3300 l gs col-1 s gr % Polyline n 3675 3450 m 3675 3300 l gs col-1 s gr % Polyline n 6300 3450 m 6300 3300 l gs col-1 s gr % Polyline n 75 3825 m 6300 3825 l 6300 4125 l 75 4125 l cp gs col-1 s gr % Polyline n 75 3825 m 150 3750 l 6375 3750 l 6300 3825 l gs col-1 s gr % Polyline n 6375 3750 m 6375 4050 l 6300 4125 l gs col-1 s gr % Polyline n 3075 4125 m 3075 3825 l 3150 3750 l gs col-1 s gr % Polyline n 3675 4125 m 3675 3825 l 3750 3750 l gs col-1 s gr % Polyline n 5325 4125 m 5325 3825 l 5400 3750 l gs col-1 s gr % Polyline n 4575 2775 m 4575 2475 l 4650 2400 l gs col-1 s gr % Polyline n 3675 3825 m 3075 4125 l gs col-1 s gr % Polyline n 3075 2775 m 3675 2475 l gs col-1 s gr % Polyline n 3000 1350 m 2400 1650 l gs col-1 s gr % Polyline n 2400 375 m 3000 75 l gs col-1 s gr % Polyline n 2400 1500 m 2775 1350 l gs col-1 s gr % Polyline n 2700 1650 m 3000 1500 l gs col-1 s gr % Polyline n 2700 375 m 3000 225 l gs col-1 s gr % Polyline n 2400 225 m 2700 75 l gs col-1 s gr % Polyline n 3075 2625 m 3375 2475 l gs col-1 s gr % Polyline n 3375 2775 m 3675 2625 l gs col-1 s gr % Polyline n 3075 3975 m 3375 3825 l gs col-1 s gr % Polyline n 3375 4125 m 3675 3975 l gs col-1 s gr % Polyline n 4200 1650 m 4200 1350 l 4275 1275 l gs col-1 s gr % Polyline n 4200 375 m 4200 75 l 4275 0 l gs col-1 s gr % Polyline n 1275 2775 m 1275 2475 l 1350 2400 l gs col-1 s gr % Polyline n 1275 4125 m 1275 3825 l 1350 3750 l gs col-1 s gr /Times-Roman-iso ff 180.00 scf sf 0 600 m gs 1 -1 sc (old page-info) col-1 sh gr /Times-Roman-iso ff 180.00 scf sf 300 825 m gs 1 -1 sc (table) col-1 sh gr /Times-Roman-iso ff 180.00 scf sf 2550 600 m gs 1 -1 sc (Hole) col-1 sh gr /Times-Roman-iso ff 180.00 scf sf 4125 1125 m gs 1 -1 sc (new segment) col-1 sh gr /Times-Roman-iso ff 180.00 scf sf 825 1125 m gs 1 -1 sc (old heap) col-1 sh gr /Times-Roman-iso ff 180.00 scf sf 1425 1875 m gs 1 -1 sc (old page-info) col-1 sh gr /Times-Roman-iso ff 180.00 scf sf 2550 1875 m gs 1 -1 sc (Hole) col-1 sh gr /Times-Roman-iso ff 180.00 scf sf 1800 2100 m gs 1 -1 sc (table) col-1 sh gr /Times-Roman-iso ff 180.00 scf sf 4650 3600 m gs 1 -1 sc (old heap) col-1 sh gr /Times-Roman-iso ff 180.00 scf sf 975 3600 m gs 1 -1 sc (new segment) col-1 sh gr /Times-Roman-iso ff 180.00 scf sf 3225 4350 m gs 1 -1 sc (Hole) col-1 sh gr /Times-Roman-iso ff 180.00 scf sf 5325 4350 m gs 1 -1 sc (old page-info) col-1 sh gr /Times-Roman-iso ff 180.00 scf sf 3675 3000 m gs 1 -1 sc (old page-info) col-1 sh gr /Times-Roman-iso ff 180.00 scf sf 3975 3225 m gs 1 -1 sc (table) col-1 sh gr /Times-Roman-iso ff 180.00 scf sf 3225 3000 m gs 1 -1 sc (Hole) col-1 sh gr /Times-Roman-iso ff 180.00 scf sf 5625 4575 m gs 1 -1 sc (table) col-1 sh gr /Times-Roman-iso ff 180.00 scf sf 150 3000 m gs 1 -1 sc (new page-info) col-1 sh gr /Times-Roman-iso ff 180.00 scf sf 525 3225 m gs 1 -1 sc (table) col-1 sh gr /Times-Roman-iso ff 180.00 scf sf 150 4350 m gs 1 -1 sc (new page-info) col-1 sh gr /Times-Roman-iso ff 180.00 scf sf 525 4575 m gs 1 -1 sc (table) col-1 sh gr /Times-Roman-iso ff 180.00 scf sf 3075 600 m gs 1 -1 sc (new page-info) col-1 sh gr /Times-Roman-iso ff 180.00 scf sf 3450 825 m gs 1 -1 sc (table) col-1 sh gr /Times-Roman-iso ff 180.00 scf sf 3075 1875 m gs 1 -1 sc (new page-info) col-1 sh gr /Times-Roman-iso ff 180.00 scf sf 3450 2100 m gs 1 -1 sc (table) col-1 sh gr $F2psEnd rs @} #if 0 void PageInfo::print() const { if(unusable()) fprintf(stderr," XXXXX"); else if(free()) fprintf(stderr," ....."); else { fprintf(stderr," %02d", space); if(size == 0) fprintf(stderr,"!%02d", big.nPages); else if(size < 0) fprintf(stderr,"-%02d", -big.nPages); else fprintf(stderr,"=%02d", size); } } if(unusable()) fprintf(stderr," XX"); else if(free()) fprintf(stderr," .."); else { if(size < 0) fprintf(stderr,"_%02", min(big.nPages, 99)); if(gc.currentSpace != gc.nextSpace) { if(space < gc.nextSpace) { putchar(' '); } else if(space < grey) { fprintf(stderr,"*%c%d", 'A' + size, min(9, countBits(wired.toScan|wired.scanned)) ); return; } else { putchar('+'); } } else { putchar(' '); } if(isbig()) fprintf(stderr,"%02", min(big.nPages, 99)); else { int to, from; if( gc.smallSize.sz[size].pageStart == data() ) { to = gc.smallSize.sz[size].top; from = gc.smallSize.sz[size].classTop + size * BYTES_PER_WORD; } else { to = normal.to; from = normal.from; } int count = (normal.from - normal.to) /(size*BYTES_PER_WORD) + 1; fprintf(stderr,"%c%d", 'A' + size, min(9,count)); } } } #endif