c - How is malloc() implemented internally? - Stack Overflow

When one calls malloc , memory is taken from the large heap cell, which is returned by malloc . The rest is formed into a new heap cell that ... Resultsfromthe2022DeveloperSurveyarenowavailable Home Public Questions Tags Users Companies Collectives ExploreCollectives Teams StackOverflowforTeams –Startcollaboratingandsharingorganizationalknowledge. CreateafreeTeam WhyTeams? Teams CreatefreeTeam Collectives™onStackOverflow Findcentralized,trustedcontentandcollaboratearoundthetechnologiesyouusemost. Learnmore Teams Q&Aforwork Connectandshareknowledgewithinasinglelocationthatisstructuredandeasytosearch. Learnmore Howismalloc()implementedinternally?[duplicate] AskQuestion Asked 11years,10monthsago Modified 1year,9monthsago Viewed 151ktimes 124 94 Thisquestionalreadyhasanswershere: Howdomalloc()andfree()work? (13answers) Closed8yearsago. Cananyoneexplainhowmalloc()worksinternally? IhavesometimesdonestraceprogramandIseealotofsbrksystemcalls,doingmansbrktalksaboutitbeingusedinmalloc()butnotmuchmore. cmemorymallocsystem-callssbrk Share Improvethisquestion Follow editedAug19,2013at1:36 orlp 107k3333goldbadges201201silverbadges300300bronzebadges askedAug13,2010at17:35 bodacydobodacydo 70.2k8686goldbadges222222silverbadges313313bronzebadges 2 Ithinkthislinkanswersyourquestiontosomeextentstackoverflow.com/questions/1119134/how-malloc-and-free-work – Rishabh Aug13,2010at17:40 2 Usethesource,BodaCydo.ftp.gnu.org/gnu/glibc – msw Aug13,2010at17:46 Addacomment  |  3Answers 3 Sortedby: Resettodefault Highestscore(default) Trending(recentvotescountmore) Datemodified(newestfirst) Datecreated(oldestfirst) 116 Thesbrksystemcallmovesthe"border"ofthedatasegment.Thismeansitmovesaborderofanareainwhichaprogrammayread/writedata(lettingitgroworshrink,althoughAFAIKnomallocreallygivesmemorysegmentsbacktothekernelwiththatmethod).Asidefromthat,there'salsommapwhichisusedtomapfilesintomemorybutisalsousedtoallocatememory(ifyouneedtoallocatesharedmemory,mmapishowyoudoit). Soyouhavetwomethodsofgettingmorememoryfromthekernel:sbrkandmmap.Therearevariousstrategiesonhowtoorganizethememorythatyou'vegotfromthekernel. Onenaivewayistopartitionitintozones,oftencalled"buckets",whicharededicatedtocertainstructuresizes.Forexample,amallocimplementationcouldcreatebucketsfor16,64,256and1024bytestructures.Ifyouaskmalloctogiveyoumemoryofagivensizeitroundsthatnumberuptothenextbucketsizeandthengivesyouanelementfromthatbucket.Ifyouneedabiggerareamalloccouldusemmaptoallocatedirectlywiththekernel.Ifthebucketofacertainsizeisemptymalloccouldusesbrktogetmorespaceforanewbucket. Therearevariousmallocdesignsandthereispropablynoonetruewayofimplementingmallocasyouneedtomakeacompromisebetweenspeed,overheadandavoidingfragmentation/spaceeffectiveness.Forexample,ifabucketrunsoutofelementsanimplementationmightgetanelementfromabiggerbucket,splititupandaddittothebucketthatranoutofelements.Thiswouldbequitespaceefficientbutwouldnotbepossiblewitheverydesign.Ifyoujustgetanotherbucketviasbrk/mmapthatmightbefasterandeveneasier,butnotasspaceefficient.Also,thedesignmustofcoursetakeintoaccountthat"free"needstomakespaceavailabletomallocagainsomehow.Youdon'tjusthandoutmemorywithoutreusingit. Ifyou'reinterested,theOpenSER/KamailioSIPproxyhastwomallocimplementations(theyneedtheirownbecausetheymakeheavyuseofsharedmemoryandthesystemmallocdoesn'tsupportsharedmemory).See:https://github.com/OpenSIPS/opensips/tree/master/mem ThenyoucouldalsohavealookattheGNUlibcmallocimplementation,butthatoneisverycomplicated,IIRC. Share Improvethisanswer Follow editedJun11,2013at8:40 mmoya 1,73211goldbadge1818silverbadges3030bronzebadges answeredAug13,2010at17:58 DarkDustDarkDust 87.9k1919goldbadges183183silverbadges217217bronzebadges 2 11 IIRC=IfIRecallCorrectly – Gab是好人 Apr29,2017at20:16 16 是好人=isagoodman – TomDawn Jul9,2018at7:11 Addacomment  |  59 Simplisticallymallocandfreeworklikethis: mallocprovidesaccesstoaprocess'sheap.TheheapisaconstructintheCcorelibrary(commonlylibc)thatallowsobjectstoobtainexclusiveaccesstosomespaceontheprocess'sheap. Eachallocationontheheapiscalledaheapcell.Thistypicallyconsistsofaheaderthatholdinformationonthesizeofthecellaswellasapointertothenextheapcell.Thismakesaheapeffectivelyalinkedlist. Whenonestartsaprocess,theheapcontainsasinglecellthatcontainsalltheheapspaceassignedonstartup.Thiscellexistsontheheap'sfreelist. Whenonecallsmalloc,memoryistakenfromthelargeheapcell,whichisreturnedbymalloc.Therestisformedintoanewheapcellthatconsistsofalltherestofthememory. Whenonefreesmemory,theheapcellisaddedtotheendoftheheap'sfreelist.Subsequentmalloc'swalkthefreelistlookingforacellofsuitablesize. Ascanbeexpectedtheheapcangetfragmentedandtheheapmanagermayfromtimetotime,trytomergeadjacentheapcells. Whenthereisnomemoryleftonthefreelistforadesiredallocation,malloccallsbrkorsbrkwhicharethesystemcallsrequestingmorememorypagesfromtheoperatingsystem. Nowthereareafewmodificationtooptimizeheapoperations. Forlargememoryallocations (typically>512bytes,theheap managermaygostraighttotheOSand allocateafullmemorypage. Theheap mayspecifyaminimumsizeof allocationtopreventlargeamounts offragmentation. Theheapmayalsodivideitselfintobinsoneforsmallallocationsandoneforlargerallocationstomakelargerallocationsquicker. Therearealsoclevermechanismsforoptimizingmulti-threadedheapallocation. Share Improvethisanswer Follow editedSep21,2020at8:45 VishnuCS 74411goldbadge88silverbadges2323bronzebadges answeredAug13,2010at18:09 dorondoron 26.6k1111goldbadges6262silverbadges9999bronzebadges Addacomment  |  9 It'salsoimportanttorealizethatsimplymovingtheprogrambreakpointeraroundwithbrkandsbrkdoesn'tactuallyallocatethememory,itjustsetsuptheaddressspace.OnLinux,forexample,thememorywillbe"backed"byactualphysicalpageswhenthataddressrangeisaccessed,whichwillresultinapagefault,andwilleventuallyleadtothekernelcallingintothepageallocatortogetabackingpage. Share Improvethisanswer Follow answeredSep16,2013at21:09 mgalgsmgalgs 14.5k99goldbadges5959silverbadges6363bronzebadges 1 1 DependingontheOS,itcanactasasignaltoincreasethereserveofnulledpages,sothatwhenarequestcomes,itcanbequicklyfulfilled.Thatdoesleadtoincreasedmemoryusage.Firstorder,however,yourstatementistrue. – MarcovandeVoort Feb8,2019at9:24 Addacomment  |  Nottheansweryou'relookingfor?Browseotherquestionstaggedcmemorymallocsystem-callssbrkoraskyourownquestion. TheOverflowBlog Askedandanswered:theresultsforthe2022Developersurveyarehere! LivingontheEdgewithNetlify(Ep.456) FeaturedonMeta Testingnewtrafficmanagementtool AskWizardTestResultsandNextSteps Updatedbuttonstylingforvotearrows:currentlyinA/Btesting Trending:Anewanswersortingoption Linked 303 Howdomalloc()andfree()work? 0 aboutmalloccallocandrealloc 27 howdocompilersassignmemoryaddressestovariables? 7 Writingnew"malloc"and"free"functions 12 RuntimeMemoryallocationonstack 3 Howareweabletoaccessthepointerafterdeallocatingthememory? 9 Isthereacustommemoryallocatordesignpatternthatdoesnotstoremetadatainitsallocations? 1 Wheredoesmallocreturnmemory? 1 Understandingandimplementingmalloc 3 Isadatabasetransactionagoodwaytomanagememoryinanoperatingsystem? Seemorelinkedquestions Related 1277 HowdoIdeterminethesizeofmyarrayinC? 2971 Howdoyouset,clear,andtoggleasinglebit? 2676 DoIcasttheresultofmalloc? 614 WhatREALLYhappenswhenyoudon'tfreeaftermallocbeforeprogramtermination? 877 Differencebetweenmallocandcalloc? 3217 ImproveINSERT-per-secondperformanceofSQLite 3593 HowcanIcreateamemoryleakinJava? 5 Whymalloc(1)givesmorethanonepagesize? 1 multiplemalloccallsinternallycallingmmaponlyonce 2 Whymallocandsbrkreturnsaddressfromseperatesegments? HotNetworkQuestions CantheEnormousTentaclesee? Drawboxesaroundnodesintikz MedicineandStabilizing SolvingaSimple'SumandProduct'Problem WhatarethecorrectspecsforanSNESpowersupply? IterativeSmallestComplement Whatisthebestsolutiontoshowtheinvisibleareaofawindowwhenit'stoobig? Expectedvalueof100briefcaseseachwith1dollarexceptfor1thatresetsyouraccumulatedamounttozero? Willmymeatloafcookifthesauceismixedintothemeat SymmetricalChessPositionWithNoLegalMoves ShortofattackingaNATOcountry,isthereanyotherthingRussiacandototriggerdirectAmericanmilitaryconfrontation? Palindromeanimationpausingatbeginningandend Whydidn’tthe1980smicrosuseMC68010? Whatisthenameofthiscreature? IsDatafromStarTrekabletoswim? Canthisdoublebreakerbemoved? CorrelationBetweenVoicingandPlaceofArticulation? What'smakingthescenariocontradictorytoMaxwell'stheoryofemwaves? WhywouldanyonebuyaPonyoveraMule? 28yofriendlookingtoattenedundergraddegreewithouttransferringanycredits TCP-WhydoRSTpacketsnotrequireacknowledgements(andFINpacketsdo)? Uglyshadowglitch HowcanIremovemarkerswithnumbers2,5,7? InMagic,areyouallowedtorevealwhatcardsyouhavedraftedtostopothersfromdraftingthesamecolors? morehotquestions lang-c Yourprivacy Byclicking“Acceptallcookies”,youagreeStackExchangecanstorecookiesonyourdeviceanddiscloseinformationinaccordancewithourCookiePolicy. Acceptallcookies Customizesettings