System And Method For Implementing Distributed-Linked Lists For Network Devices

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 configured to maintain one or more pointers to interconnect said one or more data elements stored in said main memory;   a free-entry manager configured to generate an available bank set including one or more locations in said link memory;   a context manager configured to maintain metadata for at least one list of said one or more data elements.   
     
     
         2 . The system of  claim 1 , wherein said free entry manager is configured to generate said available bank set including said one or more locations such that a write operation to said link memory does not conflict with a read operation. 
     
     
         3 . The system of  claim 1 , wherein said link memory is further configured to store one or more memory addresses for the one or more data elements stored in said main memory. 
     
     
         4 . The system of  claim 3 , wherein said link memory is further configured to store said one or more memory addresses for at least one of said one or more data elements stored in said main memory. 
     
     
         5 . The system of  claim 4 , wherein said link memory is further configured to store a data-element sequence identifier for at least one of said one or more data elements stored in said main memory. 
     
     
         6 . The system of  claim 1 , wherein said data element is a data packet. 
     
     
         7 . The system of  claim 1 , wherein said data element is a cell of a data packet. 
     
     
         8 . The system of  claim 1 , wherein a set of said one or more data elements form a sequence of data elements. 
     
     
         9 . The system of  claim 8 , wherein said context manager configured to maintain metadata for said at least one list of said one or more data elements includes being configured to store a main memory address for a first data element in said at least one list. 
     
     
         10 . The system of  claim 9 , wherein said context manager configured to maintain metadata for said at least one list of said one or more data elements includes being configured to store a second main memory address for a final element in said sequence. 
     
     
         11 . The system of  claim 10 , wherein said context manager configured to maintain metadata for said at least one list includes being configured to store a link memory address for said first element in said sequence. 
     
     
         12 . 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;   allocating one or more locations in a link memory; and   maintaining metadata to form at least one list of the one or more data elements.   
     
     
         13 . The method of  claim 12 , wherein storing said one or more data elements are in response to receiving said one or more data elements. 
     
     
         14 . The method of  claim 12 , wherein maintaining said one or more pointers to interconnect said one or more data elements includes storing said one or more pointers in a head entry. 
     
     
         15 . The method of  claim 14  wherein maintaining said one or more pointers to interconnect said one or more data elements further includes updating metadata. 
     
     
         16 . The method of  claim 1 , further comprising generating an available bank set of said one or more locations in said link memory. 
     
     
         17 . The method of  claim 12 , further comprising determining a next data element of said at least one list. 
     
     
         18 . The method of  claim 17 , wherein determining a next data element of at least one list includes comparing a plurality of head entries. 
     
     
         19 . The method of  claim 18 , wherein each of said plurality of head entries includes a data-element sequence identifier. 
     
     
         20 . The method of  claim 12 , wherein allocating one or more locations in a link memory includes selecting a location from an available bank set of locations and setting a pointer to reference the address of that location. 
     
     
         21 . An apparatus comprising:
 a means for maintaining one or more pointers to interconnect the one or more data elements;   a means for allocating one or more locations in a link memory; and   a means for maintaining metadata to form a list of the one or more data elements.   
     
     
         22 . A non-transitory program storage device readable by a machine, embodying a program of instructions executable by the machine to perform data transfer, the method comprising:
 storing one or more data elements;   maintaining one or more pointers to interconnect the one or more data elements;   allocating one or more locations in a link memory; and   maintaining metadata to form a list of the one or more data elements.