HK1230303A1 - A packet processing system, method and device to optimize packet buffer space - Google Patents

Abstract

A buffer logic unit of a packet processing device that is configured to allocate single pages to two or more packets if the current packets stored on the page do not fully fill the single page and to store and maintain page slot specific page state data for each of the packet data stored on the pages.

Description

Packet processing system, method and apparatus to optimize packet buffer space

Technical Field

The present invention relates to a packet processing system. More particularly, the present invention relates to optimizing packet buffer space in a packet processing system.

Background

Packet processing devices, such as switch microchips, often need to buffer packets into a Packet Memory (PM) having one or more banks (banks) as the device processes them. The current solution to store packets in the device's packet memory is to assign multiple chunks (called pages) of packet memory to each packet, rather than a single large chunk. With this approach, the packets are not stored contiguously in the banks of the packet memory, but are spread out over one or more pages that together form a linked list of pages that is mapped across the banks of the packet memory. Further, a plurality of these banks (and pages mapped to them) can be logically grouped into a pool (of banks and associated pages). Therefore, a linked list of all pages used by a particular packet in the packet buffer needs to be maintained in the switch (in the buffer manager or BM); this linked list is traversed as packets are read out of the packet buffer for transmission. Each page has associated with it a state that contains some information about the page. The state of all pages in the packet processor device is maintained in the switch. The packet is associated with a descriptor or tag (token) that contains, among other fields, a pointer to the first page. With this start pointer, all pages used by a packet can be retrieved in the same order they were used to store the incoming packet by traversing the linked list constructed with the next page pointer for a different page state. As a result, a linked list of all pages (and therefore banks) used by a particular packet is maintained in the switch, and then traversed to locate and read out the packet from the packet memory for transmission.

In these page-based packet processing devices, there is a tradeoff between wasted packet memory and the bandwidth requirements imposed on the buffer manager. The larger the size of each of the pages, the fewer accesses are required to read and write packet data, and thus the less pressure on the bandwidth of the buffer manager. However, a larger size of a page means that a larger portion of the packet memory may be wasted or unused, as packets that do not fill the entire page will result in the remainder of the page being unused. On the other hand, the smaller the page size, the less packet memory is wasted or unused on average, but the more pressure is applied to the buffer manager due to the increase in the number of accesses required to read and write each packet to a smaller page.

In addition, in some packet processing devices, if a portion of two or more packets has a matching portion (e.g., a header portion or a body portion) of packet data, the packets can share a page or pages in which the matching portion of packet data is stored, so that the matching data is not stored twice in different locations (e.g., different pages). To keep track of the number of packets that need to use a page, the buffer manager maintains a reference count value for each of the pages that indicates the number of pages that share the page and from which packet data has not been read. For example, when a device determines that more packets need to use a page (e.g., more packets have portions that match portions of data stored on the page), the device can increment a reference count value to account for (account for) the added packets that need to use the page. Similarly, when data is read from the pages for one or more of the packets (so that the page no longer needs to be used for the packets), the device can decrement the reference count value to account for the smaller number of packets that need to use the page. Thus, when the reference count is reduced to zero, the device can reclaim the page for reuse with other data because no more packets need to use the data stored on the page.

Disclosure of Invention

A buffer logic unit of a packet processing device is configured to allocate a single page to two or more packets if a current packet stored on the page does not completely fill the page. As a result, the buffer logic can reduce the amount of wasted packet memory space by reducing the amount of unused space on each of the pages.

A first aspect is directed to a packet processing system on a packet processing device. The system comprises: a non-transitory computer-readable banked memory comprising a plurality of physical memory cells logically divided into a plurality of pages such that each of the pages defines a separate portion of the physical memory cells; and buffer logic at least partially stored on the non-transitory computer readable buffer memory, wherein the buffer logic is configured to: allocating one of the pages to store packet data of a first packet of the plurality of packets; and if the page of pages is determined to be not sufficiently occupied by packet data of the first packet, allocating at least a portion of the unoccupied remainder of the page of pages to store packet data of one or more further packets of the plurality of packets, such that the page of pages is allocated to two or more packets of the plurality of packets. In some embodiments, each of the pages includes a plurality of segments, and the buffer memory logic determines that a page of the pages is not fully occupied if the unoccupied remainder includes at least one of the segments of the page of the pages. In some embodiments, the buffer memory comprises a reference count value for each of the pages, the reference count value indicating how many of the plurality of packets use the page, and further wherein the buffer logic is configured to, once the page of the pages has been allocated to store packet data of the first packet, set the reference count value for the page of the pages to an integer greater than one if the page of the pages is determined to be insufficiently occupied after storing the packet data of the first packet. In some embodiments, the integer greater than one is two. In some embodiments, for each packet of the plurality of packets whose packet data is allocated to the page of pages, the buffer logic is configured to increment a reference count value for a page of pages by one if the page of pages is determined to be insufficiently occupied after storing the packet data for the packet. In some embodiments, for each of the plurality of packets for which packet data is allocated to a page of the pages, the buffer logic is configured to refrain from incrementing the reference count value for the page of the pages by one if the page of the pages is determined to no longer be sufficiently unoccupied after storing the packet data for the packet. In some embodiments, the buffer memory stores state data for each of the pages, wherein the state data for each of the pages includes a separate state value for each of the segments of the page. In some embodiments, the state value for each of the segments comprises one or more of the group consisting of: a used data count value indicating how much of the segment is currently storing data; a packet start value indicating whether a start of one of the packets is stored in the segment; and a packet end value indicating whether an end of one of the packets is stored in the segment. In some embodiments, the buffer logic is configured to generate a descriptor for each of the packets stored on one or more of the pages, wherein the descriptor includes a page indicator indicating on which of the pages the start of the packet is stored and a segment indicator indicating on which of the segments of the indicated pages the start of the packet is stored. In some embodiments, for each of the packets, after storing an end of the packet (e.g., an end of the header or an end of the entire packet) on one of the segments of the page of the pages, the buffer logic reserves one or more of the adjacent subsequent segments of the page as reserved segments, the reserved segments being capable of storing data from the packet only when the size of the data of the packet increases. In some embodiments, upon determining whether the page of the pages is not sufficiently occupied, the buffer logic considers the reserved segment as occupied such that the reserved segment is not part of the remainder of the unoccupied.

