Conservative garbage collectors that can be used with general memory allocators

• US 20040139272A1
• Filed: 02/20/2003
• Published: 07/15/2004
• Est. Priority Date: 09/13/2000
• Status: Active Grant

• Current Assignee: Veritas Technologies, LLC (Whitehouse Group Ltd.)
• Original Assignee: Symantec Corporation (NortonLifeLock Inc.)
• Inventors: Spertus, Michael P, Fiterman, Charles, Rodriguez-Rivera, Gustavo
• Granted Patent: US 7,051,056 B2
• Time in Patent Office: Days
• US Class Current: 711/100
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 2212/702 Conservative garbage collection
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

A technique that permits a conservative garbage collector to be used with the heap management functions provided by an allocator which is independent of the garbage collector. The allocator and the garbage collector (139) employ a malloc table (319) to exchange information about the heap (125). When the allocator determines that determines that garbage collection is required, the allocator makes a current heap map in the malloc table that specifies the location of each block in the current heap and whether the block is collectible by the garbage collector. The allocator then invokes the garbage collector, which uses the current heap map in its mark cycle to make a mark list that indicates which of the heap blocks are pointed to by apparent pointers in the processer'"'"'s address space.

Claims

1. An allocator that manages a heap of memory blocks for a process, the process employing a conservative garbage collector that is independent of the allocator to detect unused memory blocks in the heap and the allocator having the improvement comprising:

a current heap map that is accessible to the garbage collector and that indicates the location of each block in the current heap and for each block, whether the block is collectible by the garbage collector.

2. The allocator set forth in claim 1 wherein:

the allocator and the garbage collector both execute in the process and the allocator invokes the garbage collector.

3. The allocator set forth in claim 1 wherein:

the form of the current heap map is determined by the garbage collector.

4. The allocator set forth in claim 1 and having the further improvement comprising:

a blacklist that is produced by the garbage collector and accessible to the allocator, the blacklist specifying collectible potential blocks that are pointed to by false pointers and the allocator using the black list to determine whether a potential block should be allocated when the allocator expands the heap.

5. The allocator set forth in claim 4 wherein:

the current heap map includes a map of the collectible potential blocks in a heap expansion area; and

the conservative garbage collector uses the map of collectible potential blocks to determine whether apparent pointers in the process'"'"'s address space point to collectible potential blocks and marks the blacklist accordingly.

6. The allocator set forth in claim 4 wherein:

the form of the blacklist is determined by the garbage collector.

7. The allocator set forth in claim 4 wherein:

the allocator and the garbage collector both execute in the process, the allocator invokes the garbage collector, and the blacklist is available to the allocator upon return from the invocation of the garbage collector.

8. The allocator set forth in claim 4 wherein:

the blacklist is an extension of the current heap map.

9. The allocator set forth in claim 8 wherein:

the blacklist and the current heap map are implemented in a table whose form is determined by the garbage collector.

10. An allocator that manages a heap of memory blocks for a process, the process employing a conservative garbage collector that is independent of the allocator to detect unused memory blocks in the heap and the allocator having the improvement comprising:

a blacklist that is produced by the garbage collector and accessible to the allocator, the blacklist specifying collectible potential blocks that are pointed to by false pointers and the allocator using the black list to determine whether a collectible potential block should be allocated when the allocator expands the heap.

11. The allocator set forth in claim 10 wherein:

the allocator produces a map of collectible potential blocks in a heap expansion area; and

the conservative garbage collector uses the map of collectible potential blocks to determine whether apparent pointers in the process'"'"'s address space point to collectible potential blocks and marks the blacklist accordingly.

12. The allocator set forth in claim 11 wherein:

the blacklist and the map of collectible blocks have forms which are determined by the garbage collector.

13. The allocator set forth in claim 10 wherein:

the form of the blacklist is determined by the garbage collector.

14. The allocator set forth in claim 10 wherein:

the allocator and the garbage collector both execute in the process, the allocator invokes the garbage collector, and the blacklist is available to the allocator upon return from the invocation of the garbage collector.

15. A conservative garbage collector that detects unused memory blocks in a heap that is managed by an allocator for a process, the allocator being independent of the garbage collector and

the garbage collector having the improvement comprising:

a current heap map that is made by the allocator and accessible to the garbage collector, the current heap map indicating for each block in the current heap the block'"'"'s location and whether the block is collectible by the garbage collector, the garbage collector using the current heap map to determine whether apparent pointers in the process'"'"'s address space point to collectible blocks in the current heap and marking a mark list accordingly.

