MANAGING OBJECTS STORED IN MEMORY

• US 20170344473A1
• Filed: 05/27/2016
• Published: 11/30/2017
• Est. Priority Date: 05/27/2016
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Inventors: Gidra, Lokesh, Kirshenbaum, Evan R.
• Granted Patent: US 9,846,645 B1
• Time in Patent Office: Days
• CPC Class Codes: G06F 12/0261 using reference counting
• 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 2212/1044 Space efficiency improvement

Abstract

In one example in accordance with the present disclosure, a method for managing objects stored in memory may include identifying a first object in a heap. The heap may be accessed by a plurality of mutator threads executing within a first plurality of operating system processes. The method may also include determining that the first object is a reachable object and determining that a first range of memory locations in the heap does not contain any reachable object. The method may also include receiving an allocation request from a second mutator thread from the plurality of mutator threads and allocating a first free chunk of memory including at least a part of the first range of memory locations to the second mutator thread.

Claims

1. A method comprising:

identifying a first object in a heap, wherein the heap is accessed by a plurality of mutator threads executing within a first plurality of operating system processes and each mutator thread in the plurality has a corresponding garbage collection thread from a plurality of garbage collection threads executing within a second plurality of operating system processes;

determining, based on a root pointer associated with a first mutator thread from the plurality of mutator threads, that the first object is a reachable object;

determining, based on a marking phase of a garbage collection cycle, that a first range of memory locations in the heap does not contain any reachable object;

receiving an allocation request from a second mutator thread from the plurality of mutator threads; and

allocating, responsive to the allocation request, a first free chunk of memory, including at least a part of the first range of memory locations, to the second mutator thread.

2. The method of claim 1, further comprising:

identifying, during a sweeping phase of the garbage collection cycle, a plurality of sweeping threads from a group of threads, the groups of threads including the plurality of mutator threads and the plurality of garbage collection threads;

assigning, to a sweeping thread belonging to the plurality of sweeping threads, a second range of memory locations in the heap;

identifying, by the sweeping thread, a second free chunk of memory beginning within the second range of memory locations; and

making the second free chunk available to an allocator.

3. The method of claim 1, wherein each operating system process from the first and second pluralities of operating system processes stores an associated state of the process in a non-volatile memory, the method further comprising:

determining, in a first garbage collection thread based on the stored state of a first operating system process from the first and second pluralities of operating system processes, that the first operating system process has terminated; and

performing, in a second garbage collection thread, work of the first operating system process using the state of the first operating system process stored in the non-volatile memory.

4. The method of claim 1, further comprising, for each garbage collection thread belonging to the plurality garbage collection thread:

making a first determination that there are no available references for the garbage collection thread to mark;

indicating the first determination in the non-volatile memory;

making a second determination that all garbage collection threads in the plurality of garbage collection threads have indicated and not revoked the first determination;

indicating the second determination in the non-volatile memory;

making a third determination that all garbage collection threads in the plurality of garbage collection threads have indicated and not revoked the second determination; and

determining that the marking phase has ended.

5. The method of claim 1, further comprising:

enumerating a pointer stored within the first object by reference to an object descriptor associated with the first object;

determining that the pointer points to a second object in the heap; and

determining that the second object is a reachable object.

6. The method of claim 1, further comprising:

identifying a potential object pointer associated with a potential object descriptor;

determining that the potential object descriptor is not a valid object descriptor; and

determining that the potential object pointer is not a pointer into the heap.

7. The method of claim 1, further comprising:

adding, during the garbage collection cycle, a first new process to the first plurality of operating system processes and a second new process to the second plurality of operating system processes;

adding a new mutator thread executing in the first new process to the plurality of mutator threads;

receiving an allocation request from the new mutator thread;

completing the allocation request prior to the end of the garbage collection cycle;

adding a new garbage collection thread executing in the second new process to the plurality of garbage collection threads; and

assisting, by the new garbage collection thread, the completion of the garbage collection cycle.

8. The method of claim 1, further comprising:

identifying a second range of memory locations in the heap corresponding to a free chunk contained within a previous global allocator;

determining that a third range of memory locations in the heap adjacent to the second range of memory locations does not contain any reachable object;

expanding the second range of memory locations to a fourth range of memory locations in the heap including at least the second range of memory locations and the third range of memory locations; and

adding the fourth range of memory locations to an allocator.

9. The method of claim 1, wherein a plurality of garbage collection process cooperatively coordinate to execute a garbage collection process.

10. The method of claim 1, further comprising:

identifying a root pointer source object that is not stored on a program stack;

enumerating root pointers based on the root pointer source object; and

determining that objects in the heap pointed to by enumerated root pointers are reachable objects.

11. A system comprising:

a notifier to notify a first mutator process thread belonging to a plurality of mutator process threads that a garbage collection cycle has begun, wherein each mutator process thread in the plurality has access to objects located in a heap in a memory;

a process handler to pause normal operation of the first mutator process thread so that the garbage collection cycle can proceed, wherein the normal operation is paused by a time period that is not proportional to a total number of live objects in the heap;

an object identifier to identify a first object in the heap, the object belonging to the total number of live objects in the heap;

an object reachability determiner to determine, based on a root pointer associated with a first mutator thread from the plurality of mutator threads, that the first object is a reachable object;

a memory reachability determiner to determine that a first range of memory locations in the heap does not contain any reachable object; and

a memory identifier to identify a first free chunk of memory including at least a part of the first range of memory locations.

12. The system of claim 11 wherein the time period is proportional to a stack size of the first mutator process.

13. A non-transitory machine-readable storage medium comprising instructions executable by a processor of a computing device, the machine-readable storage medium comprising instructions to:

identify a first object in a heap, wherein the heap is accessed by a plurality of mutator threads and a plurality of garbage collection threads;

determine based on a root pointer associated with a first mutator thread from the plurality of mutator threads that the first object is a reachable object;

determine based on a marking phase of a garbage collection cycle performed by a first garbage collection thread belonging to the plurality of garbage collection threads that a first range of memory locations in the heap does not contain any reachable object;

increment a shared counter upon completion of the marking phase by the first garbage collection thread; and

identify a first free chunk of memory including at least a part of the first range of memory locations.

14. The non-transitory machine-readable storage medium of claim 13 further comprising instructions to:

store a start time and a state of the first garbage collection thread on a non-volatile memory.

15. The non-transitory machine-readable storage medium of claim 14 further comprising instructions to:

determine, by a second garbage collection thread, that the shared counter has not yet reached a total number of processes;

determine, based on the start time, that the first garbage collection thread has terminated;

perform, by a second garbage collection thread, work of the first garbage collection thread using the state of the process stored in the non-volatile memory; and

adjust the total number of processes upon completion of the work of the first garbage collection process.