L6: Malloc Lab Writing a Dynamic Storage Allocator October 30, 2006L6: Malloc LabSome sort of useful backgroundsSo what is memory allocation?Malloc PackageAllocation ExamplesPerformance goalsImplementation IssuesImplementation Issues 1: Free Block OrganizationKeeping Track of Free BlocksFree Block OrganizationSlide 12Implementation Issues 2: Placement PolicyImplementation Issues 3: SplittingImplementation Issues 4: CoalescingSlide 16Performance goal (1) - ThroughputPerformance goal (2) – Memory UtilizationInternal FragmentationExternal FragmentationThe Malloc LabAssumptionsPorting to 64-bit MachineUsing MACROS – why?Approach AdviceHeap Checker (10 pts)Slide 27Style (10 pts)Debugging TechniquesDebugging TipsMore Hints?Slide 32Questions ?L6: Malloc LabWriting a Dynamic Storage AllocatorOctober 30, 2006L6: Malloc LabWriting a Dynamic Storage AllocatorOctober 30, 2006TopicsTopicsMemory Allocator (Heap)L6: Malloc LabRemindersRemindersL6: Malloc Lab Due Nov 10, 2006 Section A (Donnie H Kim) recitation8.ppt (some slides from lecture notes)15-213“The course that gives CMU its Zip!”– 2 –15-213, F’06L6: Malloc Lab L6: Malloc Lab Things that matter in this labThings that matter in this lab::Performance goalMaximizing throughputMaximizing memory utilizationImplementation Issues (Design Space)Free Block OrganizationPlacement PolicySplittingCoalescingAnd some advice– 3 –15-213, F’06Some sort of useful backgroundsSome sort of useful backgrounds– 4 –15-213, F’06So what is memory allocation?So what is memory allocation?kernel virtual memoryMemory mapped region forshared librariesrun-time heap (via malloc)program text (.text)initialized data (.data)uninitialized data (.bss)stack0%espmemory invisible to user codethe “brk” ptrAllocators requestadditional heap memoryfrom the operating system using the sbrk function.– 5 –15-213, F’06Malloc PackageMalloc Package#include <stdlib.h>#include <stdlib.h>void *malloc(size_t size)void *malloc(size_t size)If successful:Returns a pointer to a memory block of at least size bytes, (typically) aligned to 8-byte boundary.If size == 0, returns NULLIf unsuccessful: returns NULL (0) and sets errno.void free(void *p)void free(void *p)Returns the block pointed at by p to pool of available memoryp must come from a previous call to malloc or realloc.void *realloc(void *p, size_t size)void *realloc(void *p, size_t size) Changes size of block p and returns pointer to new block.Contents of new block unchanged up to min of old and new size.– 6 –15-213, F’06Allocation ExamplesAllocation Examplesp1 = malloc(4)p2 = malloc(5)p3 = malloc(6)free(p2)p4 = malloc(2)– 7 –15-213, F’06Performance goalsPerformance goalsMaximizing throughput (Temporal)Maximizing throughput (Temporal)Defined as the number of requests that it completes per unit timeMaximizing Memory Utilization (Spatial)Maximizing Memory Utilization (Spatial)Defined as the ratio of the requested memory size and the actual memory size usedThere is a tension between maximizing throughput and utilization! Find an appropriate balance between two goals!Keep this in mind, we will come back to these issues Keep this in mind, we will come back to these issues– 8 –15-213, F’06Implementation IssuesImplementation IssuesFree Block OrganizationFree Block OrganizationHow do we keep track of the free blocks?How do we know how much memory to free just given a pointer?Placement PolicyPlacement PolicyHow do we choose an appropriate free block?SplittingSplittingWhat do we do with the extra space when allocating a structure that is smaller than the free block it is placed in?CoalescingCoalescingHow do we reinsert freed block?p1 = malloc(1)p0free(p0)– 9 –15-213, F’06Implementation Issues 1: Free Block OrganizationImplementation Issues 1: Free Block OrganizationIdentifying which block is free or allocatedIdentifying which block is free or allocatedAvailable design choices of how to manage free blocksImplicit ListExplicit ListSegregated ListHeader, Footer organization storing information about the block (size, allocated, freed)– 10 –15-213, F’06Keeping Track of Free BlocksKeeping Track of Free BlocksMethod 1Method 1: : Implicit listImplicit list using lengths -- links all blocks using lengths -- links all blocksMethod 2Method 2: : Explicit listExplicit list among the free blocks using among the free blocks using pointers within the free blockspointers within the free blocksMethod 3Method 3: : Segregated free listSegregated free listDifferent free lists for different size classesMethod 4Method 4: Blocks sorted by size: Blocks sorted by sizeCan use a balanced tree (e.g. Red-Black tree) with pointers within each free block, and the length used as a key5 4 265 4 26– 11 –15-213, F’06 Free Block Organization Free Block OrganizationFree Block with headerFree Block with headersize1 wordFormat ofallocated andfree blockspayloada = 1: allocated block a = 0: free blocksize: block sizepayload: application data(allocated blocks only)aoptionalpadding– 12 –15-213, F’06 Free Block Organization Free Block OrganizationFree Block with Header and FooterFree Block with Header and FootersizeFormat ofallocated andfree blockspayload andpaddinga = 1: allocated block a = 0: free blocksize: total block sizepayload: application data(allocated blocks only)asize aBoundary tag (footer)Header– 13 –15-213, F’06Implementation Issues 2: Placement PolicyImplementation Issues 2: Placement Policy““Placement Policy” choicesPlacement Policy” choicesFirst FitSearch free list from the beginning and chose the first free blockNext FitStarts search where the previous search has left ofBest FitExamine every free block to find the best free block– 14 –15-213, F’06Implementation Issues 3: Splitting Implementation Issues 3: Splitting ““Splitting” Design choicesSplitting” Design choicesUsing the entire free blockSimple, fastIntroduces internal fragmentation (good placement policy might reduce this)SplittingSplit free block into two parts, when second part can be used for other requests (reduces internal fragmentation)p1 = malloc(1)– 15 –15-213, F’06Implementation Issues 4: CoalescingImplementation Issues 4:
View Full Document
Unlocking...