I'm a huge fan of interactive programming (see: JavaScript,
Java, Lisp, Clojure). That is, modifying and
extending a program while it's running. For certain kinds of non-batch
applications, it takes much of the tedium out of testing and tweaking
during development. Until last week I didn't know how to apply
interactive programming to C. How does one go about redefining
functions in a running C program?
Last week in Handmade Hero (days 21-25), Casey Muratori added
interactive programming to the game engine. This is especially useful
in game development, where the developer might want to tweak, say, a
boss fight without having to restart the entire game after each tweak.
Now that I've seen it done, it seems so obvious. The secret is to
build almost the entire application as a shared library.
This puts a serious constraint on the design of the program: it
cannot keep any state in global or static variables, though this
should be avoided anyway. Global state will be lost each
time the shared library is reloaded. In some situations, this can also
restrict use of the C standard library, including functions like
malloc(), depending on how these functions are implemented or
linked. For example, if the C standard library is statically linked,
functions with global state may introduce global state into the shared
library. It's difficult to know what's safe to use. This works fine in
Handmade Hero because the core game, the part loaded as a shared
library, makes no use of external libraries, including the standard
library.
Additionally, the shared library must be careful with its use of
function pointers. The functions being pointed at will no longer exist
after a reload. This is a real issue when combining interactive
programming with object oriented C.
An example with the Game of Life
To demonstrate how this works, let's go through an example. I wrote a
simple ncurses Game of Life demo that's easy to modify. You can get
the entire source here if you'd like to play around with it yourself
on a Unix-like system.
In a terminal run make then ./main. Press r randomize and q
to quit.
Edit game.c to change the Game of Life rules, add colors, etc.
In a second terminal run make. Your changes will be reflected
immediately in the original program!
As of this writing, Handmade Hero is being written on Windows, so
Casey is using a DLL and the Win32 API, but the same technique can be
applied on Linux, or any other Unix-like system, using libdl. That's
what I'll be using here.
The program will be broken into two parts: the Game of Life shared
library ("game") and a wrapper ("main") whose job is only to load the
shared library, reload it when it updates, and call it at a regular
interval. The wrapper is agnostic about the operation of the "game"
portion, so it could be re-used almost untouched in another project.
To avoid maintaining a whole bunch of function pointer assignments in
several places, the API to the "game" is enclosed in a struct. This
also eliminates warnings from the C compiler about mixing data and
function pointers. The layout and contents of the game_state
struct is private to the game itself. The wrapper will only handle a
pointer to this struct.
In the demo the API is made of 5 functions. The first 4 are primarily
concerned with loading and unloading.
init(): Allocate and return a state to be passed to every other
API call. This will be called once when the program starts and never
again, even after reloading. If we were concerned about using
malloc() in the shared library, the wrapper would be responsible
for performing the actual memory allocation.
finalize(): The opposite of init(), to free all resources held
by the game state.
reload(): Called immediately after the library is reloaded. This
is the chance to sneak in some additional initialization in the
running program. Normally this function will be empty. It's only
used temporarily during development.
unload(): Called just before the library is unloaded, before a new
version is loaded. This is a chance to prepare the state for use by
the next version of the library. This can be used to update structs
and such, if you wanted to be really careful. This would also
normally be empty.
step(): Called at a regular interval to run the game. A real game
will likely have a few more functions like this.
The library will provide a filled out API struct as a global variable,
GAME_API. This is the only exported symbol in the entire shared
library! All functions will be declared static, including the ones
referenced by the structure.
The wrapper is focused on calling dlopen(), dlsym(), and
dlclose() in the right order at the right time. The game will be
compiled to the file libgame.so, so that's what will be loaded. It's
written in the source with a ./ to force the name to be used as a
filename. The wrapper keeps track of everything in a game struct.
The handle is the value returned by dlopen(). The id is the
inode of the shared library, as returned by stat(). The rest is
defined above. Why the inode? We could use a timestamp instead, but
that's indirect. What we really care about is if the shared object
file is actually a different file than the one that was loaded. The
file will never be updated in place, it will be replaced by the
compiler/linker, so the timestamp isn't what's important.
Using the inode is a much simpler situation than in Handmade Hero. Due
to Windows' broken file locking behavior, the game DLL can't be
replaced while it's being used. To work around this limitation, the
build system and the loader have to rely on randomly-generated
filenames.
voidgame_load(structgame*game)
The purpose of the game_load() function is to load the game API into
a game struct, but only if either it hasn't been loaded yet or if
it's been updated. Since it has several independent failure
conditions, let's examine it in parts.
First, Use stat() to determine if the library's inode is different
than the one that's already loaded. The id field will be 0
initially, so as long as stat() succeeds, this will load the
library the first time.
If a library is already loaded, unload it first, being sure to call
unload() to inform the library that it's being updated. It's
critically important that dlclose() happens before dlopen(). On
my system, dlopen() looks only at the string it's given, not the
file behind it. Even though the file has been replaced on the
filesystem, dlopen() will see that the string matches a library
already opened and return a pointer to the old library. (Is this a
bug?) The handles are reference counted internally by libdl.
void*handle=dlopen(GAME_LIBRARY,RTLD_NOW);
Finally load the game library. There's a race condition here that
cannot be helped due to limitations of dlopen(). The library may
have been updated again since the call to stat(). Since we can't
ask dlopen() about the inode of the library it opened, we can't
know. Since this is only used during development, not in production,
it's not a big deal.
if(handle){game->handle=handle;game->id=attr.st_ino;/* ... more below ... */}else{game->handle=NULL;game->id=0;}
If dlopen() fails, it will return NULL. In the case of ELF, this
will happen if the compiler/linker is still in the process of writing
out the shared library. Since the unload was already done, this means
no game will be loaded when game_load returns. The user of the
struct needs to be prepared for this eventuality. It will need to try
loading again later (i.e. a few milliseconds). It may be worth filling
the API with stub functions when no library is loaded.
When the library loads without error, look up the GAME_API struct
that was mentioned before and copy it into the local struct. Copying
rather than using the pointer avoids one more layer of redirection
when making function calls. The game state is initialized if it hasn't
been already, and the reload() function is called to inform the game
it's just been reloaded.
If looking up the GAME_API fails, close the handle and consider it
a failure.
The main loop calls game_load() each time around. And that's it!
Now that I have this technique in by toolbelt, it has me itching to
develop a proper, full game in C with OpenGL and all, perhaps in
another Ludum Dare. The ability to develop interactively is very
appealing.
This past weekend I participated in Ludum Dare #31. Before the
theme was even announced, due to recent fascination I wanted
to make an old school DOS game. DOSBox would be the target platform
since it's the most practical way to run DOS applications anymore,
despite modern x86 CPUs still being fully backwards compatible all the
way back to the 16-bit 8086.
I successfully created and submitted a DOS game called DOS
Defender. It's a 32-bit 80386 real mode DOS COM program. All
assets are embedded in the executable and there are no external
dependencies, so the entire game is packed into that 10kB binary.
You'll need a joystick/gamepad in order to play. I included mouse
support in the Ludum Dare release in order to make it easier to
review, but this was removed because it doesn't work well.
The most technically interesting part is that I didn't need any
DOS development tools to create this! I only used my every day Linux
C compiler (gcc). It's not actually possible to build DOS Defender
in DOS. Instead, I'm treating DOS as an embedded platform, which is
the only form in which DOS still exists today. Along with
DOSBox and DOSEMU, this is a pretty comfortable toolchain.
If all you care about is how to do this yourself, skip to the
"Tricking GCC" section, where we'll write a "Hello, World" DOS COM
program with Linux's GCC.
Finding the right tools
I didn't have GCC in mind when I started this project. What really
triggered all of this was that I had noticed Debian's bcc
package, Bruce's C Compiler, that builds 16-bit 8086 binaries. It's
kept around for compiling x86 bootloaders and such, but it can also be
used to compile DOS COM files, which was the part that interested me.
For some background: the Intel 8086 was a 16-bit microprocessor
released in 1978. It had none of the fancy features of today's CPU: no
memory protection, no floating point instructions, and only up to 1MB
of RAM addressable. All modern x86 desktops and laptops can still
pretend to be a 40-year-old 16-bit 8086 microprocessor, with the same
limited addressing and all. That's some serious backwards
compatibility. This feature is called real mode. It's the mode in
which all x86 computers boot. Modern operating systems switch to
protected mode as soon as possible, which provides virtual
addressing and safe multi-tasking. DOS is not one of these operating
systems.
Unfortunately, bcc is not an ANSI C compiler. It supports a subset of
K&R C, along with inline x86 assembly. Unlike other 8086 C compilers,
it has no notion of "far" or "long" pointers, so inline assembly is
required to access other memory segments (VGA, clock, etc.).
Side note: the remnants of these 8086 "long pointers" still exists
today in the Win32 API: LPSTR, LPWORD, LPDWORD, etc. The inline
assembly isn't anywhere near as nice as GCC's inline assembly. The
assembly code has to manually load variables from the stack so, since
bcc supports two different calling conventions, the assembly ends up
being hard-coded to one calling convention or the other.
Given all its limitations, I went looking for alternatives.
DJGPP
DJGPP is the DOS port of GCC. It's a very impressive project,
bringing almost all of POSIX to DOS. The DOS ports of many programs
are built with DJGPP. In order to achieve this, it only produces
32-bit protected mode programs. If a protected mode program needs to
manipulate hardware (i.e. VGA), it must make requests to a DOS
Protected Mode Interface (DPMI) service. If I used DJGPP, I
couldn't make a single, standalone binary as I had wanted, since I'd
need to include a DPMI server. There's also a performance penalty for
making DPMI requests.
Getting a DJGPP toolchain working can be difficult, to put it kindly.
Fortunately I found a useful project, build-djgpp, that makes
it easy, at least on Linux.
Either there's a serious bug or the official DJGPP binaries have
become infected again, because in my testing I kept getting
the "Not COFF: check for viruses" error message when running my
programs in DOSBox. To double check that it's not an infection on my
own machine, I set up a DJGPP toolchain on my Raspberry Pi, to act as
a clean room. It's impossible for this ARM-based device to get
infected with an x86 virus. It still had the same problem, and all the
binary hashes matched up between the machines, so it's not my fault.
So given the DPMI issue and the above, I moved on.
Tricking GCC
What I finally settled on is a neat hack that involves "tricking" GCC
into producing real mode DOS COM files, so long as it can target 80386
(as is usually the case). The 80386 was released in 1985 and was the
first 32-bit x86 microprocessor. GCC still targets this instruction
set today, even in the x86_64 toolchain. Unfortunately, GCC cannot
actually produce 16-bit code, so my main goal of targeting 8086 would
not be achievable. This doesn't matter, though, since DOSBox, my
intended platform, is an 80386 emulator.
In theory this should even work unchanged with MinGW, but there's a
long-standing MinGW bug that prevents it from working right ("cannot
perform PE operations on non PE output file"). It's still do-able, and
I did it myself, but you'll need to drop the OUTPUT_FORMAT directive
and add an extra objdump step.
Hello World in DOS
To demonstrate how to do all this, let's make a DOS "Hello, World" COM
program using GCC on Linux.
There's a significant burden with this technique: there will be no
standard library. It's basically like writing an operating system
from scratch, except for the few services DOS provides. This means no
printf() or anything of the sort. Instead we'll ask DOS to print a
string to the terminal. Making a request to DOS means firing an
interrupt, which means inline assembly!
DOS has nine interrupts: 0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26,
0x27, 0x2F. The big one, and the one we're interested in, is 0x21,
function 0x09 (print string). Between DOS and BIOS, there are
thousands of functions called this way. I'm not going to try
to explain x86 assembly, but in short the function number is stuffed
into register ah and interrupt 0x21 is fired. Function 0x09 also
takes an argument, the pointer to the string to be printed, which is
passed in registers dx and ds.
Here's the GCC inline assembly print() function. Strings passed to
this function must be terminated with a $. Why? Because DOS.
staticvoidprint(char*string){asmvolatile("mov $0x09, %%ah\n""int $0x21\n":/* no output */:"d"(string):"ah");}
The assembly is declared volatile because it has a side effect
(printing the string). To GCC, the assembly is an opaque hunk, and the
optimizer relies in the output/input/clobber constraints (the last
three lines). For DOS programs like this, all inline assembly will
have side effects. This is because it's not being written for
optimization but to access hardware and DOS, things not accessible to
plain C.
Care must also be taken by the caller, because GCC doesn't know that
the memory pointed to by string is ever read. It's likely the array
that backs the string needs to be declared volatile too. This is all
foreshadowing into what's to come: doing anything in this environment
is an endless struggle against the optimizer. Not all of these battles
can be won.
Now for the main function. The name of this function shouldn't matter,
but I'm avoiding calling it main() since MinGW has a funny ideas
about mangling this particular symbol, even when it's asked not to.
COM files are limited to 65,279 bytes in side. This is because an x86
memory segment is 64kB and COM files are simply loaded by DOS to
0x0100 in the segment and executed. There are no headers, it's just a
raw binary. Since a COM program can never be of any significant size,
and no real linking needs to occur (freestanding), the entire thing
will be compiled as one translation unit. It will be one call to GCC
with a bunch of options.
Since no standard libraries are in use, the only difference between
gnu99 and c99 is that trigraphs are disabled (as they should be) and
inline assembly can be written as asm instead of __asm__. It's a
no brainer. This project will be so closely tied to GCC that I don't
care about using GCC extensions anyway.
I'm using -Os to keep the compiled output as small as possible. It
will also make the program run faster. This is important when
targeting DOSBox because, by default, it will deliberately run as slow
as a machine from the 1980's. I want to be able to fit in that
constraint. If the optimizer is causing problems, you may need to
temporarily make this -O0 to determine if the problem is your fault
or the optimizer's fault.
You see, the optimizer doesn't understand that the program will be
running in real mode, and under its addressing constraints. It will
perform all sorts of invalid optimizations that break your perfectly
valid programs. It's not a GCC bug since we're doing crazy stuff
here. I had to rework my code a number of times to stop the optimizer
from breaking my program. For example, I had to avoid returning
complex structs from functions because they'd sometimes be filled with
garbage. The real danger here is that a future version of GCC will be
more clever and will break more stuff. In this battle, volatile is
your friend.
Th next option is -nostdlib, since there are no valid libraries for
us to link against, even statically.
The options -m32 -march=i386 set the compiler to produce 80386 code.
If I was writing a bootloader for a modern computer, targeting 80686
would be fine, too, but DOSBox is 80386.
The -ffreestanding argument requires that GCC not emit code that
calls built-in standard library helper functions. Sometimes instead of
emitting code to do something, it emits code that calls a built-in
function to do it, especially with math operators. This was one of the
main problems I had with bcc, where this behavior couldn't be
disabled. This is most commonly used in writing bootloaders and
kernels. And now DOS COM files.
Linker Options
The -Wl option is used to pass arguments to the linker (ld). We
need it since we're doing all this in one call to GCC.
-Wl,--nmagic,--script=com.ld
The --nmagic turns off page alignment of sections. One, we don't
need this. Two, that would waste precious space. In my tests it
doesn't appear to be necessary, but I'm including it just in case.
The --script option tells the linker that we want to use a custom
linker script. This allows us to precisely lay out the sections
(text, data, bss, rodata) of our program. Here's the com.ld
script.
The OUTPUT_FORMAT(binary) says not to put this into an ELF (or PE,
etc.) file. The linker should just dump the raw code. A COM file is
just raw code, so this means the linker will produce a COM file!
I had said that COM files are loaded to 0x0100. The fourth line
offsets the binary to this location. The first byte of the COM file
will still be the first byte of code, but it will be designed to run
from that offset in memory.
What follows is all the sections, text (program), data (static
data), bss (zero-initialized data), rodata (strings). Finally I
mark the end of the binary with the symbol _heap. This will come in
handy later for writing sbrk(), after we're done with "Hello,
World." I've asked for the _heap position to be 4-byte aligned.
We're almost there.
Program Startup
The linker is usually aware of our entry point (main) and sets that
up for us. But since we asked for "binary" output, we're on our own.
If the print() function is emitted first, our program's execution
will begin with executing that function, which is invalid. Our program
needs a little header stanza to get things started.
The linker script has a STARTUP option for handling this, but to
keep it simple we'll put that right in the program. This is usually
called crt0.o or Boot.o, in case those names every come up in your
own reading. This inline assembly must be the very first thing in
our code, before any includes and such. DOS will so most of the setup
for us, we really just have to jump to the entry point.
The .code16gcc tells the assembler that we're going to be running in
real mode, so that it makes the proper adjustment. Despite the name,
this will not make it produce 16-bit code! First it calls dosmain,
the function we wrote above. Then it informs DOS, using function
0x4C (terminate with return code), that we're done, passing the exit
code along in the 1-byte register al (already set by dosmain).
This inline assembly is automatically volatile because it has no
inputs or outputs.
From here if you want fancy graphics, it's just a matter of making an
interrupt and writing to VGA memory. If you want sound you can
perform an interrupt for the PC speaker. I haven't sorted out how to
call Sound Blaster yet. It was from this point that I grew DOS
Defender.
Memory Allocation
To cover one more thing, remember that _heap symbol? We can use it
to implement sbrk() for dynamic memory allocation within the main
program segment. This is real mode, and there's no virtual memory, so
we're free to write to any memory we can address at any time. Some of
this is reserved (i.e. low and high memory) for hardware. So using
sbrk() specifically isn't really necessary, but it's interesting
to implement ourselves.
As is normal on x86, your text and segments are at a low address
(0x0100 in this case) and the stack is at a high address (around
0xffff in this case). On Unix-like systems, the memory returned by
malloc() comes from two places: sbrk() and mmap(). What sbrk()
does is allocates memory just above the text/data segments, growing
"up" towards the stack. Each call to sbrk() will grow this space (or
leave it exactly the same). That memory would then managed by
malloc() and friends.
Here's how we can get sbrk() in a COM program. Notice I have to
define my own size_t, since we don't have a standard library.
It just sets a pointer to _heap and grows it as needed. A slightly
smarter sbrk() would be careful about alignment as well.
In the making of DOS Defender an interesting thing happened. I was
(incorrectly) counting on the memory return by my sbrk() being
zeroed. This was the case the first time the game ran. However, DOS
doesn't zero this memory between programs. When I would run my game
again, it would pick right up where it left off, because the same
data structures with the same contents were loaded back into place. A
pretty cool accident! It's part of what makes this a fun embedded
platform.
When I was a kid I spent some time playing a top-down, 2D,
puzzle/action, 1993, MS-DOS game called God of Thunder. It
came on a shareware CD, now long lost, called Games People Play. A
couple decades later I was recently reminded of the game and decided
to dig it up and play it again. It's not quite as exciting
as I remember it -- nostalgia really warps perception -- but it's
still an interesting game nonetheless.
That got me thinking about how difficult it might be to modify ("mod")
the game to add my own levels and puzzles. It's a tiny game, so there
aren't many assets to reverse engineer. Unpacked, the game just
barely fits on a 1.44 MB high density floppy disk. That was probably
one of the game's primary design constraints. It also means it's
almost certainly employing some sort of home-brew compression
algorithm in order to fit more content. I find these sorts of things
absolutely interesting and delightful.
You see, back in those old days, compression wasn't really a "solved"
problem like it is today. They had to design and implement their own
algorithms, with varying degrees of success. Today if you
need compression for a project, you just grab zlib. Released
in 1995, it implements the most widely used compression algorithm
today, DEFLATE, with a tidy, in-memory API. zlib is well-tested,
thoroughly optimized, and sits in a nearly-perfect sweet spot between
compression ratio and performance. There's even an embeddable
version. Since spinning platters are so slow compared to CPUs,
compression is likely to speed up an application simply because fewer
bytes need to go to and from the disk. Today it's less about saving
storage space and more about reducing input/output demands.
Fortunately for me, someone has already reversed engineered
most of the God of Thunder assets. It uses its own flavor of
Lempel-Ziv-Storer-Szymanski (LZSS), which itself is derived
from LZ77, one of the algorithms used in DEFLATE. The original LZSS
paper focuses purely on the math, describing the algorithm in terms of
symbols with no concern for how it's actually serialized into bits.
Those specific details were decided by the game's developers, and
that's what I'll be describing below.
As an adult I'm finding the God of Thunder asset formats to be more
interesting than the game itself. It's a better puzzle! I really
enjoy studying the file formats of various applications,
especially older ones that didn't have modern standards to build on.
Usually lots of thought and engineering goes into the design these
formats -- and, too often, not enough thought goes into it. The
format's specifics reveal insights into the internal workings of the
application, sometimes exposing unanticipated failure modes. Prying
apart odd, proprietary formats (i.e. "data reduction") is probably my
favorite kind of work at my day job, and it comes up fairly often.
God of Thunder LZSS Definition
An LZSS compression stream is made up of two kinds of chunks: literals
and back references. A literal chunk is passed through to the output
buffer unchanged. A reference chunk is a pair of numbers: a length and
an offset backwards into the output buffer. Only a single bit is
needed for each chunk to identify its type.
To avoid any sort of complicated and slow bit wrangling, the God of
Thunder developers (or whoever inspired them) came up with the smart
idea to stage 8 of these bits up at once as a single byte, a "control"
byte. Since literal chunks are 1 byte and reference chunks are 2
bytes, everything falls onto clean byte boundaries. Every group of 8
chunks is prefixed with one of these control bytes, and so every LZSS
compression stream begins with a control byte. The least significant
bit controls the 1st chunk in the group and the most significant bit
controls the 8th chunk. A 1 denotes a literal and a 0 denotes a
reference.
So, for example, a control byte of 0xff means to pass through
unchanged the next 8 bytes of the compression stream. This would be
the least efficient compression scenario, because the "compressed"
stream is 112.5% (9/8) bigger than the uncompressed stream. Gains come
entirely from the back references.
A back reference is two bytes little endian (this was in MS-DOS
running on x86), the lower 12 bits are the offset and the upper 4 bits
are the length, minus 2. That is, you read the 4 length bits and
add 2. This is because it doesn't make any sense to reference a length
shorter than 2: a literal chunk would be shorter. The offset doesn't
have anything added to it. This was a design mistake since an offset
of 0 doesn't make any sense. It refers to a byte just outside the
output buffer. It should have been stored as the offset minus 1.
A 12-bit offset means up to a 4kB sliding window of output may be
referenced at any time. A 4-bit length, plus two, means up to 17 bytes
may be copied in a single back reference. Compared to other
compression algorithms, this is rather short.
It's important to note that the length is allowed to extend beyond the
output buffer (offset < length). The bytes are, in effect, copied one
at a time into the output and may potentially be reused within the
same operation (like the opposite of memmove). An offset of
1 and a length of 10 means "repeat the last output byte 10 times."
That's the entire format! It's extremely simple but reasonably
effective for the game's assets.
Worst Case and Best Case
In the worst case, such as compressing random data, the compression
stream will be at most 112.5% (9/8) bigger than the uncompressed
stream.
In the best case, such as a long string of zeros, the compressed
stream will be, at minimum, 12.5% (1/8) the size of the decompressed
stream. Think about it this way: imagine every chunk is a reference of
maximum length. That's 1 control byte plus 16 (8 * 2) reference
bytes, for a total of 17 compressed bytes. This emits 17 * 8
decompressed bytes, 17 being the maximum length from 8 chunks.
Conveniently those two 17s cancel, leaving a factor of 8 for the best
case.
LZSS End of Stream
If you're paying really close attention, you may have noticed that
by grouping 8 control bits at a time, the length of the input stream
is, strictly speaking, constrained to certain lengths. What if, during
compression, the input stream stream comes up short of exactly those 8
chunks? As is, there's no way to communicate a premature end to the
stream. There are three ways around this using a small amount of
metadata, each differing in robustness.
Keep track of the size of the decompressed data. When that many
bytes have been emitted, halt. This is how God of Thunder handles
it. A small validation check could be performed here. The output
stream should always end between chunks, not in the middle of a
chunk (i.e. in the middle of copying a back reference). Some of the
bits in the control byte may contain arbitrary data that doesn't
effect the output, which is a concern when hashing compressed data.
My suggestion: require the unused control bits to be 0, which
allows for an additional validation check. The output stream should
never end just short of a literal chunk.
Keep track of the size of the compressed data. Halt when no more
chunks are encountered. A similar, weaker validation check can be
performed here: the input stream should never stop between two
bytes of a reference. It's weaker because it's less sensitive to
corruption, making it harder to detect. The same unused control bit
padding situation applies here.
Use an out-of-band end marker (EOF). This is very similar to
keeping track of the input size (the filesystem is doing it), but
has the weakest validation of all. The stream could be accidentally
truncated at any point between chunks, which is undetectable. This
makes it the least sensitive to corruption.
An LZSS Quine
After spending some time playing around with this format, I thought
about what it would take to make an LZSS quine. That is, find an
LZSS compressed stream that decompresses to itself. It's been done
for DEFLATE, which I imagine is a much harder problem. There are zip
files containing exact copies of themselves, recursively. I'm
pretty confident it's never been done for this exact compression
format, simply because it's so specific to this old MS-DOS game.
I haven't figured it out yet, so you won't find the solution here.
This, dear readers, is my challenge to you! Using the format
described above, craft an LZSS quine. LZSS doesn't have no-op chunks
(i.e. length = 0), which makes this harder than it would otherwise be.
It may not even be possible, which, in that case, your challenge is to
prove it!
So far I've determined that it begins with at least 4kB of 0xff. Why
is this? First, as I mentioned, all compression streams begin with a
control byte. Second, no references can be made until at least one
literal byte has been passed, so the first bit (LSB) of the first byte
is a 1, and the second byte is exactly the same as the first byte. So
the first two bytes are xxxxxx1, with the x being "don't care (yet)."
If the next chunk is a back reference, those first two bytes become
xxxxxx01. It could only reference that one byte (so offset = 1), and
the length would need to be at least two, ensuring at least the first
three bytes of output all have that same pattern. However, on the most
significant byte of the reference chunk, this conflicts with having an
offset of 1 because the 9th bit of the offset is set to 1, forcing the
offset to an invalid 257 bytes. Therefore, the second chunk must be a
literal.
This pattern continues until the first eight chunks are all literals,
which means the quine begins with at least 9 0xff bytes. Going on,
this also means the first back reference is going to be 0xffff
(offset = 4095, length = 17), so the sliding window needs to be filled
enough to make that a offset valid. References would then be used to
"catch up" with the compression stream, then some magic is needed to
finish off the stream.
Object oriented programming, polymorphism in particular, is essential
to nearly any large, complex software system. Without it, decoupling
different system components is difficult. C doesn't come with object
oriented capabilities, so large C programs tend to grow their own out
of C's primitives. This includes huge C projects like the Linux
kernel, BSD kernels, and SQLite.
Starting Simple
Suppose you're writing a function pass_match() that takes an input
stream, an output stream, and a pattern. It works sort of like grep.
It passes to the output each line of input that matches the pattern.
The pattern string contains a shell glob pattern to be handled by
POSIX fnmatch(). Here's what the interface looks like.
Glob patterns are simple enough that pre-compilation, as would be done
for a regular expression, is unnecessary. The bare string is enough.
Some time later the customer wants the program to support regular
expressions in addition to shell-style glob patterns. For efficiency's
sake, regular expressions need to be pre-compiled and so will not be
passed to the function as a string. It will instead be a POSIX
regex_t object. A quick-and-dirty approach might be to
accept both and match whichever one isn't NULL.
Bleh. This is ugly and won't scale well. What happens when more kinds
of filters are needed? It would be much better to accept a single
object that covers both cases, and possibly even another kind of
filter in the future.
A Generalized Filter
One of the most common ways to customize the the behavior of a
function in C is to pass a function pointer. For example, the final
argument to qsort() is a comparator that determines how
objects get sorted.
For pass_match(), this function would accept a string and return a
boolean value deciding if the string should be passed to the output
stream. It gets called once on each line of input.
However, this has one of the same problems as qsort():
the passed function lacks context. It needs a pattern string or
regex_t object to operate on. In other languages these would be
attached to the function as a closure, but C doesn't have closures. It
would need to be smuggled in via a global variable, which is not
good.
Because of the global variable, in practice pass_match() would be
neither reentrant nor thread-safe. We could take a lesson from GNU's
qsort_r() and accept a context to be passed to the filter function.
This simulates a closure.
The provided context pointer would be passed to the filter function as
the second argument, and no global variables are needed. This would
probably be good enough for most purposes and it's about as simple as
possible. The interface to pass_match() would cover any kind of
filter.
But wouldn't it be nice to package the function and context together
as one object?
More Abstraction
How about putting the context on a struct and making an interface out
of that? Here's a tagged union that behaves as one or the other.
There's one function for interacting with this struct:
filter_match(). It checks the type member and calls the correct
function with the correct context.
It still doesn't care how the filter works, so it's good enough to
cover all future cases. It just calls filter_match() on the pointer
it was given. However, the switch and tagged union aren't friendly
to extension. Really, it's outright hostile. We finally have some
degree of polymorphism, but it's crude. It's like building duct tape
into a design. Adding new behavior means adding another switch case.
This is a step backwards. We can do better.
Methods
With the switch we're no longer taking advantage of function
pointers. So what about putting a function pointer on the struct?
The filter itself is passed as the first argument, providing context.
In object oriented languages, that's the implicit this argument. To
avoid requiring the caller to worry about this detail, we'll hide it
in a new switch-free version of filter_match().
For both the original filter struct is the first member. This is
critical. We're going to be using a trick called type punning. The
first member is guaranteed to be positioned at the beginning of the
struct, so a pointer to a struct filter_glob is also a pointer to a
struct filter. Notice any resemblance to inheritance?
Each type, glob and regex, needs its own match method.
I've prefixed them with method_ to indicate their intended usage. I
declared these static because they're completely private. Other
parts of the program will only be accessing them through a function
pointer on the struct. This means we need some constructors in order
to set up those function pointers. (For simplicity, I'm not error
checking.)
Now this is real polymorphism. It's really simple from the user's
perspective. They call the correct constructor and get a filter object
that has the desired behavior. This object can be passed around
trivially, and no other part of the program worries about how it's
implemented. Best of all, since each method is a separate function
rather than a switch case, new kinds of filter subtypes can be
defined independently. Users can create their own filter types that
work just as well as the two "built-in" filters.
Cleaning Up
Oops, the regex filter needs to be cleaned up when it's done, but the
user, by design, won't know how to do it. Let's add a free() method.
The glob constructor should perhaps strdup() its pattern as a
private copy, in which case it would be freed here.
Object Composition
A good rule of thumb is to prefer composition over inheritance. Having
tidy filter objects opens up some interesting possibilities for
composition. Here's an AND filter that composes two arbitrary filter
objects. It only matches when both its subfilters match. It supports
short circuiting, so put the faster, or most discriminating, filter
first in the constructor (user's responsibility).
It can combine a regex filter and a glob filter, or two regex filters,
or two glob filters, or even other AND filters. It doesn't care what
the subfilters are. Also, the free() method here frees its
subfilters. This means that the user doesn't need to keep hold of
every filter created, just the "top" one in the composition.
To make composition filters easier to use, here are two "constant"
filters. These are statically allocated, shared, and are never
actually freed.
The FILTER_NONE filter will generally be used with a (theoretical)
filter_or() and FILTER_ANY will generally be used with the
previously defined filter_and().
Here's a simple program that composes multiple glob filters into a
single filter, one for each program argument.
Notice only one call to filter_free() is needed to clean up the
entire filter.
Multiple Inheritance
As I mentioned before, the filter struct must be the first member of
filter subtype structs in order for type punning to work. If we want
to "inherit" from two different types like this, they would both need
to be in this position: a contradiction.
Fortunately type punning can be generalized such that it the
first-member constraint isn't necessary. This is commonly done through
a container_of() macro. Here's a C99-conforming definition.
Given a pointer to a member of a struct, the container_of() macro
allows us to back out to the containing struct. Suppose the regex
struct was defined differently, so that the regex_t member came
first.
It's a constant, compile-time computed offset, so there should be no
practical performance impact. The filter can now participate freely in
other intrusive data structures, like linked lists and such. It's
analogous to multiple inheritance.
Vtables
Say we want to add a third method, clone(), to the filter API, to
make an independent copy of a filter, one that will need to be
separately freed. It will be like the copy assignment operator in C++.
Each kind of filter will need to define an appropriate "method" for
it. As long as new methods like this are added at the end, this
doesn't break the API, but it does break the ABI regardless.
The filter object is starting to get big. It's got three pointers --
24 bytes on modern systems -- and these pointers are the same between
all instances of the same type. That's a lot of redundancy. Instead,
these pointers could be shared between instances in a common table
called a virtual method table, commonly known as a vtable.
Here's a vtable version of the filter API. The overhead is now only
one pointer regardless of the number of methods in the interface.
Each type creates its own vtable and links to it in the constructor.
Here's the regex filter re-written for the new vtable API and clone
method. This is all the tricks in one basket for a big object oriented
C finale!
This is almost exactly what's going on behind the scenes in C++. When
a method/function is declared virtual, and therefore dispatches
based on the run-time type of its left-most argument, it's listed in
the vtables for classes that implement it. Otherwise it's just a
normal function. This is why functions need to be declared virtual
ahead of time in C++.
In conclusion, it's relatively easy to get the core benefits of object
oriented programming in plain old C. It doesn't require heavy use of
macros, nor do users of these systems need to know that underneath
it's an object system, unless they want to extend it for themselves.
Here's the whole example program once if you're interested in poking:
For more than a decade now, Emacs has come with a built-in Tetris
clone, originally written by XEmacs' Glynn Clements. Just run M-x
tetris any time you want to play. For anyone too busy to waste time
playing Tetris, earlier this year I wrote an autotetris-mode that will
play the Emacs game automatically.
Load the source, autotetris-mode.el and M-x autotetris. It will
start the built-in Tetris but make all the moves itself. It works best
when byte compiled.
At the time I had read an article and was interested in trying
my hand at my own Tetris AI. Like most things Emacs, the built-in
Tetris game is very hackable. It's also pretty simple and easy to
understand. Rather than write my own I chose to build upon this one.
Heuristics
It's not a particularly strong AI. It doesn't pay attention to the
next piece in queue, it doesn't know the game's basic shapes, and it
doesn't try to maximize the score (clearing multiple rows at once).
The goal is to continue running for as long as possible. But since
it's able to get to the point where the game is so fast that the AI is
unable to move pieces fast enough (it's rate limited like a human
player), that means it's good enough.
When a new piece appears at the top of the screen, the AI, in memory,
tries placing it in all possible positions and all possible
orientations. For each of these positions it runs a heuristic on the
resulting game state, summing five metrics. Each metric is scaled by a
hand-tuned weight to adjust its relative priority. Smaller is better,
so the position with the lowest score is selected.
Number of Holes
A hole is any open space that has a solid block above it, even if that
hole is accessible without passing through a solid block. Count these
holes.
Maximum Height
Add the height of the tallest column. Column height includes any holes
in the column. The game ends when a column touches the top of the
screen (or something like that), so this should be kept in check.
Mean Height
Add the mean height of all columns. The higher this is, the closer we
are to losing the game. Since each row will have at least one hole,
this will be a similar measure to the hole count.
Height Disparity
Add the difference between the shortest column height and the tallest
column height. If this number is large it means we're not making
effective use of the playing area. It also discourages the AI from
getting into that annoying situation we all remember: when you
really need a 4x1 piece that never seems to come. Those are the
brief moments when I truly believe the version I'm playing has to be
rigged.
Surface Roughness
Take the root mean square of the column heights. A rougher surface
leaves fewer options when placing pieces. This measure will be similar
to the disparity measurement.
Emacs-specific Details
With a position selected, the AI sends player inputs at a limited rate
to the game itself, moving the piece into place. This is done by
calling tetris-move-right, tetris-move-left, and
tetris-rotate-next, which, in the normal game, are bound to the
arrow keys.
The built-in tetris-mode isn't quite designed for this kind of
extension, so it needs a little bit of help. I defined two pieces of
advice to create hooks. These hooks alert my AI to two specific events
in the game: the game start and a fresh, new piece.
I talked before about the problems with global state.
Fortunately, tetris-mode doesn't store any game state in global
variables. It stores everything in buffer-local variables, which can
be exploited for use in the AI. To perform the "in memory" heuristic
checks, it creates a copy of the game state and manipulates the copy.
The copy is made by way of clone-buffer on the *Tetris* buffer.
The tetris-mode functions all work equally as well on the clone, so I
can use the existing game rules to properly place the next piece in
each available position. The game's own rules take care of clearing
rows and checking for collisions for me. I wrote an
autotetris-save-excursion function to handle the messy details.
(defmacroautotetris-save-excursion(&restbody)"Restore tetris game state after BODY completes."(declare(indentdefun))`(with-current-buffertetris-buffer-name(let((autotetris-saved(clone-buffer"*Tetris-saved*")))(unwind-protect(with-current-bufferautotetris-saved(kill-local-variable'kill-buffer-hook),@body)(kill-bufferautotetris-saved)))))
The kill-buffer-hook variable is also cloned, but I don't want
tetris-mode to respond to the clone being killed, so I clear out the
hook.
That's basically all there is to it! While watching it feels like it's
making dumb mistakes, not placing pieces in optimal positions, but it
recovers well from these situations almost every time, so it must know
what it's doing. Currently it's a better player than me, which is my
rule-of-thumb for calling an AI successful.
Mutable global variables are evil. You've almost certainly heard that
before, but it's worth repeating. It makes programs, and libraries
especially, harder to understand, harder to optimize, more fragile,
more error prone, and less useful. If you're using global state in a
way that's visible to users of your API, and it's not essential to the
domain, you're almost certainly doing something wrong.
In this article I'm going to use two well-established C APIs to
demonstrate why global state is bad for APIs: BSD regular expressions
and POSIX Getopt.
BSD Regular Expressions
The BSD regular expression API dates back to 4.3BSD, released
in 1986. It's just a pair of functions: one compiles the regex, the
other executes it on a string.
It's immediately obvious that there's hidden internal state. Where
else would the resulting compiled regex object be? Also notice there's
no re_free(), or similar, for releasing resources held by the
compiled result. That's because, due to its limited design, it doesn't
hold any. It's entirely in static memory, which means there's some
upper limit on the complexity of the regex given to this API. Suppose
an implementation does use dynamically allocated memory. It seems
this might not matter when only one compiled regex is allowed.
However, this would create warnings in Valgrind and make it harder to
use for bug testing.
This API is not thread-safe. Only one thread can use it at a time.
It's not reentrant. While using a regex, calling another function that
might use a regex means you have to recompile when it returns, just in
case. The global state being entirely hidden, there's no way to tell
if another part of the program used it.
Fixing BSD Regular Expressions
This API has been deprecated for some time now, so hopefully no one's
using it anymore. 15 years after the BSD regex API came out, POSIX
standardized a much better API. It operates on an opaque
regex_t object, on which all state is stored. There's no global
state.
POSIX defines a C API called Getopt for parsing command line
arguments. It's a single function that operates on the argc and
argv values provided to main(). An option string specifies which
options are valid and whether or not they require an argument. Typical
use looks like this,
The b and c options require an argument, indicated by the colons.
When encountered, this argument is passed through a global variable
optarg. There are four external global variables in total.
externchar*optarg;externintoptind,opterr,optopt;
If an invalid option is found, getopt() will automatically print a
locale-specific error message and return ?. The opterr variable
can be used to disable this message and the optopt variable is used
to get the actual invalid option character.
The optind variable keeps track of Getopt's progress. It slides
along argv as each option is processed. In a minimal, strictly
POSIX-compliant Getopt, this is all the global state required.
The argc value in main(), and therefore the same parameter in
getopt(), is completely redundant and serves no real purpose. Just
like the C strings it points to, the argv vector is guaranteed to be
NULL-terminated. At best it's a premature optimization.
Threading an Reentrancy
The most immediate problem is that the entire program can only parse
one argument vector at a time. It's not thread-safe. This leaves out
the possibility of parsing argument vectors in other threads. For
example, if the program is a server that exposes a shell-like
interface to remote users, and multiple threads are used to handle
those requests, it won't be able to take advantage of Getopt.
The second problem is that, even in a single-threaded application, the
program can't pause to parse a different argument vector before
returning. It's not reentrant. For example, suppose one of the
arguments to the program is a string containing more arguments to be
parsed for some subsystem.
# -s Provide a set of sub-options to pass to XXX.
$ myprogram -s "-a -b -c foo"
In theory, the value of optind could be saved and restored. However,
this isn't portable. POSIX doesn't explicitly declare that the entire
state is captured by optind, nor is it required to be.
Implementations are allowed to have internal, hidden global state.
This has implications in resetting Getopt.
Resetting Getopt
In a minimal, strict Getopt, resetting Getopt for parsing another
argument vector is just a matter of setting optind to back to its
original value of 1. However, this idiom isn't portable, and POSIX
provides no portable method for resetting the global parser state.
Real implementations of Getopt go beyond POSIX. Probably the most
popular extra feature is option grouping. Typically, multiple options
can be grouped into a single argument, so long as only the final
option requires an argument.
$ myprogram -adb foo
After processing a, optind cannot be incremented, because it's
still working on the first argument. This means there's another
internal counter for stepping across the group. In glibc this is
called nextchar. Setting optind to 1 will not reset this internal
counter, nor would it be detectable by Getopt if it was already set
to 1. The glibc way to reset Getopt is to set optind to 0, which is
otherwise an invalid value. Some other Getopt implementations follow
this idiom, but it's not entirely portable.
Not only does Getopt have nasty global state, the user has no way to
reliably control it!
Error Printing
I mentioned that Getopt will automatically print an error message
unless disabled with opterr. There's no way to get at this error
message, should you want to redirect it somewhere else. It's more
hidden, internal state. You could write your own message, but you'd
lose out on the automatic locale support.
Fixing Getopt
The way Getopt should have been designed was to accept a context
argument and store all state on that context. Following other POSIX
APIs (pthreads, regex), the context itself would be an opaque object.
In typical use it would have automatic (i.e. stack) duration. The
context would either be zero initialized or a function would be
provided to initialize it. It might look something like this (in the
zero-initialized case).
Instead of optarg and optopt global variables, these values would
be obtained by interrogating the context. The same applies for
optind and the diagnostic message.
Alternatively, instead of getopt_optind() the API could have a
function that continues processing, but returns non-option arguments
instead of options. It would return NULL when no more arguments are
left. This is the API I'd prefer, because it would allow for argument
permutation (allow options to come after non-options, per GNU Getopt)
without actually modifying the argument vector. This common extension
to Getopt could be added cleanly. The real Getopt isn't designed well
for extension.
constchar*getopt_next_arg(getopt_t*ctx);
This API eliminates the global state and, as a result, solves all of
the problems listed above. It's essentially the same API defined by
Popt and my own embeddable Optparse. They're much
better options if the limitations of POSIX-style Getopt are an issue.
The challenge: As quickly as possible, find all occurrences of a
given sequence of digits in the first one billion digits of pi. You
don't have to compute pi yourself for this challenge. For
example, "141592653" appears 4 times: at positions 1, 427,238,911,
570,434,346, and 678,096,434.
To my surprise, this turned out to be harder than I expected. A
straightforward scan with Boyer-Moore-Horspool across the
entire text file is already pretty fast. On modern, COTS hardware it
takes about 6 seconds. Comparing bytes is cheap and it's largely an
I/O-bound problem. This means building fancy indexes tends to make it
slower because it's more I/O demanding.
The challenge was inspired by The Pi-Search Page, which
offers a search on the first 200 million digits. There's also a little
write-up about how their pi search works. I wanted to try to invent my
own solution. I did eventually come up with something that worked,
which can be found here. It's written in plain old C.
You might want to give the challenge a shot on your own before
continuing!
SQLite
The first thing I tried was SQLite. I thought an index (B-tree) over
fixed-length substrings would be efficient. A LIKE condition with a
right-hand wildcard is sargable and would work well with the
index. Here's the schema I tried.
There will be 1 row for each position, i.e. 1 billion rows. Using
INTEGER PRIMARY KEY means position will be used directly for row
IDs, saving some database space.
After the data has been inserted by sliding a window along pi, I
build an index. It's better to build an index after data is in the
database than before.
This takes several hours to complete. When it's done the database is
a whopping 60GB! Remember I said that this is very much an I/O-bound
problem? I wasn't kidding. This doesn't work well at all. Here's the
a search for the example sequence.
You get your answers after about 15 minutes of hammering on the disk.
Sometime later I realized that up to 18-digits sequences could be
encoded into an integer, so that TEXT column could be a much simpler
INTEGER. Unfortunately this doesn't really improve anything. I also
tried this in PostgreSQL but it was even worse. I gave up after 24
hours of waiting on it. These databases are not built for such long,
skinny tables, at least not without beefy hardware.
Offset DB
A couple weeks later I had another idea. A query is just a sequence of
digits, so it can be trivially converted into a unique number. As
before, pick a fixed length for sequences (n) for the index and an
appropriate stride. The database would be one big file. To look up a
sequence, treat that sequence as an offset into the database and seek
into the database file to that offset times the stride. The total size
of the database is 10^n * stride.
In this quick and dirty illustration, n=4 and stride=4 (far too small
for that n).
For example, if the fixed-length for sequences is 6 and the stride is
4,000 bytes, looking up "141592" is just a matter of seeking to byte
141,592 * 4,000 and reading in positions until some sort of
sentinel. The stride must be long enough to store all the positions
for any indexed sequence.
For this purpose, the digits of pi are practically random numbers. The
good news is that it means a fixed stride will work well. Any
particular sequence appears just as often as any other. The chance a
specific n-length sequence begins at a specific position is 1 /
10^n. There are 1 billion positions, so a particular sequence will
have 1e9 / 10^n positions associated with it, which is a good place
to start for picking a stride.
The bad news is that building the index means jumping around the
database essentially at random for each write. This will break any
sort of cache between the program and the hard drive. It's incredibly
slow, even mmap()ed. The workaround is to either do it entirely in RAM
(needs at least 6GB of RAM for 1 billion digits!) or to build it up
over many passes. I didn't try it on an SSD but maybe the random
access is more tolerable there.
Adding an Index
Doing all the work in memory makes it easier to improve the database
format anyway. It can be broken into an index section and a tables
section. Instead of a fixed stride for the data, front-load the
database with a similar index that points to the section (table) of
the database file that holds that sequence's pi positions. Each of the
10^n positions gets a single integer in the index at the front of
the file. Looking up the positions for a sequence means parsing the
sequence as a number, seeking to that offset into the beginning of the
database, reading in another offset integer, and then seeking to that
new offset. Now the database is compact and there are no concerns
about stride.
No sentinel mark is needed either. The tables are concatenated in
order in the table part of the database. To determine where to stop,
take a peek at the next sequence's start offset in the index. Its
table immediately follows, so this doubles as an end offset. For
convenience, one final integer in the index will point just beyond the
end of the database, so the last sequence (99999...) doesn't require
special handling.
Searching Shorter and Longer
If the database built for fixed length sequences, how is a sequence of
a different length searched? The two cases, shorter and longer, are
handled differently.
If the sequence is shorter, fill in the remaining digits, ...000 to
...999, and look up each sequence. For example, if n=6 and we're
searching for "1415", get all the positions for "141500", "141501",
"141502", ..., "141599" and concatenate them. Fortunately the database
already has them stored this way! Look up the offsets for "141500" and
"141600" and grab everything in between. The downside is that the pi
positions are only partially sorted, so they may require sorting
before presenting to the user.
If the sequence is longer, the original digits file will be needed.
Get the table for the subsequence fixed-length prefix, then seek into
the digits file checking each of the pi positions for a full match.
This requires lots of extra seeking, but a long sequence will
naturally have fewer positions to test. For example, if n=7 and we're
looking for "141592653", look up the "1415926" table in the database
and check each of its 106 positions.
With this database searches are only a few milliseconds (though very
much subject to cache misses). Here's my program in action, from the
repository linked above.
$ time ./pipattern 141592653
1: 14159265358979323
427238911: 14159265303126685
570434346: 14159265337906537
678096434: 14159265360713718
real 0m0.004s
user 0m0.000s
sys 0m0.000s
C11, the latest C standard revision, hasn't received anywhere
near the same amount of fanfare as C++11. I'm not sure why this is.
Some of the updates to each language are very similar, such as formal
support for threading and atomic object access. Three years have
passed and some parts of C11 still haven't been implemented by any
compilers or standard libraries yet. Since there's not yet a lot of
discussion online about C11, I'm basing much of this article on my own
understanding of the C11 draft. I may be under-using the
_Atomic type specifier and not paying enough attention to memory
ordering constraints.
Still, this is a good opportunity to break new ground with a
demonstration of C11. I'm going to use the new
stdatomic.h portion of C11 to build a lock-free data
structure. To compile this code you'll need a C compiler and C library
with support for both C11 and the optional stdatomic.h features. As
of this writing, as far as I know only GCC 4.9, released April
2014, supports this. It's in Debian unstable but not in Wheezy.
If you want to take a look before going further, here's the source.
The test code in the repository uses plain old pthreads because C11
threads haven't been implemented by anyone yet.
I was originally going to write this article a couple weeks ago, but I
was having trouble getting it right. Lock-free data structures are
trickier and nastier than I expected, more so than traditional mutex
locks. Getting it right requires very specific help from the hardware,
too, so it won't run just anywhere. I'll discuss all this below. So
sorry for the long article. It's just a lot more complex a topic than
I had anticipated!
Lock-free
A lock-free data structure doesn't require the use of mutex locks.
More generally, it's a data structure that can be accessed from
multiple threads without blocking. This is accomplished through the
use of atomic operations -- transformations that cannot be
interrupted. Lock-free data structures will generally provide better
throughput than mutex locks. And it's usually safer, because there's
no risk of getting stuck on a lock that will never be freed, such as a
deadlock situation. On the other hand there's additional risk of
starvation (livelock), where a thread is unable to make progress.
As a demonstration, I'll build up a lock-free stack, a sequence with
last-in, first-out (LIFO) behavior. Internally it's going to be
implemented as a linked-list, so pushing and popping is O(1) time,
just a matter of consing a new element on the head of the list. It
also means there's only one value to be updated when pushing and
popping: the pointer to the head of the list.
Here's what the API will look like. I'll define lstack_t shortly.
I'm making it an opaque type because its fields should never be
accessed directly. The goal is to completely hide the atomic
semantics from the users of the stack.
Users can push void pointers onto the stack, check the size of the
stack, and pop void pointers back off the stack. Except for
initialization and destruction, these operations are all safe to use
from multiple threads. Two different threads will never receive the
same item when popping. No elements will ever be lost if two threads
attempt to push at the same time. Most importantly a thread will never
block on a lock when accessing the stack.
Notice there's a maximum size declared at initialization time. While
lock-free allocation is possible [PDF], C makes no
guarantees that malloc() is lock-free, so being truly lock-free
means not calling malloc(). An important secondary benefit to
pre-allocating the stack's memory is that this implementation doesn't
require the use of hazard pointers, which would be far more
complicated than the stack itself.
The declared maximum size should actually be the desired maximum size
plus the number of threads accessing the stack. This is because a
thread might remove a node from the stack and before the node can
freed for reuse, another thread attempts a push. This other thread
might not find any free nodes, causing it to give up without the stack
actually being "full."
The int return value of lstack_init() and lstack_push() is for
error codes, returning 0 for success. The only way these can fail is
by running out of memory. This is an issue regardless of being
lock-free: systems can simply run out of memory. In the push case it
means the stack is full.
Structures
Here's the definition for a node in the stack. Neither field needs to
be accessed atomically, so they're not special in any way. In fact,
the fields are never updated while on the stack and visible to
multiple threads, so it's effectively immutable (outside of reuse).
Users never need to touch this structure.
Internally a lstack_t is composed of two stacks: the value stack
(head) and the free node stack (free). These will be handled
identically by the atomic functions, so it's really a matter of
convention which stack is which. All nodes are initially placed on the
free stack and the value stack starts empty. Here's what an internal
stack looks like.
There's still no atomic declaration here because the struct is going
to be handled as an entire unit. The aba field is critically
important for correctness and I'll go over it shortly. It's declared
as a uintptr_t because it needs to be the same size as a pointer.
Now, this is not guaranteed by C11 -- it's only guaranteed to be large
enough to hold any valid void * pointer, so it could be even larger
-- but this will be the case on any system that has the required
hardware support for this lock-free stack. This struct is therefore
the size of two pointers. If that's not true for any reason, this code
will not link. Users will never directly access or handle this struct
either.
Notice the use of the new _Atomic qualifier. Atomic values may have
different size, representation, and alignment requirements in order to
satisfy atomic access. These values should never be accessed directly,
even just for reading (use atomic_load()).
The size field is for convenience to check the number of elements on
the stack. It's accessed separately from the stack nodes themselves,
so it's not safe to read size and use the information to make
assumptions about future accesses (e.g. checking if the stack is empty
before popping off an element). Since there's no way to lock the
lock-free stack, there's otherwise no way to estimate the size of the
stack during concurrent access without completely disassembling it via
lstack_pop().
There's no reason to use volatile here. That's a
separate issue from atomic operations. The C11 stdatomic.h macros
and functions will ensure atomic values are accessed appropriately.
Stack Functions
As stated before, all nodes are initially placed on the internal free
stack. During initialization they're allocated in one solid chunk,
chained together, and pinned on the free pointer. The initial
assignments to atomic values are done through ATOMIC_VAR_INIT, which
deals with memory access ordering concerns. The aba counters don't
actually need to be initialized. Garbage, indeterminate values are
just fine, but not initializing them would probably look like a
mistake.
intlstack_init(lstack_t*lstack,size_tmax_size){lstack->head.aba=ATOMIC_VAR_INIT(0);lstack->head.node=ATOMIC_VAR_INIT(NULL);lstack->size=ATOMIC_VAR_INIT(0);/* Pre-allocate all nodes. */lstack->node_buffer=malloc(max_size*sizeof(structlstack_node));if(lstack->node_buffer==NULL)returnENOMEM;for(size_ti=0;i<max_size-1;i++)lstack->node_buffer[i].next=lstack->node_buffer+i+1;lstack->node_buffer[max_size-1].next=NULL;lstack->free.aba=ATOMIC_VAR_INIT(0);lstack->free.node=ATOMIC_VAR_INIT(lstack->node_buffer);return0;}
The free nodes will not necessarily be used in the same order that
they're placed on the free stack. Several threads may pop off nodes
from the free stack and, as a separate operation, push them onto the
value stack in a different order. Over time with multiple threads
pushing and popping, the nodes are likely to get shuffled around quite
a bit. This is why a linked listed is still necessary even though
allocation is contiguous.
The reverse of lstack_init() is simple, and it's assumed concurrent
access has terminated. The stack is no longer valid, at least not
until lstack_init() is used again. This one is declared inline and
put in the header.
To read an atomic value we need to use atomic_load(). Give it a
pointer to an atomic value, it dereferences the pointer and returns
the value. This is used in another inline function for reading the
size of the stack.
For operating on the two stacks there will be two internal, static
functions, push and pop. These deal directly in nodes, accepting
and returning them, so they're not suitable to expose in the API
(users aren't meant to be aware of nodes). This is the most complex
part of lock-free stacks. Here's pop().
It's centered around the new C11 stdatomic.h function
atomic_compare_exchange_weak(). This is an atomic operation more
generally called compare-and-swap (CAS). On x86 there's an
instruction specifically for this, cmpxchg. Give it a pointer to the
atomic value to be updated (head), a pointer to the value it's
expected to be (orig), and a desired new value (next). If the
expected and actual values match, it's updated to the new value. If
not, it reports a failure and updates the expected value to the latest
value. In the event of a failure we start all over again, which
requires the while loop. This is an optimistic strategy.
The "weak" part means it will sometimes spuriously fail where the
"strong" version would otherwise succeed. In exchange for more
failures, calling the weak version is faster. Use the weak version
when the body of your do ... while loop is fast and the strong
version when it's slow (when trying again is expensive), or if you
don't need a loop at all. You usually want to use weak.
The alternative to CAS is load-link/store-conditional. It's a
stronger primitive that doesn't suffer from the ABA problem described
next, but it's also not available on x86_64. On other platforms, one
or both of atomic_compare_exchange_*() will be implemented using
LL/SC, but we still have to code for the worst case (CAS).
The ABA Problem
The aba field is here to solve the ABA problem by counting
the number of changes that have been made to the stack. It will be
updated atomically alongside the pointer. Reasoning about the ABA
problem is where I got stuck last time writing this article.
Suppose aba didn't exist and it was just a pointer being swapped.
Say we have two threads, A and B.
Thread A copies the current head into orig, enters the loop body
to update next.node to orig.node->next, then gets preempted
before the CAS. The scheduler pauses the thread.
Thread B comes along performs a pop() changing the value pointed
to by head. At this point A's CAS will fail, which is fine. It
would reconstruct a new updated value and try again. While A is
still asleep, B puts the popped node back on the free node stack.
Some time passes with A still paused. The freed node gets re-used
and pushed back on top of the stack, which is likely given that
nodes are allocated FIFO. Now head has its original value again,
but the head->node->next pointer is pointing somewhere completely
new! This is very bad because A's CAS will now succeed despite
next.node having the wrong value.
A wakes up and it's CAS succeeds. At least one stack value has been
lost and at least one node struct was leaked (it will be on neither
stack, nor currently being held by a thread). This is the ABA
problem.
The core problem is that, unlike integral values, pointers have
meaning beyond their intrinsic numeric value. The meaning of a
particular pointer changes when the pointer is reused, making it
suspect when used in CAS. The unfortunate effect is that, by itself,
atomic pointer manipulation is nearly useless. They'll work with
append-only data structures, where pointers are never recycled, but
that's it.
The aba field solves the problem because it's incremented every time
the pointer is updated. Remember that this internal stack struct is
two pointers wide? That's 16 bytes on a 64-bit system. The entire 16
bytes is compared by CAS and they all have to match for it to succeed.
Since B, or other threads, will increment aba at least twice (once
to remove the node, and once to put it back in place), A will never
mistake the recycled pointer for the old one. There's a special
double-width CAS instruction specifically for this purpose,
cmpxchg16. This is generally called DCAS. It's available on most
x86_64 processors. On Linux you can check /proc/cpuinfo for support.
It will be listed as cx16.
If it's not available at compile-time this program won't link. The
function that wraps cmpxchg16 won't be there. You can tell GCC to
assume it's there with the -mcx16 flag. The same rule here applies
to C++11's new std::atomic.
There's still a tiny, tiny possibility of the ABA problem still
cropping up. On 32-bit systems A may get preempted for over 4 billion
(2^32) stack operations, such that the ABA counter wraps around to the
same value. There's nothing we can do about this, but if you witness
this in the wild you need to immediately stop what you're doing and go
buy a lottery ticket. Also avoid any lightning storms on the way to
the store.
Hazard Pointers and Garbage Collection
Another problem in pop() is dereferencing orig.node to access its
next field. By the time we get to it, the node pointed to by
orig.node may have already been removed from the stack and freed. If
the stack was using malloc() and free() for allocations, it may
even have had free() called on it. If so, the dereference would be
undefined behavior -- a segmentation fault, or worse.
There are three ways to deal with this.
Garbage collection. If memory is automatically managed, the node
will never be freed as long as we can access it, so this won't be a
problem. However, if we're interacting with a garbage collector
we're not really lock-free.
Hazard pointers. Each thread keeps track of what nodes it's
currently accessing and other threads aren't allowed to free nodes
on this list. This is messy and complicated.
Never free nodes. This implementation recycles nodes, but they're
never truly freed until lstack_free(). It's always safe to
dereference a node pointer because there's always a node behind it.
It may point to a node that's on the free list or one that was even
recycled since we got the pointer, but the aba field deals with
any of those issues.
Reference counting on the node won't work here because we can't get to
the counter fast enough (atomically). It too would require
dereferencing in order to increment. The reference counter could
potentially be packed alongside the pointer and accessed by a DCAS,
but we're already using those bytes for aba.
It's counter-intuitive, but adding a few microseconds of
sleep after CAS failures would probably increase
throughput. Under high contention, threads wouldn't take turns
clobbering each other as fast as possible. It would be a bit like
exponential backoff.
API Push and Pop
The API push and pop functions are built on these internal atomic
functions.
Push removes a node from the free stack. If the free stack is empty it
reports an out-of-memory error. It assigns the value and pushes it
onto the value stack where it will be visible to other threads.
Finally, the stack size is incremented atomically. This means there's
an instant where the stack size is listed as one shorter than it
actually is. However, since there's no way to access both the stack
size and the stack itself at the same instant, this is fine. The stack
size is really only an estimate.
Remove the top node, subtract the size estimate atomically, put the
node on the free list, and return the pointer. It's really simple with
the primitive push and pop.
SHA1 Demo
The lstack repository linked at the top of the article includes a demo
that searches for patterns in SHA-1 hashes (sort of like Bitcoin
mining). It fires off one worker thread for each core and the results
are all collected into the same lock-free stack. It's not really
exercising the library thoroughly because there are no contended pops,
but I couldn't think of a better example at the time.
The next thing to try would be implementing a C11, bounded, lock-free
queue. It would also be more generally useful than a stack,
particularly for common consumer-producer scenarios.
The C standard library includes a quicksort function called qsort().
It sorts homogeneous arrays of arbitrary type. The interface is exactly
what you'd expect given the constraints of the language.
It takes a pointer to the first element of the array, the number of
members, the size of each member, and a comparator function. The
comparator has to operate on void * pointers because C doesn't have
templates or generics or anything like that. That's two interfaces
where type safety is discarded: the arguments passed to qsort() and
again when it calls the comparator function.
One of the significant flaws of this interface is the lack of context
for the comparator. C doesn't have closures, which in other languages
would cover this situation. If the sort function depends on some
additional data, such as in Graham scan where points are
sorted relative to a selected point, the extra information needs to be
smuggled in through a global variable. This is not reentrant and
wouldn't be safe in a multi-threaded environment. There's a GNU
extension here, qsort_r(), that takes an additional context
argument, allowing for reentrant comparators.
Quicksort has some really nice properties. It's in-place, so no
temporary memory needs to be allocated. If implemented properly it
only consumes O(log n) space, which is the stack growth during
recursion. Memory usage is localized, so it plays well with caching.
That being said, qsort() is also a classic example of an API naming
mistake. Few implementations actually use straight
quicksort. For example, glibc's qsort() is merge sort (in
practice), and the other major libc implementations use a hybrid
approach. Programs using their language's sort function
shouldn't be concerned with how it's implemented. All the matters is
the interface and whether or not it's a stable sort. OpenBSD made the
exact same mistake when they introduced arc4random(),
which no longer uses RC4.
Since quicksort is an unstable sort -- there are multiple possible
results when the array contains equivalent elements -- this means
qsort() is not guaranteed to be stable, even if internally the C
library is using a stable sort like merge sort. The C standard
library has no stable sort function.
Comparator Composability
The unfortunate side effect of unstable sorts is that they hurt
composability. For example, let's say we have a person struct like
this,
structperson{constchar*first,*last;intage;};
Here are a couple of comparators to sort either by name or by age. As
a side note, strcmp() automatically works correctly with UTF-8 so
this program isn't limited to old-fashioned ASCII names.
And since we'll need it later, here's a COUNT_OF macro to get the
length of arrays at compile time. There's a less error prone
version out there, but I'm keeping it simple.
#define COUNT_OF(x) (sizeof(x) / sizeof(0[x]))
Say we want to sort by name, then age. When using a stable sort,
this is accomplished by sorting on each field separately in reverse
order of preference: a composition of individual comparators. Here's
an attempt at using quicksort to sort an array of people by age then
name.
But this doesn't always work. Jane should come before John,
but the original sort was completely lost in the second sort.
Joe Shmoe, 24
John Doe, 30
Jane Doe, 30
Alan Smithee, 42
This could be fixed by defining a new comparator that operates on both
fields at once, compare_age_name(), and performing a single sort.
But what if later you want to sort by name then age? Now you need
compare_name_age(). If a third field was added, there would need to
be 6 (3!) different comparator functions to cover all the
possibilities. If you had 6 fields, you'd need 720 comparators!
Composability has been lost to a combinatorial nightmare.
Pointer Comparison
The GNU libc documentation claims that qsort() can be made
stable by using pointer comparison as a fallback. That is, when
the relevant fields are equivalent, use their array position to
resolve the difference.
If you want the effect of a stable sort, you can get this result by
writing the comparison function so that, lacking other reason
distinguish between two elements, it compares them by their
addresses.
This is not only false, it's dangerous! Because elements may be sorted
in-place, even in glibc, their position will change during the sort.
The comparator will be using their current positions, not the
starting positions. What makes it dangerous is that the comparator
will return different orderings throughout the sort as elements are
moved around the array. This could result in an infinite loop, or
worse.
Making it Stable
The most direct way to work around the unstable sort is to eliminate
any equivalencies. Equivalent elements can be distinguished by adding
an intrusive order field which is set after each sort. The
comparators will fall back on this sort to maintain the original
ordering.
Joe Shmoe, 24
Jane Doe, 30
John Doe, 30
Alan Smithee, 42
Without defining any new comparators I can sort by name then age just
by swapping the calls to qsort(). At the cost of an extra
bookkeeping field, the number of comparator functions needed as fields
are added is O(n) and not O(n!) despite using an unstable sort.
There was an interesting /r/DailyProgrammer challenge this week
to write a program that properly hashes passwords for storage in an
account database. It's a necessary part of any system that needs to
securely authenticate users. Storing user passwords in plain text is
not just bad practice, it's irresponsible. If the database is
compromised, the attacker learns every user's password. Since people
are likely to re-use passwords on different websites, the database
could be used to infiltrate accounts on other sites.
The solution to this problem is to run the password through a one-way
cryptographic hash function before storing it in the database. When
the database is compromised, it's more difficult to work backwards to
recover the passwords. Examples of one-way hash functions are MD5,
SHA-1, and the SHA-2 family. Block ciphers can also be converted into
hash functions (e.g. bcrypt from Blowfish), though it must be done
carefully since block ciphers were generally designed with different
goals in mind.
However, these particular functions (SHA-1 and SHA-2) alone are poor
password hashing functions: they're much too fast! An offline attacker
can mount a rapid brute-force attack on these kinds of hashes. They
also don't include a salt, a unique, non-secret, per-hash value used
as additional hash function input. Without this, an attacker could
prepare the entire attack ahead of time -- a rainbow table. Once the
hashes are obtained, reversing them is just a matter of looking them
up in the table.
Good password hashing needs to be slow and it needs support for salt.
Examples of algorithms well-suited for this purpose are PBKDF2,
bcrypt, and scrypt. These are the functions you'd want to use in a
real application today. Each of these are also more generally key
derivation functions. They can strengthen a relatively short
human-memorable passphrase by running it through a long, slow
procedure before making use of it as an encryption key. An brute-force
attacker would need to perform this slow procedure for each individual
guess.
Alternatively, if you're stuck using a fast hash function anyway, it
could be slowed down by applying the function thousands or even
millions of times recursively to its own output. This is what I did
in order to strengthen my GPG passphrase. However, you're still
left with the problem of applying the salt. The naive approach would
be a plain string concatenation with the password, but this likely to
be vulnerable to a length extension attack. The proper approach
would be to use HMAC.
RC4 Solution
For my solution to the challenge, I wasn't looking for something
strong enough to do key derivation. I just need a slow hash function
that properly handles a salt. Another important goal was to keep the
solution small enough to post as a reddit comment, and I wanted to do
it without using any external crypto libraries. If I'm using a
library, I might as well just include/import/require PBKDF2 and make
it a 2-liner, but that would be boring. I wanted it to be a reasonably
short C program with no external dependencies other than standard
libraries. Not counting the porcelain, the final result weighs in at
115 lines of C, so I think I achieved all my goals.
So what's the smallest, modern cryptographic algorithm I'm aware of?
That would be RC4, my favorite random generator! Unlike
virtually every other cryptographic algorithm, it's easy to commit to
memory and to implement from scratch without any reference
documentation. Similarly, this password hashing function can be
implemented entirely from memory (if you can imagine yourself in some
outlandish sitation where that would be needed).
Unfortunately, RC4 has had a lot of holes punched in it over the
years. The initial output has been proven to be biased, leaking key
material, and there's even good reason to believe it may already be
broken by nation state actors. Despite this, RC4 remains the most
widely used stream cipher today due to its inclusion in TLS. Most
importantly here, almost none of RC4's weaknesses apply to this
situation -- we're only using a few bytes of output -- so it's still a
very strong algorithm. Besides, what I'm developing is a proof of
concept, not something to be used in a real application. It would be
interesting to see how long it takes for someone to break this (maybe
even decades).
Before I dive into the details, I'll link to the source repository. As
of this writing there are C and Elisp implementations of the
algorithm, and they will properly validate each other's hashes. I call
it RC4HASH.
Here are some example hashes for the password "foobar". It's different
each time because each has a unique salt. Notice the repeated byte
12 in the 5th byte position of the hash.
RC4 is a stream cipher, which really just means it's a fancy random
number generator. How can we turn this into a hash function? The
content to be hashed can be fed to the key schedule algorithm in
256-byte chunks, as if it were a key. The key schedule is a cipher
initialization stage that shuffles up the cipher state without
generating output. To put all this in terms of C, here's what the RC4
struct and initialization looks like: a 256-element byte array
initialized with 0-255, and two array indexes.
The key schedule shuffles this state according to a given key.
#define SWAP(a, b) if (a ^ b) {a ^= b; b ^= a; a ^= b;}voidrc4_schedule(structrc4*k,constuint8_t*key,size_tlength){intj=0;for(inti=0;i<256;i++){j=(j+k->S[i]+key[i%length])%256;SWAP(k->S[i],k->S[j]);}}
Notice it doesn't touch the array indexes. It can be called over and
over with different key material to keep shuffling the state. This is
how I'm going to mix the salt into the password. The key schedule will
first be run on the salt, then again on the password.
To produce the hash output, emit the desired number of bytes from the
cipher. Ta da! It's now an RC4-based salted hash function.
Both password and salt are the inputs to hash function. In order to
validate a password against a hash, we need to keep track of the salt.
The easiest way to do this is to concatenate it to the hash itself,
making it part of the hash. Remember, it's not a secret value, so this
is safe. For my solution, I chose to use a 32-bit salt and prepend it
to 20 bytes of generator output, just like an initialization vector
(IV). To validate a user, all we need is a hash and a password
provided by the user attempting to authenticate.
Fixing a Flaw
Right now there's a serious flaw. If you want to find it for yourself,
stop reading here. It will need to get fixed before this hash function
is any good.
It's trivial to find a collision, with is the death knell for any
cryptographic hash function. Certain kinds of passwords will collapse
down to the simplest case.
Notice a pattern? Take a look at the RC4 key schedule function. Using
modular arithmetic, the password wraps around repeating itself over
256 bytes. This means passwords with repeating patterns will mutate
the cipher identically regardless of the number of repeats, so they
result in the same hash. A password "abcabcabc" will be accepted as
"abc".
The fix is to avoid wrapping the password. Instead, the RC4 generator,
seeded only by the salt, is used to pad the password out to 256 bytes
without repeating.
This should also help mix the RC4 state up a bit more before
generating the output. I'm no cryptanalyst, though, so I don't know if
it's worth much.
Slowing It Down
The next problem is that this is way too fast! It shuffles bytes
around for a few microseconds and it's done. So far it also doesn't
address the problems of biases in RC4's initial output. We'll kill two
birds with one stone for this one.
To fix this we'll add an adaptive difficulty factor. It will be a
value that determines how much work will be done to compute the hash.
It's adaptive because the system administrator can adjust it at any
time without affecting previous hashes. To accomplish this, like the
salt, the difficulty factor will be appended to the hash output. All
the required information will come packaged together in the hash.
The difficulty factor comes into play in two areas. First, it
determines how many times the key schedule is run. This is the same
modification CipherSaber-2 uses in order to strengthen RC4's weak
key schedule. However, rather than run it on the order of 20 times,
our hash function will be running it hundreds of thousands of times.
Second, the difficulty will also determine how many initial bytes of
output are discarded before we start generating the hash.
I decided on an unsigned 8-bit value for the difficulty. The number of
key schedules will be 1 shifted left by this number of bits (i.e.
pow(2, difficulty)). This makes the minimum number of key schedules
1, since any less doesn't make sense. The number of bytes skipped is
the same bitshift, minus 1, times 64 ((pow(2, difficulty) - 1) * 64),
the muliplication is so that it can skip large swaths output.
Therefore the implementation so far has a difficulty of zero: one key
schedule round and zero bytes of output skipped.
The dynamic range of the difficulty factor (0-255) puts the the time
needed on a modern computer to compute an RC4HASH between a few
microseconds (0) to the billions of years (255). That should be a more
than sufficient amount of future proofing, especially considering that
we're using RC4, which will likely be broken before the difficulty
factor ever tops out.
I won't show the code to do this since that's how it's implemented in
the final version, so go look at the repository instead. The final
hash is 26 bytes long: a 208-bit hash. The first 4 bytes are the salt
(grabbed from /dev/urandom in my implementations), the byte is the
difficulty factor, and the final 21 bytes are RC4 output.
In the example hashes above, the 12 constant byte is the difficulty
factor. The default difficulty factor is 18 (0x12). I've considered
XORing this with some salt-seeded RC4 output just to make the hash
look nice, but that just seems like arbitrary complexity for no real
gains. With the default difficulty, it takes almost a second for my
computers to compute the hash.
I believe RC4HASH should be quite resistant to GPGPU attacks. RC4 is
software oriented, involving many random array reads and writes rather
than SIMD-style operations. GPUs are really poor at this sort of
thing, so they should take a significant performance hit when running
RC4HASH.
Break My Hash!
For those interested in breaking RC4HASH, here are a couple of hashes
of English language passphrases. Each is about one short sentence in
length ([a-zA-Z !.,]+). I'm not keeping track of the sentences I used,
so the only way to get them will be to break the hash, even for me.
If you can find a string that validates with these hashes, especially
if it's not the original passphrase, you win! I don't have any prizes
in mind right now, but perhaps some Bitcoin would be in order if your
attack is interesting.
