Garbage collection liberates you from needing to explicitly free memory. This leads to faster development cycles, cleaner code, and (hopefully) fewer bugs. Garbage collection has been used for years by languages that depend on interpreters (Lisp and Smalltalk), specialized hardware (the Lisp machine), or a carefully controlled runtime environment (Algol-68). However, "conservative" collection techniques make it possible for you to use garbage collection even when the environment does not provide support.

Programs that allocate blocks of memory must return unused blocks so that they may be used again. Most often, they do so by explicitly deallocating blocks with calls to a deallocation routine. An alternative is implicit deallocation using a garbage collector. In this case, a block is implicitly available to be returned whenever there are no references to it. From time to time, a garbage collector scans memory, looking for unreferenced blocks and returning them.

The primary impediment to using garbage collection is that most garbage collectors require help from the programming language, operating system, and/or runtime system. Many environments don't (or can't) provide such help. Conservative garbage collectors, however, require no help. The allocator of an existing program may be replaced with a conservative collector, usually with no other changes required.

Another reason for the infrequent use of garbage collectors is the mistaken belief that they are too slow. While once true, this is no longer the case. The very best garbage collectors use about 3 to 5 percent of the CPU. Conservative collectors use more of the CPU, but are still reasonably efficient.

The design and code of explicitly deallocating programs are convoluted by the need to deallocate blocks both under normal conditions and when erroneous or unusual conditions happen. The design of a garbage-collected program is simple, and the code is clear. The result is an easier-to-understand program which takes less time to design, code, and debug. The program is more likely to be correct, since fewer errors will have been made, debugging them will have been easier, and formal proofs (if used) are easier to construct. Lastly, maintenance will be easier.

The basic elements of this garbage-collecting replacement for C's malloc() will run on 80x86s under DOS. The code, which has been compiled with Microsoft C 5.1, works only with small model programs. However, we do discuss how to extend it to work with large-model programs.

An allocator satisfies dynamic requests for memory by returning the address of a block of memory, which can be used by the client to store data. A deallocator returns a block of memory to the allocator, which may reuse the memory to satisfy a later request. A garbage collector determines which previously allocated memory blocks are still in use and returns the rest to the allocator.

There are two principal methods of garbage collection: Mark and Sweep, and Stop and Copy. Both begin collecting by starting at locations known to contain references to allocated blocks. These locations are called "roots," and usually include the stack and hardware registers.

Mark and Sweep examines the roots. When it finds a reference to an allocated block, it marks the block as referenced. If the block was unmarked, the block is recursively examined for references. When all referenced blocks have been marked, a linear scan of all allocated memory is made, sweeping unreferenced blocks into the allocator's free list(s).

Stop and Copy compacts memory by copying referenced blocks to lower memory locations that were occupied by unreferenced blocks. It then updates references to point to the new locations for the allocated blocks.

Nonconservative garbage collectors receive help in recognizing a value in memory as a reference to a block. Often this is done by tagging values. Some subset of the bits in a value indicates the type of the value. For example, the low-order two bits might be used for the tag, with the value 00 representing a memory reference, 01 an integer, and 02 a float.

A conservative garbage collector requires no such help. Rather, it slithers through memory looking at values, operating on the "conservative" assumption that if a value, when interpreted as an address, refers to an allocated block, then the block must be treated as referenced and not be collected. Occasionally, random values may be incorrectly interpreted as a block reference. In these cases, an unreferenced block is not collected. An example may be helpful. On the PC, a C integer is two bytes, and a long address is two bytes of segment plus two bytes of offset. Suppose two successive integers in memory contain the following as their values: an integer which happens to be a valid segment, and an integer which happens to be the offset within the segment of an allocated block. When the garbage collector examines memory, the two integers appear to be a reference to the block, and so the block is treated as referenced. Such cases of mistaken identity are rare, and their effects usually innocuous: A limited amount of memory is not reclaimed. Sometimes the effects are more severe, but generally there are workarounds. Usually, however, as the misidentified value changes, subsequent collections will pick up the previously uncollected block.

