Memory cache-line bounce reduction for pointer ring structures

A system includes a memory including a ring buffer having a plurality of slots and at least one processor in communication with the memory. A subset of the plurality of slots are initialized with an initialization value. Additionally, the at least one processor includes a consumer processor and a producer processor. The producer processor is configured to receive a memory entry, identify an available slot in the ring buffer for the memory entry, and store the memory entry in the available slot at an offset in the ring buffer. The initialization value is interpreted as an unavailable slot by the producer processor. The consumer processor is configured to consume the memory entry and invalidate one of the subset of slots in the ring buffer by overwriting the initialization value with an invalid value to transition the one of the subset of slots from an unavailable slot to an available slot.

BACKGROUND

Computer systems may routinely copy memory entries from one memory to a different memory. For example, while forwarding incoming networking traffic to a physical or virtual machine, packets may be received and later copied to another memory location. Processors may execute instructions to read, write, and copy memory entries, such as packet addresses to forward networking traffic to different machines. For example, memory entries may be temporarily stored in ring buffers on a first-in-first-out basis before being copied to the memory associated with a different machine. Specifically, incoming networking traffic may be stored on a ring buffer and later copied to virtual machine memory.

SUMMARY

The present disclosure provides new and innovative systems and methods for memory cache-line bounce reduction for memory rings. In an example, a system includes a memory including a ring buffer having a plurality of slots and at least one processor in communication with the memory. A subset of the plurality of slots are initialized with an initialization value. Additionally, the at least one processor includes a consumer processor and a producer processor. The producer processor is configured to receive a memory entry, identify an available slot in the ring buffer for the memory entry, and store the memory entry in the available slot at an offset in the ring buffer. The initialization value is interpreted as an unavailable slot by the producer processor. The consumer processor is configured to consume the memory entry and invalidate one of the subset of slots in the ring buffer by overwriting the initialization value with an invalid value to transition the one of the subset of slots from an unavailable slot to an available slot.

In an example, a method includes receiving, by a producer processor, a memory entry. Additionally, the producer processor identifies an available slot in a ring buffer having a plurality of slots. A subset of the slots is initialized with an initialization value, and the initialization value is interpreted as an unavailable slot by the producer processor. The producer processor also stores the memory entry in the available slot at an offset in the ring buffer. Additionally, the method includes consuming, by a consumer processor, the memory entry, and invalidating, by the consumer processor, one of the subset of slots in the ring buffer by overwriting the initialization value with an invalid value to transition the one of the subset of slots from an unavailable slot to an available slot.

In an example, a method includes receiving, by a producer processor, a plurality of requests associated with a plurality of respective memory entries. The producer processor stores each of the plurality of requests in a respective slot that contains an invalid value. The producer processor is prevented from storing a request in a slot occupied by a valid value and is prevented from storing a request in a slot occupied by an initialization value. The method also includes processing, by a consumer processor, each of the plurality of requests. Additionally, the consumer processor invalidates one of a plurality of respective slots for each of the plurality of stored requests by first invalidating a first slot initialized with an initialization value for a first stored request of the plurality of stored requests. Each of the plurality of respective slots includes one of an initialization value and a valid value.

DETAILED DESCRIPTION OF EXAMPLE EMBODIMENTS

Techniques are disclosed for memory cache-line bounce reduction for memory ring structures (e.g., pointer rings) when receiving data and processing data. For example, the data may be processed and/or copied from one memory location (e.g., ring buffer) to a different memory. Specifically, the techniques disclosed may be used when receiving network traffic and forwarding incoming network traffic to a virtual machine by a hypervisor, which may include receiving a packet from a network device and copying the packet to virtual machine memory. Specifically, forwarding incoming network traffic to a virtual machine by the hypervisor may involve receiving a packet or request (e.g., disk write requests) from a network interface controller (“NIC”) in hypervisor memory (e.g., producing the packet) and copying the packet (or executing the request to write an address of the packets associated with the requests) to virtual machine memory (e.g., consuming the packet).

The techniques disclosed may be used when receiving disk write requests for incoming or outgoing network traffic, for example when processing or executing disk write requests to transmit network traffic (e.g., network traffic from a cloud computing platform) such as a data packet to or from virtual devices (e.g., a virtual machine). A guest operating system or associated guest driver may receive disk write requests and execute the requests such that a hypervisor can transmit the processed requests (e.g., packets) to/from virtual machines (“VMs”) by copying memory entries from a ring buffer and transmitting the memory entries to virtual machine memory. Virtualization may allow a host machine to run multiple virtual environments, for example using a hypervisor (e.g., Kernel-based Virtual Machine (“KVM”)) on an operating system, such as Red Hat® Enterprise Linux® (“RHEL”). The hypervisor may implement software devices and/or virtual devices. When handling network traffic (e.g., network traffic from a cloud computing platform such as the Red Hat® OpenStack® Platform), hypervisor vendors and operating system (“OS”) vendors often attempt to improve networking speed for hypervisors for use in networking stacks as well as improving performance of the associated virtual and physical devices. An example vendor is Red Hat®, which offers RHEL.

The act of receiving the data (e.g., packets) and copying the data may be executed on the same processor (e.g., central processing unit “CPU”), however, parallelizing the actions on separate processors or separate processor cores may provide significant performance advantages and may potentially double the throughput, for example. However, because the parallel process utilizes two CPUs, the process adds additional overhead as adding and removing packets on one list requires cross-CPU communication through shared memory. Traditionally, a linked list or a producer/consumer ring was used without much added performance as false cache sharing typically outweighed the benefits of parallelism. For example, false cache sharing is a performance-degrading usage pattern resulting from periodically accessing data that one of the CPUs (e.g., a first CPU) will not alter (e.g., unaltered data) and the unaltered data shares a cache block or cache line with data that is altered. Because the unaltered data shares a cache block or cache line with altered data, a caching protocol may force the other CPU (e.g., a second CPU) to reload the whole unit of data even though much of the data remains unchanged or unaltered. Thus, the second CPU bears the caching overhead associated with the reload to maintain shared access of the resource (e.g., linked list or a producer/consumer ring). Specifically, if two processors operate on independent data in the same memory address region storable in a single cache line, the entire cache line may have to be refreshed causing memory stalls in addition to wasting system bandwidth.

Additionally, other approaches such as a typical circular buffer design often creates cache line bounces between the two CPUs or CPU cores (e.g., a first CPU or core associated with a hypervisor and a second CPU or core associated with a guest OS). The processor associated with the guest OS (e.g., producer processor) may increment a pointer to address the next slot, thereby wrapping around at the end of the array. To avoid overruns, before storing the data and marking the data (e.g., the address of each packet and/or packet) as valid, the guest OS may test the value in each slot. If the descriptor value is valid, then unconsumed data (e.g., previously stored data) exists in the slot and the data intended to be stored in the circular buffer is not stored in the list at that time and may be discarded. The processor associated with a hypervisor (e.g., consumer processor), which may be referred to as a data copying processor, may maintain a consumer pointer. The hypervisor may test the value pointed to by the consumer pointer. If the descriptor value has been cleared and is invalid, then the array is empty and the hypervisor may stop and wait for more packet entries marked valid for transmission. If the descriptor value is valid, the hypervisor may retrieve the data, such as a packet address. Then, the hypervisor may clear the valid descriptor and may advance the consumer pointer to the next slot. The retrieved data may be copied to a second memory location (e.g., virtual machine memory).

