427CS 536 Spring 2008©Whether allocation is explicit orimplicit, a heap allocator isneeded. This routine takes a sizeparameter and examines unusedheap space to find space thatsatisfies the request.A heap block is returned. Thisblock must be big enough tosatisfy the space request, but itmay well be bigger.Heaps blocks contain a headerfield that contains the size of theblock as well as bookkeepinginformation.The complexity of heap allocationdepends in large measure on howdeallocation is done.Initially, the heap is one largeblock of unallocated memory.Memory requests can be satisfiedby simply modifying an “end of428CS 536 Spring 2008©heap” pointer, very much as astack is pushed by modifying astack pointer.Things get more involved whenpreviously allocated heap objectsare deallocated and reused.Deallocated objects are stored forfuture reuse on a free space list.When a request for n bytes ofheap space is received, the heapallocator must search the freespace list for a block of sufficientsize. There are many searchstrategies that might be used:• Best FitThe free space list is searched forthe free block that matches mostclosely the requested size. Thisminimizes wasted heap space, thesearch may be quite slow.429CS 536 Spring 2008©• First FitThe first free heap block ofsufficient size is used. Unusedspace within the block is split offand linked as a smaller free spaceblock. This approach is fast, butmay “clutter” the beginning of thefree space list with a number ofblocks too small to satisfy mostrequests.• Next FitThis is a variant of first fit in whichsucceeding searches of the freespace list begin at the positionwhere the last search ended. Theidea is to “cycle through” the entirefree space list rather than alwaysrevisiting free blocks at the head ofthe list.430CS 536 Spring 2008©• Segregated Free Space ListsThere is no reason why we musthave only one free space list. Analternative is to have several,indexed by the size of the freeblocks they contain.431CS 536 Spring 2008©Deallocation MechanismsAllocating heap space is fairlyeasy. But how do we deallocateheap memory no longer in use?Sometimes we may never need todeallocate! If heaps objects areallocated infrequently or are verylong-lived, deallocation isunnecessary. We simply fill heapspace with “in use” objects.Virtual memory & paging mayallow us to allocate a very largeheap area.On a 64-bit machine, if weallocate heap space at 1 MB/sec,it will take 500,000 years to spanthe entire address space!Fragmentation of a very largeheap space commonly forces usto include some form of reuse ofheap space.432CS 536 Spring 2008©User-controlled DeallocationDeallocation can be manual orautomatic. Manual deallocationinvolves explicit programmer-initiated calls to routines likefree(p) or delete(p).The object is then added to a free-space list for subsequentreallocation.It is the programmer’sresponsibility to free unneededheap space by executingdeallocation commands. The heapmanager merely keeps track offreed space and makes it availablefor later reuse.The really hard decision—whenspace should be freed—is shiftedto the programmer, possiblyleading to catastrophic danglingpointer errors.433CS 536 Spring 2008©Consider the following C programfragmentq = p = malloc(1000);free(p);/* code containing more malloc’s */q[100] = 1234;After p is freed, q is a danglingpointer. q points to heap spacethat is no longer consideredallocated.Calls to malloc may reassign thespace pointed to by q.Assignment through q is illegal,but this error is almost neverdetected.Such an assignment may changedata that is now part of anotherheap object, leading to verysubtle errors. It may even changea header field or a free-space link,causing the heap allocator itselfto fail!434CS 536 Spring 2008©Automatic Garbage CollectionThe alternative to manualdeallocation of heap space isgarbage collection.Compiler-generated code trackspointer usage. When a heapobject is no longer pointed to, it isgarbage, and is automaticallycollected for subsequent reuse.Many garbage collectiontechniques exist. Here are someof the most importantapproaches:435CS 536 Spring 2008©Reference CountingThis is one of the oldest andsimplest garbage collectiontechniques.A reference count field is added toeach heap object. It counts howmany references to the heapobject exist. When an object’sreference count reaches zero, it isgarbage and may collected.The reference count field isupdated whenever a reference iscreated, copied, or destroyed.When a reference count reacheszero and an object is collected, allpointers in the collected objectare also be followed andcorresponding reference countsdecremented.436CS 536 Spring 2008©As shown below, referencecounting has difficulty withcircular structures. If pointer P isset to null, the object’s referencecount is reduced to 1. Bothobjects have a non-zero count,but neither is accessible throughany external pointer. The twoobjects are garbage, but won’t berecognized as such.If circular structuresare common,then an auxiliary technique, likemark-sweep collection, is neededto collect garbage that referencecounting misses.LinkDataReference Count = 1Global pointer PLinkDataReference Count = 2437CS 536 Spring 2008©Mark-Sweep CollectionMany collectors, including mark &sweep, do nothing until heapspace is nearly exhausted.Then it executes a marking phasethat identifies all live heapobjects.Starting with global pointers andpointers in stack frames, it marksreachable heap objects. Pointersin marked heap objects are alsofollowed, until all live heapobjects are marked.After the marking phase, anyobject not marked is garbage thatmay be freed. We then sweepthrough the heap, collecting allunmarked objects. During thesweep phase we also clear allmarks from heap objects found tobe still in use.438CS 536 Spring 2008©Mark-sweep garbage collection isillustrated below.Objects 1 and 3 are markedbecause they are pointed to byglobal pointers. Object 5 ismarked because it is pointed toby object 3, which is marked.Shaded objects are not markedand will be added to the free-space list.In any mark-sweep collector, it isvital that we mark all accessibleheap objects. If we miss a pointer,we may fail to mark a live heapobject and later incorrectly free it.Global pointerGlobal pointerObject 1Object 3Object 5Internal pointer439CS 536 Spring 2008©Finding all pointers is a bit trickyin languages like Java, C and C++,that have pointers mixed withother types