Ekam Eclipse Plugin

Ekam now has an Eclipse plugin! As always, all code is at:

http://code.google.com/p/ekam/

A story

So, let me start with a story. A little earlier today, I was making a small edit to Ekam. I made a change, saved the file, then saw an error marker (a red squiggly underline) appear on the line of code I had just written. I hovered over it and a tooltip popped up describing a compiler error. I figured out what the problem was, edited another file to fix it, and saved that. The error marker in the first file immediately went away.

It wasn't until several moments later than I realized that Eclipse's CDT (C++ developer tools) does not actually mark errors like this in real time. Normally you have to run a build first, and let Eclipse collect errors from the build output. It's normally only in Java that you get such fast feedback as you type.

What had actually happened here is that when I saved the file, Ekam immediately built it, then it sent the error info to my Ekam Eclipse plugin, which in turn marked the error in my editor. This was the first time I had actually edited Ekam code with the new plugin active. It literally took less than a minute for the plugin to start saving me time, and I didn't even notice until after the fact because the process seemed to natural.

As soon as I realized what had just happened, I started squealing with delight.

Features

Here's what the plugin does so far:

• Connects to a running Ekam process in continuous-build mode.
  
• Individual build actions are displayed in a tree view, corresponding to the source tree.
  
• Output from each action is shown and errors in GCC format can be clicked to browse to the location of the error in the source code.
  
• Errors are also actively marked using Eclipse "markers", meaning you get the squiggly red underline in your text editor.
  
• Passing tests have a big green icon while failures (whether tests or compiles) have a big red icon (and also cause parent directories to be marked, so you can find problems in a large tree).
  

UI is Weird

I have very little experience with UI code. One thing I'm finding interesting is that when I run my code, I immediately notice obvious UX problems that weren't at all obvious when I was imagining things in my head. Little tweaks can make a huge difference. I really have to try things to find out what works.

Time to Apply

Neither Ekam as a whole nor the Eclipse plugin in particular are anywhere near complete. However, I think they are working well enough now that it's time to work on something else using Ekam. I could go on adding features that I think are useful forever, but actually trying to use it will tell me exactly what the biggest pain points are. I will then go back and tweak Ekam as needed to facilitate whatever I'm working on.

So, next week, I plan to work on Captain Proto, which I've put off for too long.

Ekam: Works on Linux again; queryable over network

Ekam works on Linux again, and supports the ability to query the build state over the network. As always, the code is at:

http://code.google.com/p/ekam/

Real Linux support

Ekam not only works on Linux again, but I've gone and written a whole EventManager implementation based on epoll, signalfd, and inotify. I like epoll, but I am not sure if it really deserves to be advertised as "simpler" than kqueue. While it is a narrower interface, I don't feel like it took significantly less work to use.

inotify in particular is a really painful interface. This is what you use to watch the filesystem for changes. The painful part is that there is no dedicated system call for reading events from the inotify event stream. Instead, you just use read, and it happens to produce bytes that match a particular struct. This would be reasonable, except that the struct is actually variable-length (the last member is a NUL-terminated string). In addition to some annoying pointer arithmetic, this means that it is impossible to read just one event at a time, because you must provide a buffer big enough to hold any possible event, and it is likely that multiple actual events will fit into the buffer.

The problem with reading multiple events at a time is that it makes cancellation really complicated. Say you read two events, and then you try to handle them in order. You handle the first event by calling a callback. But what if that callback actually cancels the second event? That event is still in the buffer, and when you get to it you have to have some way of figuring out that it was canceled. If there were a way to read one event at a time, then this becomes the kernel's problem and userspace apps have a much easier time. The kernel has to solve this problem either way, so it would be nice if userspace could leverage its solution.

To make matters even worse, the ID numbers which the inotify interface uses distinguish directories being watched can be implicitly freed when particular events occur. Namely, if a watched directory is moved or deleted, then the ID number assigned to that directory is immediately available for reuse after that event is delivered. But say that you get two events, and the *second* event is the "directory deleted" event. Now say, in the course of handling the first event, you start watching a new directory. That new watch is likely to be assigned the same ID number as the one that was just freed. But you don't actually know yet that that watch has been freed, because you haven't looked at the second event. So, it looks like inotify just assigned you a duplicated watch ID, and all kinds of confusion ensues.

