Asynchronous libraries performance

I committed next post on LShift's blog.

BTW. This is my 100th post in this blog!

Simple inter-process locks

At LShift blog I wrote about simple inter process locks in Python.

Motoman robot controlled by two Wiimotes

Some time ago I controlled a robot with a Haptic.

Inspired by Johnny Chung Lee I started to work on controlling the Motoman industrial robot using two Wiimote infrared cameras. It's a bit less accurate method than using Haptic, but it's much cheaper.


What you need:

• a robot (or whatever you'd like to control)
• two Wiimote devices
• a software (okay, here's the source, but beware, it's beta, work in progress, not finished and hackish)
• a pen with two infrared diodes

The main problem is that normal infrared diodes are directional. But for this project we need to see the diodes from the side. Normal diodes are only seen from the front. I found that the diode CQY36 is perfect (the first pen below, black one). The other solution is to use two SMD KP-3216F3C diodes (the second pen below).


Both pens have a meomentary switch, so I can turn the leds on when I want to move the robot arm. Unfortunately on the videos you can't see when the leds are lighting, so it can be confusing that sometimes the move of a pen is moving the robot and sometimes not.

First video (rotation on the Y axis is flipped and the video ends with a robot failure):


Other videos:

Useful C extensions (gcc specific)

You think that knowing ANSI C is enough? Well, okay, it's enough. But I found that some gcc extensions are very useful.

All gcc C extensions are listed in the manual.

Here are the extensions I use:

Labels as values
I remember the old assembler days, when you could jmp to to an address from an array. Nowadays in C, you can create an array of pointers to functions and call pointer from array. But jmp is faster and sometimes you don't want to create many small, almost useless functions.

In gcc you can use a trick that's called labels as values. It's like that:

int main(){
    int value  = 2;
    const void *labels[] = {&&val_0, &&val_1, &&val_2};
    goto *labels[value];
    val_0:
        printf("The value is 0\n");
        goto end;
    val_1:
        printf("The value is 1\n");
        goto end;
    val_2:
        printf("The value is 2\n");
        goto end;
    end:
    return(0);
}

Macros as functions
Here is a standard example of a macro with statements that returns a value. It's also a great example of typeof operator in gcc.

#define MAX(a,b)                    \
    ({                              \
    typeof (a) _a = (a);            \
    typeof (b) _b = (b);            \
    _a > _b ? _a : _b; })

Case ranges
Gcc allows to use ranges in case statement. In ANSI C you'd have to enumerate all the values. This code is much prettier:

int main(){
    int value  = 7;
    switch(value){
    case 0 ... 5:
        printf("The value is 0 - 5\n");
        break;
    case 6 ... 10:
        printf("The value is 6 - 10\n");
        break;
    default:
        printf("The value is ?\n");
    }
    return(0);
}

Likely
Have you ever wondered how does gcc convert if statement to assembler, how many branches are created by the compiler? For example here, how many jmp instructions processor must do in the foo() function?

int foo(int i){
    if(i == 0)
        return(1);
    return(2);
}

int main(){
    foo(0);
}

In this case you know more than a compiler. You know that all callings to the foo() are going to be with "0" as the parameter. You can suggest compiler to optimize this by using __builtin_expect and possibly reduce number of jumps.

int foo(int i){
    if(__builtin_expect(i == 0, 1))
        return(1);
    return(2);
}

There are often defined macros:

#define likely(x)    __builtin_expect(!!(x), 1)
#define unlikely(x)    __builtin_expect(!!(x), 0)

Vector extensions
This very powerful extension allows to use mmx/sse code in a portable way. Gcc would choose the best possible extensions during compile time. When you compile code without mmx/sse options, the binary will remain compatible with i386. The downside is that this extension doesn't allow to use all of the features of mmx/sse.

From my point of view the most important feature is to use the bitwise commands. For example this would do binary or on 128 bits:

typedef union{
    int v __attribute__ ((vector_size (16)));
    int i[4];
} __vec_int;


int main(){
    __vec_int a, b, c;
    a.i[0] = 1; a.i[1] = 1; a.i[2] = 1; a.i[3] = 1;
    b.i[0] = 1; b.i[1] = 2; b.i[2] = 3; b.i[3] = 4;
    
    /* do OR here on 128 bits */
    c.v = b.v | a.v;
    ...
}

Sometimes there is a need of using more advanced mmx commands than vector extensions allow. For example you may want to do four compares at a time. Unfortunately this code is specific for sse2 (-msse2).

int main(){
    __vec_int a,b;
    a.v = set_vec_int(1,2,3,4);
    b.v = set_vec_int(4,3,2,1);
    
    /* compare greater than on __m128i */
        __vec_int c;
        c.v = _mm_cmpgt_epi32(a.v, b.v);    /* 0xFFFFFFFF if gt, 0 else*/
    
    printf("a=[%i,%i,%i,%i]\n", a.s[0], a.s[1], a.s[2], a.s[3]);
    printf("b=[%i,%i,%i,%i]\n", b.s[0], b.s[1], b.s[2], b.s[3]);
    printf("c=[%u,%u,%u,%u]\n", c.s[0] ? 1 : 0, c.s[1] ? 1 : 0, c.s[2] ? 1 : 0, c.s[3] ? 1 : 0);
    
    return(0);
}

Command used here _mm_cmpgt_epi32 is ported from Intel compiler, the best documentation for this dialect I found on Microsoft sites. You may want to use gcc equivalent. By the way, don't forget that the sse2 registers (__m128i) must be aligned to 16 bytes (-mpreferred-stack-boundary=4).


Cache stuff
Sometimes it's possible to optimize code by prefetching data. It's quite simple to prefetch data to one line of cache:

__builtin_prefetch(&data[offset], 1); /* 0 - read only, 1 - rw */

On the other hand you may want to store the data without polluting the caches. If you only want to write data (and it's not currently loaded to cache) it could be faster than standard storing. I use this defs (oh. it's mmx specific):

#ifndef MMX
#define STORE(ptr, val)        \
    do{            \
        *(ptr) = (val);    \
    }while(0)
#else
#define STORE(ptr, val)        \
    do{            \
        _mm_stream_si32( (ptr), (val) );    \
    }while(0)

#endif

More?
There are more interesting extensions. Like advanced assembler operands or macros with variable number of arguments.

Emulating exit(3) and moving stack on the fly.

Recently, during coding embedded stuff for industrial robots I had very interesting problem.

I needed to implement exit(3) function. But the system on the robot is very simple. There aren't any kinds of syscalls.

So, the functions exit(3) must emulate the only proper way of exiting the program. It should emulate returning/exiting from main() function.

My friend, Michal Luczaj, found clever way of doing this. The basic idea is to do:

void (*exit)();

void user_main(){
    int whatever;
    /* bla, bla , bla */
    exit();
}

int main(){
    exit = &&final_quit;
    
    /* execute the application */
    user_main();

final_quit:
    return(0);
}

Well, this won't work, because the stack after calling exit() in user_main() is not the stack that should be in main().

That's also my other problem. My robots have very limited stack, so I want to move the stack to other memory area.

The final code emulates exit() and moves the stack. It works like this:

int main(){
    start();
}

int start()
{
    SAVE_STACK_POINTER();
    myexit = &&final_quit;

    new_sp = malloc(128*1024);
    SET_STACK_POINTER(new_sp);

    user_main();
    /* stack broken here - don't do anything please */
final_quit:
    RESTORE_STACK_POINTER();
    return(0);
}

void user_main(){
    myexit();
}

32 or 64 bits?

Just a note, that I posted an article about advantages of 32 bit architecture over 64 bit and why we chose 32 bit at Grono.net.

It's in Polish, but the main point is that in our case Django at 32 bits is consuming about 30% less memory than on 64 bits.

To show the differece, here is output from top command at 64 bits:

VIRT  RES  SHR S %CPU   TIME+  COMMAND
212m  96m 3832 S    0  1:49.61 django '/gallery/3329236/0/'
203m  96m 3120 S    0  1:37.78 django '/gallery/4871149/6/0/'
211m  95m 3832 S    0  1:38.74 django '/mailbox/box/1/'
210m  95m 3824 S    0  1:45.45 django '/gallery/photo/40328359/'
210m  95m 3844 S    0  1:48.43 django '/users/index/'
210m  94m 3848 S    0  1:33.94 django '/users/'

And here from 32 bit:

VIRT  RES  SHR S %CPU    TIME+  COMMAND
68396  62m 3484 S    0  2:06.94 django '/users/433317/'
67716  61m 3488 S    0  1:50.23 django '/gallery/photo/42009962/'
66264  60m 3488 S    0  2:01.94 django '/pub/join/'
65312  59m 3484 S    0  2:08.75 django '/users/'
65148  59m 3508 S    0  1:48.02 django '/users/1533943/friendlist/'
64884  59m 3508 S    0  1:51.48 django '/'

Is 8GB RAM faster on 64bit or on 32bit processor?

A friend asked me if 8 gigabytes of ram is much slower on 32bit than on 64bit linux. The standard 32 bit can handle at most 4GB of ram. To access more ram you have to enable the CONFIG_HIGHMEM64G option in kernel. The question is if this feature make access to memory much slower.

I created basic test to measure ram speed. The program sequentially writes to rather big memory chunk. After first benchmark, as a single process, the program forks to check if the memory access would be much slower for more concurrent processes. The goal is also to make use of more than 4GBytes of memory, so that we know that HIGHMEM is used.

The results showed that, uh, the memory access is as fast on 64 bits as on 32 bits for big memory usage.

My test program is here.

Some of the tests:
1. 4 processes, every uses 1500MB memory

32-bit-machine$ ./test-mem 4 10 1500
For single process:
In 10680.104ms done 13 tests. It means 478.629 mln (read int)/sec

For 4 processes:
In 34514.712ms done 13 tests. It means 148.105 mln (read int)/sec
In 34584.651ms done 13 tests. It means 147.806 mln (read int)/sec
In 34607.142ms done 13 tests. It means 147.710 mln (read int)/sec
In 34653.662ms done 13 tests. It means 147.511 mln (read int)/sec

64-bit-machine$ ./test-mem 4 10 1500
For single process:
In 10817.252ms done 13 tests. It means 472.561 mln (read int)/sec

For 4 processes:
In 35059.194ms done 13 tests. It means 145.805 mln (read int)/sec
In 35102.285ms done 13 tests. It means 145.626 mln (read int)/sec
In 35102.671ms done 13 tests. It means 145.624 mln (read int)/sec
In 35175.010ms done 13 tests. It means 145.325 mln (read int)/sec

2. 10 processes, every one uses 512MB of memory (this is more like context-switching test)

32-bit-machine$ ./test-mem 10 10 512
For single process:
In 10251.710ms done 37 tests. It means 484.412 mln (read int)/sec

For 10 processes:
In 82147.174ms done 37 tests. It means  60.453 mln (read int)/sec
In 82751.646ms done 37 tests. It means  60.012 mln (read int)/sec
In 83004.705ms done 37 tests. It means  59.829 mln (read int)/sec
In 82591.951ms done 37 tests. It means  60.128 mln (read int)/sec
In 82678.590ms done 37 tests. It means  60.065 mln (read int)/sec
In 82652.342ms done 37 tests. It means  60.084 mln (read int)/sec
In 82636.134ms done 37 tests. It means  60.095 mln (read int)/sec
In 82535.299ms done 37 tests. It means  60.169 mln (read int)/sec
In 82535.830ms done 37 tests. It means  60.168 mln (read int)/sec
In 82784.449ms done 37 tests. It means  59.988 mln (read int)/sec

64-bit-machine$ ./test-mem 10 10 512
For single process:
In 10273.896ms done 37 tests. It means 483.366 mln (read int)/sec

For 10 processes:
In 82660.408ms done 37 tests. It means  60.078 mln (read int)/sec
In 82557.546ms done 37 tests. It means  60.153 mln (read int)/sec
In 83497.783ms done 37 tests. It means  59.475 mln (read int)/sec
In 82660.669ms done 37 tests. It means  60.078 mln (read int)/sec
In 82708.567ms done 37 tests. It means  60.043 mln (read int)/sec
In 83360.999ms done 37 tests. It means  59.573 mln (read int)/sec
In 83044.817ms done 37 tests. It means  59.800 mln (read int)/sec
In 83117.576ms done 37 tests. It means  59.747 mln (read int)/sec
In 83245.083ms done 37 tests. It means  59.656 mln (read int)/sec
In 83203.710ms done 37 tests. It means  59.686 mln (read int)/sec

3. 3 processes, every one uses 2048MB of ram

32-bit-machine$ ./test-mem 3 10 2048
For single process:
In 10258.171ms done 9 tests. It means 471.023 mln (read int)/sec

For 3 processes:
In 20643.669ms done 9 tests. It means 234.059 mln (read int)/sec
In 21914.211ms done 9 tests. It means 220.489 mln (read int)/sec
In 24316.862ms done 9 tests. It means 198.703 mln (read int)/sec

64-bit-machine$ ./test-mem 3 10 2048
For single process:
In 10213.609ms done 9 tests. It means 473.078 mln (read int)/sec

For 3 processes:
In 20694.933ms done 9 tests. It means 233.479 mln (read int)/sec
In 23680.936ms done 9 tests. It means 204.039 mln (read int)/sec
In 24266.013ms done 9 tests. It means 199.120 mln (read int)/sec

Trinity choice: nsock over libevent

Everybody knows that Trinity is using nmap.
But what she has to nsock or libevent, well nothing.

Recently I wrote some software using libevent and I'm disgusted. Libevent is poorly documented (except the self-explanatory function names which are suggestive), there are not many examples on the web. Even though I took an effort and wrote few programs.

About a year ago I put my hands on nmap project, I wrote something for nmap's asynchronous networking library nsock.

There are some really interesting differences between these two libraries:

• In libevent you must allocate memory and set event structures by hand, from manual: "It is the responsibility of the caller to provide these functions with pre-allocated event structures.". In nsock event objects are managed by library.
• I thought that EV_PERSIST events should be persistent. I don't get exactly the idea of EV_PERSIST event type in libevent. It's not working for me when I think it should (for example for EV_WRITE). On the other hand nsock doesn't provide any kind of persistent events.
• Libevent provides the api for queuing signals. I haven't got an idea what application could theoretically take a use of such feature. I can't think of any use case for queuing signals in real world applications.
• Nsock executes callback function with the information about a state of an event like if it has succeeded, failed or timeouted. Libevent doesn't. User have to check the socket status by hand.
• In Nsock user can get current time (the time after last select() in main event loop) without syscall using nsock_gettimeofday(), which can speedup program. In libevent you have to use gettimefday().
• Libevent supports multiple polling methods, most notably epoll(), while nsock is using only slow select().
• Libevent could be used for both client or server side. Nsock is build especially for client side, it's possible to abuse it and use it for server side, but it's more like hacking.

The thing I like most in nsock is the easiness of using it. I don't have to worry about event structures. I have the guarantee that sooner or later my callback function will be called. To show the difference I have an example. It's the simplest program I could think of. It registers timer callback with null timeout, million times one after another sequentially.

First libevent example:

#include <stdlib.h>
#include <event.h>

 /* 
 gcc -Wall event_test1.c -levent && time ./a.out
 */

int counter = 0;
struct timeval tv = {0,0};
struct event ev;

void timer_handler(int fd, short event, void *ud){
    event_add(&ev, &tv);
    counter++;
    if(counter > 1000000)
        exit(0);
}

int main(){
    event_init();
    
    event_set(&ev, -1, EV_TIMEOUT, timer_handler, NULL);
    event_add(&ev, &tv);
    event_loop(0);
    return(0);
}

And very similar nsock code:

#include <nsock.h>
#include <stdlib.h>
 
 /* Sorry, some magic with compilation. Nsock isn't standalone library yet! 
 gcc -Wall nsock_test.c -I/home/majek/nmap/nsock/include /home/majek/nmap/nsock/src/libnsock.a -ldnet /home/majek/nmap/nbase/libnbase.a /home/majek/nmap/libpcap/libpcap.a && time ./a.out
 */

nsock_pool nsp; /* global */
int counter = 0;

void timer_handler (nsock_pool nsp, nsock_event nse, void *ud){
    nsock_timer_create(nsp, timer_handler, 0 /*ms*/, NULL);
    counter++;
    if(counter > 1000000)
        exit(0);
}

int main(){
    nsp = nsp_new(NULL);
    nsock_timer_create(nsp, timer_handler, 0 /*ms*/, NULL);
    nsock_loop(nsp, 1000000);
    return(0);
}

Times of execution this programs are very interesting for me. Unbelievably it seems that nsock is more than two times faster!
Libevent averate timings:

real    0m2.271s
user    0m0.640s
sys     0m1.624s

Nsock average time:

real    0m0.941s
user    0m0.392s
sys     0m0.548s

The "user time" shows that libevent implementation of internal structures is much heavier than nsock. Even that nsock should have more work because it's allocating event structures alone, without users help. The "sys time" should be similar for both libraries, but it's not. Strace is going to reveal the issue:

# The loop is reduced to 100 iterations.

# Data for NSOCK
% time     seconds  usecs/call     calls    errors syscall
------ ----------- ----------- --------- --------- ----------------
   nan    0.000000           0       203           gettimeofday

# Data for LIBEVENT
% time     seconds  usecs/call     calls    errors syscall
------ ----------- ----------- --------- --------- ----------------
   nan    0.000000           0       406           gettimeofday
   nan    0.000000           0       101           epoll_wait
   nan    0.000000           0         1           epoll_create
   nan    0.000000           0         1           epoll_ctl

Well, it seems clear that two things are broken in libevent. First, the gettimeofday() is called four times for every event loop iteration, it's unacceptable waste of resources. Second, the epoll() is executed for every event loop, while for nsock even a single select() isn't called. In this particular case, when timer events are registered with Null timeout there isn't a need of executing epoll().

Summary:
From programmers point of view, I like nsock programming style. Unfortunately nsock doesn't have many important features, like epoll or server side sockets handling.

It seems that libevent ain't no perfect either.

Maybe there is a need of async library with easy api like nsock and full-featured like libevent?

Libevent under python

So I want to write asynchronous tcp/ip server in python.

I really hate overblown twisted. The thing I like most in Python is simplicity and easiness to read. Well, twisted in my opinion doesn't have this attributes. It's of course my personal feeling, mostly because I don't know twisted. But such statements are making me sick, at first sight I really don't understand what are they for (from core twisted documentation):

internet.TCPServer(7779, IFingerFactory(f)).setServiceParent(
    service.IServiceCollection(application))

I remember such cascades from Java rather than Python and I dislike Java especially for this way of programming.

Getting back to point. If not twisted than what? Lets try libevent. Stable C library, which is a production standard now. Memcached is using it, Tor is using it, IO also. It must be really professional asynchronous library.

There are also some other async linux libraries, like liboop. Wait a moment, libevent 500k google hits, liboop 25k. Sorry, the only asynchronous library for linux is libevent for now.
(btw. Liboop's api is in my opinion totally broken)

Are there any python wrappers for libevent? Google says about two: libevent-python and pyevent. Both seem abandoned.
I don't like exceptions inside libraries, so it didn't took long to eliminate pyevent:

    Traceback (most recent call last):
    File "./tights.py", line 37, in 
        main()
    File "./tights.py", line 34, in main
        event.dispatch()
    File "event.pyx", line 262, in event.dispatch
    TypeError: exceptions must be strings, classes, or instances, not type

Update: Michael Carter writes in comments that this bug is the fault of pyrex rather than pyevent and that it shouldn't happen in python2.4(I use 2.5). I'll have to take a closer look at pyevent again.

Libevent-python seems to be working. Unfortunately this wrapper removed the concept of 'userdata' passed to callback in favor of class-based approach. The difference is that callback is not called with 'userdata' but it's called on specific class instance, so callback has 'self' object. I personally prefer the 'userdata' approach, but it's quite easy to switch.

Here's an example of simple libevent-python server, which is just printing every data it receives (something like standard echo_server.py example from libevent-python, but simpler)

#!/usr/bin/python
# -*- coding: utf-8 -*-
import socket, signal, libevent

def callback_interrupt(signum, events, event_obj):
    libevent.loopExit(0)

def callback_onconnect(fd, events, event):
    # hack to avoid passing sock_srv from main()
    sock_srv = socket.fromfd(fd, socket.AF_INET, socket.SOCK_STREAM)
    sock, (host, port) = sock_srv.accept()
    conn = Connection(sock, (host, port))

class Connection:
    def __init__(self, sock, addr):
        self.sock = sock
        self.addr = addr
        self.sock.setblocking(False)
        libevent.createEvent(sock, libevent.EV_READ, self.callback_onread).addToLoop()
    
    def callback_onread(self, fd, events, event_obj):
        buf = self.sock.recv(4096)
        if not buf: # just disconnect
            self.sock.close()
            return
        # Yeah, print!
        print "%r %r" % (self.addr, buf)
        # reuse current event
        event_obj.addToLoop()

if __name__ == '__main__':
    # bind.
    sock_srv = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    sock_srv.setblocking(False)
    sock_srv.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)
    sock_srv.bind(('0.0.0.0', 1111))
    sock_srv.listen(5)
    
    libevent.createSignalHandler(signal.SIGINT, callback_interrupt).addToLoop()
    libevent.createEvent(sock_srv, libevent.EV_READ|libevent.EV_PERSIST, callback_onconnect).addToLoop()
    libevent.dispatch()

UPDATE #1:
Here seems to be another way of connecting libevent with python, using raw ctypes: http://william-os4y.livejournal.com/3718.html.

Set process name in python

How to set process name from inside it? I know that nmap can fake name, but the question is how to do this from python.
The code that is doing this magic in nmap:

# from nmap.cc
  if (quashargv) {
    size_t fakeargvlen = strlen(FAKE_ARGV), argvlen = strlen(argv[0]);
    if (argvlen < fakeargvlen)
      fatal("If you want me to fake your argv, you need to call the program with a longer name.  Try the full pathname, or rename it fyodorssuperdedouperportscanner");
    strncpy(argv[0], FAKE_ARGV, fakeargvlen);
    memset(&argv[0][fakeargvlen], '\0', strlen(&argv[0][fakeargvlen]));
    for(i=1; i < argc; i++)
      memset(argv[i], '\0', strlen(argv[i]));
  }

There are some possible ways of doing this from python. Some guys suggest using prctl ioctl. But it didn't worked for me. Also the module proctitle haven't done what I expected.
From time I found rtgraph3d project, I'm a fan of PyInline module. Here's my python code that's working (for me):

import PyInline, time

m = PyInline.build(code=r"""
    #include <Python.h>
    #include <stdio.h>
    #include <string.h>
    
    void set_argv(char *str){
        int argc;
        char **argv;
        Py_GetArgcArgv(&argc, &argv);
        strncpy(argv[0], str , strlen(str));
        memset(&argv[0][strlen(str)], '\0', strlen(&argv[0][strlen(str)]));
    }
    """, language="C")

m.set_argv('very custom python process name')
time.sleep(100)

It looks funny from ps:

majek@tigger:~$ ps aux|grep very
majek    11688  2.6  0.4   7192  4360 pts/21   S+   00:20   0:00 very custom python process name

The mystery of extremly long "grep -i"

It's well known fact, that grep is the fastest way of searching data. The mystery was why "grep -i" took so much longer than standard, case-sensitive grep.

Finally depesz found the reason.

GNU pth instead of pthread: hardcore python tuning

Problem
I've been working on speed of an application written in python. While doing strace I found out that the most of syscalls were futex(). This futexes came from python's internal synchronization code. But the application never used any kind of threading!

Most of the users never actually realize that python is doing synchronization between threads even when threads aren't used. It's not so bad, those futex() calls are very quick about 7usecs one. But they are executed thousands times!
Sample "strace -c":

% time     seconds  usecs/call     calls    errors syscall
------ ----------- ----------- --------- --------- ----------------
 67.62    0.000570           0     15192           futex
 10.91    0.000092           0       896           sendto
  7.00    0.000059           7         8           stat
  5.34    0.000045           0      1936           poll
  3.32    0.000028           0      1076           recvfrom
  2.73    0.000023           1        28           open
  2.02    0.000017           3         6           write

Workaround
To get rid of futex() calls one can compile python without support for threading (./configure --without-threads). The fall of this method is that some modules depend on threading, like postgresql wrapper psycopg.

There is also other method. It seems that python supports GNU pth library. This library emulates threads in userspace, using pthread compatible interface. The only non-trivial thing is to get rid of pthread and use pth while python compilation (even though pth should be supported by python out of the box).

Enabling pth is not easy, but doable. Here's the compilation procedure thanks to my friend Primitive:

$ sudo apt-get install libpth-dev
$ wget http://python.org/ftp/python/2.5.1/Python-2.5.1.tar.bz2
$ wget http://ai.pjwstk.edu.pl/~majek/dump/pyconfig.h.in-pth-patch.diff
$ tar xjf Python-2.5.1.tar.bz2
$ cd Python-2.5.1
Python-2.5.1$ cat ../pyconfig.h.in-pth-patch.diff|patch -p0
patching file pyconfig.h.in
Python-2.5.1$ ./configure --with-pth  --prefix=/usr
Python-2.5.1$ find . -name Makefile -exec sed -i "s/-lpthread/-lpth/" {} \;
Python-2.5.1$ sed -i "s/-pthread//" Makefile
Python-2.5.1$ sed -i 's/$(srcdir)\/Python\/thread_pthread.h//' Makefile
Python-2.5.1$ make

Benchmarks
In corner case the time gained is about 25%-30%. The test program is not complicated at all. We know that importing modules needs synchronization. So let's do only imports:

#!/usr/bin/python
for i in xrange(1000000):
    import os

Average results for standard python 2.5.1, using pthread:

real    0m2.061s
user    0m1.728s
sys     0m0.332s

Average results for patched python 2.5.1 using pth:

real    0m1.572s
user    0m1.560s
sys     0m0.008s

What's with those futexes?
Well, as I suggested futexes are gone when using pth. Here are strace results for python with pthreads:

% time     seconds  usecs/call     calls    errors syscall
------ ----------- ----------- --------- --------- ----------------
 99.99    1.014676           1   1000020           futex
  0.01    0.000067           0       142           read
  0.01    0.000057           0      4504           _llseek

And for fixed python with pth:

% time     seconds  usecs/call     calls    errors syscall
------ ----------- ----------- --------- --------- ----------------
100.00    0.000050           0      4504           _llseek
  0.00    0.000000           0       142           read

Interesting gettimeofday() on x86_64

During doing strace() on application I found that there are no gettimeofday() syscalls. That's nothing new, for x86_64 experts, but it's interesting for me.

Here is an example of the code:

#include <stdio.h>
int main(){
        printf("start\n");
        gettimeofday(NULL,NULL);
        printf("stop\n");
        return(0);
}

Sample strace from i386:

...
write(1, "start\n", 6)                  = 6
gettimeofday(NULL, NULL)                = 0
write(1, "stop\n", 5)                   = 5
...

And the same code on x86_64:

...
write(1, "start\n", 6)                  = 6
write(1, "stop\n", 5)                   = 5
...

Is it possible to abuse icmp?

I wonder what's going to happen when malicious user will inject crafted icmp packet with some error information (like Port Unreachable) to tcp connection. Will the connection be closed? You may think that to inject something like this it's needed to guess sequential numbers. That's not exactly correct. Icmp payload can be relatively small, specification says it has to carry at least 8 bytes from OSI 3th layer, so only tcp source and destination port must be included.

I can assume that you're going to use google. To block your connection I have to only send 65K packets with payload: from google, to you, from 80port to, and sequentially select your local port. I should guess after while. That's even less than 65K possibilities, on standard linux there are less than 32K possible local ports (see proc parameter ip_local_port_range).

The question is how common tcp stacks are interpreting such crafted Icmp message.

There are also other possibly vulnerable applications. For example most dns servers, to make recursive queries use source port 53 (see bind 'query-source address' option). How dns servers react for icmp errors with relatively small payload? Is it possible to perform Dos attack using this method?

UPDATE #1:
Well, of course port number in tcp header uses only 16 bits. So to 8 bytes in icmp payload should fit: source, destination port, seq number.

I change my question. How common tcp stacks interpret icmp packets with too short payload?

UPDATE #2:
Linux seems to be immune for this kind of attack. The function that parses icmp errors for tcp transmission is in linux/net/tcp_ipv4.c:tcp_v4_err(). The code says, that payload must be at least 8 bytes long. Source and destination port in the payload must be correct and sequence number must be in correct range. In other case icmp packet is simply dropped.

Magia w tcp/ip linuxa. Bug czy ficzer?

Z tcp/ip dzieje się coś dziwnego, po odpaleniu skryptu, pierwsze dwa połączenia są poprawnie nawiązane. Natomiast system nie widzi trzeciego połączenia. Syn-ack po sieci śmiga, a jądro z jakichś powodów go nie zauważa.
Netstat pisze:

tcp        0      0 127.0.0.1:60885         127.0.0.1:8081          ESTABLISHED
tcp        0      0 127.0.0.1:8081          127.0.0.1:60885         ESTABLISHED

tcp        0      0 127.0.0.1:60886         127.0.0.1:8081          ESTABLISHED
tcp        0      0 127.0.0.1:8081          127.0.0.1:60886         ESTABLISHED

tcp        0      0 127.0.0.1:60887         127.0.0.1:8081          ESTABLISHED
tcp        0      0 127.0.0.1:8081          127.0.0.1:60887         SYN_RECV   

Taka magia, że jest SYN_RECV w jedną stronę a ESTABLISHED w drugą. Kiedyś posiedzę nad tym dłużej i wyjaśnię :)