A second aspect is directed to a buffer logic unit stored on a non-transitory computer readable buffer memory, wherein the buffer logic is configured to: allocating one of the plurality of pages to store packet data of a first packet of the plurality of packets; and if the page of pages is determined to be not sufficiently occupied by packet data of the first packet, allocating at least a fractional portion of an unoccupied remainder of the page of pages to store packet data of one or more further packets of the plurality of packets such that the page of pages is allocated to two or more packets of the plurality of packets, wherein each page of the plurality of pages comprises a plurality of segments and defines separate portions of a plurality of physical memory units. In some embodiments, each of the pages includes a plurality of segments, and the buffer memory logic determines that a page of the pages is not fully occupied if the unoccupied remainder includes at least one of the segments of the page of the pages. In some embodiments, the buffer memory comprises a reference count value for each of the pages, the reference count value indicating how many of the plurality of packets use the page, and further wherein the buffer logic is configured to, once the page of the pages has been allocated to store packet data of the first packet, set the reference count value for the page of the pages to an integer greater than one if the page of the pages is determined to be insufficiently occupied after storing the packet data of the first packet. In some embodiments, the integer greater than one is two. In some embodiments, for each packet of the plurality of packets whose packet data is allocated to the page of pages, the buffer logic is configured to increment a reference count value for a page of pages by one if the page of pages is determined to be insufficiently occupied after storing the packet data for the packet. In some embodiments, for each of the plurality of packets for which packet data is allocated to a page of the pages, the buffer logic is configured to refrain from incrementing the reference count value for the page of the pages by one if the page of the pages is determined to no longer be sufficiently unoccupied after storing the packet data for the packet. In some embodiments, the buffer memory stores state data for each of the pages, wherein the state data for each of the pages includes a separate state value for each of the segments of the page. In some embodiments, the state value for each of the segments comprises one or more of the group consisting of: a used data count value indicating how much of the segment is currently storing data; a packet start value indicating whether a start of one of the packets is stored in the segment; and a packet end value indicating whether an end of one of the packets is stored in the segment. In some embodiments, the buffer logic is configured to generate a descriptor for each of the packets stored on one or more of the pages, wherein the descriptor includes a page indicator indicating on which of the pages the start of the packet is stored and a segment indicator indicating on which of the segments of the indicated pages the start of the packet is stored. In some embodiments, for each of the packets, after storing an end of the packet on one of the segments of the page in the pages, the buffer logic reserves one or more of the adjacent subsequent segments of the page as reserved segments, the reserved segments capable of storing data from the packet only when a size of the data of the packet increases. In some embodiments, upon determining whether the page of the pages is not sufficiently occupied, the buffer logic considers the reserved segment as occupied such that the reserved segment is not part of the remainder of the unoccupied.

