Memotech Related Tools

Z-Machine and Virtual Memory

Porting Z-Machine and Virtual Memory

By Bill Brendling

Introduction

The Z-Machine is a virtual computer for running text adventure games stored in "story files". Originally developed by Infocom in 1969 for their games, the Z-Machine is considered to be one of the first uses of virtual memory. Both the Z-Machine specification and tools for developing story files are now publicly available. As a result there are now many implementations of the Z-Machine and a large number of story files available for free download.

Story files are essentially programs written in z-code, which is the machine language of the virtual Z-Machine. They can be up to 512KB long, the first 64KB of which can be regarded as RAM, which can be modified as the program executes. The remaining space is ROM and does not change during program execution. Fitting both a Z-Machine emulator and a full sized story file within the 64KB of memory that a Z80 can address is clearly a challenge.

Before I started on a Memotech implementation, I identified two existing Z80 implementations:

• ZXZVM for Spectrum +3 and Amstrad PCW. These use banked memory to store the story files. ZXZVM is composed of two modules: a machine-independent interpreter core and a machine-dependent front end.
• CPCZVM is a derivative of ZXZVM ported to Amstrad CPC machines. It uses virtual memory techniques to implement the Z-Machine with just 64KB of RAM.

First Draft

For a first draft of a port, I started with the CP/M code from CPCZVM (That download also includes a version for AMSDOS that I ignored). There were two initial issues to deal with:

• The CPC runs CP/M 3.0, whereas the MTX only runs CP/M 2.2. It was necessary to remove all the 3.0 specific calls. Mostly it was not necessary to put anything in their place as the default behaviour of 2.2 was appropriate.
• It was necessary to replace the code for writing to the display with MTX appropriate equivalents.

The resulting program worked as a proof of concept, but was hideously slow. It was however sufficient to make an initial anouncement of the project on MEMORUM.

Unfortunately, I did not keep a copy of this version so it no longer exists. I must get into the habit of using source control on all my projects.

However the feedback was sufficiently encouraging to attempt to produce a better port for the MTX. The initial target was an MTX with 64KB RAM, a disc drive and CP/M.

The Virtual Memory Implementation in CPCZVM

From the "Technical Information" section of the web page for CPCZVM:

• The program reads the first 64KB of the game file, padding with 0's if less than 64KB, and writes out a SWAP.DAT file. A Z-Machine has a maximum of 64KB of RAM. Therefore the disc which CPCZVM is run from must have at least 64KB free and be writeable. When the RAM is written to this swap file is updated. This swap file is also re-generated from the game file when the game is restarted.
• Part of the CPC's memory is used for the virtual memory cache. A page table describes which virtual memory blocks are loaded and their physical location within RAM. This is initially populated from the start from the game file. When a read is done, the virtual memory address is looked up in the page table, and if it is mapped to physical memory then the physical memory is read. A write is similar to a read with an additional flag being set if a write has been made to a mapped page. If a virtual memory page is not currently loaded, then depending on the metric used, a page is chosen to be evicted. If the page has been modified it is committed to the swap file. Then the new page is loaded into the same physical location. During game play, any access to virtual memory in the first 64KB comes from the swap file, and any accesses above 64KB come from the game file. In this way the virtual memory supports both Z-Machine RAM and Z-Machine ROM.

Looking at the data structures in Z80 RAM used to implement the above, firstly there is the virtual memory page table, which contains the following data for each mapped virtual page:

Secondly there is the virtual memory buffers, where the data for each loaded virtual page is stored. A virtual page size of 128 bytes (one CP/M sector) is used.

The process of reading a byte of Z-Machine memory consists of:

• Search the page table to find a page containing the required virtual memory address.
• If no matching page is found:
  • Search the page table again, to find the page with the greatest age.
  • If this page has dirty flag set, write the corresponding data from Z80 RAM to appropriate location in SWAP.DAT.
  • Update the slot in the page table for the oldest page with the virtual address of the required new page.
  • Load the data for the required new page from either SWAP.DAT or the story file into the Z80 RAM buffer previously occupied by the oldest page.
• Calculate the offset of the required virtual address from the start of the virtual page.
• Add the location in Z80 RAM of this virtual page to the calculated offset. This gives the location of the required data byte.
• Reset the age of the current page to minimum value.
• Loop through the page table, incrementing the ages of all the pages which are less than the maximum.
• Return the required data byte.

The process of writing a byte of Z-Machine memory is similar, except that:

• Having found or allocated the slot in the page table, the dirty flag is set to indicate that this virtual page will need saving to SWAP.DAT.
• The new value is written to the selected location in Z80 RAM (rather than returning the value currently there).

It struck me that this repeated reading through the page table was very expensive in CPU time and could be improved upon.

New CPMZVM Virtual Memory Implementation

CPMZVM uses a virtual memory page size of 256 bytes rather than 128 bytes. This has a number of advantages:

• It is easy to split a virtual address into the page number (top two bytes) and offset within the page (bottom byte).
• It means that the page size is the same as the physical sectors used by type 07 discs.
• It halves the number of pages.

The maximum Z-Machine story file size is 512KB. Thus a maximum of 2048 pages (11 bits). Rather than the page table used by the CPC implementation, this version has a page index. The index contains entries for every page in the story file (not just those in memory). However, each entry is smaller, just 2 bytes, containing either the location of the corresponding data buffer in memory, or zero if not currently loaded. This table therefore occupies a maximum of 4KB.

Conversely, the data buffers are more complex. Instead of just containing the page data each buffer consists of:

The first buffer always contains virtual page 0x0000. This page always remains in RAM. The first 64 bytes of Z-Machine memory contains the game header which is frequently referenced by the interpreter, so having these fixed in memory speeds access to this data. Secondly, the previous and next pointers in this buffer form the head and tail pointers for a doubly linked list of the virtual data buffers.

Doubly linked lists provide a method of maintaining a dynamicaly sorted list without having to copy large amounts of data. An item may be removed from its current position in the list simply by updating the pointers to it in the buffers logically either side of it. Similarly, it may be inserted in a new position, just by updating the pointers on the buffers logically either side of the new position, and setting its pointers to the locations of its new neighbours.

The process of reading a byte of Z-Machine memory with the new virtual memory implementation is:

• Look up the buffer location for the required virtual page in the index. This is at a known offset in the index, not a linear search.
• If the result is zero (so the page is not in memory):
  • The oldest buffer is at the tail of the buffer pointer. This is found immediately from the tail pointer.
  • If this buffer has its dirty flag set, save the virtual page data to SWAP.DAT. The page number for this page is given in the buffer.
  • Set the new page number for this buffer, and load the required page data from SWAP.DAT (for R/W memory) or the story file (for R/O memory).
• Unlink the selected buffer from its present location, and re-link it to the head of the list. This maintains the buffer list in order of last access, so that the least recently accessed buffer is at the tail of the list.
• Use the last byte of the virtual address as an offset into the data part of the page buffer, and return the corresponding byte.

As for the original implementation, the write process is very similar to the read process, except that the buffer dirty flag is set, and data is added to the in-memory buffer rather than removed from it.

Additional Modifications

As well as the complete re-writing of the virtual memory system as described in the previous section, a number of other changes were made, including:

• As noted in the beginning, the original ZXZVM was written as two modules, linked by a jump table, to separate the Z-Machine emulator and the machine-specific code. This seperation was removed, and the machine specific routines called directly. This allowed the code to be packed down into low memory, leaving the maximum space free for the virtual memory buffers.
• The Z-Machine is more usually loading or storing 16-bit words rather than bytes. The CPC implementation did this by calling the byte load or save routines twice, repeating all the resulting memory lookups. This was revised to look up the address once and then transfer two bytes (unless they crossed a page boundry).
• As mentioned earlier, the Z-Machine frequently references the game header. Since with this implementation, this is always present at a fixed location, many of these references were changed to be direct RAM references.

Tests with MEMU suggest that the combination of all these changes speeded up the program by a factor of around three, making it almost playable.

Large Memory Version

Some MTX/SDX machines have the luxury of additional banked RAM in excess of the 64KB needed to run CP/M. This additional RAM is typically used for a RAM disc. However the Z-Machine emulator can make much more efficient use of the memory accessing it directly.

Therefore a second program was produced that, on startup, simply copies the entire story file into this additional banked RAM. When access to Z-Machine memory is required, routines in high memory (above 0xC000) swaps in the required RAM bank and copy the required data.

This version is not using virtual memory, the entire game is in RAM. As a result it is significantly faster.

WARNINGS:

• This program must be run from physical media, not from the RAM disc.
• The program will, without any warning, overwrite any data in a RAM disc by data from the story file.
• There must be more additional RAM (above 64KB) than the size of the story file. For machines with a correctly mapped 512KB of additional RAM this should always be the case, but if there is less RAM, or if the RAM is not correctly mapped then the available memory should be checked.

Download

The source code and compiled executables are in a zip file which can be downloaded from the Memotech forum here. In this zip:

• cpmzvm.com - The version for 64KB machines, using virtual memory as described.
• m576zvm.com - The version for machines with 64+512KB of RAM, loading the entire story file into RAM.

The file is also hosted on this website and can be downloaded below
200112	Current Release