The most expensive byte in computing

Text in a computer is a run of bytes parked next to each other in memory. We call that a string, and something has to mark where the run ends. Otherwise the machine keeps cheerfully reading until it finds something it regrets. There are two ways to handle this. Both are obvious. Only one of them is why your bank had a difficult decade.

Option one: write the length at the front. Nine characters coming up. Option two: put a marker at the end and read until you trip over it. The marker won. It is a single byte set to zero, called the null terminator, and everything you own is standing on it.

C is the language most of the world's foundations are written in, and it gets the blame for this. C is innocent, or at least only an accessory. The switch happened one language earlier. Ken Thompson took BCPL and stripped it down, and he called the result B. BCPL was the Basic Combined Programming Language, written by Martin Richards at Cambridge in 1967. C is the language after B. Bell Labs, the research arm of the American telephone monopoly and probably the most productive building in the history of computing, was not spending its creative energy on names.

BCPL kept the length in the first byte. Option one was right there in the family, already working. Thompson kept the shape of the language and threw away the one part of it this article is about.

That ceiling is the good half of the argument. A length held in one byte means a string can be 255 characters long and not one more. That holds in every program, for any purpose, and it is completely fine right up until somebody writes a sentence.

Ritchie created C and co-created Unix, so he gets the benefit of the doubt on most things. He says ducking that ceiling was the point and that in his experience keeping a count around was more hassle than a terminator. The assembler for the PDP-11, the fridge-sized minicomputer Unix was built on, already had a directive that laid down text with a zero on the end. An assembler is the thin layer above raw machine code and a directive is a shortcut it offers you, so this was not merely possible, it was the house style of the hardware. The grain of the wood ran that way and he went with it, which is what any reasonable person does on a Tuesday.

It was a trade. Lose instant length, gain unlimited length, on a machine with almost no memory. Back then everybody who could reach your program was in the room with you and would have just asked.

Unfortunately the trade came with a rider nobody read.

One bit of vocabulary and then the fun starts. A buffer is a block of memory a program books in advance, before it knows what is going into it, rather like reserving a table for six and hoping.

Because the end of the text is a fact about the text rather than about the buffer it lives in, nothing in the system knows how big the buffer was. A human has to remember that separately, every single time anything is copied anywhere, forever. And humans, famously, remember things every single time.

When they do not, the copy sails past the end of the buffer and keeps writing into whatever was parked next to it. Congratulations, you have invented the buffer overflow. For about thirty years it was the single most popular method of breaking into software, and it is more a consequence of geography than a bug in C. Table booked for six, party of nine hundred, and the extra guests are now in the kitchen operating the till.

There is a nastier variant. Sneak a zero byte into the middle of a string and everything after it vanishes for anything reading up to the terminator. One half of your system sees the full name and the other half sees the first four letters. Both halves work as designed, and somebody is logged in as the administrator.

In 2011 Poul-Henning Kamp wrote the whole thing up in ACM Queue, which is the Association for Computing Machinery's own magazine and therefore not somebody's Medium post, under the title “The Most Expensive One-byte Mistake”. That is a headline you get to write once in a career.

Kamp is a Danish engineer who wrote Varnish, a cache whose entire job is flinging other people's text between buffers at speed. He has been mopping this floor for decades.

Then he went looking for the decision. The memo where somebody put length prefix in one column and terminator in the other, and picked.

He reports finding nothing. No paper trail, and no evidence it was ever a conscious decision at all. The most expensive byte in the history of computing has no receipt.

Which is honestly the moral. The moral is not that C is bad. This only became a catastrophe because it was reasonable. A sensible man made a sound local call. Then forty years of operating systems, network stacks, file formats and protocols were stacked on top of it, and somewhere in that pile the cost stopped being his and started being everybody's.

All the modern languages carry their lengths properly. They then sit on a runtime, the layer under your language that does the actual talking to the machine, and almost every one of those is written in C. Which is a bit like fitting a very good lock to a tent.