Bounded-pause time garbage collection system and method including write barrier associated with a source instance of a partially relocated object
First Claim
1. 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.
3 Assignments
0 Petitions
Accused Products
Abstract
A write barrier to stores into a partially relocated large or popular memory object facilitates bounded pause time implementations of relocating garbage collectors, including e.g., copying collectors, generational collectors, and collectors providing compaction. Such a write barrier allows a garbage collector implementation to interrupt relocation of large or popular memory objects so as to meet bounded pause time guarantees. A partially relocated object identifier store including "copy from" identifier storage accessible to write barrier logic allows the write barrier logic to maintain consistency between FromSpace and ToSpace instances of a partially relocated memory object. "Copy from" identifier storage allows the write barrier logic, or a trap handler responsive thereto, to broadcast a store-oriented memory access targeting the FromSpace instance to both FromSpace and ToSpace instances. Optional "How far" indication storage facilitates differentiation by the write barrier logic between a copied portion and an uncopied portion of the partially relocated memory object.
118 Citations
49 Claims
-
1. 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29)
-
-
30. 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. - View Dependent Claims (31, 32)
-
-
33. 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. - View Dependent Claims (34, 35)
-
-
36. 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. - View Dependent Claims (37, 38, 39, 40, 41)
-
-
42. 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. - View Dependent Claims (43)
-
-
44. 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.
-
-
45. 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. - View Dependent Claims (46, 47, 48, 49)
-
Specification