Memory Management in BASIC (1/2)

I'm working away on C64 OS. And I've got a few things on my plate, but some things have to come before some others. Here's a quick summary of the current state of dev.

Nominally, I'm working on the class hierarchy of the Toolkit. And I'll return to this subject soon to discuss how that's developing. Before I can dig deeper into that, though, I need to improve the memory manager. There is a page allocator, which works well and I'm currently using only that for all my memory allocation needs. There are also the regular malloc() and free() routines that deal with arbitrarily sized chunks of memory from within a memory pool. A memory pool is typically a block of consecutive pages, that have been allocated by the aforementioned page allocator, and initialized.

At the moment, malloc() is quite primitive. It searches for a range of memory that's bigger than the requested chunk size, that has never previously been allocated, and it carves off a chunk of that memory turns it into an allocated chunk and returns a pointer to it. Free() can mark a previously allocated chunk as available. Additionally, if malloc finds a previously allocated chunk, that is exactly the same size as the current request, that is available, it can mark that as allocated and return it again.

But what it can't yet do is take a previously allocated chunk, that is available and bigger than the current request, and split it into two chunks; One which it marks as allocated and returns, and another that remains available but smaller. The memory manager also cannot (yet) merge two small consecutive free blocks into one larger free block. Shouldn't be too hard, it just hasn't been a priority until now. The Toolkit's classes are all kinds of varying sizes, and their instantiation depends on malloc. So malloc can no longer afford to be only half implemented. Before now, though, I haven't actually needed malloc for anything.

This post is part one of a two part post which begins by looking at Memory Management of the C64 and BASIC's role in managing its region of memory. Part two is about how to extract Floating point numbers and math routines from the BASIC ROM, without making use of, or triggering, the memory management and execution environment of BASIC, as a language.

Zero Page

Okay, now let's take another step back. The 6502 depends HEAVILY on zero page to perform many common tasks. Zero page (memory addresses $0000 to $00FF) has been described, by at least one paper I read, as almost an extended register set for the CPU. Because, it isn't just faster to access but many instructions need it for some addressing modes. Essentially, all instructions that support the Indirect-Indexed, and/or Indexed-Indirect addressing modes, can do so only by referencing a pointer that is in zero page. Many other instructions can use zero page addresses both to save memory and for faster execution than doing the same thing in any other page.

But there are only 256 bytes of zero page, and in practice there are only 254 bytes, because the 6510 reserves $00 and $01 for managing its built-in port. That means that zero page addresses are at a serious premium. There is one other problem, they're global. Any programmer who knows anything about anything learned very early in his or her programming career that global variables are the devil and that you should never use them. Ask a decent PHP programmer, or Javascript, or C, programmer what he thinks about global variables.¹

In 6502, you cannot avoid using global variables. This is one of the reasons why the C64 is so unsuitable for pre-emptive multi-tasking. It can be done, but you have to work around this shared space (and small shared stack, etc). If your program is of even moderate complexity, the only thing you can do is plan carefully, and manually allocate the space so that no two things need to use the same addresses at the same time.

This is essentially what the KERNAL and BASIC roms do in the C64. Someone sat down with a stack of paper, once upon a time, and mapped out all the zero page addresses and which addresses should be used for what by BASIC and what should be used for what by the KERNAL. In fact, this static mapping and manual allocation of memory extends up beyond zero page, to the two pages beyond the stack: $00 is zero page, $01 is the hardware stack, $02 and $03 are used much like an extended zero page. I usually refer to these pages as workspace memory, I'm not sure if that's a common term.

Thank god that Jim Butterfield and others of his kind long ago mapped out all the addresses in zero page and workspace that are used by the KERNAL and BASIC. These addresses and a brief description are outlined in books like Mapping the C64, and, my go-to favorite, The Complete Commodore Inner Space Anthology.

