page_alloc.c 91 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882188318841885188618871888188918901891189218931894189518961897189818991900190119021903190419051906190719081909191019111912191319141915191619171918191919201921192219231924192519261927192819291930193119321933193419351936193719381939194019411942194319441945194619471948194919501951195219531954195519561957195819591960196119621963196419651966196719681969197019711972197319741975197619771978197919801981198219831984198519861987198819891990199119921993199419951996199719981999200020012002200320042005200620072008200920102011201220132014201520162017201820192020202120222023202420252026202720282029203020312032203320342035203620372038203920402041204220432044204520462047204820492050205120522053205420552056205720582059206020612062206320642065206620672068206920702071207220732074207520762077207820792080208120822083208420852086208720882089209020912092209320942095209620972098209921002101210221032104210521062107210821092110211121122113211421152116211721182119212021212122212321242125212621272128212921302131213221332134213521362137213821392140214121422143214421452146214721482149215021512152215321542155215621572158215921602161216221632164216521662167216821692170217121722173217421752176217721782179218021812182218321842185218621872188218921902191219221932194219521962197219821992200220122022203220422052206220722082209221022112212221322142215221622172218221922202221222222232224222522262227222822292230223122322233223422352236223722382239224022412242224322442245224622472248224922502251225222532254225522562257225822592260226122622263226422652266226722682269227022712272227322742275227622772278227922802281228222832284228522862287228822892290229122922293229422952296229722982299230023012302230323042305230623072308230923102311231223132314231523162317231823192320232123222323232423252326232723282329233023312332233323342335233623372338233923402341234223432344234523462347234823492350235123522353235423552356235723582359236023612362236323642365236623672368236923702371237223732374237523762377237823792380238123822383238423852386238723882389239023912392239323942395239623972398239924002401240224032404240524062407240824092410241124122413241424152416241724182419242024212422242324242425242624272428242924302431243224332434243524362437243824392440244124422443244424452446244724482449245024512452245324542455245624572458245924602461246224632464246524662467246824692470247124722473247424752476247724782479248024812482248324842485248624872488248924902491249224932494249524962497249824992500250125022503250425052506250725082509251025112512251325142515251625172518251925202521252225232524252525262527252825292530253125322533253425352536253725382539254025412542254325442545254625472548254925502551255225532554255525562557255825592560256125622563256425652566256725682569257025712572257325742575257625772578257925802581258225832584258525862587258825892590259125922593259425952596259725982599260026012602260326042605260626072608260926102611261226132614261526162617261826192620262126222623262426252626262726282629263026312632263326342635263626372638263926402641264226432644264526462647264826492650265126522653265426552656265726582659266026612662266326642665266626672668266926702671267226732674267526762677267826792680268126822683268426852686268726882689269026912692269326942695269626972698269927002701270227032704270527062707270827092710271127122713271427152716271727182719272027212722272327242725272627272728272927302731273227332734273527362737273827392740274127422743274427452746274727482749275027512752275327542755275627572758275927602761276227632764276527662767276827692770277127722773277427752776277727782779278027812782278327842785278627872788278927902791279227932794279527962797279827992800280128022803280428052806280728082809281028112812281328142815281628172818281928202821282228232824282528262827282828292830283128322833283428352836283728382839284028412842284328442845284628472848284928502851285228532854285528562857285828592860286128622863286428652866286728682869287028712872287328742875287628772878287928802881288228832884288528862887288828892890289128922893289428952896289728982899290029012902290329042905290629072908290929102911291229132914291529162917291829192920292129222923292429252926292729282929293029312932293329342935293629372938293929402941294229432944294529462947294829492950295129522953295429552956295729582959296029612962296329642965296629672968296929702971297229732974297529762977297829792980298129822983298429852986298729882989299029912992299329942995299629972998299930003001300230033004300530063007300830093010301130123013301430153016301730183019302030213022302330243025302630273028302930303031303230333034303530363037303830393040304130423043304430453046304730483049305030513052305330543055305630573058305930603061306230633064306530663067306830693070307130723073307430753076307730783079308030813082308330843085308630873088308930903091309230933094309530963097309830993100310131023103310431053106310731083109311031113112311331143115311631173118311931203121312231233124312531263127312831293130313131323133313431353136313731383139314031413142314331443145314631473148314931503151315231533154315531563157315831593160316131623163316431653166316731683169317031713172317331743175317631773178317931803181318231833184318531863187318831893190319131923193319431953196319731983199320032013202320332043205320632073208320932103211321232133214321532163217321832193220322132223223322432253226322732283229323032313232323332343235323632373238323932403241324232433244324532463247324832493250325132523253325432553256325732583259326032613262326332643265326632673268326932703271327232733274327532763277327832793280328132823283328432853286328732883289329032913292329332943295329632973298329933003301330233033304330533063307330833093310331133123313331433153316331733183319332033213322332333243325332633273328332933303331333233333334333533363337333833393340334133423343334433453346334733483349335033513352335333543355335633573358335933603361336233633364336533663367336833693370337133723373337433753376337733783379338033813382338333843385338633873388338933903391339233933394
  1. /*
  2. * linux/mm/page_alloc.c
  3. *
  4. * Manages the free list, the system allocates free pages here.
  5. * Note that kmalloc() lives in slab.c
  6. *
  7. * Copyright (C) 1991, 1992, 1993, 1994 Linus Torvalds
  8. * Swap reorganised 29.12.95, Stephen Tweedie
  9. * Support of BIGMEM added by Gerhard Wichert, Siemens AG, July 1999
  10. * Reshaped it to be a zoned allocator, Ingo Molnar, Red Hat, 1999
  11. * Discontiguous memory support, Kanoj Sarcar, SGI, Nov 1999
  12. * Zone balancing, Kanoj Sarcar, SGI, Jan 2000
  13. * Per cpu hot/cold page lists, bulk allocation, Martin J. Bligh, Sept 2002
  14. * (lots of bits borrowed from Ingo Molnar & Andrew Morton)
  15. */
  16. #include <linux/stddef.h>
  17. #include <linux/mm.h>
  18. #include <linux/swap.h>
  19. #include <linux/interrupt.h>
  20. #include <linux/pagemap.h>
  21. #include <linux/bootmem.h>
  22. #include <linux/compiler.h>
  23. #include <linux/kernel.h>
  24. #include <linux/module.h>
  25. #include <linux/suspend.h>
  26. #include <linux/pagevec.h>
  27. #include <linux/blkdev.h>
  28. #include <linux/slab.h>
  29. #include <linux/notifier.h>
  30. #include <linux/topology.h>
  31. #include <linux/sysctl.h>
  32. #include <linux/cpu.h>
  33. #include <linux/cpuset.h>
  34. #include <linux/memory_hotplug.h>
  35. #include <linux/nodemask.h>
  36. #include <linux/vmalloc.h>
  37. #include <linux/mempolicy.h>
  38. #include <linux/stop_machine.h>
  39. #include <linux/sort.h>
  40. #include <linux/pfn.h>
  41. #include <linux/backing-dev.h>
  42. #include <linux/fault-inject.h>
  43. #include <asm/tlbflush.h>
  44. #include <asm/div64.h>
  45. #include "internal.h"
  46. /*
  47. * MCD - HACK: Find somewhere to initialize this EARLY, or make this
  48. * initializer cleaner
  49. */
  50. nodemask_t node_online_map __read_mostly = { { [0] = 1UL } };
  51. EXPORT_SYMBOL(node_online_map);
  52. nodemask_t node_possible_map __read_mostly = NODE_MASK_ALL;
  53. EXPORT_SYMBOL(node_possible_map);
  54. unsigned long totalram_pages __read_mostly;
  55. unsigned long totalreserve_pages __read_mostly;
  56. long nr_swap_pages;
  57. int percpu_pagelist_fraction;
  58. static void __free_pages_ok(struct page *page, unsigned int order);
  59. /*
  60. * results with 256, 32 in the lowmem_reserve sysctl:
  61. * 1G machine -> (16M dma, 800M-16M normal, 1G-800M high)
  62. * 1G machine -> (16M dma, 784M normal, 224M high)
  63. * NORMAL allocation will leave 784M/256 of ram reserved in the ZONE_DMA
  64. * HIGHMEM allocation will leave 224M/32 of ram reserved in ZONE_NORMAL
  65. * HIGHMEM allocation will (224M+784M)/256 of ram reserved in ZONE_DMA
  66. *
  67. * TBD: should special case ZONE_DMA32 machines here - in those we normally
  68. * don't need any ZONE_NORMAL reservation
  69. */
  70. int sysctl_lowmem_reserve_ratio[MAX_NR_ZONES-1] = {
  71. #ifdef CONFIG_ZONE_DMA
  72. 256,
  73. #endif
  74. #ifdef CONFIG_ZONE_DMA32
  75. 256,
  76. #endif
  77. #ifdef CONFIG_HIGHMEM
  78. 32
  79. #endif
  80. };
  81. EXPORT_SYMBOL(totalram_pages);
  82. static char * const zone_names[MAX_NR_ZONES] = {
  83. #ifdef CONFIG_ZONE_DMA
  84. "DMA",
  85. #endif
  86. #ifdef CONFIG_ZONE_DMA32
  87. "DMA32",
  88. #endif
  89. "Normal",
  90. #ifdef CONFIG_HIGHMEM
  91. "HighMem"
  92. #endif
  93. };
  94. int min_free_kbytes = 1024;
  95. unsigned long __meminitdata nr_kernel_pages;
  96. unsigned long __meminitdata nr_all_pages;
  97. static unsigned long __initdata dma_reserve;
  98. #ifdef CONFIG_ARCH_POPULATES_NODE_MAP
  99. /*
  100. * MAX_ACTIVE_REGIONS determines the maxmimum number of distinct
  101. * ranges of memory (RAM) that may be registered with add_active_range().
  102. * Ranges passed to add_active_range() will be merged if possible
  103. * so the number of times add_active_range() can be called is
  104. * related to the number of nodes and the number of holes
  105. */
  106. #ifdef CONFIG_MAX_ACTIVE_REGIONS
  107. /* Allow an architecture to set MAX_ACTIVE_REGIONS to save memory */
  108. #define MAX_ACTIVE_REGIONS CONFIG_MAX_ACTIVE_REGIONS
  109. #else
  110. #if MAX_NUMNODES >= 32
  111. /* If there can be many nodes, allow up to 50 holes per node */
  112. #define MAX_ACTIVE_REGIONS (MAX_NUMNODES*50)
  113. #else
  114. /* By default, allow up to 256 distinct regions */
  115. #define MAX_ACTIVE_REGIONS 256
  116. #endif
  117. #endif
  118. struct node_active_region __initdata early_node_map[MAX_ACTIVE_REGIONS];
  119. int __initdata nr_nodemap_entries;
  120. unsigned long __initdata arch_zone_lowest_possible_pfn[MAX_NR_ZONES];
  121. unsigned long __initdata arch_zone_highest_possible_pfn[MAX_NR_ZONES];
  122. #ifdef CONFIG_MEMORY_HOTPLUG_RESERVE
  123. unsigned long __initdata node_boundary_start_pfn[MAX_NUMNODES];
  124. unsigned long __initdata node_boundary_end_pfn[MAX_NUMNODES];
  125. #endif /* CONFIG_MEMORY_HOTPLUG_RESERVE */
  126. #endif /* CONFIG_ARCH_POPULATES_NODE_MAP */
  127. #ifdef CONFIG_DEBUG_VM
  128. static int page_outside_zone_boundaries(struct zone *zone, struct page *page)
  129. {
  130. int ret = 0;
  131. unsigned seq;
  132. unsigned long pfn = page_to_pfn(page);
  133. do {
  134. seq = zone_span_seqbegin(zone);
  135. if (pfn >= zone->zone_start_pfn + zone->spanned_pages)
  136. ret = 1;
  137. else if (pfn < zone->zone_start_pfn)
  138. ret = 1;
  139. } while (zone_span_seqretry(zone, seq));
  140. return ret;
  141. }
  142. static int page_is_consistent(struct zone *zone, struct page *page)
  143. {
  144. #ifdef CONFIG_HOLES_IN_ZONE
  145. if (!pfn_valid(page_to_pfn(page)))
  146. return 0;
  147. #endif
  148. if (zone != page_zone(page))
  149. return 0;
  150. return 1;
  151. }
  152. /*
  153. * Temporary debugging check for pages not lying within a given zone.
  154. */
  155. static int bad_range(struct zone *zone, struct page *page)
  156. {
  157. if (page_outside_zone_boundaries(zone, page))
  158. return 1;
  159. if (!page_is_consistent(zone, page))
  160. return 1;
  161. return 0;
  162. }
  163. #else
  164. static inline int bad_range(struct zone *zone, struct page *page)
  165. {
  166. return 0;
  167. }
  168. #endif
  169. static void bad_page(struct page *page)
  170. {
  171. printk(KERN_EMERG "Bad page state in process '%s'\n"
  172. KERN_EMERG "page:%p flags:0x%0*lx mapping:%p mapcount:%d count:%d\n"
  173. KERN_EMERG "Trying to fix it up, but a reboot is needed\n"
  174. KERN_EMERG "Backtrace:\n",
  175. current->comm, page, (int)(2*sizeof(unsigned long)),
  176. (unsigned long)page->flags, page->mapping,
  177. page_mapcount(page), page_count(page));
  178. dump_stack();
  179. page->flags &= ~(1 << PG_lru |
  180. 1 << PG_private |
  181. 1 << PG_locked |
  182. 1 << PG_active |
  183. 1 << PG_dirty |
  184. 1 << PG_reclaim |
  185. 1 << PG_slab |
  186. 1 << PG_swapcache |
  187. 1 << PG_writeback |
  188. 1 << PG_buddy );
  189. set_page_count(page, 0);
  190. reset_page_mapcount(page);
  191. page->mapping = NULL;
  192. add_taint(TAINT_BAD_PAGE);
  193. }
  194. /*
  195. * Higher-order pages are called "compound pages". They are structured thusly:
  196. *
  197. * The first PAGE_SIZE page is called the "head page".
  198. *
  199. * The remaining PAGE_SIZE pages are called "tail pages".
  200. *
  201. * All pages have PG_compound set. All pages have their ->private pointing at
  202. * the head page (even the head page has this).
  203. *
  204. * The first tail page's ->lru.next holds the address of the compound page's
  205. * put_page() function. Its ->lru.prev holds the order of allocation.
  206. * This usage means that zero-order pages may not be compound.
  207. */
  208. static void free_compound_page(struct page *page)
  209. {
  210. __free_pages_ok(page, (unsigned long)page[1].lru.prev);
  211. }
  212. static void prep_compound_page(struct page *page, unsigned long order)
  213. {
  214. int i;
  215. int nr_pages = 1 << order;
  216. set_compound_page_dtor(page, free_compound_page);
  217. page[1].lru.prev = (void *)order;
  218. for (i = 0; i < nr_pages; i++) {
  219. struct page *p = page + i;
  220. __SetPageCompound(p);
  221. set_page_private(p, (unsigned long)page);
  222. }
  223. }
  224. static void destroy_compound_page(struct page *page, unsigned long order)
  225. {
  226. int i;
  227. int nr_pages = 1 << order;
  228. if (unlikely((unsigned long)page[1].lru.prev != order))
  229. bad_page(page);
  230. for (i = 0; i < nr_pages; i++) {
  231. struct page *p = page + i;
  232. if (unlikely(!PageCompound(p) |
  233. (page_private(p) != (unsigned long)page)))
  234. bad_page(page);
  235. __ClearPageCompound(p);
  236. }
  237. }
  238. static inline void prep_zero_page(struct page *page, int order, gfp_t gfp_flags)
  239. {
  240. int i;
  241. VM_BUG_ON((gfp_flags & (__GFP_WAIT | __GFP_HIGHMEM)) == __GFP_HIGHMEM);
  242. /*
  243. * clear_highpage() will use KM_USER0, so it's a bug to use __GFP_ZERO
  244. * and __GFP_HIGHMEM from hard or soft interrupt context.
  245. */
  246. VM_BUG_ON((gfp_flags & __GFP_HIGHMEM) && in_interrupt());
  247. for (i = 0; i < (1 << order); i++)
  248. clear_highpage(page + i);
  249. }
  250. /*
  251. * function for dealing with page's order in buddy system.
  252. * zone->lock is already acquired when we use these.
  253. * So, we don't need atomic page->flags operations here.
  254. */
  255. static inline unsigned long page_order(struct page *page)
  256. {
  257. return page_private(page);
  258. }
  259. static inline void set_page_order(struct page *page, int order)
  260. {
  261. set_page_private(page, order);
  262. __SetPageBuddy(page);
  263. }
  264. static inline void rmv_page_order(struct page *page)
  265. {
  266. __ClearPageBuddy(page);
  267. set_page_private(page, 0);
  268. }
  269. /*
  270. * Locate the struct page for both the matching buddy in our
  271. * pair (buddy1) and the combined O(n+1) page they form (page).
  272. *
  273. * 1) Any buddy B1 will have an order O twin B2 which satisfies
  274. * the following equation:
  275. * B2 = B1 ^ (1 << O)
  276. * For example, if the starting buddy (buddy2) is #8 its order
  277. * 1 buddy is #10:
  278. * B2 = 8 ^ (1 << 1) = 8 ^ 2 = 10
  279. *
  280. * 2) Any buddy B will have an order O+1 parent P which
  281. * satisfies the following equation:
  282. * P = B & ~(1 << O)
  283. *
  284. * Assumption: *_mem_map is contiguous at least up to MAX_ORDER
  285. */
  286. static inline struct page *
  287. __page_find_buddy(struct page *page, unsigned long page_idx, unsigned int order)
  288. {
  289. unsigned long buddy_idx = page_idx ^ (1 << order);
  290. return page + (buddy_idx - page_idx);
  291. }
  292. static inline unsigned long
  293. __find_combined_index(unsigned long page_idx, unsigned int order)
  294. {
  295. return (page_idx & ~(1 << order));
  296. }
  297. /*
  298. * This function checks whether a page is free && is the buddy
  299. * we can do coalesce a page and its buddy if
  300. * (a) the buddy is not in a hole &&
  301. * (b) the buddy is in the buddy system &&
  302. * (c) a page and its buddy have the same order &&
  303. * (d) a page and its buddy are in the same zone.
  304. *
  305. * For recording whether a page is in the buddy system, we use PG_buddy.
  306. * Setting, clearing, and testing PG_buddy is serialized by zone->lock.
  307. *
  308. * For recording page's order, we use page_private(page).
  309. */
  310. static inline int page_is_buddy(struct page *page, struct page *buddy,
  311. int order)
  312. {
  313. #ifdef CONFIG_HOLES_IN_ZONE
  314. if (!pfn_valid(page_to_pfn(buddy)))
  315. return 0;
  316. #endif
  317. if (page_zone_id(page) != page_zone_id(buddy))
  318. return 0;
  319. if (PageBuddy(buddy) && page_order(buddy) == order) {
  320. BUG_ON(page_count(buddy) != 0);
  321. return 1;
  322. }
  323. return 0;
  324. }
  325. /*
  326. * Freeing function for a buddy system allocator.
  327. *
  328. * The concept of a buddy system is to maintain direct-mapped table
  329. * (containing bit values) for memory blocks of various "orders".
  330. * The bottom level table contains the map for the smallest allocatable
  331. * units of memory (here, pages), and each level above it describes
  332. * pairs of units from the levels below, hence, "buddies".
  333. * At a high level, all that happens here is marking the table entry
  334. * at the bottom level available, and propagating the changes upward
  335. * as necessary, plus some accounting needed to play nicely with other
  336. * parts of the VM system.
  337. * At each level, we keep a list of pages, which are heads of continuous
  338. * free pages of length of (1 << order) and marked with PG_buddy. Page's
  339. * order is recorded in page_private(page) field.
  340. * So when we are allocating or freeing one, we can derive the state of the
  341. * other. That is, if we allocate a small block, and both were
  342. * free, the remainder of the region must be split into blocks.
  343. * If a block is freed, and its buddy is also free, then this
  344. * triggers coalescing into a block of larger size.
  345. *
  346. * -- wli
  347. */
  348. static inline void __free_one_page(struct page *page,
  349. struct zone *zone, unsigned int order)
  350. {
  351. unsigned long page_idx;
  352. int order_size = 1 << order;
  353. if (unlikely(PageCompound(page)))
  354. destroy_compound_page(page, order);
  355. page_idx = page_to_pfn(page) & ((1 << MAX_ORDER) - 1);
  356. VM_BUG_ON(page_idx & (order_size - 1));
  357. VM_BUG_ON(bad_range(zone, page));
  358. __mod_zone_page_state(zone, NR_FREE_PAGES, order_size);
  359. while (order < MAX_ORDER-1) {
  360. unsigned long combined_idx;
  361. struct free_area *area;
  362. struct page *buddy;
  363. buddy = __page_find_buddy(page, page_idx, order);
  364. if (!page_is_buddy(page, buddy, order))
  365. break; /* Move the buddy up one level. */
  366. list_del(&buddy->lru);
  367. area = zone->free_area + order;
  368. area->nr_free--;
  369. rmv_page_order(buddy);
  370. combined_idx = __find_combined_index(page_idx, order);
  371. page = page + (combined_idx - page_idx);
  372. page_idx = combined_idx;
  373. order++;
  374. }
  375. set_page_order(page, order);
  376. list_add(&page->lru, &zone->free_area[order].free_list);
  377. zone->free_area[order].nr_free++;
  378. }
  379. static inline int free_pages_check(struct page *page)
  380. {
  381. if (unlikely(page_mapcount(page) |
  382. (page->mapping != NULL) |
  383. (page_count(page) != 0) |
  384. (page->flags & (
  385. 1 << PG_lru |
  386. 1 << PG_private |
  387. 1 << PG_locked |
  388. 1 << PG_active |
  389. 1 << PG_reclaim |
  390. 1 << PG_slab |
  391. 1 << PG_swapcache |
  392. 1 << PG_writeback |
  393. 1 << PG_reserved |
  394. 1 << PG_buddy ))))
  395. bad_page(page);
  396. if (PageDirty(page))
  397. __ClearPageDirty(page);
  398. /*
  399. * For now, we report if PG_reserved was found set, but do not
  400. * clear it, and do not free the page. But we shall soon need
  401. * to do more, for when the ZERO_PAGE count wraps negative.
  402. */
  403. return PageReserved(page);
  404. }
  405. /*
  406. * Frees a list of pages.
  407. * Assumes all pages on list are in same zone, and of same order.
  408. * count is the number of pages to free.
  409. *
  410. * If the zone was previously in an "all pages pinned" state then look to
  411. * see if this freeing clears that state.
  412. *
  413. * And clear the zone's pages_scanned counter, to hold off the "all pages are
  414. * pinned" detection logic.
  415. */
  416. static void free_pages_bulk(struct zone *zone, int count,
  417. struct list_head *list, int order)
  418. {
  419. spin_lock(&zone->lock);
  420. zone->all_unreclaimable = 0;
  421. zone->pages_scanned = 0;
  422. while (count--) {
  423. struct page *page;
  424. VM_BUG_ON(list_empty(list));
  425. page = list_entry(list->prev, struct page, lru);
  426. /* have to delete it as __free_one_page list manipulates */
  427. list_del(&page->lru);
  428. __free_one_page(page, zone, order);
  429. }
  430. spin_unlock(&zone->lock);
  431. }
  432. static void free_one_page(struct zone *zone, struct page *page, int order)
  433. {
  434. spin_lock(&zone->lock);
  435. zone->all_unreclaimable = 0;
  436. zone->pages_scanned = 0;
  437. __free_one_page(page, zone, order);
  438. spin_unlock(&zone->lock);
  439. }
  440. static void __free_pages_ok(struct page *page, unsigned int order)
  441. {
  442. unsigned long flags;
  443. int i;
  444. int reserved = 0;
  445. for (i = 0 ; i < (1 << order) ; ++i)
  446. reserved += free_pages_check(page + i);
  447. if (reserved)
  448. return;
  449. if (!PageHighMem(page))
  450. debug_check_no_locks_freed(page_address(page),PAGE_SIZE<<order);
  451. arch_free_page(page, order);
  452. kernel_map_pages(page, 1 << order, 0);
  453. local_irq_save(flags);
  454. __count_vm_events(PGFREE, 1 << order);
  455. free_one_page(page_zone(page), page, order);
  456. local_irq_restore(flags);
  457. }
  458. /*
  459. * permit the bootmem allocator to evade page validation on high-order frees
  460. */
  461. void fastcall __init __free_pages_bootmem(struct page *page, unsigned int order)
  462. {
  463. if (order == 0) {
  464. __ClearPageReserved(page);
  465. set_page_count(page, 0);
  466. set_page_refcounted(page);
  467. __free_page(page);
  468. } else {
  469. int loop;
  470. prefetchw(page);
  471. for (loop = 0; loop < BITS_PER_LONG; loop++) {
  472. struct page *p = &page[loop];
  473. if (loop + 1 < BITS_PER_LONG)
  474. prefetchw(p + 1);
  475. __ClearPageReserved(p);
  476. set_page_count(p, 0);
  477. }
  478. set_page_refcounted(page);
  479. __free_pages(page, order);
  480. }
  481. }
  482. /*
  483. * The order of subdivision here is critical for the IO subsystem.
  484. * Please do not alter this order without good reasons and regression
  485. * testing. Specifically, as large blocks of memory are subdivided,
  486. * the order in which smaller blocks are delivered depends on the order
  487. * they're subdivided in this function. This is the primary factor
  488. * influencing the order in which pages are delivered to the IO
  489. * subsystem according to empirical testing, and this is also justified
  490. * by considering the behavior of a buddy system containing a single
  491. * large block of memory acted on by a series of small allocations.
  492. * This behavior is a critical factor in sglist merging's success.
  493. *
  494. * -- wli
  495. */
  496. static inline void expand(struct zone *zone, struct page *page,
  497. int low, int high, struct free_area *area)
  498. {
  499. unsigned long size = 1 << high;
  500. while (high > low) {
  501. area--;
  502. high--;
  503. size >>= 1;
  504. VM_BUG_ON(bad_range(zone, &page[size]));
  505. list_add(&page[size].lru, &area->free_list);
  506. area->nr_free++;
  507. set_page_order(&page[size], high);
  508. }
  509. }
  510. /*
  511. * This page is about to be returned from the page allocator
  512. */
  513. static int prep_new_page(struct page *page, int order, gfp_t gfp_flags)
  514. {
  515. if (unlikely(page_mapcount(page) |
  516. (page->mapping != NULL) |
  517. (page_count(page) != 0) |
  518. (page->flags & (
  519. 1 << PG_lru |
  520. 1 << PG_private |
  521. 1 << PG_locked |
  522. 1 << PG_active |
  523. 1 << PG_dirty |
  524. 1 << PG_reclaim |
  525. 1 << PG_slab |
  526. 1 << PG_swapcache |
  527. 1 << PG_writeback |
  528. 1 << PG_reserved |
  529. 1 << PG_buddy ))))
  530. bad_page(page);
  531. /*
  532. * For now, we report if PG_reserved was found set, but do not
  533. * clear it, and do not allocate the page: as a safety net.
  534. */
  535. if (PageReserved(page))
  536. return 1;
  537. page->flags &= ~(1 << PG_uptodate | 1 << PG_error |
  538. 1 << PG_referenced | 1 << PG_arch_1 |
  539. 1 << PG_owner_priv_1 | 1 << PG_mappedtodisk);
  540. set_page_private(page, 0);
  541. set_page_refcounted(page);
  542. arch_alloc_page(page, order);
  543. kernel_map_pages(page, 1 << order, 1);
  544. if (gfp_flags & __GFP_ZERO)
  545. prep_zero_page(page, order, gfp_flags);
  546. if (order && (gfp_flags & __GFP_COMP))
  547. prep_compound_page(page, order);
  548. return 0;
  549. }
  550. /*
  551. * Do the hard work of removing an element from the buddy allocator.
  552. * Call me with the zone->lock already held.
  553. */
  554. static struct page *__rmqueue(struct zone *zone, unsigned int order)
  555. {
  556. struct free_area * area;
  557. unsigned int current_order;
  558. struct page *page;
  559. for (current_order = order; current_order < MAX_ORDER; ++current_order) {
  560. area = zone->free_area + current_order;
  561. if (list_empty(&area->free_list))
  562. continue;
  563. page = list_entry(area->free_list.next, struct page, lru);
  564. list_del(&page->lru);
  565. rmv_page_order(page);
  566. area->nr_free--;
  567. __mod_zone_page_state(zone, NR_FREE_PAGES, - (1UL << order));
  568. expand(zone, page, order, current_order, area);
  569. return page;
  570. }
  571. return NULL;
  572. }
  573. /*
  574. * Obtain a specified number of elements from the buddy allocator, all under
  575. * a single hold of the lock, for efficiency. Add them to the supplied list.
  576. * Returns the number of new pages which were placed at *list.
  577. */
  578. static int rmqueue_bulk(struct zone *zone, unsigned int order,
  579. unsigned long count, struct list_head *list)
  580. {
  581. int i;
  582. spin_lock(&zone->lock);
  583. for (i = 0; i < count; ++i) {
  584. struct page *page = __rmqueue(zone, order);
  585. if (unlikely(page == NULL))
  586. break;
  587. list_add_tail(&page->lru, list);
  588. }
  589. spin_unlock(&zone->lock);
  590. return i;
  591. }
  592. #if MAX_NUMNODES > 1
  593. int nr_node_ids __read_mostly = MAX_NUMNODES;
  594. EXPORT_SYMBOL(nr_node_ids);
  595. /*
  596. * Figure out the number of possible node ids.
  597. */
  598. static void __init setup_nr_node_ids(void)
  599. {
  600. unsigned int node;
  601. unsigned int highest = 0;
  602. for_each_node_mask(node, node_possible_map)
  603. highest = node;
  604. nr_node_ids = highest + 1;
  605. }
  606. #else
  607. static void __init setup_nr_node_ids(void) {}
  608. #endif
  609. #ifdef CONFIG_NUMA
  610. /*
  611. * Called from the slab reaper to drain pagesets on a particular node that
  612. * belongs to the currently executing processor.
  613. * Note that this function must be called with the thread pinned to
  614. * a single processor.
  615. */
  616. void drain_node_pages(int nodeid)
  617. {
  618. int i;
  619. enum zone_type z;
  620. unsigned long flags;
  621. for (z = 0; z < MAX_NR_ZONES; z++) {
  622. struct zone *zone = NODE_DATA(nodeid)->node_zones + z;
  623. struct per_cpu_pageset *pset;
  624. if (!populated_zone(zone))
  625. continue;
  626. pset = zone_pcp(zone, smp_processor_id());
  627. for (i = 0; i < ARRAY_SIZE(pset->pcp); i++) {
  628. struct per_cpu_pages *pcp;
  629. pcp = &pset->pcp[i];
  630. if (pcp->count) {
  631. int to_drain;
  632. local_irq_save(flags);
  633. if (pcp->count >= pcp->batch)
  634. to_drain = pcp->batch;
  635. else
  636. to_drain = pcp->count;
  637. free_pages_bulk(zone, to_drain, &pcp->list, 0);
  638. pcp->count -= to_drain;
  639. local_irq_restore(flags);
  640. }
  641. }
  642. }
  643. }
  644. #endif
  645. static void __drain_pages(unsigned int cpu)
  646. {
  647. unsigned long flags;
  648. struct zone *zone;
  649. int i;
  650. for_each_zone(zone) {
  651. struct per_cpu_pageset *pset;
  652. if (!populated_zone(zone))
  653. continue;
  654. pset = zone_pcp(zone, cpu);
  655. for (i = 0; i < ARRAY_SIZE(pset->pcp); i++) {
  656. struct per_cpu_pages *pcp;
  657. pcp = &pset->pcp[i];
  658. local_irq_save(flags);
  659. free_pages_bulk(zone, pcp->count, &pcp->list, 0);
  660. pcp->count = 0;
  661. local_irq_restore(flags);
  662. }
  663. }
  664. }
  665. #ifdef CONFIG_PM
  666. void mark_free_pages(struct zone *zone)
  667. {
  668. unsigned long pfn, max_zone_pfn;
  669. unsigned long flags;
  670. int order;
  671. struct list_head *curr;
  672. if (!zone->spanned_pages)
  673. return;
  674. spin_lock_irqsave(&zone->lock, flags);
  675. max_zone_pfn = zone->zone_start_pfn + zone->spanned_pages;
  676. for (pfn = zone->zone_start_pfn; pfn < max_zone_pfn; pfn++)
  677. if (pfn_valid(pfn)) {
  678. struct page *page = pfn_to_page(pfn);
  679. if (!PageNosave(page))
  680. ClearPageNosaveFree(page);
  681. }
  682. for (order = MAX_ORDER - 1; order >= 0; --order)
  683. list_for_each(curr, &zone->free_area[order].free_list) {
  684. unsigned long i;
  685. pfn = page_to_pfn(list_entry(curr, struct page, lru));
  686. for (i = 0; i < (1UL << order); i++)
  687. SetPageNosaveFree(pfn_to_page(pfn + i));
  688. }
  689. spin_unlock_irqrestore(&zone->lock, flags);
  690. }
  691. /*
  692. * Spill all of this CPU's per-cpu pages back into the buddy allocator.
  693. */
  694. void drain_local_pages(void)
  695. {
  696. unsigned long flags;
  697. local_irq_save(flags);
  698. __drain_pages(smp_processor_id());
  699. local_irq_restore(flags);
  700. }
  701. #endif /* CONFIG_PM */
  702. /*
  703. * Free a 0-order page
  704. */
  705. static void fastcall free_hot_cold_page(struct page *page, int cold)
  706. {
  707. struct zone *zone = page_zone(page);
  708. struct per_cpu_pages *pcp;
  709. unsigned long flags;
  710. if (PageAnon(page))
  711. page->mapping = NULL;
  712. if (free_pages_check(page))
  713. return;
  714. if (!PageHighMem(page))
  715. debug_check_no_locks_freed(page_address(page), PAGE_SIZE);
  716. arch_free_page(page, 0);
  717. kernel_map_pages(page, 1, 0);
  718. pcp = &zone_pcp(zone, get_cpu())->pcp[cold];
  719. local_irq_save(flags);
  720. __count_vm_event(PGFREE);
  721. list_add(&page->lru, &pcp->list);
  722. pcp->count++;
  723. if (pcp->count >= pcp->high) {
  724. free_pages_bulk(zone, pcp->batch, &pcp->list, 0);
  725. pcp->count -= pcp->batch;
  726. }
  727. local_irq_restore(flags);
  728. put_cpu();
  729. }
  730. void fastcall free_hot_page(struct page *page)
  731. {
  732. free_hot_cold_page(page, 0);
  733. }
  734. void fastcall free_cold_page(struct page *page)
  735. {
  736. free_hot_cold_page(page, 1);
  737. }
  738. /*
  739. * split_page takes a non-compound higher-order page, and splits it into
  740. * n (1<<order) sub-pages: page[0..n]
  741. * Each sub-page must be freed individually.
  742. *
  743. * Note: this is probably too low level an operation for use in drivers.
  744. * Please consult with lkml before using this in your driver.
  745. */
  746. void split_page(struct page *page, unsigned int order)
  747. {
  748. int i;
  749. VM_BUG_ON(PageCompound(page));
  750. VM_BUG_ON(!page_count(page));
  751. for (i = 1; i < (1 << order); i++)
  752. set_page_refcounted(page + i);
  753. }
  754. /*
  755. * Really, prep_compound_page() should be called from __rmqueue_bulk(). But
  756. * we cheat by calling it from here, in the order > 0 path. Saves a branch
  757. * or two.
  758. */
  759. static struct page *buffered_rmqueue(struct zonelist *zonelist,
  760. struct zone *zone, int order, gfp_t gfp_flags)
  761. {
  762. unsigned long flags;
  763. struct page *page;
  764. int cold = !!(gfp_flags & __GFP_COLD);
  765. int cpu;
  766. again:
  767. cpu = get_cpu();
  768. if (likely(order == 0)) {
  769. struct per_cpu_pages *pcp;
  770. pcp = &zone_pcp(zone, cpu)->pcp[cold];
  771. local_irq_save(flags);
  772. if (!pcp->count) {
  773. pcp->count = rmqueue_bulk(zone, 0,
  774. pcp->batch, &pcp->list);
  775. if (unlikely(!pcp->count))
  776. goto failed;
  777. }
  778. page = list_entry(pcp->list.next, struct page, lru);
  779. list_del(&page->lru);
  780. pcp->count--;
  781. } else {
  782. spin_lock_irqsave(&zone->lock, flags);
  783. page = __rmqueue(zone, order);
  784. spin_unlock(&zone->lock);
  785. if (!page)
  786. goto failed;
  787. }
  788. __count_zone_vm_events(PGALLOC, zone, 1 << order);
  789. zone_statistics(zonelist, zone);
  790. local_irq_restore(flags);
  791. put_cpu();
  792. VM_BUG_ON(bad_range(zone, page));
  793. if (prep_new_page(page, order, gfp_flags))
  794. goto again;
  795. return page;
  796. failed:
  797. local_irq_restore(flags);
  798. put_cpu();
  799. return NULL;
  800. }
  801. #define ALLOC_NO_WATERMARKS 0x01 /* don't check watermarks at all */
  802. #define ALLOC_WMARK_MIN 0x02 /* use pages_min watermark */
  803. #define ALLOC_WMARK_LOW 0x04 /* use pages_low watermark */
  804. #define ALLOC_WMARK_HIGH 0x08 /* use pages_high watermark */
  805. #define ALLOC_HARDER 0x10 /* try to alloc harder */
  806. #define ALLOC_HIGH 0x20 /* __GFP_HIGH set */
  807. #define ALLOC_CPUSET 0x40 /* check for correct cpuset */
  808. #ifdef CONFIG_FAIL_PAGE_ALLOC
  809. static struct fail_page_alloc_attr {
  810. struct fault_attr attr;
  811. u32 ignore_gfp_highmem;
  812. u32 ignore_gfp_wait;
  813. #ifdef CONFIG_FAULT_INJECTION_DEBUG_FS
  814. struct dentry *ignore_gfp_highmem_file;
  815. struct dentry *ignore_gfp_wait_file;
  816. #endif /* CONFIG_FAULT_INJECTION_DEBUG_FS */
  817. } fail_page_alloc = {
  818. .attr = FAULT_ATTR_INITIALIZER,
  819. .ignore_gfp_wait = 1,
  820. .ignore_gfp_highmem = 1,
  821. };
  822. static int __init setup_fail_page_alloc(char *str)
  823. {
  824. return setup_fault_attr(&fail_page_alloc.attr, str);
  825. }
  826. __setup("fail_page_alloc=", setup_fail_page_alloc);
  827. static int should_fail_alloc_page(gfp_t gfp_mask, unsigned int order)
  828. {
  829. if (gfp_mask & __GFP_NOFAIL)
  830. return 0;
  831. if (fail_page_alloc.ignore_gfp_highmem && (gfp_mask & __GFP_HIGHMEM))
  832. return 0;
  833. if (fail_page_alloc.ignore_gfp_wait && (gfp_mask & __GFP_WAIT))
  834. return 0;
  835. return should_fail(&fail_page_alloc.attr, 1 << order);
  836. }
  837. #ifdef CONFIG_FAULT_INJECTION_DEBUG_FS
  838. static int __init fail_page_alloc_debugfs(void)
  839. {
  840. mode_t mode = S_IFREG | S_IRUSR | S_IWUSR;
  841. struct dentry *dir;
  842. int err;
  843. err = init_fault_attr_dentries(&fail_page_alloc.attr,
  844. "fail_page_alloc");
  845. if (err)
  846. return err;
  847. dir = fail_page_alloc.attr.dentries.dir;
  848. fail_page_alloc.ignore_gfp_wait_file =
  849. debugfs_create_bool("ignore-gfp-wait", mode, dir,
  850. &fail_page_alloc.ignore_gfp_wait);
  851. fail_page_alloc.ignore_gfp_highmem_file =
  852. debugfs_create_bool("ignore-gfp-highmem", mode, dir,
  853. &fail_page_alloc.ignore_gfp_highmem);
  854. if (!fail_page_alloc.ignore_gfp_wait_file ||
  855. !fail_page_alloc.ignore_gfp_highmem_file) {
  856. err = -ENOMEM;
  857. debugfs_remove(fail_page_alloc.ignore_gfp_wait_file);
  858. debugfs_remove(fail_page_alloc.ignore_gfp_highmem_file);
  859. cleanup_fault_attr_dentries(&fail_page_alloc.attr);
  860. }
  861. return err;
  862. }
  863. late_initcall(fail_page_alloc_debugfs);
  864. #endif /* CONFIG_FAULT_INJECTION_DEBUG_FS */
  865. #else /* CONFIG_FAIL_PAGE_ALLOC */
  866. static inline int should_fail_alloc_page(gfp_t gfp_mask, unsigned int order)
  867. {
  868. return 0;
  869. }
  870. #endif /* CONFIG_FAIL_PAGE_ALLOC */
  871. /*
  872. * Return 1 if free pages are above 'mark'. This takes into account the order
  873. * of the allocation.
  874. */
  875. int zone_watermark_ok(struct zone *z, int order, unsigned long mark,
  876. int classzone_idx, int alloc_flags)
  877. {
  878. /* free_pages my go negative - that's OK */
  879. long min = mark;
  880. long free_pages = zone_page_state(z, NR_FREE_PAGES) - (1 << order) + 1;
  881. int o;
  882. if (alloc_flags & ALLOC_HIGH)
  883. min -= min / 2;
  884. if (alloc_flags & ALLOC_HARDER)
  885. min -= min / 4;
  886. if (free_pages <= min + z->lowmem_reserve[classzone_idx])
  887. return 0;
  888. for (o = 0; o < order; o++) {
  889. /* At the next order, this order's pages become unavailable */
  890. free_pages -= z->free_area[o].nr_free << o;
  891. /* Require fewer higher order pages to be free */
  892. min >>= 1;
  893. if (free_pages <= min)
  894. return 0;
  895. }
  896. return 1;
  897. }
  898. #ifdef CONFIG_NUMA
  899. /*
  900. * zlc_setup - Setup for "zonelist cache". Uses cached zone data to
  901. * skip over zones that are not allowed by the cpuset, or that have
  902. * been recently (in last second) found to be nearly full. See further
  903. * comments in mmzone.h. Reduces cache footprint of zonelist scans
  904. * that have to skip over alot of full or unallowed zones.
  905. *
  906. * If the zonelist cache is present in the passed in zonelist, then
  907. * returns a pointer to the allowed node mask (either the current
  908. * tasks mems_allowed, or node_online_map.)
  909. *
  910. * If the zonelist cache is not available for this zonelist, does
  911. * nothing and returns NULL.
  912. *
  913. * If the fullzones BITMAP in the zonelist cache is stale (more than
  914. * a second since last zap'd) then we zap it out (clear its bits.)
  915. *
  916. * We hold off even calling zlc_setup, until after we've checked the
  917. * first zone in the zonelist, on the theory that most allocations will
  918. * be satisfied from that first zone, so best to examine that zone as
  919. * quickly as we can.
  920. */
  921. static nodemask_t *zlc_setup(struct zonelist *zonelist, int alloc_flags)
  922. {
  923. struct zonelist_cache *zlc; /* cached zonelist speedup info */
  924. nodemask_t *allowednodes; /* zonelist_cache approximation */
  925. zlc = zonelist->zlcache_ptr;
  926. if (!zlc)
  927. return NULL;
  928. if (jiffies - zlc->last_full_zap > 1 * HZ) {
  929. bitmap_zero(zlc->fullzones, MAX_ZONES_PER_ZONELIST);
  930. zlc->last_full_zap = jiffies;
  931. }
  932. allowednodes = !in_interrupt() && (alloc_flags & ALLOC_CPUSET) ?
  933. &cpuset_current_mems_allowed :
  934. &node_online_map;
  935. return allowednodes;
  936. }
  937. /*
  938. * Given 'z' scanning a zonelist, run a couple of quick checks to see
  939. * if it is worth looking at further for free memory:
  940. * 1) Check that the zone isn't thought to be full (doesn't have its
  941. * bit set in the zonelist_cache fullzones BITMAP).
  942. * 2) Check that the zones node (obtained from the zonelist_cache
  943. * z_to_n[] mapping) is allowed in the passed in allowednodes mask.
  944. * Return true (non-zero) if zone is worth looking at further, or
  945. * else return false (zero) if it is not.
  946. *
  947. * This check -ignores- the distinction between various watermarks,
  948. * such as GFP_HIGH, GFP_ATOMIC, PF_MEMALLOC, ... If a zone is
  949. * found to be full for any variation of these watermarks, it will
  950. * be considered full for up to one second by all requests, unless
  951. * we are so low on memory on all allowed nodes that we are forced
  952. * into the second scan of the zonelist.
  953. *
  954. * In the second scan we ignore this zonelist cache and exactly
  955. * apply the watermarks to all zones, even it is slower to do so.
  956. * We are low on memory in the second scan, and should leave no stone
  957. * unturned looking for a free page.
  958. */
  959. static int zlc_zone_worth_trying(struct zonelist *zonelist, struct zone **z,
  960. nodemask_t *allowednodes)
  961. {
  962. struct zonelist_cache *zlc; /* cached zonelist speedup info */
  963. int i; /* index of *z in zonelist zones */
  964. int n; /* node that zone *z is on */
  965. zlc = zonelist->zlcache_ptr;
  966. if (!zlc)
  967. return 1;
  968. i = z - zonelist->zones;
  969. n = zlc->z_to_n[i];
  970. /* This zone is worth trying if it is allowed but not full */
  971. return node_isset(n, *allowednodes) && !test_bit(i, zlc->fullzones);
  972. }
  973. /*
  974. * Given 'z' scanning a zonelist, set the corresponding bit in
  975. * zlc->fullzones, so that subsequent attempts to allocate a page
  976. * from that zone don't waste time re-examining it.
  977. */
  978. static void zlc_mark_zone_full(struct zonelist *zonelist, struct zone **z)
  979. {
  980. struct zonelist_cache *zlc; /* cached zonelist speedup info */
  981. int i; /* index of *z in zonelist zones */
  982. zlc = zonelist->zlcache_ptr;
  983. if (!zlc)
  984. return;
  985. i = z - zonelist->zones;
  986. set_bit(i, zlc->fullzones);
  987. }
  988. #else /* CONFIG_NUMA */
  989. static nodemask_t *zlc_setup(struct zonelist *zonelist, int alloc_flags)
  990. {
  991. return NULL;
  992. }
  993. static int zlc_zone_worth_trying(struct zonelist *zonelist, struct zone **z,
  994. nodemask_t *allowednodes)
  995. {
  996. return 1;
  997. }
  998. static void zlc_mark_zone_full(struct zonelist *zonelist, struct zone **z)
  999. {
  1000. }
  1001. #endif /* CONFIG_NUMA */
  1002. /*
  1003. * get_page_from_freelist goes through the zonelist trying to allocate
  1004. * a page.
  1005. */
  1006. static struct page *
  1007. get_page_from_freelist(gfp_t gfp_mask, unsigned int order,
  1008. struct zonelist *zonelist, int alloc_flags)
  1009. {
  1010. struct zone **z;
  1011. struct page *page = NULL;
  1012. int classzone_idx = zone_idx(zonelist->zones[0]);
  1013. struct zone *zone;
  1014. nodemask_t *allowednodes = NULL;/* zonelist_cache approximation */
  1015. int zlc_active = 0; /* set if using zonelist_cache */
  1016. int did_zlc_setup = 0; /* just call zlc_setup() one time */
  1017. zonelist_scan:
  1018. /*
  1019. * Scan zonelist, looking for a zone with enough free.
  1020. * See also cpuset_zone_allowed() comment in kernel/cpuset.c.
  1021. */
  1022. z = zonelist->zones;
  1023. do {
  1024. if (NUMA_BUILD && zlc_active &&
  1025. !zlc_zone_worth_trying(zonelist, z, allowednodes))
  1026. continue;
  1027. zone = *z;
  1028. if (unlikely(NUMA_BUILD && (gfp_mask & __GFP_THISNODE) &&
  1029. zone->zone_pgdat != zonelist->zones[0]->zone_pgdat))
  1030. break;
  1031. if ((alloc_flags & ALLOC_CPUSET) &&
  1032. !cpuset_zone_allowed_softwall(zone, gfp_mask))
  1033. goto try_next_zone;
  1034. if (!(alloc_flags & ALLOC_NO_WATERMARKS)) {
  1035. unsigned long mark;
  1036. if (alloc_flags & ALLOC_WMARK_MIN)
  1037. mark = zone->pages_min;
  1038. else if (alloc_flags & ALLOC_WMARK_LOW)
  1039. mark = zone->pages_low;
  1040. else
  1041. mark = zone->pages_high;
  1042. if (!zone_watermark_ok(zone, order, mark,
  1043. classzone_idx, alloc_flags)) {
  1044. if (!zone_reclaim_mode ||
  1045. !zone_reclaim(zone, gfp_mask, order))
  1046. goto this_zone_full;
  1047. }
  1048. }
  1049. page = buffered_rmqueue(zonelist, zone, order, gfp_mask);
  1050. if (page)
  1051. break;
  1052. this_zone_full:
  1053. if (NUMA_BUILD)
  1054. zlc_mark_zone_full(zonelist, z);
  1055. try_next_zone:
  1056. if (NUMA_BUILD && !did_zlc_setup) {
  1057. /* we do zlc_setup after the first zone is tried */
  1058. allowednodes = zlc_setup(zonelist, alloc_flags);
  1059. zlc_active = 1;
  1060. did_zlc_setup = 1;
  1061. }
  1062. } while (*(++z) != NULL);
  1063. if (unlikely(NUMA_BUILD && page == NULL && zlc_active)) {
  1064. /* Disable zlc cache for second zonelist scan */
  1065. zlc_active = 0;
  1066. goto zonelist_scan;
  1067. }
  1068. return page;
  1069. }
  1070. /*
  1071. * This is the 'heart' of the zoned buddy allocator.
  1072. */
  1073. struct page * fastcall
  1074. __alloc_pages(gfp_t gfp_mask, unsigned int order,
  1075. struct zonelist *zonelist)
  1076. {
  1077. const gfp_t wait = gfp_mask & __GFP_WAIT;
  1078. struct zone **z;
  1079. struct page *page;
  1080. struct reclaim_state reclaim_state;
  1081. struct task_struct *p = current;
  1082. int do_retry;
  1083. int alloc_flags;
  1084. int did_some_progress;
  1085. might_sleep_if(wait);
  1086. if (should_fail_alloc_page(gfp_mask, order))
  1087. return NULL;
  1088. restart:
  1089. z = zonelist->zones; /* the list of zones suitable for gfp_mask */
  1090. if (unlikely(*z == NULL)) {
  1091. /* Should this ever happen?? */
  1092. return NULL;
  1093. }
  1094. page = get_page_from_freelist(gfp_mask|__GFP_HARDWALL, order,
  1095. zonelist, ALLOC_WMARK_LOW|ALLOC_CPUSET);
  1096. if (page)
  1097. goto got_pg;
  1098. /*
  1099. * GFP_THISNODE (meaning __GFP_THISNODE, __GFP_NORETRY and
  1100. * __GFP_NOWARN set) should not cause reclaim since the subsystem
  1101. * (f.e. slab) using GFP_THISNODE may choose to trigger reclaim
  1102. * using a larger set of nodes after it has established that the
  1103. * allowed per node queues are empty and that nodes are
  1104. * over allocated.
  1105. */
  1106. if (NUMA_BUILD && (gfp_mask & GFP_THISNODE) == GFP_THISNODE)
  1107. goto nopage;
  1108. for (z = zonelist->zones; *z; z++)
  1109. wakeup_kswapd(*z, order);
  1110. /*
  1111. * OK, we're below the kswapd watermark and have kicked background
  1112. * reclaim. Now things get more complex, so set up alloc_flags according
  1113. * to how we want to proceed.
  1114. *
  1115. * The caller may dip into page reserves a bit more if the caller
  1116. * cannot run direct reclaim, or if the caller has realtime scheduling
  1117. * policy or is asking for __GFP_HIGH memory. GFP_ATOMIC requests will
  1118. * set both ALLOC_HARDER (!wait) and ALLOC_HIGH (__GFP_HIGH).
  1119. */
  1120. alloc_flags = ALLOC_WMARK_MIN;
  1121. if ((unlikely(rt_task(p)) && !in_interrupt()) || !wait)
  1122. alloc_flags |= ALLOC_HARDER;
  1123. if (gfp_mask & __GFP_HIGH)
  1124. alloc_flags |= ALLOC_HIGH;
  1125. if (wait)
  1126. alloc_flags |= ALLOC_CPUSET;
  1127. /*
  1128. * Go through the zonelist again. Let __GFP_HIGH and allocations
  1129. * coming from realtime tasks go deeper into reserves.
  1130. *
  1131. * This is the last chance, in general, before the goto nopage.
  1132. * Ignore cpuset if GFP_ATOMIC (!wait) rather than fail alloc.
  1133. * See also cpuset_zone_allowed() comment in kernel/cpuset.c.
  1134. */
  1135. page = get_page_from_freelist(gfp_mask, order, zonelist, alloc_flags);
  1136. if (page)
  1137. goto got_pg;
  1138. /* This allocation should allow future memory freeing. */
  1139. rebalance:
  1140. if (((p->flags & PF_MEMALLOC) || unlikely(test_thread_flag(TIF_MEMDIE)))
  1141. && !in_interrupt()) {
  1142. if (!(gfp_mask & __GFP_NOMEMALLOC)) {
  1143. nofail_alloc:
  1144. /* go through the zonelist yet again, ignoring mins */
  1145. page = get_page_from_freelist(gfp_mask, order,
  1146. zonelist, ALLOC_NO_WATERMARKS);
  1147. if (page)
  1148. goto got_pg;
  1149. if (gfp_mask & __GFP_NOFAIL) {
  1150. congestion_wait(WRITE, HZ/50);
  1151. goto nofail_alloc;
  1152. }
  1153. }
  1154. goto nopage;
  1155. }
  1156. /* Atomic allocations - we can't balance anything */
  1157. if (!wait)
  1158. goto nopage;
  1159. cond_resched();
  1160. /* We now go into synchronous reclaim */
  1161. cpuset_memory_pressure_bump();
  1162. p->flags |= PF_MEMALLOC;
  1163. reclaim_state.reclaimed_slab = 0;
  1164. p->reclaim_state = &reclaim_state;
  1165. did_some_progress = try_to_free_pages(zonelist->zones, gfp_mask);
  1166. p->reclaim_state = NULL;
  1167. p->flags &= ~PF_MEMALLOC;
  1168. cond_resched();
  1169. if (likely(did_some_progress)) {
  1170. page = get_page_from_freelist(gfp_mask, order,
  1171. zonelist, alloc_flags);
  1172. if (page)
  1173. goto got_pg;
  1174. } else if ((gfp_mask & __GFP_FS) && !(gfp_mask & __GFP_NORETRY)) {
  1175. /*
  1176. * Go through the zonelist yet one more time, keep
  1177. * very high watermark here, this is only to catch
  1178. * a parallel oom killing, we must fail if we're still
  1179. * under heavy pressure.
  1180. */
  1181. page = get_page_from_freelist(gfp_mask|__GFP_HARDWALL, order,
  1182. zonelist, ALLOC_WMARK_HIGH|ALLOC_CPUSET);
  1183. if (page)
  1184. goto got_pg;
  1185. out_of_memory(zonelist, gfp_mask, order);
  1186. goto restart;
  1187. }
  1188. /*
  1189. * Don't let big-order allocations loop unless the caller explicitly
  1190. * requests that. Wait for some write requests to complete then retry.
  1191. *
  1192. * In this implementation, __GFP_REPEAT means __GFP_NOFAIL for order
  1193. * <= 3, but that may not be true in other implementations.
  1194. */
  1195. do_retry = 0;
  1196. if (!(gfp_mask & __GFP_NORETRY)) {
  1197. if ((order <= 3) || (gfp_mask & __GFP_REPEAT))
  1198. do_retry = 1;
  1199. if (gfp_mask & __GFP_NOFAIL)
  1200. do_retry = 1;
  1201. }
  1202. if (do_retry) {
  1203. congestion_wait(WRITE, HZ/50);
  1204. goto rebalance;
  1205. }
  1206. nopage:
  1207. if (!(gfp_mask & __GFP_NOWARN) && printk_ratelimit()) {
  1208. printk(KERN_WARNING "%s: page allocation failure."
  1209. " order:%d, mode:0x%x\n",
  1210. p->comm, order, gfp_mask);
  1211. dump_stack();
  1212. show_mem();
  1213. }
  1214. got_pg:
  1215. return page;
  1216. }
  1217. EXPORT_SYMBOL(__alloc_pages);
  1218. /*
  1219. * Common helper functions.
  1220. */
  1221. fastcall unsigned long __get_free_pages(gfp_t gfp_mask, unsigned int order)
  1222. {
  1223. struct page * page;
  1224. page = alloc_pages(gfp_mask, order);
  1225. if (!page)
  1226. return 0;
  1227. return (unsigned long) page_address(page);
  1228. }
  1229. EXPORT_SYMBOL(__get_free_pages);
  1230. fastcall unsigned long get_zeroed_page(gfp_t gfp_mask)
  1231. {
  1232. struct page * page;
  1233. /*
  1234. * get_zeroed_page() returns a 32-bit address, which cannot represent
  1235. * a highmem page
  1236. */
  1237. VM_BUG_ON((gfp_mask & __GFP_HIGHMEM) != 0);
  1238. page = alloc_pages(gfp_mask | __GFP_ZERO, 0);
  1239. if (page)
  1240. return (unsigned long) page_address(page);
  1241. return 0;
  1242. }
  1243. EXPORT_SYMBOL(get_zeroed_page);
  1244. void __pagevec_free(struct pagevec *pvec)
  1245. {
  1246. int i = pagevec_count(pvec);
  1247. while (--i >= 0)
  1248. free_hot_cold_page(pvec->pages[i], pvec->cold);
  1249. }
  1250. fastcall void __free_pages(struct page *page, unsigned int order)
  1251. {
  1252. if (put_page_testzero(page)) {
  1253. if (order == 0)
  1254. free_hot_page(page);
  1255. else
  1256. __free_pages_ok(page, order);
  1257. }
  1258. }
  1259. EXPORT_SYMBOL(__free_pages);
  1260. fastcall void free_pages(unsigned long addr, unsigned int order)
  1261. {
  1262. if (addr != 0) {
  1263. VM_BUG_ON(!virt_addr_valid((void *)addr));
  1264. __free_pages(virt_to_page((void *)addr), order);
  1265. }
  1266. }
  1267. EXPORT_SYMBOL(free_pages);
  1268. static unsigned int nr_free_zone_pages(int offset)
  1269. {
  1270. /* Just pick one node, since fallback list is circular */
  1271. pg_data_t *pgdat = NODE_DATA(numa_node_id());
  1272. unsigned int sum = 0;
  1273. struct zonelist *zonelist = pgdat->node_zonelists + offset;
  1274. struct zone **zonep = zonelist->zones;
  1275. struct zone *zone;
  1276. for (zone = *zonep++; zone; zone = *zonep++) {
  1277. unsigned long size = zone->present_pages;
  1278. unsigned long high = zone->pages_high;
  1279. if (size > high)
  1280. sum += size - high;
  1281. }
  1282. return sum;
  1283. }
  1284. /*
  1285. * Amount of free RAM allocatable within ZONE_DMA and ZONE_NORMAL
  1286. */
  1287. unsigned int nr_free_buffer_pages(void)
  1288. {
  1289. return nr_free_zone_pages(gfp_zone(GFP_USER));
  1290. }
  1291. /*
  1292. * Amount of free RAM allocatable within all zones
  1293. */
  1294. unsigned int nr_free_pagecache_pages(void)
  1295. {
  1296. return nr_free_zone_pages(gfp_zone(GFP_HIGHUSER));
  1297. }
  1298. static inline void show_node(struct zone *zone)
  1299. {
  1300. if (NUMA_BUILD)
  1301. printk("Node %d ", zone_to_nid(zone));
  1302. }
  1303. void si_meminfo(struct sysinfo *val)
  1304. {
  1305. val->totalram = totalram_pages;
  1306. val->sharedram = 0;
  1307. val->freeram = global_page_state(NR_FREE_PAGES);
  1308. val->bufferram = nr_blockdev_pages();
  1309. val->totalhigh = totalhigh_pages;
  1310. val->freehigh = nr_free_highpages();
  1311. val->mem_unit = PAGE_SIZE;
  1312. }
  1313. EXPORT_SYMBOL(si_meminfo);
  1314. #ifdef CONFIG_NUMA
  1315. void si_meminfo_node(struct sysinfo *val, int nid)
  1316. {
  1317. pg_data_t *pgdat = NODE_DATA(nid);
  1318. val->totalram = pgdat->node_present_pages;
  1319. val->freeram = node_page_state(nid, NR_FREE_PAGES);
  1320. #ifdef CONFIG_HIGHMEM
  1321. val->totalhigh = pgdat->node_zones[ZONE_HIGHMEM].present_pages;
  1322. val->freehigh = zone_page_state(&pgdat->node_zones[ZONE_HIGHMEM],
  1323. NR_FREE_PAGES);
  1324. #else
  1325. val->totalhigh = 0;
  1326. val->freehigh = 0;
  1327. #endif
  1328. val->mem_unit = PAGE_SIZE;
  1329. }
  1330. #endif
  1331. #define K(x) ((x) << (PAGE_SHIFT-10))
  1332. /*
  1333. * Show free area list (used inside shift_scroll-lock stuff)
  1334. * We also calculate the percentage fragmentation. We do this by counting the
  1335. * memory on each free list with the exception of the first item on the list.
  1336. */
  1337. void show_free_areas(void)
  1338. {
  1339. int cpu;
  1340. struct zone *zone;
  1341. for_each_zone(zone) {
  1342. if (!populated_zone(zone))
  1343. continue;
  1344. show_node(zone);
  1345. printk("%s per-cpu:\n", zone->name);
  1346. for_each_online_cpu(cpu) {
  1347. struct per_cpu_pageset *pageset;
  1348. pageset = zone_pcp(zone, cpu);
  1349. printk("CPU %4d: Hot: hi:%5d, btch:%4d usd:%4d "
  1350. "Cold: hi:%5d, btch:%4d usd:%4d\n",
  1351. cpu, pageset->pcp[0].high,
  1352. pageset->pcp[0].batch, pageset->pcp[0].count,
  1353. pageset->pcp[1].high, pageset->pcp[1].batch,
  1354. pageset->pcp[1].count);
  1355. }
  1356. }
  1357. printk("Active:%lu inactive:%lu dirty:%lu writeback:%lu unstable:%lu\n"
  1358. " free:%lu slab:%lu mapped:%lu pagetables:%lu bounce:%lu\n",
  1359. global_page_state(NR_ACTIVE),
  1360. global_page_state(NR_INACTIVE),
  1361. global_page_state(NR_FILE_DIRTY),
  1362. global_page_state(NR_WRITEBACK),
  1363. global_page_state(NR_UNSTABLE_NFS),
  1364. global_page_state(NR_FREE_PAGES),
  1365. global_page_state(NR_SLAB_RECLAIMABLE) +
  1366. global_page_state(NR_SLAB_UNRECLAIMABLE),
  1367. global_page_state(NR_FILE_MAPPED),
  1368. global_page_state(NR_PAGETABLE),
  1369. global_page_state(NR_BOUNCE));
  1370. for_each_zone(zone) {
  1371. int i;
  1372. if (!populated_zone(zone))
  1373. continue;
  1374. show_node(zone);
  1375. printk("%s"
  1376. " free:%lukB"
  1377. " min:%lukB"
  1378. " low:%lukB"
  1379. " high:%lukB"
  1380. " active:%lukB"
  1381. " inactive:%lukB"
  1382. " present:%lukB"
  1383. " pages_scanned:%lu"
  1384. " all_unreclaimable? %s"
  1385. "\n",
  1386. zone->name,
  1387. K(zone_page_state(zone, NR_FREE_PAGES)),
  1388. K(zone->pages_min),
  1389. K(zone->pages_low),
  1390. K(zone->pages_high),
  1391. K(zone_page_state(zone, NR_ACTIVE)),
  1392. K(zone_page_state(zone, NR_INACTIVE)),
  1393. K(zone->present_pages),
  1394. zone->pages_scanned,
  1395. (zone->all_unreclaimable ? "yes" : "no")
  1396. );
  1397. printk("lowmem_reserve[]:");
  1398. for (i = 0; i < MAX_NR_ZONES; i++)
  1399. printk(" %lu", zone->lowmem_reserve[i]);
  1400. printk("\n");
  1401. }
  1402. for_each_zone(zone) {
  1403. unsigned long nr[MAX_ORDER], flags, order, total = 0;
  1404. if (!populated_zone(zone))
  1405. continue;
  1406. show_node(zone);
  1407. printk("%s: ", zone->name);
  1408. spin_lock_irqsave(&zone->lock, flags);
  1409. for (order = 0; order < MAX_ORDER; order++) {
  1410. nr[order] = zone->free_area[order].nr_free;
  1411. total += nr[order] << order;
  1412. }
  1413. spin_unlock_irqrestore(&zone->lock, flags);
  1414. for (order = 0; order < MAX_ORDER; order++)
  1415. printk("%lu*%lukB ", nr[order], K(1UL) << order);
  1416. printk("= %lukB\n", K(total));
  1417. }
  1418. show_swap_cache_info();
  1419. }
  1420. /*
  1421. * Builds allocation fallback zone lists.
  1422. *
  1423. * Add all populated zones of a node to the zonelist.
  1424. */
  1425. static int __meminit build_zonelists_node(pg_data_t *pgdat,
  1426. struct zonelist *zonelist, int nr_zones, enum zone_type zone_type)
  1427. {
  1428. struct zone *zone;
  1429. BUG_ON(zone_type >= MAX_NR_ZONES);
  1430. zone_type++;
  1431. do {
  1432. zone_type--;
  1433. zone = pgdat->node_zones + zone_type;
  1434. if (populated_zone(zone)) {
  1435. zonelist->zones[nr_zones++] = zone;
  1436. check_highest_zone(zone_type);
  1437. }
  1438. } while (zone_type);
  1439. return nr_zones;
  1440. }
  1441. #ifdef CONFIG_NUMA
  1442. #define MAX_NODE_LOAD (num_online_nodes())
  1443. static int __meminitdata node_load[MAX_NUMNODES];
  1444. /**
  1445. * find_next_best_node - find the next node that should appear in a given node's fallback list
  1446. * @node: node whose fallback list we're appending
  1447. * @used_node_mask: nodemask_t of already used nodes
  1448. *
  1449. * We use a number of factors to determine which is the next node that should
  1450. * appear on a given node's fallback list. The node should not have appeared
  1451. * already in @node's fallback list, and it should be the next closest node
  1452. * according to the distance array (which contains arbitrary distance values
  1453. * from each node to each node in the system), and should also prefer nodes
  1454. * with no CPUs, since presumably they'll have very little allocation pressure
  1455. * on them otherwise.
  1456. * It returns -1 if no node is found.
  1457. */
  1458. static int __meminit find_next_best_node(int node, nodemask_t *used_node_mask)
  1459. {
  1460. int n, val;
  1461. int min_val = INT_MAX;
  1462. int best_node = -1;
  1463. /* Use the local node if we haven't already */
  1464. if (!node_isset(node, *used_node_mask)) {
  1465. node_set(node, *used_node_mask);
  1466. return node;
  1467. }
  1468. for_each_online_node(n) {
  1469. cpumask_t tmp;
  1470. /* Don't want a node to appear more than once */
  1471. if (node_isset(n, *used_node_mask))
  1472. continue;
  1473. /* Use the distance array to find the distance */
  1474. val = node_distance(node, n);
  1475. /* Penalize nodes under us ("prefer the next node") */
  1476. val += (n < node);
  1477. /* Give preference to headless and unused nodes */
  1478. tmp = node_to_cpumask(n);
  1479. if (!cpus_empty(tmp))
  1480. val += PENALTY_FOR_NODE_WITH_CPUS;
  1481. /* Slight preference for less loaded node */
  1482. val *= (MAX_NODE_LOAD*MAX_NUMNODES);
  1483. val += node_load[n];
  1484. if (val < min_val) {
  1485. min_val = val;
  1486. best_node = n;
  1487. }
  1488. }
  1489. if (best_node >= 0)
  1490. node_set(best_node, *used_node_mask);
  1491. return best_node;
  1492. }
  1493. static void __meminit build_zonelists(pg_data_t *pgdat)
  1494. {
  1495. int j, node, local_node;
  1496. enum zone_type i;
  1497. int prev_node, load;
  1498. struct zonelist *zonelist;
  1499. nodemask_t used_mask;
  1500. /* initialize zonelists */
  1501. for (i = 0; i < MAX_NR_ZONES; i++) {
  1502. zonelist = pgdat->node_zonelists + i;
  1503. zonelist->zones[0] = NULL;
  1504. }
  1505. /* NUMA-aware ordering of nodes */
  1506. local_node = pgdat->node_id;
  1507. load = num_online_nodes();
  1508. prev_node = local_node;
  1509. nodes_clear(used_mask);
  1510. while ((node = find_next_best_node(local_node, &used_mask)) >= 0) {
  1511. int distance = node_distance(local_node, node);
  1512. /*
  1513. * If another node is sufficiently far away then it is better
  1514. * to reclaim pages in a zone before going off node.
  1515. */
  1516. if (distance > RECLAIM_DISTANCE)
  1517. zone_reclaim_mode = 1;
  1518. /*
  1519. * We don't want to pressure a particular node.
  1520. * So adding penalty to the first node in same
  1521. * distance group to make it round-robin.
  1522. */
  1523. if (distance != node_distance(local_node, prev_node))
  1524. node_load[node] += load;
  1525. prev_node = node;
  1526. load--;
  1527. for (i = 0; i < MAX_NR_ZONES; i++) {
  1528. zonelist = pgdat->node_zonelists + i;
  1529. for (j = 0; zonelist->zones[j] != NULL; j++);
  1530. j = build_zonelists_node(NODE_DATA(node), zonelist, j, i);
  1531. zonelist->zones[j] = NULL;
  1532. }
  1533. }
  1534. }
  1535. /* Construct the zonelist performance cache - see further mmzone.h */
  1536. static void __meminit build_zonelist_cache(pg_data_t *pgdat)
  1537. {
  1538. int i;
  1539. for (i = 0; i < MAX_NR_ZONES; i++) {
  1540. struct zonelist *zonelist;
  1541. struct zonelist_cache *zlc;
  1542. struct zone **z;
  1543. zonelist = pgdat->node_zonelists + i;
  1544. zonelist->zlcache_ptr = zlc = &zonelist->zlcache;
  1545. bitmap_zero(zlc->fullzones, MAX_ZONES_PER_ZONELIST);
  1546. for (z = zonelist->zones; *z; z++)
  1547. zlc->z_to_n[z - zonelist->zones] = zone_to_nid(*z);
  1548. }
  1549. }
  1550. #else /* CONFIG_NUMA */
  1551. static void __meminit build_zonelists(pg_data_t *pgdat)
  1552. {
  1553. int node, local_node;
  1554. enum zone_type i,j;
  1555. local_node = pgdat->node_id;
  1556. for (i = 0; i < MAX_NR_ZONES; i++) {
  1557. struct zonelist *zonelist;
  1558. zonelist = pgdat->node_zonelists + i;
  1559. j = build_zonelists_node(pgdat, zonelist, 0, i);
  1560. /*
  1561. * Now we build the zonelist so that it contains the zones
  1562. * of all the other nodes.
  1563. * We don't want to pressure a particular node, so when
  1564. * building the zones for node N, we make sure that the
  1565. * zones coming right after the local ones are those from
  1566. * node N+1 (modulo N)
  1567. */
  1568. for (node = local_node + 1; node < MAX_NUMNODES; node++) {
  1569. if (!node_online(node))
  1570. continue;
  1571. j = build_zonelists_node(NODE_DATA(node), zonelist, j, i);
  1572. }
  1573. for (node = 0; node < local_node; node++) {
  1574. if (!node_online(node))
  1575. continue;
  1576. j = build_zonelists_node(NODE_DATA(node), zonelist, j, i);
  1577. }
  1578. zonelist->zones[j] = NULL;
  1579. }
  1580. }
  1581. /* non-NUMA variant of zonelist performance cache - just NULL zlcache_ptr */
  1582. static void __meminit build_zonelist_cache(pg_data_t *pgdat)
  1583. {
  1584. int i;
  1585. for (i = 0; i < MAX_NR_ZONES; i++)
  1586. pgdat->node_zonelists[i].zlcache_ptr = NULL;
  1587. }
  1588. #endif /* CONFIG_NUMA */
  1589. /* return values int ....just for stop_machine_run() */
  1590. static int __meminit __build_all_zonelists(void *dummy)
  1591. {
  1592. int nid;
  1593. for_each_online_node(nid) {
  1594. build_zonelists(NODE_DATA(nid));
  1595. build_zonelist_cache(NODE_DATA(nid));
  1596. }
  1597. return 0;
  1598. }
  1599. void __meminit build_all_zonelists(void)
  1600. {
  1601. if (system_state == SYSTEM_BOOTING) {
  1602. __build_all_zonelists(NULL);
  1603. cpuset_init_current_mems_allowed();
  1604. } else {
  1605. /* we have to stop all cpus to guaranntee there is no user
  1606. of zonelist */
  1607. stop_machine_run(__build_all_zonelists, NULL, NR_CPUS);
  1608. /* cpuset refresh routine should be here */
  1609. }
  1610. vm_total_pages = nr_free_pagecache_pages();
  1611. printk("Built %i zonelists. Total pages: %ld\n",
  1612. num_online_nodes(), vm_total_pages);
  1613. }
  1614. /*
  1615. * Helper functions to size the waitqueue hash table.
  1616. * Essentially these want to choose hash table sizes sufficiently
  1617. * large so that collisions trying to wait on pages are rare.
  1618. * But in fact, the number of active page waitqueues on typical
  1619. * systems is ridiculously low, less than 200. So this is even
  1620. * conservative, even though it seems large.
  1621. *
  1622. * The constant PAGES_PER_WAITQUEUE specifies the ratio of pages to
  1623. * waitqueues, i.e. the size of the waitq table given the number of pages.
  1624. */
  1625. #define PAGES_PER_WAITQUEUE 256
  1626. #ifndef CONFIG_MEMORY_HOTPLUG
  1627. static inline unsigned long wait_table_hash_nr_entries(unsigned long pages)
  1628. {
  1629. unsigned long size = 1;
  1630. pages /= PAGES_PER_WAITQUEUE;
  1631. while (size < pages)
  1632. size <<= 1;
  1633. /*
  1634. * Once we have dozens or even hundreds of threads sleeping
  1635. * on IO we've got bigger problems than wait queue collision.
  1636. * Limit the size of the wait table to a reasonable size.
  1637. */
  1638. size = min(size, 4096UL);
  1639. return max(size, 4UL);
  1640. }
  1641. #else
  1642. /*
  1643. * A zone's size might be changed by hot-add, so it is not possible to determine
  1644. * a suitable size for its wait_table. So we use the maximum size now.
  1645. *
  1646. * The max wait table size = 4096 x sizeof(wait_queue_head_t). ie:
  1647. *
  1648. * i386 (preemption config) : 4096 x 16 = 64Kbyte.
  1649. * ia64, x86-64 (no preemption): 4096 x 20 = 80Kbyte.
  1650. * ia64, x86-64 (preemption) : 4096 x 24 = 96Kbyte.
  1651. *
  1652. * The maximum entries are prepared when a zone's memory is (512K + 256) pages
  1653. * or more by the traditional way. (See above). It equals:
  1654. *
  1655. * i386, x86-64, powerpc(4K page size) : = ( 2G + 1M)byte.
  1656. * ia64(16K page size) : = ( 8G + 4M)byte.
  1657. * powerpc (64K page size) : = (32G +16M)byte.
  1658. */
  1659. static inline unsigned long wait_table_hash_nr_entries(unsigned long pages)
  1660. {
  1661. return 4096UL;
  1662. }
  1663. #endif
  1664. /*
  1665. * This is an integer logarithm so that shifts can be used later
  1666. * to extract the more random high bits from the multiplicative
  1667. * hash function before the remainder is taken.
  1668. */
  1669. static inline unsigned long wait_table_bits(unsigned long size)
  1670. {
  1671. return ffz(~size);
  1672. }
  1673. #define LONG_ALIGN(x) (((x)+(sizeof(long))-1)&~((sizeof(long))-1))
  1674. /*
  1675. * Initially all pages are reserved - free ones are freed
  1676. * up by free_all_bootmem() once the early boot process is
  1677. * done. Non-atomic initialization, single-pass.
  1678. */
  1679. void __meminit memmap_init_zone(unsigned long size, int nid, unsigned long zone,
  1680. unsigned long start_pfn, enum memmap_context context)
  1681. {
  1682. struct page *page;
  1683. unsigned long end_pfn = start_pfn + size;
  1684. unsigned long pfn;
  1685. for (pfn = start_pfn; pfn < end_pfn; pfn++) {
  1686. /*
  1687. * There can be holes in boot-time mem_map[]s
  1688. * handed to this function. They do not
  1689. * exist on hotplugged memory.
  1690. */
  1691. if (context == MEMMAP_EARLY) {
  1692. if (!early_pfn_valid(pfn))
  1693. continue;
  1694. if (!early_pfn_in_nid(pfn, nid))
  1695. continue;
  1696. }
  1697. page = pfn_to_page(pfn);
  1698. set_page_links(page, zone, nid, pfn);
  1699. init_page_count(page);
  1700. reset_page_mapcount(page);
  1701. SetPageReserved(page);
  1702. INIT_LIST_HEAD(&page->lru);
  1703. #ifdef WANT_PAGE_VIRTUAL
  1704. /* The shift won't overflow because ZONE_NORMAL is below 4G. */
  1705. if (!is_highmem_idx(zone))
  1706. set_page_address(page, __va(pfn << PAGE_SHIFT));
  1707. #endif
  1708. }
  1709. }
  1710. void zone_init_free_lists(struct pglist_data *pgdat, struct zone *zone,
  1711. unsigned long size)
  1712. {
  1713. int order;
  1714. for (order = 0; order < MAX_ORDER ; order++) {
  1715. INIT_LIST_HEAD(&zone->free_area[order].free_list);
  1716. zone->free_area[order].nr_free = 0;
  1717. }
  1718. }
  1719. #ifndef __HAVE_ARCH_MEMMAP_INIT
  1720. #define memmap_init(size, nid, zone, start_pfn) \
  1721. memmap_init_zone((size), (nid), (zone), (start_pfn), MEMMAP_EARLY)
  1722. #endif
  1723. static int __cpuinit zone_batchsize(struct zone *zone)
  1724. {
  1725. int batch;
  1726. /*
  1727. * The per-cpu-pages pools are set to around 1000th of the
  1728. * size of the zone. But no more than 1/2 of a meg.
  1729. *
  1730. * OK, so we don't know how big the cache is. So guess.
  1731. */
  1732. batch = zone->present_pages / 1024;
  1733. if (batch * PAGE_SIZE > 512 * 1024)
  1734. batch = (512 * 1024) / PAGE_SIZE;
  1735. batch /= 4; /* We effectively *= 4 below */
  1736. if (batch < 1)
  1737. batch = 1;
  1738. /*
  1739. * Clamp the batch to a 2^n - 1 value. Having a power
  1740. * of 2 value was found to be more likely to have
  1741. * suboptimal cache aliasing properties in some cases.
  1742. *
  1743. * For example if 2 tasks are alternately allocating
  1744. * batches of pages, one task can end up with a lot
  1745. * of pages of one half of the possible page colors
  1746. * and the other with pages of the other colors.
  1747. */
  1748. batch = (1 << (fls(batch + batch/2)-1)) - 1;
  1749. return batch;
  1750. }
  1751. inline void setup_pageset(struct per_cpu_pageset *p, unsigned long batch)
  1752. {
  1753. struct per_cpu_pages *pcp;
  1754. memset(p, 0, sizeof(*p));
  1755. pcp = &p->pcp[0]; /* hot */
  1756. pcp->count = 0;
  1757. pcp->high = 6 * batch;
  1758. pcp->batch = max(1UL, 1 * batch);
  1759. INIT_LIST_HEAD(&pcp->list);
  1760. pcp = &p->pcp[1]; /* cold*/
  1761. pcp->count = 0;
  1762. pcp->high = 2 * batch;
  1763. pcp->batch = max(1UL, batch/2);
  1764. INIT_LIST_HEAD(&pcp->list);
  1765. }
  1766. /*
  1767. * setup_pagelist_highmark() sets the high water mark for hot per_cpu_pagelist
  1768. * to the value high for the pageset p.
  1769. */
  1770. static void setup_pagelist_highmark(struct per_cpu_pageset *p,
  1771. unsigned long high)
  1772. {
  1773. struct per_cpu_pages *pcp;
  1774. pcp = &p->pcp[0]; /* hot list */
  1775. pcp->high = high;
  1776. pcp->batch = max(1UL, high/4);
  1777. if ((high/4) > (PAGE_SHIFT * 8))
  1778. pcp->batch = PAGE_SHIFT * 8;
  1779. }
  1780. #ifdef CONFIG_NUMA
  1781. /*
  1782. * Boot pageset table. One per cpu which is going to be used for all
  1783. * zones and all nodes. The parameters will be set in such a way
  1784. * that an item put on a list will immediately be handed over to
  1785. * the buddy list. This is safe since pageset manipulation is done
  1786. * with interrupts disabled.
  1787. *
  1788. * Some NUMA counter updates may also be caught by the boot pagesets.
  1789. *
  1790. * The boot_pagesets must be kept even after bootup is complete for
  1791. * unused processors and/or zones. They do play a role for bootstrapping
  1792. * hotplugged processors.
  1793. *
  1794. * zoneinfo_show() and maybe other functions do
  1795. * not check if the processor is online before following the pageset pointer.
  1796. * Other parts of the kernel may not check if the zone is available.
  1797. */
  1798. static struct per_cpu_pageset boot_pageset[NR_CPUS];
  1799. /*
  1800. * Dynamically allocate memory for the
  1801. * per cpu pageset array in struct zone.
  1802. */
  1803. static int __cpuinit process_zones(int cpu)
  1804. {
  1805. struct zone *zone, *dzone;
  1806. for_each_zone(zone) {
  1807. if (!populated_zone(zone))
  1808. continue;
  1809. zone_pcp(zone, cpu) = kmalloc_node(sizeof(struct per_cpu_pageset),
  1810. GFP_KERNEL, cpu_to_node(cpu));
  1811. if (!zone_pcp(zone, cpu))
  1812. goto bad;
  1813. setup_pageset(zone_pcp(zone, cpu), zone_batchsize(zone));
  1814. if (percpu_pagelist_fraction)
  1815. setup_pagelist_highmark(zone_pcp(zone, cpu),
  1816. (zone->present_pages / percpu_pagelist_fraction));
  1817. }
  1818. return 0;
  1819. bad:
  1820. for_each_zone(dzone) {
  1821. if (dzone == zone)
  1822. break;
  1823. kfree(zone_pcp(dzone, cpu));
  1824. zone_pcp(dzone, cpu) = NULL;
  1825. }
  1826. return -ENOMEM;
  1827. }
  1828. static inline void free_zone_pagesets(int cpu)
  1829. {
  1830. struct zone *zone;
  1831. for_each_zone(zone) {
  1832. struct per_cpu_pageset *pset = zone_pcp(zone, cpu);
  1833. /* Free per_cpu_pageset if it is slab allocated */
  1834. if (pset != &boot_pageset[cpu])
  1835. kfree(pset);
  1836. zone_pcp(zone, cpu) = NULL;
  1837. }
  1838. }
  1839. static int __cpuinit pageset_cpuup_callback(struct notifier_block *nfb,
  1840. unsigned long action,
  1841. void *hcpu)
  1842. {
  1843. int cpu = (long)hcpu;
  1844. int ret = NOTIFY_OK;
  1845. switch (action) {
  1846. case CPU_UP_PREPARE:
  1847. if (process_zones(cpu))
  1848. ret = NOTIFY_BAD;
  1849. break;
  1850. case CPU_UP_CANCELED:
  1851. case CPU_DEAD:
  1852. free_zone_pagesets(cpu);
  1853. break;
  1854. default:
  1855. break;
  1856. }
  1857. return ret;
  1858. }
  1859. static struct notifier_block __cpuinitdata pageset_notifier =
  1860. { &pageset_cpuup_callback, NULL, 0 };
  1861. void __init setup_per_cpu_pageset(void)
  1862. {
  1863. int err;
  1864. /* Initialize per_cpu_pageset for cpu 0.
  1865. * A cpuup callback will do this for every cpu
  1866. * as it comes online
  1867. */
  1868. err = process_zones(smp_processor_id());
  1869. BUG_ON(err);
  1870. register_cpu_notifier(&pageset_notifier);
  1871. }
  1872. #endif
  1873. static __meminit
  1874. int zone_wait_table_init(struct zone *zone, unsigned long zone_size_pages)
  1875. {
  1876. int i;
  1877. struct pglist_data *pgdat = zone->zone_pgdat;
  1878. size_t alloc_size;
  1879. /*
  1880. * The per-page waitqueue mechanism uses hashed waitqueues
  1881. * per zone.
  1882. */
  1883. zone->wait_table_hash_nr_entries =
  1884. wait_table_hash_nr_entries(zone_size_pages);
  1885. zone->wait_table_bits =
  1886. wait_table_bits(zone->wait_table_hash_nr_entries);
  1887. alloc_size = zone->wait_table_hash_nr_entries
  1888. * sizeof(wait_queue_head_t);
  1889. if (system_state == SYSTEM_BOOTING) {
  1890. zone->wait_table = (wait_queue_head_t *)
  1891. alloc_bootmem_node(pgdat, alloc_size);
  1892. } else {
  1893. /*
  1894. * This case means that a zone whose size was 0 gets new memory
  1895. * via memory hot-add.
  1896. * But it may be the case that a new node was hot-added. In
  1897. * this case vmalloc() will not be able to use this new node's
  1898. * memory - this wait_table must be initialized to use this new
  1899. * node itself as well.
  1900. * To use this new node's memory, further consideration will be
  1901. * necessary.
  1902. */
  1903. zone->wait_table = (wait_queue_head_t *)vmalloc(alloc_size);
  1904. }
  1905. if (!zone->wait_table)
  1906. return -ENOMEM;
  1907. for(i = 0; i < zone->wait_table_hash_nr_entries; ++i)
  1908. init_waitqueue_head(zone->wait_table + i);
  1909. return 0;
  1910. }
  1911. static __meminit void zone_pcp_init(struct zone *zone)
  1912. {
  1913. int cpu;
  1914. unsigned long batch = zone_batchsize(zone);
  1915. for (cpu = 0; cpu < NR_CPUS; cpu++) {
  1916. #ifdef CONFIG_NUMA
  1917. /* Early boot. Slab allocator not functional yet */
  1918. zone_pcp(zone, cpu) = &boot_pageset[cpu];
  1919. setup_pageset(&boot_pageset[cpu],0);
  1920. #else
  1921. setup_pageset(zone_pcp(zone,cpu), batch);
  1922. #endif
  1923. }
  1924. if (zone->present_pages)
  1925. printk(KERN_DEBUG " %s zone: %lu pages, LIFO batch:%lu\n",
  1926. zone->name, zone->present_pages, batch);
  1927. }
  1928. __meminit int init_currently_empty_zone(struct zone *zone,
  1929. unsigned long zone_start_pfn,
  1930. unsigned long size,
  1931. enum memmap_context context)
  1932. {
  1933. struct pglist_data *pgdat = zone->zone_pgdat;
  1934. int ret;
  1935. ret = zone_wait_table_init(zone, size);
  1936. if (ret)
  1937. return ret;
  1938. pgdat->nr_zones = zone_idx(zone) + 1;
  1939. zone->zone_start_pfn = zone_start_pfn;
  1940. memmap_init(size, pgdat->node_id, zone_idx(zone), zone_start_pfn);
  1941. zone_init_free_lists(pgdat, zone, zone->spanned_pages);
  1942. return 0;
  1943. }
  1944. #ifdef CONFIG_ARCH_POPULATES_NODE_MAP
  1945. /*
  1946. * Basic iterator support. Return the first range of PFNs for a node
  1947. * Note: nid == MAX_NUMNODES returns first region regardless of node
  1948. */
  1949. static int __init first_active_region_index_in_nid(int nid)
  1950. {
  1951. int i;
  1952. for (i = 0; i < nr_nodemap_entries; i++)
  1953. if (nid == MAX_NUMNODES || early_node_map[i].nid == nid)
  1954. return i;
  1955. return -1;
  1956. }
  1957. /*
  1958. * Basic iterator support. Return the next active range of PFNs for a node
  1959. * Note: nid == MAX_NUMNODES returns next region regardles of node
  1960. */
  1961. static int __init next_active_region_index_in_nid(int index, int nid)
  1962. {
  1963. for (index = index + 1; index < nr_nodemap_entries; index++)
  1964. if (nid == MAX_NUMNODES || early_node_map[index].nid == nid)
  1965. return index;
  1966. return -1;
  1967. }
  1968. #ifndef CONFIG_HAVE_ARCH_EARLY_PFN_TO_NID
  1969. /*
  1970. * Required by SPARSEMEM. Given a PFN, return what node the PFN is on.
  1971. * Architectures may implement their own version but if add_active_range()
  1972. * was used and there are no special requirements, this is a convenient
  1973. * alternative
  1974. */
  1975. int __init early_pfn_to_nid(unsigned long pfn)
  1976. {
  1977. int i;
  1978. for (i = 0; i < nr_nodemap_entries; i++) {
  1979. unsigned long start_pfn = early_node_map[i].start_pfn;
  1980. unsigned long end_pfn = early_node_map[i].end_pfn;
  1981. if (start_pfn <= pfn && pfn < end_pfn)
  1982. return early_node_map[i].nid;
  1983. }
  1984. return 0;
  1985. }
  1986. #endif /* CONFIG_HAVE_ARCH_EARLY_PFN_TO_NID */
  1987. /* Basic iterator support to walk early_node_map[] */
  1988. #define for_each_active_range_index_in_nid(i, nid) \
  1989. for (i = first_active_region_index_in_nid(nid); i != -1; \
  1990. i = next_active_region_index_in_nid(i, nid))
  1991. /**
  1992. * free_bootmem_with_active_regions - Call free_bootmem_node for each active range
  1993. * @nid: The node to free memory on. If MAX_NUMNODES, all nodes are freed.
  1994. * @max_low_pfn: The highest PFN that will be passed to free_bootmem_node
  1995. *
  1996. * If an architecture guarantees that all ranges registered with
  1997. * add_active_ranges() contain no holes and may be freed, this
  1998. * this function may be used instead of calling free_bootmem() manually.
  1999. */
  2000. void __init free_bootmem_with_active_regions(int nid,
  2001. unsigned long max_low_pfn)
  2002. {
  2003. int i;
  2004. for_each_active_range_index_in_nid(i, nid) {
  2005. unsigned long size_pages = 0;
  2006. unsigned long end_pfn = early_node_map[i].end_pfn;
  2007. if (early_node_map[i].start_pfn >= max_low_pfn)
  2008. continue;
  2009. if (end_pfn > max_low_pfn)
  2010. end_pfn = max_low_pfn;
  2011. size_pages = end_pfn - early_node_map[i].start_pfn;
  2012. free_bootmem_node(NODE_DATA(early_node_map[i].nid),
  2013. PFN_PHYS(early_node_map[i].start_pfn),
  2014. size_pages << PAGE_SHIFT);
  2015. }
  2016. }
  2017. /**
  2018. * sparse_memory_present_with_active_regions - Call memory_present for each active range
  2019. * @nid: The node to call memory_present for. If MAX_NUMNODES, all nodes will be used.
  2020. *
  2021. * If an architecture guarantees that all ranges registered with
  2022. * add_active_ranges() contain no holes and may be freed, this
  2023. * function may be used instead of calling memory_present() manually.
  2024. */
  2025. void __init sparse_memory_present_with_active_regions(int nid)
  2026. {
  2027. int i;
  2028. for_each_active_range_index_in_nid(i, nid)
  2029. memory_present(early_node_map[i].nid,
  2030. early_node_map[i].start_pfn,
  2031. early_node_map[i].end_pfn);
  2032. }
  2033. /**
  2034. * push_node_boundaries - Push node boundaries to at least the requested boundary
  2035. * @nid: The nid of the node to push the boundary for
  2036. * @start_pfn: The start pfn of the node
  2037. * @end_pfn: The end pfn of the node
  2038. *
  2039. * In reserve-based hot-add, mem_map is allocated that is unused until hotadd
  2040. * time. Specifically, on x86_64, SRAT will report ranges that can potentially
  2041. * be hotplugged even though no physical memory exists. This function allows
  2042. * an arch to push out the node boundaries so mem_map is allocated that can
  2043. * be used later.
  2044. */
  2045. #ifdef CONFIG_MEMORY_HOTPLUG_RESERVE
  2046. void __init push_node_boundaries(unsigned int nid,
  2047. unsigned long start_pfn, unsigned long end_pfn)
  2048. {
  2049. printk(KERN_DEBUG "Entering push_node_boundaries(%u, %lu, %lu)\n",
  2050. nid, start_pfn, end_pfn);
  2051. /* Initialise the boundary for this node if necessary */
  2052. if (node_boundary_end_pfn[nid] == 0)
  2053. node_boundary_start_pfn[nid] = -1UL;
  2054. /* Update the boundaries */
  2055. if (node_boundary_start_pfn[nid] > start_pfn)
  2056. node_boundary_start_pfn[nid] = start_pfn;
  2057. if (node_boundary_end_pfn[nid] < end_pfn)
  2058. node_boundary_end_pfn[nid] = end_pfn;
  2059. }
  2060. /* If necessary, push the node boundary out for reserve hotadd */
  2061. static void __init account_node_boundary(unsigned int nid,
  2062. unsigned long *start_pfn, unsigned long *end_pfn)
  2063. {
  2064. printk(KERN_DEBUG "Entering account_node_boundary(%u, %lu, %lu)\n",
  2065. nid, *start_pfn, *end_pfn);
  2066. /* Return if boundary information has not been provided */
  2067. if (node_boundary_end_pfn[nid] == 0)
  2068. return;
  2069. /* Check the boundaries and update if necessary */
  2070. if (node_boundary_start_pfn[nid] < *start_pfn)
  2071. *start_pfn = node_boundary_start_pfn[nid];
  2072. if (node_boundary_end_pfn[nid] > *end_pfn)
  2073. *end_pfn = node_boundary_end_pfn[nid];
  2074. }
  2075. #else
  2076. void __init push_node_boundaries(unsigned int nid,
  2077. unsigned long start_pfn, unsigned long end_pfn) {}
  2078. static void __init account_node_boundary(unsigned int nid,
  2079. unsigned long *start_pfn, unsigned long *end_pfn) {}
  2080. #endif
  2081. /**
  2082. * get_pfn_range_for_nid - Return the start and end page frames for a node
  2083. * @nid: The nid to return the range for. If MAX_NUMNODES, the min and max PFN are returned.
  2084. * @start_pfn: Passed by reference. On return, it will have the node start_pfn.
  2085. * @end_pfn: Passed by reference. On return, it will have the node end_pfn.
  2086. *
  2087. * It returns the start and end page frame of a node based on information
  2088. * provided by an arch calling add_active_range(). If called for a node
  2089. * with no available memory, a warning is printed and the start and end
  2090. * PFNs will be 0.
  2091. */
  2092. void __init get_pfn_range_for_nid(unsigned int nid,
  2093. unsigned long *start_pfn, unsigned long *end_pfn)
  2094. {
  2095. int i;
  2096. *start_pfn = -1UL;
  2097. *end_pfn = 0;
  2098. for_each_active_range_index_in_nid(i, nid) {
  2099. *start_pfn = min(*start_pfn, early_node_map[i].start_pfn);
  2100. *end_pfn = max(*end_pfn, early_node_map[i].end_pfn);
  2101. }
  2102. if (*start_pfn == -1UL) {
  2103. printk(KERN_WARNING "Node %u active with no memory\n", nid);
  2104. *start_pfn = 0;
  2105. }
  2106. /* Push the node boundaries out if requested */
  2107. account_node_boundary(nid, start_pfn, end_pfn);
  2108. }
  2109. /*
  2110. * Return the number of pages a zone spans in a node, including holes
  2111. * present_pages = zone_spanned_pages_in_node() - zone_absent_pages_in_node()
  2112. */
  2113. unsigned long __init zone_spanned_pages_in_node(int nid,
  2114. unsigned long zone_type,
  2115. unsigned long *ignored)
  2116. {
  2117. unsigned long node_start_pfn, node_end_pfn;
  2118. unsigned long zone_start_pfn, zone_end_pfn;
  2119. /* Get the start and end of the node and zone */
  2120. get_pfn_range_for_nid(nid, &node_start_pfn, &node_end_pfn);
  2121. zone_start_pfn = arch_zone_lowest_possible_pfn[zone_type];
  2122. zone_end_pfn = arch_zone_highest_possible_pfn[zone_type];
  2123. /* Check that this node has pages within the zone's required range */
  2124. if (zone_end_pfn < node_start_pfn || zone_start_pfn > node_end_pfn)
  2125. return 0;
  2126. /* Move the zone boundaries inside the node if necessary */
  2127. zone_end_pfn = min(zone_end_pfn, node_end_pfn);
  2128. zone_start_pfn = max(zone_start_pfn, node_start_pfn);
  2129. /* Return the spanned pages */
  2130. return zone_end_pfn - zone_start_pfn;
  2131. }
  2132. /*
  2133. * Return the number of holes in a range on a node. If nid is MAX_NUMNODES,
  2134. * then all holes in the requested range will be accounted for.
  2135. */
  2136. unsigned long __init __absent_pages_in_range(int nid,
  2137. unsigned long range_start_pfn,
  2138. unsigned long range_end_pfn)
  2139. {
  2140. int i = 0;
  2141. unsigned long prev_end_pfn = 0, hole_pages = 0;
  2142. unsigned long start_pfn;
  2143. /* Find the end_pfn of the first active range of pfns in the node */
  2144. i = first_active_region_index_in_nid(nid);
  2145. if (i == -1)
  2146. return 0;
  2147. /* Account for ranges before physical memory on this node */
  2148. if (early_node_map[i].start_pfn > range_start_pfn)
  2149. hole_pages = early_node_map[i].start_pfn - range_start_pfn;
  2150. prev_end_pfn = early_node_map[i].start_pfn;
  2151. /* Find all holes for the zone within the node */
  2152. for (; i != -1; i = next_active_region_index_in_nid(i, nid)) {
  2153. /* No need to continue if prev_end_pfn is outside the zone */
  2154. if (prev_end_pfn >= range_end_pfn)
  2155. break;
  2156. /* Make sure the end of the zone is not within the hole */
  2157. start_pfn = min(early_node_map[i].start_pfn, range_end_pfn);
  2158. prev_end_pfn = max(prev_end_pfn, range_start_pfn);
  2159. /* Update the hole size cound and move on */
  2160. if (start_pfn > range_start_pfn) {
  2161. BUG_ON(prev_end_pfn > start_pfn);
  2162. hole_pages += start_pfn - prev_end_pfn;
  2163. }
  2164. prev_end_pfn = early_node_map[i].end_pfn;
  2165. }
  2166. /* Account for ranges past physical memory on this node */
  2167. if (range_end_pfn > prev_end_pfn)
  2168. hole_pages += range_end_pfn -
  2169. max(range_start_pfn, prev_end_pfn);
  2170. return hole_pages;
  2171. }
  2172. /**
  2173. * absent_pages_in_range - Return number of page frames in holes within a range
  2174. * @start_pfn: The start PFN to start searching for holes
  2175. * @end_pfn: The end PFN to stop searching for holes
  2176. *
  2177. * It returns the number of pages frames in memory holes within a range.
  2178. */
  2179. unsigned long __init absent_pages_in_range(unsigned long start_pfn,
  2180. unsigned long end_pfn)
  2181. {
  2182. return __absent_pages_in_range(MAX_NUMNODES, start_pfn, end_pfn);
  2183. }
  2184. /* Return the number of page frames in holes in a zone on a node */
  2185. unsigned long __init zone_absent_pages_in_node(int nid,
  2186. unsigned long zone_type,
  2187. unsigned long *ignored)
  2188. {
  2189. unsigned long node_start_pfn, node_end_pfn;
  2190. unsigned long zone_start_pfn, zone_end_pfn;
  2191. get_pfn_range_for_nid(nid, &node_start_pfn, &node_end_pfn);
  2192. zone_start_pfn = max(arch_zone_lowest_possible_pfn[zone_type],
  2193. node_start_pfn);
  2194. zone_end_pfn = min(arch_zone_highest_possible_pfn[zone_type],
  2195. node_end_pfn);
  2196. return __absent_pages_in_range(nid, zone_start_pfn, zone_end_pfn);
  2197. }
  2198. #else
  2199. static inline unsigned long zone_spanned_pages_in_node(int nid,
  2200. unsigned long zone_type,
  2201. unsigned long *zones_size)
  2202. {
  2203. return zones_size[zone_type];
  2204. }
  2205. static inline unsigned long zone_absent_pages_in_node(int nid,
  2206. unsigned long zone_type,
  2207. unsigned long *zholes_size)
  2208. {
  2209. if (!zholes_size)
  2210. return 0;
  2211. return zholes_size[zone_type];
  2212. }
  2213. #endif
  2214. static void __init calculate_node_totalpages(struct pglist_data *pgdat,
  2215. unsigned long *zones_size, unsigned long *zholes_size)
  2216. {
  2217. unsigned long realtotalpages, totalpages = 0;
  2218. enum zone_type i;
  2219. for (i = 0; i < MAX_NR_ZONES; i++)
  2220. totalpages += zone_spanned_pages_in_node(pgdat->node_id, i,
  2221. zones_size);
  2222. pgdat->node_spanned_pages = totalpages;
  2223. realtotalpages = totalpages;
  2224. for (i = 0; i < MAX_NR_ZONES; i++)
  2225. realtotalpages -=
  2226. zone_absent_pages_in_node(pgdat->node_id, i,
  2227. zholes_size);
  2228. pgdat->node_present_pages = realtotalpages;
  2229. printk(KERN_DEBUG "On node %d totalpages: %lu\n", pgdat->node_id,
  2230. realtotalpages);
  2231. }
  2232. /*
  2233. * Set up the zone data structures:
  2234. * - mark all pages reserved
  2235. * - mark all memory queues empty
  2236. * - clear the memory bitmaps
  2237. */
  2238. static void __meminit free_area_init_core(struct pglist_data *pgdat,
  2239. unsigned long *zones_size, unsigned long *zholes_size)
  2240. {
  2241. enum zone_type j;
  2242. int nid = pgdat->node_id;
  2243. unsigned long zone_start_pfn = pgdat->node_start_pfn;
  2244. int ret;
  2245. pgdat_resize_init(pgdat);
  2246. pgdat->nr_zones = 0;
  2247. init_waitqueue_head(&pgdat->kswapd_wait);
  2248. pgdat->kswapd_max_order = 0;
  2249. for (j = 0; j < MAX_NR_ZONES; j++) {
  2250. struct zone *zone = pgdat->node_zones + j;
  2251. unsigned long size, realsize, memmap_pages;
  2252. size = zone_spanned_pages_in_node(nid, j, zones_size);
  2253. realsize = size - zone_absent_pages_in_node(nid, j,
  2254. zholes_size);
  2255. /*
  2256. * Adjust realsize so that it accounts for how much memory
  2257. * is used by this zone for memmap. This affects the watermark
  2258. * and per-cpu initialisations
  2259. */
  2260. memmap_pages = (size * sizeof(struct page)) >> PAGE_SHIFT;
  2261. if (realsize >= memmap_pages) {
  2262. realsize -= memmap_pages;
  2263. printk(KERN_DEBUG
  2264. " %s zone: %lu pages used for memmap\n",
  2265. zone_names[j], memmap_pages);
  2266. } else
  2267. printk(KERN_WARNING
  2268. " %s zone: %lu pages exceeds realsize %lu\n",
  2269. zone_names[j], memmap_pages, realsize);
  2270. /* Account for reserved pages */
  2271. if (j == 0 && realsize > dma_reserve) {
  2272. realsize -= dma_reserve;
  2273. printk(KERN_DEBUG " %s zone: %lu pages reserved\n",
  2274. zone_names[0], dma_reserve);
  2275. }
  2276. if (!is_highmem_idx(j))
  2277. nr_kernel_pages += realsize;
  2278. nr_all_pages += realsize;
  2279. zone->spanned_pages = size;
  2280. zone->present_pages = realsize;
  2281. #ifdef CONFIG_NUMA
  2282. zone->node = nid;
  2283. zone->min_unmapped_pages = (realsize*sysctl_min_unmapped_ratio)
  2284. / 100;
  2285. zone->min_slab_pages = (realsize * sysctl_min_slab_ratio) / 100;
  2286. #endif
  2287. zone->name = zone_names[j];
  2288. spin_lock_init(&zone->lock);
  2289. spin_lock_init(&zone->lru_lock);
  2290. zone_seqlock_init(zone);
  2291. zone->zone_pgdat = pgdat;
  2292. zone->prev_priority = DEF_PRIORITY;
  2293. zone_pcp_init(zone);
  2294. INIT_LIST_HEAD(&zone->active_list);
  2295. INIT_LIST_HEAD(&zone->inactive_list);
  2296. zone->nr_scan_active = 0;
  2297. zone->nr_scan_inactive = 0;
  2298. zap_zone_vm_stats(zone);
  2299. atomic_set(&zone->reclaim_in_progress, 0);
  2300. if (!size)
  2301. continue;
  2302. ret = init_currently_empty_zone(zone, zone_start_pfn,
  2303. size, MEMMAP_EARLY);
  2304. BUG_ON(ret);
  2305. zone_start_pfn += size;
  2306. }
  2307. }
  2308. static void __init alloc_node_mem_map(struct pglist_data *pgdat)
  2309. {
  2310. /* Skip empty nodes */
  2311. if (!pgdat->node_spanned_pages)
  2312. return;
  2313. #ifdef CONFIG_FLAT_NODE_MEM_MAP
  2314. /* ia64 gets its own node_mem_map, before this, without bootmem */
  2315. if (!pgdat->node_mem_map) {
  2316. unsigned long size, start, end;
  2317. struct page *map;
  2318. /*
  2319. * The zone's endpoints aren't required to be MAX_ORDER
  2320. * aligned but the node_mem_map endpoints must be in order
  2321. * for the buddy allocator to function correctly.
  2322. */
  2323. start = pgdat->node_start_pfn & ~(MAX_ORDER_NR_PAGES - 1);
  2324. end = pgdat->node_start_pfn + pgdat->node_spanned_pages;
  2325. end = ALIGN(end, MAX_ORDER_NR_PAGES);
  2326. size = (end - start) * sizeof(struct page);
  2327. map = alloc_remap(pgdat->node_id, size);
  2328. if (!map)
  2329. map = alloc_bootmem_node(pgdat, size);
  2330. pgdat->node_mem_map = map + (pgdat->node_start_pfn - start);
  2331. }
  2332. #ifdef CONFIG_FLATMEM
  2333. /*
  2334. * With no DISCONTIG, the global mem_map is just set as node 0's
  2335. */
  2336. if (pgdat == NODE_DATA(0)) {
  2337. mem_map = NODE_DATA(0)->node_mem_map;
  2338. #ifdef CONFIG_ARCH_POPULATES_NODE_MAP
  2339. if (page_to_pfn(mem_map) != pgdat->node_start_pfn)
  2340. mem_map -= pgdat->node_start_pfn;
  2341. #endif /* CONFIG_ARCH_POPULATES_NODE_MAP */
  2342. }
  2343. #endif
  2344. #endif /* CONFIG_FLAT_NODE_MEM_MAP */
  2345. }
  2346. void __meminit free_area_init_node(int nid, struct pglist_data *pgdat,
  2347. unsigned long *zones_size, unsigned long node_start_pfn,
  2348. unsigned long *zholes_size)
  2349. {
  2350. pgdat->node_id = nid;
  2351. pgdat->node_start_pfn = node_start_pfn;
  2352. calculate_node_totalpages(pgdat, zones_size, zholes_size);
  2353. alloc_node_mem_map(pgdat);
  2354. free_area_init_core(pgdat, zones_size, zholes_size);
  2355. }
  2356. #ifdef CONFIG_ARCH_POPULATES_NODE_MAP
  2357. /**
  2358. * add_active_range - Register a range of PFNs backed by physical memory
  2359. * @nid: The node ID the range resides on
  2360. * @start_pfn: The start PFN of the available physical memory
  2361. * @end_pfn: The end PFN of the available physical memory
  2362. *
  2363. * These ranges are stored in an early_node_map[] and later used by
  2364. * free_area_init_nodes() to calculate zone sizes and holes. If the
  2365. * range spans a memory hole, it is up to the architecture to ensure
  2366. * the memory is not freed by the bootmem allocator. If possible
  2367. * the range being registered will be merged with existing ranges.
  2368. */
  2369. void __init add_active_range(unsigned int nid, unsigned long start_pfn,
  2370. unsigned long end_pfn)
  2371. {
  2372. int i;
  2373. printk(KERN_DEBUG "Entering add_active_range(%d, %lu, %lu) "
  2374. "%d entries of %d used\n",
  2375. nid, start_pfn, end_pfn,
  2376. nr_nodemap_entries, MAX_ACTIVE_REGIONS);
  2377. /* Merge with existing active regions if possible */
  2378. for (i = 0; i < nr_nodemap_entries; i++) {
  2379. if (early_node_map[i].nid != nid)
  2380. continue;
  2381. /* Skip if an existing region covers this new one */
  2382. if (start_pfn >= early_node_map[i].start_pfn &&
  2383. end_pfn <= early_node_map[i].end_pfn)
  2384. return;
  2385. /* Merge forward if suitable */
  2386. if (start_pfn <= early_node_map[i].end_pfn &&
  2387. end_pfn > early_node_map[i].end_pfn) {
  2388. early_node_map[i].end_pfn = end_pfn;
  2389. return;
  2390. }
  2391. /* Merge backward if suitable */
  2392. if (start_pfn < early_node_map[i].end_pfn &&
  2393. end_pfn >= early_node_map[i].start_pfn) {
  2394. early_node_map[i].start_pfn = start_pfn;
  2395. return;
  2396. }
  2397. }
  2398. /* Check that early_node_map is large enough */
  2399. if (i >= MAX_ACTIVE_REGIONS) {
  2400. printk(KERN_CRIT "More than %d memory regions, truncating\n",
  2401. MAX_ACTIVE_REGIONS);
  2402. return;
  2403. }
  2404. early_node_map[i].nid = nid;
  2405. early_node_map[i].start_pfn = start_pfn;
  2406. early_node_map[i].end_pfn = end_pfn;
  2407. nr_nodemap_entries = i + 1;
  2408. }
  2409. /**
  2410. * shrink_active_range - Shrink an existing registered range of PFNs
  2411. * @nid: The node id the range is on that should be shrunk
  2412. * @old_end_pfn: The old end PFN of the range
  2413. * @new_end_pfn: The new PFN of the range
  2414. *
  2415. * i386 with NUMA use alloc_remap() to store a node_mem_map on a local node.
  2416. * The map is kept at the end physical page range that has already been
  2417. * registered with add_active_range(). This function allows an arch to shrink
  2418. * an existing registered range.
  2419. */
  2420. void __init shrink_active_range(unsigned int nid, unsigned long old_end_pfn,
  2421. unsigned long new_end_pfn)
  2422. {
  2423. int i;
  2424. /* Find the old active region end and shrink */
  2425. for_each_active_range_index_in_nid(i, nid)
  2426. if (early_node_map[i].end_pfn == old_end_pfn) {
  2427. early_node_map[i].end_pfn = new_end_pfn;
  2428. break;
  2429. }
  2430. }
  2431. /**
  2432. * remove_all_active_ranges - Remove all currently registered regions
  2433. *
  2434. * During discovery, it may be found that a table like SRAT is invalid
  2435. * and an alternative discovery method must be used. This function removes
  2436. * all currently registered regions.
  2437. */
  2438. void __init remove_all_active_ranges(void)
  2439. {
  2440. memset(early_node_map, 0, sizeof(early_node_map));
  2441. nr_nodemap_entries = 0;
  2442. #ifdef CONFIG_MEMORY_HOTPLUG_RESERVE
  2443. memset(node_boundary_start_pfn, 0, sizeof(node_boundary_start_pfn));
  2444. memset(node_boundary_end_pfn, 0, sizeof(node_boundary_end_pfn));
  2445. #endif /* CONFIG_MEMORY_HOTPLUG_RESERVE */
  2446. }
  2447. /* Compare two active node_active_regions */
  2448. static int __init cmp_node_active_region(const void *a, const void *b)
  2449. {
  2450. struct node_active_region *arange = (struct node_active_region *)a;
  2451. struct node_active_region *brange = (struct node_active_region *)b;
  2452. /* Done this way to avoid overflows */
  2453. if (arange->start_pfn > brange->start_pfn)
  2454. return 1;
  2455. if (arange->start_pfn < brange->start_pfn)
  2456. return -1;
  2457. return 0;
  2458. }
  2459. /* sort the node_map by start_pfn */
  2460. static void __init sort_node_map(void)
  2461. {
  2462. sort(early_node_map, (size_t)nr_nodemap_entries,
  2463. sizeof(struct node_active_region),
  2464. cmp_node_active_region, NULL);
  2465. }
  2466. /* Find the lowest pfn for a node */
  2467. unsigned long __init find_min_pfn_for_node(unsigned long nid)
  2468. {
  2469. int i;
  2470. unsigned long min_pfn = ULONG_MAX;
  2471. /* Assuming a sorted map, the first range found has the starting pfn */
  2472. for_each_active_range_index_in_nid(i, nid)
  2473. min_pfn = min(min_pfn, early_node_map[i].start_pfn);
  2474. if (min_pfn == ULONG_MAX) {
  2475. printk(KERN_WARNING
  2476. "Could not find start_pfn for node %lu\n", nid);
  2477. return 0;
  2478. }
  2479. return min_pfn;
  2480. }
  2481. /**
  2482. * find_min_pfn_with_active_regions - Find the minimum PFN registered
  2483. *
  2484. * It returns the minimum PFN based on information provided via
  2485. * add_active_range().
  2486. */
  2487. unsigned long __init find_min_pfn_with_active_regions(void)
  2488. {
  2489. return find_min_pfn_for_node(MAX_NUMNODES);
  2490. }
  2491. /**
  2492. * find_max_pfn_with_active_regions - Find the maximum PFN registered
  2493. *
  2494. * It returns the maximum PFN based on information provided via
  2495. * add_active_range().
  2496. */
  2497. unsigned long __init find_max_pfn_with_active_regions(void)
  2498. {
  2499. int i;
  2500. unsigned long max_pfn = 0;
  2501. for (i = 0; i < nr_nodemap_entries; i++)
  2502. max_pfn = max(max_pfn, early_node_map[i].end_pfn);
  2503. return max_pfn;
  2504. }
  2505. /**
  2506. * free_area_init_nodes - Initialise all pg_data_t and zone data
  2507. * @max_zone_pfn: an array of max PFNs for each zone
  2508. *
  2509. * This will call free_area_init_node() for each active node in the system.
  2510. * Using the page ranges provided by add_active_range(), the size of each
  2511. * zone in each node and their holes is calculated. If the maximum PFN
  2512. * between two adjacent zones match, it is assumed that the zone is empty.
  2513. * For example, if arch_max_dma_pfn == arch_max_dma32_pfn, it is assumed
  2514. * that arch_max_dma32_pfn has no pages. It is also assumed that a zone
  2515. * starts where the previous one ended. For example, ZONE_DMA32 starts
  2516. * at arch_max_dma_pfn.
  2517. */
  2518. void __init free_area_init_nodes(unsigned long *max_zone_pfn)
  2519. {
  2520. unsigned long nid;
  2521. enum zone_type i;
  2522. /* Sort early_node_map as initialisation assumes it is sorted */
  2523. sort_node_map();
  2524. /* Record where the zone boundaries are */
  2525. memset(arch_zone_lowest_possible_pfn, 0,
  2526. sizeof(arch_zone_lowest_possible_pfn));
  2527. memset(arch_zone_highest_possible_pfn, 0,
  2528. sizeof(arch_zone_highest_possible_pfn));
  2529. arch_zone_lowest_possible_pfn[0] = find_min_pfn_with_active_regions();
  2530. arch_zone_highest_possible_pfn[0] = max_zone_pfn[0];
  2531. for (i = 1; i < MAX_NR_ZONES; i++) {
  2532. arch_zone_lowest_possible_pfn[i] =
  2533. arch_zone_highest_possible_pfn[i-1];
  2534. arch_zone_highest_possible_pfn[i] =
  2535. max(max_zone_pfn[i], arch_zone_lowest_possible_pfn[i]);
  2536. }
  2537. /* Print out the zone ranges */
  2538. printk("Zone PFN ranges:\n");
  2539. for (i = 0; i < MAX_NR_ZONES; i++)
  2540. printk(" %-8s %8lu -> %8lu\n",
  2541. zone_names[i],
  2542. arch_zone_lowest_possible_pfn[i],
  2543. arch_zone_highest_possible_pfn[i]);
  2544. /* Print out the early_node_map[] */
  2545. printk("early_node_map[%d] active PFN ranges\n", nr_nodemap_entries);
  2546. for (i = 0; i < nr_nodemap_entries; i++)
  2547. printk(" %3d: %8lu -> %8lu\n", early_node_map[i].nid,
  2548. early_node_map[i].start_pfn,
  2549. early_node_map[i].end_pfn);
  2550. /* Initialise every node */
  2551. setup_nr_node_ids();
  2552. for_each_online_node(nid) {
  2553. pg_data_t *pgdat = NODE_DATA(nid);
  2554. free_area_init_node(nid, pgdat, NULL,
  2555. find_min_pfn_for_node(nid), NULL);
  2556. }
  2557. }
  2558. #endif /* CONFIG_ARCH_POPULATES_NODE_MAP */
  2559. /**
  2560. * set_dma_reserve - set the specified number of pages reserved in the first zone
  2561. * @new_dma_reserve: The number of pages to mark reserved
  2562. *
  2563. * The per-cpu batchsize and zone watermarks are determined by present_pages.
  2564. * In the DMA zone, a significant percentage may be consumed by kernel image
  2565. * and other unfreeable allocations which can skew the watermarks badly. This
  2566. * function may optionally be used to account for unfreeable pages in the
  2567. * first zone (e.g., ZONE_DMA). The effect will be lower watermarks and
  2568. * smaller per-cpu batchsize.
  2569. */
  2570. void __init set_dma_reserve(unsigned long new_dma_reserve)
  2571. {
  2572. dma_reserve = new_dma_reserve;
  2573. }
  2574. #ifndef CONFIG_NEED_MULTIPLE_NODES
  2575. static bootmem_data_t contig_bootmem_data;
  2576. struct pglist_data contig_page_data = { .bdata = &contig_bootmem_data };
  2577. EXPORT_SYMBOL(contig_page_data);
  2578. #endif
  2579. void __init free_area_init(unsigned long *zones_size)
  2580. {
  2581. free_area_init_node(0, NODE_DATA(0), zones_size,
  2582. __pa(PAGE_OFFSET) >> PAGE_SHIFT, NULL);
  2583. }
  2584. static int page_alloc_cpu_notify(struct notifier_block *self,
  2585. unsigned long action, void *hcpu)
  2586. {
  2587. int cpu = (unsigned long)hcpu;
  2588. if (action == CPU_DEAD) {
  2589. local_irq_disable();
  2590. __drain_pages(cpu);
  2591. vm_events_fold_cpu(cpu);
  2592. local_irq_enable();
  2593. refresh_cpu_vm_stats(cpu);
  2594. }
  2595. return NOTIFY_OK;
  2596. }
  2597. void __init page_alloc_init(void)
  2598. {
  2599. hotcpu_notifier(page_alloc_cpu_notify, 0);
  2600. }
  2601. /*
  2602. * calculate_totalreserve_pages - called when sysctl_lower_zone_reserve_ratio
  2603. * or min_free_kbytes changes.
  2604. */
  2605. static void calculate_totalreserve_pages(void)
  2606. {
  2607. struct pglist_data *pgdat;
  2608. unsigned long reserve_pages = 0;
  2609. enum zone_type i, j;
  2610. for_each_online_pgdat(pgdat) {
  2611. for (i = 0; i < MAX_NR_ZONES; i++) {
  2612. struct zone *zone = pgdat->node_zones + i;
  2613. unsigned long max = 0;
  2614. /* Find valid and maximum lowmem_reserve in the zone */
  2615. for (j = i; j < MAX_NR_ZONES; j++) {
  2616. if (zone->lowmem_reserve[j] > max)
  2617. max = zone->lowmem_reserve[j];
  2618. }
  2619. /* we treat pages_high as reserved pages. */
  2620. max += zone->pages_high;
  2621. if (max > zone->present_pages)
  2622. max = zone->present_pages;
  2623. reserve_pages += max;
  2624. }
  2625. }
  2626. totalreserve_pages = reserve_pages;
  2627. }
  2628. /*
  2629. * setup_per_zone_lowmem_reserve - called whenever
  2630. * sysctl_lower_zone_reserve_ratio changes. Ensures that each zone
  2631. * has a correct pages reserved value, so an adequate number of
  2632. * pages are left in the zone after a successful __alloc_pages().
  2633. */
  2634. static void setup_per_zone_lowmem_reserve(void)
  2635. {
  2636. struct pglist_data *pgdat;
  2637. enum zone_type j, idx;
  2638. for_each_online_pgdat(pgdat) {
  2639. for (j = 0; j < MAX_NR_ZONES; j++) {
  2640. struct zone *zone = pgdat->node_zones + j;
  2641. unsigned long present_pages = zone->present_pages;
  2642. zone->lowmem_reserve[j] = 0;
  2643. idx = j;
  2644. while (idx) {
  2645. struct zone *lower_zone;
  2646. idx--;
  2647. if (sysctl_lowmem_reserve_ratio[idx] < 1)
  2648. sysctl_lowmem_reserve_ratio[idx] = 1;
  2649. lower_zone = pgdat->node_zones + idx;
  2650. lower_zone->lowmem_reserve[j] = present_pages /
  2651. sysctl_lowmem_reserve_ratio[idx];
  2652. present_pages += lower_zone->present_pages;
  2653. }
  2654. }
  2655. }
  2656. /* update totalreserve_pages */
  2657. calculate_totalreserve_pages();
  2658. }
  2659. /**
  2660. * setup_per_zone_pages_min - called when min_free_kbytes changes.
  2661. *
  2662. * Ensures that the pages_{min,low,high} values for each zone are set correctly
  2663. * with respect to min_free_kbytes.
  2664. */
  2665. void setup_per_zone_pages_min(void)
  2666. {
  2667. unsigned long pages_min = min_free_kbytes >> (PAGE_SHIFT - 10);
  2668. unsigned long lowmem_pages = 0;
  2669. struct zone *zone;
  2670. unsigned long flags;
  2671. /* Calculate total number of !ZONE_HIGHMEM pages */
  2672. for_each_zone(zone) {
  2673. if (!is_highmem(zone))
  2674. lowmem_pages += zone->present_pages;
  2675. }
  2676. for_each_zone(zone) {
  2677. u64 tmp;
  2678. spin_lock_irqsave(&zone->lru_lock, flags);
  2679. tmp = (u64)pages_min * zone->present_pages;
  2680. do_div(tmp, lowmem_pages);
  2681. if (is_highmem(zone)) {
  2682. /*
  2683. * __GFP_HIGH and PF_MEMALLOC allocations usually don't
  2684. * need highmem pages, so cap pages_min to a small
  2685. * value here.
  2686. *
  2687. * The (pages_high-pages_low) and (pages_low-pages_min)
  2688. * deltas controls asynch page reclaim, and so should
  2689. * not be capped for highmem.
  2690. */
  2691. int min_pages;
  2692. min_pages = zone->present_pages / 1024;
  2693. if (min_pages < SWAP_CLUSTER_MAX)
  2694. min_pages = SWAP_CLUSTER_MAX;
  2695. if (min_pages > 128)
  2696. min_pages = 128;
  2697. zone->pages_min = min_pages;
  2698. } else {
  2699. /*
  2700. * If it's a lowmem zone, reserve a number of pages
  2701. * proportionate to the zone's size.
  2702. */
  2703. zone->pages_min = tmp;
  2704. }
  2705. zone->pages_low = zone->pages_min + (tmp >> 2);
  2706. zone->pages_high = zone->pages_min + (tmp >> 1);
  2707. spin_unlock_irqrestore(&zone->lru_lock, flags);
  2708. }
  2709. /* update totalreserve_pages */
  2710. calculate_totalreserve_pages();
  2711. }
  2712. /*
  2713. * Initialise min_free_kbytes.
  2714. *
  2715. * For small machines we want it small (128k min). For large machines
  2716. * we want it large (64MB max). But it is not linear, because network
  2717. * bandwidth does not increase linearly with machine size. We use
  2718. *
  2719. * min_free_kbytes = 4 * sqrt(lowmem_kbytes), for better accuracy:
  2720. * min_free_kbytes = sqrt(lowmem_kbytes * 16)
  2721. *
  2722. * which yields
  2723. *
  2724. * 16MB: 512k
  2725. * 32MB: 724k
  2726. * 64MB: 1024k
  2727. * 128MB: 1448k
  2728. * 256MB: 2048k
  2729. * 512MB: 2896k
  2730. * 1024MB: 4096k
  2731. * 2048MB: 5792k
  2732. * 4096MB: 8192k
  2733. * 8192MB: 11584k
  2734. * 16384MB: 16384k
  2735. */
  2736. static int __init init_per_zone_pages_min(void)
  2737. {
  2738. unsigned long lowmem_kbytes;
  2739. lowmem_kbytes = nr_free_buffer_pages() * (PAGE_SIZE >> 10);
  2740. min_free_kbytes = int_sqrt(lowmem_kbytes * 16);
  2741. if (min_free_kbytes < 128)
  2742. min_free_kbytes = 128;
  2743. if (min_free_kbytes > 65536)
  2744. min_free_kbytes = 65536;
  2745. setup_per_zone_pages_min();
  2746. setup_per_zone_lowmem_reserve();
  2747. return 0;
  2748. }
  2749. module_init(init_per_zone_pages_min)
  2750. /*
  2751. * min_free_kbytes_sysctl_handler - just a wrapper around proc_dointvec() so
  2752. * that we can call two helper functions whenever min_free_kbytes
  2753. * changes.
  2754. */
  2755. int min_free_kbytes_sysctl_handler(ctl_table *table, int write,
  2756. struct file *file, void __user *buffer, size_t *length, loff_t *ppos)
  2757. {
  2758. proc_dointvec(table, write, file, buffer, length, ppos);
  2759. setup_per_zone_pages_min();
  2760. return 0;
  2761. }
  2762. #ifdef CONFIG_NUMA
  2763. int sysctl_min_unmapped_ratio_sysctl_handler(ctl_table *table, int write,
  2764. struct file *file, void __user *buffer, size_t *length, loff_t *ppos)
  2765. {
  2766. struct zone *zone;
  2767. int rc;
  2768. rc = proc_dointvec_minmax(table, write, file, buffer, length, ppos);
  2769. if (rc)
  2770. return rc;
  2771. for_each_zone(zone)
  2772. zone->min_unmapped_pages = (zone->present_pages *
  2773. sysctl_min_unmapped_ratio) / 100;
  2774. return 0;
  2775. }
  2776. int sysctl_min_slab_ratio_sysctl_handler(ctl_table *table, int write,
  2777. struct file *file, void __user *buffer, size_t *length, loff_t *ppos)
  2778. {
  2779. struct zone *zone;
  2780. int rc;
  2781. rc = proc_dointvec_minmax(table, write, file, buffer, length, ppos);
  2782. if (rc)
  2783. return rc;
  2784. for_each_zone(zone)
  2785. zone->min_slab_pages = (zone->present_pages *
  2786. sysctl_min_slab_ratio) / 100;
  2787. return 0;
  2788. }
  2789. #endif
  2790. /*
  2791. * lowmem_reserve_ratio_sysctl_handler - just a wrapper around
  2792. * proc_dointvec() so that we can call setup_per_zone_lowmem_reserve()
  2793. * whenever sysctl_lowmem_reserve_ratio changes.
  2794. *
  2795. * The reserve ratio obviously has absolutely no relation with the
  2796. * pages_min watermarks. The lowmem reserve ratio can only make sense
  2797. * if in function of the boot time zone sizes.
  2798. */
  2799. int lowmem_reserve_ratio_sysctl_handler(ctl_table *table, int write,
  2800. struct file *file, void __user *buffer, size_t *length, loff_t *ppos)
  2801. {
  2802. proc_dointvec_minmax(table, write, file, buffer, length, ppos);
  2803. setup_per_zone_lowmem_reserve();
  2804. return 0;
  2805. }
  2806. /*
  2807. * percpu_pagelist_fraction - changes the pcp->high for each zone on each
  2808. * cpu. It is the fraction of total pages in each zone that a hot per cpu pagelist
  2809. * can have before it gets flushed back to buddy allocator.
  2810. */
  2811. int percpu_pagelist_fraction_sysctl_handler(ctl_table *table, int write,
  2812. struct file *file, void __user *buffer, size_t *length, loff_t *ppos)
  2813. {
  2814. struct zone *zone;
  2815. unsigned int cpu;
  2816. int ret;
  2817. ret = proc_dointvec_minmax(table, write, file, buffer, length, ppos);
  2818. if (!write || (ret == -EINVAL))
  2819. return ret;
  2820. for_each_zone(zone) {
  2821. for_each_online_cpu(cpu) {
  2822. unsigned long high;
  2823. high = zone->present_pages / percpu_pagelist_fraction;
  2824. setup_pagelist_highmark(zone_pcp(zone, cpu), high);
  2825. }
  2826. }
  2827. return 0;
  2828. }
  2829. int hashdist = HASHDIST_DEFAULT;
  2830. #ifdef CONFIG_NUMA
  2831. static int __init set_hashdist(char *str)
  2832. {
  2833. if (!str)
  2834. return 0;
  2835. hashdist = simple_strtoul(str, &str, 0);
  2836. return 1;
  2837. }
  2838. __setup("hashdist=", set_hashdist);
  2839. #endif
  2840. /*
  2841. * allocate a large system hash table from bootmem
  2842. * - it is assumed that the hash table must contain an exact power-of-2
  2843. * quantity of entries
  2844. * - limit is the number of hash buckets, not the total allocation size
  2845. */
  2846. void *__init alloc_large_system_hash(const char *tablename,
  2847. unsigned long bucketsize,
  2848. unsigned long numentries,
  2849. int scale,
  2850. int flags,
  2851. unsigned int *_hash_shift,
  2852. unsigned int *_hash_mask,
  2853. unsigned long limit)
  2854. {
  2855. unsigned long long max = limit;
  2856. unsigned long log2qty, size;
  2857. void *table = NULL;
  2858. /* allow the kernel cmdline to have a say */
  2859. if (!numentries) {
  2860. /* round applicable memory size up to nearest megabyte */
  2861. numentries = nr_kernel_pages;
  2862. numentries += (1UL << (20 - PAGE_SHIFT)) - 1;
  2863. numentries >>= 20 - PAGE_SHIFT;
  2864. numentries <<= 20 - PAGE_SHIFT;
  2865. /* limit to 1 bucket per 2^scale bytes of low memory */
  2866. if (scale > PAGE_SHIFT)
  2867. numentries >>= (scale - PAGE_SHIFT);
  2868. else
  2869. numentries <<= (PAGE_SHIFT - scale);
  2870. /* Make sure we've got at least a 0-order allocation.. */
  2871. if (unlikely((numentries * bucketsize) < PAGE_SIZE))
  2872. numentries = PAGE_SIZE / bucketsize;
  2873. }
  2874. numentries = roundup_pow_of_two(numentries);
  2875. /* limit allocation size to 1/16 total memory by default */
  2876. if (max == 0) {
  2877. max = ((unsigned long long)nr_all_pages << PAGE_SHIFT) >> 4;
  2878. do_div(max, bucketsize);
  2879. }
  2880. if (numentries > max)
  2881. numentries = max;
  2882. log2qty = ilog2(numentries);
  2883. do {
  2884. size = bucketsize << log2qty;
  2885. if (flags & HASH_EARLY)
  2886. table = alloc_bootmem(size);
  2887. else if (hashdist)
  2888. table = __vmalloc(size, GFP_ATOMIC, PAGE_KERNEL);
  2889. else {
  2890. unsigned long order;
  2891. for (order = 0; ((1UL << order) << PAGE_SHIFT) < size; order++)
  2892. ;
  2893. table = (void*) __get_free_pages(GFP_ATOMIC, order);
  2894. }
  2895. } while (!table && size > PAGE_SIZE && --log2qty);
  2896. if (!table)
  2897. panic("Failed to allocate %s hash table\n", tablename);
  2898. printk("%s hash table entries: %d (order: %d, %lu bytes)\n",
  2899. tablename,
  2900. (1U << log2qty),
  2901. ilog2(size) - PAGE_SHIFT,
  2902. size);
  2903. if (_hash_shift)
  2904. *_hash_shift = log2qty;
  2905. if (_hash_mask)
  2906. *_hash_mask = (1 << log2qty) - 1;
  2907. return table;
  2908. }
  2909. #ifdef CONFIG_OUT_OF_LINE_PFN_TO_PAGE
  2910. struct page *pfn_to_page(unsigned long pfn)
  2911. {
  2912. return __pfn_to_page(pfn);
  2913. }
  2914. unsigned long page_to_pfn(struct page *page)
  2915. {
  2916. return __page_to_pfn(page);
  2917. }
  2918. EXPORT_SYMBOL(pfn_to_page);
  2919. EXPORT_SYMBOL(page_to_pfn);
  2920. #endif /* CONFIG_OUT_OF_LINE_PFN_TO_PAGE */