Worst Code Ever

I have my glue code for NBD working to the point where I can implement a simple RAM disk in about 40 lines of Python. Have I mentioned that NBD is one of the most egregiously bad pieces of code I have ever seen? Here’s a particularly heinous example – a “computed goto” in C:

	#define NBD_PROC_LABEL(n) 
		next_label = &&label_##n; 
		label_##n:
	...
	if (next_label) {
		void * label = next_label;
		goto *label;
	}

Some lines have been elided to highlight the awful meaning of the original code. What’s happening is that the macro – used about 20-some times in one routine – creates a goto label and stores a pointer to it in “next_label”. I’m not sure that the “&&label” construct is even legal C; I suspect it’s some gcc-specific abomination. In any case, the “goto” in the lower fragment jumps to a target that changes as the function executes. Ick. The purpose of these gyrations is to do some fairly simple error recovery. In another place the author uses almost the same trick to implement a very simple state machine. In either case the same effect can be had more cleanly and portably in about a half-dozen other ways with no loss of efficiency, but apparently Dr. Breuer wanted to be “clever”.

Yes, that’s Doctor Breuer. This bozo, who uses 400 explicit gotos in 24K lines of code plus more hidden by tricks like that described above, who has written not one line of documentation describing the protocols or interfaces he uses, whose kernel code fails to check array bounds and thus dereferences a null pointer contained in element -1 of an array…teaches computer science at the university level. My condolences to the poor students at Universidad Carlos III de Madrid.

Federated Filesystems

Filesystems are complex. Distributed systems are complex. It should come as no surprise, then, that distributed filesystems are exceedingly complex, and that in a nutshell is why there isn’t one in common use already. What about NFS, you say, or CIFS? Well, those aren’t really distributed filesystems in the sense that I or other researchers in the field use the term. CIFS and NFS are technically referred to as network filesystems, which are distinguished from their distributed brethren as follows:

  • Network filesystems allow remote access to data, but that data resides in one and only one place. This server can be both a bottleneck and a single point of failure limiting availability. Clustering at the server end can ameliorate both of these problems, but they cannot truly be solved without changing the basic architecture. In addition, network filesystem clients need explicit information about where each datum resides.
  • Distributed filesystems “virtualize” data, so that it can be replicated, moved, etc. transparently to address both performance and availability concerns. Distributed filesystem clients do not need to know exactly where a datum is located; this is discovered dynamically and transparently within the system instead.

There are two traditional approaches to distributed filesystem design:

  • In the volume-based approach, each filesystem is based on a single volume providing relatively low-level – often mere block read/write – semantics, responsible for handling data distribution and replication. A layer that runs above this data store provides synchronization and higher-level filesystem abstractions such as directories and attributes.
  • In the more common file-based approach, there is no concept of a volume at all. Every file is treated as a completely separate data store which must be managed and located separately.

The volume-based approach does a good job of “divide and conquer”; each layer has plenty of complexity, and each can manage its own complexity independently. The downside is that the load and availability characteristics of the overall system is limited by the least-distributed layer. In fact it’s even worse than that; as the two layers adapt to changing conditions they do so without coordination, and sometimes might even be working at cross purposes. Lastly, the layering itself inevitably creates some inefficiency.

The file-based approach has none of these problems. Its problem is that tracking each file separately requires more (and more complex) metadata and – more importantly – more network traffic. This additional overhead has brought many file-based distributed filesystems to their knees, sometimes making them all but unusable in anything but a fast-local-network environment – which in my opinion misses the whole point of having a distributed filesystem in the first place.

What I would like to suggest is that in a filesystem containing N files, we need not limit ourselves to either one or N data stores. Instead, a filesystem could consist of a number of volumes somewhere between one and N, linked together in a way that makes the whole thing transparent. For example, a user could create a volume to contain a few hundred of their own files. If those files are popular, the volume might be mirrored and subsequently moved somewhere else to ensure performance and availability, but the association of those files with that volume would remain intact. At the same time, some directories within that volume might actually be links to other volumes elsewhere, which are managed separately and accessed as needed.

This approach bears some superficial similarities to mount points and symbolic links, except that the URI-like links in this case are totally transparent and platform-independent, managed by the filesystem internally instead of being exposed to an OS which is – in most cases – ill prepared to deal with them in the sorts of numbers they’re likely to occur. A closer similarity exists to “junction points” in Windows NT’s DFS.

