tail -f /var/log/messages | grep vegard

Space invaders?

2010-01-26T22:28:00.003+01:00

After my exams in December, I relaxed by writing a sort of space game using C++/SDL/OpenGL:

I ripped the sprites from Space Invaders and Galaga/Galaxian, please forgive me. If whoever wants to play/hack, the source code can be found here:

http://github.com/vegard/spaceinv

The video is a bit poor, mostly because the frame rate is supposed to be 60 FPS, but the Ogg/Theora capture was 25 FPS while the actual gameplay was probably closer to ~10 while doing the capture. Need to fix that. It looks better when playing.

First Jato release

2009-09-10T18:16:00.003+02:00

So I somewhat promised to say something more on my project for the Google Summer of Code.

I participated for the first time, and it was really a great experience. This is the first time I've been paid to do what I would probably have done in either case (because I immensely enjoy it), namely to work on an interesting free software project. So this time it was Jato, a new implementation of the Java Virtual Machine.

Jato is written in C and aims to be a JIT-only compiler/VM. So before the summer started, it wouldn't run a lot of Java programs. It couldn't even run the trivial "Hello World", but more about that later. It could do a few things like (java.lang.)String operations, but that was mostly because it was riding piggyback on another VM, Jam VM, which would load classes and interpret a lot of the library code (i.e. most of the standard Java API implemented by GNU Classpath).

My own project was to replace the parts that were borrowed from Jam VM with completely new, shiny code. Well, in fact, I had already worked on a standalone library called cafebabe, which would parse the Java .class file and present it to C programs using a very thin layer of structs -- the idea was to do as little as possible with the actual data and just make it easily accessible, e.g. so cafebabe doesn't do any verification of the bytecode or make sure that a class is its own superclass.

So we linked this library with Jato, and that worked pretty well. (I believe strongly in modularisation; with the class loader in a separate library, there's no way to do stupid things like making the class loader itself depend on the rest of the VM for functioning properly.) There were problems, of course, the biggest being that after developing in my own private branch for a couple of weeks, the rest of the project with its three other GSoC student participants was moving ahead too quickly for me to keep up; I had to "fix" just about every new mainline commit, since most of the VM data structures (classes, methods, fields) now had different names, different fields, etc.

At around this point, we started to notice that Jam VM wasn't being used for nearly as little as just class loading. In fact, static initializers (the "<clinit>" methods) and their calls were all being interpreted and executed by Jam VM, not the JIT compiler of Jato. And of course, once we started using Jato for those methods which had previously been executed by Jam VM, we found tons of bugs everywhere: The core VM (mostly my code replacing that of Jam VM), including improperly implemented Java semantics, missing bytecode instruction handlers, and the compiler (instruction selection, liveness analysis, register allocation). But it was fun, and extremely educative.

Did you know that a simple System.out.println() will make a whopping 650550 Java-method calls? That's using GNU Classpath for the Java API.

So we had to implement a lot of stuff just to make that work. In fact, we have so much infrastructure that we can even run a few other programs. And thus it was decided that it was time to make a release. The version 0.0.1 announcement:

http://thread.gmane.org/gmane.comp.java.vm.jato.devel/1725

The "next big" missing feature is garbage collection. I expect that'll be version 0.0.2. In other words, if you're interested in Java, garbage collection, or just compilers in general, you're welcome to join us...

Our team consisted of:

Pekka Enberg; Original creator, project manager and mentor.
Tomek Grabiec; His original project proposal included implementing exception handling, but he ended up somwhat like Ingo Molnar of the Linux kernel; Tomek also implemented a generic radix tree, implemented the basic threading support (java.lang.Thread), rewrote large parts of the register allocator, wrote the VM side of the JNI interface from scratch, and also did a lot of other core-VM work. Tons of other things too, including a lot of debugging.
Arthur Huillet; Floating-point support, register allocator fixes, other missing bytecodes, also a lot of debugging. Various other things.
Eduard-Gabriel Munteanu; Ported Jato mostly to x86-64. A tough task, since the i386 parts were moving at close to light speed.

The Jato IRC logger

2009-09-10T17:59:00.005+02:00

Here's the recipe for the Jato IRC logger. Nothing fancy, but works surprisingly well.

/home/vegard/jato-irc-logger/irssi-config:

settings = {
       core = {
               real_name = "#jato IRC logger";
               user_name = "vegard";
               nick = "jato-irc-logger";
       };

       "fe-text" = {
               actlist_sort = "refnum";
       };

       "fe-common/core" = {
               autolog = "Yes";
               autolog_path = "logs/$0/%Y-%m-%d.txt";
       };
};

servers = (
       {
               address = "irc.freenode.net";
               chatnet = "Freenode";
               port = "6667";
               autoconnect = "Yes";
       },
);

chatnets = {
       Freenode = {
               type = "IRC";
               autosendcmd = "/^msg nickserv identify vegard password";
       };
};

channels = (
       {
               name = "#jato";
               chatnet = "Freenode";
               autojoin = "Yes";
       },
);

/home/vegard/jato-irc-logger/screenrc:

screen irssi --config=irssi-config

/home/vegard/jato-irc-logger/start-logger.sh:

#! /bin/bash -e

screen -c screenrc -dmS jato-irc-logger

crontab:

# m h  dom mon dow   command
0 * * * * rsync -r -t --chmod=a+r jato-irc-logger/logs/#jato/ vegardno@hostname:www_docs/jato-irc-logs

/etc/rc.local:

#!/bin/sh -e

cd /home/vegard/jato-irc-logger
sudo -u vegard ./start-logger.sh &

exit 0

kmemcheck in mainline

2009-06-17T14:29:00.002+02:00

First of all, I should say that on April 22, I went to Denmark to give a talk on kmemcheck. I was invited to DIKU (Datalogisk Institut på Københavns Universitet) by Julia Lawall, who held a workshop on Coccinelle (or, more generally, "finding bugs in operating system software"). It was really nice to be there, not (just) because I got a chance to talk about kmemcheck, but because I learned so much from all the other talks! Feel free to check out my slides.

I had asked my university (the University of Oslo) beforehand to sponsor the trip in exchange for a trip report, but I got no reply to my e-mail. I guess they don't see any value in collaboration with universities abroad.

And now, for the news: Yesterday, kmemcheck was merged in mainline Linux! It is quite an incredible feeling after having spent so much time to make it work properly... (Not to mention the rebase marathon that ensued after Linus initially rejected it)

I had also asked Redpill Linpro (a Norwegian/Swedish open source developer) beforehand to sponsor my work on kmemcheck for the summer, but they apparently weren't interested. At least I got a polite reply. (Instead, I got a stipend from Google for working on Jato for the summer, but more on that in a later post!)

Hiragana tutor

2009-05-21T00:10:00.004+02:00

An evening spent with Unicode charts, HTML, CSS, and JavaScript resulted in this:

The online Hiragana tutor

If you find any errors, please tell me.

LADSPA

2009-05-05T11:38:00.002+02:00

Hurrah for LADSPA.

I started (yet another) project, this time it's a sort of audio synthesisizer and sequencer library. I've always been fascinated with digital audio, since there are so many cool things we can do with it! Like e.g. create and apply filters, warp the sound waves any way we want, add cool effects, and generally do things that I can't otherwise do. Not to mention that I like music... but who doesn't? :-)

