Aug 19

GPSD 3.0 finally ships. It’s been a long epic.

Protocol transitions are hard.

Yeah, I know the experienced software developers reading that are thinking “Well, duh!“. Shut up already, I’m venting here. I’ve just spent the better part of two years – actually, if you include design time and false starts it could be closer to five years – designing a new application protocol for my gpsd service daemon, implementing it, getting it deployed, dealing with problems and course-correcting.

For those of you in the cheap seats, an “application protocol” is a kind of language that a program uses to communicate with other programs. Normally humans never see these, but there’s one big example that non-geeks have often seen bits of. HTML, the Web’s markup language, is an application protocol. Designing these is not easy. There are difficult issues and tradeoffs around flexibility, economy, expressiveness, and extensibility for uses we haven’t imagined yet.

When you have a whole bunch of programs written by different people communicating with a particular application protocol, changing that entire ecology to use a different one is not easy. A good analogy in the physical world is the difficulty of changing an entire country’s railroad gauge. The long-term benefits may be huge, but the short-term cost in capital and service disruption is daunting.

Continue reading

Jun 18

World Without Web

Technological change has a tendency to look inevitable in retrospect – “It steam-engines when it’s steam-engine time.” Likely this is true in many cases, but I often think we underestimate the alarming degree of contingency lurking behind ‘inevitable’ developments. To illustrate this point, I’m going to sketch an all-too-plausible alternate history in which the World Wide Web never happened.

Continue reading

May 31

Configuration files and switches considered harmful

Someone on the gpsd-users list asked:

I was just wondering why gpsd doesn’t have a configuration file in /etc/gpsd.conf, like most other Unix/Linux software?

Because configuration files are evil, and not to be countenanced unless they become an absolutely necessary evil. Which in gpsd’s case is not yet, and I sincerely hope not ever.

Continue reading

Apr 20

Broadening my Deepwater Horizons

I’ve gotten used to being cited in computer science and software engineering papers over the last decade, but here’s a new one. Today I read a draft in which I and the GPSD project get cited a bunch of times and it’s – er – not about open source. It’s about Marine AIS in disaster management. Broadening my deepwater horizons, as it were.

Continue reading

Apr 15

rsnapshot: you’re doing it right!

Some years back I wrote a book titled The Art of Unix Programming. My goal in that book was to convey the Zen of Unix to today’s generations of eager young Linux and *BSD programmers. In the spirit of that book, I feel impelled to point out out a program I’ve recently learned as a striking, near-perfect example of Unix style in the modern day. rsnapshot, you’re doing it right!

Continue reading

Apr 10

Analysis of scaling problems in build systems

My post SCons is full of win today triggered some interesting feedback on scaling problems in SCons. In response to anecdotal assertions that SCons is unusably slow on large projects, I argued that build systems in general must scale poorly if they are to enforce correctness. Subsequently, I received a pointer to a very well executed empirical study of SCons performance to which I replied in the same fashion.

In this post, I intend to conduct a more detailed analysis of algorithmic requirements and complexity in an idealized build system, and demonstrate the implied scaling laws more rigorously. I will also investigate tradeoffs between correctness and performance using the same explanatory framework.

Continue reading

Mar 25

Bookend consistency

I’ve been thinking recently about writing a shared-memory export for gpsd. The JSON-over-sockets client interface we have is very powerful and flexible, but more than is needed when network access to the server is not required. For embedded deployments, in particular – it would be useful to have a lower-overhead way of shipping results to clients.

Consequently, I’ve been thinking about coherence techniques for shared memory. In this particular case, we have one writer (gpsd) and multiple readers (the application clients). Updates to the shared-memory segment are long enough that writes aren’t guaranteed atomicity. It is permissible for a client to miss an update if it’s not inspecting the segment frequently enough, but required that after a read from the segment the client can always tell when it has a coherent update (as opposed to having read the segment while a write is in progress).

The obvious way to ensure update coherence would be with a semaphore. But a technique that is non-blocking and wait-free would be preferable. I have invented a method I call “bookend consistency”. I present it here for public critique, also because I’m curious whether any of my commenters can identify it with a known, published algorithm. It was inspired by a vague, distant memory of pioneering work by Butler Lampson on lock-free algorithms.

Continue reading

Mar 17

The bug that didn’t bite in the night-time: an anti-disaster story

A very curious thing happened with GPSD this week. In fact it’s so odd I’m still having trouble believing it. In software engineering we often have trouble getting seemingly simple things to work reliably. How does one react when an incredibly complex, fragile piece of bit-twiddling code works – perfectly – after six years without real-world testing, during which the surrounding architecture underwent such massive changes that any rational person would have expected the feature to bit-rot into garbage?

No, really, this one is weird. Let me unfold to you the strange tale of The RTCM2 Analyzer That Shouldn’t Have Worked. Really. At All.

Continue reading

Jan 24

The smartphone wars: Samsung folds under pressure

Some months ago I wrote (in Flattening the Smartphone Market) about the real significance of the Android 2.2 announcement. That was the moment that Google made clear that it intended to take control of the smartphone feature list from the cell carriers. Subsequently, carrier-loaded crapware and suppression of features like hotspot and tethering have been in decline under market pressure. The release of the T-Mobile G-2 and the Samsung Galaxy S (marketed as “the pure Google experience”) have been indicators of this trend.

I should have added that 2.2 takes control of the smartphone feature list away from handset vendors as well. A leak by someone claiming to be a T-mobile employee in the know alleged that Samsung has been dragging its feet on 2.2 upgrades for the Samsung Vibrant, hoping customers will upgrade to the Vibrant 4G in order to get the 2.2 that ships with it. Now comes word that Samsung has folded under pressure from the maneuver and announced an OTA update schedule for 2.2 on the Vibrant.

Continue reading

Jan 22

Embracing the suck

This is a followup to The Rollover of Doom: a Trap for Good Programmers. That post ended “This problem is a Chinese finger-trap for careful and conscientious programmers. The better you are, the worse this problem is likely to hurt your brain. Embrace the suck.”

That last phrase is a take on a military objurgation which translates as “The situation is bad. Deal with it.” Well, my friends, I am about to tell you how bad the GPS rollover situation really is.

Continue reading

Jan 15

The Rollover of Doom: a Trap for Good Programmers

GPS, the Global positioning System, was designed in the 1970s under hardware-cost constraints that would seem ridiculous today. This makes interpreting the data it sends into a black art, and produces some really painful edge cases.

There’s one edge case in particular that I’ve come to think of as the Rollover of Doom. This morning I came up with an evil, clever hack for getting around it. I call it clever because you have to think your way out of a conceptual box to see it. As to why it’s evil…well, you’ll see. If you can figure it out.

Continue reading

Jan 07

Plug and Pray in GPS-land

Welcome, ladies and gentlemen, to another darkly humorous tale of the seamy side of GPS interfacing. GPSD working with USB GPS mice has, when properly installed, lovely plug-and-play self-configuring behavior. That is, you plug a USB GPS into a USB port, the hotplug system notifies the gpsd daemon that the GPS is available, the daemon records this fact…and subsequently when you start up any GPSD client application It Just Works. Well, usually. There’s a dangerous weakness in the machinery, and yesterday it came around and bit us in the ass.

Continue reading

Dec 18

NMEA 2000 and the Obverse of Open Source

In discussion of the GPSD project, a commenter suggested that its role might be going away in part because the NMEA 0183 protocol historically used in GPS sensors is being replaced by NMEA2000. So far, this is not true, and the reasons it’s not true are worth a look because they illustrate a sort of flip side of the economic and technological tends driving the adoption of open source and open protocols in the wider technology market.

Continue reading

Nov 25

If RCS can stand it, why can’t your system?

I’ve written software for a lot of different reasons besides pure utility in the past. Sometimes I’ve been making an aesthetic statement, sometimes I’ve hacked to perpetuate a tribal in-joke, and at least once I have written a substantial piece of code exactly because the domain experts solemnly swore that job was impossible to automate (wrong, bwahahaha).

Here’s a new one. Today I released a program that is ugly and only marginally useful, but specifically designed to shame other hackers into doing the right thing.

Continue reading