Not often but sometimes I discover new tools. Today I found ACK:”http://betterthangrep.com/”. There are some nice features:

• exclude git, svn directories
• perl regex
• better highlighting support
• per default 5 lines context
• pattern to exclude searched files

E.g to search the Linux Kernel network subdirectory for TCP SACK code the following command can be used:

ack-grep -CC SACK /usr/src/net-next/net

The CC option specifies that only *.c and *.h files are searched. Under Debian the package the program is called ack-grep.

Sometimes I have to respin a patch-serie to address some new concerns. This time was a little bit more difficult: I first thought the a new feature can be applied on top of HEAD, later I realized that this particular feature should be applied on a previous commit. The workflow with git is really easy:

# save changes in stash stack
git stash

# start to rewrite history
# change the addressed patch to 'edit' 
git rebase --interactive HEAD

# re-apply the changes
git stash pop

# eventually fix merge commits
vim file-to-fix.c
git add file-to-fix.c

# recommit
git commit --amend

# finish rebasing
git rebase --continue

Wow, two new git diff options:

--minimal to spend extra CPU cycles to generate a shorter diff

--function-context to display the whole function that was affected by the change. Nice for reviews by people without the whole context in mind.

The translation lookaside buffer is a high-speed memory page cache for virtual to physical address translation. It follows the local principle to avoid time consuming lookups for recently used pages. But what happened in a virtual environment (e.g. kvm, xen, vmware)? Host mappings are not coherent to the guest and vice versa. Each guest has it’s own address space, the mapping table cannot be re-used in another guest (or host). Therefore first generation VMs like Intel Core 2 (VMX) flush the TLB on each vm-enter (resume) and vm-exit. But flushing the TLB is a show-stopper, it is one of the most critical components in a modern CPU. The relevant code for Linux is located under arch/x86/kvm/x86.c:vcpu_enter_guest().

But Intel engineers started to think about that. Intel Nehalem TLB entries have changed by introducing a Virtual Processor ID. So each TLB entry is tagged with this ID. VPID’s are not specified by the CPU, they are allocated by the hypervisor whereas the host VPID is 0. Starting with Intel Nehalem the TLB must not be flushed. When a process tries to access a mapping where the actual VPID does not match with the TLB entry VPID a standard TLB miss occur. Some Intel numbers show that the latency performance gain is 40% for a VM round trip transition compared to Meron, a Intel Core 2.

Current Kernel (at least e56c57d0d3fdb from net-next) provides no VIDS for nested VM’s. This is no limitation of Intel’s concept (arch/x86/kvm/vmx.c:prepare_vmcs02()). It is rather a proof that nested VMs are not in wide-use and nobody seems to miss that behavior.

