Garbage collection using nursery regions for new objects in a virtual heap

• US 6,763,440 B1
• Filed: 06/02/2000
• Issued: 07/13/2004
• Est. Priority Date: 06/02/2000
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Duigou, Michael J., Slaughter, Gregory L., Saulpaugh, Thomas E., Traversat, Bernard A.
• Primary Examiner(s): Kim, Matthew
• Assistant Examiner(s): Anderson, Matthew D.
• Application Number:
  US09/587,077
• Time in Patent Office: 1,502 Days
• Field of Search: 711/159, 711/133, 711/135, 711/103, 707/206
• US Class Current: 711/159
• CPC Class Codes: G06F 12/0276 Generational garbage collection
• CPC Class Codes: G06F 12/08 in hierarchically structured memory systems, e.g. virtual memory systems
• CPC Class Codes: G06F 12/0868 Data transfer between cache memory and other subsystems, e.g. storage devices or host systems
• CPC Class Codes: G06F 2212/1032 Reliability improvement, data loss prevention, degraded operation etc
• CPC Class Codes: G06F 2212/152 Virtualized environment, e.g. logically partitioned system
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

A method and system for garbage collecting a virtual heap using nursery regions for newly created objects to reduce flushing of objects from an in-memory heap to a store heap is provided. The garbage collection method is suited for use with small consumer and appliance devices that have a small amount of memory and may be using flash devices as persistent storage. The garbage collection method may provide good performance where only a portion of the virtual heap may be cached in the physical heap. The virtual heap may use a single address space for both objects in the store and the in-memory heap. In one embodiment, a single garbage collector is run on the virtual heap address space. The garbage collection method may remove non-referenced objects from the virtual heap. The garbage collection method may also include a compaction phase to reduce or eliminate fragmentation, and to improve locality of objects within the virtual heap. In one embodiment, the garbage collector for the virtual heap may be implemented as a generational garbage collector using working sets in the virtual heap, where each generation is confined to a working set of the heap. The generational garbage collector may allow the flushing of changes after each garbage collection cycle for each working set region. Heap regions with different flushing policies may be used. An object nursery region without flushing where objects are initially created may be used. When a garbage collection cycle is run, objects truly referenced in the object nursery may be copied back into heap regions to be flushed, while short-lived objects no longer referenced may be deleted without flushing.

Claims

1. A method for garbage collecting a virtual heap for a process executing within a virtual machine executing within a device, the method comprising:

providing a store heap for the process, wherein the store heap is comprised in the virtual heap;

providing an in-memory heap for the process, wherein the in-memory heap comprises a cached portion of the store heap for the process, and wherein the in-memory heap is comprised in the virtual heap;

the process creating a plurality of objects during execution;

storing the plurality of objects in a nursery region of the in-memory heap; and

a garbage collector process performing garbage collection on the virtual heap for the process executing within the virtual machine, wherein said garbage collection removes non-referenced objects from the virtual heap;

wherein said performing garbage collection on the virtual heap comprises;

flushing one or more sections of the in-memory heap to the store heap;

wherein, in said flushing the one or more sections of the in-memory heap to the store heap during said garbage collection, the nursery region is not flushed to the store heap.

2. The method of claim 1,

wherein said performing garbage collection on the virtual heap comprises:

determining that a first object in the plurality of objects stored in the nursery region is referenced by the process; and

moving the first object from the nursery region to a first section of a first plurality of sections in the in-memory heap in response to said determining that the first object is referenced by the process.

3. The method of claim 2,

wherein said determining that the first object in the nursery region is referenced by the process comprises:

examining an object reference structure for the first object, wherein the object reference structure includes reference information for the first object that indicates whether the first object is referenced by one or more other objects in the virtual heap.

4. The method of claim 2,

wherein said performing garbage collection on the virtual heap further comprises:

determining that a second object in the plurality of objects stored in the nursery region is not referenced by the process; and

deleting the second object from the nursery region in response to said determining that the second object is not referenced by the process.

