Catching memory errors on the Z-machine

Technical Development Interpreters
1

The Z machine creates a pretty standard 16 bit address space and folks have already done things like implement general purpose memory allocators within the dynamic memory.

Array overruns are a common source of programming bugs - the standard even mentions things like the read opcode should abort if requested to read too few characters or write out too few parse items since that’s likely a memory bug.

Off the top of my head, any interpreter running on a modern desktop could implement some pretty simple but robust memory checking as follows:

  • Allocate a shadow array of 64k uint16_t’s.
  • Each entry of the shadow array contains the size of the remaining space in that segment

What’s a segment? Well, the header is a segment of 64 bytes at address zero. The dictionary segment contains all of the dictionary words. Every global array (text buffer, parse buffer, etc) would be its own segment.

Any memory location that we’d expect to never be accessed by a loadb or loadw would have a zero stored in the shadow array.

For best results, you’d want to parse Inform-style debug information to glean the locations of as many valid segments as possible. Some can be obtained strictly from the header though.

This isn’t foolproof, of course, since there’s nothing preventing you from manually computing a completely bogus address, but it would catch a lot of cases where we were attempting to read past the end of a known data structure.

But this way, any loadb, loadw, storebor storew could easily bounds-check its base address and count to detect reading or writing outside of the intended area.

Somewhat related, is there a standard way to determine the highest-numbered global variable, for systems that don’t unconditionally reserve all 240 slots? It could be computed at runtime by either looking for the opcode with the largest variable index reference, or possibly by looking for any pointer “closer than” 480 bytes from the declared start of global variables. The main reason for trying to determine the number of globals would be to detect attempts to inc/dec something that contained an invalid index. (Well, a value between 1-15 should also be range checked against the number of variables in the current routine too).

(I realize “making Z-machine games memory safe” is an extremely niche subject)

-Dave

2

No. (This was mentioned in another thread recently, I forget where.) Most interpreters don’t try to figure it out so there is no standard procedure.

It could be computed at runtime by either looking for the opcode with the largest variable index reference

I think that’s what Reform does. Not sure though – I’m not much good at reading Haskell. :)

2 Likes
3

(You might be remembering the thread where I asked a similar question, which is what is the highest valid object number)

4

I’m not sure you can use this if 0 is the base address - it’s also a common technique to use 0->n to access byte n in readable memory, or 0-->n to access word n in readable memory.

5

Good point. In that case, you’d just set entry[0] to 65535 if the game expects a 0-based array to access all of memory. In most of the code I’ve written so far at least though, I tend to be starting from a particular base address (perhaps the dictionary pointer in the game header, or a text buffer I’m processing) and not zero directly.

In fact, ordinarily I’d say that entry[0] should be 64, to prevent accidental access outside the header otherwise.

My compiler has the notion of a relocatableBlob which is a block of memory that can reference other relocatableBlob’s, and has a size and (eventually) an address. The header is a blob. Each object property table is a blob. So in my case, I could trivially initialize the “segments” 1:1 from my blobs. (Well, at least the ones below high memory)

Now that I think about it, opcodes like get_prop_addr could use the segment table as well.

6

So I looked into this last night, and the first stumbling block is the DEBF Inform debug format I support doesn’t have a good way to represent these regions.

The closest thing I could find was the ARRAY_DBR, but that seems specific to dynamic memory and also assumes that the globals are actually 480 bytes long.

I could invent a new DBR type or just dump the regions in their own file. The data, in its most compressed form, would be a run of nonzero lengths that are the length of each region. Negative values could mean “negative of this many bytes defines an invalid region” that would be invalid memory for whatever reason.

7

There are always 240 globals, even if a storyfile doesn’t use all of them. They can overlap other structures in the memory.