Methods and apparatus for performing a memory management technique

• US 6,862,674 B2
• Filed: 06/06/2002
• Issued: 03/01/2005
• Est. Priority Date: 06/06/2002
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems (Oracle Corporation)
• Inventors: Garthwaite, Alexander T., Dice, David
• Primary Examiner(s): Kim, Hong
• Application Number:
  US10/163,677
• Publication Number:
  US 20030229766A1
• Time in Patent Office: 999 Days
• Field of Search: 711/170, 711/173, 711/154, 707/206, 707/205, 717/148
• US Class Current: 711/170
• CPC Class Codes: G06F 12/0261 using reference counting
• 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/99956 File allocation

Abstract

Mechanisms and techniques operate in a computerized device to perform a memory management technique such as garbage collection. The mechanisms and techniques operate to detect, within a storage structure associated with a thread, general memory references that reference storage locations in a general memory area such as a heap. The storage structure may be a stack utilized by the thread, which may be, for example, a Java thread, during operation of the thread in the computerized device. The system maintains a reference structure containing an association to the general memory area for each detected general memory reference within the storage structure. The system then operates a memory management technique on the general memory area for locations in the general memory area other than those for which an association to the general memory area is maintained in the reference structure, thus increasing the performance of the memory management technique.

Claims

1. In a computerized device, a method for performing a memory management technique, the method comprising the steps of:

detecting, within a storage structure associated with a thread, general memory references that reference storage locations in a general memory area, the storage structure utilized by the thread during operation of the thread in the computerized device;

maintaining a reference structure containing an association to the general memory area for each detected general memory reference within the storage structure; and

operating a memory management technique on the general memory area for locations in the general memory area other than those for which an association to the general memory area is maintained in the reference structure.

2. The method of claim 1 comprising the steps of:

identifying an idle condition associated with the thread;

in response to identifying the idle condition, performing the steps of detecting, maintaining and operating a memory management technique.

3. The method of claim 2 wherein:

the step of operating a memory management technique comprises the steps of;

modifying the general memory area to deallocate storage locations in the general memory area for use by threads, the deallocated storage locations being storage locations other than storage locations related to the associations to the general memory area maintained in the reference structure;

updating the reference structure to account for modifications, made to storage locations in the general memory area during operation of the memory management technique, that relate to the associations to the general memory area maintained in the reference structure; and

wherein the method further comprises the steps of;

detecting that the thread is to transition from the idle condition to a non-idle condition; and

in response to the step of detecting that the thread is to transition from an idle condition to a non-idle condition, updating each detected general memory reference in the storage structure associated with the thread based on any updates made to the associations to the general memory area in the reference structure that correspond to the detected general memory references.

4. The method of claim 2 wherein the step of identifying a first idle condition associated with the thread comprises at least one of the steps of:

detecting that the thread has not been operated by the computerized device during a performance of the memory management technique; and

detecting that a top frame of the storage structure indicates that the thread has an associated known blocking call.

5. The method of claim 2 wherein the step of identifying a first idle condition associated with the thread comprises the step of:

detecting an inactivity period of the thread in the computerized device that indicates the thread has not been operated in the computerized device for a predetermined period of time.

6. The method of claim 1 wherein the step of operating a memory management technique on the general memory area comprises the step of:

performing garbage collection on the general memory area for storage locations in the general memory area other than storage locations related to the associations to the general memory area maintained in the reference structure.

7. The method of claim 6 wherein the step of performing garbage collection on the general memory area comprises the step of:

modifying the general memory area to deallocate storage locations in the general memory area for use by threads, the deallocated storage locations being storage locations other than storage locations related to the associations to the general memory area maintained in the reference structure.

8. The method of claim 7 wherein:

the reference structure is a root array reference structure;

the association to the general memory area maintained for each detected general memory reference is copy of the contents of the detected general memory reference from the storage structure; and

wherein the step of performing garbage collection on the general memory area further comprises the step of;

updating the root array reference structure to account for modifications made to storage locations in the general memory area, made during performance of the memory management technique, that relate to the associations to the general memory area maintained in the reference structure.

9. The method of claim 8 further comprising the steps of:

detecting that the thread is to transition from an idle condition to a non-idle condition; and

in response to the step of detecting that the thread is to transition from an idle condition to a non-idle condition, updating each detected general memory reference in the storage structure associated with the thread based on any updates made to the associations to the general memory area in the root array reference structure that correspond to the detected general memory references.

10. The method of claim 7 wherein:

the reference structure is a summary reference structure; and

