Efficient memory allocator utilizing a dual free-list structure

• US 6,505,283 B1
• Filed: 09/30/1999
• Issued: 01/07/2003
• Est. Priority Date: 10/06/1998
• Status: Expired due to Fees

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Stoney, Graham
• Primary Examiner(s): Kim, Matthew
• Assistant Examiner(s): CHACE, CHRISTIAN
• Application Number:
  US09/409,055
• Time in Patent Office: 1,195 Days
• Field of Search: 711/128, 711/112, 711/150, 711/170, 711/171, 711/172, 710/206, 707/100
• US Class Current: 711/170
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement

Abstract

A method of dynamically allocating blocks of memory in a computer system (800) is disclosed. The method includes the following steps. Firstly, generating a first memory allocation list in which free memory blocks (S) are recorded on the basis of size. Secondly, generating a second memory allocation list in which free memory blocks (S) are recorded on the basis of memory block address (b). When a memory block (S) is requested by the computer system, searching the first list to determine a suitably sized memory block, allocating the requested memory block from the suitably sized memory block in response to the request, and updating the first and second lists to take the allocation into account. When a memory block (S) is freed by the computer system (800) it is determined whether a free memory block exists adjacent the freed memory block by searching the second list. In the event that one or more free memory blocks exist adjacent the freed memory block, the freed memory block and free memory blocks are merged together to form a unitary free memory block. Finally, the first and second lists are updated to take the freed memory block and any free memory block merges therewith into account.

Claims

1. A method of dynamically allocating blocks of memory in a computer system, the method including the steps of:

generating a first memory allocation list in which free memory blocks of any size are recorded, said first memory allocation list being ordered on the basis of size information associated with each of said free memory blocks;

generating a second memory allocation list in which said free memory blocks are recorded and ordered on the basis of memory block address information associated with each of said free memory blocks;

when a memory block request is generated by the computer system, searching a first list to determine a suitably sized memory block, allocating at least a portion of the suitably sized memory block in accordance with the request, and updating the size and address information in said first and second lists to take at least the portion allocated into account; and

when a first memory block of any size is freed by the computer system;

determining whether one or more additional free memory blocks of any size exist adjacent said first memory block by searching the second list;

in the event that one or more additional free memory blocks exist adjacent said first memory block, merging said first memory block and said additional free memory blocks together to form a unitary free memory block; and

updating said size and address information of the first and second lists to take said first memory block and any additional free memory blocks merged therewith into account.

2. A method of dynamically allocating blocks of memory according to claim 1, wherein the first and second lists are linked list data structures defined in part by a plurality of pointers.

3. A method of dynamically allocating blocks of memory according to claim 2, wherein pointers from the first and second lists are meshed to form an interconnected data structure.

4. A method of dynamically allocating blocks of memory according to claim 3, wherein the first and second lists take the form of skip-list.

5. A method of dynamically allocating blocks of memory according to claim 4, wherein the skip list defines a plurality of nodes, at least some of which define a plurality of elements having different levels, wherein each node is associated with a base memory address corresponding to a free memory block of a predetermined size, each element including a plurality of first and second pointer pairs, the first pointer in each pair pointing to a first element on the same level on the basis of address, and the second pointer in each pair pointing to a second element on the same level on the basis of block size.

6. An apparatus for dynamically allocating blocks of memory in a computer system, the apparatus including:

allocation list generating means for generating a first memory allocation list in which free memory blocks of any size are recorded, said first memory allocation list being ordered on the basis of size information associated with each of said free memory blocks and generating a second memory allocation list in which said free memory blocks are recorded and ordered on the basis of memory block address information associated with each of said free memory blocks;

searching means for searching a first list to determine a suitably sized memory block when a memory block request is generated by the computer system;

allocating means for allocating at least a portion of the suitably sized memory block in accordance with the request;

updating means for updating said size and address information in the first and second lists to take at least the portion allocated into account;

determining means for determining whether one or more additional free memory blocks of any size exist adjacent a first memory block, when said first memory block is freed by the computer system, by searching the second list utilising said searching means; and

merging means for merging said first memory block and any of said additional free memory blocks together to form a unitary free memory block, in the event that one or more additional free memory blocks exist adjacent said first memory block, wherein said updating means updates said size and address information of the first and second lists to take said first memory block and any additional free memory blocks merged therewith into account.

7. An apparatus for dynamically allocating blocks of memory according to claim 6, wherein the first and second lists are linked list data structures defined in part by a plurality of pointers.

8. An apparatus for dynamically allocating blocks of memory according claim 7, wherein pointers from the first and second lists are meshed to form an interconnected data structure.

9. An apparatus for dynamically allocating blocks of memory according to claim 8, wherein the first and second lists take the form of skip-list.

10. An apparatus for dynamically allocating blocks of memory according to claim 9, wherein the skip list defines a plurality of nodes, at least some of which define a plurality of elements having different levels, wherein each node is associated with a base memory address corresponding to a free memory block of a predetermined size, each element including a plurality of first and second pointer pairs, the first pointer in each pair pointing to a first element on the same level on the basis of address, and the second pointer in each pair pointing to a second element on the same level on the basis of block size.

11. A computer readable memory medium for storing a program for an apparatus which processes data, said processing comprising a process for dynamically allocating blocks of memory in a computer system, said program comprising:

code for generating a first memory allocation list in which free memory blocks of any size are recorded, said first memory allocation list being ordered on the basis of size information associated with each of said free memory blocks;

code for generating a second memory allocation list in which said free memory blocks are recorded and ordered on the basis of memory block address information associated with each of said free memory blocks;

code for when a memory block request is generated by the computer system, searching a first list to determine a suitably sized memory block, allocating at least a portion of the suitably sized memory block in accordance with the request, and updating the size and address information in said first and second lists to take at least the portion allocated into account; and

code for when a first memory block of any size is freed by the computer system;

determining whether one or more additional free memory blocks of any size exist adjacent said first memory block by searching the second list;

in the event that one or more additional free memory blocks exist adjacent said first memory block, merging said first memory block and said additional free memory blocks together to form a unitary free memory block; and

updating said size and address information of the first and second lists to take said first memory block and any additional free memory blocks merged therewith into account.

12. A computer readable memory medium according to claim 11, wherein the first and second lists are linked list data structures defined in part by a plurality of pointers.

13. A computer readable memory medium according claim 12, wherein pointers from the first and second lists are meshed to form an interconnected data structure.

14. A computer readable memory medium according to claim 13, wherein the first and second lists take the form of skip-list.

15. A computer readable memory medium according to claim 14, wherein the skip list defines a plurality of nodes, at least some of which define a plurality of elements having different levels, wherein each node is associated with a base memory address corresponding to a free memory block of a predetermined size, each element including a plurality of first and second pointer pairs, the first pointer in each pair pointing to a first element on the same level on the basis of address, and the second pointer in each pair pointing to a second element on the same level on the basis of block size.