A third aspect is directed to a method of optimizing packet memory space within a packet processing system that includes a non-transitory computer-readable packet memory that includes a plurality of physical memory units that are logically divided into a plurality of pages such that each of the pages defines a separate portion of the physical memory units. The method comprises the following steps: allocating one of the pages to store packet data for a first packet of the plurality of packets with buffer logic, wherein the buffer logic is stored at least in part on a non-transitory computer readable buffer memory; determining, with buffer logic, whether a page of pages is not fully occupied by packet data of the first packet; and if the page of pages is determined by the buffer logic to be insufficiently occupied by packet data of the first packet, allocating at least a portion of the unoccupied remainder of the page of pages with the buffer logic to store packet data of one or more further packets of the plurality of packets such that the page of pages is allocated to two or more packets of the plurality of packets. In some embodiments, each of the pages includes a plurality of segments, and the buffer memory logic determines that a page of the pages is not fully occupied if the unoccupied remainder includes at least one of the segments of the page of the pages. In some embodiments, the buffer memory comprises a reference count value for each of the pages, the reference count value indicating how many of the plurality of packets use the page, and the method further comprises: once the page of pages has been allocated to store packet data of the first packet, the reference count value for the page of pages is set to an integer greater than one if the page of pages is determined to be insufficiently occupied after storing packet data of the first packet. In some embodiments, the integer greater than one is two. In some embodiments, the method further comprises: for each of the plurality of packets whose packet data is allocated to the page of pages, incrementing a reference count value for the page of pages by one using buffer logic if the page of pages is determined to be insufficiently occupied after storing the packet data for the packet. In some embodiments, the method further comprises: for each of the plurality of packets whose packet data is allocated to the one of the pages, refraining from incrementing the reference count value for the one of the pages by one using buffer logic if the one of the pages is determined to no longer be underoccupied after storing the packet data for the one of the packets. In some embodiments, the method further comprises: the state data for each of the pages is stored within a buffer memory using buffer logic, wherein the state data for each of the pages includes a separate state value for each of the segments of the page. In some embodiments, the state value for each of the segments comprises one or more of the group consisting of: a used data count value indicating how much of the segment is currently storing data; a packet start value indicating whether a start of one of the packets is stored in the segment; and a packet end value indicating whether an end of one of the packets is stored in the segment. In some embodiments, the method further comprises: buffer logic is utilized to generate descriptors for each of the packets stored on one or more of the pages, wherein the descriptors include a page indicator indicating on which of the pages a start of the packet is stored and a segment indicator indicating on which of the segments of the indicated pages the start of the packet is stored. In some embodiments, the method further comprises: for each of the packets, after storing an end of the packet on one of the segments of the page in the pages, reserving one or more of the adjacent subsequent segments of the page as reserved segments with buffer logic, the reserved segments capable of storing data from the packet only when a size of the data of the packet increases. In some embodiments, the method further comprises: in determining whether the page of the pages is not sufficiently occupied, the reserved segment is considered occupied with buffer logic such that the reserved segment is not part of the remainder of the unoccupied.

Drawings

Fig. 1 illustrates a packet processing system on a packet processing device according to some embodiments.

FIG. 2 illustrates a buffer manager in accordance with some embodiments.

FIG. 3 illustrates an exemplary page and page status data in accordance with some embodiments.

FIG. 4 illustrates an exemplary page descriptor in accordance with some embodiments.

Fig. 5 illustrates exemplary page state data and descriptor values for two received packets, in accordance with some embodiments.

FIG. 6 illustrates a method of optimizing packet memory space of a packet processing system in accordance with some embodiments.

Detailed Description

In the following description, for purposes of explanation, numerous details are set forth. However, it will be recognized by one skilled in the art that the present invention may be practiced without these specific details. Thus, the present invention is not intended to be limited to the embodiments shown, but is to be accorded the widest scope consistent with the principles and features described herein.

Embodiments are directed to buffer logic of a packet processing device configured to allocate a single page to two or more packets if a current packet stored on the page does not completely fill the page. As a result, the buffer logic can reduce the amount of wasted packet memory space by reducing the amount of unused space on each of the pages. Further, the system provides the following advantages by automatically implementing reserved segmentation (reservdslot) after each packet: is responsible for (accounting for) packet data augmentation during processing. Furthermore, the system provides the following advantages: segment-specific page state data is stored and updated to enable packet data from different packets to be distinguished on the same page. Finally, the system provides the following advantages: the reference count value for each page is set and updated to ensure that the page is not reclaimed before it can be fully allocated to avoid wasting unused space (e.g., fragments).

Fig. 1 illustrates a packet processing system 100 on a packet processing device 99 according to some embodiments. As shown in fig. 1, packet processing system 100 includes a packet memory 102, a buffer memory 104, a read page client 108, and a write page client 110, all operatively coupled together via a network. The packet processing device 99 can be a packet processing circuit and/or a microchip. For example, the device 99 can be a switch microchip (e.g., on top of a rack switch) for a data center, or other type of packet processing circuit or application specific integrated circuit. In some embodiments, the device 99 is a software-defined network programmable microchip that can be programmed or customized to adjust the manner in which packets are processed. Alternatively, the device 99 can be other types of packet processing devices known in the art. Packet memory 102 includes a plurality of non-transitory computer-readable physical memory cells, each having one or more read ports and one or more write ports. When packet data of an incoming packet is stored on the packet memory 102, it is stored on one or more pages that map to one or more of the memory locations of the packet memory 102. As a result, when packet data is stored in a page, rather than all being stored sequentially in the same location in the packet memory 102, the packet data is distributed across multiple physical memory locations of the packet memory to which the page maps. In some embodiments, packet memory 102 comprises a Content Addressable Memory (CAM). Alternatively, the packet memory 102 can include a CAM, a Ternary Content Addressable Memory (TCAM), a Random Access Memory (RAM), a Static Random Access Memory (SRAM), other types of memory known in the art, or a combination thereof.

FIG. 2 illustrates a buffer manager 104 according to some embodiments. As shown in fig. 2, buffer manager 104 includes buffer logic 202, a plurality of buffer memory units 204, one or more page state tables 206, one or more page buffers 208 having one or more pages 212, and one or more page counters 210. Alternatively, the page counter 210 can be omitted. The buffer logic 202 implements the actions of the buffer manager 104, including allocating pages 212 to the write client 110 and reclaiming pages 212 from the read client 108, and implementing corresponding management/updates to the state table 206, page buffer 208, and page counter 210. The buffer logic 202 can include hardware, software, or a combination of hardware and software configured to perform the functions of the buffer manager 104 described herein, wherein the software is stored on a non-transitory computer readable medium (e.g., buffer memory) of the device 99.

