Malloc Lab

In this lab you will be writing a dynamic storage allocator for C programs, i.e., your own version of the malloc, free and realloc routines. You are encouraged to explore the design space creatively and implement an allocator that is correct, efficient and fast.

• The only file you will be modifying and handing in is mm.c.
• The mdriver.c program is a driver program that allows you to evaluate the performance of your solution.
• Use the command make to generate the driver code and run it with the command ./mdriver -V. (The -V flag displays helpful summary information.)

How to Work on the Lab

Your dynamic storage allocator will consist of the following four functions, which are declared in mm.h and defined in mm.c.

int mm_init(void);
//return value should be -1 if there was a problem in performing the initialization, 0 otherwise

void *mm_malloc(size_t size);
// returns a pointer to an allocated block payload of at least size bytes.

void mm_free(void *ptr);
//frees the block pointed to by ptr. It returns nothing

void *mm_realloc(void *ptr, size_t size);
//returns a pointer to an allocated region of at least size bytes with the following constraints.

Heap Consistency Checker

You will find it very helpful to write a heap checker that scans the heap and checks it for consistency.

• Your heap checker will consist of the function int mm_check(void) in mm.c.
• This consistency checker is for your own debugging during development. When you submit mm.c, make sure to remove any calls to mm_check as they will slow down your throughput.

Support Routines

You can invoke the following functions in memlib.c:

void *mem_sbrk(int incr);
void *mem_heap_lo(void);
void *mem_heap_hi(void);
size t mem_heapsize(void);
size t mem_pagesize(void);

The Trace-driven Driver Program

The driver program mdriver.c in the malloclab-handout.tar distribution tests your mm.c package for correctness, space utilization, and throughput.

Programming Rules

• You should not invoke any memory-management related library calls or system calls.
• You are not allowed to define any global or static compound data structures such as arrays, structs, trees, or lists in your mm.c program. However, you are allowed to declare global scalar variables such as integers, floats, and pointers in mm.c

Evaluation

Hints

• During initial development, using tiny trace files will simplify debugging and testing
• Don’t start working on your allocator until you understand everything about the simple implicit list allocator on the textbook

---

Tips

• arithmetic of pointers pointing tovoid will result in undefined behavior(in C standard), although in gcc void* is treated as char* when doing pointer arithmetic

---

My solution :

Simple implicit free list

+-----------+--------------+-----------+
| 4(header) | payload size | 4(footer) |
+-----------+--------------+-----------+

/*****************************************************************************/
/* single word (4) or double word (8) alignment */
#define ALIGNMENT 8

#define HFSize 4
#define HFTotalSize 8


/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)

//size_t* f(char *)
#define HeaderAddr(payloadptr)  ((size_t*)(payloadptr) - 1)
#define FooterAddr(payloadptr) ((size_t*)((payloadptr) + get_payload_size(payloadptr) ))

//size_t f( char *)
#define get_block_size(payloadptr) ( (*(HeaderAddr(payloadptr))) & ~0x7)
#define get_allocated_status(payloadptr) ( (*(HeaderAddr(payloadptr))) & 0x1)
#define get_payload_size(payloadptr) ((get_block_size(payloadptr) - (HFTotalSize) )) 


//char* f(void)
#define heap_end() (((char*)mem_heap_hi() + 1))

/*****************************************************************************/
//debug function heap checker


void printheap(void){
    char * walk = (char*)mem_heap_lo();
    char * end = (char*)mem_heap_hi() + 1 ;
    printf("\nHeap start at : %p\n" , walk );
    while ( walk < end ){
        size_t* hf = (size_t*)walk ;
        printf("\nHeader : [%p] = %zu\n" , hf , *hf);
        char * pptr = (char*)(hf + 1) ;
        size_t psize = get_payload_size(pptr);
        size_t bsize = get_block_size(pptr);
        printf("psize : %zu , bsize : %zu\n" , psize , bsize );
        /*for (size_t cot = 0 ; cot < psize ; cot++){*/
            /*printf("Byte [%zu] : %d\n" , cot , *(pptr+cot));*/
        /*}*/
        hf = (size_t*)(pptr + psize);
        printf("Footer : [%p] = %zu\n" , hf , *hf);

        walk += bsize ;
    }
    printf("Heap end at : %p\n" , end );
    printf("----------------------------------------\n");
}

/*****************************************************************************/
/* 
 * mm_init - initialize the malloc package.
 */
int mm_init(void)
{
    size_t content = HFTotalSize; 
    size_t * start = mem_sbrk( content );
    *start = (content | 0x1 );
    *(start + 1) = (content | 0x1 );

/*#ifdef  DEBUG */
    /*printheap();*/
/*#endif*/
    return  0;
}


/*****************************************************************************/
/* 
 * mm_malloc - Allocate a block by incrementing the brk pointer.
 *     Always allocate a block whose size is a multiple of the alignment.
 */


