DynamicHeap Class Reference

List of all members.

Public Member Functions
	DynamicHeap ()
	Sets up the heap variables, ready for Init() to be called.
BOOL	Init ()
	Initialise the heap object. This gets a chunk of memory from the operating system, which it will use to satsify allocation requests.
	~DynamicHeap ()
	Deallocates any memory used by this heap object. In debug builds it checks the heap for objects which have not been deallocated, or for heap corruption, and complains if it finds any.
MHANDLE	ClaimBlock (size_t Size)
	Allocates a block of 'size' bytes from the free pool, and obtains a handle for it. Blocks which are zero bytes long are permitted, but blocks must be word-sized (i.e. a multiple of 4 bytes in size).
BOOL	ReleaseBlock (MHANDLE Handle)
	Given a handle to a memory block, releases this memory block from use, and returns the block to the free pool. Subsequent accesses via this handle or via the block's address cause undefined behaviour.
BOOL	IncreaseBlock (MHANDLE Handle, UINT32 NumBytes)
	See IncreaseBlock for a full description.
BOOL	DecreaseBlock (MHANDLE Handle, UINT32 NumBytes)
	See DecreaseBlock for a full description.

---

Detailed Description

Technical Notes ~~~~~~~~~~~~~~~

General ~~~~~~~

At present, this module obtains a chunk of memory from Windows' Global heap, and uses this to satisfy client memory requests. The handle to this memory is resolved to a physical address, and the block is locked for the duration of the memory manager's use (i.e. until DeinitMemory() is called, when it is unlocked and returned to the global heap). The 'FreePoolPtr' variable points to the base of the block. Under 16bit Windows, the block is limited to 64k in size.

The handles used are managed by another module - the handle manager (see winoil.{h,cpp}).

In order to cope with 'heavy' blocks (see ClaimBlock), two heaps are maintained. One is for heavy blocks, the other for normal blocks. This is the ideal solution under Windows, because we use a GlobalAlloc call for each, so when we need to add a new heavy block, we don't need to move all the non-heavy objects to do so. The OS will cope with it by remapping the memory controller - i.e. we don't move any memory - this is *good*.

Allocated blocks of memory are not always contiguous; there may be holes (unused blocks) in the heap.

The first word of a memory block contains its size in bytes, and a flag to indicate whether or not it is a hole (i.e. not in use). Therefore it is possible to step through the heap simply by reading the size of each block and using that to move on to the next block. A size of 0 indicates that the block containing the free space at the end of the heap has been reached. This block is also marked as _not_ being a hole - this (somewhat counter-intuitively) makes certain operations on the heap simpler.

The 'FreeOffset' variable is an offset to the start of any remaining memory in the 64k block (hence it is 0 initially - all memory is available). This memory does not include holes. When a request for memory fails, the holes are examined to see if one of them can accomodate the request. If no holes are big enough, the manager incrementally removes the holes until it can be satisfied, or until there are no more holes to free. ("When Alexander saw the size of his allocation, he wept, for there were no more holes to free...")

The memory manager uses the principle of lazy evaluation - expensive operations are defered until they are absolutely necessary, or when the CPU would otherwise be idle. This minimises response times for the user.

Holes ~~~~~

Holes are intended to be transient - the idea is that when releasing a block it is simply marked as released. Then, when the application receives idle events, it should call TidyMemory(), which will move one block at a time to clean up the holes.

The upshot of all this is that when large allocations/deallocations are taking place, the user doesn't notice much (if any) degradation in response time, because the memory is not being moved. However, when the user next stops to think for a few seconds, the application will be 'covertly' tidying up its memory holes while the CPU is idle. Only one block is tidied at once so that control can be returned to the user quickly (when they stop thinking and start clicking).

The function RemoveBlockGaps() is also provided to force all holes to be purged from the heap (which may be desirable for events such as removing a document from memory, and so on).

When a block is released by its owner, the associated handle is also freed. The list of holes is maintained using the blocks themselves - as each block (either used or unused) has its size contained in the first word of its memory, the blocks effectively form a linked list which can be efficiently scanned for holes. Holes are not joined together unless this is necessary (usually when the heap is being compacted).

When tidying the memory, it is guaranteed (by calling JoinHoles() before doing anything else) that no two holes will be adjacent - any such holes will have been joined into one. Therefore when a hole is found, a block that is in use will be sitting above it in memory. These two blocks (the hole and the block in use) are then swapped around, so that the hole is above the used block, and the used block now starts where the hole used to. Any handles into the used block are updated using the handle manager. There are, of course, no handles into the hole as it is not a valid memory block anyway. The hole's first word is then set to contain its size, as before. (NB only the contents of the block in use are moved - the hole's contents are not moved because they are undefined anyway, so it would be unnecessary). Finally, if there is a hole directly above this hole, the two are joined together.

