US5873104A — Bounded-pause time garbage collection system and …

Claim 1

Independent Claim 106 words

An apparatus comprising: memory storage, wherein objects formed therein are relocatable from respective FromSpace instances to respective ToSpace instances thereof; a partially relocated object identifier store updatable to identify a FromSpace instance and a ToSpace instance of a particular one of said objects, if any, for which relocation is incomplete; and a write barrier to a store-oriented memory access targeting either of said FromSpace and said ToSpace instances of said particular object, wherein said write barrier maintains consistency between said ToSpace instance and at least a copied portion of said FromSpace instance, and wherein said write barrier allows incremental update of pointers to said particular object.

Claim 2

Independent Claim 106 words

An apparatus comprising: memory storage, wherein objects formed therein are relocatable from respective FromSpace instances to respective ToSpace instances thereof; a partially relocated object identifier store updatable to identify a FromSpace instance and a ToSpace instance of a particular one of said objects, if any, for which relocation is incomplete; and a write barrier to a store-oriented memory access targeting either of said FromSpace and said ToSpace instances of said particular object, wherein said write barrier maintains consistency between said ToSpace instance and at least a copied portion of said FromSpace instance, and wherein said write barrier allows incremental update of pointers to said particular object.

Claim 3

Dependent Claim 34 words

An apparatus, as recited in claim 1, wherein said write barrier is responsive to a correspondence between an object identifier for said store-oriented memory access and contents of said partially relocated object identifier store.

Claim 4

Dependent Claim 50 words

An apparatus, as recited in claim 1, wherein said write barrier broadcasts store data for said store-oriented memory access to both said FromSpace and said ToSpace instances in response to a correspondence between an object identifier for said store-oriented memory access and contents of said partially relocated object identifier store.

Claim 5

Dependent Claim 45 words

An apparatus, as recited in claim 3, wherein said write barrier selectively forgoes broadcasting store data if said store-oriented memory access targets an uncopied portion of said FromSpace instance, and instead directs said store data to said FromSpace instance and not to said ToSpace instance.

Claim 6

Dependent Claim 83 words

An apparatus, as recited in claim 1, wherein said partially relocated object identifier store comprises a FROM field to identify said FromSpace instance and a TO field to identify said ToSpace instance; wherein said write barrier comprises write barrier logic coupled into a store path of a hardware processor to said memory storage, said write barrier logic being responsive to a correspondence between an object identifier for said store-oriented memory access and contents of either of said FROM field and said TO field.

Claim 7

Dependent Claim 36 words

An apparatus, as recited in claim 5, wherein said write barrier logic supplies store data for said store-oriented memory access to both said FromSpace and said ToSpace instances of said particular object, thereby maintaining said consistency.

Claim 8

Dependent Claim 54 words

An apparatus, as recited in claim 5, wherein said write barrier logic supplies store data for said store-oriented memory access to said FromSpace instance and, if a portion of said particular object targeted by said store-oriented memory access has been copied to said ToSpace instance, also to said ToSpace instance, thereby maintaining said consistency.

Claim 9

Dependent Claim 76 words

An apparatus, as recited in claim 1, further comprising a partial copy position indicator to discriminate between said copied portion and an uncopied portion of said FromSpace instance; wherein said write barrier broadcasts a second store-oriented memory access targeting said copied portion to both of said FromSpace and said ToSpace instances; and wherein said write barrier directs a third store-oriented memory access targeting said uncopied portion to said FromSpace instance and not to said ToSpace instance.

Claim 10

Dependent Claim 90 words

An apparatus, as recited in claim 1, further comprising a partial copy position indicator to discriminate between said copied portion and an uncopied portion of either of said FromSpace and said ToSpace instances; wherein said write barrier broadcasts a fourth store-oriented memory access targeting said copied portion of either of said FromSpace and said ToSpace instances to both of said FromSpace and said ToSpace instances; and wherein said write barrier directs a fifth store-oriented memory access targeting said uncopied portion to said FromSpace instance and not to said ToSpace instance.

Claim 11

Dependent Claim 104 words

An apparatus, as recited in claim 1, wherein, during a copy phase of relocation of said particular object, said write barrier broadcasts a sixth store-oriented memory access targeting said copied portion to both said FromSpace said ToSpace instances; wherein, during said copy phase, said write barrier directs a seventh store-oriented memory access targeting an uncopied portion of said FromSpace instance to said FromSpace instance and not to said ToSpace instance; and wherein, during a pointer update phase, said write barrier broadcasts an eighth store-oriented memory access targeting either of said FromSpace and said ToSpace instances to both of said FromSpace and said ToSpace instances.

Claim 12

Dependent Claim 57 words

An apparatus, as recited in claim 10, further comprising: a partial copy position indicator to discriminate between said copied portion and said uncopied portion; and a relocation mode indicator to indicate a current relocation phase, including said copy phase and said pointer update phase, for said particular object, said write barrier responsive to said relocation mode indicator.

Claim 13

