Channels ▼
RSS

Design

A Simple Handle-Based Memory Manager

Source Code Accompanies This Article. Download It Now.


DEC91: A SIMPLE HANDLE-BASED MEMORY MANAGER

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


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Video