Each of the page buffers 208 stores a subset of the pages 212 (or their representations) when they are not allocated. When a page needs to be allocated to store packet data of an incoming packet as requested by write page client 110, buffer manager 104 selects one of pages 212 from one of buffers 208 via buffer logic 202 (because they are unallocated pages 212), removes it from buffer 208 and allocates that page 212 to write page client 110 for storing at least a portion of the packet data of the incoming packet. As shown in FIG. 3A, each of pages 212 includes a plurality of segments 302 (e.g., segment 0-segment n), each of which forms a portion of page 212. If not all segments 302 have been at least partially filled after storing packet data of the incoming packet on page 212, buffer manager 104 can determine that page 212 is not sufficiently full. Thus, the buffer manager 104 can allocate the remaining portion of the page 212 (including one or more of the unused segments 302 of the page 212) to packet data of subsequent incoming packets and repeat this pattern until the page 212 is determined to be sufficiently full. Later, when all read page clients 108 that need to read the packet data of one or more packets stored on the page indicate that the data stored on the page 212 is no longer needed and the page is ready to be reclaimed, the buffer manager 104 adds the page 212 back to the same page buffer 208. Thus, the page buffer 208 can dynamically indicate to the buffer manager 104 all currently unallocated pages (or portions thereof) that can be selected whenever a page is needed. In this manner, pages 212 can be allocated and reclaimed continuously as packet data is input, stored, processed, and output from the device 99 by the buffer manager 104 in cooperation with the write and read clients 108, 110.

Buffer memory units 204 are each non-transitory computer-readable physical memory having one or more read ports and one or more write ports (not shown). As a result, buffer memory units 204 are each capable of independently having data written to and/or read from them at each cycle. The page state tables 206 are each stored on one or more of the buffer memory units 204 and include a plurality of entries for storing page state data 304 for each of the pages 212 as they are assigned to packet data of a packet. As shown in fig. 3B, the state data for each of the pages 212 can include a page identifier 314, a reference count value 316, and a next page identifier 306. Further, for each of the segments 302 of the associated page 212, the state data 302 can include a data count 308 used, a start of packet indicator 310, and an end of packet indicator 312. The page identifier 314 uniquely identifies the page 212 associated with the page state data 304 in order to correlate the page 212 with the stored state data 304. The reference count value 316 indicates when the previously allocated page 212 is no longer in use and can therefore be reclaimed. In particular, the reference count value 316 indicates the number of packets having different packet data stored on the page 212 after the page 212 has been fully allocated by the buffer manager 104, so that when the reference count value 316 is zero, the buffer manager 104 is able to reclaim the page 212 back into the associated buffer 208. For example, if packet data of a first packet is stored on the first two segments 302 of the page 212 and packet data of a second packet is stored on the remaining portion of the segments 302 of the page 212, the reference count value 316 for that page 212 will be equal to two (one for each packet). Thus, only if both packets are no longer using page 212 will value 306 be decremented twice to equal zero and page 212 read for reclamation.

The next page identifier 306 indicates the next page (if any) that stores at least a portion of the remaining packet data that does not fit exactly into the packet on the current page. In other words, if the last segment 302 of a page 212 is filled, but the packet that will fill the last segment 302 still has remaining packet data to be stored, the next page identifier 306 indicates the next page 212 in which the remaining packet data of the packet is at least partially stored. Thus, the sequence of next page identifiers 306 can match the linked list of pages 212 corresponding to the large group. In some embodiments, the next page identifier 306 can be the same value as the page identifier 314 that the next page identifier 306 is identifying. Alternatively, a different identification value can be used. The data count 308 used indicates how much of the segment 302 is occupied by packet data. In some embodiments, the data count 308 used can be the number of bytes currently stored on the segment 302 of the page 212. Alternatively, the data count 308 used can be other units (e.g., kilobytes) or values (e.g., percentages, numbers) that indicate how much of the segment 302 is occupied by packet data. The start of packet indicator 310 indicates whether the packetized data begins within the segment 302 of the page 212. Similarly, the end of packet indicator 312 indicates whether the packetized data ends up within the segment 302 of the page 212. Thus, the segment-specific status data 308, 310, 312 together indicate which segments in the segment 302 of the page 212 and how much of each segment is occupied by packet data of a packet, so that packet data from different packets on the same page 212 can be distinguished. In some embodiments, the page status data 304 can also include errors incurred within the packet data and/or other types of packet/page data known in the art. In some embodiments, the buffer manager 104 includes a separate state table 206 for each of the page buffers 208, such that each table 206 is paired with a different one of the buffers 208.