My program isn't revolutionary in any way; in fact, the short story is that the program tries to "simulate" the way real, analogue audio components can be put together, as e.g. an effect rack (the guitar connects into a distortion module, which connects into a reverb module, which connects to the amplifier, which connects to a mixer board, which connects to the speakers, etc.). I stole most of the concepts from an existing non-free (but very nice) program called Reason [http://www.propellerheads.se/]. I'm sure there are also free programs that do what I'm trying to do (but part of the fun is doing it myself).

One really nice thing is that there exist a lot of free plugins that do most of the work when it comes to synthesizing instruments and applying effects. These plugins are implemented using a free library, called LADSPA (Linux Audio Developer's Simple Plugin API) [http://www.ladspa.org/], which is the interface between host programs (such as the one I'm making, but also others, like Audacity) and the plugins.

So the plugins form a directed, acyclic graph, where the nodes with no outgoing edges are the speakers (or, well, sound card), and the leaf nodes are typically synthesizers (instruments). Arranging the plugins in this way is a really nice thing, because it ensures that there are no vicious feedback cycles (if we really want some kind of feedback, like reverb, we can implement it as a plugin!) It also means that we can do a topological sort to find the order in which the plugins are to be "run".

Anyway, I've implemented these plugins for my program: A LADSPA plugin wrapper, so we can load any LADSPA plugin as a plugin for my program. An ALSA playback plugin for playing audio in real time. A WAV playback plugin for streaming to disk using libsndfile, which supports a few more formats beside WAV, by the way. A MIDI input sequencer, which reads MIDI files and presents the notes as "control output" to the synthesizer plugins. A mixer plugin, which simply combines several inputs into one output.

It would probably be possible to create an ALSA capture plugin for capturing audio in real time as well. That would be pretty cool, and we'd have a software guitar amp in no time. There seems to be a problem with using blocking ALSA streams, though, because the application sleeps while the sound card is playing the data, and we're left with almost no CPU-time to actually synthesize the sound. This can probably be solved using threads, though.

Anyway, I made something cool (I think, anyway), by hooking the CMT organ [http://www.ladspa.org/cmt/] to a plate reverb [http://plugin.org.uk/], and feeding some classical pieces into the MIDI sequencer (which now supports polyphonic songs!):

Will probably work some more on this, try to write some plugins (I have a few ideas), actually implement error handling (oops), and try to add the missing fundamental features (like reading the correct MIDI tempo, stop output at the end of the MIDI file, etc.).

One of the goals of the library is to be small and efficient, and not accept inferior solutions because they're easier to implement (some trade-offs are allowed). The next major feature will probably be to add multi-core support using pthreads, so that all CPU cores can be utilized.

The code itself can be found at github (as usual): http://github.com/vegard/trick2

Linux kernel 2.6.27 exploits

2009-04-06T15:23:00.004+02:00

I found two exploits of the Linux kernel back in January.

The first one is a crash in inotify, where a locking imbalance would unlock the inotify mutex twice before returning to userspace. It happens only if the buffer passed to read() was an invalid userspace address. It's fixed in mainline and went into -stable last month (if I recall correctly), though I can't say the fix has showed up in the Fedora kernel yet. The result is usually a BUG in the kernel log with list corruption. The system is mostly unusable afterwards, probably because the program is holding some lock at the time that it is terminated by the kernel. So it's a local DOS.

The second one is a deadlock in splice() code, which happens because splice needs to lock two mutexes, and it needs to drop them at one point too. So with two or more threads executing concurrently, they may grab them in opposite order. Oops. The result is that the process hangs as an unkillable zombie. This may or may not be so bad. If you run the exploit several times, you can end up with any number of zombies, and for some reason I don't know, zombies count in the load average, so with, say, 20 zombies, the load will rise up to around 20 (even though these processes don't actually use the CPU). I guess this makes for a nice local DOS, though. I tried to submit a fix, but it didn't make it to mainline (or -stable, or any other distribution that I know of) yet. It doesn't seem that anybody else is working on a fix either.

I guess the moral of the story is to review existing kernel code (as well as new patches), because it isn't actually perfect. I found these exploits by reading the source code and writing some test programs to test my theories, and I can testify that this method works well for finding errors.

My brain is open

2009-03-21T00:29:00.002+01:00

This week was Brain Awareness Week. I found that my university was giving some lectures on the brain, so I attended them all. As expected, it was quite interesting. I knew the basic concepts from before, but it really helps to hear different people talk about different subtopics, as it gives me a fuller picture of how this wonderful organ works.

In any case, I couldn't help feeling inspired, so yesterday I started writing my very own brain simulator. No, it doesn't really do all that much. But here's what it does do:

Implements a brain using a neural network. The neural network is actually just a fully connected, weighted graph, where the weights represent the strengths of the synapses. The neural network is currently static (it remains unchanged during the lifetime of the organism), and the model is extremely simple. It supports two types of neurones, excitatory and inhibitory neurones, but that's about it.

Implements an environment for the brain, e.g. a body and a physical world with which the creature can interact. Actually, this particular environment consists of an empty space (no gravity), and a target, which, when touched by the creature, regenerates in a different position. The body of the creature has two sensors (relative position, i.e. distance to the target and relative velocity, i.e. the speed at which we are moving towards the target) and four outputs. Each of the four outputs can be thought of as a jet pack that can be used to accelerate the creature in a particular direction (up, down, left, right).

This creature's purpose in life is therefore, as you might have guessed, to reach targets.

