Ephemeral garbage collection using a tracking mechanism on a card table to determine marked bundles

• US 8,131,955 B2
• Filed: 04/15/2004
• Issued: 03/06/2012
• 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.
• Primary Examiner(s): Savla, Arpan P.
• Application Number:
  US10/824,751
• Publication Number:
  US 20050235120A1
• Time in Patent Office: 2,882 Days
• Field of Search: 711/159, 711/154, 711/173, 707/813, 707/819
• 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 storage medium apparatus having computer-executable instructions encoded thereon to support ephemeral garbage collection by setting a write-watch mechanism to watch specified memory locations, the computer-readable storage medium apparatus being accessible by a computing device, the instructions, upon execution, causing the computing device, during execution of a program, when a statement of the program for execution is obtained, to determine whether the statement includes a store operator, the instructions, upon execution, further causing the computing device to perform operations comprising:

during a loop that is performed for at least two iterations based at least on respective store operators;

storing a value specified in the statement in a memory location specified in the statement;

determining whether the memory location specified is within an ephemeral generation;

in an event the memory location specified is within the ephemeral generation, obtaining a next statement of the program for execution; and

in an event the memory location specified is not within the ephemeral generation, setting a card associated with the memory location specified and obtaining the next statement of the program for execution;

requesting via the write-watch mechanism a list of memory locations, the list;

identifying a plurality of the memory locations that have been accessed since a last ephemeral garbage collection process, each memory location corresponding to one of a plurality of cards associated with one or more objects allocated from within a memory heap, each of the plurality of cards associated with a card table, wherein the card table identifies one or more of the plurality of cards with objects that have been accessed; and

comprising a bitmap, wherein each bit within the bitmap corresponds to one of the plurality of cards, modification of the bitmap occurring when a corresponding bit is set at the time that the card is trimmed to disk;

creating, during the current ephemeral garbage collection process and responsive to exiting the loop upon encountering a statement lacking a store operator, a bundle table containing entries identifying a plurality of bundles, wherein each of the plurality of bundles identifies groupings of subsets of the plurality of cards;

marking, outside of the loop including setting the card, during the current ephemeral garbage collection process, two or more of the plurality of bundles identified in the bundle table using the list, wherein the marked bundles identify groupings of subsets of the plurality of marked cards having associated objects that have been accessed since the last ephemeral garbage collection process; and

performing garbage collection upon at least one accessed object.

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

3. The computer-readable storage medium apparatus of claim 1, wherein the write-watch mechanism records a first access to one of the plurality of memory locations.

4. The computer-readable storage medium apparatus of claim 1, wherein the write-watch mechanism maintains the list of memory locations in response to a request from the ephemeral garbage collection process.

5. The computer-readable storage medium apparatus of claim 1, the operations further comprising resetting the list of memory locations.

6. The computer-readable storage medium apparatus of claim 1, wherein the subset of cards corresponds to a number of cards that are tracked using a page of memory storing the card table.

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

8. The computer-readable storage medium apparatus of claim 7, wherein marking the bit comprises setting the bit.

9. The computer-readable storage medium apparatus of claim 1, wherein determining the at least one marked card 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 of the card bitmap associated with one of the cards that was not accessed.

10. The computer-readable storage medium apparatus of claim 1, the operations further comprising using, by a current ephemeral garbage collection process, information from the write-watch mechanism to determine which bundles in older generations have objects for collection.

11. The computer-readable storage medium apparatus of claim 1, the operations further comprising:

for each marked bundle identified in the bundle table, determining at least one marked card in a grouping of subsets of the plurality of marked cards identified by the marked bundle; and

for each determined marked card, determining at least one accessed object associated with the marked card.

12. A method for executing statements within a program to support ephemeral garbage collection by setting a write-watch mechanism to watch specified memory locations such that during execution of a program, when a statement of the program for execution including a store operator is obtained, a computing device performs the method comprising:

specifying a range of card table memory to watch during program execution by calling a write-watch mechanism that;

performs tracking of access to the card table memory; and

maintains a write-watch list that identifies cards marked within the card table memory since a garbage collection process was last performed, each card being associated with and updated upon access to one or more objects allocated within a memory heap, the memory heap being divided into a plurality of cards with each card being grouped into one of a plurality of bundles, wherein one of the plurality of bundles corresponds to a subset of that plurality of cards that are tracked using a page of card table memory outside of a loop that is traversed at least twice based on a respective number of store operators including marking at least one of the plurality of cards;

during the loop including marking at least one of the plurality of cards, in an event the statement obtained has one of the store operators;

storing a value within the memory heap at a memory location specified by the statement obtained;

determining whether the memory location specified is within an ephemeral generation;

in an event the memory location specified is within the ephemeral generation, obtaining a next statement of the program for execution; and