In operation, each time write page client 110 receives an incoming packet, it requests page 212 from buffer manager 104 to store the packet data for that packet. In response to the request, buffer manager 104 selects a page 212 from one of buffers 208 and allocates to write page client 110 for the packet data of the packet. Upon receiving the allocated page 212, the write page client 110 writes the packet data on the allocated page 212 of the packet memory 102 and writes the page state data 302 (based on the allocated page 212 and the packet) to the corresponding state table 206 for storage using the buffer manager 104. If the packet data is the first packet data assigned to the page 212 (since the page 212 was last recycled) and the buffer manager 104 determines that the page 212 is not sufficiently filled after storing the packet data of this first packet, the buffer manager 104 sets the reference count 316 of the state data 304 of the page 212 to an integer greater than one. For example, buffer manager 104 sets reference count 316 to two. In particular, because page 212 is determined to be insufficiently filled, buffer manager 104 knows that it will need to further allocate one or more of unused segments 302 of page 212 to one or more subsequent packets until page 212 is sufficiently filled. Thus, in anticipation of packet data from at least one subsequent packet being stored on page 212 such that total packet data from at least two different packets is stored on page 212, buffer manager 104 can set reference count 316 to a number greater than one. This "expected" increment to the reference count value 306 provides the following benefits: helping to ensure that the page 212 is not reclaimed until all of the stored packet data has been retrieved (e.g., in the case where the first packet is processed before the remainder of the page 212 has been assigned to a subsequent packet). However, if this is the first packet data allocated to page 212 (since page 212 was last recycled), but the buffer manager 104 determines that page 212 is sufficiently full after storing packet data for this packet, the buffer manager 104 sets the reference count 316 of the status data 304 for the first page 212 to one, since no further packet data will be stored on page 212.

Additionally, if the packet data is not the first packet data assigned to page 212 (since page 212 was last reclaimed) and buffer manager 104 determines that page 212 is not sufficiently filled after storing the packet data of this subsequent packet, buffer manager 104 increments reference count 316 of status data 304 of page 212 by one (e.g., from 2 to 3). In particular, the buffer manager 104 has ensured that the page 212 is not recycled when the reference count 316 for the first packet is incremented, so only incrementing is necessary for subsequent packets that still do not sufficiently fill the page 212. Finally, if the packet data is not the first packet data assigned to the page 212 (since the page 212 was last recycled), but the buffer manager 104 determines that the page 212 is sufficiently full after storing the packet data for this packet, the buffer manager 104 does not change the reference count 316 of the state data 304 for the first page 212. This is because this packet data will be the last packet data stored on the page 212, which has been accounted for in the reference count value 306 (account for) when the reference count value 306 is incremented to an integer greater than one when the first packet data is assigned the page 212, as described above. Thus, the system 100 provides the following benefits: enabling each page 212 to store packet data from multiple packets thereby increasing the efficiency of packet data storage in the packet memory 102. In addition, the system 100 provides the following benefits: ensuring that page 212 is not reclaimed until it has been sufficiently filled would otherwise result in errors and possible packet data loss within system 100.

In some embodiments, the buffer manager 104 determines that the page 212 is not sufficiently filled if a predetermined number (e.g., one) of the segments 302 of the page 212 are not used after storing the packet data. Thus, after one or more segments 302 are allocated to the packet data for each packet, if the predetermined number of segments 302 are still not being used, the buffer manager 104 determines that the page 212 is not sufficiently filled and allocates one or more of the remaining unused segments 302 to subsequent packets. Further, in some embodiments, the buffer manager 104 can consider a predetermined number of fragments 302 following the fragment 302 storing the end of the last packet data stored on the page 212 as being used when determining whether the fragment 302 is used for the purpose of determining whether the page 212 is sufficiently filled. In particular, because packet data sometimes becomes larger during processing within the device 99, the predetermined number of segments 302 after storing the last segment 302 of each packet can be retained, if the packet data needs to be expanded into these retained segments 302 after processing. Thus, when determining whether page 212 is sufficiently filled, buffer manager 104 considers reserved segment 302 as being full or used, and if page 212 is still not sufficiently filled, reserved segment 302 is not allocated to packet data from the next packet. As a result, the system 100 can advantageously provide buffers within the memory 102 in the form of reserved segments 302, which reserved segments 302 enable packet data to be expanded without overwriting any subsequent packet data.

For each of the packets, the buffer manager 104 also generates a page descriptor 400 as shown in fig. 4. Page descriptor 400 includes a group identifier 402, a page identifier 404, and a segment identifier 406. The packet identifier 402 identifies a packet, the page identifier 404 identifies the page 212 storing the start of the packet, and the segment identifier 406 identifies the segment 302 of the identified page 212 storing the start of packet data of the packet (e.g., as indicated by the start of the packet indicator 312). This page descriptor 400 can be sent to the processing engine of the device 99 and/or the read page client 108 for use in processing and/or reading out packet data from the packet memory 102 as needed. In some embodiments, page identifier 404 can be the same as page identifier 314 of state data 304. Alternatively, a different identifier can be used. Meanwhile, when the read page clients 108 are ready to output outgoing packets, they read the page state data 302 associated with these outgoing packets, as indicated by the packet's descriptor 400, which is stored on the buffer manager 104. Based on this page status data 302, the read page client 108 can locate and read some or all of the packet data from the page or pages 212 of the packet memory 102 where the packet data is stored. As a result, the read page client 108 can then output the packet data of the outgoing packet. Each time the read page client 108 indicates that the packet data stored on a page has been read so that it no longer needs to be stored for that packet, the buffer manager 104 decrements the reference count value 316 for the page 212 in the buffer memory. As a result, when the reference count value 316 reaches zero, the buffer manager 104 can reclaim the page 212 back into the associated page buffer 208 as a currently unused page that can be reallocated when needed.

