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