US5845298A — Write barrier system and method for trapping garb…

Claim 1

Independent Claim 89 words

An apparatus comprising: dynamically allocable storage wherein objects formed therein are accessible via respective object references thereto; a programmably-defined garbage collection page mask; a write barrier to garbage collection page boundary crossing pointer stores, wherein said write barrier traps a store instruction if respective selected portions of first and second pointers associated therewith differ, said first pointer referring to said store instruction's target object and said second pointer being object reference data for storage thereinto, said respective selected portions defined by contents of said programmably-defined garbage collection page mask.

Claim 2

Independent Claim 89 words

An apparatus comprising: dynamically allocable storage wherein objects formed therein are accessible via respective object references thereto; a programmably-defined garbage collection page mask; a write barrier to garbage collection page boundary crossing pointer stores, wherein said write barrier traps a store instruction if respective selected portions of first and second pointers associated therewith differ, said first pointer referring to said store instruction's target object and said second pointer being object reference data for storage thereinto, said respective selected portions defined by contents of said programmably-defined garbage collection page mask.

Claim 3

Dependent Claim 20 words

An apparatus, as recited in claim 1, wherein said programmably-defined garbage collection page mask defines a garbage collection page size.

Claim 4

Dependent Claim 36 words

An apparatus, as recited in claim 1, wherein said programmably-defined garbage collection page mask defines a bitwise comparison window for comparison of said respective selected portions of said target object reference and said object reference data.

Claim 5

Dependent Claim 84 words

An apparatus, as recited in claim 1, wherein said first and said second pointers each include a most significant portion, a least significant portion, and a middle portion therebetween; and wherein said programmably-defined garbage collection page mask defines a programmably-definable middle portion of a composite mask having a most significant portion defined to pass said most significant portions of said first and said second pointers, such that an unmasked portion of said upper and said middle portions is compared for trapping said store operation.

Claim 6

Dependent Claim 30 words

An apparatus, as recited in claim 1, wherein said write barrier comprises mask and comparison logic responsive to a garbage collection page register field encoding said garbage collection page mask.

Claim 7

Dependent Claim 53 words

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.

Claim 8

Dependent Claim 100 words

An apparatus, as recited in claim 1, further comprising a virtual machine instruction processor including a representation of said programmably-defined garbage collection page mask; 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 a bitwise comparison of respective masked portions of said target object reference and said object reference data, whether a particular execution of one of said pointer-specific store instructions will store a garbage collection page boundary crossing pointer and, if so, trapping to a garbage collection fault handler.

Claim 9

Dependent Claim 30 words

An apparatus, as recited in claim 7, wherein said virtual machine instruction processor includes a hardware processor and at least a subset of virtual machine instructions are directly executable thereby.

Claim 10

Dependent Claim 39 words

An apparatus, as recited in claim 7, wherein said virtual machine instruction processor includes an interpreted implementation thereof executable on a hardware processor; and wherein said garbage collection page mask is represented in storage accessible to said hardware processor.

Claim 11

Dependent Claim 40 words

An apparatus, as recited in claim 7, wherein said virtual machine instruction processor includes a just-in-time compiler implementation thereof executable on a hardware processor; and wherein said garbage collection page mask is represented in storage accessible to said hardware processor.

Claim 12

Dependent Claim 65 words

An apparatus, as recited in claim 7, wherein said virtual machine instruction processor dynamically replaces pointer non-specific store instruction codes with said pointer-specific store instruction codes in accordance with an execution time resolution of data type, thereby restricting said write barrier to pointer stores, said programmably-defined garbage collection page mask further restricting traps by said write barrier to garbage collection page boundary crossing pointer stores.

Claim 13

Dependent Claim 81 words

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 programmably-defined garbage collection page mask; 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 execution of said store instruction stores a garbage collection page boundary crossing pointer store.

Claim 14

Dependent Claim 22 words

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

Claim 15

Dependent Claim 55 words

An apparatus, as recited in claim 12, 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.

Claim 16

Dependent Claim 50 words

An apparatus, as recited in claim 1, further comprising a hardware processor including a register representation of said programmably-defined garbage collection page mask and an execution unit having a logic circuit for masking and comparing said respective selected portions of said target object reference and of said object reference data.

Claim 17

Dependent Claim 63 words

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 programmably-defined garbage collection page mask and including program instructions for masking and comparing said respective selected portions of said target object reference and of said object reference data.

Claim 18

Independent Claim 115 words

