Network device and method for packet processing

A network device and method for packet processing are provided. A packet processing accelerator is configured to receive packets from a network and define for ones of the packets a data unit corresponding to the packet. The packet processing accelerator is configured to perform a first set of packet processing operations on the data unit. A central processing unit (CPU) is configured to perform a second set of packet processing operations on the data unit. A buffer is configured to pass data units from the packet processing accelerator to the CPU, and vice versa, where the buffer is configured to store data units in one or more lines of the buffer. Dummy data units fill a space in a buffer line that is not occupied by a data unit, and the dummy data units include an indication that the space occupied by the dummy data units is an empty space.

FIELD

The technology described herein relates generally to data communications and more particularly to systems and methods for packet processing at a network device.

BACKGROUND

Emerging network devices include hardware elements that are configured to efficiently perform certain packet processing tasks, such as parsing. In addition, the emerging devices also include software processing elements that perform different processing operations using, for example, data that is parsed from the packets. The hardware elements of the network devices need to efficiently transfer data structures to the software processing elements, and vice versa.

SUMMARY

Examples of a network device and a method for packet processing are provided. An example network device includes a packet processing accelerator configured to receive packets from a network and define for ones of the packets a data unit corresponding to the packet. The data unit is defined at least by metadata related to the packet. The packet processing accelerator is also configured to perform a first set of packet processing operations on the data unit. The example network device also includes a central processing unit (CPU) configured to perform a second set of packet processing operations on the data unit. The second set of packet processing operations is different from the first set of packet processing operations and is defined by programmable code executed in the CPU. A buffer defined in a memory is configured to pass data units from the packet processing accelerator to the CPU, and vice versa, where the buffer has a fixed width and is configured to store data units in one or more lines of the buffer. Dummy data units fill a space in a buffer line that is not occupied by a data unit when the data unit does not fill a complete buffer line, and the dummy data units include an indication that the space occupied by the dummy data units is an empty space.

As another example, in a method for packet processing, packets are received from a network. A data unit corresponding to a packet is defined for ones of the packets, where the data unit is defined at least by metadata related to the packet. A first set of packet processing operations is performed on the data unit at a packet processing accelerator. Data units are passed from the packet processing accelerator to a central processing unit (CPU), and vice versa, via a buffer defined in a memory. The buffer has a fixed width and is configured to store data units in one or more lines of the buffer. The passing of the data units includes filling a space in a buffer line that is not occupied by a data unit with dummy data units when the data unit does not fill a complete buffer line, where the dummy data units include an indication that the space occupied by the dummy data units is an empty space. A second set of packet processing operations is performed on the data unit at the CPU, where the second set of packet processing operations is defined by programmable code executed in the CPU and is different from the first set of packet processing operations.

DETAILED DESCRIPTION

FIG. 1Ais a block diagram depicting a system-on-chip (SOC)100in accordance with an embodiment of the disclosure. In an example, the SOC100comprises at least a portion of a network device that is used in a packet-switching network to forward data packets from a source to a destination. The SOC100is generally used in a computer networking device that connects two or more computer systems, network segments, subnets, and so on. For example, the SOC100comprises at least a portion of a switch in one embodiment. The SOC100is not limited to a particular protocol layer or to a particular networking technology (e.g., Ethernet), and the SOC100comprises a portion of a bridge, a router, or a VPN concentrator, among other devices, in one embodiment.

The SOC100is configured, generally, to receive a packet118, such as an Ethernet packet, from a network101, and to process the packet118. In an example, the processing of the packet118is performed by one or more processors implemented as one or more integrated circuits disposed at least on the SOC100. These integrated circuits for performing the processing are included at least in packet processing accelerator102and central processing unit (CPU)104components of the SOC100, which are described in greater detail below. The SOC100is further configured, in an example, to forward the packet118to a final destination or another packet processing system.

In an example, the packet118is a data packet received at the SOC100via an input/output (IO) interface of the packet processing accelerator102. In an example, the packet processing accelerator102is a Network and Security Subsystem (NSS) component of the SOC100. The packet processing accelerator102is configured, generally, to receive and process packets from the network101. The processing of the packets performed by the packet processing accelerator102is described in further detail below. In addition to receiving the packet118, the packet processing accelerator102is further configured to define a data unit corresponding to the packet118, in an embodiment. In an example, the data unit defined by the packet processing accelerator102is known as a “descriptor” and comprises a data structure for storing various information relating to the packet118. The information stored by the data unit includes metadata related to the packet118, in an embodiment. In an example, the metadata stored by the data unit includes (i) a buffer descriptor that includes a pointer to a location of a payload of the packet118stored in a memory108, (ii) indicators of the required processing that the packet118should undergo, and (iii) data that classifies the packet (e.g., data that classifies the packet into a packet flow or group, based on, for example, a priority of the packet and/or a Quality of Service that the packet should receive), among other data. It is noted that the metadata described herein are only examples, and that the metadata stored by the data unit includes various other information related to the packet, in an example. In an example, the data unit stores a header, or a part of the header, of the packet118.

