Recursive Mutexes

The JIT compiler needs to initialize any classes it loads during method compilation. However, the class initialization code can invoke the method under compilation which can dead-lock in Jato because we're holding the same per-method mutex during initialization and compilation.

While discussing this on #jato, someone brought up PTHREAD_MUTEX_RECURSIVE as a potential solution for the problem. For those of you not familiar with pthreads, PTHREAD_MUTEX_RECURSIVE allows one thread to acquire the same mutex multiple times without dead-locking which would solve the problem at hand.

I didn't feel comfortable using recursive mutexes because we don't have them in the kernel (which is usually a big clue not to do something). But as I didn't have any specific arguments against them, I did the next best thing to critical thinking and started googling around. I was hoping to find a rant from Linus Torvalds explaining why they are "crap, crap, crap" but instead I found an interesting post on comp.programming.threads by David Butenhof.

He claims that PTHREAD_MUTEX_RECURSIVE was never meant to be used as a locking solution:

But nobody was supposed to use recursive mutexes. For the original intended purpose, only the global mutex would work anyway. And if you could analyze the code paths enough to know that a separate mutex was safe, why the heck would anyone want the overhead and complication of a recursive mutex instead of just doing it right?

Now I don't know if it's true or not but the post seems to validate my thinking that recursive mutexes are pretty damn special and thus should be avoided unless you know what you are doing. And as I sure as hell don't know what I am doing, we're sticking to plain old mutexes.

Jato is now a standalone virtual machine

As of commit 6e064e7... ("nuke jamvm"), Jato is now a standalone virtual machine! I started working on Jato as a JIT compiler for JamVM back in 2005 thinking that I would eventually propose merging a functional JIT compiler to JamVM.

But as it turns out, it's 2009 now and we don't have a fully working JIT. As we don't want to fork JamVM, not being able to change the core VM is seriously hindering development. Furthermore, Jato is licensed under GPLv2 + linking exception whereas JamVM is GPLv2 only so there's a inherent license conflict which I haven't been able to resolve with the author of JamVM.

As the need to replace JamVM came apparent, I suggested Vegard Nossum to submit a Google Summer of Code proposal this year to write a new core VM. After lots of blood, sweat, and tears from Vegard, and some 100 commits later, we were finally able to ditch JamVM.

The new core VM is built on top of Vegard Nossum's light-weight Java classloader called cafebabe and there's some brand new VM code to glue the classloader to the JIT. The biggest hurdle now is the lack of an interpreter which we used to rely on for bytecodes that the JIT compiler doesn't support yet. We're also missing a verifier and a garbage collector too but the latter in JamVM wasn't functional with JIT'ed code anyway so we didn't regress in functionality too much.

If you have been longing to hack on a Java virtual machine, now is your chance to do just that! Just drop by #jato channel on irc.freenode.net or subscribe to the mailing list to join the fun. There's no shortage of cool things to hack on. :)

What To Do When at First You Don’t Succeed?

So what can you do if you don't succeed at first when trying out a new technique? Write a public rant on how anti-productive the whole damn technique is, of course!

Ruby scoping rules

I always knew that I am a beginner programmer in Ruby but the result of the following code snippet came as a total surprise to me:

  symbols = [ 1, 2, 3, 4 ]

  (1..2).each do |i|
    symbols.each_slice(2) do |symbols|
      puts symbols.join " "
    end
  end

If you run it, you'll see that the produced output is:

  $ ./scope.rb 
  1 2
  3 4
  3 4

which means that the block variable ("symbols") in each_slice overwrites the local variable that's outside of the each loop! And sure enough, if I change the above snippet to this:

  symbols = [ 1, 2, 3, 4 ]

  (1..2).each do |i|
    symbols.each_slice(2) do |s|
      puts s.join " "
    end
  end

the output is what I expected in the first case:

  1 2
  3 4
  1 2
  3 4

I am too lazy to look up the rationale for that from a Ruby language reference up but it's obvious I have ruined my brains with too much C and Java because that genuinely freaks me out!

How does kmemcheck work?

If you're interested in how kmemcheck works, check out Vegard Nossum's excellent set of slides from a presentation he gave at DIKU (Datalogisk Institut på Københavns Universitet) back in April.

kmemleak and kmemcheck merged to Linux 2.6.31-rc1

Two new kernel debugging tools have been merged to the upcoming 2.6.31-rc1 kernel: kmemleak and kmemcheck. The former is basically a in-kernel tracing garbage collector that is able to detect kernel memory leaks. The latter is dubbed as "valgrind for the kernel" and can detect various kinds of error conditions including use-after-free and use of unitialized memory.

Neither of the tools are intended for production kernels but should be really helpful when testing new kernels or tracking down bugs.

Jato has a profiler!

