Method and apparatus for referencing nodes using links

• US 5,915,255 A
• Filed: 04/23/1997
• Issued: 06/22/1999
• Est. Priority Date: 04/23/1997
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Schwartz, David C., Wolczko, Mario I.
• Primary Examiner(s): AMSBURY, WAYNE P
• Application Number:
  US08/842,196
• Time in Patent Office: 790 Days
• Field of Search: 707/206
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0276 Generational garbage collection
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

Apparatus, methods, systems, and computer program products are disclosed that use a link to access nodes in a generational garbage collected heap. The creation area of the heap is associated with a validation variable that is dependent on the number of scavenge operations performed on the creation area. The link comprises the value of the validation variable when the node was allocated and the index of the created node within the creation area. When the node is copied from the creation area an entry is made in a link-to-pointer translation table. Accesses to the node using the link succeed regardless of whether the node is in the creation area. Thus, not all references to the node need to be updated when the node is copied from the creation area allowing the copying process to be interrupted when resolving links to the copied node.

Claims

1. A computer controlled method for specifying a node originally allocated within a link-referenced creation area of a generational garbage collected heap subject to a plurality of scavenge operations, wherein said method comprises steps of:

(a) maintaining a current validation variable for said link-referenced creation area, said current validation variable containing an area validation value depending on said plurality of scavenge operations; and

(b) accessing a node through a link containing an offset value into said link-referenced creation area and a link validation value.

2. The computer controlled method of claim 1 wherein the method further comprises steps of:

(c) allocating said node from said generational garbage collected heap; and

(d) constructing said link to contain said offset value and said link validation value, said link validation value provided from said current validation variable, and said offset value being an offset into said link-referenced creation area of said node.

3. The computer controlled method of claim 2 wherein step (b) comprises:

(b1) using said offset value in said link for accessing said node in said link-referenced creation area if said link validation value in said link is the same as said area validation value.

4. The computer controlled method of claim 1 further comprising steps of:

(c) copying said node from said link-referenced creation area to a copied node in a pointer-referenced heap area, said copied node referenced by a node pointer; and

(d) constructing a link-to-pointer translation table for associating said link with said node pointer.

5. The computer controlled method of claim 4 wherein step (b) comprises:

(b1) using said offset value and said link validation value in said link along with said link-to-pointer translation table for accessing said node outside of said link-referenced creation area if said link validation value in said link is not the same as said area validation value.

6. The computer controlled method of claim 1 wherein said method further comprises:

(c) maintaining said link to said node after said node becomes a garbage node whereby said garbage node is referenced through said link without impacting any of said plurality of scavenge operations on said garbage node.

7. A computer system having a central processing unit (CPU) and a memory coupled to said CPU, for specifying a node originally allocated within a link-referenced creation area of a generational garbage collected heap subject to a plurality of scavenge operations, said computer system comprising:

a validation variable maintenance mechanism configured to maintain a current validation variable for said link-referenced creation area, said current validation variable containing an area validation value dependent on said plurality of scavenge operations; and

a node access mechanism configured to access a node through a link containing an offset value into said link-referenced creation area and a link validation value, said link validation value originally obtained from said current validation variable.

8. The computer system of claim 7 further comprising:

a node allocation mechanism configured to allocate said node from said generational garbage collected heap; and

a link construction mechanism configured to construct said link from said offset value and said link validation value, said link validation value copied from said area validation value, and said offset value being an offset into said link-referenced creation area.

9. The computer system of claim 8 with the node access mechanism further comprising:

a creation area access mechanism configured to use said offset value in said link to access said node in said link-referenced creation area if said link validation value in said link is the same as said area validation value.

10. The computer system of claim 7 further comprising:

a node copying mechanism configured to copy said node from said link-referenced creation area to a copied node in a pointer-referenced heap area, said copied node referenced by a node pointer; and

a table construction mechanism configured to construct a link-to-pointer translation table to associate said link with said node pointer.

11. The computer system of claim 10 with the node access mechanism further comprising:

a copied node access mechanism configured to use said offset value and said link validation value in said link along with said link-to-pointer translation table to access said node outside of said link-referenced creation area if said link validation value in said link is not the same as said area validation value.

12. The computer system of claim 7 further comprising:

