Bounded-pause time garbage collection system and method including read and write barriers associated with an instance of a partially relocated object

• US 5,857,210 A
• Filed: 06/26/1997
• Issued: 01/05/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: Heller, Steven, Vishin, Sanjay, Steele, Guy L. Jr., Agesen, Ole, Tremblay, Marc, O'Connor, James Michael, White, Derek R.
• Primary Examiner(s): Kulik, Paul V.
• Application Number:
  US08/882,801
• Time in Patent Office: 558 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" and "copy to" identifier storage accessible to write and read barrier logic allows the write and read barrier logic to selectively direct store- and load-oriented accesses to an appropriate FromSpace or ToSpace instance of a partially relocated memory object, in accordance with the memory object'"'"'s partial relocation state. In some embodiments, the barriers trap to a partially relocated object trap handler. In other embodiments, the write barrier itself directs accesses without software trap handler overheads. Optional "how far" indication storage facilitates differentiation by the barrier logic, or by the partially relocated object trap handler, between a copied portion and an uncopied portion of the partially relocated memory object.

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 particular instance of a particular one of said objects, if any, for which relocation is incomplete, said particular instance being one of a FromSpace instance and a ToSpace instance;

a write barrier to store-oriented memory accesses targeting said particular instance; and

a read barrier to load-oriented memory accesses targeting said particular instance,

said write and said read barriers being responsive to a correspondence between contents of said partially relocated object identifier store and object identifiers for respective of said store-oriented and said load-oriented memory accesses.

2. An apparatus, as recited in claim 1,

wherein said particular instance is said FromSpace instance;

wherein said relocation includes a copying phase followed by a pointer update phase; and

wherein said partially relocated object identifier includes a FromSpace instance identifier.

3. An apparatus, as recited in claim 1,

wherein said particular instance is said ToSpace instance;

wherein said relocation includes a pointer update phase followed by a copying phase; and

wherein said partially relocated object identifier includes a ToSpace instance identifier.

4. An apparatus, as recited in claim 1, wherein said relocation includes temporally overlapped incremental copying and incremental pointer update.

5. An apparatus, as recited in claim 1, wherein said write barrier directs a first of said store-oriented memory accesses to said ToSpace instance and a second of said store-oriented memory accesses to said FromSpace instance, said first and said second store-oriented memory accesses respectively targeting copied and uncopied portions of said particular instance.

6. An apparatus, as recited in claim 5, wherein said write barrier further directs said first store-oriented memory access to said FromSpace instance.

7. An apparatus, as recited in claim 1, wherein said read barrier directs a first of said load-oriented memory accesses to said ToSpace instance and a second of said load-oriented memory accesses to said FromSpace instance, said first load-oriented memory access targeting a copied portion of said particular instance, said second load-oriented memory access targeting an uncopied portion of said particular instance.

8. An apparatus, as recited in claim 7, wherein said read barrier directs a third of said load-oriented memory accesses to said ToSpace instance, said third load-oriented memory access occurring after completion of a copying phase of said relocation.

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

10. An apparatus, as recited in claim 1, wherein operation of said write and said read barriers allows incremental copying of said particular object from said FromSpace instance to said ToSpace instance, wherein said FromSpace instance and said ToSpace instance overlap in said memory storage.

11. An apparatus, as recited in claim 1, wherein said FromSpace and said ToSpace instances overlap in said memory storage.

12. An apparatus, as recited in claim 1, wherein operation of said read barrier allows incremental update of pointers to said particular object, said incremental update being from FromSpace instance referencing states to ToSpace instance referencing states.

13. An apparatus, as recited in claim 1, wherein said write and said read barriers comprise write and read barrier logic and a partially relocated object trap handler, said write and said read barrier logic responsive to correspondences between contents of said partially relocated object identifier store and object identifiers for respective of said store-oriented and said load-oriented memory accesses, said read and said write barrier logic trapping to said partially relocated object trap handler upon said correspondences.

14. An apparatus, as recited in claim 1, wherein

said partially relocated object identifier store includes FromSpace and ToSpace instance identifiers;

and

