Method for combining card marking with remembered sets for old area of a memory heap

• US 6,148,310 A
• Filed: 08/25/1998
• Issued: 11/14/2000
• Est. Priority Date: 08/25/1998
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Petrank, Erez, Kolodner, Elliot K., Yehudai, Zvi, Azagury, Alain
• Primary Examiner(s): Kulik, Paul V.
• Application Number:
  US09/139,754
• Time in Patent Office: 812 Days
• Field of Search: 707/206, 711/170-173
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0276 Generational garbage collection
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

A system for garbage collection of memory objects in a memory heap. The system includes memory heap that is partitioned into respective old and young areas. The old area is partitioned into cars and is further associated with card markings and remembered sets data structures. The card markings include for each card, a card time stamp that represents the time that the card was updated. The car includes, for each car, a car time entry stamp that represents the time the remembered set of the car was updated. The system further includes a processor communicating with the memory, and being capable of identifying all cards that were updated later than the remembered set of a selected car. In response to the event, it performs identifying change in pointers that refer from the card to a memory object in the selected car and in response to identified change in pointers, updating the remembered set of the car with the identified pointers. The process is further capable of updating the car time stamp of the selected car.

Claims

1. A computer implemented method for garbage collection of memory objects in a memory, the method comprising:

(a) partitioning said heap or portion thereof into at least one old and at least one young area;

(b) associating said at least one old area with cars that form part of said at least one old area, card markings and remembered sets data structure;

said card markings including, for each card, a card time stamp indicative of a time said card was updated;

each of said cars including, a respective car time stamp indicative of a time the remembered set of said car was updated;

(c) identifying all cards that were updated later than the remembered set of a selected one of said cars and in respect of each card thus identified;

(i) identifying change in pointers that refer from said card to memory object in said selected car and in response to identified change in pointers; and

(ii) updating the remembered set of said car with the identified pointers; and

(d) updating the car time stamp associated with said selected car.

2. The method in claim 1, further comprising

(e) in the case that a card is modified, updating the card time stamp in said card markings;

and

(f) applying garbage collection to memory objects according to said remembered set.

3. The method of claim 1, wherein the step of updating said car time stamp includes updating said car time stamp with garbage collection cycle value, and wherein the step of updating said card time stamp includes updating said card time stamp with garbage collection cycle value.

4. The method according to claim 2, wherein said garbage collection cycle number does not include 0 as a valid value and wherein said step of updating the card time stamp in said card markings, includes:

(i) updating said time stamp to 0 value;

(ii) said step of identifying all cards that were updated later than the remembered set of a selected car includes;

(i) identifying cards having time stamp value equal to 0, and in response thereto updating the card time stamp from 0 to a current garbage collection cycle valves, and

(ii) identifying all cards having updated card time stamp later than the car time stamp of said selected car.

5. The method according to claim 2, wherein said step (f) further including, applying said garbage collection according to said train algorithm.

6. The method according to claim 2, wherein said step (e) further comprising:

in the case that at least one memory object is copied from first card into a second card, updating the card time-stamp of the seconds card to the maximum over the card time stamps of said first and second cards.

7. The method according to claim 2, further comprising the step of applying garbage collection of memory objects also to said young area.

8. The method of claim 7, wherein said young area is partitioned into plurality of generations and wherein said step of applying garbage collection to said young area includes:

(a) associating each young generation with a generation time stamp indicating when the remembered set of said respective generation was last updated;

(b) updating said generation time stamp whenever a selected generation is scanned; and

(c) scanning cards having card time stamp later than the generation time stamp of said selected generation.

18. The computer implemented method of claim 1 further comprising a counter for setting first and second counter values in respect of first and second objects respectively, said counter having a range of n possible values and being incremented or decremented in accordance with update criterion,

an action is taken according to a decision criterion that includes the stipulation that the first counter value is larger or equal to the second counter value;

