US20020051460A1 - Method for automatic resource reservation and communication that facilitates using multiple processing events for a single processing task - Google Patents

Abstract

An integrated circuit for processing communication packets having separate data buffers and separate state information buffers. Each data buffer and each state information buffer (hereinafter termed resources) has an associated in-use counter. Multiple events can share the same resource. The counter associated with a resource is incremented when a resource becomes associated with a particular event. The counter associated with a resource is decremented when an event completes the use of that particular resource. When the in-use counter for a resource becomes zero, the in-use counter indicates that the resource is unassigned and that the resource can be assigned to a new event.

Description

RELATED APPLICATIONS
• Priority is claimed for the following co-pending applications:[0001]
• 1) Application Ser. No. 60/221,821 entitled “Traffic Stream Processor” filed on Jul. 31, 2000.[0002]
• 2) Application Ser. No. 09/639,915 entitled “Integrated Circuit that Processes Communication Packets with Scheduler Circuitry that Executes Scheduling Algorithms based on Cached Scheduling Parameters” filed on Aug. 16, 2000.[0003]
• 3) Application Ser. No. 09/640,258 entitled “Integrated Circuit that Processes Communication Packets with Co-Processor Circuitry to Determine a Prioritized Processing Order for a Core Processor” filed on Aug. 16, 2000.[0004]
• 4) Application Ser. No. 09/640,231 entitled “Integrated Circuit that Processes Communication Packets with Co-Processor Circuitry to Correlate a Packet Stream with Context Information” filed on Aug. 16, 2000.[0005]
• The content of the above applications is hereby incorporated herein by reference.[0006]
FIELD OF THE INVENTION
• The present invention is related to the field of communications, and more particularly to integrated circuits that process communication packets.[0007]
BACKGROUND OF THE INVENTION
• Many communication systems transfer information in streams of packets. In general, each packet contains a header and a payload. The header contains control information, such as addressing or channel information, that indicate how the packet should be handled. The payload contains the information that is being transferred. Some examples of the types of packets used in communication systems include, Asynchronous Transfer Mode (ATM) cells, Internet Protocol (IP) packets, frame relay packets, Ethernet packets, or some other packet-like information block. As used herein, the term “packet” is intended to include packet segments.[0008]
• Integrated circuits termed “traffic stream processors” have been designed to apply robust functionality to high-speed packet streams. Robust functionality is critical with today's diverse but converging communication systems. Stream processors must handle multiple protocols and inter-work between streams of different protocols. Stream processors must also ensure that quality-of service constraints, priority, and bandwidth requirements are met. This functionality must be applied differently to different streams, and there may be thousands of different streams.[0009]
• Co-pending application Ser. Nos. 09/639,966, 09/640,231 and 09/640,258, the content of which is incorporated herein by reference, describe an integrated circuit for processing communication packets. As described in the above applications, the integrated circuit includes a core processor. The processor handles a series of tasks, termed “events”. These events consist of tasks such as CPU processing steps as well as the scheduling of subsequent events. These subsequently scheduled events may consist of CAM lookups, DMA data transfers, or other generic events based on conditions in the current event. All events have an associated service address, “context information” and “data”. Information about the event such as the resource that requested the event, how much data is associated with the event, and other key information from the event requester is stored in “special state” information associated with the event. When an external resource initiates an event, the external resource supplies the core processor with a memory pointer to “context” information and it also supplies the data to be associated with the event.[0010]
• The context pointer is used to fetch the context from external memory and to store this “context” information in memory located on the chip. If the required context data has already been fetched onto the chip, the hardware recognizes this fact and sets the on chip context pointer to point to this already pre-fetched context data. Only a small number of the system “contexts” are cached on the chip at any one time, and their allocation needs to managed and sometimes shared among multiple processing events. Each cached “context” has an in-use counter so that one context can be associated with multiple sets of data. The rest of the system “contexts” are stored in external memory. This context fetch mechanism and the storage of these contexts in the co-processor is described in the above referenced co-pending applications.[0011]
• In the circuit described in the above references co-pending applications, data and context information for a number of events are stored in buffers in a co-processor. In order to process an event, the core processor needs the service address of the event as well as the “context” and “data” associated with the event. The service address is the starting address for the instructions used to service the event. The core processor branches to the service address in order to start servicing the event.[0012]
SUMMARY OF THE INVENTION
• The present invention adds flexibility and additional functions to an integrated circuit such as that described in the above references co-pending applications. In the integrated circuit shown in the referenced co-pending applications, special state information is effectively stored together with associated data in data buffers. Furthermore, the data buffers do not have associated in-use counters. With the present invention, separate logical buffers are provided for special state information and for the associated data buffer. Furthermore, each data buffer and each special state information buffer (hereinafter termed resources) has an associated in-use counter. Multiple events can share the same resource. The counter associated with a resource is incremented when a resource becomes associated with a particular event. The counter associated with a resource is decremented when an event completes the use of that particular resource. When the in-use count for a resource becomes zero, the in-use count indicates that the resource is unassigned and that the resource can be assigned to a new event.[0013]
• With the present invention, two events can point to (i.e. utilize) the same data buffer and/or the same special state information buffer. Furthermore the content of a data buffer or a special state information buffer can be passed directly from one event to another event without reading the data into and out of memory. The in-use counter is particularly useful to facilitate the timing of DMA requests without need for explicit control by an external program. With the present invention two events can use the same data buffer. This is possible since the special state information is stored in a separate buffer. Furthermore, with the present invention one can have one data buffer associated with multiple context buffers since the special state information is stored separately from the associated data. The present invention also adds a communication mechanism which allows an event to pass a multi-bit message to subsequent events. This message passing mechanism does not require that the two events share any of the same context, data, or special state resources.[0014]
BRIEF DESCRIPTION OF THE FIGURES
• FIG. 1 is an overall block diagram of a packet processing integrated circuit in an example of the invention.[0015]
• FIG. 2 is a block diagram that illustrates packet processing stages and the pipe-lining used by the circuit in an example of the invention.[0016]
• FIG. 3 is a diagram illustrating circuitry in the co-processing relating to context and data buffer processing in an example of the invention.[0017]
• FIG. 4 is a block program flow diagram illustrating buffer correlation and in-use counts in an example of the invention.[0018]
• FIG. 5 is a block diagram of the buffer management circuitry in an example of the invention.[0019]
• FIG. 6 is a block diagram showing the details of the data and special state information buffers in an example of the invention.[0020]
• FIG. 7 is a block program flow diagram illustrating how data buffers are passed between events in an example of the invention.[0021]
• FIG. 8 is a block program flow diagram illustrating how state information buffers are passed between events in an example of the invention.[0022]
• FIG. 9A and 9B are block program flow diagram illustrating examples of how DMA commands are handled in an example of the invention.[0023]
DETAILED DESCRIPTION OF THE INVENTION
• Various aspects of packet processing integrated circuits are discussed in U.S. Pat. No. 5,748,630, entitled “ASYNCHRONOUS TRANSFER MODE CELL PROCESSING WITH LOAD MULTIPLE INSTRUCTION AND MEMORY WRITE-BACK”, filed on May 9, 1996. The content of the above referenced patent is hereby incorporated by reference into this application in order to shorten and simplify the description in this application.[0024]
• One embodiment of the present invention described herein is applied as an improvement to the type of integrated circuit described in co-pending patent applications Ser. No. 60/211,863 filed on Jun. 14, 2000, Ser. No. 09/640,260 filed on Aug. 16, 2000, Ser. No. 09/639,915 filed on Aug. 16, 2000, Ser. No. 09/639,966 filed on Aug. 16, 2000, Ser. No. 09/640,258 filed on Aug. 16, 2000 and Ser. No. 091640,231 filed on Aug. 17, 2000, the content of which is hereby incorporated herein by reference in order to shorten and simplify the description of the present application.[0025]
• FIG. 1 is a block diagram that illustrates a packet processing integrated[0026]circuit100 in an example of the invention. It should be understood that the present invention can also be applied to other types of processors. The operation of thecircuit100 will first be described with reference to FIGS.1 to4 and then the operation of different embodiments of the invention will be described with reference to FIGS.5 to9.
• [0027]Integrated circuit100 includes acore processor104, ascheduler105, receiveinterface106,co-processor circuitry107, transmitinterface108, andmemory interface109. These components may be interconnected through a memory crossbar or some other type of internal interface. Receiveinterface106 is coupled tocommunication system101. Transmitinterface108 is coupled tocommunication system102. Memory interface is coupled tomemory103.
• [0028]Communication system101 could be any device that supplies communication packets with one example being the switching fabric in an Asynchronous Transfer Mode (ATM) switch.Communication system101 could be any device that receives communication packets with one example being the physical line interface in the ATM switch.Memory103 could be any memory device with one example being Random Access Memory (RAM) integrated circuits. Receiveinterface106 could be any circuitry configured to receive packets with some examples including UTOPIA interfaces or Peripheral Component Interconnect (PCI) interfaces. Transmitinterface108 could be any circuitry configured to transfer packets with some examples including UTOPIA interfaces or PCI interfaces.
• [0029]Core processor104 is a micro-processor that executes networking application software. Core-processor104 supports an instruction set that has been tuned for networking operations especially context switching. As described herein,core processor104 has the following characteristics: 166 MHz, pipelined single-cycle operation, RISC-based design, 32-bit instruction and register set, K instruction cache, 8 KB zero-latency scratchpad memory, interrupt/trap/halt support, and C compiler readiness.
• [0030]Scheduler105 comprises circuitry configured to schedule and initiate packet processing that typically results in packet transmissions fromintegrated circuit100, althoughscheduler105 may also schedule and initiate other activities.Scheduler105 schedules upcoming events, and as time passes, selects scheduled events for processing and reschedules unprocessed events.Scheduler105 transfers processing requests for selected events toco-processor circuitry107.Scheduler105 can handle multiple independent schedules to provide prioritized scheduling across multiple traffic streams. To provide scheduling,scheduler105 may execute a guaranteed cell rate algorithm to implement a leaky bucket or a token bucket scheduling system. The guaranteed cell rate algorithm is implemented through a cache that holds algorithm parameters.Scheduler105 is described in detail in the above referenced co-pending patent applications.
• [0031]Co-processor circuitry107 receives communication packets from receiveinterface106 andmemory interface109 and stores the packets in internal data buffers.Co-processor circuitry107 correlates each packet to context information describing how the packet should be handled.Co-processor circuitry107 stores the correlated context information in internal context buffers and associates individual data buffers with individual context buffers to maintain the correlation between individual packets and context information. Importantly,co-processor circuitry107 ensures that only one copy of the correlated context information is present the context buffers to maintain coherency. Multiple data buffers are associated with a single context buffer to maintain the correlation between the multiple packets and the single copy the context information.
• [0032]Co-processor circuitry107 also determines a prioritized processing order forcore processor104. The prioritized processing order controls the sequence in whichcore processor104 handles the communication packets. The prioritized processing order is typically based on the availability of all of the resources and information that are required bycore processor104 to process a given communication packet. Resource state bits are set when resources become available, soco-processor circuitry107 may determine when all of these resources are available by processing the resource state bits. If desired, the prioritized processing order may be based on information in packet handling requests.Co-processor circuitry107 selects scheduling algorithms based on an internal scheduling state bits and uses the selected scheduling algorithms to determine the prioritized processing order. The algorithms could be round robin, service-to-completion, weighted fair queuing, simple fairness, first-come first-serve, allocation through priority promotion, software override, or some other arbitration scheme. Thus, the prioritization technique used byco-processor circuitry107 is externally controllable.Co-processor circuitry107 is described in more detail with respect to FIGS.2-4.
• [0033]Memory interface109 comprises circuitry configured to exchange packets with external buffers inmemory103.Memory interface109 maintains a pointer cache that holds pointers to the external buffers.Memory interface109 allocates the external buffers when entities, such ascore processor104 orco-processor circuitry107, read pointers from the pointer cache.Memory interface109 de-allocates the external buffers when the entities write the pointers to the pointer cache. Advantageously, external buffer allocation and de-allocation is available through an on-chip cache read/write.Memory interface109 also manages various external buffer classes, and handles conditions such as external buffer exhaustion.Memory interface109 is described in detail in the above referenced patent applications.
• In operation, receive[0034]interface106 receives new packets fromcommunication system101, andscheduler105 initiates transmissions of previously received packets that are typically stored inmemory103. To initiate packet handling, receiveinterface106 andscheduler105 transfer requests toco-processor circuitry107. Under software control,core processor104 may also request packet handling fromco-processor circuitry107.Co-processor circuitry107 fields the requests, correlates the packets with their respective context information, and creates a prioritized work queue forcore processor104.Core processor104 processes the packets and context information in order from the prioritized work queue. Advantageously,co-processor circuitry107 operates in parallel withcore processor104 to offload the context correlation and prioritization tasks to conserve important core processing capacity. In response to packet handling,core processor104 typically initiates packet transfers to eithermemory103 orcommunication system102. If the packet is transferred tomemory103, then core processor instructsscheduler105 to schedule and initiate future packet transmission or processing. Advantageously,scheduler105 operates in parallel withcore processor104 to offload scheduling tasks and conserve important core processing capacity.
• In response to packet handling,[0035]core processor104 typically initiates packet transfers to eithermemory103 orcommunication system102. If the packet is transferred tomemory103, thencore processor104 instructsscheduler105 to schedule and initiate future packet transmission or processing. Advantageously,scheduler105 operates in parallel withcore processor104 to offload scheduling tasks and conserve important core processing capacity.
• Various data paths are used in response to[0036]core processor104 packet transfer instructions.Co-processor circuitry107 transfers packets directly tocommunication system102 through transmitinterface108.Co-processor circuitry107 transfers packets tomemory103 throughmemory interface109 with an on-chip pointer cache.Memory interface109 transfers packets frommemory103 tocommunication system102 through transmitinterface108.Co-processor circuitry107 transfers context information from a context buffer throughmemory interface109 tomemory103 if there are no packets in the data buffers that are correlated with the context information in the context buffer. Advantageously,memory interface109 operates in parallel withcore processor104 to offload external memory management tasks and conserve important core processing capacity.
Co-processor CircuitryFIGS.2-4
• FIGS.[0037]2-4 depict one example of co-processor circuitry. Those skilled in the art will understand that FIGS.2-4 have been simplified for clarity.
• FIG. 2 illustrates how[0038]co-processor circuitry107 provides pipelined operation in an example of the invention. FIG. 2 is vertically separated by dashed lines that indicate five packet processing stages: 1) context resolution, 2) context fetching, 3) priority queuing, 4) software application, and 5) context flushing.Co-processor circuitry107 handles stages 1-3 to provide hardware acceleration.Core processor104handles stage 4 to provide software control with optimized efficiency due to stages 1-3.Co-processor circuitry107 also handlesstage 5.Co-processor circuitry107 has eight pipelines through stages 1-3 and 5 to concurrently process multiple packet streams.
• In[0039]stage 1, requests to handle packets are resolved to a context for each packet in the internal data buffers. The requests are generated by receiveinterface106,scheduler105, andcore processor104 in response to incoming packets, scheduled transmissions, and application software instructions. The context information includes a channel descriptor that has information regarding how the packet is to be handled. For example, a channel descriptor may indicate service address information, traffic management parameters, channel status, stream queue information, and thread status. In the current implementation, there are a maximum of 64,000 channels. Thus, 64,000 channels with different characteristics are available to support a wide array of service differentiation. Channel descriptors are identified by channel identifiers. Channel identifiers may be indicated by the request. A map may be used to translate selected bits from the packet header to a channel identifier. A hardware engine may also perform a sophisticated search for the channel identifier based on various information. Different algorithms that calculate the channel identifier from the various information may be selected by setting correlation state bits inco-processor circuitry107. Thus, the technique used for context resolution is externally controllable.
• In[0040]stage 2, context information is fetched, if necessary, by using the channel identifiers to transfer the channel descriptors to internal context buffers. Prior to the transfer, the context buffers are first checked for a matching channel identifier and validity bit. If a match is found, then the context buffer with the existing channel descriptor is associated with the corresponding internal data buffer holding the packet.
• In[0041]stage 3, requests with available context are prioritized and arbitrated forcore processor104 handling. The priority may be indicated by the request—and it may be the source of the request. The priority queues1-12 are 8 entries deep. Priority queues1-12 are also ranked in a priority order by queue number. The priority for each request is determined, and when the context and data buffers for the request are valid, an entry for the request is placed in one of the priority queues that corresponds to the determined priority. The entries in the priority queues point to a pending request state RAM that contains state information for each data buffer. The state information includes a data buffer pointer, a context pointer, context validity bit, requester indicator, port status, a channel descriptor loaded indicator. This state information was referred to earlier in this document as the special state information associated with an event. These two terms may be used interchangeably.
• The work queue indicates the selected priority queue entry that[0042]core processor104 should handle next. To get to the work queue, the requests in priority queues are arbitrated using one of various algorithms such as round robin, service-to-completion, weighted fair queuing, simple fairness, first-come first-serve, allocation through priority promotion, and software override. The algorithms may be selected through scheduling state bits inco-processor circuitry107. Thus, the technique used for prioritization is externally controllable.Co-processor circuitry107loads core processor104 registers with the channel descriptor information for the next entry in the work queue.
• In[0043]stage 4,core processor104 executes the software application to process the next entry in the work queue which points to a portion of the pending state request RAM that identifies the data buffer and context buffer. The context buffer indicates one or more service addresses that direct thecore processor104 to the proper functions within the software application. One such function of the software application is traffic shaping to conform to service level agreements. Other functions include header manipulation and translation, queuing algorithms, statistical accounting, buffer management, inter-working, header encapsulation or stripping, cyclic redundancy checking, segmentation and reassembly, frame relay formatting, multicasting, and routing. Any context information changes made by thecore processor104 are linked back to the context buffer in real time.
• In[0044]stage 5, context is flushed. Typically,core processor104 instructscoprocessor circuitry107 to transfer packets to off-chip memory103 or transmitinterface108. If no other data buffers are currently associated with the pertinent context information, thenco-processor circuitry107 transfers the context information to off-chip memory103.
• FIG. 3 is a block diagram that illustrates[0045]co-processor circuitry107 in an example of the invention.Co-processor circuitry107 comprises a hardware engine that is firmware-programmable in that it operates in response to state bits and register content. In contrast,core processor104 is a micro-processor that executes application software.Co-processor circuitry107 operates in parallel withcore processor104 to conserve core processor capacity by off-loading numerous tasks from thecore processor104.
• [0046]Co-processor circuitry107 comprisescontext resolution310,control311,arbiter312,priority queues313, data buffers314, context buffers315,context DMA316, anddata DMA317. Data buffers314 hold packets and context buffers315 hold context information, such as a channel descriptor. Data buffers314 are relatively small and of a fixed size, such as 64 bytes, so if the packets are ATM cells, each data buffer holds only a single ATM cell and ATM cells do not cross data buffer boundaries.
• Individual data buffers[0047]314 are associated with individual context buffers315 as indicated by the downward arrows.Priority queues313 hold entries that represent individual data buffers314 as indicated by the upward arrows. Thus, a packet in one of the data buffers is associated with its context information in an associated one of the context buffers315 and with an entry inpriority queues313.Arbiter312 presents a next entry frompriority queues313 tocore processor104 which handles the associated packet in the order determined byarbiter312.
• [0048]Context DMA316 exchanges context information betweenmemory103 and context buffers315 throughmemory interface109. Context DMA automatically updates queue pointers in the context information.Data DMA317 exchanges packets betweendata buffers314 andmemory103 throughmemory interface109.Data DMA317 also transfers packets frommemory103 to transmitinterface108 throughmemory interface109.Data DMA317signals context DMA316 when transferring packets off-chip, andcontext DMA316 determines if the associated context should be transferred to off-chip memory103. Both DMAs316-317 may be configured to perform CRC calculations.
• For a new packet from[0049]communication system101,control311 receives the new packet and a request to handle the new packet from receiveinterface106.Control311 receives and places the packet in one of the data buffers314 and transfers the packet header tocontext resolution310. Based on gap state bits, a gap in the packet may be created between the header and the payload in the data buffer, socore processor104 can subsequently write encapsulation information to the gap without having to create the gap.Context resolution310 processes the packet header to correlate the packet with a channel descriptor, although in some cases, receiveinterface106 may have already performed this context resolution. The channel descriptor comprises information regarding packet transfer over a channel.
• [0050]Control311 determines if the channel descriptor that has been correlated with the packet is already in one of the context buffers315 and is valid. If so,control311 does not request the channel descriptor from off-chip memory103. Instead, control311 associates theparticular data buffer314 holding the new packet with theparticular context buffer315 that already holds the correlated channel descriptor. This prevents multiple copies of the channel descriptor from existing in context buffers314.Control311 then increments an in-use count for the channel descriptor to track the number ofdata buffers314 that are associated with the same channel descriptor.
• If the correlated channel descriptor is not in context buffers[0051]315, then control311 requests the channel descriptor fromcontext DMA316.Context DMA316 transfers the requested channel descriptor from off-chip memory103 to one of the context buffers315 using the channel descriptor identifier, which may be an address, that was determined during context resolution.Control311 associates thecontext buffer315 holding the transferred channel descriptor with thedata buffer314 holding the new packet to maintain the correlation between the new5 packet and the channel descriptor.Control311 also sets the in-use counter for the transferred channel descriptor to one and sets the validity bit to indicate context information validity.
• [0052]Control311 also determines a priority for the new packet. The priority may be determined by the source of the new packet, header information, or channel descriptor. Control311 places an entry in one ofpriority queues313 based on the priority. The entry indicates thedata buffer314 that has the new packet.Arbiter312 implements an arbitration scheme to select the next entry forcore processor104.Core processor104 reads the next entry and processes the associated packet and channel descriptor in theparticular data buffer314 and context buffer315 indicated in the next entry.
• Each priority queue has a service-to-completion bit and a sleep bit. When the service-to-completion bit is set, the priority queue has a higher priority that any priority queues without the service-to-completion bit set. When the sleep bit is set, the priority queues is not processed until the sleep bit is cleared. The ranking of the priority queue number breaks priority ties. Each priority queue has a weight from 0-15 to ensure a certain percentage of core processor handling. After an entry from a priority queue is handled, its weight is decremented by one if the service-to-completion bit is not set The weights are re-initialized to a default value after 128 requests have been handled or if all weights are zero. Each priority queue has a high and low watermark. When outstanding requests that are entered in a priority queue exceed its high watermark, the service-to-completion bit is set. When the outstanding requests fall to the low watermark, the service-to-completion bit is cleared. The high watermark is typically set at the number of data buffers allocated to the priority queue.[0053]
• The context buffers[0054]315 each have an associated in-use counter. The in-use counters associated with the context buffers is not shown in FIG. 3, but it is shown in FIG. 6.
• [0055]Core processor104 may instructcontrol311 to transfer the packet to off-chip memory103 throughdata DMA317.Control311 decrements the context buffer in-use counter, and if the in-use counter is zero (no data buffers314 are associated with thecontext buffer315 holding the channel descriptor), then control311 instructscontext DMA316 to transfer the channel descriptor to off-chip memory103.Control311 also clears the validity bit. This same general procedure is followed whenscheduler105 requests packet transmission, except that in response to the request fromscheduler105,control311 instructsdata DMA317 to transfer the packet frommemory103 to one of data buffers314.
• The present invention provides additional circuitry associated with data buffers[0056]314. The additional circuitry provided by the present invention is shown in FIG. 6 and it will be explained in detail later.
• FIG. 4 is a flow diagram that illustrates the operation of[0057]coprocessor circuitry107 when correlating buffers in an example of the invention.Co-processor circuitry107 has eight pipelines to concurrently process multiple packet streams in accord with FIG. 3.
• First, a packet is stored in a data buffer, and the packet is correlated to a channel descriptor as identified by a channel identifier. The channel descriptor comprises the context information regarding how packets in the different channels are to be handled.[0058]
• Next, context buffers[0059]314 are checked for a valid version of the correlated channel descriptor. This entails matching the correlated channel identifier with a channel identifier in a context buffer that is valid. If the correlated channel descriptor is not in a context buffer that is valid, then the channel descriptor is retrieved frommemory103 and stored in a context buffer using the channel identifier. The data buffer holding the packet is associated with the context buffer holding the transferred channel descriptor. An in-use counter for the context buffer holding the channel descriptor is set to one. A validity bit for the context buffer is set to indicate that the channel descriptor in the context buffer is valid. If the correlated channel descriptor is already in a context buffer that is valid, then the data buffer holding the packet is associated with the context buffer already holding the channel descriptor. The in-use counter for the context buffer holding the channel descriptor is incremented.
• Typically,[0060]core processor104 instructsco-processor circuitry107 to transfer packets to off-chip memory103 or transmitinterface108.Data DMA317 transfers the packet and signalscontext DMA316 when finished.Context DMA316 decrements the in-use counter for the context buffer holding the channel descriptor, and if the decremented in-use count equals zero, thencontext DMA316 transfers the channel descriptor tomemory103 and clears the validity bit for the context buffer. The effect of DMA operations on the in-use counts of the special state buffers and the data buffers will be explained later. FIGS. 9A and 9B will be used to illustrate these operations.
Memory Interface109FIG.5
• FIG. 5 depicts a specific example of memory interface circuitry in accord with the present invention. Those skilled in the art will appreciate numerous variations from the circuitry shown in this example may be made. Furthermore, those skilled in the art will appreciate that some conventional aspects of FIGS.[0061]5-6 have been simplified or omitted for clarity.
• FIG. 5 is a block diagram that illustrates[0062]memory interface109.Memory interface109 comprises a hardware circuitry engine that is firmware-programmable in that it operates in response to state bits and register content. In contrast,core processor104 is a micro-processor that executes application software.Memory interface109 operates in parallel withcore processor104 to conserve core processor capacity by off-loading numerous tasks from the core processor.
• Both FIG. 1 and FIG. 5[0063]show memory103,core processor104,co-processor circuitry107, transmitinterface108, andmemory interface109.Memory103 comprises Static RAM (SRAM)525 and Synchronous Dynamic RAM (SDRAM)526, although other memory systems could also be used.SDRAM526 comprisespointer stack527 andexternal buffers528.Memory interface109 comprisesbuffer management engine520,SRAM interface521, andSDRAM interface522.Buffer management engine520 comprisespointer cache523 andcontrol logic524.
• Conventional components could be used for[0064]SRAM interface521,SDRAM interface522,SRAM525, andSDRAM526.SRAM interface521 exchanges context information betweenSRAM525 andco-processor circuitry107.External buffers528 use a linked list mechanism to store communication packets externally tointegrated circuit100.Pointer stack527 is a cache of pointers to freeexternal buffers528 that is initially built bycore processor104.Pointer cache523 stores pointers that were transferred frompointer stack527 and correspond toexternal buffers528. Sets of pointers may be periodically exchanged betweenpointer stack527 andpointer cache523. Typically, the exchange fromstack527 tocache523 operates on a first-in/first-out basis.
• In operation,[0065]core processor104 writes pointers to freeexternal buffers528 topointer stack527 inSDRAM526. ThroughSDRAM interface522,control logic524 transfers a subset of these pointers topointer cache523. When an entity, such ascore processor104,co-processor circuitry107, or an external system, needs to store a packet inmemory103, the entity reads a pointer frompointer cache523 and uses the pointer to transfer the packet toexternal buffers528 throughSDRAM interface522.Control logic524 allocates the external buffer as the corresponding pointer is read frompointer cache523. SDRAM stores the packet in the external buffer indicated by the pointer. Allocation means to reserve the buffer, so other entities do not improperly write to it while it is allocated.
• When the entity no longer needs the external buffer—for example, the packet is transferred from[0066]memory103 throughSDRAM interface522 toco-processor circuitry107 or transmitinterface108, then the entity writes the pointer topointer cache523.Control logic524 de-allocates the external buffer as the corresponding pointer is written topointer cache523. De-allocation means to release the buffer, so other entities may reserve it. The allocation and de-allocation process is repeated for otherexternal buffers528.
• [0067]Control logic524 tracks the number of the pointers inpointer cache523 that point to de-allocatedexternal buffers528. If the number reaches a minimum threshold, then controllogic524 transfers additional pointers frompointer stack527 topointer cache523.Control logic524 may also transfer an exhaustion signal tocore processor104 in this situation. If the number reaches a maximum threshold, then controllogic524 transfers an excess portion of the pointers frompointer cache523 topointer stack527.
• FIG. 6 shows the detailed logic added to the[0068]data buffer314 shown in FIG. 3 in an example of the invention. Thedata buffer314 includes two sections designated data only buffers614 and special state information buffers620. For this embodiment, there are six buffers for data only and six buffers for special state information, shown in the diagram. For other embodiments, there are numerous data buffers and special state information buffers. The data buffers are assigned an index number from zero to the maximum number of data buffers in theco-processor107. The special state information buffers are also assigned an index from zero to the maximum number of special state information buffers in theco-processor107. Furthermore, the context buffers are also assigned an index from zero to the maximum number of context buffers in theco-processor107. These indexes are used by the logic in theco-processor107 and thecore processor104 to identify an individual context buffer, data buffer, or special state information buffer. In one embodiment, there are sixteen of each of these type of buffers in theco-processor107. The exact number of each of these buffers is not significant to the general operation of the logic.
• Each buffer has an associated in-use counter[0069]614-0 to614-5 and620-0 to620-5. The in-use counters keep track of the number of events, which are using the data in the particular buffers. Each in-use counter is incremented by one for each event, which is using the data or state information in a particular buffer. When an event finishes with a particular buffer, the in-use counter is decremented by one. When the count in an in-use counter reaches zero, no events are using the particular buffer and it can be reallocated. Databuffer resolution logic622 and PRSR specialdata resolution logic621 operates similar to the operation ofcontext buffer resolution310, which was previously described.
• Data[0070]buffer resolution logic622 keeps track of which data buffers614 are in use and which are available to the assigned to new events. Databuffer resolution logic622 also contains the logic for incrementing and decrementing the in use counters associated with the data buffers614. PRSR specialdata resolution logic621 keeps track of which special state information buffers are in use and which are available to be assigned to new events. PRSR specialdata resolution logic621 also contains the logic for incrementing and decrementing the in use counters associated with the special state information buffers.
• PRSR special[0071]data resolution logic621 and databuffer resolution logic622 select a buffer to be assigned to a new event by scanning the in use counts of all their associated buffers and picking the buffer with the lowest index which has an in-use count of zero. In other embodiments, there are numerous variations in selecting a buffer to be assigned to a new event and which has an in-use count of zero. Some examples of selecting a buffer are first-in-first-out selection and last-in-first-out selection.
• [0072]Context resolution310 contains the logic used to select the context buffer to be assigned to a new event. A global configuration bit is used to pick which of two mechanisms is used to select the next context buffer to be assigned to a new event. One mechanism picks the context buffer in the same manner as the next data buffer is picked. As previous described, this method returns the context buffer with a zero in-use count which has the lowest index. The problem with this selection mechanism for context buffers is that the selection mechanism tends to select the context buffer that have been most recently freed. For instance, when context buffer with index zero is freed, it is always the next new index to be selected. Because context information, which is not already stored in a context buffer, needs to be read in from off-chip memory, under certain conditions is better to not reuse a context buffer as soon as its in-use count goes to zero.
• This problem is addressed by the second context selection mechanism. This mechanism uses a moving “finger” which determines at what index the logic will start searching for an in-use count of zero. The value of the finger is incremented after each new context selection. Hence, for the first context new selection the logic will start search forward from index zero. For the second new context select, the logic will start searching forward from[0073]index1, etc.
• As is shown by the arrows in FIG. 6, the special state information data buffer[0074]620 contains a pointer to an associateddata buffer614 as well as an associated context buffer315 (hereinafter these will also be referred to as resources). Because of these links, a special state data buffer can be used to identify the resources associated with an event. As shown by the arrows from the special state data buffers to thepriority queues313, a special state data buffer pointer is stored in the appropriate priority queue. This logic was described in more detail above instage3 of FIG. 3. When thearbiter312 picks the next entry to service from the priority queue, thearbiter312 returns a special state data buffer pointer. This pointer is then used by logic associated with thecore processor104 and theco-processor circuitry107 to identify the context and data buffer resources the event will be using.
• In one embodiment, the size of a[0075]data buffer614 is 64-bytes, the size of acontext buffer315 is 64-bytes, and the size of a specialstate data buffer620 is 44 bits. As recognized by those skilled in the art, the size of these buffers could be changed without affecting the operation of the logic in FIG. 6.
• FIG. 7 is a block flow diagram showing how a[0076]data buffer614 can be passed from one event to another event in an example of the invention. When a new event begins as indicated bysteps701 and702, a check is made to determine if the particular event is using a passed data buffer. If the particular event would like to use a “passed” data buffer, theparticular data buffer614 is associated with the event and the in-use counter for the particular data. Next as indicated bystep721, the event processing takes place and at the end of the event, the in-use counter of the data buffer is decremented by one instep722. Next as indicated bystep723, a check is made to determine if the in-use counter is zero. If the count is zero, the buffer is freed and can be assigned to a new event as indicated bystep725. If the count is not zero, as indicated bystep724, the buffer is not freed since the buffer is still in use by some other event.
• FIG. 8 is a block flow diagram showing how state information is passed between events in an example of the invention. As indicated by[0077]step802, a determination is made is as to whether or not an event is passing “state” information. If state information is not being passed, the operation proceeds as indicated bysteps810 to815. A new state information buffer is selected from the unused pool of buffers as indicated bystep810. Next as indicated bystep811 the event is performed. At the end of the event, the in-use counter is decremented by one (step812) and a check is made to determine if the count is zero atstep813. If the count is zero, the buffer is free to be assigned as indicated bystep815. Otherwise, the buffer is not freed as indicated byblock814.
• The operations that occur when “state” information is passed from one event to another event are indicated by[0078]steps804 to808. When “state” information is passed from one event to another event, the information in the data only buffer614 is also passed between the events. This is indicated bysteps804 and805. The event proceeds as indicated bystep806, and at the end of the event, as indicated bysteps807 and812, the in-use counter of the data only buffer614 and thestate information buffer620 is decreased by one. As indicated bysteps808,808-a and808-b and813 to815 the check is then made to determine if the in-use counter has reached zero to determine if the buffers can be re-assigned.
• An event can pass data or special state information associated with one event to a new event, which does not share the same context information. Such transfers are possible because the state information is stored in a buffer that is separate from the data buffer. An event can also pass a multi-bit message from a current event to a subsequent event that is generated by the current event. This message is stored in the special state buffer of the subsequent event.[0079]
• FIGS. 9A and 9B illustrate examples of how one embodiment of the invention operates. The horizontal dimension in FIGS. 9A and 9B represents time. FIG. 9A illustrates how the in-use counts for a data buffer change for an event which submits a DMA command in an example of the invention. The process begins at[0080]step901. It is assumed that at this point the in-use count of the data buffer is one. While the event posted as indicated bystep901 is progressing, steps902 and903 indicate that two DMA transfers are submitted. The data buffer count is incremented to two by the first DMA command and to three by the second DMA command. As indicated bystep904, when the first DMA transfer finishes, the in-use count is reduced to two. When the event posted as indicated byblock901 is complete, the in-use count is reduced to one as indicated byblock905. Finally, when the second DMA transfer is complete, the in-use count is reduced to zero as indicated bystep906. Conventional logic is provided inco-processor circuitry107 to handle the changes to the in-use counts as described.
• FIG. 9B indicates how the in-use count of a data buffer changes for an event, which creates a shared data buffer in an example of the invention. As in FIG. 9A, the horizontal dimension indicates time. The illustrated process begins as indicated by[0081]step911 with an event being posted. In one embodiment, this event requested a new data buffer. This data buffer would have an initial in-use count of zero and when the event is posted, as indicated bystep911, the in-use count is increased to one. Step921 represents another event request, which is posted as indicated bystep922. For the event request shown in921, the first event passes its data buffer to the second event so the second event starts with a data buffer in-use count of two. This initial in-use count of two is arrived at using multiple steps. When thecore processor104 initiates a request for another event, the data buffer in-use count is immediately incremented by one in order to reserve this data buffer for the next event. Instep922, the event request is for another core processor event, theco-processor circuitry107 receives this event request and passes this request to the section of the co-processor logic which handles core processor event requests. This is the same logic, which handled the initial event generation indicated in901 or911. When the event is processed by this section of the co-process logic, the in-use count of the data buffer is again incremented as this data buffer is assigned to the new event. When this new event is created, the section of theco-processor circuitry107 that handles event requests, signals back to the section of theco-processor circuitry107, which received this event request from thecore processor104. This section of the co-processor logic, now requests the in-use count of the data buffer be decremented by one. Hence, there is a total of two increments and one decrement and the new event is posted with an effective initial data buffer in-use count two.
• The system is setup so that if[0082]step922 is delayed by stalls in the system such that this event request is really processed after912 happens, the data buffer is reserved using in-use counts by the921 operation until the922 operation can take place. This assures that independent of the relative timing of922 and912 this is not time between912 and922 that the value of the data buffer's in-use count allows this passed data buffer to be viewed as an unassigned data buffer. The effective reservation of this data buffer by incrementing the is-use count when theevent request921 is posted, assures that no intervening event request can mistakenly view this data buffer as unassigned and reallocate this data buffer.
• [0083]Step912 indicates that when the first event is finished, the data buffer count is reduced to one.Steps931 and932 indicate a DMA request that is submitted and posted using the same data buffer. As indicated bysteps932 and931 the count is increased to two and then reduced to one when the DMA request is finished. Finally, as indicated bystep923, the event posed atstep922 is finished, the in-use count is reduced to zero and the data buffer can be re-assigned to a new event.
• It should be noted that the descriptions for the examples give in FIGS. 9A and 9B explain only the change in the data buffer in-use count. The in-use counts of the context and special state information buffers change in a similar manner.[0084]
• It should also be noted that the examples given in FIGS. 9A and 9B are meant to be illustrative examples only. Many other sequences can occur. The point of FIGS. 9A and 9B is to illustrate that with the present invention, there can be a composition of multiple processing tasks in situations where the subsequent tasks have no idea that any of their resources (data buffer/context buffer/special state buffer) had been processed by a previous service task. The in-use counters keep track of this automatically.[0085]
• While the invention has been shown and described with respect to embodiments thereof, it will be appreciated by those skilled in the art that various changes in forma and detail can be made without departing from the spirit and scope of the invention. Applicant's invention is limited only by the scope of the appended claims.[0086]

