Dynamic Memory Allocation IHarsh 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 BlockImplicit 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 IDynamic Memory Allocation ITopicsTopicsSimple explicit allocatorsData structuresMechanismsPoliciesCS 105Tour of the Black Holes of Computing– 2 –CS 105Harsh RealityHarsh RealityMemory MattersMemory MattersMemory is not unboundedMemory is not unboundedIt must be allocated and managedMany applications are memory-dominatedMemory referencing bugs especially perniciousMemory referencing bugs especially perniciousEffects are distant in both time and spaceMemory performance is not uniformMemory 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 –CS 105Dynamic Memory AllocationDynamic Memory AllocationExplicit vs. Implicit Memory AllocatorExplicit vs. Implicit Memory AllocatorExplicit: application allocates and frees space E.g., malloc and free in CSemi-implicit: application allocates, but does not free spaceE.g. garbage collection in JavaImplicit: allocation and freeing done "under covers"ML, Lisp, Python, Perl, RubyAllocationAllocationIn all cases allocator provides abstraction of memory as set of blocksDoles out free memory blocks to applicationDone by run-time system (in user mode)ApplicationDynamic Memory AllocatorHeap Memory– 4 –CS 105Process Memory ImageProcess Memory Image(kernel virtual memory)Memory-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 –CS 105Malloc 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 to by p to pool of available memoryp MUST come from a previous call to malloc or realloc.NULL not a legal argument (sigh)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 –CS 105Malloc ExampleMalloc Examplevoid foo(int n, int m) { int i, *p; /* allocate a block of n ints */ if ((p = (int *) malloc(n * sizeof(int))) == 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 –CS 105AssumptionsAssumptionsAssumptions made in this lectureAssumptions made in this lectureMemory is byte-addressedWords are 4 bytesPointer fits in a word (4 bytes)All diagrams are word-basedAllocated block(4 words)(16 bytes)Free block(3 words)(12 bytes)Free wordAllocated word– 8 –CS 105Allocation ExamplesAllocation Examplesp1 = malloc(16)p2 = malloc(20)p3 = malloc(24)free(p2)p4 = malloc(8)– 9 –CS 105ConstraintsConstraintsApplications:Applications:Can issue arbitrary sequence of allocation and free requestsFree requests must correspond to an allocated block—i.e., pointer must be correctAllocatorsAllocatorsCan’t control number or size of allocated blocksMust respond immediately to all allocation requests i.e., can’t reorder or buffer requestsMust allocate blocks from free memory i.e., can only place allocated blocks in free memoryMust align blocks so they satisfy all alignment requirements 8-byte alignment for GNU malloc (libc malloc) on Linux boxesCan only manipulate and modify free memoryCan’t move the allocated blocks once they are allocated i.e., compaction is not allowed– 10 –CS 105Goals of Good malloc/free Goals of Good malloc/free Primary goalsPrimary goalsGood time performance for malloc and freeIdeally should take constant time (not always possible)Should certainly not take time linear in number of blocksGood space utilizationUser-allocated structures should be large fraction of the heap.Want to minimize “fragmentation” (to be defined later)Some other goalsSome 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 p1 – don’t free it twice, or free some other ptr…Can check that memory references are to allocated space– 11 –CS 105Performance Goals: ThroughputPerformance Goals: ThroughputGiven some sequence of malloc and free requests:Given some sequence of malloc and free requests: R0, R1, ..., Rk, ... , Rn-1Want to maximize throughput, minimize “wasted” spaceWant to maximize throughput, minimize “wasted” spaceThese goals often conflictThroughput:Throughput: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 –CS 105Performance Goals: Peak Memory UtilizationPerformance Goals: Peak Memory UtilizationRelated to wasted spaceRelated to wasted spaceGiven some sequence of malloc and free requests:Given some sequence of malloc and free requests: R0, R1, ..., Rk, ... , Rn-1Def:
View Full Document
Unlocking...