Method and apparatus for optimizing exact garbage collection using a bifurcated data structure

• US 5,900,001 A
• Filed: 04/23/1997
• Issued: 05/04/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: Wolczko, Mario I., Ungar, David M.
• Primary Examiner(s): AMSBURY, WAYNE P
• Application Number:
  US08/842,195
• Time in Patent Office: 741 Days
• Field of Search: 707/103, 707/206
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0276 Generational garbage collection
• CPC Class Codes: G06F 16/289 Object oriented databases
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

Apparatus, methods, systems and computer program products are disclosed describing a data structure and associated processes that optimize garbage collection techniques. The disclosed data structure can be used as an instantiated object in an object-oriented programming environment. The data structure uses a data structure header to separate the portion of the data structure that contains pointer values from the portion of the data structure that contains non-pointer values. The contents of the first word of the data structure header is distinguishable from any pointer value. Thus, a garbage collection procedure can more rapidly locate the pointer values in the data structure. Another advantage of this data structure organization, when applied to instantiated objects, is that the position of an instance variable (with respect to the object header structure) remains constant for all instantiated objects including those based on subclasses of the original class.

Claims

1. A computer controlled method for locating a pointer value within a data structure that includes a header structure, wherein said method comprises steps of:

(a) constructing said data structure whereby a pointer memory area is separated from a data value memory area by said header structure, said pointer memory area including a pointer variable containing said pointer value, said header structure containing a header value distinguishable from said pointer value and adjacent to said pointer memory area;

(b) scanning said pointer memory area to locate said pointer value; and

(c) advancing past said header structure and said data value memory area upon detection of said header value.

2. The computer controlled method of claim 1 wherein said data structure is a first instantiated object data structure, said pointer variable is a pointer instance variable and said header structure is an object header structure.

3. The computer controlled method of claim 2 wherein said object header structure is associated with a size field, said first instantiated object data structure is followed by a second instantiated object data structure in a contiguously addressable region of memory, and step (c) comprises steps of:

(c1) determining an advance value from said size field; and

(c2) advancing to said second instantiated object data structure by using said advance value.

4. The computer controlled method of claim 2 wherein said pointer value points to a second instantiated object data structure and step (c) comprises following said pointer value to said second instantiated object data structure.

5. The computer controlled method of claim 2 wherein said first instantiated object data structure is derived from a base-class that defines an instance variable in said first instantiated object data structure to be at an offset from said object header structure, and wherein a second instantiated object data structure based on a subclass of said base-class also defines said instance variable in said second instantiated object data structure to also be at said offset.

6. An apparatus having a central processing unit (CPU) and a memory coupled to said CPU, for locating a pointer value within a data structure in said memory, said data structure including a header structure, wherein said apparatus comprises:

a construction mechanism configured to construct said data structure in said memory, said data structure comprising a pointer memory area separated from a data value memory area by said header structure, said pointer memory area including a pointer instance variable containing said pointer value, said header structure containing a header value distinguishable from said pointer value and adjacent to said pointer memory area;

a scanning mechanism configured to scan said pointer memory area to locate said pointer value;

a header detection mechanism configured to detect said header value during the operation of the scanning mechanism; and

an advance mechanism configured to advance past said header structure and said data value memory area dependent on the header detection mechanism.

7. The apparatus of claim 6 wherein said data structure is a first instantiated object data structure, said pointer variable is a pointer instance variable and said header structure is an object header structure.

8. The apparatus of claim 7 wherein said object header structure is associated with a size field, said first instantiated object data structure is followed by a second instantiated object data structure in a contiguously addressable region of memory, and the advance mechanism comprises:

a determination mechanism configured to determine an advance value from said size field; and

an advance past object mechanism configured to advance to said second instantiated object data structure by using said advance value.

9. The apparatus of claim 7 wherein said pointer value points to a second instantiated object data structure and the advance mechanism comprises a pointer following mechanism configured to follow said pointer value to said second instantiated object data structure.

10. The apparatus of claim 7 wherein said first instantiated object data structure is derived from a base-class that defines an instance variable in said first instantiated object data structure to be at an offset from said object header structure, and wherein a second instantiated object data structure based on a subclass of said base-class also defines said instance variable in said second instantiated object data structure to also be at said offset.

