Caching mechanism for a virtual heap

• US 6,760,815 B1
• Filed: 06/02/2000
• Issued: 07/06/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: Slaughter, Gregory L., Saulpaugh, Thomas E., Traversat, Bernard A., Duigou, Michael J.
• Primary Examiner(s): Kim, Matthew
• Assistant Examiner(s): Anderson, Matthew D.
• Application Number:
  US09/587,110
• Time in Patent Office: 1,495 Days
• Field of Search: 711/118, 711/133, 711/135, 711/159, 707/206
• US Class Current: 711/135
• CPC Class Codes: G06F 12/0276 Generational garbage collection
• CPC Class Codes: G06F 9/45504 Abstract machines for programme code execution, e.g. Java virtual machine [JVM], interpreters, emulators
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

A caching mechanism for a virtual persistent heap is described. A feature of a virtual persistent heap is the method used to cache portions of the virtual persistent heap into the physical heap. The caching mechanism may be effective with small consumer and appliance devices that typically have a small amount of memory and that may be using flash devices as persistent storage. In the caching mechanism, the virtual persistent heap may be divided into cache lines. A cache line is the smallest amount of virtual persistent heap space that can be loaded or flushed at one time. Caching in and caching out operations are used to load cache lines into the heap or to flush dirty cache lines into the store. Different cache line sizes may be used for different regions of the heap. Translation between a virtual persistent heap address and the heap may be simplified by the caching mechanism. All references may be kept in one address space, the virtual persistent heap address space. The address translation is therefore simplified, and may require no swizzling of virtual references into in-memory heap references when manipulating objects in the heap.

Claims

1. A method for managing a virtual heap on a virtual machine executing within a device, the method comprising:

executing a process within the virtual machine;

providing a virtual heap for the process, wherein the virtual heap comprises a store heap comprising a first plurality of cache lines for storing objects for the process, and wherein the virtual heap further comprises an in-memory heap comprising a second plurality of cache lines for caching objects for access by the process during execution, and wherein the store heap and the in-memory heap are comprised in one memory address space;

storing objects for the process executing within the virtual machine to the store heap;

the process referencing a first one of the objects for the process;

caching a first cache line from the store heap to the in-memory heap in response to the process referencing the first one of the objects for the process, wherein said caching is performed when the first object referenced by the process is in the first cache line of the store heap and not in the in-memory heap when the first object is referenced by the process; and

the process accessing the first object in the first cache line in the in-memory heap.

2. The method of claim 1, further comprising:

determining that the in-memory heap does not comprise the first cache line prior to said caching the first cache line from the store heap to the in-memory heap.

3. The method of claim 2,

wherein said determining that the in-memory heap does not comprise the first cache line comprises:

providing a cache line table comprising entries, wherein each entry comprises information for determining if one of the first plurality of cache lines in the store heap is comprised in the in-memory heap;

locating in the cache line table an entry for the first cache line in the store heap; and

examining the entry for the first cache line in the store heap to determine if the in-memory heap does not comprise the first cache line.

4. The method of claim 3, further comprising:

updating the entry for the first cache line in the cache line table in response to said caching the first cache line from the store heap to the in-memory heap to indicate that the in-memory heap comprises the cached first cache line.

5. The method of claim 1,

wherein the process accessing the first object in the first cache line in the in-memory heap further comprises:

the process modifying the first cache line in the in-memory heap; and

flushing the modified first cache line from the in-memory heap to the store heap.

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

7. The method of claim 6,

wherein each of the plurality of store heaps in the persistent store is of a same size.

8. The method of claim 6,

wherein the persistent store further comprises a system segment comprising a third plurality of cache lines comprising system objects comprising system code and data sharable by the plurality of processes;

wherein the method further comprises;

the process referencing a first one of the system objects;

caching a second cache line from the system segment in the persistent store to the in-memory heap in response to the process referencing the first one of the system objects, wherein said caching is performed when the first system object referenced by the process is in the second cache line of the system segment of the persistent store and not in the in-memory heap when the first system object is referenced by the process; and

the process accessing the first system object in the second cache line in the in-memory heap.

9. The method of claim 1,

wherein the cache lines in the in-memory heap and the cache lines in the store heap are a same size.

10. The method of claim 1,

wherein the in-memory heap comprises a plurality of regions;

wherein each of the plurality of regions comprises one or more cache lines;

wherein a first one or more cache lines in a first region of the in-memory heap are a different size than a second one or more cache lines in a second region of the in-memory heap.

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

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 device is a mobile computing device.

14. The method of claim 1,

wherein the virtual machine is a Java virtual machine;

and wherein the process is a Java application.

15. The method of claim 1,

wherein the objects for the process comprise code and data for use by the process during execution within the virtual machine.

16. The method of claim 1,

wherein a cache line comprises one or more objects;

and

wherein the cache line is the smallest unit of memory moved between the in-memory heap and the store heap.

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, and wherein the store heap is comprised within a virtual heap for the process, and wherein the store heap comprises a first plurality of cache lines for storing objects 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, and wherein the in-memory reap is comprised within the virtual heap, and wherein the in-memory heap compris a second plurality of cache lines for caching objects for access by the process during execution;

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

wherein the process is configured to reference a first one of the objects for the process during execution;

wherein the device is further configured to execute a virtual machine virtual memory manager, wherein the virtual machine virtual memory manager is configured to;

store objects for the process executing within the virtual machine to the store heap; and

cache a first cache line from the store heap to the in-memory heap in response to the process referencing the first one of the objects for the process when the first object referenced by the process is in the first cache line of the store heap and not in the in-memory heap; and