Claims (21)

We claim:

1. An integrated circuit for processing events related to communication packets, said integrated circuit comprising:

a core processor configured to execute software to process a series of communication packets, the processing of each packet being an event and having associated data and context information; and

a co-processor comprising a plurality of state information buffers for storing state information associated with events wherein each of said state information buffers having an in-use counter indicating the number of events associated with the contents of said buffer.

2. The integrated circuit ofclaim 1 wherein said co-processor comprises a plurality of context buffers for storing context information associated with a plurality of events.

3. The integrated circuit ofclaim 2 wherein said co-processor comprises an in-use counter associated with each of said context buffers.

4. The integrated circuit ofclaim 1 wherein said co-processor comprises a plurality of data buffers for storing data.

5. The integrated circuit ofclaim 4 wherein said co-processor comprises an in-use counter associated with each of said data buffers.

6. The integrated circuit ofclaim 1 wherein said integrated circuit comprises a plurality of data buffers each having an in-use counter whereby data can be transferred from one event to another event by changing information in a data buffer.

7. The integrated circuit ofclaim 1 wherein said integrated circuit comprises a plurality of buffers for data associated with events and a plurality of buffers for context associated with events.

8. The integrated circuit ofclaim 7 wherein said integrated circuit comprises an in-use counter associated with each of said buffers.