There are a few addresses that are left unspecified, $FB, $FC, $FD, and $FE are the most conspicuous in zero page, but there are a few others. Their consecutive nature makes these good for pointers, for use in the Indirect-Indexed addressing mode. On the other hand, there aren't very many of these addresses. The KERNAL and BASIC roms make liberal use of zero page. If you write an assembly program that doesn't need the KERNAL or BASIC, well, then, you are free to carve up and plan out your use of zero page in any way you see fit. If on the other hand your program is a chunk of assembly used to speed up your BASIC program, then you've got to leave BASIC and the KERNAL patched in, and you are much more limited in what you can use, and you have to be very careful, at the risk that you'll either make BASIC explode, by overwriting one of its addresses, or it'll cause your program to crash because it'll overwrite one of your variables.

What about C64 OS?

Well, C64 OS depends on parts of the KERNAL, but not all of it. And, while typically the BASIC rom is patched out entirely, as we'll see shortly, C64 OS sometimes patches in the BASIC rom to use a few select things that it offers. We need to know what every address in zero page and in workspace memory is used for, both by the KERNAL and by BASIC. Any address that is technically used by BASIC, but a part of BASIC that C64 OS never invokes, is an address that can be reallocated to C64 OS use. Same with the KERNAL.

This is not exactly clear, because a table such as that found in the Inner Space Anthology gives only a very abbreviated description of each address. Just a couple of words. Many of these addresses, themselves, already play double-duty, by two or more different routines that are known to never be used concurrently. These addresses need, therefore, to be disentangled. Once we do that, we have a lot more breathing space, with which we can more easily implement the memory manager and toolkit, etc.

The C64's Memory Management

I once joked about how the C64 Programmers Reference Guide is so old that its terminology is no longer the same as we use today. It's like an old dialect of computerese. For example, it states memory sizes like, 30K bytes, rather than any of the following: 30K, 30KB or 30 kilobytes. Likewise, what it refers to as memory management is not at all what we think of in terms of the ability to call malloc() and reserve an arbitrary chunk of memory which can subsequently be freed back up for later use, or the more advanced automatic versions of this.

While reading through the source code of the BASIC and KERNAL roms to figure out what memory they use, I learned quite a bit about how memory is managed in the way that we're more familiar with today.

The C64's memory, the full 64K, is effectively divided up into about 6 or 7 regions, most of which are static. These are: ZP/Stack/Workspace/Screen, BASIC RAM, BASIC ROM, High Mem, I/O, KERNAL ROM. Okay, that's 6, but there can be a sort of pseudo 7th region.

The first, lowest, region is one big chunk from $0000 to $07FF, it is 100% manually laid out, as discussed earlier. Nothing "manages" it, everything just carefully uses part of it with fixed addresses. Zero page, stack, workspace and the screen matrix, and a little bit of space is left in there for a few sprites.

After this, is the largest main bulk of memory, from $0800 to $9FFF, this is managed (really, truly "managed") by BASIC. Although as we'll see in a minute, how BASIC actually manages it is very simple. Next is the BASIC ROM, underwhich is 8K of RAM. This RAM is completely untouched by the C64 in its stock mode of operation. The KERNAL doesn't touch it, BASIC doesn't touch it, they just ignore it.

After that is High Mem, that's $C000 to $CFFF. This is also completely untouched by the KERNAL and BASIC. But it's not covered over by anything, so it's an obvious and favorite place to shove a smallish <4K assembly program that needs to co-exist with a BASIC program.

After that comes I/O, that's from $D000 to $DFFF. There is memory under this region, but it's cohabited by I/O (and sometimes the Character ROM.) If BASIC and the KERNAL are patched in, I/O generally also has to be patched in, because the KERNAL makes unchecked calls to this area, expecting to find I/O devices there. Technically, the KERNAL and BASIC ROMs can be available while the Character ROM is patched in. But patching in the Character ROM is rare, and I guess you just have to be careful to not call routines expecting to find I/O. You have to disable interrupts, for example, otherwise the KERNAL's IRQ handler will try to read from the CIA (an I/O chip) to scan the keyboard. The KERNAL and BASIC, therefore, don't ever use the RAM under I/O because, well, they can't ever physically see that RAM.

And lastly, is the KERNAL ROM. There is another 8K of RAM under there from $E000 to $FFFF, and guess what, it's never used by the the KERNAL or BASIC either. So, when you start up your C64, the built-in OS effectively ignores the last 24K of its 64K of RAM. That's ~38% that is just ignored. Imagine if you bought an iPhone with 3GB of RAM, but the OS just ignored a full 1GB of it!

BASIC's Memory Management

In its default powered on state, then, only the BASIC ram region from $0800 to $9FFF gets managed. And it is only BASIC that needs to manage memory. The KERNAL provides the IRQ service handler, device I/O for the IEC bus, tape drive and RS-232, as well as interpretting PETSCII and implementing the Screen Editor, which it abstracts as just another I/O device. But the KERNAL generally only operates on reading and writing single bytes at a time. It is the software which calls the KERNAL that needs to decide where to put those single bytes. There are a couple of small exceptions. LOAD, for instance, loads a program into memory, and the RS-232 routines need to open a buffer, but we'll return to that.

BASIC uses a set of pointers, at a set of addresses reserved in zero page. These pointers divide up the chunk of BASIC ram into 4 regions (plus a flexible unused region). The pointers point to the start and ends of each of those regions:

• Program Code
• Variables (Strings, Ints, Floats)
• Arrays (i.e. Dimensions)
• Flexible Unusued Space
• Strings

The biggest issue with memory management, in general, is finding free space to allocate, marking space as taken or available, and then the inevitable fragmentation and how to deal with that. The question is, how does BASIC deal with memory? What happens as you edit a program? What does it do with strings that are already allocated when it needs to make more room for new program lines? How does it rearrange program lines when you insert a line number into the middle of a program?

When I first started investigating this maybe a year ago, I naturally assumed that it was doing something much more sophisticated than it is actually doing. On a basic program line, the first two bytes are a pointer to the start of the next line. That looks like a linked list to me, and I know that the elements in a linked list don't have be in memory in the same order that they are in the list. I assumed that if you had a 100 line program, and you inserted a line somewhere near the beginning, that it would manipulate the linked list pointers to link the new line into the correct place near the start of the program, even though the code resides somewhere higher in memory, following lines you'd entered earlier.

This didn't satisfy all of the problems though. For example, what would it do if you took an existing line and modified it making it a few characters longer? It could abandon the old line, allocate space higher in memory for the longer line, remove the old line from the linked list and link in the new line. The problem is that that would produce some serious fragmentation. Another problem is, what would it do with variables and strings already in memory as the program's source code grows? Surely it must need some overarching management schema.

It turns out I was WAY overthinking its sophistication. It is much much simpler (dare I say, more basic) than I'd initially imagined. Let's take program lines. You type a line into the screen editor, effectively into screen matrix memory. The screen editor maintains pointers to the start of each line, and uses bit flags to mark which lines are the start of a new logical line. That's how it allows two physical 40-character lines to be treated as one line of BASIC. The moment you press return anywhere within that logical line, the entire line is immediately processed.

BASIC keywords are replaced by their tokenized equivalent (all BASIC tokens have their high bit, b7, set, to distinguish them from all other constants.) Syntax is not actually checked at this point. However, the line number is interpreted to figure out where in the program the tokenized version of this line should go. Here's the crazy part: On the fly, BASIC moves every line that is already in memory that has a higher line number than this one, up by the length of this new line. And as it goes, it rewrites all of the link pointers of each line by adding the length of this line to the next pointer of each subsequent line.

Similarly, if you clear a line, by entering a line number alone, all of the lines after that line get shifted down in memory by the length of the line being removed. And all the pointers are adjusted down by this length too. And, in fact the same thing happens whenever an existing line is modified. If it is made to be longer, all higher lines are shifted up by the difference in line length, and if the line is made shorter, all higher lines are shifted down by the difference. All line pointers are updated each time.

References to line numbers within a program line are always kept in their PETSCII text format. For example, if you enter the line, 50 GOTO 100, its own line number, the 50, is used to figure out where this line needs to be inserted. The 50 is converted to an int and stored as the first two bytes of this line, following this line's next line pointer. But 100, the argument of GOTO, is left as 3 bytes of PETSCII. The GOTO is converted to the 1-byte token: $89 (note that the leftmost bit of that token is set.) ²

When the line is actually executed, however, the PETSCII 100 is converted to an int and used to search for a line with that number. This search can hop quickly from line to line by following the next line pointers. The bytes immediately following the line pointer are the line number. This realtime searching for the line numbers, is slow, yes, but when lines are shifted as a result of new lines being inserted or removed, the inner contents of the line do not have to be updated to point somewhere new.

It should be obvious, based on how this works, that there is very little memory management necessary in the program code region of BASIC ram. All the lines are always packed together, and stored as low in memory as possible. There is never any fragmentation because all holes or gaps are immediately closed by shifting everything down to fill in the empty space.

BASIC Variables: Memory Management

Well, what about BASIC variables? Where do they go? How are they found?

As you edit your program, the program gets longer or shorter. The place in memory where the program ends moves each time you modify the program. But then, how does BASIC deal with the situation where the program size encroaches on the variable space?

Are you ready for it?

Every time a BASIC program is modified, all variables, all dimensions and all strings are immediately destroyed. (ACkk!) How does it do this? Remember the pointers for the start and end of the various regions within BASIC ram. When the program is modified, the pointers for variable start, array start and array end get set to the same address. They are set to the byte immediately following the last byte of the program area. (The string area pointers are handled a bit differently.) The ACTUAL contents of memory don't get touched. The pointers simply indicate that those spaces are 0 bytes long.

This all comes into focus when you see how BASIC variables are looked up.

Dimensions are handled differently than variables of type: String, Int and Float. All string, int and float variables have exactly the same length: 7 bytes. The first two bytes are the 2-character variable name, plus a little extra. You cannot use uppercase letters in BASIC variable names, only lowercase letters, and numbers may be used as long as the variable starts with a letter.³ Lowercase letters and numbers are all in the lower half of PETSCII, so bit7 can be regarded as implicitly low. This leaves these 2 bits, b7 of each byte, free to be used to represent the 3 variable types. The variable type defines how the following 5 bytes are structured.

• String variables use 3 bytes. One byte holds the length of the string, the other two bytes are a pointer to where that string is in memory. The last 2 bytes of a string variable are just filler. They are completely ignored.
• Int variables uses just 2 bytes. The value of the variable is a 16-bit signed int stored directly in the variable itself. With ints, the final 3 bytes are ignored.
• Float variables uses all 5 bytes to store the float value directly in the variable. Floating point variables will be the focus of part two of this two part post.

Variables are all the same size, 7 bytes, because of how BASIC looks them up. When a line is executed that refers to a variable, the two bytes of the variable name are used to search through the list of variables looking for a match. It starts at the pointer for where variable memory starts, and it jumps in 7 byte increments to move from variable to variable looking for a name/type match on the first two bytes.

Keeping all variables the same size makes it fast and easy to scan through them, to overwrite one with another, to move them, etc. And the reason for the number 7 is because that's the minimum size needed to store a float.

How dimensions are structure, how strings are referenced, and how these areas are manipulated during the runtime of the program, is beyond the scope of this post. It's also somewhat beyond the scope of what I've figured out yet so far. Before moving on to look at Floats in particular, let's look at some examples of what happens to BASIC variables when a program is edited.

This screenshot shows what happens to variables when a program is modified. First the program is listed, it has one line. Next we set A, and then print A, and see that it is set. Next, we add a single line to the program and list the program again. Print A, in direct mode, one more time, and we see that A has been destroyed. When the program was modifed, all the pointers to the regions for variables, dimensions and strings got reset.

This next screenshot shows something that I hadn't yet mentioned. How does BASIC deal with fragmentation of memory between subsequent runs of the program? Easy, it blows away all variables, dimension and strings whenever the program is RUN!

List the program, all it does is print A. Run the program, A is zero. Set A to 20 and run the program again. Instead of printing 20, it prints zero again. That's because all variables are destroyed when the program is run.

The next screenshot shows that it isn't just a difference between direct mode and program mode variables. The next program starts by setting A=A+10, and then printing A. On each run, A never gets bigger, it is always 10. Because at the start A gets reset to 0, and 10 is added to zero afresh each time.

Although dimensions are a bit outside the scope of this post, these screenshots show that this behavior is not limited to regular variables. In the first screenshot, a dimension A is created with 500 placeholders. A few of them are populated, and then printed to confirm that they are set.

In the second screenshot, a program that does nothing by print A is run. After it runs, we check the stored values at some of the indexs of the dimension, they are all reset to zero.

Variables are not destroyed at the end of a program's run. This is very useful, of course, because a program could produce many intermediate strings and values that it never actually prints. When the program ends, you can print those values from direct mode. The variables are only destroyed as part of the initial behavior of the run command itself.

But there is another way to run a program, sort of. Once a program ends, it may be possible to continue with CONT command. When a program is continued, it does not destroy variables first, for obvious reasons. This has the interesting effect seen in the first screenshot. The first line increments the variable A by 10. But as we saw earlier, running the program always resets A to 0. In this case however, at line 30 there is an END command, but on the following line is a GOTO 10.

When the program hits the END it stops executing and returns to direct mode. A is still set. If we were to run the program, A would be reset. If instead we CONT, the program continues executing on the line after 30. Line 40 sends it back to line 10, and the increment does what you would expect. You can continue multiple times, and each time A increments by 10.

This is neat, but you can toss the security/integrity of a BASIC program to the wind. The STOP button on the C64 keyboard (and other Commodore 8-Bits) introduces a break in the program at any arbitrary spot. You end up back in direct mode, where you can modify variables, and then issue a CONT to pick back up where it left off, but with modified variables!

Program integrity can really be messed up by this. In the program, A is only ever incremented by 10. Program logic following this might justifiably assume that A will always be divisible by 10. But as you can see, you can hit STOP, change A to something other than a multiple of 10, type CONT, and the program carries on with A holding an "impossible" value.

The Pseudo 7th Memory Region

I said I'd come back to this.

While BASIC ram is the largest and main chunk of contiguous memory, it is divided up into regions via the set of BASIC pointers. The thing not mentioned is that those pointers include a BASIC start (that's the start of the program code area), and a BASIC end (That's the end of the Strings region at the end of BASIC ram.) BASIC's routines for starting a progrogram when run, and where to search for variables, and where to put new strings, etc. are all informed by these pointers.

One can, therefore, adjust either the start or end pointers, or both, to shrink the space which BASIC manages. Thus preventing BASIC from corrupting areas of memory below or above its start and end. As a programmer, you are then free to use that space for whatever you want. You could use it for assembled machine code, or you could use it as a data buffer with a custom structure, for example for bitmap data, or more sprites, or a SID tune, etc.

I mentioned that the KERNAL mostly only operates on single bytes. And that some other software has to decide where to put those bytes. But there were a couple of exceptions: LOAD and RS-232.

LOAD is used to read bytes from a storage device (IEC bus or Tape Drive) and put those bytes in memory. How does it deal with memory management for this process? In short, it doesn't. There is no memory management taken into consideration.

When a LOAD starts, it has no idea how much data it is going to retrieve from the storage device. It has two modes, by default it will but the data into memory starting at $0801, the default start location of a basic program. Or, alternatively, if you supress the automatic relocation, it will use the first two bytes of the file to decide where to put the data.

It just puts one byte after the next. If the file specifies that it should be loaded to $0100 (the stack), the KERNAL will try to load the data there, which will overwrite what is already in the stack, and the whole process will probably just crash. Similarly, if the data being loaded crosses over into I/O, it'll start writing those loaded bytes to I/O instead of RAM, and all sorts of whacky things will happen, and almost certainly a crash.

Under normal circumstances, the program has been designed to be loaded into the correct place for itself, and it simply assumes that it is the only thing in memory. For a BASIC program, this works out quite well. The BASIC program is written directly into memory at $0801. Ready to be run and start establishing its variables and strings within the confines of the pointers that were setup at load time and reset at the start of run time.

The KERNAL has built-in support for the RS-232 protocol over the User Port. It has a few caveats. The C64 does not have a UART (a Universal Asynchronous Receiver/Transmitter) chip. These chips are designed to handle RS-232 timing and data transfer and to buffer incoming data. This offloads the work from the CPU which only needs to handle reading and writing bytes to and from the buffer. Consequently, the C64's CPU has to do a LOT of work to make RS-232 possible, therefore, it is not very fast, but it does work.

The other caveat is that RS-232, according to specification uses a higher voltage range, +15 to -15 volts. The C64's output is driven by the CIA chip, and can therefore only be in the standard range of its own logic, 0 to +5 volts. So it's sort of a non-standard RS-232, that needs to have some voltage level converters to communicate properly with other ordinary RS-232 devices. That's an interesting side note, but it's not relevant to memory usage.

What is relevant to memory usage is that the C64's own CPU, interacting with the CIA, not only has to implement the timing and signaling protocol of RS-232, but it also has to implement its own buffer into and out of which to transfer data. The buffer is necessary because the timing is so critical. The buffer is always ready to receive, it doesn't depend upon the readiness of some other arbitrary device or process.

But, where does that buffer come from? Normally, RS-232 communications are not being used. So you wouldn't want to rob the system of a couple of pages of memory unnecessarily. Instead, the KERNAL automatically adjusts the end of BASIC pointer down. This opens up for it a space just below the BASIC ROM. Then the KERNAL sets pointers in workspace memory to this free area. All the RS-232 routines refer to this pointers to find the buffer.

Conclusions

That's a rough overview of how the C64 manages its memory. How BASIC is responsible for truly managing the only area of memory that actually gets managed at all. And a toe dip into how BASIC actually goes about performing that management.

Just as the KERNAL ROM is packed with a variety of different services, the BASIC rom is also packed with its own set of services. The running and interpretation of a BASIC program ties together all of the different parts into a cohesive whole.

We saw, however briefly, how a running BASIC program is able to store a 5-byte floating point number, embedded within a searchable, memory-managed, 7-byte BASIC variable. In the next part of this two part post, we'll focus just on Floating point numbers. We'll look at how they can be extricated out of the context of the BASIC environment, and used in conjunction with BASIC's floating point math routines from a pure machine language context. In particular, how C64 OS and C64 OS applications, written in assembly, can make use of the floating point math routines available to us in the BASIC ROM.

1. **AVOID** [↩]
2. See the VIC-20 / Commodore 64 SuperChart to see the list of all the BASIC tokens. [↩]
3. See the end discussion from my Programming Reference post VIC-20 / Commodore 64 SuperChart, for a discussion on why these letters are "lowercase" even though they appear uppercase when you first turn on your C64. [↩]

Do you like what you see?

You've just read one of my high-quality, long-form, weblog posts, for free! First, thank you for your interest, it makes producing this content feel worthwhile. I love to hear your input and feedback in the forums below. And I do my best to answer every question.

I'm creating C64 OS and documenting my progress along the way, to give something to you and contribute to the Commodore community. Please consider purchasing one of the items I am currently offering or making a small donation, to help me continue to bring you updates, in-depth technical discussions and programming reference. Your generous support is greatly appreciated.

Greg Naçu — C64OS.com

Want to support my work?

C64 OS version 1.04 is now available

The best way to help C64OS.com grow and continue is to purchase a commercial copy of C64 OS version 1.04.

Join the growing C64 OS user community. Take advantage of the powerful and useful features available now, and get access to run new and future software made for C64 OS.

Learn More Order Now

C64OS.com is hosted on a Digital Ocean droplet.

Digital Ocean is a cloud hosting platform, built for developers. They make it simple to get started. They have intuitive administrative tools and reasonable prices. And they can scale as your needs grow.

If you sign up with this referral link, you'll get a $100 credit, and after you've spent $25, I'll get $25. If you are looking for a cloud platform to host your website or web app, this is win-win.

Sign up for Digital Ocean with this refereral link.
Save money and help C64OS.com at the same time.

No, thank you.

Want to support my hard work? Here's how!