Generational garbage collector on multiple heaps

• US 9,645,923 B1
• Filed: 09/10/2013
• Issued: 05/09/2017
• Est. Priority Date: 09/10/2013
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Hara, Kentaro
• Primary Examiner(s): KUDDUS, DANIEL A
• Application Number:
  US14/023,291
• Time in Patent Office: 1,337 Days
• Field of Search: 711170
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 12/0276 Generational garbage collection
• CPC Class Codes: G06F 16/172 Caching, prefetching or hoarding of files
• CPC Class Codes: G06F 16/1748 De-duplication implemented within the file system, e.g. based on file segments de-duplication techniques in storage systems for the management of data blocks G06F3/0641
• CPC Class Codes: G06F 2212/1016 Performance improvement

Abstract

The subject technology discloses configurations for determining a list of wrappers in a new space of a host heap that include a reference to at least one object in a guest heap; marking a set of objects in a new space of the guest heap; building an eden graph for the guest heap; marking a set of objects in the new space of the host heap based on a reachability in the eden graph; determining a list of marked wrappers from the host heap that are included in the eden graph of the guest heap; marking a set of wrappers in the new space of the guest heap that are included in the list of marked wrappers in the eden graph; and collecting a set of unmarked objects from the host heap and the guest heap.

Claims

1. A computer-implemented method, the method comprising:

determining a first set of objects, in a new space of a first heap, that include a reference to at least one object in a second heap;

marking a second set of objects in a new space of the second heap, wherein the second set of objects comprises wrapper objects that are reachable from spaces other than the new space of the first heap;

building an eden graph comprising a third set of objects in the new space of the second heap, wherein the third set of objects comprises unmarked wrapper objects in the new space of the second heap such that the third set of objects does not include objects from the second set of objects;

marking a fourth set of objects in the new space of the first heap based on reachability in the eden graph;

marking a fifth set of objects in the new space of the second heap, the fifth set of objects being based on the fourth set of objects; and

collecting a set of unmarked objects from the first heap and the second heap.

2. The method of claim 1, wherein the fifth set of objects comprises a set of wrapper objects.

3. The method of claim 2, wherein each wrapper object of the set of wrapper objects is a JavaScript wrapper object.

4. The method of claim 2, wherein each wrapper object of the set of wrapper objects is bidirectionally referenced.

5. The method of claim 1, further comprising syncing between the second heap and at least one other heap.

6. The method of claim 1, wherein the first heap includes a set of non-wrapper objects.

7. The method of claim 1, wherein the first heap includes a set of wrapper objects that reference another heap different than the second heap.

8. The method of claim 1, wherein each object in the third set of objects comprises a respective wrapper object between the first heap and the second heap.

9. The method of claim 8, wherein the respective wrapper object of each object in the third set of objects is unreachable if all ancestor wrapper objects of the respective wrapper object in the graph are unreachable in the new space of the first heap.

10. The method of claim 1, wherein at least one object of the fourth set of objects is referenced by at least one object of the third set of objects.

11. The method of claim 1, wherein the second set of objects comprises at least one object in the new space of the second heap that is referenced by an object in an old space of the second heap.

12. The method of claim 1, wherein at least one object of the third set of objects is referenced by at least one object in the first set of objects.

13. The method of claim 1, wherein at least one object of the second set of objects is referenced by at least one object in the first set of objects.

14. The method of claim 1, further comprising, triggering garbage collection on the first heap, each of the determining, the marking the second set of objects, the building, the marking the fourth set of objects, the marking the fifth set of objects, and the collecting being in response to triggering the garbage collection on the first heap.

15. The method of claim 1, wherein the second set of objects comprises:

a root object of the second heap,

a first object in the new space of the second heap that is referenced by an object in an old space of the second heap, and

each object of the first set of objects that is reachable from at least one of the root object or the first object.

16. The method of claim 1, wherein the fourth set of objects comprises:

a root object of the first heap, and

each object of the third set of objects that is reachable from the root object.

17. A system, the system comprising:

one or more processors;

a memory comprising instructions stored therein, which when executed by the one or more processors, cause the processors to perform operations comprising;

determining a first set of objects in a new space of a first heap that include a reference to at least one object in a second heap;

marking a second set of objects in a new space of the second heap, wherein the second set of objects comprises wrapper objects that are reachable from spaces other than the new space of the first heap;

building eden graph comprising a third set of objects in the new space of the second heap, wherein the third set of objects comprises unmarked wrapper objects in the new space of the second heap such that the third set of objects does not include objects from the second set of objects;

marking a fourth set of objects in the new space of the first heap based on reachability in the eden graph;

marking a fifth set of objects in the new space of the second heap, the fifth set of objects being based on the fourth set of objects; and

collecting a set of unmarked objects from the first heap and the second heap.

18. The system of claim 17, wherein the fifth set of objects comprises a set of wrapper objects.

19. The system of claim 18, wherein each wrapper object of the set of wrapper objects is bidirectionally referenced.

20. The system of claim 17, wherein the first heap includes a set of non-wrapper objects.

21. The system of claim 17, wherein the first heap includes a set of wrapper objects that reference another heap different than the second heap.

22. The system of claim 17, wherein each object in the third set of objects comprises a respective wrapper object between the first heap and the second heap.

23. The system of claim 22, wherein the respective wrapper object of each object in the third set of objects is unreachable if all ancestor wrapper objects of the respective wrapper object in the graph are unreachable in the new space of the first heap.

24. A non-transitory machine-readable medium comprising instructions stored therein, which when executed by a machine, cause the machine to perform operations comprising:

determining a first set of objects in a new space of a first heap that include a reference to at least one object in a second heap;

marking a second set of objects in a new space of the second heap, wherein the second set of objects comprises wrapper objects that are reachable from spaces other than the new space of the first heap;

building eden graph comprising a third set of objects in the new space of the second heap, wherein the third set of objects comprises unmarked wrapper objects in the new space of the second heap such that the third set of objects does not include objects from the second set of objects;

marking a fourth set of objects in the new space of the first heap based on reachability in the eden graph;

marking a fifth set of objects in the new space of the second heap, the fifth set of objects being based on the fourth set of objects; and

collecting a set of unmarked objects from the first heap and the second heap.