Apparently this installer wants a title

As of some time last week, I am now a KDE committer. So far, I haven’t made a useful commit yet, but hopefully I’ll have time over the summer. KHelpCenter could use a lot of love, and I’d like to improve the startup time of various applications.

Earlier this week, I hunted down a delicious little bug in BarnOwl. A friend of mine, Alex, reported occasionally segmentation faults in his sessions. This week, we finally got a core dump to inspect.

Off-screen windows

Inspecting the backtrace, we see the crash occurred in the ncurses function wredrawln, called by our owl_function_full_redisplay. (Actually, we call redrawwin which is a macro wrapper over wredrawln.)

Now, one of many causes for crashes in ncurses is off-screen windows. It’s not clear what the state of support for it is, as the code does check for in some cases, and newwin will allow you to create them. That said, you cannot move them off-screen with mvwin, and parts of ncurses may crash.

In fact, owl_function_full_redisplay had the following code in place

  /* Work around curses segfualts with windows off the screen */
  if (g.lines >= owl_global_get_typwin_lines(&g)+2)
      redrawwin(owl_global_get_curs_typwin(&g));

Furthermore, it was that call to redrawwin that crashed. (The typwin is the typing area; the name is a holdover from the Owl days.) Perhaps the check wasn’t sufficient and we got an off-screen window again. So, some gdb dances later:

       (gdb) p g.lines
       $1 = 45
       [...]
      (gdb) print *(g->typpan->win)
       $5 = {_cury = 0, _curx = 0, _maxy = 7, _maxx = 176, _begy = 37, _begx = 0, [...]}

(g holds much of BarnOwl’s state. Again, a remnant from Owl.) Well, 7 + 37 = 44 = 45 - 1, so that looks fine. But wait!

       (gdb) print *((WINDOW*) curscr)
       $2 = {_cury = 37, _curx = 0, _maxy = 43, _maxx = 176, _begy = 0, _begx = 0, [...]}

Ncurses thinks the height of the window is 43 + 1 = 44, one less than BarnOwl’s 45. So the window is off-screen. That triggers the aforementioned wredrawln crash.

Diving into ncurses

Clearly, this crash in ncurses shouldn’t happen in the first place. So let’s take a brief foray into the tangled forests of ncurses source. The function in question is implemented in ncurses/base/lib_redrawln.c. Here is a snippet of it:

    end = beg + num;
    if (end > curscr->_maxy + 1)
        end = curscr->_maxy + 1;
    if (end > win->_maxy + 1)
        end = win->_maxy + 1;

    len = (win->_maxx + 1);
    if (len > (size_t) (curscr->_maxx + 1))
        len = (size_t) (curscr->_maxx + 1);
    len *= sizeof(curscr->_line[0].text[0]);

    for (i = beg; i < end; i++) {
        int crow = i + win->_begy;

        memset(curscr->_line[crow].text + win->_begx, 0, len);
        _nc_make_oldhash(crow);
    }

Well, that’s odd. The library is already careful to clamp the dimensions by the screen size, so we shouldn’t have a problem. But win->_beg{x,y} is added as an offset. Those checks only work on windows flush with the upper-left corner. The typwin is not, so they fail.

Ncurses resizing

Ncurses problems not withstanding, we’re not finished. The main problem is yet to be addressed: How did BarnOwl and ncurses disagree on the window size? Before that, let’s discuss how ncurses resize is handled. There is an ioctl for querying the size of a terminal, TIOCGWINSZ (as well as a handful of other mechanisms; the ncurses source code tries a ton of different ones). But we shouldn’t poll on that value, so there is a signal SIGWINCH which informs a process of a changed terminal size.

How do you react to a SIGWINCH? The traditional way was to do a endwin/doupdate pair. This is flickery, so there is an extension to curses, resizeterm which forces the resize work directly. (In ncurses, the former method is implemented using resize_term.) If you don’t register your own SIGWINCH handler, ncurses will do so on initscr, but then it’s very hard to atomically relayout and resize. (Ncurses doesn’t know enough about the application to handle resizes in full: a textbook violation of the end-to-end principle.)

Reproducing the bug

