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

• US 5,873,104 A
• Filed: 06/26/1997
• Issued: 02/16/1999
• Est. Priority Date: 06/26/1997
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Vishin, Sanjay, Steele, Guy L. Jr., Agesen, Ole, Tremblay, Marc, O'Connor, James Michael, White, Derek R., Heller, Steven
• Primary Examiner(s): Kulik, Paul V.
• Application Number:
  US08/882,796
• Time in Patent Office: 600 Days
• Field of Search: 707/206, 711/165
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0269 Incremental or concurrent garbage collection, e.g. in real-time systems G06F12/0261 takes precedence
• CPC Class Codes: G06F 12/0276 Generational garbage collection
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

A partially relocated object identifier store including "copy from" identifier and "copy to" 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 without software trap handler overhead. 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. An optional "mode" indication facilitates differentiation by the write barrier logic between a copy phase and a pointer update phase of relocation by the garbage collector implementation. In some embodiments, pointer update and copying phases may overlap. "Copy to" identifier storage facilitates broadcast of a store-oriented memory access to the FromSpace instance to both FromSpace and ToSpace instances. Similarly, during pointer update, "Copy to" and "Copy From" identifier storage facilitate broadcast of a store-oriented memory access to either the FromSpace instance or the ToSpace instance to both FromSpace and ToSpace instances.

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 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.

2. 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.

3. 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.

4. 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.

5. 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.

6. 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.

7. 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.

8. 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.

9. 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.

10. 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.

11. 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.

12. 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.

13. 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.

14. 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.

15. 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.

16. 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.

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

18. 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.

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

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

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

22. 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.

23. 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.

24. 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.

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

26. 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.

27. 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.

29. 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.

30. 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.

28. 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.

31. 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.

32. 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.

33. 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.

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

35. 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.

36. 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.

37. 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.

38. 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.