A Memory Manager for C

If you have done any program in pure C, then you sure have felt the pain of managing memory. You sure have found you asking yourself the following questions…

  • Is it safe to free this pointer?
  • Who should free this pointer?
  • Am I leaking memory?
  • How many references are pointing to this memory address?

There is a rule when working with dynamic memory: When you write a malloc call, you should also write the free call. But that rule only is enough when you are not working with abstractions, multi-threading, several object creation and other advanced stuff… after all, you end up writing a lot of code just for managing the memory, and not solving the problem you wanted.

A painful example

Suppose you have a compound object, that has many components, and many references. For example:

typedef struct Course {
char *name;
Professor_t professor;
Student_t student[];
} Course_t;
typedef struct Professor {
char *name;
}
typedef struct Student {
char *name;
}

As you can see Course has a reference to Professor , who dictates it, and an array of Student. What would happen if you program no longer needs the reference to a Course? Does the Professor should be freed? What about the Student‘s? What would happen in the other way around? What would happen if you `free` the Course reference, but you used the Professor for another thing, and that thing is holding a reference? You will end up with invalid references!

Reference Counting

One solution I’ve found was implemented in Objective-C. The idea is that each time part of your code needs to hold a reference to an object, meaning that the object should be valid as long the piece of code is using it, it should retain the reference. When the piece of code no longer needs the reserved memory, it will release it. When the reference count reaches 0, the memory is freed.

With this idea, in the previous example, each time a reference is saved to a variable, the function retain is called. If for example you are holding a reference to a Course , and you ask for the reference of Professor you also retain that reference. And now imagine you no longer need the Course reference, then you call release function on the Course. The Professor reference would be still valid since it still has a retain count of 1. Once that the reference is no longer needed it is released, and then freed.

The API

A definition of the API would include the next functions

/* 
Function to free objects when the `retain` count reaches 0.
This function would `release` the compound objects.
*/
typedef void (*free_fnc_t)(void *ptr);
/* 
Allocs memory to be used with a retain count of 1.
If no `free` function is declared, default `free` is used.
*/
void *new(size_t size, free_fnc_t free_fnc);
/*
Increments the retain count in 1.
*/
void *retain(void *ptr);
/* 
Decrements the ratain count in 1. If count reaches 0, then the reference is freed used the free_fnc or the system default and the reference is no longer valid.
*/
void release(void *ptr);
/*
Informs how many retain counts has the given reference.
*/
int retainCount(void *ptr);

An usage example:

Strings

// A String definition
struct String_c {
char *str;
};
typedef struct String_c *String_t;
String_t new_string(char *str) {
String_t ret = new(strlen(str) + 1);
strcpy(ret, str);
return str;
}
// Code example:
String_t str = new_string("Hello World!");
//Work with the String then release it.
release(str);

Properties

Course_t c = fetch_course_by_id(123); //Let's assume retain count 1.
Professor_t p = retain(c->professor);
release(c);
// Work only with the professor, then release it.
release(p);

A Collection problem

In the case of a collection, soma care should be taken. Imagine this example:

// Adds an element to the top of the stack.
void push(Stack_t stack, void* elem) {
elements[top++] = elem;
retain(elem);
}
// Returns the last element pushed to the stack
void* pop(Stack_t stack) {
void ret = elements[top--];
release(ret);
return ret;
}

What would happen if the reference in the Stack is the being pointed to that piece of memory? We would return an invalid reference. So, as a rule, removing functions that return the selected element should not release the reference. Instead, the caller should do it.

Different is the case when having a delete function that doesn’t return a reference.

void delete(List_t list, int index) {
release(elements[index]);
shift_left(index); // Shift all elements to left and override the reference
elements--;
}

Since no one needs that address anymore, it could be released without problem.

A Problematic Case

Suppose in the example of the Course and Professor. What how do we solve the problem of the professor having a reference to the courses he gives?

typedef struct Professor {
char *name;
Course_t courses[];
}

How do we free this structure? We have a circular reference, and we should avoid it. In an automatic Garbage Collector this may lead to memory leaks.

An Implementation

I started an implementation of this Memory Manager in this Github repo. You can check it out, propose improvements and use it as you please :)

With this solution, all references are hard. There are not short lived elements. In the future I will implement Memory Pools that will have weak references, in order to be able to create a lot of objects, and not need to retain/release them all the time, since they are short lived.

Acknowledgements

Thanks to José Fresco for doing a revision for this article.