Machine Problem 5, due Apr. 20

Assignment: Implement routines called mymalloc() and myfree() that conform to the behavior of malloc() and free(). These should allocate memory from a statically allocated block of 16384 bytes of memory (which is 4096 32-bit words). Your solution should be in a file called mp5.c.

Your code should use the following header file:

       # mymalloc.h
       # interface definition for heap manager
       void * mymalloc(int size);
       void myfree(void * ptr);

You are responsible for testing your code. The main program should be separately compiled from the test. You may use but need not use a makefile. Your main program will not be turned in. Just turn in, as a single source file, your implementation of the above routines.

Your program must use some dynamic allocation scheme that maintains free its free list or free lists and other data structures in your heap. You are only permitted to maintain small set of pointers outside the heap, used to find the heap and traverse the lists in the heap. Your heap implementation may not use malloc() to allocate auxiliary data structures.

One appropriate way to test the heap is with a random pattern of allocation and deallocation. Consider, for example, an inner loop in a test program that operates as:

       i = random() % BLOCKS;
       if (block[i] == NULL) {
              int size = random() % MAXSIZE;
              block[i] = mymalloc( size );
              /* add code here to initialize the block */
       } else {
              /* add code here to check that the block has not
                 been changed since it was initialized */
              free( block[i] );
              block[i] = NULL;
       }

It would make sense to test the test program by using malloc() and free() to get it working and then switch to your versions.

Grading will focus on style as much as function, so working code will not earn more than half credit unless it is clear and readable, and clean code will earn some credit even if not functional.

As usual, submit your solution using ICON.

Hint: The interface does not include an initializer! This poses problems you can solve as follows: Your static data structures pointing to the heap can include a variable statically initialized to zero or NULL (for example, the pointer to the base of a boundary tag heap, or just a boolean saying "initialized yet?"). On entry to malloc(), if this variable is in its initial state, call your own initializer and set the variable to its "already initialized" value.

An issue: What if someone passes a pointer to an object outside your heap to myfree()? It would be appropriate to detect this error so that, at the very least, you can avoid corrupting your heap if someone does this. This is an example of an "edge case" where a more refined version of the specifications would state the specific response required (probably something like raising an exception).