Method for implementing dual link list structure to enable fast link-list pointer updates
View Patent ↗A method is disclosed for free memory allocation in a linked list memory scheme. Free lists are link lists designating available memory for data storage. This method leverages the ability to read memory while concurrently updating a pointer to the next location. Multiple free lists are used to reduce the number of cycles necessary to allocate memory. The number of entries in each free list is tracked. When memory becomes available, it is spliced into the shortest free list to achieve balance between the free lists. The free list structure disclosed consists of head, head +1, and tail pointers where head +1 is the next logical address pointed to from the head pointer location. The free list consists only of the head and tail pointers. Each link list structure of memory to be freed contains the head, head +1, and tail pointers. This allows us to simultaneously allocate and free with only 1 memory cycle. This structure provides the ability to free and allocate memory for further processing without executing the allocate step. A whole logical data packet can be spliced into a free list in one processing cycle. Utilization of the dual link lists reduces the bandwidth requirements for free memory allocation. Balancing of these dual lists is achieved by splicing a freed block of memory into the shortest list. The splicing method disclosed also reduces the processing cycles necessary to allocate and free memory.
1. A method for managing data storage in a memory, comprising:
creating at least two free link lists having entries designating available free memory locations;
tracking the number of entries in each of the free link lists;
identifying free memory locations as such locations become available for data storage; and
splicing available memory locations onto the shortest one of the free link lists.
2. The method of claim 1 wherein available memory locations to be spliced onto the free link lists are structured as a freed memory link list comprising a head pointer, a head plus one pointer, and a tail pointer.
3. The method of claim 2 and including the steps of allocating from the head pointer of the freed memory link list and splicing from the head plus one to the tail pointer of the freed memory link list.
4. The method of claim 3 and including the steps of simultaneously allocating and freeing memory locations.
5. The method of claim 4 and including the step of setting tail pointer of a free link list to the head pointer plus one of the freed memory link list.
6. The method of claim 3 and including the step of setting tail pointer of a free link list to the head pointer plus one of the freed memory link list.
7. The method of claim 5 and including the step of setting the free link list tail pointer to the address of the tail of the last freed memory location.
8. A method for managing data storage in a memory, comprising:
creating at least two free link lists identifying available data storage locations in the memory;
storing data in a plurality of data locations in the memory wherein each block of data is stored in a link list and each link list includes a head and a tail;
reading a head pointer from one of the free link lists to determine a beginning location of a block of data to be stored; and
simultaneously allocating data storage at a location of a head pointer of the other of the free link lists.
9. The method of claim 8 and including the step of maintaining a plurality of free link lists wherein each list identifies different lists of available memory.
10. The method of claim 8 and including the step of adding available link lists to a shortest one of the free link lists so as to maintain balance between the free link lists.
11. The method of claim 8 wherein the plurality of free link lists comprises two free link lists.
12. The method of claim 8 and including the steps of simultaneously allocating and freeing memory in one memory cycle.