Method and system for selective memory coalescing across memory heap boundaries

• US 20050066143A1
• Filed: 09/18/2003
• Published: 03/24/2005
• Est. Priority Date: 09/18/2003
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Schopp, Joel H.
• Granted Patent: US 7,100,009 B2
• Time in Patent Office: Days
• US Class Current: 711/170
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

A method and system for efficient coalescing of memory blocks across memory heap boundaries in multiprocessor or multithread computer system. Blocks of memory are allocated into multiple heaps for exclusive utilization by separate processors or processes. Varying memory requirements result in fragmentation and increased memory utilization over time and coalescing of memory is necessary. An identification of each memory heap which contains a preceding adjacent memory block and a succeeding adjacent memory block is maintained for all memory blocks. Thereafter, each time a memory block is freed it may be coalesced across heap boundaries with an adjacent preceding or succeeding memory block by temporarily locking access to only those memory heaps containing a free preceding or succeeding adjacent memory block.

Claims

1. A method for selected memory coalescing across memory heap boundaries in a computer system having a plurality of allocated memory heaps, said method comprising the steps of:

maintaining an identification of an allocated memory heap containing a preceding adjacent block of memory and an identification of an allocated memory heap containing a succeeding adjacent block of memory for each block of memory within said plurality of allocated memory heaps;

determining a usage state of both a preceding adjacent block of memory and a succeeding adjacent block of memory in response to a freeing of a selected block of memory;

temporarily locking access to only those allocated memory heaps containing a free preceding or a free succeeding adjacent block of memory for said selected block of memory;

coalescing said selected block of memory with a free preceding adjacent block of memory and/or a free succeeding adjacent block of memory;

updating said maintained identification of allocated memory heaps containing said preceding adjacent block of memory and said succeeding adjacent block of memory to reflect said coalescing; and

releasing said temporarily locked access.

2. The method for selected memory coalescing according to claim 1 wherein said step of coalescing said selecting block of memory with a free preceding adjacent block of memory and/or a free succeeding adjacent block of memory comprises the step of coalescing said selected block of memory into a single allocated memory heap containing both a free preceding adjacent block of memory and a free succeeding adjacent block of memory.

3. The method for selected memory coalescing according to claim 1 wherein said step of coalescing said selecting block of memory with a free preceding adjacent block of memory and/or a free succeeding adjacent block of memory comprises the step of coalescing said selected block of memory with the larger of a free preceding adjacent block of memory and a free succeeding adjacent block of memory in response to a location of said free preceding adjacent block of memory and said free succeeding adjacent block of memory in two different allocated memory heaps.

4. The method for selected memory coalescing according to claim 1 wherein said computer system is a multiprocessor computer and wherein said method further includes the step of allocating a memory heap to each processor within said multiprocessor computer system.

5. The method for selected memory coalescing according to claim 1 wherein said computer system is a multithread computer system and wherein said method further includes the step of allocating a memory heap to each thread within said multithread computer system.

6. A system for selected memory coalescing across memory heap boundaries in a computer system having a plurality of allocated memory heaps, said system comprising:

means for maintaining an identification of an allocated memory heap containing a preceding adjacent block of memory and an identification of an allocated memory heap containing a succeeding adjacent block of memory for each block of memory within said plurality of allocated memory heaps;

means for determining a usage state of both a preceding adjacent block of memory and a succeeding adjacent block of memory in response to a freeing of a selected block of memory;

means for temporarily locking access to only those allocated memory heaps containing a free preceding or a free succeeding adjacent block of memory for said selected block of memory;

means for coalescing said selected block of memory with a free preceding adjacent block of memory and/or a free succeeding adjacent block of memory;

means for updating said maintained identification of allocated memory heaps containing said preceding adjacent block of memory and said succeeding adjacent block of memory to reflect said coalescing; and

means for releasing said temporarily locked access.

7. The system for selected memory coalescing according to claim 6 wherein said means for coalescing said selecting block of memory with a free preceding adjacent block of memory and/or a free succeeding adjacent block of memory comprises means for coalescing said selected block of memory into a single allocated memory heap containing both a free preceding adjacent block of memory and a free succeeding adjacent block of memory.

8. The system for selected memory coalescing according to claim 6 wherein said means for coalescing said selecting block of memory with a free preceding adjacent block of memory and/or a free succeeding adjacent block of memory comprises means for coalescing said selected block of memory with the larger of a free preceding adjacent block of memory and a free succeeding adjacent block of memory in response to a location of said free preceding adjacent block of memory and said free succeeding adjacent block of memory in two different allocated memory heaps.

9. The system for selected memory coalescing according to claim 6 wherein said computer system is a multiprocessor computer and wherein said system further includes means for allocating a memory heap to each processor within said multiprocessor computer system.

10. The system for selected memory coalescing according to claim 6 wherein said computer system is a multithread computer system and wherein said system further includes means for allocating a memory heap to each thread within said multithread computer system.

11. A computer program product for selected memory coalescing across memory heap boundaries in a computer system having a plurality of allocated memory heaps, said computer program product comprising:

computer readable media;

instruction means embodied within said computer readable media for maintaining an identification of an allocated memory heap containing a preceding adjacent block of memory and an identification of an allocated memory heap containing a succeeding adjacent block of memory for each block of memory within said plurality of allocated memory heaps;

instruction means embodied within said computer readable media for determining a usage state of both a preceding adjacent block of memory and a succeeding adjacent block of memory in response to a freeing of a selected block of memory;

instruction means embodied within said computer readable media for temporarily locking access to only those allocated memory heaps containing a free preceding or a free succeeding adjacent block of memory for said selected block of memory;

instruction means embodied within said computer readable media for coalescing said selected block of memory with a free preceding adjacent block of memory and/or a free succeeding adjacent block of memory;

instruction means embodied within said computer readable media for updating said maintained identification of allocated memory heaps containing said preceding adjacent block of memory and said succeeding adjacent block of memory to reflect said coalescing; and

instructions means embodied within said computer readable media for releasing said temporarily locked access.

12. The computer program product for selected memory coalescing according to claim 11 wherein said instruction means for coalescing said selecting block of memory with a free preceding adjacent block of memory and/or a free succeeding adjacent block of memory comprises instruction means for coalescing said selected block of memory into a single allocated memory heap containing both a free preceding adjacent block of memory and a free succeeding adjacent block of memory.

13. The computer program product for selected memory coalescing according to claim 11 wherein said instruction means for coalescing said selecting block of memory with a free preceding adjacent block of memory and/or a free succeeding adjacent block of memory comprises the instruction means for coalescing said selected block of memory with the larger of a free preceding adjacent block of memory and a free succeeding adjacent block of memory in response to a location of said free preceding adjacent block of memory and said free succeeding adjacent block of memory in two different allocated memory heaps.

14. The computer program product for selected memory coalescing according to claim 11 wherein said computer system is a multiprocessor computer and wherein said computer program product further includes instruction means for allocating a memory heap to each processor within said multiprocessor computer system.

15. The computer program product for selected memory coalescing according to claim 11 wherein said computer system is a multithread computer system and wherein said computer program product further includes instruction means for allocating a memory heap to each thread within said multithread computer system.