David is a technical editor for DDJ and the author of XLisp, XScheme, and the M&T Online conferencing system. He can be reached at DDJ, 501 Galveston Drive, Redwood City, CA 94063.
One of the problems that plagues programs that do a lot of runtime memory allocation is fragmentation. If a program allocates and deal-locates blocks of varying sizes, memory will tend to become fragmented. Eventually, an allocation request will fail, not because there isn't enough free memory, but because there isn't a large enough contiguous block of free memory to satisfy the request.
One solution to this problem is to move all of the blocks of memory that are in use to one end of the heap. This leaves all of the free space at the other end in one contiguous block. The obvious problem with this approach is that the program that allocated the memory still maintains pointers to the allocated blocks which become invalid as the blocks are moved.
The way both Windows 3 and the Macintosh operating system overcome this problem is to provide a way for programs to access allocated memory indirectly through "handles." A handle, rather than being a direct pointer to a block of allocated memory, is an indirect pointer. On the Macintosh, handles are actually pointers to pointers, whereas under Windows, they are 16-bit integer values that designate a pointer that is maintained in a table managed by the memory allocator. With handles, the memory manager is free to move around allocated blocks to free up contiguous space to satisfy an allocation request. It just needs to update the single pointer associated with the handle of each block of memory still in use.
The cost of this approach is that each time a program references data through a handle, an extra level of indirection is required. Usually, this isn't a major concern and doesn't impact performance much. The benefit is the elimination of memory fragmentation problems.
In this article, I present a simple handle-based memory manager. The package includes the include files (Listing One, page 66), C source ( Listing Two, page 66), makefile (Listing Three, page 151), and a test program (Listing Four, page 151). There are really only four entry points to this package. NewHeap( ) initializes a new heap. It takes two arguments: the initial number of handles and the size of the heap in bytes. Its counterpart is FreeHeap( ), which takes a heap allocated with NewHeap( ) and frees all of the memory associated with it. Then there is HeapAlloc( ) which allocates a block of memory from a heap and returns a handle to the block and HeapFree( ), which frees a block of memory allocated with HeapAlloc( ).
A handle is just a pointer to a pointer to a character (a Char **), so to refer to a block of memory through a handle, an extra * is required.
The heap is organized with the table of handles at its base and the memory available for allocation above that. Three variables control allocation. The variables base and top point to the base and top of the area available for allocation. The variable next points to top of the next block that will be returned by the allocator. Initially, it points to the same address as top. When it receives an allocation request, the allocator checks to see if next-base is greater than or equal to the amount requested. If it is, the allocator returns a block whose base is at next-base and sets next equal to that value. In this way, memory is allocated from the top of the heap toward the bottom.
When the allocator finds that there is not enough memory between base and next to satisfy a new allocation request, it compacts the heap by copying all of the blocks still in use toward the top of the heap, leaving all of the free space between base and next. The allocator then checks the free space between base and next again. If there is enough space, the variables are updated as described above and the new block is returned. If not, the allocation request fails.
Handles are allocated in a much simpler fashion. The table of handles is searched to find a handle that is not in use. If no free handles are available, the compactor is called and the base variable is moved up enough to provide space to allow the handle table to be expanded. Of course, this too could fail. If it does, the allocator returns NULL to indicate that the allocation request has failed.
_A SIMPLE HANDLE-BASED MEMORY MANAGER_ by David Betz[LISTING ONE]
<a name="0291_0005">
/* hmm.h - definitions for a simple handle based memory manager */
typedef char **HANDLE;
/* heap header structure */
typedef struct heaphdr {
int hh_nhandles; /* number of handles */
char *hh_next; /* next free location */
char *hh_base; /* base of heap memory */
char *hh_top; /* top of heap memory */
HANDLE hh_handles; /* base of handle array */
} HEAPHDR;
HEAPHDR *NewHeap(int,int);
void FreeHeap(HEAPHDR *);
HANDLE HeapAlloc(HEAPHDR *,int);
void HeapFree(HEAPHDR *,HANDLE);
<a name="0291_0006">
<a name="0291_0007">[LISTING TWO]<a name="0291_0007">
/* hmm.c - a simple handle based memory manager -- by David Betz */
#include <stdio.h>
#include "hmm.h"
/* number of handles to add when expanding the handle table */
#define HINC 32
/* block prefix structure */
typedef struct blockpfx {
HANDLE bp_handle; /* handle for this block */
} BLOCKPFX;
/* block suffix structure */
typedef struct blocksfx {
int bs_size; /* size of block */
} BLOCKSFX;
static HANDLE FindMemory(HEAPHDR *,HANDLE,int);
static HANDLE NewHandle(HEAPHDR *);
static HANDLE UnusedHandle(HEAPHDR *);
static void ExpandHandleTable(HEAPHDR *,int);
static void CompactHeap(HEAPHDR *);
/* NewHeap - allocate and initialize a new heap */
HEAPHDR *NewHeap(nhandles,nbytes)
int nhandles; /* initial number of handles */
int nbytes; /* initial number of free bytes */
{
char *malloc();
HEAPHDR *h;
int tsize;
HANDLE p;
tsize = nhandles * sizeof(char *);
if ((h = (HEAPHDR *)malloc(sizeof(HEAPHDR) + tsize + nbytes)) == NULL)
return (NULL);
h->hh_nhandles = nhandles;
h->hh_handles = p = (HANDLE)((char *)h + sizeof(HEAPHDR));
while (--nhandles >= 0) *p++ = NULL;
h->hh_base = (char *)h->hh_handles + tsize;
h->hh_top = h->hh_base + nbytes;
h->hh_next = h->hh_top;
return (h);
}
/* FreeHeap - free a heap allocated by NewHeap() */
void FreeHeap(h)
HEAPHDR *h; /* heap to free */
{
free(h);
}
/* HeapAlloc - allocate a block of memory from the heap */
HANDLE HeapAlloc(h,size)
HEAPHDR *h; /* the heap */
int size; /* size of block to allocate */
{
HANDLE p;
if ((p = NewHandle(h)) == NULL)
return (NULL);
return (FindMemory(h,p,size));
}
/* HeapFree - free a block of memory allocated by HeapAlloc() */
void HeapFree(h,p)
HEAPHDR *h; /* the heap */
HANDLE p; /* the handle to free */
{
BLOCKPFX *bp;
bp = (BLOCKPFX *)(*p - sizeof(BLOCKPFX));
bp->bp_handle = NULL;
*p = NULL;
}
static HANDLE NewHandle(h)
HEAPHDR *h; /* the heap */
{
HANDLE p;
if ((p = UnusedHandle(h)) == NULL)
ExpandHandleTable(h,HINC);
return (UnusedHandle(h));
}
static HANDLE UnusedHandle(h)
HEAPHDR *h; /* the heap */
{
HANDLE p;
int n;
for (p = h->hh_handles, n = h->hh_nhandles; --n >= 0; ++p)
if (*p == NULL)
return (p);
return (NULL);
}
static void ExpandHandleTable(h,n)
HEAPHDR *h; /* the heap */
int n; /* number of handles to add */
{
char *base;
HANDLE p;
CompactHeap(h);
base = h->hh_base + (n * sizeof(char *));
if (base <= h->hh_next) {
p = (HANDLE)h->hh_base;
h->hh_base = base;
h->hh_nhandles += n;
while (--n >= 0)
*p++ = NULL;
}
}
static HANDLE FindMemory(h,p,size)
HEAPHDR *h; /* the heap */
HANDLE p; /* the handle to allocate space for */
int size; /* size of block to allocate */
{
BLOCKPFX *bp;
BLOCKSFX *bs;
int tsize;
char *d;
tsize = sizeof(BLOCKPFX) + size + sizeof(BLOCKSFX);
if ((d = h->hh_next - tsize) < h->hh_base) {
CompactHeap(h);
if ((d = h->hh_next - tsize) < h->hh_base)
return (NULL);
}
h->hh_next = d;
bp = (BLOCKPFX *)d;
bp->bp_handle = p;
d += sizeof(BLOCKPFX);
bs = (BLOCKSFX *)(d + size);
bs->bs_size = size;
*p = d;
return (p);
}
static void CompactHeap(h)
HEAPHDR *h; /* the heap */
{
char *src,*dst;
BLOCKPFX *hp;
BLOCKSFX *hs;
src = dst = h->hh_top;
while (src > h->hh_next) {
hs = (BLOCKSFX *)(src - sizeof(BLOCKSFX));
hp = (BLOCKPFX *)((char *)hs - hs->bs_size - sizeof(BLOCKPFX));
if (hp->bp_handle) {
if (src == dst)
src = dst = (char *)hp;
else {
while (src > (char *)hp)
*--dst = *--src;
*hp->bp_handle = dst + sizeof(BLOCKPFX);
}
}
else
src = (char *)hp;
}
h->hh_next = dst;
}
<a name="0291_0008">
<a name="0291_0009">[LISTING THREE]<a name="0291_0009">
OFILES=hmmtest.obj hmm.obj
hmmtest.exe: $(OFILES)
cl $(OFILES)
<a name="0291_000a">
<a name="0291_000b">[LISTING FOUR]<a name="0291_000b">
#include <stdio.h>
#include "hmm.h"
HANDLE allocshow(int);
void showheap(void);
void pause(void);
#define HMAX 100
HEAPHDR *h;
HANDLE handles[HMAX];
main()
{
int i;
/* allocate a heap */
h = NewHeap(16,4096);
showheap();
pause();
/* allocate a bunch of blocks of memory from the heap */
printf("Allocating...\n");
for (i = 0; i < HMAX; ++i) {
printf("%2d: ",i);
handles[i] = allocshow(32);
sprintf(*handles[i],"%d",i); /* put something in the block */
putchar('\n');
}
/* show the state of the heap after the allocations */
showheap();
pause();
/* free every other block (to test the compaction algorithm) */
printf("Deallocating...\n");
for (i = 0; i < HMAX; i += 2)
HeapFree(h,handles[i]);
/* show the state of the heap after the deallocations */
showheap();
pause();
/* now reallocate the blocks we freed (causes compaction) */
printf("Reallocating...\n");
for (i = 0; i < HMAX; i += 2) {
printf("%2d: ",i);
handles[i] = allocshow(32);
sprintf(*handles[i],"%d",i);
putchar('\n');
}
/* show the state of the heap after the new allocations */
showheap();
pause();
/* make sure all of the blocks contain what we expect */
printf("Checking...\n");
for (i = 0; i < HMAX; ++i) {
printf("%2d: %04x->%04x=",i,handles[i],*handles[i]);
printf("%s",*handles[i]);
if (atoi(*handles[i]) != i)
printf(" *** ERROR");
putchar('\n');
}
/* free the heap and exit */
FreeHeap(h);
}
HANDLE allocshow(size)
int size;
{
HANDLE p;
if (p = HeapAlloc(h,size))
printf("%04x->%04x",p,*p);
return (p);
}
void pause()
{
while (getchar() != '\n')
;
}
void showheap()
{
printf("nhandles: %d\n",h->hh_nhandles);
printf("handles: %04x\n",h->hh_handles);
printf("base: %04x\n",h->hh_base);
printf("next: %04x\n",h->hh_next);
printf("top: %04x\n",h->hh_top);
}
Copyright © 1991, Dr. Dobb's Journal
