for this assignment, you will implement your own versions of the standard library functions

malloc$()$ and free$().$ Unlike the standard implementations, your versions will detect common

usage errors and report them.

For this assignment, you will create

$1.$ A library mymalloc.c with header mymalloc.h$,$ containing the functions and macros described

below.

$2.$ A program memgrind.c that includes mymalloc.h$.$

$3.$ Additional test programs that include mymalloc.h$,$ along with the necessary Make$-$files for

compiling these programs.

$4.$ A README file containing the name and netID of both partners, your test plan, descriptions

of your test programs $($including any arguments they may take$),$ and any design notes you

think are worth pointing out. This should be a plain text file.

Submit all files to Canvas in a single Tar archive. Place all files in a directory called $$P$1.$

We should be able to run the following commands as written $($aside from the name of the archive$)$:

$ tar $-$xf p$1.$tar

$ cd P$1$

$ make

$ $./$memgrind

$1$ Background

The heap is a region of memory managed by the run$-$time system through two functions, malloc$()$

and free$(),$ which allocate and deallocate portions of the heap for use by client code.

We will model the heap as a sequence of variably sized chunks, where a chunk is a contiguous

sequence of bytes in the heap and all bytes in the heap belong to exactly one chunk. Each chunk has

a size, which is the number of bytes it contains, and may be either allocated $($in$-$use$)$ or deallocated

$($free$).$

The number and sizes of the chunks is expected to vary over the run$-$time of a program. Large

chunks can be divided into smaller chunks, and small chunks can coalesce into larger chunks.

$1$

We can further model a chunk as having two parts. The header contains information the run$-$time

system needs to know about a chunk, such as its size and whether it is allocated. The payload

contains the actual object that will be used by client code. We say that the payload contains data,

and the header contains metadata.

Note that an object is itself a contiguous sequence of bytes, meaning that the run$-$time system

cannot intermix data and metadata.

To ensure smooth operation, the run$-$time system and the client code must operate by certain

rules:

$1.$ On success, malloc$()$ returns a pointer to the payload of an allocated chunk containing at

least the requested number of bytes. The payload does not overlap any other allocated chunks.

$2.$ The run$-$time system makes no assumptions about the data written to the payload of a chunk.

In particular, it cannot assume that certain special values are not written to the payload. In

other words, the run$-$time cannot extract any information by looking at the payload of an

allocated chunk. Conversely, clients may write to any byte received from malloc$()$ without

causing problems for the run$-$time system.

$3.$ The run$-$time system never writes to the payload of an allocated chunk. Client code may

assume that data it writes to an object will remain, unchanged, until the object is explicitly

freed.

$4.$ The run$-$time system never moves or resizes an allocated chunk. $1$

$5.$ The client never reads or writes outside the boundaries of the allocated payloads it receives.

The run$-$time system can assume that any data it writes to chunk headers or to the payloads

of unallocated chunks will be not be read or updated by client code.

malloc$()$ is called with a single integer, indicating the requested number of bytes. It searches

for a free chunk of memory containing at least that many bytes. If it finds a chunk that is large

enough, it may divide the chunk into two chunks, the first large enough for the request, and returns

a pointer to the first chunk. The second chunk remains free.

free$()$ is called with a single pointer, which must be a pointer to a chunk created by malloc$().$

free$()$ will mark the chunk free, making it available for subsequent calls to malloc$().$

$1\mathrm{.}1$ Coalescing free chunks

Consider a case where we repeatedly call malloc$()$ and request, say, $24-$byte chunks until all of

memory has been used. We then free all these chunks and request a $48-$byte chunk. To fulfil this

request, we must coalesce two adjacent $24-$byte chunks into a single chunk that will have at least $48$

bytes.

Coalescing can be done by malloc$(),$ when it is unable to find space, but it is usually less

error$-$prone to have free$()$ automatically coalesce adjacent free chunks.

$1$Functions like realloc$()$ that explicitly move or resize chunks are permitted, but malloc$()$ and free$()$ by

themselves must never change existing allocated chunks.

$2$

$1\mathrm{.}2$ Alignment

C requires that pointers to data are properly aligned : pointers to $2-$byte data must be divisible by $2,$

pointers to $4-$byte data must be divisible by $4,$ and so forth. We will assume that the largest data

type our programs will use has $8-$byte alignment. To ensure that any object allocated by malloc$()$

has $8-$byte alignment, we