Generation isolation system and method for garbage collection

• US 6,098,089 A
• Filed: 04/23/1997
• Issued: 08/01/2000
• 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: Vishin, Sanjay, Tremblay, Marc, O'Connor, James Michael
• Primary Examiner(s): Oberley, Alvin E.
• Assistant Examiner(s): Fourson, Gary Scott
• Application Number:
  US08/841,543
• Time in Patent Office: 1,196 Days
• Field of Search: 707/206, 707/103, 707/104, 711/132, 711/170, 711/200, 711/203, 711/206, 711/208, 711/221, 709/1, 395/704
• US Class Current: 718/104
• CPC Class Codes: G06F 12/0276 Generational garbage collection
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

Architectural support for generation isolation is provided through trapping of intergenerational pointer stores. Identification of pointer stores as intergenerational is performed by a store barrier responsive to an intergenerational pointer store trap matrix that is programmably encoded with store target object and store pointer data generation pairs to be trapped. The write barrier and intergenerational pointer store trap matrix provide a programmably-flexible definition of generation pairs to be trapped, affording a garbage collector implementer with support for a wide variety of generational garbage collection methods, including remembered set-based methods, card-marking type methods, write barrier based copying collector methods, etc., as well as combinations thereof and combinations including train algorithm type methods to managing mature portions of a generationally collected memory space. Pointer specific store instruction replacement allows implementations in accordance with this invention to provide an exact barrier to not only pointer stores, but to the specific intergenerational pointer stores of interest to a particular garbage collection method or combination of methods.

Claims

1. An apparatus comprising:

dynamically allocated storage wherein references to objects formed therein have generation membership tags associated therewith;

an intergenerational pointer store trap matrix including elements corresponding to store target object and store reference data generation pairs, wherein individual of said elements indicate whether said barrier should trap pointer stores of corresponding store reference data to a corresponding store target object; and

a write barrier to intergenerational pointer stores, wherein said write barrier traps a store instruction in response to selected correspondences between respective generation membership tags of a target object reference and of object reference data being stored into a target object identified by said target object reference, said selected correspondences encoded by said intergenerational pointer store trap matrix.

2. An apparatus, as recited in claim 1, wherein said write barrier comprises logic responsive to a write barrier vector register encoding said intergenerational pointer store trap matrix and responsive to object references respectively encoding said generation membership tags of a target object reference and of object reference data, said logic providing a generation membership tag-oriented lookup into said write barrier vector register.

3. An apparatus, as recited in claim 1,

wherein said generation membership tags comprise maskable portions of said target object reference and of said object reference data;

and

wherein said write barrier comprises logic responsive to states of said maskable portions and of a write barrier vector register encoding said intergenerational pointer store trap matrix.

4. An apparatus, as recited in claim 1, wherein said write barrier comprises a pointer store specific hardware write barrier, pointer store specificity thereof being provided by replacement of pointer non-specific store instructions with pointer-specific store instructions in accordance with execution-time resolution of a store target field type of said pointer non-specific store instructions.

5. An apparatus, as recited in claim 1, wherein said write barrier comprises logic responsive to said generation tags associated with said target object reference and said object reference data and to a write barrier vector register encoding said intergenerational pointer store trap matrix.

6. An apparatus, as recited in claim 1,

wherein said dynamically allocated storage comprises a heap represented in memory;

and

wherein generations of said objects are represented in contiguous regions of said memory.

7. An apparatus, as recited in claim 1,

wherein said dynamically allocated storage comprises a heap represented in memory;

wherein generations of said objects are represented in not necessarily contiguous regions of said memory; and

wherein said references to said objects include an addressing portion and a maskable generation tag portion, said write barrier being responsive to said maskable generation tag portion.

8. An apparatus, as recited in claim 1, embodied in a hardware processor.

9. An apparatus, as recited in claim 1, embodied as a computer software program product including instructions executable on a hardware processor and encoded in a computer readable medium.

10. An apparatus, as recited in claim 9, wherein said computer readable medium is selected from a set comprising a disk medium, a CD-ROM medium, an addressable memory medium, and a network communication medium.

11. An apparatus, as recited in claim 1, further comprising:

a virtual machine instruction processor including a representation of said intergenerational pointer store trap matrix;

wherein said write barrier comprises pointer specific store instruction codes executable on said virtual machine instruction processor; and

wherein execution of said pointer specific store instruction codes includes determining, based on generation tags respectively associated with said target object reference and said object reference data, whether a particular execution of one of said pointer specific store instructions will store an intergenerational pointer indicated as for trapping by said intergenerational pointer store trap matrix, and, if so, trapping to a garbage collection fault handler.

