US5873105A — Bounded-pause time garbage collection system and …

Claim 1

Independent Claim 83 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 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 said FromSpace instance of said particular object, wherein said write barrier maintains consistency between said ToSpace instance and at least a copied portion of said FromSpace instance.

Claim 2

Independent Claim 83 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 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 said FromSpace instance of said particular object, wherein said write barrier maintains consistency between said ToSpace instance and at least a copied portion of said FromSpace instance.

Claim 3

Dependent Claim 34 words

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

Claim 4

Dependent Claim 30 words

An apparatus, as recited in claim 1, wherein operation of said write barrier allows incremental copying of said particular object from said FromSpace instance thereof to said ToSpace instance thereof.

Claim 5

Dependent Claim 54 words

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

Claim 6

Dependent Claim 39 words

An apparatus, as recited in claim 4, further comprising: a ToSpace instance identifier accessible to said partially relocated object trap handler, said partially relocated object trap handler broadcasting a trapping store-oriented access to said ToSpace and said FromSpace instances.

Claim 7

Dependent Claim 31 words

An apparatus, as recited in claim 5, wherein said partially relocated object identifier store includes said ToSpace instance identifier as a TO field accessible to said partially relocated object trap handler.

Claim 8

Dependent Claim 33 words

An apparatus, as recited in claim 5, wherein said ToSpace instance identifier includes a portion of said memory storage accessible to said partially relocated object trap handler and to a garbage collector process.

Claim 9

Dependent Claim 82 words

An apparatus, as recited in claim 4, further comprising a partial copy position indicator accessible to said partially relocated object trap handler, wherein, for a trapping store-oriented access to a copied portion, said partially relocated object trap handler broadcasts to both said ToSpace and said FromSpace instances, and wherein, for a trapping store-oriented access to an uncopied portion of said particular object, said partially relocated object trap handler directs said store-oriented access to said FromSpace instance and not to said ToSpace instance.

Claim 10

Dependent Claim 74 words

An apparatus, as recited in claim 4, wherein said partially-relocated object identifier store includes a FromSpace instance identifier and a partial copy position indicator to identify a boundary between a copied portion and an uncopied portion of said particular object; and wherein said write barrier is responsive to said partially relocated object identifier store, selectively trapping to said partially relocated object trap handler upon a write to said copied portion of said particular object.

Claim 11

Dependent Claim 84 words

An apparatus, as recited in claim 1, wherein said partially relocated object identifier store includes FromSpace and ToSpace instance identifiers; and wherein said write barrier comprises write barrier logic coupled to said FromSpace and said ToSpace instance identifiers, said write barrier logic responsive to a correspondence between contents of said FromSpace instance identifier and an object identifier for a store-oriented memory access, and wherein, in response to said correspondence, said write barrier logic broadcasts said store-oriented access to said ToSpace and said FromSpace instances.

Claim 12

Dependent Claim 98 words

An apparatus, as recited in claim 1, wherein said write barrier comprises write barrier logic; wherein said partially relocated object identifier store comprises FromSpace and ToSpace instance identifiers and a partial copy position indicator, each coupled to said write barrier; wherein, for a store-oriented access to a copied portion of said particular object, said write barrier broadcasts store data to both said ToSpace and said FromSpace instances, and wherein, for a store-oriented access to an uncopied portion of said particular object, said write barrier directs said store data to said FromSpace instance and not to said ToSpace instance.

Claim 13

Dependent Claim 75 words

An apparatus, as recited in claim 1, further comprising: a garbage collection process including first instructions executable on a processor including said partially relocated object identifier store and said write barrier, said first instructions for incrementally copying portions of said particular object from said FromSpace instance to said ToSpace instance; and a mutator process including second instructions executable on said processor for making load-oriented memory accesses and said store-oriented memory access to said particular object.

Claim 14

Dependent Claim 37 words

An apparatus, as recited in claim 1, wherein said partially relocated object identifier store includes a partial copy position indicator portion indicative of a boundary between a copied portion and an uncopied portion of said particular object.

Claim 15

Dependent Claim 33 words