For example: ------------ Dynamic Heap (X = Block In Use, . = Hole)

+-------+------+------------+-------+------+-----------------+ Before tidying: |XXXXXXX|......|XXXXXXXXXXXX|.......|XXXXXX| Free Space | +-------+------+------------+-------+------+-----------------+

+-------+------------+--------------+------+-----------------+ After tidying: |XXXXXXX|XXXXXXXXXXXX|..............|XXXXXX| Free Space | +-------+------------+--------------+------+-----------------+

No special algorithms for reclaiming/joining blocks are required (as they would be in a normal malloc-style heap), because all the blocks in the heap can be moved at will. Therefore optimising allocations for FIFO schemes, buddy schemes etc., is pointless. Whenever the holes cause problems for allocation requests, they are gradually removed to free up memory - this is not possible for a static heap manager!

Inter-block gaps ~~~~~~~~~~~~~~~~

The 'EndOfBlockGap' is used to resolve the problem of not knowing whether an address refers to the end of one block or the start of the next (according to Jim). Blocks are simply separated by a 'dead zone' of 4 bytes.

Since the introduction of BlockHeader fields, I think this EndOfBlockGap can safely be dropped...must try it sometime.

Resizing blocks ~~~~~~~~~~~~~~~

Blocks can be either increased or decreased in size. There are two functions which perform simple resizing of blocks: IncreaseBlock() and DecreaseBlock(). They simply alter the size of the block's allocation, and do not move any memory. Two other functions, InsertMemory() and RemoveMemory(), are provided for inserting memory into the middle of a block, or removing it from the middle of a block.

Strategies used for resizing blocks ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

When making blocks smaller, the excess is simply made into a hole for removal later on.

When increasing the size of the block, if a large enough hole exists above the block being resized, then it is used to expand the block into, and the hole is decreased in size accordingly. Note that no other blocks are moved in this case.

(Future optimisation: at this point, the manager should try to find any hole big enough to hold the block, and reposition the block into that).

If the hole isn't big enough to accommodate the request, then the manager compacts the heap and tries again. If there is still not enough room, then the heap itself is resized - if not enough memory is available, the request fails.

SplitBlock() ~~~~~~~~~~~~

NB. SplitBlock() has been replaced by the other function calls listed above, and should no longer be used. Please change any existing code that stil uses it. The function will be removed in the future.

SplitBlock() resizes blocks of memory. It can make blocks bigger or smaller.

Releasing memory ~~~~~~~~~~~~~~~~

At present, this module never returns memory to the OS until DeinitMemory() is called. In future, TidyMemory should return memory once the free memory in the heap reaches a certain threshold.

The Invaders - Epilogue ~~~~~~~~~~~~~~~~~~~~~~~

The addition of holes complicates this module somewhat, but not unduly. The worst affected functions are SplitBlock() and ClaimBlock(), which run rings around holes in order to do their job. However, what they're trying to do is avoid redundant memory transfers which can be VERY expensive, and hence the memory manager is faster at its job, which is the point of the exercise (TANSTAAFL).

Definition at line 303 of file cammemory.cpp.

---

Constructor & Destructor Documentation

DynamicHeap::DynamicHeap (   )

Sets up the heap variables, ready for Init() to be called. Author: Tim_Browse (Xara Group Ltd) <camelotdev@xara.com> Date: 09/02/94 See also: DynamicHeap::Init; DynamicHeap::~DynamicHeap Definition at line 340 of file cammemory.cpp. { }

DynamicHeap::~DynamicHeap (   )

Deallocates any memory used by this heap object. In debug builds it checks the heap for objects which have not been deallocated, or for heap corruption, and complains if it finds any. Author: Tim_Browse (Xara Group Ltd) <camelotdev@xara.com> Date: 09/02/94 See also: DynamicHeap::Init; DynamicHeap::DynamicHeap; InitMemory; DeinitMemory Definition at line 379 of file cammemory.cpp. { }

---

Member Function Documentation

MHANDLE DynamicHeap::ClaimBlock (  size_t  Size  )

