Clustering of devices with traffic distribution by L2 Switch - One limitation & Mitigation

In my last post on "Data Center/Enterprises Clustering of Devices"  I discussed on how L2 switches are enabling device equipment vendors to provide cluster solution to take up the increasing load on the networks.  Many L2 switches are capable of analyzing multiple different types of  layer 2 headers to get to the inner IP packet and use inner IP packet source and destination IP address fields to distribute the traffic across multiple devices in the cluster using hash distribution.  L2 switches typically understand Ethernet and MPLS related headers such as Ethernet DIX,  LLC/SNAP,  802.1Q VLAN headers and MPLS Label headers.  That is, L2 switch can get hold of IP packets if packets are sent over above mentioned L2 headers. 

In some deployments, IP packets may be encapsulated in multiple L2 headers or L3 tunnels.  Some examples are : PW (Pseudo wire) header,  Ethernet over Ethernet using PW,  GRE/UDP,  GTP/UDP, IPinIP,  Mobile IP and may more.  L2 switches in the market today are not capable of understanding these headers to to get to the inner IP header.   In these cases, distribution based on inner IP header fileds will not be possible.  In these deployments, L2 switches may need to resort to distribution based on L2 header fields such as source and destination MAC or tunnel IP header fields.  Unfortunately,  distribution based on these fields may not be good at all.  If you take an example of this cluster being places between two routers,  MAC addressees of every packet traversing the cluster will be same.  Hence any distribution based on the MAC addresses would go to only one device in the cluster.  Similar would be the case, if distribution depends on the tunnel IP header fields. 

Switches have one capability though.  They can generate the hash based on calculated CRC on some part of the packet or CRC of the Ethernet packet.   CRC of the Ethernet packet can be assumed to provide good distribution as CRC on Ethernet packet is based on the complete Frame payload, that is, including the inner IP packet payload. Switches have capability to take few bits of CRC to distribute the packets across multiple cluster devices.  But the issue with this is that packets belonging to same connection would go to different cluster devices.  Base on my earlier post, cluster devices assume that packets belonging to a connection would always land on the same device. This assumption is no longer true if the cluster solution is being deployed in above mentioned environments.  These types of environments are not common at all in Data Center and Enterprises environments.  So, this problem may not be there in many instances. But service provider environments, multiple L2 and tunnel header situations are not uncommon.

How do cluster solutions work in these environments?

In these environments, if CRC based distribution is used,  switches are really doing packet sprinkling across multiple devices.  In these cluster devices should have additional intelligence.  

• Cluster devices should be able to get past the headers to get to the inner IP header.
• Cluster devices among themselves should have understanding of session distribution. One simple method is to do what switches were doing.  That is, they can generate the hash on the IP header fields (source and destination IP) and figure out the device which got the packet is the one which needs to server based on the hash value.  If it is,  it should continue processing the packet. If it is not, then it should give the packet to the device that owns the hash value.  

There could be good amount of traffic among cluster devices.  They can use the switch as their back plane to send and receive the traffic among them.  To avoid other device doing same thing, that is getting hold of the inner IP header and hashing on the inner IP header fields again,  the sending device can send this information along with the packet and receiving device can avoid doing same operations again.

As indicated above,  only few deployments where L2 switch does not do inner IP header based distribution.  If same cluster solution being provided for all kinds of deployments, then it is good for network equipment vendors of cluster solution to provide configuration on the cluster whether the packets which are being distributed by L2 switch is packet sprinkler or intelligent IP flow based sprinkling.  If it is packet based sprinkling, then additional logic in devices can kick in to figure out the real destination device.

User space Packet processing applications - Execution Engine differences with processors

Please read this post to understand Execution Engine.

Many processors with descriptor based IO devices have their own interrupts.  For each device, there is corresponding UIO device.  Hence software poll based EE provides 'file descriptor' based interface to register, deregister and get hold of indication through callbacks.  EE applications are expected to read the packets from the the hardware by themselves and do rest of the processing.

As discussed in UIO related posts,  we have discussed ways to share the interrupts across devices. As long as UIO related application kernel driver knows the type of event for which interrupt is generated, appropriate UIO FD is woken up and  things will work fine.

Non-descriptor based IO is becoming quite common in recent Multicore processors.  Hardware events (packets from the Ethernet controllers,  acceleration results from the acceleration engines) are given to the software through set of HW interfaces.  Selection of  HW interface by the hardware is based on some load balancing algorithms or based on some software inputs.  But the point is that, the events which are being given to the software through one HW interface are from multiple hardware IO sources.  Each HW interface is normally associated with one interrupt.  One might say that this can be treated as interrupt being shared across multiple devices.  But, some of  the Multicore processors don't have facility to know the reason for HW interrupt.  Nor they have facility to know the event type of first pending event in HW interface.  Unless the event is dequeued from the HW interface, it is impossible to know the type of event.  Also, due to interrupt coalescing requirements, a given interrupt instance might represent multiple events of different IO source devices.  Due to this behavior,  there may be only one  UIO device for multiple IO devices.  Hence responsibility of demultiplexing these events to right EE application falls on the EE itself.  EE needs to read the event and find out the right application and call the appropriate callback function registered to it. Let us call this functionality in EE as 'EE Event DeMux'.

In Descriptor based systems,  EE applications are expected to read the HW events (packets & acceleration results) by each EE application.  Callback function invocation only provides indication for EE application to read the events from associated hardware descriptors.  In case of 'EE Event DeMux',  the event is already read by the EE itself.  Hence, event is expected to be passed to the callback function.

'EE Event DeMux' submodule registers itself with the rest of EE module to get UIO indication in case of software poll method.  In case of  hardware poll,  'EE Event DeMux' in invoked by the  hardware poll function.

Multicore processors normally provides HW interface for multiple IO devices for the devices which are part of the Multicore processors.  External devices such as PCI and other HW bus based IO devices are still implemented using descriptor based mechanism.  Software poll based EE should not assume that all devices are satisfied using 'EE Event DeMux'.   As far as core Software poll system is concerned,  'EE Event DeMux' is another EE application.  Hardware Poll based method, if they need to use descriptor based HW interfaces, then the hardware poll should also poll descriptor based HW interfaces.

When 'EE Event DeMux' is used by EE applications (such as Ethernet Driver,  Accelerator drivers,), it is necessary that 'EE Event DeMux' considers following requirements.

• It should have its own 'Quota' as number of maximum events it is going to read from the HW interface as part of the callback function invocation by the EE core. Once it reads the 'Quota' number of events or if there are no more events, then it should return back to the 'Core EE' module.  
• Since this the module which demuxes to some EE applications, it should provide its own register/De-register functions.
• When 'Core EE' module invokes this module callback function due to interrupt generation or due to hardware poll,  as described above, it is expected to read at the most 'quota' number of events. While giving the control back to the  'Core EE', it is expected to call EE applications that there are no more events in this iteration. Some EE applications might register to get this indication.  For example, Ethernet driver application might register for this to do the 'Generic Receive Offload' function.  GRO functionality requires to know when to give up while doing TCP coalescing functionality.  In case descriptor based drivers, this issue does not arise as each Ethernet driver as part of callback invocation by the EE itself reads the events and knows when to give up.

Thanks for reading my earlier post.  I hope this helps.

User space Packet processing applications - Execution Engine

If you plan to port your data plane network processing application from Linux kernel space to user space,  first thing you would think is how you can port your software to user space with minimal changes to your software.  Execution Engine is the first thing one would think of.

Many kernel based networking applications don't create their own threads.  They work with the threads which are already present in the kernel.   For example,  packet processing applications such as Firewall, IDS/IPS, Ipsec VPN work in the context of Kernel TCP/IP stack.  This is mainly done for performance reasons.  Additional threads for these applications result in multiple context switches.  Also, it results into pipeline processing as packets handover from one execution context to another execution context.  Pipelining requires queues involving enqueue, dequeue operations which take some core cycles.  Also, it results into flow control issues when one thread processing is more than other threads. 

