Introduction

In class, we cover how the operating system manages memory to create per-process virtual address spaces. Unix-like operating systems expose system calls like mmap and munmap to request virtual address space for the calling process. In most situations, these system calls are not the most efficient (or convenient) way to dynamically allocate memory for our programs. Instead, we often rely on user-space allocators, such as malloc from the C standard library.

A user-space memory allocator (aka malloc) is a library (a set of functions and associated data structures) that handles programmer requests for memory. Most of a memory allocator’s work is to track free memory, hand out available memory blocks, and request more memory from the OS when it runs out of managed memory.

For this assignment, you will be writing your own memory allocator. Writing a custom memory allocator is something you might do if you work on performance-sensitive systems (games, graphics, quantitative finance, embedded devices, or any application you want to run fast!). Malloc and free are general-purpose functions written to manage memory in the average use case quite well, but they can always be optimized for a given workload. That said, a lot of smart people have worked on making malloc/free quite performant over a wide range of workloads. Optimization aside, you might write an allocator to add in cool debugging features, and swap it in as needed.

For this assignment, you will implement a portion of a custom memory allocator for the C language. You will write your own versions of:

• malloc
• calloc
• free

Your allocator will request memory from the operating system one or more pages at a time using mmap, hand out pieces of those pages to the program, keep track of the pieces that are free, merge neighboring free pieces back together, and return memory to the operating system with munmap when it is no longer needed.

Pre-requisite Reading

Read Chapter 17 of OSTEP. This covers most of what you need to know about free space management and the workings of a memory allocator conceptually, including splitting and coalescing. With the correct understanding, this assignment is relatively quick and easy. Ask questions.

Understanding mmap

The modern way to allocate memory is to directly request pages for a process using the mmap system call. (Older systems also provided the brk/sbrk calls to grow and shrink the heap. These are considered deprecated and discouraged, and you will not use them in this assignment.)

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 of 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 use only 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.

Unlike sbrk, which moves the end of a single contiguous heap, each successful mmap call returns a pointer to the beginning of a new page-aligned region. Regions returned by separate calls are not guaranteed to be adjacent to each other. When you no longer need a region, munmap gives it back to the operating system.

Task

Your objective is to create three functions in mymalloc.c:

1. mymalloc
2. mycalloc
3. myfree

Design Decisions

Please read through the following design decisions to help guide you. This is some of the thought process a designer of such a system may go through. There are more concrete specifications following.

Decision 1 - How to request memory?

Remember that malloc, calloc, and free are all working with memory allocated on the heap. We request memory from the operating system using the mmap system call, and we release it with munmap.

For this assignment, all memory requests MUST use the mmap system call, and you MUST NOT use malloc, sbrk, or brk.

In the text below, PAGE_SIZE refers to the system’s page size, which you can find out using the sysconf routine (see its manpage). Do not hard-code this value anywhere.

Decision 2 - How to organize our memory?

Once you have retrieved memory, we need to keep track of it. That means that every time a user uses your malloc or calloc functions, you will want to know where that memory exists and how big it is. So we want to track the memory we request in a convenient data structure that can dynamically expand.

So think about: What data structure could I use?

Decision 3 - What else will I need?

You may define any helping data structures and functions that assist you in this task. This means you might even have a global variable or two to assist with your implementation. Depending on what data structure you decide to store all of the requested memory in, it may be useful to have additional helper functions for traversing your data structure, finding free blocks, requesting new pages, splitting blocks, and inserting blocks into the free list (and coalescing them).

Decision 4 - How will I efficiently reuse memory already allocated?

Programs may frequently allocate and free memory throughout execution. It can thus become very inefficient to keep requesting new memory from the operating system. Instead, we try to reuse blocks as efficiently as possible. That is, if I allocate an 8-byte block and then free it, the next time I call malloc, I can reuse those 8 bytes without making another call to mmap.

Several strategies exist for searching free memory. The most straightforward ones are first-fit and best-fit. Both are described in detail, along with other very useful supporting information in OSTEP Chapter 17.

Decision 5 - How will I avoid fragmentation?