5. The method of claim 2,

wherein the first object comprises code and data for use by the process during execution within the virtual machine.

6. The method of claim 1,

wherein said flushing the one or more sections of the in-memory heap to the store heap comprises:

flushing the first section of the first plurality of sections in the in-memory heap to a second section in a subset of a second plurality of sections in the store heap subsequent to said moving the first object from the nursery region to the first section; and

performing garbage collection on the subset of the second plurality of sections in the store heap, wherein said garbage collection comprises;

removing objects not referenced by the process from the second section in the subset of the second plurality of sections.

7. The method of claim 6,

wherein said performing garbage collection on the subset of the second plurality of sections in the store heap further comprises:

compacting the subset of the second plurality of sections in the store heap subsequent to said removing the objects not referenced by the process from the subset of the second plurality of sections, wherein said compacting reduces fragmentation in the store heap.

8. The method of claim 7,

wherein said compacting the subset of the second plurality of sections in the store heap comprises:

moving one or more objects remaining in a first section of the subset to a second section of the subset, thereby freeing space in the first section of the subset.

9. The method of claim 6,

wherein said removing the objects not referenced by the process from the subset of the second plurality of sections comprises:

examining an object reference structure for the first object in the subset, wherein the object reference structure includes reference information for the first object that indicates whether the first object is referenced by one or more other objects in the virtual heap;

removing the first object from the subset of the second plurality of sections if said examining the object reference structure for the first object determines that the first object is not referenced by at least one of the other objects in the virtual heap; and

leaving the first object in the subset of the second plurality of sections if said examining the object reference structure for the first object determines that the first object is referenced by at least one of the other objects in the virtual heap.

10. The method of claim 1,

wherein the store heap is one of a plurality of store heaps in a persistent store;

wherein each of the plurality of store heaps is associated with one of a plurality of processes; and

wherein the process is one of the plurality of processes.

11. The method of claim 1,

wherein the store heap is comprised in a non-volatile memory coupled to the device.

12. The method of claim 1,

wherein the non-volatile memory is a flash memory addressable in block writes, wherein a block write comprises a fixed amount of the flash memory, and wherein the fixed amount of the flash memory is a block write size;

and

wherein the first plurality of cache lines in the store heap and the second plurality of cache lines in the in-memory heap are of the block write size of the flash memory.

13. The method of claim 1,

wherein the store heap and the in-memory heap are comprised in one memory address space.

14. The method of claim 1,

wherein the device is a mobile computing device.

15. The method of claim 1,

wherein the device is a network client device.

16. The method of claim 1,

wherein the virtual machine is a Java virtual machine, and wherein the process is a Java application.

17. A system comprising:

a device configured to execute a virtual machine, wherein the virtual machine is configured to execute a process;

a first memory coupled to the device, wherein the first memory is configured to store a store heap for the process, wherein the store heap is comprised within a virtual heap for the process;

a second memory coupled to the device, wherein the second memory is configured to store an in-memory heap for the process, wherein the in-memory heap is comprised within the virtual heap, wherein the in-memory heap comprises cached portions of the store heap for access by the process, and wherein the in-memory heap comprises a nursery region for storing objects created by the process during execution;

wherein the device is configured to perform garbage collection on the virtual heap according to a garbage collector process, wherein the garbage collector process is configured to;

perform garbage collection on the virtual heap for the process executing within the virtual machine, wherein said garbage collection removes non-referenced objects from the virtual heap;

wherein, in performing garbage collection on the virtual heap, the garbage collector process is further configured to;

flush one or more sections of the in-memory heap to the store heap;

wherein, in flushing the one or more sections of the in-memory heap to the store heap during said garbage collection, the nursery region is not flushed to the store heap.

18. The system of claim 17,

wherein, in performing garbage collection on the virtual heap, the garbage collector process is further configured to:

determine that a first object in the plurality of objects stored in the nursery region is referenced by the process, wherein the first object comprises code and data for use by the process during execution within the virtual machine; and