Additionally, it should be noted that the reference count value 316 of the page 212 can also be incremented when one or more packets have a portion of matching packet data stored on the page 212. This can occur, for example, for multicast or broadcast packets, where instead of storing the matching portion of the packet data twice, the reference count value 316 can be incremented by the buffer manager 104 so that the page 212 is not recycled until all packets with matching data and any other data on the page 212 have been processed and the data is no longer needed. Further, it should be noted that when the state of the page 212 storing packet data from a plurality of packets is written for a subsequent packet of the plurality of packets, the values of the used data count 308, the packet start indicator 310, and/or the packet end indicator 312 for a previous segment occupied by packet data of a previous packet of the plurality of packets need not be partially written. This is because all writes of this page state data 302 within table 206 are performed by the same source (e.g., write page client 110) so that subsequent writes can contain the same value that was written in the previous write including any additional content for the new packet data. Thus, the system 100 does not require multiple access (read-modify-write) types to the port of the buffer memory unit 204 that stores the associated state table 206, but rather a single write access. In other words, the system 100 does not require additional reads of the state table.

Fig. 5 illustrates exemplary page state data and descriptor values for two received packets, in accordance with some embodiments. As shown in fig. 5, packet a is first received and stored in the first segment 0 of page P, and the next two segments 302 are reserved segments for possible packet data growth. As a result, the descriptor for packet a has a page identifier 404 that points to page P, and a page segment value that points to segment 0, which stores the beginning of the packet data for packet a. Further, within the state data 304 of page P, the used data count of segment 0 is set to 60 bytes, and segments 1 and 2 are set to 0 bytes to reflect how much of segments 0, 1, and 2 are filled by packet a, and both the packet start indicator and the packet end indicator of segment 0 are set to 1 to indicate that packet a begins and ends in segment 0 of page P. Then, because segment 3 is not used by packet a, buffer manager 104 can determine that page P is not sufficiently filled and set reference count value 316 to an integer greater than one (e.g., two) to reflect the need for further packet data to be stored on page P. Then, when packet B requests page 212, buffer manager 104 can begin by assigning unused segment 3 of page P to packet B. As a result, the descriptor for packet B has a page identifier 404 that points to page P, and a page segment value that points to segment 3, which stores the beginning of the packet data for packet B. Further, within the state data 304 of page P, the used data count of segment 3 is set to 64 bytes to reflect how much of segment 3 is filled by packet B, and the packet start indicator of segment 3 is set to 1 to indicate that packet B begins in segment 3 of page P. Page P can then be determined to be sufficiently full so that the buffer manager 104 does not increment the reference count value 316 for page P (since no more packet data can be stored on page P). Furthermore, because more packet data for packet B still needs to be stored, buffer manager 104 can allocate a new page Q to store more data for packet B and, at the same time, set the next page identifier 306 for page P to identify page Q as the selected next page 212. Then, similar to in page P, the remainder of packet data for packet B is stored in page Q, the associated page state data 304 is added to the page Q entry within the associated state table 206, and the reference count value 316 is merely incremented to 1 to reflect that page Q (including the reserved segment) is sufficiently filled by the remainder of packet data for packet B. Thus, the system 100 can both take charge of packet data expansion with reserved segments and assign a single page to different/non-matching packet data from multiple different packets.

FIG. 6 illustrates a method of optimizing packet memory space within packet processing system 100 in accordance with some embodiments. As shown in fig. 6, at step 602, the buffer manager 104 allocates one of the pages 212 (via the buffer logic 202) to store packet data of the first packet. At step 604, the buffer manager 104 determines whether the page of pages 212 is not sufficiently occupied by packet data of the first packet. In some embodiments, buffer manager 104 determines that a page of pages 212 is not fully occupied if the unoccupied remaining portion includes at least one of segments 302 of the page of pages 212. At step 606, if the page 212 is determined by the buffer manager 104 to be insufficiently occupied by packet data, the buffer manager 104 allocates at least a portion of the unoccupied remainder (e.g., segment 302) of the page 212 to store packet data of one or more additional packets. Thus, the method provides the following advantages: enabling a single page to be assigned to different packet data of a plurality of different packets.

In some embodiments, the method further comprises: once the page of pages 212 has been assigned to store packet data for the first packet, the reference count value 316 for the page of pages is set to an integer greater than one (e.g., two) using buffer manager 104 if the page of pages is determined to be insufficiently occupied after storing packet data for the first packet. In some embodiments, the method further comprises: for each packet of the plurality of packets whose packet data is assigned to the page of pages 212, if a page 212 is determined to be insufficiently occupied after storing the packet data of the packet, then the reference count value 316 for that page of pages 212 is incremented by one. In some embodiments, the method further comprises: for each packet of the plurality of packets whose packet data is assigned to the page of pages 212, refraining from incrementing the reference count value 316 for the page of pages by one if the page 212 is determined, after storing the packet data for the packet, to no longer be insufficiently occupied. In some embodiments, the method further comprises: the state data 304 for each of the pages 212 is stored in the buffer memory 204. In some embodiments, the method further comprises: a descriptor 400 is generated for each of the groupings, where the descriptor 400 includes a page indicator 404 and a segment indicator 406. In some embodiments, the method further comprises: for each packet, after storing the end of the packet on one of the segments 302 of the page 212, one or more of the adjacent subsequent segments 302 of the page 212 are reserved as reserved segments 302, the reserved segments 302 being used to store data from the packet if the size of the data of the packet increases. In some embodiments, the method further comprises: in determining whether the page of pages 212 is not sufficiently occupied, the reserved segment 302 is considered occupied such that the reserved segment 302 is not part of the remainder of the unoccupied. Alternatively, in some embodiments, one or more of the above steps can be omitted.

