Miracles and machinery

Christiane and I decided to have a wonderful and relaxed evening. We hadn't been to the cinema for a while and so we decided to have our little fun there. No top-notch intellectual movie today, we just wanted something entertaining and so we decided to watch "The Golden Compass".

After a looooooong time of commercials and another short break, the film started and we enjoyed the first 90 minutes (until the point were Iorek Byrnison becomes king of the ice bears again and heads with Lyra towards freeing her friends), then the film went off. 10 minutes of darkness followed, whereafter a robust, elderly woman entered the room and told us that something was probably broken and they were trying to fix it. We could have our money back now or we could wait for the film to continue, but she could not tell whether and when this would be the case. Most of the people left the room and Christiane and I were just starting to think about relocating to one of the more comfortable seats when another cinema employee came in and told us that the projection machine was completely broken and we would not see the movie's end today.

So far for the reliability of non-digital film projectors. Let's hope we soon see all the movies using digital projection (with a highly available backup store and at least one primary backup for the projector hardware...). I wonder whether this hope will influence the next raise in cinema ticket prices. ;)

iMpressive

Just saw the German iPhone commercial on TV for the first time. I already tried it myself when I was in Portland some weeks ago and I'm still thinking about buying one. Can someone give me the money, please?

Qt + Processes + I/O redirection

I had a look at QtEmu today, a Qt4 frontend for Qemu. The tool is really nice, however I missed an important feature: I would like to add arbitrary command line parameters for Qemu startup, because some of my requirements (serial I/O, disabling graphics support) are not met by typical frontends, because they are quite special.

I therefore added a new edit box to QtEmu enabling me to insert my parameters. However, nothing happened in my terminal and I wasn't able to see any output from Qemu. iMichael and I found out that the QProcess class used by QtEmu does send its standard input and output to its parent by default. The solution for output is easy: standard and error output streams can be redirected using the QProcess::setProcessChannel() method.

