Category: Coding

Now for the chronicle of a bug clearly caused by poor variable names. (And arguably also the lack of semantic meaning given to string types.) This  buggy function searches for a device with a given uuid:

/*
 * Search the specified glob for devices; return error code. On
 * success dev->fd is set to a valid file descriptor and the file
 * is locked.
 */
static int __find_dev(struct vdev *dev, struct uuid *uuid,
                      const char *const path)
{
	glob_t paths;
	int ret;
	size_t i;

	ret = glob(path, 0, NULL, &paths);
	/* Error handling omitted... */

	for (i = 0; i < paths.gl_pathc; i++) {
		const char *const fname = paths.gl_pathv[i];

		dev->fd = mopen(fname, O_RDWR);
		if (dev->fd < 0)
			continue;

		if (is_requested_device(dev->fd)) {
			ret = __try_dev(dev, uuid, path);
			if (!ret)
				goto found;
		}

		close(dev->fd);
	}

	ret = -ENOENT;

found:
	globfree(&paths);

	return ret;
}

mopen() is given fname, the path produced by glob(), but __try_dev() is given path, which is actually a glob. This caused the device to import correctly but report as its path the glob used to find it instead of its actual path. path is now named search_glob, and fname is now named path. Our existing tests did check that the device path was reported correctly, but they didn’t catch this because they all explicitly specified the exact path to the device to use, so the search glob was the correct path. If the search glob had been some kind of glob type instead of a string then the patch that caused this bug wouldn’t have compiled.

First a bug, then an exercise in assuming the common case.

We were parallelizing a single-threaded operation to increase throughput and came upon a race condition that at first manifested as crashing only on Ubuntu. One thread read jobs from the disk and passed them to an existing worker pool for processing. Once all processing was complete, the reading thread exited. When a worker finished processing it marked its job as complete, then released its locks. This could result in releasing a freed lock – because the thread pool was also needed for other purposes it wasn’t joined first. My best guess as to why it only showed up on Ubuntu (and Debian, it turned out) is that it has different defaults for what we assume to be stack protection, though that wasn’t clear from listing them with gcc -Q --help=target. Though changing the order of lock releases solved the immediate problem there were also issues with deadlock due to dependencies involving the thread pool. We ended up having an additional processing thread that was joined before exiting, which avoided the problem.

While this parallelization does get its speed from doing previously single-threaded work in a thread pool, it has a twist. A final processing step must be done in disk order, but waiting for the processing slowed down reading. By reading speculatively as though processing had succeeded, we achieved a ~2x performance increase. Yay!

Freenet is decentralized, so while it’s (intended to be) a small-world network and thus short routes exist between any two nodes, it can be difficult to have a routing algorithm which can find those routes using only local information. As far as I understand it, Jon Kleinberg’s work (brief, paper) forms the basis of Freenet’s networking model. We don’t have local connections, as they’re expensive to form and in empirical testing actually detrimental to performance, but apparently the model still holds. A core finding from this work is that if connections are distributed so that more-distant connections are less likely, an implicit structure forms which allows forwarding a message to the closest peer at each hop to form a shortpath. As Freenet uses 1-dimensional locations, this distribution is based on a probability which is proportional to the inverse of the distance. The ideal distribution is logarithmic, but from what I’ve gathered, Freenet’s distribution isn’t too close to it. Making the actual match the ideal is difficult – the network size is a factor in the distribution, but it cannot (practically) be known. Techniques by Oskar Sandberg (paper) are intended to produce this distribution without such knowledge, but Freenet’s implementation seems to not behave as intended. I hope to help discover why, and how to fix it.

Edit May 2, 2012: I replaced a rather dubious ideal distribution plot made with a quick Python script with a much better-looking one made with a real simulator. Here are both distributions on the same plot:

Edit August 1, 2012: Corrected Y axis label to refer to the percent of links, not nodes.

I’m working on putting together Node-to-Node Darknet chat for Freenet. I was originally working on it as a mainline Freenet feature, but then I realized that it was too large of a feature to be present outside of a plugin. The plugin interface seems, from what I’ve seen, disturbingly close to the internals of Freenet: much of the code I was writing when internal to Freenet is very easily translated to the plugin. I hope I’m either misjudging things or doing it wrong. For example, I need to have a listener for my chat messages, and to register it, I call the same method from the plugin as I would internally. To send a message, though I can no longer add code to DarknetPeerNode, I can still call the basic message-sending method. Perhaps these things aren’t likely to change, but I somehow expected a plugin interface based more on actions than the internal structure. I hope I can get it working anyway; this has been taking longer than I’d like. I’m trying to learn JQuery as well for a shiny interface.

