mm.c

ICS 课程的Lab7

/*
 * mm-naive.c - The fastest, least memory-efficient malloc package.
 * 
 * In this naive approach, a block is allocated by simply incrementing 
 * the brk pointer.  A block is pure payload. There are no headers or footers.
 * Blocks are never coalesced or reused. Realloc is implemented 
 * directly using mm_malloc and mm_free.
 */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>

#include "mm.h"
#include "memlib.h"

/* declare mm_check as static */
static  void *extend_heap(size_t words);
static void *coalesce(void *bp);
static void *find_fit(size_t asize);
static void *place(void *bp,size_t asize);

/* $begin mallocmacros */

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

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

/* Basic constants and macros */
#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))

#define WSIZE 4          /* word size (bytes) */  

#define DSIZE 8          /* doubleword size (bytes) */

#define CHUNKSIZE (1<<12)   /* initial heap size (bytes) */

#define MAX(x,y)  ((x) > (y)? (x):(y))   /* overhead of header and footer (bytes) */

/* Pack a size and allocated bit into a word */
#define PACK(size,alloc)  ((size) | (alloc))

/* overhead byte size */
#define OVERHEAD 8

/* Read and write a word at address p */
#define GET(p)       (*(size_t *)(p))

#define PUT(p,val)   (*(size_t *)(p) =(val))

/* Read the size and allocated fields from address p */
#define GET_SIZE(p)  (GET(p) & ~0x7)

#define GET_ALLOC(p)  (GET(p) & 0x1)

/* Given block ptr bp, compute address of its header and footer */
#define HDRP(bp)      ((char *)(bp)-WSIZE)

#define FTRP(bp)      ((char *)(bp)+GET_SIZE(HDRP(bp))-DSIZE)

/* Given block ptr bp, compute address of next and previous blocks */
#define NEXT_BLKP(bp)  ((char *)(bp) + GET_SIZE(((char *)(bp)-WSIZE)))

#define PREV_BLKP(bp)  ((char *)(bp) - GET_SIZE(((char *)(bp)-DSIZE)))

#define NEXT(bp)       ((char *)(bp)+WSIZE)

/* $end mallocmacros */

void *heap_listp=NULL;   /* The global variable is a pointer to the first block */
void *header=NULL;       /* The header of the double linked list */
void *tail;              /* The tail of the double linked list */
int j=0;                 /* The global condition sign */


/* 
 * mm_init - initialize the malloc package.
 */
int mm_init(void)
{
    /* initialize all the global variables*/
    header=NULL;              
    tail=NULL;               /* set all the pointer to be null */
    j=0;                     /* set all the integers to 0 */
   
    /* initialize an start space */
    if((heap_listp=mem_sbrk(4*WSIZE))==NULL)
        return -1;          /* if get null,return due to false */
    
    PUT(heap_listp,0);      /* alignment padding */
    
    PUT(heap_listp+WSIZE,PACK(OVERHEAD,1));   /* prologue header */ 
    
    PUT(heap_listp+DSIZE,PACK(OVERHEAD,1));   /* prologue footer */ 
    
    PUT(heap_listp+WSIZE+DSIZE,PACK(0,1));    /* epilogue header */

    heap_listp += DSIZE;   

    /* Extend the empty heap with a free block of CHUNKSIZE bytes */
    if(extend_heap(1<<4)==NULL)
        return -1;         /* If error happens,return -1 */
    
    return 0;	           /* Normally exits */
}

/* 
 * extend_heap - Extend heap with free block and return its block pointer
 */
static void *extend_heap(size_t words)
{
    void* bp;           /* The return pointer to the new block */
    size_t size;        /* The apporiate size of the new block */

    /* Allocate an even number of words to maintain alignment */
    size=(words%2) ? (words+1)*WSIZE:words*WSIZE;

    /* Get a memory space by system call */
    if((int)(bp=mem_sbrk(size))<0)  
        return NULL;

    /* Initialize free block header/footer and the epilogue header */
    PUT(HDRP(bp),PACK(size,0));
    PUT(FTRP(bp),PACK(size,0));
    PUT(HDRP(NEXT_BLKP(bp)),PACK(0,1));
    
    /* Coalesce if the previous block was free */
    return coalesce(bp);       
}
/* $end mmextendheap */

