2 Implementing a heap memory allocator library

The heap memory allocator library is used to allocate and manage a (large) chunk of heap memory
that is pre-allocated from the system. Your job here is to implement the functionalities of free-
space management you learned in class which include:

• managing allocated memory blocks;

• managing free blocks using free list;

• supporting different memory allocation policies for the free-list-based free memory manage-
ment, such as first-fit allocation and best-fit allocation; and

• detecting invalid free requests (e.g., double free) and allocated block corruption.

The following library functions are provided by this library.

(1) int my mem allocator init(void): function to initialize the memory allocator.

(2) void my mem allocator destroy(void): function to deconstruct the memory alloca-
tor.

(3) void set alloc policy(ALLOC POLICY policy): function to set the memory alloca-
tion policy.

(4) void *my malloc(size t size): function to allocate heap memory, which is similar to
the malloc() function provided in a C library.

(5) void my free(void *ptr): function to free an allocated block of memory, which is sim-
ilar to the free() function provided in a C library.

(6) void *my realloc(void *ptr, size t size): function to change an allocated block
of memory, which is similar to the realloc() function provided in a C library.

The above library functions are implemented in the following files of the base code.

2.1 File my mem allocator.c

This file implements the first three library functions above and some helper functions which are
used in the test code. The library functions implemented in this file are explained as follows.

• my mem allocator init() initializes the memory allocator by pre-allocating a chunk

of heap memory, which is the memory space this allocator manages, using the system
malloc() function. The size of the pre-allocated memory is configured by the MY HEAP SIZE
macro. Then it constructs the free list by inserting a giant free block which contains all the
usable memory.
The header structure of a free block is defined in my mem allocator.h:

2
 // free/allocated block header
typedef struct _block_header{
int size; // for free block: size of the usable space in the free block
// for allocated block: size of the mem space returned to user
void * next; // for free block: pointer to the next free block
// for allocated block: magic number
}BLOCK_HDR;

Note that allocated blocks share the same header structure as free blocks. Re call that we
have discussed how free blocks and allocated blocks are converted to each other as blocks
are allocated/freed.

• my mem allocator destroy() deconstructs the memory allocator by calling the system
free() function on the pre-allocated heap memory space.

• set alloc policy() sets the memory allocation policy: first fit or best fit.

The above functions have been implemented. The helper functions for test code are also imple-
mented in this file. You may read the implementations of the helper functions and how they are
used in the test code to help you better test your implementation.

Do not add your implementation to this file (i.e., my mem allocator.h ) and
my mem allocator.h. When grading, these two files will be replaced with the original ones.

2.2 File my malloc.c

Your implementtion of the my malloc() function goes here. If none of the free blocks in the free
list is large enough to satisfy an allocation request, report such an error and return NULL to the
caller. Otherwise return the address of the space allocated to the caller.

When the allocator allocates space of a requested size from a free block, there are two scenarios
which should be taken care of as follows:

• If the remaining space in the free block is enough to accommodate a block header plus one
byte, the free block should be split into an allocated block as requested and a new free block.
Refer to the next subsection for the requirements of how a new free block should be added
to the free list.

• Otherwise, the whole free block can be used to satisfy the allocation request (i.e., splitting
is not needed).

When splitting is needed, the allocated space is taken from the front of the free block, which is
the same as the example shown in class. Please refer to the course slides and the textbook chapter
for the details.

The allocator should support two different allocation policies for selecting a free block: first fit,
which is the default, and best fit. Again, please refer to the course slides and the textbook chapter
if you forget the details.

3
2.3 File my free.c
Your implementtion of the my free() function goes here. When a allocate block is freed, it
is turned to a free block and is added to the free list. The following to requirements should be
satisified when adding a free block to the free list:

• The free blocks in the free list should be sorted from low to high based on their addresses all
the time. In other words, the free block should be inserted to the free list in an address-
ascending manner.

• After a free block is added to the free list, if it is adjacent to its neighboring block(s) in
space, coalecging should be performed to turn the blocks to a larger one.

Your implemenation of the my free() should be able to detect free anormalies, such as double
free, invalid free address, and header corruption, by using the magic number. We have discussed
this technique in details in class.

2.4 File my realloc.c

Your implementtion of the my realloc() function goes here.

void *my realloc(void *ptr, size t size) behaves similarly to the

void *realloc(void *ptr, size t size), which changes the size of the memory block
pointed to by ptr to size bytes and returns the address of the new block to the caller. Here
you only need to take care of the following two scenarios:

• If the new size is smaller than the originial size, return the orginial address of the allcoated
space to the caller. If the difference between the original size and the new size is enough
to hold a block header plus one byte, change the allocated block to the new size, turn the
freed-up space to a new free block and add it to the free list. Otherwise, nonthing needs to
be done on the allocated block for the realloc request.

• If the new size is larger than the original size, allocate the requested space from a free block,
which should be selected using the first fit policy, following the same way of my alloc().
Then copy the content of the old allcated space to the new one, free the old allocated space,
and return the address of the new allocated space to the caller.

(Continue to next page ...)

4
3 Testing your implementatioin
The test code has been given in the base code. We will use the same test cases for grading except
that we may change memory allocation request sizes in some of the test cases. The test cases are
summarized as follows. You may read the code for the details of different test cases.

• test1-4.c implements test cases 1 to 4, which test normal mallocs, normal frees without
coalescing, and normal frees with coalescing.

• test5-7.c implements test cases 5 to 7, which test the two allocation policies.

• test8-10.c implements test cases 8 to 10, which test different anormaly situtations of
malloc and free.

• test11-14.c implements test cases 11 to 14, which test the my realloc() implemen-
tation.

A sample memory allocator library (“my mem lib sample.a”) implemented by the instructor
is provided with this project specification in Brightspace. You can use the Makefile provided in
the Brightspace to link the (provided or your own) test code with the sample library to see what
the expected outputs are for different test cases.

(Continue to next page ...)