page_alloc.c 64 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036203720382039204020412042204320442045204620472048204920502051205220532054205520562057205820592060206120622063206420652066206720682069207020712072207320742075207620772078207920802081208220832084208520862087208820892090209120922093209420952096209720982099210021012102210321042105210621072108210921102111211221132114211521162117211821192120212121222123212421252126212721282129213021312132213321342135213621372138213921402141214221432144214521462147214821492150215121522153215421552156215721582159216021612162216321642165216621672168216921702171217221732174217521762177217821792180218121822183218421852186218721882189219021912192219321942195219621972198219922002201220222032204220522062207220822092210221122122213221422152216221722182219222022212222222322242225222622272228222922302231223222332234223522362237223822392240224122422243224422452246224722482249225022512252225322542255225622572258225922602261226222632264226522662267226822692270227122722273227422752276227722782279228022812282228322842285228622872288228922902291229222932294229522962297229822992300230123022303230423052306230723082309231023112312231323142315231623172318231923202321232223232324232523262327232823292330233123322333233423352336233723382339234023412342234323442345234623472348234923502351235223532354235523562357235823592360236123622363236423652366236723682369237023712372237323742375237623772378237923802381238223832384238523862387238823892390239123922393239423952396239723982399240024012402240324042405240624072408240924102411241224132414241524162417241824192420242124222423242424252426242724282429243024312432243324342435243624372438243924402441244224432444244524462447244824492450245124522453245424552456245724582459246024612462246324642465246624672468246924702471247224732474247524762477247824792480248124822483248424852486248724882489249024912492249324942495249624972498249925002501250225032504250525062507250825092510251125122513251425152516251725182519252025212522252325242525252625272528252925302531253225332534253525362537253825392540254125422543254425452546254725482549255025512552255325542555255625572558255925602561256225632564256525662567256825692570257125722573257425752576257725782579258025812582258325842585258625872588258925902591259225932594259525962597259825992600260126022603260426052606260726082609261026112612261326142615261626172618261926202621262226232624
  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/config.h>
  17. #include <linux/stddef.h>
  18. #include <linux/mm.h>
  19. #include <linux/swap.h>
  20. #include <linux/interrupt.h>
  21. #include <linux/pagemap.h>
  22. #include <linux/bootmem.h>
  23. #include <linux/compiler.h>
  24. #include <linux/kernel.h>
  25. #include <linux/module.h>
  26. #include <linux/suspend.h>
  27. #include <linux/pagevec.h>
  28. #include <linux/blkdev.h>
  29. #include <linux/slab.h>
  30. #include <linux/notifier.h>
  31. #include <linux/topology.h>
  32. #include <linux/sysctl.h>
  33. #include <linux/cpu.h>
  34. #include <linux/cpuset.h>
  35. #include <linux/memory_hotplug.h>
  36. #include <linux/nodemask.h>
  37. #include <linux/vmalloc.h>
  38. #include <asm/tlbflush.h>
  39. #include "internal.h"
  40. /*
  41. * MCD - HACK: Find somewhere to initialize this EARLY, or make this
  42. * initializer cleaner
  43. */
  44. nodemask_t node_online_map __read_mostly = { { [0] = 1UL } };
  45. EXPORT_SYMBOL(node_online_map);
  46. nodemask_t node_possible_map __read_mostly = NODE_MASK_ALL;
  47. EXPORT_SYMBOL(node_possible_map);
  48. struct pglist_data *pgdat_list __read_mostly;
  49. unsigned long totalram_pages __read_mostly;
  50. unsigned long totalhigh_pages __read_mostly;
  51. long nr_swap_pages;
  52. /*
  53. * results with 256, 32 in the lowmem_reserve sysctl:
  54. * 1G machine -> (16M dma, 800M-16M normal, 1G-800M high)
  55. * 1G machine -> (16M dma, 784M normal, 224M high)
  56. * NORMAL allocation will leave 784M/256 of ram reserved in the ZONE_DMA
  57. * HIGHMEM allocation will leave 224M/32 of ram reserved in ZONE_NORMAL
  58. * HIGHMEM allocation will (224M+784M)/256 of ram reserved in ZONE_DMA
  59. *
  60. * TBD: should special case ZONE_DMA32 machines here - in those we normally
  61. * don't need any ZONE_NORMAL reservation
  62. */
  63. int sysctl_lowmem_reserve_ratio[MAX_NR_ZONES-1] = { 256, 256, 32 };
  64. EXPORT_SYMBOL(totalram_pages);
  65. EXPORT_SYMBOL(nr_swap_pages);
  66. /*
  67. * Used by page_zone() to look up the address of the struct zone whose
  68. * id is encoded in the upper bits of page->flags
  69. */
  70. struct zone *zone_table[1 << ZONETABLE_SHIFT] __read_mostly;
  71. EXPORT_SYMBOL(zone_table);
  72. static char *zone_names[MAX_NR_ZONES] = { "DMA", "DMA32", "Normal", "HighMem" };
  73. int min_free_kbytes = 1024;
  74. unsigned long __initdata nr_kernel_pages;
  75. unsigned long __initdata nr_all_pages;
  76. static int page_outside_zone_boundaries(struct zone *zone, struct page *page)
  77. {
  78. int ret = 0;
  79. unsigned seq;
  80. unsigned long pfn = page_to_pfn(page);
  81. do {
  82. seq = zone_span_seqbegin(zone);
  83. if (pfn >= zone->zone_start_pfn + zone->spanned_pages)
  84. ret = 1;
  85. else if (pfn < zone->zone_start_pfn)
  86. ret = 1;
  87. } while (zone_span_seqretry(zone, seq));
  88. return ret;
  89. }
  90. static int page_is_consistent(struct zone *zone, struct page *page)
  91. {
  92. #ifdef CONFIG_HOLES_IN_ZONE
  93. if (!pfn_valid(page_to_pfn(page)))
  94. return 0;
  95. #endif
  96. if (zone != page_zone(page))
  97. return 0;
  98. return 1;
  99. }
  100. /*
  101. * Temporary debugging check for pages not lying within a given zone.
  102. */
  103. static int bad_range(struct zone *zone, struct page *page)
  104. {
  105. if (page_outside_zone_boundaries(zone, page))
  106. return 1;
  107. if (!page_is_consistent(zone, page))
  108. return 1;
  109. return 0;
  110. }
  111. static void bad_page(const char *function, struct page *page)
  112. {
  113. printk(KERN_EMERG "Bad page state at %s (in process '%s', page %p)\n",
  114. function, current->comm, page);
  115. printk(KERN_EMERG "flags:0x%0*lx mapping:%p mapcount:%d count:%d\n",
  116. (int)(2*sizeof(page_flags_t)), (unsigned long)page->flags,
  117. page->mapping, page_mapcount(page), page_count(page));
  118. printk(KERN_EMERG "Backtrace:\n");
  119. dump_stack();
  120. printk(KERN_EMERG "Trying to fix it up, but a reboot is needed\n");
  121. page->flags &= ~(1 << PG_lru |
  122. 1 << PG_private |
  123. 1 << PG_locked |
  124. 1 << PG_active |
  125. 1 << PG_dirty |
  126. 1 << PG_reclaim |
  127. 1 << PG_slab |
  128. 1 << PG_swapcache |
  129. 1 << PG_writeback |
  130. 1 << PG_reserved );
  131. set_page_count(page, 0);
  132. reset_page_mapcount(page);
  133. page->mapping = NULL;
  134. add_taint(TAINT_BAD_PAGE);
  135. }
  136. #ifndef CONFIG_HUGETLB_PAGE
  137. #define prep_compound_page(page, order) do { } while (0)
  138. #define destroy_compound_page(page, order) do { } while (0)
  139. #else
  140. /*
  141. * Higher-order pages are called "compound pages". They are structured thusly:
  142. *
  143. * The first PAGE_SIZE page is called the "head page".
  144. *
  145. * The remaining PAGE_SIZE pages are called "tail pages".
  146. *
  147. * All pages have PG_compound set. All pages have their ->private pointing at
  148. * the head page (even the head page has this).
  149. *
  150. * The first tail page's ->mapping, if non-zero, holds the address of the
  151. * compound page's put_page() function.
  152. *
  153. * The order of the allocation is stored in the first tail page's ->index
  154. * This is only for debug at present. This usage means that zero-order pages
  155. * may not be compound.
  156. */
  157. static void prep_compound_page(struct page *page, unsigned long order)
  158. {
  159. int i;
  160. int nr_pages = 1 << order;
  161. page[1].mapping = NULL;
  162. page[1].index = order;
  163. for (i = 0; i < nr_pages; i++) {
  164. struct page *p = page + i;
  165. SetPageCompound(p);
  166. set_page_private(p, (unsigned long)page);
  167. }
  168. }
  169. static void destroy_compound_page(struct page *page, unsigned long order)
  170. {
  171. int i;
  172. int nr_pages = 1 << order;
  173. if (!PageCompound(page))
  174. return;
  175. if (page[1].index != order)
  176. bad_page(__FUNCTION__, page);
  177. for (i = 0; i < nr_pages; i++) {
  178. struct page *p = page + i;
  179. if (!PageCompound(p))
  180. bad_page(__FUNCTION__, page);
  181. if (page_private(p) != (unsigned long)page)
  182. bad_page(__FUNCTION__, page);
  183. ClearPageCompound(p);
  184. }
  185. }
  186. #endif /* CONFIG_HUGETLB_PAGE */
  187. /*
  188. * function for dealing with page's order in buddy system.
  189. * zone->lock is already acquired when we use these.
  190. * So, we don't need atomic page->flags operations here.
  191. */
  192. static inline unsigned long page_order(struct page *page) {
  193. return page_private(page);
  194. }
  195. static inline void set_page_order(struct page *page, int order) {
  196. set_page_private(page, order);
  197. __SetPagePrivate(page);
  198. }
  199. static inline void rmv_page_order(struct page *page)
  200. {
  201. __ClearPagePrivate(page);
  202. set_page_private(page, 0);
  203. }
  204. /*
  205. * Locate the struct page for both the matching buddy in our
  206. * pair (buddy1) and the combined O(n+1) page they form (page).
  207. *
  208. * 1) Any buddy B1 will have an order O twin B2 which satisfies
  209. * the following equation:
  210. * B2 = B1 ^ (1 << O)
  211. * For example, if the starting buddy (buddy2) is #8 its order
  212. * 1 buddy is #10:
  213. * B2 = 8 ^ (1 << 1) = 8 ^ 2 = 10
  214. *
  215. * 2) Any buddy B will have an order O+1 parent P which
  216. * satisfies the following equation:
  217. * P = B & ~(1 << O)
  218. *
  219. * Assumption: *_mem_map is contigious at least up to MAX_ORDER
  220. */
  221. static inline struct page *
  222. __page_find_buddy(struct page *page, unsigned long page_idx, unsigned int order)
  223. {
  224. unsigned long buddy_idx = page_idx ^ (1 << order);
  225. return page + (buddy_idx - page_idx);
  226. }
  227. static inline unsigned long
  228. __find_combined_index(unsigned long page_idx, unsigned int order)
  229. {
  230. return (page_idx & ~(1 << order));
  231. }
  232. /*
  233. * This function checks whether a page is free && is the buddy
  234. * we can do coalesce a page and its buddy if
  235. * (a) the buddy is free &&
  236. * (b) the buddy is on the buddy system &&
  237. * (c) a page and its buddy have the same order.
  238. * for recording page's order, we use page_private(page) and PG_private.
  239. *
  240. */
  241. static inline int page_is_buddy(struct page *page, int order)
  242. {
  243. if (PagePrivate(page) &&
  244. (page_order(page) == order) &&
  245. page_count(page) == 0)
  246. return 1;
  247. return 0;
  248. }
  249. /*
  250. * Freeing function for a buddy system allocator.
  251. *
  252. * The concept of a buddy system is to maintain direct-mapped table
  253. * (containing bit values) for memory blocks of various "orders".
  254. * The bottom level table contains the map for the smallest allocatable
  255. * units of memory (here, pages), and each level above it describes
  256. * pairs of units from the levels below, hence, "buddies".
  257. * At a high level, all that happens here is marking the table entry
  258. * at the bottom level available, and propagating the changes upward
  259. * as necessary, plus some accounting needed to play nicely with other
  260. * parts of the VM system.
  261. * At each level, we keep a list of pages, which are heads of continuous
  262. * free pages of length of (1 << order) and marked with PG_Private.Page's
  263. * order is recorded in page_private(page) field.
  264. * So when we are allocating or freeing one, we can derive the state of the
  265. * other. That is, if we allocate a small block, and both were
  266. * free, the remainder of the region must be split into blocks.
  267. * If a block is freed, and its buddy is also free, then this
  268. * triggers coalescing into a block of larger size.
  269. *
  270. * -- wli
  271. */
  272. static inline void __free_pages_bulk (struct page *page,
  273. struct zone *zone, unsigned int order)
  274. {
  275. unsigned long page_idx;
  276. int order_size = 1 << order;
  277. if (unlikely(order))
  278. destroy_compound_page(page, order);
  279. page_idx = page_to_pfn(page) & ((1 << MAX_ORDER) - 1);
  280. BUG_ON(page_idx & (order_size - 1));
  281. BUG_ON(bad_range(zone, page));
  282. zone->free_pages += order_size;
  283. while (order < MAX_ORDER-1) {
  284. unsigned long combined_idx;
  285. struct free_area *area;
  286. struct page *buddy;
  287. combined_idx = __find_combined_index(page_idx, order);
  288. buddy = __page_find_buddy(page, page_idx, order);
  289. if (bad_range(zone, buddy))
  290. break;
  291. if (!page_is_buddy(buddy, order))
  292. break; /* Move the buddy up one level. */
  293. list_del(&buddy->lru);
  294. area = zone->free_area + order;
  295. area->nr_free--;
  296. rmv_page_order(buddy);
  297. page = page + (combined_idx - page_idx);
  298. page_idx = combined_idx;
  299. order++;
  300. }
  301. set_page_order(page, order);
  302. list_add(&page->lru, &zone->free_area[order].free_list);
  303. zone->free_area[order].nr_free++;
  304. }
  305. static inline void free_pages_check(const char *function, struct page *page)
  306. {
  307. if ( page_mapcount(page) ||
  308. page->mapping != NULL ||
  309. page_count(page) != 0 ||
  310. (page->flags & (
  311. 1 << PG_lru |
  312. 1 << PG_private |
  313. 1 << PG_locked |
  314. 1 << PG_active |
  315. 1 << PG_reclaim |
  316. 1 << PG_slab |
  317. 1 << PG_swapcache |
  318. 1 << PG_writeback |
  319. 1 << PG_reserved )))
  320. bad_page(function, page);
  321. if (PageDirty(page))
  322. __ClearPageDirty(page);
  323. }
  324. /*
  325. * Frees a list of pages.
  326. * Assumes all pages on list are in same zone, and of same order.
  327. * count is the number of pages to free.
  328. *
  329. * If the zone was previously in an "all pages pinned" state then look to
  330. * see if this freeing clears that state.
  331. *
  332. * And clear the zone's pages_scanned counter, to hold off the "all pages are
  333. * pinned" detection logic.
  334. */
  335. static int
  336. free_pages_bulk(struct zone *zone, int count,
  337. struct list_head *list, unsigned int order)
  338. {
  339. unsigned long flags;
  340. struct page *page = NULL;
  341. int ret = 0;
  342. spin_lock_irqsave(&zone->lock, flags);
  343. zone->all_unreclaimable = 0;
  344. zone->pages_scanned = 0;
  345. while (!list_empty(list) && count--) {
  346. page = list_entry(list->prev, struct page, lru);
  347. /* have to delete it as __free_pages_bulk list manipulates */
  348. list_del(&page->lru);
  349. __free_pages_bulk(page, zone, order);
  350. ret++;
  351. }
  352. spin_unlock_irqrestore(&zone->lock, flags);
  353. return ret;
  354. }
  355. void __free_pages_ok(struct page *page, unsigned int order)
  356. {
  357. LIST_HEAD(list);
  358. int i;
  359. arch_free_page(page, order);
  360. mod_page_state(pgfree, 1 << order);
  361. #ifndef CONFIG_MMU
  362. if (order > 0)
  363. for (i = 1 ; i < (1 << order) ; ++i)
  364. __put_page(page + i);
  365. #endif
  366. for (i = 0 ; i < (1 << order) ; ++i)
  367. free_pages_check(__FUNCTION__, page + i);
  368. list_add(&page->lru, &list);
  369. kernel_map_pages(page, 1<<order, 0);
  370. free_pages_bulk(page_zone(page), 1, &list, order);
  371. }
  372. /*
  373. * The order of subdivision here is critical for the IO subsystem.
  374. * Please do not alter this order without good reasons and regression
  375. * testing. Specifically, as large blocks of memory are subdivided,
  376. * the order in which smaller blocks are delivered depends on the order
  377. * they're subdivided in this function. This is the primary factor
  378. * influencing the order in which pages are delivered to the IO
  379. * subsystem according to empirical testing, and this is also justified
  380. * by considering the behavior of a buddy system containing a single
  381. * large block of memory acted on by a series of small allocations.
  382. * This behavior is a critical factor in sglist merging's success.
  383. *
  384. * -- wli
  385. */
  386. static inline struct page *
  387. expand(struct zone *zone, struct page *page,
  388. int low, int high, struct free_area *area)
  389. {
  390. unsigned long size = 1 << high;
  391. while (high > low) {
  392. area--;
  393. high--;
  394. size >>= 1;
  395. BUG_ON(bad_range(zone, &page[size]));
  396. list_add(&page[size].lru, &area->free_list);
  397. area->nr_free++;
  398. set_page_order(&page[size], high);
  399. }
  400. return page;
  401. }
  402. void set_page_refs(struct page *page, int order)
  403. {
  404. #ifdef CONFIG_MMU
  405. set_page_count(page, 1);
  406. #else
  407. int i;
  408. /*
  409. * We need to reference all the pages for this order, otherwise if
  410. * anyone accesses one of the pages with (get/put) it will be freed.
  411. * - eg: access_process_vm()
  412. */
  413. for (i = 0; i < (1 << order); i++)
  414. set_page_count(page + i, 1);
  415. #endif /* CONFIG_MMU */
  416. }
  417. /*
  418. * This page is about to be returned from the page allocator
  419. */
  420. static void prep_new_page(struct page *page, int order)
  421. {
  422. if ( page_mapcount(page) ||
  423. page->mapping != NULL ||
  424. page_count(page) != 0 ||
  425. (page->flags & (
  426. 1 << PG_lru |
  427. 1 << PG_private |
  428. 1 << PG_locked |
  429. 1 << PG_active |
  430. 1 << PG_dirty |
  431. 1 << PG_reclaim |
  432. 1 << PG_slab |
  433. 1 << PG_swapcache |
  434. 1 << PG_writeback |
  435. 1 << PG_reserved )))
  436. bad_page(__FUNCTION__, page);
  437. page->flags &= ~(1 << PG_uptodate | 1 << PG_error |
  438. 1 << PG_referenced | 1 << PG_arch_1 |
  439. 1 << PG_checked | 1 << PG_mappedtodisk);
  440. set_page_private(page, 0);
  441. set_page_refs(page, order);
  442. kernel_map_pages(page, 1 << order, 1);
  443. }
  444. /*
  445. * Do the hard work of removing an element from the buddy allocator.
  446. * Call me with the zone->lock already held.
  447. */
  448. static struct page *__rmqueue(struct zone *zone, unsigned int order)
  449. {
  450. struct free_area * area;
  451. unsigned int current_order;
  452. struct page *page;
  453. for (current_order = order; current_order < MAX_ORDER; ++current_order) {
  454. area = zone->free_area + current_order;
  455. if (list_empty(&area->free_list))
  456. continue;
  457. page = list_entry(area->free_list.next, struct page, lru);
  458. list_del(&page->lru);
  459. rmv_page_order(page);
  460. area->nr_free--;
  461. zone->free_pages -= 1UL << order;
  462. return expand(zone, page, order, current_order, area);
  463. }
  464. return NULL;
  465. }
  466. /*
  467. * Obtain a specified number of elements from the buddy allocator, all under
  468. * a single hold of the lock, for efficiency. Add them to the supplied list.
  469. * Returns the number of new pages which were placed at *list.
  470. */
  471. static int rmqueue_bulk(struct zone *zone, unsigned int order,
  472. unsigned long count, struct list_head *list)
  473. {
  474. unsigned long flags;
  475. int i;
  476. int allocated = 0;
  477. struct page *page;
  478. spin_lock_irqsave(&zone->lock, flags);
  479. for (i = 0; i < count; ++i) {
  480. page = __rmqueue(zone, order);
  481. if (page == NULL)
  482. break;
  483. allocated++;
  484. list_add_tail(&page->lru, list);
  485. }
  486. spin_unlock_irqrestore(&zone->lock, flags);
  487. return allocated;
  488. }
  489. #ifdef CONFIG_NUMA
  490. /* Called from the slab reaper to drain remote pagesets */
  491. void drain_remote_pages(void)
  492. {
  493. struct zone *zone;
  494. int i;
  495. unsigned long flags;
  496. local_irq_save(flags);
  497. for_each_zone(zone) {
  498. struct per_cpu_pageset *pset;
  499. /* Do not drain local pagesets */
  500. if (zone->zone_pgdat->node_id == numa_node_id())
  501. continue;
  502. pset = zone->pageset[smp_processor_id()];
  503. for (i = 0; i < ARRAY_SIZE(pset->pcp); i++) {
  504. struct per_cpu_pages *pcp;
  505. pcp = &pset->pcp[i];
  506. if (pcp->count)
  507. pcp->count -= free_pages_bulk(zone, pcp->count,
  508. &pcp->list, 0);
  509. }
  510. }
  511. local_irq_restore(flags);
  512. }
  513. #endif
  514. #if defined(CONFIG_PM) || defined(CONFIG_HOTPLUG_CPU)
  515. static void __drain_pages(unsigned int cpu)
  516. {
  517. struct zone *zone;
  518. int i;
  519. for_each_zone(zone) {
  520. struct per_cpu_pageset *pset;
  521. pset = zone_pcp(zone, cpu);
  522. for (i = 0; i < ARRAY_SIZE(pset->pcp); i++) {
  523. struct per_cpu_pages *pcp;
  524. pcp = &pset->pcp[i];
  525. pcp->count -= free_pages_bulk(zone, pcp->count,
  526. &pcp->list, 0);
  527. }
  528. }
  529. }
  530. #endif /* CONFIG_PM || CONFIG_HOTPLUG_CPU */
  531. #ifdef CONFIG_PM
  532. void mark_free_pages(struct zone *zone)
  533. {
  534. unsigned long zone_pfn, flags;
  535. int order;
  536. struct list_head *curr;
  537. if (!zone->spanned_pages)
  538. return;
  539. spin_lock_irqsave(&zone->lock, flags);
  540. for (zone_pfn = 0; zone_pfn < zone->spanned_pages; ++zone_pfn)
  541. ClearPageNosaveFree(pfn_to_page(zone_pfn + zone->zone_start_pfn));
  542. for (order = MAX_ORDER - 1; order >= 0; --order)
  543. list_for_each(curr, &zone->free_area[order].free_list) {
  544. unsigned long start_pfn, i;
  545. start_pfn = page_to_pfn(list_entry(curr, struct page, lru));
  546. for (i=0; i < (1<<order); i++)
  547. SetPageNosaveFree(pfn_to_page(start_pfn+i));
  548. }
  549. spin_unlock_irqrestore(&zone->lock, flags);
  550. }
  551. /*
  552. * Spill all of this CPU's per-cpu pages back into the buddy allocator.
  553. */
  554. void drain_local_pages(void)
  555. {
  556. unsigned long flags;
  557. local_irq_save(flags);
  558. __drain_pages(smp_processor_id());
  559. local_irq_restore(flags);
  560. }
  561. #endif /* CONFIG_PM */
  562. static void zone_statistics(struct zonelist *zonelist, struct zone *z)
  563. {
  564. #ifdef CONFIG_NUMA
  565. unsigned long flags;
  566. int cpu;
  567. pg_data_t *pg = z->zone_pgdat;
  568. pg_data_t *orig = zonelist->zones[0]->zone_pgdat;
  569. struct per_cpu_pageset *p;
  570. local_irq_save(flags);
  571. cpu = smp_processor_id();
  572. p = zone_pcp(z,cpu);
  573. if (pg == orig) {
  574. p->numa_hit++;
  575. } else {
  576. p->numa_miss++;
  577. zone_pcp(zonelist->zones[0], cpu)->numa_foreign++;
  578. }
  579. if (pg == NODE_DATA(numa_node_id()))
  580. p->local_node++;
  581. else
  582. p->other_node++;
  583. local_irq_restore(flags);
  584. #endif
  585. }
  586. /*
  587. * Free a 0-order page
  588. */
  589. static void FASTCALL(free_hot_cold_page(struct page *page, int cold));
  590. static void fastcall free_hot_cold_page(struct page *page, int cold)
  591. {
  592. struct zone *zone = page_zone(page);
  593. struct per_cpu_pages *pcp;
  594. unsigned long flags;
  595. arch_free_page(page, 0);
  596. kernel_map_pages(page, 1, 0);
  597. inc_page_state(pgfree);
  598. if (PageAnon(page))
  599. page->mapping = NULL;
  600. free_pages_check(__FUNCTION__, page);
  601. pcp = &zone_pcp(zone, get_cpu())->pcp[cold];
  602. local_irq_save(flags);
  603. list_add(&page->lru, &pcp->list);
  604. pcp->count++;
  605. if (pcp->count >= pcp->high)
  606. pcp->count -= free_pages_bulk(zone, pcp->batch, &pcp->list, 0);
  607. local_irq_restore(flags);
  608. put_cpu();
  609. }
  610. void fastcall free_hot_page(struct page *page)
  611. {
  612. free_hot_cold_page(page, 0);
  613. }
  614. void fastcall free_cold_page(struct page *page)
  615. {
  616. free_hot_cold_page(page, 1);
  617. }
  618. static inline void prep_zero_page(struct page *page, int order, gfp_t gfp_flags)
  619. {
  620. int i;
  621. BUG_ON((gfp_flags & (__GFP_WAIT | __GFP_HIGHMEM)) == __GFP_HIGHMEM);
  622. for(i = 0; i < (1 << order); i++)
  623. clear_highpage(page + i);
  624. }
  625. /*
  626. * Really, prep_compound_page() should be called from __rmqueue_bulk(). But
  627. * we cheat by calling it from here, in the order > 0 path. Saves a branch
  628. * or two.
  629. */
  630. static struct page *
  631. buffered_rmqueue(struct zone *zone, int order, gfp_t gfp_flags)
  632. {
  633. unsigned long flags;
  634. struct page *page = NULL;
  635. int cold = !!(gfp_flags & __GFP_COLD);
  636. if (order == 0) {
  637. struct per_cpu_pages *pcp;
  638. pcp = &zone_pcp(zone, get_cpu())->pcp[cold];
  639. local_irq_save(flags);
  640. if (pcp->count <= pcp->low)
  641. pcp->count += rmqueue_bulk(zone, 0,
  642. pcp->batch, &pcp->list);
  643. if (pcp->count) {
  644. page = list_entry(pcp->list.next, struct page, lru);
  645. list_del(&page->lru);
  646. pcp->count--;
  647. }
  648. local_irq_restore(flags);
  649. put_cpu();
  650. }
  651. if (page == NULL) {
  652. spin_lock_irqsave(&zone->lock, flags);
  653. page = __rmqueue(zone, order);
  654. spin_unlock_irqrestore(&zone->lock, flags);
  655. }
  656. if (page != NULL) {
  657. BUG_ON(bad_range(zone, page));
  658. mod_page_state_zone(zone, pgalloc, 1 << order);
  659. prep_new_page(page, order);
  660. if (gfp_flags & __GFP_ZERO)
  661. prep_zero_page(page, order, gfp_flags);
  662. if (order && (gfp_flags & __GFP_COMP))
  663. prep_compound_page(page, order);
  664. }
  665. return page;
  666. }
  667. /*
  668. * Return 1 if free pages are above 'mark'. This takes into account the order
  669. * of the allocation.
  670. */
  671. int zone_watermark_ok(struct zone *z, int order, unsigned long mark,
  672. int classzone_idx, int can_try_harder, gfp_t gfp_high)
  673. {
  674. /* free_pages my go negative - that's OK */
  675. long min = mark, free_pages = z->free_pages - (1 << order) + 1;
  676. int o;
  677. if (gfp_high)
  678. min -= min / 2;
  679. if (can_try_harder)
  680. min -= min / 4;
  681. if (free_pages <= min + z->lowmem_reserve[classzone_idx])
  682. return 0;
  683. for (o = 0; o < order; o++) {
  684. /* At the next order, this order's pages become unavailable */
  685. free_pages -= z->free_area[o].nr_free << o;
  686. /* Require fewer higher order pages to be free */
  687. min >>= 1;
  688. if (free_pages <= min)
  689. return 0;
  690. }
  691. return 1;
  692. }
  693. static inline int
  694. should_reclaim_zone(struct zone *z, gfp_t gfp_mask)
  695. {
  696. if (!z->reclaim_pages)
  697. return 0;
  698. if (gfp_mask & __GFP_NORECLAIM)
  699. return 0;
  700. return 1;
  701. }
  702. /*
  703. * This is the 'heart' of the zoned buddy allocator.
  704. */
  705. struct page * fastcall
  706. __alloc_pages(gfp_t gfp_mask, unsigned int order,
  707. struct zonelist *zonelist)
  708. {
  709. const gfp_t wait = gfp_mask & __GFP_WAIT;
  710. struct zone **zones, *z;
  711. struct page *page;
  712. struct reclaim_state reclaim_state;
  713. struct task_struct *p = current;
  714. int i;
  715. int classzone_idx;
  716. int do_retry;
  717. int can_try_harder;
  718. int did_some_progress;
  719. might_sleep_if(wait);
  720. /*
  721. * The caller may dip into page reserves a bit more if the caller
  722. * cannot run direct reclaim, or is the caller has realtime scheduling
  723. * policy
  724. */
  725. can_try_harder = (unlikely(rt_task(p)) && !in_interrupt()) || !wait;
  726. zones = zonelist->zones; /* the list of zones suitable for gfp_mask */
  727. if (unlikely(zones[0] == NULL)) {
  728. /* Should this ever happen?? */
  729. return NULL;
  730. }
  731. classzone_idx = zone_idx(zones[0]);
  732. restart:
  733. /*
  734. * Go through the zonelist once, looking for a zone with enough free.
  735. * See also cpuset_zone_allowed() comment in kernel/cpuset.c.
  736. */
  737. for (i = 0; (z = zones[i]) != NULL; i++) {
  738. int do_reclaim = should_reclaim_zone(z, gfp_mask);
  739. if (!cpuset_zone_allowed(z, __GFP_HARDWALL))
  740. continue;
  741. /*
  742. * If the zone is to attempt early page reclaim then this loop
  743. * will try to reclaim pages and check the watermark a second
  744. * time before giving up and falling back to the next zone.
  745. */
  746. zone_reclaim_retry:
  747. if (!zone_watermark_ok(z, order, z->pages_low,
  748. classzone_idx, 0, 0)) {
  749. if (!do_reclaim)
  750. continue;
  751. else {
  752. zone_reclaim(z, gfp_mask, order);
  753. /* Only try reclaim once */
  754. do_reclaim = 0;
  755. goto zone_reclaim_retry;
  756. }
  757. }
  758. page = buffered_rmqueue(z, order, gfp_mask);
  759. if (page)
  760. goto got_pg;
  761. }
  762. for (i = 0; (z = zones[i]) != NULL; i++)
  763. wakeup_kswapd(z, order);
  764. /*
  765. * Go through the zonelist again. Let __GFP_HIGH and allocations
  766. * coming from realtime tasks to go deeper into reserves
  767. *
  768. * This is the last chance, in general, before the goto nopage.
  769. * Ignore cpuset if GFP_ATOMIC (!wait) rather than fail alloc.
  770. * See also cpuset_zone_allowed() comment in kernel/cpuset.c.
  771. */
  772. for (i = 0; (z = zones[i]) != NULL; i++) {
  773. if (!zone_watermark_ok(z, order, z->pages_min,
  774. classzone_idx, can_try_harder,
  775. gfp_mask & __GFP_HIGH))
  776. continue;
  777. if (wait && !cpuset_zone_allowed(z, gfp_mask))
  778. continue;
  779. page = buffered_rmqueue(z, order, gfp_mask);
  780. if (page)
  781. goto got_pg;
  782. }
  783. /* This allocation should allow future memory freeing. */
  784. if (((p->flags & PF_MEMALLOC) || unlikely(test_thread_flag(TIF_MEMDIE)))
  785. && !in_interrupt()) {
  786. if (!(gfp_mask & __GFP_NOMEMALLOC)) {
  787. /* go through the zonelist yet again, ignoring mins */
  788. for (i = 0; (z = zones[i]) != NULL; i++) {
  789. if (!cpuset_zone_allowed(z, gfp_mask))
  790. continue;
  791. page = buffered_rmqueue(z, order, gfp_mask);
  792. if (page)
  793. goto got_pg;
  794. }
  795. }
  796. goto nopage;
  797. }
  798. /* Atomic allocations - we can't balance anything */
  799. if (!wait)
  800. goto nopage;
  801. rebalance:
  802. cond_resched();
  803. /* We now go into synchronous reclaim */
  804. p->flags |= PF_MEMALLOC;
  805. reclaim_state.reclaimed_slab = 0;
  806. p->reclaim_state = &reclaim_state;
  807. did_some_progress = try_to_free_pages(zones, gfp_mask);
  808. p->reclaim_state = NULL;
  809. p->flags &= ~PF_MEMALLOC;
  810. cond_resched();
  811. if (likely(did_some_progress)) {
  812. for (i = 0; (z = zones[i]) != NULL; i++) {
  813. if (!zone_watermark_ok(z, order, z->pages_min,
  814. classzone_idx, can_try_harder,
  815. gfp_mask & __GFP_HIGH))
  816. continue;
  817. if (!cpuset_zone_allowed(z, gfp_mask))
  818. continue;
  819. page = buffered_rmqueue(z, order, gfp_mask);
  820. if (page)
  821. goto got_pg;
  822. }
  823. } else if ((gfp_mask & __GFP_FS) && !(gfp_mask & __GFP_NORETRY)) {
  824. /*
  825. * Go through the zonelist yet one more time, keep
  826. * very high watermark here, this is only to catch
  827. * a parallel oom killing, we must fail if we're still
  828. * under heavy pressure.
  829. */
  830. for (i = 0; (z = zones[i]) != NULL; i++) {
  831. if (!zone_watermark_ok(z, order, z->pages_high,
  832. classzone_idx, 0, 0))
  833. continue;
  834. if (!cpuset_zone_allowed(z, __GFP_HARDWALL))
  835. continue;
  836. page = buffered_rmqueue(z, order, gfp_mask);
  837. if (page)
  838. goto got_pg;
  839. }
  840. out_of_memory(gfp_mask, order);
  841. goto restart;
  842. }
  843. /*
  844. * Don't let big-order allocations loop unless the caller explicitly
  845. * requests that. Wait for some write requests to complete then retry.
  846. *
  847. * In this implementation, __GFP_REPEAT means __GFP_NOFAIL for order
  848. * <= 3, but that may not be true in other implementations.
  849. */
  850. do_retry = 0;
  851. if (!(gfp_mask & __GFP_NORETRY)) {
  852. if ((order <= 3) || (gfp_mask & __GFP_REPEAT))
  853. do_retry = 1;
  854. if (gfp_mask & __GFP_NOFAIL)
  855. do_retry = 1;
  856. }
  857. if (do_retry) {
  858. blk_congestion_wait(WRITE, HZ/50);
  859. goto rebalance;
  860. }
  861. nopage:
  862. if (!(gfp_mask & __GFP_NOWARN) && printk_ratelimit()) {
  863. printk(KERN_WARNING "%s: page allocation failure."
  864. " order:%d, mode:0x%x\n",
  865. p->comm, order, gfp_mask);
  866. dump_stack();
  867. show_mem();
  868. }
  869. return NULL;
  870. got_pg:
  871. zone_statistics(zonelist, z);
  872. return page;
  873. }
  874. EXPORT_SYMBOL(__alloc_pages);
  875. /*
  876. * Common helper functions.
  877. */
  878. fastcall unsigned long __get_free_pages(gfp_t gfp_mask, unsigned int order)
  879. {
  880. struct page * page;
  881. page = alloc_pages(gfp_mask, order);
  882. if (!page)
  883. return 0;
  884. return (unsigned long) page_address(page);
  885. }
  886. EXPORT_SYMBOL(__get_free_pages);
  887. fastcall unsigned long get_zeroed_page(gfp_t gfp_mask)
  888. {
  889. struct page * page;
  890. /*
  891. * get_zeroed_page() returns a 32-bit address, which cannot represent
  892. * a highmem page
  893. */
  894. BUG_ON((gfp_mask & __GFP_HIGHMEM) != 0);
  895. page = alloc_pages(gfp_mask | __GFP_ZERO, 0);
  896. if (page)
  897. return (unsigned long) page_address(page);
  898. return 0;
  899. }
  900. EXPORT_SYMBOL(get_zeroed_page);
  901. void __pagevec_free(struct pagevec *pvec)
  902. {
  903. int i = pagevec_count(pvec);
  904. while (--i >= 0)
  905. free_hot_cold_page(pvec->pages[i], pvec->cold);
  906. }
  907. fastcall void __free_pages(struct page *page, unsigned int order)
  908. {
  909. if (put_page_testzero(page)) {
  910. if (order == 0)
  911. free_hot_page(page);
  912. else
  913. __free_pages_ok(page, order);
  914. }
  915. }
  916. EXPORT_SYMBOL(__free_pages);
  917. fastcall void free_pages(unsigned long addr, unsigned int order)
  918. {
  919. if (addr != 0) {
  920. BUG_ON(!virt_addr_valid((void *)addr));
  921. __free_pages(virt_to_page((void *)addr), order);
  922. }
  923. }
  924. EXPORT_SYMBOL(free_pages);
  925. /*
  926. * Total amount of free (allocatable) RAM:
  927. */
  928. unsigned int nr_free_pages(void)
  929. {
  930. unsigned int sum = 0;
  931. struct zone *zone;
  932. for_each_zone(zone)
  933. sum += zone->free_pages;
  934. return sum;
  935. }
  936. EXPORT_SYMBOL(nr_free_pages);
  937. #ifdef CONFIG_NUMA
  938. unsigned int nr_free_pages_pgdat(pg_data_t *pgdat)
  939. {
  940. unsigned int i, sum = 0;
  941. for (i = 0; i < MAX_NR_ZONES; i++)
  942. sum += pgdat->node_zones[i].free_pages;
  943. return sum;
  944. }
  945. #endif
  946. static unsigned int nr_free_zone_pages(int offset)
  947. {
  948. /* Just pick one node, since fallback list is circular */
  949. pg_data_t *pgdat = NODE_DATA(numa_node_id());
  950. unsigned int sum = 0;
  951. struct zonelist *zonelist = pgdat->node_zonelists + offset;
  952. struct zone **zonep = zonelist->zones;
  953. struct zone *zone;
  954. for (zone = *zonep++; zone; zone = *zonep++) {
  955. unsigned long size = zone->present_pages;
  956. unsigned long high = zone->pages_high;
  957. if (size > high)
  958. sum += size - high;
  959. }
  960. return sum;
  961. }
  962. /*
  963. * Amount of free RAM allocatable within ZONE_DMA and ZONE_NORMAL
  964. */
  965. unsigned int nr_free_buffer_pages(void)
  966. {
  967. return nr_free_zone_pages(gfp_zone(GFP_USER));
  968. }
  969. /*
  970. * Amount of free RAM allocatable within all zones
  971. */
  972. unsigned int nr_free_pagecache_pages(void)
  973. {
  974. return nr_free_zone_pages(gfp_zone(GFP_HIGHUSER));
  975. }
  976. #ifdef CONFIG_HIGHMEM
  977. unsigned int nr_free_highpages (void)
  978. {
  979. pg_data_t *pgdat;
  980. unsigned int pages = 0;
  981. for_each_pgdat(pgdat)
  982. pages += pgdat->node_zones[ZONE_HIGHMEM].free_pages;
  983. return pages;
  984. }
  985. #endif
  986. #ifdef CONFIG_NUMA
  987. static void show_node(struct zone *zone)
  988. {
  989. printk("Node %d ", zone->zone_pgdat->node_id);
  990. }
  991. #else
  992. #define show_node(zone) do { } while (0)
  993. #endif
  994. /*
  995. * Accumulate the page_state information across all CPUs.
  996. * The result is unavoidably approximate - it can change
  997. * during and after execution of this function.
  998. */
  999. static DEFINE_PER_CPU(struct page_state, page_states) = {0};
  1000. atomic_t nr_pagecache = ATOMIC_INIT(0);
  1001. EXPORT_SYMBOL(nr_pagecache);
  1002. #ifdef CONFIG_SMP
  1003. DEFINE_PER_CPU(long, nr_pagecache_local) = 0;
  1004. #endif
  1005. void __get_page_state(struct page_state *ret, int nr, cpumask_t *cpumask)
  1006. {
  1007. int cpu = 0;
  1008. memset(ret, 0, sizeof(*ret));
  1009. cpus_and(*cpumask, *cpumask, cpu_online_map);
  1010. cpu = first_cpu(*cpumask);
  1011. while (cpu < NR_CPUS) {
  1012. unsigned long *in, *out, off;
  1013. in = (unsigned long *)&per_cpu(page_states, cpu);
  1014. cpu = next_cpu(cpu, *cpumask);
  1015. if (cpu < NR_CPUS)
  1016. prefetch(&per_cpu(page_states, cpu));
  1017. out = (unsigned long *)ret;
  1018. for (off = 0; off < nr; off++)
  1019. *out++ += *in++;
  1020. }
  1021. }
  1022. void get_page_state_node(struct page_state *ret, int node)
  1023. {
  1024. int nr;
  1025. cpumask_t mask = node_to_cpumask(node);
  1026. nr = offsetof(struct page_state, GET_PAGE_STATE_LAST);
  1027. nr /= sizeof(unsigned long);
  1028. __get_page_state(ret, nr+1, &mask);
  1029. }
  1030. void get_page_state(struct page_state *ret)
  1031. {
  1032. int nr;
  1033. cpumask_t mask = CPU_MASK_ALL;
  1034. nr = offsetof(struct page_state, GET_PAGE_STATE_LAST);
  1035. nr /= sizeof(unsigned long);
  1036. __get_page_state(ret, nr + 1, &mask);
  1037. }
  1038. void get_full_page_state(struct page_state *ret)
  1039. {
  1040. cpumask_t mask = CPU_MASK_ALL;
  1041. __get_page_state(ret, sizeof(*ret) / sizeof(unsigned long), &mask);
  1042. }
  1043. unsigned long __read_page_state(unsigned long offset)
  1044. {
  1045. unsigned long ret = 0;
  1046. int cpu;
  1047. for_each_online_cpu(cpu) {
  1048. unsigned long in;
  1049. in = (unsigned long)&per_cpu(page_states, cpu) + offset;
  1050. ret += *((unsigned long *)in);
  1051. }
  1052. return ret;
  1053. }
  1054. void __mod_page_state(unsigned long offset, unsigned long delta)
  1055. {
  1056. unsigned long flags;
  1057. void* ptr;
  1058. local_irq_save(flags);
  1059. ptr = &__get_cpu_var(page_states);
  1060. *(unsigned long*)(ptr + offset) += delta;
  1061. local_irq_restore(flags);
  1062. }
  1063. EXPORT_SYMBOL(__mod_page_state);
  1064. void __get_zone_counts(unsigned long *active, unsigned long *inactive,
  1065. unsigned long *free, struct pglist_data *pgdat)
  1066. {
  1067. struct zone *zones = pgdat->node_zones;
  1068. int i;
  1069. *active = 0;
  1070. *inactive = 0;
  1071. *free = 0;
  1072. for (i = 0; i < MAX_NR_ZONES; i++) {
  1073. *active += zones[i].nr_active;
  1074. *inactive += zones[i].nr_inactive;
  1075. *free += zones[i].free_pages;
  1076. }
  1077. }
  1078. void get_zone_counts(unsigned long *active,
  1079. unsigned long *inactive, unsigned long *free)
  1080. {
  1081. struct pglist_data *pgdat;
  1082. *active = 0;
  1083. *inactive = 0;
  1084. *free = 0;
  1085. for_each_pgdat(pgdat) {
  1086. unsigned long l, m, n;
  1087. __get_zone_counts(&l, &m, &n, pgdat);
  1088. *active += l;
  1089. *inactive += m;
  1090. *free += n;
  1091. }
  1092. }
  1093. void si_meminfo(struct sysinfo *val)
  1094. {
  1095. val->totalram = totalram_pages;
  1096. val->sharedram = 0;
  1097. val->freeram = nr_free_pages();
  1098. val->bufferram = nr_blockdev_pages();
  1099. #ifdef CONFIG_HIGHMEM
  1100. val->totalhigh = totalhigh_pages;
  1101. val->freehigh = nr_free_highpages();
  1102. #else
  1103. val->totalhigh = 0;
  1104. val->freehigh = 0;
  1105. #endif
  1106. val->mem_unit = PAGE_SIZE;
  1107. }
  1108. EXPORT_SYMBOL(si_meminfo);
  1109. #ifdef CONFIG_NUMA
  1110. void si_meminfo_node(struct sysinfo *val, int nid)
  1111. {
  1112. pg_data_t *pgdat = NODE_DATA(nid);
  1113. val->totalram = pgdat->node_present_pages;
  1114. val->freeram = nr_free_pages_pgdat(pgdat);
  1115. val->totalhigh = pgdat->node_zones[ZONE_HIGHMEM].present_pages;
  1116. val->freehigh = pgdat->node_zones[ZONE_HIGHMEM].free_pages;
  1117. val->mem_unit = PAGE_SIZE;
  1118. }
  1119. #endif
  1120. #define K(x) ((x) << (PAGE_SHIFT-10))
  1121. /*
  1122. * Show free area list (used inside shift_scroll-lock stuff)
  1123. * We also calculate the percentage fragmentation. We do this by counting the
  1124. * memory on each free list with the exception of the first item on the list.
  1125. */
  1126. void show_free_areas(void)
  1127. {
  1128. struct page_state ps;
  1129. int cpu, temperature;
  1130. unsigned long active;
  1131. unsigned long inactive;
  1132. unsigned long free;
  1133. struct zone *zone;
  1134. for_each_zone(zone) {
  1135. show_node(zone);
  1136. printk("%s per-cpu:", zone->name);
  1137. if (!zone->present_pages) {
  1138. printk(" empty\n");
  1139. continue;
  1140. } else
  1141. printk("\n");
  1142. for_each_cpu(cpu) {
  1143. struct per_cpu_pageset *pageset;
  1144. pageset = zone_pcp(zone, cpu);
  1145. for (temperature = 0; temperature < 2; temperature++)
  1146. printk("cpu %d %s: low %d, high %d, batch %d used:%d\n",
  1147. cpu,
  1148. temperature ? "cold" : "hot",
  1149. pageset->pcp[temperature].low,
  1150. pageset->pcp[temperature].high,
  1151. pageset->pcp[temperature].batch,
  1152. pageset->pcp[temperature].count);
  1153. }
  1154. }
  1155. get_page_state(&ps);
  1156. get_zone_counts(&active, &inactive, &free);
  1157. printk("Free pages: %11ukB (%ukB HighMem)\n",
  1158. K(nr_free_pages()),
  1159. K(nr_free_highpages()));
  1160. printk("Active:%lu inactive:%lu dirty:%lu writeback:%lu "
  1161. "unstable:%lu free:%u slab:%lu mapped:%lu pagetables:%lu\n",
  1162. active,
  1163. inactive,
  1164. ps.nr_dirty,
  1165. ps.nr_writeback,
  1166. ps.nr_unstable,
  1167. nr_free_pages(),
  1168. ps.nr_slab,
  1169. ps.nr_mapped,
  1170. ps.nr_page_table_pages);
  1171. for_each_zone(zone) {
  1172. int i;
  1173. show_node(zone);
  1174. printk("%s"
  1175. " free:%lukB"
  1176. " min:%lukB"
  1177. " low:%lukB"
  1178. " high:%lukB"
  1179. " active:%lukB"
  1180. " inactive:%lukB"
  1181. " present:%lukB"
  1182. " pages_scanned:%lu"
  1183. " all_unreclaimable? %s"
  1184. "\n",
  1185. zone->name,
  1186. K(zone->free_pages),
  1187. K(zone->pages_min),
  1188. K(zone->pages_low),
  1189. K(zone->pages_high),
  1190. K(zone->nr_active),
  1191. K(zone->nr_inactive),
  1192. K(zone->present_pages),
  1193. zone->pages_scanned,
  1194. (zone->all_unreclaimable ? "yes" : "no")
  1195. );
  1196. printk("lowmem_reserve[]:");
  1197. for (i = 0; i < MAX_NR_ZONES; i++)
  1198. printk(" %lu", zone->lowmem_reserve[i]);
  1199. printk("\n");
  1200. }
  1201. for_each_zone(zone) {
  1202. unsigned long nr, flags, order, total = 0;
  1203. show_node(zone);
  1204. printk("%s: ", zone->name);
  1205. if (!zone->present_pages) {
  1206. printk("empty\n");
  1207. continue;
  1208. }
  1209. spin_lock_irqsave(&zone->lock, flags);
  1210. for (order = 0; order < MAX_ORDER; order++) {
  1211. nr = zone->free_area[order].nr_free;
  1212. total += nr << order;
  1213. printk("%lu*%lukB ", nr, K(1UL) << order);
  1214. }
  1215. spin_unlock_irqrestore(&zone->lock, flags);
  1216. printk("= %lukB\n", K(total));
  1217. }
  1218. show_swap_cache_info();
  1219. }
  1220. /*
  1221. * Builds allocation fallback zone lists.
  1222. */
  1223. static int __init build_zonelists_node(pg_data_t *pgdat, struct zonelist *zonelist, int j, int k)
  1224. {
  1225. switch (k) {
  1226. struct zone *zone;
  1227. default:
  1228. BUG();
  1229. case ZONE_HIGHMEM:
  1230. zone = pgdat->node_zones + ZONE_HIGHMEM;
  1231. if (zone->present_pages) {
  1232. #ifndef CONFIG_HIGHMEM
  1233. BUG();
  1234. #endif
  1235. zonelist->zones[j++] = zone;
  1236. }
  1237. case ZONE_NORMAL:
  1238. zone = pgdat->node_zones + ZONE_NORMAL;
  1239. if (zone->present_pages)
  1240. zonelist->zones[j++] = zone;
  1241. case ZONE_DMA32:
  1242. zone = pgdat->node_zones + ZONE_DMA32;
  1243. if (zone->present_pages)
  1244. zonelist->zones[j++] = zone;
  1245. case ZONE_DMA:
  1246. zone = pgdat->node_zones + ZONE_DMA;
  1247. if (zone->present_pages)
  1248. zonelist->zones[j++] = zone;
  1249. }
  1250. return j;
  1251. }
  1252. static inline int highest_zone(int zone_bits)
  1253. {
  1254. int res = ZONE_NORMAL;
  1255. if (zone_bits & (__force int)__GFP_HIGHMEM)
  1256. res = ZONE_HIGHMEM;
  1257. if (zone_bits & (__force int)__GFP_DMA32)
  1258. res = ZONE_DMA32;
  1259. if (zone_bits & (__force int)__GFP_DMA)
  1260. res = ZONE_DMA;
  1261. return res;
  1262. }
  1263. #ifdef CONFIG_NUMA
  1264. #define MAX_NODE_LOAD (num_online_nodes())
  1265. static int __initdata node_load[MAX_NUMNODES];
  1266. /**
  1267. * find_next_best_node - find the next node that should appear in a given node's fallback list
  1268. * @node: node whose fallback list we're appending
  1269. * @used_node_mask: nodemask_t of already used nodes
  1270. *
  1271. * We use a number of factors to determine which is the next node that should
  1272. * appear on a given node's fallback list. The node should not have appeared
  1273. * already in @node's fallback list, and it should be the next closest node
  1274. * according to the distance array (which contains arbitrary distance values
  1275. * from each node to each node in the system), and should also prefer nodes
  1276. * with no CPUs, since presumably they'll have very little allocation pressure
  1277. * on them otherwise.
  1278. * It returns -1 if no node is found.
  1279. */
  1280. static int __init find_next_best_node(int node, nodemask_t *used_node_mask)
  1281. {
  1282. int i, n, val;
  1283. int min_val = INT_MAX;
  1284. int best_node = -1;
  1285. for_each_online_node(i) {
  1286. cpumask_t tmp;
  1287. /* Start from local node */
  1288. n = (node+i) % num_online_nodes();
  1289. /* Don't want a node to appear more than once */
  1290. if (node_isset(n, *used_node_mask))
  1291. continue;
  1292. /* Use the local node if we haven't already */
  1293. if (!node_isset(node, *used_node_mask)) {
  1294. best_node = node;
  1295. break;
  1296. }
  1297. /* Use the distance array to find the distance */
  1298. val = node_distance(node, n);
  1299. /* Give preference to headless and unused nodes */
  1300. tmp = node_to_cpumask(n);
  1301. if (!cpus_empty(tmp))
  1302. val += PENALTY_FOR_NODE_WITH_CPUS;
  1303. /* Slight preference for less loaded node */
  1304. val *= (MAX_NODE_LOAD*MAX_NUMNODES);
  1305. val += node_load[n];
  1306. if (val < min_val) {
  1307. min_val = val;
  1308. best_node = n;
  1309. }
  1310. }
  1311. if (best_node >= 0)
  1312. node_set(best_node, *used_node_mask);
  1313. return best_node;
  1314. }
  1315. static void __init build_zonelists(pg_data_t *pgdat)
  1316. {
  1317. int i, j, k, node, local_node;
  1318. int prev_node, load;
  1319. struct zonelist *zonelist;
  1320. nodemask_t used_mask;
  1321. /* initialize zonelists */
  1322. for (i = 0; i < GFP_ZONETYPES; i++) {
  1323. zonelist = pgdat->node_zonelists + i;
  1324. zonelist->zones[0] = NULL;
  1325. }
  1326. /* NUMA-aware ordering of nodes */
  1327. local_node = pgdat->node_id;
  1328. load = num_online_nodes();
  1329. prev_node = local_node;
  1330. nodes_clear(used_mask);
  1331. while ((node = find_next_best_node(local_node, &used_mask)) >= 0) {
  1332. /*
  1333. * We don't want to pressure a particular node.
  1334. * So adding penalty to the first node in same
  1335. * distance group to make it round-robin.
  1336. */
  1337. if (node_distance(local_node, node) !=
  1338. node_distance(local_node, prev_node))
  1339. node_load[node] += load;
  1340. prev_node = node;
  1341. load--;
  1342. for (i = 0; i < GFP_ZONETYPES; i++) {
  1343. zonelist = pgdat->node_zonelists + i;
  1344. for (j = 0; zonelist->zones[j] != NULL; j++);
  1345. k = highest_zone(i);
  1346. j = build_zonelists_node(NODE_DATA(node), zonelist, j, k);
  1347. zonelist->zones[j] = NULL;
  1348. }
  1349. }
  1350. }
  1351. #else /* CONFIG_NUMA */
  1352. static void __init build_zonelists(pg_data_t *pgdat)
  1353. {
  1354. int i, j, k, node, local_node;
  1355. local_node = pgdat->node_id;
  1356. for (i = 0; i < GFP_ZONETYPES; i++) {
  1357. struct zonelist *zonelist;
  1358. zonelist = pgdat->node_zonelists + i;
  1359. j = 0;
  1360. k = highest_zone(i);
  1361. j = build_zonelists_node(pgdat, zonelist, j, k);
  1362. /*
  1363. * Now we build the zonelist so that it contains the zones
  1364. * of all the other nodes.
  1365. * We don't want to pressure a particular node, so when
  1366. * building the zones for node N, we make sure that the
  1367. * zones coming right after the local ones are those from
  1368. * node N+1 (modulo N)
  1369. */
  1370. for (node = local_node + 1; node < MAX_NUMNODES; node++) {
  1371. if (!node_online(node))
  1372. continue;
  1373. j = build_zonelists_node(NODE_DATA(node), zonelist, j, k);
  1374. }
  1375. for (node = 0; node < local_node; node++) {
  1376. if (!node_online(node))
  1377. continue;
  1378. j = build_zonelists_node(NODE_DATA(node), zonelist, j, k);
  1379. }
  1380. zonelist->zones[j] = NULL;
  1381. }
  1382. }
  1383. #endif /* CONFIG_NUMA */
  1384. void __init build_all_zonelists(void)
  1385. {
  1386. int i;
  1387. for_each_online_node(i)
  1388. build_zonelists(NODE_DATA(i));
  1389. printk("Built %i zonelists\n", num_online_nodes());
  1390. cpuset_init_current_mems_allowed();
  1391. }
  1392. /*
  1393. * Helper functions to size the waitqueue hash table.
  1394. * Essentially these want to choose hash table sizes sufficiently
  1395. * large so that collisions trying to wait on pages are rare.
  1396. * But in fact, the number of active page waitqueues on typical
  1397. * systems is ridiculously low, less than 200. So this is even
  1398. * conservative, even though it seems large.
  1399. *
  1400. * The constant PAGES_PER_WAITQUEUE specifies the ratio of pages to
  1401. * waitqueues, i.e. the size of the waitq table given the number of pages.
  1402. */
  1403. #define PAGES_PER_WAITQUEUE 256
  1404. static inline unsigned long wait_table_size(unsigned long pages)
  1405. {
  1406. unsigned long size = 1;
  1407. pages /= PAGES_PER_WAITQUEUE;
  1408. while (size < pages)
  1409. size <<= 1;
  1410. /*
  1411. * Once we have dozens or even hundreds of threads sleeping
  1412. * on IO we've got bigger problems than wait queue collision.
  1413. * Limit the size of the wait table to a reasonable size.
  1414. */
  1415. size = min(size, 4096UL);
  1416. return max(size, 4UL);
  1417. }
  1418. /*
  1419. * This is an integer logarithm so that shifts can be used later
  1420. * to extract the more random high bits from the multiplicative
  1421. * hash function before the remainder is taken.
  1422. */
  1423. static inline unsigned long wait_table_bits(unsigned long size)
  1424. {
  1425. return ffz(~size);
  1426. }
  1427. #define LONG_ALIGN(x) (((x)+(sizeof(long))-1)&~((sizeof(long))-1))
  1428. static void __init calculate_zone_totalpages(struct pglist_data *pgdat,
  1429. unsigned long *zones_size, unsigned long *zholes_size)
  1430. {
  1431. unsigned long realtotalpages, totalpages = 0;
  1432. int i;
  1433. for (i = 0; i < MAX_NR_ZONES; i++)
  1434. totalpages += zones_size[i];
  1435. pgdat->node_spanned_pages = totalpages;
  1436. realtotalpages = totalpages;
  1437. if (zholes_size)
  1438. for (i = 0; i < MAX_NR_ZONES; i++)
  1439. realtotalpages -= zholes_size[i];
  1440. pgdat->node_present_pages = realtotalpages;
  1441. printk(KERN_DEBUG "On node %d totalpages: %lu\n", pgdat->node_id, realtotalpages);
  1442. }
  1443. /*
  1444. * Initially all pages are reserved - free ones are freed
  1445. * up by free_all_bootmem() once the early boot process is
  1446. * done. Non-atomic initialization, single-pass.
  1447. */
  1448. void __devinit memmap_init_zone(unsigned long size, int nid, unsigned long zone,
  1449. unsigned long start_pfn)
  1450. {
  1451. struct page *page;
  1452. unsigned long end_pfn = start_pfn + size;
  1453. unsigned long pfn;
  1454. for (pfn = start_pfn; pfn < end_pfn; pfn++, page++) {
  1455. if (!early_pfn_valid(pfn))
  1456. continue;
  1457. if (!early_pfn_in_nid(pfn, nid))
  1458. continue;
  1459. page = pfn_to_page(pfn);
  1460. set_page_links(page, zone, nid, pfn);
  1461. set_page_count(page, 1);
  1462. reset_page_mapcount(page);
  1463. SetPageReserved(page);
  1464. INIT_LIST_HEAD(&page->lru);
  1465. #ifdef WANT_PAGE_VIRTUAL
  1466. /* The shift won't overflow because ZONE_NORMAL is below 4G. */
  1467. if (!is_highmem_idx(zone))
  1468. set_page_address(page, __va(pfn << PAGE_SHIFT));
  1469. #endif
  1470. }
  1471. }
  1472. void zone_init_free_lists(struct pglist_data *pgdat, struct zone *zone,
  1473. unsigned long size)
  1474. {
  1475. int order;
  1476. for (order = 0; order < MAX_ORDER ; order++) {
  1477. INIT_LIST_HEAD(&zone->free_area[order].free_list);
  1478. zone->free_area[order].nr_free = 0;
  1479. }
  1480. }
  1481. #define ZONETABLE_INDEX(x, zone_nr) ((x << ZONES_SHIFT) | zone_nr)
  1482. void zonetable_add(struct zone *zone, int nid, int zid, unsigned long pfn,
  1483. unsigned long size)
  1484. {
  1485. unsigned long snum = pfn_to_section_nr(pfn);
  1486. unsigned long end = pfn_to_section_nr(pfn + size);
  1487. if (FLAGS_HAS_NODE)
  1488. zone_table[ZONETABLE_INDEX(nid, zid)] = zone;
  1489. else
  1490. for (; snum <= end; snum++)
  1491. zone_table[ZONETABLE_INDEX(snum, zid)] = zone;
  1492. }
  1493. #ifndef __HAVE_ARCH_MEMMAP_INIT
  1494. #define memmap_init(size, nid, zone, start_pfn) \
  1495. memmap_init_zone((size), (nid), (zone), (start_pfn))
  1496. #endif
  1497. static int __devinit zone_batchsize(struct zone *zone)
  1498. {
  1499. int batch;
  1500. /*
  1501. * The per-cpu-pages pools are set to around 1000th of the
  1502. * size of the zone. But no more than 1/2 of a meg.
  1503. *
  1504. * OK, so we don't know how big the cache is. So guess.
  1505. */
  1506. batch = zone->present_pages / 1024;
  1507. if (batch * PAGE_SIZE > 512 * 1024)
  1508. batch = (512 * 1024) / PAGE_SIZE;
  1509. batch /= 4; /* We effectively *= 4 below */
  1510. if (batch < 1)
  1511. batch = 1;
  1512. /*
  1513. * We will be trying to allcoate bigger chunks of contiguous
  1514. * memory of the order of fls(batch). This should result in
  1515. * better cache coloring.
  1516. *
  1517. * A sanity check also to ensure that batch is still in limits.
  1518. */
  1519. batch = (1 << fls(batch + batch/2));
  1520. if (fls(batch) >= (PAGE_SHIFT + MAX_ORDER - 2))
  1521. batch = PAGE_SHIFT + ((MAX_ORDER - 1 - PAGE_SHIFT)/2);
  1522. return batch;
  1523. }
  1524. inline void setup_pageset(struct per_cpu_pageset *p, unsigned long batch)
  1525. {
  1526. struct per_cpu_pages *pcp;
  1527. memset(p, 0, sizeof(*p));
  1528. pcp = &p->pcp[0]; /* hot */
  1529. pcp->count = 0;
  1530. pcp->low = 0;
  1531. pcp->high = 6 * batch;
  1532. pcp->batch = max(1UL, 1 * batch);
  1533. INIT_LIST_HEAD(&pcp->list);
  1534. pcp = &p->pcp[1]; /* cold*/
  1535. pcp->count = 0;
  1536. pcp->low = 0;
  1537. pcp->high = 2 * batch;
  1538. pcp->batch = max(1UL, batch/2);
  1539. INIT_LIST_HEAD(&pcp->list);
  1540. }
  1541. #ifdef CONFIG_NUMA
  1542. /*
  1543. * Boot pageset table. One per cpu which is going to be used for all
  1544. * zones and all nodes. The parameters will be set in such a way
  1545. * that an item put on a list will immediately be handed over to
  1546. * the buddy list. This is safe since pageset manipulation is done
  1547. * with interrupts disabled.
  1548. *
  1549. * Some NUMA counter updates may also be caught by the boot pagesets.
  1550. *
  1551. * The boot_pagesets must be kept even after bootup is complete for
  1552. * unused processors and/or zones. They do play a role for bootstrapping
  1553. * hotplugged processors.
  1554. *
  1555. * zoneinfo_show() and maybe other functions do
  1556. * not check if the processor is online before following the pageset pointer.
  1557. * Other parts of the kernel may not check if the zone is available.
  1558. */
  1559. static struct per_cpu_pageset
  1560. boot_pageset[NR_CPUS];
  1561. /*
  1562. * Dynamically allocate memory for the
  1563. * per cpu pageset array in struct zone.
  1564. */
  1565. static int __devinit process_zones(int cpu)
  1566. {
  1567. struct zone *zone, *dzone;
  1568. for_each_zone(zone) {
  1569. zone->pageset[cpu] = kmalloc_node(sizeof(struct per_cpu_pageset),
  1570. GFP_KERNEL, cpu_to_node(cpu));
  1571. if (!zone->pageset[cpu])
  1572. goto bad;
  1573. setup_pageset(zone->pageset[cpu], zone_batchsize(zone));
  1574. }
  1575. return 0;
  1576. bad:
  1577. for_each_zone(dzone) {
  1578. if (dzone == zone)
  1579. break;
  1580. kfree(dzone->pageset[cpu]);
  1581. dzone->pageset[cpu] = NULL;
  1582. }
  1583. return -ENOMEM;
  1584. }
  1585. static inline void free_zone_pagesets(int cpu)
  1586. {
  1587. #ifdef CONFIG_NUMA
  1588. struct zone *zone;
  1589. for_each_zone(zone) {
  1590. struct per_cpu_pageset *pset = zone_pcp(zone, cpu);
  1591. zone_pcp(zone, cpu) = NULL;
  1592. kfree(pset);
  1593. }
  1594. #endif
  1595. }
  1596. static int __devinit pageset_cpuup_callback(struct notifier_block *nfb,
  1597. unsigned long action,
  1598. void *hcpu)
  1599. {
  1600. int cpu = (long)hcpu;
  1601. int ret = NOTIFY_OK;
  1602. switch (action) {
  1603. case CPU_UP_PREPARE:
  1604. if (process_zones(cpu))
  1605. ret = NOTIFY_BAD;
  1606. break;
  1607. #ifdef CONFIG_HOTPLUG_CPU
  1608. case CPU_DEAD:
  1609. free_zone_pagesets(cpu);
  1610. break;
  1611. #endif
  1612. default:
  1613. break;
  1614. }
  1615. return ret;
  1616. }
  1617. static struct notifier_block pageset_notifier =
  1618. { &pageset_cpuup_callback, NULL, 0 };
  1619. void __init setup_per_cpu_pageset()
  1620. {
  1621. int err;
  1622. /* Initialize per_cpu_pageset for cpu 0.
  1623. * A cpuup callback will do this for every cpu
  1624. * as it comes online
  1625. */
  1626. err = process_zones(smp_processor_id());
  1627. BUG_ON(err);
  1628. register_cpu_notifier(&pageset_notifier);
  1629. }
  1630. #endif
  1631. static __devinit
  1632. void zone_wait_table_init(struct zone *zone, unsigned long zone_size_pages)
  1633. {
  1634. int i;
  1635. struct pglist_data *pgdat = zone->zone_pgdat;
  1636. /*
  1637. * The per-page waitqueue mechanism uses hashed waitqueues
  1638. * per zone.
  1639. */
  1640. zone->wait_table_size = wait_table_size(zone_size_pages);
  1641. zone->wait_table_bits = wait_table_bits(zone->wait_table_size);
  1642. zone->wait_table = (wait_queue_head_t *)
  1643. alloc_bootmem_node(pgdat, zone->wait_table_size
  1644. * sizeof(wait_queue_head_t));
  1645. for(i = 0; i < zone->wait_table_size; ++i)
  1646. init_waitqueue_head(zone->wait_table + i);
  1647. }
  1648. static __devinit void zone_pcp_init(struct zone *zone)
  1649. {
  1650. int cpu;
  1651. unsigned long batch = zone_batchsize(zone);
  1652. for (cpu = 0; cpu < NR_CPUS; cpu++) {
  1653. #ifdef CONFIG_NUMA
  1654. /* Early boot. Slab allocator not functional yet */
  1655. zone->pageset[cpu] = &boot_pageset[cpu];
  1656. setup_pageset(&boot_pageset[cpu],0);
  1657. #else
  1658. setup_pageset(zone_pcp(zone,cpu), batch);
  1659. #endif
  1660. }
  1661. printk(KERN_DEBUG " %s zone: %lu pages, LIFO batch:%lu\n",
  1662. zone->name, zone->present_pages, batch);
  1663. }
  1664. static __devinit void init_currently_empty_zone(struct zone *zone,
  1665. unsigned long zone_start_pfn, unsigned long size)
  1666. {
  1667. struct pglist_data *pgdat = zone->zone_pgdat;
  1668. zone_wait_table_init(zone, size);
  1669. pgdat->nr_zones = zone_idx(zone) + 1;
  1670. zone->zone_mem_map = pfn_to_page(zone_start_pfn);
  1671. zone->zone_start_pfn = zone_start_pfn;
  1672. memmap_init(size, pgdat->node_id, zone_idx(zone), zone_start_pfn);
  1673. zone_init_free_lists(pgdat, zone, zone->spanned_pages);
  1674. }
  1675. /*
  1676. * Set up the zone data structures:
  1677. * - mark all pages reserved
  1678. * - mark all memory queues empty
  1679. * - clear the memory bitmaps
  1680. */
  1681. static void __init free_area_init_core(struct pglist_data *pgdat,
  1682. unsigned long *zones_size, unsigned long *zholes_size)
  1683. {
  1684. unsigned long j;
  1685. int nid = pgdat->node_id;
  1686. unsigned long zone_start_pfn = pgdat->node_start_pfn;
  1687. pgdat_resize_init(pgdat);
  1688. pgdat->nr_zones = 0;
  1689. init_waitqueue_head(&pgdat->kswapd_wait);
  1690. pgdat->kswapd_max_order = 0;
  1691. for (j = 0; j < MAX_NR_ZONES; j++) {
  1692. struct zone *zone = pgdat->node_zones + j;
  1693. unsigned long size, realsize;
  1694. realsize = size = zones_size[j];
  1695. if (zholes_size)
  1696. realsize -= zholes_size[j];
  1697. if (j < ZONE_HIGHMEM)
  1698. nr_kernel_pages += realsize;
  1699. nr_all_pages += realsize;
  1700. zone->spanned_pages = size;
  1701. zone->present_pages = realsize;
  1702. zone->name = zone_names[j];
  1703. spin_lock_init(&zone->lock);
  1704. spin_lock_init(&zone->lru_lock);
  1705. zone_seqlock_init(zone);
  1706. zone->zone_pgdat = pgdat;
  1707. zone->free_pages = 0;
  1708. zone->temp_priority = zone->prev_priority = DEF_PRIORITY;
  1709. zone_pcp_init(zone);
  1710. INIT_LIST_HEAD(&zone->active_list);
  1711. INIT_LIST_HEAD(&zone->inactive_list);
  1712. zone->nr_scan_active = 0;
  1713. zone->nr_scan_inactive = 0;
  1714. zone->nr_active = 0;
  1715. zone->nr_inactive = 0;
  1716. atomic_set(&zone->reclaim_in_progress, 0);
  1717. if (!size)
  1718. continue;
  1719. zonetable_add(zone, nid, j, zone_start_pfn, size);
  1720. init_currently_empty_zone(zone, zone_start_pfn, size);
  1721. zone_start_pfn += size;
  1722. }
  1723. }
  1724. static void __init alloc_node_mem_map(struct pglist_data *pgdat)
  1725. {
  1726. /* Skip empty nodes */
  1727. if (!pgdat->node_spanned_pages)
  1728. return;
  1729. #ifdef CONFIG_FLAT_NODE_MEM_MAP
  1730. /* ia64 gets its own node_mem_map, before this, without bootmem */
  1731. if (!pgdat->node_mem_map) {
  1732. unsigned long size;
  1733. struct page *map;
  1734. size = (pgdat->node_spanned_pages + 1) * sizeof(struct page);
  1735. map = alloc_remap(pgdat->node_id, size);
  1736. if (!map)
  1737. map = alloc_bootmem_node(pgdat, size);
  1738. pgdat->node_mem_map = map;
  1739. }
  1740. #ifdef CONFIG_FLATMEM
  1741. /*
  1742. * With no DISCONTIG, the global mem_map is just set as node 0's
  1743. */
  1744. if (pgdat == NODE_DATA(0))
  1745. mem_map = NODE_DATA(0)->node_mem_map;
  1746. #endif
  1747. #endif /* CONFIG_FLAT_NODE_MEM_MAP */
  1748. }
  1749. void __init free_area_init_node(int nid, struct pglist_data *pgdat,
  1750. unsigned long *zones_size, unsigned long node_start_pfn,
  1751. unsigned long *zholes_size)
  1752. {
  1753. pgdat->node_id = nid;
  1754. pgdat->node_start_pfn = node_start_pfn;
  1755. calculate_zone_totalpages(pgdat, zones_size, zholes_size);
  1756. alloc_node_mem_map(pgdat);
  1757. free_area_init_core(pgdat, zones_size, zholes_size);
  1758. }
  1759. #ifndef CONFIG_NEED_MULTIPLE_NODES
  1760. static bootmem_data_t contig_bootmem_data;
  1761. struct pglist_data contig_page_data = { .bdata = &contig_bootmem_data };
  1762. EXPORT_SYMBOL(contig_page_data);
  1763. #endif
  1764. void __init free_area_init(unsigned long *zones_size)
  1765. {
  1766. free_area_init_node(0, NODE_DATA(0), zones_size,
  1767. __pa(PAGE_OFFSET) >> PAGE_SHIFT, NULL);
  1768. }
  1769. #ifdef CONFIG_PROC_FS
  1770. #include <linux/seq_file.h>
  1771. static void *frag_start(struct seq_file *m, loff_t *pos)
  1772. {
  1773. pg_data_t *pgdat;
  1774. loff_t node = *pos;
  1775. for (pgdat = pgdat_list; pgdat && node; pgdat = pgdat->pgdat_next)
  1776. --node;
  1777. return pgdat;
  1778. }
  1779. static void *frag_next(struct seq_file *m, void *arg, loff_t *pos)
  1780. {
  1781. pg_data_t *pgdat = (pg_data_t *)arg;
  1782. (*pos)++;
  1783. return pgdat->pgdat_next;
  1784. }
  1785. static void frag_stop(struct seq_file *m, void *arg)
  1786. {
  1787. }
  1788. /*
  1789. * This walks the free areas for each zone.
  1790. */
  1791. static int frag_show(struct seq_file *m, void *arg)
  1792. {
  1793. pg_data_t *pgdat = (pg_data_t *)arg;
  1794. struct zone *zone;
  1795. struct zone *node_zones = pgdat->node_zones;
  1796. unsigned long flags;
  1797. int order;
  1798. for (zone = node_zones; zone - node_zones < MAX_NR_ZONES; ++zone) {
  1799. if (!zone->present_pages)
  1800. continue;
  1801. spin_lock_irqsave(&zone->lock, flags);
  1802. seq_printf(m, "Node %d, zone %8s ", pgdat->node_id, zone->name);
  1803. for (order = 0; order < MAX_ORDER; ++order)
  1804. seq_printf(m, "%6lu ", zone->free_area[order].nr_free);
  1805. spin_unlock_irqrestore(&zone->lock, flags);
  1806. seq_putc(m, '\n');
  1807. }
  1808. return 0;
  1809. }
  1810. struct seq_operations fragmentation_op = {
  1811. .start = frag_start,
  1812. .next = frag_next,
  1813. .stop = frag_stop,
  1814. .show = frag_show,
  1815. };
  1816. /*
  1817. * Output information about zones in @pgdat.
  1818. */
  1819. static int zoneinfo_show(struct seq_file *m, void *arg)
  1820. {
  1821. pg_data_t *pgdat = arg;
  1822. struct zone *zone;
  1823. struct zone *node_zones = pgdat->node_zones;
  1824. unsigned long flags;
  1825. for (zone = node_zones; zone - node_zones < MAX_NR_ZONES; zone++) {
  1826. int i;
  1827. if (!zone->present_pages)
  1828. continue;
  1829. spin_lock_irqsave(&zone->lock, flags);
  1830. seq_printf(m, "Node %d, zone %8s", pgdat->node_id, zone->name);
  1831. seq_printf(m,
  1832. "\n pages free %lu"
  1833. "\n min %lu"
  1834. "\n low %lu"
  1835. "\n high %lu"
  1836. "\n active %lu"
  1837. "\n inactive %lu"
  1838. "\n scanned %lu (a: %lu i: %lu)"
  1839. "\n spanned %lu"
  1840. "\n present %lu",
  1841. zone->free_pages,
  1842. zone->pages_min,
  1843. zone->pages_low,
  1844. zone->pages_high,
  1845. zone->nr_active,
  1846. zone->nr_inactive,
  1847. zone->pages_scanned,
  1848. zone->nr_scan_active, zone->nr_scan_inactive,
  1849. zone->spanned_pages,
  1850. zone->present_pages);
  1851. seq_printf(m,
  1852. "\n protection: (%lu",
  1853. zone->lowmem_reserve[0]);
  1854. for (i = 1; i < ARRAY_SIZE(zone->lowmem_reserve); i++)
  1855. seq_printf(m, ", %lu", zone->lowmem_reserve[i]);
  1856. seq_printf(m,
  1857. ")"
  1858. "\n pagesets");
  1859. for (i = 0; i < ARRAY_SIZE(zone->pageset); i++) {
  1860. struct per_cpu_pageset *pageset;
  1861. int j;
  1862. pageset = zone_pcp(zone, i);
  1863. for (j = 0; j < ARRAY_SIZE(pageset->pcp); j++) {
  1864. if (pageset->pcp[j].count)
  1865. break;
  1866. }
  1867. if (j == ARRAY_SIZE(pageset->pcp))
  1868. continue;
  1869. for (j = 0; j < ARRAY_SIZE(pageset->pcp); j++) {
  1870. seq_printf(m,
  1871. "\n cpu: %i pcp: %i"
  1872. "\n count: %i"
  1873. "\n low: %i"
  1874. "\n high: %i"
  1875. "\n batch: %i",
  1876. i, j,
  1877. pageset->pcp[j].count,
  1878. pageset->pcp[j].low,
  1879. pageset->pcp[j].high,
  1880. pageset->pcp[j].batch);
  1881. }
  1882. #ifdef CONFIG_NUMA
  1883. seq_printf(m,
  1884. "\n numa_hit: %lu"
  1885. "\n numa_miss: %lu"
  1886. "\n numa_foreign: %lu"
  1887. "\n interleave_hit: %lu"
  1888. "\n local_node: %lu"
  1889. "\n other_node: %lu",
  1890. pageset->numa_hit,
  1891. pageset->numa_miss,
  1892. pageset->numa_foreign,
  1893. pageset->interleave_hit,
  1894. pageset->local_node,
  1895. pageset->other_node);
  1896. #endif
  1897. }
  1898. seq_printf(m,
  1899. "\n all_unreclaimable: %u"
  1900. "\n prev_priority: %i"
  1901. "\n temp_priority: %i"
  1902. "\n start_pfn: %lu",
  1903. zone->all_unreclaimable,
  1904. zone->prev_priority,
  1905. zone->temp_priority,
  1906. zone->zone_start_pfn);
  1907. spin_unlock_irqrestore(&zone->lock, flags);
  1908. seq_putc(m, '\n');
  1909. }
  1910. return 0;
  1911. }
  1912. struct seq_operations zoneinfo_op = {
  1913. .start = frag_start, /* iterate over all zones. The same as in
  1914. * fragmentation. */
  1915. .next = frag_next,
  1916. .stop = frag_stop,
  1917. .show = zoneinfo_show,
  1918. };
  1919. static char *vmstat_text[] = {
  1920. "nr_dirty",
  1921. "nr_writeback",
  1922. "nr_unstable",
  1923. "nr_page_table_pages",
  1924. "nr_mapped",
  1925. "nr_slab",
  1926. "pgpgin",
  1927. "pgpgout",
  1928. "pswpin",
  1929. "pswpout",
  1930. "pgalloc_high",
  1931. "pgalloc_normal",
  1932. "pgalloc_dma",
  1933. "pgfree",
  1934. "pgactivate",
  1935. "pgdeactivate",
  1936. "pgfault",
  1937. "pgmajfault",
  1938. "pgrefill_high",
  1939. "pgrefill_normal",
  1940. "pgrefill_dma",
  1941. "pgsteal_high",
  1942. "pgsteal_normal",
  1943. "pgsteal_dma",
  1944. "pgscan_kswapd_high",
  1945. "pgscan_kswapd_normal",
  1946. "pgscan_kswapd_dma",
  1947. "pgscan_direct_high",
  1948. "pgscan_direct_normal",
  1949. "pgscan_direct_dma",
  1950. "pginodesteal",
  1951. "slabs_scanned",
  1952. "kswapd_steal",
  1953. "kswapd_inodesteal",
  1954. "pageoutrun",
  1955. "allocstall",
  1956. "pgrotated",
  1957. "nr_bounce",
  1958. };
  1959. static void *vmstat_start(struct seq_file *m, loff_t *pos)
  1960. {
  1961. struct page_state *ps;
  1962. if (*pos >= ARRAY_SIZE(vmstat_text))
  1963. return NULL;
  1964. ps = kmalloc(sizeof(*ps), GFP_KERNEL);
  1965. m->private = ps;
  1966. if (!ps)
  1967. return ERR_PTR(-ENOMEM);
  1968. get_full_page_state(ps);
  1969. ps->pgpgin /= 2; /* sectors -> kbytes */
  1970. ps->pgpgout /= 2;
  1971. return (unsigned long *)ps + *pos;
  1972. }
  1973. static void *vmstat_next(struct seq_file *m, void *arg, loff_t *pos)
  1974. {
  1975. (*pos)++;
  1976. if (*pos >= ARRAY_SIZE(vmstat_text))
  1977. return NULL;
  1978. return (unsigned long *)m->private + *pos;
  1979. }
  1980. static int vmstat_show(struct seq_file *m, void *arg)
  1981. {
  1982. unsigned long *l = arg;
  1983. unsigned long off = l - (unsigned long *)m->private;
  1984. seq_printf(m, "%s %lu\n", vmstat_text[off], *l);
  1985. return 0;
  1986. }
  1987. static void vmstat_stop(struct seq_file *m, void *arg)
  1988. {
  1989. kfree(m->private);
  1990. m->private = NULL;
  1991. }
  1992. struct seq_operations vmstat_op = {
  1993. .start = vmstat_start,
  1994. .next = vmstat_next,
  1995. .stop = vmstat_stop,
  1996. .show = vmstat_show,
  1997. };
  1998. #endif /* CONFIG_PROC_FS */
  1999. #ifdef CONFIG_HOTPLUG_CPU
  2000. static int page_alloc_cpu_notify(struct notifier_block *self,
  2001. unsigned long action, void *hcpu)
  2002. {
  2003. int cpu = (unsigned long)hcpu;
  2004. long *count;
  2005. unsigned long *src, *dest;
  2006. if (action == CPU_DEAD) {
  2007. int i;
  2008. /* Drain local pagecache count. */
  2009. count = &per_cpu(nr_pagecache_local, cpu);
  2010. atomic_add(*count, &nr_pagecache);
  2011. *count = 0;
  2012. local_irq_disable();
  2013. __drain_pages(cpu);
  2014. /* Add dead cpu's page_states to our own. */
  2015. dest = (unsigned long *)&__get_cpu_var(page_states);
  2016. src = (unsigned long *)&per_cpu(page_states, cpu);
  2017. for (i = 0; i < sizeof(struct page_state)/sizeof(unsigned long);
  2018. i++) {
  2019. dest[i] += src[i];
  2020. src[i] = 0;
  2021. }
  2022. local_irq_enable();
  2023. }
  2024. return NOTIFY_OK;
  2025. }
  2026. #endif /* CONFIG_HOTPLUG_CPU */
  2027. void __init page_alloc_init(void)
  2028. {
  2029. hotcpu_notifier(page_alloc_cpu_notify, 0);
  2030. }
  2031. /*
  2032. * setup_per_zone_lowmem_reserve - called whenever
  2033. * sysctl_lower_zone_reserve_ratio changes. Ensures that each zone
  2034. * has a correct pages reserved value, so an adequate number of
  2035. * pages are left in the zone after a successful __alloc_pages().
  2036. */
  2037. static void setup_per_zone_lowmem_reserve(void)
  2038. {
  2039. struct pglist_data *pgdat;
  2040. int j, idx;
  2041. for_each_pgdat(pgdat) {
  2042. for (j = 0; j < MAX_NR_ZONES; j++) {
  2043. struct zone *zone = pgdat->node_zones + j;
  2044. unsigned long present_pages = zone->present_pages;
  2045. zone->lowmem_reserve[j] = 0;
  2046. for (idx = j-1; idx >= 0; idx--) {
  2047. struct zone *lower_zone;
  2048. if (sysctl_lowmem_reserve_ratio[idx] < 1)
  2049. sysctl_lowmem_reserve_ratio[idx] = 1;
  2050. lower_zone = pgdat->node_zones + idx;
  2051. lower_zone->lowmem_reserve[j] = present_pages /
  2052. sysctl_lowmem_reserve_ratio[idx];
  2053. present_pages += lower_zone->present_pages;
  2054. }
  2055. }
  2056. }
  2057. }
  2058. /*
  2059. * setup_per_zone_pages_min - called when min_free_kbytes changes. Ensures
  2060. * that the pages_{min,low,high} values for each zone are set correctly
  2061. * with respect to min_free_kbytes.
  2062. */
  2063. void setup_per_zone_pages_min(void)
  2064. {
  2065. unsigned long pages_min = min_free_kbytes >> (PAGE_SHIFT - 10);
  2066. unsigned long lowmem_pages = 0;
  2067. struct zone *zone;
  2068. unsigned long flags;
  2069. /* Calculate total number of !ZONE_HIGHMEM pages */
  2070. for_each_zone(zone) {
  2071. if (!is_highmem(zone))
  2072. lowmem_pages += zone->present_pages;
  2073. }
  2074. for_each_zone(zone) {
  2075. spin_lock_irqsave(&zone->lru_lock, flags);
  2076. if (is_highmem(zone)) {
  2077. /*
  2078. * Often, highmem doesn't need to reserve any pages.
  2079. * But the pages_min/low/high values are also used for
  2080. * batching up page reclaim activity so we need a
  2081. * decent value here.
  2082. */
  2083. int min_pages;
  2084. min_pages = zone->present_pages / 1024;
  2085. if (min_pages < SWAP_CLUSTER_MAX)
  2086. min_pages = SWAP_CLUSTER_MAX;
  2087. if (min_pages > 128)
  2088. min_pages = 128;
  2089. zone->pages_min = min_pages;
  2090. } else {
  2091. /* if it's a lowmem zone, reserve a number of pages
  2092. * proportionate to the zone's size.
  2093. */
  2094. zone->pages_min = (pages_min * zone->present_pages) /
  2095. lowmem_pages;
  2096. }
  2097. /*
  2098. * When interpreting these watermarks, just keep in mind that:
  2099. * zone->pages_min == (zone->pages_min * 4) / 4;
  2100. */
  2101. zone->pages_low = (zone->pages_min * 5) / 4;
  2102. zone->pages_high = (zone->pages_min * 6) / 4;
  2103. spin_unlock_irqrestore(&zone->lru_lock, flags);
  2104. }
  2105. }
  2106. /*
  2107. * Initialise min_free_kbytes.
  2108. *
  2109. * For small machines we want it small (128k min). For large machines
  2110. * we want it large (64MB max). But it is not linear, because network
  2111. * bandwidth does not increase linearly with machine size. We use
  2112. *
  2113. * min_free_kbytes = 4 * sqrt(lowmem_kbytes), for better accuracy:
  2114. * min_free_kbytes = sqrt(lowmem_kbytes * 16)
  2115. *
  2116. * which yields
  2117. *
  2118. * 16MB: 512k
  2119. * 32MB: 724k
  2120. * 64MB: 1024k
  2121. * 128MB: 1448k
  2122. * 256MB: 2048k
  2123. * 512MB: 2896k
  2124. * 1024MB: 4096k
  2125. * 2048MB: 5792k
  2126. * 4096MB: 8192k
  2127. * 8192MB: 11584k
  2128. * 16384MB: 16384k
  2129. */
  2130. static int __init init_per_zone_pages_min(void)
  2131. {
  2132. unsigned long lowmem_kbytes;
  2133. lowmem_kbytes = nr_free_buffer_pages() * (PAGE_SIZE >> 10);
  2134. min_free_kbytes = int_sqrt(lowmem_kbytes * 16);
  2135. if (min_free_kbytes < 128)
  2136. min_free_kbytes = 128;
  2137. if (min_free_kbytes > 65536)
  2138. min_free_kbytes = 65536;
  2139. setup_per_zone_pages_min();
  2140. setup_per_zone_lowmem_reserve();
  2141. return 0;
  2142. }
  2143. module_init(init_per_zone_pages_min)
  2144. /*
  2145. * min_free_kbytes_sysctl_handler - just a wrapper around proc_dointvec() so
  2146. * that we can call two helper functions whenever min_free_kbytes
  2147. * changes.
  2148. */
  2149. int min_free_kbytes_sysctl_handler(ctl_table *table, int write,
  2150. struct file *file, void __user *buffer, size_t *length, loff_t *ppos)
  2151. {
  2152. proc_dointvec(table, write, file, buffer, length, ppos);
  2153. setup_per_zone_pages_min();
  2154. return 0;
  2155. }
  2156. /*
  2157. * lowmem_reserve_ratio_sysctl_handler - just a wrapper around
  2158. * proc_dointvec() so that we can call setup_per_zone_lowmem_reserve()
  2159. * whenever sysctl_lowmem_reserve_ratio changes.
  2160. *
  2161. * The reserve ratio obviously has absolutely no relation with the
  2162. * pages_min watermarks. The lowmem reserve ratio can only make sense
  2163. * if in function of the boot time zone sizes.
  2164. */
  2165. int lowmem_reserve_ratio_sysctl_handler(ctl_table *table, int write,
  2166. struct file *file, void __user *buffer, size_t *length, loff_t *ppos)
  2167. {
  2168. proc_dointvec_minmax(table, write, file, buffer, length, ppos);
  2169. setup_per_zone_lowmem_reserve();
  2170. return 0;
  2171. }
  2172. __initdata int hashdist = HASHDIST_DEFAULT;
  2173. #ifdef CONFIG_NUMA
  2174. static int __init set_hashdist(char *str)
  2175. {
  2176. if (!str)
  2177. return 0;
  2178. hashdist = simple_strtoul(str, &str, 0);
  2179. return 1;
  2180. }
  2181. __setup("hashdist=", set_hashdist);
  2182. #endif
  2183. /*
  2184. * allocate a large system hash table from bootmem
  2185. * - it is assumed that the hash table must contain an exact power-of-2
  2186. * quantity of entries
  2187. * - limit is the number of hash buckets, not the total allocation size
  2188. */
  2189. void *__init alloc_large_system_hash(const char *tablename,
  2190. unsigned long bucketsize,
  2191. unsigned long numentries,
  2192. int scale,
  2193. int flags,
  2194. unsigned int *_hash_shift,
  2195. unsigned int *_hash_mask,
  2196. unsigned long limit)
  2197. {
  2198. unsigned long long max = limit;
  2199. unsigned long log2qty, size;
  2200. void *table = NULL;
  2201. /* allow the kernel cmdline to have a say */
  2202. if (!numentries) {
  2203. /* round applicable memory size up to nearest megabyte */
  2204. numentries = (flags & HASH_HIGHMEM) ? nr_all_pages : nr_kernel_pages;
  2205. numentries += (1UL << (20 - PAGE_SHIFT)) - 1;
  2206. numentries >>= 20 - PAGE_SHIFT;
  2207. numentries <<= 20 - PAGE_SHIFT;
  2208. /* limit to 1 bucket per 2^scale bytes of low memory */
  2209. if (scale > PAGE_SHIFT)
  2210. numentries >>= (scale - PAGE_SHIFT);
  2211. else
  2212. numentries <<= (PAGE_SHIFT - scale);
  2213. }
  2214. /* rounded up to nearest power of 2 in size */
  2215. numentries = 1UL << (long_log2(numentries) + 1);
  2216. /* limit allocation size to 1/16 total memory by default */
  2217. if (max == 0) {
  2218. max = ((unsigned long long)nr_all_pages << PAGE_SHIFT) >> 4;
  2219. do_div(max, bucketsize);
  2220. }
  2221. if (numentries > max)
  2222. numentries = max;
  2223. log2qty = long_log2(numentries);
  2224. do {
  2225. size = bucketsize << log2qty;
  2226. if (flags & HASH_EARLY)
  2227. table = alloc_bootmem(size);
  2228. else if (hashdist)
  2229. table = __vmalloc(size, GFP_ATOMIC, PAGE_KERNEL);
  2230. else {
  2231. unsigned long order;
  2232. for (order = 0; ((1UL << order) << PAGE_SHIFT) < size; order++)
  2233. ;
  2234. table = (void*) __get_free_pages(GFP_ATOMIC, order);
  2235. }
  2236. } while (!table && size > PAGE_SIZE && --log2qty);
  2237. if (!table)
  2238. panic("Failed to allocate %s hash table\n", tablename);
  2239. printk("%s hash table entries: %d (order: %d, %lu bytes)\n",
  2240. tablename,
  2241. (1U << log2qty),
  2242. long_log2(size) - PAGE_SHIFT,
  2243. size);
  2244. if (_hash_shift)
  2245. *_hash_shift = log2qty;
  2246. if (_hash_mask)
  2247. *_hash_mask = (1 << log2qty) - 1;
  2248. return table;
  2249. }