I implemented support for profiling JIT generated code with the upcoming Performance Counters feature in Linux kernel. All I needed was a small patch to fix up mprotect() in the kernel and some glue to both the perf tool and Jato and I was able to successfully profile a Java program running under Jato:

penberg@penberg-laptop:~/src/jato$ cat Fibonacci.java 
public class Fibonacci {
    public static int fib(int n) {
        if (n <= 2)
            return 1;

        return fib(n-1) + fib(n-2);
    }

    public static void main(String[] args) {
       for (int i = 0; i < 10000000; i++)
           fib(8);
    }
}
penberg@penberg-laptop:~/src/jato$ javac Fibonacci.java
penberg@penberg-laptop:~/src/jato$ perf record -f ./scripts/java Fibonacci
[ perf record: Captured and wrote 1.344 MB perf.data (~58710 samples) ]
penberg@penberg-laptop:~/src/jato$ perf report --sort comm,dso,symbol

#
# (40439 samples)
#
# Overhead           Command  Shared Object              Symbol
# ........  ................  .........................  ......
#
    97.68%              jato  /tmp/perf-9389.map         [.] Fibonacci.fib(I)I
     0.57%              jato  00000000b7ff1c5d           0x000000b7ff1c5d
     0.48%              jato  /tmp/perf-9389.map         [.] Fibonacci.main([Ljava/lang/String;)V
     0.35%              jato  [kernel]                   [k] get_page_from_freelist
     0.09%              jato  [kernel]                   [k] kunmap_atomic
     0.06%              jato  ./jato                     [.] alloc_stack
     0.05%              jato  [kernel]                   [k] copy_user_highpage
     0.05%              jato  ./jato                     [.] executeJava
     0.05%              jato  ./jato                     [.] utf8Hash
     0.05%              jato  ./jato                     [.] expand_buffer_exec
     0.04%              jato  ./jato                     [.] defineClass
     0.04%              jato  [kernel]                   [k] do_page_fault
     0.04%              jato  ./jato                     [.] utf8Comp
     0.02%              jato  ./jato                     [.] alloc_compilation_unit
     0.02%              jato  [kernel]                   [k] perf_output_end
     0.02%              jato  ./jato                     [.] append_buffer
     0.01%              jato  [kernel]                   [k] kmap_atomic_prot
     0.01%              jato  [kernel]                   [k] ata_sff_interrupt
     0.01%              jato  ./jato                     [.] linkClass
     0.01%              jato  ./jato                     [.] findUtf8String
     0.01%              jato  ./jato                     [.] lockHashTable0
     0.01%              jato  ./jato                     [.] processArchive

As you can see in the trace, the perf tool is able to show a full profile of the run, including time spent in the VM and the kernel! The Jato glue is merged in master now and the kernel and perf tool bits are in the "tip" tree and will probably be merged to 2.6.31. See the Performance Counters announcement if you are willing to build your own kernel to try this out.

Unfortunately we're not able to take advantage of all the nice performance monitoring features (such as cache hit/miss profiling) in latest x86 CPUs as we're limited to the 32-bit ones for now. That's why I am looking forward to the x86-64 port that's one of the on-going Google Summer of Code this year.

I hate Linux userspace (and I guess the kernel too) part 2

So I installed Ubuntu Jaunty 9.04 on my girlfriend's Eee PC last night. There hasn't been any major problems with the Xandros installation that came with it but for whatever reason Firefox froze from time to time (probably because of Flash plugin trouble). I did install all the available updates but none of that helped so I decided to switch to an up-to-date Ubuntu that can be upgraded if needed.

I did expect problems and sure enough, I got them. I had already googled around a bit and knew that there were some performance issues with the default Netbook Remix installation. It didn't take too long to figure out that it's actually a Intel i915 driver issue and there are patches available for it. So I, of course, assumed that updating to latest Ubuntu distribution kernel would fix things. After all, the patch dates back to January.

Well, to much of my surprise, latest Ubuntu kernel didn't fix the bug and even more surprising, it is not fixed in any of the mainline kernels either including the upcoming 2.6.30 kernel! So I went ahead and applied the patches on top of 2.6.30-rc8 and installed that on the machine. I was happy to see the performance problem fixed and turned my attention to making sure Skype works. After dealing with the usual "sound doesn't work" problems (that were fixed by replacing pulseaudio with esound and changing default mixer settings), I noticed that webcam didn't work. Skype wasn't particularly helpful here, it simply claimed the machine had no camera. Cheese said the same thing. Fortunately I had some help from Arthur Huillet who explained that I need to do:

  echo 1 > /sys/devices/platform/eeepc/camera

to enable the webcam. Of course, it would make more sense to enable the thing by default, so I patched my kernel. As far as I can tell, everything works now but I do expect other problems to pop up as soon as the machine is in actual use...