Because random values are being examined, the conservative collector must be careful. It has the following constraints:

• The garbage collector must not change a value. It may not actually be a pointer, but instead a value of some other type. This constraint eliminates Stop and Copy as the basis of conservative garbage collection.
• Before treating the value as a pointer, the garbage collector must validate the value. On 80x86s this means verifying that the segment of a far pointer is valid, and that the offset corresponds to a previously allocated block. If the segment check isn't done, we might generate an address error in a protected-mode program.
• Until the value is validated, the garbage collector may only change its own data, and not, for example, the data at the value interpreted as an address.

     for ( p = malloc(Nbr0fBytes); p < p + Nbr0fItems; p++ )
  {
     process ( p );
  }

In designing the garbage-collection library presented here, we've followed an object-oriented design philosophy. The two principal classes are the allocation segment and garbage collector. The segment class knows about how to manage memory blocks in an 80x86 segment. Since the code runs only under small model, there is only a single-segment object. This segment class must therefore be aware that global data and the stack are also located within the segment. The garbage collector is responsible for marking all blocks reachable from the root. The garbage collector knows nothing about the internals of an allocation segment. The allocation segment provides routines to: validate that a value represents a valid block; return the length of a block; and sweep all unused blocks within it, so they can be reused.

The garbage collector's header files do the following: array.h defines some useful macros for dealing with arrays; bool.h defines an enumeration to represent Booleans rather than the usual usage of macros for True and False; power2.h declares some tables used to quickly perform calculations, the result or operand of which is a power of two. The input of the function is used as the array's index. The value of that array element is the function's result. The input must be in the range 1 to 255. The file pwr2gen.c is the source of a program which generates power2.h; BumpUp computes the first power of two greater or equal to its input, and Log2 computes the ceiling of the log base 2 of its input.

While the code is limited to running under small model with a single segment, we've designed the interfaces to support multiple segments so that compact, large, and mixed-memory model programs can be supported. The major problem is that when presented with a value, we must validate that its segment portion corresponds to a valid segment before calling ASegMarkValue(). The easiest way to do this is to maintain a bit table in Gc.c. When we get a segment from the operating system, we turn on the corresponding bit in the table. To validate a value we extract the segment portion and look it up in the table. If the bit is off, we know the value can't be a pointer and proceed. Otherwise, we pass the value on to ASegMarkValue() for further validation and processing. Logic must be added in several other places. We need to allocate and initialize segments. We need to traverse all allocated segments to clear their marks and sweep them. Lastly, malloc() becomes more complicated since it needs to have a policy for deciding when to garbage collect to try to free up some space vs. allocating another segment to create more space.

We've argued that garbage collecting is usually better than explicit deallocation -- and it is. Just as you often program in a high-level language while using assembler to write critical code, you can use garbage collection in most places, but when necessary, call a deallocator. But to do this, the garbage collector must supply one. While most deallocators try to coalesce adjacent blocks, it's probably better to just add the block to its free list and let the next garbage collection handle the coalescing.

No single allocation strategy is best all the time. Buddy-system allocators are fast, but they waste memory. Next fit is usually slower, but doesn't waste as much memory. Best fit is slow, but wastes very little memory. If we support multiple segments, we can have each support a different allocation scheme. Then, based on requested block size, or some other hint, malloc() can ask the segment with the best strategy for a block.

It's sometimes useful for the client program to know when a block is about to be reclaimed. The garbage collector could do this by calling a client callback function when it finds an unused block. For example, if the file I/O library stored the state data for open files in dynamic memory, then I/O clients would not need to call close. If the client ever let go of all references to a file, it would eventually be garbage collected. This would trigger a call of the callback function, which could then close the file.

Copyright © 1992, Dr. Dobb's Journal