Implementing Malloc: First-fit Free List - Embedded Artistry

Prerequisites. The only pre-requisite for the simple malloc implementation is a linked list library. While you can take the time to implement ... Skiptocontent 15February2017byPhillipJohnston•Lastupdated14March2022Nowthatwe’veseensomeusefulC++examplesthatcanbeappliedtoembeddedsystems,you’reprobablycuriousaboutgettingC++codeupandrunningonyourembeddedplatform. IfyoutrylinkingC++codeforyourplatform,youmightfindthatyouhavenumerousundefinedsymbolerrors.Unfortunately,C++runtimesarenotprovidedformanysystems.Howcanweutilizethesefeaturesifwedon’thaveoneoftheout-of-the-boxsupportedplatforms,orneedasmallerbaremetalimplementation? Thefirststeponourjourneyisanimplementationofmalloc.LikeC++,manyCfeaturesareprobablynotnativelysupportedonyourplatform! TableofContents: FreeListAllocator WhatMemoryDoIGiveIt? Prerequisites Implementation Storage AddingaBlockofMemory AllocatingMemory FreeingMemory CleaningUptheFreeList PuttingitAllTogether FurtherReading FreeListAllocator Let’sassumeyoudon’thaveanRTOSrunninganddon’thavemallocimplementedforyourplatform.Howcanyoudynamicallyallocatememory? Thesimplestallocatorwecanimplementisafirst-fitfree-list.Weinitializeourallocatorbydefininganaddressinmemoryandtheamountofspaceavailable.Theallocatorthenkeepsalinkedlistofavailablememory(free-list),givingoutthefirstblockofspacesufficienttocontaintherequestedsize(first-fit).Wecansplituplargeblocksintosmalleronesbeforevendingmemoryaddressestoutilizeourspacemoreeffectively. WhatmemorydoIgiveit? Whatsizeandaddressyouprovidetothemallocallocatoristotallyplatformandimplementationdependent.Doesyourchiphave128KBofSRAM?Maybeyoucanonlysetaside16KBfordynamicallocations.Doyouhave2GbofDDR?Setaside32MBattheendofDRAM! Forthepurposesofourexample,wewillsimplyrequestablockofmemoryfromthePC’simplementationofmallocandpassthatintotheallocator. Prerequisites Theonlypre-requisiteforthesimplemallocimplementationisalinkedlistlibrary.Whileyoucantakethetimetoimplementyourown,thereareplentyontheinternetthatcanbeutilized. Theexamplesherewillusethisdefinitionofadoubly-linkedlistnode: typedefstructll_head{ structll_head*next; structll_head*prev; }ll_t; Implementation Let’sdigintotheimplementationofourfree-listallocator. Storage First,weneedtoknowhowwe’regoingtokeeptrackofourfreelistandmemoryallocations.Weneedtoallocatespaceforthelinkedlistnodethatwillattachittothefreelist,andwedefinitelyneedtoknowthesizeofeachblock.Considerthisstructure: typedefstruct{ ll_tnode; size_tsize; char*block; }alloc_node_t; However,wedon’twanttheusertomanagethisinformation,sowewillonlyvendtheactualdatapointertotheconsumer.Thisisquiteeasyusingpointermath(oroffsetof&container_of).Aslongaswehavethedatapointer,wecanlookbackwardsinmemoryandgetthecontainingstructure. Forsimplification,we’lldefinethismacro: #defineALLOC_HEADER_SZoffsetof(alloc_node_t,block) AddingaBlockofMemory Nowthatweknowhowwe’regoingtokeeptrackofourdata,howdoweaddourblockofmemorytothefreelist? Wesimplytakethememoryweareprovided,initializeasinglefree-listblockmatchingourdata,andaddittothefree-listforlateruse.Easypeasy! voidmalloc_addblock(void*addr,size_tsize) { alloc_node_t*blk; //alignthestartaddrofourblocktothenextpointeralignedaddr blk=(void*)align_up((uintptr_t)addr,sizeof(void*)); //calculateactualsize-mgmtoverhead blk->size=(uintptr_t)addr+size-(uintptr_t)blk -ALLOC_HEADER_SZ; //andnowourgiantblockofmemoryisaddedtothelist! list_add(&blk->node,&free_list); } AllocatingMemory We’llusethemallocfunctionprototype: void*malloc(size_tsize) Whenmemoryisrequested,weneedtotrytofindablockinourfreelistofacceptablesize: void*ptr=NULL; alloc_node_t*blk=NULL; //trytofindabigenoughblocktoalloc list_for_each_entry(blk,&free_list,node) { if(blk->size>=size) { ptr=&blk->block; break; } } Ifwefoundablock(ptrisnotNULL),thenweshouldtrytosplitthatblockifwecan.Thiswillletuspreserveasmuchmemoryforlaterconsumersaspossible. //Canwesplittheblock? if((blk->size-size)>=MIN_ALLOC_SZ) { alloc_node_t*new_blk; new_blk=(alloc_node_t*)((uintptr_t)(&blk->block)+size); new_blk->size=blk->size-size-ALLOC_HEADER_SZ; blk->size=size; list_add(&new_blk->node,&blk->node,blk->node.next); } Inthisexample,Isubtracttherequestedsize(size)fromtheavailablesizeinthefreeblock(blk->size)andcheckwhethertheresultingvalueisaboveourminimumallocationthreshold(e.g.32bytes).Ifthatisnottrue,it’ssimplynotworththeoverheadofsplittingtheblocktokeepasmallnumberofavailablebytesaround. Eitherway,weneedtoremovethememorywe’reallocatingfromthefreelist: list_del(&blk->node); Nowwejustneedtoreturnourdatapointer(ptr)andwearedone! FreeingMemory Whenmemoryisreadytobefreed,weneedtoconvertfromthevendeddatapointertoourcontainerstructureandaddthenotebacktoourfreelist. Usingthestandardfreeprototype: voidfree(void*ptr) Weusecontainer_oftowalkbackwardsinmemoryfromptrtothecontainerstruct: alloc_node_t*blk,*free_blk; //wetakethepointerandusecontainer_oftogetthecorrespondingblock blk=container_of(ptr,alloc_node_t,block); Nowthatwehaveourblock,wecansearchthefree-listandputitbackatthecorrectlocation: //Let'sputitbackinthepropermemoryorder list_for_each_entry(free_blk,&free_list,node) { if(free_blk>blk) { list_add_(&blk->node,free_blk->node.prev,&free_blk->node); gotoblockadded;//breakout } } //ifwedidn'tbreak,addtotheendofthelist list_add_tail(&blk->node,&free_list); CleaningUptheFreeList Wecanreviewourfreelistandchecktoseeifanymemoryblockscanbecombinedintolargerblocks.Thishelpsusfightagainstmemoryfragmentationinasimpleway–wealwaystrytohavethelargestcontiguousfreeblockspossible. voiddefrag_free_list(void) { alloc_node_t*block,*last_block=NULL,*t; list_for_each_entry(block,t,&free_list,node) { if(last_block) { if((((uintptr_t)&last_block->block)+last_block->size) ==(uintptr_t)block) { last_block->size+=ALLOC_HEADER_SZ+block->size; list_del(&block->node); continue; } } last_block=block; } } Thesamplecodeprovideddoesthisoneveryiterationoffree().Weaddthistotheblockaddedlabelmentionedinfree(). blockadded: //Let'sseeifwecancombineanymemory defrag_free_list(); PuttingItAllTogether I’veaddedaCexamplesfoldertotheembedded-resourcesgitrepository. Inthatfolder,youcanfindalinkedlistexample,amallocfree-listexample,aswellassometestcodeshowingtheAPIusage. IhavealsoaddedaMakefileatthetopleveloftherepositoryandattheClevel.SimplyrunmakecatthetoplevelormakefreelistifyouareintheCexamplesfolder. FurtherReading ImplementingMallocwithThreadX ImplementingMallocwithFreeRTOS Wiki:FreeList AllocationTechniques OptimizingMallocandFree(Detailsonfreelists) ARMPointerAlignmentRequirements offsetof container_of Related 5Repliesto“ImplementingMalloc:First-fitFreeList” Wheredoeslbcomefrom? Reply lbissetduringthefirstiterationofthefor_eachloop.Sothefirsttimethrough,itwillnotbeset,sotheifstatementisskipped.Thenlbissettob,andduringtheseconditerationonwardlbwillbevalid. Ishouldrenametheexamplestobetterterms:). Reply Excellentexplanation!Thankyou! Reply Whatdoyoudosothatthelinkedlistdoesn’tgrowtoobig? Reply HiPeter, Whatdoyoudosothatthelinkedlistdoesn’tgrowtoobig? Canyousharesomemoredetailsaboutwhatyoumeanhere?Areyoulookingtolimitlisttraversaltimes? Reply ShareYourThoughts Cancelreply ThissiteusesAkismettoreducespam.Learnhowyourcommentdataisprocessed. Postnavigation PreviousPostPreviousTheMythicalManMonthNextPostNextImplementingMallocwithThreadX Searchfor: Search SomethingtoPonder FreeNewsletter Signupandreceiveourfreeplaybookforwritingportableembeddedsoftware. FeaturedCourses DesigningEmbeddedSoftwareforChange 59Lessons HeaplessC++ 27Lessons CreatingaCross-PlatformBuildSystemforEmbeddedProjectswithCMake 88Lessons