This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.
author: burton rosenberg
created: 21 nov 2017
update: 22 nov 2017
NAME
mymalloc, myfree, mymalloc_init, myalloc_free
SYNOPSIS
#include "mymalloc.h"
void * mymalloc(unsigned int len)
void myfree(void * ptr)
unsigned int mymalloc_init()
unsigned int mymalloc_free()
DESCRIPTION
On success mymalloc returns a pointer to len bytes; else returns NULL. When
passed a pointer previously returned by mymalloc, myfree returns the storage
for future use by malloc.
Before any calls to the mymalloc program, call mymalloc_init. Mymalloc_free
returns the current number of bytes free in the heap.
RETURN VALUE
mymalloc returns pointer to len bytes, or NULL. myalloc_init returns the heap
size, as does myalloc_free.
NOTES
To use, link against mymalloc.a.
BUGS
The template files in [repo]/class/quiz/quiz3 define the basic scheme, as was presented in class. The free list is a linked list of regions of free memory. Each region of free memory is represented by a struct FN. The len field gives the length of the region, and the struct is situated aligned with the fist byte of the region. No free region can be of len less than the size of the struct FN. The structs are linked by their next fields. A null value for next signals the end of the list.
There is always a dummy header at the front of the free list. It consists of a struct FN, with length set to zero. This is true even though it actually consumes sizeof(struct FN) bytes. The next field of the dummy points to the first usable free region, which initially spans the entire remaining bytes of the heap. Mymalloc_free returns the entire size of the heap, including the bytes taken by the dummy header. The template has code for the construction of the initially empty free list, and the code for mymalloc_free.
When allocating, your implementation must allocate from the lowest byte address in memory that has the space to satisfy the allocation. The returned pointer is advanced beyond the len field, which is retained so that myfree knows how much space to return.
Your implementation must allocate the smallest number of bytes needed and from the lowest byte address available. The template code demonstrates this requirement. The amount actually allocated is the greater of the size of a struct FN or the requested amount plus the size of the len field in the struct FN.
In order to agree with the automated tests, your free list should be kept with regions in ascending byte address order, and no two regions consecutive on the free list should be contiguous, i.e. all such contiguous free regions must be merged. The exception to this is that the dummy header is never merged.
Find programs in [repo]/class/quiz/quiz3, to copy to your [repo]/[username]/quiz/quiz3 folder and complete. I believe you only need to work with the file mymalloc.c, but you are responsible for understanding all the code.
A test has been provided. I remind you that the actual graded result is a working program. I have set up the so-called basic tests and will generally award partial credit on the passing of the basic test, but these tests are decidedly not enough. I try to create test jigs that make it easy for you to come up with you own tests, based on the knowledge you have with your own code, and what design issues you believe must have confirmation through testing.
author: burton rosenberg
created: 21 nov 2017
update: 22 nov 2017