Methods and apparatus for linked-list circular buffer management
View Patent ↗A buffer memory is provided that comprises a plurality of memory elements for storing data elements in an order of arrival, wherein the plurality of memory elements have a variable size and wherein each memory element comprises a pointer (such as a next block starting index) to a memory element storing a next data element. Additionally, each memory element optionally further comprises a block size field indicating the variable size and/or a sequence number field indicating a sequence number of the corresponding data element. The buffer memory optionally comprises a largest sequence variable to store a sequence number of a data element in the buffer memory having a largest sequence number. The largest sequence variable is updated if a newly arrived data element has a sequence number that is larger than the largest sequence variable. A method is also provided for managing the disclosed buffer memories.
1. A buffer memory, comprising:
a plurality of continuous memory elements for storing data elements in an order of arrival along with sequence information for the data elements stored therein, wherein said plurality of continuous memory elements have a variable size, wherein each memory element comprises a pointer to another memory element in said plurality of continuous memory elements storing a next data element, wherein said variable size is determined when a corresponding data element is stored and is based on a size of said corresponding data element, wherein a memory hole in said buffer memory is dissolved by a read pointer moving forward to skip a reading of the memory element associated with the memory hole, and wherein said buffer memory is defragmented by copying one or more memory fragments toward a direction of the read pointer or a write pointer; and
a largest sequence variable to store a sequence number of a data element in said buffer memory having a largest sequence number, wherein said largest sequence variable is updated if a newly arrived data element has a sequence number that is larger than said largest sequence variable.
2. The buffer memory of claim 1 , wherein each memory element further comprises a block size field indicating said variable size, wherein said block size field is stored in a block header along with the sequence information for the data element.
3. The buffer memory of claim 1 , wherein each memory element further comprises a sequence number field indicating a sequence number of said corresponding data element.
4. The buffer memory of claim 1 , wherein said data element comprises a packet.
5. The buffer memory of claim 1 , wherein said pointer comprises a next block starting index that points to a next packet in a sequence.
6. The buffer memory of claim 1 , wherein said largest sequence variable further comprises a location of said data element in said buffer memory having a largest sequence number.
7. The buffer memory of claim 1 , wherein said pointer is updated if a newly arrived data element has arrived out of sequence.
8. The buffer memory of claim 1 , wherein a data element is read from said buffer memory by reading a data element from a head of an ordered list.
9. The buffer memory of claim 8 , wherein said data element from said head of said ordered list has a smallest sequence number.
10. An integrated circuit, comprising:
a buffer memory comprising a plurality of continuous memory elements for storing data elements in an order of arrival in addition to storing sequence information for a corresponding data element, wherein said plurality of continuous memory elements have a variable size and wherein each memory element comprises a pointer to another memory element in said plurality of continuous memory elements storing a next data element, wherein said variable size is determined when said corresponding data element is stored and is based on a size of said corresponding data element, wherein a memory hole in said buffer memory is dissolved by a read pointer moving forward to skip a reading of the memory element associated with the memory hole, and wherein said buffer memory is defragmented by copying one or more memory fragments toward a direction of the read pointer or a write pointer; and
a largest sequence variable to store a sequence number of a data element in said buffer memory having a largest sequence number, wherein said largest sequence variable is updated if a newly arrived data element has a sequence number that is larger than said largest sequence variable.
11. The integrated circuit of claim 10 , wherein each memory element further comprises a block size field indicating said variable size.
12. The integrated circuit of claim 10 , wherein each memory element further comprises a sequence number field indicating a sequence number of said corresponding data element, wherein the sequence number of said corresponding data element is included in the sequence information.
13. The integrated circuit of claim 10 , wherein said data element comprises a packet.
14. The integrated circuit of claim 10 , wherein said pointer comprises a next block starting index that points to a next packet in a sequence.
15. The integrated circuit of claim 10 , wherein said pointer is updated if a newly arrived data element has arrived out of sequence.
16. A method for managing a buffer memory, comprising:
storing data elements in a plurality of continuous memory elements based on order of arrival, wherein said plurality of memory elements have a variable size and store sequence information for a corresponding data element stored therein;
updating a pointer in each of said continuous memory elements to point to another memory element in said plurality of continuous memory elements storing a next data element, wherein said variable size is determined when said corresponding data element is stored along with the sequence information and is based on a size of said corresponding data element;
dissolving a memory hole in said buffer memory by a read pointer moving forward to skip a reading of the memory element associated with the memory hole;
defragmenting said buffer memory by copying one or more memory fragments towards a direction of the read pointer or a write pointer;
updating a largest sequence variable to store a sequence number of a data element in said buffer memory having a largest sequence number; and
updating said largest sequence variable if a newly arrived data element has a sequence number that is larger than said largest sequence variable.
17. The method of claim 16 , further comprising the step of updating a block size field in each of said memory elements indicating said variable size.
18. The method of claim 16 , further comprising the step of updating a sequence number field in each of said memory elements indicating a sequence number of said corresponding data element.
19. The method of claim 16 , wherein said largest sequence variable further comprises a location of said data element in said buffer memory having a largest sequence number.
20. The method of claim 16 , further comprising the step of updating said pointer if a newly arrived data element has arrived out of sequence.
21. The method of claim 16 , further comprising the step of reading a data element from said buffer memory by reading a data element from a head of an ordered list.