Essentially,  Linux kernel itself provides execution contexts and networking packet processing applications work within these contexts.  Linux TCP/IP stack itself works in softirq context.  SoftIRQ processing in normal kernel runs from both IRQ context as well as softirqd context.  I would say 90% of the time SoftIRQ processing happens in the IRQ context.  In PREEMPT_RT patched kernel, network IRQs are mapped to the IRQ threads.  In any case,  the context at which network packet processing applications run is unknown to the applications.  Since Linux kernel execution contexts are per core basis,  there are  less shared data structure and hence less locking requirement.  Kernel and underlying hardware also provides mechanism to balance the traffic across different execution contexts with flow granularity. In cases where hardware does not provide any load balancing functionality,  IRQs are dedicated to different execution contexts.  If there are 4 Ethernet devices and 2 cores (hence two execution contexts),  four receive interrupts of Ethernet controllers are assigned equally to two execution contexts.. If the traffic from all four Ethernet devices is same or similar, then both the cores are used effectively.  

Execution Engine in user space packet processing applications, if made similar to the Kernel execution contexts, then application porting becomes simpler.  Execution Engine (EE) can be considered part of infrastructure to enable DP processing in user space.  EE design should consider following.

• There could be multiple data plane processing applications in user space.  Each DP daemon may be assigned to run in fixed set of cores - core mask may be provided at startup time.
• If DP daemon is not associated with any core mask, then it should assume that the daemon may be run by all cores. That is, it should considered as if core mask contains all core bits set.
• Set of cores are dedicated to the daemon. That is, those cores don't do anything else other than doing DP processing of the DP daemon.  This facility is typically used to ensure in Multicore processors providing hardware poll.  Recent generation of Multicore processors have facility to provide incoming events and acceleration results through single portal (or station or work group).  Since the core is dedicated, there is no software polling is required.  That is hardware polling can be used if underlying hardware supports it and if the core(s) are dedicated to the process.

It appears that number threads in the process equaling the number of cores assigned to the process provides the best performance. Also, this also provides great similarity with kernel execution contexts. With the above background,  I believe EE needs to have following capabilities:

• Provide capability to assign the core mask. 
• Provide capability to indicate whether the cores are dedicated or assigned.
• If no core mask is provided, it should have capability to read the number of cores in the system and should assume that all the cores are given in core-mask.
• Provide capability to use software poll or hardware poll.  Hardware poll should be validated and accepted only if underlying hardware supports it and only if the cores are dedicated to it. Hardware polling has performance advantages as it does not require interrupt generation and interrupt processing. But the disadvantage is that the core is not used for anything else.  One should weigh the options based on the application performance requirements. 
• API it exposes for its applications should be same whether the execution engine uses software poll (such as epoll()) or hardware poll.

Typically capabilities are provided through command line parameters or via some configuration file.  EE is expected to create as many threads as number of cores in the core mask.  Each thread should provide following functionality:

• Software timers functionality - EE should provide following functionality.
• Creation and deletion of timer block
• Starting, stopping, restarting timers in each timer block.
• Each application can create one ore more timer blocks and use large number of timers in each timer block.
• As in Kernel,  it is required that EE provides cascaded timer wheels for each timer block.
• Facility for applications to register/De register for events and passing the events.
• API function (EEGetPollType()) to return the type of poll - Software or Hardware : This function would be used by EE applications to use file descriptors such as UIO and other application oriented kernel drivers for software poll or use hardware facilities for hardware poll 
• Register Event Receiver :  EE applications can use this function to register the FD, READ/Write/Error, associated callback function pointer and callback argument.
• Deregister Event receiver:  EE applications can call this to de register the event receiver which was registered using 'Register' function.  
• Variations above API will need to be provided by EE if it is configured with hardware poll. Since each hardware device has its own way of representing this,  there may as many number of API sets. Some part of each EE application have hardware specific initialization code and calls the right set of API functions.
• Note that one thread handles multiple devices (multiple file descriptors in case of software poll). Every time epoll() comes out,  callback functions of ready FDs would need be called. These functions which are provided by the EE applications are expected to get hold of packets in case of Ethernet controllers, acceleration results in case of  acceleration devices or other kinds of events from different kinds of devices. From the UIO discussion,  if the applications use UIO based interrupts to wakeup the thread, then it is expected that all events are read from the device to reduce the number of wakeups (UIO coalescing capability).  Some EE application might be reading lot of events. For each event it reads, it is going to call its own application function.  These applications can be very heavy too. Due to this,  if there are multiple FDs are ready,  one EE application may take very long time before it returns back to the EE.  This results into unfair assignment of EE thread to FDs which are also ready.  This unfairness might even result into packet drops or increase the jitter if high priority traffic is pending to be read in other devices.  To ensure the fairness,   it is expected that EE applications process only 'quota' number of events at any time before returning back to the EE.  'Quota' is tunable parameter and can be different for different types of devices.  EE is expected to callback the same application after it runs through all other ready file descriptors.  Until all ready EE applications indicate that they don't have anything to process, EE should not be calling ePoll().  To allow EE to know whether to call the application callbacks again,  there should be some protocol.  Each EE application can indicate to the EE while returning from the callback function on whether it processed all events.  EE based on this indication will decide to call the EE application again or not before it goes to the epoll() again.  Note that epoll() is expensive call and hence it is better if all events are processed in fairness fashion before epoll() is called again.   In case of hardware poll based configuration,  this kind of facility is not required as polling is not expensive. Also Multicore SoCs implementing the single portal for all events have fairness capabilities built in.   Since the callback function definition is same for both software and hardware poll based systems,  these parameters exist, but they are not used by hardware poll based systems.

EE before creating threads should initialize itself and then create threads. Once created it should load the shared libraries of its applications one by one.  For each EE application library, it is expected to call 'init' function by getting hold of address of 'init()' symbol.  Init() function is expected to initialize its own module.  Each EE packet processing threads is expected to call another function of EE application. Let us call this symbol name is 'EEAppContextInit()'.   EEAppContextInit function expected to real initialization such as opening UIO and other character device drivers and registering with the software poll() system.

EE also would need to call 'EEAppFinish()' function when the EE is killed.  EEAppFinish does whatever graceful shutdown required for its module.

Each thread, if it is software based poll, does epoll on all the FDs registered so far.  Polling happens in the while() loop.  epoll() can take the timeout argument. Timeout argument must be next lowest timer expiry timeout of all software timer blocks.  When epoll() returns, it should call the software timer library for any timer expiry processing. In case of hardware poll,  specific hardware specific poll function would need to be used.

In addition to above functions,  EE typically needs to emulate other capabilities provided by Linux Kernel for its applications such as - Memory Pool library,  Packet descriptor buffer library,  Mutual exclusion facilities using Futexes and user space RCU  etc.. 

With these above capabilities, EE can jump start the application development. This kind of functionality only requires changes at very few places in the applications.

Hope it helps.

UIO - Acceleration Device mapping in user space

Please see this post on how to use UIO frame work to implement device drivers in user space. As noted in that post,  UIO framework predominantly is used to install the interrupt handler and to wake up the user space process implementing the device driver. Please read the earlier post, before going further.

There are two types of devices that get mapped to user space for zero-copy drivers - Ethernet devices and Accelerator devices such as Crypto Engine,  Pattern Matching Engine etc..   Normally, a given Ethernet device is completely owned by one user process.  But accelerator devices are normally needed across multiple processes and also is needed by kernel applications.  Hence acceleration device usage is more challenging. 

To enable usage of acceleration devices by multiple user processes, acceleration device normally support multiple individual descriptor rings.  I know of some acceleration devices supporting four descriptor rings, with each descriptor ring working independent of each other, that is, one descriptor ring is sufficient for issuing the command and read the result .  In this scenario,  a given user process at least should own one descriptor ring for zero copy driver.  If the acceleration device contains four descriptor rings, then four user processes can use the acceleration device without involving the kernel. Since a typical system contains more processes than the descriptor rings,  it is necessary that at least one descriptor ring is reserved for kernel usage and other application processes.  In the example where one acceleration device supports four descriptor rings,  in one scenario,  one can choose three critical user processes that require zero copy driver. Each of these critical processes use one descriptor ring each. All other user processes and kernel share one descriptor ring.  