void *mm_malloc(size_t size)
{
    size_t newsize = ALIGN(size);
    int found = 0 ;
    char * res = NULL ;

    size_t* walk  = (size_t*)(heap_end()) - 1 ;
    while(1){
        size_t content = *walk;
        size_t bsize = (content & ~0x7) ;
        size_t psize = bsize - HFTotalSize;
        size_t allocated = (content & 0x1);

        if( allocated == 1 && psize == 0){
            //hit end of free list 
            break;
        }

        if ( allocated == 0 && psize >= newsize ){
            found = 1 ;
            char * pstart =  (char*)walk - psize ;
            res =  pstart ;
            
            //if the perfectly fit
            if (psize == newsize){
               *HeaderAddr(res) = bsize | 0x1 ;
               *FooterAddr(res) = bsize | 0x1 ; 
               break;
            }
            //else fragment the block
            else{
                size_t cbsize = newsize + HFTotalSize ;
                *HeaderAddr(pstart) = cbsize | 0x1 ;
                size_t * newfooter  = (size_t*)( pstart + newsize )  ;
                *newfooter = cbsize | 0x1 ; 

                //new block result from fragmentation
                size_t nbsize = bsize - cbsize ;
                size_t npsize = nbsize - HFTotalSize ;

                size_t * nnstart = newfooter + 1 ;
                *nnstart = nbsize;
                size_t * nnend = (size_t*)( (char*)(nnstart+1) + npsize );
                *nnend = nbsize;
                break;
            }
        }

        //search next 
        walk =  (size_t*)( (char*)walk - bsize);
    }

    //no available space, extend the heap 
    if (found == 0){
        size_t increase = newsize + HFTotalSize ;
        size_t* estart = (size_t*)mem_sbrk(increase);
        *estart = (increase | 0x1);

        res = (char*)(estart+1);
        size_t* eend =(size_t*)(res + newsize); 
        *eend = (increase | 0x1 );
    }

    return  (void*)res ;

/*#ifdef  DEBUG*/
    /*printheap();*/
/*#endif*/
}


/*****************************************************************************/
/*
 * mm_free - Freeing a block does nothing.
 */


void coalesce_up(size_t * myfoot , size_t sz ){
    size_t mybsize = *myfoot & ~0x7;
    size_t mypsize = mybsize - HFTotalSize ;
    char* myptr = (char*)(myfoot) - mypsize ;
    *(HeaderAddr(myptr)) = mybsize + sz ;
    //Since FooterAddr use Header content to determine psize
    *(FooterAddr(myptr)) = mybsize + sz ;
}

void coalesce_down(size_t * myhead , size_t sz ){
#ifdef DEBUG
    printheap();
#endif
    size_t mybsize = *myhead & ~0x7;
    size_t mypsize = mybsize - HFTotalSize ;
    char* myptr = (char*)(myhead + 1);
    *(size_t*)(myptr + mypsize) = mybsize + sz ;
    *(size_t*)(myptr - HFSize - sz) = mybsize + sz ;
}

void coalesce_both(size_t* myfoot , size_t* myhead , size_t sz){
    size_t after_mybsize = *myhead & ~0x7;
    coalesce_up(myfoot, sz + after_mybsize);
}


void mm_free(void *ptr)
{


    char* pstart = (char*)ptr;
    size_t bsize = get_block_size(pstart);
    //when set the block free, only write the block size in, the 0(free bit) is implicitly set
    size_t * header = HeaderAddr(pstart);
    size_t * footer = FooterAddr(pstart);
    *header = bsize ;
    *footer = bsize ;


    //coalesce the adjacent free blocks

    size_t before_allocated = *( header - 1 ) & 0x1 ;
    size_t after_allocated = 1;

    //if free the latest malloce block, only coalesce_up;
    if(  (char*)(footer + 1) < heap_end() ){
        after_allocated = *( footer + 1 ) & 0x1 ;
    }

    if (before_allocated == 0 && after_allocated == 0){
        coalesce_both(header - 1 , footer + 1 , bsize );
    }
    else if (before_allocated == 0){
        coalesce_up(header - 1 , bsize );
    }
    else if (after_allocated == 0){
        coalesce_down(footer + 1 , bsize );
    }

}


/*****************************************************************************/
/*
 * mm_realloc - Implemented simply in terms of mm_malloc and mm_free
 */
void *mm_realloc(void *ptr, size_t size)
{
    void *oldptr = ptr;
    void *newptr;
    size_t copySize;
    
    newptr = mm_malloc(size);
    if (newptr == NULL)
      return NULL;
    copySize = *(size_t *)((char *)oldptr - HFSize);
    if (size < copySize)
      copySize = size;
    memcpy(newptr, oldptr, copySize);
    mm_free(oldptr);
    return newptr;
}

• Be Fucking careful with Pointer arithmetic !!!!!!!
• When debugging with debug tools become difficult
  • execute the code line by line in source code mode(in gdb)
  • Examine if the behavior is the one you want
  • Reread the source code carefully

$./mdriver 
Team Name:RinbowBinary
Member 1 :RB:xxx@xxx
Using default tracefiles in traces/
Perf index = 46 (util) + 14 (thru) = 60/100

• Since the malloc search the whole heap for a free block the throughput is just terrible, explicit list and segregate list will perform better.

• Also, I do not eliminate the footer of allocated block for convenience, do so may increase memory utilization.

Explicit list

Segregated list