Splitting a large free block to satisfy a small request leaves lots of small free blocks behind. If those blocks are never merged again, the free list slowly fills with fragments that are too small to be useful. To avoid this, most allocators combine free blocks that are adjacent in memory into bigger ones (coalescing), and split those bigger blocks as needed. Your allocator will do both.

Specification

Here are the specifications to put everyone on equal footing. Read them carefully, and get a basic version working before you optimize.

1. Do not modify malloc.h.

2. Use an embedded linked list data structure. See OSTEP Chapter 17.

   • This data structure will keep track of the free blocks that you have pooled within the mymalloc function.

   • The data structure will need to be accessible by the functions in your library.

   • You should have some notion of a ‘block’ of memory in your program.

   • An example is provided here with some fields that may be useful:

     typedef struct block {
       size_t size;        // How many bytes beyond this metadata are
                           // available to the user in this block
       struct block *next; // Where is the next block in the free list
     } block_t;

     Remember, you are the boss: you may embed other information in the header. However, do not waste space in the header, and note that the example traces below assume a 16-byte header (a size_t and a pointer on a 64-bit system). If your header has a different size, the sizes in your debug output will differ accordingly.

3. Use the mmap and munmap system calls. Your version of malloc (mymalloc or its helper functions) shall use mmap to obtain memory, and myfree shall use munmap to give memory back. Do not use malloc, sbrk, or brk.

4. Block headers live in the same memory as the user data. Consider how memory is laid out and make sure you are only accessing your struct when you mean to. Here is a simple diagram of the blocks within a page:

   |block|---user memory---|block|------user memory-------|block|--user memory--|
   
   ^ Here is where your struct lives; this is what you want to update.

   The mymalloc function returns the user memory, not the block header:

   |block|---user memory---|block|------user memory-------|block|--user memory--|
   
          ^ Here is what you'll return to the programmer as their memory.

   Given the pointer the programmer passes to myfree, you must be able to find the header that precedes it.

5. Block sizes and the small/large distinction (see mymalloc and myfree below):

   • A small block has user memory of size ≤ PAGE_SIZE - sizeof(block_t). Its size is the number of bytes of user memory after the header.
   • A large block has user memory of size > PAGE_SIZE - sizeof(block_t). Its size is the total size of the mmaped region (the number of pages × PAGE_SIZE), which is exactly what is needed to munmap it later.

6. The free list contains only free blocks, and it never contains blocks that are smaller than the header size. When a block is handed to the user, remove it from the free list.

7. When called, mymalloc must print out "Malloc %zu bytes\n" using the provided debug_printf function (which is used just like printf; see the file debug.h).

8. When called, mycalloc must print out "Calloc %zu bytes\n" using the provided debug_printf function (Yes, a proper implementation will print “Malloc …” followed by “Calloc …”).

9. When called, myfree must print out "Freed %zu bytes\n" (using debug_printf). In addition, mymalloc, mycalloc and myfree must print the trace messages described in Tracing Operations.

10. The malloc.h header defines aliases for these functions, so you will actually see the tests using malloc, calloc, and free.

11. With these print-outs, you can see if they match the original programs.

12. We will examine your code to confirm you do not use the C library malloc/calloc/free from stdlib.h. You should only be using syscalls such as mmap to request memory from the operating system.

mymalloc

1. For requests of size ≤ PAGE_SIZE - sizeof(block_t) (aka “small block”):

   • Use your free list to see if there is a large enough block to accommodate the request.
   • If a block is found, select it and remove it from the list.
   • If a large enough block is not found, use mmap to request a new page and set it up as a block.
   • If the block is larger than the requested memory size, determine whether it is feasible to split it: after “shrinking” the original block, is the “leftover” big enough to include a block header and at least sizeof(block_t) bytes of user memory? That means that the free list shouldn’t contain blocks that are smaller than the header size.
   • If splitting, set up the leftover as a new memory block and add it to your free list.
   • Return the selected block’s user memory pointer.

2. For requests of size > PAGE_SIZE - sizeof(block_t) (aka “large block”):

   • Compute the number of pages needed to satisfy the request (including a block header) and allocate that many pages with mmap.
   • Set up the block header and set the size to the number of pages × PAGE_SIZE.
   • Return the block’s user memory pointer.

