Locating references and roots for in-cache garbage collection
View Patent ↗A computer system providing hardware states for garbage collection including a plurality of processors, an object cache operatively connected to at least one of the plurality of processors, and a warden operatively connected to the object cache, wherein the warden broadcasts a non-local command to the object cache whenever the tagged cache line is evicted and crosses the garbage collection boundary and the modified-reference bit in the tagged cache line is set.
1. A computer system providing hardware states for garbage collection comprising:
a plurality of processors;
an object cache operatively connected to at least one of the plurality of processors; and
a tagged cache line comprising a non-local bit, a word, and a modified-reference bit associated with the word;
a warden operatively connected to the object cache, wherein the warden is located at an edge of a garbage collection boundary, wherein the warden broadcasts a non-local command to the object cache whenever the tagged cache line is evicted and crosses the garbage collection boundary and the modified-reference bit in the tagged cache line is set.
2. The computer system of claim 1 , further comprising:
a memory; and
a translator interposed between the warden and the memory, wherein the translator maps an object address to a physical address within the memory.
3. The computer system of claim 1 , wherein the plurality of processors uses an extended instruction set.
4. The computer system of claim 3 , the extended instruction set comprising a modified load procedure.
5. The computer system of claim 3 , the extended instruction set comprising a modified store procedure.
6. The computer system of claim 5 , wherein the modified store procedure sets the modified-reference bit of word whenever an object reference is stored in the word.
7. The computer system of claim 1 , wherein the non-local command to the object cache sets a non-local bit of a referenced object when the tagged cache line that crossed the garbage collection boundary comprises reference to the referenced object.
8. The computer system of claim 1 , the garbage collection boundary comprising at least of one of the plurality of processors and the object cache.
9. The computer system of claim 1 , wherein the warden sets the non-local bit of the tagged cache line when the tagged cache line enters the garbage collection boundary.
10. The computer system of claim 1 , wherein the warden clears the modified-reference bit in the tagged cache line when the tagged cache line enters the garbage collection boundary.
11. The computer system of claim 1 , wherein the object cache is associated with a hardware queue.
12. The computer system of claim 11 , wherein the hardware queue is used by the warden during broadcasts of the non-local command to the object cache.
13. The computer system of claim 1 , wherein one of the plurality of processors broadcasts a mark object command during a garbage collection routine.
14. A computer system providing hardware states for garbage collection comprising:
a plurality of processors;
a tagged cache line comprising a non-local bit, a word, and a modified-reference bit associated with the word;
an object cache operatively connected to at least one of the plurality of processors; and
a warden operatively connected to the object cache, wherein the warden is located at an edge of a garbage collection boundary, wherein the warden broadcasts a non-local command to the object cache whenever the tagged cache line is evicted and crosses the garbage collection boundary and the modified-reference bit in the tagged cache line is set;
a memory; and
a translator interposed between the warden and the memory, wherein the translator maps an object address to a physical address within the memory.
15. A method for local garbage collection in a multiprocessor environment comprising:
halting all processors within a garbage collection boundary;
scanning a tagged cache line in an object cache for a first object when the tagged cache line is live;
marking the first object as live if the first object is referenced by root;
scanning the first object for a reference to a second object if the first object is live;
broadcasting a mark object command if the reference to the second object is found;
marking the tagged cache line as done; and
reclaiming the first object if the first object is not live,
wherein the tagged cache line comprises a mark bit, a non-local bit, a word, and a modified-reference bit associated with the word, and
wherein the tagged cache line is live if at least one selected from the group consisting of the mark bit and the non-local bit is set.
16. The method of claim 15 , wherein broadcasting the mark object command places an object identification number referencing the second object into a queue.
17. The method of claim 16 , comprising:
checking the queue for the object identification number;
releasing the object identification number from the queue if the object identification number is present in the queue;
marking the second object referenced by the object identification number as live if the object identification number is present in the queue;
scanning the second object referenced by the object identification number for a reference to a third object; and
broadcasting the mark object command if the reference to the third object is found.
18. The method of claim 15 , the garbage collection boundary comprising a processor and an object cache.
19. The method of claim 15 , the garbage collection boundary comprising a plurality of processors and a plurality of object caches.
20. The method of claim 15 , wherein a warden is located at an edge of the garbage collection boundary.
21. The method of claim 15 , wherein determining if the first object is a root object uses the non-local bit.
22. The method of claim 15 , wherein scanning the first object for the reference to the second object uses the modified reference bit.
23. The method of claim 15 , further comprising:
performing a non-cached load of the object if the entirety of the first object is not in the garbage collection boundary; and
determining if the first object is live.
24. An apparatus for performing local garbage collection in a multiprocessor environment comprising:
means for halting all processors within a garbage collection boundary;
means for scanning a tagged cache line in an object cache for a first object when the tagged cache line is live;
means for marking the first object as live if the first object is referenced by a root;
means for scanning the first object for a reference to a second object if the first object is live;
means for broadcasting a mark object command if the reference to the second object is found;
means for marking the tagged cache line as done; and
means for reclaiming the first object if the first object is not live,
wherein the tagged cache line comprises a mark bit, a non-local bit, a word, and a modified-reference bit associated with the word, and
wherein the tagged cache line is live if at least one selected from the group consisting of the mark bit and the non-local bit is set.
25. The apparatus of claim 24 , further comprising:
means for checking the queue for the object identification number;
means for releasing the object identification number from the queue if the object identification number is present in the queue;
means for marking the second object referenced by the object identification number as live if the object identification number is present in the queue;
means for scanning the second object referenced by the object identification number for a reference to a third object; and
means for broadcasting the mark object command if the reference to the third object is found.