/*
 * mm_free - Freeing a block does nothing.
 */
void mm_free(void *ptr)
{
    /* Get the size of the free block */
    size_t size=GET_SIZE(HDRP(ptr));

    /* Set the mark to be free */
    PUT(HDRP(ptr),PACK(size,0));
    PUT(FTRP(ptr),PACK(size,0));
    coalesce(ptr);             /* coalesce the block to join with others */
}


/*
 * mm_realloc - Implemented simply in terms of mm_malloc and mm_free
 */
void *mm_realloc(void *ptr, size_t size)
{
    void *oldptr=ptr;      /* The old pointer pointing to the old block */
    void *newptr;          /* The new pointer pointing to the new block */
    size_t oldsize;        /* The size of the old block */
    size_t newsize;        /* The size of the new block */
    void *pre=PREV_BLKP(ptr);   /* The previous block of the old one */
    void *next=NEXT_BLKP(ptr);  /* The next block of the old one */
    size_t next_size;      /* The size of the next block */
    size_t pre_size;       /* The size of the previous block */

    size_t prev_alloc=GET_ALLOC(FTRP(pre));   /* The sign of the previous block */
    size_t next_alloc=GET_ALLOC(HDRP(next));  /* The sign of the next block */

    if(size < 0)           /* If the size smaller than 0,return null */
        return NULL;

    if(ptr == NULL)        /* If the pointer is null ,malloc a new block */
       return  mm_malloc(size);     
    else if(size == 0)     /* If size is 0,free the old one */
    {
        mm_free(ptr);
        return NULL;
    }
    else                   /* The normal case */ 
    {
        oldsize = GET_SIZE(HDRP(oldptr));   /* Get the old size */
        size = ((size+ (DSIZE - 1))/DSIZE)*DSIZE;     /* align the new size */
	
        newsize =size + DSIZE;     /* add the header and footer size */

        if(oldsize>=newsize)       /* If oldsize bigger than new size ,just return */
            return oldptr;
        else
        {
            if(prev_alloc && next_alloc)  /* If the prev and next blocks are both allocated */
            {
                newptr=mm_malloc(size);   /* Malloc a new bigger block */
                memcpy(newptr,oldptr,oldsize-DSIZE);  /* copy the data to the aim place */
                mm_free(oldptr);          /* free the old block */
		
                return newptr;            /* return the new pointer */
                
            }else if(!prev_alloc && next_alloc)  /* If prev is free and the next is allocated */
            {
                void *pre1=(void *)(GET(pre));   /* Get the previous block */
                
                void *next1=(void *)(GET(NEXT(pre))); /* Get the next pointer */
                
                pre_size = GET_SIZE(HDRP(pre));    /* Get the previous block size */
                
                if(pre_size+oldsize>=newsize)    /* If the two sum is bigger enough */
                {
                    
                    PUT(HDRP(pre),PACK(pre_size+oldsize,1));  /* Set the header and footer */
                    PUT(FTRP(pre),PACK(pre_size+oldsize,1));
		    
		    char *temp1=(char *)pre;
		    char *temp2=(char *)oldptr;
		    int ii;
		    for(ii=0;ii<oldsize;ii++)   /* copy the data to the new block */
		    {
			*temp1=*temp2;
			 temp1++;
			 temp2++;
		    }

		     /* If the pre in the list is null and next is null too */
                    if(pre1==NULL && next1==NULL)
                        tail=header=NULL;    
		    /* If the pre in the list is not null but the next is null */
                    else if(pre1!=NULL && next1==NULL)
                    {
                        PUT(NEXT(pre1),(int)NULL); /* Set the next of the prev */
                        tail=pre1;              /* Set the tail */
                    }
		    /* If the pre in the list is null but the next is not null */
                    else if(pre1==NULL && next1!=NULL)
                    {
                        PUT(next1,(int)NULL);   /* Set the next */
                        header=next1;           /* Set the header */
                    }
		    /* If the pre in the list is not null and so is the next */
                    else if(pre1!=NULL && next1!=NULL)
                    {
                        PUT(NEXT(pre1),(int)next1);  /* set the next of the pre */
                        PUT(next1,(int)pre1);        /* set the pre of the next*/
                    }
                  return pre;  
                }
                else  /* The total size is not big enough */
                {
		    newptr=mm_malloc(size);     /* malloc a new block big enough */
		    memcpy(newptr,oldptr,oldsize-DSIZE);  /* copy the data */
		    mm_free(oldptr);            /* free the old block */
		    return newptr;              /* return the new block */
                }
		/* The prevoius is allocated but the next block is not allocated */
            }else if(prev_alloc && !next_alloc)
            {
                void *pre2=(void *)(GET(next));   /* The next of the block */
                void *next2=(void *)(GET(NEXT(next))); /*The next of the next of the block*/ 
                
                next_size=GET_SIZE(HDRP(next));   /* Get the size of the next */
		
		// If the total size is big enough */
                if(next_size+oldsize>=newsize)
                {
		    /* Set the block sign */
                    PUT(HDRP(oldptr),PACK(next_size+oldsize,1));
                    PUT(FTRP(oldptr),PACK(next_size+oldsize,1));
		    /* If the pre is null and next is null too */
                    if(pre2==NULL && next2==NULL)
                        tail=header=NULL;
		    /* If the pre in the list is not null but the next is null */
                    else if(pre2!=NULL && next2==NULL)
                    {
                        PUT(NEXT(pre2),(int)NULL);
                        tail=pre2;
                    }
		    /* If the pre in the list is null but the next is not null */
                    else if(pre2==NULL && next2!=NULL)
                    {
                        PUT(next2,(int)NULL);
                        header=next2;
                    }
                    /* If the pre in the list is null and the next is null */
                    else if(pre2!=NULL && next2!=NULL)
                    {
                        PUT(NEXT(pre2),(int)next2);
                        PUT(next2,(int)pre2);
                    }
                    return oldptr;    /* return the old block pointer */
                }else
                {
		    newptr=mm_malloc(size);   /* malloc a new block */
		    memcpy(newptr,oldptr,oldsize-DSIZE); /* copy the data to the aim */
		    mm_free(oldptr);          /* free the old block */
		    return newptr;            /* return the new block pointer */
                }
            }
            else
            {
                pre_size=GET_SIZE(HDRP(pre));  /* the size of the pre block */
                next_size=GET_SIZE(HDRP(next));/* the size of the next block */
		
                void *pre1=(void *)(GET(pre)); /* the pre pointer */
                void *next2=(void *)(GET(NEXT(next)));  /* the next pointer */

                if((oldsize+pre_size)>=newsize) /* If the total size is enough */
                {
                    PUT(HDRP(pre),PACK(pre_size+oldsize,1)); /* Set the sign */
                    PUT(FTRP(pre),PACK(pre_size+oldsize,1));
		    
		    char *temp1=(char *)pre;
		    char *temp2=(char *)oldptr;
		    int ii;
		    for(ii=0;ii<oldsize;ii++)   /* copy the data to the new block */
		    {
			*temp1=*temp2;
			temp1++;
			temp2++;
		    }

		    /* The pre in the list is null */
		    if(pre1==NULL)
                     {
                         PUT(next,(int)NULL);        /* set the header */
                         header=next;
                     }
		    else   /* The pre is not null */
                     {
                         PUT(NEXT(pre1),(int)next); /* set the next */
                         PUT(next,(int)pre1);
                     }
                     
		    return pre;       /* return the pre pointer */
                }
                
                        
		/* The sum of the current and next is enough */
                else if((oldsize+next_size)>=newsize)
                { 
		    /* Set the sign */
                    PUT(HDRP(oldptr),PACK(next_size+oldsize,1));
                    PUT(FTRP(oldptr),PACK(next_size+oldsize,1));
                    if(next2==NULL)   /* If next is null */
                    {
                        PUT(NEXT(pre),(int)NULL); /* set the next */
                        tail=pre;                 /* set the tail */
                    }else
                    {
                        PUT(NEXT(pre),(int)next2); /* set the next of the pre */
                        PUT(next2,(int)pre);
                    }
                    
                    return oldptr;   /* return the old block pointer */
                }
                
                /* The total size of the three blocks are big enough */
                else  if(pre_size+oldsize+next_size>=newsize)