For mmap, use the arguments described in the Hints & Tips below.

myfree

1. For small blocks, i.e., blocks of memory of size ≤ PAGE_SIZE - sizeof(block_t): add the block to your free list and coalesce (see below) if needed. Keep at most 2 page-sized (i.e., the user’s block size is PAGE_SIZE - sizeof(block_t)) blocks in your free list. Use munmap to unmap extra blocks that take up a page.

2. For large blocks, i.e., blocks of size > PAGE_SIZE - sizeof(block_t): use munmap to unmap them.

mycalloc

The calloc function guarantees that a block it returns only contains bytes set to zero. However, reading the man page for mmap you will notice that pages requested with MAP_ANONYMOUS are already initialized to zero when returned from the OS. Only use memset when needed to zero blocks you are returning from calloc. (For example, a block that was previously used and freed may contain old data.)

Coalescing Free Blocks

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). Coalescing applies to blocks within the same page; do not merge blocks that came from different mmap calls, since each page must remain independently releasable with munmap.

Since you insert into the free list and need to handle this in two different places, a helper function is a good idea.

Tracing Operations

In addition to the original debug messages (Malloc, Calloc, Freed), use debug_printf to log the following messages from mymalloc, mycalloc, and myfree.

Function	small / large	Condition / Event	Printout
mymalloc	small	exact block is found in free list	"malloc: block of size %zu found\n"
mymalloc	small	no block found	"malloc: block of size %zu not found - calling mmap\n"
mymalloc	small	splitting block	"malloc: splitting - blocks of size %zu and %zu created\n"
mymalloc	large	mmap request	"malloc: large block - mmap region of size %zu\n"
myfree	small	coalescing	"free: coalesce blocks of size %zu and %zu to new block of size %zu\n"
myfree	large	unmapping	"free: munmap region of size %zu\n"

For example, let’s say we are servicing the first malloc request after the program starts, the request size is 1024 bytes, the header size is 16 bytes, and the system page size is 4096 bytes. Then the following log trace should be visible:

DEBUG: Malloc 1024 bytes
DEBUG: malloc: block of size 1024 not found - calling mmap
DEBUG: malloc: splitting - blocks of size 1024 and 3040 created
DEBUG: malloc: block of size 1024 found

If free was called immediately after, we get the following messages:

DEBUG: free: coalesce blocks of size 1024 and 3040 to new block of size 4080
DEBUG: Freed 1024 bytes

Here’s a large block example with malloc followed by a free of the same block. The request is for 12000 bytes, the header is 16 bytes, and the page size is 4096:

DEBUG: Malloc 12000 bytes
DEBUG: malloc: large block - mmap region of size 12288
...
DEBUG: free: munmap region of size 12288
DEBUG: Freed 12288 bytes

How to test the assignment

We have included a Makefile to make your life easier. Here’s a quick overview of the possible targets:

• make - compile mymalloc.c to the object file, mymalloc.o
• make test - compile and run tests in the tests directory with mymalloc.
• make demo - compile and run tests in the tests directory with standard malloc.
• make help - print available targets

We have provided some “tests” for you, which exercise your allocator. Most tests explain what behavior to look for. Passing all the tests without crashing does not guarantee a perfect assignment, but it will give you some confidence that your implementation is working. It would be wise to write additional tests to exercise your implementation.

Because your allocator releases large blocks of memory to the OS and coalesces smaller blocks, the most allocation-heavy tests (tests 6 and 7) might run for 10s of seconds.

It is unlikely that the provided tests will check for the exact sequence of trace messages in every situation, so compare your output against the examples above and write your own tests for the cases the provided tests do not cover.

Deliverables

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. Only submit one solution for both partners.

F.A.Q.

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.

Q: Can I use valgrind to check for memory leaks in my program?
A: Likely not, because you are implementing your own allocator. By default, valgrind is not able to reliably track calls to mmap. This is not to say that using valgrind gives no information, but it won’t give you the same level of detail as if the code had used the system allocator.

Q: So if I cannot use valgrind, what can I do?
A1: One suggestion is to keep track of how many total bytes you allocate and how many you mark as free as global variables.
A2: A second suggestion is that you could use some of gcc’s compile-time interpositioning tricks to add a function that is automatically called at the end of the program. This function would traverse your linked list structure and check to see if any of the memory in your ‘block’ structure is marked as unfreed.