wherein the process is further configured to access the first object in the first cache line in the in-memory heap.

18. The system of claim 17,

wherein the virtual machine virtual memory manager is further configured to:

determine that the in-memory heap does not comprise the first cache line prior to said caching the first cache line from the store heap to the in-memory heap.

19. The system of claim 18,

wherein, in determining that the in-memory heap does not comprise the first cache line, the virtual machine virtual memory manager is further configured to:

locate in a cache line table an entry for the first cache line in the store heap, wherein the cache line table comprises entries, wherein each entry comprises information for determining if one of the first plurality of cache lines in the store heap is comprised in the in-memory heap;

examine the entry for the first cache line in the store heap to determine if the in-memory heap does not comprise the first cache line; and

update the entry for the first cache line in the cache line table in response to said caching the first cache line from the store heap to the in-memory heap to indicate that the in-memory heap comprises the cached first cache line.

20. The system of claim 17,

wherein, in accessing the first object in the first cache line in the in-memory heap, the process is further configured to:

modify the first cache line in the in-memory heap; and

wherein the virtual machine virtual memory manager is further configured to;

flush the modified first cache line from the in-memory heap to the store heap.

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

22. The system of claim 21,

wherein each of the plurality of store heaps in the persistent store is of a same size.

23. The system of claim 21,

wherein the persistent store further comprises a system segment comprising a third plurality of cache lines comprising system objects comprising system code and data sharable by the plurality of processes;

wherein the process is further configured to;

reference a first one of the system objects;

wherein the virtual machine virtual memory manager is further configured to;

cache a second cache line from the system segment in the persistent store to the in-memory heap in response to the process referencing the first one of the system objects when the first system object referenced by the process is in the second cache line of the system segment of the persistent store and not in the in-memory heap; and

wherein the process is further configured to;

access the first system object in the second cache line in the in-memory heap.

24. The system of claim 17,

wherein the cache lines in the in-memory heap and the cache lines in the store heap are a same size.

25. The system of claim 17,

wherein the in-memory heap comprises a plurality of regions;

wherein each of the plurality of regions comprises one or more cache lines;

wherein a first one or more cache lines in a first region of the in-memory heap are a different size than a second one or more cache lines in a second region of the in-memory heap.

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

27. The system of claim 17,

wherein the device is a mobile computing device.

28. The system of claim 17,

wherein the virtual machine is a Java virtual machine;

and wherein the process is a Java application.

29. The system of claim 17,

wherein the objects for the process comprise code and data for use by the process during execution within the virtual machine.

30. The system of claim 17,

wherein a cache line comprises one or more objects;

and

wherein the cache line is the smallest unit of memory moved between the in-memory heap and the store heap.

31. A carrier medium comprising programming instructions executable to manage a virtual heap on a virtual machine executing within a device, wherein the program instructions are executable to implement:

providing a virtual heap for a process executing within the virtual machine, wherein the virtual heap comprises a store heap comprising a first plurality of cache lines for storing objects for the process, and wherein the virtual heap further comprises an in-memory heap comprising a second plurality of cache lines for caching objects for access by the process during execution, and wherein the store heap and the in-memory heap are comprised in one memory address space;

storing objects for the process executing within the virtual machine to the store heap;

caching a first cache line from the store heap to the in-memory heap in response to the process referencing a first one of the objects for the process when the first object referenced by the process is in the first cache line of the store heap and not in the in-memory heap; and

wherein the process accesses the first object in the first cache line in the in-memory heap subsequent to said caching.

32. The carrier medium of claim 31,

wherein the program instructions are further executable to implement:

determining that the in-memory heap does not comprise the first cache line prior to said caching the first cache line from the store heap to the in-memory heap.

33. The carrier medium of claim 32,

wherein, in determining that the in-memory heap does not comprise the first cache line, the program instructions are further executable to implement:

locating in a cache line table an entry for the first cache line in the store heap, wherein the cache line table comprises entries, wherein each entry comprises information for determining if one of the first plurality of cache lines in the store heap is comprised in the in-memory heap;

examining the entry for the first cache line in the store heap to determine if the in-memory heap does not comprise the first cache line; and

updating the entry for the first cache line in the cache line table in response to said caching the first cache line from the store heap to the in-memory heap to indicate that the in-memory heap comprises the cached first cache line.

34. The carrier medium of claim 31,

wherein the process modifies the first cache line in the in-memory heap when accessing the first cache line;

wherein the program instructions are further executable to implement;

flushing the modified first cache line from the in-memory heap to the store heap.

35. The carrier medium of claim 31,

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.

36. The carrier medium of claim 35,

wherein the persistent store further comprises a system segment comprising a third plurality of cache lines comprising system objects comprising system code and data sharable by the plurality of processes;

wherein the program instructions are further executable to implement;

caching a second cache line from the system segment in the persistent store to the in-memory heap in response to the process referencing a first one of the system objects when the first system object referenced by the process is in the second cache line of the system segment of the persistent store and not in the in-memory heap; and

wherein the process accesses the first system object in the second cache line in the in-memory heap.

37. The carrier medium of claim 31,

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.

38. The carrier medium of claim 31,

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.

39. The carrier medium of claim 31,

wherein the objects for the process comprise code and data for use by the process during execution within the virtual machine.

40. The carrier medium of claim 31,

wherein a cache line comprises one or more objects;

and

wherein the cache line is the smallest unit of memory moved between the in-memory heap and the store heap.