said write and said read barriers comprise write and read barrier logic coupled to said FromSpace and said ToSpace instance identifiers, said write and said read barrier logic responsive to correspondences between object identifiers for respective of said store-oriented and said load-oriented memory accesses and contents of one of said FromSpace instance and said ToSpace instance identifiers.

15. An apparatus, as recited in claim 1, wherein said write and said read barriers comprise write and read barrier logic;

said partially relocated object identifier store comprises FromSpace and ToSpace instance identifiers and a partial copy position indicator;

for a first store-oriented access targeting a copied portion of said particular object, said write barrier directs store data to at least said ToSpace instance, and

for a second store-oriented access targeting an uncopied portion of said particular object, said write barrier directs said store data to said FromSpace instance.

16. An apparatus, as recited in claim 15, wherein

for said first store-oriented access, said write barrier further directs store data to said FromSpace instance;

and

said read barrier directs a third load-oriented memory access to said ToSpace instance, said third load-oriented memory access occurring after completion of a copying phase of said relocation.

17. An apparatus, as recited in claim 15, wherein

said read barrier directs a first load-oriented memory access targeting a copied portion of said particular object to said ToSpace instance;

and

said read barrier directs a second load-oriented memory access targeting an uncopied portion of said particular object to said FromSpace instance.

18. 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, said write barrier, and said read 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 said load-oriented and said store-oriented memory accesses.

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

20. 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 and incrementally updating pointers to said particular object.

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

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

23. An apparatus, as recited in claim 1, further comprising:

a processor embodying said partially relocated object identifier store, said write barrier, and said read barrier; and

mutator process instructions encoded in media readable by said processor and executable thereby, said mutator process instructions including instructions corresponding to said store-oriented and said load-oriented memory accesses, 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 incrementally update FromSpace instance referencing pointers 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.

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

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

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

27. An apparatus, as recited in claim 1,

a hardware processor embodying said partially relocated object identifier store, said write barrier, and said read 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 accesses and a second instruction corresponding to said load-oriented memory accesses; 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.

28. 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 and said read barriers;

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.

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

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

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

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

a read barrier to a load-oriented memory access targeting said FromSpace instance, wherein, at least during a pointer update phase of said relocation, said read barrier directs said load-oriented memory access to a ToSpace instance of said particular object.

33. An apparatus, as recited in claim 32, wherein during a copying phase of said relocation, said write barrier maintains consistency between said ToSpace instance of said particular object and at least a copied portion of said FromSpace instance.

34. An apparatus, as recited in claim 32,

further comprising a partial copy position indicator indicative of a boundary between a copied and an uncopied portion of said FromSpace instance,

wherein, for a first of said store-oriented accesses targeting said copied portion, said write barrier directs store data to said ToSpace instance,

wherein, for a second of said store-oriented accesses targeting said uncopied portion, said write barrier directs said store data to said FromSpace instance;

wherein, for a first of said load-oriented memory accesses targeting said copied portion, said read barrier directs said first load-oriented memory access to said ToSpace instance; and

wherein, for a second of said load-oriented memory accesses targeting said uncopied portion, said read barrier directs said second load-oriented memory access to said FromSpace instance.

35. 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 ToSpace instance of a particular one of said objects, if any, for which relocation is incomplete;

a write barrier to store-oriented memory accesses targeting said ToSpace instance; and

a read barrier to load-oriented memory accesses targeting said ToSpace instance.

36. An apparatus, as recited in claim 35,

further comprising a partial copy position indicator indicative of a boundary between a copied and an uncopied portion of said ToSpace instance,

wherein said write and said read barriers direct respective of said store-oriented and said load-oriented memory accesses targeting said uncopied portion to said FromSpace instance.

37. 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 first instance to a second instance thereof, said garbage collection system comprising:

a partially relocated object identifier store including identifier fields for said first and said second instances;

write barrier logic responsive to a correspondence between an object identifier for a store-oriented mutator process access and contents of said first instance identifier field; and

read barrier logic responsive to a correspondence between an object identifier for a load-oriented mutator process access and contents of said first instance identifier field.

38. A garbage collection system, as recited in claim 37,

wherein said write barrier broadcasts a first of said store-oriented mutator process accesses targeting said first instance of said particular object to both said first and said second instances thereof.

39. A garbage collection system, as recited in claim 37,

