CS170: Lab 0 - MyMalloc()

Your job is to write your own version of malloc(). C is, for the most part, a statically typed language which means that all data structures ... CS170TheMyMalloc() Lab CS170Labassignment0 Due:Wednesday,Oct6,2021at11:59p.m. Url: http://www.cs.ucsb.edu/~rich/class/cs170/labs/lab1.malloc simpletest1.cisaverysimpletestcodethat callsroutinesfromyourimplementation. simpletest2.cisanothersimpletestcodethat callsroutinesfromyourimplementationwhichthislabwrite-up usesasanexample. testnocompact.cisacomplicatedtestcodeyou canusebeforeyouhavecoalescingworking. testmymalloc.cisacomplicatedtestcode thatIusedtodebugmysolution.Itrequiresthatyouwriteadebugging functioncalledPrintMyMallocFreeList()inordertowork. Hereisamakefilethatbuildsthesetestcodes. Itassumesthatyouhavesuppliedyourversionofmy_malloc.c SomehelpfulhintsfromyourAuntHeloise Compiledversionsofthesecodesareavailableinthis directory Thispagelastupdated SatAug1009:08:43PDT2019 Thegoalofthislabistohelpyoutune-upyourCskills.Byfar,thetwo biggestsourcesofdifficultywithCarepointermanipulationand memorymanagement.Tosuccessfullycompletethislab,youwillneedto becomefacilewithboth. Yourjobistowriteyourownversionofmalloc().Cis,forthemost part,astaticallytypedlanguagewhichmeansthatalldatastructureshavea fixedsizeatcompiletime.Ifyouwanttomakeadatastructure(e.g.an array)thesizeofwhichisonlyknownwhentheprogramexecutes,youneedto usetheCutilitymalloc(). Inthislab,youwillwriteyourowndynamicmemoryallocatorcalled MyMalloc()thatyoushouldbeabletouseinplaceofthestandard malloc()utility.TheAPIforMyMalloc()isgiveninthe headerfilemy_malloc.hwhichisshownbelow. #if!defined(MY_MALLOC_H) #defineMY_MALLOC_H #defineMAX_MALLOC_SIZE(1024*1024*16) voidInitMyMalloc(); void*MyMalloc(intsize); voidMyFree(void*buffer); voidPrintMyMallocFreeList(); /*optionalfordebugging*/ #endif Youmustusethisheaderfileinyour solution.Ifyoudonot,yoursolution,howeverfunctional,is incorrect.Partoftheassignmentistodemonstratethatyouknowhowto programtoanexistingAPI,whichisaskillthatisessentialtoanoperating systemsproject. YouMUSTalsoputyoursourcecodeinasingle filewiththenamemy_malloc.csothattheautogradingsoftwarewillbe abletocorrectlyfindandbuildyourwonderfulsolution. TheMyMalloc()API Yourversionofmalloc()willdifferfromthestandardoneinonlyoneway. Theveryfirstcallthatshouldbemadeinanyprogramthatusesyour versionofMyMalloc()willbeacalltoInitMalloc()whichyou willwritetoperformanyinitializationyouneed.Forexample,considerthe codeinsimpletest1.cshownbelow. #include #include #include #include"my_malloc.h" intmain(intargc,char*argv[]) { char*array; inti; /* *mustbefirstcallintheprogram */ InitMyMalloc(); array=MyMalloc(10); if(array==NULL) { fprintf(stderr,"calltoMyMalloc()failed\n"); fflush(stderr); exit(1); } for(i=0;i<9;i++) { array[i]='a'+i; } array[9]=0; printf("hereismyniftynewstring:%s\n",array); MyFree(array); return(0); } Lookatthiscodecarefully.Thefirstexecutablecodeintheprogram main()isacalltoInitMyMalloc().Yoursolutionshoulduse thecalltoInitMyMalloc()toinitializeanyglobaldatastructuresyou willneed. ThecalltoMyMalloc()worksthesamewaythatthestandardmalloc does:ittakesoneintegerargumentwhichisasize,andreturnsapointerto acontiguousregionofthatmanybytes.Thus,thecallMyMalloc(10) returnsapointer(asavoid*which)to10contiguousbytesofmemorythat thecodehasallocated. AsaquickcheckofyourCskills,makesureyouunderstandwhatthecode shownabovedoes.Whatdoestheloopdo?Whyisarray[9]treated differently? ThecalltoMyFree()isanalogoustoacalltothestandardfree() routine.Ittakesasingleargumentwhichisassumedtobeapointerthatwas returnedbyapreviouscalltoMyMalloc().MyFree()isavoid function. Howmalloc()works Topullthisoff,ithelpstoknowhowitisthatmalloc()(andotherbasic memoryallocators)work.Thefirstthingtorealizeisthatthememoryspace willbetakenfromalarge,contiguousbuffer.Inyourprograms,youwill needtoallocatethisbufferasanarrayofbytes,thesizeofwhichis definedbyMAX_MALLOC_SIZE.Thisarrayshouldbeglobalanddefined inyourcode--notthecodeoftheprogramcallingyourroutines.For example unsignedcharBigBuffer[MAX_MALLOC_SIZE]; createsanarrayofMAX_MALLOC_SIZEbytes.Allofthespaceyou allocatewithMyMalloc()shouldcomefromthisarray. Thenextthingtounderstandisthatyourcodewillneedtokeeptrack ofanyspaceitgivesaway.Thisrecordkeepingisnecessaryfortworeasons. Thefirstisthatyouwillneedtokeeptrackoffreeandallocatedmemoryso thatyoudon'tallocatethesameregionofmemorytotwodifferent MyMalloc().Thesecondreasonisthat asspaceisgivenawayandthenreturnedtoyourcode(via MyFree(),yourbufferwillbecome"fragmented"aspartsofitremain allocatedandhaveyettobefreed.Wewillstudymemoryfragmentationlater inthisclassmorecompletely,buttogetanideaofwhatitmeans,consider thefollowingsimpleexample. AssumethatMAX_MALLOC_SIZEis1000.Yourarray,then,islarge enoughtoallocateamaximumof 1000bytes,andnomore.Initially,all1000bytesarefree. Now,let'sgothroughasetofexamplesusingthecodeinsimpletest2.c.Forthisexample,assumethat MAX_MALLOC_SIZEhasbeensetto1000inmy_malloc.h. Now,let'sconsiderwhathappenswhenthecallMyMalloc(128)getsmade. Youwillneedto allocatethefirst128bytesandreturnapointertothefirstbytothe caller.Thus Inwhatfollows, we'llcolorallocatedspaceblacktoshowthatitisallocatedandleave freespacewhite. Let'snowsaythatMyMalloc(32)iscalled.Youcannotusethe first128bytessincetheyhavebeenalreadyallocatedandhavenotyetbeen freedbyMyFree().Thatwouldviolatethesemanticsofmallocwhich saysthatthememorywillbeallocateduniquelyuntilitisfreed. Howdoyouknowwherethenext32bytesshouldbe allocated?You'dprobablyliketousethe32bytesrightafterthe128 youallocatedlasttime,buthowareyougoingtofindthislocation? Theansweristhatyouneedtomaintainadatastructurethatkeepstrackof whatspaceisallocatedandwhatspaceisfree.Thetrickypartisfiguring outwheretokeepthedatastructure.Ifyouareimplementingmalloc()you can'tcallmalloc()(orelse,whywouldyouimplementit?).Instead,whatyou doistodefineaCrecordthat,moreorless,containsthefollowing information. structmalloc_stc { structmalloc_stc*next; structmalloc_stc*prev; intsize; unsignedchar*buffer; }; Thenextandprevpointersallowthisrecordtobemaintainedon adoublylinkedlist(we'llseewhyinaminute).Thesizeindicatesthesize oftheblock,andthebufferpointstothebeginningaddressoftheblock. Now,herecomesthetrickypart.You"stamp"thisdatastructureintoyour array,usingupalittleofitsspaceforbook-keeping.Typically,youput thespacerightinfrontoftheblockyou'veallocated.Sofortheprevious example,yourdatastructurewouldlooklike afterthecalltoMyMalloc(128).Takenoteofacoupleoffeaturesfrom thispicture.First,noticethat808bytes(andnot872bytes)areleftfree. Why?Becausethedatastructureyouareusingtokeeptrackofthespaceis 32byteslong(onthesystemswewillusethisquarter).Inthisexample,you lose64bytestobookkeepingoverhead(32bytesforeachbookkeepingrecord).Thatspacecomes outofyour freespacesinceyoumustreturn128bytesaccordingtothesemanticsof malloc. Therewillbeonebookkeepingrecordforeachallocatedblockandone bookkeepingrecordforeachfreeblockinyourmalloc()space. Now,let'sgothroughtheallocationprocess.Tokeeptrackofwherein yourarray youcanassignthis chunk,youkeepafreelistandlinkinallofthefreeblocks.Theheadof thefreelistisaglobalvariable.Whenyoustartout,thereshouldbeone blockonthefreelist.ItisthejobofInitMyMalloc()tosetup theinitialfreelist. AfteracalltoInitMalloc()theconfigurationshouldbethus: SplittingFreeBlocks Whenyouallocatethe128bytechunkinthecallMyMalloc(128)you splittheone,bigfreeblockintotwoblocks.Thefirstblockisthe onethatyouwillreturntotheuserofsize128.Noticethatyoudonot returnapointertoyourbook-keepingrecordtotheuser,butapointertothe firstbytethattheuserisfreetochange.Theuserofyourcodemustnot writebeyondthe128byte,norshouldheorshewritedatabeforethefirst availableaddress.Writingbeyondtheendofanallocatedblock(thereby destroyingthebook-keepingrecordthere)isacommonandverydifficultbug. Thesecondblockinyoursplitisbecomestheremainingfreespace.Youmust createanewbook-keepingrecordattheveryfrontofthisfreespacethat indicateitsstartinglocationandsize.Yourfreelisthead-pointershould beupdatedtopointtothenewfreeblock.Theresultofsplittingthe initialfreeblockintoa128byteallocatedchunkanda808bytefreechunkis whatisshowninthefigurebeforethislastone. Tokeepthediagramsreadable,wewillonlyshowthenextpointerson thefreelist.Thelistshouldbeadoublylinkedlist(withwhich youmustbefamiliar).Theprevpointersarebackpointersinthe oppositedirectionofthenextpointers andtheydoneedtobeset.Showingthemintherest ofthepictures,however,makesthediagramstoocomplex. Continuingtheexample,considerwhathappenswhenMyMalloc(32)is callednext.The808-bytefreeblockattheheadofthefreelistmustbe splitintoa32byteallocatedchunkand744-bytefreechunkwhichisatthe headofthelist(asshownbelow). Thefreelistheadpointmustbemovedtopointtothenewfreeblocksothat yourcodeknowswheretogetnewspaceifanothercalltoMyMalloc() occurs. FreeingSpace WhenacalltoMyFree()ismadebyauserofyourcode,youmust reclaimthespacebyputtingitonyourfreelist.Forexample,considerwhat happensifthe128-byteblockthatwasallocatedfirstisfreed.Theroutine MyFree()mustlinkthatblockintothefreelistand(forreasonsthat willbecomeclearinthenextsection)itisbestifthefreelistiskeptin sortedorder.Thefollowingfigureshowswhatyourdatastructuresshould looklikeafterthefirst128-byteblockisfreed. Theheadpointerpointstothe128-byteblockanditsnext pointerpointstothe744-byte freeblockattheendofthebuffer.Itisbestifyoumaintainthefreelist asadoubly-linkedlistsoprevpointer fortheendfreeblockpointsbacktothefirstblock aswell. Noticethattheallocatedspaceof32bytesisinbetweenthe 128-bytefreeblockatthefrontofthelistandthe744-byteblockandtheend ofthefreelist.Atthisstage,acalltoMyMalloc(745)shouldfail andreturnNULL.Why?Becausethereisnotafreeblockonyourfree listtopermityoutoallocatethespacecontiguously.Thetotalfree spaceinyourlistis128+744=872bytes,butthebiggestblockyoucan allocateisonly744byteslong.Thisproblemiscalledfragmentation andwewillstudyitlaterinthecourse.Fornow,youshouldrealize thatthisis,infact,aproblemthatthe"real"malloc()hasaswell. Alsonoticethatthe128-byteblockcomesbeforethe744-byteblockonthe list.Youcouldhavelinkeditinattheend,butitwouldmake coalescingfreespacemoredifficult.Whenyouimplement MyFree()youwillwanttoensurethatyourfreelistcontainsthefree blocksinsortedorder.Thatisfreeblockswithloweraddressesoccurbefore freeblockswithhigheraddressesonthelist. FirstFit Okay,atthispointyourfreelisthastwofreeblocksonit:onethatis128 byteslongandonethat744byteslong(asshowninthepreviousfigure). When acalltoMyMalloc(104)ismade,youneedtosplitthesecondfree blockbecause104bytesandthespaceneededforitsdatastructure(32 bytes)istoobigforthefirstfreeblockof128bytes.Hereisthe diagramforwhatyourdatastructuresshouldlooklikeafter MyMalloc(104)iscalledandthesecondfreeblockissplit. Yourfreeliststillonlycontainstwofreeblocks,butthesecondissmaller by136bytes(32bytesforthenewbook-keepingrecordand104bytes forthespace). If,atthispoint,acalltoMyMalloc(8)iscalled,wheredoyouget thespace?Inthisexample,therearetwochoices:eitheryousplitthe 128-bytefreeblockorthe608-bytefreeblocksinceeitherisbigenoughto accommodateanallocationof8bytesandthebook-keepingrecord. Itturnsoutthatagreatdealofresearchhasgoneintotryingtodetermine whichchoicetomake.Strange,isn'tit?We'llcovertheissuesinclass, butinthisassignment,youshouldimplementwhatiscalledfirst-fit bystartingattheheadofyourfreelistandwalkingdownthelist untilyoufindthefirstblockthatisbigenoughtoholdyourrequest. Inthepreviousexample,104byteswouldn'tfitinthefirstblocksoyouhad tomovedownthelist.Now,however,a8-byteblockwillfitinyour firstblock soyousplitthatblock(andnotthe608-byteblockattheend).Hereisthe pictureofwhatyourdatastructuresshouldlooklikeafterthecallto MyMalloc(8). Noticethattherearetwoblocksonthefreelistandhowthe128byteblock hasbeensplit.Whyistheremainingfreespacefromthatblock88bytes? Whatisthelargestallocationthatcouldcomefromthatfreeblockof88 bytesusingfirstfit? Bythispoint,you shouldunderstandcompletelywhythedatastructureslookthewaytheydo.If youdonot,gobackandre-readthelabuptothispointbeforemovingonto thenextsection.Ifyoustilldon'tunderstand,readitagain.ItisVERY importantthatyouunderstandhowthe datastructuresworkandhowtheygottothisstateinordertosuccessfully completethislab. AFewWordsConcerningAlignment Forreasonsthat,someday(nottoday)youwillcometoappreciate,I've deliberatelyusedallocationamountsinthepreviousexamplesthatare evenmultiplesof8.Thischoice,itturnsout,isnotaccidental.The machinesweusetoday,andthemachinewilluseinthefuturelabassignments inthisclass,allrequirethatcertainCdatatypesbealignedtomemory addressesthatareevenmultiplesof2,otherstomultiplesof4,andstill otherstomultiplesof8.Forthislab,becausewewillbecompilingthethe currentx86architecture,itturnsoutthatthespaceyouallocateneedtobe alignedonmemoryaddressesthatareevenmultiplesof8.Why?Becausethe x86machineswewilluserequiredthatpointersbe"8-bytealigned".That means,anymemoryaddressthatcancontainapointermustbeevenlydivisible by8. Youcanseethisrequirementbytakingacloselookatthebook-keepingdata structure structmalloc_stc { structmalloc_stc*next; structmalloc_stc*prev; intsize; unsignedchar*buffer; }; Whyisthesizeofthisdatastructure32bytes?First,onthecurrentx86, pointersare8-bytesinsize.Integers,however,areonly4-bytes.Thus,if youaddupthesizesinthisstructyoushouldget28bytesandnot32 bytes.Thereasonitis32bytes(youcanverifythisinyourcodeby printingsizeof(structmalloc_stc)isbecausethecompiler wantsthepointerunsignedchar*buffertostartonamemoryaddress evenlydivisibleby8. Whenthisstructureisallocatedeitherasaglobal variableorasalocalvariableonafunction'sstack,thecompilerwllensure thatthestartingaddressisdivisibleby8.Thusthefirsttwopointers structmalloc_stc*nextandstructmalloc_stc*prevwhichwill beputintoconsecutivememorylocations,willbothhavememoryaddresses divisibleby8.Noticethattheintegerintsizemusthaveamemory addressdivisibleby4.Becauseitoccursrightafterapointerinthe structure,itwillhaveamemoryaddressdivisibleby8,whichisalsodivible by4sothereisnoalignmentproblems. However,tomakesurethatunsignedchar*bufferhasamemoryaddress divisibleby8,thecompilerputsinpadding(wastedspace)of4bytesbetween intsizeandunsignedchar*buffer.Thus,intsizeis reallygiven8bytesofspacebut,becauseitisaninteger,theCPUwillonly use4ofthem(theother4arewasted).Asaresult,however,thesizeof thisdatastructureis32bytes(where4bytesarepaddinginsertedbythe compiler). Whatdoesthishavetodowithyouandmalloc()?Asyouarehopefully comingtounderstand,malloc()isafunctionthatallocatesspaceat runtime--notcompiletime.Thusthecompilercan'tbeassuredthatthe memoryassociatedwiththestructurewillstartonan8-bytememoryboundary thewayitcanwhenitisalocalorglobalvariable. Thisissueplacestwosubtlerequirementsonyoursolutionsforthislab.The firstisthatyourbook-keepingstructurewillalwaysneedtostartonan 8-byteboundary.Youcanassumethatthecompilerwillmaketheglobal variablethatyouuseasyourmalloc()space8-bytealigned.Thatis, "BigBuffer"inthefirstfigureofthiswrite-upis8-bytealigned. Asecondmoresubtlerequirementisthatyourimplementationofmalloc() onlyreturnspacethatstartsonan8-byteboundary.Why?Becauseif malloc()doesn'tdothat,everyCprogramwouldneedtoalignitsdata structuresexplicitlywhenusingmalloc().TheoriginalversionofCdidnot havethisrequirementanditturnsouttobearealdifficultyifitisadded. Thus,themodernversionofmalloc(),andyourimplementationofMyMalloc(), mustreturnpointerstomemorythatis8-bytealigned. Thisrequirement,whiledifficulttoexplain,iseasytoimplement.You simplyneedtoroundeachrequesttoMyMalloc()uptothenearest multipleof8(assumingyourbookkeepingstructureisamultipleof8bytesas itisinmyexample).SoifaprogramcallsMyMalloc(6)youround6up to8andallocate8bytes(theextra2bytesarewastedpadding). We'llencounteralignmentissuesintheupcominglabssonowisagoodtime tounderstandwhattheyareandhowtheycomeaboutevenifyoucan makeyourlabsolutionforthislab"work"bysimplyroundingup.Trustme. CoalescingFreeSpace Whatif,atthispoint,alltheallocateddatawerefreedusing MyFree()?YourimplementationofMyFree()shouldputeachfree blockonthefreelistinorderoftheaddresses,asshownhere. Doingsorequiresyoutowalkdownthefreelistand"find"whereaparticular blockgoeswhenitisfreed.Obviously,youcannotcountonauserprogram tofreeyourblocksinorder.ItisthecodeinMyFree()thathasto takecareofthisdetail.Andhere'swhy. Noticethatafterallofthespaceisfreed,yourfreespaceisstillbroken upintofixed-sizedchunks.Before,therewasanallocatedblockbetweenthe twofreeblockswhichcausedthefragmentationofthefreespaceNow, however,theboundariesbetweenblocksdonotdelineatefreeandallocated blocks.Assuch,thereisnoreasontokeeptheblockssubdivided--the shouldbecoalesced.Thatis,yourcode,asitisexitingtheroutine MyFree()shouldfindfreeblocksthatareadjacettoeachotherand mergethembackintobiggerfreeblocks.Bykeepingthelistinsortedorder, youcandothismerging(calledcoalescing)inonepassofthelist. Forexample,ifyourcoalescingfunctionweretostartatthebeginningof thisfreelistandwalkdown,itcouldlookateachblockandtheblockbefore it.Iftheendofonefreeblockisexactlyagainstthebook-keepingrecord ofanotherfreeblock,theblockscanbemerged. Mergingtwoblocksissimple.Youchooseoneblocktoabsorbtheother.If yourlistissortedsmallestaddresstobiggest(asinthisexample)choosing theblockoccuringearlierinthelistisabetterchoice.Ifyoudo,then theprocedureistoaddthespaceofthesecondblockandits book-keepingrecordtothespaceinthefirstblock.Nowtheblocksare"one" (don'tworryaboutre-initializingthebook-keepingrecordyoulosttoall zeros--malloc()doesn'tspecifywhatthecontentswillbeoftheallocated memory).Theonlythinglefttodonowistounlinkthesecondblock(theone youhaveremoved)fromthefreelistsinceitsspacehasbeenabsorbedinto thefirstblock.Noticethatbychoosingthefirstblockastheabsorber,you cannowconsideryournewlistwithoutstartingoveratthebeginning.That is,youcanlookatyournewbigblockandtheblockthatcomesafteriton yournewfreelisttoseeifyoucandoanyfurthermerging.Ifyoucan't, youmoveondownthelist. Hereisapictureofwhatyourlistshouldlooklikeafterthefirsttwo blockshavebeenmerged. Yourcodeshouldbeabletorepeatthisprocessuntilnomoremergesare possible.Ifyouhavedoneitcorrectly,attheend,youwillbeleftwith onebigfreeblockattheheadofyourlist. Thelastquestionconcernswhentocallcoalesce.Youreallyhavetwo options,eitheroneofwhichisfine.Thefirstoptionistocallitwhenever MyFree()isabouttoexit.Ifyoudo,yourcodewillcoalesceatmost 3blocks.Why?Thinkaboutitaminuteandyou'llseethatMyFree() onlyfreesoneblock.Ifthatblockisbetweentwofreeblocks,thenyou'll dotwomerges(onewiththeblockinfront,andonethatmergestheresult withthefreeblockbehind).ThisisthesolutionIchosebecauseitismuch easiertodebug(youonlyhavetoexaminethreeblocksintheworstcase). TheotheroptionistowaituntilacalltoMyMalloc()failsbecause thereisnospace.Inthisversion,youwouldwalkdownthelistlookingfor thefirstblockthatwillfit.Ifyoudon'tfindone,youcallcoalesceto trytocoalescealloftheblocksthatyoucan,andthenyoure-walk downthelisthopingthatyou'vemergedthingstogetherenoughtosatisfythe request.Ifthispassfails,youmustreturnNULL. ACoupleofImportantDetails Thereisanadditionalwrinkleaboutwhichyoumustbecareful.Thefirstoccurswhen you'velocatedablockthatfits,butsplittingtheblockwon'tworkbecause thefitistootight.Forexample,let'ssaythatacallto MyMalloc(120)getsmadeandthefirstblockonyourfreelistthatyou findthatisbiggerthan120hassize128.Thesizeoftherequestfits(120 islessthan128)butwhenyouaddthebook-keepingrecord,thetotalistoo big(152fortherequestversus128fortheavailablefreeblock). Ifyoureadthedescriptionof splittingcarefullyyou'llseethatwhatyouwouldnormallydoistowritea newrecordfortheremainingfreespaceinjustafterthe120thbyte,butthat recordis32byteslong.Theleft-overspaceisonly8bytes,soyour32 byterecordwould"spillover"intothenextblock. Youhavetwooptionsherethatyieldacorrectresult. Oneisto"hijack"the128-bytefreeblock. Becausetheuserdoesn'tknow(can'tsee)yourbook-keepingrecords,ifyou handoutablockthatisbiggerthanrequested,theuserwillbe none-the-wiser.Thusyoucouldsimplyreturnthepointertothe128-byte blockandunderstandthattheuserisonlygoingtouse120bytes(becauseshe doesn'tknowthereareextrabytes). Theproblemwiththisapproachisthatitcanbequitewastefulifyour book-keepingrecordsarelarge.Inmycode,theyare32byteswhichmeans(in additiontopadding)Imightwasteasmuchas32bytesofspacebychoosing thefirstrequestthatfitsandhijackingthelargerrecord.Iimplemented hijackinginthiswayinmysolutionsince32bytes(max)isasmallamountto waste. Thesecondoptionistomaketwopasses.Inthefirstpassyoulookforthe bestfitwhereyoucanimplementthesplit(i.e.therequestedspaceandthe book-keepingrecordfitintothefreeblock).Ifthispassfails,thenyou makeasecondpasslookingforablocktohijack.Theexamplefiguresinthis writeupassumeatwo-passapproach(eventhoughmyimplementationusesthe alternative).Thusthe104-byteblockdoesnothijackthe128-byteblock,but insteadsplitsthelargerblockattheendofthefreelist. Inthisassignmentyoufreetoimplementeither.However,noticethatyoucan onlyusehijackingwhentherequestfits,butthebook-keepingrecordputsyou overtheavailablespace.YouCANNOTsimplyhijackthefirstblock wheretherequestfits.Ifyoudon'tseewhy,askyourselfwhatwouldhappen if,atthebeginning,whenthefirstcalltoMyMalloc()ismade, youhijackedthefirstfreeblockyoufind. TheAssignment--WhattoTurnIn Youaretoimplementthefunctions: InitMyMalloc() MyMalloc() MyFree() PrintMyMallocFreeList() accordingtotheAPIinmy_malloc.handtheoutputformatfor PrintMyMallocFreeList()shouldbe block:0x1057ec060 size:4194304 next:0x1063ec0c0 prev:0x0 buffer:0x1057ec080 block:0x1063ec0c0 size:4194176 next:0x0 prev:0x1057ec060 buffer:0x1063ec0e0 Inthisexample,thefirstblockistheheadofthefreelist(theprev pointer isNULL).Noticethatthenextpointercontainsthesameaddressasthe addressofthesecondblockwhichisthealsothetailofthefreelist(the nextpointerisNULL). Thesefunctionsshouldallbecontainedinasinglefilecalled my_malloc.csothat theautogradingsoftwaresuppliedbyUCSBcancompileyourcode asaseparatelyloadablemodule(i.e.aC".o"file).Thefilethatcontains thecodefortheseroutinescannotcontainadefinitionforthefunction main().Wewillbelinkingthe".o"objectfileproducedbyyour my_malloc.c(whenitiscompiled)withtestroutinesthatincludea defintionofthefunctionmain().Ifthesetermsareunfamiliarto you,pleasereviewtheClecturenotesoraCtutorialwithrespecttousing makeandseparatelycompiledobjectfiles. Youmayimplementthecodeanyway youlike.Inparticular,youmayeithercoalescewhenyourunoutofspaceor whenMyFree()isterminating.Itmustbehaveinthesamewayas malloc()does,however,withtheexceptionthatmain()willbeallowed tocallInitMyMalloc()beforeanycallstoMyMalloc()or MyFree(). TheTAswillbetestingyourcodebycompilingitwiththeirowntestcodes. Theywillusethisversionofmy_malloc.hsoitis VERYimportantthatyoudonotchangethis headerfilein anyway.Ifyourcodedependsonachangetothisheaderfileandwon'twork otherwise,itwillfailwhentheTAsgradeyourassignment.