Each process requiring zero copy driver should memory map the descriptor ring space.  Since many chip vendors provide Linux kernel drivers for acceleration engines,  my suggestion is to make changes to this acceleration engine driver to provide some additional API functions to detach and attach the descriptor rings on demand basis.  When user process requires a descriptor ring, the associated application kernel module can call the acceleration driver 'detach' function for that descriptor ring.  When the process dies, the associated kernel module should attach back the descriptor ring to the kernel driver. This way, each user process need not work on the initialization of security engine.  It only need to worry about the filling up the descriptors with commands and reading responses.  It also provides the benefit that the descriptor rings can be dynamically allocated and freed based on the applications running at that point of time.

If there are as many interrupts as number of descriptor rings, then each process's zero copy driver can have its own interrupt line.  Yet times, even though there are multiple descriptor rings,  number of interrupts are less than the descriptor rings. In this case, interrupt need to be shared across multiple descriptor rings. Fortunately Linux kernel and UIO frame work provides mechanism for multiple application kernel modules to register different interrupt handlers for the same interrupt line. irq_flags field as part of uio_info structure that is registered with the UIO framework should have IRQ_SHARED bit set.  Linux Kernel and UIO frame work call the interrupt handler one by one in sequence. Interrupt handler that has data pending to be read from corresponding descriptor ring should return IRQ_HANDLED.    It means that the device should have capability to check the pending data without reading it out.  Note that reading the acceleration result should be done by the user space.   When the handler returns IRQ_HANDLED, UIO framework wakes up the user process.  Since one IRQ line is shared by multiple processes,  as described in earlier post, masking and unmasking the interrupts can't be done by the interrupt handler and user process. Since interrupts can't be disabled, one can't use natural coalescing capability as described in the earlier post.  But fortunately, many acceleration devices provide hardware interrupt coalescing capability. Hardware can be programmed to generate interrupt for X number of events or within Y amount of time. If the hardware device you have chosen does not have the coalescing capability and require IRQ to be shared across multiple user processes, then you are out of luck. Either don't use UIO facilities or live with too many interrupts coming in.

All other user process  without dedicated descriptor rings should work with accelerator kernel driver that is provided by the OS/Chip vendors.  That is, they need to send the command buffer to the kernel driver and read the result from the kernel driver.  Kernel drivers are normally intelligent enough to service multiple consumers and hence many user processes can use the acceleration engine.


Comments?

Multicore Networking applications - Mitigating the Performance bottlenecks

I had given this talk in 2010 Multicore Expo in San Jose.  It was in presentation document in concise form. I voiced the most of the details during my talk.  Many people requested me to provide details in written form.  I tried to give details here in this post.  I hope this post would give enough details on 'New techniques to improve software performance with increasing number of cores'.

Before going further, I would like to differentiate two kinds of applications - Packet processing applications and Stream processing applications.

Packet processing applications in my definition are the ones which  take  packet by packet, work on the packet and send out the same packet or packet with some minor modifications.  In packet processing applications,  there is one-to-one correspondence between input and output packets except for very small number of exceptions. One example where there is no one-to-one correspondence is when there is IP reassembly or fragmentation. Other example is when the packet is dropped by the application. Example applications in this category are:  IP forwarding, L2 Bridging,  Firewall/NAT,  Ipsec and even some portions of IDS/IPS.

Stream processing applications are the ones which may take packets or stream of data,  work on data and send out the data or  send out different packets. Most of  the TCP socket based proxy applications come under this category. Examples:  HTTP Proxy,  SMTP Proxy,  FTP Proxy etc..

This post tries to aid the programmers debugging the software to find out the performance bottlenecks in Multicore networking applications.

Always Ensure to do  flow/Session Parallelization 

Ensure that only one core is processing the session at any given time.  If multiple packets from the same session are being processed by more than one core at the same time,  then there would be requirement to ensure that Mutual exclusion on the session variables.  That would be very expensive.  Multicore SoCs actually aid you to do flow parallelization in packet processing applications.  Many Multicore SoCs support parsing the fields from the packets,  calculate hash on the software defined fields and distribute the packets across the multiple queues based on the hash value.  And then they provide provision for software threads to dequeue the packets from the queues.  These SoCs also provide provision to stop dequeue of packets from threads until the control of the queue is given up explicitly.  This ensures that a given flow is processed by only software thread at any time.

Many Multicore SoCs also have facility to bind the queues to the software threads and each software thread to the core.  If the number of flows are small, there is a possibility of cache being warmed with contexts due to previous packets. This reduces the data movement from DDR.   Also, many Multicore SoCs provide facility to stash the context as part of dequeue operation which reduces the cache thrashing issue even if  binding of the queues to the cores are not done. 

Flow parallelization not only eliminates the need for Mutexes, it also ensures that there is no packet mis-ordering in the flows.

Many stateful packet processing applications require not only flow parallelization, but also session parallelization.  Session typically consists of two flows - Client to Server traffic and Server to Client traffic.  It is possible that two packets from both the flows may be coming to the device and two separate software threads might be processing these packets. Stateful applications share many state variables across these two flows. Due to this, you may require mutual exclusion operation if both the packets are allowed to be processed at the same time.  Session Parallelization as described here would eliminate the need for mutual exclusion.  Unlike flow parallelization, session parallelization is not available in many Multicore SoCs for cases where the tuple values are different in both the flows and hence needs to be done in software.  Packet tuples are different when NAT is applied. Note that many Multicore SoCs enqueue the packet to the same queue if there is no NAT.  They are intelligent enough to generate the same hash value even though the tuples position get changed, that is, source IP in one flow would be destination IP in reverse flow and same is true for destination IP, Source Port and Destination Port.

Stream processing modules such as proxies would need to ensure that both client side and server side sockets are processed by the same software thread to ensure that there is no  Mutual exclusion operations requirement to  protect the sanctity of state variables.  Stream processing modules typically create many software threads - worker threads.  Master thread terminates the client side connections and handover the connection descriptor to one of the less loaded worker threads.  Worker thread is expected to create new connection to the server and do rest of the application processing.  Worker threads are typically implement FSM for processing multiple sessions. More often,  the number of worker threads would be same as number of cores dedicated for that application.  In cases where the threads need to block for some operations such as waiting for accelerator results, then more threads, in multiples of number of cores, would be created to take advantage of full power of accelerators.

Eliminate the Mutual Exclusion Operation while Searching for Session/Flow Context

This technique is also expected to ensure that there are no mutual exclusion operations in the packet path.  Any networking application do some search operations on the data structures to figure out the operations and other action to be done on the packet/data.  Upon the incoming packet/data,  search is done to get hold of session/flow context and then further packet processing happens based on the state variables in the session.  For example,  IP routing does search on the routing table to figure out the destination port, PMTU and other information for operations such as fragmentation, TTL decrement and packet transmit.  Similarly firewall/IPsec packet processing applications maintain the sessions in a easy to search data structures such as RB trees, hash lists etc..   Since the sessions are created or removed dynamically from these structures, it is necessary to protect the data structure while doing operations such as add/delete/search.  Mutual exclusion operations using spinlock,  futex, up/down are one way to do this.   RCU (Read-Copy-Update) is another method that can be used which eliminates the Mutex operation during search.   RCU operation is described in earlier post.  Please check that here and here.  RCU lock/unlock operations in many operating systems is very simple operation. Note that Mutex operations are still required for add/delete even in RCU based usage.

Eliminate Reference Counting 

One of the other bottlenecks in the Multicore programming is the need to keep the session safe from deletion while it is being used by other software threads. Traditionally this is achieved by doing 'reference counting'. Reference counting is used in two cases - During packet processing operation or  When neighbor module store the reference.

In the first case, reference count of the session context is incremented as part of the session lookup operation.  During packet processing, the session is referred many times to get hold of state variable values and to set the new values in the state variables of the session.  It is expected that if the session is deleted, it should not be freed until the current thread is done with its operation. Otherwise, it would corrupt some other memory if the session memory is freed and allocated to somebody else during packet processing.  To ensure that the session ownership is not given away, the reference count is checked as part of 'delete operation'.  If is is not zero, then the session is marked for deletion, but not freed until the reference count becomes zero.  If the value is zero, it indicates there is no reference to this session and the session gets freed. 
 
Since RCU operation postpones the delete operation until current processing cycles of all other threads,  reference counting becomes redundant.  Elimination of reference count not only helps in improving the performance, but also reduces the maintenance complexity. Note that reference counting operation requires atomic usage of count variable. Atomic operations are not inexpensive.

