Implementing malloc and free - Medium

The following code is the malloc function implementation. Our implementation keeps a doubly linked listed of free memory blocks and every time ... GetunlimitedaccessOpeninappHomeNotificationsListsStoriesWriteImplementingmallocandfreeChapter7of“TheLinuxProgrammingInterface”isaboutmemoryallocation.Oneoftheexercises,markedasadvanced,asksthereadertoimplementmalloc.I’vedecidedtogiveitashot.MyfullimplementationisavailableonGithub;Iwilltrytobreakdownsomeofmyreasoningonthenextsectionsandincludesomesnippetsfromthecode.MemorylayoutofaProcessThememoryallocatedtoeachprocessiscomposedofmultiplesegments,ascanbeseenonthefollowingimage:Source:https://github.com/shichao-an/notes/blob/master/docs/tlpi/figure_6-1.pngWeareparticularlyinterestedontheheap(alsoknownasthedatasegment),anareafromwhichmemorycanbedynamicallyallocatedatruntime.Thetopendoftheheapiscalledtheprogrambreak.AdjustingtheprogrambreakWecanmovetheprogrambreakonourCprogrambyusingsbrk()andbrk().intbrk(void*addr);void*sbrk(intptr_tincrement);Thefirst,movestheprogrambreaktotheaddresspointedbyaddr,whilethelatterincrementstheprogrambreakbyincrementbytes.TheirmanpagescangivemoreinformationabouttheirimplementationonLinuxandothersystems,butthosearethebasicbuildingblocksthatourmallocimplementationwillrelyon.OnLinux,sbrkreliesonbrk.TheimplementationTheentirecodefortheimplementationisavailableatgithub.Bewarethatthisimplementationisfullofbugs(somearediscussedbelow,someareobviousfromreadingtherealmallocimplementation).Thefollowingcodeisthemallocfunctionimplementation.Ourimplementationkeepsadoublylinkedlistedoffreememoryblocksandeverytime_mallocgetscalled,wetraversethelinkedlistlookingforablockwithatleastthesizerequestedbytheuser(lines8–25).Ifablockwiththeexactrequestedsizeexists,weremoveitfromthelistandreturnitsaddresstotheuser(lines11–16);iftheblockislarger,wesplititintotwoblocks,returntheonewiththerequestedsizetotheuserandaddsthenewlycreatedblocktothelist(lines19–21).Ifweareunabletofindablockonthelist,wemust“ask”theOSformorememory,byusingthesbrkfunction(lines31–35).Toreducethenumberofcallstosbrk,weallocafixednumberofbytesthatisamultipleofthememorypagesize,definedas:#defineALLOC_UNIT3*sysconf(_SC_PAGESIZE)Afterthecalltosbrk(whereourprogrambreakchangesvalue)wecreateanewblockwiththeallocatedsize.Themetadataonthisblockcontainsthesize,nextandpreviousblocksandisallocatedonthefirst24bytesoftheblock(thisisouroverhead)(lines36–38).Sincewemayhaveallocatedmuchmorememorythentheuserrequested,wesplitthisnewblockandreturntheonewiththeexactsamesizeasrequested(lines39–43).TheBLOCK_MEMmacro,definedas:#defineBLOCK_MEM(ptr)((void*)((unsignedlong)ptr+sizeof(block_t)))returnsskipsthemetadataatgivenptrandreturnstheaddressofthememoryareathatisavailablefortheuser.The_freefunctionisquitestraightforward,givenapointerthatwaspreviously“malloced”totheuser,wemustfinditsmetadata(byusingtheBLOCK_HEADERmacro)andaddittoourfreelinkedlist.Afterthat,thefunctionscan_merge()iscalledtodosomecleaning:scan_merge()firsttraversesthelinkedlistlookingforcontinuousblocks(twodifferentmemoryblocksthatarefreeandcorrespondtocontinuousaddresses).Wekeeptheblockssortedbyaddresstomakethisstepeasier.Foreverytwocontinuousblocksfound,wemergebothblockstoreduceourtotaloverhead(lessmetadatatokeep)(lines18–33).Afterfindingthelastblockonourfreelist,wecheckifthisblocksendsontheprogrambreak(line39).Ifthatistrue,andtheblockisbigenough(where“big”isdefinedasMIN_DEALLOC,alsoamultipleofthepagesize),weremovetheblockfromourlistandmovetheprogrambreaktothebeginningoftheblock,bycallingbrk.Howismallocactuallyimplemented?Beforedivingintotherealmalloccode,Idecidedtowriteasimpletestprogramandtraceit’sexecutionusingstrace.Iusedthefollowingcode:Idecidedtotracetheexecutingtestingdifferentsizes.$strace./malloc1...brk(NULL)=0x5585209f2000brk(0x558520a13000)=0x558520a13000exit_group(0)=?+++exitedwith0+++$strace./malloc100000...brk(NULL)=0x55b45a386000brk(0x55b45a3bf000)=0x55b45a3bf000exit_group(0)=?$strace./malloc1000000...mmap(NULL,1003520,PROT_READ|PROT_WRITE,MAP_PRIVATE|MAP_ANONYMOUS,-1,0)=0x7f05f7cbf000exit_group(0)=?ThefirstthingInoticedbetweenexecutionsisthatwhenaskingforalargesize,mallocactuallyusedmmapinsteadofbrktoallocatethememory.Iwasn’tsurewhy,sinceIhaveyettostudymmap.Butcheckingthecodeforglibc’smallocI’vefoundaprettynicewriteupmadebytheauthorsexplainingtheirimplementation.Ihighlyrecommendreadingit.Regardingtheuseofmmap,fromthesourcecodecomments:Thisbackupstrategygenerallyappliesonlywhensystemshave"holes"inaddressspace,sosbrkcannotperformcontiguousexpansion,butthereisstillspaceavailableonsystem.Onsystemsforwhichthisisknowntobeuseful(i.e.mostlinuxkernels),thisoccursonlywhenprogramsallocatehugeamountsofmemory.Betweenthis,andthefactthatmmapregionstendtobelimited,thesizeshouldbelarge,toavoidtoomanymmapcallsandthusavoidrunningoutofkernelresources.Thedocumentationalsoexplainstheirdesigngoals,motivations,howtheblocksareorganized(byusingbinsforthedifferentsizes,insteadofkeepingalinkedlistsortedbyaddress,asIdid)andlotsofotherdetails.Ilearnedalotreadingit.Addingacalltofreeonmytestprogramdoesnotchangethesyscallsmadebyat,asthememoryisnotreleasedtotheOS(somepeoplerelyonthisbehavior“mallocing”alargechunkofmemoryandfreeingitonthestartofaprogramtoreservethememory).OnecancontrolthisbehaviorbydefiningM_TRIM_THREASHOLD:M_TRIM_THRESHOLDisthemaximumamountofunusedtop-mostmemorytokeepbeforereleasingviamalloc_triminfree().Automatictrimmingismainlyusefulinlong-livedprograms.Becausetrimmingviasbrkcanbeslowonsomesystems,andcansometimesbewasteful(incaseswhereprogramsimmediatelyafterwardallocatemorelargechunks)thevalueshouldbehighenoughsothatyouroverallsystemperformancewouldimprovebyreleasingthismuchmemory.ThisblogpostispartofaseriesofpoststhatIintenttowritewhilereading“TheLinuxProgrammingInterface”tomakesureI’mactuallylearningsomething,asawaytopracticeandtoshareknowledge.--3MorefromAndréCarvalhoFollowLovepodcastsoraudiobooks?Learnonthegowithournewapp.TryKnowableRecommendedfromMediumJaredPetersenHowtoSetupaHomeSecurityLiveStreamingCamerawithRaspberryPiSimonMcCabeTechnologyisDelivering…..AreYou?SwipeiXUsingaCloudFrontAPIProxytoInvalidateaSingle-PageApplicationWithoutPollingmohandamezianemessaouiGettingstartedwithapachespark(PART2)“RealtimeprocessingdatawithSparkStreamingand…NoahEvansDownload2020AppleEventsinfull4KKonstantinosPatronasinBetterProgrammingPandas:HowtoProcessaDataframeinParallelGaylordAulkeRancheronHetznerElleHallalWeek2 — TestDrivenDevelopmentinRubyAboutHelpTermsPrivacyGettheMediumappGetstartedAndréCarvalho146FollowersFollowMorefromMediumSatriaJanakaHowtoinstallRubywithrbenvinWindows11WSL-Ubuntu20.04distroLeandroOliveirainJavaScriptinPlainEnglishHowtoUpgradeYourTerminalwithOhMyZshandMoreTechyedC++Project :AsimpleApplicationinWxWidgetsUniversityofGamesWhycleancodeisimportant?HelpStatusWritersBlogCareersPrivacyTermsAboutKnowable