Custom malloc() implementation header design

Question

I am trying to write a custom allocator for debugging purposes (as an exercise) in C, where I will be using a single linked list to hold together the free list of memory using the First Fit Algorithm. I've shown below the structure I would like to create in an "Empty Memory Node".

How do I write the header block (a union to be specific) at the first few bytes of the memory, I obtain (I am using malloc() to initially get a chunk of memory) so that the remaining bytes are free?

This is the union I am using:

/*Define Header Structure for proper alignment*/
union header {
struct{
 union header* next;
 unsigned size ; /*Make it size_t*/
}s; 
double dummy_align_var;
};

-------------------------------------------------------------------------------
|Next        |Size of  |16Byte| User is concerned only about |16Byte|         |
|Free Memory |Allocated|Header| this portion  of memory      |Footer|Checksum |
|Address     |Block    |Picket| and has no knowledge of rest |Picket|         |
-------------------------------------------------------------------------------
|-------Header---------|      ^Address Returned to user
                           ^------User Requested Size-----^
^-------------Memory Obtained From The Operating System-----------------------^
*/

[EDIT] Changed block structure according to suggestions provided.

Answer 1

Why are you using a union? Just use a struct and return &dummy_align_var to the user as the start of the free block.

Oh, and since this is for debugging, I suggest that you add a mungwall: Put 16 bytes on either side of the user area and fill them with some pattern (for example 0xdeadbeef, repeated four times). During free() check that these bytes didn't change.

[EDIT] Here is some pseudocode:

struct header {
    struct header * next;
    unsigned size;
    // put mungwall here
    double user_data;
};

init()
    int blockSize = 1024;
    char * bigMem = original_malloc(blockSize);
    struct header * first = (struct header *)bigMem;
    first->next = NULL;
    first->size = blockSize - (sizeof(struct header) - sizeof(double));

Answer 2

You might also want to declare the dummy_align_var as union header* prev so that you can put the free memory blocks in a doubly linked list.

This helps a lot on performance when you want to merge a freed block with the previous and next blacks in case they are free too.

Lastly, you don't mention it, keeping the list sorted on size makes it faster to find the best block to allocate for a given request while sorted on address makes it easier to merge freed blocks. If you want to do both, make the user portion at least 3 header* large it will fit te pointers needed when the block is freed.

In addition to the borders Aaron mentioned, overwrite freed buffers with the same pattern. This makes it easier to recognize code that uses already freed buffers.

Answer 3

If you want not to use malloc(), you should have a look on sbrk

Answer 4

I suggest it would be useful: Some years ago I needed to backup malloc() facility for debugging purpose (allocation tracer and so on)... And it was pretty easy to simple take FreeBSD implementation from their libstdc. It was as I remember FreeBSSD 5.0 or even 4.x late releases but the funny thing was their facility was isolated in simple library malloc.o module so overloading of this layer was very simple copy'n'paste and implementation was really good.

Do you really to do all of this work? Yes, it is only point to check, I don't pretend this solution is the best.

Answer 5

[EDIT]Deleted my own Answer.This is the first time I landed up here Please Ignore :-)

Answer 6

I would do something like

#define MEM_ALIGN 4 // 8 on 64b eventually

struct header {
    union aligned_header {
        struct _s {
            union aligned_header* next;
            size_t size;
        } data;
        char dummy_align_var[sizeof(struct _s) + sizeof(struct _s)%MEM_ALIGN];
    } header_data;
    char user_address;
};

and return &user_address.

Answer 7

You can use your original union if you want, like so:

union header *hdr = malloc(total_size);
void *user_ptr = hdr + 1;
char *trailer_ptr = (char *)user_ptr + user_size;

That will set user_ptr to where the next union header would begin, if the malloced block was treated as an array of those unions. So that's the value you return to the user.

It also sets trailer_ptr to point to the first byte after the user's allocation, where you can put your checksum.

Answer 8

For a debugging malloc, consider putting padding space between your control structure and the start of the user data, and also between the end of the user data and the checksum. One byte of the padding should be a zero byte 0x00 - so string operations stop; consider putting another as 0xFF. If you have a fixed pattern and spot that it has changed, you know something went trampling out of bounds -- but there's a better chance that your sensitive control data was not trampled. If you use 16 bytes of padding either side of the space allocated to the user, you might go as far as to put 4 bytes of zeroes suitably aligned (hence a zero 4-byte integer) and maybe 0xFFFFFFFF for -1. Also, since you will probably round up the requested size to a multiple of your basic block size, set the bytes that are not for the user to use to a known value - and validate that they remain unchanged. That will detect modifications of 'one over the allocated length', or just a few bytes over the allocated length, that can otherwise go undetected.

The only disadvantage of the zero byte in padding is that you won't readily detect read operations that do not stop at the end of the allocated memory when looking for a null byte. You could get insight into those by have an alternative option that using padding with no zero bytes in it.

Another option to consider is trying to separate your control data altogether from the memory returned to the user. Of course, complete separation is impossible, but at least maintain a list of allocations (with sizes and pointers) separately from the blocks allocated. Again, this gives you protection by putting your precious control data further away from uncontrolled memory trampling operations. You aren't completely protected from errant pointers, but you are better protected. (And you can still provide buffer zones around the allocated space to detect out-of-control writing.) However, this design is noticably different from the question.

---

Assuming you get your memory block from 'malloc()', then you would do - roughly:

void *my_malloc(size_t nbytes)
{
    size_t reqblocks = (nbytes + sizeof(header) - 1) / sizeof(header);
    size_t reqspace  = (reqblocks + 2) * sizeof(header) + 2 * sizeof(padding);
    void *space = malloc(reqspace);
    if (space == 0)
        return space;
    void *retval = (char *)space + sizeof(header) + sizeof(padding);
    header *head = space;
    head->next = ...next...;
    head->size = nbytes;
    ...set head padding to chosen value...
    ...set tail padding to chosen value...
    ...set gap between nbytes and block boundary to chosen value...
    return retval;
}

There is some interpretation left to do...