Guest Post from Bitshifter: Fixing the Oldest and Nastiest Bug in Commodore BASIC

We again are able to enjoy another guest-post from Bitshifter, as he fixes and enhances the C65 ROMs for use on the MEGA65:

---  

The probably oldest and nastiest bug in Commodore BASIC

A huge part of working on the ROM for the MEGA65, which contains the resident part of the operating system and BASIC interpreter, is Debugging. Not counting the character sets, the source code, written in 45GS02 assembler, has about 30000 lines, separated into the modules kernel, editor, DOS, BASIC and graphics.

The debugging is necessary mainly for two reasons:
1) Programmers, developers, software engineers are humans.
2) A source code, that is not your own, is full of traps, side effects and assumptions, that one is not aware of.
Of course my own code is full of traps and side effects too, but I know them (at least for the next few months).

While working on the ROM, fixing Commodore bugs, optimising code to get free space for extensions and introducing new features (and sometimes new bugs), I write often some hundred lines of assembly code and make changes on existing code. Sometimes these changes seem to work perfectly, some result in crashes and freezes, because of errors and some only seem to work fine in my own test, but fail if a developer named „ubik“ demonstrates situations, which the code cannot handle.

Well, I’ll not tell a long story, how I debug, but come directly to the bug mentioned in the title. I tracked his existence down to BASIC 2.0 as used in the VIC-20, C64 and the early PET/CBM series and it seems, that it was never detected, documented or fixed.

It is related to temporary strings, the stack of descriptors for temporary strings, that has a size of 3, and the so called „garbage collection“, which in reality doesn’t collect garbage, but does a defragmentation of string storage.

Let’s look at an example:

10 V1 = 12345: V2 = 6789

20 A$ = RIGHT$(MID$(STR$(V1),2)) + RIGHT$(MID$(STR$(V2),2))

and let’s look into string memory, after the execution of these two statements:

The interpreter needed 6 temporary strings, these are the strings, which are followed by the two byte „garbage“ word in magenta, to create the resulting permanent string, marked here with the „back link“ word in yellow.

Each time, where a string is modified or new assigned, it gets a new allocation in string memory and the old string is flagged as „garbage“ by replacing its back link, which points to the string descriptor, by the garbage word, which is the length of the string, followed by $ff (The high byte $ff can never appear as part of a back link, because the highest address in string memory is $F6FF, therefore it is safe, to use this value as flag).

In programs with much string activity, the occupied string space, which grows from top ($f6ff) to bottom (top of array space), will be filled very fast and if there is no more space left for creating a new string, the call of the defragmentation routine is triggered. This starts at top of screen memory and copies all strings, which do not carry the garbage flag, to adjacent addresses, skipping the garbage strings. Doing this it is necessary, to update the string pointers of the descriptors. That’s the purpose of the backlink: After copying a string to the new address the back link is used to find the descriptor, and the two pointer bytes of the descriptor get the new address. Te descriptor can reside in scalar space, e.g. for a variable like AB$, or in array space, e.g. XY$(I,J) or it can be a temporary descriptor on the descriptor stack in the zero page. And this is, where the bug lurks.

The descriptor stack is 9 bytes long in the zero page and has therefore room for 3 descriptors. Additionally we have a stackpointer, which has four valid values for 0,1,2 or 3 descriptors in use. And we have a LASTPT called variable, which points to the last temporary descriptor, which was used to allocate a string. This is an optimisation tool. When a string is no more needed and it is the last string, that was allocated, the pointer to the used string memory can be updated by the length (plus 2 for the back link) instead of just flagging the string as garbage. This method can slow down the speed of filling the string memory somewhat and let’s the defragmentation happen less often.

This LASTPT is initialised at the execution start, alas only the high byte!

The low byte therefore has the value, that was either initialised at power up or has the value from a previous use. This use can for example be the loading of a program, because this involves string handling for the filename and therefore the use of the descriptor stack.

So it can happen, that the routine, that pops a value from the descriptor stack compares the current pointer with LASTPT, sees equality and decides not to flag the string as garbage, but to update the pointer to free string memory instead. This is an error, if the value of LASTPT is from a previous usage and was not set in the current statement. Alas, it will have no consequences in 99.9 % of the cases, because at the end of a statement all temporary descriptors are freed anyway.

The bug can drive mischief if following conditions meet:

1) A program with heavy usage of strings, which triggers the garbage collection / defragmentation frequently.

2) Statements with complex string operations, which need more than one temporary descriptor.

Then a really rare event can happen:

The garbage collection is triggered in the middle of a complex string formula with temporary descriptors on the stack. The garbage collection is aware of temporary descriptors and copies their strings too and updates the descriptors, but if one of the descriptors freed his string due to a false LASTPT comparison, his string is outside of the garbage collection area and will not be updated. And this causes strange things to be happen. The descripror has now a pointer, that does not point to a valid string. So the whole system of links and back links is corrupt. To make the bug hunting more interesting, this corrupt pointer often does no obvious harm until the next garbage collection, or the collection after it, but each will make the error worse, until back links appear in screen memory or strings dissappear or the computer freezes.

And all this because the setting of LASTPNT was not done with:

STA LASTPT

STA LASTPT+1

instead the first part, setting the low byte, was forgotten.

BTW, the highy byte is always zero, because the descriptor stack resides in the zero page, so this usage of the high byte is redundant.

I found this bug in all versions of Commodore BASIC, that I investigated, VIC-20, C64, C128, C65, MEGA65.

But it needed the „11 BASIC“ preprocessor/compiler of UBIK, to let the bug appear.

And it was very difficult to detect, because only huge programs with heavy string activity could activate it.

So the old programmer’s talk is true:

You can only find the penultimate error in a program!
There is always the ultimate error, that remained undetected.