ARM Club 1/ARM_CLUB_CD.iso/contents/apps/program/u/wimpextend/Number/Heap

Text File | 1993-05-02 | 18.2 KB | 594 lines

Heap memory manager
===================

WimpExtension's heap manager is one of the module's most powerful, useful,
and - unavoidably - complicated features. This document is provided to
explain more about what a relocatable heap is, and how to use it.

Programming examples in this document are given in BASIC, because practically
everyone knows how to use it.

This document assumes that you know how to program in the RISC OS Wimp, and
that you understand terms such as "WimpSlot" (read the chapter "The Window
Manager" in the PRMs if you don't).

Read the "SWIs" and "Manual" files for a brief description of the parameters
for the SWI WimpExt_Heap.


NB  This document is in two sections. The first section is relatively simple
--  and tells you all you will probably need to know about using the heap
    manager. The second section explains the advanced features of the heap
    manager. BE WARNED; this section is not simple. But, most of you won't
    need to read it, so if you find it confusing, ignore it.



Section 1
=========



Why do I need a heap?
---------------------

Any program which uses more than one block of memory which changes size needs
a heap manager. For example, Edit and Paint need a heap manager, because they
can have several files loaded at once, all of which can be changing size at
any time. The files are loaded into memory "blocks", which are provided by
the heap manager.



Why use a relocatable heap?
---------------------------

RISC OS provides a non-relocatable heap manager. This means that the memory
blocks are fixed in memory, and don't move about. The problem with this is
that it gets very wasteful on memory when you have finished using the block.
Say you loaded three files into a text editor:

  /--------\ Highest memory address
  | File 3 |
  |        |
  |--------|
  | File 2 |
  |        |
  |        |
  |--------|
  | File 1 |
  \--------/ Lowest memory address

This is fine, no problems so far. However, suppose the user decided to close
the file "File 2":

  /--------\ Highest memory address
  | File 3 |
  |        |
  |--------|
  | unused |
  |        |
  |        |
  |--------|
  | File 1 |
  \--------/ Lowest memory address

The block of memory in the middle is now unused, and is wasting space. A
non-relocatable heap manager can't do anything about this. Another example is
if the user adds something to File 2, making it longer. File 2 will no longer
fit in its original block - if you extended it then it would overwrite
File 3. Therefore the heap manager has to copy the whole file up in memory,
as shown in the diagram:

  /--------\ Highest memory address
  | File 2 |
  |        |
  |        |
  |        |
  |--------|
  | File 3 |
  |        |
  |--------|
  | unused |
  |        |
  |        |
  |--------|
  | File 1 |
  \--------/ Lowest memory address

WimpExtension provides a relocatable heap manager, however. This means that
the heap manager is allowed to move the blocks about, to try and reduce the
amount of wasted memory. In the situation above, for example, WimpExtension
would move File 2 and File 3 down in memory, like so:

  /--------\ Highest memory address
  | File 2 |
  |        |
  |        |
  |        |
  |--------|
  | File 3 |
  |        |
  |--------|
  | File 1 |
  \--------/ Lowest memory address

As you can see, this can save a lot of memory.



Anchors
-------

The only disadvantage of a reloctable heap is due to the fact that it IS
relocatable - the blocks of memory aren't fixed and may move about. A
question which immediately arises is "How do I find my memory block?" - if
the block may have moved, how do you find it?

The answer is by using an "anchor". An anchor is a word in memory. The
contents of this word is always a pointer to the start of the block. ie:

                      /-------\
                      |       |
  /--------\          |       |
  | anchor |--------->| block |
  \--------/          \-------/

The anchor always stays fixed in the same place in memory, so you always know
where to find it. So, to find the location of your block, you would use:

  block%=!anchor% : REM block% now points to the first byte in the block

The anchors are stored all together at the beginning of the heap.



Size of blocks
--------------

The word before the start of any block contains the size of the block in
bytes. So to find the size of a block, you would use:

  size%=!(block%-4)

or:

  size%=!( (!anchor%) -4)

(because block%=!anchor%).

Due to the way the heap manager works, the size of a block is always four
plus a multiple of eight (ie. 12, 20, 28, etc.). If you ask WimpExtension to
make a block with a size which isn't four plus a multiple of eight, then the
size will be rounded up by between one and seven bytes, to take it to the
next largest acceptable size.



Initialising the heap
---------------------

Before you can use any of the heap operations, you must initialise the heap.
This requires two parameters - the number of anchors to create initially, and
the address in memory of the base of the heap.

The anchors are stored all together at the beginning of the heap. Because you
need one anchor for every block in use, the number of anchors is effectively
the maximum number of blocks you can have in use at any one time. You can
create more anchors later, but it is best to create enough now, and then you
don't have to worry about it later. Remember that anchors do take memory
though, so don't go wild.

For example:

  SYS "WimpExt_Heap",0,base%,anchors%

Note that a heap which is empty (ie. no blocks are in use) takes absolutely
no memory at all.



Allocating blocks
-----------------

Whenever you ask WimpExtension to make you a new block (called "allocating" a
block), it gives you a pointer to the anchor for that block. You must store
the pointer to the anchor, NOT the pointer to the block, because the anchor
will never move, but the block may do. For example, to ask WimpExtension for
a block "size%" bytes long, you would use:

  SYS "WimpExt_Heap",2,,size% TO ,anchor%

If WimpExtension cannot create the block, because there is not enough free
memory, then the anchor returned will be zero. You need to check for this
before writing anything into the block. eg:

  SYS "WimpExt_Heap",2,,size% TO ,anchor%
  IF anchor%=0 THEN ERROR 1,"Not enough free memory"



Freeing blocks
--------------

When you have finished using a block, you use the "Free block" call to tell
WimpExtension that you don't need the block any more, and the memory it takes
up can be re-used. eg:

  SYS "WimpExt_Heap",3,anchor%

or:

  SYS "WimpExt_Heap",3,block%

The block will be added to WimpExtension's list of free blocks.



Reallocating blocks
-------------------

Sometimes you will want to re-size a block - this is called "reallocating"
the block. WimpExtension allows you to increase or decrease the size of any
block at any time. eg:

  SYS "WimpExt_Heap",4,block%,new_size% TO ,flag%

or:

  SYS "WimpExt_Heap",4,anchor%,new_size% TO ,flag%

If the flag is zero on exit then the re-size failed because there wasn't
enough free memory.

Note that this call may cause the specified block to move in memory. Only the
specific block that you are re-sizing can move, though - all the other blocks
will stay where they are.



Garbarge collection
-------------------

"Garbage collection" is the whole point of the relocatable heap. This is the
process of shuffling the blocks about in memory, so that no memory is wasted.
For example, if the heap was in the following state:

  /---------\ Highest memory address
  | block 2 |
  |         |
  |---------|
  |  free   |
  |         |
  |         |
  |---------|
  | block 1 |
  \---------/ Lowest memory address

then performing garbage collection would shuffle the blocks as follows:

  /---------\ Highest memory address
  | block 2 |
  |         |
  |---------|
  | block 1 |
  \---------/ Lowest memory address

This then allows WimpExtension to decrease your task's WimpSlot, thus making
this memory available to any other programs which might need it.

Two garbage collection calls are provided; the Tidy call:

  SYS "WimpExt_Heap",5

and the Compact call:

  SYS "WimpExt_Heap",6

The Tidy call just tidies the heap a little bit - the heap won't necessarily
immediately be shuffled into the ideal position, but the call is usually
quite fast. This call is intended to be called just before you call
Wimp_Poll. If you set bit 3 of R2 when you called WimpExt_Initialise, then
the heap will be automatically Tidied once a second, in WimpExt_PrePoll. Most
of the time, you can just set this bit, and then forget all about garbage
collection - it will all be handled for you.

The Compact call tidies the heap completely - the heap will immediately be
shuffled into the ideal position. This call is often slower than the Tidy
call, however, as it does more work.



How often should I tidy the heap?
---------------------------------

How often you tidy the heap depends on the average size of the blocks your
program uses. If your program uses lots of little blocks then you should tidy
the heap quite often. If it uses a smaller number of larger blocks then you
should tidy it less often.

For a text editor, for example, the once-a-second tidy provided automatically
should be fine. For something which uses smaller blocks, you should probably
tidy the heap more often.



Finding the anchor of a block
-----------------------------

If you have a pointer to a block, and you want to locate the block's anchor,
then a call is provided to do this:

  SYS "WimpExt_Heap",7,block% TO ,anchor%

An error is produced if block% is not a valid pointer to the start of a
block.



Fixing blocks
-------------

Sometimes you may want to temporarily 'fix' the heap. This makes it so that
all the blocks are fixed and cannot move. This is useful if you need to rely
on a block staying put at the same position in memory for a while.

To fix the heap, you would use:

  SYS "WimpExt_Heap",8

and to unfix it you would use:

  SYS "WimpExt_Heap",10

Note that WimpExtension keeps a count of the number of times you haved fixed
the heap, and only unfixes the heap when you tell it to the same number of
times. ie:

  SYS "WimpExt_Heap",8
  SYS "WimpExt_Heap",8
  SYS "WimpExt_Heap",10

would leave the heap fixed. The following, however, would leave the heap
unfixed, as the number of "unfixings" matches the number of "fixings":

  SYS "WimpExt_Heap",8
  SYS "WimpExt_Heap",8
  SYS "WimpExt_Heap",10
  SYS "WimpExt_Heap",10

You can force WimpExtension to unfix the heap straight away, regardless of
the number of times it has been fixed, using the following call:

  SYS "WimpExt_Heap",9

ie. The following would leave the heap unfixed:

  SYS "WimpExt_Heap",8
  SYS "WimpExt_Heap",8
  SYS "WimpExt_Heap",9



Creating more anchors
---------------------

WimpExtension allows you to create more anchors, even while the heap is in
use. Note that this call has to move the entire heap up in memory, so it can
be quite slow. For example:

  SYS "WimpExt_Heap",11,add%

"add%" extra anchors will be created. All the blocks will be moved.

WimpExtension also provides a call to allocate a block, automatically
creating more anchors if you've run out:

  SYS "WimpExt_Heap",12,,size% TO ,anchor%


Freeing all blocks
------------------

WimpExtension provides a call to free all the blocks in the heap:

  SYS "WimpExt_Heap",13

Every single allocated block will be freed, and all the memory released.



Describing the heap
-------------------

WimpExtension provides a call which provides various bits of information
about the heap:

  SYS "WimpExt_Heap",1 TO ,,largest%,free%,heapsize%,anchors%,blocks%

  largest%  : The size of the largest continuous area of memory in the heap
  free%     : The total amount of memory free in the heap
  heapsize% : The total amount of memory used by the heap
  anchors%  : The number of anchors which have been created
  blocks%   : The number of blocks which are currently allocated


-----------------------------------------------------------------------------
Here ends the simple part of this file.

From here on it is far more complicated, but you almost certainly won't need
to read it. So if you get confused, don't worry.


Section 2
=========

OK, tremble in fear, mortals, because if you thought that the last bit was
complicated, you're just gonna LOVE this. Now we get to talk about multiple
heaps, heaps within heaps, and heaps that can move about in memory (called
'shifting' heaps).

WimpExtension's heap manager supports multiple heaps. ie. You can have more
than one heap going at once. Each heap is treated as totally separate from
all the other heaps.

It also supports 'shifting' heaps, which can move about in memory. The
standard heap is NOT a shifting heap, because although the blocks themselves
can move about, the heap itself always stays in the same place.

The extra considerations involved when using shifting heaps are NOT trivial,
and are liable to cause severe headaches if you try to think about them for
too long. (That's what happens to me, anyway.)

Different heaps are referred to by their 'heap pointers'. A heap pointer
points to a block of memory set out as follows:

  +00  hp_heap       offset of heap data area
  +04  hp_free       offset of first free block, or 0 if no free blocks
  +08  hp_anchors    offset of first anchor
  +0C  hp_heapsize   total size of heap in bytes
  +10  hp_heapfix    'fixed' counter
  +14  hp_tidytime   monotonic time of last Tidy call
  +18  hp_heaptidy   tidy flag; 0 if heap is fully tidied, non-zero otherwise
  +1C  hp_created    created flag; 0 if heap is uncreated, non-zero otherwise
  +20  hp_base       pointer to base of heap memory
  +24  hp_pagesize   'page' size
  +28  hp_setsize    pointer to routine to change size of heap
  +2C  hp_numblocks  number of blocks claimed
  +30  hp_rootptr    pointer to pointer to base of heap memory
  +34  hp_misc       depends on what sort of heap this is
All offsets are from hp_base.

The following things are defined about the heap:
  * hp_base must be a multiple of 8
  * hp_free need not contain a sensible value if hp_created is zero
  * the anchors are in the area hp_anchors to hp_heap
  * each anchor is 8 bytes, 4 bytes pointer to block then 4 bytes task handle
  * hp_heapsize must be a multiple of 8
  * hp_heap must be a multiple of 8
  * hp_anchors must be a multiple of 8



hp_rootptr and hp_base
----------------------

hp_rootptr points to a pointer to the base of the heap. This must always be
where the heap actually is in memory. hp_base contains the position of the
heap in memory last time the heap manager looked. These addresses are used by
the relocation routine (see below) to update the anchors if the heap moves.
hp_rootptr does not provide a sufficient level of indirection if the heap is
nested inside a shifting heap, and you will have to update this value
manually if this is the case.



hp_setsize and hp_pagesize
--------------------------

hp_setsize is a routine that is called when WimpExtension wants to change the
size of the heap. It is entered in SVC mode as follows:
 R0  = size required
 R10 = heap pointer
 R13 = supervisor stack
 R14 = return address
Exit:
 R0  = 0 indicates failure, non-zero indicates success
 all other registers preserved

It should NOT return errors, just indicate success or failure with R0 as
shown. The routine should update hp_heapsize as necessary, and the base of
the heap as indicated by hp_rootptr if the heap has moved. It should NOT
change hp_base, as this is needed to relocate the anchors.

hp_pagesize is used to decide whether or not it is worth increasing or
decreasing the heap size. The heap size is always decreased or increased in
multiples of this value.



hp_misc
-------

hp_misc's value depends on what sort of heap this is. For the standard heap,
it is reserved and its value is undefined. For a heap within a heap, created
for you by WimpExtension, it contains the heap pointer of the parent heap. If
the heap was created by you, then you can use it for whatever purpose you
want.



Selecting a different heap
--------------------------

To select a different heap, use call 14:

  SYS "WimpExt_Heap",14,new_heap% TO old_heap%,new_heap%

new_heap% can take one of several values:
  -1     don't change the selected heap
  +1     select the standard heap
  other  new_heap% is a heap pointer; select this heap

On exit, old_heap% and new_heap% contain the heap pointers of the previous
and current heaps respectively, or 0 if no heap was/is selected.

After this call, all other WimpExt_Heap calls act on the selected heap.



Relocating the heap
-------------------

If you have moved the heap about in memory, then use the Relocate call to
update the anchors:

  SYS "WimpExt_Heap",15

This call is used automatically after WimpExtension calls hp_setsize, and on
entry to any of the other WimpExt_Heap calls, so you will only need to use it
if you move the heap at some other time and then need to reference an anchor
before using another WimpExt_Heap call.



Creating a heap within another heap
-----------------------------------

WimpExtension supports another call to create heaps. This one creates a heap
inside a heap block in another heap. It is used as follows:

  SYS "WimpExt_Heap",16,heapptr%,anchors%

heapptr% points to a block of memory which is filled in by the call with a
heap description block. anchors% is the number of anchors to create.



Creating custom heaps
---------------------

To create a heap to your own specification, simply make a heap description
block, and then select it as the current heap. If you set hp_created to zero,
then you won't have to set up anything in the heap memory itself.



Considerations for shifting heaps
---------------------------------

Shifting heaps are fun. Not only can all the blocks move, but the heap itself
can move as well. This means that the anchors can move. So you have to store
the offset of the anchor in the heap, rather than a pointer to the anchor
itself, and then calculate the address of the anchor when you need it by
referencing hp_base.

Basically, nothing at all in a shifting heap is fixed, EXCEPT the heap
pointer. BUT the heap pointer doesn't have to be fixed, you can move it
around as long as you re-select the heap...

When you start using shifting heaps inside shifting heaps, the excitement
knows no bounds... A shifting heap inside a block in a shifting heap inside
a block in a shifting heap inside a block in a shifting heap is actually
quite tricky to keep track of ;-).