the association to the general memory area maintained for each detected general memory reference is a pointer to at least one location in the storage structure that contains the detected general memory references; and

wherein the method comprises the step of;

in response to modifying the general memory area, updating the storage structure associated with the thread to account for modifications made to storage locations in the general memory area, made during performance of the memory management technique, that relate to the associations to the general memory area maintained in the summary reference structure.

11. The method of claim 1 further comprising the step of:

identifying a first idle condition associated with the thread;

in response to identifying the idle condition, performing the steps of detecting, maintaining and operating the memory management technique;

storing the reference structure during operation of the thread in the computerized device;

detecting a second idle condition associated with the thread;

in response to detecting the second idle condition;

identifying at least a portion of the stored reference structure that contains associations to the general memory area that have not changed during the operation of the thread in the computerized device;

repeating the step of detecting, within a storage structure associated with a thread, general memory references that reference storage locations in a general memory area for portions of the storage structure that have changed during the operation of the thread in the computerized device; and

repeating the step of maintaining the reference structure containing an association to the general memory area for each detected general memory reference within the storage structure for those detected general memory references located in those portions of the storage structure that have changed during the operation of the thread in the computerized device, such that associations corresponding to the general memory references detected in the repeated step of maintaining are added to the reference structure.

12. The method of claim 11 wherein the step of identifying at least a portion of the stored reference structure that contains associations to the general memory area that have not changed during the operation of the thread in the computerized device comprises the steps of:

examining the storage structure associated with the thread to detect predetermined storage locations in the storage structure that identify portions of the storage structure that have not changed during operation of the thread between the first and second idle conditions; and

maintaining, for use in the reference structure, those associations from the stored reference structure that correspond to locations in the storage structure that have not changed during operation of the thread between the first and second idle conditions.

13. The method of claim 1 wherein:

the storage structure associated with the thread is a stack;

the step of detecting general memory references comprises the steps of traversing the stack associated with the thread to identify all stack cells in the stack that reference storage locations of objects in the general memory area; and

the step of maintaining the reference structure comprises the step of creating an association to the general memory area in the reference structure for each storage location of an object in the general memory area that is referenced by at least one stack cell in the stack; and

the step of operating a memory management technique comprises the step of performing a garbage collection technique to deallocate memory used by objects in the general memory area using the associations in the reference structure to identify objects in the general memory area that are in use by the thread so as to not deallocate the identified objects.

14. The method of claim 13 wherein steps of detecting, maintaining and operating a memory management technique are performed for a plurality of threads that have an associated idle condition, and wherein the reference structure contains associations to the general memory area for detected general memory references from the plurality of threads.

15. The method of claim 14 comprising the steps of:

detecting that a thread from the plurality of threads is to transition from the associated idle condition to a non-idle condition; and

in response to the step of detecting that the thread is to transition from an idle condition to a non-idle condition, updating each detected general memory reference in the storage structure associated with the thread based on any modifications made, during operation of the memory management technique, to the associations to the general memory area in the reference structure that correspond to the detected general memory references for that thread that is to transition from the associated idle condition to a non-idle condition.

16. The method of claim 13 wherein the reference structure is a multi-dimensional data structure including indexed association storage areas, and wherein the step of maintaining the reference structure comprises the steps of:

identifying an indexed association storage area in which to store an association to the general memory area based on an address of the object in the general memory area that is referenced by at least one stack cell in the stack; and

storing the association to the general memory area at the indexed association storage area identified in the step of identifying.

17. The method of claim 16 wherein the step of performing garbage collection on the general memory area further comprises the step of:

updating the reference structure to account for modifications made, during performance of the memory management technique, to storage locations of objects in the general memory area, the step of updating using the address of the object in the general memory area to access a proper indexed association storage area in the reference structure without having to search, within the reference structure, indexed association storage areas unrelated to the address of the object.

18. The method of claim 13 wherein at least one association in the reference structure is associated with an object in the general memory area on behalf of at least two stack cells in the stack.

19. The method of claim 1 wherein the step of operating a memory management technique comprises the step of performing a garbage collection technique without requiring access to the storage structure associated with the thread.

20. The method of claim 1 wherein:

there are a plurality of threads and wherein each thread is a Java thread associated with an Java execution environment;

the storage structure associated with each thread is a stack structure and wherein the general memory area is a heap structure used by the Java execution environment to maintain objects on behalf of each Java thread;

the detected general memory references are object references from the stack structure to the heap structure for objects referenced by the Java thread; and

wherein the memory management technique is a garbage collection technique that uses the reference structure to identify objects in the heap that are in use by threads so as not to deallocate areas of the heap related to those identified objects.

