Packet descriptor storage in packet memory with cache

Abstract

A first memory device stores (i) a head part of a FIFO queue structured as a linked list (LL) of LL elements arranged in an order in which the LL elements were added to the FIFO queue and (ii) a tail part of the FIFO queue. A second memory device stores a middle part of the FIFO queue, the middle part comprising a LL elements following, in an order, the head part and preceding, in the order, the tail part. A queue controller retrieves LL elements in the head part from the first memory device, moves LL elements in the middle part from the second memory device to the head part in the first memory device prior to the head part becoming empty, and updates LL parameters corresponding to the moved LL elements to indicate storage of the moved LL elements changing from the second memory device to the first memory device.

What is claimed is: 
     
         1 . An apparatus, comprising:
 a first memory device configured to store:
 (i) a head part of a first-in-first-out (FIFO) queue, the FIFO queue structured as a linked list (LL) of LL elements arranged in an order in which the LL elements were added to the FIFO queue, the head part including a first plurality of LL elements arranged for retrieval from the FIFO queue in the order in which the LL elements were added to the FIFO queue, and 
 (ii) a tail part of the FIFO queue, the tail part comprising a second plurality of LL elements arranged corresponding to an order in which the second plurality LL elements were added to the FIFO queue; 
   a second memory device that is separate from the first memory, the second memory configured to store a middle part of the FIFO queue, the middle part comprising a third plurality of LL elements following, in the order, the head part and preceding, in the order, the tail part; and   a queue controller configured to:
 retrieve LL elements in the head part from the first memory device according to the order, 
 move LL elements in the middle part from the second memory device to the head part in the first memory device prior to the head part becoming empty, and 
 update LL parameters corresponding to the moved LL elements to indicate storage of the moved LL elements changing from the second memory device to the first memory device.