Computer method and system for allocating and freeing memory utilizing segmenting and free block lists

A memory management system for managing a computer memory comprising:

• a block area comprising a plurality of free blocks and a plurality of allocated blocks, the block area being subdivided into a plurality of segments;
• a free list for each segment, wherein the free list is a list of the free blocks in the segment, the blocks that make up the free list being positioned within the free list according to block size;
• a free block array having an entry corresponding to each segment in the block area, each entry containing a pointer to the free list for the corresponding segment;
• a size tree comprising at least one non-leaf node and a plurality of leaf nodes, each non-leaf node having a plurality of child nodes, each node having a value, each leaf node corresponding to a plurality of entries in the free block array and having a value indicating the size of the largest free block in the segments corresponding to the plurality of entries, wherein the value of each non-leaf node is equal to the largest value of its child nodes;
• and
• a memory manager for receiving a request to allocate a block with a request size, traversing the size tree to select an entry in the free block array, following the pointer stored in the selected entry to a free list for a particular segment, and searching the free list for the particular segment to locate a free block beginning in the particular segment and having a size large enough to satisfy the request.

A computer memory management system comprising:

• a heap of memory logically subdivided into segments, each segment including a plurality of free blocks and allocated blocks, each free block and allocated block having a block size;
• a free list for each segment, each free list comprising a linked list of free blocks in that segment, the free blocks being ordered in the linked list by block size;
• a free block array having one entry for each segment in the heap, each entry comprising a pointer to a first free block within the free list for that segment;
• a size tree for organizing block sizes of first free blocks, the size tree having non-leaf nodes and leaf nodes, each non-leaf node having a plurality of child nodes, each non-leaf node having a value such that the value of each non-leaf node is equal to the largest value of its child nodes, and each leaf node corresponding to an entry in the free block array and having a value indicating the size of the largest first free block in the segment corresponding to the entry;
• means for traversing the size tree to select an entry in the free block array, the entry corresponding to a particular segment;
• and
• means for following the pointer stored in the selected entry to a first free block within the free list for said particular segment.

In a computer system having memory and executing at least one program, a method of dynamically managing the allocation and freeing of memory within a heap of memory of the system, the heap having a plurality of free blocks and a plurality of allocated blocks, the heap being logically subdivided into a plurality of segments, each block being associated with a segment, the number of segments being a power of two and each segment having a free list, the free list linking the free blocks associated with the segment according to a size ordering and being accessible through a size tree and a free block list, the free block list having a plurality of entries, each entry corresponding to a segment and pointing to the free list for the segment, the size tree having a root node, a plurality of child nodes, and a plurality of leaf nodes, each node having a value such that the nodes of the size tree are arranged as a complete binary tree wherein the value of each node is not exceeded by the value of its child nodes, and each leaf node corresponding to two entries in the free block list and having a value indicating the size of the largest free block associated with the segments corresponding to the entries, the method comprising the steps of:

• in response to a request issued by a program executing in the computer system, selecting a free block of memory of a requested size from the heap for allocation to the requesting program, wherein the free block is selected by searching the size tree and free block list to locate a segment with which is associated a free block that satisfies the request and then searching the free list corresponding to the selected segment to locate the smallest free block of the free list that satisfies the request;
• in response to a request issued by a program executing in the computer system, freeing an allocated block of memory and consolidating the newly freed block with any free blocks that are located immediately adjacent in memory to the newly freed block;
• and
• in response to a request issued by a program executing in the computer system, when the heap does not contain a free block of the requested size, creating a free block having a size that is greater than or equal to the requested size.

In a computer system, a method of allocating free memory from a heap of memory, the method comprising the steps of:

• dividing the heap into a plurality of segments, each segment having a fixed size;
• further dividing the heap into a plurality of blocks, each block having a starting address, each block being associated with the segment within which said block has its starting address, each block having an associated state variable, the state variable indicating whether the block is free or allocated, a block whose associated state variable has a value of free being called a free block;
• providing for each segment a free list, the free list comprising a size-ordered linked list of free blocks having starting addresses within the segment;
• providing a size tree for classifying segments according to the size of a largest free block having a starting address within each segment;
• providing a collection of pointers accessible via a traversal of the size tree, each pointer pointing to the free list provided for a segment, the pointers of the collection corresponding one-for-one with the segments of the plurality;
• receiving a memorial allocation request from a requesting program executing in the computer system, the request including a requested size;
• and
• responsively to the received request,
• traversing the size tree to find a segment containing a block of size greater than or equal to the requested size,
• following a pointer of the collection for the found segment to reach the free list for that segment,
• searching the free list thus reached according to the size ordering of the free list thus reached to select a free block of size greater than or equal to the requested size,
• allocating to the requesting program a block comprising a portion of the selected block, the portion being of size greater than or equal to the requested size, and
• changing the state variable value of the allocated block from free to allocated.