Management of received data within host device using linked lists

• US 20040151170A1
• Filed: 09/30/2003
• Published: 08/05/2004
• Est. Priority Date: 01/31/2003
• Status: Abandoned Application

• Current Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Original Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Inventors: Moll, Laurent R., Gulati, Manu
• Application Number:
  US10/675,745
• Publication Number:
  US 20040151170A1
• Time in Patent Office: Days
• US Class Current: 370/360
• CPC Class Codes: H04L 49/9015 for supporting a linked list
• CPC Class Codes: H04L 49/9089 replacing packets in a storage arrangement, e.g. pushout

Abstract

A received data processing and storage system includes an input that receives data blocks corresponding to a plurality of input virtual channels. A routing module inspects the received data blocks and determines an output virtual channel for the data blocks based upon their respective input virtual channels. A receiver buffer instantiates input virtual channel linked lists, output virtual channel linked lists, and a free list. A linked list control module uses input virtual channel linked list registers, output virtual channel linked list registers, and free linked list registers to manage the linked lists instantiated by the receiver buffer. An output transmits data blocks corresponding to the plurality of output virtual channels. Data blocks are stored in the receiver buffer in both input virtual channel link lists and output virtual channel linked lists.

Claims

1. A method for routing data within a host device comprising:

receiving a data block at a receiver of the host device;

storing the data block in a receiver buffer;

determining an input virtual channel corresponding to the data block;

updating an input virtual channel linked list corresponding to the input virtual channel to include the data block;

determining an output virtual channel for the data block;

transferring the data block from the input virtual channel linked list of the receiver buffer to a destination within the host device via the output virtual channel; and

updating the input virtual channel linked list to remove the data block.

2. The method of claim 1, wherein determining an output virtual channel for the data block includes processing one or more of the input virtual channel, a header corresponding to the data block, a protocol corresponding to the data block, source identifier/address corresponding to the data block, and a destination identifier/address corresponding to the data block.

3. The method of claim 1, wherein:

storing the data block in the receiver buffer includes storing the data block in the receiver buffer at an old free linked list head address; and

updating an input virtual channel linked list corresponding to the input virtual channel to include the data block comprises;

reading a new free linked list head address from the receiver buffer at an old free linked list head address;

writing the new free linked list head address to a free linked list head register;

writing the old free linked list head address to the receiver buffer at the old input virtual channel linked list tail address; and

writing the old free linked list head address to an input virtual channel linked list tail register.

4. The method of claim 1, wherein:

transferring the data block from the input virtual channel linked list of the receiver buffer to a destination within the host device via the output virtual channel includes reading the data block from the receiver buffer at an old input virtual channel linked list head address; and

updating the input virtual channel linked list to remove the data block comprises;

reading a new input virtual channel linked list head address from the receiver buffer at the old input virtual channel linked list head address;

writing the new input virtual channel linked list head address to an input virtual channel linked list head register;

writing the old input virtual channel linked list head address to the receiver buffer at an old free linked list tail address; and

writing the old input virtual channel linked list head address to a free linked list tail register.

5. The method of claim 1, further comprising writing a data block to the receiver buffer and reading a data block from the receiver buffer in a single read/write cycle.

6. The method of claim 1, further comprising anticipating the write of a data block to the receiver buffer in a subsequent read/write cycle by reading a new free linked list head address from the receiver buffer at an old free linked list head address in a current read/write cycle.

7. The method of claim 1, further comprising in a common read/write cycle in which a first data block is read from the receiver buffer and a second data block is written to the receiver buffer:

reading the first data block and a new input virtual channel head address from the receiver buffer at an old input virtual channel head address;

writing the new input virtual channel head address to the input virtual channel head register;

writing the second data block to the receiver buffer at the old input virtual channel head address;

writing the old input virtual channel head address to an input virtual channel tail register; and

writing the old input virtual channel head address to the receiver buffer at an old input virtual channel tail address.

8. The method of claim 1, further comprising supporting a plurality of input virtual channel linked lists, wherein each input virtual channel linked list corresponds to a respective input virtual channel.

9. The method of claim 1, further comprising supporting a free linked list that includes a plurality of vacant data blocks of the receiver buffer.

10. The method of claim 1, further comprising maintaining a mapping indicating a relationship between a plurality of input virtual channels and a plurality of output virtual channels.

11. A method for routing data within a host device comprising:

receiving a data block at a receiver of the host device, the data block received via an input virtual channel;

storing the data block in a receiver buffer;

when the input virtual channel has identified therewith an output virtual channel updating an output virtual channel linked list corresponding to the output virtual channel to include the data block; and

