vmalloc.c 91 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845184618471848184918501851185218531854185518561857185818591860186118621863186418651866186718681869187018711872187318741875187618771878187918801881188218831884188518861887188818891890189118921893189418951896189718981899190019011902190319041905190619071908190919101911191219131914191519161917191819191920192119221923192419251926192719281929193019311932193319341935193619371938193919401941194219431944194519461947194819491950195119521953195419551956195719581959196019611962196319641965196619671968196919701971197219731974197519761977197819791980198119821983198419851986198719881989199019911992199319941995199619971998199920002001200220032004200520062007200820092010201120122013201420152016201720182019202020212022202320242025202620272028202920302031203220332034203520362037203820392040204120422043204420452046204720482049205020512052205320542055205620572058205920602061206220632064206520662067206820692070207120722073207420752076207720782079208020812082208320842085208620872088208920902091209220932094209520962097209820992100210121022103210421052106210721082109211021112112211321142115211621172118211921202121212221232124212521262127212821292130213121322133213421352136213721382139214021412142214321442145214621472148214921502151215221532154215521562157215821592160216121622163216421652166216721682169217021712172217321742175217621772178217921802181218221832184218521862187218821892190219121922193219421952196219721982199220022012202220322042205220622072208220922102211221222132214221522162217221822192220222122222223222422252226222722282229223022312232223322342235223622372238223922402241224222432244224522462247224822492250225122522253225422552256225722582259226022612262226322642265226622672268226922702271227222732274227522762277227822792280228122822283228422852286228722882289229022912292229322942295229622972298229923002301230223032304230523062307230823092310231123122313231423152316231723182319232023212322232323242325232623272328232923302331233223332334233523362337233823392340234123422343234423452346234723482349235023512352235323542355235623572358235923602361236223632364236523662367236823692370237123722373237423752376237723782379238023812382238323842385238623872388238923902391239223932394239523962397239823992400240124022403240424052406240724082409241024112412241324142415241624172418241924202421242224232424242524262427242824292430243124322433243424352436243724382439244024412442244324442445244624472448244924502451245224532454245524562457245824592460246124622463246424652466246724682469247024712472247324742475247624772478247924802481248224832484248524862487248824892490249124922493249424952496249724982499250025012502250325042505250625072508250925102511251225132514251525162517251825192520252125222523252425252526252725282529253025312532253325342535253625372538253925402541254225432544254525462547254825492550255125522553255425552556255725582559256025612562256325642565256625672568256925702571257225732574257525762577257825792580258125822583258425852586258725882589259025912592259325942595259625972598259926002601260226032604260526062607260826092610261126122613261426152616261726182619262026212622262326242625262626272628262926302631263226332634263526362637263826392640264126422643264426452646264726482649265026512652265326542655265626572658265926602661266226632664266526662667266826692670267126722673267426752676267726782679268026812682268326842685268626872688268926902691269226932694269526962697269826992700270127022703270427052706270727082709271027112712271327142715271627172718271927202721272227232724272527262727272827292730273127322733273427352736273727382739274027412742274327442745274627472748274927502751275227532754275527562757275827592760276127622763276427652766276727682769277027712772277327742775277627772778277927802781278227832784278527862787278827892790279127922793279427952796279727982799280028012802280328042805280628072808280928102811281228132814281528162817281828192820282128222823282428252826282728282829283028312832283328342835283628372838283928402841284228432844284528462847284828492850285128522853285428552856285728582859286028612862286328642865286628672868286928702871287228732874287528762877287828792880288128822883288428852886288728882889289028912892289328942895289628972898289929002901290229032904290529062907290829092910291129122913291429152916291729182919292029212922292329242925292629272928292929302931293229332934293529362937293829392940294129422943294429452946294729482949295029512952295329542955295629572958295929602961296229632964296529662967296829692970297129722973297429752976297729782979298029812982298329842985298629872988298929902991299229932994299529962997299829993000300130023003300430053006300730083009301030113012301330143015301630173018301930203021302230233024302530263027302830293030303130323033303430353036303730383039304030413042304330443045304630473048304930503051305230533054305530563057305830593060306130623063306430653066306730683069307030713072307330743075307630773078307930803081308230833084308530863087308830893090309130923093309430953096309730983099310031013102310331043105310631073108310931103111311231133114311531163117311831193120312131223123312431253126312731283129313031313132313331343135313631373138313931403141314231433144314531463147314831493150315131523153315431553156315731583159316031613162316331643165316631673168316931703171317231733174317531763177317831793180318131823183318431853186318731883189319031913192319331943195319631973198319932003201320232033204320532063207320832093210321132123213321432153216321732183219322032213222322332243225322632273228322932303231323232333234323532363237323832393240324132423243324432453246324732483249325032513252325332543255325632573258325932603261326232633264326532663267326832693270327132723273327432753276327732783279328032813282328332843285328632873288328932903291329232933294329532963297329832993300330133023303330433053306330733083309331033113312331333143315331633173318331933203321332233233324332533263327332833293330333133323333333433353336333733383339334033413342334333443345334633473348334933503351335233533354335533563357335833593360336133623363336433653366336733683369337033713372337333743375337633773378337933803381338233833384338533863387338833893390339133923393339433953396339733983399340034013402340334043405340634073408340934103411341234133414341534163417341834193420342134223423342434253426342734283429343034313432343334343435343634373438343934403441344234433444344534463447344834493450345134523453345434553456345734583459346034613462346334643465346634673468346934703471347234733474347534763477347834793480348134823483348434853486348734883489349034913492349334943495349634973498349935003501350235033504350535063507350835093510351135123513351435153516351735183519352035213522352335243525352635273528352935303531353235333534353535363537353835393540354135423543354435453546354735483549355035513552355335543555355635573558355935603561356235633564356535663567356835693570357135723573357435753576357735783579358035813582358335843585358635873588358935903591
  1. // SPDX-License-Identifier: GPL-2.0-only
  2. /*
  3. * Copyright (C) 1993 Linus Torvalds
  4. * Support of BIGMEM added by Gerhard Wichert, Siemens AG, July 1999
  5. * SMP-safe vmalloc/vfree/ioremap, Tigran Aivazian <tigran@veritas.com>, May 2000
  6. * Major rework to support vmap/vunmap, Christoph Hellwig, SGI, August 2002
  7. * Numa awareness, Christoph Lameter, SGI, June 2005
  8. * Improving global KVA allocator, Uladzislau Rezki, Sony, May 2019
  9. */
  10. #include <linux/vmalloc.h>
  11. #include <linux/mm.h>
  12. #include <linux/module.h>
  13. #include <linux/highmem.h>
  14. #include <linux/sched/signal.h>
  15. #include <linux/slab.h>
  16. #include <linux/spinlock.h>
  17. #include <linux/interrupt.h>
  18. #include <linux/proc_fs.h>
  19. #include <linux/seq_file.h>
  20. #include <linux/set_memory.h>
  21. #include <linux/debugobjects.h>
  22. #include <linux/kallsyms.h>
  23. #include <linux/list.h>
  24. #include <linux/notifier.h>
  25. #include <linux/rbtree.h>
  26. #include <linux/xarray.h>
  27. #include <linux/rcupdate.h>
  28. #include <linux/pfn.h>
  29. #include <linux/kmemleak.h>
  30. #include <linux/atomic.h>
  31. #include <linux/compiler.h>
  32. #include <linux/llist.h>
  33. #include <linux/bitops.h>
  34. #include <linux/rbtree_augmented.h>
  35. #include <linux/overflow.h>
  36. #include <trace/hooks/mm.h>
  37. #include <linux/uaccess.h>
  38. #include <asm/tlbflush.h>
  39. #include <asm/shmparam.h>
  40. #include "internal.h"
  41. #include "pgalloc-track.h"
  42. bool is_vmalloc_addr(const void *x)
  43. {
  44. unsigned long addr = (unsigned long)x;
  45. return addr >= VMALLOC_START && addr < VMALLOC_END;
  46. }
  47. EXPORT_SYMBOL(is_vmalloc_addr);
  48. struct vfree_deferred {
  49. struct llist_head list;
  50. struct work_struct wq;
  51. };
  52. static DEFINE_PER_CPU(struct vfree_deferred, vfree_deferred);
  53. static void __vunmap(const void *, int);
  54. static void free_work(struct work_struct *w)
  55. {
  56. struct vfree_deferred *p = container_of(w, struct vfree_deferred, wq);
  57. struct llist_node *t, *llnode;
  58. llist_for_each_safe(llnode, t, llist_del_all(&p->list))
  59. __vunmap((void *)llnode, 1);
  60. }
  61. /*** Page table manipulation functions ***/
  62. static void vunmap_pte_range(pmd_t *pmd, unsigned long addr, unsigned long end,
  63. pgtbl_mod_mask *mask)
  64. {
  65. pte_t *pte;
  66. pte = pte_offset_kernel(pmd, addr);
  67. do {
  68. pte_t ptent = ptep_get_and_clear(&init_mm, addr, pte);
  69. WARN_ON(!pte_none(ptent) && !pte_present(ptent));
  70. } while (pte++, addr += PAGE_SIZE, addr != end);
  71. *mask |= PGTBL_PTE_MODIFIED;
  72. }
  73. static void vunmap_pmd_range(pud_t *pud, unsigned long addr, unsigned long end,
  74. pgtbl_mod_mask *mask)
  75. {
  76. pmd_t *pmd;
  77. unsigned long next;
  78. int cleared;
  79. pmd = pmd_offset(pud, addr);
  80. do {
  81. next = pmd_addr_end(addr, end);
  82. cleared = pmd_clear_huge(pmd);
  83. if (cleared || pmd_bad(*pmd))
  84. *mask |= PGTBL_PMD_MODIFIED;
  85. if (cleared)
  86. continue;
  87. if (pmd_none_or_clear_bad(pmd))
  88. continue;
  89. vunmap_pte_range(pmd, addr, next, mask);
  90. cond_resched();
  91. } while (pmd++, addr = next, addr != end);
  92. }
  93. static void vunmap_pud_range(p4d_t *p4d, unsigned long addr, unsigned long end,
  94. pgtbl_mod_mask *mask)
  95. {
  96. pud_t *pud;
  97. unsigned long next;
  98. int cleared;
  99. pud = pud_offset(p4d, addr);
  100. do {
  101. next = pud_addr_end(addr, end);
  102. cleared = pud_clear_huge(pud);
  103. if (cleared || pud_bad(*pud))
  104. *mask |= PGTBL_PUD_MODIFIED;
  105. if (cleared)
  106. continue;
  107. if (pud_none_or_clear_bad(pud))
  108. continue;
  109. vunmap_pmd_range(pud, addr, next, mask);
  110. } while (pud++, addr = next, addr != end);
  111. }
  112. static void vunmap_p4d_range(pgd_t *pgd, unsigned long addr, unsigned long end,
  113. pgtbl_mod_mask *mask)
  114. {
  115. p4d_t *p4d;
  116. unsigned long next;
  117. int cleared;
  118. p4d = p4d_offset(pgd, addr);
  119. do {
  120. next = p4d_addr_end(addr, end);
  121. cleared = p4d_clear_huge(p4d);
  122. if (cleared || p4d_bad(*p4d))
  123. *mask |= PGTBL_P4D_MODIFIED;
  124. if (cleared)
  125. continue;
  126. if (p4d_none_or_clear_bad(p4d))
  127. continue;
  128. vunmap_pud_range(p4d, addr, next, mask);
  129. } while (p4d++, addr = next, addr != end);
  130. }
  131. /**
  132. * unmap_kernel_range_noflush - unmap kernel VM area
  133. * @start: start of the VM area to unmap
  134. * @size: size of the VM area to unmap
  135. *
  136. * Unmap PFN_UP(@size) pages at @addr. The VM area @addr and @size specify
  137. * should have been allocated using get_vm_area() and its friends.
  138. *
  139. * NOTE:
  140. * This function does NOT do any cache flushing. The caller is responsible
  141. * for calling flush_cache_vunmap() on to-be-mapped areas before calling this
  142. * function and flush_tlb_kernel_range() after.
  143. */
  144. void unmap_kernel_range_noflush(unsigned long start, unsigned long size)
  145. {
  146. unsigned long end = start + size;
  147. unsigned long next;
  148. pgd_t *pgd;
  149. unsigned long addr = start;
  150. pgtbl_mod_mask mask = 0;
  151. BUG_ON(addr >= end);
  152. pgd = pgd_offset_k(addr);
  153. do {
  154. next = pgd_addr_end(addr, end);
  155. if (pgd_bad(*pgd))
  156. mask |= PGTBL_PGD_MODIFIED;
  157. if (pgd_none_or_clear_bad(pgd))
  158. continue;
  159. vunmap_p4d_range(pgd, addr, next, &mask);
  160. } while (pgd++, addr = next, addr != end);
  161. if (mask & ARCH_PAGE_TABLE_SYNC_MASK)
  162. arch_sync_kernel_mappings(start, end);
  163. }
  164. static int vmap_pte_range(pmd_t *pmd, unsigned long addr,
  165. unsigned long end, pgprot_t prot, struct page **pages, int *nr,
  166. pgtbl_mod_mask *mask)
  167. {
  168. pte_t *pte;
  169. /*
  170. * nr is a running index into the array which helps higher level
  171. * callers keep track of where we're up to.
  172. */
  173. pte = pte_alloc_kernel_track(pmd, addr, mask);
  174. if (!pte)
  175. return -ENOMEM;
  176. do {
  177. struct page *page = pages[*nr];
  178. if (WARN_ON(!pte_none(*pte)))
  179. return -EBUSY;
  180. if (WARN_ON(!page))
  181. return -ENOMEM;
  182. set_pte_at(&init_mm, addr, pte, mk_pte(page, prot));
  183. (*nr)++;
  184. } while (pte++, addr += PAGE_SIZE, addr != end);
  185. *mask |= PGTBL_PTE_MODIFIED;
  186. return 0;
  187. }
  188. static int vmap_pmd_range(pud_t *pud, unsigned long addr,
  189. unsigned long end, pgprot_t prot, struct page **pages, int *nr,
  190. pgtbl_mod_mask *mask)
  191. {
  192. pmd_t *pmd;
  193. unsigned long next;
  194. pmd = pmd_alloc_track(&init_mm, pud, addr, mask);
  195. if (!pmd)
  196. return -ENOMEM;
  197. do {
  198. next = pmd_addr_end(addr, end);
  199. if (vmap_pte_range(pmd, addr, next, prot, pages, nr, mask))
  200. return -ENOMEM;
  201. } while (pmd++, addr = next, addr != end);
  202. return 0;
  203. }
  204. static int vmap_pud_range(p4d_t *p4d, unsigned long addr,
  205. unsigned long end, pgprot_t prot, struct page **pages, int *nr,
  206. pgtbl_mod_mask *mask)
  207. {
  208. pud_t *pud;
  209. unsigned long next;
  210. pud = pud_alloc_track(&init_mm, p4d, addr, mask);
  211. if (!pud)
  212. return -ENOMEM;
  213. do {
  214. next = pud_addr_end(addr, end);
  215. if (vmap_pmd_range(pud, addr, next, prot, pages, nr, mask))
  216. return -ENOMEM;
  217. } while (pud++, addr = next, addr != end);
  218. return 0;
  219. }
  220. static int vmap_p4d_range(pgd_t *pgd, unsigned long addr,
  221. unsigned long end, pgprot_t prot, struct page **pages, int *nr,
  222. pgtbl_mod_mask *mask)
  223. {
  224. p4d_t *p4d;
  225. unsigned long next;
  226. p4d = p4d_alloc_track(&init_mm, pgd, addr, mask);
  227. if (!p4d)
  228. return -ENOMEM;
  229. do {
  230. next = p4d_addr_end(addr, end);
  231. if (vmap_pud_range(p4d, addr, next, prot, pages, nr, mask))
  232. return -ENOMEM;
  233. } while (p4d++, addr = next, addr != end);
  234. return 0;
  235. }
  236. /**
  237. * map_kernel_range_noflush - map kernel VM area with the specified pages
  238. * @addr: start of the VM area to map
  239. * @size: size of the VM area to map
  240. * @prot: page protection flags to use
  241. * @pages: pages to map
  242. *
  243. * Map PFN_UP(@size) pages at @addr. The VM area @addr and @size specify should
  244. * have been allocated using get_vm_area() and its friends.
  245. *
  246. * NOTE:
  247. * This function does NOT do any cache flushing. The caller is responsible for
  248. * calling flush_cache_vmap() on to-be-mapped areas before calling this
  249. * function.
  250. *
  251. * RETURNS:
  252. * 0 on success, -errno on failure.
  253. */
  254. int map_kernel_range_noflush(unsigned long addr, unsigned long size,
  255. pgprot_t prot, struct page **pages)
  256. {
  257. unsigned long start = addr;
  258. unsigned long end = addr + size;
  259. unsigned long next;
  260. pgd_t *pgd;
  261. int err = 0;
  262. int nr = 0;
  263. pgtbl_mod_mask mask = 0;
  264. BUG_ON(addr >= end);
  265. pgd = pgd_offset_k(addr);
  266. do {
  267. next = pgd_addr_end(addr, end);
  268. if (pgd_bad(*pgd))
  269. mask |= PGTBL_PGD_MODIFIED;
  270. err = vmap_p4d_range(pgd, addr, next, prot, pages, &nr, &mask);
  271. if (err)
  272. return err;
  273. } while (pgd++, addr = next, addr != end);
  274. if (mask & ARCH_PAGE_TABLE_SYNC_MASK)
  275. arch_sync_kernel_mappings(start, end);
  276. return 0;
  277. }
  278. int map_kernel_range(unsigned long start, unsigned long size, pgprot_t prot,
  279. struct page **pages)
  280. {
  281. int ret;
  282. ret = map_kernel_range_noflush(start, size, prot, pages);
  283. flush_cache_vmap(start, start + size);
  284. return ret;
  285. }
  286. EXPORT_SYMBOL_GPL(map_kernel_range);
  287. int is_vmalloc_or_module_addr(const void *x)
  288. {
  289. /*
  290. * ARM, x86-64 and sparc64 put modules in a special place,
  291. * and fall back on vmalloc() if that fails. Others
  292. * just put it in the vmalloc space.
  293. */
  294. #if defined(CONFIG_MODULES) && defined(MODULES_VADDR)
  295. unsigned long addr = (unsigned long)x;
  296. if (addr >= MODULES_VADDR && addr < MODULES_END)
  297. return 1;
  298. #endif
  299. return is_vmalloc_addr(x);
  300. }
  301. /*
  302. * Walk a vmap address to the struct page it maps.
  303. */
  304. struct page *vmalloc_to_page(const void *vmalloc_addr)
  305. {
  306. unsigned long addr = (unsigned long) vmalloc_addr;
  307. struct page *page = NULL;
  308. pgd_t *pgd = pgd_offset_k(addr);
  309. p4d_t *p4d;
  310. pud_t *pud;
  311. pmd_t *pmd;
  312. pte_t *ptep, pte;
  313. /*
  314. * XXX we might need to change this if we add VIRTUAL_BUG_ON for
  315. * architectures that do not vmalloc module space
  316. */
  317. VIRTUAL_BUG_ON(!is_vmalloc_or_module_addr(vmalloc_addr));
  318. if (pgd_none(*pgd))
  319. return NULL;
  320. p4d = p4d_offset(pgd, addr);
  321. if (p4d_none(*p4d))
  322. return NULL;
  323. pud = pud_offset(p4d, addr);
  324. /*
  325. * Don't dereference bad PUD or PMD (below) entries. This will also
  326. * identify huge mappings, which we may encounter on architectures
  327. * that define CONFIG_HAVE_ARCH_HUGE_VMAP=y. Such regions will be
  328. * identified as vmalloc addresses by is_vmalloc_addr(), but are
  329. * not [unambiguously] associated with a struct page, so there is
  330. * no correct value to return for them.
  331. */
  332. WARN_ON_ONCE(pud_bad(*pud));
  333. if (pud_none(*pud) || pud_bad(*pud))
  334. return NULL;
  335. pmd = pmd_offset(pud, addr);
  336. WARN_ON_ONCE(pmd_bad(*pmd));
  337. if (pmd_none(*pmd) || pmd_bad(*pmd))
  338. return NULL;
  339. ptep = pte_offset_map(pmd, addr);
  340. pte = *ptep;
  341. if (pte_present(pte))
  342. page = pte_page(pte);
  343. pte_unmap(ptep);
  344. return page;
  345. }
  346. EXPORT_SYMBOL(vmalloc_to_page);
  347. /*
  348. * Map a vmalloc()-space virtual address to the physical page frame number.
  349. */
  350. unsigned long vmalloc_to_pfn(const void *vmalloc_addr)
  351. {
  352. return page_to_pfn(vmalloc_to_page(vmalloc_addr));
  353. }
  354. EXPORT_SYMBOL(vmalloc_to_pfn);
  355. /*** Global kva allocator ***/
  356. #define DEBUG_AUGMENT_PROPAGATE_CHECK 0
  357. #define DEBUG_AUGMENT_LOWEST_MATCH_CHECK 0
  358. static DEFINE_SPINLOCK(vmap_area_lock);
  359. static DEFINE_SPINLOCK(free_vmap_area_lock);
  360. /* Export for kexec only */
  361. LIST_HEAD(vmap_area_list);
  362. static LLIST_HEAD(vmap_purge_list);
  363. static struct rb_root vmap_area_root = RB_ROOT;
  364. static bool vmap_initialized __read_mostly;
  365. /*
  366. * This kmem_cache is used for vmap_area objects. Instead of
  367. * allocating from slab we reuse an object from this cache to
  368. * make things faster. Especially in "no edge" splitting of
  369. * free block.
  370. */
  371. static struct kmem_cache *vmap_area_cachep;
  372. /*
  373. * This linked list is used in pair with free_vmap_area_root.
  374. * It gives O(1) access to prev/next to perform fast coalescing.
  375. */
  376. static LIST_HEAD(free_vmap_area_list);
  377. /*
  378. * This augment red-black tree represents the free vmap space.
  379. * All vmap_area objects in this tree are sorted by va->va_start
  380. * address. It is used for allocation and merging when a vmap
  381. * object is released.
  382. *
  383. * Each vmap_area node contains a maximum available free block
  384. * of its sub-tree, right or left. Therefore it is possible to
  385. * find a lowest match of free area.
  386. */
  387. static struct rb_root free_vmap_area_root = RB_ROOT;
  388. /*
  389. * Preload a CPU with one object for "no edge" split case. The
  390. * aim is to get rid of allocations from the atomic context, thus
  391. * to use more permissive allocation masks.
  392. */
  393. static DEFINE_PER_CPU(struct vmap_area *, ne_fit_preload_node);
  394. static __always_inline unsigned long
  395. va_size(struct vmap_area *va)
  396. {
  397. return (va->va_end - va->va_start);
  398. }
  399. static __always_inline unsigned long
  400. get_subtree_max_size(struct rb_node *node)
  401. {
  402. struct vmap_area *va;
  403. va = rb_entry_safe(node, struct vmap_area, rb_node);
  404. return va ? va->subtree_max_size : 0;
  405. }
  406. /*
  407. * Gets called when remove the node and rotate.
  408. */
  409. static __always_inline unsigned long
  410. compute_subtree_max_size(struct vmap_area *va)
  411. {
  412. return max3(va_size(va),
  413. get_subtree_max_size(va->rb_node.rb_left),
  414. get_subtree_max_size(va->rb_node.rb_right));
  415. }
  416. RB_DECLARE_CALLBACKS_MAX(static, free_vmap_area_rb_augment_cb,
  417. struct vmap_area, rb_node, unsigned long, subtree_max_size, va_size)
  418. static void purge_vmap_area_lazy(void);
  419. static BLOCKING_NOTIFIER_HEAD(vmap_notify_list);
  420. static unsigned long lazy_max_pages(void);
  421. static atomic_long_t nr_vmalloc_pages;
  422. unsigned long vmalloc_nr_pages(void)
  423. {
  424. return atomic_long_read(&nr_vmalloc_pages);
  425. }
  426. EXPORT_SYMBOL_GPL(vmalloc_nr_pages);
  427. static struct vmap_area *__find_vmap_area(unsigned long addr)
  428. {
  429. struct rb_node *n = vmap_area_root.rb_node;
  430. while (n) {
  431. struct vmap_area *va;
  432. va = rb_entry(n, struct vmap_area, rb_node);
  433. if (addr < va->va_start)
  434. n = n->rb_left;
  435. else if (addr >= va->va_end)
  436. n = n->rb_right;
  437. else
  438. return va;
  439. }
  440. return NULL;
  441. }
  442. /*
  443. * This function returns back addresses of parent node
  444. * and its left or right link for further processing.
  445. *
  446. * Otherwise NULL is returned. In that case all further
  447. * steps regarding inserting of conflicting overlap range
  448. * have to be declined and actually considered as a bug.
  449. */
  450. static __always_inline struct rb_node **
  451. find_va_links(struct vmap_area *va,
  452. struct rb_root *root, struct rb_node *from,
  453. struct rb_node **parent)
  454. {
  455. struct vmap_area *tmp_va;
  456. struct rb_node **link;
  457. if (root) {
  458. link = &root->rb_node;
  459. if (unlikely(!*link)) {
  460. *parent = NULL;
  461. return link;
  462. }
  463. } else {
  464. link = &from;
  465. }
  466. /*
  467. * Go to the bottom of the tree. When we hit the last point
  468. * we end up with parent rb_node and correct direction, i name
  469. * it link, where the new va->rb_node will be attached to.
  470. */
  471. do {
  472. tmp_va = rb_entry(*link, struct vmap_area, rb_node);
  473. /*
  474. * During the traversal we also do some sanity check.
  475. * Trigger the BUG() if there are sides(left/right)
  476. * or full overlaps.
  477. */
  478. if (va->va_start < tmp_va->va_end &&
  479. va->va_end <= tmp_va->va_start)
  480. link = &(*link)->rb_left;
  481. else if (va->va_end > tmp_va->va_start &&
  482. va->va_start >= tmp_va->va_end)
  483. link = &(*link)->rb_right;
  484. else {
  485. WARN(1, "vmalloc bug: 0x%lx-0x%lx overlaps with 0x%lx-0x%lx\n",
  486. va->va_start, va->va_end, tmp_va->va_start, tmp_va->va_end);
  487. return NULL;
  488. }
  489. } while (*link);
  490. *parent = &tmp_va->rb_node;
  491. return link;
  492. }
  493. static __always_inline struct list_head *
  494. get_va_next_sibling(struct rb_node *parent, struct rb_node **link)
  495. {
  496. struct list_head *list;
  497. if (unlikely(!parent))
  498. /*
  499. * The red-black tree where we try to find VA neighbors
  500. * before merging or inserting is empty, i.e. it means
  501. * there is no free vmap space. Normally it does not
  502. * happen but we handle this case anyway.
  503. */
  504. return NULL;
  505. list = &rb_entry(parent, struct vmap_area, rb_node)->list;
  506. return (&parent->rb_right == link ? list->next : list);
  507. }
  508. static __always_inline void
  509. link_va(struct vmap_area *va, struct rb_root *root,
  510. struct rb_node *parent, struct rb_node **link, struct list_head *head)
  511. {
  512. /*
  513. * VA is still not in the list, but we can
  514. * identify its future previous list_head node.
  515. */
  516. if (likely(parent)) {
  517. head = &rb_entry(parent, struct vmap_area, rb_node)->list;
  518. if (&parent->rb_right != link)
  519. head = head->prev;
  520. }
  521. /* Insert to the rb-tree */
  522. rb_link_node(&va->rb_node, parent, link);
  523. if (root == &free_vmap_area_root) {
  524. /*
  525. * Some explanation here. Just perform simple insertion
  526. * to the tree. We do not set va->subtree_max_size to
  527. * its current size before calling rb_insert_augmented().
  528. * It is because of we populate the tree from the bottom
  529. * to parent levels when the node _is_ in the tree.
  530. *
  531. * Therefore we set subtree_max_size to zero after insertion,
  532. * to let __augment_tree_propagate_from() puts everything to
  533. * the correct order later on.
  534. */
  535. rb_insert_augmented(&va->rb_node,
  536. root, &free_vmap_area_rb_augment_cb);
  537. va->subtree_max_size = 0;
  538. } else {
  539. rb_insert_color(&va->rb_node, root);
  540. }
  541. /* Address-sort this list */
  542. list_add(&va->list, head);
  543. }
  544. static __always_inline void
  545. unlink_va(struct vmap_area *va, struct rb_root *root)
  546. {
  547. if (WARN_ON(RB_EMPTY_NODE(&va->rb_node)))
  548. return;
  549. if (root == &free_vmap_area_root)
  550. rb_erase_augmented(&va->rb_node,
  551. root, &free_vmap_area_rb_augment_cb);
  552. else
  553. rb_erase(&va->rb_node, root);
  554. list_del(&va->list);
  555. RB_CLEAR_NODE(&va->rb_node);
  556. }
  557. #if DEBUG_AUGMENT_PROPAGATE_CHECK
  558. static void
  559. augment_tree_propagate_check(void)
  560. {
  561. struct vmap_area *va;
  562. unsigned long computed_size;
  563. list_for_each_entry(va, &free_vmap_area_list, list) {
  564. computed_size = compute_subtree_max_size(va);
  565. if (computed_size != va->subtree_max_size)
  566. pr_emerg("tree is corrupted: %lu, %lu\n",
  567. va_size(va), va->subtree_max_size);
  568. }
  569. }
  570. #endif
  571. /*
  572. * This function populates subtree_max_size from bottom to upper
  573. * levels starting from VA point. The propagation must be done
  574. * when VA size is modified by changing its va_start/va_end. Or
  575. * in case of newly inserting of VA to the tree.
  576. *
  577. * It means that __augment_tree_propagate_from() must be called:
  578. * - After VA has been inserted to the tree(free path);
  579. * - After VA has been shrunk(allocation path);
  580. * - After VA has been increased(merging path).
  581. *
  582. * Please note that, it does not mean that upper parent nodes
  583. * and their subtree_max_size are recalculated all the time up
  584. * to the root node.
  585. *
  586. * 4--8
  587. * /\
  588. * / \
  589. * / \
  590. * 2--2 8--8
  591. *
  592. * For example if we modify the node 4, shrinking it to 2, then
  593. * no any modification is required. If we shrink the node 2 to 1
  594. * its subtree_max_size is updated only, and set to 1. If we shrink
  595. * the node 8 to 6, then its subtree_max_size is set to 6 and parent
  596. * node becomes 4--6.
  597. */
  598. static __always_inline void
  599. augment_tree_propagate_from(struct vmap_area *va)
  600. {
  601. /*
  602. * Populate the tree from bottom towards the root until
  603. * the calculated maximum available size of checked node
  604. * is equal to its current one.
  605. */
  606. free_vmap_area_rb_augment_cb_propagate(&va->rb_node, NULL);
  607. #if DEBUG_AUGMENT_PROPAGATE_CHECK
  608. augment_tree_propagate_check();
  609. #endif
  610. }
  611. static void
  612. insert_vmap_area(struct vmap_area *va,
  613. struct rb_root *root, struct list_head *head)
  614. {
  615. struct rb_node **link;
  616. struct rb_node *parent;
  617. link = find_va_links(va, root, NULL, &parent);
  618. if (link)
  619. link_va(va, root, parent, link, head);
  620. }
  621. static void
  622. insert_vmap_area_augment(struct vmap_area *va,
  623. struct rb_node *from, struct rb_root *root,
  624. struct list_head *head)
  625. {
  626. struct rb_node **link;
  627. struct rb_node *parent;
  628. if (from)
  629. link = find_va_links(va, NULL, from, &parent);
  630. else
  631. link = find_va_links(va, root, NULL, &parent);
  632. if (link) {
  633. link_va(va, root, parent, link, head);
  634. augment_tree_propagate_from(va);
  635. }
  636. }
  637. /*
  638. * Merge de-allocated chunk of VA memory with previous
  639. * and next free blocks. If coalesce is not done a new
  640. * free area is inserted. If VA has been merged, it is
  641. * freed.
  642. *
  643. * Please note, it can return NULL in case of overlap
  644. * ranges, followed by WARN() report. Despite it is a
  645. * buggy behaviour, a system can be alive and keep
  646. * ongoing.
  647. */
  648. static __always_inline struct vmap_area *
  649. merge_or_add_vmap_area(struct vmap_area *va,
  650. struct rb_root *root, struct list_head *head)
  651. {
  652. struct vmap_area *sibling;
  653. struct list_head *next;
  654. struct rb_node **link;
  655. struct rb_node *parent;
  656. bool merged = false;
  657. /*
  658. * Find a place in the tree where VA potentially will be
  659. * inserted, unless it is merged with its sibling/siblings.
  660. */
  661. link = find_va_links(va, root, NULL, &parent);
  662. if (!link)
  663. return NULL;
  664. /*
  665. * Get next node of VA to check if merging can be done.
  666. */
  667. next = get_va_next_sibling(parent, link);
  668. if (unlikely(next == NULL))
  669. goto insert;
  670. /*
  671. * start end
  672. * | |
  673. * |<------VA------>|<-----Next----->|
  674. * | |
  675. * start end
  676. */
  677. if (next != head) {
  678. sibling = list_entry(next, struct vmap_area, list);
  679. if (sibling->va_start == va->va_end) {
  680. sibling->va_start = va->va_start;
  681. /* Free vmap_area object. */
  682. kmem_cache_free(vmap_area_cachep, va);
  683. /* Point to the new merged area. */
  684. va = sibling;
  685. merged = true;
  686. }
  687. }
  688. /*
  689. * start end
  690. * | |
  691. * |<-----Prev----->|<------VA------>|
  692. * | |
  693. * start end
  694. */
  695. if (next->prev != head) {
  696. sibling = list_entry(next->prev, struct vmap_area, list);
  697. if (sibling->va_end == va->va_start) {
  698. /*
  699. * If both neighbors are coalesced, it is important
  700. * to unlink the "next" node first, followed by merging
  701. * with "previous" one. Otherwise the tree might not be
  702. * fully populated if a sibling's augmented value is
  703. * "normalized" because of rotation operations.
  704. */
  705. if (merged)
  706. unlink_va(va, root);
  707. sibling->va_end = va->va_end;
  708. /* Free vmap_area object. */
  709. kmem_cache_free(vmap_area_cachep, va);
  710. /* Point to the new merged area. */
  711. va = sibling;
  712. merged = true;
  713. }
  714. }
  715. insert:
  716. if (!merged)
  717. link_va(va, root, parent, link, head);
  718. /*
  719. * Last step is to check and update the tree.
  720. */
  721. augment_tree_propagate_from(va);
  722. return va;
  723. }
  724. static __always_inline bool
  725. is_within_this_va(struct vmap_area *va, unsigned long size,
  726. unsigned long align, unsigned long vstart)
  727. {
  728. unsigned long nva_start_addr;
  729. if (va->va_start > vstart)
  730. nva_start_addr = ALIGN(va->va_start, align);
  731. else
  732. nva_start_addr = ALIGN(vstart, align);
  733. /* Can be overflowed due to big size or alignment. */
  734. if (nva_start_addr + size < nva_start_addr ||
  735. nva_start_addr < vstart)
  736. return false;
  737. return (nva_start_addr + size <= va->va_end);
  738. }
  739. /*
  740. * Find the first free block(lowest start address) in the tree,
  741. * that will accomplish the request corresponding to passing
  742. * parameters.
  743. */
  744. static __always_inline struct vmap_area *
  745. find_vmap_lowest_match(unsigned long size,
  746. unsigned long align, unsigned long vstart)
  747. {
  748. struct vmap_area *va;
  749. struct rb_node *node;
  750. unsigned long length;
  751. /* Start from the root. */
  752. node = free_vmap_area_root.rb_node;
  753. /* Adjust the search size for alignment overhead. */
  754. length = size + align - 1;
  755. while (node) {
  756. va = rb_entry(node, struct vmap_area, rb_node);
  757. if (get_subtree_max_size(node->rb_left) >= length &&
  758. vstart < va->va_start) {
  759. node = node->rb_left;
  760. } else {
  761. if (is_within_this_va(va, size, align, vstart))
  762. return va;
  763. /*
  764. * Does not make sense to go deeper towards the right
  765. * sub-tree if it does not have a free block that is
  766. * equal or bigger to the requested search length.
  767. */
  768. if (get_subtree_max_size(node->rb_right) >= length) {
  769. node = node->rb_right;
  770. continue;
  771. }
  772. /*
  773. * OK. We roll back and find the first right sub-tree,
  774. * that will satisfy the search criteria. It can happen
  775. * only once due to "vstart" restriction.
  776. */
  777. while ((node = rb_parent(node))) {
  778. va = rb_entry(node, struct vmap_area, rb_node);
  779. if (is_within_this_va(va, size, align, vstart))
  780. return va;
  781. if (get_subtree_max_size(node->rb_right) >= length &&
  782. vstart <= va->va_start) {
  783. node = node->rb_right;
  784. break;
  785. }
  786. }
  787. }
  788. }
  789. return NULL;
  790. }
  791. #if DEBUG_AUGMENT_LOWEST_MATCH_CHECK
  792. #include <linux/random.h>
  793. static struct vmap_area *
  794. find_vmap_lowest_linear_match(unsigned long size,
  795. unsigned long align, unsigned long vstart)
  796. {
  797. struct vmap_area *va;
  798. list_for_each_entry(va, &free_vmap_area_list, list) {
  799. if (!is_within_this_va(va, size, align, vstart))
  800. continue;
  801. return va;
  802. }
  803. return NULL;
  804. }
  805. static void
  806. find_vmap_lowest_match_check(unsigned long size)
  807. {
  808. struct vmap_area *va_1, *va_2;
  809. unsigned long vstart;
  810. unsigned int rnd;
  811. get_random_bytes(&rnd, sizeof(rnd));
  812. vstart = VMALLOC_START + rnd;
  813. va_1 = find_vmap_lowest_match(size, 1, vstart);
  814. va_2 = find_vmap_lowest_linear_match(size, 1, vstart);
  815. if (va_1 != va_2)
  816. pr_emerg("not lowest: t: 0x%p, l: 0x%p, v: 0x%lx\n",
  817. va_1, va_2, vstart);
  818. }
  819. #endif
  820. enum fit_type {
  821. NOTHING_FIT = 0,
  822. FL_FIT_TYPE = 1, /* full fit */
  823. LE_FIT_TYPE = 2, /* left edge fit */
  824. RE_FIT_TYPE = 3, /* right edge fit */
  825. NE_FIT_TYPE = 4 /* no edge fit */
  826. };
  827. static __always_inline enum fit_type
  828. classify_va_fit_type(struct vmap_area *va,
  829. unsigned long nva_start_addr, unsigned long size)
  830. {
  831. enum fit_type type;
  832. /* Check if it is within VA. */
  833. if (nva_start_addr < va->va_start ||
  834. nva_start_addr + size > va->va_end)
  835. return NOTHING_FIT;
  836. /* Now classify. */
  837. if (va->va_start == nva_start_addr) {
  838. if (va->va_end == nva_start_addr + size)
  839. type = FL_FIT_TYPE;
  840. else
  841. type = LE_FIT_TYPE;
  842. } else if (va->va_end == nva_start_addr + size) {
  843. type = RE_FIT_TYPE;
  844. } else {
  845. type = NE_FIT_TYPE;
  846. }
  847. return type;
  848. }
  849. static __always_inline int
  850. adjust_va_to_fit_type(struct vmap_area *va,
  851. unsigned long nva_start_addr, unsigned long size,
  852. enum fit_type type)
  853. {
  854. struct vmap_area *lva = NULL;
  855. if (type == FL_FIT_TYPE) {
  856. /*
  857. * No need to split VA, it fully fits.
  858. *
  859. * | |
  860. * V NVA V
  861. * |---------------|
  862. */
  863. unlink_va(va, &free_vmap_area_root);
  864. kmem_cache_free(vmap_area_cachep, va);
  865. } else if (type == LE_FIT_TYPE) {
  866. /*
  867. * Split left edge of fit VA.
  868. *
  869. * | |
  870. * V NVA V R
  871. * |-------|-------|
  872. */
  873. va->va_start += size;
  874. } else if (type == RE_FIT_TYPE) {
  875. /*
  876. * Split right edge of fit VA.
  877. *
  878. * | |
  879. * L V NVA V
  880. * |-------|-------|
  881. */
  882. va->va_end = nva_start_addr;
  883. } else if (type == NE_FIT_TYPE) {
  884. /*
  885. * Split no edge of fit VA.
  886. *
  887. * | |
  888. * L V NVA V R
  889. * |---|-------|---|
  890. */
  891. lva = __this_cpu_xchg(ne_fit_preload_node, NULL);
  892. if (unlikely(!lva)) {
  893. /*
  894. * For percpu allocator we do not do any pre-allocation
  895. * and leave it as it is. The reason is it most likely
  896. * never ends up with NE_FIT_TYPE splitting. In case of
  897. * percpu allocations offsets and sizes are aligned to
  898. * fixed align request, i.e. RE_FIT_TYPE and FL_FIT_TYPE
  899. * are its main fitting cases.
  900. *
  901. * There are a few exceptions though, as an example it is
  902. * a first allocation (early boot up) when we have "one"
  903. * big free space that has to be split.
  904. *
  905. * Also we can hit this path in case of regular "vmap"
  906. * allocations, if "this" current CPU was not preloaded.
  907. * See the comment in alloc_vmap_area() why. If so, then
  908. * GFP_NOWAIT is used instead to get an extra object for
  909. * split purpose. That is rare and most time does not
  910. * occur.
  911. *
  912. * What happens if an allocation gets failed. Basically,
  913. * an "overflow" path is triggered to purge lazily freed
  914. * areas to free some memory, then, the "retry" path is
  915. * triggered to repeat one more time. See more details
  916. * in alloc_vmap_area() function.
  917. */
  918. lva = kmem_cache_alloc(vmap_area_cachep, GFP_NOWAIT);
  919. if (!lva)
  920. return -1;
  921. }
  922. /*
  923. * Build the remainder.
  924. */
  925. lva->va_start = va->va_start;
  926. lva->va_end = nva_start_addr;
  927. /*
  928. * Shrink this VA to remaining size.
  929. */
  930. va->va_start = nva_start_addr + size;
  931. } else {
  932. return -1;
  933. }
  934. if (type != FL_FIT_TYPE) {
  935. augment_tree_propagate_from(va);
  936. if (lva) /* type == NE_FIT_TYPE */
  937. insert_vmap_area_augment(lva, &va->rb_node,
  938. &free_vmap_area_root, &free_vmap_area_list);
  939. }
  940. return 0;
  941. }
  942. /*
  943. * Returns a start address of the newly allocated area, if success.
  944. * Otherwise a vend is returned that indicates failure.
  945. */
  946. static __always_inline unsigned long
  947. __alloc_vmap_area(unsigned long size, unsigned long align,
  948. unsigned long vstart, unsigned long vend)
  949. {
  950. unsigned long nva_start_addr;
  951. struct vmap_area *va;
  952. enum fit_type type;
  953. int ret;
  954. va = find_vmap_lowest_match(size, align, vstart);
  955. if (unlikely(!va))
  956. return vend;
  957. if (va->va_start > vstart)
  958. nva_start_addr = ALIGN(va->va_start, align);
  959. else
  960. nva_start_addr = ALIGN(vstart, align);
  961. /* Check the "vend" restriction. */
  962. if (nva_start_addr + size > vend)
  963. return vend;
  964. /* Classify what we have found. */
  965. type = classify_va_fit_type(va, nva_start_addr, size);
  966. if (WARN_ON_ONCE(type == NOTHING_FIT))
  967. return vend;
  968. /* Update the free vmap_area. */
  969. ret = adjust_va_to_fit_type(va, nva_start_addr, size, type);
  970. if (ret)
  971. return vend;
  972. #if DEBUG_AUGMENT_LOWEST_MATCH_CHECK
  973. find_vmap_lowest_match_check(size);
  974. #endif
  975. return nva_start_addr;
  976. }
  977. /*
  978. * Free a region of KVA allocated by alloc_vmap_area
  979. */
  980. static void free_vmap_area(struct vmap_area *va)
  981. {
  982. /*
  983. * Remove from the busy tree/list.
  984. */
  985. spin_lock(&vmap_area_lock);
  986. unlink_va(va, &vmap_area_root);
  987. spin_unlock(&vmap_area_lock);
  988. /*
  989. * Insert/Merge it back to the free tree/list.
  990. */
  991. spin_lock(&free_vmap_area_lock);
  992. merge_or_add_vmap_area(va, &free_vmap_area_root, &free_vmap_area_list);
  993. spin_unlock(&free_vmap_area_lock);
  994. }
  995. /*
  996. * Allocate a region of KVA of the specified size and alignment, within the
  997. * vstart and vend.
  998. */
  999. static struct vmap_area *alloc_vmap_area(unsigned long size,
  1000. unsigned long align,
  1001. unsigned long vstart, unsigned long vend,
  1002. int node, gfp_t gfp_mask)
  1003. {
  1004. struct vmap_area *va, *pva;
  1005. unsigned long addr;
  1006. int purged = 0;
  1007. int ret;
  1008. BUG_ON(!size);
  1009. BUG_ON(offset_in_page(size));
  1010. BUG_ON(!is_power_of_2(align));
  1011. if (unlikely(!vmap_initialized))
  1012. return ERR_PTR(-EBUSY);
  1013. might_sleep();
  1014. gfp_mask = gfp_mask & GFP_RECLAIM_MASK;
  1015. va = kmem_cache_alloc_node(vmap_area_cachep, gfp_mask, node);
  1016. if (unlikely(!va))
  1017. return ERR_PTR(-ENOMEM);
  1018. /*
  1019. * Only scan the relevant parts containing pointers to other objects
  1020. * to avoid false negatives.
  1021. */
  1022. kmemleak_scan_area(&va->rb_node, SIZE_MAX, gfp_mask);
  1023. retry:
  1024. /*
  1025. * Preload this CPU with one extra vmap_area object. It is used
  1026. * when fit type of free area is NE_FIT_TYPE. Please note, it
  1027. * does not guarantee that an allocation occurs on a CPU that
  1028. * is preloaded, instead we minimize the case when it is not.
  1029. * It can happen because of cpu migration, because there is a
  1030. * race until the below spinlock is taken.
  1031. *
  1032. * The preload is done in non-atomic context, thus it allows us
  1033. * to use more permissive allocation masks to be more stable under
  1034. * low memory condition and high memory pressure. In rare case,
  1035. * if not preloaded, GFP_NOWAIT is used.
  1036. *
  1037. * Set "pva" to NULL here, because of "retry" path.
  1038. */
  1039. pva = NULL;
  1040. if (!this_cpu_read(ne_fit_preload_node))
  1041. /*
  1042. * Even if it fails we do not really care about that.
  1043. * Just proceed as it is. If needed "overflow" path
  1044. * will refill the cache we allocate from.
  1045. */
  1046. pva = kmem_cache_alloc_node(vmap_area_cachep, gfp_mask, node);
  1047. spin_lock(&free_vmap_area_lock);
  1048. if (pva && __this_cpu_cmpxchg(ne_fit_preload_node, NULL, pva))
  1049. kmem_cache_free(vmap_area_cachep, pva);
  1050. /*
  1051. * If an allocation fails, the "vend" address is
  1052. * returned. Therefore trigger the overflow path.
  1053. */
  1054. addr = __alloc_vmap_area(size, align, vstart, vend);
  1055. spin_unlock(&free_vmap_area_lock);
  1056. if (unlikely(addr == vend))
  1057. goto overflow;
  1058. va->va_start = addr;
  1059. va->va_end = addr + size;
  1060. va->vm = NULL;
  1061. spin_lock(&vmap_area_lock);
  1062. insert_vmap_area(va, &vmap_area_root, &vmap_area_list);
  1063. spin_unlock(&vmap_area_lock);
  1064. BUG_ON(!IS_ALIGNED(va->va_start, align));
  1065. BUG_ON(va->va_start < vstart);
  1066. BUG_ON(va->va_end > vend);
  1067. ret = kasan_populate_vmalloc(addr, size);
  1068. if (ret) {
  1069. free_vmap_area(va);
  1070. return ERR_PTR(ret);
  1071. }
  1072. return va;
  1073. overflow:
  1074. if (!purged) {
  1075. purge_vmap_area_lazy();
  1076. purged = 1;
  1077. goto retry;
  1078. }
  1079. if (gfpflags_allow_blocking(gfp_mask)) {
  1080. unsigned long freed = 0;
  1081. blocking_notifier_call_chain(&vmap_notify_list, 0, &freed);
  1082. if (freed > 0) {
  1083. purged = 0;
  1084. goto retry;
  1085. }
  1086. }
  1087. if (!(gfp_mask & __GFP_NOWARN) && printk_ratelimit())
  1088. pr_warn("vmap allocation for size %lu failed: use vmalloc=<size> to increase size\n",
  1089. size);
  1090. kmem_cache_free(vmap_area_cachep, va);
  1091. return ERR_PTR(-EBUSY);
  1092. }
  1093. int register_vmap_purge_notifier(struct notifier_block *nb)
  1094. {
  1095. return blocking_notifier_chain_register(&vmap_notify_list, nb);
  1096. }
  1097. EXPORT_SYMBOL_GPL(register_vmap_purge_notifier);
  1098. int unregister_vmap_purge_notifier(struct notifier_block *nb)
  1099. {
  1100. return blocking_notifier_chain_unregister(&vmap_notify_list, nb);
  1101. }
  1102. EXPORT_SYMBOL_GPL(unregister_vmap_purge_notifier);
  1103. /*
  1104. * lazy_max_pages is the maximum amount of virtual address space we gather up
  1105. * before attempting to purge with a TLB flush.
  1106. *
  1107. * There is a tradeoff here: a larger number will cover more kernel page tables
  1108. * and take slightly longer to purge, but it will linearly reduce the number of
  1109. * global TLB flushes that must be performed. It would seem natural to scale
  1110. * this number up linearly with the number of CPUs (because vmapping activity
  1111. * could also scale linearly with the number of CPUs), however it is likely
  1112. * that in practice, workloads might be constrained in other ways that mean
  1113. * vmap activity will not scale linearly with CPUs. Also, I want to be
  1114. * conservative and not introduce a big latency on huge systems, so go with
  1115. * a less aggressive log scale. It will still be an improvement over the old
  1116. * code, and it will be simple to change the scale factor if we find that it
  1117. * becomes a problem on bigger systems.
  1118. */
  1119. static unsigned long lazy_max_pages(void)
  1120. {
  1121. unsigned int log;
  1122. log = fls(num_online_cpus());
  1123. return log * (32UL * 1024 * 1024 / PAGE_SIZE);
  1124. }
  1125. static atomic_long_t vmap_lazy_nr = ATOMIC_LONG_INIT(0);
  1126. /*
  1127. * Serialize vmap purging. There is no actual criticial section protected
  1128. * by this look, but we want to avoid concurrent calls for performance
  1129. * reasons and to make the pcpu_get_vm_areas more deterministic.
  1130. */
  1131. static DEFINE_MUTEX(vmap_purge_lock);
  1132. /* for per-CPU blocks */
  1133. static void purge_fragmented_blocks_allcpus(void);
  1134. /*
  1135. * called before a call to iounmap() if the caller wants vm_area_struct's
  1136. * immediately freed.
  1137. */
  1138. void set_iounmap_nonlazy(void)
  1139. {
  1140. atomic_long_set(&vmap_lazy_nr, lazy_max_pages()+1);
  1141. }
  1142. /*
  1143. * Purges all lazily-freed vmap areas.
  1144. */
  1145. static bool __purge_vmap_area_lazy(unsigned long start, unsigned long end)
  1146. {
  1147. unsigned long resched_threshold;
  1148. struct llist_node *valist;
  1149. struct vmap_area *va;
  1150. struct vmap_area *n_va;
  1151. lockdep_assert_held(&vmap_purge_lock);
  1152. valist = llist_del_all(&vmap_purge_list);
  1153. if (unlikely(valist == NULL))
  1154. return false;
  1155. /*
  1156. * TODO: to calculate a flush range without looping.
  1157. * The list can be up to lazy_max_pages() elements.
  1158. */
  1159. llist_for_each_entry(va, valist, purge_list) {
  1160. if (va->va_start < start)
  1161. start = va->va_start;
  1162. if (va->va_end > end)
  1163. end = va->va_end;
  1164. }
  1165. flush_tlb_kernel_range(start, end);
  1166. resched_threshold = lazy_max_pages() << 1;
  1167. spin_lock(&free_vmap_area_lock);
  1168. llist_for_each_entry_safe(va, n_va, valist, purge_list) {
  1169. unsigned long nr = (va->va_end - va->va_start) >> PAGE_SHIFT;
  1170. unsigned long orig_start = va->va_start;
  1171. unsigned long orig_end = va->va_end;
  1172. /*
  1173. * Finally insert or merge lazily-freed area. It is
  1174. * detached and there is no need to "unlink" it from
  1175. * anything.
  1176. */
  1177. va = merge_or_add_vmap_area(va, &free_vmap_area_root,
  1178. &free_vmap_area_list);
  1179. if (!va)
  1180. continue;
  1181. if (is_vmalloc_or_module_addr((void *)orig_start))
  1182. kasan_release_vmalloc(orig_start, orig_end,
  1183. va->va_start, va->va_end);
  1184. atomic_long_sub(nr, &vmap_lazy_nr);
  1185. if (atomic_long_read(&vmap_lazy_nr) < resched_threshold)
  1186. cond_resched_lock(&free_vmap_area_lock);
  1187. }
  1188. spin_unlock(&free_vmap_area_lock);
  1189. return true;
  1190. }
  1191. /*
  1192. * Kick off a purge of the outstanding lazy areas. Don't bother if somebody
  1193. * is already purging.
  1194. */
  1195. static void try_purge_vmap_area_lazy(void)
  1196. {
  1197. if (mutex_trylock(&vmap_purge_lock)) {
  1198. __purge_vmap_area_lazy(ULONG_MAX, 0);
  1199. mutex_unlock(&vmap_purge_lock);
  1200. }
  1201. }
  1202. /*
  1203. * Kick off a purge of the outstanding lazy areas.
  1204. */
  1205. static void purge_vmap_area_lazy(void)
  1206. {
  1207. mutex_lock(&vmap_purge_lock);
  1208. purge_fragmented_blocks_allcpus();
  1209. __purge_vmap_area_lazy(ULONG_MAX, 0);
  1210. mutex_unlock(&vmap_purge_lock);
  1211. }
  1212. /*
  1213. * Free a vmap area, caller ensuring that the area has been unmapped
  1214. * and flush_cache_vunmap had been called for the correct range
  1215. * previously.
  1216. */
  1217. static void free_vmap_area_noflush(struct vmap_area *va)
  1218. {
  1219. unsigned long nr_lazy;
  1220. spin_lock(&vmap_area_lock);
  1221. unlink_va(va, &vmap_area_root);
  1222. spin_unlock(&vmap_area_lock);
  1223. nr_lazy = atomic_long_add_return((va->va_end - va->va_start) >>
  1224. PAGE_SHIFT, &vmap_lazy_nr);
  1225. /* After this point, we may free va at any time */
  1226. llist_add(&va->purge_list, &vmap_purge_list);
  1227. if (unlikely(nr_lazy > lazy_max_pages()))
  1228. try_purge_vmap_area_lazy();
  1229. }
  1230. /*
  1231. * Free and unmap a vmap area
  1232. */
  1233. static void free_unmap_vmap_area(struct vmap_area *va)
  1234. {
  1235. flush_cache_vunmap(va->va_start, va->va_end);
  1236. unmap_kernel_range_noflush(va->va_start, va->va_end - va->va_start);
  1237. if (debug_pagealloc_enabled_static())
  1238. flush_tlb_kernel_range(va->va_start, va->va_end);
  1239. free_vmap_area_noflush(va);
  1240. }
  1241. static struct vmap_area *find_vmap_area(unsigned long addr)
  1242. {
  1243. struct vmap_area *va;
  1244. spin_lock(&vmap_area_lock);
  1245. va = __find_vmap_area(addr);
  1246. spin_unlock(&vmap_area_lock);
  1247. return va;
  1248. }
  1249. /*** Per cpu kva allocator ***/
  1250. /*
  1251. * vmap space is limited especially on 32 bit architectures. Ensure there is
  1252. * room for at least 16 percpu vmap blocks per CPU.
  1253. */
  1254. /*
  1255. * If we had a constant VMALLOC_START and VMALLOC_END, we'd like to be able
  1256. * to #define VMALLOC_SPACE (VMALLOC_END-VMALLOC_START). Guess
  1257. * instead (we just need a rough idea)
  1258. */
  1259. #if BITS_PER_LONG == 32
  1260. #define VMALLOC_SPACE (128UL*1024*1024)
  1261. #else
  1262. #define VMALLOC_SPACE (128UL*1024*1024*1024)
  1263. #endif
  1264. #define VMALLOC_PAGES (VMALLOC_SPACE / PAGE_SIZE)
  1265. #define VMAP_MAX_ALLOC BITS_PER_LONG /* 256K with 4K pages */
  1266. #define VMAP_BBMAP_BITS_MAX 1024 /* 4MB with 4K pages */
  1267. #define VMAP_BBMAP_BITS_MIN (VMAP_MAX_ALLOC*2)
  1268. #define VMAP_MIN(x, y) ((x) < (y) ? (x) : (y)) /* can't use min() */
  1269. #define VMAP_MAX(x, y) ((x) > (y) ? (x) : (y)) /* can't use max() */
  1270. #define VMAP_BBMAP_BITS \
  1271. VMAP_MIN(VMAP_BBMAP_BITS_MAX, \
  1272. VMAP_MAX(VMAP_BBMAP_BITS_MIN, \
  1273. VMALLOC_PAGES / roundup_pow_of_two(NR_CPUS) / 16))
  1274. #define VMAP_BLOCK_SIZE (VMAP_BBMAP_BITS * PAGE_SIZE)
  1275. struct vmap_block_queue {
  1276. spinlock_t lock;
  1277. struct list_head free;
  1278. };
  1279. struct vmap_block {
  1280. spinlock_t lock;
  1281. struct vmap_area *va;
  1282. unsigned long free, dirty;
  1283. unsigned long dirty_min, dirty_max; /*< dirty range */
  1284. struct list_head free_list;
  1285. struct rcu_head rcu_head;
  1286. struct list_head purge;
  1287. };
  1288. /* Queue of free and dirty vmap blocks, for allocation and flushing purposes */
  1289. static DEFINE_PER_CPU(struct vmap_block_queue, vmap_block_queue);
  1290. /*
  1291. * XArray of vmap blocks, indexed by address, to quickly find a vmap block
  1292. * in the free path. Could get rid of this if we change the API to return a
  1293. * "cookie" from alloc, to be passed to free. But no big deal yet.
  1294. */
  1295. static DEFINE_XARRAY(vmap_blocks);
  1296. /*
  1297. * We should probably have a fallback mechanism to allocate virtual memory
  1298. * out of partially filled vmap blocks. However vmap block sizing should be
  1299. * fairly reasonable according to the vmalloc size, so it shouldn't be a
  1300. * big problem.
  1301. */
  1302. static unsigned long addr_to_vb_idx(unsigned long addr)
  1303. {
  1304. addr -= VMALLOC_START & ~(VMAP_BLOCK_SIZE-1);
  1305. addr /= VMAP_BLOCK_SIZE;
  1306. return addr;
  1307. }
  1308. static void *vmap_block_vaddr(unsigned long va_start, unsigned long pages_off)
  1309. {
  1310. unsigned long addr;
  1311. addr = va_start + (pages_off << PAGE_SHIFT);
  1312. BUG_ON(addr_to_vb_idx(addr) != addr_to_vb_idx(va_start));
  1313. return (void *)addr;
  1314. }
  1315. /**
  1316. * new_vmap_block - allocates new vmap_block and occupies 2^order pages in this
  1317. * block. Of course pages number can't exceed VMAP_BBMAP_BITS
  1318. * @order: how many 2^order pages should be occupied in newly allocated block
  1319. * @gfp_mask: flags for the page level allocator
  1320. *
  1321. * Return: virtual address in a newly allocated block or ERR_PTR(-errno)
  1322. */
  1323. static void *new_vmap_block(unsigned int order, gfp_t gfp_mask)
  1324. {
  1325. struct vmap_block_queue *vbq;
  1326. struct vmap_block *vb;
  1327. struct vmap_area *va;
  1328. unsigned long vb_idx;
  1329. int node, err;
  1330. void *vaddr;
  1331. node = numa_node_id();
  1332. vb = kmalloc_node(sizeof(struct vmap_block),
  1333. gfp_mask & GFP_RECLAIM_MASK, node);
  1334. if (unlikely(!vb))
  1335. return ERR_PTR(-ENOMEM);
  1336. va = alloc_vmap_area(VMAP_BLOCK_SIZE, VMAP_BLOCK_SIZE,
  1337. VMALLOC_START, VMALLOC_END,
  1338. node, gfp_mask);
  1339. if (IS_ERR(va)) {
  1340. kfree(vb);
  1341. return ERR_CAST(va);
  1342. }
  1343. vaddr = vmap_block_vaddr(va->va_start, 0);
  1344. spin_lock_init(&vb->lock);
  1345. vb->va = va;
  1346. /* At least something should be left free */
  1347. BUG_ON(VMAP_BBMAP_BITS <= (1UL << order));
  1348. vb->free = VMAP_BBMAP_BITS - (1UL << order);
  1349. vb->dirty = 0;
  1350. vb->dirty_min = VMAP_BBMAP_BITS;
  1351. vb->dirty_max = 0;
  1352. INIT_LIST_HEAD(&vb->free_list);
  1353. vb_idx = addr_to_vb_idx(va->va_start);
  1354. err = xa_insert(&vmap_blocks, vb_idx, vb, gfp_mask);
  1355. if (err) {
  1356. kfree(vb);
  1357. free_vmap_area(va);
  1358. return ERR_PTR(err);
  1359. }
  1360. vbq = &get_cpu_var(vmap_block_queue);
  1361. spin_lock(&vbq->lock);
  1362. list_add_tail_rcu(&vb->free_list, &vbq->free);
  1363. spin_unlock(&vbq->lock);
  1364. put_cpu_var(vmap_block_queue);
  1365. return vaddr;
  1366. }
  1367. static void free_vmap_block(struct vmap_block *vb)
  1368. {
  1369. struct vmap_block *tmp;
  1370. tmp = xa_erase(&vmap_blocks, addr_to_vb_idx(vb->va->va_start));
  1371. BUG_ON(tmp != vb);
  1372. free_vmap_area_noflush(vb->va);
  1373. kfree_rcu(vb, rcu_head);
  1374. }
  1375. static void purge_fragmented_blocks(int cpu)
  1376. {
  1377. LIST_HEAD(purge);
  1378. struct vmap_block *vb;
  1379. struct vmap_block *n_vb;
  1380. struct vmap_block_queue *vbq = &per_cpu(vmap_block_queue, cpu);
  1381. rcu_read_lock();
  1382. list_for_each_entry_rcu(vb, &vbq->free, free_list) {
  1383. if (!(vb->free + vb->dirty == VMAP_BBMAP_BITS && vb->dirty != VMAP_BBMAP_BITS))
  1384. continue;
  1385. spin_lock(&vb->lock);
  1386. if (vb->free + vb->dirty == VMAP_BBMAP_BITS && vb->dirty != VMAP_BBMAP_BITS) {
  1387. vb->free = 0; /* prevent further allocs after releasing lock */
  1388. vb->dirty = VMAP_BBMAP_BITS; /* prevent purging it again */
  1389. vb->dirty_min = 0;
  1390. vb->dirty_max = VMAP_BBMAP_BITS;
  1391. spin_lock(&vbq->lock);
  1392. list_del_rcu(&vb->free_list);
  1393. spin_unlock(&vbq->lock);
  1394. spin_unlock(&vb->lock);
  1395. list_add_tail(&vb->purge, &purge);
  1396. } else
  1397. spin_unlock(&vb->lock);
  1398. }
  1399. rcu_read_unlock();
  1400. list_for_each_entry_safe(vb, n_vb, &purge, purge) {
  1401. list_del(&vb->purge);
  1402. free_vmap_block(vb);
  1403. }
  1404. }
  1405. static void purge_fragmented_blocks_allcpus(void)
  1406. {
  1407. int cpu;
  1408. for_each_possible_cpu(cpu)
  1409. purge_fragmented_blocks(cpu);
  1410. }
  1411. static void *vb_alloc(unsigned long size, gfp_t gfp_mask)
  1412. {
  1413. struct vmap_block_queue *vbq;
  1414. struct vmap_block *vb;
  1415. void *vaddr = NULL;
  1416. unsigned int order;
  1417. BUG_ON(offset_in_page(size));
  1418. BUG_ON(size > PAGE_SIZE*VMAP_MAX_ALLOC);
  1419. if (WARN_ON(size == 0)) {
  1420. /*
  1421. * Allocating 0 bytes isn't what caller wants since
  1422. * get_order(0) returns funny result. Just warn and terminate
  1423. * early.
  1424. */
  1425. return NULL;
  1426. }
  1427. order = get_order(size);
  1428. rcu_read_lock();
  1429. vbq = &get_cpu_var(vmap_block_queue);
  1430. list_for_each_entry_rcu(vb, &vbq->free, free_list) {
  1431. unsigned long pages_off;
  1432. spin_lock(&vb->lock);
  1433. if (vb->free < (1UL << order)) {
  1434. spin_unlock(&vb->lock);
  1435. continue;
  1436. }
  1437. pages_off = VMAP_BBMAP_BITS - vb->free;
  1438. vaddr = vmap_block_vaddr(vb->va->va_start, pages_off);
  1439. vb->free -= 1UL << order;
  1440. if (vb->free == 0) {
  1441. spin_lock(&vbq->lock);
  1442. list_del_rcu(&vb->free_list);
  1443. spin_unlock(&vbq->lock);
  1444. }
  1445. spin_unlock(&vb->lock);
  1446. break;
  1447. }
  1448. put_cpu_var(vmap_block_queue);
  1449. rcu_read_unlock();
  1450. /* Allocate new block if nothing was found */
  1451. if (!vaddr)
  1452. vaddr = new_vmap_block(order, gfp_mask);
  1453. return vaddr;
  1454. }
  1455. static void vb_free(unsigned long addr, unsigned long size)
  1456. {
  1457. unsigned long offset;
  1458. unsigned int order;
  1459. struct vmap_block *vb;
  1460. BUG_ON(offset_in_page(size));
  1461. BUG_ON(size > PAGE_SIZE*VMAP_MAX_ALLOC);
  1462. flush_cache_vunmap(addr, addr + size);
  1463. order = get_order(size);
  1464. offset = (addr & (VMAP_BLOCK_SIZE - 1)) >> PAGE_SHIFT;
  1465. vb = xa_load(&vmap_blocks, addr_to_vb_idx(addr));
  1466. unmap_kernel_range_noflush(addr, size);
  1467. if (debug_pagealloc_enabled_static())
  1468. flush_tlb_kernel_range(addr, addr + size);
  1469. spin_lock(&vb->lock);
  1470. /* Expand dirty range */
  1471. vb->dirty_min = min(vb->dirty_min, offset);
  1472. vb->dirty_max = max(vb->dirty_max, offset + (1UL << order));
  1473. vb->dirty += 1UL << order;
  1474. if (vb->dirty == VMAP_BBMAP_BITS) {
  1475. BUG_ON(vb->free);
  1476. spin_unlock(&vb->lock);
  1477. free_vmap_block(vb);
  1478. } else
  1479. spin_unlock(&vb->lock);
  1480. }
  1481. static void _vm_unmap_aliases(unsigned long start, unsigned long end, int flush)
  1482. {
  1483. int cpu;
  1484. if (unlikely(!vmap_initialized))
  1485. return;
  1486. might_sleep();
  1487. for_each_possible_cpu(cpu) {
  1488. struct vmap_block_queue *vbq = &per_cpu(vmap_block_queue, cpu);
  1489. struct vmap_block *vb;
  1490. rcu_read_lock();
  1491. list_for_each_entry_rcu(vb, &vbq->free, free_list) {
  1492. spin_lock(&vb->lock);
  1493. if (vb->dirty && vb->dirty != VMAP_BBMAP_BITS) {
  1494. unsigned long va_start = vb->va->va_start;
  1495. unsigned long s, e;
  1496. s = va_start + (vb->dirty_min << PAGE_SHIFT);
  1497. e = va_start + (vb->dirty_max << PAGE_SHIFT);
  1498. start = min(s, start);
  1499. end = max(e, end);
  1500. flush = 1;
  1501. }
  1502. spin_unlock(&vb->lock);
  1503. }
  1504. rcu_read_unlock();
  1505. }
  1506. mutex_lock(&vmap_purge_lock);
  1507. purge_fragmented_blocks_allcpus();
  1508. if (!__purge_vmap_area_lazy(start, end) && flush)
  1509. flush_tlb_kernel_range(start, end);
  1510. mutex_unlock(&vmap_purge_lock);
  1511. }
  1512. /**
  1513. * vm_unmap_aliases - unmap outstanding lazy aliases in the vmap layer
  1514. *
  1515. * The vmap/vmalloc layer lazily flushes kernel virtual mappings primarily
  1516. * to amortize TLB flushing overheads. What this means is that any page you
  1517. * have now, may, in a former life, have been mapped into kernel virtual
  1518. * address by the vmap layer and so there might be some CPUs with TLB entries
  1519. * still referencing that page (additional to the regular 1:1 kernel mapping).
  1520. *
  1521. * vm_unmap_aliases flushes all such lazy mappings. After it returns, we can
  1522. * be sure that none of the pages we have control over will have any aliases
  1523. * from the vmap layer.
  1524. */
  1525. void vm_unmap_aliases(void)
  1526. {
  1527. unsigned long start = ULONG_MAX, end = 0;
  1528. int flush = 0;
  1529. _vm_unmap_aliases(start, end, flush);
  1530. }
  1531. EXPORT_SYMBOL_GPL(vm_unmap_aliases);
  1532. /**
  1533. * vm_unmap_ram - unmap linear kernel address space set up by vm_map_ram
  1534. * @mem: the pointer returned by vm_map_ram
  1535. * @count: the count passed to that vm_map_ram call (cannot unmap partial)
  1536. */
  1537. void vm_unmap_ram(const void *mem, unsigned int count)
  1538. {
  1539. unsigned long size = (unsigned long)count << PAGE_SHIFT;
  1540. unsigned long addr = (unsigned long)mem;
  1541. struct vmap_area *va;
  1542. might_sleep();
  1543. BUG_ON(!addr);
  1544. BUG_ON(addr < VMALLOC_START);
  1545. BUG_ON(addr > VMALLOC_END);
  1546. BUG_ON(!PAGE_ALIGNED(addr));
  1547. kasan_poison_vmalloc(mem, size);
  1548. if (likely(count <= VMAP_MAX_ALLOC)) {
  1549. debug_check_no_locks_freed(mem, size);
  1550. vb_free(addr, size);
  1551. return;
  1552. }
  1553. va = find_vmap_area(addr);
  1554. BUG_ON(!va);
  1555. debug_check_no_locks_freed((void *)va->va_start,
  1556. (va->va_end - va->va_start));
  1557. free_unmap_vmap_area(va);
  1558. }
  1559. EXPORT_SYMBOL(vm_unmap_ram);
  1560. /**
  1561. * vm_map_ram - map pages linearly into kernel virtual address (vmalloc space)
  1562. * @pages: an array of pointers to the pages to be mapped
  1563. * @count: number of pages
  1564. * @node: prefer to allocate data structures on this node
  1565. *
  1566. * If you use this function for less than VMAP_MAX_ALLOC pages, it could be
  1567. * faster than vmap so it's good. But if you mix long-life and short-life
  1568. * objects with vm_map_ram(), it could consume lots of address space through
  1569. * fragmentation (especially on a 32bit machine). You could see failures in
  1570. * the end. Please use this function for short-lived objects.
  1571. *
  1572. * Returns: a pointer to the address that has been mapped, or %NULL on failure
  1573. */
  1574. void *vm_map_ram(struct page **pages, unsigned int count, int node)
  1575. {
  1576. unsigned long size = (unsigned long)count << PAGE_SHIFT;
  1577. unsigned long addr;
  1578. void *mem;
  1579. if (likely(count <= VMAP_MAX_ALLOC)) {
  1580. mem = vb_alloc(size, GFP_KERNEL);
  1581. if (IS_ERR(mem))
  1582. return NULL;
  1583. addr = (unsigned long)mem;
  1584. } else {
  1585. struct vmap_area *va;
  1586. va = alloc_vmap_area(size, PAGE_SIZE,
  1587. VMALLOC_START, VMALLOC_END, node, GFP_KERNEL);
  1588. if (IS_ERR(va))
  1589. return NULL;
  1590. addr = va->va_start;
  1591. mem = (void *)addr;
  1592. }
  1593. kasan_unpoison_vmalloc(mem, size);
  1594. if (map_kernel_range(addr, size, PAGE_KERNEL, pages) < 0) {
  1595. vm_unmap_ram(mem, count);
  1596. return NULL;
  1597. }
  1598. return mem;
  1599. }
  1600. EXPORT_SYMBOL(vm_map_ram);
  1601. static struct vm_struct *vmlist __initdata;
  1602. /**
  1603. * vm_area_add_early - add vmap area early during boot
  1604. * @vm: vm_struct to add
  1605. *
  1606. * This function is used to add fixed kernel vm area to vmlist before
  1607. * vmalloc_init() is called. @vm->addr, @vm->size, and @vm->flags
  1608. * should contain proper values and the other fields should be zero.
  1609. *
  1610. * DO NOT USE THIS FUNCTION UNLESS YOU KNOW WHAT YOU'RE DOING.
  1611. */
  1612. void __init vm_area_add_early(struct vm_struct *vm)
  1613. {
  1614. struct vm_struct *tmp, **p;
  1615. BUG_ON(vmap_initialized);
  1616. for (p = &vmlist; (tmp = *p) != NULL; p = &tmp->next) {
  1617. if (tmp->addr >= vm->addr) {
  1618. BUG_ON(tmp->addr < vm->addr + vm->size);
  1619. break;
  1620. } else
  1621. BUG_ON(tmp->addr + tmp->size > vm->addr);
  1622. }
  1623. vm->next = *p;
  1624. *p = vm;
  1625. }
  1626. /**
  1627. * vm_area_register_early - register vmap area early during boot
  1628. * @vm: vm_struct to register
  1629. * @align: requested alignment
  1630. *
  1631. * This function is used to register kernel vm area before
  1632. * vmalloc_init() is called. @vm->size and @vm->flags should contain
  1633. * proper values on entry and other fields should be zero. On return,
  1634. * vm->addr contains the allocated address.
  1635. *
  1636. * DO NOT USE THIS FUNCTION UNLESS YOU KNOW WHAT YOU'RE DOING.
  1637. */
  1638. void __init vm_area_register_early(struct vm_struct *vm, size_t align)
  1639. {
  1640. static size_t vm_init_off __initdata;
  1641. unsigned long addr;
  1642. addr = ALIGN(VMALLOC_START + vm_init_off, align);
  1643. vm_init_off = PFN_ALIGN(addr + vm->size) - VMALLOC_START;
  1644. vm->addr = (void *)addr;
  1645. vm_area_add_early(vm);
  1646. }
  1647. static void vmap_init_free_space(void)
  1648. {
  1649. unsigned long vmap_start = 1;
  1650. const unsigned long vmap_end = ULONG_MAX;
  1651. struct vmap_area *busy, *free;
  1652. /*
  1653. * B F B B B F
  1654. * -|-----|.....|-----|-----|-----|.....|-
  1655. * | The KVA space |
  1656. * |<--------------------------------->|
  1657. */
  1658. list_for_each_entry(busy, &vmap_area_list, list) {
  1659. if (busy->va_start - vmap_start > 0) {
  1660. free = kmem_cache_zalloc(vmap_area_cachep, GFP_NOWAIT);
  1661. if (!WARN_ON_ONCE(!free)) {
  1662. free->va_start = vmap_start;
  1663. free->va_end = busy->va_start;
  1664. insert_vmap_area_augment(free, NULL,
  1665. &free_vmap_area_root,
  1666. &free_vmap_area_list);
  1667. }
  1668. }
  1669. vmap_start = busy->va_end;
  1670. }
  1671. if (vmap_end - vmap_start > 0) {
  1672. free = kmem_cache_zalloc(vmap_area_cachep, GFP_NOWAIT);
  1673. if (!WARN_ON_ONCE(!free)) {
  1674. free->va_start = vmap_start;
  1675. free->va_end = vmap_end;
  1676. insert_vmap_area_augment(free, NULL,
  1677. &free_vmap_area_root,
  1678. &free_vmap_area_list);
  1679. }
  1680. }
  1681. }
  1682. void __init vmalloc_init(void)
  1683. {
  1684. struct vmap_area *va;
  1685. struct vm_struct *tmp;
  1686. int i;
  1687. /*
  1688. * Create the cache for vmap_area objects.
  1689. */
  1690. vmap_area_cachep = KMEM_CACHE(vmap_area, SLAB_PANIC);
  1691. for_each_possible_cpu(i) {
  1692. struct vmap_block_queue *vbq;
  1693. struct vfree_deferred *p;
  1694. vbq = &per_cpu(vmap_block_queue, i);
  1695. spin_lock_init(&vbq->lock);
  1696. INIT_LIST_HEAD(&vbq->free);
  1697. p = &per_cpu(vfree_deferred, i);
  1698. init_llist_head(&p->list);
  1699. INIT_WORK(&p->wq, free_work);
  1700. }
  1701. /* Import existing vmlist entries. */
  1702. for (tmp = vmlist; tmp; tmp = tmp->next) {
  1703. va = kmem_cache_zalloc(vmap_area_cachep, GFP_NOWAIT);
  1704. if (WARN_ON_ONCE(!va))
  1705. continue;
  1706. va->va_start = (unsigned long)tmp->addr;
  1707. va->va_end = va->va_start + tmp->size;
  1708. va->vm = tmp;
  1709. insert_vmap_area(va, &vmap_area_root, &vmap_area_list);
  1710. }
  1711. /*
  1712. * Now we can initialize a free vmap space.
  1713. */
  1714. vmap_init_free_space();
  1715. vmap_initialized = true;
  1716. }
  1717. /**
  1718. * unmap_kernel_range - unmap kernel VM area and flush cache and TLB
  1719. * @addr: start of the VM area to unmap
  1720. * @size: size of the VM area to unmap
  1721. *
  1722. * Similar to unmap_kernel_range_noflush() but flushes vcache before
  1723. * the unmapping and tlb after.
  1724. */
  1725. void unmap_kernel_range(unsigned long addr, unsigned long size)
  1726. {
  1727. unsigned long end = addr + size;
  1728. flush_cache_vunmap(addr, end);
  1729. unmap_kernel_range_noflush(addr, size);
  1730. flush_tlb_kernel_range(addr, end);
  1731. }
  1732. static inline void setup_vmalloc_vm_locked(struct vm_struct *vm,
  1733. struct vmap_area *va, unsigned long flags, const void *caller)
  1734. {
  1735. vm->flags = flags;
  1736. vm->addr = (void *)va->va_start;
  1737. vm->size = va->va_end - va->va_start;
  1738. vm->caller = caller;
  1739. va->vm = vm;
  1740. trace_android_vh_save_vmalloc_stack(flags, vm);
  1741. }
  1742. static void setup_vmalloc_vm(struct vm_struct *vm, struct vmap_area *va,
  1743. unsigned long flags, const void *caller)
  1744. {
  1745. spin_lock(&vmap_area_lock);
  1746. setup_vmalloc_vm_locked(vm, va, flags, caller);
  1747. spin_unlock(&vmap_area_lock);
  1748. }
  1749. static void clear_vm_uninitialized_flag(struct vm_struct *vm)
  1750. {
  1751. /*
  1752. * Before removing VM_UNINITIALIZED,
  1753. * we should make sure that vm has proper values.
  1754. * Pair with smp_rmb() in show_numa_info().
  1755. */
  1756. smp_wmb();
  1757. vm->flags &= ~VM_UNINITIALIZED;
  1758. }
  1759. static struct vm_struct *__get_vm_area_node(unsigned long size,
  1760. unsigned long align, unsigned long flags, unsigned long start,
  1761. unsigned long end, int node, gfp_t gfp_mask, const void *caller)
  1762. {
  1763. struct vmap_area *va;
  1764. struct vm_struct *area;
  1765. unsigned long requested_size = size;
  1766. BUG_ON(in_interrupt());
  1767. size = PAGE_ALIGN(size);
  1768. if (unlikely(!size))
  1769. return NULL;
  1770. if (flags & VM_IOREMAP)
  1771. align = 1ul << clamp_t(int, get_count_order_long(size),
  1772. PAGE_SHIFT, IOREMAP_MAX_ORDER);
  1773. area = kzalloc_node(sizeof(*area), gfp_mask & GFP_RECLAIM_MASK, node);
  1774. if (unlikely(!area))
  1775. return NULL;
  1776. if (!(flags & VM_NO_GUARD))
  1777. size += PAGE_SIZE;
  1778. va = alloc_vmap_area(size, align, start, end, node, gfp_mask);
  1779. if (IS_ERR(va)) {
  1780. kfree(area);
  1781. return NULL;
  1782. }
  1783. kasan_unpoison_vmalloc((void *)va->va_start, requested_size);
  1784. setup_vmalloc_vm(area, va, flags, caller);
  1785. return area;
  1786. }
  1787. struct vm_struct *__get_vm_area_caller(unsigned long size, unsigned long flags,
  1788. unsigned long start, unsigned long end,
  1789. const void *caller)
  1790. {
  1791. return __get_vm_area_node(size, 1, flags, start, end, NUMA_NO_NODE,
  1792. GFP_KERNEL, caller);
  1793. }
  1794. EXPORT_SYMBOL_GPL(__get_vm_area_caller);
  1795. /**
  1796. * get_vm_area - reserve a contiguous kernel virtual area
  1797. * @size: size of the area
  1798. * @flags: %VM_IOREMAP for I/O mappings or VM_ALLOC
  1799. *
  1800. * Search an area of @size in the kernel virtual mapping area,
  1801. * and reserved it for out purposes. Returns the area descriptor
  1802. * on success or %NULL on failure.
  1803. *
  1804. * Return: the area descriptor on success or %NULL on failure.
  1805. */
  1806. struct vm_struct *get_vm_area(unsigned long size, unsigned long flags)
  1807. {
  1808. return __get_vm_area_node(size, 1, flags, VMALLOC_START, VMALLOC_END,
  1809. NUMA_NO_NODE, GFP_KERNEL,
  1810. __builtin_return_address(0));
  1811. }
  1812. struct vm_struct *get_vm_area_caller(unsigned long size, unsigned long flags,
  1813. const void *caller)
  1814. {
  1815. return __get_vm_area_node(size, 1, flags, VMALLOC_START, VMALLOC_END,
  1816. NUMA_NO_NODE, GFP_KERNEL, caller);
  1817. }
  1818. /**
  1819. * find_vm_area - find a continuous kernel virtual area
  1820. * @addr: base address
  1821. *
  1822. * Search for the kernel VM area starting at @addr, and return it.
  1823. * It is up to the caller to do all required locking to keep the returned
  1824. * pointer valid.
  1825. *
  1826. * Return: the area descriptor on success or %NULL on failure.
  1827. */
  1828. struct vm_struct *find_vm_area(const void *addr)
  1829. {
  1830. struct vmap_area *va;
  1831. va = find_vmap_area((unsigned long)addr);
  1832. if (!va)
  1833. return NULL;
  1834. return va->vm;
  1835. }
  1836. /**
  1837. * remove_vm_area - find and remove a continuous kernel virtual area
  1838. * @addr: base address
  1839. *
  1840. * Search for the kernel VM area starting at @addr, and remove it.
  1841. * This function returns the found VM area, but using it is NOT safe
  1842. * on SMP machines, except for its size or flags.
  1843. *
  1844. * Return: the area descriptor on success or %NULL on failure.
  1845. */
  1846. struct vm_struct *remove_vm_area(const void *addr)
  1847. {
  1848. struct vmap_area *va;
  1849. might_sleep();
  1850. spin_lock(&vmap_area_lock);
  1851. va = __find_vmap_area((unsigned long)addr);
  1852. if (va && va->vm) {
  1853. struct vm_struct *vm = va->vm;
  1854. va->vm = NULL;
  1855. spin_unlock(&vmap_area_lock);
  1856. kasan_free_shadow(vm);
  1857. free_unmap_vmap_area(va);
  1858. return vm;
  1859. }
  1860. spin_unlock(&vmap_area_lock);
  1861. return NULL;
  1862. }
  1863. static inline void set_area_direct_map(const struct vm_struct *area,
  1864. int (*set_direct_map)(struct page *page))
  1865. {
  1866. int i;
  1867. for (i = 0; i < area->nr_pages; i++)
  1868. if (page_address(area->pages[i]))
  1869. set_direct_map(area->pages[i]);
  1870. }
  1871. /* Handle removing and resetting vm mappings related to the vm_struct. */
  1872. static void vm_remove_mappings(struct vm_struct *area, int deallocate_pages)
  1873. {
  1874. unsigned long start = ULONG_MAX, end = 0;
  1875. int flush_reset = area->flags & VM_FLUSH_RESET_PERMS;
  1876. int flush_dmap = 0;
  1877. int i;
  1878. remove_vm_area(area->addr);
  1879. /* If this is not VM_FLUSH_RESET_PERMS memory, no need for the below. */
  1880. if (!flush_reset)
  1881. return;
  1882. /*
  1883. * If not deallocating pages, just do the flush of the VM area and
  1884. * return.
  1885. */
  1886. if (!deallocate_pages) {
  1887. vm_unmap_aliases();
  1888. return;
  1889. }
  1890. /*
  1891. * If execution gets here, flush the vm mapping and reset the direct
  1892. * map. Find the start and end range of the direct mappings to make sure
  1893. * the vm_unmap_aliases() flush includes the direct map.
  1894. */
  1895. for (i = 0; i < area->nr_pages; i++) {
  1896. unsigned long addr = (unsigned long)page_address(area->pages[i]);
  1897. if (addr) {
  1898. start = min(addr, start);
  1899. end = max(addr + PAGE_SIZE, end);
  1900. flush_dmap = 1;
  1901. }
  1902. }
  1903. /*
  1904. * Set direct map to something invalid so that it won't be cached if
  1905. * there are any accesses after the TLB flush, then flush the TLB and
  1906. * reset the direct map permissions to the default.
  1907. */
  1908. set_area_direct_map(area, set_direct_map_invalid_noflush);
  1909. _vm_unmap_aliases(start, end, flush_dmap);
  1910. set_area_direct_map(area, set_direct_map_default_noflush);
  1911. }
  1912. static void __vunmap(const void *addr, int deallocate_pages)
  1913. {
  1914. struct vm_struct *area;
  1915. if (!addr)
  1916. return;
  1917. if (WARN(!PAGE_ALIGNED(addr), "Trying to vfree() bad address (%p)\n",
  1918. addr))
  1919. return;
  1920. area = find_vm_area(addr);
  1921. if (unlikely(!area)) {
  1922. WARN(1, KERN_ERR "Trying to vfree() nonexistent vm area (%p)\n",
  1923. addr);
  1924. return;
  1925. }
  1926. debug_check_no_locks_freed(area->addr, get_vm_area_size(area));
  1927. debug_check_no_obj_freed(area->addr, get_vm_area_size(area));
  1928. kasan_poison_vmalloc(area->addr, get_vm_area_size(area));
  1929. vm_remove_mappings(area, deallocate_pages);
  1930. if (deallocate_pages) {
  1931. int i;
  1932. for (i = 0; i < area->nr_pages; i++) {
  1933. struct page *page = area->pages[i];
  1934. BUG_ON(!page);
  1935. __free_pages(page, 0);
  1936. }
  1937. atomic_long_sub(area->nr_pages, &nr_vmalloc_pages);
  1938. kvfree(area->pages);
  1939. }
  1940. kfree(area);
  1941. return;
  1942. }
  1943. static inline void __vfree_deferred(const void *addr)
  1944. {
  1945. /*
  1946. * Use raw_cpu_ptr() because this can be called from preemptible
  1947. * context. Preemption is absolutely fine here, because the llist_add()
  1948. * implementation is lockless, so it works even if we are adding to
  1949. * another cpu's list. schedule_work() should be fine with this too.
  1950. */
  1951. struct vfree_deferred *p = raw_cpu_ptr(&vfree_deferred);
  1952. if (llist_add((struct llist_node *)addr, &p->list))
  1953. schedule_work(&p->wq);
  1954. }
  1955. /**
  1956. * vfree_atomic - release memory allocated by vmalloc()
  1957. * @addr: memory base address
  1958. *
  1959. * This one is just like vfree() but can be called in any atomic context
  1960. * except NMIs.
  1961. */
  1962. void vfree_atomic(const void *addr)
  1963. {
  1964. BUG_ON(in_nmi());
  1965. kmemleak_free(addr);
  1966. if (!addr)
  1967. return;
  1968. __vfree_deferred(addr);
  1969. }
  1970. static void __vfree(const void *addr)
  1971. {
  1972. if (unlikely(in_interrupt()))
  1973. __vfree_deferred(addr);
  1974. else
  1975. __vunmap(addr, 1);
  1976. }
  1977. /**
  1978. * vfree - Release memory allocated by vmalloc()
  1979. * @addr: Memory base address
  1980. *
  1981. * Free the virtually continuous memory area starting at @addr, as obtained
  1982. * from one of the vmalloc() family of APIs. This will usually also free the
  1983. * physical memory underlying the virtual allocation, but that memory is
  1984. * reference counted, so it will not be freed until the last user goes away.
  1985. *
  1986. * If @addr is NULL, no operation is performed.
  1987. *
  1988. * Context:
  1989. * May sleep if called *not* from interrupt context.
  1990. * Must not be called in NMI context (strictly speaking, it could be
  1991. * if we have CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG, but making the calling
  1992. * conventions for vfree() arch-depenedent would be a really bad idea).
  1993. */
  1994. void vfree(const void *addr)
  1995. {
  1996. BUG_ON(in_nmi());
  1997. kmemleak_free(addr);
  1998. might_sleep_if(!in_interrupt());
  1999. if (!addr)
  2000. return;
  2001. __vfree(addr);
  2002. }
  2003. EXPORT_SYMBOL(vfree);
  2004. /**
  2005. * vunmap - release virtual mapping obtained by vmap()
  2006. * @addr: memory base address
  2007. *
  2008. * Free the virtually contiguous memory area starting at @addr,
  2009. * which was created from the page array passed to vmap().
  2010. *
  2011. * Must not be called in interrupt context.
  2012. */
  2013. void vunmap(const void *addr)
  2014. {
  2015. BUG_ON(in_interrupt());
  2016. might_sleep();
  2017. if (addr)
  2018. __vunmap(addr, 0);
  2019. }
  2020. EXPORT_SYMBOL(vunmap);
  2021. /**
  2022. * vmap - map an array of pages into virtually contiguous space
  2023. * @pages: array of page pointers
  2024. * @count: number of pages to map
  2025. * @flags: vm_area->flags
  2026. * @prot: page protection for the mapping
  2027. *
  2028. * Maps @count pages from @pages into contiguous kernel virtual space.
  2029. * If @flags contains %VM_MAP_PUT_PAGES the ownership of the pages array itself
  2030. * (which must be kmalloc or vmalloc memory) and one reference per pages in it
  2031. * are transferred from the caller to vmap(), and will be freed / dropped when
  2032. * vfree() is called on the return value.
  2033. *
  2034. * Return: the address of the area or %NULL on failure
  2035. */
  2036. void *vmap(struct page **pages, unsigned int count,
  2037. unsigned long flags, pgprot_t prot)
  2038. {
  2039. struct vm_struct *area;
  2040. unsigned long size; /* In bytes */
  2041. might_sleep();
  2042. if (count > totalram_pages())
  2043. return NULL;
  2044. size = (unsigned long)count << PAGE_SHIFT;
  2045. area = get_vm_area_caller(size, flags, __builtin_return_address(0));
  2046. if (!area)
  2047. return NULL;
  2048. if (map_kernel_range((unsigned long)area->addr, size, pgprot_nx(prot),
  2049. pages) < 0) {
  2050. vunmap(area->addr);
  2051. return NULL;
  2052. }
  2053. if (flags & VM_MAP_PUT_PAGES) {
  2054. area->pages = pages;
  2055. area->nr_pages = count;
  2056. }
  2057. return area->addr;
  2058. }
  2059. EXPORT_SYMBOL(vmap);
  2060. #ifdef CONFIG_VMAP_PFN
  2061. struct vmap_pfn_data {
  2062. unsigned long *pfns;
  2063. pgprot_t prot;
  2064. unsigned int idx;
  2065. };
  2066. static int vmap_pfn_apply(pte_t *pte, unsigned long addr, void *private)
  2067. {
  2068. struct vmap_pfn_data *data = private;
  2069. if (WARN_ON_ONCE(pfn_valid(data->pfns[data->idx])))
  2070. return -EINVAL;
  2071. *pte = pte_mkspecial(pfn_pte(data->pfns[data->idx++], data->prot));
  2072. return 0;
  2073. }
  2074. /**
  2075. * vmap_pfn - map an array of PFNs into virtually contiguous space
  2076. * @pfns: array of PFNs
  2077. * @count: number of pages to map
  2078. * @prot: page protection for the mapping
  2079. *
  2080. * Maps @count PFNs from @pfns into contiguous kernel virtual space and returns
  2081. * the start address of the mapping.
  2082. */
  2083. void *vmap_pfn(unsigned long *pfns, unsigned int count, pgprot_t prot)
  2084. {
  2085. struct vmap_pfn_data data = { .pfns = pfns, .prot = pgprot_nx(prot) };
  2086. struct vm_struct *area;
  2087. area = get_vm_area_caller(count * PAGE_SIZE, VM_IOREMAP,
  2088. __builtin_return_address(0));
  2089. if (!area)
  2090. return NULL;
  2091. if (apply_to_page_range(&init_mm, (unsigned long)area->addr,
  2092. count * PAGE_SIZE, vmap_pfn_apply, &data)) {
  2093. free_vm_area(area);
  2094. return NULL;
  2095. }
  2096. return area->addr;
  2097. }
  2098. EXPORT_SYMBOL_GPL(vmap_pfn);
  2099. #endif /* CONFIG_VMAP_PFN */
  2100. static void *__vmalloc_area_node(struct vm_struct *area, gfp_t gfp_mask,
  2101. pgprot_t prot, int node)
  2102. {
  2103. const gfp_t nested_gfp = (gfp_mask & GFP_RECLAIM_MASK) | __GFP_ZERO;
  2104. unsigned int nr_pages = get_vm_area_size(area) >> PAGE_SHIFT;
  2105. unsigned int array_size = nr_pages * sizeof(struct page *), i;
  2106. struct page **pages;
  2107. gfp_mask |= __GFP_NOWARN;
  2108. if (!(gfp_mask & (GFP_DMA | GFP_DMA32)))
  2109. gfp_mask |= __GFP_HIGHMEM;
  2110. /* Please note that the recursion is strictly bounded. */
  2111. if (array_size > PAGE_SIZE) {
  2112. pages = __vmalloc_node(array_size, 1, nested_gfp, node,
  2113. area->caller);
  2114. } else {
  2115. pages = kmalloc_node(array_size, nested_gfp, node);
  2116. }
  2117. if (!pages) {
  2118. remove_vm_area(area->addr);
  2119. kfree(area);
  2120. return NULL;
  2121. }
  2122. area->pages = pages;
  2123. area->nr_pages = nr_pages;
  2124. for (i = 0; i < area->nr_pages; i++) {
  2125. struct page *page;
  2126. if (node == NUMA_NO_NODE)
  2127. page = alloc_page(gfp_mask);
  2128. else
  2129. page = alloc_pages_node(node, gfp_mask, 0);
  2130. if (unlikely(!page)) {
  2131. /* Successfully allocated i pages, free them in __vfree() */
  2132. area->nr_pages = i;
  2133. atomic_long_add(area->nr_pages, &nr_vmalloc_pages);
  2134. goto fail;
  2135. }
  2136. area->pages[i] = page;
  2137. if (gfpflags_allow_blocking(gfp_mask))
  2138. cond_resched();
  2139. }
  2140. atomic_long_add(area->nr_pages, &nr_vmalloc_pages);
  2141. if (map_kernel_range((unsigned long)area->addr, get_vm_area_size(area),
  2142. prot, pages) < 0)
  2143. goto fail;
  2144. return area->addr;
  2145. fail:
  2146. warn_alloc(gfp_mask, NULL,
  2147. "vmalloc: allocation failure, allocated %ld of %ld bytes",
  2148. (area->nr_pages*PAGE_SIZE), area->size);
  2149. __vfree(area->addr);
  2150. return NULL;
  2151. }
  2152. /**
  2153. * __vmalloc_node_range - allocate virtually contiguous memory
  2154. * @size: allocation size
  2155. * @align: desired alignment
  2156. * @start: vm area range start
  2157. * @end: vm area range end
  2158. * @gfp_mask: flags for the page level allocator
  2159. * @prot: protection mask for the allocated pages
  2160. * @vm_flags: additional vm area flags (e.g. %VM_NO_GUARD)
  2161. * @node: node to use for allocation or NUMA_NO_NODE
  2162. * @caller: caller's return address
  2163. *
  2164. * Allocate enough pages to cover @size from the page level
  2165. * allocator with @gfp_mask flags. Map them into contiguous
  2166. * kernel virtual space, using a pagetable protection of @prot.
  2167. *
  2168. * Return: the address of the area or %NULL on failure
  2169. */
  2170. void *__vmalloc_node_range(unsigned long size, unsigned long align,
  2171. unsigned long start, unsigned long end, gfp_t gfp_mask,
  2172. pgprot_t prot, unsigned long vm_flags, int node,
  2173. const void *caller)
  2174. {
  2175. struct vm_struct *area;
  2176. void *addr;
  2177. unsigned long real_size = size;
  2178. size = PAGE_ALIGN(size);
  2179. if (!size || (size >> PAGE_SHIFT) > totalram_pages())
  2180. goto fail;
  2181. area = __get_vm_area_node(real_size, align, VM_ALLOC | VM_UNINITIALIZED |
  2182. vm_flags, start, end, node, gfp_mask, caller);
  2183. if (!area)
  2184. goto fail;
  2185. addr = __vmalloc_area_node(area, gfp_mask, prot, node);
  2186. if (!addr)
  2187. return NULL;
  2188. /*
  2189. * In this function, newly allocated vm_struct has VM_UNINITIALIZED
  2190. * flag. It means that vm_struct is not fully initialized.
  2191. * Now, it is fully initialized, so remove this flag here.
  2192. */
  2193. clear_vm_uninitialized_flag(area);
  2194. kmemleak_vmalloc(area, size, gfp_mask);
  2195. return addr;
  2196. fail:
  2197. warn_alloc(gfp_mask, NULL,
  2198. "vmalloc: allocation failure: %lu bytes", real_size);
  2199. return NULL;
  2200. }
  2201. /**
  2202. * __vmalloc_node - allocate virtually contiguous memory
  2203. * @size: allocation size
  2204. * @align: desired alignment
  2205. * @gfp_mask: flags for the page level allocator
  2206. * @node: node to use for allocation or NUMA_NO_NODE
  2207. * @caller: caller's return address
  2208. *
  2209. * Allocate enough pages to cover @size from the page level allocator with
  2210. * @gfp_mask flags. Map them into contiguous kernel virtual space.
  2211. *
  2212. * Reclaim modifiers in @gfp_mask - __GFP_NORETRY, __GFP_RETRY_MAYFAIL
  2213. * and __GFP_NOFAIL are not supported
  2214. *
  2215. * Any use of gfp flags outside of GFP_KERNEL should be consulted
  2216. * with mm people.
  2217. *
  2218. * Return: pointer to the allocated memory or %NULL on error
  2219. */
  2220. void *__vmalloc_node(unsigned long size, unsigned long align,
  2221. gfp_t gfp_mask, int node, const void *caller)
  2222. {
  2223. return __vmalloc_node_range(size, align, VMALLOC_START, VMALLOC_END,
  2224. gfp_mask, PAGE_KERNEL, 0, node, caller);
  2225. }
  2226. /*
  2227. * This is only for performance analysis of vmalloc and stress purpose.
  2228. * It is required by vmalloc test module, therefore do not use it other
  2229. * than that.
  2230. */
  2231. #ifdef CONFIG_TEST_VMALLOC_MODULE
  2232. EXPORT_SYMBOL_GPL(__vmalloc_node);
  2233. #endif
  2234. void *__vmalloc(unsigned long size, gfp_t gfp_mask)
  2235. {
  2236. return __vmalloc_node(size, 1, gfp_mask, NUMA_NO_NODE,
  2237. __builtin_return_address(0));
  2238. }
  2239. EXPORT_SYMBOL(__vmalloc);
  2240. /**
  2241. * vmalloc - allocate virtually contiguous memory
  2242. * @size: allocation size
  2243. *
  2244. * Allocate enough pages to cover @size from the page level
  2245. * allocator and map them into contiguous kernel virtual space.
  2246. *
  2247. * For tight control over page level allocator and protection flags
  2248. * use __vmalloc() instead.
  2249. *
  2250. * Return: pointer to the allocated memory or %NULL on error
  2251. */
  2252. void *vmalloc(unsigned long size)
  2253. {
  2254. return __vmalloc_node(size, 1, GFP_KERNEL, NUMA_NO_NODE,
  2255. __builtin_return_address(0));
  2256. }
  2257. EXPORT_SYMBOL(vmalloc);
  2258. /**
  2259. * vzalloc - allocate virtually contiguous memory with zero fill
  2260. * @size: allocation size
  2261. *
  2262. * Allocate enough pages to cover @size from the page level
  2263. * allocator and map them into contiguous kernel virtual space.
  2264. * The memory allocated is set to zero.
  2265. *
  2266. * For tight control over page level allocator and protection flags
  2267. * use __vmalloc() instead.
  2268. *
  2269. * Return: pointer to the allocated memory or %NULL on error
  2270. */
  2271. void *vzalloc(unsigned long size)
  2272. {
  2273. return __vmalloc_node(size, 1, GFP_KERNEL | __GFP_ZERO, NUMA_NO_NODE,
  2274. __builtin_return_address(0));
  2275. }
  2276. EXPORT_SYMBOL(vzalloc);
  2277. /**
  2278. * vmalloc_user - allocate zeroed virtually contiguous memory for userspace
  2279. * @size: allocation size
  2280. *
  2281. * The resulting memory area is zeroed so it can be mapped to userspace
  2282. * without leaking data.
  2283. *
  2284. * Return: pointer to the allocated memory or %NULL on error
  2285. */
  2286. void *vmalloc_user(unsigned long size)
  2287. {
  2288. return __vmalloc_node_range(size, SHMLBA, VMALLOC_START, VMALLOC_END,
  2289. GFP_KERNEL | __GFP_ZERO, PAGE_KERNEL,
  2290. VM_USERMAP, NUMA_NO_NODE,
  2291. __builtin_return_address(0));
  2292. }
  2293. EXPORT_SYMBOL(vmalloc_user);
  2294. /**
  2295. * vmalloc_node - allocate memory on a specific node
  2296. * @size: allocation size
  2297. * @node: numa node
  2298. *
  2299. * Allocate enough pages to cover @size from the page level
  2300. * allocator and map them into contiguous kernel virtual space.
  2301. *
  2302. * For tight control over page level allocator and protection flags
  2303. * use __vmalloc() instead.
  2304. *
  2305. * Return: pointer to the allocated memory or %NULL on error
  2306. */
  2307. void *vmalloc_node(unsigned long size, int node)
  2308. {
  2309. return __vmalloc_node(size, 1, GFP_KERNEL, node,
  2310. __builtin_return_address(0));
  2311. }
  2312. EXPORT_SYMBOL(vmalloc_node);
  2313. /**
  2314. * vzalloc_node - allocate memory on a specific node with zero fill
  2315. * @size: allocation size
  2316. * @node: numa node
  2317. *
  2318. * Allocate enough pages to cover @size from the page level
  2319. * allocator and map them into contiguous kernel virtual space.
  2320. * The memory allocated is set to zero.
  2321. *
  2322. * Return: pointer to the allocated memory or %NULL on error
  2323. */
  2324. void *vzalloc_node(unsigned long size, int node)
  2325. {
  2326. return __vmalloc_node(size, 1, GFP_KERNEL | __GFP_ZERO, node,
  2327. __builtin_return_address(0));
  2328. }
  2329. EXPORT_SYMBOL(vzalloc_node);
  2330. #if defined(CONFIG_64BIT) && defined(CONFIG_ZONE_DMA32)
  2331. #define GFP_VMALLOC32 (GFP_DMA32 | GFP_KERNEL)
  2332. #elif defined(CONFIG_64BIT) && defined(CONFIG_ZONE_DMA)
  2333. #define GFP_VMALLOC32 (GFP_DMA | GFP_KERNEL)
  2334. #else
  2335. /*
  2336. * 64b systems should always have either DMA or DMA32 zones. For others
  2337. * GFP_DMA32 should do the right thing and use the normal zone.
  2338. */
  2339. #define GFP_VMALLOC32 GFP_DMA32 | GFP_KERNEL
  2340. #endif
  2341. /**
  2342. * vmalloc_32 - allocate virtually contiguous memory (32bit addressable)
  2343. * @size: allocation size
  2344. *
  2345. * Allocate enough 32bit PA addressable pages to cover @size from the
  2346. * page level allocator and map them into contiguous kernel virtual space.
  2347. *
  2348. * Return: pointer to the allocated memory or %NULL on error
  2349. */
  2350. void *vmalloc_32(unsigned long size)
  2351. {
  2352. return __vmalloc_node(size, 1, GFP_VMALLOC32, NUMA_NO_NODE,
  2353. __builtin_return_address(0));
  2354. }
  2355. EXPORT_SYMBOL(vmalloc_32);
  2356. /**
  2357. * vmalloc_32_user - allocate zeroed virtually contiguous 32bit memory
  2358. * @size: allocation size
  2359. *
  2360. * The resulting memory area is 32bit addressable and zeroed so it can be
  2361. * mapped to userspace without leaking data.
  2362. *
  2363. * Return: pointer to the allocated memory or %NULL on error
  2364. */
  2365. void *vmalloc_32_user(unsigned long size)
  2366. {
  2367. return __vmalloc_node_range(size, SHMLBA, VMALLOC_START, VMALLOC_END,
  2368. GFP_VMALLOC32 | __GFP_ZERO, PAGE_KERNEL,
  2369. VM_USERMAP, NUMA_NO_NODE,
  2370. __builtin_return_address(0));
  2371. }
  2372. EXPORT_SYMBOL(vmalloc_32_user);
  2373. /*
  2374. * small helper routine , copy contents to buf from addr.
  2375. * If the page is not present, fill zero.
  2376. */
  2377. static int aligned_vread(char *buf, char *addr, unsigned long count)
  2378. {
  2379. struct page *p;
  2380. int copied = 0;
  2381. while (count) {
  2382. unsigned long offset, length;
  2383. offset = offset_in_page(addr);
  2384. length = PAGE_SIZE - offset;
  2385. if (length > count)
  2386. length = count;
  2387. p = vmalloc_to_page(addr);
  2388. /*
  2389. * To do safe access to this _mapped_ area, we need
  2390. * lock. But adding lock here means that we need to add
  2391. * overhead of vmalloc()/vfree() calles for this _debug_
  2392. * interface, rarely used. Instead of that, we'll use
  2393. * kmap() and get small overhead in this access function.
  2394. */
  2395. if (p) {
  2396. /*
  2397. * we can expect USER0 is not used (see vread/vwrite's
  2398. * function description)
  2399. */
  2400. void *map = kmap_atomic(p);
  2401. memcpy(buf, map + offset, length);
  2402. kunmap_atomic(map);
  2403. } else
  2404. memset(buf, 0, length);
  2405. addr += length;
  2406. buf += length;
  2407. copied += length;
  2408. count -= length;
  2409. }
  2410. return copied;
  2411. }
  2412. static int aligned_vwrite(char *buf, char *addr, unsigned long count)
  2413. {
  2414. struct page *p;
  2415. int copied = 0;
  2416. while (count) {
  2417. unsigned long offset, length;
  2418. offset = offset_in_page(addr);
  2419. length = PAGE_SIZE - offset;
  2420. if (length > count)
  2421. length = count;
  2422. p = vmalloc_to_page(addr);
  2423. /*
  2424. * To do safe access to this _mapped_ area, we need
  2425. * lock. But adding lock here means that we need to add
  2426. * overhead of vmalloc()/vfree() calles for this _debug_
  2427. * interface, rarely used. Instead of that, we'll use
  2428. * kmap() and get small overhead in this access function.
  2429. */
  2430. if (p) {
  2431. /*
  2432. * we can expect USER0 is not used (see vread/vwrite's
  2433. * function description)
  2434. */
  2435. void *map = kmap_atomic(p);
  2436. memcpy(map + offset, buf, length);
  2437. kunmap_atomic(map);
  2438. }
  2439. addr += length;
  2440. buf += length;
  2441. copied += length;
  2442. count -= length;
  2443. }
  2444. return copied;
  2445. }
  2446. /**
  2447. * vread() - read vmalloc area in a safe way.
  2448. * @buf: buffer for reading data
  2449. * @addr: vm address.
  2450. * @count: number of bytes to be read.
  2451. *
  2452. * This function checks that addr is a valid vmalloc'ed area, and
  2453. * copy data from that area to a given buffer. If the given memory range
  2454. * of [addr...addr+count) includes some valid address, data is copied to
  2455. * proper area of @buf. If there are memory holes, they'll be zero-filled.
  2456. * IOREMAP area is treated as memory hole and no copy is done.
  2457. *
  2458. * If [addr...addr+count) doesn't includes any intersects with alive
  2459. * vm_struct area, returns 0. @buf should be kernel's buffer.
  2460. *
  2461. * Note: In usual ops, vread() is never necessary because the caller
  2462. * should know vmalloc() area is valid and can use memcpy().
  2463. * This is for routines which have to access vmalloc area without
  2464. * any information, as /dev/kmem.
  2465. *
  2466. * Return: number of bytes for which addr and buf should be increased
  2467. * (same number as @count) or %0 if [addr...addr+count) doesn't
  2468. * include any intersection with valid vmalloc area
  2469. */
  2470. long vread(char *buf, char *addr, unsigned long count)
  2471. {
  2472. struct vmap_area *va;
  2473. struct vm_struct *vm;
  2474. char *vaddr, *buf_start = buf;
  2475. unsigned long buflen = count;
  2476. unsigned long n;
  2477. /* Don't allow overflow */
  2478. if ((unsigned long) addr + count < count)
  2479. count = -(unsigned long) addr;
  2480. spin_lock(&vmap_area_lock);
  2481. list_for_each_entry(va, &vmap_area_list, list) {
  2482. if (!count)
  2483. break;
  2484. if (!va->vm)
  2485. continue;
  2486. vm = va->vm;
  2487. vaddr = (char *) vm->addr;
  2488. if (addr >= vaddr + get_vm_area_size(vm))
  2489. continue;
  2490. while (addr < vaddr) {
  2491. if (count == 0)
  2492. goto finished;
  2493. *buf = '\0';
  2494. buf++;
  2495. addr++;
  2496. count--;
  2497. }
  2498. n = vaddr + get_vm_area_size(vm) - addr;
  2499. if (n > count)
  2500. n = count;
  2501. if (!(vm->flags & VM_IOREMAP))
  2502. aligned_vread(buf, addr, n);
  2503. else /* IOREMAP area is treated as memory hole */
  2504. memset(buf, 0, n);
  2505. buf += n;
  2506. addr += n;
  2507. count -= n;
  2508. }
  2509. finished:
  2510. spin_unlock(&vmap_area_lock);
  2511. if (buf == buf_start)
  2512. return 0;
  2513. /* zero-fill memory holes */
  2514. if (buf != buf_start + buflen)
  2515. memset(buf, 0, buflen - (buf - buf_start));
  2516. return buflen;
  2517. }
  2518. /**
  2519. * vwrite() - write vmalloc area in a safe way.
  2520. * @buf: buffer for source data
  2521. * @addr: vm address.
  2522. * @count: number of bytes to be read.
  2523. *
  2524. * This function checks that addr is a valid vmalloc'ed area, and
  2525. * copy data from a buffer to the given addr. If specified range of
  2526. * [addr...addr+count) includes some valid address, data is copied from
  2527. * proper area of @buf. If there are memory holes, no copy to hole.
  2528. * IOREMAP area is treated as memory hole and no copy is done.
  2529. *
  2530. * If [addr...addr+count) doesn't includes any intersects with alive
  2531. * vm_struct area, returns 0. @buf should be kernel's buffer.
  2532. *
  2533. * Note: In usual ops, vwrite() is never necessary because the caller
  2534. * should know vmalloc() area is valid and can use memcpy().
  2535. * This is for routines which have to access vmalloc area without
  2536. * any information, as /dev/kmem.
  2537. *
  2538. * Return: number of bytes for which addr and buf should be
  2539. * increased (same number as @count) or %0 if [addr...addr+count)
  2540. * doesn't include any intersection with valid vmalloc area
  2541. */
  2542. long vwrite(char *buf, char *addr, unsigned long count)
  2543. {
  2544. struct vmap_area *va;
  2545. struct vm_struct *vm;
  2546. char *vaddr;
  2547. unsigned long n, buflen;
  2548. int copied = 0;
  2549. /* Don't allow overflow */
  2550. if ((unsigned long) addr + count < count)
  2551. count = -(unsigned long) addr;
  2552. buflen = count;
  2553. spin_lock(&vmap_area_lock);
  2554. list_for_each_entry(va, &vmap_area_list, list) {
  2555. if (!count)
  2556. break;
  2557. if (!va->vm)
  2558. continue;
  2559. vm = va->vm;
  2560. vaddr = (char *) vm->addr;
  2561. if (addr >= vaddr + get_vm_area_size(vm))
  2562. continue;
  2563. while (addr < vaddr) {
  2564. if (count == 0)
  2565. goto finished;
  2566. buf++;
  2567. addr++;
  2568. count--;
  2569. }
  2570. n = vaddr + get_vm_area_size(vm) - addr;
  2571. if (n > count)
  2572. n = count;
  2573. if (!(vm->flags & VM_IOREMAP)) {
  2574. aligned_vwrite(buf, addr, n);
  2575. copied++;
  2576. }
  2577. buf += n;
  2578. addr += n;
  2579. count -= n;
  2580. }
  2581. finished:
  2582. spin_unlock(&vmap_area_lock);
  2583. if (!copied)
  2584. return 0;
  2585. return buflen;
  2586. }
  2587. /**
  2588. * remap_vmalloc_range_partial - map vmalloc pages to userspace
  2589. * @vma: vma to cover
  2590. * @uaddr: target user address to start at
  2591. * @kaddr: virtual address of vmalloc kernel memory
  2592. * @pgoff: offset from @kaddr to start at
  2593. * @size: size of map area
  2594. *
  2595. * Returns: 0 for success, -Exxx on failure
  2596. *
  2597. * This function checks that @kaddr is a valid vmalloc'ed area,
  2598. * and that it is big enough to cover the range starting at
  2599. * @uaddr in @vma. Will return failure if that criteria isn't
  2600. * met.
  2601. *
  2602. * Similar to remap_pfn_range() (see mm/memory.c)
  2603. */
  2604. int remap_vmalloc_range_partial(struct vm_area_struct *vma, unsigned long uaddr,
  2605. void *kaddr, unsigned long pgoff,
  2606. unsigned long size)
  2607. {
  2608. struct vm_struct *area;
  2609. unsigned long off;
  2610. unsigned long end_index;
  2611. if (check_shl_overflow(pgoff, PAGE_SHIFT, &off))
  2612. return -EINVAL;
  2613. size = PAGE_ALIGN(size);
  2614. if (!PAGE_ALIGNED(uaddr) || !PAGE_ALIGNED(kaddr))
  2615. return -EINVAL;
  2616. area = find_vm_area(kaddr);
  2617. if (!area)
  2618. return -EINVAL;
  2619. if (!(area->flags & (VM_USERMAP | VM_DMA_COHERENT)))
  2620. return -EINVAL;
  2621. if (check_add_overflow(size, off, &end_index) ||
  2622. end_index > get_vm_area_size(area))
  2623. return -EINVAL;
  2624. kaddr += off;
  2625. do {
  2626. struct page *page = vmalloc_to_page(kaddr);
  2627. int ret;
  2628. ret = vm_insert_page(vma, uaddr, page);
  2629. if (ret)
  2630. return ret;
  2631. uaddr += PAGE_SIZE;
  2632. kaddr += PAGE_SIZE;
  2633. size -= PAGE_SIZE;
  2634. } while (size > 0);
  2635. vma->vm_flags |= VM_DONTEXPAND | VM_DONTDUMP;
  2636. return 0;
  2637. }
  2638. EXPORT_SYMBOL(remap_vmalloc_range_partial);
  2639. /**
  2640. * remap_vmalloc_range - map vmalloc pages to userspace
  2641. * @vma: vma to cover (map full range of vma)
  2642. * @addr: vmalloc memory
  2643. * @pgoff: number of pages into addr before first page to map
  2644. *
  2645. * Returns: 0 for success, -Exxx on failure
  2646. *
  2647. * This function checks that addr is a valid vmalloc'ed area, and
  2648. * that it is big enough to cover the vma. Will return failure if
  2649. * that criteria isn't met.
  2650. *
  2651. * Similar to remap_pfn_range() (see mm/memory.c)
  2652. */
  2653. int remap_vmalloc_range(struct vm_area_struct *vma, void *addr,
  2654. unsigned long pgoff)
  2655. {
  2656. return remap_vmalloc_range_partial(vma, vma->vm_start,
  2657. addr, pgoff,
  2658. vma->vm_end - vma->vm_start);
  2659. }
  2660. EXPORT_SYMBOL(remap_vmalloc_range);
  2661. void free_vm_area(struct vm_struct *area)
  2662. {
  2663. struct vm_struct *ret;
  2664. ret = remove_vm_area(area->addr);
  2665. BUG_ON(ret != area);
  2666. kfree(area);
  2667. }
  2668. EXPORT_SYMBOL_GPL(free_vm_area);
  2669. #ifdef CONFIG_SMP
  2670. static struct vmap_area *node_to_va(struct rb_node *n)
  2671. {
  2672. return rb_entry_safe(n, struct vmap_area, rb_node);
  2673. }
  2674. /**
  2675. * pvm_find_va_enclose_addr - find the vmap_area @addr belongs to
  2676. * @addr: target address
  2677. *
  2678. * Returns: vmap_area if it is found. If there is no such area
  2679. * the first highest(reverse order) vmap_area is returned
  2680. * i.e. va->va_start < addr && va->va_end < addr or NULL
  2681. * if there are no any areas before @addr.
  2682. */
  2683. static struct vmap_area *
  2684. pvm_find_va_enclose_addr(unsigned long addr)
  2685. {
  2686. struct vmap_area *va, *tmp;
  2687. struct rb_node *n;
  2688. n = free_vmap_area_root.rb_node;
  2689. va = NULL;
  2690. while (n) {
  2691. tmp = rb_entry(n, struct vmap_area, rb_node);
  2692. if (tmp->va_start <= addr) {
  2693. va = tmp;
  2694. if (tmp->va_end >= addr)
  2695. break;
  2696. n = n->rb_right;
  2697. } else {
  2698. n = n->rb_left;
  2699. }
  2700. }
  2701. return va;
  2702. }
  2703. /**
  2704. * pvm_determine_end_from_reverse - find the highest aligned address
  2705. * of free block below VMALLOC_END
  2706. * @va:
  2707. * in - the VA we start the search(reverse order);
  2708. * out - the VA with the highest aligned end address.
  2709. *
  2710. * Returns: determined end address within vmap_area
  2711. */
  2712. static unsigned long
  2713. pvm_determine_end_from_reverse(struct vmap_area **va, unsigned long align)
  2714. {
  2715. unsigned long vmalloc_end = VMALLOC_END & ~(align - 1);
  2716. unsigned long addr;
  2717. if (likely(*va)) {
  2718. list_for_each_entry_from_reverse((*va),
  2719. &free_vmap_area_list, list) {
  2720. addr = min((*va)->va_end & ~(align - 1), vmalloc_end);
  2721. if ((*va)->va_start < addr)
  2722. return addr;
  2723. }
  2724. }
  2725. return 0;
  2726. }
  2727. /**
  2728. * pcpu_get_vm_areas - allocate vmalloc areas for percpu allocator
  2729. * @offsets: array containing offset of each area
  2730. * @sizes: array containing size of each area
  2731. * @nr_vms: the number of areas to allocate
  2732. * @align: alignment, all entries in @offsets and @sizes must be aligned to this
  2733. *
  2734. * Returns: kmalloc'd vm_struct pointer array pointing to allocated
  2735. * vm_structs on success, %NULL on failure
  2736. *
  2737. * Percpu allocator wants to use congruent vm areas so that it can
  2738. * maintain the offsets among percpu areas. This function allocates
  2739. * congruent vmalloc areas for it with GFP_KERNEL. These areas tend to
  2740. * be scattered pretty far, distance between two areas easily going up
  2741. * to gigabytes. To avoid interacting with regular vmallocs, these
  2742. * areas are allocated from top.
  2743. *
  2744. * Despite its complicated look, this allocator is rather simple. It
  2745. * does everything top-down and scans free blocks from the end looking
  2746. * for matching base. While scanning, if any of the areas do not fit the
  2747. * base address is pulled down to fit the area. Scanning is repeated till
  2748. * all the areas fit and then all necessary data structures are inserted
  2749. * and the result is returned.
  2750. */
  2751. struct vm_struct **pcpu_get_vm_areas(const unsigned long *offsets,
  2752. const size_t *sizes, int nr_vms,
  2753. size_t align)
  2754. {
  2755. const unsigned long vmalloc_start = ALIGN(VMALLOC_START, align);
  2756. const unsigned long vmalloc_end = VMALLOC_END & ~(align - 1);
  2757. struct vmap_area **vas, *va;
  2758. struct vm_struct **vms;
  2759. int area, area2, last_area, term_area;
  2760. unsigned long base, start, size, end, last_end, orig_start, orig_end;
  2761. bool purged = false;
  2762. enum fit_type type;
  2763. /* verify parameters and allocate data structures */
  2764. BUG_ON(offset_in_page(align) || !is_power_of_2(align));
  2765. for (last_area = 0, area = 0; area < nr_vms; area++) {
  2766. start = offsets[area];
  2767. end = start + sizes[area];
  2768. /* is everything aligned properly? */
  2769. BUG_ON(!IS_ALIGNED(offsets[area], align));
  2770. BUG_ON(!IS_ALIGNED(sizes[area], align));
  2771. /* detect the area with the highest address */
  2772. if (start > offsets[last_area])
  2773. last_area = area;
  2774. for (area2 = area + 1; area2 < nr_vms; area2++) {
  2775. unsigned long start2 = offsets[area2];
  2776. unsigned long end2 = start2 + sizes[area2];
  2777. BUG_ON(start2 < end && start < end2);
  2778. }
  2779. }
  2780. last_end = offsets[last_area] + sizes[last_area];
  2781. if (vmalloc_end - vmalloc_start < last_end) {
  2782. WARN_ON(true);
  2783. return NULL;
  2784. }
  2785. vms = kcalloc(nr_vms, sizeof(vms[0]), GFP_KERNEL);
  2786. vas = kcalloc(nr_vms, sizeof(vas[0]), GFP_KERNEL);
  2787. if (!vas || !vms)
  2788. goto err_free2;
  2789. for (area = 0; area < nr_vms; area++) {
  2790. vas[area] = kmem_cache_zalloc(vmap_area_cachep, GFP_KERNEL);
  2791. vms[area] = kzalloc(sizeof(struct vm_struct), GFP_KERNEL);
  2792. if (!vas[area] || !vms[area])
  2793. goto err_free;
  2794. }
  2795. retry:
  2796. spin_lock(&free_vmap_area_lock);
  2797. /* start scanning - we scan from the top, begin with the last area */
  2798. area = term_area = last_area;
  2799. start = offsets[area];
  2800. end = start + sizes[area];
  2801. va = pvm_find_va_enclose_addr(vmalloc_end);
  2802. base = pvm_determine_end_from_reverse(&va, align) - end;
  2803. while (true) {
  2804. /*
  2805. * base might have underflowed, add last_end before
  2806. * comparing.
  2807. */
  2808. if (base + last_end < vmalloc_start + last_end)
  2809. goto overflow;
  2810. /*
  2811. * Fitting base has not been found.
  2812. */
  2813. if (va == NULL)
  2814. goto overflow;
  2815. /*
  2816. * If required width exceeds current VA block, move
  2817. * base downwards and then recheck.
  2818. */
  2819. if (base + end > va->va_end) {
  2820. base = pvm_determine_end_from_reverse(&va, align) - end;
  2821. term_area = area;
  2822. continue;
  2823. }
  2824. /*
  2825. * If this VA does not fit, move base downwards and recheck.
  2826. */
  2827. if (base + start < va->va_start) {
  2828. va = node_to_va(rb_prev(&va->rb_node));
  2829. base = pvm_determine_end_from_reverse(&va, align) - end;
  2830. term_area = area;
  2831. continue;
  2832. }
  2833. /*
  2834. * This area fits, move on to the previous one. If
  2835. * the previous one is the terminal one, we're done.
  2836. */
  2837. area = (area + nr_vms - 1) % nr_vms;
  2838. if (area == term_area)
  2839. break;
  2840. start = offsets[area];
  2841. end = start + sizes[area];
  2842. va = pvm_find_va_enclose_addr(base + end);
  2843. }
  2844. /* we've found a fitting base, insert all va's */
  2845. for (area = 0; area < nr_vms; area++) {
  2846. int ret;
  2847. start = base + offsets[area];
  2848. size = sizes[area];
  2849. va = pvm_find_va_enclose_addr(start);
  2850. if (WARN_ON_ONCE(va == NULL))
  2851. /* It is a BUG(), but trigger recovery instead. */
  2852. goto recovery;
  2853. type = classify_va_fit_type(va, start, size);
  2854. if (WARN_ON_ONCE(type == NOTHING_FIT))
  2855. /* It is a BUG(), but trigger recovery instead. */
  2856. goto recovery;
  2857. ret = adjust_va_to_fit_type(va, start, size, type);
  2858. if (unlikely(ret))
  2859. goto recovery;
  2860. /* Allocated area. */
  2861. va = vas[area];
  2862. va->va_start = start;
  2863. va->va_end = start + size;
  2864. }
  2865. spin_unlock(&free_vmap_area_lock);
  2866. /* populate the kasan shadow space */
  2867. for (area = 0; area < nr_vms; area++) {
  2868. if (kasan_populate_vmalloc(vas[area]->va_start, sizes[area]))
  2869. goto err_free_shadow;
  2870. kasan_unpoison_vmalloc((void *)vas[area]->va_start,
  2871. sizes[area]);
  2872. }
  2873. /* insert all vm's */
  2874. spin_lock(&vmap_area_lock);
  2875. for (area = 0; area < nr_vms; area++) {
  2876. insert_vmap_area(vas[area], &vmap_area_root, &vmap_area_list);
  2877. setup_vmalloc_vm_locked(vms[area], vas[area], VM_ALLOC,
  2878. pcpu_get_vm_areas);
  2879. }
  2880. spin_unlock(&vmap_area_lock);
  2881. kfree(vas);
  2882. return vms;
  2883. recovery:
  2884. /*
  2885. * Remove previously allocated areas. There is no
  2886. * need in removing these areas from the busy tree,
  2887. * because they are inserted only on the final step
  2888. * and when pcpu_get_vm_areas() is success.
  2889. */
  2890. while (area--) {
  2891. orig_start = vas[area]->va_start;
  2892. orig_end = vas[area]->va_end;
  2893. va = merge_or_add_vmap_area(vas[area], &free_vmap_area_root,
  2894. &free_vmap_area_list);
  2895. if (va)
  2896. kasan_release_vmalloc(orig_start, orig_end,
  2897. va->va_start, va->va_end);
  2898. vas[area] = NULL;
  2899. }
  2900. overflow:
  2901. spin_unlock(&free_vmap_area_lock);
  2902. if (!purged) {
  2903. purge_vmap_area_lazy();
  2904. purged = true;
  2905. /* Before "retry", check if we recover. */
  2906. for (area = 0; area < nr_vms; area++) {
  2907. if (vas[area])
  2908. continue;
  2909. vas[area] = kmem_cache_zalloc(
  2910. vmap_area_cachep, GFP_KERNEL);
  2911. if (!vas[area])
  2912. goto err_free;
  2913. }
  2914. goto retry;
  2915. }
  2916. err_free:
  2917. for (area = 0; area < nr_vms; area++) {
  2918. if (vas[area])
  2919. kmem_cache_free(vmap_area_cachep, vas[area]);
  2920. kfree(vms[area]);
  2921. }
  2922. err_free2:
  2923. kfree(vas);
  2924. kfree(vms);
  2925. return NULL;
  2926. err_free_shadow:
  2927. spin_lock(&free_vmap_area_lock);
  2928. /*
  2929. * We release all the vmalloc shadows, even the ones for regions that
  2930. * hadn't been successfully added. This relies on kasan_release_vmalloc
  2931. * being able to tolerate this case.
  2932. */
  2933. for (area = 0; area < nr_vms; area++) {
  2934. orig_start = vas[area]->va_start;
  2935. orig_end = vas[area]->va_end;
  2936. va = merge_or_add_vmap_area(vas[area], &free_vmap_area_root,
  2937. &free_vmap_area_list);
  2938. if (va)
  2939. kasan_release_vmalloc(orig_start, orig_end,
  2940. va->va_start, va->va_end);
  2941. vas[area] = NULL;
  2942. kfree(vms[area]);
  2943. }
  2944. spin_unlock(&free_vmap_area_lock);
  2945. kfree(vas);
  2946. kfree(vms);
  2947. return NULL;
  2948. }
  2949. /**
  2950. * pcpu_free_vm_areas - free vmalloc areas for percpu allocator
  2951. * @vms: vm_struct pointer array returned by pcpu_get_vm_areas()
  2952. * @nr_vms: the number of allocated areas
  2953. *
  2954. * Free vm_structs and the array allocated by pcpu_get_vm_areas().
  2955. */
  2956. void pcpu_free_vm_areas(struct vm_struct **vms, int nr_vms)
  2957. {
  2958. int i;
  2959. for (i = 0; i < nr_vms; i++)
  2960. free_vm_area(vms[i]);
  2961. kfree(vms);
  2962. }
  2963. #endif /* CONFIG_SMP */
  2964. #ifdef CONFIG_PROC_FS
  2965. static void *s_start(struct seq_file *m, loff_t *pos)
  2966. __acquires(&vmap_purge_lock)
  2967. __acquires(&vmap_area_lock)
  2968. {
  2969. mutex_lock(&vmap_purge_lock);
  2970. spin_lock(&vmap_area_lock);
  2971. return seq_list_start(&vmap_area_list, *pos);
  2972. }
  2973. static void *s_next(struct seq_file *m, void *p, loff_t *pos)
  2974. {
  2975. return seq_list_next(p, &vmap_area_list, pos);
  2976. }
  2977. static void s_stop(struct seq_file *m, void *p)
  2978. __releases(&vmap_area_lock)
  2979. __releases(&vmap_purge_lock)
  2980. {
  2981. spin_unlock(&vmap_area_lock);
  2982. mutex_unlock(&vmap_purge_lock);
  2983. }
  2984. static void show_numa_info(struct seq_file *m, struct vm_struct *v)
  2985. {
  2986. if (IS_ENABLED(CONFIG_NUMA)) {
  2987. unsigned int nr, *counters = m->private;
  2988. if (!counters)
  2989. return;
  2990. if (v->flags & VM_UNINITIALIZED)
  2991. return;
  2992. /* Pair with smp_wmb() in clear_vm_uninitialized_flag() */
  2993. smp_rmb();
  2994. memset(counters, 0, nr_node_ids * sizeof(unsigned int));
  2995. for (nr = 0; nr < v->nr_pages; nr++)
  2996. counters[page_to_nid(v->pages[nr])]++;
  2997. for_each_node_state(nr, N_HIGH_MEMORY)
  2998. if (counters[nr])
  2999. seq_printf(m, " N%u=%u", nr, counters[nr]);
  3000. }
  3001. }
  3002. static void show_purge_info(struct seq_file *m)
  3003. {
  3004. struct llist_node *head;
  3005. struct vmap_area *va;
  3006. head = READ_ONCE(vmap_purge_list.first);
  3007. if (head == NULL)
  3008. return;
  3009. llist_for_each_entry(va, head, purge_list) {
  3010. seq_printf(m, "0x%pK-0x%pK %7ld unpurged vm_area\n",
  3011. (void *)va->va_start, (void *)va->va_end,
  3012. va->va_end - va->va_start);
  3013. }
  3014. }
  3015. static int s_show(struct seq_file *m, void *p)
  3016. {
  3017. struct vmap_area *va;
  3018. struct vm_struct *v;
  3019. va = list_entry(p, struct vmap_area, list);
  3020. /*
  3021. * s_show can encounter race with remove_vm_area, !vm on behalf
  3022. * of vmap area is being tear down or vm_map_ram allocation.
  3023. */
  3024. if (!va->vm) {
  3025. seq_printf(m, "0x%pK-0x%pK %7ld vm_map_ram\n",
  3026. (void *)va->va_start, (void *)va->va_end,
  3027. va->va_end - va->va_start);
  3028. return 0;
  3029. }
  3030. v = va->vm;
  3031. seq_printf(m, "0x%pK-0x%pK %7ld",
  3032. v->addr, v->addr + v->size, v->size);
  3033. if (v->caller)
  3034. seq_printf(m, " %pS", v->caller);
  3035. if (v->nr_pages)
  3036. seq_printf(m, " pages=%d", v->nr_pages);
  3037. if (v->phys_addr)
  3038. seq_printf(m, " phys=%pa", &v->phys_addr);
  3039. if (v->flags & VM_IOREMAP)
  3040. seq_puts(m, " ioremap");
  3041. if (v->flags & VM_ALLOC)
  3042. seq_puts(m, " vmalloc");
  3043. if (v->flags & VM_MAP)
  3044. seq_puts(m, " vmap");
  3045. if (v->flags & VM_USERMAP)
  3046. seq_puts(m, " user");
  3047. if (v->flags & VM_DMA_COHERENT)
  3048. seq_puts(m, " dma-coherent");
  3049. if (is_vmalloc_addr(v->pages))
  3050. seq_puts(m, " vpages");
  3051. show_numa_info(m, v);
  3052. trace_android_vh_show_stack_hash(m, v);
  3053. seq_putc(m, '\n');
  3054. /*
  3055. * As a final step, dump "unpurged" areas. Note,
  3056. * that entire "/proc/vmallocinfo" output will not
  3057. * be address sorted, because the purge list is not
  3058. * sorted.
  3059. */
  3060. if (list_is_last(&va->list, &vmap_area_list))
  3061. show_purge_info(m);
  3062. return 0;
  3063. }
  3064. static const struct seq_operations vmalloc_op = {
  3065. .start = s_start,
  3066. .next = s_next,
  3067. .stop = s_stop,
  3068. .show = s_show,
  3069. };
  3070. static int __init proc_vmalloc_init(void)
  3071. {
  3072. if (IS_ENABLED(CONFIG_NUMA))
  3073. proc_create_seq_private("vmallocinfo", 0400, NULL,
  3074. &vmalloc_op,
  3075. nr_node_ids * sizeof(unsigned int), NULL);
  3076. else
  3077. proc_create_seq("vmallocinfo", 0400, NULL, &vmalloc_op);
  3078. return 0;
  3079. }
  3080. module_init(proc_vmalloc_init);
  3081. #endif