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