Recitation 10 Malloc Lab Andrew Faulring 15213 Section A 11 November 2002 Logistics faulring cs cmu edu Office hours Exam 2 NSH 2504 Tuesday 2 3 Tuesday 12 November 6 00 7 20pm Doherty Hall 2315 Lab 6 Malloc due next Tuesday 19 November Today s Plan The Malloc Lab Understand mm helper c Adding debugging info to mm helper c What does mm helper c do Implicit Free List First Fit Header with each block size allocated bit No separate Free List free blocks linked implicitly by size fields in header Searches free list from beginning and picks first block that fits Immediate Boundary Tag Coalescing Footer boundary tag replica of header Block Format Header 32 bits Pointer returned by malloc Block Pointer bp Payload Footer what user asked for in malloc 32 bits Header Footer Format 3 31 size 1 0 0 Double word alignment 2 Three lower order bits of size always 0 Pack size and allocated bits into a single integer Size 24 0x18 Block is allocated Header 0 x18 0x1 0x19 0 a Heap Format Pad Prologue Header Footer Header 8 1 8 1 Epilogue 0 1 Allocated and Free Blocks Double Word Alignment Footer Very Useful Macros define WSIZE 4 define DSIZE 8 define CHUNKSIZE 1 12 define OVERHEAD 8 Very 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 heap int 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 Heap static 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 Coalescing 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 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 Malloc void 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 Fit static 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 chunk 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 Free 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 Adding debugging information For each allocated block request id malloc request counter 0 payload size the memory requested by malloc Initialize in mm init Increment in malloc Can be different from the allocated size Where do we store this In the allocated block header Allocated Block Format Header 32 bits request id 32 bits payload size Pointer returned by malloc Block Pointer bp Payload Footer 32 bits what user asked for in malloc 32 bits One way to implement this Inside malloc Allocate additional memory in malloc OVERHEAD 16 PUT bp request counter PUT bp 4 size return bp DSIZE Inside Free bp bp DSIZE Heapcheck Put all sorts of sanity checks Scan the implicit list like the first fit function print request id and size Explicit Lists Separate Free List Change Free Block Format Add prev pointer Add next pointer Where to store free list pointer Can find a free block quickly Only one WORD Can store in unused PAD word Some functions to add static void insertfree block void freeblkptr static void removefree block void freeblkptr
View Full Document
Unlocking...