Processing of the data unit corresponding to the packet118occurs at the packet processing accelerator102and at the CPU104of the SOC100. Specifically, in an example, the packet processing accelerator102is configured to perform a first set of packet processing operations on the data unit, and the CPU104is configured to perform a second set of packet processing operations on the data unit, where the second set of packet processing operations is different from the first set of packet processing operations. The first set of packet processing operations includes (i) classifying packets into groups, per their priority and/or a Quality of Service that the packets should receive, and/or (ii) dropping low-priority packets when the traffic nears the capacity of the packet processing accelerator102, in an embodiment. The packet processing accelerator102performs the first set of packet processing operations in hardware, in an embodiment. In an alternative embodiment, the first set of packet processing operations are performed in a combination of hardware and firmware (e.g., black-box software that is invisible to the CPU104). The second set of packet processing operations performed by the CPU104is defined by software (e.g., programmable code) that is executed by the CPU104, in an embodiment. The second set of packet processing operations includes (i) additional (e.g., deeper) classifying of the packets into groups that not covered by the packet processing accelerator102, and/or (ii) routing packets within the SOC100or to other systems, in an embodiment. In an example, the performing of the first set of packet processing operations in the packet processing accelerator102improves an efficiency and packet throughput of the SOC100by offloading some of the processing that would otherwise be performed in the CPU104.

To enable the processing of the data unit in both the packet processing accelerator102and the CPU104, the SOC100includes a buffer106that is configured to pass data units between the packet processing accelerator102and the CPU104. Although the example ofFIG. 1illustrates the buffer106as being separate from the memory108, in other examples, the buffer106comprises a portion of the memory108. In such examples, the packet processing accelerator102and the CPU104exchange data via this portion of the memory108. Thus, in an embodiment, the buffer106is a space defined in a larger memory, such as the memory108, that is shared by the packet processing accelerator102and the CPU104.

In an example, the buffer106has a fixed width and is configured to store data units in one or more lines of the buffer106. The lines of the buffer106are referred to as “buffer lines” herein. In an example, the data units stored in the one or more lines of the buffer106do not have a uniform length (e.g., data units do not have a uniform length that is generally the same as a width of the buffer106). The data units stored in the buffer106thus have different sizes, with a size of a data unit depending, in an example, on a type of a packet with which the data unit is associated.

The packet processing accelerator102and the CPU104respectively are configured to write a plurality of data units to the buffer106, with the writing of the data units causing the buffer106to be populated, at a given time, with data units having different sizes. To illustrate aspects of the writing of variable-sized data units to the buffer106, reference is made toFIG. 1B. This figure is a block diagram depicting a portion150of the buffer100depicted inFIG. 1A, in accordance with an embodiment of the disclosure.FIG. 1Bshows the portion150of the buffer106storing data units (numbered 1-6) having different sizes.

The packet processing accelerator102and the CPU104are also configured to write dummy data units to the buffer106to enable more efficient passing of data units between the packet processing accelerator102and the CPU104. Such dummy data units (also known as “null data units” or “dummy buffers”) fill a space in a buffer line that is not occupied by a valid data unit corresponding to a packet, in an embodiment. In an example, the dummy data units include an indication that the space occupied by the dummy data units is an empty space. To illustrate example uses of the dummy data units,FIG. 1Bdepicts the portion150of the buffer106storing dummy data units152,154written to the buffer100by the packet processing accelerator102or the CPU104. In some instances, when writing a data unit to the buffer100, the packet processing accelerator102and the CPU104respectively are configured to (i) write dummy data units to a line of the buffer106, and (ii) write the data unit starting at a buffer location immediately following an end of the dummy data units, in an embodiment. For example, inFIG. 1B, when writing the Data Unit #6to the buffer106, the packet processing accelerator102or the CPU104writes the dummy data units154and then writes the Data Unit #6starting at the buffer location immediately following an end of the dummy data units154. Prior to writing the dummy data units154, the packet processing accelerator102or the CPU104determines a size of the dummy data units154, in an embodiment. Example algorithms used by the packet processing accelerator102and the CPU104in determining the size of the dummy data units154are described in detail below. In other examples, the data unit is not written starting at a buffer location immediately following an end of the dummy data units. In these examples, the data unit is offset from the preceding dummy data units by a predetermined distance. The predetermined distance is zero in an embodiment in which the data unit is written starting at the buffer location immediately following the end of the dummy data units. However, the predetermined distance is a finite offset distance in other embodiments.

Example conditions under which such dummy data units are written to the buffer100are described in further detail below. In an example, the packet processing accelerator102and the CPU104respectively are configured to identify a condition under which a data unit could be written to multiple, non-contiguous lines of the buffer106. This condition is undesirable, as multiple memory accesses to the buffer106would be required to read the data unit from the non-contiguous buffer lines. Upon identification of this condition, the packet processing accelerator102and the CPU104respectively are configured to write dummy data units to a line of the buffer106. As described in further detail below, this writing of the dummy data units eliminates the undesirable condition, such that the data unit is written to a single buffer line or multiple contiguous lines of the buffer106.

In some instances, the packet processing accelerator102and the CPU104respectively are configured to write dummy data units of a size that complete a line of the buffer106. An example of this is shown inFIG. 1B, which depicts the dummy data units152being dimensioned to complete a last buffer line of the portion150of the buffer100. In other instances, the packet processing accelerator102and the CPU104respectively are configured to write dummy data units of a size that do not complete a line of the buffer106. For example,FIG. 1Bdepicts the dummy data units154that do not complete a line of the buffer100. Example uses of dummy data units that complete a line of the buffer106and example uses of dummy data units that do not complete a line of the buffer106are described in further detail below. It is noted that the packet processing accelerator102and the CPU104respectively are configured to write the dummy data units to any of the lines of the buffer106.