Second use case of reference count is when the neighbor modules store the reference (pointer) to the sessions in their session contexts. By eliminating the storage of pointer,  reference count usage can be eliminated.  This post helps you understand how this can be done.

Linux user space programs also can take advantage of RCUs. See this post for more details.

Use the Cache Effectively

Once the matching session is found upon incoming data/packet,  processing functionality uses many variables in the session. If these variables are together in a cache line,  any cache fill due to access of one variable result all other variable in the cache line available in the cache.  That is, Access to other variables will not result in going to DDR.  But all variables may not fill in one cache line. In those cases, it is necessary to group the related variables together to reduce going to DDR.

To effectively use instruction cache, always arrange your code with likely/unlikely compiler directives. Compilers will try to arrange the likely() code together. 

Reduce Cache Thrashing due to Statistics variables

Almost all networking applications update statistics variables.  Some variables are global and some of them are session context specific variables.  There are two types of statistics variables -  increment variables and add variables. Increment variables are typically used to maintain the count of packets.  Add variables are used to maintain the byte count.  Updating these variables require getting hold of current values and then add or increment operation.   If these variables are updated by multiple threads (with each thread running on a specific core), then every time an variable is updated,  cache information of this variable is no longer valid in other cores.  When one of other cores needs to do same operations,  it needs to get the current value first from the DDR and apply the operation.  In worst case scenario, where packets are going to round robin fashion to different software threads (hence cores), then the cache thrashing due to statistics variables would be very high and this would reduce the performance dramatically.

Always use 'per core/thread statistics counters'  whenever possible.  Please see this post for more details. 

Some Multicore SoCs provide special feature which also eliminates the need for 'per core' statistics maintenance.  These SoCs provide facility to allocate memory block for statistics.  These SoCs provide facility to fire the operation and forget about it.  Firing the operation involves the operation type (increment, decrement, add X or sub Y etc..) and memory address (32 bit or 64 bit).  SoCs internally do this operation without cache thrashing.  I suggest strongly to use this feature, if it is available in your SoC.

Use LRO/GRO facilities

Many networking applications' performance depends on the number of packets being processed than the number of bytes processed.  Examples: IP Forwarding,  Firewall/NAT and Ipsec with hardware acceleration.  So, reducing the number of packets processed becomes key in improving the performance.

LRO/GRO facilities provided by operating system in Ethernet drivers or by Multicore SoCs reduce the number of TCP packets, if multiple packets from the same TCP flow are pending to be processed.  Since TCP is byte oriented stream protocol, it does not matter whether or not the processing happens on packets.  Please see this post for more information on LRO feature in Linux operating system.  If it is supported by your operating system or Multcore SoC, always make use of it.

Process Multiple Packets together


Each packet processing module does set of operations on the packets/data - such as Search,  Process and  Pkt out.  If the packet is going through multiple modules, there are many C functions get called.  Each invocation of C function has its own overhead such as pushing the variables in the stack, initializing some local variables etc..    By bunching multiple packets of same flow together can reduce search/pkt out overhead and overhead associated with the C functions.


Some Multicore SoCs provide facility to coalesce packets together on per queue basis with coalescing parameters -  Packet threshold and time threshold.  Queue does not let the target thread to dequeue until one of the conditions reached - either number of packets in the queue exceed the packet threshold parameter or if no packet was dequeued for time 'time threshold'.   If this facility is available, ensure that your software dequeues multiple packets together and processes them together. 

Yet times, there is no one-to-one correspondence between queues and sessions.  In that case, one might ask that search overhead can't be reduced as there is no guarantee that the packets in the same queue belong to the same session.  Though it is correct, it might still have some improvements due to cache warming if there are more than one packet belonging to same session in the bunch.

As a software developer,  it would be required to strive for one-to-one correspondence between queues and sessions. This can be done easily among the modules running in software.  Some Multicore SoCs provide queues for not only to access hardware blocks, but also for inter-module communication.  Software can take advantage of this to create one-to-one mapping between queues and destination module's sessions.

It is true that when the packets are being read from the Ethernet controllers, there is no way to ensure that a queue only holds packets of one session as the queue selection happens based on the hash value of packet fields.  Two different sessions may fall into same queue.  In those cases,  as mentioned above you might not see improvement from 'serach' functionality, but you would still see improvements due to less number of invocations of C functions.

Many Multicore SoCs also have functionality to take multiple packets together for acceleration and for sending the packets out. This also will reduce the number of invocation to acceleration functions and for sending packets out.  If this facility is available in your Multicore SoCs,  take advantage of it. 

Eliminate usage of software queues

Some Multicore applications need to send the packets/data/control-data to other modules.  If multiple threads send the data to the queue, then there is a need for mutual exclusion to protect these data structure queues.

Many Multicore SoCs provide queues for software usage.  These queues would eliminate the need for software queues and hence eliminate the mutual exclusion problem, there by improving performance.   Some Multicore SoCs also provide facility to group multiple queues together into a queue group which allows sending and receiving applications to enqueue priority items and dequeue based on priority.  These queues can be used even among different processes or virtual machines as long as shared memory is used for items that get enqueued and dequeued.  Some Multicore SoCs even went a step further to provide 'copy' feature which avoids shared memory and there by providing good isolation. This feature makes a copy of these items from source process to internal managed memory by Multicore SoCs and copy to the destination process memory as part of dequeue operation.

Always use this feature if it is available in your Multicore SoC.

Eliminate the usage of Software Free pools 

Networking applications use free pools of memory blocks for memory management.  These free pools are used to allocate/free session contexts, buffers etc..   Many software threads would require these facilities at different times. Software typically maintains the memory pools on per core basis to avoid mutual exclusion operations on per allocation basis.  Since there is a possibility of asymmetric usage of pools by different threads, yet times there is a possibility of memory allocation failures even though there are free memory blocks in other threads' pools.   To avoid this, software does complex operations during these scenarios of moving memory blocks from one pool to another through global queues.   Many Multicore SoCs provide 'free pool' functionality in hardware.  Allocation and free can be done by any thread at any time without mutual exclusion operations. Use this facility whenever it is available.  It saves some core cycles.  More than that is provides efficient usage of memory blocks.

Use Multicore SoC acceleration features to improve performance

There are many acceleration features that are available in Multicore SoCs.  Try to take advantage of them.  I classify acceleration functions in Multicore SoCs into three buckets -  Ingress In-flow acceleration,  In-flight acceleration and Egress in-flow acceleration.

Ingress In-flow acceleration:  Acceleration functions that are done by Multicore SoCs in the hardware on the packets before they are handed over to software are called Ingress In-flow accelerations.  Some of the features, I am aware, in Multicore SoCs are:

• Parsing of Packet fields :  Some Multicore SoCs parse the headers and make those fields available to the software along with the packet.  Software needing the fields can eliminate the parsing of fields.   These SoCs also provide facility for software to choose the fields to be made available along with the packet.  They also provide facilities for software to create parser to extract fields from proprietary headers or from non pre-defined headers.  Try to take advantage of this feature.
• Distribution of packets across threads:  This is basic feature required in Multicore environments.  Packets needs to be distributed to different software threads.  Many Multicore SoCs also ensure that packets belonging to one flow go to one software thread at any time to ensure that packets will not get mis-ordered within a flow.  As described above,  multiple queues would be used by hardware to place the packets.  Selection of queue is based on hash value calculated on the set of software programmable fields.  As a software developer, take advantage of this feature rather than implementing the distribution in software.
• Packet Integrity checks & Processing offloads:  Many Multicore SoCs do quite a bit of integrity checks on the packet as  listed below.  Ensure that your software don't do them again to save some core cycles.
• IP Checksum verification.
• TCP, UDP checksum verification.
• Ensuring that the headers are there in full.
• Ensure that size of packet is not less than the size indicated in the headers.
• Invalid field values.
• IPsec inbound processing.
• Reassembly of fragments
• LRO/GRO as described above.
• Packet coalescing as described above.
• Many more.
• Policing :  This feature can police the traffic and reduce the amount of traffic that is seen by the software.  If your software requires policing of some particular traffic to stop cores from getting overwhelmed, this feature can be used rather than doing it in the lowest layers of software.
• Congestion Management :  This feature ensures that the number of buffers used up by the hardware won't go up exponentially. Without this feature, cores may not find buffers to send out the packets if all buffers are used up by the receiving hardware. This situation typically happens when the core is doing lot of processing and hence slow in dequeuing while lot more packets are coming in.  Many Multicore SoCs also have facility to generate pause frames in case of congestion. 

