Managing out of order buffers
A method and corresponding computer device for a shared buffer able to consecutively store received data packets without wasted storage space and enabling first-in first-out processing order. The shared buffer is divided into segments, each segment having a complete count that tracks both number of data packet stored into the segment and the number of data packets read out of the segment. The complete counts of the segments provide a way to determine if segments contain unprocessed data packets and when the segments become free to store newly received data packets. Managing the shared buffer on a segment level, instead of a data packet level reduces the amount of memory needed to be dedicated to buffer management and streamlines the packet tracking and release procedures.
1 . A computing device comprising:
a first storage area configured to temporarily store data packets consecutively, the first storage area divided into at least two segments;
a second storage area configured to store, for each of the at least two segments of the first storage area, a segment complete count, the segment complete count indicating if a corresponding segment contains unprocessed data packets;
a write controller configured to generate a write message when a data packet is stored in the first storage area and update segment complete counts of a first subset of the at least two segments, the first subset of the at least two segments selected based on where the data packet is stored in the first storage area; and
a buffer controller configured to:
receive a read message when a data packet is processed from the first storage area and update segment complete counts of a second subset of the at least two segments, the second subset of at least two segments selected based upon where the data packet is processed from the first storage area; and
update an address of a packet start read pointer located in a current segment to a subsequent segment when the segment complete count of the current section indicates that it does not contain unprocessed data packets.
2 . The computing device of claim 1 wherein the second storage area is further configured to store, for each of the at least two segments, a flag; and
the write controller is further configured:
to set the flag for a segment to full when a packet start write pointer crosses an end boundary of that segment; and
delay updating the address of the packet start read pointer to the subsequent segment until the flag for the subsequent section is set to full.
3 . The computing device of claim 2 wherein the buffer controller is further configured to clear the full flag for a segment when the segment complete count of that segment indicates that the segment does not contain unprocessed data packets.
4 . The computing device of claim 1 wherein the write message comprises i) a packet start write pointer, ii) a length of the stored data packet, iii) a segment number identifying a segment containing a start of the stored data packet; and iv) a straddle count identifying a number of segments containing the stored data packet.
5 . The computing device of claim 4 wherein the segment number and the straddle count of the stored data packet are calculated based upon the packet start write pointer and the length of the stored data packet.
6 . The computing device of claim 1 wherein the read message comprises a segment number and a straddle count of the processed data packet.
7 . The computing device of claim 1 wherein at least one of the write controller and buffer controller is a hardware controller.
8 . The computing device of claim 1 wherein the second storage area is further configured to store a number of the at least two segments and a size of the at least two segments.
9 . The computing device of claim 1 wherein the first storage area is configured to store data packets consecutively without any intervening empty space.
10 . The computing device of claim 1 wherein the data packets are stored in, and processed from, the first storage area in first-in, first-out order.
11 . A method for temporarily storing data packets, the method comprising:
consecutively storing, in a first storage area divided into at least two segments, received data packets;
storing, in a second storage area, for each of the at least two segments of the first storage area, a segment complete count, the segment complete count indicating if a corresponding segment contains unprocessed data packets;
generating, by a write controller, a write message when a data packet is stored in the first storage area;
updating, by the write controller, segment complete counts of a first subset of the at least two segments, the first subset of the at least two segments selected based on where the data packet is stored in the first storage area;
receiving, by a buffer controller, a read message when a data packet is processed from the first storage area;
updating, by the buffer controller, segment complete counts of a second subset of the at least two segments, the second subset of at least two segments selected based upon where the data packet is processed from the first storage area; and
updating, by the buffer controller, an address of a packet start read pointer located in a current segment to a subsequent segment when the segment complete count of the current section indicates that it does not contain unprocessed data packets.
12 . The method of claim 11 wherein the second storage area is further configured to store, for each of the at least two segments, a flag, the method further comprising:
setting, by the write controller, the flag for a segment to full when a packet start write pointer crosses an end boundary of that segment; and
delaying the updating of the address of the packet start read pointer to the subsequent segment until the flag for the subsequent section is set to full.
13 . The method of claim 12 further comprising clearing, by the buffer controller, the full flag for a segment when the segment complete count of that segment indicates that the that segment does not contain unprocessed data packets.
14 . The method of claim 11 wherein the write message comprises i) a packet start write pointer, ii) a length of the stored data packet, iii) a segment number identifying a segment containing a start of the stored data packet; and iv) a straddle count identifying a number of segments containing the stored data packet.
15 . The method of claim 11 wherein the read message comprises a segment number and a straddle count of the processed data packet.
16 . The method of claim 11 wherein the write controller and buffer controller are hardware controllers.
17 . The method of claim 11 wherein data packets are stored consecutively without any intervening empty space in the first storage area.
18 . The method of claim 11 wherein the data packets are stored in, and processed from, the first storage area in first-in, first-out order.
19 . The method of claim 11 wherein the first storage area is a buffer that stores the received packets before they are processed.
20 . A computing device comprising:
means for temporarily storing packets consecutively in a first storage area divided into at least two segments;
means for storing, in a second storage area, for each of the at least two segments of the first storage area, a segment complete count, the segment complete count indicating if a corresponding segment contains unprocessed data packets;
means for generating a write message when a data packet is stored in the first storage area and updating segment complete counts of a first subset of the at least two segments, the first subset of the at least two segments selected based where the data packet is stored in the first storage area;
means for receiving a read message when a data packet is processed from the first storage area and updating segment complete counts of a second subset of the at least two segments, the second subset of at least two segments selected based upon where the data packet is processed from the first storage area; and
means for updating an address of a packet start read pointer located in a current segment to a subsequent segment when the segment complete count of the current section indicates that it does not contain unprocessed data packets.