in an event the memory location specified is not within the ephemeral generation, marking the at least one of the plurality of cards within the card table memory corresponding to the memory location and obtaining a next statement of the program for execution.

13. The method of claim 12, wherein the tracking includes the write-watch mechanism that resides within a memory manager setting bits in the card table memory upon access to at least one of the plurality of cards.

14. The method of claim 12, further comprising an ephemeral garbage collection process that requests the write-watch list when performing garbage collection.

15. The method of claim 12, wherein an ephemeral garbage collection process determines a marked bundle based on the write-watch list.

16. The method of claim 12, wherein the write-watch mechanism sets bits in the card table memory upon access to at least one of the plurality of cards at the time that the card is trimmed to disk.

17. The method of claim 12, further comprising:

determining whether calling the write-watch mechanism resets a write-watch state by inquiring which cards have changed without being considered as having asked and thereby resetting the state, and

in an event the state is to be reset, placing a separate reset call to reset the range of card table memory without reporting whether the cards in the range have been marked.

18. The method of claim 12, further comprising:

tracking access to the card table memory by the write-watch mechanism;

creating, during an ephemeral garbage collection process, one or more bundle tables containing entries identifying groupings of the cards in the plurality of bundles, for each stored statement within the program, the ephemeral garbage collection process occurring after the program execution process;

updating, during the ephemeral garbage collection process, at least one bundle table by marking the entries in the bundle table based on information obtained from the write-watch list, wherein the updated marked bundle table identifies groupings the plurality of marked cards having associated objects that have been accessed since a last garbage collection process;

for each marked bundle table, determining during the ephemeral garbage collection process at least one marked card in a grouping of the plurality of marked cards identified by the marked bundle table;

for each marked card, determining during the ephemeral garbage collection process, at least one accessed object associated with the marked card; and

performing garbage collection during the ephemeral garbage collection process upon the at least one accessed object.

19. A memory management system that sets a write-watch mechanism to watch specified memory locations during execution of a program, obtain a statement of the program for execution, and determine whether the statement obtained includes a store operator, the system comprising:

a processor;

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, wherein upon execution of the plurality of instructions by the processor, the system, based at least on whether the store operator is included in the statement for execution obtained, performs an operation such that;

in an event the statement obtained does not have a store operator, executing the statement; and

in an event the statement obtained has a store operator performing at least two iterations of a loop including;

storing a value specified in the statement obtained in a memory location specified in the statement obtained;

determining whether the memory location specified is within an ephemeral generation;

in an event the memory location specified is within the ephemeral generation, obtaining a next statement of the program for execution; and

in an event the memory location specified is not within the ephemeral generation, setting a card associated with the memory location specified and obtaining the next statement of the program for execution; and

the write-watch mechanism that identifies cards that have been set in the memory location specified since a garbage collection process was last performed, the plurality of cards being grouped into one of the plurality of bundles, and a corresponding bundle of the plurality of bundles that have been marked outside of the loop based at least on encountering a statement not having a store operator including setting the card.

20. The system of claim 19, wherein the write-watch mechanism resides within a memory manager and sets bits in a card table upon access to at least one of the plurality of cards.

21. The system of claim 19, wherein the system:

requests a list from the write-watch mechanism, the list identifying memory locations that have been written into since a last garbage collection process, each memory location corresponding to one of the plurality of cards associated with a card table, wherein the card table identifies one or more cards that have been accessed, the card table and cards being marked to identify the one or more of the plurality of cards with the one or more objects that have been accessed, during execution of the program exclusive of an ephemeral garbage collection process;

creates, during a current ephemeral garbage collection process, one or more bundle tables wherein each bundle table identifies groupings of the plurality of cards in the plurality of bundles;

updates, during the current ephemeral garbage collection process, at least one bundle table by marking bundles within the bundle table based on the list, wherein the marked bundles corresponds to marked cards having associated objects that have been accessed since a last ephemeral garbage collection process;

determines, during the current ephemeral garbage collection process, for each marked bundle within the bundle table, 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 have been accessed;

determines, during the current ephemeral garbage collection process, for each marked card, the one or more objects that have been accessed; and

performs, during the current ephemeral garbage collection process, garbage collection upon the one or more accessed objects.

22. The system of claim 21, wherein the system sets a bit in the card table to identify one or more cards that have been accessed at the time a card that has been accessed is trimmed to disk.

23. The system of claim 19, wherein the system:

determines whether a request resets a write-watch state by inquiring which memory locations have changed without being considered as having asked and thereby resetting the state, and

in an event the state is to be reset, the system places a separate reset request to reset a range of memory locations without reporting whether the memory locations in the range have been marked.

24. The system of claim 21, wherein the marked bundle is identified by a marked bit associated with the marked bundle within a bundle bitmap based on the list.