mm_6.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);
static void large(int num);
static void mm_check(void);

/* 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)

#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))

#define WSIZE 4

#define DSIZE 8

#define CHUNKSIZE (1<<12)

#define MAX(x,y)  ((x) > (y)? (x):(y))

#define PACK(size,alloc)  ((size) | (alloc))

#define OVERHEAD 8

#define GET(p)   (*(size_t *)(p))

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

#define GET_SIZE(p)  (GET(p) & ~0x7)

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

#define HDRP(bp)      ((char *)(bp)-WSIZE)

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


#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)


void *heap_listp=NULL;
void *header=NULL;
void *tail;
int j=0;
int i=0;
int k=0;

size_t largest_size = 0;
int  largest_num = 0;
void *largest_ptr = NULL;

size_t second_size = 0;
int  second_num = 0;
void *second_ptr = NULL;

/* 
 * mm_init - initialize the malloc package.
 */
int mm_init(void)
{

    header=NULL;
    tail=NULL;
    i=0;
    j=0;
    k=0;
        
    largest_size = 0;
    largest_num = 0;
    second_size = 0;
    second_num = 0;
    largest_ptr = NULL;
    second_ptr = NULL;

    if((heap_listp=mem_sbrk(4*WSIZE))==NULL)
    {
        return -1;
    }
    PUT(heap_listp,0);
    
    PUT(heap_listp+WSIZE,PACK(OVERHEAD,1));
    
    PUT(heap_listp+DSIZE,PACK(OVERHEAD,1));
    
    PUT(heap_listp+WSIZE+DSIZE,PACK(0,1));

    heap_listp += DSIZE;
    if(extend_heap(CHUNKSIZE/WSIZE)==NULL)
    {
        return -1;
    }
    
    //largest_size = CHUNKSIZE;
    mm_check();
    
    return 0;	 
}

static void *extend_heap(size_t words)
{
    void* bp;
    size_t size;

    size=(words%2) ? (words+1)*WSIZE:words*WSIZE;

    if((int)(bp=mem_sbrk(size))<0)
        return NULL;

    PUT(HDRP(bp),PACK(size,0));
    PUT(FTRP(bp),PACK(size,0));
    PUT(HDRP(NEXT_BLKP(bp)),PACK(0,1));

    return coalesce(bp);
}


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

    // printf("\n\nfree block size : %d\n\n",GET_SIZE(HDRP(ptr)));
    PUT(HDRP(ptr),PACK(size,0));
    PUT(FTRP(ptr),PACK(size,0));
    coalesce(ptr);
}


/*
 * mm_realloc - Implemented simply in terms of mm_malloc and mm_free
 */