Oto jak zreprodukować to dziwne zachowanie:
a) Odpal skrypt.
b) Na innej konsoli uruchom

tcpdump -np -i any port 8081

Jak już powiedziałem, z trzecim połączeniem dzieje się magia.

A może ktoś zna racjonalne wyjaśnienie? Jakiś ficzer protokołu tcp/ip czy bug kernela?

POPRAWKA:
Wyjaśniło się. To jest ficzer jajka, wymyślony przez Van Jacobsena. Chodzi o to, żeby w przypadku gdy kolejka się przepełni nie odrzucać połączenia. Host będzie się dobijał dłużej, i możliwe że za którymś razem będzie miejsce dla niego w kolejce.

Ja bym to zaimplementował po prostu dropując pierwszy pakiet SYN, lecz widać z jakichś powodów dropują dopiero ACK.

Aby wyłączyć takie zachowanie można użyć:

 echo 1 > /proc/sys/net/ipv4/tcp_abort_on_overflow

Niskopoziomowy debugging w linuxie, czyli gdzie się podziały DR0-DR7?

Przypomniałem sobie, że przecierz i386 ma rejestry służące do debuggowania! A świat o nich zapomniał tak dawno.
Nie bardzo jeszcze wiem do czego może się przydać ich używanie, ale to nie jest ważne :)

