| 0,0 → 1,374 |
|---|
| /* |
| * Simple, 32-bit and 64-bit clean allocator based on implicit free |
| * lists, first fit placement, and boundary tag coalescing, as described |
| * in the CS:APP2e text. Blocks must be aligned to doubleword (8 byte) |
| * boundaries. Minimum block size is 16 bytes. |
| * |
| * This version is loosely based on |
| * http://csapp.cs.cmu.edu/public/ics2/code/vm/malloc/mm.c |
| * but unlike the book's version, it does not use C preprocessor |
| * macros or explicit bit operations. |
| */ |
| #include <stdio.h> |
| #include <string.h> |
| #include <stdlib.h> |
| #include <stdbool.h> |
| #include <stdint.h> |
| #include <stddef.h> |
| #include <assert.h> |
| |
| #include "mm.h" |
| #include "memlib.h" |
| |
| struct boundary_tag { |
| int inuse:1; // inuse bit |
| int size:31; // size of block, in words |
| }; |
| |
| /* FENCE is used for heap prologue/epilogue. */ |
| const struct boundary_tag FENCE = { .inuse = 1, .size = 0 }; |
| |
| /* A C struct describing the beginning of each block. |
| * For implicit lists, used and free blocks have the same |
| * structure, so one struct will suffice for this example. |
| * If each block is aligned at 4 mod 8, each payload will |
| * be aligned at 0 mod 8. |
| */ |
| struct block { |
| struct boundary_tag header; /* offset 0, at address 4 mod 8 */ |
| char payload[0]; /* offset 4, at address 0 mod 8 */ |
| }; |
| |
| /* |
| * If NEXT_FIT defined use next fit search, else use first fit search |
| */ |
| #define NEXT_FITx |
| |
| /* Basic constants and macros */ |
| #define WSIZE 4 /* Word and header/footer size (bytes) */ |
| #define DSIZE 8 /* Doubleword size (bytes) */ |
| #define MIN_BLOCK_SIZE_WORDS 4 /* Minimum block size in words */ |
| #define CHUNKSIZE (1<<10) /* Extend heap by this amount (words) */ |
| |
| #define MAX(x, y) ((x) > (y)? (x) : (y)) |
| |
| /* Global variables */ |
| static struct block *heap_listp = 0; /* Pointer to first block */ |
| #ifdef NEXT_FIT |
| static struct block *rover; /* Next fit rover */ |
| #endif |
| |
| /* Function prototypes for internal helper routines */ |
| static struct block *extend_heap(size_t words); |
| static void place(struct block *bp, size_t asize); |
| static struct block *find_fit(size_t asize); |
| static struct block *coalesce(struct block *bp); |
| |
| /* Given a block, obtain previous's block footer. |
| Works for left-most block also. */ |
| static struct boundary_tag * prev_blk_footer(struct block *blk) { |
| return &blk->header - 1; |
| } |
| |
| /* Return if block is free */ |
| static bool blk_free(struct block *blk) { |
| return !blk->header.inuse; |
| } |
| |
| /* Return size of block is free */ |
| static size_t blk_size(struct block *blk) { |
| return blk->header.size; |
| } |
| |
| /* Given a block, obtain pointer to previous block. |
| Not meaningful for left-most block. */ |
| static struct block *prev_blk(struct block *blk) { |
| struct boundary_tag *prevfooter = prev_blk_footer(blk); |
| assert(prevfooter->size != 0); |
| return (struct block *)((size_t *)blk - prevfooter->size); |
| } |
| |
| /* Given a block, obtain pointer to next block. |
| Not meaningful for right-most block. */ |
| static struct block *next_blk(struct block *blk) { |
| assert(blk_size(blk) != 0); |
| return (struct block *)((size_t *)blk + blk->header.size); |
| } |
| |
| /* Given a block, obtain its footer boundary tag */ |
| static struct boundary_tag * get_footer(struct block *blk) { |
| return (void *)((size_t *)blk + blk->header.size) |
| - sizeof(struct boundary_tag); |
| } |
| |
| /* Set a block's size and inuse bit in header and footer */ |
| static void set_header_and_footer(struct block *blk, int size, int inuse) { |
| blk->header.inuse = inuse; |
| blk->header.size = size; |
| * get_footer(blk) = blk->header; /* Copy header to footer */ |
| } |
| |
| /* Mark a block as used and set its size. */ |
| static void mark_block_used(struct block *blk, int size) { |
| set_header_and_footer(blk, size, 1); |
| } |
| |
| /* Mark a block as free and set its size. */ |
| static void mark_block_free(struct block *blk, int size) { |
| set_header_and_footer(blk, size, 0); |
| } |
| |
| /* |
| * mm_init - Initialize the memory manager |
| */ |
| int mm_init(void) |
| { |
| /* Create the initial empty heap */ |
| struct boundary_tag * initial = mem_sbrk(2 * sizeof(struct boundary_tag)); |
| if (initial == (void *)-1) |
| return -1; |
| |
| /* We use a slightly different strategy than suggested in the book. |
| * Rather than placing a min-sized prologue block at the beginning |
| * of the heap, we simply place two fences. |
| * The consequence is that coalesce() must call prev_blk_footer() |
| * and not prev_blk() - prev_blk() cannot be called on the left-most |
| * block. |
| */ |
| initial[0] = FENCE; /* Prologue footer */ |
| heap_listp = (struct block *)&initial[1]; |
| initial[1] = FENCE; /* Epilogue header */ |
| |
| #ifdef NEXT_FIT |
| rover = heap_listp; |
| #endif |
| |
| /* Extend the empty heap with a free block of CHUNKSIZE bytes */ |
| if (extend_heap(CHUNKSIZE) == NULL) |
| return -1; |
| return 0; |
| } |
| |
| /* |
| * mm_malloc - Allocate a block with at least size bytes of payload |
| */ |
| void *mm_malloc(size_t size) |
| { |
| size_t awords; /* Adjusted block size in words */ |
| size_t extendwords; /* Amount to extend heap if no fit */ |
| struct block *bp; |
| |
| if (heap_listp == 0){ |
| mm_init(); |
| } |
| /* Ignore spurious requests */ |
| if (size == 0) |
| return NULL; |
| |
| /* Adjust block size to include overhead and alignment reqs. */ |
| size += 2 * sizeof(struct boundary_tag); /* account for tags */ |
| size = (size + DSIZE - 1) & ~(DSIZE - 1); /* align to double word */ |
| awords = MAX(MIN_BLOCK_SIZE_WORDS, size/WSIZE); |
| /* respect minimum size */ |
| |
| /* Search the free list for a fit */ |
| if ((bp = find_fit(awords)) != NULL) { |
| place(bp, awords); |
| return bp->payload; |
| } |
| |
| /* No fit found. Get more memory and place the block */ |
| extendwords = MAX(awords,CHUNKSIZE); |
| if ((bp = extend_heap(extendwords)) == NULL) |
| return NULL; |
| place(bp, awords); |
| return bp->payload; |
| } |
| |
| /* |
| * mm_free - Free a block |
| */ |
| void mm_free(void *bp) |
| { |
| if (bp == 0) |
| return; |
| |
| /* Find block from user pointer */ |
| struct block *blk = bp - offsetof(struct block, payload); |
| if (heap_listp == 0) { |
| mm_init(); |
| } |
| |
| mark_block_free(blk, blk_size(blk)); |
| coalesce(blk); |
| } |
| |
| /* |
| * coalesce - Boundary tag coalescing. Return ptr to coalesced block |
| */ |
| static struct block *coalesce(struct block *bp) |
| { |
| bool prev_alloc = prev_blk_footer(bp)->inuse; |
| bool next_alloc = ! blk_free(next_blk(bp)); |
| size_t size = blk_size(bp); |
| |
| if (prev_alloc && next_alloc) { /* Case 1 */ |
| return bp; |
| } |
| |
| else if (prev_alloc && !next_alloc) { /* Case 2 */ |
| mark_block_free(bp, size + blk_size(next_blk(bp))); |
| } |
| |
| else if (!prev_alloc && next_alloc) { /* Case 3 */ |
| bp = prev_blk(bp); |
| mark_block_free(bp, size + blk_size(bp)); |
| } |
| |
| else { /* Case 4 */ |
| mark_block_free(prev_blk(bp), |
| size + blk_size(next_blk(bp)) + blk_size(prev_blk(bp))); |
| bp = prev_blk(bp); |
| } |
| #ifdef NEXT_FIT |
| /* Make sure the rover isn't pointing into the free block */ |
| /* that we just coalesced */ |
| if ((rover > bp) && (rover < next_blk(bp))) |
| rover = bp; |
| #endif |
| return bp; |
| } |
| |
| /* |
| * mm_realloc - Naive implementation of realloc |
| */ |
| void *mm_realloc(void *ptr, size_t size) |
| { |
| size_t oldsize; |
| void *newptr; |
| |
| /* If size == 0 then this is just free, and we return NULL. */ |
| if(size == 0) { |
| mm_free(ptr); |
| return 0; |
| } |
| |
| /* If oldptr is NULL, then this is just malloc. */ |
| if(ptr == NULL) { |
| return mm_malloc(size); |
| } |
| |
| newptr = mm_malloc(size); |
| |
| /* If realloc() fails the original block is left untouched */ |
| if(!newptr) { |
| return 0; |
| } |
| |
| /* Copy the old data. */ |
| struct block *oldblock = ptr - offsetof(struct block, payload); |
| oldsize = blk_size(oldblock) * WSIZE; |
| if(size < oldsize) oldsize = size; |
| memcpy(newptr, ptr, oldsize); |
| |
| /* Free the old block. */ |
| mm_free(ptr); |
| |
| return newptr; |
| } |
| |
| /* |
| * checkheap - We don't check anything right now. |
| */ |
| void mm_checkheap(int verbose) |
| { |
| } |
| |
| /* |
| * The remaining routines are internal helper routines |
| */ |
| |
| /* |
| * extend_heap - Extend heap with free block and return its block pointer |
| */ |
| static struct block *extend_heap(size_t words) |
| { |
| void *bp; |
| |
| /* Allocate an even number of words to maintain alignment */ |
| words = (words + 1) & ~1; |
| if ((long)(bp = mem_sbrk(words * WSIZE)) == -1) |
| return NULL; |
| |
| /* Initialize free block header/footer and the epilogue header. |
| * Note that we scoop up the previous epilogue here. */ |
| struct block * blk = bp - sizeof(FENCE); |
| mark_block_free(blk, words); |
| next_blk(blk)->header = FENCE; |
| |
| /* Coalesce if the previous block was free */ |
| return coalesce(blk); |
| } |
| |
| /* |
| * place - Place block of asize words at start of free block bp |
| * and split if remainder would be at least minimum block size |
| */ |
| static void place(struct block *bp, size_t asize) |
| { |
| size_t csize = blk_size(bp); |
| |
| if ((csize - asize) >= MIN_BLOCK_SIZE_WORDS) { |
| mark_block_used(bp, asize); |
| bp = next_blk(bp); |
| mark_block_free(bp, csize-asize); |
| } |
| else { |
| mark_block_used(bp, csize); |
| } |
| } |
| |
| /* |
| * find_fit - Find a fit for a block with asize words |
| */ |
| static struct block *find_fit(size_t asize) |
| { |
| |
| #ifdef NEXT_FIT |
| /* Next fit search */ |
| struct block *oldrover = rover; |
| |
| /* Search from the rover to the end of list */ |
| for ( ; blk_size(rover) > 0; rover = next_blk(rover)) |
| if (blk_free(rover) && (asize <= blk_size(rover))) |
| return rover; |
| |
| /* search from start of list to old rover */ |
| for (rover = heap_listp; rover < oldrover; rover = next_blk(rover)) |
| if (blk_free(rover) && (asize <= blk_size(rover))) |
| return rover; |
| |
| return NULL; /* no fit found */ |
| #else |
| /* First fit search */ |
| struct block *bp; |
| |
| for (bp = heap_listp; blk_size(bp) > 0; bp = next_blk(bp)) { |
| if (blk_free(bp) && asize <= blk_size(bp)) { |
| return bp; |
| } |
| } |
| return NULL; /* No fit */ |
| #endif |
| } |
| |
| team_t team = { |
| /* Team name */ |
| "Sample allocator using implicit lists", |
| /* First member's full name */ |
| "Godmar Back", |
| "gback@cs.vt.edu", |
| /* Second member's full name (leave blank if none) */ |
| "", |
| "", |
| }; |