System and method for memory reclamation

• US 6,874,074 B1
• Filed: 11/13/2000
• Issued: 03/29/2005
• Est. Priority Date: 11/13/2000
• Status: Expired due to Term

• Current Assignee: Wind River Systems Incorporated (Aptiv PLC)
• Original Assignee: Wind River Systems Incorporated (Aptiv PLC)
• Inventors: Burton, Felix, Dutta, Sandeep
• Primary Examiner(s): Padmanabhan, Mano
• Assistant Examiner(s): SONG, HUA JASMINE
• Application Number:
  US09/711,589
• Time in Patent Office: 1,597 Days
• Field of Search: 707/206, 707/205, 707/101, 711/154, 711/158, 711/170, 717/140
• US Class Current: 711/170
• CPC Class Codes: G06F 12/0269 Incremental or concurrent garbage collection, e.g. in real-time systems G06F12/0261 takes precedence
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

A method for memory reclamation is disclosed that includes marking a memory object when an attempt to alter a reference to the memory object is detected by a software write barrier. Marking be by using representations (“black,” “white”, “gray”) stored as part of a garbage collection information data structure associated with each memory object. Initially, all allocated memory objects are marked white. Objects are then processed such that objects referenced by pointers are marked gray. Each object marked gray is then processed to determine objects referenced by pointers in it, and such objects are marked gray. When all objects referenced by pointers in the selected gray objected have been processed, the selected gray object is marked black. When all processing has been completed, objects still marked white may be reclaimed. Also described is a garbage collector which runs as a task concurrently with other tasks. A priority of the garbage collector may be increased to prevent interruption during certain parts of the garbage collection procedure.

Claims

1. A method of memory reclamation, comprising:

markings a first memory object as in use when an attempt to alter a reference to the first memory object is detected by a software write barrier;

marking a second memory object as in use when the second memory object is visited by a garbage collector;

reclaiming a third memory object marked not in use; and

lowering a priority level of a garbage collector when the reclamation of the third memory object has been completed.

2. The method according to claim 1, further comprising:

reading the contents of a stack, the stack containing a reference to a referenced memory object; and

marking the referenced memory object as in use.

3. The method according to claim 2, wherein

the steps of reading the contents of the stack and marking the referenced memory object as in use are performed atomically.

4. The method according to claim 2, further comprising:

lowering a priority level of the garbage collector when the steps of reading the contents of the stack and marking the referenced memory object as in use are completed.

5. The method according to claim 1, further comprising:

repeating the steps of marking the second memory object and reclaiming the third memory object; and

controlling the frequency of repetition of the steps of marking the second memory object and reclaiming the third memory object.

6. A method for memory reclamation, comprising:

marking a first memory object when an attempt to alter a reference to the first object is detected by a software write barrier;

reading the contents of a stack, the stack containing a reference to a referenced memory object;

marking the referenced memory object;

raising a priority level of a garbage collector to a raised level before the steps of reading the contents of a stack and marking the referenced memory object; and

maintaining the priority level of the garbage collector at a raised level during the steps of reading the contents of a stack and marking the referenced memory object.

7. The method according to claim 6, further comprising:

reading the contents of a global memory location, the global memory location containing a reference to a referenced memory object; and

marking the referenced memory object as in use.

8. A method for memory reclamation, comprising:

marking a first memory object as in use when an attempt to alter a reference to the first memory object is detected by a software write barrier;

reading the contents of a stack, the stack containing a reference to a referenced memory object;

marking the referenced memory object as in use;

interpreting a word contained in the stack as a pointer, the pointer referencing a location in a potentially referenced memory object; and

marking the potentially referenced memory object as in use.

9. A method for memory reclamation, comprising:

marking a first memory object as in use when an attempt to alter a reference to the first memory object is detected by a software write barrier;

reading the contents of a register associated with a task;

interpreting the contents of the register as a pointer, the pointer referencing a location in a potentially referenced memory object; and

marking the potentially referenced memory object as in use.

10. A method for memory reclamation, comprising:

marking a first memory object when an attempt to alter a reference to the first memory object is detected by a software write barrier;

marking a second memory object when the second memory object is visited by a garbage collector;

reclaiming an unmarked memory object;

