Write barrier system and method including pointer-specific instruction variant replacement mechanism

• US 5,953,736 A
• Filed: 04/23/1997
• Issued: 09/14/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: Vishin, Sanjay, Tremblay, Marc, O'Connor, James Michael
• Primary Examiner(s): Cabeca, John W.
• Assistant Examiner(s): Namazi, Mehdi
• Application Number:
  US08/841,508
• Time in Patent Office: 874 Days
• Field of Search: 711/6, 711/165, 395/507, 395/570, 707/201, 707/206, 707/103
• US Class Current: 711/6
• CPC Class Codes: G06F 12/0276 Generational garbage collection
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

A pointer-specific instruction variant replacement mechanism facilitates an exact write barrier, i.e., a write barrier specific to pointer stores and transparent to non-pointer stores. Pointer store specific instruction replacement allows some implementations to provide an exact barrier specific to the particular set of intergenerational pointer stores that are of interest to a particular garbage collection method or combination of methods. The exact identification of pointer stores herein does not require tags encoded in-line with collected memory storage and does not require non-standard word sizes to support such tags. In one embodiment, a non-quick to quick translator cache provides pointer specific store instruction replacement. In another, self modifying code provides pointer specific store instruction replacement. An exemplary write barrier provided in accordance with the pointer-specific instruction variant replacement mechanism of this invention affords a garbage collector implementer with support for a wide variety of garbage collection methods, including remembered set-based methods, card-marking type methods, write barrier based copying collector methods, mark-sweep methods, etc., as well as combinations thereof and combinations including train algorithm type methods to managing mature portions of a generationally collected memory space. Such a write barrier can eliminate non-pointer stores from the set of stores that are evaluated against, for example, an intergenerational pointer store trap matrix or a garbage collection page mask to determine whether or not to trap. Such a write barrier can also eliminate entries associated with non-pointer stores from remembered set or card table stores for collection time scanning of modified portions of a collected generational space.

Claims

1. An apparatus comprising:

a virtual machine instruction processor, wherein executable instructions include program occurrences of a store instruction;

an instruction replacement component of said virtual machine instruction processor, wherein said instruction replacement component detects said store instruction and selectively replaces a particular program occurrence of said store instruction with a pointer-specific store instruction if a store target field of said particular program occurrence resolves to a pointer-type field; and

a write barrier provided by execution of said pointer-specific store instruction on said virtual machine instruction processor.

2. An apparatus, as recited in claim 1,

wherein said instruction replacement component includes a translator cache coupled into an instruction path of said virtual machine instruction processor,

wherein resolution of said store target field is triggered by said translator cache in response to a program occurrence identifier no match indication;

wherein said translator cache caches a pointer-specific variant of said store instruction and associates said program occurrence identifier therewith if said resolution indicates that said store target field is of type reference.

3. An apparatus, as recited in claim 2,

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

and

wherein said translator cache is coupled between an instruction decoder and an execution unit of said hardware processor.

4. An apparatus, as recited in claim 1, wherein said instruction replacement component replaces said particular program occurrence of said store instruction by modifying an in-memory image of said particular program occurrence of said store instruction.

5. An apparatus, as recited in claim 1,

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

and

wherein said write barrier includes a logic circuit responsive to a garbage collection configuration register of said hardware processor, said logic circuit employed by said hardware processor to filter garbage collection traps of said pointer-specific store instruction.

6. An apparatus, as recited in claim 1, wherein said virtual machine instruction processor includes a software program executable on a hardware processor, and wherein said store instruction and said pointer-specific store instruction are executable by said software program.

7. An apparatus, as recited in claim 6,

wherein said software program defines garbage collection configuration storage accessible thereto;

and

wherein said execution of said pointer-specific store instruction includes evaluation of hardware processor instructions implementing a logic equation to filter garbage collection traps of said pointer-specific store instruction in accordance with contents of said garbage collection configuration storage.

8. An apparatus, as recited in claim 6, wherein said software program includes an interpreter for said virtual machine instructions.

9. An apparatus, as recited in claim 6, wherein said software program includes a just-in-time compiler for incrementally compiling said virtual machine instructions to said hardware processor instructions.

10. An apparatus, as recited in claim 1, wherein said store instruction is a JAVA virtual machine bytecode.

11. An apparatus, as recited in claim 1,

wherein said store instruction is a non-quick bytecode having a first quick variant;

and

wherein said pointer-specific instruction is said first quick variant.

12. An apparatus, as recited in claim 5, wherein said garbage configuration register includes an intergenerational pointer store trap matrix representation having elements corresponding to store target object and store reference data generation pairs, such that one of said elements indicates whether said write barrier should trap execution of a particular program occurrence of said pointer-specific store instruction given generation tags associated with store reference data and a store target object thereof.

13. An apparatus, as recited in claim 1,

wherein said virtual machine instruction processor includes a representation of a garbage collection configuration store;

and

wherein said execution of said pointer specific store instruction includes determining whether a particular program occurrence of said pointer-specific store instruction will store a boundary crossing pointer indicated as for trapping by said garbage collection configuration store, and, if so, trapping to a garbage collection fault handler.

14. An apparatus, as recited in claim 13,

