Recitation 10: Malloc LabLogisticsToday’s PlanWhat does mm-helper.c do ?Block FormatHeader/Footer FormatHeap FormatVery Useful MacrosSlide 9Slide 10Initializing the heapExtending the HeapCoalescingMallocFinding First FitPlacing a block in a free chunkFreeAdding debugging informationAllocated Block FormatOne way to implement thisHeapcheckExplicit ListsRecitation 10: Malloc LabAndrew Faulring15213 Section A11 November 2002Logistics[email protected]Office hoursNSH 2504Tuesday 2–3Exam 2Tuesday, 12 November, 6:00-7:20pmDoherty Hall 2315Lab 6 (Malloc)due next Tuesday, 19 NovemberToday’s PlanThe Malloc LabUnderstand mm-helper.cAdding debugging info to mm-helper.cWhat does mm-helper.c do ?Implicit Free ListHeader with each block – (size / allocated bit)No separate Free List – free blocks linked implicitly by size fields in headerFirst FitSearches free list from beginning and picks first block that fitsImmediate Boundary Tag CoalescingFooter (boundary tag), replica of headerBlock FormatHeaderFooterPayloadPointer returnedby malloc (Block Pointer (bp))32 bits 32 bits >= what user askedfor in mallocHeader/Footer FormatDouble word alignmentThree lower-order bits of size always 0Pack size and allocated bits into a single integerSize = 24 (0x18). Block is allocated Header = 0 x18 | 0x1 = 0x190 0 asize3 2 1 0 31Heap Format8|1 8|1 0|1Pad Prologue EpilogueAllocated and Free BlocksDouble Word AlignmentHeaderFooter Header FooterVery Useful Macros#define WSIZE 4#define DSIZE 8 #define CHUNKSIZE (1<<12) #define OVERHEAD 8Very Useful Macros#define PACK(size, alloc) ((size) | (alloc)) #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)Very Useful Macros#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)))Initializing the heapint mm_init(void) {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; return 0; }Extending the Heapstatic void *extend_heap(size_t words) { char *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); }Coalescingstatic 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) { return bp; }else if (prev_alloc && !next_alloc) { ….. }else if (!prev_alloc && next_alloc) {size += GET_SIZE(HDRP(PREV_BLKP(bp))); PUT(FTRP(bp), PACK(size, 0)); PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0)); bp = PREV_BLKP(bp); } else { ……. } return bp; }Mallocvoid *mm_malloc(size_t size) { size_t asize; size_t extendsize; char *bp; if (size <= 0) return NULL; if (size <= DSIZE) asize = DSIZE + OVERHEAD; else asize = DSIZE * ((size + (OVERHEAD) + (DSIZE-1)) / DSIZE); if ((bp = find_fit(asize)) != NULL) { place(bp, asize); return bp; } extendsize = MAX(asize,CHUNKSIZE); if ((bp = extend_heap(extendsize/WSIZE)) == NULL) return NULL; place(bp, asize); return bp; }Finding First Fitstatic void *find_fit(size_t asize) { void *bp; 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;}Placing a block in a free chunkstatic 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)); } }Freevoid 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); }Adding debugging informationFor each allocated blockrequest_id : malloc request counter (0..)Initialize in mm_initIncrement in mallocpayload size : the memory requested by mallocCan be different from the allocated sizeWhere do we store thisIn the allocated block headerAllocated Block FormatHeaderFooterPayloadPointer returnedby malloc (Block Pointer (bp))32 bits 32 bits >= what user askedfor in malloc32 bits 32 bits request_idpayload sizeOne way to implement thisInside mallocAllocate additional memory in mallocOVERHEAD = 16PUT(bp,request_counter); PUT(bp+4,size);return bp+DSIZE;Inside Free bp = bp – DSIZE;HeapcheckPut all sorts of sanity checksScan the implicit list like the first fit function print request_id and sizeExplicit ListsSeparate Free ListCan find a free block quicklyChange Free Block FormatAdd prev pointerAdd next pointerWhere to store free list pointerOnly one WORDCan store in unused PAD wordSome functions to addstatic void insertfree_block(void * freeblkptr); static void removefree_block(void *
View Full Document