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

Description

Packet processing system, method and apparatus for optimizing packet buffer space

Technical Field

The present invention relates to a packet processing system and more particularly to optimizing packet buffer space in a packet processing system.

Background Art

Packet processing devices (such as switch microchips) often need to buffer packets in a packet memory (PM) having one or more banks as the device processes them. A current solution for storing 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, packets are not stored contiguously in the packet memory's banks, but rather are spread across one or more pages, which together form a linked list of pages that are mapped across the multiple banks of the packet memory. Furthermore, multiple of these banks (and the pages mapped to them) can be logically grouped into pools (of banks and associated pages). Therefore, a linked list of all pages used in a packet buffer by a particular packet needs to be maintained in the switch (in the buffer manager or BM); this linked list is traversed as packets are read from the packet buffer for transmission. Each page is associated with a state that contains some information about the page. The state of all pages in the packet processing device is maintained in the switch. A packet is associated with a descriptor or token that contains, among other fields, a pointer to the first page. Using this starting pointer, all pages used by the packet can be retrieved in the same order they were used to store the incoming packet by traversing a linked list constructed using next page pointers for different page states. As a result, a linked list of all pages (and therefore, banks) used by a particular packet is maintained in the switch and can then be traversed to locate and read packets from the packet memory for transmission.

In these page-based packet processing devices, there is a trade-off 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 therefore the less pressure is placed on the buffer manager's bandwidth. However, larger page sizes mean that a larger portion of the packet memory may be wasted or unused, as packets that do not fill an entire page will leave the remainder of the page unused. On the other hand, smaller page sizes mean that on average less packet memory is wasted or unused, but greater pressure is placed on the buffer manager due to the increased number of accesses required to read and write each packet to the smaller page.

Additionally, in some packet processing devices, if two or more packets have portions of matching packet data (e.g., header or body portions), the packets can share one or more pages storing the matching portions of the packet data, 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, indicating the number of pages that share the page and from which packet data has not yet been read. For example, when the device determines that more packets need to use a page (e.g., more packets have portions that match the portion of data stored on the page), the device can increment the reference count value to account for the additional 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 is no longer needed for these 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.

