US5930807A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Apparatus and method for fast filtering read and write barrier operations in garbage collection system
Assignee: Oracle America Inc
•
Filing: 1997-04-23
•
Granted: 1999-07-27
•
Expires: 2017-04-23
Abstract
Abstract In a computer system that utilizes write or read barriers to perform a garbage collection function, instruction execution logic avoids unnecessary calls to the write or read barrier procedure. Each object's header includes a State flag. Each object reference also includes a State flag. Each time an instruction that is the subject of a write or read barrier (e.g., a object reference write instruction) is executed, the State flag of the object reference being processed is inspected by the instruction execution logic. If the State flag in the object reference is set, the write or read barrier procedure is not invoked, because the target object has already been processed by a previous call to the write or read barrier procedure. Otherwise the write or read barrier procedure is invoked. The write or read barrier procedure first checks the State flag in the target object's header. If it is set, the State flag in the target object reference is set and then the procedure exits. Otherwise, if the State flag in the target object header is not set, a predefined garbage collection function is performed and then the State flag in the target object's header and the State flag in the target object's reference are both set. In some embodiments the setting of the State flags is conditional on the outcome of the garbage collection operation performed by the write or read barrier procedure.
Inventors
- 👤 Zahir Ebrahim
- 👤 Sanjay Vishin
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 19:37
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/0223; G06F12/023; G06F12/0253; G06F12/0269; G06F12/0276; Y; Y10; Y10S; Y10S707/00; Y10S707/99951; Y10S707/99956; Y10S707/99957
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
162 words
A method of reducing execution write/read barrier procedures in a computer system, comprising the steps of: (A) storing in a computer memory objects and object references for accessing the objects, each object reference including a State flag; (B) executing instructions stored in the computer memory, a subset of the executed instructions having associated therewith a write/read barrier procedure; wherein each instruction in the subset processes an object reference to a respective one of the objects stored in the computer memory; (C) when executing each instruction that has an associated write/read barrier procedure, (C1) determining whether the State flag of the object reference being processed is set to a first predefined value; (C2) when the determination in step C1 is positive, skipping execution of the write/read barrier procedure associated with the instruction being executed and proceeding with execution of a next instruction; and (C3) when the determination in step C1 is negative, executing the write/read barrier procedure associated with the instruction being executed.
Claim 2
Independent Claim
162 words
A method of reducing execution write/read barrier procedures in a computer system, comprising the steps of: (A) storing in a computer memory objects and object references for accessing the objects, each object reference including a State flag; (B) executing instructions stored in the computer memory, a subset of the executed instructions having associated therewith a write/read barrier procedure; wherein each instruction in the subset processes an object reference to a respective one of the objects stored in the computer memory; (C) when executing each instruction that has an associated write/read barrier procedure, (C1) determining whether the State flag of the object reference being processed is set to a first predefined value; (C2) when the determination in step C1 is positive, skipping execution of the write/read barrier procedure associated with the instruction being executed and proceeding with execution of a next instruction; and (C3) when the determination in step C1 is negative, executing the write/read barrier procedure associated with the instruction being executed.
Claim 3
Dependent Claim
25 words
The method of claim 1, wherein step C3 further includes setting to the first predefined value the State flag in the object reference being processed.
Claim 4
Dependent Claim
29 words
The method of claim 2, wherein the steps of the method are performed by instruction execution logic, without execution of any instructions other than the object reference accessing instruction.
Claim 5
Dependent Claim
39 words
The method of claim 1, wherein step C3 further includes conditionally setting to the first predefined value the State flag in the object reference being processed when predefined criteria with respect to the object reference being processed are satisfied.
Claim 6
Dependent Claim
31 words
The method of claim 1, wherein the subset of the executed instructions having associated therewith a write/read barrier procedure are object reference write instructions having associated therewith a write barrier procedure.
Claim 7
Dependent Claim
99 words
The method of claim 1, each object stored in the computer memory having an object header with a State flag therein; the step of executing the write/read barrier procedure, in step C3, including: (C3A) accessing the object header of the respective object referenced by the object reference being processed and determining whether the State flag in the respective object's header is set to the first predefined value; and (C3B) when the determination in step C3A is positive, exiting the write/read barrier procedure; (C3C) when the determination in step C3A is negative, continuing with execution of the write/read barrier procedure.
Claim 8
Dependent Claim
31 words
The method of claim 6, wherein step C3B includes setting the State flag in the object reference being processed to the first predefined value prior to exiting the write/read barrier procedure.
Claim 9
Dependent Claim
33 words
The method of claim 6, wherein step C3C includes setting to the first predefined value the State flag in the object reference being processed and the State flag in the respective object's header.
Claim 10
Independent Claim
142 words
A method of executing an object reference write bytecode in a computer program in a computer system using generational garbage collection and a remembered set to store pointers to objects that may store references to other objects, comprising the steps of: (A) executing an object reference write bytecode by writing a specified object reference into a specified field of a target object identified by a target object reference; (B) testing a State flag in the target object reference to determine whether the State flag is set or clear; (C) when the testing step determines that the State flag in the target object reference is clear, invoking a predefined write barrier procedure to perform a predefined write barrier operation; (D) when the testing step determines that the State flag in the target object reference is set, proceeding with execution of a next bytecode.
Claim 11
Independent Claim
142 words
A method of executing an object reference write bytecode in a computer program in a computer system using generational garbage collection and a remembered set to store pointers to objects that may store references to other objects, comprising the steps of: (A) executing an object reference write bytecode by writing a specified object reference into a specified field of a target object identified by a target object reference; (B) testing a State flag in the target object reference to determine whether the State flag is set or clear; (C) when the testing step determines that the State flag in the target object reference is clear, invoking a predefined write barrier procedure to perform a predefined write barrier operation; (D) when the testing step determines that the State flag in the target object reference is set, proceeding with execution of a next bytecode.
Claim 12
Dependent Claim
29 words
The method of claim 9, wherein the steps of the method are performed by instruction execution logic, without execution of any bytecodes other than the object reference write bytecode.
Claim 13
Dependent Claim
133 words
The method of claim 9, further including executing the invoked write barrier procedure by: (E) testing a header State flag in a header of the target object to determine whether the header State flag is set or clear; (F) when the testing step determines that the header State flag in the target object reference is clear, adding a reference to the target object to a predefined remembered set data structure, and setting the header State flag and the State flag in the target object reference; (G) when the testing step determines that the header State flag in the target object reference is set, setting the State flag in the target object reference and exiting the write barrier procedure without adding a reference to the target object to the predefined remembered set data structure.
Claim 14
Dependent Claim
168 words
A computer system that include a garbage collection mechanism, comprising: a memory for storing objects and object references for accessing the objects, each object reference including a State flag; and a data processor for executing instructions stored in the computer memory, a subset of the executed instructions having associated therewith a write/read barrier procedure; wherein each instruction in the subset processes an object reference that references a respective one of the objects stored in the computer memory; the data processor including instruction execution logic that, when executing each instruction that has an associated write/read barrier procedure, (C1) determines whether the State flag of the object reference being processed is set to a first predefined value; (C2) when the State flag value determination is positive, skips execution of the write/read barrier procedure associated with the instruction being executed and proceeds with execution of a next instruction; and (C3) when the State flag value determination is negative, invokes execution of the write/read barrier procedure associated with the instruction being executed.
Claim 15
Dependent Claim
168 words
A computer system that include a garbage collection mechanism, comprising: a memory for storing objects and object references for accessing the objects, each object reference including a State flag; and a data processor for executing instructions stored in the computer memory, a subset of the executed instructions having associated therewith a write/read barrier procedure; wherein each instruction in the subset processes an object reference that references a respective one of the objects stored in the computer memory; the data processor including instruction execution logic that, when executing each instruction that has an associated write/read barrier procedure, (C1) determines whether the State flag of the object reference being processed is set to a first predefined value; (C2) when the State flag value determination is positive, skips execution of the write/read barrier procedure associated with the instruction being executed and proceeds with execution of a next instruction; and (C3) when the State flag value determination is negative, invokes execution of the write/read barrier procedure associated with the instruction being executed.
Claim 16
Dependent Claim
37 words
The computer system of claim 12, wherein the instruction execution logic includes logic for setting the State flag in the object reference being processed to the first predefined value when the State flag value determination is negative.
Claim 17
Dependent Claim
52 words
The computer system of claim 12, wherein the instruction execution logic includes logic for conditionally setting the State flag in the object reference being processed to the first predefined value when the State flag value determination is negative and when predefined criteria with respect to the object reference being processed are satisfied.
Claim 18
Dependent Claim
32 words
The computer system of claim 12, wherein the subset of the executed instructions having associated therewith a write/read barrier procedure are object reference write instructions having associated therewith a write barrier procedure.
Claim 19
Dependent Claim
97 words
The computer system of claim 12, each object stored in the computer memory having an object header with a State flag therein; the write/read barrier procedure including instructions for: (C3A) accessing the object header of the respective object referenced by the object reference being processed and determining whether the State flag in the respective object's header is set to the first predefined value; and (C3B) when the determination by the C3A instructions is positive, exiting the write/read barrier procedure; (C3C) when the determination by the C3A instructions is negative, continuing with execution of the write/read barrier procedure.
Claim 20
Dependent Claim
35 words
The computer system of claim 16, wherein the C3B instructions include instructions for setting the State flag in the object reference being processed to the first predefined value prior to exiting the write/read barrier procedure.
Claim 21
Dependent Claim
38 words
The computer system method of claim 6, wherein the C3C instructions include instructions for setting to the first predefined value the State flag in the object reference being processed and the State flag in the respective object's header.
Claim 22
Dependent Claim
169 words
A computer system that includes a generational garbage collection mechanism, comprising: a memory for storing objects, object references for accessing the objects, and a predefined remembered set data structure, the predefined remembered set data structure storing a list of object references, each object reference including a State flag; and a data processor for executing bytecode instructions, including object reference write bytecode instructions for writing a datum into a specified field of a target object identified by a target object reference; the object reference write bytecode instructions having associated therewith a write barrier procedure; the data processor including instruction execution logic that, when executing each object reference write bytecode instruction: (C1) determines whether the State flag of the target object reference is set to a first predefined value; (C2) when the State flag value determination is positive, skips execution of the write barrier procedure and proceeds with execution of a next bytecode instruction; and (C3) when the State flag value determination is negative, invokes execution of the write barrier procedure.
Claim 23
Dependent Claim
169 words
A computer system that includes a generational garbage collection mechanism, comprising: a memory for storing objects, object references for accessing the objects, and a predefined remembered set data structure, the predefined remembered set data structure storing a list of object references, each object reference including a State flag; and a data processor for executing bytecode instructions, including object reference write bytecode instructions for writing a datum into a specified field of a target object identified by a target object reference; the object reference write bytecode instructions having associated therewith a write barrier procedure; the data processor including instruction execution logic that, when executing each object reference write bytecode instruction: (C1) determines whether the State flag of the target object reference is set to a first predefined value; (C2) when the State flag value determination is positive, skips execution of the write barrier procedure and proceeds with execution of a next bytecode instruction; and (C3) when the State flag value determination is negative, invokes execution of the write barrier procedure.
Claim 24
Dependent Claim
139 words
The computer system of claim 19, each object stored in the computer memory having an object header with a State flag therein; the write barrier procedure including instructions for: (C3A) testing a header State flag in a header of the target object to determine whether the header State flag is set to the first predefined value; (C3B) when the State flag determination by the C3A instructions is negative, adding a reference to the target object to the predefined remembered set data structure, and setting the header State flag and the State flag in the target object reference; (C3C) when the State flag determination by the C3A instructions is positive, setting the State flag in the target object reference and exiting the write barrier procedure without adding a reference to the target object to the predefined remembered set data structure.
References Cited (Backward Citations)
US4757438A
Cited
US4920483A
Cited
US5222221A
Cited
US4961134A
Cited
US4907151A
Cited
US5088036A
Cited
US5301288A
Cited
US5283878A
Cited
US5293614A
Cited
US5535329A
Cited
US5355483A
Cited
US5418921A
Cited
US5561786A
Cited
US5560003A
Cited
US5408650A
Cited
US5446901A
Cited
US5566321A
Cited
US5761670A
Cited
US5845298A
Cited
US5848423A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-07-26 | 2003-01-25 | 2003-07-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-07-26 | 2007-01-25 | 2007-07-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-07-26 | 2011-01-25 | 2011-07-27 | $7700.00 | Window Closed / Lapsed |