Garbage collector for a virtual heap

• US 6,865,657 B1
• Filed: 06/02/2000
• Issued: 03/08/2005
• Est. Priority Date: 06/02/2000
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation), Sony Corporation (Sony Group Corp.)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Slaughter, Gregory L., Saulpaugh, Thomas E., Traversat, Bernard A., Duigou, Michael J.
• Primary Examiner(s): Padmanabhan, Mano
• Assistant Examiner(s): HO, THANG H
• Application Number:
  US09/586,334
• Time in Patent Office: 1,740 Days
• Field of Search: 711/170, 711/103, 711/2, 707/1, 707/206, 710/36, 717/114, 709/316
• US Class Current: 711/170
• CPC Class Codes: G06F 12/0276 Generational garbage collection
• 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/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 performing generational garbage collection on a virtual heap in a virtual machine 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; and

a garbage collector process performing a generation of generational garbage collection on the virtual heap for the process executing within the virtual machine, wherein said performing the generation of garbage collection comprises;

flushing one or more sections of a first plurality of sections in the in-memory heap to a subset of a second plurality of sections in the store heap, wherein said flushing is performed when objects in the one or more sections have been modified since a previous garbage collection; 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 subset of the second plurality of sections.

2. The method of claim 1, further comprising:

the garbage collector process performing additional generations of said generational garbage collection on additional subsets of the second plurality of sections in the store heap until the entire second plurality of sections in the store heap have been garbage collected.

3. The method of claim 2,

wherein the process execution within the device continues between each generation of said generational garbage collection.

4. The method of claim 1,

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.

5. The method of claim 1, further comprising:

a virtual heap manager generating a request for garbage collection; and

the garbage collector process receiving the request;

wherein the garbage collector process performing the generational garbage collection on the virtual heap for the process executing within the virtual machine is performed in response to the garbage collector process receiving the request.

6. The method of claim 5, further comprising:

the virtual heap manager detecting that available space in the store heap for the process is below a first threshold; and

wherein the virtual heap manager generating the request for garbage collection is performed in response to said detecting.

7. The method of claim 5, further comprising:

the virtual heap manager detecting that a frequency of caching of sections from the store heap to the in-memory heap for the process is above a second threshold; and

wherein the virtual heap manager generating the request for garbage collection is performed in response to said detecting.

8. The method of claim 1, further comprising:

providing a nursery region for storing objects created by the process during execution;

the process creating a plurality of objects during execution; and

storing the plurality of objects in the nursery region.

9. The method of claim 8, further comprising:

determining that one or more of the plurality of objects in the nursery region are referenced by the process; and

moving the one or more of the plurality of objects in the nursery region to the one or more sections of the first plurality of sections in the in-memory heap prior to said flushing the one or more sections of the first plurality of sections in the in-memory heap.

10. The method of claim 9, wherein said determining that the one or more of the plurality of objects in the nursery region are referenced by the process comprises:

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

11. 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.

12. The method of claim 1,

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

13. The method of claim 12,

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.

14. The method of claim 1,

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

15. The method of claim 1,

wherein the device is a mobile computing device.

16. The method of claim 1,

wherein the device is a network client device.

17. The method of claim 1,

wherein the virtual machine is a Java virtual machine;

and wherein the process is a Java application.

18. The method of claim 1,

wherein the objects comprised in the in-memory heap and the store heap comprise code and data for use by the process during execution within the virtual machine.

50. The method of claim 4,

wherein said compacting the subset 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.

51. The method of claim 1,

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 a 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;

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; and

repeating said examining, said removing, and said leaving for each of the objects in the subset of the second plurality of sections.

19. 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;

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

perform a generation of garbage collection on the virtual heap for the process executing within the virtual machine;

wherein, in performing the generation of garbage collection, the generational garbage collector process is further configured to;

flush one or more sections of a first plurality of sections in the in-memory heap to a subset of a second plurality of sections in the store heap, wherein said flushing is performed when objects in the one or more sections have been modified since a previous garbage collection; 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 generational garbage collector process is further configured to;

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

20. The system of claim 19,

wherein the generational garbage collector process is further configured to:

perform additional generations of said garbage collection on additional subsets of the second plurality of sections in the store heap until the entire second plurality of sections in the store heap have been garbage collected;

wherein the process execution within the device continues between each generation of said generational garbage collection.

21. The system of claim 19,

wherein, in performing garbage collection on the subset of the second plurality of sections in the store heap, the generational 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.

22. The system of claim 21,

wherein, in compacting the subset of the second plurality of sections in the store heap, the generational 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 19,

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

examine an object reference structure for a 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;

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; and

repeat said examining, said removing, and said leaving for each of the objects in the subset of the second plurality of sections.