The packet processing system described herein has many advantages. In particular, the system provides the following advantages: packet memory space is optimized by assigning a single page to different/non-matching packet data from a plurality of different packets, thereby not wasting unused portions of each page. Further, the system provides the following advantages: packet data augmentation during processing is taken care of by automatically implementing reserved segments after each packet. Furthermore, the system provides the following advantages: the segment-specific page state data is stored and updated so that packet data from different packets can be distinguished on the same page. Finally, the system provides the following advantages: the reference count value for each page is set and updated to ensure that the page is not reclaimed before it can be fully allocated so as not to waste unused space (e.g., fragments).

Although the present invention has been described with reference to numerous specific details, one skilled in the art will recognize that the present invention can be embodied in other specific forms without departing from the spirit of the invention. For example, although the various methods and operations described herein describe a particular order of steps, other orders are contemplated, as well as omitting one or more of the steps and/or adding one or more new steps. Further, although the above-described methods and operations are described separately herein, one or more of the methods and operations can be combined (in whole or in part). Accordingly, it will be understood by those skilled in the art that the present invention is not limited by the foregoing illustrative details, but is defined by the appended claims.

Claims (33)

1. A packet processing system on a packet processing device, the system comprising:

a non-transitory computer-readable banked memory comprising a plurality of physical memory cells logically divided into a plurality of pages such that each of the pages defines a separate portion of the physical memory cells; and

buffer logic at least partially stored on a non-transitory computer readable buffer memory, wherein the buffer logic is configured to:

allocating one of the pages to store packet data of a first packet of a plurality of packets; and

if the one of the pages is determined to be insufficiently occupied by packet data of the first packet, at least a fraction of an unoccupied remaining portion of the one of the pages is allocated to store packet data of one or more further packets of the plurality of packets, such that the one of the pages is allocated to two or more packets of the plurality of packets.

2. The system of claim 1, wherein each of the pages comprises a plurality of segments, and buffer memory logic determines that the one of the pages is not fully occupied if the unoccupied remainder comprises at least one of the segments of the one of the pages.

3. The system of claim 2, wherein the buffer memory includes a reference count value for each of the pages, the reference count value indicating how many of the plurality of packets use the page, and further wherein the buffer logic is configured to, once the one of the pages has been allocated to store packet data for the first packet, set the reference count value for the one of the pages to an integer greater than one if the one of the pages is determined to be insufficiently occupied after storing the packet data for the first packet.

4. The system of claim 3, wherein the integer greater than one is two.

5. The system of claim 4, wherein for each packet of the plurality of packets whose packet data is allocated to the one of the pages, the buffer logic is configured to increment the reference count value of the one of the pages by one if the one of the pages is determined to be insufficiently occupied after storing the packet data of the packet.

6. The system of claim 5, wherein for each packet of the plurality of packets whose packet data is allocated to the one of the pages, the buffer logic is configured to refrain from incrementing the reference count value for the one of the pages by one if the one of the pages is determined to no longer be insufficiently occupied after storing the packet data for the packet.

7. The system of claim 6, wherein the buffer memory stores state data for each of the pages, wherein the state data for each of the pages comprises a separate state value for each of the segments of the page.

8. The system of claim 7, wherein the state value for each of the segments comprises one or more of the group consisting of: a used data count value indicating how much of the segment is currently storing data; a packet start value indicating whether a start of one of the packets is stored in the segment; and a packet end value indicating whether an end of one of the packets is stored in the segment.

9. The system of claim 8, wherein the buffer logic is configured to generate a descriptor for each of the packets stored on one or more of the pages, wherein the descriptor includes a page indicator indicating on which of the pages a start of the packet is stored and a segment indicator indicating on which of the indicated segments of pages the start of the packet is stored.

10. The system of claim 9, wherein for each of the packets, after storing an end of the packet on one of the segments of a page of the pages, the buffer logic reserves one or more of the adjacent subsequent segments of the page as reserved segments that are only capable of storing data from the packet when a size of the data of the packet increases.

11. The system of claim 10, wherein in determining whether the one of the pages is not fully occupied, the buffer logic considers the reserved segment as occupied such that the reserved segment is not part of the unoccupied remainder.

12. A buffer logic unit stored on a non-transitory computer readable buffer memory, wherein the buffer logic is configured to: allocating one of the plurality of pages to store packet data of a first packet of the plurality of packets; and if said one of said pages is determined to be insufficiently occupied by packet data of said first packet, allocating at least a fractional portion of an unoccupied remainder of said one of said pages to store packet data of one or more further packets of said plurality of packets such that said one of said pages is allocated to two or more packets of said plurality of packets, wherein each of said plurality of pages comprises a plurality of segments and defines separate portions of a plurality of physical memory units.

13. The buffer logic of claim 12, wherein each of the pages comprises a plurality of segments, and the buffer memory logic determines that the one of the pages is not fully occupied if the unoccupied remainder comprises at least one of the segments of the one of the pages.