An apparatus, as recited in claim 1, wherein said relocation comprises incrementally copying said particular object from a FromSpace portion to a ToSpace portion of a garbage collected portion of said memory storage.

Claim 16

Dependent Claim 35 words

An apparatus, as recited in claim 1, wherein said FromSpace and said ToSpace overlap; and wherein said relocation comprises incrementally copying said particular object to compact a plurality of said objects in said memory storage.

Claim 17

Dependent Claim 27 words

An apparatus, as recited in claim 1, wherein said partially relocated object identifier store is updated by a garbage collection process in correspondence with incremental copying thereby.

Claim 18

Dependent Claim 119 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 garbage collector process instructions including an instruction sequence to incrementally copy said particular object from said FromSpace instance to said ToSpace instance, to update an object reference handle 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 19

Dependent Claim 34 words

An apparatus, as recited in claim 17, 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 20

Dependent Claim 30 words

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

Claim 21

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 garbage collector process instructions including an instruction sequence to incrementally copy said particular object from said FromSpace instance to said ToSpace instance, to 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 22

Dependent Claim 15 words

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

Claim 23

Dependent Claim 15 words

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

Claim 24

Dependent Claim 17 words

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

Claim 25

Dependent Claim 78 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.

Claim 26

Dependent Claim 97 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 memory access comprises a write access 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 27

Dependent Claim 18 words

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

Claim 28

Dependent Claim 31 words

An apparatus, as recited in claim 25, 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 29

Dependent Claim 16 words

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

Claim 30

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 31

Dependent Claim 114 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, 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 said FromSpace instance identifier field, wherein said write barrier maintains consistency between said FromSpace and said ToSpace instances during said incremental copying.

Claim 32

Dependent Claim 114 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, 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 said FromSpace instance identifier field, wherein said write barrier maintains consistency between said FromSpace and said ToSpace instances during said incremental copying.

Claim 33

Dependent Claim 38 words

A garbage collection system, as recited in claim 30, wherein 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.

Claim 34

Dependent Claim 61 words

A garbage collection system, as recited in claim 30, 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 second store-oriented mutator process access to said uncopied portion, and instead directs such access to said FromSpace instance.

Claim 35

Independent Claim 99 words

A method for bounding garbage collection pause time, said method comprising: during relocating of a memory object from a source instance to a target instance thereof, interrupting said relocating in accordance with a bounded pause time commitment to a mutator process; selectively trapping, during said interruption of said relocating, a write access by said mutator process to said memory object by detecting a correspondence between an object identifier therefor and contents of a partially relocated object identifier store; and in response to said trapping, handling said write access in accordance with a partial relocation state of said memory object.

Claim 36

Independent Claim 99 words

A method for bounding garbage collection pause time, said method comprising: during relocating of a memory object from a source instance to a target instance thereof, interrupting said relocating in accordance with a bounded pause time commitment to a mutator process; selectively trapping, during said interruption of said relocating, a write access by said mutator process to said memory object by detecting a correspondence between an object identifier therefor and contents of a partially relocated object identifier store; and in response to said trapping, handling said write access in accordance with a partial relocation state of said memory object.

Claim 37

Dependent Claim 50 words

A method, as recited in claim 33, wherein, if there exists a correspondence between a copied portion of said memory object and said write access, said handling includes broadcasting said write access to both of said source instance and said target instance; and otherwise, completing said write access without broadcasting.

Claim 38

Dependent Claim 44 words

A method, as recited in claim 33, wherein said selective trapping includes further detecting a correspondence between a copied portion of said memory object and said write access such that a particular write access to an uncopied portion of said memory object is untrapped.

Claim 39

Independent Claim 83 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 a From 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 40

Independent Claim 83 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 a From 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 41

Dependent Claim 53 words

A method, as recited in claim 36, wherein said write barrier configuring comprises updating a partially relocated object identifier store to identify said From 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 42

Dependent Claim 26 words

A method, as recited in claim 37, wherein said write barrier configuring further comprises updating a partially relocated object identifier store to identify said To instance.

Claim 43

Dependent Claim 63 words

A method, as recited in claim 36, 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 44

