Method and system for detecting and coalescing free areas during garbage collection

Abstract

A threshold size of “interesting” free space regions (those areas that exceed a minimum size and are therefore worth recovering) is employed during garbage collection when detecting and reclaiming non-allocated memory space. For mark/sweep garbage collection, the threshold is based upon a number of consecutive zero mark bits in a mark bit array. The mark bit array, in which the liveness of each allocated data object is indicated by a logical “1” at the first memory segment of a live object and a logical “0” at the first memory segment for dead object, with the remaining memory segments being marked with a logical “0”, is produced by the mark phase of a mark/sweep garbage collector. During the sweep phase, however, the mark bit array is processed instead of each object in memory. Interesting free space regions, which meet or exceed the threshold size and are targeted for de-allocation and coalescing, are identified from runs of consecutive zeros, with verification that the run corresponds to unused memory. This allows sequences of bits to be inspected concurrently at a high rate, eliminating the need to inspect objects individually and skipping small free space regions intermingled with live objects. By eliminating the need to examine each object for “liveness,” groups of objects, represented by mark bits, are treated as aggregates which may be processed more quickly.