16. The conservative garbage collector set forth in claim 15 wherein:

the allocator has a free operation that returns a block in the current heap to a free list, the free operation being accessible to the garbage collector and the garbage collector using the free operation to return any collectible block in the current heap to the free list when the mark list indicates that the collectible block is not pointed to by an apparent pointer.

17. The conservative garbage collector set forth in claim 16 wherein:

the conservative garbage collector and the allocator are executed by the process;

the allocator invokes the garbage collector; and

the garbage collector invokes the free operation.

18. The conservative garbage collector set forth in claim 15 wherein:

the mark list is implemented in the current heap map.

19. The conservative garbage collector set forth in claim 15 wherein:

the conservative garbage collector determines the form of the current heap map.

20. The conservative garbage collector set forth in claim 15 wherein:

the current heap map includes a map of potential blocks in a heap expansion area; and

the conservative garbage collector uses the map of potential blocks to determine whether apparent pointers in the process'"'"'s address space point to potential blocks and marks a blacklist that is accessible to the allocator accordingly.

21. The conservative garbage collector set forth in claim 20 wherein:

the conservative garbage collector determines the form of the blacklist.

22. The conservative garbage collector set forth in claim 21 wherein:

the blacklist is implemented in the current heap map.

23. A data structure that an allocator and a conservative garbage collector that is independent of the allocator use to exchange information about a heap of memory blocks that the allocator manages for a process,

the data structure comprising:

a current heap map that is made by the allocator, the current heap map including for each block in the current heap

a location specifier for the block and

a first status specifier that indicates whether the block is collectible by the garbage collector,

the garbage collector using the current heap map to determine whether a block has an apparent pointer pointing thereto.

24. The data structure set forth in claim 23 further comprising:

a second status specifier for each block in the current heap that indicates whether a block which the first status specifier specifies is collectible is pointed to by an apparent pointer, the garbage collector scanning data in the process address space for apparent pointers and upon finding an apparent pointer that points to a given collectible block, ensuring that the second status specifier for the given collectible block so indicates and using the second status specifier to determine which blocks in the current heap may be collected.

25. The data structure set forth in claim 24 wherein:

the current heap map further comprises;

an extended heap map including for each potential block in a heap expansion area

the location specifier for the potential block,

the first status specifier for the potential block, and

the second status specifier for the potential block,

the allocator using the extended heap map to determine whether a block should be allocated when the heap is expanded into the heap expansion area.

26. A method employed in a conservative garbage collector to determine whether a block in a heap managed for a process by an allocator that is independent of the garbage collector is in use,

the method comprising the steps of:

finding an apparent pointer in the process'"'"'s address space;

accessing a current heap map that is made by the allocator and indicates for each block in the current heap the block'"'"'s location and whether the block is collectible by the garbage collector to determine whether the apparent pointer points to a collectible block in the current heap; and

when the apparent pointer points to the collectible block, ensuring that a mark list is marked accordingly.

27. The method set forth in claim 26 further comprising the step of:

when the mark list indicates that the collectible block is not pointed to by an apparent pointer, freeing the collectible block.

28. The method set forth in claim 27 wherein:

the allocator includes a free operation; and

the step of freeing the collectible block is performed using the free operation.

29. The method set forth in claim 26 wherein:

the method commences upon invocation of the garbage collector by the allocator.

30. The method set forth in claim 26 wherein:

the current heap map further indicates for each potential block in a heap expansion area the block'"'"'s location and whether the block is collectible by the garbage collector; and

when the apparent pointer points to a collectible potential block, ensuring that a blacklist is marked accordingly.

31. A method employed in an allocator that manages a heap for a process of using a conservative garbage collector that is independent of the allocator to determine whether a block in the heap is in use,

the method comprising the steps of:

making a current heap map that is accessible to the conservative garbage collector and indicates for each block in the current heap the block'"'"'s location and whether the block is collectible by the garbage collector; and

causing the conservative garbage collector to commence operation using the current heap map.

32. The method set forth in claim 31 wherein:

the allocator includes an externally-available free operation that frees blocks in the heap; and

the method includes the step of freeing blocks in response to use of the free operation by the conservative garbage collector.

33. The method set forth in claim 31 wherein:

during execution, the conservative garbage collector makes a blacklist of blocks in an extension of the current heap, the blacklist indicating blocks that should not be allocated by the allocator; and

the method includes the step performed when the allocator expands the heap into the extension of not placing blocks on the blacklist on the free list.