Redirecting input is a bit harder (but I needed it, because I'd like to interact with the Fiasco kernel debugger). There is no channel for writing to a QProcess in Qt4. However, some Trolltech developers already came up with a solution for interactive processes, which helped in our case, too.

Berlin adolescents attack blacks - Police say: "no xenophobia"

What is it then, if three young men attack a black couple because of the color of their skin??

Lexer rules need ordering...

I was trying to parse lines like

import <foo/bar.h>

using ANTLR, when I found out that ANTLR's lexer rules have a precedence: rules are tried in the order they appear in the .g file. In my case, I had a rule matching a keyword such as "import" and a rule matching anything that is a word. Playing around with rules and their order, I found that my grammar works, if I write the keyword rule before the word rule, otherwise I get a "rule not reachable"-error.

This is how you get the file name out of the line above:

fragment DIGIT : '0'..'9';
fragment CHAR : 'a'..'z' | 'A'..'Z';

IMPORT : 'import' ;
GT : '>' ;
LT : '<' ;
WORD : CHAR (CHAR|DIGIT)*;
WS : (' '|'\t'|'\n'|'\r')+ { self.skip(); } ;

filename : WORD ('/' WORD)* '.' WORD ;

import_r : IMPORT LT f=filename GT {print $f.text};

Bastei, ANTLR

I haven't posted for a while, time for an update. When not hacking L4Env, I am currently pursuing new roads.

First, I have been playing around with the Bastei OS Framework a little. Bastei is a C++-based framework for managing resources in a multi-server operating system. It has been implemented as an experiment by Norman Feske and Christian Helmuth. My first little contribution was a small Hello-World client-server example that can be used as a Getting-Started-Tutorial. Since Bastei is not available to the public up to now, I don't post it here. But the time will come...

Secondly, I am playing with ANTLR (ANother Tool for Language Recognition), a shiny parser-generator written in Java, which is able to generate parsers in many different languages such as C, C++, C#, Java, Python, ... you name it. I am currently working through Terence Parr's ANTLR Reference which I can definitely recommend for anyone interested in using ANTLR 3.0. Using ANTLR I did two things up to now:

• I wrote an IDL parser for our L4Env IDL files that generates an abstract syntax tree from those files. Now that the parser works, I could easily write an IDL compiler - given ANTLR's strong template engine this should be pretty nice. I'm however not sure that this is something really new so I'll have a look at other things.
• For debugging my grammars I wrote Tree2Dot, a tool to convert ANTLR's string representation of ASTs into GraphViz' Dot format. Sure enough this was before I reached page 191 in Parr's ANTLR reference, where I found out that this is already a builtin feature of ANTLR and I could have used it pretty easily. ;)

Now it's time to find out what I can use my newly learned parsing skills for. Several things come to mind:

• As a first experiment I'm probably going to write a tool that takes IDL files and checks whether all the functions have Doxygen comments attached. If not, we'll add templates to the file. If the tool gets really cool, it will also use existing Doxygen comments and adapt them if parameters change etc.
  
• Starting with the IDL parser I'd like to investigate how far we can go generating unit tests for specific interfaces. Typical approaches use programmer annotations to find out what specific parameters to a function are, what the parameters' domains are, and in which order functions of an interface need to be called. However I'm not convinced of the concept of annotations, because programmers are lazy. Therefore I'd like to minimize the amount of additional work posed on them and try to automate this work using static analysis.
• Norman Feske gave me some other directions related to the Bastei framework:
• Bastei uses statically allocated message buffers for its IPC framework. One could use a C++ parser to generate a callgraph from Bastei code and therefore try to determine the necessary message buffer size.
• Bastei's IPC framework implements IPC using C++ streams (which results in code that can be heavily optimized by the C++ compiler). However in contrast to IDL there is no compile-time checking for function parameters anymore, servers need to trust clients to provide the right arguments in the right order and vice versa. Using a static analysis tool, we can look at clients and servers and detect if arguments are passed in a wrong way - this will mainly invoke counting the arguments passed given a certain opcode as well as having a look at the types of arguments.
  

Cup finals

Although my favourite team already had been kicked out in round one, I was keen to watch yesterday's cup finals between Stuttgart and Nurnberg. The two most impressing teams of the recent league season faced each other for the third time.

Stuttgart has impressed me by becoming German champions against all odds and by playing intelligent and beautiful football throughout the year. I'm happy for their win, because I count this as an advantage of German football in comparison to the big European Leagues where you only have two or three teams to win at all.

Nurnberg was mainly of interest for me because they bought Dynamo's top striker Joshua Kennedy last summer. Unfortunately, after playing some minutes for Australias national team in the World Cup, Kennedy got injured in the training camp and never played for his team this season. However, Nurnberg suprised everyone by reaching a place qualifying them for next year's UEFA cup. One of the impressing facts about them was their ability to beat German champions Stuttgart in both of their matches.

So yesterday both teams faced each other for the third time. Like many others I watched the game on TV and agree with people who found it one of the most entertaining football matches of the last years. Both teams did a great job and even though Nurnberg won it by 3-2 in the extra time, Stuttgart also would have deserved it. After Cacau was sent off in minute 30, they played 90 minutes with only 10 players. Even reaching extra time was a great accomplishment for them.

National Security (2)

Someone recently attacked Kai Diekmann's car. Diekmann is the head of Germany's most controverse boulevard magazine - BILD. Unfortunately, I cannot feel sorry for him and tend to think that this serves him quite well, since he is responsible for a magazine that is keeping German masses undereducated and wrong-informed.

However, what gives me a bad feeling about this, is that the Red Army Fraction also started their terrorism by attacking things like warehouses. Just when they noticed that this didn't work they started killing people. We should not get back to these things again.

National Security (1)

German conservative politician Roland Pofalla has accused Wolfang Thiers of not being a serious president of the German Bundestag anymore. The reason for that has been Thierse's criticism of the methods German police is using to track down potential participants of protests against next week's G8 meeting (which in fact was shared by justice secretary Brigitte Zypries).

I'm convinced that Wolfgang Thierse was right. Taking smell probes of innocent people is definitely a sign of the state misusing its power, even if this is covered by laws. Reading people's mail is a sign of misuse. Preventing people from making use of their civil right to stand up when things go wrong, is also a sign of misuse. This was fortunately relaxed by a court today. All this is definitely near to the methods used by dictators and authoritarian states.

I definitely do not agree with all the criticism and the points that are made by G8 opponents. But in a democratic society we should respect their rights and not criminalize them for having a different opinion.

Splinter

I was experimenting with SPLint yesterday. It is a tool for statically analysing C source code and is able to find errors regarding uninitialized variables, memory allocation errors and such things. Source code can further be annotated to get even more information out of the checker.

What annoyed me when I used SPLint was the amount of output. For my local L4 files it gave lots of errors and warnings. I decided, that colored output might ease the task of reading the interesting parts of it and so I put together a small Python script, called Splinter, which takes SPLint's output and colorizes it, so you can easily find warnings, their explainations, the corresponding function names etc.

It's probably quite hacky, because I wrote it in about an hour, but it works for me and if you intend to use SPLint, you should definitely give it a try. Version 0.1 uses my own private colors. Future versions might get more configurable.

Whose bread I eat...

There's this German saying about people typically tending to take the opinion of their superiors. It translates to something like "Whose bread I eat, whose song I sing."

Alan Posener earned some fame today for posting an opinion about the boss of Bild, a German yellow press paper, because he did exactly the opposite. He works for the same publishing company. Posener became even more famous, when his bosses tried to censor him and removed his article from his newspaper's weblog. The text already had been spread.

SCons and vim

I recently played around with SCons, a build system alternative to GNU/Make. It is quite handy and relieves programmers from a lot of work. Building a program from two C files is as easy as putting

Program(['foo.c', 'bar.c'])

into a SConstruct file and running scons which will compile object files from foo.c and bar.c and link them to program foo. Cleaning up everything is easy, too. scons -c will do the trick. Apart from being easy for daily use, SCons is quite powerful. SConstruct files are Python scripts and so you get the whole power of a programming language for creating your builds.

As I revealed in an earlier post, I like the vim editor very much. When I started editing SConstruct files, I also wanted to use vim's beautiful syntax highlighting abilities with it. In command mode, you can type set filetype=python and syntax coloring works. But in real life, you don't want to type this every time you edit a file, so it would be nice, if vim detects the file type for you. It does this automatically for .c, .cpp, .sh and many more file types, but up to now it does not know about SConstruct and SConscript.

However, extending vim to recognize these is very easy using vim's autocmd features. These
let you specify actions that will be taken upon certain events, for instance when a new buffer is opened. I added two lines to my .vimrc in order to get SCons files highlighted as Python code:

autocmd BufReadPre SConstruct set filetype=python
autocmd BufReadPre SConscript set filetype=python

The syntax for autocmds is easy: After the autocmd keyword you specify the event for which you want to register this command. In our case it is before a new buffer (=file) is read. Thereafter you specify a pattern for which this applies. In our case SConstruct and SConscript files are handled, it is also possible to use regexes here. In the last part we specify the command that is executed upon the event. Here we set the file type to be Python and voila, syntax coloring works.

Evil Empire

This text provides another view on Anti-Americanism in Germany than the one we are used to. Nothing to add from me.

Edit, March 31st: There is another article that covers the European approach to islamic fanatism.

Eurosys 2007

I spent most part of my last week in Lisbon, Portugal. Besides being an interesting (albeit surprisingly western-European) city, it was the location of this year's EuroSys conference. Although it was just the 2nd such event, I think the organizers are on their way of establishing it as one of the major systems conferences world-wide. There were quite some nice ideas in the conference and I'd like to point you to my favorite papers from this conference.

Some of these papers are not available yet, I'll try to update the links some time in the future.

• Marek Olszewski, Adam Czajkowski, Keir Mierle, Angela Demke Brown: JIT instrumentation - a novel approach to dynamically instrument operating systems
• Anil Madhavapeddy, Alex Ho, Tim Deegan, David Scott and Ripduman Sohan: Melange: Creating a functional internet (not online yet.)
• Joseph Tucek, James Newsome, Shan Lu, Chengdu Huang, Spiros Xanthos, David Brumley, Yuanyuan Zhou and Dawn Song: Sweeper: A Lightweight End-to-End System for Defending Against Fast Worms.
• Kristis Makris, Kyung Ryu: Dynamic and Adaptive Updates of Non-Quiescent Subsystems in Commodity Operating System Kernels. (not online yet.)
• Sameh Elnikety, Steven Dropsho, Willy Zwaenepoel: Tashkent+ - memory-aware load balancing and update filtering in replicated databases
• Jake Wires, Mike Feeley: Secure file system versioning at the block level (not online yet.)
  

HipHop can also be music...

Normally I'm not a fan of hiphop or rap music. I don't even know the difference. ;)