move the first object from the nursery region to a first section of a first plurality of sections in the in-memory heap in response to said determining that the first object is referenced by the process.

19. The system of claim 18,

wherein, in determining that the first object in the nursery region is referenced by the process, the garbage collector process is further configured to:

examine an object reference structure for the first object, wherein the object reference structure includes reference information for the first object that indicates whether the first object is referenced by one or more other objects in the virtual heap.

20. The system of claim 18,

wherein, in performing garbage collection on the virtual heap, the garbage collector process is further configured to:

determine that a second object in the plurality of objects stored in the nursery region is not referenced by the process; and

delete the second object from the nursery region in response to said determining that the second object is not referenced by the process.

21. The system of claim 17,

wherein, in flushing the one or more sections of the in-memory heap to the store heap, the garbage collector process is further configured to:

flush the first section of the first plurality of sections in the in-memory heap to a second section in a subset of a second plurality of sections in the store heap subsequent to said moving the first object from the nursery region to the first section; and

perform garbage collection on the subset of the second plurality of sections in the store heap;

wherein, in performing garbage collection on the subset of the second plurality of sections in the store heap, the garbage collector process is further configured to;

remove objects not referenced by the process from the second section in the subset of the second plurality of sections.

22. The system of claim 21,

wherein, in performing garbage collection on the subset of the second plurality of sections in the store heap, the garbage collector process is further configured to:

compact the subset of the second plurality of sections in the store heap subsequent to said removing the objects not referenced by the process from the subset of the second plurality of sections, wherein said compacting reduces fragmentation in the store heap.

wherein, in compacting the subset of the second plurality of sections in the store heap, the garbage collector process is further configured to;

move one or more objects remaining in a first section of the subset to a second section of the subset, thereby freeing space in the first section of the subset.

23. The system of claim 21,

wherein, in removing the objects not referenced by the process from the subset of the second plurality of sections, the garbage collector process is further configured to:

examine an object reference structure for the first object in the subset, wherein the object reference structure includes reference information for the first object that indicates whether the first object is referenced by one or more other objects in the virtual heap;

remove the first object from the subset of the second plurality of sections if said examining the object reference structure for the first object determines that the first object is not referenced by at least one of the other objects in the virtual heap, and

leave the first object in the subset of the second plurality of sections if said examining the object reference structure for the first object determines that the first object is referenced by at least one of the other objects in the virtual heap.

24. The system of claim 17, further comprising:

wherein the first memory comprises a persistent store configured to store a plurality of store heaps, and wherein each of the plurality of store heaps is associated with one of a plurality of processes, and wherein the store heap for the process is one of the plurality of store heaps, and wherein the process is one of the plurality of processes.

25. The system of claim 17,

wherein the first memory is a flash memory addressable in block writes, wherein a block write comprises a fixed amount of the flash memory, and wherein the fixed amount of the flash memory is a block write size;

and

wherein the first plurality of cache lines in the store heap and the second plurality of cache lines in the in-memory heap are of the block write size of the flash memory.

26. The system of claim 17,

wherein the store heap and the in-memory heap are comprised in one memory address space.

27. The system of claim 17,

wherein the device is a mobile computing device.

28. The system of claim 17,

wherein the device is a network client device.

29. The system of claim 17,

wherein the virtual machine is a Java virtual machine, and wherein the process is a Java application.

30. A carrier medium comprising programming instructions executable to garbage collect a virtual heap for a process executing within a virtual machine executing within a device, wherein the program instructions are executable to implement:

providing a store heap for the process, wherein the store heap is comprised in the virtual heap;

providing an in-memory heap for the process, wherein the in-memory heap comprises a cached portion of the store heap for the process, and wherein the in-memory heap is comprised in the virtual heap;

storing a plurality of objects created by the process during execution in a nursery region of the in-memory heap; and

performing garbage collection on the virtual heap for the process executing within the virtual machine, wherein said garbage collection removes non-referenced objects from the virtual heap;