9. The integrated circuit ofclaim 1 wherein said co-processor comprises a plurality of data only information buffers, a plurality of context information buffers, an in-use counter for each of said data only buffers and an in-use counter for each of said context buffers.

10. The integrated circuit ofclaim 9 where data can be passed from one event to another event by changing the data in one of said state information buffers.

11. A method of processing events related to communication packets in an integrated circuit which includes a core processor and a co-processor having a state information buffer for storing state information for an event separate from the data associated with said event, said state information buffer having an associated in use counter, the method comprising:

incrementing the in-use counter associated with said state information buffer when an event is associated with said state information buffer; and

decrementing the in-use counter of said state information buffer when said event associated with said buffer is finished.

12. The method ofclaim 11 wherein said integrated circuit comprises a plurality of state information buffers.

13. The method ofclaim 11 wherein said integrated circuit comprises a context buffer and an in-use counter for said context information buffer and the method further comprises:

incrementing the in-use counter associated with said context buffer when an event is associated with said context buffer; and

decrementing the in-use counter of said context buffer when said events associated with said context buffer is finished.

14. The method ofclaim 11 wherein said integrated circuit comprises a data only buffer to store data associated with an event.

15. The method ofclaim 11 wherein said integrated circuit comprises a data only buffer to store data associated with an event and an in-use counter associated with said data only buffer and the method further comprises:

