ARM Club 3

home *** CD-ROM | disk | FTP | other *** search

/ ARM Club 3 / TheARMClub_PDCD3.iso / hensa / programming / b121_1 / Heap < prev next >

Wrap

Text File | 1993-08-16 | 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 ;-).