11. A computer system having a central processing unit (CPU) and a memory coupled to said CPU, for locating a pointer value within a data structure in said memory, said data structure including a header structure, wherein said computer system comprises:

a construction mechanism configured to construct said data structure in said memory, said data structure comprising a pointer memory area separated from a data value memory area by said header structure, said pointer memory area including a pointer variable containing said pointer value, said header structure containing a header value distinguishable from said pointer value and adjacent to said pointer memory area;

a scanning mechanism configured to scan said pointer memory area to locate said pointer value;

a header detection mechanism configured to detect said header value during the operation of the scanning mechanism; and

an advance mechanism configured to advance past said header structure and said data value memory area dependent on the header detection mechanism.

12. The computer controlled system of claim 11 wherein said data structure is a first instantiated object data structure, said pointer variable is a pointer instance variable and said header structure is an object header structure.

13. The system of claim 12 wherein said object header structure is associated with a size field, said first instantiated object data structure is followed by a second instantiated object data structure in a contiguously addressable region of memory, and the advance mechanism comprises:

a determination mechanism configured to determine an advance value from said size field; and

an advance past object mechanism configured to advance to said second instantiated object data structure by using said advance value.

14. The system of claim 12 wherein said pointer value points to a second instantiated object data structure and the advance mechanism comprises a pointer following mechanism configured to follow said pointer value to said second instantiated object data structure.

15. The system of claim 12 wherein said first instantiated object data structure is derived from a base-class that defines an instance variable in said first instantiated object data structure to be at an offset from said object header structure, and wherein a second instantiated object data structure based on a subclass of said base-class also defines said instance variable in said second instantiated object data structure to also be at said offset.

16. A computer program product comprising:

a computer usable storage medium having computer readable code embodied therein for causing a computer to locate a pointer value within a data structure in said memory, said data structure including a header structure;

said computer readable code comprising;

computer readable program code devices configured to cause said computer to effect a construction mechanism configured to construct said data structure in said memory, said data structure comprising a pointer memory area separated from a data value memory area by said header structure, said pointer memory area including a pointer variable containing said pointer value, said header structure containing a header value distinguishable from said pointer value and adjacent to said pointer memory area;

computer readable program code devices configured to cause said computer to effect a scanning mechanism configured to scan said pointer memory area to locate said pointer value;

computer readable program code devices configured to cause said computer to effect a header detection mechanism configured to detect said header value during the operation of the scanning mechanism; and

computer readable program code devices configured to cause said computer to effect an advance mechanism configured to advance past said header structure and said data value memory area dependent on the header detection mechanism.

17. The computer program product of claim 16 wherein said data structure is a first instantiated object data structure, said pointer variable is a pointer instance variable and said header structure is an object header structure.

18. The computer program product of claim 17 wherein said object header structure is associated with a size field, said first instantiated object data structure is followed by a second instantiated object data structure in a contiguously addressable region of memory, and the advance mechanism comprises:

computer readable program code devices configured to cause said computer to effect a determination mechanism configured to determine an advance value from said size field; and

computer readable program code devices configured to cause said computer to effect an advance past object mechanism configured to advance to said second instantiated object data structure by using said advance value.

19. The computer program product of claim 17 wherein said pointer value points to a second instantiated object data structure and the advance mechanism comprises a pointer following mechanism configured to follow said pointer value to said second instantiated object data structure.

20. The computer program product of claim 17 wherein said first instantiated object data structure is derived from a base-class that defines an instance variable in said first instantiated object data structure to be at an offset from said object header structure, and wherein a second instantiated object data structure based on a subclass of said base-class also defines said instance variable in said second instantiated object data structure to also be at said offset.

21. A memory containing an instantiated object data structure wherein said memory comprises:

a pointer memory area containing a pointer instance variable for storing a pointer value;

a data value memory area for storing a non-pointer value; and

an object header structure containing a header value distinguishable from said pointer value and adjacent to said pointer memory area the object header structure separating the pointer memory area and the data value memory area.