wherein said boundary crossing pointer is an intergenerational pointer;

and

wherein said garbage collection configuration store includes an intergenerational pointer store trap matrix representation.

15. An apparatus, as recited in claim 13,

wherein said boundary crossing pointer is a garbage collection page boundary crossing pointer;

and

wherein said garbage collection configuration store includes a garbage collection page mask representation.

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

a fault handler responsive to said write barrier.

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

18. An apparatus, as recited in claim 16, wherein said fault handler includes instructions for storing to a card table.

19. An apparatus, as recited in claim 16,

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 data structure for use by said generational collector process.

20. A method for filtering pointer stores, said method comprising:

detecting a first program occurrence of a store instruction; and

selectively replacing said first program occurrence of said store instruction with a pointer-specific store instruction based on resolution of store target field type information for said first program occurrence of said store instruction;

executing said pointer-specific store instruction; and

selectively trapping said executing in accordance with contents of said garbage collection configuration store.

21. A method, as recited in claim 20,

wherein said contents are first contents and said garbage collection configuration store programmably encodes a write barrier to selected intergenerational pointer stores.

22. A method, as recited in claim 20,

wherein said contents are second contents and said garbage collection configuration store programmably encodes a write barrier to garbage collection page boundary crossing pointer stores.

23. A method, as recited in claim 20,

wherein said store instruction is a non-quick bytecode having a first quick variant thereof;

and

wherein said pointer-specific store instruction is said first quick variant.

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

executing a non pointer store instruction corresponding to a second program occurrence of said store instruction, wherein execution of said non pointer store instruction does not include selective trapping in accordance with contents of said garbage collection configuration store.

25. A method, as recited in claim 24,

wherein said store instruction is a non-quick bytecode having first and second quick variants thereof;

wherein said pointer-specific store instruction is said first quick variant; and

wherein said non pointer store instruction is said second quick variant.

26. A method, as recited in claim 20, further comprising:

responsive to said selective trapping, executing a trap handler.

27. A method, as recited in claim 20, further comprising:

responsive to said selective trapping, storing information identifying a store instruction target object in a remembered set.

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

responsive to said selective trapping, storing information indicative of a store instruction target object in a card table.

29. A method, as recited in claim 20, wherein said detecting includes matching a program counter value associated with said first program occurrence of said store instruction with a stored program counter value.

30. A method, as recited in claim 20, wherein said selectively replacing includes modifying an in-memory image of said particular program occurrence of said store instruction.

31. A method, as recited in claim 20, wherein said selectively replacing includes:

performing a lookup in an instruction translator cache using a unique identifier for said first program occurrence of said store instruction; and

if said unique identifier matches a first entry of said instruction translator cache, substituting said pointer-specific store instruction associated therewith.

32. A method, as recited in claim 31, wherein said selectively replacing further includes:

if said unique identifier matches a second entry of instruction translator cache, substituting a non-pointer store instruction associated therewith, wherein execution of said non-pointer store instruction does not include selective trapping in accordance with contents of said garbage collection configuration store.

33. A method, as recited in claim 31, wherein said selectively replacing further includes:

if said unique identifier does not match any entry of said instruction translator cache, resolving type information for a store target field of said first program occurrence of said store instruction;

storing results of said resolving in said instruction translator cache and retrying said lookup performing and said substituting.

34. A method, as recited in claim 20, further comprising:

resolving type information for a store target field of said first program occurrence of said store instruction.

35. A method, as recited in claim 20, wherein said resolution includes

retrieving a data set associated with said store target field, said data set including said store target field type information.

36. A method, as recited in claim 20, wherein said resolution includes retrieving information, including said store target field type information, from a constant pool table associated with a store target object of said first program occurrence of said store instruction, said constant pool table including a constant pool field associated with said store target field.

37. A method, as recited in claim 20, wherein said resolution includes:

retrieving a data set associated with said store target field, said data set including store target field type information; and

storing said pointer-specific store instruction and information from said data set in an instruction translator cache.

38. A method for filtering mutator process pointer stores in a virtual machine instruction processor, said method comprising:

selectively transforming a program occurrence of a pointer non-specific mutator store instruction into one of a pointer-specific variant and a non-pointer variant thereof, said transforming based on an execution-time determination of store target field type of said pointer non-specific mutator store; and

trapping substantially only said pointer-specific variant based on correspondence between operands thereof and contents of a garbage collection configuration store.

39. A method, as recited in claim 38, further comprising:

subsequent to said transforming and for said transformed program occurrence only, executing said pointer-specific variant in lieu of said pointer non-specific mutator store instruction.

40. Architectural support for selectively trapping pointer stores in a virtual machine instruction processor having mutator and garbage collector processes executable thereon, said architectural support comprising:

a garbage collection configuration store;

instruction replacement means operably coupled into an instruction path of said virtual machine instruction processor to replace a pointer non-specific instruction with a quick variant thereof based on resolution of target field type for said pointer non-specific instruction, said quick variant being a pointer specific quick variant if said target field type is reference type;

a write barrier provided by execution of said pointer specific quick variant on said virtual machine instruction processor, said write barrier responsive to said garbage collection configuration store.