24. The system of claim 19, further comprising:

wherein the device is further configured to execute a virtual heap manager;

wherein the virtual heap manager is configured to;

generate a request for garbage collection;

wherein the generational garbage collector process is further configured to;

receive the request from the virtual heap manager; and

perform said generation of garbage collection on the virtual heap for the process executing within the virtual machine in response to receiving the request.

25. The system of claim 24,

wherein the virtual heap manager is further configured to:

detect that available space in the store heap for the process is below a first threshold;

wherein the virtual heap manager generating the request for garbage collection is performed in response to said detecting.

26. The system of claim 24,

wherein the virtual heap manager is further configured to:

detect that a frequency of caching of sections from the store heap to the in-memory heap is above a second threshold;

wherein the virtual heap manager generating the request for garbage collection is performed in response to said detecting.

27. The system of claim 19,

wherein the in-memory heap comprises a nursery region configured to store a plurality of objects created by the process during execution;

wherein, in performing the generation of garbage collection, the generational garbage collector process is further configured to;

determine that one or more of the plurality of objects stored in the nursery region are referenced by the process; and

move the one or more of the plurality of objects in the nursery region to the one or more sections of the first plurality of sections in the in-memory heap prior to said flushing the one or more sections of the first plurality of sections in the in-memory heap.

28. The system of claim 19, 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.

29. The system of claim 19,

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.

30. The system of claim 19,

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

31. The system of claim 19,

wherein the device is a mobile computing device.

32. The system of claim 19,

wherein the device is a network client device.

33. The system of claim 19,

wherein the virtual machine is a Java virtual machine;

and wherein the process is a Java application.

34. The system of claim 19,

wherein the objects comprised in the in-memory heap and the store heap comprise code and data for use by the process during execution within the virtual machine.

35. 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; and

performing a generation of generational garbage collection on the virtual heap for the process executing within the virtual machine, wherein said performing the generation of garbage collection comprises;

flushing one or more sections of a first plurality of sections in the in-memory heap to a subset of a second plurality of sections in the store heap, wherein said flushing is performed when objects in the one or more sections have been modified since a previous garbage collection; 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 subset of the second plurality of sections.

36. The carrier medium of claim 35, wherein the program instructions are further executable to implement:

performing additional generations of said generational garbage collection on additional subsets of the second plurality of sections in the store heap until the entire second plurality of sections in the store heap have been garbage collected;

wherein the process execution within the device continues between each generation of said generational garbage collection.

37. The carrier medium of claim 35,

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 by 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 and reducing fragmentation in the store heap.

38. The carrier medium of claim 35,

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 a 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;

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; and

repeating said examining, said removing, and said leaving for each of the objects in the subset of the second plurality of sections.

39. The carrier medium of claim 35, wherein the program instructions are executable to implement:

a virtual heap manager generating a request for garbage collection; and

receiving the request;

wherein performing the generational garbage collection on the virtual heap for the process executing within the virtual machine is performed in response to said receiving the request.

40. The carrier medium of claim 39, wherein the program instructions are executable to implement:

the virtual heap manager detecting that available space in the store heap for the process is below a first threshold; and

wherein the virtual heap manager generating the request for garbage collection is performed in response to said detecting.

41. The carrier medium of claim 39, wherein the program instructions are executable to implement:

the virtual heap manager detecting that a frequency of caching of sections from the store heap to the in-memory heap for the process is above a second threshold; and

wherein the virtual heap manager generating the request for garbage collection is performed in response to said detecting.

42. The carrier medium of claim 35, wherein the program instructions are executable to implement:

providing a nursery region for storing objects created by the process during execution;

storing a plurality of objects created by the process during execution in the nursery region;

determining that one or more of the plurality of objects in the nursery region are referenced by the process; and

moving the one or more of the plurality of objects in the nursery region to the one or more sections of the first plurality of sections in the in-memory heap prior to said flushing the one or more sections of the first plurality of sections in the in-memory heap.

43. The carrier medium of claim 42,

wherein, in determining that the one or more of the plurality of objects in the nursery region are referenced by the process, the program instructions are further executable to implement:

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

44. The carrier medium of claim 35,

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.

45. The carrier medium of claim 35,

wherein the store heap is comprised in a flash memory coupled to the device, and wherein the flash memory is addressable in block writes, and 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.

46. The carrier medium of claim 35,

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

47. The carrier medium of claim 35,

wherein the device is a mobile computing device.

48. The carrier medium of claim 35,

wherein the virtual machine is a Java virtual machine;

and wherein the process is a Java application.

49. The carrier medium of claim 35,

wherein the objects comprised in the in-memory heap and the store heap comprise code and data for use by the process during execution within the virtual machine.