This invention relates to garbage collectors that scan and summarize heap memory as part of a garbage collection process. In general, memory reclamation may be carried out by a special purpose garbage collection algorithm that locates and reclaims memory which is unused, but has not been explicitly de-allocated. There are many known garbage collection algorithms, including reference counting, mark-sweep, mark-compaction and generational garbage collection algorithms. These, and other garbage collection techniques, are described in detail in a book entitled “Garbage Collection, Algorithms For Automatic Dynamic Memory Management” by Richard Jones and Raphael Lins, John Wiley & Sons, 1996.
An object may be located by a “reference”, or a small amount of information that can be used to access the object data structure. Garbage collectors typically examine these references to determine which objects are reachable and, thus, must be maintained and which objects are no longer reachable and, thus, constitute garbage that can be reclaimed. However, when application threads run they can create, delete and modify references. Accordingly, some mechanism must be used to inform the collector of changes made to references by application threads while the collector is examining the references.
Write barriers are one method used to notify garbage collectors of changes in reference values in the heap caused by application threads. Typically, a write barrier intercepts an attempt by an application thread to store a value to memory. The write barrier can then check to determine whether a reference is being modified and, if so, mark the reference as modified, inform the collector of the modification or perform other processing that will later inform the collector that the reference has been modified. Write barriers are discussed in general in the aforementioned book by Jones and Lins.
Write barrier techniques have typically fallen into three categories: (1) hardware barriers and memory protection, (2) card tables, and (3) sequential store buffers (SSBs). Hardware barriers and memory protection schemes use special hardware or the memory protection provided by the virtual memory system to detect memory stores by the application threads.
Card tables are typically used with generational garbage collectors, which have younger generations that are collected frequently and older generations that are collected less frequently. In such systems it is necessary to track references from older generations into younger generations so that the younger generations can be collected without examining every object in the older generations. In a card table technique, the heap memory belonging to the older generations is split into equal-size chunks called “cards.” A card table is an array with a one entry per card in the heap. When a reference update occurs, the card containing the updated reference is marked “dirty” by setting its entry in the card table to an appropriate value. Later, during the collection process, only heap memory areas corresponding to dirty cards are scanned.
Sequential store buffers are thread-local buffers that store the addresses of fields into which cross-generational references are stored. The references may be filtered before storing them to eliminate references that are not of interest and to eliminate duplicates in the buffers. An overflow of a buffer is trapped and causes the buffer to be processed and recycled for further use.
Because most collection is driven either by the allocation activity of the application threads or by the collector, if it is performing collections concurrently with the operation of the application threads, one challenge has been how to control how much memory must be scanned and summarized by the collector when it suspends the application threads to perform a collection. The ability to limit the amount of memory that must be scanned is particularly important for space-incremental techniques like the Train algorithm. Some collectors address this problem by limiting the amount of memory the application may mark as dirty, while other collectors have employed concurrent threads to scan modified locations. The card table and sequential store buffer write barrier techniques tend to collapse repeated stores to the same or close reference locations to the same card or buffer. Since only dirty cards or buffers into which field addresses have been stored are scanned, the amount of scanned memory is reduced. However, the use of card tables incurs two costs. First, the number of cards that must be scanned can approach the number of cards comprising the generation with which they are associated; second, all entries of the card table must be examined regardless of which ones are marked as dirty; and, third, when a card is processed, all reference locations in the card must be examined regardless of which ones have been recently modified. As the size of the generation associated with the cards and card table increases both of these costs increase. Sequential store buffers can determine entries to be scanned more exactly, but incur additional processing when a buffer becomes full.