Summary of the 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 unit 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 includes: a non-transitory computer-readable packet memory comprising a plurality of physical memory cells, the plurality of physical memory cells being logically divided into a plurality of pages, whereby each of the pages defines a separate portion of the physical memory cells; and buffer logic stored at least in part on a non-transitory computer-readable buffer memory, wherein the buffer logic is configured to: allocate one of the pages to store packet data for a first packet of a plurality of packets; and if the page of the pages is determined to be underfilled with packet data for the first packet, allocate at least a portion of an unoccupied remainder of the page of the pages to store packet data for one or more additional packets of the plurality of packets, such that the page of the 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 the page of the pages is underfilled if the unoccupied remainder includes at least one of the segments of the page of the pages. In some embodiments, 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 page of the pages has been allocated to store packet data of a first packet, set the reference count value of the page of the pages to an integer greater than one if the page of the pages is determined to be underpopulated after storing the packet data of the first packet. In some embodiments, the integer greater than one is two. In some embodiments, for each of the plurality of packets whose packet data is allocated to the page of the pages, the buffer logic is configured to increment the reference count value of the page of the pages by one if the page of the pages is determined to be underpopulated after storing the packet data of the packet. In some embodiments, for each of the plurality of packets whose packet data is allocated to the page of the pages, the buffer logic is configured to refrain from incrementing the reference count value of the page of the pages by one if the page of the pages is determined to no longer be underpopulated after storing the packet data of the packet. In some embodiments, the buffer memory stores status data for each of the pages, wherein the status data for each of the pages includes a separate status value for each of the segments of the page. In some embodiments, the status value for each of the segments includes one or more of the following: a used data count value indicating how much of the segment is currently storing data; a packet start value indicating whether the start of one of the packets is stored in the segment; and a packet end value indicating whether the 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 page of the page the start of the packet is stored, and a segment indicator indicating on which segment of the segment of the indicated page 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 a header or an end of the entire packet) on one of the segments of the page in the pages, the buffer logic reserves one or more segments of the adjacent subsequent segments of the page as reserved segments, the reserved segments being capable of storing data from the packet only as the size of the data of the packet increases. In some embodiments, when determining whether the page in the pages is not substantially occupied, the buffer logic considers the reserved segments as occupied such that the reserved segments are not part of the unoccupied remainder.

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: allocate a page of a plurality of pages to store packet data of a first group of a plurality of groups; and if the page of the pages is determined to be underfilled with the packet data of the first group, allocate at least a portion of an unoccupied remainder of the page of the pages to store packet data of one or more additional groups of the plurality of groups, such that the page of the pages is allocated to two or more groups of the plurality of groups, wherein each page of the plurality of pages includes a plurality of segments and defines separate portions of a plurality of physical memory cells. In some embodiments, each of the pages includes a plurality of segments, and the buffer memory logic determines that the page of the pages is underfilled if the unoccupied remainder includes at least one of the segments of the page of the pages. In some embodiments, 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 page of the pages has been allocated to store packet data of a first packet, set the reference count value of the page of the pages to an integer greater than one if the page of the pages is determined to be underpopulated after storing the packet data of the first packet. In some embodiments, the integer greater than one is two. In some embodiments, for each of the plurality of packets whose packet data is allocated to the page of the pages, the buffer logic is configured to increment the reference count value of the page of the pages by one if the page of the pages is determined to be underpopulated after storing the packet data of the packet. In some embodiments, for each of the plurality of packets whose packet data is allocated to the page of the pages, the buffer logic is configured to refrain from incrementing the reference count value of the page of the pages by one if the page of the pages is determined to no longer be underpopulated after storing the packet data of the packet. In some embodiments, the buffer memory stores status data for each of the pages, wherein the status data for each of the pages includes a separate status value for each of the segments of the page. In some embodiments, the status value for each of the segments includes one or more of the following: a used data count value indicating how much of the segment is currently storing data; a packet start value indicating whether the start of one of the packets is stored in the segment; and a packet end value indicating whether the 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 page of the page the start of the packet is stored, and a segment indicator indicating on which segment of the segment of the indicated page the start of the packet is stored. In some embodiments, for each of the packets, after storing the end of the packet on one of the segments of the page in the pages, the buffer logic reserves one or more segments of the adjacent subsequent segments of the page as reserved segments, the reserved segments capable of storing data from the packet only as the size of the data of the packet increases. In some embodiments, when determining whether the page in the pages is not substantially occupied, the buffer logic considers the reserved segments as occupied such that the reserved segments are not part of the unoccupied remainder.

A third aspect is directed to a method for optimizing packet memory space within a packet processing system, the packet processing system comprising a non-transitory computer-readable packet memory, the non-transitory computer-readable packet memory comprising a plurality of physical memory cells, the plurality of physical memory cells being logically divided into a plurality of pages, such that each of the pages defines a separate portion of the physical memory cells. The method comprises: allocating, using buffer logic, one of the pages to store packet data for a first packet of a plurality of packets, wherein the buffer logic is at least partially stored on the non-transitory computer-readable buffer memory; determining, using the buffer logic, whether the page of the pages is under-occupied by the packet data for the first packet; and, if the page of the pages is determined by the buffer logic to be under-occupied by the packet data for the first packet, allocating, using the buffer logic, at least a portion of an unoccupied remainder of the page of the pages to store packet data for one or more additional packets of the plurality of packets, such that the page of the pages is allocated to two or more packets of the plurality of packets. In some embodiments, each of the pages comprises a plurality of segments, and the buffer memory logic determines that the page of the pages is under-occupied if the unoccupied remainder comprises at least one of the segments of the page of the pages. In some embodiments, 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 the method further includes: once the page of the pages has been allocated to store packet data of the first packet, if the page of the pages is determined to be underpopulated after storing the packet data of the first packet, setting the reference count value for the page of the pages to an integer greater than one. In some embodiments, the integer greater than one is two. In some embodiments, the method further includes: for each of the plurality of packets whose packet data is allocated to the page of the pages, if the page of the pages is determined to be underpopulated after storing the packet data of the packet, incrementing the reference count value for the page of the pages by one using the buffer logic. In some embodiments, the method further includes: for each of the plurality of packets whose packet data is allocated to the page of the pages, if the page of the pages is determined to be no longer underpopulated after storing the packet data of the packet, avoiding incrementing the reference count value for the page of the pages by one using the buffer logic. In some embodiments, the method further includes: storing, using buffer logic, status data for each of the pages in the buffer memory, wherein the status data for each of the pages includes a separate status value for each of the segments of the page. In some embodiments, the status value for each of the segments includes one or more of the following: a used data count value indicating how much of the segment is currently storing data; a packet start value indicating whether the start of one of the packets is stored in the segment; and a packet end value indicating whether the end of one of the packets is stored in the segment. In some embodiments, the method further includes: generating, using buffer logic, a descriptor for each of the packets stored on one or more of the pages, wherein the descriptor includes a page indicator and a segment indicator, the page indicator indicating on which page of the page the start of the packet is stored, and the segment indicator indicating on which segment of the segment of the indicated page the start of the packet is stored. In some embodiments, the method further includes, for each of the packets, after storing the end of the packet on one of the segments of the page in the pages, retaining, using the buffer logic, one or more segments of the adjacent subsequent segments of the page as reserved segments, the reserved segments capable of storing data from the packet only as the size of the data of the packet increases. In some embodiments, the method further includes, when determining whether the page in the pages is not sufficiently occupied, considering, using the buffer logic, the reserved segments as occupied such that the reserved segments are not part of the unoccupied remainder.

