Method and apparatus for allocation and management of shared memory with data in memory stored as multiple linked lists

Abstract

Apparatus and methods for allocating shared memory utilizing linked lists are provided which are particularly useful in telecommunications applications such as ATM. A management RAM contained within a VLSI circuit is provided for controlling the flow of data into and out of a shared memory (data RAM), and stores information regarding a number of link lists and a free link list in the shared memory, and a block pointer to unused RAM locations. A head pointer, tail pointer, block counter and empty flag are stored for each data link list. The head and tail pointers each include a block pointer and a position counter. The block counter contains the number of blocks used in the particular queue. The empty flag indicates whether the queue is empty. The free link list includes a head pointer, a block counter, and an empty flag. Each memory page of the shared data RAM receiving the incoming data includes locations for storing data. The last location of the last page in a block of shared data RAM memory is preferably used to store a next-block pointer plus parity information. If there are no more blocks in the queue, that last location is set to all ones. An independent agent is utilized in the background to monitor the integrity of the link list structure. Using the methods and apparatus of the invention, four operations are defined for ATM cell management: cell write, cell read, queue clear, and link list monitoring.

Dependencies are inferred from the claim text.