No to do roboty!

Wiadomo że gdb potrafi używać sprzętowego debugowania, komunikaty w stylu poniższego już nie raz śniły mi się:
(gdb) awatch *(0x8049534)
Hardware access (read/write) watchpoint 1: *134518068

Pytanie tylko, jak to działa. To co wiem, to że na pewno ptrace
jest podstawą działania gdb. Choć z drugiej strony w dokumentacji
ptrace nie ma żadnej wzmianki na temat ustawiania rejestrów DR.

Skrobnijmy pierwszy programik:
#include <stdio.h>
int main(){
unsigned long db_regs;
asm volatile ("mov %%dr0, %0" : "=r"(db_regs));
printf("%08lx\n", db_regs);
return(0);
}

majek:~/mutex$ gcc -Wall a.c
majek:~/mutex$ ./a.out
Segmentation fault

No tak, to było do przewidzenia, przecierz w dokumentacji intela pisze jednoznacznie: "The debug registers are privileged resources; the MOV instructions that access them can only be executed at privilege level zero." Hmm, ale gdb potrafi ustawiać je bez roota.

Weźmy nowy, równie prosty program, ale tym razem interesuje nas, jak działa gdb:
#include <stdio.h>
int i;
int main(){
for(i=0; i<4; i++);
return(0);
}

