Description

David Menendez
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 test plan, describing:
(a) What properties your library must have for you to consider it correct
(b) How you intend to check that your code has these properties
(c) The specific method(s) you will use to check each property
Submit all files to Canvas in a single Tar archive.
1 Background
1.1 Memory fragmentation
Consider a case where we repeatedly call malloc() and request, say, 20-byte chunks until all of memory has been used. We then free all these chunks and request a 40-byte chunk. To fulfil this request, we must coalesce two adjacent 20-byte chunks into a single chunk that will have at least 40 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.2 Your implementation
Your mymalloc.c will allocate memory from a global array declared like so: static char memory[4096];
The use of static will prevent client code from accessing your storage directly. You are free to name the array something else, if you prefer. It is recommended that you use a macro to specify the array length and use that macro throughout, to allow for testing scenarios with larger or smaller memory banks.
In other words: both the chunks provided to client code and the metadata used to track the chunks must be stored in your memory array.
Do not be fooled by the type of the array: all data is made up of bytes, and an array of chars is just an array of bytes. The address of any location in the array can be freely converted to a pointer of any type.
The simplest structure to use for your metadata is a linked list. Each chunk will be associated with the client’s data (the payload) and the metadata used to maintain the list (the header). Since the chunks are continuous in memory, it is enough for the header to contain (1) the size of the chunk and (2) whether the chunk is allocated or free. Given the location of one chunk, you can simply add its size to the location to get the next chunk. The first chunk will always start at the beginning of memory.
Note the pointer returned by malloc() must point to the payload, not the chunk header.
Note that your memory array, as a global variable, will be implicitly initialized to all zeros. Your malloc() and free() functions must be able to detect when they are running with uninitialized memory and set up the necessary data structures. You are not permitted to require clients to call an initialize function before calling malloc().
2 Detectable errors
The standard malloc() and free() do no error detection, beyond returning NULL if malloc() cannot find a large enough free chunk to fulfil the request.
In addition, your library must detect and report these usage errors:
1. Calling free() with an address not obtained from malloc(). For example,
int x; free(&x);
2. Calling free() with an address not at the start of a chunk.
int *p = malloc(sizeof(int)*2); free(p + 1);
3. Calling free() a second time on the same pointer.
int *p = malloc(sizeof(int)*100); int *q = p;
free(p); free(q);
3 Reporting errors
We will use features of the C pre-processor to allow malloc() and free() to report the source file and line number of the call that caused the error. To do this, your “true” functions will take additional parameters: the source file name (a string) and line number (an int).
Use these function prototypes and macros in your mymalloc.h:
void *mymalloc(size_t size, char *file, int line); void free(void *ptr, char *file, int line);
#define malloc(s) mymalloc(s, __FILE__, __LINE__)
#define free(p) myfree(p, __FILE__, __LINE__)
The C pre-processor will replace the pseudo-macros __FILE__ and __LINE__ with appropriate string and integer literals, which will give your functions the source locations from which they were called.
Note that we are stealing the names of functions defined in the standard library. For this reason, make sure that mymalloc.h is included later than stdlib.h. For example,
#include <stdlib.h>
#include “mymalloc.h”
The content and format of your error messages is up to you. Describe your design in your project’s README file.
4 Testing
Include a file memgrind.c that includes mymalloc.h. The program should perform the following tasks:
1. malloc() and immediately free() a 1-byte chunk, 120 times.
2. Use malloc() to get 120 1-byte chunks, storing the pointers in an array, then use free() to deallocate the chunks.
3. Randomly choose between
• Allocating a 1-byte chunk and storing the pointer in an array
• Deallocating one of the chunks in the array (if any)
Repeat until you have called malloc() 120 times, then free all remaining allocated chunks.
4. Two more stress tests of your design. Document these in your README.
5 Grading
Grading will be based on
• Correctness: whether your library operates as intended
• Design: the clarity and robustness of your code, including modularity, error checking, and documentation
• The thoroughness and quality of your test plan