Method and apparatus for improving parallel marking garbage collectors that use external bitmaps

1. A method for performing garbage collection, comprising:

obtaining a first reference bitmap comprising a block address and a plurality of mark bits;

obtaining a first reference;

identifying a mark bit of the plurality of mark bits based on the first reference;

comparing an address associated with the mark bit and the first reference to generate a comparison;

selecting an existing word from a global bit map based on the block address and the comparison;

calculating a new word based on the plurality of mark bits and the existing word;

replacing the existing word in the global bit map with the new word;

reclaiming a block of memory for reuse based on the global bit map after replacing the existing word;

performing a bitwise negation operation on the existing word to generate a negated existing word;

performing a bitwise AND operation on the negated existing word and the plurality of mark bits to generate a result; and

identifying a second reference based on the result, wherein the second reference is reachable.

2. The method of claim 1 , wherein calculating the new word comprises:

performing a bitwise OR operation on the existing word and the plurality of mark bits.

3. The method of claim 1 , further comprising:

setting the mark bit; and

replacing the block address based on the first reference after calculating the new word.

4. The method of claim 1 , wherein the block of memory is identified as unreachable in the global bit map.

5. The method of claim 1 , further comprising:

obtaining the second reference; and

obtaining a second reference bitmap.

6. The method of claim 5 , wherein the first reference bitmap belongs to a first private mark cache associated with a first thread.

7. The method of claim 6 , wherein the second reference bitmap belongs to a second private mark cache associated with a second thread.

8. The method of claim 6 , wherein the second reference bitmap belongs to the first private mark cache.

9. A non-transitory computer readable medium storing instructions for performing garbage collection, the instructions comprising functionality to:

obtain a first reference bitmap comprising a block address and a plurality of mark bits;

obtain a first reference;

identify a mark bit of the plurality of mark bits based on the first reference;

compare an address associated with the mark bit and the first reference to generate a comparison;

select an existing word from a global bit map based on the block address and the comparison;

calculate a new word based on the plurality of mark bits and the existing word;

replace the existing word in the global bit map with the new word;

reclaim a block of memory for reuse based on the global bit map after replacing the existing word;

perform a bitwise negation operation on the existing word to generate a negated existing word;

perform a bitwise AND operation on the negated existing word and the plurality of mark bits to generate a result; and

identify a second reference based on the result, wherein the second reference is reachable.

10. The non-transitory computer readable medium of claim 9 , the instructions to calculate the new word comprising functionality to:

perform a bitwise OR operation on the existing word and the plurality of mark bits.

11. The non-transitory computer readable medium of claim 9 , the instructions further comprising functionality to:

set the mark bit; and

replace the block address based on the first reference after calculating the new word.

12. The non-transitory computer readable medium of claim 9 , wherein the block of memory is identified as unreachable in the global bit map.

13. The non-transitory computer readable medium of claim 9 , the instructions further comprising functionality to:

obtain the second reference; and

obtain a second reference bitmap.

14. The non-transitory computer readable medium of claim 13 , wherein the first reference bitmap belongs to a first private mark cache associated with a first thread, and wherein the second reference bitmap belongs to a second private mark cache associated with a second thread.

15. A system for performing garbage collection, comprising:

a block address identifying a block of memory;

and

a first thread configured to:

obtain a first reference bitmap comprising the block address and a plurality of mark bits;

obtain a first reference;

identify a mark bit of the plurality of mark bits based on the first reference;

compare an address associated with the mark bit and the first reference to generate a comparison;

select an existing word from a global bit map based on the block address and the comparison;

calculate a new word based on the plurality of mark bits and the existing word;

replace the existing word in the global bit map with the new word;

reclaim the block of memory for reuse based on the global bit map after replacing the existing word;

perform a bitwise negation operation on the existing word to generate a negated existing word;

perform a bitwise AND operation on the negated existing word and the plurality of mark bits to generate a result; and

identify a second reference based on the result, wherein the second reference is reachable.

16. The system of claim 15 , wherein the first thread is further configured to:

identify a mark bit of the plurality of mark bits based on the first reference; and

compare an address of the plurality of addresses represented by the mark bit with the first reference.

17. The system of claim 15 ,

wherein the first thread is further configured to push the second reference on a first mark stack.

18. The system of claim 17 , further comprising:

a second mark stack; and

a second thread associated with the second mark stack.