Hello 0x00sec! This is the fifth installment of my Dynamic Memory series. In my last article, I went through using brk and sbrk to alter a process’s program break.
After a decent amount of studying, I have some code to show all of you.
I set out to roughly implement malloc and free and I have done so. valgrind shows no errors and my program’s readouts make sense.
Note: As @dtm would say, what follows is more my findings than an outright tutorial. I am no master of this; I’m learning while teaching, as many often do.
Headers
Before anything else, I need to present the header file: my-malloc.h
#include <stddef.h>
#ifndef MY_MALLOC_HDR
#define MY_MALLOC_HDR
#define FREE 1
#define NOT_FREE 0
/*
Defining a basic chunk type here.
It should pad to be the next power of 2 >=
user-requested amount of memory.
*/
typedef struct _chunk {
size_t _chunk_sz; /* not including metadata */
/* to see if the chunk is free: */
unsigned char _free;
struct _chunk *next,
*prev;
} _chunk;
typedef struct _mem_session {
_chunk *_first_chunk,
*_last_chunk;
size_t _chunks_allocated;
} _mem_session;
extern _mem_session *_session;
void *my_malloc(size_t bytes);
void my_free(void *ptr);
void _create_session();
_chunk *_find_free_chunk( size_t bytes );
#endif
There is a lot of stuff in this header. The first thing is the type definition of _chunk, which, as its name may suggest, represents a chunk of memory.
Following that, there is a type called _mem_session. This will be a global session that keeps track of all of the program’s chunks. This will be the first thing stored on the heap.
Upon a closer look, you’ll see that _chunk is actually a doublely-linked list and _mem_session keeps track of that list’s start and end. _mem_session also records how many _chunks there are, the length of the linked list. If you need a refresher on linked lists, I have a tutorial here.
We note an extern variable called _session that points to a _mem_session instance. This pointer is how we will keep track of all of the chunks during runtime.
There are four functions. The respective purposes of the first two should be quite obvious. _create_session does some first-time initialization. _find_free_chunk does as its name describes, but I’ll save revealing its exact functionality for later.
Concept
Now that I’ve shown you the header, it’s likely that you have some questions. First, let me explain in more detail what a _chunk represents.
Imagine our heap space like so:
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| |##############|
| Program Break --> |##############|
| |##############|
| |##############|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
We have a bunch of memory and it’s cut off by the break. Memory beyond the break is not currently ours to use.
When we extend the break, we can use that memory. But we need to keep this memory organized. Such is the reason for chunks. Each chunk has a certain size – and that size is a multiple of 4.
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| |****##########|
| |****##########|
| |****##########|
| |****##########|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
Imagine that the astericks represent a new chunk. What if we allocated a second chunk?
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| |********######|
| |********######|
| |********######|
| |********######|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
Well, now you can’t discern the two chunks! What we need is some metadata: information about each chunk. What would be good to know about a chunk?
- The size of the chunk
- The chunk before it
- The chunk after it
- Is the chunk being used?
Let’s add metadata to our visual:
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| |$$****$$****######|
| |$$****$$****######|
| |$$****$$****######|
| |$$****$$****######|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
While we do have to use a little extra memory, we can now differentiate between chunks. This is the use of the struct _chunk.
Starting to code my_malloc.
Now it’s time to jump into my_malloc!
#include <stddef.h>
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h> /* just for exit() */
#include "my-malloc.h"
_mem_session *_session = NULL;
Above are our inclusions. We also give _session a value of NULL, meaning that each time the program runs it has no _mem_session until we give it one.
void *my_malloc(size_t bytes) {
/* Round up to nearest power of 2. */
size_t cnt = (((bytes-1)>>2)<<2) + 4;
if (_session == NULL) {
_create_session();
}
_chunk *c = _find_free_chunk( cnt );
// ...
}
As can be seen in the above code, the first thing we do is figure out how many bytes to allocate. I briefly mentioned that we want each chunk to store a number of bytes that is a multiple of 4. That formula is explained in [1].
Next, a session is created/initialized if none exist. This happens on the first call of my_malloc.
Last in the above snippet, _find_free_chunk is called to look for any existing free chunks that are large enough to hold cnt bytes.
A note on Free Chunks: As can be seen in [2], free chunks can and do exist. They are chunks that were previously allocated but were freed. They still exist in memory so as to be reused in the future. Thus, in the metadata of a chunk, we note if said chunk is a free chunk or not. Also, two free chunks cannot be adjacent. When there are two free chunks side-by-side in RAM (in this context: virtual memory), they are merged into one big chunk.
void *my_malloc(size_t bytes) {
//...
if (c == NULL) {
void *ptr = sbrk(0);
if ( brk(ptr + sizeof(_chunk) + cnt) < 0) {
perror("couldn't allocate memory");
exit(2);
}
c = (_chunk*)ptr;
c->_chunk_sz = cnt;
c->_free = NOT_FREE;
c->prev = _session->_last_chunk;
c->next = NULL;
_session->_last_chunk = c;
_session->_chunks_allocated++;
printf("New chunk at %p\n", c);
printf("Result of ptr + sizeof(_chunk): %p\n", ptr + sizeof(_chunk));
printf("Size of a chunk: %i\n", (int)sizeof(_chunk));
printf("Amount of space requested: %i\n", (int)bytes);
printf("Amount given: %i\n", (int)cnt);
} else {
// ...
}
// ...
}
We act based on the result of _find_free_chunk. If no viable chunk is found, meaning that c = NULL, we will add a new one to the heap. How? You guessed it! By extending the program break.
- Record current program break.
- Extend program break to fit chunk metadata and user data.
- Hold pointer to the beginning of the metadata in
c. - Track the size of the chunk with
c->_chunk_sz = cnt. - Mark the chunk as not free.
- Put the chunk in the session’s chunk chain and increment
_session->_chunks_allocatedto signify the existence of this chunk.
What if there is an available chunk?
In that case, the code inside the else is executed:
void *my_malloc(size_t bytes) {
// ...
if (c == NULL) {
// ...
} else {
c->_free = NOT_FREE;
// ...
}
return (sizeof(_chunk) + (char*)c);
/* will break if all resources are used*/
}
If a free, usable chunk already exists, all we must do is note that we are now using the chunk. There are optimizations to be made that exceed the scope of this tutorial. It is important that these fundamentals of my_malloc are understood before we proceed. Also, I prefer brief articles.
As can be seen in the code, my_malloc returns void *. The last thing we do is return a pointer offset. If we take the pointer to our chunk metadata and add the size of the chunk metadata, we get the pointer to the user data. Note: The char* cast is so that we increment the pointer by bytes. A further explanation can be found here.
The counterpart to my_malloc is my_free:
void my_free(void *ptr) {
printf("[*] Now freeing...\n");
if ( ptr < (void*)((char*)_session->_first_chunk + sizeof(_chunk))
|| ptr > (void*)((char*)_session->_last_chunk + sizeof(_chunk)) ) {
perror("Invalid Free. Out of range!");
exit(3);
}
_chunk *c = (_chunk*)((char*)ptr - sizeof(_chunk) );
c->_free = FREE;
// ...
}
While my_free actually does much more than shown above, these dozen lines or so make up the most fundamental part of the function.
We make sure that the pointer is valid, meaning in the correct range of our heap. Then, we get a pointer to the chunk’s metadata by doing some sweet pointer gymnastics (@0x00pf).
Last, we mark the chunk as FREE so that it can be reused down the road.
Conclusion
I have written a lot more code than presented above; yet, I believe it to be paramount that what was shown today is understood. Thus, I’m omitting optimizations and tricks that would certainly lead to confusion.
Shortly, I will release another paper (or several) outlining the more complex aspects of the code.
Later…
@oaktree
P.S. This next article (Part 6.0) covers more details of my_malloc(), including a few optimizations.
References
- A Malloc Tutorial, Marwin Burelle
- Understanding Glibc Malloc, sploitfun