majek:~/mutex$ gcc -Wall b.c
majek:~/mutex$ strace gdb ./a.out 2>log
(gdb) maint show-debug-regs on
(gdb) awatch i
Hardware access (read/write) watchpoint 1: i
(gdb) run
Starting program: a.out
[....]
watchpoint_hit (addr=8049534, len=-1, type=data-write):
CONTROL (DR7): 000f0101 STATUS (DR6): ffff4ff1
DR0: addr=0x08049534, ref.count=1 DR1: addr=0x0000000, ref.count=0
DR2: addr=0x00000000, ref.count=0 DR3: addr=0x0000000, ref.count=0
remove_watchpoint (addr=8049534, len=4, type=data-read/write):
CONTROL (DR7): 000f0100 STATUS (DR6): ffff4ff1
DR0: addr=0x00000000, ref.count=0 DR1: addr=0x0000000, ref.count=0
DR2: addr=0x00000000, ref.count=0 DR3: addr=0x0000000, ref.count=0
Hardware access (read/write) watchpoint 1: i

Więc gdb jednak jakoś odczytał zawartość DR0-DR7, a nawet je ustawił.
Zajrzyjmy do loga strace:
majek:~/mutex$ cat log <palka> grep ptrace <palka> grep USER
[....]
ptrace(PTRACE_PEEKUSER, 28498, offsetof(struct user, u_debugreg) + 24, [0xffff4ff1]) = 0
ptrace(PTRACE_POKEUSER, 28498, offsetof(struct user, u_debugreg) + 28, 0xf0100) = 0
ptrace(PTRACE_POKEUSER, 28498, offsetof(struct user, u_debugreg), 0) = 0
[....]

No to mamy już całą magię. Jeszcze rzut okiem na <sys/user.h> I mamy już pełną jasność, ptrace z pierwszej linijki odczytuje DR7, a kolejne dwie linijki zapisują dane do DR7 i DR0.

No to programik testowy, tym razem dłuższy więc w zamieszczam tylko w osobnym pliku.
majek:~/mutex$ gcc -Wall c.c && ./a.out
#28848 child started
#28847 parent started
before change: DR0=0x00000000 DR7=0x00000000
after change: DR0=0x08049a3c DR7=0x00050101
#28847 parent stopped
#28848 got SIGTRAP
#28848 child stopped

Hurray! Udało się. Zmieniając zmienną wywołujemy SIGTRAP dla naszego procesu, i SIGCHLD dla procesu który nas śledzi.

Dla czytelnika zostawiam pytanie do czego użyć prezentowanej techniki.

Myślę, że niektórzy mogą się domyślać co kombinuję, ale zostawmy to na kolejny wpis.