Submit the contents of your repository via Gradescope. See Deliverables below for what to submit. If you are working with a partner, do not forget to include their name with the submission. Only submit one solution for both partners.
There will be no autograder for this assignment ahead of the deadline. Read the requirements and run tests locally.
Work on and test your code on either GitHub Codespaces or on login.khoury.northeastern.edu.
For this assignment, we will write a safer and more efficient version of the memory allocator from Assignment 5. Our goal is to get performance closer to that of the actual malloc, while making it safe for use by multiple threads.
mmap to Allocate Page-sized BlocksmmapFor the basic allocator implemented in Assignment 5, you were asked to use the sbrk system call to change the size of the heap. This call is not the only way to request memory for our process. In fact, the sbrk syscall is considered deprecated and its use is discouraged. We have used it in our first allocator because it provides a simple and easy-to-use interface for requesting heap memory from the OS.
So what does a modern Unix/Linux want us to use for memory allocation? The modern way to allocate memory is to directly request pages for a process using the mmap system call. In general, mmap allows us to map a file or a device into memory, meaning that any reads/writes within the memory region returned from a successful mmap call are reflected in the file (more on this in the file system project). In other words, mmap allows us to allocate memory from the operating system, backed by a particular file. On Linux and some other operating systems, we can even request “anonymous” mappings, meaning that the returned region is not backed by any file. In this mode, mmap can behave like malloc.
An “mmapped” region’s size is always aligned along the boundary of a page. This means that one constraint is that allocations with mmap should be made in multiples the size of a page. Even if you specify a size that is not a multiple of the system’s page size, mmap will round up to the nearest page. For example, if our page size is 4KB (4096 bytes), and we only use 12 bytes in total during our program’s execution, we have quite a bit of waste! In practice, for large desktop applications this is not a major issue.
The first task is to update our allocator implementation to use mmap instead of sbrk. Remember that, unlike sbrk, mmap will return a pointer to the beginning of a page of memory. Here is the overall updated strategy for mymalloc and myfree:
mymalloca) For requests of size < PAGE_SIZE:
mmap to request a new page and set it up as a block.b) For requests of size >= PAGE_SIZE:
x PAGE_SIZE.myfreea) For a block of memory of size < PAGE_SIZE: add the block to your free list and coalesce (see below) if needed.
b) For a block of size >= PAGE_SIZE: use munmap to unmap it.
When adding a block into your free list, keep the list sorted by the memory address of the blocks. This will allow coalescing: whenever two blocks in the free list form a continuous area of memory, they should be merged into one block (coalesced)
Since you insert into the free list and need to handle this in two different places, a helper function is a good idea.
Data races can affect memory allocators too. In a multi-threaded environment, we cannot simply make requests to our malloc and free functions based on our previous implementation. We could have a scenario where two or more threads request memory at the same time, and potentially all allocate the same block of memory in the heap. This would certainly be unlucky!
Luckily, we have mutexes to enforce mutual exclusion and help protect against data races. Remember, when we use pthread_mutex_lock and pthread_mutex_unlock, this creates a critical section where only one thread that has acquired the lock can execute a section of code, thus enforcing sequential execution over shared data.
Implement locking mechanisms such that, whenever there is an allocation (malloc or calloc) or deallocation (free), a lock protects that section of code from being run by another thread.
mmap
c) Move to multiple threads, adding locks around all allocations and frees
d) Add splitting of blocks
e) Add coalescing of blocks
All Tasks
~ Implement your memory allocator in mymalloc.c and include any additional .c and .h files your implementation relies on. For example, you might want to compile your helper data structure separately.
Commit the code to your repository. Do not include any executables, .o files, or other binary, temporary, or hidden files.
Once you are done, remember to submit your solution to Gradescope and do not forget to include your partner.
man pages of mmap, munmap, malloc, calloc, free, realloc, …mmap arguments. Request multiples of PAGE_SIZE. You’ll want an anonymous private mapping, that is both readable and writable. The flags you’re looking for are MAP_PRIVATE and MAP_ANON, and the protection PROT_READ and PROT_WRITE. For anonymous mappings, use -1 as the file descriptor. Offset should be 0.assert to check that your assumptions about state are valid.asserts to check expected results. Use our tests for queue/vector from Assignment 4 as an example.if-else if-else or a multi-case switch should be the only reason to go beyond 40-50 lines per function. Even so, the body of each branch/case should be at most 3-5 lines long.pthread_mutex_lock and pthread_mutex_unlock to ensure consistency.myfree function and mycalloc as well.memset (if you are using memset in calloc) that you are not memset‘ing over your block header.mallocs and frees, mallocs of a wide range of sizes to exercise the two block size strategies, in particular the edge cases.sysconf(_SC_PAGE_SIZE) to get the OS’s page size. Check the manpage for sysconf to see which header you need to include.0, meaning a freshly mmapped page does not need to be memset to initialize it.Q: If you need to split a block but the amount of remaining memory in the block is less than the amount of memory of a new block header (which we need to split the remaining memory into a new block), what should we do?
A: In this case you do not need to do anything, that is an acceptable amount of fragmentation to live with.