Malloc Tests Lab

CS 3410 Spring 2019

---

Lab 12 (5 malloc tests) Due: 11:59pm, Sunday, April 28, 2019

---

In this assignment, you will first read over the specs of a dynamic memory allocation library that supports the allocation, freeing, and resizing of blocks of memory. You will write a suite of tests that can be used to test an implementation of a dynamic memory allocation library and determine if it was implemented to specfications-correctly and robustly. You will need to put your problem-solving skills to work!

Then you will write your own implementation of a dynamic memory allocation library, that supports the allocation, freeing, and resizing of blocks of memory. Your implementation should be correct and robust, which you should be able to run your tests on. Lastly, we will be comparing your implementation of Malloc to your classmates' in a race for the best and fastest Malloc!

You can find the file for this lab in your Github repository. Be sure to make good use of git with all of its features!

What to submit

For Lab 12 upload tests.c to CMS. An autograder will provde you with pre-deadline feedback.

If you receive a file that looks like this

============================

This is a compilation error.

The Specs

This section describes the specifications of the dynamic memory allocation library you will write for Project 6 * Malloc.

By now you should be familiar with static vs dynamic allocation. Statically allocated memory is allocated on the stack and exists only for the life of the function in which it was allocated; dynamically allocated memory is allocated on the heap and exists from the moment it is allocated until it is explicitly freed. Support for dynamic memory allocation is part of the Standard C Library.

A dynamic memory allocator maintains the memory associated with the heap. The most basic task will be to keep track of which bytes of the heap are currently in use (i.e., are allocated) and which bytes are not in use (i.e., free). On real systems, the heap can grow with the needs of a process. For this assignment, however, we will consider the heap to be a fixed-size block of memory. The functions you implement will take a void *heapptr argument that points to the beginning of the heap that you must manage. (Of course the heap here being pointed to by heapptr is a simulated version of the actual heap that the C Standard Library manages.) Your dynamic memory allocator will consist of the following four functions, which are declared in heaplib.h and will be implemented (by you) in heaplib.c in P6 * Malloc, but for now you will be testin.

int hl_init(void *heapptr, unsigned int heap_size)

Sets up a new heap beginning at heapptr and of size heap_size (in bytes). Note that your hl_init function does not actually need to allocate or create the heap. It is given a block of memory of the correct size, starting at the location pointed to by heapptr. (The test cases we provide will show you a few ways in which this block of memory can be created.) The hl_init function should be called once before there are any calls to hl_alloc, hl_release, or hl_resize.

Your memory allocator must live entirely inside the heap it is managing. This means that all meta-data (pointers, size fields, flags indicating free or in-use) must all live in the heap itself. You may not use any global arrays, variables, or structures. A good test of this is whether your implementation supports multiple heapptrs. Your code should naturally support multiple heaps.

Do not assume that heapptr is 8-byte aligned.

If heap_size is not large enough to hold the meta-data required to manage the heap (as you have designed it), setup fails, and the function returns 0. Returns non-zero if successful.

void *hl_alloc(void *heapptr, unsigned int block_size)

Allocates a block of memory of size block_size bytes from the heap pointed to by heapptr.

Returns a pointer to the block of memory on success; returns 0 (NULL) if the allocator cannot satisfy the request.

Blocks of memory can be of size 0. The returned address should be aligned at multiples of 8 bytes. The function is allowed to allocate more than the requested size, but never less. The memory "allocated" by this function does not need to be zeroed out.

void hl_release(void *heapptr, void *blockptr)

Frees the block of memory pointed to by blockptr (that currently resides in the heap pointed to by heapptr). If blockptr has the value 0 (NULL), the function should do nothing. (If it has some non-zero value that was never the return value of a call to hl_alloc or hl_resize, the program behavior is undefined. You need not fail gracefully.) For utilization purposes, released memory should be able to be allocated again by subsequent calls to hl_alloc.

The memory released by this function does not need to be zeroed out.

void *hl_resize(void *heapptr, void *blockptr, unsigned int new_block_size)

Changes the size of the memory block pointed to by blockptr (that currently resides in the heap pointed to by heapptr) from its current size to size new_block_size bytes, returning a pointer to the new block, or 0 if the request cannot be satisfied. the contents of the block should be preserved. If the location of the block changes (because it is not possible to make the block pointed to by blockptr larger and a new, larger block elsewhere needs to be used), you can copy the contents by using memcpy or cast blockptr to a char * and copy the contents byte by byte.