@hal:~ $ wget https://fit.nokia.com/lars/papers/2010-imc-hgw-study.pdf                       
--2011-10-27 02:23:29--  https://fit.nokia.com/lars/papers/2010-imc-hgw-study.pdf
Resolving fit.nokia.com (fit.nokia.com)... 2001:708:40:fff1::1, 212.213.221.39, 195.148.124.194
Connecting to fit.nokia.com (fit.nokia.com)|2001:708:40:fff1::1|:443... connected.
ERROR: The certificate of `fit.nokia.com' is not trusted.

I mean not that Nokia has IPv6 connectivity, no I mean why is the default behavior of wget to verify certificates? I thought everybody use wget as a handy download tool and to make some fix bandwidth measurements. (--no-check-certificate do the trick)

Category: unlimited. The ELF spec has no real (artificial) symbol name limitation. It only restricts offsets in string table by 4 bytes. And gcc/gdb are consequent: they also introduce no artificial limitation.

Of course, resolving dynamic linked object requires hashing and strcmp’ing these symbol names. Especially larger projects with lots of symbols will suffer from this (you may notice this for C++ symbols because of namespace bloat).

The last two days I programmed an system with n input channels and n output channels. The system multiplex the input packet to the actual output channel, depending on packet IP destination address (and do some packet mangling, but this does not matter here). But the output channel can block (the socket returns EAGAIN, e.g. if TCP peer close the window). Each received packet is enqueued in the input queue. If the output channel is blocked then the input queue is stalled, no new packet can be transmitted, although the packet is indent for another output queue – this is bad.

The problem is also typical for switches: multiple input, multiple output and sometime the destination is the same output, thus buffering is required. The following image illustrate the layout of a Cisco Catalyst 6500. Catalyst do NOT suffer from HOL blocking because buffering is handled in egress queues – which is superior solution if the multiplex process is fast enough and do not consume to much cycles.

The idea to use a input queue was performance driven. At line rate – when CPU processing is at 100% load – I don’t wanted to spend the cycles in packet processing if later on the packet is dropped with a high probability. So from a performance point of view I don’t want to drop the design. But the performance issues that arise from the HOL blocking are much more relevant. So I started to look for workaraounds. The following papers look quit interesting:

RFIFO: Retreat FIFOs for the Head-of-Line Blocking problem

Head of Line blocking prevention technique based on multiple input queues per priority

Some thoughts about recent activity here at TCPM and some other places.

Since several years vendors and web companies try to address web performance problems by adjusting TCP. Congestion control, slow start (IW10), timeouts and the like are addressed like a function of time: IW10 seems adequate for 2011, IW15 for 2013, IW20 for 2016 and so on. Timeouts are adjusted to current “consumer” networks. But the actual network characteristic is hardly a function of date, it is a function of the effective link characteristic between two endpoints in a packet switched networks with no a priori bandwidth guarantee. X.25, multi-hop sensor networks and low bandwidth radio links are _still employed_. Links with just a BDP of a few thousands byte per second, links cope a few packets in flight and with a large intrinsic jitter.

IW10, IW14, IWx are proposed to speed things up. Don’t get me wrong: I am generally ok with IW10 – I believe that the (potential) negative impact is manageable, overshooting the link is unlikely. I believe that this window is in a lower range of noise so that a flow – and all other flows – reach a stable equilibrium. But I am concerned about larger IW values. Last but not least: I cherish the work of Jerry, Joe, Michael, Mark, Ilpo, Matt, Nandita at al.

The argument that modern web browsers – or FTP client’s – actually open several parallel connections to speed up the process is no valid argument. It make things worse, because it de-facto disable congestion control. I.e. in extreme to transfer 1Gbyte, a client can spawn 10000 TCP connections in parallel, but with each connection you make the global congestion control mechanism less effective. To forecast something: I don’t believe that Chrome and Co disable the “parallel connection attempt” if IW10 is approved and becomes a standard track. In the end we will see several parallel connection attempts AND IW10. Simultaneously open n connections and shortly after the three way handshake receive n*10 packets in one flush. Because clients can spawn several connection in parallel does not mean that they should or is fair regarding Jain’s fairness index.

Larger vendors should not try to modify TCP in their horizon – TCP is for everyone. To gain milliseconds on “their” side probably mean loss of several seconds on the “other” side. Modify TCP is a short term solution. The long term solution is somewhere else. HTTP for example could cache more information: nearly 95% of all web-pages on my daily basis are identical: images, logos, web-page text fragments, java script files and so on are identical. I download them over and over again. But it is easier for vendors to tune TCP. But tuning TCP will not scale infinitely, you have a limited bandwidth and with a packet switch network you have the probe the available bandwidth – that’s a fact.

This is a plea to keep the spirit of a conservative TCP in the standardization body.

Justitia, a little bit uncommon without a pair of balances. Somewhere in Brazil:

Today I spent quite some hours in spotting some packet drops at Gigabit line rate. Stress-testing the hardware at line-rate reveal a lot of noise and disagreements: it is difficult to determine what really is the source of packet drops. Due to some netperf and perf analysis and some new tracepoints the eyes focus on PCI express bus.

Quite a lot of analysis until that, first I interpreted the raw values as a CPU limitation. E.g. the CPU may not fast enough to keep sk_buff’s to the adapter. Adjusting the interrupt rate or adjusting the RX/TX ring buffer size are adequate actions, but as I indicated, the CPU was not the limiting factor in the end.

I started to adjust the e1000e driver with some PCI driver modification to set the maximum read request size. I hope I can provide some graphs tomorrow for 1 byte packets and Ethernet Jumbo Frames.

Traveling back from Berlin to Munich. This time via City-Night-Train booked in a six-person wagon. Reading “der Freitag”, a Berlin weekly newspaper produced here in Berlin until midnight. One of Kitas professor suggest the paper.

I took this extended weekend (from Thursday) to arrange our new home in Weissensee/Berlin. Paint the rooms white and the floor in a special mixed color. Next time I will establish the parquet (84m^2). After that all ground work is done and the furniture can be ebayed™. ;-)

Quit interesting Westmere-EP CPU:

In the end dual sockel boxed charges will amount to approx 1000.- Euro.

Mobility Support in IPv6 – Request for Comments: 6275

Libhashish is one of my long term project developed with git. Today I stumbled over a tool to visualize commits, called gource:

Tom posted these days a patch called “Allow no-cache copy from user on transmit”. The idea behind is the following: in net/ipv4/tcp.c:tcp_sendmsg() will copy date from user buffer to sk_buff via copy_from_user() or csum_and_copy_from_user() (which does what the name implies: copy the data and calculate a (partial) checksum). Tom realized that when data is copied data caches are touched which are often not used afterwards.

The feature is enabled if the device signals that he is doing some kind of checksum offloading. So that the driver must not touch any data – calculate the checksum. In other words: this feature is disabled if software checksumming is required. There some other interplay (e.g. with loopback interface) but these are covered. The feature is also configurable via ethtool.

Some measurements (200 instances of netperf TCP_RR):

No-cache copy disabled:
   672703 tps, 97.13% utilization
   50/90/99% latency:244.31 484.205 1028.41

No-cache copy enabled:
   702113 tps, 96.16% utilization,
   50/90/99% latency 238.56 467.56 956.955

Using 14000 byte request and response sizes demonstrate the
effects more dramatically:

No-cache copy disabled:
   79571 tps, 34.34 %utlization
   50/90/95% latency 1584.46 2319.59 5001.76

No-cache copy enabled:
   83856 tps, 34.81% utilization
   50/90/95% latency 2508.42 2622.62 2735.8

The patch seems fine but Davem take them out because of some coding issues.

[...]
        len = dwrq->length;
        ext = _malloc(len);
-       if (!_malloc(len))
+       if (!ext)
                return -ENOMEM;
        if (copy_from_user(ext, dwrq->pointer, len)) {
                kfree(ext);
[...]

IETF 80 will be held in Prague – and as a early bird I registered today. The advantage of Prague is that I am familiar with the city which makes it easy for me to find a cheaper hotel compared to the standard conference hotels (Hilton: 148 Euro/day, Inter Continental: 140 Euro/day). The hotel in Beijing (IETF 79) for example costed ~1500.- Euro for 9 days. I hope to find a hotel for about 350.- Euro. Looking forward to meet colleagues and IETF maillinglist parter.

Yesterday and today I wrote an ANSI C program to demonstrate how a non-blocking, threaded network server for current SMP/CMP systems may be structured. The design of the server is constructed in a way that all CPU may stressed and load is fair balanced. All thread local clients are multiplexed via a event loop management wrapper (epoll() or select()).

The program demonstrate the most effective architecture for current CMP/SMP server systems. One or more passive server sockets is shared by all threads. These file-descriptors are put into all thread local event loop and monitored for EV_READ. Each a new client connect() the server will trigger a EV_READ in one till probably all threads! The actual number of awaken threads depends on the Kernel internal handling. Anyway, next step for all threads is to call accept(), but only one thread will return with a new file-descriptor. The other threads will return -1 and errno is set to EWOULDBLOCK. If this happens the thread knows that another thread was a little bit faster.

The next step for the lucky thread is to process the client request and put the new client descriptor in the local event management loop. Voila, the next events are handled by this thread.

This time the program is not programmed in a portable way. On the contrary the program is really Linux centric to gain the maximum performance and use Linux specific hooks. With some modifications the program should be ported to *BSD too.

What the current design not support is active load-balancing of work. But as more unfair a CPU is penalized the more likely is that new connections are handled by the idle CPU and therefore after a while a equilibration is reached.

ps ax -L -o pid,tid,psr,pcpu,comm | grep -r parallel -
17020 17020   0  0.0 parallel-net
17020 17021   0  0.0 parallel-net
17020 17022   1  0.0 parallel-net
17020 17023   2  0.0 parallel-net
17020 17024   3  0.0 parallel-net
17020 17025   4  0.0 parallel-net
17020 17026   5  0.0 parallel-net

In the next couple of days I will publish the git repository and give a short notice here in the blog.

Jim Gettys wrote an blog entry where he describe problems with a oversized router buffer – he called the problem bufferbloat. Buffer in network equipment exist to catch temporary load peaks and allow proper internal packet exchange from one linecard to another linecard in coexist with the max. bandwidth.

In the case where buffers are overestimated the effect get worse during periods of network congestion. Overestimated buffer will shift the problem in time, or in other words: TCP will overestimate the available capacity and normal congestion avoidance mechanisms do not timely take effect. Overestimated buffers concrete shift the congestion avoidance mechanisms in time – packets are dropped to late and the packet drop is not aligned with the link capacity but rather with the buffer space. The problem with the artificial delayed congestion avoidance is that the congestion avoidance mechanism will overestimate the available bandwidth therefore. User impact is a high latency and jitter. For a proper functioning the mechanism must take promptly and should reflect the link capacity.

IAB/IESG Recommendations on IPv6 Address Allocations to Sites (RFC 3177) provides recommendations that for end sites a /48 block should be provided in normal case. A /64 block when it is absolutely sure that only one subnet is needed and /128 for the case that only one device is connected. The requirements for IPv6 in 1993 included the plan that the next IP version should address approximately 2⁴⁰ networks and 2⁵⁰ hosts. Therefore the currently IPv6 address can be loosely splitted in a 64 bit network number (including subneting) and 64 bit host number (including flat EUI-64 host part and randomly self autoconfigured host number) → 2⁴⁰ & 2⁵⁰ goal accomplished.

/48 provides end sites the ability to subnet 2¹⁶ subnet numbers for internal routing infrastructure each with theoretical max. 2⁶⁴ unique hosts. Most enterprises should be happy with this. Very large enterprises should be provided with a /47 or with multiple/48. RFC 3177 constitute a more or less hard default setting and Regional Internet Registries (RIRs) should bear on that. The idea of the IAB/IESG recommendation was that a hard structure will reduce among other things maintainership (e.g. address restructuring, see paragraph 3 for more information).

IPv6 Address Assignment to End Sites started now to obsolete RFC 3177. Thomas Narten et. al. stated that the RIRs originally started with /48 but began to switch to other policies in 2005. Namely APNIC, APNIC and RIPE encourage the assignment of smaller (e.g. /56) blocks to end sites. One concern is that the hard suggestion can lead to a classfull routing where CIDR continues to apply to all bits of the routing prefixes. Another aspect is that RIRs may have other policies which fit better in their model.

In a nowadays common SMP/CMP environment with more then one CPU it is necessary to protect global/shared data in the kernel. One prominent example are sysctl_ variables. Sysctl variables are protected via a spin lock (sysctl_lock). This look protect the /proc/sysctl interface path, the look itself does not protect the usage path itself. Consider the following example:

int global_val;
int foo(void) {
    if (global_val != 0) {
        int res = bar();
        return res / global_val;
    }
    return -1;
}

Here global_val is a global accessible variable. If you are fit in spotting errors and remember that we are in a SMP/CMP environment you will notice that global_val is not protected. Thus during the execution of bar(), global_val may might be change, in a worst case to zero.

One solution might be the following code fragment:

int global_val;
int foo(void) {
    int tmp_cpy = global_val;
    if (tmp_cpy != 0) {
        int res = bar();
        return res / tmp_cpy;
    }
    return -1;

This may looks fine, but as you can imagine there is another flaw in the code! The problem is that the compiler may eliminate tmp_cpy and read the global_val twice! The correct code may look like this:

int global_val;
int foo(void) {
    int tmp_cpy = *(volatile int *) &(global_val);
    if (tmp_cpy != 0) {
        int res = bar();
        return res / tmp_cpy;
    }
    return -1;

This guard prevents the compiler from merging or refetching accesses – no more, no less.

The bottom line is either you protect every piece of shared data costly or you know how your compiler act and you can rely on you tests (regardless if automated or you crowd source your testing ;-).

This blog post is not about micro-optimization nor about what you have to use. Neither, it is about how compilers can optimize two common flow constructs. The knowledge may provide enough background information to sharpen the view and provides enough insights what construct to use for which usage.

The following if-else statement is compiled on x86_64 with -O6 into the following ASM sequence:

int main(int ac, char **av) {
    if (a  0) foo();
    else if (a  1) bar();
    else if (a == 2) shu();
}

[...]
 main:
 .LFB35:
   .cfi_startproc
   subq  $8, %rsp
   .cfi_def_cfa_offset 16
   cmpl  $0, %edi
   je  .L19
   cmpl  $1, %edi
   je  .L20
   cmpl  $2, %edi
   je  .L21
   .p2align 4,,5
   jne .L13
[...]

The if-else statement is translated into a conditional sequence of cmp and conditional jump instruction.

A identical switch/case construct can be optimized because the compiler can generate a jump table of complexity(1) compared to a complexity of O(n) where the compiler generate a ordinary conditional construct. So if you had to branch into multiple targets and the argument is a integer a switch/case statement is superior. Requirement is that labels are dense. If not the fallback is to use the conditional jump chain.

switch (ac) {
case 1: foo(ac); break;
case 2: bar(ac); break;
case 3: sho(ac); break;
}

L18 is the label where the jump tables is saved. The jmp instruction will jump to the right label:

 main:
 .LFB35:
   .cfi_startproc
   subq  $8, %rsp
   .cfi_def_cfa_offset 16
   cmpl  $5, %edi
   ja  .L12
   mov %edi, %edi
   jmp *.L18(,%rdi,8)
   .section  .rodata
   .align 8
   .align 4
 .L18:
   .quad .L12
   .quad .L13
   .quad .L14
   .text
   .p2align 4,,10
   .p2align 3

If you have some items the if-else statement is sufficient fast and no differences are measurable. But for many entries you should definitely use a switch/case statement. And by the way: a switch/case statement is often more eye pleasant to understand and can be considered as a list of coequal options. But anyway it is a micro-optimizations and does not affect your code (exceptions are omitted). If you write code often and you are free to choose the right construct why not to pick up the more efficient one? But as always in programming: readability and maintainability are of higher interest.

Another tip: sometimes I see code something like this:

if (!strcmp(arg, "foo")) foo();
else if (!strcmp(arg, "bar")) bar();
else if (!strcmp(arg, "shu")) shu();
[...]

The delicate issue of this construct is that the key (here arg) is compared multiple time in the program – not in one place but several times arg must be considered. The key is constant and do never change and strcmp() isn’t the lightweight function. The more intelligent approach is to map the key to a enum/int type at program start and use a switch/case construct afterwards:

int map(const char *arg) {
if (!strcmp(arg, "foo")) return TYPE_FOO;
else if (!strcmp(arg, "bar")) return TYPE_BAR;
else if (!strcmp(arg, "shu")) retrn TYPE_SHU;
}

int main(int ac, char **av) {
    const int type = map(av[0]);
    switch (type) {
        case TYPE_FOO: return foo();
        case TYPE_BAR: return bar();
        case TYPE_SHU: return shu();
    }
}

A last sidenote: if you are mainly interested on the function call than another superior construct is a function pointer array where the type is the index into the array. But this is more specific but on the other hand the most efficient usage for this scenario.

My baby was my lovely Canon EOS 7D. And I lost the camera during the flight back from the IETF meeting in Beijing/China to Frankfurt/Germany. It is a story about how scatterbrained a man can be. ;-)

I deposited the camera under the seat in front of me. After the plane landed and all passengers surrounding me left the plane I left the plane too – without the camera …

At the customs check I realized that I missed my camera and started to run to the plane. Unfortunately it was not possible anymore. I instantly called the baggage check service and approx. after 15 minutes we got a call that the camera wasn’t there. 15 minutes after I left the plane!

Passengers are out of the question because I sat at the window and nobody saw the camera. Additionally fact: I was the last person in the row – so nobody saw the camera. Now there are two groups who can robed the camera: the stewards and the cleaning staff.

I don’t think that the stewardess stole the camera because normally all stewardess leave the plane in a group, such a big camera would focus the colleagues. Furthermore, stewards do not check seats for forgotten baggage.

On the other hand cleaning stuff members are clean up all corners – including the place under the seat – and they are normally alone. E.g. each of then has an assigned area …

It is so sad that this audacious burglary can happened at a Lufthansa flight. I am really disappointed and unhappy with this incident. I booked 95% of my flights via Lufthansa, I prefer to spend some more money and enjoy a warm atmosphere as well as the sense of a technical maintained airline. Maybe I should reconsider my position and switch to another airline (e.g. Emirates).

New are pleased to announce realease version 1.1 of libhashish. Major features are, ... no new features. The release includes bugfixes for (u)int{8,16,32}_t hash key collision, a memory leak fix for the collision array implementation – thanks to Emmanuel Roullit, CFLAGS adjustments from Florian Westpahl, and Debian packageizing fixes from Michael Stapelberg.

Several month ago I spend some months to analyse the behaviour of Genetic Algorithms. The research focused on mutation, selection and crossover algorithms and their behaviour. Genetic Algorithms are probabilistic search heuristics that emulate the process of evolution. Problem domains for genetic algorithms are complex scheduling problems (e.g. flight scheduling at the airport), Protein structure prediction or academic problems like traveling salesman problem. Genetic algorithms are useful where other search algorithms collapse through an almost infinite solution space.

People not familiar with complex search problems of this kind should imagine a graph where the task is to find the minimum of the function. The naive approach to scan the graph from start till end and remember the smallest value will result in a solution – no doubt. At the end of the process the result is the minimum of the function. Now imagine that the graph is not two dimensional (x and y), but rather a three or even n-dimensional problem. The naive approach to scan each section is simple far too much. Genetic algorithms will spread his probe-points, check if a pre-defined minimum is found and if not the probe-points are new-adjusted. Adjusted through mutation, selection and crossover with other probe-points. One major characteristic is that superior probe-points are favored (superior probe-points in our example will have the smaller value – because we are searching for the minimum in a n-dimension solution space) in the process of crossover. The idea is that mutation from a good and a good parent probe-point will finally result in the superior solution – hopefully.

All used and cited code is licenced under the GPLv2, see git.jauu.net

Since several weeks I deal with TCP Quick ACK mechanism. TCP Quick ACK where introduced to bypass the disadvantages of delayed ACKs. If a flow is not interactive and send fully Maximum Segment Sized (MSS) packets from one endpoint to the other there is no real need to artificially delay any packets. In this situation the receiving host will never send any data and the TCP instance can instantly trigger an ACK packet. This allows the other hand to even increase the congestion window (CWND) faster compared to TCP instances where the ACK is always delayed.

But there are some challenges with this mechanism. First, the TCP instance does not instantly know if a local TCP application will piggy back some data or not. The TCP does not know if a application behaves interactive like HTTP or like a FTP bulk application. The TCP stack must first analyze the connection pattern. Quick ACK can be employed in two ways:

• a new vanilla connection can start with QUICK ACK enabled and deactivate the mechanism if interactive characteristic is detected
• a new vanilla connection is started with Quick ACK disabled and if the connection is not interactive the QUICK ACK is enabled.

Currently under Linux the former mechanism is employed: TCP Quick ACK is enabled per default and only if the heuristic detects that the connection is interactive (e.g. HTTP) the QUICK ACK is disabled!

The drawback is not negligible: the first ACK packet is always generated and transmitted, although the server may have instantly some data. The prominent example is HTTP! Here the client ask for a file (via HTTP GET) and the server will hand-out the required file. But because of QUICK ACK the TCP instance will generate an ACK first and shortly afterwards will generate a additional DATA packet.

The additional ACK is solely generated the first time till the heuristic detects DATA from the server to the client. But especially short-lived-flows like HTTP will suffer from this. The typical HTTP flow includes only 10 till 20 data packets. One additional ACK packet is not to underrated!

The last two packets in the image illustrates this characteristic.

To identify the minimum or maximum of two values often a simple if else construct is used:

if (a < b) min = a; else min = b;

or more compact using the ternary operator:

min = (a < b) ? a : b;

The generated instructions for the first if/else construct and the ternary operator does not differs. At least if the compiler is instructed to optimize the code. If the code is not optimized the compiler generates a little bit awkward code with a branch for the former example. The later use a branch free cmovle instruction on a x86_64 architecture:

[...]
movl  %edi, -20(%rbp)
movl  %esi, -24(%rbp)
movl  -20(%rbp), %eax
cmpl  %eax, -24(%rbp)
cmovle  -24(%rbp), %eax
movl  %eax, -4(%rbp)
movl  -4(%rbp), %eax
leave

The kernel provided macros for min/max extend this by execute an apparently unnecessary pointer comparison via:

(void) (&_max1 == &_max2);

This check was introduced to enable strict type-checking to make sure that both arguments are of the same type. I build a patch to extend the current two operand limited macro and enable the use for three operands too. This will save some bytes on the stack as well as some processing cycles:

#define min3(x, y, z) ({            \
    typeof(x) _min1 = (x);          \
    typeof(y) _min2 = (y);          \
    typeof(z) _min3 = (z);          \
    (void) (&_min1  &_min2  &_min3);    \
    _min1 < _min2 ? (_min1 < _min3 ? _min1 : _min3) : \
         (_min2 < _min3 ? _min2 : _min3); })

TCP’s window scale factor is determined at the connection start-up. Among other things local memory constraints are checked and used as the basis to calculate the window scale shift factor. The exact procedure is complex and not of interest here. Currently the Linux network stack does not consider a reduced rcv buffer which can be reduced via setsockopt(). Today I sent a patch which fix this with some lines of code:

if (sk->sk_userlocks & SOCK_RCVBUF_LOCK &&
        (req->window_clamp > tcp_full_space(sk) || req->window_clamp == 0))
    req->window_clamp = tcp_full_space(sk);

I waive explaining text in the patch why I fixed the bug in this way and not modified the main function (tcp_select_initial_window()) and hope that Dave and Ilpo trust me … ;-)

just for the protocol: Linux memory management is terrible complex. Many hidden relations to and from other components in an optimized form that prevent anyone from beeing productive. {Free,Net,Open}BSD code is much more coherent and easier to understand. It is even difficult to write a proper commit message in a understandably way that more then 4 people understand why I modified the code in this way.

I thought about how I would design the Translation Lookaside Buffer of the Memory Management Unit (MMU) if I was the CTO of Intel, respective AMD. ;-) In one of my last postings I talked about an potential optimization for x86/x64_64 but at the end I decided that the effort of implementing and testing compared with the benefit is to high so I skipped this. But as said this I thought about how would I design the TLB regardless of any existing implementations …

As I already wrote the TLB is a fully associative cache because most programs exhibit so called “locality of reference”. This means that the working set will be used many times. The most recently used page mappings will be stored. The TLB cache virtual addresses to physical addresses on a page basis (e.g. 4096 byte). With a few page entries a full program can be mapped: .text, .data, heap, ...

Fully associative caches are costly because entries must be searched in parallel. Any address can be stored everywhere in the cache and no hashing or indexing is applied. n-way set associative caches on the other hand use a index.

So far so good! From my last posting we know that the TLB logic is not entirely spilled into silicon. At least some processor architectures swap some logic to the kernel. This is the point where we start!

When a TLB hit occurs the cache returns the physical address. If a miss occur two things depending on the architecture can happen:

• the processor start looking up the page table by himself – called page walk – until he find the physical address and replace the TLB by himself
• the processor generates a trap and shift the task to the operating system. The kernel must now walk over the page table, check the page permission and finally replace the TLB entry with the right physical address.

The former approach is implemented by x86, SPARC and some others. The later is implemented by the MIPS family.

But that’s not all, there are some subtle differences. As I wrote in the other postings Linux does not flush the TLB if a Kernel thread is scheduled because a kernel thread does not touch user pages and kernel pages are unique. But if the kernel scheduled another user space process the virtual to physical mappings become obsolete. Each new page walk is a costly operation and should be avoided. Some architectures extend the concept of a plain address space by (re)introduce a key – surprise! ;-) This key is bound to the task and only if the task differs the TLB entry is flushed. One example is the TI-SPARC where a context switch does not require a TLB flush.

I just started to understand how the context switch works for the SPARC is implemented. But it is hard to read SPARC assembler code (not as hard as ia64 asm ;-):

   /* At this point we have:
    * %g1 -- TSB entry address
    * %g3 -- FAULT_CODE_{D,I}TLB
    * %g5 -- valid PTE
    * %g6 -- TAG TARGET (vaddr >> 22)
    */
 tsb_reload:
   TSB_LOCK_TAG(%g1, %g2, %g7)
   TSB_WRITE(%g1, %g5, %g6)

   /* Finally, load TLB and return from trap.  */
 tsb_tlb_reload:
   cmp %g3, FAULT_CODE_DTLB
   bne,pn %xcc, tsb_itlb_load
   nop

Especially the label tsb_miss_page_table_walk_sun4v_fastpath: is of interesst. Also the division between instruction and data.

The Translation Lookaside Buffer is a small associative memory that caches virtual to physical page table addresses. When page tables have been updated, such as after a page fault, the processor may need to update the TLB for that virtual address mapping. May, because some processor architectures implement this in hardware logic some other architectures need support by the operating system. Flushing TLB is a really expensive operation – depending on the architecture (e.g. PowerPC) – and should be avoided if possible in any way. Linux for example does not invalidate the TLB if a context switch occurs, Linux rather tries to partial invalidate the TLB. Kernel threads for example access only the kernel space and do not require an invalidation of the user space TLB cache, Linux does not invalidate the cache in that case.

Today I played with some TLB optimization. Current kernel code can flush one page cache for a given page or all pages. Although the kernel API provides the possibilities to invalidate a range of pages. If a range is requested for invalidation, all pages are invalidated and not a limited range of addresses.

flush_tlb_range(vma, start, end) for a given mm context from start till end all pages are declared as invalidate via this method. Partial invalidation can happend if a memory region has moved or permissions are changed (via mprotect()). munmap() or mprotect_fixup() for example use this function.

flush tlb all() on the other hand invalidates the TLB on all processors running in the system. flush tlb mm() flushes the TLB for a given userspace context, always below PAGE_OFFSET. fork() is a user of this function.

Some words about the invalidation procedure on x86: the INTEL manual stated that all non-global TLB entries are flushed after writing to CR3 . The CR3 is used to translate the virtual addresses into physical addresses by pointing to the page directory and page tables of the current task. Read and re-write the CR3 register was the only way to flush the TLB after a page table update. Newer CPU have TLB flush instructions to partial flush a given address, i386 and i486 CPU’s didn’t have these instruction; via invlpg it is on x86 >i486 possible to flush a given memory address.

static inline void invalid_tlb_old(void)
{
    unsigned long val;
    asm volatile("mov %%cr3,%0\n\t" : "=r" (val), "=m" (__force_order));
    asm volatile("mov %0,%%cr3": : "r" (val), "m" (__force_order));
}

static inline void invalid_tlb_addr(unsigned long addr)
{
    asm volatile("invlpg (%0)" ::"r" (addr) : "memory");
}

UPDATE: I decided to stop digging into this optimization. After a while of analyzing the callees I realized that the effort is much higher as the potential benefit.

The 20 bit wide Flow Label field in the IPv6 header is a integral part of the protocol specification, standardized in RFC 2460 The field may be used to mark sequences of packets for which the sender request special handling at intermediate routers. The standard explicitly does not define the what, it exemplary provides two examples (real-time and non-default quality of service routing) and that’s all. At the specification time nobody was in the ability to specify how this field may be used in the future or may not used for. As so often the time should breed possible use cases. Good designs are often – not always – characterized by a unseen potential which is discovered later on. One famous example is the C++ template system – the powerful scope was identified after the language was already released: Modern C++ Design: Generic Programming and Design Patterns Applied

Time goes by and the use cases are still rare for Flow Label. This may be founded in the low diffusion of IPv6 at the time of writing or because larger carriers already use Multiprotocol Label Switching (MPLS) beside the common 5-tuple used to classify a packet flow (later on is a rare exception in the core). The 5-tupel has it own problems such as fragmentation or next header parsing due to the fact that the port information is at the transport layer. Anyway, use case questions accumulate over time and an I-D address some possible use cases of this 3-tuple {source address, destination address, flow label}: Survey of proposed use cases for the IPv6 flow label The I-D is worth reading!

For some analysis I plotted the inter-frame delay in microseconds within the transmitter must send a frame to archive the desired transmission rate. For a 10Gbit network adapter and a 10 byte frame the time between subsequent transmission must be 0.008 microseconds (or 8 nanoseconds or 8e^-09 seconds) The illustration with a logarithmic y scale:

Not really thrilling or exciting, I generated the images to illustrate the difficulties to generate a bandwidth exact bytestream where the operating system as well as hardware components are working at the edge.

The following image illustrates the accumulated delays during the transmission of UDP packets. Starting with a 1 second sleep with theoretical no delay, but practical delay of ~200 microseconds on a un-busy box till due to timer granularity and concurrent processes (not in this scenario), till transmission delays via intermediate routers, NIC interrupt moderation and finally RX side scheduler latency.

UDP sockets – if corking is disabled – always push packets directly to the lower layers. In the case of IPv4, ip_output() will forward the packet to Netfilter where the firewall rules are applied. ip_finish_output() calls ip_finish_output2() which on his part calls neigh_hh_output() which put the cached layer 2 Ethernet header in front of skb and finally call dev_queue_xmit().

dev_queue_xmit() queues the packet in the local egress queue – default is a FIFO queue (pfifo_fast) but sophisticated queuing strategies are available and often selected. Before the actual packet is enqueued the function dev_queue_xmit() linearize the skb if necessary, do checksumming if necessary, and finally calls enqueue() which places the packet into the queue. This function fails if the queue is (temporarily) deactivated or a overflow happens. In the common cases the function returns NET_XMIT_SUCCESS. Note that the standard queue has a short cut: if the queue length is 0 – no packet is queued – the packet is directly scheduled via sch_direct_xmit(). If something goes wrong (somewhere in the driver), the packet is pushed several times to the NIC put on the wire via qdisc_restart() until the NIC accepts the new packet. If this fails the one element queue is saved and a SOFTIRQ is raised on the local CPU. In the hope that next time the SOFTIRQ is executed the NIC is in the ability to accept the packet.

If the queue supports no short cut or the queue contains at least one element the packet must be enqueued via qdisc_enqueue_root(). This enqueue function is scheduler specific. For FIFO queueing the packet is added at the end of the list, more complicated queues implement a more sophisticated queueing.

dev_queue_xmit() {
    netif_needs_gso();
      skb_needs_linearize();
      if (q->enqueue) {
        if (TCQ_F_CAN_BYPASS && qdisc_qlen(q) == 0) {
            if (sch_direct_xmit())
                __qdisc_run(q);
            return NET_XMIT_SUCCESS;
        } else {
                    ret = qdisc_enqueue_root()
            qdisc_run(q);
            return ret;
        }
    }
}

__qdisc_run() {
    while (qdisc_restart()) {
        if (need_resched() || to_often_restarted) {
            raise_softirq_irqoff(NET_TX_SOFTIRQ);
        }
    }
}

qdisc_restart() try to call dev_hard_start_xmit() instantly to put the packet on the NIC TX descriptor ring – if possible. __qdisc_run() enabled the SOFTIRQ – if not already enabled.

Finally note that the return code of dev_queue_xmit() make no statement if the packet can be transmitted. Subsequent congestion or the queue policy can decide to drop the packet. A positive return code only signals that the enqueuing was successful.

IPv6 is similar except that neighbor resolution is done by IPv6 neighbor discovery mechanism (ND).

Last but not least some network devices have no associated queues. The loopback device and all kind of pseudo tunnel devices are common examples. These devices have no queues and instead of placing the packet in a queue the function dev_hard_start_xmit() is called directly.

This post recycles the title of a famous paper from Craig Partridge and Jonathan Stone from 2000. Traces shows that between 1 packet in 1100 and 1 packet in 32000 fails the TCP checksum – even thought a link layer CRC was used. The TCP/UDP checksum is also ineffective at detecting bus specific errors since these errors with simple summations tend to be self canceling. The paper is worth to read it: it talk about the sources of errors, how TCP react and how to reduce the error rate.

But what about the Ehternet CRC? The weakness of the CRC becomes acute in network environments with a MTU larger then 1500 bytes – data center, research networks, cluster systems and so on. Until 1500 byte the CRC is strong. Currently a MTU of 9k is possible without special NICs – almost all current gigabit network adapters support jumbo frames. Some older gigabit NICs from Realtek failed because the CRC routine failed. Intel’s e1000/e1000e adapter can even transmit and receive frames up to 16128 bytes.

Corruption could occur at the source in software, in the network interface card, out on the link, on intermediate routers or at the destination network interface card or node. Maybe I forgot some sources. The actual assumption is that one packet in 10 billion will have an error that goes undetected for Ethernet MTU frames.

Ethernet uses a 32 bit CRC that loses its effectiveness above about 11455 bytes – after this limit the CRC-32 the probability of undetected errors per frame increase. A white paper with the title Extended Frame Sized for Next Generation Ethernets discuss further issues why a frame size should not exceed 9000 byte.

Beside the standard Ethernet CRC the Castagnoli CRC (CRCNc) is worth to mention it. Standard Ethernet CRC was selected because of his performance. CRC32c – the Castagnoli counterpart to CRC32 used by iSCSI or SCTP –

CRC-32-IEEE 802.3 Polynom:

x³² + x²⁶ + x²³ + x²² + x¹⁶ + x¹² + x¹¹ + x¹⁰ + x⁸ + x⁷ + x⁵ + x⁴ + x² + x + 1

Castagnoli CRC 32C Polynom:

x³² + x²⁸ + x²⁷ + x²⁶ + x²⁵ + x²³ + x²² + x²⁰ + x¹⁹ + x¹⁸ + x¹⁴ + x¹³ + x¹¹ + x¹⁰ + x⁹ + x⁸ + x⁶ + 1

crctool is a online tool is available which generates VHDL code for a wide number of CRC algorithms. Support for Stronger Error Detection Codes in TCP for Jumbo Frames provides some text about this topic.

Last but not least Intel core i7 processors have the CRC32c function contained within their new SSE4 math coprocessor.

In user-space the answer is often simple: use gettimeofday if microseconds resolution is sufficing. Another often used mechanism is to use the time stamp counter – but as mentioned in another blog-post in the lion share of all use cases the advice is often too narrow because of clock variances in SMP/CMP systems and hibernation issues.

#define rdtscll(val) \
    __asm__ __volatile__("rdtsc" : "=A" (val))

In kernel-space the timing capabilities are a little bit more complex and several functions are provided. Three new kinds functions are available, both with different scalability and precision:

• trace_clock—this clock is good compromise of the other clocks. The clock is not completely serialized but try to level CPU boundaries.
• trace_clock_local—complete un-serialized, lowest latency.
• trace_clock_global—use clock at core with id 0, highest latency.

All three clocks provide u64 nanoseconds granularity (but not precision ;). At the end it is often more crucial to get exact timings as a precise timestamping mechanism with a small latency but variances of several magnitudes due to SMP/CMP issues.

Animated presentation held by sociologist David Harvey and Professor Philip Zimbardo for Royal Society for the encouragement of Arts, Manufactures and Commerce (RSA):

• RSA Animate – The Secret Powers of Time
• RSA Animate – Crises of Capitalism

Today I spend some hours to complete a python project. Because the project should expandable and manageable the functionality is splitted into classes, packages and so on – python best practices.

But, as long as I program with python I don’t understand why this language is so hyped! Several years back I wanted to leave Perl as the scripting language of choice (sometimes I still use Perl). As far as I remember I looked at Python and Ruby and finally I decided to use Ruby. Nowadays, When I reexamine this decision I must say that this decision was absolutely right!

There are several Python characteristics that bother me currently:

• no really clean object oriented design. Under the hood Python and Ruby are closer together then it seems but Python integrates a lot of extension that make this OO design not visible – why? Ruby on the other hand goes another way: it provides a clean OO interface and do a lot that this OO interface is usable. Why must the OO design artificial hidden from the programmer?
• classes are expandable: with ruby I can add or remove class methods at runtime or even modify already existing class methods. A really great feature which is really handy in some circumstances – where is this feature in python?

Sure, I am no python hacker but from the programmer experience the ruby interface seems quite more matured and cleaner.

666.factorial
NoMethodError: undefined method `factorial' for 666:Fixnum
class Fixnum
    def factorial
            (1..self).inject { |a,b| a * b }
    end
