How to write your own Malloc and Free using C? - TechFacts

How to write your own Malloc and Free using C? ; size_t size; /*Carries the size of the block described by it*/ ; struct block *next; /*Points to the next ... Skiptomaincontent HowtowriteyourownMallocandFreeusingC?                 Here,Iamgoingtopresentyouoneofthesimplestandeasy-to-understandcodefortheimplementationoftheMallocandFreefunctionsthatareusedfortheDynamicmemoryallocationanddeallocationinC.                 ThiscodewillworkfinewhenrunonaLinuxoperatingsystem. Clickheretogetthefullcode. Theconceptbehinditis, (QuotedfromMallocTutorial) Letmeexplainitfurther.           Basicideabehind:-                         Theblockofmemorycontainingthemetadata(dataaboutdata)isstoredadjacenttothespecificblockofallocatedmemoryaboutwhichitrefersto.Thismetadatablock,ormorespecificallythelinkedliststructure(asshownintheabovediagram),isrequiredbecauseweneedtoknowwhetheraparticularblockisfreeorwhetheritisalreadybeingallocatedandalsotoknowthesizeoftheblockwhichitrefersto.       Thisisthemetadatablockstructure,                               structblock{ size_tsize; intfree;                 structblock*next;              };                 Here,Iassumedablockofmemoryofsize20,000bytes charmemory[20000];  (assumingthatthestorageforacharacteris1byteinthemachine) andallthedatastructuresandtheallocatedmemoryblocksresideinthissamechunkofmemory.           NowIwillexplainthecode,partbypart:-       ThisistheCcodefortheheaderfilerequired. mymalloc.h    (Nameyourheaderfileinthisway) #include #include stddef.hisrequiredbecausethedefinitionforsize_tdatatypeisfoundthere. charmemory[20000]; Thisisthedeclarationofthearraywhichisconsideredasourmemory.Wegetacontiguousallocationofmemorybyusinganarray. /*Thestructuredefinitiontocontainmetadataofeachblockallocatedordeallocated*/ structblock{ size_tsize;/*Carriesthesizeoftheblockdescribedbyit*/ intfree; /*Thisflagisusedtoknowwhethertheblockdescribedbythemetadatastructureisfreeornot-->iffree,itissetto1.Otherwise0.*/ structblock*next;/*Pointstothenextmetadatablock*/ }; /*Pointingtothemainblockofmemorywhichisinitiallyfree(nostorageallocationyet)*/ structblock*freeList=(void*)memory; Hereweinitializeapointeroftype"block",namedfreeListpointingtothestartingaddressofthechunkofmemorywecreatedbefore.ThisfreeListpointerwillpointtothestartofthelinkedlistofmetadatablocks.Thestartingaddressofthearray(memory)shouldbecastedtotypevoidsothatweareabletoallocateblocksofmemorywhichareofdifferentdatatypes.(int,char,floatetc.) /*Thefunctiondefinitionswhicharedefinedinthenextsourcefilemalloc.c*/ voidinitialize(); voidsplit(structblock*fitting_slot,size_tsize); void*MyMalloc(size_tnoOfBytes); voidmerge(); voidMyFree(void*ptr); ThisistheCcodefortheimplementationofthemallocandfreefunctions mymalloc.c     (Nameyoursource fileinthis way) #include #include #include"mymalloc.h"/*Hereweincludetheheaderfilegivenabove*/ /*Initializingtheblockofmemory*/ voidinitialize(){ freeList->size=20000-sizeof(structblock);  freeList->free=1; freeList->next=NULL; } Thisiswhereweinitializethefirstmetadatablockupdateittorefertothenextblockofmemory. Thesizeoftheblockthatitreferstois(20000bytes-the_size_of_one_metadata_block) Toindicatethattheblockisnotyetallocated,wesetthefreeflagto1. Andthefirstmetadatablockhasnonextmetadatablockyet.SowesetnexttoNULL. /*Makingwayforanewblockallocationbysplittingafreeblock--(Assumefirstfitalgorithm)*/ voidsplit(structblock*fitting_slot,size_tsize){ structblock*new=(void*)((void*)fitting_slot+size+sizeof(structblock)); new->size=(fitting_slot->size)-size-sizeof(structblock); new->free=1; new->next=fitting_slot->next; fitting_slot->size=size; fitting_slot->free=0; fitting_slot->next=new; }         WeusetheFirst-fit-algorithmtofindafreeblocktoallocatememory.Assumethatwegetarequesttoallocateablockofmemoryofsize500bytes.Startingfromthefirstmetadatablockwecangoonsearchingforthefirstblockwhichhasenoughspacetoallocate.Ifwegetthefreeblocksizestobe250,130and750inorder,wewillallocatetheblockofsize750.         Ifwefindafreeblockwhichexactlyfitstherequiredsize,wedon'tneedtodothesplitting.Sothisfunctionisonlyrequiredifwehavewhatismorethanrequired.        Theargumentsacceptedbythisfunctionare---Apointertothemetadatablockwhichreferstotheblockofmemorywhosesizeismorethanrequired.(fitting_slot)andtherequiredsizeofthememorychunktobeallocated.         Herewecreateanewmetadatablockpointercalled"new".Anditshouldpointtothelocationprovidedbypassing(settingaside)ablockofmemorywhichisequaltothe_size_of_the_metadata_block_we_considered +the_size_requested_to_be_allocated         Thenthisnewpointerpointstothemetadatablockreferringtothenextfreechunk. Asyoucanseefromthecode,Ihavesettheattributesofboththenewandfitting_slotmetadatablocksaccordingly.  Note:ThemallocandfreefunctionsarenamedhereasMyMalloc()andMyFree().  /*FunctionMyMalloc(malloc)*/ void*MyMalloc(size_tnoOfBytes){ structblock*curr,*prev; WeneedmetadatablockpointerstotraversethroughthefreeList. void*result; Thisresultpointeristoreturnthestartingaddressoftheallocatedchunkofmemory. if(!(freeList->size)){  initialize(); printf("Memoryinitialized\n"); } Thisconditionwillinitializethememoryifitisnotinitializedatthebeginning.Thissetofstatementswillbeexecutedonlyifthesizeofthefirstmetadatablockisnotsetyet.Thatmeans,ifthememoryisstillnotinitialized. curr=freeList; Nowwemakethetemporarypointercurrtopinttothestartofthemetadatablocklist. while((((curr->size)free)==0))&&(curr->next!=NULL)){ Ifthisconditionismet,themetadatablockwecheckedcannotbeusedfortheallocation.Soweexecutethefollowingstatements.Thatisyougooncheckingonemetadatablockatatime. prev=curr; curr=curr->next; printf("Oneblockchecked\n"); } if((curr->size)==noOfBytes){ Ifthisconditionismet,themetadatablockwecheckedreferstoachunkofmemorythatexactlyfitstherequiredsize.Sosetthefreeflagto0,indicatingthatitisallocated.Thenreturnthestartingaddressoftheblockofallocatedmemory. curr->free=0; result=(void*)(++curr); printf("Exactfittingblockallocated\n"); returnresult; } elseif((curr->size)>(noOfBytes+sizeof(structblock))){ Ifthisconditionismet,themetadatablockwecheckedreferstoachunkofmemorythatisofsizegreaterthanwhatisrequired.Soinvokethesplit()functiontoallocateonlytheblockwhichisrequiredandthenreturnthestartingaddressoftheblockofallocatedmemory. split(curr,noOfBytes); result=(void*)(++curr); printf("Fittingblockallocatedwithasplit\n"); returnresult; } ElseitmeansthatthereisnosufficientmemorytoallocatesoyoushouldreturnaNULLpointer. else{ result=NULL; printf("Sorry.Nosufficientmemorytoallocate\n"); returnresult; } }     Therecanbeasituationwhereyouhaveconsecutiveblocksthataresetfreebydeallocatingaftertheywerepreviouslyallocated.ThisresultsinexternalfragmentationwhichwillcausetheMyMalloc()functiontoreturnaNULLpointeralthoughwehaveenoughmemorytoallocate.Thereforeweuseafunctioncalledmerge()tojointheconsecutivefreeblocksbyremovingthemetadatablockslyinginbetween. /*Thisistomergetheconsecutivefreeblocksbyremovingthemetadatablockinthemiddle.Thiswillsavespace.*/ voidmerge(){ structblock*curr,*prev; curr=freeList; while((curr->next)!=NULL){ if((curr->free)&&(curr->next->free)){ curr->size+=(curr->next->size)+sizeof(structblock); curr->next=curr->next->next; } prev=curr; curr=curr->next; } } Afterweallocatememoryforsomepurpose,itisareallygoodpracticetodeallocatethatmemoryifyouhavefinishedusingit,sothatitcanbeusedbyanotherpersonforhismemoryrequirement. WeusetheMyFree()functionforthat.  Ittakesthepointertoablockofmemorypreviouslyallocatedasaparameter. /*FunctionMyFree(free)*/ voidMyFree(void*ptr){ if(((void*)memory<=ptr)&&(ptr<=(void*)(memory+20000))){        Herewecheckwhethertheaddresstowhichthepointergivenasanargumenttothefunctionactuallylieswithintheaddressrangeofthememoryarraythatweusedforthepurpose.Ifyes,wesimplysetthefreeflaginthemetadatablockto1indicatingthatitisfreeandscanthroughandmergetheconsecutiveblocksthatarefree,ifany. structblock*curr=ptr; --curr; curr->free=1; merge(); } elseprintf("PleaseprovideavalidpointerallocatedbyMyMalloc\n"); } Ifavalidpointerisnotprovided,theabovemessagewillbeprinted. Sothatisthedetailedexplanationofthecode.(Youcanclickthelinkgivenatthetopofthepagetogetaccesstothefullcode) IhopeyougotabetterunderstandingonhowtoimplementyourownmallocandfreefunctionsusingC.                                  Thankyou! Share Getlink Facebook Twitter Pinterest Email OtherApps Share Getlink Facebook Twitter Pinterest Email OtherApps Comments BhanukaThirimanneNovember5,2015at8:48AMThisisgreatandeasytounderstand.thankyouverymuch.:)ReplyDeleteRepliesReplyAnonymousFebruary8,2016at3:52PMhy,thisisgoodtutorial,butmegrefucntionisbroken.ifyouhave1datainmemory:curr->next=curr->next->next;curr->next->next=0!!andwhenseecurraddressinwhile,curraddressisNULL,andprogramwilldie,ifNULL->next..ReplyDeleteRepliesAnonymousFebruary8,2016at3:55PMmegrefunction:while(curr&&curr->next){...}:DDeleteRepliesReplyReplykishanvadaliaAugust21,2016at10:51AMthnxReplyDeleteRepliesReplyAnonymousOctober5,2016at11:17AMthankyouforsavingmeReplyDeleteRepliesReplyUnknownFebruary2,2017at7:03PMIfthereallocandfreefunctionalsobeimplementedinit?ReplyDeleteRepliesAnonymousOctober25,2019at11:31PMIcouldbewrong(Ihaven'teventestedthecodeasis),butIthinkthiscouldworkasareallocfunction:```void*realloc(void*ptr,unsignedlongsize){void*newPtr=malloc(size);memcpy(ptr,newPtr,((structblock*)ptr)->size);free(ptr);returnnewPtr;}```ThefreefunctionisalreadypartofthearticleDeleteRepliesReplyHariOctober6,2021at10:37PMGoodPoint."curr=curr-next"shouldbeinelsepartoftheaboveif.DeleteRepliesReplyReplyUnknownJune12,2017at4:35AMgoodlogicReplyDeleteRepliesReplyUnknownDecember20,2017at8:56AMReallygoodpost;easytounderstandandwellwritten.Thanksalot!ReplyDeleteRepliesReplyJacobMay24,2018at9:13AMwell,thanksformakingchainedlistsathingthaticanexplainandutilise<3ReplyDeleteRepliesReplyAnandJune3,2018at6:32PMGreat,Ilikedsimpleidea.Ihaveonesuggestion.Inmarge(),ifthereare4consecutivefreeblocks,itwillstillresultin2consecutivefreeblocks.Iwouldmakemergerecursivetomakesureallconsecutiveblockshavebeenmerged.Ionlylookedatyourexplanationhere,sopardonmeifyouhavealreadydonethatin.c.ReplyDeleteRepliesAnonymousOctober25,2019at11:19PMIhaven'tlookedindetail,butitlookslikemergeiscalledeverytimeyoufreeablock.Sobasically:1.Youstartwithoneblock2.Youcallmalloc,creatinganotherblock(therearenow2blocks)3.Youcallfreeonyourblockonceyou'vefinishedwithit,mergingitbackintofreeList(thereisnowoneblockagain)Howevermanyblocksyoucreate,theywillallbemergedbackintofreeListwhentheyarefreed.DeleteRepliesReplyReplyAnonymousJune7,2018at2:28AMHiTharika,Thanksalotforpost.ReplyDeleteRepliesAnonymousJuly21,2018at5:37AMHi,Thanksforyourpost!Verynicelydoneandexplained.Justonecomment...Ithinkyouaremissingacontinueinyourmergefunction,insidetheifcondition,asyouwanttocontinueandmergealsothenextavailablefreeblock.Suchacasecanbepossibleifyoufreedablockwhichisinbetweentwootherfreeblocks(sonowyouhaveasequenceof3freeblockswhichyouwanttomergeintoone).DeleteRepliesReplyAnonymousMarch6,2019at12:42PMYesjustputthecurr=curr->nextinanelsestatementanditworksfine.YoushouldonlygotothenextblockifthecurrentblockandnextblockcannotbemergedDeleteRepliesReplyReplyAnonymousSeptember14,2018at9:26PMHello,thanksfortheexample.IfIwanttostoredanytypeofdataonanyblock,howcanIdothat?NicePost!!ReplyDeleteRepliesReplyLindaJanuary19,2019at7:26AMThanksforanawesometutorial.However,Isthisalgorithmbestfitorfirstfit,please?ReplyDeleteRepliesReplyAnonymousOctober8,2019at11:00PMIneedhelpwithunderstandingsplitfunctionplz,anyoneReplyDeleteRepliesReplyUnknownNovember29,2019at5:36PMthankyou&greatworkkeepitupReplyDeleteRepliesReplyMihirDeshpandeFebruary23,2020at9:41AMWhatdoes--currand++curractuallydo?ReplyDeleteRepliesReplyUnknownMay12,2020at6:37AMCharmemory[20000];Allocatesmemoryinstacknotinheap.ReplyDeleteRepliesAnonymousMay30,2020at11:44PM--currispredecrementoperation.iefirstdecrementthepointerandthendooperationofthataddresssimilarly++currispreincrement,iefirstincrementthepointerandthendotheoperationonthenewmemoryaddress.DeleteRepliesReplyReplyAnonymousMay30,2020at11:38PMgreatexplanation!onequeryinstructblock*new=(void*)((void*)fitting_slot+size+sizeof(structblock));shoulditnotbelikebelow:-fitting_slot++;structblock*new=(void*)((void*)fitting_slot+size+sizeof(structblock));ifstartwithoutincrementingfitting_slot,itwillresultinlessmemory.ReplyDeleteRepliesReplyAnonymousJuly18,2020at10:32PMExcellentpost.Inmerge,ifyouwanttokeepmergingmultiplefreeblocksstartingfromfreelist,weshouldnotmovecurrtocurr->next.Onlymovecurr->nexttocurr->next->nextandkeepupdatingcurr'sfreesize.ReplyDeleteRepliesReplyIonianNovember11,2020at8:47AMHi,wouldyoupleaseexplaineverylineofthesplit()function?Idon'tunderstandanyofit.Yousaid"new"pointstoablockofmemorywhichisequaltothe_size_of_the_metadata_block_we_considered+the_size_requested_to_be_allocated.Butinthecodetherearethreeoperands,namelyfitting_slot+size+sizeof(structblock),whereasinyourexplanationyouhaveonlytwooperands,namelyconsidered+requested?So,Iwouldappreciateifyouexplainthisandeveryotherlineinthesplit()function.Thanks.ReplyDeleteRepliesReplyAnonymousDecember23,2020at4:50AMHi,whyincrementcurrbeforeassigningittotheresult?I'mtalkingaboutthis.result=(void*)(++curr);ReplyDeleteRepliesAnandJuly12,2021at4:26AMHere,currispointingtometadata.Soweneedtoreturnpointernexttometadatabyte.DeleteRepliesReplyReplyPATRIKMarch14,2021at3:39AMAmazingexplanation.Thanksforsuchapost.Wasreallycurioushowwecandothatandthepostexplainedeverythingindetail.ReplyDeleteRepliesReplyUnknownNovember17,2021at10:35AMIthink"new->next=fitting_slot->next;"inthesplitfunctionshouldpointtotheheadofthenextmetaData,orifit'sattheendoftheHeapaddress,itshouldbeNULLReplyDeleteRepliesReplyUnknownNovember27,2021at9:29PMmergekeepsbreakingReplyDeleteRepliesReplyNirJanuary31,2022at8:01PMThanksforthepost.Anote->arithmetictoavoidpointerisillegal.ReplyDeleteRepliesReplyleocorOmyrr-geApril24,2022at1:51PMleocorOmyrr-geGinaSinclairhttps://wakelet.com/wake/TaBkIhvrhUu7EVxCEXD0LmusmanaceReplyDeleteRepliesReplyAnonymousJune23,2022at6:14PMGreatpost!justonechangeneeded-inhttp://tharikasblogs.blogspot.com/p/include-include-include-mymalloc.htmlreplacebelowint*p=(int)MyMalloc(100*sizeof(int));char*q=(char)MyMalloc(250*sizeof(char));int*r=(int)MyMalloc(1000*sizeof(int));char*w=(char)MyMalloc(700);withint*p=(int*)MyMalloc(100*sizeof(int));char*q=(char*)MyMalloc(250*sizeof(char));int*r=(int*)MyMalloc(1000*sizeof(int));char*w=(char*)MyMalloc(700);int*k=(int*)MyMalloc(500*sizeof(int)ReplyDeleteRepliesReplyAnonymousJune23,2022at6:41PMAlsoitwouldbegoodtoextendthisarticletodealwithlockstomanagethefreelistReplyDeleteRepliesReplyAddcommentLoadmore... PostaComment Popularpostsfromthisblog TheJAR/ZIPfile(...)seemscorrupted,error:zipfileisemptyduringmavenbuild Youcaneasilysolvethisproblemin2steps.Deletethefilegivenin(...)thispath,whichisgivenintheerrortrace.Buildtheprojectagainusingmvncleaninstall.Cheers! Share Getlink Facebook Twitter Pinterest Email OtherApps 5comments Readmore HowtoimportthePublicCertificateofoneWSO2producttothetruststoreofanother? Todemonstratethispoint,Iwillusethe2productsWSO2APIManager2.1.0(referredasAPIMfromhereonwards)andWSO2EnterpriseIntegrator6.1.1(referredasEIfromhereonwards).WhenusingEIastheBusinessProcessServerduringconfigurationofWorkflowsinAPIM,onesteptoperformistoimportthepubliccertificateofEItothetruststoreofAPIM[1].Sonowlet'sseehowthiscanbedone.Step1:Goto/repository/resources/security/folderandexecutethefollowingkeytoolcommand.ThiscommandisusedtoexportthepubliccertificateofEIasacertificatefilecalledwso2carbon.cer.SincethedefaultkeystoreinEIiswso2carbon.jks,wehavespecifieditasthekeystoreandthedefaultaliasiswso2carbon.Providewso2carbonasthekeystorepasswordwhenpromptedasitisthedefaultpassword.AfterexecutingtheabovecommandfromwithinthesecurityfolderinEI,youwillseethatafilewiththenameofwso2carbon.ceriscreated Share Getlink Facebook Twitter Pinterest Email OtherApps 3comments Readmore IntegratingtheJaCoCocodecoveragepluginintoaJavaMavenprojectforunittestingwithtestng I’llshowhowtodothisforbothofflineinstrumentationandforusingtheJaCoCoruntimeagent.Itisveryeasybecauseyoudon’tneedtochangetheusualwayofwritingyourtests.Itsonlyamatterofchangingthepom.xmlfileinyourmavenproject.1.JaCoCocodecoveragewithJaCoCoruntimeagentSinceweusetestngforunittestwriting,weputthefollowingdependencyunderdependencies.org.testngtestng${testng.version}testThenunderbuild,wefirstneedtohavetheJaCoCopluginputunderthepluginssectionofyourprojectpom.xml.(Note-thisistheparentpomwearereferringto)Thispluginconfiguration Share Getlink Facebook Twitter Pinterest Email OtherApps PostaComment Readmore AboutMe TharikaMadurapperuma Visitprofile Archive 2018 5 November 1 HowtolocallymergeanupstreampullrequestinG... April 3 March 1 2017 4 November 2 September 1 March 1 2016 15 November 5 October 1 September 1 June 1 May 1 April 6 2015 9 November 1 August 2 May 2 April 1 March 2 February 1 Showmore Showless ReportAbuse