I've been using two programs to simulate my worlds, these are:

The "evolver": This program is responsible for developing the "genes" of the creature. Those genes are actually just the NxN matrix that represents the neural network graph (where N is the number of neurones, or nodes in the graph). It works quite simply by randomizing the genes and running a simulation with a creature that has this brain. By checking the number of times that the creature reaches the target (each simulation runs only a fixed number of steps), we have a measure of how successful that particular set of genes is.

When we have found a reasonable brain configuration (e.g. a creature that can reach a target in around 2-3% of the simulations), we start duplicating it and perturbing the configuration slightly. In this way, we have, in each generation, a set of brain configurations corresponding to the original brain plus nine different variations of the original brain. Now each of the brain configurations are given their chances to reach their targets; the most successful configuration becomes the parent of the next generation of creatures. And we have evolution!

It actually took about 8 hours to find the configuration of the creature that is shown in the video below.

The "player": This program will run a simulation, but also display it on the screen. By default, it uses the most successful brain configuration found so far. This program is what generated the video below. There's not much more to it; the simulation is exactly the same as in the "evolver". (But without visualization, the evolver can run much faster.)

So without much further ado, here's the result:

Notice how it often overshoots a little. A problem with an earlier brain configuration was that it would start circling around the target in bigger and bigger orbits, eventually disappearing from the screen altogether. I think it's really interesting, though, to see that it actually works. It surprised me.

The source code for these programs can be found at the GitHub project website. I'm not really planning to make a project out of this (other than what you see here), but patches are welcome, as always :-) Source code is GPL version 2.

Chipmunk experiments

2009-03-15T15:54:00.007+01:00

I've been playing with Chipmunk lately. It is a C library that simulates physics in two dimensions, and is intended for use in games. It's quite easy to use, but there is a bit of overhead in setting up graphics since I have to do that on my own. I'm using OpenGL through the SDL library, and it works quite smoothly. Here is the result of today's dabbling:

There are two important fundamental concepts in Chipmunk: Bodies and collision shapes. What is the difference? A body has the usual properties like mass, position, velocity, etc. However, a body does not have an area (a shape). That is the purpose of collision shapes. A collision shape does not have any of the properties of a body, it merely defines a shape (such as a circle or a rectangle). The relationship between these two concepts is that multiple shapes can be attached to a body. Only shapes can collide; bodies do not collide by themselves.

The balls in the video above were constructed using one collision shape (a circle shape) for each of the three bodies. They were rendered using an 8x8 OpenGL 2D texture (loaded from a PNG image) on a quadrilateral (GL_QUADS). Easy as pie.

The rope was more difficult to make. For a long time, the rope would either disintegrate slowly (because it was being pulled apart by gravity), or explode (the line segments would vibrate quite violently).

When making the rope, we need another fundamental Chipmunk object: The joint. Joints are used as constraints in the simulation. A constraint is something that keeps an object from moving freely. There are different kinds of joints: Pin joints, slide joints, pivot joints, and groove joints. For example, the pin joint simply stitches together two bodies at certain offsets from the body's centre. When one body moves, the joint will cause the other to follow.

My rope uses slide joints. The only difference from a normal pin joint is that the joint allows a certain flexibility: The "stitch" can be given a minimum and a maximum length, so that the bodies can get closer together or further apart before the joint's constraint takes effect. We can easily imagine the maximum length property as that of a string connecting two objects. The string will keep the objects from getting too far apart, but it will also bend if the objects are closer together than the length of the string.

The slide joints connect the line segments of the rope. Each line segment consists of four collision shapes attached to a single body. The four collision shapes are all circles, laid out side by side. These four circles have fixed positions with regards to each other. They're not actually drawn as circles, but as solid rectangles (GL_QUADS). The rope has 30 such line segments, so that's 30 bodies and 120 collision shapes.

