Backpatching

Pattern Patter

Backpatching

June, 1999

Use mostly-sequential output streams by fixing them later.

You're generating a stream of output. Everything is mostly fine, except that you have some information that really belongs at the front of the file or at a few places in the middle.

Forces

Generating an output stream (mostly sequential).
Information occasionally must go in earlier places in the stream.

Resolution

Rather than treating the whole file as random access, use backpatching.

Generate the stream sequentially. When you get to a place where you don't know the value, insert a placeholder value. Keep a list of these "unresolved references".

As processing continues, keep track of the proper value as it becomes known. At the end, close the sequential stream. Sort the tracked values (if necessary) into the order they should have appeared. Re-open the stream for overwriting. (The access won't be random, but rather sequential but non-contiguous.) Move through the list, seek to the position, and overwrite the placeholder value with the true value. Close the stream.

In this way, we've replaced what could have been random access with two sets of sequential access.

Usage

This is a classical assembler technique. When compiling assembler code, you know the values for instructions, and references to already-defined symbols, so write them directly. When you see a forward reference (to an unknown label), store it.
This fits very well when you have a tape-based system (where sequential access is *strongly* favored): you can sort the values while the tape is rewinding.
Compilers often work like this even when random access files are available. Much of the object file can be generated sequentially, but there are often header areas that must be defined once code characteristics are known. (For example, you may have to write the size of the code space into bytes 20 through 23 of the file.)
Protocol formats are often conveniently handled by building the output directly into a buffer, and keeping a list of places to patch.

Note

[Assembler example recalled - any real reference?] A variation in the assembler example: if random access is just as fast as sequential on the second pass: instead of writing a 0 for the unreferenced value, write the address of the previous entry that should have been updated. Then, the in-memory list need only keep track of the last entry in the file (each entry in the file will point to the preceding one).

[Written 3-22-99.]