However, yesterday I discovered Monzy and his really nerdy first song called "Kill Dash Nine". I love it, because it is full of geekisms. My favourite part is "I last a mythical man-month, you a one-minute man."

VIM

My favourite editor, vim, is a very complex tool. If you search the web, you will find many places, where people tell you that even if you are an experienced vim user, you only know a subset of its features. Every once in a while you get to know another useful feature.

Vim is sometimes also annoying. For instance I was oftentimes annoyed when I hit the q key followed by another key and ended up in macro recording mode. Before I learned that I could exit this mode by hitting q another time in comand mode, I was really frustrated. Thereafter it only got on my nerves. Until today I decided to find out what's so interesting about this record mode.

By hitting q you tell vim that you want to record a macro. If you hit a number or a letter thereafter, you tell vim into which register you want this macro to be stored. So hitting qq will end up recording a macro into register q. Now you can do anything you want with vim: insert text, search for things, open new files, ... When you are done, hit q for another time. Now the macro is recorded and you can re-run it using @ where is the name of the register you stored your macro in.

This feature came in handy today. I had to wrap a lot of one-liners with #ifdef X and #endif. So I recorded a macro that

1. Entered insert mode.
2. Opened a new line.
3. Inserted #ifdef X
4. Moved one line down.
5. Opened another new line.
6. Inserted #endif
7. Exited insert mode.