Finally, we have two fixed bodies at either end of the rope. These bodies have infinite mass, are not affected by gravity, and have no collision shapes. (Actually, they're not added to the Chipmunk space, so they are not affected by any forces at all.) This is what keeps the rope in place. And to my great surprise, the way in which these bodies are connected to the rope seems to be what determines the quality of the simulation. At first, I was using pin joints to connect these stationary bodies to the endpoints of the rope. It wasn't until I replaced them with slide joints that the rope actually got as smooth as it is in the video above.

I'm currently toying with the idea of putting a cart with wheels on the thread and controlling the wheels with the arrow keys. If that works, I think it could make for a nice game element as a variation on the paddle of e.g. Breakout.

Update:

"Happy hacking"

2009-02-24T02:00:00.001+01:00

Richard M. Stallman was at the university (University of Oslo) today, and he gave a talk titled "Copyright vs. Community in the Age of Computer Networks - Free software and beyond". I was there, of course. It was an interesting topic, though I cannot say that I agree with everything he stands for.

He explained about the Four Freedoms of the Free Software Foundation [http://www.gnu.org/philosophy/free-sw.html], in short:

0. The freedom to run the program.
1. The freedom to study and modify the program.
2. The freedom to distribute the program.
3. The freedom to redistribute your modified program.

He also talked briefly about the history of copyright, to give a background for the origin of copyright law in the first place. Again, in short:

Question: Why do we have copyright at all?
Answer: To encourage the creation of "works" that benefit the society as a whole.

Then he compared this original role of copyright law with how it is used in practice today -- or perhaps misused. According to Stallman, copyright law is something that the "megacorporations" abuse in order to squeeze as much money out of the consumer market as possible. It is used for the benefit of these megacorporations by exploiting the rest of the society.

With this background, he went on with a proposal for the future laws of copyright. The most interesting point was this:

* Things like software, recipes (for food, which are shared freely among cooks anyway -- paraphrased), and works of documentation (such as encyclopedias, dictionaries, etc.) should all be outside the scope of copyright law.

(There were also proposals for shortening the copyright duration, e.g. for books of fiction, to, say, 10 years.)

And this is the point where I actually disagree -- above all the Four Freedoms is a more fundamental one: The freedom to decide whether you want to give away your program's source code, or whether you want to sell only the license to run a program (which cannot be inspected or modified at will).

I agree that Free Software _is_ superior to proprietary software (I mean as a model, not in the quality of the software itself). But we should not force this on anybody through laws. If I want to sell my compiled program, then I should be able to do that. If I want to sell my book of fiction, I _should_ be able to do it and have the right to stop others from redistributing it. More importantly, if somebody wants to buy my book of fiction and comply with my terms, then they should be able to do that!

If we must disallow proprietary software in order to have "freedom", then that freedom is not worth it. If Free Software must defend its existence, then it should do so by appealing to its users, not by changing the laws in disfavour of proprietary software.

It's a bit like Meno's paradox: "You can neither search for what you know, because you would already know it. Nor for what you don't know, because you would not know for what you are looking."

How can the laws be changed if people don't support Free Software to begin with? And, assuming that they do, there would be no reason to change the law, because they would already have discarded proprietary software of their own, free will.

I think that we would be much better off concentrating only on why the Freedoms are beneficial for society, rather than trying to change the laws and forcing the Freedoms upon us. And we are really lucky, because we currently have that choice. And many people have made their decision already -- including me.

Now, there is one more thing I would like to add to the discussion, and that is not about software, but about other kinds of works, like motion pictures and fiction litterature. I think the same principles should apply here: You shouldn't have the right to make unauthorized copies of a book you've bought (much less of books you haven't bought). If you don't respect the license of the author, you simply don't have the right to own a copy of the work in the first place.

I agree that this is hard to enforce in practice -- illegal file sharing over the Internet can never be stopped, because of the nature of the Internet. And this medium is not very likely to disappear either. All we can hope for, and I believe that this will happen, is that authors and artists will do the same thing that programmers have been doing for two decades now -- to give their works away gratis.

Of course, there are people doing this already, for example by distributing their works by the Creative Commons family of licenses. But still, the amount of such, we could say "free content", is not even close to that of "commercial content". And how can we change that? How can we make artists and authors give away their hard work for free, and how can we create communities where free content is valued more than commercial content, much like we have communities where Free Software is valued more than proprietary software? Now THAT is something I think we could do to combat the so-called "digital piracy".

Bloat

2009-01-25T23:17:00.004+01:00

Dear Gnome,

This is completely ridiculous. According to top, "clock-applet" is using 353M virtual memory, of which 17M is resident. I have no swap partition, so it really makes me wonder why those 336M were allocated in the first place. If they are not resident, and not in swap, what are they? Blank pages? mmap()ed files which can be swapped in on demand?

There is also a column for "shared memory", which says 12M. Does that mean that 12M out of those 353M are shared with one or more other processes? What is this shared memory, library code and mmapped files?

Isn't 17M also too much for "clock-applet"? It should be one of the simplest applications that run on my desktop. It would be interesting to know what all of this memory is used for. I think that most of it is library code. And here's an indication...

$ ldd /usr/libexec/clock-applet
 linux-vdso.so.1 =>  (0x00007fffb1fff000)
 libpanel-applet-2.so.0 => /usr/lib64/libpanel-applet-2.so.0 (0x000000000062c000)
 libX11.so.6 => /usr/lib64/libX11.so.6 (0x000000000083b000)
 libXau.so.6 => /usr/lib64/libXau.so.6 (0x0000000000b46000)
 libgnomeui-2.so.0 => /usr/lib64/libgnomeui-2.so.0 (0x0000000000d48000)
 libSM.so.6 => /usr/lib64/libSM.so.6 (0x0000000000fe2000)
 libICE.so.6 => /usr/lib64/libICE.so.6 (0x0000000004d22000)
 libbonoboui-2.so.0 => /usr/lib64/libbonoboui-2.so.0 (0x0000000006c5b000)
 libgnomevfs-2.so.0 => /usr/lib64/libgnomevfs-2.so.0 (0x00000000011ea000)
 libgnomecanvas-2.so.0 => /usr/lib64/libgnomecanvas-2.so.0 (0x00000000064a7000)
 libart_lgpl_2.so.2 => /usr/lib64/libart_lgpl_2.so.2 (0x00000000060ef000)
 libecal-1.2.so.7 => /usr/lib64/libecal-1.2.so.7 (0x00000000077c7000)
 libedataserverui-1.2.so.8 => /usr/lib64/libedataserverui-1.2.so.8 (0x0000000001c1c000)
 libebook-1.2.so.9 => /usr/lib64/libebook-1.2.so.9 (0x0000000001453000)
 libgnome-2.so.0 => /usr/lib64/libgnome-2.so.0 (0x00007f61a9ca3000)
 libpopt.so.0 => /lib64/libpopt.so.0 (0x00007f61a9a99000)
 libedataserver-1.2.so.11 => /usr/lib64/libedataserver-1.2.so.11 (0x00007f61a986f000)
 libsoup-2.4.so.1 => /usr/lib64/libsoup-2.4.so.1 (0x00007f61a962b000)
 libbonobo-2.so.0 => /usr/lib64/libbonobo-2.so.0 (0x00007f61a93b6000)
 libbonobo-activation.so.4 => /usr/lib64/libbonobo-activation.so.4 (0x00007f61a919b000)
 libORBit-2.so.0 => /usr/lib64/libORBit-2.so.0 (0x00007f61a8f2c000)
 libgthread-2.0.so.0 => /lib64/libgthread-2.0.so.0 (0x00007f61a8d27000)
 librt.so.1 => /lib64/librt.so.1 (0x00007f61a8b1e000)
 libglade-2.0.so.0 => /usr/lib64/libglade-2.0.so.0 (0x00007f61a8905000)
 libxml2.so.2 => /usr/lib64/libxml2.so.2 (0x00007f61a85a8000)
 librsvg-2.so.2 => /usr/lib64/librsvg-2.so.2 (0x00007f61a8373000)
 libdbus-glib-1.so.2 => /usr/lib64/libdbus-glib-1.so.2 (0x00007f61a8153000)
 libgconf-2.so.4 => /usr/lib64/libgconf-2.so.4 (0x00007f61a7f15000)
 libpolkit-gnome.so.0 => /usr/lib64/libpolkit-gnome.so.0 (0x00007f61a7d0a000)
 libpolkit-dbus.so.2 => /usr/lib64/libpolkit-dbus.so.2 (0x00007f61a7afe000)
 libpolkit-grant.so.2 => /usr/lib64/libpolkit-grant.so.2 (0x00007f61a78f3000)
 libgtk-x11-2.0.so.0 => /usr/lib64/libgtk-x11-2.0.so.0 (0x00007f61a731e000)
 libpolkit.so.2 => /usr/lib64/libpolkit.so.2 (0x00007f61a7105000)
 libgdk-x11-2.0.so.0 => /usr/lib64/libgdk-x11-2.0.so.0 (0x00007f61a6e66000)
 libatk-1.0.so.0 => /usr/lib64/libatk-1.0.so.0 (0x00007f61a6c46000)
 libgio-2.0.so.0 => /lib64/libgio-2.0.so.0 (0x00007f61a69d2000)
 libpangoft2-1.0.so.0 => /usr/lib64/libpangoft2-1.0.so.0 (0x00007f61a67a4000)
 libgdk_pixbuf-2.0.so.0 => /usr/lib64/libgdk_pixbuf-2.0.so.0 (0x00007f61a6587000)
 libpangocairo-1.0.so.0 => /usr/lib64/libpangocairo-1.0.so.0 (0x00007f61a637c000)
 libcairo.so.2 => /usr/lib64/libcairo.so.2 (0x00007f61a6107000)
 libpango-1.0.so.0 => /usr/lib64/libpango-1.0.so.0 (0x00007f61a5ebe000)
 libfreetype.so.6 => /usr/lib64/libfreetype.so.6 (0x00007f61a5c25000)
 libfontconfig.so.1 => /usr/lib64/libfontconfig.so.1 (0x00007f61a59f3000)
 libgobject-2.0.so.0 => /lib64/libgobject-2.0.so.0 (0x00007f61a57b0000)
 libgmodule-2.0.so.0 => /lib64/libgmodule-2.0.so.0 (0x00007f61a55ad000)
 libglib-2.0.so.0 => /lib64/libglib-2.0.so.0 (0x00007f61a52cb000)
 libdbus-1.so.3 => /lib64/libdbus-1.so.3 (0x00007f61a508d000)
 libgweather.so.1 => /usr/lib64/libgweather.so.1 (0x00007f61a4e75000)
 libpthread.so.0 => /lib64/libpthread.so.0 (0x00007f61a4c58000)
 libc.so.6 => /lib64/libc.so.6 (0x00007f61a48e6000)
 libm.so.6 => /lib64/libm.so.6 (0x00007f61a4661000)
 libxcb-xlib.so.0 => /usr/lib64/libxcb-xlib.so.0 (0x00007f61a445f000)
 libxcb.so.1 => /usr/lib64/libxcb.so.1 (0x00007f61a4244000)
 libdl.so.2 => /lib64/libdl.so.2 (0x00007f61a403f000)
 libgnome-keyring.so.0 => /usr/lib64/libgnome-keyring.so.0 (0x00007f61a3e2d000)
 libuuid.so.1 => /lib64/libuuid.so.1 (0x00007f61a3c28000)
 libssl.so.7 => /lib64/libssl.so.7 (0x00007f61a39d9000)
 libcrypto.so.7 => /lib64/libcrypto.so.7 (0x00007f61a3675000)
 libz.so.1 => /lib64/libz.so.1 (0x00007f61a3460000)
 libavahi-glib.so.1 => /usr/lib64/libavahi-glib.so.1 (0x00007f61a325d000)
 libavahi-common.so.3 => /usr/lib64/libavahi-common.so.3 (0x00007f61a3050000)
 libavahi-client.so.3 => /usr/lib64/libavahi-client.so.3 (0x00007f61a2e40000)
 libresolv.so.2 => /lib64/libresolv.so.2 (0x00007f61a2c28000)
 libselinux.so.1 => /lib64/libselinux.so.1 (0x00007f61a2a0b000)
 libutil.so.1 => /lib64/libutil.so.1 (0x00007f61a2808000)
 libgailutil.so.18 => /usr/lib64/libgailutil.so.18 (0x00007f61a2601000)
 libsasl2.so.2 => /usr/lib64/libsasl2.so.2 (0x00007f61a23e6000)
 libcamel-1.2.so.14 => /usr/lib64/libcamel-1.2.so.14 (0x00007f61a216b000)
 libplds4.so => /lib64/libplds4.so (0x00007f61a1f67000)
 libplc4.so => /lib64/libplc4.so (0x00007f61a1d63000)
 libnspr4.so => /lib64/libnspr4.so (0x00007f61a1b26000)
 libgnutls.so.26 => /usr/lib64/libgnutls.so.26 (0x00007f61a187b000)
 libgcrypt.so.11 => /lib64/libgcrypt.so.11 (0x00007f61a1608000)
 libORBitCosNaming-2.so.0 => /usr/lib64/libORBitCosNaming-2.so.0 (0x00007f61a1401000)
 /lib64/ld-linux-x86-64.so.2 (0x0000000000110000)
 libgsf-1.so.114 => /usr/lib64/libgsf-1.so.114 (0x00007f61a11c3000)
 libcroco-0.6.so.3 => /usr/lib64/libcroco-0.6.so.3 (0x00007f61a0f87000)
 libpng12.so.0 => /usr/lib64/libpng12.so.0 (0x00007f61a0d61000)
 libnsl.so.1 => /lib64/libnsl.so.1 (0x00007f61a0b47000)
 libXcomposite.so.1 => /usr/lib64/libXcomposite.so.1 (0x00007f61a0944000)
 libXdamage.so.1 => /usr/lib64/libXdamage.so.1 (0x00007f61a0742000)
 libXfixes.so.3 => /usr/lib64/libXfixes.so.3 (0x00007f61a053c000)
 libexpat.so.1 => /lib64/libexpat.so.1 (0x00007f61a0313000)
 libXext.so.6 => /usr/lib64/libXext.so.6 (0x00007f61a0102000)
 libXrender.so.1 => /usr/lib64/libXrender.so.1 (0x00007f619fef8000)
 libXinerama.so.1 => /usr/lib64/libXinerama.so.1 (0x00007f619fcf6000)
 libXi.so.6 => /usr/lib64/libXi.so.6 (0x00007f619faed000)
 libXrandr.so.2 => /usr/lib64/libXrandr.so.2 (0x00007f619f8e5000)
 libXcursor.so.1 => /usr/lib64/libXcursor.so.1 (0x00007f619f6db000)
 libpixman-1.so.0 => /usr/lib64/libpixman-1.so.0 (0x00007f619f496000)
 libcap.so.2 => /lib64/libcap.so.2 (0x00007f619f292000)
 libXdmcp.so.6 => /usr/lib64/libXdmcp.so.6 (0x00007f619f08c000)
 libgssapi_krb5.so.2 => /usr/lib64/libgssapi_krb5.so.2 (0x00007f619ee5d000)
 libkrb5.so.3 => /usr/lib64/libkrb5.so.3 (0x00007f619ebbb000)
 libcom_err.so.2 => /lib64/libcom_err.so.2 (0x00007f619e9b7000)
 libk5crypto.so.3 => /usr/lib64/libk5crypto.so.3 (0x00007f619e792000)
 libcrypt.so.1 => /lib64/libcrypt.so.1 (0x00007f619e559000)
 libssl3.so => /lib64/libssl3.so (0x00007f619e327000)
 libsmime3.so => /lib64/libsmime3.so (0x00007f619e0fc000)
 libnss3.so => /lib64/libnss3.so (0x00007f619dda1000)
 libnssutil3.so => /lib64/libnssutil3.so (0x00007f619db84000)
 libsqlite3.so.0 => /usr/lib64/libsqlite3.so.0 (0x00007f619d91b000)
 libtasn1.so.3 => /usr/lib64/libtasn1.so.3 (0x00007f619d70a000)
 libgpg-error.so.0 => /lib64/libgpg-error.so.0 (0x00007f619d507000)
 libbz2.so.1 => /lib64/libbz2.so.1 (0x00007f619d2f6000)
 libkrb5support.so.0 => /usr/lib64/libkrb5support.so.0 (0x00007f619d0ec000)
 libkeyutils.so.1 => /lib64/libkeyutils.so.1 (0x00007f619cee9000)

I think that's insane. Is all of this really needed? As a random example, what is libcom_err.so? Oh, of course...

$ rpm -q -f /lib64/libcom_err.so.2
e2fsprogs-libs-1.41.3-2.fc10.x86_64

$ yum search e2fsprogs-libs
[...]
e2fsprogs-libs.i386 : Ext2/3 filesystem-specific shared libraries and headers

So I wonder... is this why the memory usage of clock-applet blows up, does it really matter, and can we do anything about it?

I have a feeling that this is yet another sign of how the GNU/Linux desktop is heading the wrong way. It smells a lot like bloat :-(

Vegard

Recursive type definitions in C

2008-11-11T20:39:00.007+01:00

Hi,

It's been a while -- I've been mostly busy with university. Maybe I won't try to follow four classes next year. In other news, we didn't make it (with kmemcheck) for 2.6.28 either. Oh well. We did at least make an impression by discovering two more bugs in 2.6.28-rc.

Now for the topic of this post: Recursive type definitions in C. More specifically, the types I want to write about are not structs, but function pointers. We may use typedefs to define types which refer to function pointers:

typedef void (*funcpointer_t)();

Not strictly necessary to make it a new named type, but it helps readability. This is all well and good; we can declare variables that hold function pointers, declare functions that take function pointers as parameters, or even declare functions that return function pointers (to functions with this specific signature):

funcpointer_t x;

void do_a(funcpointer_t f);

funcpointer_t do_b(void);

Now, what I really wanted to do was to create a parser in C where a variable would hold the next function to call, and where the function itself returned a (function) pointer to the next function to call (i.e. the next state of the parser). It would look something like this:

funcpointer_t init_state(const char *token) {
   /* ... */
   return &some_other_state;
}

funcpointer_t some_other_state(const char *token) {
   /* ... */
   return &some_other_state;
}

void parse() {
   funcpointer_t state = &init_state;

   while (token = read_token())
       state = state(token);
}

Okay, so this looks quite good. But how do we define funcpointer_t? Defining structs that have pointers of the same type is quite easy, since the compiler already knows about the type as soon as you start defining it. The most obvious example is the linked list:

struct list_node {
   struct list_node *next;
   /* ... */
};

Another possibility includes forward declarations, where we simply declare that a type exists, without defining it:

struct a;
struct b {
   struct a *x;
};

The same goes for functions. They can refer to themselves, since we must provide their name at the start of their definition, or declare them beforehand. But how can we do this with function pointers?

Vegard

"Scribe" and cross-compiling for Windows

2008-09-16T21:26:00.002+02:00

Hi,

First of all: Scribe. That is my new pet project. Actually, I don't know how serious it is yet. But I've made a Project out of it; maybe somebody else who is interested will come along and help. We'll see.

But what is it? Well, it's really just a demo so far. A demo of a "3D pixel engine". It started out as an experiment to see how the graphics from "The Legend of Zelda: Link's awakening" would look in 3D. So I took the Link sprites and some desert tiles and wrote a C++ program that used OpenGL to render it in perspective. And it looked quite good. Well, I must admit that I'm a huge fan of pixel art. It's just so incredible how much spirit and soul you can put into a 16x16 bitmap! And most 3D games out there use high-resolution textures with bilinear filtering and who knows what else to try to make it look halfway realistic...

I actually wrote this code around the end of October 2007 (just before I started working on kmemcheck), and it's been lying in my "programming" folder ever since. I recovered it the other day and thought that I should publish it as an open source/free software program, simply because I have no reason not to. I probably won't have that much time to develop this further, but maybe somebody else will find it interesting and pick it up. It's open source, these things do happen!

There was one major hitch, though. I can't distribute the Zelda graphics. And copyright law has to be upheld! (As an open source/free software programmer, what other position can I take?)

I decided to look around the net for some free graphics, and free graphics I found! In particular, I found bubble league, the website of Alan Trullinger. Apparently he had planned to make some RPG game and had spent a summer making the graphics for it. Apparently, the game was also never released, so he gave away all the graphics for free (distributed under the Creative Commons license). This is how my program looks using his files:

That's not too bad, is it? The little guy can walk around and jump. (The animation is an incredible piece of work, with 8 frames worth of animation in each direction!)

(Of course, nothing beats the Zelda graphics, but that's a different story.)

Are you interested in trying it out? Perhaps you are even interested in contributing something to it? In either case, I've created a git repository for the project at http://github.com/vegard/scribe/.

(Side note: GitHub is a really nice place. I haven't used it that much yet, but everything there is easy and pleasant and just works. It's really worth trying out if you're looking for git hosting. End of note.)

All right. On to the second part of this post: Cross-compiling programs for Windows on Linux. Did you ever try to build MinGW on Linux, only to discover after hours of compiling the compiler, that it doesn't really work? (I don't remember exactly what went wrong, maybe it was missing Windows headers, or missing Windows libraries, or something. I must have suppressed the memories.) Well, there is a solution to that problem too.

Use Wine! I installed Dev-C++ on my Fedora Linux using Wine. Then I created a project inside Dev-C++, imported my source code, installed a few Devpaks, and... it worked. A slight (but only slight) elaboration of this process can be found in the Win32 build instructions for "Scribe".

The only problem I had was that the program wouldn't link unless the linker directives were put in the right order. But that's shame on me for being spoiled with shared libraries (I built with -static to avoid DLL hell).

REP STOS -- part 2

2008-08-29T22:00:00.005+02:00

I finally did it.

I fixed the problem with single-stepping REP STOS (and MOVS) instructions on the P4. (Look in the blog archive to find the original post.)

At first, I wanted emulate the instructions completely. But it wasn't really that easy. My naïve implementation did support different register/data widths. But I soon hit some real show-stoppers. It turned out that the kernel will use REP STOS or MOVS on strings which may not be aligned naturally. This means that memory accesses may now cross a page boundary, which is a big problem. Now we suddenly have to look for page boundaries, and in the case of REP MOVS, we must watch out for both the ESI and EDI registers.

The reason is of course that pages are tracked one by one, and if we cross over to a new page, we have to make sure that it is also marked present (P flag) in the page tables before touching it. Two consecutive pages are also not guaranteed to have consecutive shadow-memory pages (in fact, that's very unlikely), so we should also take care of changing shadow-memory pointers upon hitting a page boundary. But still, that is not so easy when we have a single write that can cross the boundary.

I thought about this for a long while and I came up with a scheme that would work: We can allow a REP MOVS/STOS run to cross at most one page boundary. Then we only need to keep track of at most two pages at the same time (or four pages for REP MOVS), and if we hit this limit, then we can return to the code and simply wait for a new page fault to restart where we left off.

But still it was not quite that easy. Emulating the memory accesses in effect means that we do them from the page fault handler. The kernel got through the boot sequence and a bit into userspace. But then it would BUG on a test that wanted irqs to be enabled. After a bit of debugging, I found (to my great horror) that copy_to_user() was using REP MOVS to move data from the kernel into userspace. This is of course not safe, when we consider that the userspace page might not even be present in the page tables. Because now we were making a write from the kernel (in fact, from the page fault handler itself) to userspace, causing a new page fault, and then calling into various memory subsystem functions to allocate a new page for userspace. All of this with interrupts disabled, which is forbidden. (I believe that this is also the reason why copy_to_user() cannot be used in atomic contexts. Who can confirm?)

We absolutely cannot emulate the instruction by doing the write from the page fault handler. So what can we do?

Well, all is not lost. I am rather proud of my little hack, too. This is what I wrote (in my great excitement) to Ingo Molnar:

Instead of emulating the _whole_ REP MOVS/STOS, we only emulate the REP part. That is, on #PF, we increment %eip by one, which means that when the #PF returns, it will execute just a normal MOVS/STOS instruction (and give is the #DB straight afterwards). Now, in the #DB, we check the flag that says "was this really a REP instruction?" and if it was, we start counting down %ecx and rewinding %eip each time until %ecx is 0. Each time we return to the original instruction and let the CPU execute it natively. When %ecx is 0, we turn off single-stepping and hide the pages again.

The great thing is that it actually works. With this (rather small) patch, I am able to boot my P4 and get exactly the same error reports that I get on my Pentium Dual-Core laptop.

This also prompted me to start fixing the numerous false positive warnings that occur because kmemcheck is reporting eagerly. Most prominent of these are the bitfield operations, which load a multiple of 8 bits at a time, even though just one of the bits are actually used. The solution is to explicitly initialize the whole bitfield at once just after the struct has been allocated. Yes, this means that we won't be able to detect errors in the use of uninitialized bitfields, but this has always been true and is a result of the combination of the x86 architecture and the way we detect memory accesses.

And this is the current status: 0 errors reported during kernel initialization, 3 errors reported during userspace initialization, 0 errors while transferring a 4 MiB bzImage over SSH. Compare that to the ~2400 errors this would give us a month ago. This time I believe that we are truly ready for mainline. It will be interesting to see if anybody will try it out or review the patches, however...

Notes on source code preprocessing

2008-07-25T16:24:00.014+02:00

(This post contains some reflections on the hypothetical design of an ideal programming language...)

Don't use or support the use of preprocessing source code. Preprocessing means that all the tools which operate on the source code (including editors, compilers, static analyzers, etc.) will necessarily need to either support preprocessing themselves, or call the preprocessor before operating on the resultant source code.

Consider, for example, a simple tool that parses C code and searches for a given text in all the literal strings found in that code. If the source code needs to be preprocessed, then certain parts of the code may not be searched if the part in question is contained within the equivalent of a C-preprocessor #ifdef/#endif block. On the other hand, if we want our tool to also find strings inside these sections, then we can no longer use a C parser because #ifdef and #endif are not recognized by the C parser proper.

(The solution to the problem might include using regular expressions as a kind of heuristic to determine where the strings are, and then do concatenations, etc. However, this is only an approximate solution, and is in general not entirely satisfying. What about the more complex task of looking for specific variable or function declarations? In fact, a number of such tools have had to deal with variations of this problem; see for example LXR and Coccinelle.)

Multiple, different types of preprocessors also don't mix very well. For example, as an extension to many programming languages, the source code is preprocessed so that SQL queries are substituted with the (possibly verbose) support code which would otherwise be needed to prepare and execute the query in question. Now we have exactly the same problem as mentioned above, which is that support tools (editors, compilers, etc.) will have to either support the preprocessor language or (more likely) always operate on already-preprocessed source code, with all the aforementioned drawbacks. In some cases, the order of preprocessing will also become significant, or different preprocessor languages might be incompatible.

Another practical aspect of preprocessing is that the code which is inside such #ifdef blocks will be compiled only conditionally; the compiler might not even look at it. This means that the compiler is a lot less useful than it could be. It is one of the main tasks of the compiler to inform the programmer when he/she is writing something which is internally inconsistent, such as calling a function with the wrong argument types. (This is entirely possible if there is a caller of the function inside an #ifdef block and the definition of the function was later changed to take different arguments.)

In conclusion, I think C/C++ could have done a lot better in this area. On the other hand, a lot of other programming languages did get it right. But maybe the need for alternative compilation is greater in the lower-level languages and it's really just a trade-off between performance and usability.

Single-stepping a REP STOS...

2008-07-21T10:17:00.004+02:00

I've recently made a startling discovery that explains a LOT about how kmemcheck has been working (or not) on one of my machines.

Yesterday I added the kmemcheck hooks into the DMA API, which means that we should now not give any false-positive errors about DMA-able memory. The patch was essentially a one-liner, since the rest of the DMA API deals with whole pages only (and they come straight from the page allocator, so they're not tracked anyway).

But still I was getting a huge amount of errors from sysfs code. This puzzled me for many hours. The code was apparently okay. In fact, the allocation in question was explicitly being zeroed out (it was calling kzalloc()), so it shouldn't have been possible to even find any use of uninitialized memory in it. I added some code to dump the memory along with the shadow dump, and it showed that the array was indeed being zeroed, but not marked initialized.

Because memset() is such a common operation (and needs to be fast), I've written a custom memset() function that checks whether the target memory is being tracked or not; if it is, we don't have to take any page fault at all, but we can simply zero the memory and set the initialization status to "initialized" at the same time.

I suspected my custom memset() of being in error. So I commented it out. And the result was even more startling; I now got a kmemcheck error on just about every memory access...

Something had to be wrong with the built-in memset. This is its definition:

static inline void * __memset_generic(void * s, char c,size_t count)
{
     int d0, d1;
     __asm__ __volatile__(
             "rep\n\t"
             "stosb"
             : "=&c" (d0), "=&D" (d1)
             :"a" (c),"1" (s),"0" (count)
             :"memory");
     return s;
}

(Source code taken from the Linux Kernel. This code is licensed under the GNU GPL version 2.)

Taking a new look at the first kmemcheck error reported, I got another clue. The kzalloc() allocation was uninitialized except for the very first byte!

I wrote a short program for userspace which called the above function and single-stepped it with gdb on my two machines, one P4 3.0 GHz, and one Pentium Dual-Core 1.47 GHz. To my great surprise, the P4 skipped the whole REP STOS construct in one go, while the Dual-Core got a trap for each repetition of the STOS.

This is very grave news for kmemcheck. I had tested it on my Dual-Core earlier and thought that it would behave the same for all CPUs; there's not a word about single-stepping REP instructions in the Intel's System Development Manuals that I could find, anyway.

There are basically two solutions to the problem:

Black-list the models that don't single-step each repetition
Emulate the instruction (i.e. no single-stepping at all for the REP instructions)

And neither of them is particularly attractive.

But I have started working on instruction emulation to see how far I can get.

I've also contacted Intel and asked for more information about the peculiarity.

I only hope that there are not more unpleasant surprises like this...

Vegard

PS: I have written a (32-bit) userspace program that backs up my suspicions. Compare these outputs:

$ ./a.out
processor       : 7
cpu family      : 6
model           : 15
model name      : Intel(R) Xeon(R) CPU           E5320  @ 1.86GHz

Counted 1000 REP STOS instructions (expected 1000).

$ ./a.out
processor       : 1
cpu family      : 15
model           : 6
model name      : Intel(R) Pentium(R) 4 CPU 3.00GHz

Counted 55 REP STOS instructions (expected 1000).

Fedora 8 -> 9 upgrade

2008-07-14T10:10:00.001+02:00

Yesterday, I decided that it was time to try out Fedora 9; after all, it's been a few months since it was released, and having just made a backup, I found that this was a convenient time to perform the upgrade.

Things did not start out so well, though. The installer seemed incredibly slow this time. There is a progress bar which shows how many packages that have been installed, but this could probably have been dropped; the next phase of installation, which I believe is the configuration of the just-installed packages, seemed to take just as long as the installation itself, and that with no progress bar at all (though, admittedly, with a rather honest "This may take a long time").

Well, the installer eventually completed and I rebooted the system. GRUB loaded as usual, except for the new spiffy background image. I picked the most recent kernel in the list, 2.6.25.9-40.fc8, even though the 'fc8' suffix puzzled me somewhat, but no, it didn't boot. Apparently the kernel (or initrd?) was unable to find my LVM volumes, and so couldn't mount my root partition. Well, at least the old kernel, 2.6.25.6-27.fc8, was still present in the menu, and choosing this the next time got me all the way to the (now even spiffier) graphical login screen.

My desktop shows up as usual and things seem fine. I decide to grab the most recent updates from the web, as I had downloaded the release DVD which contains packages which are now almost two months old. Unfortunately, all that 'yum' can do for me is to print a message about a missing _sha256 python package and some download instructions. I search the web for the exact error message, and I find a forum where others have the same problem [1]. The suggestion there is to download the RPMs that I need and install them manually using the 'rpm' tool, which I do. This method did in fact work, but only after resolving a few dependencies by hand and downloading amongst other things the updated python and yum packages.

And now that yum again runs successfully, I turn to those updates I've been waiting for. In the world of Free Software, changes happen quickly and the Fedora packages are usually updated quite frequently. However, all I see is a list of just two lone packages which both belong to the ".fc8" set of packages. Did the upgrade somehow forget to switch my package repositories?

No, that question will have to remain unanswered. I do not know the internals of yum, nor do I have any wish to do so (beyond fixing my broken system, obviously). I don't want to spend time on fixing the package manager; that's why I use one to begin with!

For the record, though my opinions might be biased by the experiences just recounted, I am also unimpressed by the new Firefox 3. I feel that the new user interface has been forced upon me, and it would be better to leave the former theme as it was and instead allow the user to choose the new one, if so he or she dares. I simply don't like the way things look; the elements of the drop-down URL list/chooser now displays titles of the webpages in addition to the URL itself, an incredibly annoying misfeature when my habits are already tuned to one specific behaviour. I can now also report that Firefox, only showing my Gmail inbox, now defaults to using 10% CPU when idle instead of the usual 3% of Firefox 2.5.

So thank you, but no thanks. I should have stayed with F8.

Vegard

1: http://www.fedoraforum.org/forum/showthread.php?t=193507

PS: When attempting to start gvim (to copy this very text into my browser), I got the following error: "gvim: error while loading shared libraries: libperl.so: cannot open shared object file: No such file or directory".

PPS: Several other programs were broken as well, including git, which made the computer completely useless for me. In the end, I installed F9 from scratch and restored my home directory. Yum has been downloading/installing updates for an hour now. Still, Tomboy Notes crashed while Yum was installing a SELinux policy update.