This is a dumb one, but maybe someone else will find it useful.

I have been working on some C code that uses dynamically allocated linked lists. There are index structures and record structures and individual elements of different kinds in the records, all malloc()’d and then (hopefully) free()’d at the end.

Since my background is low-resource embedded systems (one system has a mere 8K of RAM), I have never really done much with malloc(). In fact, on some of the environments I have worked in they did not even provide a malloc()/free(). And this is probably a good thing. Without an OS watching over you, any memory allocated that did not get properly freed (a “memory leak“) can be big trouble for an embedded system meant to “run forever without a reboot.”

What I am writing right now is for a PC, and my understanding is if you allocate a bunch of memory then exit, Windows will clean it up for you:

int main()
{
    char *ptr = malloc (65535); // Allocate 64K

    // And now just exit without freeing it.
    return 0;
}

But no one should be writing code like that intentionally. This is the same mentality that has people who throw their trash on the ground because “someone else will clean it up for me.” Just because you have a garbage collector doesn’t mean you should rely on it to clean up after your mistakes.

But I digress.

In my program, I was wondering if I was getting it right. Debug “printf” messages can only go so far in to seeing what is going on. Did I free every last record? Did all the elements inside the records get freed as well?

I have no idea.

MAUI to the rescue!

Then a memory popped into my head. When I worked for Microware Systems Corp., we had a New Media division that worked on digital TV set-top boxes. (Yes, Virginia, I saw a demo of streaming video-on-demand with pause, fast forward and rewind back in the summer of 1995. But that’s a story for another day…)

The D.A.V.I.D. product (Digital Audio Video Interactive Decoder) used various APIs to handle things like networking, MPEG video decoding, sound, and graphics. The graphics API was called M.A.U.I. (Multimedia Application User Interface).

MAUI had various APIs such as GFX (graphics device), DRW (drawing API), ANM (animation), CDB (configuration database?), BLT (a blitter) and more. There was even a MEM (memory) API that was a special way to allocate and free memory.

I did not understand much of this at the time, beyond the entry level stuff I sometimes taught in a training course.

But the memory API had some interesting features. The manual introduced it as follows:

“Efficient memory management is a requirement for any graphical environment. Graphical environments tend to be very dynamic when it comes to allocating and freeing memory segments. Therefore, unless an application takes specific steps to avoid it, memory fragmentation can become a serious problem.

The Shaded Memory API provides the facilities applications (and other APIs) required to manage multiple pools of memory.

– Microware MAUI manual, 2000

One interesting feature of this API was the ability to detect memory overflows and underflows. For example, if you allocate 50 bytes and get a pointer to that memory, then copy out 60 bytes, you have overflowed that memory by 10 bytes (“buffer overrun“). Likewise, if the pointer started at 0x1000 in memory, and you wrote to memory before that pointer, that would be a buffer underflow.

The manual describes it as follows:

To print the list of overflows/underflows call mem_list_overflows(). When a shade is created with the check overflows option true, safe areas are created at the beginning and the end of the segment. If these safe areas are overwritten, the overflow/underflow situation is reported by mem_list_overflows().

– Microware MAUI manual, 2000

This gave me an idea on how to verify I was allocating and freeing everything properly. I could make my own malloc() and free() wrapper that tracked how much memory was allocated and freed, and have a function that returned the current amount. Check it at startup and it should be zero. Check it after all the allocations and it should have some number. Free all the memory and it should be back at zero. (Malloc already tracks all of the internally, but C does not give us a legal way to get to that information.)

Simple!

Sounds simple!

At first, you might think it could be as simple as something like this:

static int S_memAllocated = 0;

void *MyMalloc (size_t size)
{
    S_memAllocated += size;

    return malloc (size);
}

Simple! But, when it comes time to free(), there is no way to tell how big that memory block is. All free() gets is a pointer.

Sounds almost simple!

To solve this problem, we can simply store the size of the memory allocated in the block of allocated memory. When it comes time to free, the size of that block will be contained in it.

To do this, if the user wanted to malloc(100) to get 100 bytes, you would allocate 100 + the size of an integer. You would then copy an integer containing the size of this allocated segment into the first bytes of the block (and increment the memory counter by that amount). After that, the pointer returned to the user should be after that copied integer. Like this:

malloc (100 + sizeof(int));
+---+----------------------+
|int| the user's 100 bytes |
+---+----------------------+
    ^
    |_ return this location

When this memory is free()’d, the passed-in pointer would be adjusted back past the integer. Those bytes could be copied into an int (so you know how much to subtract from the counter) and then the block free()’d.

