模拟内存分配器

调用mm_malloc函数分配一个112字节的块，存入一个字符串，统计该字符串的长度，最后调用mm_free函数释放申请的块。

#include <stdio.h> #include <errno.h> #include <stddef.h> #include <stdlib.h> #include <string.h> /* Basic constants and macros */ #define MAX_HEAP (1<<13) #define WSIZE 4 /* word size (bytes) */ #define DSIZE 8 /* doubleword size (bytes) */ #define CHUNKSIZE (1<<12) #define OVERHEAD 8 /* overhead of header and footer (bytes) */ #define MAX(x, y) ((x) > (y)? (x) : (y)) /* Pack a size and allocated bit into a word */ #define PACK(size, alloc) ((size) | (alloc)) /* Read and write a word at address p */ #define GET(p) (*(unsigned int *)(p)) #define PUT(p, val) (*(unsigned int *)(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))) /* private global variables */ static void *mem_heap; /* points to first byte of the heap */ static void *mem_brk; /* points to last byte of the heap */ static void *mem_max_addr; /* max virtual address for the heap */ static void *heap_listp; void mem_init(void); void *mem_sbrk(int incr); int mm_init(void); static void *extend_heap(size_t words); void mm_free(void *bp); static void *coalesce(void *bp); void *mm_malloc(size_t size); static void *find_fit(size_t asize); static void place(void *bp, size_t asize); /* * mem_init- initializes the memory system model */ void mem_init() { mem_heap=malloc(MAX_HEAP); /* models available VM */ mem_brk= mem_heap; /* heap is initially empty */ mem_max_addr= (char *)(mem_heap+ MAX_HEAP); /* Max legal heap addr plus 1 */ } /* * mem_sbrk- simple model of the sbrk function.Extends the heap * by incr bytes and returns the start address of the new area. In * this model,the heap can not be shrunk. */ void *mem_sbrk(int incr) { void *old_brk=mem_brk; if ( (incr< 0)|| ((mem_brk+ incr)>mem_max_addr)){ errno=ENOMEM; fprintf(stderr,"ERROR: mem_sbrk failed. Ran out of memory...\n"); return (void*)-1; } mem_brk+=incr; return old_brk; } int mm_init(void) { /* create the initial empty heap */ if ((heap_listp = mem_sbrk(4*WSIZE)) == (void *)-1) return -1; 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(CHUNKSIZE/WSIZE) == NULL) return -1; return 0; } static void *extend_heap(size_t words) { char *bp; size_t size; /* Allocate an even number of words to maintain alignment */ size = (words % 2) ? (words+1) * WSIZE : words * WSIZE; if ((long)(bp = mem_sbrk(size)) ==-1) return NULL; /* Initialize free block header/footer and the epilogue header */ PUT(HDRP(bp), PACK(size, 0)); /* free block header */ PUT(FTRP(bp), PACK(size, 0)); /* free block footer */ PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); /* new epilogue header */ /* Coalesce if the previous block was free */ return coalesce(bp); } void mm_free(void *bp) { size_t size = GET_SIZE(HDRP(bp)); PUT(HDRP(bp), PACK(size, 0)); PUT(FTRP(bp), PACK(size, 0)); coalesce(bp); } static void *coalesce(void *bp) { size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp))); size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp))); size_t size = GET_SIZE(HDRP(bp)); if (prev_alloc && next_alloc) { /* Case 1 */ return bp; } else if (prev_alloc && !next_alloc) { /* Case 2 */ size += GET_SIZE(HDRP(NEXT_BLKP(bp))); PUT(HDRP(bp), PACK(size, 0)); PUT(FTRP(bp), PACK(size,0)); return(bp); } else if (!prev_alloc && next_alloc) { /* Case 3 */ size += GET_SIZE(HDRP(PREV_BLKP(bp))); PUT(FTRP(bp), PACK(size, 0)); PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0)); return(PREV_BLKP(bp)); } else { /* Case 4 */ size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp))); PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0)); PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0)); return(PREV_BLKP(bp)); } } void *mm_malloc(size_t size) { size_t asize; /* adjusted block size */ size_t extendsize; /* amount to extend heap if no fit */ char *bp; /* Ignore spurious requests */ if (size <= 0) return NULL; /* Adjust block size to include overhead and alignment reqs. */ if (size <= DSIZE) asize = DSIZE + OVERHEAD; else asize = DSIZE * ((size +(OVERHEAD) +(DSIZE-1)) / DSIZE); /* Search the free list for a fit */ if ((bp = find_fit(asize)) != NULL) { place(bp, asize); return bp; } /* No fit found. Get more memory and place the block */ extendsize = MAX(asize,CHUNKSIZE); if ((bp = extend_heap(extendsize/WSIZE)) == NULL) return NULL; place(bp, asize); return bp; } static void *find_fit(size_t asize) { void *bp; /* first fit search */ for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) { if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) { return bp; } } return NULL; /* no fit */ } static void place(void *bp, size_t asize) { size_t csize = GET_SIZE(HDRP(bp)); if ((csize - asize) >= (DSIZE + OVERHEAD)) { PUT(HDRP(bp), PACK(asize, 1)); PUT(FTRP(bp), PACK(asize, 1)); bp = NEXT_BLKP(bp); PUT(HDRP(bp), PACK(csize-asize, 0)); PUT(FTRP(bp), PACK(csize-asize, 0)); } else { PUT(HDRP(bp), PACK(csize, 1)); PUT(FTRP(bp), PACK(csize, 1)); } } int main() { int i,sum=0; size_t nums; char *p; nums=100; mem_init(); mm_init(); p=mm_malloc(nums); if (p == NULL) { printf("Malloc failed!\n"); return -1; } strncpy(p, "abvc123456789QWERTYUIOPkjhtyui897asdfghjklqazxcswed", 99); p[99] = '\0'; for(i=0;p[i]!='\0';i++) sum++; printf("num of characters is %d\n",sum); mm_free(p); return 0; }

num of characters is 51