US6317869B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method of run-time tracking of object references in Java programs
Assignee: Intel Corp
•
Filing: 2000-06-02
•
Granted: 2001-11-13
•
Expires: 2020-06-02
Abstract
Abstract Many programming languages utilize reference pointers in computer code. Furthermore, some of these programming languages perform memory management in the form of garbage collection. Once such language is Java. During the execution of a garbage collection routine, the computer may need to locate all the variables containing reference values. The present invention introduces a method for run-time tracking of object references in computer code and determining which variables contain references to objects at garbage collection sites. The method of the present invention first creates a bit vector in memory. The bit vector is then initialized. Second, each variable declared in the computer program that may be used to store a reference value is assigned a unique bit within this bit vector. Each bit is maintained to indicate whether the variable it is assigned to is currently storing a reference value. Specifically, when a variable is assigned a reference value, the corresponding bit in the bit vector is set. When a variable is assigned a non-reference value, the corresponding bit in the bit vector is cleared.
Inventors
- 👤 Ali-Reza Adl-Tabatabai
- 👤 Guei-Yuan Lueh
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 09:45
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/44; G06F9/455; G06F9/45504; G06F9/45516; G06F12/00; G06F12/02; G06F12/0223; G06F12/023; G06F12/0253; Y; Y10; Y10S; Y10S707/00; Y10S707/99951; Y10S707/99952; Y10S707/99953; Y10S707/99956; Y10S707/99957
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
42 words
A method of run-time tracking of object references in computer code comprising: assigning a bit within a bit vector for an ambiguously typed variable; and maintaining said bit dynamically during code execution to indicate whether said variable is assigned a reference value.
Claim 2
Independent Claim
42 words
A method of run-time tracking of object references in computer code comprising: assigning a bit within a bit vector for an ambiguously typed variable; and maintaining said bit dynamically during code execution to indicate whether said variable is assigned a reference value.
Claim 3
Dependent Claim
21 words
The method of claim 1 further comprising scanning said bit vector to determine if any ambiguously typed variables contain reference values.
Claim 4
Dependent Claim
13 words
The method of claim 1 further comprising freeing space used by dead objects.
Claim 5
Dependent Claim
11 words
The method of claim 1 further comprising initializing said bit vector.
Claim 6
Dependent Claim
23 words
The method of claim 4 wherein initializing comprises setting a corresponding bit in said bit vector for a variable containing a reference value.
Claim 7
Dependent Claim
23 words
The method of claim 4 wherein initializing comprises clearing a corresponding bit in said bit vector for a variable containing a non-reference value.
Claim 8
Dependent Claim
31 words
The method of claim 1 wherein maintaining said bit to indicate whether said variable is assigned a reference value comprises setting said bit when said variable is assigned a reference value.
Claim 9
Dependent Claim
31 words
The method of claim 1 wherein maintaining said bit to indicate whether said variable is assigned a reference value comprises clearing said bit when said variable is assigned a non-reference value.
Claim 10
Dependent Claim
13 words
The method of claim 1 further comprising computing a set of live objects.
Claim 11
Dependent Claim
35 words
The method of claim 9 wherein computing a set of live object comprises: examining global variables, registers, and a run-time stack; and locating all references that can be reached from said set of live objects.
Claim 12
Dependent Claim
16 words
The method of claim 10 wherein locating all references comprises traversing a graph of reachable objects.
Claim 13
Independent Claim
54 words
A method of garbage collection comprising: maintaining a bit dynamically within a bit vector to indicate whether an ambiguously typed variable is assigned a reference value; scanning said bit vector to determine if said variable contains a reference value; and including said variable in a root set if said variable contains a reference value.
Claim 14
Independent Claim
54 words
A method of garbage collection comprising: maintaining a bit dynamically within a bit vector to indicate whether an ambiguously typed variable is assigned a reference value; scanning said bit vector to determine if said variable contains a reference value; and including said variable in a root set if said variable contains a reference value.
Claim 15
Dependent Claim
20 words
The method of claim 12 further comprising traversing said root set to find reachable objects in a first memory region.
Claim 16
Dependent Claim
13 words
The method of claim 12 further comprising reclaiming space occupied by dead objects.
Claim 17
Dependent Claim
17 words
The method of claim 12 further comprising allocating space in a second memory region for reachable objects.
Claim 18
Dependent Claim
17 words
The method of claim 15 further comprising copying contents of reachable objects to said second memory region.
Claim 19
Dependent Claim
29 words
The method of claim 16 further comprising updating memory references pointing to reachable objects in said first memory region to refer to reachable objects in said second memory region.
Claim 20
Dependent Claim
62 words
A computer readable medium having embodied thereon a computer program, the computer program being executable by a machine to perform a method of run-time tracking of object references in computer code comprising: assigning a bit within a bit vector for an ambiguously typed variable; and maintaining said bit dynamically during code execution to indicate whether said variable is assigned a reference value.
Claim 21
Dependent Claim
62 words
A computer readable medium having embodied thereon a computer program, the computer program being executable by a machine to perform a method of run-time tracking of object references in computer code comprising: assigning a bit within a bit vector for an ambiguously typed variable; and maintaining said bit dynamically during code execution to indicate whether said variable is assigned a reference value.
Claim 22
Dependent Claim
32 words
The method of claim 18 further comprising: creating a root set; traversing said root set to find reachable objects in a first memory region; and freeing memory space occupied by dead objects.
Claim 23
Dependent Claim
35 words
The method of claim 19 wherein creating a root set comprises scanning said bit vector to determine which ambiguously typed variables contain reference values and including said variables containing reference values into said root set.
References Cited (Backward Citations)
US5787287A
Cited
US5890169A
Cited
US5845298A
Cited
US5848423A
Cited
US5893121A
Cited
US5903899A
Cited
US5909579A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-11-12 | 2005-05-14 | 2005-11-13 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-11-12 | 2009-05-14 | 2009-11-13 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-11-12 | 2013-05-14 | 2013-11-13 | $7700.00 | Window Closed / Lapsed |