when the input virtual channel has not identified therewith an output virtual channel;

updating an input virtual channel linked list corresponding to the input virtual channel to include the data block;

processing the data block to determine an output virtual channel for the data block;

updating an output virtual channel linked list corresponding to the output virtual channel to include the data block; and

updating the input virtual channel linked list to remove the data block.

13. The method of claim 11, wherein:

storing the data block in the receiver buffer includes storing the data block in the receiver buffer at an old free linked list head address; and

updating an input virtual channel linked list corresponding to the input virtual channel to include the data block comprises;

reading a new free linked list head address from the receiver buffer at an old free linked list head address;

writing the new free linked list head address to a free linked list head register;

writing the old free linked list head address to the receiver buffer at the old input virtual channel linked list tail address; and

writing the old free linked list head address to an input virtual channel linked list tail register.

14. The method of claim 11, further comprising writing a data block to the receiver buffer and reading a data block from the receiver buffer in a single read/write cycle.

15. The method of claim 11, further comprising anticipating the write of a data block to the receiver buffer in a subsequent read/write cycle by reading a new free linked list head address from the receiver buffer at an old free linked list head address in a current read/write cycle.

16. The method of claim 11, further comprising in a common read/write cycle in which a first data block is read from the receiver buffer and a second data block is written to the receiver buffer:

reading the first data block and a new output virtual channel head address from the receiver buffer at the old output virtual channel head address;

writing the new output virtual channel head address to the output virtual channel head register;

writing the second data block to the receiver buffer at the old output virtual channel head address;

writing the old output virtual channel head address to an output virtual channel tail register; and

writing the old output virtual channel head address to the receiver buffer at the old output virtual channel head address.

17. The method of claim 11, further comprising supporting a plurality of input virtual channel linked lists, wherein each input virtual channel linked list corresponds to a respective input virtual channel.

18. The method of claim 11, further comprising supporting a plurality of output virtual channel linked lists, wherein each output virtual channel linked list corresponds to a respective output virtual channel.

19. The method of claim 11, further comprising supporting a free linked list that includes a plurality of vacant data blocks of the input buffer.

12. The method of claim 12, further comprising:

transferring the data block from the receiver buffer to a destination within the host device based upon a corresponding output virtual channel; and

updating the output virtual channel linked list to remove the data block.

20. A received data processing and storage system comprising:

an input that receives data blocks corresponding to a plurality of input virtual channels;

a routing module that determines an output virtual channel for data blocks based upon their respective input virtual channels;

a receiver buffer operable to instantiate an input virtual channel linked list for storing data blocks on an input virtual channel basis and to instantiate a free list that identifies free data locations;

a linked list control module operably coupled to the receiver buffer;

input virtual channel linked list registers operably coupled to the linked list control module; and

free linked list registers operably coupled to the linked list control module.

21. The received data processing and storage system of claim 20, further comprising an output that transmits data blocks corresponding to a plurality of input virtual channels.

22. The received data processing and storage system of claim 20, wherein:

the receiver buffer is further operable to instantiate an output virtual channel linked list for storing data blocks on an output virtual channel basis; and

the system further comprises output virtual channel linked list registers operably coupled to the linked list control module and an input virtual channel to output virtual channel map.

23. The received data processing and storage system of claim 20, wherein the receiver buffer comprises:

a pointer memory; and

a data memory, wherein a single address addresses corresponding locations of the pointer memory and of the data memory.

24. The received data processing and storage system of claim 23, wherein the receiver buffer further comprises a packet status memory, wherein a single address addresses corresponding locations of the pointer memory, the data memory, and the packet status memory.

25. The received data processing and storage system of claim 23, further comprising a pointer memory read port, a pointer memory write port, a data memory read port, and a data memory write port, each of which can access the receiver buffer in a common read/write cycle.

26. The received data processing and storage system of claim 25, wherein:

a single pointer memory location can be read from and written to in a common read/write cycle; and

a single data memory location can be read from and written to in a common read/write cycle.

27. The received data processing and storage system of claim 20, wherein the receiver buffer comprises:

a pointer memory;

a data memory;

a packet status memory; and

wherein a single address addresses corresponding locations of the pointer memory, the data memory, and the packet status memory.

28. The received data processing and storage system of claim 27, further comprising:

a pointer memory read port;

a pointer memory write port;

a data memory read port;

a data memory write port;

a packet status memory read port; and

a packet status memory write port.

29. The received data processing and storage system of claim 28, wherein:

a single pointer memory location can be read from and written to in a common read/write cycle;

a single data memory location can be read from and written to in a common read/write cycle; and

a single packet status memory location can be read from and written to in a common read/write cycle.