System And Method For Enabling High Read Rates To Data Element Lists

Abstract

A memory system for a network device is described. The memory system includes a main memory configured to store one or more data elements. Further, the memory system includes a link memory that is configured to maintain one or more pointers to interconnect the one or more data elements stored in the main memory. The memory system also includes a free-entry manager that is configured to generate an available bank set including one or more locations in the link memory. In addition, the memory system includes a context manager that is configured to maintain metadata for a list of the one or more data elements.

What is claimed is: 
     
         1 . A memory system for a network device comprising:
 a main memory configured to store one or more data elements;   link memory including a plurality of memory banks, each memory bank of said plurality of memory banks configured to maintain one or more pointers to interconnect said one or more memory locations in said main memory to form at least one list; and   a context manager including a plurality of head entries and a plurality of tail entries for each memory bank of said plurality of memory banks, said context manager configured to maintain metadata for a first entry of said at least one list.   
     
     
         2 . The memory system of  claim 1 , wherein said metadata is snapshot list metadata. 
     
     
         3 . The memory system of  claim 1 , wherein each head entry of said plurality of head entries is configured to store a sequence identifier. 
     
     
         4 . The memory system of  claim 2 , wherein said at least one list is a first set of a snapshot list. 
     
     
         5 . The memory system of  claim 2 , wherein each memory bank of said plurality of memory banks includes a single access port. 
     
     
         6 . The memory system of  claim 1  further comprising a free-entry manager configured to generate an available bank set including one or more locations in said link memory that are not currently used to maintain said one or more pointers. 
     
     
         7 . The memory system of  claim 6 , wherein said free-entry manager is configured to generate said available bank set including said one or more locations that are not currently used to maintain said one or more pointers such that a write operation to said link memory does not conflict with a read operation. 
     
     
         8 . The memory system of  claim 6 , wherein said free-entry manager is configured to generate said available bank set including said one or more locations that are not currently used to maintain said one or more pointers such that an access conflict will not occur. 
     
     
         9 . The memory system of  claim 1 , wherein the memory system is configured to compare a first sequence identifier in a first head entry of said plurality of head entries with a second sequence identifier in a second head entry of said plurality of head entries to determine a first snapshot in a snapshot list. 
     
     
         10 . The memory system of  claim 2 , wherein said snapshot list metadata is used to form at least one snapshot skip list. 
     
     
         11 . A method for implementing a memory system in a network device comprising:
 storing one or more data elements;   maintaining one or more pointers to interconnect the one or more data elements using a plurality of memory banks;   allocating one or more locations in at least one memory bank of said plurality of memory banks; and   maintaining metadata to form at least one data-element list of the one or more data elements using a plurality of head entries and a plurality of tail entries for each memory bank of said plurality of memory banks.   
     
     
         12 . The method of  claim 11  further comprising generating a sequence identifier for a snapshot and storing said sequence identifier in a first head entry of said plurality of head entries. 
     
     
         13 . The method of  claim 11  further comprising comparing a first sequence identifier in a first head entry of said plurality of head entries with a second sequence identifier in a second head entry of said plurality of head entries to determine a first snapshot in a snapshot list. 
     
     
         14 . The method of  claim 11  further comprising generating an available bank set including one or more locations in said plurality memory banks that are not currently being used to store metadata. 
     
     
         15 . The method of  claim 11 , wherein storing said one or more data elements are in response to receiving said one or more data elements. 
     
     
         16 . The method of  claim 11  further comprising determining a next data element of said data-element list based on said metadata. 
     
     
         17 . A memory system for a network device comprising:
 a main memory configured to store one or more data elements;   a child distributed-link list configured to maintain list metadata to interconnect said one or more data elements stored in said main memory and to generate at least a first snapshot; and   a parent distributed-linked list including a plurality of memory banks, a plurality of head entries for each of said plurality of memory banks, and a plurality of tail entries for each of said plurality of memory banks, said plurality of memory banks configured to store snapshot list metadata, at least a first head entry of said plurality of head entries for a first memory bank configured to store first snapshot list metadata for said first snapshot.   
     
     
         18 . The memory system of  claim 17 , wherein each head entry of said plurality of head entries is configured to store a snapshot sequence identifier. 
     
     
         19 . The memory system of  claim 17 , wherein said first snapshot is a first entry of a first set of snapshots in a snapshot list. 
     
     
         20 . The memory system of  claim 19 , wherein a second head entry of said plurality of head entries for a second memory bank is configured to store second snapshot list metadata for a second snapshot in said snapshot list. 
     
     
         21 . The memory system of  claim 20 , wherein said second snapshot is a head node of a skip list. 
     
     
         22 . The memory system of  claim 17 , wherein each memory bank of said plurality of memory banks includes a single access port. 
     
     
         23 . The memory system of  claim 17  further comprising a free-entry manager configured to generate an available bank set including one or more locations in said link memory that are not currently used to maintain said one or more pointers. 
     
     
         24 . The memory system of  claim 23 , wherein said free-entry manager is configured to generate said available bank set including said one or more locations that are not currently used to maintain said one or more pointers such that a write operation to said link memory does not conflict with a read operation. 
     
     
         25 . A memory system for a network device comprising:
 a means for storing one or more data elements;   a means for maintaining one or more pointers to interconnect said one or more memory locations in said means for storing one or more data elements to form at least one list; and   a means for maintaining sets of snapshot list metadata in multiple memory bank.