Dependent Claim 47 words

An apparatus, as recited in claim 10, further comprising: a partial copy position indicator to discriminate between said copied portion and said uncopied portion, wherein said pointer update phase corresponds to a partial copy position indicator state indicative of a completely copied state for said particular object.

Claim 14

Dependent Claim 122 words

An apparatus, as recited in claim 1, further comprising: a processor embodying said partially relocated object identifier store and said write barrier; and mutator process instructions encoded in media readable by said processor and executable thereby, said mutator process instructions including an instruction corresponding to said store-oriented memory access, and garbage collector process instructions encoded in media readable by said processor and executable thereby, said garbage collector process instructions including an instruction sequence to incrementally copy said particular object from said FromSpace instance to said ToSpace instance, to incrementally update pointers referencing said FromSpace instance to reference said ToSpace instance, and to maintain said partially relocated object identifier store in correspondence therewith, said instruction sequence being interruptable by said mutator process instructions.

Claim 15

Dependent Claim 120 words

An apparatus, as recited in claim 1, further comprising: a processor embodying said partially relocated object identifier store and said write barrier; and mutator process instructions encoded in media readable by said processor and executable thereby, said mutator process instructions including an instruction corresponding to said store-oriented memory access, and relocator process instructions encoded in media readable by said processor and executable thereby, said relocator process instructions including an instruction sequence to incrementally copy said particular object from said FromSpace instance to said ToSpace instance, to incrementally update pointers referencing said FromSpace instance to reference said ToSpace instance, and to maintain said partially relocated object identifier store in correspondence therewith, said instruction sequence being interruptable by said mutator process instructions.

Claim 16

Dependent Claim 34 words

An apparatus, as recited in claim 14, wherein said relocator process instructions are selected to perform one of generational garbage collection, mark-sweep-compact garbage collection, copying garbage collection, and heap compaction with bounded pause time.

Claim 17

Dependent Claim 47 words

An apparatus, as recited in claim 14, wherein said pointers referencing said particular object directly reference said particular object; and wherein said relocator process instructions are selected to perform one of generational garbage collection, mark-sweep-compact garbage collection, copying garbage collection, and heap compaction with bounded pause time.

Claim 18

Dependent Claim 16 words

An apparatus, as recited in claim 14, wherein said processor comprises a virtual machine instruction processor.

Claim 19

Dependent Claim 30 words

An apparatus, as recited in claim 14, wherein said processor comprises a hardware processor including register storage and logic embodying said partially relocated object identifier store and said write barrier.

Claim 20

Dependent Claim 15 words

An apparatus, as recited in claim 1, wherein said particular object comprises a large object.

Claim 21

Dependent Claim 15 words

An apparatus, as recited in claim 1, wherein said particular object comprises a popular object.

Claim 22

Dependent Claim 17 words

An apparatus, as recited in claim 1, wherein said particular object comprises a large and popular object.

Claim 23

Dependent Claim 37 words

An apparatus, as recited in claim 1, wherein said write barrier comprises a first write barrier to store-oriented memory accesses targeting said FromSpace instance and a second write barrier to store-oriented memory accesses targeting said ToSpace instance.

Claim 24

Dependent Claim 83 words

An apparatus, as recited in claim 1, a hardware processor embodying said partially relocated object identifier store and said write barrier; a communications device coupled to said hardware processor for receiving mutator process instructions for execution on said hardware processor, said mutator process instructions including a first instruction corresponding to said store-oriented memory access; and media readable by said hardware processor to encode garbage collector process instructions executable and said hardware processor for incrementally copying said particular object and incrementally updating pointers thereto.

Claim 25

Dependent Claim 102 words

An apparatus, as recited in claim 1, further comprising first and second processors coupled to said partially relocated object identifier store and to said memory storage, said first processor including said write barrier; wherein said relocation comprises incremental copying of said particular object by a garbage collector process executable on said second processor, and wherein said store-oriented and said load-oriented memory accesses respectively comprise write and read accesses by a mutator process executable on said first processor; and wherein said partially relocated object identifier store is maintained by said garbage collector process in correspondence with said incremental copying of said particular object.

Claim 26

Dependent Claim 18 words

An apparatus, as recited in claim 24, wherein said second processor comprises a special purpose garbage collection processor.

Claim 27

Dependent Claim 31 words

An apparatus, as recited in claim 24, wherein said second processor is integral with said memory storage, said second processor and said memory storage together comprising a garbage collected memory module.

Claim 28

Dependent Claim 76 words

An apparatus, as recited in claim 1, wherein said partially relocated object identifier store is further updatable to identify a second of said objects for which relocation is incomplete; and wherein said apparatus further comprises first and second garbage collection processors coupled to said partially relocated object identifier store and to said memory storage, relocation of said particular and said second objects comprising incremental copying thereof by said first and said second garbage collection processors, respectively.

Claim 29

Dependent Claim 135 words

