Homework 3: Implement a Malloc Library (Part 1)

---

For this assignment, you have to write a malloc library that provides the following dynamic memory allocation routines (as defined in man 3 malloc):

       #include 

       void *malloc(size_t size);
       void free(void *ptr);
       void *calloc(size_t nmemb, size_t size);
       void *realloc(void *ptr, size_t size);
       void *reallocarray(void *ptr, size_t nmemb, size_t size);

       int posix_memalign(void **memptr, size_t alignment, size_t size);
       void *memalign(size_t alignment, size_t size);
      

Other relevant functions that are typically part of a malloc library should also be implemented as you find appropriate. Mention any additional functions that you have implement in your README. You have to implement a library that implements these functions to allocate and free dynamic memory.

You will need to know about memset and memcpy to implememt calloc and realloc respectively.

Allocation

---

1. buddy allocation: You would keep a list of free blocks that can be used to satisfy a given memory request.
2. Memory request:If no blocks are available on the free-list, you must ask kernel for more memory (using sbrk() systemcall). The memory request must always be multiple of PAGE_SIZE (use the sysconf(_SC_PAGESIZE) syscall). If sbrk fails, you must set errno to ENOMEM and return NULL;
3. Alignment: The returned address from malloc, calloc and realloc must be aligned at 8-byte boundary.
4. Thread Safety: The library should be thread-safe, i.e., it should use proper locks, etc., to allow multiple threads to allocation/free memory.

Testing

---

The hw3 directory contains a skeleton malloc.c, Makefile, and a basic test case.

Once you have everything ready, you can use the following benchmarks/tools to test out your malloc library.

• t-test1.c
• Hoard benchmarks
• Malloc Microbenchmark

Deliverables

---

Your submission should contain a file for each function wrapper (i.e. malloc.c, free.c, realloc.c, calloc.c, mallinfo.c, etc.) that contains definitions for malloc, free, realloc, calloc, mallinfo, etc. These file must not have main() and shouldn't have any debugging output. There should be separate header/C files for all utility functions. For example, all code to manage a linked list should be in a separate .c file with a corresponding .h file. A Makefile should be provided with a rule lib that generates libmalloc.so from this file.

You must also provide a README file that contains:

• Design overview: A brief description of your overall code structure; important data structures (e.g., the free-node list); approach for managing arenas; allocation scheme; and any other important details.
• Design decisions that you made.
• Known bugs and errors

Conventions

• One file per wrapper (malloc.c, free.c, etc.)
• Makefile that allows compiling individual units.

Debugging, Hints and Resources

---

Memory debuggers:

---

• Valgrind Memcheck
• DUMA

See Also

---

• alloca
• Lock-free data structures