The Magic of Malloc
What is Malloc?
Malloc is a dynamic memory allocator — it gives you a block of memory on the heap during run time. You want to use malloc when you don’t know the memory size during compile time. It’s also useful when you need to allocate memory greater than the size of the stack. More commonly, malloc is used for objects that must exist beyond the scope of the current block.
When you call malloc(size), it will allocates a block of size bytes of memory, and return a pointer to the beginning of the block. The content of the newly allocated block of memory is not initialized. There will just be junk data on the heap that the user can overwrite.
If you ask malloc for a memory block of size 0, the return value depends on that particular library’s implementation (it may or may not be a null pointer). Either way, the returned pointer should not be dereferenced.
Syntax
// +1 if you need extra space for the null terminator
buffer = (char*) malloc (sizeof(char)*n+1);
// Always check if the pointer returned is valid
if (buffer == NULL) { exit (1); }
Related Functions
Here are some other functions that are used in conjunction with malloc.
- Realloc —Increases or decreases the size of the specified block of memory. Reallocates it if needed.
- Free — Releases the specified block of memory back to the system. You always have to free a block of memory that you malloc or else you will have memory leaks! Valgrind is your best friend for catching leaks.
- Calloc — Allocates the specified number of bytes and initializes them to zero. There are two differences between these functions. First, malloc takes a single argument (the amount of memory to allocate in bytes), while calloc needs two arguments (the number of variables to allocate in memory, and the size in bytes of a single variable). Secondly, malloc does not initialize the memory allocated, while calloc guarantees that all bytes of the allocated memory block have been initialized to zero.
- Sbrk — Used internally by allocators to grow or shrink the heap.
Memory Management
You should have learned everything in this next section in class, but I’ll type this up in case you need a refresher. Malloc is an explicit allocator (vs. an implicit allocator like Java’s garbage collection). The allocator maintains the heap as a list of block, which are either allocated or free. It must also respond immediately to malloc requests, only allocate free blocks, must align blocks by 8 bytes, can only manipulate and modify free blocks, can’t move the allocated blocks once they are malloc’d (since the user is already using the base pointer you returned to them before). Your performance goal with malloc is to maximize throughput (number of request per unit time) and memory utilization (don’t want to waste a lot of memory on alignment, meta data, internal fragmentation, or external fragmentation).
There are a few design choices you have to make. First you have to decide what information to hold in your header and footer. I would recommend going with the size, a status bit, a previous pointer, and a next pointer (explicit lists). You can combine the size and status bit all into one word, so the header can be 3 words in total. For the footer, I chose to save the size so I can find the header given a pointer to the footer.
These choices also tie into how your will organize your free lists. You can have implicit lists, explicit lists, or segregated lists. There are time and space trade-offs for each. Once you choose an organizational scheme, coalescing also works differently for each. For the purpose of not recreating the entire textbook chapter, I’m going to focus on explicit lists. Explicit lists are much faster compared to implicit lists. Allocation time is linear in the number of free blocks instead of being linear in all of the blocks. It’s significantly faster than implicit lists when most of the memory is malloc’d. The trade-off is an extra 2 words in the header and it’s more complicated to allocate and free blocks.
Finally, you will have to choose your policy to find a free block. You can either use first fit, next fit, or best fit. First fit is probably easier to code, but consider the trade-offs before you just take my word for it. So now that we’ve decided on first fit and explicit lists, let’s walk through what malloc, free, and realloc should do. Malloc should find the first block in your free list big enough for the request size and alignment. If no block was found, extend the heap, and try to find a block again. Take the block we just found and splice it if it’s too big. Change the block’s status bit to allocated and then return a pointer to its payload.
Free needs to put a block back into the free list. We have another decision to make here. You can either use LIFO or address ordering. See slides for more information. In either case, coalesce with its neighboring blocks in memory if needed, change your pointers where needed, and update the status bit to free.
Realloc is broken down into 4 cases. If realloc is passed in null as the pointer, then just malloc a new block. If it’s passed a negative number, free the block. If size is less than the current size, splice the block if necessary, add the extra parts to the free list, and return the old pointer. Finally, if size is greater than the current size of the block, try to malloc the new size requested. Copy the data over. Free the old block. Return the pointer to the new block.
Getting Started
Don’t code until you have a clear understanding of what every function should do and have everything planned out. You will only need to edit mm.c. Don’t leave this lab until last minute. It will be painful and you will regret it. I know I did. This guide is just a brief intro to malloc. The textbook is a way better resource for a detailed explanation. Good luck!
Source
https://en.wikipedia.org/wiki/C_dynamic_memory_allocation
http://www.cplusplus.com/reference/cstdlib/malloc/