wherein said partially relocated object identifier store further includes a partial copy position indicator to identify an uncopied portion of said particular object;

wherein said write barrier logic selectively directs a second of said store-oriented mutator process accesses targeting said uncopied portion of said particular object; and

wherein said read barrier logic selectively directs a third of said load-oriented mutator process accesses sourcing from said uncopied portion of said particular object,

said selective direction by said write and said read barrier being in accordance with a partial relocation state encoded by said copy position indicator.

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

during said interrupting of said relocating, detecting a correspondence between an object identifier for a write access by said mutator process and contents of a partially relocated object identifier store;

selectively directing, based on a partial relocation state of said memory object, said write access to one of said source instance and said target instance;

during said interrupting of said relocating, detecting a correspondence between an object identifier for a read access by said mutator process and contents of a partially relocated object identifier store;

selectively directing, based on said partial relocation state of said memory object, said read access to one of said source instance and said target instance.

41. A method, as recited in claim 40,

wherein, if there exists a correspondence between a copied portion of said memory object and said write access, said selective direction thereof includes direction of said write access to said target instance;

and

otherwise, direction of said write access to said source instance.

42. A method, as recited in claim 40,

wherein, if there exists a correspondence between a copied portion of said memory object and said read access, said selective direction thereof includes direction of said read access to said target instance;

and

otherwise, direction of said read access to said source instance.

43. A method, as recited in claim 40, wherein said relocating includes incrementally copying data associated with said source instance to said target instance and thereafter incrementally updating pointers thereto.

44. A method, as recited in claim 40, wherein said relocating includes incrementally updating pointers referencing said source instance to instead reference said target instance and thereafter incrementally copying data associated with said source instance to said target instance.

45. A method, as recited in claim 40, wherein said relocating includes incrementally updating pointers referencing said source instance to instead reference said target instance and incrementally copying data associated with said source instance to said target instance, said updating pointers and said incrementally copying being temporally overlapped.

46. A method for relocating a memory object with bounded pause time impact on a mutator process having access thereto, said method comprising:

configuring write and read barriers to respond to respective store-oriented and load-oriented accesses by said mutator process targeting a From instance of said memory object;

incrementally copying said memory object from said From instance to a To instance and incrementally updating pointers thereto;

during said incremental copying and pointer updating, and in response to a first of said store-oriented accesses, directing said first store-oriented access targeting a copied portion of said memory object to said To instance thereof;

during said incremental copying and pointer updating, and in response to a first of said load-oriented accesses, directing said first load-oriented access targeting said copied portion of said memory object to said To instance thereof.

47. A method, as recited in claim 46, wherein said write and read barrier configuring comprises updating a partially relocated object identifier store to identify said From instance.

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

49. A method, as recited in claim 46, 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.

50. A method, as recited in claim 46, wherein said directing is performed by said write barrier.

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

52. A method for relocating a memory object with bounded pause time impact on a mutator process having access thereto, said method comprising:

configuring write and read barriers to respond to respective store-oriented and load-oriented accesses by said mutator process targeting a To instance of said memory object;

incrementally updating pointers referencing said From instance to instead reference a To instance and incrementally copying said memory object from said From instance to said To instance;

during said incremental pointer updating and copying, and in response to a first of said store-oriented accesses, directing said first store-oriented access targeting an uncopied portion of said memory object to said From instance thereof,

during said incremental pointer updating and copying, and in response to a first of said load-oriented accesses, directing said first load-oriented access targeting said uncopied portion of said memory object to said From instance thereof.

53. A method comprising:

maintaining a partial relocation state including a FROM instance identifier state, a TO instance identifier state, and a partial copy position indicating state in accordance with incremental copying of a memory object and incremental updating of pointers thereto;

(a) selectively directing, using a hardware read barrier responsive to said partial relocation state, load-oriented memory accesses to either a FROM instance or a TO instance of said memory object; and

(b) selectively directing, using a hardware write barrier responsive to said partial relocation state, store-oriented memory accesses to either a FROM instance or a TO instance of said memory object,

said (a) and said (b) selective directing maintaining a consistent object representation for a mutator process making said load-oriented and said store-oriented memory accesses.

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