Ben Summers explains the workings of the RISC OS heap manager
Most programs need to hold data to work on, so they need to be able to allocate blocks of memory to store it in. High-level languages, such as Basic, provide some form of memory allocation although it is often rather primitive and when you write programs m assembler, you don't have any dynamic memory allocation facilities at all.
In Basic the memory allocation is very simple: You can create blocks of memory but you can't increase their size or give them back once you have finished with them - and in more complex programs you need to do this. When you need something a little better, heaps are an ideal way of solving your problem.
A heap is simply an area of memory from which blocks are allocated and freed as they are required. The relocatable module area (RMA), for example, is a heap. When modules are loaded, a block is allocated for the module code and usually another for some module workspace.
When the module is killed, the blocks which it used are freed, releasing the space for other modules to use. Put simply, a heap enables a large quantity of memory to be managed easily. Many different types of separate data can be kept in it without conflicting.
A heap manager is a set of routines which control the use of memory in a heap. It keeps a list of blocks which have been used and a list of free blocks of memory (the free list). When a block is requested, the free list is scanned to find out if there is enough free space in one block and, if there is, the lists are updated and a block is claimed. When a block is freed, it is simply added to the free list.
This type of heap manager has one disadvantage in that the heap tends to get fragmented. The blocks cannot be moved around to put all the free space in one block and so a request for a block will fail even if there is enough free space in the heap but it's not all in one block. It's mainly a problem where there are many small blocks in a heap.
RISC OS provides routines to perform many of the common functions a program needs. For example, the Font Manager allows all programs easy access to lots of good fonts and the printer drivers enable the programmer to print on just about any printer with the minimum of effort.
All these routines avoid repetition of code - making for fast program development and small programs.
The heap manager is one of these central resources. It maintains the structure of a heap within a block of memory provided by the program, and the program then asks the heap manager to allocate, extend and free blocks.
All data about the structure of the heap - which areas are used and which are not - is kept within the heap itself so it is not possible to use all the space for data. For example, in a heap 1,024 bytes long, it is not possible to allocate a block of 1,024 bytes.
The first words in a heap, called the heap descriptor, contain a special identification word to enable the heap manger to check that you have passed it a valid heap - there's an offset to the first block in the free list, an offset to the end of allocated blocks in the heap and the size of the heap.
Each block in the free list contains a pointer to the next block and its size, and each allocated block is prefixed by its size. All this information enables the heap manager to know precisely which bytes in the heap are used.
The exact structure of a heap is described on page 1-349 of the RISC OS 3 programmer's reference manual and on page 777 of the RISC 0S 2 manual.
Format of the heap descriptor
&00 - Special heap word
&04 - Free list offset
&08 - Heap base offset
&0C - Heap end offset
However, you shouldn't rely on this structure when you're writing a program using the heap manager as it isn't guaranteed to remain the same in future versions of RISC OS.
Like all these things, if you don't rely on it, it will remain the same indefinitely, but if you do it'll change in the next minor update.
The heap manager is controlled by a single SWI which is in fact seven separate calls. This controls all aspects of the heap manager.
Which call you want to use is specified by a reason code in R0 and, as usual, the rest of the registers are used for parameters.
R1 is always the address of the heap, and where necessary R2 is a pointer to a block within the heap and R3 either a size or a change in size.
To set up a heap, you first need to claim a block of memory from the host language. In Basic you use the DIM statement.
In assembler, you will need to allocate a block of memory either by using the store initialisation statements, claiming it from the RMA or using the address of the end of the program code as the base of your heap.
The first step is to initialise the heap, you use the SWI OS Heap with a reason code of 0. You need to tell it where the heap is and how large it is (in bytes). In Basic, to set up a 64k heap you would use code such as:
heap_size% = 64*1024 DIM heap% heap_size% SYS "OS_Heap",0,heap%,,heap_size%
The DIM statement is a little different to the form used to create an array. The above example reserves a block of memory heap_size% bytes long and puts its address in heap% which is then the pointer to the block.
The heap manager checks that the addresses and size you have passed it are valid and then sets up the heap descriptor and it's ready for use.
Once the heap has been set up you can claim blocks from it using a reason code of 2. There are two ways to tell if the attempt was successful or not. Firstly, you could use the SWI call as usual, and assume that claiming a block succeeded. If it didn't, an error will result and the error handler (set with ON ERROR in Basic) will be called. You could use something like:
SYS "OS_Heap",2,heap%,,size% TO ,,block%
Or you could use the X form of the SWI so the error handler is not called. If a block could not be allocated zero will be returned instead of a block pointer. The call looks like:
SYS "XOS_Heap",2,heap%,,size% TO ,,block%
In both cases, a block size% bytes long will be allocated, and the pointer to it is returned in block%. In the second case, block% will be zero if no block could be claimed. You can test for this and program accordingly.
Using an allocated block, either from a heap or using the DIM statement to reserve some memory, is different to using standard arrays.
Basic provides several indirection operators to access memory just as you would normal variables. However, you have to be careful not to exceed the bounds of the memory you are using.
You can use the ? indirection operator to access a byte, ! to access words (four bytes long), the $ for strings and | for floating point values (five bytes long). They are all used in the same way by prefixing a pointer. For example, to set the first byte in a block to the value 42, use the statement:
?pointer% = 42
To access the word 32 bytes into the block, use:
!(pointer%+32) = 42
The ? and ! operators have a shorter form which is more concise. The example above could be written:
pointer%!32 = 42
Once a pointer has been wrapped with an indirection operator it behaves just like a variable in all contexts. The example programs on the MegaDisk show how to use these operators.
The major advantage of using the heap manager over the Basic DIM statement is that once claimed the blocks can be extended - shrinking the block is extending it by a negative amount.
To do this, you use reason code 4. For example, to extend the block pointed to by block% by 1k, you should use a call like:
SYS "OS Heap",4,heap%,block%,1024 TO ,,block%
To shrink it by 1k, you would use:
SYS "OS_Heap",4,heap%,block%,-1024 TO ,,block%
When you are shrinking a block, the pointer will change to -1 if the block is shrunk to 0 or less. If it is possible that this may happen in your program you must check for this case, otherwise you will crash the computer when you access the block.
The calls shown above will call the error handler if it fails. The version which does not call the error handler is more complex as there's no indication that it failed in the returned parameters.
However, you can test for an error with an X form SWI by examining the processor flags. These can be returned in a variable by Basic after a SYS statement.
For this OS_Heap call, you could use:
SYS "XOS_Heap",4,heap%,block%,1024 TO ,,block% ;flags% IF (flags% AND 1)<>1 THEN REM handle the error here ENDIF
This code works by testing to see if the V flag (overflow - used to signal errors on return from X form SWIs) is set. It is returned in bit 0 of flags% in the above command.
When a block is extended, its location may change if the heap manager has to move the block within the heap when extending it, so you must always update the pointer.
The three examples above all update the pointer. If you extend blocks in your program relocatable data should not be stored in them, for example offsets to other blocks.
This is one of the simplest calls. The only time it will fail is when you've passed an incorrect pointer. It uses reason code 3, so to free the block pointed to by block%:
SYS "OS_Heap",3,heap%,block%
The heap manager has other calls to get information on the heap and to change the size of the heap. These are useful to more advanced programmers. You can find out how to use these calls in the PRMs.
There are programs on the MegaDisk which demonstrate the use of the heap manager. Example1 initialises a heap, claims a block from it, writes some data to it and reads it out again and then frees the block. Example2 changes the size of the block and shows how to store a string and a floating point number.
As a more useful demonstration of the heap manager, I've written a short library called WIMPheap for use with multitasking programs. You can use it in your own programs.
It uses the heap manager to Waintain a heap above the Basic workspace which will extend and contract as necessary. It demonstrates some of the more advanced calls of the heap manager. Read the file WHeapUse for details on how to use it in your own programs.
The application WHeapTest is a very basic application which uses the library and when run it places an icon on the iconbar then, every second, either claims, extends or frees a block at random until you quit it by clicking on its icon with Menu.
If you watch the Task Manager task display while it is running, you'll see its slot growing and shrinking.
Click here to download the example files
| Source: | Acorn Computing December 1993 |
| Publication: | Acorn Computing |
| Contributor: | Ben Summers |