12. An apparatus, as recited in claim 11, wherein said virtual machine instruction processor includes a hardware processor to directly execute at least a subset of virtual machine instructions executable thereby.

13. An apparatus, as recited in claim 11,

wherein said virtual machine instruction processor includes a hardware processor to directly execute at least a subset of virtual machine instructions executable thereby;

and

wherein said hardware processor includes logic responsive to a write barrier vector register encoding said intergenerational pointer store trap matrix and responsive to object references respectively encoding said generation membership tags of a target object reference and of object reference data, said logic effectively implementing a generation membership tag oriented lookup into said write barrier vector register.

14. An apparatus, as recited in claim 11,

wherein said virtual machine instruction processor includes an interpreter executable on a hardware processor;

and

wherein said intergenerational pointer store trap matrix is represented in storage accessible to said hardware processor.

15. An apparatus, as recited in claim 11,

wherein said virtual machine instruction processor includes a just-in-time compiler executable on a hardware processor;

and

wherein said intergenerational pointer store trap matrix is represented in storage accessible to said hardware processor.

16. An apparatus, as recited in claim 11, wherein said virtual machine instruction processor dynamically replaces pointer non-specific store instruction codes with said pointer specific store instruction codes in accordance with first execution time resolution of data type, thereby restricting said write barrier to pointer stores, said intergenerational pointer store trap matrix further restricting traps by said write barrier to intergenerational pointer stores.

17. An apparatus, as recited in claim 1, further comprising:

a virtual machine instruction processor including an implementation of said write barrier and a representation of said intergenerational pointer store trap matrix;

a fault handler including instructions executable by said virtual machine instruction processor, wherein said write barrier triggers said fault handler coincident with execution of a store instruction having a target object and store data such that said store instruction stores an intergenerational pointer.

18. An apparatus, as recited in claim 17, wherein said instructions of said fault handler include instructions for storing to a remembered set.

19. An apparatus, as recited in claim 17,

further comprising a generational collector process of instructions executable by said virtual machine instruction processor;

and

wherein said fault handler includes instructions executable by said virtual machine instruction processor for storing information identifying trapped store data to a remembered set representation for use by said generational collector process.

20. An apparatus, as recited in claim 1, wherein said target object reference and said object reference data each reference object structures in said dynamically allocated storage, said object structures including method and instance variable representations.

21. An apparatus, as recited in claim 1, wherein said target object reference and said object reference data are each pointers to literal data represented in dynamically allocated storage.

22. An apparatus, as recited in claim 1, further comprising a hardware processor including a register representation of said intergenerational pointer store trap matrix and an execution unit having a logic circuit for evaluating said selected correspondences.

23. An apparatus, as recited in claim 1, further comprising a software virtual machine instruction processor program executable on a hardware processor, said software virtual machine instruction processor program defining computer readable storage for representing said intergenerational pointer store trap matrix and including program instructions for evaluating said selected correspondences.

24. A method for trapping intergenerational pointer stores comprising:

forming an intergenerational pointer store trap matrix in computer readable storage, the intergenerational pointer store trap matrix including elements corresponding to store target object and store reference data generation pairs, wherein individual of said elements indicate whether said barrier should trap pointer stores of corresponding store reference data to a corresponding store target object;

indexing into said intergenerational pointer store trap matrix using generation membership tags respectively associated with a target object reference and object reference data being stored thereinto by a mutator process store operation; and

selectively trapping based on upon a trap indication encoded at an element of said intergenerational pointer store trap matrix so indexed.

25. A method, as recited in claim 24, further comprising:

completing said mutator process store operation without trapping based upon a no trap indication encoded at said indexed element.

26. A method, as recited in claim 24, wherein handling of said trapping includes:

storing a remembered set entry corresponding to said mutator process store operation.

27. A method, as recited in claim 24, wherein handling of said trapping includes:

emulating said mutator process store operation.

28. A method, as recited in claim 24, further comprising:

selectively transforming pointer non-specific mutator store operation instructions into pointer specific instructions based on an execution-time determination of store target field type; and

performing said indexing into said intergenerational pointer store trap matrix for substantially only said pointer specific instructions.

29. A method, as recited in claim 24, embodied in operations of a hardware processor.

30. A method, as recited in claim 24, embodied as a computer software program product including instructions executable on a hardware processor and encoded in a computer readable medium.

31. A method, as recited in claim 30, wherein said computer readable medium is selected from a set comprising a disk medium, a CD-ROM medium, an addressable memory medium, and a network communication medium.