Egress In-flow acceleration:   Acceleration functions that are done in the hardware once the packets are handed over to it by software to send the packets out are called Egress in-flow acceleration functions.  Some of the Egress in-flow acceleration functions are given below.  If these are available, take advantage of them in your software as these can reduce significant number of cycles in the core.

• Shaping and Scheduling :  High priority packets are sent out within the shaped bandwidth.  Many Multicore SoCs provide facilities to program the effective bandwidth. These SoCs shape the traffic with this bandwidth. Packets which are queued to it by software would be scheduled based on the priority of the packets.  Some SoCs even provide multiple scheduling algorithms and provide facility for software to choose the algorithm on per physical or logical port.  Some SoCs even provide hierarchical scheduling and shaping.  Take advantage of this in your software if you require shaping and scheduling of the traffic.
• Checksum Generation for IP and TCP/UDP transport packets :  Checksum generation, especially for locally generated TCP and UDP packets is very expensive.   Use the facilities provided by hardware.  
• Ipsec Outbound processing :  Some Multicore SoCs provide this functionality in hardware.  If you require Ipsec processing,  use this facility to save large number of cycles on per packet basis.
• TCP Segmentation and IP Fragmentation :  Some Multicore SoCs provide this functionality.  TCP segmentation performs well for local generated packets. Use this functionality to get best out of your Multicore.

In-flight Acceleration :   Acceleration functions provided by hardware that can be used during packet processing are called In-flight acceleration functions.  Crypto,  Crypto with protocol offload,  Pattern Matching,  XML acceleration are some of the acceleration functions that come in this category.  Here the packet/data for acceleration is handed over to the hardware acceleration functions by software. Software reads the results at later time when the results are ready.  Take advantage of these feature in your software wherever they are available . Some Multicore SoCs differentiate themselves by doing lot more in the acceleration functions.  For example,  some Multicore SoCs do protocol offload along with crypto such as Ipsec ESP,  SSL record layer protocol , SRTP and MACSec offloads which do beyond crypto offload.

I see many times people asking me a question on how to use the acceleration functions.  I had detailed this long time back here. Please see the details there and there.

Software Directed Ingress In-flow accelerations:

As described before, Ingress in-flow acceleration is applied before the packets are given to the software. Packets that are received on integrated Etherent controllers go through this acceleration.  But many times this acceleration is required from software too.  Take the example of Ipsec, SSL or any tunneling protocol.  Once the software processes these packets, that is once it gets hold of inner packets,  software would like ingress in-flow acceleration to be applied on the inner packets for distribution across cores and other acceleration functions.  To facilitate these kinds of scenarios, some Multicore SoCs provide concept of 'offline port' which allows software to reserve the offline ports and send the traffic for ingress in-flow acceleration.  Some software features that can take advantage of this feature are:

• Tunneled traffic as described above to let the inner packets to go through the ingress in-flow acceleration,
• IP reassembled traffic - Once the fragments are reassembled, it would have all 5-tuples which can be used to distribute the traffic through offline port.
• L2 encapsulated packets - Such as IP packet from PPP, FR etc..
• Ethernet controllers on PCI and Traffic from Wireless interfaces :  Here the traffic might need to be read by the software and Ingress in-flow acceleration might not have been implemented for these features. Software after getting hold of packets can be directed to in-flow acceleration functions through offline ports.

Use Multicore core features wherever they are available

Multicore SoCs from different vendors have different core architecture. Some Multicore SoCs are based on power pc, some based on MIPS core and Intel Multicore is based on x86 processors. Multicore SoC vendors provide different features to improve performance of Multicore applications.  Whenever they are available, software should make use of them to get the best performance out of cores.  Some of the features that I am aware of are listed below.

Single Instruction & Multiple Data instructions (SIMD)

Multicore SoCs from Freescale and Intel have this block in their cores.   This feature in the cores allows software do a given operation on the multiple data elements.  This kind of parallelism is called 'Data level parallelism'.  'Add' operation in typical cores is performance either on 32 bit or at the most 64 bit operands.  Current generation of SIMD do this operation on 128 bit operands. They also provide flexibility to do multiple 16 bit, 32 bit add operations on different parts of data simultaneously.  SIMD greatly helps in operations which involve arithmetic, bit, copy, compare operations on large amount of data.  Any operation that is done in a loop can be accelerated using SIMD.   In networking world,  SIMD is helpful in following cases:

• Memory compare, copy,  clear operations.
• String compare, copy, tokenization and other string operations.
• WFQ scheduling of QoS, where multiple queues need to be checked to figure out which queues need to be scheduled based on sequence number property of queues.  If the sequence numbers are arranged in array form, then SIMD can be used very effectively.
• Crypto operations.
• Big Number arithmetic which is useful in RSA, DSA and DH operations.
• XML Parsing and schema validations.
• Search algorithms -  Accelerating compare operation to find matching entry from collision elements in a hash list.
• Check-sum verification and generation:  In some cases Ingress and Egress In-flow accelerations can't be used to verify and generate the checksums.  One example is,  TCP and UDP packets that come in IPsec tunnel.   Since the packets are in encrypted form,  ingress and egress accelerators will not be able to verify and generate checksums in inner packets.  Even packets that get encapsulated in tunnels will not be able to take advantage of Ingress & Egress in-flow accelerations.  Checksum verifications and generations need to be done in software by cores.  SIMD would help in those cases tremendously.
• CRC verification and generation:  These algorithms are not very expensive to have In-flight acceleration and not inexpensive for core to do.  SIMD in these cases help as it does not involve any architecture changes to the software and still get lot better performance over the cores which don't have SIMD.

Normally SIMD based cores give at least 50% more performance improvement for typical workloads.  So, as a software developer, figure out the ones that can be improved using SIMD and modify the code to improve performance of your application.

Speculative Hardware Data Prefetching & Software Directed Prefetching

This feature fetches the next cache line worth of data from the current memory access in the hopes that software would use next memory line.  Many core technologies provide control on enabling and disabling this at run time.  Software can take advantage of this while doing memory copy, set and compare operations.  Any data is arranged in linear fashion in the memory (such as arrays) can get good boost of performance with this feature. Note that, if this feature is not used selectively and carefully, it might even give degradation in performance. Be careful in using this feature.

Many cores also provide special instruction to warm the cache given a memory address. Software developers know the kind of processing (next module) and many times next module session context is also known. In those cases, software can be developed such a way that next module session is prefetched while packet processing happens in current module.  When the next module gets the control of the packet, it already has session context in the cache which avoids getting it DDR in serial fashion.  My experience is that using software directed prefetching gives very good results.  This also ensures that the performance does not go down even with large number of sessions.

Some Multicore SoCs provide support for Cache warming on the incoming packets.  As part of making packets ready for the software, these SoCs warm the cache with some part of packet content,  annotation data containing parsed fields and software issued context data.   When the software dequeues the packet, most of the information required to process the packet of the module that is getting hold of packet is in place in the cache, thereby, avoiding on-demand DDR access.  Software can program its context on per queue basis.  Note that, this feature is useful for the first module that receives the packet.  Actually that is good enough as this module can prefetch the next module context while the packet is being processed in the current module.  As long as each modules does this, there is no performance degradation even with high capacity. 

As described before,  hardware queues may not have one-to-one correspondence with the receiving module session contexts.  A queue might be having packets for multiple session contexts. Many times, software maintains the sessions in the hash table with large number of hash buckets.  All collision sessions are arranged in linked list or RB tree.  Software can ensure that there are as many queues as number of hash buckets and program the first collision element in the queue.  If the matching context is not same as the one that was programmed, then one might not get the full benefit of cache warming by the hardware. But if there are 4 collision elements and the traffic across these four are same, cache warming would come in handy 25% of the time. Some software developers might even store the collision elements in an array and program the array to the queue.

