# heaptest.shar # Shell archive made by dwjones on Wed Mar 28 21:48:46 CDT 2018 # To install this software on a UNIX system: # 1) create a directory (e.g. with the shell command mkdir heaptest) # 2) change to that directory (e.g. with the command cd heaptest), # 3) direct the remainder of this text to sh (e.g. sh < heaptest.shar). # This will make sh create files in your heaptest directory; it will do # nothing else (if you're paranoid, you should scan the following text # to verify this before you follow these directions). Then read README # in the new directory for additional instructions. cat > README <<\xxxxxxxxxx README by Douglas Jones, Mar. 28, 2018 This is a distribution of a heap implementation and test program written to launch work on MP5 in the Spring 2018 offering of CS:3620 The component files are: README -- this file xmalloc.h -- the interface definition for xmalloc() and xfree() xmalloc.c -- the implementation of xmalloc() and xfree() main.c -- the main program to test xmalloc() and xfree() Makefile -- build heaptest from the above The xmalloc() and xfree() functions are comparable to the C standard malloc() and free() functions. The implementation distributed here is terrible: It works, but adjacent free blocks are never merged, so it suffers from severe heap fragmentation and also, it operates using a linear search through all blocks in the heap without using any auxiliary free-list data structure. The implementation distributed here uses a boundary-tag implementation of the heap, with 2 words per tag holding pointers to the next and previous blocks in the heap. The least significant bit of one tag is used to mark blocks as being free or in use. As distributed, the heap implementation in xmalloc.c fails the test imposed by main.c because the initial heap is exactly one word too small. Any success in merging free blocks will make this code pass the test. Read the Makefile for information on how to build the heaptest program. xxxxxxxxxx cat > xmalloc.h <<\xxxxxxxxxx /* xmalloc.h * xmalloc and xfree interface * originally by Douglas Jones, Mar. 28, 2018 */ void * xmalloc( int size ); void xfree( void * p ); xxxxxxxxxx cat > xmalloc.c <<\xxxxxxxxxx /* xmalloc.c * xmalloc and xfree implementation * originally by Douglas Jones, Mar. 28, 2018 * * This verion never merges free blocks. * This verion always searches through all blocks from the bottom of the heap. */ #include /* needed for NULL */ #include /* needed for sbrk() */ #include /* needed for intptr_t */ #include "xmalloc.h" /* force compatability with header file */ /* the heap size */ /* under our test 10000 is always safe. For this, 6913 works, 6912 doesn't.) */ #define HEAPSIZE 6912 /* description of boundary tag structure based on homework 9 problem 3 */ #define TAGSIZE ( 2*sizeof(void *) ) #define USED 1 #define FREE 0 /* private memory addressing functions used only in tag manipulation */ #define _PNEXT(p) ((intptr_t)(p) - sizeof(void *)) #define _PPREV(p) ((intptr_t)(p) - 2*sizeof(void *)) /* public functions to access fields of boundary tags */ /* get field values */ #define GETNEXT(p) ( (void *)( *(intptr_t *)_PNEXT( p ) & ~1 ) ) #define GETPREV(p) ( *(void **)_PPREV( p ) ) #define GETUSED(p) ( *(intptr_t *)_PNEXT( p ) & 1 ) #define GETSIZE(p) ( ((intptr_t)GETNEXT( p ) - (intptr_t)(p)) - TAGSIZE ) /* set field values */ #define SETNEXT(p, next) ( \ *(intptr_t *)_PNEXT( p ) = \ (*(intptr_t *)_PNEXT( p ) & 1) | (intptr_t)(next) \ ) #define SETPREV(p, prev) ( *(void **)_PPREV( p ) = (prev) ) #define SETUSED(p, used) ( \ *(intptr_t *)_PNEXT( p ) = \ (*(intptr_t *)_PNEXT( p ) & ~1) | (used) \ ) /* public function to round integer byte counts up to a word boundary */ #define ROUNDUP(i) ( ((i) + (sizeof(void *) - 1)) & ~(sizeof(void *) - 1) ) /* the first byte of the heap */ void * heap = NULL; void * xmalloc( int size ) { /* make sure we have a heap with a tag at each end */ if (heap == NULL) { /* the initial heap has a boundary tag at each end */ int heapsize = ROUNDUP( HEAPSIZE ); heap = (void *)( (intptr_t)sbrk( heapsize + 2*TAGSIZE ) + TAGSIZE ); /* heap points to the first block on the heap */ void * end = (void *)((intptr_t)heap + heapsize + TAGSIZE); SETPREV( heap, NULL ); SETNEXT( heap, end ); SETUSED( heap, FREE ); SETPREV( end, heap ); SETNEXT( end, NULL ); SETUSED( end, USED ); /* used so nobody ever tries to use it */ } /* round size up to the next multiple of a pointer size */ size = ROUNDUP( size ); /* search for a big enough free block */ void * p = heap; while (p != NULL) { void * next = GETNEXT( p ); if ((GETUSED( p ) == FREE) && (GETSIZE( p ) >= size)) { /* we found a big enough block */ if (GETSIZE( p ) > (size + TAGSIZE)) { /* the block is big enough to split */ void * new = (void *)( (intptr_t)p + size + TAGSIZE ); SETNEXT( new, next ); SETPREV( new, p ); SETUSED( new, FREE ); SETNEXT( p, new ); SETPREV( next, new ); } SETUSED( p, USED ); return p; } p = GETNEXT( p ); } /* control only reaches here if there is no big enough free block */ return NULL; } void xfree( void * p ) { SETUSED( p, FREE ); } xxxxxxxxxx cat > main.c <<\xxxxxxxxxx /* main.c * Main program to test malloc and free * originally by Douglas Jones, Mar. 27, 2018 */ #include /* needed for NULL, fputs() */ #include /* needed for random(), exit() */ #include /* needed for intptr_t */ #include "xmalloc.h" /* constants that determine the demand on the heap */ #define BLOCKS 100 #define MAXSIZE 100 #define TRIALS (BLOCKS * 10) /* the maximum demand this poses is MAXSIZE * BLOCKS = 10000 the average demand will be MAXSIZE/2 * BLOCKS/2 = 2500 the first BLOCKSIZE trials barely approach the steady state, so do more! */ void * blockpile[BLOCKS]; int main( int argc, char * argv[] ) { int i; /* initialize */ for (i = 0; i < BLOCKS; i++) blockpile[i] = NULL; /* now put a load on the heap */ for (i = 0; i < TRIALS; i++) { int block = random() % BLOCKS; if (blockpile[block] == NULL) { /* allocate a block */ int size = (random() % MAXSIZE) + 1; blockpile[block] = xmalloc( size ); /* verify that we got a block */ if (blockpile[block] == NULL) { fputs( "MALLOC FAILURE\n", stderr ); exit( EXIT_FAILURE ); } /* now scribble on the allocated block */ void * index = blockpile[block]; while (size > 0) { * (int *)index = size; size = size - sizeof(int); index = (void *)((intptr_t)index + sizeof(int)); /* or index = (void *)((int *)index + 1); */ /* or index = (void *)&((int *)index)[1]; */ } } else { /* verify that the scribbles are unchanged */ void * index = blockpile[block]; int size = * (int *)index; while (size > 0) { if (size != * (int *)index) { fputs( "CORRUPTED BLOCK\n", stderr ); exit( EXIT_FAILURE ); } size = size - sizeof(int); index = (void *)((intptr_t)index + sizeof(int)); } /* and then deallocate the block */ xfree( blockpile[block] ); blockpile[block] = NULL; } } fputs( "SUCCESS\n", stderr ); } xxxxxxxxxx cat > Makefile <<\xxxxxxxxxx # Makefile # make -- makes a test for a self-made heap implementation # make heaptest -- makes a test for a self-made heap implementation # make clean -- deletes all files created by make # # by Douglas Jones for MP5 in CS:3620, Mar. 28, 2018 # primary make target heaptest: main.o xmalloc.o cc -o heaptest main.o xmalloc.o # subsidiary make targets main.o: main.c xmalloc.h cc -c main.c xmalloc.o: xmalloc.c xmalloc.h cc -c xmalloc.c # utility make targets clean: rm -f *.o mush xxxxxxxxxx