Something went wrong. Try again.
(I'm so sorry!) Linux kernel mirror (for testing) git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git
kernel os linux
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845184618471848184918501851185218531854185518561857185818591860186118621863186418651866186718681869187018711872187318741875187618771878187918801881188218831884188518861887188818891890189118921893189418951896189718981899190019011902190319041905190619071908190919101911191219131914191519161917191819191920192119221923192419251926192719281929193019311932193319341935193619371938193919401941194219431944194519461947194819491950195119521953195419551956195719581959196019611962196319641965196619671968196919701971197219731974197519761977197819791980198119821983198419851986198719881989199019911992199319941995199619971998199920002001200220032004200520062007200820092010201120122013201420152016201720182019202020212022202320242025202620272028202920302031203220332034203520362037203820392040204120422043204420452046204720482049205020512052205320542055205620572058205920602061206220632064206520662067206820692070207120722073207420752076207720782079208020812082208320842085208620872088208920902091209220932094209520962097209820992100210121022103210421052106210721082109211021112112211321142115211621172118211921202121212221232124212521262127212821292130213121322133213421352136213721382139214021412142214321442145214621472148214921502151215221532154215521562157215821592160216121622163216421652166216721682169217021712172217321742175217621772178217921802181218221832184218521862187218821892190219121922193219421952196219721982199220022012202220322042205220622072208220922102211221222132214221522162217221822192220222122222223222422252226222722282229223022312232223322342235223622372238223922402241224222432244224522462247224822492250225122522253225422552256225722582259226022612262226322642265226622672268226922702271227222732274227522762277227822792280228122822283228422852286228722882289229022912292229322942295229622972298229923002301230223032304230523062307230823092310231123122313231423152316231723182319232023212322232323242325232623272328232923302331233223332334233523362337233823392340234123422343234423452346234723482349235023512352235323542355235623572358235923602361236223632364236523662367236823692370237123722373237423752376237723782379238023812382238323842385238623872388238923902391239223932394239523962397239823992400240124022403240424052406240724082409241024112412241324142415241624172418241924202421242224232424242524262427242824292430243124322433243424352436243724382439244024412442244324442445244624472448244924502451245224532454245524562457245824592460246124622463246424652466246724682469247024712472247324742475247624772478247924802481248224832484248524862487248824892490249124922493249424952496249724982499250025012502250325042505250625072508250925102511251225132514251525162517251825192520252125222523252425252526252725282529253025312532253325342535253625372538253925402541254225432544254525462547254825492550255125522553255425552556255725582559256025612562256325642565256625672568256925702571257225732574257525762577257825792580258125822583258425852586258725882589259025912592259325942595259625972598259926002601260226032604260526062607260826092610261126122613261426152616261726182619262026212622262326242625262626272628262926302631263226332634263526362637263826392640264126422643264426452646264726482649265026512652265326542655265626572658265926602661266226632664266526662667266826692670267126722673267426752676267726782679268026812682268326842685268626872688268926902691269226932694269526962697269826992700270127022703270427052706270727082709271027112712271327142715271627172718271927202721272227232724272527262727272827292730273127322733273427352736273727382739274027412742274327442745274627472748274927502751275227532754275527562757275827592760276127622763276427652766276727682769277027712772277327742775277627772778277927802781278227832784278527862787278827892790279127922793279427952796279727982799280028012802280328042805280628072808280928102811281228132814281528162817281828192820282128222823282428252826282728282829283028312832283328342835283628372838283928402841284228432844284528462847284828492850285128522853285428552856285728582859286028612862286328642865286628672868286928702871287228732874287528762877287828792880288128822883288428852886288728882889289028912892289328942895289628972898289929002901290229032904290529062907290829092910291129122913291429152916291729182919292029212922292329242925292629272928292929302931293229332934293529362937293829392940294129422943294429452946294729482949295029512952295329542955295629572958295929602961296229632964296529662967296829692970297129722973297429752976297729782979298029812982298329842985298629872988298929902991299229932994299529962997299829993000300130023003300430053006300730083009301030113012301330143015301630173018301930203021302230233024302530263027302830293030303130323033303430353036303730383039304030413042304330443045304630473048304930503051305230533054305530563057305830593060306130623063306430653066306730683069307030713072307330743075307630773078307930803081308230833084308530863087308830893090309130923093309430953096309730983099310031013102310331043105310631073108310931103111311231133114311531163117311831193120312131223123312431253126312731283129313031313132313331343135313631373138313931403141314231433144314531463147314831493150315131523153315431553156315731583159316031613162316331643165316631673168316931703171317231733174317531763177317831793180318131823183318431853186318731883189319031913192319331943195319631973198319932003201320232033204320532063207320832093210321132123213321432153216321732183219322032213222322332243225322632273228322932303231323232333234323532363237323832393240324132423243324432453246324732483249325032513252325332543255325632573258325932603261326232633264326532663267326832693270327132723273327432753276327732783279328032813282328332843285328632873288328932903291329232933294329532963297329832993300330133023303330433053306330733083309331033113312331333143315331633173318331933203321332233233324332533263327332833293330333133323333333433353336333733383339334033413342334333443345334633473348334933503351335233533354335533563357335833593360336133623363336433653366336733683369337033713372337333743375337633773378337933803381338233833384338533863387338833893390339133923393339433953396339733983399340034013402340334043405340634073408340934103411341234133414341534163417341834193420342134223423342434253426342734283429343034313432343334343435343634373438343934403441344234433444344534463447344834493450345134523453345434553456345734583459346034613462346334643465346634673468346934703471347234733474347534763477347834793480348134823483348434853486348734883489349034913492349334943495349634973498349935003501350235033504350535063507350835093510351135123513351435153516351735183519352035213522352335243525352635273528352935303531353235333534353535363537353835393540354135423543354435453546354735483549355035513552355335543555355635573558355935603561356235633564356535663567356835693570357135723573357435753576357735783579358035813582358335843585358635873588358935903591359235933594359535963597359835993600360136023603360436053606360736083609361036113612361336143615361636173618361936203621362236233624362536263627362836293630363136323633363436353636363736383639364036413642364336443645364636473648364936503651365236533654365536563657365836593660366136623663366436653666366736683669367036713672367336743675367636773678367936803681368236833684368536863687368836893690369136923693369436953696369736983699370037013702370337043705370637073708370937103711371237133714371537163717371837193720372137223723372437253726372737283729373037313732373337343735373637373738373937403741374237433744374537463747374837493750375137523753375437553756375737583759376037613762376337643765376637673768376937703771377237733774377537763777377837793780378137823783378437853786378737883789379037913792379337943795379637973798379938003801380238033804380538063807380838093810381138123813381438153816381738183819382038213822382338243825382638273828382938303831383238333834383538363837383838393840384138423843384438453846384738483849385038513852385338543855385638573858385938603861386238633864386538663867386838693870387138723873387438753876387738783879388038813882388338843885388638873888388938903891389238933894389538963897389838993900390139023903390439053906390739083909391039113912391339143915391639173918391939203921392239233924392539263927392839293930393139323933393439353936393739383939394039413942394339443945394639473948394939503951395239533954395539563957395839593960396139623963396439653966396739683969397039713972397339743975397639773978397939803981398239833984398539863987398839893990399139923993399439953996399739983999400040014002400340044005400640074008400940104011401240134014401540164017401840194020402140224023402440254026402740284029403040314032403340344035403640374038403940404041404240434044404540464047404840494050405140524053405440554056405740584059406040614062406340644065406640674068406940704071407240734074407540764077407840794080408140824083408440854086408740884089409040914092409340944095409640974098409941004101410241034104410541064107410841094110411141124113411441154116411741184119412041214122412341244125412641274128412941304131413241334134413541364137413841394140414141424143414441454146414741484149415041514152415341544155415641574158415941604161416241634164416541664167416841694170417141724173417441754176417741784179418041814182418341844185418641874188418941904191419241934194419541964197419841994200420142024203420442054206420742084209421042114212421342144215421642174218421942204221422242234224422542264227422842294230423142324233423442354236423742384239424042414242424342444245424642474248424942504251425242534254425542564257425842594260426142624263426442654266426742684269427042714272427342744275427642774278427942804281428242834284428542864287428842894290429142924293429442954296429742984299430043014302430343044305430643074308430943104311431243134314431543164317431843194320432143224323432443254326432743284329433043314332433343344335433643374338433943404341434243434344434543464347434843494350435143524353435443554356435743584359436043614362436343644365436643674368436943704371437243734374437543764377437843794380438143824383438443854386438743884389439043914392439343944395439643974398439944004401440244034404440544064407440844094410441144124413441444154416441744184419442044214422442344244425442644274428442944304431443244334434443544364437443844394440444144424443444444454446444744484449445044514452445344544455445644574458445944604461446244634464446544664467446844694470447144724473447444754476447744784479448044814482448344844485448644874488448944904491449244934494449544964497449844994500450145024503450445054506450745084509451045114512451345144515451645174518451945204521452245234524452545264527452845294530453145324533453445354536453745384539454045414542454345444545454645474548454945504551455245534554455545564557455845594560456145624563456445654566456745684569457045714572457345744575457645774578457945804581458245834584458545864587458845894590459145924593459445954596459745984599460046014602460346044605460646074608460946104611461246134614461546164617461846194620462146224623462446254626462746284629463046314632463346344635463646374638463946404641464246434644464546464647464846494650465146524653465446554656465746584659466046614662466346644665466646674668466946704671467246734674467546764677467846794680468146824683468446854686468746884689469046914692469346944695469646974698469947004701470247034704470547064707470847094710471147124713471447154716471747184719472047214722472347244725472647274728472947304731473247334734473547364737473847394740474147424743474447454746474747484749475047514752475347544755475647574758475947604761476247634764476547664767476847694770477147724773477447754776477747784779478047814782478347844785478647874788478947904791479247934794479547964797479847994800480148024803480448054806480748084809481048114812481348144815481648174818481948204821482248234824482548264827482848294830483148324833483448354836483748384839484048414842484348444845484648474848484948504851485248534854485548564857485848594860486148624863486448654866486748684869487048714872487348744875487648774878487948804881488248834884488548864887488848894890489148924893489448954896489748984899490049014902490349044905490649074908490949104911491249134914491549164917491849194920492149224923492449254926492749284929493049314932493349344935493649374938493949404941494249434944494549464947494849494950495149524953495449554956495749584959496049614962496349644965496649674968496949704971497249734974497549764977497849794980498149824983498449854986498749884989499049914992499349944995499649974998499950005001500250035004500550065007500850095010501150125013501450155016501750185019502050215022502350245025502650275028502950305031503250335034503550365037503850395040504150425043504450455046504750485049505050515052505350545055505650575058505950605061506250635064506550665067506850695070507150725073507450755076507750785079508050815082508350845085508650875088508950905091509250935094509550965097509850995100510151025103510451055106510751085109511051115112511351145115511651175118511951205121512251235124512551265127512851295130513151325133513451355136513751385139514051415142514351445145514651475148514951505151515251535154515551565157515851595160516151625163516451655166516751685169517051715172517351745175517651775178517951805181518251835184518551865187518851895190519151925193519451955196519751985199520052015202520352045205520652075208520952105211521252135214521552165217521852195220522152225223522452255226522752285229523052315232523352345235523652375238523952405241524252435244524552465247524852495250525152525253525452555256525752585259526052615262526352645265526652675268526952705271527252735274527552765277527852795280528152825283528452855286528752885289529052915292529352945295529652975298529953005301530253035304530553065307530853095310531153125313531453155316531753185319532053215322532353245325532653275328532953305331533253335334533553365337533853395340534153425343534453455346534753485349535053515352535353545355535653575358535953605361536253635364536553665367536853695370537153725373537453755376537753785379538053815382538353845385538653875388538953905391539253935394539553965397539853995400540154025403540454055406540754085409541054115412541354145415541654175418541954205421542254235424542554265427542854295430543154325433543454355436543754385439544054415442544354445445544654475448544954505451545254535454545554565457545854595460546154625463546454655466546754685469547054715472547354745475547654775478547954805481548254835484548554865487548854895490549154925493549454955496549754985499550055015502550355045505550655075508550955105511551255135514551555165517551855195520552155225523552455255526552755285529553055315532553355345535553655375538553955405541554255435544554555465547554855495550555155525553555455555556555755585559556055615562556355645565556655675568556955705571557255735574557555765577557855795580558155825583558455855586558755885589559055915592559355945595559655975598559956005601560256035604560556065607560856095610561156125613561456155616561756185619562056215622562356245625562656275628562956305631563256335634563556365637563856395640564156425643564456455646564756485649565056515652565356545655565656575658565956605661566256635664566556665667566856695670567156725673567456755676567756785679568056815682568356845685568656875688568956905691569256935694569556965697569856995700570157025703570457055706570757085709571057115712571357145715571657175718571957205721572257235724572557265727572857295730573157325733573457355736573757385739574057415742574357445745574657475748574957505751575257535754575557565757575857595760576157625763576457655766576757685769577057715772577357745775577657775778577957805781578257835784578557865787578857895790579157925793579457955796579757985799580058015802580358045805580658075808580958105811581258135814581558165817581858195820582158225823582458255826582758285829583058315832583358345835583658375838583958405841584258435844584558465847584858495850585158525853585458555856585758585859586058615862586358645865586658675868586958705871587258735874587558765877587858795880588158825883588458855886588758885889589058915892589358945895589658975898589959005901590259035904590559065907590859095910591159125913591459155916591759185919592059215922592359245925592659275928592959305931593259335934593559365937593859395940594159425943594459455946594759485949595059515952595359545955595659575958595959605961596259635964596559665967596859695970597159725973597459755976597759785979598059815982598359845985598659875988598959905991599259935994599559965997599859996000600160026003600460056006600760086009601060116012601360146015601660176018601960206021602260236024602560266027602860296030603160326033603460356036603760386039604060416042604360446045604660476048604960506051605260536054605560566057605860596060606160626063606460656066606760686069607060716072607360746075607660776078607960806081608260836084608560866087608860896090609160926093609460956096609760986099610061016102610361046105610661076108610961106111611261136114611561166117611861196120612161226123612461256126612761286129613061316132613361346135613661376138613961406141614261436144614561466147614861496150615161526153615461556156615761586159616061616162616361646165616661676168616961706171617261736174617561766177617861796180618161826183618461856186618761886189619061916192619361946195619661976198619962006201620262036204620562066207620862096210621162126213621462156216621762186219622062216222622362246225622662276228622962306231623262336234623562366237623862396240624162426243624462456246624762486249625062516252625362546255625662576258625962606261626262636264626562666267626862696270627162726273627462756276627762786279628062816282628362846285628662876288628962906291629262936294629562966297629862996300630163026303630463056306630763086309631063116312631363146315631663176318631963206321632263236324632563266327632863296330633163326333633463356336633763386339634063416342634363446345634663476348634963506351635263536354635563566357635863596360636163626363636463656366636763686369637063716372637363746375637663776378637963806381638263836384638563866387638863896390639163926393639463956396639763986399640064016402640364046405640664076408640964106411641264136414641564166417641864196420642164226423642464256426642764286429643064316432643364346435643664376438643964406441644264436444644564466447644864496450645164526453645464556456645764586459646064616462646364646465646664676468646964706471647264736474647564766477647864796480648164826483648464856486648764886489649064916492649364946495649664976498649965006501650265036504650565066507650865096510651165126513651465156516651765186519652065216522652365246525652665276528652965306531653265336534653565366537653865396540654165426543654465456546654765486549655065516552655365546555655665576558655965606561656265636564656565666567656865696570657165726573657465756576657765786579658065816582658365846585658665876588658965906591659265936594659565966597659865996600660166026603660466056606660766086609661066116612661366146615661666176618661966206621662266236624662566266627662866296630663166326633663466356636663766386639664066416642664366446645664666476648664966506651665266536654665566566657665866596660666166626663666466656666666766686669667066716672667366746675667666776678667966806681668266836684668566866687668866896690669166926693669466956696669766986699670067016702670367046705670667076708670967106711671267136714671567166717671867196720672167226723672467256726672767286729673067316732673367346735673667376738673967406741674267436744674567466747674867496750675167526753675467556756675767586759676067616762676367646765676667676768676967706771677267736774677567766777677867796780678167826783678467856786678767886789679067916792679367946795679667976798679968006801680268036804680568066807680868096810681168126813681468156816681768186819682068216822682368246825682668276828682968306831683268336834683568366837683868396840684168426843684468456846684768486849685068516852685368546855685668576858685968606861686268636864686568666867686868696870687168726873687468756876687768786879688068816882688368846885688668876888688968906891689268936894689568966897689868996900690169026903690469056906690769086909691069116912691369146915691669176918691969206921692269236924692569266927692869296930693169326933693469356936693769386939694069416942694369446945694669476948694969506951695269536954695569566957695869596960696169626963696469656966696769686969697069716972697369746975697669776978697969806981698269836984698569866987698869896990699169926993699469956996699769986999700070017002700370047005700670077008700970107011701270137014701570167017701870197020702170227023702470257026702770287029703070317032703370347035703670377038703970407041704270437044704570467047704870497050705170527053705470557056705770587059706070617062706370647065706670677068706970707071707270737074707570767077707870797080708170827083708470857086708770887089709070917092709370947095709670977098709971007101710271037104710571067107710871097110711171127113711471157116711771187119712071217122712371247125712671277128712971307131713271337134713571367137713871397140714171427143714471457146714771487149715071517152715371547155715671577158715971607161716271637164// SPDX-License-Identifier: GPL-2.0+/* * Maple Tree implementation * Copyright (c) 2018-2022 Oracle Corporation * Authors: Liam R. Howlett <liam@infradead.org> * Matthew Wilcox <willy@infradead.org> * Copyright (c) 2023 ByteDance * Author: Peng Zhang <zhangpeng.00@bytedance.com> */
/* * DOC: Interesting implementation details of the Maple Tree * * Each node type has a number of slots for entries and a number of slots for * pivots. In the case of dense nodes, the pivots are implied by the position * and are simply the slot index + the minimum of the node. * * In regular B-Tree terms, pivots are called keys. The term pivot is used to * indicate that the tree is specifying ranges. Pivots may appear in the * subtree with an entry attached to the value whereas keys are unique to a * specific position of a B-tree. Pivot values are inclusive of the slot with * the same index. * * * The following illustrates the layout of a range64 nodes slots and pivots. * * * Slots -> | 0 | 1 | 2 | ... | 12 | 13 | 14 | 15 | * ┬ ┬ ┬ ┬ ┬ ┬ ┬ ┬ ┬ * │ │ │ │ │ │ │ │ └─ Implied maximum * │ │ │ │ │ │ │ └─ Pivot 14 * │ │ │ │ │ │ └─ Pivot 13 * │ │ │ │ │ └─ Pivot 12 * │ │ │ │ └─ Pivot 11 * │ │ │ └─ Pivot 2 * │ │ └─ Pivot 1 * │ └─ Pivot 0 * └─ Implied minimum * * Slot contents: * Internal (non-leaf) nodes contain pointers to other nodes. * Leaf nodes contain entries. * * The location of interest is often referred to as an offset. All offsets have * a slot, but the last offset has an implied pivot from the node above (or * UINT_MAX for the root node. * * Ranges complicate certain write activities. When modifying any of * the B-tree variants, it is known that one entry will either be added or * deleted. When modifying the Maple Tree, one store operation may overwrite * the entire data set, or one half of the tree, or the middle half of the tree. * */
#include <linux/maple_tree.h>#include <linux/xarray.h>#include <linux/types.h>#include <linux/export.h>#include <linux/slab.h>#include <linux/limits.h>#include <asm/barrier.h>
#define CREATE_TRACE_POINTS#include <trace/events/maple_tree.h>
#define TP_FCT tracepoint_string(__func__)
/* * Kernel pointer hashing renders much of the maple tree dump useless as tagged * pointers get hashed to arbitrary values. * * If CONFIG_DEBUG_VM_MAPLE_TREE is set we are in a debug mode where it is * permissible to bypass this. Otherwise remain cautious and retain the hashing. * * Userland doesn't know about %px so also use %p there. */#if defined(__KERNEL__) && defined(CONFIG_DEBUG_VM_MAPLE_TREE)#define PTR_FMT "%px"#else#define PTR_FMT "%p"#endif
#define MA_ROOT_PARENT 1
/* * Maple state flags * * MA_STATE_PREALLOC - Preallocated nodes, WARN_ON allocation */#define MA_STATE_PREALLOC 1
#define ma_parent_ptr(x) ((struct maple_pnode *)(x))#define mas_tree_parent(x) ((unsigned long)(x->tree) | MA_ROOT_PARENT)#define ma_mnode_ptr(x) ((struct maple_node *)(x))#define ma_enode_ptr(x) ((struct maple_enode *)(x))static struct kmem_cache *maple_node_cache;
#ifdef CONFIG_DEBUG_MAPLE_TREEstatic const unsigned long mt_max[] = { [maple_dense] = MAPLE_NODE_SLOTS, [maple_leaf_64] = ULONG_MAX, [maple_range_64] = ULONG_MAX, [maple_arange_64] = ULONG_MAX, [maple_copy] = ULONG_MAX,};#define mt_node_max(x) mt_max[mte_node_type(x)]#endif
static const unsigned char mt_slots[] = { [maple_dense] = MAPLE_NODE_SLOTS, [maple_leaf_64] = MAPLE_RANGE64_SLOTS, [maple_range_64] = MAPLE_RANGE64_SLOTS, [maple_arange_64] = MAPLE_ARANGE64_SLOTS, [maple_copy] = 3,};#define mt_slot_count(x) mt_slots[mte_node_type(x)]
static const unsigned char mt_pivots[] = { [maple_dense] = 0, [maple_leaf_64] = MAPLE_RANGE64_SLOTS - 1, [maple_range_64] = MAPLE_RANGE64_SLOTS - 1, [maple_arange_64] = MAPLE_ARANGE64_SLOTS - 1, [maple_copy] = 3,};#define mt_pivot_count(x) mt_pivots[mte_node_type(x)]
static const unsigned char mt_min_slots[] = { [maple_dense] = MAPLE_NODE_SLOTS / 2, [maple_leaf_64] = (MAPLE_RANGE64_SLOTS / 2) - 2, [maple_range_64] = (MAPLE_RANGE64_SLOTS / 2) - 2, [maple_arange_64] = (MAPLE_ARANGE64_SLOTS / 2) - 1, [maple_copy] = 1, /* Should never be used */};#define mt_min_slot_count(x) mt_min_slots[mte_node_type(x)]
/* Functions */static inline struct maple_node *mt_alloc_one(gfp_t gfp){ return kmem_cache_alloc(maple_node_cache, gfp);}
static inline void mt_free_bulk(size_t size, void __rcu **nodes){ kmem_cache_free_bulk(maple_node_cache, size, (void **)nodes);}
static void mt_return_sheaf(struct slab_sheaf *sheaf){ kmem_cache_return_sheaf(maple_node_cache, GFP_NOWAIT, sheaf);}
static struct slab_sheaf *mt_get_sheaf(gfp_t gfp, int count){ return kmem_cache_prefill_sheaf(maple_node_cache, gfp, count);}
static int mt_refill_sheaf(gfp_t gfp, struct slab_sheaf **sheaf, unsigned int size){ return kmem_cache_refill_sheaf(maple_node_cache, gfp, sheaf, size);}
/* * ma_free_rcu() - Use rcu callback to free a maple node * @node: The node to free * * The maple tree uses the parent pointer to indicate this node is no longer in * use and will be freed. */static void ma_free_rcu(struct maple_node *node){ WARN_ON(node->parent != ma_parent_ptr(node)); kfree_rcu(node, rcu);}
static void mt_set_height(struct maple_tree *mt, unsigned char height){ unsigned int new_flags = mt->ma_flags;
new_flags &= ~MT_FLAGS_HEIGHT_MASK; MT_BUG_ON(mt, height > MAPLE_HEIGHT_MAX); new_flags |= height << MT_FLAGS_HEIGHT_OFFSET; mt->ma_flags = new_flags;}
static unsigned int mas_mt_height(struct ma_state *mas){ return mt_height(mas->tree);}
static inline unsigned int mt_attr(struct maple_tree *mt){ return mt->ma_flags & ~MT_FLAGS_HEIGHT_MASK;}
static __always_inline enum maple_type mte_node_type( const struct maple_enode *entry){ return ((unsigned long)entry >> MAPLE_NODE_TYPE_SHIFT) & MAPLE_NODE_TYPE_MASK;}
static __always_inline bool ma_is_dense(const enum maple_type type){ return type < maple_leaf_64;}
static __always_inline bool ma_is_leaf(const enum maple_type type){ return type < maple_range_64;}
static __always_inline bool mte_is_leaf(const struct maple_enode *entry){ return ma_is_leaf(mte_node_type(entry));}
/* * We also reserve values with the bottom two bits set to '10' which are * below 4096 */static __always_inline bool mt_is_reserved(const void *entry){ return ((unsigned long)entry < MAPLE_RESERVED_RANGE) && xa_is_internal(entry);}
static __always_inline void mas_set_err(struct ma_state *mas, long err){ mas->node = MA_ERROR(err); mas->status = ma_error;}
static __always_inline bool mas_is_ptr(const struct ma_state *mas){ return mas->status == ma_root;}
static __always_inline bool mas_is_start(const struct ma_state *mas){ return mas->status == ma_start;}
static __always_inline bool mas_is_none(const struct ma_state *mas){ return mas->status == ma_none;}
static __always_inline bool mas_is_paused(const struct ma_state *mas){ return mas->status == ma_pause;}
static __always_inline bool mas_is_overflow(struct ma_state *mas){ return mas->status == ma_overflow;}
static inline bool mas_is_underflow(struct ma_state *mas){ return mas->status == ma_underflow;}
static inline void mas_make_walkable(struct ma_state *mas){ if (!mas_is_active(mas) && !mas_is_start(mas)) mas->status = ma_start;}
static __always_inline struct maple_node *mte_to_node( const struct maple_enode *entry){ return (struct maple_node *)((unsigned long)entry & ~MAPLE_NODE_MASK);}
/* * mte_to_mat() - Convert a maple encoded node to a maple topiary node. * @entry: The maple encoded node * * Return: a maple topiary pointer */static inline struct maple_topiary *mte_to_mat(const struct maple_enode *entry){ return (struct maple_topiary *) ((unsigned long)entry & ~MAPLE_NODE_MASK);}
/* * mas_mn() - Get the maple state node. * @mas: The maple state * * Return: the maple node (not encoded - bare pointer). */static inline struct maple_node *mas_mn(const struct ma_state *mas){ return mte_to_node(mas->node);}
/* * mte_set_node_dead() - Set a maple encoded node as dead. * @mn: The maple encoded node. */static inline void mte_set_node_dead(struct maple_enode *mn){ mte_to_node(mn)->parent = ma_parent_ptr(mte_to_node(mn)); smp_wmb(); /* Needed for RCU */}
/* Bit 1 indicates the root is a node */#define MAPLE_ROOT_NODE 0x02/* maple_type stored bit 3-6 */#define MAPLE_ENODE_TYPE_SHIFT 0x03/* Bit 2 means a NULL somewhere below */#define MAPLE_ENODE_NULL 0x04
static inline struct maple_enode *mt_mk_node(const struct maple_node *node, enum maple_type type){ return (void *)((unsigned long)node | (type << MAPLE_ENODE_TYPE_SHIFT) | MAPLE_ENODE_NULL);}
static inline void ma_init_slot(void __rcu **slot, const struct maple_node *mn, const enum maple_type mt){ /* WARNING: this is unsafe if the slot is exposed to readers. */ RCU_INIT_POINTER(*slot, (void *)mt_mk_node(mn, mt));}
static inline void *mte_mk_root(const struct maple_enode *node){ return (void *)((unsigned long)node | MAPLE_ROOT_NODE);}
static inline void *mte_safe_root(const struct maple_enode *node){ return (void *)((unsigned long)node & ~MAPLE_ROOT_NODE);}
static inline void __maybe_unused *mte_set_full(const struct maple_enode *node){ return (void *)((unsigned long)node & ~MAPLE_ENODE_NULL);}
static inline void __maybe_unused *mte_clear_full(const struct maple_enode *node){ return (void *)((unsigned long)node | MAPLE_ENODE_NULL);}
static inline bool __maybe_unused mte_has_null(const struct maple_enode *node){ return (unsigned long)node & MAPLE_ENODE_NULL;}
static __always_inline bool ma_is_root(struct maple_node *node){ return ((unsigned long)node->parent & MA_ROOT_PARENT);}
static __always_inline bool mte_is_root(const struct maple_enode *node){ return ma_is_root(mte_to_node(node));}
static __always_inline bool mt_is_alloc(struct maple_tree *mt){ return (mt->ma_flags & MT_FLAGS_ALLOC_RANGE);}
/* * The Parent Pointer * Excluding root, the parent pointer is 256B aligned like all other tree nodes. * When storing a 32 or 64 bit values, the offset can fit into 5 bits. The 16 * bit values need an extra bit to store the offset. This extra bit comes from * a reuse of the last bit in the node type. This is possible by using bit 1 to * indicate if bit 2 is part of the type or the slot. * * Node types: * 0b??1 = Root * 0b?00 = 16 bit nodes * 0b010 = 32 bit nodes * 0b110 = 64 bit nodes * * Slot size and alignment * 0b??1 : Root * 0b?00 : 16 bit values, type in 0-1, slot in 2-7 * 0b010 : 32 bit values, type in 0-2, slot in 3-7 * 0b110 : 64 bit values, type in 0-2, slot in 3-7 */
#define MAPLE_PARENT_ROOT 0x01
#define MAPLE_PARENT_SLOT_SHIFT 0x03#define MAPLE_PARENT_SLOT_MASK 0xF8
#define MAPLE_PARENT_16B_SLOT_SHIFT 0x02#define MAPLE_PARENT_16B_SLOT_MASK 0xFC
#define MAPLE_PARENT_RANGE64 0x06#define MAPLE_PARENT_RANGE32 0x02#define MAPLE_PARENT_NOT_RANGE16 0x02
/* * mte_parent_shift() - Get the parent shift for the slot storage. * @parent: The parent pointer cast as an unsigned long * Return: The shift into that pointer to the star to of the slot */static inline unsigned long mte_parent_shift(unsigned long parent){ /* Note bit 1 == 0 means 16B */ if (likely(parent & MAPLE_PARENT_NOT_RANGE16)) return MAPLE_PARENT_SLOT_SHIFT;
return MAPLE_PARENT_16B_SLOT_SHIFT;}
/* * mte_parent_slot_mask() - Get the slot mask for the parent. * @parent: The parent pointer cast as an unsigned long. * Return: The slot mask for that parent. */static inline unsigned long mte_parent_slot_mask(unsigned long parent){ /* Note bit 1 == 0 means 16B */ if (likely(parent & MAPLE_PARENT_NOT_RANGE16)) return MAPLE_PARENT_SLOT_MASK;
return MAPLE_PARENT_16B_SLOT_MASK;}
/* * mas_parent_type() - Return the maple_type of the parent from the stored * parent type. * @mas: The maple state * @enode: The maple_enode to extract the parent's enum * Return: The node->parent maple_type */static inlineenum maple_type mas_parent_type(struct ma_state *mas, struct maple_enode *enode){ unsigned long p_type;
p_type = (unsigned long)mte_to_node(enode)->parent; if (WARN_ON(p_type & MAPLE_PARENT_ROOT)) return 0;
p_type &= MAPLE_NODE_MASK; p_type &= ~mte_parent_slot_mask(p_type); switch (p_type) { case MAPLE_PARENT_RANGE64: /* or MAPLE_PARENT_ARANGE64 */ if (mt_is_alloc(mas->tree)) return maple_arange_64; return maple_range_64; }
return 0;}
/* * mte_parent_slot() - get the parent slot of @enode. * @enode: The encoded maple node. * * Return: The slot in the parent node where @enode resides. */static __always_inlineunsigned int mte_parent_slot(const struct maple_enode *enode){ unsigned long val = (unsigned long)mte_to_node(enode)->parent;
if (unlikely(val & MA_ROOT_PARENT)) return 0;
/* * Okay to use MAPLE_PARENT_16B_SLOT_MASK as the last bit will be lost * by shift if the parent shift is MAPLE_PARENT_SLOT_SHIFT */ return (val & MAPLE_PARENT_16B_SLOT_MASK) >> mte_parent_shift(val);}
/* * mte_parent() - Get the parent of @node. * @enode: The encoded maple node. * * Return: The parent maple node. */static __always_inlinestruct maple_node *mte_parent(const struct maple_enode *enode){ return (void *)((unsigned long) (mte_to_node(enode)->parent) & ~MAPLE_NODE_MASK);}
/* * ma_dead_node() - check if the @enode is dead. * @enode: The encoded maple node * * Return: true if dead, false otherwise. */static __always_inline bool ma_dead_node(const struct maple_node *node){ struct maple_node *parent;
/* Do not reorder reads from the node prior to the parent check */ smp_rmb(); parent = (void *)((unsigned long) node->parent & ~MAPLE_NODE_MASK); return (parent == node);}
/* * mte_dead_node() - check if the @enode is dead. * @enode: The encoded maple node * * Return: true if dead, false otherwise. */static __always_inline bool mte_dead_node(const struct maple_enode *enode){ struct maple_node *node;
node = mte_to_node(enode); return ma_dead_node(node);}
/* * ma_pivots() - Get a pointer to the maple node pivots. * @node: the maple node * @type: the node type * * In the event of a dead node, this array may be %NULL * * Return: A pointer to the maple node pivots */static inline unsigned long *ma_pivots(struct maple_node *node, enum maple_type type){ switch (type) { case maple_arange_64: return node->ma64.pivot; case maple_range_64: case maple_leaf_64: return node->mr64.pivot; case maple_copy: return node->cp.pivot; case maple_dense: return NULL; } return NULL;}
/* * ma_gaps() - Get a pointer to the maple node gaps. * @node: the maple node * @type: the node type * * Return: A pointer to the maple node gaps */static inline unsigned long *ma_gaps(struct maple_node *node, enum maple_type type){ switch (type) { case maple_arange_64: return node->ma64.gap; case maple_copy: return node->cp.gap; case maple_range_64: case maple_leaf_64: case maple_dense: return NULL; } return NULL;}
/* * mas_safe_pivot() - get the pivot at @piv or mas->max. * @mas: The maple state * @pivots: The pointer to the maple node pivots * @piv: The pivot to fetch * @type: The maple node type * * Return: The pivot at @piv within the limit of the @pivots array, @mas->max * otherwise. */static __always_inline unsigned longmas_safe_pivot(const struct ma_state *mas, unsigned long *pivots, unsigned char piv, enum maple_type type){ if (piv >= mt_pivots[type]) return mas->max;
return pivots[piv];}
/* * mas_safe_min() - Return the minimum for a given offset. * @mas: The maple state * @pivots: The pointer to the maple node pivots * @offset: The offset into the pivot array * * Return: The minimum range value that is contained in @offset. */static inline unsigned longmas_safe_min(struct ma_state *mas, unsigned long *pivots, unsigned char offset){ if (likely(offset)) return pivots[offset - 1] + 1;
return mas->min;}
/* * mte_set_pivot() - Set a pivot to a value in an encoded maple node. * @mn: The encoded maple node * @piv: The pivot offset * @val: The value of the pivot */static inline void mte_set_pivot(struct maple_enode *mn, unsigned char piv, unsigned long val){ struct maple_node *node = mte_to_node(mn); enum maple_type type = mte_node_type(mn);
BUG_ON(piv >= mt_pivots[type]); switch (type) { case maple_range_64: case maple_leaf_64: node->mr64.pivot[piv] = val; break; case maple_arange_64: node->ma64.pivot[piv] = val; break; case maple_copy: case maple_dense: break; }
}
/* * ma_slots() - Get a pointer to the maple node slots. * @mn: The maple node * @mt: The maple node type * * Return: A pointer to the maple node slots */static inline void __rcu **ma_slots(struct maple_node *mn, enum maple_type mt){ switch (mt) { case maple_arange_64: return mn->ma64.slot; case maple_range_64: case maple_leaf_64: return mn->mr64.slot; case maple_copy: return mn->cp.slot; case maple_dense: return mn->slot; }
return NULL;}
static inline bool mt_write_locked(const struct maple_tree *mt){ return mt_external_lock(mt) ? mt_write_lock_is_held(mt) : lockdep_is_held(&mt->ma_lock);}
static __always_inline bool mt_locked(const struct maple_tree *mt){ return mt_external_lock(mt) ? mt_lock_is_held(mt) : lockdep_is_held(&mt->ma_lock);}
static __always_inline void *mt_slot(const struct maple_tree *mt, void __rcu **slots, unsigned char offset){ return rcu_dereference_check(slots[offset], mt_locked(mt));}
static __always_inline void *mt_slot_locked(struct maple_tree *mt, void __rcu **slots, unsigned char offset){ return rcu_dereference_protected(slots[offset], mt_write_locked(mt));}/* * mas_slot_locked() - Get the slot value when holding the maple tree lock. * @mas: The maple state * @slots: The pointer to the slots * @offset: The offset into the slots array to fetch * * Return: The entry stored in @slots at the @offset. */static __always_inline void *mas_slot_locked(struct ma_state *mas, void __rcu **slots, unsigned char offset){ return mt_slot_locked(mas->tree, slots, offset);}
/* * mas_slot() - Get the slot value when not holding the maple tree lock. * @mas: The maple state * @slots: The pointer to the slots * @offset: The offset into the slots array to fetch * * Return: The entry stored in @slots at the @offset */static __always_inline void *mas_slot(struct ma_state *mas, void __rcu **slots, unsigned char offset){ return mt_slot(mas->tree, slots, offset);}
/* * mas_root() - Get the maple tree root. * @mas: The maple state. * * Return: The pointer to the root of the tree */static __always_inline void *mas_root(struct ma_state *mas){ return rcu_dereference_check(mas->tree->ma_root, mt_locked(mas->tree));}
static inline void *mt_root_locked(struct maple_tree *mt){ return rcu_dereference_protected(mt->ma_root, mt_write_locked(mt));}
/* * mas_root_locked() - Get the maple tree root when holding the maple tree lock. * @mas: The maple state. * * Return: The pointer to the root of the tree */static inline void *mas_root_locked(struct ma_state *mas){ return mt_root_locked(mas->tree);}
static inline struct maple_metadata *ma_meta(struct maple_node *mn, enum maple_type mt){ switch (mt) { case maple_arange_64: return &mn->ma64.meta; default: return &mn->mr64.meta; }}
/* * ma_set_meta() - Set the metadata information of a node. * @mn: The maple node * @mt: The maple node type * @offset: The offset of the highest sub-gap in this node. * @end: The end of the data in this node. */static inline void ma_set_meta(struct maple_node *mn, enum maple_type mt, unsigned char offset, unsigned char end){ struct maple_metadata *meta = ma_meta(mn, mt);
meta->gap = offset; meta->end = end;}
/* * ma_meta_end() - Get the data end of a node from the metadata * @mn: The maple node * @mt: The maple node type */static inline unsigned char ma_meta_end(struct maple_node *mn, enum maple_type mt){ struct maple_metadata *meta = ma_meta(mn, mt);
return meta->end;}
/* * ma_meta_gap() - Get the largest gap location of a node from the metadata * @mn: The maple node */static inline unsigned char ma_meta_gap(struct maple_node *mn){ return mn->ma64.meta.gap;}
/* * ma_set_meta_gap() - Set the largest gap location in a nodes metadata * @mn: The maple node * @mt: The maple node type * @offset: The location of the largest gap. */static inline void ma_set_meta_gap(struct maple_node *mn, enum maple_type mt, unsigned char offset){
struct maple_metadata *meta = ma_meta(mn, mt);
meta->gap = offset;}
/* * mas_set_parent_slots() - Bulk operation to set many slot parent pointers * @mas: The maple state * @parent: The encoded maple node that is the parent of @enode. * @slot: The slot that of the @enode. * @start_slot: The offset into @slot * @count: The number of slots to set (eg: exclusive) */static inlinevoid mas_set_parent_slots(struct ma_state *mas, struct maple_enode *parent, void __rcu **slots, unsigned char start_slot, unsigned char count){ unsigned long val; unsigned long shift; unsigned long type; enum maple_type p_type = mte_node_type(parent); unsigned char i;
MAS_BUG_ON(mas, p_type != maple_range_64 && p_type != maple_arange_64);
shift = MAPLE_PARENT_SLOT_SHIFT; type = MAPLE_PARENT_RANGE64;
val = (unsigned long)parent; val &= ~MAPLE_NODE_MASK;
for (i = 0; i < count; i++) { unsigned long pval = val | ((start_slot + i) << shift) | type; struct maple_enode *child;
child = mt_slot_locked(mas->tree, slots, i); mte_to_node(child)->parent = ma_parent_ptr(pval); }}
/* * mat_add() - Add a @dead_enode to the ma_topiary of a list of dead nodes. * @mat: the ma_topiary, a linked list of dead nodes. * @dead_enode: the node to be marked as dead and added to the tail of the list * * Add the @dead_enode to the linked list in @mat. */static inline void mat_add(struct ma_topiary *mat, struct maple_enode *dead_enode){ mte_set_node_dead(dead_enode); mte_to_mat(dead_enode)->next = NULL; if (!mat->tail) { mat->tail = mat->head = dead_enode; return; }
mte_to_mat(mat->tail)->next = dead_enode; mat->tail = dead_enode;}
static void mt_free_walk(struct rcu_head *head);static void mt_destroy_walk(struct maple_enode *enode, struct maple_tree *mt, bool free);/* * mas_mat_destroy() - Free all nodes and subtrees in a dead list. * @mas: the maple state * @mat: the ma_topiary linked list of dead nodes to free. * * Destroy walk a dead list. */static void mas_mat_destroy(struct ma_state *mas, struct ma_topiary *mat){ struct maple_enode *next; struct maple_node *node; bool in_rcu = mt_in_rcu(mas->tree);
while (mat->head) { next = mte_to_mat(mat->head)->next; node = mte_to_node(mat->head); mt_destroy_walk(mat->head, mas->tree, !in_rcu); if (in_rcu) call_rcu(&node->rcu, mt_free_walk); mat->head = next; }}/* * mas_descend() - Descend into the slot stored in the ma_state. * @mas: the maple state. * * Note: Not RCU safe, only use in write side or debug code. */static inline void mas_descend(struct ma_state *mas){ enum maple_type type; unsigned long *pivots; struct maple_node *node; void __rcu **slots;
node = mas_mn(mas); type = mte_node_type(mas->node); pivots = ma_pivots(node, type); slots = ma_slots(node, type);
if (mas->offset) mas->min = pivots[mas->offset - 1] + 1; mas->max = mas_safe_pivot(mas, pivots, mas->offset, type); mas->node = mas_slot(mas, slots, mas->offset);}
/* * mas_ascend() - Walk up a level of the tree. * @mas: The maple state * * Sets the @mas->max and @mas->min for the parent node of mas->node. This * may cause several levels of walking up to find the correct min and max. * May find a dead node which will cause a premature return. * Return: 1 on dead node, 0 otherwise */static int mas_ascend(struct ma_state *mas){ struct maple_enode *p_enode; /* parent enode. */ struct maple_enode *a_enode; /* ancestor enode. */ struct maple_node *a_node; /* ancestor node. */ struct maple_node *p_node; /* parent node. */ unsigned char a_slot; enum maple_type a_type; unsigned long min, max; unsigned long *pivots; bool set_max = false, set_min = false;
a_node = mas_mn(mas); if (ma_is_root(a_node)) { mas->offset = 0; return 0; }
p_node = mte_parent(mas->node); if (unlikely(a_node == p_node)) return 1;
a_type = mas_parent_type(mas, mas->node); mas->offset = mte_parent_slot(mas->node); a_enode = mt_mk_node(p_node, a_type);
/* Check to make sure all parent information is still accurate */ if (p_node != mte_parent(mas->node)) return 1;
mas->node = a_enode;
if (mte_is_root(a_enode)) { mas->max = ULONG_MAX; mas->min = 0; return 0; }
min = 0; max = ULONG_MAX;
/* * !mas->offset implies that parent node min == mas->min. * mas->offset > 0 implies that we need to walk up to find the * implied pivot min. */ if (!mas->offset) { min = mas->min; set_min = true; }
if (mas->max == ULONG_MAX) set_max = true;
do { p_enode = a_enode; a_type = mas_parent_type(mas, p_enode); a_node = mte_parent(p_enode); a_slot = mte_parent_slot(p_enode); a_enode = mt_mk_node(a_node, a_type); pivots = ma_pivots(a_node, a_type);
if (unlikely(ma_dead_node(a_node))) return 1;
if (!set_min && a_slot) { set_min = true; min = pivots[a_slot - 1] + 1; }
if (!set_max && a_slot < mt_pivots[a_type]) { set_max = true; max = pivots[a_slot]; }
if (unlikely(ma_dead_node(a_node))) return 1;
if (unlikely(ma_is_root(a_node))) break;
} while (!set_min || !set_max);
mas->max = max; mas->min = min; return 0;}
/* * mas_pop_node() - Get a previously allocated maple node from the maple state. * @mas: The maple state * * Return: A pointer to a maple node. */static __always_inline struct maple_node *mas_pop_node(struct ma_state *mas){ struct maple_node *ret;
if (mas->alloc) { ret = mas->alloc; mas->alloc = NULL; goto out; }
if (WARN_ON_ONCE(!mas->sheaf)) return NULL;
ret = kmem_cache_alloc_from_sheaf(maple_node_cache, GFP_NOWAIT, mas->sheaf);
out: memset(ret, 0, sizeof(*ret)); return ret;}
/* * mas_alloc_nodes() - Allocate nodes into a maple state * @mas: The maple state * @gfp: The GFP Flags */static inline void mas_alloc_nodes(struct ma_state *mas, gfp_t gfp){ if (!mas->node_request) return;
if (mas->node_request == 1) { if (mas->sheaf) goto use_sheaf;
if (mas->alloc) return;
mas->alloc = mt_alloc_one(gfp); if (!mas->alloc) goto error;
mas->node_request = 0; return; }
use_sheaf: if (unlikely(mas->alloc)) { kfree(mas->alloc); mas->alloc = NULL; }
if (mas->sheaf) { unsigned long refill;
refill = mas->node_request; if (kmem_cache_sheaf_size(mas->sheaf) >= refill) { mas->node_request = 0; return; }
if (mt_refill_sheaf(gfp, &mas->sheaf, refill)) goto error;
mas->node_request = 0; return; }
mas->sheaf = mt_get_sheaf(gfp, mas->node_request); if (likely(mas->sheaf)) { mas->node_request = 0; return; }
error: mas_set_err(mas, -ENOMEM);}
static inline void mas_empty_nodes(struct ma_state *mas){ mas->node_request = 0; if (mas->sheaf) { mt_return_sheaf(mas->sheaf); mas->sheaf = NULL; }
if (mas->alloc) { kfree(mas->alloc); mas->alloc = NULL; }}
/* * mas_free() - Free an encoded maple node * @mas: The maple state * @used: The encoded maple node to free. * * Uses rcu free if necessary, pushes @used back on the maple state allocations * otherwise. */static inline void mas_free(struct ma_state *mas, struct maple_enode *used){ ma_free_rcu(mte_to_node(used));}
#ifdef CONFIG_LOCKDEPstatic struct lockdep_map *mas_lockdep_map(struct ma_state *mas){ struct maple_tree *mt = mas->tree;
if (mt_external_lock(mt)) return mt->ma_external_lock;
return &(mt->ma_lock).dep_map;}
#endif
static void mas_lock_check(struct ma_state *mas){#ifdef CONFIG_LOCKDEP struct lockdep_map *map; u32 seq;
if (!mas_is_active(mas)) return;
#ifdef CONFIG_RCU_STRICT_GRACE_PERIOD if (!mt_locked(mas->tree)) { if (mt_in_rcu(mas->tree)) WARN_ON_ONCE(poll_state_synchronize_rcu(mas->rcu_gp)); }#endif /* CONFIG_RCU_STRICT_GRACE_PERIOD */
map = mas_lockdep_map(mas); if (!map) return;
seq = lock_sequence(map); if (seq != UINT_MAX && mas->ld_seq != UINT_MAX) WARN_ON_ONCE(mas->ld_seq != seq);#endif /* CONFIG_LOCKDEP */
}
static void mas_init_lock_check(struct ma_state *mas){#ifdef CONFIG_LOCKDEP struct lockdep_map *map;#ifdef CONFIG_RCU_STRICT_GRACE_PERIOD if (!mt_locked(mas->tree)) { if (mt_in_rcu(mas->tree)) mas->rcu_gp = get_state_synchronize_rcu(); return; }#endif /* CONFIG_RCU_STRICT_GRACE_PERIOD */
map = mas_lockdep_map(mas); if (map) /* Update regardless of lock state */ mas->ld_seq = lock_sequence(map);#endif /* CONFIG_LOCKDEP */
}
static void mas_may_init_lock_check(struct ma_state *mas){#ifdef CONFIG_LOCKDEP#ifdef CONFIG_RCU_STRICT_GRACE_PERIOD if (mas_is_start(mas) || mas_is_paused(mas)) { mas_init_lock_check(mas); return; }#endif /* CONFIG_RCU_STRICT_GRACE_PERIOD */ mas_lock_check(mas);#endif /* CONFIG_LOCKDEP */}
/* * mas_start() - Sets up maple state for operations. * @mas: The maple state. * * If mas->status == ma_start, then set the min, max and depth to * defaults. * * Return: * - If mas->node is an error or not mas_start, return NULL. * - If it's an empty tree: NULL & mas->status == ma_none * - If it's a single entry: The entry & mas->status == ma_root * - If it's a tree: NULL & mas->status == ma_active */static inline struct maple_enode *mas_start(struct ma_state *mas){ if (likely(mas_is_start(mas))) { struct maple_enode *root;
mas_init_lock_check(mas); mas->min = 0; mas->max = ULONG_MAX;
retry: mas->depth = 0; root = mas_root(mas); /* Tree with nodes */ if (likely(xa_is_node(root))) { mas->depth = 0; mas->status = ma_active; mas->node = mte_safe_root(root); mas->offset = 0; if (mte_dead_node(mas->node)) goto retry;
return NULL; }
mas->node = NULL; /* empty tree */ if (unlikely(!root)) { mas->status = ma_none; mas->offset = MAPLE_NODE_SLOTS; return NULL; }
/* Single entry tree */ mas->status = ma_root; mas->offset = MAPLE_NODE_SLOTS;
/* Single entry tree. */ if (mas->index > 0) return NULL;
return root; }
return NULL;}
/* * ma_data_end() - Find the end of the data in a node. * @node: The maple node * @type: The maple node type * @pivots: The array of pivots in the node * @max: The maximum value in the node * * Uses metadata to find the end of the data when possible. * Return: The zero indexed last slot with data (may be null). */static __always_inline unsigned char ma_data_end(struct maple_node *node, enum maple_type type, unsigned long *pivots, unsigned long max){ unsigned char offset;
if (!pivots) return 0;
if (type == maple_arange_64) return ma_meta_end(node, type);
offset = mt_pivots[type] - 1; if (likely(!pivots[offset])) return ma_meta_end(node, type);
if (likely(pivots[offset] == max)) return offset;
return mt_pivots[type];}
/* * mas_data_end() - Find the end of the data (slot). * @mas: the maple state * * This method is optimized to check the metadata of a node if the node type * supports data end metadata. * * Return: The zero indexed last slot with data (may be null). */static inline unsigned char mas_data_end(struct ma_state *mas){ enum maple_type type; struct maple_node *node; unsigned char offset; unsigned long *pivots;
type = mte_node_type(mas->node); node = mas_mn(mas); if (type == maple_arange_64) return ma_meta_end(node, type);
pivots = ma_pivots(node, type); if (unlikely(ma_dead_node(node))) return 0;
offset = mt_pivots[type] - 1; if (likely(!pivots[offset])) return ma_meta_end(node, type);
if (likely(pivots[offset] == mas->max)) return offset;
return mt_pivots[type];}
static inlinevoid wr_mas_setup(struct ma_wr_state *wr_mas, struct ma_state *mas){ wr_mas->node = mas_mn(mas); wr_mas->type = mte_node_type(mas->node); wr_mas->pivots = ma_pivots(wr_mas->node, wr_mas->type); wr_mas->slots = ma_slots(wr_mas->node, wr_mas->type); wr_mas->r_min = mas_safe_min(mas, wr_mas->pivots, mas->offset); wr_mas->r_max = mas_safe_pivot(mas, wr_mas->pivots, mas->offset, wr_mas->type);}
static inlinevoid wr_mas_ascend(struct ma_wr_state *wr_mas){ struct ma_state *mas = wr_mas->mas;
mas_ascend(mas); wr_mas_setup(wr_mas, mas); mas->end = ma_data_end(wr_mas->node, wr_mas->type, wr_mas->pivots, mas->max); /* Careful, this may be wrong.. */ wr_mas->end_piv = wr_mas->r_max; wr_mas->offset_end = mas->offset;}
static inline unsigned long ma_leaf_max_gap(struct maple_node *mn, enum maple_type mt, unsigned long min, unsigned long max, unsigned long *pivots, void __rcu **slots){ unsigned long pstart, gap, max_gap; unsigned char i; unsigned char max_piv;
max_gap = 0; if (unlikely(ma_is_dense(mt))) { gap = 0; for (i = 0; i < mt_slots[mt]; i++) { if (slots[i]) { if (gap > max_gap) max_gap = gap; gap = 0; } else { gap++; } } if (gap > max_gap) max_gap = gap; return max_gap; }
/* * Check the first implied pivot optimizes the loop below and slot 1 may * be skipped if there is a gap in slot 0. */ if (likely(!slots[0])) { max_gap = pivots[0] - min + 1; i = 2; } else { i = 1; }
/* reduce max_piv as the special case is checked before the loop */ max_piv = ma_data_end(mn, mt, pivots, max) - 1; /* * Check end implied pivot which can only be a gap on the right most * node. */ if (unlikely(max == ULONG_MAX) && !slots[max_piv + 1]) { gap = ULONG_MAX - pivots[max_piv]; if (gap > max_gap) max_gap = gap;
if (max_gap > pivots[max_piv] - min) return max_gap; }
for (; i <= max_piv; i++) { /* data == no gap. */ if (likely(slots[i])) continue;
pstart = pivots[i - 1]; gap = pivots[i] - pstart; if (gap > max_gap) max_gap = gap;
/* There cannot be two gaps in a row. */ i++; } return max_gap;}
/* * mas_leaf_max_gap() - Returns the largest gap in a leaf node * @mas: the maple state * * Return: The maximum gap in the leaf. */static inline unsigned long mas_leaf_max_gap(struct ma_state *mas){ enum maple_type mt; struct maple_node *mn; unsigned long *pivots; void __rcu **slots;
mn = mas_mn(mas); mt = mte_node_type(mas->node); slots = ma_slots(mn, mt); pivots = ma_pivots(mn, mt);
return ma_leaf_max_gap(mn, mt, mas->min, mas->max, pivots, slots);}
/* * ma_max_gap() - Get the maximum gap in a maple node (non-leaf) * @node: The maple node * @gaps: The pointer to the gaps * @mt: The maple node type * @off: Pointer to store the offset location of the gap. * * Uses the metadata data end to scan backwards across set gaps. * * Return: The maximum gap value */static inline unsigned longma_max_gap(struct maple_node *node, unsigned long *gaps, enum maple_type mt, unsigned char *off){ unsigned char offset, i; unsigned long max_gap = 0;
i = offset = ma_meta_end(node, mt); do { if (gaps[i] > max_gap) { max_gap = gaps[i]; offset = i; } } while (i--);
*off = offset; return max_gap;}
/* * mas_max_gap() - find the largest gap in a non-leaf node and set the slot. * @mas: The maple state. * * Return: The gap value. */static inline unsigned long mas_max_gap(struct ma_state *mas){ unsigned long *gaps; unsigned char offset; enum maple_type mt; struct maple_node *node;
mt = mte_node_type(mas->node); if (ma_is_leaf(mt)) return mas_leaf_max_gap(mas);
node = mas_mn(mas); MAS_BUG_ON(mas, mt != maple_arange_64); offset = ma_meta_gap(node); gaps = ma_gaps(node, mt); return gaps[offset];}
/* * mas_parent_gap() - Set the parent gap and any gaps above, as needed * @mas: The maple state * @offset: The gap offset in the parent to set * @new: The new gap value. * * Set the parent gap then continue to set the gap upwards, using the metadata * of the parent to see if it is necessary to check the node above. */static inline void mas_parent_gap(struct ma_state *mas, unsigned char offset, unsigned long new){ unsigned long meta_gap = 0; struct maple_node *pnode; struct maple_enode *penode; unsigned long *pgaps; unsigned char meta_offset; enum maple_type pmt;
pnode = mte_parent(mas->node); pmt = mas_parent_type(mas, mas->node); penode = mt_mk_node(pnode, pmt); pgaps = ma_gaps(pnode, pmt);
ascend: MAS_BUG_ON(mas, pmt != maple_arange_64); meta_offset = ma_meta_gap(pnode); meta_gap = pgaps[meta_offset];
pgaps[offset] = new;
if (meta_gap == new) return;
if (offset != meta_offset) { if (meta_gap > new) return;
ma_set_meta_gap(pnode, pmt, offset); } else if (new < meta_gap) { new = ma_max_gap(pnode, pgaps, pmt, &meta_offset); ma_set_meta_gap(pnode, pmt, meta_offset); }
if (ma_is_root(pnode)) return;
/* Go to the parent node. */ pnode = mte_parent(penode); pmt = mas_parent_type(mas, penode); pgaps = ma_gaps(pnode, pmt); offset = mte_parent_slot(penode); penode = mt_mk_node(pnode, pmt); goto ascend;}
static __always_inline void mas_update_gap_known(struct ma_state *mas, unsigned long gap){ unsigned char pslot; unsigned long p_gap;
pslot = mte_parent_slot(mas->node); p_gap = ma_gaps(mte_parent(mas->node), mas_parent_type(mas, mas->node))[pslot];
if (p_gap != gap) mas_parent_gap(mas, pslot, gap);}
/* * mas_update_gap() - Update a nodes gaps and propagate up if necessary. * @mas: the maple state. */static inline void mas_update_gap(struct ma_state *mas){ unsigned long max_gap;
if (!mt_is_alloc(mas->tree)) return;
if (mte_is_root(mas->node)) return;
max_gap = mas_max_gap(mas); mas_update_gap_known(mas, max_gap);}
/* * mas_adopt_children() - Set the parent pointer of all nodes in @parent to * @parent with the slot encoded. * @mas: the maple state (for the tree) * @parent: the maple encoded node containing the children. */static inline void mas_adopt_children(struct ma_state *mas, struct maple_enode *parent){ enum maple_type type = mte_node_type(parent); struct maple_node *node = mte_to_node(parent); void __rcu **slots = ma_slots(node, type); unsigned long *pivots = ma_pivots(node, type); unsigned char end;
end = ma_data_end(node, type, pivots, mas->max); mas_set_parent_slots(mas, parent, slots, 0, end + 1);}
/* * mas_put_in_tree() - Put a new node in the tree, smp_wmb(), and mark the old * node as dead. * @mas: the maple state with the new node * @old_enode: The old maple encoded node to replace. * @new_height: if we are inserting a root node, update the height of the tree */static inline void mas_put_in_tree(struct ma_state *mas, struct maple_enode *old_enode, char new_height) __must_hold(mas->tree->ma_lock){ unsigned char offset; void __rcu **slots;
if (mte_is_root(mas->node)) { mas_mn(mas)->parent = ma_parent_ptr(mas_tree_parent(mas)); rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node)); mt_set_height(mas->tree, new_height); } else {
offset = mte_parent_slot(mas->node); slots = ma_slots(mte_parent(mas->node), mas_parent_type(mas, mas->node)); rcu_assign_pointer(slots[offset], mas->node); }
mte_set_node_dead(old_enode);}
/* * mas_replace_node() - Replace a node by putting it in the tree, marking it * dead, and freeing it. * the parent encoding to locate the maple node in the tree. * @mas: the ma_state with @mas->node pointing to the new node. * @old_enode: The old maple encoded node. * @new_height: The new height of the tree as a result of the operation */static inline void mas_replace_node(struct ma_state *mas, struct maple_enode *old_enode, unsigned char new_height) __must_hold(mas->tree->ma_lock){ mas_put_in_tree(mas, old_enode, new_height); mas_free(mas, old_enode);}
/* * mas_find_child() - Find a child who has the parent @mas->node. * @mas: the maple state with the parent. * @child: the maple state to store the child. */static inline bool mas_find_child(struct ma_state *mas, struct ma_state *child) __must_hold(mas->tree->ma_lock){ enum maple_type mt; unsigned char offset; unsigned char end; unsigned long *pivots; struct maple_enode *entry; struct maple_node *node; void __rcu **slots;
mt = mte_node_type(mas->node); node = mas_mn(mas); slots = ma_slots(node, mt); pivots = ma_pivots(node, mt); end = ma_data_end(node, mt, pivots, mas->max); for (offset = mas->offset; offset <= end; offset++) { entry = mas_slot_locked(mas, slots, offset); if (mte_parent(entry) == node) { *child = *mas; mas->offset = offset + 1; child->offset = offset; mas_descend(child); child->offset = 0; return true; } } return false;}
/* * mas_leaf_set_meta() - Set the metadata of a leaf if possible. * @node: The maple node * @mt: The maple type * @end: The node end */static inline void mas_leaf_set_meta(struct maple_node *node, enum maple_type mt, unsigned char end){ if (end < mt_slots[mt] - 1) ma_set_meta(node, mt, 0, end);}
/* * mas_prev_sibling() - Find the previous node with the same parent. * @mas: the maple state * * Return: True if there is a previous sibling, false otherwise. */static inline bool mas_prev_sibling(struct ma_state *mas){ unsigned int p_slot = mte_parent_slot(mas->node);
/* For root node, p_slot is set to 0 by mte_parent_slot(). */ if (!p_slot) return false;
mas_ascend(mas); mas->offset = p_slot - 1; mas_descend(mas); return true;}
/* * mas_next_sibling() - Find the next node with the same parent. * @mas: the maple state * * Return: true if there is a next sibling, false otherwise. */static inline bool mas_next_sibling(struct ma_state *mas){ MA_STATE(parent, mas->tree, mas->index, mas->last);
if (mte_is_root(mas->node)) return false;
parent = *mas; mas_ascend(&parent); parent.offset = mte_parent_slot(mas->node) + 1; if (parent.offset > mas_data_end(&parent)) return false;
*mas = parent; mas_descend(mas); return true;}
/* * mas_wr_node_walk() - Find the correct offset for the index in the @mas. * If @mas->index cannot be found within the containing * node, we traverse to the last entry in the node. * @wr_mas: The maple write state * * Uses mas_slot_locked() and does not need to worry about dead nodes. */static inline void mas_wr_node_walk(struct ma_wr_state *wr_mas){ struct ma_state *mas = wr_mas->mas; unsigned char count, offset;
if (unlikely(ma_is_dense(wr_mas->type))) { wr_mas->r_max = wr_mas->r_min = mas->index; mas->offset = mas->index = mas->min; return; }
wr_mas->node = mas_mn(wr_mas->mas); wr_mas->pivots = ma_pivots(wr_mas->node, wr_mas->type); count = mas->end = ma_data_end(wr_mas->node, wr_mas->type, wr_mas->pivots, mas->max); offset = mas->offset;
while (offset < count && mas->index > wr_mas->pivots[offset]) offset++;
wr_mas->r_max = offset < count ? wr_mas->pivots[offset] : mas->max; wr_mas->r_min = mas_safe_min(mas, wr_mas->pivots, offset); wr_mas->offset_end = mas->offset = offset;}
static inline void rebalance_sib(struct ma_state *parent, struct ma_state *sib){ *sib = *parent; /* Prioritize move right to pull data left */ if (sib->offset < sib->end) sib->offset++; else sib->offset--;
mas_descend(sib); sib->end = mas_data_end(sib);}
static inlinevoid spanning_sib(struct ma_wr_state *l_wr_mas, struct ma_wr_state *r_wr_mas, struct ma_state *nneighbour){ struct ma_state l_tmp = *l_wr_mas->mas; struct ma_state r_tmp = *r_wr_mas->mas; unsigned char depth = 0;
do { mas_ascend(&r_tmp); mas_ascend(&l_tmp); depth++; if (r_tmp.offset < mas_data_end(&r_tmp)) { r_tmp.offset++; mas_descend(&r_tmp); r_tmp.offset = 0; while (--depth) mas_descend(&r_tmp);
r_tmp.end = mas_data_end(&r_tmp); *nneighbour = r_tmp; return; } else if (l_tmp.offset) { l_tmp.offset--; do { mas_descend(&l_tmp); l_tmp.offset = mas_data_end(&l_tmp); } while (--depth);
l_tmp.end = l_tmp.offset; *nneighbour = l_tmp; return; } } while (!mte_is_root(r_tmp.node));
WARN_ON_ONCE(1);}
/* * mas_topiary_node() - Dispose of a single node * @mas: The maple state for pushing nodes * @in_rcu: If the tree is in rcu mode * * The node will either be RCU freed or pushed back on the maple state. */static inline void mas_topiary_node(struct ma_state *mas, struct ma_state *tmp_mas, bool in_rcu){ struct maple_node *tmp; struct maple_enode *enode;
if (mas_is_none(tmp_mas)) return;
enode = tmp_mas->node; tmp = mte_to_node(enode); mte_set_node_dead(enode); ma_free_rcu(tmp);}
/* * mas_topiary_replace() - Replace the data with new data, then repair the * parent links within the new tree. Iterate over the dead sub-tree and collect * the dead subtrees and topiary the nodes that are no longer of use. * * The new tree will have up to three children with the correct parent. Keep * track of the new entries as they need to be followed to find the next level * of new entries. * * The old tree will have up to three children with the old parent. Keep track * of the old entries as they may have more nodes below replaced. Nodes within * [index, last] are dead subtrees, others need to be freed and followed. * * @mas: The maple state pointing at the new data * @old_enode: The maple encoded node being replaced * @new_height: The new height of the tree as a result of the operation * */static inline void mas_topiary_replace(struct ma_state *mas, struct maple_enode *old_enode, unsigned char new_height){ struct ma_state tmp[3], tmp_next[3]; MA_TOPIARY(subtrees, mas->tree); bool in_rcu; int i, n;
/* Place data in tree & then mark node as old */ mas_put_in_tree(mas, old_enode, new_height);
/* Update the parent pointers in the tree */ tmp[0] = *mas; tmp[0].offset = 0; tmp[1].status = ma_none; tmp[2].status = ma_none; while (!mte_is_leaf(tmp[0].node)) { n = 0; for (i = 0; i < 3; i++) { if (mas_is_none(&tmp[i])) continue;
while (n < 3) { if (!mas_find_child(&tmp[i], &tmp_next[n])) break; n++; }
mas_adopt_children(&tmp[i], tmp[i].node); }
if (MAS_WARN_ON(mas, n == 0)) break;
while (n < 3) tmp_next[n++].status = ma_none;
for (i = 0; i < 3; i++) tmp[i] = tmp_next[i]; }
/* Collect the old nodes that need to be discarded */ if (mte_is_leaf(old_enode)) return mas_free(mas, old_enode);
tmp[0] = *mas; tmp[0].offset = 0; tmp[0].node = old_enode; tmp[1].status = ma_none; tmp[2].status = ma_none; in_rcu = mt_in_rcu(mas->tree); do { n = 0; for (i = 0; i < 3; i++) { if (mas_is_none(&tmp[i])) continue;
while (n < 3) { if (!mas_find_child(&tmp[i], &tmp_next[n])) break;
if ((tmp_next[n].min >= tmp_next->index) && (tmp_next[n].max <= tmp_next->last)) { mat_add(&subtrees, tmp_next[n].node); tmp_next[n].status = ma_none; } else { n++; } } }
if (MAS_WARN_ON(mas, n == 0)) break;
while (n < 3) tmp_next[n++].status = ma_none;
for (i = 0; i < 3; i++) { mas_topiary_node(mas, &tmp[i], in_rcu); tmp[i] = tmp_next[i]; } } while (!mte_is_leaf(tmp[0].node));
for (i = 0; i < 3; i++) mas_topiary_node(mas, &tmp[i], in_rcu);
mas_mat_destroy(mas, &subtrees);}
/* * node_copy() - Copy from one node to another. * * @mas: The maple state * @src: The source node * @start: The offset into the src to start copying * @size: The size to copy (non-zero) * @s_max: The source node max * @s_mt: The source maple node type * @dst: The destination * @d_start: The start location in the destination node * @d_mt: The destination maple node type */static inlineunsigned long node_copy(struct ma_state *mas, struct maple_node *src, unsigned char start, unsigned char size, unsigned long s_max, enum maple_type s_mt, struct maple_node *dst, unsigned char d_start, enum maple_type d_mt){ unsigned long *s_pivots, *d_pivots; void __rcu **s_slots, **d_slots; unsigned long *s_gaps, *d_gaps; unsigned long d_max;
d_slots = ma_slots(dst, d_mt) + d_start; d_pivots = ma_pivots(dst, d_mt) + d_start; s_slots = ma_slots(src, s_mt) + start; s_pivots = ma_pivots(src, s_mt) + start; memcpy(d_slots, s_slots, size * sizeof(void __rcu *));
if (!ma_is_leaf(d_mt) && s_mt == maple_copy) mas_set_parent_slots(mas, mt_mk_node(dst, d_mt), d_slots, d_start, size);
d_gaps = ma_gaps(dst, d_mt); if (d_gaps) { s_gaps = ma_gaps(src, s_mt) + start; d_gaps += d_start; memcpy(d_gaps, s_gaps, size * sizeof(unsigned long)); }
if (start + size - 1 < mt_pivots[s_mt]) d_max = s_pivots[size - 1]; else d_max = s_max;
if (d_start + size <= mt_pivots[d_mt]) d_pivots[size - 1] = d_max;
size--; if (size) memcpy(d_pivots, s_pivots, size * sizeof(unsigned long));
return d_max;}
/* * node_finalise() - Zero out unused area and populate metadata * @node: The maple node * @mt: The maple node type * @end: The end of the used area */static inlinevoid node_finalise(struct maple_node *node, enum maple_type mt, unsigned char end){ unsigned char max_end = mt_slots[mt]; unsigned char size; unsigned long *gaps; unsigned char gap_slot;
gaps = ma_gaps(node, mt); if (end < max_end - 1) { size = max_end - end; memset(ma_slots(node, mt) + end, 0, size * sizeof(void *));
if (gaps) memset(gaps + end, 0, size * sizeof(unsigned long));
if (--size) memset(ma_pivots(node, mt) + end, 0, size * sizeof(unsigned long)); }
gap_slot = 0; if (gaps && !ma_is_leaf(mt)) { unsigned long max_gap;
max_gap = 0; for (int i = 0; i <= end; i++) if (gaps[i] > max_gap) { gap_slot = i; max_gap = gaps[i]; } }
if (mt == maple_arange_64) ma_set_meta(node, mt, gap_slot, end - 1); else if (end <= max_end - 1) ma_set_meta(node, mt, gap_slot, end - 1);}
static inline void *mtree_range_walk(struct ma_state *mas){ unsigned long *pivots; unsigned char offset; struct maple_node *node; struct maple_enode *next, *last; enum maple_type type; void __rcu **slots; unsigned char end; unsigned long max, min; unsigned long prev_max, prev_min;
next = mas->node; min = mas->min; max = mas->max; do { last = next; node = mte_to_node(next); type = mte_node_type(next); pivots = ma_pivots(node, type); end = ma_data_end(node, type, pivots, max); prev_min = min; prev_max = max; if (pivots[0] >= mas->index) { offset = 0; max = pivots[0]; goto next; }
offset = 1; while (offset < end) { if (pivots[offset] >= mas->index) { max = pivots[offset]; break; } offset++; }
min = pivots[offset - 1] + 1;next: slots = ma_slots(node, type); next = mt_slot(mas->tree, slots, offset); if (unlikely(ma_dead_node(node))) goto dead_node; } while (!ma_is_leaf(type));
mas->end = end; mas->offset = offset; mas->index = min; mas->last = max; mas->min = prev_min; mas->max = prev_max; mas->node = last; return (void *)next;
dead_node: mas_reset(mas); return NULL;}
/* * mas_wmb_replace() - Write memory barrier and replace * @mas: The maple state * @cp: The maple copy node * * Updates gap as necessary. */static inline void mas_wmb_replace(struct ma_state *mas, struct maple_copy *cp){ struct maple_enode *old_enode;
old_enode = mas->node; mas->node = mt_slot_locked(mas->tree, cp->slot, 0); /* Insert the new data in the tree */ mas_topiary_replace(mas, old_enode, cp->height); if (mt_is_alloc(mas->tree) && !mte_is_root(mas->node)) mas_update_gap_known(mas, cp->gap[0]);
mtree_range_walk(mas);}
/* * cp_leaf_init() - Initialize a maple_copy node for the leaf level of a * spanning store * @cp: The maple copy node * @mas: The maple state * @l_wr_mas: The left write state of the spanning store * @r_wr_mas: The right write state of the spanning store */static inline void cp_leaf_init(struct maple_copy *cp, struct ma_state *mas, struct ma_wr_state *l_wr_mas, struct ma_wr_state *r_wr_mas){ unsigned char end = 0;
/* * WARNING: The use of RCU_INIT_POINTER() makes it extremely important * to not expose the maple_copy node to any readers. Exposure may * result in buggy code when a compiler reorders the instructions. */
cp->height = 1; /* Create entries to insert including split entries to left and right */ if (l_wr_mas->r_min < mas->index) { end++; RCU_INIT_POINTER(cp->slot[0], l_wr_mas->content); cp->pivot[0] = mas->index - 1; } RCU_INIT_POINTER(cp->slot[end], l_wr_mas->entry); cp->pivot[end] = mas->last;
if (r_wr_mas->end_piv > mas->last) { end++; RCU_INIT_POINTER(cp->slot[end], r_wr_mas->slots[r_wr_mas->offset_end]); cp->pivot[end] = r_wr_mas->end_piv; }
cp->min = l_wr_mas->r_min; cp->max = cp->pivot[end]; cp->end = end;}
/* * cp_data_calc() - Calculate the size of the data (1 indexed). * @cp: The maple copy struct with the new data populated. * @l_wr_mas: The maple write state containing the data to the left of the write * @r_wr_mas: The maple write state containing the data to the right of the * write * * cp->data is a size (not indexed by 0). */static inline void cp_data_calc(struct maple_copy *cp, struct ma_wr_state *l_wr_mas, struct ma_wr_state *r_wr_mas){
/* Add 1 every time for the 0th element */ cp->data = l_wr_mas->mas->offset; /* Add the new data and any partial overwrites */ cp->data += cp->end + 1; /* Data from right (offset + 1 to end), +1 for zero */ cp->data += r_wr_mas->mas->end - r_wr_mas->offset_end;}
static bool data_fits(struct ma_state *sib, struct ma_state *mas, struct maple_copy *cp){ unsigned char new_data; enum maple_type type; unsigned char space; unsigned char end;
type = mte_node_type(mas->node); space = 2 * mt_slots[type]; end = sib->end;
new_data = end + 1 + cp->data; if (new_data > space) return false;
/* * This is off by one by design. The extra space is left to reduce * jitter in operations that add then remove two entries. * * end is an index while new space and data are both sizes. Adding one * to end to convert the index to a size means that the below * calculation should be <=, but we want to keep an extra space in nodes * to reduce jitter. * * Note that it is still possible to get a full node on the left by the * NULL landing exactly on the split. The NULL ending of a node happens * in the dst_setup() function, where we will either increase the split * by one or decrease it by one, if possible. In the case of split * (this case), it is always possible to shift the spilt by one - again * because there is at least one slot free by the below checking. */ if (new_data < space) return true;
return false;}
static inline void push_data_sib(struct maple_copy *cp, struct ma_state *mas, struct ma_state *sib, struct ma_state *parent){
if (mte_is_root(mas->node)) goto no_push;
*sib = *parent; if (sib->offset) { sib->offset--; mas_descend(sib); sib->end = mas_data_end(sib); if (data_fits(sib, mas, cp)) /* Push left */ return;
*sib = *parent; }
if (sib->offset >= sib->end) goto no_push;
sib->offset++; mas_descend(sib); sib->end = mas_data_end(sib); if (data_fits(sib, mas, cp)) /* Push right*/ return;
no_push: sib->end = 0;}
/* * rebalance_data() - Calculate the @cp data, populate @sib if insufficient or * if the data can be pushed into a sibling. * @cp: The maple copy node * @wr_mas: The left write maple state * @sib: The maple state of the sibling. * * Note: @cp->data is a size and not indexed by 0. @sib->end may be set to 0 to * indicate it will not be used. * */static inline void rebalance_data(struct maple_copy *cp, struct ma_wr_state *wr_mas, struct ma_state *sib, struct ma_state *parent){ cp_data_calc(cp, wr_mas, wr_mas); sib->end = 0; if (cp->data > mt_slots[wr_mas->type]) { push_data_sib(cp, wr_mas->mas, sib, parent); if (sib->end) goto use_sib; } else if (cp->data <= mt_min_slots[wr_mas->type]) { if ((wr_mas->mas->min != 0) || (wr_mas->mas->max != ULONG_MAX)) { rebalance_sib(parent, sib); goto use_sib; } }
return;
use_sib:
cp->data += sib->end + 1;}
/* * spanning_data() - Calculate the @cp data and populate @sib if insufficient * @cp: The maple copy node * @l_wr_mas: The left write maple state * @r_wr_mas: The right write maple state * @sib: The maple state of the sibling. * * Note: @cp->data is a size and not indexed by 0. @sib->end may be set to 0 to * indicate it will not be used. */static inline void spanning_data(struct maple_copy *cp, struct ma_wr_state *l_wr_mas, struct ma_wr_state *r_wr_mas, struct ma_state *sib){ cp_data_calc(cp, l_wr_mas, r_wr_mas); if (((l_wr_mas->mas->min != 0) || (r_wr_mas->mas->max != ULONG_MAX)) && (cp->data <= mt_min_slots[l_wr_mas->type])) { spanning_sib(l_wr_mas, r_wr_mas, sib); cp->data += sib->end + 1; } else { sib->end = 0; }}
/* * dst_setup() - Set up one or more destinations for the new data. * @cp: The maple copy node * @mas: The maple state * @mt: The source node type */static inlinevoid dst_setup(struct maple_copy *cp, struct ma_state *mas, enum maple_type mt){ /* Data is 1 indexed, every src has +1 added. */
if (cp->data <= mt_slots[mt]) { cp->split = cp->data - 1; cp->d_count = 1; goto node_setup; }
cp->split = (cp->data - 1) / 2; cp->d_count = 2; if (cp->data < mt_slots[mt] * 2) goto node_setup;
if (cp->data == mt_slots[mt] * 2) { unsigned char off; unsigned char s;
if (!ma_is_leaf(mt)) goto node_setup;
/* * Leaf nodes are a bit tricky because we cannot assume the data * can fit due to the NULL limitation on node ends. */ off = cp->split; for (s = 0; s < cp->s_count; s++) { unsigned char s_off;
s_off = cp->src[s].end - cp->src[s].start; if (s_off >= off) break;
s_off++; off -= s_off; }
off += cp->src[s].start; if (ma_slots(cp->src[s].node, cp->src[s].mt)[off]) goto node_setup;
cp->split++; if (cp->split < mt_slots[mt]) goto node_setup;
cp->split -= 2; if (cp->data - 2 - cp->split < mt_slots[mt]) goto node_setup;
}
/* No other choice but to 3-way split the data */ cp->split = (cp->data + 2) / 3; cp->d_count = 3;
node_setup: for (int i = 0; i < cp->d_count; i++) { cp->dst[i].mt = mt; cp->dst[i].node = ma_mnode_ptr(mas_pop_node(mas)); }}
static inline void append_mas_cp(struct maple_copy *cp, struct ma_state *mas, unsigned char start, unsigned char end){ struct maple_node *node; enum maple_type mt; unsigned char count;
count = cp->s_count; node = mas_mn(mas); mt = mte_node_type(mas->node); cp->src[count].node = node; cp->src[count].mt = mt; if (mas->end <= end) cp->src[count].max = mas->max; else cp->src[count].max = ma_pivots(node, mt)[end];
cp->src[count].start = start; cp->src[count].end = end; cp->s_count++;}
static inline void append_wr_mas_cp(struct maple_copy *cp, struct ma_wr_state *wr_mas, unsigned char start, unsigned char end){ unsigned char count;
count = cp->s_count; cp->src[count].node = wr_mas->node; cp->src[count].mt = wr_mas->type; if (wr_mas->mas->end <= end) cp->src[count].max = wr_mas->mas->max; else cp->src[count].max = wr_mas->pivots[end];
cp->src[count].start = start; cp->src[count].end = end; cp->s_count++;}
static inline void init_cp_src(struct maple_copy *cp){ cp->src[cp->s_count].node = ma_mnode_ptr(cp); cp->src[cp->s_count].mt = maple_copy; cp->src[cp->s_count].max = cp->max; cp->src[cp->s_count].start = 0; cp->src[cp->s_count].end = cp->end; cp->s_count++;}
/* * multi_src_setup() - Set the @cp node up with multiple sources to copy from. * @cp: The maple copy node * @l_wr_mas: The left write maple state * @r_wr_mas: The right write maple state * @sib: The sibling maple state * * Note: @sib->end == 0 indicates no sibling will be used. */static inlinevoid multi_src_setup(struct maple_copy *cp, struct ma_wr_state *l_wr_mas, struct ma_wr_state *r_wr_mas, struct ma_state *sib){ cp->s_count = 0; if (sib->end && sib->max < l_wr_mas->mas->min) append_mas_cp(cp, sib, 0, sib->end);
/* Copy left 0 - offset */ if (l_wr_mas->mas->offset) { unsigned char off = l_wr_mas->mas->offset - 1;
append_wr_mas_cp(cp, l_wr_mas, 0, off); cp->src[cp->s_count - 1].max = cp->min - 1; }
init_cp_src(cp);
/* Copy right either from offset or offset + 1 pending on r_max */ if (r_wr_mas->mas->end != r_wr_mas->offset_end) append_wr_mas_cp(cp, r_wr_mas, r_wr_mas->offset_end + 1, r_wr_mas->mas->end);
if (sib->end && sib->min > r_wr_mas->mas->max) append_mas_cp(cp, sib, 0, sib->end);}
static inlinevoid cp_data_write(struct maple_copy *cp, struct ma_state *mas){ struct maple_node *dst, *src; unsigned char s, d; unsigned char dst_offset; unsigned char data_offset; unsigned char src_end, s_offset; unsigned char split; unsigned long s_max, d_max; unsigned char dst_size; enum maple_type s_mt, d_mt;
data_offset = 0; s = d = 0; /* Readability help */ src = cp->src[s].node; dst = cp->dst[d].node; s_offset = cp->src[s].start; src_end = cp->src[s].end; split = cp->split; s_max = cp->src[s].max; s_mt = cp->src[s].mt; d_mt = cp->dst[d].mt; do { dst_offset = 0; d_max = 0; dst = cp->dst[d].node; d_mt = cp->dst[d].mt; dst_size = split + 1;
while (dst_size) { unsigned char size;
if (src_end - s_offset + 1 < dst_size) size = src_end - s_offset + 1; else size = dst_size;
d_max = node_copy(mas, src, s_offset, size, s_max, s_mt, dst, dst_offset, d_mt);
dst_offset += size; s_offset += size; if (s_offset > src_end) { /* This source is exhausted */ s++; if (s >= cp->s_count) { cp->dst[d].max = d_max; node_finalise(dst, d_mt, dst_offset); return; } /* Reset local src */ src = cp->src[s].node; s_offset = cp->src[s].start; src_end = cp->src[s].end; s_max = cp->src[s].max; s_mt = cp->src[s].mt; }
dst_size -= size; data_offset += size; }
split = cp->split; cp->dst[d].max = d_max; /* Handle null entries */ if (cp->dst[d].max != ULONG_MAX && !ma_slots(dst, d_mt)[dst_offset - 1]) { if (s_offset == cp->src[s].start) { s--; src = cp->src[s].node; src_end = cp->src[s].end; s_max = cp->src[s].max; s_mt = cp->src[s].mt; s_offset = src_end; } else { s_offset--; } /* Set dst max and clear pivot */ split++; data_offset--; dst_offset--; cp->dst[d].max = ma_pivots(dst, d_mt)[dst_offset - 1]; }
node_finalise(dst, d_mt, dst_offset); ++d; /* Next destination */ if (d == cp->d_count - 1) split = cp->data - data_offset;
if (d >= cp->d_count) { WARN_ON(data_offset < cp->data); return; }
} while (data_offset <= cp->data);}
/* * cp_dst_to_slots() - Migrate the maple copy destination to the maple copy * slots * @cp: The maple copy node * @min: The minimal value represented * @max: The maximum value represented * @mas: The maple state */static inline void cp_dst_to_slots(struct maple_copy *cp, unsigned long min, unsigned long max, struct ma_state *mas){ unsigned char d; unsigned long slot_min = min;
for (d = 0; d < cp->d_count; d++) { struct maple_node *mn = cp->dst[d].node; enum maple_type mt = cp->dst[d].mt; unsigned long slot_max = cp->dst[d].max;
/* * Warning, see cp_leaf_init() comment and rcu_assign_pointer() * documentation. Since these are new nodes, there are no * read-side operations that can view them until they are * inserted into the tree after an rcu_assign_pointer() call. */ ma_init_slot(&cp->slot[d], mn, mt); cp->pivot[d] = slot_max; if (mt_is_alloc(mas->tree)) { if (ma_is_leaf(mt)) { cp->gap[d] = ma_leaf_max_gap(mn, mt, slot_min, slot_max, ma_pivots(mn, mt), ma_slots(mn, mt)); } else { unsigned long *gaps = ma_gaps(mn, mt);
if (gaps) { unsigned char gap_slot;
gap_slot = ma_meta_gap(mn); cp->gap[d] = gaps[gap_slot]; } } } slot_min = slot_max + 1; }
cp->end = cp->d_count - 1; cp->min = min; cp->max = max;}
static inline bool cp_is_new_root(struct maple_copy *cp, struct ma_state *mas){ if (cp->min || cp->max != ULONG_MAX) return false;
if (cp->d_count != 1) { enum maple_type mt = maple_arange_64;
if (!mt_is_alloc(mas->tree)) mt = maple_range_64;
cp->data = cp->d_count; cp->s_count = 0; dst_setup(cp, mas, mt); init_cp_src(cp); node_copy(mas, cp->src[0].node, 0, cp->data, cp->max, maple_copy, cp->dst[0].node, 0, mt); node_finalise(cp->dst[0].node, mt, cp->end + 1); /* * Warning, see cp_leaf_init() comment and rcu_assign_pointer() * documentation. Since this is a new root, there are no * read-side operations that can view it until it is insert into * the tree after an rcu_assign_pointer() call. */ ma_init_slot(&cp->slot[0], cp->dst[0].node, mt); cp->height++; } WARN_ON_ONCE(cp->dst[0].node != mte_to_node( mt_slot_locked(mas->tree, cp->slot, 0))); cp->dst[0].node->parent = ma_parent_ptr(mas_tree_parent(mas)); mas->min = 0; mas->max = ULONG_MAX; mas->depth = 0; mas->node = mas_root_locked(mas); return true;}
static inline bool cp_converged(struct maple_copy *cp, struct ma_state *mas, struct ma_state *sib){ if (cp->d_count != 1 || sib->end) return false;
cp->dst[0].node->parent = ma_parent_ptr(mas_mn(mas)->parent); return true;}
/* * spanning_ascend() - See if a spanning store operation has to keep walking up * the tree * @cp: The maple_copy node * @l_wr_mas: The left maple write state * @r_wr_mas: The right maple write state * @sib: the maple state of the sibling * * Returns: True if another iteration is necessary. */static bool spanning_ascend(struct maple_copy *cp, struct ma_state *mas, struct ma_wr_state *l_wr_mas, struct ma_wr_state *r_wr_mas, struct ma_state *sib){ if (sib->end) { if (sib->max < l_wr_mas->mas->min) *l_wr_mas->mas = *sib; else *r_wr_mas->mas = *sib; }
cp_dst_to_slots(cp, l_wr_mas->mas->min, r_wr_mas->mas->max, mas); if (cp_is_new_root(cp, mas)) return false;
/* Converged and has a single destination */ if ((cp->d_count == 1) && (l_wr_mas->mas->node == r_wr_mas->mas->node)) { cp->dst[0].node->parent = ma_parent_ptr(mas_mn(mas)->parent); return false; }
cp->height++; wr_mas_ascend(l_wr_mas); wr_mas_ascend(r_wr_mas); return true;}
static inlinevoid copy_tree_location(const struct ma_state *src, struct ma_state *dst){ dst->node = src->node; dst->offset = src->offset; dst->min = src->min; dst->max = src->max; dst->end = src->end; dst->depth = src->depth;}
/* * rebalance_ascend() - Ascend the tree and set up for the next loop - if * necessary * * Return: True if there another rebalancing operation on the next level is * needed, false otherwise. */static inline bool rebalance_ascend(struct maple_copy *cp, struct ma_wr_state *wr_mas, struct ma_state *sib, struct ma_state *parent){ struct ma_state *mas; unsigned long min, max;
mas = wr_mas->mas; if (!sib->end) { min = mas->min; max = mas->max; } else if (sib->min > mas->max) { /* Move right succeeded */ min = mas->min; max = sib->max; wr_mas->offset_end = parent->offset + 1; } else { min = sib->min; max = mas->max; wr_mas->offset_end = parent->offset; parent->offset--; }
cp_dst_to_slots(cp, min, max, mas); if (cp_is_new_root(cp, mas)) return false;
if (cp_converged(cp, mas, sib)) return false;
cp->height++; copy_tree_location(parent, mas); wr_mas_setup(wr_mas, mas); return true;}
/* * mas_root_expand() - Expand a root to a node * @mas: The maple state * @entry: The entry to store into the tree */static inline void mas_root_expand(struct ma_state *mas, void *entry){ void *contents = mas_root_locked(mas); enum maple_type type = maple_leaf_64; struct maple_node *node; void __rcu **slots; unsigned long *pivots; int slot = 0;
node = mas_pop_node(mas); pivots = ma_pivots(node, type); slots = ma_slots(node, type); node->parent = ma_parent_ptr(mas_tree_parent(mas)); mas->node = mt_mk_node(node, type); mas->status = ma_active;
if (mas->index) { if (contents) { rcu_assign_pointer(slots[slot], contents); if (likely(mas->index > 1)) slot++; } pivots[slot++] = mas->index - 1; }
rcu_assign_pointer(slots[slot], entry); mas->offset = slot; pivots[slot] = mas->last; if (mas->last != ULONG_MAX) pivots[++slot] = ULONG_MAX;
mt_set_height(mas->tree, 1); ma_set_meta(node, maple_leaf_64, 0, slot); /* swap the new root into the tree */ rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node));}
/* * mas_store_root() - Storing value into root. * @mas: The maple state * @entry: The entry to store. * * There is no root node now and we are storing a value into the root - this * function either assigns the pointer or expands into a node. */static inline void mas_store_root(struct ma_state *mas, void *entry){ if (!entry) { if (!mas->index) rcu_assign_pointer(mas->tree->ma_root, NULL); } else if (likely((mas->last != 0) || (mas->index != 0))) mas_root_expand(mas, entry); else if (((unsigned long) (entry) & 3) == 2) mas_root_expand(mas, entry); else { rcu_assign_pointer(mas->tree->ma_root, entry); mas->status = ma_start; }}
/* * mas_is_span_wr() - Check if the write needs to be treated as a write that * spans the node. * @wr_mas: The maple write state * * Spanning writes are writes that start in one node and end in another OR if * the write of a %NULL will cause the node to end with a %NULL. * * Return: True if this is a spanning write, false otherwise. */static bool mas_is_span_wr(struct ma_wr_state *wr_mas){ unsigned long max = wr_mas->r_max; unsigned long last = wr_mas->mas->last; enum maple_type type = wr_mas->type; void *entry = wr_mas->entry;
/* Contained in this pivot, fast path */ if (last < max) return false;
if (ma_is_leaf(type)) { max = wr_mas->mas->max; if (last < max) return false; }
if (last == max) { /* * The last entry of leaf node cannot be NULL unless it is the * rightmost node (writing ULONG_MAX), otherwise it spans slots. */ if (entry || last == ULONG_MAX) return false; }
trace_ma_write(TP_FCT, wr_mas->mas, wr_mas->r_max, entry); return true;}
static inline void mas_wr_walk_descend(struct ma_wr_state *wr_mas){ wr_mas->type = mte_node_type(wr_mas->mas->node); mas_wr_node_walk(wr_mas); wr_mas->slots = ma_slots(wr_mas->node, wr_mas->type);}
static inline void mas_wr_walk_traverse(struct ma_wr_state *wr_mas){ wr_mas->mas->max = wr_mas->r_max; wr_mas->mas->min = wr_mas->r_min; wr_mas->mas->node = wr_mas->content; wr_mas->mas->offset = 0; wr_mas->mas->depth++;}/* * mas_wr_walk() - Walk the tree for a write. * @wr_mas: The maple write state * * Uses mas_slot_locked() and does not need to worry about dead nodes. * * Return: True if it's contained in a node, false on spanning write. */static bool mas_wr_walk(struct ma_wr_state *wr_mas){ struct ma_state *mas = wr_mas->mas;
while (true) { mas_wr_walk_descend(wr_mas); if (unlikely(mas_is_span_wr(wr_mas))) return false;
wr_mas->content = mas_slot_locked(mas, wr_mas->slots, mas->offset); if (ma_is_leaf(wr_mas->type)) return true;
if (mas->end < mt_slots[wr_mas->type] - 1) wr_mas->vacant_height = mas->depth + 1;
if (ma_is_root(mas_mn(mas))) { /* root needs more than 2 entries to be sufficient + 1 */ if (mas->end > 2) wr_mas->sufficient_height = 1; } else if (mas->end > mt_min_slots[wr_mas->type] + 1) wr_mas->sufficient_height = mas->depth + 1;
mas_wr_walk_traverse(wr_mas); }
return true;}
static void mas_wr_walk_index(struct ma_wr_state *wr_mas){ struct ma_state *mas = wr_mas->mas;
while (true) { mas_wr_walk_descend(wr_mas); wr_mas->content = mas_slot_locked(mas, wr_mas->slots, mas->offset); if (ma_is_leaf(wr_mas->type)) return; mas_wr_walk_traverse(wr_mas); }}/* * mas_extend_spanning_null() - Extend a store of a %NULL to include surrounding %NULLs. * @l_wr_mas: The left maple write state * @r_wr_mas: The right maple write state */static inline void mas_extend_spanning_null(struct ma_wr_state *l_wr_mas, struct ma_wr_state *r_wr_mas){ struct ma_state *r_mas = r_wr_mas->mas; struct ma_state *l_mas = l_wr_mas->mas; unsigned char l_slot;
l_slot = l_mas->offset; if (!l_wr_mas->content) l_mas->index = l_wr_mas->r_min;
if ((l_mas->index == l_wr_mas->r_min) && (l_slot && !mas_slot_locked(l_mas, l_wr_mas->slots, l_slot - 1))) { if (l_slot > 1) l_mas->index = l_wr_mas->pivots[l_slot - 2] + 1; else l_mas->index = l_mas->min;
l_mas->offset = l_slot - 1; l_wr_mas->r_min = l_mas->index; }
if (!r_wr_mas->content) { if (r_mas->last < r_wr_mas->r_max) r_mas->last = r_wr_mas->r_max; r_mas->offset++; }}
static inline void *mas_state_walk(struct ma_state *mas){ void *entry;
entry = mas_start(mas); if (mas_is_none(mas)) return NULL;
if (mas_is_ptr(mas)) return entry;
return mtree_range_walk(mas);}
/* * mtree_lookup_walk() - Internal quick lookup that does not keep maple state up * to date. * * @mas: The maple state. * * Note: Leaves mas in undesirable state. * Return: The entry for @mas->index or %NULL on dead node. */static inline void *mtree_lookup_walk(struct ma_state *mas){ unsigned long *pivots; unsigned char offset; struct maple_node *node; struct maple_enode *next; enum maple_type type; void __rcu **slots; unsigned char end;
next = mas->node; do { node = mte_to_node(next); type = mte_node_type(next); pivots = ma_pivots(node, type); end = mt_pivots[type]; offset = 0; do { if (pivots[offset] >= mas->index) break; } while (++offset < end);
slots = ma_slots(node, type); next = mt_slot(mas->tree, slots, offset); if (unlikely(ma_dead_node(node))) goto dead_node; } while (!ma_is_leaf(type));
return (void *)next;
dead_node: mas_reset(mas); return NULL;}
static void mte_destroy_walk(struct maple_enode *, struct maple_tree *);/* * mas_new_root() - Create a new root node that only contains the entry passed * in. * @mas: The maple state * @entry: The entry to store. * * Only valid when the index == 0 and the last == ULONG_MAX */static inline void mas_new_root(struct ma_state *mas, void *entry){ struct maple_enode *root = mas_root_locked(mas); enum maple_type type = maple_leaf_64; struct maple_node *node; void __rcu **slots; unsigned long *pivots;
WARN_ON_ONCE(mas->index || mas->last != ULONG_MAX);
if (!entry) { mt_set_height(mas->tree, 0); rcu_assign_pointer(mas->tree->ma_root, entry); mas->status = ma_start; goto done; }
node = mas_pop_node(mas); pivots = ma_pivots(node, type); slots = ma_slots(node, type); node->parent = ma_parent_ptr(mas_tree_parent(mas)); mas->node = mt_mk_node(node, type); mas->status = ma_active; rcu_assign_pointer(slots[0], entry); pivots[0] = mas->last; mt_set_height(mas->tree, 1); rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node));
done: if (xa_is_node(root)) mte_destroy_walk(root, mas->tree);}/* * mas_wr_spanning_store() - Create a subtree with the store operation completed * and new nodes where necessary, then place the sub-tree in the actual tree. * Note that mas is expected to point to the node which caused the store to * span. * @wr_mas: The maple write state */static void mas_wr_spanning_store(struct ma_wr_state *wr_mas){ struct maple_copy cp; struct ma_state *mas; struct ma_state sib;
/* Left and Right side of spanning store */ MA_STATE(r_mas, NULL, 0, 0); MA_WR_STATE(r_wr_mas, &r_mas, wr_mas->entry);
/* * A store operation that spans multiple nodes is called a spanning * store and is handled early in the store call stack by the function * mas_is_span_wr(). When a spanning store is identified, the maple * state is duplicated. The first maple state walks the left tree path * to ``index``, the duplicate walks the right tree path to ``last``. * The data in the two nodes are combined into a single node, two nodes, * or possibly three nodes (see the 3-way split above). A ``NULL`` * written to the last entry of a node is considered a spanning store as * a rebalance is required for the operation to complete and an overflow * of data may happen. */ mas = wr_mas->mas; trace_ma_op(TP_FCT, mas);
if (unlikely(!mas->index && mas->last == ULONG_MAX)) return mas_new_root(mas, wr_mas->entry); /* * Node rebalancing may occur due to this store, so there may be three new * entries per level plus a new root. */
/* * Set up right side. Need to get to the next offset after the spanning * store to ensure it's not NULL and to combine both the next node and * the node with the start together. */ r_mas = *mas; /* Avoid overflow, walk to next slot in the tree. */ if (r_mas.last + 1) r_mas.last++;
r_mas.index = r_mas.last; mas_wr_walk_index(&r_wr_mas); r_mas.last = r_mas.index = mas->last; r_wr_mas.end_piv = r_wr_mas.r_max;
/* Set up left side. */ mas_wr_walk_index(wr_mas);
if (!wr_mas->entry) { mas_extend_spanning_null(wr_mas, &r_wr_mas); mas->last = r_mas.last; }
/* expanding NULLs may make this cover the entire range */ if (!mas->index && r_mas.last == ULONG_MAX) { mas_set_range(mas, 0, ULONG_MAX); return mas_new_root(mas, wr_mas->entry); }
cp_leaf_init(&cp, mas, wr_mas, &r_wr_mas); do { spanning_data(&cp, wr_mas, &r_wr_mas, &sib); multi_src_setup(&cp, wr_mas, &r_wr_mas, &sib); dst_setup(&cp, mas, wr_mas->type); cp_data_write(&cp, mas); } while (spanning_ascend(&cp, mas, wr_mas, &r_wr_mas, &sib));
mas_wmb_replace(mas, &cp);}
/* * mas_wr_node_store() - Attempt to store the value in a node * @wr_mas: The maple write state * * Attempts to reuse the node, but may allocate. */static inline void mas_wr_node_store(struct ma_wr_state *wr_mas){ unsigned char dst_offset, offset_end; unsigned char copy_size, node_pivots, node_slots; struct maple_node reuse, *newnode; unsigned long *dst_pivots; void __rcu **dst_slots; unsigned char new_end; struct ma_state *mas; bool in_rcu;
mas = wr_mas->mas; trace_ma_op(TP_FCT, mas); in_rcu = mt_in_rcu(mas->tree); offset_end = wr_mas->offset_end; node_pivots = mt_pivots[wr_mas->type]; node_slots = mt_slots[wr_mas->type]; /* Assume last adds an entry */ new_end = mas->end + 1 - offset_end + mas->offset; if (mas->last == wr_mas->end_piv) { offset_end++; /* don't copy this offset */ new_end--; }
/* set up node. */ if (in_rcu) { newnode = mas_pop_node(mas); } else { newnode = &reuse; }
newnode->parent = mas_mn(mas)->parent; dst_pivots = ma_pivots(newnode, wr_mas->type); dst_slots = ma_slots(newnode, wr_mas->type); /* Copy from start to insert point */ if (mas->offset) { memcpy(dst_pivots, wr_mas->pivots, sizeof(unsigned long) * mas->offset); memcpy(dst_slots, wr_mas->slots, sizeof(void __rcu *) * mas->offset); }
/* Handle insert of new range starting after old range */ if (wr_mas->r_min < mas->index) { rcu_assign_pointer(dst_slots[mas->offset], wr_mas->content); dst_pivots[mas->offset++] = mas->index - 1; new_end++; }
/* Store the new entry and range end. */ if (mas->offset < node_pivots) dst_pivots[mas->offset] = mas->last; rcu_assign_pointer(dst_slots[mas->offset], wr_mas->entry);
/* * this range wrote to the end of the node or it overwrote the rest of * the data */ if (offset_end > mas->end) goto done;
dst_offset = mas->offset + 1; /* Copy to the end of node if necessary. */ copy_size = mas->end - offset_end + 1; memcpy(dst_slots + dst_offset, wr_mas->slots + offset_end, sizeof(void __rcu *) * copy_size); memcpy(dst_pivots + dst_offset, wr_mas->pivots + offset_end, sizeof(unsigned long) * (copy_size - 1));
if (new_end < node_pivots) dst_pivots[new_end] = mas->max;
done: if (!in_rcu && new_end + 2 < node_slots) { unsigned char clear_from = new_end + 1;
/* * Note that the last slot is never cleared, since the metadata * will be stored there or it has a value. */ memset(dst_slots + clear_from, 0, sizeof(void __rcu *) * (node_slots - clear_from)); if (clear_from < node_pivots) memset(dst_pivots + clear_from, 0, sizeof(unsigned long) * (node_pivots - clear_from)); }
mas_leaf_set_meta(newnode, wr_mas->type, new_end); if (in_rcu) { struct maple_enode *old_enode = mas->node;
mas->node = mt_mk_node(newnode, wr_mas->type); mas_replace_node(mas, old_enode, mas_mt_height(mas)); } else { memcpy(wr_mas->node, newnode, sizeof(struct maple_node)); } trace_ma_write(TP_FCT, mas, 0, wr_mas->entry); mas_update_gap(mas); mas->end = new_end;}
/* * mas_wr_slot_store: Attempt to store a value in a slot. * @wr_mas: the maple write state */static inline void mas_wr_slot_store(struct ma_wr_state *wr_mas){ struct ma_state *mas = wr_mas->mas; unsigned char offset = mas->offset; void __rcu **slots = wr_mas->slots; bool gap = false;
gap |= !wr_mas->content; gap |= !mt_slot_locked(mas->tree, slots, offset + 1);
if (wr_mas->offset_end - offset == 1) { if (mas->index == wr_mas->r_min) { /* Overwriting the range and a part of the next one */ rcu_assign_pointer(slots[offset], wr_mas->entry); wr_mas->pivots[offset] = mas->last; } else { /* Overwriting a part of the range and the next one */ rcu_assign_pointer(slots[offset + 1], wr_mas->entry); wr_mas->pivots[offset] = mas->index - 1; mas->offset++; /* Keep mas accurate. */ } } else { WARN_ON_ONCE(mt_in_rcu(mas->tree)); /* * Expand the range, only partially overwriting the previous and * next ranges */ gap |= !mt_slot_locked(mas->tree, slots, offset + 2); rcu_assign_pointer(slots[offset + 1], wr_mas->entry); wr_mas->pivots[offset] = mas->index - 1; wr_mas->pivots[offset + 1] = mas->last; mas->offset++; /* Keep mas accurate. */ }
trace_ma_write(TP_FCT, mas, 0, wr_mas->entry); /* * Only update gap when the new entry is empty or there is an empty * entry in the original two ranges. */ if (!wr_mas->entry || gap) mas_update_gap(mas);}
static inline void mas_wr_extend_null(struct ma_wr_state *wr_mas){ struct ma_state *mas = wr_mas->mas;
if (!wr_mas->slots[wr_mas->offset_end]) { /* If this one is null, the next and prev are not */ mas->last = wr_mas->end_piv; } else { /* Check next slot(s) if we are overwriting the end */ if ((mas->last == wr_mas->end_piv) && (mas->end != wr_mas->offset_end) && !wr_mas->slots[wr_mas->offset_end + 1]) { wr_mas->offset_end++; if (wr_mas->offset_end == mas->end) mas->last = mas->max; else mas->last = wr_mas->pivots[wr_mas->offset_end]; wr_mas->end_piv = mas->last; } }
if (!wr_mas->content) { /* If this one is null, the next and prev are not */ mas->index = wr_mas->r_min; } else { /* Check prev slot if we are overwriting the start */ if (mas->index == wr_mas->r_min && mas->offset && !wr_mas->slots[mas->offset - 1]) { mas->offset--; wr_mas->r_min = mas->index = mas_safe_min(mas, wr_mas->pivots, mas->offset); wr_mas->r_max = wr_mas->pivots[mas->offset]; } }}
static inline void mas_wr_end_piv(struct ma_wr_state *wr_mas){ while ((wr_mas->offset_end < wr_mas->mas->end) && (wr_mas->mas->last > wr_mas->pivots[wr_mas->offset_end])) wr_mas->offset_end++;
if (wr_mas->offset_end < wr_mas->mas->end) wr_mas->end_piv = wr_mas->pivots[wr_mas->offset_end]; else wr_mas->end_piv = wr_mas->mas->max;}
static inline unsigned char mas_wr_new_end(struct ma_wr_state *wr_mas){ struct ma_state *mas = wr_mas->mas; unsigned char new_end = mas->end + 2;
new_end -= wr_mas->offset_end - mas->offset; if (wr_mas->r_min == mas->index) new_end--;
if (wr_mas->end_piv == mas->last) new_end--;
return new_end;}
/* * mas_wr_append: Attempt to append * @wr_mas: the maple write state * * This is currently unsafe in rcu mode since the end of the node may be cached * by readers while the node contents may be updated which could result in * inaccurate information. */static inline void mas_wr_append(struct ma_wr_state *wr_mas){ struct ma_state *mas = wr_mas->mas; void __rcu **slots; unsigned char end = mas->end; unsigned char new_end = mas_wr_new_end(wr_mas);
if (new_end < mt_pivots[wr_mas->type]) { wr_mas->pivots[new_end] = wr_mas->pivots[end]; ma_set_meta(wr_mas->node, wr_mas->type, 0, new_end); }
slots = wr_mas->slots; if (new_end == end + 1) { if (mas->last == wr_mas->r_max) { /* Append to end of range */ rcu_assign_pointer(slots[new_end], wr_mas->entry); wr_mas->pivots[end] = mas->index - 1; mas->offset = new_end; } else { /* Append to start of range */ rcu_assign_pointer(slots[new_end], wr_mas->content); wr_mas->pivots[end] = mas->last; rcu_assign_pointer(slots[end], wr_mas->entry); } } else { /* Append to the range without touching any boundaries. */ rcu_assign_pointer(slots[new_end], wr_mas->content); wr_mas->pivots[end + 1] = mas->last; rcu_assign_pointer(slots[end + 1], wr_mas->entry); wr_mas->pivots[end] = mas->index - 1; mas->offset = end + 1; }
if (!wr_mas->content || !wr_mas->entry) mas_update_gap(mas);
mas->end = new_end; trace_ma_write(TP_FCT, mas, new_end, wr_mas->entry);}
/* * split_ascend() - See if a split operation has to keep walking up the tree * @cp: The maple_copy node * @wr_mas: The maple write state * @sib: the maple state of the sibling * * Return: true if another split operation on the next level is needed, false * otherwise */static inline bool split_ascend(struct maple_copy *cp, struct ma_wr_state *wr_mas, struct ma_state *sib, struct ma_state *parent){ struct ma_state *mas; unsigned long min, max;
mas = wr_mas->mas; min = mas->min; /* push right, or normal split */ max = mas->max; wr_mas->offset_end = parent->offset; if (sib->end) { if (sib->max < mas->min) { min = sib->min; /* push left */ parent->offset--; } else { max = sib->max; /* push right */ wr_mas->offset_end++; } }
cp_dst_to_slots(cp, min, max, mas); if (cp_is_new_root(cp, mas)) return false;
if (cp_converged(cp, mas, sib)) return false;
cp->height++; copy_tree_location(parent, mas); wr_mas_setup(wr_mas, mas); return true;}
/* * split_data() - Calculate the @cp data, populate @sib if the data can be * pushed into a sibling. * @cp: The maple copy node * @wr_mas: The left write maple state * @sib: The maple state of the sibling. * * Note: @cp->data is a size and not indexed by 0. @sib->end may be set to 0 to * indicate it will not be used. * */static inline void split_data(struct maple_copy *cp, struct ma_wr_state *wr_mas, struct ma_state *sib, struct ma_state *parent){ cp_data_calc(cp, wr_mas, wr_mas); if (cp->data <= mt_slots[wr_mas->type]) { sib->end = 0; return; }
push_data_sib(cp, wr_mas->mas, sib, parent); if (sib->end) cp->data += sib->end + 1;}
/* * mas_wr_split() - Expand one node into two * @wr_mas: The write maple state */static void mas_wr_split(struct ma_wr_state *wr_mas){ struct ma_state parent; struct ma_state *mas; struct maple_copy cp; struct ma_state sib;
mas = wr_mas->mas; trace_ma_write(TP_FCT, wr_mas->mas, 0, wr_mas->entry); parent = *mas; cp_leaf_init(&cp, mas, wr_mas, wr_mas); do { if (!mte_is_root(parent.node)) { mas_ascend(&parent); parent.end = mas_data_end(&parent); } split_data(&cp, wr_mas, &sib, &parent); multi_src_setup(&cp, wr_mas, wr_mas, &sib); dst_setup(&cp, mas, wr_mas->type); cp_data_write(&cp, mas); } while (split_ascend(&cp, wr_mas, &sib, &parent));
mas_wmb_replace(mas, &cp);}
/* * mas_wr_rebalance() - Insufficient data in one node needs to either get data * from a sibling or absorb a sibling all together. * @wr_mas: The write maple state * * Rebalance is different than a spanning store in that the write state is * already at the leaf node that's being altered. */static void mas_wr_rebalance(struct ma_wr_state *wr_mas){ struct ma_state parent; struct ma_state *mas; struct maple_copy cp; struct ma_state sib;
/* * Rebalancing occurs if a node is insufficient. Data is rebalanced * against the node to the right if it exists, otherwise the node to the * left of this node is rebalanced against this node. If rebalancing * causes just one node to be produced instead of two, then the parent * is also examined and rebalanced if it is insufficient. Every level * tries to combine the data in the same way. If one node contains the * entire range of the tree, then that node is used as a new root node. */
mas = wr_mas->mas; trace_ma_op(TP_FCT, mas); parent = *mas; cp_leaf_init(&cp, mas, wr_mas, wr_mas); do { if (!mte_is_root(parent.node)) { mas_ascend(&parent); parent.end = mas_data_end(&parent); } rebalance_data(&cp, wr_mas, &sib, &parent); multi_src_setup(&cp, wr_mas, wr_mas, &sib); dst_setup(&cp, mas, wr_mas->type); cp_data_write(&cp, mas); } while (rebalance_ascend(&cp, wr_mas, &sib, &parent));
mas_wmb_replace(mas, &cp);}
/* * mas_wr_store_entry() - Internal call to store a value * @wr_mas: The maple write state */static inline void mas_wr_store_entry(struct ma_wr_state *wr_mas){ struct ma_state *mas = wr_mas->mas;
switch (mas->store_type) { case wr_exact_fit: rcu_assign_pointer(wr_mas->slots[mas->offset], wr_mas->entry); if (!!wr_mas->entry ^ !!wr_mas->content) mas_update_gap(mas); break; case wr_append: mas_wr_append(wr_mas); break; case wr_slot_store: mas_wr_slot_store(wr_mas); break; case wr_node_store: mas_wr_node_store(wr_mas); break; case wr_spanning_store: mas_wr_spanning_store(wr_mas); break; case wr_split_store: mas_wr_split(wr_mas); break; case wr_rebalance: mas_wr_rebalance(wr_mas); break; case wr_new_root: mas_new_root(mas, wr_mas->entry); break; case wr_store_root: mas_store_root(mas, wr_mas->entry); break; case wr_invalid: MT_BUG_ON(mas->tree, 1); }}
static inline void mas_wr_prealloc_setup(struct ma_wr_state *wr_mas){ struct ma_state *mas = wr_mas->mas;
if (!mas_is_active(mas)) { if (mas_is_start(mas)) goto set_content;
if (unlikely(mas_is_paused(mas))) goto reset;
if (unlikely(mas_is_none(mas))) goto reset;
if (unlikely(mas_is_overflow(mas))) goto reset;
if (unlikely(mas_is_underflow(mas))) goto reset; }
/* * A less strict version of mas_is_span_wr() where we allow spanning * writes within this node. This is to stop partial walks in * mas_prealloc() from being reset. */ if (mas->last > mas->max) goto reset;
if (wr_mas->entry) goto set_content;
if (mte_is_leaf(mas->node) && mas->last == mas->max) goto reset;
goto set_content;
reset: mas_reset(mas);set_content: wr_mas->content = mas_start(mas);}
/** * mas_prealloc_calc() - Calculate number of nodes needed for a * given store operation * @wr_mas: The maple write state * @entry: The entry to store into the tree * * Return: Number of nodes required for preallocation. */static inline void mas_prealloc_calc(struct ma_wr_state *wr_mas, void *entry){ struct ma_state *mas = wr_mas->mas; unsigned char height = mas_mt_height(mas); int ret = height * 3 + 1; unsigned char delta = height - wr_mas->vacant_height;
switch (mas->store_type) { case wr_exact_fit: case wr_append: case wr_slot_store: ret = 0; break; case wr_spanning_store: if (wr_mas->sufficient_height < wr_mas->vacant_height) ret = (height - wr_mas->sufficient_height) * 3 + 1; else ret = delta * 3 + 1; break; case wr_split_store: ret = delta * 2 + 1; break; case wr_rebalance: if (wr_mas->sufficient_height < wr_mas->vacant_height) ret = (height - wr_mas->sufficient_height) * 2 + 1; else ret = delta * 2 + 1; break; case wr_node_store: ret = mt_in_rcu(mas->tree) ? 1 : 0; break; case wr_new_root: ret = 1; break; case wr_store_root: if (likely((mas->last != 0) || (mas->index != 0))) ret = 1; else if (((unsigned long) (entry) & 3) == 2) ret = 1; else ret = 0; break; case wr_invalid: WARN_ON_ONCE(1); }
mas->node_request = ret;}
/* * mas_wr_store_type() - Determine the store type for a given * store operation. * @wr_mas: The maple write state * * Return: the type of store needed for the operation */static inline enum store_type mas_wr_store_type(struct ma_wr_state *wr_mas){ struct ma_state *mas = wr_mas->mas; unsigned char new_end; bool appending; bool one_slot; bool in_rcu;
if (unlikely(mas_is_none(mas) || mas_is_ptr(mas))) return wr_store_root;
if (unlikely(!mas_wr_walk(wr_mas))) return wr_spanning_store;
/* At this point, we are at the leaf node that needs to be altered. */ mas_wr_end_piv(wr_mas); if (!wr_mas->entry) mas_wr_extend_null(wr_mas);
if ((wr_mas->r_min == mas->index) && (wr_mas->r_max == mas->last)) return wr_exact_fit;
if (unlikely(!mas->index && mas->last == ULONG_MAX)) return wr_new_root;
new_end = mas_wr_new_end(wr_mas); in_rcu = mt_in_rcu(mas->tree); appending = mas->offset == mas->end; one_slot = wr_mas->offset_end - mas->offset == 1;
/* Potential spanning rebalance collapsing a node */ if (new_end < mt_min_slots[wr_mas->type]) { if (!mte_is_root(mas->node)) return wr_rebalance; if (!in_rcu) { if (appending) return wr_append; else if (mas->end == new_end && one_slot) return wr_slot_store; } return wr_node_store; }
if (new_end >= mt_slots[wr_mas->type]) return wr_split_store;
if (!in_rcu && appending) return wr_append;
if (new_end == mas->end && (!in_rcu || one_slot)) return wr_slot_store;
return wr_node_store;}
/** * mas_wr_preallocate() - Preallocate enough nodes for a store operation * @wr_mas: The maple write state * @entry: The entry that will be stored * */static inline void mas_wr_preallocate(struct ma_wr_state *wr_mas, void *entry){ struct ma_state *mas = wr_mas->mas;
mas_wr_prealloc_setup(wr_mas); mas->store_type = mas_wr_store_type(wr_mas); mas_prealloc_calc(wr_mas, entry); if (!mas->node_request) return;
mas_alloc_nodes(mas, GFP_NOWAIT);}
/** * mas_insert() - Internal call to insert a value * @mas: The maple state * @entry: The entry to store * * Return: %NULL or the contents that already exists at the requested index * otherwise. The maple state needs to be checked for error conditions. */static inline void *mas_insert(struct ma_state *mas, void *entry){ MA_WR_STATE(wr_mas, mas, entry);
/* * Inserting a new range inserts either 0, 1, or 2 pivots within the * tree. If the insert fits exactly into an existing gap with a value * of NULL, then the slot only needs to be written with the new value. * If the range being inserted is adjacent to another range, then only a * single pivot needs to be inserted (as well as writing the entry). If * the new range is within a gap but does not touch any other ranges, * then two pivots need to be inserted: the start - 1, and the end. As * usual, the entry must be written. Most operations require a new node * to be allocated and replace an existing node to ensure RCU safety, * when in RCU mode. The exception to requiring a newly allocated node * is when inserting at the end of a node (appending). When done * carefully, appending can reuse the node in place. */ wr_mas.content = mas_start(mas); if (wr_mas.content) goto exists;
mas_wr_preallocate(&wr_mas, entry); if (mas_is_err(mas)) return NULL;
/* spanning writes always overwrite something */ if (mas->store_type == wr_spanning_store) goto exists;
/* At this point, we are at the leaf node that needs to be altered. */ if (mas->store_type != wr_new_root && mas->store_type != wr_store_root) { wr_mas.offset_end = mas->offset; wr_mas.end_piv = wr_mas.r_max;
if (wr_mas.content || (mas->last > wr_mas.r_max)) goto exists; }
mas_wr_store_entry(&wr_mas); return wr_mas.content;
exists: mas_set_err(mas, -EEXIST); return wr_mas.content;
}
/** * mas_alloc_cyclic() - Internal call to find somewhere to store an entry * @mas: The maple state. * @startp: Pointer to ID. * @range_lo: Lower bound of range to search. * @range_hi: Upper bound of range to search. * @entry: The entry to store. * @next: Pointer to next ID to allocate. * @gfp: The GFP_FLAGS to use for allocations. * * Return: 0 if the allocation succeeded without wrapping, 1 if the * allocation succeeded after wrapping, or -EBUSY if there are no * free entries. */int mas_alloc_cyclic(struct ma_state *mas, unsigned long *startp, void *entry, unsigned long range_lo, unsigned long range_hi, unsigned long *next, gfp_t gfp){ int ret; unsigned long min;
min = range_lo; do { range_lo = max(min, *next); ret = mas_empty_area(mas, range_lo, range_hi, 1); if (ret < 0 && range_lo > min) { mas_reset(mas); ret = mas_empty_area(mas, min, range_hi, 1); if (ret == 0) ret = 1; } if (ret < 0) goto out;
mas_insert(mas, entry); } while (mas_nomem(mas, gfp));
if (mas_is_err(mas)) { ret = xa_err(mas->node); goto out; }
if ((mas->tree->ma_flags & MT_FLAGS_ALLOC_WRAPPED) && ret == 0) { mas->tree->ma_flags &= ~MT_FLAGS_ALLOC_WRAPPED; ret = 1; } *startp = mas->index; *next = *startp + 1; if (*next == 0) mas->tree->ma_flags |= MT_FLAGS_ALLOC_WRAPPED;
out: mas_destroy(mas); return ret;}EXPORT_SYMBOL(mas_alloc_cyclic);
static __always_inline void mas_rewalk(struct ma_state *mas, unsigned long index){retry: mas_set(mas, index); mas_state_walk(mas); if (mas_is_start(mas)) goto retry;}
static __always_inline bool mas_rewalk_if_dead(struct ma_state *mas, struct maple_node *node, const unsigned long index){ if (unlikely(ma_dead_node(node))) { mas_rewalk(mas, index); return true; } return false;}
/* * mas_prev_node() - Find the prev non-null entry at the same level in the * tree. The prev value will be mas->node[mas->offset] or the status will be * ma_none. * @mas: The maple state * @min: The lower limit to search * * The prev node value will be mas->node[mas->offset] or the status will be * ma_none. * Return: 1 if the node is dead, 0 otherwise. */static int mas_prev_node(struct ma_state *mas, unsigned long min){ enum maple_type mt; int offset, level; void __rcu **slots; struct maple_node *node; unsigned long *pivots; unsigned long max;
node = mas_mn(mas); if (!mas->min) goto no_entry;
max = mas->min - 1; if (max < min) goto no_entry;
level = 0; do { if (ma_is_root(node)) goto no_entry;
/* Walk up. */ if (unlikely(mas_ascend(mas))) return 1; offset = mas->offset; level++; node = mas_mn(mas); } while (!offset);
offset--; mt = mte_node_type(mas->node); while (level > 1) { level--; slots = ma_slots(node, mt); mas->node = mas_slot(mas, slots, offset); if (unlikely(ma_dead_node(node))) return 1;
mt = mte_node_type(mas->node); node = mas_mn(mas); pivots = ma_pivots(node, mt); offset = ma_data_end(node, mt, pivots, max); if (unlikely(ma_dead_node(node))) return 1; }
slots = ma_slots(node, mt); mas->node = mas_slot(mas, slots, offset); pivots = ma_pivots(node, mt); if (unlikely(ma_dead_node(node))) return 1;
if (likely(offset)) mas->min = pivots[offset - 1] + 1; mas->max = max; mas->offset = mas_data_end(mas); if (unlikely(mte_dead_node(mas->node))) return 1;
mas->end = mas->offset; return 0;
no_entry: if (unlikely(ma_dead_node(node))) return 1;
mas->status = ma_underflow; return 0;}
/* * mas_prev_slot() - Get the entry in the previous slot * * @mas: The maple state * @min: The minimum starting range * @empty: Can be empty * * Return: The entry in the previous slot which is possibly NULL */static void *mas_prev_slot(struct ma_state *mas, unsigned long min, bool empty){ void *entry; void __rcu **slots; unsigned long pivot; enum maple_type type; unsigned long *pivots; struct maple_node *node; unsigned long save_point = mas->index;
retry: node = mas_mn(mas); type = mte_node_type(mas->node); pivots = ma_pivots(node, type); if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) goto retry;
if (mas->min <= min) { pivot = mas_safe_min(mas, pivots, mas->offset);
if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) goto retry;
if (pivot <= min) goto underflow; }
again: if (likely(mas->offset)) { mas->offset--; mas->last = mas->index - 1; mas->index = mas_safe_min(mas, pivots, mas->offset); } else { if (mas->index <= min) goto underflow;
if (mas_prev_node(mas, min)) { mas_rewalk(mas, save_point); goto retry; }
if (WARN_ON_ONCE(mas_is_underflow(mas))) return NULL;
mas->last = mas->max; node = mas_mn(mas); type = mte_node_type(mas->node); pivots = ma_pivots(node, type); mas->index = pivots[mas->offset - 1] + 1; }
slots = ma_slots(node, type); entry = mas_slot(mas, slots, mas->offset); if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) goto retry;
if (likely(entry)) return entry;
if (!empty) { if (mas->index <= min) goto underflow;
goto again; }
return entry;
underflow: mas->status = ma_underflow; return NULL;}
/* * mas_next_node() - Get the next node at the same level in the tree. * @mas: The maple state * @node: The maple node * @max: The maximum pivot value to check. * * The next value will be mas->node[mas->offset] or the status will have * overflowed. * Return: 1 on dead node, 0 otherwise. */static int mas_next_node(struct ma_state *mas, struct maple_node *node, unsigned long max){ unsigned long min; unsigned long *pivots; struct maple_enode *enode; struct maple_node *tmp; int level = 0; unsigned char node_end; enum maple_type mt; void __rcu **slots;
if (mas->max >= max) goto overflow;
min = mas->max + 1; level = 0; do { if (ma_is_root(node)) goto overflow;
/* Walk up. */ if (unlikely(mas_ascend(mas))) return 1;
level++; node = mas_mn(mas); mt = mte_node_type(mas->node); pivots = ma_pivots(node, mt); node_end = ma_data_end(node, mt, pivots, mas->max); if (unlikely(ma_dead_node(node))) return 1;
} while (unlikely(mas->offset == node_end));
slots = ma_slots(node, mt); mas->offset++; enode = mas_slot(mas, slots, mas->offset); if (unlikely(ma_dead_node(node))) return 1;
if (level > 1) mas->offset = 0;
while (unlikely(level > 1)) { level--; mas->node = enode; node = mas_mn(mas); mt = mte_node_type(mas->node); slots = ma_slots(node, mt); enode = mas_slot(mas, slots, 0); if (unlikely(ma_dead_node(node))) return 1; }
if (!mas->offset) pivots = ma_pivots(node, mt);
mas->max = mas_safe_pivot(mas, pivots, mas->offset, mt); tmp = mte_to_node(enode); mt = mte_node_type(enode); pivots = ma_pivots(tmp, mt); mas->end = ma_data_end(tmp, mt, pivots, mas->max); if (unlikely(ma_dead_node(node))) return 1;
mas->node = enode; mas->min = min; return 0;
overflow: if (unlikely(ma_dead_node(node))) return 1;
mas->status = ma_overflow; return 0;}
/* * mas_next_slot() - Get the entry in the next slot * * @mas: The maple state * @max: The maximum starting range * @empty: Can be empty * * Return: The entry in the next slot which is possibly NULL */static void *mas_next_slot(struct ma_state *mas, unsigned long max, bool empty){ void __rcu **slots; unsigned long *pivots; unsigned long pivot; enum maple_type type; struct maple_node *node; unsigned long save_point = mas->last; void *entry;
retry: node = mas_mn(mas); type = mte_node_type(mas->node); pivots = ma_pivots(node, type); if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) goto retry;
if (mas->max >= max) { if (likely(mas->offset < mas->end)) pivot = pivots[mas->offset]; else pivot = mas->max;
if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) goto retry;
if (pivot >= max) { /* Was at the limit, next will extend beyond */ mas->status = ma_overflow; return NULL; } }
if (likely(mas->offset < mas->end)) { mas->index = pivots[mas->offset] + 1;again: mas->offset++; if (likely(mas->offset < mas->end)) mas->last = pivots[mas->offset]; else mas->last = mas->max; } else { if (mas->last >= max) { mas->status = ma_overflow; return NULL; }
if (mas_next_node(mas, node, max)) { mas_rewalk(mas, save_point); goto retry; }
if (WARN_ON_ONCE(mas_is_overflow(mas))) return NULL;
mas->offset = 0; mas->index = mas->min; node = mas_mn(mas); type = mte_node_type(mas->node); pivots = ma_pivots(node, type); mas->last = pivots[0]; }
slots = ma_slots(node, type); entry = mt_slot(mas->tree, slots, mas->offset); if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) goto retry;
if (entry) return entry;
if (!empty) { if (mas->last >= max) { mas->status = ma_overflow; return NULL; }
mas->index = mas->last + 1; goto again; }
return entry;}
/* * mas_rev_awalk() - Internal function. Reverse allocation walk. Find the * highest gap address of a given size in a given node and descend. * @mas: The maple state * @size: The needed size. * * Return: True if found in a leaf, false otherwise. * */static bool mas_rev_awalk(struct ma_state *mas, unsigned long size, unsigned long *gap_min, unsigned long *gap_max){ enum maple_type type = mte_node_type(mas->node); struct maple_node *node = mas_mn(mas); unsigned long *pivots, *gaps; void __rcu **slots; unsigned long gap = 0; unsigned long max, min; unsigned char offset;
if (unlikely(mas_is_err(mas))) return true;
if (ma_is_dense(type)) { /* dense nodes. */ mas->offset = (unsigned char)(mas->index - mas->min); return true; }
pivots = ma_pivots(node, type); slots = ma_slots(node, type); gaps = ma_gaps(node, type); offset = mas->offset; min = mas_safe_min(mas, pivots, offset); /* Skip out of bounds. */ while (mas->last < min) min = mas_safe_min(mas, pivots, --offset);
max = mas_safe_pivot(mas, pivots, offset, type); while (mas->index <= max) { gap = 0; if (gaps) gap = gaps[offset]; else if (!mas_slot(mas, slots, offset)) gap = max - min + 1;
if (gap) { if ((size <= gap) && (size <= mas->last - min + 1)) break;
if (!gaps) { /* Skip the next slot, it cannot be a gap. */ if (offset < 2) goto ascend;
offset -= 2; max = pivots[offset]; min = mas_safe_min(mas, pivots, offset); continue; } }
if (!offset) goto ascend;
offset--; max = min - 1; min = mas_safe_min(mas, pivots, offset); }
if (unlikely((mas->index > max) || (size - 1 > max - mas->index))) goto no_space;
if (unlikely(ma_is_leaf(type))) { mas->offset = offset; *gap_min = min; *gap_max = min + gap - 1; return true; }
/* descend, only happens under lock. */ mas->node = mas_slot(mas, slots, offset); mas->min = min; mas->max = max; mas->offset = mas_data_end(mas); return false;
ascend: if (!mte_is_root(mas->node)) return false;
no_space: mas_set_err(mas, -EBUSY); return false;}
static inline bool mas_anode_descend(struct ma_state *mas, unsigned long size){ enum maple_type type = mte_node_type(mas->node); unsigned long pivot, min, gap = 0; unsigned char offset, data_end; unsigned long *gaps, *pivots; void __rcu **slots; struct maple_node *node; bool found = false;
if (ma_is_dense(type)) { mas->offset = (unsigned char)(mas->index - mas->min); return true; }
node = mas_mn(mas); pivots = ma_pivots(node, type); slots = ma_slots(node, type); gaps = ma_gaps(node, type); offset = mas->offset; min = mas_safe_min(mas, pivots, offset); data_end = ma_data_end(node, type, pivots, mas->max); for (; offset <= data_end; offset++) { pivot = mas_safe_pivot(mas, pivots, offset, type);
/* Not within lower bounds */ if (mas->index > pivot) goto next_slot;
if (gaps) gap = gaps[offset]; else if (!mas_slot(mas, slots, offset)) gap = min(pivot, mas->last) - max(mas->index, min) + 1; else goto next_slot;
if (gap >= size) { if (ma_is_leaf(type)) { found = true; break; }
mas->node = mas_slot(mas, slots, offset); mas->min = min; mas->max = pivot; offset = 0; break; }next_slot: min = pivot + 1; if (mas->last <= pivot) { mas_set_err(mas, -EBUSY); return true; } }
mas->offset = offset; return found;}
/** * mas_walk() - Search for @mas->index in the tree. * @mas: The maple state. * * mas->index and mas->last will be set to the range if there is a value. If * mas->status is ma_none, reset to ma_start * * Return: the entry at the location or %NULL. */void *mas_walk(struct ma_state *mas){ void *entry;
mas_may_init_lock_check(mas); mas_make_walkable(mas);retry: entry = mas_state_walk(mas); if (mas_is_start(mas)) { goto retry; } else if (mas_is_none(mas)) { mas->index = 0; mas->last = ULONG_MAX; } else if (mas_is_ptr(mas)) { if (!mas->index) { mas->last = 0; return entry; }
mas->index = 1; mas->last = ULONG_MAX; mas->status = ma_none; return NULL; }
return entry;}EXPORT_SYMBOL_GPL(mas_walk);
static inline bool mas_rewind_node(struct ma_state *mas){ unsigned char slot;
do { if (mte_is_root(mas->node)) { slot = mas->offset; if (!slot) return false; } else { mas_ascend(mas); slot = mas->offset; } } while (!slot);
mas->offset = --slot; return true;}
/* * mas_skip_node() - Internal function. Skip over a node. * @mas: The maple state. * * Return: true if there is another node, false otherwise. */static inline bool mas_skip_node(struct ma_state *mas){ if (mas_is_err(mas)) return false;
do { if (mte_is_root(mas->node)) { if (mas->offset >= mas_data_end(mas)) { mas_set_err(mas, -EBUSY); return false; } } else { mas_ascend(mas); } } while (mas->offset >= mas_data_end(mas));
mas->offset++; return true;}
/* * mas_awalk() - Allocation walk. Search from low address to high, for a gap of * @size * @mas: The maple state * @size: The size of the gap required * * Search between @mas->index and @mas->last for a gap of @size. */static inline void mas_awalk(struct ma_state *mas, unsigned long size){ struct maple_enode *last = NULL;
/* * There are 4 options: * go to child (descend) * go back to parent (ascend) * no gap found. (return, error == -EBUSY) * found the gap. (return) */ while (!mas_is_err(mas) && !mas_anode_descend(mas, size)) { if (last == mas->node) mas_skip_node(mas); else last = mas->node; }}
/* * mas_sparse_area() - Internal function. Return upper or lower limit when * searching for a gap in an empty tree. * @mas: The maple state * @min: the minimum range * @max: The maximum range * @size: The size of the gap * @fwd: Searching forward or back */static inline int mas_sparse_area(struct ma_state *mas, unsigned long min, unsigned long max, unsigned long size, bool fwd){ if (!unlikely(mas_is_none(mas)) && min == 0) { min++; /* * At this time, min is increased, we need to recheck whether * the size is satisfied. */ if (min > max || max - min + 1 < size) return -EBUSY; } /* mas_is_ptr */
if (fwd) { mas->index = min; mas->last = min + size - 1; } else { mas->last = max; mas->index = max - size + 1; } return 0;}
/* * mas_empty_area() - Get the lowest address within the range that is * sufficient for the size requested. * @mas: The maple state * @min: The lowest value of the range * @max: The highest value of the range * @size: The size needed */int mas_empty_area(struct ma_state *mas, unsigned long min, unsigned long max, unsigned long size){ unsigned char offset; unsigned long *pivots; enum maple_type mt; struct maple_node *node;
if (min > max) return -EINVAL;
if (size == 0 || max - min < size - 1) return -EINVAL;
if (mas_is_start(mas)) mas_start(mas); else if (mas->offset >= 2) mas->offset -= 2; else if (!mas_skip_node(mas)) return -EBUSY;
/* Empty set */ if (mas_is_none(mas) || mas_is_ptr(mas)) return mas_sparse_area(mas, min, max, size, true);
/* The start of the window can only be within these values */ mas->index = min; mas->last = max; mas_awalk(mas, size);
if (unlikely(mas_is_err(mas))) return xa_err(mas->node);
offset = mas->offset; node = mas_mn(mas); mt = mte_node_type(mas->node); pivots = ma_pivots(node, mt); min = mas_safe_min(mas, pivots, offset); if (mas->index < min) mas->index = min; mas->last = mas->index + size - 1; mas->end = ma_data_end(node, mt, pivots, mas->max); return 0;}EXPORT_SYMBOL_GPL(mas_empty_area);
/* * mas_empty_area_rev() - Get the highest address within the range that is * sufficient for the size requested. * @mas: The maple state * @min: The lowest value of the range * @max: The highest value of the range * @size: The size needed */int mas_empty_area_rev(struct ma_state *mas, unsigned long min, unsigned long max, unsigned long size){ struct maple_enode *last = mas->node;
if (min > max) return -EINVAL;
if (size == 0 || max - min < size - 1) return -EINVAL;
if (mas_is_start(mas)) mas_start(mas); else if ((mas->offset < 2) && (!mas_rewind_node(mas))) return -EBUSY;
if (unlikely(mas_is_none(mas) || mas_is_ptr(mas))) return mas_sparse_area(mas, min, max, size, false); else if (mas->offset >= 2) mas->offset -= 2; else mas->offset = mas_data_end(mas);
/* The start of the window can only be within these values. */ mas->index = min; mas->last = max;
while (!mas_rev_awalk(mas, size, &min, &max)) { if (last == mas->node) { if (!mas_rewind_node(mas)) return -EBUSY; } else { last = mas->node; } }
if (mas_is_err(mas)) return xa_err(mas->node);
if (unlikely(mas->offset == MAPLE_NODE_SLOTS)) return -EBUSY;
/* Trim the upper limit to the max. */ if (max < mas->last) mas->last = max;
mas->index = mas->last - size + 1; mas->end = mas_data_end(mas); return 0;}EXPORT_SYMBOL_GPL(mas_empty_area_rev);
/* * mte_dead_leaves() - Mark all leaves of a node as dead. * @enode: the encoded node * @mt: the maple tree * @slots: Pointer to the slot array * * Must hold the write lock. * * Return: The number of leaves marked as dead. */static inlineunsigned char mte_dead_leaves(struct maple_enode *enode, struct maple_tree *mt, void __rcu **slots){ struct maple_node *node; enum maple_type type; void *entry; int offset;
for (offset = 0; offset < mt_slot_count(enode); offset++) { entry = mt_slot(mt, slots, offset); type = mte_node_type(entry); node = mte_to_node(entry); /* Use both node and type to catch LE & BE metadata */ if (!node || !type) break;
mte_set_node_dead(entry); node->type = type; rcu_assign_pointer(slots[offset], node); }
return offset;}
/** * mte_dead_walk() - Walk down a dead tree to just before the leaves * @enode: The maple encoded node * @offset: The starting offset * * Note: This can only be used from the RCU callback context. */static void __rcu **mte_dead_walk(struct maple_enode **enode, unsigned char offset){ struct maple_node *node, *next; void __rcu **slots = NULL;
next = mte_to_node(*enode); do { *enode = ma_enode_ptr(next); node = mte_to_node(*enode); slots = ma_slots(node, node->type); next = rcu_dereference_protected(slots[offset], lock_is_held(&rcu_callback_map)); offset = 0; } while (!ma_is_leaf(next->type));
return slots;}
/** * mt_free_walk() - Walk & free a tree in the RCU callback context * @head: The RCU head that's within the node. * * Note: This can only be used from the RCU callback context. */static void mt_free_walk(struct rcu_head *head){ void __rcu **slots; struct maple_node *node, *start; struct maple_enode *enode; unsigned char offset; enum maple_type type;
node = container_of(head, struct maple_node, rcu);
if (ma_is_leaf(node->type)) goto free_leaf;
start = node; enode = mt_mk_node(node, node->type); slots = mte_dead_walk(&enode, 0); node = mte_to_node(enode); do { mt_free_bulk(node->slot_len, slots); offset = node->parent_slot + 1; enode = node->piv_parent; if (mte_to_node(enode) == node) goto free_leaf;
type = mte_node_type(enode); slots = ma_slots(mte_to_node(enode), type); if (offset < mte_to_node(enode)->slot_len) slots = mte_dead_walk(&enode, offset); node = mte_to_node(enode); } while ((node != start) || (node->slot_len < offset));
slots = ma_slots(node, node->type); mt_free_bulk(node->slot_len, slots);
free_leaf: kfree(node);}
static inline void __rcu **mte_destroy_descend(struct maple_enode **enode, struct maple_tree *mt, struct maple_enode *prev, unsigned char offset){ struct maple_node *node; struct maple_enode *next = *enode; void __rcu **slots = NULL; enum maple_type type; unsigned char next_offset = 0;
do { *enode = next; node = mte_to_node(*enode); type = mte_node_type(*enode); slots = ma_slots(node, type); next = mt_slot_locked(mt, slots, next_offset); if ((mte_dead_node(next))) next = mt_slot_locked(mt, slots, ++next_offset);
mte_set_node_dead(*enode); node->type = type; node->piv_parent = prev; node->parent_slot = offset; offset = next_offset; next_offset = 0; prev = *enode; } while (!mte_is_leaf(next));
return slots;}
static void mt_destroy_walk(struct maple_enode *enode, struct maple_tree *mt, bool free){ void __rcu **slots; struct maple_node *node = mte_to_node(enode); struct maple_enode *start;
if (mte_is_leaf(enode)) { mte_set_node_dead(enode); node->type = mte_node_type(enode); goto free_leaf; }
start = enode; slots = mte_destroy_descend(&enode, mt, start, 0); node = mte_to_node(enode); // Updated in the above call. do { enum maple_type type; unsigned char offset; struct maple_enode *parent, *tmp;
node->slot_len = mte_dead_leaves(enode, mt, slots); if (free) mt_free_bulk(node->slot_len, slots); offset = node->parent_slot + 1; enode = node->piv_parent; if (mte_to_node(enode) == node) goto free_leaf;
type = mte_node_type(enode); slots = ma_slots(mte_to_node(enode), type); if (offset >= mt_slots[type]) goto next;
tmp = mt_slot_locked(mt, slots, offset); if (mte_node_type(tmp) && mte_to_node(tmp)) { parent = enode; enode = tmp; slots = mte_destroy_descend(&enode, mt, parent, offset); }next: node = mte_to_node(enode); } while (start != enode);
node = mte_to_node(enode); node->slot_len = mte_dead_leaves(enode, mt, slots); if (free) mt_free_bulk(node->slot_len, slots);
free_leaf: if (free) kfree(node);}
/* * mte_destroy_walk() - Free a tree or sub-tree. * @enode: the encoded maple node (maple_enode) to start * @mt: the tree to free - needed for node types. * * Must hold the write lock. */static inline void mte_destroy_walk(struct maple_enode *enode, struct maple_tree *mt){ struct maple_node *node = mte_to_node(enode);
if (mt_in_rcu(mt)) { mt_destroy_walk(enode, mt, false); call_rcu(&node->rcu, mt_free_walk); } else { mt_destroy_walk(enode, mt, true); }}/* Interface */
/** * mas_store() - Store an @entry. * @mas: The maple state. * @entry: The entry to store. * * The @mas->index and @mas->last is used to set the range for the @entry. * * Return: the first entry between mas->index and mas->last or %NULL. */void *mas_store(struct ma_state *mas, void *entry){ MA_WR_STATE(wr_mas, mas, entry);
mas_may_init_lock_check(mas); trace_ma_write(TP_FCT, mas, 0, entry);#ifdef CONFIG_DEBUG_MAPLE_TREE if (MAS_WARN_ON(mas, mas->index > mas->last)) pr_err("Error %lX > %lX " PTR_FMT "\n", mas->index, mas->last, entry);
if (mas->index > mas->last) { mas_set_err(mas, -EINVAL); return NULL; }
#endif
/* * Storing is the same operation as insert with the added caveat that it * can overwrite entries. Although this seems simple enough, one may * want to examine what happens if a single store operation was to * overwrite multiple entries within a self-balancing B-Tree. */ mas_wr_prealloc_setup(&wr_mas); mas->store_type = mas_wr_store_type(&wr_mas); if (mas->mas_flags & MA_STATE_PREALLOC) { mas_wr_store_entry(&wr_mas); MAS_WR_BUG_ON(&wr_mas, mas_is_err(mas)); return wr_mas.content; }
mas_prealloc_calc(&wr_mas, entry); if (!mas->node_request) goto store;
mas_alloc_nodes(mas, GFP_NOWAIT); if (mas_is_err(mas)) return NULL;
store: mas_wr_store_entry(&wr_mas); mas_destroy(mas); return wr_mas.content;}EXPORT_SYMBOL_GPL(mas_store);
/** * mas_store_gfp() - Store a value into the tree. * @mas: The maple state * @entry: The entry to store * @gfp: The GFP_FLAGS to use for allocations if necessary. * * Return: 0 on success, -EINVAL on invalid request, -ENOMEM if memory could not * be allocated. */int mas_store_gfp(struct ma_state *mas, void *entry, gfp_t gfp){ unsigned long index = mas->index; unsigned long last = mas->last; MA_WR_STATE(wr_mas, mas, entry); int ret = 0;
mas_may_init_lock_check(mas);retry: mas_wr_preallocate(&wr_mas, entry); if (unlikely(mas_nomem(mas, gfp))) { if (!entry) __mas_set_range(mas, index, last); goto retry; }
if (mas_is_err(mas)) { ret = xa_err(mas->node); goto out; }
mas_wr_store_entry(&wr_mas);out: mas_destroy(mas); return ret;}EXPORT_SYMBOL_GPL(mas_store_gfp);
/** * mas_store_prealloc() - Store a value into the tree using memory * preallocated in the maple state. * @mas: The maple state * @entry: The entry to store. */void mas_store_prealloc(struct ma_state *mas, void *entry){ MA_WR_STATE(wr_mas, mas, entry);
mas_lock_check(mas); if (mas->store_type == wr_store_root) { mas_wr_prealloc_setup(&wr_mas); goto store; }
mas_wr_walk_descend(&wr_mas); if (mas->store_type != wr_spanning_store) { /* set wr_mas->content to current slot */ wr_mas.content = mas_slot_locked(mas, wr_mas.slots, mas->offset); mas_wr_end_piv(&wr_mas); }
store: trace_ma_write(TP_FCT, mas, 0, entry); mas_wr_store_entry(&wr_mas); MAS_WR_BUG_ON(&wr_mas, mas_is_err(mas)); mas_destroy(mas);}EXPORT_SYMBOL_GPL(mas_store_prealloc);
/** * mas_preallocate() - Preallocate enough nodes for a store operation * @mas: The maple state * @entry: The entry that will be stored * @gfp: The GFP_FLAGS to use for allocations. * * Return: 0 on success, -ENOMEM if memory could not be allocated. */int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp){ MA_WR_STATE(wr_mas, mas, entry);
mas_may_init_lock_check(mas); mas_wr_prealloc_setup(&wr_mas); mas->store_type = mas_wr_store_type(&wr_mas); mas_prealloc_calc(&wr_mas, entry); if (!mas->node_request) goto set_flag;
mas->mas_flags &= ~MA_STATE_PREALLOC; mas_alloc_nodes(mas, gfp); if (mas_is_err(mas)) { int ret = xa_err(mas->node);
mas->node_request = 0; mas_destroy(mas); mas_reset(mas); return ret; }
set_flag: mas->mas_flags |= MA_STATE_PREALLOC; return 0;}EXPORT_SYMBOL_GPL(mas_preallocate);
/* * mas_destroy() - destroy a maple state. * @mas: The maple state * * Upon completion, check the left-most node and rebalance against the node to * the right if necessary. Frees any allocated nodes associated with this maple * state. */void mas_destroy(struct ma_state *mas){ mas->mas_flags &= ~MA_STATE_PREALLOC; mas_empty_nodes(mas);}EXPORT_SYMBOL_GPL(mas_destroy);
static void mas_may_activate(struct ma_state *mas){ if (!mas->node) { mas->status = ma_start; } else if (mas->index > mas->max || mas->index < mas->min) { mas->status = ma_start; } else { mas->status = ma_active; mas_lock_check(mas); }}
static bool mas_next_setup(struct ma_state *mas, unsigned long max, void **entry){ bool was_none = mas_is_none(mas);
if (unlikely(mas->last >= max)) { mas->status = ma_overflow; return true; }
switch (mas->status) { case ma_active: return false; case ma_none: fallthrough; case ma_pause: mas->status = ma_start; fallthrough; case ma_start: mas_walk(mas); /* Retries on dead nodes handled by mas_walk */ break; case ma_overflow: /* Overflowed before, but the max changed */ mas_may_activate(mas); break; case ma_underflow: /* The user expects the mas to be one before where it is */ mas_may_activate(mas); *entry = mas_walk(mas); if (*entry) return true; break; case ma_root: break; case ma_error: return true; }
if (likely(mas_is_active(mas))) /* Fast path */ return false;
if (mas_is_ptr(mas)) { *entry = NULL; if (was_none && mas->index == 0) { mas->index = mas->last = 0; return true; } mas->index = 1; mas->last = ULONG_MAX; mas->status = ma_none; return true; }
if (mas_is_none(mas)) return true;
return false;}
/** * mas_next() - Get the next entry. * @mas: The maple state * @max: The maximum index to check. * * Returns the next entry after @mas->index. * Must hold rcu_read_lock or the write lock. * Can return the zero entry. * * Return: The next entry or %NULL */void *mas_next(struct ma_state *mas, unsigned long max){ void *entry = NULL;
mas_may_init_lock_check(mas); if (mas_next_setup(mas, max, &entry)) return entry;
/* Retries on dead nodes handled by mas_next_slot */ return mas_next_slot(mas, max, false);}EXPORT_SYMBOL_GPL(mas_next);
/** * mas_next_range() - Advance the maple state to the next range * @mas: The maple state * @max: The maximum index to check. * * Sets @mas->index and @mas->last to the range. * Must hold rcu_read_lock or the write lock. * Can return the zero entry. * * Return: The next entry or %NULL */void *mas_next_range(struct ma_state *mas, unsigned long max){ void *entry = NULL;
mas_may_init_lock_check(mas); if (mas_next_setup(mas, max, &entry)) return entry;
/* Retries on dead nodes handled by mas_next_slot */ return mas_next_slot(mas, max, true);}EXPORT_SYMBOL_GPL(mas_next_range);
/** * mt_next() - get the next value in the maple tree * @mt: The maple tree * @index: The start index * @max: The maximum index to check * * Takes RCU read lock internally to protect the search, which does not * protect the returned pointer after dropping RCU read lock. * See also: Documentation/core-api/maple_tree.rst * * Return: The entry higher than @index or %NULL if nothing is found. */void *mt_next(struct maple_tree *mt, unsigned long index, unsigned long max){ void *entry = NULL; MA_STATE(mas, mt, index, index);
rcu_read_lock(); entry = mas_next(&mas, max); rcu_read_unlock(); return entry;}EXPORT_SYMBOL_GPL(mt_next);
static bool mas_prev_setup(struct ma_state *mas, unsigned long min, void **entry){ if (unlikely(mas->index <= min)) { mas->status = ma_underflow; return true; }
switch (mas->status) { case ma_active: return false; case ma_start: break; case ma_none: fallthrough; case ma_pause: mas->status = ma_start; break; case ma_underflow: /* underflowed before but the min changed */ mas_may_activate(mas); break; case ma_overflow: /* User expects mas to be one after where it is */ mas_may_activate(mas); *entry = mas_walk(mas); if (*entry) return true; break; case ma_root: break; case ma_error: return true; }
if (mas_is_start(mas)) mas_walk(mas);
if (unlikely(mas_is_ptr(mas))) { if (!mas->index) { mas->status = ma_none; return true; } mas->index = mas->last = 0; *entry = mas_root(mas); return true; }
if (mas_is_none(mas)) { if (mas->index) { /* Walked to out-of-range pointer? */ mas->index = mas->last = 0; mas->status = ma_root; *entry = mas_root(mas); return true; } return true; }
return false;}
/** * mas_prev() - Get the previous entry * @mas: The maple state * @min: The minimum value to check. * * Must hold rcu_read_lock or the write lock. * Will reset mas to ma_start if the status is ma_none. Will stop on not * searchable nodes. * * Return: the previous value or %NULL. */void *mas_prev(struct ma_state *mas, unsigned long min){ void *entry = NULL;
mas_may_init_lock_check(mas); if (mas_prev_setup(mas, min, &entry)) return entry;
return mas_prev_slot(mas, min, false);}EXPORT_SYMBOL_GPL(mas_prev);
/** * mas_prev_range() - Advance to the previous range * @mas: The maple state * @min: The minimum value to check. * * Sets @mas->index and @mas->last to the range. * Must hold rcu_read_lock or the write lock. * Will reset mas to ma_start if the node is ma_none. Will stop on not * searchable nodes. * * Return: the previous value or %NULL. */void *mas_prev_range(struct ma_state *mas, unsigned long min){ void *entry = NULL;
mas_may_init_lock_check(mas); if (mas_prev_setup(mas, min, &entry)) return entry;
return mas_prev_slot(mas, min, true);}EXPORT_SYMBOL_GPL(mas_prev_range);
/** * mt_prev() - get the previous value in the maple tree * @mt: The maple tree * @index: The start index * @min: The minimum index to check * * Takes RCU read lock internally to protect the search, which does not * protect the returned pointer after dropping RCU read lock. * See also: Documentation/core-api/maple_tree.rst * * Return: The entry before @index or %NULL if nothing is found. */void *mt_prev(struct maple_tree *mt, unsigned long index, unsigned long min){ void *entry = NULL; MA_STATE(mas, mt, index, index);
rcu_read_lock(); entry = mas_prev(&mas, min); rcu_read_unlock(); return entry;}EXPORT_SYMBOL_GPL(mt_prev);
/** * mas_pause() - Pause a mas_find/mas_for_each to drop the lock. * @mas: The maple state to pause * * Some users need to pause a walk and drop the lock they're holding in * order to yield to a higher priority thread or carry out an operation * on an entry. Those users should call this function before they drop * the lock. It resets the @mas to be suitable for the next iteration * of the loop after the user has reacquired the lock. If most entries * found during a walk require you to call mas_pause(), the mt_for_each() * iterator may be more appropriate. * */void mas_pause(struct ma_state *mas){ mas_lock_check(mas); mas->status = ma_pause; mas->node = NULL;}EXPORT_SYMBOL_GPL(mas_pause);
/** * mas_find_setup() - Internal function to set up mas_find*(). * @mas: The maple state * @max: The maximum index * @entry: Pointer to the entry * * Returns: True if entry is the answer, false otherwise. */static __always_inline bool mas_find_setup(struct ma_state *mas, unsigned long max, void **entry){ switch (mas->status) { case ma_active: if (mas->last < max) return false; return true; case ma_start: break; case ma_pause: if (unlikely(mas->last >= max)) return true;
mas->index = ++mas->last; mas->status = ma_start; break; case ma_none: if (unlikely(mas->last >= max)) return true;
mas->index = mas->last; mas->status = ma_start; break; case ma_underflow: /* mas is pointing at entry before unable to go lower */ if (unlikely(mas->index >= max)) { mas->status = ma_overflow; return true; }
mas_may_activate(mas); *entry = mas_walk(mas); if (*entry) return true; break; case ma_overflow: if (unlikely(mas->last >= max)) return true;
mas_may_activate(mas); *entry = mas_walk(mas); if (*entry) return true; break; case ma_root: break; case ma_error: return true; }
if (mas_is_start(mas)) { /* First run or continue */ if (mas->index > max) return true;
*entry = mas_walk(mas); if (*entry) return true;
}
if (unlikely(mas_is_ptr(mas))) goto ptr_out_of_range;
if (unlikely(mas_is_none(mas))) return true;
if (mas->index == max) return true;
return false;
ptr_out_of_range: mas->status = ma_none; mas->index = 1; mas->last = ULONG_MAX; return true;}
/** * mas_find() - On the first call, find the entry at or after mas->index up to * %max. Otherwise, find the entry after mas->index. * @mas: The maple state * @max: The maximum value to check. * * Must hold rcu_read_lock or the write lock. * If an entry exists, last and index are updated accordingly. * May set @mas->status to ma_overflow. * * Return: The entry or %NULL. */void *mas_find(struct ma_state *mas, unsigned long max){ void *entry = NULL;
mas_may_init_lock_check(mas); if (mas_find_setup(mas, max, &entry)) return entry;
/* Retries on dead nodes handled by mas_next_slot */ entry = mas_next_slot(mas, max, false); /* Ignore overflow */ mas->status = ma_active; return entry;}EXPORT_SYMBOL_GPL(mas_find);
/** * mas_find_range() - On the first call, find the entry at or after * mas->index up to %max. Otherwise, advance to the next slot mas->index. * @mas: The maple state * @max: The maximum value to check. * * Must hold rcu_read_lock or the write lock. * If an entry exists, last and index are updated accordingly. * May set @mas->status to ma_overflow. * * Return: The entry or %NULL. */void *mas_find_range(struct ma_state *mas, unsigned long max){ void *entry = NULL;
mas_may_init_lock_check(mas); if (mas_find_setup(mas, max, &entry)) return entry;
/* Retries on dead nodes handled by mas_next_slot */ return mas_next_slot(mas, max, true);}EXPORT_SYMBOL_GPL(mas_find_range);
/** * mas_find_rev_setup() - Internal function to set up mas_find_*_rev() * @mas: The maple state * @min: The minimum index * @entry: Pointer to the entry * * Returns: True if entry is the answer, false otherwise. */static bool mas_find_rev_setup(struct ma_state *mas, unsigned long min, void **entry){ switch (mas->status) { case ma_active: goto active; case ma_start: break; case ma_pause: if (unlikely(mas->index <= min)) { mas->status = ma_underflow; return true; } mas->last = --mas->index; mas->status = ma_start; break; case ma_none: if (mas->index <= min) goto none;
mas->last = mas->index; mas->status = ma_start; break; case ma_overflow: /* user expects the mas to be one after where it is */ if (unlikely(mas->index <= min)) { mas->status = ma_underflow; return true; }
mas->status = ma_active; break; case ma_underflow: /* user expects the mas to be one before where it is */ if (unlikely(mas->index <= min)) return true;
mas->status = ma_active; break; case ma_root: break; case ma_error: return true; }
if (mas_is_start(mas)) { /* First run or continue */ if (mas->index < min) return true;
*entry = mas_walk(mas); if (*entry) return true; }
if (unlikely(mas_is_ptr(mas))) goto none;
if (unlikely(mas_is_none(mas))) { /* * Walked to the location, and there was nothing so the previous * location is 0. */ mas->last = mas->index = 0; mas->status = ma_root; *entry = mas_root(mas); return true; }
active: if (mas->index < min) return true;
return false;
none: mas->status = ma_none; return true;}
/** * mas_find_rev: On the first call, find the first non-null entry at or below * mas->index down to %min. Otherwise find the first non-null entry below * mas->index down to %min. * @mas: The maple state * @min: The minimum value to check. * * Must hold rcu_read_lock or the write lock. * If an entry exists, last and index are updated accordingly. * May set @mas->status to ma_underflow. * * Return: The entry or %NULL. */void *mas_find_rev(struct ma_state *mas, unsigned long min){ void *entry = NULL;
mas_may_init_lock_check(mas); if (mas_find_rev_setup(mas, min, &entry)) return entry;
/* Retries on dead nodes handled by mas_prev_slot */ return mas_prev_slot(mas, min, false);
}EXPORT_SYMBOL_GPL(mas_find_rev);
/** * mas_find_range_rev: On the first call, find the first non-null entry at or * below mas->index down to %min. Otherwise advance to the previous slot after * mas->index down to %min. * @mas: The maple state * @min: The minimum value to check. * * Must hold rcu_read_lock or the write lock. * If an entry exists, last and index are updated accordingly. * May set @mas->status to ma_underflow. * * Return: The entry or %NULL. */void *mas_find_range_rev(struct ma_state *mas, unsigned long min){ void *entry = NULL;
mas_may_init_lock_check(mas); if (mas_find_rev_setup(mas, min, &entry)) return entry;
/* Retries on dead nodes handled by mas_prev_slot */ return mas_prev_slot(mas, min, true);}EXPORT_SYMBOL_GPL(mas_find_range_rev);
/** * mas_erase() - Find the range in which index resides and erase the entire * range. * @mas: The maple state * * Must hold the write lock. * Searches for @mas->index, sets @mas->index and @mas->last to the range and * erases that range. * * Note that erase requires allocations and will use GFP_KERNEL | __GFP_NOFAIL * to do so if necessary. If the allocation fails, the internal lock will be * dropped to retry. An externally locked tree must be protected by a lock that * allows blocking for this API. * * Return: the entry that was erased or %NULL, @mas->index and @mas->last are updated. */void *mas_erase(struct ma_state *mas){ void *entry; unsigned long index = mas->index; MA_WR_STATE(wr_mas, mas, NULL);
/* * In low memory situations, the allocation is retried with the gfp flag * GFP_KERNEL | __GFP_NOFAIL. The internal spinlock is dropped in * mas_nomem_nofail(), however the external lock is not dropped. */ if (mt_external_lock(mas->tree)) might_alloc(GFP_KERNEL);
mas_make_walkable(mas);write_retry: entry = mas_state_walk(mas); if (!entry) goto out;
/* Must reset to ensure spanning writes of last slot are detected */ mas_reset(mas); mas_wr_preallocate(&wr_mas, NULL); if (mas_nomem_nofail(mas, index, index)) goto write_retry;
mas_wr_store_entry(&wr_mas);out: mas_destroy(mas); return entry;}EXPORT_SYMBOL_GPL(mas_erase);
/** * mas_nomem() - Check if there was an error allocating and do the allocation * if necessary. * * @mas: The maple state * @gfp: The GFP_FLAGS to use for allocations * Return: False on no memory. True otherwise (partial success as well) */bool mas_nomem(struct ma_state *mas, gfp_t gfp) __must_hold(mas->tree->ma_lock){ if (likely(mas->node != MA_ERROR(-ENOMEM))) return false;
/* Allocations can fail, don't do this. */ WARN_ON_ONCE(!gfpflags_allow_blocking(gfp) && mt_external_lock(mas->tree));
if (gfpflags_allow_blocking(gfp) && !mt_external_lock(mas->tree)) { mtree_unlock(mas->tree); mas_alloc_nodes(mas, gfp); mtree_lock(mas->tree); } else { mas_alloc_nodes(mas, gfp); }
/* * Return false on zero forward progress. Partial allocations are kept * so the retry path will attempt to get the rest. The failure should * not happen as we try our best to reclaim. The user would need an * external lock with a non-blocking gfp in a low memory situation. */ if (!mas->sheaf && !mas->alloc) return false;
mas_reset(mas); return true;}
/** * mas_nomem_nofail() - Retry allocations with __GFP_NOFAIL, if the maple state * has stored the -ENOMEM error. * @mas: The maple state * @index: The start of the range for the @mas reset * @last: The end of the range for the @mas reset * * Return: false if @mas isn't in an -ENOMEM state. True if the allocation * happens, the state is reset. The internal lock will be dropped and external * locks must allow blocking. */bool mas_nomem_nofail(struct ma_state *mas, unsigned long index, unsigned long last) __must_hold(mas->tree->ma_lock){ gfp_t gfp;
if (likely(mas->node != MA_ERROR(-ENOMEM))) return false;
gfp = GFP_KERNEL | __GFP_NOFAIL; if (!mt_external_lock(mas->tree)) { mtree_unlock(mas->tree); mas_alloc_nodes(mas, gfp); mtree_lock(mas->tree); } else { mas_alloc_nodes(mas, gfp); }
mas_set_range(mas, index, last); return true;}
void __init maple_tree_init(void){ struct kmem_cache_args args = { .align = sizeof(struct maple_node), .sheaf_capacity = 32, };
maple_node_cache = kmem_cache_create("maple_node", sizeof(struct maple_node), &args, SLAB_PANIC);}
/** * mtree_load() - Load a value stored in a maple tree * @mt: The maple tree * @index: The index to load * * Return: the entry or %NULL */void *mtree_load(struct maple_tree *mt, unsigned long index){ MA_STATE(mas, mt, index, index); void *entry;
trace_ma_read(TP_FCT, &mas); rcu_read_lock();retry: entry = mas_start(&mas); if (unlikely(mas_is_none(&mas))) goto unlock;
if (unlikely(mas_is_ptr(&mas))) { if (index) entry = NULL;
goto unlock; }
entry = mtree_lookup_walk(&mas); if (!entry && unlikely(mas_is_start(&mas))) goto retry;unlock: rcu_read_unlock(); if (xa_is_zero(entry)) return NULL;
return entry;}EXPORT_SYMBOL(mtree_load);
/** * mtree_store_range() - Store an entry at a given range. * @mt: The maple tree * @index: The start of the range * @last: The end of the range * @entry: The entry to store * @gfp: The GFP_FLAGS to use for allocations * * Return: 0 on success, -EINVAL on invalid request, -ENOMEM if memory could not * be allocated. */int mtree_store_range(struct maple_tree *mt, unsigned long index, unsigned long last, void *entry, gfp_t gfp){ MA_STATE(mas, mt, index, last); int ret = 0;
trace_ma_write(TP_FCT, &mas, 0, entry); if (WARN_ON_ONCE(xa_is_advanced(entry))) return -EINVAL;
if (index > last) return -EINVAL;
mtree_lock(mt); ret = mas_store_gfp(&mas, entry, gfp); mtree_unlock(mt);
return ret;}EXPORT_SYMBOL(mtree_store_range);
/** * mtree_store() - Store an entry at a given index. * @mt: The maple tree * @index: The index to store the value * @entry: The entry to store * @gfp: The GFP_FLAGS to use for allocations * * Return: 0 on success, -EINVAL on invalid request, -ENOMEM if memory could not * be allocated. */int mtree_store(struct maple_tree *mt, unsigned long index, void *entry, gfp_t gfp){ return mtree_store_range(mt, index, index, entry, gfp);}EXPORT_SYMBOL(mtree_store);
/** * mtree_insert_range() - Insert an entry from [first, last] at a given range * if there is no value. * @mt: The maple tree * @first: The start of the range * @last: The end of the range (inclusive) * @entry: The entry to store * @gfp: The GFP_FLAGS to use for allocations. * * Note that @last is inclusive. That is, @last = @first + length - 1; * * Return: 0 on success, -EEXISTS if the range is occupied, -EINVAL on invalid * request, -ENOMEM if memory could not be allocated. */int mtree_insert_range(struct maple_tree *mt, unsigned long first, unsigned long last, void *entry, gfp_t gfp){ MA_STATE(ms, mt, first, last); int ret = 0;
if (WARN_ON_ONCE(xa_is_advanced(entry))) return -EINVAL;
if (first > last) return -EINVAL;
mtree_lock(mt);retry: mas_insert(&ms, entry); if (mas_nomem(&ms, gfp)) goto retry;
mtree_unlock(mt); if (mas_is_err(&ms)) ret = xa_err(ms.node);
mas_destroy(&ms); return ret;}EXPORT_SYMBOL(mtree_insert_range);
/** * mtree_insert() - Insert an entry at a given index if there is no value. * @mt: The maple tree * @index : The index to store the value * @entry: The entry to store * @gfp: The GFP_FLAGS to use for allocations. * * Return: 0 on success, -EEXISTS if the range is occupied, -EINVAL on invalid * request, -ENOMEM if memory could not be allocated. */int mtree_insert(struct maple_tree *mt, unsigned long index, void *entry, gfp_t gfp){ return mtree_insert_range(mt, index, index, entry, gfp);}EXPORT_SYMBOL(mtree_insert);
int mtree_alloc_range(struct maple_tree *mt, unsigned long *startp, void *entry, unsigned long size, unsigned long min, unsigned long max, gfp_t gfp){ int ret = 0;
MA_STATE(mas, mt, 0, 0); if (!mt_is_alloc(mt)) return -EINVAL;
if (WARN_ON_ONCE(mt_is_reserved(entry))) return -EINVAL;
mtree_lock(mt);retry: ret = mas_empty_area(&mas, min, max, size); if (ret) goto unlock;
mas_insert(&mas, entry); /* * mas_nomem() may release the lock, causing the allocated area * to be unavailable, so try to allocate a free area again. */ if (mas_nomem(&mas, gfp)) goto retry;
if (mas_is_err(&mas)) ret = xa_err(mas.node); else *startp = mas.index;
unlock: mtree_unlock(mt); mas_destroy(&mas); return ret;}EXPORT_SYMBOL(mtree_alloc_range);
/** * mtree_alloc_cyclic() - Find somewhere to store this entry in the tree. * @mt: The maple tree. * @startp: Pointer to ID. * @range_lo: Lower bound of range to search. * @range_hi: Upper bound of range to search. * @entry: The entry to store. * @next: Pointer to next ID to allocate. * @gfp: The GFP_FLAGS to use for allocations. * * Finds an empty entry in @mt after @next, stores the new index into * the @id pointer, stores the entry at that index, then updates @next. * * @mt must be initialized with the MT_FLAGS_ALLOC_RANGE flag. * * Context: Any context. Takes and releases the mt.lock. May sleep if * the @gfp flags permit. * * Return: 0 if the allocation succeeded without wrapping, 1 if the * allocation succeeded after wrapping, -ENOMEM if memory could not be * allocated, -EINVAL if @mt cannot be used, or -EBUSY if there are no * free entries. */int mtree_alloc_cyclic(struct maple_tree *mt, unsigned long *startp, void *entry, unsigned long range_lo, unsigned long range_hi, unsigned long *next, gfp_t gfp){ int ret;
MA_STATE(mas, mt, 0, 0);
if (!mt_is_alloc(mt)) return -EINVAL; if (WARN_ON_ONCE(mt_is_reserved(entry))) return -EINVAL; mtree_lock(mt); ret = mas_alloc_cyclic(&mas, startp, entry, range_lo, range_hi, next, gfp); mtree_unlock(mt); return ret;}EXPORT_SYMBOL(mtree_alloc_cyclic);
int mtree_alloc_rrange(struct maple_tree *mt, unsigned long *startp, void *entry, unsigned long size, unsigned long min, unsigned long max, gfp_t gfp){ int ret = 0;
MA_STATE(mas, mt, 0, 0); if (!mt_is_alloc(mt)) return -EINVAL;
if (WARN_ON_ONCE(mt_is_reserved(entry))) return -EINVAL;
mtree_lock(mt);retry: ret = mas_empty_area_rev(&mas, min, max, size); if (ret) goto unlock;
mas_insert(&mas, entry); /* * mas_nomem() may release the lock, causing the allocated area * to be unavailable, so try to allocate a free area again. */ if (mas_nomem(&mas, gfp)) goto retry;
if (mas_is_err(&mas)) ret = xa_err(mas.node); else *startp = mas.index;
unlock: mtree_unlock(mt); mas_destroy(&mas); return ret;}EXPORT_SYMBOL(mtree_alloc_rrange);
/** * mtree_erase() - Find an index and erase the entire range. * @mt: The maple tree * @index: The index to erase * * Erasing is the same as a walk to an entry then a store of a NULL to that * ENTIRE range. In fact, it is implemented as such using the advanced API. * * Note that erase requires allocations and will use GFP_KERNEL | __GFP_NOFAIL * to do so if necessary. If the allocation fails, the internal lock will be * dropped to retry. * * Return: The entry stored at the @index or %NULL */void *mtree_erase(struct maple_tree *mt, unsigned long index){ void *entry = NULL;
MA_STATE(mas, mt, index, index); trace_ma_op(TP_FCT, &mas);
might_alloc(GFP_KERNEL); mtree_lock(mt); entry = mas_erase(&mas); mtree_unlock(mt);
return entry;}EXPORT_SYMBOL(mtree_erase);
/* * mas_dup_free() - Free an incomplete duplication of a tree. * @mas: The maple state of a incomplete tree. * * The parameter @mas->node passed in indicates that the allocation failed on * this node. This function frees all nodes starting from @mas->node in the * reverse order of mas_dup_build(). There is no need to hold the source tree * lock at this time. */static void mas_dup_free(struct ma_state *mas){ struct maple_node *node; enum maple_type type; void __rcu **slots; unsigned char count, i;
/* Maybe the first node allocation failed. */ if (mas_is_none(mas)) return;
while (!mte_is_root(mas->node)) { mas_ascend(mas); if (mas->offset) { mas->offset--; do { mas_descend(mas); mas->offset = mas_data_end(mas); } while (!mte_is_leaf(mas->node));
mas_ascend(mas); }
node = mte_to_node(mas->node); type = mte_node_type(mas->node); slots = ma_slots(node, type); count = mas_data_end(mas) + 1; for (i = 0; i < count; i++) ((unsigned long *)slots)[i] &= ~MAPLE_NODE_MASK; mt_free_bulk(count, slots); }
node = mte_to_node(mas->node); kfree(node);}
/* * mas_copy_node() - Copy a maple node and replace the parent. * @mas: The maple state of source tree. * @new_mas: The maple state of new tree. * @parent: The parent of the new node. * * Copy @mas->node to @new_mas->node, set @parent to be the parent of * @new_mas->node. If memory allocation fails, @mas is set to -ENOMEM. */static inline void mas_copy_node(struct ma_state *mas, struct ma_state *new_mas, struct maple_pnode *parent){ struct maple_node *node = mte_to_node(mas->node); struct maple_node *new_node = mte_to_node(new_mas->node); unsigned long val;
/* Copy the node completely. */ memcpy(new_node, node, sizeof(struct maple_node)); /* Update the parent node pointer. */ val = (unsigned long)node->parent & MAPLE_NODE_MASK; new_node->parent = ma_parent_ptr(val | (unsigned long)parent);}
/* * mas_dup_alloc() - Allocate child nodes for a maple node. * @mas: The maple state of source tree. * @new_mas: The maple state of new tree. * @gfp: The GFP_FLAGS to use for allocations. * * This function allocates child nodes for @new_mas->node during the duplication * process. If memory allocation fails, @mas is set to -ENOMEM. */static inline void mas_dup_alloc(struct ma_state *mas, struct ma_state *new_mas, gfp_t gfp){ struct maple_node *node = mte_to_node(mas->node); struct maple_node *new_node = mte_to_node(new_mas->node); enum maple_type type; unsigned char count, i; void __rcu **slots; void __rcu **new_slots; unsigned long val;
/* Allocate memory for child nodes. */ type = mte_node_type(mas->node); new_slots = ma_slots(new_node, type); count = mas->node_request = mas_data_end(mas) + 1; mas_alloc_nodes(mas, gfp); if (unlikely(mas_is_err(mas))) return;
slots = ma_slots(node, type); for (i = 0; i < count; i++) { val = (unsigned long)mt_slot_locked(mas->tree, slots, i); val &= MAPLE_NODE_MASK; /* * Warning, see rcu_assign_pointer() documentation. Since this * is a duplication of a tree, there are no readers walking the * tree until after the rcu_assign_pointer() call in * mas_dup_build(). */ RCU_INIT_POINTER(new_slots[i], ma_mnode_ptr((unsigned long)mas_pop_node(mas) | val)); }}
/* * mas_dup_build() - Build a new maple tree from a source tree * @mas: The maple state of source tree, need to be in MAS_START state. * @new_mas: The maple state of new tree, need to be in MAS_START state. * @gfp: The GFP_FLAGS to use for allocations. * * This function builds a new tree in DFS preorder. If the memory allocation * fails, the error code -ENOMEM will be set in @mas, and @new_mas points to the * last node. mas_dup_free() will free the incomplete duplication of a tree. * * Note that the attributes of the two trees need to be exactly the same, and the * new tree needs to be empty, otherwise -EINVAL will be set in @mas. */static inline void mas_dup_build(struct ma_state *mas, struct ma_state *new_mas, gfp_t gfp){ struct maple_node *node; struct maple_pnode *parent = NULL; struct maple_enode *root; enum maple_type type;
if (unlikely(mt_attr(mas->tree) != mt_attr(new_mas->tree)) || unlikely(!mtree_empty(new_mas->tree))) { mas_set_err(mas, -EINVAL); return; }
root = mas_start(mas); if (mas_is_ptr(mas) || mas_is_none(mas)) goto set_new_tree;
node = mt_alloc_one(gfp); if (!node) { new_mas->status = ma_none; mas_set_err(mas, -ENOMEM); return; }
type = mte_node_type(mas->node); root = mt_mk_node(node, type); new_mas->node = root; new_mas->min = 0; new_mas->max = ULONG_MAX; root = mte_mk_root(root); while (1) { mas_copy_node(mas, new_mas, parent); if (!mte_is_leaf(mas->node)) { /* Only allocate child nodes for non-leaf nodes. */ mas_dup_alloc(mas, new_mas, gfp); if (unlikely(mas_is_err(mas))) goto empty_mas; } else { /* * This is the last leaf node and duplication is * completed. */ if (mas->max == ULONG_MAX) goto done;
/* This is not the last leaf node and needs to go up. */ do { mas_ascend(mas); mas_ascend(new_mas); } while (mas->offset == mas_data_end(mas));
/* Move to the next subtree. */ mas->offset++; new_mas->offset++; }
mas_descend(mas); parent = ma_parent_ptr(mte_to_node(new_mas->node)); mas_descend(new_mas); mas->offset = 0; new_mas->offset = 0; }done: /* Specially handle the parent of the root node. */ mte_to_node(root)->parent = ma_parent_ptr(mas_tree_parent(new_mas));set_new_tree: /* Make them the same height */ new_mas->tree->ma_flags = mas->tree->ma_flags; rcu_assign_pointer(new_mas->tree->ma_root, root);empty_mas: mas_empty_nodes(mas);}
/** * __mt_dup(): Duplicate an entire maple tree * @mt: The source maple tree * @new: The new maple tree * @gfp: The GFP_FLAGS to use for allocations * * This function duplicates a maple tree in Depth-First Search (DFS) pre-order * traversal. It uses memcpy() to copy nodes in the source tree and allocate * new child nodes in non-leaf nodes. The new node is exactly the same as the * source node except for all the addresses stored in it. It will be faster than * traversing all elements in the source tree and inserting them one by one into * the new tree. * The user needs to ensure that the attributes of the source tree and the new * tree are the same, and the new tree needs to be an empty tree, otherwise * -EINVAL will be returned. * Note that the user needs to manually lock the source tree and the new tree. * * Return: 0 on success, -ENOMEM if memory could not be allocated, -EINVAL If * the attributes of the two trees are different or the new tree is not an empty * tree. */int __mt_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp){ int ret = 0; MA_STATE(mas, mt, 0, 0); MA_STATE(new_mas, new, 0, 0);
mas_dup_build(&mas, &new_mas, gfp); if (unlikely(mas_is_err(&mas))) { ret = xa_err(mas.node); if (ret == -ENOMEM) mas_dup_free(&new_mas); }
return ret;}EXPORT_SYMBOL(__mt_dup);
/** * mtree_dup(): Duplicate an entire maple tree * @mt: The source maple tree * @new: The new maple tree * @gfp: The GFP_FLAGS to use for allocations * * This function duplicates a maple tree in Depth-First Search (DFS) pre-order * traversal. It uses memcpy() to copy nodes in the source tree and allocate * new child nodes in non-leaf nodes. The new node is exactly the same as the * source node except for all the addresses stored in it. It will be faster than * traversing all elements in the source tree and inserting them one by one into * the new tree. * The user needs to ensure that the attributes of the source tree and the new * tree are the same, and the new tree needs to be an empty tree, otherwise * -EINVAL will be returned. * * Return: 0 on success, -ENOMEM if memory could not be allocated, -EINVAL If * the attributes of the two trees are different or the new tree is not an empty * tree. */int mtree_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp){ int ret = 0; MA_STATE(mas, mt, 0, 0); MA_STATE(new_mas, new, 0, 0);
mas_lock(&new_mas); mas_lock_nested(&mas, SINGLE_DEPTH_NESTING); mas_dup_build(&mas, &new_mas, gfp); mas_unlock(&mas); if (unlikely(mas_is_err(&mas))) { ret = xa_err(mas.node); if (ret == -ENOMEM) mas_dup_free(&new_mas); }
mas_unlock(&new_mas); return ret;}EXPORT_SYMBOL(mtree_dup);
/** * __mt_destroy() - Walk and free all nodes of a locked maple tree. * @mt: The maple tree * * Note: Does not handle locking. */void __mt_destroy(struct maple_tree *mt){ void *root = mt_root_locked(mt);
rcu_assign_pointer(mt->ma_root, NULL); if (xa_is_node(root)) mte_destroy_walk(root, mt);
mt->ma_flags = mt_attr(mt);}EXPORT_SYMBOL_GPL(__mt_destroy);
/** * mtree_destroy() - Destroy a maple tree * @mt: The maple tree * * Frees all resources used by the tree. Handles locking. */void mtree_destroy(struct maple_tree *mt){ mtree_lock(mt); __mt_destroy(mt); mtree_unlock(mt);}EXPORT_SYMBOL(mtree_destroy);
/** * mt_find() - Search from the start up until an entry is found. * @mt: The maple tree * @index: Pointer which contains the start location of the search * @max: The maximum value of the search range * * Takes RCU read lock internally to protect the search, which does not * protect the returned pointer after dropping RCU read lock. * See also: Documentation/core-api/maple_tree.rst * * In case that an entry is found @index is updated to point to the next * possible entry independent whether the found entry is occupying a * single index or a range if indices. * * Return: The entry at or after the @index or %NULL */void *mt_find(struct maple_tree *mt, unsigned long *index, unsigned long max){ MA_STATE(mas, mt, *index, *index); void *entry;#ifdef CONFIG_DEBUG_MAPLE_TREE unsigned long copy = *index;#endif
trace_ma_read(TP_FCT, &mas);
if ((*index) > max) return NULL;
rcu_read_lock();retry: entry = mas_state_walk(&mas); if (mas_is_start(&mas)) goto retry;
if (unlikely(xa_is_zero(entry))) entry = NULL;
if (entry) goto unlock;
while (mas_is_active(&mas) && (mas.last < max)) { entry = mas_next_slot(&mas, max, false); if (likely(entry && !xa_is_zero(entry))) break; }
if (unlikely(xa_is_zero(entry))) entry = NULL;unlock: rcu_read_unlock(); if (likely(entry)) { *index = mas.last + 1;#ifdef CONFIG_DEBUG_MAPLE_TREE if (MT_WARN_ON(mt, (*index) && ((*index) <= copy))) pr_err("index not increased! %lx <= %lx\n", *index, copy);#endif }
return entry;}EXPORT_SYMBOL(mt_find);
/** * mt_find_after() - Search from the start up until an entry is found. * @mt: The maple tree * @index: Pointer which contains the start location of the search * @max: The maximum value to check * * Same as mt_find() except that it checks @index for 0 before * searching. If @index == 0, the search is aborted. This covers a wrap * around of @index to 0 in an iterator loop. * * Return: The entry at or after the @index or %NULL */void *mt_find_after(struct maple_tree *mt, unsigned long *index, unsigned long max){ if (!(*index)) return NULL;
return mt_find(mt, index, max);}EXPORT_SYMBOL(mt_find_after);
#ifdef CONFIG_DEBUG_MAPLE_TREEatomic_t maple_tree_tests_run;EXPORT_SYMBOL_GPL(maple_tree_tests_run);atomic_t maple_tree_tests_passed;EXPORT_SYMBOL_GPL(maple_tree_tests_passed);
#ifndef __KERNEL__extern void kmem_cache_set_non_kernel(struct kmem_cache *, unsigned int);void mt_set_non_kernel(unsigned int val){ kmem_cache_set_non_kernel(maple_node_cache, val);}
extern void kmem_cache_set_callback(struct kmem_cache *cachep, void (*callback)(void *));void mt_set_callback(void (*callback)(void *)){ kmem_cache_set_callback(maple_node_cache, callback);}
extern void kmem_cache_set_private(struct kmem_cache *cachep, void *private);void mt_set_private(void *private){ kmem_cache_set_private(maple_node_cache, private);}
extern unsigned long kmem_cache_get_alloc(struct kmem_cache *);unsigned long mt_get_alloc_size(void){ return kmem_cache_get_alloc(maple_node_cache);}
extern void kmem_cache_zero_nr_tallocated(struct kmem_cache *);void mt_zero_nr_tallocated(void){ kmem_cache_zero_nr_tallocated(maple_node_cache);}
extern unsigned int kmem_cache_nr_tallocated(struct kmem_cache *);unsigned int mt_nr_tallocated(void){ return kmem_cache_nr_tallocated(maple_node_cache);}
extern unsigned int kmem_cache_nr_allocated(struct kmem_cache *);unsigned int mt_nr_allocated(void){ return kmem_cache_nr_allocated(maple_node_cache);}
void mt_cache_shrink(void){}#else/* * mt_cache_shrink() - For testing, don't use this. * * Certain testcases can trigger an OOM when combined with other memory * debugging configuration options. This function is used to reduce the * possibility of an out of memory even due to kmem_cache objects remaining * around for longer than usual. */void mt_cache_shrink(void){ kmem_cache_shrink(maple_node_cache);
}EXPORT_SYMBOL_GPL(mt_cache_shrink);
#endif /* not defined __KERNEL__ *//* * mas_get_slot() - Get the entry in the maple state node stored at @offset. * @mas: The maple state * @offset: The offset into the slot array to fetch. * * Return: The entry stored at @offset. */static inline struct maple_enode *mas_get_slot(struct ma_state *mas, unsigned char offset){ return mas_slot(mas, ma_slots(mas_mn(mas), mte_node_type(mas->node)), offset);}
/* Depth first search, post-order */static void mas_dfs_postorder(struct ma_state *mas, unsigned long max){
struct maple_enode *p, *mn = mas->node; unsigned long p_min, p_max;
mas_next_node(mas, mas_mn(mas), max); if (!mas_is_overflow(mas)) return;
if (mte_is_root(mn)) return;
mas->node = mn; mas_ascend(mas); do { p = mas->node; p_min = mas->min; p_max = mas->max; mas_prev_node(mas, 0); } while (!mas_is_underflow(mas));
mas->node = p; mas->max = p_max; mas->min = p_min;}
/* Tree validations */static void mt_dump_node(const struct maple_tree *mt, void *entry, unsigned long min, unsigned long max, unsigned int depth, enum mt_dump_format format);static void mt_dump_range(unsigned long min, unsigned long max, unsigned int depth, enum mt_dump_format format){ static const char spaces[] = " ";
switch (format) { case mt_dump_hex: if (min == max) pr_info("%.*s%lx: ", depth * 2, spaces, min); else pr_info("%.*s%lx-%lx: ", depth * 2, spaces, min, max); break; case mt_dump_dec: if (min == max) pr_info("%.*s%lu: ", depth * 2, spaces, min); else pr_info("%.*s%lu-%lu: ", depth * 2, spaces, min, max); }}
static void mt_dump_entry(void *entry, unsigned long min, unsigned long max, unsigned int depth, enum mt_dump_format format){ mt_dump_range(min, max, depth, format);
if (xa_is_value(entry)) pr_cont("value %ld (0x%lx) [" PTR_FMT "]\n", xa_to_value(entry), xa_to_value(entry), entry); else if (xa_is_zero(entry)) pr_cont("zero (%ld)\n", xa_to_internal(entry)); else if (mt_is_reserved(entry)) pr_cont("UNKNOWN ENTRY (" PTR_FMT ")\n", entry); else pr_cont(PTR_FMT "\n", entry);}
static void mt_dump_range64(const struct maple_tree *mt, void *entry, unsigned long min, unsigned long max, unsigned int depth, enum mt_dump_format format){ struct maple_range_64 *node = &mte_to_node(entry)->mr64; bool leaf = mte_is_leaf(entry); unsigned long first = min; int i;
pr_cont(" contents: "); for (i = 0; i < MAPLE_RANGE64_SLOTS - 1; i++) { switch (format) { case mt_dump_hex: pr_cont(PTR_FMT " %lX ", node->slot[i], node->pivot[i]); break; case mt_dump_dec: pr_cont(PTR_FMT " %lu ", node->slot[i], node->pivot[i]); } } pr_cont(PTR_FMT "\n", node->slot[i]); for (i = 0; i < MAPLE_RANGE64_SLOTS; i++) { unsigned long last = max;
if (i < (MAPLE_RANGE64_SLOTS - 1)) last = node->pivot[i]; else if (!node->slot[i] && max != mt_node_max(entry)) break; if (last == 0 && i > 0) break; if (leaf) mt_dump_entry(mt_slot(mt, node->slot, i), first, last, depth + 1, format); else if (node->slot[i]) mt_dump_node(mt, mt_slot(mt, node->slot, i), first, last, depth + 1, format);
if (last == max) break; if (last > max) { switch (format) { case mt_dump_hex: pr_err("node " PTR_FMT " last (%lx) > max (%lx) at pivot %d!\n", node, last, max, i); break; case mt_dump_dec: pr_err("node " PTR_FMT " last (%lu) > max (%lu) at pivot %d!\n", node, last, max, i); } } first = last + 1; }}
static void mt_dump_arange64(const struct maple_tree *mt, void *entry, unsigned long min, unsigned long max, unsigned int depth, enum mt_dump_format format){ struct maple_arange_64 *node = &mte_to_node(entry)->ma64; unsigned long first = min; int i;
pr_cont(" contents: "); for (i = 0; i < MAPLE_ARANGE64_SLOTS; i++) { switch (format) { case mt_dump_hex: pr_cont("%lx ", node->gap[i]); break; case mt_dump_dec: pr_cont("%lu ", node->gap[i]); } } pr_cont("| %02X %02X| ", node->meta.end, node->meta.gap); for (i = 0; i < MAPLE_ARANGE64_SLOTS - 1; i++) { switch (format) { case mt_dump_hex: pr_cont(PTR_FMT " %lX ", node->slot[i], node->pivot[i]); break; case mt_dump_dec: pr_cont(PTR_FMT " %lu ", node->slot[i], node->pivot[i]); } } pr_cont(PTR_FMT "\n", node->slot[i]); for (i = 0; i < MAPLE_ARANGE64_SLOTS; i++) { unsigned long last = max;
if (i < (MAPLE_ARANGE64_SLOTS - 1)) last = node->pivot[i]; else if (!node->slot[i]) break; if (last == 0 && i > 0) break; if (node->slot[i]) mt_dump_node(mt, mt_slot(mt, node->slot, i), first, last, depth + 1, format);
if (last == max) break; if (last > max) { switch (format) { case mt_dump_hex: pr_err("node " PTR_FMT " last (%lx) > max (%lx) at pivot %d!\n", node, last, max, i); break; case mt_dump_dec: pr_err("node " PTR_FMT " last (%lu) > max (%lu) at pivot %d!\n", node, last, max, i); } } first = last + 1; }}
static void mt_dump_node(const struct maple_tree *mt, void *entry, unsigned long min, unsigned long max, unsigned int depth, enum mt_dump_format format){ struct maple_node *node = mte_to_node(entry); unsigned int type = mte_node_type(entry); unsigned int i;
mt_dump_range(min, max, depth, format);
pr_cont("node " PTR_FMT " depth %d type %d parent " PTR_FMT, node, depth, type, node ? node->parent : NULL); switch (type) { case maple_dense: pr_cont("\n"); for (i = 0; i < MAPLE_NODE_SLOTS; i++) { if (min + i > max) pr_cont("OUT OF RANGE: "); mt_dump_entry(mt_slot(mt, node->slot, i), min + i, min + i, depth, format); } break; case maple_leaf_64: case maple_range_64: mt_dump_range64(mt, entry, min, max, depth, format); break; case maple_arange_64: mt_dump_arange64(mt, entry, min, max, depth, format); break;
default: pr_cont(" UNKNOWN TYPE\n"); }}
void mt_dump(const struct maple_tree *mt, enum mt_dump_format format){ void *entry = rcu_dereference_check(mt->ma_root, mt_locked(mt));
pr_info("maple_tree(" PTR_FMT ") flags %X, height %u root " PTR_FMT "\n", mt, mt->ma_flags, mt_height(mt), entry); if (xa_is_node(entry)) mt_dump_node(mt, entry, 0, mt_node_max(entry), 0, format); else if (entry) mt_dump_entry(entry, 0, 0, 0, format); else pr_info("(empty)\n");}EXPORT_SYMBOL_GPL(mt_dump);
/* * Calculate the maximum gap in a node and check if that's what is reported in * the parent (unless root). */static void mas_validate_gaps(struct ma_state *mas){ struct maple_enode *mte = mas->node; struct maple_node *p_mn, *node = mte_to_node(mte); enum maple_type mt = mte_node_type(mas->node); unsigned long gap = 0, max_gap = 0; unsigned long p_end, p_start = mas->min; unsigned char p_slot, offset; unsigned long *gaps = NULL; unsigned long *pivots = ma_pivots(node, mt); unsigned int i;
if (ma_is_dense(mt)) { for (i = 0; i < mt_slot_count(mte); i++) { if (mas_get_slot(mas, i)) { if (gap > max_gap) max_gap = gap; gap = 0; continue; } gap++; } goto counted; }
gaps = ma_gaps(node, mt); for (i = 0; i < mt_slot_count(mte); i++) { p_end = mas_safe_pivot(mas, pivots, i, mt);
if (!gaps) { if (!mas_get_slot(mas, i)) gap = p_end - p_start + 1; } else { void *entry = mas_get_slot(mas, i);
gap = gaps[i]; MT_BUG_ON(mas->tree, !entry);
if (gap > p_end - p_start + 1) { pr_err(PTR_FMT "[%u] %lu >= %lu - %lu + 1 (%lu)\n", mas_mn(mas), i, gap, p_end, p_start, p_end - p_start + 1); MT_BUG_ON(mas->tree, gap > p_end - p_start + 1); } }
if (gap > max_gap) max_gap = gap;
p_start = p_end + 1; if (p_end >= mas->max) break; }
counted: if (mt == maple_arange_64) { MT_BUG_ON(mas->tree, !gaps); offset = ma_meta_gap(node); if (offset > i) { pr_err("gap offset " PTR_FMT "[%u] is invalid\n", node, offset); MT_BUG_ON(mas->tree, 1); }
if (gaps[offset] != max_gap) { pr_err("gap " PTR_FMT "[%u] is not the largest gap %lu\n", node, offset, max_gap); MT_BUG_ON(mas->tree, 1); }
for (i++ ; i < mt_slot_count(mte); i++) { if (gaps[i] != 0) { pr_err("gap " PTR_FMT "[%u] beyond node limit != 0\n", node, i); MT_BUG_ON(mas->tree, 1); } } }
if (mte_is_root(mte)) return;
p_slot = mte_parent_slot(mas->node); p_mn = mte_parent(mte); MT_BUG_ON(mas->tree, max_gap > mas->max); if (ma_gaps(p_mn, mas_parent_type(mas, mte))[p_slot] != max_gap) { pr_err("gap " PTR_FMT "[%u] != %lu\n", p_mn, p_slot, max_gap); mt_dump(mas->tree, mt_dump_hex); MT_BUG_ON(mas->tree, 1); }}
static void mas_validate_parent_slot(struct ma_state *mas){ struct maple_node *parent; struct maple_enode *node; enum maple_type p_type; unsigned char p_slot; void __rcu **slots; int i;
if (mte_is_root(mas->node)) return;
p_slot = mte_parent_slot(mas->node); p_type = mas_parent_type(mas, mas->node); parent = mte_parent(mas->node); slots = ma_slots(parent, p_type); MT_BUG_ON(mas->tree, mas_mn(mas) == parent);
/* Check prev/next parent slot for duplicate node entry */
for (i = 0; i < mt_slots[p_type]; i++) { node = mas_slot(mas, slots, i); if (i == p_slot) { if (node != mas->node) pr_err("parent " PTR_FMT "[%u] does not have " PTR_FMT "\n", parent, i, mas_mn(mas)); MT_BUG_ON(mas->tree, node != mas->node); } else if (node == mas->node) { pr_err("Invalid child " PTR_FMT " at parent " PTR_FMT "[%u] p_slot %u\n", mas_mn(mas), parent, i, p_slot); MT_BUG_ON(mas->tree, node == mas->node); } }}
static void mas_validate_child_slot(struct ma_state *mas){ enum maple_type type = mte_node_type(mas->node); void __rcu **slots = ma_slots(mte_to_node(mas->node), type); unsigned long *pivots = ma_pivots(mte_to_node(mas->node), type); struct maple_enode *child; unsigned char i;
if (mte_is_leaf(mas->node)) return;
for (i = 0; i < mt_slots[type]; i++) { child = mas_slot(mas, slots, i);
if (!child) { pr_err("Non-leaf node lacks child at " PTR_FMT "[%u]\n", mas_mn(mas), i); MT_BUG_ON(mas->tree, 1); }
if (mte_parent_slot(child) != i) { pr_err("Slot error at " PTR_FMT "[%u]: child " PTR_FMT " has pslot %u\n", mas_mn(mas), i, mte_to_node(child), mte_parent_slot(child)); MT_BUG_ON(mas->tree, 1); }
if (mte_parent(child) != mte_to_node(mas->node)) { pr_err("child " PTR_FMT " has parent " PTR_FMT " not " PTR_FMT "\n", mte_to_node(child), mte_parent(child), mte_to_node(mas->node)); MT_BUG_ON(mas->tree, 1); }
if (i < mt_pivots[type] && pivots[i] == mas->max) break; }}
/* * Validate all pivots are within mas->min and mas->max, check metadata ends * where the maximum ends and ensure there is no slots or pivots set outside of * the end of the data. */static void mas_validate_limits(struct ma_state *mas){ int i; unsigned long prev_piv = 0; enum maple_type type = mte_node_type(mas->node); void __rcu **slots = ma_slots(mte_to_node(mas->node), type); unsigned long *pivots = ma_pivots(mas_mn(mas), type);
for (i = 0; i < mt_slots[type]; i++) { unsigned long piv;
piv = mas_safe_pivot(mas, pivots, i, type);
if (!piv && (i != 0)) { pr_err("Missing node limit pivot at " PTR_FMT "[%u]", mas_mn(mas), i); MAS_WARN_ON(mas, 1); }
if (prev_piv > piv) { pr_err(PTR_FMT "[%u] piv %lu < prev_piv %lu\n", mas_mn(mas), i, piv, prev_piv); MAS_WARN_ON(mas, piv < prev_piv); }
if (piv < mas->min) { pr_err(PTR_FMT "[%u] %lu < %lu\n", mas_mn(mas), i, piv, mas->min); MAS_WARN_ON(mas, piv < mas->min); } if (piv > mas->max) { pr_err(PTR_FMT "[%u] %lu > %lu\n", mas_mn(mas), i, piv, mas->max); MAS_WARN_ON(mas, piv > mas->max); } prev_piv = piv; if (piv == mas->max) break; }
if (mas_data_end(mas) != i) { pr_err("node" PTR_FMT ": data_end %u != the last slot offset %u\n", mas_mn(mas), mas_data_end(mas), i); MT_BUG_ON(mas->tree, 1); }
for (i += 1; i < mt_slots[type]; i++) { void *entry = mas_slot(mas, slots, i);
if (entry && (i != mt_slots[type] - 1)) { pr_err(PTR_FMT "[%u] should not have entry " PTR_FMT "\n", mas_mn(mas), i, entry); MT_BUG_ON(mas->tree, entry != NULL); }
if (i < mt_pivots[type]) { unsigned long piv = pivots[i];
if (!piv) continue;
pr_err(PTR_FMT "[%u] should not have piv %lu\n", mas_mn(mas), i, piv); MAS_WARN_ON(mas, i < mt_pivots[type] - 1); } }}
static void mt_validate_nulls(struct maple_tree *mt){ void *entry, *last = (void *)1; unsigned char offset = 0; void __rcu **slots; MA_STATE(mas, mt, 0, 0);
mas_start(&mas); if (mas_is_none(&mas) || (mas_is_ptr(&mas))) return;
while (!mte_is_leaf(mas.node)) mas_descend(&mas);
slots = ma_slots(mte_to_node(mas.node), mte_node_type(mas.node)); do { entry = mas_slot(&mas, slots, offset); if (!last && !entry) { pr_err("Sequential nulls end at " PTR_FMT "[%u]\n", mas_mn(&mas), offset); } MT_BUG_ON(mt, !last && !entry); last = entry; if (offset == mas_data_end(&mas)) { mas_next_node(&mas, mas_mn(&mas), ULONG_MAX); if (mas_is_overflow(&mas)) return; offset = 0; slots = ma_slots(mte_to_node(mas.node), mte_node_type(mas.node)); } else { offset++; }
} while (!mas_is_overflow(&mas));}
/* * validate a maple tree by checking: * 1. The limits (pivots are within mas->min to mas->max) * 2. The gap is correctly set in the parents */void mt_validate(struct maple_tree *mt) __must_hold(mas->tree->ma_lock){ unsigned char end;
MA_STATE(mas, mt, 0, 0); mas_start(&mas); if (!mas_is_active(&mas)) return;
while (!mte_is_leaf(mas.node)) mas_descend(&mas);
while (!mas_is_overflow(&mas)) { MAS_WARN_ON(&mas, mte_dead_node(mas.node)); end = mas_data_end(&mas); if (MAS_WARN_ON(&mas, (end < mt_min_slot_count(mas.node)) && (!mte_is_root(mas.node)))) { pr_err("Invalid size %u of " PTR_FMT "\n", end, mas_mn(&mas)); }
mas_validate_parent_slot(&mas); mas_validate_limits(&mas); mas_validate_child_slot(&mas); if (mt_is_alloc(mt)) mas_validate_gaps(&mas); mas_dfs_postorder(&mas, ULONG_MAX); } mt_validate_nulls(mt);}EXPORT_SYMBOL_GPL(mt_validate);
void mas_dump(const struct ma_state *mas){ pr_err("MAS: tree=" PTR_FMT " enode=" PTR_FMT " ", mas->tree, mas->node); switch (mas->status) { case ma_active: pr_err("(ma_active)"); break; case ma_none: pr_err("(ma_none)"); break; case ma_root: pr_err("(ma_root)"); break; case ma_start: pr_err("(ma_start) "); break; case ma_pause: pr_err("(ma_pause) "); break; case ma_overflow: pr_err("(ma_overflow) "); break; case ma_underflow: pr_err("(ma_underflow) "); break; case ma_error: pr_err("(ma_error) "); break; }
pr_err("Store Type: "); switch (mas->store_type) { case wr_invalid: pr_err("invalid store type\n"); break; case wr_new_root: pr_err("new_root\n"); break; case wr_store_root: pr_err("store_root\n"); break; case wr_exact_fit: pr_err("exact_fit\n"); break; case wr_split_store: pr_err("split_store\n"); break; case wr_slot_store: pr_err("slot_store\n"); break; case wr_append: pr_err("append\n"); break; case wr_node_store: pr_err("node_store\n"); break; case wr_spanning_store: pr_err("spanning_store\n"); break; case wr_rebalance: pr_err("rebalance\n"); break; }
pr_err("[%u/%u] index=%lx last=%lx\n", mas->offset, mas->end, mas->index, mas->last); pr_err(" min=%lx max=%lx sheaf=" PTR_FMT ", request %lu depth=%u, flags=%x\n", mas->min, mas->max, mas->sheaf, mas->node_request, mas->depth, mas->mas_flags); if (mas->index > mas->last) pr_err("Check index & last\n");}EXPORT_SYMBOL_GPL(mas_dump);
void mas_wr_dump(const struct ma_wr_state *wr_mas){ pr_err("WR_MAS: node=" PTR_FMT " r_min=%lx r_max=%lx\n", wr_mas->node, wr_mas->r_min, wr_mas->r_max); pr_err(" type=%u off_end=%u, node_end=%u, end_piv=%lx\n", wr_mas->type, wr_mas->offset_end, wr_mas->mas->end, wr_mas->end_piv);}EXPORT_SYMBOL_GPL(mas_wr_dump);
#endif /* CONFIG_DEBUG_MAPLE_TREE */