Allocates a block of 'size' bytes from the free pool, and obtains a handle for it. Blocks which are zero bytes long are permitted, but blocks must be word-sized (i.e. a multiple of 4 bytes in size). Author: Tim_Browse (Xara Group Ltd) <camelotdev@xara.com> Date: 26/04/93 Parameters: Size,:  The size in bytes of the block being requested [INPUTS] Returns: The handle that refers to the newly allocated block. Definition at line 399 of file cammemory.cpp. { #ifdef RALPH RalphCriticalSection RalphCS; #endif // Get the memory ADDR pNewBlock = (ADDR) CCMalloc(Size); // Check for NULL if (pNewBlock==NULL) return BAD_MHANDLE; // Attempt to get a handle for a new block. MHANDLE NewHandle = ClaimHandle(pNewBlock); // if we did not get the handle, throw away the allocation if (NewHandle==BAD_MHANDLE) { TRACE( wxT("ClaimBlock - got the memory, but not a handle\n") ); CCFree(pNewBlock); pNewBlock = NULL; } // return the handle return NewHandle; }

BOOL DynamicHeap::DecreaseBlock (  MHANDLE  Handle, UINT32  NumBytes )

See DecreaseBlock for a full description. Author: Tim_Browse (Xara Group Ltd) <camelotdev@xara.com> Date: 06/12/93 Parameters: Handle  - the handle of the block to resize [INPUTS] NumBytes - the number of bytes to remove from this block's allocation (must be word-sized, and >=12 bytes). Returns: TRUE if the resize worked, FALSE if it failed. See also: DecreaseBlock; IncreaseBlock; InsertMemory; RemoveMemory; DescribeHandle Definition at line 541 of file cammemory.cpp. { #ifdef RALPH RalphCriticalSection RalphCS; #endif // Get details for this handle ADDR Address = DescribeHandle(Handle); // See if it is bad if (Address == BAD_MHANDLE) { // Invalid handle - return error TRACE( wxT("IncreaseBlock: Handle is invalid\n") ); return FALSE; } // Find out how big the old block was size_t Size = CCGetBlockSize(Address); Size -= NumBytes; // Reallocate the block to the new size ADDR pNewBlock = (ADDR) CCRealloc(Address, Size); if (pNewBlock==NULL) { TRACE( wxT("realloc failed in IncreaseBlock\n") ); return FALSE; } // Update the handle AlterHandle(Handle, pNewBlock); return TRUE; }

BOOL DynamicHeap::IncreaseBlock (  MHANDLE  Handle, UINT32  NumBytes )

See IncreaseBlock for a full description. Author: Tim_Browse (Xara Group Ltd) <camelotdev@xara.com> Date: 06/12/93 Parameters: Handle  - the handle of the block to resize [INPUTS] NumBytes - the number of bytes to add to this block's allocation (must be word-sized, and >=12 bytes). Returns: TRUE if the resize worked, FALSE if it failed. See also: IncreaseBlock; DecreaseBlock; InsertMemory; RemoveMemory; DescribeHandle Definition at line 490 of file cammemory.cpp. { #ifdef RALPH RalphCriticalSection RalphCS; #endif // Get details for this handle ADDR Address = DescribeHandle(Handle); // See if it is bad if (Address == BAD_MHANDLE) { // Invalid handle - return error TRACE( wxT("IncreaseBlock: Handle is invalid\n") ); return FALSE; } // Find out how big the old block was size_t Size = CCGetBlockSize(Address); Size += NumBytes; // Reallocate the block to the new size ADDR pNewBlock = (ADDR)CCRealloc(Address, Size); if( pNewBlock==NULL ) { TRACE( wxT("realloc failed in IncreaseBlock\n") ); return FALSE; } // Update the handle AlterHandle( Handle, pNewBlock ); return TRUE; }

BOOL DynamicHeap::Init (  void   )

Initialise the heap object. This gets a chunk of memory from the operating system, which it will use to satsify allocation requests. Author: Tim_Browse (Xara Group Ltd) <camelotdev@xara.com> Date: 09/02/94 Returns: TRUE if the initialisation was successful, FALSE if not (e.g. couldn't get any memory). Errors: If unable to claim memory. Definition at line 358 of file cammemory.cpp. { // Everything went ok return TRUE; }

BOOL DynamicHeap::ReleaseBlock (  MHANDLE  Handle  )

Given a handle to a memory block, releases this memory block from use, and returns the block to the free pool. Subsequent accesses via this handle or via the block's address cause undefined behaviour. Author: Tim_Browse (Xara Group Ltd) <camelotdev@xara.com> Date: 26/4/93 Parameters: Handle,:  The handle of the block to be released. [INPUTS] Returns: TRUE if the handle was valid Definition at line 445 of file cammemory.cpp. { #ifdef RALPH RalphCriticalSection RalphCS; #endif // Get details for this handle ADDR Address = DescribeHandle(Handle); // See if it was bad if (Address == BAD_MHANDLE) { // Invalid handle - return error TRACE( wxT("ReleaseBlock: Handle is invalid\n") ); return FALSE; } // It was OK, so free the memory CCFree(Address); // And release the handle or it never will be ReleaseHandle(Handle); return TRUE; }

---

The documentation for this class was generated from the following file:

• wxOil/cammemory.cpp (r1785/r1492)

---