end
23.factorial
25852016738884976640000

During some off-line discussion with Florian – one of the main developers of TCP SYN cookies – I was a little bit skeptic about the mechanism and the interplay with the TCP window scaling option.

First I will describe these two mechanism; later on I will discuss their relationship and interplay. At the end I will discuss the regression and possible solutions. I shifted this off-line discussion to the kernel ml because it is not that trivial as it sounds.

TCP Window Scaling

This TCP extension was introduced by RFC 1323 (TCP Extensions for High Performance) and expands the 16 bit window to an effective 32 bit window. This option specify a logarithmic scale factor which is applied to the received and transmitted window. Receive and send window scale factor are established separately in each direction. This factor is fixed at the three way handshake (in the SYN and SYN/ACK packet ) and cannot be changed during the TCP session. The scale factor and therefore the maximum receive window is determined by the maximum receive buffer space. Linux for example check the maximum possible receive memory in bytes and level the window scale factor based on this value (sysctl_rmem_max and sysctl_tcp_rmem).

The actual window size is calculated each time a TCP packet is transmitted via tcp_output.c:tcp_select_window() and advertise the amount of free space in the receive buffer (under consideration of RFC1323 scaling is applied). The algorithm never shrink the offered window – conforming to the RFC 793. This buffer is sticked to exactly one socket. Expanding the window is more complicated, RFC 1122 says:

the suggested [SWS] avoidance algorithm for the receiver is to keep RECV.NEXT +
RCV.WIN fixed until: RCV.BUFF - RCV.USER - RCV.WINDOW >= min(1/2 RCV.BUFF, MSS)

Means that the window is never raised on the right side until at least memory is available to increase it at least MSS bytes. This RFC statement is a little bit unlovely because it breaks the header prediction algorithm but this is another topic. ;)

Last but not least the actual window calculation is not purely based on actual available and advanced allocated memory, it is also based on window clamping. Which is roughly 3/4 the size of the receive buffer minus the size of the application buffer minus the maximum segment size. In the presence of dynamic window sizing the window clamping is a little bit more complicated because the memory control is more dynamic and so on …

SYN Cookies

SYN cookies are one answer to reduce the “effective area” of an network stack socket listening in the wild. Back in 1990 TCP SYN flood attacks where the new black and form a not irrelevant problem for network serves. The attack is extreme simple: craft a lot of SYN packets, sent it to a open listening socket – leave the socket in the half-open state – and wait until the server resources are exhausted. The problem is that the initial SYN packet signals the network stack to initiate a connection which requires a lot of resources. This normally includes all received TCP socket options, transmitted (in the SYN/ACK packet) socket options and a lot of other bookkeeping stuff. Under Linux struct tcp_sock is nearly 2000 byte big! It is imaginable that 200k SYN packets can exhaust the whole memory pool of the server (we are talking about kernel memory which is bound to 1GB at 32 bit architectures without EMT64 support) and no other legitimate connection can established.

