System and method for performing garbage collection on a large heap

• US 20050235120A1
• Filed: 04/15/2004
• Published: 10/20/2005
• Est. Priority Date: 04/15/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Dussud, Patrick H.
• Granted Patent: US 8,131,955 B2
• Time in Patent Office: Days
• US Class Current: 711/159
• CPC Class Codes: G06F 12/0276 Generational garbage collection

Abstract

The techniques and mechanisms described herein are directed to a system for performing garbage collection on a large heap that is divided into several cards which are grouped into bundles. The techniques include initiating a write-watch mechanism to track accesses to a card table that identifies marked cards. The write-watch mechanism provides a list of the written card table locations to a garbage collection process which determines marked bundles based on the list. For each marked bundle, the marked cards within the marked bundle are scanned to identify the accessed objects. The accessed objects are then collected. Because determining the marked bundles is performed at the start of the garbage collection process and not whenever the memory locations within the bundle are accessed, the present technique reduces the overhead associated with bundle marking and allows the efficiency of the garbage collection process to be less dependent on heap size.

Claims

1. A computer-readable medium having computer-executable instructions for performing ephemeral garbage collection, the instructions comprising:

obtaining a list of memory locations that have been written into since the last ephemeral garbage collection, each memory location corresponding to one of a plurality of addresses for accessing a card table that identifies marked cards, the marked cards being associated with one or more objects allocated from within a memory heap, the memory heap being divided into a plurality of cards which are grouped into a plurality of bundles, each marked card being one of the plurality of cards;

identifying at least one marked bundle out of the plurality of bundles based on the list;

for each marked bundle, determining the marked cards within the marked bundle;

for each marked card, determining at least one accessed object within the marked card; and

performing garbage collection upon the at least one accessed object.

2. The computer-readable medium of claim 1, wherein obtaining the list of memory locations comprises requesting the list from a write-watch mechanism.

3. The computer-readable medium of claim 2, wherein the write-watch mechanism operates within a memory manager.

4. The computer-readable medium of claim 2, wherein the write-watch mechanism records a first access to the memory location.

5. The computer-readable medium of claim 4, wherein the write-watch mechanism does not record subsequent accesses to the same memory location.

6. The computer-readable medium of claim 2, wherein the list of memory locations is maintained in response to a request from the ephemeral garbage collection process.

7. The computer-readable medium of claim 1, further comprising resetting the list of memory locations.

8. The computer-readable medium of claim 1, wherein the group of cards grouped into each bundle corresponds to a number of cards that are tracked using a page of memory storing the card table.

9. The computer-readable medium of claim 1, wherein identifying the marked bundle comprises marking a bit associated with the marked bundle within a bundle bitmap based on the memory locations within the list.

10. The computer-readable medium of claim 9, wherein marking the bit comprises setting the bit.

11. The computer-readable medium of claim 1, wherein determining the marked cards comprises scanning a card bitmap having a bit for each of the plurality of cards, the bit for each marked card being different than another bit associated with one of the cards that was not accessed.

12. A method for executing statements within a program to support ephemeral garbage collection, the method comprising:

specifying a range of card table memory to watch during program execution, the card table memory identifying marked cards that are associated with one or more objects allocated within a memory heap, the memory heap being divided into a plurality of cards which are grouped into a plurality of bundles, each marked card being one of the plurality of cards; and

for each store statement within the program, storing a value at a memory location within the heap memory based on the store statement, marking one of the plurality of cards within the card table based on the memory location, and tracking the card table memory.

13. The method of claim 12, wherein specifying the range of card table memory includes calling a write-watch mechanism that performs the tracking of the card table memory.

14. The method of claim 13, wherein the write-watch mechanism resides within a memory manager.

15. The method of claim 12, wherein each bundle corresponds to a number of cards that are tracked using a page of card table memory.

16. The method of claim 12, further comprising providing a list of addresses that access the card table memory.

17. The method of claim 16, wherein an ephemeral garbage collection process requests the list when performing a garbage collection cycle.

18. The method of claim 12, wherein tracking is performed on an initial access to the card table memory and not upon subsequent accesses to the card table memory.

19. A system for performing ephemeral garbage collection, the system comprising:

a processor; and

a memory into which a plurality of instructions are loaded and into which a plurality of objects are dynamically allocated, the memory having a heap into which the objects are allocated, the heap being divided into a plurality of cards which are grouped into a plurality of bundles, each card being associated with one or more of the plurality of objects, the plurality of instructions performing a method comprising;

during a garbage collection cycle, obtaining a list of memory locations that have been written into since the last garbage collection cycle, each memory location corresponding to one of a plurality of addresses for accessing a card table that identifies marked cards, each marked card being one of the plurality of cards;

identifying at least one marked bundle out of the plurality of bundles based on the list;

for each marked bundle, determining at least one marked card within the marked bundle the at least one marked card indicating that one or more objects associated with the marked card has been accessed;

for each marked card, determining at least one accessed object within the marked card; and

performing garbage collection upon the at least one accessed object.

20. The system of claim 19, wherein obtaining the list of memory locations comprises requesting the list from a write-watch mechanism.

21. The system of claim 20, wherein the write-watch mechanism resides within a memory manager.

22. The computer-readable medium of claim 19, wherein the group of cards grouped into each bundle corresponds to a number of cards that are tracked using a page of memory storing the card table.

23. The computer-readable medium of claim 19, wherein identifying the marked bundle comprises marking a bit associated with the marked bundle within a bundle bitmap based on the memory locations within the list.

24. The computer-readable medium of claim 23, wherein marking the bit comprises setting the bit.