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

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...

Answer 2

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.