BRIEF DESCRIPTION OF THE DRAWINGS

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

FIG2 illustrates a buffer manager according to some embodiments.

FIG3 illustrates exemplary pages and page state data according to some embodiments.

FIG4 illustrates an exemplary page descriptor according to some embodiments.

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

FIG6 illustrates a method of optimizing packet memory space of a packet processing system according to some embodiments.

DETAILED DESCRIPTION

In the following description, numerous details are set forth for purposes of explanation. However, those skilled in the art will recognize that the present invention can be practiced without these specific details. Therefore, 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 a buffer logic unit of a packet processing device that is configured to allocate a single page to two or more packets if the current packet stored on the page does not completely fill the page. As a result, the buffer logic unit is able to 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 advantage of accounting for packet data expansion during processing by automatically implementing reserved slots after each packet. In addition, the system provides the advantage of storing and updating segment-specific page status data so that packet data from different packets can be distinguished on the same page. Finally, the system provides the advantage of setting and updating a reference count value for each page to ensure that the page is not reclaimed before it can be completely allocated to avoid wasting unused space (e.g., a segment).

FIG1 illustrates a packet processing system 100 on a packet processing device 99 according to some embodiments. As shown in FIG1 , 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 operably coupled together via a network. Packet processing device 99 can be a packet processing circuit and/or microchip. For example, device 99 can be a switch microchip used in a data center (e.g., a top of rack switch), or other types of packet processing circuits or application-specific integrated circuits. In some embodiments, device 99 is a software-defined network programmable microchip that can be programmed or customized to adjust how packets are processed. Alternatively, 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 packet memory 102, it is stored in one or more pages that are mapped to one or more memory cells in the memory cells of packet memory 102. As a result, when packet data is stored in pages rather than all sequentially in the same location in packet memory 102, the packet data is distributed across multiple physical memory cells of the packet memory to which the pages are mapped. In some embodiments, packet memory 102 comprises a content addressable memory (CAM). Alternatively, packet memory 102 can comprise 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.

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

