Merge branch 'x86-bsp-hotplug-for-linus' of git://git.kernel.org/pub/scm/linux/kernel...
[linux-3.10.git] / mm / page_alloc.c
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
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/jiffies.h>
23 #include <linux/bootmem.h>
24 #include <linux/memblock.h>
25 #include <linux/compiler.h>
26 #include <linux/kernel.h>
27 #include <linux/kmemcheck.h>
28 #include <linux/module.h>
29 #include <linux/suspend.h>
30 #include <linux/pagevec.h>
31 #include <linux/blkdev.h>
32 #include <linux/slab.h>
33 #include <linux/ratelimit.h>
34 #include <linux/oom.h>
35 #include <linux/notifier.h>
36 #include <linux/topology.h>
37 #include <linux/sysctl.h>
38 #include <linux/cpu.h>
39 #include <linux/cpuset.h>
40 #include <linux/memory_hotplug.h>
41 #include <linux/nodemask.h>
42 #include <linux/vmalloc.h>
43 #include <linux/vmstat.h>
44 #include <linux/mempolicy.h>
45 #include <linux/stop_machine.h>
46 #include <linux/sort.h>
47 #include <linux/pfn.h>
48 #include <linux/backing-dev.h>
49 #include <linux/fault-inject.h>
50 #include <linux/page-isolation.h>
51 #include <linux/page_cgroup.h>
52 #include <linux/debugobjects.h>
53 #include <linux/kmemleak.h>
54 #include <linux/compaction.h>
55 #include <trace/events/kmem.h>
56 #include <linux/ftrace_event.h>
57 #include <linux/memcontrol.h>
58 #include <linux/prefetch.h>
59 #include <linux/migrate.h>
60 #include <linux/page-debug-flags.h>
61
62 #include <asm/tlbflush.h>
63 #include <asm/div64.h>
64 #include "internal.h"
65
66 #ifdef CONFIG_USE_PERCPU_NUMA_NODE_ID
67 DEFINE_PER_CPU(int, numa_node);
68 EXPORT_PER_CPU_SYMBOL(numa_node);
69 #endif
70
71 #ifdef CONFIG_HAVE_MEMORYLESS_NODES
72 /*
73  * N.B., Do NOT reference the '_numa_mem_' per cpu variable directly.
74  * It will not be defined when CONFIG_HAVE_MEMORYLESS_NODES is not defined.
75  * Use the accessor functions set_numa_mem(), numa_mem_id() and cpu_to_mem()
76  * defined in <linux/topology.h>.
77  */
78 DEFINE_PER_CPU(int, _numa_mem_);                /* Kernel "local memory" node */
79 EXPORT_PER_CPU_SYMBOL(_numa_mem_);
80 #endif
81
82 /*
83  * Array of node states.
84  */
85 nodemask_t node_states[NR_NODE_STATES] __read_mostly = {
86         [N_POSSIBLE] = NODE_MASK_ALL,
87         [N_ONLINE] = { { [0] = 1UL } },
88 #ifndef CONFIG_NUMA
89         [N_NORMAL_MEMORY] = { { [0] = 1UL } },
90 #ifdef CONFIG_HIGHMEM
91         [N_HIGH_MEMORY] = { { [0] = 1UL } },
92 #endif
93         [N_CPU] = { { [0] = 1UL } },
94 #endif  /* NUMA */
95 };
96 EXPORT_SYMBOL(node_states);
97
98 unsigned long totalram_pages __read_mostly;
99 unsigned long totalreserve_pages __read_mostly;
100 /*
101  * When calculating the number of globally allowed dirty pages, there
102  * is a certain number of per-zone reserves that should not be
103  * considered dirtyable memory.  This is the sum of those reserves
104  * over all existing zones that contribute dirtyable memory.
105  */
106 unsigned long dirty_balance_reserve __read_mostly;
107
108 int percpu_pagelist_fraction;
109 gfp_t gfp_allowed_mask __read_mostly = GFP_BOOT_MASK;
110
111 #ifdef CONFIG_PM_SLEEP
112 /*
113  * The following functions are used by the suspend/hibernate code to temporarily
114  * change gfp_allowed_mask in order to avoid using I/O during memory allocations
115  * while devices are suspended.  To avoid races with the suspend/hibernate code,
116  * they should always be called with pm_mutex held (gfp_allowed_mask also should
117  * only be modified with pm_mutex held, unless the suspend/hibernate code is
118  * guaranteed not to run in parallel with that modification).
119  */
120
121 static gfp_t saved_gfp_mask;
122
123 void pm_restore_gfp_mask(void)
124 {
125         WARN_ON(!mutex_is_locked(&pm_mutex));
126         if (saved_gfp_mask) {
127                 gfp_allowed_mask = saved_gfp_mask;
128                 saved_gfp_mask = 0;
129         }
130 }
131
132 void pm_restrict_gfp_mask(void)
133 {
134         WARN_ON(!mutex_is_locked(&pm_mutex));
135         WARN_ON(saved_gfp_mask);
136         saved_gfp_mask = gfp_allowed_mask;
137         gfp_allowed_mask &= ~GFP_IOFS;
138 }
139
140 bool pm_suspended_storage(void)
141 {
142         if ((gfp_allowed_mask & GFP_IOFS) == GFP_IOFS)
143                 return false;
144         return true;
145 }
146 #endif /* CONFIG_PM_SLEEP */
147
148 #ifdef CONFIG_HUGETLB_PAGE_SIZE_VARIABLE
149 int pageblock_order __read_mostly;
150 #endif
151
152 static void __free_pages_ok(struct page *page, unsigned int order);
153
154 /*
155  * results with 256, 32 in the lowmem_reserve sysctl:
156  *      1G machine -> (16M dma, 800M-16M normal, 1G-800M high)
157  *      1G machine -> (16M dma, 784M normal, 224M high)
158  *      NORMAL allocation will leave 784M/256 of ram reserved in the ZONE_DMA
159  *      HIGHMEM allocation will leave 224M/32 of ram reserved in ZONE_NORMAL
160  *      HIGHMEM allocation will (224M+784M)/256 of ram reserved in ZONE_DMA
161  *
162  * TBD: should special case ZONE_DMA32 machines here - in those we normally
163  * don't need any ZONE_NORMAL reservation
164  */
165 int sysctl_lowmem_reserve_ratio[MAX_NR_ZONES-1] = {
166 #ifdef CONFIG_ZONE_DMA
167          256,
168 #endif
169 #ifdef CONFIG_ZONE_DMA32
170          256,
171 #endif
172 #ifdef CONFIG_HIGHMEM
173          32,
174 #endif
175          32,
176 };
177
178 EXPORT_SYMBOL(totalram_pages);
179
180 static char * const zone_names[MAX_NR_ZONES] = {
181 #ifdef CONFIG_ZONE_DMA
182          "DMA",
183 #endif
184 #ifdef CONFIG_ZONE_DMA32
185          "DMA32",
186 #endif
187          "Normal",
188 #ifdef CONFIG_HIGHMEM
189          "HighMem",
190 #endif
191          "Movable",
192 };
193
194 int min_free_kbytes = 1024;
195
196 static unsigned long __meminitdata nr_kernel_pages;
197 static unsigned long __meminitdata nr_all_pages;
198 static unsigned long __meminitdata dma_reserve;
199
200 #ifdef CONFIG_HAVE_MEMBLOCK_NODE_MAP
201 static unsigned long __meminitdata arch_zone_lowest_possible_pfn[MAX_NR_ZONES];
202 static unsigned long __meminitdata arch_zone_highest_possible_pfn[MAX_NR_ZONES];
203 static unsigned long __initdata required_kernelcore;
204 static unsigned long __initdata required_movablecore;
205 static unsigned long __meminitdata zone_movable_pfn[MAX_NUMNODES];
206
207 /* movable_zone is the "real" zone pages in ZONE_MOVABLE are taken from */
208 int movable_zone;
209 EXPORT_SYMBOL(movable_zone);
210 #endif /* CONFIG_HAVE_MEMBLOCK_NODE_MAP */
211
212 #if MAX_NUMNODES > 1
213 int nr_node_ids __read_mostly = MAX_NUMNODES;
214 int nr_online_nodes __read_mostly = 1;
215 EXPORT_SYMBOL(nr_node_ids);
216 EXPORT_SYMBOL(nr_online_nodes);
217 #endif
218
219 int page_group_by_mobility_disabled __read_mostly;
220
221 /*
222  * NOTE:
223  * Don't use set_pageblock_migratetype(page, MIGRATE_ISOLATE) directly.
224  * Instead, use {un}set_pageblock_isolate.
225  */
226 void set_pageblock_migratetype(struct page *page, int migratetype)
227 {
228
229         if (unlikely(page_group_by_mobility_disabled))
230                 migratetype = MIGRATE_UNMOVABLE;
231
232         set_pageblock_flags_group(page, (unsigned long)migratetype,
233                                         PB_migrate, PB_migrate_end);
234 }
235
236 bool oom_killer_disabled __read_mostly;
237
238 #ifdef CONFIG_DEBUG_VM
239 static int page_outside_zone_boundaries(struct zone *zone, struct page *page)
240 {
241         int ret = 0;
242         unsigned seq;
243         unsigned long pfn = page_to_pfn(page);
244
245         do {
246                 seq = zone_span_seqbegin(zone);
247                 if (pfn >= zone->zone_start_pfn + zone->spanned_pages)
248                         ret = 1;
249                 else if (pfn < zone->zone_start_pfn)
250                         ret = 1;
251         } while (zone_span_seqretry(zone, seq));
252
253         return ret;
254 }
255
256 static int page_is_consistent(struct zone *zone, struct page *page)
257 {
258         if (!pfn_valid_within(page_to_pfn(page)))
259                 return 0;
260         if (zone != page_zone(page))
261                 return 0;
262
263         return 1;
264 }
265 /*
266  * Temporary debugging check for pages not lying within a given zone.
267  */
268 static int bad_range(struct zone *zone, struct page *page)
269 {
270         if (page_outside_zone_boundaries(zone, page))
271                 return 1;
272         if (!page_is_consistent(zone, page))
273                 return 1;
274
275         return 0;
276 }
277 #else
278 static inline int bad_range(struct zone *zone, struct page *page)
279 {
280         return 0;
281 }
282 #endif
283
284 static void bad_page(struct page *page)
285 {
286         static unsigned long resume;
287         static unsigned long nr_shown;
288         static unsigned long nr_unshown;
289
290         /* Don't complain about poisoned pages */
291         if (PageHWPoison(page)) {
292                 reset_page_mapcount(page); /* remove PageBuddy */
293                 return;
294         }
295
296         /*
297          * Allow a burst of 60 reports, then keep quiet for that minute;
298          * or allow a steady drip of one report per second.
299          */
300         if (nr_shown == 60) {
301                 if (time_before(jiffies, resume)) {
302                         nr_unshown++;
303                         goto out;
304                 }
305                 if (nr_unshown) {
306                         printk(KERN_ALERT
307                               "BUG: Bad page state: %lu messages suppressed\n",
308                                 nr_unshown);
309                         nr_unshown = 0;
310                 }
311                 nr_shown = 0;
312         }
313         if (nr_shown++ == 0)
314                 resume = jiffies + 60 * HZ;
315
316         printk(KERN_ALERT "BUG: Bad page state in process %s  pfn:%05lx\n",
317                 current->comm, page_to_pfn(page));
318         dump_page(page);
319
320         print_modules();
321         dump_stack();
322 out:
323         /* Leave bad fields for debug, except PageBuddy could make trouble */
324         reset_page_mapcount(page); /* remove PageBuddy */
325         add_taint(TAINT_BAD_PAGE);
326 }
327
328 /*
329  * Higher-order pages are called "compound pages".  They are structured thusly:
330  *
331  * The first PAGE_SIZE page is called the "head page".
332  *
333  * The remaining PAGE_SIZE pages are called "tail pages".
334  *
335  * All pages have PG_compound set.  All tail pages have their ->first_page
336  * pointing at the head page.
337  *
338  * The first tail page's ->lru.next holds the address of the compound page's
339  * put_page() function.  Its ->lru.prev holds the order of allocation.
340  * This usage means that zero-order pages may not be compound.
341  */
342
343 static void free_compound_page(struct page *page)
344 {
345         __free_pages_ok(page, compound_order(page));
346 }
347
348 void prep_compound_page(struct page *page, unsigned long order)
349 {
350         int i;
351         int nr_pages = 1 << order;
352
353         set_compound_page_dtor(page, free_compound_page);
354         set_compound_order(page, order);
355         __SetPageHead(page);
356         for (i = 1; i < nr_pages; i++) {
357                 struct page *p = page + i;
358                 __SetPageTail(p);
359                 set_page_count(p, 0);
360                 p->first_page = page;
361         }
362 }
363
364 /* update __split_huge_page_refcount if you change this function */
365 static int destroy_compound_page(struct page *page, unsigned long order)
366 {
367         int i;
368         int nr_pages = 1 << order;
369         int bad = 0;
370
371         if (unlikely(compound_order(page) != order) ||
372             unlikely(!PageHead(page))) {
373                 bad_page(page);
374                 bad++;
375         }
376
377         __ClearPageHead(page);
378
379         for (i = 1; i < nr_pages; i++) {
380                 struct page *p = page + i;
381
382                 if (unlikely(!PageTail(p) || (p->first_page != page))) {
383                         bad_page(page);
384                         bad++;
385                 }
386                 __ClearPageTail(p);
387         }
388
389         return bad;
390 }
391
392 static inline void prep_zero_page(struct page *page, int order, gfp_t gfp_flags)
393 {
394         int i;
395
396         /*
397          * clear_highpage() will use KM_USER0, so it's a bug to use __GFP_ZERO
398          * and __GFP_HIGHMEM from hard or soft interrupt context.
399          */
400         VM_BUG_ON((gfp_flags & __GFP_HIGHMEM) && in_interrupt());
401         for (i = 0; i < (1 << order); i++)
402                 clear_highpage(page + i);
403 }
404
405 #ifdef CONFIG_DEBUG_PAGEALLOC
406 unsigned int _debug_guardpage_minorder;
407
408 static int __init debug_guardpage_minorder_setup(char *buf)
409 {
410         unsigned long res;
411
412         if (kstrtoul(buf, 10, &res) < 0 ||  res > MAX_ORDER / 2) {
413                 printk(KERN_ERR "Bad debug_guardpage_minorder value\n");
414                 return 0;
415         }
416         _debug_guardpage_minorder = res;
417         printk(KERN_INFO "Setting debug_guardpage_minorder to %lu\n", res);
418         return 0;
419 }
420 __setup("debug_guardpage_minorder=", debug_guardpage_minorder_setup);
421
422 static inline void set_page_guard_flag(struct page *page)
423 {
424         __set_bit(PAGE_DEBUG_FLAG_GUARD, &page->debug_flags);
425 }
426
427 static inline void clear_page_guard_flag(struct page *page)
428 {
429         __clear_bit(PAGE_DEBUG_FLAG_GUARD, &page->debug_flags);
430 }
431 #else
432 static inline void set_page_guard_flag(struct page *page) { }
433 static inline void clear_page_guard_flag(struct page *page) { }
434 #endif
435
436 static inline void set_page_order(struct page *page, int order)
437 {
438         set_page_private(page, order);
439         __SetPageBuddy(page);
440 }
441
442 static inline void rmv_page_order(struct page *page)
443 {
444         __ClearPageBuddy(page);
445         set_page_private(page, 0);
446 }
447
448 /*
449  * Locate the struct page for both the matching buddy in our
450  * pair (buddy1) and the combined O(n+1) page they form (page).
451  *
452  * 1) Any buddy B1 will have an order O twin B2 which satisfies
453  * the following equation:
454  *     B2 = B1 ^ (1 << O)
455  * For example, if the starting buddy (buddy2) is #8 its order
456  * 1 buddy is #10:
457  *     B2 = 8 ^ (1 << 1) = 8 ^ 2 = 10
458  *
459  * 2) Any buddy B will have an order O+1 parent P which
460  * satisfies the following equation:
461  *     P = B & ~(1 << O)
462  *
463  * Assumption: *_mem_map is contiguous at least up to MAX_ORDER
464  */
465 static inline unsigned long
466 __find_buddy_index(unsigned long page_idx, unsigned int order)
467 {
468         return page_idx ^ (1 << order);
469 }
470
471 /*
472  * This function checks whether a page is free && is the buddy
473  * we can do coalesce a page and its buddy if
474  * (a) the buddy is not in a hole &&
475  * (b) the buddy is in the buddy system &&
476  * (c) a page and its buddy have the same order &&
477  * (d) a page and its buddy are in the same zone.
478  *
479  * For recording whether a page is in the buddy system, we set ->_mapcount -2.
480  * Setting, clearing, and testing _mapcount -2 is serialized by zone->lock.
481  *
482  * For recording page's order, we use page_private(page).
483  */
484 static inline int page_is_buddy(struct page *page, struct page *buddy,
485                                                                 int order)
486 {
487         if (!pfn_valid_within(page_to_pfn(buddy)))
488                 return 0;
489
490         if (page_zone_id(page) != page_zone_id(buddy))
491                 return 0;
492
493         if (page_is_guard(buddy) && page_order(buddy) == order) {
494                 VM_BUG_ON(page_count(buddy) != 0);
495                 return 1;
496         }
497
498         if (PageBuddy(buddy) && page_order(buddy) == order) {
499                 VM_BUG_ON(page_count(buddy) != 0);
500                 return 1;
501         }
502         return 0;
503 }
504
505 /*
506  * Freeing function for a buddy system allocator.
507  *
508  * The concept of a buddy system is to maintain direct-mapped table
509  * (containing bit values) for memory blocks of various "orders".
510  * The bottom level table contains the map for the smallest allocatable
511  * units of memory (here, pages), and each level above it describes
512  * pairs of units from the levels below, hence, "buddies".
513  * At a high level, all that happens here is marking the table entry
514  * at the bottom level available, and propagating the changes upward
515  * as necessary, plus some accounting needed to play nicely with other
516  * parts of the VM system.
517  * At each level, we keep a list of pages, which are heads of continuous
518  * free pages of length of (1 << order) and marked with _mapcount -2. Page's
519  * order is recorded in page_private(page) field.
520  * So when we are allocating or freeing one, we can derive the state of the
521  * other.  That is, if we allocate a small block, and both were
522  * free, the remainder of the region must be split into blocks.
523  * If a block is freed, and its buddy is also free, then this
524  * triggers coalescing into a block of larger size.
525  *
526  * -- wli
527  */
528
529 static inline void __free_one_page(struct page *page,
530                 struct zone *zone, unsigned int order,
531                 int migratetype)
532 {
533         unsigned long page_idx;
534         unsigned long combined_idx;
535         unsigned long uninitialized_var(buddy_idx);
536         struct page *buddy;
537
538         if (unlikely(PageCompound(page)))
539                 if (unlikely(destroy_compound_page(page, order)))
540                         return;
541
542         VM_BUG_ON(migratetype == -1);
543
544         page_idx = page_to_pfn(page) & ((1 << MAX_ORDER) - 1);
545
546         VM_BUG_ON(page_idx & ((1 << order) - 1));
547         VM_BUG_ON(bad_range(zone, page));
548
549         while (order < MAX_ORDER-1) {
550                 buddy_idx = __find_buddy_index(page_idx, order);
551                 buddy = page + (buddy_idx - page_idx);
552                 if (!page_is_buddy(page, buddy, order))
553                         break;
554                 /*
555                  * Our buddy is free or it is CONFIG_DEBUG_PAGEALLOC guard page,
556                  * merge with it and move up one order.
557                  */
558                 if (page_is_guard(buddy)) {
559                         clear_page_guard_flag(buddy);
560                         set_page_private(page, 0);
561                         __mod_zone_freepage_state(zone, 1 << order,
562                                                   migratetype);
563                 } else {
564                         list_del(&buddy->lru);
565                         zone->free_area[order].nr_free--;
566                         rmv_page_order(buddy);
567                 }
568                 combined_idx = buddy_idx & page_idx;
569                 page = page + (combined_idx - page_idx);
570                 page_idx = combined_idx;
571                 order++;
572         }
573         set_page_order(page, order);
574
575         /*
576          * If this is not the largest possible page, check if the buddy
577          * of the next-highest order is free. If it is, it's possible
578          * that pages are being freed that will coalesce soon. In case,
579          * that is happening, add the free page to the tail of the list
580          * so it's less likely to be used soon and more likely to be merged
581          * as a higher order page
582          */
583         if ((order < MAX_ORDER-2) && pfn_valid_within(page_to_pfn(buddy))) {
584                 struct page *higher_page, *higher_buddy;
585                 combined_idx = buddy_idx & page_idx;
586                 higher_page = page + (combined_idx - page_idx);
587                 buddy_idx = __find_buddy_index(combined_idx, order + 1);
588                 higher_buddy = higher_page + (buddy_idx - combined_idx);
589                 if (page_is_buddy(higher_page, higher_buddy, order + 1)) {
590                         list_add_tail(&page->lru,
591                                 &zone->free_area[order].free_list[migratetype]);
592                         goto out;
593                 }
594         }
595
596         list_add(&page->lru, &zone->free_area[order].free_list[migratetype]);
597 out:
598         zone->free_area[order].nr_free++;
599 }
600
601 static inline int free_pages_check(struct page *page)
602 {
603         if (unlikely(page_mapcount(page) |
604                 (page->mapping != NULL)  |
605                 (atomic_read(&page->_count) != 0) |
606                 (page->flags & PAGE_FLAGS_CHECK_AT_FREE) |
607                 (mem_cgroup_bad_page_check(page)))) {
608                 bad_page(page);
609                 return 1;
610         }
611         if (page->flags & PAGE_FLAGS_CHECK_AT_PREP)
612                 page->flags &= ~PAGE_FLAGS_CHECK_AT_PREP;
613         return 0;
614 }
615
616 /*
617  * Frees a number of pages from the PCP lists
618  * Assumes all pages on list are in same zone, and of same order.
619  * count is the number of pages to free.
620  *
621  * If the zone was previously in an "all pages pinned" state then look to
622  * see if this freeing clears that state.
623  *
624  * And clear the zone's pages_scanned counter, to hold off the "all pages are
625  * pinned" detection logic.
626  */
627 static void free_pcppages_bulk(struct zone *zone, int count,
628                                         struct per_cpu_pages *pcp)
629 {
630         int migratetype = 0;
631         int batch_free = 0;
632         int to_free = count;
633
634         spin_lock(&zone->lock);
635         zone->all_unreclaimable = 0;
636         zone->pages_scanned = 0;
637
638         while (to_free) {
639                 struct page *page;
640                 struct list_head *list;
641
642                 /*
643                  * Remove pages from lists in a round-robin fashion. A
644                  * batch_free count is maintained that is incremented when an
645                  * empty list is encountered.  This is so more pages are freed
646                  * off fuller lists instead of spinning excessively around empty
647                  * lists
648                  */
649                 do {
650                         batch_free++;
651                         if (++migratetype == MIGRATE_PCPTYPES)
652                                 migratetype = 0;
653                         list = &pcp->lists[migratetype];
654                 } while (list_empty(list));
655
656                 /* This is the only non-empty list. Free them all. */
657                 if (batch_free == MIGRATE_PCPTYPES)
658                         batch_free = to_free;
659
660                 do {
661                         int mt; /* migratetype of the to-be-freed page */
662
663                         page = list_entry(list->prev, struct page, lru);
664                         /* must delete as __free_one_page list manipulates */
665                         list_del(&page->lru);
666                         mt = get_freepage_migratetype(page);
667                         /* MIGRATE_MOVABLE list may include MIGRATE_RESERVEs */
668                         __free_one_page(page, zone, 0, mt);
669                         trace_mm_page_pcpu_drain(page, 0, mt);
670                         if (likely(get_pageblock_migratetype(page) != MIGRATE_ISOLATE)) {
671                                 __mod_zone_page_state(zone, NR_FREE_PAGES, 1);
672                                 if (is_migrate_cma(mt))
673                                         __mod_zone_page_state(zone, NR_FREE_CMA_PAGES, 1);
674                         }
675                 } while (--to_free && --batch_free && !list_empty(list));
676         }
677         spin_unlock(&zone->lock);
678 }
679
680 static void free_one_page(struct zone *zone, struct page *page, int order,
681                                 int migratetype)
682 {
683         spin_lock(&zone->lock);
684         zone->all_unreclaimable = 0;
685         zone->pages_scanned = 0;
686
687         __free_one_page(page, zone, order, migratetype);
688         if (unlikely(migratetype != MIGRATE_ISOLATE))
689                 __mod_zone_freepage_state(zone, 1 << order, migratetype);
690         spin_unlock(&zone->lock);
691 }
692
693 static bool free_pages_prepare(struct page *page, unsigned int order)
694 {
695         int i;
696         int bad = 0;
697
698         trace_mm_page_free(page, order);
699         kmemcheck_free_shadow(page, order);
700
701         if (PageAnon(page))
702                 page->mapping = NULL;
703         for (i = 0; i < (1 << order); i++)
704                 bad += free_pages_check(page + i);
705         if (bad)
706                 return false;
707
708         if (!PageHighMem(page)) {
709                 debug_check_no_locks_freed(page_address(page),PAGE_SIZE<<order);
710                 debug_check_no_obj_freed(page_address(page),
711                                            PAGE_SIZE << order);
712         }
713         arch_free_page(page, order);
714         kernel_map_pages(page, 1 << order, 0);
715
716         return true;
717 }
718
719 static void __free_pages_ok(struct page *page, unsigned int order)
720 {
721         unsigned long flags;
722         int migratetype;
723
724         if (!free_pages_prepare(page, order))
725                 return;
726
727         local_irq_save(flags);
728         __count_vm_events(PGFREE, 1 << order);
729         migratetype = get_pageblock_migratetype(page);
730         set_freepage_migratetype(page, migratetype);
731         free_one_page(page_zone(page), page, order, migratetype);
732         local_irq_restore(flags);
733 }
734
735 void __meminit __free_pages_bootmem(struct page *page, unsigned int order)
736 {
737         unsigned int nr_pages = 1 << order;
738         unsigned int loop;
739
740         prefetchw(page);
741         for (loop = 0; loop < nr_pages; loop++) {
742                 struct page *p = &page[loop];
743
744                 if (loop + 1 < nr_pages)
745                         prefetchw(p + 1);
746                 __ClearPageReserved(p);
747                 set_page_count(p, 0);
748         }
749
750         set_page_refcounted(page);
751         __free_pages(page, order);
752 }
753
754 #ifdef CONFIG_CMA
755 /* Free whole pageblock and set it's migration type to MIGRATE_CMA. */
756 void __init init_cma_reserved_pageblock(struct page *page)
757 {
758         unsigned i = pageblock_nr_pages;
759         struct page *p = page;
760
761         do {
762                 __ClearPageReserved(p);
763                 set_page_count(p, 0);
764         } while (++p, --i);
765
766         set_page_refcounted(page);
767         set_pageblock_migratetype(page, MIGRATE_CMA);
768         __free_pages(page, pageblock_order);
769         totalram_pages += pageblock_nr_pages;
770 }
771 #endif
772
773 /*
774  * The order of subdivision here is critical for the IO subsystem.
775  * Please do not alter this order without good reasons and regression
776  * testing. Specifically, as large blocks of memory are subdivided,
777  * the order in which smaller blocks are delivered depends on the order
778  * they're subdivided in this function. This is the primary factor
779  * influencing the order in which pages are delivered to the IO
780  * subsystem according to empirical testing, and this is also justified
781  * by considering the behavior of a buddy system containing a single
782  * large block of memory acted on by a series of small allocations.
783  * This behavior is a critical factor in sglist merging's success.
784  *
785  * -- wli
786  */
787 static inline void expand(struct zone *zone, struct page *page,
788         int low, int high, struct free_area *area,
789         int migratetype)
790 {
791         unsigned long size = 1 << high;
792
793         while (high > low) {
794                 area--;
795                 high--;
796                 size >>= 1;
797                 VM_BUG_ON(bad_range(zone, &page[size]));
798
799 #ifdef CONFIG_DEBUG_PAGEALLOC
800                 if (high < debug_guardpage_minorder()) {
801                         /*
802                          * Mark as guard pages (or page), that will allow to
803                          * merge back to allocator when buddy will be freed.
804                          * Corresponding page table entries will not be touched,
805                          * pages will stay not present in virtual address space
806                          */
807                         INIT_LIST_HEAD(&page[size].lru);
808                         set_page_guard_flag(&page[size]);
809                         set_page_private(&page[size], high);
810                         /* Guard pages are not available for any usage */
811                         __mod_zone_freepage_state(zone, -(1 << high),
812                                                   migratetype);
813                         continue;
814                 }
815 #endif
816                 list_add(&page[size].lru, &area->free_list[migratetype]);
817                 area->nr_free++;
818                 set_page_order(&page[size], high);
819         }
820 }
821
822 /*
823  * This page is about to be returned from the page allocator
824  */
825 static inline int check_new_page(struct page *page)
826 {
827         if (unlikely(page_mapcount(page) |
828                 (page->mapping != NULL)  |
829                 (atomic_read(&page->_count) != 0)  |
830                 (page->flags & PAGE_FLAGS_CHECK_AT_PREP) |
831                 (mem_cgroup_bad_page_check(page)))) {
832                 bad_page(page);
833                 return 1;
834         }
835         return 0;
836 }
837
838 static int prep_new_page(struct page *page, int order, gfp_t gfp_flags)
839 {
840         int i;
841
842         for (i = 0; i < (1 << order); i++) {
843                 struct page *p = page + i;
844                 if (unlikely(check_new_page(p)))
845                         return 1;
846         }
847
848         set_page_private(page, 0);
849         set_page_refcounted(page);
850
851         arch_alloc_page(page, order);
852         kernel_map_pages(page, 1 << order, 1);
853
854         if (gfp_flags & __GFP_ZERO)
855                 prep_zero_page(page, order, gfp_flags);
856
857         if (order && (gfp_flags & __GFP_COMP))
858                 prep_compound_page(page, order);
859
860         return 0;
861 }
862
863 /*
864  * Go through the free lists for the given migratetype and remove
865  * the smallest available page from the freelists
866  */
867 static inline
868 struct page *__rmqueue_smallest(struct zone *zone, unsigned int order,
869                                                 int migratetype)
870 {
871         unsigned int current_order;
872         struct free_area * area;
873         struct page *page;
874
875         /* Find a page of the appropriate size in the preferred list */
876         for (current_order = order; current_order < MAX_ORDER; ++current_order) {
877                 area = &(zone->free_area[current_order]);
878                 if (list_empty(&area->free_list[migratetype]))
879                         continue;
880
881                 page = list_entry(area->free_list[migratetype].next,
882                                                         struct page, lru);
883                 list_del(&page->lru);
884                 rmv_page_order(page);
885                 area->nr_free--;
886                 expand(zone, page, order, current_order, area, migratetype);
887                 return page;
888         }
889
890         return NULL;
891 }
892
893
894 /*
895  * This array describes the order lists are fallen back to when
896  * the free lists for the desirable migrate type are depleted
897  */
898 static int fallbacks[MIGRATE_TYPES][4] = {
899         [MIGRATE_UNMOVABLE]   = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE,     MIGRATE_RESERVE },
900         [MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE,   MIGRATE_MOVABLE,     MIGRATE_RESERVE },
901 #ifdef CONFIG_CMA
902         [MIGRATE_MOVABLE]     = { MIGRATE_CMA,         MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_RESERVE },
903         [MIGRATE_CMA]         = { MIGRATE_RESERVE }, /* Never used */
904 #else
905         [MIGRATE_MOVABLE]     = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE,   MIGRATE_RESERVE },
906 #endif
907         [MIGRATE_RESERVE]     = { MIGRATE_RESERVE }, /* Never used */
908         [MIGRATE_ISOLATE]     = { MIGRATE_RESERVE }, /* Never used */
909 };
910
911 /*
912  * Move the free pages in a range to the free lists of the requested type.
913  * Note that start_page and end_pages are not aligned on a pageblock
914  * boundary. If alignment is required, use move_freepages_block()
915  */
916 int move_freepages(struct zone *zone,
917                           struct page *start_page, struct page *end_page,
918                           int migratetype)
919 {
920         struct page *page;
921         unsigned long order;
922         int pages_moved = 0;
923
924 #ifndef CONFIG_HOLES_IN_ZONE
925         /*
926          * page_zone is not safe to call in this context when
927          * CONFIG_HOLES_IN_ZONE is set. This bug check is probably redundant
928          * anyway as we check zone boundaries in move_freepages_block().
929          * Remove at a later date when no bug reports exist related to
930          * grouping pages by mobility
931          */
932         BUG_ON(page_zone(start_page) != page_zone(end_page));
933 #endif
934
935         for (page = start_page; page <= end_page;) {
936                 /* Make sure we are not inadvertently changing nodes */
937                 VM_BUG_ON(page_to_nid(page) != zone_to_nid(zone));
938
939                 if (!pfn_valid_within(page_to_pfn(page))) {
940                         page++;
941                         continue;
942                 }
943
944                 if (!PageBuddy(page)) {
945                         page++;
946                         continue;
947                 }
948
949                 order = page_order(page);
950                 list_move(&page->lru,
951                           &zone->free_area[order].free_list[migratetype]);
952                 set_freepage_migratetype(page, migratetype);
953                 page += 1 << order;
954                 pages_moved += 1 << order;
955         }
956
957         return pages_moved;
958 }
959
960 int move_freepages_block(struct zone *zone, struct page *page,
961                                 int migratetype)
962 {
963         unsigned long start_pfn, end_pfn;
964         struct page *start_page, *end_page;
965
966         start_pfn = page_to_pfn(page);
967         start_pfn = start_pfn & ~(pageblock_nr_pages-1);
968         start_page = pfn_to_page(start_pfn);
969         end_page = start_page + pageblock_nr_pages - 1;
970         end_pfn = start_pfn + pageblock_nr_pages - 1;
971
972         /* Do not cross zone boundaries */
973         if (start_pfn < zone->zone_start_pfn)
974                 start_page = page;
975         if (end_pfn >= zone->zone_start_pfn + zone->spanned_pages)
976                 return 0;
977
978         return move_freepages(zone, start_page, end_page, migratetype);
979 }
980
981 static void change_pageblock_range(struct page *pageblock_page,
982                                         int start_order, int migratetype)
983 {
984         int nr_pageblocks = 1 << (start_order - pageblock_order);
985
986         while (nr_pageblocks--) {
987                 set_pageblock_migratetype(pageblock_page, migratetype);
988                 pageblock_page += pageblock_nr_pages;
989         }
990 }
991
992 /* Remove an element from the buddy allocator from the fallback list */
993 static inline struct page *
994 __rmqueue_fallback(struct zone *zone, int order, int start_migratetype)
995 {
996         struct free_area * area;
997         int current_order;
998         struct page *page;
999         int migratetype, i;
1000
1001         /* Find the largest possible block of pages in the other list */
1002         for (current_order = MAX_ORDER-1; current_order >= order;
1003                                                 --current_order) {
1004                 for (i = 0;; i++) {
1005                         migratetype = fallbacks[start_migratetype][i];
1006
1007                         /* MIGRATE_RESERVE handled later if necessary */
1008                         if (migratetype == MIGRATE_RESERVE)
1009                                 break;
1010
1011                         area = &(zone->free_area[current_order]);
1012                         if (list_empty(&area->free_list[migratetype]))
1013                                 continue;
1014
1015                         page = list_entry(area->free_list[migratetype].next,
1016                                         struct page, lru);
1017                         area->nr_free--;
1018
1019                         /*
1020                          * If breaking a large block of pages, move all free
1021                          * pages to the preferred allocation list. If falling
1022                          * back for a reclaimable kernel allocation, be more
1023                          * aggressive about taking ownership of free pages
1024                          *
1025                          * On the other hand, never change migration
1026                          * type of MIGRATE_CMA pageblocks nor move CMA
1027                          * pages on different free lists. We don't
1028                          * want unmovable pages to be allocated from
1029                          * MIGRATE_CMA areas.
1030                          */
1031                         if (!is_migrate_cma(migratetype) &&
1032                             (unlikely(current_order >= pageblock_order / 2) ||
1033                              start_migratetype == MIGRATE_RECLAIMABLE ||
1034                              page_group_by_mobility_disabled)) {
1035                                 int pages;
1036                                 pages = move_freepages_block(zone, page,
1037                                                                 start_migratetype);
1038
1039                                 /* Claim the whole block if over half of it is free */
1040                                 if (pages >= (1 << (pageblock_order-1)) ||
1041                                                 page_group_by_mobility_disabled)
1042                                         set_pageblock_migratetype(page,
1043                                                                 start_migratetype);
1044
1045                                 migratetype = start_migratetype;
1046                         }
1047
1048                         /* Remove the page from the freelists */
1049                         list_del(&page->lru);
1050                         rmv_page_order(page);
1051
1052                         /* Take ownership for orders >= pageblock_order */
1053                         if (current_order >= pageblock_order &&
1054                             !is_migrate_cma(migratetype))
1055                                 change_pageblock_range(page, current_order,
1056                                                         start_migratetype);
1057
1058                         expand(zone, page, order, current_order, area,
1059                                is_migrate_cma(migratetype)
1060                              ? migratetype : start_migratetype);
1061
1062                         trace_mm_page_alloc_extfrag(page, order, current_order,
1063                                 start_migratetype, migratetype);
1064
1065                         return page;
1066                 }
1067         }
1068
1069         return NULL;
1070 }
1071
1072 /*
1073  * Do the hard work of removing an element from the buddy allocator.
1074  * Call me with the zone->lock already held.
1075  */
1076 static struct page *__rmqueue(struct zone *zone, unsigned int order,
1077                                                 int migratetype)
1078 {
1079         struct page *page;
1080
1081 retry_reserve:
1082         page = __rmqueue_smallest(zone, order, migratetype);
1083
1084         if (unlikely(!page) && migratetype != MIGRATE_RESERVE) {
1085                 page = __rmqueue_fallback(zone, order, migratetype);
1086
1087                 /*
1088                  * Use MIGRATE_RESERVE rather than fail an allocation. goto
1089                  * is used because __rmqueue_smallest is an inline function
1090                  * and we want just one call site
1091                  */
1092                 if (!page) {
1093                         migratetype = MIGRATE_RESERVE;
1094                         goto retry_reserve;
1095                 }
1096         }
1097
1098         trace_mm_page_alloc_zone_locked(page, order, migratetype);
1099         return page;
1100 }
1101
1102 /*
1103  * Obtain a specified number of elements from the buddy allocator, all under
1104  * a single hold of the lock, for efficiency.  Add them to the supplied list.
1105  * Returns the number of new pages which were placed at *list.
1106  */
1107 static int rmqueue_bulk(struct zone *zone, unsigned int order,
1108                         unsigned long count, struct list_head *list,
1109                         int migratetype, int cold)
1110 {
1111         int mt = migratetype, i;
1112
1113         spin_lock(&zone->lock);
1114         for (i = 0; i < count; ++i) {
1115                 struct page *page = __rmqueue(zone, order, migratetype);
1116                 if (unlikely(page == NULL))
1117                         break;
1118
1119                 /*
1120                  * Split buddy pages returned by expand() are received here
1121                  * in physical page order. The page is added to the callers and
1122                  * list and the list head then moves forward. From the callers
1123                  * perspective, the linked list is ordered by page number in
1124                  * some conditions. This is useful for IO devices that can
1125                  * merge IO requests if the physical pages are ordered
1126                  * properly.
1127                  */
1128                 if (likely(cold == 0))
1129                         list_add(&page->lru, list);
1130                 else
1131                         list_add_tail(&page->lru, list);
1132                 if (IS_ENABLED(CONFIG_CMA)) {
1133                         mt = get_pageblock_migratetype(page);
1134                         if (!is_migrate_cma(mt) && mt != MIGRATE_ISOLATE)
1135                                 mt = migratetype;
1136                 }
1137                 set_freepage_migratetype(page, mt);
1138                 list = &page->lru;
1139                 if (is_migrate_cma(mt))
1140                         __mod_zone_page_state(zone, NR_FREE_CMA_PAGES,
1141                                               -(1 << order));
1142         }
1143         __mod_zone_page_state(zone, NR_FREE_PAGES, -(i << order));
1144         spin_unlock(&zone->lock);
1145         return i;
1146 }
1147
1148 #ifdef CONFIG_NUMA
1149 /*
1150  * Called from the vmstat counter updater to drain pagesets of this
1151  * currently executing processor on remote nodes after they have
1152  * expired.
1153  *
1154  * Note that this function must be called with the thread pinned to
1155  * a single processor.
1156  */
1157 void drain_zone_pages(struct zone *zone, struct per_cpu_pages *pcp)
1158 {
1159         unsigned long flags;
1160         int to_drain;
1161
1162         local_irq_save(flags);
1163         if (pcp->count >= pcp->batch)
1164                 to_drain = pcp->batch;
1165         else
1166                 to_drain = pcp->count;
1167         if (to_drain > 0) {
1168                 free_pcppages_bulk(zone, to_drain, pcp);
1169                 pcp->count -= to_drain;
1170         }
1171         local_irq_restore(flags);
1172 }
1173 #endif
1174
1175 /*
1176  * Drain pages of the indicated processor.
1177  *
1178  * The processor must either be the current processor and the
1179  * thread pinned to the current processor or a processor that
1180  * is not online.
1181  */
1182 static void drain_pages(unsigned int cpu)
1183 {
1184         unsigned long flags;
1185         struct zone *zone;
1186
1187         for_each_populated_zone(zone) {
1188                 struct per_cpu_pageset *pset;
1189                 struct per_cpu_pages *pcp;
1190
1191                 local_irq_save(flags);
1192                 pset = per_cpu_ptr(zone->pageset, cpu);
1193
1194                 pcp = &pset->pcp;
1195                 if (pcp->count) {
1196                         free_pcppages_bulk(zone, pcp->count, pcp);
1197                         pcp->count = 0;
1198                 }
1199                 local_irq_restore(flags);
1200         }
1201 }
1202
1203 /*
1204  * Spill all of this CPU's per-cpu pages back into the buddy allocator.
1205  */
1206 void drain_local_pages(void *arg)
1207 {
1208         drain_pages(smp_processor_id());
1209 }
1210
1211 /*
1212  * Spill all the per-cpu pages from all CPUs back into the buddy allocator.
1213  *
1214  * Note that this code is protected against sending an IPI to an offline
1215  * CPU but does not guarantee sending an IPI to newly hotplugged CPUs:
1216  * on_each_cpu_mask() blocks hotplug and won't talk to offlined CPUs but
1217  * nothing keeps CPUs from showing up after we populated the cpumask and
1218  * before the call to on_each_cpu_mask().
1219  */
1220 void drain_all_pages(void)
1221 {
1222         int cpu;
1223         struct per_cpu_pageset *pcp;
1224         struct zone *zone;
1225
1226         /*
1227          * Allocate in the BSS so we wont require allocation in
1228          * direct reclaim path for CONFIG_CPUMASK_OFFSTACK=y
1229          */
1230         static cpumask_t cpus_with_pcps;
1231
1232         /*
1233          * We don't care about racing with CPU hotplug event
1234          * as offline notification will cause the notified
1235          * cpu to drain that CPU pcps and on_each_cpu_mask
1236          * disables preemption as part of its processing
1237          */
1238         for_each_online_cpu(cpu) {
1239                 bool has_pcps = false;
1240                 for_each_populated_zone(zone) {
1241                         pcp = per_cpu_ptr(zone->pageset, cpu);
1242                         if (pcp->pcp.count) {
1243                                 has_pcps = true;
1244                                 break;
1245                         }
1246                 }
1247                 if (has_pcps)
1248                         cpumask_set_cpu(cpu, &cpus_with_pcps);
1249                 else
1250                         cpumask_clear_cpu(cpu, &cpus_with_pcps);
1251         }
1252         on_each_cpu_mask(&cpus_with_pcps, drain_local_pages, NULL, 1);
1253 }
1254
1255 #ifdef CONFIG_HIBERNATION
1256
1257 void mark_free_pages(struct zone *zone)
1258 {
1259         unsigned long pfn, max_zone_pfn;
1260         unsigned long flags;
1261         int order, t;
1262         struct list_head *curr;
1263
1264         if (!zone->spanned_pages)
1265                 return;
1266
1267         spin_lock_irqsave(&zone->lock, flags);
1268
1269         max_zone_pfn = zone->zone_start_pfn + zone->spanned_pages;
1270         for (pfn = zone->zone_start_pfn; pfn < max_zone_pfn; pfn++)
1271                 if (pfn_valid(pfn)) {
1272                         struct page *page = pfn_to_page(pfn);
1273
1274                         if (!swsusp_page_is_forbidden(page))
1275                                 swsusp_unset_page_free(page);
1276                 }
1277
1278         for_each_migratetype_order(order, t) {
1279                 list_for_each(curr, &zone->free_area[order].free_list[t]) {
1280                         unsigned long i;
1281
1282                         pfn = page_to_pfn(list_entry(curr, struct page, lru));
1283                         for (i = 0; i < (1UL << order); i++)
1284                                 swsusp_set_page_free(pfn_to_page(pfn + i));
1285                 }
1286         }
1287         spin_unlock_irqrestore(&zone->lock, flags);
1288 }
1289 #endif /* CONFIG_PM */
1290
1291 /*
1292  * Free a 0-order page
1293  * cold == 1 ? free a cold page : free a hot page
1294  */
1295 void free_hot_cold_page(struct page *page, int cold)
1296 {
1297         struct zone *zone = page_zone(page);
1298         struct per_cpu_pages *pcp;
1299         unsigned long flags;
1300         int migratetype;
1301
1302         if (!free_pages_prepare(page, 0))
1303                 return;
1304
1305         migratetype = get_pageblock_migratetype(page);
1306         set_freepage_migratetype(page, migratetype);
1307         local_irq_save(flags);
1308         __count_vm_event(PGFREE);
1309
1310         /*
1311          * We only track unmovable, reclaimable and movable on pcp lists.
1312          * Free ISOLATE pages back to the allocator because they are being
1313          * offlined but treat RESERVE as movable pages so we can get those
1314          * areas back if necessary. Otherwise, we may have to free
1315          * excessively into the page allocator
1316          */
1317         if (migratetype >= MIGRATE_PCPTYPES) {
1318                 if (unlikely(migratetype == MIGRATE_ISOLATE)) {
1319                         free_one_page(zone, page, 0, migratetype);
1320                         goto out;
1321                 }
1322                 migratetype = MIGRATE_MOVABLE;
1323         }
1324
1325         pcp = &this_cpu_ptr(zone->pageset)->pcp;
1326         if (cold)
1327                 list_add_tail(&page->lru, &pcp->lists[migratetype]);
1328         else
1329                 list_add(&page->lru, &pcp->lists[migratetype]);
1330         pcp->count++;
1331         if (pcp->count >= pcp->high) {
1332                 free_pcppages_bulk(zone, pcp->batch, pcp);
1333                 pcp->count -= pcp->batch;
1334         }
1335
1336 out:
1337         local_irq_restore(flags);
1338 }
1339
1340 /*
1341  * Free a list of 0-order pages
1342  */
1343 void free_hot_cold_page_list(struct list_head *list, int cold)
1344 {
1345         struct page *page, *next;
1346
1347         list_for_each_entry_safe(page, next, list, lru) {
1348                 trace_mm_page_free_batched(page, cold);
1349                 free_hot_cold_page(page, cold);
1350         }
1351 }
1352
1353 /*
1354  * split_page takes a non-compound higher-order page, and splits it into
1355  * n (1<<order) sub-pages: page[0..n]
1356  * Each sub-page must be freed individually.
1357  *
1358  * Note: this is probably too low level an operation for use in drivers.
1359  * Please consult with lkml before using this in your driver.
1360  */
1361 void split_page(struct page *page, unsigned int order)
1362 {
1363         int i;
1364
1365         VM_BUG_ON(PageCompound(page));
1366         VM_BUG_ON(!page_count(page));
1367
1368 #ifdef CONFIG_KMEMCHECK
1369         /*
1370          * Split shadow pages too, because free(page[0]) would
1371          * otherwise free the whole shadow.
1372          */
1373         if (kmemcheck_page_is_tracked(page))
1374                 split_page(virt_to_page(page[0].shadow), order);
1375 #endif
1376
1377         for (i = 1; i < (1 << order); i++)
1378                 set_page_refcounted(page + i);
1379 }
1380
1381 /*
1382  * Similar to the split_page family of functions except that the page
1383  * required at the given order and being isolated now to prevent races
1384  * with parallel allocators
1385  */
1386 int capture_free_page(struct page *page, int alloc_order, int migratetype)
1387 {
1388         unsigned int order;
1389         unsigned long watermark;
1390         struct zone *zone;
1391         int mt;
1392
1393         BUG_ON(!PageBuddy(page));
1394
1395         zone = page_zone(page);
1396         order = page_order(page);
1397         mt = get_pageblock_migratetype(page);
1398
1399         if (mt != MIGRATE_ISOLATE) {
1400                 /* Obey watermarks as if the page was being allocated */
1401                 watermark = low_wmark_pages(zone) + (1 << order);
1402                 if (!zone_watermark_ok(zone, 0, watermark, 0, 0))
1403                         return 0;
1404
1405                 __mod_zone_freepage_state(zone, -(1UL << alloc_order), mt);
1406         }
1407
1408         /* Remove page from free list */
1409         list_del(&page->lru);
1410         zone->free_area[order].nr_free--;
1411         rmv_page_order(page);
1412
1413         if (alloc_order != order)
1414                 expand(zone, page, alloc_order, order,
1415                         &zone->free_area[order], migratetype);
1416
1417         /* Set the pageblock if the captured page is at least a pageblock */
1418         if (order >= pageblock_order - 1) {
1419                 struct page *endpage = page + (1 << order) - 1;
1420                 for (; page < endpage; page += pageblock_nr_pages) {
1421                         int mt = get_pageblock_migratetype(page);
1422                         if (mt != MIGRATE_ISOLATE && !is_migrate_cma(mt))
1423                                 set_pageblock_migratetype(page,
1424                                                           MIGRATE_MOVABLE);
1425                 }
1426         }
1427
1428         return 1UL << alloc_order;
1429 }
1430
1431 /*
1432  * Similar to split_page except the page is already free. As this is only
1433  * being used for migration, the migratetype of the block also changes.
1434  * As this is called with interrupts disabled, the caller is responsible
1435  * for calling arch_alloc_page() and kernel_map_page() after interrupts
1436  * are enabled.
1437  *
1438  * Note: this is probably too low level an operation for use in drivers.
1439  * Please consult with lkml before using this in your driver.
1440  */
1441 int split_free_page(struct page *page)
1442 {
1443         unsigned int order;
1444         int nr_pages;
1445
1446         BUG_ON(!PageBuddy(page));
1447         order = page_order(page);
1448
1449         nr_pages = capture_free_page(page, order, 0);
1450         if (!nr_pages)
1451                 return 0;
1452
1453         /* Split into individual pages */
1454         set_page_refcounted(page);
1455         split_page(page, order);
1456         return nr_pages;
1457 }
1458
1459 /*
1460  * Really, prep_compound_page() should be called from __rmqueue_bulk().  But
1461  * we cheat by calling it from here, in the order > 0 path.  Saves a branch
1462  * or two.
1463  */
1464 static inline
1465 struct page *buffered_rmqueue(struct zone *preferred_zone,
1466                         struct zone *zone, int order, gfp_t gfp_flags,
1467                         int migratetype)
1468 {
1469         unsigned long flags;
1470         struct page *page;
1471         int cold = !!(gfp_flags & __GFP_COLD);
1472
1473 again:
1474         if (likely(order == 0)) {
1475                 struct per_cpu_pages *pcp;
1476                 struct list_head *list;
1477
1478                 local_irq_save(flags);
1479                 pcp = &this_cpu_ptr(zone->pageset)->pcp;
1480                 list = &pcp->lists[migratetype];
1481                 if (list_empty(list)) {
1482                         pcp->count += rmqueue_bulk(zone, 0,
1483                                         pcp->batch, list,
1484                                         migratetype, cold);
1485                         if (unlikely(list_empty(list)))
1486                                 goto failed;
1487                 }
1488
1489                 if (cold)
1490                         page = list_entry(list->prev, struct page, lru);
1491                 else
1492                         page = list_entry(list->next, struct page, lru);
1493
1494                 list_del(&page->lru);
1495                 pcp->count--;
1496         } else {
1497                 if (unlikely(gfp_flags & __GFP_NOFAIL)) {
1498                         /*
1499                          * __GFP_NOFAIL is not to be used in new code.
1500                          *
1501                          * All __GFP_NOFAIL callers should be fixed so that they
1502                          * properly detect and handle allocation failures.
1503                          *
1504                          * We most definitely don't want callers attempting to
1505                          * allocate greater than order-1 page units with
1506                          * __GFP_NOFAIL.
1507                          */
1508                         WARN_ON_ONCE(order > 1);
1509                 }
1510                 spin_lock_irqsave(&zone->lock, flags);
1511                 page = __rmqueue(zone, order, migratetype);
1512                 spin_unlock(&zone->lock);
1513                 if (!page)
1514                         goto failed;
1515                 __mod_zone_freepage_state(zone, -(1 << order),
1516                                           get_pageblock_migratetype(page));
1517         }
1518
1519         __count_zone_vm_events(PGALLOC, zone, 1 << order);
1520         zone_statistics(preferred_zone, zone, gfp_flags);
1521         local_irq_restore(flags);
1522
1523         VM_BUG_ON(bad_range(zone, page));
1524         if (prep_new_page(page, order, gfp_flags))
1525                 goto again;
1526         return page;
1527
1528 failed:
1529         local_irq_restore(flags);
1530         return NULL;
1531 }
1532
1533 #ifdef CONFIG_FAIL_PAGE_ALLOC
1534
1535 static struct {
1536         struct fault_attr attr;
1537
1538         u32 ignore_gfp_highmem;
1539         u32 ignore_gfp_wait;
1540         u32 min_order;
1541 } fail_page_alloc = {
1542         .attr = FAULT_ATTR_INITIALIZER,
1543         .ignore_gfp_wait = 1,
1544         .ignore_gfp_highmem = 1,
1545         .min_order = 1,
1546 };
1547
1548 static int __init setup_fail_page_alloc(char *str)
1549 {
1550         return setup_fault_attr(&fail_page_alloc.attr, str);
1551 }
1552 __setup("fail_page_alloc=", setup_fail_page_alloc);
1553
1554 static bool should_fail_alloc_page(gfp_t gfp_mask, unsigned int order)
1555 {
1556         if (order < fail_page_alloc.min_order)
1557                 return false;
1558         if (gfp_mask & __GFP_NOFAIL)
1559                 return false;
1560         if (fail_page_alloc.ignore_gfp_highmem && (gfp_mask & __GFP_HIGHMEM))
1561                 return false;
1562         if (fail_page_alloc.ignore_gfp_wait && (gfp_mask & __GFP_WAIT))
1563                 return false;
1564
1565         return should_fail(&fail_page_alloc.attr, 1 << order);
1566 }
1567
1568 #ifdef CONFIG_FAULT_INJECTION_DEBUG_FS
1569
1570 static int __init fail_page_alloc_debugfs(void)
1571 {
1572         umode_t mode = S_IFREG | S_IRUSR | S_IWUSR;
1573         struct dentry *dir;
1574
1575         dir = fault_create_debugfs_attr("fail_page_alloc", NULL,
1576                                         &fail_page_alloc.attr);
1577         if (IS_ERR(dir))
1578                 return PTR_ERR(dir);
1579
1580         if (!debugfs_create_bool("ignore-gfp-wait", mode, dir,
1581                                 &fail_page_alloc.ignore_gfp_wait))
1582                 goto fail;
1583         if (!debugfs_create_bool("ignore-gfp-highmem", mode, dir,
1584                                 &fail_page_alloc.ignore_gfp_highmem))
1585                 goto fail;
1586         if (!debugfs_create_u32("min-order", mode, dir,
1587                                 &fail_page_alloc.min_order))
1588                 goto fail;
1589
1590         return 0;
1591 fail:
1592         debugfs_remove_recursive(dir);
1593
1594         return -ENOMEM;
1595 }
1596
1597 late_initcall(fail_page_alloc_debugfs);
1598
1599 #endif /* CONFIG_FAULT_INJECTION_DEBUG_FS */
1600
1601 #else /* CONFIG_FAIL_PAGE_ALLOC */
1602
1603 static inline bool should_fail_alloc_page(gfp_t gfp_mask, unsigned int order)
1604 {
1605         return false;
1606 }
1607
1608 #endif /* CONFIG_FAIL_PAGE_ALLOC */
1609
1610 /*
1611  * Return true if free pages are above 'mark'. This takes into account the order
1612  * of the allocation.
1613  */
1614 static bool __zone_watermark_ok(struct zone *z, int order, unsigned long mark,
1615                       int classzone_idx, int alloc_flags, long free_pages)
1616 {
1617         /* free_pages my go negative - that's OK */
1618         long min = mark;
1619         long lowmem_reserve = z->lowmem_reserve[classzone_idx];
1620         int o;
1621
1622         free_pages -= (1 << order) - 1;
1623         if (alloc_flags & ALLOC_HIGH)
1624                 min -= min / 2;
1625         if (alloc_flags & ALLOC_HARDER)
1626                 min -= min / 4;
1627 #ifdef CONFIG_CMA
1628         /* If allocation can't use CMA areas don't use free CMA pages */
1629         if (!(alloc_flags & ALLOC_CMA))
1630                 free_pages -= zone_page_state(z, NR_FREE_CMA_PAGES);
1631 #endif
1632         if (free_pages <= min + lowmem_reserve)
1633                 return false;
1634         for (o = 0; o < order; o++) {
1635                 /* At the next order, this order's pages become unavailable */
1636                 free_pages -= z->free_area[o].nr_free << o;
1637
1638                 /* Require fewer higher order pages to be free */
1639                 min >>= 1;
1640
1641                 if (free_pages <= min)
1642                         return false;
1643         }
1644         return true;
1645 }
1646
1647 #ifdef CONFIG_MEMORY_ISOLATION
1648 static inline unsigned long nr_zone_isolate_freepages(struct zone *zone)
1649 {
1650         if (unlikely(zone->nr_pageblock_isolate))
1651                 return zone->nr_pageblock_isolate * pageblock_nr_pages;
1652         return 0;
1653 }
1654 #else
1655 static inline unsigned long nr_zone_isolate_freepages(struct zone *zone)
1656 {
1657         return 0;
1658 }
1659 #endif
1660
1661 bool zone_watermark_ok(struct zone *z, int order, unsigned long mark,
1662                       int classzone_idx, int alloc_flags)
1663 {
1664         return __zone_watermark_ok(z, order, mark, classzone_idx, alloc_flags,
1665                                         zone_page_state(z, NR_FREE_PAGES));
1666 }
1667
1668 bool zone_watermark_ok_safe(struct zone *z, int order, unsigned long mark,
1669                       int classzone_idx, int alloc_flags)
1670 {
1671         long free_pages = zone_page_state(z, NR_FREE_PAGES);
1672
1673         if (z->percpu_drift_mark && free_pages < z->percpu_drift_mark)
1674                 free_pages = zone_page_state_snapshot(z, NR_FREE_PAGES);
1675
1676         /*
1677          * If the zone has MIGRATE_ISOLATE type free pages, we should consider
1678          * it.  nr_zone_isolate_freepages is never accurate so kswapd might not
1679          * sleep although it could do so.  But this is more desirable for memory
1680          * hotplug than sleeping which can cause a livelock in the direct
1681          * reclaim path.
1682          */
1683         free_pages -= nr_zone_isolate_freepages(z);
1684         return __zone_watermark_ok(z, order, mark, classzone_idx, alloc_flags,
1685                                                                 free_pages);
1686 }
1687
1688 #ifdef CONFIG_NUMA
1689 /*
1690  * zlc_setup - Setup for "zonelist cache".  Uses cached zone data to
1691  * skip over zones that are not allowed by the cpuset, or that have
1692  * been recently (in last second) found to be nearly full.  See further
1693  * comments in mmzone.h.  Reduces cache footprint of zonelist scans
1694  * that have to skip over a lot of full or unallowed zones.
1695  *
1696  * If the zonelist cache is present in the passed in zonelist, then
1697  * returns a pointer to the allowed node mask (either the current
1698  * tasks mems_allowed, or node_states[N_HIGH_MEMORY].)
1699  *
1700  * If the zonelist cache is not available for this zonelist, does
1701  * nothing and returns NULL.
1702  *
1703  * If the fullzones BITMAP in the zonelist cache is stale (more than
1704  * a second since last zap'd) then we zap it out (clear its bits.)
1705  *
1706  * We hold off even calling zlc_setup, until after we've checked the
1707  * first zone in the zonelist, on the theory that most allocations will
1708  * be satisfied from that first zone, so best to examine that zone as
1709  * quickly as we can.
1710  */
1711 static nodemask_t *zlc_setup(struct zonelist *zonelist, int alloc_flags)
1712 {
1713         struct zonelist_cache *zlc;     /* cached zonelist speedup info */
1714         nodemask_t *allowednodes;       /* zonelist_cache approximation */
1715
1716         zlc = zonelist->zlcache_ptr;
1717         if (!zlc)
1718                 return NULL;
1719
1720         if (time_after(jiffies, zlc->last_full_zap + HZ)) {
1721                 bitmap_zero(zlc->fullzones, MAX_ZONES_PER_ZONELIST);
1722                 zlc->last_full_zap = jiffies;
1723         }
1724
1725         allowednodes = !in_interrupt() && (alloc_flags & ALLOC_CPUSET) ?
1726                                         &cpuset_current_mems_allowed :
1727                                         &node_states[N_HIGH_MEMORY];
1728         return allowednodes;
1729 }
1730
1731 /*
1732  * Given 'z' scanning a zonelist, run a couple of quick checks to see
1733  * if it is worth looking at further for free memory:
1734  *  1) Check that the zone isn't thought to be full (doesn't have its
1735  *     bit set in the zonelist_cache fullzones BITMAP).
1736  *  2) Check that the zones node (obtained from the zonelist_cache
1737  *     z_to_n[] mapping) is allowed in the passed in allowednodes mask.
1738  * Return true (non-zero) if zone is worth looking at further, or
1739  * else return false (zero) if it is not.
1740  *
1741  * This check -ignores- the distinction between various watermarks,
1742  * such as GFP_HIGH, GFP_ATOMIC, PF_MEMALLOC, ...  If a zone is
1743  * found to be full for any variation of these watermarks, it will
1744  * be considered full for up to one second by all requests, unless
1745  * we are so low on memory on all allowed nodes that we are forced
1746  * into the second scan of the zonelist.
1747  *
1748  * In the second scan we ignore this zonelist cache and exactly
1749  * apply the watermarks to all zones, even it is slower to do so.
1750  * We are low on memory in the second scan, and should leave no stone
1751  * unturned looking for a free page.
1752  */
1753 static int zlc_zone_worth_trying(struct zonelist *zonelist, struct zoneref *z,
1754                                                 nodemask_t *allowednodes)
1755 {
1756         struct zonelist_cache *zlc;     /* cached zonelist speedup info */
1757         int i;                          /* index of *z in zonelist zones */
1758         int n;                          /* node that zone *z is on */
1759
1760         zlc = zonelist->zlcache_ptr;
1761         if (!zlc)
1762                 return 1;
1763
1764         i = z - zonelist->_zonerefs;
1765         n = zlc->z_to_n[i];
1766
1767         /* This zone is worth trying if it is allowed but not full */
1768         return node_isset(n, *allowednodes) && !test_bit(i, zlc->fullzones);
1769 }
1770
1771 /*
1772  * Given 'z' scanning a zonelist, set the corresponding bit in
1773  * zlc->fullzones, so that subsequent attempts to allocate a page
1774  * from that zone don't waste time re-examining it.
1775  */
1776 static void zlc_mark_zone_full(struct zonelist *zonelist, struct zoneref *z)
1777 {
1778         struct zonelist_cache *zlc;     /* cached zonelist speedup info */
1779         int i;                          /* index of *z in zonelist zones */
1780
1781         zlc = zonelist->zlcache_ptr;
1782         if (!zlc)
1783                 return;
1784
1785         i = z - zonelist->_zonerefs;
1786
1787         set_bit(i, zlc->fullzones);
1788 }
1789
1790 /*
1791  * clear all zones full, called after direct reclaim makes progress so that
1792  * a zone that was recently full is not skipped over for up to a second
1793  */
1794 static void zlc_clear_zones_full(struct zonelist *zonelist)
1795 {
1796         struct zonelist_cache *zlc;     /* cached zonelist speedup info */
1797
1798         zlc = zonelist->zlcache_ptr;
1799         if (!zlc)
1800                 return;
1801
1802         bitmap_zero(zlc->fullzones, MAX_ZONES_PER_ZONELIST);
1803 }
1804
1805 static bool zone_allows_reclaim(struct zone *local_zone, struct zone *zone)
1806 {
1807         return node_isset(local_zone->node, zone->zone_pgdat->reclaim_nodes);
1808 }
1809
1810 static void __paginginit init_zone_allows_reclaim(int nid)
1811 {
1812         int i;
1813
1814         for_each_online_node(i)
1815                 if (node_distance(nid, i) <= RECLAIM_DISTANCE)
1816                         node_set(i, NODE_DATA(nid)->reclaim_nodes);
1817                 else
1818                         zone_reclaim_mode = 1;
1819 }
1820
1821 #else   /* CONFIG_NUMA */
1822
1823 static nodemask_t *zlc_setup(struct zonelist *zonelist, int alloc_flags)
1824 {
1825         return NULL;
1826 }
1827
1828 static int zlc_zone_worth_trying(struct zonelist *zonelist, struct zoneref *z,
1829                                 nodemask_t *allowednodes)
1830 {
1831         return 1;
1832 }
1833
1834 static void zlc_mark_zone_full(struct zonelist *zonelist, struct zoneref *z)
1835 {
1836 }
1837
1838 static void zlc_clear_zones_full(struct zonelist *zonelist)
1839 {
1840 }
1841
1842 static bool zone_allows_reclaim(struct zone *local_zone, struct zone *zone)
1843 {
1844         return true;
1845 }
1846
1847 static inline void init_zone_allows_reclaim(int nid)
1848 {
1849 }
1850 #endif  /* CONFIG_NUMA */
1851
1852 /*
1853  * get_page_from_freelist goes through the zonelist trying to allocate
1854  * a page.
1855  */
1856 static struct page *
1857 get_page_from_freelist(gfp_t gfp_mask, nodemask_t *nodemask, unsigned int order,
1858                 struct zonelist *zonelist, int high_zoneidx, int alloc_flags,
1859                 struct zone *preferred_zone, int migratetype)
1860 {
1861         struct zoneref *z;
1862         struct page *page = NULL;
1863         int classzone_idx;
1864         struct zone *zone;
1865         nodemask_t *allowednodes = NULL;/* zonelist_cache approximation */
1866         int zlc_active = 0;             /* set if using zonelist_cache */
1867         int did_zlc_setup = 0;          /* just call zlc_setup() one time */
1868
1869         classzone_idx = zone_idx(preferred_zone);
1870 zonelist_scan:
1871         /*
1872          * Scan zonelist, looking for a zone with enough free.
1873          * See also cpuset_zone_allowed() comment in kernel/cpuset.c.
1874          */
1875         for_each_zone_zonelist_nodemask(zone, z, zonelist,
1876                                                 high_zoneidx, nodemask) {
1877                 if (IS_ENABLED(CONFIG_NUMA) && zlc_active &&
1878                         !zlc_zone_worth_trying(zonelist, z, allowednodes))
1879                                 continue;
1880                 if ((alloc_flags & ALLOC_CPUSET) &&
1881                         !cpuset_zone_allowed_softwall(zone, gfp_mask))
1882                                 continue;
1883                 /*
1884                  * When allocating a page cache page for writing, we
1885                  * want to get it from a zone that is within its dirty
1886                  * limit, such that no single zone holds more than its
1887                  * proportional share of globally allowed dirty pages.
1888                  * The dirty limits take into account the zone's
1889                  * lowmem reserves and high watermark so that kswapd
1890                  * should be able to balance it without having to
1891                  * write pages from its LRU list.
1892                  *
1893                  * This may look like it could increase pressure on
1894                  * lower zones by failing allocations in higher zones
1895                  * before they are full.  But the pages that do spill
1896                  * over are limited as the lower zones are protected
1897                  * by this very same mechanism.  It should not become
1898                  * a practical burden to them.
1899                  *
1900                  * XXX: For now, allow allocations to potentially
1901                  * exceed the per-zone dirty limit in the slowpath
1902                  * (ALLOC_WMARK_LOW unset) before going into reclaim,
1903                  * which is important when on a NUMA setup the allowed
1904                  * zones are together not big enough to reach the
1905                  * global limit.  The proper fix for these situations
1906                  * will require awareness of zones in the
1907                  * dirty-throttling and the flusher threads.
1908                  */
1909                 if ((alloc_flags & ALLOC_WMARK_LOW) &&
1910                     (gfp_mask & __GFP_WRITE) && !zone_dirty_ok(zone))
1911                         goto this_zone_full;
1912
1913                 BUILD_BUG_ON(ALLOC_NO_WATERMARKS < NR_WMARK);
1914                 if (!(alloc_flags & ALLOC_NO_WATERMARKS)) {
1915                         unsigned long mark;
1916                         int ret;
1917
1918                         mark = zone->watermark[alloc_flags & ALLOC_WMARK_MASK];
1919                         if (zone_watermark_ok(zone, order, mark,
1920                                     classzone_idx, alloc_flags))
1921                                 goto try_this_zone;
1922
1923                         if (IS_ENABLED(CONFIG_NUMA) &&
1924                                         !did_zlc_setup && nr_online_nodes > 1) {
1925                                 /*
1926                                  * we do zlc_setup if there are multiple nodes
1927                                  * and before considering the first zone allowed
1928                                  * by the cpuset.
1929                                  */
1930                                 allowednodes = zlc_setup(zonelist, alloc_flags);
1931                                 zlc_active = 1;
1932                                 did_zlc_setup = 1;
1933                         }
1934
1935                         if (zone_reclaim_mode == 0 ||
1936                             !zone_allows_reclaim(preferred_zone, zone))
1937                                 goto this_zone_full;
1938
1939                         /*
1940                          * As we may have just activated ZLC, check if the first
1941                          * eligible zone has failed zone_reclaim recently.
1942                          */
1943                         if (IS_ENABLED(CONFIG_NUMA) && zlc_active &&
1944                                 !zlc_zone_worth_trying(zonelist, z, allowednodes))
1945                                 continue;
1946
1947                         ret = zone_reclaim(zone, gfp_mask, order);
1948                         switch (ret) {
1949                         case ZONE_RECLAIM_NOSCAN:
1950                                 /* did not scan */
1951                                 continue;
1952                         case ZONE_RECLAIM_FULL:
1953                                 /* scanned but unreclaimable */
1954                                 continue;
1955                         default:
1956                                 /* did we reclaim enough */
1957                                 if (!zone_watermark_ok(zone, order, mark,
1958                                                 classzone_idx, alloc_flags))
1959                                         goto this_zone_full;
1960                         }
1961                 }
1962
1963 try_this_zone:
1964                 page = buffered_rmqueue(preferred_zone, zone, order,
1965                                                 gfp_mask, migratetype);
1966                 if (page)
1967                         break;
1968 this_zone_full:
1969                 if (IS_ENABLED(CONFIG_NUMA))
1970                         zlc_mark_zone_full(zonelist, z);
1971         }
1972
1973         if (unlikely(IS_ENABLED(CONFIG_NUMA) && page == NULL && zlc_active)) {
1974                 /* Disable zlc cache for second zonelist scan */
1975                 zlc_active = 0;
1976                 goto zonelist_scan;
1977         }
1978
1979         if (page)
1980                 /*
1981                  * page->pfmemalloc is set when ALLOC_NO_WATERMARKS was
1982                  * necessary to allocate the page. The expectation is
1983                  * that the caller is taking steps that will free more
1984                  * memory. The caller should avoid the page being used
1985                  * for !PFMEMALLOC purposes.
1986                  */
1987                 page->pfmemalloc = !!(alloc_flags & ALLOC_NO_WATERMARKS);
1988
1989         return page;
1990 }
1991
1992 /*
1993  * Large machines with many possible nodes should not always dump per-node
1994  * meminfo in irq context.
1995  */
1996 static inline bool should_suppress_show_mem(void)
1997 {
1998         bool ret = false;
1999
2000 #if NODES_SHIFT > 8
2001         ret = in_interrupt();
2002 #endif
2003         return ret;
2004 }
2005
2006 static DEFINE_RATELIMIT_STATE(nopage_rs,
2007                 DEFAULT_RATELIMIT_INTERVAL,
2008                 DEFAULT_RATELIMIT_BURST);
2009
2010 void warn_alloc_failed(gfp_t gfp_mask, int order, const char *fmt, ...)
2011 {
2012         unsigned int filter = SHOW_MEM_FILTER_NODES;
2013
2014         if ((gfp_mask & __GFP_NOWARN) || !__ratelimit(&nopage_rs) ||
2015             debug_guardpage_minorder() > 0)
2016                 return;
2017
2018         /*
2019          * This documents exceptions given to allocations in certain
2020          * contexts that are allowed to allocate outside current's set
2021          * of allowed nodes.
2022          */
2023         if (!(gfp_mask & __GFP_NOMEMALLOC))
2024                 if (test_thread_flag(TIF_MEMDIE) ||
2025                     (current->flags & (PF_MEMALLOC | PF_EXITING)))
2026                         filter &= ~SHOW_MEM_FILTER_NODES;
2027         if (in_interrupt() || !(gfp_mask & __GFP_WAIT))
2028                 filter &= ~SHOW_MEM_FILTER_NODES;
2029
2030         if (fmt) {
2031                 struct va_format vaf;
2032                 va_list args;
2033
2034                 va_start(args, fmt);
2035
2036                 vaf.fmt = fmt;
2037                 vaf.va = &args;
2038
2039                 pr_warn("%pV", &vaf);
2040
2041                 va_end(args);
2042         }
2043
2044         pr_warn("%s: page allocation failure: order:%d, mode:0x%x\n",
2045                 current->comm, order, gfp_mask);
2046
2047         dump_stack();
2048         if (!should_suppress_show_mem())
2049                 show_mem(filter);
2050 }
2051
2052 static inline int
2053 should_alloc_retry(gfp_t gfp_mask, unsigned int order,
2054                                 unsigned long did_some_progress,
2055                                 unsigned long pages_reclaimed)
2056 {
2057         /* Do not loop if specifically requested */
2058         if (gfp_mask & __GFP_NORETRY)
2059                 return 0;
2060
2061         /* Always retry if specifically requested */
2062         if (gfp_mask & __GFP_NOFAIL)
2063                 return 1;
2064
2065         /*
2066          * Suspend converts GFP_KERNEL to __GFP_WAIT which can prevent reclaim
2067          * making forward progress without invoking OOM. Suspend also disables
2068          * storage devices so kswapd will not help. Bail if we are suspending.
2069          */
2070         if (!did_some_progress && pm_suspended_storage())
2071                 return 0;
2072
2073         /*
2074          * In this implementation, order <= PAGE_ALLOC_COSTLY_ORDER
2075          * means __GFP_NOFAIL, but that may not be true in other
2076          * implementations.
2077          */
2078         if (order <= PAGE_ALLOC_COSTLY_ORDER)
2079                 return 1;
2080
2081         /*
2082          * For order > PAGE_ALLOC_COSTLY_ORDER, if __GFP_REPEAT is
2083          * specified, then we retry until we no longer reclaim any pages
2084          * (above), or we've reclaimed an order of pages at least as
2085          * large as the allocation's order. In both cases, if the
2086          * allocation still fails, we stop retrying.
2087          */
2088         if (gfp_mask & __GFP_REPEAT && pages_reclaimed < (1 << order))
2089                 return 1;
2090
2091         return 0;
2092 }
2093
2094 static inline struct page *
2095 __alloc_pages_may_oom(gfp_t gfp_mask, unsigned int order,
2096         struct zonelist *zonelist, enum zone_type high_zoneidx,
2097         nodemask_t *nodemask, struct zone *preferred_zone,
2098         int migratetype)
2099 {
2100         struct page *page;
2101
2102         /* Acquire the OOM killer lock for the zones in zonelist */
2103         if (!try_set_zonelist_oom(zonelist, gfp_mask)) {
2104                 schedule_timeout_uninterruptible(1);
2105                 return NULL;
2106         }
2107
2108         /*
2109          * Go through the zonelist yet one more time, keep very high watermark
2110          * here, this is only to catch a parallel oom killing, we must fail if
2111          * we're still under heavy pressure.
2112          */
2113         page = get_page_from_freelist(gfp_mask|__GFP_HARDWALL, nodemask,
2114                 order, zonelist, high_zoneidx,
2115                 ALLOC_WMARK_HIGH|ALLOC_CPUSET,
2116                 preferred_zone, migratetype);
2117         if (page)
2118                 goto out;
2119
2120         if (!(gfp_mask & __GFP_NOFAIL)) {
2121                 /* The OOM killer will not help higher order allocs */
2122                 if (order > PAGE_ALLOC_COSTLY_ORDER)
2123                         goto out;
2124                 /* The OOM killer does not needlessly kill tasks for lowmem */
2125                 if (high_zoneidx < ZONE_NORMAL)
2126                         goto out;
2127                 /*
2128                  * GFP_THISNODE contains __GFP_NORETRY and we never hit this.
2129                  * Sanity check for bare calls of __GFP_THISNODE, not real OOM.
2130                  * The caller should handle page allocation failure by itself if
2131                  * it specifies __GFP_THISNODE.
2132                  * Note: Hugepage uses it but will hit PAGE_ALLOC_COSTLY_ORDER.
2133                  */
2134                 if (gfp_mask & __GFP_THISNODE)
2135                         goto out;
2136         }
2137         /* Exhausted what can be done so it's blamo time */
2138         out_of_memory(zonelist, gfp_mask, order, nodemask, false);
2139
2140 out:
2141         clear_zonelist_oom(zonelist, gfp_mask);
2142         return page;
2143 }
2144
2145 #ifdef CONFIG_COMPACTION
2146 /* Try memory compaction for high-order allocations before reclaim */
2147 static struct page *
2148 __alloc_pages_direct_compact(gfp_t gfp_mask, unsigned int order,
2149         struct zonelist *zonelist, enum zone_type high_zoneidx,
2150         nodemask_t *nodemask, int alloc_flags, struct zone *preferred_zone,
2151         int migratetype, bool sync_migration,
2152         bool *contended_compaction, bool *deferred_compaction,
2153         unsigned long *did_some_progress)
2154 {
2155         struct page *page = NULL;
2156
2157         if (!order)
2158                 return NULL;
2159
2160         if (compaction_deferred(preferred_zone, order)) {
2161                 *deferred_compaction = true;
2162                 return NULL;
2163         }
2164
2165         current->flags |= PF_MEMALLOC;
2166         *did_some_progress = try_to_compact_pages(zonelist, order, gfp_mask,
2167                                                 nodemask, sync_migration,
2168                                                 contended_compaction, &page);
2169         current->flags &= ~PF_MEMALLOC;
2170
2171         /* If compaction captured a page, prep and use it */
2172         if (page) {
2173                 prep_new_page(page, order, gfp_mask);
2174                 goto got_page;
2175         }
2176
2177         if (*did_some_progress != COMPACT_SKIPPED) {
2178                 /* Page migration frees to the PCP lists but we want merging */
2179                 drain_pages(get_cpu());
2180                 put_cpu();
2181
2182                 page = get_page_from_freelist(gfp_mask, nodemask,
2183                                 order, zonelist, high_zoneidx,
2184                                 alloc_flags & ~ALLOC_NO_WATERMARKS,
2185                                 preferred_zone, migratetype);
2186                 if (page) {
2187 got_page:
2188                         preferred_zone->compact_blockskip_flush = false;
2189                         preferred_zone->compact_considered = 0;
2190                         preferred_zone->compact_defer_shift = 0;
2191                         if (order >= preferred_zone->compact_order_failed)
2192                                 preferred_zone->compact_order_failed = order + 1;
2193                         count_vm_event(COMPACTSUCCESS);
2194                         return page;
2195                 }
2196
2197                 /*
2198                  * It's bad if compaction run occurs and fails.
2199                  * The most likely reason is that pages exist,
2200                  * but not enough to satisfy watermarks.
2201                  */
2202                 count_vm_event(COMPACTFAIL);
2203
2204                 /*
2205                  * As async compaction considers a subset of pageblocks, only
2206                  * defer if the failure was a sync compaction failure.
2207                  */
2208                 if (sync_migration)
2209                         defer_compaction(preferred_zone, order);
2210
2211                 cond_resched();
2212         }
2213
2214         return NULL;
2215 }
2216 #else
2217 static inline struct page *
2218 __alloc_pages_direct_compact(gfp_t gfp_mask, unsigned int order,
2219         struct zonelist *zonelist, enum zone_type high_zoneidx,
2220         nodemask_t *nodemask, int alloc_flags, struct zone *preferred_zone,
2221         int migratetype, bool sync_migration,
2222         bool *contended_compaction, bool *deferred_compaction,
2223         unsigned long *did_some_progress)
2224 {
2225         return NULL;
2226 }
2227 #endif /* CONFIG_COMPACTION */
2228
2229 /* Perform direct synchronous page reclaim */
2230 static int
2231 __perform_reclaim(gfp_t gfp_mask, unsigned int order, struct zonelist *zonelist,
2232                   nodemask_t *nodemask)
2233 {
2234         struct reclaim_state reclaim_state;
2235         int progress;
2236
2237         cond_resched();
2238
2239         /* We now go into synchronous reclaim */
2240         cpuset_memory_pressure_bump();
2241         current->flags |= PF_MEMALLOC;
2242         lockdep_set_current_reclaim_state(gfp_mask);
2243         reclaim_state.reclaimed_slab = 0;
2244         current->reclaim_state = &reclaim_state;
2245
2246         progress = try_to_free_pages(zonelist, order, gfp_mask, nodemask);
2247
2248         current->reclaim_state = NULL;
2249         lockdep_clear_current_reclaim_state();
2250         current->flags &= ~PF_MEMALLOC;
2251
2252         cond_resched();
2253
2254         return progress;
2255 }
2256
2257 /* The really slow allocator path where we enter direct reclaim */
2258 static inline struct page *
2259 __alloc_pages_direct_reclaim(gfp_t gfp_mask, unsigned int order,
2260         struct zonelist *zonelist, enum zone_type high_zoneidx,
2261         nodemask_t *nodemask, int alloc_flags, struct zone *preferred_zone,
2262         int migratetype, unsigned long *did_some_progress)
2263 {
2264         struct page *page = NULL;
2265         bool drained = false;
2266
2267         *did_some_progress = __perform_reclaim(gfp_mask, order, zonelist,
2268                                                nodemask);
2269         if (unlikely(!(*did_some_progress)))
2270                 return NULL;
2271
2272         /* After successful reclaim, reconsider all zones for allocation */
2273         if (IS_ENABLED(CONFIG_NUMA))
2274                 zlc_clear_zones_full(zonelist);
2275
2276 retry:
2277         page = get_page_from_freelist(gfp_mask, nodemask, order,
2278                                         zonelist, high_zoneidx,
2279                                         alloc_flags & ~ALLOC_NO_WATERMARKS,
2280                                         preferred_zone, migratetype);
2281
2282         /*
2283          * If an allocation failed after direct reclaim, it could be because
2284          * pages are pinned on the per-cpu lists. Drain them and try again
2285          */
2286         if (!page && !drained) {
2287                 drain_all_pages();
2288                 drained = true;
2289                 goto retry;
2290         }
2291
2292         return page;
2293 }
2294
2295 /*
2296  * This is called in the allocator slow-path if the allocation request is of
2297  * sufficient urgency to ignore watermarks and take other desperate measures
2298  */
2299 static inline struct page *
2300 __alloc_pages_high_priority(gfp_t gfp_mask, unsigned int order,
2301         struct zonelist *zonelist, enum zone_type high_zoneidx,
2302         nodemask_t *nodemask, struct zone *preferred_zone,
2303         int migratetype)
2304 {
2305         struct page *page;
2306
2307         do {
2308                 page = get_page_from_freelist(gfp_mask, nodemask, order,
2309                         zonelist, high_zoneidx, ALLOC_NO_WATERMARKS,
2310                         preferred_zone, migratetype);
2311
2312                 if (!page && gfp_mask & __GFP_NOFAIL)
2313                         wait_iff_congested(preferred_zone, BLK_RW_ASYNC, HZ/50);
2314         } while (!page && (gfp_mask & __GFP_NOFAIL));
2315
2316         return page;
2317 }
2318
2319 static inline
2320 void wake_all_kswapd(unsigned int order, struct zonelist *zonelist,
2321                                                 enum zone_type high_zoneidx,
2322                                                 enum zone_type classzone_idx)
2323 {
2324         struct zoneref *z;
2325         struct zone *zone;
2326
2327         for_each_zone_zonelist(zone, z, zonelist, high_zoneidx)
2328                 wakeup_kswapd(zone, order, classzone_idx);
2329 }
2330
2331 static inline int
2332 gfp_to_alloc_flags(gfp_t gfp_mask)
2333 {
2334         int alloc_flags = ALLOC_WMARK_MIN | ALLOC_CPUSET;
2335         const gfp_t wait = gfp_mask & __GFP_WAIT;
2336
2337         /* __GFP_HIGH is assumed to be the same as ALLOC_HIGH to save a branch. */
2338         BUILD_BUG_ON(__GFP_HIGH != (__force gfp_t) ALLOC_HIGH);
2339
2340         /*
2341          * The caller may dip into page reserves a bit more if the caller
2342          * cannot run direct reclaim, or if the caller has realtime scheduling
2343          * policy or is asking for __GFP_HIGH memory.  GFP_ATOMIC requests will
2344          * set both ALLOC_HARDER (!wait) and ALLOC_HIGH (__GFP_HIGH).
2345          */
2346         alloc_flags |= (__force int) (gfp_mask & __GFP_HIGH);
2347
2348         if (!wait) {
2349                 /*
2350                  * Not worth trying to allocate harder for
2351                  * __GFP_NOMEMALLOC even if it can't schedule.
2352                  */
2353                 if  (!(gfp_mask & __GFP_NOMEMALLOC))
2354                         alloc_flags |= ALLOC_HARDER;
2355                 /*
2356                  * Ignore cpuset if GFP_ATOMIC (!wait) rather than fail alloc.
2357                  * See also cpuset_zone_allowed() comment in kernel/cpuset.c.
2358                  */
2359                 alloc_flags &= ~ALLOC_CPUSET;
2360         } else if (unlikely(rt_task(current)) && !in_interrupt())
2361                 alloc_flags |= ALLOC_HARDER;
2362
2363         if (likely(!(gfp_mask & __GFP_NOMEMALLOC))) {
2364                 if (gfp_mask & __GFP_MEMALLOC)
2365                         alloc_flags |= ALLOC_NO_WATERMARKS;
2366                 else if (in_serving_softirq() && (current->flags & PF_MEMALLOC))
2367                         alloc_flags |= ALLOC_NO_WATERMARKS;
2368                 else if (!in_interrupt() &&
2369                                 ((current->flags & PF_MEMALLOC) ||
2370                                  unlikely(test_thread_flag(TIF_MEMDIE))))
2371                         alloc_flags |= ALLOC_NO_WATERMARKS;
2372         }
2373 #ifdef CONFIG_CMA
2374         if (allocflags_to_migratetype(gfp_mask) == MIGRATE_MOVABLE)
2375                 alloc_flags |= ALLOC_CMA;
2376 #endif
2377         return alloc_flags;
2378 }
2379
2380 bool gfp_pfmemalloc_allowed(gfp_t gfp_mask)
2381 {
2382         return !!(gfp_to_alloc_flags(gfp_mask) & ALLOC_NO_WATERMARKS);
2383 }
2384
2385 static inline struct page *
2386 __alloc_pages_slowpath(gfp_t gfp_mask, unsigned int order,
2387         struct zonelist *zonelist, enum zone_type high_zoneidx,
2388         nodemask_t *nodemask, struct zone *preferred_zone,
2389         int migratetype)
2390 {
2391         const gfp_t wait = gfp_mask & __GFP_WAIT;
2392         struct page *page = NULL;
2393         int alloc_flags;
2394         unsigned long pages_reclaimed = 0;
2395         unsigned long did_some_progress;
2396         bool sync_migration = false;
2397         bool deferred_compaction = false;
2398         bool contended_compaction = false;
2399
2400         /*
2401          * In the slowpath, we sanity check order to avoid ever trying to
2402          * reclaim >= MAX_ORDER areas which will never succeed. Callers may
2403          * be using allocators in order of preference for an area that is
2404          * too large.
2405          */
2406         if (order >= MAX_ORDER) {
2407                 WARN_ON_ONCE(!(gfp_mask & __GFP_NOWARN));
2408                 return NULL;
2409         }
2410
2411         /*
2412          * GFP_THISNODE (meaning __GFP_THISNODE, __GFP_NORETRY and
2413          * __GFP_NOWARN set) should not cause reclaim since the subsystem
2414          * (f.e. slab) using GFP_THISNODE may choose to trigger reclaim
2415          * using a larger set of nodes after it has established that the
2416          * allowed per node queues are empty and that nodes are
2417          * over allocated.
2418          */
2419         if (IS_ENABLED(CONFIG_NUMA) &&
2420                         (gfp_mask & GFP_THISNODE) == GFP_THISNODE)
2421                 goto nopage;
2422
2423 restart:
2424         if (!(gfp_mask & __GFP_NO_KSWAPD))
2425                 wake_all_kswapd(order, zonelist, high_zoneidx,
2426                                                 zone_idx(preferred_zone));
2427
2428         /*
2429          * OK, we're below the kswapd watermark and have kicked background
2430          * reclaim. Now things get more complex, so set up alloc_flags according
2431          * to how we want to proceed.
2432          */
2433         alloc_flags = gfp_to_alloc_flags(gfp_mask);
2434
2435         /*
2436          * Find the true preferred zone if the allocation is unconstrained by
2437          * cpusets.
2438          */
2439         if (!(alloc_flags & ALLOC_CPUSET) && !nodemask)
2440                 first_zones_zonelist(zonelist, high_zoneidx, NULL,
2441                                         &preferred_zone);
2442
2443 rebalance:
2444         /* This is the last chance, in general, before the goto nopage. */
2445         page = get_page_from_freelist(gfp_mask, nodemask, order, zonelist,
2446                         high_zoneidx, alloc_flags & ~ALLOC_NO_WATERMARKS,
2447                         preferred_zone, migratetype);
2448         if (page)
2449                 goto got_pg;
2450
2451         /* Allocate without watermarks if the context allows */
2452         if (alloc_flags & ALLOC_NO_WATERMARKS) {
2453                 /*
2454                  * Ignore mempolicies if ALLOC_NO_WATERMARKS on the grounds
2455                  * the allocation is high priority and these type of
2456                  * allocations are system rather than user orientated
2457                  */
2458                 zonelist = node_zonelist(numa_node_id(), gfp_mask);
2459
2460                 page = __alloc_pages_high_priority(gfp_mask, order,
2461                                 zonelist, high_zoneidx, nodemask,
2462                                 preferred_zone, migratetype);
2463                 if (page) {
2464                         goto got_pg;
2465                 }
2466         }
2467
2468         /* Atomic allocations - we can't balance anything */
2469         if (!wait)
2470                 goto nopage;
2471
2472         /* Avoid recursion of direct reclaim */
2473         if (current->flags & PF_MEMALLOC)
2474                 goto nopage;
2475
2476         /* Avoid allocations with no watermarks from looping endlessly */
2477         if (test_thread_flag(TIF_MEMDIE) && !(gfp_mask & __GFP_NOFAIL))
2478                 goto nopage;
2479
2480         /*
2481          * Try direct compaction. The first pass is asynchronous. Subsequent
2482          * attempts after direct reclaim are synchronous
2483          */
2484         page = __alloc_pages_direct_compact(gfp_mask, order,
2485                                         zonelist, high_zoneidx,
2486                                         nodemask,
2487                                         alloc_flags, preferred_zone,
2488                                         migratetype, sync_migration,
2489                                         &contended_compaction,
2490                                         &deferred_compaction,
2491                                         &did_some_progress);
2492         if (page)
2493                 goto got_pg;
2494         sync_migration = true;
2495
2496         /*
2497          * If compaction is deferred for high-order allocations, it is because
2498          * sync compaction recently failed. In this is the case and the caller
2499          * requested a movable allocation that does not heavily disrupt the
2500          * system then fail the allocation instead of entering direct reclaim.
2501          */
2502         if ((deferred_compaction || contended_compaction) &&
2503                                                 (gfp_mask & __GFP_NO_KSWAPD))
2504                 goto nopage;
2505
2506         /* Try direct reclaim and then allocating */
2507         page = __alloc_pages_direct_reclaim(gfp_mask, order,
2508                                         zonelist, high_zoneidx,
2509                                         nodemask,
2510                                         alloc_flags, preferred_zone,
2511                                         migratetype, &did_some_progress);
2512         if (page)
2513                 goto got_pg;
2514
2515         /*
2516          * If we failed to make any progress reclaiming, then we are
2517          * running out of options and have to consider going OOM
2518          */
2519         if (!did_some_progress) {
2520                 if ((gfp_mask & __GFP_FS) && !(gfp_mask & __GFP_NORETRY)) {
2521                         if (oom_killer_disabled)
2522                                 goto nopage;
2523                         /* Coredumps can quickly deplete all memory reserves */
2524                         if ((current->flags & PF_DUMPCORE) &&
2525                             !(gfp_mask & __GFP_NOFAIL))
2526                                 goto nopage;
2527                         page = __alloc_pages_may_oom(gfp_mask, order,
2528                                         zonelist, high_zoneidx,
2529                                         nodemask, preferred_zone,
2530                                         migratetype);
2531                         if (page)
2532                                 goto got_pg;
2533
2534                         if (!(gfp_mask & __GFP_NOFAIL)) {
2535                                 /*
2536                                  * The oom killer is not called for high-order
2537                                  * allocations that may fail, so if no progress
2538                                  * is being made, there are no other options and
2539                                  * retrying is unlikely to help.
2540                                  */
2541                                 if (order > PAGE_ALLOC_COSTLY_ORDER)
2542                                         goto nopage;
2543                                 /*
2544                                  * The oom killer is not called for lowmem
2545                                  * allocations to prevent needlessly killing
2546                                  * innocent tasks.
2547                                  */
2548                                 if (high_zoneidx < ZONE_NORMAL)
2549                                         goto nopage;
2550                         }
2551
2552                         goto restart;
2553                 }
2554         }
2555
2556         /* Check if we should retry the allocation */
2557         pages_reclaimed += did_some_progress;
2558         if (should_alloc_retry(gfp_mask, order, did_some_progress,
2559                                                 pages_reclaimed)) {
2560                 /* Wait for some write requests to complete then retry */
2561                 wait_iff_congested(preferred_zone, BLK_RW_ASYNC, HZ/50);
2562                 goto rebalance;
2563         } else {
2564                 /*
2565                  * High-order allocations do not necessarily loop after
2566                  * direct reclaim and reclaim/compaction depends on compaction
2567                  * being called after reclaim so call directly if necessary
2568                  */
2569                 page = __alloc_pages_direct_compact(gfp_mask, order,
2570                                         zonelist, high_zoneidx,
2571                                         nodemask,
2572                                         alloc_flags, preferred_zone,
2573                                         migratetype, sync_migration,
2574                                         &contended_compaction,
2575                                         &deferred_compaction,
2576                                         &did_some_progress);
2577                 if (page)
2578                         goto got_pg;
2579         }
2580
2581 nopage:
2582         warn_alloc_failed(gfp_mask, order, NULL);
2583         return page;
2584 got_pg:
2585         if (kmemcheck_enabled)
2586                 kmemcheck_pagealloc_alloc(page, order, gfp_mask);
2587
2588         return page;
2589 }
2590
2591 /*
2592  * This is the 'heart' of the zoned buddy allocator.
2593  */
2594 struct page *
2595 __alloc_pages_nodemask(gfp_t gfp_mask, unsigned int order,
2596                         struct zonelist *zonelist, nodemask_t *nodemask)
2597 {
2598         enum zone_type high_zoneidx = gfp_zone(gfp_mask);
2599         struct zone *preferred_zone;
2600         struct page *page = NULL;
2601         int migratetype = allocflags_to_migratetype(gfp_mask);
2602         unsigned int cpuset_mems_cookie;
2603         int alloc_flags = ALLOC_WMARK_LOW|ALLOC_CPUSET;
2604
2605         gfp_mask &= gfp_allowed_mask;
2606
2607         lockdep_trace_alloc(gfp_mask);
2608
2609         might_sleep_if(gfp_mask & __GFP_WAIT);
2610
2611         if (should_fail_alloc_page(gfp_mask, order))
2612                 return NULL;
2613
2614         /*
2615          * Check the zones suitable for the gfp_mask contain at least one
2616          * valid zone. It's possible to have an empty zonelist as a result
2617          * of GFP_THISNODE and a memoryless node
2618          */
2619         if (unlikely(!zonelist->_zonerefs->zone))
2620                 return NULL;
2621
2622 retry_cpuset:
2623         cpuset_mems_cookie = get_mems_allowed();
2624
2625         /* The preferred zone is used for statistics later */
2626         first_zones_zonelist(zonelist, high_zoneidx,
2627                                 nodemask ? : &cpuset_current_mems_allowed,
2628                                 &preferred_zone);
2629         if (!preferred_zone)
2630                 goto out;
2631
2632 #ifdef CONFIG_CMA
2633         if (allocflags_to_migratetype(gfp_mask) == MIGRATE_MOVABLE)
2634                 alloc_flags |= ALLOC_CMA;
2635 #endif
2636         /* First allocation attempt */
2637         page = get_page_from_freelist(gfp_mask|__GFP_HARDWALL, nodemask, order,
2638                         zonelist, high_zoneidx, alloc_flags,
2639                         preferred_zone, migratetype);
2640         if (unlikely(!page))
2641                 page = __alloc_pages_slowpath(gfp_mask, order,
2642                                 zonelist, high_zoneidx, nodemask,
2643                                 preferred_zone, migratetype);
2644
2645         trace_mm_page_alloc(page, order, gfp_mask, migratetype);
2646
2647 out:
2648         /*
2649          * When updating a task's mems_allowed, it is possible to race with
2650          * parallel threads in such a way that an allocation can fail while
2651          * the mask is being updated. If a page allocation is about to fail,
2652          * check if the cpuset changed during allocation and if so, retry.
2653          */
2654         if (unlikely(!put_mems_allowed(cpuset_mems_cookie) && !page))
2655                 goto retry_cpuset;
2656
2657         return page;
2658 }
2659 EXPORT_SYMBOL(__alloc_pages_nodemask);
2660
2661 /*
2662  * Common helper functions.
2663  */
2664 unsigned long __get_free_pages(gfp_t gfp_mask, unsigned int order)
2665 {
2666         struct page *page;
2667
2668         /*
2669          * __get_free_pages() returns a 32-bit address, which cannot represent
2670          * a highmem page
2671          */
2672         VM_BUG_ON((gfp_mask & __GFP_HIGHMEM) != 0);
2673
2674         page = alloc_pages(gfp_mask, order);
2675         if (!page)
2676                 return 0;
2677         return (unsigned long) page_address(page);
2678 }
2679 EXPORT_SYMBOL(__get_free_pages);
2680
2681 unsigned long get_zeroed_page(gfp_t gfp_mask)
2682 {
2683         return __get_free_pages(gfp_mask | __GFP_ZERO, 0);
2684 }
2685 EXPORT_SYMBOL(get_zeroed_page);
2686
2687 void __free_pages(struct page *page, unsigned int order)
2688 {
2689         if (put_page_testzero(page)) {
2690                 if (order == 0)
2691                         free_hot_cold_page(page, 0);
2692                 else
2693                         __free_pages_ok(page, order);
2694         }
2695 }
2696
2697 EXPORT_SYMBOL(__free_pages);
2698
2699 void free_pages(unsigned long addr, unsigned int order)
2700 {
2701         if (addr != 0) {
2702                 VM_BUG_ON(!virt_addr_valid((void *)addr));
2703                 __free_pages(virt_to_page((void *)addr), order);
2704         }
2705 }
2706
2707 EXPORT_SYMBOL(free_pages);
2708
2709 static void *make_alloc_exact(unsigned long addr, unsigned order, size_t size)
2710 {
2711         if (addr) {
2712                 unsigned long alloc_end = addr + (PAGE_SIZE << order);
2713                 unsigned long used = addr + PAGE_ALIGN(size);
2714
2715                 split_page(virt_to_page((void *)addr), order);
2716                 while (used < alloc_end) {
2717                         free_page(used);
2718                         used += PAGE_SIZE;
2719                 }
2720         }
2721         return (void *)addr;
2722 }
2723
2724 /**
2725  * alloc_pages_exact - allocate an exact number physically-contiguous pages.
2726  * @size: the number of bytes to allocate
2727  * @gfp_mask: GFP flags for the allocation
2728  *
2729  * This function is similar to alloc_pages(), except that it allocates the
2730  * minimum number of pages to satisfy the request.  alloc_pages() can only
2731  * allocate memory in power-of-two pages.
2732  *
2733  * This function is also limited by MAX_ORDER.
2734  *
2735  * Memory allocated by this function must be released by free_pages_exact().
2736  */
2737 void *alloc_pages_exact(size_t size, gfp_t gfp_mask)
2738 {
2739         unsigned int order = get_order(size);
2740         unsigned long addr;
2741
2742         addr = __get_free_pages(gfp_mask, order);
2743         return make_alloc_exact(addr, order, size);
2744 }
2745 EXPORT_SYMBOL(alloc_pages_exact);
2746
2747 /**
2748  * alloc_pages_exact_nid - allocate an exact number of physically-contiguous
2749  *                         pages on a node.
2750  * @nid: the preferred node ID where memory should be allocated
2751  * @size: the number of bytes to allocate
2752  * @gfp_mask: GFP flags for the allocation
2753  *
2754  * Like alloc_pages_exact(), but try to allocate on node nid first before falling
2755  * back.
2756  * Note this is not alloc_pages_exact_node() which allocates on a specific node,
2757  * but is not exact.
2758  */
2759 void *alloc_pages_exact_nid(int nid, size_t size, gfp_t gfp_mask)
2760 {
2761         unsigned order = get_order(size);
2762         struct page *p = alloc_pages_node(nid, gfp_mask, order);
2763         if (!p)
2764                 return NULL;
2765         return make_alloc_exact((unsigned long)page_address(p), order, size);
2766 }
2767 EXPORT_SYMBOL(alloc_pages_exact_nid);
2768
2769 /**
2770  * free_pages_exact - release memory allocated via alloc_pages_exact()
2771  * @virt: the value returned by alloc_pages_exact.
2772  * @size: size of allocation, same value as passed to alloc_pages_exact().
2773  *
2774  * Release the memory allocated by a previous call to alloc_pages_exact.
2775  */
2776 void free_pages_exact(void *virt, size_t size)
2777 {
2778         unsigned long addr = (unsigned long)virt;
2779         unsigned long end = addr + PAGE_ALIGN(size);
2780
2781         while (addr < end) {
2782                 free_page(addr);
2783                 addr += PAGE_SIZE;
2784         }
2785 }
2786 EXPORT_SYMBOL(free_pages_exact);
2787
2788 static unsigned int nr_free_zone_pages(int offset)
2789 {
2790         struct zoneref *z;
2791         struct zone *zone;
2792
2793         /* Just pick one node, since fallback list is circular */
2794         unsigned int sum = 0;
2795
2796         struct zonelist *zonelist = node_zonelist(numa_node_id(), GFP_KERNEL);
2797
2798         for_each_zone_zonelist(zone, z, zonelist, offset) {
2799                 unsigned long size = zone->present_pages;
2800                 unsigned long high = high_wmark_pages(zone);
2801                 if (size > high)
2802                         sum += size - high;
2803         }
2804
2805         return sum;
2806 }
2807
2808 /*
2809  * Amount of free RAM allocatable within ZONE_DMA and ZONE_NORMAL
2810  */
2811 unsigned int nr_free_buffer_pages(void)
2812 {
2813         return nr_free_zone_pages(gfp_zone(GFP_USER));
2814 }
2815 EXPORT_SYMBOL_GPL(nr_free_buffer_pages);
2816
2817 /*
2818  * Amount of free RAM allocatable within all zones
2819  */
2820 unsigned int nr_free_pagecache_pages(void)
2821 {
2822         return nr_free_zone_pages(gfp_zone(GFP_HIGHUSER_MOVABLE));
2823 }
2824
2825 static inline void show_node(struct zone *zone)
2826 {
2827         if (IS_ENABLED(CONFIG_NUMA))
2828                 printk("Node %d ", zone_to_nid(zone));
2829 }
2830
2831 void si_meminfo(struct sysinfo *val)
2832 {
2833         val->totalram = totalram_pages;
2834         val->sharedram = 0;
2835         val->freeram = global_page_state(NR_FREE_PAGES);
2836         val->bufferram = nr_blockdev_pages();
2837         val->totalhigh = totalhigh_pages;
2838         val->freehigh = nr_free_highpages();
2839         val->mem_unit = PAGE_SIZE;
2840 }
2841
2842 EXPORT_SYMBOL(si_meminfo);
2843
2844 #ifdef CONFIG_NUMA
2845 void si_meminfo_node(struct sysinfo *val, int nid)
2846 {
2847         pg_data_t *pgdat = NODE_DATA(nid);
2848
2849         val->totalram = pgdat->node_present_pages;
2850         val->freeram = node_page_state(nid, NR_FREE_PAGES);
2851 #ifdef CONFIG_HIGHMEM
2852         val->totalhigh = pgdat->node_zones[ZONE_HIGHMEM].present_pages;
2853         val->freehigh = zone_page_state(&pgdat->node_zones[ZONE_HIGHMEM],
2854                         NR_FREE_PAGES);
2855 #else
2856         val->totalhigh = 0;
2857         val->freehigh = 0;
2858 #endif
2859         val->mem_unit = PAGE_SIZE;
2860 }
2861 #endif
2862
2863 /*
2864  * Determine whether the node should be displayed or not, depending on whether
2865  * SHOW_MEM_FILTER_NODES was passed to show_free_areas().
2866  */
2867 bool skip_free_areas_node(unsigned int flags, int nid)
2868 {
2869         bool ret = false;
2870         unsigned int cpuset_mems_cookie;
2871
2872         if (!(flags & SHOW_MEM_FILTER_NODES))
2873                 goto out;
2874
2875         do {
2876                 cpuset_mems_cookie = get_mems_allowed();
2877                 ret = !node_isset(nid, cpuset_current_mems_allowed);
2878         } while (!put_mems_allowed(cpuset_mems_cookie));
2879 out:
2880         return ret;
2881 }
2882
2883 #define K(x) ((x) << (PAGE_SHIFT-10))
2884
2885 static void show_migration_types(unsigned char type)
2886 {
2887         static const char types[MIGRATE_TYPES] = {
2888                 [MIGRATE_UNMOVABLE]     = 'U',
2889                 [MIGRATE_RECLAIMABLE]   = 'E',
2890                 [MIGRATE_MOVABLE]       = 'M',
2891                 [MIGRATE_RESERVE]       = 'R',
2892 #ifdef CONFIG_CMA
2893                 [MIGRATE_CMA]           = 'C',
2894 #endif
2895                 [MIGRATE_ISOLATE]       = 'I',
2896         };
2897         char tmp[MIGRATE_TYPES + 1];
2898         char *p = tmp;
2899         int i;
2900
2901         for (i = 0; i < MIGRATE_TYPES; i++) {
2902                 if (type & (1 << i))
2903                         *p++ = types[i];
2904         }
2905
2906         *p = '\0';
2907         printk("(%s) ", tmp);
2908 }
2909
2910 /*
2911  * Show free area list (used inside shift_scroll-lock stuff)
2912  * We also calculate the percentage fragmentation. We do this by counting the
2913  * memory on each free list with the exception of the first item on the list.
2914  * Suppresses nodes that are not allowed by current's cpuset if
2915  * SHOW_MEM_FILTER_NODES is passed.
2916  */
2917 void show_free_areas(unsigned int filter)
2918 {
2919         int cpu;
2920         struct zone *zone;
2921
2922         for_each_populated_zone(zone) {
2923                 if (skip_free_areas_node(filter, zone_to_nid(zone)))
2924                         continue;
2925                 show_node(zone);
2926                 printk("%s per-cpu:\n", zone->name);
2927
2928                 for_each_online_cpu(cpu) {
2929                         struct per_cpu_pageset *pageset;
2930
2931                         pageset = per_cpu_ptr(zone->pageset, cpu);
2932
2933                         printk("CPU %4d: hi:%5d, btch:%4d usd:%4d\n",
2934                                cpu, pageset->pcp.high,
2935                                pageset->pcp.batch, pageset->pcp.count);
2936                 }
2937         }
2938
2939         printk("active_anon:%lu inactive_anon:%lu isolated_anon:%lu\n"
2940                 " active_file:%lu inactive_file:%lu isolated_file:%lu\n"
2941                 " unevictable:%lu"
2942                 " dirty:%lu writeback:%lu unstable:%lu\n"
2943                 " free:%lu slab_reclaimable:%lu slab_unreclaimable:%lu\n"
2944                 " mapped:%lu shmem:%lu pagetables:%lu bounce:%lu\n"
2945                 " free_cma:%lu\n",
2946                 global_page_state(NR_ACTIVE_ANON),
2947                 global_page_state(NR_INACTIVE_ANON),
2948                 global_page_state(NR_ISOLATED_ANON),
2949                 global_page_state(NR_ACTIVE_FILE),
2950                 global_page_state(NR_INACTIVE_FILE),
2951                 global_page_state(NR_ISOLATED_FILE),
2952                 global_page_state(NR_UNEVICTABLE),
2953                 global_page_state(NR_FILE_DIRTY),
2954                 global_page_state(NR_WRITEBACK),
2955                 global_page_state(NR_UNSTABLE_NFS),
2956                 global_page_state(NR_FREE_PAGES),
2957                 global_page_state(NR_SLAB_RECLAIMABLE),
2958                 global_page_state(NR_SLAB_UNRECLAIMABLE),
2959                 global_page_state(NR_FILE_MAPPED),
2960                 global_page_state(NR_SHMEM),
2961                 global_page_state(NR_PAGETABLE),
2962                 global_page_state(NR_BOUNCE),
2963                 global_page_state(NR_FREE_CMA_PAGES));
2964
2965         for_each_populated_zone(zone) {
2966                 int i;
2967
2968                 if (skip_free_areas_node(filter, zone_to_nid(zone)))
2969                         continue;
2970                 show_node(zone);
2971                 printk("%s"
2972                         " free:%lukB"
2973                         " min:%lukB"
2974                         " low:%lukB"
2975                         " high:%lukB"
2976                         " active_anon:%lukB"
2977                         " inactive_anon:%lukB"
2978                         " active_file:%lukB"
2979                         " inactive_file:%lukB"
2980                         " unevictable:%lukB"
2981                         " isolated(anon):%lukB"
2982                         " isolated(file):%lukB"
2983                         " present:%lukB"
2984                         " mlocked:%lukB"
2985                         " dirty:%lukB"
2986                         " writeback:%lukB"
2987                         " mapped:%lukB"
2988                         " shmem:%lukB"
2989                         " slab_reclaimable:%lukB"
2990                         " slab_unreclaimable:%lukB"
2991                         " kernel_stack:%lukB"
2992                         " pagetables:%lukB"
2993                         " unstable:%lukB"
2994                         " bounce:%lukB"
2995                         " free_cma:%lukB"
2996                         " writeback_tmp:%lukB"
2997                         " pages_scanned:%lu"
2998                         " all_unreclaimable? %s"
2999                         "\n",
3000                         zone->name,
3001                         K(zone_page_state(zone, NR_FREE_PAGES)),
3002                         K(min_wmark_pages(zone)),
3003                         K(low_wmark_pages(zone)),
3004                         K(high_wmark_pages(zone)),
3005                         K(zone_page_state(zone, NR_ACTIVE_ANON)),
3006                         K(zone_page_state(zone, NR_INACTIVE_ANON)),
3007                         K(zone_page_state(zone, NR_ACTIVE_FILE)),
3008                         K(zone_page_state(zone, NR_INACTIVE_FILE)),
3009                         K(zone_page_state(zone, NR_UNEVICTABLE)),
3010                         K(zone_page_state(zone, NR_ISOLATED_ANON)),
3011                         K(zone_page_state(zone, NR_ISOLATED_FILE)),
3012                         K(zone->present_pages),
3013                         K(zone_page_state(zone, NR_MLOCK)),
3014                         K(zone_page_state(zone, NR_FILE_DIRTY)),
3015                         K(zone_page_state(zone, NR_WRITEBACK)),
3016                         K(zone_page_state(zone, NR_FILE_MAPPED)),
3017                         K(zone_page_state(zone, NR_SHMEM)),
3018                         K(zone_page_state(zone, NR_SLAB_RECLAIMABLE)),
3019                         K(zone_page_state(zone, NR_SLAB_UNRECLAIMABLE)),
3020                         zone_page_state(zone, NR_KERNEL_STACK) *
3021                                 THREAD_SIZE / 1024,
3022                         K(zone_page_state(zone, NR_PAGETABLE)),
3023                         K(zone_page_state(zone, NR_UNSTABLE_NFS)),
3024                         K(zone_page_state(zone, NR_BOUNCE)),
3025                         K(zone_page_state(zone, NR_FREE_CMA_PAGES)),
3026                         K(zone_page_state(zone, NR_WRITEBACK_TEMP)),
3027                         zone->pages_scanned,
3028                         (zone->all_unreclaimable ? "yes" : "no")
3029                         );
3030                 printk("lowmem_reserve[]:");
3031                 for (i = 0; i < MAX_NR_ZONES; i++)
3032                         printk(" %lu", zone->lowmem_reserve[i]);
3033                 printk("\n");
3034         }
3035
3036         for_each_populated_zone(zone) {
3037                 unsigned long nr[MAX_ORDER], flags, order, total = 0;
3038                 unsigned char types[MAX_ORDER];
3039
3040                 if (skip_free_areas_node(filter, zone_to_nid(zone)))
3041                         continue;
3042                 show_node(zone);
3043                 printk("%s: ", zone->name);
3044
3045                 spin_lock_irqsave(&zone->lock, flags);
3046                 for (order = 0; order < MAX_ORDER; order++) {
3047                         struct free_area *area = &zone->free_area[order];
3048                         int type;
3049
3050                         nr[order] = area->nr_free;
3051                         total += nr[order] << order;
3052
3053                         types[order] = 0;
3054                         for (type = 0; type < MIGRATE_TYPES; type++) {
3055                                 if (!list_empty(&area->free_list[type]))
3056                                         types[order] |= 1 << type;
3057                         }
3058                 }
3059                 spin_unlock_irqrestore(&zone->lock, flags);
3060                 for (order = 0; order < MAX_ORDER; order++) {
3061                         printk("%lu*%lukB ", nr[order], K(1UL) << order);
3062                         if (nr[order])
3063                                 show_migration_types(types[order]);
3064                 }
3065                 printk("= %lukB\n", K(total));
3066         }
3067
3068         printk("%ld total pagecache pages\n", global_page_state(NR_FILE_PAGES));
3069
3070         show_swap_cache_info();
3071 }
3072
3073 static void zoneref_set_zone(struct zone *zone, struct zoneref *zoneref)
3074 {
3075         zoneref->zone = zone;
3076         zoneref->zone_idx = zone_idx(zone);
3077 }
3078
3079 /*
3080  * Builds allocation fallback zone lists.
3081  *
3082  * Add all populated zones of a node to the zonelist.
3083  */
3084 static int build_zonelists_node(pg_data_t *pgdat, struct zonelist *zonelist,
3085                                 int nr_zones, enum zone_type zone_type)
3086 {
3087         struct zone *zone;
3088
3089         BUG_ON(zone_type >= MAX_NR_ZONES);
3090         zone_type++;
3091
3092         do {
3093                 zone_type--;
3094                 zone = pgdat->node_zones + zone_type;
3095                 if (populated_zone(zone)) {
3096                         zoneref_set_zone(zone,
3097                                 &zonelist->_zonerefs[nr_zones++]);
3098                         check_highest_zone(zone_type);
3099                 }
3100
3101         } while (zone_type);
3102         return nr_zones;
3103 }
3104
3105
3106 /*
3107  *  zonelist_order:
3108  *  0 = automatic detection of better ordering.
3109  *  1 = order by ([node] distance, -zonetype)
3110  *  2 = order by (-zonetype, [node] distance)
3111  *
3112  *  If not NUMA, ZONELIST_ORDER_ZONE and ZONELIST_ORDER_NODE will create
3113  *  the same zonelist. So only NUMA can configure this param.
3114  */
3115 #define ZONELIST_ORDER_DEFAULT  0
3116 #define ZONELIST_ORDER_NODE     1
3117 #define ZONELIST_ORDER_ZONE     2
3118
3119 /* zonelist order in the kernel.
3120  * set_zonelist_order() will set this to NODE or ZONE.
3121  */
3122 static int current_zonelist_order = ZONELIST_ORDER_DEFAULT;
3123 static char zonelist_order_name[3][8] = {"Default", "Node", "Zone"};
3124
3125
3126 #ifdef CONFIG_NUMA
3127 /* The value user specified ....changed by config */
3128 static int user_zonelist_order = ZONELIST_ORDER_DEFAULT;
3129 /* string for sysctl */
3130 #define NUMA_ZONELIST_ORDER_LEN 16
3131 char numa_zonelist_order[16] = "default";
3132
3133 /*
3134  * interface for configure zonelist ordering.
3135  * command line option "numa_zonelist_order"
3136  *      = "[dD]efault   - default, automatic configuration.
3137  *      = "[nN]ode      - order by node locality, then by zone within node
3138  *      = "[zZ]one      - order by zone, then by locality within zone
3139  */
3140
3141 static int __parse_numa_zonelist_order(char *s)
3142 {
3143         if (*s == 'd' || *s == 'D') {
3144                 user_zonelist_order = ZONELIST_ORDER_DEFAULT;
3145         } else if (*s == 'n' || *s == 'N') {
3146                 user_zonelist_order = ZONELIST_ORDER_NODE;
3147         } else if (*s == 'z' || *s == 'Z') {
3148                 user_zonelist_order = ZONELIST_ORDER_ZONE;
3149         } else {
3150                 printk(KERN_WARNING
3151                         "Ignoring invalid numa_zonelist_order value:  "
3152                         "%s\n", s);
3153                 return -EINVAL;
3154         }
3155         return 0;
3156 }
3157
3158 static __init int setup_numa_zonelist_order(char *s)
3159 {
3160         int ret;
3161
3162         if (!s)
3163                 return 0;
3164
3165         ret = __parse_numa_zonelist_order(s);
3166         if (ret == 0)
3167                 strlcpy(numa_zonelist_order, s, NUMA_ZONELIST_ORDER_LEN);
3168
3169         return ret;
3170 }
3171 early_param("numa_zonelist_order", setup_numa_zonelist_order);
3172
3173 /*
3174  * sysctl handler for numa_zonelist_order
3175  */
3176 int numa_zonelist_order_handler(ctl_table *table, int write,
3177                 void __user *buffer, size_t *length,
3178                 loff_t *ppos)
3179 {
3180         char saved_string[NUMA_ZONELIST_ORDER_LEN];
3181         int ret;
3182         static DEFINE_MUTEX(zl_order_mutex);
3183
3184         mutex_lock(&zl_order_mutex);
3185         if (write)
3186                 strcpy(saved_string, (char*)table->data);
3187         ret = proc_dostring(table, write, buffer, length, ppos);
3188         if (ret)
3189                 goto out;
3190         if (write) {
3191                 int oldval = user_zonelist_order;
3192                 if (__parse_numa_zonelist_order((char*)table->data)) {
3193                         /*
3194                          * bogus value.  restore saved string
3195                          */
3196                         strncpy((char*)table->data, saved_string,
3197                                 NUMA_ZONELIST_ORDER_LEN);
3198                         user_zonelist_order = oldval;
3199                 } else if (oldval != user_zonelist_order) {
3200                         mutex_lock(&zonelists_mutex);
3201                         build_all_zonelists(NULL, NULL);
3202                         mutex_unlock(&zonelists_mutex);
3203                 }
3204         }
3205 out:
3206         mutex_unlock(&zl_order_mutex);
3207         return ret;
3208 }
3209
3210
3211 #define MAX_NODE_LOAD (nr_online_nodes)
3212 static int node_load[MAX_NUMNODES];
3213
3214 /**
3215  * find_next_best_node - find the next node that should appear in a given node's fallback list
3216  * @node: node whose fallback list we're appending
3217  * @used_node_mask: nodemask_t of already used nodes
3218  *
3219  * We use a number of factors to determine which is the next node that should
3220  * appear on a given node's fallback list.  The node should not have appeared
3221  * already in @node's fallback list, and it should be the next closest node
3222  * according to the distance array (which contains arbitrary distance values
3223  * from each node to each node in the system), and should also prefer nodes
3224  * with no CPUs, since presumably they'll have very little allocation pressure
3225  * on them otherwise.
3226  * It returns -1 if no node is found.
3227  */
3228 static int find_next_best_node(int node, nodemask_t *used_node_mask)
3229 {
3230         int n, val;
3231         int min_val = INT_MAX;
3232         int best_node = -1;
3233         const struct cpumask *tmp = cpumask_of_node(0);
3234
3235         /* Use the local node if we haven't already */
3236         if (!node_isset(node, *used_node_mask)) {
3237                 node_set(node, *used_node_mask);
3238                 return node;
3239         }
3240
3241         for_each_node_state(n, N_HIGH_MEMORY) {
3242
3243                 /* Don't want a node to appear more than once */
3244                 if (node_isset(n, *used_node_mask))
3245                         continue;
3246
3247                 /* Use the distance array to find the distance */
3248                 val = node_distance(node, n);
3249
3250                 /* Penalize nodes under us ("prefer the next node") */
3251                 val += (n < node);
3252
3253                 /* Give preference to headless and unused nodes */
3254                 tmp = cpumask_of_node(n);
3255                 if (!cpumask_empty(tmp))
3256                         val += PENALTY_FOR_NODE_WITH_CPUS;
3257
3258                 /* Slight preference for less loaded node */
3259                 val *= (MAX_NODE_LOAD*MAX_NUMNODES);
3260                 val += node_load[n];
3261
3262                 if (val < min_val) {
3263                         min_val = val;
3264                         best_node = n;
3265                 }
3266         }
3267
3268         if (best_node >= 0)
3269                 node_set(best_node, *used_node_mask);
3270
3271         return best_node;
3272 }
3273
3274
3275 /*
3276  * Build zonelists ordered by node and zones within node.
3277  * This results in maximum locality--normal zone overflows into local
3278  * DMA zone, if any--but risks exhausting DMA zone.
3279  */
3280 static void build_zonelists_in_node_order(pg_data_t *pgdat, int node)
3281 {
3282         int j;
3283         struct zonelist *zonelist;
3284
3285         zonelist = &pgdat->node_zonelists[0];
3286         for (j = 0; zonelist->_zonerefs[j].zone != NULL; j++)
3287                 ;
3288         j = build_zonelists_node(NODE_DATA(node), zonelist, j,
3289                                                         MAX_NR_ZONES - 1);
3290         zonelist->_zonerefs[j].zone = NULL;
3291         zonelist->_zonerefs[j].zone_idx = 0;
3292 }
3293
3294 /*
3295  * Build gfp_thisnode zonelists
3296  */
3297 static void build_thisnode_zonelists(pg_data_t *pgdat)
3298 {
3299         int j;
3300         struct zonelist *zonelist;
3301
3302         zonelist = &pgdat->node_zonelists[1];
3303         j = build_zonelists_node(pgdat, zonelist, 0, MAX_NR_ZONES - 1);
3304         zonelist->_zonerefs[j].zone = NULL;
3305         zonelist->_zonerefs[j].zone_idx = 0;
3306 }
3307
3308 /*
3309  * Build zonelists ordered by zone and nodes within zones.
3310  * This results in conserving DMA zone[s] until all Normal memory is
3311  * exhausted, but results in overflowing to remote node while memory
3312  * may still exist in local DMA zone.
3313  */
3314 static int node_order[MAX_NUMNODES];
3315
3316 static void build_zonelists_in_zone_order(pg_data_t *pgdat, int nr_nodes)
3317 {
3318         int pos, j, node;
3319         int zone_type;          /* needs to be signed */
3320         struct zone *z;
3321         struct zonelist *zonelist;
3322
3323         zonelist = &pgdat->node_zonelists[0];
3324         pos = 0;
3325         for (zone_type = MAX_NR_ZONES - 1; zone_type >= 0; zone_type--) {
3326                 for (j = 0; j < nr_nodes; j++) {
3327                         node = node_order[j];
3328                         z = &NODE_DATA(node)->node_zones[zone_type];
3329                         if (populated_zone(z)) {
3330                                 zoneref_set_zone(z,
3331                                         &zonelist->_zonerefs[pos++]);
3332                                 check_highest_zone(zone_type);
3333                         }
3334                 }
3335         }
3336         zonelist->_zonerefs[pos].zone = NULL;
3337         zonelist->_zonerefs[pos].zone_idx = 0;
3338 }
3339
3340 static int default_zonelist_order(void)
3341 {
3342         int nid, zone_type;
3343         unsigned long low_kmem_size,total_size;
3344         struct zone *z;
3345         int average_size;
3346         /*
3347          * ZONE_DMA and ZONE_DMA32 can be very small area in the system.
3348          * If they are really small and used heavily, the system can fall
3349          * into OOM very easily.
3350          * This function detect ZONE_DMA/DMA32 size and configures zone order.
3351          */
3352         /* Is there ZONE_NORMAL ? (ex. ppc has only DMA zone..) */
3353         low_kmem_size = 0;
3354         total_size = 0;
3355         for_each_online_node(nid) {
3356                 for (zone_type = 0; zone_type < MAX_NR_ZONES; zone_type++) {
3357                         z = &NODE_DATA(nid)->node_zones[zone_type];
3358                         if (populated_zone(z)) {
3359                                 if (zone_type < ZONE_NORMAL)
3360                                         low_kmem_size += z->present_pages;
3361                                 total_size += z->present_pages;
3362                         } else if (zone_type == ZONE_NORMAL) {
3363                                 /*
3364                                  * If any node has only lowmem, then node order
3365                                  * is preferred to allow kernel allocations
3366                                  * locally; otherwise, they can easily infringe
3367                                  * on other nodes when there is an abundance of
3368                                  * lowmem available to allocate from.
3369                                  */
3370                                 return ZONELIST_ORDER_NODE;
3371                         }
3372                 }
3373         }
3374         if (!low_kmem_size ||  /* there are no DMA area. */
3375             low_kmem_size > total_size/2) /* DMA/DMA32 is big. */
3376                 return ZONELIST_ORDER_NODE;
3377         /*
3378          * look into each node's config.
3379          * If there is a node whose DMA/DMA32 memory is very big area on
3380          * local memory, NODE_ORDER may be suitable.
3381          */
3382         average_size = total_size /
3383                                 (nodes_weight(node_states[N_HIGH_MEMORY]) + 1);
3384         for_each_online_node(nid) {
3385                 low_kmem_size = 0;
3386                 total_size = 0;
3387                 for (zone_type = 0; zone_type < MAX_NR_ZONES; zone_type++) {
3388                         z = &NODE_DATA(nid)->node_zones[zone_type];
3389                         if (populated_zone(z)) {
3390                                 if (zone_type < ZONE_NORMAL)
3391                                         low_kmem_size += z->present_pages;
3392                                 total_size += z->present_pages;
3393                         }
3394                 }
3395                 if (low_kmem_size &&
3396                     total_size > average_size && /* ignore small node */
3397                     low_kmem_size > total_size * 70/100)
3398                         return ZONELIST_ORDER_NODE;
3399         }
3400         return ZONELIST_ORDER_ZONE;
3401 }
3402
3403 static void set_zonelist_order(void)
3404 {
3405         if (user_zonelist_order == ZONELIST_ORDER_DEFAULT)
3406                 current_zonelist_order = default_zonelist_order();
3407         else
3408                 current_zonelist_order = user_zonelist_order;
3409 }
3410
3411 static void build_zonelists(pg_data_t *pgdat)
3412 {
3413         int j, node, load;
3414         enum zone_type i;
3415         nodemask_t used_mask;
3416         int local_node, prev_node;
3417         struct zonelist *zonelist;
3418         int order = current_zonelist_order;
3419
3420         /* initialize zonelists */
3421         for (i = 0; i < MAX_ZONELISTS; i++) {
3422                 zonelist = pgdat->node_zonelists + i;
3423                 zonelist->_zonerefs[0].zone = NULL;
3424                 zonelist->_zonerefs[0].zone_idx = 0;
3425         }
3426
3427         /* NUMA-aware ordering of nodes */
3428         local_node = pgdat->node_id;
3429         load = nr_online_nodes;
3430         prev_node = local_node;
3431         nodes_clear(used_mask);
3432
3433         memset(node_order, 0, sizeof(node_order));
3434         j = 0;
3435
3436         while ((node = find_next_best_node(local_node, &used_mask)) >= 0) {
3437                 /*
3438                  * We don't want to pressure a particular node.
3439                  * So adding penalty to the first node in same
3440                  * distance group to make it round-robin.
3441                  */
3442                 if (node_distance(local_node, node) !=
3443                     node_distance(local_node, prev_node))
3444                         node_load[node] = load;
3445
3446                 prev_node = node;
3447                 load--;
3448                 if (order == ZONELIST_ORDER_NODE)
3449                         build_zonelists_in_node_order(pgdat, node);
3450                 else
3451                         node_order[j++] = node; /* remember order */
3452         }
3453
3454         if (order == ZONELIST_ORDER_ZONE) {
3455                 /* calculate node order -- i.e., DMA last! */
3456                 build_zonelists_in_zone_order(pgdat, j);
3457         }
3458
3459         build_thisnode_zonelists(pgdat);
3460 }
3461
3462 /* Construct the zonelist performance cache - see further mmzone.h */
3463 static void build_zonelist_cache(pg_data_t *pgdat)
3464 {
3465         struct zonelist *zonelist;
3466         struct zonelist_cache *zlc;
3467         struct zoneref *z;
3468
3469         zonelist = &pgdat->node_zonelists[0];
3470         zonelist->zlcache_ptr = zlc = &zonelist->zlcache;
3471         bitmap_zero(zlc->fullzones, MAX_ZONES_PER_ZONELIST);
3472         for (z = zonelist->_zonerefs; z->zone; z++)
3473                 zlc->z_to_n[z - zonelist->_zonerefs] = zonelist_node_idx(z);
3474 }
3475
3476 #ifdef CONFIG_HAVE_MEMORYLESS_NODES
3477 /*
3478  * Return node id of node used for "local" allocations.
3479  * I.e., first node id of first zone in arg node's generic zonelist.
3480  * Used for initializing percpu 'numa_mem', which is used primarily
3481  * for kernel allocations, so use GFP_KERNEL flags to locate zonelist.
3482  */
3483 int local_memory_node(int node)
3484 {
3485         struct zone *zone;
3486
3487         (void)first_zones_zonelist(node_zonelist(node, GFP_KERNEL),
3488                                    gfp_zone(GFP_KERNEL),
3489                                    NULL,
3490                                    &zone);
3491         return zone->node;
3492 }
3493 #endif
3494
3495 #else   /* CONFIG_NUMA */
3496
3497 static void set_zonelist_order(void)
3498 {
3499         current_zonelist_order = ZONELIST_ORDER_ZONE;
3500 }
3501
3502 static void build_zonelists(pg_data_t *pgdat)
3503 {
3504         int node, local_node;
3505         enum zone_type j;
3506         struct zonelist *zonelist;
3507
3508         local_node = pgdat->node_id;
3509
3510         zonelist = &pgdat->node_zonelists[0];
3511         j = build_zonelists_node(pgdat, zonelist, 0, MAX_NR_ZONES - 1);
3512
3513         /*
3514          * Now we build the zonelist so that it contains the zones
3515          * of all the other nodes.
3516          * We don't want to pressure a particular node, so when
3517          * building the zones for node N, we make sure that the
3518          * zones coming right after the local ones are those from
3519          * node N+1 (modulo N)
3520          */
3521         for (node = local_node + 1; node < MAX_NUMNODES; node++) {
3522                 if (!node_online(node))
3523                         continue;
3524                 j = build_zonelists_node(NODE_DATA(node), zonelist, j,
3525                                                         MAX_NR_ZONES - 1);
3526         }
3527         for (node = 0; node < local_node; node++) {
3528                 if (!node_online(node))
3529                         continue;
3530                 j = build_zonelists_node(NODE_DATA(node), zonelist, j,
3531                                                         MAX_NR_ZONES - 1);
3532         }
3533
3534         zonelist->_zonerefs[j].zone = NULL;
3535         zonelist->_zonerefs[j].zone_idx = 0;
3536 }
3537
3538 /* non-NUMA variant of zonelist performance cache - just NULL zlcache_ptr */
3539 static void build_zonelist_cache(pg_data_t *pgdat)
3540 {
3541         pgdat->node_zonelists[0].zlcache_ptr = NULL;
3542 }
3543
3544 #endif  /* CONFIG_NUMA */
3545
3546 /*
3547  * Boot pageset table. One per cpu which is going to be used for all
3548  * zones and all nodes. The parameters will be set in such a way
3549  * that an item put on a list will immediately be handed over to
3550  * the buddy list. This is safe since pageset manipulation is done
3551  * with interrupts disabled.
3552  *
3553  * The boot_pagesets must be kept even after bootup is complete for
3554  * unused processors and/or zones. They do play a role for bootstrapping
3555  * hotplugged processors.
3556  *
3557  * zoneinfo_show() and maybe other functions do
3558  * not check if the processor is online before following the pageset pointer.
3559  * Other parts of the kernel may not check if the zone is available.
3560  */
3561 static void setup_pageset(struct per_cpu_pageset *p, unsigned long batch);
3562 static DEFINE_PER_CPU(struct per_cpu_pageset, boot_pageset);
3563 static void setup_zone_pageset(struct zone *zone);
3564
3565 /*
3566  * Global mutex to protect against size modification of zonelists
3567  * as well as to serialize pageset setup for the new populated zone.
3568  */
3569 DEFINE_MUTEX(zonelists_mutex);
3570
3571 /* return values int ....just for stop_machine() */
3572 static int __build_all_zonelists(void *data)
3573 {
3574         int nid;
3575         int cpu;
3576         pg_data_t *self = data;
3577
3578 #ifdef CONFIG_NUMA
3579         memset(node_load, 0, sizeof(node_load));
3580 #endif
3581
3582         if (self && !node_online(self->node_id)) {
3583                 build_zonelists(self);
3584                 build_zonelist_cache(self);
3585         }
3586
3587         for_each_online_node(nid) {
3588                 pg_data_t *pgdat = NODE_DATA(nid);
3589
3590                 build_zonelists(pgdat);
3591                 build_zonelist_cache(pgdat);
3592         }
3593
3594         /*
3595          * Initialize the boot_pagesets that are going to be used
3596          * for bootstrapping processors. The real pagesets for
3597          * each zone will be allocated later when the per cpu
3598          * allocator is available.
3599          *
3600          * boot_pagesets are used also for bootstrapping offline
3601          * cpus if the system is already booted because the pagesets
3602          * are needed to initialize allocators on a specific cpu too.
3603          * F.e. the percpu allocator needs the page allocator which
3604          * needs the percpu allocator in order to allocate its pagesets
3605          * (a chicken-egg dilemma).
3606          */
3607         for_each_possible_cpu(cpu) {
3608                 setup_pageset(&per_cpu(boot_pageset, cpu), 0);
3609
3610 #ifdef CONFIG_HAVE_MEMORYLESS_NODES
3611                 /*
3612                  * We now know the "local memory node" for each node--
3613                  * i.e., the node of the first zone in the generic zonelist.
3614                  * Set up numa_mem percpu variable for on-line cpus.  During
3615                  * boot, only the boot cpu should be on-line;  we'll init the
3616                  * secondary cpus' numa_mem as they come on-line.  During
3617                  * node/memory hotplug, we'll fixup all on-line cpus.
3618                  */
3619                 if (cpu_online(cpu))
3620                         set_cpu_numa_mem(cpu, local_memory_node(cpu_to_node(cpu)));
3621 #endif
3622         }
3623
3624         return 0;
3625 }
3626
3627 /*
3628  * Called with zonelists_mutex held always
3629  * unless system_state == SYSTEM_BOOTING.
3630  */
3631 void __ref build_all_zonelists(pg_data_t *pgdat, struct zone *zone)
3632 {
3633         set_zonelist_order();
3634
3635         if (system_state == SYSTEM_BOOTING) {
3636                 __build_all_zonelists(NULL);
3637                 mminit_verify_zonelist();
3638                 cpuset_init_current_mems_allowed();
3639         } else {
3640                 /* we have to stop all cpus to guarantee there is no user
3641                    of zonelist */
3642 #ifdef CONFIG_MEMORY_HOTPLUG
3643                 if (zone)
3644                         setup_zone_pageset(zone);
3645 #endif
3646                 stop_machine(__build_all_zonelists, pgdat, NULL);
3647                 /* cpuset refresh routine should be here */
3648         }
3649         vm_total_pages = nr_free_pagecache_pages();
3650         /*
3651          * Disable grouping by mobility if the number of pages in the
3652          * system is too low to allow the mechanism to work. It would be
3653          * more accurate, but expensive to check per-zone. This check is
3654          * made on memory-hotadd so a system can start with mobility
3655          * disabled and enable it later
3656          */
3657         if (vm_total_pages < (pageblock_nr_pages * MIGRATE_TYPES))
3658                 page_group_by_mobility_disabled = 1;
3659         else
3660                 page_group_by_mobility_disabled = 0;
3661
3662         printk("Built %i zonelists in %s order, mobility grouping %s.  "
3663                 "Total pages: %ld\n",
3664                         nr_online_nodes,
3665                         zonelist_order_name[current_zonelist_order],
3666                         page_group_by_mobility_disabled ? "off" : "on",
3667                         vm_total_pages);
3668 #ifdef CONFIG_NUMA
3669         printk("Policy zone: %s\n", zone_names[policy_zone]);
3670 #endif
3671 }
3672
3673 /*
3674  * Helper functions to size the waitqueue hash table.
3675  * Essentially these want to choose hash table sizes sufficiently
3676  * large so that collisions trying to wait on pages are rare.
3677  * But in fact, the number of active page waitqueues on typical
3678  * systems is ridiculously low, less than 200. So this is even
3679  * conservative, even though it seems large.
3680  *
3681  * The constant PAGES_PER_WAITQUEUE specifies the ratio of pages to
3682  * waitqueues, i.e. the size of the waitq table given the number of pages.
3683  */
3684 #define PAGES_PER_WAITQUEUE     256
3685
3686 #ifndef CONFIG_MEMORY_HOTPLUG
3687 static inline unsigned long wait_table_hash_nr_entries(unsigned long pages)
3688 {
3689         unsigned long size = 1;
3690
3691         pages /= PAGES_PER_WAITQUEUE;
3692
3693         while (size < pages)
3694                 size <<= 1;
3695
3696         /*
3697          * Once we have dozens or even hundreds of threads sleeping
3698          * on IO we've got bigger problems than wait queue collision.
3699          * Limit the size of the wait table to a reasonable size.
3700          */
3701         size = min(size, 4096UL);
3702
3703         return max(size, 4UL);
3704 }
3705 #else
3706 /*
3707  * A zone's size might be changed by hot-add, so it is not possible to determine
3708  * a suitable size for its wait_table.  So we use the maximum size now.
3709  *
3710  * The max wait table size = 4096 x sizeof(wait_queue_head_t).   ie:
3711  *
3712  *    i386 (preemption config)    : 4096 x 16 = 64Kbyte.
3713  *    ia64, x86-64 (no preemption): 4096 x 20 = 80Kbyte.
3714  *    ia64, x86-64 (preemption)   : 4096 x 24 = 96Kbyte.
3715  *
3716  * The maximum entries are prepared when a zone's memory is (512K + 256) pages
3717  * or more by the traditional way. (See above).  It equals:
3718  *
3719  *    i386, x86-64, powerpc(4K page size) : =  ( 2G + 1M)byte.
3720  *    ia64(16K page size)                 : =  ( 8G + 4M)byte.
3721  *    powerpc (64K page size)             : =  (32G +16M)byte.
3722  */
3723 static inline unsigned long wait_table_hash_nr_entries(unsigned long pages)
3724 {
3725         return 4096UL;
3726 }
3727 #endif
3728
3729 /*
3730  * This is an integer logarithm so that shifts can be used later
3731  * to extract the more random high bits from the multiplicative
3732  * hash function before the remainder is taken.
3733  */
3734 static inline unsigned long wait_table_bits(unsigned long size)
3735 {
3736         return ffz(~size);
3737 }
3738
3739 #define LONG_ALIGN(x) (((x)+(sizeof(long))-1)&~((sizeof(long))-1))
3740
3741 /*
3742  * Check if a pageblock contains reserved pages
3743  */
3744 static int pageblock_is_reserved(unsigned long start_pfn, unsigned long end_pfn)
3745 {
3746         unsigned long pfn;
3747
3748         for (pfn = start_pfn; pfn < end_pfn; pfn++) {
3749                 if (!pfn_valid_within(pfn) || PageReserved(pfn_to_page(pfn)))
3750                         return 1;
3751         }
3752         return 0;
3753 }
3754
3755 /*
3756  * Mark a number of pageblocks as MIGRATE_RESERVE. The number
3757  * of blocks reserved is based on min_wmark_pages(zone). The memory within
3758  * the reserve will tend to store contiguous free pages. Setting min_free_kbytes
3759  * higher will lead to a bigger reserve which will get freed as contiguous
3760  * blocks as reclaim kicks in
3761  */
3762 static void setup_zone_migrate_reserve(struct zone *zone)
3763 {
3764         unsigned long start_pfn, pfn, end_pfn, block_end_pfn;
3765         struct page *page;
3766         unsigned long block_migratetype;
3767         int reserve;
3768
3769         /*
3770          * Get the start pfn, end pfn and the number of blocks to reserve
3771          * We have to be careful to be aligned to pageblock_nr_pages to
3772          * make sure that we always check pfn_valid for the first page in
3773          * the block.
3774          */
3775         start_pfn = zone->zone_start_pfn;
3776         end_pfn = start_pfn + zone->spanned_pages;
3777         start_pfn = roundup(start_pfn, pageblock_nr_pages);
3778         reserve = roundup(min_wmark_pages(zone), pageblock_nr_pages) >>
3779                                                         pageblock_order;
3780
3781         /*
3782          * Reserve blocks are generally in place to help high-order atomic
3783          * allocations that are short-lived. A min_free_kbytes value that
3784          * would result in more than 2 reserve blocks for atomic allocations
3785          * is assumed to be in place to help anti-fragmentation for the
3786          * future allocation of hugepages at runtime.
3787          */
3788         reserve = min(2, reserve);
3789
3790         for (pfn = start_pfn; pfn < end_pfn; pfn += pageblock_nr_pages) {
3791                 if (!pfn_valid(pfn))
3792                         continue;
3793                 page = pfn_to_page(pfn);
3794
3795                 /* Watch out for overlapping nodes */
3796                 if (page_to_nid(page) != zone_to_nid(zone))
3797                         continue;
3798
3799                 block_migratetype = get_pageblock_migratetype(page);
3800
3801                 /* Only test what is necessary when the reserves are not met */
3802                 if (reserve > 0) {
3803                         /*
3804                          * Blocks with reserved pages will never free, skip
3805                          * them.
3806                          */
3807                         block_end_pfn = min(pfn + pageblock_nr_pages, end_pfn);
3808                         if (pageblock_is_reserved(pfn, block_end_pfn))
3809                                 continue;
3810
3811                         /* If this block is reserved, account for it */
3812                         if (block_migratetype == MIGRATE_RESERVE) {
3813                                 reserve--;
3814                                 continue;
3815                         }
3816
3817                         /* Suitable for reserving if this block is movable */
3818                         if (block_migratetype == MIGRATE_MOVABLE) {
3819                                 set_pageblock_migratetype(page,
3820                                                         MIGRATE_RESERVE);
3821                                 move_freepages_block(zone, page,
3822                                                         MIGRATE_RESERVE);
3823                                 reserve--;
3824                                 continue;
3825                         }
3826                 }
3827
3828                 /*
3829                  * If the reserve is met and this is a previous reserved block,
3830                  * take it back
3831                  */
3832                 if (block_migratetype == MIGRATE_RESERVE) {
3833                         set_pageblock_migratetype(page, MIGRATE_MOVABLE);
3834                         move_freepages_block(zone, page, MIGRATE_MOVABLE);
3835                 }
3836         }
3837 }
3838
3839 /*
3840  * Initially all pages are reserved - free ones are freed
3841  * up by free_all_bootmem() once the early boot process is
3842  * done. Non-atomic initialization, single-pass.
3843  */
3844 void __meminit memmap_init_zone(unsigned long size, int nid, unsigned long zone,
3845                 unsigned long start_pfn, enum memmap_context context)
3846 {
3847         struct page *page;
3848         unsigned long end_pfn = start_pfn + size;
3849         unsigned long pfn;
3850         struct zone *z;
3851
3852         if (highest_memmap_pfn < end_pfn - 1)
3853                 highest_memmap_pfn = end_pfn - 1;
3854
3855         z = &NODE_DATA(nid)->node_zones[zone];
3856         for (pfn = start_pfn; pfn < end_pfn; pfn++) {
3857                 /*
3858                  * There can be holes in boot-time mem_map[]s
3859                  * handed to this function.  They do not
3860                  * exist on hotplugged memory.
3861                  */
3862                 if (context == MEMMAP_EARLY) {
3863                         if (!early_pfn_valid(pfn))
3864                                 continue;
3865                         if (!early_pfn_in_nid(pfn, nid))
3866                                 continue;
3867                 }
3868                 page = pfn_to_page(pfn);
3869                 set_page_links(page, zone, nid, pfn);
3870                 mminit_verify_page_links(page, zone, nid, pfn);
3871                 init_page_count(page);
3872                 reset_page_mapcount(page);
3873                 SetPageReserved(page);
3874                 /*
3875                  * Mark the block movable so that blocks are reserved for
3876                  * movable at startup. This will force kernel allocations
3877                  * to reserve their blocks rather than leaking throughout
3878                  * the address space during boot when many long-lived
3879                  * kernel allocations are made. Later some blocks near
3880                  * the start are marked MIGRATE_RESERVE by
3881                  * setup_zone_migrate_reserve()
3882                  *
3883                  * bitmap is created for zone's valid pfn range. but memmap
3884                  * can be created for invalid pages (for alignment)
3885                  * check here not to call set_pageblock_migratetype() against
3886                  * pfn out of zone.
3887                  */
3888                 if ((z->zone_start_pfn <= pfn)
3889                     && (pfn < z->zone_start_pfn + z->spanned_pages)
3890                     && !(pfn & (pageblock_nr_pages - 1)))
3891                         set_pageblock_migratetype(page, MIGRATE_MOVABLE);
3892
3893                 INIT_LIST_HEAD(&page->lru);
3894 #ifdef WANT_PAGE_VIRTUAL
3895                 /* The shift won't overflow because ZONE_NORMAL is below 4G. */
3896                 if (!is_highmem_idx(zone))
3897                         set_page_address(page, __va(pfn << PAGE_SHIFT));
3898 #endif
3899         }
3900 }
3901
3902 static void __meminit zone_init_free_lists(struct zone *zone)
3903 {
3904         int order, t;
3905         for_each_migratetype_order(order, t) {
3906                 INIT_LIST_HEAD(&zone->free_area[order].free_list[t]);
3907                 zone->free_area[order].nr_free = 0;
3908         }
3909 }
3910
3911 #ifndef __HAVE_ARCH_MEMMAP_INIT
3912 #define memmap_init(size, nid, zone, start_pfn) \
3913         memmap_init_zone((size), (nid), (zone), (start_pfn), MEMMAP_EARLY)
3914 #endif
3915
3916 static int __meminit zone_batchsize(struct zone *zone)
3917 {
3918 #ifdef CONFIG_MMU
3919         int batch;
3920
3921         /*
3922          * The per-cpu-pages pools are set to around 1000th of the
3923          * size of the zone.  But no more than 1/2 of a meg.
3924          *
3925          * OK, so we don't know how big the cache is.  So guess.
3926          */
3927         batch = zone->present_pages / 1024;
3928         if (batch * PAGE_SIZE > 512 * 1024)
3929                 batch = (512 * 1024) / PAGE_SIZE;
3930         batch /= 4;             /* We effectively *= 4 below */
3931         if (batch < 1)
3932                 batch = 1;
3933
3934         /*
3935          * Clamp the batch to a 2^n - 1 value. Having a power
3936          * of 2 value was found to be more likely to have
3937          * suboptimal cache aliasing properties in some cases.
3938          *
3939          * For example if 2 tasks are alternately allocating
3940          * batches of pages, one task can end up with a lot
3941          * of pages of one half of the possible page colors
3942          * and the other with pages of the other colors.
3943          */
3944         batch = rounddown_pow_of_two(batch + batch/2) - 1;
3945
3946         return batch;
3947
3948 #else
3949         /* The deferral and batching of frees should be suppressed under NOMMU
3950          * conditions.
3951          *
3952          * The problem is that NOMMU needs to be able to allocate large chunks
3953          * of contiguous memory as there's no hardware page translation to
3954          * assemble apparent contiguous memory from discontiguous pages.
3955          *
3956          * Queueing large contiguous runs of pages for batching, however,
3957          * causes the pages to actually be freed in smaller chunks.  As there
3958          * can be a significant delay between the individual batches being
3959          * recycled, this leads to the once large chunks of space being
3960          * fragmented and becoming unavailable for high-order allocations.
3961          */
3962         return 0;
3963 #endif
3964 }
3965
3966 static void setup_pageset(struct per_cpu_pageset *p, unsigned long batch)
3967 {
3968         struct per_cpu_pages *pcp;
3969         int migratetype;
3970
3971         memset(p, 0, sizeof(*p));
3972
3973         pcp = &p->pcp;
3974         pcp->count = 0;
3975         pcp->high = 6 * batch;
3976         pcp->batch = max(1UL, 1 * batch);
3977         for (migratetype = 0; migratetype < MIGRATE_PCPTYPES; migratetype++)
3978                 INIT_LIST_HEAD(&pcp->lists[migratetype]);
3979 }
3980
3981 /*
3982  * setup_pagelist_highmark() sets the high water mark for hot per_cpu_pagelist
3983  * to the value high for the pageset p.
3984  */
3985
3986 static void setup_pagelist_highmark(struct per_cpu_pageset *p,
3987                                 unsigned long high)
3988 {
3989         struct per_cpu_pages *pcp;
3990
3991         pcp = &p->pcp;
3992         pcp->high = high;
3993         pcp->batch = max(1UL, high/4);
3994         if ((high/4) > (PAGE_SHIFT * 8))
3995                 pcp->batch = PAGE_SHIFT * 8;
3996 }
3997
3998 static void __meminit setup_zone_pageset(struct zone *zone)
3999 {
4000         int cpu;
4001
4002         zone->pageset = alloc_percpu(struct per_cpu_pageset);
4003
4004         for_each_possible_cpu(cpu) {
4005                 struct per_cpu_pageset *pcp = per_cpu_ptr(zone->pageset, cpu);
4006
4007                 setup_pageset(pcp, zone_batchsize(zone));
4008
4009                 if (percpu_pagelist_fraction)
4010                         setup_pagelist_highmark(pcp,
4011                                 (zone->present_pages /
4012                                         percpu_pagelist_fraction));
4013         }
4014 }
4015
4016 /*
4017  * Allocate per cpu pagesets and initialize them.
4018  * Before this call only boot pagesets were available.
4019  */
4020 void __init setup_per_cpu_pageset(void)
4021 {
4022         struct zone *zone;
4023
4024         for_each_populated_zone(zone)
4025                 setup_zone_pageset(zone);
4026 }
4027
4028 static noinline __init_refok
4029 int zone_wait_table_init(struct zone *zone, unsigned long zone_size_pages)
4030 {
4031         int i;
4032         struct pglist_data *pgdat = zone->zone_pgdat;
4033         size_t alloc_size;
4034
4035         /*
4036          * The per-page waitqueue mechanism uses hashed waitqueues
4037          * per zone.
4038          */
4039         zone->wait_table_hash_nr_entries =
4040                  wait_table_hash_nr_entries(zone_size_pages);
4041         zone->wait_table_bits =
4042                 wait_table_bits(zone->wait_table_hash_nr_entries);
4043         alloc_size = zone->wait_table_hash_nr_entries
4044                                         * sizeof(wait_queue_head_t);
4045
4046         if (!slab_is_available()) {
4047                 zone->wait_table = (wait_queue_head_t *)
4048                         alloc_bootmem_node_nopanic(pgdat, alloc_size);
4049         } else {
4050                 /*
4051                  * This case means that a zone whose size was 0 gets new memory
4052                  * via memory hot-add.
4053                  * But it may be the case that a new node was hot-added.  In
4054                  * this case vmalloc() will not be able to use this new node's
4055                  * memory - this wait_table must be initialized to use this new
4056                  * node itself as well.
4057                  * To use this new node's memory, further consideration will be
4058                  * necessary.
4059                  */
4060                 zone->wait_table = vmalloc(alloc_size);
4061         }
4062         if (!zone->wait_table)
4063                 return -ENOMEM;
4064
4065         for(i = 0; i < zone->wait_table_hash_nr_entries; ++i)
4066                 init_waitqueue_head(zone->wait_table + i);
4067
4068         return 0;
4069 }
4070
4071 static __meminit void zone_pcp_init(struct zone *zone)
4072 {
4073         /*
4074          * per cpu subsystem is not up at this point. The following code
4075          * relies on the ability of the linker to provide the
4076          * offset of a (static) per cpu variable into the per cpu area.
4077          */
4078         zone->pageset = &boot_pageset;
4079
4080         if (zone->present_pages)
4081                 printk(KERN_DEBUG "  %s zone: %lu pages, LIFO batch:%u\n",
4082                         zone->name, zone->present_pages,
4083                                          zone_batchsize(zone));
4084 }
4085
4086 int __meminit init_currently_empty_zone(struct zone *zone,
4087                                         unsigned long zone_start_pfn,
4088                                         unsigned long size,
4089                                         enum memmap_context context)
4090 {
4091         struct pglist_data *pgdat = zone->zone_pgdat;
4092         int ret;
4093         ret = zone_wait_table_init(zone, size);
4094         if (ret)
4095                 return ret;
4096         pgdat->nr_zones = zone_idx(zone) + 1;
4097
4098         zone->zone_start_pfn = zone_start_pfn;
4099
4100         mminit_dprintk(MMINIT_TRACE, "memmap_init",
4101                         "Initialising map node %d zone %lu pfns %lu -> %lu\n",
4102                         pgdat->node_id,
4103                         (unsigned long)zone_idx(zone),
4104                         zone_start_pfn, (zone_start_pfn + size));
4105
4106         zone_init_free_lists(zone);
4107
4108         return 0;
4109 }
4110
4111 #ifdef CONFIG_HAVE_MEMBLOCK_NODE_MAP
4112 #ifndef CONFIG_HAVE_ARCH_EARLY_PFN_TO_NID
4113 /*
4114  * Required by SPARSEMEM. Given a PFN, return what node the PFN is on.
4115  * Architectures may implement their own version but if add_active_range()
4116  * was used and there are no special requirements, this is a convenient
4117  * alternative
4118  */
4119 int __meminit __early_pfn_to_nid(unsigned long pfn)
4120 {
4121         unsigned long start_pfn, end_pfn;
4122         int i, nid;
4123
4124         for_each_mem_pfn_range(i, MAX_NUMNODES, &start_pfn, &end_pfn, &nid)
4125                 if (start_pfn <= pfn && pfn < end_pfn)
4126                         return nid;
4127         /* This is a memory hole */
4128         return -1;
4129 }
4130 #endif /* CONFIG_HAVE_ARCH_EARLY_PFN_TO_NID */
4131
4132 int __meminit early_pfn_to_nid(unsigned long pfn)
4133 {
4134         int nid;
4135
4136         nid = __early_pfn_to_nid(pfn);
4137         if (nid >= 0)
4138                 return nid;
4139         /* just returns 0 */
4140         return 0;
4141 }
4142
4143 #ifdef CONFIG_NODES_SPAN_OTHER_NODES
4144 bool __meminit early_pfn_in_nid(unsigned long pfn, int node)
4145 {
4146         int nid;
4147
4148         nid = __early_pfn_to_nid(pfn);
4149         if (nid >= 0 && nid != node)
4150                 return false;
4151         return true;
4152 }
4153 #endif
4154
4155 /**
4156  * free_bootmem_with_active_regions - Call free_bootmem_node for each active range
4157  * @nid: The node to free memory on. If MAX_NUMNODES, all nodes are freed.
4158  * @max_low_pfn: The highest PFN that will be passed to free_bootmem_node
4159  *
4160  * If an architecture guarantees that all ranges registered with
4161  * add_active_ranges() contain no holes and may be freed, this
4162  * this function may be used instead of calling free_bootmem() manually.
4163  */
4164 void __init free_bootmem_with_active_regions(int nid, unsigned long max_low_pfn)
4165 {
4166         unsigned long start_pfn, end_pfn;
4167         int i, this_nid;
4168
4169         for_each_mem_pfn_range(i, nid, &start_pfn, &end_pfn, &this_nid) {
4170                 start_pfn = min(start_pfn, max_low_pfn);
4171                 end_pfn = min(end_pfn, max_low_pfn);
4172
4173                 if (start_pfn < end_pfn)
4174                         free_bootmem_node(NODE_DATA(this_nid),
4175                                           PFN_PHYS(start_pfn),
4176                                           (end_pfn - start_pfn) << PAGE_SHIFT);
4177         }
4178 }
4179
4180 /**
4181  * sparse_memory_present_with_active_regions - Call memory_present for each active range
4182  * @nid: The node to call memory_present for. If MAX_NUMNODES, all nodes will be used.
4183  *
4184  * If an architecture guarantees that all ranges registered with
4185  * add_active_ranges() contain no holes and may be freed, this
4186  * function may be used instead of calling memory_present() manually.
4187  */
4188 void __init sparse_memory_present_with_active_regions(int nid)
4189 {
4190         unsigned long start_pfn, end_pfn;
4191         int i, this_nid;
4192
4193         for_each_mem_pfn_range(i, nid, &start_pfn, &end_pfn, &this_nid)
4194                 memory_present(this_nid, start_pfn, end_pfn);
4195 }
4196
4197 /**
4198  * get_pfn_range_for_nid - Return the start and end page frames for a node
4199  * @nid: The nid to return the range for. If MAX_NUMNODES, the min and max PFN are returned.
4200  * @start_pfn: Passed by reference. On return, it will have the node start_pfn.
4201  * @end_pfn: Passed by reference. On return, it will have the node end_pfn.
4202  *
4203  * It returns the start and end page frame of a node based on information
4204  * provided by an arch calling add_active_range(). If called for a node
4205  * with no available memory, a warning is printed and the start and end
4206  * PFNs will be 0.
4207  */
4208 void __meminit get_pfn_range_for_nid(unsigned int nid,
4209                         unsigned long *start_pfn, unsigned long *end_pfn)
4210 {
4211         unsigned long this_start_pfn, this_end_pfn;
4212         int i;
4213
4214         *start_pfn = -1UL;
4215         *end_pfn = 0;
4216
4217         for_each_mem_pfn_range(i, nid, &this_start_pfn, &this_end_pfn, NULL) {
4218                 *start_pfn = min(*start_pfn, this_start_pfn);
4219                 *end_pfn = max(*end_pfn, this_end_pfn);
4220         }
4221
4222         if (*start_pfn == -1UL)
4223                 *start_pfn = 0;
4224 }
4225
4226 /*
4227  * This finds a zone that can be used for ZONE_MOVABLE pages. The
4228  * assumption is made that zones within a node are ordered in monotonic
4229  * increasing memory addresses so that the "highest" populated zone is used
4230  */
4231 static void __init find_usable_zone_for_movable(void)
4232 {
4233         int zone_index;
4234         for (zone_index = MAX_NR_ZONES - 1; zone_index >= 0; zone_index--) {
4235                 if (zone_index == ZONE_MOVABLE)
4236                         continue;
4237
4238                 if (arch_zone_highest_possible_pfn[zone_index] >
4239                                 arch_zone_lowest_possible_pfn[zone_index])
4240                         break;
4241         }
4242
4243         VM_BUG_ON(zone_index == -1);
4244         movable_zone = zone_index;
4245 }
4246
4247 /*
4248  * The zone ranges provided by the architecture do not include ZONE_MOVABLE
4249  * because it is sized independent of architecture. Unlike the other zones,
4250  * the starting point for ZONE_MOVABLE is not fixed. It may be different
4251  * in each node depending on the size of each node and how evenly kernelcore
4252  * is distributed. This helper function adjusts the zone ranges
4253  * provided by the architecture for a given node by using the end of the
4254  * highest usable zone for ZONE_MOVABLE. This preserves the assumption that
4255  * zones within a node are in order of monotonic increases memory addresses
4256  */
4257 static void __meminit adjust_zone_range_for_zone_movable(int nid,
4258                                         unsigned long zone_type,
4259                                         unsigned long node_start_pfn,
4260                                         unsigned long node_end_pfn,
4261                                         unsigned long *zone_start_pfn,
4262                                         unsigned long *zone_end_pfn)
4263 {
4264         /* Only adjust if ZONE_MOVABLE is on this node */
4265         if (zone_movable_pfn[nid]) {
4266                 /* Size ZONE_MOVABLE */
4267                 if (zone_type == ZONE_MOVABLE) {
4268                         *zone_start_pfn = zone_movable_pfn[nid];
4269                         *zone_end_pfn = min(node_end_pfn,
4270                                 arch_zone_highest_possible_pfn[movable_zone]);
4271
4272                 /* Adjust for ZONE_MOVABLE starting within this range */
4273                 } else if (*zone_start_pfn < zone_movable_pfn[nid] &&
4274                                 *zone_end_pfn > zone_movable_pfn[nid]) {
4275                         *zone_end_pfn = zone_movable_pfn[nid];
4276
4277                 /* Check if this whole range is within ZONE_MOVABLE */
4278                 } else if (*zone_start_pfn >= zone_movable_pfn[nid])
4279                         *zone_start_pfn = *zone_end_pfn;
4280         }
4281 }
4282
4283 /*
4284  * Return the number of pages a zone spans in a node, including holes
4285  * present_pages = zone_spanned_pages_in_node() - zone_absent_pages_in_node()
4286  */
4287 static unsigned long __meminit zone_spanned_pages_in_node(int nid,
4288                                         unsigned long zone_type,
4289                                         unsigned long *ignored)
4290 {
4291         unsigned long node_start_pfn, node_end_pfn;
4292         unsigned long zone_start_pfn, zone_end_pfn;
4293
4294         /* Get the start and end of the node and zone */
4295         get_pfn_range_for_nid(nid, &node_start_pfn, &node_end_pfn);
4296         zone_start_pfn = arch_zone_lowest_possible_pfn[zone_type];
4297         zone_end_pfn = arch_zone_highest_possible_pfn[zone_type];
4298         adjust_zone_range_for_zone_movable(nid, zone_type,
4299                                 node_start_pfn, node_end_pfn,
4300                                 &zone_start_pfn, &zone_end_pfn);
4301
4302         /* Check that this node has pages within the zone's required range */
4303         if (zone_end_pfn < node_start_pfn || zone_start_pfn > node_end_pfn)
4304                 return 0;
4305
4306         /* Move the zone boundaries inside the node if necessary */
4307         zone_end_pfn = min(zone_end_pfn, node_end_pfn);
4308         zone_start_pfn = max(zone_start_pfn, node_start_pfn);
4309
4310         /* Return the spanned pages */
4311         return zone_end_pfn - zone_start_pfn;
4312 }
4313
4314 /*
4315  * Return the number of holes in a range on a node. If nid is MAX_NUMNODES,
4316  * then all holes in the requested range will be accounted for.
4317  */
4318 unsigned long __meminit __absent_pages_in_range(int nid,
4319                                 unsigned long range_start_pfn,
4320                                 unsigned long range_end_pfn)
4321 {
4322         unsigned long nr_absent = range_end_pfn - range_start_pfn;
4323         unsigned long start_pfn, end_pfn;
4324         int i;
4325
4326         for_each_mem_pfn_range(i, nid, &start_pfn, &end_pfn, NULL) {
4327                 start_pfn = clamp(start_pfn, range_start_pfn, range_end_pfn);
4328                 end_pfn = clamp(end_pfn, range_start_pfn, range_end_pfn);
4329                 nr_absent -= end_pfn - start_pfn;
4330         }
4331         return nr_absent;
4332 }
4333
4334 /**
4335  * absent_pages_in_range - Return number of page frames in holes within a range
4336  * @start_pfn: The start PFN to start searching for holes
4337  * @end_pfn: The end PFN to stop searching for holes
4338  *
4339  * It returns the number of pages frames in memory holes within a range.
4340  */
4341 unsigned long __init absent_pages_in_range(unsigned long start_pfn,
4342                                                         unsigned long end_pfn)
4343 {
4344         return __absent_pages_in_range(MAX_NUMNODES, start_pfn, end_pfn);
4345 }
4346
4347 /* Return the number of page frames in holes in a zone on a node */
4348 static unsigned long __meminit zone_absent_pages_in_node(int nid,
4349                                         unsigned long zone_type,
4350                                         unsigned long *ignored)
4351 {
4352         unsigned long zone_low = arch_zone_lowest_possible_pfn[zone_type];
4353         unsigned long zone_high = arch_zone_highest_possible_pfn[zone_type];
4354         unsigned long node_start_pfn, node_end_pfn;
4355         unsigned long zone_start_pfn, zone_end_pfn;
4356
4357         get_pfn_range_for_nid(nid, &node_start_pfn, &node_end_pfn);
4358         zone_start_pfn = clamp(node_start_pfn, zone_low, zone_high);
4359         zone_end_pfn = clamp(node_end_pfn, zone_low, zone_high);
4360
4361         adjust_zone_range_for_zone_movable(nid, zone_type,
4362                         node_start_pfn, node_end_pfn,
4363                         &zone_start_pfn, &zone_end_pfn);
4364         return __absent_pages_in_range(nid, zone_start_pfn, zone_end_pfn);
4365 }
4366
4367 #else /* CONFIG_HAVE_MEMBLOCK_NODE_MAP */
4368 static inline unsigned long __meminit zone_spanned_pages_in_node(int nid,
4369                                         unsigned long zone_type,
4370                                         unsigned long *zones_size)
4371 {
4372         return zones_size[zone_type];
4373 }
4374
4375 static inline unsigned long __meminit zone_absent_pages_in_node(int nid,
4376                                                 unsigned long zone_type,
4377                                                 unsigned long *zholes_size)
4378 {
4379         if (!zholes_size)
4380                 return 0;
4381
4382         return zholes_size[zone_type];
4383 }
4384
4385 #endif /* CONFIG_HAVE_MEMBLOCK_NODE_MAP */
4386
4387 static void __meminit calculate_node_totalpages(struct pglist_data *pgdat,
4388                 unsigned long *zones_size, unsigned long *zholes_size)
4389 {
4390         unsigned long realtotalpages, totalpages = 0;
4391         enum zone_type i;
4392
4393         for (i = 0; i < MAX_NR_ZONES; i++)
4394                 totalpages += zone_spanned_pages_in_node(pgdat->node_id, i,
4395                                                                 zones_size);
4396         pgdat->node_spanned_pages = totalpages;
4397
4398         realtotalpages = totalpages;
4399         for (i = 0; i < MAX_NR_ZONES; i++)
4400                 realtotalpages -=
4401                         zone_absent_pages_in_node(pgdat->node_id, i,
4402                                                                 zholes_size);
4403         pgdat->node_present_pages = realtotalpages;
4404         printk(KERN_DEBUG "On node %d totalpages: %lu\n", pgdat->node_id,
4405                                                         realtotalpages);
4406 }
4407
4408 #ifndef CONFIG_SPARSEMEM
4409 /*
4410  * Calculate the size of the zone->blockflags rounded to an unsigned long
4411  * Start by making sure zonesize is a multiple of pageblock_order by rounding
4412  * up. Then use 1 NR_PAGEBLOCK_BITS worth of bits per pageblock, finally
4413  * round what is now in bits to nearest long in bits, then return it in
4414  * bytes.
4415  */
4416 static unsigned long __init usemap_size(unsigned long zonesize)
4417 {
4418         unsigned long usemapsize;
4419
4420         usemapsize = roundup(zonesize, pageblock_nr_pages);
4421         usemapsize = usemapsize >> pageblock_order;
4422         usemapsize *= NR_PAGEBLOCK_BITS;
4423         usemapsize = roundup(usemapsize, 8 * sizeof(unsigned long));
4424
4425         return usemapsize / 8;
4426 }
4427
4428 static void __init setup_usemap(struct pglist_data *pgdat,
4429                                 struct zone *zone, unsigned long zonesize)
4430 {
4431         unsigned long usemapsize = usemap_size(zonesize);
4432         zone->pageblock_flags = NULL;
4433         if (usemapsize)
4434                 zone->pageblock_flags = alloc_bootmem_node_nopanic(pgdat,
4435                                                                    usemapsize);
4436 }
4437 #else
4438 static inline void setup_usemap(struct pglist_data *pgdat,
4439                                 struct zone *zone, unsigned long zonesize) {}
4440 #endif /* CONFIG_SPARSEMEM */
4441
4442 #ifdef CONFIG_HUGETLB_PAGE_SIZE_VARIABLE
4443
4444 /* Initialise the number of pages represented by NR_PAGEBLOCK_BITS */
4445 void __init set_pageblock_order(void)
4446 {
4447         unsigned int order;
4448
4449         /* Check that pageblock_nr_pages has not already been setup */
4450         if (pageblock_order)
4451                 return;
4452
4453         if (HPAGE_SHIFT > PAGE_SHIFT)
4454                 order = HUGETLB_PAGE_ORDER;
4455         else
4456                 order = MAX_ORDER - 1;
4457
4458         /*
4459          * Assume the largest contiguous order of interest is a huge page.
4460          * This value may be variable depending on boot parameters on IA64 and
4461          * powerpc.
4462          */
4463         pageblock_order = order;
4464 }
4465 #else /* CONFIG_HUGETLB_PAGE_SIZE_VARIABLE */
4466
4467 /*
4468  * When CONFIG_HUGETLB_PAGE_SIZE_VARIABLE is not set, set_pageblock_order()
4469  * is unused as pageblock_order is set at compile-time. See
4470  * include/linux/pageblock-flags.h for the values of pageblock_order based on
4471  * the kernel config
4472  */
4473 void __init set_pageblock_order(void)
4474 {
4475 }
4476
4477 #endif /* CONFIG_HUGETLB_PAGE_SIZE_VARIABLE */
4478
4479 /*
4480  * Set up the zone data structures:
4481  *   - mark all pages reserved
4482  *   - mark all memory queues empty
4483  *   - clear the memory bitmaps
4484  *
4485  * NOTE: pgdat should get zeroed by caller.
4486  */
4487 static void __paginginit free_area_init_core(struct pglist_data *pgdat,
4488                 unsigned long *zones_size, unsigned long *zholes_size)
4489 {
4490         enum zone_type j;
4491         int nid = pgdat->node_id;
4492         unsigned long zone_start_pfn = pgdat->node_start_pfn;
4493         int ret;
4494
4495         pgdat_resize_init(pgdat);
4496         init_waitqueue_head(&pgdat->kswapd_wait);
4497         init_waitqueue_head(&pgdat->pfmemalloc_wait);
4498         pgdat_page_cgroup_init(pgdat);
4499
4500         for (j = 0; j < MAX_NR_ZONES; j++) {
4501                 struct zone *zone = pgdat->node_zones + j;
4502                 unsigned long size, realsize, memmap_pages;
4503
4504                 size = zone_spanned_pages_in_node(nid, j, zones_size);
4505                 realsize = size - zone_absent_pages_in_node(nid, j,
4506                                                                 zholes_size);
4507
4508                 /*
4509                  * Adjust realsize so that it accounts for how much memory
4510                  * is used by this zone for memmap. This affects the watermark
4511                  * and per-cpu initialisations
4512                  */
4513                 memmap_pages =
4514                         PAGE_ALIGN(size * sizeof(struct page)) >> PAGE_SHIFT;
4515                 if (realsize >= memmap_pages) {
4516                         realsize -= memmap_pages;
4517                         if (memmap_pages)
4518                                 printk(KERN_DEBUG
4519                                        "  %s zone: %lu pages used for memmap\n",
4520                                        zone_names[j], memmap_pages);
4521                 } else
4522                         printk(KERN_WARNING
4523                                 "  %s zone: %lu pages exceeds realsize %lu\n",
4524                                 zone_names[j], memmap_pages, realsize);
4525
4526                 /* Account for reserved pages */
4527                 if (j == 0 && realsize > dma_reserve) {
4528                         realsize -= dma_reserve;
4529                         printk(KERN_DEBUG "  %s zone: %lu pages reserved\n",
4530                                         zone_names[0], dma_reserve);
4531                 }
4532
4533                 if (!is_highmem_idx(j))
4534                         nr_kernel_pages += realsize;
4535                 nr_all_pages += realsize;
4536
4537                 zone->spanned_pages = size;
4538                 zone->present_pages = realsize;
4539 #ifdef CONFIG_NUMA
4540                 zone->node = nid;
4541                 zone->min_unmapped_pages = (realsize*sysctl_min_unmapped_ratio)
4542                                                 / 100;
4543                 zone->min_slab_pages = (realsize * sysctl_min_slab_ratio) / 100;
4544 #endif
4545                 zone->name = zone_names[j];
4546                 spin_lock_init(&zone->lock);
4547                 spin_lock_init(&zone->lru_lock);
4548                 zone_seqlock_init(zone);
4549                 zone->zone_pgdat = pgdat;
4550
4551                 zone_pcp_init(zone);
4552                 lruvec_init(&zone->lruvec);
4553                 if (!size)
4554                         continue;
4555
4556                 set_pageblock_order();
4557                 setup_usemap(pgdat, zone, size);
4558                 ret = init_currently_empty_zone(zone, zone_start_pfn,
4559                                                 size, MEMMAP_EARLY);
4560                 BUG_ON(ret);
4561                 memmap_init(size, nid, j, zone_start_pfn);
4562                 zone_start_pfn += size;
4563         }
4564 }
4565
4566 static void __init_refok alloc_node_mem_map(struct pglist_data *pgdat)
4567 {
4568         /* Skip empty nodes */
4569         if (!pgdat->node_spanned_pages)
4570                 return;
4571
4572 #ifdef CONFIG_FLAT_NODE_MEM_MAP
4573         /* ia64 gets its own node_mem_map, before this, without bootmem */
4574         if (!pgdat->node_mem_map) {
4575                 unsigned long size, start, end;
4576                 struct page *map;
4577
4578                 /*
4579                  * The zone's endpoints aren't required to be MAX_ORDER
4580                  * aligned but the node_mem_map endpoints must be in order
4581                  * for the buddy allocator to function correctly.
4582                  */
4583                 start = pgdat->node_start_pfn & ~(MAX_ORDER_NR_PAGES - 1);
4584                 end = pgdat->node_start_pfn + pgdat->node_spanned_pages;
4585                 end = ALIGN(end, MAX_ORDER_NR_PAGES);
4586                 size =  (end - start) * sizeof(struct page);
4587                 map = alloc_remap(pgdat->node_id, size);
4588                 if (!map)
4589                         map = alloc_bootmem_node_nopanic(pgdat, size);
4590                 pgdat->node_mem_map = map + (pgdat->node_start_pfn - start);
4591         }
4592 #ifndef CONFIG_NEED_MULTIPLE_NODES
4593         /*
4594          * With no DISCONTIG, the global mem_map is just set as node 0's
4595          */
4596         if (pgdat == NODE_DATA(0)) {
4597                 mem_map = NODE_DATA(0)->node_mem_map;
4598 #ifdef CONFIG_HAVE_MEMBLOCK_NODE_MAP
4599                 if (page_to_pfn(mem_map) != pgdat->node_start_pfn)
4600                         mem_map -= (pgdat->node_start_pfn - ARCH_PFN_OFFSET);
4601 #endif /* CONFIG_HAVE_MEMBLOCK_NODE_MAP */
4602         }
4603 #endif
4604 #endif /* CONFIG_FLAT_NODE_MEM_MAP */
4605 }
4606
4607 void __paginginit free_area_init_node(int nid, unsigned long *zones_size,
4608                 unsigned long node_start_pfn, unsigned long *zholes_size)
4609 {
4610         pg_data_t *pgdat = NODE_DATA(nid);
4611
4612         /* pg_data_t should be reset to zero when it's allocated */
4613         WARN_ON(pgdat->nr_zones || pgdat->classzone_idx);
4614
4615         pgdat->node_id = nid;
4616         pgdat->node_start_pfn = node_start_pfn;
4617         init_zone_allows_reclaim(nid);
4618         calculate_node_totalpages(pgdat, zones_size, zholes_size);
4619
4620         alloc_node_mem_map(pgdat);
4621 #ifdef CONFIG_FLAT_NODE_MEM_MAP
4622         printk(KERN_DEBUG "free_area_init_node: node %d, pgdat %08lx, node_mem_map %08lx\n",
4623                 nid, (unsigned long)pgdat,
4624                 (unsigned long)pgdat->node_mem_map);
4625 #endif
4626
4627         free_area_init_core(pgdat, zones_size, zholes_size);
4628 }
4629
4630 #ifdef CONFIG_HAVE_MEMBLOCK_NODE_MAP
4631
4632 #if MAX_NUMNODES > 1
4633 /*
4634  * Figure out the number of possible node ids.
4635  */
4636 static void __init setup_nr_node_ids(void)
4637 {
4638         unsigned int node;
4639         unsigned int highest = 0;
4640
4641         for_each_node_mask(node, node_possible_map)
4642                 highest = node;
4643         nr_node_ids = highest + 1;
4644 }
4645 #else
4646 static inline void setup_nr_node_ids(void)
4647 {
4648 }
4649 #endif
4650
4651 /**
4652  * node_map_pfn_alignment - determine the maximum internode alignment
4653  *
4654  * This function should be called after node map is populated and sorted.
4655  * It calculates the maximum power of two alignment which can distinguish
4656  * all the nodes.
4657  *
4658  * For example, if all nodes are 1GiB and aligned to 1GiB, the return value
4659  * would indicate 1GiB alignment with (1 << (30 - PAGE_SHIFT)).  If the
4660  * nodes are shifted by 256MiB, 256MiB.  Note that if only the last node is
4661  * shifted, 1GiB is enough and this function will indicate so.
4662  *
4663  * This is used to test whether pfn -> nid mapping of the chosen memory
4664  * model has fine enough granularity to avoid incorrect mapping for the
4665  * populated node map.
4666  *
4667  * Returns the determined alignment in pfn's.  0 if there is no alignment
4668  * requirement (single node).
4669  */
4670 unsigned long __init node_map_pfn_alignment(void)
4671 {
4672         unsigned long accl_mask = 0, last_end = 0;
4673         unsigned long start, end, mask;
4674         int last_nid = -1;
4675         int i, nid;
4676
4677         for_each_mem_pfn_range(i, MAX_NUMNODES, &start, &end, &nid) {
4678                 if (!start || last_nid < 0 || last_nid == nid) {
4679                         last_nid = nid;
4680                         last_end = end;
4681                         continue;
4682                 }
4683
4684                 /*
4685                  * Start with a mask granular enough to pin-point to the
4686                  * start pfn and tick off bits one-by-one until it becomes
4687                  * too coarse to separate the current node from the last.
4688                  */
4689                 mask = ~((1 << __ffs(start)) - 1);
4690                 while (mask && last_end <= (start & (mask << 1)))
4691                         mask <<= 1;
4692
4693                 /* accumulate all internode masks */
4694                 accl_mask |= mask;
4695         }
4696
4697         /* convert mask to number of pages */
4698         return ~accl_mask + 1;
4699 }
4700
4701 /* Find the lowest pfn for a node */
4702 static unsigned long __init find_min_pfn_for_node(int nid)
4703 {
4704         unsigned long min_pfn = ULONG_MAX;
4705         unsigned long start_pfn;
4706         int i;
4707
4708         for_each_mem_pfn_range(i, nid, &start_pfn, NULL, NULL)
4709                 min_pfn = min(min_pfn, start_pfn);
4710
4711         if (min_pfn == ULONG_MAX) {
4712                 printk(KERN_WARNING
4713                         "Could not find start_pfn for node %d\n", nid);
4714                 return 0;
4715         }
4716
4717         return min_pfn;
4718 }
4719
4720 /**
4721  * find_min_pfn_with_active_regions - Find the minimum PFN registered
4722  *
4723  * It returns the minimum PFN based on information provided via
4724  * add_active_range().
4725  */
4726 unsigned long __init find_min_pfn_with_active_regions(void)
4727 {
4728         return find_min_pfn_for_node(MAX_NUMNODES);
4729 }
4730
4731 /*
4732  * early_calculate_totalpages()
4733  * Sum pages in active regions for movable zone.
4734  * Populate N_HIGH_MEMORY for calculating usable_nodes.
4735  */
4736 static unsigned long __init early_calculate_totalpages(void)
4737 {
4738         unsigned long totalpages = 0;
4739         unsigned long start_pfn, end_pfn;
4740         int i, nid;
4741
4742         for_each_mem_pfn_range(i, MAX_NUMNODES, &start_pfn, &end_pfn, &nid) {
4743                 unsigned long pages = end_pfn - start_pfn;
4744
4745                 totalpages += pages;
4746                 if (pages)
4747                         node_set_state(nid, N_HIGH_MEMORY);
4748         }
4749         return totalpages;
4750 }
4751
4752 /*
4753  * Find the PFN the Movable zone begins in each node. Kernel memory
4754  * is spread evenly between nodes as long as the nodes have enough
4755  * memory. When they don't, some nodes will have more kernelcore than
4756  * others
4757  */
4758 static void __init find_zone_movable_pfns_for_nodes(void)
4759 {
4760         int i, nid;
4761         unsigned long usable_startpfn;
4762         unsigned long kernelcore_node, kernelcore_remaining;
4763         /* save the state before borrow the nodemask */
4764         nodemask_t saved_node_state = node_states[N_HIGH_MEMORY];
4765         unsigned long totalpages = early_calculate_totalpages();
4766         int usable_nodes = nodes_weight(node_states[N_HIGH_MEMORY]);
4767
4768         /*
4769          * If movablecore was specified, calculate what size of
4770          * kernelcore that corresponds so that memory usable for
4771          * any allocation type is evenly spread. If both kernelcore
4772          * and movablecore are specified, then the value of kernelcore
4773          * will be used for required_kernelcore if it's greater than
4774          * what movablecore would have allowed.
4775          */
4776         if (required_movablecore) {
4777                 unsigned long corepages;
4778
4779                 /*
4780                  * Round-up so that ZONE_MOVABLE is at least as large as what
4781                  * was requested by the user
4782                  */
4783                 required_movablecore =
4784                         roundup(required_movablecore, MAX_ORDER_NR_PAGES);
4785                 corepages = totalpages - required_movablecore;
4786
4787                 required_kernelcore = max(required_kernelcore, corepages);
4788         }
4789
4790         /* If kernelcore was not specified, there is no ZONE_MOVABLE */
4791         if (!required_kernelcore)
4792                 goto out;
4793
4794         /* usable_startpfn is the lowest possible pfn ZONE_MOVABLE can be at */
4795         find_usable_zone_for_movable();
4796         usable_startpfn = arch_zone_lowest_possible_pfn[movable_zone];
4797
4798 restart:
4799         /* Spread kernelcore memory as evenly as possible throughout nodes */
4800         kernelcore_node = required_kernelcore / usable_nodes;
4801         for_each_node_state(nid, N_HIGH_MEMORY) {
4802                 unsigned long start_pfn, end_pfn;
4803
4804                 /*
4805                  * Recalculate kernelcore_node if the division per node
4806                  * now exceeds what is necessary to satisfy the requested
4807                  * amount of memory for the kernel
4808                  */
4809                 if (required_kernelcore < kernelcore_node)
4810                         kernelcore_node = required_kernelcore / usable_nodes;
4811
4812                 /*
4813                  * As the map is walked, we track how much memory is usable
4814                  * by the kernel using kernelcore_remaining. When it is
4815                  * 0, the rest of the node is usable by ZONE_MOVABLE
4816                  */
4817                 kernelcore_remaining = kernelcore_node;
4818
4819                 /* Go through each range of PFNs within this node */
4820                 for_each_mem_pfn_range(i, nid, &start_pfn, &end_pfn, NULL) {
4821                         unsigned long size_pages;
4822
4823                         start_pfn = max(start_pfn, zone_movable_pfn[nid]);
4824                         if (start_pfn >= end_pfn)
4825                                 continue;
4826
4827                         /* Account for what is only usable for kernelcore */
4828                         if (start_pfn < usable_startpfn) {
4829                                 unsigned long kernel_pages;
4830                                 kernel_pages = min(end_pfn, usable_startpfn)
4831                                                                 - start_pfn;
4832
4833                                 kernelcore_remaining -= min(kernel_pages,
4834                                                         kernelcore_remaining);
4835                                 required_kernelcore -= min(kernel_pages,
4836                                                         required_kernelcore);
4837
4838                                 /* Continue if range is now fully accounted */
4839                                 if (end_pfn <= usable_startpfn) {
4840
4841                                         /*
4842                                          * Push zone_movable_pfn to the end so
4843                                          * that if we have to rebalance
4844                                          * kernelcore across nodes, we will
4845                                          * not double account here
4846                                          */
4847                                         zone_movable_pfn[nid] = end_pfn;
4848                                         continue;
4849                                 }
4850                                 start_pfn = usable_startpfn;
4851                         }
4852
4853                         /*
4854                          * The usable PFN range for ZONE_MOVABLE is from
4855                          * start_pfn->end_pfn. Calculate size_pages as the
4856                          * number of pages used as kernelcore
4857                          */
4858                         size_pages = end_pfn - start_pfn;
4859                         if (size_pages > kernelcore_remaining)
4860                                 size_pages = kernelcore_remaining;
4861                         zone_movable_pfn[nid] = start_pfn + size_pages;
4862
4863                         /*
4864                          * Some kernelcore has been met, update counts and
4865                          * break if the kernelcore for this node has been
4866                          * satisified
4867                          */
4868                         required_kernelcore -= min(required_kernelcore,
4869                                                                 size_pages);
4870                         kernelcore_remaining -= size_pages;
4871                         if (!kernelcore_remaining)
4872                                 break;
4873                 }
4874         }
4875
4876         /*
4877          * If there is still required_kernelcore, we do another pass with one
4878          * less node in the count. This will push zone_movable_pfn[nid] further
4879          * along on the nodes that still have memory until kernelcore is
4880          * satisified
4881          */
4882         usable_nodes--;
4883         if (usable_nodes && required_kernelcore > usable_nodes)
4884                 goto restart;
4885
4886         /* Align start of ZONE_MOVABLE on all nids to MAX_ORDER_NR_PAGES */
4887         for (nid = 0; nid < MAX_NUMNODES; nid++)
4888                 zone_movable_pfn[nid] =
4889                         roundup(zone_movable_pfn[nid], MAX_ORDER_NR_PAGES);
4890
4891 out:
4892         /* restore the node_state */
4893         node_states[N_HIGH_MEMORY] = saved_node_state;
4894 }
4895
4896 /* Any regular memory on that node ? */
4897 static void __init check_for_regular_memory(pg_data_t *pgdat)
4898 {
4899 #ifdef CONFIG_HIGHMEM
4900         enum zone_type zone_type;
4901
4902         for (zone_type = 0; zone_type <= ZONE_NORMAL; zone_type++) {
4903                 struct zone *zone = &pgdat->node_zones[zone_type];
4904                 if (zone->present_pages) {
4905                         node_set_state(zone_to_nid(zone), N_NORMAL_MEMORY);
4906                         break;
4907                 }
4908         }
4909 #endif
4910 }
4911
4912 /**
4913  * free_area_init_nodes - Initialise all pg_data_t and zone data
4914  * @max_zone_pfn: an array of max PFNs for each zone
4915  *
4916  * This will call free_area_init_node() for each active node in the system.
4917  * Using the page ranges provided by add_active_range(), the size of each
4918  * zone in each node and their holes is calculated. If the maximum PFN
4919  * between two adjacent zones match, it is assumed that the zone is empty.
4920  * For example, if arch_max_dma_pfn == arch_max_dma32_pfn, it is assumed
4921  * that arch_max_dma32_pfn has no pages. It is also assumed that a zone
4922  * starts where the previous one ended. For example, ZONE_DMA32 starts
4923  * at arch_max_dma_pfn.
4924  */
4925 void __init free_area_init_nodes(unsigned long *max_zone_pfn)
4926 {
4927         unsigned long start_pfn, end_pfn;
4928         int i, nid;
4929
4930         /* Record where the zone boundaries are */
4931         memset(arch_zone_lowest_possible_pfn, 0,
4932                                 sizeof(arch_zone_lowest_possible_pfn));
4933         memset(arch_zone_highest_possible_pfn, 0,
4934                                 sizeof(arch_zone_highest_possible_pfn));
4935         arch_zone_lowest_possible_pfn[0] = find_min_pfn_with_active_regions();
4936         arch_zone_highest_possible_pfn[0] = max_zone_pfn[0];
4937         for (i = 1; i < MAX_NR_ZONES; i++) {
4938                 if (i == ZONE_MOVABLE)
4939                         continue;
4940                 arch_zone_lowest_possible_pfn[i] =
4941                         arch_zone_highest_possible_pfn[i-1];
4942                 arch_zone_highest_possible_pfn[i] =
4943                         max(max_zone_pfn[i], arch_zone_lowest_possible_pfn[i]);
4944         }
4945         arch_zone_lowest_possible_pfn[ZONE_MOVABLE] = 0;
4946         arch_zone_highest_possible_pfn[ZONE_MOVABLE] = 0;
4947
4948         /* Find the PFNs that ZONE_MOVABLE begins at in each node */
4949         memset(zone_movable_pfn, 0, sizeof(zone_movable_pfn));
4950         find_zone_movable_pfns_for_nodes();
4951
4952         /* Print out the zone ranges */
4953         printk("Zone ranges:\n");
4954         for (i = 0; i < MAX_NR_ZONES; i++) {
4955                 if (i == ZONE_MOVABLE)
4956                         continue;
4957                 printk(KERN_CONT "  %-8s ", zone_names[i]);
4958                 if (arch_zone_lowest_possible_pfn[i] ==
4959                                 arch_zone_highest_possible_pfn[i])
4960                         printk(KERN_CONT "empty\n");
4961                 else
4962                         printk(KERN_CONT "[mem %0#10lx-%0#10lx]\n",
4963                                 arch_zone_lowest_possible_pfn[i] << PAGE_SHIFT,
4964                                 (arch_zone_highest_possible_pfn[i]
4965                                         << PAGE_SHIFT) - 1);
4966         }
4967
4968         /* Print out the PFNs ZONE_MOVABLE begins at in each node */
4969         printk("Movable zone start for each node\n");
4970         for (i = 0; i < MAX_NUMNODES; i++) {
4971                 if (zone_movable_pfn[i])
4972                         printk("  Node %d: %#010lx\n", i,
4973                                zone_movable_pfn[i] << PAGE_SHIFT);
4974         }
4975
4976         /* Print out the early node map */
4977         printk("Early memory node ranges\n");
4978         for_each_mem_pfn_range(i, MAX_NUMNODES, &start_pfn, &end_pfn, &nid)
4979                 printk("  node %3d: [mem %#010lx-%#010lx]\n", nid,
4980                        start_pfn << PAGE_SHIFT, (end_pfn << PAGE_SHIFT) - 1);
4981
4982         /* Initialise every node */
4983         mminit_verify_pageflags_layout();
4984         setup_nr_node_ids();
4985         for_each_online_node(nid) {
4986                 pg_data_t *pgdat = NODE_DATA(nid);
4987                 free_area_init_node(nid, NULL,
4988                                 find_min_pfn_for_node(nid), NULL);
4989
4990                 /* Any memory on that node */
4991                 if (pgdat->node_present_pages)
4992                         node_set_state(nid, N_HIGH_MEMORY);
4993                 check_for_regular_memory(pgdat);
4994         }
4995 }
4996
4997 static int __init cmdline_parse_core(char *p, unsigned long *core)
4998 {
4999         unsigned long long coremem;
5000         if (!p)
5001                 return -EINVAL;
5002
5003         coremem = memparse(p, &p);
5004         *core = coremem >> PAGE_SHIFT;
5005
5006         /* Paranoid check that UL is enough for the coremem value */
5007         WARN_ON((coremem >> PAGE_SHIFT) > ULONG_MAX);
5008
5009         return 0;
5010 }
5011
5012 /*
5013  * kernelcore=size sets the amount of memory for use for allocations that
5014  * cannot be reclaimed or migrated.
5015  */
5016 static int __init cmdline_parse_kernelcore(char *p)
5017 {
5018         return cmdline_parse_core(p, &required_kernelcore);
5019 }
5020
5021 /*
5022  * movablecore=size sets the amount of memory for use for allocations that
5023  * can be reclaimed or migrated.
5024  */
5025 static int __init cmdline_parse_movablecore(char *p)
5026 {
5027         return cmdline_parse_core(p, &required_movablecore);
5028 }
5029
5030 early_param("kernelcore", cmdline_parse_kernelcore);
5031 early_param("movablecore", cmdline_parse_movablecore);
5032
5033 #endif /* CONFIG_HAVE_MEMBLOCK_NODE_MAP */
5034
5035 /**
5036  * set_dma_reserve - set the specified number of pages reserved in the first zone
5037  * @new_dma_reserve: The number of pages to mark reserved
5038  *
5039  * The per-cpu batchsize and zone watermarks are determined by present_pages.
5040  * In the DMA zone, a significant percentage may be consumed by kernel image
5041  * and other unfreeable allocations which can skew the watermarks badly. This
5042  * function may optionally be used to account for unfreeable pages in the
5043  * first zone (e.g., ZONE_DMA). The effect will be lower watermarks and
5044  * smaller per-cpu batchsize.
5045  */
5046 void __init set_dma_reserve(unsigned long new_dma_reserve)
5047 {
5048         dma_reserve = new_dma_reserve;
5049 }
5050
5051 void __init free_area_init(unsigned long *zones_size)
5052 {
5053         free_area_init_node(0, zones_size,
5054                         __pa(PAGE_OFFSET) >> PAGE_SHIFT, NULL);
5055 }
5056
5057 static int page_alloc_cpu_notify(struct notifier_block *self,
5058                                  unsigned long action, void *hcpu)
5059 {
5060         int cpu = (unsigned long)hcpu;
5061
5062         if (action == CPU_DEAD || action == CPU_DEAD_FROZEN) {
5063                 lru_add_drain_cpu(cpu);
5064                 drain_pages(cpu);
5065
5066                 /*
5067                  * Spill the event counters of the dead processor
5068                  * into the current processors event counters.
5069                  * This artificially elevates the count of the current
5070                  * processor.
5071                  */
5072                 vm_events_fold_cpu(cpu);
5073
5074                 /*
5075                  * Zero the differential counters of the dead processor
5076                  * so that the vm statistics are consistent.
5077                  *
5078                  * This is only okay since the processor is dead and cannot
5079                  * race with what we are doing.
5080                  */
5081                 refresh_cpu_vm_stats(cpu);
5082         }
5083         return NOTIFY_OK;
5084 }
5085
5086 void __init page_alloc_init(void)
5087 {
5088         hotcpu_notifier(page_alloc_cpu_notify, 0);
5089 }
5090
5091 /*
5092  * calculate_totalreserve_pages - called when sysctl_lower_zone_reserve_ratio
5093  *      or min_free_kbytes changes.
5094  */
5095 static void calculate_totalreserve_pages(void)
5096 {
5097         struct pglist_data *pgdat;
5098         unsigned long reserve_pages = 0;
5099         enum zone_type i, j;
5100
5101         for_each_online_pgdat(pgdat) {
5102                 for (i = 0; i < MAX_NR_ZONES; i++) {
5103                         struct zone *zone = pgdat->node_zones + i;
5104                         unsigned long max = 0;
5105
5106                         /* Find valid and maximum lowmem_reserve in the zone */
5107                         for (j = i; j < MAX_NR_ZONES; j++) {
5108                                 if (zone->lowmem_reserve[j] > max)
5109                                         max = zone->lowmem_reserve[j];
5110                         }
5111
5112                         /* we treat the high watermark as reserved pages. */
5113                         max += high_wmark_pages(zone);
5114
5115                         if (max > zone->present_pages)
5116                                 max = zone->present_pages;
5117                         reserve_pages += max;
5118                         /*
5119                          * Lowmem reserves are not available to
5120                          * GFP_HIGHUSER page cache allocations and
5121                          * kswapd tries to balance zones to their high
5122                          * watermark.  As a result, neither should be
5123                          * regarded as dirtyable memory, to prevent a
5124                          * situation where reclaim has to clean pages
5125                          * in order to balance the zones.
5126                          */
5127                         zone->dirty_balance_reserve = max;
5128                 }
5129         }
5130         dirty_balance_reserve = reserve_pages;
5131         totalreserve_pages = reserve_pages;
5132 }
5133
5134 /*
5135  * setup_per_zone_lowmem_reserve - called whenever
5136  *      sysctl_lower_zone_reserve_ratio changes.  Ensures that each zone
5137  *      has a correct pages reserved value, so an adequate number of
5138  *      pages are left in the zone after a successful __alloc_pages().
5139  */
5140 static void setup_per_zone_lowmem_reserve(void)
5141 {
5142         struct pglist_data *pgdat;
5143         enum zone_type j, idx;
5144
5145         for_each_online_pgdat(pgdat) {
5146                 for (j = 0; j < MAX_NR_ZONES; j++) {
5147                         struct zone *zone = pgdat->node_zones + j;
5148                         unsigned long present_pages = zone->present_pages;
5149
5150                         zone->lowmem_reserve[j] = 0;
5151
5152                         idx = j;
5153                         while (idx) {
5154                                 struct zone *lower_zone;
5155
5156                                 idx--;
5157
5158                                 if (sysctl_lowmem_reserve_ratio[idx] < 1)
5159                                         sysctl_lowmem_reserve_ratio[idx] = 1;
5160
5161                                 lower_zone = pgdat->node_zones + idx;
5162                                 lower_zone->lowmem_reserve[j] = present_pages /
5163                                         sysctl_lowmem_reserve_ratio[idx];
5164                                 present_pages += lower_zone->present_pages;
5165                         }
5166                 }
5167         }
5168
5169         /* update totalreserve_pages */
5170         calculate_totalreserve_pages();
5171 }
5172
5173 static void __setup_per_zone_wmarks(void)
5174 {
5175         unsigned long pages_min = min_free_kbytes >> (PAGE_SHIFT - 10);
5176         unsigned long lowmem_pages = 0;
5177         struct zone *zone;
5178         unsigned long flags;
5179
5180         /* Calculate total number of !ZONE_HIGHMEM pages */
5181         for_each_zone(zone) {
5182                 if (!is_highmem(zone))
5183                         lowmem_pages += zone->present_pages;
5184         }
5185
5186         for_each_zone(zone) {
5187                 u64 tmp;
5188
5189                 spin_lock_irqsave(&zone->lock, flags);
5190                 tmp = (u64)pages_min * zone->present_pages;
5191                 do_div(tmp, lowmem_pages);
5192                 if (is_highmem(zone)) {
5193                         /*
5194                          * __GFP_HIGH and PF_MEMALLOC allocations usually don't
5195                          * need highmem pages, so cap pages_min to a small
5196                          * value here.
5197                          *
5198                          * The WMARK_HIGH-WMARK_LOW and (WMARK_LOW-WMARK_MIN)
5199                          * deltas controls asynch page reclaim, and so should
5200                          * not be capped for highmem.
5201                          */
5202                         int min_pages;
5203
5204                         min_pages = zone->present_pages / 1024;
5205                         if (min_pages < SWAP_CLUSTER_MAX)
5206                                 min_pages = SWAP_CLUSTER_MAX;
5207                         if (min_pages > 128)
5208                                 min_pages = 128;
5209                         zone->watermark[WMARK_MIN] = min_pages;
5210                 } else {
5211                         /*
5212                          * If it's a lowmem zone, reserve a number of pages
5213                          * proportionate to the zone's size.
5214                          */
5215                         zone->watermark[WMARK_MIN] = tmp;
5216                 }
5217
5218                 zone->watermark[WMARK_LOW]  = min_wmark_pages(zone) + (tmp >> 2);
5219                 zone->watermark[WMARK_HIGH] = min_wmark_pages(zone) + (tmp >> 1);
5220
5221                 setup_zone_migrate_reserve(zone);
5222                 spin_unlock_irqrestore(&zone->lock, flags);
5223         }
5224
5225         /* update totalreserve_pages */
5226         calculate_totalreserve_pages();
5227 }
5228
5229 /**
5230  * setup_per_zone_wmarks - called when min_free_kbytes changes
5231  * or when memory is hot-{added|removed}
5232  *
5233  * Ensures that the watermark[min,low,high] values for each zone are set
5234  * correctly with respect to min_free_kbytes.
5235  */
5236 void setup_per_zone_wmarks(void)
5237 {
5238         mutex_lock(&zonelists_mutex);
5239         __setup_per_zone_wmarks();
5240         mutex_unlock(&zonelists_mutex);
5241 }
5242
5243 /*
5244  * The inactive anon list should be small enough that the VM never has to
5245  * do too much work, but large enough that each inactive page has a chance
5246  * to be referenced again before it is swapped out.
5247  *
5248  * The inactive_anon ratio is the target ratio of ACTIVE_ANON to
5249  * INACTIVE_ANON pages on this zone's LRU, maintained by the
5250  * pageout code. A zone->inactive_ratio of 3 means 3:1 or 25% of
5251  * the anonymous pages are kept on the inactive list.
5252  *
5253  * total     target    max
5254  * memory    ratio     inactive anon
5255  * -------------------------------------
5256  *   10MB       1         5MB
5257  *  100MB       1        50MB
5258  *    1GB       3       250MB
5259  *   10GB      10       0.9GB
5260  *  100GB      31         3GB
5261  *    1TB     101        10GB
5262  *   10TB     320        32GB
5263  */
5264 static void __meminit calculate_zone_inactive_ratio(struct zone *zone)
5265 {
5266         unsigned int gb, ratio;
5267
5268         /* Zone size in gigabytes */
5269         gb = zone->present_pages >> (30 - PAGE_SHIFT);
5270         if (gb)
5271                 ratio = int_sqrt(10 * gb);
5272         else
5273                 ratio = 1;
5274
5275         zone->inactive_ratio = ratio;
5276 }
5277
5278 static void __meminit setup_per_zone_inactive_ratio(void)
5279 {
5280         struct zone *zone;
5281
5282         for_each_zone(zone)
5283                 calculate_zone_inactive_ratio(zone);
5284 }
5285
5286 /*
5287  * Initialise min_free_kbytes.
5288  *
5289  * For small machines we want it small (128k min).  For large machines
5290  * we want it large (64MB max).  But it is not linear, because network
5291  * bandwidth does not increase linearly with machine size.  We use
5292  *
5293  *      min_free_kbytes = 4 * sqrt(lowmem_kbytes), for better accuracy:
5294  *      min_free_kbytes = sqrt(lowmem_kbytes * 16)
5295  *
5296  * which yields
5297  *
5298  * 16MB:        512k
5299  * 32MB:        724k
5300  * 64MB:        1024k
5301  * 128MB:       1448k
5302  * 256MB:       2048k
5303  * 512MB:       2896k
5304  * 1024MB:      4096k
5305  * 2048MB:      5792k
5306  * 4096MB:      8192k
5307  * 8192MB:      11584k
5308  * 16384MB:     16384k
5309  */
5310 int __meminit init_per_zone_wmark_min(void)
5311 {
5312         unsigned long lowmem_kbytes;
5313
5314         lowmem_kbytes = nr_free_buffer_pages() * (PAGE_SIZE >> 10);
5315
5316         min_free_kbytes = int_sqrt(lowmem_kbytes * 16);
5317         if (min_free_kbytes < 128)
5318                 min_free_kbytes = 128;
5319         if (min_free_kbytes > 65536)
5320                 min_free_kbytes = 65536;
5321         setup_per_zone_wmarks();
5322         refresh_zone_stat_thresholds();
5323         setup_per_zone_lowmem_reserve();
5324         setup_per_zone_inactive_ratio();
5325         return 0;
5326 }
5327 module_init(init_per_zone_wmark_min)
5328
5329 /*
5330  * min_free_kbytes_sysctl_handler - just a wrapper around proc_dointvec() so 
5331  *      that we can call two helper functions whenever min_free_kbytes
5332  *      changes.
5333  */
5334 int min_free_kbytes_sysctl_handler(ctl_table *table, int write, 
5335         void __user *buffer, size_t *length, loff_t *ppos)
5336 {
5337         proc_dointvec(table, write, buffer, length, ppos);
5338         if (write)
5339                 setup_per_zone_wmarks();
5340         return 0;
5341 }
5342
5343 #ifdef CONFIG_NUMA
5344 int sysctl_min_unmapped_ratio_sysctl_handler(ctl_table *table, int write,
5345         void __user *buffer, size_t *length, loff_t *ppos)
5346 {
5347         struct zone *zone;
5348         int rc;
5349
5350         rc = proc_dointvec_minmax(table, write, buffer, length, ppos);
5351         if (rc)
5352                 return rc;
5353
5354         for_each_zone(zone)
5355                 zone->min_unmapped_pages = (zone->present_pages *
5356                                 sysctl_min_unmapped_ratio) / 100;
5357         return 0;
5358 }
5359
5360 int sysctl_min_slab_ratio_sysctl_handler(ctl_table *table, int write,
5361         void __user *buffer, size_t *length, loff_t *ppos)
5362 {
5363         struct zone *zone;
5364         int rc;
5365
5366         rc = proc_dointvec_minmax(table, write, buffer, length, ppos);
5367         if (rc)
5368                 return rc;
5369
5370         for_each_zone(zone)
5371                 zone->min_slab_pages = (zone->present_pages *
5372                                 sysctl_min_slab_ratio) / 100;
5373         return 0;
5374 }
5375 #endif
5376
5377 /*
5378  * lowmem_reserve_ratio_sysctl_handler - just a wrapper around
5379  *      proc_dointvec() so that we can call setup_per_zone_lowmem_reserve()
5380  *      whenever sysctl_lowmem_reserve_ratio changes.
5381  *
5382  * The reserve ratio obviously has absolutely no relation with the
5383  * minimum watermarks. The lowmem reserve ratio can only make sense
5384  * if in function of the boot time zone sizes.
5385  */
5386 int lowmem_reserve_ratio_sysctl_handler(ctl_table *table, int write,
5387         void __user *buffer, size_t *length, loff_t *ppos)
5388 {
5389         proc_dointvec_minmax(table, write, buffer, length, ppos);
5390         setup_per_zone_lowmem_reserve();
5391         return 0;
5392 }
5393
5394 /*
5395  * percpu_pagelist_fraction - changes the pcp->high for each zone on each
5396  * cpu.  It is the fraction of total pages in each zone that a hot per cpu pagelist
5397  * can have before it gets flushed back to buddy allocator.
5398  */
5399
5400 int percpu_pagelist_fraction_sysctl_handler(ctl_table *table, int write,
5401         void __user *buffer, size_t *length, loff_t *ppos)
5402 {
5403         struct zone *zone;
5404         unsigned int cpu;
5405         int ret;
5406
5407         ret = proc_dointvec_minmax(table, write, buffer, length, ppos);
5408         if (!write || (ret < 0))
5409                 return ret;
5410         for_each_populated_zone(zone) {
5411                 for_each_possible_cpu(cpu) {
5412                         unsigned long  high;
5413                         high = zone->present_pages / percpu_pagelist_fraction;
5414                         setup_pagelist_highmark(
5415                                 per_cpu_ptr(zone->pageset, cpu), high);
5416                 }
5417         }
5418         return 0;
5419 }
5420
5421 int hashdist = HASHDIST_DEFAULT;
5422
5423 #ifdef CONFIG_NUMA
5424 static int __init set_hashdist(char *str)
5425 {
5426         if (!str)
5427                 return 0;
5428         hashdist = simple_strtoul(str, &str, 0);
5429         return 1;
5430 }
5431 __setup("hashdist=", set_hashdist);
5432 #endif
5433
5434 /*
5435  * allocate a large system hash table from bootmem
5436  * - it is assumed that the hash table must contain an exact power-of-2
5437  *   quantity of entries
5438  * - limit is the number of hash buckets, not the total allocation size
5439  */
5440 void *__init alloc_large_system_hash(const char *tablename,
5441                                      unsigned long bucketsize,
5442                                      unsigned long numentries,
5443                                      int scale,
5444                                      int flags,
5445                                      unsigned int *_hash_shift,
5446                                      unsigned int *_hash_mask,
5447                                      unsigned long low_limit,
5448                                      unsigned long high_limit)
5449 {
5450         unsigned long long max = high_limit;
5451         unsigned long log2qty, size;
5452         void *table = NULL;
5453
5454         /* allow the kernel cmdline to have a say */
5455         if (!numentries) {
5456                 /* round applicable memory size up to nearest megabyte */
5457                 numentries = nr_kernel_pages;
5458                 numentries += (1UL << (20 - PAGE_SHIFT)) - 1;
5459                 numentries >>= 20 - PAGE_SHIFT;
5460                 numentries <<= 20 - PAGE_SHIFT;
5461
5462                 /* limit to 1 bucket per 2^scale bytes of low memory */
5463                 if (scale > PAGE_SHIFT)
5464                         numentries >>= (scale - PAGE_SHIFT);
5465                 else
5466                         numentries <<= (PAGE_SHIFT - scale);
5467
5468                 /* Make sure we've got at least a 0-order allocation.. */
5469                 if (unlikely(flags & HASH_SMALL)) {
5470                         /* Makes no sense without HASH_EARLY */
5471                         WARN_ON(!(flags & HASH_EARLY));
5472                         if (!(numentries >> *_hash_shift)) {
5473                                 numentries = 1UL << *_hash_shift;
5474                                 BUG_ON(!numentries);
5475                         }
5476                 } else if (unlikely((numentries * bucketsize) < PAGE_SIZE))
5477                         numentries = PAGE_SIZE / bucketsize;
5478         }
5479         numentries = roundup_pow_of_two(numentries);
5480
5481         /* limit allocation size to 1/16 total memory by default */
5482         if (max == 0) {
5483                 max = ((unsigned long long)nr_all_pages << PAGE_SHIFT) >> 4;
5484                 do_div(max, bucketsize);
5485         }
5486         max = min(max, 0x80000000ULL);
5487
5488         if (numentries < low_limit)
5489                 numentries = low_limit;
5490         if (numentries > max)
5491                 numentries = max;
5492
5493         log2qty = ilog2(numentries);
5494
5495         do {
5496                 size = bucketsize << log2qty;
5497                 if (flags & HASH_EARLY)
5498                         table = alloc_bootmem_nopanic(size);
5499                 else if (hashdist)
5500                         table = __vmalloc(size, GFP_ATOMIC, PAGE_KERNEL);
5501                 else {
5502                         /*
5503                          * If bucketsize is not a power-of-two, we may free
5504                          * some pages at the end of hash table which
5505                          * alloc_pages_exact() automatically does
5506                          */
5507                         if (get_order(size) < MAX_ORDER) {
5508                                 table = alloc_pages_exact(size, GFP_ATOMIC);
5509                                 kmemleak_alloc(table, size, 1, GFP_ATOMIC);
5510                         }
5511                 }
5512         } while (!table && size > PAGE_SIZE && --log2qty);
5513
5514         if (!table)
5515                 panic("Failed to allocate %s hash table\n", tablename);
5516
5517         printk(KERN_INFO "%s hash table entries: %ld (order: %d, %lu bytes)\n",
5518                tablename,
5519                (1UL << log2qty),
5520                ilog2(size) - PAGE_SHIFT,
5521                size);
5522
5523         if (_hash_shift)
5524                 *_hash_shift = log2qty;
5525         if (_hash_mask)
5526                 *_hash_mask = (1 << log2qty) - 1;
5527
5528         return table;
5529 }
5530
5531 /* Return a pointer to the bitmap storing bits affecting a block of pages */
5532 static inline unsigned long *get_pageblock_bitmap(struct zone *zone,
5533                                                         unsigned long pfn)
5534 {
5535 #ifdef CONFIG_SPARSEMEM
5536         return __pfn_to_section(pfn)->pageblock_flags;
5537 #else
5538         return zone->pageblock_flags;
5539 #endif /* CONFIG_SPARSEMEM */
5540 }
5541
5542 static inline int pfn_to_bitidx(struct zone *zone, unsigned long pfn)
5543 {
5544 #ifdef CONFIG_SPARSEMEM
5545         pfn &= (PAGES_PER_SECTION-1);
5546         return (pfn >> pageblock_order) * NR_PAGEBLOCK_BITS;
5547 #else
5548         pfn = pfn - zone->zone_start_pfn;
5549         return (pfn >> pageblock_order) * NR_PAGEBLOCK_BITS;
5550 #endif /* CONFIG_SPARSEMEM */
5551 }
5552
5553 /**
5554  * get_pageblock_flags_group - Return the requested group of flags for the pageblock_nr_pages block of pages
5555  * @page: The page within the block of interest
5556  * @start_bitidx: The first bit of interest to retrieve
5557  * @end_bitidx: The last bit of interest
5558  * returns pageblock_bits flags
5559  */
5560 unsigned long get_pageblock_flags_group(struct page *page,
5561                                         int start_bitidx, int end_bitidx)
5562 {
5563         struct zone *zone;
5564         unsigned long *bitmap;
5565         unsigned long pfn, bitidx;
5566         unsigned long flags = 0;
5567         unsigned long value = 1;
5568
5569         zone = page_zone(page);
5570         pfn = page_to_pfn(page);
5571         bitmap = get_pageblock_bitmap(zone, pfn);
5572         bitidx = pfn_to_bitidx(zone, pfn);
5573
5574         for (; start_bitidx <= end_bitidx; start_bitidx++, value <<= 1)
5575                 if (test_bit(bitidx + start_bitidx, bitmap))
5576                         flags |= value;
5577
5578         return flags;
5579 }
5580
5581 /**
5582  * set_pageblock_flags_group - Set the requested group of flags for a pageblock_nr_pages block of pages
5583  * @page: The page within the block of interest
5584  * @start_bitidx: The first bit of interest
5585  * @end_bitidx: The last bit of interest
5586  * @flags: The flags to set
5587  */
5588 void set_pageblock_flags_group(struct page *page, unsigned long flags,
5589                                         int start_bitidx, int end_bitidx)
5590 {
5591         struct zone *zone;
5592         unsigned long *bitmap;
5593         unsigned long pfn, bitidx;
5594         unsigned long value = 1;
5595
5596         zone = page_zone(page);
5597         pfn = page_to_pfn(page);
5598         bitmap = get_pageblock_bitmap(zone, pfn);
5599         bitidx = pfn_to_bitidx(zone, pfn);
5600         VM_BUG_ON(pfn < zone->zone_start_pfn);
5601         VM_BUG_ON(pfn >= zone->zone_start_pfn + zone->spanned_pages);
5602
5603         for (; start_bitidx <= end_bitidx; start_bitidx++, value <<= 1)
5604                 if (flags & value)
5605                         __set_bit(bitidx + start_bitidx, bitmap);
5606                 else
5607                         __clear_bit(bitidx + start_bitidx, bitmap);
5608 }
5609
5610 /*
5611  * This function checks whether pageblock includes unmovable pages or not.
5612  * If @count is not zero, it is okay to include less @count unmovable pages
5613  *
5614  * PageLRU check wihtout isolation or lru_lock could race so that
5615  * MIGRATE_MOVABLE block might include unmovable pages. It means you can't
5616  * expect this function should be exact.
5617  */
5618 bool has_unmovable_pages(struct zone *zone, struct page *page, int count,
5619                          bool skip_hwpoisoned_pages)
5620 {
5621         unsigned long pfn, iter, found;
5622         int mt;
5623
5624         /*
5625          * For avoiding noise data, lru_add_drain_all() should be called
5626          * If ZONE_MOVABLE, the zone never contains unmovable pages
5627          */
5628         if (zone_idx(zone) == ZONE_MOVABLE)
5629                 return false;
5630         mt = get_pageblock_migratetype(page);
5631         if (mt == MIGRATE_MOVABLE || is_migrate_cma(mt))
5632                 return false;
5633
5634         pfn = page_to_pfn(page);
5635         for (found = 0, iter = 0; iter < pageblock_nr_pages; iter++) {
5636                 unsigned long check = pfn + iter;
5637
5638                 if (!pfn_valid_within(check))
5639                         continue;
5640
5641                 page = pfn_to_page(check);
5642                 /*
5643                  * We can't use page_count without pin a page
5644                  * because another CPU can free compound page.
5645                  * This check already skips compound tails of THP
5646                  * because their page->_count is zero at all time.
5647                  */
5648                 if (!atomic_read(&page->_count)) {
5649                         if (PageBuddy(page))
5650                                 iter += (1 << page_order(page)) - 1;
5651                         continue;
5652                 }
5653
5654                 /*
5655                  * The HWPoisoned page may be not in buddy system, and
5656                  * page_count() is not 0.
5657                  */
5658                 if (skip_hwpoisoned_pages && PageHWPoison(page))
5659                         continue;
5660
5661                 if (!PageLRU(page))
5662                         found++;
5663                 /*
5664                  * If there are RECLAIMABLE pages, we need to check it.
5665                  * But now, memory offline itself doesn't call shrink_slab()
5666                  * and it still to be fixed.
5667                  */
5668                 /*
5669                  * If the page is not RAM, page_count()should be 0.
5670                  * we don't need more check. This is an _used_ not-movable page.
5671                  *
5672                  * The problematic thing here is PG_reserved pages. PG_reserved
5673                  * is set to both of a memory hole page and a _used_ kernel
5674                  * page at boot.
5675                  */
5676                 if (found > count)
5677                         return true;
5678         }
5679         return false;
5680 }
5681
5682 bool is_pageblock_removable_nolock(struct page *page)
5683 {
5684         struct zone *zone;
5685         unsigned long pfn;
5686
5687         /*
5688          * We have to be careful here because we are iterating over memory
5689          * sections which are not zone aware so we might end up outside of
5690          * the zone but still within the section.
5691          * We have to take care about the node as well. If the node is offline
5692          * its NODE_DATA will be NULL - see page_zone.
5693          */
5694         if (!node_online(page_to_nid(page)))
5695                 return false;
5696
5697         zone = page_zone(page);
5698         pfn = page_to_pfn(page);
5699         if (zone->zone_start_pfn > pfn ||
5700                         zone->zone_start_pfn + zone->spanned_pages <= pfn)
5701                 return false;
5702
5703         return !has_unmovable_pages(zone, page, 0, true);
5704 }
5705
5706 #ifdef CONFIG_CMA
5707
5708 static unsigned long pfn_max_align_down(unsigned long pfn)
5709 {
5710         return pfn & ~(max_t(unsigned long, MAX_ORDER_NR_PAGES,
5711                              pageblock_nr_pages) - 1);
5712 }
5713
5714 static unsigned long pfn_max_align_up(unsigned long pfn)
5715 {
5716         return ALIGN(pfn, max_t(unsigned long, MAX_ORDER_NR_PAGES,
5717                                 pageblock_nr_pages));
5718 }
5719
5720 /* [start, end) must belong to a single zone. */
5721 static int __alloc_contig_migrate_range(struct compact_control *cc,
5722                                         unsigned long start, unsigned long end)
5723 {
5724         /* This function is based on compact_zone() from compaction.c. */
5725         unsigned long nr_reclaimed;
5726         unsigned long pfn = start;
5727         unsigned int tries = 0;
5728         int ret = 0;
5729
5730         migrate_prep_local();
5731
5732         while (pfn < end || !list_empty(&cc->migratepages)) {
5733                 if (fatal_signal_pending(current)) {
5734                         ret = -EINTR;
5735                         break;
5736                 }
5737
5738                 if (list_empty(&cc->migratepages)) {
5739                         cc->nr_migratepages = 0;
5740                         pfn = isolate_migratepages_range(cc->zone, cc,
5741                                                          pfn, end, true);
5742                         if (!pfn) {
5743                                 ret = -EINTR;
5744                                 break;
5745                         }
5746                         tries = 0;
5747                 } else if (++tries == 5) {
5748                         ret = ret < 0 ? ret : -EBUSY;
5749                         break;
5750                 }
5751
5752                 nr_reclaimed = reclaim_clean_pages_from_list(cc->zone,
5753                                                         &cc->migratepages);
5754                 cc->nr_migratepages -= nr_reclaimed;
5755
5756                 ret = migrate_pages(&cc->migratepages,
5757                                     alloc_migrate_target,
5758                                     0, false, MIGRATE_SYNC);
5759         }
5760
5761         putback_movable_pages(&cc->migratepages);
5762         return ret > 0 ? 0 : ret;
5763 }
5764
5765 /**
5766  * alloc_contig_range() -- tries to allocate given range of pages
5767  * @start:      start PFN to allocate
5768  * @end:        one-past-the-last PFN to allocate
5769  * @migratetype:        migratetype of the underlaying pageblocks (either
5770  *                      #MIGRATE_MOVABLE or #MIGRATE_CMA).  All pageblocks
5771  *                      in range must have the same migratetype and it must
5772  *                      be either of the two.
5773  *
5774  * The PFN range does not have to be pageblock or MAX_ORDER_NR_PAGES
5775  * aligned, however it's the caller's responsibility to guarantee that
5776  * we are the only thread that changes migrate type of pageblocks the
5777  * pages fall in.
5778  *
5779  * The PFN range must belong to a single zone.
5780  *
5781  * Returns zero on success or negative error code.  On success all
5782  * pages which PFN is in [start, end) are allocated for the caller and
5783  * need to be freed with free_contig_range().
5784  */
5785 int alloc_contig_range(unsigned long start, unsigned long end,
5786                        unsigned migratetype)
5787 {
5788         unsigned long outer_start, outer_end;
5789         int ret = 0, order;
5790
5791         struct compact_control cc = {
5792                 .nr_migratepages = 0,
5793                 .order = -1,
5794                 .zone = page_zone(pfn_to_page(start)),
5795                 .sync = true,
5796                 .ignore_skip_hint = true,
5797         };
5798         INIT_LIST_HEAD(&cc.migratepages);
5799
5800         /*
5801          * What we do here is we mark all pageblocks in range as
5802          * MIGRATE_ISOLATE.  Because pageblock and max order pages may
5803          * have different sizes, and due to the way page allocator
5804          * work, we align the range to biggest of the two pages so
5805          * that page allocator won't try to merge buddies from
5806          * different pageblocks and change MIGRATE_ISOLATE to some
5807          * other migration type.
5808          *
5809          * Once the pageblocks are marked as MIGRATE_ISOLATE, we
5810          * migrate the pages from an unaligned range (ie. pages that
5811          * we are interested in).  This will put all the pages in
5812          * range back to page allocator as MIGRATE_ISOLATE.
5813          *
5814          * When this is done, we take the pages in range from page
5815          * allocator removing them from the buddy system.  This way
5816          * page allocator will never consider using them.
5817          *
5818          * This lets us mark the pageblocks back as
5819          * MIGRATE_CMA/MIGRATE_MOVABLE so that free pages in the
5820          * aligned range but not in the unaligned, original range are
5821          * put back to page allocator so that buddy can use them.
5822          */
5823
5824         ret = start_isolate_page_range(pfn_max_align_down(start),
5825                                        pfn_max_align_up(end), migratetype,
5826                                        false);
5827         if (ret)
5828                 return ret;
5829
5830         ret = __alloc_contig_migrate_range(&cc, start, end);
5831         if (ret)
5832                 goto done;
5833
5834         /*
5835          * Pages from [start, end) are within a MAX_ORDER_NR_PAGES
5836          * aligned blocks that are marked as MIGRATE_ISOLATE.  What's
5837          * more, all pages in [start, end) are free in page allocator.
5838          * What we are going to do is to allocate all pages from
5839          * [start, end) (that is remove them from page allocator).
5840          *
5841          * The only problem is that pages at the beginning and at the
5842          * end of interesting range may be not aligned with pages that
5843          * page allocator holds, ie. they can be part of higher order
5844          * pages.  Because of this, we reserve the bigger range and
5845          * once this is done free the pages we are not interested in.
5846          *
5847          * We don't have to hold zone->lock here because the pages are
5848          * isolated thus they won't get removed from buddy.
5849          */
5850
5851         lru_add_drain_all();
5852         drain_all_pages();
5853
5854         order = 0;
5855         outer_start = start;
5856         while (!PageBuddy(pfn_to_page(outer_start))) {
5857                 if (++order >= MAX_ORDER) {
5858                         ret = -EBUSY;
5859                         goto done;
5860                 }
5861                 outer_start &= ~0UL << order;
5862         }
5863
5864         /* Make sure the range is really isolated. */
5865         if (test_pages_isolated(outer_start, end, false)) {
5866                 pr_warn("alloc_contig_range test_pages_isolated(%lx, %lx) failed\n",
5867                        outer_start, end);
5868                 ret = -EBUSY;
5869                 goto done;
5870         }
5871
5872
5873         /* Grab isolated pages from freelists. */
5874         outer_end = isolate_freepages_range(&cc, outer_start, end);
5875         if (!outer_end) {
5876                 ret = -EBUSY;
5877                 goto done;
5878         }
5879
5880         /* Free head and tail (if any) */
5881         if (start != outer_start)
5882                 free_contig_range(outer_start, start - outer_start);
5883         if (end != outer_end)
5884                 free_contig_range(end, outer_end - end);
5885
5886 done:
5887         undo_isolate_page_range(pfn_max_align_down(start),
5888                                 pfn_max_align_up(end), migratetype);
5889         return ret;
5890 }
5891
5892 void free_contig_range(unsigned long pfn, unsigned nr_pages)
5893 {
5894         for (; nr_pages--; ++pfn)
5895                 __free_page(pfn_to_page(pfn));
5896 }
5897 #endif
5898
5899 #ifdef CONFIG_MEMORY_HOTPLUG
5900 static int __meminit __zone_pcp_update(void *data)
5901 {
5902         struct zone *zone = data;
5903         int cpu;
5904         unsigned long batch = zone_batchsize(zone), flags;
5905
5906         for_each_possible_cpu(cpu) {
5907                 struct per_cpu_pageset *pset;
5908                 struct per_cpu_pages *pcp;
5909
5910                 pset = per_cpu_ptr(zone->pageset, cpu);
5911                 pcp = &pset->pcp;
5912
5913                 local_irq_save(flags);
5914                 if (pcp->count > 0)
5915                         free_pcppages_bulk(zone, pcp->count, pcp);
5916                 drain_zonestat(zone, pset);
5917                 setup_pageset(pset, batch);
5918                 local_irq_restore(flags);
5919         }
5920         return 0;
5921 }
5922
5923 void __meminit zone_pcp_update(struct zone *zone)
5924 {
5925         stop_machine(__zone_pcp_update, zone, NULL);
5926 }
5927 #endif
5928
5929 void zone_pcp_reset(struct zone *zone)
5930 {
5931         unsigned long flags;
5932         int cpu;
5933         struct per_cpu_pageset *pset;
5934
5935         /* avoid races with drain_pages()  */
5936         local_irq_save(flags);
5937         if (zone->pageset != &boot_pageset) {
5938                 for_each_online_cpu(cpu) {
5939                         pset = per_cpu_ptr(zone->pageset, cpu);
5940                         drain_zonestat(zone, pset);
5941                 }
5942                 free_percpu(zone->pageset);
5943                 zone->pageset = &boot_pageset;
5944         }
5945         local_irq_restore(flags);
5946 }
5947
5948 #ifdef CONFIG_MEMORY_HOTREMOVE
5949 /*
5950  * All pages in the range must be isolated before calling this.
5951  */
5952 void
5953 __offline_isolated_pages(unsigned long start_pfn, unsigned long end_pfn)
5954 {
5955         struct page *page;
5956         struct zone *zone;
5957         int order, i;
5958         unsigned long pfn;
5959         unsigned long flags;
5960         /* find the first valid pfn */
5961         for (pfn = start_pfn; pfn < end_pfn; pfn++)
5962                 if (pfn_valid(pfn))
5963                         break;
5964         if (pfn == end_pfn)
5965                 return;
5966         zone = page_zone(pfn_to_page(pfn));
5967         spin_lock_irqsave(&zone->lock, flags);
5968         pfn = start_pfn;
5969         while (pfn < end_pfn) {
5970                 if (!pfn_valid(pfn)) {
5971                         pfn++;
5972                         continue;
5973                 }
5974                 page = pfn_to_page(pfn);
5975                 /*
5976                  * The HWPoisoned page may be not in buddy system, and
5977                  * page_count() is not 0.
5978                  */
5979                 if (unlikely(!PageBuddy(page) && PageHWPoison(page))) {
5980                         pfn++;
5981                         SetPageReserved(page);
5982                         continue;
5983                 }
5984
5985                 BUG_ON(page_count(page));
5986                 BUG_ON(!PageBuddy(page));
5987                 order = page_order(page);
5988 #ifdef CONFIG_DEBUG_VM
5989                 printk(KERN_INFO "remove from free list %lx %d %lx\n",
5990                        pfn, 1 << order, end_pfn);
5991 #endif
5992                 list_del(&page->lru);
5993                 rmv_page_order(page);
5994                 zone->free_area[order].nr_free--;
5995                 for (i = 0; i < (1 << order); i++)
5996                         SetPageReserved((page+i));
5997                 pfn += (1 << order);
5998         }
5999         spin_unlock_irqrestore(&zone->lock, flags);
6000 }
6001 #endif
6002
6003 #ifdef CONFIG_MEMORY_FAILURE
6004 bool is_free_buddy_page(struct page *page)
6005 {
6006         struct zone *zone = page_zone(page);
6007         unsigned long pfn = page_to_pfn(page);
6008         unsigned long flags;
6009         int order;
6010
6011         spin_lock_irqsave(&zone->lock, flags);
6012         for (order = 0; order < MAX_ORDER; order++) {
6013                 struct page *page_head = page - (pfn & ((1 << order) - 1));
6014
6015                 if (PageBuddy(page_head) && page_order(page_head) >= order)
6016                         break;
6017         }
6018         spin_unlock_irqrestore(&zone->lock, flags);
6019
6020         return order < MAX_ORDER;
6021 }
6022 #endif
6023
6024 static const struct trace_print_flags pageflag_names[] = {
6025         {1UL << PG_locked,              "locked"        },
6026         {1UL << PG_error,               "error"         },
6027         {1UL << PG_referenced,          "referenced"    },
6028         {1UL << PG_uptodate,            "uptodate"      },
6029         {1UL << PG_dirty,               "dirty"         },
6030         {1UL << PG_lru,                 "lru"           },
6031         {1UL << PG_active,              "active"        },
6032         {1UL << PG_slab,                "slab"          },
6033         {1UL << PG_owner_priv_1,        "owner_priv_1"  },
6034         {1UL << PG_arch_1,              "arch_1"        },
6035         {1UL << PG_reserved,            "reserved"      },
6036         {1UL << PG_private,             "private"       },
6037         {1UL << PG_private_2,           "private_2"     },
6038         {1UL << PG_writeback,           "writeback"     },
6039 #ifdef CONFIG_PAGEFLAGS_EXTENDED
6040         {1UL << PG_head,                "head"          },
6041         {1UL << PG_tail,                "tail"          },
6042 #else
6043         {1UL << PG_compound,            "compound"      },
6044 #endif
6045         {1UL << PG_swapcache,           "swapcache"     },
6046         {1UL << PG_mappedtodisk,        "mappedtodisk"  },
6047         {1UL << PG_reclaim,             "reclaim"       },
6048         {1UL << PG_swapbacked,          "swapbacked"    },
6049         {1UL << PG_unevictable,         "unevictable"   },
6050 #ifdef CONFIG_MMU
6051         {1UL << PG_mlocked,             "mlocked"       },
6052 #endif
6053 #ifdef CONFIG_ARCH_USES_PG_UNCACHED
6054         {1UL << PG_uncached,            "uncached"      },
6055 #endif
6056 #ifdef CONFIG_MEMORY_FAILURE
6057         {1UL << PG_hwpoison,            "hwpoison"      },
6058 #endif
6059 #ifdef CONFIG_TRANSPARENT_HUGEPAGE
6060         {1UL << PG_compound_lock,       "compound_lock" },
6061 #endif
6062 };
6063
6064 static void dump_page_flags(unsigned long flags)
6065 {
6066         const char *delim = "";
6067         unsigned long mask;
6068         int i;
6069
6070         BUILD_BUG_ON(ARRAY_SIZE(pageflag_names) != __NR_PAGEFLAGS);
6071
6072         printk(KERN_ALERT "page flags: %#lx(", flags);
6073
6074         /* remove zone id */
6075         flags &= (1UL << NR_PAGEFLAGS) - 1;
6076
6077         for (i = 0; i < ARRAY_SIZE(pageflag_names) && flags; i++) {
6078
6079                 mask = pageflag_names[i].mask;
6080                 if ((flags & mask) != mask)
6081                         continue;
6082
6083                 flags &= ~mask;
6084                 printk("%s%s", delim, pageflag_names[i].name);
6085                 delim