Clearing a valid descriptor or slot (e.g., overwriting the valid bit or storing a NULL value in a slot) advantageously allows reuse of the slot for additional data (e.g., forwarding a new packet). For example, typically multiple requests fit in a single cache-line and as a requester or producer (e.g., driver) attempts to produce another request while the previous request is overwritten with a NULL value by the consumer (e.g., device), both the producer (e.g., driver) and the consumer (e.g., device) may end up writing into the same cache-line, which causes a cache-line bounce.

Specifically, this data structure may experience performance bottlenecks. For example, when consuming packets is slower than producing packets for transmission or conversely when producing packets is slower than consuming packets. In the first case, the ring may be full for a large part of the time, and as a result, as the hypervisor signals completion of an entry or the producer process produces an entry, the entry is immediately made valid again by the interrupt handling processor (e.g., the consumer processor processes the entry and invalidates a slot to make the slot available), which causes a cache line to bounce between the processors and results in a significant slowdown. Similarly, when the ring is empty for a large part of the time, as the consumer processor makes a slot available (e.g., the slot is immediately accessed by the consumer processor, consumed and signaled as complete by storing a NULL value in the slot). Due to the bottleneck and resulting slowdown, the producer processor and consumer processor may be unable to achieve sufficient separations, resulting in cache line bounces for each data operation in the ring buffer.

As described in the various examples disclosed herein, to reduce the frequency of cache-line bounces and prevent slowdown, the ring configuration may be augmented and initialized with a subset of slots to include initialization values (e.g., INIT values). The ring buffer or memory ring (e.g., pointer ring) may be modified and made larger based on a quantity of outstanding entries “N” (e.g., a typical size of pointer ring) and a quantity of pointers in a cache-line “C”. For example, a ring buffer or memory ring may be allocated with a size of “N+C−1”. In an example, eight pointers may fit in a cache-line resulting in seven extra entries that may be added to a typical ring size. For a ring that is designed to handle16requests or has 16 slots (e.g., “N=16”), the ring size may be augmented by seven slots resulting in a ring size of 23 slots (e.g., 16+8−1=23). In the example illustrated inFIGS.3A and3B, the augmented ring buffer or memory ring300includes seven slots (e.g., slots305A-G) and a typical cache-line may be four slots.

Specifically, the ring is augmented such that the memory area is larger than the area required to hold a maximum number of outstanding requests (e.g., 16). The ring may be initialized with initialization values (e.g., ‘INIT’ values) in the extended or enlarged area. The initialization values are interpreted as an unavailable slot by the producer processor (e.g., the producer processor interprets or perceives an initialization value as an unconsumed valid memory entry). The consumer processor may interpret or perceive the initialization values as a previously consumed value (e.g., a slot that can be invalidated and made for reuse by overwriting the ‘INIT’ value with a NULL value). During request processing, the active requests or newly produced memory entries are stored at an offset, ahead of the slots initialized with the ‘INIT’ values. For example, four 16 byte requests may fit in a 64 byte cache-line. The active requests or newly produced requests may be stored at an offset of at least 48 bytes, and the processed requests (or consumed requests) may be consumed and a previously consumed request or ‘INIT’ value stored at an offset of 0 bytes (e.g., the active requests or newly produced memory entries may be stored at least 3 slots ahead of the processed or consumed requests). Therefore, when a single new request is added to the ring, the next request will be written at an offset of 64 bytes (e.g., 48 bytes+16 bytes), which is in a different cache-line from where the processed requests are written (e.g., where slots are invalidated and NULL values are written in the ring by the consumer processor). Augmenting the ring and initializing the ring with some initialization values creates and maintains a spacing between the consumer processor and the producer processor, which prevents the cache-line from moving or bouncing multiple times in and out of the cache of one or more of the processors or CPUs. Preventing cache-line bouncing advantageously increases performance, especially for low latency applications (e.g., applications that process high volumes of data with minimal delay) by further increasing the throughput or volume of data that can be passed through the system without incurring any additional cache-line bouncing delays, which helps to minimize latency.

FIG.1depicts a high-level component diagram of an example computing system100in accordance with one or more aspects of the present disclosure. The computing system100may include an operating system (e.g., host OS186), one or more virtual machines (VM170A-B), nodes (e.g., nodes110A-B), a consumer processor (e.g., device)124, a producer processor (e.g., driver)128, and memory134including a ring buffer138. Ring buffer138may be a data structure using a single, fixed-size buffer as if it were connected end-to-end (e.g., in a ring). In an example, the ring buffer138may be a first-in-first-out (FIFO) data structure. For example, requests associated with memory entries such as packet addresses may be written into and retrieved from the ring buffer138based on when the request was first produced to the ring buffer138. Additionally, the ring buffer138may have a plurality of slots, which may store memory entries. The slots may be tracked by pointers or indices, or through the use of a counter. In an example, the counter may be configured to track a position of a current slot accessed by the producer processor128, the consumer processor124, or both the producer processor128and consumer processor124. Other methods may be used to prevent either the consumer processor (e.g., device)124or the producer processor (e.g., driver) from over-writing ring entries while the ring is full. For example, the producer processor128may use a counter or a pointer to wrap around the ring buffer138while avoiding over-writing active ring entries while the ring is full (at least until some are processed by the consumer processor124).

Virtual machines170A-B may include a guest OS, guest memory, a virtual CPU (VCPU), virtual memory devices (VMD), and virtual input/output devices (VI/O). For example, virtual machine170A may include guest OS196A, guest memory or virtual machine memory195A, a virtual CPU190A, a virtual memory devices192A, and virtual input/output device194A. Virtual machine memory195A may include one or more memory pages. Similarly, virtual machine170B may include guest OS196B, virtual machine memory195B, a virtual CPU190B, a virtual memory devices192B, and virtual input/output device194B. Virtual machine memory195B may include one or more memory pages.

The computing system100may also include a hypervisor180and host memory184. Hypervisor180may manage host memory184for the host operating system186as well as memory allocated to the virtual machines170A-B and guest operating systems196A-B such as guest memory or virtual machine memory195A-B provided to guest OS196A-B. Host memory184and virtual machine memory195A-B may be divided into a plurality of memory pages that are managed by the hypervisor180. Virtual machine memory195A-B allocated to the guest OS196A-B may be mapped from host memory184such that when a guest application198A-D uses or accesses a memory page of virtual machine memory195A-B, the guest application198A-D is actually using or accessing host memory184.

In an example, a virtual machine170A may execute a guest operating system196A and run applications198A-B which may utilize the underlying VCPU190A, VMD192A, and VI/O device194A. One or more applications198A-B may be running on a virtual machine170A under the respective guest operating system196A. A virtual machine (e.g., VM170A-B, as illustrated inFIG.1) may run on any type of dependent, independent, compatible, and/or incompatible applications on the underlying hardware and OS. In an example, applications (e.g., App198A-B) run on a virtual machine170A may be dependent on the underlying hardware and/or OS186. In another example, applications198A-B run on a virtual machine170A may be independent of the underlying hardware and/or OS186. For example, applications198A-B run on a first virtual machine170A may be dependent on the underlying hardware and/or OS186while applications (e.g., application198C-D) run on a second virtual machine (e.g., VM170B) are independent of the underlying hardware and/or OS186A. Additionally, applications198A-B run on a virtual machine170A may be compatible with the underlying hardware and/or OS186. In an example, applications198A-B run on a virtual machine170A may be incompatible with the underlying hardware and/or OS186. For example, applications198A-B run on one virtual machine170A may be compatible with the underlying hardware and/or OS186A while applications198C-D run on another virtual machine170B are incompatible with the underlying hardware and/or OS186A. In an example, a device may be implemented as a virtual machine (e.g., virtual machine170A-B).

The computer system100may include one or more nodes110A-B. Each node110A-B may in turn include one or more physical processors (e.g., CPU120A-C) communicatively coupled to memory devices (e.g., MD130A-C) and input/output devices (e.g., I/O140A-B). Each node110A-B may be a computer, such as a physical machine and may include a device, such as hardware device. In an example, a hardware device may include a network device (e.g., a network adapter or any other component that connects a computer to a computer network), a peripheral component interconnect (PCI) device, storage devices, disk drives, sound or video adaptors, photo/video cameras, printer devices, keyboards, displays, etc. Virtual machines170A-B may be provisioned on the same host or node (e.g., node110A) or different nodes. For example, VM170A and VM170B may both be provisioned on node110A. Alternatively, VM170A may be provided on node110A while VM170B is provisioned on node110B.

In an example, consumer processor (e.g., device)124and producer processor (e.g., driver)128may be one of the other processor(s) illustrated inFIG.1, such as a CPU (e.g., CPU120A-C) on node110A-B. Similarly, ring buffer138may be stored in a memory device, and may be one of the other memory(s) illustrated inFIG.1, such as MD130A-C on node110A-B. Additionally, consumer processor124and producer processor128may be different cores on the same physical processor. The producer processor128may be configured to receive one or more requests (e.g., memory entries) and store the requests or associated memory entries in the ring buffer138at a first offset (e.g., in the slots initialized with invalid values or NULL values ahead of the slots initialized with initialization values or ‘INIT’ values). In an example, the offset may be a slot that is indicated by a pointer. The producer processor128may receive and produce the next request in the next successive slot after the first produced request. The consumer processor124may be configured to consume and process the requests and invalid a slot for each processed request. The consumer processor124may write the NULL value associated with the processed requests at a second offset in the ring buffer138(e.g., at an offset of ‘0’ at the start of the ring or the first slot initialized with an ‘INIT’ value).

By producing requests (e.g., memory entries) at the first offset and writing processed or consumed memory entries at the second offset, a spacing is created between the producer processor128and the consumer processor124and cache-line bounces are prevented. Specifically, memory operations can be handled by both the producer processor and consumer processor without a cache-line bounce thereby improving performance (e.g., reduced latency and increased throughput).

As used herein, physical processor or processor120A-C,124, and128refers to a device capable of executing instructions encoding arithmetic, logical, and/or I/O operations. In one illustrative example, a processor may follow Von Neumann architectural model and may include an arithmetic logic unit (ALU), a control unit, and a plurality of registers. In a further aspect, a processor may be a single core processor which is typically capable of executing one instruction at a time (or process a single pipeline of instructions), or a multi-core processor which may simultaneously execute multiple instructions. In another aspect, a processor may be implemented as a single integrated circuit, two or more integrated circuits, or may be a component of a multi-chip module (e.g., in which individual microprocessor dies are included in a single integrated circuit package and hence share a single socket). A processor may also be referred to as a central processing unit (CPU).

As discussed herein, a memory device130A-C refers to a volatile or non-volatile memory device, such as RAM, ROM, EEPROM, or any other device capable of storing data. As discussed herein, I/O device140A-B refers to a device capable of providing an interface between one or more processor pins and an external device capable of inputting and/or outputting binary data.

Processors120A-C may be interconnected using a variety of techniques, ranging from a point-to-point processor interconnect, to a system area network, such as an Ethernet-based network. Local connections within each node, including the connections between a processor120A-C and a memory device130A-C may be provided by one or more local buses of suitable architecture, for example, peripheral component interconnect (PCI).

FIGS.2A and2Billustrate block diagrams of example ring buffers200A and200B (generally referred to as ring buffer200). For example,FIG.2Aillustrates a linear buffer implementation of ring buffer200A whileFIG.2Billustrates the “ring” structure of ring buffer200B. It should be appreciated that ring buffers200A-B may be the same actual memory structure illustrated in two different ways. Ring buffers200A-B may in be located in cacheable memory, such as L1 cache if on the same physical processor but on different CPU cores. In another example, the ring buffer200A-B may be on a different level of cache other than L1. Additionally, ring buffers200A-B may include a plurality of slots (e.g., slots210A-N). For example, slots210A-N may correspond to Slot_1to Slot_n respectively. Each slot may include a request or memory entry, such as a data packet, a packet address, or the like. Additionally, slots may be initially empty or may include an invalid value, such as “0”. For example, a slot with a memory address of “0” may be used to indicate an empty slot or invalid slot. Conversely, a valid slot may include a request or memory entry, such as a data packet or a packet address.

FIGS.3A and3Billustrate a block diagram of request processing in an example memory ring (e.g., pointer ring), such as ring buffer138or300A-N (generally referred to herein as shared ring buffer200,300). For example, memory ring300is illustrated as300A-N, which represents different states of memory ring300at different points in time. Memory ring or ring buffer300may include seven slots (e.g., slots305A-G). In an example, each slot may include a memory entry, such as a request ‘R_1’ to ‘R_12’, a non-valid or invalid value or an initialization value. An invalid value may be a zero value or a NULL value and changing a valid value to an invalid value may include changing a valid packet length to an invalid packet length, etc. The initialization value may be a predetermined value that is selected such that the initialization value is recognized by a consumer as non-valid or invalid, but is recognized by the producer as valid. In an example, the initialization value may be “1”, which is typically not recognized as a valid pointer value.

The ring buffer or memory ring300(e.g., pointer ring) may be modified and made larger based on a quantity of outstanding entries “N” and a quantity of pointers in a cache-line “C”. For example, a ring buffer or memory ring300may be allocated with a size of “N+C−1”. In a typical scenario, eight pointers may fit in a cache-line, seven extra entries may be added to a typical ring size. For example, with a cache-line than can accommodate eight pointers or eight slots of the ring (e.g., “C=8), and a ring buffer or memory ring300that is typically designed to handle 16 requests (e.g., “N=16”), the ring size may be augmented by seven slots resulting in a ring size of 23 slots (e.g., 16+8−1=23). In the example illustrated inFIGS.3A and3B, the augmented ring buffer or memory ring300includes seven slots (e.g., slots305A-G) and a typical cache-line may be four slots.

Requests or memory entries, such as packets (e.g., requests302A-K) may be received by producer processor128. After one or more requests are received, the producer processor128may start producing the requests at a later time. In an example, the request may be addresses, such as packet address ‘P_1’ to ‘P_12’. As illustrated in ring buffer300A, which is illustrated with four slots per cache-line, the ring is provided with three additional slots (e.g., slots305A-C), which are initialized with an initialization value and the remaining slots (e.g., slots305D-G) are initialized with an invalid value (e.g., NULL value). At300B, a request302A (e.g., ‘R_1’) is received and is written at the first invalid value slot (e.g., slot305D). For example,305D includes request302A (e.g., ‘R_1’) and the other slots (e.g., slots305A-C) have initialization values (e.g., ‘INIT’ values) and slots305E-G) include an invalid value, such as a NULL value. The request302A (e.g., ‘R_1’, which may be a packet address) may be written into the memory ring or ring buffer300by a producer processor, such as producer processor128. In the illustrated example, a cache-line may occupy four slots or 64 bytes, such that slots305A-C partially occupy a first cache-line and slots305D-G are in a second cache-line (e.g., slots305D-G fully occupy the second cache-line), which are illustrated as being separated by cache-line boundary315. The producer processor128may store request302A (e.g., ‘R_1’) at an offset after the initialization values (e.g., ‘INIT’ values) such that the request ‘R_1’ is written over the first invalid value or NULL value (e.g., at an offset of ‘48’ bytes), which positions the request in slot305D, of the ring buffer300. By initializing the ring buffer300with initialization values (e.g., ‘INIT’ values) and producing the first request (e.g., ‘R_1’) in the first available slot after the initialization values (e.g., in the first ‘NULL’ slot), a spacing310A is advantageously created to reduce cache-line bouncing between the producer processor128and consumer processor124about cache-line315.

For VMs, the producer processor128may be a guest of the VM, which may program the request data ‘R_1’ (e.g., request302A such as a packet address) into the ring buffer300. The ring buffer300may be associated with a virtual device and accessible to the hypervisor180. Similarly for physical systems, the producer processor128may be a device driver, which may program the request data ‘R_1’ (e.g., request302A such as a packet address) into the active ring buffer300. Additionally, the ring buffer may be accessible to a device (e.g., consumer processor124). As the requests are processed by the consumer processor124, other slots are invalidated or overwritten with a NULL value to indicate that a request has been processed. For example, the processed requests (e.g., ‘R_1*’) may later be invalidated or overwritten with NULL values from subsequently consumed requests.

Then, in300C, the producer processor128may receive another request302B (e.g., ‘R_2’) and may write the request in the next successive slot (e.g., slot305E), which is adjacent to the previously produced request ‘R_1’ in slot305D.

The consumer processor128may start looking for new entries at the same offset (e.g., offset of “C−1=3 slots or ‘48’ bytes) because the consumer processor128is recognized by the consumer processor128as a non-valid or invalid value (e.g., NULL) processes requests when a valid value is encountered (e.g., the valid value of ‘R_1’ produced in slot305D). For example, in300D, the consumer processor128may process the request302A (e.g., ‘R_1’) and write an invalid value (e.g., NULL value) at an offset of ‘0’ bytes at the start of the ring buffer300, which positions the invalid value (e.g., NULL value) associated with the processed request302A (e.g., ‘R_1*’) in slot305A in a different cache-line than the slots305D-E for requests ‘R_1’ and ‘R_2’ that were last produced by producer processor128. The spacing310B of three slots that are either ‘INIT’ values or processed requests is maintained, which includes two ‘INIT’ values and the processed request ‘R_1*.’ Each of the slots within the spacing310B are perceived by the producer processor128to be unavailable (e.g., full or occupied). A request (e.g., ‘R_1’) may retain its value as it is processed and written as a processed request (e.g., ‘R_1*’) such that both values of ‘R_1’ and ‘R_1*’ are the same.

For example, slot305A is a full cache-line behind slots305D-E, and thus writing the NULL value in slot305A prevents a cache-line bounce between the producer processor128and the consumer processor124. As indicated inFIGS.3A and3B, after a request has been consumed, the entry is denoted with an asterisk to indicate that the consumer processor124has consumed the request and written an invalid value (e.g., NULL value) into the ring buffer300.

The processed requests may be copied to another location, for example consuming or processing a request may include copying the request (e.g., packet data) to another memory location, such as VM memory195A. For example, the consumer CPU124may retrieve packet address associated with the request and then copy the packet associated with packet address to VM memory195A.

Similarly, the consumer processor124may process the request302B (e.g., ‘R_2’) and write an invalid value (e.g., NULL value) in slot305B, which is the next successive slot, which positions the invalid value (e.g., NULL value) associated with the processed request302B (e.g., ‘R_2*’) in slot305B in a different cache-line than the slots305D-E for requests ‘R_1’ and ‘R_2’ that were last produced by producer processor128. The consumer processor124writes the invalid values (e.g., NULL values) into slots by overwriting valid values or values that are perceived as valid values (e.g., ‘INIT’ values).

The producer processor128may then receive requests302C,302D and302E. Additionally, the producer processor128may produce the request in slots305F,305G and305A respectively. The producer processor128may produce the requests one-by-one or may produce the requests in batches. For example, the producer processor may first produce request302C (e.g., ‘R_3’) in slot305F and then produce request302D (e.g., ‘R_4’) in slot305G, which are a full cache-line ahead of slots305A and305B, and thus prevents a cache-line bounce between the producer processor128and the consumer processor124. Then, the producer processor128may wrap-around and produce request302E (e.g., ‘R_5’) in slot305A. The producer processor128may continue producing requests to the ring buffer300until it reaches a valid entry or an entry the producer processor128perceives as a valid entry (e.g., ‘INIT’ value) thereby maintaining the spacing310C of the three slots.

As illustrated in ring buffer300F, the consumer processor124processes the requests302C and302D (e.g., ‘R_3’ and ‘R_4’) and write invalid values (e.g., NULL values) in slots305C and305D respectively, which are the next successive slots after the previous NULL entry that was written in slot305B. As discussed above, the processed requests are denoted as (‘R_3*’ and ‘R_4*’). Then, at300G, the consumer processor124consumes request302E and overwrites the previously processed request (e.g., ‘R_2*’) in slot305E with a NULL value, as illustrated in300H. At300G, the spacing310D includes slots305E-G, which each include consumed requests ‘R_2*’, ‘R_3*’ and ‘R_4*.’ Since each of the slots305E-G within the spacing310D include requests (e.g., consumed requests), the producer processor128is prevented from producing new requests in these slots until they are later invalidated by the consumer processor124. By maintaining the spacing310D between the consumer processor124and producer processor128, the occurrence of cache-line bounces about cache-line boundary315are advantageously reduced and in some instances entirely prevented.

Continuing onFIG.3B, at3001the producer processor128receives requests302F and302G (e.g., ‘R_6’ and ‘R_7’) and produces the requests in slots305B and305C, which were previously occupied by NULL values. Again, the consumer processor124processes the requests and writes an invalid value (e.g., NULL value) in slots305F and305G by overwriting the previously processed requests ‘R_3*’ and ‘R_4*’. As discussed above, a cache-line may occupy four slots or 64 bytes, such that slots305D-G are in one cache-line and slots305A-C are in a different cache-line. For example, at300J, the entire second cache-line (e.g., slots305D-G) includes NULL values and the first cache-line, which is partially occupied by slots305A-C includes processed requests ‘R_5*’, ‘R_6*’ and ‘R_7*’, which form the spacing310E.

The producer processor128may receive another batch of requests302H-L (e.g., ‘R_8’ through ‘R_12’). As shown in300K, the producer processor produces requests302H-K (e.g., ‘R_8’, ‘R_9’, ‘R_10’ and ‘R_11’) in each of the slots that include a NULL value (e.g., slots305D-G). As discussed above, the producer processor128may continue producing requests to the ring buffer300until it reaches a valid entry or an entry the producer processor128perceives as a valid entry (e.g., ‘INIT’ value). In the illustrated example, slot305A includes a valid entry (e.g., ‘R_5*’) and thus the producer processor128is prevented from producing another entry until the consumer processor124makes progress and overwrites the ‘R_5*’ value with a NULL value. The processed requests ‘R_6*’, ‘R_7*’ and ‘R_8*’ maintain the spacing310F between the consumer processor124and the producer processor128since the producer processor128is prevented from producing additional requests to the ring buffer300until the consumer processor124consumes additional entries.

In an example, the unproduced request302L from the batch may be returned to the user. For example, request302L is shown in a dotted-line at300K since the request is produced at a later time. In the illustrated example, the request302L is held and produced at a later time as request302M.

The consumer processor looks for the newly produced entries (e.g., ‘R_8’ through ‘R_11’) and consumes the entries. For example at300K and300L, request302H (e.g., ‘R_8’) is consumed and the value in slot305A is overwritten with an invalid value (e.g., NULL value). After slot305A becomes available for production, the producer processor128may produce request302M (e.g., ‘R_12’) into the slot as illustrated at300M. Then, the consumer processor124may continue consuming requests and consume request3021, which is indicated by overwriting the value in slot305B (e.g., ‘R_6*’) with a NULL value at300N while the spacing310G is maintained.

As mentioned above, the producer processor128and consumer processor124may store and write processed requests one-by-one or in batches. Since slots305A-C and slots305D-G are in different cache-lines, the consumer processor124and producer processor128may produce and consume requests (in parallel or even simultaneously) without causing a cache-line bounce between the consumer processor124and the producer processor124. Additionally, because the ring buffer300was initialized with three initialization values (e.g., ‘INIT’ values), the ‘INIT’ values create and maintain a spacing between the consumer processor124and producer processor128to prevent cache-line bouncing.

FIG.4Aillustrates a flowchart of an example method400for memory cache-line bounce reduction in a memory ring according to an example of the present disclosure. Although the example method400is described with reference to the flowchart illustrated inFIG.4A, it will be appreciated that many other methods of performing the acts associated with the method400may be used. For example, the order of some of the blocks may be changed, certain blocks may be combined with other blocks, and some of the blocks described are optional. The method400may be performed by processing logic that may comprise hardware (circuitry, dedicated logic, etc.), software, or a combination of both.

The example method400includes receiving a memory entry (block410). For example, a producer processor128may receive a memory entry or a request associated with a memory entry (e.g., a packet). In an example, the memory entry may be a data packet. Then, the method includes identifying an available slot in a ring buffer (block412). For example, the producer processor128may identify an available slot in the ring buffer138(e.g., ring buffer200ofFIGS.2A and2Bor ring buffer300ofFIGS.3A and3B) that has a plurality of slots. In an example, a subset of the slots is initialized with an initialization value (e.g., ‘INIT’ value), which may be interpreted or perceived as an unavailable slot by the producer processor128. The method also includes storing the memory entry in the available slot at an offset (block414). For example, the producer processor128may store the memory entry or request associated with a memory entry in a slot provided at an offset in the ring buffer138. The slot may be an available slot that includes an invalid value, such as a NULL value.

Then, the method includes consuming the memory entry (block416). For example, the memory entry may be consumed (e.g., processed) by a consumer processor124similar to what has been described and illustrated inFIGS.3A and3B. Additionally, method400includes invalidating a slot in the ring buffer by overwriting an initialization value with an invalid value to transition the slot from an unavailable slot to an available slot (block418). For example, the consumer processor124may invalidate one of the subset of slots in the ring buffer138, which was previously initialized with an initialization value (e.g., ‘INIT’ value) by overwriting the ‘INIT’ value with an invalid value to transition the one of the subset of slots from an unavailable slot to an available slot. In an example, the slot initialized with the initialization value may be at a different offset in the ring buffer (e.g., an offset of ‘0’). The slot(s) initialized with initialization values may be predetermined such that the producer processor128and the consumer processor124maintain a spacing while producing and consuming memory entries in the ring buffer to avoid cache-line bounces.

FIG.4Billustrates a flowchart of an example method450for memory cache-line bounce reduction in a memory ring according to an example of the present disclosure. Although the example method450is described with reference to the flowchart illustrated inFIG.4B, it will be appreciated that many other methods of performing the acts associated with the method450may be used. For example, the order of some of the blocks may be changed, certain blocks may be combined with other blocks, and some of the blocks described are optional. The method750may be performed by processing logic that may comprise hardware (circuitry, dedicated logic, etc.), software, or a combination of both.

The example method450includes receiving a plurality of requests associated with a plurality of respective memory entries (block460). Requests may be received individually or received in batches. Then the method includes storing each of the plurality of requests in a respective slot that contains an invalid value (block462). The producer processor128may store the request in the first slot, which may be an intermediate slot in the ring buffer at an offset spaced from the start of the ring buffer (e.g., a slot after the slots initialized with ‘INIT’ values). The method includes processing each of the plurality of requests (block464). For example, a consumer processor124may process each of the requests. Then, the method includes invalidating one of a plurality of respective slots for each of the plurality of stored requests by first invalidating a first slot initialized with an initialization value for a first stored request of the plurality of requests (block466). The ring buffer being augmented and initialized with some slots with initialization values creates a spacing and the spacing may be adapted such that the consumer processor124and the producer processor128can perform memory operations on different cache-lines in parallel or simultaneously, without causing a cache-line bounce.

FIGS.5A,5B and5Cillustrate a flowchart of an example method500for memory cache-line bounce reduction in a pointer memory ring in accordance with an example of the present disclosure. Although the example method500is described with reference to the flowchart illustrated inFIGS.5A,5B and5Cit will be appreciated that many other methods of performing the acts associated with the method500may be used. For example, the order of some of the blocks may be changed, certain blocks may be combined with other blocks, and some of the blocks described are optional. For example, a consumer processor124(e.g., consumer CPU) and a producer processor128(e.g., producer CPU) may communicate with a ring buffer138to perform example method500.

In the illustrated example, the ring138includes six slots (e.g., slot_0to slot_5), where slot_0and slot_1are initialized with initialization values (e.g., ‘INIT’ values) and slot_2, slot_3, slot_4and slot_5are initialized with invalid values, such as NULL values (block502). In an example, each slot may occupy a portion of a cache-line. In the illustrated example, the ring138may occupy an integer number of cache-lines (e.g., two cache-lines). However, the ring138may also occupy a non-integer number cache-lines.

In an example, a memory address of “0” may represent a NULL value and a value of “1” may represent an initialization value. The producer CPU128may receive a batch of packets associated with packet addresses P_0to P_4(block504). For example, the producer CPU128may receive a batch of packets with packet addresses 0x9000:0000, 0x7000:0000, 0x3000:0000, 0x4000:0000 and 0x5000:0000 corresponding to packet addresses P_0to P_4. Then, the producer CPU128may start producing packets (block506). In an example, the producer CPU128may start producing packets (e.g., packet addresses) after receiving the batch301of packets.

To start producing packets, the producer CPU128may identify the slot associated with a producer pointer (block508). For example, the producer CPU128may identify the slot indicated by the producer pointer (e.g., an original slot), which is preferably the next available slot after the last full slot (e.g., a slot that includes a non-NULL memory entry such as the slot after the last ‘INIT’ value slot). For example, if the ring buffer138is typically initialized with initialization values (e.g., ‘INIT’ values) in slot_0and slot_1and NULL values in slot_2to slot_5, then in the illustrated example, the producer pointer would indicate slot_2(e.g., the next available slot after slot_1) such that packets can sequentially be stored in slot_2to slot_5. Then, the producer CPU may test the original slot (e.g., slot_2) (block510). For example, the producer CPU128may test slot_2to determine the value of the memory entry or packet address in the slot. In the illustrated example, the original slot includes a NULL value or “0” value (block512). For example, the producer CPU128may read slot_2while testing the first slot or original slot to determine that the first slot includes a packet address of “0”.

After determining that the original slot includes a NULL value, the producer CPU128may walk to the second slot (e.g., slot_3) (block514). For example, the producer CPU128may advance to the second slot using a walk function. Then, the producer CPU128may test the second slot (e.g., slot_3) (block516). For example, the producer CPU128may test slot_3to determine the value of the memory entry or packet address in the slot. In the illustrated example, the second slot includes a NULL value or “0” value (block518). For example, the producer CPU128may read slot_3while testing the second slot to determine that the second slot includes a packet address of “0”. After determining that the second slot includes a NULL value, the producer CPU128may walk to the third slot (e.g., slot_4) (block520). Similar to above, the producer CPU128may advance to the third slot using a walk function. Then, the producer CPU128may test the third slot (e.g., slot_4) (block522). For example, the producer CPU128may test slot_3to determine the value of the memory entry or packet address in the slot. In the illustrated example, the third slot includes a NULL value or “0” value (block524). For example, the producer CPU128may read slot_4while testing the third slot to determine that the third slot includes a packet address of “0”. After determining that the third slot includes a NULL value, the producer CPU128may walk to the fourth slot (e.g., slot_5) (block526), test the fourth slot (e.g., slot_5) (block528) and determine the value of the memory entry or packet address in the fourth slot is a NULL value or “0” value (block530).

Then, the producer CPU128may walk to the fifth slot (e.g., slot_0) after wrapping around to the start of the ring (block532), test the fifth slot (e.g., slot_0) (block534) and determine the value of the memory entry or packet address in the fifth slot is an ‘INIT’ value (block536). Since there is an inadequate quantity of invalid value slots or empty slots for each packet (e.g., there is not a slot available for the packet associated with packet address P_4) in the batch of packets, the producer CPU128may store a portion of the batch (e.g., packets associated with packet addresses P_0to P_3) in the ring buffer138. In the illustrated example, the producer CPU128stores packet address for P_0to P_3in the ring from the original slot (e.g., slot_2) to the end slot (e.g., slot_5) (blocks538and540). In an example, the producer CPU128may store packet addresses P_0to P_3in the ring buffer138in reverse order while walking the ring138backwards from slot_5(e.g., the end slot) to slot_2(e.g. the original slot). Then, the producer CPU128may advance the producer pointer to the fourth slot (e.g., slot_0) (block544).

In an example, the producer CPU128may wait to advance the producer pointer to slot_0until after the slot is consumed. By maintaining the producer pointer location, the producer CPU128may advantageously store packets or packet addresses in the ring buffer138in sequential order, as they are received in the batches, such that data is consumed by the consumer CPU124sequentially.

Then, the consumer CPU124starts consuming packets (block548). For example, the consumer CPU124retrieves and copies (e.g., consumes) packet data for P_0to VM memory195A (block550). For example, the consumer CPU124may retrieve packet address P_0from slot_2, and then copies the packet associated with packet address P_0to VM memory195A. Additionally, consuming packets may include invalidating slot_2. In an example, the packet data may be copied to VM memory195A from a temporary memory location. Then, the consumer CPU124overwrites the ‘INIT’ value in slot_0with a NULL value (blocks552and554). Now, the ring138has slot_0overwritten with a NULL value (block556). The consumer CPU124also retrieves and copies (e.g., consumes) packet data for P_1to VM memory195A (block558). For example, the consumer CPU124may retrieve packet address P_1from slot_3, and then copies the packet associated with packet address P_1to VM memory195A. Additionally, consuming packets may include invalidating slot_3, and the consumer CPU124may overwrite the ‘INIT’ value in slot_1with a NULL value (blocks560and562). Now, the ring138has slot_1overwritten with a NULL value (block564).

Similarly, the consumer CPU124retrieves and copies packet data for P_2to VM memory195A (block566) and overwrites the P_0* value of slot_2with a NULL value (blocks568and570) such that slot_2in the ring buffer138includes a null value (block572). As discussed above, the ‘*’ indicates that the packet ‘P_0’ has been processed or consumed, which is denoted as ‘P_0*’ inFIG.5B. Also, the consumer CPU124retrieves and copies packet data for ‘P_3’ to VM memory195A (block574) and overwrites the ‘P_1*’ value of slot_3with a NULL value (blocks576and578) such that slot_3in the ring buffer138includes a null value (block580) The consumer CPU124may wait until an entire batch of packets or the maximum quantity of packets from the batch is produced before consuming additional packets to ensure that adequate spacing is maintained between slots accessed by the producer CPU128and the consumer CPU124to help further reduce the frequency of cache line bounces.

Now, the six slots of the ring138have NULL values in slot_0to slot_3, slot_4includes packet address ‘P_2*’ and slot_5includes packet address ‘P_3*’ (e.g., addresses 0x3000:0000 and 0x4000:0000) (block582). The producer CPU128may start producing packets again (block584). For example, the producer CPU128may identify the slot associated with the producer pointer (e.g., slot_0) (block586). Then, the producer CPU128tests slot_0(block588) and determines that slot_0includes a NULL value (block590). After determining that slot_0is available for production, the producer CPU128stores the packet address for ‘P_4’ in the ring buffer138at slot_0(block592and594). Then, the packet address for ‘P_4’ is stored in the ring at slot_0(block596).

Then, the producer CPU128may advance the producer pointer to the fourth slot (e.g., slot_1) (block597). Now, the six slots of the ring138include packet address ‘P_4’ in slot_0, NULL values in slots_1to slot_3, packet address ‘P_2*’ in slot_4and packet address ‘P_3*’ in slot_5(block598). Therefore, the initial offsets chosen of 48 bytes and 0 bytes create a spacing between the slots successively accessed between the consumer CPU124and the producer CPU128to prevent cache-line bouncing. In the illustrated example, memory operations can be handled by both the producer CPU128and consumer CPU124without a cache-line bounce thereby improving performance (e.g., reduce latency and increased throughput). Additionally, the improved performance may be achieved without increasing the ring size by a factor of two, but instead by extending the shared memory region.

FIG.6is a block diagram of an example pointer ring structure production and consumption system600according to an example of the present disclosure. The pointer ring structure production and consumption system600includes a memory610including a ring buffer620having a plurality of slots642A-C and at least one processor650A-B in communication with the memory610. A subset680of the plurality of slots (e.g., slots642A-B) are initialized with an initialization value644A-B. Additionally, the at least one processor650A-B includes a consumer processor650A and a producer processor650B. The producer processor650B is configured to receive a memory entry662, identify an available slot (e.g., slot642C) in the ring buffer620for the memory entry662, and store the memory entry662in the available slot (e.g., slot642C) at an offset690in the ring buffer620. The initialization value6424A-B is interpreted as an unavailable slot (e.g., slots642A-B) by the producer processor650B. The consumer processor650A is configured to consume the memory entry662, and invalidate one of the subset680of slots (e.g., slot642A) in the ring buffer by overwriting the initialization value644A with an invalid value648to transition the one of the subset680of slots (e.g., slot642A) from an unavailable slot to an available slot.

Instead of a cache-line constantly bouncing between the consumer processor650A and the producer processor650B, the memory entry662is produced at the offset690(e.g., ahead of the slots642A-B initialized with the initialization values644A-B), which creates and maintains a spacing. The spacing advantageously allows memory operations such as processing (e.g., producing and consuming) memory entries662without the cache-line bouncing between the consumer processor650A and the producer processor650B, which improves performance (e.g., reduced latency and increased throughput) without substantially increasing the size of the ring buffer620.