Software directed prefetch works very well as long as there is one-to-one correspondence between current module session context and next module session context.  In this case,  current module session context can cache the reference to the next module session context and use this to do prefetch operation.  This scheme also work fine if next module context is super set of multiple current module contexts.  But it does not work well if the next module context is finer granular.  Example:  Ipsec SA transfer packets from  multiple firewall/NAT sessions.  In this case, 'Software Directed Ingress In-flow acceleration' method can be used to direct the hardware to send the packet to next module.  This method not only provides cache warming, but also distributes the processing to multiple cores.


Hardware Page Table walk:

Some cores provide nested hardware page table walk to find out the physical address given the virtual address.  This is really useful for user space applications in Linux kind of operating systems.  Hardware page table walk feature is expected to be taken care by operating system vendors.  But unfortunately many OS vendors are not taking advantage of this feature.  As a software developer, if your Multicore SoC provide this feature, don't forget to ask your OS vendors to take advantage of this.  This will ensure that your performance does not go down when you move your application from Bare-metal environment (where the TLB are fixed and there is no page walk required) to Linux user space.

I hope it helps.

User space IO - Some Challenges & Mitigations

There is pretty good information about UIO in Internet.  This link provides good introduction to this subject.

What is UIO (User space I/O) framework?

UIO framework is part of Linux kernel to enable device driver development in user space.


Which applications require User space drivers?

Zero-Copy drivers are  becoming necessary for performance reasons.  Many network packet processing applications are traditionally used to be developed in Linux kernel space.  Firewall, NAT, IPsec are some of the examples which you find in the kernel space.  Increasingly,  these applications are moved to the user space for multiple reasons such as - Availability of large memory space,   Easy-to-debug,  faster image upgrade and restart and many more.    Moving these applications without moving the Ethernet driver or acceleration drivers reduces the performance.  Even though there are some efficient mechanisms to transfer packets between kernel and user space, they  still take some core cycles.  Having access to the hardware from the user space eliminates the need for any mechanisms to transfer packets back and forth between user space and kernel space. UIO frame work allows user space applications to own the device.  UIO frame work does this by letting the application kernel driver to map the hardware IO to the user space process.  UIO frame work also allows the application kernel driver to register interrupt handler with hardware IRQ and wake up the user space daemon upon hardware interrupt.  User space application upon getting indication from the UIO frame work,  reads the packets or acceleration results from the hardware memory directly without involving kernel.


What are components involved in UIO?

UIO frame work is part of Kernel itself.  Application developers need to develop one simple kernel module and user space application.   Kernel module as indicated above is expected to register interrupt handler with the UIO framework and also indicate the memory ranges (address, size pairs) to the UIO framework.  User space application open the appropriate UIO device /dev/uioX  (X being the minor number),  get hold of memory map ranges from 'sysfs' file system, do memory map and wait for the interrupt events either using 'read' or 'ePoll()' system calls.  When the read/ePoll returns,  it can read the content from the memory mapped area and do the actual application processing on the packets.

API exposed by UIO framework for application kernel modules:

uio_register_device(struct device *parent,  struct uio_info *info)

This function is expected to be called by the application kernel module.  'info' to be filled up with the right values.   At the end of this function,  UIO frame work creates the device /dev/uioX where X is dynamically assigned minor number.  This is the device which is expected to be opened by the user space program to read the interrupt events.

struct uio_info {
    const char        *name;
    const char        *version;
    struct uio_mem        mem[MAX_UIO_MAPS];
    struct uio_port        port[MAX_UIO_PORT_REGIONS];
    long            irq;
    unsigned long        irq_flags;
    struct uio_device *uio_dev;
    irqreturn_t (*handler)(int irq, struct uio_info *dev_info);
    int (*mmap)(struct uio_info *info, struct vm_area_struct *vma);
    int (*open)(struct uio_info *info, struct inode *inode);
    int (*release)(struct uio_info *info, struct inode *inode);
    int (*irqcontrol)(struct uio_info *info, s32 irq_on);
};

name, version:  Application driver can provide any string as part of it.  Since this 'name' field is used by user space application to figure out the device name (/dev/uioX),  it is necessary that the name field is chosen such a way that it is specific to your application and unique across UIO devices.  Note that value X in /dev/uioX is chosen dynamically by the UIO frame work.  X value can be different across restarts of Linux system.  So, if user space application hardcodes the device file in its code, then it could be an issue when the system restarts and different UIO devices register with UIO framework in different order.  'name' is the one which is constant across restarts as it is given by the application driver.  Since the device name is not constant,   user space application, upon its initi8alization, should find out the UIO device name based on the value of 'name'.  UIO frame work creates set of files under /sys/class/uio/ directory. Under /sys/class/uio/, all device names are present. As many sub directories as number UIO files are present in /sys/class/uio. If there are two UIO files, then there would be two sub directories -  /sys/class/uio/uio0/,  /sys/class/uio/uio1/. Under each uioX directory, there are set of files -  'name', 'version', 'event' and set of directories - 'maps' and 'device'.   'name' file contains name of the device given by the application driver in the first line.  'version' file contains the version string given by the application driver.   'events' contains the number of times the interrupt service routine called so far.

User space application software is expected to find out the right device name by scanning through the directory entries (using scandir()) in /sys/class/uio/ directory.  For each directory entry, it needs to open the file 'name', read the first line and check the name.  If it matches with the name the application is looking for, then note down the directory entry that has matching entry - uioX.  Use this to form /dev/uioX string to open the UIO device.  FD returned by opening the device can be used to read the interrupt events.  This FD can be kept even in epoll(). This is useful if your application requires to wait for event from multiple file descriptors.

struct uio_mem mem[MAX_UIO_MAPS]:   If your application requires to map the register space of hardware in your user space application, then application kernel driver is expected to fill this up.  Since there could be multiple memory ranges required to access the hardware and hence there is array of mappings,  UIO provides facility to give multiple memory ranges. 

struct uio_mem {

    const char *name;

    unsigned long addr;

    unsigned long size;

    int memtype;

    void  __iomem *internal_addr;

   ...

}

It is expected that application kernel driver fills up the array of memory ranges using above structure during registration time. User space application is expected to read memory ranges from the /sys/class/uio/uioX/maps/ directory and do the memory mapping using mmap().  If application kernel driver fills up four memory addresses, then there would be four sub directories  under /sys/class/uio/uioX/maps/ -  map0, map1, map2, map3 and map4.   Under each 'mapX' sub directory, there are three  files - name, addr,  and size.   'addr' file contains address and 'size' file contains 'size'.  See below for explanation.   User space application is expected to read all paris of 'addr' and 'size' and use mmap() function to map them  to its virtual space.   Some explanation of fileds of uio_mem before going into further details.

• addr:  It could be physical,  logical or virtual memory. Mostly it would be physical address as hardware device memory is exposed here.
• size:  Size of the memory that needs to be exposed to the user space.
• name :  Name given to each memory range.  
• internal_addr:  This is not meant for user space programs to do anything.  Kernel driver can initialize this for its own usage at later time by interrupt service routine or irqcontrol function.  Typically, this memory is mapped using ioremap().

One thing note is that the memory mapping is always with respect to page boundary.  Very often, the device memory does not start at the page boundary. Hence it is required that the user space application adds the right offset to the return address of mmap() to point to the right locations in the device.  User space application is expected to keep the 'offset' parameter for each memory range using 'name'.

mmap() function takes one parameter 'offset' (note that this offset is nothing to do with offset explained above).  This offset is normally given in the multiples of page size.  This offset field is used by UIO frame work to determine the the memory range that user space programs intends to map.  Note that Linux IO infrastructure allows UIO framework to have only one corresponding mmap() function. Whenever mmap() is called in user space,  mmap() function of UIO framework in kernel is called.  UIO mmap() function internally calls remap_pfn_range() function to map the memory.  Note that there is only one mmap() function. How does UIO know which memory range to use to map?  TO solve this issue, UIO expects the user space programs to pass offset which is N * getpagesize() where N being the memory map index.   UIO internally gets hold of memory map index from the offset field and use corresponding 'addr' and 'size' values.

irq:  If your hardware device requires to interrupt the user process, then the application kernel driver is expected to register the IRQ number with the UIO frame work.  If the hardware device does not have this facility or interrupt is not required, then '0' need to be passed to it.  UIO frame work also provides an API function ' uio_notify_event()' to wakeup the user process. This can be used by timer or other facilities to wake up the user space process if the hardware device does not support interrupts.