a maintenance mechanism configured to maintain said link to said node after said node becomes a garbage node whereby said garbage node is referenced through said link without impacting any of said plurality of scavenge operations on said garbage node.

13. An apparatus having a central processing unit (CPU) and a memory coupled to said CPU, for specifying a node originally allocated within a link-referenced creation area of a generational garbage collected heap subject to a plurality of scavenge operations, said apparatus comprising:

a validation variable maintenance mechanism configured to maintain a current validation variable for said link-referenced creation area, said current validation variable containing an area validation value dependent on said plurality of scavenge operations; and

a node access mechanism configured to access a node through a link containing an offset value into said link-referenced creation area and a link validation value, said link validation value originally obtained from said current validation variable.

14. The apparatus of claim 13 further comprising:

a node allocation mechanism configured to allocate said node from said generational garbage collected heap; and

a link construction mechanism configured to construct said link to contain said offset value and said link validation value, said link validation value copied from said area validation value, and said offset value being an offset into said link-referenced creation area.

15. The apparatus of claim 14 with the node access mechanism further comprising:

a creation area access mechanism configured to use said offset value in said link to access said node in said link-referenced creation area if said link validation value in said link is the same as said area validation value.

16. The apparatus of claim 13 further comprising:

a node copying mechanism configured to copy said node from said link-referenced creation area to a copied node in a pointer-referenced heap area, said copied node referenced by a node pointer; and

a table construction mechanism configured to construct a link-to-pointer translation table to associate said link with said node pointer.

17. The apparatus of claim 16 with the node access mechanism further comprising:

a copied node access mechanism configured to use said offset value and said link validation value in said link along with said link-to-pointer translation table to access said node outside of said link-referenced creation area if said link validation value in said link is not the same as said area validation value.

18. The apparatus of claim 13 further comprising:

a maintenance mechanism configured to maintain said link to said node after said node becomes a garbage node whereby said garbage node is referenced through said link without impacting any of said plurality of scavenge operations on said garbage node.

19. A computer program product comprising:

a computer usable storage medium having computer readable code embodied therein for causing a computer to specify a node originally allocated within a link-referenced creation area of a generational garbage collected heap subject to a plurality of scavenge operations, said computer readable code comprising;

computer readable program code devices configured to cause said computer to effect a validation variable maintenance mechanism configured to maintain a current validation variable for said link-referenced creation area, said current validation variable containing an area validation value dependent on said plurality of scavenge operations; and

computer readable program code devices configured to cause said computer to effect a node access mechanism configured to access a node through a link containing an offset value into said link-referenced creation area and a link validation value, said link validation value originally obtained from said current validation variable.

20. The computer program product of claim 19 further comprising:

computer readable program code devices configured to cause said computer to effect a node allocation mechanism configured to allocate said node from said generational garbage collected heap; and

computer readable program code devices configured to cause said computer to effect a link construction mechanism configured to construct said link to contain said offset value and said link validation value, said link validation value copied from said area validation value, and said offset value being an offset into said link-referenced creation area.

21. The computer program product of claim 20 with the node access mechanism further comprising:

computer readable program code devices configured to cause said computer to effect a creation area access mechanism configured to use said offset value in said link to access said node in said link-referenced creation area if said link validation value in said link is the same as said area validation value.

22. The computer program product of claim 19 further comprising:

computer readable program code devices configured to cause said computer to effect a node copying mechanism configured to copy said node from said link-referenced creation area to a copied node in a pointer-referenced heap area, said copied node referenced by a node pointer; and

computer readable program code devices configured to cause said computer to effect a table construction mechanism configured to construct a link-to-pointer translation table to associate said link with said node pointer.

23. The computer program product of claim 22 with the node access mechanism further comprising:

computer readable program code devices configured to cause said computer to effect a copied node access mechanism configured to use said offset value and said link validation value in said link along with said link-to-pointer translation table to access said node outside of said link-referenced creation area if said link validation value in said link is not the same as said area validation value.

24. The computer program product of claim 19 further comprising:

computer readable program code devices configured to cause said computer to effect a maintenance mechanism configured to maintain said link to said node after said node becomes a garbage node whereby said garbage node is referenced through said link without impacting any of said plurality of scavenge operations on said garbage node.