The new block size might be smaller than the current size of the block. As it was for hl_alloc, the return value should be 8-byte aligned. If blockptr has the value 0 (NULL), the function should behave like hl_alloc.

Note: Your functions hl_alloc(), hl_release(), and hl_resize() correspond to the actual C Standard Library functions malloc(), free(), and realloc(). Nowhere in heaplib.c should you call these three library functions.

Compiling and Running Your Code

You have will be given the following files as part of P6 * Malloc (tests.c is the only one you will work on for Lab 12):

• heaplib.h -- contains the interfaces of the functions you are to test and implement
• heaplib.c — this is the file containing your implementation
• tests.c — this is the file containing your test suite
• compile.sh — this is how you will compile your malloc implemenation
• run_each_tests.sh — this is how you will run your malloc implemation against tests
• spinlock.h — this contains the headers for the spinlock you are to implement
• spinlock.c — this is the file containing the spinlock you should implement with RISCV assembly

The heart of this assignment is your implementation of the functions declared in heaplib.h. You are implementing a library, which does not contain a main. The tests.c file uses your library. The test file will contain many test files but will not be exhaustive. You should consider implementing some of your own tests. You should be prepared to do this after your lab.

Completing Tests for Correctness

Testing is a huge part of writing good code and will be a significant part of your grade for this assignment.

You will begin writing a series of tests that check to see whether an implementation of this dynamic memory allocation library was done correctly. We have prepared approximately 13 broken malloc implementations that do not meet the specs in some way. Your task is to write tests that accurately flag these broken versions as broken while at the same time accurately flagging a correct implementation as correct.

For lab 12, you will only need to write the first 5 of these tests, located in tests.c. (Feel free to add additional tests). You can implement the rest of the tests on your own to test the validity of your malloc implementation in Project 6.
For lab 12 only, you will have unlimited runs of the autograder, so that you can become familiar with how this system will work.

tests.c is intended to be a thorough test for the correctness of any heaplib implementation. At the moment, however, it only tests three things:

• whether hl_init works
• whether hl_alloc fails when there is not enough space
• whether the pointer returned by hl_alloc is 8 byte aligned

There are many more possible correctness problems. Modify tests.c to catch the first five of them. (The fixed code will be helpful for your heaplib.c.)

The goal is to convince yourself that your code is correct. Try to come up with a number of cases that really stress your allocation functions. It's a good idea to test corner cases as well. For example, create a test that uses two different heapptr pointers to two different chunks of memory. Make sure that a user is never given permission to write past the end of the heapptr associated with any allocation request. (Note: a user could always write past the heapptr, but if a user requests 32 bytes and is given a pointer to the very last byte in the heapptr, this is a correctness problem. Similarly, a user should never be given permission to write into memory that was already reserved (and not freed) in a previous call to hl_alloc. Think about how you might test whether data in a block is preserved over time.

When you have completed tests.c it should report the first five of the correctness problems with a broken implementation of malloc. You will submit this file to CMS. Each submission will trigger an automatic autograder run and you will receive an email with the result of your tests running on our broken versions of malloc. This test will be graded on how thoroughly it tests the correctness of yours and our broken implementations of malloc and heaplib.c. Points will be deducted for false positives (finding errors where there are none) and false negatives (not finding errors when they are there).

What is correctness? For the purposes of this assignment, any error that would occur even in an infinite heap is considered a correctness error. For example, not guaranteeing pointer alignment is a correctness error. Not implementing hl_release will be considered a utilization error, not a correctness error.

What constitutes as flagging as broken? You can either return FAILURE from your test function, or you can have the code SEGFAULT. The second option may seem unintuitive at first, but it is helpful to realize that if an implementation of malloc is indeed broken, it will have bad behavior such as SEGFAULT.

Note that your tests should not flag a working malloc as broken.

A thorough correctness test will not only earn you points and glory, but it will be invaluable in finishing subsequent tasks for this assignment.

Grading

Lab 12 will be graded on catching all 5 broken mallocs using the first 5 test cases, but we highly encourage you to implement as many malloc tests as you can since they will be instrumental in testing your malloc implementation in Project 6 * Malloc.