irq_flags: Kernel driver is expected pass these flags. These flags would be given to request_irq() function by the UIO framework.  Typically,  IRQ_SHARED flag is sent if the IRQ is shared across more than one hardware device.

uio_dev:   This is filled up by the UIO framework.  UIO frame work puts the its own private information in there.  For every registration, UIO frame work creates an instance of uio_dev and keeps it in there. It is not expected to be interpreted by application kernel driver. Any further calls to the UIO framework from the application kernel driver is expected to pass uio_info. UIO frame works gets its instance from the uio_info->uio_dev and use the information in there to do its processing.

irqreturn_t (*handler)(int irq, struct uio_info *dev_info):   This is main interrupt handler.  It is expected to be provided by the application kernel driver.   Application kernel driver implements the interrupt service routine as required by the device. Waking up the user process is taken care by the UIO frame work itself.  UIO framework sets its own function as interrupt handler while calling request_irq() function.  That is, when there is an interrupt,  UIO framework gets the control first.  It calls the application driver handler function and then it does whatever is necessary to wake up the user process.  Hence the application driver handler does not worry about waking up the user process.  More often, my observation is that the application driver interrupt handler function does not do much.  Mostly, it just disables any interrupt generation by programming the device registers.  What should be done in the application driver handler depends on the hardware device capabilities.

•  Hardware devices typically have capability for software to mask/unmask interrupt generation.  They also provide ability for software to indicate to the hardware to generate interrupts only for new events by acknowledging the previous events. and hardware devices generate interrupt, if new packets have come in , when interrupt is enabled.   If hardware has these capabilities , then the kernel handler typically disables the interrupt generation.  User space process upon being woken up,  indicates to the hardware to generate interrupts only for new events from now onward,   reads all device events in a loop (packets, results etc..) and then enables the interrupt.  This method automatically provides coalescing capability.  User space process is woken up upon first event and interrupts are disabled by the kernel handler. By the time, user space process woken up, it processes not only the event that had woken this up, but also any other events that have come after that.  
• Note that the user space process or thread may be processing packets from multiple UIO devices.  In this case,  if the  user process processes all the packets coming from one device in a loop until all events are read, then there is a chance that packets from other devices are not handled in timely fashion.  It is expected that all devices are given fair chance.   One way to take care of this is to have one thread each for devices. But that may not be efficient.  It appears that the performance is best if the number of packet processing threads are equal to number of cores/HW threads.  There could be more devices than the threads.  Due to efficiency reasons, one thread may need to work with multiple devices.  In these cases, to give the fairness across devices,  it is necessary that thread handles only 'quota' number of packets from each device before revisiting the devices again.  This concept is similar to NAPI model adopted in Linux Ethernet drivers.
•  

 int (*irqcontrol)(struct uio_info *info, s32 irq_on) :  This function pointer is filled up by application kernel driver to allow user space process to explicitly enable/disable interrupt generation by the hardware device.  This function gets called by UIO infrastructure when the user space process calls write() function on the UIO device fd.  Normally, irq handler disables interrupt generation and user space process enables interrupts using mapped memory. Some hardware devices might have race conditions if two contexts update interrupt mask related registers. This can happen when the mask register is used for other purposes.  In these cases,  central control of enable and disable is necessary.  But modern hardware devices don't have this issue and hence this function registration is not required.

 int (*mmap)(struct uio_info *info, struct vm_area_struct *vma) :  In usual cases, application kernel driver need not set this pointer.  UIO infrastructure has its own mmap() function defined which can do the memory mapping when user space calls mmap() function.  UIO Infrastructure itself can do the mapping using uio_mem mapping array.  Yet times, the number of entries needed to map could be more tham MAX_UIO_MAPS. In that case,  UIO infrastructure will not be able to do the mapping.  In this case, application kernel driver will need to provide mmap() function pointer and do the mapping necessary.  

Even though UIO framework provides  application kernel driver to indicate the memory ranges to map or register application specific mmap() function pointer,  more often I see that both of them are not used.  UIO framework predominantly used only for registering the interrupt handler to wake up the application user process. Many times, application kernel driver itself made as character devices driver with its ioctl() and mmap() functions in addition to open(), close().    There are multiple reasons for doing this. One of  the reason is given below.

• Applications not only require to map the device specific memory locations, but also map the kernel memory for packet/acceleration-result buffers. UIO infrastructure does not provide this.  Ethernet hardware devices are typically expose descriptor rings of descriptors to receive packets.  Application is expected to provide buffer in each descriptor.  Ethernet controller fills up the buffer in the descriptors with incoming packets.  Buffers that are to be given to the Ethernet controller must be physical addresses. Current generation of Multicore SoCs don't have capability to convert from virtual space to physical space internally.  Hence physical addresses need to be provided for buffers that go in receive descriptors.  Since Linux user space does not have physical memory with it, it needs to get this memory from the kernel space.  Application kernel driver does this job.   User space program asks the kernel driver to allocate and map the memory to user space.  When the mmap() in  user space returns, it has the virtual address.  It gets the physical address of allocated buffer from the kernel driver and uses the physical address while programming the hardware and uses virtual space while using it in its program.  User space programs typically ask kernel driver to allocate big amount of memory and then asks that memory to be mapped. Packet buffers are allocation/free is done from  this big chunk.   

Applications may require big chunks of memory blocks for several reasons - packet buffers, acceleration results and even for local contexts.   But there is only one mmap() function and there are no special arguments by which user process indicates the purpose to the application driver.  Hence, it is necessary that there is some kind of protocol between user space process and the kernel driver.  One method that is typically followed is to indicate the purpose via one IOCTL command, then do mmap() and another IOCTL command to know the base address of allocated memory.  Let us say that there are two different memory chunks to be allocated - Chunk1 of size 128Kbyets for packets   and Chunk 2 for acceleration results of size 64K.  Then the sequence by which user space calls the kernel driver through FD are:

ioctl(fd,  SET_PURPOSE,  argument consisting of  type 'CHUNK1',  size '128K')
mmap()
ioctl(fd,  GET_MMAP_RESULT, argument consisting of 'physical address').

Similar sequence need to be followed whenever Chunk2 is required.

Kernel Driver need to keep the information given via SET_PURPOSE in its private information. When kernel driver mmap() function gets invoked, then it allocates memory using  kmalloc(),  calls remap_pfn_range.  It stores the address returns by kmalloc() in private information.  This is given back to user space when GET_MMAP_RESULT command is issued by user space.  All these three operations need to happen atomically.  Kernel driver may like to ensure the sequence and return error if new sequence is started before old sequence is completed.

 int (*open)(struct uio_info *info, struct inode *inode),  int (*release)(struct uio_info *info, struct inode *inode) :   These function pointers are can be set by application kernel driver to get hold of control whenever user space applications open or close the UIO device. It can do any cleanup necessary. 

Example Program



  

Performance considerations in Proxy based nework applications

Many details on performance considerations on proxy based networking applications are given here. 


There are some more performance considerations in developing proxy based applications. Here they are:

• Use Hugelbfs system to for running code and for application context memory (for connections):  Please see this for getting understanding of this technique.
• Use User space RCU wherever possible:  See the RCU related information here.
• Use Futexes as part of RCU implementation for add/delete operations.  See about Futexes here. 
• Use posix spinlock kind of Mutexes only for small portion of the code.
• Use UIO based Interrupt indication to the User space processes while dealing with memory mapped hardware accelerators.

Hash Tables versus Balanced Binary trees - Hybrid model

Hash tables are most commonly used in network infrastructure components.  Firewall/NAT sessions, IPsec SAs and routing cache entries are some of the examples where hash tables are used to store them.

In many of the packet processing applications,  there are three operations -
'Session Creation',  'Session Deletion' and 'Session Search'.  Session Creation and Deletion performance affects the session rate where as session search operation impacts the throughput. That is 'Session find' operation typically happens on per packet basis and 'Session creation/deletion' happens for each connection.  Both the metrics - connection rate and throughput - are important.  Any data structure selected should take care of these two important metrics.  Also, any data structure selected should also perform well in Multicore environment.  Fields used to search for the session depends on the application.  5-tuples of the packet is used in case of firewall/NAT/TCP/UDP,  SIP, DIP, DSCP fields are used in case of forwarding application and DIP and SPI are used in case of IPsec.

