Custom malloc () header design

Question

I am trying to write a custom allocator for debugging purposes (as an exercise) in C, where I will use one linked list to keep a free list of memory using the First Fit algorithm. I showed below the structure that I would like to create in the "Empty Node repository."

How to write a header block (concrete union) in the first few bytes of memory, I get (I use malloc () to get a piece of memory first) so that the remaining bytes are free

This is the union I'm 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] Modified block structure as proposed.

Answer 1

To debug malloc, consider placing a space between your control structure and the start of user data, as well as between the end user data and the checksum. One fill byte must be 0x00 byte zero, so string operations are stopped; consider putting another as 0xFF. If you have a fixed pattern and a stain that has changed, you know something is out of control - but there is more chance that your sensitive management data will not be trampled. If you use 16 bytes of padding on either side of the space allotted to the user, you can go up to 4 bytes of zeros appropriately aligned (hence a null 4-byte integer) and possibly 0xFFFFFFFF for -1. In addition, since you are likely to round the requested size to a multiple of your base block size, set bytes that are not for the user to use with a known value, and confirm that they remain unchanged. This will detect one-over-all-length modifications, or just a few bytes over the allotted length, which might otherwise go unnoticed.

The only drawback of a null byte in padding is that you will not easily detect read operations that do not stop at the end of the allocated memory when searching for a null byte. You can get an idea of ​​this by having an alternative that uses padding without zero bytes in it.

Another option is to try to completely separate your control data from the memory returned to the user. Of course, complete separation is impossible, but at least to maintain a list of distributions (with sizes and pointers) separately from the selected blocks. Again, this gives you protection by putting your precious management data away from uncontrolled memory loss operations. You are not completely protected from strange pointers, but you are better protected. (And you can still create buffer zones around the allocated space for recording detection without control). However, this design is noticeably different from the question.

---

Assuming you get a memory block from "malloc ()", then you would do it 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 ...

Answer 2

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

Oh, and since this is for debugging, I suggest you add mungwall: put 16 bytes on both sides of the user area and fill them with some pattern (for example, 0xdeadbeef, repeated four times). During free() make sure these bytes have not changed.

[EDIT] Here are a few pseudo codes:

 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 3

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 4

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

This helps a lot in performance when you want to combine the freed block with the previous and subsequent blacks, if they are also free.

Finally, you did not mention this, keeping the list sorted by size in order to quickly find the best block to allocate for a given query, and sorting by address makes it easy to combine free blocks. If you want to do both, make the user part at least 3 header* large, it will correspond to those pointers that are needed when the block is freed.

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

Answer 5

I suggest, it would be useful: A few years ago I needed to create a backup copy of the malloc () object for the purpose of debugging (selection tracing, etc.) ... And it was quite simple to make an implementation of FreeBSD from my libstdc. It was the way I remember FreeBSSD 5.0 ​​or even 4.x later releases, but the funny thing is that their object was isolated in a simple module of the malloc.o library, so overloading this layer was very simple copy'n'paste and implementation was really good.

Do you really want to do all this work? Yes, this is just a point to check, I do not pretend that this is the best solution.

Answer 6

You can use your original union if you want, for example:

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

This sets user_ptr to where the next union header will start if the malloc ed block is considered an array of these unions. So the value that you return to the user.

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

Answer 7

If you do not want to use malloc (), you should look at sbrk