wherein, in performing garbage collection on the virtual heap, the program instructions are further executable to implement;

flushing one or more sections of the in-memory heap to the store heap;

wherein, in said flushing the one or more sections of the in-memory heap to the store heap during said garbage collection, the nursery region is not flushed to the store heap.

31. The carrier medium of claim 30,

wherein, in performing garbage collection on the virtual heap, the program instructions are further executable to implement:

determining that a first object in the plurality of objects stored in the nursery region is referenced by the process, wherein the first object comprises code and data for use by the process during execution within the virtual machine; and

moving the first object from the nursery region to a first section of a first plurality of sections in the in-memory heap in response to said determining that the first object is referenced by the process.

32. The carrier medium of claim 31,

wherein, in determining that the first object in the nursery region is referenced by the process, the program instructions are further executable to implement:

examining an object reference structure for the first object, wherein the object reference structure includes reference information for the first object that indicates whether the first object is referenced by one or more other objects in the virtual heap.

33. The carrier medium of claim 31,

wherein, in performing garbage collection on the virtual heap, the program instructions are further executable to implement:

determining that a second object in the plurality of objects stored in the nursery region is not referenced by the process; and

deleting the second object from the nursery region in response to said determining that the second object is not referenced by the process.

34. The carrier medium of claim 30,

wherein, in flushing the one or more sections of the in-memory heap to the store heap, the program instructions are further executable to implement:

flushing the first section of the first plurality of sections in the in-memory heap to a second section in a subset of a second plurality of sections in the store heap subsequent to said moving the first object from the nursery region to the first section; and

performing garbage collection on the subset of the second plurality of sections in the store heap;

wherein, in performing garbage collection on the subset of the second plurality of sections in the store heap, the program instructions are further executable to implement;

removing objects not referenced by the process from the second section in the subset of the second plurality of sections.

35. The carrier medium of claim 34,

wherein, in performing garbage collection on the subset of the second plurality of sections in the store heap, the program instructions are further executable to implement:

compacting the subset of the second plurality of sections in the store heap subsequent to said removing the objects not referenced by the process from the subset of the second plurality of sections, wherein said compacting reduces fragmentation in the store heap; and

wherein, in compacting the subset of the second plurality of sections in the store heap, the program instructions are further executable to implement;

moving one or more objects remaining in a first section of the subset to a second section of the subset, thereby freeing space in the first section of the subset.

36. The carrier medium of claim 34,

wherein, in removing the objects not referenced by the process from the subset of the second plurality of sections, the program instructions are further executable to implement:

examining an object reference structure for the first object in the subset, wherein the object reference structure includes reference information for the first object that indicates whether the first object is referenced by one or more other objects in the virtual heap;

removing the first object from the subset of the second plurality of sections if said examining the object reference structure for the first object determines that the first object is not referenced by at least one of the other objects in the virtual heap; and

leaving the first object in the subset of the second plurality of sections if said examining the object reference structure for the first object determines that the first object is referenced by at least one of the other objects in the virtual heap.

37. The carrier medium of claim 30,

wherein the store heap is one of a plurality of store heaps in a persistent store;

wherein each of the plurality of store heaps is associated with one of a plurality of processes; and

wherein the process is one of the plurality of processes.

38. The carrier medium of claim 30,

wherein the store heap is comprised in a flash memory coupled to the device;

wherein the flash memory is addressable in block writes, wherein a block write comprises a fixed amount of the flash memory, and wherein the fixed amount of the flash memory is a block write size; and

wherein the first plurality of cache lines in the store heap and the second plurality of cache lines in the in-memory heap are of the block write size of the flash memory.

39. The carrier medium of claim 30,

wherein the store heap and the in-memory heap are comprised in one memory address space.

40. The carrier medium of claim 30,

wherein the device is a mobile computing device;

and

wherein the virtual machine is a Java virtual machine; and

wherein the process is a Java application.