D. J. Bernstein come to the conclusion that holding the initial state is the problem and his solution was to hold no state at the server side until the third packet in the three way handshake is exchanged. The idea was to encode the important data received in the initial SYN packet in the TCP timestamp option in the second (SYN/ACK) packet. The peer is engaged to piggy back this timestamp in the third packet (the ACK packet) where the server can reconstruct the information. Assumption: the peer supports the TCP timestamp option, but this is standard today and was more or less standard back in the 90’s.

But encode all information in the timestamp option is not trivial because RFC 1323 requires that the clock increases, a dump replacement is not sufficient. So the values are encoded in the following manner: top 5 bits encodes the timer counter, followed by 3 bits which encodes the MSS of the client side and finally a 24 bit server-selected secret function of the client IP address and port number. This is required because it must be prevented that the client can control the network stack by sending crafted timestamp options, therefore some “cryptography” must be employed. It is obvious that in few bits not the whole information can be encoded – this is a shortcoming of the mechanism.

This was the original idea of Dan. But ideas involve and nowadays the situation is more well-thought-out: Linux per default uses mini sockets (struct tcp_request_sock; ~100 byte) to hold the minimal initial state after SYN packet. This provides the whole feature set but requires only a few bytes. The cookie mechanism – if enabled – is inactive if the network stack don’t experience any memory pressure. If the network stack suffers from memory the cookie mechanism becomes active. Some final word: Linux nowadays encodes additional values in the SYN cookie: window scaling, selective acknowledgements and so on.