I upgraded my graphics card driver (AMD Catalyst) in the hope that they’d fixed the bug introduced in 11.5 where the mouse cursor gets stuck and moves choppily in the lower right and upper left corners. They hadn’t, and in the process of installing the driver somehow my sound broke. It started working again this morning. It may have been that I re-added myself to pulse and pulse-access groups and needed to reboot for the changes to take effect, but if not I can’t think of why. EDIT: I think it’s working again now. The HDMI on my Radeon HD 5770 may be conflicting with the normal sound card now for some reason: it’s not listed in sound preferences and the sound is working; when it was the sound wasn’t. It’s worth noting that the “Use audio devices” privilege checkbox is apparently not supposed to be checked. This article is helpful as well. EDIT 2: This article ended up doing the trick to get surround sound output and front panel input working. What worked for me was appending options snd-hda-intel model=auto to /etc/modprobe.d/alsa-base.conf and running sudo alsa force-reload to apply the changes. This is running Ubuntu Natty 11.04.

I’m looking into self-hosted or open source alternatives to Dropbox. After looking at lipsync and sparkleshare, I tried dvcs-autosync as it seemed more lightweight and used XMPP (instead of IRC like sparkleshare) for communication. It didn’t seem to work – changes were committed one file at a time, which was annoying as it popped up a notification bubble for each one. Although one side would appear to log in to the XMPP server and send its status updates, the other side always ignored them. When using Jabber.org instead of a local server, it seemed like only one side could log on at a time. sparkleshare, as it uses git, is incapable of syncing git repos. I’m now trying lipsync, but it’s not working quite right yet. On the upside, it’s a small enough thing that it’s fairly easy to pick up.

My section of Engineering 100 is Microprocessors and Toys, and having started with combinational logic, we progressed to finite state machines, then instruction set architectures, and finally to Assembly. We implemented simple instructions in Verilog, and we are now finally programming on that processor in Assembly. It’s oddly gratifying, although I have many gripes about Assembly. We are using E100: a heavily simplified instruction set without programmer-accessible registers, but even so these difficulties seem basic enough to be widely applicable. So far, the bugs we’ve run into have not been problems with overall logic but with return and jump addresses. An incorrect return address can often restart the program: memory by default holds a value of zero, which is also the address of the start of the program. This makes for an especially baffling form of infinite loop. Using the incorrect destination label for an unconditional branch leads to chunks of code mysteriously remaining unexecuted. I hope we figure out how to do this better, as currently it is often difficult to tell even what the values of variables are because on the emulator they are just one of many hexadecimal values out of several pages of them. Without the emulator it would be even more difficult. I’d rather stare at a page of numbers than have to add wait-for-key loops and hex digit outputs for each breakpoint and value I was interested in.

I’ve made big changes to Cavez of Phear!

Because most terminal windows default to 80×24, it now fits in that space. There is no longer a lives system because it was only frustrating and didn’t add anything to the gameplay. A game should not be difficult through starting over again if you make too many mistakes. With the saves and without the lives, it allows for focus on the puzzles. Upon death, the savefile will load if it’s of the same level. I recoded the key bindings to be cleaner, and it now supports multiple keys for a single command. Sortie made very nice tutorial levels.

The editor is much improved and can now place bombs in addition to bomb packs, apply physics to a level, and make changes in rectangles and whole-level fills in addition to single points.  It also is more flexible in opening and saving files. I also fixed the persistent and seemingly vague problem that it sometimes required multiple keypresses to get back to the main menu. It ended up being caused by recursive calls to main_loop(). There’s now yet another while(true) in the main loop that gets break;‘d out of for it to go back to the beginning and load a level or save as needed. I greatly improved the screen dissolve function – it only writes to each position once, and is guaranteed to cover every location in 1840 writes. I fill an array with all possible positions, perform a Fisher-Yates shuffle on it, then iterate over the array, writing spaces. Writing the shuffle algorithm was interesting. The previous one did overwrite – it was pure rand() – and took 10000 writes, which led to horrid performance over SSH, and it wasn’t even guaranteed to clear everything. In general I’ve tried to improve the UI – the reaper on the main menu only comes in from the left on the first run, after which the menu comes up without pause. I’ve cleaned up a lot of code, but there remains is_ready(), which Sortie tells me has something to do with asynchronous file operations, and do_the_monster_dance(), which I’ve been avoiding because it looks messy.

In playtests I’ve had trouble with people getting confused because they don’t read the directions. I’m resisting making big boxes proclaiming what the controls are because I’m assuming players are intelligent, and so far they’ve managed to figure it out. I got embarrassed when I didn’t realize which commits had gone through and made an inaccurate, duplicate commit. I’m worried that I might get caught up in a never-ending parade of new features and not stop long enough to add more levels. I suppose with all the improvements to the editor it’ll be much easier.

Next on the list of feature additions is support for level packs, cleaning up the level code by actually reading the directory instead of relying on a #define, figuring out why the game spontaneously quits on some keypresses and freezes on Ctrl-S, and perhaps reimplementing the menus in light of the knowledge that ncurses has menu functionality.

If you’d like to try it out, either grab PuTTY and ask me for a shell account, or download the source, compile it yourself, (requires ncurses) and have fun!

EDIT: I like to think that my desk’s keyboard platform is falling off because I coded so hard all day and it couldn’t take the greatness. The friggin’ monitor is hot!