Most people run BarnOwl inside a screen session, so let’s (incorrectly) guess that screen was failing to send the signal on attach. Aided by the backtrace, we open BarnOwl in screen with a popup open. We then detach, resize the terminal, reattach, close the popup, and BOOM! It crashes! That was easy.

Unfortunately, none of the other developers were able to reproduce this. Also, this theory doesn’t account for ncurses and BarnOwl getting different values as the same signal handler updates both. Furthermore, the bug isn’t always hit, so there’s a race condition happening somewhere.

Tracing

Stepping back a bit, there are three sets of window sizes here. The first is the actual terminal size. Then, we have ncurses’ record of the size (from which the size of the screen buffer is determined). Finally, we have BarnOwl’s own record of the size (from which the window layout is determined). Playing with signals will allow us to synchronize the first with the other two. The crash we’re interested in comes from a discrepancy between between the latter. But BarnOwl is the only one calling resizeterm, so how can a discrepancy arise?

Quite conveniently, ncurses has a trace feature which is indispensable in debugging ncurses applications. By examining trace data, we notice something strange: when the bug is triggered BarnOwl runs its SIGWINCH handler, but ncurses enters resizeterm twice.

So who made the second call. If you were reading carefully, you may already know the answer: doupdate. BarnOwl’s resize code not only called a resizeterm, but it also calls endwin.

  if (!isendwin()) {
    endwin();
  }

  /* get the new size */
  ioctl(STDIN_FILENO, TIOCGWINSZ, &size);
  // [...]

#ifdef HAVE_RESIZETERM
  resizeterm(size.ws_row, size.ws_col);
#endif

Because we call an endwin, the next screen update (the doupdate at the end of the event loop iteration) triggers ncurses’ internal resize routine. It then does its own ioctl and finds the size. Now, if we change terminal size twice in a row, such that the second happens while we are still reacting to the first, ncurses’ later ioctl will return different values than BarnOwl’s query. As a result, we get our inconsistency.

Where does this quick resize come from? Screen has this feature to enable a status bar. Both Alex and I happen to have them enabled. Screen has (arguably) a bug where it resizes the window twice in quick succession; the second time to add a status bar. This also explains why the numbers of lines were off by exactly 1. And that is final piece of the puzzle.

Summary

To help put these pieces together, I made a diagram. A fairly complex interaction between BarnOwl, ncurses, and screen was required here.

Closing a popup window eventually calls redrawwin on a number of windows.

This call is rather pointless. In BarnOwl 1.6, I landed some code to use the libpanel library to manage overlapping windows. The much safer touchwin can be used instead of redrawwin, and owl_popwin_down has no need to repaint the screen anyway.

wredrawln checks boundaries incorrectly

I sent a patch upstream to correct this. It has been incorporated into ncurses-5.7-20100501.

Screen sends two SIGWINCHs in succession

Screen’s code is really scary. I’m not touching that one.

BarnOwl’s resize handler calls both endwin and resizeterm

This one is actually partially my fault. As part of the libpanel changes, I removed many of the extraneous explicit screen updates, including a refresh right after the endwin. This has now been changed. We no longer call endwin at all and require resizeterm. (As we already required ncurses for Unicode, this is not actually a change in dependencies.) We should also finally have flicker-free resizing now.

Had even one of these bugs not occurred, it is quite likely that we would never have noticed. But they all did and meshed together to form a crash. Some failures are simple and fairly easy to debug. Some are not. Sometimes, you have to dig quite far to understand the motions of all the players on the board.

So, Saturday, SIPB ran a hackathon, named Velocihacker following what is apparently becoming a trend. Last time, I ended up spending much of my time floundering over a Qt bug that apparently already got fixed the week before. This one was somewhat more productive. (Not to say the floundering wasn’t interesting or useful in itself. Source-diving a large project like Qt is always an adventure.)

As of this hackathon, I’m now a BarnOwl maintainer. Yay! Nelson helped me through the release process for the barnowl locker. (The versions are, quite excitingly, parallel-installed.)

