rob@idacom.uucp (Rob Chapman) (09/17/90)
Here's last Thursdays FUG [Forth Users Group] handout (unedited):
Dynamic memory management
A Simple Heap
ptForth and botForth use a simple memory management system: DP or dp .
These are variables which point to the division between used and free
memory. The used memory is, of course, the Forth dictionary.
___________ high memory
| |
| |
| Free |
| |
DP or dp --->|-----------| \
| | |
| Used | > Forth dictionary
| | |
|___________| low memory /
The dynamics of these variables are controlled by ALLOT and FORGET and they
may be read by HERE. Also, since DP is a globally known variable and the
model is well understood, it lends itself to abstractions like the the Test
Manager where DP is pointed into a separate dictionary space.
Managing the Free Memory
If Free memory were were infinite, this would not be necessary (ie. if it
were truly "free"). As life has it though, Free memory is bound. But it
can be made to appear infinite by managing it over time (ie. give it a
life).
A Simple Aproach
( ==== Managing the upper limit ==== )
( Usage: #limit 100 - CONSTANT #limit ( grab 100 bytes of Free memory )
RAMEND CONSTANT #limit ( equate a constant to the top of Free memory )
This approach, allows for a second source of memory allotment separate from
the dictionary. It is useful for data space which does not have to reside
on disk. It makes use of the same destructor, FORGET, as the DP management
scheme. It is elegant and simple but it is dynamic only during time of
Interpretation.
Continuous Memory Management
Chunks are ALLOCATEd from DICTLIMIT. DICTLIMIT points to the lowest chunk
in Free memory (or at high memory when all memory is FREEd). The first 4
bytes of each chunk contains a pointer to the next chunk higher up in
memory.
___________ high memory
| | |_____________________
|ALLOCATE | ALLOCATEd |\ | |
\|/ | | \ | data |
DICTLIMIT -->|-----------| \ | area |
| Free | \ |___________|
DP --------->|-----------| \| pointer |
/|\ | | -----------
|ALLOT | ALLOTed |
| | |
| |___________| low memory
: ALLOCATE ( n -- a )
DICTLIMIT @ DUP >R SWAP - DUP 4 - DUP DICTLIMIT ! R> SWAP ! ;
: FREE ( a -- ) 4 - DICTLIMIT BEGIN 2DUP @ XOR WHILE @ REPEAT
SWAP @ SWAP ! ;
ALLOCATE moves DICTLIMIT down, n 4 + bytes, and stores the previous value
of DICTLIMIT at the current value. The address returned for the chunk is
DICTLIMIT @ 4 + since the pointer sits at DICTLIMIT @.
FREE looks thru the link list of ALLOCATEd chunks for the chunk which points
the the one to be freed. Then, the previous chunk is set, to point to, the
one that the freed one is pointing to. Essentially, it is merged with a
chunk of memory which is still in use. Once all chunks have been returned,
DICTLIMIT will again point to high memory.
__\ ___________
| /| |
| | FREEd |
| |-----------|
| | Used |
| |___________|
---|___________|/__
| |\ |
| FREEd | |
|-----------| |
| Used | |
|___________| |
DICTLIMIT _____\ |___________|---
/
This management strategy meets the following criteria:
1. Coalescence of freed memory
2. Recovery of DICTLIMIT
3. Any size available
However, this method is not efficient since it does not reuse freed chunks
of memory. Depending on the nature of the dynamics, this could lead to a
situation where no more Free memory could be ALLOCATEd.
Managing More Dynamically
Reusing the FREEd chunks, is done by keeping a separate list of these
chunks and searching it inside of ALLOCATE. Coalescence is performed on
the freed chunks. Each free chunk would have its size for quicker checking.
: REUSE? ( n -- n | a \ f ) ( search thru free list )
: ALLOCATE ( n -- a ) REUSE? IF EXIT ENDIF
DICTLIMIT @ DUP >R SWAP - DUP 4 - DUP DICTLIMIT ! R> SWAP ! ;
: WITHIN ( low \ mid \ high -- f ) 2DUP U< >R U< R> AND ;
: INSERT ( a \ entry -- ) 2DUP @ SWAP ! SWAP ! ;
: COALESCE ( a \ entry -- ) ...
: FREE ( a -- ) DUP FREE free BEGIN 2DUP @ U> WHILE @ REPEAT
2DUP @ OVER @ WITHIN IF COALESCE ELSE INSERT ENDIF ;
Managing Several Domains of Memory
In the most general case, it may be required to manage several descrete
chunks of memory. These would appear in the free list as uncoalesced
chunks ordered by address.
ANS Forth Proposed Wordset (don't quote me on this)
ALLOCATE ( n -- a ) allocate a chunk of memory and return the address or 0.
FREE ( a -- ) return allocated chunk of memory.
AVAILABLE ( -- n ) return the size of the largest contigous chunk.
RESIZE ( a \ n -- a \ f ) resize current block.