void *mm_realloc(void *ptr, size_t size)
{
    k++;



    void *oldptr=ptr;
    void *newptr;
    size_t oldsize;
    size_t newsize;
    void *pre=PREV_BLKP(ptr);
    void *next=NEXT_BLKP(ptr);
    size_t next_size;
    size_t pre_size;

    size_t prev_alloc=GET_ALLOC(FTRP(pre));
    size_t next_alloc=GET_ALLOC(HDRP(next));

    if(size < 0)
    {
        return NULL;
        
    }

    if(ptr == NULL)
    {
       return  mm_malloc(size); 
        
    }else if(size == 0)
    {
        mm_free(ptr);
        
        return NULL;
    }
    else 
    {
        oldsize=GET_SIZE(HDRP(oldptr));
        size=((size+7)/8)*8;
	
        newsize=size+8;

        if(oldsize>=newsize)
        {
            return oldptr;
            
        }
        else
        {
            if(prev_alloc && next_alloc)
            {
                newptr=mm_malloc(size);
                memcpy(newptr,oldptr,oldsize-DSIZE);
                mm_free(oldptr);
		
                return newptr;
                
            }else if(!prev_alloc && next_alloc)
            {
                void *pre1=(void *)(GET(pre));
                
                void *next1=(void *)(GET(NEXT(pre)));
                
                pre_size=GET_SIZE(HDRP(pre));
                
                if(pre_size+oldsize>=newsize)
                {
                    
                    PUT(HDRP(pre),PACK(pre_size+oldsize,1));
                    PUT(FTRP(pre),PACK(pre_size+oldsize,1));
		    
		    char *temp1=(char *)pre;
		    char *temp2=(char *)oldptr;
		    int ii;
		    for(ii=0;ii<oldsize;ii++)
		    {
			*temp1=*temp2;
			 temp1++;
			 temp2++;
			
		    }
		    
                    if(pre1==NULL && next1==NULL)
                    {
                        tail=header=NULL;
                        
                        
                    }else if(pre1!=NULL && next1==NULL)
                    {
                        PUT(NEXT(pre1),(int)NULL);
                        tail=pre1;
                        
                    }
                    else if(pre1==NULL && next1!=NULL)
                    {
                        PUT(next1,(int)NULL);
                        header=next1;
                        
                    }
                    else if(pre1!=NULL && next1!=NULL)
                    {
                        
                        PUT(NEXT(pre1),(int)next1);
                        PUT(next1,(int)pre1);
                              
                    }
                    
                  return pre;  
                    
                }
                else
                {
                     newptr=mm_malloc(size);
                     memcpy(newptr,oldptr,oldsize-DSIZE);
                     mm_free(oldptr);
                     return newptr;
                     
                    
                }
                
                
                
                
            }else if(prev_alloc && !next_alloc)
            {
                void *pre2=(void *)(GET(next));
                void *next2=(void *)(GET(NEXT(next)));
                
                next_size=GET_SIZE(HDRP(next));

                
                if(next_size+oldsize>=newsize)
                {
                    PUT(HDRP(oldptr),PACK(next_size+oldsize,1));
                    PUT(FTRP(oldptr),PACK(next_size+oldsize,1));
                    if(pre2==NULL && next2==NULL)
                    {
                        tail=header=NULL;
                        
                        
                    }else if(pre2!=NULL && next2==NULL)
                    {
                        PUT(NEXT(pre2),(int)NULL);
                        tail=pre2;
                        
                    }
                    else if(pre2==NULL && next2!=NULL)
                    {
                        PUT(next2,(int)NULL);
                        header=next2;
                        
                    }
                    else if(pre2!=NULL && next2!=NULL)
                    {
                        PUT(NEXT(pre2),(int)next2);
                        PUT(next2,(int)pre2);
                              
                    }
                    return oldptr;
                    
                    
                }else
                    
                {
                     newptr=mm_malloc(size);
                     memcpy(newptr,oldptr,oldsize-DSIZE);
                     mm_free(oldptr);
                     return newptr;
                    
                }
                    
                   
                
            }
            else
            {
		

                pre_size=GET_SIZE(HDRP(pre));
                next_size=GET_SIZE(HDRP(next));
		
                void *pre1=(void *)(GET(pre));
                void *next2=(void *)(GET(NEXT(next)));
                if(pre_size+oldsize+next_size>=newsize)
                {

                    PUT(HDRP(pre),PACK(pre_size+oldsize+next_size,1));
                    PUT(FTRP(pre),PACK(pre_size+oldsize+next_size,1));

		    char *temp1=(char *)pre;
		    char *temp2=(char *)oldptr;
		    int ii;
		    
		    for(ii=0;ii<oldsize;ii++)
		    {
			*temp1=*temp2;
			 temp1++;
			 temp2++;
			
		    }
                    if(pre1==NULL && next2==NULL)
                    {
                        tail=header=NULL;
                        
                    }
                    else if(pre1==NULL && next2!=NULL)
                    {
                        PUT(next2,(int)NULL);
                        header=next2;
                        
                    }
                    else if(pre1!=NULL && next2==NULL)
                    {
                        PUT(NEXT(pre1),(int)NULL);
                        tail=pre1;
                        
                    }
                    else
                    {
                        PUT(NEXT(pre1),(int)next2);
                        PUT(next2,(int)pre1);
                        
                    }
                    return pre;
                    
                }
                else
                {
                     newptr=mm_malloc(size);
                     memcpy(newptr,oldptr,oldsize-DSIZE);
                     mm_free(oldptr);
                     return newptr;
                    
                }
                
                
                
            }
        }
        
    }
    
        
        
        // oldsize=GET_SIZE(HDRP(ptr));
        // newptr = mm_malloc(size);

        // size =  GET_SIZE(HDRP(newptr));
        
        // if (oldsize <size)
        // {
        // memcpy(newptr,oldptr,oldsize-DSIZE); 
            
            // }else
            // {
            
            // memcpy(newptr,oldptr,size-DSIZE); 
            // }

            // mm_free(oldptr);

            // return newptr;
}



void *mm_malloc(size_t size)
{
    size_t asize;
    size_t extendsize;
    void  *bp;
    j++;

    
    // printf("\n\nmalloc the palce,size : %d\n\n\n",size);
    
    if(size<=0)
    {
        return NULL;
    }

    if(size <= DSIZE)
    {
        asize = DSIZE + OVERHEAD;
        
    }else
    {
        asize = DSIZE *((size +(OVERHEAD) + (DSIZE - 1))/DSIZE);
    }
    // printf("required size :%d\n",size);
    // printf("largest_num: %d \n",largest_num);
    //printf("largest_size:%d \n",largest_size);
    //printf("second_num: %d \n",second_num);
    //printf("second_size:%d \n",second_size);
     if(((largest_num > 0) && (asize > largest_size)) || ((largest_num < 0) && (second_num > 0) && (asize > second_size))){
	 extendsize = MAX(asize,CHUNKSIZE);

	 if((bp = extend_heap(extendsize/WSIZE )) == NULL)
	 {
	     return NULL;
	 }
	 // printf("exit malloc\n");
	 return  place(bp,asize);
	  //return bp;
	
    }

    if((bp = find_fit(asize)) !=NULL)
    {
       	if (GET_SIZE(HDRP(bp)) >= largest_size) {
	    largest_num --;
	}
	else if (GET_SIZE(HDRP(bp)) == second_size)
	    second_num --;
//	printf("exit malloc find_fit\n");
	return place(bp,asize);

    }

    extendsize = MAX(asize,CHUNKSIZE);