repeating the steps of marking the second memory object and reclaiming the unmarked memory object; and

controlling the frequency of repetition of the steps of marking the second memory object and reclaiming the unmarked memory object;

wherein the frequency of repetition is controlled by adjusting the priority of a garbage collector.

11. A method for memory reclamation, comprising:

marking a first memory object when an attempt to alter a reference to the first memory object is detected by a software write barrier;

marking a second memory object when the second memory object is visited by a garbage collector;

reading the contents of a global memory location, the global memory location containing a reference to a third referenced memory object;

marking the third referenced memory object;

reading the contents of a stack, the stack containing a reference to a fourth referenced memory object;

marking the fourth referenced memory object;

raising a priority level of a garbage collector to a raised level before the steps of reading the contents of the stack and marking the fourth referenced memory object;

maintaining the priority level of the garbage collector at a raised level during the steps of reading the contents of the stack and marking the fourth referenced memory object;

lowering the priority level of the garbage collector when the steps of reading the contents of the stack and marking the fourth referenced memory object are completed; and

reclaiming an unmarked memory object;

lowering the priority level of the garbage collector when the step of reclaiming the unmarked memory object is completed;

wherein the steps of reading the contents of the stack and marking the fourth referenced memory object are performed atomically.

12. A system comprising:

a software write barrier, the software write barrier marking a first memory object when an attempt is made to alter a reference to the first memory object;

a garbage collector, the garbage collector visiting and marking a second memory object, the garbage collector reclaiming a third memory object that has not been marked;

a garbage collector controller, the garbage collector controller controlling the frequency and duration of execution of the garbage collector;

a priority control scheme, the garbage collector controller using the priority control scheme to control the frequency and duration of execution of the garbage collector.

13. The system according to claim 12, further comprising:

a garbage collection data structure, the garbage collection data structure accessible by the garbage collector.

14. The system according to claim 13, wherein the garbage collection data structure includes a variable indicative of whether a memory object has been visited by the garbage collector.

15. The system according to claim 13, wherein the garbage collection data structure includes a variable indicative of whether a memory object is available for reclamation.

16. The system according to claim 13, wherein the garbage collection data structure includes a variable indicative of whether all children of a memory object have been visited by the garbage collector.

17. The system according to claim 12, wherein the garbage collector reads the contents of a global memory location, the global memory location containing a reference to a referenced memory object, the garbage collector marking the referenced memory object as in use.

18. A method, comprising

receiving a software module, the software module including at least one instruction that modifies a pointer, the pointer referencing a memory object;

and

inserting a software write barrier in the at least one instruction that modifies the pointer;

wherein the software write barrier includes computer code that tests a variable indicative of whether one of

the memory object has been visited by a garbage collector, and

the memory object is available for reclamation.

19. The method according to claim 18, wherein the software write barrier is automatically inserted by a compiler when the software module is compiled.

20. The method according to claim 18, wherein the software write barrier includes computer code that sets a variable to indicate the memory object has been visited by the garbage collector.

21. The method according to claim 18, wherein the software write barrier includes computer code that sets a variable to indicate the memory object is not available for reclamation.

22. The method according to claim 21, wherein the software write barrier is automatically inserted by a compiler when the software module is compiled.

23. A system, comprising:

a compiler, the compiler receiving a software module, the software module including at least one instruction that modifies a pointer, the compiler automatically inserting a software write barrier in the at least one instruction that modifies the pointer.

24. An article of manufacture comprising a computer-readable medium having stored thereon instructions adapted to be executed by a processor, the instructions which, when executed, define a series of steps to be used to control memory reclamation, said steps comprising:

marking a first memory object as in use when the first memory object is visited by a garbage collector;

marking a second memory object as in use when an attempt to alter a reference to the second memory object is detected by a software write barrier;

reclaiming a third memory object; and

lowering a priority level of a garbage collector in response to the reclamation of the third memory object.

25. An article of manufacture comprising a computer-readable medium having stored thereon instructions adapted to be executed by a processor, the instructions which, when executed, define a series of steps to be used to control a method, said steps comprising:

receiving a software module, the software module including at least one instruction that modifies a pointer; and

automatically inserting a software write barrier in the at least one instruction that modifies the pointer.