A garbage collection system to manage memory object instance consistency during relocation of a particular memory object in a computer system providing bounded pause-time relocation of said particular memory object using incremental copying of said particular object from a FromSpace instance to a ToSpace instance thereof and using incremental update of direct referencing pointers thereto, said garbage collection system comprising: a partially relocated object identifier store including identifier fields for said FromSpace and said ToSpace instances; write barrier logic responsive to a correspondence between a target object identifier for a store-oriented mutator process access to said particular object and contents of either of said FromSpace and said ToSpace instance identifier fields, wherein said write barrier maintains consistency between said FromSpace and said ToSpace instances during said incremental copying and during said incremental update of pointers.

Claim 30

Dependent Claim 135 words

A garbage collection system to manage memory object instance consistency during relocation of a particular memory object in a computer system providing bounded pause-time relocation of said particular memory object using incremental copying of said particular object from a FromSpace instance to a ToSpace instance thereof and using incremental update of direct referencing pointers thereto, said garbage collection system comprising: a partially relocated object identifier store including identifier fields for said FromSpace and said ToSpace instances; write barrier logic responsive to a correspondence between a target object identifier for a store-oriented mutator process access to said particular object and contents of either of said FromSpace and said ToSpace instance identifier fields, wherein said write barrier maintains consistency between said FromSpace and said ToSpace instances during said incremental copying and during said incremental update of pointers.

Claim 31

Dependent Claim 82 words

A garbage collection system, as recited in claim 27, wherein, during said incremental copying, said consistency maintenance includes broadcasting a first store-oriented mutator process access targeting said FromSpace instance of said particular object to both said FromSpace and said ToSpace instances thereof; and wherein, during said update of pointers, said consistency maintenance includes broadcasting a second store-oriented mutator process access targeting either of said FromSpace and said ToSpace instances of said particular object to both said FromSpace and said ToSpace instances thereof.

Claim 32

Dependent Claim 61 words

A garbage collection system, as recited in claim 27, wherein said partially relocated object identifier store further includes a partial copy position indicator to identify an uncopied portion of said particular object; and wherein said write barrier logic selectively forgoes broadcast for a third store-oriented mutator process access to said uncopied portion, and instead directs such access to said FromSpace instance.

Claim 33

Independent Claim 89 words

A method for relocating a memory object with bounded pause time impact on a mutator process having access thereto, said method comprising: configuring a write barrier to respond to store-oriented accesses of said mutator process targeting either of a From instance and a To instance of said memory object; incrementally copying said memory object from said From instance to said To instance; during said incremental copying and in response to a first of said store-oriented accesses, broadcasting said first store-oriented access to both said From and said To instances.

Claim 34

Independent Claim 89 words

A method for relocating a memory object with bounded pause time impact on a mutator process having access thereto, said method comprising: configuring a write barrier to respond to store-oriented accesses of said mutator process targeting either of a From instance and a To instance of said memory object; incrementally copying said memory object from said From instance to said To instance; during said incremental copying and in response to a first of said store-oriented accesses, broadcasting said first store-oriented access to both said From and said To instances.

Claim 35

Dependent Claim 57 words

A method, as recited in claim 31, wherein said write barrier configuring comprises updating a partially relocated object identifier store to identify said From instance and said To instance; and wherein said broadcasting is in response to a correspondence between an object identifier for said first store-oriented access and contents of said partially relocated object identifier store.

Claim 36

Dependent Claim 63 words

A method, as recited in claim 31, further comprising: maintaining a partial copy position indicator to discriminate between a copied portion and an uncopied portion of said memory object; and during said incremental copying and in response to a second of said store-oriented accesses targeting said uncopied portion, directing said second store-oriented access to said From instance and not to said To instance.

Claim 37

Dependent Claim 16 words

A method, as recited in claim 31, wherein said broadcasting is performed by said write barrier.

Claim 38

Dependent Claim 25 words

A method, as recited in claim 31, wherein said broadcasting is performed by trap handler software in response to a trap by said write barrier.

Claim 39

Dependent Claim 60 words

A method, as recited in claim 31, further comprising: incrementally updating pointers to said memory object to refer to said To instance rather than to said From instance; and during said incremental updating of pointers and in response to a third of said store-oriented access, broadcasting said third store-oriented access to both of said From instance and said To instance.

Claim 40

Dependent Claim 39 words

A method, as recited in claim 36, further comprising distinguishing between said incremental copying and said incremental updating using a relocation mode indicator maintained by a garbage collection process performing said incremental copying and said incremental updating of pointers.

Claim 41

Dependent Claim 30 words

A method, as recited in claim 36, further comprising distinguishing between said incremental copying and said incremental updating using a partial copy position indicator maintained by a garbage collection process.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2002-02-15	2002-08-17	2003-02-16	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2006-02-15	2006-08-17	2007-02-16	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2010-02-15	2010-08-17	2011-02-16	$7700.00	Window Closed / Lapsed

Bounded-pause time garbage collection system and method including write barrier associated with source and target instances of a partially relocated object

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag