COORDINATING DATA PACKET PROCESSING BETWEEN KERNEL SPACE AND USER SPACE

A system may comprise a group of processor cores configured to generate kernel-space threads in a kernel space and user-space threads in a user space of a Linux operating system. Each kernel-space thread may be executable by one of the processor cores to perform operations. For example, a kernel-space thread may receive a data packet transmitted from a client device via a network. The kernel-space thread may determine a particular communication channel assigned to a processor core that is executing the kernel-space thread. The kernel-space thread may determine if the data packet satisfies a condition based on information extracted from the data packet. In response to determining that the data packet does not satisfy the condition, the kernel-space thread may transmit data from the data packet via the particular communication channel to a user-space thread. The user-space thread may be configured to receive and process the data.

TECHNICAL FIELD

The present disclosure relates generally to processing data packets in computing systems. More specifically, but not by way of limitation, this disclosure relates to coordinating data packet processing between kernel spaces and user spaces in operating systems.

BACKGROUND

Computers use operating systems to manage system processes and resources. Some operating systems, such as the Linux operating system, include a low-level software component, referred to as a kernel, for managing system processes and resources. The memory of the operating system can be partitioned into two distinct regions: a kernel space and a user space. The kernel space is where the kernel executes and provides its services. The user space is where user processes (e.g., everything other than the kernel) execute. Generally, the kernel space can only be accessed by user processes through system calls. A system call is a request by a user process for a service performed by the kernel, such as an input/output (I/O) service. User processes can invoke system calls for causing the kernel to perform tasks in kernel space. Conversely, the kernel can perform upcalls. An upcall is a request by the kernel for a user process to perform a task in user space.

DETAILED DESCRIPTION

A computing system with multiple processor cores may receive data packets via ports. In some cases, a communication channel can be established between each port and each processor core to transmit data packets to the processor core for handling. For example, a computing system with two processor cores and three ports may establish six communication channels, such that there is a first set of communication channels between the first processor core and the three ports and a second set of communication channels between the second processor core and the three ports. But there are limits on the number of communication channels that may be created on a given computing system given the finite number of available computing resources (e.g., processing power and memory). As a result, this approach can quickly reach the maximum number of communication channels that can be created, resulting in scaling problems.

Computing systems can also have other problems with respect to how data packets are handled. For example, each data packet may be received by any of the processor cores. But when a data packet is received by a processor core, it may trigger the thundering herd problem, where a large number of processes or threads in the computing system are concurrently “awoken” and attempt to process the data packet even though only one process or thread may actually do so. This may cause the processes or threads to unnecessarily consume and compete for resources, which may negatively affect the performance of the computing system. Computing systems may also have difficulty processing multiple data packets in a particular order. For example, a computing system may establish a single communication channel for each port. A single port may have multiple threads processing data packets from that port. If multiple data packets are received by that port in a particular order, the multiple threads may process the multiple data packets. Because some threads may process data packets faster than other threads, or because of how data processing is distributed among the threads, the multiple data packets may be processed out-of-order (e.g., in an order that is different from the sequence in which the data packets were received). This may cause problems in a variety of contexts in which maintaining the order of the data packets is important.

Some examples of the present disclosure can overcome one or more of the abovementioned problems by generating a one-to-one mapping of kernel-space threads to user-space threads, so that the same types of data packets are handled by the same kernel-space thread and the same user-space thread. A kernel-space thread is a processing thread operating in kernel space, and a user-space thread is a processing thread operating in user space. More specifically, a computing system can include multiple thread pairs, where each pair includes a single kernel-space thread and a single user-space thread. The user-space thread may establish a single communication channel between itself and the kernel-space thread. The Linux kernel can receive data packets and distribute the incoming data packets among the kernel-space threads according to a predefined distribution scheme, for example such that the same types of data packets are consistently distributed to the same kernel-space thread. This, in turn, may help ensure that the data packets are handled by the same user-space thread. Since the same types of data packets are consistently handled by the same kernel-space thread and the same user-space thread, the sequencing problem described above may be avoided. And by using the same kernel-space thread and user-space thread to consistently handle the same types of data packets, the scaling problem and thundering herd problem described above may also be avoided.

As one particular example, the above techniques may be implemented by a network switch, router, or other networking component executing a Linux operating system with a kernel. After receiving a data packet, a kernel-space thread of the networking component may determine if a flow path exists for the data packet in a flow table located in the Linux kernel. The flow table may be a table of flow paths. A flow path may correspond to a type of data packet and may include instructions for how to handle that type of data packet. If a flow path exists for the data packet, the kernel-space thread may execute the instructions included in the flow path on the data packet. If the flow path does not exist, the kernel-space thread may transmit (e.g., via an upcall) the data packet to the user-space thread that corresponds to the kernel-space thread via a communication channel, so that the user-space thread can further process the data packet. For example, the user-space thread may determine a flow path for the data packet. The user-space thread may transmit data describing the flow path to the kernel-space thread, which can receive the data and add the flow path to the flow table. Thereafter, the kernel-space thread may receive new data packets that are similar to (e.g., of the same type as) the previously handled data packet. Because the kernel-space thread may now have the requisite flow path information in the flow table, the kernel-space thread can access the flow path and handle the data packets accordingly, instead of relying on the user-space thread again to process the new data packets. This can reduce latency and conserve computing resources.

FIG.1is a block diagram of an example of a system100including a kernel space102and a user space106for coordinating data flow according to some aspects of the present disclosure. The kernel space102and the user space106can exist in a memory of a Linux operating system. The kernel space102can include kernel-space threads104a-f, which are processing threads executing in the kernel space102. The user space106can include user-space threads108a-f, which are processing threads executing in the user space106. The kernel-space threads104a-fand user-space threads108a-fmay be executed by processor cores.

The user-space threads108a-fmay generate communication channels112a-ffor enabling the user-space threads108a-fand the kernel-space threads104a-fto communicate (e.g., bidirectionally) with one another. Examples of the communication channels112a-fmay include netlink sockets or shared memory locations. Each user-space thread108may generate one communication channel112, and each communication channel112may be associated with one kernel-space thread104. In some examples, a paired kernel-space thread and user-space thread, such as kernel-space thread104aand user-space thread108a, may be executed by the same processor core or different processor cores.

After generating the communication channels, the user-space threads108a-fcan transmit identifiers of the communication channels112a-fto the kernel-space threads104a-f. Examples of the identifiers may include a netlink socket ID or a memory location. One or more of the kernel-space threads104a-fmay use the identifiers to generate a mapping120. The mapping120can indicate relationships between the user-space threads108a-fand the kernel-space threads104a-f. For example, the mapping120can define relationships between the communication channel identifiers and the processor cores executing the kernel-space threads104a-f. An example of such a mapping120is shown in the dashed box ofFIG.1.

Once the mapping120has been generated, one or more client devices116may send data packets118to a processing thread110located within the kernel space102. Thus, the processing thread110is a kernel-space thread. The processing thread110can include one or more distribution schemes122. The data packets118can include a sequence of data packets that can be distributed by the processing thread110to individual kernel-space threads104a-faccording to the distribution schemes122. The distribution schemes122may be predefined. Examples of the distribution schemes122can include receive flow steering (“RFS”), receive side-scaling (“RSS”), and receive packet steering (“RPS”).

After receiving a data packet118, a kernel-space thread104, such as kernel-space thread104c, may process the data packet118. In some examples, processing the data packet118may include extracting information (e.g., header data or payload data) from the data packet118and analyzing the extracted information to determine whether it satisfies one or more predefined criteria. For example, the system100can be part of a virtual switch such as Open vSwitch. In some such examples, the kernel-space thread104ccan analyze header data of the data packet118to determine if the data packet118corresponds to any flow paths126defined in a flow table124in the kernel space102. If the data packet118corresponds to a flow path126in the flow table124, the kernel-space thread104cmay execute actions associated with the flow path126corresponding to the data packet118. For example, the kernel-space thread104cmay transmit the data packet118out of the system100to a destination. If the data packet118does not correspond to any flow paths126in the flow table124, it may mean that a flow path for the data packet118does not yet exist in the flow table124. So, the kernel-space thread104cmay coordinate with the user space106so that the data packet118can be further processed in user space106. Coordinating with the user space106may include transmitting the data packet118or the information extracted therefrom to the user space106for further processing by a corresponding user-space thread.

The kernel-space thread104cmay transmit the data packet118or information extracted therefrom to the user space106via one of the communication channels112a-f. To determine which communication channel to use, the kernel-space thread104caccess the mapping120. For example, the kernel-space thread104ccan determine which particular processor core is executing the kernel-space thread104c. The kernel-space thread104cmay then access the mapping120to identify a particular communication channel112cthat is associated with that processor core. For example, the communication channel112ccan be correlated in the mapping120to the processor core that executes kernel-space thread104c. So, kernel-space thread104ccan transmit the data packet118via communication channel112cto whichever user-space thread108a-fcorresponds to that communication channel112c. Since user-space thread108ccorresponds to the communication channel112cinFIG.1, the user-space thread108ccan receive the data packet118and perform additional processing with respect to the data packet118. For example, the user-space thread108ccan determine a flow path for the data packet118based on information extracted from the data packet118. The user-space thread108cmay then cause the flow path to be included in the flow table124. For example, the user-space thread108ccan indicate the flow path to the kernel-space thread104c, which in turn can incorporate the flow path into the flow table124.

In the above example, the kernel-space thread104cprovided the data packet118to the user-space thread108cin response to determining that the data packet118does not satisfy one or more predefined criteria. In particular, the kernel-space thread104cprovided the data packet118to the user-space thread108cin response to determining that the data packet118does not correspond to any flow paths126in the flow table124. But, the kernel-space thread104cmay additionally or alternatively provide the data packet118to the user-space thread108cfor other reasons. For example, the kernel-space thread104ccan provide the data packet118to the user-space thread108cin response to determining that the data packet118does satisfy one or more predefined criteria. In one such example, the kernel-space thread104ccan determine that the data packet118has a corresponding flow path in the flow table124. But the flow path may include instructions for the kernel-space thread104cto provide (e.g., via an upcall) the data packet118to the user-space thread108c, so that the user-space thread108ccan further process the data packet118(e.g., rather than the kernel-space thread104c). This may be done, for example, to provide the data packet118to a particular user-space application or because the kernel-space thread104cdoes not support a particular computing operation. Based on these instructions, the kernel-space104ccan still provide the data packet118to the user-space thread108c.

As noted above, the processing thread110may forward data packets118of the same type to a single kernel-space thread104based on the distribution scheme122. This may allow for the data packets118to be processed in sequence by the same kernel-space thread104(and consequently the same user-space thread108). By processing the data packets118in sequence, it may allow for the data packets118to be transmitted to a destination in the same order that they were received by the processing thread110. In this way, the ordering of the data packets118can be preserved such that they arrive at the destination in a correct sequence.

AlthoughFIG.1depicts a certain number and arrangement of components, this is for illustrative purposes and intended to be non-limiting. Other examples may include more components, fewer components, different components, or a different arrangement of the components shown inFIG.1.

FIG.2is a block diagram of a system202including multiple processor cores204a-dfor coordinating data flow according to some aspects of the present disclosure. AlthoughFIG.2shows four processor cores204a-d, in other examples the system202may include more or fewer processor cores. The system202may include a Linux operating system203that includes a kernel space102and a user space106. The kernel space102and the user space106may contain kernel-space threads104a-dand user-space threads108a-d, respectively. Each processor core204may execute a kernel-space thread104and a user-space thread108.

Non-limiting examples of the processor cores204a-dinclude a Field-Programmable Gate Array (FPGA), an application-specific integrated circuit (ASIC), a microprocessor, etc. The processor cores204a-dcan execute instructions stored in memory to perform operations. The instructions may include processor-specific instructions generated by a compiler or an interpreter from code written in any suitable computer-programming language, such as C, C++, C#, etc. In some examples, the instructions can correspond to the kernel-space threads104a-dor user-space threads108a-d.

The system202can also include a memory. The memory can have a set of memory locations allocated to kernel space102and another set of memory locations allocated to user space106. The memory can include one memory device or multiple memory devices. The memory can be non-volatile and may include any type of memory that retains stored information when powered off. Non-limiting examples of the memory include electrically erasable and programmable read-only memory (EEPROM), flash memory, or any other type of non-volatile memory. At least some of the memory can include a non-transitory computer-readable medium from which the processor cores204a-dcan read instructions. A computer-readable medium can include electronic, optical, magnetic, or other storage devices capable of providing the processor cores204a-dwith computer-readable instructions or other program code. Non-limiting examples of a computer-readable medium include magnetic disk(s), memory chip(s), ROM, random-access memory (RAM), an ASIC, a configured processor, optical storage, or any other medium from which a computer processor can read the instructions.

The processor cores204a-dcan execute the instructions to perform operations. For example, a client device116may send a data packet118to the system202. The data packet118may be distributed to kernel-space thread104aexecuting on processor core204a. The kernel-space thread104amay extract information206from the data packet118. The information206may be used by the kernel-space thread104ato determine if the data packet118satisfies a condition. For example, the condition may be whether a flow path126exists for the data packet118. If the condition is not satisfied, the kernel-space thread104amay transmit the data packet118or the information206extracted therefrom to a user-space thread108athat corresponds to the kernel-space thread104a. The user-space thread108aand the kernel-space thread104amay be executed by the same processor core204a. The user-space thread108acan receive and process the data packet118or information206. For example, the user-space thread108amay inspect, filter, or analyze the data packet118. Based on the processing results, the user-space thread108amay perform one or more computing operations. For example, the user-space thread108amay deliver the data packet118to an application such as a web server. As another example, the user-space thread108amay determine a flow path for the data packet and insert the flow path into a flow table. As yet another example, the user-space thread108amay reject the data packet118(e.g., if the data packet is determined to be suspicious or malicious).

FIG.3is a flow chart of an example of a process300performed by a kernel-space thread104afor handling a data packet118according to some aspects of the present disclosure. Other examples can include more steps, few steps, different steps, or a different order of steps than is shown inFIG.3. The steps ofFIG.3are discussed below with reference to the components discussed above in relation toFIG.2.

In block302, a kernel-space thread104aexecuting on a processor core204areceives a data packet118transmitted from a client device116via a network. The network may be a local area network or the Internet.

In block304, the kernel-space thread104adetermines, from among a group of communication channels112a-dassigned to processor cores204a-d, a particular communication channel112aassigned to the processor core204athat includes the kernel-space thread104a. The kernel-space thread104amay determine the particular communication channel112aby accessing a mapping120located in the memory. Each communication channel112may be associated with a single processor core204, and the mapping120may include a table of the associations.

In block306, the kernel-space thread104adetermines if the data packet118satisfies a condition based on information206(e.g., header data, payload data, etc.) extracted from the data packet118. For example, the information206may include a source address, such as an IP address or a MAC address. The kernel-space thread104amay access a flow table124located in the memory to determine if a flow path126exists for data packets118with a certain source address. If the flow path126exists for the source address, the data packet118satisfies the condition and the kernel-space thread104amay process the data packet118according to the instructions in the flow path126. If the data packet118does not satisfy the condition, the process300continues to block308.

In block308, in response to determining that the data packet118does not satisfy the condition, the kernel-space thread104atransmits data from the data packet118via the particular communication channel112ato a user-space thread108aof the plurality of user-space threads108. The data may be the same as or different from the information206. The user-space thread108ais configured to receive and process the data. The user-space thread108amay have additional instructions and resources for processing the data that the kernel-space thread104amay not have. The user-space thread108amay transmit the data packet118to a destination (e.g., that is remote to the system202) after processing.

FIG.4is a flow chart of an example of a process400performed by a kernel-space thread104aand a user-space thread108afor handling a data packet118according to some aspects of the present disclosure. Other examples can include more steps, few steps, different steps, or a different order of steps than is shown inFIG.4. The steps ofFIG.4are discussed below with reference to the components discussed above in relation toFIG.2.

In block402, the kernel-space thread104adetermines whether a flow path126for a data packet118exists in a flow table124. To do so, the kernel-space thread104amay determine if the flow paths126in the flow table124are associated with information206extracted from the data packet118.

In block404, in response to determining that the flow path126does not exist in the flow table124, the kernel-space thread104atransmits the data packet118via the particular communication channel112ato the user-space thread108a.

In block406, the user-space thread108areceives the data packet118via the particular communication channel112a.

In block408, in response to receiving the data packet118, the user-space thread108adetermines a flow path126for the data packet118. In particular, the user-space thread108amay determine a flow path126using information206extracted from the data packet118. The user-space thread108amay use predetermined user-defined criteria for assigning a flow path to the data packet118.

In block410, in response to determining the flow path126, the user-space thread108acauses the flow path126for the data packet118to be added to the flow table124. For example, the user-space thread108amay indicate the flow path126to the kernel-space thread104avia the communication channel112a. In some examples, the communication channels112amay be a shared memory location between the kernel-space thread104aand the user-space thread108a. For example, the user-space thread108amay store data describing the flow path126in the shared memory location, and the kernel-space thread104amay access the shared memory location to retrieve data. In other examples, the communication channel112amay be a netlink socket for transmitting data describing the flow path126from the user-space thread108ato the kernel-space thread104a. The kernel-space thread104amay then add the flow path126to the flow table124. Alternatively, the user-space thread108amay directly add the flow path126to the flow table124. Adding the flow path126to the flow table124may allow subsequent data packets118received by the kernel space102to be processed by a kernel-space thread104rather than a user-space thread108, so as to reduce latency and conserve computing resources (e.g., processing power and memory).

FIG.5is a flow chart of an example of a process500for generating a mapping120according to some aspects of the present disclosure. Other examples can include more steps, few steps, different steps, or a different order of steps than is shown inFIG.5. The steps ofFIG.5are discussed below with reference to the components discussed above in relation toFIGS.1-2.

In block502, one or more processing threads receive identifiers of the communication channels112from the user-space threads108. Examples of the one or more processing threads can include the one or more kernel-space threads104, the processing thread110, or any combination of these. Each user-space thread108may generate a single communication channel112. Each communication channel112may be associated with a single processor core204. In one example, user-space thread108amay generate a communication channel112athat has an identifier. The communication channel112amay be a netlink socket with a netlink socket ID. The processing thread may receive the netlink socket ID from user-space108a.

In block504, the processing thread110generates the mapping120based on the identifiers. In some examples, the mapping120may be a table of associations between communication channel identifiers (e.g., netlink socket ID's) and processor-core identifiers. The processor-core identifiers can identify the processor cores204. The processor cores204can execute the user-space threads108that sent the communication channel identifiers. A reason that the communication channels may be correlated in the mapping120to the processor cores204is that the kernel space102and the user space106may have different views of the computer system (e.g., the available number of processor cores204a-d), and thus using the processor cores in the mapping120can provide a common indexing mechanism between user space106and kernel space102. The mapping120may be accessed by a kernel-space thread104for determining a communication channel to which to transmit a data packet118for further processing by a user-space thread.

While the above examples involve kernel-space threads providing data packets to user-space threads, the present disclosure is not intended to be limited to this arrangement. Similar techniques can also be applied such that kernel-space threads provide data packets to other kernel-space threads, user-space threads provide data packets to other user-space threads, or user-space threads provide data packets to kernel-space threads. Thus, any processing thread in the system may provide data packets to any other processing thread, regardless of whether the other processor thread is located on the same processor core or a different processor core. This is described in further detail below with respect toFIG.6.

FIG.6is a block diagram of an example of a system600including multiple processing threads602aand602bfor coordinating data flow according to some aspects of the present disclosure. In some examples, a computing system such as the system600may include processing thread pairs. The processing thread pairs may include one kernel-space thread and one user-space thread, as depicted inFIGS.1and2. Alternatively, the processing thread pairs may include any two threads in a computing system, such as processing threads602aand602b. In the example depicted inFIG.6, processing threads602aand602bmay both be user-space threads or may both be kernel-space threads. The processing threads602a-bmay be located in a memory604in the system600. As depicted inFIG.6, the processing threads602a-bmay be executed by a single processor core606in the system600to coordinate data flow. Alternatively, processing thread602amay be executed by a first processor core and processing thread602bmay be executed by a second processor core in the system600.

The processing threads602a-bmay coordinate data flow in a similar manner to the systems and methods described above with respect toFIGS.1-5. For example, the processing thread602bmay generate a communication channel608for enabling the processing threads602a-bto communicate (e.g., bidirectionally) with one another. The processing thread602bmay transmit an identifier of the communication channel608to the processing thread602a. The processing thread602amay use the identifier to generate a mapping610that can indicate a relationship between the processing threads602a-b. The processing thread602amay receive a data packet612from a client device614. The processing thread602amay process the data packet612to determine if the data packet612corresponds to a flow path616in a flow table618. If the data packet612does not correspond to any flow paths616, the processing thread602amay transmit the data packet612or information extracted therefrom to the processing thread602bvia the communication channel608. The processing thread602bmay perform further processing on the data packet612.