Aspects of the subject matter described herein may be useful alone or in combination with one or more other aspects described herein. In a 1st exemplary aspect of the present disclosure, a system includes a memory including a ring buffer having a plurality of slots and at least one processor in communication with the memory. A subset of the plurality of slots are initialized with an initialization value. Additionally, the at least one processor includes a consumer processor and a producer processor. The producer processor is configured to receive a memory entry, identify an available slot in the ring buffer for the memory entry, and store the memory entry in the available slot at an offset in the ring buffer. The initialization value is interpreted as an unavailable slot by the producer processor. The consumer processor is configured to consume the memory entry and invalidate one of the subset of slots in the ring buffer by overwriting the initialization value with an invalid value to transition the one of the subset of slots from an unavailable slot to an available slot.

In a 2nd exemplary aspect of the present disclosure, which may be used in combination with any one or more of the preceding aspects (e.g., the 1st aspect), identifying the available slot includes walking the ring buffer starting from an original slot, wherein the original slot is indicated by a current producer pointer.

In a 3rd exemplary aspect of the present disclosure, which may be used in combination with any one or more of the preceding aspects (e.g., the 2nd aspect), the current producer pointer is an index.

In a 4th exemplary aspect of the present disclosure, which may be used in combination with any one or more of the preceding aspects (e.g., the 1st aspect), the producer processor is further configured to prior to storing the memory entry, walk the ring buffer.

In a 5th exemplary aspect of the present disclosure, which may be used in combination with any one or more of the preceding aspects (e.g., the 1st aspect), identifying the available slot includes testing a respective value associated with a respective memory entry of a slot in the ring buffer. Additionally, the testing is conducted while the contents of each slot remain unchanged.

In a 6th exemplary aspect of the present disclosure, which may be used in combination with any one or more of the preceding aspects (e.g., the 5th aspect), an unavailable slot includes a non-NULL value. Upon receiving a non-NULL value from the test, the producer processor is configured to return an un-stored memory entry.

In a 7th exemplary aspect of the present disclosure, which may be used in combination with any one or more of the preceding aspects (e.g., the 6th aspect), a non-NULL value includes one of a valid memory entry and an initialization value.

In an 8th exemplary aspect of the present disclosure, which may be used in combination with any one or more of the preceding aspects (e.g., the 1st aspect), the consumer processor is configured to retrieve the memory entry and copy the respective memory entry to a second memory.

In a 9th exemplary aspect of the present disclosure, which may be used in combination with any one or more of the preceding aspects (e.g., the 1st aspect), the producer processor is further configured to receive additional memory entries along with the memory entry, which form a batch of memory entries. The batch of memory entries has an initial memory entry and a final memory entry. Additionally, the producer processor is configured to identify a last memory entry in the batch of memory entries such that each of the initial memory entry to the last memory entry form a group that fits in available slots in the ring buffer. The last memory entry and the final memory entry are the same memory entry.

In a 10th exemplary aspect of the present disclosure, which may be used in combination with any one or more of the preceding aspects (e.g., the 9th aspect), the system further includes a batch counter, wherein the batch counter is configured to count memory entries and send the batch of memory entries to the producer processor.

In an 11th exemplary aspect of the present disclosure, which may be used in combination with any one or more of the preceding aspects (e.g., the 1st aspect), the memory entry is a packet address.

In a 12th exemplary aspect of the present disclosure, which may be used in combination with any one or more of the preceding aspects (e.g., the 1st aspect), the invalid value is a NULL value.

In a 13th exemplary aspect of the present disclosure, which may be used in combination with any one or more of the preceding aspects (e.g., the 1st aspect), the consumer processor and the producer processor execute on different cores of the same physical processor.

In a 14th exemplary aspect of the present disclosure, which may be used in combination with any one or more of the preceding aspects (e.g., the 1st aspect), the consumer processor and the producer processor execute on different physical processors.

In a 15th exemplary aspect of the present disclosure, which may be used in combination with any one or more of the preceding aspects (e.g., the 1st aspect), the system further includes a second memory, wherein the second memory is a virtual memory.

In a 16th exemplary aspect of the present disclosure, which may be used in combination with any one or more of the preceding aspects (e.g., the 1st aspect), the ring buffer is an augmented ring that is initialized with a first quantity of additional slots and the subset of the slots has a second quantity. Additionally, the first quantity equals the second quantity.

Aspects of the subject matter described herein may be useful alone or in combination with one or more other aspects described herein. In a 17th exemplary aspect of the present disclosure, a method includes receiving, by a producer processor, a memory entry. Additionally, the producer processor identifies an available slot in a ring buffer having a plurality of slots. A subset of the slots is initialized with an initialization value, and the initialization value is interpreted as an unavailable slot by the producer processor. The producer processor also stores the memory entry in the available slot at an offset in the ring buffer. Additionally, the method includes consuming, by a consumer processor, the memory entry, and invalidating, by the consumer processor, one of the subset of slots in the ring buffer by overwriting the initialization value with an invalid value to transition the one of the subset of slots from an unavailable slot to an available slot.

In an 18th exemplary aspect of the present disclosure, which may be used in combination with any one or more of the preceding aspects (e.g., the 17th aspect), identifying the available slot includes walking, by the producer processor, the ring buffer starting from an original slot, wherein the original slot is indicated by a current producer pointer.

In a 19th exemplary aspect of the present disclosure, which may be used in combination with any one or more of the preceding aspects (e.g., the 18th aspect), the method further includes advancing, by the producer processor, the current producer pointer to the end slot.

In a 20th exemplary aspect of the present disclosure, which may be used in combination with any one or more of the preceding aspects (e.g., the 17th aspect), the method further includes prior to storing the memory entry, walking, by the producer processor, the ring buffer.

In a 21st exemplary aspect of the present disclosure, which may be used in combination with any one or more of the preceding aspects (e.g., the 17th aspect), identifying the available slot includes testing a respective value associated with a respective memory entry of a slot in the ring buffer. The testing is conducted while the contents of each slot remain unchanged.

In a 22nd exemplary aspect of the present disclosure, which may be used in combination with any one or more of the preceding aspects (e.g., the 21st aspect), an unavailable slot includes a non-NULL value. The method further includes upon receiving the non-NULL value from the test, returning, by the producer processor, an un-stored memory entry.

In a 23rd exemplary aspect of the present disclosure, which may be used in combination with any one or more of the preceding aspects (e.g., the 21st aspect), the method further includes responsive to testing an unavailable slot, pausing, by the producer processor, a predetermined timespan before testing the slot again.

In a 24th exemplary aspect of the present disclosure, which may be used in combination with any one or more of the preceding aspects (e.g., the 17th aspect), the method further includes retrieving, by the consumer processor, the memory entry from a first memory and copying the memory entry to a second memory.

In a 25th exemplary aspect of the present disclosure, which may be used in combination with any one or more of the preceding aspects (e.g., the 17th aspect), consuming the memory entry includes retrieving, by the consumer processor, the memory entry from a first memory and copying the memory entry to a second memory.

In a 26th exemplary aspect of the present disclosure, which may be used in combination with any one or more of the preceding aspects (e.g., the 17th aspect), the consumer processor starts processing the memory entry after a batch of memory entries has been stored by the producer processor.