Dependent Claim 16 words

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

Claim 45

Dependent Claim 25 words

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

Claim 46

Dependent Claim 60 words

A virtual machine instruction processor with support for a bounded pause time implementation of a relocating garbage collector comprising: a partially relocated memory object identifier store; and a write barrier responsive to said partially relocated memory object identifier store such that evaluation of a store instruction to a memory object identified in said partially relocated memory object identifier store traps.

Claim 47

Dependent Claim 60 words

A virtual machine instruction processor with support for a bounded pause time implementation of a relocating garbage collector comprising: a partially relocated memory object identifier store; and a write barrier responsive to said partially relocated memory object identifier store such that evaluation of a store instruction to a memory object identified in said partially relocated memory object identifier store traps.

Claim 48

Dependent Claim 33 words

A virtual machine instruction processor with support for a bounded pause time implementation of a relocating garbage collector as recited in claim 42 further comprising: a trap handler responsive to said write barrier.

Claim 49

Dependent Claim 114 words

A computing machine comprising: a processor; memory, wherein objects formed therein are referenceable by said processor; and means accessible by said processor for identifying a partially collected object in said memory, wherein a correspondence between said partially collected object identifier means and an object identifier for an object reference operation by said processor triggers fault handler means; means for garbage collecting said memory, wherein said garbage collecting means maintains said partially collected object identifier means to identify a particular one, if any, of said objects for which garbage collection is incomplete, thereby allowing interruption of said garbage collecting means in accordance with a bounded pause time commitment to mutator means executable on said processor.

Claim 50

Dependent Claim 114 words

A computing machine comprising: a processor; memory, wherein objects formed therein are referenceable by said processor; and means accessible by said processor for identifying a partially collected object in said memory, wherein a correspondence between said partially collected object identifier means and an object identifier for an object reference operation by said processor triggers fault handler means; means for garbage collecting said memory, wherein said garbage collecting means maintains said partially collected object identifier means to identify a particular one, if any, of said objects for which garbage collection is incomplete, thereby allowing interruption of said garbage collecting means in accordance with a bounded pause time commitment to mutator means executable on said processor.

Claim 51

Dependent Claim 113 words

A computer program product comprising: an interruptable object relocator encoded in media readable by a processor and executable on said processor, wherein said interruptable object relocator causes, at least upon interruption, a partially relocated object identifier store of said processor to identify a from instance of a partially relocated memory object; a partially relocated object access handler invoked in response to a correspondence between contents of said partially relocated object identifier store and an object identifier for an object reference operation by a mutator executable on said processor, wherein said partially relocated object access handler handles said object reference operation in accordance with a partial relocation state of said partially relocated memory object.

Claim 52

Dependent Claim 113 words

A computer program product comprising: an interruptable object relocator encoded in media readable by a processor and executable on said processor, wherein said interruptable object relocator causes, at least upon interruption, a partially relocated object identifier store of said processor to identify a from instance of a partially relocated memory object; a partially relocated object access handler invoked in response to a correspondence between contents of said partially relocated object identifier store and an object identifier for an object reference operation by a mutator executable on said processor, wherein said partially relocated object access handler handles said object reference operation in accordance with a partial relocation state of said partially relocated memory object.

Claim 53

Dependent Claim 35 words

A computer program product, as recited in claim 45, wherein said interruptable object relocator provides object copying from a FromSpace portion of memory to a ToSpace portion of memory in accordance with a copying collector.

Claim 54

Dependent Claim 39 words

A computer program product, as recited in claim 45, wherein said interruptable object relocator provides object copying from a source instance to a potentially overlapping target instance within a collected portion of memory in accordance with a compacting operation.

Claim 55

Dependent Claim 30 words

A computer program product, as recited in claim 45, wherein said interruptable object relocator provides object relocation within a collected portion of memory in accordance with a mark-compact collector implementation.

Claim 56

Dependent Claim 34 words

A computer program product, as recited in claim 45, wherein said interruptable object relocator provides object copying from a young-portion of memory to a older-portion of memory in accordance with a generational collector implementation.

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 a source instance 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