It might seem that the “root” volume in such a system would still be more critical than others, creating an undesirable point of centralization. In fact that’s not true because there need not be any one root. In a sense, every volume is a root volume, potentially containing using links to create a “personalized view” of the entire filesystem as in Plan 9. Even loops need not be considered a problem. So what if volume A contains a link to B, while B also contains a link to A? That’s not a problem on the web, nor would it be one here. Certainly some roots might begin to seem more “authoritative” than others because of usage, but that’s entirely voluntary. One would hope that the owners of such roots would adopt more robust replication/distribution policies, just as the providers of more popular content on the web use content distribution networks to satisfy the same sorts of goals.

One of the nice things about this sort of “federated filesystem” is that the volume boundaries can match administrative boundaries. Each volume could have its own methods or policies for distribution or authentication, or even its own protocol, within a coherent general framework. The impact of a failure would be limited to a volume, and recovery would involve only that volume, instead of the whole filesystem being affected. At the same time, the prohibitive overhead of finding and tracking every single file would also be avoided. As often turns out to be the case, the middle path might turn out to be preferable to either extreme.

Why Romania?

I finally got tired of explaining why I registered this site in Romania, so I wrote a short explanation. One of these days I’m going to draw a picture of a vampire platypus and use it for a logo.

Reply from David Brin (for real)

I forgot to post the reply I got from David Brin. Here it is, posted with permission and without comment (I’m not worthy). I thank DB, and hope that he doesn’t mind how I’ve reformatted it a little for readability – no content was harmed, I assure you.

re recent events –Above all, I wish people would ask these questions.

  1. Security mavens are demanding tighter restrictions on daily life, while civil libertarians preach we should accept risk to avoid “Big Brother”. Both groups assume a fundamental tradeoff between safety and freedom. But is such a tradeoff real? Can we have both safety and freedom?
  2. Most of the useful video footage during this tragedy was taken by private citizens. Most of the practical and immediately useful communications took place over private cell phones. The only effective direct actions taken – to defeat terror and reduce casualties – were all taken by individuals armed with modern tools of “intelligence” and communications, outside official channels. What does this indicate about the coming era? (See my arguments about a coming “age of amateurs.”)
  3. The actions of 9/11 were facilitated by terror networks that moved large amounts of money secretly and with great ease. Is it time to reconsider the value of banking secrecy?
  4. Consider the possibility that we’re over-reacting with measures for added “security”. No measures will ever prevent small knives from being smuggled aboard airliners, and trying to prevent it will only hurt our way of life. Was 9/11 was caused by lack of security or by a passivity doctrine taught to crew & passengers. This doctrine has already been changed by the brave passengers of flight 93. Instead of getting into a security lather over knives, shouldn’t we simply arm the pilots and get back to our lives?

Sick Joke

ObSickJoke: apparently a bunch of inmates at a prison were given large doses of antidepressants instead of the antiviral drugs they were supposed to receive (that part’s true). My question: were they pissed off about it?

BookmarkSync Goes For-Pay

A while back – 30 August to be exact – I described right here a way to synchronize bookmarks between Windows systems using the Briefcase, but also pointed out that the free service provided by BookmarkSync was really a better solution. Well, today I got mail telling me that BookmarkSync is becoming a subscription at $50 one-time or $40 one-time for existing members, so it looks like I might be using the method I described after all. I might also think about putting together my own free tool/service for this purpose, since it is in fact closely related conceptually to work I already do in the area of data consistency in distributed systems.

Looking For Spam Solution

I’ve been thinking about spam. One of the problems I have is the Taiwanese spammers who send me crap with no To: line, forged sender, etc. I use Outlook Express – not Outlook, and I can’t hear you booing – for email, and because of the munged headers there’s no way I can set up an OE rule to do The Right Thing. What I need is a mail-filtering solution with the following characteristics:

  • It must work with any mail program, on any platform, which pretty much means it must be a POP3/IMAP server.
  • It must be capable of preserving mail-account information so that the user’s mail program can still use the correct account to send replies. This means that the server functionality must support multiple POP3/IMAP mailboxes.
  • It must run entirely on the user’s own machine.

The obvious solution would be procmail, but that seems to fall just short of the second requirement and it doesn’t actually fetch mail itself (it relies on being invoked by the MTA for that) so using it would involve the extra headache of compiling and setting up another program for that purpose – in my case on Windows, which is not usually the primary platform for such things. Fetchmail has the opposite problem: it fetches but doesn’t serve. What I really need is an N-in N-out POP3/IMAP proxy (both client and server) with built-in filtering. Does anyone know of one, especially one that already runs on Windows? If so, please let me know. Otherwise, I might whip one together myself.

Many-Device Distributed Filesystems