The packet processing accelerator102and the CPU104are also respectively configured to read from the buffer106, where the reading includes the reading of both valid data units and dummy data units. In some instances, the packet processing accelerator102and the CPU104respectively are configured to (i) read the dummy data units and a data unit from the buffer106, and (ii) discard the dummy data units based on the dummy data units' indication that the space occupied by the dummy data units is an empty space. In such instances, the packet processing accelerator102and the CPU104respectively are configured to discard the dummy data units without performing the first or second sets of packet processing operations on the dummy data units. In other instances, dummy data units and a data unit stored in the buffer106are moved from the buffer106to an internal cache of the memory108. In an example where the buffer106comprises a portion of the memory108, the dummy data units and the data unit are moved from the buffer106to another portion of the memory108(e.g., the portion of the memory108including the internal cache). The movement occurs without explicit action by the packet processing accelerator102or the CPU104, in an embodiment. In these examples where data is moved from the buffer106to another portion of the memory108without explicit action by the packet processing accelerator102or the CPU104, transparent mechanisms such as caching and coherency move the data without requiring the packet processing accelerator102or CPU104to read and write the data. The dummy data units moved from the buffer106to the memory108complete a line of the memory108(e.g., a cache line of an internal cache of the memory108), in an embodiment.

FIG. 2is a block diagram illustrating additional features of the buffer106depicted inFIG. 1A, in accordance with an embodiment of the disclosure. As shown inFIG. 2, the buffer106includes a receive queue210and a send queue (i.e., transfer queue)212, in an embodiment. In passing data units from the packet processing accelerator102to the CPU104, the receive queue210is utilized. Thus, the packet processing accelerator102writes a data unit to the receive queue210starting at a location determined by a write pointer214, and the CPU104subsequently reads the data unit from the receive queue210based on a read pointer216. In passing data units from the CPU104to the packet processing accelerator102, the send queue212is utilized. The CPU104writes a data unit to the send queue212starting at a location determined by a write pointer218, and the packet processing accelerator102subsequently reads the data unit from the send queue212based on a read pointer220.

In an example, the receive and send queues210,212comprise circular queues (i.e., cyclic queues) configured to queue data units during the passing of the data units between the packet processing accelerator102and the CPU104. Each of the circular queues210,212has a head of the queue comprising a first buffer line of the buffer106and a tail of the queue comprising a second buffer line of the buffer106. As shown inFIG. 2, the circular receive queue210has a fixed maximum size of four buffer lines, and additional lines of the buffer106cannot be allocated to the queue210, in an example. A head of the queue210comprises a first buffer line202(numbered “0” inFIG. 2), and a tail of the queue210comprises a second buffer line204(numbered “3”). Similarly, the circular send queue212has a fixed maximum size of four buffer lines, with buffer lines206and208comprising the head and tail of the queue212, respectively. In each of the circular queues210,212, the first and last buffer lines comprising the respective heads and tails of the queues210,212are located at multiple, non-contiguous lines of the buffer106, in an embodiment. Further, each of the circular queues210,212has a fixed width that is equal to the fixed width of the buffer106. In an example, the queues210,212are defined by programmable code (e.g., software) executed in the CPU104.

To implement the “circular” (i.e., “cyclic”) nature of the queues210,212, in each of the queues, the tail of the queue is connected back to the head of the queue via a linking indication (e.g., a pointer), such that read and write pointers to the queue wrap around to a start of the queue upon reaching an end of the queue. Thus, for example, in the receive queue210ofFIG. 2, after the packet processing accelerator102writes data to the end of the receive queue210, the write pointer214wraps around to the start of the queue210. Next data written to the queue210starting a location determined by the write pointer214is stored at the start of the queue210.

With reference again toFIG. 1A, the packet processing accelerator102and the CPU104are also respectively configured to store data to the memory108. As explained above, in some examples, the buffer106comprises a portion of the memory108that is shared by the packet processing accelerator102and the CPU104. The memory108comprises at least a portion of the network device but is not disposed on the SOC100, in an embodiment. In other embodiments, the memory108is integrated into the SOC100. In an example, portions of the SOC100are distributed across multiple silicon dies that are coupled, for example, by way of a silicon interposer. In this example, the collection of dies makes up the SOC100. In an embodiment, the respective accelerator102, CPU104, and possibly memory108, are respectively disposed on separate silicon dies. In an example, upon receipt of the packet118, the packet processing accelerator102defines the data unit corresponding to the packet118based on metadata related to the packet118(as described above) and then writes a payload of the packet to the memory108. The payload is stored in a payload portion of the memory108, in an embodiment. The packet payload remains stored in the memory108and is accessed only when needed. With the packet payload stored to the memory108, only the data unit corresponding to the packet118is transferred between the packet processing accelerator102and the CPU104via the buffer106, in an embodiment. As noted above, the data unit corresponding to the packet118stores a pointer to a location of the payload of the packet118in the memory108. Additionally, as described in further detail below with reference toFIGS. 5A-6, data units held in the receive and send queues210,212of the buffer106are moved to an internal cache of the memory108, in an embodiment. In examples where the buffer106comprises a portion of the memory108, the data units are moved from a first portion of the memory108(e.g., a first portion comprising the receive and send queues210,212) to a second portion of the memory108(e.g., a second portion comprising the internal cache of the memory108), in an embodiment. The passing of data units between the different portions of the memory108is performed without explicit action by the packet processing accelerator102or the CPU104, in an embodiment. As described below, the writing of dummy data units to the receive and send queues210,212enables this passing of data units to be more efficient (e.g., to require fewer memory accesses).