Sounds sorta simple?

Here is what I quickly came up with…

// MyMalloc.h
#ifndef MYMALLOC_H_INCLUDED
#define MYMALLOC_H_INCLUDED
size_t GetSizeAllocated (void);
void *MyMalloc (size_t size);
void MyFree (void *ptr);
#endif // MYMALLOC_H_INCLUDED

// MyMalloc.c
#include <stdlib.h> // for malloc()/free();
#include <string.h> // for memcpy()

#include "MyMalloc.h"

static size_t S_bytesAllocated = 0;

size_t GetSizeAllocated (void)
{
    return S_bytesAllocated;
}

void *MyMalloc (size_t size)
{
    // Allocate room for a "size_t" plus user's requested bytes.
    void *ptr = malloc (sizeof(size) + size);
    
    if (NULL != ptr)
    {
        // Add this amount.
        S_bytesAllocated = S_bytesAllocated + size;
        
        // Copy size into start of memory.
        memcpy (ptr, &size, sizeof (size));

        // Move pointer past the size.
        ptr = ((char*)ptr + sizeof (size));
    }

    return ptr;
}

void MyFree (void *ptr)
{
    if (NULL != ptr)
    {
        size_t size = 0;

        // Move pointer back to the size.
        ptr = ((char*)ptr - sizeof (size));
        
        // Copy out size.
        memcpy (&size, ptr, sizeof(size));

        // Subtract this amount.
        S_bytesAllocated = S_bytesAllocated - size;
        
        // Release the memory.
        free (ptr);
    }
}

Then, as a test, I wrote this program that randomly allocates ‘x’ blocks of memory of random sizes… then frees all those blocks.

#include <stdio.h>
#include <stdlib.h>

#include "MyMalloc.h"

#define NUM_ALLOCATIONS     100
#define LARGEST_ALLOCATION  1024

int main()
{
    char *ptr[NUM_ALLOCATIONS];
    
    printf ("Memory Allocated: %zu\n", GetSizeAllocated());

    // Allocate    
    for (int idx=0; idx<NUM_ALLOCATIONS; idx++)
    {
        ptr[idx] = MyMalloc ( rand() % LARGEST_ALLOCATION + 1);
        
    }

    printf ("Memory Allocated: %zu\n", GetSizeAllocated());

    // Free    
    for (int idx=0; idx<NUM_ALLOCATIONS; idx++)
    {
        MyFree (ptr[idx]);
    }

    printf ("Memory Allocated: %zu\n", GetSizeAllocated());

    return EXIT_SUCCESS;
}

When I run this, I see the memory count before the allocation, after the allocation, then after the free.

Memory Allocated: 0
Memory Allocated: 45464
Memory Allocated: 0

Since it is randomly choosing sizes, the number in the middle may* be different when you run it.

I then plugged this code into my program (I did a search/replace of malloc->MyMalloc and free->MyFree) and added the same memory prints at the start, after allocation, and after freeing.

And it worked. Whew! I guess I did not need to spend time writing MyMalloc() or this post after all.

But I had fun doing it.

Additional thoughts…

Thinking back to the MAUI memory API, extra code could be added to put a pattern at the start and end of the block. A function could be written to verify that the block still had those patterns intact, else it could report a buffer overflow or underflow.

Also, I chose “size_t” for this example just to match the parameter that malloc() takes. But, if you knew you would never be allocating more than 255 bytes at a time, you could change the value you store in the buffer to a uint8_t. Or if you knew 65535 bytes was your upper limit, use a uint16_t. This would prevent wasting 8 bytes (on a 64-bit compiler) at the start of each malloc’d buffer.

But why would you want to do that? If you were on a PC, you wouldn’t need to worry about a few extra bytes each allocation. And if you were on a memory constrained embedded system, you probably shouldn’t be doing dynamic memory allocations anyway! (But if you did, maybe uint8_t would be more than enough.)

I suppose there are plenty of enhanced memory allocation routines in existence that do really useful and fancy things. Feel free to share any suggestions in the comments.

Until next time…

Bonus Tip

If you want to integrate this code in your program without having to change all the “malloc” and “free” instances, try this:

// Other headers
#include "MyMalloc.h"
#define malloc MyMalloc
#define free MyFree

That will cause the C preprocessor to replace instances of “malloc” and “free” in your code to “MyMalloc” and “MyFree” and then it will compile referencing those functions instead.

---

* Or you may see the same number over and over again each time you run it. But that’s a story for another time…