21. A computerized device comprising:

a processor;

a memory encoded with a storage structure, a reference structure and a general memory area;

an interconnection mechanism coupling the memory and the processor; and

wherein the processor operates an execution environment to perform a memory management technique by performing the steps of;

detecting, within the storage structure associated with a thread, general memory references that reference storage locations in a general memory area, the storage structure utilized by the thread during operation of the thread in the computerized device;

maintaining the reference structure containing an association to the general memory area for each detected general memory reference within the storage structure; and

operating a memory management technique on the general memory area for locations in the general memory area other than those for which an association to the general memory area is maintained in the reference structure.

22. The computerized device of claim 21 wherein the processor operates the execution environment to perform the steps of:

identifying an idle condition associated with the thread;

in response to identifying the idle condition, performing the steps of detecting, maintaining and operating a memory management technique.

23. The computerized device of claim 22 wherein:

wherein when the processor performs the step of operating a memory management technique, the processor performs the steps of;

modifying the general memory area to deallocate storage locations in the general memory area for use by threads, the deallocated storage locations being storage locations other than storage locations related to the associations to the general memory area maintained in the reference structure;

updating the reference structure to account for modifications, made to storage locations in the general memory area during operation of the memory management technique, that relate to the associations to the general memory area maintained in the reference structure; and

wherein the processor further performs the steps of;

detecting that the thread is to transition from the idle condition to a non-idle condition; and

in response to the step of detecting that the thread is to transition from an idle condition to a non-idle condition, updating each detected general memory reference in the storage structure associated with the thread based on any updates made to the associations to the general memory area in the reference structure that correspond to the detected general memory references.

24. The computerized device of claim 22 wherein when the processor performs the step of identifying a first idle condition associated with the thread the processor performs the step of:

detecting that the thread has not been operated by the computerized device during a performance of the memory management technique.

25. The computerized device of claim 22 wherein when the processor performs the step of identifying a first idle condition associated with the thread the processor performs the step of:

detecting an inactivity period of the thread in the computerized device that indicates the thread has not been operated in the computerized device for a predetermined period of time.

26. The computerized device of claim 21 wherein when the processor performs the step of operating a memory management technique on the general memory area the processor performs the step of:

performing garbage collection on the general memory area for storage locations in the general memory area other than storage locations related to the associations to the general memory area maintained in the reference structure.

27. The computerized device of claim 26 wherein when the processor performs the step of performing garbage collection on the general memory area the processor performs the step of:

modifying the general memory area to deallocate storage locations in the general memory area for use by threads, the deallocated storage locations being storage locations other than storage locations related to the associations to the general memory area maintained in the reference structure.

28. The computerized device of claim 27 wherein the reference structure is a root array reference structure and wherein the association to the general memory area maintained for each detected general memory reference is copy of the contents of the detected general memory reference from the storage structure;

and

wherein when the processor performs the step of performing garbage collection on the general memory area further the processor performs the step of;

updating the root array reference structure to account for modifications made to storage locations in the general memory area, made during performance of the memory management technique, that relate to the associations to the general memory area maintained in the reference structure.

29. The computerized device of claim 28 wherein the processor performs the step of:

detecting that the thread is to transition from an idle condition to a non-idle condition; and

in response to the step of detecting that the thread is to transition from an idle condition to a non-idle condition, updating each detected general memory reference in the storage structure associated with the thread based on any updates made to the associations to the general memory area in the root array reference structure that correspond to the detected general memory references.

30. The computerized device of claim 27 wherein:

the reference structure is a summary reference structure; and

the association to the general memory area maintained for each detected general memory reference is a pointer to at least one location in the storage structure that contains the detected general memory references; and

wherein the processor performs the step of;

in response to modifying the general memory area, updating the storage structure associated with the thread to account for modifications made to storage locations in the general memory area, made during performance of the memory management technique, that relate to the associations to the general memory area maintained in the summary reference structure.

31. The computerized device of claim 21 wherein the processor performs the steps of:

identifying a first idle condition associated with the thread;

in response to identifying the idle condition, performing the steps of detecting, maintaining and operating the memory management technique;

storing the reference structure during operation of the thread in the computerized device;

detecting a second idle condition associated with the thread;

in response to detecting the second idle condition;

identifying at least a portion of the stored reference structure that contains associations to the general memory area that have not changed during the operation of the thread in the computerized device;

repeating the step of detecting, within a storage structure associated with a thread, general memory references that reference storage locations in a general memory area for portions of the storage structure that have changed during the operation of the thread in the computerized device; and