14. The buffer logic of claim 13, wherein the buffer memory includes a reference count value for each of the pages, the reference count value indicating how many of the plurality of packets use the page, and further wherein the buffer logic is configured to, once the one of the pages has been allocated to store packet data for the first packet, set the reference count value for the one of the pages to an integer greater than one if the one of the pages is determined to be insufficiently occupied after storing packet data for the first packet.

15. The buffer logic of claim 14, wherein the integer greater than one is two.

16. The buffer logic unit of claim 15, wherein for each packet of the plurality of packets whose packet data is allocated to the one of the pages, the buffer logic is configured to increment the reference count value of the one of the pages by one if the one of the pages is determined to be insufficiently occupied after storing packet data of the packet.

17. The buffer logic unit of claim 16, wherein for each of the plurality of packets whose packet data is allocated to the one of the pages, the buffer logic is configured to refrain from incrementing the reference count value for the one of the pages by one if the one of the pages is determined to no longer be underoccupied after storing packet data for the packet.

18. The buffer logic of claim 17, wherein the buffer memory stores state data for each of the pages, wherein the state data for each of the pages comprises a separate state value for each of the segments of the pages.

19. The buffer logic of claim 18, wherein the state value for each of the segments comprises one or more of the group consisting of: a used data count value indicating how much of the segment is currently storing data; a packet start value indicating whether a start of one of the packets is stored in the segment; and a packet end value indicating whether an end of one of the packets is stored in the segment.

20. The buffer logic of claim 19, wherein the buffer logic is configured to generate a descriptor for each of the packets stored on one or more of the pages, wherein the descriptor includes a page indicator indicating on which of the pages the start of the packet is stored and a segment indicator indicating on which of the indicated segments of pages the start of the packet is stored.

21. The buffer logic of claim 20, wherein for each of the packets, after storing an end of the packet on one of the segments of a page of the pages, the buffer logic reserves one or more of the adjacent subsequent segments of the page as reserved segments that are only capable of storing data from the packet when a size of the data of the packet increases.

22. The buffer logic of claim 21, wherein in determining whether the one of the pages is not fully occupied, the buffer logic considers the reserved segment as occupied such that the reserved segment is not part of the unoccupied remainder.

23. A method of optimizing packet memory space within a packet processing system, the packet processing system including a non-transitory computer-readable packet memory, the non-transitory computer-readable packet memory including a plurality of physical memory units logically divided into a plurality of pages such that each of the pages defines a separate portion of the physical memory units, the method comprising:

allocating one of the pages to store packet data for a first packet of a plurality of packets with buffer logic, wherein the buffer logic is stored at least in part on a non-transitory computer readable buffer memory;

determining, with the buffer logic, whether the one of the pages is not fully occupied by packet data of the first packet; and

if the one of the pages is determined by the buffer logic to be insufficiently occupied by the packet data of the first packet, allocating at least a portion of an unoccupied remainder of the one of the pages with the buffer logic to store packet data of one or more additional packets of the plurality of packets such that the one of the pages is allocated to two or more packets of the plurality of packets.

24. The method of claim 23, wherein each of the pages comprises a plurality of segments, and buffer memory logic determines that the one of the pages is not fully occupied if the unoccupied remainder comprises at least one of the segments of the one of the pages.

25. The method of claim 24, wherein the buffer memory includes a reference count value for each of the pages, the reference count value indicating how many of the plurality of packets use the page, the method further comprising: once the one of the pages has been allocated to store packet data for the first packet, setting the reference count value for the one of the pages to an integer greater than one using the buffer logic if the one of the pages is determined to be insufficiently occupied after storing packet data for the first packet.

26. The method of claim 25, wherein the integer greater than one is two.

27. The method of claim 26, further comprising: for each of the plurality of packets whose packet data is allocated to the one of the pages, incrementing the reference count value for the one of the pages by one using the buffer logic if the one of the pages is determined to be insufficiently occupied after storing the packet data for the packet.

28. The method of claim 27, further comprising: for each of the plurality of packets whose packet data is allocated to the one of the pages, refraining from incrementing the reference count value for the one of the pages by one using the buffer logic if the one of the pages is determined to no longer be underoccupied after storing the packet data for the packet.

29. The method of claim 28, further comprising: storing, with the buffer logic, state data for each of the pages within the buffer memory, wherein the state data for each of the pages includes a separate state value for each of the segments of the page.

30. The method of claim 29, wherein the state value for each of the segments comprises one or more of the group consisting of: a used data count value indicating how much of the segment is currently storing data; a packet start value indicating whether a start of one of the packets is stored in the segment; and a packet end value indicating whether an end of one of the packets is stored in the segment.

31. The method of claim 30, further comprising: generating, with the buffer logic, a descriptor for each of the packets stored on one or more of the pages, wherein the descriptor includes a page indicator indicating on which of the pages a start of the packet is stored and a segment indicator indicating on which of the segments of the indicated pages the start of the packet is stored.

32. The method of claim 31, further comprising: for each of the packets, after storing an end of the packet on one of the segments of a page in the page, reserving one or more of the adjacent subsequent segments of the page as reserved segments that can only store data from the packet with the buffer logic when the size of the data of the packet increases.

33. The method of claim 32, further comprising: in determining whether the one of the pages is not fully occupied, considering the reserved segment as occupied with the buffer logic such that the reserved segment is not part of the unoccupied remainder.