Conservative garbage collection and access protection

• US 9,378,138 B2
• Filed: 06/29/2011
• Issued: 06/28/2016
• Est. Priority Date: 06/29/2011
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Varma, Pradeep
• Primary Examiner(s): Chen, Susan
• Application Number:
  US13/172,039
• Publication Number:
  US 20130007073A1
• Time in Patent Office: 1,826 Days
• Field of Search: 707/206, 707/813, 711/114, 711/118, 711/165
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 12/1416 by checking the object accessibility, e.g. type of access defined by the memory independently of subject rights G06F12/1458 takes precedence
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement
• CPC Class Codes: G06F 2212/702 Conservative garbage collection
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/0673 Single storage device

Abstract

A method of memory management can include creating an initial root set of pointers for a program during execution of the program and performing a marking process by iteratively marking referred objects of each pointer of the root set and expanding the root set with filtered, encoded pointers. The method also can include identifying each non-live object for any marked object as red-marked and performing, using a processor, a re-marking process on the root set in which red-marked objects are excluded. Each object of the root set not marked can be designated as including a memory leak.

Claims

1. A method of memory management comprising:

creating an initial root set of pointers for a program during execution of the program;

performing a marking process by iteratively marking referred objects of each pointer of the root set and expanding the root set with filtered, encoded pointers;

identifying each non-live object for any marked object as red-marked;

performing, using a processor, a re-marking process on the root set in which red-marked objects are excluded; and

designating each object of the root set not marked as comprising a memory leak.

2. The method of claim 1, further comprising:

performing the marking process until no changes are made to the root set.

3. The method of claim 1, wherein identifying each non-live object for any marked object as red-marked further comprises:

identifying objects marked during the marking process; and

subtracting objects specified on an allocated objects list from the objects that are marked.

4. The method of claim 1, further comprising:

requiring each pointer generated by the program be live and inbound to a referent object.

5. The method of claim 1, wherein performing a re-marking process on the root set in which red-marked objects are excluded further comprises:

filtering pointer and object pairs according to a version number included within each pointer and a version number included within each object.

6. The method of claim 5, further comprising:

recycling version numbers determined to be out of use.

7. The method of claim 1, further comprising:

partitioning objects identified on a list of candidate objects into contiguous object sets, wherein each candidate object is not specified by a pointer;

replacing each set of contiguous objects sets with a starting position and an ending position; and

reclaiming each set of contiguous objects as a memory gap that is available as specified by the starting position and the ending position.

8. A system comprising:

a computer readable storage medium having computer readable program code embodied therewith;

a processor coupled to the computer readable storage medium, wherein responsive to executing the computer readable program code, the processor is configured to perform executable operations for memory management comprising;

creating an initial root set of pointers for a program during execution of the program;

performing a marking process by iteratively marking referred objects of each pointer of the root sot and expanding the root set with filtered, encoded pointers;

identifying each non-live object for any marked object as red-marked;

performing a re-marking process on the root set in which red-marked objects are excluded; and

designating each object of the root set not marked as comprising a memory leak.

9. The system of claim 8, wherein the processor is further configured to execute an operation comprising:

performing the marking process until no changes are made to the root set.

10. The system of claim 8, wherein identifying each non-live object for any marked object as red-marked further comprises:

identifying objects marked during the marking process; and

subtracting objects specified on an allocated objects list from the objects that are marked.

11. The system of claim 8, wherein the processor is further configured to execute an operation comprising:

requiring each pointer generated by the program be live and inbound to a referent object.

12. The system of claim 8, wherein performing a re-marking process on the root set in which red-marked objects are excluded further comprises:

filtering pointer and object pairs according to a version number included within each pointer and a version number included within each object.

13. The system of claim 12, wherein the processor is further configured to execute an operation comprising:

recycling version numbers determined to be out of use.

14. The system of claim 8, wherein the processor is further configured to execute operations comprising:

partitioning objects identified on a list of candidate objects into contiguous object sets, wherein each candidate object is not specified by a pointer;

replacing each set of contiguous objects sets with a starting position and an ending position; and

reclaiming each set of contiguous objects as a memory gap that is available as specified by the starting position and the ending position.

15. A computer program product for memory management, the computer program product comprising:

a computer readable storage medium having computer readable program code embodied therewith, the computer readable program code comprising;

computer readable program code configured to create an initial root set of pointers for a program during execution of the program;

computer readable program code configured to perform a marking process by iteratively marking referred objects of each pointer of the root set and expanding the root set with filtered, encoded pointers;

computer readable program code configured to identify each non-live object for any marked object as red-marked;

computer readable program code configured to perform a re-marking process on the root set in which red-marked objects are excluded; and

computer readable program code configured to designate each object of the root set not marked as comprising a memory leak, wherein

the computer readable storage medium does not consist of a transitory, propagating signal.

16. The computer program product of claim 15, wherein the computer readable program code configured to identify each non-live object for any marked object as red-marked further comprises:

computer readable program code configured to identify objects marked during the marking process; and

computer readable program code configured to subtract objects specified on an allocated objects list from the objects that are marked.

17. The computer program product of claim 15, wherein the computer readable program code further comprises:

computer readable program code configured to require each pointer generated by the program be live and inbound to a referent object.

18. The computer program product of claim 15, wherein the computer readable program code configured to perform a re-marking process on the root set in which red-marked objects are excluded further comprises:

computer readable program code configured to filter pointer and object pairs according to a version number included within each pointer and aversion number included within each object.

19. The computer program product of claim 18, wherein the computer readable program code further comprises:

computer readable program code configured to recycle version numbers determined to be out of use.

20. The computer program product of claim 15, wherein the computer readable program code further comprises:

computer readable program code configured to partition objects identified on a list of candidate objects into contiguous object sets, wherein each candidate object is not specified by a pointer;

computer readable program code configured to replace each set of contiguous objects sets with a starting position and an ending position; and

computer readable program code configured to reclaim each set of contiguous objects as a memory gap that is available as specified by the starting position and the ending position.