repeating the step of maintaining the reference structure containing an association to the general memory area for each detected general memory reference within the storage structure for those detected general memory references located in those portions of the storage structure that have changed during the operation of the thread in the computerized device, such that associations corresponding to the general memory references detected in the repeated step of maintaining are added to the reference structure.

32. The computerized device of claim 21 wherein when the processor performs the step of identifying at least a portion of the stored reference structure that contains associations to the general memory area that have not changed during the operation of the thread in the computerized device the processor performs the steps of:

examining the storage structure associated with the thread to detect predetermined storage locations in the storage structure that identify portions of the storage structure that have not changed during operation of the thread between the first and second idle conditions; and

maintaining, for use in the reference structure, those associations from the stored reference structure that correspond to locations in the storage structure that have not changed during operation of the thread between the first and second idle conditions.

33. The computerized device of claim 21 wherein:

the storage structure associated with the thread is a stack;

wherein when the processor performs the step of detecting general memory references, the processor performs the step of traversing the stack associated with the thread to identify all stack cells in the stack that reference storage locations of objects in the general memory area; and

wherein when the processor performs the step of maintaining the reference structure, the processor performs the step of creating an association to the general memory area in the reference structure for each storage location of an object in the general memory area that is referenced by at least one stack cell in the stack; and

wherein when the processor performs the step of operating a memory management technique, the processor performs the step of performing a garbage collection technique to deallocate memory used by objects in the general memory area using the associations in the reference structure to identify objects in the general memory area that are in use by the thread so as to not deallocate the identified objects.

34. The computerized device of claim 33 wherein steps of detecting, maintaining and operating a memory management technique are performed by the processor for a plurality of threads that have an associated idle condition, and wherein the reference structure contains associations to the general memory area for detected general memory references from the plurality of threads.

35. The computerized device of claim 34 wherein the processor performs the steps of:

detecting that a thread from the plurality of threads is to transition from the associated idle condition to a non-idle condition; and

in response to the step of detecting that the thread is to transition from an idle condition to a non-idle condition, updating each detected general memory reference in the storage structure associated with the thread based on any modifications made, during operation of the memory management technique, to the associations to the general memory area in the reference structure that correspond to the detected general memory references for that thread that is to transition from the associated idle condition to a non-idle condition.

36. The computerized device of claim 33 wherein the reference structure is a multi-dimensional data structure including indexed association storage areas, and wherein when the processor performs the step of maintaining the reference structure, the processor performs the steps of:

identifying an indexed association storage area in which to store an association to the general memory area based on an address of the object in the general memory area that is referenced by at least one stack cell in the stack; and

storing the association to the general memory area at the indexed association storage area identified in the step of identifying.

37. The computerized device of claim 36 wherein when the processor performs the step of performing garbage collection on the general memory area further, the processor performs the step of:

updating the reference structure to account for modifications made, during performance of the memory management technique, to storage locations of objects in the general memory area, the step of updating using the address of the object in the general memory area to access a proper indexed association storage area in the reference structure without having to search, within the reference structure, indexed association storage areas unrelated to the address of the object.

38. The computerized device of claim 33 wherein at least one association in the reference structure is associated with an object in the general memory area on behalf of at least two stack cells in the stack.

39. The computerized device of claim 21 wherein when the processor performs the step of operating a memory management technique, the processor performs the step of performing a garbage collection technique without requiring access to the storage structure associated with the thread.

40. The computerized device of claim 21 wherein:

there are a plurality of threads and wherein each thread is a Java thread associated with a Java execution environment;

the storage structure associated with each thread is a stack structure and wherein the general memory area is a heap structure used by the Java execution environment to maintain objects on behalf of each Java thread;

the detected general memory references are object references from the stack structure to the heap structure for objects referenced by the Java thread; and

wherein the memory management technique is a garbage collection technique that uses the reference structure to identify objects in the heap that are in use by threads so as not to deallocate areas of the heap related to those identified objects.

41. A computer program product having a computer-readable medium including computer program logic encoded thereon that, when performed in a computer device having a coupling of a memory and a processor, programs the processor to perform a memory management technique by performing the operations of:

detecting, within the storage structure associated with a thread, general memory references that reference storage locations in a general memory area, the storage structure utilized by the thread during operation of the thread in the computerized device;

maintaining the reference structure containing an association to the general memory area for each detected general memory reference within the storage structure; and

operating a memory management technique on the general memory area for locations in the general memory area other than those for which an association to the general memory area is maintained in the reference structure.