After that, I went to work on a problem we’ve been having. So, the locker contains builds for various different platforms, but they all need to show up under bin. So, there is some magic in AFS to translate @sys components in paths into your sysname, a string which identifies your platform and architecture. For instance, the SIPB-run Linerva dial-up has a sysname of i386_deb50. Lockers typically symlink bin to arch/@sys and everything magically just works.

Well, not quite. BarnOwl actually uses a wrapper script which launches the executable at BARNOWL_REAL after modifying the environment as appropriate. But other than that, all is good.

Except Athena only puts adjacent Ubuntu and Debian releases in the same sysname. In particular, Debian Lenny and Ubuntu Karmic share sysname suffix deb50. But, they include incompatible versions of libzephyr. Karmic includes zephyr 3 (with soname libzephyr.so.4) while Lenny includes zephyr 2 (soname libzephyr.so.4). So, we spent much of the hackathon messing with the build scripts and wrapper scripts to work around this issue. We eventually decided to incorporate the zephyr soname into the version for the lenny/karmic sysnames and modified the wrapper script.

A bit of work and fiddling later, and BarnOwl runs on both Karmic and Lenny out of the same sysname. It’s a fairly ugly hack, but it works. In the future, I hope to reorganize the BarnOwl locker to be a little cleaner; right now the folder hierarchy isn’t quite what I’d like. It’d also be nice to make this dispatch less of a hack, but I don’t know how to solve this problem in general. My preferred solution to these sorts of problems is to declare that we don’t care and parallel-install conflicting libraries as needed. However, zephyr requires a zhm be running on the machine, so we have dependency on the actual system; it’s no longer clear how to transform a global conflict into a local one. I guess we could try to run two zhms, but that seems ridiculous.

I also fixed an annoying redraw/resize issue, but that will likely wait until the master is ready to take changes for the 1.7 release. 1.6 isn’t out yet. Hopefully I will also have time in the future to finish the massive graphics layer project I’ve been planning for many months now.

A short continuation of the previous post on KDEDIRS.

So, after the KDEDIRS game, I was able to get most of the old programs running. But I had some trouble with the newer ones. KDE is slowly moving all their PIM applications to this framework called Akonadi. As of 4.4, the contacts were maintained by Akonadi.

Even though I don’t use much of KDE PIM, the pieces notoriously all integrate which each other, and KDE would constantly try to launch the Akonadi server, even at login (I have since disabled the offending KRunner plugin). Each time it would fail, complaining that the D-Bus services were not configured, among other problems.

D-Bus is the IPC mechanism behind the modern free desktop. It was inspired by KDE3′s old DCOP system and GNOME’s CORBA implementation, and has since replaced both its predecessors. Now, D-Bus has this concept of services. These services allow D-Bus to automatically launch a service when one attempts to connect to a name.

While the services for the system bus are a hopeless cause for me, I should be able to influence my session bus as I wish. dbus-daemon‘s man page does claim to follow the XDG Base Directory Specification, so everything should Just Work. I set XDG_DATA_DIRS and D-Bus picks up my session files.

But it doesn’t. Inspecting the process’s environment (via /proc/PID/environ) reveals that my changes don’t take effect.

The problem: D-Bus is not launched by my .xsession, where all the magic happens. D-Bus is launched by login manager! (Well, indirectly.) In /etc/X11/Xsession.d/ are files that get sourced by your login session. In particular, /etc/X11/Xsession.d/75dbus_dbus-launch puts dbus-launch into the startup sequence before I ever get to do anything. It is conditional on a STARTDBUS variable, but I am unaware of any way to modify that for my session alone. Removing this script or otherwise messing with it is not fair game; the goal is that I should be able to log back into system KDE safely having not modified any files it cares about.

So, lacking a better way to do this, my KDE 4.4 startup script contains this terrible little hack:

# Kill D-Bus
killall -u "$USER" dbus-daemon

# Launch KDE
exec dbus-launch --exit-with-session startkde

At some point when I have time, I’ll investigate how NixOS manages this. I imagine they patch the display manager or session scripts at some level.

Continuing from the previous installment on lockers.

So, you would think that, with the previous path setup alone, things would Just Work. Of course, there’s a minor issue needing a newer Qt than Ubuntu provides in Karmic, but that’s easy to fix with another locker. In fact, one could even download the LGPL SDK installer for Linux and use the folder as-is as a locker.