Q: How will I know my tool is working?
A1: This is a pretty general question, but a tool like strace can be helpful. strace can be run on the tests once you have compiled them. strace reports how many calls you have made to mmap and munmap, and you can test your assumptions to see if those system calls are being made too often (i.e., not reusing blocks that have been previously allocated and could be used). strace will also confirm that you are NOT using the system malloc or free.
A2: You could also run your allocator with your linked list or other data structures and see if it passes the given unit tests.
A3: Write unit tests to exercise your implementation, e.g., mallocs of random sizes, interleaved mallocs and frees, large numbers of mallocs and frees, walking the free list, edge cases…

Hints & Tips

• This assignment is mainly about implementing a data structure for managing free blocks of memory. You are expected to do the reading and ask clarifying questions. There isn’t much code to write.
• Refresh your memory on pointer arithmetic. Section 6 of Essential C is a good start (take a close look at “Pointer Type Effects” there).
• It might help to refresh yourself on how a linked list is implemented in C (see Lab 4). Our allocator basically uses a linked list “with a twist”.
• Check out the man pages of mmap, munmap, sysconf, 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_ANONYMOUS, and the protection PROT_READ and PROT_WRITE. For anonymous mappings, use -1 as the file descriptor. Offset should be 0. Check the return value against MAP_FAILED.
• Use sysconf(_SC_PAGE_SIZE) to get the OS’s page size. Check the man page for sysconf to see which header you need to include.
• On Linux, anonymously mapped pages are guaranteed to be initialized to 0, meaning a freshly mmapped page does not need to be memset to initialize it.
• Make sure when you memset (if you are using memset in calloc) that you are not memset-ing over your block header.
• A function to print the contents of the free list might be useful for debugging.
• Compile and test often.
• Use assert to check that your assumptions about state are valid (e.g., the free list is sorted by address, and contains no block smaller than the header size).
• Write your own (unit) tests. Doing so will save you time in the long run, especially in conjunction with the debugger. In office hours, the instructors or the TAs may ask you to show how you tested code that fails.
• Write additional tests to examine high volumes of mallocs and frees, and mallocs of a wide range of sizes to exercise the two block size strategies, in particular the edge cases (requests of exactly PAGE_SIZE - sizeof(block_t) bytes and one byte more or less).
• Unit tests can be just a bunch of functions and a main, with asserts to check expected results. Use our tests for vector from Assignment 4 as an example.
• Follow good coding practices. Make sure your function prototypes (signatures) are correct and always provide purpose statements. Add comments where appropriate to document your thinking, although strive to write self-documenting code. State your assumptions explicitly, and use types correctly (e.g., do not assign -1 to an unsigned).
• Split code into short functions. Avoid producing “spaghetti code”. A multi-branch 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.
• It is ok to use global variables, but be judicious with their use. Give them meaningful names and explain their purpose.
• Programming in C (aka, the K&R book) has a nice description of memory allocators.
• Advanced Material: https://www.youtube.com/watch?v=kSWfushlvB8 (“How to Write a Custom Allocator” for C++)

Going Further and Additional Resources

• There are various open source malloc implementations (the GNU C library is just one), so you can take a look at them if you are curious.
• A nice survey of dynamic memory allocation strategies: http://www.cs.northwestern.edu/~pdinda/ics-s05/doc/dsa.pdf
• Investigate the ‘buddy allocator’ and ‘arena allocators’
• John Lakos Memory Allocator talks
  • part 1: https://www.youtube.com/watch?v=nZNd5FjSquk
  • part 2: https://www.youtube.com/watch?v=CFzuFNSpycI
• Some high performance memory allocators are
  • tcmalloc
  • jemalloc
• Pool Allocators: https://blog.molecular-matters.com/2012/09/17/memory-allocation-strategies-a-pool-allocator/
• Our allocator works on the ‘heap’ working with dynamic memory. Other memory may work on the ‘stack’ which is for really hot code. Read up on alloca (in alloca.h) and see how one could implement a custom stack allocator.