Patent ID: 8612493

Claim:
A method of keeping newly allocated objects alive in a snap-shot-at-the-beginning (SATB) garbage collection operation, the method comprising: running a garbage collection cycle in conjunction with an application program; tracing live objects during the garbage collection cycle by utilizing a mark map to identify the live objects, each object being associated with a bit in the mark map, and keeping alive the newly created objects during the step of tracing live objects; populating an allocation cache with a memory chunk having a low address and a high address defining the memory chunk having a plurality of objects stored contiguously, the populating including marking and tracking newly created objects during an allocation cache population phase of the garbage collection cycle, the newly created objects being created during the garbage collection cycle, and the allocation cache population phase of the garbage collection cycle including populating the allocation cache with cells from a heap allocation system; calculating an address of a low mark map word corresponding to the low address of the memory chunk and a position of a low mark map bit within the low mark map word, the low mark map bit defining the low boundary of the mark map range; calculating an address of a high mark map word corresponding to the high address of the memory chunk and a position of a high mark map bit within the low mark map word, the high mark map bit defining the high boundary of the mark map range; determining whether the address of the low mark map word is less than the address of the high mark map word; and responsive to determining that the address of the low mark map word is less than the address of the high mark map word: accessing the low mark map word to update a state of a partial set of bits among the total bits in the low mark map word using an atomic operation, wherein a marked state of a bit indicates a live object; accessing each map word arranged between the low mark map word and the high mark map word to set all bits in all mark map words arranged between the low mark map word and the high mark map word as marked using a non-atomic operation; and accessing the high mark map word to set a partial set of bits among the total bits in the high map word as marked.