Each page buffer in page buffers 208 stores a subset of pages 212 (or representations thereof) when these pages are unallocated. When a page needs to be allocated to store packet data for an incoming packet due to a request by a write page client 110, buffer manager 104, via buffer logic 202, selects one of pages 212 from one of buffers 208 (because it is an unallocated page 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 for the incoming packet. As shown in FIG3A , each of pages 212 includes a plurality of segments 302 (e.g., segment 0-segment n), each of which constitutes a portion of page 212. If, after storing the packet data for the incoming packet on a page 212, not all segments 302 have been at least partially filled, buffer manager 104 can determine that page 212 is not sufficiently full. Thus, the buffer manager 104 can allocate the remaining portion of page 212 (including one or more of the unused segments 302 of page 212) to the packet data of subsequent incoming packets, and repeat this pattern until 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 that page indicate that the data stored on page 212 is no longer needed and that the page is ready to be reclaimed, the buffer manager 104 adds 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 way, pages 212 can be continuously allocated and reclaimed 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.

Each of the buffer memory cells 204 is a non-transitory computer-readable physical memory having one or more read ports and one or more write ports (not shown). As a result, each of the buffer memory cells 204 can independently have data written to and/or read from them during each cycle. Each of the page status tables 206 is stored on one or more of the buffer memory cells 204 and includes a plurality of entries for storing page status data 304 for each of the pages 212 as they are assigned to the packetized data. As shown in FIG. 3B , the status 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 status data 302 can include a used data count 308, a start-of-packet indicator 310, and an end-of-packet indicator 312. Page identifier 314 uniquely identifies page 212 associated with page status data 304, so as to correlate page 212 with the stored status data 304. Reference count value 316 indicates when a previously allocated page 212 is no longer in use and can therefore be reclaimed. Specifically, after page 212 has been fully allocated by buffer manager 104, reference count value 316 indicates the number of packets with different packet data stored on page 212, so that buffer manager 104 can reclaim page 212 back into the associated buffer 208 when reference count value 316 is zero. For example, if packet data for a first packet is stored on the first two segments 302 of page 212, and packet data for a second packet is stored on the remainder of segment 302 of page 212, then reference count value 316 for that page 212 will be equal to two (one for each packet). Therefore, only when both packets are no longer using page 212 will value 306 be decremented twice to zero and page 212 read for reclaiming.

Next page identifier 306 indicates the next page (if any) that stores at least a portion of the remaining packet data for the packet that does not fit completely on the current page. In other words, if the last segment 302 of page 212 is full, but the packet that filled the last segment 302 still has remaining packet data to be stored, next page identifier 306 indicates the next page 212 in which the remaining packet data for that 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 packet. In some embodiments, next page identifier 306 can be the same value as page identifier 314 that next page identifier 306 is identifying. Alternatively, a different identifying value can be used. Used data count 308 indicates how much of segment 302 is occupied by packet data. In some embodiments, used data count 308 can be the number of bytes currently stored in segment 302 of page 212. Alternatively, the data count 308 used can be another unit (e.g., kilobytes) or value (e.g., a percentage, a number) indicating how much of the segment 302 is occupied by packet data. A start-of-packet indicator 310 indicates whether the packet data of the packet begins within the segment 302 of the page 212. Similarly, an end-of-packet indicator 312 indicates whether the packet data of the packet ends within the segment 302 of the page 212. Thus, the segment-specific status data 308, 310, 312 together indicate which segments of the segments 302 of the page 212 and how much of each segment is occupied by the packet data of the packet, thereby enabling packet data from different packets on the same page 212 to be distinguished. In some embodiments, the page status data 304 can also include errors caused 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 status table 206 for each page buffer in the page buffer 208, such that each table 206 is paired with a different one of the buffers 208.

In operation, each time the write page client 110 receives an incoming packet, it requests a page 212 from the buffer manager 104 to store the packet data for the packet. In response to the request, the buffer manager 104 selects a page 212 from one of the buffers 208 and allocates it to the write page client 110 for the packet data for the packet. Upon receiving the allocated page 212, the write page client 110 writes the packet data onto the allocated page 212 of the packet memory 102 and writes the page status data 302 to the corresponding status table 206 for storage using the buffer manager 104 (based on the allocated page 212 and the packet). If the packet data is the first packet data allocated to the page 212 (since the page 212 was last reclaimed) and the buffer manager 104 determines that the page 212 is not sufficiently full after storing the packet data for this first packet, the buffer manager 104 sets the reference count 316 of the status data 304 for the page 212 to an integer greater than one. For example, buffer manager 104 sets reference count 316 to two. Specifically, because page 212 is determined to be insufficiently full, buffer manager 104 knows that it will need to further allocate one or more of the unused segments 302 of page 212 to one or more subsequent packets until page 212 is sufficiently full. 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" incrementing of reference count value 306 provides the benefit of helping to ensure that page 212 is not reclaimed before all stored packet data has been retrieved (e.g., in the event that a first packet is processed before the remainder of 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 reclaimed), but the buffer manager 104 determines that page 212 is sufficiently full after storing this packet of packet data, the buffer manager 104 sets the reference count 316 of the status data 304 of 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 full after storing the packet data for this subsequent packet, buffer manager 104 increments reference count 316 of state data 304 for page 212 by one (e.g., from 2 to 3). Specifically, buffer manager 104 has already ensured that page 212 is not reclaimed when incrementing reference count 316 for the first packet, so incrementing by one is only necessary for subsequent packets that still do not sufficiently fill page 212. Finally, if the packet data is not the first packet data assigned to page 212 (since page 212 was last reclaimed), but buffer manager 104 determines that page 212 is sufficiently full after storing the packet data for this packet, buffer manager 104 does not change reference count 316 of state data 304 for the first page 212. This is because this packet data will be the last packet data stored on page 212, which is accounted for in reference count value 306 when reference count value 306 is incremented to an integer greater than one when the first packet data is allocated page 212, as described above. Thus, system 100 provides the benefit of enabling each page 212 to store packet data from multiple packets, thereby increasing the efficiency of packet data storage in packet memory 102. Additionally, system 100 provides the benefit of ensuring that page 212 is not reclaimed before it is sufficiently full, which would result in errors within system 100 and possible packet data loss.

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

For each of the packets, buffer manager 104 also generates a page descriptor 400, as shown in FIG4 . Page descriptor 400 includes a packet identifier 402, a page identifier 404, and a segment identifier 406. Packet identifier 402 identifies the packet, page identifier 404 identifies the starting page 212 storing the packet, and segment identifier 406 identifies the starting segment 302 of the identified page 212 storing the packet's packet data (e.g., as indicated by the start of packet indicator 312). This page descriptor 400 can be sent to a processing engine and/or a read page client 108 of device 99 for use in processing and/or reading packet data from packet memory 102, as needed. In some embodiments, page identifier 404 can be the same as page identifier 314 of state data 304. Alternatively, different identifiers can be used. At the same time, when the read page clients 108 are ready to output outgoing packets, they read the page status 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 clients 108 are able to 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 clients 108 are then able to output the packet data for the outgoing packets. Each time the read page client 108 indicates that the packet data stored on a page has been read and therefore no longer needs to be stored for that packet, the buffer manager 104 decrements the reference count value 316 for the page 212 within 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 when one or more packets have a portion of matching packet data stored on page 212, the reference count value 316 for page 212 can also be incremented. For example, this can occur 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 buffer manager 104 so that page 212 is not reclaimed until all packets with matching data and any other data on page 212 have been processed and the data is no longer needed. Further, it should be noted that when the state of a page 212 storing packet data from a plurality of packets is written for a subsequent packet of the plurality of packets, it is not necessary to partially write the values of the used data count 308, packet start indicator 310, and/or packet end indicator 312 for the previous segment occupied by packet data of a previous packet of the plurality of packets. This is because all writes to this page state data 302 within table 206 are performed by the same source (e.g., write page client 110), so that the subsequent write can contain the same values written in the previous write, including any additional content for the new packet data. Thus, the system 100 does not require multiple accesses (read-modify-write) types, but rather a single write access to the port of the buffer memory unit 204 storing the associated status table 206. In other words, the system 100 does not require additional reads of the status table.

Figure 5 illustrates exemplary page status data and descriptor values for two received packets according to some embodiments. As shown in Figure 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 pointing to page P, and a page segment value of segment 0 pointing to the beginning of the packet data stored with packet A. Further, within the status data 304 for page P, the used data count for 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 with packet A, and the packet start indicator and packet end indicator for segment 0 are both 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, the buffer manager 104 can determine that page P is not sufficiently full and sets the 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, the buffer manager 104 can begin by allocating the unused segment 3 of page P to packet B. As a result, the descriptor for packet B has a page identifier 404 pointing to page P and a page segment value pointing to segment 3, which is where the packet data for packet B is stored. Further, within the status data 304 for page P, the used data count for segment 3 is set to 64 bytes to reflect how much of segment 3 is filled by packet B, and the packet start indicator for 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 (because no more packet data can be stored on page P). Furthermore, because more packet data for packet B still needs to be stored, the buffer manager 104 can allocate a new page Q to store more data for packet B and simultaneously set the next page identifier 306 of page P to identify page Q as the selected next page 212. The remaining portion of the packet data for packet B is then stored in page Q, similar to page P, the associated page status data 304 is added to the page Q entry within the associated status table 206, and the reference count value 316 is simply incremented to 1 to reflect that page Q (including the reserved segment) is fully filled with the remaining packet data for packet B. Thus, the system 100 can both utilize the reserved segment to account for packet data expansion and allocate a single page to different/non-matching packet data from multiple different packets.

FIG6 illustrates a method for optimizing packet memory space within packet processing system 100 according to some embodiments. As shown in FIG6 , at step 602, buffer manager 104 (via buffer logic 202) allocates one of pages 212 to store packet data for a first packet. At step 604, buffer manager 104 determines whether the page in page 212 is not fully occupied by packet data for the first packet. In some embodiments, buffer manager 104 determines that the page in page 212 is not fully occupied if the unoccupied remaining portion includes at least one of segments 302 of the page in page 212. At step 606, if buffer manager 104 determines that page 212 is not fully occupied by packet data, buffer manager 104 allocates at least a portion of the unoccupied remaining portion (e.g., segment 302) of page 212 to store packet data for one or more additional packets. Thus, this method provides the advantage of enabling a single page to be allocated to different packet data for multiple different packets.

In some embodiments, the method further includes, once the page in pages 212 has been allocated to store the packet data of the first packet, setting, using buffer manager 104, a reference count value 316 for the page in pages to an integer greater than one (e.g., two) if the page in pages is determined to be underpopulated after storing the packet data of the first packet. In some embodiments, the method further includes, for each group in the plurality of groups whose packet data is allocated to the page in pages 212, incrementing the reference count value 316 for the page in pages 212 by one if page 212 is determined to be underpopulated after storing the packet data of the group. In some embodiments, the method further includes, for each group in the plurality of groups whose packet data is allocated to the page in pages 212, refraining from incrementing the reference count value 316 for the page in pages by one if page 212 is determined to no longer be underpopulated after storing the packet data of the group. In some embodiments, the method further includes storing status data 304 for each page in pages 212 within buffer memory 204. In some embodiments, the method further includes generating a descriptor 400 for each of the packets, wherein the descriptor 400 includes a page indicator 404 and a segment indicator 406. In some embodiments, the method further includes, for each packet, after storing the end of the packet in one of the segments 302 of page 212, reserving one or more segments of adjacent subsequent segments 302 of page 212 as reserved segments 302 for storing data from the packet if the size of the data for the packet increases. In some embodiments, the method further includes considering the reserved segments 302 as occupied when determining whether the page in pages 212 is not fully occupied, such that the reserved segments 302 are not part of the unoccupied remainder. Alternatively, in some embodiments, one or more of the above steps can be omitted.

The packet processing system described herein has numerous advantages. In particular, the system provides the advantage of optimizing packet memory space by allocating a single page to different/non-matching packet data from multiple different packets, thereby not wasting unused portions of each page. Further, the system provides the advantage of accounting for packet data expansion during processing by automatically implementing reserved segments after each packet. Additionally, the system provides the advantage of storing and updating segment-specific page status data so that packet data from different packets can be distinguished on the same page. Finally, the system provides the advantage of setting and updating a reference count value for each page to ensure that the page is not reclaimed before it can be fully allocated so as not to waste unused space (e.g., segments).

Although the present invention has been described with reference to many specific details, it will be appreciated by those skilled in the art that, without departing from the spirit of the present invention, the present invention can be embodied in other specific forms. For example, although the different methods and operations described herein describe the steps of a particular order, it is also contemplated that other orders, and one or more steps in the step of omitting and/or adding one or more new steps are contemplated. In addition, although the above methods and operations are described separately herein, one or more methods and operations in the method and operation can be combined (in whole or in part). Therefore, it will be appreciated by those skilled in the art that the present invention will not be limited by the aforementioned illustrative details, but will be limited by the appended claims.

Claims (30)

1. A packet processing system on a packet processing device, the system comprising: A non-transient computer-readable block memory comprising multiple physical memory cells logically divided into multiple pages, such that each page defines a separate portion of the physical memory cell; and Buffer logic, at least partially stored in a non-transient computer-readable buffer memory, wherein the buffer logic is configured to: One page of the page is allocated to store group data of a group of multiple groups, wherein the buffer memory includes a reference count value for each page of the page, the reference count value indicating whether the page is in use; If the page in the page is determined to be underutilized after storing the group data of the group, and the group is the only group currently allocated to the page in the page, then the reference count value of the page in the page is adjusted by a first amount. If a page in the page is determined to be underutilized after storing the group data of the group, and the group is not the only group currently allocated to the page in the page, then the reference count value of the page in the page is adjusted by a second quantity, wherein the first quantity is an integer greater than 1, and the first quantity is greater than the second quantity; and If a page in the page is determined to be not sufficiently occupied by the group data of the group, then at least a portion of the unoccupied remaining portion of the page in the page is allocated to store the group data of one or more other groups in the plurality of groups, such that the page in the page is allocated to two or more groups in the plurality of groups. 2. The system of claim 1, wherein each page in the page comprises a plurality of segments, and if the unoccupied remaining portion comprises at least one segment of the segments of the page in the page, then the buffer memory logic determines that the page in the page is not sufficiently occupied. 3. The system according to claim 1, wherein the first quantity is two. 4. The system of claim 3, wherein for each group of the plurality of groups whose group data is allocated to the one page of the page, the buffer logic is configured to increment the reference count value of the one page of the page by one if the one page of the page is determined to be underutilized after storing the group data of the group. 5. The system of claim 4, wherein for each group of the plurality of groups whose group data is allocated to the one page of the page, the buffer logic is configured to avoid incrementing the reference count value of the one page of the page by one if the one page of the page is determined to no longer be underutilized after storing the group data of the group. 6. The system of claim 5, wherein the buffer memory stores state data for each page in the page, wherein the state data for each page in the page includes a separate state value for each segment in the segments of the page. 7. The system of claim 6, wherein the status value for each segment in the segment includes one or more of the following group, the group including: a data used count value, indicating how much data is currently stored in the segment; a group start value, indicating whether the beginning of a group in the group is stored in the segment; and a group end value, indicating whether the end of a group in the group is stored in the segment. 8. The system of claim 7, wherein the buffer logic is configured to generate a descriptor for each of the groups stored on one or more pages of the page, wherein the descriptor includes a page indicator and a segment indicator, the page indicator indicating on which page the start of the group is stored, and the segment indicator indicating on which segment of the indicated page the start of the group is stored. 9. The system of claim 1, wherein, for each of the groups, after storing the end of the group on a segment of the page in the page, the buffer logic reserves one or more segments of the adjacent subsequent segments of the page as reserved segments, the reserved segments being able to store data from the group only as the size of the data in the group increases. 10. The system of claim 9, wherein when determining whether a page in the page is not sufficiently occupied, the buffer logic considers the reserved segment as occupied such that the reserved segment is not part of the unoccupied remainder. 11. A non-transient computer-readable buffer memory having buffer logic units stored thereon, wherein the buffer logic is configured to: One of multiple pages is allocated to store group data of multiple groups, wherein the buffer memory includes a reference count value for each of the pages, the reference count value indicating whether the page is in use; If the page in the page is determined to be underutilized after storing the group data of the group, and the group is the only group currently allocated to the page in the page, then the reference count value of the page in the page is adjusted by a first amount. If a page in the page is determined to be underutilized after storing the group data of the group, and the group is not the only group currently allocated to the page in the page, then the reference count value of the page in the page is adjusted by a second quantity, wherein the first quantity is an integer greater than 1, and the first quantity is greater than the second quantity; and If a page in the plurality of pages is determined to be not sufficiently occupied by the group data of the group, then at least a portion of the unoccupied remaining portion of the page in the plurality of pages is allocated to store the group data of one or more other groups in the plurality of groups, such that the page in the plurality of pages is allocated to two or more groups in the plurality of groups, wherein each of the plurality of pages includes a plurality of segments and defines separate portions of a plurality of physical memory units. 12. The non-transient computer-readable buffer memory of claim 11, wherein each page in the page comprises a plurality of segments, and the buffer memory logic determines that the page in the page is not sufficiently occupied if the unoccupied remainder includes at least one segment of the segments of the page in the page. 13. The non-transient computer-readable buffer memory of claim 11, wherein the first quantity is two. 14. The non-transient computer-readable buffer memory of claim 13, wherein for each group of the plurality of groups whose group data is allocated to the one page of the page, the buffer logic is configured to increment the reference count value of the one page of the page by one if the one page of the page is determined to be underutilized after storing the group data of the group. 15. The non-transient computer-readable buffer memory of claim 14, wherein for each group of the plurality of groups whose group data is allocated to the one page of the page, the buffer logic is configured to avoid incrementing the reference count value of the one page of the page by one if the one page of the page is determined to no longer be underutilized after storing the group data of the group. 16. The non-transient computer-readable buffer memory of claim 15, wherein the buffer memory stores state data for each page in the page, wherein the state data for each page in the page includes a separate state value for each segment in the segments of the page. 17. The non-transient computer-readable buffer memory of claim 16, wherein the state value for each segment in the segment includes one or more of the following group, the group including: a data used count value, indicating how much data is currently stored in the segment; a group start value, indicating whether the beginning of a group in the group is stored in the segment; and a group end value, indicating whether the end of a group in the group is stored in the segment. 18. The non-transient computer-readable buffer memory of claim 17, wherein the buffer logic is configured to generate a descriptor for each of the packets stored on one or more pages of the page, wherein the descriptor includes a page indicator and a segment indicator, the page indicator indicating on which page the start of the packet is stored, and the segment indicator indicating on which segment of the indicated page the start of the packet is stored. 19. The non-transient computer-readable buffer memory of claim 11, wherein, for each of the groups, after storing the end of the group on a segment of a page in the page, the buffer logic reserves one or more segments of the adjacent subsequent segments of the page as reserved segments, the reserved segments being able to store data from the group only as the size of the data in the group increases. 20. The non-transient computer-readable buffer memory of claim 19, wherein when determining whether a page in the page is not sufficiently occupied, the buffer logic considers the reserved segment as occupied such that the reserved segment is not part of the unoccupied remainder. 21. A method for optimizing packet memory space within a packet processing system, the packet processing system including a non-transient computer-readable packet memory, the non-transient computer-readable packet memory including a plurality of physical memory cells, the plurality of physical memory cells being logically divided into a plurality of pages, such that each page defines a separate portion of the physical memory cell, the method comprising: Buffer logic is used to allocate one page of the page to store group data of a group of multiple groups, wherein the buffer logic is at least partially stored on a non-transient computer-readable buffer memory; The buffer logic is used to determine whether a page in the page is not sufficiently occupied by the group data of the group, wherein the buffer memory includes a reference count value for each page in the page, the reference count value indicating whether the page is in use; If the page in the page is determined to be underutilized after storing the group data of the group, and the group is the only group currently allocated to the page in the page, then the reference count value of the page in the page is adjusted by a first amount. If a page in the page is determined to be underutilized after storing the group data of the group, and the group is not the only group currently allocated to the page in the page, then the reference count value of the page in the page is adjusted by a second quantity, wherein the first quantity is an integer greater than 1, and the first quantity is greater than the second quantity; and If the buffer logic determines that a page in the page is not sufficiently occupied by the group data of the group, then the buffer logic is used to allocate at least a portion of the unoccupied remaining portion of the page in the page to store the group data of one or more other groups in the plurality of groups, so that the page in the page is allocated to two or more groups in the plurality of groups. 22. The method of claim 21, wherein each page in the page comprises a plurality of segments, and if the unoccupied remainder comprises at least one segment of the segments of the page in the page, then the buffer memory logic determines that the page in the page is not sufficiently occupied. 23. The method of claim 21, wherein the first quantity is two. 24. The method of claim 23, further comprising: for each group of the plurality of groups whose group data is allocated to the one page of the page, if the one page of the page is determined to be underutilized after storing the group data of the group, using the buffer logic to increment the reference count value of the one page of the page by one. 25. The method of claim 24, further comprising: for each group of the plurality of groups whose group data is allocated to the one page of the page, if the one page of the page is determined to no longer be underutilized after storing the group data of the group, utilizing the buffer logic to prevent the reference count value of the one page of the page from being incremented by one. 26. The method of claim 25, further comprising: storing state data for each page in the page in the buffer memory using the buffer logic, wherein the state data for each page in the page includes a separate state value for each segment in the segments of the page. 27. The method of claim 26, wherein the status value for each segment in the segment includes one or more of the following group, the group including: a data used count value, indicating how much data is currently stored in the segment; a group start value, indicating whether the beginning of a group in the group is stored in the segment; and a group end value, indicating whether the end of a group in the group is stored in the segment. 28. The method of claim 27, further comprising: using the buffer logic to generate a descriptor for each of the groups stored on one or more pages of the page, wherein the descriptor includes a page indicator and a segment indicator, the page indicator indicating on which page the start of the group is stored, and the segment indicator indicating on which segment of the indicated page the start of the group is stored. 29. The method of claim 21, further comprising: for each of the groups, after storing the end of the group on a segment of a page in the page, reserving one or more segments of the adjacent subsequent segments of the page as reserved segments, the reserved segments being able to utilize the buffer logic to store data from the group only as the size of the data in the group increases. 30. The method of claim 29, further comprising: when determining whether a page in the page is not sufficiently occupied, using the buffer logic to consider the reserved segment as occupied, such that the reserved segment is not part of the unoccupied remaining portion.