# US 2003/0229766 A1 · Methods and apparatus for performing a memory management technique

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2003/0229766 A1
- Document ID: US20030229766A1
- Status: Published application
- Kind: A1
- Application number: 10/163,677
- Filed: 2002-06-06
- Published: 2003-12-11
- Earliest claimed: 2002-06-06
- Assignees: Sun Microsystems, Inc.
- Inventors: David Dice; Alexander T. Garthwaite
- Web page: https://patentgrep.com/patent/US20030229766A1

## CPC

- G06F 12/0269: {Incremental or concurrent garbage collection, e.g. in real-time systems (G06F12/0261 takes precedence)}
- G06F 12/0261: {using reference counting}
- Y10S 707/99953: Recoverability
- Y10S 707/99956: File allocation
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- Y10S: TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS

## 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

### Claim 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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 2)

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.

### Claim 4 (depends on 2)

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.

### Claim 5 (depends on 2)

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.

### Claim 6 (depends on 1)

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.

### Claim 7 (depends on 6)

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.

### Claim 8 (depends on 7)

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.

### Claim 9 (depends on 8)

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.

### Claim 10 (depends on 7)

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.

### Claim 11 (depends on 1)

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.

### Claim 12 (depends on 11)

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.

### Claim 13 (depends on 1)

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.

### Claim 14 (depends on 13)

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.

### Claim 15 (depends on 14)

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.

### Claim 16 (depends on 13)

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.

### Claim 17 (depends on 16)

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.

### Claim 18 (depends on 13)

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.

### Claim 19 (depends on 1)

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.

### Claim 20 (depends on 1)

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.

### Claim 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.

### Claim 22 (depends on 21)

The computerized 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.

### Claim 23 (depends on 22)

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.

### Claim 24 (depends on 22)

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.

### Claim 25 (depends on 22)

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.

### Claim 26 (depends on 21)

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.

### Claim 27 (depends on 26)

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.

### Claim 28 (depends on 27)

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.

### Claim 29 (depends on 28)

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.

### Claim 30 (depends on 27)

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.

### Claim 31 (depends on 21)

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.

### Claim 32 (depends on 21)

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.

### Claim 33 (depends on 21)

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.

### Claim 34 (depends on 33)

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.

### Claim 35 (depends on 34)

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.

### Claim 36 (depends on 33)

The computerized device of claim 33 wherein the reference structure is a multidimensional 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.

### Claim 37 (depends on 36)

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.

### Claim 38 (depends on 33)

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.

### Claim 39 (depends on 21)

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.

### Claim 40 (depends on 1)

The computerized device 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.

### Claim 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.
