My brain is open

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

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"

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

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

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

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

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...