a method is capable of handling a counter overflow event whereby the counter is incremented beyond said range, the method further includes the steps of;

A) compacting the first and second counter values to m values (m<

n) so as to constitute first and second compacted counter values respectively;

such that if the first counter value is larger than or equal to the second counter value then the compacted first value is not smaller than the compacted second value; and

B) setting the counter to a value from among n-m values within said range,

whereby substantially n-m counter values are released.

9. A system for garbage collection of memory objects in a memory heap;

the system comprising memory heap or portion thereof that is partitioned into at least one old and at least one young areas;

said at least one old area is associated at least cars that form part of said at least one old area, card markings and remembered sets data structure;

said card markings includes, for each card, a card time stamp indicative of the time said card was updated;

said car includes, for each car, a car time entry stamp indicative of the time the remembered set of said car was updated;

the system further comprising;

processor communicating with said memory, and being capable of;

(i) identifying all cards that were updated later than the remembered set of a selected car and in response thereto perform;

identifying change in pointers that refer from said card to memory object in said selected car and in response to identified change in pointers, updating the remembered set of said car with the identified pointers; and

(ii) updating the car time stamp associated with said selected car.

10. The system of claim 9, wherein said processor is further capable of:

(i) in the case that a card is modified, updating the card time stamp in said card markings; and

(ii) applying garbage collection to memory objects according to said remembered set.

11. The system of claim 9, wherein said time stamp is updated by said processor with garbage collection cycle value, and wherein the said card time stamp is updated by said processor with garbage collection cycle value.

12. The system of claim 10, wherein said garbage collection cycle does not include 0 as a valid value and wherein said processor updates the card time stamp in said card marking by updating said time stamp to 0 value;

said processor is further capable of identifying all cards that were updated later than the remembered set of a selected car by identifying cards having time stamp value equal to 0, and in response thereto updating the card time stamp from 0 to a current garbage collection cycle, and identifying all cards having updated card time stamp later than the car time stamp of said selected car.

13. The system of claim 9, wherein said processor is capable of applying said garbage collection according to a train algorithm.

14. The system according to claim 9, wherein said processor is further capable:

in the case that at least one memory object is copied from first card into a second card, updating the card time-stamp of the second card to the maximum over the card time stamps of said first and second cards.

15. The system according to claim 9, wherein said processor is further capable of applying garbage collection of memory objects also to said young area.

16. The system according to claim 15, wherein said young area is partitioned into plurality of generations and wherein said processor is capable of applying garbage collection to said young area by:

(a) associating each young generation with a generation time stamp indicating when the remembered set of said respective generation was last updated;

(b) updating said generation time stamp whenever a selected generation is scanned; and

(c) scanning cards having card time stamp later than the generation time stamp of said selected generation.

19. The system of claim 9, further comprising a counter for setting first and second counter values in respect of first and second objects, respectively, said counter having a range of n possible values and being incremented or decremented in accordance with update criterion,

an action is taken according to a decision criterion that includes the stipulation that the first counter value is larger or equal to the second counter value;

the processor is capable of handling a counter overflow event whereby the counter is incremented beyond said range;

said processor includes;

(i) compactor, compacting the first and second counter values to m values (m<

n) so as to constitute first and second compacted counter values respectively;

such that if the first counter value is larger than or equal to the second counter value then the compacted first value is not smaller than the compacted second value; and

(ii) counter setting unit, setting the counter to a value to a value from among n-m values within said range, whereby substantially n-m counter values are released.

17. A storage medium associated with a processor and accessible to garbage collection application running on said processor, for garbage collection of memory objects, the storage medium includes:

memory heap or portion thereof that is partitioned into at least one old and at least one young areas;

said at least one old area is associated at least cars that form part of said at least one old area, card markings and remembered sets data structure;

said card markings includes, for each card, a card time stamp indicative of the time said card was updated;

said car includes, for each car, a car time stamp indicative of the time the remembered set of said car was updated.