To work around all this, I ended up writing some very complicated code. It seems to work, but I do not completely trust it, much less am I happy with it. In contrast, the kqueue file watching implementation for FreeBSD was a breeze to write.

Network status updates

Ekam can now run in a mode where it listens for connections on a particular port, and then serves streaming information on the build state to anyone who connects. The protocol is (unsurprisingly) based on Protocol Buffers. I intend to use this to implement an Eclipse plugin.

If you would like to write this plugin, or a plugin for some other editor/IDE, let me know!

Kubuntu desktop

FreeBSD fails me

Hose my computer while trying to update my OS once, shame on me.

Hose my computer while trying to update my OS twice, shame on my OS.

Last night I tried to update my "ports" (basically all the non-core software) on my FreeBSD system. There are three different programs to do this: portupgrade, portmanager, and portmaster. AFAICT they all do the same thing, so I chose the one that was installed: portupgrade.

Unfortunately, the process isn't completely automatic. There is this file called UPDATING in the ports tree which contains a list of things that have changed which require manual intervention. It appears that several things get added to the list every week. Ugh. But after whittling it down, I concluded that the only thing I really needed to do was follow some instructions to remove KDE, because the KDE port had been updated to a new release and some things changed in incompatible ways.

Fine, whatever. I did as instructed. But then when I tried to run portupgrade, it started complaining about ports being in an inconsistent state because the KDE libs had been removed. It directed me to run some pkgdb, which started asking me obscure questions for which there didn't appear to be any right answer. After struggling with that for a bit, I canceled it and went back to portupgrade, this time passing a flag which it had suggested I use if I wanted to skip verification of port states. It started installing, so I let it stew for awhile, and when I came back, my FreeBSD install was thoroughly broken.

I don't have time for this crap. It was fun while it lasted, FreeBSD, but it's time to find something a little lower-maintenance.

Let's try Kubuntu

I hear Ubuntu is popular, and it even has a specialized KDE-based version called Kubuntu. I decided to give it a try instead. Let's catalog the problems I run into and see how they compare to installing FreeBSD.

Can only prepare USB installer from Windows or Linux

My spare machine is a MacBook. When installing FreeBSD, I was able to download an installer image explicitly designed for a USB stick. Kubuntu can be installed from USB, but the images provided on the web site are strictly CD images. You can convert these into USB images, but it seems the only tools available to do this run on Windows and Linux, not OSX or FreeBSD. After struggling a bit I rebooted my MacBook into Windows.

syslinux hangs

Once I had the USB stick prepared, I tried to boot from it. Failure. All it did was print the version of syslinux it was using and then hang. "syslinux" is apparently a utility for producing bootable USB sticks based on Linux.

I really had no idea what to do about this, and a Google search didn't produce any hints. On a lark I tried downloading syslinux on my Windows machine and then running it to re-initialize the USB stick. I noticed that the version the Kubuntu installer had chosen to use was 3.86, whereas 4.03 is now available. The package contained an executable called "syslinux.exe". Not knowing what else to do, I ran it on the command line. It informed me of a bunch of options, none of which made any particular sense to me.

I tried "syslinux g:" to initialize the G drive. Nothing appeared to happen. But just in case, I then tried booting from it and, miraculously, it worked! Wow. Did not expect.

Installer fails

Unfortunately, immediately after choosing what to do from the bootloader menu, I was dumped to a shell with the error message: Can not mount /dev/loop1 on cow

Some Googling revealed that this happens if, when running the Ubuntu tool to prepare the USB stick, you choose the option to allocate some space to save temporary files on the stick. This is the only option the tool gives you, and it is enabled by default. Apparently it doesn't work. You have to disable this option. WTF?

OK fine. Re-did the USB stick and tried again. Hung at syslinux. Re-fixed syslinux and tried again. Finally, it works!

Whoa

I...

Whoa.

Holy polished OS, Batman. I mean, really. Wow.

Let's go through the problems I had on FreeBSD, and compare.

Installer

Once I got the USB stick correctly initialized, I have to say that the Kubuntu installer was the best OS installer I have ever used. The thing ran at native 2560x1600 resolution. It gave me the option to choose my keyboard layout (Dvorak) at the very first menu. The partition manager was simple and intuitive, and even gave me the option of using btrfs (though I held off for now since it seems it is not yet ready for prime-time). And the installer let me configure the system while it copied the files -- although there was very little configuration to do. The whole process took about ten minutes. It was better than the OSX installer. This was completely the opposite of FreeBSD.