Many implementations used to use hash tables for arranging the sessions.  Hash algorithms vary from simple rotation & XOR operations, Bob-jenkins to CRC-32/64.  Few bits of the output of algorithm is used to index into the hash table.  Collision entries are normally arranged in double linked list form.  As part of search operation, collision entries are searched for exact match by comparing all fields that comprise the key.

Problem with the hash table implementations are known for some time. Some of the issues are:

• Number of collision entries has impact on search performance. In some cases, if hash algorithm is bad' or if the type of sessions created at that instance are similar,  it is possible that there are many entries in one hash bucket.  That results to poor performance.
• Hash table attacks are not uncommon.  There are cases where attackers broke the hash algorithm.  Attacker send packets such a way that the device under attack creates large number of collision elements in one hash bucket.  This leads to CPU exhaustion attack whenever packets are sent (by attackers)  whose hash falls to a bucket having large number of entries.
• Some hash implementations try to take care of above problem by resizing the hash table dynamically. Even that can lead to 'CPU exhaustion' attack. 

Hash tables are also has advantages:

• Add/Delete operations are as simple as adding and removing a node from linked list. Session rate performance is typically better - O(1).
• Search operation tends to be good for most normal cases.  Number of buckets per hash table is typically chosen as 1/4 of the number of maximum of sessions. That is, if 1M sessions to be supported by a device, then the hash table size is typically chosen as 256K.  In ideal case, there would not be more than 4 collision entries.  In many cases, it varies from 0 to 16 or so for good hash algorithms.
• Since hash tables use linked lists,  RCU mechanisms can be used.  As we know, read or search operations do not take any CPU cycles.  Due to this, there is no lock overhead in Multicore processors. 

Balanced binary trees (RB trees or AVL trees) are also increasingly used in place of hash tables. They provide consistent performance in both best and worst cases scenarios.  Every time the session is added or deleted, the tree gets balanced.  Search operation is also completed with O(LogN) performance where N being the number of sessions in the tree.  If there are 1M sessions,  at the most 3 nodes are checked.  Addition and deletion operations are also happen within O(LogN).  It would have some  performance degradation with addition and deletion operation, but there is no attack possible.

Balanced binary trees also have one more disadvantage -  It is not Multicore friendly.  RCU can't be used for search operation.  Read spin locks need to be used. This would take some cycles on per search operation.  My observation is that it takes around 200 CPU cycles if there is no contention with writers.  For some packet processing applications such as IP forwarding, Firewall/NAT, IPsec VPN  200 cycles can be huge as the rest of packet processing might happen within 1000 cycles or so.  200 cycles adds to 20% overhead and hence might not be acceptable.

Hybrid model of hash tables and balanced binary tree may be right approach.  This approach is simple.

•  Have hash tables for storing the sessions.
•  By default, each hash bucket is a linked list.
•  if number of entries in the linked list go beyond X elements, then rearrange them in a RB tree for that bucket.  When the number of entries in the linked list go below Y elements and after some XYZ time it can move back to linked list.

This method would get best of both worlds.  In normal work loads, performance would be as good as hash table.  If there is any attack or any fringe cases,  performance degradation is managed with RB tree.


Comments?

epoll - Small tutorial

For a long time, programmers are used to using 'select' and 'poll' calls to wait for events from multiple sockets and file descriptors etc..   Though they served their purpose well,  they are no longer sufficient from scalability and performance perspective.  'Select' mechanism expects all 'fds' to be represented in a three different bit masks (one for read events, one for write and one for exceptions).  'select' call waits until some event happens. Once the 'select' call returns, user program needs to go through all descriptors (basically go through the corresponding bit masks) to identify the actual descriptors which have events ready.    Normally only few descriptors are ready with events.  Going through bit by bit is really wasting CPU cycles. Also, user programs typically require to store some data on per 'FD' basis and expect this data to be passed to it when there is some event on the FD.  'select' mechanism does not provide that facility. 

'poll' mechanism is certainly a big improvement over the 'select' mechanism.  It does not use bit masks, hence there is no limit on number of descriptors to wait on.  Also, along with the FD, user programs can provide 'callback' argument.   But it has similar performance problems as 'select'. That is, every time 'poll' comes out, it needs to figure out which descriptors have events ready by going through all descriptors which were given to 'poll' call.  Though scalability problem is taken care, performance problem still continues to be there.

'epoll' mechanism solves both scalability and performance problems.  It has mechanisms to add descriptors and remove descriptors with descriptor value, not the bit position. It also has facility for user programs to associate its data to the descriptor, which is returned along with descriptor that is ready when 'epoll_wait' returns. More importantly, epoll_wait returns the array of descriptors which has some event ready. Due to this, user programs need not go through complete 'fd' list to figure out ready descriptors.

Usage is also simple. Create a epoll instance using epoll_create.  Add, Delete and Modify descriptors and events they are interested in using epoll_ctl and call epoll_wait to wait for events to occur.  epoll_wait outputs the descriptors which are ready with some events. User program can walk though this ready descriptors to do whatever they need to do.

It provides following API functions.

• int epoll_create(int size):   This function is expected to be called by user thread only once.  'size' parameter was hint for old Linux distributions to allocate memory internally in the kernel.  But this value is no longer used. You can pass any value.
• int epoll_ctl(int epfd,  int op, int fd, struct epoll_event *event) :   This function can be used  to add new descriptor and associated interested events,  delete existing descriptor from the epoll instance and modify the interested events information for the existing descriptor.  User programs can do this on dynamic basis. 
• int epoll_wait(int epfd,  struct epoll_event *events,  int maxevents,  int timeout) :  This function is used by user threads to wait for events on the descriptors which were added to the epoll instance identified by epfd.   This call waits until there is some ready event on any descriptor or until timeout.  'events' would have all ready descriptors when this call returns. 
• Use typical 'close' call on epfd to close the epoll instance. This is typically done when the thread is exiting.

Huge-tlb-fs to improve Linux user space program performance

As I indicated  before, many networking vendors are moving their heavy packet processing applications to user space from kernel space for maintainability of the code, richness of libraries available in user space and GPL concerns of running applications in Kernel space. Typical concern one has in moving their applications to user space is performance.  This write up is one of the techniques that can be followed in reducing performance degradation in moving programs from Kernel space to user space.

Linux kernel space text, data segments are generally fixed and contiguous. Hence TLBs required are less and TLBs are assigned at initialization time.  Unlike kernel programs,  user space applications are divided across multiple processes. Each process runs in virtual memory.  TLBs are used to translate virtual address to physical address of memory.

Number of TLBs in processors are limited.  Hence TLBs are used as cache by Linux.  When there is no TLB entry corresponding to virtual address that is being accessed,  processor frees up one of the TLB entries, searches through the page tables for the mapping between virtual address space and physical address space  and adds this mapping to the freed TLB entry.   Programs with sparse memory address access will have more TLB misses and due to this performance can suffer.  In addition, if page tables are accessed more often,  then the number of times L1 and L2 cache filled up with page tables is also becomes high, there by programs usage of cache can go down, decreasing the performance of applications. This kind of problem is not there in Kernel space programs because of one time mapping of TLB entries for kernel text and data segments. Reduction of TLB misses is the key to improve performance. "hugetlbfs" facility allows TLB entries to map to bigger chunks of memory i.e huge pages.

This facility can be used to map text segment and also to do application memory management.   Linux documentation on this topic and some examples can be found here at:  http://www.kernel.org/doc/Documentation/vm/hugetlbpage.txt.


Above documentation and usage is mainly limited to applications allocating huge page from the kernel space. In addition to applications allocating big  page, it is also necessary that the text segment of the program also makes use of this facility to decrease TLB misses.  Some work was done on this, but it is not yet available in the kernel main line. But patch is available for developers to try this.  Explanation on this technique is provided here http://www.kernel.org/doc/ols/2006/ols2006v2-pages-83-90.pdf  

Patch to the kernel,binutils and Glibc is provided here  http://www.kernel.org/pub/linux/devel/binutils/hugepage/