Method for heap management
View Patent ↗A bitmask array is implemented as a two dimensional bit array where each bit represents an allocated/free cell of the heap. Groups of bits of the bitmask array are assigned to implement commonly sized memory cell allocation requests. The heap manager keeps track of allocations by keeping separate lists of which groups are being used to implement commonly sized memory cell allocations requests by maintaining linked lists according to the number of cells allocated per request. Each list contains a list of the bit groups that have been used to provide allocations for particularly sized requests. By maintaining lists based on allocation size, the heap manager is able to cause new allocation requests to be matched up with previously retired allocations of the same size. Memory may be dynamically allocated between lists of differently sized memory requests.
1. A method for heap management, the method comprising the steps of:
implementing a bitmap in which each bit in the bitmap represents a memory cell of the heap;
forming logical groups of bits from the bitmap, each of the logical groups of bits representing an area of the heap sufficiently large to be used to allocate memory cells in response to multiple memory allocation requests;
implementing a set of memory size specific linked lists, each of the linked lists referencing sets of the logical groups of bits that are being used to allocate memory cells from the heap for differently sized memory cell allocation requests;
implementing a free linked list referencing a subset of the logical groups of bits that are not referenced in any of the set of memory size specific linked lists; and
dynamically moving logical groups of bits from the free linked list to the sets of memory size specific linked lists as needed;
moving one of the logical groups of bits from one of the set of memory size specific linked lists to the free linked list when no memory cells are allocated from memory cells associated with the one of the logical groups of bits;
wherein the logical groups of bits are predetermined size groups of contiguous bits of the bitmap.
2. The method of claim 1 , wherein the logical groups of bits are rows of the bitmap.
3. The method of claim 1 , wherein the set of memory size specific linked lists includes:
a first memory size specific linked list used to allocate memory cells for memory cell allocation requests for one memory cell;
a second memory size specific linked list used to allocate memory cells for memory cell allocation requests for two memory cells; and
a third memory size specific linked list used to allocate memory cells for memory cell allocation requests for three memory cells.
4. The method of claim 1 , wherein the set of memory size specific linked lists includes m memory size specific linked lists, each of the m memory size specific linked lists being used to allocate memory cells for memory cell allocation requests for a respective memory cell allocation size between 1 and m memory cells.
5. The method of claim 1 , wherein each of the memory size specific linked lists includes a partially allocated linked list and a fully allocated linked list, the partially allocated linked list including references to groups of bits representing memory cells from which a group of contiguous memory cells of the respective memory cell allocation size exists, and the fully allocated linked list including references to groups of bits representing memory cells from which a group of contiguous memory cells of the respective memory cell allocation size is not available.
6. A method of heap management, comprising:
receiving a request for memory allocation, the request having a size indicating a number of contiguous memory cells required to fulfill the request;
accessing a data structure specific to the size and containing references to logical groups of memory cells used by a heap management system to fulfill requests only of the size; and
determining whether a set of contiguous memory cells of the size requested is available from one of the logical groups of memory cells referenced by the data structure;
if the set of contiguous memory cells of the size requested is available from the one of the logical groups of memory cells referenced by the data structure, then allocating the set of contiguous memory cells of the size requested from the one of the logical groups of memory cells; and
if none of the logical groups of memory cells referenced by the data structure has an available set of contiguous memory cells of the size requested, then allocating an additional logical group of memory cells to the data structure, and allocating the set of contiguous memory cells of the size requested from the additional logical group of memory cells;
wherein each of the logical groups of memory cells represents an area of the heap sufficiently large to be used to allocate memory cells in response to multiple memory allocation requests;
wherein the data structure containing references to logical groups of memory cells is a linked list referencing logical groups of bits of a bitmap in which each bit of the bitmap is used to identify a memory cell of the heap; and
wherein the logical groups of bits are predetermined size groups of contiguous bits of the bitmap.
7. The method of claim 6 , wherein the heap management system maintains a separate data structure for each size request supported by the heap management system to separately keep track of memory allocations according to the sizes of the memory allocation requests.
8. The method of claim 6 , wherein the logical groups of bits are rows of the bitmap.
9. A method of keeping track of memory allocations according to memory allocation request size, the method comprising the steps of:
implementing a bitmap array in which each bit of the bitmap array corresponds with a cell of memory;
maintaining a set of size specific data structures, each size specific data structure being used to keep track of portions of memory that are allocated in response to memory allocation requests of a respective unique memory allocation request size;
maintaining a free data structure, the free data structure being used to keep track of portions of memory that are not allocated to any of the size specific data structure in the set of size specific data structures;
dynamically moving references to portions of memory from the free data structure to the size specific data structures in the set of size specific data structures as the size specific data structures in the set of size specific data structures require access to additional memory; and
dynamically moving references to portions of memory from the size specific data structures in the set of size specific data structures to the free data structure when no memory allocations are associated with the portions of memory; and
upon receipt of a memory allocation request:
determining a size of the memory allocation request, and
allocating memory in response to the memory allocation request from the portion of memory associated with the size specific data structure being used to keep track of memory allocationa requests of the memory allocation request size;
wherein each of the portions of memory represents an area of the memory sufficiently large to be used to allocate memory cells in response to multiple memory allocation requests;
wherein each size specific data structure keeps track of a portion of memory by referencing logical groups of bits of the bitmap array; and
wherein the logical groups of bits are predetermined size groups of contiguous bits of the bitmap array.
10. The method of claim 9 , wherein the logical groups of bits are rows of the bitmap array.
11. The method of claim 9 , wherein each data structure is a linked list of logical groups of bits of the bitmap array.
12. The method of claim 11 , wherein each size specific data structure includes a partially allocated linked list and a fully allocated linked list, the partially allocated linked list containing a linked list of logical groups of bits of the bitmap array in which contiguous sets of bits of the size is available to be used to allocate memory for a memory for the request size, and the fully allocated linked list containing a linked list of logical groups of bits of the bitmap array in which no contiguous sets of bits of the size is available to be used to allocate memory for a memory for the request size.
13. The method of claim 12 , further comprising moving one of the logical groups of bits of the bitmap array from the fully allocated linked list to the partially allocated linked list upon release of memory previously allocated from memory associated with the one of the logical groups of bits of the bitmap array.