Heap management using dynamic memory allocation

• US 9,389,997 B2
• Filed: 04/24/2013
• Issued: 07/12/2016
• Est. Priority Date: 04/24/2013
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Winn, Geoffrey M.
• Primary Examiner(s): Rones, Charles
• Assistant Examiner(s): Li, Sidney
• Application Number:
  US13/869,505
• Publication Number:
  US 20140325177A1
• Time in Patent Office: 1,175 Days
• Field of Search: 711/170, 711/173
• US Class Current: 1/1
• CPC Class Codes: G06F 12/023 Free address space management

Abstract

Embodiments of the present invention provide a method, system, and program product for heap management using dynamic memory allocation. The method comprises receiving, via a computing device, a memory request associated with a memory block, wherein the computing device has a double linked list of fixed sized memory blocks and a double linked list of variable sized memory blocks; and wherein each memory block includes a value field and a header field, which includes one or more of a backward link, forward link, and memory block size indicator that includes a first bit and a second bit. The method further comprises determining a scope of the received memory request, which can be a request for memory allocation or memory deallocation. Further still, the method comprises servicing the received memory request.

Claims

1. A method, the method comprising:

receiving, via a computing device, a memory request associated with a memory block, wherein the computing device has a double linked list of fixed sized memory blocks and a double linked list of variable sized memory blocks; and

wherein each memory block included in the double linked list of fixed sized memory blocks and a double linked list of variable sized memory blocks includes a value field and a header field;

wherein the header fields includes one or more of a backward link, forward link, and memory block size indicator; and

wherein the memory block size indicator includes a first bit that reflects whether the value field includes a start address of another memory block that precedes the memory block in memory address and a second bit that reflects whether the memory block is in use by a process associated with the computing device;

determining a scope of the received memory request, wherein the scope of the received memory request is a request for memory allocation or memory deallocation; and

servicing, in response to the determining the scope of the received memory request, the received memory request.

2. The method of claim 1, wherein servicing the received memory request includes setting the second bit to reflect that the memory block is in use, in response to determining that the scope of the received memory request is a request for memory allocation.

3. The method of claim 1, wherein servicing the received memory request includes setting the first bit to reflect whether the address of the other memory block that precedes the memory block in memory is included in value field, in response to determining that the scope of the received memory request is a request for memory allocation.

4. The method of claim 1, wherein servicing the received memory request includes determining whether a size of the received memory request is at least a threshold size compared to a predetermined memory block that satisfies the received memory request.

5. The method of claim 1, wherein servicing the received memory request includes returning the memory block to the linked list of fixed sized memory blocks, in response to determining that the first bit reflects that the address of the other memory block that precedes the memory block in memory is included in value field and determining that the scope of the received memory request is a request for memory deallocation.

6. The method of claim 1, wherein servicing the received memory request includes merging the memory block with the other memory block, in response to determining that the first bit reflects that the address of the other memory block that precedes the memory block in memory is included in the value field and determining that the scope of the received memory request is a request for memory deallocation.

7. A computer program product, the computer program product comprising:

one or more computer-readable storage media and program instructions stored on the one or more computer-readable storage media, the program instructions comprising;

program instructions to receive a memory request associated with a memory block, wherein a computing device configured to execute the computer program product has a double linked list of fixed sized memory blocks and a double linked list of variable sized memory blocks; and

wherein each memory block included in the double linked list of fixed sized memory blocks and a double linked list of variable sized memory blocks includes a value field and a header field;

wherein the header fields includes one or more of a backward link, forward link, and memory block size indicator; and

wherein the memory block size indicator includes a first bit that reflects whether the value field includes a start address of another memory block that precedes the memory block in memory address and a second bit that reflects whether the memory block is in use by a process associated with the computing device;

program instructions to determine a scope of the received memory request, wherein the scope of the received memory request is a request for memory allocation or memory deallocation; and

program instructions to service, in response to the program instructions to determine the scope of the received memory request, the received memory request.

8. The computer program product of claim 7, wherein the program instructions to service the received memory request includes program instructions to set the second bit to reflect that the memory block is in use, in response to the program instructions to determine that the scope of the received memory request is a request for memory allocation.

9. The computer program product of claim 7, wherein the program instructions to service the received memory request includes program instructions to set the first bit to reflect whether the address of the other memory block that precedes the memory block in memory is included in value field, in response to the program instructions to determine that the scope of the received memory request is a request for memory allocation.

10. The computer program product of claim 7, wherein the program instructions to service the received memory request includes program instructions to determine whether a size of the received memory request is at least a threshold size compared to a predetermined memory block that satisfies the received memory request.

11. The computer program product of claim 7, wherein the program instructions to service the received memory request includes program instructions to return the memory block to the linked list of fixed sized memory blocks, in response to program instructions to determine that the first bit reflects that the address of the other memory block that precedes the memory block in memory is included in value field and program instructions to determine that the scope of the received memory request is a request for memory deallocation.

12. The computer program product of claim 7, wherein the program instructions to service the received memory request includes program instructions to merge the memory block with the other memory block, in response to the program instructions to determine that the first bit reflects that the address of the other memory block that precedes the memory block in memory is included in the value field and the program instructions to determine that the scope of the received memory request is a request for memory deallocation.

13. A computer system, the computer system comprising:

one or more computer processors;

one or more computer-readable storage media;

program instructions stored on the computer-readable storage media for execution by at least one of the one or more processors, the program instructions comprising;

program instructions to receive a memory request associated with a memory block, wherein a computing device configured to execute the computer program product has a double linked list of fixed sized memory blocks and a double linked list of variable sized memory blocks; and

wherein each memory block included in the double linked list of fixed sized memory blocks and a double linked list of variable sized memory blocks includes a value field and a header field;

wherein the header fields includes one or more of a backward link, forward link, and memory block size indicator; and

wherein the memory block size indicator includes a first bit that reflects whether the value field includes a start address of another memory block that precedes the memory block in memory address and a second bit that reflects whether the memory block is in use by a process associated with the computing device;

program instructions to determine a scope of the received memory request, wherein the scope of the received memory request is a request for memory allocation or memory deallocation; and

program instructions to service, in response to the program instructions to determine the scope of the received memory request, the received memory request.

14. The computer system of claim 13, wherein the program instructions to service the received memory request includes program instructions to set the second bit to reflect that the memory block is in use, in response to the program instructions to determine that the scope of the received memory request is a request for memory allocation.

15. The computer system of claim 13, wherein the program instructions to service the received memory request includes program instructions to set the first bit to reflect whether the address of the other memory block that precedes the memory block in memory is included in value field, in response to the program instructions to determine that the scope of the received memory request is a request for memory allocation.

16. The computer system of claim 13, wherein the program instructions to service the received memory request includes program instructions to determine whether a size of the received memory request is at least a threshold size compared to a predetermined memory block that satisfies the received memory request.

17. The computer system of claim 13, wherein the program instructions to service the received memory request includes program instructions to return the memory block to the linked list of fixed sized memory blocks, in response to program instructions to determine that the first bit reflects that the address of the other memory block that precedes the memory block in memory is included in value field and program instructions to determine that the scope of the received memory request is a request for memory deallocation.

18. The computer system of claim 13, wherein the program instructions to service the received memory request includes program instructions to merge the memory block with the other memory block, in response to the program instructions to determine that the first bit reflects that the address of the other memory block that precedes the memory block in memory is included in the value field and the program instructions to determine that the scope of the received memory request is a request for memory deallocation.