I’ve been trying to collect some thoughts on distributed filesystems based on lots of small virtual block devices, for an essay. Expect to see it or a link here soon.

Joust Tutorial

One of the things that’s really great about Joust, and which probably underlies its enduring appeal for a surprising number of hard-core geeks, is its variety. As you go from the first few red-dominated waves to the mixed-red-and-grey waves and on up to the all-blue waves, the game changes quite a bit. Egg waves are a whole different thing; at first they’re opportunities for free points, but at the highest waves they actually involve dangers all their own. Pterodactyl waves are always “special” in their own way that is deliberately intended to foil common stratagems used on other waves. Most good players eventually reach a state where they lose more men on pterodactyl waves than on all other waves combined.

As a result of this variety, not every suggestion works in every circumstance, or for every player. Some of the things that every Joust “millionaire” does routinely and feels compelled to do would be absolutely suicidal even for a player at the 300K level. I’ll try to identify these sorts of limits, but I also encourage you to exercise caution on your own. You have been warned.

Before I get to the actual hints, let’s clarify some terms:

Launchpads
These are the four (sometimes three) points where enemies appear.
Platforms
Platforms are permanent, and there are two: one at the bottom of the screen (the “floor”) and one that wraps around on both left and right about half-way up. Three of the four launchpads are on the platforms – one on the floor, and two on the upper one.
Islands
Islands are temporary; they come and go depending on the level. There are actually three, though there appear to be four: one high up in the middle (with a launchpad on it), one between that and the floor, and one that wraps around on both left and right a little above the first. I refer to these as the upper, lower, and side islands respectively.
The Step
The upper platform is divided into two parts, with the part toward the center on the right higher than the rest and separated by a small crack; I call the transition point the step. You can go through the crack if you come along the lower part of the platform on your belly – you have to fly in low from the side – but I rarely find it useful. Eggs and opponents, including pterodactyls, can also go through it, and it’s worth watching for. The most important thing about the step, though, is its value for sudden direction changes; if you run into it going right to left, you very quickly find yourself going left to right. This is extremely useful, particularly on egg waves.

And now, the basics:

  • Learn how to control your bird. Well, duh. Seriously, though, this involves a lot more than just the basics of figuring out how high a single flap moves you and how to move from side to side. Experiment with how two- and three-flap bursts differ from single flaps. A flap can move you horizontally or vertically, or both; learn when it will do which, and how much. Make sure you know the effect of hitting an obstacle; the way that you bounce is one of the least physically-realistic parts of the game, and forms the basis of several useful tricks that the computer already knows. Don’t forget that the top of a screen is an obstacle too, with its own interesting rules and uses.
  • Know your enemy. Reds, greys and blues all have characteristic patterns of movement. A friend used to believe that there were actually two kinds of blues, which needed to be handled differently; I never quite believed it, but I sort of believe there are two kinds of reds. Did you know reds are actually stronger fliers than greys? Reds and greys – particularly reds – have patterns of flying level for a while, then suddenly rising at a particular angle, based on where you are.
  • Develop “situational awareness” so you always know where everything is and can anticipate where it’s going. Learn to recognize “attack formations” such as one bird slightly above and behind another so it can cream you when you go for the leader. Pay particular attention to the edges; the “playing area” is actually very slightly larger than the visible screen, creating a hole not quite big enough for an enemy to hide but big enough to throw off your ability to anticipate.
  • Learn where your sanctuaries are, and how to get there, for when things get too hot. For example, learning to “drop in” under the lower island and handle close-in fighting there can save many otherwise-disastrous waves. The spot at the right end of the floor is great for stuff coming in from your left – even from above – when there’s no lower island, but is also dangerous when stuff’s coming in from your right (including those that slip through the little crack in the step). In general, note the general “flow” of your enemies – left to right or vice versa – in choosing non-center sanctuaries.
  • Track your eggs. A successful start to a wave can easily turn into a disaster if you let the last couple of guys keep you distracted until the eggs from previous victories hatch into more difficult opponents. Get used to timing the eggs yourself, and use “idle time” – e.g. when opponents are stubbornly refusing to come to your level – to clean up.

If you just practice these basics, you’ll have no trouble with the early waves – up to fifteen certainly, and decreasingly for the next fifteen. While no special tricks are necessary, you should find yourself frequently planning and executing certain maneuvers. Luring an opponent under the top island before turning around to nail them as they come up the far side is a good one; getting a double kill by bouncing off an opponent coming toward you into one following you is another. As you become more comfortable, you should start taking the best opportunities to kill pterodactyls too…but don’t push it. While killing pterodactyls is both useful and fun, I find that even at the highest levels it never really becomes a central part of my strategy.

The one “trick” that’s essential has to do with egg waves. Here’s the drill:

  1. Start at the left end of the side island (which is always present for egg waves).
  2. Run right-to-left all the way along the side island. By this time you’ll be going at full speed, and your momentum will allow you to sweep the upper island right to left as well without extra effort (though one flap while crossing the gap doesn’t hurt).
  3. Let your bird keep running off the precipice, down to the middle platform. You will land in front of the step, hit it, and reverse direction. Keep in mind that the birds always come last to the part above the step, and don’t worry.
  4. Keep running across the lower island. It’s a matter of taste whether you slow slightly to sweep the whole thing or not, so long as you’re at full speed when you reach the right side.
  5. As you come off the lower island, going left to right, do three quick but deliberate flaps. This will be just enough to avoid the lava troll without missing an egg on the very left edge of the floor. If there is no egg at the very edge, flap four times.
  6. Sweep the floor from left to right, then ascend to the level of the lower island.
  7. If you didn’t slow down to sweep the lower island before, take care of the left end now and slow your momentum just a tiny bit so you can execute the last step.
  8. As you cross the center of the lower island, flap so you can hop onto the part of the upper platform above the step and pick up the last eggs.

I captured a short video (400K) demonstrating the basic technique. Yeah, AVI sucks, but that’s what the program I used produces and I’m too lazy to convert it.

This approach works marvelously all the way up to at least wave 40, even on higher difficulty settings (the difficulty setting affects egg-hatch time). After that you’ll start to run out of time, and you’ll have to make smart decisions about when to abandon the egg-hunt and take care of a mounted opponent. By the time you’re able to reach those levels, you won’t have a problem with this.

When the blues start to predominate, you need to know a few things about them:

  • Blues have a distinctive “looping” pattern of flight, requiring a special kind of awareness of the points where they’ll be high and low. You have to nail this exactly; unlike reds and greys, where missing by a little just results in a “draw” and you get to try again, missing a blue by a little bit is one of the best ways in the game to get killed. You’re better off being a long way away than being just a little off center.
  • The blues’ flight patterns near the top create certain “hot spots” immediately above the launchpads and – to a lesser extent – precisely in between them. Despite all the variations in movement that exist, if you’re in one of these hot spots you’ll win far more battles than you lose. Think of them as attractors in chaos theory.
  • Blues are amazingly vulnerable when they’re running along the ground. The two- or three-flap “hop” to take them out as they run toward you is any good player’s most frequently executed maneuver and often the foundation of their high scores.
  • Blues are also pretty stupid about the edges of islands and platforms…usually. Sometimes they’ll surprise you, so watch out. The trick of hanging just next to the edge of a platform or island, without any gap, waiting for a lower blue to come right along the bottom of the obstacle and up into your bird’s butt, is totally standard. This makes the sanctuary at the right end of the floor especially important. A well-timed pop up next to the near edge of the upper platform often provides happy hunting, and if you miss you can often get a second chance just above that – off the right edge of the top island when it’s present
  • The single piece of knowledge that most clearly distinguishes a novice from a master in Joust is awareness of how blues respond to your altitude when they first appear (waves 16 and above, not from eggs). Here’s the key: if you’re below them when they appear, they won’t fly off their platforms. They’ll take the maximum time to appear, and then they’ll walk toward you. When they reach the edge of the platform/island above you, they will drop down in a very characteristic fashion that makes it easy to pick them – and their eggs – off if you know what you’re doing.

These facts about blues, and the distributions of greys and blues in the various waves, suggest certain strategies. At this point you’ll see good players developing certain styles; here are some suggestions based on my own:

  • In waves from 16-20, I usually don’t bother doing anything special. An intermediate player might consider picking off the first grey guy at the top level, then dropping down to pick greys off from the “caravan” that forms at the middle level. Staying low like this has the advantage of keeping the blue – which will normally appear on the top platform – “frozen” at first. This is a good way to practice a common maneuver – a timed swoop upward on a trajectory that causes them to “lift off” right into you.
    BTW, wave 18 is still often my worst of the game. I hate mixed blues and greys more than I hate all blues because they require two different and often conflicting approaches.
  • For 21-29 I stay on the floor launchpad, under the bottom island at first, but then “naked” afterward. It is safe, though it can be tricky and more than a little nerve-wracking. Knowing greys’ habits, especially when they collide with each other, is a must for this. Just let everyone come to you. Don’t stray too far from that bottom launchpad; you don’t want anyone appearing there.
  • You’ll eventually start having trouble with pterodactyls appearing before you’re done; when depends on the difficulty setting. At this point you need to start practicing the “hover” maneuver when there’s no lower island. At levels 37 onward, there will be no greys coming across and all the blues will be frozen when they appear. Pop directly up from the floor launchpad, being careful to stay below the level of the others. At a certain height, an opponent will appear beneath you and fly almost straight up; look to see which way they’re facing and make small adjustments quickly toward that side to account for the “almost” part. If you miss, just drop down and deal with the “freed” blue however you want; just don’t move far from that bottom launchpad.
    Just get one “extra” opponent this way at first, then two, until you get the hang of it. Before long you’ll be picking off all that’ll come, dropping down only when one of the guys from the other launchpads walks off a cliff.
  • When there is a lower island and there are still greys, you just kind of have to suck it up, do your fighting on the floor as best you can until the pterodactyls show up, and hope for the best avoiding them as you pick up stragglers.
  • When there are no more greys (57 onward) you can do some more sophisticated hovering. When there is no lower island, continue as before; it’s still the best. When there is a lower island, set up your hover above the rightmost launchpad. If you do it right, this can produce some of the most spectacular killing sprees of the game as you’re nailing guys from left, right and below all at once. Ending a high-number wave in ten seconds is a great way to impress onlookers.
    One side benefit of this approach is that you actually seem to get fewer pterodactyls on some ptero waves if you stay high than if you stay low. Maybe it’s a bug. Several times, though, I’ve noticed that I only had one ptero to contend with when I expected three, and it doesn’t seem likely that I killed two without even noticing.

That’s it. If you master all of the techniques here, you’ll be getting million-plus scores consistently. If you can think of anything else, please let me know and I’ll include it. Happy jousting!

Last Refuge of Scoundrels

Democracy is the Darwinism of ideas. Certain people in certain circumstances, most notably soldiers on active duty, must in the interests of mutual survival take and carry out orders that represent ideas they consider stupid or counterproductive. Even then they are not required to surrender their conscience. In every other circumstance, it is not just the right but the duty of every citizen – including and sometimes especially military personnel – to lend the benefit of their knowledge and intelligence to the betterment of our society. If that means offering up dissent or criticism or even condemnation of policies we regard as wrong, so be it. Suppressing ideas is the surest route to stagnation and eventual extinction.

What brought this on? Well, I’m tired of people calling me anti-American when they themselves don’t have the slightest clue about what it means to be American – and I don’t mean the BS they try to stuff into your heads (I received most of my schooling elsewhere) in school. The founders of the US were a very fractious bunch. The diversity of their views makes the distinctions between “liberal” and “conservative” today look laughably small. Nonetheless, they agreed on certain principles, among which was the principle that they could hold these disparate views without being enemies either of each other or of the nation they were forming. E Pluribus Unum = From Many, One. Think about it. That’s one of the cornerstones of our society, and it’s a principle that has served us well. The people who try to champion America by branding opinions they don’t like as unpatriotic are engaged in a self-defeating exercise – trying to save something by the very actions that destroy it. They’re the true anti-Americans, even though they don’t know it.

If I seem very critical of the current administration’s policies, it’s because I think those policies will lead to more American dead, and those still alive tainted by association with actions that are inhumane and immoral. I think many of those policies are not only morally wrong, but stupid and counterproductive even if you agree with the moral stance. If this were just a game, with no lives or moral issues at stake, I would still look at what Bush is doing and say, “You’re an idiot. You’re causing your team to lose.” Any military strategist from Sun Tzu onward could tell you that you don’t prepare for war by showing one’s intentions before one is ready (especially with regard to intelligence), stiffening the enemy’s resolve by leaving them no choice more palatable than fighting to the bitter end, and alienating allies with your hard-line rhetoric that tars them as well as your enemy. You cannot win a war by adopting the enemy’s terms and giving them what they want, or by destroying the sources of your strength.

But apparently the “patriotic” thing to do is ignore all we know and support plans we realize are stupid. It infuriates me to think that people won’t learn until we’re treated yet again to the sight of American servicemen, caught in a Somalia-style ambush, being dragged dead and mutilated through the streets by terrorist scum. I guess it’s “anti-American” to want to avoid that. I want to see Osama bin Laden and every other terrorist dead as much as anyone. I support legal, financial, and diplomatic means, military action and even “assassination” (a misnomer in this situation) to that end. I just happen to think that we can achieve that goal without killing more of our own or sinking to the terrorists’ moral level. That’s about as pro-American as one can be, and anyone who thinks otherwise will just have to grow a brain.