Dynamic Memory Allocation I October 28, 2003Harsh RealityDynamic Memory AllocationProcess Memory ImageMalloc PackageMalloc ExampleAssumptionsAllocation ExamplesConstraintsGoals of Good malloc/freePerformance Goals: ThroughputPerformance Goals: Peak Memory UtilizationInternal FragmentationExternal FragmentationImplementation IssuesKnowing How Much to FreeKeeping Track of Free BlocksMethod 1: Implicit ListImplicit List: Finding a Free BlockBitfieldsImplicit List: Allocating in Free BlockImplicit List: Freeing a BlockImplicit List: CoalescingImplicit List: Bidirectional CoalescingConstant Time CoalescingConstant Time Coalescing (Case 1)Constant Time Coalescing (Case 2)Constant Time Coalescing (Case 3)Constant Time Coalescing (Case 4)Summary of Key Allocator PoliciesImplicit Lists: SummaryDynamic Memory Allocation IOctober 28, 2003Dynamic Memory Allocation IOctober 28, 2003TopicsSimple explicit allocatorsData structuresMechanismsPoliciesclass19.ppt15-213“The course that gives CMU its Zip!”– 2 –15-213, F’03Harsh RealityHarsh RealityMemory MattersMemory is not unboundedIt must be allocated and managedMany applications are memory dominatedEspecially those based on complex, graph algorithmsMemory referencing bugs especially perniciousEffects are distant in both time and spaceMemory performance is not uniformCache and virtual memory effects can greatly affect program performanceAdapting program to characteristics of memory system can lead to major speed improvements– 3 –15-213, F’03Dynamic Memory AllocationDynamic Memory AllocationExplicit vs. Implicit Memory AllocatorExplicit: application allocates and frees space E.g., malloc and free in CImplicit: application allocates, but does not free spaceE.g. garbage collection in Java, ML or LispAllocationIn both cases the memory allocator provides an abstraction of memory as a set of blocksDoles out free memory blocks to applicationWill discuss simple explicit memory allocation todayApplicationDynamic Memory AllocatorHeap Memory– 4 –15-213, F’03Process Memory ImageProcess Memory Imagekernel virtual memoryMemory mapped region forshared librariesrun-time heap (via malloc)program text (.text)initialized data (.data)uninitialized data (.bss)stack0%espmemory invisibleto user codethe “brk” ptrAllocators requestadditional heap memoryfrom the operating system using the sbrk function.– 5 –15-213, F’03Malloc PackageMalloc Package#include <stdlib.h>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)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) 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’03Malloc ExampleMalloc Examplevoid foo(int n, int m) { int i, *p; /* allocate a block of n ints */ p = (int *)malloc(n * sizeof(int)); if (p == NULL) { perror("malloc"); exit(0); } for (i=0; i<n; i++) p[i] = i; /* add m bytes to end of p block */ if ((p = (int *) realloc(p, (n+m) * sizeof(int))) == NULL) { perror("realloc"); exit(0); } for (i=n; i < n+m; i++) p[i] = i; /* print new array */ for (i=0; i<n+m; i++) printf("%d\n", p[i]); free(p); /* return p to available memory pool */}– 7 –15-213, F’03AssumptionsAssumptionsAssumptions made in this lectureMemory is word addressed (each word can hold a pointer)Allocated block(4 words)Free block(3 words)Free wordAllocated word– 8 –15-213, F’03Allocation ExamplesAllocation Examplesp1 = malloc(4)p2 = malloc(5)p3 = malloc(6)free(p2)p4 = malloc(2)– 9 –15-213, F’03ConstraintsConstraintsApplications:Can issue arbitrary sequence of allocation and free requestsFree requests must correspond to an allocated blockAllocatorsCan’t control number or size of allocated blocksMust respond immediately to all allocation requestsi.e., can’t reorder or buffer requestsMust allocate blocks from free memoryi.e., can only place allocated blocks in free memoryMust align blocks so they satisfy all alignment requirements8 byte alignment for GNU malloc (libc malloc) on Linux boxesCan only manipulate and modify free memoryCan’t move the allocated blocks once they are allocatedi.e., compaction is not allowed– 10 –15-213, F’03Goals of Good malloc/free Goals of Good malloc/free Primary goalsGood time performance for malloc and freeIdeally should take constant time (not always possible)Should certainly not take linear time in the number of blocksGood space utilizationUser allocated structures should be large fraction of the heap.Want to minimize “fragmentation”.Some other goalsGood locality propertiesStructures allocated close in time should be close in space“Similar” objects should be allocated close in spaceRobustCan check that free(p1) is on a valid allocated object p1Can check that memory references are to allocated space– 11 –15-213, F’03Performance Goals: ThroughputPerformance Goals: ThroughputGiven some sequence of malloc and free requests: R0, R1, ..., Rk, ... , Rn-1Want to maximize throughput and peak memory utilization.These goals are often conflictingThroughput:Number of completed requests per unit timeExample:5,000 malloc calls and 5,000 free calls in 10 seconds Throughput is 1,000 operations/second.– 12 –15-213, F’03Performance Goals: Peak Memory UtilizationPerformance Goals: Peak Memory UtilizationGiven some sequence of malloc and free requests: R0, R1, ..., Rk, ... , Rn-1Def: Aggregate payload Pk: malloc(p) results in a block with a payload of p bytes.. After request Rk has completed, the aggregate payload Pk is the sum of currently allocated payloads.Def: Current heap size is denoted by HkAssume that Hk is monotonically nondecreasingDef: Peak memory utilization: After k requests, peak memory utilization is:Uk = ( maxi<k Pi ) / Hk– 13 –15-213, F’03Internal FragmentationInternal FragmentationPoor memory utilization caused by fragmentation.Comes in two forms: internal and external fragmentationInternal fragmentationFor some block, internal fragmentation is the
View Full Document