percpu.c 96 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845184618471848184918501851185218531854185518561857185818591860186118621863186418651866186718681869187018711872187318741875187618771878187918801881188218831884188518861887188818891890189118921893189418951896189718981899190019011902190319041905190619071908190919101911191219131914191519161917191819191920192119221923192419251926192719281929193019311932193319341935193619371938193919401941194219431944194519461947194819491950195119521953195419551956195719581959196019611962196319641965196619671968196919701971197219731974197519761977197819791980198119821983198419851986198719881989199019911992199319941995199619971998199920002001200220032004200520062007200820092010201120122013201420152016201720182019202020212022202320242025202620272028202920302031203220332034203520362037203820392040204120422043204420452046204720482049205020512052205320542055205620572058205920602061206220632064206520662067206820692070207120722073207420752076207720782079208020812082208320842085208620872088208920902091209220932094209520962097209820992100210121022103210421052106210721082109211021112112211321142115211621172118211921202121212221232124212521262127212821292130213121322133213421352136213721382139214021412142214321442145214621472148214921502151215221532154215521562157215821592160216121622163216421652166216721682169217021712172217321742175217621772178217921802181218221832184218521862187218821892190219121922193219421952196219721982199220022012202220322042205220622072208220922102211221222132214221522162217221822192220222122222223222422252226222722282229223022312232223322342235223622372238223922402241224222432244224522462247224822492250225122522253225422552256225722582259226022612262226322642265226622672268226922702271227222732274227522762277227822792280228122822283228422852286228722882289229022912292229322942295229622972298229923002301230223032304230523062307230823092310231123122313231423152316231723182319232023212322232323242325232623272328232923302331233223332334233523362337233823392340234123422343234423452346234723482349235023512352235323542355235623572358235923602361236223632364236523662367236823692370237123722373237423752376237723782379238023812382238323842385238623872388238923902391239223932394239523962397239823992400240124022403240424052406240724082409241024112412241324142415241624172418241924202421242224232424242524262427242824292430243124322433243424352436243724382439244024412442244324442445244624472448244924502451245224532454245524562457245824592460246124622463246424652466246724682469247024712472247324742475247624772478247924802481248224832484248524862487248824892490249124922493249424952496249724982499250025012502250325042505250625072508250925102511251225132514251525162517251825192520252125222523252425252526252725282529253025312532253325342535253625372538253925402541254225432544254525462547254825492550255125522553255425552556255725582559256025612562256325642565256625672568256925702571257225732574257525762577257825792580258125822583258425852586258725882589259025912592259325942595259625972598259926002601260226032604260526062607260826092610261126122613261426152616261726182619262026212622262326242625262626272628262926302631263226332634263526362637263826392640264126422643264426452646264726482649265026512652265326542655265626572658265926602661266226632664266526662667266826692670267126722673267426752676267726782679268026812682268326842685268626872688268926902691269226932694269526962697269826992700270127022703270427052706270727082709271027112712271327142715271627172718271927202721272227232724272527262727272827292730273127322733273427352736273727382739274027412742274327442745274627472748274927502751275227532754275527562757275827592760276127622763276427652766276727682769277027712772277327742775277627772778277927802781278227832784278527862787278827892790279127922793279427952796279727982799280028012802280328042805280628072808280928102811281228132814281528162817281828192820282128222823282428252826282728282829283028312832283328342835283628372838283928402841284228432844284528462847284828492850285128522853285428552856285728582859286028612862286328642865286628672868286928702871287228732874287528762877287828792880288128822883288428852886288728882889289028912892289328942895289628972898289929002901290229032904290529062907290829092910291129122913291429152916291729182919292029212922292329242925292629272928292929302931293229332934293529362937293829392940294129422943294429452946294729482949295029512952295329542955295629572958295929602961296229632964296529662967296829692970297129722973297429752976297729782979298029812982298329842985298629872988298929902991299229932994299529962997299829993000300130023003300430053006300730083009301030113012301330143015301630173018301930203021302230233024302530263027302830293030303130323033303430353036303730383039304030413042304330443045304630473048304930503051305230533054305530563057305830593060306130623063306430653066306730683069307030713072307330743075307630773078307930803081308230833084308530863087308830893090309130923093309430953096309730983099310031013102310331043105310631073108310931103111311231133114311531163117311831193120312131223123312431253126312731283129313031313132313331343135313631373138313931403141314231433144314531463147314831493150315131523153315431553156315731583159316031613162316331643165316631673168316931703171317231733174317531763177317831793180318131823183
  1. // SPDX-License-Identifier: GPL-2.0-only
  2. /*
  3. * mm/percpu.c - percpu memory allocator
  4. *
  5. * Copyright (C) 2009 SUSE Linux Products GmbH
  6. * Copyright (C) 2009 Tejun Heo <tj@kernel.org>
  7. *
  8. * Copyright (C) 2017 Facebook Inc.
  9. * Copyright (C) 2017 Dennis Zhou <dennis@kernel.org>
  10. *
  11. * The percpu allocator handles both static and dynamic areas. Percpu
  12. * areas are allocated in chunks which are divided into units. There is
  13. * a 1-to-1 mapping for units to possible cpus. These units are grouped
  14. * based on NUMA properties of the machine.
  15. *
  16. * c0 c1 c2
  17. * ------------------- ------------------- ------------
  18. * | u0 | u1 | u2 | u3 | | u0 | u1 | u2 | u3 | | u0 | u1 | u
  19. * ------------------- ...... ------------------- .... ------------
  20. *
  21. * Allocation is done by offsets into a unit's address space. Ie., an
  22. * area of 512 bytes at 6k in c1 occupies 512 bytes at 6k in c1:u0,
  23. * c1:u1, c1:u2, etc. On NUMA machines, the mapping may be non-linear
  24. * and even sparse. Access is handled by configuring percpu base
  25. * registers according to the cpu to unit mappings and offsetting the
  26. * base address using pcpu_unit_size.
  27. *
  28. * There is special consideration for the first chunk which must handle
  29. * the static percpu variables in the kernel image as allocation services
  30. * are not online yet. In short, the first chunk is structured like so:
  31. *
  32. * <Static | [Reserved] | Dynamic>
  33. *
  34. * The static data is copied from the original section managed by the
  35. * linker. The reserved section, if non-zero, primarily manages static
  36. * percpu variables from kernel modules. Finally, the dynamic section
  37. * takes care of normal allocations.
  38. *
  39. * The allocator organizes chunks into lists according to free size and
  40. * memcg-awareness. To make a percpu allocation memcg-aware the __GFP_ACCOUNT
  41. * flag should be passed. All memcg-aware allocations are sharing one set
  42. * of chunks and all unaccounted allocations and allocations performed
  43. * by processes belonging to the root memory cgroup are using the second set.
  44. *
  45. * The allocator tries to allocate from the fullest chunk first. Each chunk
  46. * is managed by a bitmap with metadata blocks. The allocation map is updated
  47. * on every allocation and free to reflect the current state while the boundary
  48. * map is only updated on allocation. Each metadata block contains
  49. * information to help mitigate the need to iterate over large portions
  50. * of the bitmap. The reverse mapping from page to chunk is stored in
  51. * the page's index. Lastly, units are lazily backed and grow in unison.
  52. *
  53. * There is a unique conversion that goes on here between bytes and bits.
  54. * Each bit represents a fragment of size PCPU_MIN_ALLOC_SIZE. The chunk
  55. * tracks the number of pages it is responsible for in nr_pages. Helper
  56. * functions are used to convert from between the bytes, bits, and blocks.
  57. * All hints are managed in bits unless explicitly stated.
  58. *
  59. * To use this allocator, arch code should do the following:
  60. *
  61. * - define __addr_to_pcpu_ptr() and __pcpu_ptr_to_addr() to translate
  62. * regular address to percpu pointer and back if they need to be
  63. * different from the default
  64. *
  65. * - use pcpu_setup_first_chunk() during percpu area initialization to
  66. * setup the first chunk containing the kernel static percpu area
  67. */
  68. #define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
  69. #include <linux/bitmap.h>
  70. #include <linux/memblock.h>
  71. #include <linux/err.h>
  72. #include <linux/lcm.h>
  73. #include <linux/list.h>
  74. #include <linux/log2.h>
  75. #include <linux/mm.h>
  76. #include <linux/module.h>
  77. #include <linux/mutex.h>
  78. #include <linux/percpu.h>
  79. #include <linux/pfn.h>
  80. #include <linux/slab.h>
  81. #include <linux/spinlock.h>
  82. #include <linux/vmalloc.h>
  83. #include <linux/workqueue.h>
  84. #include <linux/kmemleak.h>
  85. #include <linux/sched.h>
  86. #include <linux/sched/mm.h>
  87. #include <linux/memcontrol.h>
  88. #include <asm/cacheflush.h>
  89. #include <asm/sections.h>
  90. #include <asm/tlbflush.h>
  91. #include <asm/io.h>
  92. #define CREATE_TRACE_POINTS
  93. #include <trace/events/percpu.h>
  94. #include "percpu-internal.h"
  95. /* the slots are sorted by free bytes left, 1-31 bytes share the same slot */
  96. #define PCPU_SLOT_BASE_SHIFT 5
  97. /* chunks in slots below this are subject to being sidelined on failed alloc */
  98. #define PCPU_SLOT_FAIL_THRESHOLD 3
  99. #define PCPU_EMPTY_POP_PAGES_LOW 2
  100. #define PCPU_EMPTY_POP_PAGES_HIGH 4
  101. #ifdef CONFIG_SMP
  102. /* default addr <-> pcpu_ptr mapping, override in asm/percpu.h if necessary */
  103. #ifndef __addr_to_pcpu_ptr
  104. #define __addr_to_pcpu_ptr(addr) \
  105. (void __percpu *)((unsigned long)(addr) - \
  106. (unsigned long)pcpu_base_addr + \
  107. (unsigned long)__per_cpu_start)
  108. #endif
  109. #ifndef __pcpu_ptr_to_addr
  110. #define __pcpu_ptr_to_addr(ptr) \
  111. (void __force *)((unsigned long)(ptr) + \
  112. (unsigned long)pcpu_base_addr - \
  113. (unsigned long)__per_cpu_start)
  114. #endif
  115. #else /* CONFIG_SMP */
  116. /* on UP, it's always identity mapped */
  117. #define __addr_to_pcpu_ptr(addr) (void __percpu *)(addr)
  118. #define __pcpu_ptr_to_addr(ptr) (void __force *)(ptr)
  119. #endif /* CONFIG_SMP */
  120. static int pcpu_unit_pages __ro_after_init;
  121. static int pcpu_unit_size __ro_after_init;
  122. static int pcpu_nr_units __ro_after_init;
  123. static int pcpu_atom_size __ro_after_init;
  124. int pcpu_nr_slots __ro_after_init;
  125. static size_t pcpu_chunk_struct_size __ro_after_init;
  126. /* cpus with the lowest and highest unit addresses */
  127. static unsigned int pcpu_low_unit_cpu __ro_after_init;
  128. static unsigned int pcpu_high_unit_cpu __ro_after_init;
  129. /* the address of the first chunk which starts with the kernel static area */
  130. void *pcpu_base_addr __ro_after_init;
  131. EXPORT_SYMBOL_GPL(pcpu_base_addr);
  132. static const int *pcpu_unit_map __ro_after_init; /* cpu -> unit */
  133. const unsigned long *pcpu_unit_offsets __ro_after_init; /* cpu -> unit offset */
  134. /* group information, used for vm allocation */
  135. static int pcpu_nr_groups __ro_after_init;
  136. static const unsigned long *pcpu_group_offsets __ro_after_init;
  137. static const size_t *pcpu_group_sizes __ro_after_init;
  138. /*
  139. * The first chunk which always exists. Note that unlike other
  140. * chunks, this one can be allocated and mapped in several different
  141. * ways and thus often doesn't live in the vmalloc area.
  142. */
  143. struct pcpu_chunk *pcpu_first_chunk __ro_after_init;
  144. /*
  145. * Optional reserved chunk. This chunk reserves part of the first
  146. * chunk and serves it for reserved allocations. When the reserved
  147. * region doesn't exist, the following variable is NULL.
  148. */
  149. struct pcpu_chunk *pcpu_reserved_chunk __ro_after_init;
  150. DEFINE_SPINLOCK(pcpu_lock); /* all internal data structures */
  151. static DEFINE_MUTEX(pcpu_alloc_mutex); /* chunk create/destroy, [de]pop, map ext */
  152. struct list_head *pcpu_chunk_lists __ro_after_init; /* chunk list slots */
  153. /* chunks which need their map areas extended, protected by pcpu_lock */
  154. static LIST_HEAD(pcpu_map_extend_chunks);
  155. /*
  156. * The number of empty populated pages by chunk type, protected by pcpu_lock.
  157. * The reserved chunk doesn't contribute to the count.
  158. */
  159. int pcpu_nr_empty_pop_pages[PCPU_NR_CHUNK_TYPES];
  160. /*
  161. * The number of populated pages in use by the allocator, protected by
  162. * pcpu_lock. This number is kept per a unit per chunk (i.e. when a page gets
  163. * allocated/deallocated, it is allocated/deallocated in all units of a chunk
  164. * and increments/decrements this count by 1).
  165. */
  166. static unsigned long pcpu_nr_populated;
  167. /*
  168. * Balance work is used to populate or destroy chunks asynchronously. We
  169. * try to keep the number of populated free pages between
  170. * PCPU_EMPTY_POP_PAGES_LOW and HIGH for atomic allocations and at most one
  171. * empty chunk.
  172. */
  173. static void pcpu_balance_workfn(struct work_struct *work);
  174. static DECLARE_WORK(pcpu_balance_work, pcpu_balance_workfn);
  175. static bool pcpu_async_enabled __read_mostly;
  176. static bool pcpu_atomic_alloc_failed;
  177. static void pcpu_schedule_balance_work(void)
  178. {
  179. if (pcpu_async_enabled)
  180. schedule_work(&pcpu_balance_work);
  181. }
  182. /**
  183. * pcpu_addr_in_chunk - check if the address is served from this chunk
  184. * @chunk: chunk of interest
  185. * @addr: percpu address
  186. *
  187. * RETURNS:
  188. * True if the address is served from this chunk.
  189. */
  190. static bool pcpu_addr_in_chunk(struct pcpu_chunk *chunk, void *addr)
  191. {
  192. void *start_addr, *end_addr;
  193. if (!chunk)
  194. return false;
  195. start_addr = chunk->base_addr + chunk->start_offset;
  196. end_addr = chunk->base_addr + chunk->nr_pages * PAGE_SIZE -
  197. chunk->end_offset;
  198. return addr >= start_addr && addr < end_addr;
  199. }
  200. static int __pcpu_size_to_slot(int size)
  201. {
  202. int highbit = fls(size); /* size is in bytes */
  203. return max(highbit - PCPU_SLOT_BASE_SHIFT + 2, 1);
  204. }
  205. static int pcpu_size_to_slot(int size)
  206. {
  207. if (size == pcpu_unit_size)
  208. return pcpu_nr_slots - 1;
  209. return __pcpu_size_to_slot(size);
  210. }
  211. static int pcpu_chunk_slot(const struct pcpu_chunk *chunk)
  212. {
  213. const struct pcpu_block_md *chunk_md = &chunk->chunk_md;
  214. if (chunk->free_bytes < PCPU_MIN_ALLOC_SIZE ||
  215. chunk_md->contig_hint == 0)
  216. return 0;
  217. return pcpu_size_to_slot(chunk_md->contig_hint * PCPU_MIN_ALLOC_SIZE);
  218. }
  219. /* set the pointer to a chunk in a page struct */
  220. static void pcpu_set_page_chunk(struct page *page, struct pcpu_chunk *pcpu)
  221. {
  222. page->index = (unsigned long)pcpu;
  223. }
  224. /* obtain pointer to a chunk from a page struct */
  225. static struct pcpu_chunk *pcpu_get_page_chunk(struct page *page)
  226. {
  227. return (struct pcpu_chunk *)page->index;
  228. }
  229. static int __maybe_unused pcpu_page_idx(unsigned int cpu, int page_idx)
  230. {
  231. return pcpu_unit_map[cpu] * pcpu_unit_pages + page_idx;
  232. }
  233. static unsigned long pcpu_unit_page_offset(unsigned int cpu, int page_idx)
  234. {
  235. return pcpu_unit_offsets[cpu] + (page_idx << PAGE_SHIFT);
  236. }
  237. static unsigned long pcpu_chunk_addr(struct pcpu_chunk *chunk,
  238. unsigned int cpu, int page_idx)
  239. {
  240. return (unsigned long)chunk->base_addr +
  241. pcpu_unit_page_offset(cpu, page_idx);
  242. }
  243. /*
  244. * The following are helper functions to help access bitmaps and convert
  245. * between bitmap offsets to address offsets.
  246. */
  247. static unsigned long *pcpu_index_alloc_map(struct pcpu_chunk *chunk, int index)
  248. {
  249. return chunk->alloc_map +
  250. (index * PCPU_BITMAP_BLOCK_BITS / BITS_PER_LONG);
  251. }
  252. static unsigned long pcpu_off_to_block_index(int off)
  253. {
  254. return off / PCPU_BITMAP_BLOCK_BITS;
  255. }
  256. static unsigned long pcpu_off_to_block_off(int off)
  257. {
  258. return off & (PCPU_BITMAP_BLOCK_BITS - 1);
  259. }
  260. static unsigned long pcpu_block_off_to_off(int index, int off)
  261. {
  262. return index * PCPU_BITMAP_BLOCK_BITS + off;
  263. }
  264. /*
  265. * pcpu_next_hint - determine which hint to use
  266. * @block: block of interest
  267. * @alloc_bits: size of allocation
  268. *
  269. * This determines if we should scan based on the scan_hint or first_free.
  270. * In general, we want to scan from first_free to fulfill allocations by
  271. * first fit. However, if we know a scan_hint at position scan_hint_start
  272. * cannot fulfill an allocation, we can begin scanning from there knowing
  273. * the contig_hint will be our fallback.
  274. */
  275. static int pcpu_next_hint(struct pcpu_block_md *block, int alloc_bits)
  276. {
  277. /*
  278. * The three conditions below determine if we can skip past the
  279. * scan_hint. First, does the scan hint exist. Second, is the
  280. * contig_hint after the scan_hint (possibly not true iff
  281. * contig_hint == scan_hint). Third, is the allocation request
  282. * larger than the scan_hint.
  283. */
  284. if (block->scan_hint &&
  285. block->contig_hint_start > block->scan_hint_start &&
  286. alloc_bits > block->scan_hint)
  287. return block->scan_hint_start + block->scan_hint;
  288. return block->first_free;
  289. }
  290. /**
  291. * pcpu_next_md_free_region - finds the next hint free area
  292. * @chunk: chunk of interest
  293. * @bit_off: chunk offset
  294. * @bits: size of free area
  295. *
  296. * Helper function for pcpu_for_each_md_free_region. It checks
  297. * block->contig_hint and performs aggregation across blocks to find the
  298. * next hint. It modifies bit_off and bits in-place to be consumed in the
  299. * loop.
  300. */
  301. static void pcpu_next_md_free_region(struct pcpu_chunk *chunk, int *bit_off,
  302. int *bits)
  303. {
  304. int i = pcpu_off_to_block_index(*bit_off);
  305. int block_off = pcpu_off_to_block_off(*bit_off);
  306. struct pcpu_block_md *block;
  307. *bits = 0;
  308. for (block = chunk->md_blocks + i; i < pcpu_chunk_nr_blocks(chunk);
  309. block++, i++) {
  310. /* handles contig area across blocks */
  311. if (*bits) {
  312. *bits += block->left_free;
  313. if (block->left_free == PCPU_BITMAP_BLOCK_BITS)
  314. continue;
  315. return;
  316. }
  317. /*
  318. * This checks three things. First is there a contig_hint to
  319. * check. Second, have we checked this hint before by
  320. * comparing the block_off. Third, is this the same as the
  321. * right contig hint. In the last case, it spills over into
  322. * the next block and should be handled by the contig area
  323. * across blocks code.
  324. */
  325. *bits = block->contig_hint;
  326. if (*bits && block->contig_hint_start >= block_off &&
  327. *bits + block->contig_hint_start < PCPU_BITMAP_BLOCK_BITS) {
  328. *bit_off = pcpu_block_off_to_off(i,
  329. block->contig_hint_start);
  330. return;
  331. }
  332. /* reset to satisfy the second predicate above */
  333. block_off = 0;
  334. *bits = block->right_free;
  335. *bit_off = (i + 1) * PCPU_BITMAP_BLOCK_BITS - block->right_free;
  336. }
  337. }
  338. /**
  339. * pcpu_next_fit_region - finds fit areas for a given allocation request
  340. * @chunk: chunk of interest
  341. * @alloc_bits: size of allocation
  342. * @align: alignment of area (max PAGE_SIZE)
  343. * @bit_off: chunk offset
  344. * @bits: size of free area
  345. *
  346. * Finds the next free region that is viable for use with a given size and
  347. * alignment. This only returns if there is a valid area to be used for this
  348. * allocation. block->first_free is returned if the allocation request fits
  349. * within the block to see if the request can be fulfilled prior to the contig
  350. * hint.
  351. */
  352. static void pcpu_next_fit_region(struct pcpu_chunk *chunk, int alloc_bits,
  353. int align, int *bit_off, int *bits)
  354. {
  355. int i = pcpu_off_to_block_index(*bit_off);
  356. int block_off = pcpu_off_to_block_off(*bit_off);
  357. struct pcpu_block_md *block;
  358. *bits = 0;
  359. for (block = chunk->md_blocks + i; i < pcpu_chunk_nr_blocks(chunk);
  360. block++, i++) {
  361. /* handles contig area across blocks */
  362. if (*bits) {
  363. *bits += block->left_free;
  364. if (*bits >= alloc_bits)
  365. return;
  366. if (block->left_free == PCPU_BITMAP_BLOCK_BITS)
  367. continue;
  368. }
  369. /* check block->contig_hint */
  370. *bits = ALIGN(block->contig_hint_start, align) -
  371. block->contig_hint_start;
  372. /*
  373. * This uses the block offset to determine if this has been
  374. * checked in the prior iteration.
  375. */
  376. if (block->contig_hint &&
  377. block->contig_hint_start >= block_off &&
  378. block->contig_hint >= *bits + alloc_bits) {
  379. int start = pcpu_next_hint(block, alloc_bits);
  380. *bits += alloc_bits + block->contig_hint_start -
  381. start;
  382. *bit_off = pcpu_block_off_to_off(i, start);
  383. return;
  384. }
  385. /* reset to satisfy the second predicate above */
  386. block_off = 0;
  387. *bit_off = ALIGN(PCPU_BITMAP_BLOCK_BITS - block->right_free,
  388. align);
  389. *bits = PCPU_BITMAP_BLOCK_BITS - *bit_off;
  390. *bit_off = pcpu_block_off_to_off(i, *bit_off);
  391. if (*bits >= alloc_bits)
  392. return;
  393. }
  394. /* no valid offsets were found - fail condition */
  395. *bit_off = pcpu_chunk_map_bits(chunk);
  396. }
  397. /*
  398. * Metadata free area iterators. These perform aggregation of free areas
  399. * based on the metadata blocks and return the offset @bit_off and size in
  400. * bits of the free area @bits. pcpu_for_each_fit_region only returns when
  401. * a fit is found for the allocation request.
  402. */
  403. #define pcpu_for_each_md_free_region(chunk, bit_off, bits) \
  404. for (pcpu_next_md_free_region((chunk), &(bit_off), &(bits)); \
  405. (bit_off) < pcpu_chunk_map_bits((chunk)); \
  406. (bit_off) += (bits) + 1, \
  407. pcpu_next_md_free_region((chunk), &(bit_off), &(bits)))
  408. #define pcpu_for_each_fit_region(chunk, alloc_bits, align, bit_off, bits) \
  409. for (pcpu_next_fit_region((chunk), (alloc_bits), (align), &(bit_off), \
  410. &(bits)); \
  411. (bit_off) < pcpu_chunk_map_bits((chunk)); \
  412. (bit_off) += (bits), \
  413. pcpu_next_fit_region((chunk), (alloc_bits), (align), &(bit_off), \
  414. &(bits)))
  415. /**
  416. * pcpu_mem_zalloc - allocate memory
  417. * @size: bytes to allocate
  418. * @gfp: allocation flags
  419. *
  420. * Allocate @size bytes. If @size is smaller than PAGE_SIZE,
  421. * kzalloc() is used; otherwise, the equivalent of vzalloc() is used.
  422. * This is to facilitate passing through whitelisted flags. The
  423. * returned memory is always zeroed.
  424. *
  425. * RETURNS:
  426. * Pointer to the allocated area on success, NULL on failure.
  427. */
  428. static void *pcpu_mem_zalloc(size_t size, gfp_t gfp)
  429. {
  430. if (WARN_ON_ONCE(!slab_is_available()))
  431. return NULL;
  432. if (size <= PAGE_SIZE)
  433. return kzalloc(size, gfp);
  434. else
  435. return __vmalloc(size, gfp | __GFP_ZERO);
  436. }
  437. /**
  438. * pcpu_mem_free - free memory
  439. * @ptr: memory to free
  440. *
  441. * Free @ptr. @ptr should have been allocated using pcpu_mem_zalloc().
  442. */
  443. static void pcpu_mem_free(void *ptr)
  444. {
  445. kvfree(ptr);
  446. }
  447. static void __pcpu_chunk_move(struct pcpu_chunk *chunk, int slot,
  448. bool move_front)
  449. {
  450. if (chunk != pcpu_reserved_chunk) {
  451. struct list_head *pcpu_slot;
  452. pcpu_slot = pcpu_chunk_list(pcpu_chunk_type(chunk));
  453. if (move_front)
  454. list_move(&chunk->list, &pcpu_slot[slot]);
  455. else
  456. list_move_tail(&chunk->list, &pcpu_slot[slot]);
  457. }
  458. }
  459. static void pcpu_chunk_move(struct pcpu_chunk *chunk, int slot)
  460. {
  461. __pcpu_chunk_move(chunk, slot, true);
  462. }
  463. /**
  464. * pcpu_chunk_relocate - put chunk in the appropriate chunk slot
  465. * @chunk: chunk of interest
  466. * @oslot: the previous slot it was on
  467. *
  468. * This function is called after an allocation or free changed @chunk.
  469. * New slot according to the changed state is determined and @chunk is
  470. * moved to the slot. Note that the reserved chunk is never put on
  471. * chunk slots.
  472. *
  473. * CONTEXT:
  474. * pcpu_lock.
  475. */
  476. static void pcpu_chunk_relocate(struct pcpu_chunk *chunk, int oslot)
  477. {
  478. int nslot = pcpu_chunk_slot(chunk);
  479. if (oslot != nslot)
  480. __pcpu_chunk_move(chunk, nslot, oslot < nslot);
  481. }
  482. /*
  483. * pcpu_update_empty_pages - update empty page counters
  484. * @chunk: chunk of interest
  485. * @nr: nr of empty pages
  486. *
  487. * This is used to keep track of the empty pages now based on the premise
  488. * a md_block covers a page. The hint update functions recognize if a block
  489. * is made full or broken to calculate deltas for keeping track of free pages.
  490. */
  491. static inline void pcpu_update_empty_pages(struct pcpu_chunk *chunk, int nr)
  492. {
  493. chunk->nr_empty_pop_pages += nr;
  494. if (chunk != pcpu_reserved_chunk)
  495. pcpu_nr_empty_pop_pages[pcpu_chunk_type(chunk)] += nr;
  496. }
  497. /*
  498. * pcpu_region_overlap - determines if two regions overlap
  499. * @a: start of first region, inclusive
  500. * @b: end of first region, exclusive
  501. * @x: start of second region, inclusive
  502. * @y: end of second region, exclusive
  503. *
  504. * This is used to determine if the hint region [a, b) overlaps with the
  505. * allocated region [x, y).
  506. */
  507. static inline bool pcpu_region_overlap(int a, int b, int x, int y)
  508. {
  509. return (a < y) && (x < b);
  510. }
  511. /**
  512. * pcpu_block_update - updates a block given a free area
  513. * @block: block of interest
  514. * @start: start offset in block
  515. * @end: end offset in block
  516. *
  517. * Updates a block given a known free area. The region [start, end) is
  518. * expected to be the entirety of the free area within a block. Chooses
  519. * the best starting offset if the contig hints are equal.
  520. */
  521. static void pcpu_block_update(struct pcpu_block_md *block, int start, int end)
  522. {
  523. int contig = end - start;
  524. block->first_free = min(block->first_free, start);
  525. if (start == 0)
  526. block->left_free = contig;
  527. if (end == block->nr_bits)
  528. block->right_free = contig;
  529. if (contig > block->contig_hint) {
  530. /* promote the old contig_hint to be the new scan_hint */
  531. if (start > block->contig_hint_start) {
  532. if (block->contig_hint > block->scan_hint) {
  533. block->scan_hint_start =
  534. block->contig_hint_start;
  535. block->scan_hint = block->contig_hint;
  536. } else if (start < block->scan_hint_start) {
  537. /*
  538. * The old contig_hint == scan_hint. But, the
  539. * new contig is larger so hold the invariant
  540. * scan_hint_start < contig_hint_start.
  541. */
  542. block->scan_hint = 0;
  543. }
  544. } else {
  545. block->scan_hint = 0;
  546. }
  547. block->contig_hint_start = start;
  548. block->contig_hint = contig;
  549. } else if (contig == block->contig_hint) {
  550. if (block->contig_hint_start &&
  551. (!start ||
  552. __ffs(start) > __ffs(block->contig_hint_start))) {
  553. /* start has a better alignment so use it */
  554. block->contig_hint_start = start;
  555. if (start < block->scan_hint_start &&
  556. block->contig_hint > block->scan_hint)
  557. block->scan_hint = 0;
  558. } else if (start > block->scan_hint_start ||
  559. block->contig_hint > block->scan_hint) {
  560. /*
  561. * Knowing contig == contig_hint, update the scan_hint
  562. * if it is farther than or larger than the current
  563. * scan_hint.
  564. */
  565. block->scan_hint_start = start;
  566. block->scan_hint = contig;
  567. }
  568. } else {
  569. /*
  570. * The region is smaller than the contig_hint. So only update
  571. * the scan_hint if it is larger than or equal and farther than
  572. * the current scan_hint.
  573. */
  574. if ((start < block->contig_hint_start &&
  575. (contig > block->scan_hint ||
  576. (contig == block->scan_hint &&
  577. start > block->scan_hint_start)))) {
  578. block->scan_hint_start = start;
  579. block->scan_hint = contig;
  580. }
  581. }
  582. }
  583. /*
  584. * pcpu_block_update_scan - update a block given a free area from a scan
  585. * @chunk: chunk of interest
  586. * @bit_off: chunk offset
  587. * @bits: size of free area
  588. *
  589. * Finding the final allocation spot first goes through pcpu_find_block_fit()
  590. * to find a block that can hold the allocation and then pcpu_alloc_area()
  591. * where a scan is used. When allocations require specific alignments,
  592. * we can inadvertently create holes which will not be seen in the alloc
  593. * or free paths.
  594. *
  595. * This takes a given free area hole and updates a block as it may change the
  596. * scan_hint. We need to scan backwards to ensure we don't miss free bits
  597. * from alignment.
  598. */
  599. static void pcpu_block_update_scan(struct pcpu_chunk *chunk, int bit_off,
  600. int bits)
  601. {
  602. int s_off = pcpu_off_to_block_off(bit_off);
  603. int e_off = s_off + bits;
  604. int s_index, l_bit;
  605. struct pcpu_block_md *block;
  606. if (e_off > PCPU_BITMAP_BLOCK_BITS)
  607. return;
  608. s_index = pcpu_off_to_block_index(bit_off);
  609. block = chunk->md_blocks + s_index;
  610. /* scan backwards in case of alignment skipping free bits */
  611. l_bit = find_last_bit(pcpu_index_alloc_map(chunk, s_index), s_off);
  612. s_off = (s_off == l_bit) ? 0 : l_bit + 1;
  613. pcpu_block_update(block, s_off, e_off);
  614. }
  615. /**
  616. * pcpu_chunk_refresh_hint - updates metadata about a chunk
  617. * @chunk: chunk of interest
  618. * @full_scan: if we should scan from the beginning
  619. *
  620. * Iterates over the metadata blocks to find the largest contig area.
  621. * A full scan can be avoided on the allocation path as this is triggered
  622. * if we broke the contig_hint. In doing so, the scan_hint will be before
  623. * the contig_hint or after if the scan_hint == contig_hint. This cannot
  624. * be prevented on freeing as we want to find the largest area possibly
  625. * spanning blocks.
  626. */
  627. static void pcpu_chunk_refresh_hint(struct pcpu_chunk *chunk, bool full_scan)
  628. {
  629. struct pcpu_block_md *chunk_md = &chunk->chunk_md;
  630. int bit_off, bits;
  631. /* promote scan_hint to contig_hint */
  632. if (!full_scan && chunk_md->scan_hint) {
  633. bit_off = chunk_md->scan_hint_start + chunk_md->scan_hint;
  634. chunk_md->contig_hint_start = chunk_md->scan_hint_start;
  635. chunk_md->contig_hint = chunk_md->scan_hint;
  636. chunk_md->scan_hint = 0;
  637. } else {
  638. bit_off = chunk_md->first_free;
  639. chunk_md->contig_hint = 0;
  640. }
  641. bits = 0;
  642. pcpu_for_each_md_free_region(chunk, bit_off, bits)
  643. pcpu_block_update(chunk_md, bit_off, bit_off + bits);
  644. }
  645. /**
  646. * pcpu_block_refresh_hint
  647. * @chunk: chunk of interest
  648. * @index: index of the metadata block
  649. *
  650. * Scans over the block beginning at first_free and updates the block
  651. * metadata accordingly.
  652. */
  653. static void pcpu_block_refresh_hint(struct pcpu_chunk *chunk, int index)
  654. {
  655. struct pcpu_block_md *block = chunk->md_blocks + index;
  656. unsigned long *alloc_map = pcpu_index_alloc_map(chunk, index);
  657. unsigned int rs, re, start; /* region start, region end */
  658. /* promote scan_hint to contig_hint */
  659. if (block->scan_hint) {
  660. start = block->scan_hint_start + block->scan_hint;
  661. block->contig_hint_start = block->scan_hint_start;
  662. block->contig_hint = block->scan_hint;
  663. block->scan_hint = 0;
  664. } else {
  665. start = block->first_free;
  666. block->contig_hint = 0;
  667. }
  668. block->right_free = 0;
  669. /* iterate over free areas and update the contig hints */
  670. bitmap_for_each_clear_region(alloc_map, rs, re, start,
  671. PCPU_BITMAP_BLOCK_BITS)
  672. pcpu_block_update(block, rs, re);
  673. }
  674. /**
  675. * pcpu_block_update_hint_alloc - update hint on allocation path
  676. * @chunk: chunk of interest
  677. * @bit_off: chunk offset
  678. * @bits: size of request
  679. *
  680. * Updates metadata for the allocation path. The metadata only has to be
  681. * refreshed by a full scan iff the chunk's contig hint is broken. Block level
  682. * scans are required if the block's contig hint is broken.
  683. */
  684. static void pcpu_block_update_hint_alloc(struct pcpu_chunk *chunk, int bit_off,
  685. int bits)
  686. {
  687. struct pcpu_block_md *chunk_md = &chunk->chunk_md;
  688. int nr_empty_pages = 0;
  689. struct pcpu_block_md *s_block, *e_block, *block;
  690. int s_index, e_index; /* block indexes of the freed allocation */
  691. int s_off, e_off; /* block offsets of the freed allocation */
  692. /*
  693. * Calculate per block offsets.
  694. * The calculation uses an inclusive range, but the resulting offsets
  695. * are [start, end). e_index always points to the last block in the
  696. * range.
  697. */
  698. s_index = pcpu_off_to_block_index(bit_off);
  699. e_index = pcpu_off_to_block_index(bit_off + bits - 1);
  700. s_off = pcpu_off_to_block_off(bit_off);
  701. e_off = pcpu_off_to_block_off(bit_off + bits - 1) + 1;
  702. s_block = chunk->md_blocks + s_index;
  703. e_block = chunk->md_blocks + e_index;
  704. /*
  705. * Update s_block.
  706. * block->first_free must be updated if the allocation takes its place.
  707. * If the allocation breaks the contig_hint, a scan is required to
  708. * restore this hint.
  709. */
  710. if (s_block->contig_hint == PCPU_BITMAP_BLOCK_BITS)
  711. nr_empty_pages++;
  712. if (s_off == s_block->first_free)
  713. s_block->first_free = find_next_zero_bit(
  714. pcpu_index_alloc_map(chunk, s_index),
  715. PCPU_BITMAP_BLOCK_BITS,
  716. s_off + bits);
  717. if (pcpu_region_overlap(s_block->scan_hint_start,
  718. s_block->scan_hint_start + s_block->scan_hint,
  719. s_off,
  720. s_off + bits))
  721. s_block->scan_hint = 0;
  722. if (pcpu_region_overlap(s_block->contig_hint_start,
  723. s_block->contig_hint_start +
  724. s_block->contig_hint,
  725. s_off,
  726. s_off + bits)) {
  727. /* block contig hint is broken - scan to fix it */
  728. if (!s_off)
  729. s_block->left_free = 0;
  730. pcpu_block_refresh_hint(chunk, s_index);
  731. } else {
  732. /* update left and right contig manually */
  733. s_block->left_free = min(s_block->left_free, s_off);
  734. if (s_index == e_index)
  735. s_block->right_free = min_t(int, s_block->right_free,
  736. PCPU_BITMAP_BLOCK_BITS - e_off);
  737. else
  738. s_block->right_free = 0;
  739. }
  740. /*
  741. * Update e_block.
  742. */
  743. if (s_index != e_index) {
  744. if (e_block->contig_hint == PCPU_BITMAP_BLOCK_BITS)
  745. nr_empty_pages++;
  746. /*
  747. * When the allocation is across blocks, the end is along
  748. * the left part of the e_block.
  749. */
  750. e_block->first_free = find_next_zero_bit(
  751. pcpu_index_alloc_map(chunk, e_index),
  752. PCPU_BITMAP_BLOCK_BITS, e_off);
  753. if (e_off == PCPU_BITMAP_BLOCK_BITS) {
  754. /* reset the block */
  755. e_block++;
  756. } else {
  757. if (e_off > e_block->scan_hint_start)
  758. e_block->scan_hint = 0;
  759. e_block->left_free = 0;
  760. if (e_off > e_block->contig_hint_start) {
  761. /* contig hint is broken - scan to fix it */
  762. pcpu_block_refresh_hint(chunk, e_index);
  763. } else {
  764. e_block->right_free =
  765. min_t(int, e_block->right_free,
  766. PCPU_BITMAP_BLOCK_BITS - e_off);
  767. }
  768. }
  769. /* update in-between md_blocks */
  770. nr_empty_pages += (e_index - s_index - 1);
  771. for (block = s_block + 1; block < e_block; block++) {
  772. block->scan_hint = 0;
  773. block->contig_hint = 0;
  774. block->left_free = 0;
  775. block->right_free = 0;
  776. }
  777. }
  778. if (nr_empty_pages)
  779. pcpu_update_empty_pages(chunk, -nr_empty_pages);
  780. if (pcpu_region_overlap(chunk_md->scan_hint_start,
  781. chunk_md->scan_hint_start +
  782. chunk_md->scan_hint,
  783. bit_off,
  784. bit_off + bits))
  785. chunk_md->scan_hint = 0;
  786. /*
  787. * The only time a full chunk scan is required is if the chunk
  788. * contig hint is broken. Otherwise, it means a smaller space
  789. * was used and therefore the chunk contig hint is still correct.
  790. */
  791. if (pcpu_region_overlap(chunk_md->contig_hint_start,
  792. chunk_md->contig_hint_start +
  793. chunk_md->contig_hint,
  794. bit_off,
  795. bit_off + bits))
  796. pcpu_chunk_refresh_hint(chunk, false);
  797. }
  798. /**
  799. * pcpu_block_update_hint_free - updates the block hints on the free path
  800. * @chunk: chunk of interest
  801. * @bit_off: chunk offset
  802. * @bits: size of request
  803. *
  804. * Updates metadata for the allocation path. This avoids a blind block
  805. * refresh by making use of the block contig hints. If this fails, it scans
  806. * forward and backward to determine the extent of the free area. This is
  807. * capped at the boundary of blocks.
  808. *
  809. * A chunk update is triggered if a page becomes free, a block becomes free,
  810. * or the free spans across blocks. This tradeoff is to minimize iterating
  811. * over the block metadata to update chunk_md->contig_hint.
  812. * chunk_md->contig_hint may be off by up to a page, but it will never be more
  813. * than the available space. If the contig hint is contained in one block, it
  814. * will be accurate.
  815. */
  816. static void pcpu_block_update_hint_free(struct pcpu_chunk *chunk, int bit_off,
  817. int bits)
  818. {
  819. int nr_empty_pages = 0;
  820. struct pcpu_block_md *s_block, *e_block, *block;
  821. int s_index, e_index; /* block indexes of the freed allocation */
  822. int s_off, e_off; /* block offsets of the freed allocation */
  823. int start, end; /* start and end of the whole free area */
  824. /*
  825. * Calculate per block offsets.
  826. * The calculation uses an inclusive range, but the resulting offsets
  827. * are [start, end). e_index always points to the last block in the
  828. * range.
  829. */
  830. s_index = pcpu_off_to_block_index(bit_off);
  831. e_index = pcpu_off_to_block_index(bit_off + bits - 1);
  832. s_off = pcpu_off_to_block_off(bit_off);
  833. e_off = pcpu_off_to_block_off(bit_off + bits - 1) + 1;
  834. s_block = chunk->md_blocks + s_index;
  835. e_block = chunk->md_blocks + e_index;
  836. /*
  837. * Check if the freed area aligns with the block->contig_hint.
  838. * If it does, then the scan to find the beginning/end of the
  839. * larger free area can be avoided.
  840. *
  841. * start and end refer to beginning and end of the free area
  842. * within each their respective blocks. This is not necessarily
  843. * the entire free area as it may span blocks past the beginning
  844. * or end of the block.
  845. */
  846. start = s_off;
  847. if (s_off == s_block->contig_hint + s_block->contig_hint_start) {
  848. start = s_block->contig_hint_start;
  849. } else {
  850. /*
  851. * Scan backwards to find the extent of the free area.
  852. * find_last_bit returns the starting bit, so if the start bit
  853. * is returned, that means there was no last bit and the
  854. * remainder of the chunk is free.
  855. */
  856. int l_bit = find_last_bit(pcpu_index_alloc_map(chunk, s_index),
  857. start);
  858. start = (start == l_bit) ? 0 : l_bit + 1;
  859. }
  860. end = e_off;
  861. if (e_off == e_block->contig_hint_start)
  862. end = e_block->contig_hint_start + e_block->contig_hint;
  863. else
  864. end = find_next_bit(pcpu_index_alloc_map(chunk, e_index),
  865. PCPU_BITMAP_BLOCK_BITS, end);
  866. /* update s_block */
  867. e_off = (s_index == e_index) ? end : PCPU_BITMAP_BLOCK_BITS;
  868. if (!start && e_off == PCPU_BITMAP_BLOCK_BITS)
  869. nr_empty_pages++;
  870. pcpu_block_update(s_block, start, e_off);
  871. /* freeing in the same block */
  872. if (s_index != e_index) {
  873. /* update e_block */
  874. if (end == PCPU_BITMAP_BLOCK_BITS)
  875. nr_empty_pages++;
  876. pcpu_block_update(e_block, 0, end);
  877. /* reset md_blocks in the middle */
  878. nr_empty_pages += (e_index - s_index - 1);
  879. for (block = s_block + 1; block < e_block; block++) {
  880. block->first_free = 0;
  881. block->scan_hint = 0;
  882. block->contig_hint_start = 0;
  883. block->contig_hint = PCPU_BITMAP_BLOCK_BITS;
  884. block->left_free = PCPU_BITMAP_BLOCK_BITS;
  885. block->right_free = PCPU_BITMAP_BLOCK_BITS;
  886. }
  887. }
  888. if (nr_empty_pages)
  889. pcpu_update_empty_pages(chunk, nr_empty_pages);
  890. /*
  891. * Refresh chunk metadata when the free makes a block free or spans
  892. * across blocks. The contig_hint may be off by up to a page, but if
  893. * the contig_hint is contained in a block, it will be accurate with
  894. * the else condition below.
  895. */
  896. if (((end - start) >= PCPU_BITMAP_BLOCK_BITS) || s_index != e_index)
  897. pcpu_chunk_refresh_hint(chunk, true);
  898. else
  899. pcpu_block_update(&chunk->chunk_md,
  900. pcpu_block_off_to_off(s_index, start),
  901. end);
  902. }
  903. /**
  904. * pcpu_is_populated - determines if the region is populated
  905. * @chunk: chunk of interest
  906. * @bit_off: chunk offset
  907. * @bits: size of area
  908. * @next_off: return value for the next offset to start searching
  909. *
  910. * For atomic allocations, check if the backing pages are populated.
  911. *
  912. * RETURNS:
  913. * Bool if the backing pages are populated.
  914. * next_index is to skip over unpopulated blocks in pcpu_find_block_fit.
  915. */
  916. static bool pcpu_is_populated(struct pcpu_chunk *chunk, int bit_off, int bits,
  917. int *next_off)
  918. {
  919. unsigned int page_start, page_end, rs, re;
  920. page_start = PFN_DOWN(bit_off * PCPU_MIN_ALLOC_SIZE);
  921. page_end = PFN_UP((bit_off + bits) * PCPU_MIN_ALLOC_SIZE);
  922. rs = page_start;
  923. bitmap_next_clear_region(chunk->populated, &rs, &re, page_end);
  924. if (rs >= page_end)
  925. return true;
  926. *next_off = re * PAGE_SIZE / PCPU_MIN_ALLOC_SIZE;
  927. return false;
  928. }
  929. /**
  930. * pcpu_find_block_fit - finds the block index to start searching
  931. * @chunk: chunk of interest
  932. * @alloc_bits: size of request in allocation units
  933. * @align: alignment of area (max PAGE_SIZE bytes)
  934. * @pop_only: use populated regions only
  935. *
  936. * Given a chunk and an allocation spec, find the offset to begin searching
  937. * for a free region. This iterates over the bitmap metadata blocks to
  938. * find an offset that will be guaranteed to fit the requirements. It is
  939. * not quite first fit as if the allocation does not fit in the contig hint
  940. * of a block or chunk, it is skipped. This errs on the side of caution
  941. * to prevent excess iteration. Poor alignment can cause the allocator to
  942. * skip over blocks and chunks that have valid free areas.
  943. *
  944. * RETURNS:
  945. * The offset in the bitmap to begin searching.
  946. * -1 if no offset is found.
  947. */
  948. static int pcpu_find_block_fit(struct pcpu_chunk *chunk, int alloc_bits,
  949. size_t align, bool pop_only)
  950. {
  951. struct pcpu_block_md *chunk_md = &chunk->chunk_md;
  952. int bit_off, bits, next_off;
  953. /*
  954. * Check to see if the allocation can fit in the chunk's contig hint.
  955. * This is an optimization to prevent scanning by assuming if it
  956. * cannot fit in the global hint, there is memory pressure and creating
  957. * a new chunk would happen soon.
  958. */
  959. bit_off = ALIGN(chunk_md->contig_hint_start, align) -
  960. chunk_md->contig_hint_start;
  961. if (bit_off + alloc_bits > chunk_md->contig_hint)
  962. return -1;
  963. bit_off = pcpu_next_hint(chunk_md, alloc_bits);
  964. bits = 0;
  965. pcpu_for_each_fit_region(chunk, alloc_bits, align, bit_off, bits) {
  966. if (!pop_only || pcpu_is_populated(chunk, bit_off, bits,
  967. &next_off))
  968. break;
  969. bit_off = next_off;
  970. bits = 0;
  971. }
  972. if (bit_off == pcpu_chunk_map_bits(chunk))
  973. return -1;
  974. return bit_off;
  975. }
  976. /*
  977. * pcpu_find_zero_area - modified from bitmap_find_next_zero_area_off()
  978. * @map: the address to base the search on
  979. * @size: the bitmap size in bits
  980. * @start: the bitnumber to start searching at
  981. * @nr: the number of zeroed bits we're looking for
  982. * @align_mask: alignment mask for zero area
  983. * @largest_off: offset of the largest area skipped
  984. * @largest_bits: size of the largest area skipped
  985. *
  986. * The @align_mask should be one less than a power of 2.
  987. *
  988. * This is a modified version of bitmap_find_next_zero_area_off() to remember
  989. * the largest area that was skipped. This is imperfect, but in general is
  990. * good enough. The largest remembered region is the largest failed region
  991. * seen. This does not include anything we possibly skipped due to alignment.
  992. * pcpu_block_update_scan() does scan backwards to try and recover what was
  993. * lost to alignment. While this can cause scanning to miss earlier possible
  994. * free areas, smaller allocations will eventually fill those holes.
  995. */
  996. static unsigned long pcpu_find_zero_area(unsigned long *map,
  997. unsigned long size,
  998. unsigned long start,
  999. unsigned long nr,
  1000. unsigned long align_mask,
  1001. unsigned long *largest_off,
  1002. unsigned long *largest_bits)
  1003. {
  1004. unsigned long index, end, i, area_off, area_bits;
  1005. again:
  1006. index = find_next_zero_bit(map, size, start);
  1007. /* Align allocation */
  1008. index = __ALIGN_MASK(index, align_mask);
  1009. area_off = index;
  1010. end = index + nr;
  1011. if (end > size)
  1012. return end;
  1013. i = find_next_bit(map, end, index);
  1014. if (i < end) {
  1015. area_bits = i - area_off;
  1016. /* remember largest unused area with best alignment */
  1017. if (area_bits > *largest_bits ||
  1018. (area_bits == *largest_bits && *largest_off &&
  1019. (!area_off || __ffs(area_off) > __ffs(*largest_off)))) {
  1020. *largest_off = area_off;
  1021. *largest_bits = area_bits;
  1022. }
  1023. start = i + 1;
  1024. goto again;
  1025. }
  1026. return index;
  1027. }
  1028. /**
  1029. * pcpu_alloc_area - allocates an area from a pcpu_chunk
  1030. * @chunk: chunk of interest
  1031. * @alloc_bits: size of request in allocation units
  1032. * @align: alignment of area (max PAGE_SIZE)
  1033. * @start: bit_off to start searching
  1034. *
  1035. * This function takes in a @start offset to begin searching to fit an
  1036. * allocation of @alloc_bits with alignment @align. It needs to scan
  1037. * the allocation map because if it fits within the block's contig hint,
  1038. * @start will be block->first_free. This is an attempt to fill the
  1039. * allocation prior to breaking the contig hint. The allocation and
  1040. * boundary maps are updated accordingly if it confirms a valid
  1041. * free area.
  1042. *
  1043. * RETURNS:
  1044. * Allocated addr offset in @chunk on success.
  1045. * -1 if no matching area is found.
  1046. */
  1047. static int pcpu_alloc_area(struct pcpu_chunk *chunk, int alloc_bits,
  1048. size_t align, int start)
  1049. {
  1050. struct pcpu_block_md *chunk_md = &chunk->chunk_md;
  1051. size_t align_mask = (align) ? (align - 1) : 0;
  1052. unsigned long area_off = 0, area_bits = 0;
  1053. int bit_off, end, oslot;
  1054. lockdep_assert_held(&pcpu_lock);
  1055. oslot = pcpu_chunk_slot(chunk);
  1056. /*
  1057. * Search to find a fit.
  1058. */
  1059. end = min_t(int, start + alloc_bits + PCPU_BITMAP_BLOCK_BITS,
  1060. pcpu_chunk_map_bits(chunk));
  1061. bit_off = pcpu_find_zero_area(chunk->alloc_map, end, start, alloc_bits,
  1062. align_mask, &area_off, &area_bits);
  1063. if (bit_off >= end)
  1064. return -1;
  1065. if (area_bits)
  1066. pcpu_block_update_scan(chunk, area_off, area_bits);
  1067. /* update alloc map */
  1068. bitmap_set(chunk->alloc_map, bit_off, alloc_bits);
  1069. /* update boundary map */
  1070. set_bit(bit_off, chunk->bound_map);
  1071. bitmap_clear(chunk->bound_map, bit_off + 1, alloc_bits - 1);
  1072. set_bit(bit_off + alloc_bits, chunk->bound_map);
  1073. chunk->free_bytes -= alloc_bits * PCPU_MIN_ALLOC_SIZE;
  1074. /* update first free bit */
  1075. if (bit_off == chunk_md->first_free)
  1076. chunk_md->first_free = find_next_zero_bit(
  1077. chunk->alloc_map,
  1078. pcpu_chunk_map_bits(chunk),
  1079. bit_off + alloc_bits);
  1080. pcpu_block_update_hint_alloc(chunk, bit_off, alloc_bits);
  1081. pcpu_chunk_relocate(chunk, oslot);
  1082. return bit_off * PCPU_MIN_ALLOC_SIZE;
  1083. }
  1084. /**
  1085. * pcpu_free_area - frees the corresponding offset
  1086. * @chunk: chunk of interest
  1087. * @off: addr offset into chunk
  1088. *
  1089. * This function determines the size of an allocation to free using
  1090. * the boundary bitmap and clears the allocation map.
  1091. *
  1092. * RETURNS:
  1093. * Number of freed bytes.
  1094. */
  1095. static int pcpu_free_area(struct pcpu_chunk *chunk, int off)
  1096. {
  1097. struct pcpu_block_md *chunk_md = &chunk->chunk_md;
  1098. int bit_off, bits, end, oslot, freed;
  1099. lockdep_assert_held(&pcpu_lock);
  1100. pcpu_stats_area_dealloc(chunk);
  1101. oslot = pcpu_chunk_slot(chunk);
  1102. bit_off = off / PCPU_MIN_ALLOC_SIZE;
  1103. /* find end index */
  1104. end = find_next_bit(chunk->bound_map, pcpu_chunk_map_bits(chunk),
  1105. bit_off + 1);
  1106. bits = end - bit_off;
  1107. bitmap_clear(chunk->alloc_map, bit_off, bits);
  1108. freed = bits * PCPU_MIN_ALLOC_SIZE;
  1109. /* update metadata */
  1110. chunk->free_bytes += freed;
  1111. /* update first free bit */
  1112. chunk_md->first_free = min(chunk_md->first_free, bit_off);
  1113. pcpu_block_update_hint_free(chunk, bit_off, bits);
  1114. pcpu_chunk_relocate(chunk, oslot);
  1115. return freed;
  1116. }
  1117. static void pcpu_init_md_block(struct pcpu_block_md *block, int nr_bits)
  1118. {
  1119. block->scan_hint = 0;
  1120. block->contig_hint = nr_bits;
  1121. block->left_free = nr_bits;
  1122. block->right_free = nr_bits;
  1123. block->first_free = 0;
  1124. block->nr_bits = nr_bits;
  1125. }
  1126. static void pcpu_init_md_blocks(struct pcpu_chunk *chunk)
  1127. {
  1128. struct pcpu_block_md *md_block;
  1129. /* init the chunk's block */
  1130. pcpu_init_md_block(&chunk->chunk_md, pcpu_chunk_map_bits(chunk));
  1131. for (md_block = chunk->md_blocks;
  1132. md_block != chunk->md_blocks + pcpu_chunk_nr_blocks(chunk);
  1133. md_block++)
  1134. pcpu_init_md_block(md_block, PCPU_BITMAP_BLOCK_BITS);
  1135. }
  1136. /**
  1137. * pcpu_alloc_first_chunk - creates chunks that serve the first chunk
  1138. * @tmp_addr: the start of the region served
  1139. * @map_size: size of the region served
  1140. *
  1141. * This is responsible for creating the chunks that serve the first chunk. The
  1142. * base_addr is page aligned down of @tmp_addr while the region end is page
  1143. * aligned up. Offsets are kept track of to determine the region served. All
  1144. * this is done to appease the bitmap allocator in avoiding partial blocks.
  1145. *
  1146. * RETURNS:
  1147. * Chunk serving the region at @tmp_addr of @map_size.
  1148. */
  1149. static struct pcpu_chunk * __init pcpu_alloc_first_chunk(unsigned long tmp_addr,
  1150. int map_size)
  1151. {
  1152. struct pcpu_chunk *chunk;
  1153. unsigned long aligned_addr, lcm_align;
  1154. int start_offset, offset_bits, region_size, region_bits;
  1155. size_t alloc_size;
  1156. /* region calculations */
  1157. aligned_addr = tmp_addr & PAGE_MASK;
  1158. start_offset = tmp_addr - aligned_addr;
  1159. /*
  1160. * Align the end of the region with the LCM of PAGE_SIZE and
  1161. * PCPU_BITMAP_BLOCK_SIZE. One of these constants is a multiple of
  1162. * the other.
  1163. */
  1164. lcm_align = lcm(PAGE_SIZE, PCPU_BITMAP_BLOCK_SIZE);
  1165. region_size = ALIGN(start_offset + map_size, lcm_align);
  1166. /* allocate chunk */
  1167. alloc_size = struct_size(chunk, populated,
  1168. BITS_TO_LONGS(region_size >> PAGE_SHIFT));
  1169. chunk = memblock_alloc(alloc_size, SMP_CACHE_BYTES);
  1170. if (!chunk)
  1171. panic("%s: Failed to allocate %zu bytes\n", __func__,
  1172. alloc_size);
  1173. INIT_LIST_HEAD(&chunk->list);
  1174. chunk->base_addr = (void *)aligned_addr;
  1175. chunk->start_offset = start_offset;
  1176. chunk->end_offset = region_size - chunk->start_offset - map_size;
  1177. chunk->nr_pages = region_size >> PAGE_SHIFT;
  1178. region_bits = pcpu_chunk_map_bits(chunk);
  1179. alloc_size = BITS_TO_LONGS(region_bits) * sizeof(chunk->alloc_map[0]);
  1180. chunk->alloc_map = memblock_alloc(alloc_size, SMP_CACHE_BYTES);
  1181. if (!chunk->alloc_map)
  1182. panic("%s: Failed to allocate %zu bytes\n", __func__,
  1183. alloc_size);
  1184. alloc_size =
  1185. BITS_TO_LONGS(region_bits + 1) * sizeof(chunk->bound_map[0]);
  1186. chunk->bound_map = memblock_alloc(alloc_size, SMP_CACHE_BYTES);
  1187. if (!chunk->bound_map)
  1188. panic("%s: Failed to allocate %zu bytes\n", __func__,
  1189. alloc_size);
  1190. alloc_size = pcpu_chunk_nr_blocks(chunk) * sizeof(chunk->md_blocks[0]);
  1191. chunk->md_blocks = memblock_alloc(alloc_size, SMP_CACHE_BYTES);
  1192. if (!chunk->md_blocks)
  1193. panic("%s: Failed to allocate %zu bytes\n", __func__,
  1194. alloc_size);
  1195. #ifdef CONFIG_MEMCG_KMEM
  1196. /* first chunk isn't memcg-aware */
  1197. chunk->obj_cgroups = NULL;
  1198. #endif
  1199. pcpu_init_md_blocks(chunk);
  1200. /* manage populated page bitmap */
  1201. chunk->immutable = true;
  1202. bitmap_fill(chunk->populated, chunk->nr_pages);
  1203. chunk->nr_populated = chunk->nr_pages;
  1204. chunk->nr_empty_pop_pages = chunk->nr_pages;
  1205. chunk->free_bytes = map_size;
  1206. if (chunk->start_offset) {
  1207. /* hide the beginning of the bitmap */
  1208. offset_bits = chunk->start_offset / PCPU_MIN_ALLOC_SIZE;
  1209. bitmap_set(chunk->alloc_map, 0, offset_bits);
  1210. set_bit(0, chunk->bound_map);
  1211. set_bit(offset_bits, chunk->bound_map);
  1212. chunk->chunk_md.first_free = offset_bits;
  1213. pcpu_block_update_hint_alloc(chunk, 0, offset_bits);
  1214. }
  1215. if (chunk->end_offset) {
  1216. /* hide the end of the bitmap */
  1217. offset_bits = chunk->end_offset / PCPU_MIN_ALLOC_SIZE;
  1218. bitmap_set(chunk->alloc_map,
  1219. pcpu_chunk_map_bits(chunk) - offset_bits,
  1220. offset_bits);
  1221. set_bit((start_offset + map_size) / PCPU_MIN_ALLOC_SIZE,
  1222. chunk->bound_map);
  1223. set_bit(region_bits, chunk->bound_map);
  1224. pcpu_block_update_hint_alloc(chunk, pcpu_chunk_map_bits(chunk)
  1225. - offset_bits, offset_bits);
  1226. }
  1227. return chunk;
  1228. }
  1229. static struct pcpu_chunk *pcpu_alloc_chunk(enum pcpu_chunk_type type, gfp_t gfp)
  1230. {
  1231. struct pcpu_chunk *chunk;
  1232. int region_bits;
  1233. chunk = pcpu_mem_zalloc(pcpu_chunk_struct_size, gfp);
  1234. if (!chunk)
  1235. return NULL;
  1236. INIT_LIST_HEAD(&chunk->list);
  1237. chunk->nr_pages = pcpu_unit_pages;
  1238. region_bits = pcpu_chunk_map_bits(chunk);
  1239. chunk->alloc_map = pcpu_mem_zalloc(BITS_TO_LONGS(region_bits) *
  1240. sizeof(chunk->alloc_map[0]), gfp);
  1241. if (!chunk->alloc_map)
  1242. goto alloc_map_fail;
  1243. chunk->bound_map = pcpu_mem_zalloc(BITS_TO_LONGS(region_bits + 1) *
  1244. sizeof(chunk->bound_map[0]), gfp);
  1245. if (!chunk->bound_map)
  1246. goto bound_map_fail;
  1247. chunk->md_blocks = pcpu_mem_zalloc(pcpu_chunk_nr_blocks(chunk) *
  1248. sizeof(chunk->md_blocks[0]), gfp);
  1249. if (!chunk->md_blocks)
  1250. goto md_blocks_fail;
  1251. #ifdef CONFIG_MEMCG_KMEM
  1252. if (pcpu_is_memcg_chunk(type)) {
  1253. chunk->obj_cgroups =
  1254. pcpu_mem_zalloc(pcpu_chunk_map_bits(chunk) *
  1255. sizeof(struct obj_cgroup *), gfp);
  1256. if (!chunk->obj_cgroups)
  1257. goto objcg_fail;
  1258. }
  1259. #endif
  1260. pcpu_init_md_blocks(chunk);
  1261. /* init metadata */
  1262. chunk->free_bytes = chunk->nr_pages * PAGE_SIZE;
  1263. return chunk;
  1264. #ifdef CONFIG_MEMCG_KMEM
  1265. objcg_fail:
  1266. pcpu_mem_free(chunk->md_blocks);
  1267. #endif
  1268. md_blocks_fail:
  1269. pcpu_mem_free(chunk->bound_map);
  1270. bound_map_fail:
  1271. pcpu_mem_free(chunk->alloc_map);
  1272. alloc_map_fail:
  1273. pcpu_mem_free(chunk);
  1274. return NULL;
  1275. }
  1276. static void pcpu_free_chunk(struct pcpu_chunk *chunk)
  1277. {
  1278. if (!chunk)
  1279. return;
  1280. #ifdef CONFIG_MEMCG_KMEM
  1281. pcpu_mem_free(chunk->obj_cgroups);
  1282. #endif
  1283. pcpu_mem_free(chunk->md_blocks);
  1284. pcpu_mem_free(chunk->bound_map);
  1285. pcpu_mem_free(chunk->alloc_map);
  1286. pcpu_mem_free(chunk);
  1287. }
  1288. /**
  1289. * pcpu_chunk_populated - post-population bookkeeping
  1290. * @chunk: pcpu_chunk which got populated
  1291. * @page_start: the start page
  1292. * @page_end: the end page
  1293. *
  1294. * Pages in [@page_start,@page_end) have been populated to @chunk. Update
  1295. * the bookkeeping information accordingly. Must be called after each
  1296. * successful population.
  1297. *
  1298. * If this is @for_alloc, do not increment pcpu_nr_empty_pop_pages because it
  1299. * is to serve an allocation in that area.
  1300. */
  1301. static void pcpu_chunk_populated(struct pcpu_chunk *chunk, int page_start,
  1302. int page_end)
  1303. {
  1304. int nr = page_end - page_start;
  1305. lockdep_assert_held(&pcpu_lock);
  1306. bitmap_set(chunk->populated, page_start, nr);
  1307. chunk->nr_populated += nr;
  1308. pcpu_nr_populated += nr;
  1309. pcpu_update_empty_pages(chunk, nr);
  1310. }
  1311. /**
  1312. * pcpu_chunk_depopulated - post-depopulation bookkeeping
  1313. * @chunk: pcpu_chunk which got depopulated
  1314. * @page_start: the start page
  1315. * @page_end: the end page
  1316. *
  1317. * Pages in [@page_start,@page_end) have been depopulated from @chunk.
  1318. * Update the bookkeeping information accordingly. Must be called after
  1319. * each successful depopulation.
  1320. */
  1321. static void pcpu_chunk_depopulated(struct pcpu_chunk *chunk,
  1322. int page_start, int page_end)
  1323. {
  1324. int nr = page_end - page_start;
  1325. lockdep_assert_held(&pcpu_lock);
  1326. bitmap_clear(chunk->populated, page_start, nr);
  1327. chunk->nr_populated -= nr;
  1328. pcpu_nr_populated -= nr;
  1329. pcpu_update_empty_pages(chunk, -nr);
  1330. }
  1331. /*
  1332. * Chunk management implementation.
  1333. *
  1334. * To allow different implementations, chunk alloc/free and
  1335. * [de]population are implemented in a separate file which is pulled
  1336. * into this file and compiled together. The following functions
  1337. * should be implemented.
  1338. *
  1339. * pcpu_populate_chunk - populate the specified range of a chunk
  1340. * pcpu_depopulate_chunk - depopulate the specified range of a chunk
  1341. * pcpu_create_chunk - create a new chunk
  1342. * pcpu_destroy_chunk - destroy a chunk, always preceded by full depop
  1343. * pcpu_addr_to_page - translate address to physical address
  1344. * pcpu_verify_alloc_info - check alloc_info is acceptable during init
  1345. */
  1346. static int pcpu_populate_chunk(struct pcpu_chunk *chunk,
  1347. int page_start, int page_end, gfp_t gfp);
  1348. static void pcpu_depopulate_chunk(struct pcpu_chunk *chunk,
  1349. int page_start, int page_end);
  1350. static struct pcpu_chunk *pcpu_create_chunk(enum pcpu_chunk_type type,
  1351. gfp_t gfp);
  1352. static void pcpu_destroy_chunk(struct pcpu_chunk *chunk);
  1353. static struct page *pcpu_addr_to_page(void *addr);
  1354. static int __init pcpu_verify_alloc_info(const struct pcpu_alloc_info *ai);
  1355. #ifdef CONFIG_NEED_PER_CPU_KM
  1356. #include "percpu-km.c"
  1357. #else
  1358. #include "percpu-vm.c"
  1359. #endif
  1360. /**
  1361. * pcpu_chunk_addr_search - determine chunk containing specified address
  1362. * @addr: address for which the chunk needs to be determined.
  1363. *
  1364. * This is an internal function that handles all but static allocations.
  1365. * Static percpu address values should never be passed into the allocator.
  1366. *
  1367. * RETURNS:
  1368. * The address of the found chunk.
  1369. */
  1370. static struct pcpu_chunk *pcpu_chunk_addr_search(void *addr)
  1371. {
  1372. /* is it in the dynamic region (first chunk)? */
  1373. if (pcpu_addr_in_chunk(pcpu_first_chunk, addr))
  1374. return pcpu_first_chunk;
  1375. /* is it in the reserved region? */
  1376. if (pcpu_addr_in_chunk(pcpu_reserved_chunk, addr))
  1377. return pcpu_reserved_chunk;
  1378. /*
  1379. * The address is relative to unit0 which might be unused and
  1380. * thus unmapped. Offset the address to the unit space of the
  1381. * current processor before looking it up in the vmalloc
  1382. * space. Note that any possible cpu id can be used here, so
  1383. * there's no need to worry about preemption or cpu hotplug.
  1384. */
  1385. addr += pcpu_unit_offsets[raw_smp_processor_id()];
  1386. return pcpu_get_page_chunk(pcpu_addr_to_page(addr));
  1387. }
  1388. #ifdef CONFIG_MEMCG_KMEM
  1389. static enum pcpu_chunk_type pcpu_memcg_pre_alloc_hook(size_t size, gfp_t gfp,
  1390. struct obj_cgroup **objcgp)
  1391. {
  1392. struct obj_cgroup *objcg;
  1393. if (!memcg_kmem_enabled() || !(gfp & __GFP_ACCOUNT))
  1394. return PCPU_CHUNK_ROOT;
  1395. objcg = get_obj_cgroup_from_current();
  1396. if (!objcg)
  1397. return PCPU_CHUNK_ROOT;
  1398. if (obj_cgroup_charge(objcg, gfp, size * num_possible_cpus())) {
  1399. obj_cgroup_put(objcg);
  1400. return PCPU_FAIL_ALLOC;
  1401. }
  1402. *objcgp = objcg;
  1403. return PCPU_CHUNK_MEMCG;
  1404. }
  1405. static void pcpu_memcg_post_alloc_hook(struct obj_cgroup *objcg,
  1406. struct pcpu_chunk *chunk, int off,
  1407. size_t size)
  1408. {
  1409. if (!objcg)
  1410. return;
  1411. if (chunk) {
  1412. chunk->obj_cgroups[off >> PCPU_MIN_ALLOC_SHIFT] = objcg;
  1413. rcu_read_lock();
  1414. mod_memcg_state(obj_cgroup_memcg(objcg), MEMCG_PERCPU_B,
  1415. size * num_possible_cpus());
  1416. rcu_read_unlock();
  1417. } else {
  1418. obj_cgroup_uncharge(objcg, size * num_possible_cpus());
  1419. obj_cgroup_put(objcg);
  1420. }
  1421. }
  1422. static void pcpu_memcg_free_hook(struct pcpu_chunk *chunk, int off, size_t size)
  1423. {
  1424. struct obj_cgroup *objcg;
  1425. if (!pcpu_is_memcg_chunk(pcpu_chunk_type(chunk)))
  1426. return;
  1427. objcg = chunk->obj_cgroups[off >> PCPU_MIN_ALLOC_SHIFT];
  1428. chunk->obj_cgroups[off >> PCPU_MIN_ALLOC_SHIFT] = NULL;
  1429. obj_cgroup_uncharge(objcg, size * num_possible_cpus());
  1430. rcu_read_lock();
  1431. mod_memcg_state(obj_cgroup_memcg(objcg), MEMCG_PERCPU_B,
  1432. -(size * num_possible_cpus()));
  1433. rcu_read_unlock();
  1434. obj_cgroup_put(objcg);
  1435. }
  1436. #else /* CONFIG_MEMCG_KMEM */
  1437. static enum pcpu_chunk_type
  1438. pcpu_memcg_pre_alloc_hook(size_t size, gfp_t gfp, struct obj_cgroup **objcgp)
  1439. {
  1440. return PCPU_CHUNK_ROOT;
  1441. }
  1442. static void pcpu_memcg_post_alloc_hook(struct obj_cgroup *objcg,
  1443. struct pcpu_chunk *chunk, int off,
  1444. size_t size)
  1445. {
  1446. }
  1447. static void pcpu_memcg_free_hook(struct pcpu_chunk *chunk, int off, size_t size)
  1448. {
  1449. }
  1450. #endif /* CONFIG_MEMCG_KMEM */
  1451. /**
  1452. * pcpu_alloc - the percpu allocator
  1453. * @size: size of area to allocate in bytes
  1454. * @align: alignment of area (max PAGE_SIZE)
  1455. * @reserved: allocate from the reserved chunk if available
  1456. * @gfp: allocation flags
  1457. *
  1458. * Allocate percpu area of @size bytes aligned at @align. If @gfp doesn't
  1459. * contain %GFP_KERNEL, the allocation is atomic. If @gfp has __GFP_NOWARN
  1460. * then no warning will be triggered on invalid or failed allocation
  1461. * requests.
  1462. *
  1463. * RETURNS:
  1464. * Percpu pointer to the allocated area on success, NULL on failure.
  1465. */
  1466. static void __percpu *pcpu_alloc(size_t size, size_t align, bool reserved,
  1467. gfp_t gfp)
  1468. {
  1469. gfp_t pcpu_gfp;
  1470. bool is_atomic;
  1471. bool do_warn;
  1472. enum pcpu_chunk_type type;
  1473. struct list_head *pcpu_slot;
  1474. struct obj_cgroup *objcg = NULL;
  1475. static int warn_limit = 10;
  1476. struct pcpu_chunk *chunk, *next;
  1477. const char *err;
  1478. int slot, off, cpu, ret;
  1479. unsigned long flags;
  1480. void __percpu *ptr;
  1481. size_t bits, bit_align;
  1482. gfp = current_gfp_context(gfp);
  1483. /* whitelisted flags that can be passed to the backing allocators */
  1484. pcpu_gfp = gfp & (GFP_KERNEL | __GFP_NORETRY | __GFP_NOWARN);
  1485. is_atomic = (gfp & GFP_KERNEL) != GFP_KERNEL;
  1486. do_warn = !(gfp & __GFP_NOWARN);
  1487. /*
  1488. * There is now a minimum allocation size of PCPU_MIN_ALLOC_SIZE,
  1489. * therefore alignment must be a minimum of that many bytes.
  1490. * An allocation may have internal fragmentation from rounding up
  1491. * of up to PCPU_MIN_ALLOC_SIZE - 1 bytes.
  1492. */
  1493. if (unlikely(align < PCPU_MIN_ALLOC_SIZE))
  1494. align = PCPU_MIN_ALLOC_SIZE;
  1495. size = ALIGN(size, PCPU_MIN_ALLOC_SIZE);
  1496. bits = size >> PCPU_MIN_ALLOC_SHIFT;
  1497. bit_align = align >> PCPU_MIN_ALLOC_SHIFT;
  1498. if (unlikely(!size || size > PCPU_MIN_UNIT_SIZE || align > PAGE_SIZE ||
  1499. !is_power_of_2(align))) {
  1500. WARN(do_warn, "illegal size (%zu) or align (%zu) for percpu allocation\n",
  1501. size, align);
  1502. return NULL;
  1503. }
  1504. type = pcpu_memcg_pre_alloc_hook(size, gfp, &objcg);
  1505. if (unlikely(type == PCPU_FAIL_ALLOC))
  1506. return NULL;
  1507. pcpu_slot = pcpu_chunk_list(type);
  1508. if (!is_atomic) {
  1509. /*
  1510. * pcpu_balance_workfn() allocates memory under this mutex,
  1511. * and it may wait for memory reclaim. Allow current task
  1512. * to become OOM victim, in case of memory pressure.
  1513. */
  1514. if (gfp & __GFP_NOFAIL) {
  1515. mutex_lock(&pcpu_alloc_mutex);
  1516. } else if (mutex_lock_killable(&pcpu_alloc_mutex)) {
  1517. pcpu_memcg_post_alloc_hook(objcg, NULL, 0, size);
  1518. return NULL;
  1519. }
  1520. }
  1521. spin_lock_irqsave(&pcpu_lock, flags);
  1522. /* serve reserved allocations from the reserved chunk if available */
  1523. if (reserved && pcpu_reserved_chunk) {
  1524. chunk = pcpu_reserved_chunk;
  1525. off = pcpu_find_block_fit(chunk, bits, bit_align, is_atomic);
  1526. if (off < 0) {
  1527. err = "alloc from reserved chunk failed";
  1528. goto fail_unlock;
  1529. }
  1530. off = pcpu_alloc_area(chunk, bits, bit_align, off);
  1531. if (off >= 0)
  1532. goto area_found;
  1533. err = "alloc from reserved chunk failed";
  1534. goto fail_unlock;
  1535. }
  1536. restart:
  1537. /* search through normal chunks */
  1538. for (slot = pcpu_size_to_slot(size); slot < pcpu_nr_slots; slot++) {
  1539. list_for_each_entry_safe(chunk, next, &pcpu_slot[slot], list) {
  1540. off = pcpu_find_block_fit(chunk, bits, bit_align,
  1541. is_atomic);
  1542. if (off < 0) {
  1543. if (slot < PCPU_SLOT_FAIL_THRESHOLD)
  1544. pcpu_chunk_move(chunk, 0);
  1545. continue;
  1546. }
  1547. off = pcpu_alloc_area(chunk, bits, bit_align, off);
  1548. if (off >= 0)
  1549. goto area_found;
  1550. }
  1551. }
  1552. spin_unlock_irqrestore(&pcpu_lock, flags);
  1553. /*
  1554. * No space left. Create a new chunk. We don't want multiple
  1555. * tasks to create chunks simultaneously. Serialize and create iff
  1556. * there's still no empty chunk after grabbing the mutex.
  1557. */
  1558. if (is_atomic) {
  1559. err = "atomic alloc failed, no space left";
  1560. goto fail;
  1561. }
  1562. if (list_empty(&pcpu_slot[pcpu_nr_slots - 1])) {
  1563. chunk = pcpu_create_chunk(type, pcpu_gfp);
  1564. if (!chunk) {
  1565. err = "failed to allocate new chunk";
  1566. goto fail;
  1567. }
  1568. spin_lock_irqsave(&pcpu_lock, flags);
  1569. pcpu_chunk_relocate(chunk, -1);
  1570. } else {
  1571. spin_lock_irqsave(&pcpu_lock, flags);
  1572. }
  1573. goto restart;
  1574. area_found:
  1575. pcpu_stats_area_alloc(chunk, size);
  1576. spin_unlock_irqrestore(&pcpu_lock, flags);
  1577. /* populate if not all pages are already there */
  1578. if (!is_atomic) {
  1579. unsigned int page_start, page_end, rs, re;
  1580. page_start = PFN_DOWN(off);
  1581. page_end = PFN_UP(off + size);
  1582. bitmap_for_each_clear_region(chunk->populated, rs, re,
  1583. page_start, page_end) {
  1584. WARN_ON(chunk->immutable);
  1585. ret = pcpu_populate_chunk(chunk, rs, re, pcpu_gfp);
  1586. spin_lock_irqsave(&pcpu_lock, flags);
  1587. if (ret) {
  1588. pcpu_free_area(chunk, off);
  1589. err = "failed to populate";
  1590. goto fail_unlock;
  1591. }
  1592. pcpu_chunk_populated(chunk, rs, re);
  1593. spin_unlock_irqrestore(&pcpu_lock, flags);
  1594. }
  1595. mutex_unlock(&pcpu_alloc_mutex);
  1596. }
  1597. if (pcpu_nr_empty_pop_pages[type] < PCPU_EMPTY_POP_PAGES_LOW)
  1598. pcpu_schedule_balance_work();
  1599. /* clear the areas and return address relative to base address */
  1600. for_each_possible_cpu(cpu)
  1601. memset((void *)pcpu_chunk_addr(chunk, cpu, 0) + off, 0, size);
  1602. ptr = __addr_to_pcpu_ptr(chunk->base_addr + off);
  1603. kmemleak_alloc_percpu(ptr, size, gfp);
  1604. trace_percpu_alloc_percpu(reserved, is_atomic, size, align,
  1605. chunk->base_addr, off, ptr);
  1606. pcpu_memcg_post_alloc_hook(objcg, chunk, off, size);
  1607. return ptr;
  1608. fail_unlock:
  1609. spin_unlock_irqrestore(&pcpu_lock, flags);
  1610. fail:
  1611. trace_percpu_alloc_percpu_fail(reserved, is_atomic, size, align);
  1612. if (!is_atomic && do_warn && warn_limit) {
  1613. pr_warn("allocation failed, size=%zu align=%zu atomic=%d, %s\n",
  1614. size, align, is_atomic, err);
  1615. dump_stack();
  1616. if (!--warn_limit)
  1617. pr_info("limit reached, disable warning\n");
  1618. }
  1619. if (is_atomic) {
  1620. /* see the flag handling in pcpu_blance_workfn() */
  1621. pcpu_atomic_alloc_failed = true;
  1622. pcpu_schedule_balance_work();
  1623. } else {
  1624. mutex_unlock(&pcpu_alloc_mutex);
  1625. }
  1626. pcpu_memcg_post_alloc_hook(objcg, NULL, 0, size);
  1627. return NULL;
  1628. }
  1629. /**
  1630. * __alloc_percpu_gfp - allocate dynamic percpu area
  1631. * @size: size of area to allocate in bytes
  1632. * @align: alignment of area (max PAGE_SIZE)
  1633. * @gfp: allocation flags
  1634. *
  1635. * Allocate zero-filled percpu area of @size bytes aligned at @align. If
  1636. * @gfp doesn't contain %GFP_KERNEL, the allocation doesn't block and can
  1637. * be called from any context but is a lot more likely to fail. If @gfp
  1638. * has __GFP_NOWARN then no warning will be triggered on invalid or failed
  1639. * allocation requests.
  1640. *
  1641. * RETURNS:
  1642. * Percpu pointer to the allocated area on success, NULL on failure.
  1643. */
  1644. void __percpu *__alloc_percpu_gfp(size_t size, size_t align, gfp_t gfp)
  1645. {
  1646. return pcpu_alloc(size, align, false, gfp);
  1647. }
  1648. EXPORT_SYMBOL_GPL(__alloc_percpu_gfp);
  1649. /**
  1650. * __alloc_percpu - allocate dynamic percpu area
  1651. * @size: size of area to allocate in bytes
  1652. * @align: alignment of area (max PAGE_SIZE)
  1653. *
  1654. * Equivalent to __alloc_percpu_gfp(size, align, %GFP_KERNEL).
  1655. */
  1656. void __percpu *__alloc_percpu(size_t size, size_t align)
  1657. {
  1658. return pcpu_alloc(size, align, false, GFP_KERNEL);
  1659. }
  1660. EXPORT_SYMBOL_GPL(__alloc_percpu);
  1661. /**
  1662. * __alloc_reserved_percpu - allocate reserved percpu area
  1663. * @size: size of area to allocate in bytes
  1664. * @align: alignment of area (max PAGE_SIZE)
  1665. *
  1666. * Allocate zero-filled percpu area of @size bytes aligned at @align
  1667. * from reserved percpu area if arch has set it up; otherwise,
  1668. * allocation is served from the same dynamic area. Might sleep.
  1669. * Might trigger writeouts.
  1670. *
  1671. * CONTEXT:
  1672. * Does GFP_KERNEL allocation.
  1673. *
  1674. * RETURNS:
  1675. * Percpu pointer to the allocated area on success, NULL on failure.
  1676. */
  1677. void __percpu *__alloc_reserved_percpu(size_t size, size_t align)
  1678. {
  1679. return pcpu_alloc(size, align, true, GFP_KERNEL);
  1680. }
  1681. /**
  1682. * __pcpu_balance_workfn - manage the amount of free chunks and populated pages
  1683. * @type: chunk type
  1684. *
  1685. * Reclaim all fully free chunks except for the first one. This is also
  1686. * responsible for maintaining the pool of empty populated pages. However,
  1687. * it is possible that this is called when physical memory is scarce causing
  1688. * OOM killer to be triggered. We should avoid doing so until an actual
  1689. * allocation causes the failure as it is possible that requests can be
  1690. * serviced from already backed regions.
  1691. */
  1692. static void __pcpu_balance_workfn(enum pcpu_chunk_type type)
  1693. {
  1694. /* gfp flags passed to underlying allocators */
  1695. const gfp_t gfp = GFP_KERNEL | __GFP_NORETRY | __GFP_NOWARN;
  1696. LIST_HEAD(to_free);
  1697. struct list_head *pcpu_slot = pcpu_chunk_list(type);
  1698. struct list_head *free_head = &pcpu_slot[pcpu_nr_slots - 1];
  1699. struct pcpu_chunk *chunk, *next;
  1700. int slot, nr_to_pop, ret;
  1701. /*
  1702. * There's no reason to keep around multiple unused chunks and VM
  1703. * areas can be scarce. Destroy all free chunks except for one.
  1704. */
  1705. mutex_lock(&pcpu_alloc_mutex);
  1706. spin_lock_irq(&pcpu_lock);
  1707. list_for_each_entry_safe(chunk, next, free_head, list) {
  1708. WARN_ON(chunk->immutable);
  1709. /* spare the first one */
  1710. if (chunk == list_first_entry(free_head, struct pcpu_chunk, list))
  1711. continue;
  1712. list_move(&chunk->list, &to_free);
  1713. }
  1714. spin_unlock_irq(&pcpu_lock);
  1715. list_for_each_entry_safe(chunk, next, &to_free, list) {
  1716. unsigned int rs, re;
  1717. bitmap_for_each_set_region(chunk->populated, rs, re, 0,
  1718. chunk->nr_pages) {
  1719. pcpu_depopulate_chunk(chunk, rs, re);
  1720. spin_lock_irq(&pcpu_lock);
  1721. pcpu_chunk_depopulated(chunk, rs, re);
  1722. spin_unlock_irq(&pcpu_lock);
  1723. }
  1724. pcpu_destroy_chunk(chunk);
  1725. cond_resched();
  1726. }
  1727. /*
  1728. * Ensure there are certain number of free populated pages for
  1729. * atomic allocs. Fill up from the most packed so that atomic
  1730. * allocs don't increase fragmentation. If atomic allocation
  1731. * failed previously, always populate the maximum amount. This
  1732. * should prevent atomic allocs larger than PAGE_SIZE from keeping
  1733. * failing indefinitely; however, large atomic allocs are not
  1734. * something we support properly and can be highly unreliable and
  1735. * inefficient.
  1736. */
  1737. retry_pop:
  1738. if (pcpu_atomic_alloc_failed) {
  1739. nr_to_pop = PCPU_EMPTY_POP_PAGES_HIGH;
  1740. /* best effort anyway, don't worry about synchronization */
  1741. pcpu_atomic_alloc_failed = false;
  1742. } else {
  1743. nr_to_pop = clamp(PCPU_EMPTY_POP_PAGES_HIGH -
  1744. pcpu_nr_empty_pop_pages[type],
  1745. 0, PCPU_EMPTY_POP_PAGES_HIGH);
  1746. }
  1747. for (slot = pcpu_size_to_slot(PAGE_SIZE); slot < pcpu_nr_slots; slot++) {
  1748. unsigned int nr_unpop = 0, rs, re;
  1749. if (!nr_to_pop)
  1750. break;
  1751. spin_lock_irq(&pcpu_lock);
  1752. list_for_each_entry(chunk, &pcpu_slot[slot], list) {
  1753. nr_unpop = chunk->nr_pages - chunk->nr_populated;
  1754. if (nr_unpop)
  1755. break;
  1756. }
  1757. spin_unlock_irq(&pcpu_lock);
  1758. if (!nr_unpop)
  1759. continue;
  1760. /* @chunk can't go away while pcpu_alloc_mutex is held */
  1761. bitmap_for_each_clear_region(chunk->populated, rs, re, 0,
  1762. chunk->nr_pages) {
  1763. int nr = min_t(int, re - rs, nr_to_pop);
  1764. ret = pcpu_populate_chunk(chunk, rs, rs + nr, gfp);
  1765. if (!ret) {
  1766. nr_to_pop -= nr;
  1767. spin_lock_irq(&pcpu_lock);
  1768. pcpu_chunk_populated(chunk, rs, rs + nr);
  1769. spin_unlock_irq(&pcpu_lock);
  1770. } else {
  1771. nr_to_pop = 0;
  1772. }
  1773. if (!nr_to_pop)
  1774. break;
  1775. }
  1776. }
  1777. if (nr_to_pop) {
  1778. /* ran out of chunks to populate, create a new one and retry */
  1779. chunk = pcpu_create_chunk(type, gfp);
  1780. if (chunk) {
  1781. spin_lock_irq(&pcpu_lock);
  1782. pcpu_chunk_relocate(chunk, -1);
  1783. spin_unlock_irq(&pcpu_lock);
  1784. goto retry_pop;
  1785. }
  1786. }
  1787. mutex_unlock(&pcpu_alloc_mutex);
  1788. }
  1789. /**
  1790. * pcpu_balance_workfn - manage the amount of free chunks and populated pages
  1791. * @work: unused
  1792. *
  1793. * Call __pcpu_balance_workfn() for each chunk type.
  1794. */
  1795. static void pcpu_balance_workfn(struct work_struct *work)
  1796. {
  1797. enum pcpu_chunk_type type;
  1798. for (type = 0; type < PCPU_NR_CHUNK_TYPES; type++)
  1799. __pcpu_balance_workfn(type);
  1800. }
  1801. /**
  1802. * free_percpu - free percpu area
  1803. * @ptr: pointer to area to free
  1804. *
  1805. * Free percpu area @ptr.
  1806. *
  1807. * CONTEXT:
  1808. * Can be called from atomic context.
  1809. */
  1810. void free_percpu(void __percpu *ptr)
  1811. {
  1812. void *addr;
  1813. struct pcpu_chunk *chunk;
  1814. unsigned long flags;
  1815. int size, off;
  1816. bool need_balance = false;
  1817. struct list_head *pcpu_slot;
  1818. if (!ptr)
  1819. return;
  1820. kmemleak_free_percpu(ptr);
  1821. addr = __pcpu_ptr_to_addr(ptr);
  1822. spin_lock_irqsave(&pcpu_lock, flags);
  1823. chunk = pcpu_chunk_addr_search(addr);
  1824. off = addr - chunk->base_addr;
  1825. size = pcpu_free_area(chunk, off);
  1826. pcpu_slot = pcpu_chunk_list(pcpu_chunk_type(chunk));
  1827. pcpu_memcg_free_hook(chunk, off, size);
  1828. /* if there are more than one fully free chunks, wake up grim reaper */
  1829. if (chunk->free_bytes == pcpu_unit_size) {
  1830. struct pcpu_chunk *pos;
  1831. list_for_each_entry(pos, &pcpu_slot[pcpu_nr_slots - 1], list)
  1832. if (pos != chunk) {
  1833. need_balance = true;
  1834. break;
  1835. }
  1836. }
  1837. trace_percpu_free_percpu(chunk->base_addr, off, ptr);
  1838. spin_unlock_irqrestore(&pcpu_lock, flags);
  1839. if (need_balance)
  1840. pcpu_schedule_balance_work();
  1841. }
  1842. EXPORT_SYMBOL_GPL(free_percpu);
  1843. bool __is_kernel_percpu_address(unsigned long addr, unsigned long *can_addr)
  1844. {
  1845. #ifdef CONFIG_SMP
  1846. const size_t static_size = __per_cpu_end - __per_cpu_start;
  1847. void __percpu *base = __addr_to_pcpu_ptr(pcpu_base_addr);
  1848. unsigned int cpu;
  1849. for_each_possible_cpu(cpu) {
  1850. void *start = per_cpu_ptr(base, cpu);
  1851. void *va = (void *)addr;
  1852. if (va >= start && va < start + static_size) {
  1853. if (can_addr) {
  1854. *can_addr = (unsigned long) (va - start);
  1855. *can_addr += (unsigned long)
  1856. per_cpu_ptr(base, get_boot_cpu_id());
  1857. }
  1858. return true;
  1859. }
  1860. }
  1861. #endif
  1862. /* on UP, can't distinguish from other static vars, always false */
  1863. return false;
  1864. }
  1865. /**
  1866. * is_kernel_percpu_address - test whether address is from static percpu area
  1867. * @addr: address to test
  1868. *
  1869. * Test whether @addr belongs to in-kernel static percpu area. Module
  1870. * static percpu areas are not considered. For those, use
  1871. * is_module_percpu_address().
  1872. *
  1873. * RETURNS:
  1874. * %true if @addr is from in-kernel static percpu area, %false otherwise.
  1875. */
  1876. bool is_kernel_percpu_address(unsigned long addr)
  1877. {
  1878. return __is_kernel_percpu_address(addr, NULL);
  1879. }
  1880. /**
  1881. * per_cpu_ptr_to_phys - convert translated percpu address to physical address
  1882. * @addr: the address to be converted to physical address
  1883. *
  1884. * Given @addr which is dereferenceable address obtained via one of
  1885. * percpu access macros, this function translates it into its physical
  1886. * address. The caller is responsible for ensuring @addr stays valid
  1887. * until this function finishes.
  1888. *
  1889. * percpu allocator has special setup for the first chunk, which currently
  1890. * supports either embedding in linear address space or vmalloc mapping,
  1891. * and, from the second one, the backing allocator (currently either vm or
  1892. * km) provides translation.
  1893. *
  1894. * The addr can be translated simply without checking if it falls into the
  1895. * first chunk. But the current code reflects better how percpu allocator
  1896. * actually works, and the verification can discover both bugs in percpu
  1897. * allocator itself and per_cpu_ptr_to_phys() callers. So we keep current
  1898. * code.
  1899. *
  1900. * RETURNS:
  1901. * The physical address for @addr.
  1902. */
  1903. phys_addr_t per_cpu_ptr_to_phys(void *addr)
  1904. {
  1905. void __percpu *base = __addr_to_pcpu_ptr(pcpu_base_addr);
  1906. bool in_first_chunk = false;
  1907. unsigned long first_low, first_high;
  1908. unsigned int cpu;
  1909. /*
  1910. * The following test on unit_low/high isn't strictly
  1911. * necessary but will speed up lookups of addresses which
  1912. * aren't in the first chunk.
  1913. *
  1914. * The address check is against full chunk sizes. pcpu_base_addr
  1915. * points to the beginning of the first chunk including the
  1916. * static region. Assumes good intent as the first chunk may
  1917. * not be full (ie. < pcpu_unit_pages in size).
  1918. */
  1919. first_low = (unsigned long)pcpu_base_addr +
  1920. pcpu_unit_page_offset(pcpu_low_unit_cpu, 0);
  1921. first_high = (unsigned long)pcpu_base_addr +
  1922. pcpu_unit_page_offset(pcpu_high_unit_cpu, pcpu_unit_pages);
  1923. if ((unsigned long)addr >= first_low &&
  1924. (unsigned long)addr < first_high) {
  1925. for_each_possible_cpu(cpu) {
  1926. void *start = per_cpu_ptr(base, cpu);
  1927. if (addr >= start && addr < start + pcpu_unit_size) {
  1928. in_first_chunk = true;
  1929. break;
  1930. }
  1931. }
  1932. }
  1933. if (in_first_chunk) {
  1934. if (!is_vmalloc_addr(addr))
  1935. return __pa(addr);
  1936. else
  1937. return page_to_phys(vmalloc_to_page(addr)) +
  1938. offset_in_page(addr);
  1939. } else
  1940. return page_to_phys(pcpu_addr_to_page(addr)) +
  1941. offset_in_page(addr);
  1942. }
  1943. EXPORT_SYMBOL_GPL(per_cpu_ptr_to_phys);
  1944. /**
  1945. * pcpu_alloc_alloc_info - allocate percpu allocation info
  1946. * @nr_groups: the number of groups
  1947. * @nr_units: the number of units
  1948. *
  1949. * Allocate ai which is large enough for @nr_groups groups containing
  1950. * @nr_units units. The returned ai's groups[0].cpu_map points to the
  1951. * cpu_map array which is long enough for @nr_units and filled with
  1952. * NR_CPUS. It's the caller's responsibility to initialize cpu_map
  1953. * pointer of other groups.
  1954. *
  1955. * RETURNS:
  1956. * Pointer to the allocated pcpu_alloc_info on success, NULL on
  1957. * failure.
  1958. */
  1959. struct pcpu_alloc_info * __init pcpu_alloc_alloc_info(int nr_groups,
  1960. int nr_units)
  1961. {
  1962. struct pcpu_alloc_info *ai;
  1963. size_t base_size, ai_size;
  1964. void *ptr;
  1965. int unit;
  1966. base_size = ALIGN(struct_size(ai, groups, nr_groups),
  1967. __alignof__(ai->groups[0].cpu_map[0]));
  1968. ai_size = base_size + nr_units * sizeof(ai->groups[0].cpu_map[0]);
  1969. ptr = memblock_alloc(PFN_ALIGN(ai_size), PAGE_SIZE);
  1970. if (!ptr)
  1971. return NULL;
  1972. ai = ptr;
  1973. ptr += base_size;
  1974. ai->groups[0].cpu_map = ptr;
  1975. for (unit = 0; unit < nr_units; unit++)
  1976. ai->groups[0].cpu_map[unit] = NR_CPUS;
  1977. ai->nr_groups = nr_groups;
  1978. ai->__ai_size = PFN_ALIGN(ai_size);
  1979. return ai;
  1980. }
  1981. /**
  1982. * pcpu_free_alloc_info - free percpu allocation info
  1983. * @ai: pcpu_alloc_info to free
  1984. *
  1985. * Free @ai which was allocated by pcpu_alloc_alloc_info().
  1986. */
  1987. void __init pcpu_free_alloc_info(struct pcpu_alloc_info *ai)
  1988. {
  1989. memblock_free_early(__pa(ai), ai->__ai_size);
  1990. }
  1991. /**
  1992. * pcpu_dump_alloc_info - print out information about pcpu_alloc_info
  1993. * @lvl: loglevel
  1994. * @ai: allocation info to dump
  1995. *
  1996. * Print out information about @ai using loglevel @lvl.
  1997. */
  1998. static void pcpu_dump_alloc_info(const char *lvl,
  1999. const struct pcpu_alloc_info *ai)
  2000. {
  2001. int group_width = 1, cpu_width = 1, width;
  2002. char empty_str[] = "--------";
  2003. int alloc = 0, alloc_end = 0;
  2004. int group, v;
  2005. int upa, apl; /* units per alloc, allocs per line */
  2006. v = ai->nr_groups;
  2007. while (v /= 10)
  2008. group_width++;
  2009. v = num_possible_cpus();
  2010. while (v /= 10)
  2011. cpu_width++;
  2012. empty_str[min_t(int, cpu_width, sizeof(empty_str) - 1)] = '\0';
  2013. upa = ai->alloc_size / ai->unit_size;
  2014. width = upa * (cpu_width + 1) + group_width + 3;
  2015. apl = rounddown_pow_of_two(max(60 / width, 1));
  2016. printk("%spcpu-alloc: s%zu r%zu d%zu u%zu alloc=%zu*%zu",
  2017. lvl, ai->static_size, ai->reserved_size, ai->dyn_size,
  2018. ai->unit_size, ai->alloc_size / ai->atom_size, ai->atom_size);
  2019. for (group = 0; group < ai->nr_groups; group++) {
  2020. const struct pcpu_group_info *gi = &ai->groups[group];
  2021. int unit = 0, unit_end = 0;
  2022. BUG_ON(gi->nr_units % upa);
  2023. for (alloc_end += gi->nr_units / upa;
  2024. alloc < alloc_end; alloc++) {
  2025. if (!(alloc % apl)) {
  2026. pr_cont("\n");
  2027. printk("%spcpu-alloc: ", lvl);
  2028. }
  2029. pr_cont("[%0*d] ", group_width, group);
  2030. for (unit_end += upa; unit < unit_end; unit++)
  2031. if (gi->cpu_map[unit] != NR_CPUS)
  2032. pr_cont("%0*d ",
  2033. cpu_width, gi->cpu_map[unit]);
  2034. else
  2035. pr_cont("%s ", empty_str);
  2036. }
  2037. }
  2038. pr_cont("\n");
  2039. }
  2040. /**
  2041. * pcpu_setup_first_chunk - initialize the first percpu chunk
  2042. * @ai: pcpu_alloc_info describing how to percpu area is shaped
  2043. * @base_addr: mapped address
  2044. *
  2045. * Initialize the first percpu chunk which contains the kernel static
  2046. * percpu area. This function is to be called from arch percpu area
  2047. * setup path.
  2048. *
  2049. * @ai contains all information necessary to initialize the first
  2050. * chunk and prime the dynamic percpu allocator.
  2051. *
  2052. * @ai->static_size is the size of static percpu area.
  2053. *
  2054. * @ai->reserved_size, if non-zero, specifies the amount of bytes to
  2055. * reserve after the static area in the first chunk. This reserves
  2056. * the first chunk such that it's available only through reserved
  2057. * percpu allocation. This is primarily used to serve module percpu
  2058. * static areas on architectures where the addressing model has
  2059. * limited offset range for symbol relocations to guarantee module
  2060. * percpu symbols fall inside the relocatable range.
  2061. *
  2062. * @ai->dyn_size determines the number of bytes available for dynamic
  2063. * allocation in the first chunk. The area between @ai->static_size +
  2064. * @ai->reserved_size + @ai->dyn_size and @ai->unit_size is unused.
  2065. *
  2066. * @ai->unit_size specifies unit size and must be aligned to PAGE_SIZE
  2067. * and equal to or larger than @ai->static_size + @ai->reserved_size +
  2068. * @ai->dyn_size.
  2069. *
  2070. * @ai->atom_size is the allocation atom size and used as alignment
  2071. * for vm areas.
  2072. *
  2073. * @ai->alloc_size is the allocation size and always multiple of
  2074. * @ai->atom_size. This is larger than @ai->atom_size if
  2075. * @ai->unit_size is larger than @ai->atom_size.
  2076. *
  2077. * @ai->nr_groups and @ai->groups describe virtual memory layout of
  2078. * percpu areas. Units which should be colocated are put into the
  2079. * same group. Dynamic VM areas will be allocated according to these
  2080. * groupings. If @ai->nr_groups is zero, a single group containing
  2081. * all units is assumed.
  2082. *
  2083. * The caller should have mapped the first chunk at @base_addr and
  2084. * copied static data to each unit.
  2085. *
  2086. * The first chunk will always contain a static and a dynamic region.
  2087. * However, the static region is not managed by any chunk. If the first
  2088. * chunk also contains a reserved region, it is served by two chunks -
  2089. * one for the reserved region and one for the dynamic region. They
  2090. * share the same vm, but use offset regions in the area allocation map.
  2091. * The chunk serving the dynamic region is circulated in the chunk slots
  2092. * and available for dynamic allocation like any other chunk.
  2093. */
  2094. void __init pcpu_setup_first_chunk(const struct pcpu_alloc_info *ai,
  2095. void *base_addr)
  2096. {
  2097. size_t size_sum = ai->static_size + ai->reserved_size + ai->dyn_size;
  2098. size_t static_size, dyn_size;
  2099. struct pcpu_chunk *chunk;
  2100. unsigned long *group_offsets;
  2101. size_t *group_sizes;
  2102. unsigned long *unit_off;
  2103. unsigned int cpu;
  2104. int *unit_map;
  2105. int group, unit, i;
  2106. int map_size;
  2107. unsigned long tmp_addr;
  2108. size_t alloc_size;
  2109. enum pcpu_chunk_type type;
  2110. #define PCPU_SETUP_BUG_ON(cond) do { \
  2111. if (unlikely(cond)) { \
  2112. pr_emerg("failed to initialize, %s\n", #cond); \
  2113. pr_emerg("cpu_possible_mask=%*pb\n", \
  2114. cpumask_pr_args(cpu_possible_mask)); \
  2115. pcpu_dump_alloc_info(KERN_EMERG, ai); \
  2116. BUG(); \
  2117. } \
  2118. } while (0)
  2119. /* sanity checks */
  2120. PCPU_SETUP_BUG_ON(ai->nr_groups <= 0);
  2121. #ifdef CONFIG_SMP
  2122. PCPU_SETUP_BUG_ON(!ai->static_size);
  2123. PCPU_SETUP_BUG_ON(offset_in_page(__per_cpu_start));
  2124. #endif
  2125. PCPU_SETUP_BUG_ON(!base_addr);
  2126. PCPU_SETUP_BUG_ON(offset_in_page(base_addr));
  2127. PCPU_SETUP_BUG_ON(ai->unit_size < size_sum);
  2128. PCPU_SETUP_BUG_ON(offset_in_page(ai->unit_size));
  2129. PCPU_SETUP_BUG_ON(ai->unit_size < PCPU_MIN_UNIT_SIZE);
  2130. PCPU_SETUP_BUG_ON(!IS_ALIGNED(ai->unit_size, PCPU_BITMAP_BLOCK_SIZE));
  2131. PCPU_SETUP_BUG_ON(ai->dyn_size < PERCPU_DYNAMIC_EARLY_SIZE);
  2132. PCPU_SETUP_BUG_ON(!ai->dyn_size);
  2133. PCPU_SETUP_BUG_ON(!IS_ALIGNED(ai->reserved_size, PCPU_MIN_ALLOC_SIZE));
  2134. PCPU_SETUP_BUG_ON(!(IS_ALIGNED(PCPU_BITMAP_BLOCK_SIZE, PAGE_SIZE) ||
  2135. IS_ALIGNED(PAGE_SIZE, PCPU_BITMAP_BLOCK_SIZE)));
  2136. PCPU_SETUP_BUG_ON(pcpu_verify_alloc_info(ai) < 0);
  2137. /* process group information and build config tables accordingly */
  2138. alloc_size = ai->nr_groups * sizeof(group_offsets[0]);
  2139. group_offsets = memblock_alloc(alloc_size, SMP_CACHE_BYTES);
  2140. if (!group_offsets)
  2141. panic("%s: Failed to allocate %zu bytes\n", __func__,
  2142. alloc_size);
  2143. alloc_size = ai->nr_groups * sizeof(group_sizes[0]);
  2144. group_sizes = memblock_alloc(alloc_size, SMP_CACHE_BYTES);
  2145. if (!group_sizes)
  2146. panic("%s: Failed to allocate %zu bytes\n", __func__,
  2147. alloc_size);
  2148. alloc_size = nr_cpu_ids * sizeof(unit_map[0]);
  2149. unit_map = memblock_alloc(alloc_size, SMP_CACHE_BYTES);
  2150. if (!unit_map)
  2151. panic("%s: Failed to allocate %zu bytes\n", __func__,
  2152. alloc_size);
  2153. alloc_size = nr_cpu_ids * sizeof(unit_off[0]);
  2154. unit_off = memblock_alloc(alloc_size, SMP_CACHE_BYTES);
  2155. if (!unit_off)
  2156. panic("%s: Failed to allocate %zu bytes\n", __func__,
  2157. alloc_size);
  2158. for (cpu = 0; cpu < nr_cpu_ids; cpu++)
  2159. unit_map[cpu] = UINT_MAX;
  2160. pcpu_low_unit_cpu = NR_CPUS;
  2161. pcpu_high_unit_cpu = NR_CPUS;
  2162. for (group = 0, unit = 0; group < ai->nr_groups; group++, unit += i) {
  2163. const struct pcpu_group_info *gi = &ai->groups[group];
  2164. group_offsets[group] = gi->base_offset;
  2165. group_sizes[group] = gi->nr_units * ai->unit_size;
  2166. for (i = 0; i < gi->nr_units; i++) {
  2167. cpu = gi->cpu_map[i];
  2168. if (cpu == NR_CPUS)
  2169. continue;
  2170. PCPU_SETUP_BUG_ON(cpu >= nr_cpu_ids);
  2171. PCPU_SETUP_BUG_ON(!cpu_possible(cpu));
  2172. PCPU_SETUP_BUG_ON(unit_map[cpu] != UINT_MAX);
  2173. unit_map[cpu] = unit + i;
  2174. unit_off[cpu] = gi->base_offset + i * ai->unit_size;
  2175. /* determine low/high unit_cpu */
  2176. if (pcpu_low_unit_cpu == NR_CPUS ||
  2177. unit_off[cpu] < unit_off[pcpu_low_unit_cpu])
  2178. pcpu_low_unit_cpu = cpu;
  2179. if (pcpu_high_unit_cpu == NR_CPUS ||
  2180. unit_off[cpu] > unit_off[pcpu_high_unit_cpu])
  2181. pcpu_high_unit_cpu = cpu;
  2182. }
  2183. }
  2184. pcpu_nr_units = unit;
  2185. for_each_possible_cpu(cpu)
  2186. PCPU_SETUP_BUG_ON(unit_map[cpu] == UINT_MAX);
  2187. /* we're done parsing the input, undefine BUG macro and dump config */
  2188. #undef PCPU_SETUP_BUG_ON
  2189. pcpu_dump_alloc_info(KERN_DEBUG, ai);
  2190. pcpu_nr_groups = ai->nr_groups;
  2191. pcpu_group_offsets = group_offsets;
  2192. pcpu_group_sizes = group_sizes;
  2193. pcpu_unit_map = unit_map;
  2194. pcpu_unit_offsets = unit_off;
  2195. /* determine basic parameters */
  2196. pcpu_unit_pages = ai->unit_size >> PAGE_SHIFT;
  2197. pcpu_unit_size = pcpu_unit_pages << PAGE_SHIFT;
  2198. pcpu_atom_size = ai->atom_size;
  2199. pcpu_chunk_struct_size = struct_size(chunk, populated,
  2200. BITS_TO_LONGS(pcpu_unit_pages));
  2201. pcpu_stats_save_ai(ai);
  2202. /*
  2203. * Allocate chunk slots. The additional last slot is for
  2204. * empty chunks.
  2205. */
  2206. pcpu_nr_slots = __pcpu_size_to_slot(pcpu_unit_size) + 2;
  2207. pcpu_chunk_lists = memblock_alloc(pcpu_nr_slots *
  2208. sizeof(pcpu_chunk_lists[0]) *
  2209. PCPU_NR_CHUNK_TYPES,
  2210. SMP_CACHE_BYTES);
  2211. if (!pcpu_chunk_lists)
  2212. panic("%s: Failed to allocate %zu bytes\n", __func__,
  2213. pcpu_nr_slots * sizeof(pcpu_chunk_lists[0]) *
  2214. PCPU_NR_CHUNK_TYPES);
  2215. for (type = 0; type < PCPU_NR_CHUNK_TYPES; type++)
  2216. for (i = 0; i < pcpu_nr_slots; i++)
  2217. INIT_LIST_HEAD(&pcpu_chunk_list(type)[i]);
  2218. /*
  2219. * The end of the static region needs to be aligned with the
  2220. * minimum allocation size as this offsets the reserved and
  2221. * dynamic region. The first chunk ends page aligned by
  2222. * expanding the dynamic region, therefore the dynamic region
  2223. * can be shrunk to compensate while still staying above the
  2224. * configured sizes.
  2225. */
  2226. static_size = ALIGN(ai->static_size, PCPU_MIN_ALLOC_SIZE);
  2227. dyn_size = ai->dyn_size - (static_size - ai->static_size);
  2228. /*
  2229. * Initialize first chunk.
  2230. * If the reserved_size is non-zero, this initializes the reserved
  2231. * chunk. If the reserved_size is zero, the reserved chunk is NULL
  2232. * and the dynamic region is initialized here. The first chunk,
  2233. * pcpu_first_chunk, will always point to the chunk that serves
  2234. * the dynamic region.
  2235. */
  2236. tmp_addr = (unsigned long)base_addr + static_size;
  2237. map_size = ai->reserved_size ?: dyn_size;
  2238. chunk = pcpu_alloc_first_chunk(tmp_addr, map_size);
  2239. /* init dynamic chunk if necessary */
  2240. if (ai->reserved_size) {
  2241. pcpu_reserved_chunk = chunk;
  2242. tmp_addr = (unsigned long)base_addr + static_size +
  2243. ai->reserved_size;
  2244. map_size = dyn_size;
  2245. chunk = pcpu_alloc_first_chunk(tmp_addr, map_size);
  2246. }
  2247. /* link the first chunk in */
  2248. pcpu_first_chunk = chunk;
  2249. pcpu_nr_empty_pop_pages[PCPU_CHUNK_ROOT] = pcpu_first_chunk->nr_empty_pop_pages;
  2250. pcpu_chunk_relocate(pcpu_first_chunk, -1);
  2251. /* include all regions of the first chunk */
  2252. pcpu_nr_populated += PFN_DOWN(size_sum);
  2253. pcpu_stats_chunk_alloc();
  2254. trace_percpu_create_chunk(base_addr);
  2255. /* we're done */
  2256. pcpu_base_addr = base_addr;
  2257. }
  2258. #ifdef CONFIG_SMP
  2259. const char * const pcpu_fc_names[PCPU_FC_NR] __initconst = {
  2260. [PCPU_FC_AUTO] = "auto",
  2261. [PCPU_FC_EMBED] = "embed",
  2262. [PCPU_FC_PAGE] = "page",
  2263. };
  2264. enum pcpu_fc pcpu_chosen_fc __initdata = PCPU_FC_AUTO;
  2265. static int __init percpu_alloc_setup(char *str)
  2266. {
  2267. if (!str)
  2268. return -EINVAL;
  2269. if (0)
  2270. /* nada */;
  2271. #ifdef CONFIG_NEED_PER_CPU_EMBED_FIRST_CHUNK
  2272. else if (!strcmp(str, "embed"))
  2273. pcpu_chosen_fc = PCPU_FC_EMBED;
  2274. #endif
  2275. #ifdef CONFIG_NEED_PER_CPU_PAGE_FIRST_CHUNK
  2276. else if (!strcmp(str, "page"))
  2277. pcpu_chosen_fc = PCPU_FC_PAGE;
  2278. #endif
  2279. else
  2280. pr_warn("unknown allocator %s specified\n", str);
  2281. return 0;
  2282. }
  2283. early_param("percpu_alloc", percpu_alloc_setup);
  2284. /*
  2285. * pcpu_embed_first_chunk() is used by the generic percpu setup.
  2286. * Build it if needed by the arch config or the generic setup is going
  2287. * to be used.
  2288. */
  2289. #if defined(CONFIG_NEED_PER_CPU_EMBED_FIRST_CHUNK) || \
  2290. !defined(CONFIG_HAVE_SETUP_PER_CPU_AREA)
  2291. #define BUILD_EMBED_FIRST_CHUNK
  2292. #endif
  2293. /* build pcpu_page_first_chunk() iff needed by the arch config */
  2294. #if defined(CONFIG_NEED_PER_CPU_PAGE_FIRST_CHUNK)
  2295. #define BUILD_PAGE_FIRST_CHUNK
  2296. #endif
  2297. /* pcpu_build_alloc_info() is used by both embed and page first chunk */
  2298. #if defined(BUILD_EMBED_FIRST_CHUNK) || defined(BUILD_PAGE_FIRST_CHUNK)
  2299. /**
  2300. * pcpu_build_alloc_info - build alloc_info considering distances between CPUs
  2301. * @reserved_size: the size of reserved percpu area in bytes
  2302. * @dyn_size: minimum free size for dynamic allocation in bytes
  2303. * @atom_size: allocation atom size
  2304. * @cpu_distance_fn: callback to determine distance between cpus, optional
  2305. *
  2306. * This function determines grouping of units, their mappings to cpus
  2307. * and other parameters considering needed percpu size, allocation
  2308. * atom size and distances between CPUs.
  2309. *
  2310. * Groups are always multiples of atom size and CPUs which are of
  2311. * LOCAL_DISTANCE both ways are grouped together and share space for
  2312. * units in the same group. The returned configuration is guaranteed
  2313. * to have CPUs on different nodes on different groups and >=75% usage
  2314. * of allocated virtual address space.
  2315. *
  2316. * RETURNS:
  2317. * On success, pointer to the new allocation_info is returned. On
  2318. * failure, ERR_PTR value is returned.
  2319. */
  2320. static struct pcpu_alloc_info * __init pcpu_build_alloc_info(
  2321. size_t reserved_size, size_t dyn_size,
  2322. size_t atom_size,
  2323. pcpu_fc_cpu_distance_fn_t cpu_distance_fn)
  2324. {
  2325. static int group_map[NR_CPUS] __initdata;
  2326. static int group_cnt[NR_CPUS] __initdata;
  2327. const size_t static_size = __per_cpu_end - __per_cpu_start;
  2328. int nr_groups = 1, nr_units = 0;
  2329. size_t size_sum, min_unit_size, alloc_size;
  2330. int upa, max_upa, best_upa; /* units_per_alloc */
  2331. int last_allocs, group, unit;
  2332. unsigned int cpu, tcpu;
  2333. struct pcpu_alloc_info *ai;
  2334. unsigned int *cpu_map;
  2335. /* this function may be called multiple times */
  2336. memset(group_map, 0, sizeof(group_map));
  2337. memset(group_cnt, 0, sizeof(group_cnt));
  2338. /* calculate size_sum and ensure dyn_size is enough for early alloc */
  2339. size_sum = PFN_ALIGN(static_size + reserved_size +
  2340. max_t(size_t, dyn_size, PERCPU_DYNAMIC_EARLY_SIZE));
  2341. dyn_size = size_sum - static_size - reserved_size;
  2342. /*
  2343. * Determine min_unit_size, alloc_size and max_upa such that
  2344. * alloc_size is multiple of atom_size and is the smallest
  2345. * which can accommodate 4k aligned segments which are equal to
  2346. * or larger than min_unit_size.
  2347. */
  2348. min_unit_size = max_t(size_t, size_sum, PCPU_MIN_UNIT_SIZE);
  2349. /* determine the maximum # of units that can fit in an allocation */
  2350. alloc_size = roundup(min_unit_size, atom_size);
  2351. upa = alloc_size / min_unit_size;
  2352. while (alloc_size % upa || (offset_in_page(alloc_size / upa)))
  2353. upa--;
  2354. max_upa = upa;
  2355. /* group cpus according to their proximity */
  2356. for_each_possible_cpu(cpu) {
  2357. group = 0;
  2358. next_group:
  2359. for_each_possible_cpu(tcpu) {
  2360. if (cpu == tcpu)
  2361. break;
  2362. if (group_map[tcpu] == group && cpu_distance_fn &&
  2363. (cpu_distance_fn(cpu, tcpu) > LOCAL_DISTANCE ||
  2364. cpu_distance_fn(tcpu, cpu) > LOCAL_DISTANCE)) {
  2365. group++;
  2366. nr_groups = max(nr_groups, group + 1);
  2367. goto next_group;
  2368. }
  2369. }
  2370. group_map[cpu] = group;
  2371. group_cnt[group]++;
  2372. }
  2373. /*
  2374. * Wasted space is caused by a ratio imbalance of upa to group_cnt.
  2375. * Expand the unit_size until we use >= 75% of the units allocated.
  2376. * Related to atom_size, which could be much larger than the unit_size.
  2377. */
  2378. last_allocs = INT_MAX;
  2379. for (upa = max_upa; upa; upa--) {
  2380. int allocs = 0, wasted = 0;
  2381. if (alloc_size % upa || (offset_in_page(alloc_size / upa)))
  2382. continue;
  2383. for (group = 0; group < nr_groups; group++) {
  2384. int this_allocs = DIV_ROUND_UP(group_cnt[group], upa);
  2385. allocs += this_allocs;
  2386. wasted += this_allocs * upa - group_cnt[group];
  2387. }
  2388. /*
  2389. * Don't accept if wastage is over 1/3. The
  2390. * greater-than comparison ensures upa==1 always
  2391. * passes the following check.
  2392. */
  2393. if (wasted > num_possible_cpus() / 3)
  2394. continue;
  2395. /* and then don't consume more memory */
  2396. if (allocs > last_allocs)
  2397. break;
  2398. last_allocs = allocs;
  2399. best_upa = upa;
  2400. }
  2401. upa = best_upa;
  2402. /* allocate and fill alloc_info */
  2403. for (group = 0; group < nr_groups; group++)
  2404. nr_units += roundup(group_cnt[group], upa);
  2405. ai = pcpu_alloc_alloc_info(nr_groups, nr_units);
  2406. if (!ai)
  2407. return ERR_PTR(-ENOMEM);
  2408. cpu_map = ai->groups[0].cpu_map;
  2409. for (group = 0; group < nr_groups; group++) {
  2410. ai->groups[group].cpu_map = cpu_map;
  2411. cpu_map += roundup(group_cnt[group], upa);
  2412. }
  2413. ai->static_size = static_size;
  2414. ai->reserved_size = reserved_size;
  2415. ai->dyn_size = dyn_size;
  2416. ai->unit_size = alloc_size / upa;
  2417. ai->atom_size = atom_size;
  2418. ai->alloc_size = alloc_size;
  2419. for (group = 0, unit = 0; group < nr_groups; group++) {
  2420. struct pcpu_group_info *gi = &ai->groups[group];
  2421. /*
  2422. * Initialize base_offset as if all groups are located
  2423. * back-to-back. The caller should update this to
  2424. * reflect actual allocation.
  2425. */
  2426. gi->base_offset = unit * ai->unit_size;
  2427. for_each_possible_cpu(cpu)
  2428. if (group_map[cpu] == group)
  2429. gi->cpu_map[gi->nr_units++] = cpu;
  2430. gi->nr_units = roundup(gi->nr_units, upa);
  2431. unit += gi->nr_units;
  2432. }
  2433. BUG_ON(unit != nr_units);
  2434. return ai;
  2435. }
  2436. #endif /* BUILD_EMBED_FIRST_CHUNK || BUILD_PAGE_FIRST_CHUNK */
  2437. #if defined(BUILD_EMBED_FIRST_CHUNK)
  2438. /**
  2439. * pcpu_embed_first_chunk - embed the first percpu chunk into bootmem
  2440. * @reserved_size: the size of reserved percpu area in bytes
  2441. * @dyn_size: minimum free size for dynamic allocation in bytes
  2442. * @atom_size: allocation atom size
  2443. * @cpu_distance_fn: callback to determine distance between cpus, optional
  2444. * @alloc_fn: function to allocate percpu page
  2445. * @free_fn: function to free percpu page
  2446. *
  2447. * This is a helper to ease setting up embedded first percpu chunk and
  2448. * can be called where pcpu_setup_first_chunk() is expected.
  2449. *
  2450. * If this function is used to setup the first chunk, it is allocated
  2451. * by calling @alloc_fn and used as-is without being mapped into
  2452. * vmalloc area. Allocations are always whole multiples of @atom_size
  2453. * aligned to @atom_size.
  2454. *
  2455. * This enables the first chunk to piggy back on the linear physical
  2456. * mapping which often uses larger page size. Please note that this
  2457. * can result in very sparse cpu->unit mapping on NUMA machines thus
  2458. * requiring large vmalloc address space. Don't use this allocator if
  2459. * vmalloc space is not orders of magnitude larger than distances
  2460. * between node memory addresses (ie. 32bit NUMA machines).
  2461. *
  2462. * @dyn_size specifies the minimum dynamic area size.
  2463. *
  2464. * If the needed size is smaller than the minimum or specified unit
  2465. * size, the leftover is returned using @free_fn.
  2466. *
  2467. * RETURNS:
  2468. * 0 on success, -errno on failure.
  2469. */
  2470. int __init pcpu_embed_first_chunk(size_t reserved_size, size_t dyn_size,
  2471. size_t atom_size,
  2472. pcpu_fc_cpu_distance_fn_t cpu_distance_fn,
  2473. pcpu_fc_alloc_fn_t alloc_fn,
  2474. pcpu_fc_free_fn_t free_fn)
  2475. {
  2476. void *base = (void *)ULONG_MAX;
  2477. void **areas = NULL;
  2478. struct pcpu_alloc_info *ai;
  2479. size_t size_sum, areas_size;
  2480. unsigned long max_distance;
  2481. int group, i, highest_group, rc = 0;
  2482. ai = pcpu_build_alloc_info(reserved_size, dyn_size, atom_size,
  2483. cpu_distance_fn);
  2484. if (IS_ERR(ai))
  2485. return PTR_ERR(ai);
  2486. size_sum = ai->static_size + ai->reserved_size + ai->dyn_size;
  2487. areas_size = PFN_ALIGN(ai->nr_groups * sizeof(void *));
  2488. areas = memblock_alloc(areas_size, SMP_CACHE_BYTES);
  2489. if (!areas) {
  2490. rc = -ENOMEM;
  2491. goto out_free;
  2492. }
  2493. /* allocate, copy and determine base address & max_distance */
  2494. highest_group = 0;
  2495. for (group = 0; group < ai->nr_groups; group++) {
  2496. struct pcpu_group_info *gi = &ai->groups[group];
  2497. unsigned int cpu = NR_CPUS;
  2498. void *ptr;
  2499. for (i = 0; i < gi->nr_units && cpu == NR_CPUS; i++)
  2500. cpu = gi->cpu_map[i];
  2501. BUG_ON(cpu == NR_CPUS);
  2502. /* allocate space for the whole group */
  2503. ptr = alloc_fn(cpu, gi->nr_units * ai->unit_size, atom_size);
  2504. if (!ptr) {
  2505. rc = -ENOMEM;
  2506. goto out_free_areas;
  2507. }
  2508. /* kmemleak tracks the percpu allocations separately */
  2509. kmemleak_free(ptr);
  2510. areas[group] = ptr;
  2511. base = min(ptr, base);
  2512. if (ptr > areas[highest_group])
  2513. highest_group = group;
  2514. }
  2515. max_distance = areas[highest_group] - base;
  2516. max_distance += ai->unit_size * ai->groups[highest_group].nr_units;
  2517. /* warn if maximum distance is further than 75% of vmalloc space */
  2518. if (max_distance > VMALLOC_TOTAL * 3 / 4) {
  2519. pr_warn("max_distance=0x%lx too large for vmalloc space 0x%lx\n",
  2520. max_distance, VMALLOC_TOTAL);
  2521. #ifdef CONFIG_NEED_PER_CPU_PAGE_FIRST_CHUNK
  2522. /* and fail if we have fallback */
  2523. rc = -EINVAL;
  2524. goto out_free_areas;
  2525. #endif
  2526. }
  2527. /*
  2528. * Copy data and free unused parts. This should happen after all
  2529. * allocations are complete; otherwise, we may end up with
  2530. * overlapping groups.
  2531. */
  2532. for (group = 0; group < ai->nr_groups; group++) {
  2533. struct pcpu_group_info *gi = &ai->groups[group];
  2534. void *ptr = areas[group];
  2535. for (i = 0; i < gi->nr_units; i++, ptr += ai->unit_size) {
  2536. if (gi->cpu_map[i] == NR_CPUS) {
  2537. /* unused unit, free whole */
  2538. free_fn(ptr, ai->unit_size);
  2539. continue;
  2540. }
  2541. /* copy and return the unused part */
  2542. memcpy(ptr, __per_cpu_load, ai->static_size);
  2543. free_fn(ptr + size_sum, ai->unit_size - size_sum);
  2544. }
  2545. }
  2546. /* base address is now known, determine group base offsets */
  2547. for (group = 0; group < ai->nr_groups; group++) {
  2548. ai->groups[group].base_offset = areas[group] - base;
  2549. }
  2550. pr_info("Embedded %zu pages/cpu s%zu r%zu d%zu u%zu\n",
  2551. PFN_DOWN(size_sum), ai->static_size, ai->reserved_size,
  2552. ai->dyn_size, ai->unit_size);
  2553. pcpu_setup_first_chunk(ai, base);
  2554. goto out_free;
  2555. out_free_areas:
  2556. for (group = 0; group < ai->nr_groups; group++)
  2557. if (areas[group])
  2558. free_fn(areas[group],
  2559. ai->groups[group].nr_units * ai->unit_size);
  2560. out_free:
  2561. pcpu_free_alloc_info(ai);
  2562. if (areas)
  2563. memblock_free_early(__pa(areas), areas_size);
  2564. return rc;
  2565. }
  2566. #endif /* BUILD_EMBED_FIRST_CHUNK */
  2567. #ifdef BUILD_PAGE_FIRST_CHUNK
  2568. /**
  2569. * pcpu_page_first_chunk - map the first chunk using PAGE_SIZE pages
  2570. * @reserved_size: the size of reserved percpu area in bytes
  2571. * @alloc_fn: function to allocate percpu page, always called with PAGE_SIZE
  2572. * @free_fn: function to free percpu page, always called with PAGE_SIZE
  2573. * @populate_pte_fn: function to populate pte
  2574. *
  2575. * This is a helper to ease setting up page-remapped first percpu
  2576. * chunk and can be called where pcpu_setup_first_chunk() is expected.
  2577. *
  2578. * This is the basic allocator. Static percpu area is allocated
  2579. * page-by-page into vmalloc area.
  2580. *
  2581. * RETURNS:
  2582. * 0 on success, -errno on failure.
  2583. */
  2584. int __init pcpu_page_first_chunk(size_t reserved_size,
  2585. pcpu_fc_alloc_fn_t alloc_fn,
  2586. pcpu_fc_free_fn_t free_fn,
  2587. pcpu_fc_populate_pte_fn_t populate_pte_fn)
  2588. {
  2589. static struct vm_struct vm;
  2590. struct pcpu_alloc_info *ai;
  2591. char psize_str[16];
  2592. int unit_pages;
  2593. size_t pages_size;
  2594. struct page **pages;
  2595. int unit, i, j, rc = 0;
  2596. int upa;
  2597. int nr_g0_units;
  2598. snprintf(psize_str, sizeof(psize_str), "%luK", PAGE_SIZE >> 10);
  2599. ai = pcpu_build_alloc_info(reserved_size, 0, PAGE_SIZE, NULL);
  2600. if (IS_ERR(ai))
  2601. return PTR_ERR(ai);
  2602. BUG_ON(ai->nr_groups != 1);
  2603. upa = ai->alloc_size/ai->unit_size;
  2604. nr_g0_units = roundup(num_possible_cpus(), upa);
  2605. if (WARN_ON(ai->groups[0].nr_units != nr_g0_units)) {
  2606. pcpu_free_alloc_info(ai);
  2607. return -EINVAL;
  2608. }
  2609. unit_pages = ai->unit_size >> PAGE_SHIFT;
  2610. /* unaligned allocations can't be freed, round up to page size */
  2611. pages_size = PFN_ALIGN(unit_pages * num_possible_cpus() *
  2612. sizeof(pages[0]));
  2613. pages = memblock_alloc(pages_size, SMP_CACHE_BYTES);
  2614. if (!pages)
  2615. panic("%s: Failed to allocate %zu bytes\n", __func__,
  2616. pages_size);
  2617. /* allocate pages */
  2618. j = 0;
  2619. for (unit = 0; unit < num_possible_cpus(); unit++) {
  2620. unsigned int cpu = ai->groups[0].cpu_map[unit];
  2621. for (i = 0; i < unit_pages; i++) {
  2622. void *ptr;
  2623. ptr = alloc_fn(cpu, PAGE_SIZE, PAGE_SIZE);
  2624. if (!ptr) {
  2625. pr_warn("failed to allocate %s page for cpu%u\n",
  2626. psize_str, cpu);
  2627. goto enomem;
  2628. }
  2629. /* kmemleak tracks the percpu allocations separately */
  2630. kmemleak_free(ptr);
  2631. pages[j++] = virt_to_page(ptr);
  2632. }
  2633. }
  2634. /* allocate vm area, map the pages and copy static data */
  2635. vm.flags = VM_ALLOC;
  2636. vm.size = num_possible_cpus() * ai->unit_size;
  2637. vm_area_register_early(&vm, PAGE_SIZE);
  2638. for (unit = 0; unit < num_possible_cpus(); unit++) {
  2639. unsigned long unit_addr =
  2640. (unsigned long)vm.addr + unit * ai->unit_size;
  2641. for (i = 0; i < unit_pages; i++)
  2642. populate_pte_fn(unit_addr + (i << PAGE_SHIFT));
  2643. /* pte already populated, the following shouldn't fail */
  2644. rc = __pcpu_map_pages(unit_addr, &pages[unit * unit_pages],
  2645. unit_pages);
  2646. if (rc < 0)
  2647. panic("failed to map percpu area, err=%d\n", rc);
  2648. /*
  2649. * FIXME: Archs with virtual cache should flush local
  2650. * cache for the linear mapping here - something
  2651. * equivalent to flush_cache_vmap() on the local cpu.
  2652. * flush_cache_vmap() can't be used as most supporting
  2653. * data structures are not set up yet.
  2654. */
  2655. /* copy static data */
  2656. memcpy((void *)unit_addr, __per_cpu_load, ai->static_size);
  2657. }
  2658. /* we're ready, commit */
  2659. pr_info("%d %s pages/cpu s%zu r%zu d%zu\n",
  2660. unit_pages, psize_str, ai->static_size,
  2661. ai->reserved_size, ai->dyn_size);
  2662. pcpu_setup_first_chunk(ai, vm.addr);
  2663. goto out_free_ar;
  2664. enomem:
  2665. while (--j >= 0)
  2666. free_fn(page_address(pages[j]), PAGE_SIZE);
  2667. rc = -ENOMEM;
  2668. out_free_ar:
  2669. memblock_free_early(__pa(pages), pages_size);
  2670. pcpu_free_alloc_info(ai);
  2671. return rc;
  2672. }
  2673. #endif /* BUILD_PAGE_FIRST_CHUNK */
  2674. #ifndef CONFIG_HAVE_SETUP_PER_CPU_AREA
  2675. /*
  2676. * Generic SMP percpu area setup.
  2677. *
  2678. * The embedding helper is used because its behavior closely resembles
  2679. * the original non-dynamic generic percpu area setup. This is
  2680. * important because many archs have addressing restrictions and might
  2681. * fail if the percpu area is located far away from the previous
  2682. * location. As an added bonus, in non-NUMA cases, embedding is
  2683. * generally a good idea TLB-wise because percpu area can piggy back
  2684. * on the physical linear memory mapping which uses large page
  2685. * mappings on applicable archs.
  2686. */
  2687. unsigned long __per_cpu_offset[NR_CPUS] __read_mostly;
  2688. EXPORT_SYMBOL(__per_cpu_offset);
  2689. static void * __init pcpu_dfl_fc_alloc(unsigned int cpu, size_t size,
  2690. size_t align)
  2691. {
  2692. return memblock_alloc_from(size, align, __pa(MAX_DMA_ADDRESS));
  2693. }
  2694. static void __init pcpu_dfl_fc_free(void *ptr, size_t size)
  2695. {
  2696. memblock_free_early(__pa(ptr), size);
  2697. }
  2698. void __init setup_per_cpu_areas(void)
  2699. {
  2700. unsigned long delta;
  2701. unsigned int cpu;
  2702. int rc;
  2703. /*
  2704. * Always reserve area for module percpu variables. That's
  2705. * what the legacy allocator did.
  2706. */
  2707. rc = pcpu_embed_first_chunk(PERCPU_MODULE_RESERVE,
  2708. PERCPU_DYNAMIC_RESERVE, PAGE_SIZE, NULL,
  2709. pcpu_dfl_fc_alloc, pcpu_dfl_fc_free);
  2710. if (rc < 0)
  2711. panic("Failed to initialize percpu areas.");
  2712. delta = (unsigned long)pcpu_base_addr - (unsigned long)__per_cpu_start;
  2713. for_each_possible_cpu(cpu)
  2714. __per_cpu_offset[cpu] = delta + pcpu_unit_offsets[cpu];
  2715. }
  2716. #endif /* CONFIG_HAVE_SETUP_PER_CPU_AREA */
  2717. #else /* CONFIG_SMP */
  2718. /*
  2719. * UP percpu area setup.
  2720. *
  2721. * UP always uses km-based percpu allocator with identity mapping.
  2722. * Static percpu variables are indistinguishable from the usual static
  2723. * variables and don't require any special preparation.
  2724. */
  2725. void __init setup_per_cpu_areas(void)
  2726. {
  2727. const size_t unit_size =
  2728. roundup_pow_of_two(max_t(size_t, PCPU_MIN_UNIT_SIZE,
  2729. PERCPU_DYNAMIC_RESERVE));
  2730. struct pcpu_alloc_info *ai;
  2731. void *fc;
  2732. ai = pcpu_alloc_alloc_info(1, 1);
  2733. fc = memblock_alloc_from(unit_size, PAGE_SIZE, __pa(MAX_DMA_ADDRESS));
  2734. if (!ai || !fc)
  2735. panic("Failed to allocate memory for percpu areas.");
  2736. /* kmemleak tracks the percpu allocations separately */
  2737. kmemleak_free(fc);
  2738. ai->dyn_size = unit_size;
  2739. ai->unit_size = unit_size;
  2740. ai->atom_size = unit_size;
  2741. ai->alloc_size = unit_size;
  2742. ai->groups[0].nr_units = 1;
  2743. ai->groups[0].cpu_map[0] = 0;
  2744. pcpu_setup_first_chunk(ai, fc);
  2745. pcpu_free_alloc_info(ai);
  2746. }
  2747. #endif /* CONFIG_SMP */
  2748. /*
  2749. * pcpu_nr_pages - calculate total number of populated backing pages
  2750. *
  2751. * This reflects the number of pages populated to back chunks. Metadata is
  2752. * excluded in the number exposed in meminfo as the number of backing pages
  2753. * scales with the number of cpus and can quickly outweigh the memory used for
  2754. * metadata. It also keeps this calculation nice and simple.
  2755. *
  2756. * RETURNS:
  2757. * Total number of populated backing pages in use by the allocator.
  2758. */
  2759. unsigned long pcpu_nr_pages(void)
  2760. {
  2761. return pcpu_nr_populated * pcpu_nr_units;
  2762. }
  2763. EXPORT_SYMBOL_GPL(pcpu_nr_pages);
  2764. /*
  2765. * Percpu allocator is initialized early during boot when neither slab or
  2766. * workqueue is available. Plug async management until everything is up
  2767. * and running.
  2768. */
  2769. static int __init percpu_enable_async(void)
  2770. {
  2771. pcpu_async_enabled = true;
  2772. return 0;
  2773. }
  2774. subsys_initcall(percpu_enable_async);