Installing Packages

There's a beautiful GUI for this, and it's of course backed by apt. All packages are available in binary form and are updated regularly.

Graphics Driver

The included Nouveau driver immediately had me running at 2560x1600. Of course, it was a bit sluggish, so I set out to install the nVidia driver.

Kubuntu includes a GUI app for this. It fetches the driver for you, builds, and installs it, all with a nice progress bar.

Holy. Crap.

Graphical login

This was already working on first boot.

Audio

Here I have a minor problem. Audio works, but goes to both my headphones and speakers. Plugging in the headphones does not mute the speakers. This is not a big deal for me since I can separately turn off my speakers, but I was a little bit surprised to find that Linux did not seem to provide me any way to fix this. I actually found a GUI app for twiddling all kinds of things related to the HD Audio driver, but couldn't find any knob that would make it mute the speakers when the headphones were plugged in. AFAICT from the internets, this is a common problem, and the solution is usually to wait for the driver to be updated for your hardware.

Oh well. At least it does actually play to both the speakers and headphones by default, unlike FreeBSD which did not do anything with the headphones until I started poking at the boot configs.

Chrome

Well, obviously, I just installed the Google-provided package, which will now happily auto-update Chrome for me. No mucking around with source code here.

Flash

This worked out-of-the-box. Contrary to my experience on my work Linux machine, I have not seen any performance problems.

Fonts

A few fonts looked a little weird at first, until I installed the msttcorefonts package. Now everything looks good.

Suspend/Resume

The "sleep" option in the Kubuntu menu seems to work fine. The only odd part is that I have to press power to wake it -- keyboard keys are ignored. But I guess that's not a big deal.

iTunes replacement

Amarok is available, obviously. But after using it for awhile on FreeBSD, I have decided it is pretty much crap. The UI is weird and just does not do the things I want. I'll be on the lookout for something new, but this isn't really an OS issue.

ZFS

Linux does not have ZFS due to stupid licensing squabbles. ZFS is open source. Linux is open source. But the technicalities of the licenses do not allow them to be used together. Lame.

But I guess Linux now has BTRFS, which is similar. The Kubuntu installer actually gave me the option to use it, unlike the FreeBSD installer where I had to set up ZFS manually on the console. However, from what I've read, BTRFS is not quite ready yet, because it lacks an fsck-like tool. This apparently means that a BTRFS partition can be left unrecoverable after a power failure. It looks like this will be resolved Real Soon Now, but I decided to play it safe until then.

Eclipse

Eclipse officially supports Linux, of course. But the packages available from apt were for version 3.5, whereas 3.6 has been out for a few months now. So, I decided to install the official release instead of the apt package.

Boot-up Splash Screen

