For this assignment, you will be writing a memory allocation library called libmalloc. This library should provide basic heap memory management features.

Required Features

The required interface for your library is as follows,

void *allocate(size_t) 
  Returns a pointer to an available region of heap memory of a specified number of bytes. 
  If the allocation fails for some reason, return NULL instead. This function should use 
  the sbrk syscall to grow the heap as needed, and should prioritize allocating memory 
  from the free list if possible.

  Returned pointers must be aligned to a 16 byte boundary and the allocated region must
  be within the programs heap.

  
void release(void*)
  Frees a region of memory allocated by the allocate function by adding it to the free 
  list. This function should also handle coalescing contiguous memory regions on the 
  free list at the time of release.

  You may assume that the input argument is a pointer that has been returned by
  allocate, and has not already been released.
  

typedef struct freelist_hdr freelist_hdr;
  A struct for the header of memory regions on the free list. This type should
  *not* be opaque externally to the library, and can be used for testing

  
freelist_hdr *list_head()
  Returns a pointer to the head of the free list--can be used for testing

Other Requirements

Beyond the required interface, there are a few constraints on how your implementation must function.

1. Do not use any heap memory management libraries, including the standard library's implementations of malloc, free, etc. You must do all memory management manually, yourself. The only memory management function you can call is sbrk
2. If there exists space on the free list to service an allocation, you must use that space rather than growing the heap. 
3. You should include a C program which imports and tests your library in your submission. You do not need to use a unit test framework, though you may use check if you like.
4. Your submission should include the following,
   1. A Makefile for building a static library, as well as the test binary
   2. An include file for your library

Hints

1. Read Chapter 17 of the textbook. It provides near step by step instructions for this project.
2. You can get the initial memory address for the start of the heap by calling sbrk(0).
3. Not being able to use heap memory within your library will feel quite limiting. You will need to make generous use of global variables to track the necessary state information. 
4. C doesn't provide a mechanism for automatic module initialization. Because this library doesn't include an explicit init() function in its API, you will need to piggyback initialization on the first call to allocate(). Consider using a global variable to track whether the library has been initialized yet.
5. You can use subtraction on a pointer to embed headers prior to heap memory addresses. Just be careful to ensure that your library doesn't clobber these headers accidentally. 

Grading Criteria

Submissions will be graded on the following criteria,

Library Correctness (30 pts)

Testing (10 pts)

Code Quality (10 pts)