And, indeed, this mostly worked. However, I did not simply want to run my own build of a desktop. I wanted my original software to still work, but use the newer libraries. There, I ran into a problem. If I tried to launch yakuake, a terminal that I like to use for things like zephyr, I got this strange error:

I'm sorry Dave. I'm afraid I can't do that.

Well, that’s a bother. To understand what happened, let’s look at how KDE applications locate files.

At the heart of the core kdelibs library is KStandardDirs. (KDE’s API pages are down right now, so I shall direct you to this mirror a developer set up.) When a KDE application wishes to locate a file, it does not hard-code a path or use a compiled-in PREFIX value. Instead, it asks KDECore to find it for them. You provide a resource type (such as data, lib, or config) and a file path. KStandardDirs then goes and locates it for you.

Reading down the docs a bit, we see that the class works by checking a set of registered suffixes for the resource type against a set of roots. (It also does some other magic like appending the application name for some resources.) These roots include the compiled prefix and a colon-separated variable KDEDIRS. This prefix is the prefix kdelibs was compiled with, not the application. As I was using my own KDE, of course it could not find Yakuake’s files. Aha! So I add /usr to KDEDIRS and everything works.

I'm sorry Dave. I'm afraid I still can't do that.

Bah! What’s going on?

Well, if we look at the set of prefixes, the standard suffix for data is share/apps. This fairly KDE-specific namespace in a global install gets stuffed under /usr/share/apps, which is offensive to distributions, so they like to redirect it to /usr/share/kde4/apps. A few other directories get a similar treatment. In Ubuntu’s case, a snippet from /usr/share/pkg-kde-tools/makefiles/1/variables.mk reveals the cause:

# Standard Debian KDE 4 cmake flags
DEB_CMAKE_KDE4_FLAGS += \
        -DCMAKE_BUILD_TYPE=Debian \
        -DKDE4_BUILD_TESTS=false \
        -DKDE_DISTRIBUTION_TEXT="Kubuntu packages" \
        -DCMAKE_SKIP_RPATH=true \
        -DKDE4_USE_ALWAYS_FULL_RPATH=false \
        -DCONFIG_INSTALL_DIR=$(DEB_CONFIG_INSTALL_DIR) \
        -DDATA_INSTALL_DIR=/usr/share/kde4/apps \
        -DHTML_INSTALL_DIR=/usr/share/doc/kde/HTML \
        -DKCFG_INSTALL_DIR=/usr/share/kde4/config.kcfg \
        -DLIB_INSTALL_DIR=/usr/lib \
        -DSYSCONF_INSTALL_DIR=/etc

My kdelibs, however, were compiled directly from upstream sources (in fact, I compiled from the 4.4 branch on a git-svn and hack on it myself). Moreover, these settings fail to set the standard suffixes, only a compiled-in value. (Kubuntu also carries a patch that changes the system-wide FindKDE4Internal.cmake. It may actually register suffixes. I’m not sure.) When using the system kdelibs, these compiled values do their job and everything works fine. However, this makes the system KDE files special in that they are only a priori accessible via the system kdelibs. While I can inform KDE of the system root, the suffix is wrong.

So, I add a little hack. I have yet another locker, kde-kubuntu-fake which contains a fake additional root for each of those directories. This contains merely a symlink farm:

kde-kubuntu-fake
`-- share
    |-- apps -> /usr/share/kde4/apps/
    |-- config -> /usr/share/kde4/config
    |-- config.kcfg -> /usr/share/kde4/config.kcfg
    `-- doc
        `-- HTML -> /usr/share/doc/kde4/HTML

which also gets added to my KDEDIRS. Finally, after all that work, I can launch Yakuake.

So, hopefully this will help convince that random distribution patches like this are sketchy. Admittedly, given the mistake of trying to mush all packages into one single hierarchy under /usr, the namespace poisoning of /usr/share/apps is a little obnoxious, and this is a defensible change. Still, such things do prevent the compatibility between distributions and upstream and make it very hard for a unified free desktop platform to ever emerge from this tangled mess we have now.

C++ is a hideously complicated language with many little-known features and details. One of these features is member pointers, which we shall play a few games with here. The feature itself is largely useless, but quite amusing.

C++ allows pointers to a member of a class. This can be a pointer to a member function (in which case you get a delegate) or a pointer to a data member. Now, for reasons I won’t go into, member function pointers are incredibly complex. Member data pointers, however, are fairly simple; they’re just type-safe offsets with strange syntax (and limited use).

The syntax is as follows:

struct A {
    int a;
    int b;
};

int main() {
    A object;
    int A::* some_field = &A::b;
    object.*some_field = 27;
};

The type declaration states that some_field is a member of class A with type int. This is precisely an offsetof.

The C++ language doesn’t allow you to easily cast these into longs, but you can use the usual offsetof pointer trick to do it.

template<class C, class V>
inline unsigned long memptr_to_int(V C::*ptr) {
    return (unsigned long) &(((C *)0)->*ptr);
}
// ...
int A::*some_field = &A::a;
unsigned long offset = memptr_to_int(some_field);

The compiler will also allow you to change either of the types embedded in the pointer with a reinterpret_cast, for instance:

int A::* foo = &A::field;
char B::* bar = reinterpret_cast<char B::*>(foo);

Using this, we can cast any arbitrary constant integer to a cast:

template <int N> struct offset_struct {
    int pad[N];
    int field;
private:
    offset_struct() {} // forbid actual construction
};

template<class C, class V, int N>
inline V C::* const_to_memptr() {
    return reinterpret_cast<V C::*>(&(offset_struct<N>::field));
}

// ...
int A::*some_field = const_to_memptr<A, int, 5>();

Sadly, I have not yet found a way (short of terrible tricks with unions) to convert an arbitrary integer variable into such an offset. So, if you need offsets which (almost) prevent you from pointing to any undefined fields in a class, C++ data member pointers are what you want.

In practice, this construct sees considerably more use as a template argument, or something similarly inlined. The actual pointers tend not to be created. For instance, in the Boost.Python library, they’re used to create properties out of fields.

Isn’t C++ fun?

Spring break is over. As expected, I didn’t manage to finish most of my projects for the week, but I did manage one of them: my laptop is is now running an install of KDE 4.4 parallel to the system 4.3 provided by Kubuntu.

A parallel KDE 4.4, with the, uh, most important apps in KDE: KNetWalk and Potato Guy

Why I did this was described previously. Actually managing it was not that simple. We do not live in a perfect world, and indeed it’s silly to expect all of KDE to run without any root activity — any setuid portions, or global dbus configuration, for instance. Still, I wanted to try. For this and the next few posts, I’ll talk about the setup.

I have been managing software out of my home directory for quite some time now. To that end, I’ve built up a collection of functions in zsh, my primary shell. (There’s no particular reason why they’re in zsh; I just prefer it to bash.) They are inspired by the software lockers of MIT’s Athena system and the runtime setup of of Zero Install. At some point, I expect this system will converge to something that smells very much like part of Zero Install.

Any time I need some software which Ubuntu does not provide, I build it myself (or, if I’m lucky, find binary to unpack) isolated somewhere in my home directory. The current convention so far has been ~/pkg/PKGNAME for random software or ~/proj-build/PROJECTNAME for things I’m working on, but I’m not particular happy with this naming scheme. (It’s come up mostly by accident. I’ll likely move everything into ~/pkg or something.) Every locker contains approximately a UNIX directory tree.

A set of (fairly hacky) shell functions then inject subdirectories, as appropriate, into the environment when a locker is to be added. Unlike Zero Install, the variables are not specified by the locker. Instead, the shell script will look for, e.g. bin, and add it to, e.g. PATH, if it exists. This was mostly done out of laziness. At some point, variable choices will become the locker’s business. Current variables set include

• PATH
• LD_LIBRARY_PATH
• PKG_CONFIG_PATH
• MANPATH
• PYTHONPATH
• XDG_DATA_DIRS
• XDG_CONFIG_DIRS
• INCLUDEPATH
• CMAKE_PREFIX_PATH

There are two commands, borrowed from Athena, to add a locker to an environment. The first is dir_run which runs a command with the given locker injected. The second is dir_add which injects a locker into your current environment. I primarily use dir_run with fancy completion scripts, but my dot files dir_add any lockers which I use often or want injected into my standard environment.

So far, this setup has allowed me to run my system evince and okular on a development build of popper when I hack on it. It’s allowed me to maintain a local build of git. It’s allowed me to parallel-install multiple snapshots of Chromium. It’s even allowed me to, via dir_add, replace my system’s PyKerberos, when a bug in the packaged version prevented system software from using it. And, indeed, it allows me to run KDE out of my home directory.

Of course, building KDE for this wasn’t simply a matter of stuffing things into a folder and launching it. There were numerous problems along the way which I had to address, which I’ll describe in later posts.

If anyone wants my hacky scripts, they can be found in my athena Public. A disclaimer: they are hairy and very much need a cleanup. Also, they might need to tweaks to work well in bash; zsh lets me be lazy about quoting arguments. All that said, it’s sufficient for my needs and, despite being far from a true package management system, I think superior to anything apt or dpkg offers when it comes to maintaining different software configurations in parallel.

It’s no secret that I am unhappy with package management on Linux. One of these days, I’ll gather coherent enough thoughts on how things should work. In the meantime, here’s a glimpse at one of the biggest problems today.

If you look at the package management stacks in use on Linux today, be it apt/dpkg or yum/rpm or whatever, they share a fundamental assumption: there will only ever be one version of any package on the system. I argue that this mode of thinking is simply incorrect for a package manager on the free desktop. We need a package manager which fundamentally assumes parallel installation of packages. While correct parallel-install semantics are difficult, the flaws it fixes are well worth the effort.

Testing

One important use for parallel installation is testing. The user-base on any platform is different, and multiple configurations should be tested. One possibility is to use a separate machine, but this is painful. Indeed, Microsoft has not solved this problem; web designers wishing to run IE 6 and 7 concurrently were recommended to use a virtual machine.

When I used Windows, I used Portable Firefox for this. On Linux, I similarly download the official tarballs and run them out of my home directory, taking care not to eat my profile. But why should I manually manage this when I have a state-of-the-art (if the rumors on every Ubuntu advocate’s top 10 lists are true) package manager on my system!

Safe fall-backs

Related to the needs of testing environments is the ability to fall-back when software breaks. for instance, my current browser of choice is Chrome. Now, Google provides an apt repository for Chrome, and yet I use the Chromium nightlies. The apt repositories force me into a single-install setup. Chrome is a very fast-moving target, and things sometimes break. Yet, I appreciate the movement as features I require quickly get added, such as client-side certificates. There is a simple solution with parallel installation: I keep around my old version when updating to a new build. If the new one proves unstable, I just revert to using the old one.

(These days things are less unstable than before. Should Youtube’s HTML5 video fix its quality problems, I’ll likely start using Chrome proper. Of course, my Chromium setup still parallel-installs, so I can rollback at will.)

But why bother? I can just uninstall the new version and install the old version. In practice, this doesn’t work. A month or so ago, KDE 4.4 was released. I, being the avid KDE user that I am, was eager to try it. Well, Kubuntu offered backported packages… why not? I can always go back to 4.3 if I wanted, right? To make a long story short, no. When I rolled back, dpkg and apt got woefully confused and I reinstalled most of the software on my machine. I am now in the process of creating a KDE 4.4 to run out of my home directory. When the last few remaining kinks are ironed out, I’ll describe the setup.

As they say, the best code is code you don’t have to write. Likewise, the best rollback procedure is one you don’t have to perform.

Incompatibilities

Finally, parallel installation acknowledges a fundamental fact of library compatibility: no two different pieces of software are completely compatible. Distributions love to force every package to use the same copy of every library. Most of the time, this is a sound and sensible goal. But it often falls short of reality. Even if the author of a library is very careful about keeping API and ABI working, programs may depend on subtle effects.

Take, for instance, this hypothetical situation. libfoo has a bug which causes some functionality of bar to fail. Bar eventually diagnoses this and perhaps even sends a patch to libfoo. In the meantime, bar should still work, so bar adds a workaround for this bug. This is, sadly, not compatible with the fix, so the workaround is conditionalized on libfoo’s version. Now, a distributor comes along, packages an older libfoo for stability, but backports the fix. Now bar fails to work on that distribution. Think I’m exaggerating? Search for “Debian” on these Eclipse release notes. Indeed, their solution is to install a different version of GTK+. Would it not be better if we could parallel install GTK+ and only use this specially crafted one for Eclipse?

Sometimes a package may even be incompatible with itself. SQLite has countless incompatible build options. The only possible solution is for every program to bundle its own SQLite in parallel.

Conclusion

Linux package managers of today are inadequate for supporting a platform for developers, content producers, and users. We need package managers which allow as much of the system as possible to be parallel-installed to support the evolving, disorganized nature of the Linux desktop.

Often when solving a problem, a useful approach is to do some local work which then reduces to a smaller instance. Sometimes this smaller instance can be complex to build. In the case of Kruskal’s algorithm for finding a minimum spanning tree, we pick edges and recurse over a reduced graph. Specifically, we identify two vertices as “the same”, merge them together and continue. Well, we can literally merge the vertices, but if vertices have many degrees or the wrong edges are picked, it is easy to get a needless O(N²) or the like. We would like to do this more efficiently.

Having a dynamic notion of “sameness” is common in many problems. Quite conveniently, there is a data structure that allows one to track this efficiently, called union-find or the disjoint-set data structure.

The spec of union-find is as follows: Initially, we have N objects and N buckets, with object i in bucket i. We then provide two operations union and find. find takes an object and returns the bucket it lives in. union takes two buckets and merges them into one. Naively, implementing this efficiently isn’t trivial. To implement union, we must alter state of many objects at once. To resolve this, we do what is often done in data structures and lazily post-pone work done on writes to read time.

For every object, we create a node with a single pointer coming out. This pointer means “I am in the same bucket as”. A self pointer means that this object is also a bucket (or they are the representative element of their bucket). Initially, our structure looks like this:

To union buckets, we take take their representative elements and hang one under the other. For instance, we were to union 1 with 2, and then 3 and 5 with 4, it may look like this:

Note that these are trees, but with only parent pointers. To find, we just walk up the structure until we reach a bucket and return. However, we’ve offloaded perhaps too much work at read time. It is very easy to reach this configuration, with an arbitrarily long chain:

A find of 5 will take linear time — unacceptable. The whole point of this exercise is to avoid linear queries. However, we may add a simple optimization. When unioning two trees, we have a choice: either the first hangs below the second or vice versa. It is better to hang the shorter one underneath the taller one, to avoid increasing the height. (If the two trees are of equal height, we must increase by 1, so pick arbitrarily.) To manage this, we do a little book-keeping and maintain the tree of each node’s subtree. This is called union by rank. It turns out that this alone will guarantee balanced trees. Each operation will run in time O(lg N). That’s already pretty good, but we can do better!

Consider a fairly expensive find. We may traverse something like this:

So, now we’ve learned that find(5) = 1. Now, I ask you this again. And again. And again. Each time, we walk up the tree. Why bother, when you can cache? We can just repoint 5 from 4 all the way to 1. But why stop there? We traversed 4, so why don’t we rewrite its pointers?

By rewriting every edge along any path we walk, we never traverse a path twice. By paying for one expensive find of 5, we speed up future queries to anyone on the path. Furthermore, queries to anyone underneath those nodes (7, 8, and 9) get sped up too.

This optimization is called path compression. By a fairly involved proof, one can show that, using path compression alone, we obtain amortized O(lg N) performance.

So what if we put them together? With both path compression and union by rank, we bring the time down to O(α(N)) where α is the inverse Ackermann function. This is a ridiculously fast-growing function. A(4, 4) is 2^265,536, which is far bigger than any number you will care about. Furthermore, you can prove that any implementation of this must make O(α(N)) operations amoritized. So, not only is this fancy expression for O(4) possible, but is its optimal. It’s also extremely simple; a couple dozen lines of your favorite language will suffice.

Follow-up to A Very Subtle Bug from nelhage, reposted from a discussion on zephyr.

The tar format is, conceptually, a very simple one. You concatenate a bunch of files together and preface each with a metadata header (path, size, etc.). Partial extraction of a single file requires a linear walk across the archive until you find the record you want. Of course, once you’ve extracted it, the file can be closed and no more work need be done. This, combined with a piped gzip and Python’s odd SIGPIPE handling, gives the problem from nelhage’s A Very Subtle Bug.

But the details don’t quite seem to work that way. lbzip2 on reddit notes that, on a large file,

GNU tar 1.20 didn’t stop reading from lbzip2 after finding and extracting the file from the tar stream. (That stream continues after the specified file for another 270M or so, and the compressed tarball continues for another 47M or so.)

So what is going on here? Because it’s so much fun, let’s source-dive! The primary loop is a read_and function in src/list.c (abridged):

/* Main loop for reading an archive.  */
void
read_and (void (*do_something) (void))
{
  /* [Initialize some things...] */
  open_archive (ACCESS_READ);
  do
    {
      prev_status = status;
      tar_stat_destroy (&current_stat_info);

      status = read_header (false);
      /* [Call do_something () per appropriate header] */
    }
  while (!all_names_found (&current_stat_info));

  close_archive ();
  names_notfound ();            /* print names not found */
}

Certainly looks like we close the archive after we’ve seen everything we care about. Looking at all_names_found from src/names.c, it iterates over the arguments reasonably and checks if they’ve all been seen. However, there is one funny check before that loop:

  if (!p->file_name || occurrence_option == 0 || p->had_trailing_slash)
    return false;

occurrence_option corresponds to the --occurrence option. Quoth the man page:

 --occurrence
       process only the NUMBERth occurrence of each file in the archive;

What does that mean? Well, like I said, tar files are very simple. You concatenate files together. They are so simple that duplicate files are allowed. Both versions get extracted and the later ones override the earlier ones. tar does not, and cannot, abort upon seeing all files because there may be newer versions later. The --occurrence option allows you to specify that you want a particular set of versions. Only then will tar prematurely cut off the pipe.

Given that, why the occasional SIGPIPE bug? We’ve established that, by default, tar will not prematurely close the pipe after extracting, so there must be some place where we close the pipe. Looking back to read_and, it does break out of the loop in other cases: end of file (HEADER_END_OF_FILE) and NUL block (HEADER_ZERO_BLOCK). The latter is handled by this snippet (abridged):

    case HEADER_ZERO_BLOCK:
      if (block_number_option)
        {
          char buf[UINTMAX_STRSIZE_BOUND];
          fprintf (stdlis, _("block %s: ** Block of NULs **\n"),
                   STRINGIFY_BIGINT (current_block_ordinal (), buf));
        }

      set_next_block_after (current_header);

      if (!ignore_zeros_option)
        {
          /* [Long comment about POSIX compatibility, disabled warning] */
          break;
        }
      status = prev_status;
      continue;

Unless one passes -i or --ignore-zeroes, NUL blocks are treated as EOF. And indeed, if one inspects a random tar file with -i and --block-number,

davidben@rupert:/tmp% tar -tzf tar_1.22.orig.tar.gz -i --block-number | tail
block 22151: ** Block of NULs **
block 22152: ** Block of NULs **
block 22153: ** Block of NULs **
block 22154: ** Block of NULs **
block 22155: ** Block of NULs **
block 22156: ** Block of NULs **
block 22157: ** Block of NULs **
block 22158: ** Block of NULs **
block 22159: ** Block of NULs **
block 22160: ** End of File **

(This file appears to end in 22 of them.) And now we have the culprit. Tar files end with a few NUL blocks, signifying end-of-file. tar closes the pipe on the first, leaving a few blocks written by gzip and ignored by tar. This race condition allows for tar to finish before gzip does, triggering the Python problem.

A final note: don’t start passing --occurrence to all your tar calls. The logic in all_names_found does rather odd things with directories and does strange things with some tarballs. This will be the subject of a future post, possibly after some mail with bug-tar@gnu.org.