Kubuntu provides a very nice, minimalist splash screen by default, and it even runs at native resolution (which the FreeBSD one certainly didn't).

Wine

The default apt repositories did not include Wine 1.3, but there's apparently an alternate repository listed on the Wine site that does. Installed from there. Piece of cake.

Starcraft 2 installed and patched with no problems, following basically the same procedure as I did on FreeBSD, except without the part where I had to upgrade the kernel, or the part where the patcher kept crashing. The latter is probably due to the newer Wine version.

Conclusion

Well, I'm pretty much blown away. What took me two or more weekends to set up on FreeBSD took only two weeknights on Kubuntu. Of course, it's no real surprise that Kubuntu would be more usable than FreeBSD, but I honestly didn't expect this much polish. I could actually see non-technical users using this. Canonical has done an amazing job.

Ekam continuously builds

I just pushed some changes to Ekam adding a mode in which it monitors your source code and immediately rebuilds when a file changes. As usual, code is at:

http://code.google.com/p/ekam/

Just run Ekam with -c to put it in continuous mode. When it finishes building, it will wait for changes and then rebuild. It also notices changes which happen mid-build and accounts for them, so you don't need to worry about confusing it as you edit.

I've only implemented this for FreeBSD and OSX so far, but things are still broken on Linux anyway (see previous post).

kqueue/EVFILT_VNODE vs. inotify

Speaking of Linux and monitoring directory trees, it turns out that Linux has a completely different interface for doing this vs. FreeBSD/OSX. The latter systems implement kqueue, which, via the EVFILT_VNODE filter, can monitor changes to a file pointed at by an open file descriptor. This includes directories -- adding or removing a file from a directory counts as modifying the directory.

Linux, on the other hand, has inotify, a completely different interface that, in the end, does the same thing.

There is a key difference, though: kqueue requires you to have an open file descriptor for every file and directory you wish to monitor. inotify takes a path instead. Normally I prefer interfaces based on file descriptors because they are more object-oriented. However, the number of file descriptors that may be opened at one time is typically limited to a few thousand -- easily less than the number of files in a large source tree. On OSX (which seems to have lower limits than FreeBSD) I was not even able to monitor the protobuf source tree without hitting the limit.

Furthermore, watching a directory using inotify also means watching all files in the directory. While I have to assume that this is NOT transitive (so you can't watch an entire tree with one call), it still (presumably) greatly reduces the overhead of watching an entire tree, since the OS doesn't have to flag every file individually.

I'm still waiting for confirmation from the freebsd-questions mailing list on whether EVFILT_VNODE is really so much less scalable, but lots of Googling didn't produce any answers. I just see lots of people asking for inotify on FreeBSD and being told to use EVFILT_VNODE instead, as if it were an equal replacement.

This may mean that FreeBSD and OSX will have to use some sort of gimpy polling strategy instead, but that will have its own scalability issues as the directory tree gets large. Sigh.

I may give up and switch my desktop to Linux. Fully-supported Chrome and Eclipse would be nice, as well as a more robust package update mechanism (I'm getting sick of compiling things). Figuring out how to do everything on FreeBSD was fun, but getting a bit old now.

Ekam finds includes, runs tests

Sorry for missing the last couple weeks. I have been working on Ekam, but didn't have time to get a whole lot done and didn't feel like I had anything worth talking about. But now, an update! As always, the code can be found at:

http://code.google.com/p/ekam/

Ekam now compiles and runs tests:

Here you can see it running some tests from protocol buffers. It automatically detects object files which register tests with Google Test and links them against gtest_main (if necessary). Then, it runs them, highlighting passing tests in green, and printing error logs of failing tests which show just the failures:

By the way, compile failures look pretty nice too:

Is that... word wrap? And highlighting the word "error" so you can see it easily? *gasp* Unthinkable!

Intercepting open()

Ekam now intercepts open() and other filesystem calls made by the compiler. It works by using LD_PRELOAD (DYLD_INSERT_LIBRARIES on Mac) to inject a custom shared library into the compiler process. This library defines its own implementation of open() which makes an RPC to the Ekam process in order to map file names to their actual physical locations. Essentially, it creates a virtual filesystem, but is lighter-weight than FUSE. This serves two purposes:

1. Ekam can detect what the dependencies of an action are, e.g. what headers are included by a C++ source file, based on what files the compiler tries to open. With this information it can construct the build graph and determine when actions need to be re-run. (See previous blog entries about how Ekam manages dependencies.)
   
2. Ekam can locate dependencies just-in-time, rather than telling the compiler where to look ahead of time. For example, Ekam does not need to set up the C++ compiler's include path to cover all the directories of everything the code might include. Instead, the include path contains only a single "magic" directory. When the compiler tries to open a file in that directory, Ekam searches for that file among all public headers it knows about across the source tree.
   

The down side of this approach is that every OS has quirks that must be worked around. FreeBSD seems to be the least quirky: the only thing I found weird about this system is that I had to define both open() and _open() to catch everything (and similarly for all other system calls I wanted to intercept). OSX and Linux, meanwhile, have some ridiculous hacks going on in which certain system calls are remapped to different names at compile time, so the injected library has to be sure to intercept the remapped name instead of the original. I still am running into some trouble on Linux where some calls to open() seem to bypass my code, while others hit it just fine. I need to spend more time working on it, but I do not have a Linux machine at home. (Maybe someone else would like to volunteer?)

Try it out

If you are running FreeBSD or OSX, you can try using Ekam to build protobufs or your own code (currently broken on Linux as described above). I've updated the quick start guide with instructions.

Ekam: Core model improvements

Finally got some Ekam work done again. As always, code can be found at:

http://code.google.com/p/ekam/

This weekend and last were spent slightly re-designing the basic model used to track dependencies between actions. I think it is simpler and more versatile now.

Ekam build model

I haven't really discussed Ekam's core logic before, only the features built on top of it. Let's do that now. Here are the basic objects that Ekam works with:

• Files: Obviously, there are some set of input (source) files, some intermediate files, and some output files. Actually, at the moment, there is no real support for "outputs" -- everything goes to the "intermediate files" directory (tmp) and you have to dig out the one you're interested in.
  
• Tags: Each file has a set of tags. Each tag is just a text string (or rather, a hash of a text string, for efficiency). Tags can mean anything, but usually each tag indicates something that the file provides which something else might depend on.
  
• Actions: An action takes some set of input files and produces some set of output files. The inputs may be source files, or they may be the outputs of other actions. An action is specific to a particular set of files -- e.g. each C++ source file has a separate "compile" action. An action may search for inputs by tag, and may add new tags to any file (inputs and outputs). Note that applying tags to inputs is useful for implementing actions which simply scan existing files to see what they provide.
  
• Rules: A rule describes how to construct a particular action given a particular input file with a particular tag. In fact, currently the class representing a rule in Ekam is called ActionFactory. Each rule defines some set of "trigger" tags in which it is interested, and whenever Ekam encounters one of those tags, the rule is asked to generate an action based on the file that defined the tag.
  

Example

There is one rule which defines how to compile C++ source files. This rule triggers on the tag "filetype:.cpp", so Ekam calls it whenever it sees a file name with the .cpp extension. The rule compiles the file to produce an object file, and adds a tag to the object file for every C++ symbol defined within it.

Meanwhile, another rule defines how to link object files into a binary. This rule triggers on the tag "c++symbol:main" to pick up object files which define a main() function. When it finds one, it checks that object file to see what external symbols it references, and then asks Ekam to find other object files with the corresponding tags. It does this recursively until it can't find any more objects, then attempts to link (even if some symbols weren't found).

If not all objects needed by the binary have been compiled yet, then this link will fail. That's fine, because Ekam remembers what tags the action asked for. If, later on, one of the missing tags shows up, Ekam will retry the link action that failed before, to see if the new tag makes a difference. Assuming the source code is complete, the link should eventually succeed. If not, once Ekam has nothing left to do, it will report to the user whatever errors remain.

Note that Ekam will retry an action any time any of the tags it asked for change. So, for example, say the binary calls malloc(). The link action may have searched for "c++symbol:malloc" and found nothing. But, the link may have succeeded despite this, because malloc() is defined by the C runtime. Later on, Ekam might find some other definition of malloc() elsewhere. When it does, it will re-run the link action from before to make sure it gets a chance to link in this new malloc() implementation instead.

Say Ekam then finds yet another malloc() implementation somewhere else. Ekam will then try to decide which malloc() is preferred by the link action. By default, the file which is closest to the action's trigger file will be used. So when linking foo/bar/main.o, Ekam will prefer foo/mem/myMalloc.cpp over bar/anotherMalloc.cpp -- the file name with the longest common prefix is preferred. Ties are broken by alphabetical ordering. In the future, it will be possible for a package to explicitly specify preferences when the default is not good enough.

The work I did over the last two weekends made Ekam able to handle and choose between multiple instances of the same tag.

Up next

• I still have the code laying around to intercept open() calls from arbitrary processes. I intend to use this to intercept the compiler's attempts to search for included headers, and translate those into Ekam tag lookups. Once Ekam responds with a file name, the intercepted open() will open that file instead. Thus the compile action will not need to know ahead of time what the dependencies are, in order to construct an include path.
  
• I would like to implement the mechanism by which preferences are specified sometime soon. I think the mechanism should also provide a way to define visibility of files and/or tags defined within a package, in order to prevent others from depending on your internal implementation details.
  
• I need to make Ekam into a daemon that runs continuously in the background, detecting when source files change and immediately rebuilding. This will allow Ekam to perform incremental builds, which currently it does not do. Longer term, Ekam should persist its state somehow, but I think simply running as a daemon should be good enough for most users. Rebuilding from scratch once a day or so is not so bad, right?
  
• Rules, rules, rules! Implement fully-featured C++ rules (supporting libraries and such), Java rules, Protobufs, etc.
  
• Documentation. Including user documentation, implementation documentation, and code comments.
  

After the above, I think Ekam will be useful enough to start actually using.

No coding this weekend

I spent this weekend on things far more important than neat projects. I expect to get back to work next weekend.

Last Monday, though, I did manage to write up some proof-of-concept code to intercept open() system calls via LD_PRELOAD, as described in last week's post. It works pretty well. I'm excited to actually apply this technique next weekend.