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.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845184618471848184918501851185218531854185518561857185818591860186118621863186418651866186718681869187018711872187318741875187618771878187918801881188218831884188518861887188818891890189118921893189418951896189718981899190019011902190319041905190619071908190919101911191219131914191519161917191819191920192119221923192419251926192719281929193019311932193319341935193619371938193919401941194219431944194519461947194819491950195119521953195419551956195719581959196019611962196319641965196619671968196919701971197219731974197519761977197819791980198119821983198419851986198719881989199019911992199319941995199619971998199920002001200220032004200520062007200820092010201120122013201420152016201720182019202020212022202320242025202620272028202920302031203220332034203520362037203820392040204120422043204420452046204720482049205020512052205320542055205620572058205920602061206220632064206520662067206820692070207120722073207420752076207720782079208020812082208320842085208620872088208920902091209220932094209520962097209820992100210121022103210421052106210721082109211021112112211321142115211621172118211921202121212221232124212521262127212821292130213121322133213421352136213721382139214021412142214321442145214621472148214921502151215221532154215521562157215821592160216121622163216421652166216721682169217021712172217321742175217621772178217921802181218221832184218521862187218821892190219121922193219421952196219721982199220022012202220322042205220622072208220922102211221222132214221522162217221822192220222122222223222422252226222722282229223022312232223322342235223622372238223922402241224222432244224522462247224822492250225122522253225422552256225722582259226022612262226322642265226622672268226922702271227222732274227522762277227822792280228122822283228422852286228722882289229022912292229322942295229622972298229923002301230223032304230523062307230823092310231123122313231423152316231723182319232023212322232323242325232623272328232923302331233223332334233523362337233823392340234123422343234423452346234723482349235023512352235323542355235623572358235923602361236223632364236523662367236823692370237123722373237423752376237723782379238023812382238323842385238623872388238923902391239223932394239523962397239823992400240124022403240424052406240724082409241024112412241324142415241624172418241924202421242224232424242524262427242824292430243124322433243424352436243724382439244024412442244324442445244624472448244924502451245224532454245524562457245824592460246124622463246424652466246724682469247024712472247324742475247624772478247924802481248224832484248524862487248824892490249124922493249424952496249724982499250025012502250325042505250625072508250925102511251225132514251525162517251825192520252125222523252425252526252725282529253025312532253325342535253625372538253925402541254225432544254525462547254825492550255125522553255425552556255725582559256025612562256325642565256625672568256925702571257225732574257525762577257825792580258125822583258425852586258725882589259025912592259325942595259625972598259926002601260226032604260526062607260826092610261126122613261426152616261726182619262026212622262326242625262626272628262926302631263226332634263526362637263826392640264126422643264426452646264726482649265026512652265326542655265626572658265926602661266226632664266526662667266826692670267126722673267426752676267726782679268026812682268326842685268626872688268926902691269226932694269526962697269826992700270127022703270427052706270727082709271027112712271327142715271627172718271927202721272227232724272527262727272827292730273127322733273427352736273727382739274027412742274327442745274627472748274927502751275227532754275527562757275827592760276127622763276427652766276727682769277027712772277327742775277627772778277927802781278227832784278527862787278827892790279127922793279427952796279727982799280028012802280328042805280628072808280928102811281228132814281528162817281828192820282128222823282428252826282728282829283028312832283328342835283628372838283928402841284228432844284528462847284828492850285128522853285428552856285728582859286028612862286328642865286628672868286928702871287228732874287528762877287828792880288128822883288428852886288728882889289028912892289328942895289628972898289929002901290229032904290529062907290829092910291129122913291429152916291729182919292029212922292329242925292629272928292929302931293229332934293529362937293829392940294129422943294429452946294729482949295029512952295329542955295629572958295929602961296229632964296529662967296829692970297129722973297429752976297729782979298029812982298329842985298629872988298929902991299229932994299529962997299829993000300130023003300430053006300730083009301030113012301330143015301630173018301930203021302230233024302530263027302830293030303130323033303430353036303730383039304030413042304330443045304630473048304930503051305230533054305530563057305830593060306130623063306430653066306730683069307030713072307330743075307630773078307930803081308230833084308530863087308830893090309130923093309430953096309730983099310031013102310331043105310631073108310931103111311231133114311531163117311831193120312131223123312431253126312731283129313031313132313331343135313631373138313931403141314231433144314531463147314831493150315131523153315431553156315731583159316031613162316331643165316631673168316931703171317231733174317531763177317831793180318131823183318431853186318731883189319031913192319331943195319631973198319932003201320232033204320532063207320832093210321132123213321432153216321732183219322032213222322332243225322632273228322932303231323232333234323532363237323832393240324132423243324432453246324732483249325032513252325332543255325632573258325932603261326232633264326532663267326832693270327132723273327432753276327732783279328032813282328332843285328632873288328932903291329232933294329532963297329832993300330133023303330433053306330733083309331033113312331333143315331633173318331933203321332233233324332533263327332833293330333133323333333433353336333733383339334033413342334333443345334633473348334933503351335233533354335533563357335833593360336133623363336433653366336733683369337033713372337333743375337633773378337933803381338233833384338533863387338833893390339133923393339433953396339733983399340034013402340334043405340634073408340934103411341234133414341534163417341834193420342134223423342434253426342734283429343034313432343334343435343634373438343934403441344234433444344534463447344834493450345134523453345434553456345734583459346034613462346334643465346634673468346934703471347234733474347534763477347834793480348134823483348434853486348734883489349034913492349334943495349634973498349935003501350235033504350535063507350835093510351135123513351435153516351735183519352035213522352335243525352635273528352935303531353235333534353535363537353835393540354135423543354435453546354735483549355035513552355335543555355635573558355935603561356235633564356535663567356835693570357135723573357435753576357735783579358035813582358335843585358635873588358935903591359235933594359535963597359835993600360136023603360436053606360736083609361036113612361336143615361636173618361936203621362236233624362536263627362836293630363136323633363436353636363736383639364036413642364336443645364636473648364936503651365236533654365536563657365836593660366136623663366436653666366736683669367036713672367336743675367636773678367936803681368236833684368536863687368836893690369136923693369436953696369736983699370037013702370337043705370637073708370937103711371237133714371537163717371837193720372137223723372437253726372737283729373037313732373337343735373637373738373937403741374237433744374537463747374837493750375137523753375437553756375737583759376037613762376337643765376637673768376937703771377237733774377537763777377837793780378137823783378437853786378737883789379037913792379337943795379637973798379938003801380238033804380538063807380838093810381138123813381438153816381738183819382038213822382338243825382638273828382938303831383238333834383538363837383838393840384138423843384438453846384738483849385038513852385338543855385638573858385938603861386238633864386538663867386838693870387138723873387438753876387738783879388038813882388338843885388638873888388938903891389238933894389538963897389838993900390139023903390439053906390739083909391039113912391339143915391639173918391939203921392239233924392539263927392839293930393139323933393439353936393739383939394039413942394339443945394639473948394939503951395239533954395539563957395839593960396139623963396439653966396739683969397039713972397339743975397639773978397939803981398239833984398539863987398839893990399139923993399439953996399739983999400040014002400340044005400640074008400940104011401240134014401540164017401840194020402140224023402440254026402740284029403040314032403340344035403640374038403940404041404240434044404540464047404840494050405140524053405440554056405740584059// SPDX-License-Identifier: GPL-2.0+/* * test_maple_tree.c: Test the maple tree API * Copyright (c) 2018-2022 Oracle Corporation * Author: Liam R. Howlett <liam@infradead.org> * * Any tests that only require the interface of the tree. */
#include <linux/maple_tree.h>#include <linux/module.h>#include <linux/rwsem.h>
#define MTREE_ALLOC_MAX 0x2000000000000Ul#define CONFIG_MAPLE_SEARCH#define MAPLE_32BIT (MAPLE_NODE_SLOTS > 31)
#ifndef CONFIG_DEBUG_MAPLE_TREE#define mt_dump(mt, fmt) do {} while (0)#define mt_validate(mt) do {} while (0)#define mt_cache_shrink() do {} while (0)#define mas_dump(mas) do {} while (0)#define mas_wr_dump(mas) do {} while (0)atomic_t maple_tree_tests_run;atomic_t maple_tree_tests_passed;#undef MT_BUG_ON
#define MT_BUG_ON(__tree, __x) do { \ atomic_inc(&maple_tree_tests_run); \ if (__x) { \ pr_info("BUG at %s:%d (%u)\n", \ __func__, __LINE__, __x); \ pr_info("Pass: %u Run:%u\n", \ atomic_read(&maple_tree_tests_passed), \ atomic_read(&maple_tree_tests_run)); \ } else { \ atomic_inc(&maple_tree_tests_passed); \ } \} while (0)#endif
/* #define BENCH_SLOT_STORE *//* #define BENCH_NODE_STORE *//* #define BENCH_AWALK *//* #define BENCH_WALK *//* #define BENCH_LOAD *//* #define BENCH_MT_FOR_EACH *//* #define BENCH_FORK *//* #define BENCH_MAS_FOR_EACH *//* #define BENCH_MAS_PREV */
#ifdef __KERNEL__#define mt_set_non_kernel(x) do {} while (0)#define mt_zero_nr_tallocated(x) do {} while (0)#else#define cond_resched() do {} while (0)#endif
#define mas_is_none(x) ((x)->status == ma_none)#define mas_is_overflow(x) ((x)->status == ma_overflow)#define mas_is_underflow(x) ((x)->status == ma_underflow)
static int __init mtree_insert_index(struct maple_tree *mt, unsigned long index, gfp_t gfp){ return mtree_insert(mt, index, xa_mk_value(index & LONG_MAX), gfp);}
static void __init mtree_erase_index(struct maple_tree *mt, unsigned long index){ MT_BUG_ON(mt, mtree_erase(mt, index) != xa_mk_value(index & LONG_MAX)); MT_BUG_ON(mt, mtree_load(mt, index) != NULL);}
static int __init mtree_test_insert(struct maple_tree *mt, unsigned long index, void *ptr){ return mtree_insert(mt, index, ptr, GFP_KERNEL);}
static int __init mtree_test_store_range(struct maple_tree *mt, unsigned long start, unsigned long end, void *ptr){ return mtree_store_range(mt, start, end, ptr, GFP_KERNEL);}
static int __init mtree_test_store(struct maple_tree *mt, unsigned long start, void *ptr){ return mtree_test_store_range(mt, start, start, ptr);}
static int __init mtree_test_insert_range(struct maple_tree *mt, unsigned long start, unsigned long end, void *ptr){ return mtree_insert_range(mt, start, end, ptr, GFP_KERNEL);}
static void __init *mtree_test_load(struct maple_tree *mt, unsigned long index){ return mtree_load(mt, index);}
static void __init *mtree_test_erase(struct maple_tree *mt, unsigned long index){ return mtree_erase(mt, index);}
#if defined(CONFIG_64BIT)static noinline void __init check_mtree_alloc_range(struct maple_tree *mt, unsigned long start, unsigned long end, unsigned long size, unsigned long expected, int eret, void *ptr){
unsigned long result = expected + 1; int ret;
ret = mtree_alloc_range(mt, &result, ptr, size, start, end, GFP_KERNEL); MT_BUG_ON(mt, ret != eret); if (ret) return;
MT_BUG_ON(mt, result != expected);}
static noinline void __init check_mtree_alloc_rrange(struct maple_tree *mt, unsigned long start, unsigned long end, unsigned long size, unsigned long expected, int eret, void *ptr){
unsigned long result = expected + 1; int ret;
ret = mtree_alloc_rrange(mt, &result, ptr, size, start, end, GFP_KERNEL); MT_BUG_ON(mt, ret != eret); if (ret) return;
MT_BUG_ON(mt, result != expected);}#endif
static noinline void __init check_load(struct maple_tree *mt, unsigned long index, void *ptr){ void *ret = mtree_test_load(mt, index);
if (ret != ptr) pr_err("Load %lu returned %p expect %p\n", index, ret, ptr); MT_BUG_ON(mt, ret != ptr);}
static noinline void __init check_store_range(struct maple_tree *mt, unsigned long start, unsigned long end, void *ptr, int expected){ int ret = -EINVAL; unsigned long i;
ret = mtree_test_store_range(mt, start, end, ptr); MT_BUG_ON(mt, ret != expected);
if (ret) return;
for (i = start; i <= end; i++) check_load(mt, i, ptr);}
static noinline void __init check_insert_range(struct maple_tree *mt, unsigned long start, unsigned long end, void *ptr, int expected){ int ret = -EINVAL; unsigned long i;
ret = mtree_test_insert_range(mt, start, end, ptr); MT_BUG_ON(mt, ret != expected);
if (ret) return;
for (i = start; i <= end; i++) check_load(mt, i, ptr);}
static noinline void __init check_insert(struct maple_tree *mt, unsigned long index, void *ptr){ int ret = -EINVAL;
ret = mtree_test_insert(mt, index, ptr); MT_BUG_ON(mt, ret != 0);}
static noinline void __init check_dup_insert(struct maple_tree *mt, unsigned long index, void *ptr){ int ret = -EINVAL;
ret = mtree_test_insert(mt, index, ptr); MT_BUG_ON(mt, ret != -EEXIST);}
static noinline void __init check_index_load(struct maple_tree *mt, unsigned long index){ return check_load(mt, index, xa_mk_value(index & LONG_MAX));}
static inline __init int not_empty(struct maple_node *node){ int i;
if (node->parent) return 1;
for (i = 0; i < ARRAY_SIZE(node->slot); i++) if (node->slot[i]) return 1;
return 0;}
static noinline void __init check_rev_seq(struct maple_tree *mt, unsigned long max, bool verbose){ unsigned long i = max, j;
MT_BUG_ON(mt, !mtree_empty(mt));
mt_zero_nr_tallocated(); while (i) { MT_BUG_ON(mt, mtree_insert_index(mt, i, GFP_KERNEL)); for (j = i; j <= max; j++) check_index_load(mt, j);
check_load(mt, i - 1, NULL); mt_set_in_rcu(mt); MT_BUG_ON(mt, !mt_height(mt)); mt_clear_in_rcu(mt); MT_BUG_ON(mt, !mt_height(mt)); i--; } check_load(mt, max + 1, NULL);
#ifndef __KERNEL__ if (verbose) { rcu_barrier(); mt_dump(mt, mt_dump_dec); pr_info(" %s test of 0-%lu %luK in %d active (%d total)\n", __func__, max, mt_get_alloc_size()/1024, mt_nr_allocated(), mt_nr_tallocated()); }#endif}
static noinline void __init check_seq(struct maple_tree *mt, unsigned long max, bool verbose){ unsigned long i, j;
MT_BUG_ON(mt, !mtree_empty(mt));
mt_zero_nr_tallocated(); for (i = 0; i <= max; i++) { MT_BUG_ON(mt, mtree_insert_index(mt, i, GFP_KERNEL)); for (j = 0; j <= i; j++) check_index_load(mt, j);
if (i) MT_BUG_ON(mt, !mt_height(mt)); check_load(mt, i + 1, NULL); }
#ifndef __KERNEL__ if (verbose) { rcu_barrier(); mt_dump(mt, mt_dump_dec); pr_info(" seq test of 0-%lu %luK in %d active (%d total)\n", max, mt_get_alloc_size()/1024, mt_nr_allocated(), mt_nr_tallocated()); }#endif}
static noinline void __init check_lb_not_empty(struct maple_tree *mt){ unsigned long i, j; unsigned long huge = 4000UL * 1000 * 1000;
i = huge; while (i > 4096) { check_insert(mt, i, (void *) i); for (j = huge; j >= i; j /= 2) { check_load(mt, j-1, NULL); check_load(mt, j, (void *) j); check_load(mt, j+1, NULL); } i /= 2; } mtree_destroy(mt);}
static noinline void __init check_lower_bound_split(struct maple_tree *mt){ MT_BUG_ON(mt, !mtree_empty(mt)); check_lb_not_empty(mt);}
static noinline void __init check_upper_bound_split(struct maple_tree *mt){ unsigned long i, j; unsigned long huge;
MT_BUG_ON(mt, !mtree_empty(mt));
if (MAPLE_32BIT) huge = 2147483647UL; else huge = 4000UL * 1000 * 1000;
i = 4096; while (i < huge) { check_insert(mt, i, (void *) i); for (j = i; j >= huge; j *= 2) { check_load(mt, j-1, NULL); check_load(mt, j, (void *) j); check_load(mt, j+1, NULL); } i *= 2; } mtree_destroy(mt);}
static noinline void __init check_mid_split(struct maple_tree *mt){ unsigned long huge = 8000UL * 1000 * 1000;
check_insert(mt, huge, (void *) huge); check_insert(mt, 0, xa_mk_value(0)); check_lb_not_empty(mt);}
static noinline void __init check_rev_find(struct maple_tree *mt){ int i, nr_entries = 200; void *val; MA_STATE(mas, mt, 0, 0);
for (i = 0; i <= nr_entries; i++) mtree_store_range(mt, i*10, i*10 + 5, xa_mk_value(i), GFP_KERNEL);
rcu_read_lock(); mas_set(&mas, 1000); val = mas_find_rev(&mas, 1000); MT_BUG_ON(mt, val != xa_mk_value(100)); val = mas_find_rev(&mas, 1000); MT_BUG_ON(mt, val != NULL);
mas_set(&mas, 999); val = mas_find_rev(&mas, 997); MT_BUG_ON(mt, val != NULL);
mas_set(&mas, 1000); val = mas_find_rev(&mas, 900); MT_BUG_ON(mt, val != xa_mk_value(100)); val = mas_find_rev(&mas, 900); MT_BUG_ON(mt, val != xa_mk_value(99));
mas_set(&mas, 20); val = mas_find_rev(&mas, 0); MT_BUG_ON(mt, val != xa_mk_value(2)); val = mas_find_rev(&mas, 0); MT_BUG_ON(mt, val != xa_mk_value(1)); val = mas_find_rev(&mas, 0); MT_BUG_ON(mt, val != xa_mk_value(0)); val = mas_find_rev(&mas, 0); MT_BUG_ON(mt, val != NULL); rcu_read_unlock();}
static noinline void __init check_find(struct maple_tree *mt){ unsigned long val = 0; unsigned long count; unsigned long max; unsigned long top; unsigned long last = 0, index = 0; void *entry, *entry2;
MA_STATE(mas, mt, 0, 0);
/* Insert 0. */ MT_BUG_ON(mt, mtree_insert_index(mt, val++, GFP_KERNEL));
#if defined(CONFIG_64BIT) top = 4398046511104UL;#else top = ULONG_MAX;#endif
if (MAPLE_32BIT) { count = 15; } else { count = 20; }
for (int i = 0; i <= count; i++) { if (val != 64) MT_BUG_ON(mt, mtree_insert_index(mt, val, GFP_KERNEL)); else MT_BUG_ON(mt, mtree_insert(mt, val, XA_ZERO_ENTRY, GFP_KERNEL));
val <<= 2; }
val = 0; mas_set(&mas, val); mas_lock(&mas); while ((entry = mas_find(&mas, 268435456)) != NULL) { if (val != 64) MT_BUG_ON(mt, xa_mk_value(val) != entry); else MT_BUG_ON(mt, entry != XA_ZERO_ENTRY);
val <<= 2; /* For zero check. */ if (!val) val = 1; } mas_unlock(&mas);
val = 0; mas_set(&mas, val); mas_lock(&mas); mas_for_each(&mas, entry, ULONG_MAX) { if (val != 64) MT_BUG_ON(mt, xa_mk_value(val) != entry); else MT_BUG_ON(mt, entry != XA_ZERO_ENTRY); val <<= 2; /* For zero check. */ if (!val) val = 1; } mas_unlock(&mas);
/* Test mas_pause */ val = 0; mas_set(&mas, val); mas_lock(&mas); mas_for_each(&mas, entry, ULONG_MAX) { if (val != 64) MT_BUG_ON(mt, xa_mk_value(val) != entry); else MT_BUG_ON(mt, entry != XA_ZERO_ENTRY); val <<= 2; /* For zero check. */ if (!val) val = 1;
mas_pause(&mas); mas_unlock(&mas); mas_lock(&mas); } mas_unlock(&mas);
val = 0; max = 300; /* A value big enough to include XA_ZERO_ENTRY at 64. */ mt_for_each(mt, entry, index, max) { MT_BUG_ON(mt, xa_mk_value(val) != entry); val <<= 2; if (val == 64) /* Skip zero entry. */ val <<= 2; /* For zero check. */ if (!val) val = 1; }
val = 0; max = 0; index = 0; MT_BUG_ON(mt, mtree_insert_index(mt, ULONG_MAX, GFP_KERNEL)); mt_for_each(mt, entry, index, ULONG_MAX) { if (val == top) MT_BUG_ON(mt, entry != xa_mk_value(LONG_MAX)); else MT_BUG_ON(mt, xa_mk_value(val) != entry);
/* Workaround for 32bit */ if ((val << 2) < val) val = ULONG_MAX; else val <<= 2;
if (val == 64) /* Skip zero entry. */ val <<= 2; /* For zero check. */ if (!val) val = 1; max++; MT_BUG_ON(mt, max > 25); } mtree_erase_index(mt, ULONG_MAX);
mas_reset(&mas); index = 17; entry = mt_find(mt, &index, 512); MT_BUG_ON(mt, xa_mk_value(256) != entry);
mas_reset(&mas); index = 17; entry = mt_find(mt, &index, 20); MT_BUG_ON(mt, entry != NULL);
/* Range check.. */ /* Insert ULONG_MAX */ MT_BUG_ON(mt, mtree_insert_index(mt, ULONG_MAX, GFP_KERNEL));
val = 0; mas_set(&mas, 0); mas_lock(&mas); mas_for_each(&mas, entry, ULONG_MAX) { if (val == 64) MT_BUG_ON(mt, entry != XA_ZERO_ENTRY); else if (val == top) MT_BUG_ON(mt, entry != xa_mk_value(LONG_MAX)); else MT_BUG_ON(mt, xa_mk_value(val) != entry);
/* Workaround for 32bit */ if ((val << 2) < val) val = ULONG_MAX; else val <<= 2;
/* For zero check. */ if (!val) val = 1; mas_pause(&mas); mas_unlock(&mas); mas_lock(&mas); } mas_unlock(&mas);
mas_set(&mas, 1048576); mas_lock(&mas); entry = mas_find(&mas, 1048576); mas_unlock(&mas); MT_BUG_ON(mas.tree, entry == NULL);
/* * Find last value. * 1. get the expected value, leveraging the existence of an end entry * 2. delete end entry * 3. find the last value but searching for ULONG_MAX and then using * prev */ /* First, get the expected result. */ mas_lock(&mas); mas_reset(&mas); mas.index = ULONG_MAX; /* start at max.. */ entry = mas_find(&mas, ULONG_MAX); entry = mas_prev(&mas, 0); index = mas.index; last = mas.last;
/* Erase the last entry. */ mas_reset(&mas); mas.index = ULONG_MAX; mas.last = ULONG_MAX; mas_erase(&mas);
/* Get the previous value from MAS_START */ mas_reset(&mas); entry2 = mas_prev(&mas, 0);
/* Check results. */ MT_BUG_ON(mt, entry != entry2); MT_BUG_ON(mt, index != mas.index); MT_BUG_ON(mt, last != mas.last);
mas.status = ma_none; mas.index = ULONG_MAX; mas.last = ULONG_MAX; entry2 = mas_prev(&mas, 0); MT_BUG_ON(mt, entry != entry2);
mas_set(&mas, 0); MT_BUG_ON(mt, mas_prev(&mas, 0) != NULL);
mas_unlock(&mas); mtree_destroy(mt);}
static noinline void __init check_find_2(struct maple_tree *mt){ unsigned long i, j; void *entry;
MA_STATE(mas, mt, 0, 0); rcu_read_lock(); mas_for_each(&mas, entry, ULONG_MAX) MT_BUG_ON(mt, true); rcu_read_unlock();
for (i = 0; i < 256; i++) { mtree_insert_index(mt, i, GFP_KERNEL); j = 0; mas_set(&mas, 0); rcu_read_lock(); mas_for_each(&mas, entry, ULONG_MAX) { MT_BUG_ON(mt, entry != xa_mk_value(j)); j++; } rcu_read_unlock(); MT_BUG_ON(mt, j != i + 1); }
for (i = 0; i < 256; i++) { mtree_erase_index(mt, i); j = i + 1; mas_set(&mas, 0); rcu_read_lock(); mas_for_each(&mas, entry, ULONG_MAX) { if (xa_is_zero(entry)) continue;
MT_BUG_ON(mt, entry != xa_mk_value(j)); j++; } rcu_read_unlock(); MT_BUG_ON(mt, j != 256); }
/*MT_BUG_ON(mt, !mtree_empty(mt)); */}
#if defined(CONFIG_64BIT)static noinline void __init check_alloc_rev_range(struct maple_tree *mt){ /* * Generated by: * cat /proc/self/maps | awk '{print $1}'| * awk -F "-" '{printf "0x%s, 0x%s, ", $1, $2}' */
static const unsigned long range[] = { /* Inclusive , Exclusive. */ 0x565234af2000, 0x565234af4000, 0x565234af4000, 0x565234af9000, 0x565234af9000, 0x565234afb000, 0x565234afc000, 0x565234afd000, 0x565234afd000, 0x565234afe000, 0x565235def000, 0x565235e10000, 0x7f36d4bfd000, 0x7f36d4ee2000, 0x7f36d4ee2000, 0x7f36d4f04000, 0x7f36d4f04000, 0x7f36d504c000, 0x7f36d504c000, 0x7f36d5098000, 0x7f36d5098000, 0x7f36d5099000, 0x7f36d5099000, 0x7f36d509d000, 0x7f36d509d000, 0x7f36d509f000, 0x7f36d509f000, 0x7f36d50a5000, 0x7f36d50b9000, 0x7f36d50db000, 0x7f36d50db000, 0x7f36d50dc000, 0x7f36d50dc000, 0x7f36d50fa000, 0x7f36d50fa000, 0x7f36d5102000, 0x7f36d5102000, 0x7f36d5103000, 0x7f36d5103000, 0x7f36d5104000, 0x7f36d5104000, 0x7f36d5105000, 0x7fff5876b000, 0x7fff5878d000, 0x7fff5878e000, 0x7fff58791000, 0x7fff58791000, 0x7fff58793000, };
static const unsigned long holes[] = { /* * Note: start of hole is INCLUSIVE * end of hole is EXCLUSIVE * (opposite of the above table.) * Start of hole, end of hole, size of hole (+1) */ 0x565234afb000, 0x565234afc000, 0x1000, 0x565234afe000, 0x565235def000, 0x12F1000, 0x565235e10000, 0x7f36d4bfd000, 0x28E49EDED000, };
/* * req_range consists of 4 values. * 1. min index * 2. max index * 3. size * 4. number that should be returned. * 5. return value */ static const unsigned long req_range[] = { 0x565234af9000, /* Min */ 0x7fff58791000, /* Max */ 0x1000, /* Size */ 0x7fff5878d << 12, /* First rev hole of size 0x1000 */ 0, /* Return value success. */
0x0, /* Min */ 0x565234AF0 << 12, /* Max */ 0x3000, /* Size */ 0x565234AEE << 12, /* max - 3. */ 0, /* Return value success. */
0x0, /* Min */ -1, /* Max */ 0x1000, /* Size */ 562949953421311 << 12,/* First rev hole of size 0x1000 */ 0, /* Return value success. */
0x0, /* Min */ 0x7F36D5109 << 12, /* Max */ 0x4000, /* Size */ 0x7F36D5106 << 12, /* First rev hole of size 0x4000 */ 0, /* Return value success. */
/* Ascend test. */ 0x0, 34148798628 << 12, 19 << 12, 34148797418 << 12, 0x0,
/* Too big test. */ 0x0, 18446744073709551615UL, 562915594369134UL << 12, 0x0, -EBUSY,
/* Single space test. */ 34148798725 << 12, 34148798725 << 12, 1 << 12, 34148798725 << 12, 0, };
int i, range_count = ARRAY_SIZE(range); int req_range_count = ARRAY_SIZE(req_range); unsigned long min = 0;
MA_STATE(mas, mt, 0, 0);
mtree_store_range(mt, MTREE_ALLOC_MAX, ULONG_MAX, XA_ZERO_ENTRY, GFP_KERNEL);#define DEBUG_REV_RANGE 0 for (i = 0; i < range_count; i += 2) { /* Inclusive, Inclusive (with the -1) */
#if DEBUG_REV_RANGE pr_debug("\t%s: Insert %lu-%lu\n", __func__, range[i] >> 12, (range[i + 1] >> 12) - 1);#endif check_insert_range(mt, range[i] >> 12, (range[i + 1] >> 12) - 1, xa_mk_value(range[i] >> 12), 0); mt_validate(mt); }
mas_lock(&mas); for (i = 0; i < ARRAY_SIZE(holes); i += 3) {#if DEBUG_REV_RANGE pr_debug("Search from %lu-%lu for gap %lu should be at %lu\n", min, holes[i+1]>>12, holes[i+2]>>12, holes[i] >> 12);#endif MT_BUG_ON(mt, mas_empty_area_rev(&mas, min, holes[i+1] >> 12, holes[i+2] >> 12));#if DEBUG_REV_RANGE pr_debug("Found %lu %lu\n", mas.index, mas.last); pr_debug("gap %lu %lu\n", (holes[i] >> 12), (holes[i+1] >> 12));#endif MT_BUG_ON(mt, mas.last + 1 != (holes[i+1] >> 12)); MT_BUG_ON(mt, mas.index != (holes[i+1] >> 12) - (holes[i+2] >> 12)); min = holes[i+1] >> 12; mas_reset(&mas); }
mas_unlock(&mas); for (i = 0; i < req_range_count; i += 5) {#if DEBUG_REV_RANGE pr_debug("\tReverse request %d between %lu-%lu size %lu, should get %lu\n", i, req_range[i] >> 12, (req_range[i + 1] >> 12), req_range[i+2] >> 12, req_range[i+3] >> 12);#endif check_mtree_alloc_rrange(mt, req_range[i] >> 12, /* start */ req_range[i+1] >> 12, /* end */ req_range[i+2] >> 12, /* size */ req_range[i+3] >> 12, /* expected address */ req_range[i+4], /* expected return */ xa_mk_value(req_range[i] >> 12)); /* pointer */ mt_validate(mt); }
mt_set_non_kernel(1); mtree_erase(mt, 34148798727); /* create a deleted range. */ mtree_erase(mt, 34148798725); check_mtree_alloc_rrange(mt, 0, 34359052173, 210253414, 34148798725, 0, mt);
mtree_destroy(mt);}
static noinline void __init check_alloc_range(struct maple_tree *mt){ /* * Generated by: * cat /proc/self/maps|awk '{print $1}'| * awk -F "-" '{printf "0x%s, 0x%s, ", $1, $2}' */
static const unsigned long range[] = { /* Inclusive , Exclusive. */ 0x565234af2000, 0x565234af4000, 0x565234af4000, 0x565234af9000, 0x565234af9000, 0x565234afb000, 0x565234afc000, 0x565234afd000, 0x565234afd000, 0x565234afe000, 0x565235def000, 0x565235e10000, 0x7f36d4bfd000, 0x7f36d4ee2000, 0x7f36d4ee2000, 0x7f36d4f04000, 0x7f36d4f04000, 0x7f36d504c000, 0x7f36d504c000, 0x7f36d5098000, 0x7f36d5098000, 0x7f36d5099000, 0x7f36d5099000, 0x7f36d509d000, 0x7f36d509d000, 0x7f36d509f000, 0x7f36d509f000, 0x7f36d50a5000, 0x7f36d50b9000, 0x7f36d50db000, 0x7f36d50db000, 0x7f36d50dc000, 0x7f36d50dc000, 0x7f36d50fa000, 0x7f36d50fa000, 0x7f36d5102000, 0x7f36d5102000, 0x7f36d5103000, 0x7f36d5103000, 0x7f36d5104000, 0x7f36d5104000, 0x7f36d5105000, 0x7fff5876b000, 0x7fff5878d000, 0x7fff5878e000, 0x7fff58791000, 0x7fff58791000, 0x7fff58793000, }; static const unsigned long holes[] = { /* Start of hole, end of hole, size of hole (+1) */ 0x565234afb000, 0x565234afc000, 0x1000, 0x565234afe000, 0x565235def000, 0x12F1000, 0x565235e10000, 0x7f36d4bfd000, 0x28E49EDED000, };
/* * req_range consists of 4 values. * 1. min index * 2. max index * 3. size * 4. number that should be returned. * 5. return value */ static const unsigned long req_range[] = { 0x565234af9000, /* Min */ 0x7fff58791000, /* Max */ 0x1000, /* Size */ 0x565234afb000, /* First hole in our data of size 1000. */ 0, /* Return value success. */
0x0, /* Min */ 0x7fff58791000, /* Max */ 0x1F00, /* Size */ 0x0, /* First hole in our data of size 2000. */ 0, /* Return value success. */
/* Test ascend. */ 34148797436 << 12, /* Min */ 0x7fff587AF000, /* Max */ 0x3000, /* Size */ 34148798629 << 12, /* Expected location */ 0, /* Return value success. */
/* Test failing. */ 34148798623 << 12, /* Min */ 34148798683 << 12, /* Max */ 0x15000, /* Size */ 0, /* Expected location */ -EBUSY, /* Return value failed. */
/* Test filling entire gap. */ 34148798623 << 12, /* Min */ 0x7fff587AF000, /* Max */ 0x10000, /* Size */ 34148798632 << 12, /* Expected location */ 0, /* Return value success. */
/* Test walking off the end of root. */ 0, /* Min */ -1, /* Max */ -1, /* Size */ 0, /* Expected location */ -EBUSY, /* Return value failure. */
/* Test looking for too large a hole across entire range. */ 0, /* Min */ -1, /* Max */ 4503599618982063UL << 12, /* Size */ 34359052178 << 12, /* Expected location */ -EBUSY, /* Return failure. */
/* Test a single entry */ 34148798648 << 12, /* Min */ 34148798648 << 12, /* Max */ 4096, /* Size of 1 */ 34148798648 << 12, /* Location is the same as min/max */ 0, /* Success */ }; int i, range_count = ARRAY_SIZE(range); int req_range_count = ARRAY_SIZE(req_range); unsigned long min = 0x565234af2000; MA_STATE(mas, mt, 0, 0);
mtree_store_range(mt, MTREE_ALLOC_MAX, ULONG_MAX, XA_ZERO_ENTRY, GFP_KERNEL); for (i = 0; i < range_count; i += 2) {#define DEBUG_ALLOC_RANGE 0#if DEBUG_ALLOC_RANGE pr_debug("\tInsert %lu-%lu\n", range[i] >> 12, (range[i + 1] >> 12) - 1); mt_dump(mt, mt_dump_hex);#endif check_insert_range(mt, range[i] >> 12, (range[i + 1] >> 12) - 1, xa_mk_value(range[i] >> 12), 0); mt_validate(mt); }
mas_lock(&mas); for (i = 0; i < ARRAY_SIZE(holes); i += 3) {
#if DEBUG_ALLOC_RANGE pr_debug("\tGet empty %lu-%lu size %lu (%lx-%lx)\n", min >> 12, holes[i+1] >> 12, holes[i+2] >> 12, min, holes[i+1]);#endif MT_BUG_ON(mt, mas_empty_area(&mas, min >> 12, holes[i+1] >> 12, holes[i+2] >> 12)); MT_BUG_ON(mt, mas.index != holes[i] >> 12); min = holes[i+1]; mas_reset(&mas); } mas_unlock(&mas); for (i = 0; i < req_range_count; i += 5) {#if DEBUG_ALLOC_RANGE pr_debug("\tTest %d: %lu-%lu size %lu expected %lu (%lu-%lu)\n", i/5, req_range[i] >> 12, req_range[i + 1] >> 12, req_range[i + 2] >> 12, req_range[i + 3] >> 12, req_range[i], req_range[i+1]);#endif check_mtree_alloc_range(mt, req_range[i] >> 12, /* start */ req_range[i+1] >> 12, /* end */ req_range[i+2] >> 12, /* size */ req_range[i+3] >> 12, /* expected address */ req_range[i+4], /* expected return */ xa_mk_value(req_range[i] >> 12)); /* pointer */ mt_validate(mt);#if DEBUG_ALLOC_RANGE mt_dump(mt, mt_dump_hex);#endif }
mtree_destroy(mt);}#endif
static noinline void __init check_ranges(struct maple_tree *mt){ int i, val, val2; static const unsigned long r[] = { 10, 15, 20, 25, 17, 22, /* Overlaps previous range. */ 9, 1000, /* Huge. */ 100, 200, 45, 168, 118, 128, };
MT_BUG_ON(mt, !mtree_empty(mt)); check_insert_range(mt, r[0], r[1], xa_mk_value(r[0]), 0); check_insert_range(mt, r[2], r[3], xa_mk_value(r[2]), 0); check_insert_range(mt, r[4], r[5], xa_mk_value(r[4]), -EEXIST); MT_BUG_ON(mt, !mt_height(mt)); /* Store */ check_store_range(mt, r[4], r[5], xa_mk_value(r[4]), 0); check_store_range(mt, r[6], r[7], xa_mk_value(r[6]), 0); check_store_range(mt, r[8], r[9], xa_mk_value(r[8]), 0); MT_BUG_ON(mt, !mt_height(mt)); mtree_destroy(mt); MT_BUG_ON(mt, mt_height(mt));
check_seq(mt, 50, false); mt_set_non_kernel(4); check_store_range(mt, 5, 47, xa_mk_value(47), 0); MT_BUG_ON(mt, !mt_height(mt)); mtree_destroy(mt);
/* Create tree of 1-100 */ check_seq(mt, 100, false); /* Store 45-168 */ mt_set_non_kernel(10); check_store_range(mt, r[10], r[11], xa_mk_value(r[10]), 0); MT_BUG_ON(mt, !mt_height(mt)); mt_validate(mt); mtree_destroy(mt);
/* Create tree of 1-200 */ check_seq(mt, 200, false); /* Store 45-168 */ check_store_range(mt, r[10], r[11], xa_mk_value(r[10]), 0); MT_BUG_ON(mt, !mt_height(mt)); mt_validate(mt); mtree_destroy(mt);
check_seq(mt, 30, false); check_store_range(mt, 6, 18, xa_mk_value(6), 0); MT_BUG_ON(mt, !mt_height(mt)); mt_validate(mt); mtree_destroy(mt);
/* Overwrite across multiple levels. */ /* Create tree of 1-400 */ check_seq(mt, 400, false); mt_set_non_kernel(50); /* Store 118-128 */ check_store_range(mt, r[12], r[13], xa_mk_value(r[12]), 0); mt_set_non_kernel(50); mtree_test_erase(mt, 140); mtree_test_erase(mt, 141); mtree_test_erase(mt, 142); mtree_test_erase(mt, 143); mtree_test_erase(mt, 130); mtree_test_erase(mt, 131); mtree_test_erase(mt, 132); mtree_test_erase(mt, 133); mtree_test_erase(mt, 134); mtree_test_erase(mt, 135); check_load(mt, r[12], xa_mk_value(r[12])); check_load(mt, r[13], xa_mk_value(r[12])); check_load(mt, r[13] - 1, xa_mk_value(r[12])); check_load(mt, r[13] + 1, xa_mk_value(r[13] + 1)); check_load(mt, 135, NULL); check_load(mt, 140, NULL); mt_validate(mt); mt_set_non_kernel(0); MT_BUG_ON(mt, !mt_height(mt)); mtree_destroy(mt);
/* Overwrite multiple levels at the end of the tree (slot 7) */ mt_set_non_kernel(50); check_seq(mt, 400, false); check_store_range(mt, 353, 361, xa_mk_value(353), 0); check_store_range(mt, 347, 352, xa_mk_value(347), 0);
check_load(mt, 346, xa_mk_value(346)); for (i = 347; i <= 352; i++) check_load(mt, i, xa_mk_value(347)); for (i = 353; i <= 361; i++) check_load(mt, i, xa_mk_value(353)); check_load(mt, 362, xa_mk_value(362)); mt_set_non_kernel(0); MT_BUG_ON(mt, !mt_height(mt)); mtree_destroy(mt);
mt_set_non_kernel(50); check_seq(mt, 400, false); check_store_range(mt, 352, 364, NULL, 0); check_store_range(mt, 351, 363, xa_mk_value(352), 0); check_load(mt, 350, xa_mk_value(350)); check_load(mt, 351, xa_mk_value(352)); for (i = 352; i <= 363; i++) check_load(mt, i, xa_mk_value(352)); check_load(mt, 364, NULL); check_load(mt, 365, xa_mk_value(365)); mt_set_non_kernel(0); MT_BUG_ON(mt, !mt_height(mt)); mtree_destroy(mt);
mt_set_non_kernel(5); check_seq(mt, 400, false); check_store_range(mt, 352, 364, NULL, 0); check_store_range(mt, 351, 364, xa_mk_value(352), 0); check_load(mt, 350, xa_mk_value(350)); check_load(mt, 351, xa_mk_value(352)); for (i = 352; i <= 364; i++) check_load(mt, i, xa_mk_value(352)); check_load(mt, 365, xa_mk_value(365)); mt_set_non_kernel(0); MT_BUG_ON(mt, !mt_height(mt)); mtree_destroy(mt);
mt_set_non_kernel(50); check_seq(mt, 400, false); check_store_range(mt, 362, 367, xa_mk_value(362), 0); check_store_range(mt, 353, 361, xa_mk_value(353), 0); mt_set_non_kernel(0); mt_validate(mt); MT_BUG_ON(mt, !mt_height(mt)); mtree_destroy(mt); /* * Interesting cases: * 1. Overwrite the end of a node and end in the first entry of the next * node. * 2. Split a single range * 3. Overwrite the start of a range * 4. Overwrite the end of a range * 5. Overwrite the entire range * 6. Overwrite a range that causes multiple parent nodes to be * combined * 7. Overwrite a range that causes multiple parent nodes and part of * root to be combined * 8. Overwrite the whole tree * 9. Try to overwrite the zero entry of an alloc tree. * 10. Write a range larger than a nodes current pivot */
mt_set_non_kernel(50); for (i = 0; i <= 500; i++) { val = i*5; val2 = (i+1)*5; check_store_range(mt, val, val2, xa_mk_value(val), 0); } check_store_range(mt, 2400, 2400, xa_mk_value(2400), 0); check_store_range(mt, 2411, 2411, xa_mk_value(2411), 0); check_store_range(mt, 2412, 2412, xa_mk_value(2412), 0); check_store_range(mt, 2396, 2400, xa_mk_value(4052020), 0); check_store_range(mt, 2402, 2402, xa_mk_value(2402), 0); mtree_destroy(mt); mt_set_non_kernel(0);
mt_set_non_kernel(50); for (i = 0; i <= 500; i++) { val = i*5; val2 = (i+1)*5; check_store_range(mt, val, val2, xa_mk_value(val), 0); } check_store_range(mt, 2422, 2422, xa_mk_value(2422), 0); check_store_range(mt, 2424, 2424, xa_mk_value(2424), 0); check_store_range(mt, 2425, 2425, xa_mk_value(2), 0); check_store_range(mt, 2460, 2470, NULL, 0); check_store_range(mt, 2435, 2460, xa_mk_value(2435), 0); check_store_range(mt, 2461, 2470, xa_mk_value(2461), 0); mt_set_non_kernel(0); MT_BUG_ON(mt, !mt_height(mt)); mtree_destroy(mt);
/* Check in-place modifications */ mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); /* Append to the start of last range */ mt_set_non_kernel(50); for (i = 0; i <= 500; i++) { val = i * 5 + 1; val2 = val + 4; check_store_range(mt, val, val2, xa_mk_value(val), 0); }
/* Append to the last range without touching any boundaries */ for (i = 0; i < 10; i++) { val = val2 + 5; val2 = val + 4; check_store_range(mt, val, val2, xa_mk_value(val), 0); }
/* Append to the end of last range */ val = val2; for (i = 0; i < 10; i++) { val += 5; MT_BUG_ON(mt, mtree_test_store_range(mt, val, ULONG_MAX, xa_mk_value(val)) != 0); }
/* Overwriting the range and over a part of the next range */ for (i = 10; i < 30; i += 2) { val = i * 5 + 1; val2 = val + 5; check_store_range(mt, val, val2, xa_mk_value(val), 0); }
/* Overwriting a part of the range and over the next range */ for (i = 50; i < 70; i += 2) { val2 = i * 5; val = val2 - 5; check_store_range(mt, val, val2, xa_mk_value(val), 0); }
/* * Expand the range, only partially overwriting the previous and * next ranges */ for (i = 100; i < 130; i += 3) { val = i * 5 - 5; val2 = i * 5 + 1; check_store_range(mt, val, val2, xa_mk_value(val), 0); }
/* * Expand the range, only partially overwriting the previous and * next ranges, in RCU mode */ mt_set_in_rcu(mt); for (i = 150; i < 180; i += 3) { val = i * 5 - 5; val2 = i * 5 + 1; check_store_range(mt, val, val2, xa_mk_value(val), 0); }
MT_BUG_ON(mt, !mt_height(mt)); mt_validate(mt); mt_set_non_kernel(0); mtree_destroy(mt);
/* Test rebalance gaps */ mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); mt_set_non_kernel(50); for (i = 0; i <= 50; i++) { val = i*10; val2 = (i+1)*10; check_store_range(mt, val, val2, xa_mk_value(val), 0); } check_store_range(mt, 161, 161, xa_mk_value(161), 0); check_store_range(mt, 162, 162, xa_mk_value(162), 0); check_store_range(mt, 163, 163, xa_mk_value(163), 0); check_store_range(mt, 240, 249, NULL, 0); mtree_erase(mt, 200); mtree_erase(mt, 210); mtree_erase(mt, 220); mtree_erase(mt, 230); mt_set_non_kernel(0); MT_BUG_ON(mt, !mt_height(mt)); mtree_destroy(mt);
mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); for (i = 0; i <= 500; i++) { val = i*10; val2 = (i+1)*10; check_store_range(mt, val, val2, xa_mk_value(val), 0); } check_store_range(mt, 4600, 4959, xa_mk_value(1), 0); mt_validate(mt); MT_BUG_ON(mt, !mt_height(mt)); mtree_destroy(mt);
mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); for (i = 0; i <= 500; i++) { val = i*10; val2 = (i+1)*10; check_store_range(mt, val, val2, xa_mk_value(val), 0); } check_store_range(mt, 4811, 4811, xa_mk_value(4811), 0); check_store_range(mt, 4812, 4812, xa_mk_value(4812), 0); check_store_range(mt, 4861, 4861, xa_mk_value(4861), 0); check_store_range(mt, 4862, 4862, xa_mk_value(4862), 0); check_store_range(mt, 4842, 4849, NULL, 0); mt_validate(mt); MT_BUG_ON(mt, !mt_height(mt)); mtree_destroy(mt);
mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); for (i = 0; i <= 1300; i++) { val = i*10; val2 = (i+1)*10; check_store_range(mt, val, val2, xa_mk_value(val), 0); MT_BUG_ON(mt, mt_height(mt) >= 4); } /* Cause a 3 child split all the way up the tree. */ for (i = 5; i < 215; i += 10) { check_store_range(mt, 11450 + i, 11450 + i + 1, NULL, 0); mt_validate(mt); } for (i = 5; i < 65; i += 10) { check_store_range(mt, 11770 + i, 11770 + i + 1, NULL, 0); mt_validate(mt); }
MT_BUG_ON(mt, mt_height(mt) >= 4); for (i = 5; i < 45; i += 10) { check_store_range(mt, 11700 + i, 11700 + i + 1, NULL, 0); mt_validate(mt); } if (!MAPLE_32BIT) MT_BUG_ON(mt, mt_height(mt) < 4); mtree_destroy(mt);
mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); for (i = 0; i <= 1200; i++) { val = i*10; val2 = (i+1)*10; check_store_range(mt, val, val2, xa_mk_value(val), 0); MT_BUG_ON(mt, mt_height(mt) >= 4); mt_validate(mt); } /* Fill parents and leaves before split. */ val = 7660; for (i = 5; i < 490; i += 5) { val += 5; check_store_range(mt, val, val + 1, NULL, 0); mt_validate(mt); MT_BUG_ON(mt, mt_height(mt) >= 4); }
val = 9460; /* Fill parents and leaves before split. */ for (i = 1; i < 10; i++) { val++; check_store_range(mt, val, val + 1, xa_mk_value(val), 0); mt_validate(mt); }
val = 8000; for (i = 1; i < 14; i++) { val++; check_store_range(mt, val, val + 1, xa_mk_value(val), 0); mt_validate(mt); }
check_store_range(mt, 8051, 8051, xa_mk_value(8081), 0); check_store_range(mt, 8052, 8052, xa_mk_value(8082), 0); check_store_range(mt, 8083, 8083, xa_mk_value(8083), 0); check_store_range(mt, 8084, 8084, xa_mk_value(8084), 0); check_store_range(mt, 8085, 8085, xa_mk_value(8085), 0); /* triple split across multiple levels. */ check_store_range(mt, 8099, 8100, xa_mk_value(1), 0);
mt_validate(mt); if (!MAPLE_32BIT) MT_BUG_ON(mt, mt_height(mt) != 4);}
static noinline void __init check_next_entry(struct maple_tree *mt){ void *entry = NULL; unsigned long limit = 30, i = 0; MA_STATE(mas, mt, i, i);
MT_BUG_ON(mt, !mtree_empty(mt));
check_seq(mt, limit, false); rcu_read_lock();
/* Check the first one and get ma_state in the correct state. */ MT_BUG_ON(mt, mas_walk(&mas) != xa_mk_value(i++)); for ( ; i <= limit + 1; i++) { entry = mas_next(&mas, limit); if (i > limit) MT_BUG_ON(mt, entry != NULL); else MT_BUG_ON(mt, xa_mk_value(i) != entry); } rcu_read_unlock(); mtree_destroy(mt);}
static noinline void __init check_prev_entry(struct maple_tree *mt){ unsigned long index = 16; void *value; int i;
MA_STATE(mas, mt, index, index);
MT_BUG_ON(mt, !mtree_empty(mt)); check_seq(mt, 30, false);
rcu_read_lock(); value = mas_find(&mas, ULONG_MAX); MT_BUG_ON(mt, value != xa_mk_value(index)); value = mas_prev(&mas, 0); MT_BUG_ON(mt, value != xa_mk_value(index - 1)); rcu_read_unlock(); mtree_destroy(mt);
/* Check limits on prev */ mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); mas_lock(&mas); for (i = 0; i <= index; i++) { mas_set_range(&mas, i*10, i*10+5); mas_store_gfp(&mas, xa_mk_value(i), GFP_KERNEL); }
mas_set(&mas, 20); value = mas_walk(&mas); MT_BUG_ON(mt, value != xa_mk_value(2));
value = mas_prev(&mas, 19); MT_BUG_ON(mt, value != NULL);
mas_set(&mas, 80); value = mas_walk(&mas); MT_BUG_ON(mt, value != xa_mk_value(8));
value = mas_prev(&mas, 76); MT_BUG_ON(mt, value != NULL);
mas_unlock(&mas);}
static noinline void __init check_store_null(struct maple_tree *mt){ MA_STATE(mas, mt, 0, ULONG_MAX);
/* * Store NULL at range [0, ULONG_MAX] to an empty tree should result * in an empty tree */ mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); mas_lock(&mas); mas_store_gfp(&mas, NULL, GFP_KERNEL); MT_BUG_ON(mt, !mtree_empty(mt)); mas_unlock(&mas); mtree_destroy(mt);
/* * Store NULL at any range to an empty tree should result in an empty * tree */ mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); mas_lock(&mas); mas_set_range(&mas, 3, 10); mas_store_gfp(&mas, NULL, GFP_KERNEL); MT_BUG_ON(mt, !mtree_empty(mt)); mas_unlock(&mas); mtree_destroy(mt);
/* * Store NULL at range [0, ULONG_MAX] to a single entry tree should * result in an empty tree */ mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); mas_lock(&mas); mas_set(&mas, 0); mas_store_gfp(&mas, &mas, GFP_KERNEL); mas_set_range(&mas, 0, ULONG_MAX); mas_store_gfp(&mas, NULL, GFP_KERNEL); MT_BUG_ON(mt, !mtree_empty(mt)); mas_unlock(&mas); mtree_destroy(mt);
/* * Store NULL at range [0, n] to a single entry tree should * result in an empty tree */ mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); mas_lock(&mas); mas_set(&mas, 0); mas_store_gfp(&mas, &mas, GFP_KERNEL); mas_set_range(&mas, 0, 5); mas_store_gfp(&mas, NULL, GFP_KERNEL); MT_BUG_ON(mt, !mtree_empty(mt)); mas_unlock(&mas); mtree_destroy(mt);
/* * Store NULL at range [m, n] where m > 0 to a single entry tree * should still be a single entry tree */ mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); mas_lock(&mas); mas_set(&mas, 0); mas_store_gfp(&mas, &mas, GFP_KERNEL); mas_set_range(&mas, 2, 5); mas_store_gfp(&mas, NULL, GFP_KERNEL); MT_BUG_ON(mt, mtree_empty(mt));// MT_BUG_ON(mt, xa_is_node(mas_root(&mas))); mas_unlock(&mas); mtree_destroy(mt);
/* * Store NULL at range [0, ULONG_MAX] to a tree with node should * result in an empty tree */ mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); mas_lock(&mas); mas_set_range(&mas, 1, 3); mas_store_gfp(&mas, &mas, GFP_KERNEL);// MT_BUG_ON(mt, !xa_is_node(mas_root(&mas))); mas_set_range(&mas, 0, ULONG_MAX); mas_store_gfp(&mas, NULL, GFP_KERNEL); MT_BUG_ON(mt, !mtree_empty(mt)); mas_unlock(&mas); mtree_destroy(mt);}
static noinline void __init check_root_expand(struct maple_tree *mt){ MA_STATE(mas, mt, 0, 0); void *ptr;
mas_lock(&mas); mas_set(&mas, 3); ptr = mas_walk(&mas); MT_BUG_ON(mt, mas.index != 0); MT_BUG_ON(mt, ptr != NULL); MT_BUG_ON(mt, mas.index != 0); MT_BUG_ON(mt, mas.last != ULONG_MAX);
ptr = &check_prev_entry; mas_set(&mas, 1); mas_store_gfp(&mas, ptr, GFP_KERNEL);
mas_set(&mas, 0); ptr = mas_walk(&mas); MT_BUG_ON(mt, ptr != NULL);
mas_set(&mas, 1); ptr = mas_walk(&mas); MT_BUG_ON(mt, ptr != &check_prev_entry);
mas_set(&mas, 2); ptr = mas_walk(&mas); MT_BUG_ON(mt, ptr != NULL); mas_unlock(&mas); mtree_destroy(mt);
mt_init_flags(mt, 0); mas_lock(&mas);
mas_set(&mas, 0); ptr = &check_prev_entry; mas_store_gfp(&mas, ptr, GFP_KERNEL);
mas_set(&mas, 5); ptr = mas_walk(&mas); MT_BUG_ON(mt, ptr != NULL); MT_BUG_ON(mt, mas.index != 1); MT_BUG_ON(mt, mas.last != ULONG_MAX);
mas_set_range(&mas, 0, 100); ptr = mas_walk(&mas); MT_BUG_ON(mt, ptr != &check_prev_entry); MT_BUG_ON(mt, mas.last != 0); mas_unlock(&mas); mtree_destroy(mt);
mt_init_flags(mt, 0); mas_lock(&mas);
mas_set(&mas, 0); ptr = (void *)((unsigned long) check_prev_entry | 1UL); mas_store_gfp(&mas, ptr, GFP_KERNEL); ptr = mas_next(&mas, ULONG_MAX); MT_BUG_ON(mt, ptr != NULL); MT_BUG_ON(mt, (mas.index != 1) && (mas.last != ULONG_MAX));
mas_set(&mas, 1); ptr = mas_prev(&mas, 0); MT_BUG_ON(mt, (mas.index != 0) && (mas.last != 0)); MT_BUG_ON(mt, ptr != (void *)((unsigned long) check_prev_entry | 1UL));
mas_unlock(&mas);
mtree_destroy(mt);
mt_init_flags(mt, 0); mas_lock(&mas); mas_set(&mas, 0); ptr = (void *)((unsigned long) check_prev_entry | 2UL); mas_store_gfp(&mas, ptr, GFP_KERNEL); ptr = mas_next(&mas, ULONG_MAX); MT_BUG_ON(mt, ptr != NULL); MT_BUG_ON(mt, (mas.index != ULONG_MAX) && (mas.last != ULONG_MAX));
mas_set(&mas, 1); ptr = mas_prev(&mas, 0); MT_BUG_ON(mt, (mas.index != 0) && (mas.last != 0)); MT_BUG_ON(mt, ptr != (void *)((unsigned long) check_prev_entry | 2UL));
mas_unlock(&mas);}
static noinline void __init check_deficient_node(struct maple_tree *mt){ MA_STATE(mas, mt, 0, 0); int count;
mas_lock(&mas); for (count = 0; count < 10; count++) { mas_set(&mas, count); mas_store_gfp(&mas, xa_mk_value(count), GFP_KERNEL); }
for (count = 20; count < 39; count++) { mas_set(&mas, count); mas_store_gfp(&mas, xa_mk_value(count), GFP_KERNEL); }
for (count = 10; count < 12; count++) { mas_set(&mas, count); mas_store_gfp(&mas, xa_mk_value(count), GFP_KERNEL); } mas_unlock(&mas); mt_validate(mt);}
static noinline void __init check_gap_combining(struct maple_tree *mt){ struct maple_enode *mn1, *mn2; void *entry; unsigned long singletons = 100; static const unsigned long *seq100; static const unsigned long seq100_64[] = { /* 0-5 */ 74, 75, 76, 50, 100, 2,
/* 6-12 */ 44, 45, 46, 43, 20, 50, 3,
/* 13-20*/ 80, 81, 82, 76, 2, 79, 85, 4, };
static const unsigned long seq100_32[] = { /* 0-5 */ 61, 62, 63, 50, 100, 2,
/* 6-12 */ 31, 32, 33, 30, 20, 50, 3,
/* 13-20*/ 80, 81, 82, 76, 2, 79, 85, 4, };
static const unsigned long seq2000[] = { 1152, 1151, 1100, 1200, 2, }; static const unsigned long seq400[] = { 286, 318, 256, 260, 266, 270, 275, 280, 290, 398, 286, 310, };
unsigned long index;
MA_STATE(mas, mt, 0, 0);
if (MAPLE_32BIT) seq100 = seq100_32; else seq100 = seq100_64;
index = seq100[0]; mas_set(&mas, index); MT_BUG_ON(mt, !mtree_empty(mt)); check_seq(mt, singletons, false); /* create 100 singletons. */
mt_set_non_kernel(1); mtree_test_erase(mt, seq100[2]); check_load(mt, seq100[2], NULL); mtree_test_erase(mt, seq100[1]); check_load(mt, seq100[1], NULL);
rcu_read_lock(); entry = mas_find(&mas, ULONG_MAX); MT_BUG_ON(mt, entry != xa_mk_value(index)); mn1 = mas.node; mas_next(&mas, ULONG_MAX); entry = mas_next(&mas, ULONG_MAX); MT_BUG_ON(mt, entry != xa_mk_value(index + 4)); mn2 = mas.node; MT_BUG_ON(mt, mn1 == mn2); /* test the test. */
/* * At this point, there is a gap of 2 at index + 1 between seq100[3] and * seq100[4]. Search for the gap. */ mt_set_non_kernel(1); mas_reset(&mas); MT_BUG_ON(mt, mas_empty_area_rev(&mas, seq100[3], seq100[4], seq100[5])); MT_BUG_ON(mt, mas.index != index + 1); rcu_read_unlock();
mtree_test_erase(mt, seq100[6]); check_load(mt, seq100[6], NULL); mtree_test_erase(mt, seq100[7]); check_load(mt, seq100[7], NULL); mtree_test_erase(mt, seq100[8]); index = seq100[9];
rcu_read_lock(); mas.index = index; mas.last = index; mas_reset(&mas); entry = mas_find(&mas, ULONG_MAX); MT_BUG_ON(mt, entry != xa_mk_value(index)); mn1 = mas.node; entry = mas_next(&mas, ULONG_MAX); MT_BUG_ON(mt, entry != xa_mk_value(index + 4)); mas_next(&mas, ULONG_MAX); /* go to the next entry. */ mn2 = mas.node; MT_BUG_ON(mt, mn1 == mn2); /* test the next entry is in the next node. */
/* * At this point, there is a gap of 3 at seq100[6]. Find it by * searching 20 - 50 for size 3. */ mas_reset(&mas); MT_BUG_ON(mt, mas_empty_area_rev(&mas, seq100[10], seq100[11], seq100[12])); MT_BUG_ON(mt, mas.index != seq100[6]); rcu_read_unlock();
mt_set_non_kernel(1); mtree_store(mt, seq100[13], NULL, GFP_KERNEL); check_load(mt, seq100[13], NULL); check_load(mt, seq100[14], xa_mk_value(seq100[14])); mtree_store(mt, seq100[14], NULL, GFP_KERNEL); check_load(mt, seq100[13], NULL); check_load(mt, seq100[14], NULL);
mas_reset(&mas); rcu_read_lock(); MT_BUG_ON(mt, mas_empty_area_rev(&mas, seq100[16], seq100[15], seq100[17])); MT_BUG_ON(mt, mas.index != seq100[13]); mt_validate(mt); rcu_read_unlock();
/* * *DEPRECATED: no retries anymore* Test retry entry in the start of a * gap. */ mt_set_non_kernel(2); mtree_test_store_range(mt, seq100[18], seq100[14], NULL); mtree_test_erase(mt, seq100[15]); mas_reset(&mas); rcu_read_lock(); MT_BUG_ON(mt, mas_empty_area_rev(&mas, seq100[16], seq100[19], seq100[20])); rcu_read_unlock(); MT_BUG_ON(mt, mas.index != seq100[18]); mt_validate(mt); mtree_destroy(mt);
/* seq 2000 tests are for multi-level tree gaps */ mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); check_seq(mt, 2000, false); mt_set_non_kernel(1); mtree_test_erase(mt, seq2000[0]); mtree_test_erase(mt, seq2000[1]);
mt_set_non_kernel(2); mas_reset(&mas); rcu_read_lock(); MT_BUG_ON(mt, mas_empty_area_rev(&mas, seq2000[2], seq2000[3], seq2000[4])); MT_BUG_ON(mt, mas.index != seq2000[1]); rcu_read_unlock(); mt_validate(mt); mtree_destroy(mt);
/* seq 400 tests rebalancing over two levels. */ mt_set_non_kernel(99); mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); check_seq(mt, 400, false); mtree_test_store_range(mt, seq400[0], seq400[1], NULL); mt_set_non_kernel(0); mtree_destroy(mt);
mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); check_seq(mt, 400, false); mt_set_non_kernel(50); mtree_test_store_range(mt, seq400[2], seq400[9], xa_mk_value(seq400[2])); mtree_test_store_range(mt, seq400[3], seq400[9], xa_mk_value(seq400[3])); mtree_test_store_range(mt, seq400[4], seq400[9], xa_mk_value(seq400[4])); mtree_test_store_range(mt, seq400[5], seq400[9], xa_mk_value(seq400[5])); mtree_test_store_range(mt, seq400[0], seq400[9], xa_mk_value(seq400[0])); mtree_test_store_range(mt, seq400[6], seq400[9], xa_mk_value(seq400[6])); mtree_test_store_range(mt, seq400[7], seq400[9], xa_mk_value(seq400[7])); mtree_test_store_range(mt, seq400[8], seq400[9], xa_mk_value(seq400[8])); mtree_test_store_range(mt, seq400[10], seq400[11], xa_mk_value(seq400[10])); mt_validate(mt); mt_set_non_kernel(0); mtree_destroy(mt);}static noinline void __init check_node_overwrite(struct maple_tree *mt){ int i, max = 4000;
for (i = 0; i < max; i++) mtree_test_store_range(mt, i*100, i*100 + 50, xa_mk_value(i*100));
mtree_test_store_range(mt, 319951, 367950, NULL); /*mt_dump(mt, mt_dump_dec); */ mt_validate(mt);}
#if defined(BENCH_SLOT_STORE)static noinline void __init bench_slot_store(struct maple_tree *mt){ int i, brk = 105, max = 1040, brk_start = 100, count = 20000000;
for (i = 0; i < max; i += 10) mtree_store_range(mt, i, i + 5, xa_mk_value(i), GFP_KERNEL);
for (i = 0; i < count; i++) { mtree_store_range(mt, brk, brk, NULL, GFP_KERNEL); mtree_store_range(mt, brk_start, brk, xa_mk_value(brk), GFP_KERNEL); }}#endif
#if defined(BENCH_NODE_STORE)static noinline void __init bench_node_store(struct maple_tree *mt){ int i, overwrite = 76, max = 240, count = 20000000;
for (i = 0; i < max; i += 10) mtree_store_range(mt, i, i + 5, xa_mk_value(i), GFP_KERNEL);
for (i = 0; i < count; i++) { mtree_store_range(mt, overwrite, overwrite + 15, xa_mk_value(overwrite), GFP_KERNEL);
overwrite += 5; if (overwrite >= 135) overwrite = 76; }}#endif
#if defined(BENCH_AWALK)static noinline void __init bench_awalk(struct maple_tree *mt){ int i, max = 2500, count = 50000000; MA_STATE(mas, mt, 1470, 1470);
for (i = 0; i < max; i += 10) mtree_store_range(mt, i, i + 5, xa_mk_value(i), GFP_KERNEL);
mtree_store_range(mt, 1470, 1475, NULL, GFP_KERNEL);
for (i = 0; i < count; i++) { mas_empty_area_rev(&mas, 0, 2000, 10); mas_reset(&mas); }}#endif#if defined(BENCH_WALK)static noinline void __init bench_walk(struct maple_tree *mt){ int i, max = 2500, count = 550000000; MA_STATE(mas, mt, 1470, 1470);
for (i = 0; i < max; i += 10) mtree_store_range(mt, i, i + 5, xa_mk_value(i), GFP_KERNEL);
for (i = 0; i < count; i++) { mas_walk(&mas); mas_reset(&mas); }
}#endif
#if defined(BENCH_LOAD)static noinline void __init bench_load(struct maple_tree *mt){ int i, max = 2500, count = 550000000;
for (i = 0; i < max; i += 10) mtree_store_range(mt, i, i + 5, xa_mk_value(i), GFP_KERNEL);
for (i = 0; i < count; i++) mtree_load(mt, 1470);}#endif
#if defined(BENCH_MT_FOR_EACH)static noinline void __init bench_mt_for_each(struct maple_tree *mt){ int i, count = 1000000; unsigned long max = 2500, index = 0; void *entry;
for (i = 0; i < max; i += 5) mtree_store_range(mt, i, i + 4, xa_mk_value(i), GFP_KERNEL);
for (i = 0; i < count; i++) { unsigned long j = 0;
mt_for_each(mt, entry, index, max) { MT_BUG_ON(mt, entry != xa_mk_value(j)); j += 5; }
index = 0; }
}#endif
#if defined(BENCH_MAS_FOR_EACH)static noinline void __init bench_mas_for_each(struct maple_tree *mt){ int i, count = 1000000; unsigned long max = 2500; void *entry; MA_STATE(mas, mt, 0, 0);
for (i = 0; i < max; i += 5) { int gap = 4;
if (i % 30 == 0) gap = 3; mtree_store_range(mt, i, i + gap, xa_mk_value(i), GFP_KERNEL); }
rcu_read_lock(); for (i = 0; i < count; i++) { unsigned long j = 0;
mas_for_each(&mas, entry, max) { MT_BUG_ON(mt, entry != xa_mk_value(j)); j += 5; } mas_set(&mas, 0); } rcu_read_unlock();
}#endif#if defined(BENCH_MAS_PREV)static noinline void __init bench_mas_prev(struct maple_tree *mt){ int i, count = 1000000; unsigned long max = 2500; void *entry; MA_STATE(mas, mt, 0, 0);
for (i = 0; i < max; i += 5) { int gap = 4;
if (i % 30 == 0) gap = 3; mtree_store_range(mt, i, i + gap, xa_mk_value(i), GFP_KERNEL); }
rcu_read_lock(); for (i = 0; i < count; i++) { unsigned long j = 2495;
mas_set(&mas, ULONG_MAX); while ((entry = mas_prev(&mas, 0)) != NULL) { MT_BUG_ON(mt, entry != xa_mk_value(j)); j -= 5; } } rcu_read_unlock();
}#endif/* check_forking - simulate the kernel forking sequence with the tree. */static noinline void __init check_forking(void){ struct maple_tree mt, newmt; int i, nr_entries = 134, ret; void *val; MA_STATE(mas, &mt, 0, 0); MA_STATE(newmas, &newmt, 0, 0); struct rw_semaphore mt_lock, newmt_lock;
init_rwsem(&mt_lock); init_rwsem(&newmt_lock);
mt_init_flags(&mt, MT_FLAGS_ALLOC_RANGE | MT_FLAGS_LOCK_EXTERN); mt_set_external_lock(&mt, &mt_lock);
mt_init_flags(&newmt, MT_FLAGS_ALLOC_RANGE | MT_FLAGS_LOCK_EXTERN); mt_set_external_lock(&newmt, &newmt_lock);
down_write(&mt_lock); for (i = 0; i <= nr_entries; i++) { mas_set_range(&mas, i*10, i*10 + 5); mas_store_gfp(&mas, xa_mk_value(i), GFP_KERNEL); }
down_write_nested(&newmt_lock, SINGLE_DEPTH_NESTING); ret = __mt_dup(&mt, &newmt, GFP_KERNEL); if (ret) { pr_err("OOM!"); BUG_ON(1); }
mas_set(&newmas, 0); mas_for_each(&newmas, val, ULONG_MAX) mas_store(&newmas, val);
mas_destroy(&newmas); mas_destroy(&mas); mt_validate(&newmt); __mt_destroy(&newmt); __mt_destroy(&mt); up_write(&newmt_lock); up_write(&mt_lock);}
static noinline void __init check_iteration(struct maple_tree *mt){ int i, nr_entries = 125; void *val; MA_STATE(mas, mt, 0, 0);
for (i = 0; i <= nr_entries; i++) mtree_store_range(mt, i * 10, i * 10 + 9, xa_mk_value(i), GFP_KERNEL);
mt_set_non_kernel(99999);
i = 0; mas_lock(&mas); mas_for_each(&mas, val, 925) { MT_BUG_ON(mt, mas.index != i * 10); MT_BUG_ON(mt, mas.last != i * 10 + 9); /* Overwrite end of entry 92 */ if (i == 92) { mas.index = 925; mas.last = 929; mas_store(&mas, val); } i++; } /* Ensure mas_find() gets the next value */ val = mas_find(&mas, ULONG_MAX); MT_BUG_ON(mt, val != xa_mk_value(i));
mas_set(&mas, 0); i = 0; mas_for_each(&mas, val, 785) { MT_BUG_ON(mt, mas.index != i * 10); MT_BUG_ON(mt, mas.last != i * 10 + 9); /* Overwrite start of entry 78 */ if (i == 78) { mas.index = 780; mas.last = 785; mas_store(&mas, val); } else { i++; } } val = mas_find(&mas, ULONG_MAX); MT_BUG_ON(mt, val != xa_mk_value(i));
mas_set(&mas, 0); i = 0; mas_for_each(&mas, val, 765) { MT_BUG_ON(mt, mas.index != i * 10); MT_BUG_ON(mt, mas.last != i * 10 + 9); /* Overwrite end of entry 76 and advance to the end */ if (i == 76) { mas.index = 760; mas.last = 765; mas_store(&mas, val); } i++; } /* Make sure the next find returns the one after 765, 766-769 */ val = mas_find(&mas, ULONG_MAX); MT_BUG_ON(mt, val != xa_mk_value(76)); mas_unlock(&mas); mas_destroy(&mas); mt_set_non_kernel(0);}
static noinline void __init check_mas_store_gfp(struct maple_tree *mt){
struct maple_tree newmt; int i, nr_entries = 135; void *val; MA_STATE(mas, mt, 0, 0); MA_STATE(newmas, mt, 0, 0);
for (i = 0; i <= nr_entries; i++) mtree_store_range(mt, i*10, i*10 + 5, xa_mk_value(i), GFP_KERNEL);
mt_set_non_kernel(99999); mt_init_flags(&newmt, MT_FLAGS_ALLOC_RANGE); newmas.tree = &newmt; rcu_read_lock(); mas_lock(&newmas); mas_reset(&newmas); mas_set(&mas, 0); mas_for_each(&mas, val, ULONG_MAX) { newmas.index = mas.index; newmas.last = mas.last; mas_store_gfp(&newmas, val, GFP_KERNEL); } mas_unlock(&newmas); rcu_read_unlock(); mt_validate(&newmt); mt_set_non_kernel(0); mtree_destroy(&newmt);}
#if defined(BENCH_FORK)static noinline void __init bench_forking(void){ struct maple_tree mt, newmt; int i, nr_entries = 134, nr_fork = 80000, ret; void *val; MA_STATE(mas, &mt, 0, 0); MA_STATE(newmas, &newmt, 0, 0); struct rw_semaphore mt_lock, newmt_lock;
init_rwsem(&mt_lock); init_rwsem(&newmt_lock);
mt_init_flags(&mt, MT_FLAGS_ALLOC_RANGE | MT_FLAGS_LOCK_EXTERN); mt_set_external_lock(&mt, &mt_lock);
down_write(&mt_lock); for (i = 0; i <= nr_entries; i++) { mas_set_range(&mas, i*10, i*10 + 5); mas_store_gfp(&mas, xa_mk_value(i), GFP_KERNEL); }
for (i = 0; i < nr_fork; i++) { mt_init_flags(&newmt, MT_FLAGS_ALLOC_RANGE | MT_FLAGS_LOCK_EXTERN); mt_set_external_lock(&newmt, &newmt_lock);
down_write_nested(&newmt_lock, SINGLE_DEPTH_NESTING); ret = __mt_dup(&mt, &newmt, GFP_KERNEL); if (ret) { pr_err("OOM!"); BUG_ON(1); }
mas_set(&newmas, 0); mas_for_each(&newmas, val, ULONG_MAX) mas_store(&newmas, val);
mas_destroy(&newmas); mt_validate(&newmt); __mt_destroy(&newmt); up_write(&newmt_lock); } mas_destroy(&mas); __mt_destroy(&mt); up_write(&mt_lock);}#endif
static noinline void __init next_prev_test(struct maple_tree *mt){ int i, nr_entries; void *val; MA_STATE(mas, mt, 0, 0); struct maple_enode *mn; static const unsigned long *level2; static const unsigned long level2_64[] = { 707, 1000, 710, 715, 720, 725}; static const unsigned long level2_32[] = { 1747, 2000, 1750, 1755, 1760, 1765}; unsigned long last_index;
if (MAPLE_32BIT) { nr_entries = 500; level2 = level2_32; last_index = 0x138e; } else { nr_entries = 200; level2 = level2_64; last_index = 0x7d6; }
for (i = 0; i <= nr_entries; i++) mtree_store_range(mt, i*10, i*10 + 5, xa_mk_value(i), GFP_KERNEL);
mas_lock(&mas); for (i = 0; i <= nr_entries / 2; i++) { mas_next(&mas, 1000); if (mas_is_none(&mas)) break;
} mas_reset(&mas); mas_set(&mas, 0); i = 0; mas_for_each(&mas, val, 1000) { i++; }
mas_reset(&mas); mas_set(&mas, 0); i = 0; mas_for_each(&mas, val, 1000) { mas_pause(&mas); i++; }
/* * 680 - 685 = 0x61a00001930c * 686 - 689 = NULL; * 690 - 695 = 0x61a00001930c * Check simple next/prev */ mas_set(&mas, 686); val = mas_walk(&mas); MT_BUG_ON(mt, val != NULL);
val = mas_next(&mas, 1000); MT_BUG_ON(mt, val != xa_mk_value(690 / 10)); MT_BUG_ON(mt, mas.index != 690); MT_BUG_ON(mt, mas.last != 695);
val = mas_prev(&mas, 0); MT_BUG_ON(mt, val != xa_mk_value(680 / 10)); MT_BUG_ON(mt, mas.index != 680); MT_BUG_ON(mt, mas.last != 685);
val = mas_next(&mas, 1000); MT_BUG_ON(mt, val != xa_mk_value(690 / 10)); MT_BUG_ON(mt, mas.index != 690); MT_BUG_ON(mt, mas.last != 695);
val = mas_next(&mas, 1000); MT_BUG_ON(mt, val != xa_mk_value(700 / 10)); MT_BUG_ON(mt, mas.index != 700); MT_BUG_ON(mt, mas.last != 705);
/* Check across node boundaries of the tree */ mas_set(&mas, 70); val = mas_walk(&mas); MT_BUG_ON(mt, val != xa_mk_value(70 / 10)); MT_BUG_ON(mt, mas.index != 70); MT_BUG_ON(mt, mas.last != 75);
val = mas_next(&mas, 1000); MT_BUG_ON(mt, val != xa_mk_value(80 / 10)); MT_BUG_ON(mt, mas.index != 80); MT_BUG_ON(mt, mas.last != 85);
val = mas_prev(&mas, 70); MT_BUG_ON(mt, val != xa_mk_value(70 / 10)); MT_BUG_ON(mt, mas.index != 70); MT_BUG_ON(mt, mas.last != 75);
/* Check across two levels of the tree */ mas_reset(&mas); mas_set(&mas, level2[0]); val = mas_walk(&mas); MT_BUG_ON(mt, val != NULL); val = mas_next(&mas, level2[1]); MT_BUG_ON(mt, val != xa_mk_value(level2[2] / 10)); MT_BUG_ON(mt, mas.index != level2[2]); MT_BUG_ON(mt, mas.last != level2[3]); mn = mas.node;
val = mas_next(&mas, level2[1]); MT_BUG_ON(mt, val != xa_mk_value(level2[4] / 10)); MT_BUG_ON(mt, mas.index != level2[4]); MT_BUG_ON(mt, mas.last != level2[5]); MT_BUG_ON(mt, mn == mas.node);
val = mas_prev(&mas, 0); MT_BUG_ON(mt, val != xa_mk_value(level2[2] / 10)); MT_BUG_ON(mt, mas.index != level2[2]); MT_BUG_ON(mt, mas.last != level2[3]);
/* Check running off the end and back on */ mas_set(&mas, nr_entries * 10); val = mas_walk(&mas); MT_BUG_ON(mt, val != xa_mk_value(nr_entries)); MT_BUG_ON(mt, mas.index != (nr_entries * 10)); MT_BUG_ON(mt, mas.last != (nr_entries * 10 + 5));
val = mas_next(&mas, ULONG_MAX); MT_BUG_ON(mt, val != NULL); MT_BUG_ON(mt, mas.index != last_index); MT_BUG_ON(mt, mas.last != ULONG_MAX);
val = mas_prev(&mas, 0); MT_BUG_ON(mt, val != xa_mk_value(nr_entries)); MT_BUG_ON(mt, mas.index != (nr_entries * 10)); MT_BUG_ON(mt, mas.last != (nr_entries * 10 + 5));
/* Check running off the start and back on */ mas_reset(&mas); mas_set(&mas, 10); val = mas_walk(&mas); MT_BUG_ON(mt, val != xa_mk_value(1)); MT_BUG_ON(mt, mas.index != 10); MT_BUG_ON(mt, mas.last != 15);
val = mas_prev(&mas, 0); MT_BUG_ON(mt, val != xa_mk_value(0)); MT_BUG_ON(mt, mas.index != 0); MT_BUG_ON(mt, mas.last != 5);
val = mas_prev(&mas, 0); MT_BUG_ON(mt, val != NULL); MT_BUG_ON(mt, mas.index != 0); MT_BUG_ON(mt, mas.last != 5); MT_BUG_ON(mt, !mas_is_underflow(&mas));
mas.index = 0; mas.last = 5; mas_store(&mas, NULL); mas_reset(&mas); mas_set(&mas, 10); mas_walk(&mas);
val = mas_prev(&mas, 0); MT_BUG_ON(mt, val != NULL); MT_BUG_ON(mt, mas.index != 0); MT_BUG_ON(mt, mas.last != 9); mas_unlock(&mas);
mtree_destroy(mt);
mt_init(mt); mtree_store_range(mt, 0, 0, xa_mk_value(0), GFP_KERNEL); mtree_store_range(mt, 5, 5, xa_mk_value(5), GFP_KERNEL); rcu_read_lock(); mas_set(&mas, 5); val = mas_prev(&mas, 4); MT_BUG_ON(mt, val != NULL); rcu_read_unlock();}
/* Test spanning writes that require balancing right sibling or right cousin */static noinline void __init check_spanning_relatives(struct maple_tree *mt){
unsigned long i, nr_entries = 1000;
for (i = 0; i <= nr_entries; i++) mtree_store_range(mt, i*10, i*10 + 5, xa_mk_value(i), GFP_KERNEL);
mtree_store_range(mt, 9365, 9955, NULL, GFP_KERNEL);}
static noinline void __init check_fuzzer(struct maple_tree *mt){ /* * 1. Causes a spanning rebalance of a single root node. * Fixed by setting the correct limit in mast_cp_to_nodes() when the * entire right side is consumed. */ mtree_test_insert(mt, 88, (void *)0xb1); mtree_test_insert(mt, 84, (void *)0xa9); mtree_test_insert(mt, 2, (void *)0x5); mtree_test_insert(mt, 4, (void *)0x9); mtree_test_insert(mt, 14, (void *)0x1d); mtree_test_insert(mt, 7, (void *)0xf); mtree_test_insert(mt, 12, (void *)0x19); mtree_test_insert(mt, 18, (void *)0x25); mtree_test_store_range(mt, 8, 18, (void *)0x11); mtree_destroy(mt);
/* * 2. Cause a spanning rebalance of two nodes in root. * Fixed by setting mast->r->max correctly. */ mt_init_flags(mt, 0); mtree_test_store(mt, 87, (void *)0xaf); mtree_test_store(mt, 0, (void *)0x1); mtree_test_load(mt, 4); mtree_test_insert(mt, 4, (void *)0x9); mtree_test_store(mt, 8, (void *)0x11); mtree_test_store(mt, 44, (void *)0x59); mtree_test_store(mt, 68, (void *)0x89); mtree_test_store(mt, 2, (void *)0x5); mtree_test_insert(mt, 43, (void *)0x57); mtree_test_insert(mt, 24, (void *)0x31); mtree_test_insert(mt, 844, (void *)0x699); mtree_test_store(mt, 84, (void *)0xa9); mtree_test_store(mt, 4, (void *)0x9); mtree_test_erase(mt, 4); mtree_test_load(mt, 5); mtree_test_erase(mt, 0); mtree_destroy(mt);
/* * 3. Cause a node overflow on copy * Fixed by using the correct check for node size in mas_wr_modify() * Also discovered issue with metadata setting. */ mt_init_flags(mt, 0); mtree_test_store_range(mt, 0, ULONG_MAX, (void *)0x1); mtree_test_store(mt, 4, (void *)0x9); mtree_test_erase(mt, 5); mtree_test_erase(mt, 0); mtree_test_erase(mt, 4); mtree_test_store(mt, 5, (void *)0xb); mtree_test_erase(mt, 5); mtree_test_store(mt, 5, (void *)0xb); mtree_test_erase(mt, 5); mtree_test_erase(mt, 4); mtree_test_store(mt, 4, (void *)0x9); mtree_test_store(mt, 444, (void *)0x379); mtree_test_store(mt, 0, (void *)0x1); mtree_test_load(mt, 0); mtree_test_store(mt, 5, (void *)0xb); mtree_test_erase(mt, 0); mtree_destroy(mt);
/* * 4. spanning store failure due to writing incorrect pivot value at * last slot. * Fixed by setting mast->r->max correctly in mast_cp_to_nodes() * */ mt_init_flags(mt, 0); mtree_test_insert(mt, 261, (void *)0x20b); mtree_test_store(mt, 516, (void *)0x409); mtree_test_store(mt, 6, (void *)0xd); mtree_test_insert(mt, 5, (void *)0xb); mtree_test_insert(mt, 1256, (void *)0x9d1); mtree_test_store(mt, 4, (void *)0x9); mtree_test_erase(mt, 1); mtree_test_store(mt, 56, (void *)0x71); mtree_test_insert(mt, 1, (void *)0x3); mtree_test_store(mt, 24, (void *)0x31); mtree_test_erase(mt, 1); mtree_test_insert(mt, 2263, (void *)0x11af); mtree_test_insert(mt, 446, (void *)0x37d); mtree_test_store_range(mt, 6, 45, (void *)0xd); mtree_test_store_range(mt, 3, 446, (void *)0x7); mtree_destroy(mt);
/* * 5. mas_wr_extend_null() may overflow slots. * Fix by checking against wr_mas->node_end. */ mt_init_flags(mt, 0); mtree_test_store(mt, 48, (void *)0x61); mtree_test_store(mt, 3, (void *)0x7); mtree_test_load(mt, 0); mtree_test_store(mt, 88, (void *)0xb1); mtree_test_store(mt, 81, (void *)0xa3); mtree_test_insert(mt, 0, (void *)0x1); mtree_test_insert(mt, 8, (void *)0x11); mtree_test_insert(mt, 4, (void *)0x9); mtree_test_insert(mt, 2480, (void *)0x1361); mtree_test_insert(mt, ULONG_MAX, (void *)0xffffffffffffffff); mtree_test_erase(mt, ULONG_MAX); mtree_destroy(mt);
/* * 6. When reusing a node with an implied pivot and the node is * shrinking, old data would be left in the implied slot * Fixed by checking the last pivot for the mas->max and clear * accordingly. This only affected the left-most node as that node is * the only one allowed to end in NULL. */ mt_init_flags(mt, 0); mtree_test_erase(mt, 3); mtree_test_insert(mt, 22, (void *)0x2d); mtree_test_insert(mt, 15, (void *)0x1f); mtree_test_load(mt, 2); mtree_test_insert(mt, 1, (void *)0x3); mtree_test_insert(mt, 1, (void *)0x3); mtree_test_insert(mt, 5, (void *)0xb); mtree_test_erase(mt, 1); mtree_test_insert(mt, 1, (void *)0x3); mtree_test_insert(mt, 4, (void *)0x9); mtree_test_insert(mt, 1, (void *)0x3); mtree_test_erase(mt, 1); mtree_test_insert(mt, 2, (void *)0x5); mtree_test_insert(mt, 1, (void *)0x3); mtree_test_erase(mt, 3); mtree_test_insert(mt, 22, (void *)0x2d); mtree_test_insert(mt, 15, (void *)0x1f); mtree_test_insert(mt, 2, (void *)0x5); mtree_test_insert(mt, 1, (void *)0x3); mtree_test_insert(mt, 8, (void *)0x11); mtree_test_load(mt, 2); mtree_test_insert(mt, 1, (void *)0x3); mtree_test_insert(mt, 1, (void *)0x3); mtree_test_store(mt, 1, (void *)0x3); mtree_test_insert(mt, 5, (void *)0xb); mtree_test_erase(mt, 1); mtree_test_insert(mt, 1, (void *)0x3); mtree_test_insert(mt, 4, (void *)0x9); mtree_test_insert(mt, 1, (void *)0x3); mtree_test_erase(mt, 1); mtree_test_insert(mt, 2, (void *)0x5); mtree_test_insert(mt, 1, (void *)0x3); mtree_test_erase(mt, 3); mtree_test_insert(mt, 22, (void *)0x2d); mtree_test_insert(mt, 15, (void *)0x1f); mtree_test_insert(mt, 2, (void *)0x5); mtree_test_insert(mt, 1, (void *)0x3); mtree_test_insert(mt, 8, (void *)0x11); mtree_test_insert(mt, 12, (void *)0x19); mtree_test_erase(mt, 1); mtree_test_store_range(mt, 4, 62, (void *)0x9); mtree_test_erase(mt, 62); mtree_test_store_range(mt, 1, 0, (void *)0x3); mtree_test_insert(mt, 11, (void *)0x17); mtree_test_insert(mt, 3, (void *)0x7); mtree_test_insert(mt, 3, (void *)0x7); mtree_test_store(mt, 62, (void *)0x7d); mtree_test_erase(mt, 62); mtree_test_store_range(mt, 1, 15, (void *)0x3); mtree_test_erase(mt, 1); mtree_test_insert(mt, 22, (void *)0x2d); mtree_test_insert(mt, 12, (void *)0x19); mtree_test_erase(mt, 1); mtree_test_insert(mt, 3, (void *)0x7); mtree_test_store(mt, 62, (void *)0x7d); mtree_test_erase(mt, 62); mtree_test_insert(mt, 122, (void *)0xf5); mtree_test_store(mt, 3, (void *)0x7); mtree_test_insert(mt, 0, (void *)0x1); mtree_test_store_range(mt, 0, 1, (void *)0x1); mtree_test_insert(mt, 85, (void *)0xab); mtree_test_insert(mt, 72, (void *)0x91); mtree_test_insert(mt, 81, (void *)0xa3); mtree_test_insert(mt, 726, (void *)0x5ad); mtree_test_insert(mt, 0, (void *)0x1); mtree_test_insert(mt, 1, (void *)0x3); mtree_test_store(mt, 51, (void *)0x67); mtree_test_insert(mt, 611, (void *)0x4c7); mtree_test_insert(mt, 485, (void *)0x3cb); mtree_test_insert(mt, 1, (void *)0x3); mtree_test_erase(mt, 1); mtree_test_insert(mt, 0, (void *)0x1); mtree_test_insert(mt, 1, (void *)0x3); mtree_test_insert_range(mt, 26, 1, (void *)0x35); mtree_test_load(mt, 1); mtree_test_store_range(mt, 1, 22, (void *)0x3); mtree_test_insert(mt, 1, (void *)0x3); mtree_test_erase(mt, 1); mtree_test_load(mt, 53); mtree_test_load(mt, 1); mtree_test_store_range(mt, 1, 1, (void *)0x3); mtree_test_insert(mt, 222, (void *)0x1bd); mtree_test_insert(mt, 485, (void *)0x3cb); mtree_test_insert(mt, 1, (void *)0x3); mtree_test_erase(mt, 1); mtree_test_load(mt, 0); mtree_test_insert(mt, 21, (void *)0x2b); mtree_test_insert(mt, 3, (void *)0x7); mtree_test_store(mt, 621, (void *)0x4db); mtree_test_insert(mt, 0, (void *)0x1); mtree_test_erase(mt, 5); mtree_test_insert(mt, 1, (void *)0x3); mtree_test_store(mt, 62, (void *)0x7d); mtree_test_erase(mt, 62); mtree_test_store_range(mt, 1, 0, (void *)0x3); mtree_test_insert(mt, 22, (void *)0x2d); mtree_test_insert(mt, 12, (void *)0x19); mtree_test_erase(mt, 1); mtree_test_insert(mt, 1, (void *)0x3); mtree_test_store_range(mt, 4, 62, (void *)0x9); mtree_test_erase(mt, 62); mtree_test_erase(mt, 1); mtree_test_load(mt, 1); mtree_test_store_range(mt, 1, 22, (void *)0x3); mtree_test_insert(mt, 1, (void *)0x3); mtree_test_erase(mt, 1); mtree_test_load(mt, 53); mtree_test_load(mt, 1); mtree_test_store_range(mt, 1, 1, (void *)0x3); mtree_test_insert(mt, 222, (void *)0x1bd); mtree_test_insert(mt, 485, (void *)0x3cb); mtree_test_insert(mt, 1, (void *)0x3); mtree_test_erase(mt, 1); mtree_test_insert(mt, 1, (void *)0x3); mtree_test_load(mt, 0); mtree_test_load(mt, 0); mtree_destroy(mt);
/* * 7. Previous fix was incomplete, fix mas_resuse_node() clearing of old * data by overwriting it first - that way metadata is of no concern. */ mt_init_flags(mt, 0); mtree_test_load(mt, 1); mtree_test_insert(mt, 102, (void *)0xcd); mtree_test_erase(mt, 2); mtree_test_erase(mt, 0); mtree_test_load(mt, 0); mtree_test_insert(mt, 4, (void *)0x9); mtree_test_insert(mt, 2, (void *)0x5); mtree_test_insert(mt, 110, (void *)0xdd); mtree_test_insert(mt, 1, (void *)0x3); mtree_test_insert_range(mt, 5, 0, (void *)0xb); mtree_test_erase(mt, 2); mtree_test_store(mt, 0, (void *)0x1); mtree_test_store(mt, 112, (void *)0xe1); mtree_test_insert(mt, 21, (void *)0x2b); mtree_test_store(mt, 1, (void *)0x3); mtree_test_insert_range(mt, 110, 2, (void *)0xdd); mtree_test_store(mt, 2, (void *)0x5); mtree_test_load(mt, 22); mtree_test_erase(mt, 2); mtree_test_store(mt, 210, (void *)0x1a5); mtree_test_store_range(mt, 0, 2, (void *)0x1); mtree_test_store(mt, 2, (void *)0x5); mtree_test_erase(mt, 2); mtree_test_erase(mt, 22); mtree_test_erase(mt, 1); mtree_test_erase(mt, 2); mtree_test_store(mt, 0, (void *)0x1); mtree_test_load(mt, 112); mtree_test_insert(mt, 2, (void *)0x5); mtree_test_erase(mt, 2); mtree_test_store(mt, 1, (void *)0x3); mtree_test_insert_range(mt, 1, 2, (void *)0x3); mtree_test_erase(mt, 0); mtree_test_erase(mt, 2); mtree_test_store(mt, 2, (void *)0x5); mtree_test_erase(mt, 0); mtree_test_erase(mt, 2); mtree_test_store(mt, 0, (void *)0x1); mtree_test_store(mt, 0, (void *)0x1); mtree_test_erase(mt, 2); mtree_test_store(mt, 2, (void *)0x5); mtree_test_erase(mt, 2); mtree_test_insert(mt, 2, (void *)0x5); mtree_test_insert_range(mt, 1, 2, (void *)0x3); mtree_test_erase(mt, 0); mtree_test_erase(mt, 2); mtree_test_store(mt, 0, (void *)0x1); mtree_test_load(mt, 112); mtree_test_store_range(mt, 110, 12, (void *)0xdd); mtree_test_store(mt, 2, (void *)0x5); mtree_test_load(mt, 110); mtree_test_insert_range(mt, 4, 71, (void *)0x9); mtree_test_load(mt, 2); mtree_test_store(mt, 2, (void *)0x5); mtree_test_insert_range(mt, 11, 22, (void *)0x17); mtree_test_erase(mt, 12); mtree_test_store(mt, 2, (void *)0x5); mtree_test_load(mt, 22); mtree_destroy(mt);
/* * 8. When rebalancing or spanning_rebalance(), the max of the new node * may be set incorrectly to the final pivot and not the right max. * Fix by setting the left max to orig right max if the entire node is * consumed. */ mt_init_flags(mt, 0); mtree_test_store(mt, 6, (void *)0xd); mtree_test_store(mt, 67, (void *)0x87); mtree_test_insert(mt, 15, (void *)0x1f); mtree_test_insert(mt, 6716, (void *)0x3479); mtree_test_store(mt, 61, (void *)0x7b); mtree_test_insert(mt, 13, (void *)0x1b); mtree_test_store(mt, 8, (void *)0x11); mtree_test_insert(mt, 1, (void *)0x3); mtree_test_load(mt, 0); mtree_test_erase(mt, 67167); mtree_test_insert_range(mt, 6, 7167, (void *)0xd); mtree_test_insert(mt, 6, (void *)0xd); mtree_test_erase(mt, 67); mtree_test_insert(mt, 1, (void *)0x3); mtree_test_erase(mt, 667167); mtree_test_insert(mt, 6, (void *)0xd); mtree_test_store(mt, 67, (void *)0x87); mtree_test_insert(mt, 5, (void *)0xb); mtree_test_erase(mt, 1); mtree_test_insert(mt, 6, (void *)0xd); mtree_test_erase(mt, 67); mtree_test_insert(mt, 15, (void *)0x1f); mtree_test_insert(mt, 67167, (void *)0x20cbf); mtree_test_insert(mt, 1, (void *)0x3); mtree_test_load(mt, 7); mtree_test_insert(mt, 16, (void *)0x21); mtree_test_insert(mt, 36, (void *)0x49); mtree_test_store(mt, 67, (void *)0x87); mtree_test_store(mt, 6, (void *)0xd); mtree_test_insert(mt, 367, (void *)0x2df); mtree_test_insert(mt, 115, (void *)0xe7); mtree_test_store(mt, 0, (void *)0x1); mtree_test_store_range(mt, 1, 3, (void *)0x3); mtree_test_store(mt, 1, (void *)0x3); mtree_test_erase(mt, 67167); mtree_test_insert_range(mt, 6, 47, (void *)0xd); mtree_test_store(mt, 1, (void *)0x3); mtree_test_insert_range(mt, 1, 67, (void *)0x3); mtree_test_load(mt, 67); mtree_test_insert(mt, 1, (void *)0x3); mtree_test_erase(mt, 67167); mtree_destroy(mt);
/* * 9. spanning store to the end of data caused an invalid metadata * length which resulted in a crash eventually. * Fix by checking if there is a value in pivot before incrementing the * metadata end in mab_mas_cp(). To ensure this doesn't happen again, * abstract the two locations this happens into a function called * mas_leaf_set_meta(). */ mt_init_flags(mt, 0); mtree_test_insert(mt, 21, (void *)0x2b); mtree_test_insert(mt, 12, (void *)0x19); mtree_test_insert(mt, 6, (void *)0xd); mtree_test_insert(mt, 8, (void *)0x11); mtree_test_insert(mt, 2, (void *)0x5); mtree_test_insert(mt, 91, (void *)0xb7); mtree_test_insert(mt, 18, (void *)0x25); mtree_test_insert(mt, 81, (void *)0xa3); mtree_test_store_range(mt, 0, 128, (void *)0x1); mtree_test_store(mt, 1, (void *)0x3); mtree_test_erase(mt, 8); mtree_test_insert(mt, 11, (void *)0x17); mtree_test_insert(mt, 8, (void *)0x11); mtree_test_insert(mt, 21, (void *)0x2b); mtree_test_insert(mt, 2, (void *)0x5); mtree_test_insert(mt, ULONG_MAX - 10, (void *)0xffffffffffffffeb); mtree_test_erase(mt, ULONG_MAX - 10); mtree_test_store_range(mt, 0, 281, (void *)0x1); mtree_test_erase(mt, 2); mtree_test_insert(mt, 1211, (void *)0x977); mtree_test_insert(mt, 111, (void *)0xdf); mtree_test_insert(mt, 13, (void *)0x1b); mtree_test_insert(mt, 211, (void *)0x1a7); mtree_test_insert(mt, 11, (void *)0x17); mtree_test_insert(mt, 5, (void *)0xb); mtree_test_insert(mt, 1218, (void *)0x985); mtree_test_insert(mt, 61, (void *)0x7b); mtree_test_store(mt, 1, (void *)0x3); mtree_test_insert(mt, 121, (void *)0xf3); mtree_test_insert(mt, 8, (void *)0x11); mtree_test_insert(mt, 21, (void *)0x2b); mtree_test_insert(mt, 2, (void *)0x5); mtree_test_insert(mt, ULONG_MAX - 10, (void *)0xffffffffffffffeb); mtree_test_erase(mt, ULONG_MAX - 10);}
static noinline void __init check_bnode_min_spanning(struct maple_tree *mt){ int i = 50; MA_STATE(mas, mt, 0, 0);
mt_set_non_kernel(9999); mas_lock(&mas); do { mas_set_range(&mas, i*10, i*10+9); mas_store(&mas, check_bnode_min_spanning); } while (i--);
mas_set_range(&mas, 240, 509); mas_store(&mas, NULL); mas_unlock(&mas); mas_destroy(&mas); mt_set_non_kernel(0);}
static noinline void __init check_empty_area_window(struct maple_tree *mt){ unsigned long i, nr_entries = 20; MA_STATE(mas, mt, 0, 0);
for (i = 1; i <= nr_entries; i++) mtree_store_range(mt, i*10, i*10 + 9, xa_mk_value(i), GFP_KERNEL);
/* Create another hole besides the one at 0 */ mtree_store_range(mt, 160, 169, NULL, GFP_KERNEL);
/* Check lower bounds that don't fit */ rcu_read_lock(); MT_BUG_ON(mt, mas_empty_area_rev(&mas, 5, 90, 10) != -EBUSY);
mas_reset(&mas); MT_BUG_ON(mt, mas_empty_area_rev(&mas, 6, 90, 5) != -EBUSY);
/* Check lower bound that does fit */ mas_reset(&mas); MT_BUG_ON(mt, mas_empty_area_rev(&mas, 5, 90, 5) != 0); MT_BUG_ON(mt, mas.index != 5); MT_BUG_ON(mt, mas.last != 9); rcu_read_unlock();
/* Check one gap that doesn't fit and one that does */ rcu_read_lock(); mas_reset(&mas); MT_BUG_ON(mt, mas_empty_area_rev(&mas, 5, 217, 9) != 0); MT_BUG_ON(mt, mas.index != 161); MT_BUG_ON(mt, mas.last != 169);
/* Check one gap that does fit above the min */ mas_reset(&mas); MT_BUG_ON(mt, mas_empty_area_rev(&mas, 100, 218, 3) != 0); MT_BUG_ON(mt, mas.index != 216); MT_BUG_ON(mt, mas.last != 218);
/* Check size that doesn't fit any gap */ mas_reset(&mas); MT_BUG_ON(mt, mas_empty_area_rev(&mas, 100, 218, 16) != -EBUSY);
/* * Check size that doesn't fit the lower end of the window but * does fit the gap */ mas_reset(&mas); MT_BUG_ON(mt, mas_empty_area_rev(&mas, 167, 200, 4) != -EBUSY);
/* * Check size that doesn't fit the upper end of the window but * does fit the gap */ mas_reset(&mas); MT_BUG_ON(mt, mas_empty_area_rev(&mas, 100, 162, 4) != -EBUSY);
/* Check mas_empty_area forward */ mas_reset(&mas); MT_BUG_ON(mt, mas_empty_area(&mas, 0, 100, 9) != 0); MT_BUG_ON(mt, mas.index != 0); MT_BUG_ON(mt, mas.last != 8);
mas_reset(&mas); MT_BUG_ON(mt, mas_empty_area(&mas, 0, 100, 4) != 0); MT_BUG_ON(mt, mas.index != 0); MT_BUG_ON(mt, mas.last != 3);
mas_reset(&mas); MT_BUG_ON(mt, mas_empty_area(&mas, 0, 100, 11) != -EBUSY);
mas_reset(&mas); MT_BUG_ON(mt, mas_empty_area(&mas, 5, 100, 6) != -EBUSY);
mas_reset(&mas); MT_BUG_ON(mt, mas_empty_area(&mas, 0, 8, 10) != -EINVAL);
mas_reset(&mas); mas_empty_area(&mas, 100, 165, 3);
mas_reset(&mas); MT_BUG_ON(mt, mas_empty_area(&mas, 100, 163, 6) != -EBUSY); rcu_read_unlock();}
static noinline void __init check_empty_area_fill(struct maple_tree *mt){ const unsigned long max = 0x25D78000; unsigned long size; int loop, shift; MA_STATE(mas, mt, 0, 0);
mt_set_non_kernel(99999); for (shift = 12; shift <= 16; shift++) { loop = 5000; size = 1 << shift; while (loop--) { mas_set(&mas, 0); mas_lock(&mas); MT_BUG_ON(mt, mas_empty_area(&mas, 0, max, size) != 0); MT_BUG_ON(mt, mas.last != mas.index + size - 1); mas_store_gfp(&mas, (void *)size, GFP_KERNEL); mas_unlock(&mas); mas_reset(&mas); } }
/* No space left. */ size = 0x1000; rcu_read_lock(); MT_BUG_ON(mt, mas_empty_area(&mas, 0, max, size) != -EBUSY); rcu_read_unlock();
/* Fill a depth 3 node to the maximum */ for (unsigned long i = 629440511; i <= 629440800; i += 6) mtree_store_range(mt, i, i + 5, (void *)i, GFP_KERNEL); /* Make space in the second-last depth 4 node */ mtree_erase(mt, 631668735); /* Make space in the last depth 4 node */ mtree_erase(mt, 629506047); mas_reset(&mas); /* Search from just after the gap in the second-last depth 4 */ rcu_read_lock(); MT_BUG_ON(mt, mas_empty_area(&mas, 629506048, 690000000, 0x5000) != 0); rcu_read_unlock(); mt_set_non_kernel(0);}
/* * Check MAS_START, MAS_PAUSE, active (implied), and MAS_NONE transitions. * * The table below shows the single entry tree (0-0 pointer) and normal tree * with nodes. * * Function ENTRY Start Result index & last * ┬ ┬ ┬ ┬ ┬ * │ │ │ │ └─ the final range * │ │ │ └─ The node value after execution * │ │ └─ The node value before execution * │ └─ If the entry exists or does not exists (DNE) * └─ The function name * * Function ENTRY Start Result index & last * mas_next() * - after last * Single entry tree at 0-0 * ------------------------ * DNE MAS_START MAS_NONE 1 - oo * DNE MAS_PAUSE MAS_NONE 1 - oo * DNE MAS_ROOT MAS_NONE 1 - oo * when index = 0 * DNE MAS_NONE MAS_ROOT 0 * when index > 0 * DNE MAS_NONE MAS_NONE 1 - oo * * Normal tree * ----------- * exists MAS_START active range * DNE MAS_START active set to last range * exists MAS_PAUSE active range * DNE MAS_PAUSE active set to last range * exists MAS_NONE active range * exists active active range * DNE active active set to last range * ERANGE active MAS_OVERFLOW last range * * Function ENTRY Start Result index & last * mas_prev() * - before index * Single entry tree at 0-0 * ------------------------ * if index > 0 * exists MAS_START MAS_ROOT 0 * exists MAS_PAUSE MAS_ROOT 0 * exists MAS_NONE MAS_ROOT 0 * * if index == 0 * DNE MAS_START MAS_NONE 0 * DNE MAS_PAUSE MAS_NONE 0 * DNE MAS_NONE MAS_NONE 0 * DNE MAS_ROOT MAS_NONE 0 * * Normal tree * ----------- * exists MAS_START active range * DNE MAS_START active set to min * exists MAS_PAUSE active range * DNE MAS_PAUSE active set to min * exists MAS_NONE active range * DNE MAS_NONE MAS_NONE set to min * any MAS_ROOT MAS_NONE 0 * exists active active range * DNE active active last range * ERANGE active MAS_UNDERFLOW last range * * Function ENTRY Start Result index & last * mas_find() * - at index or next * Single entry tree at 0-0 * ------------------------ * if index > 0 * DNE MAS_START MAS_NONE 0 * DNE MAS_PAUSE MAS_NONE 0 * DNE MAS_ROOT MAS_NONE 0 * DNE MAS_NONE MAS_NONE 1 * if index == 0 * exists MAS_START MAS_ROOT 0 * exists MAS_PAUSE MAS_ROOT 0 * exists MAS_NONE MAS_ROOT 0 * * Normal tree * ----------- * exists MAS_START active range * DNE MAS_START active set to max * exists MAS_PAUSE active range * DNE MAS_PAUSE active set to max * exists MAS_NONE active range (start at last) * exists active active range * DNE active active last range (max < last) * * Function ENTRY Start Result index & last * mas_find_rev() * - at index or before * Single entry tree at 0-0 * ------------------------ * if index > 0 * exists MAS_START MAS_ROOT 0 * exists MAS_PAUSE MAS_ROOT 0 * exists MAS_NONE MAS_ROOT 0 * if index == 0 * DNE MAS_START MAS_NONE 0 * DNE MAS_PAUSE MAS_NONE 0 * DNE MAS_NONE MAS_NONE 0 * DNE MAS_ROOT MAS_NONE 0 * * Normal tree * ----------- * exists MAS_START active range * DNE MAS_START active set to min * exists MAS_PAUSE active range * DNE MAS_PAUSE active set to min * exists MAS_NONE active range (start at index) * exists active active range * DNE active active last range (min > index) * * Function ENTRY Start Result index & last * mas_walk() * - Look up index * Single entry tree at 0-0 * ------------------------ * if index > 0 * DNE MAS_START MAS_ROOT 1 - oo * DNE MAS_PAUSE MAS_ROOT 1 - oo * DNE MAS_NONE MAS_ROOT 1 - oo * DNE MAS_ROOT MAS_ROOT 1 - oo * if index == 0 * exists MAS_START MAS_ROOT 0 * exists MAS_PAUSE MAS_ROOT 0 * exists MAS_NONE MAS_ROOT 0 * exists MAS_ROOT MAS_ROOT 0 * * Normal tree * ----------- * exists MAS_START active range * DNE MAS_START active range of NULL * exists MAS_PAUSE active range * DNE MAS_PAUSE active range of NULL * exists MAS_NONE active range * DNE MAS_NONE active range of NULL * exists active active range * DNE active active range of NULL */
static noinline void __init check_state_handling(struct maple_tree *mt){ MA_STATE(mas, mt, 0, 0); void *entry, *ptr = (void *) 0x1234500; void *ptr2 = &ptr; void *ptr3 = &ptr2; unsigned long index;
/* Check MAS_ROOT First */ mtree_store_range(mt, 0, 0, ptr, GFP_KERNEL);
mas_lock(&mas); /* prev: Start -> underflow*/ entry = mas_prev(&mas, 0); MT_BUG_ON(mt, entry != NULL); MT_BUG_ON(mt, mas.status != ma_underflow);
/* prev: Start -> root */ mas_set(&mas, 10); entry = mas_prev(&mas, 0); MT_BUG_ON(mt, entry != ptr); MT_BUG_ON(mt, mas.index != 0); MT_BUG_ON(mt, mas.last != 0); MT_BUG_ON(mt, mas.status != ma_root);
/* prev: pause -> root */ mas_set(&mas, 10); mas_pause(&mas); entry = mas_prev(&mas, 0); MT_BUG_ON(mt, entry != ptr); MT_BUG_ON(mt, mas.index != 0); MT_BUG_ON(mt, mas.last != 0); MT_BUG_ON(mt, mas.status != ma_root);
/* next: start -> none */ mas_set(&mas, 0); entry = mas_next(&mas, ULONG_MAX); MT_BUG_ON(mt, mas.index != 1); MT_BUG_ON(mt, mas.last != ULONG_MAX); MT_BUG_ON(mt, entry != NULL); MT_BUG_ON(mt, mas.status != ma_none);
/* next: start -> none*/ mas_set(&mas, 10); entry = mas_next(&mas, ULONG_MAX); MT_BUG_ON(mt, mas.index != 1); MT_BUG_ON(mt, mas.last != ULONG_MAX); MT_BUG_ON(mt, entry != NULL); MT_BUG_ON(mt, mas.status != ma_none);
/* find: start -> root */ mas_set(&mas, 0); entry = mas_find(&mas, ULONG_MAX); MT_BUG_ON(mt, entry != ptr); MT_BUG_ON(mt, mas.index != 0); MT_BUG_ON(mt, mas.last != 0); MT_BUG_ON(mt, mas.status != ma_root);
/* find: root -> none */ entry = mas_find(&mas, ULONG_MAX); MT_BUG_ON(mt, entry != NULL); MT_BUG_ON(mt, mas.index != 1); MT_BUG_ON(mt, mas.last != ULONG_MAX); MT_BUG_ON(mt, mas.status != ma_none);
/* find: none -> none */ entry = mas_find(&mas, ULONG_MAX); MT_BUG_ON(mt, entry != NULL); MT_BUG_ON(mt, mas.index != 1); MT_BUG_ON(mt, mas.last != ULONG_MAX); MT_BUG_ON(mt, mas.status != ma_none);
/* find: start -> none */ mas_set(&mas, 10); entry = mas_find(&mas, ULONG_MAX); MT_BUG_ON(mt, entry != NULL); MT_BUG_ON(mt, mas.index != 1); MT_BUG_ON(mt, mas.last != ULONG_MAX); MT_BUG_ON(mt, mas.status != ma_none);
/* find_rev: none -> root */ entry = mas_find_rev(&mas, 0); MT_BUG_ON(mt, entry != ptr); MT_BUG_ON(mt, mas.index != 0); MT_BUG_ON(mt, mas.last != 0); MT_BUG_ON(mt, mas.status != ma_root);
/* find_rev: start -> root */ mas_set(&mas, 0); entry = mas_find_rev(&mas, 0); MT_BUG_ON(mt, entry != ptr); MT_BUG_ON(mt, mas.index != 0); MT_BUG_ON(mt, mas.last != 0); MT_BUG_ON(mt, mas.status != ma_root);
/* find_rev: root -> none */ entry = mas_find_rev(&mas, 0); MT_BUG_ON(mt, entry != NULL); MT_BUG_ON(mt, mas.index != 0); MT_BUG_ON(mt, mas.last != 0); MT_BUG_ON(mt, mas.status != ma_none);
/* find_rev: none -> none */ entry = mas_find_rev(&mas, 0); MT_BUG_ON(mt, entry != NULL); MT_BUG_ON(mt, mas.index != 0); MT_BUG_ON(mt, mas.last != 0); MT_BUG_ON(mt, mas.status != ma_none);
/* find_rev: start -> root */ mas_set(&mas, 10); entry = mas_find_rev(&mas, 0); MT_BUG_ON(mt, entry != ptr); MT_BUG_ON(mt, mas.index != 0); MT_BUG_ON(mt, mas.last != 0); MT_BUG_ON(mt, mas.status != ma_root);
/* walk: start -> none */ mas_set(&mas, 10); entry = mas_walk(&mas); MT_BUG_ON(mt, entry != NULL); MT_BUG_ON(mt, mas.index != 1); MT_BUG_ON(mt, mas.last != ULONG_MAX); MT_BUG_ON(mt, mas.status != ma_none);
/* walk: pause -> none*/ mas_set(&mas, 10); mas_pause(&mas); entry = mas_walk(&mas); MT_BUG_ON(mt, entry != NULL); MT_BUG_ON(mt, mas.index != 1); MT_BUG_ON(mt, mas.last != ULONG_MAX); MT_BUG_ON(mt, mas.status != ma_none);
/* walk: none -> none */ mas.index = mas.last = 10; entry = mas_walk(&mas); MT_BUG_ON(mt, entry != NULL); MT_BUG_ON(mt, mas.index != 1); MT_BUG_ON(mt, mas.last != ULONG_MAX); MT_BUG_ON(mt, mas.status != ma_none);
/* walk: none -> none */ entry = mas_walk(&mas); MT_BUG_ON(mt, entry != NULL); MT_BUG_ON(mt, mas.index != 1); MT_BUG_ON(mt, mas.last != ULONG_MAX); MT_BUG_ON(mt, mas.status != ma_none);
/* walk: start -> root */ mas_set(&mas, 0); entry = mas_walk(&mas); MT_BUG_ON(mt, entry != ptr); MT_BUG_ON(mt, mas.index != 0); MT_BUG_ON(mt, mas.last != 0); MT_BUG_ON(mt, mas.status != ma_root);
/* walk: pause -> root */ mas_set(&mas, 0); mas_pause(&mas); entry = mas_walk(&mas); MT_BUG_ON(mt, entry != ptr); MT_BUG_ON(mt, mas.index != 0); MT_BUG_ON(mt, mas.last != 0); MT_BUG_ON(mt, mas.status != ma_root);
/* walk: none -> root */ mas.status = ma_none; entry = mas_walk(&mas); MT_BUG_ON(mt, entry != ptr); MT_BUG_ON(mt, mas.index != 0); MT_BUG_ON(mt, mas.last != 0); MT_BUG_ON(mt, mas.status != ma_root);
/* walk: root -> root */ entry = mas_walk(&mas); MT_BUG_ON(mt, entry != ptr); MT_BUG_ON(mt, mas.index != 0); MT_BUG_ON(mt, mas.last != 0); MT_BUG_ON(mt, mas.status != ma_root);
/* walk: root -> none */ mas_set(&mas, 10); entry = mas_walk(&mas); MT_BUG_ON(mt, entry != NULL); MT_BUG_ON(mt, mas.index != 1); MT_BUG_ON(mt, mas.last != ULONG_MAX); MT_BUG_ON(mt, mas.status != ma_none);
/* walk: none -> root */ mas.index = mas.last = 0; entry = mas_walk(&mas); MT_BUG_ON(mt, entry != ptr); MT_BUG_ON(mt, mas.index != 0); MT_BUG_ON(mt, mas.last != 0); MT_BUG_ON(mt, mas.status != ma_root);
mas_unlock(&mas);
/* Check when there is an actual node */ mtree_store_range(mt, 0, 0, NULL, GFP_KERNEL); mtree_store_range(mt, 0x1000, 0x1500, ptr, GFP_KERNEL); mtree_store_range(mt, 0x2000, 0x2500, ptr2, GFP_KERNEL); mtree_store_range(mt, 0x3000, 0x3500, ptr3, GFP_KERNEL);
mas_lock(&mas);
/* next: start ->active */ mas_set(&mas, 0); entry = mas_next(&mas, ULONG_MAX); MT_BUG_ON(mt, entry != ptr); MT_BUG_ON(mt, mas.index != 0x1000); MT_BUG_ON(mt, mas.last != 0x1500); MT_BUG_ON(mt, !mas_is_active(&mas));
/* next: pause ->active */ mas_set(&mas, 0); mas_pause(&mas); entry = mas_next(&mas, ULONG_MAX); MT_BUG_ON(mt, entry != ptr); MT_BUG_ON(mt, mas.index != 0x1000); MT_BUG_ON(mt, mas.last != 0x1500); MT_BUG_ON(mt, !mas_is_active(&mas));
/* next: none ->active */ mas.index = mas.last = 0; mas.offset = 0; mas.status = ma_none; entry = mas_next(&mas, ULONG_MAX); MT_BUG_ON(mt, entry != ptr); MT_BUG_ON(mt, mas.index != 0x1000); MT_BUG_ON(mt, mas.last != 0x1500); MT_BUG_ON(mt, !mas_is_active(&mas));
/* next:active ->active (spanning limit) */ entry = mas_next(&mas, 0x2100); MT_BUG_ON(mt, entry != ptr2); MT_BUG_ON(mt, mas.index != 0x2000); MT_BUG_ON(mt, mas.last != 0x2500); MT_BUG_ON(mt, !mas_is_active(&mas));
/* next:active -> overflow (limit reached) beyond data */ entry = mas_next(&mas, 0x2999); MT_BUG_ON(mt, entry != NULL); MT_BUG_ON(mt, mas.index != 0x2501); MT_BUG_ON(mt, mas.last != 0x2fff); MT_BUG_ON(mt, !mas_is_overflow(&mas));
/* next:overflow -> active (limit changed) */ entry = mas_next(&mas, ULONG_MAX); MT_BUG_ON(mt, entry != ptr3); MT_BUG_ON(mt, mas.index != 0x3000); MT_BUG_ON(mt, mas.last != 0x3500); MT_BUG_ON(mt, !mas_is_active(&mas));
/* next:active -> overflow (limit reached) */ entry = mas_next(&mas, ULONG_MAX); MT_BUG_ON(mt, entry != NULL); MT_BUG_ON(mt, mas.index != 0x3501); MT_BUG_ON(mt, mas.last != ULONG_MAX); MT_BUG_ON(mt, !mas_is_overflow(&mas));
/* next:overflow -> overflow */ entry = mas_next(&mas, ULONG_MAX); MT_BUG_ON(mt, entry != NULL); MT_BUG_ON(mt, mas.index != 0x3501); MT_BUG_ON(mt, mas.last != ULONG_MAX); MT_BUG_ON(mt, !mas_is_overflow(&mas));
/* prev:overflow -> active */ entry = mas_prev(&mas, 0); MT_BUG_ON(mt, entry != ptr3); MT_BUG_ON(mt, mas.index != 0x3000); MT_BUG_ON(mt, mas.last != 0x3500); MT_BUG_ON(mt, !mas_is_active(&mas));
/* next: none -> active, skip value at location */ mas_set(&mas, 0); entry = mas_next(&mas, ULONG_MAX); mas.status = ma_none; mas.offset = 0; entry = mas_next(&mas, ULONG_MAX); MT_BUG_ON(mt, entry != ptr2); MT_BUG_ON(mt, mas.index != 0x2000); MT_BUG_ON(mt, mas.last != 0x2500); MT_BUG_ON(mt, !mas_is_active(&mas));
/* prev:active ->active */ entry = mas_prev(&mas, 0); MT_BUG_ON(mt, entry != ptr); MT_BUG_ON(mt, mas.index != 0x1000); MT_BUG_ON(mt, mas.last != 0x1500); MT_BUG_ON(mt, !mas_is_active(&mas));
/* prev:active -> underflow (span limit) */ mas_next(&mas, ULONG_MAX); entry = mas_prev(&mas, 0x1200); MT_BUG_ON(mt, entry != ptr); MT_BUG_ON(mt, mas.index != 0x1000); MT_BUG_ON(mt, mas.last != 0x1500); MT_BUG_ON(mt, !mas_is_active(&mas)); /* spanning limit */ entry = mas_prev(&mas, 0x1200); /* underflow */ MT_BUG_ON(mt, entry != NULL); MT_BUG_ON(mt, mas.index != 0x1000); MT_BUG_ON(mt, mas.last != 0x1500); MT_BUG_ON(mt, !mas_is_underflow(&mas));
/* prev:underflow -> underflow (lower limit) spanning end range */ entry = mas_prev(&mas, 0x0100); MT_BUG_ON(mt, entry != NULL); MT_BUG_ON(mt, mas.index != 0); MT_BUG_ON(mt, mas.last != 0x0FFF); MT_BUG_ON(mt, !mas_is_underflow(&mas));
/* prev:underflow -> underflow */ entry = mas_prev(&mas, 0); MT_BUG_ON(mt, entry != NULL); MT_BUG_ON(mt, mas.index != 0); MT_BUG_ON(mt, mas.last != 0x0FFF); MT_BUG_ON(mt, !mas_is_underflow(&mas));
/* prev:underflow -> underflow */ entry = mas_prev(&mas, 0); MT_BUG_ON(mt, entry != NULL); MT_BUG_ON(mt, mas.index != 0); MT_BUG_ON(mt, mas.last != 0x0FFF); MT_BUG_ON(mt, !mas_is_underflow(&mas));
/* next:underflow -> active */ entry = mas_next(&mas, ULONG_MAX); MT_BUG_ON(mt, entry != ptr); MT_BUG_ON(mt, mas.index != 0x1000); MT_BUG_ON(mt, mas.last != 0x1500); MT_BUG_ON(mt, !mas_is_active(&mas));
/* prev:first value -> underflow */ entry = mas_prev(&mas, 0x1000); MT_BUG_ON(mt, entry != NULL); MT_BUG_ON(mt, mas.index != 0x1000); MT_BUG_ON(mt, mas.last != 0x1500); MT_BUG_ON(mt, !mas_is_underflow(&mas));
/* find:underflow -> first value */ entry = mas_find(&mas, ULONG_MAX); MT_BUG_ON(mt, entry != ptr); MT_BUG_ON(mt, mas.index != 0x1000); MT_BUG_ON(mt, mas.last != 0x1500); MT_BUG_ON(mt, !mas_is_active(&mas));
/* prev: pause ->active */ mas_set(&mas, 0x3600); entry = mas_prev(&mas, 0); MT_BUG_ON(mt, entry != ptr3); mas_pause(&mas); entry = mas_prev(&mas, 0); MT_BUG_ON(mt, entry != ptr2); MT_BUG_ON(mt, mas.index != 0x2000); MT_BUG_ON(mt, mas.last != 0x2500); MT_BUG_ON(mt, !mas_is_active(&mas));
/* prev:active -> underflow spanning min */ entry = mas_prev(&mas, 0x1600); MT_BUG_ON(mt, entry != NULL); MT_BUG_ON(mt, mas.index != 0x1501); MT_BUG_ON(mt, mas.last != 0x1FFF); MT_BUG_ON(mt, !mas_is_underflow(&mas));
/* prev: active ->active, continue */ entry = mas_prev(&mas, 0); MT_BUG_ON(mt, entry != ptr); MT_BUG_ON(mt, mas.index != 0x1000); MT_BUG_ON(mt, mas.last != 0x1500); MT_BUG_ON(mt, !mas_is_active(&mas));
/* find: start ->active */ mas_set(&mas, 0); entry = mas_find(&mas, ULONG_MAX); MT_BUG_ON(mt, entry != ptr); MT_BUG_ON(mt, mas.index != 0x1000); MT_BUG_ON(mt, mas.last != 0x1500); MT_BUG_ON(mt, !mas_is_active(&mas));
/* find: pause ->active */ mas_set(&mas, 0); mas_pause(&mas); entry = mas_find(&mas, ULONG_MAX); MT_BUG_ON(mt, entry != ptr); MT_BUG_ON(mt, mas.index != 0x1000); MT_BUG_ON(mt, mas.last != 0x1500); MT_BUG_ON(mt, !mas_is_active(&mas));
/* find: start ->active on value */ mas_set(&mas, 1200); entry = mas_find(&mas, ULONG_MAX); MT_BUG_ON(mt, entry != ptr); MT_BUG_ON(mt, mas.index != 0x1000); MT_BUG_ON(mt, mas.last != 0x1500); MT_BUG_ON(mt, !mas_is_active(&mas));
/* find:active ->active */ entry = mas_find(&mas, ULONG_MAX); MT_BUG_ON(mt, entry != ptr2); MT_BUG_ON(mt, mas.index != 0x2000); MT_BUG_ON(mt, mas.last != 0x2500); MT_BUG_ON(mt, !mas_is_active(&mas));
/* find:active -> active (NULL)*/ entry = mas_find(&mas, 0x2700); MT_BUG_ON(mt, entry != NULL); MT_BUG_ON(mt, mas.index != 0x2501); MT_BUG_ON(mt, mas.last != 0x2FFF); MAS_BUG_ON(&mas, !mas_is_active(&mas));
/* find: overflow ->active */ entry = mas_find(&mas, 0x5000); MT_BUG_ON(mt, entry != ptr3); MT_BUG_ON(mt, mas.index != 0x3000); MT_BUG_ON(mt, mas.last != 0x3500); MT_BUG_ON(mt, !mas_is_active(&mas));
/* find:active -> active (NULL) end*/ entry = mas_find(&mas, ULONG_MAX); MT_BUG_ON(mt, entry != NULL); MT_BUG_ON(mt, mas.index != 0x3501); MT_BUG_ON(mt, mas.last != ULONG_MAX); MAS_BUG_ON(&mas, !mas_is_active(&mas));
/* find_rev: active (END) ->active */ entry = mas_find_rev(&mas, 0); MT_BUG_ON(mt, entry != ptr3); MT_BUG_ON(mt, mas.index != 0x3000); MT_BUG_ON(mt, mas.last != 0x3500); MT_BUG_ON(mt, !mas_is_active(&mas));
/* find_rev:active ->active */ entry = mas_find_rev(&mas, 0); MT_BUG_ON(mt, entry != ptr2); MT_BUG_ON(mt, mas.index != 0x2000); MT_BUG_ON(mt, mas.last != 0x2500); MT_BUG_ON(mt, !mas_is_active(&mas));
/* find_rev: pause ->active */ mas_pause(&mas); entry = mas_find_rev(&mas, 0); MT_BUG_ON(mt, entry != ptr); MT_BUG_ON(mt, mas.index != 0x1000); MT_BUG_ON(mt, mas.last != 0x1500); MT_BUG_ON(mt, !mas_is_active(&mas));
/* find_rev:active -> underflow */ entry = mas_find_rev(&mas, 0); MT_BUG_ON(mt, entry != NULL); MT_BUG_ON(mt, mas.index != 0); MT_BUG_ON(mt, mas.last != 0x0FFF); MT_BUG_ON(mt, !mas_is_underflow(&mas));
/* find_rev: start ->active */ mas_set(&mas, 0x1200); entry = mas_find_rev(&mas, 0); MT_BUG_ON(mt, entry != ptr); MT_BUG_ON(mt, mas.index != 0x1000); MT_BUG_ON(mt, mas.last != 0x1500); MT_BUG_ON(mt, !mas_is_active(&mas));
/* mas_walk start ->active */ mas_set(&mas, 0x1200); entry = mas_walk(&mas); MT_BUG_ON(mt, entry != ptr); MT_BUG_ON(mt, mas.index != 0x1000); MT_BUG_ON(mt, mas.last != 0x1500); MT_BUG_ON(mt, !mas_is_active(&mas));
/* mas_walk start ->active */ mas_set(&mas, 0x1600); entry = mas_walk(&mas); MT_BUG_ON(mt, entry != NULL); MT_BUG_ON(mt, mas.index != 0x1501); MT_BUG_ON(mt, mas.last != 0x1fff); MT_BUG_ON(mt, !mas_is_active(&mas));
/* mas_walk pause ->active */ mas_set(&mas, 0x1200); mas_pause(&mas); entry = mas_walk(&mas); MT_BUG_ON(mt, entry != ptr); MT_BUG_ON(mt, mas.index != 0x1000); MT_BUG_ON(mt, mas.last != 0x1500); MT_BUG_ON(mt, !mas_is_active(&mas));
/* mas_walk pause -> active */ mas_set(&mas, 0x1600); mas_pause(&mas); entry = mas_walk(&mas); MT_BUG_ON(mt, entry != NULL); MT_BUG_ON(mt, mas.index != 0x1501); MT_BUG_ON(mt, mas.last != 0x1fff); MT_BUG_ON(mt, !mas_is_active(&mas));
/* mas_walk none -> active */ mas_set(&mas, 0x1200); mas.status = ma_none; entry = mas_walk(&mas); MT_BUG_ON(mt, entry != ptr); MT_BUG_ON(mt, mas.index != 0x1000); MT_BUG_ON(mt, mas.last != 0x1500); MT_BUG_ON(mt, !mas_is_active(&mas));
/* mas_walk none -> active */ mas_set(&mas, 0x1600); mas.status = ma_none; entry = mas_walk(&mas); MT_BUG_ON(mt, entry != NULL); MT_BUG_ON(mt, mas.index != 0x1501); MT_BUG_ON(mt, mas.last != 0x1fff); MT_BUG_ON(mt, !mas_is_active(&mas));
/* mas_walk active -> active */ mas.index = 0x1200; mas.last = 0x1200; mas.offset = 0; entry = mas_walk(&mas); MT_BUG_ON(mt, entry != ptr); MT_BUG_ON(mt, mas.index != 0x1000); MT_BUG_ON(mt, mas.last != 0x1500); MT_BUG_ON(mt, !mas_is_active(&mas));
/* mas_walk active -> active */ mas.index = 0x1600; mas.last = 0x1600; entry = mas_walk(&mas); MT_BUG_ON(mt, entry != NULL); MT_BUG_ON(mt, mas.index != 0x1501); MT_BUG_ON(mt, mas.last != 0x1fff); MT_BUG_ON(mt, !mas_is_active(&mas));
mas_unlock(&mas); mtree_destroy(mt);
mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); mas_lock(&mas); for (int count = 0; count < 30; count++) { mas_set(&mas, count); mas_store_gfp(&mas, xa_mk_value(count), GFP_KERNEL); }
/* Ensure mas_find works with MA_UNDERFLOW */ mas_set(&mas, 0); entry = mas_walk(&mas); mas_set(&mas, 0); mas_prev(&mas, 0); MT_BUG_ON(mt, mas.status != ma_underflow); MT_BUG_ON(mt, mas_find(&mas, ULONG_MAX) != entry);
/* Restore active on mas_next */ entry = mas_next(&mas, ULONG_MAX); index = mas.index; mas_prev(&mas, index); MT_BUG_ON(mt, mas.status != ma_underflow); MT_BUG_ON(mt, mas_next(&mas, ULONG_MAX) != entry);
/* Ensure overflow -> active works */ mas_prev(&mas, 0); mas_next(&mas, index - 1); MT_BUG_ON(mt, mas.status != ma_overflow); MT_BUG_ON(mt, mas_next(&mas, ULONG_MAX) != entry);
mas_unlock(&mas);}
static noinline void __init alloc_cyclic_testing(struct maple_tree *mt){ unsigned long location; unsigned long next; int ret = 0; MA_STATE(mas, mt, 0, 0);
next = 0; mtree_lock(mt); for (int i = 0; i < 100; i++) { mas_alloc_cyclic(&mas, &location, mt, 2, ULONG_MAX, &next, GFP_KERNEL); MAS_BUG_ON(&mas, i != location - 2); MAS_BUG_ON(&mas, mas.index != location); MAS_BUG_ON(&mas, mas.last != location); MAS_BUG_ON(&mas, i != next - 3); }
mtree_unlock(mt); mtree_destroy(mt); next = 0; mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); for (int i = 0; i < 100; i++) { mtree_alloc_cyclic(mt, &location, mt, 2, ULONG_MAX, &next, GFP_KERNEL); MT_BUG_ON(mt, i != location - 2); MT_BUG_ON(mt, i != next - 3); MT_BUG_ON(mt, mtree_load(mt, location) != mt); }
mtree_destroy(mt);
/* * Issue with reverse search was discovered * https://lore.kernel.org/all/20241216060600.287B4C4CED0@smtp.kernel.org/ * Exhausting the allocation area and forcing the search to wrap needs a * mas_reset() in mas_alloc_cyclic(). */ next = 0; mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); for (int i = 0; i < 1023; i++) { mtree_alloc_cyclic(mt, &location, mt, 2, 1024, &next, GFP_KERNEL); MT_BUG_ON(mt, i != location - 2); MT_BUG_ON(mt, i != next - 3); MT_BUG_ON(mt, mtree_load(mt, location) != mt); } mtree_erase(mt, 123); MT_BUG_ON(mt, mtree_load(mt, 123) != NULL); mtree_alloc_cyclic(mt, &location, mt, 2, 1024, &next, GFP_KERNEL); MT_BUG_ON(mt, 123 != location); MT_BUG_ON(mt, 124 != next); MT_BUG_ON(mt, mtree_load(mt, location) != mt); mtree_erase(mt, 100); mtree_alloc_cyclic(mt, &location, mt, 2, 1024, &next, GFP_KERNEL); MT_BUG_ON(mt, 100 != location); MT_BUG_ON(mt, 101 != next); MT_BUG_ON(mt, mtree_load(mt, location) != mt); mtree_destroy(mt);
/* Overflow test */ next = ULONG_MAX - 1; ret = mtree_alloc_cyclic(mt, &location, mt, 2, ULONG_MAX, &next, GFP_KERNEL); MT_BUG_ON(mt, ret != 0); ret = mtree_alloc_cyclic(mt, &location, mt, 2, ULONG_MAX, &next, GFP_KERNEL); MT_BUG_ON(mt, ret != 0); ret = mtree_alloc_cyclic(mt, &location, mt, 2, ULONG_MAX, &next, GFP_KERNEL); MT_BUG_ON(mt, ret != 1);}
static noinline void __init check_range64_in_rcu(struct maple_tree *mt){ unsigned long i; unsigned long nr_entries = 226; /* Build a full maple_range_64 root node */
MT_BUG_ON(mt, !mtree_empty(mt)); mt_init_flags(mt, MT_FLAGS_USE_RCU);
for (i = 0; i < nr_entries; i++) { MT_BUG_ON(mt, mtree_test_insert_range(mt, i*10, i*10 + 9, xa_mk_value(i))); }
mtree_destroy(mt); rcu_barrier();
nr_entries = 3166; /* Height 3. Root has 15 children + metadata */
MT_BUG_ON(mt, !mtree_empty(mt)); mt_init_flags(mt, MT_FLAGS_USE_RCU);
for (i = 0; i < nr_entries; i++) { MT_BUG_ON(mt, mtree_test_insert_range(mt, i*10, i*10 + 9, xa_mk_value(i))); }
mtree_destroy(mt); rcu_barrier();}
static DEFINE_MTREE(tree);static int __init maple_tree_seed(void){ unsigned long set[] = { 5015, 5014, 5017, 25, 1000, 1001, 1002, 1003, 1005, 0, 5003, 5002}; void *ptr = &set;
pr_info("\nTEST STARTING\n\n");
#if defined(BENCH_SLOT_STORE)#define BENCH mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); bench_slot_store(&tree); mtree_destroy(&tree); goto skip;#endif#if defined(BENCH_NODE_STORE)#define BENCH mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); bench_node_store(&tree); mtree_destroy(&tree); goto skip;#endif#if defined(BENCH_AWALK)#define BENCH mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); bench_awalk(&tree); mtree_destroy(&tree); goto skip;#endif#if defined(BENCH_WALK)#define BENCH mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); bench_walk(&tree); mtree_destroy(&tree); goto skip;#endif#if defined(BENCH_LOAD)#define BENCH mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); bench_load(&tree); mtree_destroy(&tree); goto skip;#endif#if defined(BENCH_FORK)#define BENCH bench_forking(); goto skip;#endif#if defined(BENCH_MT_FOR_EACH)#define BENCH mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); bench_mt_for_each(&tree); mtree_destroy(&tree); goto skip;#endif#if defined(BENCH_MAS_FOR_EACH)#define BENCH mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); bench_mas_for_each(&tree); mtree_destroy(&tree); goto skip;#endif#if defined(BENCH_MAS_PREV)#define BENCH mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); bench_mas_prev(&tree); mtree_destroy(&tree); goto skip;#endif
mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); check_deficient_node(&tree); mtree_destroy(&tree);
mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); check_store_null(&tree); mtree_destroy(&tree);
mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); check_root_expand(&tree); mtree_destroy(&tree);
mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); check_iteration(&tree); mtree_destroy(&tree);
check_forking();
mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); check_mas_store_gfp(&tree); mtree_destroy(&tree);
/* Test ranges (store and insert) */ mt_init_flags(&tree, 0); check_ranges(&tree); mtree_destroy(&tree);
#if defined(CONFIG_64BIT) /* These tests have ranges outside of 4GB */ mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); check_alloc_range(&tree); mtree_destroy(&tree);
mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); check_alloc_rev_range(&tree); mtree_destroy(&tree);#endif
mt_init_flags(&tree, 0);
check_load(&tree, set[0], NULL); /* See if 5015 -> NULL */
check_insert(&tree, set[9], &tree); /* Insert 0 */ check_load(&tree, set[9], &tree); /* See if 0 -> &tree */ check_load(&tree, set[0], NULL); /* See if 5015 -> NULL */
check_insert(&tree, set[10], ptr); /* Insert 5003 */ check_load(&tree, set[9], &tree); /* See if 0 -> &tree */ check_load(&tree, set[11], NULL); /* See if 5002 -> NULL */ check_load(&tree, set[10], ptr); /* See if 5003 -> ptr */
/* Clear out the tree */ mtree_destroy(&tree);
/* Try to insert, insert a dup, and load back what was inserted. */ mt_init_flags(&tree, 0); check_insert(&tree, set[0], &tree); /* Insert 5015 */ check_dup_insert(&tree, set[0], &tree); /* Insert 5015 again */ check_load(&tree, set[0], &tree); /* See if 5015 -> &tree */
/* * Second set of tests try to load a value that doesn't exist, inserts * a second value, then loads the value again */ check_load(&tree, set[1], NULL); /* See if 5014 -> NULL */ check_insert(&tree, set[1], ptr); /* insert 5014 -> ptr */ check_load(&tree, set[1], ptr); /* See if 5014 -> ptr */ check_load(&tree, set[0], &tree); /* See if 5015 -> &tree */ /* * Tree currently contains: * p[0]: 14 -> (nil) p[1]: 15 -> ptr p[2]: 16 -> &tree p[3]: 0 -> (nil) */ check_insert(&tree, set[6], ptr); /* insert 1002 -> ptr */ check_insert(&tree, set[7], &tree); /* insert 1003 -> &tree */
check_load(&tree, set[0], &tree); /* See if 5015 -> &tree */ check_load(&tree, set[1], ptr); /* See if 5014 -> ptr */ check_load(&tree, set[6], ptr); /* See if 1002 -> ptr */ check_load(&tree, set[7], &tree); /* 1003 = &tree ? */
/* Clear out tree */ mtree_destroy(&tree);
mt_init_flags(&tree, 0); /* Test inserting into a NULL hole. */ check_insert(&tree, set[5], ptr); /* insert 1001 -> ptr */ check_insert(&tree, set[7], &tree); /* insert 1003 -> &tree */ check_insert(&tree, set[6], ptr); /* insert 1002 -> ptr */ check_load(&tree, set[5], ptr); /* See if 1001 -> ptr */ check_load(&tree, set[6], ptr); /* See if 1002 -> ptr */ check_load(&tree, set[7], &tree); /* See if 1003 -> &tree */
/* Clear out the tree */ mtree_destroy(&tree);
mt_init_flags(&tree, 0); /* * set[] = {5015, 5014, 5017, 25, 1000, * 1001, 1002, 1003, 1005, 0, * 5003, 5002}; */
check_insert(&tree, set[0], ptr); /* 5015 */ check_insert(&tree, set[1], &tree); /* 5014 */ check_insert(&tree, set[2], ptr); /* 5017 */ check_insert(&tree, set[3], &tree); /* 25 */ check_load(&tree, set[0], ptr); check_load(&tree, set[1], &tree); check_load(&tree, set[2], ptr); check_load(&tree, set[3], &tree); check_insert(&tree, set[4], ptr); /* 1000 < Should split. */ check_load(&tree, set[0], ptr); check_load(&tree, set[1], &tree); check_load(&tree, set[2], ptr); check_load(&tree, set[3], &tree); /*25 */ check_load(&tree, set[4], ptr); check_insert(&tree, set[5], &tree); /* 1001 */ check_load(&tree, set[0], ptr); check_load(&tree, set[1], &tree); check_load(&tree, set[2], ptr); check_load(&tree, set[3], &tree); check_load(&tree, set[4], ptr); check_load(&tree, set[5], &tree); check_insert(&tree, set[6], ptr); check_load(&tree, set[0], ptr); check_load(&tree, set[1], &tree); check_load(&tree, set[2], ptr); check_load(&tree, set[3], &tree); check_load(&tree, set[4], ptr); check_load(&tree, set[5], &tree); check_load(&tree, set[6], ptr); check_insert(&tree, set[7], &tree); check_load(&tree, set[0], ptr); check_insert(&tree, set[8], ptr);
check_insert(&tree, set[9], &tree);
check_load(&tree, set[0], ptr); check_load(&tree, set[1], &tree); check_load(&tree, set[2], ptr); check_load(&tree, set[3], &tree); check_load(&tree, set[4], ptr); check_load(&tree, set[5], &tree); check_load(&tree, set[6], ptr); check_load(&tree, set[9], &tree); mtree_destroy(&tree);
mt_init_flags(&tree, 0); check_seq(&tree, 16, false); mtree_destroy(&tree);
mt_init_flags(&tree, 0); check_seq(&tree, 1000, true); mtree_destroy(&tree);
mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); check_rev_seq(&tree, 1000, true); mtree_destroy(&tree);
check_lower_bound_split(&tree); check_upper_bound_split(&tree); check_mid_split(&tree);
mt_init_flags(&tree, 0); check_next_entry(&tree); check_find(&tree); check_find_2(&tree); mtree_destroy(&tree);
mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); check_prev_entry(&tree); mtree_destroy(&tree);
mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); check_gap_combining(&tree); mtree_destroy(&tree);
mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); check_node_overwrite(&tree); mtree_destroy(&tree);
mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); next_prev_test(&tree); mtree_destroy(&tree);
mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); check_spanning_relatives(&tree); mtree_destroy(&tree);
mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); check_rev_find(&tree); mtree_destroy(&tree);
mt_init_flags(&tree, 0); check_fuzzer(&tree); mtree_destroy(&tree);
mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); check_bnode_min_spanning(&tree); mtree_destroy(&tree);
mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); check_empty_area_window(&tree); mtree_destroy(&tree);
mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); check_empty_area_fill(&tree); mtree_destroy(&tree);
mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); check_state_handling(&tree); mtree_destroy(&tree);
mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); alloc_cyclic_testing(&tree); mtree_destroy(&tree);
check_range64_in_rcu(&tree);
#if defined(BENCH)skip:#endif rcu_barrier(); pr_info("maple_tree: %u of %u tests passed\n", atomic_read(&maple_tree_tests_passed), atomic_read(&maple_tree_tests_run)); if (atomic_read(&maple_tree_tests_run) == atomic_read(&maple_tree_tests_passed)) return 0;
return -EINVAL;}
static void __exit maple_tree_harvest(void){
}
module_init(maple_tree_seed);module_exit(maple_tree_harvest);MODULE_AUTHOR("Liam R. Howlett <liam@infradead.org>");MODULE_DESCRIPTION("maple tree API test module");MODULE_LICENSE("GPL");