Wednesday, June 17, 2009

kmemcheck in mainline

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!)

Thursday, May 21, 2009

Hiragana tutor

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.

Tuesday, May 5, 2009

LADSPA

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

Monday, April 6, 2009

Linux kernel 2.6.27 exploits

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.

Saturday, March 21, 2009

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.

Sunday, March 15, 2009

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:

Tuesday, February 24, 2009

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