A method for trapping garbage collection page boundary crossing pointer stores, said method comprising: forming a garbage collection page mask in computer readable storage; masking first and second pointers associated with a particular execution of a pointer-specific store instruction, said first pointer being said pointer-specific store instruction's target object reference and said second pointer being said pointer-specific store instruction's object reference data, said masking based on contents of said garbage collection page mask; comparing respective unmasked portions of said first and second pointers to determine whether said first and second pointers each refer to respective storage on a same garbage collection page; and triggering a trap handler based on a mismatch result of said comparing.

Claim 19

Independent Claim 115 words

A method for trapping garbage collection page boundary crossing pointer stores, said method comprising: forming a garbage collection page mask in computer readable storage; masking first and second pointers associated with a particular execution of a pointer-specific store instruction, said first pointer being said pointer-specific store instruction's target object reference and said second pointer being said pointer-specific store instruction's object reference data, said masking based on contents of said garbage collection page mask; comparing respective unmasked portions of said first and second pointers to determine whether said first and second pointers each refer to respective storage on a same garbage collection page; and triggering a trap handler based on a mismatch result of said comparing.

Claim 20

Dependent Claim 28 words

A method, as recited in claim 17, further comprising: completing said particular execution of said pointer-specific store instruction without trapping based on a match result of said comparing.

Claim 21

Dependent Claim 25 words

A method, as recited in claim 17, wherein operation of said trap handler includes: storing a remembered set entry corresponding to said pointer-specific store instruction.

Claim 22

Dependent Claim 19 words

A method, as recited in claim 17, wherein operation of said trap handler includes: emulating said pointer-specific store instruction.

Claim 23

Dependent Claim 49 words

A method, as recited in claim 17, further comprising: selectively transforming program occurrences of pointer non-specific instructions into pointer-specific instructions, such as said pointer-specific instruction, based on an execution-time determination of store target field type; and performing said masking and said comparing for substantially only said pointer specific instructions.

Claim 24

Dependent Claim 115 words

Architectural support for trapping garbage collection page boundary crossing pointer stores in a virtual machine instruction processor having mutator and garbage collector processes executable thereon, said architectural support comprising: a programmably-defined garbage collection page mask; and write barrier means responsive to said programmably-defined garbage collection page mask, evaluation of a store instruction of said mutator process triggering a garbage collection fault handler if (1) said store instruction resolves to a pointer store and (2) a target memory object of said store instruction and a memory object identified by object reference data of said store both reside in a same garbage collection page, garbage collection page boundaries being defined by said programmably-defined garbage collection page mask.

Claim 25

Dependent Claim 115 words

Architectural support for trapping garbage collection page boundary crossing pointer stores in a virtual machine instruction processor having mutator and garbage collector processes executable thereon, said architectural support comprising: a programmably-defined garbage collection page mask; and write barrier means responsive to said programmably-defined garbage collection page mask, evaluation of a store instruction of said mutator process triggering a garbage collection fault handler if (1) said store instruction resolves to a pointer store and (2) a target memory object of said store instruction and a memory object identified by object reference data of said store both reside in a same garbage collection page, garbage collection page boundaries being defined by said programmably-defined garbage collection page mask.

Claim 26

Dependent Claim 44 words

Architectural support for trapping garbage collection page boundary crossing pointer stores, as recited in claim 22, wherein said write barrier means includes a pointer-specific store instruction executable by a virtual machine instruction processor, said pointer-specific store instruction restricting said write barrier to pointer stores.

Claim 27

Dependent Claim 29 words

Architectural support for trapping garbage collection page boundary crossing pointer stores, as recited in claim 23, wherein said pointer-specific store instruction is a quick variant of a non-quick bytecode.

Claim 28

Dependent Claim 94 words

Architectural support for trapping garbage collection page boundary crossing pointer stores, as recited in claim 22, wherein said write barrier means includes a logic circuit, said logic circuit effectively masking portions of first and second pointers associated with a particular execution of said store instruction and bitwise comparing unmasked portions of said first and second pointers, said first pointer identifying said target memory object of said store instruction and said second pointer being said data of said store instruction, said logic circuit triggering a trap handler based on a difference result of said comparing.

Claim 29

Dependent Claim 63 words

Architectural support for trapping garbage collection page boundary crossing pointer stores, as recited in claim 22, wherein said write barrier means 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 nonspecific store instructions.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2001-11-30	2002-06-01	2002-12-01	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2005-11-30	2006-06-01	2006-12-01	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2009-11-30	2010-06-01	2010-12-01	$7700.00	Window Closed / Lapsed

Write barrier system and method for trapping garbage collection page boundary crossing pointer stores

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag