ExecSG in detail: Memory
by Thomas Frieden, Hyperion Entertainment

After last month's article about the new library system in OS4, I'd like to take the opportunity to introduce yet another area of improvement: The memory system.

Classic Exec view of memory

The Amiga is a 32-bit system. This means that it has 32 bit addresses, which allows it to access 4294967296 individual cells which make up it's address space. Some parts of these addresses are "real" memory, that is, if you store data to these addresses, you can read it back. Other parts are used for other purposes, like, for example, to access the Amiga's custom chip hardware.

Most Amigas have different memory banks. All of them have chip ram (which always starts at address 0), some have additional fast ram (for example on the A4000 mainboard), and if there's a PPC board in the machine, it's likely to have it's own memory bank as well. All of these memory banks are sitting at specific addresses that are fixed by the hardware.

Older exec versions used this exact layout of memory. To allow programs to dynamically allocate memory, these versions use simple lists, covering each consecutive memory area: Free memory is part of the list, occupied memory is not. Initially, the whole memory bank is covered by a list with one node. When memory is allocated, the list is scanned, and the first block that is either larger or the exact size is taken and removed from the list, and if larger than the requested amount, it's split and the remaining memory is returned into the list.

This method is rather simple and can be efficiently implemented, but it bears several problems. One problem, obviously, is that this method only allows programs to allocate up to the amount of memory installed in the machine. If a machine has, for example, 16 MB installed, it's not possible for any program to allocate more than 16 MB, even though the 32-bit address space would allow for 4 GB of "addressable" memory.

Another problem is even more annoying, and chances are that you might already encountered it when working with your Amiga: After several hours, the machine will become slower, and programs might complain about not having enough memory available, even though Workbench shows you that there's enough free memory. This problem is called fragmentation, and is an inherent problem of the list approach described above.

Fragmentation is caused by continuously allocating and freeing memory, which leads to gaps in the free memory. It also causes the list to become quite large, so it takes longer to traverse it (hence the slowdown). Once fragmentation is present, the only method to get rid of it is to reset the machine. not a good solution, one has to admit.

ExecSG: moving towards a virtual environment

To address these issues, ExecSG introduces something called "virtual addressing". Instead of accepting the memory layout introduced by the hardware, ExecSG tries to "reorganize" memory. This allows it to avoid fragmentation, and fix a number of other problems (it introduces some incompatibilities, though).

Before we go on, I have to explain what virtual addressing means. Don't worry; I will try to make it as non-technical as possible.

Virtual addressing

A dictionary defines "virtual" as "existing or resulting in essence or effect though not in actual fact, form, or name". In other words, it describes something that is seen but not actually there, like a mirage.

And this in fact nicely describes virtual addressing: You address memory at a place it's not normally available. For example, the CPU might try to access memory at address 100, but in reality, it's accessing address 2340. A part of the CPU called the "memory management unit" (or MMU for short) just replaces the virtual address by a physical address. So it's possible to use the MMU to completely change the memory layout. We can, for example, combine several areas of memory into one linear block. If you ponder this possibility, you probably know how to prevent memory fragmentation: by combining smaller blocks into one larger (virtual) block.

Of course, this remapping can't be arbitrary. Modern CPUs can remap blocks of memory to other blocks. These blocks are commonly called tiles, or pages. The term tile aptly describes how this works: Imagine the tiles on a bathroom wall. The MMU can "virtually" rearrange those tiles to form a new version of the wall (the comparison is a bit weak, but should give you an idea on how this works).

Note: Even though the term tile more obviously describes what's happening, the term page is normally used.

As a real-life example, the PowerPC can remap pages of 4096 bytes each (Older CPUs, like the original 68000 didn't even have such a facility, it was introduced with the 68020 as an external chip, and as part of the CPU since the 68030).

To keep down management overhead, ExecSG uses a page size of 64 KB. This means it divides the complete 4 GB address space into 65536 different pages.

Object oriented memory management

ExecSG goes beyond the list approach used in old exec. Memory areas are now objects that are kept in a priority-sorted list. When memory is required, ExecSG queries the objects in the list, asking if it can fulfill the request in terms of size and requirements (for example, a program might ask for a size of 100 bytes and a require chip ram). If the object can't fulfill the request, the next one is asked.

When the object can fulfill the request, the request is executed, and the object reports the allocated memory area back to ExecSG.

The key point to note is that the actual implementation of the object is opaque: Instead of requiring a memory list, the object is free to implement this however it wants to. This makes it possible to exchange the implementation of an object. An object doesn't even need to have the ability to allocate memory at all (see the next section).

But these objects can do even more: Each object controls an area of address space. In addition to managing memory, it also manages other things. For example, when a program tries to access something inside the area controlled by an object, and this results in an error condition, the object itself can intercept that error condition and act accordingly. This is a very powerful mechanism that can be used for a lot of applications, as we will see in a few moments.

Applications and possibilities

The object-oriented approach allows a lot of mechanisms to be implemented that where not possible with the original design. In this section, I'd like to list some of the possibilities: Some are already implemented, some are planned.

Virtual memory: This is the most basic application of the memory objects. An area of address space is used as memory, with "real" (i.e. physically existing) memory being re-mapped to form one large area of memory. This addresses the fragmentation issues that where plaguing the old Exec memory lists.

In addition, this also allows other features, like resizing allocated memory blocks, and delayed memory allocation. Delayed allocation means that the virtual addresses are allocated, but the physical memory is not. Whenever a program now accesses the memory, the above-mentioned error condition hits. As the memory object can intercept this, it can then allocate a tiny bit of memory to make sure that the access works, and return control to the program.

This can be interesting for programs that want to load compressed data into memory: Allocate a large area with delayed allocation (this does not use real memory), then uncompress into this memory, and afterward resize the block to the necessary size. No more than the necessary memory is really used.

Paging/Swapping: This is what is often referred to as virtual memory. If memory is needed but not available, parts of the existing memory are written to a disk, and the now free memory is used by someone who needs it. Remember that virtual addressing allows blocks of memory to appear anywhere, so it doesn't really matter where the memory comes from.

Automatic stack enlargement: If you ever used gcc on the Amiga, or played one of our game ports, you'll probably know that they use a very big stack. You have to set this manually, either in the shell, or in the program's icon. With the ExecSG memory objects, it's possible to make stacks that are automatically enlarged when they are too small. This doesn't require special code in the program (like it's now), and will come with no additional overhead (normally, programs that check their stack themselves run slower than programs that don't care about it).

Memory mapped files or objects: A feature of other operating systems is the ability to "map" files into memory: Instead of using special functions to read or write to a file, the file is accessible as if it was completely loaded into memory, even if it's bigger than the available memory. This feature is also possible with ExecSG's memory objects.

Mediator support: A simple version of a memory object can also simulate the "MMU feature" of the Mediator.

Memory protection: This is the next big step forward. One of the next versions of AmigaOS 4 will have per-application memory objects. The available objects will depend on the currently running process. This simple step will have a very big effect: It will give each running program it's own memory layout. That means that each program will run in it's own address space, and thus it's memory is protected from accidental access from other programs. Some memory objects will remain valid for all programs, for supplying memory that's part of all programs (shared memory).

This step will give the Amiga a new level of stability and security.

Closing

As you can see, there are lots of possibilities. This article could only scratch the surface. I hope it wasn't too technical, but the subject is inherently technical in nature.

Have fun.

Thomas Frieden
Hyperion Entertainment