BTW: if you are not trained you will not even realize that SYN cookies are active:

13:51:04.582464 IP 127.0.0.1.57985 > 127.0.0.1.4050: S 1061746051:1061746051(0) win 32792 <mss 16396,sackOK,timestamp 0xfffea013 0,nop,wscale 6>
13:51:04.582478 IP 127.0.0.1.4050 > 127.0.0.1.57985: S 2800702917:2800702917(0) ack 1061746052 win 32768 <mss 16396,sackOK,timestamp 0xfffe9f66 0xfffea013,nop,wscale 6>
13:51:04.582480 IP 127.0.0.1.57985 > 127.0.0.1.4050: . ack 1 win 513 <nop,nop,timestamp 0xfffea013 0xfffe9466>

13:59:19.047306 IP 127.0.0.1.45979 > 127.0.0.1.4050: S 218483035:218483035(0) win 32792 <mss 16396,sackOK,timestamp 0x0001bed4 0,nop,wscale 6>
13:59:19.047320 IP 127.0.0.1.4050 > 127.0.0.1.45979: S 1141094138:1141094138(0) ack 218483036 win 32768 <mss 16396,sackOK,timestamp 0x0001bd66 0x0001bed4,nop,wscale 6>
13:59:19.047322 IP 127.0.0.1.45979 > 127.0.0.1.4050: . ack 1 win 513 <nop,nop,timestamp 0x0001bed4 0x0001bd66>

Do you realize the “conspicuousness” in the lower nine bits of the timestamp in thesecond SYN/ACK packet? ;-)

Network Stack Regression

The detected regression in the current network stack arise from the circumstance that that their is a race between the SYN/ACK where we initial force a particular window scale and the next time where we recalculate the window via tcp_select_initial_window().

If the user change net.core.rmem_max or net.ipv4.tcp_rmem in between this time, the recalculated window scale (rcv_wscale) can be smaller. But the receiver still operates with the initial window scale and can overshot the granted window – and bang.

There are several solutions:

• encode rcv_wscale into the SYN cookie and don’t recalculate the scaling factor via tcp_select_initial_window() or

*disable window scaling and don’t transmit any scaling option when SYN cookies are active. The later option is not that defective as it sounds. Even if the server suffers from memory the window scaling becomes insignificant.

Just now, two new Request for Comments are now online available:

• RFC 5925 – The TCP Authentication Option
• RFC 5926 – Cryptographic Algorithms for the TCP Authentication Option (TCP-AO)

These two standards (and probably upcomming enhancements in several years ;) are the replacement for TCP MD5 Option (RFC 2385). TCP-AO specifies stronger Message Authentication Codes to protect against replay attacks for long lived connections like BGP sessions. It is a generic contaier where other authentication codes can be used. Several other aspects are adjusted too like an extended sequence number mechanism (imaginable as shadow registers) and IPv6 support.

Florian Westphal and I held a presentation where we mentioned TCP-AO at that time upcoming standard: Trends und Neuerungen bei der Protokollentwicklung

The Internet is now a more safer place … ;)

The Munich Symphony Orchestra will perform during Apil 2011 the Lord of the Rings Epos with chorus, soloists and more then 250 assistants – sounds great!

PS: http://www.youtube.com/watch?v=R-4nH1ajQJY

Nearly 99 percent of all kernel patches touch someones code. Someone is often the maintainer of the subsystem or another developer who is responsible for special tweaks. So the patch should not limited to some maillinglist but should also be addressed directly to the stakeholders of the code. If you are familiar with the current subsystem you know how is the stakeholder and it easy to Cc the right people. On the other hand if you are working within complete unfamiliar code it is not that easy.

The most simple strategy is to look at source code and annotate the lines. Beside that it is of interest who contributes the lion shares. The following git command displays the top 3 contributors since kernel version 2.6.12 for the KVM directory:

git shortlog --email v2.6.12.. -sn arch/x86/kvm/ | cat -n | head -n 3

The kernel version as well as the restriction of the source code files must be adjusted for the personal needs – of course.

(17:17) < fw> pakete kriegt das ding via libnetfilter_queue, was prinzipiell schon richtig ist
(17:18) < fw> Typische loesung ist, nur "noch-nicht-klassifiziert" pakete zu queuen, und nach sagen wir 4k aufhoeren
(17:18) <hgn> das wird eine baumstruktur
(17:19) < fw> so sollte es sein
(17:19) <hgn> genau
(17:19) < fw> aber fuer l7filter sind alle pakete gleich, und alle pattern auch
(17:19) < fw> und das ist schlecht[tm]
(17:19) <hgn> ok
(17:19) <hgn> das ist wirklich schlecht
(17:19) < fw> und es ist c++ ;)

Today I had the idea of accelerate respective decelerate the time for virtual guest machines. The idea comes into mind with time discrete simulators where the wall clock behavior is not required or rather cumbersome. Linux sophisticated kernel virtualization infrastructure is kvm (Kernel-based Virtual Machine, where Intels VT-x or AMD-V native virtualization technique is used).

Several timing systems are supported by QEMU and the kernel side:

• PIT, an emulation of Intels i8254 Programmable Interval Timer, normally with three 16 bit counters, modern back in i8086 CPUs days
• RTC, the real time clock with a interval of 32768 ticks per second to advance the time system reported by interrupt number 8. A really comprehensive documentation can be found at Documentation/rtc.txt
• TSC, a 64 bit wide counter (time step counter) and present on all x86 processors. Based on the famous rdtsc instruction, but as usual the disadvantages of rdtsc also employees for kernel side clock keeping: not CPU hibernation aware, core migration problems and so on. The Kernel on the other hand will do everything to analyze the behavior of the RTC. If the analyze results in a inaccurate behavior the RTC clock is not used. Some days ago Thomas Gleixner talked about the problems of TSC and why he dissuade user space applications from using it.
• HPET, the high precision event timer is the new kind on the block and take over the RTC. HPET has a ~10MHz 64 bit wide counter and 3 independent 64-bit comparators as well as 29 additional 32-bit comparators for random interrupt generation. My hardware HPET announce itself as hpet0: 4 comparators, 32-bit 14.318180 MHz counter (see x86/kernel/hpet.c)

My KVM environment provides no stable RTC clock source so it switch from RTC to HPET emulation mode.

VMWare provides a good overview about timekeeping and virtualization: vmware_timekeeping.pdf

So currently I am working at the mentioned feature but high resultion timer implementation as well as the clock diversity zoo make life not easy. The code lacks of documentation too, so often only reverse engineering provides the required information and this decelerate the flow …

The disassembled output of filter.o looks not cache-line friendly, with the current generated code two cache-lines must be hit—at least. A switch statement with two case statements is translated into a sequence of conditional branches like this (arch: x86_64):

4b8: 8b 06                 mov    (%rsi),%eax
4ba: 66 83 f8 35           cmp    $0x35,%ax
4be: 0f 84 d8 02 00 00     je     79c <sk_run_filter+0x325>
4c4: 0f 87 07 01 00 00     ja     5d1 <sk_run_filter+0x15a>
4ca: 66 83 f8 15           cmp    $0x15,%ax
4ce: 0f 84 cd 02 00 00     je     7a1 <sk_run_filter+0x32a>
4d4: 77 73                 ja     549 <sk_run_filter+0xd2>
4d6: 66 83 f8 04           cmp    $0x4,%ax
4da: 0f 84 1f 02 00 00     je     6ff <sk_run_filter+0x288>
4e0: 77 29                 ja     50b <sk_run_filter+0x94>

