15213 Recitation Section C Shimin Chen Nov 11 2002 Outline Understanding mm helper c Adding debugging info to mm helper c What does mm helper c do Implicit Free List Header with each block size allocated bit No separate Free List free blocks linked implicitly by size fields in header First Fit Searches free list from beginning and picks first block that is large enough Immediate Boundary Tag Coalescing Footer boundary tag replica of header 15213 Recitation C 2 Shimin Chen Block Format Header 32 bits Pointer returned by malloc Block Pointer bp Payload Footer 15213 Recitation C 3 what user asked for in malloc 32 bits Shimin Chen Header Footer Format 3 31 size 1 0 0 0 a Double word alignment 2 Three lower order bits of size always 0 Pack size and allocated bits into a single integer 15213 Recitation C Size 24 0x18 Block is allocated Header 0 x18 0x1 0x19 4 Shimin Chen Heap Format 4 bytes Pad Prologue 8 1 8 1 Epilogue Footer Header Header Footer 0 1 Allocated and Free Blocks Double Word Alignment 8 bytes 15213 Recitation C 5 Shimin Chen Very Useful Macros define WSIZE 4 define DSIZE 8 define CHUNKSIZE 1 12 define OVERHEAD 8 15213 Recitation C 6 Shimin Chen 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 15213 Recitation C 7 Shimin Chen 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 15213 Recitation C 8 Shimin Chen 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 15213 Recitation C 9 Shimin Chen 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 15213 Recitation C 10 Shimin Chen Malloc void mm malloc size t size size t asize 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 15213 Recitation C 11 Shimin Chen 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 15213 Recitation C 12 Shimin Chen Malloc void mm malloc size t size size t asize 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 15213 Recitation C 13 Shimin Chen Placing a Block in a Free Block 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 15213 Recitation C 14 Shimin Chen Malloc void mm malloc size t size size t asize 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 15213 Recitation C 15 Shimin Chen 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 15213 Recitation C 16 Shimin Chen Coalesce Called by mm free extend heap 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 15213 Recitation C 17 Shimin Chen Adding Debugging Information mm heapcheck Display request id and payload of every active block request id malloc request counter 0 mm init sets the counter to 0 mm malloc increments the counter payload size the memory requested by malloc Can be different from the allocated size We need to store the info somewhere 15213 Recitation C 18 Shimin Chen Allocated Block Format Header 32 bits request id 32 bits payload size Pointer returned to user Payload Footer 15213 Recitation C 19 32 bits what user asked for in malloc 32 bits Shimin Chen One Way to Implement This Inside malloc Allocate additional memory in malloc PUT bp request counter PUT bp 4 size return bp DSIZE Inside Free 15213 Recitation C bp bp DSIZE 20 Shimin Chen Heapcheck Put all sorts of sanity checks Scan the implicit list like the first fit function print request id and size 15213 Recitation C 21 Shimin Chen 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 15213 Recitation C 22 Shimin Chen
View Full Document
Unlocking...