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