Patent ID: 8335806

Claim:
A non-transitory computer readable storage medium comprising a plurality of instructions for garbage collection, the plurality of instructions comprising functionality to: create a mark bitmap comprising a plurality of marks, wherein each of the plurality of marks corresponds to a memory location of a heap memory; create a rescan map comprising a plurality of region fields, wherein each of the plurality of region fields corresponds to a fixed-size contiguous region of the mark bitmap; identify a first data object referenced by a second data object, wherein the first data object and the second data object are included in a plurality of data objects residing in the heap memory; determine that an address of the first data object is lower than a pointer position, wherein the pointer position is an address of the second data object; add, in response to determining that the address of the first data object is lower than the pointer position, an identifier for the first data object to a mark stack; determine that a number of identifiers in the mark stack has reached a predefined flush threshold, wherein each identifier in the mark stack is associated with a different one of the plurality of data objects; in response to determining that the number of identifiers in the mark stack has reached the predefined flush threshold: increment a flush counter; set a subset of the plurality of marks included in the mark bitmap to grey, wherein each of the subset of the plurality of marks is associated with a unique identifier in the mark stack; set, in the rescan map, at least one region field of the plurality of region fields to a value of the flush counter to indicate that at least one fixed-size contiguous region of the mark bitmap includes any of the plurality of marks; identify, in the plurality of region fields of the rescan map, a set of region fields having the value of the flush counter; perform a rescan of a portion of the heap memory corresponding to the set of region fields; identify, based on the rescan, at least one unreachable data object of the plurality of data objects; and free, in the portion of the heap memory, at least one memory segment corresponding to the unreachable data object.