Methods and apparatus for forming linked list queue using chunk-based structure

• US 6,754,795 B2
• Filed: 12/21/2001
• Issued: 06/22/2004
• Est. Priority Date: 12/21/2001
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: Agere Systems Incorporated (Broadcom, Inc.)
• Inventors: Chen, Jian-Guo, Sonnier, David P., Clune, David E., Moller, Hanan Z.
• Primary Examiner(s): Ellis, Kevin L.
• Application Number:
  US10/029,680
• Publication Number:
  US 20030120879A1
• Time in Patent Office: 914 Days
• Field of Search: 711/154, 711/170, 711/171, 711/173, 707/100
• US Class Current: 711/170
• CPC Class Codes: G06F 2205/064 Linked list, i.e. structure using pointers, e.g. allowing non-contiguous address segments in one logical buffer or dynamic buffer space allocation
• CPC Class Codes: G06F 5/10 having a sequence of storage locations each being individually accessible for both enqueue and dequeue operations, e.g. using random access memory G06F5/065 takes precedence
• CPC Class Codes: H04L 49/25 Routing or path finding in a switch fabric
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/901 using storage descriptor, e.g. read or write pointers
• CPC Class Codes: H04L 49/9073 Early interruption upon arrival of a fraction of a packet

Abstract

A processing system comprises processing circuitry and memory circuitry coupled to the processing circuitry. The memory circuitry is configurable to maintain at least one queue structure representing a list of data units (e.g., pointers to packets stored in a packet memory). The queue structure is partitioned into two or more blocks (e.g., chunks) wherein at least some of the blocks of the queue structure include two or more data units. Further, at least some of the blocks of the queue structure may include a pointer to a next block of the queue structure (e.g., a next chunk pointer). Given such a queue structure, the processing circuitry is configurable to address a first block of the queue structure, and then address a next block of the queue structure by setting the next block pointer of the first block to point to the next block.

Claims

1. A processing system comprising:

processing circuitry; and

memory circuitry, coupled to the processing circuitry, the memory circuitry configurable to maintain at least one queue structure representing a list of data units, the queue structure being partitioned into two or more blocks, at least some of the blocks of the queue structure including two or more data units, the at least one queue structure having a head pointer and a tail pointer associated therewith, the head pointer and the tail pointer being configurable to point to a data unit within a block.

2. The system of claim 1 wherein the data units are pointers to packets stored in a packet memory.

3. The system of claim 1 wherein at least some of the blocks of the queue structure include a pointer to a next block of the queue structure.

4. The system of claim 3 wherein the processing circuitry is configurable to:

(i) address a first block of the queue structure; and

(ii) address a next block of the queue structure by setting the next block pointer of the first block to point to the next block.

5. The system of claim 1 wherein the data units in a given block are contiguously located in the memory circuitry.

6. The system of claim 1 further comprising at least one list of pointers representing available blocks of the queue structure, the available blocks list being maintaining in association with the queue structure.

7. The system of claim 6 wherein the processing circuitry is further configurable to reference the available blocks list when adding a data unit to the queue structure.

8. The system of claim 6 wherein the processing circuitry is further configurable to update the available blocks list when removing a data unit from the queue structure.

9. The system of claim 1 wherein the queue structure is associated with a traffic manager.

10. The system of claim 1 wherein at least one of the processing circuitry and the memory circuitry are implemented on an integrated circuit.

11. A method for use in a data processing system, the method comprising the step of:

maintaining, in memory circuitry, at least one queue structure representing a list of data units, the queue structure being partitioned into two or more blocks, at least some of the blocks of the queue structure including two or more data units, the at least one queue structure having a head pointer and a tail pointer associated therewith, the head pointer and the tail pointer being configurable to point to a data unit within a block.

12. The method of claim 11 wherein the data units are pointers to packets stored in a packet memory.

13. The method of claim 11 wherein at least some of the blocks of the queue structure include a pointer to a next block of the queue structure.

14. The method of claim 13 further comprising the steps of:

addressing a first block of the queue structure, in accordance with processing circuitry coupled to the memory circuitry; and

addressing a next block of the queue structure by setting the next block pointer of the first block to point to the next block, in accordance with the processing circuitry.

15. The method of claim 11 wherein the data units in a given block are contiguously located in the memory circuitry.

16. The method of claim 11 further comprising the step of maintaining, in association with the queue structure, at least one list of pointers representing available blocks of the queue structure.

17. A data structure comprising:

a first data block element representing two or more data units; and

at least a second data block element, partitioned from the first data block element, also representing two or more data units;

wherein the first data block element and the at least a second data block element cumulatively form a queue structure representing a list of data units, the queue structure having a head pointer and a tail pointer associated therewith, the head pointer and the tail pointer being configurable to point to a data unit within a data block element.

18. The data structure of claim 17 wherein the data units are pointers to packets stored in a packet memory.