A custom malloc implementation in C, made for CSC369H (Operating Systems) - Fall 2014 - University of Toronto
Useful readings to better understand how memory management works:
- Memory API
- Free Space Management
- How do malloc() and free() work (StackOverflow)
- Hoard: A Scalable Memory Allocator for Multithreaded Applications (Berger et al.)
- Doug Lea's article on optimizing malloc
The data structure is located before each chunk of memory, to keep track of its status (metadata). Through the linked list of this data structure, it is possible to access the address of any memory block in the list, its size, availability, the next and previous chunks of adjacent memory and the end of the block. With this attributes, it’s possible to manage and manipulate the memory using the algorithm quickly described below.
It uses the “first fit” strategy. The algorithm search the list from the beginning to end, until it finds the first big enough (greater or equal the size requested) chunk of memory (splitting it in two, in case it’s bigger than needed), and finally return its adress to the user. If there is no more space in the heap, the algorithm then extends it, using the sbrk system call. To free memory, the algorithm changes the “available” state of the chunk’s metadata (struct), releasing it to further allocation. After that, the freed chunk is merged with the previous block (if this one is also freed), this is useful to avoid memory fragmentation in small sized blocks (it can happens after some splittings).
Space optimization: now myfree function will merge the two adjacent chunks (adjacents to the chunk being freed at the moment), if they are available (not allocated). By doing this, I'm preventing memory fragmentation, and these blocks will be easily reallocated in the next mymalloc.
Sbrk calls: to avoid calling sbrk() all the time, when the user first calls mymalloc (or when the heap need extension), mymalloc will allocate more memory than the amount asked. This way, it will take longer before the heap need to be extended again, and less times sbrk() will be invoked.
