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