As described herein, the buffer106is defined in a memory space shared by the packet processing accelerator102and the CPU104. In an example, the shared memory space is the memory108illustrated inFIG. 1and described herein. In some embodiments, the memory space comprises static random-access memory (SRAM), and in other embodiments, the memory space comprises dynamic random-access memory (DRAM). The shared memory space also stores packet payloads in an embodiment, but not necessarily.

As described above, data units corresponding to packets are transferred between the packet processing accelerator102and the CPU104via the queues210,212of the buffer106. In order to save storage space and transfer bandwidth, the schemes and mechanisms described herein accommodate data units having different sizes. By allowing data units to have different sizes, information (e.g., a packet's header, software-firmware fields, etc.) can be stored in a data unit only when the information is needed, thus avoiding a fixed-size data unit that stores information regardless of whether the information is needed. The variable-sized data unit approach described herein allows data units to be kept as small as possible, in an example. The use of data units having different sizes varies from conventional approaches, which utilize data units having a fixed size, in which the data units themselves typically are padded to maintain size uniformity of the data units.

To illustrate aspects of the variable-sized data unit approach, reference is made toFIG. 3A. This figure depicts a circular queue300configured to store data units having different sizes. In an example, the circular queue300is the receive queue210or the send queue212of the buffer106. Thus, the queue300comprises a fixed number of lines of the buffer106and has a head of the queue comprising a first buffer line301of the buffer106and a tail of the queue comprising a second buffer line302of the buffer106. The tail of the queue300is connected back to the head of the queue300via a linking indication, such that write and read pointers308,310wrap around to a start of the queue300upon reaching an end of the queue300. In the circular queue300, the first and second buffer lines301,302comprising the respective head and tail of the queue300are disposed at multiple, non-contiguous lines of the buffer106, in an embodiment.

In the example ofFIG. 3A, the circular queue300is configured to store data units (numbered 1-6) having different sizes, with one or more of the data units being stored starting at locations of the buffer106that are not beginnings of buffer lines. For example, inFIG. 3A, although Data Unit #1is stored starting at a beginning of a buffer line, Data Unit #2is stored starting at an intermediate position of the same buffer line that is not the beginning of the buffer line. Thus, the packet processing accelerator102and the CPU104respectively are configured to write data units to the buffer106(i) starting at beginnings of buffer lines, and (ii) starting at locations of the buffer106that are not beginnings of buffer lines.

The circular queue300is also configured to store a data unit having a size that is greater than an amount of available space in a given buffer line in multiple lines of the buffer. In an example, a first portion of the data unit is stored in the given buffer line, and a second portion of the data unit is stored in at least one other buffer line that is different than the given buffer line. The packet processing accelerator102and the CPU104respectively are configured to write the data units to the buffer106in this manner. For example, inFIG. 3A, after the Data Unit #1is written to a buffer line303, it can be seen that the Data Unit #2has a size that is greater than the amount of available space in the buffer line303. Consequently, the packet processing accelerator102or the CPU104writes the Data Unit #2to multiple lines of the buffer106, with a first portion304of the Data Unit #2being written to the buffer line303and a second portion305of the Data Unit #2being written to the buffer line302.

The circular or cyclic nature of the queue300(e.g., where pointers308,310accessing the queue300wrap around upon reaching the end of the queue300) creates the possibility that portions of a data unit could be written to both the head buffer line and the tail buffer line of the queue300. This possibility is illustrated inFIG. 3A. After the packet processing accelerator102or the CPU104writes the first and second portions of the Data Unit #2to the buffer lines303,302, respectively, a Data Unit #3is to be written to the circular queue300starting at a location immediately following an end of the Data Unit #2. An amount of available space in the buffer line302is X bytes, as illustrated inFIG. 3A. Because the Data Unit #3has a size that is greater than X bytes, the Data Unit #3is stored in multiple lines of the buffer. Thus, the packet processing accelerator102or the CPU104writes a first portion306of the Data Unit #3to the buffer line302. After the writing of the first portion306to the buffer line302, the write pointer308reaches the end of the queue300and wraps around to the start of the queue300. This is illustrated inFIG. 3A, which shows the write pointer308positioned at the start of the queue300. After the write pointer308wraps around, the packet processing accelerator102or the CPU104writes a second portion307of the Data Unit #3to the buffer line301.

As noted above, the buffer lines301,302comprising the head and tail of the queue300, respectively, are located at multiple, non-contiguous lines of the buffer106, in an embodiment. Because the packet processing accelerator102and the CPU104access the circular queues210,212of the buffer106via standard buses in burst transactions to a contiguous memory range, the splitting of the Data Unit #3between the head and tail of the queue300requires the packet processing accelerator102or the CPU104to perform two memory accesses to read this data unit. This is undesirable, as it is inefficient to require multiple memory accesses to read the data unit. It is also undesirable because the second memory access could be a cache miss or a page miss due to the wrap around. As explained above, the buffer106comprises a portion of the memory108, in an embodiment. In some examples, the memory108is DRAM memory. The DRAM memory serves faster data that belongs to the same cache line or page (e.g., where the cache line or page has a size of several KBs) that was recently accessed. A memory access after a wrap around (e.g., a wrap around as described above, where first data is written to the end of the queue, a write pointer wraps around to the start of the queue, and second data is written to the start of the queue) increases the probability of this situation occurring.

In order to eliminate or minimize the occurrence of such undesirable situations, the techniques described herein utilize dummy data units. Such dummy data units are intentionally written to the queues210,212of the buffer106to prevent the undesirable situation illustrated inFIG. 3A, in an embodiment. The determination as to when the dummy data units should be written to a queue and the actual writing of the dummy data units are performed by the packet processing accelerator102or the CPU104writing to the queue. Thus, with reference toFIGS. 1A and 2, the packet processing accelerator102that writes to the receive queue210determines when the dummy data units should be written to the receive queue210and performs the writing of the dummy data units to the receive queue210. Likewise, the CPU104that writes to the send queue212determines when the dummy data units should be written to the send queue212and performs the writing of the dummy data units to the send queue212.

To illustrate an example use of the dummy data units,FIG. 3Bdepicts a circular queue350. The circular queue350has properties similar to those of the circular queue300ofFIG. 3A. Specifically, pointers352,356accessing the queue350wrap around when they reach the end of the queue350, and the queue350is configured to store variable-sized data units in one or more buffer lines. In an example, Data Unit #1is written to the buffer line303by the packet processing accelerator102or the CPU104. Next, first and second portions of Data Unit #2are written to the buffer lines303,302, respectively, by the packet processing accelerator102or the CPU104. After each of these writes, a write pointer352is advanced within the circular queue350.

At this point, a Data Unit #3is to be written to the circular queue350, potentially starting at a location determined by the write pointer352that immediately follows an end of the Data Unit #2. In an example, the packet processing accelerator102or the CPU104identifies a wrap-around condition in the circular queue350. Specifically, the packet processing accelerator102or the CPU104identifies that the Data Unit #3, if written to the queue350starting at the location determined by the write pointer352, would include a portion of data disposed in the buffer line301and another portion of data disposed in the buffer line302. This would occur due to the write pointer352wrapping around to the start of the queue350upon reaching the end of the queue350. As explained above, this condition is undesirable. The packet processing accelerator102or the CPU104identifies this condition, in an embodiment, based on the fact that the amount of available space in the queue350between the write pointer352and the end of the queue350(equal to X bytes in the example ofFIG. 3B) is less than a size of the Data Unit #3(equal to Y bytes in the example ofFIG. 3B).

Based on the identification of the wrap-around condition, the packet processing accelerator102or the CPU104writes dummy data units354to the last line of the circular queue350, starting at the location determined by the write pointer352. As shown inFIG. 3B, the dummy data units354complete the last buffer line. After writing the dummy data units354, the write pointer352wraps around to the start of the queue, and the packet processing accelerator102or the CPU104writes the Data Unit #3to the buffer line301starting at a location of the advanced write pointer.

The writing of the Data Unit #3to the head of the queue350in this manner enables the packet processing accelerator102or the CPU104(i.e., the component reading from the queue350based on a read pointer356) to read the Data Unit #3using a single memory access and without reading from both of the non-contiguous buffer lines301,302. This is in contrast to the multiple memory accesses that would be required to read the Data Unit #3if the Data Unit #3was written to both of the buffer lines301,302(e.g., as was illustrated inFIG. 3A). The writing of the dummy data units354at the end of the queue350thus enables more efficient passing of data units between the packet processing accelerator102and the CPU104by decreasing a number of memory accesses required in reading certain data units from the queue350.

FIG. 4Ais a flow diagram400depicting example steps performed by the packet processing accelerator102or the CPU104in writing a data unit to the circular queue350ofFIG. 3B, in accordance with an embodiment of the disclosure. At401, an amount of space between a write pointer and an end of the circular queue350is determined. At402, it is determined whether a size of the data unit to be written to the circular queue350is greater than the amount of space available. If the size of the data unit is not greater than the amount of space, at404, the data unit is written to the circular queue starting at a location determined by the write pointer. If the size of the data unit is greater than the amount of space, this indicates a presence of a wrap-around condition. Based on the identification of the wrap-around condition, at406, a space in the circular queue350between the write pointer and the end of the circular queue350is filled with dummy data units. At408, the write pointer is advanced to the start of the circular queue350as a result of the write pointer wrapping around to the start of the queue350upon reaching the end of the queue350. At410, the data unit is written to the circular queue350starting at a location determined by the advanced write pointer.

The writing of dummy data units to the circular queue350, as described above with reference toFIGS. 3B and 4A, enables a particular data unit to be read from the circular queue350without reading from both of the non-contiguous buffer lines301,302.FIG. 4Bis a flow diagram450depicting example steps performed by the packet processing accelerator102or the CPU104in reading the particular data unit from the circular queue350ofFIG. 3B, in accordance with an embodiment of the disclosure. As data units are read from the queue350by the packet processing accelerator102or the CPU104, the read pointer356is advanced. The read pointer356eventually reaches the buffer line302, which is the last buffer line of the cyclic queue350. At452, the buffer line302, including the dummy data units354, is read.

At454, the dummy data units354are discarded. In an example, the dummy data units354are discarded based on an indication included in the dummy data units354, where the indication indicates that a space occupied by the dummy data units354is an empty space. In an example, all data units (i.e., both null data units comprising dummy data units and valid data units) written to the circular queue350include a field (e.g., a binary, one-bit field) that specifies whether the data unit is null or not. Thus, for example, if the data unit includes the field having a first logical value, the component that reads the data unit identifies the data unit as comprising dummy data units and subsequently discards the data unit, in an embodiment. Conversely, if a data unit includes the field having a second logical value, the component that reads the data unit identifies the data unit as being a valid data unit corresponding to a packet and does not discard the data unit, in an embodiment.

In these examples, the packet processing accelerator102and the CPU104respectively are configured to (i) read a data unit from the circular queue350, (ii) identify a presence or absence of the indication that the space occupied by the data unit is an empty space, and (iii) discard or not discard the data unit based on the presence or absence of the indication. Specifically, the CPU104performs these steps if the circular queue350is the receive queue210of the buffer106, and the packet processing accelerator104performs these steps if the circular queue350is the send queue212of the buffer106.

At456, following the reading of the buffer line302, the read pointer356wraps around to the start of the queue350. At458, the buffer line301, which is the first buffer line of the circular queue350, is read. In reading the buffer line301, the Data Unit #3is read. Thus, the Data Unit #3is read without reading from both the first and last lines301,302of the circular queue350.

As noted above with reference toFIG. 1A, the packet processing accelerator102and the CPU104respectively are configured to store data to a memory108. Specifically, in an example, upon receipt of the packet118, the packet processing accelerator102defines the data unit corresponding to the packet118and stores the payload of the packet to the memory108. The data unit corresponding to the packet118includes a pointer to a location of the payload of the packet118in the memory108, in an embodiment. Additionally, in an example, data units stored in the circular queues210,212are moved from the circular queues210,212to an internal cache of the memory108. In an example where the buffer106comprises a portion of the memory108, the data units are moved from a first portion of the memory108(e.g., a portion of the memory108including the circular queue210or the circular queue212) to a second portion of the memory108(e.g., a portion of the memory including the internal cache of the memory108). The movement occurs without explicit action by the packet processing accelerator102or the CPU104, in an embodiment.

To illustrate aspects of the movement of data units from the circular queues210,212to the internal cache of the memory108, reference is made toFIG. 5A. It is noted thatFIG. 5Adoes not illustrate the use of dummy data units. The description ofFIG. 5Ais intended to be contrasted with that ofFIG. 5B, which does illustrate the use of dummy data units. This figure depicts a circular queue500configured to store data units having different sizes, in an embodiment. In an example, the circular queue500is one of the circular queues210,212depicted inFIG. 2. The circular queue500ofFIG. 5Ahas properties similar to those of the circular queues300,350ofFIGS. 3A and 3Band has a fixed width (e.g., 128 bytes in the example ofFIG. 5A) that is equal to the fixed width of the buffer106.

FIG. 5Aalso depicts example features of a cache540. The cache540comprises a first portion of the memory108, in an example. As described above, the buffer106is part of the memory108, in an example. Because the circular queue500is part of the buffer106, the circular queue comprises a second portion of the memory108, in an example. As illustrated in the figure, the cache540has a fixed width (e.g., 64 bytes in the example ofFIG. 5A) that is different from the fixed width of the circular queue500, in an embodiment. In an example, each buffer line in the circular queue500has a size of 128 bytes, and a cache line size of the cache540is 64 bytes. The buffer line size of 128 bytes relates to a typical size of a data unit that is written as a burst access to the circular queue500. The cache540is configured to store data, including data units moved from the circular queue500, in one or more lines of the cache540. When the data units are moved from the queue500to the cache540, there is a possibility that a data unit could be stored in a number of lines of the cache540that is greater than a minimum number of lines necessary to store the data unit. For example, if the cache540has a fixed width of 64 bytes, then a minimum number of lines necessary to store a 128-byte data unit is two. Storing the 128-byte data unit in three or more lines of the cache540is an example of storing a data unit in a number of lines that is greater than the minimum number of lines necessary to store the data unit. This possibility is illustrated inFIG. 5Aand described below with reference to that figure.

InFIG. 5A, after Data Unit #3, Data Unit #4, and Data Unit #5are written to portions of the first, second, and third buffer lines comprising the queue500, a Data Unit #6is to be written to the circular queue500starting at a location determined by a write pointer506. The Data Unit #6has a size of Y bytes. The Data Unit #6, upon being moved from the circular queue500to the cache540, would be stored starting at a location of the cache540determined by a second write pointer509, which is included in a third cache line of the cache540. An amount of available space in the third line of the cache540is equal to X bytes, where Y is greater than X. Thus, if the Data Unit #6is written to the circular queue500starting at the location determined by the write pointer506, this data unit, upon being moved from the circular queue500to the cache540, would be disposed in two lines of the cache540(i.e., a first X bytes of the Data Unit #6would be stored in the third line of the cache540, and a remaining portion of the Data Unit #6would be stored in the fourth line of the cache540).

Because the Y bytes of the Data Unit #6are less than the 64 bytes comprising the fixed width of the cache540in the example ofFIG. 5A, the Data Unit #6would be disposed in a number of lines of the cache540that is greater than a minimum number of lines necessary to store the Data Unit #6. In other words, although the Y bytes of the Data Unit #6could fit within a single cache line of the cache540, in the scenario detailed above, the Data Unit #6would be disposed in two cache lines of the cache540. This is undesirable, as it requires multiple memory accesses to write the Data Unit #6to multiple lines of the cache540, which is in contrast to the single memory access that would be required to write the Data Unit #6to a single cache line, in an embodiment. Further, subsequent reading of the Data Unit #6from the multiple lines of the cache540would require multiple memory accesses instead of a single memory access, in an embodiment.

In order to eliminate the occurrence of such undesirable situations, dummy data units similar to those described above with reference toFIGS. 3A-4Bare intentionally written to the queue. The determination as to when the dummy data units should be written to a queue and the actual writing of the dummy data units are performed by the packet processing accelerator102or the CPU104writing to the queue. Specifically, in an example, the packet processing accelerator102writes the dummy data units to the receive queue210, and the CPU104writes the dummy data units to the send queue212.

To illustrate an example writing of dummy data units to a queue in accordance with an embodiment of the disclosure, reference is made toFIG. 5B. In this figure, after the writing of Data Unit #3, Data Unit #4, and Data Unit #5to portions of the first, second, and third buffer lines of the circular queue550, a write pointer556is positioned immediately after the Data Unit #5, and a Data Unit #6is to be written to the circular queue550. As in the example ofFIG. 5A, the Data Unit #6has a size of Y bytes. A next data unit written to the circular queue550starting at a location determined by the write pointer556will be later moved from the circular queue550to the cache540. The moving causes this data unit to be stored in the cache540starting at a location determined by a second write pointer559, which is included in a third cache line of the cache540. As in the example ofFIG. 5A, an amount of available space in the third line of the cache540is equal to X bytes, where Y is greater than X.

In an example, the packet processing accelerator102or the CPU104makes a determination that the Data Unit #6, if written to the circular queue550starting at the location determined by the write pointer556, would be disposed in a number of lines of the cache540(e.g., 2 cache lines in the example ofFIG. 5B) that is greater than a minimum number of lines necessary to store the Data Unit #6(e.g., a single cache line). As explained above, this is undesirable. Based on this determination, the packet processing accelerator102or the CPU104writes dummy data units504to the circular queue550starting at the location determined by the write pointer556. As shown inFIG. 5B, the dummy data units504have a size of X bytes, which is equal to the amount of available space in the third line of the cache540. After writing the dummy data units504to the circular queue550, the write pointer556is advanced to a location in the queue550immediately following an end of the dummy data units504, and the Data Unit #6is written to the queue550starting at a location determined by the write pointer that has been advanced.

After the writing of the dummy data units504and the Data Unit #6to the circular queue550, the dummy data units504and the Data Unit #6are moved from the circular queue550to the cache540. This moving causes the dummy data units504to be stored in the cache540starting at the location determined by the second write pointer559, which is included in the third cache line of the cache540. Because the dummy data units504have the size of X bytes that is equal to the amount of available space in the third cache line, the dummy data units504complete the third cache line. The second write pointer559is then advanced to a beginning of a fourth line of the cache540. The Data Unit #6is written to the cache540starting at the location determined by the advanced write pointer559.

Because the Y bytes of the Data Unit #6are less than the 64 bytes comprising the fixed width of the cache540in the example ofFIG. 5B, the Data Unit #6is stored in a single line of the cache540, which is the minimum number of lines of the cache540necessary to store the Data Unit #6. Storing the Data Unit #6to the single line of the cache540enables the Data Unit #6to be written to the cache540and read from the cache540using a minimum number of memory accesses. The writing of the dummy data units504to the circular queue550and the subsequent moving of these dummy data units504to the cache540thus enables more efficient storage and retrieval of data units to and from the cache540.

FIG. 6is a flow diagram600depicting example steps performed by the packet processing accelerator102or the CPU104in writing a data unit to the circular queue550ofFIG. 5B, in accordance with an embodiment of the disclosure. As described above with reference toFIG. 5B, a data unit written to the circular queue550is moved from the queue550to the cache540, in an embodiment. At602, the packet processing accelerator102or the CPU104determines an amount of free space available in a line of the cache540to which the data unit would be moved if written to the circular queue550starting at a location determined by a write pointer. In the example ofFIG. 5B, the amount of free space available in the third cache line to which the Data Unit #6would be moved is equal to X bytes.

At604, the packet processing accelerator102or the CPU104determines a remainder of a division of a size of the data unit by the fixed width of a line of the cache540, where the remainder is a second amount of space. In an example, the remainder is determined based on
remainder=(size of the data unit)mod(fixed width of the cache line),
where “mod” is the modulo operator. In the example ofFIG. 5B, the size of the Data Unit #6is Y bytes, and the fixed width of the line of the cache540is 64 bytes. Assuming, for example, that Y is equal to 40, such that the Data Unit #6has a size of 40 bytes, the remainder (i.e., equal to 40 bytes mod 64 bytes) is 40 bytes. At606, it is determined whether the remainder is greater than the amount of free space available in the line of the cache540to which the data unit would be moved. As noted above, in the example ofFIG. 5B, the amount of free space available in the third cache line to which the Data Unit #6would be moved is equal to X bytes. Assuming, for example, that X is equal to 32 bytes, then the example remainder of 40 bytes is greater than the amount of free space available in the third cache line.

If the result of the determination at606is “no,” then at608, the data unit is written to the circular queue550starting at the location of the circular queue550determined by the write pointer. Conversely, if the result of the determination at606is “yes,” then at610, dummy data units having a size equal to the amount of free space available in the line of the cache540to which the data unit would be moved is written to the circular queue550. The dummy data units are written to the circular queue550starting at the location of the circular queue550determined by the write pointer. At612, the write pointer is advanced to a location in the circular queue550immediately following the dummy data units. At614, the data unit is written to the circular queue550starting at the location determined by the advanced write pointer.

The writing of dummy data units to the circular queue550, as described above with reference toFIGS. 5B and 6, enables a data unit to be moved to the cache540of the memory108in a minimum number of cache lines necessary to store the data unit.

It is noted that in an embodiment, the packet processing accelerator102and the CPU104respectively are configured to write dummy data units to the buffer106under both the conditions described above with reference toFIGS. 3B-4Aand the conditions described above with reference toFIGS. 5B-6. Thus, in an example, when writing a data unit to the buffer106, the packet processing accelerator102and the CPU104respectively are configured to (i) determine a presence or an absence of a wrap-around condition and write dummy data units, if necessary (i.e., as described above with reference toFIGS. 3B-4A), and also (ii) determine a presence or absence of a condition under which the data unit would be stored in a number of lines of the memory108that is greater than a minimum number of lines necessary to store the data unit and write dummy data units, if necessary (i.e., as described above with reference toFIGS. 5B-6). Similarly, in an embodiment, the packet processing accelerator102and the CPU104respectively are configured to read and process dummy data units from the buffer106under both the conditions described above with reference toFIGS. 3B-4Band the conditions described above with reference toFIGS. 5B-6.

As described herein, the send and receive queues210,212of the buffer106are configured to be populated, at a given point in time, with data units having different sizes (e.g., the send queue210is configured to be populated, at a given point in time, with a first data unit having a size of 30 bytes and a second data unit having a size of 60 bytes). The use of data units having different sizes allows content to be stored in a data unit only when the content is necessary, thus allowing sizes of data units to be kept to a minimum. An example of content that may be stored in a variable-sized data unit depending on whether it is needed or not is a packet's headers. As described above, a data unit corresponds to a packet received from a network, and in certain instances, it is useful to extract the headers from the packet and include the headers as part of the data unit. Such extraction of the headers and building of the data unit are performed by the packet processing accelerator102. An example format for a variable-sized data unit is illustrated inFIG. 7. This figure shows that the variable-sized data unit700includes a portion706for storing L2, L3, and L4 headers of a packet that corresponds to the data unit700, in an embodiment. The portion706itself has different sizes in different examples, depending on the headers and sizes of the headers stored in the field706.

In addition to the portion706for storing the packet headers, the data unit700also includes a fixed-size control portion702. The fixed-size control portion702includes various control and status fields with which the packet processing accelerator102and/or the CPU104interact. Although other portions of the data unit (i.e., portions704,706) are optional and only included in the data unit700if necessary, the fixed-size control portion702comprises a portion of all data units, in an example. The control and status fields of the fixed-size control portion702include a size field703that defines a size of the data unit700. The size of the data unit700defined by the size field703is based on a size of the fixed-size control portion702and sizes of any other portions (e.g., optional portions704,706) that are included in the data unit700, in an embodiment.

In an example, the fixed-size control portion702has a size of 16 bytes. Thus, a minimum size of the data unit700is 16 bytes, in an embodiment. Further, in an example, the size of the data unit700is some multiple of 16 bytes, with a maximum size of 128 bytes. In examples where the buffer106has a fixed width of 128 bytes (e.g., as illustrated in the example ofFIGS. 5A and 5B), a size of the dummy data units is between 16 bytes and (128-16) bytes. It is noted that the sizes described herein are examples only.

Another example of content that may be stored in a variable-sized data unit depending on whether it is needed or not is information to be passed between the packet processing accelerator102and the CPU104. Such information is used, in an example, to pass conclusions from the packet processing accelerator102to the CPU104or to pass intent from the CPU104to the packet processing accelerator102. Such information is used, in other examples, to add new packet processing flows (e.g., due to new customer requests). This information is also used to change the work partition between the packet processing accelerator102and the CPU104when processing packets, in an embodiment. Further, such information is used to implement fixes and workarounds for problems identified in the field, in an embodiment. In the example ofFIG. 7, this information is stored in a variable-sized control portion704of the data unit700.

In general, the variable-sized control portion704is used to store any additional control or status data (e.g., additional metadata) beyond what is stored in the fixed-size control portion702. In an example, the CPU104sends a group of fragments with a shared header (e.g., a scatter-gather list), such that a first data unit has a larger size and includes both control data and headers of a corresponding packet, and a second data unit has a smaller size and includes only a pointer to the fragments' payload in the memory108. In this example, the first data unit uses the variable-sized control portion704to store additional control data beyond what is stored in the fixed-size control portion702and uses the portion706for storing the headers.

In another example, where a packet has a very small size, the entire packet is stored in a data unit. This promotes efficiency because it eliminates a need to store a payload of the packet to the memory108and subsequently retrieve the payload from the memory108. In this example, the variable-sized control portion704is used to store the payload of the packet, and the portion706is used to store the headers of the packet.

FIG. 8is a flow diagram800depicting steps of a method for packet processing in accordance with an embodiment of the disclosure. At802, packets are received from a network. At804, a data unit corresponding to a packet is defined for ones of the packets, where the data unit is defined by metadata related to the packet. At806, a first set of packet processing operations is performed on the data unit at a packet processing accelerator. At808, data units are passed from the packet processing accelerator to a central processing unit (CPU), and vice versa, via a buffer defined in a memory. The buffer has a fixed width and is configured to store data units in one or more lines of the buffer. The passing of the data units includes filling a space in a buffer line that is not occupied by a data unit with dummy data units when the data unit does not fill a complete buffer line, where the dummy data units include an indication that the space occupied by the dummy data units is empty. At810, a second set of packet processing operations is performed on the data unit at the CPU, where the second set of packet processing operations is defined by programmable code and is different from the first set of packet processing operations.

This application uses examples to illustrate the invention. The patentable scope of the invention may include other examples.