The whole switch/case jump construct in run_filter() eat exactly 567 byte .text memory! But why does gcc not generate a jump table (also known as branch table)?

The basic gcc algorithm for switch constructs is simple: less then 5 case statements forces gcc to generate code as explained above. More then 5 case statements command gcc to use a jump table – if the labels are in some degree stick together(dense). A heuristic will calculate if the degree is sufficient. And this kicks in here, the labels are exposed and filling the gaps with defaults is to costly. So keep the labels close to each other to make this optimization possible for gcc! gcc generates a small data section where the addresses of all labels are stored and the finally switch construct leads to a simple jump (I simplified the code):

cmpl $4, %eax
ja   .L8
jmp *.JUMPTABLE(,%eax,4)

The advantage is a reduced complexity from O(n) to O(1). The threshold is 5 cases if less then 5 a binary search is applied, more then 5 leads to the jump table.

The alternative is illustrated in the first listing where each label is a sequence of compare and jump instructions. The labels are GCC internally encoded as a binary tree data structure which results in the end in a ordered tree. Finally, small switch statements can generate a series of bit instructions and branches.

gcc permits to disable jump table generation via -fno-jump-tables. For example if you do branch analysis or program other code analyzers the jump table trick is not easy to parse.

See gcc/stmt.c, especially expand_case() is quite interesting. A simple jump table optimization by subtracting the minimal label value is only applied when optimization for speed is enabled—strange!

A tiny drawback of quagga is a missing feature to signal the host environment when routes change. So it is not simple to start/stop scripts if routes are added or deleted. For example: if you want to add or delete a security association if a route changes then it is not directly possible via quagga. But Linux and other operating systems provides a monitor mode where all relevant network events can be caught by the user space. Linux uses netlink sockets for network related communication between user-space and kernel-space. ip, the command, can be forced to print all network related messages to STDOUT via ip monitor all (under BSD route -n monitor will do the same).

If the IP packet size exceed the link layer maximum transmission unit (MTU, 1500 byte for Ethernet v2) a packet must be fragmented. Yesterday Changli Gao submited a patch that optimize the reassembling process in the kernel. Changli assumption was that fragments arrived in accureate ascending order. He optimized the processing behavior by optimizing the list processing of inet_frag_queue for IPv4 and IPv6 by introducing an additional pointer, called fragments_tail that points to the end of the list. So nothing sophisticated here.

The main point against his patch was the following argument: Linux generates since more then 10 years fragments in descending, in other words reverse order – starting with fragment n, n - 1, n - 2, .... So for Linux this is a noop. But Linux isn’t the only OS on the earth and as stated by Changli all other major operating systems generate fragments in ascending order.

I don’t want to write about the Path MTU discovery (PMTUD) mechanism, but to manually probe for a path MTU it is quite comfortable to use ping or ping6, simple specify a packet size and set the DF bit in the case of IPv4: ping -c 1 -M do -s 1464 google.com. 1506 bytes on wire, 14 byte Ethernet header, 20 byte IPv4 header, 8 byte ICMP header, 1464 byte payload; this is a PPP limitation, Ethernet v2 can transport 1514 bytes on wire and if you do local PMTUD you can discover this limit.

The posted flash advisory list is really long so I tried to update the player. But unfortunately Adobe skipped their 64 bit support (what a piece of software is this anyway – in 2010?) which actually means I had no change to run flash any more! 32 bit combat mode – no thank you, buggy software – no thank you. I installed the dev version of firefox with webm support which works great. OK, many videos aren’t rendered yet but this is a question of time.

Let say goodby to Adobe Flash! ;-)

Today after some time-killing IETF debates I started to analyze the in-kernel BPF filter execution time for different BDP filters. Starting with no filter, which is translated into a simple BPF_RET|BPF_K OPCODE till some more complex instructions. The average execution time lies somewhere at 300ns for no filter and somewhere above 350ns for a simple ICMP filter with 17 CPU instructions on my x86_64 (excluding call overhead).

The next image illustrates this (statistically sampled data):

Lars Eggert posted today a Draft where RFC1106, RFC1110, RFC1145, RFC1146, RFC1263, RFC1379, RFC1644 and RFC1693 are declared as historic documents. But RFC1146 – TCP Alternate Checksum Options – was not superseded by a new standard nor is he defective by any sense. These both arguments are normally the statement why a RFC is declared as historic. In my eyes this is not true for this standard. In the debate Lars argued that the already assigned code points do remain assigned. This guarantee that implementations – not seen in the wild for RFC1146 – are not touched or affected.

I mentioned that TCP can have a legal desire towards a more strong checksum and as an example I mentioned interplanetary TCP. Lloyd Wood pointed out that TCP isn’t suitable for Interplanetary communication. The fact is known sure, but I know several modifications of TCP where the RTO mechanism is adjusted just because to meet interplanetary requirements!

Anantha Ramaiah pointed out a Draft that address exactly the same shortcomings: enhancing TCP checksums mechanism. Lars noticed that it Transport Layer Security (TLS/SSL) can be used to guarantee the integrity of the data even more stronger then as with a plain CRC.

The discussion with Lloyd slided away from the actual topic to some general discussion about TCP and the interplay with RTO. His research background focus on interplanetary communication and it is quite interesting to know about some real world problems.

I stumbled across the default hash size for the different hash tables used in the network subsystem. Hash tables are used as a efficient container for different network subsystems – compared to let say list containers. The optimal complexity of a hash table is O(1), this means access in constant time, no matter how many entries are in the container. The optimum is a theoretical value and requires a hash bucket fill level from maximum ~60 percent as well as good hashing algorithms. Higher workloads tends to collisions, this again shift the complexity of the container from O(1) to O(n). Linux provides the Jenkins Hash function as one of the best hashing algorithm. Some network components use their own hash function because they can do it better because of a good key knowledge.

The fact the the fill level should not be higher they ~60 percent is a little bit problematic. Some major hash table implementation dynamically extend or shrink the hash table size depending on the current workload to guarantee this fill level. Within the Linux kernel this is not as easy as it requires a clever locking mechanism and some other difficult quirks, therefore no dynamic approach is applied. As a consequence the default hash table size is sized for worst case workloads (e.g. server systems, ...).

If I sum up all network related hash tables nearly 0.5 percent of the main memory are use for containers:

TCP established hash table: 4194304 bytes
TCP bind hash table:        1048576 bytes
IP route cache hash table:   524288 bytes
UDP hash table:               32768 bytes
UDP-Lite hash table:          32768 byte

The .text segment of my current kernel consumes only 6241407 bytes! Free memory is bad memory—sure, but wasted memory is bad memory too.

Actually $user posted a regression that he measured a RTO of less then 200ms via tcpdump. Normally this is not possible because Linux bounds the minimum to 200ms. So lets see what the actual trace offers.

RFC 2988 specifies that the minimum TCP Retransmission Timeout (RTO) SHOULD be 1 second. The relative large value was selected to keep TCP conservative and avoid spurious retransmissions. The RFC was written back in 2000 and things changed. The timer and clock granularity of current operating systems is more accurate and allow a more fine grained minimum. Furthermore, analysis had demonstrated that a RTO of 1 second badly breaks throughput in environments faster then 33kB with minor packet loss rate (e.g. 1%).

Therefore current Operating Systems use a RTO smaller then 1 second. Linux defaults to 200ms and FreeBSD to even 30ms. At least Linux implement a algorithm called Forward RTO Recovery to detect spurious timeouts. This also permits the use of a reduced RTO and make the 1 second suggestion superfluous.

Also of impact is the interplay with Delayed ACKs: The TCP Minimum RTO Revisited

UPDATE: $user emailed the tcpdump traces and no spurious timeout triggered packet is identifiable:

000027 IP 1.46799 > 2.47500: 168809236:168812132(2896) ack 1 win 46 <nop,nop,timestamp 1375977402 2077240628>
000024 IP 1.46799 > 2.47500: 168812132:168815028(2896) ack 1 win 46 <nop,nop,timestamp 1375977402 2077240628>
000029 IP 1.46799 > 2.47500: 168815028:168817924(2896) ack 1 win 46 <nop,nop,timestamp 1375977402 2077240628>
000077 IP 2.47500 > 1.46799: ack 168786068 win 16200 <nop,nop,timestamp 2077240629 1375977402>
000006 IP 2.47500 > 1.46799: ack 168787516 win 16200 <nop,nop,timestamp 2077240629 1375977402,nop,nop,sack 1 {168801996:168804892}>
000002 IP 2.47500 > 1.46799: ack 168787516 win 16200 <nop,nop,timestamp 2077240629 1375977402,nop,nop,sack 1 {168801996:168806340}>
000001 IP 2.47500 > 1.46799: ack 168787516 win 16200 <nop,nop,timestamp 2077240629 1375977402,nop,nop,sack 1 {168801996:168809236}>
000002 IP 2.47500 > 1.46799: ack 168787516 win 16200 <nop,nop,timestamp 2077240629 1375977402,nop,nop,sack 1 {168801996:168812132}>
000003 IP 2.47500 > 1.46799: ack 168787516 win 16200 <nop,nop,timestamp 2077240629 1375977402,nop,nop,sack 1 {168801996:168815028}>
000001 IP 2.47500 > 1.46799: ack 168787516 win 16200 <nop,nop,timestamp 2077240629 1375977402,nop,nop,sack 1 {168801996:168817924}>
000203 IP 1.46799 > 2.47500: 168817924:168819372(1448) ack 1 win 46 <nop,nop,timestamp 1375977403 2077240629>
000028 IP 1.46799 > 2.47500: 168819372:168822268(2896) ack 1 win 46 <nop,nop,timestamp 1375977403 2077240629>
000025 IP 1.46799 > 2.47500: 168822268:168825164(2896) ack 1 win 46 <nop,nop,timestamp 1375977403 2077240629>
000024 IP 1.46799 > 2.47500: 168825164:168826612(1448) ack 1 win 46 <nop,nop,timestamp 1375977403 2077240629>

UPDATE II: so after a more exact analysis the posted regression looks like false alarm – so ignore this post.

Yesterday as well as today I worked meticulously to build a own blog software. This post is the first post on a self-hosting basis. In the next couple of days I will publish the software via git as usual. The technique is simple: blog posts are written with your editor of choice (e.g. vim), after that the file is checked into the git repository (database and versioning is done via git) and after that a simple ruby script generates all html pages (via git post hooks). Simple, lightweight and functional.

One tiny extension is image recognition. Each blog post have impact on two pages: the post specific page and the index.html. To link management for image links is done by textile – path substitution is required.

Anyway, the big blocks are already implemented: html file generation, category archive, year archive and last but not least RSS feed (xml 2.0) generator.

Because I see it again and again (to highlight it: I mean in NEW software):

• you MUST use sockaddr, sockaddr_in and sockaddr_in6 since the beginning.Don’t use uint32_t or even worse unsigned long for IPv4 storage. But as you realize this is not protocol independent: sockaddr_in and sockaddr_in6 are container for IPv4(IP Version 4) and IPv6(IP Version 6). You will end up in switch/case statements to distinguish between both protocols. The superior solution is to use struct sockaddr_storage (big enough to also handle UNIX sockets). Currently there is nearly no excuse to use the protocol dependent containers. There are a few exceptions where (e.g. where sockaddr_storage will eat up to much memory) but this is really, really rare.
• gethostbyname() and gethostbyaddr() must be replaced (and also getipnodebyname and getipnodebyaddr)
• MUST also be replaced inet_ntop(), inet_pton() and inet_aton() (e.g. they they do not support scoped IPv6 address)
• in6_addr isn’t guaranteed sufficient to identify a node. The scope information (the interface information) is missing
• Name resolution? use getaddrinfo() and getnameinfo()!

and last but not least: do not hardcode AF_INET or AF_INET6!

To clone the parallelized ns-3 branch you can type the following:

hg clone http://code.nsnam.org/pfeifer/ns-3-para

1. after some days you can update the repository via hg pull http://code.nsnam.org/pfeifer/ns-3-para
2. and update the local copy hg update

BTW: to push the changes upstream type:

hg -v push ssh://pfeifer@code.nsnam.org//home/pfeifer/repositories/pfeifer/ns-3-para

today in the evening I received the following bug report for libhashish (especially the bloom filter implementation):

[...]
../include/libhashish.h:116: syntax error before "pthread_rwlock_t" 
../include/libhashish.h:116: warning: no semicolon at end of struct or union
[...]

Looks pretty forward, but hold on! One line above in the spotted code are some tricky compiler forward declarations so we checked this first with some older GCC versions – no success. After that we focused on glibc and their threading support for older versions and voilà: some today really outdated glibc versions (especially the linuxthread ones, the NPTL predecessor) require to define a additional constant.

At the end: thank you for spotting the bug and why for god’s sake use CISCO premature software?

Libhashish is a hash library for UNIX witch support nearly all functionality seen in other hash table implementations. Furthermore, libhashish implement a lot of different ideas beside the normal hash list chaining strategy. It implement array chaining, list and array chaining with reordering functionality (most often referred elements first) and double key hashing (to lower O(n) complexity in the hash key compare function (normally strcmp()).

Yesterday I added mutex lock support so that the library is now thread clean!

I reworked the netsend commandline parsing code. It now support a more network specific user input. See the following screenshot for netsend help:

Usage: netsend [OPTIONS] PROTOCOL MODE { COMMAND | HELP }
OPTIONS := { -T FORMAT | -6 | -4 | -n | -d | -r RTTPROBE | -P SCHED-POLICY | -N level
-m MEM-ADVISORY | -V[version] | -v[erbose] LEVEL | -h[elp] | -a[ll-options] }
PROTOCOL := { tcp | udp | dccp | tipc | sctp | udplite }
MODE := { receive | transmit }
FORMAT := { human | machine }
RTTPROBE := { 10n,10d,10m,10f }
MEM-ADVISORY := { normal | sequential | random | willneed | dontneed | noreuse }
SCHED-POLICY := { sched_rr | sched_fifo | sched_batch | sched_other } priority
LEVEL := { quitscent | gentle | loudish | stressful }

Through some additional performance measurements I realize some interesting plateau. Two points are of interest, first at ~200 byte and the seconds at 600 byte (the x scale is denoted as DWORD size (uint32_t)

Also quit interesting: the long duration to “warm” the cache, tlb, etc .. (BTW: we talk about microseconds)

New measurements for the mentioned, increased latency if you lock pages physically. As you can see, the violet line (without memory locking) reflect a superior latency behavior (lesser is better).

On the other side, there is one negative peek with mlockall() – but it shouldn’t. After all: mlockall() prevent worst case scenario – the principal task for real-time application. On the other hand, it introduces a small overhead – but why? More kernel studies needed!

The recv() function has a really rare argument: MSG_WAITALL. It tells that the syscall should not return before length bytes are read. The problem is that normally nobody knows how much data is send by the peer node. So if you rely on a particular amount of data and the data isn’t send, this call blocks infinity! On the other hand, a programmer must also handle this kind of failure, because a simple read() of a socket can also block forever. A timeout handler is always needed (alarm() as the simplest solution).

The background is that recv() normally return after length bytes or if a threshold values is raised. sock_rcvlowat() is the function who look if the user want to wait until length bytes are ready or returns earlier. sk_rcvlowat is the socket specific variable which determine the break out szenario.

return (waitall ? len : min_t(int, sk->sk_rcvlowat, len)) ? : 1;

sk_rcvlowat can be set on a socket basis via setsockopt(). Normally sk_rcvlowat is initialized with 1. Therefore a recv() call does block minimum for 1 byte. If you increase sk_rcvlowat beyond the recv() length parameter then min(sk_rcvlowat, length) → length is taken – of course!

recv() will also return if OOB data is received, an error occured or an signal arrived us.

In talks I often noted that in the a big part, pointer casts are dump and futile. The C Standard stated out that a cast to another type raise an “undefined behavior”:

float a = 23.f; uint32_t b = *(uint32_t *)&a;

Depending on the current gcc version this leads to different results in b. Sometimes a is interpreted as a uint32_t type (that what you want – probably) – sometimes the result is 0;

The interesting part come now into play: why 0, why should a compiler catch that user failure and invest CPU cycles here? Why not interpret an values of type x as type y?

The answer is: it is not a service for the user, it is an compiler optimization technique called aliasing.

The root of many optimization challenges in C are pointers. Often it is impossible to predict a values, because a pointer had always the change to modify a memory location. Nor does somebody know how many pointers, points to a particular value. This circumstance prevent the compiler from a lot of optimization.

The optimization is, that the C standard document stated out, that a pointer cannot point to a locations of different type (with the exception of char *) and gcc utilize this circumstance! The compiler can therefor optimize code because he can ensure that they doesn’t interfere.

If you really need transparent access and interpret a value as a values of another types take a union type:

union conv {
    float f;
    uint32_t ui32;
};

due a productive weekend we implement three additional protocols for netsend

• DCCP ( RFC 4340 )
• SCTP ( RFC 2960 )
• UDP-LITE ( RFC 3828 )

So nowadays there are seven supported protocols (if you consider ip and transport layer protocols). TCP, IPv4, IPv6, TIPC and UDP.

Some minor bugs are fixed and code rearanged – the daily work …