incrementing the in-use counter associated with said data buffer when an event is associated with said data buffer; and

decrementing the in-use counter of said data buffer when said event associated with said data buffer is finished.

16. An integrated circuit for processing events associated with communication packets which includes a core processor and a co-processor, the improvement which comprises, separate buffers for data and state information and in-use counters for all of said buffers, whereby the contents of a data can be passed from one event to another event, each of said events having state information in a separate state information buffer.

17. The integrated circuit ofclaim 16 which includes context information buffers.

18. The integrated circuit ofclaim 17 which includes in-use counters for said context information buffers.

19. The integrated circuit ofclaim 16 including a plurality of data buffers and a plurality of state information buffers.

20. The integrated circuit ofclaim 16 which includes a plurality of data buffers, a plurality of state information buffers and a plurality of context information buffers, each of said buffers having an in-use counter which is increments when an event is associated with the buffer and decremented when an event is finished utilizing the buffer.

21. An integrated circuit for processing events related to communication packets, said integrated circuit comprising:

a core processor configured to execute software to process a series of communication packets, the processing of each packet being an event and having associated data, state and context information; and

a co-processor having a plurality buffers which separately store data, state and context information associated with events wherein each of said data, state and context buffers having an in-use counter indicating the number of events associated with said buffer.

Images