Thereafter the boring task of inserting those ifdef's was just some keystrokes and I realized that I should have learned this feature earlier.

Now can somebody tell me how I can store macros for reusing them later on?

Speeding up your compiler

I recently played around with ccache. This tool caches compiled C/C++ object files. Whenever you recompile a file, it checks whether the corresponding object file is in the cache and the compiler run may be saved.

You may ask, why we need this tool although we already have build systems that determine, when files need to be recompiled. The answer is, that build systems make their decisions upon file modification times and the existence of an older object. If the object is missing - for instance because you ran "make cleanall", make will trigger a rebuild. ccache however takes a preprocessed file and matches its checksum with the one it has cached. If both match, the cached object file is used and you save the time you'd otherwise need for running the compiler.

My benchmarks took place in our L4 environment - I compiled some applications without their objects being cached. Then, I ran "make cleanall" and started the build again, this time with caching enabled. The (reasonable) speedups are shown in the picture. We can see two things:

• C++ (Dice, C++ small) builds are sped up more than C builds (the rest). This is because compiling a C++ file typically takes much more time which is then saved by ccache.
• Large builds (L4Linux, Dice) are sped up more than small ones (cUnit, ...), because they include more compiler runs.

Makes you feel hit by a train

Literature is beautiful. There are loads of Terry Pratchetts and Jasper Ffordes to make you laugh and sometimes think about the wisdom that lies deep beneath their jokes. There is Nick Hornby taking you for a tour of someone else's absolutely usual life.

Literature is not always about great deeds or true heroes. Literature doesn't always make you laugh. Sometimes it is there to make you cry. It makes you feel sick. Words that hit you as if a train was crossing your path. Stories that make you want to put aside the book because you know that what happens will end up in a mess making you feel terrible for the rest of the day or even more. But on the other hand you simply can't let go, because you are enchanted by the words.

Even though (or exactly because?) the story is narrated in many different ways, even though you have to build it in your head from the patches of information you gain from the book, even though there is much more than a simple story in the book and even though you cannot tell which parts of the story are true and which ones are phantasy, even though it is crowded of anti-heroes - some books may give your thoughts (if not your life) a new direction.

Jonathan Safran Foer's "Everything is illuminated" is one of those books. Go and get a read.

Poetry

Geek-parody on the German poem "Der Erlkönig" by Johann Wolfgang von Goethe.

Smoke while you may...

Last week my favorite students club met again for its annual plenum. Apart from electing our new heads, we had a very strong, unintellectual and non-objective discussion about whether we wanted to permit smoking in our club or not. Unfortunately, the smokers once again won with arguments like that smokers drink more beer and are therefore economically more important for us.

Spiegel online features smoking in a nice squib.