Aspects of the subject matter described herein may be useful alone or in combination with one or more other aspects described herein. In a 27th exemplary aspect of the present disclosure, a non-transitory machine-readable medium storing code, which when executed by a producer processor and a consumer processor, is configured to receive a memory entry and identify an available slot in a ring buffer having a plurality of slots. A subset of the slots is initialized with an initialization value, and the initialization value is interpreted as an unavailable slot by the producer processor. The non-transitory machine-readable medium is also configured to store the memory entry in the available slot at an offset in the ring buffer, consume the memory entry and invalidate one of the subset of slots in the ring buffer by overwriting the initialization value with an invalid value to transition the one of the subset of slots from an unavailable slot to an available slot.

Aspects of the subject matter described herein may be useful alone or in combination with one or more other aspects described herein. In a 28th exemplary aspect of the present disclosure, a system includes a means for receiving a memory entry and a means for identifying an available slot in a ring buffer having a plurality of slots. A subset of the slots is initialized with an initialization value, and the initialization value is interpreted as an unavailable slot by the producer processor. The system also includes a means for storing the memory entry in the available slot at an offset in the ring buffer, a means for consuming the memory entry, and a means for invalidating one of the subset of slots in the ring buffer by overwriting the initialization value with an invalid value to transition the one of the subset of slots from an unavailable slot to an available slot

Aspects of the subject matter described herein may be useful alone or in combination with one or more other aspects described herein. In a 29th exemplary aspect of the present disclosure, a system includes a memory including a ring buffer with a plurality of slots. A first subset of the plurality of slots is initialized with an initialization value and a second subset of the plurality of slots is initialized with an invalid value. The system also includes a producer processor and a consumer processor, both of which are in communication with the memory. The producer processor is configured to receive a plurality of requests associated with a plurality of respective memory entries and store each of the plurality of requests in a respective slot that contains an invalid value. The producer processor is prevented from storing a request in a slot occupied by a valid value and is prevented from storing a request in a slot occupied by an initialization value. The consumer processor is configured to process each of the plurality of requests and invalidate one of a plurality of respective slots for each of the plurality of stored requests. Each of the plurality of respective slots includes one of an initialization value and a valid value, and the consumer processor invalidates a first slot initialized with an initialization value for a first stored request of the plurality of stored requests.

In a 30th exemplary aspect of the present disclosure, which may be used in combination with any one or more of the preceding aspects (e.g., the 29th aspect), the first subset of initialization values is configured to maintain a spacing between the consumer processor and the producer process. Additionally, the spacing includes a set of slots that occupy less than one entire cache-line.

In a 31st exemplary aspect of the present disclosure, which may be used in combination with any one or more of the preceding aspects (e.g., the 29th aspect), the producer processor is configured to interpret an initialization value as a valid value.

In a 32nd exemplary aspect of the present disclosure, which may be used in combination with any one or more of the preceding aspects (e.g., the 29th aspect), the consumer processor is configured to interpret an initialization value as a valid value.

In a 33rd exemplary aspect of the present disclosure, which may be used in combination with any one or more of the preceding aspects (e.g., the 29th aspect), processing each of the plurality of requests includes retrieving each of the plurality of requests and copying each of the plurality of requests to a different memory.

In a 34th exemplary aspect of the present disclosure, which may be used in combination with any one or more of the preceding aspects (e.g., the 29th aspect), the consumer processor and the producer processor execute on different cores of a physical processor.

In a 35th exemplary aspect of the present disclosure, which may be used in combination with any one or more of the preceding aspects (e.g., the 29th aspect), the consumer processor and the producer processor execute on different physical processors.

In a 36th exemplary aspect of the present disclosure, which may be used in combination with any one or more of the preceding aspects (e.g., the 29th aspect), the first slot is initialized with an initialization value is in a different cache line than the slot with the first stored request.

In a 37th exemplary aspect of the present disclosure, which may be used in combination with any one or more of the preceding aspects (e.g., the 29th aspect), the ring buffer occupies a non-integer number of cache lines.

In a 38th exemplary aspect of the present disclosure, which may be used in combination with any one or more of the preceding aspects (e.g., the 29th aspect), the ring buffer occupies an integer number of cache lines.

In a 39th exemplary aspect of the present disclosure, which may be used in combination with any one or more of the preceding aspects (e.g., the 29th aspect), the ring buffer is augmented with a quantity of additional slots and each slot of the quantity of additional slots is initialized with the initialization value.

Aspects of the subject matter described herein may be useful alone or in combination with one or more other aspects described herein. In a 40th exemplary aspect of the present disclosure, method includes receiving, by a producer processor, a plurality of requests associated with a plurality of respective memory entries. The producer processor stores each of the plurality of requests in a respective slot that contains an invalid value. The producer processor is prevented from storing a request in a slot occupied by a valid value and is prevented from storing a request in a slot occupied by an initialization value. The method also includes processing, by a consumer processor, each of the plurality of requests. Additionally, the consumer processor invalidates one of a plurality of respective slots for each of the plurality of stored requests by first invalidating a first slot initialized with an initialization value for a first stored request of the plurality of stored requests. Each of the plurality of respective slots includes one of an initialization value and a valid value.

In a 41st exemplary aspect of the present disclosure, which may be used in combination with any one or more of the preceding aspects (e.g., the 40th aspect), a first subset of initialization values is configured to maintain a spacing between the consumer processor and the producer process, and the spacing includes a set of slots that occupy less than one entire cache-line.

In a 42nd exemplary aspect of the present disclosure, which may be used in combination with any one or more of the preceding aspects (e.g., the 40th aspect), processing each of the plurality of requests includes retrieving each of the plurality of requests and copying each of the plurality of requests to a different memory.

In a 43rd exemplary aspect of the present disclosure, which may be used in combination with any one or more of the preceding aspects (e.g., the 40th aspect), the method further includes allocating an augmented ring buffer forming each of the respective slots. The augmented ring buffer includes a quantity of additional slots and each additional slot is initialized with a respective initialization value.

Aspects of the subject matter described herein may be useful alone or in combination with one or more other aspects described herein. In a 44th exemplary aspect of the present disclosure, a non-transitory machine-readable medium storing code, which when executed by a producer processor and a consumer processor, is configured to receive a plurality of requests associated with a plurality of respective memory entries and store each of the plurality of requests in a respective slot that contains an invalid value. The producer processor is prevented from storing a request in a slot occupied by a valid value and prevented from storing a request in a slot occupied by an initialization value. The non-transitory machine-readable medium is also configured to process each of the plurality of requests and invalidate one of a plurality of respective slots for each of the plurality of stored requests by first invalidating a first slot initialized with an initialization value for a first stored request of the plurality of stored requests. Each of the plurality of respective slots includes one of an initialization value and a valid value.

Aspects of the subject matter described herein may be useful alone or in combination with one or more other aspects described herein. In a 45th exemplary aspect of the present disclosure, a system includes a means for receiving a plurality of requests associated with a plurality of respective memory entries and a means for storing each of the plurality of requests in a respective slot that contains an invalid value. The means for storing is prevented from storing a request in a slot occupied by a valid value and prevented from storing an initialization value The system also includes a means for processing each of the plurality of requests, and a means for invalidating one of a plurality of respective slots for each of the plurality of stored requests by first invalidating a first slot initialized with an initialization value for a first stored request of the plurality of stored requests, wherein each of the plurality of respective slots includes one of an initialization value and a valid value.